11institutetext: ILLC, IVI-CCI
University of Amsterdam
11email: P. W. Adriaans@ uva. nl

# Differential information theory

Pieter Adriaans

###### Abstract

This paper presents a new foundational approach to information theory based on
the concept of the _information efficiency_ of a recursive function, which is
defined as the difference between the information in the input and the output.
The theory allows us to study _planar representations_ of various infinite
domains. _Dilation theory_ studies the information effects of recursive
operations in terms of _topological deformations of the plane_. I show that
the well-known _class of finite sets of natural numbers_ behaves erratically
under such transformations. It is subject to phase transitions that in some
cases have a fractal nature. The class is _semi-countable_ : there is no
intrinsic information theory for this class and there are no efficient methods
for systematic search.

There is a relation between the _information efficiency_ of the function and
the _time_ needed to compute it: a deterministic computational process can
destroy information in linear time, but it can only generate information at
logarithmic speed. Checking functions for problems in $NP$ are information
discarding. Consequently, when we try to solve a decision problem based on an
efficiently computable checking function, we need exponential time to
reconstruct the information destroyed by such a function.

$NP$-complete problems are hard because they are defined on semi-countable
domains. There is a smaller class of problems, based on countable domains,
that has a more transparent structure. One such problem, _Subset Bitwise XOR_
, which could also be described as _Multiple Mutual Key Encryption_ , is shown
to be in $NP$ but not in $P$. At the end of the paper I sketch a systematic
taxonomy for problems in $NP$.

keywords: Information, Computation, Complexity theory, Information efficient,
dilation theory, semi-countable sets, $NP$ completeness, $NP$-intermediate.

##  1 Introduction

Philosophy of Information is a relatively young discipline that attempts to
rethink the foundations of science from the perspective of information theory
[5][1]. At a very basic level there are deep theoretical questions, like the
Church-Turing thesis, that are bound to remain unanswered for a long time (see
[1]). In this paper I will turn my attention to two questions for which some
perspective of a resolution exists:

  * •

What is the interaction between information and computation?

  * •

How much information is there in a set of numbers?

The short answer to the first question is easy: deterministic processes do not
generate information. Information measures uncertainty and there is nothing
uncertain about the future of deterministic systems. The amount of information
we need to describe a deteriministic system at time $t$ of its evolution is a
description of the initial configuration and $\log t$ bits to measure the
time. The descriptive complexity of a deterministic system grows slowly at
_logarithmic_ speed with time. Yet such systems can _destroy_ information at
linear speed: think of a Turing machine that erases a random string. This
_asymmetry_ between _destruction_ and _creation_ of information during
deterministic computation is a phenomenon that is at focus of this paper. The
second question is less trivial and current information theories do not give
us much perspective of an answer. In order to make any progress we need a
stronger and more accurate theory to measure information.

Differential Information theory studies the interaction between information
and computation in the context of recursive functions operating on natural
numbers. It is non-stochastic but via the concept of non-determinstic
computing its relation with Shannon information is relatively unproblematic.
It is conceptually closer to Kolmogorov complexity in the sense that it
studies deterministic computational functions. The difference is that
Kolmogorov complexity quantifies over all computable functions with unbounded
time and therefore is uncomputable. Differential information theory
investigates the other end of the spectrum: it studies efficiently computable
bijections between infinite data sets and the natural numbers. It is known
that Kolmogorov complexity can be approximated from below and differential
information theory can be said to explore initial segments of these
approximations.

An advantage of differential information theory is the fact that recursive
functions are defined axiomatically: we can really follow the creation and
generation of information through the axioms from the very basic principles.
Central is the concept of an _information theory_ : an efficiently computable
bijection between a data domain and the set of natural numbers. In this way we
can estimate the computational complexity of elementary recursive functions
such as addition, multiplication and polynomial functions.

As soon as we allow for efficiently computable bijections to more complex
domains, like multi-dimensional datasets or finite subsets of infinite sets,
the behavior of these information theories is non-trivial. In the main body of
the paper I investigate efficiently computable planar representations of
infinite data sets. These representations are inherently inefficient. The
Cantor packing functions, for example, _map_ the set of natural numbers to the
two dimensional plane, but they do not _characterize_ it. Information about
the topological structure is lost in the mapping and there exist many other
efficiently computable bijections. As a consequence there is no precise answer
to the question: what is the exact amount of informaton of a point in a
discrete multi-dimensional space?

Since Cantor’s work planar representations of infinite data sets play an
important role in proof theory, so it is worthwhile to attempt a deeper
analysis of their structure. One set that is of particular interest is the set
of finite sets of natural numbers, denoted as $\mathfrak{P}(\mathbb{N})$, in
contrast to the classical power set of $\mathbb{N}$ which is denoted as
$\mathcal{P}(\mathbb{N})$. It is generally assumed that we need the axiom of
choice to prove this set to be countable. I show that this set is _semi-
countable_ 111The term was suggested to me by Peter Van Emde Boas.: there are
various ways to count this set but, dependent on the initial choices we make,
the corresponding information measurement generated by the choices vary
unboundedly. The proof technique I use is called _dilation theory_ 222The term
was suggested to me by David Oliver: the systematic study of the information
effects of recursive operations on sets of numbers in terms of topological
deformations of the discrete plane.

The recursive functions generate dilations of the discrete plane of decreasing
density and, consequently, increasing information efficiency. For semi-
countable sets there is an endless sequence of efficiently computable phase
transitions from planar to linear representations: from density one, via
intermediate densities, to sparse sets, to linear representations with density
zero. Close to the linear reprentations the sets have a _fractal_ structure
Since the linear dilations can be embedded in the plane the cycle phase
transitions is unbounded. Consequently for these sets there is no intrinsic
measurement theory, no intrinsic definition of density, no intrinsic notions
of typicality or neighbourhood.

This special nature of semi-countable sets is important because serveral
notoriously difficult open problems in mathematics are defined on these
domains. One example is factorisation, the other is the $P$ vs. $NP$ problem.
The subset sum problem is known to be $NP$-complete. It is defined on finite
sets of natural numbers and via efficiently computable transformations the
whole class of $NP$ complete problems shares the same semi-countable data
structure. This implies that none of the well-known concepts like information,
density, neighborhood or typicality can be used unconditionally in attempts to
solve these problems. A prooftheoretical analysis of this class is complex and
there are many open questions. I show, however, that there are ‘easier’
problems in $NP$, based on countable domains, that are not $NP$-complete and
that are not in $P$. Based on this analysis I give a taxonomy of problems in
$NP$ based on three dimensions: expressiveness of the domain, density of the
domain, information efficiency of the checking function (see table 6 in
section 9).

An overview of the structure of the paper:

  1. 1.

Introduction

  2. 2.

Information, computation and time

  3. 3.

Differential Information Theory

  4. 4.

From $\mathbb{N}$ to $\mathbb{N}^{2}$: Planar information theories

  5. 5.

Dilations of $\mathfrak{P}(\mathbb{N})$ on $\mathbb{N}^{2}$

  6. 6.

The class $NP$

  7. 7.

Problems in $NP$ defined on countable domains

  8. 8.

A taxonomy for decision problems

The reader that wants to get a general impression of the results can read
sections 2, 3, 7 and 9. For a deeper understanding the other sections can be
consulted. Additional material can be found in the appendices:

  * •

Section 11: The information structure of data domains

  * •

Section 12: Computing the bijection between $\mathfrak{P}(\mathbb{N})$ and
$\mathbb{N}$ via $\mathbb{N}^{2}$ using the Cantor pairing function: an
example

  * •

Section 13: Scale-free Subset Sum problems

  * •

Section14: The entropy and information efficiency of logical operations on
bits under maximal entropy of the input

  * •

Section 15: Encoding a message in MMK by Absorbtion

  * •

Section 16: Bitwise XOR is in SAT

##  2 Information, computation and time

There are many procedures in the real world that we can use to compute
mathematical functions. We might select:

  * •

An _abacus_ , manipulating _objects_ , e.g. shells or pabbles on a table,

  * •

An _algorithm_ , manipulating _symbols_ , e.g. arabic numerals on a piece of
paper or binary strings on a tape as in a Turing machine.

The fact that the same mathematical function can be computed in different ways
implies that there exists an underlying independent concept of computation,
which in modern mathematics is understood in terms of _recursion_. A
mathematical function is recursive if the function itself is invoked in its
definition. An example is addition that can be defined recursively using the
successor function: there is a base case $m+0=m$ and a recursive step
$m+S(n)=S(m+n)$. When we compute we create and destroy information. Since we
manipulate information in space and time when we perform our computational
procedures there must also exist an underlying pure abstract theory of
information associated with the concept of resursion.

###  2.1 Algorithmic Computation

Algorithmic computation is the sequential manipulation of a finite set of
discrete symbols, local in space and time, according to a finite set of fixed
rules. There are many abstract systems that incorporate these ideas, but in
the study of computation, we will restrict ourselves to the study of Turing
machines that work in discrete one-dimensional space (a tape with cells) and
time, using only three symbols: “0”, “1” and “b” (for blank). A Turing machine
has a read-write head and a finite set of internal states. The computational
behavior is given by the state transition table. A move of a Turing machine
consists of reading a symbol in a cell, overwriting it with a symbol and
moving the tape one cell in one or the other direction. We will consider
computations that start with a finite binary string as input and after a
finite amount of time end with a binary string as output.

For a deterministic machine the state transition table is a function. If the
state transition table is a relation, then the machine is non-deterministic,
because it can shift from one configuration to several others. A non-
deterministic machine makes an unbiased choice between the transition options
given by the transition table. The amount of information that is generated by
such a choice is given by the Hartley function: 333In this paper I will use
$\log x$ as shorthand for $\log_{2}x$. The base of the logarithm is of no
specific importance. If one chooses the natural logarithm, information is
measured in _gnats_ if we choose base two the measure is in _bits_ , but any
other base is acceptable. We will use the expression $\log_{a}$ of $\log$ for
any general logarithm with base $a$ and $\ln$ for the natural logarithm.

$H_{0}(A)=\log_{k}|A|$ (1)

The Hartley function gives the information that is revealed when one picks a
random element from $A$ under uniform distribution. Shannon information is a
generalisation of the Hartley function. It defines the amount of information
in a message as the negative logarithm of the probability that a message
occurs: $I(x)=-\log_{2}p(x)$. The Shannon entropy of a system of messages is:

$H=-\Sigma_{i}p_{i}\log_{2}(p_{i})$ (2)

Here $p_{i}$ is the probability of occurrence of the $i$-th possible value of
the source symbol. If $X$ is a system of messages then the entropy rate of a
stochastic process is the time density of the average information:

$H(X)=\lim_{n\rightarrow\infty}\frac{1}{n}H(X_{1},X_{2},\dots X_{n})$ (3)

We get strings of messages with the highest entropy when the distribution over
the set of messages is uniform. For bitstrings this is the case when zero and
one messages have equal probability: $p(1)=p(0)=\frac{1}{2}$. Strings that are
produced by such a system with maximum entropy are with high probability
random. They contain the maximum amount of information possible, have no
special features that allow us to classify them and cannot be compressed.
Shannon information allows us to study the information generation in
stochastic Turing machines that have a probability distribution over the
transition relation.

The choice for the logarithmic function is motivated by the fact that it
characterizes the additive nature of entropy and information _exactly_. At the
heart of the concept of information there is a specific interaction between
multiplication and addition, that satisfies our intuition about the behaviour
of information. First we want information to be _additive_ : if we get two
messages that have no mutual information we want the total information of the
set of messages to be the sum of the information in the separate messages:

######  Definition 1 (Additivity Constraint:)

$I(m\texttimes n)=I(m)+I(n)$

We want higher numbers to contain more information:

######  Definition 2 (Monotonicity Constraint:)

$I(m)\leq I(m+1)$

We want to have a unit of measurement:

######  Definition 3 (Normalization Constraint:)

$I(a)=1$

The following theorem is due to Rényi (1961)

###### Theorem 2.1

The logarithm is the only mathematical operation that satisfies additivity,
monotonicity and normalisation.

The historical background of this definition is discussed extensively in [1].
Formula 1 is related to Boltzmann’s entropy equation, $S=k\log W$, for an
ideal gas, that gives, in Planck’s words: the logarithmic connection between
entropy and probability. Here $S$ is the entropy, $k$ is the Boltzmann
constant and $W$ is the number of microstates of the gas that correspond to
the observed macrostate of the gas. The formula statistically links the
information we have about the observed state, to the information we lack about
the specific microstate of the ideal gas. The logarithmic function is
neccesary to capture the specific _extensive_ nature of entropy as a measure
which is specified by theorem 2.1: if we join two ideal gases with entropy $S$
we get $k\log(W\times W)=2S$, twice the amount of entropy from the product of
the sets of possible microstates $W\times W$.

###  2.2 Information and the Axiom of Choice

The concept of information is _not well-defined_ for infinite sets. For such
sets the notion of extensiveness does not discriminate. There are various ways
to illustrate this. A set is Dedekind infinite if it can be mapped to a proper
subset of itself. Or take the equation
$\infty+\infty=\infty\times\infty=\infty$. In the context of information
theory there is a relation with the axiom of choice says that given an
infinite collection of sets, each containing at least one object, it is
possible to make a selection of exactly one object from each set. The
consequences of the axiom for information theory are non-trivial given the
observation by Foley:444Duncan Foley, personal communication.

###### Observation 1

$\dots$ a central problem is the paradox that there is no unconstrained
maximum entropy distribution on the set of integers, and hence no generally
convincing way to make the intuitively appealing concept of “an integer chosen
at random” operational.

A large part of this paper (specifically sections 4 and 5) is dedicated to the
analysis of the information theoretical consequences of choosing elements of
classes of sets of objects, finite or infinite. Betrand Russell famously
illustrated the Axiom of Choice by the following example: we may select an
element of a collection of pairs shoes, by selecting the left shoe from each
pair, but we do not have that option when it comes to a collection of socks.
In the context of information theory this also true in finite cases: the
conditional descriptive complexity of a set of left shoes is constant, but the
conditional descriptivie complexity of a selection of socks chosen from a
collection of pairs of socks depends on the cardinality of the collection.
Each choice is made under uniform distribution, so, according to equation 1,
we generate exactly one bit of information. This example shows that even in
finite cases the Axiom of Choice is at stake. Some collections of objects can
only be made accessible for manipulation after we have made certain choices,
but these choises inherently add information to the sets.

###  2.3 Data structures and information

The set of natural numbers $\mathbb{N}$ is the smallest set that satisfies
Peano’s axioms:

  1. 1.

Zero is a number.

  2. 2.

If a is a number, the successor of a is a number.

  3. 3.

Zero is not the successor of a number.

  4. 4.

Two numbers of which the successors are equal are themselves equal.

  5. 5.

(induction axiom.) If a set S of numbers contains zero and also the successor
of every number in S, then every number is in S.

Numbers are abstract objects and we cannot touch them. If we want to
manipulate numbers we will have to use representations of these numbers. In
modern mathematics we use _positional numeral systems_ for this purpose.
Numbers are represented _strings_ based on an _finite ordered set of numeral
symbols_. The value of a sympbol in a string is dependent on its position in
the string: the symbol $j$ on position $k$ has value $jn^{k}$ where $n$ is the
cardinality of the set of symbols. In this way we can generate an infinite
amount of objects. In this paper I will generally study representations using
binary strings.

Figure 1: Self-similarity in the infinite binary tree: $\\{0,1\\}^{\infty}$

Figure 2: Partial self-similarity in the set of binary strings of length $4$:
$\\{0,1\\}^{4}$

