Astounding “Natural” Identities

Algebra, , , , , , ,

The modest sequence \(1,2,3,4,\ldots\) can do some rather awe-inspiring things, when properly arranged. Here’s a short list of some of its many impressive feats.

There are numerous expressions for \(\pi\) relying on the progression of integers, including the Wallis formula: $$\frac{\pi}{2} = \frac{2}{1} \cdot \frac{2}{3} \cdot \frac{4}{3} \cdot \frac{4}{5} \cdot \frac{6}{5} \cdot \frac{6}{7} \cdots$$ (which can be derived from Complex Analysis using an infinite product representation for the sine function) and an elegant alternating sum: $$\frac{\pi-3}{4} = \frac{1}{2\cdot 3\cdot 4}-\frac{1}{4\cdot 5\cdot 6}+\frac{1}{6\cdot 7\cdot 8}-\cdots$$ (try to prove this!). Euler’s number \(e\) has similarly surprising formulas, such as $$\frac{1}{e-2} = 1+\frac{1}{2+\frac{2}{3+\frac{3}{4+\frac{4}{5+\cdots}}}}$$ (listed at MathWorld) and $$\frac{e}{e-1} = 1+\frac{1+\frac{1+\frac{1+\cdots}{2+\cdots}}{2+\frac{2+\cdots}{3+\cdots}}}{2+\frac{2+\frac{2+\cdots}{3+\cdots}}{3+\frac{3+\cdots}{4+\cdots}}}$$ (which is problem 1745 in Mathematics Magazine, posed by Gerald A. Edgar).

The list doesn’t stop here! The nested square-root identity $$3 = \sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1+\cdots}}}}$$ is attributed to Ramanujan (on this Wikipedia page). As another curiosity, the sequence $$\frac{1}{2},\qquad
\frac{1}{2} \Big/ \frac{3}{4},\qquad
\frac{\frac{1}{2} \big/ \frac{3}{4}}{\frac{5}{6} \big/ \frac{7}{8}},\qquad
\frac{\frac{1}{2} \big/ \frac{3}{4}}{\frac{5}{6} \big/ \frac{7}{8}} \bigg/ \frac{\frac{9}{10} \big/ \frac{11}{12}}{\frac{13}{14} \big/ \frac{15}{16}},\qquad\ldots$$ (which relates to the Thue-Morse sequence) can be shown to converge to \(\sqrt{2}/2\).

There are many pretty/unexpected/crazy formulas obtainable from the natural numbers \(1,2,3,4,\ldots\) that could not fit in this post. What are some of your favorites?

A Distinctly Odd Coincidence

Counting/Probability, Proofs, , , , , , ,

This week’s topic comes from partition theory. Consider all the ways to write 7 as the sum of positive integers:
$$\begin{align*}
&7, && 3+2+2,\\
&6+1, && 3+2+1+1,\\
&5+2, && 3+1+1+1+1,\\
&5+1+1, && 2+2+2+1,\\
&4+3, && 2+2+1+1+1,\\
&4+2+1, && 2+1+1+1+1+1,\\
&4+1+1+1, && 1+1+1+1+1+1+1+1.\\
&3+3+1, &&
\end{align*}$$ (We don’t care about order: for example, \(5+2\) and \(2+5\) are the same.) These are called the partitions of 7, and there are 15 of them.

We can also consider imposing constraints on these partitions: For example, how many of these partitions of 7 use only odd integers? These “odd” partitions are
$$\begin{align*}
& 7, && 3+1+1+1+1, \\
& 5+1+1, && 1+1+1+1+1+1+1, \\
& 3+3+1, &&
\end{align*}$$ and there are 5 of them. Here’s a very different question: how many partition of 7 have no repeated parts? These “distinct” partition are
$$\begin{align*}
& 7, && 6+1, && 5+2, && 4+3, && 4+2+1,
\end{align*}$$ and there are 5 of these as well.

This must be coincidence, right? Let’s try a bigger example. How many partitions of 11 use only odd parts? You can (and should!) check that there are 12. And how many partitions of 11 use only distinct parts? Again, there are 12. Surprisingly, these numbers will always match!:

