• 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):
  • 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