Reused writeup on Math-6155 (gpt pro 5.2)

Erdős Problem 1101 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/1101

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/1101.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/1101.tex.

FORMAL RESTATEMENT. Let $u=\{u_1<u_2<\cdots\}$ be a strictly increasing sequence of integers with $u_i\ge 2$ such that

• $\gcd(u_i,u_j)=1$ for all $i\ne j$,
• $\sum_{i=1}^{\infty}\frac{1}{u_i}<\infty$.

Let $A\subset\mathbb N$ be the set of positive integers not divisible by any $u_i$, and write it in increasing order as $A=\{a_1<a_2<\cdots\}$. For each real $x\ge 1$ define $t_x\in\mathbb N\cup\{0\}$ by \[ U_{t_x}:=\prod_{i=1}^{t_x}u_i\le x < \prod_{i=1}^{t_x+1}u_i=U_{t_x}u_{t_x+1}, \] (with the convention $U_0=1$). Write \[\delta:=\prod_{i=1}^{\infty}\left(1-\frac{1}{u_i}\right)\in(0,1],\qquad C:=\delta^{-1}. \] Call $u$ good if for every $\varepsilon>0$ there exists $X_0(\varepsilon)$ such that for all $x\ge X_0(\varepsilon)$, \[ \max_{a_k<x}(a_{k+1}-a_k) < (1+\varepsilon)\,t_x\,C. \] Question: does there exist a good sequence $u$ with $u_n<n^{O(1)}$? does there exist a good sequence with $u_n\le e^{o(n)}$?

QUICK LITERATURE/CONTEXT CHECK (from the problem file only). The problem text states: (i) Erdős proved existence of some good sequence with all $u_i$ prime. (ii) Erdős believed: no good sequence with $u_n<n^{O(1)}$, but yes with $u_n\le e^{o(n)}$. (iii) "An easy sieve argument" gives, for any such $u$, the lower bound \[ \max_{a_k<x}(a_{k+1}-a_k)>(1+o(1))\,t_x\,C. \] (iv) A strong form asks whether $u_i=p_i^2$ (prime squares) is good. I do not use any external literature beyond these statements.

ATTACK PLAN.

• (Structure) Prove exact periodic counting for the finite-prefix sieve by $u_1,\dots,u_m$ and deduce existence of density $\delta$ for $A$.
• (Disproof track) Try to build long gaps (intervals with no elements of $A$) via CRT congruences; compare their length to the conjectured scale $t_xC$.
• (Reality check) For the concrete sequence $u_i=p_i^2$, compute the maximal gap between squarefree numbers up to moderate $x$ and compare to $t_xC$.

WORK.

Lemma 1 (exact finite-prefix count and periodicity). Fix $m\ge 1$ and set $U_m:=\prod_{i=1}^m u_i$ and \[A^{(m)}:=\{n\in\mathbb N: u_i\nmid n\ \text{for all }1\le i\le m\}. \] Then for every integer $q\ge 0$ and $0\le r\le U_m$ we have \[ |A^{(m)}\cap[1,qU_m+r]| = q\,U_m\prod_{i=1}^m\left(1-\frac{1}{u_i}\right) + |A^{(m)}\cap[1,r]|. \] In particular the natural density of $A^{(m)}$ exists and equals \[\delta_m:=\prod_{i=1}^m\left(1-\frac{1}{u_i}\right),\qquad\text{i.e. }\frac{|A^{(m)}\cap[1,X]|}{X}=\delta_m+O\!\left(\frac{U_m}{X}\right). \]

Proof. Membership of $n$ in $A^{(m)}$ depends only on $n\bmod U_m$ because each condition $u_i\nmid n$ depends only on $n\bmod u_i$, and $u_i\mid U_m$. Thus the pattern of membership repeats with period $U_m$. So to prove the first displayed identity it suffices to count the number of allowed residues in one full period $[1,U_m]$.

