\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 
Infinite Sets of Integers Whose Distinct \\
\vskip .15in
Elements Do Not Sum to a Power
}
\vskip 1cm
\large
Art\= uras Dubickas and Paulius \v Sarka\\
Department of Mathematics and Informatics\\ 
Vilnius University\\
Naugarduko 24 \\
Vilnius LT-03225\\ 
Lithuania \\
\href{mailto:arturas.dubickas@maf.vu.lt}{\tt arturas.dubickas@maf.vu.lt} \\
\href{mailto:paulius.sarka@mif.vu.lt}{\tt paulius.sarka@mif.vu.lt}
%\address{Institute of Mathematics and Informatics\\
%Akademijos 4, Vilnius LT-08663\\ Lithuania}
\end{center}

\def\leq{\leqslant}
\def\geq{\geqslant}
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\C{\mathbb C}
\def\F{\mathbb F}
\def\N{\mathbb N}
\def\R{\mathbb R}
\def\Q{\mathbb Q}
\def\Z{\mathbb Z}
\newcommand{\eps}{\varepsilon}
\def\ro{\varrho}
\newcommand{\Qbar}{{\overline{\Q}}}

\vskip .2 in
\begin{abstract}
We first prove two results which both imply that for any sequence
$B$ of asymptotic density zero there exists an infinite sequence
$A$ such that the sum of any number of distinct elements of $A$
does not belong to $B.$ Then, for any $\eps>0,$ we construct an
infinite sequence of positive integers $A=\{a_1<a_2<a_3<\dots\}$
satisfying $a_n < K(\eps) (1+\eps)^n$ for each $n \in \N$ such
that no sum of some distinct elements of $A$ is a perfect square.
Finally, given any finite set $U \subset \N,$ we construct a
sequence $A$ of the same growth, namely, $a_n < K(\eps,U)
(1+\eps)^n$  for every $n \in \N$ such that no sum of its distinct
elements is equal to $uv^s$ with $u \in U,$ $v \in \N$ and $s \geq
2.$
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 


%\newtheorem{theorem}{Theorem}




\bigskip

\section{Introduction}

Let $B=\{b_1< b_2< b_3< \dots\}$ be an infinite sequence of
positive integers. In this note we are interested in the following
two questions.
\begin{itemize}
\item For which $B$ there exists an infinite sequence of positive
integers $A=\{a_1< a_2< a_3<\dots\}$ such that
$a_{i_1}+\dots+a_{i_m} \notin B$ for every $m \in \N$ and any
distinct elements $a_{i_1}, \dots, a_{i_m} \in A$?

\item In the case when the answer is `yes', how dense the sequence
$A$ can be?
\end{itemize}

In his paper \cite{luc}, F.~Luca considered the case when $B$ is
the set of all perfect squares $\{1,4,9,16,25,36,\dots\}$ and of
all perfect powers $\{1,4,8,9,16,25, 27,32,36,\dots\}.$ He showed
that in both cases the answer to the first question is `yes'. In
particular, it was observed in \cite{luc} that the sum of any
distinct Fermat numbers $2^{2^{n}}+1,$ $n=1,2,\dots,$ is not a
perfect square. Moreover, it was proved that the sum of any
distinct numbers of the form $a^{p_1p_2\dots p_n}+1,$ $n=n_0,
n_0+1, \dots,$ where $a \geq 2$ is an integer, $p_k$ is the $k$th
prime number and $n_0=n_0(a)$ is an effectively computable
constant, cannot be a perfect power.

\bigskip

\section{Sets with asymptotic density zero}

We begin with the following observation (see also \cite{cil})
which settles the first of the two problems stated above for every
set $B$ satisfying $\limsup_{n \to \infty} (b_{n+1}-b_n)=\infty.$

\begin{theorem}\label{dens}
Let $m \in \N$ and let $B=\{b_1<b_2<b_3<\dots\}$ be an infinite
sequence of positive integers satisfying $\limsup_{n \to \infty}
(b_{n+1}-mb_n)=\infty.$ Then there exists an infinite sequence of
positive integers $A$ such that every sum over some elements of
$A,$ at most $m$ of which are equal, is not in $B.$
\end{theorem}

