3
$\begingroup$

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?

$\endgroup$
2
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @LarryFreeman: Thanks a lot for accepting my answer and granting the bounty. I've added a proof of (1) which might be useful. $\endgroup$ – Markus Scheuer Nov 27 '18 at 23:08

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.