OFFSET
1,2
COMMENTS
Let g(x) = Sum_{i=0..n-1} g_i x^i in GF(q)[x]. Define an action on the algebraic closure of GF(q) by g*a = Sum_{i=0..n-1} g_i a^(q^i). The annihilator of a is an ideal and is generated by a polynomial g of minimum degree. If deg(g) = n-k then a is k-normal.
An element a in GF(q^n) is 0-normal if {a, a^q, a^(q^2), ..., a^(q^(n-1))} is a basis for GF(q^n) over GF(q).
LINKS
S. Huczynska, G. Mullen, D. Panario, and D. Thomson, Existences and properties of k-normal elements over finite fields, Finite Fields and Their Applications, 24 (2013), 170-183.
Zülfükar Saygi, Ernist Tilenbaev, Çetin Ürtiş, On the number of k-normal elements over finite fields, Turk J Math., (2019) 43.795.812.
David Thompson, Something about normal bases over finite fields, Existence and properties of k-normal elements over finite fields, Slides, (2013).
FORMULA
T(n, k) = Sum_{h | x^n-1, deg(h) = n-k} phi_2(h) where phi_2(h) is the generalized Euler phi function and the polynomial division is in GF(2)[x].
EXAMPLE
Triangle begins
1;
2, 1;
3, 3, 1;
8, 4, 2, 1;
15, 15, 0, 0, 1;
24, 12, 18, 3, 5, 1;
49, 49, 0, 14, 14, 0, 1;
128, 64, 32, 16, 8, 4, 2, 1;
189, 189, 63, 63, 0, 0, 3, 3, 1;
480, 240, 240, 0, 30, 15, 15, 0, 2, 1;
1023, 1023, 0, 0, 0, 0, 0, 0, 0, 0, 1;
1536, 768, 768, 384, 384, 96, 96, 24, 26, 7, 5, 1;
4095, 4095, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1;
MATHEMATICA
Needs["FiniteFields`"]; Table[b = Map[GF[2^n][#] &, Tuples[{0, 1}, n]];
Table[Count[Table[MatrixRank[Table[b[[i]]^(2^k), {k, 0, n - 1}][[All, 1]],
Modulus -> 2], {i, 2, 2^n}], k], {k, 1, n}] // Reverse, {n, 1, 8}] // Grid
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Geoffrey Critzer, Dec 25 2019
STATUS
approved