{"id":"d8c05067-0b6e-42a8-a673-4ccf2b230a55","arxiv_id":"2607.17261","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every skew Hamming set-pair system at threshold t has at most 2^(t+1) pairs, and this bound is tight.","lead":"This paper proves a sharp bound on how many word pairs can be stacked under a one-sided Hamming-distance condition, resolving an open problem posed by Alon, Jin, and Sudakov. The bound, 2^(t+1), matches the known two-sided case and is achieved by a characteristic-two algebraic kernel that may be reusable.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The proof is a clean linear-algebra argument with a carefully constructed kernel. I stress-tested the most delicate step identified by the reader: the non-cancellation of the determinant sum in Lemma 3.2. The argument is valid because the monomial z_{k_1,1}...z_{k_d,d} can only arise from the determinant whose row set is exactly S0; any other size-d subset of D omits at least one of the rows k_i, and within det Z_{S0} the identity permutation is the only one yielding that monomial since all variables are distinct. The coefficient is the nonzero product of α_k. This holds as a polynomial identity in K0[z], and algebraic independence of the z's then guarantees the element is nonzero in K. The subsequent triangular/rank step is also sound: M is lower triangular with nonzero diagonal, so rank m, and the factorization M=RHC^T through the 2^d-dimensional algebra A forces rank at most 2^d. The sharpness construction is consistent. I found no internal inconsistency, no missing edge case, and no unsupported assumption; therefore I would keep the reader's ACCEPT verdict unchanged.","tokens_in":4681,"tokens_out":28062,"duration_ms":250120,"concrete_test":"Independently verify Lemma 3.2 for a small nontrivial case: set d=2, D={1,2,3}, arbitrary nonzero α_1,α_2,α_3 in F2(s), and compute the coefficient of z_{1,1}z_{2,2} in the sum ∑_{|S|=2}(∏_{k∈S}α_k)det Z_S. It should be α_1α_2, with no contribution from S={1,3} or {2,3}; this directly checks the unique-monomial claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. I examined the two points on which the central claim m≤2^{t+1} depends. (1) Lemma 3.2's exact zero pattern. The cancellation worry is resolved by the unique-monomial argument: for S0={k_1<...<k_d}⊆D, the monomial z_{k_1,1}...z_{k_d,d} occurs only in det Z_{S0} (different row sets use different variables, and within det Z_{S0} only the identity permutation yields this monomial), with coefficient ∏_{k∈S0}α_k≠0. Hence the sum in (11) is a nonzero polynomial and β(P(a),P(b))≠0 for dist(a,b)≥d. (2) The rank argument: M is lower triangular with nonzero diagonal over K, so rank M=m, while M=RHC^T factors through A of dimension 2^d, giving rank M≤2^d. Both steps are internally consistent; no hidden assumption fails. The sharpness construction is consistent with the bound, so the central claim is supported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":4947,"tokens_out":8369,"duration_ms":74997,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"§1.2"},{"comment":"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.","section":"§3, Lemma 3.2"}],"recommendation":"accept","confidential_remarks":"I read the paper carefully and found the proof complete and correct. The only delicate point is the cancellation argument in Lemma 3.2; I checked it and the unique-monomial argument is sound. The paper is well written and the result is significant enough for publication. Recommend acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this closes the skew Hamming set-pair problem. The bound m ≤ 2^{t+1} is sharp, matches the two-sided case, and improves Furedi's binomial estimate by an exponential factor. The proof is a short, self-contained algebraic argument that I checked line by line.\n\nThe new ingredient is the bilinear kernel over K[e_1,...,e_d]/(e_i^2) in characteristic two, d=t+1. Each word maps to P(x) = ∏(1+c(x_k)u_k), and the bilinear form extracting the top coefficient has the exact zero pattern: β(P(a),P(b))=0 iff dist(a,b) ≤ d-1. The skew condition makes the matrix M lower triangular with nonzero diagonal, so rank M=m; the kernel dimension is 2^d, so m≤2^d. The sharpness construction is the natural one (binary words and complements). The proof is fully self-contained; the algebraic-independence step in Lemma 3.2 is the only delicate point, and the unique-monomial argument there is rigorous.\n\nSoft spots are minor. The paper is terse on the Helly-number/learning background; readers outside the area should consult [1]. The phrase \"graded commutative\" is slightly off: the algebra is just commutative (no exterior signs are used), though it doesn't affect anything. The AI declaration is transparent and the references are on point. No fitted parameters, no hidden assumptions, no circularity.\n\nThis is for anyone interested in set-pair inequalities or Helly-type questions for Hamming balls. It deserves a serious referee and will almost certainly be accepted; I would also cite it. The stress-test note found no issue, and I agree.\n\nRecommendation: send to peer review. I'd bring it to reading group.","headline":"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.","tokens_in":5374,"tokens_out":5048,"would_cite":true,"duration_ms":44322,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Skew Hamming set-pair families have size at most 2^{t+1}, and this bound is sharp.","keywords":["skew Hamming set-pair problem","Hamming distance","set-pair method","characteristic-two algebra","bilinear kernel","triangular matrix rank","sharp bound","Helly number of Hamming balls"],"falsifier":"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.","tokens_in":4628,"feed_emoji":"📏","tokens_out":3817,"duration_ms":33229,"temperature":0.7,"pith_summary":"The paper resolves the skew Hamming set-pair problem, proving that any ordered family of word pairs over an arbitrary alphabet—where each pair is at distance at least t+1 and every earlier first word is within distance t of a later second word—has size at most 2^{t+1}. This bound is tight, achieved by all binary words of length t+1. The proof introduces a bilinear kernel built from a characteristic-two algebra, which turns the skewed distance conditions into a lower triangular matrix with nonzero diagonal. Because the underlying algebra has dimension 2^{t+1}, the matrix rank is simultaneously full and capped at 2^{t+1}, forcing the family size to be at most that number. This settles an open question from work on Helly numbers of Hamming balls and improves the earlier bound of choose(2t+2, t+1) to the optimal exponential value.","feed_headline":"2^{t+1} is the exact limit for skew Hamming set-pair families","feed_subtitle":"A one-sided distance condition now yields the same tight exponential bound as the two-sided Helly-number result.","key_machinery":"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.","core_discovery":"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}.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Skew Hamming set-pair bound pinned to 2^{t+1}","Tight limit found for skew Hamming set-pairs","Sharp bound 2^{t+1} for skew Hamming families","Alon-Jin-Sudakov problem resolved: m ≤ 2^{t+1}","Characteristic-two algebra yields exact skew Hamming bound"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Skew Hamming set-pair bound pinned to 2^{t+1}","Tight limit found for skew Hamming set-pairs","Sharp bound 2^{t+1} for skew Hamming families","Alon-Jin-Sudakov problem resolved: m ≤ 2^{t+1}","Characteristic-two algebra yields exact skew Hamming bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000644,"raw_usage":{"total_tokens":2783,"prompt_tokens":715,"completion_tokens":2068,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":459,"completion_tokens_details":{"reasoning_tokens":1971}},"tokens_in":459,"tokens_out":2068,"duration_ms":12956,"temperature":1.0,"reasoning_tokens":1971,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T18:32:15.263934+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}