|
%I #33 May 04 2022 11:33:59
%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,1536,1864,1960,1962,2048,2150,2306,2368,3072,4096
%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 self-reciprocal polynomials, see Theorem 7 of the Cohen reference.
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, figure 40.9-G on p.854.
%H Stephen D. Cohen, <a href="https://www.researchgate.net/publication/220638305_The_Explicit_Construction_of_Irreducible_Polynomials_over_Finite_Fields">The explicit construction of irreducible polynomials over finite fields</a>, Designs, Codes and Cryptography, vol.2, no.2, pp. 169-174, (June 1992).
%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 my(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 my(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 { my(e=8, N = 2^e, M = Mfunc(e) );
%o for (k=1, N,
%o K = matrix(k, k, r, c, M[r, c]);
%o C = charpoly(K);
%o C = polrecip(C); C = polrecip(C); /* get rid of trivial factor (power of x) */
%o if ( polisirreducible(C), print1(k, ", ") );
%o ); } \\ edited for speed, _Joerg Arndt_, May 03 2022
%K nonn
%O 1,2
%A _Joerg Arndt_, Aug 17 2011
%E Terms 1536..4092 from _Joerg Arndt_, May 04 2022
|
