pith. sign in

arxiv: 2604.05607 · v1 · submitted 2026-04-07 · 🧮 math.CO

Forbidding Exactly One Hamming Distance

J\'ozsef Balogh , Ce Chen , Bowen Li This is my paper

Pith reviewed 2026-05-10 19:48 UTC · model grok-4.3

classification 🧮 math.CO
keywords independence numberHamming distancehypercubesunflower-free setsBCH codesconstant-weight codesextremal set theoryforbidden distances
0
0 comments X

The pith

For even r and fixed s, the s-independence number of the exact-r Hamming distance graph on the hypercube is Θ(2^n / n^{r/2}).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the asymptotic size of the largest subset of the n-dimensional hypercube such that no s+1 points lie at pairwise Hamming distance exactly r. It establishes that this size is on the order of 2^n divided by n to the power r/2 when r is even. The result resolves open questions on forbidden-distance problems in the Boolean cube by combining a combinatorial upper bound with explicit constructions. This pins down the growth rate of large codes avoiding a single prescribed distance.

Core claim

In the r-distance graph H_r(n) on the Boolean cube, two vertices are adjacent precisely when their Hamming distance equals r. For fixed integers s ≥ 2 and even r ≥ 2, the s-independence number α_s(H_r(n)) satisfies α_s(H_r(n)) = Θ(2^n / n^{r/2}). The upper bound is obtained by reducing the problem to an extremal question on sunflower-free set systems. The matching lower bound is supplied by algebraic constructions that employ BCH codes together with constant-weight codes.

What carries the argument

Reduction of s-independence in the exact-r distance graph to the maximum size of sunflower-free set systems, matched by BCH-code and constant-weight-code constructions.

If this is right

  • The precise asymptotic order of α_s(H_r(n)) is settled for every even r and fixed s.
  • Sunflower-free families yield the extremal upper bound for these independence numbers.
  • BCH codes and constant-weight codes produce explicit constructions achieving the lower bound.
  • The result holds uniformly across all even distances r ≥ 2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction technique may extend to odd r, possibly with a different polynomial factor in the denominator.
  • The connection to sunflower-free systems links single-distance forbidden problems directly to classical extremal set theory.
  • Computational enumeration for moderate n and small even r could verify whether the predicted order appears already in finite cases.

Load-bearing premise

The reduction from s-independent sets in the r-distance hypercube graph to sunflower-free set systems gives an upper bound tight enough to match the algebraic lower-bound constructions.

What would settle it

An explicit s-independent set in H_r(n) whose size exceeds C · 2^n / n^{r/2} for every constant C and some even r, or a proof that the sunflower-free upper bound is not tight.

read the original abstract

Addressing questions raised in recent papers, we study the $r$-distance graph $H_r(n)$ on the Boolean cube $\{0,1\}^n$, where two vertices are adjacent if their Hamming distance is exactly $r$. For fixed integers $s \ge 2$ and even $r \ge 2$, we determine the asymptotic order of the $s$-independence number $\alpha_s(H_r(n))$, showing that \[ \alpha_s\left(H_r(n)\right)=\Theta\left(\frac{2^n}{n^{r/2}}\right). \] The upper bound is derived via a reduction to extremal problems for sunflower-free set systems, while the lower bound is obtained using algebraic constructions based on BCH codes and constant-weight codes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript studies the r-distance graph H_r(n) on the Boolean hypercube, with edges between vectors at exact Hamming distance r. For fixed s ≥ 2 and even r ≥ 2, it determines the asymptotic order of the s-independence number, proving α_s(H_r(n)) = Θ(2^n / n^{r/2}). The upper bound is obtained by reducing an s-independent set to a sunflower-free family of r-subsets whose size is controlled by the known extremal function for sunflowers; the lower bound is realized by constant-weight subcodes of BCH codes of designed distance r+1.

Significance. The result supplies matching upper and lower bounds of the same order, thereby resolving the asymptotic growth rate for even r. The reduction to sunflower-free set systems is a clean application of extremal set theory, while the algebraic constructions via BCH codes furnish explicit, constructive lower bounds that achieve the stated order. This interplay between coding theory and sunflower extremal functions is a strength of the work.

