Sets of integers that do not contain long arithmetic progressions

MaRDI QIDQ540042zbMATH OpenFDO

Authors Kevin O'Bryant

Publication date 1 June 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0811.3057, https://eudml.org/doc/228885, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p59.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

arithmetic progressions

Mathematics Subject Classification ID

Arithmetic progressions (11B25)

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.

Review text

Summary: Combining ideas of Rankin, Elkin, Green and Wolf, we give constructive lower bounds for \(r_k(N)\), the largest size of a subset of \(\{1,2,\dots,N\}\) that does not contain a \(k\)-element arithmetic progression: For every \(\varepsilon>0\), if \(N\) is sufficiently large, then \[ r_3(N)\geq N \left(\frac{6\cdot 2^{3/4} \sqrt{5}}{e \,\pi^{3/2}}-\varepsilon\right) \exp\left({-\sqrt{8\log N}+\tfrac14\log\log N}\right), \] \[ r_k(N) \geq N \, C_k\,\exp\left({-n 2^{(n-1)/2} \sqrt[n]{\log N}+\tfrac{1}{2n}\log\log N}\right), \] where \(C_k>0\) is an unspecified constant, \(\log=\log_2\), \(\exp(x)=2^x\), and \(n=\lceil\log k\rceil\). These are currently the best lower bounds for all \(k\), and are an improvement over previous lower bounds for all \(k\neq 4\).

Recommendations

• Large subsets of \(\mathbb{Z}_m^n\) without arithmetic progressions
• Sets without k‐term progressions can have many shorter progressions
• Bounds on the size of progression-free sets in \(\mathbb{Z}_m^n\)
• The number of subsets of integers with no k-term arithmetic progression

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)