{"id":"493e95e6-f19f-439e-aa6e-cee9f6329a5f","arxiv_id":"2505.07706","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper bounds the maximum size of m-trifferent ternary codes, identifies a phase transition near m=2n/9, and connects the linear case to strong blocking sets.","lead":"This paper studies the largest family of ternary strings in which any three strings are all different in at least m positions, and proves that the growth changes sharply when m is about 2/9 of the length. It also links a linear version to geometric blocking sets and gives exact values for small lengths.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central phase-transition theorem is sound, but Theorem 4.7's random-line proof uses an unjustified reduction: failure of a strength-m strong blocking set does not imply that at most m-1 selected lines miss some (k-3)-subspace.","rationale":"The main phase-transition theorem and the Section 3 bounds (Chernoff alteration for the lower bound, AM-GM double counting for the upper threshold, and the refined upper bounds) check out; I found no issue there. The reader's flagged reliance on the strong-blocking bound from [7] is a normal citation and affects only the linear upper bound, so it does not seem load-bearing for the central claim. The gap that does matter is in Theorem 4.7: the proof's reduction of the strength-m failure event is false, as shown by an explicit k=5, m=2 configuration in which every (k-3)-subspace misses at least two selected lines even though deleting one point makes the H-intersection span a plane. The claimed linear lower bounds may still be true, but the current proof and inequality (5) do not establish them. Since the paper states these as main results, I would make acceptance conditional on repairing this proof rather than rejecting the paper.","tokens_in":14575,"tokens_out":42538,"duration_ms":435616,"concrete_test":"Re-do the failure probability calculation for Theorem 4.7 without the unsupported reduction, separating configurations by the set of deleted points and the number of selected lines through each point. For k=5, m=2, compute or upper-bound the probability of the obstruction described above (two lines through a deleted point p and four lines through a 4-arc in a plane S), and check whether it is already covered by the right-hand side of inequality (5). If the corrected union bound still gives positive probability for t = ceil(10.729k + 4.385m - 23.287), the theorem can be repaired; if the omitted term can dominate, the constants or the construction need revision.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The main threshold result (Theorem 1.2) and the Section 3 bounds appear correct. The concern is in the linear-section lower bound, Theorem 4.7, which is stated as a main result. In its proof, failure of B = union of t random lines is reduced to: there is a hyperplane H and a (k-3)-subspace H' such that at most m-1 of the lines miss H'. The probability bound (5) charges only this event. That reduction is not justified and is false in general. If after deleting R (|R|=m-1) the remaining points of B∩H span a subspace S of dimension at most k-3, a selected line can miss H' even when its intersection point with H lies in S, simply because H' avoids that point. Moreover, one deleted point can lie on many lines, so the number of lines missing H' need not be bounded by |R|. Concrete configuration (k=5, m=2): let H be a hyperplane, S a plane in H, p in H\\S. Take two lines through p not in H and four lines through four points of S with no three collinear, also not in H. After deleting p, the four survivor points span S, so B fails to be strong-blocking of strength 2. Yet every plane H' in H misses at least two of the lines: if p is not in H', the two p-lines miss H'; if p is in H', then H'∩S is a line containing at most two of the four survivor points, so the other two survivor lines miss H'. Thus the claimed implication, and hence the union bound, do not establish Theorem 4.7. The theorem may be true, but the stated proof is incomplete.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies T(n,m), the largest size of a ternary code in which every three distinct codewords triffer in at least m coordinates. The main result is a phase transition at m ≈ 2n/9: T(n,m) is bounded by a constant when m > (2/9+ε)n and grows exponentially when m < (2/9−ε)n (Theorem 1.2). The authors prove quantitative upper bounds (Theorems 1.5 and 1.7) and lower bounds (Theorem 1.8), establish an equivalence between linear m-trifferent codes and m-minimal codes / strong blocking sets with strength m (Section 4), give probabilistic constructions for linear codes, and compute small cases. The paper also draws a connection to sunflower-free families.","tokens_in":14936,"tokens_out":28013,"duration_ms":251687,"significance":"If the results hold, the paper gives a clean and nontrivial generalization of the trifference problem with a sharp threshold, quantitative bounds that improve on earlier work, and a useful bridge to finite geometry via m-minimal codes and strong blocking sets. The Section 3 arguments are careful and checkable: the Chernoff-based lower bound, the double-counting upper bounds with the Jensen step, and the P4-free graph argument all appear sound. The linear equivalence in Lemma 4.1 and the geometric reformulation in Lemma 4.4 are natural and potentially useful. The main weakness is the proof of the probabilistic lower bound in Theorem 4.7, which has a genuine gap and should be repaired before publication.","major_comments":[{"comment":"The reduction 'if B fails to be a strong blocking set with strength m then there exists a (k−3)-subspace H′ such that apart from at most m−1 lines, H′∩ℓ_i is non-empty' is not justified and is false in general. Once R (|R|=m−1) is deleted, the surviving points of B∩H may span a subspace S of dimension at most k−3; a line whose intersection point with H lies outside S misses every H′ contained in H that contains S, and the number of such lines is not bounded by |R| because one deleted point can lie on many selected lines. For example, for k=5,m=2, take H a hyperplane, S a plane in H, p∈H\\S, two lines through p and four lines through points of S with no three collinear; after deleting p the survivor points span S, yet every plane H′ in H misses at least two lines. Thus the claimed implication, and hence the probability estimate (5), do not bound the failure event. In addition, even if the implication were valid, the display multiplies only by the number of hyperplanes and omits a union over the choice of H′. The proof of Theorem 4.7 is therefore incomplete as written.","section":"§4.2, proof of Theorem 4.7"},{"comment":"In the backward direction of Lemma 4.1, the sentence 'Since x and y remain distinct and nonzero after deleting the coordinates in eS, we have (σ(x)\\eS)≠(σ(y)\\eS)' is false as a general statement: distinct nonzero codewords can have equal support when one is a scalar multiple of the other. Under the no-triffer-outside-S condition the intended conclusion may be salvageable with an additional case analysis, but as presented the proof of the m-minimal implies m-trifferent implication is incomplete. Since Lemma 4.4 and Corollary 4.5 depend on this equivalence, the gap should be repaired.","section":"§4, Lemma 4.1"}],"minor_comments":[{"comment":"The displayed definition of t in the proof of Theorem 3.4, as printed, does not imply m ≥ (2/9+ε)(n−t); the correct choice should be t ≈ n − m/(2/9+ε) (up to rounding). This appears to be a typographical error, but the proof should be corrected so that the chosen t yields the stated conclusion.","section":"§3, Theorem 3.4"},{"comment":"In the last line of the proof of Corollary 4.8, the exponent is printed as (n−5m+23)/10, while the statement and the bound |B|≤10k+5m−21 give (n−5m+21)/10. One of these is a typo and should be fixed.","section":"§4.2, Corollary 4.8"},{"comment":"For r=0 the bound contains the binomial coefficient C(n,2ℓ−1), which requires ℓ≥1; the statement should explicitly exclude or separately handle ℓ=0.","section":"§1, Theorem 1.5"},{"comment":"The name 'Kullback-Liebler' should be 'Kullback–Leibler'.","section":"§2"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the scope of math.CO and the central phase-transition theorem appears sound. The main obstacle is Section 4.2: Theorem 4.7 is a stated main result of the linear section and its proof has a substantial gap. I recommend major revision rather than rejection because the threshold theorem and Section 3 are solid and the linear lower bound may be repairable with a more careful union bound that accounts for the deleted points and for the choice of H′. The use of the lower bound on strong blocking sets from [7] as an external black box is acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's core is genuinely good: it proves the phase transition at m = 2n/9 for the generalized trifference problem, gives quantitative bounds that improve on Bassalygo et al. and on the recent trifference upper bound, and the equivalence between linear m-trifferent codes, m-minimal codes, and strong blocking sets with strength m is clean. The double-counting arguments in Section 3, including the Jensen step and the P4-free graph argument for small m, are careful and check out. I would be happy to see the nonlinear results published.\n\nThe soft spot is in Section 4, specifically the proof of Theorem 4.7. The reduction from “B fails to be a strong blocking set with strength m” to “there is a (k−3)-subspace H′ that all but at most m−1 of the random lines meet” does not hold. The stress-test note is right: after deleting m−1 points, the remaining points in a hyperplane H can span a subspace S of dimension at most k−3, but a deleted point can lie on many randomly chosen lines, so the number of lines missing H′ can far exceed m−1. The concrete k=5, m=2 configuration shows this failure explicitly. That means the probability bound in (5) does not bound the actual failure event, and the size bounds |B| ≤ 43k+18m−93 and the claimed improved 10k+5m−21 are not established. Corollary 4.8 inherits this gap. The theorem may still be true, but this proof is incomplete.\n\nMinor issues: Corollary 4.8 has a range where the floor is vacuous, and the exact small values in Section 5 are reported without code or raw data, so they are hard to verify. These are secondary.\n\nWho is this for? People working on trifference, perfect hashing, or strong blocking sets will find the nonlinear threshold and bounds valuable. The linear-section connection is also useful conceptually, but I would not cite the linear lower bound until the proof is repaired.","headline":"Solid phase-transition paper with an invalid step in the linear-code lower-bound proof; the nonlinear results are worth refereeing, but Theorem 4.7 needs a genuine fix.","tokens_in":15509,"tokens_out":3754,"would_cite":false,"duration_ms":35954,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D40","51E20","94B65"],"pacs":[],"model":"deepseek-v4-flash","headline":"For ternary codes in which every three words must disagree in at least m coordinates, the maximum size jumps from bounded to exponential when m crosses about 2n/9.","keywords":["generalized trifference codes","ternary codes","perfect hash codes","phase transition","strong blocking sets","m-minimal codes","probabilistic method","finite geometry"],"falsifier":"Exhibit a strong blocking set in $\\mathrm{PG}(k-1,3)$ with fewer than $4.55(k-1)$ points for some $k$, which would break the constant in Theorem 4.6; alternatively, construct a family of ternary codes with $m>(2/9+\\varepsilon)n$ whose size grows with $n$, contradicting Theorem 1.2.","tokens_in":14411,"feed_emoji":"🔢","tokens_out":17295,"duration_ms":148682,"temperature":0.7,"pith_summary":"This paper studies $T(n,m)$, the largest size of a ternary code of length $n$ in which every three distinct codewords triffer—that is, disagree three ways—in at least $m$ coordinates. Its central result is a phase transition: for any fixed $\\varepsilon>0$, $T(n,m)$ is bounded by a constant when $m>(2/9+\\varepsilon)n$, and grows exponentially in $n$ when $m<(2/9-\\varepsilon)n$. For the subcritical range $m=\\lfloor\\lambda n\\rfloor$ with $0<\\lambda<2/9$, the paper improves both upper and lower bounds, replacing the classical $(3/2)^n$-type growth with more precise exponential bases and polynomial factors. For the linear version, it proves that $m$-trifferent ternary linear codes are exactly $m$-minimal codes, whose generator columns form strong blocking sets of strength $m$ in the projective space $\\mathrm{PG}(k-1,3)$, and uses this geometric translation to bound the maximal linear size $T_L(n,m)$. The significance is that the long-open $m=1$ trifference problem sits at the boundary of a family of thresholds that are now understood to leading order.","feed_headline":"Ternary codes flip from constant to exponential at m≈2n/9","feed_subtitle":"Any three codewords differ in m spots; the paper proves the threshold and matching-rate bounds.","key_machinery":"Two mechanisms carry the argument. On the nonlinear side, Lemma 2.5 lets every upper bound proved on a structured subset $S\\subseteq\\{0,1,2\\}^n$ transfer to the whole space by averaging over translates, and the bounds double-count triples that triffer at a coordinate, using $r_i s_i t_i\\le (T/3)^3$ and concavity inequalities to control the concentration of the symbol $2$. On the lower side, the alteration method is driven by the fact that three random ternary symbols are all distinct with probability $2/9$, so the number of triffering positions in a random triple follows a binomial distribution with parameters $n$ and $2/9$, and a standard large-deviation bound gives exponential size after deleting one word from each bad triple. In the linear case, the key object is the $m$-minimal code: deleting any $m-1$ coordinates must leave a minimal code, and Lemma 4.4 identifies such codes with strong blocking sets of strength $m$ in $\\mathrm{PG}(k-1,3)$. This translation turns the size question into a finite-geometry question about how few points can remain strong blockers after the removal of any $m-1$ points.","core_discovery":"The paper's main claim, Theorem 1.2, is that $2/9$ is the critical density of coordinates for three-way disagreement. Whenever $m>(2/9+\\varepsilon)n$ the maximum code size $T(n,m)$ is bounded by a constant depending only on $\\varepsilon$; whenever $m<(2/9-\\varepsilon)n$ the maximum is at least exponential, with base $(1+\\delta)^n$ for some $\\delta>0$ depending only on $\\varepsilon$. The quantitative lower bound for $m=\\lfloor\\lambda n\\rfloor$ has exponential base $b(\\lambda)=2^{\\frac12 H(\\lambda,2/9)}$, which decreases from $3/\\sqrt{7}$ at $\\lambda=0$ to $1$ at $\\lambda=2/9$. On the upper side, the paper proves bounds of the form $(3/2)^n$ times binomial and polynomial factors, with a refined version governed by the smallest real root of $\\lambda-\\frac32 x(1-x)^2$. For linear codes, the paper establishes that an $m$-trifferent code is the same as an $m$-minimal code and that the columns of its generator matrix form a strong blocking set of strength $m$, leading to $T_L(n,m)\\le c\\,3^{(n-m)/4.55}$ and constructive lower bounds of $3^{\\lfloor(n-18m+93)/43\\rfloor}$, improved to $3^{\\lfloor(n-5m+21)/10\\rfloor}$ when $m=o(n)$.","pith_inferences":["By the same alteration argument, the analogous critical density for $q$-ary $k$-hash codes should be the probability that $k$ random $q$-ary symbols are all distinct, namely $q(q-1)\\cdots(q-k+1)/q^k$, with constant size forced above that density by the paper's double-counting upper bound.","A sharper lower bound on strong blocking sets in $\\mathrm{PG}(k-1,3)$ would immediately tighten the linear upper bound; the constructions here could be tested computationally for small $k$ to see whether the constant $4.55$ is close to optimal.","The sunflower-free connection in Section 5.3 suggests that any future improvement to sunflower-free set upper bounds could feed directly into the $m=1$ trifference problem, even though the bound derived in the paper is not competitive with the current $(3/2)^n$ upper bound.","The exact ILP computations for $(k,m)$ indicate a roughly linear growth of the minimal length as $m$ grows with $k$ fixed; extending that table would provide data for conjecturing the true constant in the linear bound."],"forward_implications":["For any fixed gap $\\varepsilon>0$, the maximum code size is constant above $m=(2/9+\\varepsilon)n$ and exponential below $m=(2/9-\\varepsilon)n$, so the growth rate has a genuine discontinuity at density $2/9$.","In the linear setting, every $m$-trifferent code of dimension $k$ needs length at least $4.55k+m-O(1)$, and random constructions achieve length about $43k+18m$ (or $10k+5m$ when $m=o(k)$), giving explicit trade-offs between redundancy and required three-way disagreement.","The upper bounds for small $m$ improve the polynomial factors attached to $(3/2)^n$: for example $T(n,2)\\le (10/n)(3/2)^n$, and monotonicity gives $T(n,3)\\le T(n,2)$.","The small-parameter computations fix $T(4,2)=4$, $T(5,2)=T(6,2)=6$, $T(4,3)=T(5,3)=3$, $T(6,3)=T(7,3)=4$, and $T_L(n,2)=3^3$ for $12\\le n\\le 15$ with $T_L(16,2)=3^4$.","The paper's closing remark indicates that the same methods apply to $q$-ary $k$-hash codes with larger alphabets and larger tuples."],"supporting_citations":[{"why":"Defines $k$-hash codes with distance and states an earlier threshold result that Theorem 3.3 extends.","marker":"[5]"},{"why":"Supplies the polynomial improvement on $T(n,1)$ used in Corollary 1.4 and the restricted-set averaging lemma behind the new upper bounds.","marker":"[6]"},{"why":"Provides the strong-blocking-set size lower bound $4.55(k-1)$ that Theorem 4.6 imports, and the minimal-code equivalence for $m=1$ that the paper generalizes.","marker":"[7]"},{"why":"Introduces the probabilistic construction of short minimal codes via strong blocking sets that Theorem 4.7 adapts to strength $m$.","marker":"[15]"},{"why":"Origin of the double-counting bound for perfect hash families, used in Theorems 3.3 and 3.7.","marker":"[16]"},{"why":"Gives the classical lower bound for the $m=1$ trifference problem and the probabilistic technique behind Theorem 1.8.","marker":"[17]"},{"why":"Characterizes minimal linear codes as cutting blocking sets; Lemma 4.4 generalizes this to $m$-minimal codes.","marker":"[22]"}],"fun_headline_variants":["Threshold: m=2n/9 divides constant and exponential ternary codes","Ternary code size jumps at m=2n/9 from constant to exponential","Phase transition at m≈2n/9: trifference codes go exponential","For m<2n/9 ternary codes grow exponentially; above, constant","2n/9 threshold: constant vs exponential for trifference codes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The linear upper bound imports, without proof in this paper, the published lower bound that every strong blocking set in $\\mathrm{PG}(k-1,3)$ has size at least $4.55(k-1)$; if that constant is not correct, the rate $3^{(n-m)/4.55}$ in Theorem 4.6 would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Threshold: m=2n/9 divides constant and exponential ternary codes","Ternary code size jumps at m=2n/9 from constant to exponential","Phase transition at m≈2n/9: trifference codes go exponential","For m<2n/9 ternary codes grow exponentially; above, constant","2n/9 threshold: constant vs exponential for trifference codes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001183,"raw_usage":{"total_tokens":4907,"prompt_tokens":988,"completion_tokens":3919,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":604,"completion_tokens_details":{"reasoning_tokens":3821}},"tokens_in":604,"tokens_out":3919,"duration_ms":29227,"temperature":1.0,"reasoning_tokens":3821,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:13:45.770500+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a strong blocking set in $\\mathrm{PG}(k-1,3)$ with fewer than $4.55(k-1)$ points for some $k$, which would break the constant in Theorem 4.6; alternatively, construct a family of ternary codes with $m>(2/9+\\varepsilon)n$ whose size grows with $n$, contradicting Theorem 1.2.","supporting_citations":[{"cited_title":"Bassalygo, M","cited_arxiv_id":null,"evidence_quote":"Defines $k$-hash codes with distance and states an earlier threshold result that Theorem 3.3 extends."},{"cited_title":"Bhandari and A","cited_arxiv_id":null,"evidence_quote":"Supplies the polynomial improvement on $T(n,1)$ used in Corollary 1.4 and the restricted-set averaging lemma behind the new upper bounds."},{"cited_title":"Bishnoi, J","cited_arxiv_id":null,"evidence_quote":"Provides the strong-blocking-set size lower bound $4.55(k-1)$ that Theorem 4.6 imports, and the minimal-code equivalence for $m=1$ that the paper generalizes."},{"cited_title":"H´ eger and Z","cited_arxiv_id":null,"evidence_quote":"Introduces the probabilistic construction of short minimal codes via strong blocking sets that Theorem 4.7 adapts to strength $m$."},{"cited_title":"K¨ orner","cited_arxiv_id":null,"evidence_quote":"Origin of the double-counting bound for perfect hash families, used in Theorems 3.3 and 3.7."},{"cited_title":"K¨ orner and K","cited_arxiv_id":null,"evidence_quote":"Gives the classical lower bound for the $m=1$ trifference problem and the probabilistic technique behind Theorem 1.8."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Characterizes minimal linear codes as cutting blocking sets; Lemma 4.4 generalizes this to $m$-minimal codes."}],"review_version":1}