Six Operations

It fascinates me that we can use the function P to pack an arbitrarily long (but finite) array of arbitrarily large positive integers into a matrix of just four arbitrarily large nonnegative integers. That, too, goes to show that infinity is strange.

For comparison, here are two of the many ways of packing arbitrarily many numbers into a single number. We can use the numbers as the digits of a number in base N, but that only works if the number of possible digits is finite. Or, we can use Gödel numbering, like so, …

2^a₀ 3^a₁ 5^a₂ 7^a₃ 11^a₄ 13^a₅ 17^a₆ 19^a₇

… but that's not computationally convenient because we can't do much of anything with the resulting number except unpack it.

The function P doesn't have either of those disadvantages. In particular, it's computationally convenient, and to prove it, I'll show you six useful operations on packed matrices that require no more than a single matrix multiplication each. I'm going to reuse the example from The Discriminant, so here's the result of running the second algorithm on one iteration of [1,2,3,4].

		1	2	3	4
0	1	1	3	10	43
1	0	1	2	7	30

Here's the matrix that we get.

43	10
30	7

And here are the six operations.

1. We already know that we can concatenate expansions by multiplying the matrices. In particular, we can add any number of coefficients to an expansion as either a prefix or a suffix.
2. We also already know that we can reverse an expansion by taking the transpose of the matrix.
3. We can read the first coefficient of an expansion. The key is to strip away all the abstraction and remember that the original purpose of the second algorithm was to compute convergents, not matrices. So, in the example, we can look at the first column of the matrix and see that the finite expansion [1,2,3,4] has the value 43/30. Then we can start running the first algorithm and see that the first coefficient is the integer part of 43/30.

   We do have to consider two special cases.

   First, if the number from the first column is infinite, then the matrix is the identity matrix, the expansion is empty, and there is no first coefficient.

   Second, the first algorithm only produces proper forms, but one iteration of a repeating expansion might look like an improper form. So, if the number from the first column is an integer, we need to check the entry in the lower right corner of the matrix. If it's zero, the expansion is the proper form [a], and we're done. Otherwise, the expansion is the improper form [a−1,1], and we need to subtract 1 to get the correct first coefficient.

4. We can read the last coefficient by reversing the expansion and then reading the first coefficient. So, in the example, we can look at the first row of the matrix and see that the last coefficient is the integer part of 43/10.

   The same special cases apply here.

5. We can remove the last coefficient (after reading it) by running the second algorithm backward for one step.

   43 − 4 ×	10	= 3
   30 − 4 ×	7	= 2

   Here's the resulting matrix.

   10	3
   7	2

   Equivalently, we can multiply by P₁(a)⁻¹ on the right.

   P1(a)−1 = 0	1
   1	−a

6. We can remove the first coefficient (after reading it) by reversing, removing the last coefficient, and reversing. Equivalently, we can multiply by P₁(a)⁻¹ on the left.

Finally, let's continue the train of thought from point 3.

1. If we keep running the first algorithm, we can read more coefficients, or even the whole expansion. In other words, we can unpack the matrix! That requires effort linear in the number of coefficients, so it doesn't belong in the list above, but it's definitely a useful operation. It's also the clever way that I was looking for near the end of Group Elements and Matrices.

   The same special cases apply here, with a few adjustments.

   First, if the number from the first column is infinite, then the matrix is the identity matrix and the expansion is empty.

   Second, we need a more general way to check whether the expansion is proper or improper. But that's easy enough! With one exception, an expansion is improper if and only if it ends in 1, so we can check just by reading the last coefficient. The exception is that the proper form [1] ends in 1, but even in that case there's no ambiguity because the improper form [0,1] can't be used as a repeating expansion.