THE COMPLETE ARITHMETIZATION PROJECT - PART I: REASONING & DEFINITIONS

T. E. Raptis © 2020

 

A PDF with all three parts is available here

Introduction

 

"God created the integers, all else is the work of humans"

Leopold Kronecker

This is an ongoing research in an effort to provide a unifying context for a variety of topics underlying low level computations interpreted as pattern processing including a surprising ubiquity of arithmetic fractals constraining these operations as a whole. Additionally, what is revealed is a set of methods that could reduce digital machines to arithmetic analogues. Sometimes, one needs to build a narrative in order to cut a long story short so here is a try:

A magician trickster provokes you with a challenge. He holds a stack of cards on his right hand and a great white envelope on his left. He then puts the whole stack inside the envelope and seals it while immediately after he starts shaking the envelope in all possible and strange ways. When he stops, the envelope is dropped against you and you are asked to recognize the new order of the cards stack without opening the envelope. If he was able to prove you that he already knows the new pattern would you believe him? Is it possible to affect a whole pattern without actually referring to its specific contents?

However strange this question sounds, it has already been pointed out that nature appears to work somewhat similar at a microscopic scale assuming that the explicit contents of any pattern are spread around in space and time. In the course of our exploration we will find a construct that seems to serve as an abstract model for a variety of different themes including structured programming in itself. It will be also necessary to deploy a large set of careful definitions that occupy the first part of this presentation before moving to concrete methods and code snippets.

The reward expected is that we should end up with a set of analytical formulas over large integers of which the simplicity should allow executing them with isomething as elementary as the well known Linux bc calculator. As for lists, they can always be provided in terms of appropriate shell programming or even via such advanced shells like the lust2 lisp-based shell available at least in Ubuntu. In various cases, use of matlab/octave conventions for vectorized operations will also be helpful. This first part is unavoidably large if a bit tedious introduction to some terminology and careful definitions without which the reader would find it difficult to reach the main conclusions as easily as it should.

 

What's in an integer?

 

Given enough thought one may see that the most simple thing like say, a normal number, the one that simply count sheep or cans of beer including absence (0), or whatever similar is far from trivial due to the numerous ways to associate each one of them with infinite varieties of patterns. In the simplest of cases one can make an associative list as

 

|0| ß [0 0 0 ...]

 

|1| ß [1 0 0 ...]

 

What this lists says is that one can have the ``'One' on the left column composed by the ``'Many' on the right column. There is a kind of number-pattern duality involved here as if between a unique, abstract quantity or ``'valuation' expressed as one unique instantiation of something tangible as say, a voltage or a current and its expansion which is necessarily extensive and it does in fact correspond to the spatial dimensions of a "record length". And of course such is not even unique since we could as well write in ternary

 

|0| ß [0 0 0 ...]

 

|1| ß [1 0 0 ...]

 

|2| ß [2 0 0 ...]

 

One may ask what is not trivial here. For the devil's shake, it should suffice to go deep down this bottomless list to realize that sooner or later, one may meet any arbitrary description of any possible finite picture or idea of almost everything in this world or another, being it an appropriately encoded set of directives for a 3D printer to reproduce say, the shape of the Parthenon or a bitmap of sufficient accuracy for reproducing say, all of Picasso's paintings.This is similar to the content of the well known Infinite Monkey Theorem used also by Jorge Luis Borges in his 1939 essay "The Total Library". One might say that triviality here is apparently context dependent.

 

There are other things that are less trivial from a more formal viewpoint. For instance, to fix the above representations one has to invoke the whole ring of polynomials, undoubtedly a much less trivial object than simple arithmetic. And yet, this is the one fundamental thing upon which we base the whole of so called, "Digital Design" or in general, register based computing machines. Not even the original Henry Babbage's Analytical Engine and the later Difference Engine could escape this necessity even if by using a decimal system. And of course, there do exist even more contorted representations like the one based on the golden ratio ,or the more useful Fibonnaci representation due to a theorem by Zeckendorf . This last one can in fact be used to replace an ALU unit with a symbolic substation machine, something that will be touched on a later section.

 

