Mathematics is often referred to as the "study of patterns." What I'm wondering is whether there is somehow a technical way to describe a pattern. For the length of this question let's assume that we're considering integer patterns (i.e. some set of integer sequences $(a_n)_{n \in \mathbb N}$).

A bit more formally, we have a subset $P \subset \mathbb{Z}^\mathbb{N}$ consisting of all patterns. Since $\mathbb{Z}^\mathbb{N}$ is uncountable, it seems desirable that $P$ be countable.

A few examples of patterns are as follows:

  • The prime numbers
  • The outputs of any polynomial with integer coefficients
  • Any recursive formula

The key to these examples is that they are finitely described. So my naive thought is that we wish to have a bijection between some set of finite strings (i.e. descriptions of some sort) (this is a countable set) and the sequences which are described by those strings.

My first solution was to make the following definition:

A pattern is any sequence of integers $(a_n)_{n \in \Bbb{N}}$ such that there exists a Turing machine $M$ which on input $n$ returns $a_n$. Or, essentially, a pattern is any sequence of integers which can be computed by an algorithm.

This ends up failing since the following should be a pattern: Order the set of all Turing machines, and let $t_i$ be the integer describing the $i$th Turing machine that does not halt on a possible input. The sequence $(t_i)_{i \in \Bbb N}$ is inherently not computable, but seems to be a perfectly reasonable pattern.

So I guess my question is, is there a way of making rigorous the notion of a sequence being "finitely described" which would then serve to be a natural definition of pattern?

  • $\begingroup$ I don't see how. I can represent a sequence, finitely, by $a_n = x_0 + x_1n + x_2n^2 + x_3n^3 + x_4n^4$...and this sequence may appear quite complicated (certainly not easily discernible--well unless you guess this form). Given enough such terms--but always finite, say 1,000 terms--we can create almost an arbitrarily complex sequence (the more complex the more terms needed). $\endgroup$ – Jared Jun 5 '15 at 6:11
  • $\begingroup$ It seems like a big oversimplification to reduce patterns, which are pretty much everything in math, to just some subsets. How would you for instance describe quadratic reciprocity (a very nice pattern) with this? $\endgroup$ – Prometheus Jun 5 '15 at 6:13
  • 1
    $\begingroup$ I guess a pattern should be a relation between things, not a thing itself. $\endgroup$ – Prometheus Jun 5 '15 at 6:14
  • $\begingroup$ @Jared Exactly. So with this definition of sequence, given any finite number of terms there exist countably many sequences which can be "extensions" of this finite tail. $\endgroup$ – Andrew Maurer Jun 5 '15 at 6:14
  • 2
    $\begingroup$ Nice question! It reminds me of the old joke: Theorem: Every number is interesting. Proof: Let $S$ be the set of interesting numbers. Then $S$ has a minimum element $n$. But then $n$ has a the very interesting property that it is the least noninteresting number, a contradiction. $\endgroup$ – Jair Taylor Jun 5 '15 at 6:49

Your Answer

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

Browse other questions tagged or ask your own question.