Mathematics

I've tried my hand at a few of Peter Winkler's stumpers in Mathematical Puzzles^[1] with limited success when I lighted on this innocuous-looking one on page 43:

Even Split. Prove that from every subset of \(2n\) integers, you can choose a subset of size \(n\) whose sum is divisible by \(n\).

Aha! One I understand and can no doubt address with some application. Sometimes you can get an idea of the general solution by working through the problem for small \(n\). \(n=1\) and \(n=2\) are easy and \(n=3\) isn't too bad, but \(n=4\) leads to a rat's nest of special cases. I knew trouble was imminent after trying Gemini ("Prove that from every set of 8 integers, you can always choose a subset of size 4 whose sum is divisible by 4"). Several things jumped out:

• It's possible to feel sorry for Gemini as it engages in some world class wheel-spinning.
• Examining cases for small \(n\) brings zero illumination.
• The problem is well known as the Erdös-Ginzburg-Ziv Theorem (EGZ).^[2]

Ivan Niven (1915-1999)

Ivan Niven gave a one page proof that \(\pi\) is irrational in 1946.^[1] I had to work a bit to understand it, so thought a write-up was in order. The proof is by contradiction. Niven starts by assuming that \(\pi = a/b\) for positive integers \(a, b\). Then define:
\begin{align*}
f(x) = f_n(x) = \frac{x^n(a-bx)^n}{n!},
\end{align*}
for some positive integer \(n\). I'm generally going to stick to the notation \(f(x)\) in what follows, otherwise things get a bit top-heavy. Just keep in mind that \(f(x)\) depends on \(n\).

Liouville was the first to produce transcendental numbers.^[1] These "Liouville numbers" are of the form:
\begin{align*}
\frac{1}{a} + \frac{1}{a^{2!}} + \frac{1}{a^{3!}} + \frac{1}{a^{4!}} + \cdots,
\end{align*}
where \(a\) is a positive integer. The key is Liouville's inequality:^[2]

For every real irrational algebraic real number \(\alpha\) of degree \(n\), there exists a positive number \(C\) such that for arbitrary integers \(p\) and \( q \; (q > 0) \):
\begin{align*}
\left|\alpha - \frac{p}{q}\right| > \frac{C}{q^n}.\tag{1}
\end{align*}

The Weierstrass Approximation Theorem states that a real continuous function on an interval can be uniformly approximated as close as desired by polynomials. That is, given a continuous real function \(f: [a,b] \rightarrow \mathbb{R}\) and an \(\varepsilon > 0\), there is a polynomial \(p(x)\) such that \(|f(x)-p(x)| < \varepsilon\) for all \(x \in [a,b]\). Weierstrass first proved this theorem in a fruitful but unintuitive way in 1885.^[1] Lebesgue's proof of 1898, presented here, takes a natural approach that Euclid would have appreciated.^[2] Weierstrass proved the theorem towards the end of his career when he was 70 years old; Lebesgue's proof was in his first published paper at the age of 23. Lebesgue stitches together three principles:

1) A continuous function on an interval can be uniformly approximated by a polygonal line.

2) A polygonal line can be represented as a constant plus a sum of functions of the form \(a|x-b|\).

3) The function \(|x|\) can be uniformly approximated by polynomials on an interval.

I'm working through the problems in this book in a (vain) attempt to prove I'm as smart as a good Soviet high school student in 1935. The complete title is The USSR Olympiad Problem Book: Selected Problems and Theorems of Elementary Mathematics, first published in English in 1962 and available in a cheap Dover reprint or at archive.org.^[1] The problems are unconventional with a pedigree going back to the 1930s and are targeted at advanced high school students — they require little to no advanced machinery, but a great deal of ingenuity to solve in most cases. I wrote up about half of them up to #106 and then skipped ahead in order to have one for each chapter to show below, always trying hard to solve a problem, maybe over days, before peeking at the hint in the back or the solution when severely pressed. The questions take up the first 73 page of the book, the solutions the last 349 pages. Sometimes a problem is just plain out of reach, even after some effort, in other cases unappetizing for some reason — only then is a look at the solution in order.

