Problems 66 and 67 on sums of residue classes and primes of András Sárközy’s collection of unsolved problems Yuchen Ding, Christian Elsholtz, Yu-Chen Sun Abstract . In this note, we discuss two problems of Sárközy (2001). In particular, we prove an optimal result on sumsets of sparse subset of primes. 2010 Mathematics Subject Classification Primary 11A41, 11A05 1. Sárközy’s problems In this paper we look at two problems from the collection of open problems by András Sárközy (2001) [ 16 ] . Problem 66 . Is it true, that if \varepsilon>0,m\in\mathbb{N} , m is even, m\rightarrow\infty , and A is a set of distinct modulo m reduced 1 1 1 The word “reduced” is missing here, but it is required, for details see the beginning of section 2 . Also, Sárközy compares with \varphi(m) , which is the number of reduced residue classes modulo m . residue classes with |A|>\Big(\frac{1}{2}+\varepsilon\Big)\varphi(m), then a) A+A contains almost all even residue classes modulo m ; b) A+A+A contains every odd residue class modulo m ? Problem 67 . Is it true that if Q=\{q_{1},q_{2},\ldots\} is an infinite set of primes such that \liminf_{x\rightarrow\infty}\frac{\log x}{x}|\{q_{i}:q_{i}\leq x,q_{i}\in Q\}|>\frac{1}{2}, then every large odd integer 2n+1 can be represented in the form q_{i}+q_{j}+q_{k}=2n+1~(\text{with~}q_{i},q_{j},q_{k}\in Q)? Here A+A=\{a_{i}+a_{j}:a_{i},a_{j}\in A\} is the usual sumset notation, similarly Q-W=\{q_{i}-w_{j}:q_{i}\in Q,w_{j}\in W\} . Problem 66 can be understood as an analogue of the well known problems of sums of two primes (in part a) and sums of three primes (in part b) in the positive integers, to the group \mathbb{Z}_{m}^{*} of reduced residue classes modulo m . For sums of two primes the famous Goldbach conjecture states that every even integer n\geq 4 can be written as a sum of two primes. This conjecture is still open. There are many partial results proving it for almost all even numbers, including a result by Pintz [ 13 ] saying that the number of possible exceptions below X is at most X^{3/4} , for sufficiently large X . The so called ternary Goldbach conjecture states, that every odd integer n\geq 7 can be written as a sum of three primes. This was proven, under the additional assumption of the generalized Riemann Hypothesis (GRH) for all but at most finitely many exceptions by Hardy and Littlewood (1923), and unconditionally for all but at most finitely many exceptions by I.M. Vinogradov (1937) [ 19 ] . A complete proof of the ternary Goldbach problem was announced by Harald Helfgott [ 9 ] , the final version is yet to appear. These very well known problems in the integers have their origin in a correspondence of 1742 between Christian Goldbach and Leonhard Euler, even though the precise statements were a bit different: at that time the integer 1 was considered to be a prime, whereas today one does not consider 1 as a prime, by definition, as it would make statements about unique factorization much more clumsy. An analogue of the binary Goldbach problem has been proved in the ring of polynomials, and has been a popular theme [ 8 , 10 , 14 , 15 ] and see also [ 6 ] . Note that in these cases a positive proportion of the polynomials is irreducible. For Problem 67 subsets of the primes now come into the play. Let \pi(x) denote the number of primes p\leq x . The function \pi(x) grows asymptotically like \frac{x}{\log x} . Sárközy’s question 67 is a very early example of a question on sums of primes with a positive density, (relative to the set of all primes). (In fact, we are aware of some growing literature on this topic, starting in 2011, see e.g. [ 1 , 2 , 3 , 4 , 7 , 11 , 17 , 20 ] .) Problem 67 can be understood as asking whether the Vinogradov approach (using the circle) method can be extended if one only uses a bit more than half of all primes, or whether other serious obstacles could occur. In [ 20 ] Yang and Togbé answered negatively Problem 67 and obtained more explicit results on this problem. We will make further considerations of it later in Section 3. 2. Problem 66 There is a small inaccuracy in Sárközy’s original statement. Without the word “reduced” simple counter examples are products of the first primes: m=p_{1}p_{2}\cdots p_{t} . Here it is well known that \varphi(m)\sim e^{-\gamma}\frac{m}{\log\log m} , where e=2.718\ldots is the base of the natural logarithm and \gamma=0.577\ldots is the Euler-Mascheroni constant. With such small values of \varphi(m) the choice {\mathcal{A}}=\{i\mod m:1\leq i\leq\varphi(m)\} shows that |{\mathcal{A}}+{\mathcal{A}}|=2\varphi(m)-1 and |{\mathcal{A}}+{\mathcal{A}}+{\mathcal{A}}|=3\varphi(m)-2 . As m=p_{1}\cdots p_{t}\rightarrow\infty , the proportion of residue classes represented by A+A or A+A+A respectively, tends to 0 . Next let us first look at the ternary case b) for which we not only find counter examples to the question, but also find an essentially best possible answer to the problem. As the problem is about a ternary sum of reducible residue classes it is natural to compare this with results on the sum of three primes. In his work on a density result to the ternary Goldbach problem Shao [ 17 ] gave the following example. Let A_{1}=\{1,2,4,7,13\}\subset\mathbb{Z}/(15\mathbb{Z}) . 2 2 2 We remark that in a later paper Shen [ 18 ] used A_{2}=\{1,4,7,11,13\} to avoid the class 2\mod 15 in A_{2}+A_{2}+A_{2} . This second example is isomorphic to the first one, as a multiplication by 13 shows. Then |A_{1}|>\frac{\varphi(15)}{2}=4 , but the residue class 14\pmod{15} is not in A_{1}+A_{1}+A_{1} , which would answer negatively Problem 66b via slight adjustments according to its requirements. As Sárközy’s question is about large even m , we modify the example above as follows. Let p be a sufficiently large prime, let m=30p and therefore \varphi(m)=8(p-1) , and let A=\{30k+1,30k+7,30k+13,30k+17,30k+19:1\leq 30k\leq m\}. For each i\in\{1,7,13,17,19\} there is at most one k with the constraint 1\leq 30k\leq m satisfying 30k+i\equiv 0\pmod{p} , leading to the bound |A|\geq\frac{m}{6}-5=\frac{5}{8}\varphi(m). One easily checks that 29\pmod{30} cannot be written as the sum of A_{0}+A_{0}+A_{0} , where A_{0}=\{1,7,13,17,19\pmod{30}\}. As a simple consequence, we know that no member of A+A+A is contained in \{30k+29\pmod{m}:1\leq 30k\leq m\} , answering negatively problem 66b). Next we come to Problem 66a). Here we have an even simpler counter example, based on residue classes modulo 12. Let p be a sufficiently large prime, m=12p , and A=\{12k+1,12k+5,12k+7:1\leq 12k\leq m\}. Similar discussions as above lead to |A|\geq 2\varphi(m)/3 as well as that no element of \{12k+4\pmod{m}:1\leq 12k\leq m\} is in A+A , which yields a proportion of 1/6 of all the even residue classes modulo m not covered by A+A . The following quite different type of counter example to Problem 66a) may be of independent interest. If a class a in \{1,2,4,7,13\} is even we replace it by a+15 . This gives the set A=\{1,7,13,17,19\} , understood as residue classes modulo 30 . Then |A|>\frac{\varphi(30)}{2}=4 , but the residue classes B=\{10,12,16,22,28\pmod{30}\} are not in A+A . We obtain the infinite family m_{k}=30\cdot 2^{k} . Choose A_{1}=A\cup(A+30)\subset\mathbb{Z}/(60\mathbb{Z}) and for any k\geq 1 , \quad A_{k+1}=A_{k}\cup(A_{k}+2^{k}\cdot 30)\subset\mathbb{Z}/(30\cdot 2^{k+1}\mathbb{Z}). Hence |A_{k}|=5\cdot 2^{k}>\frac{1}{2}\varphi(30\cdot 2^{k})=2^{k+2} , and A_{k}+A_{k} misses out a positive proportion of the even residue classes modulo m_{k} . This provides another counter example of Problem 66a). We point out that Sárközy’s predicition, i.e., Problem 66 b), is not far from the truth. Actually, Shao [ 17 , Corollary 1.5] proved the following very interesting result. Proposition 1 . Let m be a square-free positive odd integer. Let A be a subsets of \mathbb{Z}_{m}^{*} with |A|>\frac{5}{8}\varphi(m). Then A+A+A=\mathbb{Z}_{m}. Here \mathbb{Z}_{m}=\mathbb{Z}/m\mathbb{Z} and \mathbb{Z}_{m}^{*}=(\mathbb{Z}/m\mathbb{Z})^{*} . This gives a best possible result for odd m , which is sharp, for example when m=15 . As a conclusion, we now have the following theorem. Theorem 1 . The answers to Problem 66 a) and b) are both negative. Moreover, if we replace 1/2 and even m by 5/8 and odd squre-free m respectively, the answer to b) will be positive. It is here also worth mentioning a more general version proved by Shen [ 18 , Corollary 1.4] . Let m be a square-free positive odd integer. Let A_{1},A_{2},A_{3} be three subsets of \mathbb{Z}_{m}^{*} with |A_{1}|>\frac{5}{8}\varphi(m),|A_{i}|\geq\frac{5}{8}\varphi(m)\,(i=2,3) . Then A_{1}+A_{2}+A_{3}=\mathbb{Z}_{m}. 3. Problem 67 This question is on primes, but as almost all of the primes lie in the reduced residue classes modulo any fixed integer m the two problems are closely connected. As pointed out by Yang and Togbé [ 20 ] , the negative answer of Problem 67 can be concluded from Shao [ 17 ] as follows. Let Q be the set of primes in the residue classes 1,2,4,7,13\pmod{15} . Then the counting function of elements p\leq x of Q is Q(x)\sim\frac{5}{8}\frac{x}{\log x}>\frac{1}{2}\frac{x}{\log x} , by Dirichlet’s theorem on primes in arithmetic progressions [ 5 ] . As the residue class 14 modulo 15 cannot be written as a ternary sum of \{1,2,4,7,13\} there is even a positive proportion of all integers which are counter examples to this question. We now state Shao’s important result below for further discussions. Proposition 2 (Shao [ 17 ] ) . If Q=\{q_{1},q_{2},\ldots\} is an infinite set of primes such that (1) \displaystyle\liminf_{x\rightarrow\infty}\frac{\log x}{x}|\{q_{i}:q_{i}\leq x,q_{i}\in Q\}|>\frac{5}{8}, then every large odd integer 2n+1 can be represented in the form q_{i}+q_{j}+q_{k}=2n+1~(\text{with~}q_{i},q_{j},q_{k}\in Q). In [ 20 ] , Yang and Togbé also constructed a set Q of primes with upper relative prime density 1 such that there are infinitely many odd integers n that cannot be represented as q_{1}+q_{2}+q_{3}=2n+1 with q_{i}\in Q~(1\leq i\leq 3) . Moreover, the set Q in their construction has lower relative prime density 1/3 . It now seems of interest to step a little further on the counter example of Problem 67, pursuing the maximal value of the lower relative prime density. We now state our main result, which may appear surprising, in view of the proposition above. Theorem 2 . There is an infinite set Q of primes with upper relative prime density 1 and lower relative prime density 5/8 such that there are infinitely many odd integers 2n+1 that cannot be represented as q_{1}+q_{2}+q_{3}=2n+1 with q_{i}\in Q~(1\leq i\leq 3) . Proof. Let \mathcal{P} be the set of primes and S any subset of \mathcal{P} . For any x , let S(x) be the number of elements of S not exceeding x . Define \overline{d}(S)=\limsup_{x\rightarrow\infty}\frac{\log x}{x}|\{s_{i}:s_{i}\leq x,~s_{i}\in S\}| and \underline{d}(S)=\liminf_{x\rightarrow\infty}\frac{\log x}{x}|\{s_{i}:s_{i}\leq x,~s_{i}\in S\}|. We will construct the desired set Q step by step. Step 1. We first construct a set H\subset\mathcal{P} with \overline{d}(H)=1 and \underline{d}(H)=\frac{5}{8} . Let x_{1} be a sufficiently large number and x_{2}=e^{e^{x_{1}}}. Define H_{1}=(x_{1},x_{2}]\cap\mathcal{P}. Let d_{2}=e^{e^{x_{2}}} . Then we choose some odd integer x_{3}>d_{2} satisfying x_{3}\equiv 29\pmod{30}. Let H_{2}=\big\{p\in\mathcal{P}:x_{2}
d_{2k+2} satisfying x_{2k+3}\equiv 29\pmod{30} . Define H_{2k+2}=\big\{p\in\mathcal{P}:x_{2k+2}
\frac{x_{2k+1}}{\sqrt{\log x_{2k+1}}}.
We conclude from (
3
) and (
7
) that
Q(x)\sim W(x),
as
x\rightarrow\infty
since
\pi\bigg(\frac{x_{2k+1}}{\sqrt{\log x_{2k+1}}}\bigg)\gg\frac{x_{2k+1}}{(\log x_{2k+1})^{3/2}},
where
\pi(x)
is the number of primes not exceeding
x
.
Fact 2. For sufficiently large
k
, we have
x_{2k+1}\not\in Q+Q+Q.
Assume the contrary, we have
x_{2k+1}=q_{1}+q_{2}+q_{3}~(q_{1}\leq q_{2}\leq q_{3}).
We separate our discussions into three case.
Case I.
q_{1},q_{2},q_{3}\in Q_{2k}
.
This is an apparent contradiction since any odd integer
29\pmod{30}
is not contained in the ternary sumset
Q_{2k}+Q_{2k}+Q_{2k}
.
Case II.
q_{1},q_{2}\not\in Q_{2k}
and
q_{3}\in Q_{2k}
. By the construction, we have
q_{1}+q_{2}+q_{3}\leq 2x_{2k}+\Big(x_{2k+1}-x_{2k}-\frac{x_{2k+1}}{\sqrt{\log x_{2k+1}}}\Big)