A function is recursive if the function itself is invoked in its definition,
so by definition recursive functions operate on data structures that are self-
similar. Self-similar data sets contain identical copies of themselves, so by
definition they are infinite. An example of such a data structure is the
binary tree (see figure 2). We can count the nodes of a binary tree breadth
first (blue arrow). This is a simple process that can easily be implemented on
a deterministic computer. At any stage of the counting process we investigate
a set of nodes of the tree with the same path length $k$. Such a set can be
characterized by a set of binary strings of length $k$ in which traces of the
self-similar structure of the tree still exist (see figure 2). If we want to
search the string depth first (red arrow) the situation is different. We have
to make a choice between two options at each step and so with each step we
generate one bit of information. This can not be done by a determinstic
computer. We can say that there is a standard method to search the tree
breadth first, but there is no such method for an exploration of the tree
depth first.

Note that both methods generate the same amount of information when
identifying a node. In order to arrive at the node $100110$ the depth first
process has to take $6$ binary decisions which generate $6$ bits of
information in $6$ steps. The determinstic process has to check
$2^{5}+2^{2}+2^{1}=38$ cases. We have $log_{2}38\approx 5,25$ bits, which
gives in discrete bits $\lceil 5,25\rceil=6$. The deterministic process
creates in exponential time the same amount of information as the non-
deterministic process in linear time.

The self-similar structures of these data sets suggest that we can analyze
them as fractals, but this analogy is not straightforward. A well-known
fractal is the Cantor set. It is constructed from the real interval $[0,1]$ by
removing all the segments of numbers that contain the digit $1$ when expressed
as a ternary number fraction with base $\\{0,1,2\\}$. Although this may appear
to be a harmless operation it involves the manipulation of infinite objects
and as such it lies beyond the jurisdiction of information theory. In fact
almost all empirical reasearch into fractal data sets involves symbolic
computation on finite representations. The concept of a fractal arises from
the fact that in finite domains we observe repetative patterns created by
recursive computational processes that can generate chaotic behaviour at any
stage of their evolution.The estimates of the fractal dimensions of these data
sets are by necessity made in finite discrete domains for which the Hausmann
dimension is zero.

What we study in this way is the notion of unbounded recursion in countable
domains. In this context we can say that countable sets have a fractal
structure and estimate their dimension. The Cantor set then consist of all
ternary numbers that do not contain the number $1$. This set can be expressed
as $\\{0,2\\}^{\infty}$. Consequently the cardinality of the set is equal to
that of the set of binary numbers associated with $\\{0,1\\}^{\infty}$, i.e.
it is uncountable. The density of the countable subset of the Cantor set
consisting of rational numbers can be estimated for each $k$ as
$\frac{2^{k}}{3^{k}}$, which gives the difference in expressivity between a
ternary number system and a binary number system in terms of the length of
their representations in a string of lenght $k$:

$\frac{\log 2^{k}}{\log 3^{k}}=\frac{\log 2}{\log 3}\approx 0.63093$ (4)

Since the set $\mathbb{Q}$ is countable, the formal Hausdorff dimension is
$0$, but the analysis shows that we may for countable subsets of fratal sets
use counting methods to estimate the fractal dimension.

###  2.4 Processes and information

Figure 3: Processes that generate binary strings.

Next we analyze processes that generate strings. In figure 3 four basic
processes that produce strings are illustrated in terms of their generating
finite automata:

  * •

Automaton $A$ is _deterministic_. It has no stop criterion and only describes
one object: an infinite sequence of ones $1^{\infty}=111111\dots$. This object
is _transcendent_. It is not accessible in our world.

  * •

Automaton $B$ is _non-deterministic_. At any stage of its execution it has two
choices: 1) write another one or 2) quit. Automaton $B$ describes the set
$\\{1\\}^{\ast}$ that is closed under concatenation. This set is _countable_
in a natural manner according to the correspondence:

$(0,\varepsilon),(1,1),(2,11),(3,111),(4,1111),\ldots$

Here $\varepsilon$ denotes the empty word. We can estimate the amount of
information in the elements of $\\{1\\}^{\ast}$. A finite sequence of ones of
length $k$ is the result of $k+1$ binary decisions, but since the last
decision, by necessity, is taken only once it does not generate any
information: it is merely the decision to bring the string into existence. The
amount of information in the string is $\log_{2}k$.

  * •

Automaton $C$ is also _non-deterministic_ but in a conceptually different way
since it has no stop criterion. Instead it generates an infinity of infinite
binary strings. We could call the class of objects $\\{0,1\\}^{\infty}$. All
its elements are _transcendent_. There is no information theory for this class

  * •

Automaton $D$ again is _non-deterministic_ but it has a stop criterion. The
set of strings that it describes is $\\{0,1\\}^{\ast}$, which is closed under
concatenation. The set $\\{0,1\\}^{\ast}$ is _countable_ (see figure 4). We
can define a bijjection between ${\mathbb{N}}$ and $\\{0,1\\}^{\ast}$
according to the correspondence:

$(0,\varepsilon),(1,0),(2,1),(3,00),(4,01),\ldots$

We can measure the amount of information in elements of $\\{0,1\\}^{\ast}$. At
any stage, except the last step, the automaton makes a choice between two
options (write a zero or write a one). When we apply the Hartley function
(equation 1) it adds one bit of information at each generative step. The
maximum amount of information in a binary string of length $k$ is $k$ bits.

Figure 4: Proof of the countability of $\\{0,1\\}^{\ast}$. There is a natural
partial order for elements of the set on the length of strings. For each
length $k$ there is a finite set of strings of that length of size $2^{k}$:
columns ordered on length, rows lexicographically.

We can use the elements of $\\{0,1\\}^{\ast}$ to encode subsets of finite sets
and to measure the information in these subsets

######  Definition 4 (Conditional information in subsets)

Let $S$ be a totally ordered finite set with cardinality $n$, where $s_{i}$ is
the $i$-th element of the set. A subset of $S^{\prime}\subset S$ is coded by a
_characteristic string_ : a binary string $a$ of length $n$ such that
$a_{i}=1$ iff $s_{i}\in S^{\prime}$ and $s_{i}=0$ otherwise. The conditional
information in $S^{\prime}$ with cardinality $k\leq n$ given $S$ is:

$I(S^{\prime}|S)=\log_{2}{n\choose k}$ (5)

This is the value of the Hartley function (see equation 1) applied to the
number of ways we can choose $k$ elements from a set of $n$ elements. The set
of binary strings of length $k$, written as $\\{0,1\\}^{k}$, gives the
information structure of the power set of any finite set with $k$ elements.
See figure 6 and 6.

###### Example 1

The set $s=\\{2,3,5\\}$ is coded as a subset of a set of cardinality $6$ by
the string $0010101$ and as a subset of a set of cardinality $10$ by the
string $00101010000$. In the first representation the set is coded as an
element of the powerset of $7$ elements and the second as an element of the
power set of $11$ elements. The conditonal information in the set $s$ in the
first representation is $\log_{2}{6\choose 2}\approx 2.0$ and in the second
representation $\log_{2}{15\choose 2}\approx 6.7$. There are infinitely many
other strings that describe $s$. The effects of the bias generated by these
different options is analyzed in section 6.4.

Figure 5: Power set $\mathcal{P}(\\{a,b,c,d\\})$ ordered on cardinality
(vertical) and lexicographically horizontal.

Figure 6: The information structure of the set $\mathcal{P}(\\{a,b,c,d\\})$

For infinite sets this approach is not unproblematic.
$\mathcal{P}(\mathbb{N})$ is the powerset or set of subsets of $\mathbb{N}$.
This set is associated with the object $\\{0,1\\}^{\infty}$ or coded by the
infinite binary tree and its elements are _transcendent_. We cannot manipulate
them in our world. But even for sets that we do encounter in daily life
measuring information is not always trivial. Consider the _set of finite
subsets of $\mathbb{N}$_, which I denote as $\mathfrak{P}(\mathbb{N})$.

###### Theorem 2.2

There is no intrisic definition of the amount of conditional information for
elements of $\mathfrak{P}(\mathbb{N})$.

Proof: Definition 4 does not apply. Since the domain of
$\mathfrak{P}(\mathbb{N})$ is infinite equation, 5 gives no finite value. For
any $x\in\mathfrak{P}(\mathbb{N})$ the conditional information
$I(x|\mathbb{N})$ is undefined. $\Box$

I define a separate class for this object:

###### Definition 5

$\mathfrak{P}(\mathbb{N})$ is _semi-countable_.

The set has many interesting qualities:

  * •

The set is formally countable, but the proofs rely on the notorious _axiom of
choice_. Choices generate information, so if we need to make choices to count
an infinite set of objects, then the individual elements of the counted set
contain more information then the numbers we use to count them.

  * •

$\mathfrak{P}(\mathbb{N})$ has a clear partial order on the subset
relationship, but information theory is not monotone over set theoretical
operations (see pargraph 3.4 and [1], par. 6.2) so this partial order cannot
be used to prove countability.

  * •

There is no natural mapping between the countable set $\\{0,1\\}^{\ast}$ and
$\mathfrak{P}(\mathbb{N})$ in terms of characteristic vectors. The set of
$\\{0,1\\}^{k}$ characterizes the power set of finite sets of cardinality $k$
(see example 1).

Figure 7: A hierarchy of countability classes.

This analysis proves the existence of an infinite class of objects that is
placed _in between_ the domain of the countable and the uncountable: semi-
countable sets (see figure 7). The fact that we need the axiom of choice to
count these classes implies that semi-countable classes are more expressive:
their elements contain _more_ information than normal countable objects.
Through the choices we make we _add_ information to the elements which make
them accessible. Later in this paper (see paragraph 5) I will show that the
question: what is the amount of information in a set of numbers has no
univocal answer. Observe that semi-countable sets are very common in
mathematics. Any problem domain in which we consider finite subsets of totally
ordered domains is semi-countable: e.g. sets of litterals, nodes in a graph,
etc.

###  2.5 Types of Computational Processes

There are at least three fundamentally different types of computing (See
Figure 8) :

Figure 8: Classes of Computing Systems

  * •

_Elementary deterministic computing_ as embodied in the primitive recursive
functions. This kind of computing does not generate information: the amount of
information in the Output is limited by the sum of the descriptive complexity
of the Input and the Program.

  * •

_Deterministic computing enriched with search_ (bounded or unbounded) as
embodied by the class of Turing equivalent systems, specifically the
$\mu$-recursive functions. This type of computing generates information at
logarithmic speed: the amount of information in the Output is not limited by
the sum of the descriptive complexities of the Input and the Program.

  * •

_Non-deterministic computing generates_ information at linear speed.

There is a subtle difference between systematic search and deterministic
construction that is blurred in our current definitions of what computing is.
If one considers the three fundamental equivalent theories of computation,
Turing machines, $\lambda$-calculus and recursion theory, only the latter
defines a clear distinction between construction and search, in terms of the
difference between primitive recursive functions and $\mu$-recursive
functions. The set of primitive recursive functions consists of: the constant
function, the successor function, the projection function, composition and
primitive recursion. With these we can define everyday mathematical functions
like addition, subtraction, multiplication, division, exponentiation etc. In
order to get full Turing equivalence one must add the $\mu$-operator. In the
world of Turing machines this device coincides with infinite loops associated
with undefined variables. It is defined as follows in [9]:

> For every 2-place function $f(x,y)$ one can define a new function, $g(x)=\mu
> y[f(x,y)=0]$, where $g(x)$ returns the smallest number y such that
> $f(x,y)=0.$ Defined in this way $\mu$ is a partial function. One way to
> think about $\mu$ as in terms of an operator that tries to compute in
> succession all the values $f(x,0)$, $f(x,1)$, $f(x,2)$, … until for some $m$
> $f(x,m)$ returns $0$, in which case such an $m$ is returned. In this
> interpretation, if $m$ is the first value for which $f(x,m)=0$ and thus
> $g(x)=m$, the expression $\mu y[f(x,y)=0]$ is associated with a routine that
> performs exactly $m$ successive test computations of the form $f(x,y)$
> before finding $m$. Since the $\mu$-operator is unbounded $m$ can have any
> value.

Note that the name $g$ does not refer to a function but to a function-scheme.
The $x$ in the expression $g(x)$ is not an argument of a function but the
index of a function name $f_{x}(y)\Leftrightarrow f(x,y)$. We can interpret
the $\mu$-operator as a meta-operator that has access to an infinite number of
primitive recursive functions. In this interpretation there is no such thing
as a general search routine. Each search function is specific: searching for
your glasses is different from searching for your wallet, even when you look
for them in the same places.

The difference between primitive recursion and $\mu$-recursion formally
defines the difference between _construction_ and _search_. Systematic search
involves an _enumeration_ of all the elements in the search space together
with _checking function_ that helps us to decide that we have found what we
are looking for (See appendix in paragraph 11.1 for a discussion).

###  2.6 Information and time

Suppose we have a way to measure the descriptive complexity of a working
Turing machine during its execution. One could think of the minimal number of
bits needed to be transported over a telephone line in order to decide whether
the configuration of Turing machine $A$ is equal to that of $B$ at time
$t_{i}$ of their execution. Using this theory we could study the creation and
destruction of information during the execution of a program.The basic
equation of the theory of computation is:

$program(input)=output$ (6)

We specify a $program$, that operates on a certain $input$ and after some
finite time this combination produces an $output$. The _Information
Efficiency_ of a program is measured as:

$\Delta(program(input))=I(output)-I(input)$ (7)

Here $I(x)$ is the information in the object $x$. Note that the complexity of
the program is irrelevant for measuring the information efficiency. The
following thought experiment might help.

###### Example 2

Imagine a closed room containing, amongst other objects (a sofa, some books,
some random strings), a Turing machine, with a binary string on the input tape
at some time t of a computational process. We ask ourselves: what is the
difference in descriptive complexity of the total room at time t and at time
t+c given the information that the only change in the room is the fact that c
computational steps have taken place? We will abstract from issues like the
energy that our machine is using during its computations. In this case the
descriptive complexity of the invariant part of the room itself, including the
specific complexity of the selected Turing machine, is irrelevant. The only
things we need to know to estimate the in- or decrease of information in the
room are:

  * •

The change in the content of the tape

  * •

The change in the place of the read-write head

  * •

The change in the internal state of the machine

By taking two snapshots of the room at different times we can eliminate some
of the problems of descriptive complexity theory. We do not need to compute
the full descriptive complexity of the room at time $t$, since we subtract
this descriptive complexity of the contents that have not changed again at
time $t+c$. Without loss of generality we get a pure measurement based on the
contents of the tape only if we assume that the read-write head is at the end
of the string created so far and the internal state of the machine is the same
at the moments we take the measurements.

In this way our differential measurement is insensitive to specific Turing
machine we use and computable in sufficiently rich and relevant paradigmatic
cases.

######  Example 3 (Information generation by means of unary counting)

A unary number is one that exists only of ones or zeros. All a computer needs
to know to create such a number is a program that writes a sequence of symbols
and a counter that specifies the length of the sequence. The length of a unary
number of length $k$ be expressed in $\log_{2}k$ bits. Suppose the Turing
machine simply writes an infinite string of ones. At $t_{0}$ the tape is
empty. At $t_{i}$ the tape contains $i$ ones. The naive descriptive complexity
at $t_{(0+i)}=log_{2}i$, In general, for this program, the complexity at time
$t_{(i+j)}$ compared to the complexity at $t_{i}$ is $\log_{2}j-log_{2}i$.
Note that the read-write head is always at the end of the generated string, so
this is an invariant aspect of the process. Unary counting processes generate
information at logarithmic speed.

###### Example 4

(Information destruction by means of erasing strings) Suppose the tape of the
Turing machine at $t_{0}$ contains a finite string of length $k$ with maximal
information and the program simply overwrites the cells by blanks. When the
program is ready erasing the string there are $k$ bits less information in the
total system.

