Simpler and Faster ways to compute the "Number Wall" ==========Warren D. Smith=====March 2016============ The idea of the number wall was invented by James J. Sylvester (1814-1897). For an introduction to using it (and the "difference table") to analyse sequences, see chapter 3 of "The book of numbers" by J.H.Conway & R.K.Guy (Springer 1996), except, according to Lunnon, their discussion is marred by several errors in its details. (Lunnon doesn't actually say what those errors were, which was not very helpful.) The top three rows of the number wall are all-0, all-1, and your integer sequence S. To determine subsequent rows, the slow but safe method is this: The entry H hops vertically below sequence entry S[A] is the determinant of the KxK Toeplitz matrix whose leftmost column and top row are (if we walk up the leftmost column then rightward along the top row) S[A-K], S[A-K+1], ... S[A-1], S[A], S[A+1], ..., S[A+K-1], S[K]. This makes it obvious all entries of the number wall are integers (if the sequence was integers) and indeed if the seqeunce was elements from any commutative ring, then so are all entries of the number wall. A much faster and simpler, but not entirely safe, way to fill in the subsequent rows of the number wall is to use the "holy cross law" that any 5 numbers adjacent in a "holy cross" configuration in the number wall: . N . W X E are related by X*X = N*S + E*W. . S . The reason this is "not entirely safe" is because, e.g, trying to determine S via S=(X*X-E*W)/N might give you 0/0. (Also, if we are operating in a ring that is not a field, then division by a "zero divisor" can yield non-unique answers. It also is possible in such rings for division problems to have no solutions, but the division problems that arise inside number walls always do have solutions so that is not an issue.) That problem happens if and only if N=0 while W,X,E are in geometric progression: W*E = X*X. The best try at a rigorous and correct development seems to be W.F.Lunnon: The Number-Wall Algorithm: an LFSR Cookbook, Journal of Integer Sequences 4 (2001) Article 01.1.1 https://cs.uwaterloo.ca/journals/JIS/VOL4/LUNNON/numbwall10.pdf But in Lunnon's crux "algorithm description" page 16 his formula in step iii was wrong and presumably should have ended with G_k/C_k not C_k/M_k. Lunnon's main theorems (3.8, 4.1, 4.2, 4.3 pp.9-11) state that zero-entries in a number wall can only arise in the form of gXg square "windows in the wall" (consisting entirely of 0s) surrounded by an "inner frame" of 4(g+1) nonzero entries, where the g+2 entries forming each side (including their corners) of this inner frame, must be in geometric progression, and the 4 growth ratios for the 4 geometric progressions (regarding all 4 are progressing clockwise) must have product = (-1)^g. [Obviously if P is the product, then P^(g+1) = 1 since return to starting point after g+1 hops in each direction. That forces P to equal +1 except that if g is odd, then -1 also could be possible. And in fact, this -1 does happen.] ##aA#### #000000# #000000b Picture of gXg zero-window with inner frame #000000B showing 4 entires A,B,C,D (one per side) of the D000000# inner frame (arbitrarily located) and their adjacent d000000# predecessors a,b,c,d in clockwise order. #000000# (Here "#" means "irrelevant nonzero entry".) ###Cc### In other words, ABCD = (-1)^g abcd if A,B,C,D are any 4 entries on the inner frame (one per side) with a,b,c,d the immediately preceding entries in clockwise order. (Or anticlockwise; both directions work, so long as we are consistent.) This allows us to work out the entire inner frame from the 6 entries at and adjacent to the top two corners; indeed we need only three among the four top-row members within those six. Therefore, pick two antipodal corners of the inner frame, labeled * in the diagram below. if we have 4 entries on the inner frame, 1 per side, call them A,B,C,D such that A & D are distance k from one *-corner while B & C both are at the same distance k from the other (or A&B and C&D if we choose to star the complementary set of corners), *##A#### #000000# Picture of gXg zero-window, with inner frame. #000000# Here "#" means "irrelevant nonzero entry", D000000# and "*" means the same but the two *'s must be #000000B antipodal corners. A&D lie at same distance k #000000# from *, as do B&C from their *, where 1<=k<=g. #000000# ####C##* then A*C = (-1)^(g*k) * B*D, which is a polynomial relation of only degree=2 and enables deduction of any inner frame entry given that the other 3 sides of the inner frame are known. (Smaller degrees are better since they allow carrying fewer digits in arithmetic.) This inner frame is surrounded by an "outer frame," consisting of 4(g+2) entries. These obey ....E..... .*#aA####. .#000000#. Picture of gXg zero-window, with inner & outer frames, .d000000#. where "0" means "zero entry," HD000000#. "#" means "irrelevant nonzero entry" of inner frame, .#000000BF "*" means same as # except these must be two antipodal corners, .#000000b. and "." means "irrelevant entry" of outer frame. .#000000#. Note A,B,C,D,a,b,c,d all are nonzero. .####Cc#*. A&D lie at same distance k from *, as do B&C from their *, .....G.... where 1<=k<=g. The 12 entries labeled with letters obey (-1)^(k+g) * (A*H*c*B - C*F*a*D) = B*G*d*A - D*E*b*C. This is a new identity of polynomial degree=4 and enables deduction of any outer frame entry given that the other 3 sides of the outer frame are known. Is there any identity of degree=3? I conducted a fairly exhaustive computer search and failed to find any for the task of relating these 8 entries: ..AB.. ..CD.. EF00GH for a 2x2 window. JK00LM ..NP.. ..QR.. In other words, I suspect my degree-4 identity is best possible in the sense of having least possible degree and enabling "walking through windows," even for 2x2 windows. But in the special case of an isolated zero (1x1 "zero window") an identity of degree=3 does suffice: ..n.. ..N.. Conway & Guy bottom of p.87 claim s*N*N + n*S*S = w*E*E + e*W*W wW0Ee agreeing with Lunnon EQ 5.2 p.16. ..S.. ..s.. It now is possible to fill in the entries of the number wall row by row by an algorithm whose runtime is linear in the number of entries it computes, and which uses storage equivalent to the latest 6 rows of the wall, plus the row currently being computed as a 7th -- provided that 1. denote the 5 rows stored as V, W, X, Y and the new one (being computed) is Z, in order going down. 2. If X contains zero-entries, then assume there are special symbols available meaning "zero whose vertical location is j," where the top row of a gXg zero-window has j=1 and the bottom row has j=g, and use them. 3. If W contains zero-entries, then cheat by agreeing each entry of W that would have been 0, will contain the first nonzero entry of the number wall you'd reach by walking vertically upward from that 0. 4. And similarly cheat for V; it contains the entry immediately above the corresponding entry for W. 5. Finally up to two more rows worth of storage need to be added, which store the two vertical edges of the outer frame of each window. I point this out since for some reason Lunnon (p.23) claimed runtime and storage both a factor N larger than my claims (N is the length of a row of the number wall), except if doing arithmetic over the binary field GF(2) where he claimed to equal my bounds (but claimed going to higher fields like GF(5) would probably be "infeasible"). That all was pretty silly. With the aid of the number wall, it is easy to recognize sequences that obey linear recurrences, e.g. the powers of 2 or Fibonacci numbers. In all these cases (and some others) some pattern can be recognized inside the number wall, then used in combination with the holy-cross-relation to fill in all other entries, thereby "predicting" the sequence forever. Numerical example containing 1x1, 1x1, and 3x3 windows (latter with *'s at corners of inner frame): 0:1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1:9 8 7 5 4 1* 1 1 1 1 2 5 9 12 16 18 21 2: 1 9 -3 11 -3 0 0 0 -1 -1 7 21 0 40 -12 3: 12 -18 28 9 0 0 0 1 4 14 49 -70 100 4: 4 86 -27 0 0 0 -1 -2 0 161 7 5: 268 81 -27 9 -3 1* 1 23 529 6: -511 -76 -109 -16 -4 11 -151 7: 1849 1185 60 192 -483 8: -11865 13995 -16461 9: 9171