On Lower Order Extremal Integral Sets Avoiding Prime Pairwise Sums

Ram Krishna Pandey Department of Mathematics Indian Institute of Technology, Patna Patliputra Colony, Patna - 800013 India

                    ram@iitp.ac.in

Abstract

Let A be a subset of {1, 2, …, n} such that the sum of no two distinct elements of A is a prime number. Such a subset is called a prime-sumset-free subset of {1, 2, …, n}. A prime-sumset-free subset 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. We prove that if n ≥ 10 then there is no any extremal prime-sumset-free subset of {1, 2, …, n} of order 2 and if n ≥ 13 then there is no any extremal prime-sumset-free subset of {1, 2, …, n} of order 3. Moreover, we prove that for each integer k ≥ 2, there exists a n_{k} such that if n ≥ n_{k} then there does not exist any extremal prime-sumset-free subset of {1, 2, …, n} of length k. Furthermore, for some small values of n, we give the orders of all extremal prime-sumset-free subset of {1, 2, …, n} along with an example of each order, and we give all extremal prime-sumset-free subsets of {1, 2, …, n} of orders 2 and 3 for n ≤ 13.

1 Introduction

Let A be a subset of {1, 2, …, n}. Then a combinatorial problem posed by Chen [1] is to study the subsets A such that

(A ˆ+A) ∩ P = ∅,  (1)

where A ˆ+A = {a + b : a, b ∈ A, a ≠ b} and P is the set of all prime numbers. Such a set is called a prime-sumset-free subset of the set {1, 2, …, n}. If we replace the set P above by a given set T of positive integers then A is called a T -sumset-free set. Chen [1] determined all prime-sumset-free subsets of {1, 2, …, n} with the largest cardinality. Let the largest cardinality be U_{n}. Chen [1] proved the following theorem.

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.

With this, the natural and more challenging question coming in mind is that what is the largest cardinality of A ⊂ {1, 2, …, n} satisfying (1) when A contains elements of both parities?

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} be the sequence of cardinalities of all the extremal prime-sumset-free subsets of {1, 2, …, n} with P F_{1}(n) > P F_{2}(n) > · · · . Then by the theorem of Chen we have P F_{1}(n) = U_{n} = ⌊\frac{1}{2}(n + 1)⌋.

In this paper we provide the sequence (P F_{k}(n)) for a few small values of n and we study the finite monotonic strictly decreasing sequence P F_{k}(n) with the largest term ⌊\frac{1}{2}(n+1)⌋ and the smallest term 2 (if it exists) from the lower end of the sequence for all sufficiently large values of n. In particular, we show that if n ≥ 10 then there is no extremal prime-sumset-free subset of {1, 2, …, n} of order 2 and if n ≥ 13 then there is no extremal prime-sumset-free subset of {1, 2, …, n} of order 3. That is in the case n ≥ 10 the sequence P F_{k}(n) will not take the value 2 and hence will terminate at 3 (if it exists) and in the case n ≥ 13 the sequence P F_{k}(n) will not take the value 3 and hence will terminate at 4 (if it exists) as P F_{k}(n) ≠ 1 for any n. We also prove that for each integer k ≥ 2, there exists a n_{k} such that if n ≥ n_{k} then there does not exist any extremal prime-sumset-free subset of {1, 2, …, n} of length k.

2 Main Results

Sometimes we use [n] for {1, 2, …, n} and PSFS for prime-sumset-free subset in this section. Observe that any proper subset of an extremal prime-sumset-free subset of {1, 2, …, n} of order l can not be an extremal prime-sumset-free subset of {1, 2, …, n}. Thus if we have extremal prime-sumset-free subsets of {1, 2, …, n} of both orders k and l where k < l then the extremal prime-sumset-free subset of {1, 2, …, n} of order k will not be a subset of the extremal prime-sumset-free subset of {1, 2, …, n} of order l. In the table below we provide the sequence (P F_{k}(n)) and an example of extremal prime-sumset-free subset of [n] for each term of the sequence for all 1 ≤ n ≤ 14.

