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
A000695.
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
interesting:
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.
Thanks!
More information about the SeqFan
mailing list