Reasoning about factorials: is this equation correct

factorialleast-common-multiplemobius-inversionproof-verification

I was playing around with the möbius inversion formula and factorials and I came up with an equation that I found interesting:

$$\prod_{i\ge2}\left\lfloor\frac{x}{i}\right\rfloor! = \prod_{i \ge 2}\prod_{j \ge 1}\left(\left\lfloor\frac{x}{ij}\right\rfloor!\right)^{-\mu(i)}$$

I'm not sure if this equation is valid.

Here is the reasoning:

(1) Let $\text{lcm}(x) = $ the least common multiple of $\{1, 2, 3, \dots, x\}$

(2) Using a well known equation:

$$x! = \prod_{i \ge 1}\text{lcm}\left(\left\lfloor\frac{x}{i}\right\rfloor\right)$$

(3) Using mobius inversion, I believe that this is now valid:

$$\text{lcm}(x) = \prod_{i \ge 1}\left(\left\lfloor\frac{x}{i}\right\rfloor!\right)^{\mu(i)}$$

(4) Combining the two equations gets me to:

$$x! = \prod_{j \ge 1}\prod_{i \ge 1}\left(\left\lfloor\frac{x}{ij}\right\rfloor!\right)^{\mu(i)}$$

(5) Since order of the products doesn't matter:

$$x! = \prod_{i \ge 1}\prod_{j \ge 1}\left(\left\lfloor\frac{x}{ij}\right\rfloor!\right)^{\mu(i)}$$

(6) Since for $i=1,j=1$, $x! = \left(\frac{x}{ij}!\right)^{\mu(i)}$:

$$1 = \prod_{i \ge 1}\prod_{j \ge 1\text{ and }j\ne1\text{ if }i=1 }\left(\left\lfloor\frac{x}{ij}\right\rfloor!\right)^{\mu(i)}$$

(7) We can now use division to separate the remaining cases of $i=1$ so that we get:

$$\prod_{j \ge 2}\left\lfloor\frac{x}{j}\right\rfloor! = \prod_{i \ge 2}\prod_{j \ge 1}\left(\left\lfloor\frac{x}{ij}\right\rfloor!\right)^{-\mu(i)}$$

Is this equation correct? And if correct, is it well known?

Best Answer

The calculations are correct.

We have from OP's referenced formula (2) for positive integers $x$

\begin{align*} \color{blue}{x!=\prod_{j=1}^x\mathrm{lcm}\left(\left\lfloor\frac{x}{j}\right\rfloor\right)}\tag{1} \end{align*} where $\mathrm{lcm}(x)$ denotes the least common multiple of all numbers up to $x$. We can write (1) in the form \begin{align*} \log\left(x!\right)&=\log \prod_{j=1}^{x}\mathrm{lcm}\left(\left\lfloor\frac{x}{j}\right\rfloor\right)\\ &=\sum_{j=1}^x\log\mathrm{lcm} \left(\left\lfloor\frac{x}{j}\right\rfloor\right)\tag{2} \end{align*}

We recall an inversion formula which can be found for instance as Theorem 268 in An Introduction to the Theory of Numbers by G.H. Hardy and E.M. Wright:

If for all positive $x$ \begin{align*} G(x)=\sum_{j=1}^{\lfloor x\rfloor} F\left(\frac{x}{j}\right)\qquad\text{ then}\qquad F(x)=\sum_{j=1}^{\lfloor x\rfloor}\mu(j)G\left(\frac{x}{j}\right)\tag{3} \end{align*}

With $G(x)=\log\left(\lfloor x\rfloor !\right)$ and $F(x)=\log\mathrm{lcm}\left(\left\lfloor\frac{x}{j}\right\rfloor\right)$ we obtain from (2) and (3)

\begin{align*} \log\mathrm{lcm}\left(\lfloor x\rfloor\right)&=\sum_{j=1}^{\lfloor x\rfloor}\mu(j)\log\left(\left\lfloor\frac{x}{j}\right\rfloor !\right)\\ &=\sum_{j=1}^{\lfloor x\rfloor}\log\left(\left\lfloor \frac{x}{j}\right\rfloor !\right)^{\mu(j)}\\ &=\log\prod_{j=1}^{\lfloor x\rfloor}\left(\left\lfloor \frac{x}{j}\right\rfloor !\right)^{\mu(j)}\\ \color{blue}{\mathrm{lcm}\left(\left\lfloor x\right\rfloor\right)}& \color{blue}{=\prod_{j=1}^{\lfloor x\rfloor}\left(\left\lfloor\frac{x}{j}\right\rfloor !\right)^{\mu(j)}}\tag{4} \end{align*}

We obtain for positive integer $x$ from (1) and (4) \begin{align*} x!&=\prod_{j=1}^x\mathrm{lcm}\left(\left\lfloor \frac{x}{j}\right\rfloor\right)\tag{5}\\ &=\prod_{j=1}^x\prod_{k=1}^{\lfloor x/j\rfloor}\left(\left\lfloor \left\lfloor \frac{x}{j}\right\rfloor\frac{1}{k}\right\rfloor !\right)^{\mu(k)}\tag{6}\\ &=\prod_{k=1}^x\prod_{j=1}^x\left(\left \lfloor\frac{x}{jk}\right\rfloor !\right)^{\mu(k)}\tag{7}\\ &=\prod_{j=1}^x\left(\left\lfloor \frac{x}{j}\right \rfloor !\right)\prod_{k=2}^x\prod_{j=1}^x\left(\left\lfloor\frac{x}{jk}\right\rfloor !\right)^{\mu(k)}\tag{8}\\ 1&=\prod_{j=2}^x\left(\left\lfloor\frac{x}{j}\right\rfloor !\right)\prod_{k=2}^x\prod_{j=1}^x\left(\left\lfloor \frac{x}{jk}\right\rfloor !\right)^{\mu(k)}\tag{9} \end{align*} from which finally OP's claim \begin{align*} \color{blue}{\prod_{j=2}^x\left(\left\lfloor\frac{x}{j}\right\rfloor !\right)=\prod_{k=2}^x\prod_{j=1}^x\left(\left\lfloor \frac{x}{jk}\right\rfloor !\right)^{-\mu(k)}}\tag{10} \end{align*} follows.

Comment:

  • In (6) we substitute (4) in (5).

  • In (7) we use the identity $\left\lfloor \left\lfloor \frac{x}{j} \right\rfloor \frac{1}{k}\right\rfloor=\left\lfloor \frac{x}{jk}\right\rfloor$. We also exchange the order of the products which is feasible since they are finite and we set the upper limit to $x$ without changing anything since we are only multiplying with $1$.

  • In (8) we separate the case $k=1$.

  • In (9) we divide by $x!$.

I've looked for a citation of formula (10) in

but was not succssful. In fact I think the essential identities are (1) and the inversion formula (3). Since there are so many different variations we can build, it is not that asthonishing that OP's formula is not stated.

Related Question