Patterns without patterns

 

It was Kurt Gödel who first showed that even arbitrary symbols of mathematical logic and whole propositions can be encoded one-to-one to the integers. There are by now such techniques that allow doing similar things in a variety of complex systems and automata, collectively known as 'Arithmetization' methods. While the original encoding made use of a list of primes, it is possible to restrict attention to a much simple one that holds true for bounded sets of integers. This is just a string concatenation which has an arithmetic analog as

 

 

where and for the binary representations while k is the upper bound for the bit lengths of both x and y. Given this one can also turn an operator over a bunch of integers of arbitrary arity into a single unary one via

 

 

where k now corresponds to the maximal bit length of the whole collection of inputs. The same exact method can of course be used for multiple outputs. This of course covers all cases of possible automata as elementary symbol maps A( \sigma 1,, \sigma k), in some alphabet in base b.

A word of caution is due here regarding actual implementations. The above scheme is only used to denote a correspondence serving the creation of what shall be called, a "Global Map" as a projection from a multi-dimensional to a one dimensional map. It is not to be used as such for a real function call. If it is desirable, this could be done if all methods can be made to have access to some global mechanism extracting and factoring large bit lengths in the nk format for arbitrary length integers. This is only possible by providing one of the divisors, either n or k as the first part of the list under an appropriate encoding as for instance by leaving an additional maximal all zeros block as the second one thus increasing to (n+2)k total length. This requires also an additional axiom for removing ambiguities where the first divisor part always ends with a redundant 1 bit before the all zeros block thus taking the final "viral" self-descriptive encoding as

 

[Div, 1][0...0][block]...[block]

 

To simplify things a bit, one does not need Div to refer to the whole of the string since one can now simply remove the first block and the redundant bit and extract the divisor for the shifted blocks. No actual division has to be performed here due to an equivalence with a very special algorithm that can extract the same information via a symmetric integer partition. This shall be given in Part II where we analyze this and other methods in more depth.

 

What is proposed next is simply a program for the ultimate reduction of as much as possible of low level functions from pattern processing to simpler ones acting directly on the corresponding valuations |x| as quantities and still affecting the same pattern changes. If a sufficiently large subset of low level "basis" functions can be found which is capable of universal computation then this would serve as a proof for the existence of some equivalent "analog" means or physical mechanisms capable of the same. Suffice it to say that the abstract meaning of |x| here may refer to any appropriate physical quantity including say, frequencies or even the absolute values of some wavelength of some phase front in normal 3D space or inside a material.

 

Herein hides an additional tricky element that needs to be handled with great care. Such methods require the pairing of an integer with its bit length as (x, L) and it may be that we want to keep a maximal constant length L or it may be that we need to take this as a function in itself or L(x). It makes a great difference how we choose this option and some consequences will be discussed in later sections. At the moment, we conclude that the need for bounded integers leads to the need of some hierarchical construction in order to handle potentially unlimited inputs or pattern lists. Additionally, it should be mentioned that whenever pairing numbers we are closing into something known to mathematicians as a 'Complexification' even if discrete, thus effectively doubling the dimensions of our space something not trivial. But we need some more ingredients for everything to become apparent.

 

For any ordinary computing machine known till today, typing an integer in any arbitrary system only becomes meaningful for the machine after being stored in a particular memory location as a binary string or loaded on a RAM register. Yet, as claimed, an integer always has a dual nature and it can always be considered simultaneously as a quantity or a ``'valuation'. It could be a voltage or a current or anything quantifiable. ``Typing'' is only a metaphor here since one can have automated systems using signal processing based on quantization techniques to load a digital version of an external signal measurement to a memory for further processing and then also send its answer to a controller via some D/A converter. All this implies the ever presence of a triplet of morphisms that could be stated as a chain of maps {D, A, E} which stand for a Decoder, a sufficiently simple processing stage represented by a low level string operation (automaton) A and an Encoder symbolically written as a chain of the form

 

 