\begin{proof}
Take the smallest positive integer $\ell$ such that
$b_{\ell+1}-b_{\ell} \geq 2,$ and set $a_1:=b_{\ell}+1.$ Then $a_1
\notin B.$ Suppose we already have a finite set
$\{a_1<a_2<\dots<a_k\}$ such that all possible $(m+1)^k-1$ nonzero
sums $\delta_1 a_1+\dots+\delta_k a_k,$ where
$\delta_1,\dots,\delta_k \in \{0,1,\dots,m\},$
 do not belong to $B.$ Put $a_{k+1}:=b_{l}+1,$ where $l$ is the
smallest positive integer for which $b_{l+1}-mb_l \geq
1+m+m(a_1+\dots+a_k)$ and $b_{l} \geq a_k.$ Such an $l$ exists,
because $\limsup_{n \to \infty} (b_{n+1}-mb_n)=\infty.$

Clearly, $b_{l} \geq a_k$ implies that $a_{k+1}>a_k.$ In order to
complete the proof of the theorem (by induction) it suffices to
show that no sum of the form $\delta_1 a_1+\dots +\delta_k a_k +
\delta_{k+1} a_{k+1},$ where $\delta_1, \dots, \delta_{k+1} \in
\{0,1,\dots,m\},$ lies in $B.$ If $\delta_{k+1}=0,$ this follows
by our assumption, so suppose that $\delta_{k+1}\geq 1.$ Then
$\delta_1a_1+\dots+\delta_ka_k+\delta_{k+1} a_{k+1}$ is greater
than $a_{k+1}-1=b_l$ and smaller than
$$1+m(a_1+\dots+a_k+a_{k+1})\leq b_{l+1}-mb_l-m+ma_{k+1}
= b_{l+1}-mb_l-m+m(b_l+1)=b_{l+1},$$ so it is not in $B,$ as
claimed. $\square$
\end{proof}

\medskip

Recall that the {\it upper asymptotic density} $\overline{d}(B)$
of the sequence $B$ is defined as
$$\overline{d}(B)=\limsup_{N \to \infty}\frac{\#\{n \in \N : b_n \leq N\}}
{N}$$ (see, e.g., 1.2 in \cite{stpo}). Similarly, the {\it lower
asymptotic density} $\underline{d}(B)$ is defined as
$\underline{d}(B)=\liminf_{N \to \infty} N^{-1}\#\{n \in \N : b_n
\leq N\}.$ If $\overline{d}(B)=\underline{d}(B),$ then the common
value $d(B)=\overline{d}(B)=\underline{d}(B)$ is said to be the
{\it asymptotic density} of $B.$

Evidently, if $B$ has asymptotic density zero then, for any
positive integer $k,$ there are infinitely many positive integers
$N$ such that the numbers $N+1, N+2, \dots, N+k$ do not lie in
$B.$ This implies that the condition $\limsup_{n \to \infty}
(b_{n+1}-b_n)=\infty$ holds. Hence, by Theorem~\ref{dens} with
$m=1,$ for any sequence $B$ of asymptotic density zero there
exists an infinite sequence $A$ such that the sum of any number of
distinct elements of $A$ is not in $B.$ It is well-known that the
sequence of perfect powers has asymptotic density zero, so such an
$A$ as claimed exists for $B=\{1,4,8,9,16,25,27,32,36,\dots\}.$

For $m \geq 2,$ it can very often happen that $b_{n+1}<mb_n$ for
every $n \in\N.$ For such a set $B$ Theorem~\ref{dens} is not
applicable. However, its conclusion is true for any set $B$ of
asymptotic density zero.

\begin{theorem}\label{dens1}
Let $m \in \N$ and let $B$ be an infinite sequence of positive
integers of asymptotic density zero. Then there exists an infinite
sequence of positive integers $A$ such that every sum over some
elements of $A,$ at most $m$ of which are equal, is not in $B.$
\end{theorem}

