1 Introduction
For two sets
$A, B$
of integers and
$a\in \mathbb {Z}$
, define
$$ \begin{align*}A+B=\{a+b: a\in A, b\in B\},\end{align*} $$
and
$$ \begin{align*}a-B=\{a-b: b\in B\}.\end{align*} $$
For a positive integer
$h\geq 2$
, let
$$ \begin{align*}hA=\{a_{1}+\cdots+a_{h}:a_{1}, \ldots, a_{h}\in A\}.\end{align*} $$
A set A of nonnegative integers is called normal if
$0\in A$
and the greatest common divisor of all elements of A is 1.
In 1990, Erdős and Freiman [Reference Erdős and Freiman2] proved a conjecture of Erdős and Freud: if a set
$A$
of integers is a subset of
$[1,n]$
and
$|A|>{n}/{3}$
, then a power of 2 can be written as the sum of elements of A. In 1989, Nathanson and Sárközy [Reference Nathanson and Sárközy6] improved this result by showing that 3504 elements of A is enough. Finally, Lev [Reference Lev4] obtained the best possible result that a power of 2 is the sum of at most four elements of A. In 2004, Abe [Reference Abe1] extended Lev’s result to a power of m. In 2006, Pan [Reference Pan7] generalised the results of Lev and Abe.
Theorem 1.1 [Reference Pan7, Theorem 1].
Let
$k, m, n\geq 2$
be integers. Let A be a normal subset of
$[0, n]$
satisfying
$$ \begin{align*}|A|>\frac{1}{l+1}\bigg(\bigg(2-\frac{k}{lm}\bigg)n+2l\bigg),\end{align*} $$
where
$l=\lceil k/m\rceil $
. If
$m\geq 3$
, or
$m=2$
and k is even, then
$kA$
contains a power of m.
Pan conjectured that Theorem 1.1 still holds for
$m=2$
and k is odd. In 2012, Wu and Chen [Reference Wu and Chen8] made some progress towards this conjecture.
In 2010, Kapoor [Reference Kapoor3] extended Pan’s result for
$2A$
to general sequences. He proved the following two results.
Theorem 1.2 [Reference Kapoor3, Theorem 1].
Let
$\{a_{1}, a_{2}, a_{3}, \ldots \}$
be an unbounded sequence of positive integers. Assume that
$a_{n+1}/a_{n}$
approaches some limit
$\alpha $
as
$n\rightarrow \infty $
, and let
$\beta>2$
be some real number greater than
$\alpha $
. Then for sufficiently large
$x\geq 0$
, if A is a set of nonnegative integers less than or equal to x containing
$0$
and satisfying
$$ \begin{align*}|A|\geq\bigg(1-\frac{1}{\beta}\bigg)x,\end{align*} $$
then
$2A$
contains an element of
$\{a_{n}\}$
.
Theorem 1.3 [Reference Kapoor3, Theorem 2].
Let
$\{a_{1}, a_{2}, a_{3}, \ldots \}$
be an unbounded sequence of positive integers such that
$a_{n+1}/a_{n}\leq \beta $
for some constant
$\beta \geq 2$
. Then for any
$x\geq 0$
, if A is a set of nonnegative integers less than or equal to x containing
$0$
and satisfying
$$ \begin{align*}|A|>\bigg(1-\frac{1}{\beta}\bigg)x+\frac{1}{\beta}\cdot\bigg\lfloor\frac{a_{1}-1}{2}\bigg\rfloor+1,\end{align*} $$
then
$2A$
contains an element of
$\{a_{n}\}$
.
We extend Pan’s result for
$kA\ (k\geq 3)$
to general sequences that grow like the powers of a real number greater than or equal to 2.
Theorem 1.4. Let
$\beta> 2$
be a real number and let
$S=\{s_{1}, s_{2}, \ldots \}$
be an unbounded sequence of positive integers such that
$\lim _{n\to \infty } {s_{n+1}}/{s_{n}}=\alpha <\beta $
. Let
$k\geq 3$
be a positive integer. For large enough l, let A be a normal subset of
$[0, l]$
with
$l\in A$
such that
$$ \begin{align*}|A|\geq\frac{1}{\lambda+1}\bigg(2-\frac{k}{\lambda\beta}\bigg)l,\end{align*} $$
where
$\lambda =\lceil {k}/{\beta }\rceil $
. If
$2<\beta \leq 3$
, then
$kA\cap S\neq \emptyset $
for all
$k\geq {2\beta }/{(\beta -2)}$
. If
$\beta>3$
, then
$kA\cap S\neq \emptyset $
for all
$k\geq 3$
.
Theorem 1.5. Let
$\beta>2$
be a real number and let
$S=\{s_{1}, s_{2}, \ldots \}$
be an unbounded sequence of positive integers such that
$s_{n+1}/s_{n}\leq \beta $
. Let
$k\geq 3$
and l be positive integers such that
$$ \begin{align} l\bigg(\frac{k}{\beta}-\lambda+1\bigg)\geq\frac{2}{\beta}\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor+1. \end{align} $$
Let A be a normal subset of
$[0, l]$
with
$l\in A$
satisfying
$$ \begin{align} |A|>\frac{2}{ \lambda\beta(\lambda+1)} \bigg(\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor+\frac{\beta}{2}\bigg)+\frac{1}{\lambda+1} \bigg(\bigg(2-\frac{k}{\lambda\beta}\bigg)l+2\lambda\bigg), \end{align} $$
where
$\lambda =\lceil {k}/{\beta }\rceil $
. If
$2<\beta <3$
, then
$kA\cap S\neq \emptyset $
for all
$k\geq {2\beta }/{(\beta -2)}$
. If
$\beta \geq 3$
, then
$kA\cap S\neq \emptyset $
for all
$k\geq 3$
.
2 Lemmas
Lemma 2.1 [Reference Lev5, Corollary 1].
If A is a normal subset of
$[0, l]$
with
$l\in A$
and
$\rho =\lceil (l-1)/(|A|-2)\rceil -1$
, then
$$ \begin{align*} |hA|\geq \begin{cases} B_{h}(|A|) &\text{if } h\leq \rho,\\ B_{\rho}(|A|)+(h-\rho)l &\text{if } h\geq \rho,\\ \end{cases} \end{align*} $$
where
$B_{h}(x)=\tfrac 12h(h+1)(x-2)+h+1$
.
Lemma 2.2. Let
$\beta \geq 2$
be a real number. Let
$S=\{s_{1}, s_{2}, \ldots \}$
be an unbounded sequence of positive integers such that
$s_{n+1}/s_{n}\leq \beta $
. Let a, b be two positive integers. Suppose A and B are sets of integers satisfying
$A\subseteq [0, a]$
,
$B\subseteq [0, b]$
and
$0\in A\cap B$
. If
$$ \begin{align} |A|+|B|>3+\frac{2}{\beta}\bigg\lfloor \frac{s_{1}-1}{2}\bigg\rfloor+\max\bigg\{a, b, \bigg(1-\frac{1}{\beta}\bigg)(a+b)\bigg\}, \end{align} $$
then
$(A+B)\cap S\neq \emptyset $
.
Proof. We may assume that
$a\leq b$
. If
$0\leq b<s_{1}$
, put
$x_{0}=\lfloor (s_{1}-1)/2\rfloor $
. If
$b<x_{0}$
, then
$$ \begin{align*} |A|+|B|&>2+\frac{2}{\beta}\bigg\lfloor \frac{s_{1}-1}{2}\bigg\rfloor+\bigg(1-\frac{1}{\beta}\bigg)(a+b)\\ &>2+\frac{1}{\beta}(a+b)+\bigg(1-\frac{1}{\beta}\bigg)(a+b) =2+a+b, \end{align*} $$
which is a contradiction since
$|A|+|B|\leq a+b+2$
. Thus,
$x_{0}\leq b<s_{1}$
. If
$a+b<s_{1}$
, then
$$ \begin{align*} |A|+|B|&>3+\frac{2}{\beta}\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor+\bigg(1-\frac{1}{\beta}\bigg)(a+b)\\ &\geq 3+\frac{1}{\beta}(s_{1}-2)+\bigg(1-\frac{1}{\beta}\bigg)(a+b)\\ &\geq3+\frac{1}{\beta}(a+b-1)+\bigg(1-\frac{1}{\beta}\bigg)(a+b)\\ &\geq3-\frac{1}{\beta}+a+b > a+b+2, \end{align*} $$
which is again impossible. Thus,
$a+b\geq s_{1}$
. Then,
$$ \begin{align*} |A|+|B|&>3+\frac{1}{\beta}(s_{1}-2)+\bigg(1-\frac{1}{\beta}\bigg)(a+b)\\ &\geq3+\frac{1}{\beta}s_{1}-\frac{2}{\beta}+\bigg(1-\frac{1}{\beta}\bigg)s_{1}\\ &=3-\frac{2}{\beta}+s_{1} \geq s_{1}+2. \end{align*} $$
Since
$B, s_{1}-A\subseteq [0, s_{1}]$
, we must have
$s_{1}\in A+B$
.
Next, we consider
$b\geq s_{1}$
. Choose r such that
$s_{r}\leq b<s_{r+1}$
. We proceed by induction on
$a+b$
.
If
$a+b=s_{1}+1$
, then
$A\subseteq [0, 1]$
and
$B\subseteq [0, s_{1}]$
. Since
$s_{1}-A$
,
$B\subseteq [0,s_{1}]$
and
$$ \begin{align*} |A|+|B|&>3+\frac{1}{\beta}(s_{1}-2)+\bigg(1-\frac{1}{\beta}\bigg)(a+b)\\ &=3-\frac{3}{\beta}+s_{1}+1 >s_{1}+2, \end{align*} $$
we have
$s_{1}\in A+B$
.
Now, assume that
$a+b>s_{1}+1$
and that the lemma holds for the sets
$A{'}\subseteq [0, a_{1}]$
and
$B{'}\subseteq [0, b_{1}]$
with
$a_{1}+b_{1}<a+b$
. Suppose that
$(A+B)\cap S=\emptyset $
.
Case 1:
$a<s_{r}$
. Write
$A_{1}=s_{r}-A$
. Thus,
$A_{1}\subseteq [s_{r}-a, s_{r}]\subseteq [0, b]$
. If
$|A_{1}|+|B|>b+1$
, then
$$ \begin{align*} |A_{1}\cap B|=|A_{1}|+|B|-|A_{1}\cup B| \geq b+2-(b+1) =1. \end{align*} $$
Thus,
$s_{r}\in A+B$
, which is impossible. Hence,
$|A|+|B|=|A_{1}|+|B|\leq b+1$
, which contradicts the hypothesis (2.1).
Case 2:
$a\geq s_{r}$
and
$a+b>s_{r+1}$
. Write
$$ \begin{align*}A_{1}=[0, b]\cap(s_{r+1}-A), \;B_{1}=[s_{r+1}-a, b]\cap B, \end{align*} $$
$$ \begin{align*}A_{2}=[0, s_{r+1}-b-1]\cap A,\; B_{2}=[0, s_{r+1}-a-1]\cap B. \end{align*} $$
Then,
$$ \begin{align} |B|=|B_{1}|+|B_{2}|\end{align} $$
$$ \begin{align} |A|&=|A_{2}|+|[s_{r+1}-b, a]\cap A|\nonumber\\ &=|A_{2}|+|s_{r+1}-([s_{r+1}-b, a]\cap A)| \nonumber \\ &=|A_{2}|+|[s_{r+1}-a, b]\cap(s_{r+1}-A)|\nonumber\\ &=|A_{1}|+|A_{2}|. \end{align} $$
Since
$A_{1}, B_{1}\subseteq [s_{r+1}-a,b]$
and
$s_{r+1}\notin A_{1}+B_{1}$
,
$$ \begin{align} |A_{1}|+|B_{1}|\leq b-s_{r+1}+a+1.\end{align} $$
If
$b=s_{r+1}-1$
, then
$|A_{2}|=1$
and
$|B_{2}|\leq s_{r+1}-a$
. By (2.2)–(2.4),
$$ \begin{align*}|A|+|B|\leq s_{r+1}-a+1+b-s_{r+1}+a+1=b+2,\end{align*} $$
which contradicts the hypothesis (2.1). Thus,
$b\leq s_{r+1}-2$
.
Since
$(A+B)\cap S=\emptyset $
, we have
$(A_2+B_2)\cap S=\emptyset $
. Noting that
$$ \begin{align*}s_{r+1}-b-1+s_{r+1}-a-1<2(a+b)-a-b-2<a+b,\end{align*} $$
it follows from the hypothesis that if
$$ \begin{align*} \max\bigg\{s_{r+1}-b-1, s_{r+1}-a-1, \bigg(1-\frac{1}{\beta}\bigg)(2s_{r+1}-a-b-2)\bigg\}=s_{r+1}-a-1, \end{align*} $$
then
$$ \begin{align} |A_{2}|+|B_{2}|\leq s_{r+1}-a-1+3+\frac{2}{\beta}\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor. \end{align} $$
$$ \begin{align*} |A|+|B| \leq b-s_{r+1}+a+1+s_{r+1}-a-1+3+\frac{2}{\beta}\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor = b+3+\frac{2}{\beta}\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor, \end{align*} $$
which contradicts (2.1). If
$$ \begin{align*} \max\bigg\{s_{r+1}-b-1, s_{r+1} -a-1, \ & \bigg(1-\frac{1}{\beta}\bigg)(2s_{r+1}-a-b-2)\bigg\} \\ & =\bigg(1-\frac{1}{\beta}\bigg)(2s_{r+1}-a-b-2), \end{align*} $$
then
$$ \begin{align} |A_{2}|+|B_{2}|\leq\bigg(1-\frac{1}{\beta}\bigg)(2s_{r+1}-a-b-2)+3+\frac{2}{\beta}\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor. \end{align} $$
$$ \begin{align*} |A|+|B|&\leq b-s_{r+1}+a+1+\bigg(1-\frac{1}{\beta}\bigg)(2s_{r+1}-a-b-2)+3+\frac{2}{\beta} \bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor\\ &= s_{r+1}-\frac{2}{\beta}s_{r+1}+\frac{1}{\beta}(a+b)+\frac{2}{\beta}+2+\frac{2}{\beta}\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor\\ &\leq a+b-\frac{2}{\beta}(a+b)+\frac{1}{\beta}(a+b)+\frac{2}{\beta}+2+\frac{2}{\beta}\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor\\ &= \bigg(1-\frac{1}{\beta}\bigg)(a+b)+\frac{2}{\beta}+2+\frac{2}{\beta}\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor\\ &\leq \bigg(1-\frac{1}{\beta}\bigg)(a+b)+3+\frac{2}{\beta}\bigg\lfloor\frac{a_{1}-1}{2}\bigg\rfloor, \end{align*} $$
which again contradicts (2.1).
Case 3:
$a\geq s_{r}$
and
$a+b\leq s_{r+1}$
. Write
$$ \begin{align*}A_{1}=[0, s_{r}]\cap A,\; B_{1}=[0, s_{r}]\cap B,\end{align*} $$
$$ \begin{align*}A_{2}=(s_{r}, a]\cap A,\; B_{2}=(s_{r}, b]\cap B.\end{align*} $$
Since
$(A+B)\cap S=\emptyset $
, it follows that
$(A_{1}+B_{1})\cap S=\emptyset $
and so
$|s_{r}-A_{1}|+|B_{1}|\leq s_{r}+1$
. Thus,
$$ \begin{align*} |A|+|B|&\leq a+b-2s_{r}+s_{r}+1 = a+b-s_{r}+1. \end{align*} $$
However, by (2.1),
$$ \begin{align*} |A|+|B|&> 2+\bigg(1-\frac{1}{\beta}\bigg)(a+b)\\ &= a+b-\frac{1}{\beta}(a+b)+2\\ &\geq a+b-\frac{1}{\beta}s_{r+1}+2\\ &\geq a+b-s_{r}+2, \end{align*} $$
which is a contradiction. Hence, we have
$(A+B)\cap S\neq \emptyset $
.
This completes the proof of Lemma 2.2.
Remark 2.3. If
$s_{1}$
is odd, this lower bound can be improved to
$$ \begin{align*} |A|+|B|>2+\frac{2}{\beta}\bigg\lfloor \frac{s_{1}-1}{2}\bigg\rfloor+\max\bigg\{a, b, \bigg(1-\frac{1}{\beta}\bigg)(a+b)\bigg\}. \end{align*} $$
3 Proof of Theorem 1.5
Let
$k_{1}=\lfloor {k}/{2}\rfloor $
and
$k_{2}=\lceil {k}/{2}\rceil $
. Then,
$$ \begin{align*}k_{1}A\subseteq\bigg[0, \bigg\lfloor\frac{k}{2}\bigg\rfloor l\bigg], \quad k_{2}A\subseteq\bigg[0, \bigg\lceil\frac{k}{2}\bigg\rceil l\bigg].\end{align*} $$
Since
$\beta>2$
, if
$k\geq {\beta }/{(\beta -2)}$
, then
$$ \begin{align*}\bigg\lceil\frac{k}{2}\bigg\rceil\leq(\beta-1)\bigg\lfloor\frac{k}{2}\bigg\rfloor.\end{align*} $$
In particular, if
$\beta \geq 3$
, then
$$ \begin{align*}k\geq3\geq1+\frac{2}{\beta-2}=\frac{\beta}{\beta-2}. \end{align*} $$
Hence, if
$2<\beta <3$
and
$k\geq {\beta }/{(\beta -2)}$
, or
$\beta \geq 3$
, then
$\lceil {k}/{2}\rceil \leq (\beta -1)\lfloor {k}/{2}\rfloor $
. So,
$$ \begin{align} \bigg\lfloor\frac{k}{2}\bigg\rfloor\leq\bigg\lceil\frac{k}{2}\bigg\rceil \leq\bigg(1-\frac{1}{\beta}\bigg)\bigg(\bigg\lceil\frac{k}{2}\bigg\rceil+\bigg\lfloor\frac{k}{2}\bigg\rfloor\bigg). \end{align} $$
Since
$0\in A$
,
$$ \begin{align*}k_{1}A+k_{2}A=\bigg(\bigg\lfloor\frac{k}{2}\bigg\rfloor+\bigg\lceil\frac{k}{2}\bigg\rceil\bigg)A=kA.\end{align*} $$
To show
$kA\cap S\neq \emptyset $
, by Lemma 2.2 and (3.1), it is sufficient to show that
$$ \begin{align*}|k_{1}A|+|k_{2}A|>3+\frac{2}{\beta}\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor+\bigg(1-\frac{1}{\beta}\bigg)kl.\end{align*} $$
By (1.2),
$$ \begin{align} (\lambda+1)(|A|-2)>\frac{2}{\lambda\beta }\bigg(\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor+\frac{\beta}{2}\bigg)+\bigg(2-\frac{k}{\lambda\beta }\bigg)l-2. \end{align} $$
Noting that
$\lambda \geq {k}/{\beta }$
,
$$ \begin{align} (\lambda+1)(|A|-2)>\bigg(2-\frac{k}{\lambda\beta}\bigg)l-2\geq l-2. \end{align} $$
Write
$$ \begin{align*}\rho=\lceil(l-1)/(|A|-2)\rceil-1.\end{align*} $$
Then by (3.3),
$$ \begin{align} \rho<\frac{l-1}{|A|-2}\leq \lambda+1. \end{align} $$
If
$\beta>2$
and
$k\geq {2\beta }/{(\beta -2)}$
, then
$$ \begin{align*}k\bigg(\frac{1}{2}-\frac{1}{\beta}\bigg)\geq1>\bigg\lceil\frac{k}{\beta}\bigg\rceil-\frac{k}{\beta}\end{align*} $$
and so
${k}/{2}>\lceil {k}/{\beta }\rceil $
. If
$\beta \geq 3$
and
$3\leq k<2\beta $
, then
$\lceil {k}/{\beta }\rceil \leq {k}/{2}$
. If
$\beta \geq 3$
and
$k\geq 2\beta $
, then
$$ \begin{align*}\lambda=\bigg\lceil\frac{k}{\beta}\bigg\rceil<\frac{k}{\beta}+1=\frac{k}{2}-\frac{(\beta-2)k}{2\beta}+1\leq\frac{k}{2}.\end{align*} $$
Thus,
$\lambda \leq {k}/{2}$
for
$\beta \geq 3$
or
$2<\beta <3$
and
$k\geq {2\beta }/{(\beta -2)}$
. Hence, by (3.4),
$$ \begin{align*}\rho\leq\lambda\leq\bigg\lfloor\frac{k}{2}\bigg\rfloor=k_{1}.\end{align*} $$
By Lemma 2.1,
$$ \begin{align} |k_{i}A|\geq B_{\rho}(|A|)+(k_{i}-\rho)l \quad\mbox{for } i=1, 2. \end{align} $$
If
$\lambda =\rho $
, then by (3.2) and (3.5),
$$ \begin{align*} |k_{1}A|+|k_{2}A|&\geq \lambda(\lambda+1)(|A|-2)+2\lambda+2+(k-2\lambda)l\\ &> \lambda\bigg(\frac{2}{\lambda\beta}\bigg(\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor+\frac{\beta}{2}\bigg)+\bigg(2-\frac{k}{\lambda\beta}\bigg)l-2\bigg) +2\lambda+2+(k-2\lambda)l\\ &= 3+\frac{2}{\beta}\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor+\bigg(1-\frac{1}{\beta}\bigg)kl. \end{align*} $$
Now suppose that
$\rho \leq \lambda -1$
. Then,
$0\leq \rho \leq \lceil {k}/{\beta }\rceil -1$
. Hence, by (1.1),
$$ \begin{align*} |k_{1}A|+|k_{2}A|&\geq \rho(\rho+1)(|A|-2)+2\rho+2+(k-2\rho)l\\ &\geq \rho(l-1)+2\rho+2+(k-2\rho)l\\ &= kl-\rho(l-1)+2\\ &> kl-\bigg(\frac{k}{\beta}+\bigg\lceil\frac{k}{\beta}\bigg\rceil-\frac{k}{\beta}-1\bigg)l+2\\ &= kl-\frac{k}{\beta}l+\bigg(\frac{k}{\beta}-\bigg\lceil\frac{k}{\beta}\bigg\rceil+1\bigg)l+2\\ &\geq \bigg(1-\frac{1}{\beta}\bigg)kl+3+\frac{2}{\beta}\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor. \end{align*} $$
This completes the proof of Theorem 1.5.
4 Proof of Theorem 1.4
Let
$\beta ^{-}$
be some constant satisfying
$\alpha <\beta ^{-}<\beta $
, and assume that
$$ \begin{align} \frac{s_{n+1}}{s_{n}}\leq \beta^{-} \quad\mbox{for all } n\geq1. \end{align} $$
Then for any l so large that
$$ \begin{align*} \frac{1}{\lambda+1}\bigg(2-\frac{k}{\lambda\beta}\bigg)l \geq \frac{1}{\lambda+1}\bigg(\bigg(2-\frac{k}{\lambda\beta^{-}}\bigg)l+2\lambda\bigg) +\frac{2}{\lambda(\lambda+1)\beta^{-}} \bigg(\bigg\lfloor\frac{s_{1}-1}{2}\bigg\rfloor+\frac{\beta^{-}}{2}\bigg), \end{align*} $$
we see that Theorem 1.5, using the constant
$\beta ^{-}$
, gives the conclusion of Theorem 1.4. If (4.1) does not hold for all
$n\geq 1$
, then as
${s_{n+1}}/{s_{n}}\leq \beta ^{-} $
for sufficiently large n, a simple relabelling of the terms of the sequence, omitting finitely many terms at the beginning, would suffice.
This completes the proof of Theorem 1.4.
Acknowledgment
The authors would like to thank the referee for helpful comments and valuable suggestions.