n Sequence P F_{k}(n) with an extremal prime-sumset-free subset of [n] for each term
1  not defined
2  not defined
3  (P F_{k}(3)) ≡ (2); ({1,3})
4  (P F_{k}(4)) ≡ (2); ({1,3})
5  (P F_{k}(5)) ≡ (3, 2); ({1,3,5}, {2,4})
6  (P F_{k}(6)) ≡ (3, 2); ({1,3,5}, {4,5})
7  (P F_{k}(7)) ≡ (4, 3, 2); ({1,3,5,7}, {2,4,6}, {4,5})
8  (P F_{k}(8)) ≡ (4, 3, 2); ({1,3,5,7}, {2,7,8}, {4,5})
9  (P F_{k}(9)) ≡ (5, 4, 3, 2); ({1,3,5,7,9}, {2,4,6,8},{2,7,8}, {4,5})
10  (P F_{k}(10)) ≡ (5, 3); ({1,3,5,7,9},{2,7,8})
11  (P F_{k}(11)) ≡ (6, 5, 4, 3); ({1,3,5,7,9,11}, {2,4,6,8,10}, {4,5,10,11}, {1,7,8})
12  (P F_{k}(12)) ≡ (6, 4, 3); ({1,3,5,7,9,11}, {4,5,10,11}, {1,7,8})
13  (P F_{k}(13)) ≡ (7, 6, 4); ({1,3,5,7,9,11,13}, {2,4,6,8,10,12}, {1,7,8,13})
14  (P F_{k}(14)) ≡ (7, 5, 4); ({1,3,5,7,9,11,13}, {1,7,11,13,14}, {3,9,12,13})

Table 1: P F_{k}(n) and extremal-prime-sumset-free subset of [n] for 1 ≤ n ≤ 14

After having a look at the above table a natural question coming in mind is that for a given positive integer n does there exist an extremal prime-sumset-free subset of [n] of each order l, where 2 ≤ l < ⌊\frac{1}{2}(n + 1)⌋? We shall see that if n ≥ 10 then there is no extremal prime-sumset-free subset of [n] of order 2 and if n ≥ 13 then there is no extremal prime-sumset-free subset of [n] of order 3. Before we prove these results we give all extremal prime-sumset-free subset of [n] of order 2 and 3 for each n where 1 ≤ n ≤ 13 in the following table.

n All extremal PSFSs of [n] of order 2 All extremal PSFSs of [n] of order 3
3  {1,3}  not defined
4  {1,3,}, {2,4}  not defined
5  {2,4}, {4,5}  {1,3,5}
6  {6,3}, {4,5}  {1,3,5}, {2,4,6}
7  {2,7}, {6,3}, {4,5}  {2,4,6}
8  {6,3}, {4,5}  {1,7,8}, {2,7,8}
9  {4,5}  {1,7,8}, {2,7,8}, {3,6,9}
10  not exists  {1,7,8}, {2,7,8}, {3,6,9}, {4,5,10}
11  not exists  {1,7,8}, {2,7,8}, {3,6,9}
12  not exists  {1,7,8}, {2,7,8}
13  not exists  not exists

Table 2: Extremal prime-sumset-free subset of [n] of orders 2 and 3 for 1 ≤ n ≤ 13

Theorem 2. If n ≥ 10 then there does not exist any extremal prime-sumset-free subset of [n] of order 2.

Proof. The proof is by induction on n. If n = 10 then there does not exist any extremal prime-sumset-free subset of [10] of order 2. Indeed, we know that if n ≥ 6 then an extremal prime-sumset-free subset of order 2 (if exists) will contain integers of opposite parity. Therefore, the only possibilities of two elements subsets of [10] to be an extremal prime-sumset-free subset are the following sets:

{1, 8}, {3, 6}, {5, 4}, {5, 10}, {7, 2}, {7, 8}, {9, 6}

But none of the above sets is an extremal prime-sumset-free subset as each one is a subset of some prime-sumset-free subsets of order 3 given below.

{1, 8, 7}, {3, 6, 9}, {5, 4, 10}, {7, 2, 8}.

Hence the theorem is true for n = 10. Now let the theorem is true for k ≥ 10. Without loss of generality we can assume that k is odd. Take all subsets {k + 1, a} where a is odd and 1 ≤ a ≤ k such that k + 1 + a is a composite integer. We shall show that there exists an integer t such that t ∈ [k + 1] \ {k + 1, a} and both k + 1 + t and a + t are composite.

CASE I: 1 ≤ a ≤ k − 1. By induction the subset {k, a + 1} is not an extremal primesumset-free subset of [k]. Hence there exists an integer l ∈ [k] \ {k, a + 1} such that all l + k, k + a + 1 and a + 1 + l are composite integers. Now if l is odd then taking t = l + 1 and if l is even then taking t = l − 1, we see that {k + 1, a, t} is a prime-sumset-free subset of [k + 1]. Hence the theorem is true in this case.

CASE II: a = k. The subset {k + 1, a} becomes {k + 1, k}. In this case the integer t is given in the following table depending on k.

Units digit of k t
1  4
3  2
5  10
7  8
9  6

Table 3: t as a function of k

This completes the proof of the theorem.