Atle Selberg (1917-2007)

In 1949, Selberg and Erdős proved the Prime Number Theorem in an elementary way based on an inequality Selberg had proved shortly before, "elementary" meaning without the machinery of complex analysis.^[1] This was notable because the theorem had first been proven by Hadamard and de la Vallée Poussin in 1896 using complex analysis and there had been doubts that an elementary proof was possible. The Prime Number Theorem states that:
\[\lim_{x \to \infty} \; \frac{\pi(x)}{x/\log{x}} = 1, \hspace{8pt} \text{ where } \pi(x) = \text{ #primes } \leq x.\]
It seemed unreasonable that such advanced methods far from basic number theory were necessary to prove a theorem about prime numbers. Selberg closed the gap in 1949 and Tatuzawa and Iseki^[1'] gave a compact proof of Selberg's Inequality in 1951, a derivation I propose to follow in this article.^[2]

P. L. Chebyshev (1821-1894)

Mémoire sur les nombres premiers^[1] is Chebyshev's great work of 1850, where he used ingenious arguments to find the order of \(\pi(x),\) the number of prime numbers less than or equal to \(x,\) and proved Bertrand's postulate, that there is always at least one prime number strictly between \(n\) and \(2n-2\) for every integer \(n > 3.\)^[2] To this end, he introduced:
\begin{align}
\theta(x) &= \sum_{p \leq x} \log{p}\\[1em]
\psi(x) &= \theta(x) + \theta\left(x^{1/2}\right) + \theta\left(x^{1/3}\right) + \ldots,
\end{align}
where the first sum is taken over all primes less than or equal to the positive real number \(x.\) Note that the second sum has a finite number of terms, since for a given \(x, x^{1/n}\) is eventually less than 2 and for such \(n, \; \theta(x^{1/n}) = 0.\)

Complex multiplication in Argand (Essai, 1806).

The Fundamental Theorem of Algebra states that every non-constant polynomial with complex coefficients has at least one root in the complex plane. The quadratic formula provides two roots for every complex quadratic polynomial, considering that every complex number has two square roots. There are similar formulas for polynomials of degree three and four, but no general formula for polynomials of degree higher than that. This theorem has a long pedigree going back to Euler and before, d'Alembert attempting a proof in 1748. Gauss is often credited with the first proof in 1799, but it was incomplete.^[1] Argand gave a simple and direct proof in 1806 in an anonymous self-published pamphlet where he showed how to represent complex numbers geometrically and took up complex addition, multiplication, division, root taking, and absolute value.^[2]

Ratdolt's Euclid of 1482, page 1. First sentence: "Punctum est cuius ps nó est."

Like the Bible, Euclid's Elements is revered as a font of ancient wisdom and has indeed served as a kind of bible for those seeking knowledge for 2300 years. The Elements is the foremost scientific text of western civilization and has been studied assiduously since the day it was written around 300 BCE, not only for its mathematical content, but also as a template for how to think clearly. It was one of the very first printed scientific works^[1] and became a foundation stone of the revival of mathematics in the Renaissance made possible by printing, vernacular as well as Latin versions falling from the presses like autumn leaves starting in earnest in the sixteenth century.^[2] Isaac Newton, for example, studied the Elements carefully and wrote the Principia very much in a Euclidean spirit, augmented by limiting processes.^[2a]

Joseph Henry Maclagen Wedderburn (1882-1948)

Wedderburn's Theorem of 1905 is a beauty, that a finite division ring is a field. The result itself, but also the proof, which surely is enrolled in The Book, Paul Erdős's whimsical imaginary list of the finest proofs in all mathematics.^[1] A division ring is a ring with a 1 in which every non-zero element has a multiplicative inverse. Add multiplicative commutativity and you have a field. The quaternions over the reals are an example of an infinite division ring that is not a field, but Wedderburn says that such an example must be infinite — there is no example of a finite division ring that is not a field. What is striking about this proof is the range of techniques it employs, including group theory, linear algebra, the cyclotomic polynomials, Euclidean geometry, and basic facts about integers and complex numbers.^[2]