# Accidents of small $n$

In studying mathematics, I sometimes come across examples of general facts that hold for all $n$ greater than some small number. One that comes to mind is the Abel–Ruffini theorem, which states that there is no general algebraic solution for polynomials of degree $n$ except when $n \leq 4$.

It seems that there are many interesting examples of these special accidents of structure that occur when the objects in question are "small enough", and I'd be interested in seeing more of them.

• Related, maybe even a duplicate: math.stackexchange.com/questions/111440/… – Asaf Karagila Aug 2 '12 at 21:52
• I don't think they're the same question. The one you linked is about large counterexamples, this is about small ones. – SiliconCelery Aug 2 '12 at 21:57
• @SiliconCelery: All finite numbers are small, merely by the virtue that there are only finitely many smaller. For some people even countable sets are small and when talking about things like Woodin cardinals then pretty much every feasible set is nothing more than a tiny speck of insignificance. – Asaf Karagila Aug 2 '12 at 22:40
• $\mathbb R^n$ remains connected after the removal of a point, unless $n=1$. I'm sure I don't understand the question. – user856 Aug 2 '12 at 22:45
• This is something like mathoverflow.net/questions/101463/…, e.g., there is no number $n$ whose every prefix is prime except when $n\le73939133$. – Gerry Myerson Aug 2 '12 at 23:50

You might enjoy the article The Strong Law of Small Numbers by Richard K. Guy.

He has other publications in which he partly recycles the title.

Another accident of small dimension: in all dimensions $\gt 4$, there are only three regular polytopes: the simplex, hypercube, and cross-polytope (the dual of the hypercube). In two dimensions there are infinitely many (all of the $n$-gons); in three dimensions you have two additional polyhedra, the dodecahedron and icosahedron; and in four dimensions there are three additional ones, the 120-cell and 600-cell (which are dual to each other) and the 24-cell (which is self-dual).

• Thank you, this is a very nice example. – Will Aug 3 '12 at 15:16

The 26 sporadic groups is also an "accidental" occurrence. Since there is a finite number of them, after some large N, all the simple groups of order N or larger fit into a given category.

• This is probably my favorite. Though it's perhaps strange to think of the Monster as a coincidence of small order. :) – anon Aug 3 '12 at 3:40

The outer automorphism group of $S_n$ is trivial, except when $n=6$.

• This is probably the "funniest" case that I know of, how it just "randomly" fails for 6. – tomasz Aug 3 '12 at 17:44
• Out(S2)=1 is still trivial, it just isn't equal to S2. – Jack Schmidt Aug 3 '12 at 19:44

The $n^\mathrm{th}$ cyclotomic polynomial is the minimal polynomial whose roots are the primitive $n^\mathrm{th}$ roots of unity, that is

$$\Phi_n(X) = \prod_{ {0\leq j < n} \atop {\gcd(j,n)=1}}(X - e^{2\pi i j / n})$$

The first few examples are: $$\Phi_1(X) = X - 1$$ $$\Phi_2(X) = X + 1$$ $$\Phi_3(X) = X^2 + X + 1$$

For all $n$ small enough, all the coefficients are $\pm 1$ or $0$. But if at least three odd primes divide $n$ (which requires at least $n\geq3\cdot5\cdot7 = 105$), other coefficients are possible.

The alternating group $A_n$ is simple for $n\neq 4$.

This is related to the example given by the thread creator since it allows $S_4$ to be solvable, thus guaranteeing that all polynomials of degree $4$ or less are resolvable with only the field operations plus the extraction of roots.

• Related: the symmetric group $S_n$ has only one nontrivial proper normal subgroup ($A_n$) ... except when $n=4$. – MJD Feb 3 at 14:09

Deciding whether a graph is $2$-colorable has an obvious polynomial-time algorithm.

Deciding whether a graph is $k$-colorable for $k \geq 3$ is already NP-Complete!

• Also works for $2-SAT$ and $3-SAT$ – Belgi Aug 2 '12 at 22:32
• And two-dimensional matching (P) versus three-dimensional matching (NP-complete); also exact cover by 2-sets (P) versus exact cover by 3-sets (NP-complete). – MJD Aug 3 '12 at 1:53
• There's a lot of structure in the 'booleanness' of two, in particular arguably the fact that $S_2$ is abelian (and so one can rearrange products of elements of $S_2^n$ arbitrarily), that tends to make all of these problems 'easy' for $n=2$. – Steven Stadnicki May 25 '14 at 19:00

Similar to the answer about the $26$ sporadic groups and nontrivial $\mathrm{Out}(S_n)$ for $n=2,6$, there are a bunch of what are called exceptional isomorphisms that occur with low order/dimension. Basically, groups come in all sorts of special families (where there is a rule designating what groups are in the family and why) that are infinite, but these infinite families share a few finite cases between them.

Orthogonal Latin squares exist for every order except 2 and 6. Euler conjectured from the small examples that they existed for any order not of the form $4k+2$, but he was mistaken.

$\mathbb{R}^n$ has a unique smooth structure except when $n=4$. Furthermore, the cardinality of [diffeomorphism classes of] smooth manifolds that are homeomorphic but not diffeomorphic to $\mathbb{R}^4$ is $\mathfrak{c}=2^{\aleph_0}$.

I would include in this list a discussion of $G(n)$ and $g(n)$ in the Waring Problem.

