The single most common method of representing numbers in the modern world is in positional numeral system. Despite being taught in early grade school, it is the result of millennia of mathematical thought.
The decimal system we use today assigns integers to expansions consisting several symbols called numerals next to each other. Each numeral is positioned at a place value, which has a value ten times greater than its neighbor to the right and a tenth as much of its neighbor to the left. Due to place values sharing a constant ratio of ten, the system is called decimal.
\begin{align*}
\scriptsize 10^2 && \scriptsize 10^1 && \scriptsize 10^0 && \scriptsize 10^{-1} &
\quad \} \quad \text{Place values} \\
4 && 3 && 2 .&& 1 &
\quad \} \quad \text {Numerals: 1, 2, 3, 4} \\
\hline
\end{align*} \\
\text{Four hundred, thirty-two, and one tenth}It is difficult to write about the way we represent numbers without inadvertently reverting to the default of decimal. I will take care to write out each number explicitly in English when I mean that number. Conversely, when I want to refer to the symbols themselves, I will enclose them in quotes; for example, “0” refers to the symbol 0.
A Brief History
As I mentioned, this practice is millenia old. Before proceeding, I would like to discuss its history.
Arguably, this practice began with the Babylonians (circa eighteenth century BC), who instead used a sexagesimal (base sixty) system. It lacked a “decimal point” (more properly a sexagesimal point, fractional separator, or radix point), meaning that a representation could equally as well refer to thirty (30) or one-half (1/2), or one hundred and eight thousand (108000), since all these numbers differ by a power of sixty (60). This system lacked a “0” symbol to represent an empty place value, opting instead to simply skip them. Thus, the onus was on the arithmetician to properly align digits, maintain spacing, and correctly interpret results. Despite these limitations, it was robust enough to develop basic trigonometry and approximate the square root of 2.
Later, Indian mathematics developed its own place value system — this time in the familiar base ten — at least by the time of Aryabhata (4th century AD). It introduced the empty “0” symbol that the Babylonian system lacked. Eventually, this system made its way to Europe by means of the Arabs. The 16th century Dutch engineer Simon Stevin was one of the first individuals to introduce a “decimal point”. Though modern notation differs slightly from his, it introduced (or perhaps re-introduced) a simple means of adding and multiplying fractions. Needless to say, this has become so popular as to become one of the most predominant ways to express integers and nonintegers alike.
Later thought realized bases other than ten were possible; for example, binary (base two) due in part to Leibniz. The strangest are non-integral bases, for example the complex base 2i due to Knuth. However, I find bases which rely on irrational numbers to be the most interesting.
Staying Golden
The golden ratio, a number with many apocryphal attributions, was the favorite of many Greek mathematicians. As such, it was originally recognized in the context of geometry, long before the development of algebra. It is constructed by dividing a line segment such that the ratio between the longer and shorter sub-segments is the same as the ratio between original segment and the longer one.
Phrased in modern algebraic language, the golden ratio \phi[katex] is the unique positive root of the polynomial [katex]x^2 - x - 1, expressed as \frac{1 + \sqrt 5}{2} \approx 1.618…. Despite its name, this number is irrational, since it cannot be represented as a ratio of integers. Furthermore, raising it to any integral power does not produce an integer.
It might seem inconceivable that one may obtain an integer (other than zero or one) by summing powers of \phi. However, base \phi, also called phinary, does in fact exist. Here is a list of (canonical) expansions up to 10
0 0
1 1
2 10.01
3 100.01
4 101.01
5 1000.1001
6 1010.0001
7 10000.0001
8 10001.0001
9 10010.0101
10 10100.0101We can obtain the entries on this list in two ways: generally and imprecisely, or directly and complexly.
The General Approach
In the most general sense, an expansion is just a sequence of integers, or digits. We can recover the value by summing the products of the integers by their place values. For example, a decimal number has the form
x = ({a_n a_{n-1}... a_1 a_0})_{10} = a_0 \cdot 10^0 + a_1 \cdot 10^1 + ... + a_{n-1} \cdot 10^{n-1} + a_n \cdot 10^{n}Of course, negative indices may also be used, but these have been omitted for horizontal space.
This equivalence means that we can convert to and from a particular base. Naively, we might use the following "greedy" algorithm to derive the base b expansion (also called a \beta-expansion) of a number x
\begin{align*}
&x_0 = x \\
&\text{while}\ x_i > \epsilon &&
\textcolor{blue}{\text{While we're not precise enough}}\\
&\qquad p = \lfloor log_b {~x_i} \rfloor &&
\textcolor{blue}{\text{Get the place value $p$}} \\
&\qquad a_p = \left \lfloor \frac {n_i} {b^p} \right \rfloor &&
\textcolor{blue}{\text{Place the correct digit in the $p^\text{th}$ place value}} \\
&\qquad x_{i+1} = x_i -\ a_p \cdot b^l &&
\textcolor{blue}{\text{Subtract out the value we just added to the expansion}} \\
&\text{end}
\end{align*}There are three problems with this.
- It is inexact. The x_i get smaller, but we can only ever approximate the result. For numbers smaller than the tolerance \epsilon, it is outright wrong.
- If p goes negative, a naive computation requires floating point arithmetic.
- Algebraic extensions may be used, but this requires additional complexity.
- It relies on a transcendental function, the logarithm. One may approximate it by repeated division, but in general, it is practical to use the floating point operation.
Modern FPUs are fairly good at handling the latter two operations, but they are necessarily approximate. Fortunately for phinary, there is a direct method which remedies all these issues and produces exact results without floating point operations.
Deriving Expansions
Take another look at the representations above. Much like binary, phinary only requires the digits 0 and 1. Another slightly less obvious fact is that the string "11" does not occur in the expansion. This is because we can rewrite the polynomial as the following
\begin{gather*}
x - 2 = 0 \implies
\left. \begin{align*}
x &= 2 \\
10_x &= 02
\end{align*} \right\} & \text{Binary}
\\ \\
\phi^2 - \phi - 1 = 0 \implies
\left. \begin{align*}
\phi^2 &= \phi + 1 \\
100_\phi &= 11_\phi
\end{align*} \right \} & \text{Phinary}
\end{gather*}This shows a connection between polynomials and positional notation which is not at all obvious. The second lines leverage positional notation in lieu of a symbol; their literal interpretation is the same as the first line.
When we multiply or divide by ten in decimal (or two in binary), we shift the digits left or right. Likewise, we may multiply or divide by \phi on either side of the equation. Thus, it is also true that
\begin{gather*}
\left.
\begin{align*}
2^2 &= 2\cdot 2 &&\iff&
100_2 &= 20_2 \\
1 &= 2\cdot 2^{-1} &&\iff&
1_2 &= 0.2_2
\end{align*}\right \} & \text{Binary}
\\ \\
\left.
\begin{align*}
\phi^3 &= \phi^2 + \phi &&\iff&
1000_\phi &= 110_\phi \\
\phi &= 1 + \frac 1 \phi &&\iff&
10_\phi &= 1.1_\phi
\end{align*}\right \} & \text{Phinary}
\end{gather*}Since this relationship holds for any adjacent place values, it is analogous to "carrying" in base ten. In decimal, we care if a single place value exceeds ten, and its excess goes into the next place value. In phinary, we care if there are two "1"s in adjacent place values, and do the same.
More generally, we can look at expansions not restricted to the symbols "0" and "1" and do similarly
\begin{align*}
32_\phi &= 121_\phi \\
0.61_\phi &= 1.5_\phi
\end{align*}Thinking a little more cleverly, we can decompose 2 as
\begin{align*}
\textcolor{red}{2} = 1.\textcolor{red}{11}_\phi =
\textcolor{blue}{1.1}1_\phi &= \textcolor{blue}{1}0.01_\phi \\
2 &= \phi + \phi^{-2}
\end{align*}Using this rule, we can learn how to count in phinary. We count in base ten by incrementing the ones digit (or 0th place value) and carrying tens to higher digits. In phinary, we have two carry rules, which we repeat until we cannot:
- Express "011" as "100"
- Express "0200" as "1001"
Both of these rules hold for larger digits as well, for example:
\stackrel{\text{Carry 033 = 300}}{
00\textcolor{red}{043}_\phi =
00\textcolor{red}{310}}_\phi =
\stackrel{\text{Carry 0200 = 1001}}{
0\textcolor{blue}{0310}_\phi =
0\textcolor{blue}{1111}}_\phi =
0\textcolor{green}{11}\textcolor{orange}{11}_\phi =
\textcolor{green}{1}0\textcolor{orange}{1}00_\phiAggressively applying these rules results in the same expansion as the greedy algorithm.
The Other Root
As a quadratic, the polynomial x^2 - x - 1 has two roots: \phi and its conjugate \phi^* = -\phi^{-1}. This implies that each phinary string can be interpreted by either root.
\begin{align*}
5 = 1000.1001_{\phi_{\phantom{*}}}
&= \phi^3 + \phi^{-1} + \phi^{-4} \\
\phantom{5} = 1000.1001_{\phi^*}
&= ((-\phi)^{-1})^3 + ((-\phi)^{-1})^{-1} + ((-\phi)^{-1})^{-4} \\
&= \phi^{4} -\ \phi -\ \phi^{-3} \\
&= 10000_\phi -\ 10.001_\phi
\end{align*}Since -\phi^{-1} is negative, its powers alternate between positive and negative. Also, since its magnitude is less than 1, place values to the right of the radix point are larger than 1, the inverse of what one is used to with base ten.
Proceeding onwards,
\begin{align*}
10000_\phi &= 1100_\phi = 1011_\phi = 1010.11_\phi \\
&= 1010.1011_\phi \\
1000.1001_{\phi^*} &= 10000_\phi -\ 10.001_\phi \\
&= 1010.1011_\phi -\ 10.001_\phi \\
&= 1000.1001_\phi
\end{align*}And we breathe a sigh of relief since these expansions are equal. This is perhaps one of the reasons phinary expansions seem so verbose.
Fibonacci and Zeckendorf
Instead of assigning place values to powers of the base, we can instead imagine a situation where the place values correspond to the values of a sequence, in particular the Fibonacci numbers. Phi also turns up when discussing this sequence, or more generally, sequences generated by the recurrence a_{n+1} = a_n + a_{n-1}. This bears a startling resemblance the the polynomial mentioned above, with cursory examination by generating functions revealing the connection.
Fibonacci numbers are all integers, so sums of them can only express integers. This is called the Zeckendorf expansion. We assign place values to unique Fibonacci numbers starting with the second 1. Hence, one is "1" and not "10".
Analogously to the algorithm above, we may derive an expansion for a number by subtracting out the largest Fibonacci number less than it (possibly multiple times) and repeating with the remainder. Expansions of the integers up to 10 are:
0 0
1 1
2 10
3 100
4 101
5 1000
6 1001
7 1010
8 10000
9 10001
10 10010Not only are these representations very similar to the phinary strings above, but they are also all binary strings that do not contain two consecutive 1's (OEIS A014417). This representation is exactly as arbitrary as preferring the greedy phinary representation; instead, this is the "greedy series expansion" of an integer in the Fibonacci numbers.
Similar relationships apply here like they do on phinary expansions. For one, the relationships "011" = "100" and "0200" = "1001" hold. However, we must take care near the 0th place value
8 5 3 2 1 | 1 ~
2 2
1 0 . 0 1
1 0
4 2 0
1 0 0 . 1
1 0 1In the expansion of 2, the rightmost "1" seems to underflow. However, in the expansion of 4, we must consider the second "1" in the negative first place value. It acts as a sort of temporary storage which is immediately transferred into the actual place value.
Synthesis: Generalizing Phinary
By starting with the golden ratio base, many natural questions arise. Does this approach work with other quadratic roots? Are there any restrictions on the coefficients (or sequences)? Does it work with any polynomial with positive roots? Are only monic polynomials allowed? What digits are minimally necessary to represent any integer? How "canonical" can "canonical" really be?
Rather than answering these questions or giving proofs, I think it's best to lay some ground rules. Using the above examples, I have defined two genera of positional number systems:
- A fractional number system is one where the place values are determined by the powers of the root of a polynomial with integer coefficients. The "fraction" in fractional comes allowing negative powers of our base. Therefore, we can represent rational numbers and use a fractional separator.
- Naturally, the decimal system currently in use fits in here, corresponding to the polynomial x - 10.
- Likewise, phinary corresponds to the polynomial x^2\ - x\ - 1.
- An integral number system is one where the place values are given by a strictly increasing integral sequence. It can express only integers and there is no fractional separator.
- As an example, the sequence produced from powers of an integer (e.g.: 1, 2, 4, 8, …), correspond to a "normal" system without support for fractions.
- The already-discussed the Fibonacci base fits here as well. In fact, since linear recurrence relations correspond to polynomials, this extends to a correspondence between an integral system and a fractional one.
- Other sequences are also valid, like the square numbers. In the "square number base" we know the digital root (of canonical expansions) never exceeds 4 due to Lagrange's four-square theorem.
Alphabets
A positional number system not only has place values, but a numeral alphabet. In standard decimal, there are ten distinct symbols including "0": {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. The choice of symbols is arbitrary (it can vary with language), but each has a weight, the integer quantity assigned to them. In the modern world, Arabic numerals are standard and distinct from alphabetic characters, so the distinction between "weight" and "symbol" can be ignored by using them conventionally for the first ten whole numbers. Subsets of this alphabet include the binary alphabet, {0, 1}, and the ternary alphabet, {0, 1, 2}.
A minimal alphabet for a number system is an alphabet of the smallest size which can still represent every integer. It is most convenient to consider an alphabet of integers from 0 up to a particular value, even though it may be true that minimal alphabets might exist which "skip" over certain weights.
It is often useful to be able to borrow a symbol of a certain weight, even if it would not be present in a minimal alphabet (for example, using "2" when it is convenient to do so, as above). In this manner, it is also possible to interpret the representation of a number in one base in another arbitrary base.
Balanced alphabets also exist, which contain negative numeral weights. For example, the balanced ternary alphabet consists of the weights of \{-1, 0, 1\}. Powers of 3 always determine the place values in ternary, but expansions change to suit the alphabet. To conserve horizontal space, I'll use the symbols \bar{1} and "T" to signify -1.
Canonicity
Finding the canonical expansion of a number should be as simple as incrementing the 0th place value and aggressively applying the carry. For fractional systems, this amounts to adding 1 the 1's digit, and for integral ones, adding it to the rightmost. However, note that irrational systems have at least two carry rules. In phinary, these are the "011" = "100" rule, and the "0200" = "1001" rule.
Questions About the Above Rules
One may take several exceptions with these definitions and the restrictions they impose, to which I will offer a brief dismissal:
Why limit alphabet weights to integers?
Integers and integer arithmetic are fundamental systems with very straightforward addition and multiplication. Adding more complex rules by introducing fractions or polynomial roots creates unnecessary complications.
Why prefer weights of integers from 0 to n (or if balanced, -n to n)?
Alphabets are best kept inductive. Either a weight is the largest possible or its successor is also a weight. ?If we start with a negative weight, this includes balanced alphabets.
Unbounded alphabets have their uses. For example, we might hold off from carrying until necessary, or prefer expansions like 21_\phi = 1 + 2\phi to 21_\phi = 1000_\phi = \phi^4.
The inductive base case, the binary alphabet, is fairly important for two reasons:
- Expansions can always be padded with 0s to produce other valid expansions.
- If "1" does not exist in the alphabet, it should be derivable in some way from other symbols like "2" and "3".
Do we prefer monic polynomials?
The recurrence relation corresponding to a non-monic polynomials must cycle mod the leading term. The simplest (only?) examples are just geometric series, in other words normal integral systems.
For example, the powers of 3 satisfy 2a_{n+1} = 5a_n + 3a_{n-1}. But the RHS simplifies:
2a_{n+1} = 5a_n + 3a_{n-1} = 5a_n + a_n = 6a_n \\
a_{n+1} = 3a_nIncidentally, 3 is a root of 2x^2 - 5x - 3 . Fermat's little theorem is likely a component in proving this generally.
Why exclude transcendentals from fractional systems?
Convergent series like \exp{x} require coefficients which shrink quickly, far below a magnitude of 1. This conflicts with our expectation of counting polynomials to be integral polynomials. This is disappointing, since relatively simple (in terms of continued fractions, combinatorics, etc) transcendental like e relies on a series in rationals.
Closing
With these restrictions in mind, I wrote a simple Haskell library to help explore these systems (found here). The next post will discuss quadratic polynomials with larger coefficients than 1, and problems not discussed with higher expansions.