\documentclass[12pt]{article}
\textwidth=6.25in
\textheight=9.0in
\topmargin=-10pt
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9
\def\mathbbm{\mathbb}

%\usepackage{bbm}
\usepackage{latexsym}
\usepackage{amssymb,amsmath}

\begin{document}
\vspace*{-60pt}
\centerline{\smalltt INTEGERS:
 \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 4
(2004), \#A13}
\vskip 50pt
\begin{center}
{\bf A NOTE ON P-SETS}
\vskip 20pt
{\bf Stephan Baier}\\
{\smallit 
Center of Mathematics, 
Department of Pure Mathematics and Mathematical Statistics, 
University of Cambridge,
Wilberforce Road, Cambridge CB3 0WB, United Kingdom}\\
{\tt S.Baier@dpmms.cam.ac.uk}
\end{center}
\vskip 30pt
\centerline{\smallit Received: 10/3/03, Accepted: 9/26/04, Published:
10/8/04}
\vskip 30pt

\centerline{\bf Abstract} 

\noindent
A $\cal{P}$-set is a set $\mathcal{S}$ of positive integers such that no element of $\mathcal{S}$
divides the sum of any two (not necessarily being different) 
larger elements.  Erd\"os and
S\'ark\"ozy [2] conjectured that there exists a constant $c>0$ such that
for every $\mathcal{P}$-set $\mathcal{S}$ we have 
$\vert\{s\in \mathcal{S} \ \! : \ \! s\le N\} \vert<N^{1-c}$ for
infinitely many integers $N$. 
For $\cal{P}$-sets ${\mathcal{S}}$ consisting of pairwise coprime
integers this conjecture has been  
proved by T. Schoen [6] who
showed that in this case we have
$\vert\{s\in \mathcal{S} \ \! : \ \! s\le N\} \vert<2N^{2/3}$ 
for infinitely many
integers $N$. In the present note we prove that the term $2N^{2/3}$ in
Schoen$^{\prime}$s estimate can be replaced by
$(3+\varepsilon)N^{2/3}/\log N$. Our method  uses the arithmetic
form of the large sieve as well as mean value estimates for
multiplicative functions. (Mathematics Subject Classification
(2000): 11B05, 10H25)

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL 
NUMBER THEORY \smalltt x (200x), \#Axx\hfill}
 
\thispagestyle{empty}
\baselineskip=15pt
\vskip 30pt
\section*{\normalsize 1. Introduction} 
{\bf Notation:} Whenever $S$ is a discrete set of positive real
numbers, we define the corresponding counting function 
$\mathcal{A}_S:\mathbbm{R}^+\rightarrow \mathbbm{N}\cup \{0\}$ by 
\begin{displaymath}
\mathcal{A}_S(N):=\vert\{s\in S \ \! : \ \! s\le N\} \vert.
\end{displaymath}

A $\cal{P}$-set is a set $\mathcal{S}$ of positive integers such that no element of $\mathcal{S}$
divides the sum of any two (not necessarily being different) 
larger elements. In [2] Erd\"os and
S\'ark\"ozy studied the behaviour of the corresponding counting function
$\mathcal{A}_{\mathcal{S}}(N)$.
They showed that $\mathcal{A}_{\mathcal{S}}(N)=o(N)$ as 
$N\rightarrow\infty$ and pointed out
that this estimate is in a certain sense optimal.
Furthermore, they conjectured
that there exists a constant $c>0$ such that 
$\mathcal{A}_{\mathcal{S}}(N)<N^{1-c}$ for
infinitely many integers $N$. 
For $\cal{P}$-sets ${\mathcal{S}}$ consisting of pairwise coprime
integers this conjecture has been  
proved by T. Schoen [6] who
showed that in this case we have $\mathcal{A}_{\mathcal{S}}(N)<2N^{2/3}$ 
for infinitely many
integers $N$. His
method depends on the analytic form of the large sieve. 
Moreover, by giving
a counterexample, Schoen pointed out that $c$ cannot be choosen greater
than $1/2$.

In the present note we improve Schoen$^{\prime}$s first-mentioned
result. Throughout the following, we suppose that 
${\mathcal{S}}$ is a given
$\cal{P}$-set consisting of pairwise coprime integers.

\noindent
{\bf Theorem:} \begin{it} Let any $\varepsilon>0$ be given. Then  
we have 
\begin{displaymath}
\mathcal{A}_{\mathcal{S}}(N)<(3+\varepsilon)N^{2/3}(\log N)^{-1}
\end{displaymath}
for infinitely many integers $N$.\end{it}
\vskip 30pt 
\section*{\normalsize 2. 
General estimation of $\mathcal{A}_{\mathcal{S}}(N)$} 
Without
loss of generality, we suppose that $1\not\in \mathcal{S}$
(otherwise, $\mathcal{S}$ could not contain any integer greater than
1). 

Our starting point for
estimating $\mathcal{A}_{\mathcal{S}}(N)$ 
is the following simple observation: 
If $q,r\in \mathcal{S}$ and $q<r$, then we have
$s\not\equiv -r$ mod $q$ for all $s\in\mathcal{S}$ with $s>q$  
(this follows directly from the definition of ${\mathcal{S}}$ 
to be a $\cal{P}$-set). From this, we conclude that for every $q\in
{\mathcal{S}}$ there exist at least $1+[q/2]$ residue classes 
$R_1(q)$,$R_2(q)$,...,$R_{\omega(q)}(q)$ mod $q$ 
which do not contain any element of $\mathcal{S}$
greater than $q$ (particularly, the residue class $0$ mod $q$ will be
one of them and, if
 $q$ is even, $q/2$ mod $q$ will be another of them). 

This leads us to defining the following sieve for
given real $z,N$ with $1\le z\le N$ (however, here
we use a set of pairwise coprime integers instead of a set of primes):
\begin{eqnarray*}
\mathfrak{A}&:=&\{n\in \mathbbm{N} \ \! : \ \! z<n\le N\},\\
\mathfrak{P}&:=&\{q\in {\mathcal{S}}\ \! : \ \! q\le z\},\\
\Omega(q)&:=&\bigcup\limits_{i=1}^{\omega(q)} R_i(q)\ \ \ \ 
(q\in \mathfrak{P}),\\
\mathfrak{M}&:=&\{m\in \mathfrak{A} \ \! : \ \! m\not\in \Omega(q) 
\mbox{ for all }
q\in \mathfrak{P}\}. \
\end{eqnarray*}
Then, by our above observations, we have 
\begin{equation}
\mathcal{A}_{\mathcal{S}}\left(N\right)\le \vert \mathfrak{M} \vert +z.
\end{equation}
To obtain an upper bound for 
$\vert \mathfrak{M}\vert$, we use the arithmetic form of the large
sieve established by H.L. Montgomery (see [1], [5]).

\noindent
{\bf Lemma 1:} \begin{it} On the above sieve hypotheses, we have 
\begin{displaymath}
\vert \mathfrak{M} \vert \le (N+Q^2)\left(\sum\limits_{k\le Q} g(k)\right)^{-1}
\end{displaymath}
for every $Q\ge 1$, where $g(k)$ is defined by
\begin{displaymath}
g(k):=\left\{\begin{array}{llll} 1& \mbox{ if } k=1,\medskip\\ 
\prod\limits_{i=1}^r 
\frac{\omega(q_i)}{q_i-\omega(q_i)}& \mbox{ if there are distinct }
q_1,...,q_r\in \mathfrak{P} \mbox{ such that } k=q_1\cdots q_r,\medskip\\ 
0& \mbox{ otherwise.}
 \end{array}\right.
\end{displaymath}\end{it}

We note that $g$ is well-defined since the set $\mathfrak{P}$ consists of
pairwise coprime integers.
 
The original version of Montgomery$^{\prime}$s sieve employs, 
as usual in context
of sieve theory, 
a set of prime numbers $\mathfrak{P}$ instead of, more generally, a set of
pairwise coprime integers, but our more general version of this sieve 
can be proved in
exactly the same manner as the original one.

As already pointed out, in our application we have $\omega(q)\ge
1+[q/2]$ if $q\in \mathfrak{P}$. This implies $g(k)\ge 1$ whenever
$g(k)>0$. Hence, choosing $z:=Q$ and $N:=Q^2$, we obtain the
following result from (1) and Lemma 1.

\noindent
{\bf Lemma 2:} \begin{it} For every real $Q\ge 1$ we have
\begin{displaymath}
\mathcal{A}_{\mathcal{S}}\left(Q^2\right)\le \frac{2Q^2}{\vert 
\mathcal{A}_{\mathcal{K}}(Q)\vert} + Q,
\end{displaymath}
where the set $\mathcal{K}$ is defined to be the union of $\{1\}$ and 
the set of all products of
distinct elements of $\mathcal{S}$, {\it i.e.}
\begin{displaymath}
\mathcal{K}:=\{1\}\cup \left\{q_1\cdots q_r\ \! : \ \! r\in
  \mathbbm{N},\ q_1,...,q_r \mbox{ are
  distinct elements of } \mathcal{S}\right\},
\end{displaymath}
and $\mathcal{A}_{\mathcal{K}}(Q)$ denotes the counting function
corresponding to $\mathcal{K}$. 
\end{it}
\vskip 30pt 
\section*{\normalsize 3. Proof of Theorem.} 
The key ingredient
for our improvement of Schoen$^{\prime}$s result
is the following

\noindent
{\bf Lemma 3}: \begin{it} Let $\alpha$, $\beta$ and $N_0$ be real numbers with 
$\alpha>0$, $1/2<\beta<1$ and $N_0\ge 2$. Suppose that  
\begin{equation}
\mathcal{A}_{\mathcal{S}}(N)\ge \alpha N^{\beta}(\log N)^{-1}
\end{equation}
holds for every integer $N\ge N_0$. Define the set $\mathcal{K}$ 
as in Lemma $2$.
Then for every $\varepsilon_0>0$ there exist real numbers 
$x_0(\varepsilon_0)\ge 2$ and $C(\varepsilon_0)>0$ such that
\begin{displaymath}
\mathcal{A}_{\mathcal{K}}(x)\ge 
C(\varepsilon_0)x^{\beta}(\log x)^{\alpha\beta-1-\varepsilon_0}
\end{displaymath}
for every real $x\ge x_0(\varepsilon_0)$. \end{it}

\noindent
{\it Proof.} The condition (2) implies that there is a subset
$\mathcal{T}$ of $\mathcal{S}$ such that 
  \begin{equation}
  \mathcal{A}_{\mathcal{T}}(x)\sim \alpha x^{\beta}(\log x)^{-1}
  \end{equation}
as $x\rightarrow\infty$. Let $\mathcal{L}$ be the union of $\{1\}$ and
the set of all elements of
$\mathcal{K}$ which can be represented as a product of elements of 
$\mathcal{T}$, {\it i.e.}
  \begin{displaymath}
  \mathcal{L}:=\{1\}\cup \left\{q_1\cdots q_r\ \! : \ \! r\in
  \mathbbm{N},\ q_1,...,q_r \mbox{ are
  distinct elements of } \mathcal{T}\right\}.
  \end{displaymath} 
We employ the following result in [4], page 202 to obtain a lower bound for 
$\mathcal{A}_{\mathcal{L}}(x)$:

\begin{it} Let $f$ be a non-negative multiplicative function defined
on the usual set of positive integers. Suppose that
  \begin{displaymath}
  \sum\limits_{p\le x} f(p)\ \sim\ \alpha\cdot \frac{x^{\beta}}{\log x}\
  \ \ \ \ (\alpha>0,\ \beta>0)
  \end{displaymath}
as $x\rightarrow\infty$,
where the sum on the left side runs over the prime numbers $p\le x$.
Suppose further that for a certain $\delta>0$ we have
  \begin{displaymath}
  \sum\limits_{p,\ \! k\ge 2}\ \frac{f(p^k)}{p^{k\beta(1-\delta)}}\ <\ \infty.
  \end{displaymath}
Then,
  \begin{displaymath}
  \sum\limits_{n\le x} f(n) \ \sim\ \left(\sum\limits_{p\le x} f(p)
  \right) \cdot \frac{e^{-\alpha\beta\gamma}}{\Gamma(1+\alpha\beta)}
  \cdot \prod\limits_{p\le x}
  \left(1+\frac{f(p)}{p^{\beta}}+\frac{f(p^2)}{p^{2\beta}}+...\right)
  \end{displaymath}
as $x\rightarrow\infty$, where $\gamma$ denotes the Euler constant.\end{it}

We note that this result keeps its validity if the set of prime
numbers is replaced by a set $\mathfrak{Q}$
of pairwise coprime integers and the function
$f$ is, more generally, defined to be a multiplicative function on
the {\bf arithmetical semigroup} $\mathfrak{G}$ 
generated by the set $\mathfrak{Q}$ 
(see [3]; the arithmetical semigroup $\mathfrak{G}$ may be understood as
``generalized integers'', the set $\mathfrak{Q}$ as 
``generalized prime numbers''). 

In our case, we set $\mathfrak{Q}:=\mathcal{T}$. Hence, 
the arithmetical semigroup $\mathfrak{G}$ is the union
of $\{1\}$ and the set of all 
products of (not necessarily being different) elements of
$\mathcal{T}$. For $f$ we take the 
characteristic
function of the set $\mathcal{L}$ (this set $\mathcal{L}$ may be
understood as the set of ``squarefree'' elements of our arithmetical
semigroup $\mathfrak{G}$, and
the function $f$ corresponds to the function $\mu^2$ on the set
of usual positive integers, where $\mu$ is the M\"obius function), {\it i.e.} we set
\begin{displaymath}
f(n):=\left\{ \begin{array}{llll} 1& \mbox{ if } n\in \mathcal{L},\\
  \\ 0& \mbox{ if } n\in \mathfrak{G}\setminus\mathcal{L}.
\end{array} \right.
\end{displaymath}
Now, from (3) and our generalized version of the above-mentioned
result on multiplicative functions in [4, page 202], we derive
  \begin{equation} 
  \mathcal{A}_{\mathcal{L}}(x)\sim \mathcal{A}_{\mathcal{T}}(x) \cdot
  \frac{e^{-\alpha \beta \gamma}}{\Gamma(1+\alpha \beta)} \cdot
  \hspace{-0.4cm}
  \prod\limits_{\scriptsize\begin{array}{cccc} &q\leq x,& \\ 
  &q\in \mathcal{T}& 
  \end{array}} \hspace{-0.4cm} \left(1+q^{-\beta}\right)
  \end{equation}
as $x\rightarrow\infty$. Using
the Taylor series expansion of the logarithm in the neighbourhood of
1, the asymptotic estimate (3) and the condition $1/2<\beta$ in Lemma 3,
 we deduce that
  \begin{equation}
  \log \hspace{-0.4cm}
  \prod\limits_{\scriptsize\begin{array}{cccc} &q\leq x,& \\ 
  &q\in \mathcal{T}& 
  \end{array}} \hspace{-0.4cm} \left(1+q^{-\beta}\right) =
  \hspace{-0.4cm}
  \sum\limits_{\scriptsize\begin{array}{cccc} &q\leq x,& \\ 
  &q\in \mathcal{T}& 
  \end{array}} \hspace{-0.4cm} \left(q^{-\beta}+O(q^{-2\beta})\right)
  =\hspace{-0.4cm}
  \sum\limits_{\scriptsize\begin{array}{cccc} &q\leq x,& \\ 
  &q\in \mathcal{T}& 
  \end{array}} \hspace{-0.4cm} q^{-\beta}\ +\ O(1).
  \end{equation}
Using partial summation, we get
  \begin{equation}
  \hspace{-0.4cm}
  \sum\limits_{\scriptsize\begin{array}{cccc} &q\leq x,& \\ 
  &q\in \mathcal{T}& 
  \end{array}} \hspace{-0.4cm} q^{-\beta} \ =\
  x^{-\beta}\mathcal{A}_{\mathcal{T}}(x)\ +\ 
  \beta\int\limits_2^{x} y^{-(\beta+1)}\mathcal{A}_{\mathcal{T}}(y)\
  {\rm d}y \ +\ O(1).  
  \end{equation}
>From (3), we obtain
  \begin{equation}
  \int\limits_2^{x} y^{-(\beta+1)}\mathcal{A}_{\mathcal{T}}(y)\ {\rm
  d}y \ \sim\ \alpha\log\log x
  \end{equation}
as $x\rightarrow\infty$. Let $\varepsilon_0>0$ be given.
Then, combining (3), (4), (5), (6) and (7), we get
  \begin{displaymath}
  \mathcal{A}_{\mathcal{L}}(x)\ge 
  Cx^{\beta}(\log x)^{\alpha\beta-1-\varepsilon_0}
  \end{displaymath}
for every sufficiently large real $x$, 
where $C$ is a suitable positive constant depending on
$\varepsilon_0$. 
This implies the result of
Lemma 3 since $\mathcal{L}$ is a subset of $\mathcal{K}$. \hfill $\Box$

We now turn to the final 

\noindent
{\it Proof of Theorem}. 
We assume that there exists a $N_0\ge 2$ such that 
\begin{equation}
\mathcal{A}_{\mathcal{S}}(N)\ge  (3+\varepsilon)N^{2/3}(\log N)^{-1}
\end{equation}
holds for all integers $N\ge N_0$. 
>From this assumption and Lemmas 2 and 3
(choose $\alpha:=3+\varepsilon$, $\beta:=2/3$ and 
$\varepsilon_0:=\varepsilon/3$)
it follows that there exist real numbers $Q_0\ge 2$ and $D>0$ such that
\begin{equation}
\mathcal{A}_{\mathcal{S}}\left(Q^2\right)\le 
DQ^{4/3}\left(\log Q\right)^{-1-\varepsilon/3}+Q
\end{equation}
for every real $Q\ge Q_0$. But (9) contradicts (8) if $N=Q^2$ and 
$Q$ is sufficiently large. Therewith, the proof of Theorem is
completed. \hfill $\Box$
\vskip 30pt

\section*{\normalsize Acknowledgement} 
This paper was written when the author held a
Postdoctoral Fellowship at the Harish-Chandra Research Institute at
Allahabad (India). He wishes to thank this institute for financial
support and for providing very good working conditions. 
Furthermore, the author would like to thank Prof. Lutz Lucht (University of
Clausthal, Germany) for some valuable comments on multiplicative functions.
\vskip 30pt 

\section*{\normalsize References}
\noindent 
[1] B\"udern, J., {\it Einf\"uhrung in die analytische
  Zahlentheorie}, Springer-Verlag, Berlin 1995.

\noindent
[2] Erd\"os, P., S\'ark\"ozy, A., {\it On the divisibility of
  sequences of integers}, Proc. London Math. Soc. (3) 21 (1970),
  97-101.

\noindent
[3] Knopfmacher, J., {\it Abstract Analytic Number Theory
(2nd. ed. Dover)}, New York 1990.

\noindent
[4] Lucht, L., {\it Asymptotische Eigenschaften
  multiplikativer Funktionen}, J.
Reine Angew. Math. 266 (1974), 200--220.
 
\noindent
[5] Montgomery, H.L., {\it Topics in multiplicative number
  theory}, Springer-Verlag, Berlin 1971.

\noindent
[6] Schoen, T., {\it On a problem of Erd\"os and Sark\"ozy,}
  J. Comb. Theory Ser. A 94 (2001), no. 1, 191-195.
\end{document}