In the notation used one sees the term often referred to as the Kleene star [9] implying all possible combinations of the symbols of an alphabet. This particular notation will have to be amended in a very specific way which is part of the scope of this article the reason being that such is a very loose and less organized notion for our purposes.

 

Suppose now that we compute all possible instances of transitions in some sufficiently large subset of the Kleene star and we find that such a global map allows building a new, perhaps simpler map 'bridging' the gap imposed by the need to invoke both intermediates $D, E$ which eventually project into a hypercube. That could then be translated into a direct relationship of inputs and outputs as a simple functional relation . Of course this would only be useful whenever we can satisfy at least one additional criterion of lesser complexity to the degree that h can be somehow compressed. To state it more formally, given some measure of complexity say C(h) and similarly for the original mapping represented by C(A) it should roughly hold that

 

 

From a practical viewpoint, one could consider here not just a mere formal definition of complexity but also costs of implementation and time consumption in the realization of any abstract A mapping. There may be cases where abstract, formal definitions of complexity as say, compressibility or the practically uncomputable Kolmogorov complexity [10] may not be sufficient for classifying the overall benefit of such a procedure. We now see to the above proposal the equivalent of moving the envelope with the whole card stack inside as the aforementioned elimination process.

 

Last but not least, the section's title is a paraphrase of another saying due to Wheeler who first tried to reduce everything in a kind of geometrodynamics Were it successful his project should lead to a physical theory obtaining "mass without mass, charge without charge and fields without fields."

 

Global Maps and Hamming Hierarchies

Consider any automaton as a map from the integers to the integers sign included if necessary as the first congruence ( mod 2 ) or the last bit depending on the context. It is possible to ask for the overall behavior of any such automaton over any integer which requires knowledge of what one usually calls a 'Global Map', actually nothing more than a complete graph of all possible outputs at a single step over all integers which could be stored in a large one dimensional array. This is no more than a kind of abstract generalization of what is often referred as the "memoization" technique but under the additional scope of further reduction of a LookUp Table's contents. Inclusion of branching is a secondary problem since it can be treated as a special type of functional composite.

There are already many interesting examples of such maps for all elementary Cellular Automata in the relevant pages of Wolfram's dedicated site.The evident fractal character of the resulting arithmetic sequences is part of the discussion that follows.

 

While it is impossible to exhaust the countable infinity of the set of natural numbers yet, in certain cases, we may find out by explicit computation that such a graph is in fact recursive or contains such symmetries that allow compressing it in some finite interval like [0,...,2Lmax-1]. Of course, it would still not be possible to consider this as anything but a heuristic in the absence of a formal proof, unless we were able to provide some method of automatic induction.

 

The possibility for constructing such a method is offered by what is already known as a i 'Hamming Space' which is simply a array of constant maximal length L patterns forming a word dictionary in some alphabet in base b inside any interval [0...bL - 1]. The name derives from the fact that any such can be turned into a linear vector space when equipped with a distance given by the L1 Hamming norm but is not necessary to make explicit use of this fact here unless it is clearly stated. We will only keep the term to denote the hierarchy of dictionaries which can be defined in a self-similar manner when an upper constant length L is imposed and which is inductive by default or ``by construction'' to use a more mathematical terminology.

 

Construction starts with an inclusive, countable unbounded hierarchy of exponential integer intervals where i and upon which we superpose the associated hierarchy of Hamming spaces as a self-similar set of submatrices In what follows we shall fix the alphabet base to the binary case b = 2 and interpret \Sigmak as . We shall also call any SL a Mersenne interval since it is always terminated by what is known as a Mersenne integer 2L-1, also known due to the fact that some of them are special primes forming prime pairs. For additional justification the reader may check the last section. Since any such has the simplest all ones run length the next integer being a shift, it is fairly easy to write a function isMersenne( x ) = bitand( x, x + 1 ) and of course an IsPow2(x) = IsMersenne( x - 1 ) function and as we will see in the sequel of this first part, every bitwise Boolean operation can be arithmetized via a special recursion which is given in Part II.

 

