6
$\begingroup$

I've seen this stated in a few places.

If $$\vartheta(x) = \sum_{p\le{x}} \log (p) \qquad \psi(x) = \sum_{m=1}^{\infty}\vartheta\left(\sqrt[m]{x}\right)$$ Then $$\log(x!) = \sum_{m=1}^{\infty} \psi\left(\frac{x}{m}\right).$$

It is used by Ramanujan here. It is used by Jitsuro Nagura here.

Can anyone provide a proof for why it is true or provide a link to a proof?

Thanks very much.

$\endgroup$
8
$\begingroup$

We find

$$\sum_{m\ge1}\psi\left(\frac{x}{m}\right)=\sum_{m\ge1}\sum_{k\ge1}\vartheta\left(\sqrt[k]{\frac{x}{m}}\right)=\sum_{m\ge1}\sum_{k\ge1}\sum_{p\le \sqrt[k]{x/m}}\log p$$

$$=\sum_{m\ge1}\sum_{k\ge1}\sum_{mp^k\le x}\log p=\log \prod_{p\le x}p^{\#\{(m,k):mp^k\le x\}}=\log x!$$

since when counting $\#\{(m,k):mp^k\le x\}$, one sees for every $1\le n\le x$ there are $t=v_p(n)$ different tuples $(m,t),(mp,t-1),\cdots,(mp^{t-1},1)$ counted in the set (note $k\ge1$).

$\endgroup$
  • $\begingroup$ Could you please expand a bit on your last paragraph? It looks to me like you're counting only the pairs $(m,v_p(n))$ with $m = 1$. $\endgroup$ – A.P. Apr 28 '15 at 9:13
  • $\begingroup$ @A.P. Sorry, it's been two years so I don't quite remember what went wrong, but I suspect my brain might have went dark when typing out what I saw in my head. I've edited to give the correct list of tuples corresponding to each $1\le n\le x$. Basically, compute the sizes of the fibers of the obvious map $\{(m,k):mp^k\le x\}\to\{n:1\le n\le x\}$ given by $(m,k)\mapsto mp^k$ then sum the fibers' sizes. $\endgroup$ – anon Apr 28 '15 at 10:56
  • 1
    $\begingroup$ Thank you, now I understand. It still took me a while to parse your wording, so for the benefit of other here is how I see it: for every positive integer $n$ there are exactly $v_p(n)$ ways of writing $n$ as $m p^t$ with $m \in \Bbb{Z}$ and $t \geq 1$. $\endgroup$ – A.P. Apr 28 '15 at 11:06
2
$\begingroup$

A slightly different variation based upon the prime factorisation of $x!$.

We obtain for integers $x>0$ \begin{align*} \color{blue}{\log x!}&=\log\prod_{p\leq x}p^{\left\lfloor\frac{x}{p}\right\rfloor+\left\lfloor\frac{x}{p^2}\right\rfloor+\cdots}\tag{1}\\ &=\log\prod_{p\leq x}p^{\sum_{m=1}^\infty\left\lfloor\frac{x}{p^m}\right\rfloor}\tag{2}\\ &=\sum_{p\leq x}\sum_{m=1}^\infty\log p\left\lfloor\frac{x}{p^m}\right\rfloor\tag{3}\\ &=\sum_{m=1}^\infty\sum_{p\leq \sqrt[m]{x}}\log p\left\lfloor\frac{x}{p^m}\right\rfloor\tag{4}\\ &=\sum_{m=1}^\infty\sum_{p\leq \sqrt[m]{x}}\log p\sum_{j=1}^{x/p^m}1\tag{5}\\ &=\sum_{m=1}^\infty\sum_{j=1}^x\sum_{p\leq \sqrt[m]{x}}\log p\tag{6}\\ &\,\,\color{blue}{=\sum_{j=1}^x\psi\left(\frac{x}{j}\right)} \end{align*} and the claim follows.

Comment:

  • In (1) we do the prime factorisation of $x!$ and observe that $\left\lfloor\frac{x}{p}\right\rfloor$ counts the numbers $\leq x$ which are a multiple of $p$. Since we also have to add $1$ for each number which is a multiple of $p^2$ we add $\left\lfloor\frac{x}{p^2}\right\rfloor$, etc.

  • In (2) we use the series notation. Note the series is finite.

  • In (3) we use properties of the logarithm.

  • In (4) we exchange the order of the series.

  • In (5) we write the factor $\left\lfloor\frac{x}{p^m}\right\rfloor$ as sum.

  • In (6) we exchange the order of the series again.

$\endgroup$
  • $\begingroup$ +1. It's a nice job. $\endgroup$ – Felix Marin Dec 11 '18 at 4:07
  • 1
    $\begingroup$ @FelixMarin: Thanks Felix. This answer follows a proof which was given by E. Landau in 1909. $\endgroup$ – Markus Scheuer Dec 11 '18 at 5:11
  • $\begingroup$ I didn't know that. Thanks because everyday we learn something new. $\endgroup$ – Felix Marin Dec 11 '18 at 16:22
  • 1
    $\begingroup$ @FelixMarin: You're welcome. The same holds true for me. :-) $\endgroup$ – Markus Scheuer Dec 11 '18 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.