ADDITIVE COMPLETION OF THIN SETS

Abstract

Two sets $A,B$ of positive integers are called exact additive complements if $A+B$ contains all sufficiently large integers and $A(x)B(x)/x\rightarrow 1$. For $A=\{a_1<a_2<\cdots \}$, let $A(x)$ denote the counting function of A and let $a^*(x)$ denote the largest element in $A\bigcap [1,x]$. Following the work of Ruzsa [‘Exact additive complements’, Quart. J. Math. 68 (2017) 227–235] and Chen and Fang [‘Additive complements with Narkiewicz’s condition’, Combinatorica 39 (2019), 813–823], we prove that, for exact additive complements $A,B$ with ${a_{n+1}}/ {na_n}\rightarrow \infty $,

$$ \begin{align*}A(x)B(x)-x\geqslant \frac{a^*(x)}{A(x)}+o\bigg(\frac{a^*(x)}{A(x)^2}\bigg) \quad\mbox{as } x\rightarrow +\infty.\end{align*} $$

We also construct exact additive complements $A,B$ with ${a_{n+1}}/{na_n}\rightarrow \infty $ such that

$$ \begin{align*}A(x)B(x)-x\leqslant \frac{a^*(x)}{A(x)}+(1+o(1))\bigg(\frac{a^*(x)}{A(x)^2}\bigg)\end{align*} $$

for infinitely many positive integers x.

1 Introduction

Two sets $A,B$ of positive integers are called additive complements, if $A+B$ contains all sufficiently large integers. Let $A=\{a_1<a_2<\cdots \}$ be a set of positive integers. Denote by $A(x)$ the counting function of A and by $a^*(x)$ the largest element in $A\bigcap [1,x]$ . If additive complements $A,B$ satisfy

$$ \begin{align*} \frac{A(x)B(x)}{x}\rightarrow1,\end{align*} $$

then we call such $A,B$ exact additive complements. In 2001, Ruzsa [2] introduced the following notation which is powerful for the proof of additive complements. Let ${m>a_1}$ be an integer and let $k=A(m)$ . Denote by $L(m)$ the smallest number l for which there are integers $b_1,\ldots ,b_l$ such that the numbers $a_i+b_j,1\leqslant i\leqslant k, 1\leqslant j\leqslant l$ , contain every residue modulo m. Obviously, $L(m)\geqslant m/k$ .

Theorem 1.1 (Ruzsa [2]).

If

(1.1) $$ \begin{align} \frac{a_{n+1}}{na_n}\rightarrow\infty,\end{align} $$

then A has an exact complement.

Theorem 1.2 (Ruzsa [2]).

Let A be a set satisfying ${A(2x)}/{A(x)}\rightarrow 1$ . The following are equivalent.

1. (a) A has an exact complement.

2. (b) $A(m)L(m)/m\rightarrow 1$ .

3. (c) There is a sequence $m_1\kern1.5pt{<}\kern1.5pt m_2\kern1.5pt{<}\kern1.2pt\cdots $ of positive integers such that ${A(m_{i+1})/ A(m_i)\kern1.2pt{\rightarrow}\kern1.2pt 1}$ and $A(m_i)L(m_i)/m_i\rightarrow 1$ .

Theorem 1.3 (Ruzsa [3]).

For exact additive complements $A,B$ with ${A(2x)}/ {A(x)}\rightarrow 1$ ,

$$ \begin{align*} A(x)B(x)-x\geqslant (1+o(1))\frac{a^*(x)}{A(x)} \quad\mbox{as } x\rightarrow +\infty. \end{align*} $$

In 2019, Chen and Fang [1] improved Theorem 1.3 by removing the exact condition. Chen and Fang also showed in [1] that Theorem 1.3 is the best possible.

Theorem 1.4 (Chen and Fang [1]).

There exist exact additive complements $A,B$ with ${A(2x)}/{A(x)}\rightarrow 1$ such that

$$ \begin{align*} A(x)B(x)-x\leqslant (1+o(1))\frac{a^*(x)}{A(x)}\end{align*} $$

for infinitely many positive integers x.

In this paper, under condition (1.1) from [2], we obtain the following result.

Theorem 1.5. For exact additive complements $A,B$ with (1.1),

(1.2) $$ \begin{align} A(x)B(x)-x\geqslant \frac{a^*(x)}{A(x)}+o\bigg( \frac{a^*(x)}{A(x)^2}\bigg) \quad \mbox{as}\ x\rightarrow +\infty.\end{align} $$

