Secrets of the lost number walls

This video is about number walls a very beautiful corner of mathematics that hardly anybody seems to be aware of. Time for a thorough Mathologerization :) Overall a very natural follow-on to the very popular video on difference tables from a couple of months ago ("Why don't they teach Newton's calculus of 'What comes next?'")

00:00 Intro
01:02 Chapter 1: What's in a wall
03:35 Chapter 2: Number wall oracle
14:31 Chapter 3: Walls have windows
16:34 Animations of Pagoda sequence
18:13 Chapter 4: Zero problems
25:31 Chapter 5: Determinants
32:49 Animation sequence with music
35:22 Thank you :)

References for number walls
The main reference for number walls is Fred Lunnon's article "The number-wall algorithm: an LFSR cookbook", Journal of Integer Sequences 4 (2001), no. 1, 01.1.1.

Conway and Guy's famous "The book of numbers" has a chapter dedicated to number walls. This is where I first learned about number walls. Sadly, Figure 3.24 on page 88 which describes the horse shoe rule is full of typos. Careful:
1. (formulae on right) Negate signs attached to w_l/w and e_l/e ;
2. (diagram on left) Leftward arrow missing from edge marked w_2 ;
3. The last row of arrows bears labels " s_3 " ... " s_2 " ... " s_1 " , which should instead read " s_1 " ... " s_2 " ... " s_3 " .

More articles/books to check out if you are really keen:
Jacek Gilewicz, Approximants de Padé, Springer Lecture Notes in Mathematics 667 (1978).

The Wiki page on linear recurrence with constant coefficients is a good resource for finding out about how the characteristic polynomial of a sequence translates into a "function rule"

Coding challenge

Research challenge
Prove the Pagoda sequence wall conjecture or find a counterexample.

Bug report
In the video I say that figuring out the factor rule is easy. This is only true for windows of 0s of even dimensions. Showing that the factor rule has a -1 on the right side for windows of odd dimensions is actually somewhat tricky. Details in the first article by Fred Lunnon listed above.

Today's music: Asturias by Isaac Albeniz performed by Guitar Classics and Taiyo (Sun) by Yuhi (Evening Sun)
Today's t-shirt: Yes, I am always right. If you are interested in getting one just google "Yes, I am always right math t-shirt" and pick the version you like best.

Enjoy!

Burkard

[Stekey]

This is mad! I am a PhD student who is actively studying number walls! Specifically, I have written a program to generate the number wall from a sequence and I have some nice formulas for the number of sequences that have a given window in their number wall. They have some beautiful relationships to diophantine approximation over function fields and linear complexity! It's so excititing to see them be popularised more.

[johnchessant]

Yet another awesome topic that has me saying "how is this the first time I'm hearing about this?"! The mystery of why the number walls will always have integer entries would've been enough to hold my attention, let alone all the other cool properties!
Also, fun fact: The characteristic polynomial is the denominator of the generating function of the sequence! The numerator will be a polynomial of degree less than the denominator, determined by the initial terms of the sequence.

[gammanob]

The recursive formula for the squares translates to:
x^2 = 3(x-1)^2 - 3(x-2)^2 + (x-3)^2
Expanding the right hand side gives us:
(3x^2 - 6x + 3) - (3x^2 - 12x + 12) + (x^2 - 6x + 9)
= 3x^2 - 3x^2 + x^2 - 6x +12x - 6x + 3 - 12 + 9
= x^2
The formula works :)

The coefficients of the formulas look like the binomial coefficients, they are matching with the rows in pascals triangle.
You can generate the formla by expanding the right side of the equation 0 = (x - 1)^n and replacing every x^k by the k-th coefficient c_k. Then solve for the highest power (x^n) and you have the formula for the sums of x^(n-1). Notice, the formula for the squares uses the coefficients of the 3rd row, expanding (x-1)^3 not (x-1)^2.

[maxwellgrossman]

I love how every time mathologer posts he just shows up with a new video about something I've never heard of and then suddenly I have something new to explore for the next month or so.

[matthewgiallourakis]

I love the feeling of having just about finished watching another great math video, and then I remember this is Matholologer and I've only just finished chapter 2 of 5!

You spoil us with knowledge!

[canaDavid]