\begin{proof}
Once again, take the smallest positive integer $\ell$
such that $b_{\ell+1}-b_{\ell} \geq 2,$ and put $a_1:=b_{\ell}+1.$
Then $a_1 \notin B.$ Suppose we already have a finite set
$\{a_1<a_2<\dots<a_k\}$ such that all possible $(m+1)^k-1$ nonzero
sums $\delta_1 a_1+\dots+\delta_k a_k,$ where
$\delta_1,\dots,\delta_k \in \{0,1,\dots,m\},$ do not belong to
$B.$ It suffices to prove that there exists an integer $a_{k+1}$
greater than $a_k$ such that, for every $i \in \{1,\dots,m\},$ the
sum $ia_{k+1}+\delta_ka_k+\dots+\delta_1a_1,$ where
$\delta_1,\dots,\delta_k \in \{0,1,\dots,m\},$ is not in $B.$

Suppose that $B=\{b_1<b_2<b_3<\dots\}.$ For any $h \in \N,$ the
set $\{hb_1<hb_2<hb_3<\dots\}$ will be denoted by $hB.$ Put
$B_i:=\frac{m!}{i} B$ for $i=1,2,\dots,m.$ Since $d(B_i)=0$ for
each $i=1,\dots,m,$ we have $d(B_1\cup \dots \cup B_m)=0.$ Thus,
for any $v>m!(mS+1),$ where $S:=a_1+\dots+a_k,$ there is an
integer $u>m! a_k$ such that the interval $[u,u+v]$ is free of the
elements of the set $B_1 \cup \dots \cup B_m.$

Put $a_{k+1}:=\lfloor u/m! \rfloor +1.$ Clearly, $a_{k+1}>a_k.$ Furthermore, for
any $i \in \{1,\dots,m\},$ no element of $B_i$ lies in $[u,u+v].$
Thus there is a nonnegative integer $j=j(i)$ such that $m!b_j/i <
u$ and $m!b_{j+1}/i>u+v.$ (Here, for convenience of notation, we
assume that $b_0=0$.) Hence $ia_{k+1}
> iu/m!>b_j$ and $$ia_{k+1}+mS<ia_{k+1}+imS \leq
i(u/m!+1+mS)<i(u+v)/m!<b_{j+1}.$$ In particular, these
inequalities imply that, for each $i \in \{1,\dots,m\},$ the sum
$ia_{k+1}+\delta_ka_k+\dots+\delta_1a_1,$ where
$\delta_1,\dots,\delta_k \in \{0,1,\dots,m\},$ is between
$b_{j(i)}+1$ and $b_{j(i)+1}-1,$ hence it is not in $B.$ This
completes the proof of the theorem. $\square$
\end{proof}

\medskip

Several examples illustrating Theorem~2 will be given in
Section~5. In particular, for any $\eps>0,$ there is a set $B
\subset \N$ with asymptotic density $d(B)<\eps$ such that for any
infinite set $A \subseteq \N$ some of its distinct elements sum to
an element lying in $B.$ On the other hand, there are sets $B
\subseteq \N$ with asymptotic density $1$ for which there exists
an infinite set $A$ whose distinct elements do not sum to an
element lying in $B$.

\bigskip

\section{Infinite sets whose elements do not sum to a square}

