Alternative Logarithms, Part 2

Alternative Logarithms, Part 2
------------------------------

Let's look again at the alternative logarithm identity:

  s(ab) = f( s(a), s(b) ) for some symmetric function f.

Consider now f being the XOR operator (working in the integer domain now):

  s(ab) = s(a) XOR s(b)

The XOR operation is in some ways similar to integer addition, and the traditional symbol for it (+) reflects this fact.

Let us look at the binary for both addition and XOR:

0+0 = 00       0 XOR 0 = 0
0+1 = 01       0 XOR 1 = 1
1+0 = 01       1 XOR 0 = 1
1+1 = 10       1 XOR 1 = 0

The LSB of the addition operator is clearly following the truth table for XOR. But XOR does not elicit an overflow/carry in the way that addition does.

The similarity between XOR and addition could have some interesting implications, and this s() may have some association with our familar (discrete) logarithm.

Though unlike addition, and unlike the Lp norm we explored in the previous installment of this analysis, XOR is a non-monotonic function.


Regardless, we will continue by asking the same question as before: Can we determine a closed form of s() from this rule??

Let us evaluate it at some points:

  s(a.1) = s(a) XOR s(1) = s(a)

So s(1) = 0

  s(a.0) = s(a) XOR s(0) = s(0)

Clearly s(0) is undefined.

  s(a.1/a) = s(a) XOR s(1/a) = s(1) = 0

So s(1/a) = s(a), and this gives us a way to extend s() over the field of rationals.

  s(a^2) = s(a) XOR s(a), which must be zero because XOR is self inverting.

So s() sends squares to zero, meaning that s() is not a one-to-one function, as s(a^2) = s(1) = 0 for all non-zero a.

In particular, s(x) "ignores" square factors of x:

  s(a.b^2) = s(a) XOR s(b^2) = s(a) XOR 0 = s(a)

Clearly:

 - prime factors of x which appear an even number of times are ignored.
 - prime factors of x which appear an odd number of times, need only have appeared once.

x  s(x)
0  undefined
1  0
2  s(2)
3  s(3)
4  0
5  s(5)
6  s(2) XOR s(3)
7  s(7)
8  [ s(2) XOR s(2) ] XOR s(2) = [ 0 ] XOR s(2) = s(2)
9  0
10 s(2) XOR s(5)
etc

The most obvious way to realise this function is for the i'th bit of s(x) to count the number of times (modulo 2) that the i'th prime appears as a factor of x.

ie,
s(2) = 1
s(3) = 2
s(5) = 4
s(7) = 8
s(11) = 16
s(13) = 32
s(17) = 64
s(i'th prime) = 2^i

Thus, for composite x,
s(6) = s(2) XOR s(3) = 1 XOR 2 = 3
s(10) = s(2) XOR s(5) = 1 XOR 4 = 5
s(15) = s(3) XOR s(5) = 2 XOR 4 = 6
etc

s(x) is clearly a surjection onto the codomain Y = (0,inf), as every integer in Y has a preimage.

To see this, any integer y in Y can be represented as a sequence of bits, with each 1 bit corresponding to a prime. A preimage of y is the x equal to the product of these primes.

Also: Because of the fundamental theorem of arithmetic (unique factorisation of x), and because XOR is an associative and commutative operation, there is only one way to arrive at s(composite x). s() is well-defined.



-------------------------------

There are some curious things to observe about this solution:

- The primes could appear in any order, not necessarily in the ascending order I have used.

- Not all primes need to be considered. ie, s() could easily map some primes to zero, such that their presence in x is ignored just like squares are ignored, and without consequence. Mapping squares to zero is unavoidable, but further degeneracy is entirely optional.

- A prime could be flagged in more than one bit position. ie, each prime corresponds to a 'bit pattern' rather than a single bit.

- The bit patterns corresponding to different primes could overlap! This is not immediately obvious, but it is a simple consequence of XOR. Unlike addition, XOR doesn't entangle neighbouring bits with a cascade of overflows/carries - each bit position is effectively a silo. s() is essentially just a vector of binary flags, without an interesting algebra.

- And finally, these bit patterns are actually arbitrary. But they should be an orthogonal set to avoid degeneracy.

eg,
s(a) = 110
s(b) = 011
s(c) = 101

Then s(abc) = s(a) XOR s(b) XOR s(c) = 000, because these three bit patterns form a degenerate set over XOR.