Theorem (Euler): For any positive integer \(n\), the number of “odd” partitions of \(n\) is the same as the number of “distinct” partitions of \(n\).

Transforming Between “Odd” and “Distinct” Partitions

Let’s try to make sense of this. Given a partition of \(n\) into odd parts, there is a simple way to transform it into a partition with distinct parts: whenever two parts are the same, add them together, and repeat until they are all distinct. For example, the partition \(7+3+3+3+3+3+3+1+1+1\) of 28 is transformed into
$$\begin{align*}
& 7+(3+3)+(3+3)+(3+3)+(1+1)+1 \\
& \quad \to 7+(6+6)+6+2+1 \\
& \quad \to 12+7+6+2+1,
\end{align*}$$ which has distinct parts. In the other direction, to transform a “distinct” partition to an “odd” one, we can reverse this process: whenever there is an even part, cut it in half and write it twice. Our example \(12+7+6+2+1\) from above becomes
$$\begin{align*}
& (6+6)+7+(3+3)+(1+1)+1 \\
&\quad \to (3+3)+(3+3)+7+3+3+1+1+1,
\end{align*}$$ which is the “odd” permutation we started with. These transformations can be shown to match “odd” permutations with “distinct” permutations in pairs, proving that these sets have the same size. (A careful argument uses binary representation.) For example, the 5 partitions of 7 above are paired as follows:
$$\begin{align*}
& 7 &&\leftrightarrow && 7 \\
& 6+1 &&\leftrightarrow && 3+3+1 \\
& 5+2 &&\leftrightarrow && 5+1+1 \\
& 4+3 &&\leftrightarrow && 3+1+1+1+1 \\
& 4+2+1 &&\leftrightarrow && 1+1+1+1+1+1+1.
\end{align*}$$ (If you know something about generating functions, then a different proof follows by proving the identity
$$\frac{1}{(1-x)(1-x^3)(1-x^5)(1-x^7)\cdots} = (1+x)(1+x^2)(1+x^3)(1+x^4)\cdots$$ and noting that the coefficients of \(x^n\) in the expansions of the left and right products equals the number of “odd” and “distinct” permutations of \(n\), respectively.)

More Coincidences

These apparent coincidences are characteristic of many results in partition theory. Try your hand at proving the following generalization:

Theorem: The number of partitions of \(n\) into parts that are not divisible by 10 equals the number of partitions of \(n\) where no part is repeated 10 or more times. The same is true for any positive integer in place of 10.

(Hint: both methods used above can be extended to prove this.) If instead we want the parts to be really distinct and make sure no two parts are equal or consecutive, then we want my favorite partition theory result:

Theorem (Rogers-Ramanujan Identity): The number of partitions of \(n\) where any two parts differ by at least 2 is the same as the number of partitions of \(n\) where every part is one more or one less than a multiple of 5.

Despite the simplicity of the statement, this is much harder to prove than the previous theorems.

Secret Santa (Now with Fewer Hats!)

Counting/Probability, Proofs, , , , ,

As we approach the holiday season, some of you may soon participate in—or perhaps even organize—a “Secret Santa” exchange. Specifically, some number of people enter the exchange, and each is assigned one person (their Santee) to give a gift to (or multiple gifts… or other craziness…), in such a way that each person also receives from one person (their Santa). As organizers of such an exchange, how should we choose a permutation of the participants, i.e., an assignment of each person to his/her Santee? Here’s one method: put all names in a hat, and let each player extract a name at random. What could go wrong?

For starters, someone might pick their own name! Shopping for yourself might make the task easier, but this seems to contradict the (Christmas) spirit of the exchange. If we pick randomly as above, and if there are \(n\) people in the exchange, what is the probability that no one picks him/herself? For large \(n\), this answer tends toward \(1/e = .3679\ldots\), where \(e = 2.718\ldots\) is Euler’s number. So, with more than a 63 percent chance, someone is left out. (See below for a proof of this fact.)

