A213224 Minimal order A(n,k) of degree-n irreducible polynomials over GF(prime(k)); square array A(n,k), n>=1, k>=1, read by antidiagonals.

1, 1, 3, 1, 4, 7, 1, 3, 13, 5, 1, 4, 31, 5, 31, 1, 3, 9, 13, 11, 9, 1, 7, 7, 5, 11, 7, 127, 1, 3, 9, 16, 2801, 7, 1093, 17, 1, 4, 307, 5, 25, 36, 19531, 32, 73, 1, 3, 27, 5, 30941, 9, 29, 32, 757, 11, 1, 3, 7, 16, 88741, 63, 43, 64, 19, 44, 23

Offset: 1

Author

Alois P. Heinz, Jun 06 2012

Keywords

• nonn
• tabl

Comments

Maximal order of degree-n irreducible polynomials over GF(prime(k)) is prime(k)^n-1 and thus A(n,k) < prime(k)^n.

Examples

			A(4,1) = 5: The degree-4 irreducible polynomials p over GF(prime(1)) = GF(2) are 1+x+x^2+x^3+x^4, 1+x+x^4, 1+x^3+x^4. Their orders (i.e., the smallest integer e for which p divides x^e+1) are 5, 15, 15, and the minimal order is 5. (1+x+x^2+x^3+x^4) * (1+x) == x^5+1 (mod 2).
Square array A(n,k) begins:
    1,    1,     1,    1,   1,       1,        1,   1, ...
    3,    4,     3,    4,   3,       7,        3,   4, ...
    7,   13,    31,    9,   7,       9,      307,  27, ...
    5,    5,    13,    5,  16,       5,        5,  16, ...
   31,   11,    11, 2801,  25,   30941,    88741, 151, ...
    9,    7,     7,   36,   9,      63,        7,   7, ...
  127, 1093, 19531,   29,  43, 5229043, 25646167, 701, ...
   17,   32,    32,   64,  32,      32,      128,  17, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 1..45, flattened
• Eric Weisstein's World of Mathematics, Irreducible Polynomial
• Eric Weisstein's World of Mathematics, Polynomial Order

Crossrefs

Columns k=1-10 give: A212953, A218356, A218357, A218358, A218359, A218360, A218361, A218362, A218363, A218364.

Columns k=1-10 are first columns of: A059912, A212906, A212485, A212486, A218336, A218337, A218338, A218339, A218340, A218341.

Cf. A212737 (all orders).

Programs

Maple

with(numtheory):
M:= proc(n, i) option remember;
      divisors(ithprime(i)^n-1) minus U(n-1, i)
    end:
U:= proc(n, i) option remember;
      `if`(n=0, {}, M(n, i) union U(n-1, i))
    end:
A:= (n, k)-> min(M(n, k)[]):
seq(seq(A(n, d+1-n), n=1..d), d=1..14);

Mathematica

M[n_, i_] := M[n, i] = Divisors[Prime[i]^n - 1] ~Complement~ U[n-1, i]; U[n_, i_] := U[n, i] = If[n == 0, {}, M[n, i] ~Union~ U[n-1, i]]; A[n_, k_] := Min[M[n, k]]; Table[Table[A[n, d+1-n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)

Formula

A(n,k) = min(M(n,k)) with M(n,k) = {d : d|(prime(k)^n-1)} \ U(n-1,k) and U(n,k) = M(n,k) union U(n-1,k) for n>0, U(0,k) = {}.