cp's OEIS Frontend

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 .

%I A375729 #19 Sep 22 2024 18:42:42
%S A375729 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,
%T A375729 93,128,64,64,32,32,8,6,1,315,315,448,224,224,112,56,56,23,8,8,2,675,
%U A375729 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
%N 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 .
%C A375729 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.
%C A375729 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.
%H A375729 M. Alizadeh, M Darafsheh, and S. Mehrabi, <a href="https://ijpam.uniud.it/online_issue/201839/38-Alizadeh-Darafsheh-Mehrabi.pdf">On the k-normal elements and polynomials over finite fields</a>, Italian Journal of Pure and Applied Mathematics, 39 (2018), 451-464.
%H A375729 S. Huczynska, G. Mullen, D. Panario, and D. Thomson, <a href="https://doi.org/10.1016/j.ffa.2013.07.004">Existences and properties of k-normal elements over finite fileds</a>, Finite Fields and Their Applications, 24 (2013), 170-183.
%e A375729  Triangle begins ...
%e A375729     1,     1;
%e A375729     1;
%e A375729     1,     1;
%e A375729     2,     1;
%e A375729     3,     3;
%e A375729     4,     2,   3;
%e A375729     7,     7,   0,   2,   2;
%e A375729    16,     8,   4,   2;
%e A375729    21,    21,   7,   7;
%e A375729    48,    24,  24,   0,   3;
%e A375729    93,    93;
%e A375729   128,    64,  64,  32,  32,   8,  6,  1;
%e A375729   315,   315;
%e A375729   448,   224, 224, 112,  56,  56, 23,  8,  8,  2;
%e A375729   675,   675, 225, 225, 135, 135, 45, 45,  9,  9, 2, 2;
%e A375729   2048, 1024, 512, 256, 128,  64, 32, 16;
%e A375729   3825, 3825,   0,   0,   0,   0,  0,  0, 30, 30;
%e A375729   ...
%e A375729  T(6,1) = 2 because we have 1+X+X^6 and 1+X+X^3+X^4+X^6.
%t A375729 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}]]
%Y A375729  Cf. A001037 (row sums), A027362 (column k=0), A330694, A003473.
%K A375729 nonn,tabf
%O A375729 1,6
%A A375729 _Geoffrey Critzer_, Aug 25 2024