4
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ Replacing $\mathbf{F}_p[X]$ with $\mathbf{Z}$, the analogue of this number is $\operatorname{lcm}(1,\ldots,n)$, whose asymptotic behaviour is somewhat similar : $\log \operatorname{lcm}(1,\ldots,n) \sim n$ by the prime number theorem, see e.g. mathworld.wolfram.com/LeastCommonMultiple.html $\endgroup$ – François Brunault Jul 6 '12 at 14:05
3
$\begingroup$

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}$$

$\endgroup$
2
2
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ You probably shouldn't use $[\ast]$ both for the floor function and the Iverson bracket... $\endgroup$ – Dan Petersen Jul 6 '12 at 14:03
  • $\begingroup$ Yes this ambiguity would make this answer hard to parse for a robot. I am sure all curious robots can figure out answers for themselves ;) $\endgroup$ – Vladimir Dotsenko Jul 9 '12 at 7:45

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.