A useful proof technique is the analysis of the information efficiency of
deterministic computational processes under maximum entropy input. In some
cases we can compute the resulting information efficiencies exactly. I give an
example for logical operations.

###### Example 5

(Information efficiency of logical operation under max entropy input)555For a
systematic overview of information efficiency of logical functions under
random input see the appendix in paragraph 14. We will use the $\oplus$ sign
to represent the logical XOR operation. The OR, AND and XOR functions are
defined in table 1. The operations are _commutative_ and _associative_. Under
random input we can interpret these logical operations as systems of messages
in Shannon’s sense and compute the entropy and the information efficiency.
Both the AND and the OR operation have an inbalance between zeros and ones in
the output and therefore discard more information than the XOR function. Using
Shannon’s function, $H=-\Sigma_{i}p_{i}\log_{2}(p_{i})$, the entropy of
logical operations on bits under random input is:

A | B | $\vee$
---|---|---
1 | 1 | 1
1 | 0 | 1
0 | 1 | 1
0 | 0 | 0

A | B | $\wedge$
---|---|---
1 | 1 | 1
1 | 0 | 0
0 | 1 | 0
0 | 0 | 0

A | B | $\oplus$
---|---|---
1 | 1 | 0
1 | 0 | 1
0 | 1 | 1
0 | 0 | 0

Table 1: The , OR, AND and XOR operation.

$H(x\vee y))=H(x\wedge
y)=(\frac{3}{4}\log_{2}\frac{3}{4})+(\frac{1}{4}\log_{2}\frac{1}{4})\approx
0.8$ (8)

$H(x\oplus y)=2(\frac{1}{2}\log_{2}\frac{1}{2}))=1$ (9)

The information efficiency of logical operations on bits under random input
is:

$\Delta(x\vee y)=\Delta(x\wedge y)\approx 0.8-2\log_{2}\frac{1}{2}=-1.2$ (10)

$\Delta(x\oplus y)=1-2\log_{2}\frac{1}{2}=-1$ (11)

Under random input we lose roughly $1.2$ bits when we perform the AND and the
OR operation and $1$ bit when we perform the XOR operation. Since the
operations are commutative and associative, they can be interpreted as
operations on multisets of bits, irrespective of the order of the bits in a
specific string. This implies that the first two operations performed on
random strings are trivial. We know that random strings have roughly the same
amount of zero and one bits. A sequence of OR operations on a random string
will always be true, even if we flip a considerable number of bits. The same
holds for a sequence of AND operations on a random string: it will always be
false. Only the XOR operation remains maximally sensitive under bit flipping,
even if the input is random.

Important is the insight that deterministic processes can destroy information
at relatively high speed and only generate information at exponentially slow
speed:

######  Theorem 2.3 (Asymmetry between creation and destruction of information
during deterministic computation)

  * •

_Destruction_ : The maximum average speed at which a deterministic process can
destroy information is linear time: one bit at each computational step.

  * •

_Creation_ : The maximum average speed at which a deterministic process can
generate information is logarithmic time.

Proof:

  * •

_Destruction_ The maximum amount of information destroyed is reached when we
erase a bit from a string with maximum information. If we remove one bit, we
get a new string of length $k-1$ and thus complexity $k-1$.

  * •

_Creation_ : Given the description of a computational process at time $t$ the
naive incremental complexity of the process at time $t+c$ is $\log_{2}c$,
since we only need to know the description of the process at $t=0$ and the
actual time $t=c$ to describe the system at time $c$.

$\Box$

An important other result in this context is what one could call the:

######  Lemma 1 (Collapse lemma)

The descriptive complexity of the output of a deterministic computation after
halting is at most one bit higher than the complexity at the start of the
process.

Proof: if we have the description of the system at the start, we only must
code one bit of extra information telling us the process has finished. $\Box$

###### Lemma 2

Collorary: The descriptive complexity of deterministic computational processes
during their execution is in general higher than after halting.

Proof: immediate consequence of the asymmetry theorem 2.3 and the collapse
lemma 1. $\Box$

###### Example 6

Take a program that writes a unary number (sequence of ones) of length
$2^{k}$. The stop criterium for the program is easily specified in terms of
$O(\log_{2}k)$ bits, but during execution the program will sequentially
generate all incompressible numbers of complexity $k-1$ bits.

###### Lemma 3

The maximum amount of information generated by a polynomial time deterministic
program during its execution working on input of length $x$ is $clog_{2}x$
bits.

Suppose the input of a program $p$ has length $x$ and the computation finishes
within $x^{c}$ steps. Apply theorem 2.3. $\Box$

##  3 Differential Information Theory

Up till now we do not have a theory of information measurement that is
sensitive enough to catch the subtleties of information flow during
deterministic computational processes. Shannon information measures
information in terms of the probability of messages, which is not useful for
the analysis of deterministic computation. Kolmogorov complexity, or
descriptive complexity, defines the amount of information in terms of the
shortest program that generates the data set (on a universal Turing machine).
The intuition behind the theory is clear. If the data sets contain
regularities, we can use these in a program that produces the set.

###  3.1 Kolmogorov Complexity

We follow the standard reference for Kolmogorov complexity [7]. The set
$\\{0,1\\}^{\ast}$ contains all finite binary strings. ${\mathbb{N}}$ denotes
the natural numbers and we identify ${\mathbb{N}}$ and $\\{0,1\\}^{\ast}$
according to the correspondence:

$(0,\varepsilon),(1,0),(2,1),(3,00),(4,01),\ldots$

Here $\varepsilon$ denotes the empty word. The amount of information in a
number is specified as $I(n)=\log_{2}n$. The length $\mathit{l}(s)$ of $s$ is
the number of bits in the binary string $s$. Note that every natural number
$n$ corresponds to a string $s$ such that $l(s)=\lceil\log_{2}(n+1)\rceil$. If
$x$ is a string than $\overline{x}^{U}$ is the self delimiting code for this
string in the format of the universal Turing machine $U$. When we select a
reference prefix-free universal Turing machine $U$ we can define the prefix-
free Kolmogorov complexity $K(x)$ of an element $x\in\\{0,1\\}^{\ast}$ as the
length $\mathit{l}(p)$ of the smallest prefix-free program $p$ that produces
$x$ on $U$:

###### Definition 6

$K_{U}(x|y)=\min_{i}\\{\mathit{l}(\overline{i}):U(\overline{i}y)=x\\}$ The
actual Kolmogorov complexity of a string is defined as the one-part code:
$K(x)=K(x|\varepsilon)$

For two universal Turing machines $U_{i}$ and $U_{j}$, satisfying the
invariance theorem, the complexities assigned to a string $x$ will never
differ more than a constant: $|K_{U_{i}}(x)-K_{U_{j}}(x)|\leq c_{U_{i}U_{j}}$.
By prefixing a print program to any string $x$ one can prove that
$\forall(x)K(x)\leq l(x)+O(1)$. There are some basic problems with this
definition:

  1. 1.

It quantifies over all possible programs up till a certain length. This
implies that Kolmogorov complexity is uncomputable because of the Halting set.

  2. 2.

It is sensitive to our choice of reference Turing machine. This implies the
Kolmogorov complexity is an asymptotic measure that is correct up to a
constant.

  3. 3.

It does not give us any insight into the flow of information during the
computational process itself because it only focusses on computations that
halt irrespective of the amount of time needed to complete the process.

###  3.2 Information in numbers

Differential information theory moves away from algorithmic computing and
studies the way information flows through functions on natural numbers. The
main motivation for the development of differential information theory is the
formulation of a theory of information measurement that is 1) _non-asymptotic_
, and 2)_efficiently computable_. It is based on two very general constraints:

  * •

it studies recursive functions defined on the set of natural numbers and

  * •

it measures the information content of a natural number in terms of its
logarithm.

The choice for recursive fuctions on natural numbers helps us to reach these
objectives. The theory is orthogonal to existing quantitative theories, like
Shannon information and Kolmogorov complexity. Since recursion theory is
axiomatic, we do not have to bother about the selection of a universal Turing
machine: the set of recursive functions is our natural choice. We get a full
theory of measurement, as in Kologorov complexity, if we add a computable
enumeration of the recursive functions to the theory, but in general we will
approximate the complexity estimates from below by means of restricting
ourselves to efficiently computable recursive functions on strings with
maximum information. An additional bonus is the fact that recursive functions
have been studied to a much larger extend than programs for Turing machines
and there is a rich history of many deep results that we can use in our
analysis.

We start with some defintions. Given a number $r$ with a positional
representation666e.g. If $n=2$ we get a binary number system, if $n=10$ we
have a digital number system, etc. of length $n$ we have
$n=\lceil\log(r)\rceil$.

###### Definition 7

For a natural number $n$ the scale of $n$ is defined as
$\lceil\log_{2}n\rceil$.

It seems natural to take this value, that is associated with the length of a
representation, as a measure of the amount of information in a number, so,
abstracting from discrete representations. We define:

######  Definition 8 (Information in Natural numbers)

For all $n\in\mathbb{N}^{+}$:

$I(n)=\log_{2}n$ (12)

######  Definition 9 (Descriptive complexity)

Let $A$ be an infinite set of objects. An _information theory_ for $A$ is an
efficiently computable bijection $f:\mathbb{N}\rightarrow A$. For any $x\in A$
the _descriptive complexity_ of $x$ given $f$ is:

$I(x|f)=\log_{2}(f^{-1}(x))$

###### Example 7

The set $\mathbb{Z}$ can easily be mapped onto $\mathbb{N}$ by mapping the
even numbers to positive numbers and the uneven to negative numbers:

$g(x)=\begin{cases}0&\text{if }x=0\\\ 2x&\text{if }x>0\\\ -2x-1&\text{if
}x<0\end{cases}$

Given the fact the $g$ is an efficiently computable bijection we now have an
efficient information theory for $\mathbb{Z}$:

$I(x|g)=\log(g^{-1}(x))$ (13)

The information efficiency of this function is for positive $x\in\mathbb{Z}$:

$\Delta(f(x))=\log_{2}g^{-1}(x)-\log_{2}x=1$

This reflects the fact that by taking the absolute value of $x\in\mathbb{Z}$
we lose exactly $1$ bit of information about $x$. This bit is coded by the
function $g$ as it multiplies the absolute value of a positive element of
$\mathbb{Z}$ by a factor two and uses the interleaving spaces to code the
negative values. There are many other possible informarion theories for
$\mathbb{Z}$ and, as we shall see, designing the right information theory for
a set is in mnay cases non-trivial.

We get a theory about compressible numbers when we study information theories
for subsets of $\mathbb{N}$. If $f$ is a surjection then $x$ is an index of
the value $f(x)$. Let A be a subset of the set of natural numbers
$\mathbb{N}$. For any $n\in\mathbb{N}$ put $A(n)=\\{1,2,\ldots,n\\}\cap A$.
The _index function_ of $A$ is $i_{A}(j)=n$, where $n=a_{j}$ the $j$-th
element of $A$. The _compression function_ of $A$ is $c_{A}(n)=|A(n)|$. The
density of a set is defined if in the limit the distance between the index
function and the compression function does not fluctuate.

###### Definition 10

Let A be a subset of the set of natural numbers $\mathbb{N}$ with $c_{A}(n)$
as compression function. The lower asymptotic density $\underline{d}(A)$ of
$A(n)$ in $n$ is defined as:

$\underline{d}(A)=\liminf_{n\rightarrow\infty}\frac{c_{A}(n)}{n}$ (14)

We call a set _dense_ if $\underline{d}(A)>0$. The upper asymptotic density
$\overline{d}(A)$ of $A(n)$ in $n$ is defined as:

$\overline{d}(A)=\limsup_{n\rightarrow\infty}\frac{c_{A}(n)}{n}$ (15)

The natural density $d(A)$ of $A(n)$ in $n$ is defined when both the upper and
the lower density exist as:

$d(A)=\lim_{n\rightarrow\infty}\frac{c_{A}(n)}{n}$ (16)

With these definitions we can, for any subset $A$ of any countably infinite
set $\mathcal{A}$, estimate the density based on the density of the index set
of $A$. The density of the even numbers is $\frac{1}{2}$. The density of the
primes is $0$. Note that $d$ is not a measure. There exist sets $A$ and $B$
such that $d(A)$ and $d(B)$ are defined, but $d(A\cup B)$ and $d(A\cap B)$ are
not defined. The sequence
$A=\\{a_{1}<a_{2}<\ldots<a_{n}<\ldots;n\in\mathbb{N}\\}$ has a natural density
$\alpha\in[0,1]$ iff $d(A)=\lim_{n\rightarrow\infty}\frac{n}{c_{A}(n)}$ exists
[8]. There is a close relation between the density of a computable set and
compressibility:

######  Definition 11 (Asymptotic decay)

When the density of a recursive set $A(n)$ is defined then the asymtotic decay
function $f$ is defined by:

$\lim_{n\to\infty}\frac{c_{A}(n)f(n)}{n}=1$

In the limit every $n\in A$ can be compressed by $\log f(n)$ bits: $\log
a(n)+\log f(n)\approx\log n$.

The decay of the set of primes is $\ln n$ which in the limit gives a
compression of $\log\ln n$ bits for each prime.

######  Lemma 4 (Incompressibility of the set $\mathbb{N}$)

The density of the set of numbers compressible by more than a constant factor
is zero in the limit.

Proof: Suppose $A(n)$ is the set of compressible numbers. If the density is
defined, the asymptotic decay function is defined:

$\lim_{n\to\infty}\frac{c_{A}(n)f(n)}{n}=1$

which gives $\log c_{A}(n)+\log f(n)\sim\log n$. Members of $A(n)$ can be
compressed by a factor $\log f(n)$. If $\log f(n)$ is not bound by a constant
then $f(n)$ is growing strictly monotone which gives:

$\lim_{n\to\infty}\frac{c_{A}(n)}{n}=\frac{1}{f(n)}=0$

$\Box$

The set of decimal numbers that start with a $1$ has no natural density in the
limit. It flucutates between $1/9$ and $5/9$ indefinitely, but this set can be
easiliy described by a total function with finite information. The countable
subset of the Cantor set also has no defined density. There are also sets that
have density $1$ with infinite information: take the set of natural numers in
binary representation and scramble for each $k$ all the numbers with a
representation of length $k$. In such a set all the numbers keep the same
information content up to one bit, but the set has no finite description.

###  3.3 Typical (random, incompressible) strings and numbers

As a direct consequence of lemma 4 there must be an abundance of numbers that
cannot be redefined in terms of recursive functions with more efficient
representation. We will call these nubers, _random_ or _typical_. When we
think of string representations of these numbers their defining characteristic
is that they are _incompressible_. A number $x$ is compressible in some
context if there exists a representation shorter than
$\mathit{l}(x)=\lceil\log_{2}x+1\rceil$. By the equality
$\Sigma_{i=0}^{k}2^{i}=2^{k}-1$ there is at least one incompressible number in
the set of numbers with length $k$, and at most $2^{k-c}$ numbers can be
compressed to numbers of length $k-c$. The concepts of compressibility and
density of numbers are related. Random strings are an important proof tool
since they contain the maximum amount of information, exactly $k$ bits for a
string of length $k$. Although we cannot prove that a binary string is random,
we can specify some general characteristics:

  * •

Kolmogorov complexity tells us that, when we see some overt repeating pattern
in the string it cannot be random, since the pattern can be used in a program
generating the string.

  * •

Shannon information tells us that, if there is an unbalance in the number of
zeros and ones in a string, it cannot be random. Apparently, such a string was
generated by a system of messages with less than maximal entropy.

A useful concept is the notion of _randomness deficiency_ :

###### Definition 12

The _randomness deficiency_ of a string $x$ is $\delta(x)=\mathit{l}(x)-K(x)$.
A string $s$ is _typical_ or _random_ if $\delta(x)\leq\log\mathit{l}(x)$. A
string is _compressible_ if it is not typical.