The second question concerning the `densiest' sequence $A$ for a
fixed $B$ seems to be much more subtle. It seems likely that this
question is very difficult already for the above mentioned
sequence of perfect squares $\{1,4,9,16,25,36,\dots\}.$ The
example of Fermat numbers $2^{2^{n}}+1,$ $n=1,2,\dots,$ given
above is clearly not satisfactory, because this sequence grows
very rapidly.

In this sense, much better is the sequence $2^{2n-1},$
$n=1,2,\dots.$ The sum of its distinct elements
$$2^{2n_1-1}+\dots+2^{2n_l-1}=2^{2n_1-1}(1+4^{n_2-n_1}+\dots+4^{n_l-n_1}),$$
where $1\leq n_1<\dots<n_l,$ is not a perfect square, because it
is divisible by $2^{2n_1-1},$ but not divisible by $2^{2n_1}.$

Smaller, but still of exponential growth, is the sequence $2\cdot
3^n,$ $n=0,1,2,\dots.$ No sum of its distinct elements is a
perfect square, because
$$2(3^{n_1}+\dots+3^{n_l})=2\cdot 3^{n_1} (1+3^{n_2-n_1}+\dots+3^{n_l-n_1})
=h^2$$
implies that $n_1$ is even, so
$2(1+3^{n_2-n_1}+\dots+3^{n_l-n_1})$ must be a square too.
However, this number is of the form $3k+2$ with integer $k,$ so it
is not a perfect square.

A natural way to generate an infinite sequence whose distinct
elements do not sum to square is to start with $c_1=2.$ Then, for
each $n \in \N,$ take the smallest positive integer $c_{n+1}$ such
that no sum of the form $c_{n+1}+\delta_n c_n+\dots+\delta_1 c_1,$
where $\delta_1, \dots, \delta_n \in \{0,1\},$ is a perfect
square. Clearly, $c_2=3,$ $c_3=5.$ Then, as $6+3=3^2,$ $7+2=3^2,$
$8+5+3=4^2,$ $9=3^2,$ we obtain that $c_4=10,$ and so on. In the
following table we give the first $18$ elements of this sequence:


\bigskip
\begin{center}


\begin{tabular}{| r | r | r | r | r | r |}

\hline

$n$ & $c_n$ & $\log c_n$ & $n$  & $c_n$ & $\log c_n$ \\ \hline

$1$ & $2$ & $0.6931$ & $10$  & $2030$ & $7.6157$ \\ \hline

$2$ & $3$ & $1.0986$ & $11$  & $3225$ & $8.0786$ \\ \hline

$3$ & $5$ & $1.6094$ & $12$  & $8295$ & $9.0234$ \\ \hline

$4$ & $10$ & $2.3025$ & $13$  & $15850$ & $9.6709$ \\
\hline

$5$ & $27$ & $3.2958$ & $14$  & $80642$ & $11.2977$ \\
\hline

$6$ & $38$ & $3.6375$ & $15$  & $378295$ & $12.8434$ \\
\hline

$7$ & $120$ & $4.7874$ & $16$  & $1049868$ & $13.8641$ \\
\hline

$8$ & $258$ & $5.5529$ & $17$  & $3031570$ & $14.9245$ \\
\hline

$9$ & $907$ & $6.8101$ & $18$  & $12565348$ & $16.3464$ \\
\hline

\end{tabular}
\end{center}
\bigskip
Here, the values of $\log c_n$ are truncated at the fourth decimal
place. At the first glance, they suggest that the limit
$\liminf_{n \to \infty} n^{-1}\log c_n$ is positive. If so, then
the sequence $c_n,$ $n=1,2,3,\dots,$ is of exponential growth too.
It seems that the sequence $c_n,$ $n=1,2,3,\dots,$ i.e.,
$$2,3,5,10,27,38,120,258,907, 2030, 3225, 8295, 15850, 80642, 378295,
1049868, \dots$$ was not studied before. At least, it is not given
in N.J.A.~Sloane's on-line encyclopedia of integer sequences {\tt
http://www.research.att.com/}\~{\tt njas/sequences/}. We thus
raise the following problem.
\begin{itemize}
\item Determine whether $\liminf_{n \to \infty} n^{-1}\log c_n$ is
zero or a positive number.
\end{itemize}

In the opposite direction, one can easily show that $c_n<4^n$ for
each $n \geq 1.$ Here is the proof of this inequality by induction
(due to a referee). Suppose that $c_n<4^n.$ If $c_{n+1}\leq
c_n+4^n,$ then $c_{n+1}<4^n+4^n<4^{n+1}.$ Otherwise, for each
$j=1,2,\dots,4^n,$ there exists a set $I = I_j \subseteq
\{1,2,\dots,n\}$ such that $c_n+j+S(I)=s_j^2,$ where
$S(I):=\sum_{i \in I} c_i$ and $s_j \in \N.$ There are $2^n$
different subsets $I$ of $\{1,2,\dots,n\},$ so the set $\{4^n-2^n,
\dots, 4^n-1, 4^n\}$ with $2^n+1$ elements contains some two
indices $j<j'$ for which the corresponding subsets $I$ (and so the
values for $S(I)$) are equal. Subtracting $c_n+j+S(I)=s_{j}^2$
from $c_n+j'+S(I)=s_{j'}^2,$ we deduce that
$j'-j=(s_{j'}-s_{j})(s_{j'}+s_{j}).$ Since $j'-j \leq 2^n,$ we
have $s_{j'}+s_j \leq 2^n,$ i.e., $s_{j'} \leq 2^n-1.$ Hence
$$ 4^n-2^n < j' < c_n+j'+S(I)=s_{j'}^2 \leq
(2^n-1)^2=4^n-2^{n+1}+1,$$ a contradiction.

Of course, $c_n<4^n$ implies that $\limsup_{n \to \infty} n^{-1}
\log c_n <\log 4.$ Our next theorem shows that, for any fixed
positive $\eps,$ there is a sequence $A=\{a_1<a_2<a_3<\dots\}$
whose distinct elements do not sum to a square and whose growth is
small in the sense that $\limsup_{n \to \infty} n^{-1} \log a_n
<\eps.$

\begin{theorem}\label{squar}
For any $\eps>0$ there is a positive constant $K=K(\eps)$ and an
infinite sequence $A=\{a_1<a_2<a_3<\dots\} \subset \N$ satisfying
$a_n < K(1+\eps)^n$ for each $n \in \N$ such that the sum of any
number of distinct elements of $A$ is not a perfect square.
\end{theorem}

\begin{proof}
Fix a prime number $p$ to be chosen later and
consider the following infinite set
$$A:=\{gp^{2m}+p^{2m-1} : g \in \{0,1,\dots,p-2\}, \> m\in \N \}.$$
Each element of $A$ in base $p$ can be written as
$\overline{g100\dots 0}$ with $2m-1$ zeros, where the `digit' $g$
is allowed to be zero. So all the elements of $A$ are distinct.

