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.

  • $\begingroup$ What do you mean exactly by "self similar at some point"? I don't quite understand this language, or your example. $\endgroup$ – john Nov 26 '16 at 21:52
  • $\begingroup$ i mean after some term defined by us as minimum to show similarity. thank you for the immediate(!!!!) reply $\endgroup$ – mehmet Nov 26 '16 at 21:54
  • $\begingroup$ @mehmet What do you mean by similarity? $\endgroup$ – leibnewtz Nov 26 '16 at 21:57
  • $\begingroup$ a mathematical sequence is self-similar when the same exactly sequence occurs, for example when taking every second term $\endgroup$ – mehmet Nov 26 '16 at 21:59
  • $\begingroup$ Thanks for trying to explain a bit more what you mean. Unfortunately, it's still not clear what you mean exactly by self-similarity - the explanation you have in the previous comment could mean a few different things. But perhaps something that should be mentioned sooner rather than later is that the sequence of digits in the decimal expansion of an irrational number (e.g. $\sqrt{2}$) will never start consecutively repeating a constant finite string of digits. So in that sense, it can't be self-similar. $\endgroup$ – john Nov 26 '16 at 22:08

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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.