Lyndon words over the binary alphabet that begin with "00"

102 Views Asked by At

Lydon words over the binary alphabet are strings of $1$s and $0$s such that all rotations of the word are strictly lexicographically later. I've been looking at Lyndon words of length $n$, which are counted by OEIS sequence A001037.

1 | 0,      1
2 | 01
3 | 001,    011
4 | 0001,   0011,   0111
5 | 00001,  00011,  00101,  00111,  01011,  01111
6 | 000001, 000011, 000101, 000111, 001011, 001101, 001111, 010111, 011111

In particular, though, I'm interested in the number of Lyndon words that begin with two or more $0$s.

I generated all Lyndon words of length $n$ and counted those that start with two zeros. Starting at index $n = 1$ there are

0, 0, 1, 2, 4, 7, 14, 25, 48, 88, 168, 310

such words. For $n \geq 3$, this matches OEIS sequence $A065491(n-1)$:

Exponents in expansion of $\displaystyle\prod_{\textrm{prime }p\, \geq\, 3} \left(1 - \frac1{p^2-p-1}\right)$ as a product $\zeta(n)^{-a(n)}$.

That is, $$ \prod_{\textrm{prime }p\, \geq\, 3} \left(1 - \frac1{p^2-p-1}\right) = \zeta(0)^0 \cdot \zeta(1)^{-1} \cdot \zeta(2)^{-1} \cdot \zeta(3)^{-2} \cdot \zeta(4)^{-4} \cdot \zeta(5)^{-7} \cdots $$

I can't prove (or disprove!) this identity. Why are these two sequences equal? Or is this just a coincidence?