It is known that [Polya's conjecture](http://en.wikipedia.org/wiki/Polya_conjecture) is false and the smallest counter-example is about $10^9$.


Assuming that we are searching for a counter-example not knowing that it exists. What useful information can I use to speed up my search ? 


**Motivation :** If we try brute force on an (i7), 32 bits system with 8 GB of RAM, we are looking to a hour of computation but this was done fifty years ago on a very slow machine, so they used some fancy mathematical techniques which I do not know of.


**How my brute force search works :**


First I have $L$ a large list of primes (up to $10^{10}$ for example).


to calculate $\Omega(n)$ the number of divisors of $n$ I look of a prime $p$ that divides $n$ and then calculate $\Omega(n)=\Omega(n/p)+1$.


The summatory function is done by a simple while loop.



Counterexample to Pólya's conjecture
[Lehman's paper](http://dx.doi.org/10.2307%2F2003890) is very clear about what he is doing. One can express $L(x)=\sum\_{n\leq x}\lambda(n)$ as a rather short sum whose terms are expressible easily from the values of $\mu(m)$, $\lambda(k)$, $L(y)$ for $m,k,y$ much smaller than $x$. 


The starting identity is (4) in the paper, namely
$$ \sum\_{m\leq x}L(x/m) = \lfloor \sqrt x \rfloor. $$
This can be proved as follows:
$$ \sum\_{m\leq x}L(x/m) = \sum\_{m\leq x}\sum\_{n\leq x/m}\lambda(n) = \sum\_{mn\leq x}\lambda(n)=\sum\_{k\leq x}\sum\_{n\mid k}\lambda(n).$$
The inner sum is a multiplicative function in $k$, and on a prime power $p^r$ it is zero or one according to whether $r$ is even or odd. Hence the inner sum is zero or one according to whether $k$ is a square or not, so
$$ \sum\_{m\leq x}L(x/m) = \sum\_{\substack{k\leq x\\k=\square}}1=\lfloor \sqrt x \rfloor.$$


This formula can be refined/generalized to yield similar (more complicated but for computational purposes more effective) identities, and the paper makes use of them. The general method is called "Dirichlet's hyperbola method'', and you can learn about it in number theory textbooks.


In short, Lehman's paper utilizes basic multiplicative number theory in a clever way. With a little effort you can understand all the details.


