login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A193498 n such that certain polynomials are irreducible over GF(2), see first comment. 0

%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 self-reciprocal 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. 169-174, (June 1992).

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, figure 40.9-G 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 28 22:40 EST 2020. Contains 331328 sequences. (Running on oeis4.)