Polynomial Counting: Binary and beyond

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

Before I start, I’d like to introduce some shorthand. Since we prefer (monic) polynomials which may correspond to linear recurrences, it is useful to use an ordered tuple of their coefficients.

\begin{gather*} x^{n+1} - a_0 x^n - a_1 x^{n-1} + ... - a_{n-1} x - a_n \iff \langle a_0, a_1, a_2, ..., a_{n-1}, a_n | \end{gather*}

I choose this notation because the left angle bracket points in the direction of the carry. For example, the Fibonacci numbers satisfy the recurrence $\langle 1, 1|$ . Equally, $\phi$ is the unique positive root of $\langle 1, 1|$ . In the future, I’ll refer to these tuples as “carries” for simplicity.

The Silver Ratio

The golden ratio is actually the first member of a sequence of metallic ratios. They are the roots of the polynomials $x^2 - nx - 1$ or $\langle n, 1|$ in the newly introduced notation. The next member (n = 2) is termed the silver ratio. It value is $\delta_s = 1 + \sqrt 2 \approx 2.414...$ .

Like the the golden ratio corresponds to the Fibonacci numbers, the silver ratio corresponds to the Pell numbers (OEIS A000129). The Pell numbers begin $0, 1$ like the Fibonacci numbers, but instead have the recurrence $a_{n+1} = 2a_n + a_{n-1}$ , and the sequence continues as $2, 5, 12, 29...$

With this relationship in mind, we can construct the (fractional) silver ratio system and the (integral) Pell number system. $\delta_s$ is bounded above by the integer 3, which is also strictly greater than the coefficients in $\langle 2 1|$ . Therefore, it would make sense to derive the expansion of 3 in the same way as the golden ratio expansion of 2

\textcolor{red}{3} = 2.\textcolor{red}{21} = \textcolor{blue}{2.2}1 = \textcolor{blue}{1}0.11

Consequently, the expansions for the integers up to 10 are as follows:

	Silver Ratio   Pell Numbers
	     __
	 210 12       5 2 1
0 	   0              0
1 	   1              1
2 	   2            1 0
3 	  10.11         1 1
4 	  11.11         2 0
5 	  20.01       1 0 0
6 	 100.01       1 0 1
7 	 101.01       1 1 0
8 	 102.01       1 1 1
9 	 110.12       1 2 0
10 	 111.12       2 0 0

Weighing the Silver

Alternatively, we may choose a balanced alphabet ( $\{\bar{1}, 0, 1\}$ ) to express these expansions. Because the carry is two place values wide, defining a canonical expansion is particularly tricky. Instead of the string “21” being illegal, it could be either of:

\begin{align} 11_{\delta_s} &= 1\bar{1}0_{\delta_s} &&\iff& \bar{1}\bar{1}_{\delta_s} &= \bar{1}10_{\delta_s} \\ 10_{\delta_s} &= 1\bar{1}\bar{1}_{\delta_s} &&\iff& \bar{1}0_{\delta_s} &= \bar{1}11_{\delta_s} \end{align}

We prefer expansions to allow (2) rather than (1) since “0”s can be padded to (or removed from) either side indefinitely. Also, a standard conversion of the string “2” results in $10.\bar{1}$ , which resembles (2).

The balanced expansions are as follows:

	Silver Ratio   Pell Numbers
	     ___
	3210 123     12 5 2 1
0 	   0                0
1 	   1                1
2 	  10.T            1 0
3 	 1T0.T          1 T 0
4 	 1T1.T          1 0 T
5 	 10T.01         1 0 0
6 	 100.01         1 0 1
7 	 101.01       1 T 0 0
8 	1T00.T1       1 T 0 1
9 	1T01.T1       1 T 1 0
10 	1T1T.10T      1 0 T 0

Swapping the 2

The Jacbosthal numbers (OEIS A001045) are a similar series to the Pell numbers. They are defined by swapping the Pell number recurrence coefficients, giving $\langle 1, 2|$ . The sequence is “seeded” with $0, 1$ as before, producing $1, 3, 5, 11, 21\dots$ . Since the coefficients are still bounded 3, we can try deriving its expansion

