Pith. sign in

REVIEW 2 major objections 4 minor 24 references

The generalized trifference problem

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2505.07706 v1 pith:765Q7F3O submitted 2025-05-12 math.CO cs.ITmath.IT

Anurag Bishnoi , Bart{l}omiej Kielak , Benedek Kovács , Zoltán Lóránt Nagy , Gábor Somlai , Máté Vizer , Zeyu Zheng This is my paper · ORCID
classification math.COcs.ITmath.IT MSC 05D4051E2094B65
keywords generalizedtrifferencecodesternaryperfecthashphasetransitionstrongblockingsetsm-minimalprobabilisticmethodfinitegeometry
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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)$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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.

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 (2)
  1. [§4.2, proof of Theorem 4.7] 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.
  2. [§4, Lemma 4.1] 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.
minor comments (4)
  1. [§3, Theorem 3.4] 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.
  2. [§4.2, Corollary 4.8] 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.
  3. [§1, Theorem 1.5] 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.
  4. [§2] The name 'Kullback-Liebler' should be 'Kullback–Leibler'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: all central bounds are proved from first principles; external citations are independent black boxes, not self-referential inputs.

full rationale

The main phase-transition result (Theorem 1.2) is proved self-containedly: the upper bound for m > (2/9+eps)n follows from the AM-GM double-counting argument in Theorem 3.3, and the lower bound for m < (2/9-eps)n follows from the random alteration argument with Chernoff bounds in Theorem 3.1. Neither direction assumes T(n,m) or any translated version of it. The Section 3 upper bounds use the in-paper density Lemma 2.5 together with elementary double-counting, graph P4-freeness, and entropy estimates; no fitted parameter is later renamed as a prediction. The linear section proves Lemma 4.1 and Lemma 4.4 in the paper, and the external inputs are the standard minimal-code/strong-blocking-set characterization and the published lower bound of 4.55(k-1) on strong blocking sets in PG(k-1,3). Although reference [7] shares an author with the present paper, it is a published, independently proved theorem used only as a black box, not a load-bearing self-citation that asserts the present target result. The skeptical concern about Theorem 4.7 is a possible gap in the probabilistic reduction, not an equivalence of output to input, so it does not constitute circularity. No equation is shown to equal its own input by construction, and no predictive claim is derived from the very data it predicts.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central results are self-contained combinatorics. The only unproved inputs are published black boxes: the Bhandari-Khetan bound for m=1 and the strong-blocking-set lower bound from [7]. No fitted constants enter the derivation, and no new entities are postulated. The threshold 2/9 comes from the exact probability 2/9 that three random ternary symbols are all distinct.

assumptions (5)
  • domain assumption Strong blocking sets in PG(k-1,3) have size at least 4.55(k-1), cited from [7] in Theorem 4.6.
    External known result used to derive the linear upper bound rate; not proved in this paper.
  • domain assumption The known upper bound T(n,1) <= c n^{-2/5}(3/2)^n from Bhandari and Khetan [6] is used in Corollary 1.4.
    Prior published result used as a black box to bootstrap small-m upper bounds.
  • standard math Standard Chernoff tail bound for Bin(n,2/9) in Theorem 3.1.
    Used in the probabilistic alteration lower bound; standard and uncontroversial.
  • standard math Gaussian binomial counting of subspaces and lines in PG(k-1,3), plus the union bound, in Theorem 4.7.
    Routine finite-geometry counting for the probabilistic construction of strong blocking sets.
  • standard math P4-free bipartite graphs have at most |V|-1 edges when they are also triangle-free, used in Theorem 3.6.
    Graph-theoretic bound used to control a class of 2-trifferent codes in a fixed coordinate support set.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The generalized trifference problem." pith.science (2026). https://pith.science/paper/765Q7F3O

@misc{pith2026250507706,
  author       = {Pith},
  title        = {Pith review of: The generalized trifference problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/765Q7F3O}},
  note         = {Machine review of arXiv:2505.07706}
}
abstract

We study the problem of finding the largest number $T(n, m)$ of ternary vectors of length $n$ such that for any three distinct vectors there are at least $m$ coordinates where they pairwise differ. For $m = 1$, this is the classical trifference problem which is wide open. We prove upper and lower bounds on $T(n, m)$ for various ranges of the parameter $m$ and determine the phase transition threshold on $m=m(n)$ where $T(n, m)$ jumps from constant to exponential in $n$. By relating the linear version of this problem to a problem on blocking sets in finite geometry, we give explicit constructions and probabilistic lower bounds. We also compute the exact values of this function and its linear variation for small parameters.

Figures

Figures reproduced from arXiv: 2505.07706 by the authors.

