Pith. sign in

REVIEW 2 major objections 2 minor 30 references

The paper proves that for every k≥5, the number of subsets of {1,...,n} containing no k-term arithmetic progression is 2^{r_k(n)(1+o(1))} for infinitely many n, resolving a long-standing question in extremal combinatorics.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

For k≥5, infinitely many n have exactly 2^{r_k(n)(1+o(1))} k-AP-free subsets of [n]; for all n and k≥3 the count is 2^{O(r_k(n))}.

T0 review reviewed 2026-08-01 challenge →

load-bearing objection Strong sharp-counting theorem for k-APs, but the appendix proof that powers the broader applications has a degree error that looks fatal for those parts. the 2 major comments →

arxiv 2607.17746 v1 pith:4MFBUZSZ submitted 2026-07-20 math.CO math.NT

Counting subsets of integers free of arithmetic configurations

Patrick Morris , Miquel Ortega , Juanjo Ru\'e This is my paper
classification math.CO math.NT MSC 05D0511B2505D40
keywords arithmetic progressionsk-term progression-free setsextremal combinatoricshypergraph containerssupersaturationtranslation-invariant systems of equationsmultidimensional Szemerédi theoremcounting subsets
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

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 answers a long-standing counting question: how many subsets of {1,...,n} contain no k-term arithmetic progression? The authors prove that for every k≥5, along an infinite sequence of n, the number is 2^{r_k(n)(1+o(1))}, where r_k(n) is the size of the largest such subset; this matches the trivial lower bound. They also prove that for every k≥3 and every n, the number is at most 2^{O(r_k(n))}. Both results are instances of a general framework for translation-invariant systems of arithmetic equations: if the extremal threshold is at least n^d exp(-O(log^α n)) with α<1/2, the sharp exponent follows; with α<1, the all-n bound follows. The framework also yields analogous counting theorems for multidimensional patterns and for almost all systems of linear equations.

Core claim

The central discovery is that, for any translation-invariant matrix A defining forbidden arithmetic configurations, the number of A-free subsets of [n]^d is controlled by the extremal threshold r_A(n): for an infinite sequence of n it is 2^{(1+o(1))r_A(n)} whenever r_A(n)≥n^d exp(-O(log^α n)) with α<1/2, and for all n it is 2^{O(r_A(n))} whenever α<1. For k-term progressions with k≥5, known lower-bound constructions provide the required α<1/2, so the sharp exponent holds; the best constructions for k=3,4 only reach α=1/2, which the proof's smoothness condition cannot handle. The proof's engine is a supersaturation statement: any set exceeding the extremal threshold by a factor (1+δ) must con

What carries the argument

The key mechanism is a pair of supersaturation lemmas (Propositions 4.1 and 5.3) that rule out 'cheap covers' of the hypergraph of forbidden configurations. Proposition 4.1 samples a random grid with prime common difference; if the extremal density changes slowly across scales n and n e^{-√log n}, any set of size (1+δ)r_A(n) contains a forbidden configuration outside every low-weight cover. Lemma 4.2 converts the lower bound r_A(n) ≥ n^d exp(-O(log^α n)) with α<1/2 into this smoothness condition for an infinite sequence. For the all-n bound, a supermultiplicativity property of r_A(n) replaces smoothness, and an iterative container-shrinking argument produces containers of size O(r_A(n)). Tog

Load-bearing premise

The sharp-exponent theorem rests on the extremal threshold being at least n^d exp(-O(log^α n)) with α<1/2, the condition that guarantees the density smoothness across scales; for 3- and 4-term progressions even the strongest conjectured lower bounds provide only α=1/2, so the main conclusion currently stops at k≥5.

What would settle it

