A statistical theorem of set addition (Q1340134): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q228786 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Imre Z. Ruzsa / rank | |||
Normal rank |
Revision as of 13:53, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A statistical theorem of set addition |
scientific article |
Statements
A statistical theorem of set addition (English)
0 references
15 May 1995
0 references
Let \(A\) be a set of \(n\) integers. Suppose that for some \(c>0\) there are \(cn\) numbers that have at least \(cn\) representations of the form \(a+a'\), \(a,a'\in A\). The main result of the paper asserts that in this case there is a subset \(A'\subset A\) such that \(| A'| \geq c'n\), \(| A'+ A'|\leq c''n\), where \(c'\), \(c''\) are positive constants that depend only on \(c\). Since the structure of such sets \(A'\) is well understood by a famous result of G. Freiman, we have essentially a complete understanding of these sets. This is a basic result with many possible applications, of which the paper mentions the following problem of P. Erdős: if \(A\) contains \(cn^ 2\) 3-term arithmetic progressions, it contains an arithmetic progression of length \(k\) for \(n> n_ 0(k,c)\).
0 references
sumsets
0 references
inverse additive problems
0 references
3-term arithmetic progressions
0 references