The deliberation behind this particular choice of intervals will become evident after analyzing certain underlying symmetries which are the main contributing factors in performing an efficient elimination process. It is now possible to rephrase the triplet of morphisms of the previous section in terms of these new matrices as

 

 

That this is always possible is trivially proven by the existence of at least one minimal interval Sk for which the definition of any A must be meaningful. Apparently, whenever or the opposite we can talk of A as an endomorphism inside some maximal interval Sk. There may be also several cases where for some maximal k in which case we may talk of a 1-1 automorphism (at most a permutation) inside the same interval. These cases can be systematized further by checking several interesting properties of the hierarchy of Sigma-matrices. Lastly, we should stress the fact that the hierarchy of matrices is by construction equivalent to a countable set and cannot be used to argue about the uncountable set of infinite binary sequences since these include the ( mod 1) set of all irrationals which is of course uncountable. In this spirit we could more properly call the approach offered a constructivist approach.

 

Essential properties of Sigma matrices

 

A generic analytical formula for anySigmamatrix in any alphabet can be given via number theoretic formulas as

 

 

 

 

 

Simple visual inspection of any such matrix reveals the above to be two things at once, a) the unfolding of the paths of a rooted binary tree and b) the quantization or sampling of an underlying continuous multi-periodic flow since it coincides with a system of counters of increasing exponential periods. There is also a third, deeper possibility in terms of the multinomial expansion of a set on non-commuting objects which will be deferred for the last chapter on the reduction of every structured program on a "Universal Multiplexer" (UMUX) device. At the moment it suffices to redefine the same set of matrices using a much simpler, division-free operation given in terms of the square pulse function with arbitrary periods

Obviously, all rows across the hierarchy correspond to the choice P(x, 2k, 2k), k = 0,1,...,L, so that one can rebuild any such matrix by a simple superposition of rows. We shall denote this as P(x, k) for convenience in what follows. The generic form of the 2-period square pulse function above has still other uses since it can be used as the analytic form of a Boolean indicator for spanning a large interval in which branching is required for certain data as long as the periods can be known beforehand by some other reasoning. A trivial example is for instance the choice of only even inputs in a vectorized format. We shall see more uses of it while describing the UMUX trick at the last part. Also, for the more algebraically inclined, this coexistence of multiple periods implies a kind of group property where binary shifts across columns can be exchanged with arithmetic shifts across rows (taking only integer parts) otherwise said, a shift in scale becomes a shift in time. More on this in the last section.

 

Additionally, all such Sigmak matrices naturally contain two involutive operations for unsigned integers, the bitwise binary complement ~x and the bit reversal which shall be denoted as x*and which are both automorphisms. The complement is in fact a fixed-point-free involution since there is no integer satisfying ~x = x and it actually separates each Sk in two symmetric halves with the fully arithmetized formula

 

In the second case it also suffices to take an up-down flip of a copy of any such matrix and superpose it to the original to prove that can exist precisely 2L palindrom words as fixed points for any even order in S2L and just the same for only L-1 rows in any odd order S2L+1. We shall make a deeper study in the second part of the intriguing nature of this operation which forces the full arithmetization of bit reversals only via a chain of maps. Lastly, if one wants to map signed integers into the same hierarchy one has two choices by either adding a third sign involution between odd and even Sigma entries or by a direct correspondence between NOT and sign using the last bit in any such matrix. What is preferable may depend on context.

Any SigmaL matrix and its associated interval SL admits a refinement of its columns into groups of constant sum of bits of which the recursive structure shall be studied in the second part. This follows naturally from the combinatorial identity

 

