# $k$-ary Lyndon words with given trace mod $k$

A $k$-ary Lyndon word is a string made from the characters $\{0,1,\ldots,k-1\}$, i.e., the integers mod $k$. It must be aperiodic (not equal to any of its non-trivial rotations) and be lexicographically least among its rotations. Here we consider the number $L_k(n;t)$ of length $n$ Lyndon words $a_1 a_2 \ldots a_n$ over the alphabet $\{0,1,\ldots,k-1\}$, i.e., $\mathbb{Z}_k$, that have trace $t$. The trace of a $k$-ary Lyndon word is the sum of its digits mod $k$, i.e., $t = a_1 + a_2 + \cdots + a_n \pmod{k}$.

 (trace) binary ternary 4-ary 5-ary 6-ary $n$ 0 1 0 1,2 0,2 1,3 0 1,2,3,4 0 1,5 2,4 3 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 1 1 1 1 2 2 2 2 3 2 3 3 1 1 2 3 5 5 8 8 11 12 12 11 4 1 2 6 6 14 16 30 30 51 54 51 54 5 3 3 16 16 51 51 124 125 259 259 259 259 6 4 5 38 39 165 170 516 516 1282 1296 1284 1293 7 9 9 104 104 585 585 2232 2232 6665 6665 6665 6665 8 14 16 270 270 2032 2048 9750 9750 34938 34992 34938 34992 9 28 28 726 729 7280 7280 43400 43400 186612 186624 186624 186612 10 48 51 1960 1960 26163 26214 195248 195250 1007510 1007769 1007510 1007769 11 93 93 5368 5368 95325 95325 887784 887784 5496925 5496925 5496925 5496925 12 165 170 14736 14742 349350 349520 4068740 4068740 30231741 30233088 30231792 30233034 13 315 315 40880 40880 1290555 1290555 18780048 18780048 167444795 167444795 167444795 167444795 14 576 585 113828 113828 4792905 4793490 87191964 87191964 932900050 932906715 932900050 932906715 15 1091 1091 318848 318864 17895679 17895679 406900992 406901000 5224277345 5224277604 5224277604 5224277345 16 2032 2048 896670 896670 67106816 67108864 1907343750 1907343750 29386526544 29386561536 29386526544 29386561536

## Examples

The three 6-ary Lyndon words of trace 3 and length 2 are $\{03, 12, 45\}$. The two ternary Lyndon words of trace 0 and length 3 are $\{021, 012\}$. The five 4-ary Lyndon words of trace 2 and length 3 are $\{002, 011, 033, 123, 132\}$.

## Enumeration (OEIS)

• The number of Lyndon words with trace 1 is equal to the number of irreducible polynomials over $GF(k)$ with non-zero trace.
• The number $L_k(n;t)$ of $k$-ary Lyndon words of trace $t$ and length $n$ is $L_k(n;t) = \frac{1}{kn} \sum_{\substack{d\vert n \\ \gcd(d,k)\vert t}} \gcd(d,k) \mu(d) k^{n/d}.$
• The number of $k$-ary Lyndon words with given trace is the same whenever the $\gcd$ of the traces with $k$ is the same. Further, if $k$ is the power of a prime $p$, then the number is the same for trace $0, p, p^2 ,\ldots$.
• The binary trace 0 column is OEIS A051841.
• The binary trace 1 column is OEIS A000048.
• The ternary trace=0 column is OEIS A046209.
• The ternary trace=1,2 column is OEIS A046211.
• The 4-ary trace=0,2 column is OEIS A054664.
• The 4-ary trace=1,3 column is OEIS A054660.
• The 5-ary trace=0 column is OEIS A054663.
• The 5-ary trace=1,2,3,4 column is OEIS A054662.
• The 6-ary trace=0 column is OEIS A054665.
• The 6-ary trace=1,5 column is OEIS A054666.
• The 6-ary trace=2,4 column is OEIS A054667.
• The 6-ary trace=3 column is OEIS A054700.