Erdős Problem #424

Erdős Problem 424 --- collection record

PROVENANCE AND STATUS

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

REUSED SOURCE 1

FORMAL RESTATEMENT Let $S_0=\{2,3\}\subset\mathbb N$. For $t\ge 0$, define \[ S_{t+1}:=S_t\cup\{ab-1: a,b\in S_t,\ a\ne b\}. \] Let $S:=\bigcup_{t\ge 0}S_t$ be the set of integers that eventually appear.

Question: does $S$ have positive (natural) density in $\mathbb N$; i.e. is it true that \[ \liminf_{x\to\infty}\frac{|S\cap[1,x]|}{x}>0\ ? \] (Equivalently, does $|S\cap[1,x]|\gg x$ as $x\to\infty$?)

Ambiguity note: the problem statement phrases a “sequence” obtained by appending all values $a_ia_j-1$. Since the question is about which integers appear “eventually”, the order and multiplicities are irrelevant; the definition above treats it as a closure process generating a set.

QUICK LITERATURE/CONTEXT CHECK The problem statement itself notes an obstruction mod $3$ (no integer $\equiv 1\pmod 3$ ever appears) and cites Guy’s book for discussion. No other external results are used here.

ATTACK PLAN Proof track ideas. 1) Identify modular and structural invariants (e.g. residue classes) to describe $S$. 2) Prove closure properties that generate large structured subsets (e.g. affine recurrences) and attempt to bootstrap to a positive-density subset.

Disproof track ideas. 1) Try to bound the growth of $|S\cap[1,x]|$ by showing that the operation $ab-1$ is too sparse to fill a positive proportion. 2) Search for further congruence obstructions that force density $0$.

WORK Fast reality check (finite closure in $[1,N]$). Because $ab-1\ge 3$ and is increasing in both arguments, any number $\le N$ that can be generated must be generated using only factors $\le N$. Thus iterating the closure rule while discarding values $>N$ produces the exact set $S\cap[1,N]$. A direct computation gives: \[ \begin{array}{c|c|c} N & |S\cap[1,N]| & |S\cap[1,N]|/N\\\hline 1000&250&0.25\\ 2000&530&0.265\\ 5000&1496&0.2992\\ 10000&3207&0.3207 \end{array} \] The first $30$ generated values in increasing order are \[ 2,3,5,9,14,17,26,27,33,41,44,50,51,53,65,69,77,80,81,84,87,98,99,101,105,122,125,129,131,134,\dots \]

Lemma 424.1 (mod $3$ obstruction). Every $s\in S$ satisfies $s\equiv 0$ or $2\pmod 3$. In particular, no integer $\equiv 1\pmod 3$ ever appears.

Proof. We prove by induction on $t$ that every element of $S_t$ is congruent to $0$ or $2$ modulo $3$. For $t=0$, $S_0=\{2,3\}$ and indeed $2\equiv 2\pmod 3$ and $3\equiv 0\pmod 3$. Assume the claim holds for $S_t$. Take any new element $x\in S_{t+1}\setminus S_t$. Then $x=ab-1$ for some distinct $a,b\in S_t$. By the induction hypothesis, $a,b\in\{0,2\}\pmod 3$. - If at least one of $a,b$ is $0\pmod 3$, then $ab\equiv 0\pmod 3$ and hence $x=ab-1\equiv -1\equiv 2\pmod 3$. - If $a\equiv b\equiv 2\pmod 3$, then $ab\equiv 4\equiv 1\pmod 3$ and hence $x=ab-1\equiv 0\pmod 3$. In both cases $x\equiv 0$ or $2\pmod 3$, so the claim holds for $S_{t+1}$. By induction it holds for all $t$, hence for $S=\bigcup_t S_t$. $\square$

Lemma 424.2 (closure under $x\mapsto 2x-1$ and an explicit infinite family). For every $x\in S$ we have $2x-1\in S$. In particular, for all integers $k\ge 0$, \[ 2^{k+1}+1\in S. \]

Proof. Let $x\in S$. Then $x\in S_t$ for some $t$. If $x\ne 2$, then $2\in S_0\subseteq S_t$ and $2\ne x$, so by the defining rule $2x-1\in S_{t+1}\subseteq S$. If $x=2$, then $2x-1=3\in S$ already. Thus $x\in S$ implies $2x-1\in S$.

