Erdős Problem #983

Erdős Problem 983 --- 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/983.tex.

REUSED SOURCE 1

1) FORMAL RESTATEMENT

Let $n\ge 2$ and let $\pi(n)$ be the number of primes $\le n$. Fix an integer $k$ with $\pi(n)<k\le n$. For a subset $A\subseteq\{1,\dots,n\}$ of size $|A|=k$, consider the following property for a given integer $r\ge 1$: there exist distinct primes $p_1,\dots,p_r$ such that at least $r$ elements $a\in A$ have all their prime divisors contained in $\{p_1,\dots,p_r\}$. Define $f(k,n)$ to be the smallest integer $r$ such that this property holds for every $A\subseteq\{1,\dots,n\}$ with $|A|=k$.

Ambiguity note (literal vs corrected): - Literally, the condition "$a$ is only divisible by primes from $\{p_1,\dots,p_r\}$" is vacuously true for $a=1$ (since $1$ has no prime divisors). This makes very small-$n$ cases somewhat degenerate. - A minimal corrected variant sometimes used in number theory is to require the counted elements $a\in A$ to satisfy $a>1$. In the computations below, I report both conventions for small $n$.

The question asks whether \[ 2\pi(\sqrt n)-f(\pi(n)+1,n)\to\infty\quad\text{as }n\to\infty, \] and more generally to estimate $f(k,n)$ when $\pi(n)+1<k=o(n)$.

2) QUICK LITERATURE/CONTEXT CHECK

The provided statement includes asymptotics proved by Erdős and Straus for $f(\pi(n)+1,n)$ and for $f(cn,n)$. A quick web search $2026-01-16$ did not surface an explicit resolution of the limit question beyond what is in the problem statement.

3) ATTACK PLAN

Proof track: reinterpret the problem in terms of prime-support sets of elements of $A$ and search for extremal set-system configurations. Disproof track: attempt to construct sets $A$ of size $\pi(n)+1$ in which prime supports are spread out so that any set of $r$ primes can certify fewer than $r$ elements.

Here I provide two elementary equivalences and exact brute-force values for $f(\pi(n)+1,n)$ for $n\le 24$.

4) WORK

Definition. For $a\in\{1,\dots,n\}$, let $\operatorname{supp}(a)$ be the set of prime divisors of $a$.

Lemma 4.1 (equivalent "union of supports" formulation). Fix $A\subseteq\{1,\dots,n\}$. For a given $r\ge 1$, there exist primes $p_1,\dots,p_r$ such that at least $r$ elements of $A$ have all prime divisors in $\{p_1,\dots,p_r\}$ if and only if there exists a subset $B\subseteq A$ with $|B|=r$ such that \[ \left|\,\bigcup_{b\in B}\operatorname{supp}(b)\,\right|\le r. \]

Proof. ($\Rightarrow$) If $p_1,\dots,p_r$ certify at least $r$ elements, choose any $r$ certified elements and call them $B$. Every prime divisor of every $b\in B$ lies in $\{p_1,\dots,p_r\}$, hence $\bigcup_{b\in B}\operatorname{supp}(b)\subseteq\{p_1,\dots,p_r\}$ and so its size is $\le r$.

($\Leftarrow$) Conversely, suppose $B\subseteq A$ has $|B|=r$ and the union of supports has size $s\le r$. Let $Q$ be the set of primes in this union (so $|Q|=s$), and enlarge $Q$ arbitrarily by adding $r-s$ further distinct primes $\le n$ to obtain a set $P$ of exactly $r$ primes. Then every $b\in B$ has all prime divisors in $P$, so $P$ certifies at least $r$ elements. $\square$

Lemma 4.2 (characterization of the case $r=1$). For a set $A\subseteq\{1,\dots,n\}$, the property holds with $r=1$ if and only if $A$ contains a prime power (including $1$ under the literal convention). If one insists on counting only $a>1$, then $r=1$ holds if and only if $A$ contains $p^t$ for some prime $p$ and integer $t\ge 1$.

