a pleasing notation (long)

Marc LeBrun mlb at well.com
Tue Mar 6 15:36:04 CET 2001

 >=Antti Karttunen

 > Yes, it has its merits, although the notation is a bit confusing
 > at first (one thinks Z2[x] polynomials first).

Excellent point!  I welcome your help perfecting it.

 > What about similar notations for the Zeckendorf expansion (Fibonacci
 > number system), and the factorial base notation? [A007623]
 > (Would ZZ[...] or ZF[...] be a good notation for the former, and Z![...]
 > for the latter?)

It's natural, but I was thinking of something slightly different.  Probably 
the terminology needs adjusting to make the intent clearer:

Consider A000695 = A[n] = Z2[n](4), which reinterprets the binary expansion 
of n as a radix-4 value.  The bits of n become the "quaternary digits" of 

Unfortunately both what I called "the base" parameter 2 and "the argument" 
parameter 4 are legitimately "bases".  So this was a poor choice of names: 
any suggestions for a better term for "the base"?

Anyhow, more generally, the parameter n indexes "the A objects".   In the 
above example these A are "numbers whose quaternary expansions contain only 
0s and 1s".

Now the objects that arise when "the argument" isn't a vanilla integer are 

For example Z2[n](sqrt(2)) correspond to the "tinker toy numbers", of the 
form x + y sqrt(2).  The Z2 indicates a binary representation of these 
objects (with the bits of x and y interleaved as alternate coefficients).

The concrete arithmetic operations on this representation are just like 
ordinary binary arithmetic, except that when you add them the carries 
propagate two places to the left instead of just one.

However this addition algorithm actually works just as well if the argument 
parameter had been sqrt(3) or pi or any other irrational value.  "Skip-one 
carry" addition is, by itself, just a nice binary representation of general 
2-vector addition.

The multiplication algorithm for Z2[n](sqrt(2)) will distinguish these 
particular objects. It is simple, implemented by vanilla "digit 
convolution".  This relates the bit positions in a specific way, different, 
from, say, an argument of sqrt(3).

Now changing the argument in Z2[n](sqrt(2)) produces various "binary 
arithmetics" with different concrete algorithms.  For example we could 
change it to sqrt(-2), and then "build hardware" that computes using the 
objects in that domain.

Moreover, just as sqrt(-2) isn't a real number, the argument needn't be an 
ordinary number at all.  We can substitute general "umbral objects" U, by 
which I just mean we blithely write U^k for some set of objects U[k], along 
with defining addition and multiplication on this "basis".

So, to belatedly answer your question, I would advocate Z2[n](F) for the 
Zeckendorf objects, Z[n](!) for factorial expansions, and so on.

Writing "Z" instead of "Z2" for the factorial case also exposes my original 
intent--this argument was to suggest the domain of the "digit" coefficients.

For instance representations of the rationals by their prime factorizations 
might be written as N[n](P), where P is the exotic "umbral unit" whose 
powers correspond to the sequence of prime numbers (with N[n] enumerating 
the finite vectors of signed integers).

When the contextual machinery is understood, the notation can be simplified 
to just the "umbral numerals" [n], which I like to call 
"numbrals".  Usually there is a natural way to "cast" [n] as an integer, eg 
by taking Z2[n](U) to Z2[n](2), and this allows us to easily compute and 
present operations on the numbrals.

Thus a larger rationale for this notation is to provide a standardized tool 
to study "numbral arithmetics", including such things as "nimbers" and 
their ilk.  The bias is concrete: Given an addition algorithm what additive 
theory do we get, such as the partitions of [n]?  Multiplication raises 
further questions: When are the factorizations unique?  Over what additions 
does vanilla digit convolution distribute?  And so on...

So any further suggestions for improvements are greatly appreciated.

More information about the SeqFan mailing list