A probabilistic technique for finding almost-periods of convolutions

DOI10.1007/S00039-010-0101-8MaRDI QIDQ616150zbMATH OpenOpenAlexFDO

Authors Ernie Croot, Olof Sisask

Publication date 7 January 2011

Published in Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.2978

zbMATH Keywords

arithmetic progressionBogolyubov's methodconvolutionFreiman's theoremproduct-setRoth's theoremsum-set

Mathematics Subject Classification ID

Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Arithmetic combinatorics; higher degree uniformity (11B30)

Abstract: We introduce a new probabilistic technique for finding 'almost-periods' of convolutions of subsets of groups. This gives results similar to the Bogolyubov-type estimates established by Fourier analysis on abelian groups but without the need for a nice Fourier transform to exist. We also present applications, some of which are new even in the abelian setting. These include a probabilistic proof of Roth's theorem on three-term arithmetic progressions and a proof of a variant of the Bourgain-Green theorem on the existence of long arithmetic progressions in sumsets A+B that works with sparser subsets of {1, ..., N} than previously possible. In the non-abelian setting we exhibit analogues of the Bogolyubov-Freiman-Halberstam-Ruzsa-type results of additive combinatorics, showing that product sets A B C and A^2 A^{-2} are rather structured, in the sense that they contain very large iterated product sets. This is particularly so when the sets in question satisfy small-doubling conditions or high multiplicative energy conditions. We also present results on structures in product sets A B. Our results are 'local' in nature, meaning that it is not necessary for the sets under consideration to be dense in the ambient group. In particular, our results apply to finite subsets of infinite groups provided they 'interact nicely' with some other set.

Recommendations

• On some almost periodic convolutions
• scientific article; zbMATH DE number 4196661
• scientific article; zbMATH DE number 6262857
• The exact estimation on n-widths of certain periodic convolution classes
• Periodicity in quasipolynomial convolution
• On the properties of oscillation and almost periodicity of certain convolutions
• Weak almost periodicity of convolutions
• Rational approximation of classes of convolutions of periodic functions
• On the best approximation in classes of convolutions of periodic functions
• Convergence of periodic mapping and periodic probability mapping

Cites work

• A new proof of Roth’s theorem on arithmetic progressions
• A polynomial bound in Freiman's theorem.
• Additive combinatorics
• Additive structures in sumsets
• Approximate groups. II: The solvable linear case
• Arithmetic progressions in sumsets
• Arithmetic progressions in sumsets
• Freiman's theorem for solvable groups
• Freiman's theorem in an arbitrary abelian group
• Generalized arithmetical progressions and sumsets
• scientific article; zbMATH DE number 3425719 (Why is no real title available?)
• scientific article; zbMATH DE number 5219601 (Why is no real title available?)
• scientific article; zbMATH DE number 5181747 (Why is no real title available?)
• Integer Sum Sets Containing Long Arithmetic Progressions
• ON A NONABELIAN BALOG–SZEMERÉDI-TYPE LEMMA
• On a problem of Konyagin
• On Certain Sets of Integers
• On Certain Sets of Positive Density
• On subsets of finite Abelian groups with no 3-term arithmetic progressions
• Probability Inequalities for Sums of Bounded Random Variables
• Product set estimates for non-commutative groups
• Reconstructing integer sets from their representation functions
• Roth's theorem on progressions revisited
• SETS WITH SMALL SUMSET AND RECTIFICATION
• Sums of Dilates
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The tail of the hypergeometric distribution
• Three-term arithmetic progressions and sumsets

Cited in

(46)

• Additive combinatorics and graph theory
• Sumsets of dense sets and sparse sets
• The structure of approximate groups.
• Higher moments of convolutions
• On the Bogolyubov-Ruzsa lemma
• Roth's theorem in many variables
• Coset decision trees and the Fourier algebra
• A note on bilinear exponential sums in prime fields
• Long regularly-spaced and convex sequences in dense sets of integers
• Bounds in Cohen's idempotent theorem
• Sums of multiplicative characters with additive convolutions
• Noncommutative sets of small doubling
• Finite field models in arithmetic combinatorics -- ten years on
• Roth's theorem for four variables and additive structures in sums of sparse sets
• Arithmetic progressions in sets of small doubling
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• New bounds on cap sets
• Some properties of lower level-sets of convolutions
• Growth and expansion in algebraic groups over finite fields
• Convolutions of sets with bounded VC-dimension are uniformly continuous
• A question of Bukh on sums of dilates
• From affine to two-source extractors via approximate duality
• Long arithmetic progressions in \(A+A+A\) with \(A\) a prime subset
• Structure of protocols for XOR functions
• The structure theory of set addition revisited
• Arithmetic progressions in sumsets and \(L^p\)-almost-periodicity
• On finite sets of small tripling or small alternation in arbitrary groups
• Optimality of linear sketching under modular updates
• Quantitative structure of stable sets in finite abelian groups
• The Erdős-Moser sum-free set problem
• Additive energy of regular measures in one and higher dimensions, and the fractal uncertainty principle
• Sampling-based proofs of almost-periodicity results and algorithmic applications
• Logarithmic bounds for Roth's theorem via almost-periodicity
• Exponential sum estimates over prime fields
• Growth in groups: ideas and perspectives
• An additive combinatorics approach relating rank to communication complexity
• Extractors in Paley graphs: a random model
• The Kelley-Meka bounds for sets free of three-term arithmetic progressions
• A quantitative version of the non-Abelian idempotent theorem
• On Roth's theorem on progressions
• An Explicit Croot-Łaba-Sisask Lemma Free of Probabilistic Language
• Complete type amalgamation for nonstandard finite groups
• Closed approximate subgroups: compactness, amenability and approximate lattices
• Some new results on the higher energies
• On Fourier coefficients of sets with small doubling
• On the distribution of quadratic residues

This page was built for publication: A probabilistic technique for finding almost-periods of convolutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616150)