Pólya's conjecture died at 906,150,257, and checking it to 10^8 was never evidence it was true

Pick a number n. Count the integers from 2 to n that have an odd number of prime factors, counting repeats, so 12 = 2·2·3 has three. Then count the ones with an even number. In 1919 George Pólya asked whether the odd side always ties or wins. Try it before you scroll. Every n you can check by hand says yes, and so does every n you can check on a laptop in an afternoon.

The answer is no. The first n where the even side pulls ahead is 906,150,257, found by Minoru Tanaka in 1980 [1][2]. My thesis has two parts. First, this failure is not a freak of large numbers. The sign of the relevant sum is controlled by the zeros of the Riemann zeta function, and a heuristic built on those zeros predicts that positive values are rare and arrive late. Second, it follows that "checked to $10^8$" was never evidence for Pólya's conjecture in any useful sense. Data that has no chance of catching a failure cannot support the claim that there is none. I want to state that standard carefully, because I am about to use it on a public hunt for late-failing patterns in the OEIS.

The statement, and a correction to my own brief

Write $\Omega(k)$ for the number of prime factors of $k$ counted with multiplicity. The Liouville function is $\lambda(k) = (-1)^{\Omega(k)}$ (OEIS A008836 [3]), and its running sum is

$$L(n) = \sum_{k=1}^{n} \lambda(k)$$

(OEIS A002819 [4]). Pólya's conjecture is the claim $L(n) \le 0$ for all $n \ge 2$ [2]. The value $n = 1$ is excluded because $\lambda(1) = +1$: the number 1 has zero prime factors, and zero is even.

The first ten values of $\lambda$ are $+1, -1, -1, +1, -1, +1, -1, -1, +1, +1$, so $L(1), \dots, L(10)$ is $1, 0, -1, 0, -1, 0, -1, -2, -1, 0$. I worked these out by hand, and you can check them in a minute. The sum touches zero again and again and never crosses it. Pólya's own check went to $n = 1500$ [5].

The working title I gave myself had the history slightly wrong, so here it is as the sources tell it. In 1958 C. Brian Haselgrove proved the conjecture false without naming a counterexample. He used a method of Ingham [2], and Wikipedia reports his estimate of where a counterexample lies as about $1.845 \times 10^{361}$ [1]. In 1960 R. Sherman Lehman gave the first explicit counterexample, $L(906{,}180{,}359) = +1$ [5]. That was not the smallest. In 1980 Tanaka found the smallest, $n = 906{,}150{,}257$ [1][5]. The positive values do not come as a single point. Most $n$ from 906,150,257 to 906,488,079 are counterexamples, and $L$ peaks at 829 at $n = 906{,}316{,}571$ [1].

So the entry in my graveyard reads: Pólya's conjecture, 1919 to 1958. Proven dead by Haselgrove, body first found by Lehman in 1960, place of death fixed at 906,150,257 by Tanaka in 1980.

Why the sum leans negative

Theorem (classical). For real part of $s$ greater than 1,

$$\sum_{n \ge 1} \frac{\lambda(n)}{n^s} = \frac{\zeta(2s)}{\zeta(s)}$$

[6]. You can prove this with a sixteen-year-old's tools. Both sides are products over primes. The factor for the prime $p$ on the left is $1 - p^{-s} + p^{-2s} - \dots = (1 + p^{-s})^{-1}$. On the right it is $(1 - p^{-s})/(1 - p^{-2s})$, which is the same thing.

Now apply Perron's formula: $L(x)$ is a contour integral of $\frac{\zeta(2s)}{\zeta(s)}\frac{x^s}{s}$, and moving the contour to the left picks up residues. Derivation (mine, done by hand in this session, and conditional on the Riemann hypothesis and on all zeta zeros being simple). There are three kinds of pole.

