You are currently browsing the category archive for the ‘Number Theory’ category.

John Wilson (1741-1793) was a well-known English mathematician in his time, whose legacy lives on in his eponymous result, Wilson’s Theorem. To recall, this is the statement that an integer $n >1$ is prime if and only if

$(n-1)! \equiv -1 \mod n.$

(The “if” part is trivial.) As is the case for many historical results, Wilson’s Theorem was not proven by Wilson. Instead, it was Joseph Lagrange who provided the first proof.

The proof, as we see it today, might be phrased as follows:

Proof: Suppose that $p$ is prime. Then each of the nonzero residues modulo $p$ is a unit, so that $(p-1)!$ represents the product over all units in $\mathbb{Z}/p\mathbb{Z}$. If

$a \not\equiv a^{-1} \mod p$,   i.e.    $a^2 \not\equiv 1 \mod p$,

then $a$ and its inverse each show up in our list of units. We cancel out such terms in pairs, and conclude that

$\displaystyle (p-1)! \equiv \prod_{a^2 \equiv 1 (p)} a \mod p.$

We have $a^2 \equiv 1 \mod p$ if and only if $p \mid (a-1)(a+1)$, which by primality of $p$ forces $p \mid (a-1)$ or $p \mid (a+1)$. In other words, $a \equiv \pm 1 \mod p$. It follows that

$(p-1)! \equiv 1(-1) \equiv -1 \mod p.$

$\square$

When $n$ is composite, the direct translation of Wilson’s problem gives

$(n-1)! \equiv 0 \mod n.$

The problem, here, is that we’ve multiplied a number of zero divisors together, which can be avoided by only multiplying across the units, $U_n$, of $\mathbb{Z}/n\mathbb{Z}$. In this post, we consider the product

$\displaystyle \prod_{a \in U_n} a \mod n,$

determine its value, give credit to Gauss for doing so over two centuries ago, and discuss a few generalizations.

Back in high school, I came across the following contest problem:

Question: Let $S$ be a set of positive integers totaling 20.  What is the maximum value of

$\displaystyle\prod_{x \in S} x$

It’s a fun problem, so don’t rush past the spoiler tags too fast.  When you’re ready, I’ll spoil the solution to the question above, and discuss a “continuous” version of the question above.  Namely, what happens when $S$ is allowed to include positive real numbers?

In 1737, Euler presented a novel proof of the infinitude of the primes, in showing that the harmonic sum of the primes diverges.  Explicitly, Euler’s work furnishes the estimate

$\displaystyle\sum_{p \leq x} 1/p=\log \log x + O(1),$

in which the sum exhausts the rational primes at most $x$.  At this point, it becomes quite elementary to derive the two inequalities

$\displaystyle\limsup_{n \to \infty} \frac{p_n}{n \log n} \geq 1 \quad \text{and} \quad \liminf_{n \to \infty} \frac{p_n}{n \log n} \leq 1.$

Results of this flavor remained essentially unimproved for over a century, until Chebyshev presented the following landmark theorem in 1852:

Theorem (Chebyshev): There exist positive constants $c_1,c_2$ such that

$\displaystyle c_1 \leq \liminf_{x \to \infty} \frac{\pi(x)\log x}{x} \leq \limsup_{x \to \infty} \frac{\pi(x) \log x}{x} \leq c_2.$

Thus Chebyshev’s Theorem shows that $x/\log x$ represents the growth rate (up to constants) of $\pi(x)$; stated equivalently in Bachmann-Landau notation, we have $\pi(x) \in \Theta(x/\log x)$.  Yet more is true: the constants$c_1,c_2>0$ in Chebyshev’s proof are therein made effective, and can be taken as

$c_1 =\frac{\log 2}{2} +\frac{\log 3}{3} + \frac{\log 5}{5}-\frac{\log 30}{30} \approx 0.921292;$

$c_2 = \frac{6}{5}\left(\frac{\log 2}{2} +\frac{\log 3}{3} + \frac{\log 5}{5}-\frac{\log 30}{30}\right)\approx1.10555.$

As a corollary to Chebyshev’s Theorem, we have $\pi(2n-3)>\pi(n)$ for$n \gg 0$.  By making this implicit bound on $n$ precise, Chebyshev was able to prove Bertrand’s Postulate (thereafter known as the Bertrand-Chebyshev Theorem).

In this post, we’ll prove a variant of Chebyshev’s Theorem in great generality, and discuss some historically competitive bounds on the constants $c_1$ and $c_2$ given above.  Lastly, we’ll discuss how Chebyshev’s Theorem relates to proposed “elementary” proofs of the PNT.

This post serves to resolve some questions posed at the end of a previous article, Unit-Prime Dichotomy for Complex Subrings, in which we began to look at the tension between the relative sizes of the units group and the spectrum of  a complex subring (with unity).  As a disclaimer, I assume from this point familiarity with the topics presented therein.  To begin, we recall a Theorem from the prequel (Theorem 4):

