Reused writeup on Math-974 (gpt pro 5.2)

Erdős Problem 892 --- collection record

PROVENANCE AND STATUS

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

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/892.tex.

REUSED SOURCE 1

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

1) FORMAL RESTATEMENT

Let $(b_n)_{n\ge 1}$ be a strictly increasing sequence of positive integers. We ask for conditions on $(b_n)$ that guarantee the existence of a strictly increasing primitive sequence $(a_n)_{n\ge 1}$ of integers with

\[ a_n \le C\, b_n \quad \text{for all } n\ge 1 \]

for some absolute constant $C\ge 1$ (depending on $b_\bullet$ but not on $n$). Here primitive means: for all $i<j$, $a_i\nmid a_j$.

The problem also asks, in particular, whether such an $(a_n)$ always exists under an additional hypothesis on $(b_n)$:

(*) There are no non-trivial solutions to $(b_i,b_j)=b_k$.

Ambiguity. Since $b_i<b_j$ implies $(b_i,b_j)\le b_i$, any equality $(b_i,b_j)=b_k$ forces $k\le i$. Thus the only “trivial” equalities that can occur with $i<j$ are $(b_i,b_j)=b_i$ (equivalently $b_i\mid b_j$), with $k=i$. A natural minimal interpretation of (*) is therefore:

\[ \forall\, i<j,\; (b_i,b_j)\notin\{b_1,\dots,b_{i-1}\}. \]

I will keep this interpretation; all statements below that mention (*) will explicitly use only this meaning.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement (input file) records two known necessary conditions on $b_n$: $\sum_n 1/(b_n\log b_n)<\infty$ (attributed there to Erdős $1935$) and $\sum_{b_n<x}1/b_n = o(\log x/\sqrt{\log\log x})$ (attributed there to Erdős--Sárközy--Szemerédi $1967$). No sufficient condition is given there, and the existence of a necessary and sufficient condition is the open question.

3) ATTACK PLAN

Proof track (partial results):

• Derive clean necessary conditions on $(b_n)$ from the existence of a primitive $(a_n)$ with $a_n\le Cb_n$.
• Give at least one transparent sufficient condition on $(b_n)$ that allows an explicit construction of a primitive $(a_n)$ with $a_n\le Cb_n$.

Disproof/construction track:

• Test the “in particular” hypothesis (*) on toy sequences: does it prevent obvious obstructions (e.g. forcing $b_n$ to grow too slowly)?
• Search small prefixes computationally for feasibility of a primitive approximation under fixed $C$.

4) WORK

PHASE 1 — FAST REALITY CHECK (small prefixes).

I ran a small backtracking search for finite prefixes $b_1,\dots,b_m$ asking whether there exist strictly increasing integers $a_1<\dots<a_m$ with $a_i\le C b_i$ and $a_i\nmid a_j$ for all $i<j$.

• For $b_n=n$ and $C=2$, solutions exist for $m\le 4$ (e.g. $[2,3,5,7]$) but no solution exists for $m=5$.
• For $b_n=n$ and $C=3$, solutions exist up to $m=10$; one solution is the prime list $[2,3,5,7,11,13,17,19,23,29]$.
• For $b_n=2^n$ and $C=1$, solutions exist (again via primes) at least up to $m=12$.

These are only sanity checks on prefixes; they do not decide the infinite question.

Problem-specific lemmas towards the classical necessary condition $\sum 1/(b_n\log b_n)<\infty$.

The next two lemmas are purely about primitive sets and are the key combinatorial input in Erdős’ 1935 argument bounding $\sum_{a\in A} 1/(a\log a)$ for a primitive set $A$.

Lemma 892.1 (Disjointness of Erdős L-sets). Let $a>1$ be an integer and write $P(a)$ for the largest prime factor of $a$. Define \[ L_a := \{ a\,m : m\in\mathbb{N},\ \text{every prime }p\mid m \text{ satisfies } p>P(a)\}. \] If $A$ is a primitive set of integers $>1$, then the sets $(L_a)_{a\in A}$ are pairwise disjoint.

