Polynomial Counting: Pentamerous multiplication

This post assumes you have read the first, which introduces generalized polynomial counting.

Arithmetic on Integral Systems

Addition is a fairly simple process for positional systems: align the place values, add each term together, then apply the carry as many times as possible. Without a carry rule, this can be approached formally by treating the place values as a sequence b_n and gathering terms:

\begin{gather*}
\phantom{+~}
\overset{b_2}{1}
\overset{b_1}{2}
\overset{b_0}{3} &

\phantom{+~}1b_2 + 2b_1 + 3b_0 
\\
\underline{+\ \smash{
\overset{\phantom{b_0}}4
\overset{\phantom{b_0}}5
\overset{\phantom{b_0}}6
}\vphantom,} &

\underline{+\ 
4b_2 + 5b_1 + 6b_0
\vphantom,} \\

\phantom{+~}\smash{
\overset{\phantom{b_0}}5
\overset{\phantom{b_0}}7
\overset{\phantom{b_0}}9} &

\phantom{+~}5b_2 + 7b_1 + 9b_0

\end{gather*}

Multiplication is somewhat trickier. Its validity follows from the interpretation of an expansion as a polynomial. Polynomial multiplication itself is equivalent to discrete convolution

\begin{align*}&
\begin{matrix}
\phantom{\cdot~}
111_x \\
\underline{\cdot\ 
\phantom{1}21_x\vphantom,} \\

\phantom{\cdot \ 0}
111_{\phantom{x}} \\
\underline{\phantom{\cdot\ }
2220_{\phantom{x}} \vphantom,} \\
\phantom{\cdot\ }
2331_{\phantom{x}}
\end{matrix} &\qquad&

\begin{gather*}
(x^2 + x + 1)(2x + 1) \\ \\

= 2x^3 + 2x^2 + 2x \phantom{+ 1}\\
\phantom{= 2x^3 } + \phantom{2}x^2 + \phantom{2}x + 1 \\ 
= 2x^3 + 3x^2 + 3x + 1

\end{gather*}
&\qquad&

\begin{gather*}
[1,1,1] * [2,1] \\ 
\begin{matrix}
\textcolor{blue}0 &\textcolor{red}1 & \textcolor{red}1 & \textcolor{red}1 & \textcolor{blue}0 &\\
& & &1 & 2 & =~1\\
& & 1 & 2 & &=~3\\
& 1 & 2 & & &=~3\\
1 & 2 & & & & =~2
\end{matrix}
\end{gather*}

\end{align*}

The left equation shows familiar multiplication, the middle equation is the same product when expressed as polynomials, and the right equation shows this product obtained by convolution. Note that the string of the second argument ([2, 1]) is reversed when performing the convolution.

Without carrying, multiplication and addition are base-agnostic. When doing arithmetic in a particular base, we should obtain the same result even if we perform the same operations in another base.

\begin{gather*}

&18 = 10010_2 &&
5 = 101_2 \\ \\

&
\begin{matrix}
\phantom{\cdot~}
18_{10} \\
\underline{\cdot\
\phantom{1}5_{10}\vphantom,} \\
\phantom{\cdot~}90_{10} \\ \\
=~1011010_2
\end{matrix}
&&

\begin{matrix}
[1,0,0,1,0] * [1,0,1] \\ \\
\begin{matrix}
\textcolor{blue}0 & \textcolor{blue}0 &\textcolor{red}1 & \textcolor{red}0 & \textcolor{red}0 & \textcolor{red}1 & \textcolor{red}0 & \textcolor{blue}0 & \textcolor{blue}0 &\\
& & & & & &1 & 0 & 1 & =~0\\
& & & & &1 & 0 & 1 & & =~1\\
& & & &1 & 0 & 1 & & & =~0\\
& & &1 & 0 & 1 & & & & =~1\\
& &1 & 0 & 1 & & & & & =~1\\
& 1 & 0 & 1 & & & & & & =~0\\
1 & 0 & 1 & & & & & & & =~1\\
\end{matrix}
\end{matrix}
\end{gather*}

In the example above, we multiply 18 and 5 together to obtain 90 in base ten, then convert it to binary. This is precisely the same as converting 18 and 5 to binary, then convolving the strings of digits. Fortunately in this instance, we don’t have to worry about any carries in the result.

Two Times Tables

The strings “10010” and “101” do not contain adjacent “1”s, so they can also be interpreted as the Zeckendorf expansions (of 10 and 4, respectively). This destroys their correspondence to polynomials, so their product by convolution, as a Zeckendorf expansion (when returned to canonical form) is not the product of 10 and 4.

\begin{gather*}
[1,0,0,1,0]_{\text{Zeck}} * [1,0,1]_{\text{Zeck}} = 1011010_{\text{Zeck}} 
= 1100010_{\text{Zeck}} \\
= 10000010_{\text{Zeck}} = 36 \\

\text{Zeck}(10) * \text{Zeck}(4)
= 36 \neq 40 = 10 \cdot 4
\end{gather*}

The process of expanding both terms, convolving, and interpreting can be captured by the operator \odot_{Zeck}. Its definition requires a unique greedy expansion for every integer (which exists), and is defined via convolution (which is commutative), so it is commutative. We can tabulate the results in a times table as follows

The expansions for 0 and 1 are invariably the strings “0” and “1”. When a sequence has length 1, convolution degenerates to term-by-term multiplication. Thus, convolution by “0” produces a sequence of 0’s, and convolution with the string “1” produces the same sequence. Accordingly, the only “correct” columns and rows that appear in the table are the first two. Ignoring them, this array exists in the OEIS (A101330) and is known as Knuth’s Fibonacci product.

