SOLVED - $250

The density of integers which have two divisors $d_1,d_2$ such that $d_1<d_2<2d_1$ exists and is equal to $1$.

OPEN

Let $P(n)$ denote the largest prime factor of $n$. Show that the set of $n$ with $P(n+1)>P(n)$ has density $1/2$.

OPEN

Let $V(x)$ count the number of $n\leq x$ such that $\phi(m)=n$ is solvable. Does $V(2x)/V(x)\to 2$? Is there an asymptotic formula for $V(x)$?

Pillai [Pi29] proved $V(x)=o(x)$. Erdős [Er35b] proved $V(x)=x(\log x)^{-1+o(1)}$.

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$.

SOLVED

Let $\delta(n)$ denote the density of integers which are divisible by some integer in $(n,2n)$. What is the growth rate of $\delta(n)$?

If $\delta'(n)$ is the density of integers which have exactly one divisor in $(n,2n)$ then is it true that $\delta'(n)=o(\delta(n))$?

Besicovitch [Be34] proved that $\liminf \delta(n)=0$. Erdős [Er35] proved that $\delta(n)=o(1)$. Erdős [Er60] proved that $\delta(n)=(\log n)^{-\alpha+o(1)}$ where
\[\alpha=1-\frac{1+\log\log 2}{\log 2}=0.08607\cdots.\]
This estimate was refined by Tenenbaum [Te84], and the true growth rate of $\delta(n)$ was determined by Ford [Fo08] who proved
\[\delta(n)\asymp \frac{1}{(\log n)^\alpha(\log\log n)^{3/2}}.\]

Among many other results in [Fo08], Ford also proves that the second conjecture is false, and more generally that if $\delta_r(n)$ is the density of integers with exactly $r$ divisors in $(n,2n)$ then $\delta_r(n)\gg_r\delta(n)$.

SOLVED

Let $\tau(n)$ count the divisors of $n$ and $\tau^+(n)$ count the number of $k$ such that $n$ has a divisor in $[2^k,2^{k+1})$. Is it true that, for all $\epsilon>0$,
\[\tau^+(n) < \epsilon \tau(n)\]
for almost all $n$?

This is false, and was disproved by Erdős and Tenenbaum [ErTe81], who showed that in fact the upper density of the set of such $n$ is $\asymp \epsilon^{1-o(1)}$ (where the $o(1)$ in the exponent $\to 0$ as $\epsilon \to 0$).

A more precise result was proved by Hall and Tenenbaum [HaTe88] (see Section 4.6), who showed that the upper density is $\ll\epsilon \log(2/\epsilon)$. Hall and Tenenbaum further prove that $\tau^+(n)/\tau(n)$ has a distribution function.

Erdős and Graham also asked whether there is a good inequality known for $\sum_{n\leq x}\tau^+(n)$. This was provided by Ford [Fo08] who proved \[\sum_{n\leq x}\tau^+(n)\asymp x\frac{(\log x)^{1-\alpha}}{(\log\log x)^{3/2}}\] where \[\alpha=1-\frac{1+\log\log 2}{\log 2}=0.08607\cdots.\]

OPEN

Let $p_n$ be the smallest prime $\equiv 1\pmod{n}$ and let $m_n$ be the smallest integer such that $n\mid \phi(m_n)$. Is it true that $p_n>m_n$ for almost all $n$? Does $p_n/m_n\to \infty$ for almost all $n$? Are there infinitely many primes $p$ such that $p-1$ is the only $n$ for which $m_n=p$?

Linnik's theorem implies that $p_n\leq n^{O(1)}$. Erdős [Er79e] writes it is 'easy to show' that for infinitely many $n$ we have $p_n <m_n$.

SOLVED

Let $1=d_1<\cdots <d_{\tau(n)}=n$ be the divisors of $n$ and
\[G(n) = \sum_{1\leq i<\tau(n)}\frac{d_i}{d_{i+1}}.\]
Is it true that $G(n)\to \infty$ for almost all $n$? Can one prove an asymptotic formula for $\sum_{n\leq X}G(n)$?

Erdős writes it is 'easy' to prove $\frac{1}{X}\sum_{n\leq X}G(n)\to \infty$.

Terence Tao has observed that, for any divisor $m\mid n$, \[\frac{\tau(n/m)}{m} \leq G(n) \leq \tau(n),\] and hence for example $\tau(n)/4\leq G(n)\leq \tau(n)$ for even $n$. It is easy to then see that $G(n)$ grows on average, and in general behaves very similarly to $\tau(n)$ (and in particular the answer to the first question is yes). Tao suggests that this was a mistaken conjecture of Erdős, which he soon corrected a year later to [448].

