From: dresden@max.ma.utexas.edu (Greg Dresden)
Newsgroups: sci.math
Subject: "Law of Small Numbers"... more examples!
Date: 21 Oct 1996 14:02:59 GMT
Well, I don't actually *have* more examples, I'm *looking* for them.
What I'm talking about here are statements (usually in number theory)
that appear to be true for the first five, or first five hundred,
cases, but only "further along the list" does a counter-example appear
that shows that one's original statement is, in fact, not true.
Mathematicians call this the "law of small numbers:" small numbers
do amazing things, and don't always reflect the "true" nature
of a theory.
A simple example: "every odd number is prime."
This is true for 3,5, and 7, and a naive person might then assume it's
true for all primes (of course, this fails for 9).
A better example: "Q(sqrt(d)) is a unique factorization domain."
This is true for 0 dresden@max.ma.utexas.edu
(Greg Dresden) writes:
>Well, I don't actually *have* more examples, I'm *looking* for them.
>
>What I'm talking about here are statements (usually in number theory)
>that appear to be true for the first five, or first five hundred,
>cases, but only "further along the list" does a counter-example appear
>that shows that one's original statement is, in fact, not true.
>
>Mathematicians call this the "law of small numbers:" small numbers
>do amazing things, and don't always reflect the "true" nature
>of a theory.
Yes, here is my favorite example, from my paper A mod-n Ackermann
function, or What's so special about 1969? (with Jon Froemke), American
Mathematical Monthly 100 (1993) 180-183. We define a certain process,
rather like the famous Ackermann function, but operating modulo a
parameter n. If you play with it, you see that for each n the process
eventually terminates in a constant, so of course we conjectured that this
always happens. We programmed our computer to check this out for all n up
to a million. Much to our surprise, the conjecture is true for every
value in that range except n=1969. We have no idea why. See the paper
for details.
--
Jerrold W. Grossman, Professor VOICE: (810) 370-3443
Department of Mathematical Sciences FAX: (810) 370-4184
Oakland University FLESH: 322 O'Dowd Hall
Rochester, MI 48309-4401 E-MAIL: grossman@oakland.edu
WEB: http://www.oakland.edu/~grossman/
==============================================================================
From: numtheor@tiac.net (Bob Silverman)
Newsgroups: sci.math
Subject: Re: "Law of Small Numbers"... more examples!
Date: Tue, 22 Oct 1996 01:17:56 GMT
dresden@max.ma.utexas.edu (Greg Dresden) wrote:
>Well, I don't actually *have* more examples, I'm *looking* for them.
>What I'm talking about here are statements (usually in number theory)
>that appear to be true for the first five, or first five hundred,
Richard Guy wrote 2 articles covering this sometime in the late 80's.
I believe they appeared in Math. Intelligencer
You can lead a horse's ass to knowledge, but you can't make him think.
==============================================================================
From: gerry@mpce.mq.edu.au (Gerry Myerson)
Newsgroups: sci.math
Subject: Re: "Law of Small Numbers"... more examples!
Date: 22 Oct 1996 01:22:16 GMT
In article <54gsto$e5a@news-central.tiac.net>, numtheor@tiac.net (Bob
Silverman) wrote:
=>
=> dresden@max.ma.utexas.edu (Greg Dresden) wrote:
=>
=> >Well, I don't actually *have* more examples, I'm *looking* for them.
=>
=> >What I'm talking about here are statements (usually in number theory)
=> >that appear to be true for the first five, or first five hundred,
=>
=> Richard Guy wrote 2 articles covering this sometime in the late 80's.
True.
=> I believe they appeared in Math. Intelligencer
No, I think one was in the American Math Monthly, and the other in the
College Math Journal.
Gerry Myerson (gerry@mpce.mq.edu.au)
==============================================================================
From: mlerma@pythagoras.ma.utexas.edu (Miguel Lerma)
Newsgroups: sci.math
Subject: Re: "Law of Small Numbers"... more examples!
Date: 22 Oct 1996 02:18:26 GMT
Greg Dresden (dresden@max.ma.utexas.edu) wrote:
> Well, I don't actually *have* more examples, I'm *looking* for them.
> What I'm talking about here are statements (usually in number theory)
> that appear to be true for the first five, or first five hundred,
> cases, but only "further along the list" does a counter-example appear
> that shows that one's original statement is, in fact, not true.
> Mathematicians call this the "law of small numbers:" small numbers
> do amazing things, and don't always reflect the "true" nature
> of a theory.
My favorite has to do with the functions pi(x) = # of primes less
than or equal to x, and the logarithmoc integral Li(x). It is known
that pi(x)/Li(x) -> 0 for x -> infinity. On the other hand computation
always shows that pi(x) < Li(x) for x >= 3. This might make us think
pi(x) < Li(x) for every x >= 3, however Littlewood proved that it is
false, and Skewes showed that the first counterexample should be less
than 10^10^10^34.
Another example comes from the following observation: let p be a
prime number different from 2 and 5 and compare the lenghts n and n'
of the periods of the decimal expansions of 1/p and 1/p^2 respectively.
For instance, for p=7 we have 1/7 = .142857... repeated periodically, and
1/7^2 = 1/49 = .020408163265306122448979591836734693877551... repeated
periodically, so in this case n = 6 and n' = 42 = 6*7. The rule seems to
be that always n' = n*p, except for p=3, since both 1/3 = 0.3333... and
1/3^2 = 1/9 = 0.1111... have a period of lenght 1 in their decimal expansion
(it is easy to prove that either n' = n*p or n' = n). I knew of an amateur
mathematician convinced that that was the truth. That was before the era
of calculators and computers, so he could be understood for not checking
p=487: boths 1/487 and 1/487^2 have decimal expansions with a period of
486 digits. The third exception is a number of 8 digits. I do not know
of a fourth exception, however some heuristic arguments seem to support
that there are infinitelly many exceptions, but they are so rare that
we can expect to find only about n of such numbers among the first
exp(exp(n)) primes.
Miguel A. Lerma
==============================================================================
From: ndm@shore.net (Norman D. Megill)
Newsgroups: sci.math
Subject: Re: "Law of Small Numbers"... more examples!
Date: 22 Oct 1996 04:05:38 -0400
In article <54fvqj$54h@geraldo.cc.utexas.edu>,
Greg Dresden wrote:
>
>My favorite example: "The cyclotomic polynomials have +/-1 as
>coefficients." This holds all the way up to the 104th polynomial,
>after which you start seeing 2's and 3's and more.
>
>Does anyone else know any easily-stated problems similar to this?
>
"Given integer p>0, there exists an integer n>1 such that the sum of
digits of n^p = n." E.g. 25^4 = 390625, 3+9+0+6+2+5 = 25. This
is true all the way up to p = 104, and fails at p = 105.
Norm Megill
==============================================================================
From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: "Law of Small Numbers"... more examples!
Date: 22 Oct 1996 19:07:14 GMT
In article <54fvqj$54h@geraldo.cc.utexas.edu>,
Greg Dresden wrote:
>
>My favorite example: "The cyclotomic polynomials have +/-1 as
>coefficients." This holds all the way up to the 104th polynomial,
>after which you start seeing 2's and 3's and more.
>
>Does anyone else know any easily-stated problems similar to this?
"The following pattern generates primes only:
41, 41+2=43, 43+4=47, 47+6=53, 53+8=6, ..."
One could give many examples of diophantine equations stated with
very small integers whose only (known) solutions are comparatively
large. Among some well-known examples:
2^n = 2 mod n^2 [usually with n prime]
x^2-94y^2 = 1
y^2=x^3+877x (very dramatic)
Elliptic curves generally tend to create big numbers very fast.
Likewise there is the connection between diophantine equations in
logic via Hilbert's 10th problem; for example, there is a comparatively
simple set of equations in 26 variables which is solvable iff n is
prime; but the solutions of those equations will of necessity grow
quite quickly with n, so you can get some big solutions to small problems.
A number of primality tests use theorems of the form "if n=prime then X"
for which the converse statement "if X then n=prime" has comparatively
few counterexamples. For example, take X to be the
statement "... n divides u_n, where u_2=0, u_2=2, u_3=3, and
u_(n+1)=u_(n-1)+u_(n-2)".
Some properties fail for reasonably small values of n but those
values don't seem small when there is a lot of work involved even in
the small cases, or in which there is a certain resistance to the
idea for some reason. For example, one could state "If n is prime
then n does not divide the n-th Bernoulli number"; n=37 is the
first counterexample. There is no end of famous problems which more
or less say, "Two big theorems may be viewed as cases n=1 and n=2 of the
following general statement; is the case n=3 also valid?";
then perhaps n=3 is very difficult. Just offhand I might mention
the "dimension subgroup" problem in finite group theory as a (not
particularly important or striking) example.
There are some examples in topology in which the cases n=1,2,3 are
easily visualizes, but starting with n=4 our intuition fails. Thus
counterexamples may be found even after what is seen, after the
fact, as a small number of previous cases. For example, there
are no nontrivial maps from the n-sphere to the m-sphere if
n <> m (false if n=3, m=2!) or there is only one differentiable structure
on the n-sphere (false if n=7).
If you're not careful to explain what you want, this discussion can
degenerate into the threads "what are some places big numbers occur
in mathematics?" and "are there any surprising results in mathematics?".
dave
==============================================================================
From: lfr942f@cnas.smsu.edu (Reid Les)
Newsgroups: sci.math
Subject: Re: "Law of Small Numbers"... more examples!
Date: 24 Oct 1996 19:45:56 GMT
Greg Dresden (dresden@max.ma.utexas.edu) wrote:
: Well, I don't actually *have* more examples, I'm *looking* for them.
: What I'm talking about here are statements (usually in number theory)
: that appear to be true for the first five, or first five hundred,
: cases, but only "further along the list" does a counter-example appear
: that shows that one's original statement is, in fact, not true.
Here are some examples. George Berzsenyi first asked about this
sort of question in the January 1996 issue of Quantum magazine.
Stan Wagon posed the first problem as one of his Problems of the
Week and Ilan Vardi provided the subsequent examples.
1. gcd[n^5 + 5, (n+1)^5 + 5] = 1 for all n < 533360, but
gcd[533360^5 + 5, 533361^5 + 5] = 1968751.
2. gcd[n^17 + 9, (n+1)^17 + 9] = 1 for all n <
8424432925592889329288197322308900672459420460792433,
at which point the GCD is not 1.
3. A much longer string of 1's occurs if (17, 9) is replaced by
(23, 6).
==============================================================================
From: dean@math.math.ucdavis.edu (Dean Hickerson)
Newsgroups: sci.math
Subject: Re: "Law of Small Numbers"... more examples!
Date: 25 Oct 1996 14:33:54 GMT
Greg Dresden (dresden@max.ma.utexas.edu) wrote:
: Well, I don't actually *have* more examples, I'm *looking* for them.
: What I'm talking about here are statements (usually in number theory)
: that appear to be true for the first five, or first five hundred,
: cases, but only "further along the list" does a counter-example appear
: that shows that one's original statement is, in fact, not true.
...
The period of the simple continued fraction expansion of sqrt(d) (where
d is a positive integer that's not a perfect square) is less than or
equal to 2 floor(sqrt(d)), for d<1726. But for d=1726, the period is
88, while 2 floor(sqrt(d)) = 82.
Dean Hickerson
dean@ucdmath.ucdavis.edu
==============================================================================
From: ikastan@alumnae.caltech.edu (Ilias Kastanas)
Newsgroups: sci.math
Subject: Re: "Law of Small Numbers"... more examples!
Date: 27 Oct 1996 06:09:19 GMT
In article <54qj4i$hs9@mark.ucdavis.edu>,
Dean Hickerson wrote:
>Greg Dresden (dresden@max.ma.utexas.edu) wrote:
>: Well, I don't actually *have* more examples, I'm *looking* for them.
>
>: What I'm talking about here are statements (usually in number theory)
>: that appear to be true for the first five, or first five hundred,
>: cases, but only "further along the list" does a counter-example appear
>: that shows that one's original statement is, in fact, not true.
>...
>
>The period of the simple continued fraction expansion of sqrt(d) (where
>d is a positive integer that's not a perfect square) is less than or
>equal to 2 floor(sqrt(d)), for d<1726. But for d=1726, the period is
>88, while 2 floor(sqrt(d)) = 82.
If you just search for a positive integer solution of
x^2 - 991y^2 = 1
you might end up by giving up. But theory says that it exists (and hence
infinitely many exist). The least one is
x = 379516400906811930638014896080,
y = 12055735790331359447442538767.
Knowing about continued fractions saves you some work...
Ilias
==============================================================================
From: mckay@cs.concordia.ca (MCKAY john)
Newsgroups: sci.math
Subject: Re: Law of small numbers
Date: 25 Oct 1996 08:58:28 GMT
a[0]:=1;a[1]:=1; for n>=1, a[n+1]:=sum(a[k]^2,k=0..n)/n
What is the smallest value of a[n] not an integer?
--
Deep ideas are simple.
Odd groups are even.
Even simples are not;
and Gal/F2(t)(x^24-x-t) = Mathieu group, M24.
==============================================================================
From: Helmut.Richter@lrz-muenchen.de (Helmut Richter)
Newsgroups: sci.math
Subject: Re: "Law of Small Numbers"... more examples!
Date: 28 Oct 1996 09:15:12 GMT
dresden@max.ma.utexas.edu (Greg Dresden) writes:
>Well, I don't actually *have* more examples, I'm *looking* for them.
>What I'm talking about here are statements (usually in number theory)
>that appear to be true for the first five, or first five hundred,
>cases, but only "further along the list" does a counter-example appear
>that shows that one's original statement is, in fact, not true.
I browsed through the "Penguin Dictionary of Curious and Interesting
Numbers" and through Graham/Knuth/Patashnik's "Concrete Mathematics"
and found some others. Unfortunately, the former does not provide
proofs nor references, so you will have to double-check the "facts"
yourself.
Here is what I found:
1. There are as many primes of form 4k+1 as there are of form 4k+3
(that is: Let M(n,m,r) = # {x : x<=n, x prime, x mod m = r}
Then M(n,4,1)-M(n,4,3) changes sign infinitively often))
One should therefore expect the first change of sign quite early,
but it does not happen any earlier than at 26863.
2. There are more primes of form 3n+1 than of form 3n+2 (in an
analogous sense). One should therefore expect either no exceptions
or exceptions only at small numbers. However, the exceptions are
in a limited region starting at 608981813029.
(This one is stated very ambiguously in the Penguin Dictionary;
and the above is my interpretation of what I read. Before you believe
it, you should check whether it is true.)
3. Wrong: n^2 divides C(2n-1,n-1)-1 if and only if n is prime. (C(m,n)
is the binominal coefficient "m over n").
Smallest counterexample: n = 283686649 = 16843^2
4. Wrong: Let a0, a1 be relatively prime. Then the Fibonacci-like
sequence given by a(n+2) = a(n+1) + a(n) contains at least one prime.
Graham/Knuth/Patashnik's book contain a counterexample but it is
not quite clear what the smallest counterexample is. There seems to
be one with 17 digits for both a0 and a1.
5. Wrong: Every odd number is the sum of a prime and a power (or: of
a prime and twice a square).
Smallest counterexamples: 1549 (or: 5777, respectively).
There is an abundance of such results, usually with some big number
opening a huge set of counterexamples. In these two cases, this is
not so: there are relatively few counterexamples known.
6. The innocent-looking equation 2^x mod x = 3 has its first (only?)
solution at 4700063497.
Helmut Richter
==============================================================================
From: jmcgowan@metric.inch.com (John McGowan)
Newsgroups: sci.math
Subject: Re: "Law of Small Numbers"... more examples!
Date: 29 Oct 1996 15:53:20 GMT
Helmut Richter (Helmut.Richter@lrz-muenchen.de) wrote:
> dresden@max.ma.utexas.edu (Greg Dresden) writes:
> >What I'm talking about here are statements (usually in number theory)
> >that appear to be true for the first five, or first five hundred,
> >cases, but only "further along the list" does a counter-example appear
> >that shows that one's original statement is, in fact, not true.
> I browsed through the "Penguin Dictionary of Curious and Interesting
> Numbers" and through Graham/Knuth/Patashnik's "Concrete Mathematics"
> and found some others. Unfortunately, the former does not provide
> proofs nor references, so you will have to double-check the "facts"
> yourself.
> 2. There are more primes of form 3n+1 than of form 3n+2 (in an
> analogous sense). One should therefore expect either no exceptions
> or exceptions only at small numbers. However, the exceptions are
> in a limited region starting at 608981813029.
> (This one is stated very ambiguously in the Penguin Dictionary;
> and the above is my interpretation of what I read. Before you believe
> it, you should check whether it is true.)
If a an b are relatively prime, than the number of primes smaller than n
of the form ax+b is asymptotically given by n/{phi(a)*ln(n)} (basically,
the primes with a given residue mod a are obtained by taking all the
primes and dividing by how many such residues could be prime... so b must
be rel. prime to a). In particular, asymptotically, the number of primes
of the form 3n+1 and 3n+2 are the same (the ratio tends to one... that
still does not answer the question of what the difference is, only that
the difference is o(the number of primes of that form))
----------
My favourite small number example is take a circle. Place n+1 vertices on
the circle. Join each vertex to all the others (complete graph) and place
them so at no point in the interior do more than two such joining edges
intersect (symmetry can reduce the number of regions one gets, below).
Into how many regions does this divide the interior of the circular disk?
The results are:
n # of regions
0 1 (n+1=1, no division
1 2 n+1=2, a diameter
2 4 n+1=3, a triangle... the regions from each
edge to the circle and the interior
of the triangle itself)
3 8
4 16
and the next number is... (1,2,4,8,16....)... 31. (it is a fourth order
polynomial)
==============================================================================
From: lfr942f@cnas.smsu.edu (Reid Les)
Newsgroups: sci.math
Subject: Re: "Law of Small Numbers"... more examples!
Date: 24 Oct 1996 19:45:56 GMT
Greg Dresden (dresden@max.ma.utexas.edu) wrote:
: Well, I don't actually *have* more examples, I'm *looking* for them.
: What I'm talking about here are statements (usually in number theory)
: that appear to be true for the first five, or first five hundred,
: cases, but only "further along the list" does a counter-example appear
: that shows that one's original statement is, in fact, not true.
Here are some examples. George Berzsenyi first asked about this
sort of question in the January 1996 issue of Quantum magazine.
Stan Wagon posed the first problem as one of his Problems of the
Week and Ilan Vardi provided the subsequent examples.
1. gcd[n^5 + 5, (n+1)^5 + 5] = 1 for all n < 533360, but
gcd[533360^5 + 5, 533361^5 + 5] = 1968751.
2. gcd[n^17 + 9, (n+1)^17 + 9] = 1 for all n <
8424432925592889329288197322308900672459420460792433,
at which point the GCD is not 1.
3. A much longer string of 1's occurs if (17, 9) is replaced by
(23, 6).
==============================================================================
[Notes to myself -- djr]
==============================================================================
a[43] :=
614935539181658947036220820675882164876880528693079999087607604486044051630733\
847558410043862292323393103032971238329183964590881111459999970178036965722869\
76
Error, the modular inverse does not exist
> uu:=factorial(100);
uu :=
933262154439441526816992388562667004907159682643816214685929638952175999932299\
156089414639761565182862536979208272237582511852109168640000000000000000000000\
00
> for i from 1 to 100 do a[i+1]:=(sum(a[k]^2, k=0..i)/i) mod uu; od;
==============================================================================
90c:11002 11-01 00A05 05-01
Guy, Richard K.(3-CALG)
The strong law of small numbers. (English)
Amer. Math. Monthly 95 (1988), no. 8, 697--712.
This very engaging article discusses $35$ examples of patterns that
seem to appear when we check small values of $n$. Some work, some
don't, and the second half of the paper sorts them out while supplying
background information.
The patterns come from all over: elementary number theory, geometry,
algebra, combinatorics, calculus, and games. The answers sometimes
require doing one or two more cases, sometimes a good bit of higher
mathematics and/or extensive computation. Some, such as the Fermat
primes and pseudoprimes, are famous but the majority are not well
known.
Every mathematician should find something of interest in this article.
With the recent emphasis on teaching pattern recognition throughout
the elementary and high school curriculum this relatively brief
article will be invaluable.
Reviewed by Louis Shapiro
© Copyright American Mathematical Society 1990, 1997