Proof. For $r=1$ we choose a single prime $p$ and ask for at least one $a\in A$ whose prime divisors all lie in $\{p\}$. This means either $a=1$ (empty support) or $a=p^t$ for some $t\ge 1$. Conversely, any such element is certified by choosing $p$ to be its prime base (or any $p$ if $a=1$). $\square$

FAST REALITY CHECK (exact values for $f(\pi(n)+1,n)$ for $n\le 24$)

Let $k=\pi(n)+1$. I computed $f(k,n)$ by brute force over all subsets $A\subseteq\{1,\dots,n\}$ of size $k$. I report both the literal convention (allowing $a=1$ to count) and the corrected convention (counting only $a>1$ among the certified elements).

\[ \begin{array}{c|c|c|c|c} n & \pi(n) & k=\pi(n)+1 & f(k,n)\ \text{(literal)} & f(k,n)\ \text{(count only }a>1)\\\hline 2&1&2&1&1\\ 3&2&3&1&1\\ 4&2&3&1&1\\ 5&3&4&1&1\\ 6&3&4&1&1\\ 7&4&5&1&1\\ 8&4&5&1&1\\ 9&4&5&1&1\\ 10&4&5&1&1\\ 11&5&6&1&1\\ 12&5&6&1&1\\ 13&6&7&1&1\\ 14&6&7&1&1\\ 15&6&7&1&1\\ 16&6&7&1&1\\ 17&7&8&1&1\\ 18&7&8&1&1\\ 19&8&9&1&1\\ 20&8&9&1&1\\ 21&8&9&1&2\\ 22&8&9&2&2\\ 23&9&10&1&2\\ 24&9&10&2&2 \end{array} \]

For example at $n=22$ (so $\pi(n)=8$ and $k=9$), the worst-case set (for the literal convention) is \[ A=\{6,10,12,14,15,18,20,21,22\}, \] for which $r=1$ fails (no prime powers in $A$), while $r=2$ works by choosing primes $\{2,3\}$ which certify $\{6,12,18\}$.

5) VERIFICATION

- Lemma 4.1 is a direct translation between "certifying primes" and "union of supports". - Lemma 4.2 follows by classifying the integers with prime support contained in a singleton. - The brute-force table is exact for the stated range $n\le 24$.

6) FINAL

UNRESOLVED (i) Strongest proved partial result: an equivalent formulation of the certification property in terms of subsets with small union of prime supports (Lemma 4.1) and a complete characterization of the case $r=1$ (Lemma 4.2). Exact values of $f(\pi(n)+1,n)$ for $n\le 24$ are given above under both conventions regarding whether $a=1$ counts. (ii) First gap (crisp): determine the asymptotic behavior of $f(\pi(n)+1,n)$ well enough to decide whether $2\pi(\sqrt n)-f(\pi(n)+1,n)\to\infty$. (iii) Top 3 next moves: 1. Using Lemma 4.1, model the multihypergraph of prime supports of elements of $A$ and search for extremal configurations maximizing the minimum $r$ for which an $r$-set of vertices contains $r$ hyperedges. 2. Construct explicit "bad" sets $A$ of size $\pi(n)+1$ that avoid prime powers and control overlaps of prime supports, to obtain lower bounds on $f(\pi(n)+1,n)$. 3. Computation: for moderate $n$ (beyond $24$), use heuristic/optimization search (rather than exhaustive search) to find candidate worst-case sets $A$ and estimate $f(\pi(n)+1,n)$ numerically. (iv) Minimal counterexample structure: for the limit question to be true, one would need that for large $n$ the worst-case $A$ forces $f(\pi(n)+1,n)$ to be noticeably smaller than $2\pi(\sqrt n)$; such an $A$ would have to concentrate many elements on a relatively small set of primes while simultaneously preventing the existence of an $r$-subset of $A$ whose prime supports collectively use only $r$ primes.

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.

