login
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).
1

%I #26 Jul 08 2020 20:39:26

%S 2,4,36,1536,22500000,263303591362560,

%T 20851424802623573443244703744000,

%U 504371920429767576352765364956611950142002504147895582720000000

%N 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).

%C 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).

%C 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).

%H Michael De Vlieger, <a href="/A326932/b326932.txt">Table of n, a(n) for n = 1..11</a>

%H Christof Beierle, Marcus Brinkmann, Gregor Leander, <a href="https://arxiv.org/abs/2003.12006">Linearly Self-Equivalent APN Permutations in Small Dimension</a>, arXiv:2003.12006 [cs.IT], 2020.

%H L. Carlitz and D. R. Hayes, <a href="https://doi.org/10.4064/aa-21-1-131-135">Permutations with coefficients in a subfield</a>, Acta Arithmetica 21.1 (1972), 131-135.

%F 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.

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

%Y Cf. A001037.

%K nonn

%O 1,1

%A _Christof Beierle_, Oct 22 2019