Even the case $k=3$ is non-trivial, but was proved by Bloom and Sisask [BlSi20]. Much better bounds for $r_3(N)$ were subsequently proved by Kelley and Meka [KeMe23]. Green and Tao [GrTa17] proved $r_4(N)\ll N/(\log N)^{c}$ for some small constant $c>0$. Gowers [Go01] proved \[r_k(N) \ll \frac{N}{(\log\log N)^{c_k}},\] where $c_k>0$ is a small constant depending on $k$. The current best bounds for general $k$ are due to Leng, Sah, and Sawhney [LSS24], who show that \[r_k(N) \ll \frac{N}{\exp((\log\log N)^{c_k})}\] for some constant $c_k>0$ depending on $k$.
Curiously, Erdős [Er83c] thought this conjecture was the 'only way to approach' the conjecture that there are arbitrarily long arithmetic progressions of prime numbers, now a theorem due to Green and Tao [GrTa08] (see [219]).
In [Er81] Erdős makes the stronger conjecture that \[r_k(N) \ll_C\frac{N}{(\log N)^C}\] for every $C>0$ (now known for $k=3$ due to Kelley and Meka [KeMe23]) - see [140].
Are there infinitely many practical $m$ such that \[h(m) < (\log\log m)^{O(1)}?\] Is it true that $h(n!)<n^{o(1)}$? Or perhaps even $h(n!)<(\log n)^{O(1)}$?
The sequence of practical numbers is A005153 in the OEIS.
This is true if $A$ is unbounded or dense in some interval. It therefore suffices to prove this when $A=\{a_1>a_2>\cdots\}$ is a countable strictly monotone sequence which converges to $0$.
Steinhaus [St20] has proved this is false whenever $A$ is a finite set.
This conjecture is known in many special cases (but, for example, it is is open when $A=\{1,1/2,1/4,\ldots\}$. For an overview of progress we recommend a nice survey by Svetic [Sv00] on this problem.
In [Er88c] Erdős notes that Cusick had a simple proof that there do exist infinitely many such $n$. Erdődoes not record what this was, but Kovač has provided the following proof: for every positive integer $m$ and $n=2^{m+1}-m-2$ we have \[\frac{n}{2^n}=\sum_{n<k\leq n+m}\frac{k}{2^k}.\]
The behaviour of $V(x)$ is now almost completely understood. Maier and Pomerance [MaPo88] proved \[V(x)=\frac{x}{\log x}e^{(C+o(1))(\log\log\log x)^2},\] for some explicit constant $C>0$. Ford [Fo98] improved this to \[V(x)\asymp\frac{x}{\log x}e^{C_1(\log\log\log x-\log\log\log\log x)^2+C_2\log\log\log x-C_3\log\log\log\log x}\] for some explicit constants $C_1,C_2,C_3>0$. Unfortunately this falls just short of an asymptotic formula for $V(x)$ and determining whether $V(2x)/V(x)\to 2$.
In [Er79e] Erdős asks further to estimate the number of $n\leq x$ such that the smallest solution to $\phi(m)=n$ satisfies $kx<m\leq (k+1)x$.
Erdős [Er73b] has shown that a positive density set of integers cannot be written as $\sigma(n)-n$.
This is true, as shown by Browkin and Schinzel [BrSc95], who show that any integer of the shape $2^{k}\cdot 509203$ is not of this form. It seems to be open whether there is a positive density set of integers not of this form.
Does, for every prime $p$, the density $\delta_p$ of integers with $h(n)=p$ exist? Does $\liminf h(n)=\infty$? Is it true that if $p$ is the greatest prime such that $p-1\mid n$ and $p>n^\epsilon$ then $h(n)=p$?
It is probably true that $h(n)=3$ for infinitely many $n$.
Is it true that $H(n)=3$ infinitely often? (That is, $(2^n-1,3^n-1)=1$ infinitely often?)
Estimate $H(n)$. Is it true that there exists some constant $c>0$ such that, for all $\epsilon>0$, \[H(n) > \exp(n^{(c-\epsilon)/\log\log n})\] for infinitely many $n$ and \[H(n) < \exp(n^{(c+\epsilon)/\log\log n})\] for all large enough $n$?
Does a similar upper bound hold for the smallest $k$ such that $(k^n-1,2^n-1)=1$?
This conjecture would follow if we knew that, for every $\epsilon>0$, there are $\gg_\epsilon \frac{x}{\log x}$ many primes $p<x$ such that all prime factors of $p-1$ are $<p^\epsilon$.
See also [416].
Is it true that $h(x)>x^{2-o(1)}$?
A similar question can be asked if we replace the condition $(a,b)=1$ with the condition that $a$ and $b$ are squarefree.
Erdős suggested that as $C\to \infty$ only divisors at most $\epsilon n$ need to be used, where $\epsilon \to 0$.
See also [18].
