On the density of bounded bases

Abstract

For a nonempty set A of integers and an integer n, let $r_{A}(n)$ be the number of representations of n in the form $n=a+a'$, where $a\leqslant a'$ and $a, a'\in A$, and $d_{A}(n)$ be the number of representations of n in the form $n=a-a'$, where $a, a'\in A$. The binary support of a positive integer n is defined as the subset S(n) of nonnegative integers consisting of the exponents in the binary expansion of n, i.e., $n=\sum_{i\in S(n)} 2^i$, $S(-n)=-S(n)$ and $S(0)=\emptyset$. For real number x, let $A(-x,x)$ be the number of elements $a\in A$ with $-x\leqslant a\leqslant x$. The famous Erdős-Turán Conjecture states that if A is a set of positive integers such that $r_A(n)\geqslant 1$ for all sufficiently large n, then $\limsup_{n\rightarrow\infty}r_A(n)=\infty$. In 2004, Nešetřil and Serra initially introduced the notation of “bounded” property and confirmed the Erdős-Turán conjecture for a class of bounded bases. They also proved that, there exists a set A of integers satisfying $r_A(n)=1$ for all integers n and $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in A$. On the other hand, Nathanson proved that there exists a set A of integers such that $r_A(n)=1$ for all integers n and $2\log x/\log 5+c_1\leqslant A(-x,x)\leqslant 2\log x/\log 3+c_2$ for all $x\geqslant 1$, where $c_1,c_2$ are absolute constants. In this paper, following these results, we prove that, there exists a set A of integers such that: $r_A(n)=1$ for all integers n and $d_A(n)=1$ for all positive integers n, $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in A$ and $A(-x,x) \gt (4/\log 5)\log\log x+c$ for all $x\geqslant 1$, where c is an absolute constant. Furthermore, we also construct a family of arbitrarily spare such sets A.

1. Introduction

For nonempty sets $A,B$ of integers, define

\begin{equation*}A+A=\{a+a':a,a'\in A\}\hskip3mm\textrm{and}\hskip3mm A-A=\{a-a':a,a'\in A\}.\end{equation*}

Let $\mathbb{Z}$ be the set of integers and $\mathbb{N}$ the set of positive integers. For any integer n, let $r_{A}(n)$ be the number of representations of n in the form $n=a+a'$, where $a\leqslant a'$ and $a, a'\in A$, and $d_{A}(n)$ be the number of representations of n in the form $n=a-a'$, where $a, a'\in A$. Clearly, $d_{A}(-n)=d_{A}(n)$ for any positive integer n. Let $|A|$ be the cardinality of the set A and $\max A$ be the maximal element in A. For a real number x, denote $|x|$ by the absolute value of x, $\lfloor x\rfloor$ by the largest integer no larger than x, $A+x=\{a+x:a\in A\}$, and $A(-x,x)$ by the number of elements $a\in A$ with $-x\leqslant a\leqslant x$.

The famous Erdős-Turán Conjecture [3] states that if A is a set of positive integers such that $r_A(n)\geqslant 1$ for all sufficiently large n, then

\begin{equation*}\limsup_{n\rightarrow\infty}r_A(n)=\infty.\end{equation*}

In 2004, Nešetřil and Serra [6] initially introduced the notation of “bounded” property. For a positive integer n, denote the binary support of n by the subset S(n) of nonnegative integers consisting of the exponents in the binary expansion of n, i.e., $n=\sum_{i\in S(n)} 2^i$, and $S(-n)=-S(n)$. Define $S(0)=\emptyset$. A set A of integers is called bounded if there is a function $f:\mathbb{N}\bigcup\{0\}\rightarrow \mathbb{N}\bigcup\{0\}$ such that $f(0)=0$ and for each $n\in A+A$ there exists a pair $x,y\in A$ with

\begin{equation*}n=x+y,\hskip6mm|S(x)\bigcup S(y)|\leqslant f(|S(n)|).\end{equation*}

Obviously, if A is a set of positive integers and the binary expansion of each element in A has no two consecutive 1’s, then A is a bounded set with $f(n)=n$. Nešetřil and Serra [6] confirmed the Erdős-Turán conjecture for a class of “bounded” bases.

For a set A of integers, A is a basis for $\mathbb{Z}$ if $r_A(n)\geqslant 1$ for all integers n and a unique representation basis for $\mathbb{Z}$ if $r_A(n)=1$ for all integers n. For the unique representation basis for $\mathbb{Z}$, by considering the bounded property, Nešetřil and Serra [6] also obtained the following result:

Theorem A. ([6, Theorem 5])

There is a bounded basis A of $\mathbb{Z}$ satisfying $r_A(n)=1$ for each $n\in \mathbb{Z}$.

Recently, the author [4] generalized the above result by adding the restriction that $d_A(n)=1$ for all positive integers n. On the other hand, research on the density of basis also attracts much interest from experts. In 2003, Nathanson [5] considered the existence of unique representation basis A with logarithmic growth, that is:

Theorem B. ([5, Theorem 2])

There is a unique representation basis A for $\mathbb{Z}$ such that

\begin{eqnarray*}\frac{2\log x}{\log 5}+2(1-\frac{\log 3}{\log 5})\leqslant A(-x,x)\leqslant \frac{2\log x}{\log 3}+2 \end{eqnarray*}