First, we will show that the sum of any distinct elements of $A$
is not a perfect square. Assume that there exists a sum $S$ which
is a perfect square. Suppose that for every $t =1,2,\dots,l$ the
sum $S$ contains $s_t>0$ elements of the form
$gp^{2m_t}+p^{2m_t-1},$ where $g \in \{0,1,\dots,p-2\}$ and $1\leq
m_1<m_2<\dots<m_l.$ Clearly, $s_t \leq p-1.$ Let us write $S$ in
the form
$$S=s_1p^{2m_1-1}+h_1p^{2m_1}+s_2p^{2m_2-1}+h_2p^{2m_2}+\dots+s_l
p^{2m_l-1}+h_l p^{2m_l}$$ $$=p^{2m_1-1}(s_1+h_1p+\dots+s_l
p^{2m_l-2m_1}+h_l p^{2m_l-2m_1+1})=p^{2m_1-1}(s_1+pH).$$ Now,
since $s_1 \in \{1,\dots,p-1\}$ and since $H$ is an integer, we
see that $S$ is divisible by $p^{2m_1-1},$ but not by $p^{2m_1},$
so it is not a perfect square.

It remains to estimate the size of the $n$th element $a_n$ of $A.$
Write $n$ in the form $n=(p-1)(m-1)+r,$ where $r \in
\{1,\dots,p-2,p-1\}$ and $m \geq 1$ is an integer. Suppose that
the elements of $A$ are divided into consecutive equal blocks with
$p-1$ elements in each block. Then all the elements of the $m$th
block are of the form $\overline{g100\dots 0}$ (with $2m-1$
zeros), where $g=0,1,\dots,p-2.$ Hence the $n$th element of $A,$
where $n=(p-1)(m-1)+r,$ is precisely the $r$th element of the
$m$th block, i.e., $a_n=a_{(p-1)(m-1)+r}=(r-1)p^{2m}+p^{2m-1}.$ It
follows that
$$a_n \leq (p-2)p^{2m}+p^{2m-1}<p^{2m+1}=p^{2(n-r)/(p-1)+3}<p^{2n/(p-1)+3}
=p^3 e^{(2n\log p)/(p-1)}.$$ Clearly, $(2\log p)/(p-1) \to 0$ as
$p \to \infty.$ Thus, for any $\eps>0,$ there exists a prime
number $p$ such that $e^{(2\log p)/(p-1)}<1+\eps.$ Take the
smallest such a prime $p=p(\eps).$ Setting $K(\eps):=p(\eps)^3,$
we obtain that $a_n < K(\eps) (1+\eps)^n$ for each $n \in \N.$
$\square$
\end{proof}

\bigskip

\section{Infinite sets whose elements do not sum to a power}

