%I
%S 1,2,3,4,5,6,7,8,9,11,12,16,18,21,24,32,34,48,64,65,74,81,96,117,121,
%T 128,144,153,161,192,241,256,258,288,321,384,493,512,611,617,768,974,
%U 1024
%N n such that certain polynomials are irreducible over GF(2), see first comment.
%C Recursively build matrices by setting M(0) = [1], and M(k+1)=[M(k),E(k); E(k),Z(k)] where E(k) is the N x N unit matrix and Z(k) is the N x N zero matrix (and N=2^k). Let c(x) the characteristic polynomial (over GF(2)) of the upper left n x n submatrix. If c(x), divided by the least power of x with nonzero coefficient, is irreducible over GF(2) then n is a term of this sequence (see example).
%C All powers of 2 are terms, corresponding to selfreciprocal polynomials, see Theorem 7 of the Cohen reference.
%D Stephen D. Cohen, "The explicit construction of irreducible polynomials over finite fields", Designs, Codes and Cryptography, vol.2, no.2, pp. 169174, (June 1992).
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, figure 40.9G on p.854
%e The 16 x 16 matrix M(4) is (dots for zeros):
%e 111.1...1.......
%e 1..1.1...1......
%e 1.....1...1.....
%e .1.....1...1....
%e 1...........1...
%e .1...........1..
%e ..1...........1.
%e ...1...........1
%e 1...............
%e .1..............
%e ..1.............
%e ...1............
%e ....1...........
%e .....1..........
%e ......1.........
%e .......1........
%e The characteristic polynomial of the 9 x 9 (upper left) submatrix is c(x)=x^9 + x^8 + x^5 + x^3 + x^2, and C(x)/x^2 = x^7 + x^6 + x^3 + x + 1 is irreducible over GF(2), so 9 is a term.
%o (PARI)
%o Mrec(t)=
%o { /* Auxiliary routine to build up matrices */
%o local(n, M);
%o n = matsize(t)[1];
%o M = matrix(2*n, 2*n); /* double the size */
%o /* lower left and upper right: unit matrices */
%o for (k=1, n, M[k,n+k]=1; M[n+k,k]=1; );
%o /* upper left: copy of smaller matrix */
%o for (k=1, n, for (j=1, n, M[k,j]=t[k,j]; ); );
%o return ( M );
%o }
%o Mfunc(n)=
%o { /* Compute matrix of size 2^n */
%o local(M);
%o M = matrix(1,1, r,c, 1 ); /* start with unit matrix */
%o for (k=1, n, M=Mrec(M) ); /* build up to size 2^n */
%o return( M * Mod(1,2) ); /* over GF(2) */
%o }
%o { for (k=1, N,
%o K =matrix(k,k,r,c,M[r, c]);
%o C = charpoly(K, , 2); /* Hessenberg is much faster than Berkowitz */
%o c = polrecip(C); c = polrecip(c); /* get rid of trivial factor (power of x) */
%o if ( polisirreducible(c), print1(k,", ") );
%o ); }
%K nonn
%O 1,2
%A _Joerg Arndt_, Aug 17 2011