Each combinatoric subset with all elements sorted follows a natural Gray code with only one bit in different position as for instance, the subset of all binary shifts. An interesting application of this division is the problem of locating the powerset of all subspaces of a given L-dimensional space. Indeed, if we identify the presence of a single line with one bit, a plane with two bits, a hyper-plane with three or more and so on, then each group counts exactly the presence of each subspace. This is the only refinement that can be given also in terms of the standard Shannon's entropy since this measure cannot discriminate further between patterns inside the same subset. More on this on the second part where an arhitmetized form of the entropy shall be provided as well.

 

Inside each such group there is a second possible refinement into subsets of cyclic permutations of whose the trajectories of same constant maximal length L. It is possible to show that any such complete list independently of its unique elements being lesser than L or not will always form a special integer partition. By putting all circular shifts of the same integer in one of the above groups on a circulant matrix and using the notation DS2 for the sum of bits one immediately finds that the summand factorizes giving rise to the partition

 

 

The sequence DS2 can be given recursively which is shown in the second part. While this sequence can be used to immediately isolate any specific G set, no other simple indicator allows further separating distinct trajectories of each cyclic group inside each larger G set and the above expression is the same for all of them. There is also a special subset across any Sigma matrix known in combinatorics as a necklace with its minimal arithmetic value representing the so called, Lyndon word but more on this at the second part.

Last but not least, the role of the different bit lengths defined by either maximal bits or by the constant upper length across each level of the hierarchy leads to different ways of computing certain sequences of outputs depending on the type of question posed. Before exploring the details of the originally proposed elimination process in the next installments, we leave some space for a slightly deeper understanding of the reasoning behind the particular choice of the hierarchy construct.

Math Addendum

It may have become obvious that the choice of Mersenne intervals as a possible span of the integer line was not at random and has a lot to do with the fact that each integer of the form 2L - 1 coincides with a resonant sub-interval where precisely L square oscillators are in phase. The same can be said for any higher alphabets where all intervals bL - 1 stand again for resonances of sampled triangular waveforms which correspond to modulo operations. We shall see in the examples that this property alone guarantees in many relatively simple cases that the sequence of outputs obtained during the elimination process inherits the structure of an Arithmetic Fractal. A formal definition of a precise Degree of Inheritance of the underlying periodicities for arbitrary types of morphisms is still lacking and it does not appear to be an easy task. Such a property points towards a deeper mathematical structure which goes directly into the heart of group theory and a special case of semi-direct group products. Due to the technicalities involved this material can be skipped.

 

What is perhaps less obvious, is that the same primordial self-similarity can also be attributed to a sampling of a set of harmonic oscillators/cyclic signals via a trick due to Rademacher. While the original Rademacher system was made for a different purpose paving the way for the Walsh-Hadamard transform, one can slightly modify it to show the equivalence with the square pulse function for the rows of every submatrix in the hierarchy in the form of a sampling scheme as

 

 

It is easy to show the overall structure using a multiple plot with a magnification factor for each wavy mode to avoid overlap as well as the sampled square pulses as in the below graph

 

doppler.jpg

 

Such an expression contains a transcedental function which can and will be avoided for the low level set of elementary global maps we will seek afterwards. It does serve though to prove something rather unexpected which is probably also missing from ordinary textbooks. It suffices to notice the peculiar role of the modulating factor inside the sin function. Whenever one has a flow that gets modulated by another one as in the case of an autonomous dynamical system driving another, the result is that any symmetries of the first get mixed up with the symmetries of the second and such a mixing up is known to mathematicians as a special case of a group product with the peculiar -if not sufficiently descriptive - name "Wreath" product, implying the crossing of two flows as much as in an act of wreathing.

 

