Pith. sign in

REVIEW 3 major objections 4 minor 34 references

Finding Large Sets Without Arithmetic Progressions of Length Three: An Empirical View and Survey II

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read The paper claims that the nonconstructive sphere method produces the largest known 3-free subsets of {1,...,n} once n reaches 10^9, and reports exact maximum sizes for all n up to 186.

desk verdict Useful small-n exact values and survey, but the main large-n comparison rests on a false SPHERE-NZ construction. read the letter →

arxiv 2501.01634 v1 pith:JIOCGJUS submitted 2025-01-03 math.CO

William Gasarch , James Glenn , Clyde Kruskal This is my paper · ORCID
classification math.CO MSC 05D1011B25
keywords arithmeticprogressions3-freesetsspheremethodexactvaluesempiricalcrossoverupperboundsintegerprogrammingRamsey-typetheorems
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 asks how large a subset of {1,...,n} can be while containing no three equally spaced numbers, a set called 3-free. Its headline empirical claim is that the asymptotically best construction, the nonconstructive sphere method, first overtakes all constructive competitors at about n = $10^{9}$, so from that point on the best known sets come from a method whose proof only shows existence. The paper also pushes exact values of the maximum size sz(n) from n ≤ 150 to n ≤ 186 and gives close upper and lower bounds for 187 ≤ n ≤ 250. These numbers matter because large 3-free sets appear in applications from diagonal queens domination to communication complexity and linearity testing, and the crossover shows that the asymptotic ordering of constructions can govern practical behavior at finite but very large n.

What carries the argument

The sphere method represents each integer in base 4d+1 with digits in {-d,...,d}, identifies the number with its digit vector, and selects all numbers whose digit vectors have a fixed squared length s. Because x+z=2y would force the digit vectors to satisfy x-vector + z-vector = 2y-vector, and two distinct vectors of length sqrt(s) cannot sum to a vector of length 2sqrt(s), each individual sphere is 3-free. The SPHERE-NZ variant unions the sphere at s with the sphere at s+1 restricted to vectors with no zero coordinate; Theorem 4.18 uses a parallelogram norm identity, Lemma 4.15, to claim the union remains 3-free. The construction is made algorithmic by a dynamic program that counts digit vectors of a given norm, so the optimal parameters (d,s,k) can be found even though the proof of existence is nonconstructive.

What would settle it

For d=2, k=2, s=1 in base 9, check the three digit vectors (-1,1), (0,1), and (1,1): the outer two have squared norm 2 and no zero coordinates, the middle has squared norm 1, and the corresponding integers form a 3-term arithmetic progression; if all three are included in the SPHERE-NZ union, the claimed 3-freeness fails.

Watch

Extended reading notes

Core claim

The central discovery is a quantitative crossover among known constructions. When base-3, base-5, KD, block, and sphere methods are all coded and compared for n from $10^{1}$ up to $10^{65}$, the sphere method produces larger 3-free sets than every other method for every n ≥ $10^{9}$. The authors support the sphere construction with a new variant, SPHERE-NZ, which takes the union of two spheres of squared norms s and s+1 and imposes a nonzero-coordinate condition on the outer sphere; Theorem 4.18 asserts that this union is 3-free. In the small-n regime the paper computes sz(n) exactly for 1 ≤ n ≤ 186, gives upper and lower bounds for 187 ≤ n ≤ 250, and obtains new lower bounds such as sz(204) ≥ 42, sz(227) ≥ 45, and sz(233) ≥ 46. It also shows that using the analytic upper-bound proof numerically improves upper bounds on sz(N) by roughly 17 percent for the largest N tested.

Load-bearing premise

The proof that the SPHERE-NZ union is 3-free assumes that every would-be arithmetic progression forces the middle vector to have a zero coordinate where the nonzero condition applies, even though that condition is only imposed on the outer sphere's vectors.

Editorial extensions

