All Random Solved Random Open
5 solved out of 12 shown (show only solved or open)
SOLVED - $1000
Can the smallest modulus of a covering system be arbitrarily large?
Described by Erdős as 'perhaps my favourite problem'. Hough [Ho15], building on work of Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07], has shown the answer is no: the smallest modulus must be at most $10^{18}$.

An alternative, simpler, proof was given by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22], who improved the bound on the smallest modulus to $616000$.

SOLVED - $10000
For any $C>0$ are there infinitely many $n$ such that \[p_{n+1}-p_n> C\frac{\log\log n\log\log\log\log n}{(\log\log \log n)^2}\log n?\]
The peculiar quantitative form of Erdős' question was motivated by an old result of Rankin [Ra38], who proved there exists some constant $C>0$ such that the claim holds. Solved by Maynard [Ma16] and Ford, Green, Konyagin, and Tao [FGKT16]. The best bound available, due to all five authors [FGKMT18], is that there are infinitely many $n$ such that \[p_{n+1}-p_n\gg \frac{\log\log n\log\log\log\log n}{\log\log \log n}\log n.\] The likely truth is a lower bound like $\gg(\log n)^2$. In [Er97c] Erdős revised the value of this problem to \$5000 and reserved the \$10000 for a lower bound of $>(\log n)^{1+c}$ for some $c>0$.

See also [687].

Let $C\geq 0$. Is there an infinite sequence of $n_i$ such that \[\lim_{i\to \infty}\frac{p_{n_i+1}-p_{n_i}}{\log n_i}=C?\]
Let $S$ be the set of limit points of $(p_{n+1}-p_n)/\log n$. This problem asks whether $S=[0,\infty]$. Although this conjecture remains unproven, a lot is known about $S$. Some highlights:
  • $\infty\in S$ by Westzynthius' result [We31] on large prime gaps,
  • $0\in S$ by the work of Goldston, Pintz, and Yildirim [GPY09] on small prime gaps,
  • Erdős [Er55] and Ricci [Ri56] independently showed that $S$ has positive Lebesgue measure,
  • Hildebrand and Maier [HiMa88] showed that $S$ contains arbitrarily large (finite) numbers,
  • Pintz [Pi16] showed that there exists some small constant $c>0$ such that $[0,c]\subset S$,
  • Banks, Freiberg, and Maynard [BFM16] showed that at least $12.5\%$ of $[0,\infty)$ belongs to $S$,
  • Merikoski [Me20] showed that at least $1/3$ of $[0,\infty)$ belongs to $S$, and that $S$ has bounded gaps.
In [Er97c] Erdős asks whether $S$ is everywhere dense.
SOLVED - $100
Let $d_n=p_{n+1}-p_n$. Are there infinitely many $n$ such that $d_n<d_{n+1}<d_{n+2}$?
Conjectured by Erdős and Turán [ErTu48]. Shockingly Erdős offered \$25000 for a disproof of this, but as he comments, it 'is certainly true'.

Indeed, the answer is yes, as proved by Banks, Freiberg, and Turnage-Butterbaugh [BFT15] with an application of the Maynard-Tao machinery concerning bounded gaps between primes [Ma15]. They in fact prove that, for any $m\geq 1$, there are infinitely many $n$ such that \[d_n<d_{n+1}<\cdots <d_{n+m}\] and infinitely many $n$ such that \[d_n> d_{n+1}>\cdots >d_{n+m}.\]

Additional thanks to: Mehtaab Sawhney
Let $d_n=p_{n+1}-p_n$. The set of $n$ such that $d_{n+1}\geq d_n$ has density $1/2$, and similarly for $d_{n+1}\leq d_n$. Furthermore, there are infinitely many $n$ such that $d_{n+1}=d_n$.
SOLVED - $250
Let $n\geq 1$ and \[A=\{a_1<\cdots <a_{\phi(n)}\}=\{ 1\leq m<n : (m,n)=1\}.\] Is it true that \[ \sum_{1\leq k<\phi(n)}(a_{k+1}-a_k)^2 \ll \frac{n^2}{\phi(n)}?\]
The answer is yes, as proved by Montgomery and Vaughan [MoVa86], who in fact found the correct order of magnitude with the power $2$ replaced by any $\gamma\geq 1$ (which was also asked by Erdős in [Er73]).
Let $d_n=p_{n+1}-p_n$. Prove that \[\sum_{1\leq n\leq N}d_n^2 \ll N(\log N)^2.\]
Cramer proved an upper bound of $O(N(\log N)^4)$ conditional on the Riemann hypothesis. The prime number theorem immediately implies a lower bound of $\gg N(\log N)^2$.
For every $c\geq 0$ the density $f(c)$ of integers for which \[\frac{p_{n+1}-p_n}{\log n}< c\] exists and is a continuous function of $c$.
Let $N_k=2\cdot 3\cdots p_k$ and $\{a_1<a_2<\cdots <a_{\phi(N_k)}\}$ be the integers $<N_k$ which are relatively prime to $N_k$. Then, for any $c\geq 0$, the limit \[\frac{\#\{ a_i-a_{i-1}\leq c \frac{N_k}{\phi(N_k)} : 2\leq i\leq \phi(N_k)\}}{\phi(N_k)}\] exists and is a continuous function of $c$.
Let $f(n)$ count the number of solutions to $n=p+2^k$ for prime $p$ and $k\geq 0$. Is it true that $f(n)=o(\log n)$?
Erdős [Er50] proved that there are infinitely many $n$ such that $f(n)\gg \log\log n$. Erdős could not even prove that there do not exist infinitely many integers $n$ such that for all $2^k<n$ the number $n-2^k$ is prime (probably $n=105$ is the largest such integer).

See also [237].

Let $A\subseteq \mathbb{N}$ be a set such that $\lvert A\cap \{1,\ldots,N\}\rvert \gg \log N$ for all large $N$. Let $f(n)$ count the number of solutions to $n=p+a$ for $p$ prime and $a\in A$. Is it true that $\limsup f(n)=\infty$?
Erdős [Er50] proved this when $A=\{2^k : k\geq 0\}$. Solved by Chen and Ding [ChDi22].

See also [236].

Let $c_1,c_2>0$. Is it true that, for any sufficiently large $x$, there exist more than $c_1\log x$ many consecutive primes $\leq x$ such that the difference between any two is $>c_2$?
This is well-known if $c_1$ is sufficiently small.