Observe that distinct elements of the sequence $2 \cdot 6^n,$
$n=0,1,2,\dots,$ cannot sum to a perfect power. Indeed,
$$S=2(6^{n_1}+\dots+6^{n_l})=
2^{n_1+1}3^{n_1}(1+6^{n_2-n_1}+\dots+6^{n_l-n_1}),$$ where $0\leq
n_1<\dots<n_l,$ is not a perfect power, because $n_1+1$ and $n_1$
are exact powers of $2$ and $3$ in the prime decomposition of $S.$
So if $S>1$ were a $k$th power, where $k$ is a prime number (which
can be assumed without loss of generality), then both $n_1+1$ and
$n_1$ must be divisible by $k,$ a contradiction.

This example is already `better' than the example $a^{p_1p_2\dots
p_n}+1,$ $n=n_0, n_0+1, \dots,$ given in \cite{luc} not only
because it is completely explicit, but also because the sequence
$2\cdot 6^n,$ $n=0,1,2,\dots,$ grows slower.

As above, we can also consider the sequence $2,3,10,18,\dots,$
starting with $e_1=2,$ whose each `next' element $e_{n+1}>e_n,$
where $n \geq 1,$ is the smallest positive integer preserving the
property that no sum of the form $\delta_1 e_1+\dots +\delta_n
e_{n} + e_{n+1},$ where $\delta_1, \dots, \delta_n \in \{0,1\},$
is a perfect power. By an argument which is slightly more
complicated than the one given for $c_n,$ one can prove again that
$e_n < 4^n$ for $n$ large enough.

However, our aim is to prove the existence of the sequence whose
$n$th element is bounded from above by $K(\eps)(1+\eps)^n$ for $n
\in \N.$ For this, we shall generalize Theorem~2 as follows:

\begin{theorem}\label{powers}
Let $U$ be the set of positive integers of the form $q_1^{\al_1}
\dots q_k^{\al_k},$ where $q_1, \dots, q_k$ are some fixed prime
numbers and $\al_1, \dots, \al_k$ run through all nonnegative
integers. Then, for any $\eps>0,$ there is a positive constant
$K=K(\eps, U)$ and an infinite sequence $A=\{a_1<a_2<a_3<\dots\}
\subset \N$ satisfying $a_n < K(1+\eps)^n$ for $n \in \N$ such
that the sum of any number of distinct elements of $A$ is not
equal to $uv^s$ with positive integers $u,v,s$ such that $u \in U$
and $s \geq 2.$
\end{theorem}

In particular, Theorem~3 with $U=\{1\}$ implies a more general
version of Theorem~2 with `perfect square' replaced by `perfect
power'.

\medskip

\begin{proof}
Fix two prime numbers $p$ and $q$ satisfying
$p<q<2p.$ Here, the prime number $p$ will be chosen later,
whereas, by Bertrand's postulate,  the interval $(p,2p)$ always
contains at least one prime number, so we can take $q$ to be any
of those primes. Consider the following infinite set
$$A:=\{gp^{m+1}q^{m}+p^{m}q^{m-1} : g \in \{1,\dots,p-1\},
\> m\in \N \}.$$ The inequality
$p^{m+2}q^{m+1}+p^{m+1}q^m>(p-1)p^{m+1}q^{m}+p^{m}q^{m-1}$ implies
that all the elements of $A$ are distinct. Also, as above, by
dividing the sequence $A$ into consecutive equal blocks with $p-1$
elements each, we find that
$$a_n=rp^{m+1}q^{m}+p^{m}q^{m-1}$$ for $n=(p-1)(m-1)+r,$ where  $m
\in \N$ and $r \in \{1,\dots,p-2,p-1\}.$

Assume that there exists a sum $S$ of some distinct $a_n$ which is
of the form $uv^s.$ Without loss of generality we may assume that
$s \geq 2$ is a prime number. Suppose that for every
$t=1,2,\dots,l$ the sum $S$ contains $s_t>0$ elements of the form
$gp^{m_t+1}q^{m_t}+p^{m_t}q^{m_t-1},$ where $g \in
\{1,\dots,p-1\}$ and $1\leq m_1<m_2<\dots<m_l.$ Clearly, $s_t \leq
p-1,$ so, in particular, $1\leq s_1 \leq p-1.$ Then, as above,
$S=p^{m_1}q^{m_1-1}(s_1+pqH)$ with an integer $H.$ If $q>p>q_k,$
then $p,q \notin U,$ so the equality
$uv^s=p^{m_1}q^{m_1-1}(s_1+pqH)$ implies that $s|m_1$ and
$s|(m_1-1),$ a contradiction.