for all $x\geqslant 1$.

Afterwards, Xiong and Tang [7] extended Theorem B by considering the structure of difference, and constructed a unique representation basis A of integers such that $d_A(n)=1$ for all positive integers n and

\begin{equation*}\frac{4(\log x-\log 2)}{\log 15}-1 \lt A(-x,x) \lt \frac{4(\log x-\log 2)}{\log 3}+7\end{equation*}

for all x > 1.

In this paper, based on the above results, we incorporate the bounded property and prove that:

Theorem 1.1. There exists a bounded basis A of integers such that $r_A(n)=1$ for all integers n and $d_A(n)=1$ for all positive integers n, and

\begin{equation*}A(-x,x) \gt \frac{4}{\log 5}\log\log x+c \hskip2mm \text{for all} \hskip2mm x\geqslant 1,\end{equation*}

where c is an absolute constant.

On the other hand, similar to [5] and [7], we also obtain the following result:

Theorem 1.2. Let f(x) be a function such that $\lim_{x\rightarrow\infty}f(x)=\infty$. Then there exists a bounded basis A of integers such that $r_A(n)=1$ for all integers n and $d_A(n)=1$ for all positive integers n, and

\begin{equation*}A(-x,x)\leqslant f(x) \hskip2mm\textrm{for all sufficiently large}\hskip2mm x.\end{equation*}

Furthermore, noting that if $r_{A}(n)=2$ for infinitely many integers, then $d_A(n)\geqslant 2$ for infinitely many integers n, Cilleruelo and Nathanson [2] posed the following problem:

Cilleruelo-Nathanson Problem. Give general conditions for functions f ₁ and f ₂ to assure that there exists a set A such that $d_A(n)\equiv f_1(n)$ and $r_{A}(n)\equiv f_2(n)$. Is the condition $\liminf_{u\rightarrow \infty}f_1(u)\geqslant 2$ and $\liminf_{|u|\rightarrow \infty}f_2(u)\geqslant 2$ sufficient?

In 2011, Y.G. Chen and the author [1] answered this problem affirmatively. In this paper, we also consider the bounded property and obtain that:

Theorem 1.3. If two functions $f_1:\mathbb{N}\rightarrow \mathbb{N}$ and $f_2:\mathbb{Z}\rightarrow \mathbb{N}$ satisfy that $\liminf_{u\rightarrow \infty}f_1(u)\geqslant 2$ and $\liminf_{|u|\rightarrow \infty}f_2(u)\geqslant 2$, then there exists a bounded set A of integers such that $d_A(n)=f_1(n)$ for all $n\in \mathbb{N}$ and $r_{A}(n)=f_2(n)$ for all $n\in \mathbb{Z}$.

2. Proof of Theorem 1.1 and Theorem 1.2

The main idea is from [5]-[7]. During the induction process, we focus on the choice of critical values. Denote $\sigma(n)$ by

\begin{equation*}S(\sigma(n))=\{i\in S(n): i-1\not\in S(n)\} \hskip2mm \textrm{for positive integer} \hskip2mm n\end{equation*}

and

\begin{equation*}S(\sigma(n))=\{i\in S(n): i+1\not\in S(n)\} \hskip2mm \textrm{for negative integer} \hskip2mm n.\end{equation*}

It easily follows from the definition of $\sigma(n)$ that $|S(n+\sigma(n))|=|S(\sigma(n))|\leqslant |S(n)|$, $S(\sigma(n))$ and $S(n+\sigma(n))$ has no two consecutive integers.

Lemma 2.1. ([4, Lemma 2.1])

Let $x,y,z$ be integers with yz > 0 such that

1. (i) $|S(|y|)|\leqslant |S(|z|)|$;

2. (ii) a > b for any $a\in S(|z|)$ and $b\in S(|x|)\bigcup S(|y|)$;

3. (iii) each of S(x), S(y) and S(z) has no two consecutive integers.

Then

\begin{equation*}|S(x)\bigcup S(y+z)|\leqslant 4|S(x+y+z)|.\end{equation*}

Proof of Theorem 1.1. We will construct finite sets of integers $A_1\subseteq A_2\subseteq\cdots\subseteq A_k\subseteq \cdots$ such that for any positive integer k, we have:

1. (i) $|A_k|=4k+3$;

2. (ii) $r_{A_k}(n)\leqslant 1$ for all $n\in \mathbb{Z}$ and $d_{A_k}(n)\leqslant 1$ for all $n\in \mathbb{N}$;

3. (iii) $r_{A_{k}}(n)=1$ for all $n\in \mathbb{Z}$ with $|n|\leqslant \lfloor\frac{k}{2}\rfloor$ and $d_{A_k}(n)=1$ for all $n\in \mathbb{N}$ with $1\leqslant n\leqslant k$;

4. (iv) $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in A_k$;

5. (v) the binary support of each element in A_k has no two consecutive integers;

6. (vi) $d_{k} \lt 172d_{k-1}^5$, where $d_k=\max\{|a|:a\in A_k\}$ and $d_0=1$.