###### Lemma 5

Almost all strings are typical: the density of the set of compressible strings
in the limit is $0$.

Proof: The set of finite binary strings is countable. The number of binary
strings of length $k$ or less is $\Sigma_{i=0}^{k}2^{i}=2^{k+1}-1$ so the
number of strings of length $k-d$, where $d$ is a constant is at most
$2^{k-d+1}-1$. A string $s$ is compressible if $\delta(s)\leq
c\log\mathit{l}(s)$, i.e. $K(s)<\mathit{l}(s)-c\log\mathit{l}(s)$. The density
of the number of strings that could function as a program to compress a string
$s$ in the limit is $\lim_{n\rightarrow\infty}(2^{k-c(\log k)+1}-1)/2^{k}=0$.
Since the upper density is zero, the lower- and natural density are defined
and both zero. $\Box$

Lemma 5 in the world of strings is the counterpart of lemma 4 in the world of
numbers. By the correspondence between binary strings and numbers these
results also hold for natural numbers. The randomness deficiency of a number
is $\delta(x)=\log_{2}x-K(x)$. Most numbers are typical, the density of the
set of compressible numbers is $0$ in the limit. Note that the existence of an
abundance of typical numbers is established by a simple counting argument. If
we measure the amount of information by means of the logarithm then most
numbers will be incompressible simply because the number of smaller numbers
that can be used to index compressible numbers decays exponentially with their
information content.

###  3.4 Typical sets

A useful concept for proofs using randomization techniques is that of a
_Typical Set_. A set is typical if it has no special qualities that
distinguish it from most other sets. To pin the concept down, we ask the
following question: Given a finite set $s$ of cardinality $|s|=n$, which
subsets of $n$ are hard to find?

###### Lemma 6

The typical (most information rich) subsets of a set $s$ with $n$ elements are
those that consist of a random selection of $\frac{n}{2}$ elements. The amount
of information in such a subset approaches $n$ bits.

Proof: The binomial distribution is symmetrical so we expect that the class of
the hardest subsets to be those with $\frac{n}{2}$ elements. We have the
following limit:

$\lim_{n\rightarrow\infty}\frac{\log_{2}{n\choose\frac{n}{2}}}{n}=1$ (17)

This is also a hard upper bound since the conditional information in a subset
of a set with $n$ elements can be characterized by a binary string of length
$n$. $\Box$

Figure 9: Schematic overview of the location of _typical sets_ in terms of a
cardinalility lattice ordered on the subset relation from top to bottom.
Typical sets are placed in the middle of the lattice. In order to move over
the lattice from sets with low conditional complexity sets like $S$ (via arrow
$A$) and $\emptyset$ (via arrow $B$) to any typical set $S_{i}$, we have to
make at least $n$ binary choices. An efficient deterministic algorithm cannot
do this but a non-deterministic algorithm can make the choices in linear time.

The location of typical sets in a lattice of subsets of a finite set $S$ is
given in figure 9. On top we find the set $S$ with cardinaltity $n$, at the
bottom the empty set $\emptyset$. The conditional information in these sets is
constant for all finite sets: $I(S|S)=O(1)$, $I(\emptyset)=0$. Exactly in the
middle we find a dense layer of mostly typical sets with cardinality
$\frac{n}{2}$. The conditional information of a typical set $S^{\prime}\subset
S$ is $I(S^{\prime}|S)\approx n$ bits. This makes typical sets _inaccessible_
for efficient deterministic algorithms:

###### Lemma 7

There is no deterministic algorithm that generates a typical subset of a set
$S$ in time polynomial to the cardinality of $S$.

Proof: Immediate consequence of lemma 6 and lemma 3. If the cardinality of $S$
is $n$ and $S^{\prime}$ is a typical subset of $S$ then
$I(S^{\prime}|S)\approx n$. By lemma 3 the maximum amount of information
produced by a deteministic algorith running in time $n^{c}$ is $c\log n\ll n$.
$\Box$

Another consequence of this analysis is:

###### Theorem 3.1

Information is not monotone over set theoretical operations.

Proof: Subsets can contain more information than their supersets. Consider the
set $S_{<n}$ of all natural numbers smaller than $n$. The descriptive
complexity of this set is $O(\log n)$. Create a set $A$ by selecting
$\frac{1}{2}n$ elements from $n$ under uniform distribution. This set is a
typical subset with $I(A|N)\approx n$, according to definition 4 and lemma 6.
The same holds for $B=S_{<n}-A$. Yet we have $S_{<n}=A\cup B$, so $I(A\cup
B)=O(\log n)\ll I(A)\approx I(B)\approx n$. $\Box$

I make some observations:

###### Observation 2

Typicality is a structural concept that is independent from to information in
the elements of the generating set.

###### Observation 3

Typical sets can be generated by non-deterministic algorithms in linear time.
See figure 9.

###### Observation 4

The notion of typicality is not defined for finite sets of natural numbers.
This is an immediate consequence of the fact that $\mathfrak{P}(\mathbb{N})$
is semi-countable.

###  3.5 Information efficiency of functions

We can now specify more exactly what it means for a function to ‘carry
information’. The _Information Efficiency_ of a function is the difference
between the amount of information in the input of a function and the amount of
information in the output. We use the shorthand $f(\overline{x})$ for
$f(x_{1},x_{2},\dots,x_{k})$:

######  Definition 13 (Information Efficiency of a Function)

Let $f:\mathbb{N}^{k}\rightarrow\mathbb{N}$ be a function of $k$ variables. We
have:

  * •

the _input information_ $I(\overline{x})$ and

  * •

the _output information_ $I(f(\overline{x}))$.

  * •

The information efficiency of the expression $f(\overline{x})$ is

$\Delta(f(\overline{x}))=I(f(\overline{x}))-I(\overline{x})$

  * •

A function $f$ is _information conserving_ if $\Delta(f(\overline{x}))=0$ i.e.
it contains exactly the amount of information in its input parameters,

  * •

it is _information discarding_ if $\Delta(f(\overline{x}))<0$ and

  * •

it has _constant information_ if $\Delta(f(\overline{x}))=0$.

  * •

it is _information expanding_ if $\Delta(f(\overline{x}))>0$.

Surjective total functions expand information, infective total functions
compress information and bijections preserve information. Classes of numbers
that are generated by monotonically expanding functions are unboundly
compressible and thus their density is zero. The same holds for results of
section 3.3: if a class of numbers is generated by an information expanding
function then the numbers in the class are not random.

###  3.6 Information Efficiency of Recursive Functions

We have defined $\forall(x\in\mathbb{N})I(x)=\log x$. Note that
$n\in\mathbb{N}$ is a _cardinality_ and that the measurements $I(n)$ represent
a cloud of _scalar_ point values in $\mathbb{R}$. The relation between the two
sets is described by the Taylor series for $\log(x+1)$:

$I(s+1)=\log(x+1)=\Sigma_{n=1}^{\infty}(-1)^{n-1}\frac{x^{n}}{n}$ (18)

We have $\lim_{x\rightarrow\infty}I(x+1)-I(x)=0$. In the limit the production
of information by incremental processes stops as specified by the derivative
$\frac{d}{dx}\ln x=\frac{1}{x}$. The intuition that one could express based on
this observation is that information in numbers in the limit becomes extremely
dense, much denser than the values in ‘normal’ counting processes: if we have
a recursive function that maps a search domain to the set of natural numbers,
then the information gain we realize by exploring any bounded neigbourhood
according to this mapping goes to zero as the complexity of the domain
increases. Differential information theory only works on finite domains.

Given definition 13. We can construct a theory about the flow of information
in computation. For primitive recursive functions we follow [9]. Given $\log
0=0$, the numbers $0$ and $1$ contain no information.

  * •

_Composition of functions_ is information neutral:

$\Delta(f(g(x)))+\Delta(g(x))=\log f(g(x))-\log g(x)+\log g(x)-\log x=$ $\log
f(g(x))-\log x$

  * •

The _constant function_ $z(n)=0$ carries no information
$z^{-1}z(n)=\mathbb{N}$.

  * •

The first application of the _successor function_ $s(n)=x+1$ is information
conserving:

$\Delta(s(0))=\log(0+1)-\log 0=0$

  * •

The _successor function_ expands information for values $>1$. By equation 18
we have:

$I(s)=\log(x+1)=\Sigma_{n=1}^{\infty}(-1)^{n-1}\frac{x^{n}}{n}>\log x$

Consequently:

$\Delta(s(x))=I(s(x))-\log x-\log 1=\log(x+1)-\log x=\epsilon>0$

Note that $\epsilon$ goes to zero as $x$ goes to $\infty$.

  * •