Using $a_n=rp^{m+1}q^{m}+p^{m}q^{m-1},$ where $n=(p-1)(m-1)+r$ and
$p<q<2p,$ we find that
$$a_n < (p-1)q^{2m+1}+q^{2m-1}<q^{2m+2}<(2p)^{2(n-r)/(p-1)+4}<
(2p)^4 e^{(2n\log (2p))/(p-1)}.$$ For any $\eps>0,$ there exists a
positive number $p_{\eps}$ such that $e^{(2\log
(2p))/(p-1)}<1+\eps$ for each $p>p_{\eps}.$ Take the smallest
prime number $p=p(\eps)$ greater than $\max \{p_{\eps}, q_k\},$
and put $K(\eps,q_k)=K(\eps,U):=2p(\eps)^4.$ Then
$a_n<K(\eps,U)(1+\eps)^n$ for each $n \in \N,$ as claimed.
 $\square$
\end{proof}

\bigskip

\section{Concluding remarks}


We do not give any lower bounds for the $n$th element $a_n$ of the
`densiest' sequence $A=\{a_1<a_2<\dots\}$ whose distinct elements
do not sum to a square or, more generally, to a power. As a first
step towards solution of this problem, it would be of interest to
find out whether every infinite sequence of positive integers $A$
which has a positive asymptotic density (i.e., $d(A)>0$) contains
some elements that sum to a square. It is essential that we can
only sum distinct elements of $A,$ because, for any nonempty set
$A \subset \N,$ there is a sumset $A+A+\dots+A$ which contains a
square. In this direction, we can mention the following result of
T.~Schoen \cite{sch}: if $A$ is a set of positive integers with
asymptotic density $d(A)>2/5$ then the sumset $A+A$ contains a
perfect square. For more references on sumset related results see
the recent book \cite{tavu} of T.~Tao and V. H.~Vu.

A `finite version' of the problem on the `densiest' set whose
elements do not sum to a square was recently considered by
J.~Cilleruelo \cite{cil}. He showed that there is an absolute
positive constant $c$ such that, for any positive integer $N \geq
2,$ there exists a subset $A$ of $\{1,2,\dots,N\}$ with $\geq
cN^{1/3}$ elements whose distinct elements do not sum to a perfect
square. In fact, by taking the largest prime number $p \leq
N^{1/3},$ we see that the set
$A:=\{p,p^2+p,2p^2+p,\dots,(p-2)p^2+p\}$ with $p-1$ element is a
subset of $\{1,2,\dots,N\}.$ Since any sum of distinct elements of
$A$ is divisible by $p,$ but not by $p^2,$ we conclude that no sum
of distinct elements of the set $A$ of cardinality $p-1 \geq
\frac{1}{2} N^{1/3}$ is a perfect power.

