On the number of popular differences (Q980505): Difference between revisions

The paper shows the existence of a \(c>0\) such that for any set of integers \(A\) with at least two elements, and any \(m<c|A|/\ln |A|\), there are at most \(m\) integers \(b>0\) satisfying \(|(A+b)\setminus A|\leq m\), or equivalently, there are at most \(m\) positive integers possessing \(|A|-m\) (or more) representation as a difference of two elements of \(A\). The result is the best possible in the sense that for each positive integer \(m\) there exists a finite set of integers \(A\) with \(|A|>m \log_2(m/2) \) such that \(|(A+b)\setminus A|\leq m\) holds for \(b=1,2,...,m+1\). For an alternative formulation of the main result, for finite subsets \(A\) and \(B\) of an abelian group write \(\mu_A(B)=\max \{ |(A+b)\setminus A| : b\in B\}\). The alternative formulation is that there is a (small) \(c>0\) such that \(\mu_A(B)\geq |B|\) holds for all finite subsets \(A,B\) of integers with \(|A|>1\) and \(|B|<c |A|/ \ln |A|\). Interestingly, the following, somewhat weaker result follows from Graham's famous g.c.d. conjecture, which was proved by \textit{R. Balasubramanian} and \textit{K. Soundararajan} [Acta Arith. 75, No. 1, 1--38 (1996; Zbl 0853.11002)]: \(\mu_A(B)\geq |B|\) holds for all finite subsets \(A,B\) of integers with \(|B|<c\sqrt{|A|}\).