Addendum: Mathematical Principles

The mathematical principles at the core of the Lindsey-Fox algorithm are basic.

An N^th degree polynomial is denoted by

P(z) = a₀ + a₁z + a₂z² + … + a_Nz^N = ∑ a_nzⁿ, where n = 0 … N

or

P(z) = ∏(z-z_k) where k = 1 … N

or

P(z) = ∏ (z-z_m)^Mm with N = ∑ M_m where m = 1 … Q

where a_n is the n^th coefficient, z_k is the k^th zero or root, N is the degree of the polynomial, M_m is the multiplicity of the m^th zero, and Q is number of distinct roots or zeros.

The fundamental theorem of algebra states that an N^th degree polynomial has N zeros.

The length-M discrete Fourier transform (DFT) of the N coefficients of a polynomial P(z) with (M≥N) are the M equally spaced samples of the polynomial evaluated on the unit circle of the complex plane.

DFT_M{a_n} = P(e^2*PI*i*k/M) k=0,1,2,...M-1

If the coefficients are multiplied by a geometric sequence, rⁿ, the DFT of this modulated set of coefficients are the M equally spaced samples of the polynomial evaluated on a circle of radius r in the complex plane.

DFT_M{rⁿ a_n} = P(r e^2*PI*i*k/M) k=0,1,2,...M-1

Using Horner's method, the number of multiplications and additions necessary to directly calculate N equally spaced values of a degree N polynomial on the unit circle is proportional to N². If evaluated with the DFT, it is also proportional to N². If evaluated with the FFT, it is proportional to N log(N).

If the roots of a polynomial are at z, the roots of the same polynomial with the sequence of coefficients reversed (“flipped”), are at 1/z.

P_N,a’ (1/z) = P_N,a (z)

The “Minimum Modulus Theorem” can be stated several ways. A way most applicable to our test of the 3 by 3 cells is: If the minimum of an analytic function of a complex variable occurs in the interior of an open set, the minimum must in fact be a zero of the function.

If Newton’s algorithm is applied to a polynomial and is started sufficiently close to a zero, it will quadratically converge to that zero if the zero is simple. If the zero is multiple, it still converges but only linearly. If Laguarre’s algorithm is applied to a polynomial and is started sufficiently close to a zero, it will cubically converge to that zero if the zero is simple. If the zero is multiple, it still converges but only linearly.