Notice that in this type of questions not everything is determined
by the density of $B.$ In fact, there are some `large' sets $B$
for which there is a `large' set $A$ whose elements do not sum to
an integer lying in $B.$ For example, for the set of all odd
positive integers $B=\{1,3,5,7,\dots\}$ whose density $d(B)$ is
$1/2,$ the `densiest' set $A$ whose elements do not sum to an odd
number is the set of all even positive integers
$\{2,4,6,8,\dots\}$ with density $d(A)=1/2.$ On the other hand,
taking $B=\{2,4,6,8,\dots\},$ we see that no infinite sequence $A$
as required exists. Moreover, if $B$ is the set of all positive
integers divisible by $m,$ where $m \in \N$ is large, then the
density $d(B)=1/m$ is small. However, by a simple argument modulo
$m,$ it is easy to see that there is no infinite set $A \subset
\N$ (and even no set $A$ with $\geq m$ distinct positive integers)
with the property that its distinct elements always sum to a
number lying outside $B.$ Indeed, if $a_1, \dots, a_m \in \N$ then
either at least two of the following $m$ numbers
$S_j:=\sum_{i=1}^j a_i,$ where $j=1,\dots,m,$ say, $S_u$ and $S_v$
($u<v,$ $u,v \in \{1,\dots,m\}$) are equal modulo $m$ or $m|S_t,$
where $t\in \{1,\dots,m\}.$ Therefore, either their difference
$S_v-S_u=a_{u+1}+a_{u+2}+\dots+a_{v}$ or $S_t=a_1+\dots+a_t$ is
divisible by $m.$ In both cases, there is a sum of distinct
elements of $\{a_1,a_2,\dots,a_m\}$ that lies in $B.$

It follows that if, for an infinite set $B \subset \N,$ there
exists an infinite sequence of positive integers $A=\{a_1< a_2<
a_3<\dots\}$ for which $a_{i_1}+\dots+a_{i_m} \notin B$ for every
$m \in \N$ and any distinct elements $a_{i_1}, \dots, a_{i_m} \in
A,$ then $B$ must have the following property. For each $m \in \N$
there are infinitely many $k \in \N$ such that $km \notin B.$

This necessary condition is not sufficient. Take, for instance,
$B:=\N \setminus \{j^2 : j \in \N\}.$ Then, for each $m \in \N,$
there are infinitely many positive integers $k,$ say, $k=\ell^2
m,$ where $\ell=1,2,\dots,$ such that $km=(\ell m)^2 \notin B.$
However, there does not exist an infinite set of positive integers
$A=\{a_1<a_2<a_3<\dots\}$ such that for any $n \in \N$ and any
distinct $a_{i_1},\dots,a_{i_n} \in A$ the sum
$a_{i_1}+\dots+a_{i_n}$ is a perfect square. See, e.g., the
proposition in the same paper \cite{luc}, where this was proved in
a more general form with `perfect square' replaced by `perfect
power'.

Given any infinite set $B \subset \N,$ put $K:=\N \setminus B.$
Our first question stated in the introduction can be also
formulated in the following equivalent form.
\begin{itemize}
\item For which $K=\{k_1<k_2<k_3<\dots\} \subset \N$ there exists
an infinite subsequence of $\{k_{i_1}< k_{i_2}< k_{i_3}<\dots\}$
of $K$ such that all possible sums over its distinct elements lie
in $K$?
\end{itemize}

Theorem~\ref{dens} implies that if $d(K)=1$ then such a
subsequence exists. On the other hand, take the sequence $K$ of
positive integers that are not divisible by $m$ with asymptotic
density $d(K)=1-1/m$ (which is `close' to $1$ if $m$ is `large').
Then such a subsequence does not exist despite of $d(K)$ being
large. Finally, set $D:=\{2^{2^j} : j \in \N\}$ and suppose that
$K$ is the set of all possible finite sums over distinct elements
of $D.$ Then $d(K)$ is easily seen to be $0,$ but for $K$ such a
subsequence exists, e.g., $D.$

\section{Acknowledgments}

We are most grateful to the referee of this
paper, who not only carefully read the paper, but also made several
useful suggestions and also supplied us with a few recent
references. We thank A. Stankevi\v cius, who computed the first
$18$ elements of the sequence $c_n,$ $n=1,2,\dots.$ This research
was supported in part by the Lithuanian State Studies and Science
Foundation.

\begin{thebibliography}{99}

\bibitem{cil}  J.~Cilleruelo,
Solution of the Problem 38, {\it Gaceta de la Real Sociedad
Matematica Espa\~nola} {\bf 9} (2006), 455--460.

\bibitem{luc}  F.~Luca,
Infinite sets of positive integers whose sums are free of
powers, {\it Rev. Colomb. Matem.} {\bf 36} (2002), 67--70.

\bibitem{sch}  T.~Schoen,
On sets of natural numbers whose sumset  is free of squares,
{\it J. Comb. Theory, Ser. A} {\bf 88} (1999), 385--388.

\bibitem{stpo}  O.~Strauch and \v S.~Porubsk\'y,
{\it Distribution of Sequences: A Sampler},  Schriftenreihe der
Slo\-wakischen Akademie der Wissenschaften, Peter Lang, 2005.

\bibitem{tavu}  T.~Tao and V. H.~Vu, {\it Additive Combinatorics,}
 CUP, 2006.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 
Primary 11A99; Secondary 11B05, 11B99.

\noindent \emph{Keywords: } infinite sequence,
perfect square, power, asymptotic density, sumset.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

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


\end{document}