Lyndon words over $GF(4)$ with given trace and subtrace
Here we consider the number $L(n;t,s)$ of length $n$ Lyndon words $a_1 a_2 \ldots a_n$ over the alphabet consisting of the elements of the field $GF(4)$ that have trace $t$ and subtrace $s$.
The
trace of a Lyndon word is the sum of its digits over the field, i.e., $t = a_1 + a_2 + \cdots + a_n$.
The
subtrace is the sum of the products of all $n(n-1)/2$ pairs of digits taken over the field, i.e., $s=\sum_{1\leq i\lt j\leq n} a_i a_j$.
Below we use $a=\operatorname{root}(x^2+x+1)$ and $b=1+a$.
|
| (trace,subtrace) |
| $n$
| (0,0)
| (0,1)
(0,$a$)
(0,$b$)
| (1,0)
($a$,0)
($b$,0)
| (1,1)
($a$,$b$)
($b$,$a$)
| (1,$a$)
(1,$b$)
($a$,1)
($a$,$a$)
($b$,1)
($b$,$b$)
|
| 1 |
1 | 0
| 1 | 0
| 0
|
|---|
| 2 |
0 | 0
| 1 | 1
| 0
|
|---|
| 3 |
2 | 1
| 1 | 2
| 1
|
|---|
| 4 |
6 | 2
| 4 | 4
| 4
|
|---|
| 5 |
15 | 12
| 15 | 12
| 12
|
|---|
| 6 |
40 | 40
| 45 | 45
| 40
|
|---|
| 7 |
153 | 144
| 144 | 153
| 144
|
|---|
| 8 |
528 | 496
| 512 | 512
| 512
|
|---|
| 9 |
1841 | 1813
| 1841 | 1813
| 1813
|
|---|
| 10 |
6528 | 6528
| 6579 | 6579
| 6528
|
|---|
| 11 |
23901 | 23808
| 23808 | 23901
| 23808
|
|---|
| 12 |
87550 | 87210
| 87380 | 87380
| 87380
|
|---|
| 13 |
322875 | 322560
| 322875 | 322560
| 322560
|
|---|
| 14 |
1198080 | 1198080
| 1198665 | 1198665
| 1198080
|
|---|
| 15 |
4474738 | 4473647
| 4473647 | 4474738
| 4473647
|
|---|
Examples
The one 4-ary Lyndon word of trace $b$, subtrace $a$ and length 2 is $\{1a\}$.
The two 4-ary Lyndon words of trace 0, subtrace 0 and length 3 are $\{123, 132\}$.
The two 4-ary Lyndon words of trace 0, subtrace 1 and length 4 are $\{0011, 11aa\}$.
Enumeration (OEIS)
-
Column (0,0) is OEIS A074446.
-
Column (0,1),(0,$a$),(0,$b$) is OEIS A074447.
-
Column (1,0),($a$,0),($b$,0) is OEIS A074448.
-
Column (1,1),($a$,$b$),($b$,$a$) is OEIS A074449.
-
Column (1,$a$),(1,$b$),($a$,1),($a$,$a$),($b$,1),($b$,$b$) is OEIS A074450.