# What Constitutes a Pattern

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?

• 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). Commented Jun 5, 2015 at 6:11
• 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? Commented Jun 5, 2015 at 6:13
• I guess a pattern should be a relation between things, not a thing itself. Commented Jun 5, 2015 at 6:14
• @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. Commented Jun 5, 2015 at 6:14
• 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. Commented Jun 5, 2015 at 6:49