%&latex
%will accept 10pt 11pt or 12 pt in following line
\documentclass[11pt]{article}
\marginparwidth 0pt
\oddsidemargin 0pt
\evensidemargin 0pt
\marginparsep 0pt
\topmargin 0pt
\textwidth 6.3in
\textheight 8.5in
\def\la{\lambda}
\usepackage{amstex}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\begin{document}
\begin{center}
{\bf The Cyclotomic Identity via Lyndon Words }
\end{center}
\vspace{10mm}
\noindent DAVID CALLAN \\
Department of Statistics \\
University of Wisconsin-Madison \\
1210 W. Dayton St \\
Madison, WI \ 53706-1693 \\
{\bf callan@@stat.wisc.edu}\\
\vspace*{10mm}
{\bf 1. Introduction}. The identity of the title is
\begin{equation}
\frac{1}{1-az} = \prod_{n \geq 1}
\frac{1}{(1-z^{n})^{M(a,n)}}
\end{equation}
where $M(a,n)=\frac{1}{n} \sum_{d|n} \mu(\frac{n}{d}) a^{d}.$
Here $\mu$ is the classical M\"{o}bius
function, and (1) is a formal power series identity in $z$.
When $a$ is a positive integer, the
exponent $M(a,n)$ is also a positive integer and counts
the number of circular arrangements of $n$ letters taken from an
alphabet of $a$ letters. This suggests the possibility of a combinatorial proof.
The present note shows how a straightforward search for such a proof
leads almost directly to the Unique Factorization Theorem for
the so-called Lyndon words that arise in the theory of
Combinatorics on Words. The Lyndon word proof does not seem to be well known.
It is only vaguely referred to
in Rota and Metropolis's 1983/84 papers \cite{rota83, rota84}, where a
``natural'' bijective proof is given. Nor is it mentioned in several
subsequent proofs and generalizations
\cite{varadarajan,taylor,nelson,buchanan,domocos}.
{\bf 2. Notation and Terminology}. Let ${\cal A}=\{A,B,C,\dots\}$ denote a
fixed alphabet of $a$ distinct letters. A {\em word} (on alphabet
${\cal A}$) is any finite sequence of these letters. The {\em length} of
a word is the number of letters in its sequence. There is one word
of length 0: the empty word. Let ${\cal W}(a,n)$ denote the set of $a^{n}$
words of length $n$ on ${\cal A}$ and let
${\cal W}(a)= \bigcup_{n=0}^{\infty} {\cal W}(a,n)$ denote the set of all words
on ${\cal A}.$ In fact, ${\cal W}(a)$ is a monoid with the product of two
words given by juxtaposition and the empty word as identity.
Let ${\cal W}(a)^{+}$ denote the set of nonempty
words in ${\cal W}(a).$
${\cal W}(a)^{+}$ is partitioned into equivalence classes, called
{\em necklaces}, by the following equivalence relation:
$w_{1} \sim w_{2}$ iff $w_{2}$ can be obtained from
$w_{1}$ by cyclic rotation of its letters. Thus $\{ABA,AAB,BAA\}$ is
a necklace, as is $\{ABAB,BABA\}$.
A word $w \in {\cal W}(a)^{+}$ is {\em primitive} if it
cannot be expressed as a power of a shorter word.
Let $<$ denote lex (dictionary) order on ${\cal W}(a)^{+}.$
Thus $A