Now define $x_0:=3\in S$ and $x_{k+1}:=2x_k-1$. By the closure just proved, $x_k\in S$ for all $k$. We solve the recurrence explicitly: we claim $x_k=2^{k+1}+1$. This holds for $k=0$. If it holds for $k$, then $x_{k+1}=2(2^{k+1}+1)-1=2^{k+2}+1$. So by induction, $2^{k+1}+1\in S$ for all $k\ge 0$. $\square$

Lemma 424.3 (closure under $x\mapsto 3x-1$ away from $x=3$ and a second explicit infinite family). For every $x\in S$ with $x\ne 3$ we have $3x-1\in S$. In particular, for all integers $k\ge 0$, \[ \frac{3^{k+1}+1}{2}\in S. \]

Proof. Let $x\in S$ with $x\ne 3$. Choose $t$ such that $x\in S_t$. Then $3\in S_0\subseteq S_t$ and $3\ne x$, so by the defining rule $3x-1\in S_{t+1}\subseteq S$.

Now define $y_0:=2$ and $y_{k+1}:=3y_k-1$ for $k\ge 0$. We have $y_0=2\in S$ and $y_0\ne 3$, hence $y_1=3\cdot 2-1=5\in S$. Also for every $k\ge 0$ we have $y_{k+1}=3y_k-1>y_k$ (since $y_k\ge 2$), so $(y_k)$ is strictly increasing and in particular $y_k\ne 3$ for all $k$. Therefore, applying the first paragraph with $x=y_k$ for each $k$, we get $y_{k+1}\in S$ whenever $y_k\in S$; hence by induction $y_k\in S$ for all $k\ge 0$.

We claim $y_k=(3^{k+1}+1)/2$ for all $k\ge 0$. For $k=0$, $y_0=2=(3^{1}+1)/2$. Assume $y_k=(3^{k+1}+1)/2$. Then \[ y_{k+1}=3y_k-1 = 3\cdot\frac{3^{k+1}+1}{2}-1=\frac{3^{k+2}+3-2}{2}=\frac{3^{k+2}+1}{2}. \] So the closed form holds for all $k$. $\square$

VERIFICATION - Lemma 424.1: the only residues used are $0$ and $2$ mod $3$, and the computation of $ab-1$ mod $3$ is checked case-by-case. - Lemma 424.2: the rule requires distinct inputs; the special case $x=2$ is handled separately. - Lemma 424.3: the same distinctness issue appears at $x=3$; the explicit family is produced starting from $2$ to avoid the forbidden pair $(3,3)$. - Computations: the “closure up to $N$” computation is exact for $S\cap[1,N]$ because $ab-1\le N$ forces $a,b\le N$.

FINAL UNRESOLVED (i) Strongest proved partial result: $S\subseteq\{n\in\mathbb N: n\not\equiv 1\pmod 3\}$ (Lemma 424.1), so the density of $S$ is at most $2/3$. Also $S$ contains explicit infinite families such as $\{2^{k+1}+1\}_{k\ge 0}$ and $\{(3^{k+1}+1)/2\}_{k\ge 0}$ (Lemmas 424.2–424.3). (ii) First gap (crisp): prove a lower bound $|S\cap[1,x]|\gg x$ (or refute it) as $x\to\infty$. (iii) Top 3 next moves: 1. Strengthen invariants: search systematically (by computation, then proof) for further modular obstructions beyond mod $3$. 2. Growth mechanism: prove that for many $x$, the set $S\cap[1,x]$ contains a large multiplicative structure that forces many new values $ab-1$ also $\le x$. 3. Large-$N$ exact closures: compute $|S\cap[1,N]|$ for much larger $N$ using optimised incremental methods to see whether the observed density $\approx 0.32$ keeps increasing and whether it plausibly converges. (iv) Minimal counterexample structure: if one conjectures positive density, a minimal counterexample would be a proof that $|S\cap[1,x]|=o(x)$; heuristically this would require that the operation $ab-1$ mostly “escapes” above $x$ and does not feed back into $[1,x]$ often enough. If one conjectures density $>0$, the minimal obstruction would likely be an additional congruence class (or a thin union of classes) avoiding closure under $ab-1$.