\textcolor{red}{3}00 = 2\textcolor{red}{12} = \textcolor{blue}{21}2 = \textcolor{blue}{1}1\bar{1}2

Unfortunately, there’s not a clear way to progress. Carrying the rightmost “2” to the left undoes our work, and expanding it to the right just adds another 2. Perhaps the problem is with its expansion

\begin{gather*} \textcolor{red}{2}00 = 1\textcolor{red}{0}\bar{1}2 ; \quad 0 = 1\bar{2}\bar{1}2 = \bar{1}21\bar{2} \\ \\ \begin{align*} 2.0000 &= \phantom{+}10.\bar{1}200 \\ + 0.0000 &= + \phantom{1}0.1\bar{2}\bar{1}2 \\ \hline \vphantom{2^{2^2}}\phantom{+}2.0000 &= \phantom{+} 10.00\bar{1}2 \end{align*} \end{gather*}

Since the symbol “2” still appears in the expansion we can continue carrying and cancelling. If continued ad infinitum, we get an infinite string of “0”s. When this is chopped off, the final string is “ $2 = 10$ “, which is obviously the same rule as binary.

Actually, it turns out that the roots of the polynomial $\langle 1, 2|$ are 2 and -1. The whole time, the polynomial was reducible! Moreover, an extended alphabet ended up being ultimately unnecessary. The integral base is not so fortunate, and requires the extra symbol “2”:

	Binary   Jacobsthal Numbers
	    
	3210        5 3 1
0 	   0            0
1 	   1            1
2 	  10            2
3 	  11          1 0
4 	 100          1 1
5 	 101        1 0 0
6 	 110        1 0 1
7 	 111        1 0 2
8 	1000        1 1 0
9 	1001        1 1 1
10 	1010        2 0 0

Numbers which include a 2 in their integral expansion seem to align with the sequence OEIS 003158.

Adding a Negative

Another simple modification to the Pell numbers is the recurrence $\langle 2,\bar{1}|$ . The sequence produced from $0, 1$ is $2, 3, 4, 5...$ , which are just the natural numbers. Since 2 still bounds (the absolute values of) the numbers in the recurrence, the binary alphabet still makes sense. Consider two expansions of 2 as below:

\begin{align*} \textcolor{red}{20} &= 1\textcolor{red}{01} \\ \textcolor{red}{2}000 = 1\textcolor{red}{2\bar{1}}0 &= 1\textcolor{blue}{2}\bar{1}0 = 11\textcolor{blue}{1\bar{1}} \\ \end{align*}

In all of these expansions, the sum of the digits (or digital root) is 2. This is similar to the degenerate “positional” system unary, where the magnitude of the number is just its length in tally marks. The empty string signifies 0, “1” signifies 1, “11” signifies 2, and so on.

Looking at the polynomial $\langle 2, -1|$ a little closer, this is clearly the polynomial $x^2 - 2x + 1 = (x - 1)^2$ . Expansions in unary and in the naturals are as follows:

	Unary     Naturals
	    
	3210      4 3 2 1
0 	                0
1 	   1            1
2 	  11          1 0
3 	 111        1 0 0
4 	1111      1 0 0 0

The lengths of the strings in both expansions match up. However in unary, the place values never grow from 1, while the naturals are unbounded.

The carry is applied in slightly different ways between the systems. In unary, it keeps the digital root consistent (if one introduces negative tallies), and in the naturals, the relationship $20 = 101$ is equivalent to the expression $2x = (x+1) + (x -1)$ .

Our carry can be even worse than this. Consider $\langle 1, \bar{1}|$ . The simple string “1” duplicates itself indefinitely in either direction:

0\textcolor{red}{10} = \textcolor{red}{1}01

The roots of $x^2 - x + 1$ are complex and have magnitude 1. While a well-defined counting system can arise from carries with negative numbers, complex numbers clearly require some care.