If this is right

  • For n at least 10^9, the best known 3-free sets come from the nonconstructive sphere method, so anyone needing large 3-free sets in practice can use the optimized search over (d,s,k) despite the absence of an explicit construction.
  • The exact values sz(n) for n ≤ 186, the bounds for 187 ≤ n ≤ 250, and the new lower bounds for n = 204, 227, and 233 update the small-n record.
  • Among the sphere variants tested, SPHERE-NZ is the best for most n, beating plain SPHERE and SPHERE-NN in the authors' tables.
  • Using the analytic upper-bound proof numerically gives upper bounds on sz(N) that are about 17 percent better than elementary splitting for the largest tested N.
  • Beyond n ≈ 10^90, the block method overtakes the KD method, and the empirical ordering of all methods appears to settle into the asymptotic ordering.

Reading between the lines

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

  • If the theoretical gap in the proof of Theorem 4.18 is real, the empirical crossover claim would still be testable by verifying the 3-freeness of each constructed set directly, though the validity of the SPHERE-NZ union would then need a corrected condition or proof.
  • The estimated constants c for sphere and block methods, around 2.55 and 4.3 respectively, suggest the finite-n data already reflect the asymptotic quality ordering, so the crossover point at 10^9 may serve as a practical threshold for when asymptotic results dominate elementary constructions.
  • The same empirical comparison could be extended to k-APs for k ≥ 4 and to the higher-level sphere unions sketched in Theorem 4.23, where the required conditions grow more complex; the paper leaves that as future work.
  • Because the paper notes that larger 3-free sets do not automatically improve matrix multiplication algorithms, the practical payoff of the crossover is more direct in communication complexity and linearity testing than in algebraic complexity.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. This paper is an empirical survey of methods for constructing large subsets of [n] with no three-term arithmetic progressions (3-free sets). It reports exact values of sz(n) for 1 ≤ n ≤ 186, upper and lower bounds for 187 ≤ n ≤ 250, numerical applications of Roth's theorem to obtain upper bounds, and a comparison of several asymptotic constructions: Base 3, Base 5, KD, Block, and the Sphere methods. The central large-n claim is that, for n ≥ 10^9, the nonconstructive sphere methods, especially the variant called SPHERE-NZ, produce larger 3-free sets than any other tested method.

Significance. If the main claims were valid, the paper would be a useful empirical complement to the asymptotic literature on 3-free sets. The small-n exact values, the careful discussion of backtracking and linear-programming upper bounds, and the numerical comparison of Roth's upper bound against splitting are valuable and appear to be self-contained. The paper also includes reproducible dynamic-programming computations, and the fitted constants in Appendices III and V are descriptive rather than used to derive the central claim. However, the headline comparison for large n rests on Theorem 4.18, which is false. Consequently the claimed superiority of SPHERE-NZ and the associated Section 5 conclusion are unsupported and cannot be repaired by a local correction.

major comments (3)
  1. [§4.5.2, Theorem 4.18] Theorem 4.18 is false. The proof's final step claims that Lemma 4.15.6b.ii, which gives y_i = 0 for some coordinate of the middle vector, contradicts condition C (all coordinates nonzero). But C is imposed only on the sphere of norm s+1, namely A_{d,s+1,k,C}; the middle vector y has norm s and lies in A_{d,s,k}, where zero coordinates are allowed. A concrete counterexample is obtained with d=2, k=2, s=1 in base 9: the vectors x = (-1,1), y = (0,1), z = (1,1) correspond to the integers 8, 9, 10. Both x and z have squared norm 2 with all coordinates nonzero, so they lie in A_{2,2,2,C}; y has squared norm 1, so it lies in A_{2,1,2}. These three integers form a 3-AP, contradicting the theorem.
  2. [§5 and Appendix VII, Tables 7–13] The large-n comparison rests on the invalid SPHERE-NZ construction. Table 7 reports SPHERE-NZ = 5.97×10^5 for n = 10^9, and Table 8's SP column also gives 5.97×10^5 at n = 10^9, even though the text of Section 5 identifies SP as SPHERE-NN. Table 7 gives SPHERE-NN = 3.00×10^5 for n = 10^9, so the SP column is actually using the SPHERE-NZ counts. Because Theorem 4.18 is false, these numbers are not valid lower bounds for sz(n), and the observation that the sphere method beats all other methods for n ≥ 10^9 is unsupported.
  3. [§5, Observation 1] The empirical conclusion fails even if one substitutes the valid SPHERE-NN variant for the invalid SPHERE-NZ. At n = 10^9, Table 7 gives SPHERE-NN = 3.00×10^5 while Table 8 gives Base 3 = 5.24×10^5, so the valid sphere construction does not beat the Base 3 method at the claimed crossover point. The headline claim that the nonconstructive sphere methods produce the largest sets for n ≥ 10^9 therefore cannot be maintained in the paper's current form.
