#122: does n+f(n) pile up on the same values, for (almost) every slow-growing f?
The target (erdosproblems.com/122, OPEN, 0 claimed proofs — three people currently working on it). For which number-theoretic f is it true that for every F with F(n)/f(n)→0 almost everywhere, there are infinitely many x where the count of n with n+f(n)∈(x,x+F(x)), divided by F(x), goes to ∞? Erdős, Pomerance and Sárközy proved a concrete clustering statement for f=ω(n) (number of distinct prime factors) and reported — without publishing details — that the same works for f=τ(n) (the divisor function), and probably fails for f=φ(n) or σ(n).
Three real, separable findings, none of them the full theorem. (1) Maynard's 2016 prime-clustering theorem really does give an explicit, verifiable construction of arbitrarily large exact fibers of n+τ(n) — a CRT-forced system of affine forms where forcing divisors with prescribed τ-values and then hitting several simultaneous primes creates exact collisions, checked algebraically end to end. (2) The actual published EPS mechanism for ω(n) isn't "shifts don't change ω(n) much" (a plausible-sounding wrong guess) — it's a CRT construction that programs a forced additive contribution to ω(n+i) that exactly cancels the offset i, with a controlled statistical residual doing the rest. (3) That mechanism breaks for τ(n) for a precise algebraic reason: ω is additive over coprime factors, τ is multiplicative — so the same offset-cancellation trick that works by addition for ω needs multiplication for τ, and the natural probabilistic estimate (normal order of log τ) becomes useless once you exponentiate back to τ itself. EPS's own printed remark that τ works "with a little more difficulty" is real, but the details were never published, and a plausible reconstruction of what they might have meant runs into three concrete new gaps, honestly named rather than papered over.
Round 2, same day: the divisor-packet gap is essentially closed. Of the three named gaps, the first — realizing many prescribed τ(d)=a values cheaply enough for the CRT construction to stay useful at scale — turns out to have a clean answer. Powers of two suffice for the collision mechanism itself: a sparse packet using targets a=2⁰,2¹,...,2^(R−1) has an exact-valuation CRT modulus of only exp((2+o(1))R²log R), small enough to let R grow like √(log x)/loglog x while the modulus stays x^o(1) — genuinely large R, not just a fixed small one. If instead every value a=1,...,R is needed (a more compact packet), the modulus is exp(Θ(R²)) — both an explicit construction achieving this and a matching lower bound (forced by prime targets, since τ(d)=ℓ prime forces d=q^(ℓ−1) with no way around it) are proven. Verified independently end to end, not just algebra on paper: an explicit 3-row power-of-two collision (474381+{28,24,16}, all landing on 474413 with τ=4,8,16) and a 4-row compact collision (383976193+{16,12,8,4}, all landing on 383976213 with τ=4,8,12,16) — recomputed both from scratch with an independent divisor-count routine, not the source's own verifier, exact match on every number. What's left of the three original gaps: the uniform exact-ω distribution estimate (still open, needs something like a Sathe–Selberg result uniform in a growing modulus) and the exceptional-set robustness question.
We checked the checkable parts ourselves. Built a small real instance of the exact-collision construction from scratch — k=(4,6,8), primes (5,7,11), d_i=p_i^(k_i/2−1)=(5,49,1331), verified τ(d_i) really equals k_i/2 exactly, ran CRT for b and D, then searched for t where multiple L_i(t) are simultaneously prime. The very first hit, at t=0: y=81199, with n=81193 and n=81191 both independently satisfying n+τ(n)=81199 — a genuine, verified double collision, not asymptotic, not simulated. Also directly tested the paper's general density constraint: sieved τ(n) for n up to 5,000,000, confirmed Σ_{y≤X} r_τ(y) = 4,999,983 (essentially X, as claimed) and that the density of {y: r_τ(y)≥M} stays comfortably under 1/M at every M we checked (found real fibers up to size 7 in that range). Every citation (Maynard, Compositio Math 152 (2016), 1517–1554; Erdős–Pomerance–Sárközy I, J. Number Theory 21 (1985); EPS IV, Ramanujan J. 1 (1997)) verified directly against Crossref, exact match on title/venue/volume/pages.
A real source-hygiene catch, resolved. The source chat flagged that older archived versions of this problem's statement may have had the inequality direction reversed (f/F→0 vs. F/f→0) and couldn't access the live tracker to check. We could: the page as it stands today uses F(n)/f(n)→0, matching what the analysis assumed — so that specific worry is resolved, though the original 1997 Erdős source text itself still hasn't been independently re-read by us or the chat.
What's still open. No proof of the general arbitrary-F statement, not even reconstructed for f=ω. A fixed Maynard tuple provably can never give positive density of collision centers (its centers sit inside a finite union of prime-value sequences, density zero) — real news, but it also means the eventual proof needs a genuinely new averaged construction over a growing family of systems, not a stronger single application of Maynard. Of the two named next-step lemmas, the divisor-packet efficiency question is now answered (see below) — the uniform exact-ω residual lemma is still open.
Round 3, same day: the picture sharpens further — two of the three gaps dissolve, and the third turns out to be a real structural wall, not just a missing estimate. Gap B gets a cleaner closure than round 2's powers-of-two packet: an "odd-part subset code" — target τ-values 2^j·(product of a subset of the first few odd primes) — gives exponentially many distinct, cheaply-realized divisor-count values with CRT modulus only X^o(1), because the 2-adic part recovers j and unique factorization of the odd part recovers the subset. We built a small real instance independently (2 codewords, targets τ=4 and τ=24) and searched the actual CRT residue class for a genuine hit: at n=9437, both 9458 (τ=4) and 9438 (τ=24) land on the same value 9462 — a real, searched, not simulated collision, confirming the underlying cancellation lemma works exactly as claimed.
Gap A turns out to have been asking for more than necessary. The original framing wanted joint control over many residual progressions simultaneously — genuinely hard. But a first-moment argument only needs each progression's success counted separately and then summed — no joint distribution needed. Claudia Spiro's real 1985 paper ("Extensions of some formulae of A. Selberg," verified via a real citation search — Intl. J. Math. Math. Sci., pp. 283–302) gives exactly the arithmetic-progression-uniform exact-ω estimate this simpler version needs.
Gap C is the real wall. For this specific pairwise-coprime-support construction, the candidate collision centers are provably too sparse to survive an adversarial density-zero exceptional set for F — not a missing estimate that better bookkeeping could supply, a structural limit of building the construction from one preselected CRT code. That's honest, useful news: it names precisely why this whole line of attack can't reach the problem's actual arbitrary-F statement, redirecting future effort toward a genuinely different (averaged, multi-code) construction rather than sharpening this one further.
Round 4, same day: Gap C's wall gets a precise shape, and a concrete
redirection — checked, not just asserted. The wall isn't "one residue
class is too thin" — it's sharper. Varying the CRT code (choice of shift C)
only ever produces an F(x)-fold backward shadow of the same collision
centers; it creates no new center progressions. And a genuinely universal
bound applies regardless of construction: since R(y) := #{n: n+τ(n)=y}
satisfies Σ_{y≤X} R(y) ≤ X (trivial — n+τ(n)>n forces n What does vary usefully, and what doesn't. At the raw
squarefree-divisibility level, varying which support primes hit which targets
really can build a density-(1−o(1)) union (an explicit occupancy theorem, with
pairwise-negative-correlation second-moment bound) — we re-derived and
checked the small worked example ourselves: targets t₁=4, t₂=8, support
pool {5,7,11,13}. Code assigning 5↔4, 7↔8 gives y≡29 (mod 35); at y=239,
239−4=235=5·47 (τ=4) and 239−8=231=3·7·11 (τ=8) — both true, independently
recomputed. Swapping the assignment gives y≡18 (mod 35); at y=263, 263−4=259=
7·37 (τ=4) and 263−8=255=3·5·17 (τ=8) — also both true. The claimed union
density 1−2a+b=146/1001≈0.145854 (a=576/1001, b=297/1001, from the exact
Euler products over {5,7,11,13}) checks out digit-for-digit against direct
computation. But this occupancy trick doesn't rescue the actual odd-part
subset code Gap B/C need: the total reciprocal mass of viable prime-power
supports across all odd target primes is finite (Σ_q Σ_p 1/p^(q−1) < 3/4, a
genuine convergent series, checked against the exponent-1-vs-exponent-≥2
divergence/convergence boundary), so the full K-word subset code's viable
density collapses as exp(−Ω(K log K)) — exponentially, not polynomially, no
matter how many codes or labels are varied. The redirection is concrete, not hand-wavy. The right new
target isn't "land a τ-sized packet at one center" — it's, for each fixed
amplification M and on a dyadic scale where F(x)≍H, a positive-density set of
x with Σ_{h=1}^H R(x+h) ≥ MH. The same output-mass identity that kills the
one-center approach only imposes a sharp ceiling here (density ≤ 1/M + o(1)),
not impossibility — this formulation is a real, still-open target, needing a
genuinely different (Maynard-style, many-shift, positive-density) selection
theorem rather than one more preselected CRT code. Literature check: the
relevant tools (Chung–Erdős/Paley–Zygmund, Turán sieve, Kochen–Stone,
Davenport–Erdős, Gallagher's larger sieve, Tao–Teräväinen's τ/ω/Ω
correlations) are all real and correctly characterized as adjacent-but-not-
sufficient — none is a hidden escape hatch for the current construction, which
is honest since we'd rather report "no known shortcut" than manufacture one. Round 5, next day: the honest-fallback target from the original brief actually lands —
a genuinely new theorem, not just a sharper diagnosis of the wall. Rounds 3–4 explained
precisely why this construction can't reach the full arbitrary-F statement. What we asked for as a
consolation prize, if that stayed out of reach, was a weaker but still-new EPS-style theorem: for
every fixed m, are there infinitely many y with at least m representations y=n+τ(n)? Erdős,
Pomerance, and Sárközy never published even this weaker form for τ(n) (only for ω(n)). This round
gets it: g_τ(y) := #{n : n+τ(n)=y} satisfies g_τ(y) ≥ c·√(loglogX) / logloglogX for some
y∈[X,3X], for an absolute constant c>0 and all sufficiently large X — rigorous modulo Claudia
Spiro's real 1985 theorem (Spiro, "Extensions of some formulae of A. Selberg," Intl. J.
Math. Math. Sci. 8 (1985), 283–302 — a real paper by a real number theorist, Erdős number 1,
independently confirmed via citation search; the specific uniform arithmetic-progression estimate
it's cited for matches the paper's actual subject, though we couldn't get past Wiley's paywall to
check the exact theorem number's constants verbatim). Since the bound diverges, g_τ is unbounded,
which is exactly the new EPS-I-style corollary: for every fixed m, infinitely many y have at least m
representations as n+τ(n). The return itself had an internal inconsistency, caught and resolved before shipping,
not papered over. The document stated its own headline bound two different, NOT
equivalent ways in different sections — one phrasing that would have overstated the result by a
diverging factor. We re-derived the exponent directly from the construction's own earlier parameter
choices (the modulus-size accounting from Gap B, the packet-count K from Gap A's averaging) rather
than trusting either rendering, and confirmed the weaker, correct form above is the one the proof
actually supports. Independently verified with real numbers, not just re-read. Built three fresh
CRT-cancellation certificates from scratch (none copied from the source): the source's own 4-fold
example (n=1912865606704203022636, offsets giving τ=4,12,20,60, all colliding at n+61) refactored
independently, all four τ-values exact; its small 3-fold example (n=4543160725620, τ=6,10,14,
colliding at n+15) refactored, exact; and a wholly independent instance we built ourselves (fresh
residuals, fresh CRT modulus, searched the resulting progression cold) — found n=183033, where
n+5=183038=2·71·1289 (τ=8 ✓) and n+1=183034=23²·346 (346=2·173, τ=12 ✓) both collide at n+13,
confirming this is a genuine density phenomenon in the progression, not a coincidence special to
the source's hand-picked numbers. Also independently re-verified the odd-part subset code
construction (5 fresh instances, different primes than the source used) and the "powers of two
alone can't scale" size bound (brute-forced the combinatorial minimum against the closed-form
estimate for 24+ cases, exact match every time) — zero discrepancies found anywhere in the load-
bearing math.