Problem solving and conjecture: experiments, examples and heuristics

Research begins long before the first proof. It begins with examples, computations, guesses, failed attempts and revised guesses, a phase that published papers almost entirely hide. A paper presents a theorem and its proof in logical order; it rarely mentions the three wrong conjectures that came first or the table of numbers on which the right one was spotted. This lesson is about that hidden phase: how to generate examples, how to turn patterns into conjectures, how to test them, and how to avoid being fooled. It draws on George Pólya's classic account of problem solving and on cautionary tales from the history of mathematics.

Pólya's four phases

In How to Solve It, published in 1945, the Hungarian-American mathematician George Pólya described problem solving in four phases: understanding the problem, devising a plan, carrying out the plan and looking back. The book is aimed at students solving set problems, but its framework applies remarkably well to research, provided one remembers that in research the phases repeat many times, and that looking back often reveals that the problem should be changed.

Understanding the problem means being able to state it precisely, identify the unknown, the data and the conditions, and draw a figure or compute an example. In research this phase is larger than it sounds. Making a vague question precise is often half the work: Amara's question became tractable only when she defined a representation exactly, decided to count the trivial one, and wrote the equation \(2n = k(2a + k - 1)\).

Devising a plan means finding a connection between the data and the unknown. Pólya's questions are worth memorizing. Do you know a related problem? Could you solve a special case? A more general problem? An analogous problem? Could you work backwards from the desired conclusion? Could you introduce auxiliary elements, a new variable, a figure, a function, a generating series, that make the structure visible?

Carrying out the plan means doing the work and checking each step. Looking back means checking the result, seeing whether it can be derived differently, and asking whether the method or result can be used for other problems. In research, looking back is where the next question comes from.

Heuristics that work

Beyond Pólya's questions, a few heuristics recur constantly in research.

Specialize. If the general problem is hard, solve it for small parameters, special shapes or extreme values. Specialization produces data, and data produce conjectures. Amara's first step, computing representations for \(n \le 40\), is pure specialization.

Generalize. Paradoxically, a more general problem is sometimes easier, because the general setting strips away irrelevant features and suggests natural tools. Proving a statement for all \(n\) by induction can require proving a stronger statement, since the induction hypothesis is then stronger too.

Change the representation. A problem about sums becomes a problem about factorizations; a counting problem becomes a problem about bijections or generating functions; a geometric problem becomes algebraic. The staircase pictures of lesson 1 are a change of representation: they suggest viewing a representation as a shape, which leads to Sylvester's partition-theoretic proofs.

Look for invariants and extremes. Quantities that do not change under a process, such as parity, often prove impossibility; extreme cases, such as the smallest counterexample, often yield contradictions.

Work backwards. Assume the conclusion and see what it requires. For existence problems, guess the form of the object and solve for its parameters, as when we solve \(2n = k(2a + k - 1)\) for \(a\).

From pattern to conjecture

A conjecture is a precise statement that you believe and cannot yet prove. A good conjecture is precise enough to be falsified by a single counterexample, general enough to be interesting and supported by evidence. Turning a pattern into a conjecture involves several deliberate steps: tabulate systematically rather than looking at scattered examples; look at the data in several ways, sorted, factored, differenced, plotted; formulate a statement covering all cases; and decide in advance what evidence would refute it.

Amara's data showed that \(r(n)\) is unchanged when \(n\) doubles. That is a statement about the data, not yet a conjecture about all integers. She made it precise: if \(n = 2^e m\) with \(m\) odd, then \(r(n) = r(m)\). Then for odd \(m\) she factored the values: \(r(3) = r(5) = r(7) = 2\), \(r(9) = 3\), \(r(15) = 4\), \(r(25) = 3\), \(r(45) = 6\), \(r(105) = 8\). The values \(2, 3, 4, 6, 8\) match \(\tau(m)\), the number of divisors of \(m\), suggesting the full conjecture \(r(n) = \tau(m)\), equivalently the number of odd divisors of \(n\).

