# Algorithm to tell if an infinite sequence is random or not?

## Background

I recently came up with an algorithm which creates patterns.

Consider the famous sequence of the primes. They have considerable amount of "structure" but no "obvious pattern". I will illustrate "row math" making a pattern emerge with the example of primes:

## Row math

$$2,3,5,7,11,13,17,19,23,\dots$$

Now we will take the modulus/absolute difference of every element with its adjacent neighbor. $$2,3,5,7,11,13,17,19,\dots$$ $$1,2,2,4,2,4,2,\dots$$

Now we will take the difference (not the absolute difference) of the $2$'nd row with the first:

$$2,3,5,7,11,13,17,19,\dots$$ $$1,2,2,4,2,4,2,\dots$$ $$1,1,3,3,9,9,15,\dots$$

Again now we repeat the process of taking the absolute difference between adjacent neighbors:

$$2,3,5,7,11,13,17,19,\dots$$ $$1,2,2,4,2,4,2,\dots$$ $$1,1,3,3,9,9,15,\dots$$ $$0,2,0,6,0,6,\dots$$

Again now we take the difference between this foremost row and the one preceding it:

$$2,3,5,7,11,13,17,19,\dots$$ $$1,2,2,4,2,4,2,\dots$$ $$1,1,3,3,9,9,15,\dots$$ $$0,2,0,6,0,6,\dots$$

Alternating between these two procedures indefinitely on sees a pattern emerge:

$$2,3,5,7,11,13,17,19,\dots$$ $$1,2,2,4,2,4,2,\dots$$ $$1,\textbf{1},3,3,9,9,15,\dots$$ $$0,\textbf{2},0,6,0,6,\dots$$ $$\textbf{1},\textbf{-1},3,-3,9,3,\dots$$ $$\textbf{2},\textbf{4},6,12,6,\dots$$ $$\textbf{-1},\textbf{-5},-3,-15,3,\dots$$ $$\textbf{4},\textbf{2},12,18,\dots$$ $$\textbf{-5},\textbf{-7},-15,-33,\dots$$ $$\textbf{2},\textbf{8},18,\dots$$ $$\textbf{-7},\textbf{-15},10,\dots$$ $$\textbf{8},\textbf{25},\dots$$ $$\textbf{-15},-40,\dots$$ $$\textbf{25},\dots$$

We note that in the number $1$ in bold in rowrepeats again in row. Similarly we see the bold $2$ repeats in another row. And so on for every bold number. Hence, as a pattern has emerged the sequence contains structure.

## Algebraic Representation

The above manipulations can also be represented algebraically using a nilpotent matrix. Consider the following example of primes, again. But first some definitions:

Let $x = 1 - \epsilon$ where 1 represents the identity matrix and epsilon is a nilpotent matrix such that $\epsilon^2 = 0$. We define $y$ satisfying the properties: $xy =1$ and $x^\lambda + y^\lambda = 2$ for any $\lambda$ being an integer.

$$K = s x^2 + s^2 x^3 + s^3 x^5 + \dots$$

Multiplying $s$ both sides we get:

$$Ks = 0+ s^2 x^2 + s^3 x^3 + s^4 x^5 + \dots$$

Subtracting the equations one gets:

$$K(s-1) = -s x^2 + s^2 x^2(1-x) + s^3 x^3(1-x^2 ) + \dots$$

Note in the above procedure this is quite similar to taking absolute difference between the primes. Now, using $x^\lambda + y^\lambda = 2$:

$$K(s-1) = -s x^2 + s^2 x^2(y-1) + s^3 x^3(y^2-1 ) + \dots$$

Defining $K_1$ as a sequence with only positive coefficients: $K_1 = s x^2 + s^2 x^2 + s^3 x^3 + \dots$ and using $xy =1$. Hence,

$$K(s-1) + K_1 = s^2 x + s^3 x + \dots$$

Note the above step is similar to subtraction between rows!

Hence, we can represent all the manipulations algebraically!

=

## Questions