minor comments (3)
  1. [§2] §2: the precise definition of an s-independent set in H_r(n) (no s vertices with all pairwise distances exactly r) is stated clearly, but a short sentence recalling the standard independence number when s=2 would aid readers.
  2. [§4.2] §4.2, construction paragraph: the constant-weight subcode is extracted from the BCH code; it would be helpful to include a one-line verification that the minimum distance r+1 indeed forbids any s-tuple at mutual distance exactly r.
  3. [Introduction] The paper focuses exclusively on even r; a brief remark in the introduction or conclusion on the obstruction for odd r would contextualize the result without expanding the scope.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our manuscript, including the recognition of the clean reduction to sunflower-free families and the explicit constructions via BCH codes. We appreciate the recommendation to accept.

Circularity Check

0 steps flagged

Derivation relies on independent extremal results and standard code constructions

full rationale

The paper reduces the upper bound on α_s(H_r(n)) to the extremal function for sunflower-free families of r-subsets (a classical result in extremal set theory independent of this manuscript), with the reduction shown to preserve the asymptotic order. The lower bound is realized explicitly by taking supports of constant-weight subcodes of BCH codes with designed distance r+1, invoking only standard facts from algebraic coding theory. No equation or claim reduces to a fitted parameter, self-definition, or load-bearing self-citation; the central Θ statement is obtained from two externally grounded directions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the validity of a reduction to sunflower-free set systems (an independent extremal problem) and on the existence and distance properties of BCH codes and constant-weight codes drawn from prior literature. No new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math Standard definitions and properties of the hypercube graph and Hamming distance
    Used to define H_r(n) and α_s.
  • domain assumption Existence and distance-distribution properties of BCH codes and constant-weight codes
    Invoked for the lower-bound construction.

