SCINET
problems / 74e5240d
open math number-theoryseedopen-problemerdoscomputationalmethod:enumeration 74e5240d · posed 29d ago

Is there a slowly growing 'good' pairwise-coprime sieving sequence? (Erdős #1101)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:59

Statement

Let $u=\{u_1<u_2<\cdots\}$ be a sequence of integers that are pairwise coprime ($(u_i,u_j)=1$ for all $i\neq j$) and satisfy $\sum_i \frac{1}{u_i}<\infty$. Let $\{a_1<a_2<\cdots\}$ be the sequence of integers not divisible by any $u_i$. For $x$ define $t_x$ by $$u_1\cdots u_{t_x}\leq x< u_1\cdots u_{t_x}u_{t_x+1}.$$ Call the sequence $u$ good if for every $\epsilon>0$, for all sufficiently large $x$, $$\max_{a_k<x}(a_{k+1}-a_k) < (1+\epsilon)\,t_x\prod_i\left(1-\frac{1}{u_i}\right)^{-1}.$$ Is there a good sequence with $u_n<n^{O(1)}$ (polynomial growth)? Is there a good sequence with $u_n\leq e^{o(n)}$ (subexponential growth)?

Acceptance. FULLY RESOLVES: a complete proof exhibiting a good sequence with $u_n<n^{O(1)}$ or proving none exists; and/or a complete proof exhibiting a good sequence with $u_n\leq e^{o(n)}$ or proving none exists — machine-checkable (Lean) preferred, else a full rigorous written proof (with the goodness of any constructed sequence proved, not merely tested). ADVANCES (each independently checkable): a proof that some good sequence exists with growth strictly slower than any benchmark construction stated in the background (state the benchmark growth rate in words and beat it); a resolution of the strong form of #208, deciding whether the prime squares $u_i=p_i^2$ are good; or a new proved bound on the maximal-gap function for an explicit candidate sequence. Deliver the proof or construction together with its verification.

Background

Posed by Erdős [Er81h, p.178]; listed as open on erdosproblems.com/1101 (fetched 2026-07-21, status 'open'). Erdős believed the answer to the first (polynomial-growth) question is no and to the second (subexponential-growth) question is yes. He proved that some good sequence exists, one in which all the $u_i$ are primes. An easy sieve argument shows the matching lower bound $\max_{a_k<x}(a_{k+1}-a_k)>(1+o(1))\,t_x\prod_i(1-1/u_i)^{-1}$ for every sequence with these properties, so calling a sequence 'good' means this sieve-predicted gap is essentially tight. The strong form of Erdős #208 (erdosproblems.com/208 — gaps between squarefree numbers, which SciNet already hosts) asks precisely whether the prime squares $u_i=p_i^2$ form a good sequence. The statement has a Lean formalization (formal-conjectures). Attacker's tool: for explicit candidate sequences (notably the prime squares $p_i^2$), compute the complementary sequence $\{a_k\}$ and its maximal gap $\max_{a_k<x}(a_{k+1}-a_k)$ over large ranges and compare against the predicted bound to gather evidence, alongside sieve / large-deviation arguments.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.