Theorem 3. If n ≥ 13 then there does not exist any extremal prime-sumset-free subset of [n] of order 3.

Proof. Let A = {a_{1}, a_{2}, a_{3}} be a prime-sumset-free subset of [n] of order 3. We are required to show that A is not an extremal prime-sumset-free subset of [n]. If all elements of A are of same parity then clearly, A is not an extremal prime-sumset-free subset of [n] as n ≥ 13. So, let us assume that A contains elements of both parities.

CASE I: A contains two odd integers and an even integer. Without loss of generality let a_{1} be even.

Subcase (i): 2 ≤ a_{1} ≤ 10. First let a_{2}, a_{3} ∈ {1, 3, 5, …, 13}. In this case the only possibilities of the set A for each a_{1} is {2, 7, 13}, {4, 5, 11}, {6, 3, 9}, {8, 1, 7}, {8, 1, 13}, {8, 7, 13}, {10, 5, 11}. None of the above subsets is an extremal prime-sumset-free subset because of the following prime-sumset-free subsets.

{2, 7, 13, 8}, {4, 5, 11, 10}, {6, 3, 9, 12}, {8, 1, 7, 13}.

Secondly, let a_{2}, a_{3} be any odd numbers in A not necessarily from the set {1, 3, 5, …, 13} and the set A be distinct from the sets given in the above list: {2, 7, 13}, {4, 5, 11}, {6, 3, 9}, {8, 1, 7}, {8, 1, 13}, {8, 7, 13}, {10, 5, 11}. We have the following: 2 ∈ A ⇒ A ∪ {a} is a prime-sumset-free subset for some a ∈ {7, 13}, 4 ∈ A ⇒ A ∪ {a} is a prime-sumset-free subset for some a ∈ {5, 11}, 6 ∈ A ⇒ A ∪ {a} is a prime-sumset-free subset for some a ∈ {3, 9}, 8 ∈ A ⇒ A ∪ {a} is a prime-sumset-free subset for some a ∈ {1, 7, 13}, 10 ∈ A ⇒ A ∪ {a} is a prime-sumset-free subset for some a ∈ {5, 11}. Consequently, A is not an extremal prime-sumset-free subset. Thus we have seen that if 2 ≤ a_{1} ≤ 10 then A is not an extremal prime-sumset-free subset.

Subcase (ii): 12 ≤ a_{1} ≤ 28. In the list below, for each a_{1} we provide at least three distinct odd integers from [n] such that their sum with a_{1} give composite integers. Hence if 12 ≤ a_{1} ≤ 28, we do not have extremal prime-sumset-free subsets of [n] of length 3.

List: {12, 3, 9, 13}, {14, 1, 7, 11}, {16, 5, 9, 11}, {18, 3, 7, 9}, {20, 1, 5, 15}, {22, 3, 5, 13}, {24, 1, 3, 11}, {26, 1, 9, 19}, {28, 5, 7, 17}.

Subcase (iii): a_{1} ≥ 30. Depending on a_{1} we have at least three distinct odd integers from [n] such that their sum with a_{1} give composite integers. Hence if a_{1} ≥ 30, we do not have extremal prime-sumset-free subsets of [n] of length 3.

Units digit of a_{1} Three distinct odd integers
0  5,15,25
2  3,13,23
4  1,11,21
6  9,19,29
8  7,17,27

Table 4: Examples for Subcase (iii)

CASE II: A contains two even integers and an odd integer. Without loss of generality let a_{1} be odd.

Subcase (i): 1 ≤ a_{1} ≤ 11. First let a_{2}, a_{3} ∈ {2, 4, 6, …, 12}. In this case the only possibility of the set A for each a_{1} is {3, 6, 12}, {5, 4, 10}, {7, 2, 8}, {9, 6, 12}, {11, 4, 10}. None of the above subsets is an extremal prime-sumset-free subset because of the following primesumset-free subsets.

{3, 6, 12, 9}, {5, 4, 10, 11}, {7, 2, 8, 13}.