Figure 1
Figure 1. Graph indicating various bounds of the form ( [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    G. N. Alfarano, M. Borello, A. Neri, and A. Ravagnani. Three combinatorial perspectives on minimal codes. SIAM Journal on Discrete Mathematics , 36(1):461–489, 2022

    work page 2022

  2. [2]

    N. Alon, A. Bishnoi, S. Das, and A. Neri. Strong blocking sets and minimal codes from expander graphs. Transactions of the American Mathematical Society , 2024

    work page 2024

  3. [3]

    E. Arikan. An upper bound on the zero-error list-coding capacity. IEEE Transactions on Information Theory , 40(4):1237–1240, 1994

    work page 1994

  4. [4]

    A. Barg, G. R. Blakley, G. Kabatiansky, and C. Tavernier. Robust parent-identifying codes. In 2010 IEEE Information Theory Workshop , pages 1–4. IEEE, 2010

    work page 2010

  5. [5]

    Bassalygo, M

    L. Bassalygo, M. Burmester, A. Dyachkov, and G. Kabatianski. Hash codes. In Proceedings of the IEEE International Symposium on Information Theory . IEEE, 1997

    work page 1997

  6. [6]

    Bhandari and A

    S. Bhandari and A. Khetan. Improved upper bound for the size of a trifferent code. Combinatorica, 45(1):2, 2025

    work page 2025

  7. [7]

    Bishnoi, J

    A. Bishnoi, J. D’haeseleer, D. Gijswijt, and A. Potukuchi. Blocking sets, minimal codes and trifferent codes. Journal of LMS , 109.6:e12938, 2024

    work page 2024

  8. [8]

    T. M. Cover and J. A. Thomas. Elements of Information Theory . John Wiley & Sons, Inc., 1991

    work page 1991

Show all 24 references
  1. [9]

    Dalai, V

    M. Dalai, V. Guruswami, and J. Radhakrishnan. An improved bound on the zero-error list-decoding capacity of the 4/3 channel. IEEE Transactions on Information Theory , 66(2):749–756, 2019

    2019

  2. [10]

    A. A. Davydov, M. Giulietti, S. Marcugini, and F. Pambianco. Linear nonbinary covering codes and satu- rating sets in projective spaces. Advances in Mathematics of Communications , 5(1):119, 2011

    2011

  3. [11]

    Della Fiore and M

    S. Della Fiore and M. Dalai. Bounds on k-hash distances and rates of linear codes. arXiv preprint arXiv:2505.05239, 2025

    2025

  4. [12]

    M. L. Fredman and J. Koml´ os. On the size of separating systems and families of perfect hash functions. SIAM Journal on Algebraic Discrete Methods , 5(1):61–68, 1984

    1984

  5. [13]

    Gurobi Optimizer Reference Manual , 2024

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual , 2024. https://www.gurobi.com

    2024

  6. [14]

    Guruswami and A

    V. Guruswami and A. Riazanov. Beating fredman-koml´ os for perfect k-hashing. Journal of Combinatorial Theory, Series A , 188:105580, 2022

    2022

  7. [15]

    H´ eger and Z

    T. H´ eger and Z. L. Nagy. Short minimal codes and covering codes via strong blocking sets in projective spaces. IEEE Transactions on Information Theory , 68(2):881–890, 2021

    2021

  8. [16]

    K¨ orner

    J. K¨ orner. Coding of an information source having ambiguous alphabet and the entropy of graphs. In 6th Prague conference on information theory , pages 411–425, 1973

    1973

  9. [17]

    K¨ orner and K

    J. K¨ orner and K. Marton. New bounds for perfect hashing via information theory. European Journal of Combinatorics, 9(6):523–530, 1988

    1988

  10. [18]

    S. Kurz. Trifferent codes with small lengths. Examples and Counterexamples , 5:100139, 2024

    2024

  11. [19]

    F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes , volume 16. Elsevier, 1977

    1977

  12. [20]

    Naslund and W

    E. Naslund and W. Sawin. Upper bounds for sunflower-free sets. Forum of Mathematics, Sigma , 5:e15, 2017

    2017

  13. [21]

    Pohoata and D

    C. Pohoata and D. Zakharov. On the trifference problem for linear codes. IEEE Transactions on Information Theory, 68(11):7096–7099, 2022

    2022

  14. [22]

    C. Tang, Y. Qiu, Q. Liao, and Z. Zhou. Full characterization of minimal linear codes as cutting blocking sets. IEEE Transactions on Information Theory , 67(6):3690–3700, 2021

    2021

  15. [23]

    Wang and C

    H. Wang and C. Xing. Explicit constructions of perfect hash families from algebraic curves over finite fields. Journal of Combinatorial Theory, Series A , 93(1):112–124, 2001

    2001

  16. [24]

    Zaverucha

    G. Zaverucha. Hash families and cover-free families with cryptographic applications. 2010. 14

    2010

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.