2022-08-27

[public] 19.3K views, 6.33K likes, dislikes audio only

Mathologer

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.

https://cs.uwaterloo.ca/journals/JIS/VOL4/LUNNON/numbwall10.html

Also check out Fred's article "The Pagoda sequence: a ramble through linear complexity, number walls, D0L sequences, finite state automata, and aperiodic tilings", Electronic Proceedings in Theoretical Computer Science 1 (2009), 130–148. https://arxiv.org/abs/0906.3286. Among many other things this one features lots of pretty pictures :)

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:

https://tinyurl.com/bdhyzscw

https://core.ac.uk/download/pdf/82737163.pdf

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"

https://en.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficients

Coding challenge

Create an online implementation of the number wall algorithm using determinants or, ideally, using the cross and horseshoe rules and do a couple of fun things with your program. Here are some possible ideas you could play with: 1. generate pictures of even number (or, more generally, mod p) windows of random integer sequences or of sequences grabbed from here https://oeis.org/ . 2. Explore the Pagoda sequence number wall, again mod various prime numbers. Here is the entry for this sequence in the on-line Encyclopaedia of integer sequences https://tinyurl.com/yc45cfvf 3. Be inspired by the examples in this article https://arxiv.org/abs/0906.3286 Send me a link to your app before the next Mathologer video comes out and I'll enter you in the draw for a copy of Marty and my book Putting two and two together :)

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