Erdős Problem #332

Erdős Problem 332: differences occurring infinitely often

Statement and scope

Source: https://www.erdosproblems.com/332. This repairs the earlier GPT-5.2 packing proof: upper Banach densities of arbitrary disjoint sets cannot be added. The corrected proof uses the fact that all sets are translates of one fixed set. The sufficient condition is classical, not a new theorem.

The corrected common-interval packing argument

Starting with shift zero, repeatedly add a shift whose translate has finite intersection with all previous translates. The preceding bound forces this procedure to stop with a finite maximal set $X$. For every $t\in\mathbb Z$, some $x\in X$ has $|(A+t)\cap(A+x)|=\infty$; this is also true if $t\in X$, since $A$ is infinite. Hence $t-x\in D(A)$ and \[ \mathbb Z=X+D(A). \tag{1} \] Let $L=\max X-\min X+1$. Given an interval $[v,v+L-1]$, apply $1$ to $t=v+\max X$. Then $t-x\in D(A)$ for some $x\in X$, and $v\le t-x\le v+L-1$. Thus $D(A)$ has bounded gaps. In particular positive upper asymptotic density is sufficient.

Zero upper Banach density can still give every difference

Nevertheless $d^*(A)=0$. The gaps between the consecutive two-point blocks tend to infinity. For any fixed $K$, discard finitely many initial blocks so that every later inter-block gap is at least $K$. An interval of $N$ integers then meets at most $N/K+2$ of those blocks, hence contains at most $2N/K+4$ of their points. Restoring the fixed finite initial set contributes $O_K(1)$. Taking the supremum over intervals, then $N\to\infty$, gives $d^*(A)\le2/K$. Letting $K\to\infty$ proves the claim.

For comparison, $A=\{2^j:j\ge0\}$ has no infinitely repeated nonzero difference: in $2^u-2^v=2^v(2^{u-v}-1)$, the $2$-adic valuation determines $v$, then the value determines $u$. Hence its $D(A)$ is just $\{0\}$.

Remaining gap

COMPLETION ESTIMATE

1) FORMAL RESTATEMENT

Let $A\subseteq\mathbb N$. Define \[ D(A):=\{d\in\mathbb Z:\ d\text{ occurs infinitely often as }a_1-a_2\text{ with }a_1,a_2\in A\}. \] Equivalently, \[ D(A)=\{d\in\mathbb Z:\ |A\cap(A+d)|=\infty\}, \] where $A+d:=\{a+d: a\in A\}$.

A set $S\subseteq\mathbb Z$ has bounded gaps (is syndetic) if there exists an integer $L\ge 1$ such that every interval of $L$ consecutive integers meets $S$.

Question: what conditions on $A$ ensure that $D(A)$ has bounded gaps? The statement says that a sufficient condition is that $A$ has positive density.

2) QUICK LITERATURE/CONTEXT CHECK

I do not use any external results beyond the problem statement. I will prove from scratch the classical sufficient condition:

If $A$ has positive upper Banach density (in particular, positive asymptotic density), then $D(A)$ is syndetic.

3) ATTACK PLAN

Prove a sufficient condition (positive density) by a translate-packing argument:

$1$ Using positive upper Banach density $\delta>0$, build a finite maximal set of shifts $X$ such that the translates $A+x$ have pairwise finite intersections.

$2$ Maximality forces every translate $A+t$ to have infinite intersection with some $A+x$ from the family, which implies $t-x\in D(A)$.

$3$ Conclude $\mathbb Z = X + D(A)$, hence $D(A)$ has bounded gaps.

Also provide simple examples as sanity checks.

4) WORK

PHASE 1: FAST REALITY CHECK (sanity examples)

* If $A=2\mathbb N$ (even numbers), then $D(A)$ contains all even integers (each difference occurs infinitely often), hence has bounded gaps (gap size $2$).

* If $A=\{2^n: n\ge 0\}$, then every nonzero difference $2^i-2^j$ occurs at most once (because the binary expansion is unique), so $D(A)=\{0\}$ (if we allow $a_1=a_2$). In particular, $D(A)\cap\mathbb N$ has unbounded gaps.

So density-type hypotheses are necessary in some form.

Definitions for the proof. The upper Banach density of $A\subseteq\mathbb Z$ is \[ d^*(A):=\limsup_{N\to\infty}\ \max_{M\in\mathbb Z}\ \frac{|A\cap\{M+1,\dots,M+N\}|}{N}. \] If $A\subseteq\mathbb N$ has positive upper asymptotic density, then viewing it as a subset of $\mathbb Z$ gives $d^*(A)>0$. Also $d^*(A+t)=d^*(A)$ for every integer shift $t$ (by translation invariance of the definition).

Lemma 332.1 (finite packing by almost-disjoint translates).

Assume $d^*(A)=\delta>0$. There exists a finite set of integers $X=\{x_1,\dots,x_m\}$ such that:

(a) For all $i\neq j$, the intersection $(A+x_i)\cap(A+x_j)$ is finite.

(b) $X$ is maximal with respect to property (a): if $t\in\mathbb Z\setminus X$, then there exists $x\in X$ such that $(A+t)\cap(A+x)$ is infinite.

Moreover, necessarily $m\le 1/\delta$.