pith-pipeline@v0.9.0 · 5422 in / 1489 out tokens · 56717 ms · 2026-05-10T19:48:28.514630+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · 1 internal anchor

  1. [1]

    R. C. Baker, G. Harman, and J. Pintz. The difference between consecutive primes, II.Pro- ceedings of the London Mathematical Society83.3, 2001, pp. 532–562

    work page 2001

  2. [2]

    Bannai and T

    E. Bannai and T. Ito.Algebraic Combinatorics I: Association Schemes. Benjamin Cummings Pub. Co., 1984

    work page 1984

  3. [3]

    L. A. Bassalygo. New Upper Bounds for Error Correcting Codes.Problems of Information Transmission1.4, 1965. English translation ofProblemy Peredachi Informatsii(1965), vol. 1, no. 4., pp. 32–35

    work page 1965

  4. [4]

    Bassalygo, G

    L. Bassalygo, G. Cohen, and G. Z´ emor. Codes with Forbidden Distances.Discrete Mathemat- ics213.1–3, 2000, pp. 3–11

    work page 2000

  5. [5]

    Bohman, M

    T. Bohman, M. Michelen, and D. Mubayi. The largestK r-free set of vertices in a random graph.arXiv 2603.16454

    work page arXiv

  6. [6]

    Bradaˇ c, M

    D. Bradaˇ c, M. Buci´ c, and B. Sudakov. Tur´ an numbers of sunflowers.Proceedings of the Amer- ican Mathematical Society151.03, 2023, pp. 961–975

    work page 2023

  7. [7]

    Castro-Silva, F

    D. Castro-Silva, F. M. de Oliveira Filho, L. Slot, and F. Vallentin. A recursive theta body for hypergraphs.Combinatorica43.5, 2023, pp. 909–938

    work page 2023

  8. [8]

    Cherkashin

    D. Cherkashin. On Set Systems Without Singleton Intersections.Discrete Mathematics Let- ters, 2024, pp. 85–88

    work page 2024

  9. [9]

    Cohen and G

    G. Cohen and G. Z´ emor. Subset sums and coding theory. Ast´ erisque 258, 1999. Ed. by J.-M. Deshouilliers, B. Landreau, and A. A. Yudin, pp. 327–339

    work page 1999

  10. [10]

    Delsarte

    P. Delsarte. An Algebraic Approach to the Association Schemes of Coding Theory, 1973. Also published asPhilips Research Reports Supplements, No. 10 (1973). 7

    work page 1973

  11. [11]

    Delsarte and V

    P. Delsarte and V. I. Levenshtein. Association Schemes and Coding Theory.IEEE Transac- tions on Information Theory44.6, 1998, pp. 2477–2504

    work page 1998

  12. [12]

    D. Ellis. Intersection problems in extremal combinatorics: theorems, techniques and questions old and new.Surveys in combinatorics, 2022, pp. 115–173

    work page 2022

  13. [13]

    Erd˝ os, A

    P. Erd˝ os, A. Hajnal, M. Simonovits, V. T. S´ os, and E. Szemer´ edi. Tur´ an-Ramsey Theo- rems andK p-Independence Numbers.Combinatorics, Probability and Computing3.3, 1994, pp. 297–325

    work page 1994

  14. [14]

    Erd˝ os and C

    P. Erd˝ os and C. A. Rogers. The construction of certain graphs.Canadian J. Math.14, 1962, pp. 702–707

    work page 1962

  15. [15]

    P. Erd˝ os. A problem on independentr-tuples.Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math 8.93-95, 1965, p. 2

    work page 1965

  16. [16]

    P. Erd˝ os. Problems and results in graph theory and combinatorial analysis.Proceedings of the Fifth British Combinatorial Conference, 1975, pp. 169–192

    work page 1975

  17. [17]

    Frankl and Z

    P. Frankl and Z. F¨ uredi. Exact solution of some Tur´ an-type problems.Journal of Combina- torial Theory, Series A45.2, 1987, pp. 226–262

    work page 1987

  18. [18]

    Frankl and Z

    P. Frankl and Z. F¨ uredi. Forbidding Just One Intersection.Journal of Combinatorial Theory, Series A39.2, 1985, pp. 160–176

    work page 1985

  19. [19]

    Frankl and R

    P. Frankl and R. M. Wilson. Intersection theorems with geometric consequences.Combina- torica1.4, 1981, pp. 357–368

    work page 1981

  20. [20]

    F¨ uredi

    Z. F¨ uredi. On finite set-systems whose every intersection is a kernel of a star.Discrete math- ematics47, 1983, pp. 129–132

    work page 1983

  21. [21]

    Graham and N

    R. Graham and N. Sloane. Lower bounds for constant weight codes.IEEE Transactions on Information Theory26.1, 2003, pp. 37–43

    work page 2003

  22. [22]

    Gr¨ otschel, L

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver. Relaxations of vertex packing.Journal of Combi- natorial Theory, Series B40.3, 1986, pp. 330–343

    work page 1986

  23. [23]

    Linial, R

    N. Linial, R. Meshulam, and M. Tarsi. Matroidal bijections between graphs.Journal of Com- binatorial Theory, Series B45.1, 1988, pp. 31–44

    work page 1988

  24. [24]

    W. Linz. Set systems containing no singleton intersection and the Delsarte number.arXiv 2604.00418

    work page arXiv

  25. [25]

    Lov´ asz

    L. Lov´ asz. On the Shannon capacity of a graph.IEEE Transactions on Information theory 25.1, 1979, pp. 1–7

    work page 1979

  26. [26]

    F. J. MacWilliams and N. J. A. Sloane.The Theory of Error-Correcting Codes. Vol. 16. North-Holland Mathematical Library. North-Holland, 1977

    work page 1977

  27. [27]

    Triangle-free subsets of the $r$-distance graph of the Hypercube

    P. Mukkamala. Triangle-free subsets of the Hypercube.arXiv:2506.18782

    work page internal anchor Pith review Pith/arXiv arXiv

  28. [28]

    Skupie´ n

    Z. Skupie´ n. BCH codes and distance multi- or fractional colorings in hypercubes asymptoti- cally.Discrete Mathematics307.7, 2007. Cycles and Colourings 2003, pp. 990–1000. 5 Appendix: BCH Codes The description for this BCH code construction is not easy to locate, thus we include a proof here for completeness. One classical version of the BCH code corres...

    work page 2007