What else might go wrong? Perhaps we also want to avoid two people being assigned each other, so that this pair doesn’t feel excluded. What is the chance of a randomly chosen permutation having no excluded person or pair? This can be computed to tend toward \(1/e^{3/2} = .2231\ldots\), so there is some left out person or pair with almost 80% probability. And if we wish to make sure there are no excluded groups of size at most 6, say, then the chance of failure limits to $$1-e^{-1-\frac{1}{2}-\frac{1}{3}-\frac{1}{4}-\frac{1}{5}-\frac{1}{6}} = .9137$$ for large \(n\).

So, while Santa hats may be fluffy and festive, Secret Santa hats are a bad idea. What should we do to organize our exchange? Here’s one option: just make a big cycle. Specifically, write all names in some random order and chain them up, e.g., \(2\to 6\to 7\to 3\to 1\to 4\to 5\to 2\) (if the “names” are just 1, 2, …, 7).

Where do these numbers come from?

How can we compute the probabilities mentioned above? One common method to prove the \(1/e\) probability uses the principle of Inclusion-Exclusion, but here is a sketch of an argument that doesn’t rely on this technique. Let \(A_n\) be the number of permutations of \(n\) people with no person assigned to him/herself. Such a permutation is called a Derangement, and a direct counting argument can be used to show that \(A_n = (n-1)(A_{n-1} + A_{n-2})\) (see the Wikipedia page for derangements, for example). As there are \(n!\) total permutations of the players, the desired probability is \(P_n = A_n/n!\), so the above formula can be manipulated to \(P_n-P_{n-1} = -\frac{1}{n}(P_{n-1}-P_{n-2})\). This produces \(P_n-P_{n-1} = \frac{(-1)^n}{n!}\) by induction, so we obtain $$P_n = 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+\frac{(-1)^n}{n!}.$$ As \(n\) gets big this value tends toward the infinite sum \(\sum_{i=0}^\infty \frac{(-1)^i}{i!} = 1/e\).

The other probabilities mentioned take more work. A well-suited tool is that of (Exponential) Generating Functions, which in this case help organize a more complicated Inclusion-Exclusion argument. Using these, it can be shown that the probability that a random permutation of \(n\) players has no groups of size 6 or less is equal to the coefficient of \(x^n\) in the power series expansion of $$\frac{1}{1-x}\cdot e^{-\left(x+\frac{x^2}{2} + \cdots + \frac{x^6}{6}\right)}.$$

Some Strange Sums

Calculus/Analysis, Proofs, , , ,

If someone told you to compute the value of the infinite sum \(Z = 1+2+3+4+\cdots\), you would tell them that it simply does not converge. But what if they insisted that you assign a finite value to this sum? Which value would you give? Is there any way to make sense of this question? Yes, and the answer is \(-1/12\).

Before tackling this sum, let’s try a slightly easier one, known as Grandi’s Series: \(G = 1-1+1-1+\cdots\). How can we compute its value? Let’s write $$\begin{align*}G &= 1-1+1-1+1-\cdots \text{ and}\\ G &= 0+1-1+1-1+\ldots,\end{align*}$$ and adding these term by term gives \(2G = 1+0+0+0+0+\cdots = 1\), i.e., \(G = 1/2\). So we got a value! The same “trick” lets us sum \(H = 1-2+3-4+\cdots\) like this: $$\begin{align*}2H &= 1 + (-2+1) + (3-2) + (-4+3) + \cdots\\ &= 1-1+1-1+\cdots\\ &= G = 1/2,\end{align*}$$ so \(H = 1/4\).

What’s really going on here? A good way to understand it is to look at the functions \(g(x) = 1-x+x^2-x^3+\cdots\) and \(h(x) = 1-2x+3x^2-4x^3+\cdots\), and to realize that we’re asking for \(g(1)\) and \(h(1)\), respectively. The sum defining \(g(x)\) converges for \(-1 < x < 1[/latex], and since [latex]g(x) + x \cdot g(x) = 1[/latex] (this is just the "trick" from above!), we find [latex]g(x) = 1/(1+x)[/latex]. So, even though the sum defining [latex]g(1) = 1-1+1-\cdots[/latex] does not converge, the limit as [latex]x[/latex] approaches 1 from below is well defined and equals [latex]1/(1+1) = 1/2[/latex]. Likewise, we find that [latex]h(x) = 1/(1+x)^2[/latex] for [latex]-1 < x < 1[/latex], and the limit as [latex]x[/latex] goes to 1 is 1/4. This method of putting the terms as the coefficients of a power series and extrapolating with limits is called Abel Regularization. Notice, however, that this method does not work for the sum [latex]Z\), because \(1 + 2x + 3x^2 + 4x^3 + \cdots = 1/(1-x)^2\), and the limit as \(x\) approaches 1 is still infinite.

