REVIEW 3 major objections 4 minor 18 references
An improved construction for the triangle removal lemma
T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read The paper constructs graphs that double the best-known lower-bound exponent for the triangle removal lemma, reaching C\approx 1.6601 instead of C\approx 0.8301.
desk verdict The ball-for-box swap gives a real factor-two improvement and the proof is sound, but the abstract and Theorem 2 misstate the numerical constants (C≈0.602, not 1.660). 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 a corner-free set inside a product grid: a set with no triple $(x,y),(x+d,y),(x,y+d)$ for $d\neq 0$. Lemma 2.1 converts such a set into a tripartite graph whose triangles are edge-disjoint, so the graph is an instance of the $\eta(n)$ extremal problem; Corollary 2.4 reduces the density to the additive concentration probability $\Pr_{x\sim X,y\sim Y}(x+y\in Z)$. The paper's new choice for $X,Y,Z$ is a discretization of the Euclidean ball, and Proposition 3.1 supplies the estimate $\Pr_{x,y\sim B}(x+y\in B)\gg D^{-O(1)}(3/4)^{D/2}$ via the known density of the dot product of two random unit vectors. This estimate, rather than the box's $(3/4)^D$, is what carries the improved exponent after optimizing $D$.
What would settle it
Evaluate the closure probability of the centered Euclidean ball numerically for large dimension, say $D=100$, by Monte Carlo sampling or by direct integration of $\int_{-1/2}^{-1}(1-r^2)^{D/2}\,dr$. If the observed decay follows $(3/4)^D$ rather than $(3/4)^{D/2}$, then Proposition 3.1 is false and the improved constant in Theorem 2 cannot stand; a rigorous asymptotic of that integral that contradicts $\gg D^{-O(1)}(3/4)^{D/2}$ would settle it the same way.
Extended reading notes
Core claim
On the paper's own terms, the discovery is Theorem 2: $\delta(\varepsilon) \le \varepsilon^{(C-o(1))\log_2(1/\varepsilon)}$ for $C = 1/(4\log_2(4/3)) \approx 1.6601$, upgrading the previously known constant $C_{\text{old}} \approx 0.8301$. Equivalently, Theorem 1 gives $\eta(3n) \gg D^{-O(1)}(3/4)^{D/2} n^{-2/D}$ for every dimension $D$, which optimizes to $\eta(n) \gg 2^{-(2\sqrt{\log_2(4/3)}+o(1))\sqrt{\log_2 n}}$. The engine is the Euclidean ball: a $D$-dimensional box gives only a $(3/4)^D$ closure probability, while the ball gives $(3/4)^{D/2}$ (Proposition 3.1), and that square-root saving is exactly what doubles the exponent in the final bound. The paper also records a general reduction (Proposition 1.2) from additive sets with a 3-AP-free difference set to such graphs, and a converse estimate (Proposition 4.1) showing that this particular reduction cannot by itself produce dramatically stronger bounds.
Load-bearing premise
The whole improvement rests on the estimate that two independent random points in a high-dimensional Euclidean ball have their sum inside the ball with probability at least $D^{-O(1)}(3/4)^{D/2}$; if the true probability decayed as $(3/4)^D$, optimizing the dimension would return the old, unimproved constant.
Editorial extensions
If this is right
- If Theorem 2 is correct, the best-known lower bound on the inverse triangle removal function becomes $1/\delta(\varepsilon) \gg \exp((C-o(1))\log(1/\varepsilon)\log_2(1/\varepsilon))$ with $C\approx 1.6601$, the strongest known.
- The construction supplies $n$-vertex graphs that are $\varepsilon$-far from triangle-free while containing only $\varepsilon^{(C-o(1))\log_2(1/\varepsilon)} n^3$ triangles, for the same constant.
- The dimension-range formulation $\eta(3n)\gg D^{-O(1)}(3/4)^{D/2}n^{-2/D}$ means the improvement is robust to the choice of dimension and is optimized near $D \sim 2\sqrt{\log_2 n/\log_2(4/3)}$.
- For every construction coming from this additive-combinatorial template, the constant is controlled by the closure probability of the chosen geometric body, so the improved exponent is a direct corollary of the ball's square-root saving over the box.
Reading between the lines
- The same 'ball instead of box' move could plausibly improve lower bounds for other removal lemmas whose constructions are built from additive concentration, such as the $k$-clique removal lemma, by replacing the box closure probability with the ball's.
- A sharper asymptotic for the closure probability $\Pr_{x,y\sim B}(x+y\in B)$ than the lower bound in Proposition 3.1 might move the constant further; the paper's $D^{-O(1)}$ factor leaves room.
- The paper's converse estimate suggests that to go beyond this exponent through additive-set reductions one would need new bounds for 3-AP-free sets themselves; the geometric improvement is already tight within that reduction.
- One could test the mechanism numerically by estimating the decay exponent of the closure probability for $\ell^p$ balls with $p\neq 2$, to see whether the Euclidean ball is optimally closed under addition among convex bodies.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper constructs n-vertex graphs with few triangles but many edges that must be deleted in a triangle-free subgraph, thereby giving lower bounds for the triangle removal lemma. It proves a new 'range' of bounds η(3n) ≫ D^{-O(1)}(3/4)^{D/2} n^{-2/D} for arbitrary D, improving the previous Green-type range (3/4)^D. Optimizing D gives η(n) ≫ 2^{-(2√(log_2(4/3))+o(1))√log_2 n} and hence δ(ε) ≤ ε^{(C-o(1)) log_2(1/ε)} with C = 1/(4 log_2(4/3)). The source of the improvement is Proposition 3.1, which replaces the box of side roughly M with a Euclidean ball: the probability that two independent random points of the ball have their sum in the ball is ≫ D^{-O(1)}(3/4)^{D/2}, instead of (3/4)^D for a box. The proof chain uses a reduction from corner-free sets (Lemma 2.1 and Claim 2.2), a Behrend-style coloring (Lemma 2.3), a discretization lemma (Lemma 3.2), and an explicit integration bound. The paper also proves a limitation result (Proposition 4.1) showing that the more general Proposition 1.2 is polynomially related to the 3-AP-free density r3(n)/n.
Significance. After correcting the arithmetic errors noted below, the paper improves the best-known exponent coefficient in the lower bound for 1/δ(ε) from 1/(8 log_2(4/3)) ≈ 0.301 to 1/(4 log_2(4/3)) ≈ 0.602, a factor of 2. This is a modest but genuine advance over the previous corner-based bound of Green. The proof is elementary, self-contained, and has no fitted parameters; the central geometric estimate is explicit. The limitation discussion in Section 4 is honest and connects the construction to known bounds for r3(n). The self-citation [5] is not used in the proof, so there is no circularity. The paper is a short note that fits well in a combinatorics venue, provided the numerical and proof-presentation issues are fixed.
major comments (3)
- [Abstract and Theorem 2] The decimal evaluations of the constants are arithmetically wrong. C = 1/(4 log_2(4/3)) is approximately 0.602, not 1.6601; the value 1.6601 is instead 4 log_2(4/3). Similarly, 1/(2 log_2(4/3)) is approximately 1.204, not 0.8301, and the previous exponent coefficient from Eq. (1.2) is actually C_old = 1/(8 log_2(4/3)) ≈ 0.301, with C_new = 2·C_old. As printed, the abstract and Theorem 2 overstate the improvement by a factor of about 2.76. The symbolic formulas are correct, and the proof actually gives the smaller constant, but the headline numerical claims must be corrected.
- [Section 3.1, proof of Lemma 3.5] The expansion of ||x+y||² is printed as ||x||² − 2⟨x,y⟩ + ||y||²; the correct identity has +2⟨x,y⟩. With the printed minus sign, the inequality λ_x² − 2λ_xλ_y⟨x̂,ŷ⟩ + λ_y² ≤ λ_x² does not follow from ⟨x̂,ŷ⟩ ≤ −1/2. Replacing the minus sign with a plus sign makes the argument work: one obtains λ_x² + λ_y² + 2λ_xλ_y⟨x̂,ŷ⟩ ≤ λ_x² + λ_y² − λ_xλ_y ≤ λ_x² when λ_x ≥ λ_y. Since Lemma 3.5 is the bridge from the ball probability to the inner-product computation (Eqs. 3.1–3.4), the proof as written is invalid, though the fix is local.
- [Proof of Theorem 1 (Section 3)] The lattice-shift step has a gap. The set S is defined as {(x,y): x,y,x+y ∈ B}, and Lemma 3.2 gives lattice points (ξ,η) ∈ (t+S)∩Z^{2D}. For such a point, ξ ∈ t^(1)+B, η ∈ t^(2)+B, and ξ+η ∈ t^(1)+t^(2)+B. The proof then sets Z0 := B∩Z^D and lower-bounds the number of pairs (x,y) ∈ X0×Y0 with x+y ∈ Z0, but these pairs are not directly counted by the measure μ(S). The correct choice is Z0 := (t^(1)+t^(2)+B)∩Z^D, or one must argue that t^(1)+t^(2) is negligible compared with the radius of B (which is plausible under the hypothesis n > (2D)^{100D} and the later bound r ≥ D^{50}). As written, the displayed lower bound '#(x∈X0,y∈Y0: x+y∈Z0) ≫ D^{-O(1)}(3/4)^{D/2} n²' is not justified.
minor comments (4)
- [Lemma 2.1 and Corollary 2.4] Lemma 2.1 states η(3n) ≥ |A|/(9n²), but the constructed graph has 3|A| edges because each triangle contributes three edges and the triangles are edge-disjoint; hence one actually gets η(3n) ≥ |A|/(3n²). This constant factor does not affect the asymptotic exponent, but it propagates to Proposition 1.2 and Corollary 2.4, which are accordingly weaker by a factor of 3.
- [Proof of Theorem 1, optimizing D] The displayed formula for D_n is hard to parse and appears to read 2√(log_2(4/3))√(log_2 n). If that is the intended choice, substituting it into (3/4)^{D/2} n^{-2/D} gives an exponent of about (a^{3/2}+a^{-1/2})√log n with a = log_2(4/3), i.e., about 1.82√log n, not the claimed 2√(log_2(4/3))√log n. The correct optimizing choice is D_n ≈ 2√(log_2 n / log_2(4/3)). Please clarify or correct the formula.
- [Throughout] There are several typographical errors: 'Vinagradov' should be 'Vinogradov'; the reference to 'Proposition 2.4' after Lemma 3.2 should be to Corollary 2.4; and the sentence 'It is clear that Eq. 3.2 holds' appears to refer to the equality to P(⟨u,v⟩ ≤ −1/2), not to the inequality Eq. 3.1.
- [Section 1, introduction] The phrase 'the previous best bound had a worse constant of 1/(2 log_2(4/3)) ≈ 0.8301' is inconsistent both arithmetically and with the abstract's definition C_old := C_new/2. The previous bound from Eq. (1.2) has C_old = 1/(8 log_2(4/3)) ≈ 0.301; please correct the displayed expression and its decimal evaluation.
Circularity Check
No significant circularity; the improved bound is obtained by an explicit construction, though the printed decimal constants contain an arithmetic error.
full rationale
The derivation chain is self-contained: Corollary 2.4 converts additive-combinatorial configurations into graphs, Lemma 2.3 supplies a corner-free coloring, Proposition 3.1 estimates the probability that a Euclidean ball is closed under addition, Theorem 1 optimizes the dimension D, and Theorem 2 translates the resulting lower bound on eta(n) into an upper bound on delta(epsilon). No parameter in the final delta bound is fitted to delta; the only choices are M = n^{1/D}, the analytically optimized D, and the Euclidean ball. Proposition 3.1 is proved directly from the standard distribution formula in Claim 3.4 plus explicit integration, and the reduction lemmas are proved in the paper rather than imported from the target result. The one self-citation, [5], appears only in the introduction and is explicitly set aside: the paper says it 'would have improved lower bounds for triangle removal, if not for some different progress,' so it is not load-bearing for Theorem 1 or Theorem 2. Section 4's Ruzsa and Balogh-Szemeredi-Gowers inputs are used only for the concluding limitation discussion, not for the main construction, so they do not create circularity. There is a genuine arithmetic misstatement in the abstract and Theorem 2: 1/(4 log_2(4/3)) is about 0.602, not 1.6601, and 1/(2 log_2(4/3)) is about 1.204, not 0.8301; there is also a sign issue in Lemma 3.5. These are correctness and verification concerns, not circularity, because the symbolic formula C = 1/(4 log_2(4/3)) is derived by optimizing an explicit construction rather than being equivalent to the target bound by construction. The paper is self-contained against external benchmarks, so the circularity score is 0.
Assumptions & free parameters
free parameters (1)
- D (dimension parameter) =
D_n = ceil(2 sqrt(log_2(4/3)) sqrt(log_2 n))
assumptions (3)
- standard math Claim 3.4: the dot product of two independent uniform random unit vectors in R^D has the stated density f_R(r) = Γ(D/2)/(√π Γ((D-1)/2)) (1-r^2)^{(D-3)/2}.
- standard math Theorem 3 (Ruzsa): if A ⊂ Z is 3-AP-free of size n, then |A+A| ≥ (1/2)(n/r3(n))^{1/4} n.
- standard math Lemma 4.2 (Balogh-Szemerédi-Gowers type concentration plus Ruzsa triangle inequality): for |E| ≥ c n^2 and sumset size ≤ n, one can find large subsets A',B' with |A'+A'-B'-B'| ≪ (1/c)^{O(1)} n.
Cite this review
Pith. "Pith review of An improved construction for the triangle removal lemma." pith.science (2026). https://pith.science/paper/762BOSMG
@misc{pith2026250705231,
author = {Pith},
title = {Pith review of: An improved construction for the triangle removal lemma},
year = {2026},
howpublished = {\url{https://pith.science/paper/762BOSMG}},
note = {Machine review of arXiv:2507.05231}
}
abstract
We construct $n$-vertex graphs $G$ where $\epsilon n^2$ edges must be deleted to become triangle-free, which contain less than $\epsilon^{(C_{\text{new}}-o(1))\log_2 1/\epsilon}n^3$ triangles for $C_{\text{new}}= \frac{1}{4\log_2(4/3)} \approx 1.6601$. Previously, a bound of the same shape was known, but with $C_{\text{new}}$ replaced by $C_{\text{old}} := C_{\text{new}}/2$. Our construction uses ideas from additive combinatorics, drawing especially from the corners problem, but does not yield new bounds for those problems.
Reference graph
Works this paper leans on
-
[5]
C. Elsholtz, Z. Hunter, L. Proske, and L. Sauermann, Improving Behrend’s construction: Sets without arithmetic progressions in integers and over finite fields, preprint (June 2024), 15 pp. https: //arxiv.org/abs/2406.12290
arXiv 2024
-
[1]
F. A. Behrend, On sets of integers which contain no three in arithmetic progression, in Proceedings of the National Academy of Sciences 32 (1946), p. 331-332
work page 1946
-
[2]
J. Bourgain, On the Dimension of Kakeya Sets and Related Maximal Inequalities, in Geometric and Functional Analysis 9 (1999), p. 256-282
work page 1999
-
[3]
M. Christandl, O. Fawzi, H. Ta, and J. Zuiddam, Larger Corner-Free Sets from Combinatorial Degenerations, in 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215
work page 2022
-
[4]
Elkin, An improved construction of progression-free sets, in SODA 10’ (2010), p
M. Elkin, An improved construction of progression-free sets, in SODA 10’ (2010), p. 886-905
work page 2010
-
[6]
E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samorodnitsky, Monotonicity testing over general poset domains, in Proceedings of the thirty-fourth annual ACM symposium on Theory of computing (2002), p. 474–483
work page 2002
-
[7]
Fox, A new proof of the graph removal lemma, in Annals of Mathematics 174 (2011), p
J. Fox, A new proof of the graph removal lemma, in Annals of Mathematics 174 (2011), p. 561–579. 6The author does not hold this view, though we know a person or two who does. AN IMPROVED CONSTRUCTION FOR THE TRIANGLE REMOV AL LEMMA 13
work page 2011
-
[8]
J. Fox, H. Huang, and B. Sudakov, On graphs decomposable into induced matchings of linear sizes, in Bulletin of the London Mathematical Soceity 49 (2016), p. 45-57
work page 2016
Show all 18 references
-
[9]
B. J. Green, Lower bounds for corner-free sets, in New Zealand Journal of Mathematics 51 (2021), p. 1-2
2021
-
[10]
B. J. Green and J. Wolf, A note on Elkin ’s improvement of Behrend’s construction, in Additive Number Theory, p. 141–144, Springer, New York 2010
2010
-
[11]
Jaber, Y
M. Jaber, Y. Liu, S. Lovett, A. Osthuni, and M. Sawhney, Quasipolynomial bounds for the corners theorem, preprint (April 2025), 85 pp. https://arxiv.org/abs/2504.07006
2025 arXiv
-
[12]
Kelley and R
Z. Kelley and R. Meka, Strong bounds for 3-Progressions, in IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) (2023), p. 933-973
2023
-
[13]
Kleinberg, D
R. Kleinberg, D. Speyer, and W. Sawin, The growth rate of tri-colored sum-free sets, in Discrete Analysis 12 (2018), 10 pp
2018
-
[14]
Linial and A
N. Linial and A. Shraibman, Larger Corner-Free Sets from Better NOF Exactly- N Protocols, in Discrete Analysis 19 (2021), 9 pp
2021
-
[15]
Scalar product of random unit vectors
I. Pinelis, Answer to “Scalar product of random unit vectors”, https://mathoverflow.net/a/ 361614/130484, 2020
2020
-
[16]
Pratt, A note on Ordered Ruzsa-Szemer´ edi graphs, preprint (February 2025), 4 pp
K. Pratt, A note on Ordered Ruzsa-Szemer´ edi graphs, preprint (February 2025), 4 pp. https: //arxiv.org/abs/2502.02455
2025 arXiv
-
[17]
Ruzsa, Arithmetical progressions and the number of sums, in Periodica Mathematica Hungarica 25 (1992), p
I. Ruzsa, Arithmetical progressions and the number of sums, in Periodica Mathematica Hungarica 25 (1992), p. 105-111
1992
-
[18]
Tao and V
T. Tao and V. Vu, Additive Combinatorics, Cambridge Stud. Adv. Math., 105 Cambridge Uni- versity Press, Cambridge, 2006, xviii+512 pp. Email address : zach.hunter@math.ethz.ch
2006
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.