Sets of integers that do not contain long arithmetic progressions
From MaRDI portal
Abstract: In 1946, Behrend gave a construction of dense finite sets of integers that do not contain 3-term arithmetic progressions. In 1961, Rankin generalized Behrend's construction to sets avoiding k-term arithmetic progressions, and in 2008 Elkin refined Behrend's 3-term construction. In this work, we combine Elkin's refinement and Rankin's generalization. Arithmetic progressions are handled as a special case of polynomial progressions. In 1946, Behrend gave a construction of dense finite sets of integers that do not contain a 3-term arithmetic progression (AP). In 1961, Rankin generalized Behrend's construction to sets avoiding k-term APs. In 2008, Elkin refined Behrend's 3-term construction, and later in 2008, Green & Wolf found a distinct approach (albeit morally similar) that is technically more straightforward. This work combines Elkin's refinement and Rankin's generalization in the Green & Wolf framework. A curious aspect of the construction is that we induct through sets that do not contain a long polynomial progression in order to construct a set without a long AP. The bounds for r_k(N), the largest size of a subset of {1,2,...,N} that does not contain a k element AP, are (where log=log_2, for sufficiently large N, with n=ceiling{log k}): r_3(N) > N (sqrt{360}/(e pi^{3/2})-epsilon) sqrt[4]{2log N} * 4^{-sqrt{2 log N}}, r_k(N) > CN 2^{-n 2^{(n-1)/2} sqrt[n]{log N}+frac{1}{2n}loglog N}. The improvement over earlier work is in the simplification of the construction, the explicitness of the bound for r_3, and in the loglog term for general k.
Recommendations
Cited in
(24)- A new lower bound for van der Waerden numbers
- Threshold functions and Poisson convergence for systems of equations in random sets
- A note on multiparty communication complexity and the Hales-Jewett theorem
- Bounds on the size of progression-free sets in \(\mathbb{Z}_m^n\)
- The number of k-dimensional corner-free subsets of grids
- 3SUM, 3XOR, triangles
- Improved bounds on the dimensions of sets that avoid approximate arithmetic progressions
- Large subsets of \(\mathbb{Z}_m^n\) without arithmetic progressions
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- A note on Elkin's improvement of Behrend's construction
- Integer Sets Containing No Arithmetic Progressions
- The number of subsets of integers with no k-term arithmetic progression
- Szemerédi's Theorem in the Primes
- Colourings of uniform hypergraphs with large girth and applications
- The NOF multiparty communication complexity of composed functions
- Sets avoiding six-term arithmetic progressions in \(\mathbb{Z}_6^n\) are exponentially small
- Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small
- scientific article; zbMATH DE number 5181747 (Why is no real title available?)
- Dimensions of sets which uniformly avoid arithmetic progressions
- A blurred view of Van der Waerden type theorems
- The Kelley-Meka bounds for sets free of three-term arithmetic progressions
- Improved bounds for five-term arithmetic progressions
- Arithmetic progressions and thickness properties in self-similar Cantor sets
- A generalization of sets without long arithmetic progressions based on Szekeres algorithm
This page was built for publication: Sets of integers that do not contain long arithmetic progressions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q540042)