1) FORMAL RESTATEMENT

Let $n\ge 2$ and let $\pi(n)$ be the number of primes $\le n$. Fix an integer $k$ with $\pi(n)<k\le n$. For a subset $A\subseteq\{1,\dots,n\}$ of size $|A|=k$, consider the following property for a given integer $r\ge 1$: there exist distinct primes $p_1,\dots,p_r$ such that at least $r$ elements $a\in A$ have all their prime divisors contained in $\{p_1,\dots,p_r\}$. Define $f(k,n)$ to be the smallest integer $r$ such that this property holds for every $A\subseteq\{1,\dots,n\}$ with $|A|=k$.

Ambiguity note (literal vs corrected): - Literally, the condition "$a$ is only divisible by primes from $\{p_1,\dots,p_r\}$" is vacuously true for $a=1$ (since $1$ has no prime divisors). This makes very small-$n$ cases somewhat degenerate. - A minimal corrected variant sometimes used in number theory is to require the counted elements $a\in A$ to satisfy $a>1$. In the computations below, I report both conventions for small $n$.

The question asks whether \[ 2\pi(\sqrt n)-f(\pi(n)+1,n)\to\infty\quad\text{as }n\to\infty, \] and more generally to estimate $f(k,n)$ when $\pi(n)+1<k=o(n)$.

2) QUICK LITERATURE/CONTEXT CHECK

The provided statement includes asymptotics proved by Erdős and Straus for $f(\pi(n)+1,n)$ and for $f(cn,n)$. A quick web search $2026-01-16$ did not surface an explicit resolution of the limit question beyond what is in the problem statement.

3) ATTACK PLAN

Proof track: reinterpret the problem in terms of prime-support sets of elements of $A$ and search for extremal set-system configurations. Disproof track: attempt to construct sets $A$ of size $\pi(n)+1$ in which prime supports are spread out so that any set of $r$ primes can certify fewer than $r$ elements.

Here I provide two elementary equivalences and exact brute-force values for $f(\pi(n)+1,n)$ for $n\le 24$.

4) WORK

Definition. For $a\in\{1,\dots,n\}$, let $\operatorname{supp}(a)$ be the set of prime divisors of $a$.

Lemma 4.1 (equivalent "union of supports" formulation). Fix $A\subseteq\{1,\dots,n\}$. For a given $r\ge 1$, there exist primes $p_1,\dots,p_r$ such that at least $r$ elements of $A$ have all prime divisors in $\{p_1,\dots,p_r\}$ if and only if there exists a subset $B\subseteq A$ with $|B|=r$ such that \[ \left|\,\bigcup_{b\in B}\operatorname{supp}(b)\,\right|\le r. \]

Proof. ($\Rightarrow$) If $p_1,\dots,p_r$ certify at least $r$ elements, choose any $r$ certified elements and call them $B$. Every prime divisor of every $b\in B$ lies in $\{p_1,\dots,p_r\}$, hence $\bigcup_{b\in B}\operatorname{supp}(b)\subseteq\{p_1,\dots,p_r\}$ and so its size is $\le r$.

($\Leftarrow$) Conversely, suppose $B\subseteq A$ has $|B|=r$ and the union of supports has size $s\le r$. Let $Q$ be the set of primes in this union (so $|Q|=s$), and enlarge $Q$ arbitrarily by adding $r-s$ further distinct primes $\le n$ to obtain a set $P$ of exactly $r$ primes. Then every $b\in B$ has all prime divisors in $P$, so $P$ certifies at least $r$ elements. $\square$

Lemma 4.2 (characterization of the case $r=1$). For a set $A\subseteq\{1,\dots,n\}$, the property holds with $r=1$ if and only if $A$ contains a prime power (including $1$ under the literal convention). If one insists on counting only $a>1$, then $r=1$ holds if and only if $A$ contains $p^t$ for some prime $p$ and integer $t\ge 1$.

