cp's OEIS Frontend

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

%I A326932 #26 Jul 08 2020 20:39:26
%S A326932 2,4,36,1536,22500000,263303591362560,
%T A326932 20851424802623573443244703744000,
%U A326932 504371920429767576352765364956611950142002504147895582720000000
%N 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).
%C A326932 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 A326932 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 A326932 Michael De Vlieger, <a href="/A326932/b326932.txt">Table of n, a(n) for n = 1..11</a>
%H A326932 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 A326932 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 A326932 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 A326932 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 A326932 Cf. A001037.
%K A326932 nonn
%O A326932 1,1
%A A326932 _Christof Beierle_, Oct 22 2019