login
This site is supported by donations to The OEIS 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
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, 128, 144, 153, 161, 192, 241, 256, 258, 288, 321, 384, 493, 512, 611, 617, 768, 974, 1024 (list; graph; refs; listen; history; text; internal format)
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.

REFERENCES

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

LINKS

Table of n, a(n) for n=1..43.

Joerg Arndt, Matters Computational (The Fxtbook), figure 40.9-G on p.854

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 */

    local(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 */

    local(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) */

}

{ for (k=1, N,

  K =matrix(k, k, r, c, M[r, c]);

  C = charpoly(K, , 2);  /* Hessenberg is much faster than Berkowitz */

  c = polrecip(C);  c = polrecip(c); /* get rid of trivial factor (power of x) */

  if ( polisirreducible(c), print1(k, ", ") );

); }

CROSSREFS

Sequence in context: A007602 A167620 A169935 * A239087 A095227 A131366

Adjacent sequences:  A193495 A193496 A193497 * A193499 A193500 A193501

KEYWORD

nonn

AUTHOR

Joerg Arndt, Aug 17 2011

STATUS

approved

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 May 20 02:22 EDT 2019. Contains 323411 sequences. (Running on oeis4.)