Proof. For $r=1$ we choose a single prime $p$ and ask for at least one $a\in A$ whose prime divisors all lie in $\{p\}$. This means either $a=1$ (empty support) or $a=p^t$ for some $t\ge 1$. Conversely, any such element is certified by choosing $p$ to be its prime base (or any $p$ if $a=1$). $\square$

FAST REALITY CHECK (exact values for $f(\pi(n)+1,n)$ for $n\le 24$)

Let $k=\pi(n)+1$. I computed $f(k,n)$ by brute force over all subsets $A\subseteq\{1,\dots,n\}$ of size $k$. I report both the literal convention (allowing $a=1$ to count) and the corrected convention (counting only $a>1$ among the certified elements).

\[ \begin{array}{c|c|c|c|c} n & \pi(n) & k=\pi(n)+1 & f(k,n)\ \text{(literal)} & f(k,n)\ \text{(count only }a>1)\\\hline 2&1&2&1&1\\ 3&2&3&1&1\\ 4&2&3&1&1\\ 5&3&4&1&1\\ 6&3&4&1&1\\ 7&4&5&1&1\\ 8&4&5&1&1\\ 9&4&5&1&1\\ 10&4&5&1&1\\ 11&5&6&1&1\\ 12&5&6&1&1\\ 13&6&7&1&1\\ 14&6&7&1&1\\ 15&6&7&1&1\\ 16&6&7&1&1\\ 17&7&8&1&1\\ 18&7&8&1&1\\ 19&8&9&1&1\\ 20&8&9&1&1\\ 21&8&9&1&2\\ 22&8&9&2&2\\ 23&9&10&1&2\\ 24&9&10&2&2 \end{array} \]

For example at $n=22$ (so $\pi(n)=8$ and $k=9$), the worst-case set (for the literal convention) is \[ A=\{6,10,12,14,15,18,20,21,22\}, \] for which $r=1$ fails (no prime powers in $A$), while $r=2$ works by choosing primes $\{2,3\}$ which certify $\{6,12,18\}$.

5) VERIFICATION

- Lemma 4.1 is a direct translation between "certifying primes" and "union of supports". - Lemma 4.2 follows by classifying the integers with prime support contained in a singleton. - The brute-force table is exact for the stated range $n\le 24$.

6) FINAL

UNRESOLVED (i) Strongest proved partial result: an equivalent formulation of the certification property in terms of subsets with small union of prime supports (Lemma 4.1) and a complete characterization of the case $r=1$ (Lemma 4.2). Exact values of $f(\pi(n)+1,n)$ for $n\le 24$ are given above under both conventions regarding whether $a=1$ counts. (ii) First gap (crisp): determine the asymptotic behavior of $f(\pi(n)+1,n)$ well enough to decide whether $2\pi(\sqrt n)-f(\pi(n)+1,n)\to\infty$. (iii) Top 3 next moves: 1. Using Lemma 4.1, model the multihypergraph of prime supports of elements of $A$ and search for extremal configurations maximizing the minimum $r$ for which an $r$-set of vertices contains $r$ hyperedges. 2. Construct explicit "bad" sets $A$ of size $\pi(n)+1$ that avoid prime powers and control overlaps of prime supports, to obtain lower bounds on $f(\pi(n)+1,n)$. 3. Computation: for moderate $n$ (beyond $24$), use heuristic/optimization search (rather than exhaustive search) to find candidate worst-case sets $A$ and estimate $f(\pi(n)+1,n)$ numerically. (iv) Minimal counterexample structure: for the limit question to be true, one would need that for large $n$ the worst-case $A$ forces $f(\pi(n)+1,n)$ to be noticeably smaller than $2\pi(\sqrt n)$; such an $A$ would have to concentrate many elements on a relatively small set of primes while simultaneously preventing the existence of an $r$-subset of $A$ whose prime supports collectively use only $r$ primes.