The point is that when it comes to representing integers as sums of powers of non-negative integers, it seems to happen that some (smallish) integers require more powers to represent them due to some some (presumably unknown) peculiarity of small integers.

For example, in the case of representing integers as sums of cubes, it has been proved that 9 cubes are sufficient, and some numbers require 9, so that $g(3)=9$.

On the other hand, calculations suggest that almost all numbers from some point onwards are sums of at most 4 cubes (so that $G(3)$ might be 4, but this is not proved), and it appears that it is an "accident of small $n$" that there are some (smallish) numbers which require more than 4 cubes.

• The 'pecularity' of small integers for Waring's problem is presumably just that there aren't enough of them to go around; for large numbers there are so many possible cubes to consider for expressing them as sums of $k$ cubes that at least one combination 'should' fit, but for smaller $n$ the number of possibilities for a fit is so much smaller that it's unsurprising when some numbers don't fit at all. – Steven Stadnicki Aug 3 '12 at 0:19
• You are probably right - I had always assumed it was something to do with quirks of small numbers, but your explanation seems more likely. – Old John Aug 3 '12 at 7:15

The ring of integers of $\mathbf{Q}[\sqrt d]$ is a principal ideal domain for $1 \leq d < 10$, but not for $d=10$.

• $2\times5=(4+\sqrt6)(4-\sqrt6)$. – Gerry Myerson Aug 4 '12 at 2:33
• Bruno, $(4+\sqrt6)(4-\sqrt6)=4^2-\sqrt6^2=16-6=10=2\times5$. – Gerry Myerson Aug 4 '12 at 5:54
• @GerryMyerson, 2 is not prime in $\mathbb{Q}[\sqrt d]$. We have $(2)=(2+\sqrt 6)(2-\sqrt 6)$. Neither is 5 - we have $(5)=(1-\sqrt 6)(1+\sqrt 6)$. In fact the class group of $\mathbb{Q}[\sqrt 6]$ really does have order one. Look here. – Bruno Joyal Aug 4 '12 at 20:02
• Yes, you're right. I was thinking 2 was irreducible in that ring, since there's nothing of norm 2, but there are elements of norm $-2$, and they do the trick. – Gerry Myerson Aug 4 '12 at 23:38

Every integer is less then 100, except for $n>99$, where the pattern breaks.

• This is supposed to be an answer? – J. M. isn't a mathematician Aug 3 '12 at 8:15
• I do not understand the downvotes... This is the obvious example of a pattern that holds only for small $n$! – Mariano Suárez-Álvarez Aug 3 '12 at 17:22
• Better: Every integer is not equal to seven, except 7. – Mark Hurd Aug 3 '12 at 18:40
• What about: Every natural number is positive, except $0$. – celtschk Aug 3 '12 at 20:04
• I suppose I should have specified "nontrivial examples". – Will Aug 4 '12 at 19:51

The sequence of the maximal number of regions formed by drawing chords between all pairs of n points in arbitrary position on the border of a circle starts 1, 2, 4, 8, 16; and then the next term, of course, is... 31. (The canonical formula is $1+{n\choose2}+{n\choose4}$.) For more details, see http://oeis.org/A000127

• This seems to be an example of a formula that seems to hold for small n, but doesn't hold for slightly larger n. OP was looking for a formula/rule that holds for all numbers except for small n. – BlueRaja - Danny Pflughoeft Aug 3 '12 at 2:19
• I realized that after writing this up (though it's an example of a small-$n$ trend that doesn't continue for large $n$); it's part of the reason I wrote up my other answer. I'm tempted to delete this one, but it seems to be liked... – Steven Stadnicki Aug 3 '12 at 2:23
• It's fun to point out to people that the sequence contains 256; that provides extra "evidence" that it consists of powers of two! – Michael Lugo Aug 24 '12 at 21:34

Let $n$ be fixed and let $x_1, x_2, \ldots x_n$ by any positive numbers, where the indices are taken mod $n$, so that $x_{n+i}$ is understood to be the same as $x_i$.

It is easy to show that $$\sum_{i=1}^n \frac{x_i}{x_{i+1}} \ge n$$

It is tempting to conjecture similarly:

$$\sum_{i=1}^n \frac{x_i}{x_{i+1}+x_{i+2}} \ge \frac n2.$$

And indeed, you would be hard-pressed to find a counterexample, since the conjecture is true…

if $n$ is one of: $$\left\{\begin{array}{cccccc}1,&2,&3,&4,&5,&6,\\ 7,&8,&9,&10,&11,&12,\\ 13,&&15,&&17,\\ 19,&&21,&&23 \end{array}\right\}$$ In all other cases, the conjecture is false.

I wouldn't really call them accidents, but here are two simple related results from algebra:

There exists algebraic extensions of $\mathbb{R}$ of dimension $n$ only for $n=1$ and $n=2$.

Also it is not possible to construct an Division Ring over $\mathbb{R}$ of dimension $n$, excepting when $n=4$.

On the congruence $(x-1)! \mod x$:

• This is $0$ if $x>4$ is composite.
• This is $1$ if $x$ is prime.
• This is $2$ when $x=4$.

One can say that $x=4$ is here the exception.

There are cyclic numbers for all bases $>4$, except for perfect squares, and $6$ (if you exclude leading zeros).

Although there is an infinite family of generalized Petersen graphs with arbitrarily many vertices, there are exactly seven of these that are edge-transitive, the largest having 48 vertices.