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

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Created claim: DBLP publication ID (P1635): journals/combinatorica/BalogS94, #quickstatements; #temporary_batch_1731468600454
 
(One intermediate revision by one other user not shown)
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/bf01212974 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2091329824 / rank
 
Normal rank
Property / DBLP publication ID
 
Property / DBLP publication ID: journals/combinatorica/BalogS94 / rank
 
Normal rank

Latest revision as of 04:45, 13 November 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
    0 references
    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
    0 references

    Identifiers