Find a translation-invariant matrix A and an infinite sequence n_i with r_A(n_i) ≥ n_i^d exp(-O(log^{1/3} n_i)) but for which the number of A-free sets in [n_i]^d is at least 2^{(1+c) r_A(n_i)} for a fixed c>0; this would contradict Theorem 2.6 and its progression corollary. A more targeted probe is to compute the density ratio r_A(n)/n^d versus r_A(n e^{-√log n})/(n e^{-√log n})^d along candidate sequences: if it fails to stay above 1 - δ/8 for every infinite sequence, the proof's smoothness condition is genuinely necessary, and if it ever does so for a sequence where the count is not sharp,

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • For every k≥5, the number of k-term-progression-free subsets of [n] is 2^{r_k(n)(1+o(1))} for infinitely many n, answering the long-standing counting question in the affirmative along that sequence.
  • For every k≥3 and all n, the number of k-term-progression-free subsets is 2^{O(r_k(n))}, so the trivial lower bound is always tight up to a constant in the exponent.
  • For any finite pattern X⊂Z^d with |X|≥5, the number of subsets of [n]^d avoiding positive copies of X is 2^{r_X(n)(1+o(1))} for infinitely many n; with |X|≥3, a 2^{O(r_X(n))} bound holds for all n.
  • For almost all (k,h)-systems of translation-invariant linear equations with enough equations, the number of solution-free sets satisfies the sharp exponent for infinitely many n and a 2^{O(r_A(n))} bound for all n.
  • The two general theorems unify many previous counting results and show that a sufficiently strong lower bound on the extremal threshold essentially determines the counting exponent.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If future work improves the lower bounds for 3- and 4-term progressions to the required α<1/2, the same framework would likely settle the counting question for all k and all n.
  • The unconditional all-n bound suggests that for generic translation-invariant patterns, avoiding sets are spread out enough for the extremal size alone to control the count; deviations from this, as in some classical examples, must stem from special additive structure.
  • The random-grid supersaturation technique may be adaptable to other hypergraphs defined by polynomial or algebraic configurations, potentially giving new counting theorems outside the linear-equation setting.
  • The iterative container-shrinking scheme appears to be a reusable tool for extremal counting problems whose extremal function satisfies a supermultiplicativity inequality.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 2 minor

Summary. The paper develops a general hypergraph-container framework for counting subsets of [n]^d that avoid solutions to translation-invariant systems of linear equations. The two abstract theorems, Theorem 2.6 and Theorem 2.7, assert that if the extremal function r_A(n) satisfies a Behrend-type lower bound n^d exp(-O(log^α n)) with α<1/2 or α<1 respectively, then the number of A-free sets is, respectively, 2^{(1+o(1))r_A(n)} for infinitely many n or 2^{O(r_A(n))} for all n. From these the paper derives: for k≥5, the number of k-AP-free subsets of [n] is 2^{r_k(n)(1+o(1))} for infinitely many n (Theorem 1.3), and for k≥3, it is 2^{O(r_k(n))} for all n (Theorem 1.4); analogous multidimensional and almost-all linear equation results (Theorems 1.5, 1.6, 1.8, 1.9). The proofs use a new supersaturation statement phrased as absence of cheap covers, a smoothness lemma passing to a subsequence, and an iterative container-shrinking argument.

Significance. If the main framework is valid, Theorem 1.3 is a substantial advance on the Balogh–Liu–Sharifzadeh result and resolves the Cameron–Erdős question in the qualitative form for infinitely many n. Theorem 1.4 is also notable and is best possible up to a constant factor in the exponent. The abstract container formulation, with supersaturation statements in the cheap-cover language, is elegant and likely to be reusable. The paper is careful in transferring the extremal condition to the counting exponent, and the proofs of Propositions 4.1 and 5.3 are largely transparent. However, the advertised generality depends on an appendix whose degree estimates are wrong in a load-bearing way, and the proof of Theorem 5.4 has a constant-factor gap. These issues do not affect the k-AP results, but they must be repaired before the broader claims (Theorems 1.5 and 1.8) can be accepted.