Correcting for Errors

The difference between the actual product and the false product can be interpreted as an error endemic to Zeckendorf expansions. If assigned to the symbol \oplus_\text{Zeck}, then the normal product can be recovered as mn = m \odot_\text{Zeck} n + m \oplus_\text{Zeck} n. We can then collect errors into table of their own:

In this table, unsurprisingly, the first two columns are populated entirely by 0’s. The rest of the errors are grouped together in rectangular blocks.

Fibonacci Runs

A pattern can be observed along any column or row (except the first two) or along the main diagonal (where they squares lie). In each, the number of terms the series “hangs” before progressing (i.e., the run lengths) is the same:

\begin{gather*}
RL(0, 0, 1, 1, 1, 2, 2, 3, 3, ...) = \\
RL(0, 0, 2, 2, 2, 4, 4, 6, 6, ...) = \\
RL(0, 0, 1, 1, 1, 4, 4, 9, 9, ...) = \\
2,3,2,3,3,2,3,2,3,3 ...
\end{gather*}

The initial 2 can be ignored since it corresponds to the 0 and 1 rows. If the rest is converted such that 3 \mapsto 0,~ 2 \mapsto 1, then the sequence becomes (truncated to 30 terms):

0,1,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0...

This matches the Fibonacci word (OEIS A3849), a sequence obtained in a similar manner to the typical Fibonacci numbers. Rather than operating on integers by addition, it operates on strings by concatenation. Perhaps this is unsurprising, since Zeckendorf expansions are literally expansions in Fibonacci numbers. The run-length transform is the key to this infinite string, which in effect discards the numbers in the sequence for information about discrete chunks of the sequence.

Visualizing Tables

While a table is a wonderful thing, it does not lend itself well to visualization. WolframAlpha has a feature that produces the multiplication table for a finite field (example).

I’d like to reproduce it with color, but there’s a slight problem. Since we don’t have a finite number of elements, we’ll have to take our tables mod an integer. In the HSV color space, colors are cyclic just like the integers mod n. This actually has an additional appealing feature: two colors with similar hues are “near” in a similar way to the underlying numbers. Then, the entry-to-color mapping can just be given as

k \mapsto HSV \left({2\pi k \over n}, 100\%, 100\% \right)

In this mapping, for n = 2, red is 0 and cyan is 1. The following is a 100×100 image of the multiplication table of \oplus_\text{Zeck} from 0 to 99.

Anima Moduli

This table can by animated by gathering various n into an animation and incrementing n every frame. Before applying this technique to an error table, I find it prudent to apply it to standard addition and multiplication tables first.

Both images appear to zoom in as the animation progresses. Unsurprisingly, addition produces diagonal stripes, along which the sum is the same. Multiplication produces a squarish pattern (with somewhat appealing moirés).

Tables for \odot_\text{Zeck} and \oplus_\text{Zeck} should resemble the table to the right, since their definition relies on it.

The zooming is still present. At later frames, both tables share the same “square rainbow” pattern, but the error table is closer. Though both tables appear to have a repeating pattern, the blocks in the error table are still irregularly shaped, as in the mod 2 case.

The error table also demonstrates (for a given modulus) how much the series differs from a geometric series. We know there will always be an error since, while Fibonacci numbers grow on the order of O(\phi^n), the place values is only \phi in the limit.

Other Error Tables

These operations can can also be defined in terms of any other series expansion (i.e., integral system). Rather than showing both of the multiplication and error tables, I will elect to show only the latter. The error table is more fundamental since the table for \odot can be constructed from it and the normal multiplication table.

The error tables for some of the previously-discussed generalizations of the Fibonacci numbers are presented below.

Pell, Jacobsthal

Of the two tables, the Pell table looks more similar to the Fibonacci one. Meanwhile, the Jacobsthal table has frames which are significantly redder than the either surrounding it. These occur on frames for which n is a power of 2, which is a root of the recurrence polynomial.

n-nacci

Compared to the Fibonacci image, the size of the square pattern in the Tribonacci and Tetranacci images is larger. Higher orders of Fibonacci recurrences approach binary, so in the limit, the pattern disappears, as if the slowly-encroaching red corner is all that remains.

Other

Of course, integral systems are not limited to linear recurrences, and tables can also be produced that correspond to other integer sequences. For example, the factorials produce distinct patterns at certain frames. The Catalan numbers (which are their own recurrence) mod 2 appear to be constructed from regular blocks of XORs. To prevent the page from getting bloated, these frames are presented in isolation.

Additional tables which I find interesting are:

• Triangular Numbers (recurrence \langle 3, \bar{3}, 1|)
• Square Numbers
• Padovan Numbers (recurrence \langle 0,1,1|)
• \langle 1, 1, 2|, based on the first 3 Catalan numbers

Closing

Even if not particularly useful, I enjoy the emergent behavior apparent in the tables. Even for typical multiplication, this visualization technique shows regular patterns which appear to “grow”. Meanwhile, the sequence products frequently produce a pattern that either repeats, or is composed of many similar elements.

My first attempt to map integers to colors was to consider the prime factorization of each integer. The largest number in the factorization was related to the hue, and the number of terms in the factorization was related to the saturation. Results were not great.

While I rendered these animations as GIFs, I also attempted to convert some of them to MP4s in hopes of shrinking the filesize. However, this is a use case where the MP4 is larger than the GIF, at least without compromising on resolution. This is a case when space-compression beats ill-suited time-compression.

The project that I used to render the images can be found here. I didn’t put much thought into command line arguments, nor did I build in many features. As an executable, it should be completely serviceable to generate error tables based on recurrence relations; the GHCi REPL can be used for more sophisticated sequences.