Conjecture, and why a pattern is not a proof
Something has held every time you tried it. How do you state it so that it can be tested, and what has to happen before it stops being a guess?
Where you are 14 in Proof techniques
Why this exists
Mathematics is found before it is proved. Someone adds up the first few odd numbers and gets square numbers, or colors a map and never needs a fifth color, and a guess forms. Most of the time the guess is right. Sometimes it survives for centuries with no proof, and sometimes it breaks on the very next case.
A guess like that needs a status. It is not a fact, because nothing has shown it always holds, so nothing safe can be built on it. It is not rubbish either, because it points at something real. Conjecture is the name for the middle state: a claim that is worth working on and is not yet safe to use.
The word keeps everyone honest. Whoever hands one over says plainly that it is unproved, and whoever builds on one says plainly that the building is only as sure as the guess beneath it.
History shows how long the middle state can last. The claim that four colors always suffice for a map was made in 1852 and proved in 1976. Fermat wrote his famous claim in a margin around 1637 and it was proved in 1994. Goldbach set out his in a letter in 1742, and it is still open today.
It is tempting to shorten the wait by checking more cases. Draw a circle and mark one point on it. The inside is one region. Mark a second point and join the two with a straight chord: two regions. Three points, with all three chords between them, give four regions. Four points give eight, and five points give sixteen.
The counts 1, 2, 4, 8, 16 are the powers of two, and anyone asked for the next one says 32. It is an easy bet. Five cases agree, the rule is simple, and nothing in the drawing hints at trouble. The sixth point gives 31.
A claim in mathematics usually covers more cases than anyone can look at: every whole number, every triangle, every circle. The cases we do look at are a few of them, and the cases we have not looked at are still there. So this lesson has two halves. The first says what status a guess has while it waits and what ends the wait. The second, why a pattern is not a proof, asks why the waiting cannot be shortened by looking at more examples, how badly a pattern can mislead before it gives way, and what a proof has that a pile of examples never will.
Definition
Conjecture
A conjecture is a statement that is believed to be true, for reasons short of proof, and that has been neither proved nor disproved.
Three things are packed into that sentence.
- It is a statement: a sentence that is either true or false. A question, an instruction, or an opinion such as “primes are beautiful” is not one.
- It is precise: every word has one meaning, and it says what it is about. “Big numbers behave nicely” is not precise. “Every even whole number greater than 2 is the sum of two primes” is.
- It is open: nobody has a proof, and nobody has a counterexample.
Most conjectures claim something about every member of a collection, the “for all” of a universal statement. A few claim that something exists, the “there is” of an existential statement. With P for the property and D for the collection, the two shapes are
read “for every x in D, P holds for x” and “for some x in D, P holds for x”.
A conjecture is always in one of three states, and it leaves the first only through a proof or a counterexample.
| State | What puts it there | Its name |
|---|---|---|
| open | nothing has settled it yet | a conjecture |
| proved | an argument that covers every case | a theorem |
| disproved | a counterexample, or a proof of the opposite | a false conjecture |
Names outlive states. “Fermat’s Last Theorem” was a conjecture for more than three centuries and kept its name when it became a theorem. The old name tells you it once was a guess; the status is what matters.
Case, check, pattern and proof
A case is one particular instance of a claim: one value of n in a statement about every whole number, or one triangle in a statement about every triangle. A check is the work of confirming the claim for one case.
A rule fits a list of values when, given the position of each value, it returns that value. The rule “double the last term” fits 1, 2, 4, 8, 16, and so does the rule “the nth term is 2^{n-1}”.
A pattern is a rule that fits every case checked so far. A proof is an argument that the rule is right in every case, checked or not.
Those two differ in one word: a pattern says “so far” and a proof says “always”. The claim of the second half of this lesson is that fitting the cases checked does not, by itself, show that the rule is right for the next one. A pattern that has not yet been proved or broken is a conjecture.
Intuition
A public bet
Think of a conjecture as a public bet. The claim is written down in words exact enough that anyone can try to break it. Each case that fails to break it makes the claim look better, and nothing else changes. Only two events end the bet: a proof that no case can break it, or one case that does.
Conjectures come from several places. A table of values suggests one, as with the odd numbers. A drawing suggests one, as with the diagonals of a quadrilateral. A rule applied again and again suggests one. So does a result that is proved for a few cases, or a stronger or weaker cousin of a claim already known. The worked examples below use each.
A good conjecture has three marks.
- It is precise enough to fail. A claim that no case could break says nothing.
- It has been tested where it might fail. Cases unlike the ones that suggested it are worth far more than more of the same: the smallest case, zero, two equal values, an odd-looking shape.
- It is not obvious. A claim whose proof anyone can see at a glance is proved on the spot and never needs the name. The interesting ones are the ones somebody had to notice.
Agreement is worth something. A claim that has survived a great many varied tests deserves more belief than one that has survived three. But belief is not status, and however long the list of agreeing cases grows, the next case is still unchecked.
Why a pattern is not a proof
Think of five checked cases as five dots on a graph, with the case number along the bottom and the value up the side. Anyone can draw a smooth curve through five dots, and the curve will go on past the last one. The trouble is that many different curves go through the same five dots and then go to different places. Figure 1 shows three of them. Nothing about the dots says which curve is the right one, because the dots were all that was given.
A list of numbers is a finite thing. A rule is a statement about every case, so it is an infinite thing. A finite list cannot pin an infinite rule down, in the same way that five dots cannot pin down one curve. Something else has to do that job, and what does it is a reason.
We come to believe a claim in several ways: someone we trust says so, we try examples, we look at a picture, or we argue from statements already proved. Examples are how claims are found, but they are the weakest way of showing a claim holds in every case. A picture also shows particular cases, and what it may be trusted for is treated in what a diagram lets you assume. Only an argument from what is already proved reaches every case at once.
What such an argument has is a reason: something that explains why the next case has to come out the way the earlier ones did. The numbers 1, 2, 4, 8, 16 turn up in two different places, as the regions of a circle and as the subsets of a set, and the worked examples below set them side by side. In one the doubling has a reason, and in the other it has none. The five numbers give no way of telling which is which. The reasons do.
Results
What settles a conjecture
A conjecture is true or false even while it is open. Nobody knowing which does not make it “neither”.
Only a proof or a counterexample changes its status. A thousand agreeing cases, or a million, leave it exactly where it was.
One case cuts differently for the two shapes. For a “for every” conjecture, one failing case disproves it, and no number of passing cases proves it. For a “there is” conjecture it is the other way round: one example proves it, and no number of failed searches disproves it.
Stronger and weaker. If conjecture A implies conjecture B, then A is the stronger. Proving A proves B, and disproving B disproves A, but proving B does not prove A, and disproving A does not disprove B.
A false conjecture can often be repaired. Adding a hypothesis, or narrowing what it is about, removes the failing case. The repaired claim is a new conjecture and needs its own proof.
What examples can and cannot show
The next value is free. Take any finite list of values, at the cases 1, 2, \dots, k, and any number v you like. There is a polynomial f with f(1), \dots, f(k) equal to the listed values and f(k+1) = v.
Agreement can stop anywhere. Choose any case number N \ge 2. There is a rule that agrees with “double each time” at every case before N and does not agree with it at N. So the first failure of a pattern can be placed as early or as late as you like, and the cases before it give no warning.
Regions made by a circle’s chords. Mark n points on a circle, so that no three of the chords between them pass through one point, and draw every chord. The number of regions inside is
For n = 1, 2, \dots, 8 this gives 1, 2, 4, 8, 16, 31, 57, 99.
A reason is an argument about a general n. A claim about every whole number is proved when an argument is given in which n stays a letter, so that the same steps serve for every n. A common shape is an argument from each case to the next, which is the idea behind proof by induction. An argument that has to be redone with a new number each time is a check and not a proof.
Why it is true
What settles a conjecture
It has a truth value. A precise statement about a named collection is, for each member of the collection, true or false, and a “for every” statement is true exactly when it holds for every member. Our not knowing which does not alter how things are, only what we can say about them.
Why one failing case is enough, and no passing cases are. The opposite of “for every x in D, P holds” is “for some x in D, P fails”, as in negating a quantified statement. A “for some” statement is true as soon as one member is shown, so a single member where P fails is a proof of the opposite. Going the other way, a finite list of passing members covers only those members. If D is infinite, it leaves infinitely many members unchecked, and any one of them could be the failure. The same reasoning read backwards handles the “there is” shape: one example proves it, but a finite list of failed members leaves the rest untouched.
Why the implication runs the way it does. Suppose A \Longrightarrow B. If A is proved, B follows by the implication, so B is proved. If B is disproved, then A cannot be true, because a true A would bring a true B with it, so A is disproved. But if B is proved, A may still fail, since A asks for more than B does, and if A is disproved, B may still hold for the same reason.
Why narrowing can repair a claim. A counterexample is a member of the collection D where the property fails. If the claim is restated for a smaller collection that leaves that member out, the counterexample no longer belongs to it. The other members of the smaller collection have not been examined, which is why the repaired claim is a fresh conjecture and not a theorem.
What examples can and cannot show
The next value is free. First build a polynomial that matches the list. For each position i from 1 to k, let
with the factor n - i left out of the top and the factor i - i left out of the bottom. At n = i every factor on top is canceled by the matching factor below, so L_i(i) = 1. At any other whole number m from 1 to k, the top has the factor m - m = 0, so L_i(m) = 0. Then
has f_0(i) = a_i for each i. Now add a multiple of the product that is zero at every listed case:
The added term is 0 at n = 1, \dots, k, so f still matches the list. At n = k + 1 the product equals k!, so f(k+1) = f_0(k+1) + c \cdot k!. Choosing c = \dfrac{v - f_0(k+1)}{k!} makes f(k+1) = v.
Agreement can stop anywhere. Apply the first result to the N - 1 values 1, 2, 4, \dots, 2^{N-2} and to any value v other than 2^{N-1}. The resulting f agrees with doubling at the cases 1, \dots, N-1 and differs from it at case N.
Regions made by a circle’s chords. Take the picture as a graph in the plane, with a corner at each of the n points and at each place where two chords cross, and an edge for each piece of chord and each arc of the circle between neighboring points. Let I be the number of crossings.
A crossing needs two chords with four different ends, and any four points on a circle have exactly one pair of chords that cross, the two diagonals of the four-sided shape they make. Different quadruples give different crossing points because no three chords meet at a point. So I = \binom{n}{4}.
The corners number V = n + I. Each chord with k crossings on it is cut into k + 1 pieces, and each crossing lies on two chords, so the chords make \binom{n}{2} + 2I pieces. With the n arcs, the edges number E = \binom{n}{2} + 2I + n.
Euler’s formula says that a connected graph drawn in the plane has V - E + F = 2, where F counts the faces and includes the outside one. Then
and taking away the outside face leaves 1 + \binom{n}{2} + \binom{n}{4} regions inside the circle. This argument is for n \ge 3. For n = 1 and n = 2 the regions can be counted at sight, one and two, and the formula gives the same.
A reason is an argument about a general n. An argument whose steps do not depend on which n was chosen applies to every n, because nothing in it was special to the one picked. A list of checks, however long, has a last item, and nothing in the list covers the item after it. The test is whether the argument would still work unchanged for a number nobody has tried yet.
Worked examples
Stating a conjecture exactly, and testing it
Goldbach’s conjecture says that every even whole number greater than 2 is the sum of two primes. Write it in the for-every form, say what would disprove it, and test it on every even number from 4 to 30.
SolutionIn the for-every form: for every even whole number n > 2, there are primes p and q with n = p + q.
Being exact forces two decisions. The primes p and q may be the same prime, since otherwise 4 = 2 + 2 would be a failure on the first case. And n must exceed 2, since 2 = 1 + 1 and 1 is not prime.
It is a for-every statement, so one even number greater than 2 that is not a sum of two primes would disprove it.
To test an even number n, try the small primes p = 2, 3, 5, \dots and ask whether n - p is prime. For 26: p = 3 gives 23, which is prime, so 26 = 3 + 23. Doing this for each even number gives one way to write each:
| n | one way | n | one way |
|---|---|---|---|
| 4 | 2 + 2 | 18 | 5 + 13 |
| 6 | 3 + 3 | 20 | 3 + 17 |
| 8 | 3 + 5 | 22 | 3 + 19 |
| 10 | 3 + 7 | 24 | 5 + 19 |
| 12 | 5 + 7 | 26 | 3 + 23 |
| 14 | 3 + 11 | 28 | 5 + 23 |
| 16 | 3 + 13 | 30 | 7 + 23 |
All fourteen pass. Computers have gone much further and have checked every even number up to 4 \times 10^{18} with no failure. The status has not moved: the claim is about every even number, the checks cover finitely many of them, and the conjecture is still open.
Which way does one case cut?
For each claim, say what one case would do and then settle it.
- (a) Every prime is odd.
- (b) There is a perfect number greater than 28. (A number is perfect if it equals the sum of its divisors that are smaller than itself, like 6 = 1 + 2 + 3.)
- (c) There is a prime between 24 and 28.
(a) is a for-every claim, so one failing case disproves it. The prime 2 is even, so the claim is false. Looking at the odd primes 3, 5, 7, 11 would never have shown this.
(b) is a there-is claim, so one example proves it. Take 496. Its divisors below itself are 1, 2, 4, 8, 16, 31, 62, 124, 248. Add the first five, then the last four:
and 31 + 465 = 496, so 496 is perfect and the claim is true. One example was enough.
(c) is a there-is claim too, but here a failed try proves nothing. To refute it you must check every candidate. The candidates are 25, 26, 27, and 25 = 5 \times 5, 26 = 2 \times 13, 27 = 3 \times 9, so none is prime and the claim is false. That worked because the collection to search was small. For a claim like “there is an odd perfect number” the collection is infinite, no example is known and no proof that none exists is known, so it remains an open conjecture.
A false conjecture, refuted exactly
Fermat noticed that F_n = 2^{2^n} + 1 gives 3, 5, 17, 257, 65537 for n = 0, 1, 2, 3, 4, and that all five are prime. He conjectured that every F_n is prime. Decide whether that is true by looking at n = 5.
SolutionThe next number is
Five primes in a row is strong agreement, but the claim is about every n, so the next case matters. Euler found in 1732 that F_5 is not prime. To show that it really fails, write out a factorization that the reader can multiply for themselves:
and check the product, splitting 641 as 600 + 41, since 600 \times 6700417 = 4020250200 and 41 \times 6700417 = 274717097:
Both factors are larger than 1, so F_5 is composite. The conjecture is false, and one failing n was enough.
The story did not end there. Every F_n with 5 \le n \le 32 has since been shown to be composite, and no Fermat number beyond F_4 is known to be prime. Whether some larger F_n is prime is a new open question that grew from the refuted conjecture.
A conjecture that becomes a theorem
Add two neighboring triangular numbers. The triangular numbers are T_n = 1 + 2 + \dots + n, so T_1 = 1, T_2 = 3, T_3 = 6, and so on. Find a pattern, state it exactly, test it once beyond the table, and then settle it.
SolutionCompute T_n + T_{n+1} for the first few n:
| n | T_n + T_{n+1} | total |
|---|---|---|
| 1 | 1 + 3 | 4 = 2^2 |
| 2 | 3 + 6 | 9 = 3^2 |
| 3 | 6 + 10 | 16 = 4^2 |
| 4 | 10 + 15 | 25 = 5^2 |
| 5 | 15 + 21 | 36 = 6^2 |
| 6 | 21 + 28 | 49 = 7^2 |
Every total is a square, and it is the square of n + 1. So the conjecture, with its collection named, is: for every whole number n \ge 1, T_n + T_{n+1} = (n + 1)^2.
A test beyond the table: T_7 = 28 and T_8 = 36, and 28 + 36 = 64 = 8^2. It holds again.
The picture in Figure 2 shows why. A square array of dots with n{+}1 dots on each side holds (n{+}1)^2 dots in all. Cut it along a diagonal, with the diagonal’s own dots on one side. One piece has 1, 2, 3, \dots dots in its rows, and the other has one fewer in each row. The two pieces are two neighboring triangular numbers.
The picture suggests the argument, and algebra makes it complete for every n. Since \displaystyle T_n = \frac{n(n+1)}{2},
The steps are allowed because the common factor n + 1 can be taken out of both fractions, and then n + (n + 2) = 2n + 2 = 2(n+1). The conjecture now has a proof that covers every n, so it is a theorem.
The same five terms, three different sixth terms
The first five terms of a list are 1, 2, 4, 8, 16. Give three rules that fit all five terms and have three different sixth terms.
SolutionThe first rule is the obvious one: double each time, so the nth term is 2^{n-1}. Its sixth term is 32.
For a second rule, look at the differences between neighboring terms, then the differences of those, and so on.
| level | values |
|---|---|
| terms | 1, 2, 4, 8, 16, and then 31 |
| first differences | 1, 2, 4, 8, and then 15 |
| second differences | 1, 2, 4, and then 7 |
| third differences | 1, 2, and then 3 |
| fourth differences | 1, and then 1 |
Five terms leave only one fourth difference, which is 1. Suppose the next fourth difference is also 1. Working back up the table, the third differences continue 3, the second differences continue 7, the first differences continue 15, and the terms continue with 16 + 15 = 31. A rule whose fourth differences are always 1 is a polynomial of degree 4 with leading coefficient \displaystyle \frac{1}{4!} = \frac{1}{24}, and the one through these five terms is
Putting in n = 1, 2, 3, 4, 5, 6 gives 1, 2, 4, 8, 16, 31. The second rule fits all five terms, and its sixth term is 31.
For a third rule, use the idea behind “the next value is free”. Let
This product is zero at n = 1, 2, 3, 4, 5, so adding any multiple of it to p changes nothing at those five cases. At n = 6 it is P(6) = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120. To reach 100 at n = 6, add c times P with 31 + 120c = 100, so \displaystyle c = \frac{23}{40}:
This fits the five terms, and \displaystyle q(6) = 31 + \frac{23}{40} \cdot 120 = 100.
So the terms 1, 2, 4, 8, 16 are continued by 32, by 31 and by 100, each by a rule that fits every term given. Nothing in the five terms chooses between them.
Dots on a circle, and subsets of a set
Use the result for R_n to count the regions when 5 points and when 6 points are marked on a circle, and compare with doubling. Then compare with a second list: the number of subsets of a set with n elements, counting the empty set, is 1, 2, 4, 8, 16 for n = 0, 1, 2, 3, 4, the same numbers as the first five region counts. Show that the subset counts really do keep doubling, and show where the region counts stop doing so.
SolutionFor five points, \binom{5}{2} = 10 and \binom{5}{4} = 5, so R_5 = 1 + 10 + 5 = 16. For six points, \binom{6}{2} = 15 and \binom{6}{4} = 15, so R_6 = 1 + 15 + 15 = 31.
Figure 3 shows both. The points are placed so that no three chords meet at a point, which the formula needs. The left circle has 5 crossings inside it and the right one has 15, the values of \binom{5}{4} and \binom{6}{4}, and counting the regions in the picture gives 16 and 31.
Carrying on, the formula gives more of the list, set beside doubling:
| n | \binom{n}{2} | \binom{n}{4} | R_n | 2^{n-1} |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 1 |
| 2 | 1 | 0 | 2 | 2 |
| 3 | 3 | 0 | 4 | 4 |
| 4 | 6 | 1 | 8 | 8 |
| 5 | 10 | 5 | 16 | 16 |
| 6 | 15 | 15 | 31 | 32 |
| 7 | 21 | 35 | 57 | 64 |
| 8 | 28 | 70 | 99 | 128 |
The two columns agree for five cases and then drift apart, slowly at first (31 against 32) and then faster. Five agreements did not make R_n a power of two.
Now the subsets. Take a set with n + 1 elements and single out one element x. Every subset either leaves x out or has x in it. The subsets that leave x out are exactly the subsets of the other n elements. The subsets that have x in are those same subsets with x added, one for each. So the two piles have equal size and the total is double: the number of subsets of an (n+1)-element set is twice the number for an n-element set. The argument never used a particular n, so it covers every n. This is a reason, and the count is 2^n for ever. A 5-element set has 32 subsets, a 10-element set has 1024.
For regions, doubling from R_n to R_{n+1} would mean that the new point adds exactly R_n regions. By the formula and Pascal’s rule, \binom{n+1}{4} - \binom{n}{4} = \binom{n}{3} and \binom{n+1}{2} - \binom{n}{2} = \binom{n}{1}, so
Setting that beside R_n:
| n | regions added, \binom{n}{3} + n | R_n | equal? |
|---|---|---|---|
| 1 | 1 | 1 | yes |
| 2 | 2 | 2 | yes |
| 3 | 4 | 4 | yes |
| 4 | 8 | 8 | yes |
| 5 | 15 | 16 | no |
| 6 | 26 | 31 | no |
| 7 | 42 | 57 | no |
The step from one case to the next holds for n = 1, 2, 3, 4 and fails at n = 5 and every case after it. Both lists start 1, 2, 4, 8, 16. One has a step that works for every n, and the other has a step that happens to work four times.
A reason that covers every case
Add the first few odd numbers and find a rule. Then show that the rule holds for every n.
SolutionWrite S_n = 1 + 3 + 5 + \dots + (2n - 1), the sum of the first n odd numbers. The first few:
| n | S_n |
|---|---|
| 1 | 1 |
| 2 | 1 + 3 = 4 |
| 3 | 4 + 5 = 9 |
| 4 | 9 + 7 = 16 |
| 5 | 16 + 9 = 25 |
They are 1^2, 2^2, 3^2, 4^2, 5^2, so the rule is S_n = n^2. So far this is a pattern and nothing more.
The reason comes from looking at how one case leads to the next. The sum S_{n+1} is S_n with one more odd number added, and the odd number after 2n - 1 is 2n + 1. So S_{n+1} = S_n + (2n + 1).
Now suppose that for some whole number n we know S_n = n^2. Then
because n^2 + 2n + 1 is the square of n + 1. So if the rule holds at n, it holds at n + 1. It does hold at n = 1, and therefore at 2, and so at 3, and so on without end.
The step used n as a letter and needed nothing about it except that it is a whole number. That is what makes it a proof, and it is what the dots on the circle did not have: there the step from n to n + 1 failed at n = 5, as Example 6 shows. The idea of passing from each case to the next is worked out fully in proof by induction, and the parts of such an argument, with a sum formula like this one as a case, are set out in base case, hypothesis and step.
When finitely many checks are a proof
Show that n^3 - n is a multiple of 6 for every whole number n \ge 0, by checking only six values of n.
SolutionThe six values are n = 0, 1, 2, 3, 4, 5:
| n | n^3 - n | multiple of 6? |
|---|---|---|
| 0 | 0 | yes, 6 \cdot 0 |
| 1 | 0 | yes, 6 \cdot 0 |
| 2 | 6 | yes, 6 \cdot 1 |
| 3 | 24 | yes, 6 \cdot 4 |
| 4 | 60 | yes, 6 \cdot 10 |
| 5 | 120 | yes, 6 \cdot 20 |
Six checks would settle nothing on their own. They settle this claim because of one more fact, that the value at n + 6 is the value at n plus a multiple of 6. Write D(n) = n^3 - n. Expanding,
So if n^3 - n is a multiple of 6, so is the value six steps on. Every whole number n \ge 6 is six more than a smaller whole number n - 6 \ge 0. Starting from the six checked cases, the case 6 follows from case 0, case 7 from case 1, and so on through every whole number.
Here a finite check is a proof, but the proof is the argument that the checks need and not the checks themselves. Take the argument away and the six agreeing cases are six more dots on a graph.
Repairing a false conjecture
Draw a rectangle, a rhombus and a parallelogram with both diagonals. In each, the diagonals cut each other into equal halves. State the conjecture this suggests, test it on a kite, and repair it.
SolutionThe conjecture: in every quadrilateral, the two diagonals bisect each other. That means each diagonal crosses the other at its midpoint.
A good test is a shape unlike the ones that suggested it. A kite has two pairs of equal sides, but each pair meets at a corner instead of the equal sides sitting opposite each other. In Figure 4, take the kite with corners at (0, 6), (-3, 2), (0, -4) and (3, 2), which has sides \displaystyle 5, 5, \sqrt{45}, \sqrt{45}.
The horizontal diagonal runs from (-3, 2) to (3, 2), with midpoint (0, 2). The vertical diagonal runs from (0, 6) to (0, -4), with midpoint (0, 1). The diagonals cross at (0, 2). That is the midpoint of the horizontal one and not of the vertical one, since (0, 2) \ne (0, 1). The conjecture fails, and this kite is a counterexample.
What survives? The claim still held in the parallelogram, rhombus and rectangle, and the kite failed because it is none of those. Narrow the collection:
in every parallelogram, the two diagonals bisect each other.
The kite no longer belongs to the claim, so it cannot break it. This is a new conjecture, and it does need its own proof: the proof is a separate lesson, and the result is a theorem about the diagonals of a parallelogram. The kite kept something, too: the diagonal joining the two corners where equal sides meet does bisect the other one, which is a true fact about kites.
A strong conjecture and a weaker one
The weak Goldbach conjecture says that every odd whole number greater than 5 is a sum of three primes. Show that it follows from Goldbach’s original conjecture, and use the argument to write 21 as a sum of three primes.
SolutionCall Goldbach’s original claim A (every even number greater than 2 is a sum of two primes) and the weak claim B. To show that A implies B, suppose A is true and take any odd number n > 5.
Then n - 3 is even, and n - 3 > 2. By A, n - 3 = p + q for some primes p and q. So n = 3 + p + q, which is a sum of three primes. The prime 3 was chosen because subtracting an odd prime from an odd number leaves an even number, which is what A speaks about.
For n = 21: 21 - 3 = 18 = 5 + 13, so 21 = 3 + 5 + 13.
So A \Longrightarrow B, and A is the stronger claim. In practice the order shows: a proof of the weak conjecture was put forward in 2013 and is widely accepted, while the original, stronger one is still open. Proving the weak one could not prove the strong one, since the implication only runs from strong to weak.
A failure that no search would find
Is 991n^2 + 1 ever a perfect square, for a whole number n \ge 1? Test the first few n, and then look at where the first failure of “never” is.
SolutionThe first few cases: n = 1, 2, 3 give 992, 3965, 8920. Since 31^2 = 961 < 992 < 1024 = 32^2, and 62^2 = 3844 < 3965 < 3969 = 63^2, and 94^2 = 8836 < 8920 < 9025 = 95^2, none of the three is a square. A computer can run through n up to a billion in moments, and every one of those fails to be a square as well. The claim that 991n^2 + 1 is never a square looks entirely safe.
It is false. The equation x^2 - 991y^2 = 1 is an old kind of equation, called a Pell equation, and its smallest solution in whole numbers with y \ge 1 is
That is, 991y^2 + 1 = x^2 for these two numbers, which a computer confirms by multiplying them out. That no smaller n works is not found by testing smaller values, which would never finish. It comes from the theory of Pell equations: every solution appears among the fractions x/y that approximate \displaystyle \sqrt{991} in its continued fraction, which come in increasing size, and this is the first of them that works. So the claim holds for every n below 1.2 \times 10^{28} and fails at the number above.
A machine testing a billion values of n a second would need hundreds of billions of years to get there (exercise 19). No amount of testing would ever have met the failure; it was found by an argument about the equation.
Digits can mislead in the same way. The number \displaystyle e^{\pi\sqrt{163}} starts 262537412640768743.99999999999925\ldots and the digits after the point begin with twelve nines in a row. A reader who stopped there would guess that the number is the whole number 262537412640768744. It is not: a computation that keeps track of its own rounding error shows the whole number is larger by 7.4992740\ldots \times 10^{-13}, which is small and is not zero. Agreement to thirty figures still did not make a whole number.
A precise conjecture with huge evidence and no proof
Start with a positive whole number. If it is even, halve it. If it is odd, triple it and add 1. Repeat. The Collatz conjecture says that every positive whole number eventually reaches 1. Follow the rule from 6 and from 27, and say what would disprove the conjecture.
SolutionFrom 6:
That is 8 steps. After 1 the rule gives 4, then 2, then 1 again, so 1 is where it settles, into the loop 1, 4, 2, 1, \dots.
From 27 the sequence is much wilder. It takes 111 steps to reach 1, and on the way it climbs as high as 9232 before falling. Nothing about 27 hints at that.
Computers have followed the rule from every starting number up to at least 2^{68}, which is about 3 \times 10^{20}, and every one of them reaches 1. Yet nobody has a proof, and nobody knows what a proof would even use.
A disproof would be a starting number whose sequence never reaches 1. There are two ways that could happen. The sequence could come back to a value it had before without passing through 1, which traps it in a different loop, and that loop could be written out and checked. Or the sequence could grow forever, and no finite list can display that. So even if the conjecture is false, a counterexample might be impossible to show.
The statement could hardly be simpler or more exact, and it is still open. Being precise is not the same as being easy.
Boundaries
It must be a statement. A question, an instruction or a matter of taste has no truth value and cannot be a conjecture. “Find the largest prime” is an instruction, and “primes are interesting” is an opinion.
It must be precise. If a word in the claim has no definite meaning (“large”, “nice”, “usually”), then nobody can tell what a counterexample would be, and the claim cannot be tested. Stating the collection it is about, and whether edge cases count, is part of the statement.
It stops being a conjecture when it is settled. A proved claim is a theorem and a refuted one is false. Claims that are already known, such as “every whole number is a sum of four squares”, are not conjectures.
It is not an axiom. An axiom is accepted without proof on purpose, as a starting point. A conjecture is waiting for a proof and is not yet used as one.
Open does not always mean unsettled for good. For a few statements it has been shown that the standard axioms cannot decide them either way, the continuum hypothesis among them. Such a statement is in a state none of the three above describes, and most named conjectures are not known to be of that kind.
Checking every case is a proof. A claim with finitely many cases is settled by going through all of them: “every even number from 4 to 30 is a sum of two primes” is a finite claim, and the fourteen cases of Example 1 settle it. A claim about infinitely many cases can also be settled by finitely many checks, but only when a theorem shows that finitely many cases cover the rest: two polynomials of degree at most d are the same once they agree at d + 1 values (exercises 22 and 24), and the multiples of 6 in Example 8 needed a repeat after six steps (exercise 23). Without such a theorem the checks are a pattern, and checking finitely many cases of an infinite claim is where the gap opens.
A pattern is not a false claim. Plenty of patterns are true, like the one for the odd numbers, and one failing check still ends a false one. What this lesson says is about what agreeing cases have shown, which is less than what they suggest.
The region formula needs general position. The count R_n assumes that no three chords pass through one point. Six points at the corners of a regular hexagon break that, since the three long diagonals meet in the center, and they make 30 regions, not 31 (exercise 17).
Simplicity is a guide and not a guarantee. It is natural to prefer the simple rule, and it is often right to. But “the simplest rule that fits” is a habit and not a theorem: the simple rule 2^{n-1} is wrong for the circle, and the true rule for the circle is the degree-4 polynomial of Example 5, with nothing about it to suggest it in advance.
Mathematical evidence is not statistical evidence. In a science, repeated observation is the ordinary way to learn, and in hypothesis testing a hypothesis is a claim about a population, tested against data, which can only make it more or less plausible. A mathematical conjecture is about exact cases and is settled by a proof or a single counterexample, never by a sample. The word “hypothesis” is also used for the “if” part of an if-then statement (conditionals and their converses), which has nothing to do with guessing.
Where this goes next
Once a conjecture is on the table, the work splits in two. One side tries to break it. Searching for the failing case, and knowing what a single failure proves, is counterexamples; for claims about shapes it continues in conjectures and counterexamples. The other side tries to settle it for good, with a reason that covers a general n: direct proof begins from what is known and reaches the claim, and proof by induction is the tool built for claims about every whole number, using exactly the step from each case to the next that the odd numbers showed.
The guessing itself has a name too, inductive reasoning: going from cases to a general claim. It is how conjectures are made, and it stops exactly where a conjecture begins. Proving them is deductive reasoning, and this lesson sits at the join between the two. Once proved, a conjecture takes its place in the map under theorem, lemma and corollary, and some of the most famous results began as conjectures, such as the four color theorem. Questions about primes are a rich source of new ones, including the gaps between primes and perfect numbers.
The circle count is also a first taste of a method worth having: counting the same picture two ways, once by its faces and once by its corners and edges, which is what Euler’s formula does. And the region formula is built from binomial coefficients, the same numbers that run through Pascal’s triangle.
Exercises
Stating and testing
- Find every way to write 34 as a sum of two primes p + q with p \le q.
- Write “a whole number ending in 5 is a multiple of 5” as a for-every statement, and prove it.
- Find the sum of the first n cubes, 1^3 + 2^3 + \dots + n^3, for n = 1, 2, 3, 4, 5. Compare each with the triangular number T_n and state a conjecture.
- Apply the Collatz rule (halve if even, triple and add 1 if odd) and count how many steps it takes to reach 1 from 12 and from 9.
- Use the theorem of Example 4 to find T_{49} + T_{50} without finding either number.
Refuting
- Conjecture: 6n + 1 is prime for every positive whole number n. Test n = 1, 2, 3, 4 and say what you find.
- Conjecture: the product of two irrational numbers is always irrational. Refute it, using the fact that \displaystyle \sqrt{2} is irrational (the irrationality of the square root of two).
- Conjecture: doubling every side of a rectangle doubles its area. Test it on a 3 by 5 rectangle and say what you find.
- Conjecture: every whole number greater than 3 is a sum of two primes. Find the smallest counterexample.
- Conjecture: n^2 + n + 41 is prime for every whole number n \ge 0. Test n = 0, 1, 2, and find a value of n that refutes it.
Which way one case cuts
- For each claim, say whether it is for-every or there-is, and whether finding one example proves it, disproves it, or settles nothing. (a) There is a whole number whose square is 169. (b) Every prime leaves remainder 1 when divided by 4. (c) There is a prime between 32 and 36. (d) Every multiple of 4 is even.
- Show that 8128 is a perfect number, and say what that settles about the claim “there is a perfect number greater than 496”.
One list, many futures
- The terms 2, 4, 6, 8, 10 are fitted by the rule “the nth term is 2n”, which gives 12 next. Give a second rule that fits the same five terms and gives 132 as the sixth term.
- Give a formula f(n) with f(1), f(2), f(3), f(4) = 1, 2, 4, 8 and f(5) = 100.
Dots on a circle
- Use the formula for R_n to find the number of regions for 7, 8 and 9 points, with no three chords through a point.
- Find R_{10} and compare it with 2^9. Then use R_{n+1} - R_n = \binom{n}{3} + n, from Example 6, to find R_{11} from R_{10}.
- Six points are the corners of a regular hexagon. The three chords joining opposite corners all pass through the center, and no other three chords meet at a point. How many regions do the chords make, and why is it not 31?
Long runs
- The claim is that 13n^2 + 1 is never a perfect square. Show that it holds for n = 1, 2, 3, 4, and show that n = 180 breaks it. Is 180 the first n to do so?
- A machine tests a billion values of n a second. About how many years would it take to reach n = 12055735790331359447442538767, the n of Example 11? Use a year of 3.16 \times 10^7 seconds and give the answer to two significant figures.
Patterns with a reason
- Add the first n even numbers, 2 + 4 + \dots + 2n, for n = 1, 2, 3, 4, 5, and state the rule the sums follow. Then show that n(n+1) + 2(n+1) = (n+1)(n+2), and explain what this says about going from the rule at case n to the rule at case n + 1.
- Add pairs of consecutive odd numbers: 1 + 3, 3 + 5, 5 + 7, 7 + 9. State a conjecture about the sums and prove it.
When finitely many checks are enough
- The two sides of (n+1)^3 = n^3 + 3n^2 + 3n + 1 are both polynomials of degree 3. Show that they agree at n = 0, 1, 2, 3, and explain why four agreements are enough for every n.
- Show that n^3 - n is divisible by 6 at n = 0, \dots, 5. Then, with D(n) = n^3 - n as in Example 8, find the multiple of 6 by which D(n + 6) differs from D(n) for n = 2.
- Let f(n) = n^2 + 3n + 1 and g(n) = n^2 + 3n + 1 + n(n-1)(n-2). They agree at n = 0, 1, 2. Why do these three agreements not show that f and g are the same rule, and what do f(3) and g(3) give?
Stronger and weaker
- Twin prime conjecture: there are infinitely many primes p for which p + 2 is also prime. Bounded gaps: there are infinitely many pairs of primes that differ by at most 246. The second has been proved. Which claim is stronger, and what does the proof of the second settle about the first?
- Use the method of Example 10 to write 41 as a sum of three primes.
- Conjecture A implies conjecture B, and B is disproved. What follows about A? What would follow if only A were disproved?
Reasoning
- Goldbach’s conjecture is open. Explain why it is nevertheless either true or false, and not “neither”.
- A computer search finds no failure of Goldbach’s conjecture for any even number up to 10^{18}. Explain what this shows and what it does not.
- Explain why each of these is not a conjecture in the sense of this lesson. (a) Large numbers are interesting. (b) 7 + 8 = 16. (c) Every whole number is a sum of four squares. (d) Solve x^2 = 9.
- Explain in your own words why the terms 1, 2, 4, 8, 16 do not force the next term to be 32.
- For a whole number N, describe a claim about n that holds for n = 1, 2, \dots, N and fails at n = N + 1. Write it out for N = 1000.
- The subset counts and the region counts both begin 1, 2, 4, 8, 16. Explain what the argument for the subsets supplies that the list of numbers does not.
- The claim 2^n > n^2 is about every whole number n \ge 1. Tabulate 2^n and n^2 for n = 1, \dots, 8 and say where the claim holds and where it fails. Does the run of successes at the end show it holds for every n \ge 5?
- Prove 1 + 3 + \dots + (2n - 1) = n^2 in a different way from Example 7: write the sum twice, the second time in reverse order, and add column by column.
- Show that 641 divides 2^{32} + 1, using 641 = 5^4 + 2^4 and 641 = 5 \cdot 2^7 + 1.
Answers
- 3 + 31, 5 + 29, 11 + 23, 17 + 17. Try each prime p up to 17 and keep it when 34 - p is prime too: p = 2, 7, 13 give 32, 27, 21, none prime.
- For every whole number n ending in 5, n is a multiple of 5. Such a number is 10k + 5 for some whole number k \ge 0, and 10k + 5 = 5(2k + 1), a multiple of 5.
- The sums are 1, 9, 36, 100, 225. The triangular numbers T_1, \dots, T_5 are 1, 3, 6, 10, 15, and 1 = 1^2, 9 = 3^2, 36 = 6^2, 100 = 10^2, 225 = 15^2. Conjecture: for every whole number n \ge 1, 1^3 + 2^3 + \dots + n^3 = T_n^2. (The conjecture is true, and proof by induction settles it.)
- 12 takes 9 steps: 12, 6, 3, 10, 5, 16, 8, 4, 2, 1. 9 takes 19 steps: 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, and then 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
- T_{49} + T_{50} = 50^2 = 2500. The theorem with n = 49 says T_{49} + T_{50} = (49 + 1)^2.
- n = 1, 2, 3 give 7, 13, 19, all prime, but n = 4 gives 25 = 5 \times 5, which is not. The conjecture is false, refuted by n = 4.
- \displaystyle \sqrt{2} \times \sqrt{2} = 2. Both factors are irrational and the product is the rational number 2, so the conjecture is false.
- A 3 by 5 rectangle has area 15. Doubling the sides gives 6 by 10, area 60, which is 4 times 15 and not 2 times. The conjecture is false, and in fact the area always quadruples.
- The smallest counterexample is 11. The numbers 4 to 10 all work (4 = 2 + 2, 5 = 2 + 3, 6 = 3 + 3, 7 = 2 + 5, 8 = 3 + 5, 9 = 2 + 7, 10 = 3 + 7), but 11 - 2 = 9, 11 - 3 = 8, 11 - 5 = 6 and 11 - 7 = 4, and none of 9, 8, 6, 4 is prime; there are no other primes below 11.
- n = 0, 1, 2 give 41, 43, 47, all prime. The smallest failure is n = 40: 40^2 + 40 + 41 = 1681 = 41 \times 41. The conjecture is false, after 40 agreeing cases.
- (a) There-is. One example, 13, proves it. (b) For-every. One example disproves it: 3 leaves remainder 3. (c) There-is. One example would prove it, but there is none: the candidates 33 = 3 \times 11, 34 = 2 \times 17 and 35 = 5 \times 7 are all composite, so it is false, but only checking every candidate shows that; one failed try settles nothing. (d) For-every. No number of examples proves it. A proof writes a multiple of 4 as 4k = 2(2k), which is even.
- The divisors of 8128 below itself are 1, 2, 4, 8, 16, 32, 64, which add to 127, and 127 times each of 1, 2, 4, 8, 16, 32, which adds to 127 \times 63 = 8001, and 127 + 8001 = 8128. So 8128 is perfect. The claim is a there-is claim and 8128 > 496, so this one example proves it.
- 2n + (n-1)(n-2)(n-3)(n-4)(n-5). The product is 0 at n = 1, \dots, 5, so the rule gives 2, 4, 6, 8, 10, and at n = 6 it gives 12 + 120 = 132.
- \displaystyle f(n) = 2^{n-1} + \frac{7}{2}(n-1)(n-2)(n-3)(n-4). The product is 0 at n = 1, \dots, 4, so f gives 1, 2, 4, 8, and \displaystyle f(5) = 16 + \frac{7}{2} \cdot 24 = 16 + 84 = 100.
- R_7 = 1 + 21 + 35 = 57, R_8 = 1 + 28 + 70 = 99 and R_9 = 1 + 36 + 126 = 163.
- R_{10} = 1 + 45 + 210 = 256, while 2^9 = 512, so R_{10} is exactly half of 2^9. For n = 10 the step is \binom{10}{3} + 10 = 120 + 10 = 130, so R_{11} = 256 + 130 = 386.
- 30 regions. Draw the chords one at a time. A chord adds one region, and one more for each different point where it meets chords already drawn. So the count is 1 + 15 for the 15 chords, plus the number of such meetings. With no three chords through a point, each of the 15 pairs of crossing chords gives one meeting, which makes 1 + 15 + 15 = 31. In the hexagon, 12 of the crossings are ordinary and give one meeting each. The center gives only 2 meetings, because the third long chord meets the first two at the one point, where separate crossings would have given 3. So the count is 1 + 15 + 12 + 2 = 30.
- For n = 1, 2, 3, 4 the values are 14, 53, 118, 209, and 3^2 = 9 < 14 < 16 = 4^2, 7^2 = 49 < 53 < 64 = 8^2, 10^2 = 100 < 118 < 121 = 11^2, 14^2 = 196 < 209 < 225 = 15^2, so none is a square. For n = 180: 13 \cdot 180^2 + 1 = 13 \cdot 32400 + 1 = 421201, and 421201 = 649^2. Yes, 180 is the first, since a search of n = 1, \dots, 179 finds no square.
- About 3.8 \times 10^{11} years. The number of seconds is about 1.2 \times 10^{28} \div 10^9 = 1.2 \times 10^{19}, and dividing by 3.16 \times 10^7 seconds a year gives about 3.8 \times 10^{11} years.
- The sums are 2, 6, 12, 20, 30, which are 1 \cdot 2, 2 \cdot 3, 3 \cdot 4, 4 \cdot 5, 5 \cdot 6, so the rule is 2 + 4 + \dots + 2n = n(n+1). Expanding gives n^2 + n + 2n + 2 = n^2 + 3n + 2, which factors as (n+1)(n+2). If the sum of the first n even numbers is n(n+1), then adding the next even number 2(n+1) gives n(n+1) + 2(n+1) = (n+1)(n+2), which is the rule at n + 1. So the rule at any case forces it at the next, and with the rule true at n = 1 it holds for every n.
- Every sum is a multiple of 4: 4, 8, 12, 16. Write the two odd numbers as 2k + 1 and 2k + 3, so the sum is 4k + 4 = 4(k + 1), a multiple of 4 for every whole number k \ge 0.
- At n = 0, 1, 2, 3 the left side is 1, 8, 27, 64 and the right side is 1, 1 + 3 + 3 + 1 = 8, 8 + 12 + 6 + 1 = 27 and 27 + 27 + 9 + 1 = 64. They agree. The difference of the two sides is a polynomial of degree at most 3 that is 0 at four values of n, and by the factor theorem a nonzero polynomial of degree at most 3 has at most 3 such values. So the difference is the zero polynomial, and the sides agree at every n.
- The values at n = 0, \dots, 5 are 0, 0, 6, 24, 60, 120, all multiples of 6. For n = 2, (2+6)^3 - (2+6) = 504 and 2^3 - 2 = 6, which differ by 498 = 6 \cdot 83, matching 6(3n^2 + 18n + 35) at n = 2, which is 6 \cdot 83.
- Their difference n(n-1)(n-2) is a polynomial of degree 3, and a polynomial of degree 3 is zero at up to three values of n without being the zero polynomial. Three agreements are not enough, and a fourth check is needed. At n = 3, f(3) = 19 and g(3) = 19 + 6 = 25, so they differ.
- The twin prime conjecture is stronger: if there are infinitely many pairs differing by 2, there are infinitely many differing by at most 246. So proving the twin prime conjecture would prove bounded gaps. The reverse does not hold. Proving bounded gaps settles nothing about the twin prime conjecture, which stays open.
- 41 = 3 + 7 + 31. Here 41 - 3 = 38, and 38 = 7 + 31 with both primes.
- A is disproved as well. If A were true, B would be true, but B is false. If only A were disproved, nothing follows about B, which might still be true.
- A precise statement about a named collection holds for every member or it does not. Goldbach’s statement is one of these, so it is true or false, and only our knowledge of which is missing.
- It shows that any counterexample to Goldbach’s conjecture is larger than 10^{18}, and it is strong evidence. It does not prove the conjecture, because infinitely many even numbers are unchecked. Only a proof can settle it.
- (a) “Interesting” has no definite meaning, so it is not precise. (b) It is a statement, but it is false and known to be false (7 + 8 = 15), so it is not open. (c) It is a statement and precise, but it has already been proved, so it is a theorem. (d) It is an instruction, not a statement, and has no truth value.
- The five terms are all that has been given, and many different rules fit them: doubling gives 32, the degree-4 polynomial gives 31, and by the result that the next value is free there is a rule for any sixth term at all. The terms say nothing about which rule is meant, so they cannot fix the next term. Only a reason, such as a proof about the rule, can.
- Take the claim “the nth term of 2n + (n-1)(n-2)\cdots(n-N) is 2n”. The product has a factor 0 at each of n = 1, \dots, N, so the claim holds there, and at n = N + 1 the product is N!, which is not 0, so it fails. For N = 1000: 2n + (n-1)(n-2)\cdots(n-1000), which equals 2n for n = 1, \dots, 1000 and equals 2002 + 1000! at n = 1001.
- The argument shows why each subset count is double the one before it, for every n, so that the doubling is guaranteed and is not just observed. The list 1, 2, 4, 8, 16 is the same in both situations and cannot show the difference. For the regions, the matching argument fails: the step from n to n + 1 adds \binom{n}{3} + n regions and that equals R_n only for n \le 4.
- The values of 2^n are 2, 4, 8, 16, 32, 64, 128, 256 and of n^2 are 1, 4, 9, 16, 25, 36, 49, 64. The claim holds at n = 1 (2 > 1), fails at n = 2 (4 = 4), n = 3 (8 < 9) and n = 4 (16 = 16), and holds at n = 5, 6, 7, 8. Four successes in a row do not prove it for every n \ge 5, for the same reason as always: they are four cases. It is in fact true for every n \ge 5, but that needs an argument from each case to the next, as in proof by induction.
- Let S = 1 + 3 + \dots + (2n-1). Written in reverse, S = (2n-1) + (2n-3) + \dots + 1. Adding the two lines column by column, each column is (2k - 1) + (2(n - k + 1) - 1) = 2n, and there are n columns, so 2S = n \cdot 2n = 2n^2 and S = n^2. The steps do not depend on which n was taken, so this covers every n.
- From 641 = 5^4 + 2^4 we get 5^4 \equiv -2^4 \pmod{641}. From 641 = 5 \cdot 2^7 + 1 we get 5 \cdot 2^7 \equiv -1, and raising both sides to the fourth power gives 5^4 \cdot 2^{28} \equiv 1. Substituting the first into the second gives -2^4 \cdot 2^{28} \equiv 1, which is 2^{32} \equiv -1, so adding 1 to both sides gives 2^{32} + 1 \equiv 0 \pmod{641}, and 641 divides it.