Integer Sequences Avoiding Prime Pairwise Sums

Yong-Gao Chen^{1} Department of Mathematics Nanjing Normal University Nanjing 210097 P. R. CHINA

                      ygchen@njnu.edu.cn

Abstract

The following result is proved: If A ⊆ {1, 2, …, n} is the subset of largest cardinality such that the sum of no two (distinct) elements of A is prime, then |A| = ⌊(n+1)/2⌋ and all the elements of A have the same parity. The following open question is posed: what is the largest cardinality of A ⊆ {1, 2, …, n} such that the sum of no two (distinct) elements of A is prime and A contains elements of both parities?

1 Introduction

Some combinatorial problems have the following structure: find subsets A ⊆ {1, 2, …, n} such that the sum of no two (distinct) elements of A belongs to T, where T is a given set. We say that such a A is a T -sumset-free set. In this note we deal with the case T = P, the set of all primes. There appear to be no previous papers on this topic.

We try to determine all prime-sumset-free subsets of {1, 2, …, n} with the largest cardinality. Let the largest cardinality be U_{n}. It is clear that the set of all even (odd) integers in {1, 2, …, n} is a prime-sumset-free set. So U_{n} ≥ ⌊(n + 1)/2⌋. If n + 1 is prime, then by considering a and n + 1 − a we have U_{n} ≤ ⌊(n + 1)/2⌋. Thus U_{n} = ⌊(n + 1)/2⌋ if n + 1 is prime. By employing results about the distribution of primes we prove

Theorem 1. For all n ≥ 1 we have U_{n} = ⌊\frac{1}{2}(n + 1)⌋. Furthermore, if A ⊆ \{1, 2, …, n\} is a prime-sumset-free set with |A| = U_{n}, then all elements of A have the same parity.

1Supported by the National Natural Science Foundation of China, Grant No. 10771103.

A prime-sumset-free subset A of {1, 2, …, n} is called an extremal prime-sumset-free subset of {1, 2, …, n} if A∪{a} is not a prime-sumset-free subset for any a ∈ {1, 2, …, n}\ A. Let P F_{k}(n) (k = 1, 2, …) be the sequence of cardinalities of all extremal primesumset-free subsets of {1, 2, …, n} with P F_{1}(n) > P F_{2}(n) > . . .. By the theorem we have P F_{1}(n) = U_{n} = ⌊(n + 1)/2⌋. We pose the following open question:

Question 2. What are the values of P F_{k}(n)? In particular, What is the value of P F_{2}(n)?

Question 3. Determine all extremal prime-sumset-free subsets A with |A| = P F_{2}(n).

2 Proof of the Theorem

Although the proof of the second part implies the first part, we give a proof of the first part by induction and the application of Bertrand’s postulate here. It is easy to see that the conclusion is true for n = 1. Now we assume that the conclusion is true for n < k(k ≥ 2). By the Bertrand’s postulate (see [1]) there exists a prime p with k < p < 2k. Assume that A ⊆ {1, 2, …, n} is prime-sumset-free. For p − k ≤ a ≤ k we have |{a, p − a} ∩ A| ≤ 1. So

|A ∩ [p − k, k]| ≤ \frac{1}{2}(2k − p + 1).

By the induction hypothesis we have

|A ∩ [1, p − k − 1]| ≤ \frac{1}{2}(p − k).

Hence

|A ∩ [1, k]| ≤ \frac{1}{2}(2k − p + 1) + \frac{1}{2}(p − k) = \frac{1}{2}(k + 1).

This implies that U_{k} ≤ [(k + 1)/2]. By the remark before the theorem we have U_{k} ≥ ⌊(k + 1)/2⌋. So U_{k} = ⌊(k + 1)/2⌋. This completes the proof of the first part.

To prove the second part of Theorem 1, we need a lemma.

Lemma 4. For any real number x ≥ 8 we have

π(\sqrt{2}x) − π(x) ≥ 1.

In particular, if m, n are positive integers with m > \sqrt{2}n and n ≥ 8, then there exists at least one prime p with m > p > n.

Proof. By direct calculation we know that Lemma 4 is true for 8 ≤ x ≤ 25. If x > 25, by Nagura [2] (see also [3, Lemma 4] ) we have

π(\sqrt{2}x) − π(x) ≥ π(\frac{6}{5}x) − π(x) ≥ 1.

This completes the proof of Lemma 4.

Now we return to prove the second part of Theorem 1.

For n ≤ 8 we can verify Theorem 1 directly. Now we assume that k > 8 and Theorem 1 is true for all n < k. Let A ⊆ {1, 2, …, k} be a prime-sumset-free set with |A| = U_{k}. Let q_{k} be the largest prime q with q ≤ 2k. By Lemma 4 we have q_{k} > \sqrt{2}k. If 8 < k ≤ 20, by direct verification we have q_{k} − k ≥ 8. If k ≥ 21, then q_{k} − k > (\sqrt{2} − 1)k ≥ 8. For any q_{k} − k ≤ a ≤ k we have |A ∩ {a, q_{k} − a}| ≤ 1. Hence

