On a problem of Erdös and Turán and some related results
For \(A\subset \mathbb{N}\), \(n,N\in \mathbb{N}\) let \(r_A (n):= |\{ (a,b): a,b\in A\), \(a\leq b\), \(n= a+b\}|\), \(h_{A, N} (n):= |\{ (a, b): a,b\in A\cap [1, N^2 ]\), \(n= a- b\}|\), and \(A(x):= \sum_{a\in A, 1\leq a\leq x}1\). \(A\) is called an asymptotic basis of order 2 of \(\mathbb{N}\) if there exists \(n_1\in \mathbb{N}\) such that \(r_A (n)> 0\) for all \(n> n_1\). A conjecture of Erdös and Turán asserts that for any asymptotic basis of order 2 of \(\mathbb{N}\), \(\limsup_{n\to\infty} r_A (n)= \infty\). Erdös has proved that \(r_A (n)=1\) for all sufficiently large \(n\) cannot be true, showing that any sequence \(A\) with \(A(x) \gg \sqrt {x}\) satisfies (1) \(\sum_{n=1}^N h_{A, N} (n) \gg N\log N\). Indeed, an explicit construction shows that (1) is best possible. Employing the probabilistic method the authors establish stronger results, proving the existence of a sequence \(A\subset \mathbb{N}\) with \(A(x)\gg \sqrt {x}\) such that for any \(N\in \mathbb{N}\), \[ c_1\log n\leq h_{A, N} (n)\leq c_2\log n \] for all \(n\in [1,N ]\) and suitably chosen constants \(c_1\), \(c_2\). It is also proved in this paper that for every \(M\subset \mathbb{N}\) there exists \(A\subset \mathbb{N}\) such that \(M\cap (A- A)= \emptyset\) and \(A(x)> x/ (M(x)+ 1)\). Furthermore the authors show that this result is essentially best possible and they demonstrate how to construct a sequence \(A\) with \(A(x)> cx/ (M(x) +1)\) for which every element of \(M\) is represented exactly as many times as wanted as a difference of elements of \(A\).
scientific article; zbMATH DE number 821865