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