Strings over $GF(4)$ with given trace and subtrace
Here we consider the number $S(n;t,s)$ of length $n$ 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 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$) ($a$,1) ($b$,1) (1,$b$) ($a$,$a$) ($b$,$b$)
|
1 |
1 | 0
| 1 | 0
| 0
|
---|
2 |
1 | 1
| 2 | 2
| 0
|
---|
3 |
7 | 3
| 3 | 7
| 3
|
---|
4 |
28 | 12
| 16 | 16
| 16
|
---|
5 |
76 | 60
| 76 | 60
| 60
|
---|
6 |
256 | 256
| 272 | 272
| 240
|
---|
7 |
1072 | 1008
| 1008 | 1072
| 1008
|
---|
8 |
4288 | 4032
| 4096 | 4096
| 4096
|
---|
9 |
16576 | 16320
| 16576 | 16320
| 16320
|
---|
10 |
65536 | 65536
| 65792 | 65792
| 65280
|
---|
11 |
262912 | 261888
| 261888 | 262912
| 261888
|
---|
12 |
1051648 | 1047552
| 1048576 | 1048576
| 1048576
|
---|
13 |
4197376 | 4193280
| 4197376 | 4193280
| 4193280
|
---|
14 |
16777216 | 16777216
| 16781312 | 16781312
| 16773120
|
---|
15 |
67121152 | 67104768
| 67104768 | 67121152
| 67104768
|
---|
Examples
The one 4-ary string of trace 0, subtrace 1 and length 2 is $\{11\}$.
The two 4-ary strings of trace $a$, subtrace $b$ and length 2 are $\{1b, b1\}$.
The three 4-ary strings of trace $b$, subtrace 1 and length 3 are $\{11b, 1b1, b11\}$.
Enumeration (OEIS)
-
The number $S(n;t,s)$ can be computed from the following recurrence relation
\begin{align}
S(n;t,s) &= S(n-1;t,s) + S(n-1;t-1,s-(t-1)) + S(n-1;t-a,s-a(t-a)) + S(n-1;t-b,s-b(t-b)) \\
&= S(n-1;t,s) + S(n-1;t+1,s+t+1) + S(n-1;t+a,s+a(t+a)) + S(n-1;t+b,s+b(t+b)).
\end{align}
Note that all operations involving operands $t$ or $s$ are carried out over $GF(4)$.
-
Column (0,0) is OEIS A073995.
-
Column (0,1),(0,$a$),(0,$b$) is OEIS A073996.
-
Column (1,0),($a$,0),($b$,0) is OEIS A073997.
-
Column (1,1),($a$,$b$),($b$,$a$) is OEIS A073998.
-
Column (1,$a$),($a$,1),($b$,1),(1,$a$),($a$,$a$),($b$,$b$) is OEIS A073999.