Theorem: Let $R \subset \mathbb{C}$ be a subring (with unity), and suppose that $R$ has finite spectrum.  Then $R^\times$ is dense in $\mathrm{cl}(\mathrm{Frac}(R))$, the topological closure of the fraction field of $R$.

In particular — assuming a finite spectrum — it follows that the rank of $R^\times$ (considered as an abelian group) is bounded below by two. Unfortunately, this is as far as our previous methods will take us, even when $R \not\subset \mathbb{R}$ (see the Exercises).

The primary objective of this post is an extension to this result.  Specifically, we would like to capture in a purely algebraic way (e.g. without mention of the topology on $\mathbb{C}$) the fact that $R^\times$ becomes quite large in certain rings with finite spectrum.  After the fold we’ll accomplish exactly that, with the following Theorem and its generalizations to a wide class of commutative rings:

Theorem 1: Suppose that $R \subset \mathbb{C}$ is a subring (with unity).  If $R$ has finite spectrum, then $R^\times$ has infinite rank as an abelian group.

Throughout, we take $R \subset \mathbb{C}$ as a complex subring (with unity).  In this article, we’ll be interested in natural analogues of Euclid’s proof of the infinitude of the primes (i.e. the case $R = \mathbb{Z})$.  In particular, we’ll show that Euclid’s proof (and generalizations to this method) can be recast as a relationship between the size of the unit group $R^\times$ of $R$ and $\# \mathrm{Spec}(R)$, the number of prime ideals in$R$. (Here, $\mathrm{Spec}(R)$ denotes the spectrum of $R$.)

For the sake of explicit analogy, we include a (needlessly abstracted) version of Euclid’s result now:

Theorem 1 (Euclid):  The integers have infinite spectrum.

Proof: If not, let $\mathfrak{p}_1,\ldots, \mathfrak{p}_m$ exhaust the list of prime ideals.  As the integers form a PID, (in fact, they form a Euclidean domain), we may associate to each given ideal a prime generator $p_i$ such that $(p_i) = \mathfrak{p}_i$.  Let $N:= \prod p_i$; as $N+1$ is not a unit (replacing $N$ with $kN \gg 0$ if necessary), it admits a prime factor $p$ which equals some $p_i$.  But then $p$ divides both $N$ and $N+1$, whence $1$ as well.  This is a contradiction, and our result follows. $\square$

It is worth remarking that the “PID-ness” of the integers is not needed in the derivation of Theorem 1.  Indeed, if $\mathfrak{p}_i$ were not principal, we may take instead $p_i$ to be any non-zero element of $\mathfrak{p}_i$.  Thus, we see that the PID-ness of $\mathbb{Z}$ is not the crucial property of the integers (viewed as a subfield of $\mathbb{C}$) upon which our proof stands.  Rather — as we’ll see after the fold — Euclid’s proof frames the infinitude of primes as a consequence of the finiteness of the units group!

Let $k/\mathbb{Q}$ be a number field, i.e. a finite field extension to $\mathbb{Q}$.  We recall that the ring of integers in k, denoted $\mathcal{O}_k$, is the ring

$\mathcal{O}_k := \{\alpha \in k : f(\alpha)=0 \text{ for some monic } f(t) \in \mathbb{Z}[t]\}.$

For $k= \mathbb{Q}$, the ring of integers is just the integers $\mathbb{Z}$, in which case we recall the  Fundamental Theorem of Arithmetic: that every integer $n \neq 0$ may be written as a finite product

$n=\pm 1\cdot p_1 \cdots p_k,$

in which the $\{p_i\}$ are prime and uniquely determined (up to permutation). Domains for which this holds are known in general as unique factorization domains (UFDs). For $k = \mathbb{Q}(\sqrt{d})$ — with $d \neq 0,1$ square-free — the ring of integers $\mathcal{O}_k$ will in general not be a UFD.  In fact, for $d <0$, the integers $\mathcal{O}_k$ have unique factorization only in the 9 cases

$d=-1, -2, -3, -7, -11, -19, -43, -67, -163.$

Far less is known in the case $d >0$ (in which case k is known as a real quadratic field), although an unproven conjecture dating back to Gauss suggests that there should be infinitely many real quadratic fields.  More recently, some heuristics stemming from Cohen suggests that the ring of integers in $\mathbb{Q}(\sqrt{d})$ should be a UFD with probability $\approx 0.75446$ as $d \to \infty$ on the square-free integers.

Here, we’ll focus on a more tractable variant of this problem:

Question: What can be said about the number $\tau(n)$ of distinct real quadratic fields $k=\mathbb{Q}(\sqrt{d})$ with $d\leq n$ for which $\mathcal{O}_k$ is not a UFD?

For a weak answer to the question above, we devote the rest of this article to the establishment of the following bound:

Theorem: As $n \to \infty$, we have

$\tau(n) \gg \sqrt{n}\log n,$

in which the implied constant is made effective (e.g. greater than $1/11$).

