**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

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,...,2^{Lmax}-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...b* ^{L
- 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

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 *\Sigma** _{k}* as .
We shall also call any

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 *S _{k}* for which the definition of
any

**Essential properties of ***Sigma*** matrices**

A generic analytical formula for any*Sigma*matrix
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,
*2 ^{k}*,

Additionally, all such *Sigma** _{k}* matrices naturally contain two involutive operations for unsigned
integers, the bitwise binary complement ~

** **

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 *2 ^{L}*

Any *Sigma** _{L}* matrix and its associated interval

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 *DS*_{2} for the sum of bits one immediately
finds that the summand factorizes giving rise to the partition

The sequence *DS _{2}* can be given recursively which is
shown in the second part. While this sequence can be used to immediately isolate
any specific

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 *2 ^{L}* - 1 coincides with
a

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

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 *Z ^{b}*
denotes a discrete cyclic group and the

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

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)) )

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

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