The _projection function_ $P_{i,n}((x_{1},x_{2},\dots,x_{n})=x_{i}$, which
returns the i-th argument $x_{i}$, is information discarding. Note that the
combination of the index $i$ and the ordered set $(x_{1},x_{2},..,x_{n})$
already specifies $x_{i}$ so:

$\Delta(P_{i,n}(x_{1},x_{2},..,x_{n})=I(x_{i})-\log
i-I(x_{1},x_{2},\dots,x_{n})<0$

  * •

_Substitution._ If $g$ is a function of $m$ arguments, and each of
$h_{1},\dots,h_{m}$ is a function of $n$ arguments, then the function $f$:

$f(x_{1},\dots,x_{n})=g(h_{1}(x_{1},\dots,x_{n}),\dots,h_{m}(x_{1},\dots,x_{n}))$

is definable by composition from $g$ and $h_{1},\dots,h_{m}$. We write
$f=[g\circ h_{1},\dots,h_{m}]$, and in the simple case where $m=1$ and $h_{1}$
is designated $h$, we write $f(x)=[g\circ h](x)$. Substitution is information
neutral:

$\Delta(f(x_{1},\dots,x_{n}))=\Delta(g(h_{1}(x_{1},\dots,x_{n}),\dots,h_{m}(x_{1},\dots,x_{n})))=$
$I(f(x_{1},\dots,x_{n}))-I(x_{1},\dots,x_{n})$

Where $I(f(x_{1},\dots,x_{n}))$ is dependent on $\Delta(g)$ and $\Delta(h)$.

  * •

_Primitive Recursion._ A function $f$ is definable by primitive recursion from
$g$ and $h$ if $f(x,0)=g(x)$ and $f(x,s(y))=h(x,y,f(x,y))$. Primitive
recursion is information neutral:

$\Delta(f(x,0))=\Delta(g(x))=I(g(x)-I(x)$

which dependent on $I(g(x)$ and

$\Delta(f(x,s(y)))=\Delta(h(x,y,f(x,y)))=I(h(x,y,f(x,y)))-I(x)-I(y)$

which is dependent on $I(h(x,y,f(x,y)))$.

Summarizing: the primitive recursive functions have one information expanding
operation, _increment_ , one information discarding operation, _choosing_ ,
all the others are information neutral. With the primitive recursive functions
we can define everyday mathematical functions like addition, substraction,
multiplication, division, exponention etc. In order to get full Turing
equivalence one must add the $\mu$-operator (See appendix in paragraph 11.1
for a discussion).

###  3.7 Information Efficiency of Elementary Arithmetical Operations

The information efficiency of more complex operations is defined by a
combination of counting and choosing. We analyse the definition of addition by
primitive recursion: suppose $f(x)=P^{1}_{1}(x)=x$ and
$g(x,y,z)=S(P_{2}^{3}(x,y,z))=S(y)$. Then $h(0,x)=x$ and
$h(S(y),x)=g(y,h(y,x),x)=S(h(y,x))$. The information efficiency is dependent
on the balance between choosing and counting in the definition of $g$:

$\Delta(g(x,y,z))=I(S(y))-I(x,y,z)=(\Sigma_{n=1}^{\infty}(-1)^{n-1}\frac{y^{n}}{n})-I(x,y,z)$

Note that the operation looses information and the information loss is
asymmetrical. The commutativity and associativity of information efficiency
for complex arithmetical operations are not trivial:

######  Theorem 3.2 (Information Efficiency of Elementary Arithmetical
Operations)

  * •

_Addition of different variables is information discarding_. In the case of
addition we know the total number of times the successor operation has been
applied to both elements of the domain: for the number $c$ our input is
restricted to the tuples of numbers that satisfy the equation $a+b=c$
$(a,b,c\in\mathbb{N})$. Addition is information discarding for numbers $>2$:

$\Delta(x+y)=\log(x+y)-\log x-\log y<0$ (19)

  * •

_Addition of the same variable has constant information_. It measures the
reduction of information in the input of the function as a constant term:

$\forall(x)\Delta(x+x)=\log 2x-\log x=\log 2$ (20)

  * •

_Commutativity for addition is information efficient:_

$\Delta(x+y)=\log(x+y)-\log x-\log y=\log(y+x)-\log y-\log x=\Delta(y+x)$ (21)

  * •

_Associativity for addition is information efficient:_

$\begin{split}\Delta(x+(y+z))=\log(x+(y+z))-\log x-\log(y+z)=\\\
\log((x+y)+z)-\log(x+y)-\log z=\Delta((x+y)+z)\end{split}$ (22)

  * •

_Multiplication of different variables is information conserving._ We call
this operation _extensive_ : it concerves the amount of information but not
the structure of generating numbers. In the case of multiplication $a\times
b=c$ $(a,b,c\in\mathbb{N})$ the set of tuples that satisfy this equation is
much smaller than for addition and thus we can say that multiplication carries
more information. If $a=b$ is prime (excluding the number $1$) then the
equation even identifies the tuple. Multiplication is information conserving
for numbers $>2$:

$\Delta(x\times y)=\log(x\times y)-\log x-\log y=0$ (23)

  * •

_Multiplication by the same variable is information expanding_. It measures
the reduction of information in the input of the function as a logarithmic
term:

$\forall(x)\Delta(x\times x)=\log(x\times x)-\log x=\log x>0$ (24)

  * •

_Commutative for multiplication is information efficient:_

$\Delta(x\times y)=\log(x\times y)-\log x-\log y=\log(y\times x)-\log y-\log
x=\Delta(y\times x)$ (25)

  * •

_Associativity for multiplication is information efficient:_

$\begin{split}\Delta(x\times(y\times z))=\log(x\times(y\times z))-\log
x-\log(y\times z)=\\\ \log((x\times y)+z)-\log(x\times y)-\log
z=\Delta((x\times y)\times z)\end{split}$ (26)

##  4 From $\mathbb{N}$ to $\mathbb{N}^{2}$: Planar information theories

A dilation is a function $f$ from a metric space into itself that satisfies
the identity $d(f(x),f(y))=rd(x,y)$ for all points $(x,y)$, where $d(x,y)$ is
the distance from $x$ to $y$ and $r$ is some positive real number. Dilations
preserve the shape of an object (See figure 10).

Figure 10: Dilation of a complex geometric figure in two-dimensional Euclidean
space. The shape and orientation of the image is preserved. The size varies.

In a discrete space like $\mathbb{N}^{2}$ a dilation takes a different form.
We need an alternative notion of distance:

###### Definition 14

The _taxicab distance_ between two points ${\bf{a}}=(x_{1},y_{1})$ and
${\bf{b}}=(x_{2},y_{2})$ is:

$d({\bf{a}},{\bf{b}})=|x_{1}-x_{2}|+|y_{1}-y_{2}|$

Figure 11: An illustration of the taxicab distance. Unlike the situation in
Euclidean space there is no shortcut to point $(m,n)$.  Figure 12: Dilation
with a factor $3$ over the discrete plane $\mathbb{N}^{2}$. The taxicab
distance of points on the counter diagonals is preserved. The density of the
set after a dilation by a factor $n$ is $\frac{1}{n^{2}}$, in this case
$\frac{1}{3^{2}}=\frac{1}{9}$.

We define ${\bf{0}}=(0,0)$. There are exactly $k+1$ points ${\bf{a}}=(x,y)$,
with $d({\bf{a}},{\bf{0})}=k$. All points with the same distance to the origin
are situated on the counter diagonal.The distance function in Euclidean space
is $x^{2}+y^{2}=r^{2}$, a second degree equation that defines a semi-circle,
while in discrete space we have $x+y=r$, a first degree equation that defines
the counter diagonal (See figure 11).

###### Lemma 8

Point ${\bf{a}}=(x,y)$ with taxicab distance $k=x+y$ to the origin has
entropy:

$H({\bf{a}})=-\frac{x}{k}\log\frac{x}{k}-\frac{y}{k}\log\frac{y}{k}$

This is also the entropy rate of stochastic walks over the plane in the
directions $\frac{x}{y}$ or $\frac{y}{x}$.

Proof: There are exactly $n+m\choose m$ different ascending paths from the
origin ${\bf{0}}=(0,0)$ to the point with coordinates $(x,y)$. These paths can
be expressed as binary strings of length $x+y$, with $1$ for a step in the $x$
direction and $0$ for a step in the $y$ direction. All strings associated with
paths on the line $x=\frac{x}{y}$ have the same Shannon entropy:
$-\frac{x}{x+y}\log\frac{x}{x+y}-\frac{y}{x+y}\log\frac{y}{x+y}$. $\Box$

I make some observations:

  1. 1.

Random strings with max entropy are located on the line $x=y$.

  2. 2.

Walks in the directions $x=c$ or $y=c$ have zero entropy in the limit.

  3. 3.

The set $\\{0,1\\}^{k}$ charaterizes all paths to points with taxicab distance
$k$.

  4. 4.

This gives an embedding of the uncountable object $\\{0,1\\}^{\infty}$ in the
discrete plane. The plane itself is countable but the number of ascending
walks we can make on this plane is transfinite.

Using the taxicab distance we can define the notion of a discrete dilation
(See figure 12):

###### Definition 15

A _discrete dilation_ is a function
$f:\mathbb{N}^{k}\rightarrow\mathbb{N}^{k}$ from a discrete space into itself
that satisfies the identity $d(f(x),f(y))=rd(x,y)$ for all points $(x,y)$,
where $d(x,y)$ is the taxicab distance from $x$ to $y$ and $r$ is some natural
number.

${\mathbb{N}^{2}}$${\mathbb{N}}$${\mathbb{N}^{2}}$${\mathbb{N}}$$\scriptstyle{\pi^{k}}$$\scriptstyle{\rho_{n}}$$\scriptstyle{\tau_{n}}$$\scriptstyle{\pi^{k}}$
Figure 13: The effect of a dilation
$\rho_{n}:\mathbb{N}^{2}\rightarrow\mathbb{N}^{2}$ given the fact that
$\pi^{k}$ is a bijection. There is a correponding dilation
$\tau_{n}:\mathbb{N}\rightarrow\mathbb{N}$.

Note that a dilation of the discrete plane is also an injection. If the
function $\pi^{k}:\mathbb{N}^{k}\rightarrow\mathbb{N}$ is a bijection and
$\rho_{n}:\mathbb{N}^{2}\rightarrow\mathbb{N}^{2}$ a dilation by a factor $n$
then there will be a corresponding dilation
$\tau_{n}:\mathbb{N}\rightarrow\mathbb{N}$. The relations are given in figure
13. Both dilations will give a uniform density reduction to $\frac{1}{n^{2}}$.

###  4.1 The Cantor pairing functions

The set of natural numbers $\mathbb{N}$ can be mapped to its product set by
the so-called Cantor pairing function
$\pi:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ (and its symmetric
counterpart) that defines a two-way polynomial time computable bijection:

$\pi(x,y):=\frac{1}{2}(x+y)(x+y+1)+y$ (27)

Figure 14: An initial segment of the Cantor pairing function

Note that the Cantor pairing function uses the taxicab distance to order
points on the plane. If ${\bf{a}}=(x,y)$, with $d({\bf{a}},{\bf{0}})=k$ then:

$\pi({\bf{a}})=\pi(x,y)=\frac{1}{2}(k)(k+1)+y=y+\sum_{1}^{k}i$ (28)

Consquently lemma 8 is relevant for an understanding of the information
theoretical behaviour of the function. The Fueter - Pólya theorem [4] states
that the Cantor pairing function and its symmetric counterpart
$\pi^{\prime}(x,y)=\pi(y,x)$ are the only possible quadratic pairing
functions. Note that there exist many other polynomial time computable
bijective mappings between $\mathbb{N}\times\mathbb{N}$ and $\mathbb{N}$ (e.g.
Szudzik pairing)777See http://szudzik.com/ElegantPairing.pdf, retrieved
January 2016. and $\mathbb{N}^{k}$ and $\mathbb{N}$. A segment of this
function is shown in figure 14.

Figure 15: The information efficiency of the Cantor pairing function,
$0<x<10^{9}$, $0<y<10^{9}$, $-1<z<7$. The shaded area is the $z=0$ surface.
The Cantor index values stay at least one bit above this plane, because of
symmetry. Close to the lines $x=0$ and $y=0$ the Cantor index contains orders
of magnitude more information than the input, which indicates that the Cantor
bijection is inefficient close to the edges of the space.

The information efficiency of this function is:

$\Delta(\pi(x,y))=\log(\frac{1}{2}(x+y+1)(x+y)+y)-\log x-\log y$ (29)

For the majority of the points in the space $\mathbb{N}^{2}$ the function
$\pi$ has an information efficiency close to one bit. This total lift of the
graph with one bit is easily explained by the symmetry of the plane over the
diagonal $x=y$. There are two ordered pairs $(a,b)$ and $(b,a)$ but there is
only one set $\\{a,b\\}$. In the formula
$\Delta(\pi(x,y))=\log(\frac{1}{2}(x+y+1)(x+y)+y)-\log x-\log y$ the input is
an ordered pair $(x,y)$, but the order of the terms $-\log x-\log y$ is
irrelevant. Consequently the input always contains at least one bit of
information more than the balance factor $-\log x-\log y$. The pairing
function defines what one could call: a _discontinuous folding operation over
the counter diagonals_. On the line $y=0$ we find the images
$1/2x(x-1)=\Sigma_{i}^{x}i$. Equation 29 can be seen as the description of an
information topology. The Cantor function runs over the counter diagonals and
the image shows that the information efficiencies of points that are in the
same neighborhood are also close. The coding given by the Cantor pairing
function is maximally efficient near the diagonal $x=y$ and unboundedly
inefficient near the edges $x=0$ and $y=0$. This illustrates the fact that
$\mathbb{N}^{2}$ is an object that is fundamentally different from
$\mathbb{N}$. Objects of a dimension higher than $1$ display non-trivial
behavior in the context of information theory. One aspect I want to point out
explicitly, because it is vital for the rest of the paper:

###### Observation 5

Planar representations of linear datasets are inherently inefficient.

The surface of the plot in figure 15 _never_ crosses the surface $z=1$. The
embedding of $\mathbb{N}$ in $\mathbb{N}^{2}$ is _inefficient_ for _every_
element of those sets. The lift to the surface $z=1$ is caused by the fact
that we measure the input for the information efficiency function in terms of
sets. If we use ordered pairs instead the surface will drop $1$ bit to $z=0$.
This makes the cantor function $\pi(x,y)=z$ prima facie a sort of
computational _perpetuum mobile_ : in most cases $z$ contains more information
than the elements of the ordered pair $(x,y)$. Ordered pairs have more
structure than isolated numbers and this structure contains information.
Specifically when $x\ll y$ or $y\ll x$ the function $\pi(x,y)=z$ does a bad
job. In most cases these irregularities have no great impact on our
computational processes, but as soon as the difference between $x$ and $y$ is
exponential the effects are considerable, and relevant for our subject For
some data sets, search in $\mathbb{N}$ might be much more effective than
search in $\mathbb{N}^{2}$ and vice versa.

The Cantor pairing functions play an important role in differential
information theory since they allow us to develop information theories for
multi-valued functions and richer sets. An example: Cantor himself already
gave the the proof of the countability of the rational numbers. A rational
number has the form $\frac{a}{b}$ where $a,b\in\mathbb{N}$. It corresponds to
an ordered pair $(a,b)$, which can be mapped on a two-dimensional cartesian
grid. We can map the rational numbers onto the natural numbers by counting
them along the counter diagonal. Georg Cantor himself used this construction
to prove the countability of the set $\mathbb{Q}$, but it also provides us
with an efficient theory of information measurement by the following
definition:

$g_{\mathbb{Q}}(\frac{x}{y})=\pi(x,y)$ (30)

$\forall(x,y\in\mathbb{N})(I(\frac{x}{y})=\log(g_{\mathbb{Q}}(\frac{x}{y}))$
(31)

A visual impression of the information efficiency of this function is given in
figure 15. Following equation 33 the information efficiency of this theory of
measurement for a rational number $n=\frac{a}{b}$ is solely dependent on the
value $\frac{a}{b}$, independent on the size of $n$. We analyse some limits
that define the information efficiency of the function. On the line $y=x$ we
get:

$\lim_{x\rightarrow\infty}\Delta\pi(x,x)=\lim_{x\rightarrow\infty}\log(\frac{1}{2}(2x+1)(2x))-2\log
x=$ (32)

$\lim_{x\rightarrow\infty}\log\frac{2x^{2}+x}{x^{2}}=1$

For the majority of the points in the space $\mathbb{N}^{2}$ the function
$\pi$ has an information efficiency close to one bit. On every line through
the origin $y=hx$ $(h>0)$ the information efficiency in the limit is constant:

$\lim_{x\rightarrow\infty}\Delta(\pi(x,hx))=$ (33)
$\lim_{x\rightarrow\infty}\log(\frac{1}{2}(x+hx+1)(x+hx)+hx)-\log x-\log hx=$
$\log(1/2(h+1)^{2})-\log h$

Yet on every line $y=c$ (and by symmetry $x=c$) the information efficiency is
unbounded:

$\lim_{x\rightarrow\infty}\Delta(\pi(x,c))=$ (34)
$\lim_{x\rightarrow\infty}\log(\frac{1}{2}(x+c+1)(x+c)+c)-\log x-\log
c=\infty$

Together the equations 27, 29, 32, 33 and 34 characterize the basic behavior
of the information efficiency of the Cantor function.

Figure 16: Row expansion by factor $2$ and dilation by a factor 2 for the
segment in Figure 14. For a computation of the exact information efficiency
see figure 17.  Figure 17: An exact computation of the point by point
information efficiency after an dilation by a factor $2$ for a segment (1-4 by
1-19) of the table in figure 16. The existence of two seperate interleaving
information efficiency functions is clearly visible.  Figure 18: A fragment of
the bijection generated by an dilation by a factor $2$ for a segment (0-4 by
0-9) of the table in figure 16. The bijection
$\pi(\epsilon_{2}(\pi^{-1})):\mathbb{N}\rightarrow\mathbb{N}$ generates a
cloud of compressible and expandable points. The compressible points are above
the line $x=y$.

###  4.2 Linear dilations of the Cantor space

Now that we have a two-dimensional representation of the set of natural
numbers we can start to develop, what one could call, _dilation theory_ : the
study of the information effects of recursive operations on natural numbers on
this set in terms of topological deformations of the discrete plane. We start
with simple linear dilations over the $y$-axis that define bijections on
$\mathbb{N}$.

Equation 34 is responsible for remarkable behavior of the Cantor function
under _elastic dilations_. For such dilations we can compress the Cantor space
along the $y$-axis by any constant without actually losing information.
Visually one can inspect this counter intuitive phenomenon in figure 15 by
observing the concave shape of the information efficiency function: at the
edges ($x=0$, $y=0$) it has in the limit an unbounded amount of compressible
information. The source of this compressibility in the set $\mathbb{N}$ is the
set of numbers that is logarithmically close to sets $\frac{1}{2}x(x+1)$ and
$\frac{1}{2}y(y+1)+y)$. In terms of Kolmogorov complexity these sets of points
define regular dips of depth $\frac{1}{2}\log x$ in the integer complexity
function that in the limit provides an infinite source of highly compressible
numbers. In fact, when we would draw figure 15 at any scale over all functions
$f:\mathbb{N}^{2}\rightarrow\mathbb{N}$ we would see a surface with all kinds
of regular and irregular elevations related to the integer complexity
function.

Observe figure 16. The upper part shows a discrete translation over the
$x$-axis by a factor $2$. This is an information expanding operation: we add
the factor $2$, i.e. one bit of information, to each $x$ coordinate. Since we
expand information, the density of the resulting set in $\mathbb{N}^{2}$ also
changes by a factor 2. In the lower part we have distributed the values in the
columns $0,2,4,\dots$ over the columns $0-1,2-3,4-5,\dots$. We call this an
dilation by a factor $2$. The space $10\times 10=100$ is transformed into a
$5\times 20=100$ space. The exact form of the translation is:
$\epsilon_{2}(x,y)=(2x+(y\bmod{2}),\lfloor\frac{y}{2}\rfloor)$.

Figure 19: The information efficiency of the reference function of the Cantor
packing function on the same area as in figure 15 after a dilation by a factor
100, $0<x<10^{9}$, $0<y<10^{9}$, $-1<z<10.6$. The shaded area is the $z=0$
surface.

The effect of this dilation on the information efficiency on a local scale can
be seen in figure 17. After some erratic behavior close to the origin the
effect of the translation evens out. There are traces of a phase transition:
close to the origin the size of the $x$, $y$ coordinates is comparable to the
size of the shift $c$, which influences the information efficiency
considerably. From the wave pattern in the image it is clear that a linear
dilation by a factor $c$ essentially behaves like a set of $c$ functions (in
this case $2$), each with a markedly different information efficiency.

Even more interesting is the behavior, shown in figure 18, of the bijection:

${\mathbb{N}}$${\mathbb{N}^{2}}$${\mathbb{N}^{2}}$${\mathbb{N}}$$\scriptstyle{\pi^{-1}}$$\scriptstyle{\epsilon_{2}}$$\scriptstyle{\pi}$
(35)

Although the functions $\pi$, $\pi^{-1}$ and $\epsilon_{2}$ are bijections and
can be computed point wise in polynomial time, all correlations between the
sets of numbers seems to have been lost. The reverse part of the bijection
shown in formula 36 seems hard to compute, without computing large parts of 35
first.

${\mathbb{N}}$${\mathbb{N}^{2}}$${\mathbb{N}^{2}}$${\mathbb{N}}$$\scriptstyle{\pi^{-1}}$$\scriptstyle{\epsilon_{2}^{-1}}$$\scriptstyle{\pi}$
(36)

###### Observation 6

Linear dilations introduce a second type of _horizontal discontinuous folding
operations over the columns._. These operations locally distort the smooth
topology of the Cantor function into clouds of isolated points.

On a larger scale visible in figure 19 we get a smooth surface. The distortion
of the symmetry compared to figure 15 is clearly visible. In accordance with
equation 34, nowhere in the set $\mathbb{N}^{2}$ the information efficiency is
negative. In fact the information efficiency is lifted over almost the whole
surface. On the line $x=y$ the value in the limit is:

$\lim_{x\rightarrow\infty}\Delta\pi(\epsilon_{2}((x,x)))=$ (37)
$\lim_{x\rightarrow\infty}\log(\frac{1}{2}(2x+x/2+1)(2x+x/2)+x/2)-\log 2x-\log
x/2=2\log 5-3$

Figure 20: The first information efficiency function of the Cantor packing
function on the same area as in Figure 15 after a dilation by a factor 100,
$0<x<10^{9}$, $0<y<10^{9}$, $-1<z<17$. The shaded area is the $z=0$ surface.
For this transformation we have $100$ different information efficiency
functions. Only the first is shown.

A more extreme form of such a distortion can be seen in figure 20 that shows
the effect on the information efficiency after a dilation by factor $100$.
Clearly the lift in information efficiency over the whole surface can be seen.
We only show the first of $100$ different information efficiency functions
here. Computed on a point by point basis we would see periodic saw-tooth
fluctuations over the $x$-axis with a period of $100$. This discussion shows
that dilations of the Cantor space act as a kind of _perpetuum mobile_ of
information creation. For every dilation by a constant $c$ the information
efficiency in the limit is still positive:

###### Lemma 9

No compression by a constant factor $c$ along the $y$-axis (or $x$-axis, by
symmetry) will generate a negative information efficiency in the limit.

Proof: immediate consequence of equation 34. The information efficiency is
unbounded in the limit on every line $x=c$ or $y=c$. $\Box$

###  4.3 A general model of elastic dilations

In the following we will study a more general model of _dilations_ of the
space $\mathbb{N}^{2}$:

###### Definition 16

The function $\epsilon_{f}:\mathbb{N}^{2}\rightarrow\mathbb{N}^{2}$ defines an
_elastic dilation_ by a function $f$ of the form:

$\epsilon_{r}(x,y)=(xf(x)+(y\bmod{r(x)}),\lfloor\frac{y}{r(x)}\rfloor)$ (38)

Such a dilation is _super-elastic_ when:

$\lim_{x\rightarrow\infty}r(x)=\infty$

It is _polynomial_ when it preserves information about $x$ :

$\lim_{x\rightarrow\infty}r(x)=cx^{k}$

It is _linear_ when:

$r(x)=c$

The _reference function_ of the dilation is:

$\epsilon^{\prime}_{r}(x,y)=(r(x)x,\frac{y}{r(x)})$

We will assume that the function $f$ can be computed in time polynomial to the
length of the input.

Observe that the reference function:
$\epsilon^{\prime}_{r}(x,y)=(r(x)x,\frac{y}{r(x)})$ is information neutral on
the arguments:

$\log x+\log y-(\log r(x)x+\log\frac{y}{r(x)})=0$

A dilation consists from an algorithmic point of view of two additional
operations:

  1. 1.

An _information discarding_ operation on
$y:\frac{y}{r(x)}\rightarrow\lfloor\frac{y}{r(x)}\rfloor$.

  2. 2.

An _information generating_ operation on $x:r(x)x\rightarrow
r(x)x+(y\bmod{r(x)})$.

Figure 21: A dilation from neighborhood $\alpha$ to neighborhood $\beta$.

A schematic overview of a linear dilation is given in figure 21. Here the
letters $a,\dots i$ are natural numbers. An arbitrary point in neighborhood
$\alpha$ with coordinates $(b,f)$ close to the diagonal is translated to point
$(a,h)$ in neighborhood $\beta$. The formula for the translation is given by
definition 16:
$\epsilon_{r}(x,y)=(r(x)x+(y\bmod{r(x)}),\lfloor\frac{y}{r(x)}\rfloor)$. We
have $a=\lfloor\frac{b}{r(f)}\rfloor$ and $h=r(f)e+(b\bmod{r(f)})$.

The information efficiency of an _elastic dilation_ is:

$\Delta(\pi(\epsilon_{r})(x,y))=\Delta(\pi(r(x)x+(y\bmod{r(x)}),\lfloor\frac{y}{r(x)}\rfloor))$

The information efficiency of a _linear dilation_ by a factor $f(x)=c$ is:

$\Delta(\pi(cx+(y\bmod c),\lfloor\frac{y}{c}\rfloor))$

###### Observation 7

Dilations by a constant $c$ of the Cantor space replace the highly efficient
Cantor packing function with $c$ different interleaving functions, each with a
different information efficiency. Equation 38 must be seen as a _meta-
function_ or _meta-program_ that spawns off $c$ different new programs.

This is illustrated by the following lemma:

###### Lemma 10

Linear dilations generate information.

Proof: This is an immediate effect of the use of the mod function. A _dilation
by a constant $c$_ of the form:

$\epsilon_{c}(x,y)=(cx+(y\bmod c),\lfloor\frac{y}{c}\rfloor)$

has $c$ different information efficiency functions. Note that the function
$x\bmod c$ produces all numbers $d<c$, including the incompressible ones that
have no mutual information with $c$: $K(d|c)=\log d+O(1)$.For each value
$d=y\bmod c$ we get a function with different information efficieny:

$\Delta(\pi(\epsilon_{c,d}(x,y))))=\log\pi(cx+d,\lfloor\frac{y}{c}\rfloor)-\log
x-\log y$

On a point by point basis the number $d$ is part of the information computed
by $\pi(\epsilon_{c,d}(x,y)))$. In other words the computation
$\pi(\epsilon_{c,d}(x,y))$ adds information to the input for specific pairs
$(x,y)$ that is not available in the formula for $\epsilon_{c}(x,y)$. The
effect is for linear dilations constant in the limit, so it is below the
accuracy of Kolmogorov complexity. $\Box$

For typical cells $(x,hx)$ on a line $y=hx$ the function
$\Delta(\pi(\epsilon^{\prime}_{c}(x,y)))$ gives in the limit a constant shift
which can be computed as:

$\lim_{x\rightarrow\infty}\frac{\pi(\epsilon^{\prime}_{c}(x,y))}{\pi(x,y)}=\lim_{x\rightarrow\infty}\frac{\frac{1}{2}(cx+\frac{hx}{c}+1)(cx+\frac{hx}{c})+\frac{hx}{c}}{\frac{1}{2}(x+hx+1)(x+hx)+hx}=\frac{(c^{2}+h)^{2}}{c^{2}(1+h)^{2}}\geq
1$ (39)

Note that this value is only dependent on $h$ and $c$ for all
$c\in\mathbb{N}^{+}$ and $r\in\mathbb{R}^{+}$. The general lift of the line
$x=y$ for a dilation by a constant $c$ is:

$\lim_{x\rightarrow\infty}\log(\frac{1}{2}(cx+\frac{x}{c}+1)(cx+\frac{x}{c})+\frac{x}{c}))-\log
cx-\log\frac{x}{c}=$ (40)

