A combinatorial formula involving the necklace polynomial

Question

This question is motivated by the answers given to my previous one. In combinatorics, the necklace polynomials are given by $$M(X,n)=\frac1n\sum_{d|n}\mu\left(\frac{n}{d}\right)X^d,$$ where $\mu$ is the Möbius function.

It seems that the following formula holds true (at least, I checked it up to $n=6$): $$\sum_{k\le n}k\left[\frac{n}{k}\right]M(X,k)=X^n+X^{n-1}+\cdots+X^2+X.$$ Is this classical. Is there any reference. Are there known applications of it ?

To me, here is an application: the lcm of all the monic polynomials of degree $n$ over ${\mathbb F}_p$, which is the simplest polynomial vanishing identically over ${\bf M}_n({\mathbb F}_p)$, has degree $p^n+p^{n-1}+\cdots+p^2+p$.

Answer 1

By plugging in the definition of $M$ and rearranging the terms, your polynomial is $$\sum_dx^d\sum_{m\le n/d}\left\lfloor\frac n{md}\right\rfloor\mu(m).$$ A basic property of Möbius inversion is that $$\sum_{m\le x}\left\lfloor\frac xm\right\rfloor\mu(m)=\begin{cases}1,&x\ge1,\\\\0,&x<1.\end{cases}$$

Answer 2

The LHS of your formula can be rewritten as $$ \sum_{k\ge 1, d\mid k}\left[\frac{n}{k}\right]\mu(k/d)X^d, $$ which after rearranging terms becomes $$ \sum_{d\ge 1}X^d\sum_{s\ge 1}\mu(s)\left[\frac{n}{ds}\right]. $$ Let us denote $l:=\frac{n}{d}$, then the coefficient of $X^d$ in this sum is $$ \sum_{s\ge 1}\mu(s)\left[\frac{l}{s}\right]. $$ Applying the M\"obius inversion in the form (see Concrete Mathematics (4.61)) $$ g(x)=\sum_{d\ge 1}f(x/d) \quad \text{ iff } \quad f(x)=\sum_{d\ge 1}\mu(d)g(x/d) $$ to the functions $$ f(x)=[x\ge 1] $$ and $$ g(x)=[x], $$ we conclude that $$ \sum_{s\ge 1}\mu(s)\left[\frac{n}{ds}\right] $$ is equal to $0$ for $1>\frac{n}{d}$ and is equal to $1$ for $1\le\frac{n}{d}$, which is precisely what your conjectured RHS says.