Self-similar algebras in the framework of A New Kind of Science
Dedicated to Prof. Said Sidki
Author: José Manuel Rodríguez Caballero (University of Tartu)
Abstract. I present some examples of the simple and complex structures emerging from self-similar algebras. I establish a speculative connection between the Wolfram model and Leibniz's monads. I conjecture that the evolution of the universe (and multiverse) converges to a self-similar structure.

Self-similar algebras

General definition

Let A be an algebra. A self-similar algebra is (A, ϕ, d), where d is a positive integer and ϕ is a homomorphism ϕ: A ⟶
Mat
d
(A) from A to the algebra of d×d matrices with entries in A.

Free algebras

Consider a fixed finite alphabet Σ, for example Σ = {"1", "2"}, Σ = {"5"}, Σ = {"x", "y", "z"}. Let Σ* be the free monoid generated by Σ. We denote C(Σ*) the free algebra generated by Σ* over the complex numbers.
The product of two matrices with entries on C(Σ*) is given by the following function, where the matrix product is given by the concatenation of words.
In[]:=
SDot[A_,B_]:=Table[Table[Total[Table[If[A[[i,k]]==0||B[[k,j]]==0,0,A[[i,k]]<>B[[k,j]]],{k,First[Dimensions[B]]}]],{j,Last[Dimensions[A]]}],{i,First[Dimensions[A]]}]
Example 1.
In[]:=
{{"a","b"},{"c","d"}}//MatrixForm​​{{"p","q"},{"r","s"}}//MatrixForm​​SDot[{{"a","b"},{"c","d"}},{{"p","q"},{"r","s"}}]//MatrixForm
Out[]//MatrixForm=
a
b
c
d
Out[]//MatrixForm=

p
q
r
s

Out[]//MatrixForm=
ap+br
aq+bs
cp+dr
cq+ds
Example 2.
In[]:=
Table[Table["a"<>ToString[i]<>ToString[j],{j,2}],{i,3}]//MatrixForm​​Table[Table["b"<>ToString[i]<>ToString[j],{j,3}],{i,2}]//MatrixForm​​SDot[Table[Table["a"<>ToString[i]<>ToString[j],{j,2}],{i,3}],Table[Table["b"<>ToString[i]<>ToString[j],{j,3}],{i,2}]]//MatrixForm
Out[]//MatrixForm=
a11
a12
a21
a22
a31
a32
Out[]//MatrixForm=
b11
b12
b13
b21
b22
b23
Out[]//MatrixForm=
a11b11+a12b21
a11b12+a12b22
a21b11+a22b21
a21b12+a22b22
a31b11+a32b21
a31b12+a32b22

Iterations of 2×2 matrices