Secondly, let a_{2}, a_{3} be any even numbers of A not necessarily from the set {2, 4, …, 12} and the set A be distinct from the sets given in the above list: {3, 6, 12}, {5, 4, 10}, {7, 2, 8}, {9, 6, 12}, {11, 4, 10}. We have the following: 1 ∈ A and A = {1, 8, 14} then A is not an extremal prime-sumset-free subset because {1, 8, 14, 7} is a prime-sumset-free subset. 1 ∈ A and A ≠ {1, 8, 14} ⇒ A ∪ {a} is a prime-sumset-free subset for some a ∈ {8, 14}, 3 ∈ A ⇒ A ∪ {a} is a prime-sumset-free subset for some a ∈ {6, 12}, 5 ∈ A ⇒ A ∪ {a} is a prime-sumset-free subset for some a ∈ {4, 10}, 7 ∈ A ⇒ A ∪ {a} is a prime-sumset-free subset for some a ∈ {2, 8}, 9 ∈ A ⇒ A ∪ {a} is a prime-sumset-free subset for some a ∈ {6, 12}, 11 ∈ A ⇒ A ∪ {a} is a prime-sumset-free subset for some a ∈ {4, 10}. Consequently, A is not an extremal prime-sumset-free subset.

Subcase (ii): 13 ≤ a_{1} ≤ 29. In the list below, for each a_{1} we provide at least three distinct even integers from [n] such that their sum with a_{1} give composite integers. Hence if 13 ≤ a_{1} ≤ 29, we do not have extremal prime-sumset-free subsets of [n] of length 3.

List: {13, 2, 8, 12}, {15, 6, 10, 12}, {17, 4, 8, 10}, {19, 6, 8, 16}, {21, 4, 6, 14}, {23, 2, 4, 12}, {25, 2, 10, 20}, {27, 8, 18, 6}, {29, 4, 6, 16}.

Subcase (iii): a_{1} ≥ 31. Depending on a_{1} we have at least three distinct even integers from [n] such that their sum with a_{1} give composite integers. Hence if a_{1} ≥ 31, we do not have extremal prime-sumset-free subsets of [n] of length 3.

Units digit of a_{1} Three distinct even integers
1  4,14,24
3  2,12,22
5  10,20,30
7  8,18,28
9  6,16,26

Table 5: Examples for Subcase (iii)

This completes the proof of the theorem.

Inspired by the above two theorems, we have the following:

Theorem 4. For each integer k ≥ 2, there exists a n_{k} such that if n ≥ n_{k} then there does not exist any extremal prime-sumset-free subsets of [n] of length k.

One can consult [2] for definitions, notation and results used in the proof below.

Proof. Suppose that A = {a_{1}, a_{2}, …, a_{k}} be a prime-sumset-free subset of [n]. Clearly, by the definition of psfs we have that a_{i} + a_{j} = m_{ij} is a composite integer for each 1 ≤ i, j ≤ k. Let 1 < m_{j}^{i} < m_{ij} and m_{j}^{i}|m_{ij} for each fixed 1 ≤ i ≤ k and for each 1 ≤ j ≤ k. Let us consider the following k simultaneous congruences

x ≡ −a_{1} (mod m_{1}^{i})
x ≡ −a_{2} (mod m_{2}^{i})
⋮
x ≡ −a_{k} (mod m_{k}^{i})

for each 1 ≤ i ≤ k. Each one of the k simultaneous congruences is consistent being a_{i} is the common solution for the ith simultaneous congruence for each 1 ≤ i ≤ k. Set

a_{k+1}^{i} = a_{i} + t[m_{1}^{i}, m_{2}^{i}, …, m_{k}^{i}],

for each 1 ≤ i ≤ k and t ≥ 0 . We see that a_{k+1}^{i} is a solution of the ith simultaneous congruence and hence all a_{1} + a_{k+1}^{i}, a_{2} + a_{k+1}^{i}, …, a_{k} + a_{k+1}^{i} are composite integers for each 1 ≤ i ≤ k. Choosing t minimum such that a_{k+1}^{i} ∉ {a_{1}, a_{2}, …, a_{k}}, we see that for n ≥ n_{k} = max_{i} a_{k+1}^{i} := a_{k+1} we have all a_{1} + a_{k+1}, a_{2} + a_{k+1}, …, a_{k} + a_{k+1} are composite integers. Consequently, the set {a_{1}, a_{2}, …, a_{k+1}} is a prime-sumset-free subset of [n] and hence A is not an extremal prime-sumset-free subset of [n] of length k. This proves the theorem.

3 Acknowledgments

The author is very much thankful to the anonymous referee for his/her useful comments/suggestions (especially for the proof of the last theorem) to make the paper in a better format.

References

[1] Y. G. Chen, Integer sequences avoiding prime pairwise sums, J. Integer Sequences, 11 (2008), Article 08.5.6.

[2] I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers, John Wiley & Sons, 1991.

2000 Mathematics Subject Classification: Primary 11A41, Secondary 11B75, 05D05. Keywords: primes, sumsets, simultaneous congruences.

Received March 16 2012; revised version received June 1 2012. Published in Journal of Integer Sequences, June 12 2012.

Return to Journal of Integer Sequences home page.