|A ∩ [q_{k} − k, k]| ≤ \frac{1}{2}(2k − q_{k} + 1).

Since A ∩ [1, q_{k} − k − 1] is a prime-sumset-free set, we have

|A ∩ [1, q_{k} − k − 1]| ≤ U_{q_{k}−k−1} = ⌊\frac{1}{2}(q_{k} − k)⌋.

By the assumption |A| = U_{k} = ⌊(k + 1)/2⌋ we have

⌊\frac{1}{2}(k + 1)⌋ = |A| = |A ∩ [1, q_{k} − k − 1]| + |A ∩ [q_{k} − k, k]|
≤ ⌊\frac{1}{2}(q_{k} − k)⌋ + \frac{1}{2}(2k − q_{k} + 1)
= ⌊\frac{1}{2}(k + 1)⌋.

So

|A ∩ [1, q_{k} − k − 1]| = ⌊\frac{1}{2}(q_{k} − k)⌋ = U_{q_{k}−k−1}.

If 2|k, then by the induction hypothesis we have

A ∩ [1, q_{k} − k − 1] = {1, 3, …, q_{k} − k − 2} or {2, 4, …, q_{k} − k − 1}.

If 2 |̸k, then by the induction hypothesis we have

A ∩ [1, q_{k} − k − 1] = {1, 3, …, q_{k} − k − 1}.

Case 1: 2|k and A ∩ [1, q_{k} − k − 1] = {1, 3, …, q_{k} − k − 2}.

Let 2m ∈ [q_{k} − k, k]. Then

\frac{2m + q_{k} − k}{2m} = 1 + \frac{q_{k} − k}{2m} > 1 + \frac{\sqrt{2}k − k}{k} = \sqrt{2}.

By q_{k} − k ≥ 8 and Lemma 4 there exists at least one prime p with 2m < p < 2m + q_{k} − k. So 1 ≤ p − 2m ≤ q_{k} − k − 2. Thus p − 2m ∈ A ∩ [1, q_{k} − k − 1]. Hence 2m ∉ A. So

A ⊆ {1, 3, 5, …, k − 1}.

Since |A| = U_{k} = \frac{1}{2}k, we have A = \{1, 3, 5, …, k − 1\}.

Case 2: 2|k and A ∩ [1, q_{k} − k − 1] = {2, 4, …, q_{k} − k − 1}.

Let 2m + 1 ∈ [q_{k} − k, k]. Then

\frac{2m + 1 + q_{k} − k}{2m + 1} = 1 + \frac{q_{k} − k}{2m + 1} > 1 + \frac{\sqrt{2}k − k}{k} = \sqrt{2}.

By q_{k}−k ≥ 8 and Lemma 4 there exists at least one prime p with 2m+1 < p < 2m+1+q_{k}−k. So 1 ≤ p − 2m − 1 ≤ q_{k} − k − 1. Thus p − 2m − 1 ∈ A ∩ [1, q_{k} − k − 1]. Hence 2m + 1 ∉ A. So

A ⊆ {2, 4, …, k}.

Since |A| = U_{k} = \frac{1}{2}k, we have A = \{2, 4, …, k\}.

Case 3: 2 |̸k. Then

A ∩ [1, q_{k} − k − 1] = {1, 3, …, q_{k} − k − 1}.

Let 2m ∈ [q_{k} − k, k]. Then

\frac{2m + q_{k} − k}{2m} = 1 + \frac{q_{k} − k}{2m} > 1 + \frac{\sqrt{2}k − k}{k} = \sqrt{2}.

By q_{k} − k ≥ 8 and Lemma 4 there exists at least one prime p with 2m < p < 2m + q_{k} − k. So 1 ≤ p − 2m ≤ q_{k} − k − 1. Thus p − 2m ∈ A ∩ [1, q_{k} − k − 1]. Hence 2m ∉ A. So

A ⊆ {1, 3, 5, …, k − 1}.

Since |A| = U_{k} = \frac{1}{2}(k − 1), we have A = \{1, 3, 5, …, k − 1\}.

This completes the proof.

3 Acknowledgements

We would like to thank the referee for his/her helpful comments and S. D. Adhikari for improving English.

References

[1] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Ed., Oxford University Press, 1979.

[2] J. Nagura, On the interval containing at least one prime number, Proc. Japan Acad. 28(1952), 177–181.

[3] Y. -G. Chen, The Analogue of Erdős-Turán Conjecture in Z_{m}, J. Number Theory 128 (2008), 2573–2581.

2000 Mathematics Subject Classification: Primary 11A41; Secondary 11B75, 05D05. Keywords: primes, sumsets, distribution of primes.

Received April 16 2008; revised version received December 13 2008. Published in Journal of Integer Sequences, December 13 2008.

Return to Journal of Integer Sequences home page.