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.

Read the rest of this entry »

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?

Read the rest of this entry »

In this post, we discuss a few ways in which the symmetric and alternating groups can be realized as finite collections of self-maps on the Riemann sphere.  Throughout, our group operation will be composition of functions: as such, the maps we choose will necessarily be homeomorphisms of \mathbb{P}^1.  Within this broad framework, two classes are of particular interest:

1. The group of biholomorphic maps f: \mathbb{P}^1 \to \mathbb{P}^1 (those that respect the structure of \mathbb{P}^1 as a Riemann surface). It is well-known that such maps are given by Möbius transformations, i.e. rational functions of the form

\displaystyle f(z) = \frac{a z +b}{cz +d},

satisfying ad-bc \neq 0 \in \mathbb{C}. The group of Möbius transformations (also known as the Möbius Group and herein denoted \mathcal{M}) is naturally isomorphic to \mathrm{PSL}_2(\mathbb{C}), the projective (special) linear group, via:

\displaystyle\frac{az+b}{cz+d} \mapsto \left(\begin{matrix} a & b \\ c & d \end{matrix} \right).

2. The group of conformal maps f: \mathbb{P}^1 \to \mathbb{P}^1, denoted \mathcal{C} for brevity.  To be clear, here we refer to those maps f which preserve unsigned angle measure. (In contrast, some authors require conformal maps to preserve orientation as well.)  We recall the fundamental result that such maps contain the Möbius group as a subgroup of index two.  To be specific, any conformal self-map on \mathbb{P}^1 is either biholomorphic (returning to case (1)), or bijective and anti-holomorphic: a biholomorphic function of the complex conjugate \overline{z}.

After the fold, we begin a two-part program to calculate the maximal n such that the symmetric group S_n injects into \mathcal{M} (resp. \mathcal{C}).  Along the way, we study injections of the alternating group into \mathcal{M}, and highlight some exceptional cases in which our injections can be attached to group actions on a finite invariant set.

Read the rest of this entry »

In differential calculus, the product rule is both simple in form and high in utility.  As such, it is typically presented early on in calculus courses — soon after the linearity of the derivative, in fact.  Moreover, the product rule is easy to derive from first principles:

Theorem (Product Rule): Let f and g be differentiable on the open set U. Then fg is differentiable on U, and we have

(fg)'(x)=f(x)g'(x)+g(x)f'(x)  for all  x \in U.

Proof: For x \in U, we have (by definition of the derivative)

\displaystyle(fg)'(x) = \lim_{\epsilon \to 0} \frac{f(x+\epsilon)g(x+\epsilon)-f(x)g(x)}{\epsilon}

\displaystyle = \lim_{\epsilon \to 0} \frac{\left(f(x+\epsilon)-f(x)\right)g(x+\epsilon)+f(x)\left(g(x+\epsilon)-g(x)\right)}{\epsilon}

\displaystyle = \lim_{\epsilon \to 0} \frac{g(x\!+\!\epsilon)\left(f(x\!+\!\epsilon)-f(x)\right)}{\epsilon}\!+\!\lim_{\epsilon \to 0} \frac{f(x)(g(x\!+\!\epsilon)-g(x))}{\epsilon},

under the assumption that each of these last two limits exists.  This of course holds, as these limits are g(x)f'(x) and f(x)g'(x), respectively.   \square

All in all, then, the product rule is easy to prove and easy to use.  But — and this is of utmost pedagogical importance — is the product rule intuitive? By this proof alone, I would argue not; the manipulation of the numerator is weakly-motivated and our result falls out without reference to more general phenomena.

In this post, we’ll explore the merits of a second proof of the product rule, one that I hope presents a motivated and compelling argument as to why the product rule should look the way it does.

Read the rest of this entry »

In 1946, S. Bochner published the paper Formal Lie Groups, in which he noted that several classical theorems (due to Sophus Lie) concerning infinitesimal transformations on Lie groups continue to hold when the (convergent) power series locally representing the group law was replaced by a suitable formal analogue.  It was not long before this formalism found far-reaching uses in algebraic number theory and algebraic topology.

Unfortunately, few students see more than two or three explicit (i.e. closed form) group laws before stumbling into the deep end of abstract nonsense.  In this article, we’ll see in a rigorous sense why this must be the case, providing along the way a complete classification of polynomial and rational formal group laws (over any reduced ring).

Read the rest of this entry »

In its early years, the rigorous study of games (game theory) looked only upon games of so-called perfect information, in which each player knows the moves carried out by all players.  Such games laid the foundation for early economic models of perfect competition, wherein consumers have full knowledge of both market conditions and each others’ consumer tendencies.

Of course, perfect competition — taken literally — cannot exist, and the failure of this model and others prompted economic theorists to study a more-general class of games, games of limited information (also known as games of imperfect information).

In this post, we’ll look at one-player games of limited information (sometimes classified as puzzles, not games) through a topological lens, and create for each game a poset of topologies under which topologically indistinguishable points correspond to outcomes that are indiscernible in a limited-information context.  Expanding this dictionary, we’ll describe a topology on the outcome space under which the “safe” or “warranted” extension of one’s limited information relates to the continuity of certain maps.

Read the rest of this entry »

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 constantsc_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) forn \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.

Read the rest of this entry »

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.

Read the rest of this entry »

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

Read the rest of this entry »

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

Read the rest of this entry »