Thematics Of Order -- Discussion

[Jon Awbrey]

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

TOO.  Discussion Note 4

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

AK = Antti Karttunen
JA = Jon Awbrey

Re: TOO-DIS 3.  http://stderr.org/pipermail/inquiry/2005-April/002549.html
In: TOO-DIS.    http://stderr.org/pipermail/inquiry/2005-April/thread.html#2546

In part:

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].

JA: I do see the connection you are making with logic ...

AK: 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

AK: see http://www.cs.uvic.ca/~ruskey/Publications/GenIrrPoly.html
    and http://www.theory.cs.uvic.ca/~cos/gen/poly.html

I said I saw the connection you were making with logic ---
I didn't say 'you' saw the connection you were making ...

AK: 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:

AK: http://www.research.att.com/projects/OEIS?Anum=A091206

AK: and of course it's here where the carry bits,
    those little lice of binary arithmetics come
    in picture.

Well, that one makes me scratch my head a little ...
It's still a bit too additive for my present bit
of gnosis-following, but I did spend/waste a lot
of time once thinking about how 1 was the first
imaginary number, as it's a solution to x+1 = 0
in mod 2 arithmetic, the irreducible polynomial
x+1 having a coefficient representation of 11,
which is the prime 3 if you read it in base 2.
And x^2 + 1, whose zeroes are +-i, associates
to 101, which is the prime 5 over base 2.

But I was very young then ---
and so much dimmer now ...

JA: 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.

AK: 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).

AK: Follow the link in:

    http://www.research.att.com/projects/OEIS?Anum=A050600

Thanks for the link, though I'm
sure it is much older than that.

JA: 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.

AK: 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.

Yes, part of the context on another list that jogged my memory of
these questions, in combination with Leroy Quet's recent messages
on permutational sequences, was the problem of what distinguishes
genuine from specious analogies, with especial reference to those
between logic and math that Leibniz, Boole, DeMorgan, Peirce, and
a host of others were wont (or wanton) to experiement with.

AK: BTW, this reminds me of the simple "binary/quaternary" coding of
    the Game Trees (as in the Combinatorial Game Theory) I stumbled
    upon a few months ago.

AK: Unfortunately, it doesn't give an isomorphism between
    the natural numbers and the equivalence classes of the
    game positions in the CGT (e.g. when you collapse various
    dominated and reversible positions to the same equivalence
    class), although it does filter out multiple occurrences of
    the exactly identical branches.

AK: I was wondering whether one could "extend" the CGT-addition
    to these game tree codes, so that an addition of two trees,
    of which the other or both are "non-canonical", would also
    yield a "non-canonical" tree (i.e. the corresponding code).
    I will later submit some associated sequences to OEIS,
    time permitting.

AK: I include a scanned JPEG-image from the page 40
    of 'Winning Ways' as an appendix, with the margin
    notes in my bad handwriting ... SeqFan-server will
    probably balk.

AK: From those ten examples it should be an easy
    exercise to figure the principle of encoding.

AK: Just another proof that there's so many ways of playing
    with integers, and their various representations.

Just to continue with the free-associative logics,
there is always a game-theoretic aspect to proofs,
especially with respect to untangling quantifiers,
and one of the things that led me to this present
nexus was looking for multiplicative analogues of
surreal numbers.  But I diverge ...

Jon Awbrey

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