OFFSET
1,2
COMMENTS
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).
All powers of 2 are terms, corresponding to self-reciprocal polynomials, see Theorem 7 of the Cohen reference.
LINKS
Joerg Arndt, Matters Computational (The Fxtbook), figure 40.9-G on p.854.
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).
EXAMPLE
The 16 x 16 matrix M(4) is (dots for zeros):
111.1...1.......
1..1.1...1......
1.....1...1.....
.1.....1...1....
1...........1...
.1...........1..
..1...........1.
...1...........1
1...............
.1..............
..1.............
...1............
....1...........
.....1..........
......1.........
.......1........
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.
PROG
(PARI)
Mrec(t)=
{ /* Auxiliary routine to build up matrices */
my(n, M);
n = matsize(t)[1];
M = matrix(2*n, 2*n); /* double the size */
/* lower left and upper right: unit matrices */
for (k=1, n, M[k, n+k]=1; M[n+k, k]=1; );
/* upper left: copy of smaller matrix */
for (k=1, n, for (j=1, n, M[k, j]=t[k, j]; ); );
return ( M );
}
Mfunc(n)=
{ /* Compute matrix of size 2^n */
my(M);
M = matrix(1, 1, r, c, 1 ); /* start with unit matrix */
for (k=1, n, M=Mrec(M) ); /* build up to size 2^n */
return( M * Mod(1, 2) ); /* over GF(2) */
}
{ my(e=8, N = 2^e, M = Mfunc(e) );
for (k=1, N,
K = matrix(k, k, r, c, M[r, c]);
C = charpoly(K);
C = polrecip(C); C = polrecip(C); /* get rid of trivial factor (power of x) */
if ( polisirreducible(C), print1(k, ", ") );
); } \\ edited for speed, Joerg Arndt, May 03 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Joerg Arndt, Aug 17 2011
EXTENSIONS
Terms 1536..4092 from Joerg Arndt, May 04 2022
STATUS
approved