$-\log\frac{2}{c}-\log c+\log(2+\frac{1}{c^{2}}+c^{2})$

We get a better understanding of the extreme behavior of the reference
function $\Delta(\pi(\epsilon^{\prime}_{c}(x,y)))$ when we rewrite equation 39
as:

$\frac{(c^{2}+h)^{2}}{c^{2}(1+h)^{2}}=\frac{c^{2}}{1+2h+h^{2}}+\frac{2h}{1+2h+h^{2}}+\frac{h^{2}}{c^{2}+2c^{2}h+c^{2}h^{2}}\geq
1$

and take the following limit:

$\lim_{h\rightarrow\infty}\frac{(c^{2}+h)^{2}}{c^{2}(1+h)^{2}}=c^{-2}$

If $c$ is constant then it has small effects on large $h$ in the limit. The
reference function allows us to study the dynamics of well-behaved “guide
points” independent of the local distortions generated by the information
compression and expansion operations. Note that dilations start to generate
unbounded amounts of information in each direction $y=hx$ in the limit on the
basis of equation 39:

$\lim_{c\rightarrow\infty}\frac{(c^{2}+h)^{2}}{c^{2}(1+h)^{2}}=\infty$ (41)

If $c$ grows unboundedly then the information efficiency of the corresponding
reference functions goes to infinity for every value of $h$. Consequently,
when $c$ goes to infinity, the reference functions predict infinite
information efficiency in $\mathbb{N}^{2}$ in all directions, i.e. we get
infinite expansion of information in all regions without the existence of
regions with information compression. This clearly contradicts central results
of Komogorov complexity if we asume that dilations are defined in terms of a
single program. The situation is clarified by the proof of lemma 10: if $c$
goes to infinity we create an unbounded amount of new functions that generate
an unbounded amount of information.

###  4.4 Polynomial transformations

The picture that emerges from the previous paragraphs is the following: we can
define bijections on the set of natural numbers that generate information for
almost all numbers. The mechanism involves the manipulation of clouds of
points of the set $\mathbb{N}$: sets with density close to the origin are
projected into sparse sets of points further removed from the origin. This
process can continue indefinitely.

In this context we analyse polynomial translations. The simplest example is
the dilation by the factor $x$:

Figure 22: Row expansion by a superlinear, $r(x)=x$ factor and a fragment of
the corresponding dilation for the segment in Figure 14

$\epsilon_{x}(x,y)=(x^{2}+(y\bmod{x}),\lfloor\frac{y}{x}\rfloor)$ (42)

Figure 23: Above: Super linear expansion by a function $r(x)=x$ up to 32.
Below: Linear dilation by a factor $2$ up to the number $32$.

A tiny fragment of the effects is shown in figure 22. There does not seem to
be a fundamental difference compared to the previous examples and there seems
to be no difficulty in constructing such a translation along the lines
suggested in the figure. However upon closer inspection things are different
as can be observed in figure 23. The first table shows the computation of the
function up to the number $32$. Observe that the columns $14$ and $15$ are
empty, while column $16-18$ have a value. This effect does not appear in the
second table. Linear dilations induce a change in the direction of the iso-
information line $(d,g)$, but the image of the translation keeps a coherent
topology at any stage of the computation.

Polynomial translations on the other side are discontinuous. They tear the
space apart into separate regions. An appropriate metaphor would be the
following: expansion away from the origin over the $x$-axis, sucks a _vacuum_
that must be filled by a contraction over the $y$-axis. Actually the creation
of such a vacuum is an information discarding operation. The analysis above
shows that the vacuum created by the shift described by equation 42 for cells
on the line $y=0$ is bigger than the _whole surface_ of the triangle
$(o,d,g)$. The effect is that the image of the translation becomes
discontinuous.

###### Theorem 4.1

Polynomial dilations of $\mathbb{N}^{2}$:

  1. 1.

Discard and expand information on the line $y=0$ unboundedly.

  2. 2.

Project a dense part of $\mathbb{N}^{2}$ and $\mathbb{N}$ on $y=0$.

  3. 3.

Generate an unbounded amount of information for typical points in
$\mathbb{N}^{2}$ in the limit.

Proof: The formula for a polynomial translation is:

$\epsilon_{r}(x,y)=(cx^{k+1}+(y\bmod{cx}),\lfloor\frac{y}{cx}\rfloor)$

Take $k=c=1$. Consider a typical point $f$ in figure 21. We may assume that
the numbers $d$ and $g$ are typical (i.e. incompressible and thus $\pi(g,d)$
is inompressible too. Remember that the Cantor function runs over the counter
diagonal which makes the line $(d,g)$ an _iso-information_ line.

  1. 1.

Discard and expand information on the line $y=0$ unboundedly:

     * •

Discard information: Horizontally point $(f,0)$ will be shifted to location
$(f^{2},0)$ and $(f(+1),0)$ to $(f^{2}+2f+1,0)$. The cantor index for point
$(f,0)$ is $\frac{1}{2}f(f-1)<f^{2}$.

     * •

Expand information: The cells from $(f,0)$ to $f(f,2f)$ will be “padded” in
the strip between $(f^{2},0)$ and $(f^{2}+2f+1,0)$. But this operation
“steals” a number of $f$ cells from the domain above the line $(d,g)$. Now
take a typical point $n$ on location $(f,m)$. such that $f<m<2f$. This point
will land at $(f^{2}+m,0)$ somewhere between $(f^{2},0)$ and $(f^{2}+2f+1,0)$,
which gives:

$\pi(f,(f+m))=\frac{1}{2}(f+(f+m)+1)(f+(f+m))+(f+m)=$
$2f^{2}+\frac{1}{2}fm+m^{2}+3f+1\frac{1}{2}(m+fm)$ $\gg f^{2}+2f+1$

Note that the effects are dependent on $f$ and $m$, so they are unbounded in
the limit. Alternatively observe the fact that polynomial dilations are
superelastic and apply equation 41.

  2. 2.

Project a dense part of $\mathbb{N}^{2}$ and $\mathbb{N}$ on $y=0$: For every
point $f$ all the cells $(f,0)$ to $f(f,2f)$ up to the line $y=2x$ will end up
on line $y=0$. since all points in this dense region are projected on the line
$y=0$ most points $\pi(f,(f+m))$ are incompressible.

  3. 3.

Generate an unbounded amount of information for typical points in
$\mathbb{N}^{2}$ in the limit. Take a typical point $(x,y)$ such that $\log
x\approx\log y$:

$\pi(\epsilon_{r}(x,y))>\pi(\epsilon_{r}(x,1))=\frac{1}{2}(x^{2}+2)(x^{2}+1)+1>\frac{1}{2}x^{4}$
(43) $\Delta(\pi(\epsilon_{r}(x,y)))>\log\frac{1}{2}x^{4}-\log x-\log y\approx
4\log x-2\log x=2\log x$

which gives $K\pi(\epsilon_{r}(x,y))>K(\pi(x,y))+2\log x$.

This argument can easily be generalized to other values of $c$ and $k$. $\Box$

Polynomial shifts generate information above the asymptotic sensitivity level
of Kolmogorov complexity. Note that $\epsilon_{r}(x,y)$ is still a computable
bijection:

$\forall(x,y)_{\in\mathbb{N}^{2}}\exists(u,v)_{\in\mathbb{N}^{2}}(\epsilon_{r}(u,v)=(x,y))$

$u^{2}\leq x<(u+1)^{2}$ $a=(u+1)^{2}-u^{2}$ $y=\lfloor\frac{v}{a}\rfloor$

This analysis holds for all values
$\Delta(\pi(\epsilon_{r}(x,y)))\in\mathbb{N}$ including the values that are
typical, i.e. incompressible.

###### Observation 8

An immediate consequence is the translation
$\epsilon_{r}(x,y)=(cx^{k+1}+(y\bmod{cx}),\lfloor\frac{y}{cx}\rfloor)$ must be
interpreted as a _function scheme_ , that produces a countable set of new
functions. One for each column $x=c$. Actually $x$ can be seen as an _index_
of the function that is used to compute $\epsilon_{r}(u,v)=(x,y)$.

##  5 From $\mathbb{N}^{2}$ to $\mathfrak{P}(\mathbb{N})$: semi-countable sets

In this paragraph I investigate information theories for the set of finite
sets of natural numbers. I wil show that this set is indeed semi-countable:
there is no intrinsic theory of measurement for the set. This means that there
is no objective answer to the question: how much information does a finite set
of natural numbers contain? A useful concept in this context is the notion of
_combinatorial number systems_ :

###### Definition 17

The function $\sigma_{k}:\mathbb{N}^{k}\rightarrow\mathbb{N}$ defines for each
element

$s=(s_{k},\dots,s_{2},s_{1})\in\mathbb{N}^{k}$

with the strict ordering $s_{k}>\dots s_{2}>s_{1}\geq 0$ its index in a
$k$-dimensional _combinatorial number system_ as:

$\sigma_{k}(s)={s_{k}\choose k}+\dots+{s_{2}\choose 2}+{s_{1}\choose 1}$ (44)

The function $\sigma_{k}$ defines for each set $s$ its index in the
lexicographic ordering of all sets of numbers with the same cardinality $k$.
The correspondence does not depend on the size $n$ of the set that the
$k$-combinations are taken from, so it can be interpreted as a map from
$\mathbb{N}$ to the $k$-combinations taken from $\mathbb{N}$. For singleton
sets we have: $\sigma_{1}(x)={x\choose 1}=x$, $x\geq 0$. For sets with
cardinality $2$ we have:

$\sigma_{2}((1,0))={1\choose 2}+{0\choose 1}=0\Leftrightarrow\\{1,0\\}$
$\sigma_{2}((2,0))={2\choose 2}+{0\choose 1}=1\Leftrightarrow\\{2,0\\}$
$\sigma_{2}((2,1))={2\choose 2}+{1\choose 1}=2\Leftrightarrow\\{2,1\\}$
$\sigma_{2}((3,0))={3\choose 2}+{0\choose 1}=3\Leftrightarrow\\{3,0\\}$
$\dots$

We can use the notion of combinatorial number systems to prove the following
result:

###### Theorem 5.1

There is a bijection $\phi:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}^{2}$
that can be computed efficiently.

