Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 12 min ago
PreprintCC BY 4.0arXiv

The Asymptotic Number of Anticodes in Hamming Spaces

  • Anna-Lena Horlemann
  • Ananthakrishnan Ravi
Open at sourcePDFDOICite

Abstract

In the Hamming space 𝔽qn, a d-anticode is a subset in which every pair of points has Hamming distance at most d, or equivalently, a set of diameter at most d. Let mq(n,d) denote the maximum size of a d-anticode and let π’œq(n,d) be the family of all d-anticodes. We show that for fixed q, as nβ†’βˆž, the total number of d-anticodes satisfies |π’œq(n,d)|=2(1+o(1))mq(n,d) for 4≀ d≀ nβˆ’1, except when q=2 and d=nβˆ’1. We also count linear d-anticodes, that is, subspaces of 𝔽qn with diameter at most d. For fixed q and d, their number is polynomial in n. For growing d, we determine the exponential order as qΘq(d2+dlogq(n/d)) in the sublinear regime and qΘ(n2) when d/nβ†’Ξ±βˆˆ(0,1). In the near-full regime nβˆ’d=o(n), we obtain the sharper count q(1/4+o(1))n2. A random-generator construction further improves the binary lower bound for every fixed linear diameter.

Related

  1. An upper bound on the number of relevant variables in a bounded degree Boolean function on the Hamming graph
    Alexandr Valyuzhenich
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The crossing number and the unit-distance crossing number of the Hamming graphs H(d,3)=K_3^{box d}, and their realizations over many coordinate fields
    Haroldo Costa Silva Filho
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Quantitative tiling stability from quadratic discrepancy in Hamming spaces
    Valery, Grishin, Aryeh Lev Zabokritskiy
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Perfect codes as exact minimizers of quadratic discrepancy in q-ary Hamming spaces
    Aryeh Lev Zabokritskiy
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Asymptotic behaviour of the v-number of homogeneous ideals
    Antonino Ficarra, Emanuele Sgroi
    Journal of AlgebraPeer-reviewedLicence not statedFull text26 citedAlgebra & number theoryOpenAlex

Cite

BibTeXRIS
BibTeX
@misc{horlemann2026asymptotic,
  title = {{The Asymptotic Number of Anticodes in Hamming Spaces}},
  author = {Anna-Lena Horlemann and Ananthakrishnan Ravi},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.31618},
  eprint = {2610.31618},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.31618},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The Asymptotic Number of Anticodes in Hamming Spaces
AU  - Anna-Lena Horlemann
AU  - Ananthakrishnan Ravi
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2610.31618
UR  - https://arxiv.org/abs/2610.31618
AB  - In the Hamming space 𝔽_q^n, a d-anticode is a subset in which every pair of points has Hamming distance at most d, or equivalently, a set of diameter at most d. Let m_q(n,d) denote the maximum size of a d-anticode and let π’œ_q(n,d) be the family of all d-anticodes. We show that for fixed q, as nβ†’βˆž, the total number of d-anticodes satisfies |π’œ_q(n,d)|=2^(1+o(1))m_q(n,d) for 4≀ d≀ nβˆ’1, except when q=2 and d=nβˆ’1. We also count linear d-anticodes, that is, subspaces of 𝔽_q^n with diameter at most d. For fixed q and d, their number is polynomial in n. For growing d, we determine the exponential order as q^Θ_q(d^2+dlog_q(n/d)) in the sublinear regime and q^Θ(n^2) when d/nβ†’Ξ±βˆˆ(0,1). In the near-full regime nβˆ’d=o(n), we obtain the sharper count q^(1/4+o(1))n^2. A random-generator construction further improves the binary lower bound for every fixed linear diameter.
ER  -