The Lumenary · First-year graduate

Experimental mathematics: conjectures and counterexamples

Name: ______________________

Date: ______________________

You will learn to

Generate and test conjectures numerically, and design a counterexample search whose bounds are stated and whose completeness can be checked
Use high-precision arithmetic and integer-relation detection (PSLQ) to guess closed forms, and then prove them, as for the Bailey–Borwein–Plouffe formula
Explain with examples — Fermat numbers, Euler's conjecture, prime races, π(x) and li(x), Borwein integrals — why patterns that hold in many cases can fail
Assess computer-assisted proofs such as those of the four colour theorem and the Kepler conjecture, and how they were verified

1.
The Fermat numbers are $F_n = 2^{2^n} + 1$ . What is the smallest $n$ for which $F_n$ is not prime?
2.
Let $\varphi = (1 + \sqrt5)/2$ . Which vector is an integer relation for $(\varphi^2, \varphi, 1)$ ?
- A. $(1, -1, -1)$
- B. $(1, 1, -1)$
- C. $(2, -1, -3)$
- D. $(0, 0, 0)$
3.
Which of these are honest, adequately specified reports of a counterexample search for Goldbach's conjecture? (Choose all that apply.)
- A."Every even $n$ with $4 \le n \le 10^9$ is a sum of two primes; code, primality test and logs are archived."
- B."Our program ran for a week and found no counterexample."
- C."We tested $10^6$ even numbers chosen uniformly at random below $10^{20}$ (seed and generator recorded); all were sums of two primes."
- D."Exhaustive computer search confirms Goldbach's conjecture."
4.
At 100 digits, PSLQ finds a relation with coefficients of size below $100$ among six constants, with residual $10^{-95}$ ; at 200 digits the same relation holds to $10^{-195}$ . What may you claim?
- A.Strong numerical evidence for an exact identity, which should now be proved.
- B.A theorem: the identity holds.
- C.Nothing at all, since numerical computations are unreliable.
- D.The relation is probably spurious, because the coefficients are small.
5.
Among the primes $p \le 50$ , let $T$ be the number with $p \equiv 3 \pmod 4$ and $O$ the number with $p \equiv 1 \pmod 4$ . Compute $T - O$ .
6.
In the proof of the BBP formula, which step needs an analytic justification rather than algebra alone?
- A.Writing $\sum_k 2^{-(8k+j)/2}/(8k+j)$ as $\int_0^{1/\sqrt2} x^{j-1}/(1 - x^8)\,dx$ , i.e. integrating the geometric series term by term.
- B.The partial-fraction decomposition of $(16y - 16)/(y^4 - 2y^3 + 4y - 4)$ .
- C.Evaluating $\arctan(-1) = -\pi/4$ .
- D.Factoring $16 - y^8$ .
7.
With fermat n = 2 ^ (2 ^ n) + 1, which Lean statement says that Fermat's conjecture is false?
- A.¬ ∀ n, (fermat n).Prime
- B.∀ n, ¬ (fermat n).Prime
- C.∃ n, (fermat n).Prime
- D.¬ ∃ n, (fermat n).Prime
8.
Which conjecture would be refuted by a finite counterexample that a computer can check, whatever form the counterexample takes?
- A.Goldbach's conjecture: every even number greater than 2 is a sum of two primes.
- B.There are infinitely many twin primes.
- C.There are infinitely many Fermat primes.
- D.The Collatz conjecture.
9.
Write first_counterexample(pred, start, bound) that checks pred(n) for every integer n with start <= n <= bound in increasing order and returns the first n for which pred(n) is false, or None if there is none (an exhaustive search up to bound). Then use it to find the first prime p for which $2^p - 1$ is not prime. The helper is_prime is provided.
Computational — Practice

Answer key — Experimental mathematics: conjectures and counterexamples

1.
$F_0, \dots, F_4 = 3, 5, 17, 257, 65537$ are prime, but $F_5 = 2^{32} + 1 = 641 \cdot 6700417$ (Euler, 1732). So $n = 5$ . Fermat's five cases were evidence, not proof — and no Fermat prime beyond $F_4$ is known.
2.
$(1, -1, -1)$ , since $\varphi^2 = \varphi + 1$ . In general, $\alpha$ is algebraic of degree at most $d$ exactly when $(1, \alpha, \dots, \alpha^d)$ — or, equivalently here, $(\alpha^d, \dots, \alpha, 1)$ — has an integer relation; this is how PSLQ is used to recognise algebraic numbers.
3.
(a) and (c). Both specify the searched set (an initial segment, or a recorded random sample) and make the work checkable; (c) is evidence of a different kind from (a). (b) gives no bound, and (d) claims a confirmation that no finite search can give. For comparison, Oliveira e Silva, Herzog and Pardi (2014) verified Goldbach's conjecture for all even numbers up to $4 \times 10^{18}$ , documenting their methods and checks.
4.
(a). Six numbers to 100 digits could only produce spurious relations with coefficients around $10^{100/6} \approx 10^{17}$ ; a relation with coefficients below $100$ that persists at 200 digits is very strong evidence. It remains a conjecture until proved — the BBP formula followed exactly this path.
5.
$p \equiv 1$ : $5, 13, 17, 29, 37, 41$ ( $O = 6$ ). $p \equiv 3$ : $3, 7, 11, 19, 23, 31, 43, 47$ ( $T = 8$ ). So $T - O = 2$ . The "3" team stays ahead (or level) until $x = 26861$ — Chebyshev's bias — but Littlewood proved that the lead changes infinitely often.
6.
(a). Term-by-term integration of $\sum_k x^{8k + j - 1}$ is justified because the series converges uniformly on $[0, 1/\sqrt2]$ (a geometric series with ratio at most $1/16$ ). This is exactly the step not formalised in the lesson's Lean module, which proves the integral $\int_0^1 \frac{16y - 16}{y^4 - 2y^3 + 4y - 4}\,dy = \pi$ .
7.
(a). The conjecture is ∀ n, (fermat n).Prime; to refute it is to prove its negation, equivalently ∃ n, ¬ (fermat n).Prime, witnessed by n = 5. Option (b) confuses "not all" with "none".
8.
(a). Goldbach's conjecture is $\Pi_1$ : "for all $n$ , a decidable property holds", so a false instance can be found and verified. The twin-prime and Fermat-prime conjectures are $\Pi_2$ ("for every $N$ there exists a larger example"), and the Collatz conjecture is also $\Pi_2$ ("for every $n$ there exists $k$ with $T^k(n) = 1$ "); a divergent trajectory would refute it without any finite certificate.

def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True


def first_counterexample(pred, start, bound):
    for n in range(start, bound + 1):
        if not pred(n):
            return n
    return None


mersenne_claim = lambda p: (not is_prime(p)) or is_prime(2 ** p - 1)

The claim " $p$ prime $\Rightarrow 2^p - 1$ prime" holds for $p = 2, 3, 5, 7$ and fails at $p = 11$ : $2^{11} - 1 = 2047 = 23 \cdot 89$ . A None result should always be reported with its range: "no counterexample for $\text{start} \le n \le \text{bound}$ ".