About Polya's conjecture.

Primes, divisors, arithmetic, number properties, ...
Post Reply
aziiri
Posts: 1
Joined: Mon Jan 13, 2014 12:10 pm

About Polya's conjecture.

Post by aziiri » Sun Nov 02, 2014 9:57 am

If you are not familiar with Polya's conjecture you may want to read this.

This conjecture was proven false for n=906,316,571 fifty years ago. This means that they did not have fancy computers.

Assume this is ProjectEuler problem (finding the counter-example), what is the solution that you propose ? I prefer that it does not use much memory and running time.

User avatar
Marcus_Andrews
Administrator
Posts: 1447
Joined: Wed Nov 09, 2011 5:23 pm

Re: About Polya's conjecture.

Post by Marcus_Andrews » Sun Nov 02, 2014 5:43 pm

Here is a way to find the first counterexample $906150257$ in C++ (about 40 seconds on my machine):

The Liouville value $\lambda(n)$ is defined as $\lambda(n) = (-1)^{\Omega(n)}$ where $\Omega(n)$ is the number of prime factors of $n$ counted with multiplicity. If the summatory Liouville function $L = \sum_{i=1}^{k} \lambda(i)$ is greater than $0$ for some $k$, then we have found a counterexample to the Pólya conjecture.

Moving onto the main program (using $n = 10^9$):

We can use a modified Sieve of Eratosthenes algorithm to calculate a prime divisor (which we'll denote $D(i)$) for each $i$ over $2 \leq i \leq n$.

After initializing the summatory value $L = 1$, we iterate from $i=2$ upwards and calculate $\lambda(i) = -\lambda(i / D(i))$. As we calculate each Liouville value, we add it to $L$. Once $L>0$, we have found our counterexample, and we stop.

Overall, the sieve requires $O(n)$ space and $O(n \log \log n)$ time, and then finding the counterexample can be done in $O(n)$ time.

Code: Select all

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

long long polya(long long n){
	long long L = 1, sqrtN;
	vector<long long> D(n+1); //prime divisors
	vector<int> lambda(n+1); //Liouville values
	lambda[1] = 1;
	for (long long i = 0; i<=n; ++i) D[i] = i; //D = [0,1,2,...,n]
    
    sqrtN = sqrt(n);
    for (long long i = 2; i <= sqrtN; ++i) //Sieve of Eratosthenes
    	if (D[i] == i) //i is prime
    		for (long long j = i*i; j<=n; j+=i)
    			D[j] = i; //i is a prime divisor of j

    for (long long i = 2; i<= n; ++i){ //look for counterexample
    	lambda[i] = -lambda[i/D[i]];
    	L += lambda[i];
    	if (L>0) return i; //counterexample found
    }
    return 0; //no counterexample found
}

int main(){
	long long n = 1000000000LL;
	cout << polya(n) << endl;
	return 0;
}
There are ways to improve this, but I leave that as an exercise to the reader. :lol:
Image

stimmer
Posts: 10
Joined: Mon Jul 25, 2011 4:56 pm

Re: About Polya's conjecture.

Post by stimmer » Sun Nov 02, 2014 7:25 pm

Isn't the summatory Liouville function just the sum of the Mertens function at [n/(d^2)] for 1<= (d^2)<=n ?

There's a way of calculating the Mertens function in O(n^(2/3+e)) (by Lehman, the same Lehman named on the page you linked to.) And on PE there are dozens of questions on the topic of 'sum the multiplicative function' where there's a O(n^(3/4)) or better solution - the method has attained an almost legendary status here and I don't want to give away any clues :D

Post Reply