Self-similarity in mathematical sequences

Question

Can any mathematical sequence be considered self-similar after some predefined number of terms similar to the initial sequence?

Such a function could be something crazy or simply every second term, exactly as in here: https://oeis.org/selfsimilar.html

We just don't know the function yet.. and how to find it if it's not polynomial. How could I find such a function? What A.I. method could help me on that or is already used.

Answer 1

So as john explained to me:

Ok. So how about this: suppose your infinite sequence is made up of digits 0-9. >Then for any length NN of a finite string, there can only be 10N10N >possibilities for what that string actually is. Since we can easily view an >infinite sequence as a concatenation of infinitely many strings of length NN, >the pigeonhole principle then tells us that some fixed length NN string occurs >infinitely often. Since you said this is the notion of self-similarity you had >in mind, this means all infinite sequences of digits 0-9 exhibit your kind of >self-similarity.

So pigeonhole principle allows my assumption that any infinite (decimal/0-9) sequence is selfsimilar, as long as it contains itself. is that right?

What are the methods to find the function which returns the indexes of the contained terms?

Heuristic methods? Artificial Intelligence?

Answer 2

I believe there are a couple of misconceptions, based on the website you refer to:

1. Let $X$ be a nonempty set. Then a (mathematical) sequence is a function $f:\Bbb{N}\to X$, where $\Bbb{N}=\{1,2,...,n,...\}$. Observe that this is to say that a sequence is simply an (indexed) list of objects. When $X:=\Bbb{Z}=\{...,-n,...,-1,0,1,...,n,...\}$, f is an integer sequence. The webpage you refer to contains nothing but integer sequences. Further, the title "Some Self-Similar Integer Sequences" does not mean that all integer sequences are self-similar (let alone all sequences). It precisely means some of them are.
2. In the webpage you refer to all the examples are given by defining the general term of the sequence, so that it is not the case that one gets to decide what a term is going to be after finite time. In fact, defining only finitely many terms of a sequence does not define the sequence at all.

---

You might want to have a look at the area called symbolic dynamics. Roughly speaking symbolic dynamics is concerned with the following:

Let $X$ be a finite nonempty set and $X^\Bbb{N}$ be the set of all sequences that can be written using the elements of $X$. For instance $\{0,1\}^\Bbb{N}$ is the set of all binary sequences. Define

\begin{align} \sigma:&X^\Bbb{N}\to X^\Bbb{N}\\ &\{x_0,x_1,...,x_n,...\}_n\mapsto \{x_1,x_2,...,x_{n+1},...\}_n. \end{align}

$\sigma$ is the Bernoulli shift on $X$. Observe that $\sigma$ takes a sequence and erases its first term, so that the result is still a sequence. For instance in our example $\{0,1\}^\Bbb{N}$,

$$\sigma: \{0,1,0,1,...,0,1,...\}_n\mapsto \{1,0,1,0,...,1,0,...\}_n$$

A sequence $\{x_0,x_1,...,x_n,...\}_n \in X^\Bbb{N}$ is a periodic point of $\sigma$ if

$$\exists k\in\Bbb{N}: \sigma^k(\{x_0,x_1,...,x_n,...\}_n)=\{x_0,x_1,...,x_n,...\}_n.$$

I'll leave it to you to argue that a sequence is self-similar iff it is a periodic point of $\sigma$.

---

I don't know much about the computer scientific aspects of symbolic dynamics, but I wouldn't be surprised if there were numerical/computational theories developed by/for/with it. Also note that the requirement that $X$ be finite is not necessary to define the shift nor a periodic point of it.