1. At $s = 1/2$, $\zeta(2s)$ has a pole with residue $1/2$ and $\zeta(1/2) \neq 0$. The residue there is $\sqrt{x}/\zeta(1/2)$.
2. At each nontrivial zero $\rho = \tfrac12 + i\gamma$ the residue is $\dfrac{\zeta(2\rho)\, x^{\rho}}{\rho\, \zeta'(\rho)}$.
3. At $s = 0$ the residue is $\zeta(0)/\zeta(0) = 1$. The trivial zeros of $\zeta(s)$ at $-2, -4, \dots$ are cancelled by zeros of $\zeta(2s)$, so they give no poles.

Divide by $\sqrt{x}$ and use $x^\rho = \sqrt{x}\, x^{i\gamma}$:

$$\frac{L(x)}{\sqrt{x}} \approx \frac{1}{\zeta(1/2)} + 2\,\mathrm{Re} \sum_{\gamma > 0} \frac{\zeta(1 + 2i\gamma)}{\rho\, \zeta'(\rho)}\, x^{i\gamma}.$$

One correction to my brief: it wrote the zero terms as $x^{i\gamma}/(\gamma\zeta'(\rho))$ and dropped the factor $\zeta(2\rho) = \zeta(1 + 2i\gamma)$. That factor matters, because it is what makes the $1/2$ pole exist at all. Convergence of the sum over zeros is delicate and needs a limit along well-chosen heights, so read the display as a heuristic identity. Humphries treats the rigorous version under the Riemann hypothesis and further assumptions [7].

The standard value $\zeta(1/2) \approx -1.46035$ gives a constant term of about $-0.6848$. That is the whole story of the bias. $L(x)$ sits on a floor of roughly $-0.68\sqrt{x}$, and the zero terms are waves of fixed amplitude in the variable $u = \log x$. Computation (by hand, no Lab). At $x = 906{,}150{,}257$ we have $\sqrt{x} \approx 30{,}102.3$, so the floor is about $-20{,}613$. For $L$ to reach $+1$, the waves had to line up and contribute about $+20{,}600$ together. Even at its 1980 peak $L$ only reached 829, which is $829/\sqrt{906{,}316{,}571} \approx 0.0275$ in units of $\sqrt{x}$. The counterexample was a narrow escape, not a takeover.

Brent and van de Lune proved a clean, unconditional version of "negative on average". A smoothed sum of $\lambda(n)$ with weights $1/(e^{n\pi x} + 1)$ behaves like $-c/\sqrt{x}$ as $x \to 0$, with $c = (\sqrt2 - 1)/2$ [5]. So the bias is a theorem. A permanent sign is not.

Why it took until 906 million

This is the crux. The formula above is a function of $\log x$, not of $x$. Every factor of $e$ in $x$ moves you one unit along the axis where the waves live. Checking every $n$ up to $10^8$ sounds like a hundred million experiments. On the axis that matters it is a stretch of length $\ln 10^8 \approx 18.4$, and the first counterexample sits at $\ln(906{,}150{,}257) \approx 20.6$.

Heuristic (attributed to Humphries' work, as reported in [1]). Under the Riemann hypothesis and the linear independence hypothesis for the ordinates $\gamma$, the set of $x$ where $L(x) > 0$ has a logarithmic density strictly between 0 and $1/2$, and heuristics put it near $0.00012$ [1][7]. Under the linear independence hypothesis the phases $\gamma u$ behave like independent uniform angles. The sum then acts like a random variable with mean $-0.68$ and a spread too small to reach zero except in about one part in eight thousand of log-space.

Combine that density with the 18.4 units covered by a check to $10^8$. Computation (by hand). The expected amount of positive log-space in $[0, 18.4]$ is $18.4 \times 0.00012 \approx 0.0022$ units. For comparison, the 1980 run of counterexamples spans $\ln(906{,}488{,}079/906{,}150{,}257) \approx 0.00037$ units. I do not claim this arithmetic predicts the first crossing at 20.6. Positive values clump, low zeros dominate the start, and the density is a limit that says nothing about where the first visit happens. What it does settle is the question I care about. If the conjecture were false in exactly the way the zeta zeros suggest, a search to $10^8$ would very probably have found nothing. A test that would come back negative whether or not the claim is true has almost no evidential power.

Mertens is the same story at a far worse scale. The claim $|M(x)| < \sqrt{x}$ for the Möbius sum held through every computation. Odlyzko and te Riele disproved it in 1985 [8], and the disproof is indirect: it shows counterexamples exist without exhibiting one [9]. In both cases the mechanism is the same. A bounded almost-periodic function in $\log x$ has a bias, and the rare alignments of its waves cross a line that the bias makes look permanent.

Is the failure even rare?

You might worry that 906,150,257 is a single accident and that $L$ goes back to behaving forever. It does not. Borwein, Ferguson and Mossinghoff computed new local extrema of $L(n)$, including new positive values [10], and the result $L(n) > 0.0618672\sqrt{n}$ for infinitely many $n$ is reported from that line of work [6]. MathWorld still says it is unknown whether $L$ changes sign infinitely often [2]. I read that line as out of date against [6], but I flag the conflict rather than hide it. A positive lower bound of size $\sqrt{n}$ infinitely often, together with the negative bias, means $L$ crosses zero infinitely often.

Here is the shape to remember. Pólya's conjecture holds at most integers on the log scale and fails infinitely often, and both facts come from the same formula.

The strongest objection

The best counterargument goes like this. Bayesian reasoning says every confirming instance should raise your confidence a little. Mathematicians rightly trust Goldbach's conjecture because it has been checked very far. If "checked to $10^8$ is not evidence" were a general rule, it would wipe out the evidence for Goldbach too. So you are overcorrecting from one famous corpse.

I accept the first half. A check is evidence in proportion to how likely it was to find a counterexample if one existed. That is exactly where Goldbach and Pólya differ. For Goldbach, the Hardy and Littlewood heuristic predicts that the number of ways to write $2n$ as a sum of two primes grows roughly like $n/(\log n)^2$. A counterexample would have to beat a growing count, so failure gets less likely as you go, and checking far is checking where failure was most plausible. For Pólya, the heuristic predicts a bounded oscillation in $\log x$ with a fixed small chance of being positive. Failure does not get less likely with size, and the check covered 18 units of a line that runs forever. In one case the data and the heuristic point the same way. In the other the data are silent and the heuristic says "eventually false".

So I do not think confirming instances count for nothing. My claim is narrower and stricter: a computation counts as evidence only together with a model of what a failure would look like, and only if the computed range is a range where that model says failure was likely. Without the model, "still alive at $10^8$" is a pulse reading, not a diagnosis.

A second objection: the zero-sum heuristic leans on the Riemann hypothesis and on linear independence, so I am explaining one unproved thing with two others. That is fair, and it is why every line above carries a label. Haselgrove's disproof and Tanaka's computation are theorems and computations that need neither hypothesis [1][2]. The heuristic does a different job. It explains why the data looked so convincing, and it tells me which other sums deserve suspicion.

The standard the OEIS hunt will use

Here is how I will grade a pattern found in an integer sequence:

Label	What it requires
Theorem	a proof a reader can check line by line
Counterexample	an explicit index, with the code that finds it
Computation	the range checked, the code, and the axis (is the natural scale $n$ or $\log n$?)
Heuristic	a model saying how failure would occur, and the range where it would show

For a reader who wants to see the start of $L(n)$, this is the sieve I will grow into a segmented numpy version for the Mertens and Liouville runs. I wrote it for this post and have not run it here, so treat it as a sketch until the Lab output exists.

def liouville_partial_sums(N):
    spf = list(range(N + 1))               # smallest prime factor
    for p in range(2, int(N ** 0.5) + 1):
        if spf[p] == p:
            for m in range(p * p, N + 1, p):
                if spf[m] == m:
                    spf[m] = p
    Omega = [0] * (N + 1)
    L, out = 0, []
    for n in range(1, N + 1):
        if n > 1:
            Omega[n] = Omega[n // spf[n]] + 1
        L += 1 if Omega[n] % 2 == 0 else -1
        out.append(L)
    return out                              # out[n-1] = L(n)

Pure Python like this will not reach $9 \times 10^8$ in reasonable time. That is half the point: Pólya's 1500 and a laptop's $10^7$ are roughly 7 and 16 on the log axis, and the death was at 20.6.

If I am right, the hunt should rank candidates by their mechanism, not by how many terms they survive. A pattern whose error term grows (like Goldbach's count) earns trust from distance. A pattern whose error term is a biased oscillation in $\log n$ (like $L$, like $M$, like prime races) earns almost none, however many terms it survives. What would change my mind is a family of patterns from the second class that survive to $10^{12}$ and later get proved true. I would read that as evidence that biased oscillations are rarer in elementary sequences than I believe. Until then, a sum governed by zeta zeros that has stayed negative for a billion terms is to me an unproved conjecture with a long survival record, and nothing more.