OFFSET
1,6
COMMENTS
A monic irreducible polynomial of degree n in F_q[x] is k-normal if the span of its roots (expressed as a q-ary word with respect to any normal basis) in F_q^n has dimension n-k. For a more detailed definition of a k-normal polynomial see the abstract of the Alizadeh, Darafsheh, Mehrabi link below.
Conjecture: Let alpha be in F_q^n. Write alpha as a q-ary word w with respect to the standard polynomial basis (1,x,x^2,x^3,...,x^(n-1)). Let beta in F_q^n be the q-ary word w interpreted with respect to any normal basis. Then beta is a root of a k-normal polynomial iff the period of w = n and deg(gcd(alpha,x^n-1))=k.
LINKS
M. Alizadeh, M Darafsheh, and S. Mehrabi, On the k-normal elements and polynomials over finite fields, Italian Journal of Pure and Applied Mathematics, 39 (2018), 451-464.
S. Huczynska, G. Mullen, D. Panario, and D. Thomson, Existences and properties of k-normal elements over finite fileds, Finite Fields and Their Applications, 24 (2013), 170-183.
EXAMPLE
Triangle begins ...
1, 1;
1;
1, 1;
2, 1;
3, 3;
4, 2, 3;
7, 7, 0, 2, 2;
16, 8, 4, 2;
21, 21, 7, 7;
48, 24, 24, 0, 3;
93, 93;
128, 64, 64, 32, 32, 8, 6, 1;
315, 315;
448, 224, 224, 112, 56, 56, 23, 8, 8, 2;
675, 675, 225, 225, 135, 135, 45, 45, 9, 9, 2, 2;
2048, 1024, 512, 256, 128, 64, 32, 16;
3825, 3825, 0, 0, 0, 0, 0, 0, 30, 30;
...
T(6,1) = 2 because we have 1+X+X^6 and 1+X+X^3+X^4+X^6.
MATHEMATICA
knormalcy[lyndonword_, n_] := n - MatrixRank[Table[RotateRight[lyndonword, k], {k, 0, n - 1}], Modulus -> 2]; Map[Table[Count[#, i], {i, 0, Max[#]}] &, Table[orbit[word_] := Table[RotateLeft[word, k], {k, 0, nn - 1}]; c = Select[DeleteDuplicates[Map[Sort, Map[orbit, Tuples[{0, 1}, nn]] /. Table[Tuples[{0, 1}, nn][[i]] -> i - 1, {i, 1, 2^nn}]]], Length[DeleteDuplicates[#]] == nn &][[All, 1]]; Map[knormalcy[#, nn] &, Table[Tuples[{0, 1}, nn][[i]], {i, 1, 2^nn}][[c + 1]]], {nn, 1, 5}]]
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Geoffrey Critzer, Aug 25 2024
STATUS
approved