OPEN

Let $d_k(p)$ be the density of those integers whose $k$th smallest prime factor is $p$ (i.e. if $p_1<p_2<\cdots$ are the primes dividing $n$ then $p_k=p$).

For fixed $k\geq 1$ is $d_k(p)$ unimodular in $p$? That is, it first increases in $p$ until its maximum then decreases.

Erdős believes that this is not possible, but could not disprove it. He could show that $p_k$ is about $e^{e^k}$ for almost all $n$, but the maximal value of $d_k(p)$ is assumed for much smaller values of $p$, at
\[p=e^{(1+o(1))k}.\]

A similar question can be asked if we consider the density of integers whose $k$th smallest divisor is $d$. Erdős could show that this function is not unimodular.

OPEN

Given $A\subseteq \mathbb{N}$ let $M_A=\{ n \geq 1 : a\mid n\textrm{ for some }a\in A\}$ be the set of multiples of $A$. Find a necessary and sufficient condition on $A$ for $M_A$ to have density $1$.

If $A$ is a set of prime numbers then a necessary and sufficient condition is that $\sum_{p\in A}\frac{1}{p}=\infty$.

The general situation is more complicated. For example suppose $A$ is the union of $(n_k,(1+\eta_k)n_k)\cap \mathbb{Z}$ where $1\leq n_1<n_2<\cdots$ is a lacunary sequence. If $\sum \eta_k<\infty$ then the density of $M_A$ exists and is $<1$. If $\eta_k=1/k$, so $\sum \eta_k=\infty$, then the density exists and is $<1$.

Erdős writes it 'seems certain' that there is some threshold $\alpha\in (0,1)$ such that, if $\eta_k=k^{-\beta}$, then the density of $M_A$ is $1$ if $\beta <\alpha$ and the density is $<1$ if $\beta >\alpha$.

OPEN

Let $\delta_1(n,m)$ be the density of the set of integers which exactly one divisor in $(n,m)$. Is $\delta_1(n,m)$ unimodular for $m>n+1$ (i.e. increases until some $m$ then decreases thereafter)? For fixed $n$, where does $\delta_1(n,m)$ achieve its maximum?

OPEN

Let $f_{\max}(n)$ be the largest $m$ such that $\phi(m)=n$, and $f_{\min}(n)$ be the smallest such $m$, where $\phi$ is Euler's totient function. Investigate
\[\max_{n\leq x}\frac{f_{\max}(n)}{f_{\min}(n)}.\]

Carmichael has asked whether there is an integer $n$ for which $\phi(m)=n$ has exactly one solution, that is, $\frac{f_{\max}(n)}{f_{\min}(n)}=1$. Erdős has proved that if such an $n$ exists then there must be infinitely many such $n$.

See also [51].

OPEN

Let $q_1<q_2<\cdots$ be a sequence of primes such that $q_{i+1}\equiv 1\pmod{q_i}$. Is it true that
\[\lim_k q_k^{1/k}=\infty?\]
Does there exist such a sequence with
\[q_k \leq \exp(k(\log k)^{1+o(1)})?\]

Linnik's theorem implies that there exists such a sequence of primes with
\[q_k \leq e^{e^{O(k)}}.\]

See also [696].

OPEN

Let $h(n)$ be the largest $\ell$ such that there is a sequence of primes $p_1<\cdots p_\ell$ all dividing $n$ with $p_{i+1}\equiv 1\pmod{p_i}$. Let $H(n)$ be the largest $u$ such that there is a sequence of integers $d_1<\cdots d_u$ all dividing $n$ with $d_{i+1}\equiv 1\pmod{d_i}$.

Estimate $h(n)$ and $H(n)$. Is it true that $H(n)/h(n)\to \infty$ for almost all $n$?

Erdős writes it is 'easy to see' that $h(n)\to \infty$ for almost all $n$, and believed he could show that the normal order of $h(n)$ is $\log_*(n)$ (the iterated logarithm).

See also [695].

OPEN

Let $\delta(m,\alpha)$ denote the density of the set of integers which are divisible by some $d\equiv 1\pmod{m}$ with $1<d<\exp(m^\alpha)$. Does there exist some $\beta\in (1,\infty)$ such that
\[\lim_{m\to \infty}\delta(m,\alpha)\]
is $0$ if $\alpha<\beta$ and $1$ if $\alpha>\beta$?

It is trivial that $\delta(m,\alpha)\to 0$ if $\alpha <1$, and Erdős could prove that the same is true for $\alpha=1$.

See also [696].