Putnam 2004, Problem B-6

Let $\mathcal{A}$ be a non-empty set of positive integers, and let $N(x)$ denote the number of elements of $\mathcal{A}$ not exceeding $x$. Let $\mathcal{B}$ denote the set of positive integers $b$ that can be written in the form $b = a - a'$ with $a \in \mathcal{A}$ and $a' \in \mathcal{A}$. Let $b_1 < b_2 < \cdots$ be the members of $\mathcal{B}$, listed in increasing order. Show that if the sequence $b_{i+1} - b_i$ is unbounded, then
\[
\lim_{x \to \infty} \frac{N(x)}{x} = 0.
\]


Solution:
**First solution:** (based on a solution of Dan Bernstein) Note that for any $b$, the condition that $b \notin \mathcal{B}$ already forces $\limsup N(x)/x$ to be at most $1/2$: pair off $2mb + n$ with $(2m+1)b + n$ for $n = 1, \ldots, b$, and note that at most one member of each pair may belong to $\mathcal{A}$. The idea of the proof is to do something similar with pairs replaced by larger clumps, using long runs of excluded elements of $\mathcal{B}$.

Suppose we have positive integers $b_0 = 1, b_1, \ldots, b_n$ with the following properties:

(a) For $i = 1, \ldots, n$, $c_i = b_i/(2b_{i-1})$ is an integer.

(b) For $e_i \in \{-1,0,1\}$, $|e_1b_1 + \cdots + e_nb_n| \notin \mathcal{B}$.

Each nonnegative integer $a$ has a unique "base expansion"
$$a = a_0b_0 + \cdots + a_{n-1}b_{n-1} + mb_n \quad (0 \leq a_i < 2c_i);$$
if two integers have expansions with the same value of $m$, and values of $a_i$ differing by at most 1 for $i = 0, \ldots, n-1$, then their difference is not in $\mathcal{B}$, so at most one of them lies in $\mathcal{A}$. In particular, for any $d_i \in \{0, \ldots, c_i - 1\}$, any $m_0 \in \{0, 2c_0 - 1\}$ and any $m_n$, the set
$$\{m_0b_0 + (2d_1 + e_1)b_1 + \cdots$$
$$+ (2d_{n-1} + e_{n-1})b_{n-1} + (2m_n + e_n)b_n\},$$
where each $e_i$ runs over $\{0,1\}$, contains at most one element of $\mathcal{A}$; consequently, $\limsup N(x)/x \leq 1/2^n$.

We now produce such $b_i$ recursively, starting with $b_0 = 1$ (and both (a) and (b) holding vacuously). Given $b_0, \ldots, b_n$ satisfying (a) and (b), note that $b_0 + \cdots + b_{n-1} < b_n$ by induction on $n$. By the hypotheses of the problem, we can find a set $S_n$ of $6b_n$ consecutive integers, none of which belongs to $\mathcal{B}$. Let $b_{n+1}$ be the second-smallest multiple of $2b_n$ in $S_n$; then $b_{n+1} + x \in S_n$ for $-2b_n \leq x \leq 0$ clearly, and also for $0 \leq x \leq 2b_n$ because there are most $4b_n - 1$ elements of $S_n$ preceding $b_{n+1}$. In particular, the analogue of (b) with $n$ replaced by $n+1$ holds for $e_{n+1} = 0$ because (b) was already known. Since the analogue of (a) holds by construction, we have completed this step of the construction and the recursion may continue.

Since we can construct $b_0, \ldots, b_n$ satisfying (a) and (b) for any $n$, we have $\limsup N(x)/x \leq 1/2^n$ for any $n$, yielding $\lim N(x)/x = 0$ as desired.

**Second solution:** (by Paul Pollack) Let $S$ be the set of possible values of $\limsup N(x)/x$; since $S \subseteq [0,1]$ is bounded, it has a least upper bound $L$. Suppose by way of contradiction that $L > 0$; we can then choose $\mathcal{A}, \mathcal{B}$ satisfying the conditions of the problem such that $\limsup N(x)/x > 3L/4$.

To begin with, we can certainly find some positive integer $m \notin \mathcal{B}$, so that $\mathcal{A}$ is disjoint from $\mathcal{A} + m = \{a + m : a \in \mathcal{A}\}$. Put $\mathcal{A}' = \mathcal{A} \cup (\mathcal{A} + m)$ and let $N'(x)$ be the size of $\mathcal{A}' \cap \{1, \ldots, x\}$; then $\limsup N'(x)/x = 3L/2 > L$, so $\mathcal{A}'$ cannot obey the conditions of the problem statement. That is, if we let $\mathcal{B}'$ be the set of positive integers that occur as differences between elements of $\mathcal{A}'$, then there exists an integer $n$ such that among any $n$ consecutive integers, at least one lies in $\mathcal{B}'$. But
$$\mathcal{B}' \subseteq \{b + em : b \in \mathcal{B}, e \in \{-1,0,1\}\},$$
so among any $n + 2m$ consecutive integers, at least one lies in $\mathcal{B}$. This contradicts the condition of the problem statement.

We conclude that it is impossible to have $L > 0$, so $L = 0$ and $\lim N(x)/x = 0$ as desired.

**Remark:** A hybrid between these two arguments is to note that if we can produce $c_1, \ldots, c_n$ such that $|c_i - c_j| \notin \mathcal{B}$ for $i,j = 1, \ldots, n$, then the translates $\mathcal{A} + c_1, \ldots, \mathcal{A} + c_n$ are disjoint and so $\limsup N(x)/x \leq 1/n$. Given $c_1 \leq \cdots \leq c_n$ as above, we can then choose $c_{n+1}$ to be the largest element of a run of $c_n + 1$ consecutive integers, none of which lie in $\mathcal{B}$.