minor comments (4)
  1. [Throughout] There are numerous typographical errors, including "su ch sets" in the abstract, "Erdos" for "Erdős", and "Health-Brown" for "Heath-Brown" in Section 1.1; these should be corrected.
  2. [§5] The notation is inconsistent: the text says the SP column abbreviates SPHERE-NN, but the numerical values correspond to SPHERE-NZ, as noted above. The labels in Tables 8–13 should be reconciled with the definition in Section 4.5.4.
  3. [Appendix VIII, Table 16] The table header says "300,000 < N < 1,000,000" but the table includes values of N up to 178,970,459; the header or the table should be corrected.
  4. [Appendix V, Table 6] The entry for n = 10^11 reports size 1.56×10^7, which is smaller than the neighboring entries for n = 10^10 (2.74×10^7) and n = 10^12 (9.81×10^7). Since the SPHERE method should be monotone in n, this is likely a typo and should be checked.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; the empirical constructions and comparisons are self-contained, with any concern about Theorem 4.18 being a correctness issue rather than a circular one.

full rationale

The paper's constructions (Base 3, Base 5, KD, Block, Sphere variants) are explicit and checked against external benchmarks. The central large-n comparison in Section 5 is an empirical computation of sizes of explicitly defined sets, not a fitted parameter renamed as a prediction. The estimated constants c in Appendices III and V are descriptive summaries of observed sizes ('The value of c seems pretty steady') and are not used to define the sets or to derive the claim that SPHERE methods win. The proof of Theorem 4.18 does depend on Lemma 4.15 and condition C, and a careful reading shows the printed proof applies C to the norm-s vector y even though C is imposed only on the norm-(s+1) sphere; the base-9 example may contradict the theorem as stated. However, that is an internal mathematical error, not circularity: the theorem is not assumed in its own proof, the sets are not defined in terms of the conclusion, and no fitted value or self-citation is load-bearing. Therefore no circularity is present.

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

The central computational claims rest on the correctness of a hand-coded backtracking search and on Theorem 4.18. The backtracking correctness is an unverified implementation assumption, and Theorem 4.18 is false. No new physical or formal entities are introduced.

free parameters (4)
  • Backtracking information parameters L=25, m=80 = L=25, m=80
    Chosen by hand in Section 3.3.2 for the GATHER and FINAL phases; they control pruning power and feasibility but are not fitted to a target result.
  • LP prefix parameter L=30 = L=30
    Chosen in Section 3.4 partly for word-size reasons; it affects which upper bounds are obtained by the linear programming method.
  • Sphere method optimization parameters d, k, s = Varies by n, listed in Table 5
    The paper maximizes set size over admissible d, k, and s for each n. This is an optimization over the construction parameters, not a fit to data, but the resulting sizes are only valid if the construction is 3-free.
  • Estimated exponent c for sphere and block methods = About 2.28 to 2.55 for SPHERE-NZ, 4.0 to 5.3 for the Block method
    Appendices III and V fit c to sizes of the form n^(1-c/sqrt(log n)); this is a descriptive fit and is not used to derive the central claims.
assumptions (4)
  • standard math A set has no 3-AP iff no x<y<z with x+z=2y (Fact 1.6).
    Used throughout the paper as the working definition of a 3-AP.
  • standard math Base-B representation with digits in a bounded range yields digit-wise equations for x+z=2y without carries (Lemma 4.9).
    Used by all sphere variants and the base-3, base-5, and block methods.
  • domain assumption The backtracking implementation and its pruning tests are correct and exhaustive for n<=186.
    No code, formal proof, or certificates are provided; the exact values depend on this implementation assumption.
  • ad hoc to paper The union Ad,s,k union Ad,s+1,k,C is 3-free under the SPHERE-NZ condition.
    This is Theorem 4.18 in the paper. It is load-bearing for the SPHERE-NZ tables, but the proof's final step fails and a concrete counterexample exists.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Finding Large Sets Without Arithmetic Progressions of Length Three: An Empirical View and Survey II." pith.science (2026). https://pith.science/paper/JIOCGJUS

