# On the prime factorisation of g(k) = (k^2)! * prod (j=0, k-1, j!/(j+k)!)

In "The Riemann Hypothesis", Notices of the AMS, March 2003, J. B. Conrey points out that g(k) = (k^2)! * prod (j=0, k-1, j!/(j+k)!) has an interesting prime factorisation.

I have discovered (or re-discovered) that if v(g(k), p(n)) denotes the power to which the nth prime p(n) is raised in the prime factorisation of g(k) then it appears that the following partial symmetry holds

      v(g(k), p(n)) = v(g(p(n) - k), p(n)), n > 1, 1 <= k <= (p(n) – 1)/2


To see the full extent of the partial symmetry, each prime factorisation needs to be infinite in extent.

The partial symmetry can clearly be seen in the portion of the table of exponents below defined by 1 <= k < p(n), 2 < p(n) <= 23.

       n  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
p(n) 2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79
k
1       0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
2       1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
3       1  1  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
4       3  1  0  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
5       2  1  1  0  2  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0
6       4  2  1  0  2  2  2  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0
7       4  1  1  1  1  2  2  2  2  1  1  1  1  1  1  0  0  0  0  0  0  0
8       7  2  2  1  0  1  3  3  2  2  2  1  1  1  1  1  1  1  0  0  0  0
9       6  4  3  1  0  1  3  4  3  2  2  2  1  1  1  1  1  1  1  1  1  1
10       7  4  4  3  0  0  2  4  4  3  3  2  2  2  2  1  1  1  1  1  1  1
11       6  5  4  3  1  0  2  3  5  4  3  3  2  2  2  2  1  1  1  1  1  1
12      10  7  6  2  1  0  1  2  5  4  4  3  3  3  3  2  2  2  2  2  1  1
13       9  9  6  3  1  1  0  1  4  5  5  4  4  3  3  3  2  2  2  2  2  2
14      11  9  5  4  1  1  0  1  3  6  6  5  4  4  4  3  3  3  2  2  2  2
15      11  8  5  4  2  1  0  0  2  6  7  6  5  5  4  4  3  3  3  3  3  2
16      15  8  5  5  4  1  0  0  2  5  7  6  6  5  5  4  4  4  3  3  3  3
17      14  7  4  6  4  2  1  0  1  4  6  7  7  6  6  5  4  4  4  4  3  3
18      15  8  3  7  3  2  1  0  1  4  5  8  7  7  6  6  5  5  4  4  4  4
19      14  7  3  8  2  4  1  1  0  3  4  8  8  8  7  6  6  5  5  5  4  4
20      17  6  4  9  3  4  1  1  0  2  3  7  9  9  8  7  6  6  5  5  5  5
21      15  8  3 10  3  3  1  1  0  2  3  6  9 10  9  8  7  7  6  6  6  5
22      17  7  3 10  4  3  2  1  0  1  2  6  8 10 10  9  8  7  7  6  6  6


v(g(k), p(n)) can be quickly calculated by noting that

v(g(k), p(n)) = (sum(j=0, k-1; sod(j+k, p(n)) - sod(j, p(n))) - sod(k^2, p(n)))/(p(n) - 1)


where sod(m, p(n)) is the sum of the digits of m in base p(n).

I have not seen this conjecture mentioned in the literature to which I have access so I would be most grateful if someone could point me in the right direction to learn more about it.

-

The trick is to simplify as much as possible. Have you noticed that the $n$ never appears alone in your question, but only in the context of $p(n)$, so why don't you just write $p$ for $p(n)$ ? Then, what is sod(j+k, p(n)) ? Notice that if $1\leq k\leq\frac{p-1}{2}$, then the number $j+k$ (for $j\leq k-1$) can only have one digit in base $p$. It's a bit more complicated for $j+(p-k)$; it can have one or two digits. Both $k^2$ and $\left(p-k\right)^2$ can also have one or two digits, but not more. Things simplify if you proceed further this way.