Proof: Let $S_{k}$ be the subset of all elements
$s\in\mathfrak{P}(\mathbb{N})$ with cardinality $|s|=k$. For each
$k\in\mathbb{N}$ by definition 17 the set $S_{k}$ is described by a
combinatorial number system of degree $k$. The function
$\sigma_{k}:\mathbb{N}^{k}\rightarrow\mathbb{N}$ defines for each element
$s=(s_{k},\dots,s_{2},s_{1})\in\mathbb{N}^{k}$, with the strict ordering
$s_{k}>\dots s_{2}>s_{1}\geq 0$, its index in a $k$-dimensional combinatorial
number system. By definition 17 the correspondence is a polynomial time
computable bijection. Now define
$\phi_{car}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}^{2}$ as:

$\phi_{car}(s)=((|s|-1),\sigma_{|s|}(s))$ (45)

We use the symbol $||$ to refer to the cardinality operation. Note that both
$\pi$ and $\sigma$ are computable bijections. When we have the set $s$ we can
compute its cardinality $|s|$ in linear time and compute $\sigma_{|s|}(s)$
from $s$ in polynomial time. $\Box$

The construction of the proof of theorem 5.1 separates the set
$\mathfrak{P}(\mathbb{N})$ in an infinite number of infinite countable
partitions ordered in two dimensions: in the columns we find elements with the
same cardinality, in the rows we have the elements with the same index. An
elaborate example of the computation both ways is given in the appendix in
paragraph 12. An example of the mapping can be seen in figure 24.

Figure 24: An initial segment of the set $\mathfrak{P}(\mathbb{N})-\emptyset$
projected on the plane. It can be interpreted as an infinite planar
representation of nested powersets indicated by shaded areas for the sets
$\\{1,0\\}$, $\\{2,1,0\\}$, $\\{3,2,1,0\\}$ and $\\{4,3,2,1,0\\}$.

Theorem 5.1 not only gives us a proof of the countability of
$\mathfrak{P}(\mathbb{N})$, but we now also have an efficient theory of
information measurement:

$\forall(s\in\mathfrak{P}(\mathbb{N}))I(s)=\log(\pi(\phi_{car}(s)))$ (46)

The bijection $\phi_{car}$ has interesting mathematical properties:

  * •

Note that $\emptyset$ is not represented in the plane.

  * •

On the line $x=0$ we find sets of the form $\\{0,1,\dots,k\\}$ in column $k$.

  * •

On the line $y=0$ we find the singletons containing the natural numbers.

  * •

In column $k$ we find sets of cardinality $k+1$ ordered lexicografically.

  * •

The first $n\choose k$ sets in column $k-1$ are exactly the subsets of
cardinality $k$ of the set on location $(0,n)$.

  * •

For the set on location $(0,k)$ we find the $2^{k}-1$ elements of the set
$\mathcal{P}(\\{0,1,2,\dots,k\\})-\emptyset$ in the columns $(0,x)$ with
$x<k$. The length of the highlighted columns is given by the Pascal triangle
at row $k$: ${k\choose 1},{k\choose 2},\dots k\choose k$ again with omission
of the empty set.

  * •

Note that ${k\choose 1}+{k\choose 2}+\dots+{k\choose k}=2^{k}-1$, which
coincides with a powerset of a set with $k$ elements minus the empty set
$\emptyset$.

###  5.1 The binary number bijection $\phi_{bin}$.

We first study the effect of the power sum operation. The power sum operation
defines a bijection between $\mathbb{N}$ and $\mathfrak{P}(\mathbb{N})$. In
fact this bijection is well-known since it is the basis for our binary number
system.

###### Lemma 11

The function $\Upsilon:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}$ with
$\Upsilon(x)=\Sigma_{i\in X}2^{i}$ defines a two-way efficiently computable
bijection.

Proof: Suppose $\Upsilon(s)=n$ where $s=\\{s_{1},s_{2},\dots s_{k}\\}$ is a
set of natural numbers and $n$ an natural number. We have:

$\Upsilon(s)=\Sigma_{i\in s}2^{i}=2^{s_{1}}+2^{s_{2}}+\dots+2^{s_{k}}=n$

This function is easy to compute. Observe that the natural number $n$ can be
written as a unique binary number which can be computed efficiently:

$n=2^{a_{1}}+2^{a_{2}}+\dots+2^{a_{m}}$

Since such a binary number is unique it is the case that

$\\{a_{1},a_{2},\dots,a_{m}\\}=\\{s_{1},s_{2},\dots,s_{k}\\}=s$

$\Box$

Figure 25: The values of taking the sum of the exponentials of the elements of
the sets in figure 24. If we take the empty set $\emptyset$ as representing
$0$ we get an endomorphism on $\mathbb{N}$. On the line $x=0$ we find powers
of two $2^{i}$. On the line $y=0$ we have $2^{i}-1$ and on the line $x=y$ we
have $2(2^{i}-1)-1$. Observe that the values in this bijection diverge
considerably from the ones found in figure 24.

An initial segment of the values of the function $\Upsilon$ is seen in figure
25. Observe that we have three sets:

  * •

The set of natural numbers: $\mathbb{N}$,

  * •

The two-dimensional plane $\mathbb{N}^{2}$ and

  * •

The class of all finite sets of natural numbers $\mathfrak{P}(\mathbb{N})$.

with three corresponding efficiently computable bijections:

  * •

The Cantor function $\pi:\mathbb{N}^{2}\rightarrow\mathbb{N}$,

  * •

The cardinality bijection
$\phi_{car}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}^{2}$, and

  * •

The power sum operation
$\Upsilon:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}$,

Together these bijections characterize the interconnectedness of the set of
numbers and the set of finite sets on the basis of the following endomorphism:

${\mathbb{N}}$${\mathbb{N}^{2}}$${\mathfrak{P}(\mathbb{N})}$${\mathbb{N}}$$\scriptstyle{\pi^{-1}}$$\scriptstyle{\phi_{car}^{-1}}$$\scriptstyle{\Upsilon}$
(47)

By definition the binary numbers define a second efficiciently computable
theory of information measurement:

$\forall(s\in\mathfrak{P}(\mathbb{N}))I(s)=\log(\Upsilon(s))$ (48)

We define the corresponding bijection:

$\phi_{bin}(s)=(\Upsilon(s),0)$ (49)

Metaphorically we could say that the power sum operation $\Upsilon$ pulls the
sets in $\mathfrak{P}(\mathbb{N})$ with exactly enough force to project each
cell in $\mathbb{N}^{2}$ to a unique location on the line $y=0$.

##  6 Dilations of $\mathfrak{P}(\mathbb{N})$ on $\mathbb{N}^{2}$

In this paragraph we will study dilation on $\phi_{car}$. We will investigate
the conditions under which these operation still lead to (efficiently)
computable bijections. Since the grid is discrete the effect of such elastic
translations is disruptive and involves discontinuous translations of cells
over various distances. The force that “pulls” the cells in the $y$-axis
direction will be an arithmetical operation on sets of numbers. There are four
dilations that are of special interest to us:

  * •

The cardinality dilation:
$\phi_{car}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}^{2}$

  * •

The sum dilation:
$\phi_{sum}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}^{2}$

  * •

The product dilation
$\phi_{prod}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}^{2}$

  * •

The binary number dilation
$\phi_{bin}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}^{2}$

Only the first is a real bijction. The other three are injections, although
the last one gives us a direct bijection to $\mathbb{N}$. We give an example.

###### Example 8

Consider the set $s=\\{1,4,6,8,10,11\\}$. The cardinality of this set is $6$
so in figure 24 it will be placed in column $5$. The row of this set is $811$,
the Cantor pairing function gives the index
$\pi(\phi_{car}(s))=\pi(5,811)=334147$ (see appendix 12). The operations of
interest on this set are:

  * •

Cardinality: $|\\{1,4,6,8,10,11\\}|=6$,

  * •

Lexicographic rank in the class of sets with cardinality $6$:
$\sigma_{6}(\\{1,4,6,8,10,11\\})=811$,

  * •

Cantor index: $\pi(\phi_{car}(s))=\pi((6-1),811)=334147$,

  * •

Sum: $\Sigma_{i\in s}i=1+4+6+8+10+11=40$

  * •

Product: $\Pi_{i\in s}i=1\times 4\times 6\times 8\times 10\times 11=21120$

  * •

Binary number: $\Upsilon(s)=\Sigma_{i\in
s}2^{i}=2^{1}+2^{4}+2^{6}+2^{8}+2^{10}+2^{11}=3410$

We can study the effect of arithmetical dilations of $\phi_{car}$ on the
plane. A dilation $\phi_{prod}$ will place the set $s$ in column $21120$, and
a dilation $\phi_{sum}$ will place it in column $40$. A dilation $\phi_{bin}$
will place the set $s$ in column $3410$ on the plane. Note also that the set
$s$ is typical: the binary representation of our example set is
$110101010010$. We have $12$ bits with $6$ ones. The three arithmetical
operations define injections in $\mathbb{N}^{2}$. Since the arithmetical
functions define, in comparison to cardinality, an information expansion
function in the direction of the $y$-axis, there will be a corresponding
“compression” force in the direction of the $x$-axis. Metaphorically speaking
one could say that the points are attracted to the line $y=0$ and want to stay
as close as possible to it.

###  6.1 A general theory of dilations for arithmetical functions

We define a general construction for the study of the information efficiency
of arithmetical functions on sets of numbers:

###### Definition 18

$\phi_{\zeta}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}$, a _injection
sorted on $\zeta$_, is a mapping of the form:

$\phi_{\zeta}(s)=\pi(\zeta(s),\theta_{\zeta(s)}(s))$ (50)

where $\pi$ is the Cantor function and:

  * •

$\zeta:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}$ is a _general
arithmetical function operating on finite sets of numbers_. It can be
interpreted as a type assignment function that assigns the elements of
$\mathfrak{P}(\mathbb{N})$ to a type (column, sort) represented as a natural
number.

  * •

$\theta_{k}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}$ is an index
function for each type $k$, that assigns an index to the set in column $k$.The
equation $\theta_{\zeta(s)}(s)=n$ should be read as: $s$ is the $n$-th set for
which $\zeta(s)=k$.

By theorem 5.1 we have that $\phi_{car}$ is efficiently countable. We can use
$\phi_{car}$ as a _calibration device_ to evaluate $\phi_{\zeta}$. If
$\phi_{\zeta}$ is a sorted injection the following mappings exists
$\phi_{car}^{-1}:\mathbb{N}\rightarrow\mathfrak{P}(\mathbb{N})$ and
$\phi_{\zeta}^{-1}:\mathbb{N}\rightarrow\mathfrak{P}(\mathbb{N})$ such that
$\phi_{car}^{-1}(\phi_{car}(x))$, $\phi_{\zeta}(\phi_{\zeta}^{-1}(x))$ are
identities in $\mathfrak{P}(\mathbb{N})$. Given this interconnectedness we can
always use $\phi_{car}$ to construct $\phi_{\zeta}$ algorithimically:

Algorithm 1 Compute the sorted index function $\theta_{\zeta(s)}(s)$ using
$\phi_{car}$.

1: $k\leftarrow 0$

2: $i\leftarrow 0$

3: while $k\leq\phi_{car}(s)$ do

4: if $\zeta(\phi_{car}^{-1}(k))=\zeta(s)$ then

5: $k\leftarrow k+1$

6: $i\leftarrow i+1$

7: else

8: $k\leftarrow k+1$

9: end if

10: end while

11: $\theta_{\zeta(s)}(s)=i$

###### Theorem 6.1

If the function $\zeta$ exists and can be computed in polynomial time then
sorted injections $\phi_{\zeta}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}$
of the form $\phi_{\zeta}(s)=\pi(\zeta(s),\theta_{\zeta(s)}(s))$ exist and can
be computed in time exponential to the representation of $s$.

Proof: We have to compute
$\phi_{\zeta}(s)=\pi(\zeta(s),\theta_{\zeta(s)}(s))$. The functions $\pi$ and
$\zeta$ can be computed in polynomial time. The function $\theta$ can be
computed using $\phi_{car}$ with algorithm 1. This algorithm runs in time
exponential in the representation of $k$ which is the index of the set $s$:
$\phi_{car}^{-1}(k)=s$. $\Box$

Observe that $\phi_{\zeta}$ ca be interpreted as an operationalization of the
axiom of choice:

######  Definition 19 (Axiom of Choice)

For every indexed family $(S_{i})_{i\in I}$ of nonempty sets there exists an
indexed family $(x_{i})_{i\in I}$ of elements such that $x_{i}\in S_{i}$ for
every $i\in I$.

Here $\zeta:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}$ indexes the
elements of $\mathfrak{P}(\mathbb{N})$ and
$\theta_{k}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}$ selects the
elements of the indexed classes. Dilation theory allows us to study the
effects of the spectrum of choices on $\mathfrak{P}(\mathbb{N})$ associated
with elementary recursive functions. Metaphorically one would envisage the
spectrum in terms of a rubber sheet lying over the space $\mathbb{N}^{2}$. We
measure the information efficiency resulting from the translations. When one
starts to pull the sheet over the $x$-axis it starts to shrink over the
$y$-axis. As long as one pulls with linear force the notion of a smooth
information efficiency associated with a computable bijection over the space
is conserved. When we pull with monotonely increasing force of a polynomial
function, a computable bijection is still available, but the space starts to
fluctuate with increasing discontinuities and the tension in the limit is
infinite. When one pulls superpolynomially, using functions on sets of
numbers, the rubber sheet starts to disintegrate at finite dimensions and
stops to be a computable bijection. It becomes an injection that is only
occasionally locally computable on a point to point basis, although every
stage of the translation can be reconstructed from the origin in exponential
time. When we pull the sheet super exponentially the shift is so big that the
place of the image on the x-axis starts to carry information about the origin
of all sets for which the image is on the line $x=c$. This is the case for
primes and square numbers that have only two generating sets. When all points
in the space $\mathbb{N}^{2}$ are mapped densely to the line $y=0$ the
translation becomes the trivial inverse of the Cantor packing function, which
is by definition information efficient again. This is the case for
$\phi_{bin}$.

###  6.2 A formal analysis of the object $\phi_{sum}$

Define $\Sigma s=\Sigma_{s_{i}\in s}s_{i}$ as the addition function for sets.
Suppose $s$ is the set associated with the index $(x,y)$ in $\mathbb{N}^{2}$
and $\pi(x,y)$ in $\mathbb{N}$. We have the sum function for sets:
$\Sigma:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}$. The function
$\epsilon_{\Sigma}:\mathbb{N}^{2}\rightarrow\mathbb{N}^{2}$ defines an
_dilation_ by a function $\Sigma$ of the form:

$\epsilon_{\Sigma}(x,y)=(\Sigma s,\theta_{\Sigma s}(s))$ (51)

Here $\theta_{\Sigma}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}$ is the
function that enumerates sets with the same sum. We have the functions:
$\pi:\mathbb{N}^{2}\rightarrow\mathbb{N}$ and
$\phi_{car}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}$. We define an
injection $\phi_{sum}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}$ sorted on
sum:

$\phi_{car}(\epsilon_{\Sigma}(s))=\phi_{sum}(s)=\pi(\Sigma s,\theta_{\Sigma
s}(s))$ (52)