A different method of summing divergent series is called Zeta Function Regularization: to compute \(a_1 + a_2 + a_3 + \cdots\), define the function \(a_1^{-s} + a_2^{-s} + a_3^{-s} + \cdots\) (which hopefully converges for large enough s), and try to “extend” this to a function we can evaluate at \(s=-1\). For example, for \(H = 1-2+3-\cdots\), the corresponding function \(1/1^2-1/2^s+1/3^s-\cdots\) is called the Dirichlet Eta Function, \(\eta(s)\). Analysis based on our “trick” from above (iterated infinitely many times! [producing the so-called Euler Transform]) can be used to show that \(\eta(s)\) can be defined for all values \(s\) (even complex values!) and that \(\eta(-1) = 1/4\), which agrees with our computation of \(1-2+3-4+\cdots\) above. The corresponding function for the sum \(Z\) is called the Riemann Zeta Function, \(\zeta(s)\), and we can compute (for all \(s\) where this makes sense): $$\begin{gather*}
\zeta(s) = \frac{1}{1^s} + \frac{1}{2^s} + \frac{1}{3^s} + \frac{1}{4^s} + \cdots,\\
2^{-s} \zeta(s) = \frac{1}{2^s} + \frac{1}{4^s} + \frac{1}{6^s} + \frac{1}{8^s} + \cdots, \text{ and so}\\
\zeta(s)-2\cdot 2^{-s} \zeta(s) = \frac{1}{1^s}-\frac{1}{2^s}+\frac{1}{3^s}-\frac{1}{4^s}+\cdots = \eta(s).\end{gather*}$$ So \((1-2^{1-s}) \zeta(s)\) equals \(\eta(s)\) everywhere (by general complex analysis facts). At \(s = -1\), this says \(\zeta(-1) = \eta(-1)/(-3) = -1/12\), as claimed.

A “Frac”ing Prime Generator

Computer Science, Number Theory, , ,

Last week we saw a few ways to (try to) generate prime numbers with simple formulas. I will now describe a much more puzzling (and recreational) method. The following numbers specify everything you need: $$\left(\frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{14}, \frac{15}{2}, \frac{55}{1} \right).$$ To run this “game,” the rules are as follows: Start with value \(v = 2\). At each step, find the first fraction \(f\) in the list so that \(v \cdot f\) is an integer, and replace the value \(v\) by this integer. Repeat indefinitely (or until no such \(f\) can be found). The beginning of the computation looks like this:

  1. Start with value \(v = 2\).
  2. The first fraction \(f\) in the list such that \(2\cdot f\) is an integer is \(f=15/2\), so the new value \(v\) is \(2 \cdot 15/2 = 15\).
  3. The first \(f\) in the list with \(15 \cdot f\) an integer is \(f=55/1\), so the new \(v\) is \(15 \cdot 55/1 = 825\).
  4. The first \(f\) with \(825 \cdot f\) an integer is \(29/33\), so set \(v = 825 \cdot 29/33 = 725\).

And so on.

Continuing as above, the list of values looks like 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30, 225, 12375, … .

But what does this have to do with primes? The list of fractions was carefully constructed so that many powers of 2 will appear, in exactly the following order: $$2^1, 2^2, 2^3, 2^5, 2^7, 2^{11}, 2^{13}, 2^{17}, \ldots .$$ Indeed, except for \(2^1\) (the starting value), any power of two obtained by this process will have a prime exponent, and all primes will appear in this way (in order)! This is a very special property of the chosen list of fractions, and different lists give rise to vastly different output sequences.

