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.
Best Answer
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.