@misc{pith2026250101634,
  author       = {Pith},
  title        = {Pith review of: Finding Large Sets Without Arithmetic Progressions of Length Three: An Empirical View and Survey II},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JIOCGJUS}},
  note         = {Machine review of arXiv:2501.01634}
}
read the original abstract

There has been much work on the following question: given n how large can a subset of {1,...,n} be that has no arithmetic progressions of length 3. We call such sets 3-free. Most of the work has been asymptotic. In this paper we sketch applications of large 3-free sets, review the literature of how to construct large 3-free sets, and present empirical studies on how large such sets actually are. The two main questions considered are (1) How large can a 3-free set be when n is small, and (2) How do the methods in the literature compare to each other? In particular, when do the ones that are asymptotically better actually yield larger sets? (This paper overlaps with our previous paper with the title { Finding Large 3-Free Sets I: the Small n Case}.)

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 33 canonical work pages

  1. [1]

    Arora, C

    S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proo f verification and the hardness of approximation problems. Journal of the ACM , 45(3):501–555, 1998. https://doi.org/10.1145/278298.278306

    work page arXiv 1998

  2. [2]

    Arora and S

    S. Arora and S. Safra. Probabilistic checking of proofs: A new ch aracterization of NP. Journal of the ACM , 45(1):70–122, 1998. https://doi.org/10.1145/273865.273901

    work page arXiv 1998

  3. [3]

    F. Behrend. On set of integers which contain no three in arithmet ic progres- sion. Proceedings of the National Academy of Science (USA) , 23:331–332, 1946. http://www.pnas.org/content/32/12/331.full.pdf+html?sid=aeac9fed-6205-4b25-9f16-7a34a

    work page 1946

  4. [4]

    M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences , 47:549–595, 1993. 61

    work page 1993

  5. [5]

    Bourgain

    J. Bourgain. On triples in arithmetic progression. Ge- ometric and Functional Analysis , 9:968–984, 1999. http://www.springer.com/new+%26+forthcoming+titles+%28default%29/journal/493

    work page 1999

  6. [6]

    Chandra, M

    A. Chandra, M. Furst, and R. Lipton. Multiparty protocols. In Proceedings of the Fifteenth Annual ACM Symposium on the Theory of Computing, Boston MA, pages 94–99, 1983. http://portal.acm.org/citation.cfm?id=808737

    work page 1983

  7. [7]

    Cockayne and S

    E. Cockayne and S. Hedetniemi. On the diagonal queens dominatio n problem. Journal of Combinatorial Theory, Series A , 42:137–139, 1986

    work page 1986

  8. [8]

    Coppersmith and S

    D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation , 9:251–280, 1990. Earlier Version in STOC87

    work page 1990

