law of small numbers
Richard Guy often refers to the law of small numbers which states that there are not enough small numbers to satisfy all the demands placed on them. What this means is that we will often see things happen with small numbers that are not normative, that is, often small numbers do not well represent the behavior of large numbers. I think this demands a few examples before we discuss it further.
- Let's start real small: the first four odd numbers are 1, 3, 5, 7; so should we conclude all odd numbers are either one or prime? I'd hope not!
- Look at the remainders when the first few primes are
divided by four
2, 3, 1, 3, 3, 1, 1, 3, 3, 1, 3, 1, 1, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 1, 1, 1, 3, 3, 1, 1, ...
It looks like if we stop this list at any point, there are always at least as many 3's as there are 1's. This pattern would hold even if we looked at the first 25000 terms of this sequence. But it has been proven that the number which is more common in the first n terms switches back and forth between 1 and 3 infinitely often.
seems to always be one. In fact, if you
had your computer checking this for n=1, 2, 3, . . .
successively, it would never find a counter-example. That
is because the first counter-example is
- Finally, Riemann's function Li(x) (see the page linked below) is an approximation for pi(x) (the number of primes less than or equal to x). For all values x ≥ 3 for which pi(x) is known, pi(x) < Li(x). And this is a lot of values--it includes at least all integers below 1,000,000,000,000. But Littlewood proved that pi(x) > Li(x) infinitely often! Skewes showed that the first such x is less than 10^10^10^34, a horrendously large number now called Skewes' number. This bound has been greatly reduced to a "mere" 10314, but Skewes' number is well remembered in the folklore of arithmetic.
So the moral behind the law of small numbers is this: do not believe a pattern continues just because it holds for all the numbers that you have checked so far. Look for proof, or at least a heuristic argument, before you conjecture. Large numbers are different!
In his article [Guy88], Guy restated his law is several other forms:
- You can't tell by looking [at a few examples].
- Superficial similarities spawn spurious statements.
- Capricious coincidences cause careless conjectures.
- Early exceptions eclipse eventual essentials.
- Initial irregularities inhibit incisive intuition.
Related pages (outside of this work)
- How big of an infinity? (information on pi(x), Li(x), ...)
- R. K. Guy, "The strong law of small numbers," Amer. Math. Monthly, 95:8 (1988) 697--712. MR 90c:11002
- R. K. Guy, Unsolved problems in number theory, Springer-Verlag, New York, NY, 1994. ISBN 0-387-94289-0. MR 96e:11002 [An excellent resource! Guy briefly describes many open questions, then provides numerous references. See his newer editions of this text.]