Moreover, we also show that ${a^*(x)}/{A(x)^2}$ is the best possible.

Theorem 1.6. There exist exact additive complements $A,B$ with (1.1) such that

(1.3) $$ \begin{align} \liminf_{x\to \infty }\frac{A(x)B(x)-x-\frac{a^*(x)}{A(x)}}{\frac{a^*(x)}{A(x)^2}}\leqslant 1. \end{align} $$

2 Proofs of the main results

Let

$$ \begin{align*}\sigma (x, n)=|\{ (a, b) : a+b=n, a, b\leqslant x, a\in A, b\in B\} |\end{align*} $$

and

$$ \begin{align*}\delta (x, n)=|\{ (a, b) : b-a=n, a, b\leqslant x, a\in A, b\in B\} |.\end{align*} $$

The ideas used in the proofs of the main results come from [1–3]. We use the following lemma of Ruzsa in the proof of Theorem 1.5.

Lemma 2.1 [3, Lemma 2.1].

Let U and V be finite sets of integers and let

$$ \begin{align*}\sigma (n)=|\{ (u,v) : u\in U, v\in V, u+v=n\} |\end{align*} $$

and

$$ \begin{align*}\delta (n)= |\{ (u,v) : u\in U, v\in V, v-u=n\} |.\end{align*} $$

Then

$$ \begin{align*}\sum_{\sigma (n)>1} (\sigma (n)-1) \geqslant \frac 1{|U|} \sum_{\delta (n)>1} (\delta (n)-1).\end{align*} $$

Proof of Theorem 1.5.

Assume the contrary. Suppose that (1.2) does not hold. Then there exist a positive number $\delta _0(<1)$ and a sequence $x_1<x_2<\cdots <x_k<\cdots $ such that

(2.1) $$ \begin{align} A(x_k)B(x_k)-x_k\leqslant \frac{a^*(x_k)}{A(x_k)}-\delta _0\frac{a^*(x_k)}{A(x_k)^2}. \end{align} $$

We know that

$$ \begin{align*} A(x_k)B(x_k)-x_k&=\sum_{\substack{a\leqslant x_k, b\leqslant x_k\\ a\in A, b\in B}} 1 -x_k=\sum_{n=1}^{2x_k} \sigma (x_k, n)-x_k \\ & =\sum_{\substack{n=1\\ \sigma (x_k, n)\geqslant 1}}^{x_k} (\sigma(x_k, n)-1)+ \sum_{\substack{n=x_k+1\\ \sigma (x_k, n)\geqslant 1}}^{2x_k} \sigma (x_k, n) \\ & = \sum_{\substack{n=1\\ \sigma (x_k, n)\geqslant 1}}^{2x_k} (\sigma (x_k, n)-1) + \sum_{\substack{n=x_k+1\\ \sigma (x_k, n)\geqslant 1} }^{2x_k} 1 \\ & =\sum_{\substack{n=1\\ \sigma (x_k,n)>1}}^{2x_k} (\sigma (x_k, n)-1) + \sum_{\substack{n=x_k+1\\ \sigma (x_k, n)\geqslant 1} }^{2x_k} 1. \end{align*} $$

Since $a^*(x_k)\in A$ and $a^*(x_k)+b>x_k$ for all $b\in B$ with $x_k-a^*(x_k)<b\leqslant x_k$ ,

$$ \begin{align*}\sum_{\substack{n=x_k+1\\ \sigma (x_k, n)\geqslant 1} }^{2x_k} 1\geqslant B(x_k)-B(x_k-a^*(x_k)).\end{align*} $$

Thus,

$$ \begin{align*} A(x_k)B(x_k)-x_k\geqslant \sum_{\substack{n\\ \sigma(x_k, n)>1} } (\sigma (x_k,n)-1)+B(x_k)-B(x_k-a^*(x_k)).\end{align*} $$

From Ruzsa’s Lemma 2.1,

(2.2) $$ \begin{align} A(x_k)B(x_k)-x_k\geqslant \frac{1}{A(x_k)}\sum_{\substack{n\\ \delta(x_k, n)>1} } (\delta (x_k,n)-1)+B(x_k)-B(x_k-a^*(x_k)).\end{align} $$

Let

$$ \begin{align*}D=\{(a,b) : a\in A, b\in B, a\leqslant b\leqslant x_k-a^*(x_k) \}.\end{align*} $$

Then