What are some non random sequences row math does not make a pattern emerge (I've tried it for Fibonacci, geometric, etc)? And a pattern emerges everytime (for some reason). Why does a pattern emerge to begin with?

• So, one wouldn't know how to generate the primes (that we all know how to generate)? – John B Jan 28 '18 at 21:38
• nothing is random in math – The Great Duck Jan 29 '18 at 0:04
• @TheGreatDuck I think I've edited my question to be even clearer now (about the randomness ) ... by randomness I'm referring to non-deterministic – More Anonymous Jan 29 '18 at 1:03
• By randomly flipping a coin, I can produce a sequence $00000\ldots$. There is a very well known theory of random infinite sequences, known as the theory of Martin-Lof randomness. But that theory does not try to ask whether a sequence was produced by a non-deterministic Turing machine, because every sequence can be produced by a nondeterministic Turing machine. – Carl Mummert Jan 29 '18 at 1:40
• @More Anonymous: yes, the odds are zero. But it could be generated by a nondeterministic Turing machine, following one of the legal execution paths. Your example is interesting, though. – Carl Mummert Jan 29 '18 at 2:10

It looks to me like your method always produces this pattern.

Here is a list of random integers between 1 and 10, and the result of your procedure:

$$\begin{array}{cccccccccc} 10 & 7 & 8 & 5 & 10 & 8 & 5 & 3 & 3 & 1 \\ 3 & 1 & 3 & 5 & 2 & 3 & 2 & 0 & 2 & \text{} \\ 7 & 6 & 5 & 0 & 8 & 5 & 3 & 3 & 1 & \text{} \\ 1 & 1 & 5 & 8 & 3 & 2 & 0 & 2 & \text{} & \text{} \\ 6 & 5 & 0 & -8 & 5 & 3 & 3 & 1 & \text{} & \text{} \\ 1 & 5 & 8 & 13 & 2 & 0 & 2 & \text{} & \text{} & \text{} \\ 5 & 0 & -8 & -21 & 3 & 3 & 1 & \text{} & \text{} & \text{} \\ 5 & 8 & 13 & 24 & 0 & 2 & \text{} & \text{} & \text{} & \text{} \\ 0 & -8 & -21 & -45 & 3 & 1 & \text{} & \text{} & \text{} & \text{} \\ 8 & 13 & 24 & 48 & 2 & \text{} & \text{} & \text{} & \text{} & \text{} \\ -8 & -21 & -45 & -93 & 1 & \text{} & \text{} & \text{} & \text{} & \text{} \\ 13 & 24 & 48 & 94 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ -21 & -45 & -93 & -187 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 24 & 48 & 94 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ -45 & -93 & -187 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 48 & 94 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ -93 & -187 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 94 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ -187 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ \end{array}$$

• Thus we learn an important lesson on the necessity of testing a classification scheme not just on positive examples but also negative ones. – Rahul Jan 29 '18 at 5:21
• that's quite interesting are you sure you didn't pick the pattern first and then reverse engineer the numbers ? Is this true for all "random" numbers ? – More Anonymous Jan 29 '18 at 6:32
• Also while the definition of pattern is vague I feel it is improbable any pattern would pursisit in an infinite sequence ..... – More Anonymous Jan 29 '18 at 6:38
• Also there was a comment which said $1,2,3,4,5,6,7,8,...$ creates a different pattern – More Anonymous Jan 29 '18 at 6:40
• Why don't you try it yourself before insinuating fabrication on my part? – Rahul Jan 29 '18 at 7:04

Why does a pattern emerge to begin with?

Regardless of the source of the first row (deterministic vs. non-deterministic, random vs. non-random, etc.), your procedure may naturally produce that pattern because (1) it produces the pattern just when a row contains non-increasing segments, (2) it always replaces non-increasing segments by other non-increasing segments (thus maintaining the pattern once it appears), whereas (3) it often replaces increasing segments by non-increasing segments.

To see this, consider just the odd-numbered rows, the first row being row #1. If the $i$th element of an odd row equals the $(i+1)$th element of the preceding odd row, then let us say that those two positions exhibit "Pattern A" -- i.e., the pattern you've noticed.

Now if $(a,b,c,\dots)$ is any segment of an odd row, then the next odd row contains, in the same positions, segment $(a-|a-b|,\ b-|b-c|,\ldots)$; so, if $a\ge b$, then $a-|a-b|=b\ge b-|b-c|$, and the non-increasing pair $(a,b)$ is just replaced by another non-increasing pair $(b,\ b-|b-c|)$, thus exhibiting Pattern A in those positions in those two rows and in all future odd rows.

Hence, any segment of non-increasing values will generate Pattern A, and this pattern is permanent, as the "non-increasingness" persists in all future odd rows. On the other hand, examples show that the "increasingness" of a segment is often transient, so we should not be surprised to see Pattern A arising as some increasing segments get replaced by permanent non-increasing segments. (Evidently, a similar phenomenon occurs also among even-numbered rows.)

NB: If a sequence is not strictly increasing, then it is guaranteed to produce Pattern A in some positions, so I think there are some interesting unanswered questions concerning the odd rows:

1. What property of a strictly increasing sequence guarantees that it will never produce Pattern A (i.e., that it never generates a non-increasing segment). The only examples I've found are linearly increasing sequences; i.e., $x_n = an+b,\ \ a>0.$ Are there others?

2. What property of a sequence guarantees that it will never produce Pattern A in a particular place (i.e., that a particular increasing adjacent pair $(a,b)$ does not eventually get replaced by a non-increasing pair)?

For the sequence of primes, here's a picture showing whether the first $80$ (overlapping) pairs in each odd row are increasing $(+)$ or non-increasing $(-)$; i.e., Pattern A occurs at every $(-)$. The index here counts how many odd rows precede it:

For the sequence of primes, do all pairs -- no matter how far down a row -- eventually become non-increasing (and hence exhibit Pattern A)?

Many very regular sequences have proper sub-regions where Pattern A seems to never appear, e.g., the Fibonacci sequence:

How to prove here that the $(+)$ (increasing) pairs in alternate positions never get converted to $(-)$ (non-increasing) pairs?