Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given an even integer N, what is the minimum set of primes such that any even number $x \leq N$ can be expressed as the sum of two primes in the set?

Goldbach's conjecture said Every even integer greater than 2 can be expressed as the sum of two primes. http://en.wikipedia.org/wiki/Goldbach's_conjecture

But think from the other way, it seems like we don't need that many primes in order to express every even number as the sum of two primes.

For example, there are 168 primes for $N=1000$, but using only 58 of them we can already express every even number as the sum of two primes: 2, 3, 5, 7, 13, 19, 23, 31, 37, 43, 47, 53, 61, 79, 83, 109, 113, 101, 131, 139, 157, 167, 199, 107, 211, 251, 281, 269, 283, 307, 313, 337, 293, 401, 421, 383, 439, 449, 431, 457, 491, 509, 523, 569, 601, 461, 643, 683, 673, 691, 743, 769, 761, 811, 863, 881, 929, 883

For $N=10000$, I found there only need 236 primes out of 1229: 2, 3, 5, 7, 13, 19, 23, 31, 37, 43, 47, 53, 61, 79, 83, 109, 113, 101, 131, 139, 157, 167, 199, 107, 211, 251, 281, 269, 283, 307, 313, 337, 293, 401, 421, 383, 439, 449, 431, 457, 491, 509, 523, 569, 601, 461, 643, 683, 673, 691, 743, 769, 761, 811, 863, 881, 929, 883, 983, 1013, 1031, 1063, 1069, 1097, 1103, 1129, 1151, 1163, 1181, 1237, 1229, 1307, 1327, 1399, 1381, 1367, 1459, 1511, 1489, 1559, 1567, 1637, 1699, 1787, 1811, 1709, 1831, 1879, 1931, 1901, 1951, 1973, 2063, 2081, 2099, 2161, 2153, 2243, 2273, 2287, 2207, 2309, 2381, 2411, 2417, 2377, 2473, 2503, 2593, 2663, 2671, 2621, 2731, 2819, 2843, 2861, 2969, 2971, 3011, 3049, 3119, 3137, 3187, 3299, 3373, 3319, 3461, 3541, 3533, 3583, 3631, 3623, 3709, 3761, 3779, 3793, 3833, 3923, 4021, 4073, 4091, 4111, 4133, 4177, 4241, 4259, 4273, 4337, 4339, 4357, 4363, 4523, 4621, 4657, 4703, 4721, 4729, 4813, 4861, 4943, 4973, 5099, 5153, 5119, 5209, 5303, 5351, 5347, 5393, 5443, 5521, 5573, 5581, 5693, 5701, 5743, 5903, 5923, 6053, 6037, 6203, 6277, 6287, 6473, 6469, 6529, 6569, 6607, 6581, 6653, 6659, 6719, 6781, 6841, 6863, 7039, 7121, 7129, 7177, 7253, 7351, 7417, 7517, 7523, 7703, 7691, 7741, 7823, 7879, 7951, 8123, 8101, 8111, 8243, 8269, 8039, 8291, 8443, 8537, 8681, 8747, 8783, 8819, 8849, 8839, 8933, 9091, 9187, 9241, 9323, 9419, 9349, 9551, 9547, 9803, 9883

All I can see is the lower bound of the size of necessary prime set is $\sqrt{N}$, the expected number of primes is $N/log(N)$, of course the later is much larger.

What is the law behind this? I'm not an expert in number theory, but just curious.

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

It is reasonable to believe that there is a constant $c$ such that that there exists a set of prime numbers containing at most $c \sqrt{x \log x}$ elements below $x$ such that each even number is the sum of two primes from this set. So the (lower) bound of $\sqrt{x}$ you mentioned is likely not too far away from the truth.

More specifically Granville showed (Theorem 2 in Refinements of Goldbach's conjecture, and the generalized Riemann hypothesis, Funct. Approx. Comment. Math. Volume 37, Number 1 (2007), 159-173) that this is true assuming a strong form of the Goldbach conjecture, namely that there is a positive constant $d$ such that each even number $n \gt 2$ has more than $d n/ (\log n)^2$ representations as a sum of two primes.

Essentially this came already up before on this site see Thin subbases for the primes? where among other things Mark Lewko also mentions this result.

share|improve this answer
    
I'm looking at the review of Granville's paper at MR, and it looks like where you have $c\sqrt x\log x$ it should be $c\sqrt{x\log x}$. –  Gerry Myerson May 24 '13 at 1:47
    
@Gerry Myerson: thank you, yes, this was a typo (which I fixed in parallel with your comment). As additional general remark: the paper is freely available on the page I link to. –  quid May 24 '13 at 2:02
    
Thank you quid, I know such kind of problem must have been studied long time ago, the related works you provide are great! (although as a computer science researcher I'm not sure if I can fully understand it:) –  user34326 May 24 '13 at 7:02
    
@unknown: You are welcome! –  quid May 24 '13 at 10:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.