Let $A_1=\{-32,-10,0,9,33,128,129\}$. Then $d_1=129$, $r_{A_1}(0)=1$, $r_{A_1}(1)=r_{A_1}(-1)=d_{A_1}(1)=1$, $r_{A_1}(n)\leqslant 1$ for all $n\in \mathbb{Z}$ and $d_{A_1}(n)\leqslant 1$ for all $n\in \mathbb{N}$, $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in A_1$, and the binary support of each element in A ₁ has no two consecutive integers. Thus, (i)-(vi) hold for k = 1.

Assume that we have already obtained a set A_k of integers satisfying (i)-(vi) for some positive integer k. By the definition of d_k we know that $A_k\subseteq [-d_k,d_k]$. Since $r_{A_k}(0)\leqslant 1$, we have $d_k\in A_k$ and $-d_k\not\in A_k$, or $-d_k\in A_k$ and $d_k\not\in A_k$. Thus, $A_k+A_k\subseteq [-2d_k+2,2d_k]$ or $[-2d_k,2d_k-2]$. In any case, we have $A_k-A_k\subseteq [-2d_k+1,2d_k-1]$. Write

\begin{equation*} u_k=\min\{|n|:n\not\in A_k+A_k\},\hskip4mm v_k=\min\{n \gt 0:n\not\in A_k-A_k\}.\end{equation*}

It follows that

\begin{equation*} 2\leqslant u_k\leqslant 2d_k-1,\hskip3mm 2\leqslant v_k\leqslant 2d_k.\end{equation*}

Let

(2.1)\begin{eqnarray} a_k=\lceil\max\{\log_2\left(\frac{3d_k+1-\sigma(u_k)}{4^{|S(u_k)|-1}}\right), \log_2d_k+1, \max S(u_k)+3\}\rceil, \end{eqnarray}

where $\lceil x \rceil$ is the least integer no less than x. Then

\begin{equation*} \sigma(u_k)+2^{a_k}4^{|S(u_k)|-1}\geqslant 3d_k+1.\end{equation*}

Take

(2.2)\begin{eqnarray} x_k=u_k+\sigma(u_k)+2^{a_k}+2^{a_k+2}+2^{a_k+4}+\cdots+2^{a_k+2(|S(u_k)|-1)}. \end{eqnarray}

Thus, $x_k-u_k\geqslant 3d_k+1$. Furthermore,

(2.3)\begin{eqnarray} x_k=u_k+\sigma(u_k)+2^{a_k}\frac{4^{|S(u_k)|}-1}{3} \lt 4d_k+\frac{1}{3}4^{|S(u_k)|}2^{a_k}, \end{eqnarray}

where the last inequality is based on the facts that $\sigma(u_k)\leqslant u_k$ and $u_k\leqslant 2d_k-1$. If $a_k=\lceil \log_2\left(\frac{3d_k+1-\sigma(u_k)}{4^{|S(u_k)|-1}}\right)\rceil$, then

\begin{equation*}4d_k+\frac{1}{3}4^{|S(u_k)|}2^{a_k} \lt 4d_k+\frac{1}{3}4^{|S(u_k)|}(2\cdot\frac{3d_k}{4^{|S(u_k)|-1}})=12d_k.\end{equation*}

If $a_k=\lceil \log_2d_k+1\rceil$, then by $|S(u_k)|\leqslant \max S(u_k)+1$ and $2^{\max S(u_k)}\leqslant u_k$ we know that

\begin{eqnarray*}4d_k+\frac{1}{3}4^{|S(u_k)|}2^{a_k} & \lt &4d_k+\frac{1}{3}4^{|S(u_k)|}(2\cdot2^{\log_2d_k+1})\\ &\leqslant &4d_k+\frac{4}{3}d_k4^{\max S(u_k)+1}\leqslant 4d_k+\frac{16}{3}d_ku_k^2\\ &\leqslant &4d_k+\frac{64}{3}d_k^3 \lt 22d_k^3.\end{eqnarray*}

If $a_k=\max S(u_k)+3$, then

\begin{eqnarray*}4d_k+\frac{1}{3}4^{|S(u_k)|}2^{a_k} &=&4d_k+\frac{8}{3}4^{|S(u_k)|}2^{\max S(u_k)}\leqslant 4d_k+\frac{32}{3}2^{3\max S(u_k)}\\ &\leqslant &4d_k+\frac{32}{3}u_k^3\leqslant 86d_k^3.\end{eqnarray*}

In any case,

(2.4)\begin{eqnarray} 4d_k+\frac{1}{3}4^{|S(u_k)|}2^{a_k}\leqslant 86d_k^3. \end{eqnarray}

It infers from (2.1) and (2.3) that

\begin{equation*} x_k \lt 86d_k^3.\end{equation*}

Let

(2.5)\begin{eqnarray} b_k=\lceil\max\{\log_2\left(\frac{3x_k+2u_k-\sigma(v_k)}{4^{|S(v_k)|-1}}\right),\max S(v_k)+3, a_k+2|S(u_k)|-1\}\rceil. \end{eqnarray}

Then

\begin{equation*} \sigma(v_k)+2^{b_k}4^{|S(v_k)|-1}\geqslant3x_k+2u_k.\end{equation*}

Take

(2.6)\begin{eqnarray} y_k=\sigma(v_k)+2^{b_k}+2^{b_k+2}+2^{b_k+4}+\cdots+2^{b_k+2(|S(v_k)|-1)}. \end{eqnarray}

Thus, $y_k\geqslant3x_k+2u_k$. Furthermore,

