Disproof by Counter Example

Sometimes we need to show that a claim is false. This can be done by finding a counterexample. Consider any claim of the form: . To show that the claim is false, we need to find a value of $x\in S$ for which P_x is true and Q_x is false.

That is, we need to prove the negation of the above claim: $\exists x\in S\mid P_x\wedge \overline Q_{x}$ . Finding any that supports the negation of the original claim is sufficient to disprove it.

Example

Disprove the following claim.

Claim: $\forall x,y\in\mathbb{R},\:(x+y)^{2} = x^{2} + y^{2}$

Counterexample: We need to show that $\exists x,y\in\mathbb{R},\:(x+y)^{2} \ne x^{2} + y^{2}$

A good idea is to try typical edge values, such as 1.

Let x=y=1 .

$\begin{array}{lcr} (x+y) ^{2} \: \: ? \: \: x^{2} + y^{2} \\ (1+1) ^{2} \: \: ? \: \: 1^{2} + 1^{2} \\ \: \: \: \: \: \: \: \: \: \: \: 4 \: \ne \: 2 \end{array}$

When x=y=1 , $(x+y)^{2} \ne x^{2} + y^{2}$ .
Thus disproving the original claim.

Of course, it is unusual to disprove a claim on the first attempt. If an inspection of the problem and some back-of-the-envelope calculations do not pan out, you may want to write a program to search for a counterexample.

A Fermat Number is a number of the form: f(x) = $2^{2^{x} }+1$ . Fermat numbers were first studied by mathematician Pierre de Fermat, who conjectured that all Fermat numbers are prime. Let’s try to disprove his conjecture claim.

Claim: $\forall x\in\mathbb{N},\:2^{2^x}+1 \text{ is prime. }$

Counterexample: We need to show that $\exists x\in\mathbb{N},\:2^{2^x}+1 \text{ is not prime. }$

A good idea is to try typical edge cases such as x=0 and x=1 .

	$2^{2^{x} }+1$	Prime?
0	3	✔
1	5	✔

That didn’t work, so let’s write a program to systematically try all values of x to see if there is break in the pattern.

First, we need a way to determine if $2^{2^{x} }+1$ is prime. Let’s write a method that returns the first prime divisor of a given number m. If the first prime divisor of the number m equals m, then the number m is prime.

public static BigInteger primeDivisor(BigInteger n ) {
   // All primes are greater than 1 
   if ( n.compareTo( BigInteger.ONE ) <= 0 )
      return BigInteger.valueOf( -1L );
   // 2 is the only even prime
   if ( n.mod( BigInteger.valueOf( 2L ) )
         .compareTo( BigInteger.ZERO ) == 0 ) 
      return BigInteger.valueOf( 2L ); 
   // Check for divisibility
   for( BigInteger i = BigInteger.valueOf( 3L ); 
        i.pow( 2 ).compareTo( n ) <= 0; 
        i = i.add( BigInteger.valueOf( 2L ) ) ) {
      // Does i divide n?
      if ( n.mod( i ).compareTo(BigInteger.ZERO) == 0 ) 
         return i; // n is not prime
    }
    return n; // n is prime
}

We use BigInteger values because the value of $2^{2^{x} }+1$ will get large very quickly and exceed the maximum number that can be stored in a long

The BigInteger Data Type
The BigInteger class is used for mathematical operations which involve very large numbers that are outside the limit of all available primitive data types. For integers, this means numbers smaller than -9223372036854775808 or larger than 9223372036854775807, which are Long.MIN_VALUE and Long.MAX_VALUE, respectively.

Now we write code to exhaustively try all values of x starting with 0. Well, not all values of x. We will stop when x is 30 to avoid integer overflow. Placing such a boundary on the search is pragmatic and recognizes that we may not be able to identify a counterexample with our available computing resources.

Let’s write the code to display each x and f(x) and indicate if f(x) is prime in a table.

// Print the header row
System.out.printf("%2s %-10s prime?%n", "x", "f(x)" );
// stop at x = 30 to prevent integer overflow
for( int x = 0; x <= 30; x++ ) {
   BigInteger result = 
       BigInteger.valueOf( 2L )
                 .pow( (int) Math.pow( 2, x ) )
                 .add( BigInteger.ONE);
   System.out.printf("%2d %-10s ", x, result );
   BigInteger divisor = primeDivisor( result );
   if ( divisor != result ) {
      // result is not prime
      System.out.printf("No: Divisible by %d%n", divisor );
      break;
   }
   // result is prime
   System.out.println( "Yes" );
}

The table generated by the above code is presented below.

	$2^{2^{x} }+1$	Prime?
0	3	Yes
1	5	Yes
2	17	Yes
3	257	Yes
4	65537	Yes
5	4294967297	No! Divisible by 641

When x=5 , $2^{2^{x} }$ is not prime. Thus disproving the original claim.

We are in good company. The conjecture was originally refuted by Leonhard Euler in 1732, but he had to do the calculations by hand.