For each $i\le m$, among the $U_m$ residues modulo $U_m$ there are exactly $U_m/u_i$ residues divisible by $u_i$. Because the $u_i$ are pairwise coprime, for any subset $S\subseteq\{1,\dots,m\}$ the number of residues divisible by all $u_i$ with $i\in S$ is \[\frac{U_m}{\prod_{i\in S}u_i}, \] since the divisibility condition is equivalently divisibility by $\prod_{i\in S}u_i$. By inclusion--exclusion, the number of residues divisible by none of $u_1,\dots,u_m$ is \[ U_m\sum_{S\subseteq[m]}(-1)^{|S|}\frac{1}{\prod_{i\in S}u_i}=U_m\prod_{i=1}^m\left(1-\frac{1}{u_i}\right)=U_m\delta_m. \] Therefore in each full block of length $U_m$ exactly $U_m\delta_m$ integers lie in $A^{(m)}$, which gives the claimed periodic counting formula and the density statement. $\square$

Lemma 2 (existence and value of the density of $A$). The set $A$ has a natural density and \[\lim_{X\to\infty}\frac{|A\cap[1,X]|}{X}=\delta:=\prod_{i=1}^{\infty}\left(1-\frac{1}{u_i}\right)\in(0,1). \]

Proof. First, because $\sum_i \frac1{u_i}<\infty$, we have $\sum_i \frac1{u_i^2}<\infty$ as well. Using the Taylor bound $\log(1-x)=-x+O(x^2)$ for $0<x\le 1/2$ and the fact that $1/u_i\to 0$, the series \[\sum_{i=1}^{\infty}\log\left(1-\frac1{u_i}\right) \] converges, hence $\delta_m\to\delta\in(0,1)$.

Now fix $m\ge 1$. We have $A\subseteq A^{(m)}$. If $n\in A^{(m)}\setminus A$, then $n$ is divisible by some $u_i$ with $i>m$. Hence for every $X\ge 1$, \[ |A^{(m)}\cap[1,X]|-|A\cap[1,X]|\le \sum_{i>m}\lfloor\frac{X}{u_i}\rfloor\le X\sum_{i>m}\frac1{u_i}. \] Divide by $X$ and let $X\to\infty$. By Lemma 1, $|A^{(m)}\cap[1,X]|/X\to\delta_m$, so \[ 0\le \delta_m-\limsup_{X\to\infty}\frac{|A\cap[1,X]|}{X} \le \sum_{i>m}\frac1{u_i}. \] Letting $m\to\infty$ forces the right-hand side to $0$ and $\delta_m\to\delta$, so \[\limsup_{X\to\infty}\frac{|A\cap[1,X]|}{X}\ge \delta. \] On the other hand, since $A\subseteq A^{(m)}$, \[\liminf_{X\to\infty}\frac{|A\cap[1,X]|}{X}\le \delta_m\quad\text{for every }m, \] so letting $m\to\infty$ gives $\liminf\le \delta$. Combining yields $\liminf=\limsup=\delta$, i.e. the density exists and equals $\delta$. $\square$

Lemma 3 (CRT gap of length $m$). For every $m\ge 1$ there exists an integer $N\ge 0$ such that \[u_i\mid (N+i)\qquad\text{for all }1\le i\le m. \] Consequently, the interval $\{N+1,\dots,N+m\}$ contains no element of $A$, so for any $x\ge N+m$ one has \[\max_{a_k<x}(a_{k+1}-a_k)\ge m. \]

Proof. Consider the congruences $N\equiv -i\pmod{u_i}$ for $i=1,\dots,m$. Because the moduli $u_i$ are pairwise coprime, the Chinese remainder theorem guarantees a simultaneous solution modulo $U_m=\prod_{i=1}^m u_i$. Choose $N\in\{0,1,\dots,U_m-1\}$ satisfying these congruences. Then $u_i\mid(N+i)$ for all $i\le m$. Thus each integer in $\{N+1,\dots,N+m\}$ is divisible by at least one $u_i$, so none belongs to $A$. If $x\ge N+m$, then among the increasing sequence $a_k$ there is some $a_{k}\le N$ and the next element $a_{k+1}\ge N+m+1$, implying $a_{k+1}-a_k\ge m+1\ge m$. $\square$