In fact, you can think of this procedure as a programming language, where the list of fractions and the starting value constitute your “program.” This language is called FRACTRAN, and both the language and the above prime-enumerating program were designed by John Conway. What else is this language capable of computing? Lots! FRACTRAN can compute anything that modern computers could—but much less efficiently. (In Theoretical Computer Science terminology, FRACTRAN is turing complete.) See the Wikipedia page for more information, as well as an explanation of why the above program works.

Generating Primes with Formulas

Algebra, Number Theory, Proofs, , , ,

Prime numbers—namely, positive integers with no divisors other than 1 and themselves—have long fascinated mathematicians. As a result, there have been many attempts at formulas to generate prime numbers. For example, the polynomial \(x^2-x+41\) spits out a prime number for \(x = 0, 1, 2, …, 40\). But for \(x = 41\), the value is \(41^2\), which is not prime. Can we find some nonconstant polynomial \(f(x)\) with integer coefficients that only spits out prime values? (The constant polynomial \(f(x) = 2\) always returns a prime, but this is not very interesting.) In a word: No. There is no such polynomial. To prove this, assume \(f\) is such a polynomial. Then \(f(0) = p\) for some prime \(p\), and all of the numbers \(\{f(p), f(2p), f(3p), \ldots \}\) are divisible by \(p\). This sequence grows toward infinity, so one of them is greater than \(p\). Since this number has a factor of \(p\), it is not prime.

What if we switch from polynomials to exponents? Maybe the function \(2^m + 1\) will give us lots of primes. It can be shown that if \(2^m + 1\) is prime then \(m\) itself has to be a power of 2. (Indeed, if a prime \(p > 2\) divides \(m\), check that \(2^{m/p} + 1\) divides \(2^m + 1\).) So the only possibilities are the numbers \(F_n = 2^{2^n} + 1\), which are called Fermat numbers. The first few are $$\begin{align*}
F_0 &= 3,\\
F_1 &= 5,\\
F_2 &= 17,\\
F_3 &= 257,\\
F_4 &= 65537.
\end{align*}$$ It was long believed that all Fermat numbers were prime (Fermat himself conjectured this!), but in fact the very next one, \(F_5 = 4294967297 = 641 \cdot 6700417\), is composite. (In Fermat’s defense, this is a large number to factor by hand!) Are there at least infinitely many Fermat primes? We currently don’t know. In fact, the Fermat primes shown above are the only known Fermat primes!

Similarly, numbers of the form \(2^n-1\) are called Mersenne numbers. In order for this to be prime, it is necessary for \(n\) itself to be prime. (Indeed, if \(a\) divides \(n\) then \(2^a-1\) divides \(2^n-1\).) So is \(2^p-1\) prime for every prime \(p\)? Unfortunately, no: \(2^{11}-1\) is not prime. But there seem to be many Mersenne primes. Thanks to the “Great Internet Mersenne Prime Search,” a.k.a. GIMPS, there are 47 Mersenne primes known, the largest of which is \(2^{43112609}-1\), which has 12978189 digits (in base 10).

OK, so the above “prime-generating” functions don’t work very well. Here’s one that does work. It can be shown that there is some polynomial \(Z(a, b, c, d, e, f, g, h, i, j)\) with 10 variables and integer coefficients such that any positive output from \(Z\) (when given integer inputs) is prime, and furthermore, every prime is obtained in this way. (Note: \(Z\) spits out many non-positive values as well.) Unfortunately, this polynomial \(Z\) is not very practical. For one thing, its degree is about \(38!\). (Yes, I mean 38 factorial.)

“Read Backwards” Month

Games/Experiments, Number Theory, , , ,

There are quite a few beautifully symmetric dates that present themselves this month, including 11/1/11, 11/02/2011, 11/05/2011 (use a mirror!), 11/11/11, and 11/22/11. In honor of this phenomenon, I want to say a few words about palindromes, which are simply things that read the same backwards as forwards. A few famous examples include “racecar,” “Never odd or even,” “I prefer pi”, “Dr. Awkward”, “Aibohphobia” (which means fear of palindromes [I didn’t make this up!]), “Go hang a salami; I’m a lasagna hog!”, or if you read by word instead of by letter, “Blessed are they that believe that they are blessed.”

