Thematics Of Order -- Discussion

[Antti Karttunen]

Jon Awbrey wrote:

>o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
>TOO.  Discussion Note 3
>
>o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
>AK = Antti Karttunen
>
>AK: Inspired by this I propose a more practical question:
>    Can we find a nice "closed" (or somehow easily computed)
>    form for:
>
>AK: http://www.research.att.com/projects/OEIS?Anum=A061858
>
>AK: or a similar table involving the differences of ordinary
>    integer multiplication table and e.g. the mult. table of
>    GF(3)[X].
>
>Antti,
>
>That sounds like an interesting line of inquiry --
>one of the reasons why I'm excavating these old
>questions in a personal developmental manner is
>that one person's huis clos is often another's
>autobahn -- but I am struggling to maintain my
>focus on the door I came in by, so I will have
>to keep doing that for a while.
>
>I do see the connection you are making with logic,
>
No, not really, I wasn't interested about logic when I submitted
A061858 and the related tables and sequences, but instead, I was
intrigued by Frank Ruskey's algorithm for generating irreducible
GF(2)[X] polynomials
(see http://www.cs.uvic.ca/~ruskey/Publications/GenIrrPoly.htm
and http://www.theory.cs.uvic.ca/~cos/gen/poly.html )
and was then wondering whether there's any reasonable way
to estimate whether an irreducible GF(2)[X] polynomial
(its binary encoding) is also a prime in N. (See:
http://www.research.att.com/projects/OEIS?Anum=A091206 ),
and of course it's here where the carry bits, those little lice of
binary arithmetics come in picture.

> though --
>back when we used to call these "mask operations", it was
>said that ADD was a combination of XOR plus a shifted AND,
>and of course the process would have to be iterated until
>it terminated.
>  
>
This is the item #23 (by Richard Schroeppel) in HAKMEM:
(A AND B) + (A OR B) = A + B = (A XOR B) + 2 (A AND B).

Follow the link in
http://www.research.att.com/projects/OEIS?Anum=A050600


>For example:
>
>0101 = x
>0011 = y
>----
>0110 = x_1 = XOR(x, y)
>0010 = y_1 = AND(x, y)*2
>----
>0100 = x_2 = XOR(x_1, y_1)
>0100 = y_2 = AND(x_1, y_1)*2
>----
>0000 = x_3 = XOR(x_2, y_2)
>1000 = y_3 = AND(x_2, y_2)*2
>----
>1000 = ADD(x, y)
>
>Let me observe, however, that you are still staying largely within
>the arena of additive representations, since base representations
>are sums of products, or sums of multiples of powers of the base.
>Here the main connective is additive, so maybe this would be
>roughly analogous to disjunctive normal forms in logic.
>
>  
>
I admit that one can find many "rough analogies" between various
domains of mathematics (and maybe life in general...), but as long
as they don't turn out to be real isomorphisms/homomorphisms,
I wonder where this kind of "top-down musing" will eventually
lead. I think the real surprises come from the bottom,
small but significant details, after all.


Cordially,

Antti Karttunen

>Jon Awbrey
>
>o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>inquiry e-lab: http://stderr.org/pipermail/inquiry/
>o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
>
>  
>