Show all 34 references
  1. [9]

    Erd˝ os and P

    P. Erd˝ os and P. Tur´ an. On some sequences of integers. Journal of the London Mathe- matical Society, 11(2):261–264, 1936. http://jlms.oxfordjournals.org/

    1936

  2. [10]

    F¨ urstenberg

    H. F¨ urstenberg. Ergodic behavior of diagonal measures and a theorem of Szemer´ edi’s on arithmetic progressions. Journal of d’Analyse Mathematique , 31:204–256, 1977. http://www.cs.umd.edu/~gasarch/TOPICS/vdw/furstenbergsz.pdf

    1977

  3. [11]

    Gasarch, J

    W. Gasarch, J. Glenn, and C. Kruskal. Finding large 3-free sets I: the small n case. Journal of Computer and Systems Science , 74:628–655, 2008

    2008

  4. [12]

    W. Gowers. A new proof for Szemer´ edi’s theorem for arithmet ic progressions of length four. Geometric and Functional Analysis , 8:529–551, 1998. http://www.dpmms.cam.ac.uk/~wtg10/papers.html

    1998

  5. [13]

    W. Gowers. A new proof of Szemer´ edi’s theorem. Geometric and Functional Analysis , 11:465–588, 2001. http://www.dpmms.cam.ac.uk/~wtg10/papers/html

    2001

  6. [14]

    Graham, B

    R. Graham, B. Rothschild, and J. Spencer. Ramsey Theory. Wiley, New York, 1990

    1990

  7. [15]

    R. Guy. Unsolved problems in number theory . Springer Verlag, New York, Heidelberg, Berlin, 1981

    1981

  8. [16]

    J. Hastad. Clique is hard to approximate within n1−ǫ. Acta Mathematica, 1999. https://www.csc.kth.se/~johanh/cliqueinap.pdf

    1999

  9. [17]

    Hastad and A

    J. Hastad and A. Wigderson. Simple analysis of graph tests for lin earity. Random Structures and Algorithms , 22, 2003. Prior version in Complexity 2001. On line at http://www.math.ias.edu/~avi/PUBLICATIONS/

    2003

  10. [18]

    Heath-Brown

    R. Heath-Brown. The density of zeros of forms for which weak approximation fails. Mathematics of Computation , 59(200):612–623, 1992. 62

    1992

  11. [19]

    Ireland and M

    K. Ireland and M. Rosen. A classical introduction to modern number theory . Springer- Verlag, New York, Heidelberg, Berlin, 1982

    1982

  12. [20]

    Kushilevitz and N

    E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, Cambridge, England, 1997

    1997

  13. [21]

    L. Moser. On non-averaging sets of integers. Canadian Journal of Mathematics , 5:245– 252, 1953

    1953

  14. [22]

    K. Roth. Sur quelques ensembles d’ entiers. C.R. Acad. Sci Paris , 234:388–3901, 1952

    1952

  15. [23]

    K. Roth. On certain sets of integers. Journal of the London Mathematical So- ciety, 28:104–109, 1953. http://jlms.oxfordjournals.org/. For exposition see http://www.math.missouri.edu/~iosevich/expositorypapers.html

    1953

  16. [24]

    I. Ruzsa. Erd˝ os and the integers. Journal of Number Theory , pages 115–163, 1999. MR number 2002e:11002

    1999

  17. [25]

    Salem and D

    R. Salem and D. Spencer. On set of integers which contain no thr ee in arithmetic progression. Proceedings of the National Academy of Science (USA) , 28:561–563, 1942. http://www.cs.umd.edu/~gasarch/TOPICS/vdw/vdw.html

    1942

  18. [26]

    Samorodnitsky and L

    A. Samorodnitsky and L. Trevisan. A PCP characterization of N P with optimal amor- tized query complexity. In Proceedings of the Thirty-second Annual ACM Symposium on the Theory of Computing, Portland OR, pages 191–199, 2000

    2000

  19. [27]

    Strassen

    V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik , 14:354–356, 1969

    1969

  20. [28]

    Szem´ eredi

    E. Szem´ eredi. On sets of integers containing no four elements in arithmetic progression. Acta Math. Sci. Hung. , 20:89–104, 1974. http://www.cs.umd.edu/~gasarch/TOPICS/vdw/vdw.html

    1974

  21. [29]

    Szem´ eredi

    E. Szem´ eredi. On sets of integers containing no k ele- ments in arithmetic progression. Acta Arith. , 27:299–345, 1975. http://www.cs.umd.edu/~gasarch/TOPICS/vdw/szdensity.pdf

    1975

  22. [30]

    van der Waerden

    B. van der Waerden. Beweis einer Baudetschen Vermutung (in d utch). Nieuw Arch. Wisk., 15:212–216, 1927

    1927

  23. [31]

    van der Waerden

    B. van der Waerden. How the proof of Baudet’s conjecture wa s found. In L. Mirsky, editor, Studies in Pure Math , pages 251–260. Academic Press, 1971

    1971

  24. [32]

    S. Wagstaff. On k-free sequences of integers. Mathematics of Computation , pages 767– 771, 1972. 63

    1972

  25. [33]

    V. V. Williams, Y. Xu, Z. Xu, and R. Zhou. New bounds for matrix mu ltiplication: from alpha to omega. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 . SIAM, 2024. https://arxiv.org/abs/2307.07970

    2024 arXiv

  26. [34]

    Wroblewski

    J. Wroblewski. Nonaveraging sets search. www.math.uni.wroc.pl/~jwr/non-ave/index.htm. 64

Pith tools

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