Is this a correct proof that $\tau(n)$ is eventually smaller than any $n^{\delta}$, $\delta>0$?

350 Views Asked by At

Is this a correct proof that $\tau(n)$ is eventually smaller than any $n^{\delta}$, $\delta>0$? I'm not even sure about the statement, let alone the proof.

Let's first proof this result: $\tau(n) \leq \lceil \log_2(n) \rceil\cdot n^{\log_3(2)}$.

We use $$\tau(n)= (e_2(n)+1)(e_3(n)+1)(e_5(n)+1)(e_7(n)+1)\cdots$$

There are at most $\lfloor \log_2(n) \rfloor$ factors two in the number, hence this multiplies the tau function by at most $\lfloor \log_2(n) \rfloor+1=\lceil \log_2(n) \rceil$. Furthermore, any other factor is at least 3 and multiplies the tau by at most 2. So this brings in a factor of at most $2^{\log_3(n)}=n^{\log_3(2)}$.


In general, for every $i \leq k$, there are at most $\lfloor \log_{p_i}(n) \rfloor$ factors $p_i$ in the number, hence this multiplies the tau function by at most $\lfloor \log_{p_i}(n) \rfloor+1=\lceil \log_{p_i}(n) \rceil$. Furthermore, any other factor is at least $p_{k+1}$ and multiplies the tau by at most 2. So this brings in a factor of at most $2^{\log_{p_{k+1}}(n)}=n^{\log_{p_{k+1}}(2)}$.

Thus we get for any $k$ that $$\tau(n) \leq n^{\log_{p_{k+1}}(2)} \prod^k_{i=1} \lceil\log_{p_i}(n) \rceil$$

This implies that $\tau(n)$ is eventually smaller than any $n^{\delta}$, for any $\delta>0$.

I don't think it is written very rigourously, please give suggestions to write it more rigourously.

1

There are 1 best solutions below

0
On BEST ANSWER

Notice $\tau(p)=2$ and so for sufficiently large primes, say $p> p_r$ we have $\dfrac{2}{p^a}$ is going to be less than $\frac{1}{r}$. for any positive real $r$

Also notice $\tau(p^a)=a+1$ and so for sufficiently large $a$ we have $\dfrac{a+1}{p^{a\delta}}<\frac{1}{r}$.

If we set $r=1$:

This means the value $\frac{\tau(n)}{n^a}$ reaches a maximum, because since $\frac{\tau(n)}{n^{\delta}}$ is multiplicative it must be larger than $1$ at every prime power, so there is only a finite number of possible prime divisors, and only a finite number of options for the power of each prime.

Suppose $r$ is the maximum value reached by $\frac{\tau(n)}{n^{\delta}}$.

Now, let $a_i$ be the maximum positive integer so that $\frac{\tau(p_i^{a_i})}{p_i^{a_i\delta}}\geq \frac{1}{r}$.

let $N=p_1^{a_1}p_2^{a_2}\dots p_r^{a_r}$. Then any integer larger than $N+1$ must have a prime divisor larger than $p_r$ or a prime divisor $p_i$ with $1\leq i\leq r$ which is raised to an exponent $a$ that is larger than its corresponding $a_i$.

This tells us if $n>N$ we can write $n$ as $dk$ with $\frac{\tau(d)}{d^\delta}<\frac{1}{r}$( Let $d$ be the prime power or prime we proved must exist in the previous paragraph). Now notice $\tau(k)\leq r$ since $r$ is the maximum value reached by the function.

Using this along with $\tau(dk)\leq \tau(d)\tau(k)$ we get:

$$\frac{\tau(dk)}{(dk)^\delta}\leq\frac{\tau(d)\tau(k)}{d^\delta k^{\delta}}<\frac{1}{r}{r}=1$$