Nonstandard methods in combinatorial number theory

4. Asymptotic Bases

Let $A$ be a set of nonnegative integers. The representation function $r_A(n)$ counts the number of representations of an integer $n$ as the sum of $2$ elements of $A$: \[ r_A(n) = \text{card} \{ (a,a') \in A^2: a \leq a' \text{ and } a+a'=n\}. \] The sumset \[ 2A = \{a+a': a,a' \in A\} \] is an asymptotic basis of order 2 if it contains all sufficiently large integers, or if, equivalently, the set $\mathbb{N}_0 \backslash 2A$ is finite.

An asymptotic basis $A$ is minimal if no proper subset of $A$ is an asymptotic basis of order 2. Equivalently, the set $A$ is a minimal asymptotic basis if, for every $a \in A$, the set $\{a' \in A: r_A(a+a') = 1\}$ is infinite.

Theorem.

(Nathanson [MR0347764]) Minimal asymptotic bases exist, but not every asymptotic basis contains a minimal asymptotic basis.

A simple example of an asymptotic basis of order 2 that does not contain a minimal asymptotic basis is $\{1\} \cup \{ 2n:n \in \mathbb{N}_0 \}$.

Theorem.

(Erdős and Nathanson [MR0564925]) Let $A$ be a set of nonnegative integers. If \[ r_A(n) > c\log n \] for some $c > (\log(4/3))^{-1}$ and all $n \geq n_0$, then $A$ is an asymptotic basis of order 2 that contains a minimal asymptotic basis of order 2.

For background and many related problems see [MR0564925], [MR0894505], [MR0347764], [MR1023923].