(2.7)\begin{eqnarray} y_k+v_k=v_k+\sigma(v_k)+2^{b_k}\frac{4^{|S(v_k)|}-1}{3} \lt 4d_k+\frac{1}{3}4^{|S(v_k)|}2^{b_k}, \end{eqnarray}

where the last inequality is based on the facts that $\sigma(v_k)\leqslant v_k$ and $v_k\leqslant 2d_k$. If $b_k=\lceil \log_2\left(\frac{3x_k+2u_k-\sigma(v_k)}{4^{|S(v_k)|-1}}\right)\rceil$, then by $x_k \lt 86 d_k^3$ we know that

\begin{equation*}4d_k+\frac{1}{3}4^{|S(v_k)|}2^{b_k} \lt 4d_k+\frac{1}{3}4^{|S(v_k)|}(2\cdot\frac{3x_k+2u_k}{4^{|S(v_k)|-1}}) =4d_k+\frac{8}{3}(3x_k+2u_k) \lt 689d_k^3.\end{equation*}

If $b_k=\max S(v_k)+3$, then we could deduce from $|S(v_k)|\leqslant \max S(v_k)+1$ and $2^{\max S(v_k)}\leqslant v_k$ that

\begin{eqnarray*}4d_k+\frac{1}{3}4^{|S(v_k)|}2^{b_k} &=&4d_k+\frac{8}{3}4^{|S(v_k)|}2^{\max S(v_k)}\leqslant 4d_k+\frac{32}{3}2^{3\max S(v_k)}\\ &\leqslant &4d_k+\frac{32}{3}v_k^3\leqslant 86d_k^3.\end{eqnarray*}

If $b_k=a_k+2|S(u_k)|-1$, then it infers from (2.4) that

\begin{eqnarray*}4d_k+\frac{1}{3}4^{|S(v_k)|}2^{b_k} &=&4d_k+\frac{1}{3}4^{|S(u_k)|}2^{a_k}\cdot\frac{1}{2}4^{|S(v_k)|}\leqslant 86d_k^3\cdot\frac{1}{2}4^{|S(v_k)|}\\ &\leqslant& 86d_k^3\cdot\frac{1}{2}(2d_k)^2=172d_k^5. \end{eqnarray*}

In any case,

\begin{eqnarray*}4d_k+\frac{1}{3}4^{|S(v_k)|}2^{b_k}\leqslant 172d_k^5.\end{eqnarray*}

It infers from (2.5) and (2.7) that

\begin{equation*} y_k+v_k \lt 172d_k^5.\end{equation*}

To sum up,

(2.8)\begin{equation}3d_k \lt x_k-u_k \lt x_k \lt y_k \lt y_k+v_k \lt 172d_k^5. \end{equation}

Now we divide into the following two cases according to $u_k\not\in A_k+A_k$ or $u_k\in A_k+A_k$.

Case 1. $u_k\not\in A_k+A_k$.

Let

\begin{equation*}B_{k+1}=A_k\bigcup\{x_k,-x_k+u_k\} \hskip3mm \textrm{and} \hskip2mm A_{k+1}=B_{k+1}\bigcup\{y_k,y_k+v_k\}.\end{equation*}

It follows from $x_k \gt x_k-u_k \gt 3d_k$, $3x_k+2u_k\leqslant y_k \lt y_k+v_k$ and the definitions of d_k, x_k, y_k, we know that $r_{A_{k+1}}(u_k)=d_{A_{k+1}}(v_k)=1$, $r_{A_{k+1}}(n)\leqslant 1$ for all $n\in \mathbb{Z}$ and $d_{A_{k+1}}(n)\leqslant 1$ for all $n\in \mathbb{N}$. Thus, (ii) holds. By $a_k\geqslant\max S(u_k)+3$, $b_k\geqslant\max S(v_k)+3$ and the definition of $A_{k+1}$ we know that (i) and (v) hold. We will prove that $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in A_{k+1}$. If x = y, then

\begin{equation*}|S(x)\bigcup S(y)|=|S(x)|=|S(2x)|=|S(x+y)|\leqslant 4|S(x+y)|.\end{equation*}

So we only need to consider x ≠ y.

Firstly, we will prove that $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in B_{k+1}$ with x ≠ y. Noting that

\begin{eqnarray*}|S(x_k)|&\leqslant& |S(u_k+\sigma(u_k))|+\left|S\left(2^{a_k}+2^{a_k+2} +2^{a_k+4}+\cdots+2^{a_k+2(|S(u_k)|-1)}\right)\right|\\ &=&|S(\sigma(u_k))|+|S(u_k)|\leqslant 2|S(u_k)|\end{eqnarray*}

and

\begin{eqnarray*}|S(-x_k+u_k)|&=&\left|S\left(\sigma(u_k)+2^{a_k}+2^{a_k+2} +2^{a_k+4}+\cdots+2^{a_k+2(|S(u_k)|-1)}\right)\right|\\ &\leqslant& |S(\sigma(u_k))|+|S(u_k)|\leqslant 2|S(u_k)|,\end{eqnarray*}

we have

\begin{equation*}|S(x_k)\bigcup S(-x_k+u_k)|\leqslant 4|S(u_k)|=4|S(x_k+(-x_k+u_k))|.\end{equation*}

