Goldbach's weak conjecture

MattcAnderson · 2017-03-18, 10:51

Hi Mersenneforum,

The 3 primes problem, or weak Goldbach conjecture has been proved true by
Helfgott in 2013.

It simply states that all odd numbers < 7 are the sum of 3 odd prime numbers.

See
https://en.wikipedia.org/wiki/Goldba...eak_conjecture

In My Humble Opinion (IMHO) this was quite a proof.

wanted you to know.

Regards,
Matt

CRGreathouse · 2017-03-18, 23:32

Greater than 7, that is.

Yes, it was a big deal! The proof had three parts: major arcs, minor arcs, and verifying weak Goldbach on small values. The third part was joint work with Platt and was verified considerably further than necessary: to 8.875e30 when Helfgott needed only 10^27.

Here's my understanding of the major+minor arc decomposition. Instead of looking at the sum
$\sum_{p+q+r=N}1$
of the number of ways a given odd number N can be written as a sum of three primes, Helfgott looks at the related sum
$\sum_{p+q+r=N}\log p\log q\log r$
which is a weighted version of the first which is easier to work with analytically.

Next the sum is transformed into an integral
$\int_0^1 S(\alpha,x)^3 - \exp(-2\pi iN\alpha)d\alpha$
which is then split into two pieces: the major arcs, which are small intervals around rationals with small denominators, and the minor arcs which are everything else.

Actually, the integral Helfgott actually uses is a somewhat more complicated 'smoothed' version of this integral, but the basic idea is the same: it can be broken into major and minor arcs, and proving that it takes on positive values for a given N shows that weak Goldbach holds for that N.

Helfgott spends a paper describing how to bound the minor arcs very precisely, then has a somewhat easier task (because of the groundwork he laid) on the major arcs. Combining the two Helfgott proves that the smoothed integral is at least 0.000422 * N^2 when N is an odd number greater than 10^27, which together with the numerical verification with Platt proves the weak Goldbach conjecture.

Helfgott cites a lot of software used in the proof including PARI, Maxima, Gnuplot, VNODE-LP, PROFIL / BIAS, SAGE, and Platt’s interval-arithmetic package (based in part on Crlibm).

MattcAnderson · 2017-03-19, 18:23

Hi Mersenneforum,

In 2013, Harald Helfgott proved Goldbach's weak conjecture.

See -

Wikipedia Article about Goldbach's weak conjecture

I wrote some Maple (Maple is a computer algebra system.) code in order to shine a light on Harald's accomplishment.

Regards,
Matt

R. Gerbicz · 2017-03-19, 19:01

Quote:

Originally Posted by MattcAnderson

I wrote some Maple (Maple is a computer algebra system.) code in order to shine a light on Harald's accomplishment.

That is a surprisingly slow implementation.

MattcAnderson · 2017-03-19, 20:18

Hi again Mersenneforum,

So I was unable to improve my computer code significantly. I found better code at

Online Encyclopedia of Integer Sequences

My code cannot calculate gwc(7000) in under 102 seconds.

At least it produces correct results. (as far as I tested it.)

Regards,
Matt

danaj · 2017-03-19, 22:24

I added a simple Perl program based on Luschny's algorithm. It takes ~5 seconds on my laptop for a(7000).

Code:

perl -E 'use ntheory ":all"; sub a007963 { my($n,$c)=(shift,0); forpart { $c++ if vecall { is_prime($_) } @_; } $n,{n=>3,amin=>3}; $c; }  say "$_ ",a007963(2*$_+1) for 0..100;'

Pari/GP has a similar forpart function which last I checked was better optimized for restrictions so might run even faster. I am drawing a blank on a simple shortcutting "all" vector predicate, but worst case you could use a verbose for loop like Luschny's code.

For OEIS use it's almost getting to the point where it would be worthwhile to add a isprime option to forpart as seems to keep coming up as a restriction. It would make this function trivial.

danaj · 2017-03-19, 22:36

It was simple (5 lines) to add a prime restriction to my forpart, and it runs this function about 20x faster, since forpart's C code is doing all the work. 0.25s for a(7000).

CRGreathouse · 2017-03-20, 03:59

Here's a translation of the original program into GP:

Code:

gold(n)=sum(a=2,n\3,sum(b=2,a,sum(c=2,b,prime(a)+prime(b)+prime(c)==n)))

