A statistical theorem of set addition (Q1340134): Difference between revisions

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)\).