How do I prove that there are infinitely many natural numbers $n$ such that $\lfloor\sqrt{3}\cdot\tau(n)\rfloor$ divides $n$?

Question

Let $\tau(n)$ denote the number of positive divisors of a natural number $n$. Prove that there are infinitely many natural numbers $n$ such that $\lfloor\sqrt{3}\cdot \tau(n)\rfloor$ divides $n$.

$∗$ A slightly strengthened version: prove that this remains true by replacing $\sqrt{3}$ with an arbitrary irrational number $0<\alpha<2$.

Attempt:

Let $\tau(n)=12$. Then $\lfloor\sqrt{3}\cdot\tau(n)\rfloor=\lfloor\sqrt{432}\rfloor=20$. Consider numbers of the form $n=2^{2}5p$, where $p$ is prime, not equal to $2$ or $5$. Then $\tau(n)=12$, and all such numbers fit.

Is this the correct solution? (could it be simpler?) And can you please give hints on how to approach the strengthened version?

Answer 1

Yes, your attempt is fine. But you may want to explicitly state (the obvious) that for $n=2^25p$, we indeed do have $\tau(n)=12$ -- or just rewrite the attempt as a forward (and thereby more compelling) proof:

Let $n$ be one of the infinitely many natural numbers of the form $n=2^25p$ where $p$ is a prime $>5$. Then $\tau(n)=3\cdot 2\cdot 2=12$ and $\lfloor\sqrt 3\tau(n)\rfloor=20$ is a divisor of $n$, as desired.

---

For the general case of arbitrary $\alpha>0$, we can proceed somewhat similarly, but need to find "magic" numbers ($2^N$ and $M'$ below) plyaing the same role as the "magic" numbers $12$ and $20$ for $\alpha=\sqrt 3$.

Lemma. Fix $k\in\Bbb N$. Then the sequence $f(1), f(2), f(3),\ldots$ given by $f(n)=\frac{n}{\tau(n)^k}$ diverges to infinity.

Proof. Before we begin, note that $f$ is multiplicative. For each prime $p$, $f(p^r)=\frac{p^r}{(r+1)^k}>0$ is strictly positive and $r\mapsto f(p^r)$ diverges to $+\infty$. Hence for each $p$, $r\mapsto f(p^r)$ attains its minimum and we have $$\tilde f(p):=\min_{r\ge1}f(p^r)>0.$$ If $p>2^k$, then for $r\ge1$, $$\frac{f(p^{r+1})}{f(p^{r})}=\frac{\frac{p^{r+1}}{(r+2)^k}}{\frac{p^r}{(r+1)^k}} =p\cdot \left(1-\frac1{r+2}\right)^k\ge 2^k\cdot \left(\frac23\right)^k>1.$$ Thus for all $p>2^k$, the map $r\mapsto f(p^r)$ is strictly increasing, making $\tilde f(p)=f(p^1)=\frac p{2^k}>1$. Let $$\ell=\prod_p\min\{\tilde f(p),1\}.$$ Then almost all factors are $=1$ and we have $\ell>0$.

Nor for the actual proof of the lemma, let $L>0$ be given. We have to show that for almost all $n$, $f(n)>L$. We may assume wlog. that $ L > \ell$. I claim that we have $f(p^r)> \frac L \ell$ for almost all $(p,r)$. Indeed, if $p>2^k\frac L\ell$, we have $f(p^r)\ge f(p)=\frac p{2^k}> \frac L\ell$, and for the finitely many smaller $p$, $f(p^r)> \frac L\ell$ for almost all $r$ follows from $f(p^r)\to+\infty$.

Then there are only finitely many natural number $n$ that are the product of only prime powers with $f(p^r)\le \frac L\ell$. For all other $n$, $$ f(n)=\prod_{p^r\mid n}f(p^r)>\frac L\ell\prod_p\min\{\tilde f(p),1\}\ge L.$$ This proves the lemma. $\square$

Theorem. Let $\alpha$ be a positive real number. Then there exist infinitely many naturals $n$ with $$ \lfloor \alpha\tau(n)\rfloor\mid n.$$

Proof. Given a natural $N$, let $M=\lfloor2^N\alpha\rfloor$. Write $M=\prod_pp^{a_p}$. Let $M'$ be the least multiple of $M$ such that $\tau(M')$ is a power of $2$, say $\tau(M')=2^K$. Then $M'=\prod_pp^{b_p}$ where $b_p+1$ is the least power of $2$ greater than $a_p$ (and $K=\prod_p(b_p+1)$). It follows that $a_p\le b_p\le 2a_p$, i.e., $M\mid M'\mid M^2$. By the lemma (with $k=2$), there exists $L$ such that $$ \frac{m}{\tau(m)^2}>\alpha^2\qquad\text{for all }m>L.$$ Pick $N>\log_2\frac{L+1}\alpha$. Then $2^N\alpha>L+1$, $M'\ge M>L$, and hence $$ \frac{M'}{\tau(M')^2}>\alpha^2$$ and $$2^K=\tau(M') < \frac1\alpha \sqrt{M'}\le \frac1\alpha M\le \frac1\alpha 2^N\alpha=2^N.$$ Now let $n$ be any of the infinitely many numbers that can be obtained by multiplying $M'$ with $N-K$ distinct primes not dividing $M'$. Then $$\lfloor \alpha \tau(n)\rfloor = \lfloor \alpha\tau(M')2^{N-K}\rfloor = \lfloor 2^N\alpha\rfloor = M\mid M'\mid n$$ as desired. $\square$

Answer 2

It is known that, for any positive irrational number $\beta > 0$, there exist infinitely many $n \in \mathbb{Z}_{\geq 1}$ such that $\lfloor n\beta \rfloor = p$ is a prime. It is even possible to bound the least prime number occurs in such sequence $\{\lfloor n\beta \rfloor | n \geq 1\}$ (which is called Beatty sequence) - see here for details.

Although the above fact is nontrivial, one can deduce the strengthened version of the problem you mentioned from this. The argument is similar to yours but we use simpler $n$. For given $\alpha$, let $\beta = 2\alpha$ and one can find $m \geq 2$ with $\lfloor m\beta\rfloor = \lfloor 2m\alpha \rfloor = p$ is prime. Now, for any prime $q\neq p$, $n = p^{m-1}q$ satisfies $\tau(n) = 2m$ and so $\lfloor \tau(n) \alpha\rfloor = \lfloor m\alpha\rfloor = p $ divides $n = p^{m-1}q$.