It takes about 31 seconds to find the a(1000) = 2216 3-Goldbach partitions of 2001.

Code:

gold1(n)=my(s,t); forprime(p=(n+2)\3,n-6, t=n-p; forprime(q=t\2,min(t-3,p), if(isprime(t-q), s++))); s

82 milliseconds for a(7000) = 48363 3-Goldbach partitions of 14001, about 2 milliseconds for a(1000). a(10^4) = 87357 took 166 ms, a(10^5) = 4242960 took 11 seconds.

These should definitely be improvable -- sieving should replace the final primality test for fairly large gains. But not bad for a one-line script.

CRGreathouse · 2017-03-20, 04:18

13 minutes, 52 seconds to get a(10^6) = 235945824.

While I'm here I'll also advertise my post on the other Goldbach thread Matt started recently, where I attempt to summarize Helfgott's basic argument.

danaj · 2017-03-20, 04:19

The OEIS sequence was fun, but to be clear it is horrifically slow in terms of the simpler question for the ternary Goldbach conjecture.

Helfgott in his intro describes the covering for all n < 10^27 "really a minor computational task." 1.2.2 discusses some methods. Using Oliveira e Silva et al.'s results of the binary Goldbach conjecture to 4*10^18 make it quite reasonable -- this rather underplays the considerable effort of that check. The paper co-authored with Platt points out how useful that result was. He notes it took 25 hours on a single core to finish the verification.

I wrote a simple checker and it's quite fast at first. Helfgott and Platt use a method that saves time on the primality proof by spending more time on the selection. I just used a simple prec_prime + is_provable_prime loop. The precprimes themselves are less than 2 hours on a single core to reach 10^27. The proofs are very fast until 3*10^24, then start sucking up quite a bit of time. I'm not sure it'd beat 25 hours, but I don't think it'd be too far off.

CRGreathouse · 2017-03-20, 04:35

Quote:

Originally Posted by danaj

The OEIS sequence was fun, but to be clear it is horrifically slow in terms of the simpler question for the ternary Goldbach conjecture.

Definitely -- any time you have a sequence that counts things, and a conjecture that says that from some point on, a(n) > 0, it's a waste to construct all of the things when you could just find one and then move on, and that goes double for sequences like this with near-quadratic (assumed) growth.

Quote:

Originally Posted by danaj

Helfgott in his intro describes the covering for all n < 10^27 "really a minor computational task." 1.2.2 discusses some methods. Using Oliveira e Silva et al.'s results of the binary Goldbach conjecture to 4*10^18 make it quite reasonable -- this rather underplays the considerable effort of that check. The paper co-authored with Platt points out how useful that result was. He notes it took 25 hours on a single core to finish the verification.

Yep. Although since they ended up going 8875 times higher the final calculation took 40,000 CPU-hours. Hmm, that's actually pretty good -- only 1600 times longer, they must have improved the algorithm further between those two.

2017-03-18, 10:51	#1
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 2³·149 Posts	Goldbach's weak conjecture Hi Mersenneforum, The 3 primes problem, or weak Goldbach conjecture has been proved true by Helfgott in 2013. It simply states that all odd numbers < 7 are the sum of 3 odd prime numbers. See https://en.wikipedia.org/wiki/Goldba...eak_conjecture In My Humble Opinion (IMHO) this was quite a proof. wanted you to know. Regards, Matt

2017-03-19, 22:24	#6
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 3²×101 Posts	I added a simple Perl program based on Luschny's algorithm. It takes ~5 seconds on my laptop for a(7000). Code: perl -E 'use ntheory ":all"; sub a007963 { my($n,$c)=(shift,0); forpart { $c++ if vecall { is_prime($_) } @_; } $n,{n=>3,amin=>3}; $c; } say "$_ ",a007963(2*$_+1) for 0..100;' Pari/GP has a similar forpart function which last I checked was better optimized for restrictions so might run even faster. I am drawing a blank on a simple shortcutting "all" vector predicate, but worst case you could use a verbose for loop like Luschny's code. For OEIS use it's almost getting to the point where it would be worthwhile to add a isprime option to forpart as seems to keep coming up as a restriction. It would make this function trivial.

