Wikipedia:Reference desk/Archives/Mathematics/2013 September 30

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 30

"Disproof" (not really) of Goldbach's conjecture

(Background. My previous try here on Wikipedia Reference Desk a few weeks ago, using a statistical/probabilistic/heuristic proof to prove Goldbach's conjecture, was shot down by it being pointed out that the "proof" did not preclude the - admittedly small - possibility of there being some 2N for which there is not even one pair of primes such that P1+P2=2N.)

So, I decided to see just what is the possibility of such a 2N for which not even one pair of primes P1+P2=2N.

SPOILER ALERT: The results are not at all what you might expect.

Obviously, 2N-3 must not be prime. The probability of that is 1-1/ln(2N-3).

Also, 2N-5 must not be prime. The probability of that is 1-1/ln(2N-5).

And so on, down to N+a not being prime, N-a being the largest prime .LE. N and "a" being an integer .GE. 0. The probability of that is 1-1/ln(N+a).

We note that all of these the probabilities are smaller than 1-1/ln(2N) and greater than 1-1/ln(N).

For 3, 5, ... , 19, 23, 29, ... , N-a, there are a total of ln(N) case, ALL of which must be true for 2N to have no pair of primes such that P1+P2=2N.

That is, the probability of 2N for which not even one pair of primes P1+P2=2N, is .LE. (1-1/ln(2N))^ln(N) and .GE. (1-1/ln(N))^ln(N).

These two results - "(1-1/ln(2N))^ln(N)" and "(1-1/ln(N))^ln(N)" - are very much like the expression for e, which is (1+1/n)^n as n grows without bound.

We can substitute -m for n in the expression for e, to get (1-1/m)^(-m), or 1/((1-1/m)^m).

The minus sign inverts the results, so in the limit we have (approximately) 1/e as the probability of 2N for which no pair of primes P1+P2=2N.

A 37% (thirty-seven percent) probability!!?? That's not so small.

And what's worse, it appears that this whole process can repeat itself for 4N, 8N, 16N, etc.

(Curiouser and curiouser, said Alice.)

Yet Goldbach's comet and numeric calculations, so far as they go, completely contradict this probability of 1/e.

Some possible suggestions (whether correct or not) to solve this paradox:

1. There is an error in my logic/mathematics. (What is the error?)

2. The primes have a distribution law that has not been taken into account. (What is this law?)

3. When actual numbers are plugged in, theories about primes suffer quantum collapse. (OK, just checking if you read this far.)

4. Something else. (Please state your suggestion.) Bh12 (talk) 10:58, 30 September 2013 (UTC)

I don't understand why you say "there are a total of ln(N) cases". Since there are approximately N/ln(N) primes less than N, I would have expected the number of cases (and hence your exponents too) to be N/ln(N), not ln(N). Gandalf61 (talk) 11:37, 30 September 2013 (UTC)

I said there are a total of ln(N) cases precisely because there are a total of ln(N) primes (3,5,...,19,23,29,...,N-a) that must have a non-prime as their complement to 2N, if 2N cannot be a sum of two primes.Bh12 (talk) 12:12, 30 September 2013 (UTC)

So take N = 100 (so 2N = 200). There are 24 primes between 3 and 100. So I would have thought you had 24 cases. But ln(N) = 4.6, so you say there should only be 4 or 5 cases. Which 4 or 5 primes from the 25 available primes do you pick ? And how do you pick them ? Gandalf61 (talk) 12:19, 30 September 2013 (UTC)

Yes, you are correct that the number of primes 3,5,...,N-a is N/ln(N), and not ln(N) as I had previously said. This changes the expression for the probability of 2N not being the sum of rwo primes to (1-1/(ln))^(N/ln(N)), or (1/e)^(N/ln(N)), which not only destroys the "disproof," it also shows that finding a 2N that is not the sum of two primes becomes exponentially more unlikely (yet still theoretically possible) as 2N increases.Bh12 (talk) 13:22, 30 September 2013 (UTC)

Resolved

Confusion about Diffie-Hellman

According to the article on Diffie-Hellman, for the algorithm to be secure: "The order of G should be prime or have a large prime factor to prevent use of the Pohlig–Hellman algorithm to obtain a or b". But since "p" is supposed to be prime and given that the generator "g" of group G is the primitive root mod "p", then the order of G is always going to be p-1 (which itself cannot be prime, obviously!). So should the wording in the article instead be: "The order of G should have a large prime factor to prevent use of the Pohlig–Hellman algorithm to obtain a or b" or am I just missing something here? Thanks! 70.112.97.77 (talk) 14:39, 30 September 2013 (UTC)

The article says very little about the choice of group, which does not (as far as I know) have to be the multiplicative group of integers modulo a prime, only a group in which the discrete logarithm is hard. Nevertheless, the alternative of the order of the group being prime is superfluous, and I have made your suggested change. In the specific case of this type of group, your observation that the order cannot be prime is correct (except, of course, in the trivial case of p = 3). — Quondum 16:10, 30 September 2013 (UTC)

Great, thanks for the clarification and correcting the page in question. Cheers! 70.112.97.77 (talk) 18:33, 30 September 2013 (UTC)

Resolved

Polynomial divisibility

Is there an algorithm that can determine whether a polynomial is divisible (with no remainder) by another polynomial that is faster than the standard polynomial long division? 68.0.144.214 (talk) 21:16, 30 September 2013 (UTC)

Not quite... But for instance if you happen to know the roots of one of them, then you can check and see if the other one has them as well. And if it doesn't, then they're not divisible. — 79.113.232.83 (talk) 22:18, 30 September 2013 (UTC)

But precisely that computation can be done without explicitly knowing the roots, you just reduce the polynomial modulo that other polynomial (that other polynomial is, of course, zero modulo itself), and that is much faster than division, becase you don't need to keep track of the quotient. Count Iblis (talk) 22:30, 30 September 2013 (UTC)

Is the question about polynomials with integer coefficients? --catslash (talk) 22:55, 30 September 2013 (UTC)

Instead of using standard polynomial long division, which would have complexity O(M(N-M)) for numerator and denominator polynomials of degrees N and M respectively, you can the Fast Fourier Transform to deconvolve the two polynomials and achieve a computational complexity of O(N log N) (see this page describing how to use FFTs for polynomial multiplication; the modifications for division are straightforward if you are familiar with convolution and the Discrete Fourier Transform). In practice, you will have to worry about problem conditioning and a few edge cases, but this will hopefully get you started. Note: There well may be a method to test for divisibility w/o performing the division at all, but I can't think of any except for special cases eg, when the roots of one of the polynomials is known (as mentioned above). Abecedare (talk) 05:48, 1 October 2013 (UTC)