Let $x\in A_k$. By (2.1) we have $a_k\geqslant \log_2 d_k+1$, then $a_k \gt \max S(|x|)$. Also by (2.1), we know that $a_k\geqslant\max S(u_k)+3$. Taking $y_1=u_k+\sigma(u_k)$ and $z_1=2^{a_k}+2^{a_k+2}+2^{a_k+4}+\cdots+2^{a_k+2(|S(u_k)|-1)}$ in Lemma 2.1, we have

\begin{eqnarray*}|S(x)\bigcup S(x_k)|=|S(x)\bigcup S(y_1+z_1)|\leqslant 4|S(x+y_1+z_1)|=4|S(x+x_k)|.\end{eqnarray*}

Taking $y_2=-\sigma(u_k)$ and $z_2=-(2^{a_k}+2^{a_k+2}+2^{a_k+4}+\cdots+2^{a_k+2(|S(u_k)|-1)})$ in Lemma 2.1, we have

\begin{eqnarray*}|S(x)\bigcup S(-x_k+u_k)|=|S(x)\bigcup S(y_2+z_2)|\leqslant 4|S(x+y_2+z_2)|=4|S(x-x_k+u_k)|.\end{eqnarray*}

Thus, $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in B_{k+1}$ with x ≠ y.

Now, we will prove that $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in A_{k+1}$ with x ≠ y. It follows from (2.6) that

\begin{eqnarray*}|S(y_k)|&=&\left|S\left(\sigma(v_k)+2^{b_k}+2^{b_k+2}+2^{b_k+4}+\cdots +2^{b_k+2(|S(v_k)|-1)}\right)\right|\\ &\leqslant& |S(\sigma(v_k))|+\left|S\left(2^{b_k}+2^{b_k+2}+2^{b_k+4}+\cdots +2^{b_k+2(|S(v_k)|-1)}\right)\right|\\ &=&|S(\sigma(v_k))|+|S(v_k)|\leqslant 2|S(v_k)|\end{eqnarray*}

and

\begin{eqnarray*}|S(y_k+v_k)|&=&\left|S\left(v_k+\sigma(v_k)+2^{b_k}+2^{b_k+2}+2^{b_k+4}+\cdots +2^{b_k+2(|S(v_k)|-1)}\right)\right|\\ &\leqslant&|S(v_k+\sigma(v_k))|+|S(v_k)|\leqslant 2|S(v_k)|,\end{eqnarray*}

we have

\begin{equation*}|S(y_k)\bigcup S(y_k+v_k)|\leqslant 4|S(v_k)|.\end{equation*}

By $b_k\geqslant\max S(v_k)+3$ and

\begin{eqnarray*}S(2y_k+v_k)=S(2\sigma(v_k)+v_k+2\left(2^{b_k}+2^{b_k+2}+2^{b_k+4}+\cdots +2^{b_k+2(|S(v_k)|-1)}\right)),\end{eqnarray*}

we know that

\begin{eqnarray*}|S(2y_k+v_k)|&=&|S(2\sigma(v_k)+v_k)|+\left|S\left(2^{b_k}+2^{b_k+2}+2^{b_k+4}+\cdots +2^{b_k+2(|S(v_k)|-1)}\right)\right|\\ &\geqslant& \left|S\left(2^{b_k}+2^{b_k+2}+2^{b_k+4}+\cdots +2^{b_k+2(|S(v_k)|-1)}\right)\right|=|S(v_k)|.\end{eqnarray*}

Thus,

\begin{equation*}|S(y_k)\bigcup S(y_k+v_k)|\leqslant 4|S(2y_k+v_k)|.\end{equation*}

Let $x\in B_{k+1}$. By (2.5) we have $b_k\geqslant a_k+2|S(u_k)|-1$, namely, $b_k \gt a_k+2(|S(u_k)|-1)$. Then $b_k \gt \max S(|x|)$. Also by (2.5), we know that $b_k\geqslant\max S(v_k)+3$. Taking $y_1=\sigma(v_k)$ and $z_1=2^{b_k}+2^{b_k+2}+2^{b_k+4}+\cdots +2^{b_k+2(|S(v_k)|-1)}$ in Lemma 2.1, we have

\begin{eqnarray*}|S(x)\bigcup S(y_k)|=|S(x)\bigcup S(y_1+z_1)|\leqslant 4|S(x+y_1+z_1)|=4|S(x+y_k)|.\end{eqnarray*}

Taking $y_2=\sigma(v_k)+v_k$ and $z_2=2^{b_k}+2^{b_k+2}+2^{b_k+4}+\cdots +2^{b_k+2(|S(v_k)|-1)}$ in Lemma 2.1, we have

\begin{eqnarray*}|S(x)\bigcup S(y_k+v_k)|=|S(x)\bigcup S(y_2+z_2)|\leqslant 4|S(x+y_2+z_2)|=4|S(x+y_k+v_k)|.\end{eqnarray*}

To sum up, $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in A_{k+1}$.

Case 2. $u_k\in A_k+A_k$. Then $-u_k\not\in A_k+A_k$.

Let

\begin{equation*}B_{k+1}=\{x_k,-x_k-u_k\} \hskip3mm \textrm{and} \hskip3mm A_{k+1}=\{y_k,y_k+v_k\},\end{equation*}