COMPLETION ESTIMATE

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

FORMAL RESTATEMENT Let $S_0=\{2,3\}\subset\mathbb N$. For $t\ge 0$, define \[ S_{t+1}:=S_t\cup\{ab-1: a,b\in S_t,\ a\ne b\}. \] Let $S:=\bigcup_{t\ge 0}S_t$ be the set of integers that eventually appear.

Question: does $S$ have positive (natural) density in $\mathbb N$; i.e. is it true that \[ \liminf_{x\to\infty}\frac{|S\cap[1,x]|}{x}>0\ ? \] (Equivalently, does $|S\cap[1,x]|\gg x$ as $x\to\infty$?)

Ambiguity note: the problem statement phrases a “sequence” obtained by appending all values $a_ia_j-1$. Since the question is about which integers appear “eventually”, the order and multiplicities are irrelevant; the definition above treats it as a closure process generating a set.

QUICK LITERATURE/CONTEXT CHECK The problem statement itself notes an obstruction mod $3$ (no integer $\equiv 1\pmod 3$ ever appears) and cites Guy’s book for discussion. No other external results are used here.

ATTACK PLAN Proof track ideas. 1) Identify modular and structural invariants (e.g. residue classes) to describe $S$. 2) Prove closure properties that generate large structured subsets (e.g. affine recurrences) and attempt to bootstrap to a positive-density subset.

Disproof track ideas. 1) Try to bound the growth of $|S\cap[1,x]|$ by showing that the operation $ab-1$ is too sparse to fill a positive proportion. 2) Search for further congruence obstructions that force density $0$.

WORK Fast reality check (finite closure in $[1,N]$). Because $ab-1\ge 3$ and is increasing in both arguments, any number $\le N$ that can be generated must be generated using only factors $\le N$. Thus iterating the closure rule while discarding values $>N$ produces the exact set $S\cap[1,N]$. A direct computation gives: \[ \begin{array}{c|c|c} N & |S\cap[1,N]| & |S\cap[1,N]|/N\\\hline 1000&250&0.25\\ 2000&530&0.265\\ 5000&1496&0.2992\\ 10000&3207&0.3207 \end{array} \] The first $30$ generated values in increasing order are \[ 2,3,5,9,14,17,26,27,33,41,44,50,51,53,65,69,77,80,81,84,87,98,99,101,105,122,125,129,131,134,\dots \]

Lemma 424.1 (mod $3$ obstruction). Every $s\in S$ satisfies $s\equiv 0$ or $2\pmod 3$. In particular, no integer $\equiv 1\pmod 3$ ever appears.

Proof. We prove by induction on $t$ that every element of $S_t$ is congruent to $0$ or $2$ modulo $3$. For $t=0$, $S_0=\{2,3\}$ and indeed $2\equiv 2\pmod 3$ and $3\equiv 0\pmod 3$. Assume the claim holds for $S_t$. Take any new element $x\in S_{t+1}\setminus S_t$. Then $x=ab-1$ for some distinct $a,b\in S_t$. By the induction hypothesis, $a,b\in\{0,2\}\pmod 3$. - If at least one of $a,b$ is $0\pmod 3$, then $ab\equiv 0\pmod 3$ and hence $x=ab-1\equiv -1\equiv 2\pmod 3$. - If $a\equiv b\equiv 2\pmod 3$, then $ab\equiv 4\equiv 1\pmod 3$ and hence $x=ab-1\equiv 0\pmod 3$. In both cases $x\equiv 0$ or $2\pmod 3$, so the claim holds for $S_{t+1}$. By induction it holds for all $t$, hence for $S=\bigcup_t S_t$. $\square$

Lemma 424.2 (closure under $x\mapsto 2x-1$ and an explicit infinite family). For every $x\in S$ we have $2x-1\in S$. In particular, for all integers $k\ge 0$, \[ 2^{k+1}+1\in S. \]

Proof. Let $x\in S$. Then $x\in S_t$ for some $t$. If $x\ne 2$, then $2\in S_0\subseteq S_t$ and $2\ne x$, so by the defining rule $2x-1\in S_{t+1}\subseteq S$. If $x=2$, then $2x-1=3\in S$ already. Thus $x\in S$ implies $2x-1\in S$.

