# The minimal Goldbach basis

Let $n \in \mathbb{N}, n \geq 2$. By minimal Goldbach basis $G_{2n}$(if it is nonempty) of $2n$ , I mean the minimal set of primes such that every even number less than or equal to $2n$ can be written as a sum of two primes of that set. Minimal refers to the number of elements of the set. For instance,

$G_{4}= \left \{ 2 \right \}, G_{6}= \left \{ 2,3 \right \} , G_{8}= \left \{ 2,3,5 \right \}, G_{10}= \left \{ 2,3,5 \right \}$

However, $\left \{ 2,3,5,7 \right \}$ also works for $2n = 10$ but it is not minimal.

The minimal set is unique since among many possibilities(if any) we are choosing one that has (1) the smallest number of elements(this is the primary criterion) and (2)say, if we have $\left \{ 2,3,5,11,13\right\}$ and $\left \{ 2,3,5,7,13\right\}$, we would choose the second. That means when ordering the elements in increasing order, the one chosen will have elements that are smaller under pairwise comparison with the other choices.

Question 1:(not yet answered) Obviously, $\left | G_{2p} \right |\leq \pi(p)$, for primes p. Proving that $\left | G_{2n} \right |= 0$ for at least one $n$ is harder than the old Goldbach. Still harder would be to show that $\left | G_{2n}\left | \leq \right |G_{2n+2} \right |$ Also, some experiment shows that $\left | G_{2n} \right |= \pi(n) + 1$ when $n \geq6$ till the numbers I checked (excluding $n = 7$ and $13$). How good is this formula at least for some $n$?

Question 2:(has been answered below) Does $G_{2n}$ always contain the primes in linear order, without jumping any primes? (I asked this because none of the $G_{2n}$'s I computed have missing primes.)

Thanks.

N.B.: I have been making many revisions. So, some comments may not make sense. In that case, you may look up the edit history.

-
If the minimal set is not unique how are you defining G_{2n}? – Qiaochu Yuan Feb 8 '11 at 0:09
@Qiaochu, good point. The minimal set is unique since among many possibilities(if any) we are choosing one that has (1) the smallest number of elements(this is the primary criterion) and (2)say if we have$\left \{ 2,3,5,11,13\right\}$ and $\left \{ 2,3,5,7,13\right\}$, we would choose the second. That means when ordering the elements in increasing order, the one chosen will have elements that are smaller under pairwise comparison with the other choices. I will add this above. – Unknown Feb 8 '11 at 0:36
Are there any results relating to how 'thin' a prime basis can be? In other words where the asymptotic for the representation function $r_{Q,h}(n)$ is small asymptotically for some subset $Q$ of the primes. – Stanley Yao Xiao Feb 8 '11 at 2:12
You say that the largest pairwise sum is $2n$, but your example of $G_8$ has a pairwise sum $5+5 =10$. Could you describe the pairwise sum condition more precisely? – S. Carnahan Feb 8 '11 at 4:59
@Scott, sorry. I will do that. – Unknown Feb 8 '11 at 10:26

corrected: I'll ignore the prime 2 and sums giving 4. Then $G_{32}=\lbrace 3, 5, 7, 13, 19, 23 \rbrace$. This is the only solution with 6 primes and there are none with 5:

A set of 5 primes could at best give 15 distinct pairwise sums. 3 is needed for 6 and 5,7 for 12. The only ways to get 32 are 3+29 and 13+19. A set of 5 primes including 3,5,7,29 would give sums as large as 36 (as well as 10 in two ways .. thanks other aaron) and hence could not give all even numbers from 4 to 32.

The minimality criterion is not totally clear but that may not matter since your questions are only about the size anyway. There are 4 ways to have a set of 11 odd primes generate all even sums from 4 up to 84. Since $\pi(42)=13$ this shows that one can have $|G_{2n}|<\pi(n)+1$ (and then some) even if we decide to include the prime $2$ for the sole purpose of getting the sum 4. One way is $\lbrace 3,5,7,13,17,19,23,29,31,53,61 \rbrace$.

There is every reason to believe that for every r there are only finitely many even numbers which can be written in less ways than r as a sum of two primes. In the same spirit, I'm confident that one could show (heuristically of course) this: Select an infinite set G of primes taking each one with probability p (at random) (or taking every kth prime). Then there are only finitely many even integers which are not in G+G (so we can fix G to a true basis by adding in finitely many of the excluded primes).

I did an experiment by starting with the G being the primes from 3 to 23 and then greedily looking for the first even number not in G+G (the target) and introducing into G the LARGEST prime which lets me get that target. I stopped once I had the even numbers up to 2000. My last 4 targets were 1798,1886,1946,1948. The first few evens then not accounted for were 2048,2050,2068,2080,2092.. $\pi(1024)=172$ and $\pi(2048)=309$ . This process (which only gives an upper bound for $|G_{2n}|$) Used 88 primes. The proportion of primes used seemed to decrease and be around 1/3 near the end. Here are the primes from 1400 to 2000. The ones in bold are used in this set $G$. It may be that a few excluded primes get picked up later (the next few targets will require 1979,1987 and 1997) but the behavior of large gaps followed by taking every few seems to happen (based on this small sample)

1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,

1499 , 1511, 1523, 1531, 1543, 1549, 1553, 1559,

1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,

1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783,

1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877,

1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999

-
@Aaron, thanks for your interest. Since $\binom{5}{2}$ is 10, how did you get 30? Are you providing counterexamples. I'm sorry. I did not understand your intention. – Unknown Feb 8 '11 at 3:12
A set of primes could give 15 distinct sums (repeats are allowed). There are 14 evens from 6 to 32 (inclusive) so having 36 and at least one repeat, e.g. 5+5=3+7, rules out a set of 5 primes including 3,5,7,29. – aaron Feb 8 '11 at 3:17
I think we are having a misunderstanding w.r.t notation. $G_{16}=G_{2\times 8}=\left \{ 2,3,5,7,11 \right \}$ So, interpreting your example $G_{32}=G_{2\times 16}=\left \{ 2,3,5,7,13,19,23 \right \}$. – Unknown Feb 8 '11 at 3:57
@Aaron, I have edited my question. I had the implicit assumption that the largest pairwise sum from $G_{2n}$ to be $2n$. – Unknown Feb 8 '11 at 3:59
@Aaron, thanks. I have revised the criteria. We are done with Q2. Q1 remains, which I think is harder. – Unknown Feb 8 '11 at 10:47