FAST REALITY CHECK (prime squares $u_i=p_i^2$). For $u_i=p_i^2$, the set $A$ is exactly the squarefree positive integers and $\delta=\prod_p(1-1/p^2)=6/\pi^2$, so $C=\pi^2/6\approx 1.644934$. I computed by a direct sieve the maximum gap between consecutive squarefree numbers up to $x$ for several $x$. For each $x$ I also computed $t_x$ from $(p_1\cdots p_{t_x})^2\le x < (p_1\cdots p_{t_x}p_{t_x+1})^2$. The results were: \[ \begin{array}{c|c|c|c} x & t_x & \max_{a_k\le x}(a_{k+1}-a_k) & \text{ratio }\frac{\max\text{ gap}}{t_x C}\\\hline 10^4 & 3 & 6 & 1.215854\dots\\ 10^5 & 4 & 7 & 1.063872\dots\\ 10^6 & 4 & 8 & 1.215854\dots\\ 10^7 & 5 & 10 & 1.215854\dots \end{array} \] (In each case the maximising gap occurred at the specific interval reported by the script; e.g. for $x=10^7$ the gap $10$ occurred between $8870023$ and $8870033$.) These computations are only a sanity check at small $x$ and do not resolve goodness.

VERIFICATION.

• Lemma 1: checked that inclusion--exclusion is valid because the $u_i$ are pairwise coprime, so intersections correspond to divisibility by the product.
• Lemma 2: the only place convergence is used is (a) to ensure $\delta_m$ converges to a positive limit, and (b) to make the tail bound $\sum_{i>m}1/u_i$ small.
• Lemma 3: CRT applies to the finite set of congruences; no hidden assumptions.
• For the computation: for $u_i=p_i^2$ the identification of $A$ with squarefree integers is correct because an integer is squarefree iff it is not divisible by $p^2$ for any prime $p$.

FINAL: UNRESOLVED. (i) Strongest proved partial result here. The set $A$ has positive density $\delta=\prod_i(1-1/u_i)$ (Lemma 2), and for each $m$ there exist gaps of length at least $m$ in $A$ produced by CRT (Lemma 3).

(ii) First gap (crisp). For any explicit growth regime on $u_n$ (e.g. $u_n<n^{O(1)}$ or $u_n\le e^{o(n)}$), I do not have a proof or disproof of the upper bound \[\max_{a_k<x}(a_{k+1}-a_k) < (1+\varepsilon)\,t_x\,\delta^{-1}\] for all sufficiently large $x$.

(iii) Top 3 next moves. 1. For the candidate $u_i=p_i^2$, attempt to bound maximal runs of non-squarefree numbers in terms of $t_x$ by constructing explicit coverings of intervals using many prime squares beyond the first $t_x$. 2. Try to prove (or disprove) that the extremal gap is achieved (up to $1+o(1)$ factors) by a CRT-type construction using the first $t_x$ moduli; this would convert goodness to an optimization problem over residue choices. 3. For sequences with $u_n\le e^{o(n)}$, model the sieve process as a random covering and attempt to prove a high-probability upper bound for the maximal uncovered gap using dependence estimates specific to coprime moduli.

(iv) Minimal counterexample structure. A counterexample to "$u$ is good" would be a sequence $u$ with the stated hypotheses for which there exist arbitrarily large $x$ admitting an interval $[y,y+L]$ of length $L\gg t_x\,\delta^{-1}$ completely covered by the residue classes $0\bmod u_i$; equivalently, a highly non-random alignment of many moduli producing unusually long consecutive runs of excluded integers.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.