Self-similarity in algebra, dynamics and algorithmics – AutoSim

A common language, that of \emph{finite state automata}, is put
forward to bring together these fields and provide them with unifying,
systematic tools with which to approach their fundamental questions.

While self-similarity in geometry and physics has been studied since
quite some time, its development in algebra is new. Geometric group
theory provides links between geometric and algebraic intuitions. In
it, self-similarity is interpreted as the notion of a group containing
permuted copies of itself as subgroups. It has already proven the
existence of groups with intermediate growth (answering a famous
problem by Milnor), of non-uniform exponential growth (answering
another famous problem by Gromov), with striking spectral properties
(solving a conjecture attributed to Atiyah), \dots

However, this is only the beginning! By extending the notion of
self-similar group, and its interpretation by finite state automata, a
larger class of groups is obtained which will provide answers to
more fundamental questions in group theory.

Even more recently, strong links have emerged between dynamical
systems and self-similar group theory. These links have by far not
been sufficiently exploited; they yield powerful invariants to
describe complex dynamical systems, and means to reconstruct them
\emph{ab initio} out of algebraic data.

This proposal propounds the use of group theory, and in particular
self-similar groups and automata, in order to explore dynamical
systems, decompose them canonically into elementary pieces, recombine
them, and, most importantly, provide a global viewpoint, based on
automata, of the parameter space of a whole family of dynamical
systems.

All these question raise fundamental complexity problems: is this
object computable? How should it be described? How efficient is that
description? It is a fundamental issue, to be able of performing
finite calculations on infinite objects. Finite state automata are
particularly simple computational devices, yet are powerful enough to
encode complicated groups and dynamical systems.

The algorithms designed to solve these tasks, furthermore, are of
great practical utility in experimenting with new objects. The
to-and-fro between computer simulation and experimentation, software
development and purely theoretical research benefits, in the end, to
all three.

Already three articles written, 2 accepted

The proposed research activity gravitates around a simple idea, that of "self-similarity", and all its avatars in geometry, algebra, dynamics and theoretical computer science.

It propounds the use of tools from algebra and theoretical computer science to answer questions and provide illuminating structure in geometric and dynamical contexts; and, conversely, to borrow methods, ideas and constructions from these areas so as to enrich algebraic objects.

Self-similarity is a powerful concept: the idea that an object can be described "recursively" as being built of scaled-down copies of itself. This self-reference leads to elementary constructions of objects with striking properties. A common language, that of "finite state automata", is put forward to bring together these fields and provide them with unifying, systematic tools with which to approach their fundamental questions.

While self-similarity in geometry and physics has been studied since quite some time, its development in algebra is new. Geometric group theory provides links between geometric and algebraic intuitions. In it, self-similarity is interpreted as the notion of a group containing permuted copies of itself as subgroups. It has already proven the existence of groups with intermediate growth (answering a famous problem by Milnor), of non-uniform exponential growth (answering another famous problem by Gromov), with striking spectral properties (solving a conjecture attributed to Atiyah), ...

However, this is only the beginning! By extending the notion of self-similar group, and its interpretation by finite state automata, a larger class of groups is obtained which will provide answers to more fundamental questions in group theory.

Even more recently, strong links have emerged between dynamical systems and self-similar group theory. These links have by far not been sufficiently exploited; they yield powerful invariants to describe complex dynamical systems, and means to reconstruct them ab initio out of algebraic data.

This proposal propounds the use of group theory, and in particular self-similar groups and automata, in order to explore dynamical systems, decompose them canonically into elementary pieces, recombine them, and, most importantly, provide a global viewpoint, based on automata, of the parameter space of a whole family of dynamical systems.

All these question raise fundamental complexity problems: is this object computable? How should it be described? How efficient is that description? It is a fundamental issue, to be able of performing finite calculations on infinite objects. Finite state automata are particularly simple computational devices, yet are powerful enough to encode complicated groups and dynamical systems.

The algorithms designed to solve these tasks, furthermore, are of great practical utility in experimenting with new objects. The to-and-fro between computer simulation and experimentation, software development and purely theoretical research benefits, in the end, to all three.