{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T04:20:27Z","timestamp":1691554827691},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T00:00:00Z","timestamp":1684368000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the problem of determining the minimum number <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000123_inline1.png\" \/><jats:tex-math>\n$f(n,k,d)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of affine subspaces of codimension <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000123_inline2.png\" \/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> that are required to cover all points of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000123_inline3.png\" \/><jats:tex-math>\n$\\mathbb{F}_2^n\\setminus \\{\\vec{0}\\}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> at least <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000123_inline4.png\" \/><jats:tex-math>\n$k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> times while covering the origin at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000123_inline5.png\" \/><jats:tex-math>\n$k - 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> times. The case <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000123_inline6.png\" \/><jats:tex-math>\n$k=1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is a classic result of Jamison, which was independently obtained by Brouwer and Schrijver for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000123_inline7.png\" \/><jats:tex-math>\n$d = 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. The value of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000123_inline8.png\" \/><jats:tex-math>\n$f(n,1,1)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> also follows from a well-known theorem of Alon and F\u00fcredi about coverings of finite grids in affine spaces over arbitrary fields. Here we determine the value of this function exactly in various ranges of the parameters. In particular, we prove that for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000123_inline9.png\" \/><jats:tex-math>\n$k\\geq 2^{n-d-1}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> we have <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000123_inline10.png\" \/><jats:tex-math>\n$f(n,k,d)=2^d k-\\left\\lfloor{\\frac{k}{2^{n-d}}}\\right\\rfloor$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, while for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000123_inline11.png\" \/><jats:tex-math>\n$n \\gt 2^{2^d k-k-d+1}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> we have <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000123_inline12.png\" \/><jats:tex-math>\n$f(n,k,d)=n + 2^d k -d-2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, and obtain asymptotic results between these two ranges. While previous work in this direction has primarily employed the polynomial method, we prove our results through more direct combinatorial and probabilistic arguments, and also exploit a connection to coding theory.<\/jats:p>","DOI":"10.1017\/s0963548323000123","type":"journal-article","created":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T05:58:25Z","timestamp":1684389505000},"page":"782-795","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Subspace coverings with multiplicities"],"prefix":"10.1017","volume":"32","author":[{"given":"Anurag","family":"Bishnoi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simona","family":"Boyadzhiyska","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shagnik","family":"Das","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tam\u00e1s","family":"M\u00e9sz\u00e1ros","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2023,5,18]]},"reference":[{"key":"S0963548323000123_ref20","doi-asserted-by":"publisher","DOI":"10.5486\/PMD.2011.5133"},{"key":"S0963548323000123_ref25","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.851748"},{"key":"S0963548323000123_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90013-4"},{"key":"S0963548323000123_ref2","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.2000.0350"},{"key":"S0963548323000123_ref17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.831751"},{"key":"S0963548323000123_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(92)90035-S"},{"key":"S0963548323000123_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-4221-y"},{"key":"S0963548323000123_ref23","unstructured":"[23] The Sage Developers. (2023) SageMath, the Sage Mathematics Software System (Version 9.0). The Sage Developers. https:\/\/www.sagemath.org."},{"key":"S0963548323000123_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2758-0"},{"key":"S0963548323000123_ref3","first-page":"105","volume-title":"Current Research Topics in Galois Geometry","author":"Ball","year":"2012"},{"key":"S0963548323000123_ref15","doi-asserted-by":"publisher","DOI":"10.1090\/ulect\/064"},{"key":"S0963548323000123_ref24","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12637"},{"key":"S0963548323000123_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00413-7"},{"key":"S0963548323000123_ref13","unstructured":"[13] Gurobi Optimization, LLC. (2023) Gurobi Optimizer Reference Manual. Gurobi Optimization, LLC. http:\/\/www.gurobi.com."},{"key":"S0963548323000123_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(77)90001-2"},{"key":"S0963548323000123_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-012-9783-2"},{"key":"S0963548323000123_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-009-0204-1"},{"key":"S0963548323000123_ref11","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.928288"},{"key":"S0963548323000123_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548317000566"},{"key":"S0963548323000123_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01876338"},{"key":"S0963548323000123_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58575-3"},{"key":"S0963548323000123_ref22","doi-asserted-by":"publisher","DOI":"10.1109\/18.992776"},{"key":"S0963548323000123_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF00123760"},{"key":"S0963548323000123_ref1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1993.1011"},{"key":"S0963548323000123_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2509-z"},{"key":"S0963548323000123_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000342"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548323000123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T12:49:51Z","timestamp":1691498991000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548323000123\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,18]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["S0963548323000123"],"URL":"https:\/\/doi.org\/10.1017\/s0963548323000123","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,18]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}