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