But it's better not to work with digits at all - digits are chaotic, they tend to split arguments into many cases (because of carries). A more suitable formula is

$v\left(u!,p\right)=\sum\limits_{l=1}^{\infty}\left\lfloor\frac{u}{p^l}\right\rfloor$, where $p$ is prime and $u$ is a nonnegative integer.

This sum is not really infinite; it's a sum of the form $\text{finitely many nonzero addends}+0+0+0+...$ (because $\left\lfloor\frac{u}{p^l}\right\rfloor=0$ for sufficiently high $l$).

Now let $1\leq k\leq \frac{p-1}{2}$. Then,

$v\left(g\left(k\right),p\right)=v\left(k^2!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!},p\right)$

$=v\left(k^2!,p\right)+\sum\limits_{j=0}^{k-1}\left(v\left(j!,p\right)-v\left(\left(j+k\right)!,p\right)\right)$

$=\sum\limits_{l=1}^{\infty}\left\lfloor\frac{k^2}{p^l}\right\rfloor+\sum\limits_{j=0}^{k-1}\left(\sum\limits_{l=1}^{\infty}\left\lfloor\frac{j}{p^l}\right\rfloor -\sum\limits_{l=1}^{\infty}\left\lfloor\frac{j+k}{p^l}\right\rfloor\right)$.

Now, the sum $\sum\limits_{l=1}^{\infty}\left\lfloor\frac{k^2}{p^l}\right\rfloor$ stops at $l=1$, because $k^2 < p^2$ and thus all the terms for $l\geq 2$ are zero. The sums $\sum\limits_{l=1}^{\infty}\left\lfloor\frac{j}{p^l}\right\rfloor$ and $\sum\limits_{l=1}^{\infty}\left\lfloor\frac{j+k}{p^l}\right\rfloor$ have not even one nonzero addend, i. e. we can forget about them.

Computing $v\left(g\left(j+p-k\right),p\right)$ goes the same way, but this time we cannot forget about the sum $\sum\limits_{l=1}^{\infty}\left\lfloor\frac{j+p-k}{p^l}\right\rfloor$; it may be nonzero, although it can only have one nonzero term.

I'll leave you the further computations. At the end you will have to prove that

$\left\lfloor \frac{k^2}{p}\right\rfloor = \left\lfloor \frac{(p-k)^2}{p}\right\rfloor - \sum\limits_{j=1}^{p-k-1}\left\lfloor \frac{j+p-k}{p} \right\rfloor$.

Now, noticing that $\left\lfloor \frac{j+p-k}{p} \right\rfloor$ can only take the values $0$ and $1$ (because $\frac{j+p-k}{p} < 2$), and actually is $1$ if $j\geq k$ and $0$ otherwise, we see that $\sum\limits_{j=1}^{p-k-1}\left\lfloor \frac{j+p-k}{p} \right\rfloor$ is simply the number of all $j\in\left\lbrace 1,2,...,p-k-1\right\rbrace$ satisfying $j\geq k$. In other words, $\sum\limits_{j=1}^{p-k-1}\left\lfloor \frac{j+p-k}{p} \right\rfloor = \left(p-k-1\right)-k+1=p-2k$. So it remains to prove that

$\left\lfloor \frac{k^2}{p}\right\rfloor = \left\lfloor \frac{(p-k)^2}{p}\right\rfloor - \left(p-2k\right)$.

But $\left\lfloor \frac{(p-k)^2}{p}\right\rfloor - \left(p-2k\right)=\left\lfloor \frac{(p-k)^2}{p} - \left(p-2k\right)\right\rfloor = \left\lfloor \frac{k^2}{p}\right\rfloor$,

qed.

-
Thank you very much for this, Darij. Best regards, Chris Gribble –  Chris Gribble Mar 16 '10 at 7:24
Some of them even don't know how to accept the answer. :-) –  Wadim Zudilin Jun 8 '10 at 13:11