Erdős problem #332: live audit and a sharp upper-Banach-density boundary
Access/search date: 2026-07-28 UTC.
Claim labels used throughout:
- (a) elementary-rigorous
- (b) rigorous modulo the explicitly named theorem/source
- (c) plausible/structural-unverified
- (d) computational-only
Statements transcribed from a live page are identified as source-audit facts
rather than mathematical theorems.
Result in one paragraph
The mandatory stop gate did not fire: the authoritative live page is
OPEN, displays 0 claimed proofs, and lists no current worker or interested
collaborator. I do not claim a full characterization of all \(A\). I proved
the following sharp delimiter:
\[ \boxed{\text{For every }S\subseteq\mathbb N\text{ there is }A\subseteq\mathbb N \text{ with }d^*(A)=0\text{ and }D(A)=S.} \tag{R} \]Here \(d^*\) is upper Banach density and \(D(A)\) means positive recurring
differences. The construction is an explicit superlacunary union of pairs,
and it comes with the uniform estimate
\[ \sup_M |A\cap[M,M+L)| \leq 2\bigl(1+\lfloor\log_2(1+L)\rfloor\bigr)+1. \tag{1} \]For example, taking \(e_n=1+\nu _2(n)\), \(x_1=1\),
\(y_n=x_n+e_n\), and \(x_{n+1}=2y_n+1\), the set
\(A=\bigcup_n\{x_n,y_n\}\) has \(d^*(A)=0\) and
\(D(A)=\mathbb N\). Conversely, every nonsyndetic or empty target is also
realizable at the same zero density. Combined with an independent proof of
the live comment that \(d^*(A)>0\) forces \(D(A)\) to have bounded gaps, this
shows that upper Banach density has a sharp universal dichotomy: positivity
suffices, while its zero level by itself imposes no restriction whatsoever
on \(D(A)\). All assertions in this paragraph are (a) and are proved
below. The bare arbitrary-target realization was already implicit at the
level of ordinary upper/lower density in Stewart--Tijdeman (1979); the added
point here is zero upper Banach density, the explicit two-point blocks,
and the quantitative local-count bound (1).
0. Mandatory live-page gate
I first fetched the live #332 page, its
LaTeX view, and the complete
discussion thread using the
Bright Data residential-browser route. The first body extraction was
truncated by the helper's 200-character display limit, so I made a second
browser evaluation of document.body.innerText and all links. Direct
datacenter curl was not used as the source of truth.
Verbatim current statement
> Let \(A\subseteq \mathbb{N}\) and \(D(A)\) be the set of those numbers which occur infinitely often as \(a_1-a_2\) with \(a_1,a_2\in A\). What conditions on \(A\) are sufficient to ensure \(D(A)\) has bounded gaps?
The page cites [ErGr80,p.50] and tags the problem number theory.
The page's further question “or even just \(D(A)\ne\varnothing\)” makes clear
that \(D(A)\) there means positive differences; otherwise \(0=a-a\) would
make that question vacuous. Below I therefore write
\[ D(A)=\{d\in\mathbb N:|\{a\in A:a+d\in A\}|=\infty\}. \tag{2} \]If one instead includes zero, every formula simply gains the unavoidable
element \(0\). (a)
Exact displayed state and activity markers
The rendered live state was:
- status
OPEN; - main page last edited
28 October 2025; 1 comment on this problem;0 claimed proofs for this problem;Likes this problem None;Interested in collaborating None;Currently working on this problem None;This problem looks difficult None;This problem looks tractable None;The results on this problem could be formalisable None;I am working on formalising the results on this problem None;- external database field
Formalised statement? Yes.
Thus neither the claimed-proof/solved/falsified stop condition nor the
current-worker collision condition applied.
Listed known result and the one comment
The main page says that Prikry, Tijdeman, Stewart, and others proved that
positive density of \(A\) is sufficient, referring to Stewart's 1978 and
Tijdeman's 1979 surveys. It also asks for conditions forcing the weaker
conclusions that \(D(A)\) has positive density, that
\(\sum_{d\in D(A)}1/d=\infty\), or merely that
\(D(A)\ne\varnothing\).
The displayed page does not specify in that sentence which density
convention is intended. The cited primary papers do: their theorem assumes
positive upper asymptotic density. (b)
The only comment is by aditya, posted 14:40 on 4 May 2026. It says that an
observation by GPT-5.5 Pro weakens positive natural density to positive upper
Banach density. With
\[ P=\{h\in\mathbb Z:d^*(A\cap(A-h))>0\}, \]the comment sketches a translate-packing proof that \(P\) is syndetic and
links a Google Drive document as a full proof. It explicitly says this is
not a full characterization. The site warns that comments are unverified,
and the item is not entered as a claimed proof. I do not take it on trust:
Section 2 gives a complete independent proof. (a)
1. Primary-source literature audit
Original source
The cited original source exists:
P. Erdős and R. L. Graham,
[*Old and New Problems and Results in Combinatorial Number
Theory*](https://mathweb.ucsd.edu/~ronspubs/80_11_number_theory.pdf)
(1980), p. 50. The PDF is a scan with no text layer, so I rendered and
OCRed PDF pages 45--65 and located the paragraph on printed page 50. It
records the positive-density bounded-gap result, its finite-intersection
version, the request for weaker hypotheses, and the three weaker conclusions
now shown on the live page. It additionally asks for the best gap bound in
terms of densities. The live page remains the authoritative statement for
this run. (a: bibliographic/content check)
The cited surveys and underlying paper
1. C. L. Stewart,
[*On difference sets of sets of
integers*](https://www.numdam.org/item/SDPP_1977-1978__19_1_A4_0.pdf),
Séminaire Delange-Pisot-Poitou 19 (1977--78), Exp. 5, 1--8, is the
live page's [St78]. It surveys ordinary-, infinite-, and
density-difference sets. Its Theorem 2 states the finite-translate
covering result for a set of positive upper density and hence bounded
gaps for the infinite-difference set. (b)
2. R. Tijdeman,
[*Distance sets of sequences of
integers](https://ir.cwi.nl/pub/13299/13299D.pdf), in Proceedings,
Bicentennial Congress Wiskundig Genootschap*, Part II (1979), 405--415,
is the live page's [Ti79]. Sections 2 and 5 state that positive upper
density gives bounded gaps for the infinite distance set and for finite
intersections. It also states that no bound for the largest gap can
depend only on the density. (b)
3. The full proof is C. L. Stewart and R. Tijdeman,
[*On Infinite-Difference
Sets*](https://doi.org/10.4153/CJM-1979-085-6),
Canadian Journal of Mathematics 31 (1979), 897--910. Its Theorem 2
covers \(\mathbb N_0\) by finitely many translates of \(D(A)\), and
Corollary 1 gives
\(\underline d(D(A))\geq\overline d(A)\). The paper credits an
independent proof to Prikry via Hindman's theorem; Prikry's item is
explicitly listed as a private communication, so there is no primary
Prikry manuscript to inspect. (b)
4. Stewart and Tijdeman's continuation,
[*On density-difference sets of sets of
integers*](https://doi.org/10.1007/978-3-0348-5438-2_60)
(1983), says explicitly that no simple characterization of the three
difference-set classes associated with positive-upper-density sets was
known. It concerns density-difference closure properties rather than a
later solution of #332. (b)
The 1979 paper's Theorem 3 is especially relevant to the construction below:
if \(D(A)\subseteq E\), it constructs \(B\) with \(D(B)=E\) and the same
upper and lower asymptotic densities as \(A\). Starting from a lacunary set
therefore already realizes every target \(E\) at asymptotic density zero.
That theorem does not assert zero upper Banach density. (b)
Later-search audit and honest misses
I searched exact title/phrase combinations for “infinite-difference set,”
“occur infinitely often,” “bounded gaps,” and upper Banach density; screened
the metadata for all 28 works returned by the current OpenAlex citation
endpoint for the 1979 paper; and searched 2024--2026 results. The relevant
later records I could verify concern adjacent topics such as
intersectivity, missing differences, or recurrence. For example,
R. Nair's [*On general densities and
intersectivity*](https://doi.org/10.1016/j.indag.2011.08.007)
(2011) has a primary publisher abstract about positive Banach density and
multiple recurrence along prescribed rectangles, but it does not advertise
a characterization of the recurring-difference sets in #332.
A 2005 publisher record titled *Collection of Infinite Difference Sets and
Its Application* (R. S. Yang, DOI 10.12386/A2005sxxb0055) also appeared.
Its page exposed neither abstract nor references in the indexed HTML, direct
access returned HTTP 403, and a Bright Data navigation timed out after 120
seconds. “Infinite difference set” is also used for a different Ramsey
notion, so I make no claim about that inaccessible paper.
I found no inspectable primary source claiming the requested full
characterization or superseding the live OPEN status. This is a documented
search miss, not a proof of bibliographic completeness. (c)
2. Independent proof of the live upper-Banach-density comment
For \(B\subseteq\mathbb Z\), set
\[ d^*(B)=\limsup_{L\to\infty}\sup_M \frac{|B\cap[M,M+L)|}{L}. \]Theorem 1. If \(d^*(A)=\delta>0\), then \(D(A)\) is syndetic (has bounded
gaps). (a)
Proof. Extend \(A\subseteq\mathbb N\) by zero to negative integers and
put
\[ P=\{h\in\mathbb Z:d^*(A\cap(A-h))>0\}. \tag{3} \]The set \(P\) is symmetric, contains \(0\), and
\(P\cap\mathbb N\subseteq D(A)\).
Call a finite set \(F=\{t_0,\ldots,t_m\}\) \(P\)-independent if no nonzero
difference \(t_i-t_j\) belongs to \(P\). Choose intervals \(I_r\), with
\(|I_r|\to\infty\), on which the density of \(A\) tends to \(\delta\). For
each fixed \(t_i\), translating the interval changes only
\(O(|t_i|)\) boundary points, so
\[ \frac{|(A-t_i)\cap I_r|}{|I_r|}\longrightarrow\delta. \tag{4} \]For \(i\ne j\), the intersection
\((A-t_i)\cap(A-t_j)\) is a translate of
\(A\cap(A-(t_j-t_i))\), which has upper Banach density zero by
\(P\)-independence. In particular, its density on \(I_r\) tends uniformly
to zero. The first Bonferroni inequality now gives
\[ \begin{aligned} 1 &\geq \frac{\left|\bigcup_{i=0}^m(A-t_i)\cap I_r\right|}{|I_r|}\\ &\geq \sum_{i=0}^m\frac{|(A-t_i)\cap I_r|}{|I_r|} -\sum_{0\leq iThus all \(P\)-independent finite sets have uniformly bounded cardinality.
Choose one, \(F\), of maximum cardinality. Maximality and symmetry imply
that every \(z\in\mathbb Z\) has \(z-f\in P\) for some \(f\in F\); hence
\[ P+F=\mathbb Z. \tag{6} \]A set admitting a finite translate cover (6) is syndetic. Therefore
\(P\cap\mathbb N\), and hence its superset \(D(A)\), has bounded gaps.
\(\square\)The argument bounds \(|F|\) by \(1/\delta\), but it does not bound the
diameter of \(F\), which is what controls the actual gap size. This is a
real obstruction, not an artifact of the proof. For every \(t\geq1\), let
\[ A_t=\{n\geq0:n\bmod 3t\in\{0,1,\ldots,t-1\}\}. \]Then \(d^*(A_t)=1/3\), while
\[ D(A_t)\bmod 3t =\{0,\ldots,t-1\}\cup\{2t+1,\ldots,3t-1\}. \tag{7} \]Consecutive elements of \(D(A_t)\) therefore have gaps as large as
\(t+2\). Thus no gap bound can be a function of \(\delta\) alone. (a)
This is the precisely specified residue-block version of the example
reported by Stewart--Tijdeman. (b)
3. Explicit zero-Banach-density realization
The general theorem
Theorem 2. For every \(S\subseteq\mathbb N\), there exists
\(A\subseteq\mathbb N\) such that
\[ d^*(A)=0,\qquad D(A)=S. \tag{8} \]For nonempty \(S\), the construction is effective relative to any
enumeration of \(S\). (a)
Construction for \(S\ne\varnothing\). Choose a sequence
\((e_n)_{n\geq1}\) of elements of \(S\) in which every element of \(S\)
occurs infinitely often. Define
\[ x_1=1,\qquad y_n=x_n+e_n,\qquad x_{n+1}=2y_n+1, \tag{9} \]and set
\[ A=\bigcup_{n\geq1}P_n,\qquad P_n=\{x_n,y_n\}. \tag{10} \]Exact recurring differences. The pairs are strictly ordered:
\[ x_noccurs infinitely often. A difference between a point of the new pair
\(P_n\) and any earlier point lies in
\[ [\,x_n-y_{n-1},\,y_n-x_1\,] =[\,y_{n-1}+1,\,y_n-1\,]. \tag{11} \]The intervals in (11) for different stages are disjoint. Consequently a
cross-pair difference can be created at only one stage and has only finitely
many representations. If \(d\notin S\), it is never a within-pair
difference, so it is not in \(D(A)\). Hence \(D(A)=S\). (a)
Uniform sparsity. From (9),
\[ x_{n+1}>2x_n. \tag{12} \]Fix an integer half-open interval \(I=[M,M+L)\). If \(k\) pair-starts
\(x_n\) lie in \(I\), (12) gives
\[ 2^{k-1}<1+L, \qquad k\leq1+\lfloor\log_2(1+L)\rfloor. \tag{13} \]Each such start contributes at most its two pair points. At most one
additional endpoint \(y_n\) can lie in \(I\) while its start lies to the
left of \(I\): if two did, the earlier endpoint would be below the later
start and hence below \(M\). Therefore
\[ |A\cap I| \leq2\bigl(1+\lfloor\log_2(1+L)\rfloor\bigr)+1. \tag{14} \]The right side divided by \(L\) tends to zero uniformly in \(M\). This
proves \(d^*(A)=0\). (a)
If \(S=\varnothing\), take \(A=\{2^n:n\geq0\}\). Its consecutive gaps tend
to infinity, so every fixed positive difference has only finitely many
representations; the same lacunary interval count gives \(d^*(A)=0\).
This completes Theorem 2. (a)
Closed-form targets
For the most direct bounded-gap example, take
\[ e_n=1+\nu _2(n). \tag{15} \]Every \(k\geq1\) occurs at
\(n=2^{k-1}(2j+1)\) for all \(j\geq0\). Equations (9)--(10) then give
\[ \begin{split} P_1,\ldots,P_8={}& \{1,2\},\{5,7\},\{15,16\},\{33,36\},\\ &\{73,74\},\{149,151\},\{303,304\},\{609,613\}. \end{split} \]This explicit \(A\) has \(d^*(A)=0\) and \(D(A)=\mathbb N\). (a)
For a non-syndetic comparison, take
\[ e_n=(1+\nu _2(n))^2. \]The same recurrence gives a zero-upper-Banach-density set whose recurring
positive differences are exactly the squares. Taking a repeating
enumeration of any finite set, or an interleaved enumeration of any infinite
set, gives every other target. (a)
What this does and does not settle
Theorem 2 is a counterexample to every proposed conclusion based merely on
“\(A\) has density zero,” even when “density” is strengthened to upper
Banach density: at \(d^*(A)=0\), the set \(D(A)\) can be empty, finite,
syndetic, nonsyndetic, of any density behavior, or exactly \(\mathbb N\).
In particular:
- upper Banach density \(>0\) is sufficient by Theorem 1;
- upper Banach density \(>0\) is not necessary, by (15);
- upper Banach density \(=0\) does not even force \(D(A)\ne\varnothing\);
- no scalar weakening of positivity at the zero endpoint can distinguish
bounded-gap from unbounded-gap outcomes. (a)
This is a sharp density-only diagnosis, not a full answer to the open-ended
request for structural conditions.
4. A clean reduction for any further structural hypothesis
Define the symmetric recurring-correlation set
\[ P_\infty(A)= \{h\in\mathbb Z:|A\cap(A-h)|=\infty\} =D(A)\cup(-D(A))\cup\{0\}. \tag{16} \]Packing criterion. Suppose there is a finite \(K\) such that every
finite \(F\subseteq\mathbb Z\) satisfying
\[ f-g\notin P_\infty(A)\quad(f\ne g) \tag{17} \]has \(|F|\leq K\). Then \(D(A)\) has bounded gaps. (a)
Indeed, choose a set \(F\) of maximum possible size under (17). Exactly as
in (6), maximality gives \(P_\infty(A)+F=\mathbb Z\), so
\(P_\infty(A)\), and then its positive part \(D(A)\), is syndetic.
This isolates a concrete missing lemma for any proposed hypothesis \(H\) on
\(A\):
> Prove from \(H\) that only boundedly many translates \(A-f\) can have all
> pairwise intersections finite.
Positive upper Banach density supplies that lemma through (5). Theorem 2
shows that no argument using only \(d^*(A)=0\) can supply it: choosing
\(S=\varnothing\) makes the packing number infinite, while choosing
\(S=\mathbb N\) makes it one. Thus future progress below the positive
Banach-density threshold must impose genuine recurrence/translate-overlap
structure, not merely a counting-function lower bound. (a)
For the weakest live-page alternative there is a complete elementary
criterion already noted in the 1979 paper:
if \(A=\{a_1 If infinitely many consecutive gaps are at most \(H\), one of the values \(1,\ldots,H\) repeats infinitely often. Conversely, infinitely many pairs at a fixed distance \(d\) force infinitely many consecutive gaps at most \(d\). (a) The complete standard-library checker is It generates all data from scratch and: 1. verifies the recurrence, ordering, exact stage intervals (11), and pairwise disjointness of 59,075 cross-difference values for the first 180 pairs of the all-positive target; 2. repeats the mechanism for the square target and 46,649 cross-difference values; 3. exactly maximizes finite-prefix occupancy over several interval lengths and checks (14); 4. checks the density-\(1/3\) periodic family (7) for \(1\leq t\leq40\); 5. exhausts 2,036 nonempty subsets of cyclic groups of orders at most 10, independently checking the finite translate-packing analogue behind (5)--(6). Items in this list are finite checks (d). The infinite conclusions come from the elementary proofs above, not extrapolation. Run: On Python 3.12.3 the run took 0.13 seconds, used 28,816 KB maximum resident memory, and printed: The open problem is not closed: Theorem 2 deliberately demonstrates why density alone cannot characterize the zero-Banach-density regime. The verified gain is an explicit universal sparse realization theorem, including a closed-form density-zero \(A\) with \(D(A)=\mathbb N\), plus the packing reduction in Section 4. A genuinely broader sufficient condition now has a precise target: it must bound the translate packing number (17), or supply a different structural mechanism forcing those recurring correlations to be syndetic. (a) PARTIAL: Proved an explicit zero-upper-Banach-density realization \(D(A)=S\) for every \(S\subseteq\mathbb N\), independently verified positive-upper-Banach sufficiency and the packing reduction, and ran the standalone checker; the full structural characterization remains open.5. Standalone independent checker
runs/erdos332_wave8s_reverify.py, SHA-25622fa846534d07a1e9c07e7a4a10cc3262be7bc429d26d5efca1225d02a5b6a52.python3 runs/erdos332_wave8s_reverify.py
all-positive target: {'pairs': 180, 'points': 360, 'cross_values': 59075, 'largest_point_bits': 182, 'minimum_occupancy_bound_slack': 3}
first eight pairs: [(1, 2), (5, 7), (15, 16), (33, 36), (73, 74), (149, 151), (303, 304), (609, 613)]
intra-pair counts: {1: 90, 2: 45, 3: 23, 4: 11, 5: 6, 6: 3, 7: 1, 8: 1}
square target: {'pairs': 160, 'points': 320, 'cross_values': 46649, 'largest_point_bits': 162, 'minimum_occupancy_bound_slack': 3}
target squares seen: [1, 4, 9, 16, 25, 36, 49, 64]
density-1/3 periodic family:
columns: t, occupied residues, modulus, largest D step
(1, 1, 3, 3)
(2, 2, 6, 4)
(3, 3, 9, 5)
(4, 4, 12, 6)
(5, 5, 15, 7)
(38, 38, 114, 40)
(39, 39, 117, 41)
(40, 40, 120, 42)
finite popular-difference analogue: {'groups_through': 10, 'subsets_checked': 2036}
ALL CHECKS PASSED
6. Final assessment