This seems very similar to second order automata - each cell's value is determined by the three cells over it, and the cell 2 over it.

[trizgo_]

i can't help but smile whenever self-similarity pops up out of seemingly nowhere!

[chriszachtian]

How on earth could you resist to check what happens with the sequence of primes???
Thanks for the video.

[ritchards]

Immediate thought: what does the number wall of the prime numbers look like?

[hybmnzz]

If discrete calculus leads to calculus, I wonder if there is a continuous analog to number walls.

[gideonk]

Fantastic video!

A more computationally-efficient method than the determinant method, which also easily and transparently deals with single and multiple zeros:

Step 1: After using k delayed copies of the original sequence, instead of repeatedly computing determinants (as in the video), take a rectangular “snapshot” — this is a rectangular matrix of size k-by-n, with n > k.

Step 2: Transpose this matrix (so now it’s n-by-k with n > k) and compute its “economy” SVD (singular value decomposition). There are many existing software libraries to do this. This step is the only computationally-intensive step, whose complexity is O(n k^2), which is much less than the determinant method as stated in the video, which is O(n k^3), or even more if care is not taken…

Step 3: Now, look at the singular values: If one or more of the smallest singular values is/are zero, then we’re sure this is what Burkard calls “Fibonacci-like sequence”, something usually called “linear recurrence with constant coefficients” (which he mentioned in the video). However, if none of the singular values is zero, then repeat with larger k, i.e., more delayed copies of the original sequence.

Step 4: The linear recurrence with constant coefficients is easily determined from the column of the SVD result corresponding to the zero singular value (because this is the vector which can zero-out any set of k consecutive elements of the sequence). Specifically, if the “economy” SVD result of the original n-by-k matrix is U, s, Vt, then the last row of the square k-by-k matrix Vt will be the desired set of linear constant recurrence values. This last row has size 1-by-k, of course. These values will probably need to be scaled by a common multiple if nice integer values are desired! Move the 1st element of this set of k values to the other side of the equation to use as a prediction recurrence equation, i.e., the next value is determined linearly from the previous k-1 values.

Remark: The idea of a singular value decomposition (SVD) is mathematically very closely related to a determinant, because it essentially also determines linear combinations of columns (and/or rows). But it is more computationally-efficient in this case, because it can be computed for a rectangular set of values simultaneously, rather than small squares of values one after the other. The second advantage of the SVD is that it can also give us the linear recurrence with constant coefficients “for free” (from the same computational result).

[alokaggarwal]

Thank you the video was fantastic!! I never heard of number walls before, and the graphical presentation was very informative. I look forward to learning more from the links.

[theMichaelsLi]

For years people have discussed the level of mathematics that can be found within art. Number Walls are proof that a hidden masterpiece can exist if you recognize the pattern of beauty. In the past I watched your videos for the lessons and enthusiasm, given the level of excitement you've displayed concerning Number Walls - I'm afraid you'll forever be the Paint by Number Guy in my book. It's really something to see a scientist morph into an artist in a video. Good job!

[mathyland]

Well, you’ve set me down a rabbit hole again for at least the next week. Amazing video as always!

[johnchessant]

The closed formula for the mortal enemy's sequence is: E_n = 0.8469 (1.5747)^n + 0.2636 (1.3802)^n cos(1.7805n + 0.9507).
All the decimals are rounded so this won't be very accurate past n = 15 or so, but we can use this to get the asymptotic formula for E_n. Since 1.3802^n << 1.5747^n for large n, we can drop the second term and say E_n ~ 0.8469 (1.5747)^n. So for large enough n, each term in the mortal enemy's sequence will be 57.47% larger than the previous term.

[ApteraPioneer]

More (fabric designers) should partner with mathematicians. Gorgeous animations!

[binathiessen]

You can get the non-recursive function from a recursive function using the z-transform. This is used often in Digital Signal Processing problems.

[marcozarantonello]

You are by far the best math channel on YouTube

[jimmy]

So, could the infinite row of zeros at the top be considered to be infinitely high moving upwards too? … thus also being a square window ….. which, for want of a better term, I think should be called the “sky” 😀

[Mutual_Information]

Very original video. I watch a ton of math edu content.. and I’ve never heard of math walls. Well done!