/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
[Er70b] Erdős, P., Some applications of graph theory to number theory. Proc. Second Chapel
Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel
Hill, N.C., 1970) (1970), 136-145. PDF
[Po79] Pomerance, C., The prime number graph. Math. Comp. 33 (1979), 399-408.
PDF
$f(k,n)$ is the least $r$ such that every $A\subseteq{1,\ldots,n}$ with $|A|=k$ has a set
$S$ of $r$ primes with more than $r$ elements of $A$ divisible only by primes from $S$.
For $\pi(n)<k\leq n$ the value $r=\pi(n)$ is admissible (take all primes $\leq n$), so sInf is
a minimum. Outside this range f k n = 0 is a junk value: for $k\leq\pi(n)$ no $r$ is
admissible, and for $k>n$ every $r$ is.
Let $n\geq 2$ and $\pi(n)<k\leq n$. Let $f(k,n)$ be the smallest integer $r$ such that in any
$A\subseteq {1,\ldots,n}$ of size $\lvert A\rvert=k$ there exist primes $p_1,\ldots,p_r$ such
that $>r$ many $a\in A$ are only divisible by primes from ${p_1,\ldots,p_r}$.
Is it true that
$$2\pi(n^{1/2})-f(\pi(n)+1,n)\to \infty$$
as $n\to \infty$?
This is the first part. The primes may depend on $A$. Erdős and Straus conjectured this
[Er70b, p. 138 and p. 140].
The answer is no: Liam Price and GPT-5.5 Pro showed on the
forum that
$f(\pi(n)+1,n)=2\pi(n^{1/2})+1$ for infinitely many $n$; see the
explanation by Nat Sothanaphan.
Write $p_k$ for the $k$-th prime. By [Po79, Corollary after Theorem 2.2] there are infinitely
many $N$ with $p_{N-i}p_{N+i}<p_N^2$ for $1\leq i<N$. Take $n=p_N^2-1$, so
$\pi(n^{1/2})=N-1$. Let $A$ consist of the products of adjacent primes on the path
$p_{2N-1},p_1,p_{2N-2},p_2,\ldots,p_{N+1},p_{N-1},p_N$, its two endpoint primes, and the
other primes up to $n$. Then $\lvert A\rvert=\pi(n)+1$, and for any $r\leq 2N-2$ primes at
most $r$ elements of $A$ are divisible only by those primes, so $f(\pi(n)+1,n)\geq 2N-1$.
Let $n\geq 2$ and $\pi(n)<k\leq n$. Let $f(k,n)$ be the smallest integer $r$ such that in any
$A\subseteq {1,\ldots,n}$ of size $\lvert A\rvert=k$ there exist primes $p_1,\ldots,p_r$ such
that $>r$ many $a\in A$ are only divisible by primes from ${p_1,\ldots,p_r}$.
In general, estimate $f(k,n)$, particularly when $\pi(n)+1<k=o(n)$.
This is the second part. We read "estimate" as an asymptotic formula answer k n, valid for
every function $k=k(n)$ with $\pi(n)+1<k(n)=o(n)$.