Source-linked AI summary
An Improved Construction of Progression-Free Sets
Michael Elkin
TL;DR
The paper addresses the long-standing problem of constructing large progression-free subsets of {1,2,...,n}. It replaces Behrend’s sphere-based construction with an annulus-based construction and improves Behrend’s lower bound by a factor of Θ(√log n), while showing that Behrend’s construction is not optimal.
Problem
The paper studies how to construct large subsets of {1,2,...,n} containing no arithmetic triple, a central additive-number-theory problem whose Behrend lower bound had not improved for more than sixty years.
Method
The construction replaces Behrend’s sphere with a thin annulus containing a large convexly independent subset of integer points, using an elementary and self-contained proof.
Results
The construction improves Behrend’s lower bound by a factor of Θ(√log n) and shows that Behrend’s construction is not optimal.
Takeaways & Limitations
The result provides the first reported improvement over Behrend’s lower bound in more than sixty years within the paper’s progression-free-set setting.
Takeaways & Limitations
The construction still relies on the Pigeonhole Principle, and the authors were unable to formally prove that the proposed alternative annulus has sufficiently many integer points.
Abstract
from arXiv · showhide
The problem of constructing dense subsets S of {1,2,..,n} that contain no arithmetic triple was introduced by Erdos and Turan in 1936. They have presented a construction with |S| = Ω(n^{\log_3 2}) elements. Their construction was improved by Salem and Spencer, and further improved by Behrend in 1946. The lower bound of Behrend is |S| = Omega({n \over {2^{2 \sqrt{2} \sqrt{\log_2 n}} \cdot \log^{1/4} n}}). Since then the problem became one of the most central, most fundamental, and most intensively studied problems in additive number theory. Nevertheless, no improvement of the lower bound of Behrend was reported since 1946. In this paper we present a construction that improves the result of Behrend by a factor of Theta(\sqrt{\log n}), and shows that |S| = Omega({n \over {2^{2 \sqrt{2} \sqrt{\log_2 n}}}} \cdot \log^{1/4} n). In particular, our result implies that the construction of Behrend is not optimal. Our construction and proof are elementary and self-contained.
1 Introduction
The paper studies dense progression-free subsets of {1,2,...,n}, a central additive-number-theory problem whose best lower bound had remained Behrend’s for more than sixty years. It improves that bound using an elementary, self-contained construction based on a thin annulus and a large convexly independent subset.
- Problem: The problem asks for large subsets of {1,2,...,n} containing no arithmetic triple and is a central problem in additive number theory.For a progression-free set, no element is the arithmetic average of two other distinct elements.
- Prior work: Erdős–Turan, Salem–Spencer, and Behrend progressively improved lower bounds for the largest progression-free-set size ν(n).The supplied passages identify Behrend’s 1946 construction as the strongest of these successive lower bounds.
- Contribution: The paper improves Behrend’s lower bound by a factor of Θ(√log n), after more than sixty years without an improvement.The result also demonstrates that Behrend’s construction is not optimal.
- Method: The construction replaces Behrend’s sphere with a thin annulus containing a large convexly independent subset of integer points.The annulus width is chosen as large as possible while retaining a constant fraction of its integer points in the selected subset.
- Scope: The paper notes that its construction, like Behrend’s, relies on the Pigeonhole Principle and may extend to progression-free sets avoiding longer arithmetic progressions.The authors identify independence from that principle as an unresolved direction and connect the technique to Rankin’s generalization.
2 Preliminaries
The preliminaries define progression-free sets, asymptotic notation, logarithm conventions, vector norms, convex independence, and geometric quantities used later. They also introduce standard interval and ball-volume notation.
- Geometric notation: They establish standard notation for intervals, integer ranges, unit-ball volumes, and the Gamma function used in later estimates.The unit-ball volume is denoted β_ℓ, with its Gamma-function representation introduced in this section.
- Definitions: A progression-free set contains no arithmetic triple, and ν(n) denotes the largest such subset of [{n}].An arithmetic triple consists of three distinct integers, one of which is the average of the other two.
- Asymptotic notation: The paper defines O, Ω, Θ, and o using eventual constant-factor or vanishing asymptotic comparisons.These conventions apply to integer and positive real functions as specified.
- Notation: Unless explicitly stated otherwise, log denotes the base-2 logarithm and ln denotes the natural logarithm.
- Geometric definitions: The preliminaries define convex combinations and convexly independent vector sets for the geometric construction.A convexly independent set contains no vector that is a non-trivial convex combination of two other members.
3 Behrend Construction
Behrend’s construction encodes equal-norm integer vectors as digits to obtain progression-free sets, with the state-of-the-art lower bound improved by a factor of Θ(√log n) in this presentation.
- The Behrend lower bound is improved by a factor of Θ(√log n).
- Behrend’s construction starts with a parameter k, sets y = n^(1/k)/2, and samples vectors uniformly from [{0, y−1}]^k.
- A value T is selected so that many sampled vectors have the same integer squared norm, producing a large set S of equal-norm vectors.
- Equal norms rule out three distinct mapped integers forming an arithmetic triple, yielding a progression-free set with the stated lower-bound scale.
- The vectors are mapped injectively to integers using base-(2y) digits, preserving set size while translating vector relations into arithmetic relations.
4 Our Construction
The new construction replaces Behrend’s sphere with a thin annulus and extracts many convexly independent integer points before applying the same digit encoding.
- The construction presents progression-free sets S ⊆ [{n}] with at least the paper’s improved lower-bound scale.
- A thin annulus is chosen to contain many integer points, and its width is partitioned so one subannulus contains a substantial share.
- The construction shows that at least half of the relevant integer points form a convexly independent subset.
- Mapping the convexly independent vectors to integers preserves their cardinality and makes the resulting set progression-free.
- The argument bounds non-exterior annulus points by associating them with short integer vectors δ and controlling the number of such vectors.
5 Discrepancy between Volume and Number of Integer Points
This section controls the discrepancy between volume and lattice-point counts in ball and half-space intersections, including after rotating the lattice basis.
- The analysis compares integer-point counts with volumes of intersections between balls, annuli, and coordinate half-spaces.
- The section proves the bound needed to complete the lower-bound argument for the discrepancy between volume and integer-point counts.
- A discrepancy estimate is established inductively for dimensions that may grow with the radius parameter.
- Because the argument rotates the vector space, the relevant lattice is rotated as well, and the estimate must apply to that rotated lattice.
- The proof uses Euler’s sum formula and auxiliary properties of the function ψ to control the lattice-volume discrepancy.
6 Conclusion
The paper improves Behrend’s lower bound by a factor of Θ(√log n). Removing reliance on the Pigeonhole Principle remains an unresolved direction requiring sharper probabilistic estimates.
- A factor of Θ(√log n) improves Behrend’s lower bound.
- The construction still relies on the Pigeonhole Principle, as does Behrend’s argument.
- Making the construction independent of the Pigeonhole Principle would require formalizing a probabilistic comparison involving the variable Z.The authors have not found sufficiently precise estimates to prove this comparison formally.