MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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. – François Brunault Jul 6 '12 at 14:05
up vote 3 down vote accepted

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

share|cite|improve this answer
any reference ? – Denis Serre Jul 6 '12 at 13:37
1 . If you need something printed, Möbius inversion is treated in detail in Apostol’s “Introduction to analytic number theory”. – Emil Jeřábek Jul 6 '12 at 13:44

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.

share|cite|improve this answer
You probably shouldn't use $[\ast]$ both for the floor function and the Iverson bracket... – Dan Petersen Jul 6 '12 at 14:03
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 ;) – Vladimir Dotsenko Jul 9 '12 at 7:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.