1+1 = ?

Marc LeBrun mlb at well.com
Tue Mar 13 08:57:59 CET 2001

Can anyone help shed some light on the following mutant arithmetics?

Let a (+c) b be a generalized binary addition operator on a and b, defined 
as a+b when a*b=0, otherwise as (a XOR b) (+c) (a AND b)*c.

The parameter c effectively just specifies the carry bits of the addition.

For what c does this definition define a meaningfully effective (eg 
convergent) recursive algorithm?

Identifying [1] (+c) [1] with 2, we can solve 2 = Z2[c](U) for U, defining 
numbrals [n] with addition (+c) cast as "numbers in base U with digits 0 
and 1" or equivalently as "partitions into unique powers of U".

If c=2^s, a simple left shift of s bits, we get
   for c=2   (s=1)  ordinary addition, "base 2"
   for c=1/2 (s=-1) "reflected" addition, "base 1/2"
   for c=4   (s=2)  "skip-carry" addition, "base sqrt(2)"
and thus generally a left shift of s gives "base 2^(1/s)".

For s=0 the operation (+0) is IOR, which is apparently to be understood as 
addition in "base infinity".

But what kind of infinity is it?  "Powers" of this infinity are distinct, 
and adding any given power to itself just results in that same power.  Are 
they perhaps like the cardinal "alephs" or something?

Similarly, unbounding s gives (+infinity) alias XOR, which is thus addition 
in an "infinitesimal base", I guess.  The units are again distinct 
"powers", yet they are so tiny that adding them to themselves "carries out 
to infinity", with vanishing result!  Are these nim-additive objects 
identifiable as some surreal or otherwise "non-standard" epsilonics?

Of course we needn't just shift: setting c=3 produces a kind of "unary" or 
"tally-run" representation, and  setting c=9/4 gives a "base tau" or more 
accurately "partitions into golden powers" since Z2[n](tau) casts into 
indistinct values for many n.

To get unique values requires some kind of canonicalization, such as the 
Zeckendorf expansion.  This is typical of non-simple c values--the numbrals 
seem to correspond to distinct "combinatorial objects" that are cast 
together into similarity classes of given "weights" that are "conserved 
additively" by (+c).  When does this happen, and what is the structure?

A related diagnostic symptom in these cases seems to be that (+c) doesn't 
associate.  When does it?

For each (+c) we can also define a corresponding multiplication a (*c) b as 
0 when ab=0 and
otherwise by the usual sort of formal "shift-and-add" procedure, with "add" 
meaning (+c).

When does (*c) distribute over (+c)?  Is it just when (+c) associates?

No doubt these numbral arithmetics correspond to known algebraic 
systems--but which?

(Of course there's no reason to be so binary.  For example try generalizing 
XOR to minimum and AND to absolute difference...)


More information about the SeqFan mailing list