Some rather large (counter)examples

The coming of the computer era has led to some people outsourcing their thinking to silicon. This can turn up results, but don't be fooled into believing this is a substitute for having ideas. Nonetheless, brute force sometimes turns up things which one simply couldn't hope to find by hand, and these things are still good to know. In this spirit, let us see what sort of funny and noteworthy counterexamples have turned up. Most of these will be of a number-theoretic nature, because there are just so many conjectures there, waiting to be answered.

Some large counterexamples:

1. Conjecture: $n^{17}+9$ and $(n+1)^{17}+9$ are relatively prime.
   The first counterexample is $n=8424432925592889329288197322308900672459420460792433$
2. Euler's sum of powers conjecture: If the equation $\sum_{i=1}^kx_i^n=z^n$ has a solution in positive integers, then $n \leq k$ (unless $k=1$). Fermat's Last Theorem is the $k=2$ case of this conjecture.
   A counterexample for $n=5$ was found in 1966: it's  $$61917364224=27^5+84^5+110^5+133^5=144^5 $$. The smallest counterexample for $n=4$ was found in 1988:  $$ 31858749840007945920321 = 95800^4+217519^4+414560^4=422481^4 $$
3. Merten's conjecture: a now disproved conjecture about a function $M(n)$, the Merten function, being bounded by $\sqrt{n}$. If true, it would imply the Riemann hypothesis. The first counterexample is known to be $>10^{16}$.
4. Skewes' number: the smallest integer for which the prime counting function exceeds $\mathrm{li}(x)$. The exact value is unknown but the bounds are ridiculously big. 
5. The Pólya conjecture: for any $n > 1$, if the natural numbers less than or equal to $n$ are partitioned into those with an odd number of prime factors and those with an even number of prime factors, then the former set has at least as many members as the latter set. The conjecture fails to hold for most values of n in the region of 906,150,257 ≤ n ≤ 906,488,079, and the lower bound is in fact the smallest counterexample.

Items 3 and 4 have numberphile videos about them. All this goes to show that one should be a little careful about accepting things are true based solely on computational evidence.

Some extremely sporadic counterexamples:

The items here are taken from these two MSE questions:

