A probabilistic technique for finding almost-periods of convolutions

DOI10.1007/S00039-010-0101-8zbMATH Open1234.11013arXiv1003.2978OpenAlexW2161591058MaRDI QIDQ616150FDOQ616150

Authors: Ernie Croot, Olof Sisask 

Publication date: 7 January 2011

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

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.

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

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

zbMATH Keywords

convolutionarithmetic progressionFreiman's theoremRoth's theoremBogolyubov's methodproduct-setsum-set

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (42)

• Structure of Protocols for XOR Functions
• Logarithmic bounds for Roth's theorem via almost-periodicity
• Extractors in Paley graphs: a random model
• Roth's theorem in many variables
• Quantitative structure of stable sets in finite abelian groups
• Optimality of linear sketching under modular updates
• From Affine to Two-Source Extractors via Approximate Duality
• Noncommutative sets of small doubling
• Complete type amalgamation for nonstandard finite groups
• Long arithmetic progressions in \(A+A+A\) with \(A\) a prime subset
• Growth and expansion in algebraic groups over finite fields
• Long regularly-spaced and convex sequences in dense sets of integers
• Sums of multiplicative characters with additive convolutions
• Finite field models in arithmetic combinatorics -- ten years on
• Some properties of lower level-sets of convolutions
• New bounds on cap sets
• Exponential sum estimates over prime fields
• Arithmetic Progressions in Sumsets and L^p-Almost-Periodicity
• Sumsets of dense sets and sparse sets
• The Kelley-Meka bounds for sets free of three-term arithmetic progressions
• The Erdős–Moser Sum-free Set Problem
• Higher moments of convolutions
• Growth in groups: ideas and perspectives
• The structure theory of set addition revisited
• On Roth's theorem on progressions
• Roth's theorem for four variables and additive structures in sums of sparse sets
• Arithmetic progressions in sets of small doubling
• A quantitative version of the non-Abelian idempotent theorem
• A question of Bukh on sums of dilates
• On finite sets of small tripling or small alternation in arbitrary groups
• Convolutions of sets with bounded VC-dimension are uniformly continuous
• An Explicit Croot-Łaba-Sisask Lemma Free of Probabilistic Language
• On the Bogolyubov-Ruzsa lemma
• Closed approximate subgroups: compactness, amenability and approximate lattices
• Coset decision trees and the Fourier algebra
• Additive energy of regular measures in one and higher dimensions, and the fractal uncertainty principle
• An Additive Combinatorics Approach Relating Rank to Communication Complexity
• A note on bilinear exponential sums in prime fields
• Bounds in Cohen's idempotent theorem
• The structure of approximate groups.
• Additive combinatorics and graph theory
• Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition

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)