Proof. Assume for contradiction that $x\in L_a\cap L_{a'}$ for distinct $a,a'\in A$. Then there exist $m,m'\in\mathbb{N}$ such that \[ x = a m = a' m', \] with every prime divisor of $m$ strictly larger than $P(a)$ and every prime divisor of $m'$ strictly larger than $P(a')$.

Let $p:=P(a)$ and $q:=P(a')$. Without loss of generality assume $p\le q$. Since $p\mid a$ and every prime divisor of $m$ is $>p$, the exact exponent of $p$ in the prime factorization of $x$ equals the exponent of $p$ in $a$. Similarly, since $p\le q$ and every prime divisor of $m'$ is $>q\ge p$, the prime $p$ cannot divide $m'$, so the exponent of $p$ in $x$ equals the exponent of $p$ in $a'$. Hence $v_p(a)=v_p(a')$.

Now let $r$ be any prime $\le p$. Because every prime divisor of $m$ is $>p\ge r$, the exponent of $r$ in $x$ equals $v_r(a)$. Likewise, every prime divisor of $m'$ is $>q\ge p\ge r$, so the exponent of $r$ in $x$ equals $v_r(a')$. Hence $v_r(a)=v_r(a')$ for every prime $r\le p$.

But all prime factors of $a$ are $\le p$ by definition of $p=P(a)$. Therefore $a$ is exactly the product of $r^{v_r(a)}$ over primes $r\le p$, and the same exponents occur in $a'$. It follows that $a\mid a'$. Since $A$ is primitive and $a\ne a'$, this is impossible. Thus $L_a\cap L_{a'}=\emptyset$. $\square$

Lemma 892.2 (Density of $L_a$). With $L_a$ as above, the natural density $d(L_a)$ exists and equals \[ d(L_a)=\frac{1}{a}\prod_{p\le P(a)}\left(1-\frac{1}{p}\right). \]

Proof. Let $p_0:=P(a)$ and let $S:=\{p\ \text{prime}: p\le p_0\}$. Define the set of $p_0$-rough integers \[ R_{p_0}:=\{m\in\mathbb{N}: \forall p\in S,\ p\nmid m\}. \] By inclusion--exclusion over the finite set $S$, the natural density of $R_{p_0}$ exists and equals \[ d(R_{p_0})=\prod_{p\in S}\left(1-\frac{1}{p}\right). \] (Indeed, for any finite set of primes $S$, the density of integers divisible by a fixed squarefree modulus $d=\prod_{p\in T}p$ is $1/d$, and inclusion--exclusion computes the density of those divisible by none of the primes in $S$.)

Now $L_a = a\,R_{p_0}$ is the image of $R_{p_0}$ under multiplication by $a$. Scaling by $a$ multiplies natural densities by $1/a$: \[ d(L_a)=d(aR_{p_0})=\lim_{x\to\infty}\frac{|\{m\le x/a: m\in R_{p_0}\}|}{x} =\frac{1}{a} d(R_{p_0}). \] Substituting the expression for $d(R_{p_0})$ gives the stated formula. $\square$

Proposition 892.3 (Erdős’ convergence mechanism; conditional on Mertens). Let $A$ be a primitive set of integers $>1$. Then \[ \sum_{a\in A} \frac{1}{a\log a}<\infty. \]

Proof. By Lemma 892.1 the sets $\{L_a\}_{a\in A}$ are disjoint, so \[ \sum_{a\in A} d(L_a) \le 1. \] By Lemma 892.2, \[ \sum_{a\in A} \frac{1}{a}\prod_{p\le P(a)}\left(1-\frac{1}{p}\right) \le 1. \] A classical analytic estimate (Mertens’ product theorem) asserts that $\prod_{p\le y}(1-1/p) \asymp 1/\log y$ as $y\to\infty$. In particular, there is an absolute constant $c>0$ and a threshold $y_0$ such that for all $y\ge y_0$, \[ \prod_{p\le y}\left(1-\frac{1}{p}\right) \ge \frac{c}{\log y}. \] Applying this with $y=P(a)$ for all sufficiently large $a\in A$ gives \[ \sum_{a\in A,\ a\ \text{large}} \frac{c}{a\log P(a)} \le 1. \] Since $P(a)\le a$ we have $\log P(a)\le \log a$ and hence $1/(a\log a)\le 1/(a\log P(a))$ for $a>1$. Therefore the tail $\sum_{a\in A,\ a\ \text{large}} 1/(a\log a)$ is bounded by $(1/c)$, and adding finitely many initial terms shows the full series converges. $\square$

Proposition 892.4 (Necessary condition on $b_n$ from existence of $a_n$). Assume there exist $C\ge 1$ and a primitive increasing sequence $(a_n)$ such that $a_n\le C b_n$ for all $n$. Then \[ \sum_{n\ge 1} \frac{1}{b_n\log b_n} <\infty. \]

Proof. Fix $C$ and let $n$ be large enough that $a_n\ge C^2e$. Then $b_n\ge a_n/C\ge Ce$ and \[ \log b_n \ge \log(a_n/C)=\log a_n -\log C \ge \tfrac12\log a_n. \] Thus for all such $n$, \[ \frac{1}{b_n\log b_n} \le \frac{C}{a_n}\cdot\frac{2}{\log a_n} = \frac{2C}{a_n\log a_n}. \] By Proposition 892.3 the series $\sum_n 1/(a_n\log a_n)$ converges, hence so does the tail $\sum_{n\ge n_0} 1/(b_n\log b_n)$. Adding finitely many initial terms finishes. $\square$

A transparent sufficient condition (one explicit construction).

Proposition 892.5 (Doubling-growth suffices). Assume $b_1\ge 2$ and $b_{n}\ge 2b_{n-1}$ for all $n\ge 2$. Then there exists a primitive increasing sequence $(a_n)$ with $a_n\le b_n$ for all $n$.

Proof. We will choose $a_n$ to be primes, one from each interval $(b_{n-1},b_n]$. Since $b_n\ge 2b_{n-1}$, the interval $(b_{n-1},b_n]$ contains the sub-interval $(b_{n-1},2b_{n-1}]$. By Bertrand’s postulate, for every integer $x\ge 2$ there is a prime in $(x,2x]$. Applying this with $x=b_{n-1}$ yields a prime $a_n\in(b_{n-1},2b_{n-1}]$. In particular $a_n\le 2b_{n-1}\le b_n$, and $a_n>b_{n-1}\ge a_{n-1}$, so the sequence is strictly increasing. Distinct primes never divide each other, so $(a_n)$ is primitive. $\square$

5) VERIFICATION

• Lemma 892.1: the only subtle point is handling the largest prime factor $p=P(a)$ when comparing factorizations in $x=am=a'm'$. This is why $L_a$ was defined using primes strictly larger than $P(a)$; then primes $\le P(a)$ come only from $a$, making the divisibility conclusion $a\mid a'$ robust.
• Lemma 892.2: inclusion--exclusion is exact since only finitely many primes $\le P(a)$ are involved.
• Proposition 892.3: the only external input is the lower bound in Mertens’ product theorem. All other steps are explicit. The comparison $\log P(a)\le \log a$ is correct.
• Proposition 892.4: the comparison of logs uses $\log a_n -\log C\ge \tfrac12\log a_n$ for $a_n\ge C^2$, which is correct.
• Proposition 892.5: depends on Bertrand’s postulate; the rest is immediate.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. If such a primitive $(a_n)$ with $a_n\le Cb_n$ exists, then necessarily $\sum_n 1/(b_n\log b_n)<\infty$ (Proposition 892.4). Also, a simple sufficient condition is doubling growth $b_n\ge 2b_{n-1}$, which guarantees a construction with $a_n\le b_n$ (Proposition 892.5).

(ii) First gap (crisp). Give a necessary and sufficient condition on an arbitrary increasing integer sequence $(b_n)$ that is equivalent to the existence of a primitive $(a_n)$ with $a_n\le Cb_n$ for all $n$. In particular, decide whether hypothesis (*) alone implies existence.

(iii) Top 3 next moves.

1. Prove (or disprove) that the two known necessary conditions listed in the problem statement (the $\sum 1/(b_n\log b_n)$ condition and the upper-log-density condition) are jointly sufficient.
2. Try to construct a counterexample sequence $(b_n)$ satisfying (*) but violating any plausible sufficient condition by forcing many divisibility constraints on any nearby $a_n$.
3. Computationally: for candidate $b_n$ with (*) and modest growth, attempt SAT/backtracking search for longer prefixes and look for structural obstructions (e.g. forced divisibility chains among all $a\le Cb_n$).

(iv) Minimal counterexample structure (if false). A minimal counterexample to “(*) implies existence” would likely have relatively slow growth (to make primitivity hard) while being arranged so that gcds of pairs avoid earlier terms. One expects many shared small prime factors across $b_n$ (creating divisibility pressure) but arranged so that each common gcd is not itself among the earlier $b_k$.

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.