We have an m x n rectangular array of switches, each of which can be in the off or on state. We can "push" any vertex, which changes its state, and the state of each of its rectilinear neighbors. We say the pair (m,n) is completely solvable if each initial configuration of off and on vertices in the m x n grid can be brought to the all off state by a sequence of "pushes".
It is easy to show that (m,n) is completely solvable if and only if a certain (mn)x(mn) matrix is nonsingular over GF(2). We have shown that (m,n) is completely solvable if and only if fm+1(x) and fn+1(x+1) are relatively prime, where f0, f1, f2,... is the sequence of Fibonacci polynomials over GF(2) defined by f0 = 0, f1 = 1, fn = xfn-1 + fn-2 for n = 2,3,4,... Among the amazing divisibility properties of these polynomials are the following two, each of which was used to extract information about the m x n grid:
(1) fmn(x) = [fm(x)][fn(xfm(x)] for all m,n
(2) [f2k + 1][f2k - 1] is equal to the square of the product of all irreducible polynomials with degrees dividing k, except x.
If time permits, brief mention will be made of how linear codes can be used to extract further information.
This talk is aimed at a general graduate student - faculty audience.