where x_k and y_k are defined in (2.2) and (2.6). Similar to Case 1, we know that $A_{k+1}$ satisfies (i)-(ii), (iv)-(v) and $r_{A_{k+1}}(-u_k)=d_{A_{k+1}}(v_k)=1$.

In both cases, it follows from (2.8) and the construction of $A_{k+1}$ that $d_{k+1} \lt 172d_k^5$. Thus, (vi) holds.

Now we will prove that (iii) holds. (The proof of (iii) is the same as in [7, Theorem 1.1], we also give the details for the sake of completeness). If $u_k\not\in A_k+A_k$, then by Case 1 we know that $u_k\in A_{k+1}+A_{k+1}$, thus, $u_{k+2}\geqslant u_{k+1} \gt u_k$ if $-u_k\in A_{k+1}+A_{k+1}$. Otherwise, if $-u_k\not\in A_{k+1}+A_{k+1}$, then $u_{k+1}=u_k\in A_{k+1}+A_{k+1}$ and $-u_{k+1}\in A_{k+2}+A_{k+2}$ by Case 2, thus, $u_{k+2} \gt u_{k+1}=u_k$. If $u_k\in A_k+A_k$, then by Case 2 we know that $-u_k\in A_{k+1}+A_{k+1}$. It follows from $u_k\in A_k+A_k\subseteq A_{k+1}+A_{k+1}$ that $u_{k+2}\geqslant u_{k+1} \gt u_k$. In both cases, $u_{k+2} \gt u_k$. It follows from $u_2\geqslant 2$ that $u_{2k}\geqslant u_2+k-1\geqslant k+1$. Thus, for any positive integer k we have

\begin{equation*}\{-k,\cdots,-1,0,1,\cdots,k\}\subseteq A_{2k}+A_{2k}.\end{equation*}

Similarly, $v_k \lt v_{k+1}$. It infers from $v_1\geqslant 2$ that $v_k\geqslant k+1$. Thus, for any positive integer k we have

\begin{equation*}\{-k,\cdots,-1,0,1,\cdots,k\}\subseteq A_{k}-A_{k}.\end{equation*}

Namely, $r_{A_{k+1}}(n)=1$ for all $n\in \mathbb{Z}$ with $|n|\leqslant \lfloor\frac{k+1}{2}\rfloor$ and $d_{A_{k+1}}(n)=1$ for all $n\in \mathbb{N}$ with $1\leqslant n\leqslant k+1$. Thus, (iii) holds.

Let

\begin{equation*}A=\bigcup_{k=1}^{\infty} A_k.\end{equation*}

Then $r_A(n)=1$ for all $n\in \mathbb{Z}$ and $d_A(n)=1$ for all $n\in \mathbb{N}$, $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in A$. Furthermore, we could deduce from (vi) and $d_0=1$ that

\begin{eqnarray*} d_k\leqslant c_1^{5^k}, \hskip3mm \textrm{where} \hskip3mm c_1=\sqrt[4]{172}. \end{eqnarray*}

For sufficiently large x, there exists a positive integer k such that $d_k\leqslant x \lt d_{k+1}$. It follows from $4k+3\leqslant A(-x,x)\leqslant 4k+7$ that

\begin{equation*}A(-x,x) \gt \frac{4}{\log 5}\log\log x+c, \hskip2mm\textrm{where}\hskip2mm c \hskip2mm\textrm{is an absolute constant}.\end{equation*}

This completes the proof of Theorem 1.1. $\Box$

Proof of Theorem 1.2. In the proof of Theorem 1.1, the only constraint on the choice of x_k (resp. y_k) is the size of the value a_k (resp. b_k). The following proof is similar to [5, Theorem 1] and [7, Theorem 1.1]. We apply the method of Theorem 1.1 by replacing a_k with $s_k(\geqslant a_k)$. Namely, take

(2.9)\begin{equation}x_k=u_k+\sigma(u_k)+2^{s_k}+2^{s_k+2} +2^{s_k+4}+\cdots+2^{s_k+2(|S(u_k)|-1)}.\end{equation}

Given a function f(x) tending to infinity, we shall take induction on k to construct a non-decreasing sequence of integers $\{h_k\}_{k=1}^\infty$ such that $A(-x,x)\leqslant f(x)$ for all integers x with $h_1\leqslant x\leqslant d_k$. Firstly, choose $h_1\geqslant d_1$ so that $f(x)\geqslant 11$ for $x\geqslant h_1$. Then

\begin{equation*} A(-x,x)\leqslant 11\leqslant f(x) \hskip2mm\textrm{for}\hskip2mm h_1\leqslant x\leqslant d_2.\end{equation*}

Suppose that for some integer $k\geqslant 2$, we have already selected an integer $h_{k-1}\geqslant d_{k-1}$ such that

\begin{equation*} f(x)\geqslant 4k+3 \hskip2mm\textrm{for}\hskip2mm x\geqslant h_{k-1}, \hskip3mm A(-x,x)\leqslant f(x) \hskip2mm\textrm{for}\hskip2mm h_1\leqslant x\leqslant d_k.\end{equation*}

Noting that f(x) tends to infinity, there exist positive integers h_k and $s_{k+1}$ with $h_k\geqslant d_k$ and $h_k \lt x_{k+1}-u_{k+1}$ (taking large $s_{k+1}$ in (2.9)) such that $f(x)\geqslant 4k+7$ for $x\geqslant h_{k}$. It follows that

