Priming for the primes

Question

I have to confess that most often my eyes begin to glaze over when someone starts discussing the prime numbers. However, my ears have perked up at times over the primes--maybe first when I learned of their use by Godel and second, of their links to the Riemann zeta function and related analysis. More recently I have encountered the primes when observing the simplicity/regularity of indexed expressions in certain sequences of expressions when the index is prime in contrast to those for the non-prime indices, such as for the cyclotomic polynomials (see "A tangential note" in this MO-A) and for certain colored necklaces (see this MO-Q). In the interest of stimulating interest in or a more informed appreciation of the primes for those who are not classical number theorists, I'd like to ask

In what scenarios do the primes occur that you find of particular interest or utility outside of pure number theory?

Anecdote: Once long ago I was quickly passing through a wing of the Getty Art Museum, the Roman villa in the Palisades in L.A.--a wing containing medieval art with its religious motifs, at that time of little interest to me. I stopped in front of a docent who was enthusiastically informing a group of the symbology underlying a painting. She posed questions that revealed the painting subtly and cleverly indicates three events in the life of Christ in what appears on the surface to be a single moment frozen in time. I now appreciate the depth of meaning in such art.

Answer 1

The nonzero characteristics of fields are precisely the prime numbers.

Answer 2

The abelian simple groups are precisely the groups of prime order.

Answer 3

Primes even appear outside mathematics, here is an example from biology:

The fact that some species of cicadas appear every 7, 13, or 17 years and that these periods are prime numbers has been regarded as a coincidence. We found a simple evolutionary predator-prey model that yields prime-periodic preys having cycles predominantly around the observed values. An evolutionary game on a spatial array leads to travelling waves reminiscent of those observed in excitable systems. The model marks an encounter of two seemingly unrelated disciplines: biology and number theory. A restriction to the latter, provides an evolutionary generator of arbitrarily large prime numbers.

Answer 4

Obvious, but still worth mentionning, because the trick is frequently helpful: to represent a collection of elements of different types, where you can have more than one element per type, and order does not count. E.g. 5 forks + 6 spoons + 4 knives will be represented by $2^5.3^6.5^4$.

Then, union of 2 collections is just multiplication of the integers that represent them.

Note that this can be extended to collections where negative numbers of elements are allowed. (Which happens e.g. in a geometric setting when counting elements that have an orientation, and where the combination of two same-but-opposite-orientation elements is identity). For this, use $\mathbb{Q}$.

Actually one can use other primes in specific cases. If you want to represent a collection of numbers (or any field elements): use prime polynomials. E.g. 3 instances of 2.5 plus 2 instances of 3.7 is represented by $(X-2.5)^3 (X-3.7)^2$. This is handy, because we get for free the elementary symmetric polynomials of the elements being represented: they are $(-1)^k$ the polynomial coefficients.

Answer 5

Here is a characterization of entropy functions due to Faddeev in 1956 (see pp. 229-231 of Faddeev's paper here if you read Russian or Chapter 1 of A. Feinstein's 1958 book Foundations of information theory otherwise).

Theorem. For $d \geq 2$, let $\Delta_d = \{(x_1,\dots,x_d) : 0 \leq x_i \leq 1, \sum x_i = 1\}$. Suppose on each $\Delta_d$ a function $H_d \colon \Delta_d \rightarrow \mathbf R$ is given with the following properties:

(1) each $H_d$ is continuous,

(2) each $H_d$ is a symmetric function of its arguments,

(3) for $d \geq 2$ and all $(x_1,\dots,x_d) \in \Delta_d$ with $x_d > 0$, and $t \in [0,1]$,
$$ H_{d+1}(x_1,\dots,x_{d-1},tx_d,(1-t)x_d) = H_d(x_1,\dots,x_{d-1},x_d) + x_dH_2(t,1-t). $$

Then there is a $k$ in $\mathbf R$ such that on each $\Delta_d$ for $d \geq 2$, $H_d(x_1,\dots,x_d) = -k\sum_{i=1}^d x_i\log x_i$.