When patterns lie

The great danger of the experimental phase is believing a pattern too soon. Richard Guy called this the strong law of small numbers: there are not enough small numbers to meet the many demands made of them, so striking coincidences among small cases are common. The classic example is the circle problem shown below. Place \(n\) points on a circle in general position, so that no three chords meet at a single interior point, and draw all chords between them. Count the regions into which the disc is divided.

The counts for \(n = 1, \ldots, 5\) are \(1, 2, 4, 8, 16\). Anyone would conjecture \(2^{n-1}\). But six points give 31 regions, not 32, and the true formula, which we prove in lesson 6, is

which gives \(1, 2, 4, 8, 16, 31, 57, 99, \ldots\) and grows only like \(n^4\). The program below counts regions experimentally for random points on a circle, using the fact that each interior crossing of two chords and each chord adds one region, and compares the results with both the false and the true formulas.

import random
from math import comb, cos, sin, pi

def crossings(pts):
    """number of interior intersection points of chords among points on a circle"""
    def ccw(a, b, c):
        return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
    n, chords, total = len(pts), [], 0
    for i in range(n):
        for j in range(i + 1, n):
            chords.append((pts[i], pts[j], {i, j}))
    for x in range(len(chords)):
        for y in range(x + 1, len(chords)):
            p, q, s1 = chords[x]
            r, s, s2 = chords[y]
            if s1 & s2:
                continue           # chords sharing an endpoint meet on the circle
            if ccw(p, q, r) * ccw(p, q, s) < 0 and ccw(r, s, p) * ccw(r, s, q) < 0:
                total += 1
    return total

random.seed(5)
print(" n  regions  2^(n-1)  C(n,4)+C(n,2)+1")
for n in range(1, 11):
    angles = sorted(random.uniform(0, 2 * pi) for _ in range(n))
    pts = [(cos(t), sin(t)) for t in angles]
    regions = 1 + comb(n, 2) + crossings(pts)   # each chord and each crossing adds a region
    print(f"{n:2d}  {regions:7d}  {2 ** (n - 1):7d}  {comb(n, 4) + comb(n, 2) + 1:9d}")

 n  regions  2^(n-1)  C(n,4)+C(n,2)+1
 1        1        1          1
 2        2        2          2
 3        4        4          4
 4        8        8          8
 5       16       16         16
 6       31       32         31
 7       57       64         57
 8       99      128         99
 9      163      256        163
10      256      512        256

The experimental counts agree with the binomial formula for every \(n\), and the powers of two fail from \(n = 6\) onward. Observe that the program itself rests on a claim, that each chord and each crossing adds exactly one region, which needs proof; that proof is the content of lesson 6. Random points are almost surely in general position, so the experiment tests the general-position case.

Other cautionary tales are more dramatic. Pólya himself conjectured in 1919 that for every \(n \ge 2\), at least half of the integers up to \(n\) have an odd number of prime factors counted with multiplicity. In terms of the Liouville function \(\lambda(k) = (-1)^{\Omega(k)}\), where \(\Omega(k)\) counts prime factors with multiplicity, the conjecture says that \(L(n) = \lambda(1) + \cdots + \lambda(n) \le 0\) for \(n \ge 2\). It holds for every \(n\) anyone checked by hand, and C. B. Haselgrove proved in 1958 that it is false; the smallest counterexample, found by Minoru Tanaka in 1980, is 906,150,257. The Mertens conjecture, that \(|M(n)| < \sqrt{n}\) for the summatory Möbius function, was disproved by Andrew Odlyzko and Herman te Riele in 1985, though no explicit counterexample is known. No amount of computation over small ranges could have settled either question.