Now define $x_0:=3\in S$ and $x_{k+1}:=2x_k-1$. By the closure just proved, $x_k\in S$ for all $k$. We solve the recurrence explicitly: we claim $x_k=2^{k+1}+1$. This holds for $k=0$. If it holds for $k$, then $x_{k+1}=2(2^{k+1}+1)-1=2^{k+2}+1$. So by induction, $2^{k+1}+1\in S$ for all $k\ge 0$. $\square$

Lemma 424.3 (closure under $x\mapsto 3x-1$ away from $x=3$ and a second explicit infinite family). For every $x\in S$ with $x\ne 3$ we have $3x-1\in S$. In particular, for all integers $k\ge 0$, \[ \frac{3^{k+1}+1}{2}\in S. \]

Proof. Let $x\in S$ with $x\ne 3$. Choose $t$ such that $x\in S_t$. Then $3\in S_0\subseteq S_t$ and $3\ne x$, so by the defining rule $3x-1\in S_{t+1}\subseteq S$.

Now define $y_0:=2$ and $y_{k+1}:=3y_k-1$ for $k\ge 0$. We have $y_0=2\in S$ and $y_0\ne 3$, hence $y_1=3\cdot 2-1=5\in S$. Also for every $k\ge 0$ we have $y_{k+1}=3y_k-1>y_k$ (since $y_k\ge 2$), so $(y_k)$ is strictly increasing and in particular $y_k\ne 3$ for all $k$. Therefore, applying the first paragraph with $x=y_k$ for each $k$, we get $y_{k+1}\in S$ whenever $y_k\in S$; hence by induction $y_k\in S$ for all $k\ge 0$.

We claim $y_k=(3^{k+1}+1)/2$ for all $k\ge 0$. For $k=0$, $y_0=2=(3^{1}+1)/2$. Assume $y_k=(3^{k+1}+1)/2$. Then \[ y_{k+1}=3y_k-1 = 3\cdot\frac{3^{k+1}+1}{2}-1=\frac{3^{k+2}+3-2}{2}=\frac{3^{k+2}+1}{2}. \] So the closed form holds for all $k$. $\square$

VERIFICATION - Lemma 424.1: the only residues used are $0$ and $2$ mod $3$, and the computation of $ab-1$ mod $3$ is checked case-by-case. - Lemma 424.2: the rule requires distinct inputs; the special case $x=2$ is handled separately. - Lemma 424.3: the same distinctness issue appears at $x=3$; the explicit family is produced starting from $2$ to avoid the forbidden pair $(3,3)$. - Computations: the “closure up to $N$” computation is exact for $S\cap[1,N]$ because $ab-1\le N$ forces $a,b\le N$.

FINAL UNRESOLVED (i) Strongest proved partial result: $S\subseteq\{n\in\mathbb N: n\not\equiv 1\pmod 3\}$ (Lemma 424.1), so the density of $S$ is at most $2/3$. Also $S$ contains explicit infinite families such as $\{2^{k+1}+1\}_{k\ge 0}$ and $\{(3^{k+1}+1)/2\}_{k\ge 0}$ (Lemmas 424.2–424.3). (ii) First gap (crisp): prove a lower bound $|S\cap[1,x]|\gg x$ (or refute it) as $x\to\infty$. (iii) Top 3 next moves: 1. Strengthen invariants: search systematically (by computation, then proof) for further modular obstructions beyond mod $3$. 2. Growth mechanism: prove that for many $x$, the set $S\cap[1,x]$ contains a large multiplicative structure that forces many new values $ab-1$ also $\le x$. 3. Large-$N$ exact closures: compute $|S\cap[1,N]|$ for much larger $N$ using optimised incremental methods to see whether the observed density $\approx 0.32$ keeps increasing and whether it plausibly converges. (iv) Minimal counterexample structure: if one conjectures positive density, a minimal counterexample would be a proof that $|S\cap[1,x]|=o(x)$; heuristically this would require that the operation $ab-1$ mostly “escapes” above $x$ and does not feed back into $[1,x]$ often enough. If one conjectures density $>0$, the minimal obstruction would likely be an additional congruence class (or a thin union of classes) avoiding closure under $ab-1$.