Conjecture of Validity

After the experimentation in this article, I can now make claims about whether or not a polynomial is “valid” for counting.

Positive Carries

Systems like those based on the golden and silver ratios ( $\langle 2,1|$ ) have carries with “nice” coefficients. To ensure that situations like the Jacobsthal base ( $\langle 1,2|$ ) do not occur, I prefer carries which are irreducible and of the form

\langle a_n, a_{n-1}, a_{n-2}, ..., a_0| , \quad a_n \geq a_{n-1} \geq a_{n-2} \geq ... \geq a_0 \geq 0

In other words, the numbers which appear in the carry are strictly positive and monotonically decreasing. Since $a_n$ bounds the coefficients, we use the alphabet bounded above by $a_n + 1$ .

While “normal” carries follow this scheme, they only have a single carry rule. Irrational bases typically have a second rule, which as it turns out, is equivalent to multiplying the carry by $(x - 1)$ .

\begin{gather*} \text{Phinary:} & (x^2 - x - 1)(x - 1) = x^3 - 2x^2 + 1 = 1\bar{2}01 \\ \text{Silver Ratio:} & (x^2 - 2x - 1)(x - 1) = x^3 - 3x^2 + x + 1 = 1\bar{3}11 \\ \text{Jacobsthal:} & (x^2 - x - 2)(x - 1) = x^3 - 2x^2 - x + 2 = 1\bar{2}\bar{1}2 \end{gather*}

I choose to call these carries implicit. Importantly for the valid bases, there is only a single negative term among all the positive terms. It describes the way in which a particular numeral “flows” into adjacent place values.

Reducible polynomials like the Jacobsthal one must have two integer roots, meaning that expansions have to conform to both bases simultaneously. Quadratic polynomials like this have the form: $(x - m)(x - n) = x^2 - (m+n)x + mn$ . The latter term, as a product, grows faster than a sum, so fortunately these kinds of polynomials are rare (with the restriction given).

Negative Terms

The (valid) strings produced before by multiplying $x - 1$ into the carry have only one term with opposite sign from the rest. Therefore, we might dream up carries with a single positive term among all of the negatives. Like “2” in phinary, this positive term is the largest weight which can appear in the alphabet.

One must take special care with the sum of terms in the carry. $\langle 2,\bar{1}|$ is valid, but $\langle 1,\bar{1}|$ is not. The sum of the entries in the former is 1, while sum of the latter’s is 0. Both of these are actually off by one due due to the highest term of the monic polynomial. The true digital roots are 0 and -1 respectively. The latter implies that the digital root of an expansion is unbounded, and this can be seen with $\langle 1, \bar{1}|$ .

In other words, the single positive term must be at least 1 greater than the negative of the sum of the remaining terms.

\begin{gather*} \langle a_n, a_{n-1}, a_{n-2}, ..., a_0| ,~ \text{ for } \sum_{i = 0}^{n}{a_i} \geq 1 \\ \max(a_i) = a_{max} > 0 \ge a_i, ~ i \neq p \end{gather*}

Since these carries directly describe the rule for expanding the largest numeral, I refer to these carries as explicit.

In fact, the carry polynomials in these systems need not be monic. The only restriction is that all terms but one have the same sign, and that the remaining term dominates the rest (meaning the polynomial has a negative value when evaluated at 1). This is a complicated matter which I will not be delving into.

Closing

Polynomials with roots with magnitude 1 (but are not equal to 1) are a bit tricky to deal with. Again with regards to $\langle 1,2|$ , the expansion for 2 was only achieved after assuming an infinite application of carries converged. Enough has been said about $\langle 1, \bar{1}|$ to disqualify it. This polynomial belongs to a family called cyclotomic polynomials, which have complex roots of 1 as their roots. I’ll have more to say about cyclotomic polynomials in the future, but by themselves, they cannot be carries.

Since higher numbers appearing in carries are somewhat scary, the next post will focus on two more generalizations of the Fibonacci numbers and exceptions to the above rules.