# Priming for the primes [closed]

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.

• There appears to be a connection between prime numbers and knot theory which is explained in the context of arithmetic topology; see arXiv:0904.3399. Note this is distinct from the concept of prime knots. Jun 25 at 3:09
• FYI: the use of products of prime numbers to encode logical statements dates back to long before Gödel. It was used by Leibniz, for example. Jun 25 at 12:48
• I enjoyed the flowery language and even the anecdote, but I don't see much content in this question. Indeed, primes appear in many places in math, not only in number theory. Making a "big list" of such appearances seems (to me) pointless, and in the examples you list (cyclotomic polynomials, necklaces), the link to prime numbers is entirely obvious. Jun 25 at 14:00
• Surely you know that the place for disputing closure is meta.mathoverflow.net/questions/223/… – if you can write a strong defense of this question, and refrain from making snide remarks about other MO users, you may convince others to vote to reopen. Jun 30 at 2:51
• You just can't help yourself, can you, Tom? Jul 1 at 4:16

The nonzero characteristics of fields are precisely the prime numbers.

• A simple reference? Jun 25 at 8:11
• @TomCopeland see any algebra textbook that discusses fields. Or google "field characteristic prime". Jun 25 at 13:56
• Gerry, please email me. Jun 27 at 21:58

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

• Though “simple” is vaguely “prime, but for groups”. Jun 25 at 8:02
• A simple reference? Jun 25 at 8:11
• @TomCopeland see any algebra book that discusses simple groups. Or google "simple group abelian prime". Jun 25 at 13:57
• E.g. (?), Naive Lie Theory by Stillwell: More generally, $A_n$ is simple for n > 5, so Galois had in fact discovered an infinite family of finite simple groups. Apart from the infinite family of cyclic groups of prime order, the finite simple groups in the other infinite families are finite analogues of Lie groups. Each infinite matrix Lie group G spawns infinitely many finite groups, obtained by replacing the matrix entries in elements of G by entries from a finite field, such as the field of integers mod 2. Jun 25 at 16:44
• @TomCopeland Galois did not prove that $A_n$ is simple for $n>4$. He did not do any work whatsoever with the alternating group. This is a common misconception. Jun 25 at 20:45

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.

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.

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.

• In your example with the forks and spoons, what does addition correspond to?
– Joe
Jun 25 at 15:59
• @Joe If you mean addition of two integers that represent two sets: it corresponds to nothing simple. Prime factorization interacts very badly with addition. Although not completely at random, if abc conjecture is true. Jun 25 at 18:25
• I had a teacher who said, as an explanation of why Goldbach's Conjecture and such are so hard to deal with, "Primes were not meant to be added." Jun 25 at 23:45
• @GerryMyerson Similarly, Pierre Colmez says, in his book "Éléments d'analyse et d'algèbre", in a note about the abc conjecture: "it does not seem about to be proven (which means the equation $a + b = c$ is more subtle than it looks...)". Jun 26 at 0:50

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.

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.

• "...which no prime number theorist would be interested in..." Such a person may be interested in other areas of math too! For a similar example closer to number theory (but not "prime number theory"), an $f \in \mathbf Q[x_1,\ldots,x_n]$ is irreducible over the algebraic closure $\overline{\mathbf Q}$ if and only if it is irreducible over $\overline{\mathbf F}_p$ for all sufficiently large $p$, and the lower bound on $p$ could be big: $x^9y−9x^9−2x+9y+2$ is irreducible over $\overline{\mathbf Q}$ and reducible mod $p$ for $p=86940255267545011$ (an 18-digit prime). Is that uninteresting? Jun 26 at 4:30
• See Example A.19 in kconrad.math.uconn.edu/blurbs/ringtheory/maxideal-polyring.pdf for an explanation of the example in my previous comment. Jun 26 at 4:31
• From a theorem of Adyan and Lysenok in 1991 (see iopscience.iop.org/article/10.1070/IM1992v039n02ABEH002232/pdf), Tarski monsters exist for all primes $p \geq 1009$. This had initially been proved by Olshansky for primes $p > 10^{75}$. If I correctly understand the main result of a paper of Adian from 2015 (see link.springer.com/content/pdf/10.1134/S0081543815040045.pdf), Tarski monsters exist for all primes $p \geq 101$. I wonder why the Wikipedia page on Tarski monsters only mentions the lower bound $p > 10^{75}$. Jun 26 at 4:59
• @KConrad At least for the case of $p \geq 101$, no full proof ever appeared before Adian passed away. Jun 26 at 7:34
• @Wojowu yes they are the same. See page 49 of the Springer-Verlag article. Jun 26 at 12:59

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

• Around 1977-78, I used maximal shift registers to construct indecomposable finite window 1-dimensional covariant image transformations. Jun 25 at 13:39
• Isn't the length of a maximal shift register actually $p^k-1$, not $p^k$? Jun 25 at 23:53
• @GerryMyerson, of course, I'll correct it (0....0 is an orbit by itself, etc. I had Galois fields in the back of my mind). Jun 26 at 3:46

(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.

• But that's (applied) number theory, right? Jun 25 at 17:53
• Hm, I am not really into that field so can not advocate for any side, but I will say that cryptography is definitely a separate branch of mathematics/theoretical computer science. Is use of prime numbers in that field only applied number theory is a different question. Jun 25 at 17:56
• In the early days of public-key cryptography, it was said that only primes $p$ for which $p\pm1$ had large prime factors were safe to use, thus, not all (very large) primes. I don't know whether this is still the case. Jun 26 at 0:04
• @GerryMyerson, in some applications it's still advised to use "safe primes" (the counterparts of Sophie-Germain primes), but in general public-key cryptography is moving to elliptic curve groups rather than multiplication groups modulo a semiprime. Jun 27 at 13:39

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.

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

• Are all prime numbers relevant here, or only those of some special form(s)? Jun 27 at 2:55
• @GerryMyerson, it depends on the subtopics. Sometimes all promes are involved and sometimes only special primes. #### In the case of basic early results, they hold for arbitrary primes. Jun 27 at 4:53

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.

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.

• No, you don't need the fundamental theorem of arithmetic for the bijectivity of $f$. You need the even/odd dichotomy and an induction that shows that each positive integer can only be divided by $2$ a finite number of times. Jun 26 at 22:32
• I have just rephrased those lines of my answer. Jun 28 at 2:12

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