On a problem of Erdös and Turán and some related results
type: Item
instance of: scholarly article
title: On a problem of Erdös and Turán and some related results
zbMATH Open document ID: 0834.11007
author: Noga Alon
author: Mihail N. Kolountzakis
published in: Journal of Number Theory
publication date: 1996-03-31T00:00:00Z
review text: 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\).
reviewed by: Martin Helm
Mathematics Subject Classification ID: 11B13
zbMATH DE Number: 821865
zbMATH Keywords: additive basis
zbMATH Keywords: Erdös-Turan conjecture
zbMATH Keywords: asymptotic basis of order 2
zbMATH Keywords: probabilistic method
MaRDI profile type: Publication
full work available at URL: jnth.1995.1129
OpenAlex ID: W2093977403
DOI: 10.1006/JNTH.1995.1129
Recommended article: On a problem of Erdős-Turán
Recommended article: On a Turán type problem of Erdős
Recommended article: On a Theorem of Erdos and Turan
Recommended article: Q3344281
Recommended article: On the Erdős-Turán conjecture
Recommended article: On a problem of Erdös and Taylor
Recommended article: On a problem of Erdős and Szemerédi
Recommended article: Q5659540
description: scientific article; zbMATH DE number 821865