REVIEW 2 minor 11 references
Tight bound for the skew Hamming set-pair problem
T0 review · 0 major / 2 minor · reviewed 2026-08-01 · deepseek-v4-flash
Pith's one-line read Skew Hamming set-pair families have size at most 2^{t+1}, and this bound is sharp.
desk verdict Closes the skew Hamming set-pair problem with a sharp 2^{t+1} bound and a genuinely new characteristic-two kernel; the proof is self-contained and checks out. 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 load-bearing mechanism is the characteristic-two bilinear kernel with exact zero pattern. Words are encoded as products P(x) = ∏_k (1 + c(x_k) u_k) in the 2^d-dimensional algebra K[e_1,…,e_d]/(e_1^2,…,e_d^2), with u_k = Σ_r z_{k,r} e_r and c an injective coding of the alphabet into a characteristic-two field. The bilinear form β extracts the coefficient of the top monomial e_1…e_d, and characteristic two makes every linear form square to zero and makes permanents equal determinants, so the kernel vanishes precisely when the Hamming distance is at most d−1. This converts the one-sided skew conditions into a triangular matrix while the algebra's dimension bounds the rank.
What would settle it
Construct, for t=1, n=2, |X|=2, a skew Hamming set-pair system with m=5 word pairs satisfying dist(a_i,b_i)≥2 and dist(a_i,b_j)≤1 for all i<j; the theorem predicts the maximum is 4, so any such family would disprove the claim.
Extended reading notes
Core claim
The central discovery is an exact encoding of the threshold relation dist(x,y) ≤ t by the zero pattern of a bilinear form. For d = t+1, the authors map each word x to an element P(x) in the characteristic-two algebra K[e_1,…,e_d]/(e_1^2,…,e_d^2), and define β(p,q) as the coefficient of e_1…e_d in pq. They prove that β(P(a),P(b)) = 0 exactly when dist(a,b) ≤ d−1, and β(P(a),P(b)) ≠ 0 when dist(a,b) ≥ d. Under the skew hypotheses, the matrix M_{ij} = β(P(a_i),P(b_j)) is lower triangular with nonzero diagonal, so rank M = m. Yet M factors as R H C^T, where H is a 2^d×2^d permutation matrix in the squarefree basis, so rank M ≤ 2^d. Therefore m ≤ 2^{t+1}.
Load-bearing premise
The proof relies on the existence of an injective coding of the alphabet into an infinite characteristic-two field and on choosing the z_{k,r} variables algebraically independent so that the top-coefficient sum in the kernel does not cancel; if such independence were impossible or the coding forced a relation, the exact zero pattern could fail.
Editorial extensions
If this is right
- The bound m ≤ 2^{t+1} is tight for every alphabet of size at least 2 and every n ≥ t+1, as shown by taking all binary words of length t+1.
- This answers the open problem of Alon, Jin, and Sudakov; the one-sided skew condition alone suffices for the same exponential bound that was previously known only under the two-sided condition.
- The result improves Furedi's inequality in this setting from binomial(2t+2, t+1) to the optimal 2^{t+1}.
- The characteristic-two bilinear kernel gives a self-contained linear-algebraic proof that does not depend on the alphabet size or word length n, so the same bound holds uniformly over all alphabets.
- The algebraic construction may be reused for other distance-constrained set-pair problems, as the authors note it is of independent interest.
Reading between the lines
- Beyond the paper: the same kernel construction could be adapted to weighted Hamming distances or other metrics where a d-dimensional exterior-type algebra admits an exact zero-pattern bilinear form, potentially yielding analogous tight bounds.
- Beyond the paper: the algebraic-independence trick used to prevent cancellation in the determinant sum suggests that a generic choice of variables can be replaced by a small explicit field extension or derandomized, at least when the alphabet is small.
- Beyond the paper: since the motivating problem came from online learning with set-valued feedback, the sharp Helly-type bound may have direct implications for the sample complexity of learning with Hamming-distance queries, though the paper does not discuss this.
- Beyond the paper: the triangular-rank argument is reminiscent of exterior-algebra proofs of skew set-pair inequalities; it hints at a common framework where a low-dimensional bilinear representation with exact zero patterns yields sharp bounds for other one-sided intersection conditions.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper resolves a problem posed by Alon, Jin, and Sudakov: for an ordered family ((a_i,b_i))_{i=1}^m of word pairs in X^n satisfying dist(a_i,b_i) ≥ t+1 and dist(a_i,b_j) ≤ t for every i<j, the bound m ≤ 2^{t+1} holds. The proof sets d=t+1, constructs a characteristic-two algebra A=K[e_1,...,e_d]/(e_1^2,...,e_d^2) of dimension 2^d, encodes each word x as P(x)=∏_{k=1}^n (1+c(x_k)u_k) with u_k=Σ_r z_{k,r}e_r, and defines a bilinear form β by extracting the coefficient of e_1···e_d. Lemma 3.2 establishes the exact zero pattern β(P(a),P(b))=0 iff dist(a,b)≤d-1, via a unique-monomial argument that prevents cancellation. The matrix M_ij=β(P(a_i),P(b_j)) is then lower triangular with nonzero diagonal, so rank M=m, while M factors through the 2^d-dimensional space A, yielding rank M≤2^d. A binary complement construction shows sharpness when |X|≥2. The proof is complete, self-contained, and does not depend on any prior result beyond standard linear algebra.
Significance. If correct, this is a clean and satisfying resolution of an open problem in extremal set-pair theory. The proof is short and elegant; the characteristic-two nilpotent algebra is a novel device that gives an exact zero pattern for the Hamming distance threshold. The construction has no free parameters and the rank argument is fully transparent. The paper also provides a simple sharpness example. The method may be of independent interest for related skew set-pair problems. The manuscript is well within the scope of a combinatorics journal and makes a solid contribution.
minor comments (2)
- [§1.2] The derivation of the previously known bound (4) via Furedi's inequality is correct, but it may help readers to explicitly state that |\hat{a_i}∩\hat{b_i}|=n−dist(a_i,b_i) and that the cross-condition dist(a_i,b_j)≤t translates to |\hat{a_i}∩\hat{b_j}|≥n−t, as the text currently does in prose. No change is required for correctness.
- [§3, Lemma 3.2] In the non-cancellation argument, the phrase 'the right-hand side of (11) is a nonzero polynomial in K_0[z_{k,r}]' could be made slightly more explicit by noting that the variables z_{k,r} are algebraically independent by construction, so a nonzero polynomial in them is nonzero in the fraction field K. This is already clear from the text, but stating it as a separate sentence would improve readability.
Circularity Check
No significant circularity: the proof is self-contained and derives the bound from a constructed bilinear kernel.
full rationale
The derivation is self-contained. Theorem 2.2 is proved by constructing the algebra A = K[e_1,...,e_d]/(e_1^2,...,e_d^2) of dimension 2^d, the encoding P(x), and the bilinear form β. Lemma 3.2 proves the exact zero pattern β(P(a),P(b)) = 0 iff dist(a,b) ≤ d-1 by explicitly computing P(a)P(b); the cancellation concern is resolved by the unique monomial z_{k_1,1}...z_{k_d,d} in det Z_{S0}, which is nonzero because the z-variables are algebraically independent by construction. This is not an assumption of the target result. The matrix M defined in (12) is then lower triangular with nonzero diagonal under exactly the skew hypotheses, so rank M = m, while the factorization M = R H C^T through A gives rank M ≤ 2^d. Neither the word length nor the alphabet enters the final bound, and the sharpness example is an independent construction, not part of the upper-bound proof. Citations to Alon--Jin--Sudakov and Furedi provide background and the previously known bound (4), but the theorem is not derived from them; no fitted parameter is renamed as a prediction and no self-citation is load-bearing.
Assumptions & free parameters
assumptions (4)
- domain assumption An injective coding map c: Σ → K0 exists from the finite set of appearing symbols into an infinite field of characteristic two.
- standard math The z_{k,r} variables are algebraically independent over K0.
- standard math The algebra A = K[e_1,...,e_d]/(e_1^2,...,e_d^2) has dimension 2^d with squarefree monomial basis.
- standard math In characteristic two, determinant equals permanent.
Cite this review
Pith. "Pith review of Tight bound for the skew Hamming set-pair problem." pith.science (2026). https://pith.science/paper/Y4SEQ47X
@misc{pith2026260717261,
author = {Pith},
title = {Pith review of: Tight bound for the skew Hamming set-pair problem},
year = {2026},
howpublished = {\url{https://pith.science/paper/Y4SEQ47X}},
note = {Machine review of arXiv:2607.17261}
}
abstract
Let $X$ be an alphabet, let $t\geq 0$ and $n\geq t+1$, and let $((a_i,b_i))_{i=1}^{m}$ be an ordered family of word pairs in $X^n$ satisfying $dist(a_i,b_i)\geq t+1$ for every $i$ and $dist(a_i,b_j)\leq t$ whenever $i<j$. We prove the sharp bound $m\leq 2^{t+1}$, thereby resolving a problem posed by Alon, Jin, and Sudakov. Our proof uses a linear-algebraic method based on a characteristic-two algebra, which may be of independent interest.
Reference graph
Works this paper leans on
-
[1]
N. Alon, Z. Jin, and B. Sudakov, The Helly number of Hamming balls and related problems,Transac- tions of the American Mathematical Society, in press, doi:10.1090/tran/9730; current author version; arXiv:2405.10275
-
[2]
B. Bollob´ as, On generalized graphs,Acta Mathematica Academiae Scientiarum Hungaricae16(1965), 447–452, doi:10.1007/BF01904851
- [3]
-
[4]
P. Frankl and N. Tokushige,Extremal Problems for Finite Sets, Student Mathematical Library, vol. 86, American Mathematical Society, Providence, RI, 2018, doi:10.1090/stml/086
-
[5]
Z. F¨ uredi, Geometrical solution of an intersection problem for two hypergraphs,European Journal of Combinatorics5(2) (1984), 133–136, doi:10.1016/S0195-6698(84)80026-8
-
[6]
G. Heged˝ us and P. Frankl, Variations on the Bollob´ as set-pair theorem,European Journal of Combina- torics120(2024), Article 103983, doi:10.1016/j.ejc.2024.103983; arXiv:2307.14704
arXiv 2024
-
[7]
G. Kalai, Intersection patterns of convex sets,Israel Journal of Mathematics48(2–3) (1984), 161–174, doi:10.1007/BF02761162
-
[8]
Lov´ asz, Flats in matroids and geometric graphs, in P
L. Lov´ asz, Flats in matroids and geometric graphs, in P. J. Cameron (ed.),Combinatorial Surveys: Proceedings of the Sixth British Combinatorial Conference, Academic Press, London–New York, 1977, pp. 45–86
1977
Show all 11 references
-
[9]
Raman, U
V. Raman, U. Subedi, and A. Tewari, Online learning with set-valued feedback, in S. Agrawal and A. Roth (eds.),Proceedings of the 37th Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 247, PMLR, 2024, pp. 4381–4412, proceedings.mlr.press/v247/raman...
2024 arXiv
-
[10]
Tuza, Inequalities for two set systems with prescribed intersections,Graphs and Combinatorics3 (1987), 75–80, doi:10.1007/BF01788531
Z. Tuza, Inequalities for two set systems with prescribed intersections,Graphs and Combinatorics3 (1987), 75–80, doi:10.1007/BF01788531
1987 doi
-
[11]
Tuza, Applications of the set-pair method in extremal hypergraph theory, in P
Z. Tuza, Applications of the set-pair method in extremal hypergraph theory, in P. Frankl, Z. F¨ uredi, G. O. H. Katona, and D. Mikl´ os (eds.),Extremal Problems for Finite Sets (Visegr´ ad, 1991), Bolyai Society Mathematical Studies, vol. 3, J´ anos Bolyai Mathematical Society...
1991
Reviewed August 1, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.