Otherwise said, at least for discrete systems, it might be that a finite, countable set of group operations gets somehow 'modulated' by a different group acting on their indices. More formally, in our case there are these two properties that should be satisfied and they do - at least in the case of the Rademacher system. Specifically, one needs what is called a leftwise-forward action as and an inverse as for the mixing of two morphisms {f, g}. By simple inspection, the first one (f) must correspond to the cyclic group denoted as U(1) while the second is a particular case of a scaling group say, D which acts as a set of dilations. Then the discrete version resulting from the sampling as in the original Rademacher system generalized now in any arbitrary alphabet could be written formally as where Zb denotes a discrete cyclic group and the b complex roots of unity correspond to the symbols of any alphabet. This implication shows the Hamming hierarchy to have a certain analogy with the topology of a spiral but that's not the last word on the subject.

 

Mostly, there is a direct physical interpretation of the dilation group D which is nothing but a particular sector of the full physical Lorentz group, the one used in special relativity. Indeed, it suffices to consider a clock at rest on the ground and a set of clocks atop a set of rockets running at different velocities which when adjusted appropriately they will cause the necessary dilation of periods so as to form a set of counters due to time dilation. If we really want to compute that it suffices to consider the formula where . Solving that readily gives. Hence, one concludes that this entire story about counters was actually about hyperbolic geometry hidden on the patterns of the integers all along!

 

But we came full circle because if we check backwards we will see that a Sigma matrix is the same as what is known in combinatorics as a "Factorial Design" which demands for every symbol to meet every other and for similar reasons it is also the unfolding of the paths of any b-ary tree. Since any such action necessarily leads to exponential increase it is only natural that such an increase can only be contained in a distorted space as for instance is the Poincare disk model for hyperbolic geometry. What is more interesting for our purposes here is the possibility of using the internal periodicities and self-similarities of all patterns in order to essentially perform a reduction of the complexity of computations and perhaps be led to alternative computational structures that could have a hybrid, semi-analog character.

 

We can still offer a nice geometric game which allows making more evident the presence of the hyperbolic structure which leads to a nice tiling of the Euclidean plane and a mesmerizing wallpaper which is easy to construct using only rotations and reflections of matrices already offered in a standard matlab library as the fliplr and flipud functions. The basic building block requires making copies of an original rectangle following an exponential subdivision of its sides. The first block is as below composed of a reflected inner triangle

BasicTile.jpg

Another way to describe it is with a walker trying to exit from the lower or rightmost side who would suffer a kind of "Zeno paradox"! Completing this four more reflections plus two inversions one gets the complete tile of whom the repetition would give rise to a kind of lattice made out of some sort of "event horizons" so to speak. The full script and the final result are as below

 

 

clc, close all, clear all

n = 9; dim = 2^n;

 m = zeros(dim); flag = 1; % change viewpoint

seq=@(x,y,z)floor(mod((x:y)/2^z,2));

 p = dim/2;m(1:p,1:p) = 1; pc = p;

for i=1:n

    pold = pc; p = floor(p/2);

    pc = pc + p; p1 = floor(dim/2^(i+1));   

    s = seq(p1, pc+p1-1, n-i-1);

    s = repmat(s, p, 1 );

    m( pold+1:pc, 1:pc) = s;

end

m = (m + m')==0;

%imagesc(m), colormap gray % basic tile

if flag

    m = [fliplr(1-m), m];m = [flipud(1-m); m];

else

    m = [m, fliplr(m)];m = [m; flipud(m)];

end

set( gca, 'xtick', [] ); set( gca, 'xticklabel', [] )

set( gca, 'ytick', [] ); set( gca, 'yticklabel', [] )

figure(1), imagesc(m), colormap gray

w =  fftshift( fft2(m) );

figure(2), mesh(log10(abs(w)) )

 

 

HyperbolicSquare1.jpg

An interesting fractal also occurs if you try the standard fft2 in the above of who's the modulus is as below

fft2.jpg

Lastly, the interested reader can try projecting the above tile conformally onto a unit disk by modifying a recent advanced method due to Choi and Lui with the relevant software being available from Mathworks.