If we consider digits instead of letters or words, then numbers such as 676, 100020001, and 12345678987654321 are palindromes. These are in fact quite special palindromes, as they are all squares of integers: \(26^2 = 676\), \(111111111^2 = 12345678987654321\), and \(10001^2 = 100020001\). Are there infinitely many palindromic squares? Yes: the last example above hints that \(10\ldots01^2 = 10\ldots020\ldots01\) for however many 0s you put in the middle. By contrast, if we ask for \(n^5\) to be palindromic (or any higher power), then no solutions are currently known!

You might ask for other types of palindromic numbers, such as palindromic primes. A few examples include 7 (this is a palindrome!), 101, 19391, and 1000000008000000001. Are there infinitely many? We don’t know. But the largest palindromic prime currently known is \(10^{200000} + 47960506974 \cdot 10^{99995} + 1\), according to Wikipedia.

For one more game, here’s a way to make palindromes out of non-palindromes. Start with a non-palindrome, like 86, and keep adding it to its reversal until you get a palindrome: e.g., 86+68 = 154, 154+451 = 605, and 605+506 = 1111, which is a palindrome. How quickly will this terminate? Well, try starting with 89 and see how long it takes! (Answer: it finally stops at a 13-digit palindrome.) But surely it always terminates eventually, right? Surprisingly, the answer to this question is currently unknown. In fact, it is unknown if the sequence starting at 196 ever finds a palindrome!

Finally, if you still want more to think about, try repeating this entire discussion in another base, e.g. base 2. Good luck!

All Your Base (Jokes)

Computer Science, Number Theory, , , ,

There’s something unsatisfyingly arbitrary about the number 10. When we write numbers, e.g. 1729, our notation means that we have 1 thousand (\(10^3\)), 7 hundreds (\(10^2\)), 2 tens (\(10^1\)), and 9 ones (\(10^0\)), so the number 10 is ingrained in our very writing system. And it’s not just the Arabic numeral system: Roman numerals also organize themselves around powers of 10 (such as I=1, X=10, C=100, etc.). But why 10? (Other than the fact that we usually have 10 fingers and 10 toes [why not 20 instead?].)

Our “decimal” system centers around powers of 10, but there are other equally useful systems based on other numbers. For example, we could use sums of powers of 2, and instead of needing 10 digits (0,1,…,9) we can use just 2, namely 0 and 1. For example, the number 1101 in base 2 means \(1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0\), also known as 13 in base 10. This may seem inefficient, since we need more digits (or, more correctly, “bits” in the binary setting) to express the same value, but it has many benefits. Each bit has only 2 choices, and can therefore be represented by a pair of opposites such as “on/off” (e.g. in circuits) or the two magnetic polarities. The latter is how hard drive disks store information (in binary!), which is one reason this system is beloved by computer scientists. It also allows for jokes like this: “There are 10 types of people in the world: those that understand binary, and those that don’t.”

Another common base is Hexadecimal, using powers of 16 with digits 0,…,9,A,B,C,D,E,F. (A hexadecimal digit is sometimes called a “nibble”.) It is common to prefix a hexadecimal number with “0x”, so 0x3B7 means \(3 \cdot 16^2 + 11 \cdot 16 + 7 = 951\) in decimal. It also makes the phrase “I see 0xDEAD people” perfectly reasonable (how many is that?).

But there are more possibilities still! For example, the octal system uses powers of 8 and (octal) digits 0,…,7. With this we can prove Christmas and Halloween are really the same holiday: indeed, Dec 25 = Oct 31. And don’t miss the octal system’s cameo in Tom Lehrer’s New Math song.

The possibilities are endless! We can use base \(n\) for any positive integer \(n>1\) in similar ways, but we can also use negative \(n\) as well! (My favorite is base -4.) If you want to go ever further, think about what base \((1+\sqrt{5})/2\) (a.k.a. phinary) would look like! Or the related bases Fibonacci and NegaFibonacci!

Kissing Spheres

Geometry, Math History, , , ,