In 1832, Galois introduced the concept of normal subgroups, and proved that the groups $A_n$ (for $n>4$) and $\mathrm{PSL}_2(\mathbb{F}_q)$ (for $q>4$) were simple, i.e. admit no non-trivial (proper) normal subgroups.  In 1892, Hölder asked for a classification of all finite simple groups, and the final classification of finite simple groups in 2004 by Aschbacher and Smith’s resolution of the quasithin case thus resolves an open problem over a century in the making. (Note: the great majority of the classification theorem concluded in the 1980’s.  A computational error was identified and resolved in 2008.)

One immediate consequence of the classification of finite simple groups (CFSG) is that the set S given by

$S:=\{n \in \mathbb{N} : \text{there exists a simple group of order } n\}$

has natural density 0.  Yet it seems unlikely that this result requires the tens of thousands of pages currently involved in the proof of the CFSG, and for the rest of this article we seek to bound the density of S using arithmetic methods.

Let $S_n$ denote the permutation group on n letters.  Herein, we consider the following question, brought to light by Landau in 1902:

Question: What is the maximal order of an element in $S_n$?

By convention, we shall refer to this maximal order as $g(n)$.  Thus, for instance, Lagrange’s theorem gives the elementary bound $g(n) \leq n!$.  We may obtain sharper bounds by noting that $S_n$ is centerless, but tweaks like this will fail to give more than a gain of a multiplicative constant.  A far more productive route comes from the following Proposition:

Proposition: Let $\{a_1,\ldots, a_k\}$ be a partition of n into positive integers.  Then $\prod_i a_i \leq 3^{n/3}$, with equality if and only if $a_i = 3$ for all i.

Proof: Let $\{a_1,\ldots, a_k\}$ be a partition of n such that $\prod a_i$ is maximized.  If $a_i >3$ for any i, we have $2(a_i-2)>a_i$, and the partition

$\{a_1,\ldots, a_{i-1}, 2, a_i-2,a_{i+1},\ldots, a_k\}$

admits a strictly larger product.  Thus, we may assume that $a_i =2,3$ for all i. Furthermore, the relation $2^3 <3^2$ implies that in a maximal partition we may have $a_i =2$ for at most two such i.  It now follows (by cases) that our maximal product $A(n)$ takes the form

$A(n) = \begin{cases} 3^{n/3}, \hspace{15.5 mm} n \equiv 0 \mod 3 \\ 4 \cdot 3^{(n-4)/3}, \quad n \equiv 1 \mod 3 \\ 2 \cdot 3^{(n-2)/3}, \quad n \equiv 2 \mod 3 \end{cases}.$

Our result follows from the inequalities $4 \cdot 3^{-4/3} < 2 \cdot 3^{-2/3} <1$. $\square$

Note: buried under all of this is the fact that the function $f(x) = x^{1/x}$ attains a global maximum at $x=e$, and that 3 is the closest integer to e (this also underlies the marginal appearance of 2, as the second closest integer approximation to e).  This will become more evident as we continue.

As a Corollary, we obtain a new upper bound for the function $g(n)$:

Corollary: For all n, we have $g(n) \leq 3^{n/3}$, with equality if and only if $n=3$.

Proof: We note that $g(n)$ is the maximum value of $\mathrm{lcm}(a_1,\ldots a_k)$, as $\{a_i\}$ varies over the partitions of n.  But $\mathrm{lcm}(a_1\ldots, a_k) \leq \prod a_i \leq 3^{n/3}$, with equality if and only if (1) $a_i =3$ for all and (2) the $\{a_i\}$ are pairwise coprime.  In particular, equality holds above if and only if $n=3$ (achieved with the partition $\{3\}$). $\square$

Note: this result is stronger than the commonly-cited bound $g(n) < e^{n/e}$, which holds for all n.

The bound arising from our Proposition is nevertheless weak in method (in that we have only used the fact that $\mathrm{lcm}(a_1,\ldots,a_k)$ divides $a_1\cdots a_k$), and to strengthen it significantly requires the Prime number theorem (PNT).  In fact, Landau’s classical result

$\log g(n) \sim \sqrt{n \log n}$

(which we will derive after the fold) is equivalent to the PNT by means of elementary methods.

For what follows, we define a loaded die as a discrete probability distribution with six outcomes (labelled {1,…,6}), each of which has positive probability. To each such die, we associate a generating polynomial, given by

$p(t):=p_1t+p_2t^2+\ldots +p_6 t^6$

in which $p_i$ denotes the probability of the outcome i.  If $q(t)$ corresponds to another such die, we note that the product

$p(t)q(t) =\sum_i a_i t^i:=\sum_{i=2}^{12}\big( \sum_{k=1}^{i-1} p_k q_{i-k}\big) t^i$

has coefficients which reflect the probabilities of  certain dice sums for p and (and this is the utility of generating polynomials).  We are now ready to ask the following question:

Question: Does there exist a pair of loaded dice such that the probability of rolling any dice sum ({2,…12}) is equally likely?