1. For squarefree positive integer $d$, every imaginary quadratic field $\mathbb{Q}(\sqrt{−d})$ has class number greater than 1 unless $d$ is equal to one of the Heegner numbers: 1, 2, 3, 7, 11, 19, 43, 67, 163.
2. Let $G$ be a finite group and $p,q$ primes dividing $|G|$.  If $G$ contains no element of order $pq$, then either 
   a. the Sylow $p$-subgroups or the Sylow $q$-subgroups are abelian, or
   b. $G/O_{\{p,q\}'}(G)$ is the Monster and $\{p,q\}=\{5,13\}$ or $\{7,13\}$.
3. Mihailescu's theorem (formerly the Catalan conjecture): The only consecutive positive integer powers are 8 and 9.
4. There are no positive integers $a \neq b$ such that $a^b = b^a$, with the exception of $2^4=4^2$.
5. For $n \geq 0$, the commutator subgroup of the general linear group $\mathrm{GL}_n(K)$ is always the special linear group $\mathrm{SL}_n(K)$, with the exception of $n=2$ and $K=\mathbb{F}_2$. See here for a proof.
6. There is exactly one case where consecutive binomial coefficients form a Pythagorean triple and the proof is completely elementary.
7. No number is equal to the sum of the subfactorials of its digits, apart from $148349=!1+!4+!8+!3+!4+!9$. 
   The subfactorial $!n$ is the number of *derangements* of a set of $n$ elements, that is, the number of permutations $\rho$ of the set with no $x$ such that $\rho(x)=x$. Values are tabulated, with scads of information, at https://oeis.org/A000166. The result is attributed to Madachy, J. S., Madachy's Mathematical Recreations. New York: Dover, p. 167, 1979.

Our final example, which we will actually say something about, is the cannonball problem: given a square arrangement of cannonballs, for what size squares can these cannonballs also be arranged into a square pyramid? Equivalently, which squares can be represented as the sum of consecutive squares, starting from 1? or equivalently yet, solve in integers $ {\frac {1}{6}}N(N+1)(2N+1)={\frac {2N^{3}+3N^{2}+N}{6}}=M^{2}.$ The original proofs that the only solution is $N = 24, M = 70$ were rather involved, but a substantially shorter and completely elementary proof of this was given by Ma Degang. I include the proof sketch here for the benefit of those who can't read Chinese. Anglin later gave another elementary proof.

Proof: We solve the equivalent equation \[6y^2=x(x+1)(2x+1)\]. One checks easily that $x, x+1, 2x+1$ have to be coprime. This implies that each of these is a square times some factor to account for the factor of 6 on the LHS. We distinguish the cases when $x$ is odd and even. After some amount of case bashing modulo 2 and modulo 3, the problem of solving the Diophantine equation can be reduced to finding common solutions of the Pell systems:

\[
\begin{cases}
2y_1^2 - 3y_3^2 = -1, \\
4y_2^2 - 3y_3^2 = 1,
\end{cases} \tag{2}
\]
where \( x = y_1^2, x + 1 = 2y_2^2, 2x + 1 = 3y_3^2, y = y_1y_2y_3 \) (this is the odd case), and

\[
\begin{cases}
y_2^2 - 24y_1^2 = 1, \\
y_3^2 - 48y_1^2 = 1,
\end{cases} \tag{3}
\]
where \( x = 24y_1^2, x + 1 = y_2^2, 2x + 1 = y_3^2, y = 2y_1y_2y_3 \)(this is the even case).

Let \( \varepsilon = 2 + \sqrt{3} \) be the fundamental solution of the Pell equation \( x^2 - 3y^2 = 1 \), with \( \varepsilon^{-1} = 2 - \sqrt{3} \), and \( U_n = \frac{\varepsilon^n + \varepsilon^{-n}}{2} \). We obtain from equations (2) and (3) respectively the relations:
\[
4y_1^2 = U_n - 3 \tag{4}
\]
and
\[4y_2^2 = U_n + 3, \tag{5}\]

Using the properties of \( U_n \) and classifying modulo 20, we prove that equation (4) has only the solution \( n = \pm 2 \), and equation (5) has only the solution \( n = \pm 4 \). That is, equation (4) has only the solution \( y_1^2 = 1 \), and equation (5) has only the solution \( y_2^2 = 25 \). This proves that equation (1) has only the non-trivial solution \( x = 24, y = 70 \). $\blacksquare$

The wikipedia page lists variants of this problem which have also been solved. I assume by similar techniques but I can't be bothered to actually read the proofs. A triangular-pyramid version of the cannonball problem, which is to yield a perfect square from the Nth tetrahedral number, would have N = 48. That means that the (24 × 2 = ) 48th tetrahedral number equals to 19600. This is comparable with the 24th square pyramid having a total of 702 cannonballs. This is because a square pyramidal number is one-fourth of a larger tetrahedral number (meaning the points from four copies of the same square pyramid can be rearranged to form a single tetrahedron with twice as many points along each edge). Similarly, a pentagonal-pyramid version of the cannonball problem to produce a perfect square, would have $N = 8$, yielding a total of (14 × 14 = ) 196 cannonballs.

The only numbers that are simultaneously triangular and square pyramidal are 1, 55, 91, and 208335. There are no numbers (other than the trivial solution 1) that are both tetrahedral and square pyramidal.

While this is a numerical curiosity, it is also much more than that. Recall that a lattice in Euclidean space $\mathbb{R}^n$ is a discrete subgroup with finite covolume. All of these in fact give rise to a torus quotient. The case of integral lattices, i.e. when the generators all have integer entries, is particularly interesting. Another property that a lattice $L$ can have is being "even", that is, for any $x$ in $L$ the inner product $x.x$ is even. This implies that $L$ is integral, by the identity

\[(x + y).(x + y) = x.x + 2x.y + y.y\]

Even more interesting is when $L$ is "unimodular". There are different equivalent ways to define this concept.  

• The volume of each lattice cell is 1.
• Take any basis of $L$, and make a matrix with the components of these vectors as rows. Then take its determinant. That should equal plus or minus 1. 
• We can define the "dual" of $L$, say $L*$, to be all the vectors $x$ such that $x.y$ is an integer for all y in L. An integer lattice is one that's contained in its dual, but $L$ is unimodular if and only if $L = L*$. Hence people also call unimodular lattices "self-dual".

It's a fun little exercise in linear algebra to show that all these definitions are equivalent. Now something cool happens: even unimodular lattices are only possible in certain dimensions - namely, dimensions divisible by 8. 

In dimension 8 there is only one even unimodular lattice (up to isometry), namely the wonderful lattice $E_8$! The easiest way to think about this lattice is as follows. Say you are packing spheres in $n $ dimensions in a checkerboard lattice - in other words, you color the cubes of an n-dimensional checkerboard alternately red and black, and you put spheres centered at the center of every red cube, using the biggest spheres that will fit. There are some little hole left over where you could put smaller spheres if you wanted. And as you go up to higher dimensions, these little holes gets bigger! By the time you get up to dimension 8, there's enough room to put another sphere of the same size in each hole! If you do that, you get the lattice $E_8$. Many exotic objects in mathematics come from things related to this lattice, for instance isospectral manifolds, originally due to Milnor, or manifolds which don't carry a smooth structure, alluded to in an earlier blog post.

In dimension 16 there are only two even unimodular lattices. One is $E_8 \oplus E_8$. A vector in this is just a pair of vectors in $E_8$. The other is called $D_{16}^+$, which we get the same way as we got $E_8$: we take a checkerboard lattice in 16 dimensions and stick in extra spheres in all the holes. More precisely, to get $E_8$ or $D_{16}^+$, we take all vectors in $\mathbb{R}^{8}$ or $\mathbb{R}^{16}$, respectively, whose coordinates are either all integers or all half-integers, for which the coordinates add up to an even integer.  There are at least 80 million even unimodular lattices in 32 dimensions, and the count only explodes even faster in higher dimensions. However, dimension 24 is still tractable and extremely interesting.

Well, in dimension 24, there are 24 even unimodular lattices, which were classified by Niemeier. A few of these are obvious, like E8 + E8 + E8 and E8 + D16+, but the coolest one is the "Leech lattice", which is the only one having no vectors of length 2. This is related to a whole WORLD of bizarre and perversely fascinating mathematics, like the "Monster group", the largest sporadic finite simple group - and also to string theory. I said a bit about this stuff in "week66", and I will say more in the future, but for now let me just describe how to get the Leech lattice.

First of all, let's think about Lorentzian lattices, that is, lattices in Minkowski spacetime instead of Euclidean space. The difference is just that now the dot product is defined by

\[(x1,...,xn) \dot (y1,...,yn) = - x1 \dot y1 + x2 \dot y2 + ... + xn \dot yn\]

with the first coordinate representing time. It turns out that the only even unimodular Lorentzian lattices occur in dimensions of the form $8k + 2$. There is only one in each of those dimensions, and it is very easy to describe: it consists of all vectors whose coordinates are either all integers or all half-integers, and whose coordinates add up to an even number. Now, as the only solution to the cannonball problem, we get that the vector

             \[  v = (70,0,1,2,3,4,...,24) \]

satisfies $v \dot v = 0$. What this implies is that if we let $T$ be the set of all integer multiples of $v$, and let $S$ be the set of all vectors x in our Lorentzian lattice with $x\dot v = 0$, then $T$ is contained in $S$, and $S/T$ is a 24-dimensional lattice - the Leech lattice!

I hope to return to the Leech lattice and its connections to all sorts of incredible mathematics like sphere packing, algebraic coding theory, and monstrous moonshine at some point. It suffices to say, when trying to convey how interesting this is in mathematics, that (at least) two Fields medals have been awarded for work on related topics. See Baez's Week95 for the connections to physics.