When a Number System Loses Uniqueness: The Case of the Maya - Place-Value Systems

Author(s): 
Pedro J. Freitas (Universidade de Lisboa) and Amy Shell-Gellasch (Beloit College)

Our modern Indo-Arabic base \(10\) place-value system eventually became the predominant system of all the various systems used throughout history (although it can be argued that a base \(12\) system would be more user-friendly given the larger number of divisors of \(12\) compared to \(10\)). Encoded in our system is the value of the number decomposed as a sum of multiples of powers of ten. Any whole number can be written as a sum of powers of \(10\) in the following way: \[a_0+a_1\,10+a_2\,10^2+\cdots+a_k\,10^k,\quad\quad\quad\quad (1)\] where each \(a_i\) is one of \(0,1,2,3,4,5,6,7,8\) or \(9.\) (The system can be extended to represent any decimal fraction, rational or irrational. Decimal fractions did not appear until the 16th century.)

To take a completely arbitrary example, Amy's dog Isabel was born on May 4th, 2006.

Isabel

Figure 1. Isabel is a five-year-old Keeshond.

If we encode Isabel’s birth date as \(5042006,\) it would be represented as: \[5(10^6 )+0(10^5 )+4(10^4 )+2(10^3 )+0(10^2 )+0(10^1 )+6(10^0 ).\] Note that in keeping with writing the most signficant digit on the left, we have reversed the order of the powers to align with the written number. Notice that, when writing a generalized expansion as in expression (1) above, we write in ascending powers of ten, but when we expand an actual number, we write in descending powers so as not to confuse the numerical order of the digits as compared to the actual written number.

Likewise, given any natural number \(b\,\,(> 1)\) as a base, any integer can be written as sums of multiples of powers of \(b\) in the following manner: \[a_0+a_1\,b+a_2\,b^2+\cdots+a_k\,b^k,\quad\quad\quad\quad (2)\] with all coefficients \(a_i\) satisfying \(0\le{a_i}\le{b-1}.\)

In addition to base \(10,\) two of the most ubiquitous number systems in use today are base \(2\) and base \(16,\) binary and hexadecimal respectively, used in computing. For example, in ASCII, every key stroke has one 8-bit binary representation and every 8-bit binary number represents a key stroke. To continue Amy's dog example (have to keep up with Elvis, the dog who does calculus, you know), suppose we wanted to convert Isabel's birth date into a hex number to see what her “true color” was. To express any integer \(n\) in a certain base, one of two iterative division algorithms can be used.

The “top-down” division algorithm works as follows. Divide \(n\) by the largest power of the base smaller than or equal to \(n.\) That quotient is the most significant, or leading, digit. The remainder is then divided by the next highest power of the base and so on. So Isabel's hex number is found as follows:

\(5042006\) \(=\) \(4(16^5)+847702\)
  \(=\) \(4(16^5)+12(16^4)+612704\)
  \(=\) \(4(16^5)+12(16^4)+14(16^3)+3926\)
  \(=\) \(4(16^5)+12(16^4)+14(16^3)+15(16^2)+86\)
  \(=\) \(4(16^5)+12(16^4)+14(16^3)+15(16^2)+5(16^1)+6\)

So we can write \({5042006}_{10} = {4(12)(14)(15)56}_{16}.\) Since hex needs more than ten digits (16 to be exact), the first six capital letters are used to denote ten through fifteen respectively. So Isabel's hex number is \(4CEF56.\)

It is important to note that this division algorithm is a greedy algorithm in that it fills the largest place value fi rst by taking as large a "bite" as possible at each stage.

In the "bottom-up" algorithm, based on the Euclidean algorithm, we divide \(n\) by \(b,\) and take the remainder as the least signi ficant digit. Then we consider the quotient, and iterate the procedure. In our case, we get

\(5042006\) \(=\) \(6+315125\times{16}\)
  \(=\) \(6+(5+19695\times{16})\times{16}\)
  \(=\) \(6+5\times{16^1}+19695\times{16^2}\)
  \(=\) \(6+5\times{16^1}+15\times{16^2}+1230\times{16^3}\)
  \(=\) \(6+5\times{16^1}+15\times{16^2}+14\times{16^3}+76\times{16^4}\)
  \(=\) \(6+5\times{16^1}+15\times{16^2}+14\times{16^3}+12\times{16^4}+4\times{16^5}\)

Hexadecimal numbers are currently used for encoding colors. Inputting Isabel's birth date in hex into an online RGB calculator, we found her RGB value to be \((76, 239, 86),\) which is a very bright green. We could not find an exact name for this color, but it is very close to one called "medium spring green." (Somehow we thought of her as more of an earth tone.) To convert back to base ten, simply multiply each base \(b\) digit by its respective power of \(b\) and add.

All place-value number systems inherently use the above expansion. This is precisely what makes a place-value system a place-value system and why these systems are so powerful. That the above expansion is well-defined is essential to the working of a place-value system. The existence and uniqueness of the above expansion have been attested to widely and need not be fully repeated here. The general proof of existence of such an expression is nothing but a generalization, using induction, of the procedure we used for Isabel's birth date. We will outline the proof of uniqueness on the next page, because it is exactly the issue we are going to address.