def omega_table(N):
    """Omega(k) = number of prime factors of k with multiplicity, for k <= N, by a sieve"""
    Om = [0] * (N + 1)
    rest = list(range(N + 1))
    for p in range(2, N + 1):
        if rest[p] == p and Om[p] == 0:          # p is prime
            for m in range(p, N + 1, p):
                while rest[m] % p == 0:
                    rest[m] //= p
                    Om[m] += 1
    return Om

N = 200000
Om = omega_table(N)
L, worst, where = 0, -10 ** 9, None
for k in range(1, N + 1):
    L += -1 if Om[k] % 2 else 1
    if k >= 2 and L > worst:
        worst, where = L, k
print(f"largest L(n) for 2 <= n <= {N}: {worst} at n = {where}")
print("Polya's conjecture predicts L(n) <= 0; it survives this range")
print("first counterexample (Tanaka 1980): n = 906150257")

largest L(n) for 2 <= n <= 200000: 0 at n = 2
Polya's conjecture predicts L(n) <= 0; it survives this range
first counterexample (Tanaka 1980): n = 906150257

The largest value of \(L(n)\) for \(2 \le n \le 200{,}000\) is 0, attained first at \(n = 2\) and then at \(n = 4, 6, 10, 16, 26\) and a few other small values, after which the sum stays comfortably negative. Evidence like this is exactly what made the conjecture plausible for nearly forty years.

The Collatz problem

Some patterns are believed but resist all proof. Start with a positive integer \(n\); if it is even, halve it; if it is odd, replace it by \(3n + 1\); repeat. Lothar Collatz considered this process in the 1930s, and the conjecture that every starting value eventually reaches 1 has been verified by computer for all starting values below \(2^{68}\), about \(3 \times 10^{20}\), by David Barina's computations around 2020. In 2019 Terence Tao proved that almost all orbits attain almost bounded values, in a precise logarithmic-density sense, which is among the strongest results known. The conjecture itself remains open.

The Collatz problem is a good example of a question that can anchor an excellent experimental project even though nobody expects a student to solve it. A project might study the distribution of stopping times, the records, the behavior of the map modulo powers of two, or generalizations such as \(n \mapsto 5n + 1\), for which some orbits are believed to diverge. Each of these offers precise sub-questions that can actually be answered, and the honest framing is part of the scholarship.

Testing a conjecture hard

Once you have a conjecture, try to break it. Test it far beyond the range that suggested it. Test extreme cases: primes, prime powers, highly composite numbers, numbers of special forms. Test random cases, since your hand-picked examples may share a hidden feature. Test the boundaries of the hypotheses: if the conjecture is stated for odd \(n\), does it fail for even \(n\), and how? A conjecture that survives determined attack deserves an attempt at proof; one that fails has taught you something, often by its counterexample, which may point to the right statement.

N = 10 ** 6
reps = [0] * (N + 1)
k = 1
while k * (k + 1) // 2 <= N:
    s = k * (k + 1) // 2           # start a = 1
    while s <= N:
        reps[s] += 1
        s += k                     # increasing a by 1 adds k to the sum
    k += 1

odd_div = [0] * (N + 1)
for d in range(1, N + 1, 2):
    for m in range(d, N + 1, d):
        odd_div[m] += 1

bad = [n for n in range(1, N + 1) if reps[n] != odd_div[n]]
print("checked n up to", N, "- counterexamples:", bad[:5] if bad else "none")
print("most representations:", max(range(1, N + 1), key=lambda n: reps[n]), "with", max(reps), "representations")

checked n up to 1000000 - counterexamples: none
most representations: 675675 with 96 representations

Keeping an experimental notebook

Record your experiments: the question, the code or calculation, the output, and what you concluded. Date the entries. It is astonishing how quickly one forgets which variant of a computation produced which table, and an undated printout is nearly useless in March. Keep code under version control or at least in dated files, so that every number in the thesis can be regenerated. Most importantly, record failed conjectures and the counterexamples that killed them. They often belong in the thesis as remarks showing why a hypothesis is needed.