Logo
All Random Solved Random Open
3 solved out of 16 shown (show only solved or open)
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$.
In [Er79] asks the stronger version with $2$ replaced by any constant $c>1$.

The answer is yes (also to this stronger version), proved by Maier and Tenenbaum [MaTe84]. (Tenenbaum has told me that they received \$650 for their solution.)

See also [449].

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$.
Conjectured by Erdős and Pomerance [ErPo78], who proved that this set and its complement both have positive upper density.

In [Er79e] Erdős also asks whether, for every $\alpha>0$, the density of the set of $n$ where \[P(n+1)>P(n)n^\alpha\] exists.

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

See also [417].

Additional thanks to: Kevin Ford
OPEN
Let \[V'(x)=\#\{\phi(m) : 1\leq m\leq x\}\] and \[V(x)=\#\{\phi(m) \leq x : 1\leq m\}.\] Does $\lim V(x)/V'(x)$ exist? Is it $>1$?
It is trivial that $V'(x) \leq V(x)$. See also [416].
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)$.

See also [448], [692], and [693].

Additional thanks to: Zachary Chase and Kevin Ford
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.\]

See also [446] and [449].

Additional thanks to: Kevin Ford
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$.
OPEN
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$.
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?
Erdős proved that \[\delta_1(n,m) \ll \frac{1}{(\log n)^c}\] for all $m$, for some constant $c>0$. Sharper bounds (for various ranges of $n$ and $m$) were given by Ford [Fo08].

See also [446].

OPEN
Let $k\geq 2$ and $n$ be sufficiently large depending on $k$. Let $A=\{a_1<a_2<\cdots \}$ be the set of those integers in $[n,n^k]$ which have a divisor in $(n,2n)$. Estimate \[\max_{i} a_{i+1}-a_i.\] Is this $\leq (\log n)^{O(1)}$?
See also [446].
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].