(2.3) $$ \begin{align} \sum_{\substack{n\\ \delta(x_k, n)>1} } (\delta (x_k,n)-1)=\sum_{\substack{n\\ \delta(x_k, n)\geqslant 1} } (\delta (x_k,n)-1)\geqslant |D|-(x_k-a^*(x_k)+1). \end{align} $$

Now we need a lower bound for $|D|$ . We consider the following two cases.

Case 1: $a^*(x_k)>\frac 12x_k$ for infinitely many k. By (1.1),

$$ \begin{align*}A\bigg(\frac{\delta _0}{5}\frac{a^*(x_k)}{A(x_k)}\bigg)=A(x_k)-1 \quad\mbox{for all sufficiently large integers } k.\end{align*} $$

Thus, in this case, by Theorem 1.3 and $A(x)B(x)/x\rightarrow 1$ ,

$$ \begin{align*} |D|&\geqslant \sum_{\substack{\frac{\delta _0}{5}\frac{a^*(x_k)}{A(x_k)}\leqslant b\leqslant x_k-a^*(x_k)\\ b\in B}} A(b) \geqslant A\bigg(\frac{\delta _0}{5}\frac{a^*(x_k)}{A(x_k)}\bigg)\bigg(B(x_k-a^*(x_k))-B\bigg(\frac{\delta _0}{5}\frac{a^*(x_k)}{A(x_k)}\bigg)\bigg) \\ &= (A(x_k)-1)B(x_k-a^*(x_k))-A\bigg(\frac{\delta _0}{5}\frac{a^*(x_k)}{A(x_k)}\bigg)B\bigg(\frac{\delta _0}{5}\frac{a^*(x_k)}{A(x_k)}\bigg) \\ &= A(x_k)B(x_k)+A(x_k)(B(x_k-a^*(x_k))-B(x_k))-B(x_k-a^*(x_k)) \\ & \quad -A\bigg(\frac{\delta _0}{5}\frac{a^*(x_k)}{A(x_k)}\bigg)B\bigg(\frac{\delta _0}{5}\frac{a^*(x_k)}{A(x_k)}\bigg) \\ &\geqslant x_k+\bigg(1-\frac{\delta _0}{4}\bigg)\frac{a^*(x_k)}{A(x_k)}+A(x_k)(B(x_k-a^*(x_k))-B(x_k))-B(a^*(x_k))-\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)} \\ &\geqslant x_k+\bigg(1-\frac{\delta _0}{4}\bigg)\frac{a^*(x_k)}{A(x_k)}+A(x_k)(B(x_k-a^*(x_k))-B(x_k)) \\&\quad -\bigg(1+\frac{\delta _0}{4}\bigg)\frac{a^*(x_k)}{A(x_k)}-\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)} \\ &= x_k-\frac{3\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}+A(x_k)(B(x_k-a^*(x_k))-B(x_k)) \end{align*} $$

for sufficiently large k. It follows from (2.2) and (2.3) that

$$ \begin{align*} A(x_k)B(x_k)-x_k &\geqslant \frac{x_k}{A(x_k)}-\frac{3\delta _0}{4}\frac{a^*(x_k)}{A(x_k)^2} +B(x_k-a^*(x_k))-B(x_k)-\frac{x_k-a^*(x_k)+1}{A(x_k)} \\ & \quad +B(x_k)-B(x_k-a^*(x_k) )\\ &>\frac{a^*(x_k)}{A(x_k)}-\delta _0\frac{a^*(x_k)}{A(x_k)^2} \end{align*} $$

for sufficiently large k, which is in contradiction with (2.1).

Case 2: $a^*(x_k)\leqslant \tfrac 12x_k$ for infinitely many k. By (1.1),

$$ \begin{align*}A\bigg(\frac{\delta_0}{4}\frac{a^*(x_k)}{A(x_k)}\bigg)=A(x_k)-1 \quad\mbox{for all sufficiently large integers } k.\end{align*} $$

Thus, in this case, by Theorem 1.3 and $A(x)B(x)/x\rightarrow 1$ ,

