Counterexamples and Conjectures - Forms of Argument

Mathematical Writing - Vivaldi Franco 2014

Counterexamples and Conjectures
Forms of Argument

Suppose that a statement concerning all elements of a set is false. To prove this, it is sufficient to exhibit a single element of that set for which the statement fails. This argument is called a counterexample. In symbols, we show that the statement

$$ \forall x\in X,\,\,{\fancyscript{P}}(x) $$

is false by proving its negation, namely

$$ \exists x\in X,\,\,\lnot {\fancyscript{P}}(x). $$

To explore the idea of a counterexample, let us consider a famous polynomial proposed by Euler: $$p(n)=n^2+n+41$$. We evaluate $$p(n)$$ at integer values of the indeterminate: $$n=0,1,\ldots $$.

$$ \begin{array}{c|cccccccccccccccc} n &{} 0&{} 1 &{} 2 &{} 3&{}4&{}5&{}6&{}7&{}8&{}9&{}10&{}\cdots &{}20&{}\cdots &{}30\\ \hline p(n)&{}41&{}43&{}47&{}53&{}61&{}71&{}83&{}97&{}113&{}131&{}151&{}\cdots &{}461&{}\cdots &{}971 \end{array} $$

All these values of $$p(n)$$ are prime! Moreover, $$p(-n)=p(n-1)$$, so it seems plausible—if a bit daring—to put forward the following conjecture:

Conjecture 1. For all integers $$n$$, $$p(n)$$ is prime.

A conjecture is a statement that we wish were a theorem. Three things may happen to a conjecture: (i) someone proves it, and the conjecture becomes a theorem; (ii) someone produces a counterexample, and the conjecture is proved false; (iii) none of the above, and the conjecture remains a conjecture.

Our case is (ii). The negation of conjecture 1 is

There is an integer $$n$$ such that $$p(n)$$ is composite.

To prove it, we exhibit such a value of $$n$$. For $$n=40$$, we find

$$ p(40)=40^2+40+41=40(40+1)+41=41(40+1)=41^2. $$

So $$p(40)$$ is not prime, and conjecture 1 is false.

For a mathematician, the formulation of a conjecture is accompanied by the fear of a counterexample. Let us return to conjecture 1: we know it’s false, but can it be modified into a weaker statement? It can be verified that $$n=40$$ is the smallest value for $$n$$ for which $$p(n)$$ is not prime.4 Are there other such values? If these values were exceptional, then a meaningful weaker version of conjecture 1 could be

Conjecture 2. For all but finitely many integers $$n$$, $$p(n)$$ is prime.

Even if $$p(n)$$ were composite for, say, a billion values of $$n$$, the conjecture would still hold. Unfortunately, conjecture 2 is not true either. Its negation

There are infinitely many integers $$n$$ for which $$p(n)$$ is composite.

is established by the simple, devastating counterexample:

$$\begin{aligned} p(41k)=(41k)^2+41k+41=41(41k^2+k+1)\qquad k=1,2,\ldots \end{aligned}$$

(7.8)

which says that $$41$$ is a proper divisor of $$p(41k)$$ for infinitely many values of $$k$$.

Let’s make one final attempt to salvage something from our original claim.

Conjecture 3. There are infinitely many integers $$n$$ such that $$p(n)$$ is prime.

This is a very meaningful conjecture. Nobody has ever been able to prove that any quadratic polynomial with integer coefficients assumes infinitely many prime values. On the other hand, if we perform a numerical experiment we discover that, as $$n$$ increases, $$p(n)$$ continues to supply prime values, even though the composite values slowly become dominant (see Exercise 10.4.1). So this conjecture is very likely to be true, and it makes sense to put it forward.

Arguably, the most famous conjecture in mathematics is the Riemann’s hypothesis (RH), formulated in 1859. This conjecture (essentially) says that the zeta-function defined in Eq. (6.3), vanishes only at points whose real part is equal to $$1/2$$. The depth of this statement is not at all apparent from its idiosyncratic formulation.

In a sense, the mathematics community cannot afford to wait for this important matter to be settled, and several theorems about the RH have been proved. Some of these theorems formulate the RH in terms of equivalent statements, establishing the importance of the RH in many areas of mathematics. There are also proofs of conditional theorems, which assume the validity of the RH, and deduce some of its consequences.

Other famous conjectures include the twin-primes conjecture, attributed to Euclid:

There are infinitely many primes $$p$$ such that $$p+2$$ is also prime.

and the Goldbach conjecture 5:

Every even integer greater than 2 can be written as a sum of two primes.

Both conjectures are easy to formulate and widely believed to be true, but their proof seems hopelessly difficult. This situation is common in the theory of numbers, where assessing the difficulty of a problem is not always easy. To illustrate this phenomenon, let us arrange the natural numbers into four columns, with the primes highlighted in boldface:

$$\begin{aligned} \begin{array}{cccc} 1 &{}\mathbf 2&{}\mathbf{3} &{} 4 \\ \mathbf 5 &{} 6 &{}\mathbf{7} &{} 8 \\ 9 &{} 10 &{}\mathbf{11} &{} 12 \\ \mathbf{13} &{} 14 &{} 15 &{} 16 \\ \mathbf{17} &{} 18 &{}\mathbf{19} &{} 20 \\ 21 &{} 22 &{}\mathbf{23} &{} 24 \\ 25 &{} 26 &{} 27 &{} 28 \\ \mathbf{29} &{} 39 &{}\mathbf{31} &{} 32 \\ 33 &{} 34 &{} 35 &{} 36 \\ \mathbf{37} &{} 38 &{} 39 &{} 40 \\ \mathbf{41} &{} 42 &{}\mathbf{43} &{} 44 \\ 45 &{} 46 &{}\mathbf{47} &{} 48 \\ 49 &{} 50 &{} 51 &{} 52 \\ \mathbf{53} &{} 54 &{} 55 &{} 56 \\ 57 &{} 58 &{}\mathbf{59} &{} 60 \\ \vdots &{} \vdots &{} \vdots &{} \vdots \\ \end{array} \end{aligned}$$

We guide the reader through these data by asking some questions, arranged in order of increasing difficulty. (We have considered this form of exposition in Sect. 6.5.)

1.

2.

3.

4.

5.

6.

7.

8.

At the end of primary school, a pupil should be able to answer question 1, while in secondary school one could see why the answer to question 2 must be negative (one of three consecutive odd integers is divisible by 3). The answer to questions 3 to 7 is affirmative. Euclid’s theorem (Sect. 7.5), which answers question 3, is normally taught in a first year university course, although we have seen that the proof does not require advanced ideas. Answering questions 4 and 5 does involve some ingenuity, but no major difficulty.

The mathematics needed to answer 6 and 7 becomes difficult. The proof that column 1 contains infinitely many primes, known since the 17th Century, is given today in an undergraduate course in number theory. The formulation of question 7 can be made precise, and the affirmative answer was given at the end of the 19th Century. Understanding the proof requires a solid background in analysis.

Many mathematicians would conjecture that the answer to question 8 is again positive, but at present nobody knows how to prove it. This is a variant of the twin primes conjecture stated above.

An accessible introduction to this beautiful part of mathematics is found in [38].