OFFSET
1,1
COMMENTS
Let q be a prime power. Each function from GF(q) to itself can be uniquely represented by a polynomial in GF(q)[X] of degree at most q-1. A polynomial g in GF(q)[X] is said to be a permutation polynomial, if the function x -> g(x) is a permutation of GF(q). a(n) gives the number of permutation polynomials in GF(2^n)[X] of degree at most 2^n-1 whose coefficients are all in the prime field GF(2).
Let GF(p) be a subfield of GF(q). The permutations of GF(q) of the form x -> g(x), where g is a polynomial with coefficients in GF(p), form a subgroup of the permutations of GF(q) (see Carlitz and Hayes, 1972).
LINKS
Michael De Vlieger, Table of n, a(n) for n = 1..11
Christof Beierle, Marcus Brinkmann, Gregor Leander, Linearly Self-Equivalent APN Permutations in Small Dimension, arXiv:2003.12006 [cs.IT], 2020.
L. Carlitz and D. R. Hayes, Permutations with coefficients in a subfield, Acta Arithmetica 21.1 (1972), 131-135.
FORMULA
a(n) = Product_{d|n} p(d)!*d^p(d), where p(d) is the number of irreducible polynomials over GF(2) of degree d (i.e., sequence A001037). Proven more generally in Carlitz and Hayes, 1972.
MATHEMATICA
Block[{p}, p[n_] := p[n] = DivisorSum[n, (MoebiusMu[n/#]*2^#/n) &]; Array[Times @@ Map[p[#]!*#^p[#] &, Divisors@ #] &, 11]] (* Michael De Vlieger, Jul 08 2020 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Christof Beierle, Oct 22 2019
STATUS
approved