REVIEW 3 major objections 5 minor 13 references
Reasonable Bounds for Combinatorial Lines of Length Three
T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read The paper proves that any subset of the ternary cube [3]^n with density at least (log log log log n)^{-c} contains a combinatorial line of length three, improving the previous (log* n)^{-1/2} bound.
desk verdict First sub-tower bound for DHJ[3] via a genuinely new Shkredov-style framework; the main caveat is heavy dependence on same-author companion theorems. 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 object is product pseudorandomness: a 1-bounded function is (n', gamma)-product pseudorandom if, after any random restriction leaving at least n' coordinates, the probability that the restriction correlates by gamma or more with a product of single-coordinate 1-bounded functions is less than gamma. Its partner is the disjoint product E1 ⊠ E2, the analogue of a rectangle in the corners proof, consisting of strings whose set of 1s lies in E1 and whose set of 2s lies in E2. The proof alternates between two operations: uniformization converts non-pseudorandom E1 and E2 into pseudorandom ones while preserving density, and a Cauchy-Schwarz box-norm argument converts a large triple correlation over the DHJ[3] distribution into a four-fold correlation that yields a density increment. The imported inverse theorems (Theorems 2 and 3) are the engine that makes both operations work: they certify that large correlation over a connected or pairwise-connected distribution implies product correlation after random restriction.
What would settle it
Run a finite connectedness check on the auxiliary distributions in Tables 1-3: each projection onto any three coordinates is asserted to be connected, and the Cauchy-Schwarz chain invokes the four-ary inverse theorem through exactly those projections. A disconnected projection would break the proof; if all are connected, that link is sound. To decide Theorem 1 itself, one would need a counterexample to the imported inverse theorems at the stated quantitative scale, or an explicit line-free set in [3]^n with density above C(log log log log n)^{-c}, neither of which is known.
Extended reading notes
Core claim
On the paper's own terms, the discovery is Theorem 1: for every n and every A subset [3]^n with $3^{{-n}}$|A| >= C(log log log log n)^{-c}, there are x, y, z in A, not all equal, with each coordinate either constant or equal to (0,1,2). The proof proceeds by contradiction: assume A has no such line and run a density-increment scheme that maintains a set S of relative density $\alpha$ inside a 'disjoint product' E1 ⊠ E2, where E1 encodes the positions of 1s and E2 the positions of 2s. Each no-line step either increases $\alpha$ by $\Omega$($alpha^{15}$) or passes to a smaller instance on which E1 and E2 are product-pseudorandom; the increment is forced by a large box-norm correlation obtained through repeated Cauchy-Schwarz manipulations. The paper's central structural claim is that product pseudorandomness, rather than Fourier pseudorandomness, is the right notion of pseudorandomness in this setting, and that the imported inverse theorems reduce the necessary analysis to checking connectedness of several small auxiliary distributions.
Load-bearing premise
The load-bearing premise is that two structural theorems from the companion papers are correct and quantitatively as strong as stated: any large statistical dependence surviving random restrictions must be a product of independent per-coordinate factors, at the exact strength needed for the four-log threshold.
Editorial extensions
If this is right
- As a direct consequence of Theorem 1, any subset of [3]^n with density at least C(log log log log n)^{-c} contains a combinatorial line of length three; equivalently, the density Hales-Jewett theorem for k=3 holds with a fixed finite tower of exponentials in 1/density.
- The new bound subsumes and improves the previous Polymath bound, which required density Omega((log* n)^{-1/2}), so the paper reduces the required density for large n by a substantial margin.
- The proof's density-increment scheme gives a quantitative structure theorem: a set avoiding lines forces successive relative densities at least alpha + Omega(alpha^15) on nested disjoint products, with dimension shrinking only by a controlled factor, until contradiction.
- Consequently, to disprove Theorem 1 it would not be enough to find line-free sets at the known Behrend-style lower-bound scale exp(-(log n)^{1/2}); one would need a line-free set at the much larger four-fold-log density scale.
- The method demonstrates that the non-pairwise-connected DHJ[3] distribution can be controlled by decomposing it into connected pieces and then invoking inverse theorems for pairwise-connected and connected CSP distributions.
Reading between the lines
- The four-fold iterated logarithm is not obviously the end of the line: the bottleneck is the gamma >= exp(-epsilon^{-O_alpha(1)}) dependence in the imported inverse theorems, so any future improvement in those constants should translate directly into a better DHJ[3] bound.
- The disjoint-product and product-pseudorandomness dictionary may extend to other distributions whose support is not pairwise-connected, such as the corners distribution, potentially yielding comparable quantitative improvements for corners and multidimensional Szemerédi problems.
- A low-cost internal check of the proof is to verify computationally that the small distributions in Tables 1-3 have all the connected projections the proof claims; this does not test the inverse theorems, but it isolates the finite combinatorial part of the argument and would catch a discrete mistake near the Cauchy-Schwarz chain.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that every subset of [3]^n of density at least C (log log log log n)^{-c} contains a combinatorial line of length 3, improving the previous bound Omega((log* n)^{-1/2}) of Polymath 2012. The proof adapts Shkredov's density-increment proof for corners to DHJ[3], using a notion of product pseudorandomness and quantitative inverse theorems for pairwise-connected and connected distributions imported from two companion papers by the same authors. The argument maintains a set S of relative density inside a disjoint product E1 ⊠ E2, and alternates between a density-increment step (Sections 5-6) and a uniformization step (Section 7) that restores product pseudorandomness at a polynomial cost in dimension, leading to the iterated-logarithm bound.
Significance. If the proof is correct, this is a substantial quantitative advance for DHJ[3], replacing a tower-type bound with a very slowly growing iterated-logarithmic density threshold. The conceptual contribution — importing quantitative inverse theorems for CSPs into the Shkredov/Polymath framework — is novel and likely to be influential. The paper is carefully structured and the final parameter arithmetic is internally consistent. However, the central claim depends on the exact quantitative form of two black-box inverse theorems from unpublished companion papers, and on several connectivity checks that are asserted rather than shown; these points must be resolved before the result can be considered established.
major comments (3)
- [§3.2, §5-6] The proof of Theorem 1 relies on Theorems 2 and 3 and on the density-increment lemma from [BKLM24a, Section 8] as black boxes. These are same-author companion papers that are not proved or included here, and the references give no venue or preprint availability. The claimed bound (log log log log n)^{-c} depends exactly on the quantitative form gamma >= exp(-epsilon^{-O_alpha(1)}) (see §2.4 and the dimension loss in Theorem 6): if the true bounds were only double-exponential in epsilon^{-1}, or if Theorem 3 required a stronger connectivity hypothesis, the iteration would not close. The manuscript should either include complete proofs of these theorems in an appendix or rely on publicly available, refereed versions; as it stands, the main theorem is conditional on unverified external results.
- [§5.2, Lemma 5.8] The proof of Lemma 5.8 states that the projections of the support of (pi1(y), pi2(y), pi1(z), pi2(z)) to coordinates 234 and 123 are connected, and then says the result follows by expanding E1 and E2 and applying Theorem 3. This is not sufficient. Theorem 3 is asymmetric: to apply it to a function on a given coordinate, one needs the marginal on the other three coordinates to be connected. For the support S4 = {(0,0,0,0),(1,0,1,0),(0,2,0,2),(1,0,0,2)}, the projections to 134 and 124 are disconnected (the point (1,1,0) is isolated in 134, and (0,2,2) is isolated in 124). Hence Theorem 3 cannot directly control terms in the expansion where the non-constant factor is E1 - delta1 applied to pi1(z) or E2 - delta2 applied to pi2(y). An additional argument, for example a Cauchy-Schwarz reduction to correlations on the connected coordinates, is needed before this load-bearing lemma is justified.
- [§7, Lemma 7.1] The proof of Lemma 7.1 requires gamma to be substantially larger than m^{-1/72}: the displayed inequalities 'gamma - 101 m^{-1/72}' and the final bound E[mu(E1'')^2] >= mu(E1)^2 + 0.6 gamma^4 only give an index increment when gamma^2 >> m^{-1/72}. The lemma statement does not include any such hypothesis, and for gamma <= m^{-1/72} the proof's lower bounds are vacuous, so the claimed increment fails. In the final application the chosen gamma = exp(-exp(alpha_0^{-O(1)})) and the maintained dimension at least exp((log n)^{0.999}) do satisfy the needed condition, but this dependence should be stated explicitly in Lemma 7.1 or Theorem 6 rather than left implicit.
minor comments (5)
- [Abstract and Theorem 1] The theorem is stated for all positive integers n, but the iterated logarithm is not defined for small n and the statement is false for n = 1 (a singleton has no combinatorial line of length 3). It should be stated for all sufficiently large n, or the iterated logarithm and the constants should be defined so that small n are handled separately.
- [§1.3 and §3.1] The notation 'I ~ delta [n]' is used in Definition 3.1 but only 'I ~ 1-alpha [n]' is defined in Definition 1.2. Define the general notation explicitly to avoid ambiguity about whether delta denotes the probability of inclusion in the fixed set or the remaining set.
- [Tables 1-3] The tables list supports but not the masses of the distributions mu1, mu2, mu3. Since Theorem 3 requires each atom to have probability at least alpha and the connectivity checks depend on the support, please state the exact masses or explain how they are derived from the construction in Theorem 4.
- [§5.2, §6.1, §6.2] Several load-bearing connectivity assertions are only given as 'it can be checked' or 'can easily be seen' (in Lemmas 5.8, 6.1, 6.2, and 6.3). Given that the inverse theorems are applied only when these connectedness conditions hold, these checks should be written out explicitly or placed in an appendix.
- [Throughout] There are multiple typographical errors, including 'combiantorial' in the Introduction, the malformed density expression in the abstract, and stray spacing in equations. A careful proofreading pass is needed.
Circularity Check
No significant circularity: the core derivation reduces DHJ[3] to independent inverse theorems for connected CSP distributions, and the companion-paper dependency is a matter of completeness, not of circular inference.
full rationale
The paper's derivation chain assumes only that S contains no combinatorial line, then derives a lower bound on a 3-wise correlation (Lemma 5.3), converts it to a box-norm correlation (Theorem 4), uses product pseudorandomness to control error terms, and obtains a density increment (Theorem 5) and a uniformization step (Theorem 6). The load-bearing black boxes are Theorems 2 and 3, imported from the same authors' companion papers [BKLM24a, BKLM24b], and the density-increment lemma from [BKLM24a, Section 8]; these are stated with explicit hypotheses (pairwise-connected / connected distributions) that do not include the target DHJ[3] bound. Indeed, the paper explicitly notes that the DHJ[3] distribution is not pairwise-connected, and the new work is precisely to force DHJ[3] into that framework via Shkredov's corners argument. The quantitative bound gamma >= exp(-epsilon^{-O_alpha(1)}) from the companion theorems is used to set gamma = exp(-exp(alpha^{-C})), and the final density threshold depends on that relationship. However, this is a dependency on unproved (in the present paper) same-author results, not a circular reduction: the inverse theorems do not assume the conclusion, and the cited results are external in the sense of being about different distributions. Several 'it can be checked' connectivity assertions (e.g., in Lemmas 5.8, 6.1, 6.2, 6.3) are not expanded and are load-bearing for the application of Theorem 3, but these are omitted proof details, not circular steps. No fitted parameter is renamed as a prediction, and no uniqueness theorem or ansatz from the authors' prior work is used to forbid alternatives or smuggle in the conclusion. The central claim therefore has independent content, and the appropriate finding is a minor self-citation dependency, not circularity.
Assumptions & free parameters
free parameters (3)
- c in Lemma 7.1 =
1/1000
- zeta in Lemma 7.1 =
1/72
- C in Section 2.4 =
20
assumptions (4)
- domain assumption Theorem 2 (3-ary inverse theorem) from [BKLM24a]
- domain assumption Theorem 3 (4-ary inverse theorem) from [BKLM24b]
- domain assumption Density-increment lemma for product-correlating functions from [BKLM24a, Section 8]
- standard math Standard analytic tools: Cauchy-Schwarz, pigeonhole, Dirichlet approximation, total variation distance bounds
Cite this review
Pith. "Pith review of Reasonable Bounds for Combinatorial Lines of Length Three." pith.science (2026). https://pith.science/paper/6GUDTM3M
@misc{pith2026241115137,
author = {Pith},
title = {Pith review of: Reasonable Bounds for Combinatorial Lines of Length Three},
year = {2026},
howpublished = {\url{https://pith.science/paper/6GUDTM3M}},
note = {Machine review of arXiv:2411.15137}
}
abstract
We prove that any subset $A \subseteq [3]^n$ with $3^{-n}|A| \ge (\log\log\log\log n)^{-c}$ contains a combinatorial line of length $3$, i.e., $x, y, z \in A$, not all equal, with $x_i=y_i=z_i$ or $(x_i,y_i,z_i)=(0,1,2)$ for all $i = 1, 2, \dots, n$. This improves on the previous best bound of $3^{-n}|A| \ge \Omega((\log^* n)^{-1/2})$ of [D.H.J. Polymath, Ann. of Math. 2012].
Reference graph
Works this paper leans on
-
[3]
On app roximability of satisfiable k-csps: IV
[BKM24a] Amey Bhangale, Subhash Khot, and Dor Minzer. On app roximability of satisfiable k-csps: IV. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC , Canada, June 24-28, 2024, pages 1423–1434. ACM,
work page 2024
-
[2]
On app roximability of satisfiable k-csps: III
[BKM23c] Amey Bhangale, Subhash Khot, and Dor Minzer. On app roximability of satisfiable k-csps: III. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23 , 2023 , pages 643–655. ACM,
work page 2023
-
[6]
[DKT14] Pandelis Dodos, Vassilis Kanellopoulos, and Konst antinos Tyros
A vailable at https://arxiv.org/pdf/2309.02353. [DKT14] Pandelis Dodos, Vassilis Kanellopoulos, and Konst antinos Tyros. A simple proof of the density Hales-Jewett theorem. Int. Math. Res. Not. IMRN , (12):3340–3352,
-
[11]
©2023. [Len24] James Leng. A quantitative bound for Szemerédi’s th eorem for a complexity one polynomial progression over Z/N Z. Discrete Anal., pages Paper No. 3, 33,
work page 2023
-
[13]
Improved bounds for five-term arithmetic progressions
A vailable at https://arxiv.org/pdf/2312.10776. [LSS24a] James Leng, Ashwin Sah, and Mehtaab Sawhney. Impro ved bounds for Szemerédi’s theorem. arXiv preprint arXiv:2402.17995 ,
-
[14]
[LSS24b] James Leng, Ashwin Sah, and Mehtaab Sawhney
A vailable at https://arxiv.org/pdf/2402.17995. [LSS24b] James Leng, Ashwin Sah, and Mehtaab Sawhney. Quasi polynomial bounds on the inverse theorem for the Gowers U s+1[N ]-norm. arXiv preprint arXiv:2402.17994 ,
-
[15]
A vailable at https://arxiv.org/pdf/2402.17994v3. [Pel18] Sarah Peluse. Three-term polynomial progressions in subsets of finite fields. Israel J. Math. , 228(1):379–405,
- [1989]
Show all 13 references
-
[2004]
[Gre05a] Ben Green
A vailable at https://arxiv.org/pdf/math/0409420. [Gre05a] Ben Green. An argument of Shkredov in the finite field setting. Preprint,
-
[2006]
Szemerédi
[Sze75] E. Szemerédi. On sets of integers containing no k elements in arithmetic progression. In Proceedings of the International Congress of Mathematicians (Vancouver, B.C., 1974), Vol. 2 , pages 503–505. Canad. Math. Congr., Montreal, QC,
1974
-
[2021]
Strong bounds for 3-pro gressions
[KM23] Zander Kelley and Raghu Meka. Strong bounds for 3-pro gressions. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science—FOCS 2023 , pages 933–973. IEEE Computer Soc., Los Alamitos, CA,
2023
-
[2023]
[BKM23b] Amey Bhangale, Subhash Khot, and Dor Minzer
To appear in Discrete Analysis. [BKM23b] Amey Bhangale, Subhash Khot, and Dor Minzer. On app roximability of satisfiable k-csps: II. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, J...
2023
-
[2024]
On app roximability of satisfiable k-csps: V
[BKM24b] Amey Bhangale, Subhash Khot, and Dor Minzer. On app roximability of satisfiable k-csps: V. CoRR, abs/2408.15377,
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.