We will focus on the case of 2×2 matrices, i.e., d = 2.
The homomorphism ϕ: A ⟶
Mat
d
(A), that in this case will be called Unfold is defined so that to any word s over the alphabet {"X", "Y"}, we associate a 2×2 matrix Unfold[s]
In[]:=
CharacterToMatrix[s_,X_,Y_]:=Switch[s,"X",X,"Y",Y,"1",{{"1",0},{0,"1"}},_,$Aborted];
In[]:=
Unfold[s_,X_,Y_]:=If[s=="",{{"",0},{0,""}},SDot[CharacterToMatrix[StringTake[s,1],X,Y],Unfold[StringTake[s,{2,-1}],X,Y]]]
We define the self-iterations as
In[]:=
Self[A_,X_,Y_]:=ArrayFlatten[Function[r,If[#==0,{{0,0},{0,0}},Unfold[#,X,Y]]&/@r]/@A]
In[]:=
Self[A_,X_,Y_,n_]:=If[n==1,A,Self[Self[A,X,Y],X,Y,n-1]]

Anti-run-length encoding

The anti-run-length encoding AntiRLE[w, s, a, b] of a word w over the alphabet {a, b}, beginning by s is the unique word beginning by s whose run-length encoding is w.
In[]:=
AntiRLE[w_,s_,a_,b_]:=If[w=="","",​​If[StringTake[w,1]==a,​​s<>AntiRLE[StringTake[w,{2,-1}],If[s==a,b,a],a,b],​​StringJoin[Table[s,{ToExpression[b]}]]<>AntiRLE[StringTake[w,{2,-1}],If[s==a,b,a],a,b]​​]];

Miscellaneous

Given a matrix M having strings and 0s as entries, ToOne[M] substitutes any nonzero entry in M by 1.
In[]:=
ToOne[M_]:=Function[r,If[#==0,0,1]&/@r]/@M
NonZero[M] outputs the set of coordinates of nonzero entries of M.
In[]:=
NonZero[M_]:=Select[Tuples[Range[First[Dimensions[M]]],2],M[[First[#],Last[#]]]≠0&]

Sidki's monomial algebra

Some iterations

Sidki[Sidki2009] introduced a self-similar associative algebra on two generators X and Y satisfying the following self-similarity structure
In[]:=
X={{0,"X"},{0,"Y"}};​​Y={{0,0},{"1",0}};​​MatrixForm/@{X,Y}
Out[]=

0
X
0
Y
,
0
0
1
0

In[]:=
Self[Y,X,Y,2]//MatrixForm
Out[]//MatrixForm=
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
In[]:=
Self[Y,X,Y,3]//MatrixForm
Out[]//MatrixForm=
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
The unfolding of Y is easy to guess
In[]:=
Self[Y,X,Y,4]//MatrixForm
Out[]//MatrixForm=
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
The unfolding of X is more interesting
In[]:=
Self[X,X,Y,8]//MatrixPlot
Out[]=

Zigzag evolution

Nonzero entries during the iterations of X.

Fibonacci numbers

Characteristic polynomial of the sum ToOne[Self[X,X,Y,i]] + ToOne[Self[Y,X,Y,i]]
Notice the role of Fibonacci numbers in these polynomials

MonadDyad["X", "Y", "", ""]

Monad-Dyad pairs

Given the strings p, q, r and s over the alphabet Σ = {"X", "Y"}, the MonadDyad[p,q,r,s] is the pair of matrices given by

Some iterations

Consider the monad-dyad pair
Let's see the iterations of the unfolding of X

Zigzag evolution

Nonzero entries during the iterations of X.

Thue-Morse sequence

In Chapter 12 (The Principle of Computational Equivalence), Section 10 (Intelligence in the Universe) of A New Kind of Science, we find the minimal cellular automata for generating the Thue-Morse sequence as the column in the middle.
Link: https://www.wolframscience.com/nks/notes-12-10--minimal-cellular-automata-for-sequences/
Given the Thue-Morse sequence (identification of 0 and 1 with X and Y respectively)
One nonzero entries of the unfolding of TM is a prefix of this sequence and the other nonzero entry is the same prefix with the letters X and Y interchanged.
Indeed,

Chebyshev Polynomial of the First Kind

In Chapter 10 (Processes of Perception and Analysis), Section 11 (Traditional Mathematics and Mathematical Formulas), note "[Reduced formulas in] continuous systems", we find an expression involving the Chebyshev Polynomials of the first kind indexed by powers of 2,
that is the closed formula the sequence of iterations x  4 x (1-x).
Link: https://www.wolframscience.com/nks/notes-10-11--reduced-formulas-in-continuous-systems/
We will show that the characteristic polynomial of
(ToOne[Self[X,X,Y,n]] + ToOne[Self[Y,X,Y,n]])/2
is a product of Chebyshev Polynomial of the First Kind (as a function of q) indexed by powers of 2, times q^2 - 1. For example,
Let's check

MonadDyad["X", "Y", "XXX", "YYY"]

Some iterations

Consider the monad-dyad pair
Let's see the iterations of the unfolding of X
Remark. All these matrices are all anti-diagonal.

Characteristic polynomial

The characteristic polynomials of the sum
are trivial to guess

Colored tree

Non-zero entries of the sequence of matrices generated by X (3 iterations)
can be represented as a tree of run-length encoding (the length of the word mod 3 is represented by different colors)
Remark 1. All the strings in this tree are of odd length. Also, they are palindrome.
Let's take 9 iterations and distinguish the vertices with colors corresponding to the length of the strings mod 3.
Question. Is the distribution of the colors of an infinite binary tree computationally reducible?
Recall of the definition. Computations that cannot be sped up by means of any shortcut are called computationally irreducible.​
​Rowland, Todd. "Computational Irreducibility." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/ComputationalIrreducibility.html

MonadDyad["X", "Y", "XX", "YY"]

Some iterations

Consider the monad-dyad pair
From the monad
evolved the dyad
and from it all the natural numbers
but everything is already folded in the monad (notice that the following matrix contains the previous matrices)

Characteristic polynomial

The characteristic polynomials of the sum
are extremely hard to guess.
Conjecture. The computation of the characteristic polynomials of ToOne[Self[X,X,Y,n]] + ToOne[Self[Y,X,Y,n]] as a function of n is computationally irreducible.

Zigzag evolution

Nonzero entries during the iterations of X.
Nonzero entries during the iterations of Y.

Connection with Kolakoski sequence

Michel Dekking characterized the Kolakoski sequence (A000002 in OEIS) as the unique infinite fixed point of the 2-block substitution (a 2-block substitution beta maps a word w(1)...w(2n) to the word beta(w(1)w(2))...beta(w(2n-1)w(2n)). If the word has odd length, then the last letter is ignored)
Consider the n-th iteration of Dekking
The sequence consisting of the nonzero entry of the first column of each unfolding of the dyad Y converges to the Kolakoski sequence, when X and Y are identified with 1 and 2 respectively.
For example
In a similar way as with Thue-Morse sequence, the Kolakoski sequence is connected with the unfolding of X
One nonzero entries of the unfolding of Kol is a contain Kol as prefix and the other nonzero entry is the same prefix with the letters X and Y interchanged.
Indeed,

Colored tree

Non-zero entries of the sequence of matrices generated by X (5 iterations)
can be represented as a tree of run-length encoding (the length of the word mod 3 is represented by different colors)
​
Let's take 9 iterations and distinguish the vertices with colors corresponding to the parity of the length of the strings
Question. Is the distribution of the colors of this last tree computationally reducible?

Leibniz's monad revisited

Trigger Warning: This section is highly speculative.

Turtles all the way down

In pages 80 of Leibniz's La Monadologie (éd. Bertrand, 1886), we find the following thought illustrating the concept of monad:
"Each piece of matter can be thought of as a garden full of plants and a pond full of fish. But each branch of the plant, each member of the animal, each drop of bodily fluid is also a garden or a pond."
Therefore, a Leibniz's monad is self-similar.
Reference: https://fr.wikisource.org/wiki/Page:Leibniz_-_La_Monadologie,_%C3%A9d._Bertrand,_1886.djvu/81

Polymones

According to G. Deleuze [Deleuze2014], a Leibniz's monad is a fold of space, movement and time. This concept may sound attractive for the Wolfram Physics Project.
Nevertheless, it is still an open problem to find the right definition of Leibniz's monads in the framework of A New Kind of Science.
Indeed, on May 14, 2013, S. Wolfram [Wolfram2013] wrote:
"[...] in the prehistory of my work on A New Kind of Science, when I first started formulating and studying one-dimensional cellular automata in 1981, I considered naming them “polymones” [in reference to Leibniz's monads]"
In note 6.6 of A New Kind of Science [Wolfram2002], there is a mention of self-similarity in additive cellular automaton rules, e.g., rule 90​
​link: https://www.wolframscience.com/nks/notes-6-6--self-similarity-of-additive-cellular-automaton-rules/

Artificial vs Natural

In pages 79 of Leibniz's La Monadologie (éd. Bertrand, 1886), we find the following thought concerning the distinction between artificial and natural systems:
"[...] a Machine, made by the art of human, is not Machine in all of its parts. [...] But the machines of nature, that is, living bodies are still machines in their smallest parts, to infinity. This is what makes the difference between Nature and Art, that is to say between Divine art and ours [...]"
In other words, for Leibniz, something is natural if and only if it is turtles all the way down.
Notice that if something is made of atoms (in the etiological sense of non-divisible), then it is artificial according to Leibniz.
Leibniz would recognize rule 90 as artificial, because its self-similarity is not infinite. Indeed, in iteration 2021 we already see some degeneration in the self-similar structure of rule 90.
Reference: https://fr.wikisource.org/wiki/Page:Leibniz_-_La_Monadologie,_%C3%A9d._Bertrand,_1886.djvu/80

Eternity

In the Wolfram Physics Project, there are atoms of space, whereas Leibniz's principle of continuity ("nature does not jump") is synechistic (a conception of space, time, matter, and other components of reality as continuous).
Nevertheless, there is a possible reconciliation between these two worldviews by considering that the synechistic universe postulated by Leibniz is the set of accumulation points of the multiway evolution of an atomistic universe described by the Wolfram model.
If a synechistic universe is self-similar, it makes sense to call it Leibniz's monad.
In the language of dynamical systems: A Leibniz's monad — according to this interpretation — is an attractor of the multiway evolution of a hypergraph.
Analogy: A Leibniz's monad is to its Wolfram model as an irrational number is to its sequence of approximations by rational numbers.
Consider the rule
acting on the initial condition
we see that the single-way evolution of this atomistic universe converges to a synechistic universe known as Sierpiński triangle
Here is an approximation of the Sierpiński triangle (Leibnitz monad of this Wolfram model)
Causal graph (spacetime structure of this Wolfram model)
Multiway system (quantum structure of this Wolfram Model)

Indiscernibles

Assuming that nature is described by a Wolfram model that converges to a Leibniz monad. The following question may be meaningless:
What is the size of space atoms with respect to us?
Indeed, there may be infinitely many positions in the multiway evolution of the hypergraph that will produce a copy of us asking the same question, but our relative size with respect to space atoms could be different in each copy. If we cannot distinguish in which of these copies are we, then applying Leibniz's identity of indiscernibles, our reality is not just a position in the multiway evolution but a class of such positions.
Of course, there may be some theorem guaranteeing that each class contains exactly one representative, in the same way that there are cosmological models preventing the existence of Boltzmann brains. If this is the case, this question will be well-defined.

Open Problem

To extend Wolfram's definition of particle to the case of a sequence of hypergraphs converging to a Leibniz’s monad.

References

[AhmedCaballero2019] Ahmed, Tanbir, and José Manuel Rodriguez Caballero. "A family of doubly stochastic matrices involving Chebyshev polynomials." Algebra and Discrete Mathematics 27.2 (2019). http://admjournal.luguniv.edu.ua/index.php/adm/article/view/557
[Bartholdi2015] Bartholdi, Laurent. "Self-similar Lie algebras." Journal of the European Mathematical Society 17.12 (2015): 3113-3151.
[Bartholdi2020] Bartholdi, Laurent, José Manuel Rodríguez Caballero, and Ahmed Tanbir. "The Thue-Morse substitutions and self-similar groups and algebras." arXiv preprint arXiv:2005.05126 (2020).
[Dekking1980] F. M. Dekking, Regularity and irregularity of sequences generated by automata, Seminar on Number Theory, 1979-1980 (Talence, 1979-1980), Exp. No. 9, 10 pp., Univ. Bordeaux I, Talence, 1980.
[Dekking1981] F. M. Dekking, On the structure of self-generating sequences, Seminar on Number Theory, 1980-1981 (Talence, 1980-1981), Exp. No. 31, 6 pp., Univ. Bordeaux I, Talence, 1981. Math. Rev. 83e:10075.
[Dekking1995] F. M. Dekking, What Is the Long Range Order in the Kolakoski Sequence?, Report 95-100, Technische Universiteit Delft, 1995.
[Deleuze2014] Deleuze, Gilles. Le pli. Leibniz et le baroque. Minuit, 2014.
[FutornyKochloukovaSidki2019 ] Futorny, Vyacheslav, Dessislava H. Kochloukova, and Said N. Sidki. "On self-similar Lie algebras and virtual endomorphisms." Mathematische Zeitschrift 292.3-4 (2019): 1123-1156.
[GrigorchukKravchenko2014] Grigorchuk, Rostislav, and Rostyslav Kravchenko. "On the lattice of subgroups of the lamplighter group." International Journal of Algebra and Computation 24.06 (2014): 837-877.
[HarlowShenkerStanfordSusskind2011] Harlow D, Shenker S, Stanford D, Susskind L. Eternal symmetree. arXiv preprint arXiv:1110.0496. 2011 Oct 3. https://arxiv.org/abs/1110.0496
[Oldenburger1939] Oldenburger, Rufus. "Exponent trajectories in symbolic dynamics." Transactions of the American Mathematical Society 46.3 (1939): 453-466.
[PetrogradskyShestakov2013] Petrogradsky, V. M., and I. P. Shestakov. "Self-similar associative algebras." Journal of Algebra 390 (2013): 100-125.
[MatildeTedeschi2014] Marcolli, Matilde, and Nicolas Tedeschi. "Multifractals, Mumford curves and eternal inflation." P-Adic Numbers, Ultrametric Analysis, and Applications 6.2 (2014): 135-154.
[Nekrashevych2005] Nekrashevych, Volodymyr. Self-similar groups. No. 117. American Mathematical Soc., 2005.
[Nekrashevych2007] Nekrashevych, Volodymyr. "Self-similar groups and their geometry." São Paulo Journal of Mathematical Sciences 1.1 (2007): 41-95.
[Nekrashevych2008] Nekrashevych, Volodymyr. "Symbolic dynamics and self-similar groups." preprint (2008).
[Sidki2009] Sidki, Said N. "Functionally recursive rings of matrices—Two examples." Journal of Algebra 322.12 (2009): 4408-4429.
[Wolfram2002] Wolfram, Stephen. A New Kind of Science. Vol. 5. Champaign, IL: Wolfram media, 2002.
[Wolfram2013] Dropping In on Gottfried Leibniz—Stephen Wolfram Writings. https://writings.stephenwolfram.com/2013/05/dropping-in-on-gottfried-leibniz/
[Wolfram2020] S. Wolfram, “A Class of Models with the Potential to Represent Fundamental Physics,” Complex Systems, 29(2), 2020 pp. 107–536.​
​https://doi.org/10.25088/ComplexSystems.29.2.107