\begin{equation*} A(-x,x)\leqslant 4k+7\leqslant f(x) \hskip2mm\textrm{for}\hskip2mm h_k\leqslant x\leqslant d_{k+1}.\end{equation*}

For $d_k\leqslant x\leqslant h_k$, we could deduce from the construction of $A_{k+1}\setminus A_k$ and the fact $h_k \lt x_{k+1}-u_{k+1}$ that

\begin{equation*} A(-x,x)=A_k(-x,x)=4k+3\leqslant f(x)\hskip2mm\textrm{for}\hskip2mm d_k\leqslant x\leqslant h_k.\end{equation*}

To sum up,

\begin{equation*} A(-x,x)\leqslant f(x) \hskip2mm\textrm{for}\hskip2mm d_k\leqslant x\leqslant d_{k+1}.\end{equation*}

By the induction hypothesis we know that $A(-x,x)\leqslant f(x)$ for $h_1\leqslant x\leqslant d_{k+1}$. It follows that

\begin{equation*}A(-x,x)\leqslant f(x) \hskip3mm\textrm{for all}\hskip3mm x\geqslant h_1. \end{equation*}

This completes the proof of Theorem 1.2.

3. Proof of Theorem 1.3

To give the proof of Theorem 1.3, we need the following preliminary lemmas. The idea is from [1, Theorem 1.2], [4, Theorem 1.1] and [6, Theorem 5].

Lemma 3.1. Let $f_1:\mathbb{N}\rightarrow \mathbb{N}$ and $f_2:\mathbb{Z}\rightarrow \mathbb{N}$ be two functions such that

(3.1)\begin{eqnarray} \liminf_{u\rightarrow \infty}f_1(u)\geqslant 2 \hskip4mm \textrm{and} \hskip4mm \liminf_{|u|\rightarrow \infty}f_2(u)\geqslant 2. \end{eqnarray}

Let $B\subseteq \mathbb{Z}$ be a finite set with $|B|\geqslant 2$ such that:

1. (i) $d_B(n)\leqslant f_1(n)$ for all $n\in \mathbb{N}$ and $r_B(n)\leqslant f_2(n)$ for all $n\in \mathbb{Z}$;

2. (ii) $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in B$;

3. (iii) the binary support of each element in B has no two consecutive integers.

   If k is a positive integer with $d_B(k) \lt f_1(k)$, then there exists a finite set D with $B\subseteq D\subseteq \mathbb{Z}$ such that:

4. (iv) $d_D(k)=d_B(k)+1$;

5. (v) $d_D(n)\leqslant f_1(n)$ for all $n\in \mathbb{N}$ and $r_D(n)\leqslant f_2(n)$ for all $n\in \mathbb{Z}$;

6. (vi) $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in D$;

7. (vii) the binary support of each element in D has no two consecutive integers.

Proof. Let $B=\{b_1,b_2,\cdots,b_s\}$, where $b_1 \lt b_2 \lt \cdots \lt b_s$. Let $m=2\max_{1\leqslant j\leqslant s}|b_j|+k$. By (3.1), we could choose a subset U_k of positive integers such that:

1. (1) $|U_k|=|S(k)|$;

2. (2) $\min U_k \gt k+3\max ||B||$, where $||B||=\{|b|:b\in B\}$;

3. (3) U_k has no two consecutive integers;

4. (4) $f_1(n)\geqslant 2$ and $f_2(n)\geqslant 2$ for all integers $n\in [b-m,b+m]\bigcap \mathbb{Z}$, where $b=\sigma(k)+\sum_{i\in U_k} 2^i$.

Let

\begin{equation*}D=B\bigcup \{b,b+k\}.\end{equation*}

Then

\begin{equation*}D+D=\{2b,2b+k,2b+2k\}\bigcup\{B+B\}\bigcup\{B+b\}\bigcup\{B+b+k\}\end{equation*}

and

\begin{equation*}D-D=\pm\{\{k\}\bigcup\{B-B\}\bigcup\{B-b\}\bigcup\{B-b-k\}\}.\end{equation*}

We could deduce from (i)-(iii), the definition of D and the fact $b \gt 3\max ||B||+k$ that $d_D(k)=d_B(k)+1$, and the binary support of each element in D has no two consecutive integers. Furthermore, $r_D(2b)=r_D(2b+k)=r_D(2b+2k)=1$. It also follows from

\begin{eqnarray*}&&b-m \lt b+b_1 \lt b+b_2 \lt \cdots \lt b+b_s \lt b+m,\\ &&b-m \lt b+k+b_1 \lt b+k+b_2 \lt \cdots \lt b+k+b_s \lt b+m\end{eqnarray*}

and (4) that $r_D(n)\leqslant 2\leqslant f_2(n)$ for each $n\in \{B+b\}\bigcup\{B+b+k\}$. Noting that the sets $\{2b,2b+k,2b+2k\}$, B + B, B + b and $B+b+k$ are pairwise disjoint, we know that $r_D(n)\leqslant f_2(n)$ for all integers n. Similarly, by

\begin{eqnarray*}&&b-m \lt b-b_s \lt b-b_{s-1} \lt \cdots \lt b-b_1 \lt b+m,\\ &&b-m \lt b+k-b_s \lt b+k-b_{s-1} \lt \cdots \lt b+k-b_1 \lt b+m,\end{eqnarray*}