$$ \begin{align*} |D| & \geqslant \sum_{\substack{\frac{\delta _0}{2}\frac{a^*(x_k)}{A(x_k)}<b\leqslant x_k-a^*(x_k)\\ b\in B}} A\bigg(b-\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}\bigg) \\ & =\sum_{\substack{\frac{\delta _0}{2}\frac{a^*(x_k)}{A(x_k)}<b<a^*(x_k)+\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}\\ b\in B}} A\bigg(b-\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}\bigg)+ \sum_{\substack{a^*(x_k)+\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}\leqslant b\leqslant x_k-a^*(x_k)\\b\in B}} A\bigg(b-\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}\bigg) \\ & =(A(x_k)-1)\bigg(B\bigg(a^*(x_k)+\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}\bigg)-B\bigg(\frac{\delta _0}{2}\frac{a^*(x_k)}{A(x_k)}\bigg)\bigg) \\ &\quad +A(x_k)\bigg(B( x_k-a^*(x_k))-B\bigg(a^*(x_k)+\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}\bigg)\bigg) \\ & =A\bigg(a^*(x_k)+\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}\bigg)B\bigg(a^*(x_k)+\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}\bigg)-B\bigg(a^*(x_k)+\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}\bigg) \\ &\quad -A\bigg(\frac{\delta _0}{2}\frac{a^*(x_k)}{A(x_k)}\bigg)B\bigg(\frac{\delta _0}{2}\frac{a^*(x_k)}{A(x_k)}\bigg)+A(x_k)B(x_k)+A(x_k)(B(x_k-a^*(x_k))-B(x_k)) \\ &\quad -A\bigg(a^*(x_k)+\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}\bigg)B\bigg(a^*(x_k)+\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}\bigg) \\ & =A(x_k)B(x_k)+A(x_k)(B(x_k-a^*(x_k))-B(x_k))-B\bigg(a^*(x_k)+\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}\bigg) \\ &\quad -A\bigg(\frac{\delta _0}{2}\frac{a^*(x_k)}{A(x_k)}\bigg)B\bigg(\frac{\delta _0}{2}\frac{a^*(x_k)}{A(x_k)}\bigg) \\& \geqslant x_k+\bigg(1-\frac{\delta _0}{10}\bigg)\frac{a^*(x_k)}{A(x_k)}+A(x_k)(B(x_k-a^*(x_k))-B(x_k)) \\ &\quad -\bigg(1+\frac{\delta _0}{10}\bigg)\frac{a^*(x_k)+\frac{\delta _0}{4}\frac{a^*(x_k)}{A(x_k)}}{A(x_k)} -\frac{3\delta _0}{5}\frac{a^*(x_k)}{A(x_k)} \\ &\geqslant x_k-\frac{9\delta _0}{10}\frac{a^*(x_k)}{A(x_k)}+A(x_k)(B(x_k-a^*(x_k))-B(x_k)), \end{align*} $$

for sufficiently large k. It follows from (2.2) and (2.3) that

$$ \begin{align*} A(x_k)B(x_k)-x_k &\geqslant \frac{x_k}{A(x_k)}-\frac{9\delta _0}{10}\frac{a^*(x_k)}{A(x_k)^2}+B(x_k-a^*(x_k))-B(x_k)-\frac{x_k-a^*(x_k)+1}{A(x_k)} \\ &\quad +B(x_k)-B(x_k-a^*(x_k))\\ &> \frac{a^*(x_k)}{A(x_k)}-\delta_0\frac{a^*(x_k)}{A(x_k)^2} \end{align*} $$

for sufficiently large k, which is in contradiction with (2.1).

This completes the proof of Theorem 1.5.

Proof of Theorem 1.6.

Let $a_1=1$ and $a_2=4$ . We construct the sequence $a_3,a_4,\dots $ with

(2.4) $$ \begin{align}a_{n+1}\gg n^4a_n\end{align} $$

and a sequence $n_1,n_2,\dots $ such that $a_1,a_2,\dots ,a_{n_k}$ form a complete residue system modulo $n_k$ and $n_k\mid a_{n_k}$ . We get such a sequence by a greedy algorithm: let $n_1=2$ , and if $n_1,n_2,\dots ,n_k$ are already defined, then let $n_{k+1}=a_{n_k}$ . Since $a_1,\dots ,a_{n_k}$ are distinct residues modulo $a_{n_k}$ , we can choose $a_{n_k+1},\dots ,a_{n_{k+1}}$ such that $a_{m+1}\gg m^4a_m$ for ${m=n_k,\ldots , n_{k+1}-1}$ , $a_{n_k}\mid a_{a_{n_k}}$ and $a_1,\dots ,a_{n_{k+1}}$ form a complete residue system modulo $n_{k+1}$ .

For every positive integer k, we further take

$$ \begin{align*} b_1=n_k, \quad b_2=2n_k, \dots, b_{{a_{n_k}}/{n_k}}=\frac{a_{n_k}}{n_k}\cdot n_k.\end{align*} $$