Observe that the shift is an injection. For every natural number there is only
a finite number of sets that add up to this number. The injection is dense
when sampled over the counter diagonal.

There are for each set $s_{k}=\\{1,2,\dots,k\\}$, with $\Sigma_{x\in
s_{k}}x=u$, according to equation 70 exactly $B_{k}$ partitions that add up to
$n$. This means that there is a super exponential number of sets that add up
to $u$ which gives, when sampled over the counterdiagonal, using $\pi$, a
density of $1$ in the limit. This fact is remarkable, at every line $x=c$ we
compress an infinite set to a finite one, but the density of the resulting
index stays close to $x-\log x$.

Figure 26: Schematic overview of the translation $\phi_{sum}$ generated by
$\phi_{car}$ at a finite moment $t$.

In figure 26 we give a schematic overview of the translation $\phi_{sum}$
driven by the Cantor function for finite sets $\phi_{car}$ at a finite moment
$t$. The area $(o,a,b)$ is the set of points that have been “surveyed” by
$\phi_{car}$ up till now. The area below the red line illustrates the points
that have been generated by $\phi_{sum}$. The exponential function illustrated
by the line $(0,c,d)$ marks the empty area where $\phi_{sum}$ will never
generate images. Point $(a,0)$ is on line $y=0$. It codes the set
$\\{0,1,2,\dots a\\}$ with the image $a^{\prime}$ at $(\frac{1}{2}a(a-1),0)$.
Point $a-1^{\prime}$ is the image of $(a-1,0)$ at $(\frac{1}{2}(a-1)(a-2),0)$.
The gaussian distribution $e$ illustrates the density of the points around
$\frac{1}{2}a$ that corresponds to sets of numbers, generated by a random
selection of $\frac{1}{2}a$ elements from the set $\\{0,1,2,\dots a\\}$ that
will have an image in the neighborhood of
$(\frac{1}{2}(\frac{1}{2}a(\frac{1}{2}a-1)),0)$. Note that only a tiny
fragment of these sets has been surveyed by $\phi_{car}$. About al others we
have no information at time $t$.

Observe that figure 26 describes the situation of the computation of
$\phi_{sum}(s)$ at any finite moment in time and that the line $(a,b)$ is a
hard _information boundary_. At any moment in time $t$ the characterization of
the set $\phi_{sum}$ by any finite segment of $\mathbb{N}$ is fundamentally
incomplete. The images on the line $y=0$ form a discontinuous cloud of points.
There is an exponential amount of relevant computations that we have not seen
yet.

###  6.3 A formal analysis of the object $\phi_{prod}$

The information efficiency of multiplication is extensive. We do not lose
information when we multiply although we lose the structure of the generating
sets. This is an indication that $\phi_{prod}$ as a bijection is easier to
compute than $\phi_{sum}$. Define $\Pi s=\Pi_{s_{i}\in s}s_{i}$ as the
multiplication function for sets. We define an injection
$\phi_{prod}:\mathfrak{P}(\mathbb{N})\rightarrow\mathbb{N}$ sorted on product:

$\phi_{prod}(s)=\pi(\Pi s,\theta_{\Pi s}(s))$ (53)

Figure 27: Schematic overview of the translation $\phi_{prod}$ generated by
$\phi_{car}$ at a finite moment $t$.

Observe that this shift is also an injection. The complexity of $\phi_{prod}$
is fundamentally different from the complexity of $\phi_{sum}$. For every
natural number there is only a finite number of sets that multiply up to this
number. There are for each set $s_{k}=\\{1,2,\dots,k\\}$, with $\Pi_{x\in
s_{k}}x=k!$, according to equation 70 exactly $B_{k}$ partitions that multiply
up to $k!$. This gives a density of the counter diagonal that is approximately
logarithmic.

Since for every set $s$ the computation $\phi_{prod}(x)=n$ is different, the
number $\phi_{car}(s)=\pi(x)$ is an index of the computation. Consequently we
can only compute $\phi_{prod}^{-1}(n)=s$, if we already know $s$. This is
exactly the case for prime numbers, they code the information about their own
multiplicative history. Since we know that primality is in $P$ the object
$\phi_{prod}$ is a bijection that at least partly for certain columns $x=c$
can be computed in polynomial time both ways.

###  6.4 The axiom of choice at work: the divergence between
$\pi(\phi_{car}(s))$ and $\Upsilon(s)$.

Theorem 2.2 tells us that there is no intrinsice information theory for
$\mathfrak{P}(\mathbb{N})$ and consequently there is no valid concept of a
typical set in this domain. In this paragraph I show that different
representational choices for $\mathfrak{P}(\mathbb{N})$ lead to diverging
measurements of the information content of ‘typical’ sets. The discovery was
of vital importance in the definition of the notion of semi-countability,
although now we have the concept the material is only an illustration of the
theory.

Note that the values of the cardinality bijection and the power sum bijection
vary considerably in the example above. We have
$\pi(\phi_{car}(s))=334147\gg\Upsilon(s)=3410$. This is interesting, since
both operations define efficiently computable bijections to
$\mathfrak{P}(\mathbb{N})$ and consequently an endomorphism of $\mathbb{N}$.
This endomorphism is illustrated in figure 28 where the binary strings related
to the sets in figure 24 are depicted. We can draw iso-information lines that
mark borders between points with less and more information in the plots. The
iso-information line of $\pi(\phi_{car}(x))$ follows the counter diagonal of
the Cantor pairing function. The border that is associated with the length of
the strings that code $\Upsilon(x)$ follows a binomial distribution given by
the dashed line.

Figure 28: The binary strings corresponding to the sets in figure 24. The
solid line indicates the iso-information border associated with the Cantor
function that follows the counter diagonal. The dashed line indicates the iso-
information border associated with the strings: this follows the binomial
distribution and marks (in this case) the border between strings of length up
to 5 and strings that are longer.

Clearly visible in figure 28 is the fact that the information coded in strings
created vaults of more efficient representations in the landscape of sets of
numbers defined by $\phi_{car}$. A graphical overview of the difference
between the two bijections is given in figure 29.

Figure 29: A plot of the difference between the values generated by the
Cardinality Dilation (see figure 24) and the Power Sum bijection (see figure
25). The global difference between the two bijections is clearly visible. In
the middle of the plot there is a valley in which the Power Sum bijection
gives a more efficient coding of numbers. Around the valley are elevated parts
of the landscape where the Cardinality bijection is more efficient.

We now have two different representations of the set
$\mathfrak{P}(\mathbb{N})$, one as a bijection to $\mathbb{N}^{2}$ and one as
a bijection to $\mathbb{N}$. Via the Cantor pairing function we also have an
index for elements of $\mathfrak{P}(\mathbb{N})$ in $\mathbb{N}$. The set from
example 8 seems to be typical, yet the index values vary greatly in the two
representations: $334147$ versus $3410$.

We now investigate bijections for, what I call, _string-typical sets_ : sets
of numbers based on random characteristic vectors. We show that the planar
representation ordered on cardinality is inefficient for string-typical sets.

###### Lemma 12

$\phi_{car}$ is inefficient for typical sets. For a typical set $s$ with
$\Upsilon(s)=2^{n}$ we need at least $n-2\log n-5$ extra bits to represent
$\phi_{car}(s)$.

Proof: We assume a typical set $s=\\{s_{1},\dots,s_{k}\\}$ of numbers with
cardinality $k$ for which the largest element has size $n=2k$. Furthermore we
assume that the elements of $s$ are ordered on numeric value
$i<j\Leftrightarrow s_{i}>s_{j}$. Since we know that $s_{1}=2k$ and all other
elements of $s$ are smaller than $2k$ we have the following upper bound for
$\Upsilon(s)$:

$\Upsilon(s)=\Sigma_{i\in s}2^{i}=2^{2k}+2^{s_{2}}+\dots+2^{2k}<2^{2k+1}$ (54)

For the cardinalty bijection we can compute a lower bound for the
lexicographic index as:

$\sigma_{k}(s)={2k\choose k}+\dots+{s_{2}\choose 2}+{s_{1}\choose
1}>{2k\choose k}$ (55)

This gives the following lower bound for the Cantor index:

$\phi_{car}(s)=\pi({2k\choose k},2k):=\frac{1}{2}({2k\choose k}+2k)({2k\choose
k}+2k+1)+2k>\frac{1}{2}{2k\choose k}^{2}$ (56)

We have:

${2k\choose
k}=\frac{2^{2k}\Gamma(k+\frac{1}{2})}{\sqrt{\pi}\Gamma(k+1)}>\frac{2^{2k}\Gamma(k)}{\sqrt{\pi}\Gamma(k+1)}=\frac{2^{2k}}{\sqrt{\pi}k}$
(57)

Where $\Gamma(n)=(n-1)!$ is the gamma function. Combining equations 54, 56 and
57 we get:

$\frac{\phi_{car}(s)}{\Upsilon(s)}>\frac{\frac{1}{2}(\frac{2^{2k}}{\sqrt{\pi}k})^{2}}{2^{2k+1}}=\frac{2^{2k-1}}{4\pi
k^{2}}=\frac{2^{2k-3}}{\pi k^{2}}$ (58)

Which gives for a set with an $\Upsilon$ index of length $n=2k$ bits (given
equation 54), an overhead for the $\phi_{car}$ index of at least
$2k-3-\log_{2}\pi-2\log_{2}k>n-2\log_{2}n-5$ bits. $\Box$

We need almost twice as many bits to represent a typical set on the plane then
as a binary number. This effect is exponential, so it is invariant under
polynomially computable bijections of the plane. We make the following
observation:

###### Observation 9

This extreme behavior of string-typical sets is caused by a choice bias in
their definition, which leads to an extreme unbalance in their planar
coordinates in the cardinality bijection $\phi_{car}$. The phenomenon is
illustrated in example 1. Since a set of size $k$ has $2^{k}$ subsets, for
most sets the difference between their lexicographic index will be
exponentially bigger than their cardinality, pushing their planar
representation into edge regions of the plane in which planar representation
is inherently inefficient (see par. 4). This illustrates the fact that a
random selection of numbers from an initial segment of $\mathbb{N}$ under
uniform distribution does not lead to a valid notion of a typical set.

The divergence between $\phi_{car}$ and $\phi_{bin}$ brings us a step closer
to understanding conjecture 1 and the effects of theorem 2.2.

  1. 1.

The bijection $\phi_{bin}$ orders the set $\mathfrak{P}(\mathbb{N})$ on sums
of the exponential functions in the one-dimensional space $\mathbb{N}$.

  2. 2.

The bijection $\phi_{car}$ orders the set $\mathfrak{P}(\mathbb{N})$ on
cardinality in the two-dimensional space $\mathbb{N}^{2}$.

  3. 3.

The bijection given in equation 47 between the two sets is efficiently
computable but the information content of the data points that are connected
by the bijection varies considerably.

  4. 4.

The embedding is topologically incoherent. There is in $\phi_{car}$ no
neighborhood function that reflects the structure of $\phi_{bin}$. Sets with
the same sum are scattered over the space $\phi_{car}$.

  5. 5.

For string-typical sets the divergence can be estimated to be large, close to
twice as many bits. See theorem 12.

  6. 6.

This gives two different information theories for sets of numbers specified by
equations 46 and 48. In these two information theories the same set can have a
different information content.

$\Box$

A binary number has two, what one could call, “ontologies”; it is both a
_number_ in the world of $\phi_{bin}$ and a _set of numbers_ in the world
$\phi_{car}$. In the corresponding measurement theories the amount of
information in _the same object_ varies. Lists code information inherently
more efficient than isolated numbers, because they have a richer structure.
The bijection $\phi_{car}$ gives one embedding of $\mathbb{N}$ in
$\mathbb{N}^{2}$, the bijection $\phi_{bin}$ another. For some numbers the set
description is more effective, for some numbers it is the other way around.
Specifically for finite typical subsets the number description is more
effective.

$\phi_{bin}$ and $\phi_{car}$ are two information theories that mutually
expand and compress descriptive information in a topologically non-coherent
way. $\phi_{bin}$ is linear, or one-dimensional; $\phi_{car}$ is planar, or
two-dimensional. $\phi_{bin}$ can be embedded in $\phi_{car}$ via its
codification in terms of sets of numbers, but in this embedding the notion of
topological coherence is lost. The elements of $\phi_{bin}$ are distributed
over $\phi_{car}$ as a dense cloud of points, seemingly without any global
structure. From the $\phi_{bin}$ perspective the $\phi_{car}$ landscape looks
like a chaotical structure of expandable and compressible isolated data
points, and vice versa.

###  6.5 Fractal dilations

Equation 47 describes an endomorphism on the set of natural numbers. For
reasons of readibility I repeat it here:

${\mathbb{N}}$${\mathbb{N}^{2}}$${\mathfrak{P}(\mathbb{N})}$${\mathbb{N}}$$\scriptstyle{\pi^{-1}}$$\scriptstyle{\phi_{car}^{-1}}$$\scriptstyle{\Upsilon}$

Here $\Upsilon(x)=\Sigma_{i\in X}2^{i}$, with $i\in\mathbb{N}$ (see lemma 11).
The construction of the endomorphism ‘travels’ over the representation of the
plane, via a bijection $\phi_{car}^{-1}$ to $\mathfrak{P}(\mathbb{N})$ with
density $1$, to a bijection $\Upsilon$ to the set $\mathbb{N}$ with density
zero in the plane.

The transformation defines a _phase transition_ from a _planar_ to a
_numerical_ representation of information that in principle can be continued
in unbounded number of cycles, leading to ever increasing topological
distortions of the discreate plane. In this paragraph I investigate dilations
that are ‘close’ to $\Upsilon$ in terms of information efficiencty and show
that they lead to data sets with a fractal nature. Observe that $\Upsilon$ is
based on powers of two. Data sets ‘close’ the one generated by $\Upsilon$ are
base on _injured_ or _randomized_ natural numbers selected by the _intervals_
defined by powers of two. I define:

###### Definition 20

The function $rnd(2^{i})$ selects a random number from the interval
$[0,2^{i}]$ under uniform distribution.

###### Definition 21

A codebook _template_ 888The term “template” was suggested to me by Daan van
den Berg. is a finite or infinite totally ordered set of numbers. The
_canonical template_ is the infinite set of powers of two
$P=[2^{0},2^{1},\dots]$.

###### Definition 22

A _randomized Scale-free Codebook_ based on the canonical template is a
totally ordered set of unique numbers of the form $a_{i}=rnd(2^{i})$ with
$i\in\mathbb{N}$.

Figure 30: The densities of $\phi_{sum}$ dilations of various types of subsets
of $\mathbb{N}$ ordered by the information in the elements of the sets. The
gray line in the figure is based on a small scale-free randomized set that is
analyzed extensively in the appendix in paragraph 13.

Figure 30 gives an overview of the fractal landscape that emerges from this
analysis:

  * •

The blue line, $y=\log_{2}x$, gives the information in the canonical code book
$P=[2^{0},2^{1},\dots]$. The sum dilation of this set again generated the
totally ordered chain of natural numbers and thus has dimension $1$ in the
discrete plane.

  * •

Scale-free code books are self-similar to their own set of expected values:

$P^{\frac{1}{2}}=[\\{0,1\\},2^{0},2^{1}\dots]$

where we replace $2^{0}$ by zero or one and $2^{i}$ by $2^{i-1}$. The
resulting codebook has two representations for each number.

  * •

The scale-free structure of sum dilations of such codebooks is clear from the
fact that the codebook $P$ is _self-similar_ under multiplication with powers
of two.

  * •

For the sum diliation of any subset of $\mathbb{N}$ that stays asymptotically
above the $y=\log_{2}x$ line, the chain will be broken. The fractal dimension