major comments (2)
  1. [Appendix A, Lemmas A.4 and A.11] The proof of Lemma A.4 asserts that Q = ΣP_i^2 − R has degree at most 2ℓ. Since each P_i has degree at most 2ℓ−1, deg(Q) ≤ 4ℓ−2, not 2ℓ. Thus a nonzero Q can vanish at 2ℓ+1 points, and the conclusion that the polynomial copy is trivial does not follow for ℓ≥2. The same miscalculation appears in Lemma A.11. This is load-bearing: Propositions 6.2 and 6.3, and therefore Theorems 1.8 and 1.5, rest on these lemmas. Additionally, Lemma A.4’s statement promises an (X,2ℓ′)-free set, but the application needs an (X,1)-free set; for ℓ=1, ℓ′=0 gives only (X,0)-freeness, which is vacuous. The degree indices are inconsistent throughout the appendix. The argument may be repairable by constructing the sphere as (X,ℓ)-free and then iterating down to degree 1, but as printed the proof is invalid.
  2. [§5, Theorem 5.4] In the second case of the iterative step, Proposition 5.3 is applied to a container C with |C| ≥ λ_{i+1}r_A(n). However, the container lemma supplies a cover G of H[C] with w_p(G) ≤ p|C|, not w_p(G) ≤ p|C'| for a subset C' of size exactly λ_{i+1}r_A(n). The inherited weight bound is therefore p|C|, which can be a constant factor larger than the q|B| required by Proposition 5.3. The argument is likely salvageable by choosing p = c λ^{-3} with a sufficiently small constant c to absorb the factor, but this adjustment is not written and the present application has a mismatch of hypotheses.
minor comments (2)
  1. [§4, Proposition 4.1] The tiling sentence in the border case is garbled: 'with 1 ≤ h_i ≤ t box [t]^d' should explain that each Q_i is a translate of [h_i]^d for some h_i ≤ t, and that |Z'∩Q_i| ≤ r_A(h_i) is then bounded using monotonicity and Lemma 3.1.
  2. [References] In Appendix A the text attributes the treatment to 'Lacey and Laba', while reference [19] is listed as 'Laba and Lacey'. Please make the citation consistent.

Circularity Check

0 steps flagged

No significant circularity: the counting theorems are conditional on explicit extremal lower bounds, which are external inputs rather than consequences of the counting argument.

full rationale

The main derivation is conditional on explicit hypotheses about the extremal function r_A(n), not on the counting conclusion. Theorem 2.6 and Theorem 2.7 assume r_A(n) >= n^d exp(-O(log(n)^alpha)) and then prove upper bounds on the number of A-free sets via the container method and supersaturation. The extremal lower bounds are inputs used to control container count and smoothness; they do not encode the number of A-free sets, so there is no self-definition or fitted-input-called-prediction pattern. Applications instantiate these hypotheses with external lower bounds: Rankin's bound for k-APs with k>=5, Shapira's framework plus Appendix A for linear systems, and Appendix A for multidimensional configurations. The paper does cite the authors' own work, notably Morris-Saxton [21] for the iterative container-shrinking scheme and Balogh-Morris-Samotij [3] for the container method, but the needed container arguments are re-proved or cited to an external formulation (Campos-Samotij), and the iterative refinement is given in full in the current paper. These self-citations are explanatory rather than load-bearing. There is no invoked uniqueness theorem from the authors' prior work, and no ansatz smuggled in solely by self-citation. The possible Appendix A degree miscalculation flagged by the reviewer is a correctness concern about the proof of the lower bounds, not a circularity: even if that proof fails, the counting theorems still hold conditional on the stated lower-bound hypotheses. Therefore no circular step meeting the required evidentiary standard is present.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

No data-driven free parameters exist: all constants in the proofs are asymptotic and chosen for the argument, not to force the target estimate. The axioms are standard theorems in combinatorics and number theory. The paper introduces mathematical definitions (translation-invariant matrices, A-free families) but no new physical or structural entities.

axioms (4)
  • standard math Campos–Samotij hypergraph container theorem (Theorem 3.6)
    Used as a black box to obtain containers and cheap covers; from [10].
  • standard math Prime Number Theorem and Bertrand's postulate
    PNT controls the number of prime grid steps in Proposition 4.1; Bertrand's postulate provides the prime in Lemma 5.2.
  • domain assumption Rankin/Behrend lower bounds for r_k(n) (from [24],[5],[11])
    These are hypotheses of Theorems 2.6/2.7. For the applications they are known theorems from the literature; Appendix A re-proves the multidimensional analogs.
  • domain assumption Shapira's parametric-representation result for almost all systems of equations [28]
    Used in Appendix A to deduce Proposition 6.3; the paper extends it to stronger Rankin-type bounds.

