The Fibonacci polynomials are defined as f_0 (x) = 0; f_1(x) = 1; f_2(x) = x;
and f_i(x) = xf_{i-1}(x) + f_{i-2}(x). Note that by letting x=1,
the recurrence simply generates the Fibobacci numbers.
We are interested in these polynomials over GF(2), as they play
a role in The Coin Flipping Problem
For example, all initial configurations of the m by n grid can be
made all-white if and only if GCD(f_{n+1}(x+1), f_{m+1}(x))=1.
For more details see the following (and the references therein):
- Maximum orbit weight in the sigma-game and lit-only sigma-game on
grids and graphs, J. Goldwasser and W. Klostermeyer, Graphs and
Combinatorics 45 (2009), pp. 235-250
- Total Odd Dominating Sets in Grid Graphs, W. Klostermeyer, UNF
CCEC Symposium, 2006
- Parity Dominating Sets in Grid
Graphs J. Goldwasser and W. Klostermeyer, Cong. Num., vol. 172, 2005,
pp. 79-96
- Odd and Even Dominating Sets with
Open Neighborhoods , J. Goldwasser
and W. Klostermeyer, Ars Combinatoria, 2007, pp. 229-247
- Maximization Versions of 'Lights Out'
Games in Grids and Graphs; J. Goldwasser and
W. Klostermeyer, Congressus Numerantium, vol. 126, 1997, pp. 99-111
- Fibonacci Polynomials and Parity Domination
in Grid Graphs; J. Goldwasser, W. Klostermeyer, and H. Ware,Graphs and
Combinatorics, vol. 18 (2002), pp. 271-283
- Characterizing Switch Setting Problems; J. Goldwasser, W. Klostermeyer,
and G. Trapp, Linear and Multilinear Algebra, vol. 43, no. 1-3 (1997), pp. 121-136
- Another Way to Solve Nine Tails; F. Delahan, W. Klostermeyer, and
G. Trapp; SIGCSE Bulletin, vol. 27, 1995, no. 4, pp. 27-28, 34
Powerpoint Presentation
Note: Yair Caro and I (with John Goldwasser) have written two papers
on the sizes of odd dominating sets in graphs (a subject related
to the above papers). E-mail me if interested.
Below are some (large) files with lots of interesting data. Source code
is available upon request.
List of some periods, Ln
List of Fibonacci indices of some polynomials
List of first 258 factored Fibonacci Polynomials
List of first 2669 factored Fibonacci Polynomials
List of factored Fibonacci Polynomials with Index 2^k +-1
List of n's such that n by n grids are completely solvable
List of Fibonacci indices of some irreducible self-conjugate polynomials
List of Fibonacci-primes
Click here to see Pascal's Rhombus (mod 2), a triangle with nice fractals.
Pascal's Rhombus is generated by a[i, j]=a[i-1, j] + a[i-1, j-1] + a[i-1, j+1] + a[i-2, j]
which is related to the recurrence used in generating nullspace matrices for the
coin-flipping problem.
Some references and an example are listed here