2017-03-20, 03:59	#8
CRGreathouse Aug 2006 1011101100011₂ Posts	Here's a translation of the original program into GP: Code: gold(n)=sum(a=2,n\3,sum(b=2,a,sum(c=2,b,prime(a)+prime(b)+prime(c)==n))) It takes about 31 seconds to find the a(1000) = 2216 3-Goldbach partitions of 2001. Code: gold1(n)=my(s,t); forprime(p=(n+2)\3,n-6, t=n-p; forprime(q=t\2,min(t-3,p), if(isprime(t-q), s++))); s 82 milliseconds for a(7000) = 48363 3-Goldbach partitions of 14001, about 2 milliseconds for a(1000). a(10^4) = 87357 took 166 ms, a(10^5) = 4242960 took 11 seconds. These should definitely be improvable -- sieving should replace the final primality test for fairly large gains. But not bad for a one-line script.

2017-03-20, 04:18	#9
CRGreathouse Aug 2006 13543₈ Posts	13 minutes, 52 seconds to get a(10^6) = 235945824. While I'm here I'll also advertise my post on the other Goldbach thread Matt started recently, where I attempt to summarize Helfgott's basic argument. Last fiddled with by CRGreathouse on 2017-03-20 at 04:20

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Goldbach Conjecture	MattcAnderson	MattcAnderson	4	2021-04-04 19:21
Factorial and Goldbach conjecture.	MisterBitcoin	MisterBitcoin	17	2018-01-29 00:50
Goldbach's Conjecture	Patrick123	Miscellaneous Math	242	2011-03-15 14:28
Goldbach's conjecture	Citrix	Puzzles	3	2005-09-09 13:58

2017-03-18, 23:32	#2
CRGreathouse Aug 2006 5987₁₀ Posts	Greater than 7, that is. Yes, it was a big deal! The proof had three parts: major arcs, minor arcs, and verifying weak Goldbach on small values. The third part was joint work with Platt and was verified considerably further than necessary: to 8.875e30 when Helfgott needed only 10^27. Here's my understanding of the major+minor arc decomposition. Instead of looking at the sum $\sum_{p+q+r=N}1$ of the number of ways a given odd number N can be written as a sum of three primes, Helfgott looks at the related sum $\sum_{p+q+r=N}\log p\log q\log r$ which is a weighted version of the first which is easier to work with analytically. Next the sum is transformed into an integral $\int_0^1 S(\alpha,x)^3 - \exp(-2\pi iN\alpha)d\alpha$ which is then split into two pieces: the major arcs, which are small intervals around rationals with small denominators, and the minor arcs which are everything else. Actually, the integral Helfgott actually uses is a somewhat more complicated 'smoothed' version of this integral, but the basic idea is the same: it can be broken into major and minor arcs, and proving that it takes on positive values for a given N shows that weak Goldbach holds for that N. Helfgott spends a paper describing how to bound the minor arcs very precisely, then has a somewhat easier task (because of the groundwork he laid) on the major arcs. Combining the two Helfgott proves that the smoothed integral is at least 0.000422 * N^2 when N is an odd number greater than 10^27, which together with the numerical verification with Platt proves the weak Goldbach conjecture. Helfgott cites a lot of software used in the proof including PARI, Maxima, Gnuplot, VNODE-LP, PROFIL / BIAS, SAGE, and Platt’s interval-arithmetic package (based in part on Crlibm).

2017-03-19, 22:36	#7
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 909₁₀ Posts	It was simple (5 lines) to add a prime restriction to my forpart, and it runs this function about 20x faster, since forpart's C code is doing all the work. 0.25s for a(7000).

2017-03-20, 04:19	#10
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 3²·101 Posts	The OEIS sequence was fun, but to be clear it is horrifically slow in terms of the simpler question for the ternary Goldbach conjecture. Helfgott in his intro describes the covering for all n < 10^27 "really a minor computational task." 1.2.2 discusses some methods. Using Oliveira e Silva et al.'s results of the binary Goldbach conjecture to 410^18 make it quite reasonable -- this rather underplays the considerable effort of that check. The paper co-authored with Platt points out how useful that result was. He notes it took 25 hours on a single core to finish the verification. I wrote a simple checker and it's quite fast at first. Helfgott and Platt use a method that saves time on the primality proof by spending more time on the selection. I just used a simple prec_prime + is_provable_prime loop. The precprimes themselves are less than 2 hours on a single core to reach 10^27. The proofs are very fast until 310^24, then start sucking up quite a bit of time. I'm not sure it'd beat 25 hours, but I don't think it'd be too far off.