Skip to content

Erdős problem 448

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

Sources

Browse retained paths and inspect the exact material available for this Problem.

8 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

448.lean

Retained formal statement1 of 8

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

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 nn is ϵ1o(1)\asymp \epsilon^{1-o(1)} (where the o(1)o(1) in the exponent 0\to 0 as ϵ0\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 ϵlog(2/ϵ)\ll \epsilon \log(2/\epsilon). Hall and Tenenbaum further prove that τ+(n)/τ(n)\tau^+(n)/\tau(n) has a distribution function. Erdős and Graham also asked whether there is a good inequality known for nxτ+(n)\sum_{n \leq x} \tau^+(n). This was provided by Ford [Fo08] who proved nxτ+(n)x(logx)1α(loglogx)3/2 \sum_{n \leq x} \tau^+(n) \asymp x\frac{(\log x)^{1-\alpha}}{(\log\log x)^{3/2}} where α=11+loglog2log2=0.08607. \alpha = 1-\frac{1+\log\log 2}{\log 2} = 0.08607\cdots.

FormalConjectures/ErdosProblems/448.leanErdos448.erdos_4481 lineExact file
False ↔ ∀ (ε : ℝ), 0 < ε → {n | ↑(Erdos448.tauPlus n) < ε * ↑n.divisors.card}.HasDensity 1
SolvedStatement only, no proof

Search problems.science

Find a Problem, Result, source, or page