%\input amstex
\input psfig
% Number Wall, W.F.Lunnon, 23/08/01, TeX on Sparc.
% Process via " tex numbwall.tex ; dvips -o numbwall.ps numbwall.dvi "
% then " lp numbwall.ps " or " imagetool numbwall.ps & "
% and ftp, chmod or " telnet csa8 "," cp textproc/numbwall.ps /web/staff/fred "
%
%\magnification = \magstep1
\def\init{
\hsize=210truemm
\advance\hsize by -1.7truein
\vsize=297truemm
\advance\vsize by -1.7truein
\advance\vsize by -4\baselineskip % cure page numbers off bottom
\advance\topskip by +4\baselineskip % cure extra space at top
}
% Rejig book defn of \beginsection to avoid large gaps
\outer\def\beginsection#1\par{\vskip0pt plus.2\vsize\penalty-250
\vskip0pt plus-.2\vsize\bigskip\vskip\parskip
\message{#1}\leftline{\bf#1}\nobreak\smallskip\noindent}
%\def\assert #1 #2 #3
%{$$\vcenter{\noindent\advance\hsize by \dimen0 {\bf #1:\/} #3}\eqno #2$$}
\dimen0 = -0.5 truein % room for equn. no. in displayed text
\def\assert #1 #2 #3
{$$\vcenter{\noindent\advance\hsize by \dimen0
\advance\hsize by \dimen0 {\bf #1:\/} #3}\eqno #2$$}
%
\def\title #1#2#3#4{
\vskip 1 in
\centerline{\bf #1}
\vskip 36 pt
\centerline{\sl #3}
\centerline{\sl (#4)}
\centerline{\sl #2.}
\vskip 36 pt}
%
%\def\figure #1 #2 #3{\smallskip
%$$\vcenter{\noindent\advance\hsize by \dimen0 \centerline {\bf #1}
%\smallskip\centerline{\vbox {#3}}}\eqno\hbox{#2}$$
%\smallskip}
\def\figure #1 #2 #3{\smallskip
$$\vcenter{\noindent\advance\hsize by \dimen0 \centerline {{\bf #1}\ {#2}}
\medskip\centerline{\vbox {#3}}}$$
\smallskip}
%
\def\ref(#1.#2){\if0#1[#2]\else(#1.#2)\fi}
\def\fer[#1]{{\bf#1}} % new style biblio reference
\long\def\delete #1{} % \long digests \par but not \beginsection
% \omit and \span are defined previously for use with \halign
%
% $\sqcap\llap\sqcup$ % FAILS and fouls up subsequent stuff ??
%\def\QED{QED}
\def\QED{\vrule height 7pt width 7pt depth 1pt} % 10pt, not scaleable
\def\Proof{Proof}
\def\qmod #1{({\rm mod}\ #1)}
%
\font\tenbg=cmmib10%bold-face math chars
\textfont9=\tenbg
\def\bmit{\fam=9}
\mathchardef\theta="7112%only bold theta,
\mathchardef\pi="7119%pi
\def\1{\overline{1}} %use tilde?
\def\half{{\textstyle{1\over 2}}}
\def\s#1{{\scriptstyle#1}}
\def\Z{{\bf Z}} % AMS-style blackboard bold here?
\def\F{{\bf F}}
\def\R{{\bf R}}
%
\init
\centerline{\psfig{file=logo111.eps,width=4in}}
%NJAS commented out next line
%\title
\centerline{\bf The Number-Wall Algorithm: an LFSR Cookbook}
\vskip .3in
\centerline{W. F. Lunnon}
\smallskip
\centerline{Department of Computer Science}
\centerline{National University of Ireland}
\centerline{Maynooth, Co. Kildare, Ireland}
\smallskip
\centerline{Email address: fred@cs.may.ie}
\bigskip
\par
\delete{
%\beginsection Contents
\par
$$\halign{\hfil#\ &#\hfil\cr
\S{} &Abstract\cr
\S0 &Introduction and Acknowledgements\cr
\S1 &Notation and Formal Laurent Series\cr
\S2 &LFSR Sequences\cr
\S3 &Determinants and Zero-windows\cr
\S4 &The Frame Theorems\cr
\S5 &The Algorithm, Special Cases\cr
\S6 &General Symmetric Walls\cr
\S7 &Performance and the FSSP\cr
\S8 &Interpolation and Vandermonde Matrices\cr
\S9 &Difference Tables\cr
\S10 &Explicit Form of an LFSR Sequence\cr
\S11 &Pad\'e Tables\cr
\S12 &Applications and Related Algorithms\cr
\S13 &Hideous Numerical Example\cr
&References\cr
}$$
\par
}
\beginsection Abstract
\par
This paper might fairly be said to fall between three stools:
the presentation and justification of a number of related computational methods
associated with LFSR sequences, including finding the order, recurrence and
general term; the exploration of tutorial examples and survey of applications;
and a rigorous treatment of one topic, the recursive construction of the
number wall, which we believe has not previously appeared.
\par
The {\sl Number Wall} is the table of Toeplitz determinants associated with a
sequence over an arbitrary integral domain, particularly $\Z$, $\F_p$,
$\R$, and their polynomial and series extensions by many variables.
The relation borne by number walls to LFSR (linear recurring shift register) sequences is
analogous to that borne by difference tables to polynomial sequences:
They can be employed to find the order and recurrence \S3, or to
compute further terms and express the general term explicitly \S10
(although other more elaborate methods may be more efficient \S12, \S8).
\par
Much of the paper collects and summarizes relevant classical theory in
Formal Power Series \S1, Linear Recurrences \S2, Pad\'e Blocks (essentially)
\S3,
Vandermonde Interpolation \S8, and Difference Tables \S9.
A `frame' relation between the elements of the number wall containing zeros
(a {\sl non-normal C-table}, in Pad\'e terminology) is stated and proved \S4,
with the resulting recursive generation algorithm and some special cases \S5;
the consequences of basing the wall on this algorithm instead are explored \S6,
and a cellular automaton is employed to optimize it in linear time \S7.
\par
The connections between number walls and classical Pad\'e tables are
discussed briefly \S11, with other associated areas (Linear Complexity,
QD Algorithm, Toda Flows, Berlekamp-Massey) reviewed even more briefly
\S12. Among topics covered incidentally are the explicit number wall
for an LFSR, in particular for a diagonal binomial coefficient \S8;
dealing with high-degree `polynomials' over finite fields, fast computation
of LFSR order over $\F_p$, and the wall of a linear function of a given
sequence \S9. There are numerous examples throughout, culminating in a final
gruelingly extensive one \S13.
\vskip .3in
\par
{\sl Keywords:} Number Wall, Zero Window, Persymmetric, Toeplitz Matrix,
Hankel Determinant, Linear Complexity, Finite Field, Cryptographic Security,
LFSR, Extrapolation, Toda Flow, Linear Recurring Sequence, Difference Equation,
Zero-Square Table, QD Method, Vandermonde, Formal Laurent Series, Pad\'e Table.
\par
{\sl AMS Subject Classification:} 94A55, 65D05, 11C20, 65-04, 68Q15, 68Q68, 41A21.
\par
\beginsection 0. Introduction and Acknowledgements
\par
The initial aim of this rambling dissertation was to codify what J.~H.~Conway
has christened the {\sl Number Wall}, an efficient algorithm for computing the
array of Toeplitz determinants associated with a sequence over an arbitrary
integral domain: particularly interesting domains in this context are
integers $\Z$, integers modulo a prime $\F_p$, reals $\R$,
and their polynomials and power series extensions.
\S1 (Notation and Formal Laurent Series) sketches elementary the algebraic
machinery of these domains and their pitfalls,
and \S2 (LFSR Sequences) summarizes the elementary theory of Linear Feedback
Shift Registers.
\par
Our original program is now carried out with an earnest aspiration to rigor
that may well appear inappropriate (and may yet be incomplete): however,
on numerous occasions, we discovered the hard way that to rely on intuition
and hope for the best is an embarrassingly unrewarding strategy in this
deceptively elementary corner of mathematical folklore.
In \S3 (Determinants and Zero-windows) we define the number wall,
give simple algorithms for using it to determine the order and recurrence
of an LFSR, establish the recursive construction rule in the absence of zeros
(a.k.a. the Sylvester Identity) and the square window property of zeros (a.k.a.
the Pad\'e Block Theorem) which, despite of its great age and simplicity
of statement, appears to have evaded a substantial number of previous attempts
to furnish it with a coherent demonstration.
In \S4 (The Frame Theorems) we develop the central identities connecting
elements around inner and outer frame of a window of zeros in a wall;
equally contrary to expectation, these prove to be a notably delicate matter!
\S5 (The Algorithm, Special Cases) discusses the recursive algorithm implicit
in the Frame Theorems, particularly the special cases of an isolated zero
and of a binary domain, and digressing along the way to an instructive
fallacy which felled a earlier attempted proof.
\S6 (General Symmetric Walls) explores the consequences of employing this oddly
symmetric algorithm --- rather than the original Toeplitz determinant ---
to build a generalized wall from an arbitrary pair of
sequences of variables or numerals. We show the denominators are always
monomial, and that there is arbitrarily large long-range dependence;
and give some striking examples.
\S7 (Performance and the FSSP) explores how an apparently unrelated idea from
Cellular Automaton Theory --- Firing Squad Synchronization --- plays a major
part in tuning a fast computational algorithm, which has actually been
implemented for the binary domain.
\par
At this point in writing, the focus shifted rather towards a survey of existing
methods, as it became apparent that --- while much if not all of this material is
known by somebody --- there is no collected source reference
for a whole batch of elementary computational problems associated with LFSRs.
\S8 (Interpolation and Vandermonde Matrices) summarizes classical material
which is used to find explicitly the coefficients needed in \S10, digressing to
give explicitly the wall for binomial coefficient diagonals, and a formula for
the general element of the wall in terms of the general element of the sequence
in the LFSR case.
\S9 (Difference Tables) takes a look at a venerable ancestor, the difference
table being to polynomials what the number wall (in a more general way) is to
linear recurrences. Appropriate definition and effective evaluation of a
polynomial are nontrivial for finite characteristic; the ensuing
investigation leads {\sl inter alia} to a fast algorithm for computing
the order of an LFSR over $\F_p$, applicable to a recent study of deBruijn
sequences.
At least some of these strands are pulled together in \S10 (Explicit Term of an
LFSR Sequence)
where we discuss efficient methods of computing the roots and coefficients of
the `exponential' formula for the general element of an LFSR sequence from a
finite set of its elements.
\par
In \S11 (Pad\'e Tables) we make the classical connection between number
walls and rational approximation, and develop some pleasantly straightforward
algorithms for series reciprocal and (`non-normal') Pad\'e approximants.
\S12 (Applications and Related Algorithms) surveys applications including
linear complexity profiles (LCPs) and numerical roots of polynomials
(Rutishauser QD),
with a brief description of the well-known Berlekamp-Massey algorithm
for computing the recurrence of an LFSR sequence from its elements.
Finally \S13 (Hideous Numerical Example) features an intimidating computation,
intended to illustrate some of the nastier aspects of the Outer Frame Theorem,
and succeeding we fear only too well.
\par
As a third strand, we have felt obliged to make this something of a tutorial,
and to that end have sketched proofs for the sake of completeness wherever
practicable: existing proofs of well-known results in this area seem often
to be difficult of access, incomplete, over-complicated or just plain wrong.
We have included frequent illustrative examples, some of which we hope are
of interest in their own right; and a number of conjectures, for this is still
an active research area (or would be if more people knew about it).
\par
It would be surprising if much of the material presented here was genuinely
new --- we have been scrupulous in acknowledging earlier sources where known
to us --- but we felt it worth collating under a uniform approach.
We originally unearthed the Frame Theorems over 25 years ago, and
although the result might now quite reasonably be considered to lie in the
public domain, to the best of our knowledge no complete proof has ever
been published. We trust it is at last in a form fit for civilized consumption:
if so, some of the credit should go to the numerous colleagues who have
persistently encouraged, struggled with earlier drafts, and made suggestions
gratefully incorporated --- in particular Simon Blackburn, David Cantor,
John Conway, Jim Propp, Jeff Shallit, Nelson Stephens.
\par
\beginsection 1. Notation and Formal Laurent Series
\par
For applications we are interested principally in sequences over the
integers $\Z$ or a finite field $\F_p$, especially the binary
field. However, to treat these cases simultaneously, as well as to facilitate
the proofs, we shall need to formulate our results over an arbitrary ground
{\sl integral domain}, i.e. a commutative ring with unity and without divisors
of zero. Such a domain may be extended to its field of fractions by
\fer[Her75] \S3.6, permitting elementary linear algebra, matrices
and determinants to be defined and linear equations to be solved in the usual
way; and further extended to its ring of polynomials and field of (formal)
Laurent power series in a transcendental variable, following a fairly routine
procedure to be expounded below.
\par
There is rarely any need for us to distinguish between variables over
these different domains, so they are all simply denoted by italic capitals.
Integer variables (required for subscripts etc, whose values may include
$\pm\infty$ where this makes sense) are denoted by lower-case italic letters.
Vectors, sequences and matrices are indicated by brackets ---
the sequence $[S_n]$ has elements $\ldots,S_0,S_1,S_2,\ldots$, and
the matrix $[F_{ij}]$ has determinant $|F_{ij}|$.
A sequence is implicitly infinite in both directions, where not explicitly
finite; context should suggest if a truncated segment requires extrapolation
by zero elements, periodic repetition, or the application of some LFSR.
\par
In \S4 the elements are actually polynomials over the ground
domain; and all the quantities we deal with could be expressed as rational
functions (quotients of polynomials) over it. While it is both feasible and
conceptually simpler to couch our argument in terms of these, the
mechanics of the order notation ${\cal O}(X^k)$ introduced below become
unnecessarily awkward; therefore we prefer to utilize the slightly less
familiar concept of {\sl Formal Laurent Series} (FLS).
\par
We define the field of FLS to be the set of two-sided sequences $[\ldots,
S_k, \ldots]$ whose components lie in the given ground field,
and which are {\sl left-finite}, that is
only finitely many components are nonzero for $k < 0$. Arithmetic is defined in
the usual Taylor-Laurent power-series fashion: that is, addition and negation
are term-by-term, multiplication by Cauchy (polynomial) product,
reciprocal of nonzeros by the binomial expansion.
The ground field is injected into the extension by
$S_0\to [\ldots, 0, S_0, 0, \ldots]$.
\par
As usual we write an FLS as an infinite sum of integer powers of the
transcendental $X$ with finitely many negative exponents: its {\sl generating
function}.
The notation is suggestive, but has to be interpreted with some care.
For instance, we cannot in general map from FLSs to values in the ground field
by substituting some value for $X$, since this would require the notion of
convergence to be incorporated in the formalism.
Fortunately we have no need to do so here, since we only ever {\sl specialize}
$X\to 0$, defined simply as extracting the component $S_0$ with zero subscript.
\par
The following property is deceptively important in subsequent applications.
\assert Theorem \ref(1.0)
{Specialization commutes with FLS arithmetic: that is, if $W(V(X),\ldots)$
denotes some (arithmetic) function of FLS elements $V(X),\ldots$, and $V(0)$
denotes $V(X)$ with $X\to 0$ etc, then $W(V(0),\ldots)\ =\ W(V(X),\ldots)(0)$.}
\Proof: This is the case $k = 0$ of the nontrivial fact that two FLSs
$U = [\ldots, S_k, \ldots]$ and $V = [\ldots, T_k, \ldots]$ are equal under
the operations of field arithmetic (if and) only if they are equal
component-wise, that is only if $S_k = T_k$ for all $k$. For suppose there
existed distinct sequences $[S_k], [T_k]$ for which $U = V$ arithmetically.
Then $U-V = 0$, where the sequence corresponding to $U-V$ has some nonzero
component. Using the binomial expansion, we calculate its reciprocal;
now $1 = (U-V)^{-1}\cdot (U-V) = (U-V)^{-1}\cdot 0 = 0$.
So the field would be trivial, which it plainly is not, since it subsumes the
ring of polynomials in X. \QED
\par
In this connection it is instructive to emphasize the significance of
left-finiteness. If this restriction were abandoned, we could consider say
(expanding by the binomial theorem)
$$\eqalign{U\ &=\ 1/(1-X)\ =\ 1+X^{1}+X^{2}+X^{3}+\ldots,\cr
-V\ &=\ X^{-1}/(1-X^{-1})\ =\ \ldots +X^{-3}+X^{-2}+X^{-1};}$$
now by elementary algebra $U = V$ despite the two distinct expansions,
and \ref(1.0) would no longer hold.
Related to this difficulty is the fact that we no longer have a field:
$U-V$ for instance, the constant unity sequence, has no square.
\par
One unwelcome consequence is that the generating function approach frequently
employed as in \fer[Nie89] to discuss Linear Complexity is applicable only to
right- (or mut. mut. left-) infinite sequences, and is unable to penetrate
the `central diamond' region of a number-wall (\S3) or shifted LCP (\S12),
being restricted to a region bounded to the South by some diagonal line.
[It is noteworthy that, elementary as they might be, these matters have
on occasion been completely overlooked elsewhere in the literature.]
% see for instance \fer[Wan89].
\par
\assert Definition \ref(1.1)
{For FLS $U$, the statement $$U = {\cal O}(X^{k})$$ shall mean that $U_l = 0$
for $l < k$.}
It is immediate from the definition that
$$\eqalign{0\ &=\ {\cal O}(X^{\infty});\cr
U + {\cal O}(X^k)\ &=\ U + {\cal O}(X^l)\cr
&\quad\hbox{for $l \le k$ (asymmetry of equality)};\cr
(U + {\cal O}(X^k)) \pm (V + {\cal O}(X^l))\ &=\ (U \pm V) + {\cal
O}(X^{\min(k,l)});\cr
(U + {\cal O}(X^k)) \cdot (V + {\cal O}(X^l))\ &=\ (U \cdot V) + {\cal
O}(X^{\min(k+n,l+m)})\cr
&\quad\hbox{if $U = {\cal O}(X^m)$ and $V = {\cal O}(X^n)$};\cr
(U + {\cal O}(X^k)) / (V + {\cal O}(X^l))\ &=\ (U / V) + {\cal
O}(X^{\min(k-n,l+m)})\cr
&\quad\hbox{if in addition $V_n \ne 0$, so $n$ is maximal}.\cr
}$$
Notice that we can only let $X\to 0$ in $U + {\cal O}(X^k)$ if $k > 0$,
otherwise the component at the origin is undefined; and in practice, we
only ever do so when also $U = {\cal O}(1)$.
In \S4 -- \S5 we shall implicitly make extensive use of these rules.
\par
For completeness, we should perhaps mention the more usual classical strategy
for
ensuring that a set of FLSs forms a field: to define convergence and enforce it,
say over some annular region of the domain of complex numbers. The connection
with our counterexample above is of course that any $S, T$ corresponding to the
same meromorphic function in distinct regions will give $U-V = 0$.
The elementary definitions and algorithms of FLS arithmetic are fully
discussed in standard texts such as \fer[Hen74] \S1.2, or \fer[Knu81]
\S1.2.9 and \S4.7. With the exception of the thorough tutorial \fer[Niv69],
these authors consider only the ring of formal Taylor series with exponents
$k \ge 0$; however, it is a fairly routine matter to extend the ring to a
field, and there seems little reason to constrain oneself in this manner.
\par
\beginsection 2. LFSR Sequences
\par
A sequence $S_n$ is a {\sl linear recurring} or {\sl linear feedback shift
register} (LFSR) sequence when there exists a nonzero vector $[J_i]$
(the {\sl relation}) of length $r+1$ such that
$$\sum_{i=0}^rJ_iS_{n+i}\ =\ 0 \quad\hbox{for all integers $n$.}$$
The integer $r$ is the {\sl order} of the relation.
If the relation has been established only for $a\le n\le b-r$ we say that
the relation {\sl spans} (at least) $S_a,\ldots,S_b$, with $a=-\infty$ and
$b=+\infty$ permitted.
LFSR sequences over finite fields are discussed comprehensively in \fer[Lid86]
\S6.1--6.4.
\par
It is usual to write a relation as an {\sl auxiliary} polynomial $J({\bf E})$
of degree $r$ in the {\sl shift} operator ${\bf E}:\ S_n\to S_{n+1}$:
\assert Definition \ref(2.1)
{The LFSR sequence $[S_n]$ satisfies the relation
$J({\bf E})$ just when for all $n$
$$J({\bf E}) [S_n]\ \equiv\ \sum_i J_i {\bf E}^i[S_n]
\ \equiv\ \sum_i J_i [S_{n+i}]\ =\ [O_n],$$
the zero sequence (with order $0$ and relation $J({\bf E})\ =\ 1$).}
Notice that the number of nonzero components or {\sl dimension} of a relation as a vector is in general $r+1$,
two relations being regarded as equal (as for projective homogeneous
coordinates) if they differ only by some nonzero constant multiple;
also in the case of sequences whose values are given by a polynomial in $n$ \S9,
the {\sl degree} of the polynomial is in general $r-1$.
\par
The {\sl order} of a sequence (infinite in both directions)
is normally understood to mean the minimum order of any relation it satisfies;
this {\sl minimal} relation is simply the polynomial highest common factor
of all relations satisfied by the sequence, and is therefore unique.
[The existence of such an HCF is guaranteed by the Euclidean property of the
ring of polynomials in a {\sl single} variable ${\bf E}$ over the ground
domain, see \fer[Her75] \S3.9.]
The leading and trailing coefficients $J_r,J_0$ of the minimal relation $J$
of a (two-way-infinite) sequence are nonzero: such relations we shall call
{\sl proper}.
These definitions must be interpreted with care when applied to segments
with finite end-points, principally because even minimal relations may fail
to be proper: both leading and trailing zero coefficients will then need
to be retained during polynomial arithmetic on relations. Furthermore, if the
minimum order is $r$ and the span has length $< 2r$, a minimal relation is no
longer unique, since there are too few equations to specify its coefficients.
\par
By the elementary theory (\fer[Lid86] \S6.2) we have an explicit formula for
an LFSR sequence:
\assert Theorem \ref(2.2)
{$[S_n]$ satisfies $J({\bf E})[S_n]\ =\ [O_n]$ just when
$$S_n\ =\ \sum_i K_i X_i{}^n \quad\hbox{for all $n$},$$
where the $X_i$ are the roots of $J(X)$ and the $K_i$ are coefficients,
both lying in the algebraic closure of the ground domain
when $J(X)$ has distinct roots;
when the root $X_i$ occurs with multiplicity $e_i$, $K_i$
is a polynomial in $n$ of degree $e_i-1$.}
\par
\Proof: Since we make frequent reference to this well-known result,
we sketch a demonstration for the sake of completeness.
[Over ground domains of finite characteristic, it is important that the
`polynomials' $K_i(n)$ are defined in terms of binomial coefficients;
we return to this point in \S9.]
\par
From the Pascal triangle recursion, by induction on $e$
$$\eqalign{
({\bf E} - 1) {n\choose e-1}\ &=\ {n\choose e-2},\cr
({\bf E} - 1)^e {n\choose e-1}\ &=\ 0;}\eqno \ref(2.3)$$
and so by expressing the arbitrary polynomial $K(n)$ of degree $e-1$ in $n$ as a
linear combination of binomial coefficients,
we see that its $e$-th difference $({\bf E} - 1)^e K(n)$ is zero.
Similary $({\bf E} - X) X^n\ =\ 0$ and $({\bf E} - X)^e K(n)X^n\ =\ 0$ for
arbitrary $X$.
Suppose $S_n$ has the explicit form above \ref(2.2), where $J(X)$ has just $m$
distinct roots; let $X\ \equiv\ X_m$ etc., and let primes denote the
analogous expressions involving only the other $m-1$ roots; then
$$\eqalign{
J({\bf E})S_n\ &=\ \prod_i ({\bf E} - X_i)^e_i S_n\cr
\ &=\ J'({\bf E})\bigl(({\bf E} - X)^e K(n)X^n\bigr)\ +
\ ({\bf E} - X)^e\bigl(J'({\bf E}) S'{}_n\bigr)\cr
\ &=\ J'({\bf E}) (0) + ({\bf E} - X)^e(0)\ =\ 0}$$
for all $n$, using induction on $m$.
\par
The converse can be approached constructively as in \fer[Lid86]
(who prove the distinct case only)
by setting up linear equations for the $K_i$ and showing that they possess a
unique solution, as we shall do in \ref(8.6) (for distinct $X_i$) and
\ref(9.2) (for coincident $X_i$ effectively). In the general case of multiple
roots, it is simpler to observe that the set of sequences satisfying a given
relation $J$ (assumed to possess nonzero leading and trailing coefficients)
comprise a vector space \fer[Her75] \S4 whose dimension must be $r$,
since each is completely determined by its initial $r$ terms. The set
constructed earlier is also a subspace of dimension $r$,
so the two sets are identical by \fer[Her75] Lemma 4.1.2. \QED
\par
If $J$ is minimal then all the $K_i$ are nonzero: for the Galois group of
an irreducible factor of $J$ is transitive on those $X_i$ and their
corresponding $K_i$ while leaving $S_n$ invariant, so those $K_i$ must all
be nonzero or all zero. In the latter case, $J$ may be divided by the factor
and so is not minimal.
When all the roots coincide at unity, $S_n$ equals an arbitrary
polynomial of degree $r-1$ in $n$; so the latter are seen to be a special case
of LFSR sequences.
\par
\beginsection 3. Determinants and Zero-windows
\par
Given some sequence $[S_n]$, we define its {\sl Number Wall} (also {\sl Zero
Square Table} or --- misleadingly --- {\sl QD Table}) $[S_{m,n}]$ to be the
two dimensional array of determinants given by
\assert Definition \ref(3.1)
{$$S_{m,n}\ =\ \left|\matrix{S_n&S_{n+1}&\ldots&S_{n+m}\cr
S_{n-1}&S_{n}&\ldots&S_{n+m-1}\cr
\vdots&\vdots&\ddots&\vdots\cr
S_{n-m}&S_{n-m+1}&\ldots&S_n\cr}\right|.$$}
The value of $S_{m,n}$ is defined to be unity for $m=-1$, and zero for $m<-1$.
[These are known as {\sl Toeplitz} determinants; or,
with a reflection making them symmetric, and a corresponding sign change of
$(-1)^{m+1\choose 2}$, as {\sl persymmetric} or {\sl Hankel} determinants.]
The rows and columns are indexed by $m$, $n$ resp. in the usual orientation,
with the $m$ axis increasing to the South (bottom of page) and $n$ to the East
(right). [For examples see the end of \S5 and elsewhere.]
\par
\assert Lemma \ref(3.2)
{For any sequence $[S_n]$ and integers $n$ and $m\ge 0$, we have
$S_{m-1,n} \ne 0$ and $S_{m,n} = 0$ just when there is a proper linear
relation of minimum order $m$ spanning at least $S_{n-m},\ldots,S_{n+m}$.
Its coefficients $J_i$ are unique up to a common factor. Further, when
$$S_{m,n} = S_{m,n+1} = \ldots = S_{m,n+g-1} = 0\hbox{\quad and\quad }
S_{m,n-1}\ne 0,\ S_{m,n+g} \ne 0$$ the relation maximally spans
$S_{n-m},\ldots,S_{n+m+g-1}$.
[Notice that we may have $n=-\infty$ or $g=+\infty$.]}
\par
\Proof: by elementary linear algebra. For $g = 1$, set up $m+1$ homogeneous
linear equations for the $J_i$, with a unique solution when they have rank $m$:
$$\eqalign{S_{n-m}J_0\ +\ S_{n-m+1}J_1\ +\ \ldots\ +\ S_{n}J_m\ &=\ 0,\cr
\vdots\cr
S_{n}J_0\ +\ S_{n+1}J_1\ +\ \ldots\ +\ S_{n+m}J_m\ &=\ 0,\cr
\vdots\cr
S_{n+g-1}J_0\ +\ S_{n+g}J_1\ +\ \ldots\ +\ S_{n+m+g-1}J_m\ &=\ 0.\cr}$$
Using $S_{n-m+1},\ldots,S_{n+m+1}$ on the right-hand side instead of
$S_{n-m},\ldots,S_{n+m}$ leaves $m$ of these equations unaltered, so by
induction on $g$ the solution is constant over the whole segment of $[S_n]$
of length $2m+g$, and no further.
This solution is proper: for if $J_m = 0$ there would be a nontrivial solution
to the equations with $m$ replaced by $m-1$, and so we should have
$S_{m-1,n} = 0$ contrary to hypothesis; similarly if $J_0 = 0$. Similarly,
it is minimal. Conversely, if a there is a relation, then $S_{m,n} = 0$;
if it is minimal, then it is unique, and if it is also proper then $m$ cannot
be reduced, so $S_{m-1,n} \ne 0$. \QED
\par
\assert Corollary \ref(3.3)
{$[S_n]$ is an LFSR sequence of order $r$ if and only if row $r$ (and
all subsequent rows) of its number-wall degenerate to the zero sequence,
but row $r-1$ does not.}
\par
Given as many terms as we require of an LFSR sequence $[S_n]$,
we can use \ref(3.3) to compute its order $r$ from its number-wall.
Now suppose in addition we require to find the linear relation $J({\bf E})$
which generates it. We introduce a new sequence of polynomials in a
transcendental X over the domain, defined by
$$U_n(X)\ =\ ({\bf E} - X)S_n\ =\ S_{n+1} - X.S_n,$$
and form its number wall $U_{m,n}(X)$. If we set $X\to {\bf E}$, both sequence
and
wall (for $m\ne -1$) perforce degenerate to all zeros; therefore each
$U_{m,n}({\bf E})$ is a relation spanning those $2m+2$ elements of $[S_n]$ from
which it was computed.
Now for degree $r$ there is only one such polynomial (modulo a constant factor),
and that is the required minimal relation $J({\bf E})$:
for all $n$ therefore, $U_{r-1,n}$ equals $J(X)$ multiplied by some domain
element (nonzero since setting $X\to 0$ gives the wall for $[S_n]$
itself); and similarly $U_{r-1,n} = 0$ on all subsequent rows $m\ge r$.
\par
\assert Corollary \ref(3.4)
{$[S_n]$ is an LFSR sequence of order $r$ if and only if row $r$
(and all subsequent rows) of the number-wall of $S_{n+1} - X.S_n$
degenerate to the zero sequence, but row $r$ does not; then row $r-1$
equals the minimal relation $J(X)$ of $[S_n]$ times a geometric
sequence over the ground domain.}
This algorithm is slower than the more sophisticated Berlekamp-Massey method
\ref(12.1), taking time of order $r^4$ arithmetic operations over the ground
domain (using straightforward polynomial multiplication) rather than $r^2$;
but it is noticeably easier to justify, and it also gives the relations of
intermediate (odd) spans.
\par
A simple recursive rule for constructing the number-wall of a given sequence
in the absence of zeros is classical, and follows immediately from the
pivotal condensation rule styled by \fer[Ioh82] \S1.2 the
{\sl Sylvester Identity} [described by \fer[Ait62] \S45 as an
{\sl extensional} identity due to Jacobi, and elsewhere credited to
Desnanot, Dodgson or Frobenius]:
\par
\assert Lemma \ref(3.5)
{Given an $m\times m$ matrix $[F_{ij}]$ and an arbitrary $(m-k)\times(m-k)$
minor $[G_{ij}]$ where $0\le k\le m$, define $H_{ij}$ to be the cofactor
in $|F|$ selecting all the rows and columns of $|G|$,
together with the $i$-th row and $j$-th column not in $|G|$.
Then $$|F_{ij}|\ \times\ |G_{ij}|^{k-1}\ =\ |H_{ij}|.$$}
\par
\Proof: We may suppose the elements of $[F_{ij}]$ to be distinct
variables transcendental over the ground domain, thus avoiding any problem with
singular matrices. We may also suppose the rows and columns of $[F_{ij}]$
permuted so that $[G_{ij}]$ occupies the SE corner, $i,j > k$: this
leaves the determinant unaltered except for a possible change of sign. % ??
Consider the matrix $[E_{ij}]$ with $E_{ij}$ being $F_{ij}$ when $i > k$,
or $|G|$ bordered by row $i$ and column $j$ of $F$ when $i\le k$.
Expanding this determinant by its first row, we see (with some difficulty ---
the reader is advised to work through a small example) that
$$E_{ij}\ =\ |G|F_{ij}\ +\ \sum_q A_{iq}F_{iq},$$
where the $A_{iq}$ are cofactors from the last $m-k$ rows which do not depend
on $j$. So $[E_{ij}]$ is effectively $[F_{ij}]$ with each of its first $k$
rows multiplied by $|G|$, then subjected to a sequence of elementary column
operations which leave the determinant unaltered. On the one hand then,
$|E| = |F|\times|G|^k$.
\par
Again,
$$E_{ij}\ =\ \cases{
H_{ij} &for $1\le i\le k$ and $1\le j\le k$ by definition,\cr
G_{ij} &for $k* 0$,}\cr
&\qquad\qquad\hbox{provided $S_{m-2,n} \ne 0$.}\cr}$$}
[The initial row of zeros is not a great deal of use at this point, but comes
in useful later as an {\sl outer frame} for zeros occurring in the sequence.]
\par
The possibility of zero elements in the wall is a stumbling block to
the use of \ref(3.7) for its computation, particularly if the ground domain
happens to be a small finite field, when they are almost certain to occur.
The next result sharpens a classical one in the study of Pad\'e Tables \S11,
the first half of the `Pad\'e Block Theorem'. All proofs of it (including
this author's) should be regarded with suspicion, having a disconcerting
tendency to resort to hand-waving at some crucial point in the proceedings:
for this reason we feel regretfully unable to recommend a prior version.
\par
A {\sl region} of a number wall is defined to be a simply-connected subset
of elements, where two elements are {\sl connected} when they have one
subscript ($m$ or $n$) equal, the other ($n$ or $m$) differing by unity.
The regions which we consider are $g\times g'$ {\sl rectangles}, having at most
four boundary segments along each of which some subscript is constant;
their {\sl lengths} $g, g'$ (measured in numbers of elements along each segment)
may range from zero to infinity.
The {\sl inner frame} of a rectangle is the smallest connected set which
disconnects the region from its complement: it normally comprises four
edges and four corners. The {\sl outer frame} similarly disconnects the
union of the rectangle with its inner frame from the complement.
[In the example at the end of \S5 will be found a $4\times 4$ (square) rectangle
of zeros, with an inner frame of ones.]
\par
\assert Theorem \ref(3.8) {Square Window Theorem:
Zero elements $S_{m,n} = 0$ of a number-wall occur only within
{\sl zero-windows}, that is square $g\times g$ regions with nonzero inner
frames. The nullity of (the matrix corresponding to)
a zero element equals its distance $h$ from the inner frame.}
\par
\Proof: To start with, by \ref(3.6) if $S_{m-1,n} = S_{m,n-1} = 0$ then
$S_{m,n} = 0$, and by \ref(3.6) shifting $m\leftarrow m-1, n\leftarrow n-1$,
similarly $S_{m-1,n-1} = 0$; the mirror-image argument yields the converse.
Now by an easy induction, any connected region of zeros must be a
(possibly infinite) rectangle.
\par
Now let there be such a rectangle with $g$ rows, $g'$ columns, and NW
corner ($n$ increasing to the East and $m$ to the South) located at $S_{m,n}$:
in detail,
$$\eqalign {S_{m,n} = 0,\ \ldots,\ S_{m,n+g'-1} = 0;\cr
S_{m,n} = 0,\ \ldots,\ S_{m+g-1,n} = 0,\cr
S_{m,n+g'-1} = 0,\ \ldots,\ S_{m+g-1,n+g'-1} = 0,\cr
S_{m+g-1,n} = 0,\ \ldots,\ S_{m+g-1,n+g'-1} = 0,\cr
S_{m-1,n} \ne 0,\ \ldots,\ S_{m-1,n+g'} \ne 0;\cr
S_{m,n} \ne 0,\ \ldots,\ S_{m+g,n} \ne 0;\cr
S_{m,n+g'} \ne 0,\ \ldots,\ S_{m+g,n+g'} \ne 0;\cr
S_{m+g,n} \ne 0,\ \ldots,\ S_{m+g,n+g'} \ne 0.\cr}$$
Then by \ref(3.2) a unique minimal relation $J({\bf E})$ of order $m$ spans
$S_{n-m}, \ldots, S_{n+m+g-1}$. Suppose $g' > g$: then the relation
${\bf E}^{g}J$ of order $m+g$ spans $S_{n-m-g}, \ldots, S_{n+m+g}$,
so by \ref(3.2) $S_{m+g,n} = 0$, contrary to hypothesis.
Suppose $g' < g$: then since $S_{m+g',n} = 0$, there is a relation spanning
$S_{n-m-g'}, \ldots, S_{n+m+g'}$; also since $S_{m+g'-1,n-1}\ne 0$ is a
nonzero minor of $S_{m+g',n}$, the latter has nullity 1 and the relation
must therefore be unique. One such relation is simply ${\bf E}^{g'}J$:
so $J$ spans $S_{n-m+g'}, \ldots, S_{n+m+g'}$ and
by \ref(3.2) $S_{m,n+g'} = 0$, contrary to hypothesis. The only possibility
remaining is that $g' = g$, and the rectangle must be a square.
\par
Consider this square divided by its diagonals $i-j = m-n$ and $i+j = m+n+g-1$
into North, East, South, West quarters; let $h$ denote the distance of the
element $S_{i,j}$ from the frame in the same quarter.
All the elements in the North quarter have rank $m$, since the only
relations spanning subintervals of $S_{n-m}, \ldots, S_{n+m+g-1}$ are
(polynomial) multiples of $J$ itself: in particular, if $g$ is odd, the central
element has rank $m$ and nullity $h = [(g+1)/2]$. If $g$ is even, there are
four elements at the centre, the North pair having rank $m$ and nullity $h$ as
before; the South pair have rank $m+1$, since (for example) any relation
corresponding to $S_{m+g/2, n+g/2-1}$ spans $S_{m-n-1},\ldots,S_{n+m+g/2}$,
but $S_{m-n-1}$ lies outside the span of $J$ (the relations are multiples of
${\bf E}J$). So for any $g$ the central elements have nullity equal to their
distance $h$ from the frame.
Now observe that the nullity of any element $S_{i,j}$ can only differ
from that of its neighbors $S_{i-1,j},S_{i,j-1},S_{i,j+1},S_{i+1,j}$ by at
most unity, since the matrices differ essentially by a single row or column.
Therefore it must decrease with $h$ in all directions, in order to reach zero
with $h$ at the inner frame where all elements are nonzero. \QED
\par
A simple consequence of \ref(3.8) is the occurrence of `prime windows'
in a wall over some larger ground domain:
\assert Corollary \ref(3.9) {Elements divisible by some prime ideal $P$ clump
together in square regions, elements at distance $h$ from the frame being
divisible by (at least) $P^h$.}
In particular, these windows are noticeable for ordinary primes $p$ in integer
walls.
\par
A less obvious but more useful and rather elegant consequence, credited to
Massey in \fer[Cha82], quantifies the notion that, if two different sequences
have a large common portion, then at least one of them has high linear order.
It could be proved directly by linear dependence arguments.
\assert Corollary \ref(3.10) {Massey's Lemma:
The sum of the orders of proper relations spanning two intervals of a sequence
exceeds the length of the intersection, unless each relation spans their union.}
\Proof:
Let the intervals $(a_i,b_i)$ of the sequence be spanned maximally
by minimal proper relations of orders $r_i$, for $i = 1,2$.
By \ref(3.2), \ref(3.8) there are corresponding windows in the number-wall
at $(m_i,n_i)$ of size $g_i$ where
$a_i = n_i - m_i$, $b_i = n_i + m_i + g_i - 1$, so
$$m_i = r_i,\quad n_i = a_i + r_i,\quad g_i = b_i - a_i - 2r_i + 1.$$
Suppose the windows to be distinct (failing which their parameters coincide
in pairs); since they are square and cannot overlap, one of the following is
true:
$$m_1+g_1 < m_2,\quad n_1+g_1 < n_2,\quad m_2+g_2 < m_1,\quad n_2+g_2 < n_1.$$
Substituting, either
$$\cases{
b_1 - a_1 - r_1 + 1 < r_2 &or\cr
b_1 - r_1 + 1 < a_2 + r_2 &or\cr
b_2 - a_2 - r_2 + 1 < r_1 &or\cr
b_2 - r_2 + 1 < a_1 + r_1 &\cr
}$$
whence
$$r_1 + r_2\ >\ 1 + \min(b_1-a_1, b_1-a_2, b_2-a_2, b_2-a_1).$$
as claimed.
\par
Relaxing the maximality constraint on the intervals and the minimality on
the order does not affect the result. \QED
\delete{
\assert Theorem (3.0)
{Let $S^1,S^2$ be FSR sequences of (minimum) orders $r_1,r_2$, such that
$S^1_n = S^2_n$ maximally for $1 \le n \le l$.
Then either $S^1_n = S^2_n$ for all $n$ or $r_1 + r_2 > l$; that is, either
$l = \infty$ or the sum of their orders exceeds the length of their
common segment.}
\Proof: Let $S^1,S^2$ have minimal relations $J^1,J^2$ of orders $r_1,r_2$
resp., where (without loss of generality) $r_1 \le r_2$.
Suppose $r_1 + r_2 \le l$, that is $r_2 \le l - r_1$:
Then the minimality of $J^1$ assures us that the elements of the common span
give $r_1$ independent simultaneous linear equations in the coefficients of
$K$, so the solution space of these equations has dimension $r_2 - r_1$.
Now a subspace of these solutions comprises the polynomial multiples of $J^1$
of degree $r_2$: this also has dimension $r_2 - r_1$, so constitutes the whole
space. Therefore $J^2$ must be a multiple of $J^1$; $S^1,S^2$ both satisfy
$J^2$, both have the same $r_2$ initial elements, and must be identical. \QED
}
% Theorem 5 in [Cha82], attr. to Massey; no proof or citation,
% maybe [Mas69] on BCH decoding and B-M algorithm.
\par
As an illustration, suppose we are to find the order and relation spanning
$$S\ =\ [0,0,0,1,16,170,1520,12411,96096,719860,\ldots].$$
The following pair of number-walls can be computed via (3.6):
The final row of zeros of the first suggests \ref(3.3) that the order might
be $r = 4$. The final row of the second gives \ref(3.4) the auxiliary
polynomial $J\ =\ {\bf E}^4-16{\bf E}^3+86{\bf E}^2-176{\bf E}+105\ = \ 0$,
that is $S$ satisfies the relation
$$S_{n+4}-16S_{n+3}+86S_{n+2}-176S_{n+1}+105S_n\ =\ 0.$$
$$\hbox{\vbox{\offinterlineskip\hrule
\halign{\vrule#&\strut\quad\hfil$#$&\quad\vrule#
&\strut\quad\hfil$#$&\strut\quad\hfil$#$&\strut\quad\hfil$#$
&\strut\quad\hfil$#$&\strut\quad\hfil$#$&\strut\quad\hfil$#$
&\strut\quad\hfil$#$&\strut\quad\hfil$#$&\strut\quad\hfil$#$
&\strut\quad\hfil$#$&\quad\vrule#\cr
&&&&&&&&&&&&&\cr
&{m\backslash n} &&0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &\cr
&&&&&&&&&&&&&\cr
\noalign{\hrule}
&&&&&&&&&&&&&\cr
&{-2}&&0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &\cr
&{-1}&&1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &\cr
&0 &&0 &0 &0 &1 &16 &170 &1520 &12411 &96096 &719860 &\cr
&1 &&0 &0 &0 &1 &86 &4580 &200530 &7967001 &300258756 &&\cr
&2 &&0 &0 &0 &1 &176 &21946 &2449616 &262848811 &&&\cr
&3 &&&&&1 &105 &11025 &115762 &&&&\cr
&4 &&&&&&0 &0 &&&&&\cr
&&&&&&&&&&&&&\cr
}\hrule}}$$
$$\hbox{\vbox{
\offinterlineskip\hrule
\halign{\vrule\ #
&\strut\hfil$\scriptstyle#$
&\strut\hfil$\scriptstyle#$
&\strut\hfil$\scriptstyle#$
&\strut\hfil$\scriptstyle#$
&\strut\hfil$\scriptstyle#$
&\strut\hfil$\scriptstyle#$
&\strut\hfil$\scriptstyle#$&\ \vrule#\cr
&&&&&&&&\cr
&0&0&0&0&0&0&0&\cr
&1&1&1&1&1&1&1&\cr
&0&0&1&16-X&170-16X&1520-170X&12411-1520X&\cr
&0&0&1&86-16X+X^2&4580-1200X+86X^2&200530-59824X+4580X^2&&\cr
&&&1&176-86X+16X^2-X^3&21946-13456X+2711X^2-176X^3&&&\cr
&&&&105-176X+86X^2-16X^3+X^4&&&&\cr
&&&&&&&&\cr
}\hrule}}$$
\par
\beginsection 4. The Frame Formulae
\par
We are now ready to tackle the central undertaking of this investigation:
the elucidation of conditions on the number-wall elements of the inner and
outer frames surrounding a zero-window, permitting the
recursive rule \ref(3.7) to be completed. The results to be proved
are as follows, the adjacent diagram illustrating the notation employed, to be
explained in more detail as we proceed.
\figure {Diagram} {Window Notation}
{$$\matrix{
& &E_0 &E_1 &E_2 &\ldots &E_k &\ldots&E_g &E_{g+1} &
&\cr
&F_0 &B,A_0 &A_1 &A_2 &\ldots &A_k &\ldots&A_g &A,C_{g+1}
&G_{g+1}&\cr
&F_1 &B_1 &{\bf 0}&{\bf 0}&\ldots &{\bf 0}&\ldots&{\bf 0}&C_g
&G_g &\cr
&F_2 &B_2 &{\bf 0}&\ddots &(P) &\rightarrow & &\vdots
&\vdots &\vdots &\cr
&\vdots &\vdots &\vdots &(Q) &\ddots& &\uparrow &{\bf 0}&C_k
&G_k &\cr
&F_k &B_k &{\bf 0}&\downarrow & &\ddots&(R) &\vdots&\vdots
&\vdots &\cr
&\vdots &\vdots &\vdots & &\leftarrow &(T) &\ddots&{\bf 0}&C_2
&G_2 &\cr
&F_g &B_g &{\bf 0}&\ldots &{\bf 0}&\ldots&{\bf 0}&{\bf 0}&C_1
&G_1 &\cr
&F_{g+1}&B,D_{g+1} &D_g &\ldots &D_k &\ldots&D_2 &D_1 &D,C_0 &G_0
&\cr
& &H_{g+1} &H_g &\ldots &H_k &\ldots&H_2 &H_1 &H_0 &
&\cr
}$$}
\par
\assert Theorem \ref(4.1) {Frame Ratio Theorem:
The inner frame of a $g\times g$ zero-window comprises four geometric
sequences, along the North, West, East, South edges, with ratios $P,Q,R,T$
resp., and origins at the NW and SE corners. They satisfy
$$PT/QR\ =\ (-)^g;$$}
\assert Corollary \ref(4.2) {Inner Frame Theorem:
The inner frame sequences $A_k,B_k,C_k,D_k$ satisfy
$$A_kD_k/B_kC_k\ =\ (-)^{gk} \quad\hbox{for $0\le k \le g+1$};$$}
\assert Theorem \ref(4.3) {Outer Frame Theorem:
The outer frame sequences $E_k,F_k,G_k,H_k$ lie immediately outside
$A_k,B_k,C_k,D_k$ resp., and are aligned with them. They satisfy the relation:
For $g\ge 0$, $0\le k\le g+1$,
$$QE_k/A_k\ +\ (-)^k PF_k/B_k\ =\ RH_k/D_k\ +\ (-)^k TG_k/C_k.$$}
\par
The method of proof is straightforward in principle: unfortunately, the details
are somewhat involved. Suppose we are given an {\sl original} sequence $[S_n]$
with elements in some given ground domain, such that the number wall
displays a $g\times g$ zero-window with NW corner $S_{m,n}$.
We proceed to modify one element by adding a
transcendental $$S_{n+m+g-1}\ \leftarrow\ S_{n+m+g-1} + (-)^m X,$$
yielding a {\sl perturbed} sequence over the domain extended to formal power
series, whose (perturbed) wall has only a $(g-1)\times(g-1)$ zero-square at
the same location.
\par
Now assuming the exact result for the smaller zero-window over the extension,
we proceed to prove it by induction for the perturbed wall, then
finally let $X\to 0$ [i.e. specialize to FLS coefficient of $X^0$].
To avoid unnecessarily complicating an already quite sufficiently involved
notation, we do not explicitly distinguish between the original and perturbed
quantities; but claims referring to the latter are styled {\sl Lemma} rather
than {\sl Theorem}, and explicitly involve $X$.
We make heavy implicit use of our ${\cal O}(X^k)$ notation and rules \ref(1.1).
\par
Here we digress to emphasize that, for this induction to take effect,
the perturbed configuration must itself constitute the number wall of some
actual sequence; the importance of this will subsequently be underlined by
a counterexample \ref(5.4).
Failure to respect this principle fatally compromised at least one earlier
attempted proof of an essentially equivalent result --- credited to Gilewicz
and Froissart in \fer[Gil78] --- where the postulated configuration of four
perturbed inner edges, each linear in the perturbing variable, can be seen by
\ref(4.5) to be impossible.
[It is intriguing to speculate how such a strategy might have come to be
preferred over that adopted here. A partial explanation may lie in the
various other pitfalls awaiting us below, which shall duly be paraded for
the reader's edification.]
\par
%------------------------------------------------------------------------------%
\figure {Diagram} {Perturbed Window Notation}
{%\advance\hsize by -\dimen0 %diagram too wide
$$\matrix{
& &E_0 &E_1 &E_2 &\ldots &E_k &\ldots&\ldots&E_g &E_{g+1}
& &\cr
&F_0 &B,A_0 &A_1 &A_2 &\ldots &A_k &\ldots&\ldots&A_g
&A,C_{g+1} &G_{g+1}&\cr
&F_1 &B_1 &{\bf 0}&{\bf 0}&\ldots &{\bf 0}&\ldots&{\bf 0}&M_g &C_g
&G_g &\cr
&F_2 &B_2 &{\bf 0}&\ddots &(P) &\rightarrow & &\vdots&\vdots
&\vdots &\vdots &\cr
&\vdots &\vdots &\vdots &(Q) &\ddots& &\uparrow &{\bf 0}&M_k
&C_k &G_k &\cr
&F_k &B_k &{\bf 0}&\downarrow & &\ddots&(R)
&\vdots&\vdots&\vdots &\vdots &\cr
&\vdots &\vdots &\vdots & &\leftarrow &(T) &\ddots&\vdots&\vdots
&\vdots &\vdots &\cr
&\vdots &\vdots &{\bf 0}&\ldots &{\bf 0}&\ldots&\ldots&{\bf 0}&M_2 &C_2
&G_2 &\cr
&F_g &B_g &N_g &\ldots &N_k &\ldots&\ldots&N_2 &N,M_1 &C_1
&G_1 &\cr
&F_{g+1}&B,D_{g+1} &D_g &\ldots &D_k &\ldots&\ldots&D_2 &D_1 &D,C_0
&G_0 &\cr
& &H_{g+1} &H_g &\ldots &H_k &\ldots&\ldots&H_2 &H_1 &H_0
& &\cr
}$$}
\par
%------------------------------------------------------------------------------%
The perturbed window is illustrated in the accompanying Diagram, representing
a region within the perturbed wall, for some sequence which is not shown.
Below and on the counter diagonal, all perturbed elements are polynomial
(finite FLS); above it, they remain as original. The original zero-window had
inner frame comprising $A,B,C,D$ and outer frame $E,F,G,H$ on its
North, West, East, South sides; the perturbed window has inner frame $M,N$
(where originally there were zeros) and outer frame $C,D$ on its East, South.
The frame vectors are of length $g+2$ (original) or $g+1$ (perturbed),
indexed from 0: the origin of North frame vectors is on column $n-1$,
of West on row $m-1$ ($A_0$ and $B_0$ are identical), of East on row $m+g$,
and of South on column $n+g$ ($C_0$ and $D_0$ are identical).
It will emerge that $A,B,C,D,M,N$ are approximately geometric sequences
\ref(4.5) -- \ref(4.7), their ratios denoted by $A_1/A_0 = P,Q,R,T,U,V$
respectively.
\vfill\eject
\par
\assert Lemma \ref(4.5)
{There are elements $U,V$ such that for $1\le k\le g+1$,
$$\eqalign{&M_k\ =\ A_gU^{k-g-1},\quad N_k\ =\ B_gV^{k-g-1};\cr
\quad\hbox{in fact,}\quad &U\ =\ P/X,\quad V\ =\ (-)^{g-1}Q/X.\cr}$$}
\Proof: By definition \ref(3.1)
$$\eqalign{M_g\ &=\ \left|\matrix{S_{n+g-1}&\ldots&S_{n+g+m-1}+(-)^mX\cr
\vdots&\ddots&\vdots\cr
S_{n+g-m-1}&\ldots&S_{n+g-1}\cr}\right|\cr
&\ \cr% all I want is a smallskip
&=\ \left|\matrix{S_{n+g-2}&\ldots&S_{n+g+m-3}\cr
\vdots&\ddots&\vdots\cr
S_{n+g-m-1}&\ldots&S_{n+g-2}\cr}\right|X
\ +\ \left|\matrix{S_{n+g-1}&\ldots&S_{n+g+m-1}\cr
\vdots&\ddots&\vdots\cr
S_{n+g-m-1}&\ldots&S_{n+g-1}\cr}\right|,\cr}$$
expanding the determinant;
$$\ =\ A_{g-1}X\ +\ 0$$
in terms of the original wall. Also $M_{g+1} \equiv A_g$, so we can define
$$U\ =\ M_{g+1}/M_g\ =\ A_g/A_{g-1}X,\quad\hbox{or}\quad U\ =\ P/X.$$
For $N,V,Q$ the only difference is that the determinant is order $m+g-1$;
notice that we can use the same $X$ in both contexts, by \ref(3.8).
Finally, for $1\le k\le g-1$, by \ref(3.6), $M_{k+1}{}^2=M_{k+2}M_{k}$,
showing that $[M_k]$ is geometric with ratio $U$; similarly for $N$.
\QED
\assert Lemma \ref(4.6)
{There are elements $P,Q$ such that for $0\le k\le g+1$,
$$A_k\ =\ A_0P^k\ +\ {\cal O}(X),\quad B_k\ =\ B_0Q^k\ +\ {\cal O}(X).$$}
\Proof: For $0\le k\le g$, see the end of the proof of \ref(4.5) with
$P = A_1/A_0$, $Q = B_1/B_0$.
For $k=g+1$, using \ref(3.6) and \ref(4.6) [$A$ is exactly geometric for
$k < g+1$], we have
$$A_{g+1}\ =\ (A_g{}^2-E_gM_g)/A_{g-1}\ =\ A_0P^{g+1}-E_gX.$$
$B$ behaves similarly. \QED
\par
It is important to bear in mind that we may always divide by elements of the
inner frame or by ratios, since we know these to be nonzero; indeed the same
is true of $C$ and $D$, even in the perturbed case \ref(4.7). And when
multiplying or dividing FLSs \ref(1.1), we need to ascertain that the
factors have order sufficiently large to justify the order claimed for the
error in their product: $E,F,G,H$ are always ${\cal O}(1)$ at worst; $A,B,C,D$
and $P,Q,R,T$ are ${\cal O}(1)$ exactly; but $U,V$ are ${\cal O}(1/X)$.
\par
Notice here too that the `ratios' $R,T$ of the approximately geometric outer
frames are defined explicitly by $C_1/C_0,D_1/D_0$, rather than retaining their
original values,
an apparently insignificant detail which is central to the proof: it allows
us to get an unexpectedly small and explicit first perturbation term in the
expansions \ref(4.7) of $C,D$, without which the crucial information carried
by the perturbation term in the proof of the central result \ref(4.9) would
be swamped by noise of order ${\cal O}(X)$.
\par
\assert Lemma \ref(4.7)
{There are elements $R,T$ such that for $2\le k\le g+1$,
$$\eqalign{C_k\ &=\ C_0R^k\ -\ (R/P)^{g-k+3}G_{k-1}X^{g-k+2}\ +\ {\cal
O}(X^{g-k+3}),\cr
D_k\ &=\ D_0T^k\ -\ (-)^{(g-1)k} (T/Q)^{g-k+3}H_{k-1}X^{g-k+2}\ +\ {\cal
O}(X^{g-k+3}).\cr}$$}
\Proof: By induction on $k$.
For $k = 1$ we have $C_1 = C_0 R$ exactly by definition; the Lemma fails
here, but still $C_1 = C_0 R + {\cal O}(X^{g+1})$ as required to commence the
induction. For $2 \le k \le g+1$,
$$\eqalign{C_k\ &=\ C_{k-2}{}^{-1}(C_{k-1}{}^2 - M_{k-1}G_{k-1})
\quad\hbox{by \ref(3.6),}\cr
\ &=\ C_0{}^{-1}R^{2-k} (C_0{}^2R^{2k-2}\ -\ A_g(X/P)^{g-k+2}G_{k-1})
\ +\ {\cal O}(X^{g-k+3}),\cr}$$
by \ref(4.5) and hypothesis or definition;
now we get the result since by \ref(4.6) and the previous line
$$C_0{}^{-1}A_g\ =\ \bigl(C_{g+1}{}^{-1}R^{g+1} + {\cal O}(X)\bigr)
\bigl(A_{g+1}P^{-1} + {\cal O}(X)\bigr)\ =\ R^{g+1}/P + {\cal O}(X).$$
$D_k$ is treated similarly. \QED
\par
We proceed to the perturbed forms of the Frame Ratio and Outer Frame Theorems.
%Lemma \ref(4.8) may seem a tad indirect, on the grounds that its
%proof can actually be interpreted as directly establishing the original
%Theorem \ref(4.1) for size $g-1$;
%the excuse is that it will be needed later in perturbed form.
The form of Lemma \ref(4.9) demands some explanation. As explained earlier,
the sequence and its wall have been perturbed so that the window of size $g$
has shrunk to size $g-1$, and the natural approach would seem to be simply
to apply the original Outer Frame Theorem \ref(4.3) to compute
the perturbed row $D$ inductively, then find $H$ immediately by \ref(3.6) as
$H_k = (D_k{}^2 - D_{k-1}D_{k+1})/N_k$:
the idea is illustrated towards the end of \S13.
\par
There are several reasons why this program fails in a formal context.
To begin with, finding one $H_k$ would require three elements from $D$, which in
turn involve three from $E$ and $F$, rather than the single one demanded by the
Theorem \ref(4.3) to be proved.
Then we should need to divide by $N_k = {\cal O}(X^{g-1-k})$ by \ref(4.5):
this implies that all terms of smaller order in the numerator must cancel,
so requires pre-evaluation of this many terms of the polynomials $D_k$.
Finally similar reasons demands the polynomials $C_k$, which would have to
be calculated in some unrelated fashion, since we have only one equation
connecting $E,F,C,D$: to wit \ref(4.3) with $C,D$ playing the part of $G,H$ etc.
[It is a fairly safe bet that \ref(4.3) is the only condition possible
on the outer frame elements, since
by manipulating the original sequence, we can arrange for $E$,$F$,$G$ to take
arbitrary values. Consequential alterations to the inner frame, being fixed by
just four elements $A_0,P,Q,R$, have little influence on this situation.]
\par
\assert Lemma \ref(4.8)
{$$PT/QR\ =\ (-)^g\ +\ {\cal O}(X^{g+1}).$$}
\Proof: By \ref(4.5), $QU/PV = (-)^{g-1}$ (avoiding induction on $g$);
and using \ref(4.5) with $k=2$ and \ref(4.7) with $k=g$
(both of which in fact need no error term)
$$\eqalign{N_2/M_2\ &=\ B_gV^{1-g}/A_gU^{1-g}\cr
&=\ A_0P^g(X/P)^{g-1}/B_0Q^g(X/Q)^{g-1}(-)^{(g-1)^2}\ =\ V/U,\cr}$$
noting that $A_0 = B_0$ and $(g-1)^2$, $(g-1)$ have the same parity;
also by \ref(4.7) $$C_1/D_1\ =\ C_0R/D_0T\ =\ R/T.$$
Collecting,
$$\eqalign{QR/PT\ &=\ (QU/PV)(V/U)(R/T)\ =\ (-)^g N_2C_1/M_2D_1\cr
&=\ (-)^g (-M_2D_1+M_1^2)/M_2D_1\quad\hbox{by \ref(3.6)}\cr
&=\ -(-)^g +{\cal O}(X^{g+1})\quad\hbox{by \ref(4.5). \QED}\cr}$$
\par
\assert Lemma \ref(4.9) {For $g\ge 0$, $0\le k\le g+1$,
$$QE_k/A_k\ +\ (-)^k PF_k/B_k\ =\ RH_k/D_k\ +\ (-)^k TG_k/C_k + {\cal O}(X)
$$}
\Proof\ in cases $k = 0, g+1$:
By \ref(3.6) and definition of $P,Q,R,T$,
$$A_0{}^2\ =\ B_1E_0 + A_1F_0\ =\ A_0QE_0 + A_0PF_0,$$
whence $A_0{}^{-1}(QE_0\ +\ PF_0) \ =\ 1$; similarly
$C_0{}^{-1}(RH_0\ +\ TG_0) \ =\ 1$. Also $A_0 = B_0$ and $C_0 = D_0$,
which proves case $k=0$; case $k=g+1$ is similar.
\par
\noindent\Proof\ in cases $1 \le k \le g$:
For $g=0$ there are no (further) cases to consider. For $g\ge 1$, we assume
\ref(4.9), replacing $g$ by $g-1$ for the induction;
$C_k$, $D_k$, $G_k$, $H_k$ by $M_{k+1}$, $N_{k+1}$, $C_{k+1}$, $D_{k+1}$,
noticing the shift in origin caused by the new SE corner; $R$, $T$ by
$U$, $V$; and letting $X\to 0$. Then by inductive hypothesis
$$\eqalign{&Q.E_k/A_k\ +\ (-)^k P.F_k/B_k\cr
&\quad=\ U.D_{k+1}/N_{k+1}\ +\ (-)^k V.C_{k+1}/M_{k+1}\cr
&\quad=\ (P/X) (-)^{(g+1)k} B_g{}^{-1} (X/Q)^{k-g} D_{k+1}\cr
&\qquad\ +\ (-)^{k+g+1} (Q/X) A_g{}^{-1} (X/P)^{k-g} C_{k+1} \ +\ {\cal O}(X)
\quad\hbox{by \ref(4.5)}\cr
&\quad=\ Y + Z + {\cal O}(X^{g-k+2}) \ +\ {\cal O}(X),\quad\hbox{say.}\cr}$$
At this point we expand $C,D$ by \ref(4.7) and separate them into
main $Y$, first perturbation $Z$ and residual error terms.
The main terms cancel to order $X$, as expected:
$$\eqalign{&Y = X^{k-g-1}(-)^{g+k+1} \bigl( (-)^{gk+g+1} D_0 B_g{}^{-1} Q^{-g}
(T/Q)^k PT\ +\ C_0 A_g{}^{-1} P^{-g} (R/P)^k QR \bigr)\cr
&\quad=\ X^{k-g-1}(-)^{g+k+1} A_0C_0 \bigl( (-)^{gk+g+1} (T/Q)^k PT + (R/P)^k
QR \bigr)\cr
&\qquad\hbox{since $B_g Q^{-g} = B_0 = A_0 = A_g P^{-g}$, $D_0 = C_0$;}\cr
&\quad=\ X^{k-g-1}(-)^{g+k+1} A_0C_0 (R/P)^k QR ( -1 + 1 )\ +\ {\cal
O}(X^{g+1})\cr
&\qquad\hbox{since $T/Q = (-)^g R/P + O(X^{g+1})$, $PT = (-)^g QR\ +\ {\cal
O}(X^{g+1})$ by \ref(4.8);}\cr
&\quad=\ {\cal O}(X^{k}).\cr}$$
The first perturbation terms incorporate the desired right-hand side:
$$\eqalign{&Z = (-)^{g+k} \bigl( (-)^k B_g{}^{-1} P Q^{-2} T^{g-k+2} H_k
\ +\ A_g{}^{-1} P^{-2} Q R^{g-k+2} G_k \bigr)\cr
&\qquad\hbox{simplifying --- the exponents of X cancel exactly;}\cr
&\quad=\ (-)^{g+k} \bigl( (-)^k (PT/QR) RH_k/D_k + (QR/PT) TG_k/C_k \bigr)\ +\
{\cal O}(X)\cr
&\qquad\hbox{since $A_g P R^{g-k+1} = C_k\ +\ {\cal O}(X)$ etc by \ref(4.6)
then \ref(4.7) with $k = g+1$;}\cr
&\quad=\ RH_k/D_k\ +\ (-)^k TG_k/C_k\ +\ {\cal O}(X)\quad\hbox{by
\ref(4.8)}.\cr}$$
Collecting $Y$, $Z$, etc and
checking that the error terms are all ${\cal O}(X)$ now gives the result. \QED
\par
Finally, setting $X \to 0$ in \ref(4.8) and \ref(4.9), we are home and dry
in the original wall: \ref(4.1) and \ref(4.3) are immediate, and \ref(4.2)
is a simple consequence of \ref(4.8), \ref(4.6), \ref(4.7). However, notice
that this last step is only possible because specialization commutes with
arithmetic \ref(1.0).
\par
\beginsection 5. The Algorithm, Special Cases
\par
By isolating $T$, $D_k$ and $H_k$ on the left-hand side of the Frame Theorems,
we immediately get a comprehensive and efficient recursion for computing the
number-wall by induction on rows $m$:
\assert Corollary \ref(5.1)
{If $m \le 0$ or $S_{m-2,n} \ne 0$ use \ref(3.7);
otherwise, determine whether $S_{m,n}$, with respect to the zero-window
immediately to the North, lies within:\hfil\break
(i) the interior, when by \ref(4.1)
$$S_{m,n} = 0 \quad\hbox{and}\quad T\ =\ (-)^g QR/P;$$
(ii) the inner frame, when by \ref(4.2)
$$S_{m,n}\ \equiv\ D_k\ =\ (-)^{gk} B_k C_k/A_k;$$
(iii) the outer frame, when by \ref(4.3)
$$S_{m,n}\ \equiv\ H_k\ =\ (D_k/R)(QE_k/A_k + (-1)^k(PF_k/B_k - TC_k/M_k)).$$}
%$$\eqalign{
%T\ &=\ (-)^g QR/P\cr
%D_k\ &=\ (-)^{gk} C_k B_k/A_k\cr
%H_k\ &=\ (D_k/R)(QE_k/A_k + (-1)^k(PF_k/B_k - TC_k/M_k))\cr}$$
Illustrative examples are given later in this section.
\par
In principle the original Sylvester recursion \ref(3.6) might be dispensed with,
since the Frame Theorems hold even for $g = k = 0$; but in practice it is
impossible to avoid programming the latter as a special case anyway,
so the saving is only conceptual.
[To quote Alf van der Poorten \fer[Poo96]: In theory, there is no difference
between theory and practice. In practice, it doesn't quite work that way.]
\par
The special case $g = k = 1$ can be recast in the simplified form:
\assert Corollary \ref(5.2) {In the notation of the attached figure depicting
a portion of the number-wall,
for an isolated zero at $W$ we have $ED^2 + HA^2 = FC^2 + GB^2$;}
this follows directly by setting $W = 0$ in the (polynomial) identity:
\assert Lemma \ref(5.3) {In the notation of the attached figure
$$ED^2 + HA^2 - W(EH+AD)\ =\ FC^2 + GB^2 - W(FG+BC).$$}
$$\matrix{&&E&&\cr &L&A&K\cr F&B&W&C&G\cr &N&D&M&\cr &&H&&\cr}$$
\Proof: Suppose $W$ transcendental over the ground domain of $[S_n]$
[strictly, $W$ is some not-identically-vanishing function of transcendental
$X$, such as $W = LX$ where $L \ne 0$ and $X$ is the perturbation of $[S_n]$
in the proof of \ref(4.5)].
Expanding $LK\cdot NM = LN\cdot KM$ via \ref(3.6) then rearranging,
$$(A^2-EW)(D^2-HW)\ =\ (B^2-FW)(C^2-GW),$$
$$(BC+AD)(AD-BC)\ + \ W(FC^2+GB^2-ED^2-HA^2)\ +\ W^2(EH-FG)\ =\ 0.$$
Again using \ref(3.6), substituting for $BC+AD\ =\ W^2$, canceling $W$
and rearranging gives the desired equation.
We can now argue, as in the proof of \ref(3.5), that for fixed $m$ this is a
polynomial identity in elements of a sequence $[S_n]$ of distinct
transcendentals, so it remains true even when some of the constituent
elements such as $W$ take zero values. Alternatively, in the spirit of \S7,
we can examine each possible pattern of zeros individually, and resolve it
by applying \ref(3.8), \ref(4.2) for various $g\le 3$. \QED
\par
[The above approach is noteworthy by reason of its beguiling unreliability:
not only does equation \ref(5.2) possess more symmetry than the general
Outer Frame Theorem --- obstructing attempts to guess the latter ---
but we have so far been unable to construct an analogous identity for the
the $g = 2$ case, even though already in possession of \ref(4.3). The
analytically motivated proof technique conceals a pitfall, on which
we now dilate.]
We have been careful throughout to ensure that every table considered is
actually the valid number wall of some sequence. To emphasize that this is
not merely some pedantic logical conceit, we give a simple example to
illustrate the consequences of abandoning this restriction during a proof,
irrelevant though it might be to the initial formulation of a conjecture.
\par
Consider the portion of a number wall shown (diagram left), where
the NW zero is $S_{mn}$, say, and the three zeros are all isolated.
$$\matrix{&.&.&E&.&.&\cr &.&.&.&A&.&\cr &F&.&{\bf 0}&Y&{\bf 0}&\cr
&.&B&Z&X&.&\cr &.&.&{\bf 0}&.&.&\cr}\qquad
\matrix{&.&.&E&.&.&\cr &.&.&.&A&.&\cr &F&.&{\bf 0}&{\bf 0}&{\bf 0}&\cr
&.&B&{\bf 0}&{\bf 0}&{\bf 0}&\cr &.&.&{\bf 0}&{\bf 0}&{\bf 0}&\cr}\qquad
\matrix{&.&.&E&.&.&\cr &.&.&.&A&.&\cr
&{\bf 0}&{\bf 0}&{\bf 0}&{\bf 0}&{\bf 0}&\cr
&{\bf 0}&{\bf 0}&{\bf 0}&{\bf 0}&{\bf 0}&\cr
&{\bf 0}&{\bf 0}&{\bf 0}&{\bf 0}&{\bf 0}&\cr }$$
By \ref(5.2) and \ref(3.6) we have $FY^2 = EZ^2$ and $Y^2 = AX$,
$Z^2 = BX$; substituting the latter into the former gives $EBX = FAX$,
from which we cancel $X$ to get $EB = FA$. Letting $X \to 0$, by \ref(3.8)
$Y,Z \to 0$ also, leaving a $3\times3$ window (diagram centre) for which we
have established the engagingly succinct
\assert Canard \ref(5.4) {Fool's Frame Theorem: In the notation of the diagram,
there is reason to believe that $$EB\ =\ FA.$$}
\par
Sadly, the attached period 6 wall over $\Z$, where $A = E = 1$, $F = 2$,
$B = 4$, offers little comfort to anyone disposed to give this credence.
$$\matrix{&0&0&0&0&0&0&0&0&0&\cr
&1&1&1&1&1&1&1&1&1&\cr
&-1&-1&1&1&1&1&1&-1&-1&\cr
&2&2&2&0&0&0&2&2&2&\cr
&4&0&4&0&0&0&4&0&4&\cr
&8&-8&8&0&0&0&8&-8&8&\cr
&16&-16&16&-16&16&-16&16&-16&16&\cr
&0&0&0&0&0&0&0&0&0&\cr}$$
What went wrong? We could just shrug and say `where's the sequence?'; but
for the sake of explaining the phenomenon a little more convincingly,
let us temporarily abandon the formal algebraic context and restrict the wall
to some continuous ground domain such as $\R$, in particular interpreting
$X \to 0$ as the familiar limit operator.
\par
By \ref(3.2), if $Z \ne 0$ then there is a proper relation of order $m+2$
spanning $S_{n-m-2}, ..., S_{n+m+2}$; and if $A \ne 0$, $Y = 0$, there is
a proper relation of order $m$ spanning $S_{n-m}, ..., S_{n+m+2}$. Then as
$X \to 0$, by continuity both claims become true. The sum of the orders is
$2m+2$ and the length of the intersection is $2m+3$, so by a minor abuse of
\ref(3.10) the two relations must be identical. Hence the limiting
configuration is actually a window of size $5\times5$ with NW corner
at $S_{m,n-2}$ (diagram right): in particular, $F = B = 0$, and \ref(5.4) is
actually true for the subset of number walls to which we have inadvertently
restricted ourselves --- it's just not very interesting.
\par
A second interesting special case of the Frame Theorems occurs when the
ground domain is the binary field $\F_2$:
The frame ratios $P,Q,R,S$ and inner frames
$A,B,C,D$ are nonzero, so they must all be unity, and the algorithm reduces to
\assert Corollary \ref(5.5) {Over the binary field, $S_{m,n} = 0$ in the
interior of a window, $S_{m,n} = 1$ along its inner frame,
and $S_{m,n} \equiv H_k = E_k + F_k + G_k\pmod 2$ along its outer frame.}
\par
We illustrate \ref(5.5) with a rather more extensive example of a number-wall.
$[S_n]$ is the minimal order binary deBruijn sequence (see \S9) with period
$[1 1 1 1 0 0 0 0 1 1 0 1 0 0 1 0]$, and binary wall as in the Diagram
(periodic horizontally, zero above and below vertically):
\figure {Diagram} {Binary Wall}
{$$\hfil\vbox{\halign{\hfil{\tt#}\quad&{\tt#}\cr
m$\backslash$n& 0 1 2 3 4 5 6 7 8 9101112131415 \cr
-2& 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \cr
-1& 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 \cr
0& 1 1 1 1 0 0 0 0 1 1 0 1 0 0 1 0 \cr
1& 1 0 0 1 0 0 0 0 1 1 1 1 0 0 1 1 \cr
2& 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 \cr
3& 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 \cr
4& 1 0 0 1 1 1 1 1 1 0 1 1 1 1 0 0 \cr
5& 1 0 0 1 0 1 0 0 1 1 1 1 0 1 1 1 \cr
6& 1 1 1 1 1 1 0 0 1 0 0 1 1 1 1 0 \cr
7& 1 0 0 0 0 1 1 1 1 0 0 1 1 0 1 1 \cr
8& 1 0 0 0 0 1 0 0 1 1 1 1 1 1 1 0 \cr
9& 1 0 0 0 0 1 0 0 1 1 1 0 0 1 1 1 \cr
10& 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 1 \cr
11& 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 \cr
12& 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \cr
}}$$}
\par
For example, assuming rows $m < 7$ already to hand, we can immediately complete
the $4\times 4$ window of zeros with NW corner at $(m,n) = (7,1)$, together with
its inner frame of ones. Once rows $m<12$ are to hand, we can
find element $(12,0)$ by \ref(3.7),
then element $(12,1)$ by \ref(5.5) with $k = 4$,
$E = S_{5,4} = 0$, $F = S_{10,15} = 1$, $G = S_{7,6} = 1$,
$H = S_{12,1} = 0+1+1 = 0\ \qmod 2$.
The final row of zeros shows that the order over the binary domain is $r = 12$.
\vfill\eject
\par
If instead we regard $[S_n]$ as defined over the integers, the following wall
results.
To find element $(10,7)$ from previous rows we can employ \ref(5.2) with
$A,B,C,D\ =\ 3,6,3,-6$ and $E,F,G = -2,1,1$, getting
$$H\ =\ (FC^2 + GB^2 - ED^2)/A^2\ =\ (1.9+1.36+2.36)/9\ =\ 13.$$
To find find our way around the window at $(0,4)$ with $g = 4$ demands the full
works: happily $P = Q = R = 1$ so $T = 1$ by \ref(4.1), $A = B = C = 1$ so
$D = 1$ by \ref(4.2), and we find say element $(5,7)$ by \ref(4.3) with
$k = 1$ and $E,F,G = 0,1,3$, $H = (QE/A - PF/B + TG/C)D/R = 2$. The order
over the integer domain is $r = 13$.
\figure {Diagram} {Integer Wall}
{$$\matrix{
m\backslash n&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\cr
-2&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\cr
-1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\cr
0&1&1&1&1&0&0&0&0&1&1&0&1&0&0&1&0\cr
1&1&0&0&1&0&0&0&0&1&1&-1&1&0&0&1&-1\cr
2&1&0&0&1&0&0&0&0&1&2&1&1&1&1&1&1\cr
3&1&1&1&1&0&0&0&0&1&3&1&0&-1&-1&0&0\cr
4&1&2&2&1&1&1&1&1&1&4&1&1&1&1&0&0\cr
5&1&2&2&-1&0&1&-2&2&-3&5&-3&1&0&-1&1&-1\cr
6&3&1&3&1&1&1&2&-2&-1&4&4&1&1&1&3&4\cr
7&5&-4&4&2&0&-1&-3&3&-3&4&-4&-3&-1&2&5&-7\cr
8&-1&-4&8&4&2&1&6&0&3&1&7&5&7&9&13&6\cr
9&5&-6&20&0&-8&11&-12&-6&-3&-5&-11&8&-4&-5&23&-7\cr
10&17&16&50&40&32&25&35&13&-7&-8&23&4&8&13&38&-11\cr
11&93&99&93&51&-3&-45&-75&-69&-51&-45&-51&-21&-3&27&69&75\cr
12&72&72&72&72&72&72&72&72&72&72&72&72&72&72&72&72\cr
13&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\cr
}$$}
\par
Finally, it is natural to ask is whether a simple recursive algorithm exists
for number walls over more general ground rings, in particular over
$\Z/q\Z$ for $q$ an arbitrary natural number. [The obvious approach,
to compute the wall over $\Z$ and then reduce $\qmod q$, is less than
ideal since the intermediate integers may be very large.]
If $q = \prod_k p_k{}^{e_k}$ is expressed as a product of prime powers,
the residue $\qmod q$ can be computed easily from residues $\qmod{p^e}$
via the Chinese Remainder Theorem \fer[Dav88] \S{}A.5.1, reducing the problem
to the case $q = p^e$. By \ref(3.8), the power of $p$
(or in general, any prime ideal) dividing an element at distance $h$ from the
frame within a zero-window $\qmod p$ must be at least $p^h$, and one might
na\"\i{}vely hope that perhaps it might be exactly $p^h$ (it needn't);
or failing that, the frames might behave in a fashion which generalizes the
situation modulo $p$, involving the excess over $p^h$ near a particular point
on the frame. However, it is easy to construct a wall modulo $q = 4$ with
a large window $\qmod 2$ which is also perfectly square $\qmod 4$, but for
which the outer frame sum $E+F+G+H$ varies irregularly between $0$ and
$2\ \qmod 4$ --- strongly suggesting that the hope is unjustified.
[However some progress in this area has been made --- see \fer[Ree85].]
\par
\beginsection 6. General Symmetric Walls
\par
We now need no longer rely on the determinant approach \ref(3.1) to define
the number-wall, but may generate it instead by placing an arbitrary pair of
sequences
$[T_n], [S_n]$ on rows $m = -1,0$ --- subject to zero-windows \ref(3.8),
and supplemented where necessary by consistent frame data around such windows
--- then employing frame recursion \ref(5.1) for $m > 0$, and by reflection for
$m < -1$.
The unexpected square-tiling symmetry of the new definition is noteworthy:
Since neither $m$ nor $n$ appears explicitly, we have invariance under 2-D
translations; furthermore, despite an apparent asymmetry of \ref(3.1) between
$m$ and $n$, \ref(4.1) -- \ref(4.3) are invariant under reflection in diagonals
of the window, and under half-turn about its centre.
[This last is rather less mysterious when viewed in the context of Pad\'e
tables \S11, where it arises directly from the fact that the reciprocal
transpose of the Pad\'e table for $F(X)$ is the table for $1/F(X)$.]
To distinguish the new wall from the {\sl special number wall} (SNW) of
\ref(3.1) etc, we refer to it as a {\sl general symmetric wall} (GSW).
[It must be admitted that at the moment this construction, as was memorably
observed of an entirely different subject, fills a much-needed gap.]
\par
The elements of a GSW are plainly rational functions in the elements from
which they are generated; and it seems reasonable to suppose that they should
possess some explicit characterization, analogous to \ref(3.1) defining the SNW.
Such an expression would undoubtedly be immediately useful (see below),
but at present we have in lieu only the following partial result, initially
communicated to us by Jim Propp as a corollary of a more general combinatorial
expression in \fer[Rob86].
\assert Theorem \ref(6.1) {For $m \ge 1$,
the general element $S_{m,n}$ of a GSW constructed (via \ref(3.7))
from sequences of variables $S_{-1,n} = U_n$ and $S_{0,n} = V_n$ is of the form
$S_{m,n}\ =\ W_{m,n}/Z_{m,n}$, where $W_{m,n}$ is an irreducible polynomial
of total degree (at most) $2(m^2-m+1)$ in the assorted variables, and $Z_{m,n}$
is (a factor of) the degree $m^2 + (m-1)^2$ monomial
$$Z_{m,n}\ =\ \prod_{k=1-m}^{k=m-1} U_{n+k}{}^{m-|k|} V_{n+k}{}^{m-1-|k|}.$$}
For $m < 0$, immediately by symmetry
$$S_{m,n}(\ldots,U_k,\ldots,V_k,\ldots)\ =\
S_{-1-m,n}(\ldots,V_k,\ldots,U_k,\ldots).$$
\Proof: Notice that in the setting of a GSW, both $m$ and $n$ subscripts
may be arbitrarily translated; so without loss of generality, we may
represent an arbitrary element $S_{m,n}$ by $S_{4,4}$. By \ref(3.6),
$$S_{44}\ =\ (S_{34}^2 - S_{33} S_{35}) / S_{24}. \eqno \ref(6.2)$$
Also, substituting for the $S_{3,j}$,
$$S_{44}\ =\ \bigl(S_{24}^2 - S_{23} S_{25})^2 / S_{14}^2 -
(S_{23}^2 - S_{22} S_{24}) (S_{25}^2 - S_{24} S_{26})
/ S_{13} S_{15}\bigr) / S_{24}.$$
Most of the terms in the numerator of the right-hand side above
have a factor $S_{24}$, the exceptions simplifying to
$$ - S_{23} S_{25}^2 (S_{14}^2 - S_{13} S_{15}) / S_{13} S_{14}^2 S_{15} S_{24}
\ =\ - S_{04} S_{23} S_{25}^2 S_{24} / S_{13} S_{14}^2 S_{15} S_{24}$$
using \ref(3.6); so $S_{24}$ cancels completely from the denominator, giving
$$S_{44}\ =\ {S_{13} S_{15} S_{24}^3 - 2 S_{13} S_{15} S_{23} S_{24} S_{25} -
S_{14}^2 S_{22} S_{24} S_{26} + S_{14}^2 S_{23}^2 S_{26} +
S_{14}^2 S_{22} S_{25}^2 - S_{04} S_{23}^2 S_{25}^2
\over S_{13} S_{14}^2 S_{15}}. \eqno \ref(6.3)$$
\par
We proceed by induction on $m$: elementary computation as above establishes
\ref(6.1) for $m = 1,2$. For $m > 2$, translating \ref(6.2) and \ref(6.3) from
$S_{4,4}$ to $S_{m,n}$, we see $S_{m,n}$
must be of the form \ref(6.1), possibly divided by some factor of the HCF of
$W_{m-2,n}$ and $W_{m-3,n}^2 W_{m-3,n-1} W_{m-3,n+1}$. However, we show below
that $W_{i,j}$ is an irreducible polynomial in the $U_k$ and $V_k$, so this HCF
is unity, and $S_{m,n}$ is also of the form \ref(6.1) as required.
\par
To establish the irreducibility of $W_{m,n}$, we consider first the special
number wall of a transcendental sequence $[V_k]$, i.e. $U_k = 1$ for all $k$.
Notice that any factor of a homogeneous polynomial must also be homogeneous,
since the product of two polynomials with minimum total degree $a,c$ and
maximum $b,d$ resp. necessarily contains terms of degrees $a+c$ and $b+d$.
Fixing say $n = m$, by \ref(3.1)
$$S_{m,m}\ =\ \left|\matrix{
V_m&\ldots&V_{2m}\cr \vdots&\ddots&\vdots\cr V_0&\ldots&V_m\cr}\right|.$$
$V_{2m}$ has cofactor $S_{m-1,m-1}$, which by assumption is irreducible. So
if $S_{m,m}$ factorizes properly, it has a linear factor containing $V_{2m}$;
and the other factor must equal $S_{m-1,m-1}$, which does not contain
$V_m{}^m$. So their product does not contain $V_m{}^{m+1}$, and cannot be
$S_{m,m}$: thus in the special number wall of a sequence of distinct
transcendentals,
$S_{m,m}$ and by translation $S_{m,n}$ is an irreducible polynomial.
\par
Now consider the GSW. If $W_{m,n}$ factorizes properly, it has a factor
containing no $V_k$ elements (otherwise we could specialize to a factorization
for the special wall above). By an easy induction using \ref(3.6), $W_{m,n}$
contains just one term which is a multiple of $V_n{}^{m+1}$: specifically,
$Z_{m,n} V_n{}^{m+1}/U_n^m$.
So any factor can only be a monomial which (partially) cancels with the
denominator as given above, and what remains of the numerator is irreducible.
\QED
\par
A more refined induction ought to show that not even monomial cancellation can
occur above; hence that the polynomial degrees and the form of $Z_{m,n}$
given in \ref(6.1) are exact, and indeed that
the total degree of $W_{m,n}$ in the $U_{k}$, $V_{k}$ separately is
uniformly $m(m-1)$, $m(m-1)+2$ resp. Moreover we conjecture that the sum of
the absolute values of the coefficients of $W_{m,n}$ is $2^{m(m+1)/2}$. This
last quantity --- essentially the number of terms in the $m$-th row of a
polynomial GSW --- is uncomfortably large: for example,
$W_{4,n}$ is a polynomial of about $30,000$ terms, each of degree $26$.
\par
A referee has made the point that we have inadvertently introduced not one
but two generalizations here.
Given sequences $[T_n], [S_n]$ over the ground domain, firstly we
generate the `numerical' GSW $S_{m,n}$ via recursion \ref(5.1);
secondly we substitute them for $[U_n], [V_n]$ in the formal GSW \ref(6.1).
[It is assumed both $[T_n], [S_n]$ everywhere nonzero, ensuring
both that \ref(3.8) holds initially --- without which no \ref(5.1)) ---
and that the denominators $Z_{m,n}$ are nonzero in \ref(6.1).]
Now, are the two walls equal? If we had an explicit expression for the GSW
element, we might consider adapting the Frame Theorem proof to incorporate it.
Failing that, we can at least observe that they are surely equal if either wall
is everywhere nonzero, since algorithms \ref(3.7) and \ref(5.1) are then
equivalent;
and again, they are equal if $[T_n], [S_n]$ happen to be a pair of adjacent
rows (or indeed columns) from some pukka SNW, by the existing Frame Theorem.
\par
Now any given GSW element depends on only a finite subset of $[T_n], [S_n]$.
We might therefore seek to show that every finite region of the GSW may be
embedded in some SNW, generated by some sequence $[R_n]$ say (dependent on
the region).
[The region may be taken to be a (square) diamond, with base on the row $[T_n]$
and apices at some target element and its reflection in the base].
In specific instances, this embedding is straightforward to verify:
the equations for $[R_n]$ turn out to be linear in $[T_n], [S_n]$, and
it appears sufficient to consider $[R_n]$ of period at most thrice the diameter.
However, a general proof is complicated by the fact that any
fixed scheme of equations may be rendered singular by some zero within
the region, in spite of the fact that in practice such zero-windows make
a specific problem easier to solve.
\par
We turn to another question posed by Propp, the statement and solution
of which exemplify the geometric nature of the number wall.
It concerns the extent to which
the frame rules might be in some covert fashion {\sl local,} in the sense
that the value of an element is independent on those outside some bounded
neighborhood. Specifically he asks: given arbitrarily large $k$,
do there exist two distinct walls with $k$ (or more, but only finitely many)
consecutive rows in common?
Such questions as what ground domain is specified, whether horizontal
and/or vertical translations are to be regarded as differences in this context,
and whether the wall is special, can be postponed; we shall see that the
answer turns out to satisfy the most stringent of such conditions.
\par
Consider an arbitrary relation $J$ of order $r$ with leading and trailing
coefficients equal to unity, with $[S_n]$ satisfying $S_1 = \ldots = S_{r-1}
= 0$ and $S_r = 1$ (the so-called {\sl impulse response sequence} or IRS), and
having period $q$; then define
$$T_n\ =\ \cases{S_n &if $r \le n \le q$;\cr
0 &otherwise.\cr}$$
Then the wall for $T$ is easily seen to be of form diagrammed,
where $Z_g$ denotes a $g\times g$ window (with inner frame unity),
$R$ denotes the $(r+1)\times (q-r+1)$ rectangular region comprising one period
of the wall for $[S_n]$ but excluding its initial $Z_{r-1}$, and $R'$ denotes
the reflection of $R$ about a horizontal line.
Now replace the original relation $J$ by any other relation satisfying
the same restrictions: all rows meeting the interior of $R$ or $R'$ will in
general be altered, whereas those meeting the finite windows must remain the
same. So the wall generated satisfies Propp's conditions with $k = q-r+1$.
\par
Incidentally, there is a sense in which the `real' wall here is actually just
the finite rectangle $R$; we make this manifest by repositioning the
inner frames of the infinite windows, so that there are instead four
half-infinite frames spiraling away in the same sense (as in the next example)
from the corners of $R$, which is now isolated at the centre.
The result is easily verified to be a GSW.
\par
%
% Z
% oo
% --------------------------------------------------------------
% |//////////////////|
% |/////// ////////|
% |/////// R ////////|
% |/////// ////////|
% |//////////////////|
% Z |------------------| Z
% oo | | oo
% | |
% | Z |
% | q-r-1 |
% | |
% |------------------|
% |//////////////////|
% |/////// ////////|
% |/////// R'////////|
% |/////// ////////|
% |//////////////////|
% |------------------|
% .
% .
% .
%
\def\horiz{\leaders\hrule\hfil}
\figure {Diagram} {Generalized Wall}
{$$\hbox{\vbox{\offinterlineskip
\halign{&#&#&#&#&#&#\cr
&\hfil&\hfil&\hfil$Z_{\infty}$\hfil&\hfil&\hfil&\cr
&\hfil&\hfil&\strut\hfil&\hfil&\hfil&\cr
&\horiz&\horiz&\horiz&\horiz&\horiz&\cr
%&\hfil&\vrule\hfil//////&//////&//////\hfil\vrule&\hfil&\cr
&\hfil&\vrule\hfil//////&\hfil&//////\hfil\vrule&\hfil&\cr
&\hskip 1in&\vrule\hfil//////&\hfil$R$\hfil&//////\hfil\vrule&\hskip 1in&\cr
&\hfil&\vrule\hfil//////&\hfil&//////\hfil\vrule&\hfil&\cr
%&\hfil&\vrule\hfil//////&//////&//////\hfil\vrule&\hfil&\cr
&\hfil&\horiz&\horiz&\horiz&\hfil&\cr
&\hfil&\vrule\hfil&\strut\hfil&\hfil\vrule&\hfil&\cr
&\hfil&\vrule\hfil&\strut\hfil&\hfil\vrule&\hfil&\cr
&\hfil&\vrule\hfil&\strut\hfil&\hfil\vrule&\hfil&\cr
&\hfil$Z_{\infty}$\hfil&\vrule\hfil&\hfil$Z_{q-r-1}\hfil$&\hfil\vrule&\hfil$Z_{\
infty}$\hfil&\cr
&\hfil&\vrule\hfil&\strut\hfil&\hfil\vrule&\hfil&\cr
&\hfil&\vrule\hfil&\strut\hfil&\hfil\vrule&\hfil&\cr
&\hfil&\vrule\hfil&\strut\hfil&\hfil\vrule&\hfil&\cr
&\hfil&\vrule\horiz&\horiz&\horiz\vrule&\hfil&\cr
%&\hfil&\vrule\hfil//////&//////&//////\hfil\vrule&\hfil&\cr
&\hfil&\vrule\hfil//////&\hfil&//////\hfil\vrule&\hfil&\cr
&\hfil&\vrule\hfil//////&\hfil$R'$\hfil&//////\hfil\vrule&\hfil&\cr
&\hfil&\vrule\hfil//////&\hfil&//////\hfil\vrule&\hfil&\cr
%&\hfil&\vrule\hfil//////&//////&//////\hfil\vrule&\hfil&\cr
&\hfil&\horiz&\horiz&\horiz&\hfil&\cr
&\hfil&\vrule\hfil&\strut\hfil&\hfil\vrule&\hfil&\cr
&\hfil&\hfil&\hfil\vdots\hfil&\hfil&\hfil&\cr
}}}$$}
\par
[For the remainder of this section we assume the ground domain is binary.]
The simplest examples of these GSW's occur when $R$ is itself a single
$g\times g$ window, surrounded by four infinite windows.
This is the special case $h = \infty$ of what one might call a `bathroom wall':
an offset tiling of windows of sizes $g+1$ and $h+1$
(note the increase in size resulting from the frame),
where $0 \le g < h \le \infty$.
Another important example, the case $g = 0, h = 1$ is the unique binary wall
with minimum density $(1/5)$ of zeros; it consists of the pattern below,
replicated on a tiling of squares.
\par
$$\hfil\vbox{\halign {\tt #\cr
0 1 1 1 1 \cr
1 1 0 1 1 \cr
1 1 1 1 0 \cr
1 0 1 1 1 \cr
1 1 1 0 1 \cr}}\hfil$$
\par
Finally, an entertaining problem is suggested by the observation that
there are binary GSW's with isolated rectangular regions, and also with
isolated square windows: are there any with nontrivial isolated squares,
i.e. possessing some interior structure? The answer is a little surprising:
there is essentially just one, as follows.
The relation
$$J\ =\ ({\bf E}+1)({\bf E}^3+{\bf E}+1)^2
\ =\ {\bf E}^7+{\bf E}^6+{\bf E}^3+{\bf E}^2+{\bf E}+1,$$
has IRS period comprising a block of $r-1$ zeros followed by the
coefficients of $J$ itself (because $J(X)J(1/X) = X^r + X^{-r}$):
$$S_n\ =\ [\ldots,0,0,0,0,0,0,1,1,1,1,0,0,1,1,\ldots],$$
and $r = 7, q = 14$ in the earlier notation.
The wall (illustrated below) of the modified sequence
$$T_n\ =\ [...,0,0,0,0,0,0,1,1,1,1,0,0,1,1,0,0,0,0,0,0,...],$$
manipulated as above, is essentially an isolated 8x8 square $R$ which is not a
$6\times 6$ window; it has four symmetries generated by quarter-turns,
and the only other solution is its reflection $R'$.
\par
%
% 0 0 1 0 0 0 0 0 0 0 0 0 |
% 0 0 1 0 0 0 0 0 0 0 0 0 |
% 0 0 1 1 1 1 1 1 1 1 1 1 |__________________
% 0 0 1 1 0 0 1 1 1 1 0 0 |_| |_|_|_|
% 0 0 1 1 0 0 1 0 0 1 0 0 |_| | |
% 0 0 1 1 1 1 1 0 0 1 0 0 |_|_____| |
% 0 0 1 0 0 1 1 1 1 1 0 0 | |_|_____|
% 0 0 1 0 0 1 0 0 1 1 0 0 | | |_|
% 0 0 1 1 1 1 0 0 1 1 0 0 |_____| |_|
% 1 1 1 1 1 1 1 1 1 1 0 0 ____|_|_|_|_____|_|
% 0 0 0 0 0 0 0 0 0 1 0 0 |
% 0 0 0 0 0 0 0 0 0 1 0 0 |
%
\def\hori{\vbox{\hrule width12pt}\hfil}
\def\vert{\vrule height12pt\llap\hfil}
\figure {Diagram} {Isolated Square Wall}
{$$\hfil\vbox{\halign {\tt #\cr
0 0 1 0 0 0 0 0 0 0 0 0 \cr
0 0 1 0 0 0 0 0 0 0 0 0 \cr
0 0 1 1 1 1 1 1 1 1 1 1 \cr
0 0 1 1 0 0 1 1 1 1 0 0 \cr
0 0 1 1 0 0 1 0 0 1 0 0 \cr
0 0 1 1 1 1 1 0 0 1 0 0 \cr
0 0 1 0 0 1 1 1 1 1 0 0 \cr
0 0 1 0 0 1 0 0 1 1 0 0 \cr
0 0 1 1 1 1 0 0 1 1 0 0 \cr
1 1 1 1 1 1 1 1 1 1 0 0 \cr
0 0 0 0 0 0 0 0 0 1 0 0 \cr
0 0 0 0 0 0 0 0 0 1 0 0 \cr
}}
\qquad
\vbox{\offinterlineskip
\halign{&#&#&#&#&#&#&#&#&#&#&#&#\cr
&\hfil&\hfil&\vert&\hfil&\hfil&\hfil&\hfil&\hfil&\hfil&\hfil&\hfil&\cr
&\hfil&\hfil&\vert\hori&\hori&\hori&\hori&\hori&\hori&\hori&\hori&\hori&\cr
&\hfil&\hfil&\vert\hori&\vert&\hfil&\hfil&\vert\hori&\vert\hori&\vert\hori&\vert
&\hfil&\cr
&\hfil&\hfil&\vert\hori&\vert&\hfil&\hfil&\vert&\hfil&\hfil&\vert&\hfil&\cr
&\hfil&\hfil&\vert\hori&\vert\hori&\hori&\hori&\vert&\hfil&\hfil&\vert&\hfil&\cr
&\hfil&\hfil&\vert&\hfil&\hfil&\vert\hori&\vert\hori&\hori&\hori&\vert&\hfil&\cr
&\hfil&\hfil&\vert&\hfil&\hfil&\vert&\hfil&\hfil&\vert\hori&\vert&\hfil&\cr
&\hfil&\hfil&\vert\hori&\hori&\hori&\vert&\hfil&\hfil&\vert\hori&\vert&\hfil&\cr
&\hori&\hori&\vert\hori&\vert\hori&\vert\hori&\vert\hori&\hori&\hori&\vert\hori&
\vert&\hfil&\cr
&\hfil&\hfil&\hfil&\hfil&\hfil&\hfil&\hfil&\hfil&\hfil&\vert&\hfil&\cr
&\hfil&\hfil&\hfil&\hfil&\hfil&\hfil&\hfil&\hfil&\hfil&\vert&\hfil&\cr
}}\hfil$$}
\par
The uniqueness is a matter of constructing all binary polynomials with
period twice their order, a straightforward exercise in finite field theory.
As the diagram suggests, it can be regarded geometrically as a question of
packing a square with smaller squares, with side-conditions
equivalent to \ref(5.5), which does not look too easy combinatorially!
\par
\beginsection 7. Performance and the FSSP
\par
For a number-wall of length and depth $N$, the complexity of a
straightforward implementation of the
number-wall algorithm as described above is easily seen to be of order
$N^2$ space and $N^3$ time (assuming arithmetic operations to be of constant
complexity); an extra factor of $N$ arises in both requirements
from the necessity to locate the frame of the current zero-window,
which may itself be of size $N$. [The time could be improved simply by storing
the origin and size of the window above for each element of the current row,
at the cost of storing three rows of integers.]
\par
It is possible to reduce the complexity to order $N$ space and $N^2$ time,
at least in the binary case,
by `hard-wiring' the algorithm as a {\sl Cellular Finite-State Automaton}
(C-A; see \fer[Min67]).
Briefly, the C-A stores the current row $m$ of the wall, each cell $n$
holding the value of a single binary determinant $S_{m,n}$ (in practice,
two copies of the array are required, for old and new values of the state).
The state is a 44-valued product comprising 2 bits for left and right-shifting
buffers for the outer frames of the current zero-window, and 11 states for a
slightly modified Firing-Squad Synchronization Problem machine (FSSP; see
\fer[Maz86]) to locate the South edge of the inner frame.
\par
[It would take us too far afield to go into detail about the FSSP. Briefly,
imagine a squad of identical soldiers, each equipped with his own gun and with
a (synchronized) clock marking instants of time; between instants a soldier
assumes any one of an initially determined set of states.
At each instant the state of a soldier changes to a new value, completely
determined by his own previous state and those of his two nearest neighbors.
There are $g$ soldiers in the line, but none of them knows the value of $g$.
Initially, the whole squad is {\sl Quiescent}; but at some random instant the
leftmost soldier assumes the {\sl Command} state. The problem is to train the
squad identically so that at some instant ($2g-1$ after the command is in
general the minimum achievable) they will all for the first time simultaneously
assume the {\sl Firing} state.]
\par
In the notation of the Frame Theorems (\S4 figure),
each cell picks up $E$ from the North of the window, then shifts it rightward
until it hits the East frame, where $G$ is added in, after which $E+G$ is
sent leftward. In the meantime $F$ from the West is shifted rightward until
the two collide on the South frame, where they are added to give $H$.
The FSSP is started by
commands in both North corners of the window simultaneously, so that it fires
after $g$ steps rather than $2g$; sadly, this means we cannot employ Mazoyer's
beautiful asymmetric 6-state solution \fer[Maz87], although we could use
Balzer's symmetric 8-state solution to reduce the state total to 40.
The transition table for the binary C-A is only 85 Kbyte, and it is quite
stunningly fast: a single 3-D array lookup for each determinant computed.
Because of the localization of the data, on a massively parallel machine the
complexity improves to order $N$ time and space.
\par
The C-A method can in principle be generalized to ground field $\Z_p$,
but implementation seems to demand on the order of $p^5$ states,
so is unlikely to be feasible for $p > 3$.
A more practical approach is to retain the FSSP synchronization and the
technique of shifting frame values right or left till they bounce off the
frame of the window, but abandon any attempt to do arithmetic in the
control structure: the values of the frame elements are simply shifted
separately, each inner or outer edge having its own row of shifting buffers
($A,E$ need two each, but their rightward buffers can be shared with $B,F$).
The arithmetic for the South frame is all performed explicitly when the FSSP
fires. This requires around ten one-dimensional arrays to implement,
and retains the order $N$ space and $N^2$ time complexity of the C-A,
as well as its potential for parallelization.
\par
The Frame algorithm \ref(5.1), including the binary C-A variant, has been
implemented in C-language as part of a sophisticated application program
running on a Sun SPARC workstation, incorporating a graphical front-end
allowing large segments (up to one million elements) of a number-wall to be
viewed in color-coding. At a more modest level, there is available a
pedagogic Maple implementation of most of the algorithms described here,
designed for the examples shown here.
\par
\beginsection 8. Interpolation and Vandermonde Matrices
\par
In the next three sections we turn to a distinct but closely related problem,
which receives surprisingly little attention in standard texts:
the efficient computation of the explicit form of $S_n$ for an LFSR sequence
$[S_n]$ from its relation and/or from (a sufficiency of) its terms.
The first two sections summarize and dilate upon standard material required
for the third.
\par
We denote by $\sigma_i(X_1,\ldots,X_r)$ the elementary symmetric function of
degree $i$ on $r$ variables $X_i$, and recall the well-known
\assert Lemma \ref(8.1)
{The polynomial equation with roots $X = X_1,\ldots,X_r$
$$J(X)\ =\ \prod_k (X-X_k)\ =\ \sum_i J_i X^i$$
has coefficients given by $J_i = (-)^{r-i}\sigma_{r-i}((X_1,\ldots,X_r))$.}
\par
For development and analysis of algorithmic efficiency, we need to make the
point that all the `defective' symmetric functions
$\sigma_i(\ldots,X_{\ne k},\ldots)$ --- that is, on $r-1$ variables
excluding $X_k$ --- can be computed efficiently in order $r^2$ time by
first employing and then reversing the usual inductive algorithm:
\assert Algorithm \ref(8.2)
{Initially for $i = 0$, $k = 0,1,\ldots,r$ set $\sigma_0(X_1,\ldots,X_{k}) =
1$;\hfil\break
for $k = 0$, $i = 1,\ldots,r$ set $\sigma_i() = 0$;\hfil\break
for $k = 1,2,\ldots,r$ set
$$\eqalign{\sigma_0(X_1,\ldots,X_k)\ &=\ 1,\cr
\sigma_{i+1}(X_1,\ldots,X_k)\ &=\ \sigma_{i+1}(X_1,\ldots,X_{k-1}) + X_k
\sigma_i(X_1,\ldots,X_{k-1});\cr}$$
then for $k = 1,2,\ldots,r$ set
$$\eqalign{\sigma_0(\ldots,X_{\ne k},\ldots)\ &=\ 1,\cr
\sigma_{i+1}(\ldots,X_{\ne k},\ldots)\ &=\ \sigma_{i+1}(X_1,\ldots,X_r) - X_k
\sigma_i(\ldots,X_{\ne k},\ldots).
\cr}$$}
\par
From now on we shall assume that the $[X_i]$ are {\sl distinct}, that is
either they are transcendental or $X_i \ne X_j$ for $1 \le (i,j) \le r$.
We require some properties of the (fairly) well-known {\sl Vandermonde}
matrix $M$, defined by
\assert Definition \ref(8.3) {$$M_{ij}\ =\ (X_j)^i.$$}
\delete{
[Its columns are the eigenvectors of the shift operator $E$ on a sequence
$S_n$ satisfying relation $J$, the corresponding eigenvalues being the $X_j$.]
}
Its determinant is given by
\assert Theorem \ref(8.4) {$$|M_{ij}|\ =\ \prod_{k}\prod_{l 0$;}\cr}$$}
it has the property that $T_{m,n}$ vanishes for all $m>r$ just when $S_n$
equals a polynomial in $n$ of degree $r$. By extending the region of zeros
with $n$ then reversing the direction of the recursion with $m$, we can
efficiently extrapolate such a sequence to greater $n$.
Further, the explicit form of the polynomial may be recovered via Newton's
forward difference formula, subject to the caveat below:
\assert Theorem \ref(9.2) {If the polynomial sequence $[S_n]$ has difference
table $[T_{i,j}]$ then
$$S_n\ =\ \sum_i T_{i,0} {n \choose i}.$$}
\par
Similarly if $[S_n]$ is LFSR of order $r$, then by \ref(3.3) its wall vanishes
for $m>r$. Since by \ref(2.2) a polynomial sequence of degree $r$ is a
(special case of a) LFSR sequence of degree $r+1$, the same use
may be made of the number-wall to give a generalized extrapolation
algorithm, albeit requiring an extra term and a rather more complicated
computation of the explicit form. This application is described in an
elementary fashion in \fer[Slo95] \S1 and \fer[Con96] \S3, employing an
ingenious notation unhappily compromised by a clutch of demoralizing misprints.
\par
A difficulty with interpreting \ref(2.2) for finite ground characteristic $p$
is that the Little Fermat Theorem $n^p = n \pmod p$ effectively prevents the
degree of `na\"\i ve' polynomials based on powers $n^j$ from exceeding $p-1$.
A straightforward solution to the difficulty is suggested by \ref(9.2): to base
our polynomials on binomial coefficients ${n \choose j}$ instead. This falls
over in a similar fashion if we attempt the usual
\assert Definition \ref(9.3) {
$${n \choose j}\ =\ \prod_{0\le i 2$; but as required
$$[{n\choose 3}]\ =\ [0,0,0,1,4,10,20,35,...]\ \equiv\ [S_n]\pmod 2$$
\par
Sequences with period a power of the characteristic have a useful property:
\assert {Lemma} \ref(9.6)
{If $[S_n]$ has period $l = p^k$ then
$$({\bf E}^l - 1) [S_n]\ =\ ({\bf E} - 1)^l [S_n]\ =\ [O_n],$$}
since ${l \choose j} = 0$ except when $j = 0,l,$ using \ref(9.4).
So by \ref(2.2), $S_n$ is a polynomial (in the binomial sense) of degree $r$,
where $l/p < r\le l$ (unless the period is $l/p$ or smaller).
By \ref(9.1), we can employ a difference table rather than a number wall
to compute its order. Moreover, by \ref(9.6) in reverse, we can difference
$p^i$ times in the same time as differencing once: so initially setting
$i = k$ and progressively reducing $i$ as the period of the current row $m$
decreases, we can compute the order in $kp$ rows instead of $l$, giving about
order $lp$ time.
\par
We illustrate the method with a Maple program:
\assert Algorithm \ref(9.7) {
$$\hfil\vbox{\halign {\tt #\cr
orderSpk := proc (S, p, k) \cr
local T, dT, m, j, l; \cr
l := p$\wedge$k; m := 0; T := S; \cr
while l > 1 do \cr
dT := [seq((T[j+l/p mod l +1] - T[j+1]) mod p, j = 0..l-1)]; \cr
if sum(dT[j+1], j = 0..l-1) = 0 \cr
then l := l/p else m := m + l/p; T := dT fi od; \cr
m + min(1, T[1]) end; \cr
}}$$}
\par
An application of the preceding theory occurs in the study of deBruijn
sequences, which are defined traditionally over a finite set of size $q$
as $k$-distributed (every $k$-tuple occurring with the same frequency),
and having minimum period $q^k$. In the case where
the set is actually a finite field, the extra structure allows us to define
and compute the order of the sequence {\sl qua} LFSR sequence over that domain;
now the method outline above can be employed to substantially reduce the time
(by the traditional factor of $l/\log l$).
In an investigation such as \fer[Bla96], \fer[Cha82] where the computation
of the order is the inner loop of a lengthy combinatorial search, such a
reduction is crucial. [In fact \fer[Bla96] employed a more involved
formulation of polynomials, basing the computation of the order
on a modified Fast Fourier Transform.]
\par
As a numerical example, we compute the order of the deBruijn sequence with
$q = p = 2$, $k = 5$ and order $r = 21$ over $\F_2$ (but 25 over
$\Z$). [It is essentially unique, modulo reflection and (independent)
complementation of the first or last half.] $T$ denotes the current $m$-th
difference of $S$, $l$ the currently detected period; when the $l/p$-th
difference of $T$ would be zero, the period is reduced instead.
$$\matrix{
l &m &dT=0? &T\cr
32 &0 &N &11111001000001010011101011000110\cr
32 &16 &Y &11000011110000111100001111000011\cr
16 &16 &Y &1100001111000011\cr
8 &16 &N &1100001111000011\cr
8 &20 &Y &11111111\cr
4 &20 &Y &1111\cr
2 &20 &Y &11\cr
1 &20 &N &1\cr
0 &21 & &\cr}$$
For the deBruijn sequence with $q = p = 2$, $k = 4$ at the end of \S6,
we find from the full difference table (not shown)
that $T_{i,0} = 1$ only for $i = 0,4,10,11$; therefore an explicit `binomial'
expression for the $n$-th term is
$$S_n\ =\ 1 + {n\choose 4} + {n\choose 10} + {n\choose 11}.$$
\par
Finally, we touch on a rather curious interaction between difference tables
and number walls, which comes to light when we try to establish exactly what
effect a simple transformation of the sequence has on its wall. For instance,
a little thought suggests that term-by-term addition of a low-order LFSR
sequence to $[S_n]$ will only have a (literally) marginal effect on any large
windows, causing their frames to shift by at most the order added. However,
our only explicit progress in this direction is the
\assert Theorem \ref(9.8) {
The wall for $1 + S_n$ is just the wall for $S_n$ itself added to the wall
for $-{\bf \Delta}^2 S_{n-1}$ shifted down by one row. That is,
$$\hbox{Let } R_n\ =\ 1 + S_n,\quad T_n\ =\ - S_{n+1} + 2.S_n - S_{n-1};
\quad \hbox{then } R_{m,n} = S_{m,n} + T_{m-1,n}$$}
\Proof: Rather than attempt a formal but notationally impenetrable proof
for the general case, we illustrate it by the case $m = n = 3$.
Starting from the determinant definition \ref(3.1), $R_{33}\ =\ $
$$\left|\matrix{
1+S_3&1+S_4&1+S_5&1+S_6\cr
1+S_2&1+S_3&1+S_4&1+S_5\cr
1+S_1&1+S_2&1+S_3&1+S_4\cr
1+S_0&1+S_1&1+S_2&1+S_3\cr}\right|;$$
expanding each by column in turn, and noticing that any determinant with two
or more equal columns of ones must be zero, this becomes
$$S_{33}\ +
\ \left|\matrix{
1&1+S_4&1+S_5&1+S_6\cr
1&1+S_3&1+S_4&1+S_5\cr
1&1+S_2&1+S_3&1+S_4\cr
1&1+S_1&1+S_2&1+S_3\cr}\right|\ +
\ \left|\matrix{
1+S_3&1&1+S_5&1+S_6\cr
1+S_2&1&1+S_4&1+S_5\cr
1+S_1&1&1+S_3&1+S_4\cr
1+S_0&1&1+S_2&1+S_3\cr}\right|\ +
\ \ldots\ +
\ \left|\matrix{
1+S_3&1+S_4&1+S_5&1\cr
1+S_2&1+S_3&1+S_4&1\cr
1+S_1&1+S_2&1+S_3&1\cr
1+S_0&1+S_1&1+S_2&1\cr}\right|;$$
then subtracting row $i+1$ from row $i$ for $i = 1,\ldots,m$ and pivoting
on the bottom one for each determinant,
$$S_{33}\ -
\ \left|\matrix{{\bf \Delta}S_3&{\bf \Delta}S_4&{\bf \Delta}S_5\cr
{\bf \Delta}S_2&{\bf \Delta}S_3&{\bf \Delta}S_4\cr
{\bf \Delta}S_1&{\bf \Delta}S_2&{\bf \Delta}S_3}\right|\ +
\ \left|\matrix{{\bf \Delta}S_2&{\bf \Delta}S_4&{\bf \Delta}S_5\cr
{\bf \Delta}S_1&{\bf \Delta}S_3&{\bf \Delta}S_4\cr
{\bf \Delta}S_0&{\bf \Delta}S_2&{\bf \Delta}S_3}\right|\ -
\ \left|\matrix{{\bf \Delta}S_2&{\bf \Delta}S_3&{\bf \Delta}S_5\cr
{\bf \Delta}S_1&{\bf \Delta}S_2&{\bf \Delta}S_4\cr
{\bf \Delta}S_0&{\bf \Delta}S_1&{\bf \Delta}S_3}\right|\ +
\ \left|\matrix{{\bf \Delta}S_2&{\bf \Delta}S_3&{\bf \Delta}S_4\cr
{\bf \Delta}S_1&{\bf \Delta}S_2&{\bf \Delta}S_3\cr
{\bf \Delta}S_0&{\bf \Delta}S_1&{\bf \Delta}S_2}\right|.$$
The first two determinants have identical columns except the
leftmost, say $[F_i]$ in the first and $[G_i]$ in the second;
we contract them into a single determinant, with first column $[F_i-G_i]$.
Each remaining determinant contains both columns;
we subtract $[F_i]$ from $[G_i]$ and change the sign, giving
$$S_{33}\ -
\ \left|\matrix{{\bf \Delta}^2S_2&{\bf \Delta}S_4&{\bf \Delta}S_5\cr
{\bf \Delta}^2S_1&{\bf \Delta}S_3&{\bf \Delta}S_4\cr
{\bf \Delta}^2S_0&{\bf \Delta}S_2&{\bf \Delta}S_3}\right|\ +
\ \left|\matrix{{\bf \Delta}^2S_2&{\bf \Delta}S_3&{\bf \Delta}S_5\cr
{\bf \Delta}^2S_1&{\bf \Delta}S_2&{\bf \Delta}S_4\cr
{\bf \Delta}^2S_0&{\bf \Delta}S_1&{\bf \Delta}S_3}\right|\ -
\ \left|\matrix{{\bf \Delta}S_2&{\bf \Delta}S_3&{\bf \Delta}S_4\cr
{\bf \Delta}^2S_1&{\bf \Delta}S_2&{\bf \Delta}S_3\cr
{\bf \Delta}^2S_0&{\bf \Delta}S_1&{\bf \Delta}S_2}\right|.$$
We are now in a similar situation, except that $[F_i]$ and $[G_i]$ are now the
column two of the first two determinants. Repeating the previous operation,
$$S_{33}\ -
\ \left|\matrix{{\bf \Delta}^2S_2&{\bf \Delta}^2S_3&{\bf \Delta}S_5\cr
{\bf \Delta}^2S_1&{\bf \Delta}^2S_2&{\bf \Delta}S_4\cr
{\bf \Delta}^2S_0&{\bf \Delta}^2S_1&{\bf \Delta}S_3}\right|\ +
\ \left|\matrix{{\bf \Delta}^2S_2&{\bf \Delta}^2S_3&{\bf \Delta}S_4\cr
{\bf \Delta}^2S_1&{\bf \Delta}^2S_2&{\bf \Delta}S_3\cr
{\bf \Delta}^2S_0&{\bf \Delta}^2S_1&{\bf \Delta}S_2}\right|.$$
Finally after $m-2$ iterations, we are left with the required expression
$$S_{33}\ -
\ \left|\matrix{{\bf \Delta}^2S_2&{\bf \Delta}^2S_3&{\bf \Delta}^2S_4\cr
{\bf \Delta}^2S_1&{\bf \Delta}^2S_2&{\bf \Delta}^2S_3\cr
{\bf \Delta}^2S_0&{\bf \Delta}^2S_1&{\bf \Delta}^2S_2}\right|
\ =\ S_{33}\ + T_{23}.\ \QED$$
\par
\delete {
\Proof: Rather than attempt a formal but notationally impenetrable proof
for the general case, we illustrate it by the case $m = n = 2$.
Starting from the determinant definition \ref(3.1),
$$R_{m,n}\ =\ \left|\matrix{1+S_2&1+S_3&1+S_4\cr
1+S_1&1+S_2&1+S_3\cr
1+S_0&1+S_1&1+S_2\cr}\right|;$$
expanding each by column in turn, and noticing that any determinant with two
or more equal columns of ones must be zero, this becomes
$$S_{m,n}\ +\ \left|\matrix{1&S_3&S_4\cr 1&S_2&S_3\cr 1&S_1&S_2\cr}\right|\ +
\ \left|\matrix{S_2&1&S_4\cr S_1&1&S_3\cr S_0&1&S_2\cr}\right|\ +
\ \left|\matrix{S_2&S_3&1\cr S_1&S_2&1\cr S_0&S_1&1\cr}\right|;$$
then by subtracting row $i$ from row $i+1$ for $i = 1,\ldots,m$ and pivoting,
$$S_{m,n}\ +\ \left|\matrix{S_3-S_2&S_4-S_3\cr S_2-S_1&S_3-S_2\cr}\right|\ +
\ \left|\matrix{S_2-S_1&S_4-S_3\cr S_1-S_0&S_3-S_2\cr}\right|\ -
\ \left|\matrix{S_2-S_1&S_3-S_2\cr S_1-S_0&S_2-S_1\cr}\right|.$$
Now the first two determinants have all their columns identical except one,
call it $[F_i]$ in the first and $[G_i]$ in the second. We contract these two
into a single determinant, with first column $[F_i-G_i]$. The remaining terms
each contain both columns, so there we subtract $[G_i]$ from $[F_i]$, giving
$$S_{m,n}\ +\ \left|\matrix{S_3-2S_2+S_1&S_4-S_3\cr
S_2-2S_1+S_0&S_3-S_2\cr}\right|\ -
\ \left|\matrix{S_3-2S_2+S_1&S_3-S_2\cr S_2-2S_1+S_0&S_2-S_1\cr}\right|.$$
We are now in a similar situation, except that $[F_i]$ and $[G_i]$ are now the
second columns in the first two determinants. Repeating the previous operation
we get
$$S_{m,n}\ +\ \left|\matrix{S_3-2S_2+S_1&S_4-2S_3+S_2\cr
S_2-2S_1+S_0&S_3-2S_2+S_1\cr}\right|.$$
After $m-2$ iterations, we are left with the required expression. \QED
}
%[This has been checked computationally for $m\le 6$.]
Hence by \ref(3.1) we easily get the wall for $R_n = A + B.S_n$: with $S_n$
and $T_n$ as in \ref(9.8), $R_{m,n} = B^{m+1}S_{m,n} + A^{m+1}T_{m-1,n}$.
Notice also that the wall for $R_n = C^nS_n$ is $R_{m,n} = C^{(m+1)n}S_{m,n}$.
\par
\beginsection 10. Explicit Form of an LFSR Sequence
\par
We shall briefly discuss efficient methods for computing the roots $X_i$ and
coefficients $K_i$ in the explicit form \ref(2.2) for $S_n$.
From now on we mostly restrict ourselves to the integer domain $\Z$
embedded within the complex numbers ${\bf C}$;
still, much of what we say is interpretable in a more general context of a
continuous algebraic completion of the ground domain.
% such as the $p$-adic completion ${\bf C}_p$ of $\F_p$.
% biblio ? is C_p p-adic completion of Q or algebraic of F_p ?
`Combinatorial explosion' (exponential numerical growth) is a constant
hazard in integer algebraic computation,
and it may sometimes be worth remembering a spectacular trick: where
there is good reason to suppose that, for instance, the coefficients of the
relation of a given sequence are going to be small, then the Berlekamp-Massey
algorithm can perfectly well be applied modulo a smallish prime instead; or
even modulo several very small primes and, the result being reconstructed by the
Chinese Remainder Theorem as in \fer[Dav88] \S4.
\par
In order to calculate the relation for a given sequence, or the explicit
coefficients for given roots, it is possible to set up simultaneous
linear equations and solve them in order $r^3$ time. This approach becomes
cumbersome by hand for $r>4$, whereas (by contrast) the coefficient
equations are rapidly solvable explicitly.
A more practical approach is to compute the relation polynomial $J(X)$
using Berlekamp-Massey \ref(12.1), which costs order $r^2$ time; then extract
its roots $X_i$ formally, or more likely approximate them numerically using
one of the various available methods surveyed for instance in \fer[Hen74] \S6.9.
With the $X_i$ to hand, assuming them to be distinct we can immediately
apply \ref(8.6) to find the $K_i$, again in order $r^2$ time.
\par
We have avoided the general case of multiple roots in the present treatment;
in this direction we currently have only partial results. In the first place,
multiple roots of polynomials are numerically ill-conditioned, so that
it's quite likely that we never get to the point of trying to find the
coefficients at all. If we do, and it happens that all the roots coincide,
then $S_n$ is a known exponential times a polynomial, and the latter is
found by \ref(9.2).
For the general confluent case, the analogue of the Vandermonde determinant
$|M|$ and the explicit form of $S_{m,n}$ can be evaluated; but the formal
inversion of the matrix $M$ looks rather gruesome, and will be postponed
for the present.
\par
An alternative approach bypasses the relation and Vandermonde inverse
altogether, approximating roots and coefficients directly via quotients of
number wall elements. The point here is that if $|X_1| > |X_2| > \ldots$,
then for large $n$, $Y_1^n = (X_1X_2\ldots X_{m+1})^n$ dominates in \ref(8.7).
So it becomes possible to divide out unwanted factors from this term in the
explicit representation, leaving only the desired quantities together with
error terms which decrease exponentially with $n$ --- in fact, as
$|X_{m}/X_{m+1}|^{-n}$. Of course, $n$ can be made arbitrarily large simply
by extrapolating from the bottom (zero) row of the number-wall upwards.
In this way, we approximate first the $[X_i]$, then the $[K_i]$:
\assert Corollary \ref(10.1)
{If the roots $X_i$ of the relation $J({\bf E}) = 0$ for $[S_n]$
have distinct magnitudes (so are real), then
$$(S_{m,n+1}/S_{m-1,n+1})/(S_{m,n}/S_{m-1,n}) \to X_m$$
in order of magnitude descending as $m$ increases.}
\assert Corollary \ref(10.2)
{With $X_i$ as above, $$S_{m,n}/S_{m-1,n} \to L_m K_m X_m{}^n$$ where
$$L_m\ =\ \prod_{k 8$. Reversing $U_8$ gives the auxiliary
polynomial $J\ =\ {\bf E}^4-16{\bf E}^3+86{\bf E}^2-176{\bf E}+105\ = \ 0$,
that is $S$ satisfies the relation
$$S_{n+4}-16S_{n+3}+86S_{n+2}-176S_{n+1}+105S_n\ =\ 0.$$
\par
Algorithms reported by \fer[Sen92] and \fer[Ris74] compute the rank and
inverse resp. of an individual numerical $n\times n$ Toeplitz matrix,
at a cost of order $n^2$ time. The method involves decomposition into
triangular matrices, and does not appear to compete with ours for number walls.
%There is more on this topic in the survey \fer[Win96].
\par
\beginsection 13. Hideous Numerical Example
\par
In the number-wall diagrammed, all arithmetic (including division) is
to be done modulo $p = 5$. The entire table wraps around cyclically with $n$.
The LFSR order is $r = 21$ [hardly overwhelming news, since $r \le n$ for
any (periodic) sequence satisfying ${\bf E}^{n} - 1\ =\ 0$].
\figure {Diagram}
{Modulo $5$ wall of test sequence $S_n$ for $n = 1(1)21$
($S_n = 3^{k(k+1)/2 - n}$ with $k = [\sqrt{2n} + \half]$.)}
{$$\hfil\vbox{
\halign{\hfil{\tt#}\quad&{\tt#}\cr
m$\backslash$n& 1 2 3 4 5 6 7 8 9101112131415161718192021 \cr
-2& 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \cr
-1& 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 \cr
0& 1 3 1 4 3 1 2 4 3 1 1 2 4 3 1 3 1 2 4 3 1 \cr
1& 3 3 4 3 0 0 0 0 0 3 4 0 0 0 2 3 0 0 0 0 3 \cr
2& 0 4 2 1 0 0 0 0 0 4 1 0 0 0 4 3 0 0 0 0 4 \cr
3& 3 2 0 2 0 0 0 0 0 2 4 0 0 0 3 3 0 0 0 0 2 \cr
4& 2 1 3 4 0 0 0 0 0 1 1 4 1 4 1 3 0 0 0 0 1 \cr
5& 1 0 4 3 0 0 0 0 0 3 3 4 2 1 3 3 3 3 3 3 3 \cr
6& 3 1 2 1 2 4 3 1 2 4 2 0 0 0 1 0 0 3 0 0 1 \cr
7& 3 4 2 4 2 0 3 4 1 4 3 0 0 0 2 0 0 3 0 0 2 \cr
8& 2 0 4 2 2 1 3 3 0 2 2 0 0 0 4 2 1 3 1 2 4 \cr
9& 3 3 3 4 1 2 2 1 4 1 3 3 3 3 3 0 2 1 2 3 1 \cr
10& 3 3 3 4 4 2 4 1 3 2 3 3 1 1 1 2 4 4 1 1 3 \cr
11& 0 0 4 1 3 4 2 4 3 0 1 2 1 0 3 4 4 2 1 1 1 \cr
12& 0 0 2 1 0 0 2 0 3 1 2 1 1 2 4 2 2 0 4 0 2 \cr
13& 1 4 1 1 0 0 2 1 3 4 3 2 4 0 4 4 1 1 1 2 4 \cr
14& 3 1 1 1 3 4 2 3 0 2 3 2 1 2 4 1 1 2 1 1 2 \cr
15& 2 2 0 3 3 2 1 4 3 1 0 3 3 4 1 3 4 3 4 2 4 \cr
16& 2 4 4 4 1 4 4 1 2 3 4 2 2 4 1 0 2 4 0 3 1 \cr
17& 0 4 4 4 0 1 2 2 2 1 3 2 2 1 1 1 1 2 2 2 0 \cr
18& 0 4 0 4 1 4 3 0 1 0 3 4 1 1 0 1 2 3 0 3 0 \cr
19& 3 4 1 4 3 3 2 1 3 2 3 4 1 1 4 1 1 2 3 2 1 \cr
20& 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 \cr
21& 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \cr
}}\hfil$$}
\par
Perturbing $S_{10}$ by subtracting $X$ causes the following changes
around the frames of the 5x5 window with NE corner at $S_{1,9}$.
[The
notation is as in \S4 Diagram. Only terms significant to the inductive step
of the proof of Lemma \ref(4.9) are retained, along with the dominant term of
the remainder; missing terms are indicated by a final `+'.
Components not in range of the relevant lemma are omitted from vectors.]
$$\eqalign{
A\ &=\ [4,\ 3,\ 1,\ 2,\ 4,\ 3,\ 1+4X]\cr
B\ &=\ [4,\ 3,\ 1,\ 2,\ 4,\ 3,\ 1+X]\cr
C\ &=\ [{\ },\ 3+4X+4X^5+X^6,\ 1+4X^5,\ 2+4X+3X^2+X^3+X^4,\cr
&\qquad\ 4+X+3X^2+4X^3,\ 3+3X+X^2,\ 1+4X]\cr
D\ &=\ [{\ },\ 2+X+X^5+X^6,\ 1+X^5,\ 3+X+2X^2+4X^3+2X^4,\cr
&\qquad\ 4+X+3X^2,\ 2+2X+3X^2,\ 1+X]\cr}$$
$$\eqalign{
E\ &=\ [1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1]\cr
F\ &=\ [1,\ 4,\ 2,\ 0,\ 3,\ 4,\ 2]\cr
G\ &=\ [2+X+,\ 3+,\ 1+2X+,\ 4+X+,\ 1+X+,\ 4+2X,\ 1]\cr
H\ &=\ [4+4X+,\ 1+,\ 4+4X+,\ 3+4X+,\ 3X+,\ 2+3X+,\ 4+X]\cr}$$
$$\eqalign{
M\ &=\ N\ =\ [{\ },\ 4X^5,\ 3X^4,\ X^3,\ 2X^2,\ 4X,\ 3]\cr
P\ &=\ Q\ =\ 2\qquad U\ =\ V\ =\ 2/X\cr
R\ &=\ 2+4X+3X^2+X^3+2X^4+2X^5+2X^6+\cr
T\ &=\ 3+X+2X^2+4X^3+3X^4+3X^5+X^6+\cr}$$
To illustrate the perturbed frame results of \S4, we show the dominant term
of the error in \ref(4.7),\ref(4.8),\ref(4.9):
$$\eqalign{
{\rm err}(C)\ &=\ [{\ },\ {},\ 4X^5+,\ X^5+,\ 2X^3+,\ 2X^3+,\ 2X+]\cr
{\rm err}(D)\ &=\ [{\ },\ {},\ 3X^5+,\ 2X^5+,\ 4X^3+,\ 2X^3+,\ X+]\cr
{\rm err}(PT/QR)\ &=\ 4X^6+\cr
{\rm err}(E+F+G+H)\ &=\ [0+,\ 3X+,\ 4X+,\ 3X+,\ 3X+,\ X+,\ 4X+]\cr}$$
\par
Now suppose that we knew the Frame Theorems for $4\times 4$ only, and had
computed the original table as far as the bottom of the $5\times 5$ window.
To compute the South frames of this square, we might proceed thus:
First perturb the table as above, then find $N$ by \ref(4.2), $D$ by \ref(4.3),
$H$ by \ref(3.6) since $N$ is now nonzero, and finally let $X\to 0$.
The inductive versions of these theorems for $g-1$ in the form required in the
perturbed table for $1\le k\le k+1$ are:
$$\eqalign{
N_k\ &=\ (-)^{(g-1)(k-1)} M_k B_{k-1}/A{k-1}\cr
D_k\ &=\ (N_k/U)(Q E_{k-1}/A_{k-1} - (-1)^k(P F_{k-1}/B_{k-1} - V C_k/M_k))\cr
H_k\ &=\ (D_k{}^2 - D_{k-1} D_{k+1})/N_k\cr}$$
Notice how we need to compute $D$ to ${\cal O}(X^6)$ in order to be able to
compute $H_2$ to ${\cal O}(X)$ --- i.e. at all --- because $N_2 = 4X^5$.
\par
But all this is idle speculation, since we do know the Frame Theorems
for all $g$, and can simply compute the original frames directly by \ref(5.1).
\vfill\eject
\par
\beginsection References
\par
\frenchspacing
\item{\fer[Ait62]} Aitken,~A. \sl Determinants and Matrices, \rm Oliver \& Boyd
(1962).
\item{\fer[Bak75]} Baker,~G.~A.~Jr. \sl Essentials of Pad\'{e} Approximants,
\rm Academic Press (1975).
\item{\fer[Bla96]} Blackburn,~S.~R. \& Etzion,~T. \& Paterson,~K.~G.
\sl Permutation Polynomials, deBruijn Sequences, and Linear Complexity,
\rm J. Comb. Theory Ser. A \bf 76 \rm (1996) 55--82.
\item{\fer[Cha82]} Chan,~A.~H. \& Games,~R.~A. \& Key,~E.~L.
\sl On the Complexities of deBruijn Sequences,
\rm J. Comb. Theory ser. A \bf 33 \rm (1982) 55--82.
\item{\fer[Con96]} Conway,~J.~H. \& Guy,~R.~K. \sl The Book of Numbers,
\rm Springer (1996).
\item{\fer[Dav88]} Davenport,~J.~H. \& Siret,~Y. \& Tournier,~E. \sl Computer
Algebra, \rm Academic Press (1988).
\item{\fer[Fay94]} Faybusovich, Leonid \sl Rational functions, Toda flows, and
$LR$-like algorithms, \rm Linear Algebra Appl. \bf 203--204 \rm (1994) 359--383.
\item{\fer[Fro85]} Froberg,~C-E. \sl Numerical Mathematics, \rm Benjamin
Cummings (1985).
\item{\fer[Gil78]} Gilewicz,~Jacek \sl Approximants de Pad\'e, \rm Springer
Lecture Notes in Mathematics \bf 667 \rm (1978).
\item{\fer[Gra72]} Gragg,~W.~B. \sl The Pad\'e Table and its Relation to
Certain Algorithms of Numerical Analysis, \rm SIAM Review \bf 14 \rm (1972)
1--62.
\item{\fer[Gra96]} Granville,~A. \sl The Arithmetic Properties of Binomial
Coefficients, \rm in Proceedings of the Organic Mathematics Workshop (1996).
\item{\fer[Hen74]} Henrici,~P. \sl Applied and Computational Complex Analysis,
\rm Wiley (1974).
\item{\fer[Her75]} Herstein,~N. \sl Topics in Algebra, \rm 2nd ed. Wiley (1975).
\item{\fer[Ioh82]} Iohvidov,~I.~S. \sl Hankel and Toeplitz Matrices and Forms,
\rm Birkh\"auser (1982).
\item{\fer[Knu81]} Knuth,~D. \sl The Art of Computer Programming, \bf 1,2
\rm ed~2, Addison-Wesley (1981).
\item{\fer[Lan93]} Lang,~S. \sl Algebra, \rm Addison-Wesley (1993).
\item{\fer[Lid86]} Lidl,~R. \& Niederreiter,~H. \sl Introduction to Finite
Fields and their Applications, \rm Cambridge (1986). % ??
\item{\fer[Lun00]} Lunnon,~W.~F. \sl Pagodas and Sackcloth: Ternary Sequences
of Considerable Linear Complexity, \rm (to appear).
\item{\fer[Maz86]} Mazoyer,~J. \sl An Overview of the FSSP, \rm in C. Choffrut
(ed) \sl Automata Networks, \rm Springer (1986) 82--94.
\item{\fer[Maz87]} Mazoyer,~J. \sl A Six-State Minimal-Time Solution to the
FSSP, \rm Theoretical Computer Science \bf 50 \rm (1987) 183--238.
\item{\fer[Min67]} Minsky,~M. \sl Computation: Finite and Infinite Machines,
\rm Prentice-Hall (1967).
%\item{\fer[Nie87]} Niederreiter,~H. \sl Sequences with almost Perfect Linear
%Complexity Profile \rm in \sl EUROCRYPT '87 \rm LNCS \bf 330 \rm (1987) 37--51.
%\item{\fer[Nie88]} Niederreiter,~H. \sl The Probabilistic Theory of Linear
%Complexity \rm in \sl EUROCRYPT '88 \rm LNCS \bf 330 \rm (1988) 191--209.
\item{\fer[Nie89]} Niederreiter,~H. \sl Keystream Sequences with a Good Linear
Complexity Profile for Every Starting Point, \rm in \sl Eurocrypt '89 Abstracts,
\rm Houthalen, Holland (1989).
\item{\fer[Niv69]} Niven, Ivan \sl Formal Power Series, \rm Amer. Math. Monthly
\bf 76 \rm (1969) 871--889.
\item{\fer[Pap94]} Papageorgiou,~V. \& Grammaticos,~B. \& Ramani,~A.
\sl Integrable difference equations and numerical analysis algorithms,
\rm pp. 269-280 in Levi, Decio (ed.) et al. \sl Symmetries and integrability of difference
equations: Papers from the workshop, May 22--29, 1994, Esterel,
Canada; \rm Amer. Math. Soc. Proc. Lect. Notes \bf 9, \rm 1996.
% arto salomaa and matti soitola, _automata, languages and power series
\item{\fer[Poo96]} van~der~Poorten,~Alf \sl Notes on Fermat's Last Theorem,
\rm Wiley (1996)
\item{\fer[Ree85]} Reeds,~J.~A. \& Sloane,~N.~J.~A. \sl Shift-Register Synthesis
(Modulo m),
\rm SIAM J. Computing \bf 14 \rm (1985) 505--513.
\item{\fer[Ris74]} Rissanen,~J. \sl Solution of Linear Equations with Hankel
and Toeplitz Matrices, \rm Numer. Math. \bf 22 \rm (1974) 361--366.
\item{\fer[Rob86]} Robbins,~D.~P. \& Rumsey Jr.,~H. \sl Determinants and
Alternating Sign Matrices, \rm Adv. in Math. \bf 62 \rm (1986) 169--184.
\item{\fer[Sen92]} Sendra,~J.~R. \& Llovat,~J. \sl Rank of a Hankel Matrix over
$Z[x_1 \ldots x_r]$, \rm Appl. Algebra in Eng. Comm. and Computing
\bf 3 \rm (1992) 245--256.
\item{\fer[Slo95]} Sloane,~N.~J.~A. \& Plouffe,~S. \sl The Encyclopedia of
Integer Sequences, \rm Academic Press (1995).
\item{\fer[Ste92]} Stephens,~N.~M. \sl The Zero-square Algorithm for
Computing Linear Complexity Profiles, \rm in Mitchell, Chris (ed.)
\sl Cryptography and Coding II, \rm Clarendon press Oxford (1992) 259--272.
%\item{\fer[Wan89]} Wang,~M. \sl Linear Complexity Profiles and Continued
%Fractions in \sl EUROCRYPT '89 \rm LNCS (1989) 1--12. % vol. ??
%\item{\fer[Win96]} Winkler,~F. \sl Polynomial Algorithms in Computer Algebra
%\rm Springer (1996). % Thm 7.2.3, refers to \fer[Sen92]
\item{\fer[Wyn60]} Wynn,~P. \sl The Rational Approximation of Functions which
are Formally Defined by a Power-Series Expansion, \rm Math. Comp.\bf 14
\rm (1960) 147--186.
\item{\fer[Wyn66]} Wynn,~P. \sl Upon Systems of Recursions which Obtain among
the Quotients of the Pad\'e Table, \rm Numer. Math. \bf 8 \rm (1966) 264--269.
\medskip
\hrule
\medskip
\noindent
Received Jan 1, 2001;
revised version received Sep 25, 2001.
Published in Journal of Integer Sequences, Oct 7, 2001.
\medskip
\hrule
\bye
*