A326932 The number of permutations of GF(2^n) that are of the form x -> g(x), where g is a polynomial with coefficients in GF(2).

2, 4, 36, 1536, 22500000, 263303591362560, 20851424802623573443244703744000, 504371920429767576352765364956611950142002504147895582720000000

Offset: 1

Author

Christof Beierle, Oct 22 2019

Keywords

• nonn

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.

Crossrefs

Cf. A001037.

Programs

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 *)

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.