and (4) we have $d_D(n)\leqslant 2\leqslant f_1(n)$ for each $n\in \{B-b\}\bigcup\{B-b-k\}$. Noting that the sets B − B, B − b and $B-b-k$ are pairwise disjoint, we know that $d_D(n)\leqslant f_1(n)$ for all positive integers n. By the same proof as in Theorem 1.1, we know that $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in D$.

This completes the proof of Lemma 3.1.

Lemma 3.2. Let $f_1:\mathbb{N}\rightarrow \mathbb{N}$ and $f_2:\mathbb{Z}\rightarrow \mathbb{N}$ be two functions such that (3.1) holds. Let $B\subseteq \mathbb{Z}$ be a finite set with $|B|\geqslant 2$ such that:

1. (i) $d_B(n)\leqslant f_1(n)$ for all $n\in \mathbb{N}$ and $r_B(n)\leqslant f_2(n)$ for all $n\in \mathbb{Z}$;

2. (ii) $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in B$;

3. (iii) the binary support of each element in B has no two consecutive integers.

   If k is an integer with $r_B(k) \lt f_2(k)$, then there exists a finite set D with $B\subseteq D\subseteq \mathbb{Z}$ such that:

4. (iv) $r_D(k)=r_B(k)+1$;

5. (v) $d_D(n)\leqslant f_1(n)$ for all $n\in \mathbb{N}$ and $r_D(n)\leqslant f_2(n)$ for all $n\in \mathbb{Z}$;

6. (vi) $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in D$;

7. (vii) the binary support of each element in D has no two consecutive integers.

Proof. Let $B=\{b_1,b_2,\cdots,b_s\}$, where $b_1 \lt b_2 \lt \cdots \lt b_s$. Let $m=2\max_{1\leqslant j\leqslant s}|b_j|+|k|$. By (3.1), we could choose a subset U_k of positive integers such that:

1. (1) $|U_k|=|S(k)|$;

2. (2) $\min U_k \gt |k|+3\max ||B||$;

3. (3) U_k has no two consecutive integers;

4. (4) $f_1(n)\geqslant 2$ and $f_2(n)\geqslant 2$ for all integers $n\in [b-m,b+m]\bigcap \mathbb{Z}$, where

   \begin{eqnarray*}b= \begin{cases} k+\sigma(k)+\sum_{i\in U_k} 2^i, &\textrm{if}\hskip2mm k \gt 0, \cr \sum_{i\in U_k} 2^i, & \textrm{if}\hskip2mm k=0, \cr k+\sigma(k)+\sum_{i\in U_k} 2^{-i}, & \textrm{if}\hskip2mm k \lt 0.\end{cases} \end{eqnarray*}

Let

\begin{equation*}D=B\bigcup \{b,-b+k\}.\end{equation*}

Then

\begin{equation*}D+D=\{k,2b,-2b+2k\}\bigcup(B+B)\bigcup(B+b)\bigcup(B-b+k)\end{equation*}

and

\begin{equation*}D-D=\pm\{\{2b-k\}\bigcup(B-B)\bigcup(B-b)\bigcup(B+b-k)\}.\end{equation*}

We could deduce from (i)-(iii), the definition of D and the fact $b \gt 3\max ||B||+k$ that $r_D(k)=r_B(k)+1$, and the binary support of each element in D has no two consecutive integers. Furthermore, $r_D(2b)=r_D(-2b+2k)=1$. It also follows from

\begin{eqnarray*}&&b-m \lt b+b_1 \lt b+b_2 \lt \cdots \lt b+b_s \lt b+m,\\ &&b-m \lt -b+k+b_1 \lt -b+k+b_2 \lt \cdots \lt -b+k+b_s \lt b+m\end{eqnarray*}

and (4) that $r_D(n)\leqslant 2\leqslant f_2(n)$ for each $n\in \{B+b\}\bigcup\{B-b+k\}$. Noting that the sets $\{2b,-2b+2k\}$, B + B, B + b and $B-b+k$ are pairwise disjoint, we know that $r_D(n)\leqslant f_2(n)$ for all integers n. Similarly, by

\begin{eqnarray*}&&-2b-k \lt b-m \lt b-b_s \lt b-b_{s-1} \lt \cdots \lt b-b_1 \lt b+m \lt 2b+k,\\ &&b-m \lt b-k+b_1 \lt b-k+b_2 \lt \cdots \lt b-k+b_s \lt b+m\end{eqnarray*}

and (4) we have $d_D(n)\leqslant 2\leqslant f_1(n)$ for each $n\in \{B-b\}\bigcup\{B+b-k\}$. Noting that the sets $\{2b-k\}$, B − B, B − b and $B+b-k$ are pairwise disjoint, we know that $d_D(n)\leqslant f_1(n)$ for all positive integers n. By the same proof as in Theorem 1.1, we know that $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in D$.

This completes the proof of Lemma 3.2.

Remark 3.3. During the proof of Lemma 3.1 and Lemma 3.2, since we do not need accurate quantitative estimation for d_k, we just choose sufficiently large b in each stage.

Proof of Theorem 1.3. Theorem 1.3 follows from Lemma 3.1 and Lemma 3.2. The proof is similar to Theorem 1.1, we omit the detail here.