reviewed 2026-08-01 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Counting subsets of integers free of arithmetic configurations." pith.science (2026). https://pith.science/paper/4MFBUZSZ

@misc{pith2026260717746,
  author       = {Pith},
  title        = {Pith review of: Counting subsets of integers free of arithmetic configurations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4MFBUZSZ}},
  note         = {Machine review of arXiv:2607.17746}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Cameron and Erd\H{o}s asked if the number of sets free of arithmetic progressions of length $k$ is $2^{r_k(n)(1+o(1))}$, where $r_k(n)$ is the maximum cardinality of a $k$-AP-free subset of $\{1, \dots, n\}$. Balogh, Liu and Sharifzadeh made significant progress on this question showing that it is $2^{O(r_k(n))}$ for an infinite sequence of $n$. We improve their result in two ways. On the one hand, we prove that, for $k\geq 5$, the number of $k$-AP-free sets in $[n]$ is $2^{r_k(n)(1+o(1))}$ for an infinite sequence of $n$, solving the question of Cameron and Erd\H{o}s for infinitely many values. On the other hand, we also prove that for $k \geq 3$ and all $n$ the number of $k$-AP-free sets in $[n]$ is $2^{O(r_k(n))}$. These results are in fact special cases of a general framework that we develop to count families of sets excluding certain arithmetic patterns, which applies as long as the corresponding extremal threshold satisfies certain Behrend-type lower bounds. As further examples, we get analogous results for solution sets to almost all systems of linear equations as well as counting versions of the multidimensional Szemer\'edi theorem.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 7 linked inside Pith

  1. [1]

    Balogh, S

    J. Balogh, S. Das, H. Liu, M. Sharifzadeh, and T. Tran. Structure and supersaturation for intersecting families.Electron. J. Combin., 26(2):Paper No. 2.34, 38, 2019

    2019

  2. [2]

    Balogh, H

    J. Balogh, H. Liu, and M. Sharifzadeh. The number of subsets of integers with no k-term arithmetic progression.Int. Math. Res. Not. IMRN, pages 6168–6186, 2017

    2017

  3. [3]

    Balogh, R

    J. Balogh, R. Morris, and W. Samotij. Independent sets in hypergraphs.J. Amer. Math. Soc., 28(3):669– 709, 2015

    2015

  4. [4]

    Behague, J

    N. Behague, J. Hyde, N. Morrison, J. A. Noel, and A. Wright. An approximate counting version of the multidimensional Szemer´ edi theorem.Combinatorica, 45(4):Paper No. 42, 21, 2025

    2025

  5. [5]

    F. A. Behrend. On sets of integers which contain no three terms in arithmetical progression.Proc. Nat. Acad. Sci. U.S.A., 32:331–332, 1946

    1946

  6. [6]

    T. F. Bloom. A quantitative improvement for Roth’s theorem on arithmetic progressions.J. Lond. Math. Soc. (2), 93(3):643–663, 2016

    2016

  7. [7]

    T. F. Bloom and O. Sisask. An improvement to the Kelley-Meka bounds on three-term arithmetic progressions, 2023. arXiv:2309.02353

    Pith/arXiv arXiv 2023

  8. [8]

    N. J. Calkin. On the number of sum-free sets.Bull. London Math. Soc., 22(2):141–144, 1990

    1990

  9. [9]

    P. J. Cameron and P. Erd˝ os. On the number of sets of integers with various properties. InNumber theory (Banff, AB, 1988), pages 61–79. de Gruyter, Berlin, 1990

    1988

  10. [10]

    Campos and W

    M. Campos and W. Samotij. Towards an optimal hypergraph container lemma, 2024. arXiv:2305.05304

    Pith/arXiv arXiv 2024

  11. [11]

    Elsholtz, Z

    C. Elsholtz, Z. Hunter, L. Proske, and L. Sauermann. Improving Behrend’s construction: Sets without arithmetic progressions in integers and over finite fields, 2024. arXiv:2406.12290

    Pith/arXiv arXiv 2024

  12. [12]

    Erd˝ os, P

    P. Erd˝ os, P. Frankl, and V. R¨ odl. The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent.Graphs Combin., 2(2):113–121, 1986

    1986

  13. [13]

    Erd˝ os, D

    P. Erd˝ os, D. J. Kleitman, and B. L. Rothschild. Asymptotic enumeration ofKn-free graphs. InColloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo II, pages 19–27. Accad. Naz. Lincei, Rome, 1976. 22 P. MORRIS, M. ORTEGA, AND J. RU ´E

    1973

  14. [14]

    Ferber, G

    A. Ferber, G. McKinley, and W. Samotij. Supersaturated sparse graphs and hypergraphs.Int. Math. Res. Not. IMRN, (2):378–402, 2020

    2020

  15. [15]

    Kelley and R

    Z. Kelley and R. Meka. Strong bounds for 3-progressions, 2024. arXiv:2302.05537

    Pith/arXiv arXiv 2024

  16. [16]

    Y. Kim. The number of k-dimensional corner-free subsets of grids.Electron. J. Combin., 29(2):Paper No. 2.53, 19, 2022

    2022

  17. [17]

    Kleitman

    D. Kleitman. On Dedekind’s problem: The number of monotone Boolean functions.Proc. Amer. Math. Soc., 21:677–682, 1969

    1969

  18. [18]

    Kohayakawa, S

    Y. Kohayakawa, S. J. Lee, V. R¨ odl, and W. Samotij. The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers.Random Structures Algorithms, 46(1):1–25, 2015

    2015

  19. [19]

    Laba and M

    I. Laba and M. T. Lacey. On sets of integers not containing long arithmetic progressions, 2001. arXiv:math/0108155

    Pith/arXiv arXiv 2001

  20. [20]

    J. Leng, A. Sah, and M. Sawhney. Improved bounds for Szemer´ edi’s theorem, 2024. arXiv:2402.17995

    Pith/arXiv arXiv 2024

  21. [21]

    Morris and D

    R. Morris and D. Saxton. The number ofC 2ℓ-free graphs.Adv. Math., 298:534–580, 2016

    2016

  22. [22]

    O’Bryant

    K. O’Bryant. Sets of integers that do not contain long arithmetic progressions.Electron. J. Combin., 18(1):Paper 59, 15, 2011

    2011

  23. [23]

    Raghavan

    R. Raghavan. Improved bounds for 3-progressions, 2026. arXiv:2603.27045

    Pith/arXiv arXiv 2026

  24. [24]

    R. A. Rankin. Sets of integers containing not more than a given number of terms in arithmetical progression.Proc. Roy. Soc. Edinburgh Sect. A, 65:332–344 (1960/61), 1960/61

    1960

  25. [25]

    I. Z. Ruzsa. Solving a linear equation in a set of integers. I.Acta Arith., 65(3):259–282, 1993

    1993

  26. [26]

    Ru´ e, C

    J. Ru´ e, C. Spiegel, and A. Zumalac´ arregui. Threshold functions and poisson convergence for systems of equations in random sets.Mathematische Zeitschrift, 288:333–360, 2017

    2017

  27. [27]

    Saxton and A

    D. Saxton and A. Thomason. Hypergraph containers.Invent. Math., 201(3):925–992, 2015

    2015

  28. [28]

    A. Shapira. Behrend-type constructions for sets of linear equations.Acta Arith., 122(1):17–33, 2006

    2006

  29. [29]

    Szemer´ edi

    E. Szemer´ edi. On sets of integers containing no k elements in arithmetic progression.Acta Arith., 27:199–245, 1975

    1975

  30. [30]

    Tao and V

    T. Tao and V. Vu.Additive combinatorics, volume 105 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2006. AppendixA.Rankin-type lower bounds A.1.Multidimensional Szemer´ edi.The goal of this section is to prove Proposition 6.2. As we mentioned before, the proof is standard and uses Rankin’s argument to find large k-AP-f...

    2006

This paper was first reviewed by deepseek-v4-flash on August 1, 2026.