REVIEW 3 major objections 4 minor 9 references
Maximal sets of a given diameter in Hamming cubes
T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Every d-maximal Hamming-cube set is small unless it contains a radius-1 ball.
desk verdict A genuine advance on the lifting-stability problem, with a real but local gap in Lemma 12 that is fixable without changing the main results. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument is carried by a template-refinement scheme. Fix a word $w\in S$; a regular template is a word over $[n]\cup\{\star\}$ that differs from $w$ wherever it is specified, and its weight is the number of specified positions. Starting from the empty template, the proof repeatedly replaces one wildcard by a letter, keeping a nontrivial fraction of the original set that fits the template; Proposition 8 controls this fraction, and Lemma 9 is the only place where the absence of $(L+1)$-balls enters, guaranteeing a point $r\in S$ at distance at least $d-L$ from any prescribed word. To prevent the fitting sets from becoming too large, Lemma 12 bounds the number of ball centers fitting a weight-$m$ template via a generalized sunflower lemma: after encoding each word at distance $k$ from $w$ by an auxiliary set system of size $2k$, the ordinary sunflower lemma forces a sunflower of words with respect to $w$, provided the number of petals $p$ exceeds the alphabet size $n$. The quantitative sunflower bound $\mathrm{Sun}(p,k)\le(Cp\log k)^k$ then yields the polynomial factors and the $8n^{2/3}$ in the exponent.
What would settle it
A single construction settles the dichotomy: a d-maximal set in $[n]^\infty$ with no 1-ball and size above $d^2(n+8n^{2/3})^d$ would refute Theorem 1; since the critical Lemma 11 is the bridge from set-sunflowers to word-sunflowers, a smaller counterexample would be a family of more than $\mathrm{Sun}(p,2k)$ words at distance $k$ from a base word that contains no p-sunflower of words for some $p>n$.
Extended reading notes
Core claim
The central claim is Theorem 1: if $S\subset[n]^\infty$ is d-maximal and contains no 1-ball, then $|S|\le d^2(n+8n^{2/3})^d$. Phrased as a dichotomy, every d-maximal set is either of size at most this quantity or contains a non-trivial Hamming ball. The constant is not the point; the qualitative content is that the only way to be large is to contain a ball, and the leading term $(n+o(n))^d$ is best possible, witnessed by the d-dimensional cube $[n]^d\times\{0\}$. The paper proves the same dichotomy in a stronger form for sets that avoid larger balls: for a d-maximal set with no $(L+1)$-ball, the collection $S^{(\ell)}$ of centers of $\ell$-balls in it has size at most $C d^{2L+2}(n+8n^{2/3})^d$, which in turn implies that the number of isomorphism types of d-maximal sets is finite. For the binary alphabet the paper separates growth bases: it constructs d-maximal sets of size $\binom{\lfloor 3d/2\rfloor}{d}\ge(2.59+o(1))^d$ and proves that every ball-free binary d-maximal set has size at most $(4-10^{-10})^d$.
Load-bearing premise
The load-bearing step is the generalized sunflower lemma: many words at a fixed distance from a base word must contain p words whose differing coordinates are pairwise disjoint, and the proof of that step needs p to be larger than the alphabet size.
Editorial extensions
If this is right
- Every d-maximal set in $[n]^\infty$ with no 1-ball has at most $d^2(n+8n^{2/3})^d$ points, so lifting-stable large examples of diameter d necessarily contain a ball.
- The d-dimensional cube $[n]^d\times\{0\}$ is d-maximal and has $n^d$ elements, so the main bound is tight up to the $o(n)$ term.
- For the binary alphabet, ball-free d-maximal sets can be exponentially large with growth base $2.59+o(1)$, but no such set reaches base $4-10^{-10}$; the true growth base lies in between.
- Every d-maximal set has at least $(1/2)(d/\log 2d)^{2/3}$ elements, a polynomial bound far below the exponential constructions.
- For fixed d and alphabet size n, there are only finitely many d-maximal sets up to coordinate and alphabet permutations, so complete classification by finite search is possible in principle.
Reading between the lines
- Beyond the paper, the only alphabet-size-sensitive step is the word-sunflower translation; replacing that translation by another structure theorem would generalize the dichotomy to other metric spaces.
- The gap between the binary construction's growth base $2.59$ and the upper bound's base $4-10^{-10}$ is probably not intrinsic; a finite search for small d could map the true range.
- The exponent $2/3$ in the lower bound comes from the discrepancy-style rounding step, so a different rounding method could raise the proven minimum size, possibly toward the $2^d$ growth of the known constructions.
- Theorem 4's bounded skeleton of ball centers suggests that the right next object to classify is not the whole d-maximal set but the finite set of centers whose balls cover it.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies d-maximal subsets of the infinite Hamming cube [n]^∞. The main result, Theorem 1, states that a d-maximal set containing no 1-ball has size at most d^2(n+8n^{2/3})^d, which yields the dichotomy that every d-maximal set either has this bounded size or contains a nontrivial Hamming ball. The paper also proves a more general bound for the centers S^(ℓ), deduces finiteness of isomorphism types of d-maximal sets, gives a polynomial lower bound on the size of any d-maximal set, and provides improved upper and lower bounds for the binary alphabet. The proofs use regular templates, a generalized sunflower lemma, Kleitman's theorem, and Azuma's inequality.
Significance. If the main theorem is established, it resolves the lifting-stability question of Briggs, Feng and Wells and gives the first general upper bound for ball-free d-maximal sets. The finiteness of isomorphism types and the polynomial lower bound are also substantial additions. The argument is transparent, uses standard and independent tools, and contains no fitted parameters. The paper's main claim is plausible, but the proof of the central Lemma 12 contains a genuine gap that must be repaired before the main result can be considered proven.
major comments (3)
- [§1, proof of Lemma 12] The displayed distance identity after the pigeonhole step is not implied by the condition stated in the proof. For a coordinate i>m' with w_i=0, a^j_i=1, z_i=2, the condition that {i>m': a^j_i=z_i ≠ w_i} is contained in [m'] is satisfied, but [a^j_i ≠ z_i]=1 while [z_i ≠ w_i]+[a^j_i ≠ w_i]=2, so the equality fails. The same pigeonhole argument actually yields the stronger condition E_j ∩ {i>m': z_i ≠ w_i}=∅, because the sets E_j are pairwise disjoint and z differs from w in at most d<p positions. Under this stronger condition the identity becomes correct. This step is load-bearing: it is used to convert Ball(a^j,ℓ)⊂Ball(z,d) into Ball(b,ℓ+k−m′)⊂Ball(z,d), and hence it is essential for the sunflower-based bound on |S^(ℓ)_k[t(m)]|.
- [§1, proof of Lemma 11] The sentence 'Since C2(a1)=···=C2(ap)' is false as stated: the sunflower condition gives identical pairwise intersections and pairwise disjoint petals, not equality of the C2 sets. The intended inference is nevertheless valid, because the C2(a^j) form a sunflower: if (i,ℓ) belongs to two of them, it belongs to the common core and hence to all of them. This correction should be stated explicitly; as printed, the proof of the generalized sunflower lemma contains an incorrect assertion in a central lemma.
- [§1, proof of Lemma 12] The final contradiction with the definition of S^(ℓ) is not immediate as written. The definition forbids Ball(a^j,ℓ)⊂Ball(c,ℓ+1)⊂S, whereas the proof has established Ball(a^j,ℓ)⊂Ball(b,ℓ+k−m′)⊂S with possibly k−m′>1. For k−m′≥1, one can choose c on a shortest path from b to a^j with dist(b,c)=k−m′−1; then Ball(c,ℓ+1)⊂Ball(b,ℓ+k−m′)⊂S and Ball(a^j,ℓ)⊂Ball(c,ℓ+1), yielding the required contradiction. Without this additional argument, the final step of Lemma 12 does not follow from the definition of S^(ℓ).
minor comments (4)
- [§3, floating-coloring argument] The stopping condition 'as long as the number of floating variables is less than f + m' should read 'greater than f + m'; otherwise the process would not run when the number of floating variables is initially large.
- [§2, first paragraph] The sentence 'for otherwise n + 8n^{2/3} ≤ 2n' is false for n=100; the correct inequality for n<512 is n+8n^{2/3} ≥ 2n. The reduction to Corollary 14 should be corrected, and in fact the derivation in §2 yields the stated bound for all n≥2, so the assumption n≥100 is unnecessary.
- [§4, Lemma 17] The template t_i=1 used in Lemma 17 is regular with respect to w only after a coordinate-wise permutation making w_i=2 for every i. This WLOG reduction should be stated explicitly.
- [Corollary 5] The equality S=⋃_{ℓ≤d}⋃_{a∈S^(ℓ)}Ball(a,ℓ) and the subsequent counting of isomorphism types are only sketched; a few more sentences justifying the finite support argument would improve readability.
Circularity Check
No circularity found: the main derivation is self-contained and rests on independent external lemmas.
full rationale
The paper's central claim, Theorem 1 / Theorem 4, is derived from a sequence of lemmas (Proposition 8, Lemma 12, Corollary 13) whose inputs are standard external results: the sunflower lemma of Erdős–Rado/Alweiss–Lovett–Wu–Zhang/Bell–Chueluecha–Warnke, Kleitman's theorem, and Azuma's inequality. No parameter is fitted to the target quantity, and no conclusion is assumed in the proof. The only cited prior work by Briggs–Feng–Wells is motivational and used for a lower-bound construction, not as an input to the upper-bound proof. There are no self-citations by the authors that are load-bearing. The 'generalized sunflower lemma' (Lemma 11) is proved in the paper from the classical sunflower lemma, and while the attached skeptic note identifies a possible gap in the distance identity inside Lemma 12, that issue concerns correctness, not circularity: even if the displayed identity fails as stated, the proof does not presuppose Theorem 1 or reduce to a fitted input. The definition of S^(ℓ) and the template hierarchy are genuine proof devices rather than disguised versions of the conclusion. Consequently, the derivation is self-contained against external benchmarks and the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (4)
- standard math Zorn's lemma can be used to extend any set of diameter at most d to a d-maximal set.
- standard math Sunflower lemma with bound Sun(p,k) ≤ (C p log k)^k for C > 4.
- standard math Kleitman's theorem: for d < n, Ball_n(d/2) and [2] × Ball_{n-1}((d-1)/2) are largest diameter-d subsets of [2]^n.
- standard math Azuma's inequality and the entropy bound |Ball_n(r)| ≤ 2^{nH(r/n)} for r ≤ n/2.
Cite this review
Pith. "Pith review of Maximal sets of a given diameter in Hamming cubes." pith.science (2026). https://pith.science/paper/OOCYFF76
@misc{pith2026250710828,
author = {Pith},
title = {Pith review of: Maximal sets of a given diameter in Hamming cubes},
year = {2026},
howpublished = {\url{https://pith.science/paper/OOCYFF76}},
note = {Machine review of arXiv:2507.10828}
}
abstract
A subset of the Hamming cube over $n$-letter alphabet is said to be $d$-maximal if its diameter is $d$, and adding any point increases the diameter. Our main result shows that each $d$-maximal set is either of size at most $(n+o(n))^d$ or contains a non-trivial Hamming ball. The bound of $(n+o(n))^d$ is asymptotically tight. Additionally, we give a non-trivial lower bound on the size of any $d$-maximal set and show that the number of essentially different $d$-maximal sets is finite.
Reference graph
Works this paper leans on
-
[1]
Noga Alon and Joel H. Spencer. The probabilistic method . Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience [John Wiley & Sons], New York, second edi- tion, 2000. With an appendix on the life and work of Paul Erd˝ os
work page 2000
-
[2]
Improved bounds for the sunflower lemma
Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Improved bounds for the sunflower lemma. Ann. of Math. (2) , 194(3):795–815, 2021
work page 2021
-
[3]
Constructive algorithms for discrepancy minimization
Nikhil Bansal. Constructive algorithms for discrepancy minimization. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science—FOCS 2010, pages 3–10. IEEE Computer Soc., Los Alamitos, CA, 2010. arXiv:1002.2259
arXiv 2010
-
[4]
Tolson Bell, Suchakree Chueluecha, and Lutz Warnke. Note on sunflowers. Discrete Math. , 344(7):Paper No. 112367, 3, 2021. arXiv:2009.09327
work page Pith review arXiv 2021
-
[5]
Facets in the Vietoris—Rips complexes of hypercubes
Joseph Briggs, Ziqin Feng, and Chris Wells. Facets in the Vietoris—Rips complexes of hypercubes
-
[6]
Benjamin Doerr and Anand Srivastav. Multicolour discrepancies. Combin. Probab. Comput. , 12(4):365–399, 2003
work page 2003
-
[7]
P. Erd˝ os and R. Rado. Intersection theorems for systems of sets.J. London Math. Soc., 35:85–90, 1960
work page 1960
- [8]
Show all 9 references
-
[9]
Six standard deviations suffice
Joel Spencer. Six standard deviations suffice. Trans. Amer. Math. Soc. , 289(2):679–706, 1985. 14
1985
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.