There is no mention anywhere in the theorem about prime numbers. The first step of the proof of the theorem is to show $F(n) = H_n(1/n,1/n,\dots,1/n)$ has the form $c\log n$ for a constant $c$. To do this, he shows if $F \colon \mathbf Z^+ \to \mathbf R$ satisfies the three conditions (i) $F(mn) = F(m) + F(n)$ for all $m$ and $n$, (ii) $F(n)/n \to 0$ as $n \to \infty$, and (iii) $F(n) - F(n-1) \to 0$ as $n \to \infty$, then $F(p)/\log p$ has the same value for all prime numbers $p$, and calling that common value $c$ we get $F(n) = c\log n$ for all positive integers $n$ by the prime factorization of $n$. In the proof of this he needs to know there are infinitely many primes.

Answer 6

Regular polygons which you can construct with compass and straightedge have $2^k \cdot p_1 \cdot p_2 \dots p_n$ edges, where $p_i$ are all distinct Fermat primes (so not all primes).

It's the reason Gauss wanted a 17-gon to be carved on his tombstone.

Answer 7

For me, the most spectacular fact that uses primes in an essential way and which no prime number theorist would be interested in is the fact that Tarski monsters exist for all sufficiently large primes $p$. If this was a prime number theory theorem then it would be considered "done", since usually in such cases one can simply check the remaining cases by hand (although sometimes this is itself a non-trivial task; see Helfgott's proof of the ternary Goldbach conjecture in 2013. The "almost" version was proved by Vinogradov in the 1930's). However, it seems that the question of whether there exist Tarski monsters for small primes $p$ is extremely difficult, and that answering the question of whether they exist or not for $p = 5$ is already worthy of top honours.

Answer 8

There are maximal shift registers of length $\ p^k-1\ $ where $\ p\ $ is an arbitrary prime, and $\ k\ $ is an arbitrary natural number.

Answer 9

This concerns prime powers and not strictly primes, but the fact that the topological Tverberg conjecture (see e.g. https://arxiv.org/abs/1605.05141) holds for prime power values of “r” and not any others strikes me as very surprising when you just hear the statement of the conjecture.

Answer 10

(Very large) prime numbers are of particular importance in cryptography. See e.g. RSA algorithm. I remember also some quasi random number generators using prime numbers.

Answer 11

The prime numbers come in handy when studying countability. For example, one can prove that the set of finite subsets of $\mathbb{N}=\{1, 2, 3, \ldots\}$ is countable basically by considering the function $f$ that sends the (finite) subset $\{a_{1}, \ldots, a_{k}\} \in \mathcal{P}(\mathbb{N})$ to the number $p_{1}^{a_{1}}\cdots p_{k}^{a_{k}}$ (where $p_{i}$ is the $i$-th prime number) and invoking afterwards the fundamental theorem of arithmetic.

In addition, the infinitude of the prime numbers is brought to bear in some variants of the Hilbert Hotel story: if all of the $\aleph_{0}$ rooms in the Hotel are already occupied and a countable set of buses with countably infinite passengers in each one of them arrives, how can the manager accommodate all those new visitors? Here is a nice video wherein this variant of the story is discussed: https://youtu.be/Uj3_KqkI9Zo

Last but not least, one can prove that the cartesian product $A \times B$ of the countable sets $A$ and $B$ is countable by considering the function $g \colon \mathbb{N}_{0} \times \mathbb{N}_{0} \to \mathbb{N}_{0}$ defined by $$g(m,n)=2^{m}(2n+1)-1.$$ In order to establish the bijectivity of $g$ one could just invoke the fundamental theorem of arithmetic.

Answer 12

Feedback with carry shift register sequences (FCSRs) are an arithmetic parallel of the LFSRs in the answer by @WlodAA.

They can be represented using $N-$adic numbers and achieve maximal period when $N$ is prime.

Answer 13

Virtually all important examples of error-correcting codes that have a chance to be optimal and practical in applications utilize prime numbers.

Answer 14

Prime numbers occur in a major way in the theory of tactical configurations, in particular in finite geometries.