If you put a quarter flat on a table, you can surround it with six other quarters that all touch the original. Is this the best you can do, if the coins can’t overlap? Well, yes: the coins are packed as tightly as possible, so there is no room for a seventh coin to fit around the middle one. We call this the Kissing Number Problem, and it gets much more interesting if you jump from two dimensions to three: given a sphere of radius 1, how many nonoverlapping spheres (of radius 1) can you place around it such that they all “kiss” the original sphere? Said differently, what is the kissing number in 3 dimensions?

Here’s a pretty good attempt: If you put one sphere at each vertex of a cuboctahedron like this,

Twelve spheres all kissing a central (blue) sphere and arranged at the vertices of a cuboctahedron.
Twelve spheres all kissing a central (blue) sphere and arranged at the vertices of a cuboctahedron.

you’ll end up with 12 that seem pretty tightly packed. In another try, you could put a sphere at each vertex of an icosahedron:

Twelve spheres all kissing a central (blue) sphere and arranged at the vertices of an icosahedron.
Twelve spheres all kissing a central (blue) sphere and arranged at the vertices of an icosahedron.

You’ll again get 12, but this time there is noticable wiggle room to move the spheres without losing contact with the central sphere—so much wiggle room, in fact, that any two spheres can switch places! Is there enough extra space for a 13th sphere to fit? This was a topic of heated debate between Isaac Newton and David Gregory (who believed 12 and 13, respectively), but it was not resolved until much later, in 1953, in favor of Newton’s 12. The proof is highly nontrivial.

What about still higher dimensions? What is the kissing number in four dimensions? (What does a 4-dimensional sphere even look like? Perhaps a topic of a future post…) This too is known, and the answer is 24—the proof is again quite difficult. See if you can figure out the arrangement! What about dimension 5, 6, 7, … ? As might be expected, the problem gets even harder in higher dimensions, and no other exact kissing numbers are known—except for two. Due to some veritable mathematical miracles (namely, the highly symmetric structures called the E8 lattice and the Leech lattice), the kissing numbers in dimensions 8 and 24 have been shown to be 240 and 196560, respectively.

Teach an Old Dog New Trigs

Geometry, Trigonometry, , , , ,

If you studied your Trig tables in high school, you probably remember some facts like $$\begin{align*}
\cos(30) &= \sqrt{3}/2,\\
\cos(45) &= \sqrt{2}/2, \text{ and}\\
\cos(60) &= 1/2.
\end{align*}$$ With a few formulas you can get at a few more angles, e.g., $$\cos(15) = \cos(45 – 30) = \cos(45) \cos(30) + \sin(45) \sin(30) = \frac{ \sqrt{6} + \sqrt{2} }{4},$$ and likewise \(\cos(75) = (\sqrt{6} – \sqrt{2})/4\).

I now offer two more angles that are not as straightforward but nevertheless have surprisingly nice trig values: 18 and 36. Specifically, we have $$\cos(36) = \frac{1 + \sqrt{5}}{4} = \frac{\phi}{2}, \text{ and }
\sin(18) = \frac{-1 + \sqrt{5}}{4} = \frac{1}{2 \phi},$$ where \(\phi = (1 + \sqrt{5})/2\) is the golden ratio. Try to prove these! (Here’s a hint: Draw a 36-72-72 triangle, and bisect one of the large angles to form a 36-36-108 triangle and a smaller 36-72-72 triangle. Both are isosceles! And one of them is similar to the original triangle!)

You may ask for which other angles we can get “nice” answers. Well, this at least lets us get 18 – 15 = 3 degrees, and therefore any multiple of 3 degrees, as long as we don’t mind multiply nested square roots. But if we’re allowing this then there are even more! For example, Gauss showed that $$\begin{align*}\cos(360/17) &= \frac{1}{16}\bigg( -1 + \sqrt{17} + \sqrt{34-2 \sqrt{17}} \\
& \qquad {} + 2 \sqrt{ 17 + 3 \sqrt{17} – \sqrt{34-2 \sqrt{17}} – 2 \sqrt{34+2 \sqrt{17}} } \bigg),\end{align*}$$ and there are similar (lengthier!) formulas for \(\cos(360/257)\) and \(\cos(360/65537)\) using just nested square roots. Why these denominators? You’ll have to ask our friends Fermat and Galois.