Spiked Math Games  // Math Fail Blog  // Gauss Facts  // Spiked Math Comics

# 294

Polya's Conjecture - August 28, 2010
Rating: 4.7/5 (144 votes cast)
• Currently 4.7/5
• 1
• 2
• 3
• 4
• 5

wow, that'd be a bitch to prove. is there even a formula? how do you make a formula out of primes?

In this case, a proof is by counterexample. Take n = 906150257, then you can show that the conjecture is false as it fails for a specific n.

To prove a theorem involving prime numbers in general, we usually need to abstract away to group theory, or in simple cases just integer divisibility.

Sounds somewhat similar to Merten's Conjecture, but Merten's only dealt with square-free numbers. They are similar both in the respect that they have to do with the parity of the factors and also that they are false, but don't have counterexamples until the numbers get very large.

i wonder where the cut off would be if you could somehow generalize the problem to include decimals

1. prove that E(n)=O(n) when n = 906,150,256
2. prove that 906,150,257 is even type

something tells me you will need to break down your proof into further steps...

what the factorial!!! :D

Never never never use "big O" as a function name. ... especially when discussing growth rates ...

And this result, of course, leads to any number of follow-up questions, similar to those about primes congruent to 1 or 3 modulo 4. (E.g., do O and E swap dominance infinitely often?)

I just "stumbled upon" your site. It is excellent!!!

why was "stumbled upon" in quotes?

there is a wonderful internet app thing, called "stumble upon," which allows you to randomly jump from one interesting website to the next.

It's how I found this wonderful comic... I highly recommend it.

I assume he was directed to the site from www.stumbleupon.com.

Oh, cool, didn't know that, thanks

It's false - E(N)>O(N) for N=1

N was defined to be > 1.

If we disprove it, do we have to salvage it?

I've been taught at school that you cannot prove something that's wrong. So either you find a counter-example which cancels the proposition, either you work on a proof.

As said by Mike, checking lots of cases is not a proof, but if any counter-example exists, we might get a chance to stumble upon it.
That's why people are working on a theoretical proof, and at the same time computing lots of values about the Riemann's Zeta function possibility of describing prime number's distribution (or something like that).

Although, the thin limit between theoretical proof and computation has been reached with the 4-colourable graph proof, narrowing the set of planar graphs to a subset of a few thousand graphs, and trying them all by computer. The code used was given as part of the proof.

The 4-color proof is, I should think, a proof because it checked all possible cases. Checking lots of cases isn't a proof, but checking all of them is. So, in this case, you could write a program that checked all possible cases, and it would be a proof.

Well, it first reduced all cases to a finite list by traditional techniques. Only then the automated check of the list could work. Still, I'd consider the source code of the program as well as the executable it produced and the CPU back then to be part of the proof since all of those could have bugs that may have rendered the proof invalid ;-)

Well yes, obviously. You can't actually check all maps, as there are infinitely many of them, and computers can only truly work with finite quantities...

But the point was to reduce the infinite class of possible maps to a very large, but finite, class of maps that, if they could be four-colored, all maps could. Then they created a program to check all the required maps.

Why is 1 of the even type?

We know taht 2 is of odd type, because 2=2. But 2 = 2·1 = 2·1·1 = … Clearly, it's not a good idea to let 1's get into it. So we just decide that 1=, which has 0 prime factor (or 1=1, with 1 not being a prime).

Here's an example why it's a good idea to say that 1 has a factorization with 0 prime factor:
Let define Omega(N) the number of prime factors in the factorization of N (so that Omega(N) is even N is of even type). With that, a=b·c => Omega(a)=Omega(b)+Omega(c). But this is correct for b or c = 1 only if Omega(1)=0, that is the factorization of 1 has 0 prime.

Quicker answer: so that the rule [a=b·c => (b is of the same type as c a is of even type)] is correct also when b or c is 1.

See http://en.wikipedia.org/wiki/M%C3%B6bius_function for details.

Maybe 1 is of the even type because it has 0 prime factors in its prime factorization? 1 is not a prime.

(Note: You must have javascript enabled to leave comments, otherwise you will get a comment submission error.)
If you make a mistake or the comment doesn't show up properly, email me and I'll gladly fix it :-).

Welcome to Spiked Math!

Hello my fellow math geeks. My name is Mike and I am the creator of Spiked Math Comics, a math comic dedicated to humor, educate and entertain the geek in you. Beware though, there might be some math involved :D

New to Spiked Math?
View the top comics.

New Feature: Browse the archives in quick view! Choose from a black, white or grey background.

Other Math Comics