\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
Integer Sequences Avoiding Prime Pairwise \\
\vskip .1in Sums
}
\vskip 1cm
\large
Yong-Gao Chen\footnote{Supported by the
National Natural Science Foundation of China, Grant No.\ 
10771103.}\\ 
Department of Mathematics \\
Nanjing Normal University\\  
Nanjing 210097 \\
P. R. CHINA\\
\href{mailto:ygchen@njnu.edu.cn}{\tt ygchen@njnu.edu.cn} \\
\end{center}

\vskip .2 in

\begin{abstract}
The following result is proved: If $A\subseteq \{
1,\, 2,\,  \ldots ,\,  n\} $ is the subset of largest cardinality such
that the sum of  no two (distinct) elements of $A$ is  prime, then
$|A|=\lfloor(n+1)/2\rfloor$ and all the elements of $A$ have the
same parity. The following open question is posed: what is the
largest cardinality of $A\subseteq \{ 1,\, 2,\,  \ldots ,\,  n\} $
such that the sum of  no two (distinct) elements of $A$ is  prime
and $A$ contains elements of both parities?
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Example}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}
\newtheorem{ques}[theorem]{Question}
\newenvironment{question}{\begin{ques}\normalfont\quad}{\end{ques}}


\section{Introduction}

Some combinatorial problems have the following structure:
find subsets $A\subseteq \{ 1,\,  2,\,  \ldots ,\,  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 {\it
$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,\, \ldots ,\,  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,\, \ldots
,\, n\} $ is a prime-sumset-free set. So $U_n\ge
\lfloor(n+1)/2\rfloor$. If $n+1$ is prime,\, then by considering
$a$ and $n+1-a$ we have $U_n\le \lfloor(n+1)/2\rfloor$. Thus
$U_n=\lfloor(n+1)/2\rfloor$ if $n+1$ is prime. By employing
results about the distribution of primes we prove 

\begin{theorem}\label{thm1}
For all $n\ge 1$ we have
$U_n=\lfloor\frac12(n+1)\rfloor$. Furthermore,\,  if $A\subseteq
\{ 1,\, 2,\, \ldots ,\,  n\} $ is a prime-sumset-free set with
$|A|=U_n$,\, then all elements of $A$ have the same
parity.
\end{theorem}

A prime-sumset-free subset $A$ of $\{ 1,\, 2,\,
\ldots ,\,  n\} $ is called {\it an extremal prime-sumset-free
subset} of $\{ 1,\, 2,\, \ldots ,\,  n\} $ if $A\cup \{ a\} $ is
not a prime-sumset-free subset for any $a\in \{ 1,\, 2,\, \ldots
,\, n\}\setminus A $.   Let $PF_k(n)$ $(k=1,\, 2,\, \ldots )$ be
the sequence of cardinalities of all extremal prime-sumset-free
subsets of $\{ 1,\, 2,\, \ldots ,\,  n\} $ with
$PF_1(n)>PF_2(n)>\ldots $. By the theorem we have
$PF_1(n)=U_n=\lfloor(n+1)/2\rfloor$. We pose the following open
question:

\begin{question}  What are the values of $PF_k(n)$? In
particular,\, What is the value of $PF_2(n)$?\end{question}

\begin{question}  Determine all extremal prime-sumset-free
subsets $A$ with $|A|=PF_2(n)$.\end{question}


\section{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\ge 2)$. By the Bertrand's postulate
(see \cite{Hardy}) there exists a prime $p$ with $k<p<2k$. Assume
that $A\subseteq \{ 1,\, 2,\, \ldots ,\,  n\} $ is
prime-sumset-free. For $p-k\le a\le k$ we have $|\{ a,\,  p-a\}
\cap A|\le 1$. So
$$|A\cap [p-k,\,  k]|\le \frac 12(2k-p+1).$$
By the induction hypothesis we have
$$|A\cap [1,\,  p-k-1]|\le \frac 12(p-k).$$
Hence
$$|A\cap [1,\,  k]|\le \frac 12(2k-p+1)+\frac 12(p-k)=\frac
12(k+1).$$ This implies that $U_k\le [(k+1)/2]$. By the remark
before the theorem we have $U_k\ge \lfloor(k+1)/2\rfloor$. So
$U_k=\lfloor(k+1)/2\rfloor$. This completes the proof of the first
part.



To prove the second part of Theorem \ref{thm1}, we need a lemma.

 \begin{lemma}\label{lem1}  For any real number $x\ge 8$ we have
$$\pi (\sqrt 2 x)-\pi (x)\ge 1.$$ In particular,\,  if $m,\, n$ are
positive integers with $m>\sqrt 2 n$ and $n\ge 8$,\,  then there
exists at least one prime $p$ with $m>p>n$.\end{lemma}

 \begin{proof} By direct calculation we know that Lemma \ref{lem1} is true
for $8\le x\le 25$. If $x>25$, by Nagura \cite{Nagura} (see also
\cite[Lemma 4]{Chen} ) we have
$$\pi (\sqrt 2 x)-\pi (x)\ge \pi \bigl(\frac 65 x\bigr)-\pi (x)\ge 1.$$
This completes the proof of Lemma \ref{lem1}.\end{proof}

 Now we return to prove the second part of Theorem \ref{thm1}.

For $n\le 8$ we can verify Theorem \ref{thm1} directly. Now we
assume that $k>8$ and Theorem \ref{thm1} is true for all $n<k$.
Let $A\subseteq \{ 1,\, 2,\, \ldots ,\,  k\} $ be a
prime-sumset-free set with $|A|=U_k$. Let $q_k$ be the largest
prime $q$ with $q\le 2k$. By Lemma \ref{lem1} we have $q_k>\sqrt 2
k$. If $8<k\le 20$,\,  by direct verification we have $q_k-k\ge
8$. If $k\ge 21$,\,  then $q_k-k>(\sqrt 2-1)k\ge 8$. For any
$q_k-k\le a \le k$ we have $|A\cap \{ a,\, \,\, q_k-a\} |\le 1$.
Hence
$$|A\cap [q_k-k,\, \,\,  k]|\le \frac 12 (2k-q_k+1).$$
Since $A\cap [1,\, \,\,  q_k-k-1]$ is a prime-sumset-free set,\,
we have
$$|A\cap [1,\, \,\,  q_k-k-1]|\le U_{q_k-k-1}=\bigl\lfloor \frac 12(q_k-k)\bigr\rfloor .$$
By the assumption $|A|=U_k=\lfloor(k+1)/2\rfloor$  we have
\begin{eqnarray*}\bigl\lfloor\frac 12(k+1)\bigr\rfloor=|A|&=&|A\cap [1,\, \,\,
q_k-k-1]| +|A\cap [q_k-k,\, \,\,  k]|\\
&\le & \bigl\lfloor\frac 12(q_k-k)\bigr\rfloor +\frac
12(2k-q_k+1)\\
&=&\bigl\lfloor\frac 12(k+1)\bigr\rfloor.\end{eqnarray*}
 So
$$|A\cap [1,\, \,\,  q_k-k-1]|= \bigl\lfloor\frac 12(q_k-k)\bigr\rfloor =U_{q_k-k-1} .$$
If $2|k$,\,  then by the induction hypothesis we have
$$A\cap [1,\, \,\,  q_k-k-1]=\{ 1,\,  3,\,  \ldots ,\,
q_k-k-2\} \mbox{ or } \{ 2,\,  4,\,  \ldots ,\,  q_k-k-1\} .$$ If
$2\not| k$,\,  then by the induction hypothesis we have
$$A\cap [1,\, \,\,  q_k-k-1]=\{ 1,\,  3,\,  \ldots ,\,  q_k-k-1\} .$$



 {\bf Case 1:} $2|k$ and $A\cap [1,\, \,\,  q_k-k-1]=\{ 1,\,  3,\,  \ldots
,\,  q_k-k-2\} $.

Let $2m\in [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\ge 8$ and Lemma \ref{lem1} there
exists at least one prime $p$ with $2m<p<2m+q_k-k$. So $1\le
p-2m\le q_k-k-2$. Thus $p-2m\in A\cap [1,\, \,\,  q_k-k-1]$. Hence
$2m\notin A$. So
$$A\subseteq \{ 1,\,  3,\,  5,\,  \ldots ,\,  k-1\} .$$
Since $|A|=U_k=\frac 12 k$,\,  we have $A=\{ 1,\,  3,\,  5,\,
\ldots ,\,  k-1\} $.



{\bf Case 2:} $2|k$ and $A\cap [1,\, \,\,  q_k-k-1]=\{ 2,\,  4,\,
\ldots ,\,  q_k-k-1\} .$

Let $2m+1\in [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\ge 8$ and Lemma \ref{lem1} there
exists at least one prime $p$ with $2m+1<p<2m+1+q_k-k$. So $1\le
p-2m-1\le q_k-k-1$. Thus $p-2m-1\in A\cap [1,\, \,\,  q_k-k-1]$.
Hence $2m+1\notin A$. So
$$A\subseteq \{ 2,\,  4,\,  \ldots ,\,  k\} .$$  Since $|A|=U_k=\frac 12 k$,\,
we have $A=\{ 2,\,  4,\,  \ldots ,\,  k\}  $.

{\bf Case 3:} $2\not| k$. Then
$$A\cap [1,\, \,\,  q_k-k-1]=\{ 1,\,  3,\,  \ldots ,\,  q_k-k-1\} .$$

Let $2m\in [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\ge 8$ and Lemma \ref{lem1} there
exists at least one prime $p$ with $2m<p<2m+q_k-k$. So $1\le
p-2m\le q_k-k-1$. Thus $p-2m\in A\cap [1,\, \,\,  q_k-k-1]$. Hence
$2m\notin A$. So
$$A\subseteq \{ 1,\,  3,\,  5,\,  \ldots ,\,  k-1\} .$$
Since $|A|=U_k=\frac 12 (k-1)$,\,  we have $A=\{ 1,\,  3,\,  5,\,
\ldots ,\,  k-1\} $.

This completes the proof.

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


\begin{thebibliography}{10}

\bibitem{Hardy} G. H. Hardy and E. M. Wright, {\it An Introduction to the Theory
of Numbers},  Fifth Ed.,  Oxford University Press, 1979.

\bibitem{Nagura} J. Nagura, On the interval containing at least
one prime number, {\it Proc. Japan Acad.} {\bf 28}(1952),
177--181.

\bibitem{Chen} Y. -G. Chen, The Analogue of Erd\H os-Tur\'an
Conjecture in ${\bf Z}_m$, {\it J. Number Theory} {\bf 128}
(2008), 2573--2581.
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11A41; Secondary 11B75, 05D05.

\noindent \emph{Keywords: } primes, sumsets, distribution of primes.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 16 2008;
revised version received December 13 2008.
Published in {\it Journal of Integer Sequences},
December 13 2008.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                


.