Proof. We build $X$ greedily. Start with $X=\{0\}$. While there exists an integer $t$ such that $(A+t)\cap(A+x)$ is finite for every $x\in X$, add such a $t$ to $X$. This process either stops after finitely many steps or continues indefinitely.

We show it cannot continue beyond $\lfloor 1/\delta\rfloor+1$ steps. Suppose we have constructed $m$ shifts $x_1,\dots,x_m$ with pairwise finite intersections. For each $i$, the set $A+x_i$ has upper Banach density $\delta$. Because the pairwise intersections are finite, we may delete from each $A+x_i$ a finite set so that the resulting sets become pairwise disjoint; deleting finitely many points does not change upper Banach density. Call these disjoint sets $B_i\subseteq A+x_i$ with $d^*(B_i)=\delta$. Then for any interval $I$ of length $N$, \[ \left|\bigcup_{i=1}^m B_i\cap I\right| = \sum_{i=1}^m |B_i\cap I|. \] Taking a limsup over $N$ and a max over shifts in the definition of $d^*$ yields \[ d^*\left(\bigcup_{i=1}^m B_i\right) \ge \sum_{i=1}^m d^*(B_i)=m\delta. \] But $\bigcup_i B_i\subseteq\mathbb Z$, so its upper Banach density is at most $1$. Therefore $m\delta\le 1$, i.e. $m\le 1/\delta$. So the greedy process must stop after finitely many steps, producing a finite maximal family $X$ satisfying (a). The stopping condition is exactly maximality (b). $\square$

Lemma 332.2 (maximality forces $\mathbb Z=X+D(A)$).

Let $A\subseteq\mathbb Z$ with $d^*(A)>0$, and let $X$ be as in Lemma 332.1. Then \[ \mathbb Z = X + D(A):=\{x+d: x\in X,\ d\in D(A)\}. \]

Proof. Let $t\in\mathbb Z$ be arbitrary. By maximality of $X$ (Lemma 332.1(b)), there exists $x\in X$ such that $(A+t)\cap(A+x)$ is infinite. Thus there are infinitely many integers $y$ with $y\in A+t$ and $y\in A+x$. Write $y=a_1+t=a_2+x$ with $a_1,a_2\in A$. Then \[ a_2-a_1 = t-x. \] Because this happens for infinitely many such $y$, the difference $t-x$ occurs infinitely often as a difference of two elements of $A$. Hence $t-x\in D(A)$. Therefore $t=x+(t-x)\in X+D(A)$. Since $t$ was arbitrary, $\mathbb Z\subseteq X+D(A)$, and the reverse inclusion is trivial. $\square$

Proposition 332.3 (positive density $\Rightarrow$ bounded gaps in $D(A)$).

If $A\subseteq\mathbb N$ has positive (upper) density, then $D(A)$ has bounded gaps.

Proof. Positive upper density implies positive upper Banach density: if $\overline d(A)>0$ then $d^*(A)\ge \overline d(A)>0$. Apply Lemma 332.1 to obtain a finite set $X$ and Lemma 332.2 to obtain $\mathbb Z=X+D(A)$. Let \[ L:=\max X - \min X + 1. \] This is a finite positive integer because $X$ is finite. Fix any integer $m$ and consider the interval $[m,m+L-1]$. Let $t:=m+\max X$. By $\mathbb Z=X+D(A)$ there exist $x\in X$ and $d\in D(A)$ with $t=x+d$, so $d=t-x$. Because $x\in X$, we have $\min X\le x\le \max X$, hence \[ m = t-\max X \le d = t-x \le t-\min X = m+\max X-\min X = m+L-1. \] So $d\in D(A)\cap[m,m+L-1]$. Thus every interval of length $L$ meets $D(A)$, proving bounded gaps. $\square$

5) VERIFICATION

-- Lemma 332.1: the only nontrivial point is bounding $m$. For pairwise finite intersections, deleting finitely many points makes the sets disjoint; upper Banach density is unchanged under finite modifications. The inequality $d^*(\cup B_i)\ge\sum d^*(B_i)$ holds for disjoint sets because counts add on each interval.

-- Lemma 332.2: "infinite intersection" is exactly what is needed for membership in $D(A)$.

-- Proposition 332.3: the bounded-gap constant depends on the constructed finite set $X$ but is finite.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here.

* A complete proof that positive density of $A$ implies $D(A)$ has bounded gaps (Proposition 332.3).

(ii) Exact first gap.

Find weaker hypotheses on $A$ (strictly weaker than positive density) that still force $D(A)$ to be syndetic, or determine sharp thresholds/characterizations.

(iii) Top 3 next moves (concrete targets).

1. Identify density-free conditions implying $d^*(A)>0$ on long intervals (e.g. piecewise syndeticity) and test whether they suffice for bounded gaps in $D(A)$. 2. Investigate conditions ensuring $D(A)$ has positive density (stronger than bounded gaps), and whether this can be characterized by additive energy of $A$. 3. Construct sparse sets $A$ (density $0$) where $D(A)$ is nevertheless syndetic, to map the boundary of the phenomenon.

(iv) What a minimal counterexample would likely look like.

A minimal counterexample to "$D(A)$ syndetic" under a proposed weaker condition would be a sparse $A$ whose translates almost never overlap infinitely often, so that $A\cap(A+d)$ is finite for all but a very sparse set of $d$. The powers-of-two example illustrates how extreme sparsity can force $D(A)$ to be tiny.