ERDŐS/DAILY ▸

← back to the ledger

ERDőS #332 · PARTIAL

Erdős problem #332: live audit and a sharp upper-Banach-density boundary

Access/search date: 2026-07-28 UTC.

Claim labels used throughout:

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:

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 (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, 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)

  1. R. Tijdeman,

Distance sets of sequences of integers, 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)

  1. The full proof is C. L. Stewart and R. Tijdeman,

On Infinite-Difference Sets, 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)

  1. Stewart and Tijdeman's continuation,

On density-difference sets of sets of integers (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 (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 i<j\leq m} \frac{|(A-t_i)\cap(A-t_j)\cap I_r|}{|I_r|}. \end{aligned} \]

Letting \(r\to\infty\) yields

\[ (m+1)\delta\leq1. \tag{5} \]

Thus 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_n<y_n<x_{n+1}. \]

The within-pair positive difference is \(e_n\), so every member of \(S\) occurs 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:

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<a_2<\cdots\}\), then

\[ D(A)\ne\varnothing \quad\Longleftrightarrow\quad a_{n+1}-a_n\not\longrightarrow\infty. \tag{18} \]

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)

5. Standalone independent checker

The complete standard-library checker is runs/erdos332_wave8s_reverify.py, SHA-256 22fa846534d07a1e9c07e7a4a10cc3262be7bc429d26d5efca1225d02a5b6a52. 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;

  1. repeats the mechanism for the square target and 46,649 cross-difference

values;

  1. exactly maximizes finite-prefix occupancy over several interval lengths

and checks (14);

  1. checks the density-\(1/3\) periodic family (7) for \(1\leq t\leq40\);
  2. 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:

python3 runs/erdos332_wave8s_reverify.py

On Python 3.12.3 the run took 0.13 seconds, used 28,816 KB maximum resident memory, and printed:

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

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.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger