Skip to content

Erdős Problem #1101

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Choose an increasing sequence of pairwise coprime integers \(u_1<u_2<\cdots\) greater than one, with convergent reciprocal sum

\[ \sum_{i=1}^\infty \frac1{u_i}<\infty. \]

Remove from the positive integers every number divisible by any \(u_i\). Arrange the remaining survivors as \(a_1<a_2<\cdots\).

Erdős Problem #1101 asks whether the sieve values \(u_i\) can grow quite slowly while the gaps between successive survivors stay asymptotically as small as a sieve-theoretic lower bound permits.

A small example

Consider the first six squares of distinct primes:

\[ 4,\ 9,\ 25,\ 49,\ 121,\ 169. \]

They are pairwise coprime. If integers from \(1\) to \(200\) divisible by any of these six numbers are removed, 122 survive. The corresponding finite density product is

\[ \prod_{u\in\{4,9,25,49,121,169\}}\left(1-\frac1u\right) =\frac{442368}{715715}. \]

For the infinite prime-square sequence and \(x=1000\), the product of the first three sieve moduli is \(4\cdot9\cdot25=900\), while including the next gives \(44100\). The scale parameter below is therefore \(t_{1000}=3\).

The finite sieve does not show that the infinite prime-square sequence has the required gap property. That particular question is linked to another open Erdős problem.

What is known

Let \(t_x\) be determined by

\[ u_1\cdots u_{t_x}\le x <u_1\cdots u_{t_x+1}, \]

and write \(\delta=\prod_i(1-1/u_i)>0\). The sequence is called good when for every \(\varepsilon>0\) and all sufficiently large \(x\), the largest consecutive-survivor gap below \(x\) is less than

\[ (1+\varepsilon)t_x\delta^{-1}. \]

A standard sieve argument supplies an asymptotically matching lower bound. Erdős proved the existence of some good sequence of primes, but the main open questions require controlling their growth:

Can one choose \(u_n\) of polynomial size in \(n\)? Can one choose \(u_n\le\exp(o(n))\)?

These are different assertions; existence of one good sequence with no growth guarantee does not settle either.

GCL's current state

Authenticated source audit #2372 verifies the finite sieve and the exact scale parameter. The frozen Lean statement defines the sieve and the two open assertions, but contains unproved theorem bodies.

#1101 is a predetermined critical-review sample. Its source semantics and original proof remain to be independently audited.

What remains

Review Erdős's original 1981 paper, the strict inequality and \(a_k<x\) endpoint convention, and the precise meaning of the infinite product and its gap lower bound. Then independently assess the existence proof for a good sequence and the separate polynomial/subexponential questions.

Sources and claim boundaries

Erdős Problem #1101; Erdős (1981), p.178; frozen formal statement; authenticated source return #2372. Finite sieve arithmetic independently verified; polynomial/subexponential existence open. Critical review pending; article unaccepted.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2372 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction