You are here

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

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

We now outline the proof of uniqueness of representation in a pure place-value system because this is exactly the issue we are going to address in the Maya number system. To establish uniqueness of the coefficients of the expression \[a_0+a_1\,b+a_2\,b^2+\cdots+a_k\,b^k,\quad\quad\quad\quad (2)\] in which all coefficients \(a_i\) satisfy \(0\le{a_i}\le{b-1},\) we can use a strong induction argument. The result is true for zero. (If you want the sum (2) to be zero, you need all coefficients to be zero.)

Now take a natural number \(n\) and assume uniqueness holds for every positive integer smaller than \(n.\) We wish to prove that \(n\) has a unique expression in base \(b.\) Suppose \[n=a_0+a_1\,b+a_2\,b^2+\cdots+a_k\,b^k=a^{\prime}_0+a^{\prime}_1\,b+a^{\prime}_2\,b^2+\cdots+a^{\prime}_t\,b^t,\] with, say, \(t\ge{k}.\) We want to prove that \(k=t\) and \({a_i}={a^{\prime}_i}\) for \(0\le{i}\le{k}.\) One can rearrange the equation to get \[a_0-a^{\prime}_0=(a^{\prime}_1-a_1)b+(a^{\prime}_2-a_2)b^2+\cdots\] where the left side of the equation is a number between \(-b+1\) and \(b-1\) and the right side is a multiple of \(b.\) Therefore both sides must be \(0,\) and \(a_0=a^{\prime}_0.\) Now we take, as was done in the example on page 2, the integer \(n_1\) such that \[n=a_0+bn_1\quad{\rm{or}}\quad{n_1}=\frac{n-a_0}{b},\] which is strictly smaller than \(n,\) and is expressed as \[n_1=a_1+a_2\,b+a_3\,b^2+\cdots+a_k\,b^{k-1}=a^{\prime}_1+a^{\prime}_2\,b+a^{\prime}_3\,b^2+\cdots+a^{\prime}_t\,b^{t-1}.\] By the hypothesis of strong induction, the result is true for \(n_1\) and we get that \(k=t\) and \({a_i}={a^{\prime}_i}\) for \(1\le{i}\le{k}.\)

If the encoding of a number were not well-defi ned, we would venture to say that our modern society, so reliant on technology that is driven by numbers (in particular base \(2\)), would come to a grinding halt. It should also be said that we are referring to the uniqueness of a finite integer, regardless of the base. But it also applies to terminating fractional expressions. The well known case of the non-uniqueness of decimal fractions ending in repeating \(9\)'s (for example, \(1.999\dots=2\)) does not fall under this defi nition. However, since no computer system uses an infinite expansion, the dire consequences of non-uniqueness are avoided. But there was one highly advanced civilization whose place-value system did not maintain the uniqueness requirement. Although this civilization did not come to a grinding halt, it did mysteriously decline ....