Then $a_i+b_j$ for $1\leqslant i\leqslant p, 1\leqslant j\leqslant {a_{n_k}}/{n_k}$ , form a complete residue system modulo $a_{n_k}$ . From the definition of $L(a_{n_k})$ ,

(2.5) $$ \begin{align}L(a_{n_k})=\frac{a_{n_k}}{n_k}.\end{align} $$

For the set $A=\{a_k\}_{k=1}^{\infty }$ and every positive integer k, define $q_k$ by

(2.6) $$ \begin{align} q_k=\bigg\lfloor\frac{a_{k+1}}{k^4a_k}\bigg\rfloor, \quad \mbox{that is},\quad q_k\cdot k^4a_k<a_{k+1}\leqslant (q_k+1)\cdot k^4a_k.\end{align} $$

Define the same sets $A,B$ as in [2, Theorem 3] (replacing $m_k$ by $a_k$ ) and write ${A_k=A\bigcap [1,a_k]}$ . Take $U_k\subseteq [1,a_k]$ so that $|U_k|=L(a_k)$ and $A_k+U_k$ contains every residue module $a_k$ . Let

$$ \begin{align*} V_k=U_k+\bigg\{(q_k-1)a_k,q_ka_k,(q_k+1)a_k,\ldots, \bigg\lfloor \frac{q_{k+1}a_{k+1}}{a_k}\bigg\rfloor a_k\bigg\} \quad\mbox{and}\quad B=\bigcup_{k=1}^\infty V_k.\end{align*} $$

Let $q_ka_k\leqslant x\leqslant q_{k+1}a_{k+1}$ . The sequence $\{q_k\}_{k=1}^{\infty }$ defined in (2.6) is increasing to infinity by (2.4) and $A(q_ka_k)\sim A(a_k)$ . (In fact, $A(q_ka_k)=k=A(a_k)$ by (2.6).) By the same proof as in [2, Theorem 3], $A,B$ are additive complements and $A(x)B(x)\sim x$ . Thus, the set A with (2.4) has an exact complement B. Obviously, such an A with (2.4) satisfies (1.1).

Finally, we prove that (1.3) holds for infinitely many $x_k$ . For x with $q_ka_k\leqslant x<(q_{k+1}-1)a_{k+1}$ , we have $k\leqslant A(x)\leqslant k+1$ and

(2.7) $$ \begin{align} B(x)\leqslant \bigg(\bigg\lfloor\frac{x}{a_k}\bigg\rfloor-q_k+2\bigg)L(a_k) +\sum_{i=2}^k\bigg(\bigg\lfloor\frac{q_ia_i}{a_{i-1}}\bigg\rfloor-q_{i-1}+2\bigg)L(a_{i-1}). \end{align} $$

By Theorem 1.2(b), $L(a_{k-1})\leqslant {2a_{k-1}}/{(k-1)} \mbox { for large } k$ . From (2.6),

$$ \begin{align*} \sum_{i=2}^k\bigg(\bigg\lfloor\frac{q_ia_i}{a_{i-1}}\bigg\rfloor-q_{i-1}+2\bigg)L(a_{i-1}) \leqslant (k-1)\frac{2q_ka_k}{k-1}=O(q_ka_k)=O\bigg(\frac{a_{k+1}}{(k+1)^4}\bigg).\end{align*} $$

It is easy to see that, for large k,

$$ \begin{align*}(q_k-2)L(a_k)\leqslant 2\frac{q_ka_k}{k}=O\bigg(\frac{a_{k+1}}{(k+1)^5}\bigg).\end{align*} $$

It follows from (2.7) that

(2.8) $$ \begin{align} B(x)\leqslant \frac{x}{a_k}L(a_k)+O\bigg(\frac{a_{k+1}}{(k+1)^4}\bigg).\end{align} $$

Choose $x_k=a_{n_k+1}$ , where $n_k$ is the index satisfying (2.5). Then by (2.8),

$$ \begin{align*} A(x_k)B(x_k)-x_k-\frac{a^*(x_k)}{A(x_k)} &\leqslant(n_k+1)\frac{x_k}{n_k}-x_k-\frac{x_k}{n_k+1} +O\bigg(\frac{x_k}{(n_k+1)^3}\bigg)\\ &=\frac{x_k}{A(x_k)^2}+O\bigg(\frac{x_k}{A(x_k)^3}\bigg). \end{align*} $$

This completes the proof of Theorem 1.6.