0
$\begingroup$

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

\begin{equation} 2,3,5,7,11,13,17,19,23,\dots \end{equation}

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

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

\begin{equation} 2,3,5,7,11,13,17,19,\dots \end{equation} \begin{equation} 1,2,2,4,2,4,2,\dots \end{equation} \begin{equation} 1,1,3,3,9,9,15,\dots \end{equation}

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

\begin{equation} 2,3,5,7,11,13,17,19,\dots \end{equation} \begin{equation} 1,2,2,4,2,4,2,\dots \end{equation} \begin{equation} 1,1,3,3,9,9,15,\dots \end{equation} \begin{equation} 0,2,0,6,0,6,\dots \end{equation}

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

\begin{equation} 2,3,5,7,11,13,17,19,\dots \end{equation} \begin{equation} 1,2,2,4,2,4,2,\dots \end{equation} \begin{equation} 1,1,3,3,9,9,15,\dots \end{equation} \begin{equation} 0,2,0,6,0,6,\dots \end{equation}

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

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

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.

enter image description here

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.

\begin{equation} K = s x^2 + s^2 x^3 + s^3 x^5 + \dots \end{equation}

Multiplying $s$ both sides we get:

\begin{equation} Ks = 0+ s^2 x^2 + s^3 x^3 + s^4 x^5 + \dots \end{equation}

Subtracting the equations one gets:

\begin{equation} K(s-1) = -s x^2 + s^2 x^2(1-x) + s^3 x^3(1-x^2 ) + \dots \end{equation}

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

\begin{equation} K(s-1) = -s x^2 + s^2 x^2(y-1) + s^3 x^3(y^2-1 ) + \dots \end{equation}

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,

\begin{equation} K(s-1) + K_1 = s^2 x + s^3 x + \dots \end{equation}

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?

$\endgroup$
  • 3
    $\begingroup$ So, one wouldn't know how to generate the primes (that we all know how to generate)? $\endgroup$ – John B Jan 28 '18 at 21:38
  • 2
    $\begingroup$ nothing is random in math $\endgroup$ – The Great Duck Jan 29 '18 at 0:04
  • 2
    $\begingroup$ @TheGreatDuck I think I've edited my question to be even clearer now (about the randomness ) ... by randomness I'm referring to non-deterministic $\endgroup$ – More Anonymous Jan 29 '18 at 1:03
  • 2
    $\begingroup$ 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. $\endgroup$ – Carl Mummert Jan 29 '18 at 1:40
  • 4
    $\begingroup$ @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. $\endgroup$ – Carl Mummert Jan 29 '18 at 2:10
3
$\begingroup$

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} $$

$\endgroup$
  • 7
    $\begingroup$ Thus we learn an important lesson on the necessity of testing a classification scheme not just on positive examples but also negative ones. $\endgroup$ – Rahul Jan 29 '18 at 5:21
  • $\begingroup$ 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 ? $\endgroup$ – More Anonymous Jan 29 '18 at 6:32
  • $\begingroup$ Also while the definition of pattern is vague I feel it is improbable any pattern would pursisit in an infinite sequence ..... $\endgroup$ – More Anonymous Jan 29 '18 at 6:38
  • $\begingroup$ Also there was a comment which said $1,2,3,4,5,6,7,8,... $ creates a different pattern $\endgroup$ – More Anonymous Jan 29 '18 at 6:40
  • 5
    $\begingroup$ Why don't you try it yourself before insinuating fabrication on my part? $\endgroup$ – Rahul Jan 29 '18 at 7:04
3
$\begingroup$

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:

+/- picture for the primes sequence

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:

+/- picture for the Fibonacci sequence

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

$\endgroup$

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.