A375729 Irregular triangular array read by rows. T(n,k) is the number of monic irreducible polynomials of degree n in F_2[x] that are k-normal, n>=1, k>=0 .

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

Offset: 1

Author

Geoffrey Critzer, Aug 25 2024

Keywords

• nonn
• tabf

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.

Examples

			 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.
		

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.

Crossrefs

Cf. A001037 (row sums), A027362 (column k=0), A330694, A003473.

Programs

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}]]