Proof. Suppose that there exist two pairs of sets $(C_{1}, D_{1}),(C_{2}, D_{2})$ satisfying the conditions of Lemma 2.1. Let v be the minimal nonnegative integer such that $\chi _{C_{1}}(v) \neq \chi _{C_{2}}(v)$ . Then, $C_{1} \cap [0, v-1]=C_{2} \cap [0, v-1]$ and $R_{C_1}(v)\not =R_{C_2}(v)$ since $0\in C_1,C_2$ . By $R_{C_1}(v)=R_{D_1}(v)$ and $R_{C_2}(v)=R_{D_2}(v)$ , it suffices to prove that $R_{D_1}(v)=R_{D_2}(v)$ for a contradiction.

Since $0 \in C$ and $C \cap D=\emptyset $ , it follows that $0\notin D$ , and so

$$ \begin{align*}R_{D_{1}}(v)=|\{(d, d^{\prime}): d<d^{\prime}<v, d, d^{\prime} \in D_{1}, d+d^{\prime}=v\}|.\end{align*} $$

Let t be an integer with $0\le t\le s$ such that $r_{t}<v<r_{t+1}$ . Here we define $r_{0}=0$ , $r_{s+1}=+\infty $ . Since

$$ \begin{align*}[0, v-1] \setminus\{r_{1},r_2, \ldots, r_{t}\}=(C_{1} \cap[0, v-1]) \cup(D_{1} \cap[0, v-1]),\end{align*} $$

it follows that

$$ \begin{align*} D_{1} \cap[0, v-1] & =([0, v-1]\setminus\{r_{1}, r_2,\ldots, r_{t}\}) \setminus (C_{1} \cap[0, v-1]) \\[3pt] & =[0, v-1] \setminus((C_{1} \cap[0, v-1]) \cup\{r_{1},r_2, \ldots, r_{s}\}). \end{align*} $$

Similarly,

$$ \begin{align*}D_{2} \cap[0, v-1]=[0, v-1]\setminus((C_{2} \cap[0, v-1]) \cup\{r_{1},r_2, \ldots, r_{t}\}).\end{align*} $$

Hence, $D_{1} \cap [0, v-1]=D_{2} \cap [0, v-1]$ and so $R_{D_{1}}(v)=R_{D_{2}}(v)$ .

Proof. For $k=0,1,\ldots ,2m$ ,

$$ \begin{align*} R_{C^{\prime}}(k)&=|\{(c, c^{\prime}): c<c^{\prime}, c, c^{\prime} \in C^{\prime}, c+c^{\prime}=k\}| \\ &=|\{(c, c^{\prime}): c<c^{\prime}, m-c, m-c^{\prime} \in C, c+c^{\prime}=k\}| \\ &=|\{(m-c, m-c^{\prime}): c<c^{\prime}, m-c, m-c^{\prime} \in C, 2 m-(c+c^{\prime})=2 m-k\}| \\ &=R_{C}(2 m-k). \end{align*} $$

Similarly, $R_{D^{\prime }}(k)=R_{D}(2 m-k)$ . Since $R_{C}(2 m-k)=R_{D}(2 m-k)$ , it follows that $R_{C^{\prime }}(k)=R_{D^{\prime }}(k)$ .

Proof. If for some even positive integer M, the integers $M-2, M-4, \ldots , M-2^{\lceil \log _{2} M\rceil -1}$ are all contained in the set A, then $\tfrac 12M-1,\tfrac 12M-2,\ldots ,\tfrac 12M-2^{\lceil \log _{2} {M}/{2}\rceil -1}$ are all contained in the set A. By Lemma 2.4, it follows that $\tfrac 12M=2^{\lceil \log _{2} {M}/{2}\rceil }-1$ , and so $M=2^{\lceil \log _{2} M\rceil }-2$ .

Proof of Theorem 1.3.

(Sufficiency). Suppose that there exists a positive integer $l \geq 1$ such that $C=A_{l-1} \cup (2^{l-1}+1+B_{l-1})$ and $D=B_{l-1} \cup (2^{l-1}+1+A_{l-1})$ . Now we prove that $R_{C}(n)=R_{D}(n)$ for all nonnegative integers n. Clearly,

$$ \begin{align*} R_{C}(n) & =|\{(c, c^{\prime}): c<c^{\prime}, c, c^{\prime} \in A_{l-1}, c+c^{\prime}=n\}| \\[4pt] &\quad +|\{(c, c^{\prime}): c \in A_{l-1}, c^{\prime} \in 2^{l-1}+1+B_{l-1}, c+c^{\prime}=n\}| \\[4pt] &\quad +|\{(c, c^{\prime}): c<c^{\prime}, c, c^{\prime} \in 2^{l-1}+1+B_{l-1}, c+c^{\prime}=n\}| \\[4pt] & =R_{A_{l-1}}(n)+|\{(c, c^{\prime}): c \in A_{l-1}, c^{\prime} \in B_{l-1}, c+c^{\prime}=n-(2^{l-1}+1) \}| \\[4pt] &\quad +R_{B_{l-1}}(n-2(2^{l-1}+1)). \end{align*} $$

Similarly,

$$ \begin{align*} R_{D}(n) & =R_{B_{l-1}}(n)+|\{(d, d^{\prime}): d \in B_{l-1}, d^{\prime} \in A_{l-1}, d+d^{\prime}=n-(2^{l-1}+1)\}| \\[4pt] &\quad +R_{A_{l-1}}(n-2(2^{l-1}+1)). \end{align*} $$

By Lemma 2.1, for any positive integer m, $R_{A_{l-1}}(m)=R_{B_{l-1}}(m)$ . Hence, $R_{C}(n)=R_{D}(n)$ .

(Necessity). Suppose that $C \cup D=[0, m]\setminus \{r\}$ , $C \cap D=\emptyset $ and, for any positive integer n, $R_{C}(n)=R_{D}(n)$ . Let $C^{\prime }=m-C$ , $D^{\prime }=m-D$ . Then by Lemma 2.3, we have $C^{\prime } \cup D^{\prime }=[0, m]\setminus \{m-r\}$ , $C^{\prime } \cap D^{\prime }=\emptyset $ and $R_{C^{\prime }}(n)=R_{D^{\prime }}(n)$ for any positive integer n. Hence, we can assume that $r \leq {m}/{2}$ without loss of generality.

Let $p_{C}(x)\kern-1pt=\kern-1.2pt\sum _{i=0}^{m} \chi _{C}(i) x^{i}$ , $p_{D}(x)\kern-1pt=\kern-1.2pt\sum _{i=0}^{m} \chi _{D}(i) x^{i}$ . Since $C \kern-0.5pt\cup\kern-0.5pt D \kern-1pt=\kern-0.5pt [0, m]\kern-0.5pt\setminus\kern-0.5pt \{r\}$ , $C \kern-0.5pt\cap\kern-0.5pt D\kern-1pt=\kern-1pt\emptyset $ , it follows that

(3.1) $$ \begin{align} p_{C}(x)+p_{D}(x)=\frac{1-x^{m+1}}{1-x}-x^{r}. \end{align} $$

Since $R_{C}(n)=R_{D}(n)$ for any positive integer n,

$$ \begin{align*}\sum_{n=0}^{\infty} R_{C}(n) x^{n}=\sum_{n=0}^{\infty} R_{D}(n) x^{n}.\end{align*} $$

Hence,

$$ \begin{align*} \frac{1}{2} p_{C}(x)^{2}-\frac{1}{2} p_{C}(x^{2}) & =\frac{1}{2}\bigg(\sum_{i \in C} x^{i}\bigg)^{2}-\frac{1}{2} \sum_{i \in C} x^{2 i}=\sum_{\substack{i_{1},i_2 \in C\\ i_{1}<i_{2}}} x^{i_{1}} \cdot x^{i_{2}} =\sum_{\substack{i_{1},i_2 \in C\\ i_{1}<i_{2}}} x^{i_{1}+i_{2}} \\ & =\sum_{n=0}^{\infty} R_{C}(n) x^{n}=\sum_{n=0}^{\infty} R_{D}(n) x^{n} =\frac{1}{2} p_{D}(x)^{2}-\frac{1}{2} p_{D}(x^{2}), \end{align*} $$

and then, substituting for $p_D(x)$ from (3.1),

$$ \begin{align*} p_{C}(x)^{2}-p_{C}(x^{2})&=\bigg(\frac{1-x^{m+1}}{1-x}-p_{C}(x)-x^{r}\bigg)^{2}-\bigg(\frac{1-x^{2 m+2}}{1-x^{2}}-p_{C}(x^{2})-x^{2 r}\bigg)\\[4pt] &=\bigg(\frac{1-x^{m+1}}{1-x}\bigg)^{2}+p_{C}(x)^{2}+x^{2 r}-2 \frac{1-x^{m+1}}{1-x} \cdot p_{C}(x) \\[4pt] &\quad -2 \frac{1-x^{m+1}}{1-x} \cdot x^{r} +2 p_{C}(x)x^{r}-\frac{1-x^{2 m+2}}{1-x^{2}}+p_{C}\big(x^{2}\big)+x^{2 r}. \end{align*} $$

Therefore,

(3.2) $$ \begin{align} 2 p_{C}(x^{2}) & =\frac{1-x^{2 m+2}}{1-x^{2}}+2 p_{C}(x) \frac{1-x^{m+1}}{1-x}-\bigg(\frac{1-x^{m+1}}{1-x}\bigg)^{2} \nonumber\\[4pt] &\quad +2 x^{r} \frac{1-x^{m+1}}{1-x}-2 p_{C}(x) x^{r}-2 x^{2 r}.\end{align} $$

We first check the necessity for $1\le r\le 5$ .

For $r=1$ , if there is a suitable decomposition $C\cup D=[0,m]\setminus \{ 1 \}$ and $m\ge 4$ , then $0\in C$ and $2,3,4\in D$ . Let $E=m-C$ , $F=m-D$ . Then,

$$ \begin{align*}(E\cap [0,m-2])\cap (F\cap [0,m-2])&=\emptyset,\\ (E\cap [0,m-2])\cup (F\cap [0,m-2])&=[0,m-2].\end{align*} $$

By Lemma 2.3, $R_E(n)=R_F(n)$ for all integers $n\le m-2$ . Further, by Lemma 2.1, ${F\cap [0,m-2]=A\cap [0,m-2]}$ or $B\cap [0,m-2]$ , but this is a contradiction, because $F\cap [0,m-2]$ contains three consecutive integers $m-4$ , $m-3$ and $m-2$ . Hence, the only solution is $m=2$ .

For $r=2,3,4,5$ , the proof is similar. Here we give the details in the case where $r=4$ . Since $0\in C$ , we have $1\in D$ , otherwise $R_C(1)\not =R_D(1)$ . Similarly, we can obtain $2\in D$ , $3\in C$ , $5\in D$ , $6\in C$ , $7\in C$ , $8\in D$ , $9\in D$ , $10\in C$ , $11\in D$ , $12\in C$ , $13\in D$ , and we cannot put $14$ in both C and D. Hence if $m\ge 14$ , there is no C and D. For $m<13$ , we can check only $m=8$ holds and $C=\{0,3,6,7\}$ , $D=\{1,2,5,8\}$ .

Now we assume $r\ge 6$ . First we shall prove that r is even. Suppose that r is odd. Let k be an even integer such that $r<k<2r$ . Then the coefficient of $x^k$ in (3.2) is

(3.3) $$ \begin{align} 2 \chi_{C}\bigg(\frac{k}{2}\bigg)=1+2 \sum_{i \leq k} \chi_{C}(i)-(k+1)+2-2 \chi_{C}(k-r), \end{align} $$

and the coefficient of $x^{k-1}$ in (3.2) is

(3.4) $$ \begin{align}0=0+2 \sum_{i \leq k-1} \chi_{C}(i)-k+2-2 \chi_{C}(k-1-r).\end{align} $$

Calculating ((3.3) and (3.4)) $\times \tfrac 12$ , we have

(3.5) $$ \begin{align} \chi_{C}\bigg(\frac{k}{2}\bigg)=\chi_{C}(k)-\chi_{C}(k-r)+\chi_{C}(k-1-r). \end{align} $$

By Lemma 2.1,

(3.6) $$ \begin{align} C \cap[0, r-1]=A \cap[0, r-1],\end{align} $$

(3.7) $$ \begin{align} D \cap[0, r-1]=B \cap[0, r-1].\end{align} $$

Since $k-1-r$ is even, $k-r<r$ . By (3.6) and the definition of A,

$$ \begin{align*}\chi_{C}(k-r)+\chi_{C}(k-1-r)=1.\end{align*} $$

If $\chi _{C}(k-r)=0, \chi _{C}(k-1-r)=1$ , then by (3.5), $\chi _{C}(k)=0$ and $\chi _{C}({k}/{2})=1$ . If $\chi _{C}(k-r)=1, \chi _{C}(k-1-r)=0$ , then by (3.5), $\chi _{C}(k)=1$ and $\chi _{C}({k}/{2})=0$ . Hence, $\chi _{C}(k-1-r)=\chi _{C}({k}/{2})$ .

Let $k=2 r-2^{i+1}+2$ , where $i \geq 1$ . Then $\tfrac 12k=r+1-2^{i}$ , $k-1-r=r+1-2^{i+1}$ . Hence, $\chi _{C}(r+1-2^{i})=\chi _{C}(r+1-2^{i+1})$ . Therefore,

$$ \begin{align*}\chi_{C}(r+1-2)=\chi_{C}(r+1-4)=\cdots=\chi_{C}(r+1-2^{\lceil\log _{2}(r+1) \rceil-1}), \end{align*} $$

and so

$$ \begin{align*}\chi_{A}(r+1-2)=\chi_{A}(r+1-4)=\cdots=\chi_{A}(r+1-2^{\lceil\log _{2}(r+1)\rceil-1}). \end{align*} $$

By Lemma 2.6, it follows that $r+1=2^{u}-2$ and $\chi _{A}(r+1)=\chi _{A}(r)$ .

Next we shall prove $r\in B$ . Suppose that $r \in A$ . Since $0 \in C$ , $r \notin C$ , by (3.6), it follows that

$$ \begin{align*} R_{C}(r)=R_{C \cap[0, r-1]}(r)=R_{A \cap[0, r-1]}(r)=R_{A \cap[0, r]}(r)-1. \end{align*} $$

Similarly, by (3.7), it follows that

$$ \begin{align*} R_{D}(r)=R_{D \cap[0, r-1]}(r)=R_{B \cap[0, r-1]}(r)=R_{B \cap[0, r]}(r). \end{align*} $$

Noting that

$$ \begin{align*}R_{A \cap[0, r]}(r)=R_{A}(r)=R_{B}(r)=R_{B \cap[0, r]}(r),\end{align*} $$

we have $R_{C}(r) \neq R_{D}(r)$ , which is a contradiction. Hence, $r \in B$ and $r+1 \in B$ , and so $r \notin A$ .

By (3.6) and $r \notin C$ , we have $C \cap [0, r]=A \cap [0, r]$ . Hence,

$$ \begin{align*}R_{C}(r+1)=R_{C \cap[0, r]}(r+1)+\chi_{C}(r+1)=R_{A \cap[0, r]}(r+1)+\chi_{C}(r+1). \end{align*} $$

By (3.7) and $1, r \in B, r \notin D$ ,

$$ \begin{align*}R_{D}(r+1)=R_{B \cap[0, r]}(r+1)-1.\end{align*} $$

Noting that $r,r+1\in B$ ,

$$ \begin{align*}R_{A \cap[0, r]}(r+1)=R_{A \cap[0, r+1]}(r+1), \quad R_{B \cap[0, r]}(r+1)=R_{B \cap[0, r+1]}(r+1).\end{align*} $$

Since

$$ \begin{align*}R_{A \cap[0, r+1]}(r+1)=R_{A}(r+1)=R_{B}(r+1)=R_{B \cap[0, r+1]}(r+1),\end{align*} $$

it follows that $R_{C}(r+1) \neq R_{D}(r+1)$ , which is a contradiction. Therefore, r is not odd.

Suppose that r is even. Take an even integer k with $r \leq k \leq 2 r$ . Then, the coefficient of $x^{k-2}$ in (3.2) is

(3.8) $$ \begin{align} 2 \chi_{C}\bigg(\frac{k-2}{2}\bigg)=1+2 \sum_{i \leq k-2} \chi_{C}(i)-(k-1)+2-2 \chi_{C}(k-2-r), \end{align} $$

and the coefficient of $x^{k-1}$ in (3.2) is

(3.9) $$ \begin{align} 0=0+2 \sum_{i \leq k-1} \chi_{C}(i)-k+2-2 \chi_{C}(k-1-r). \end{align} $$

Calculating ((3.8) and (3.9)) $\times \tfrac 12$ , we obtain

$$ \begin{align*}\chi_{C}\bigg(\frac{k-2}{2}\bigg)=1-\chi_{C}(k-1)-\chi_{C}(k-2-r)+\chi_{C}(k-1-r).\end{align*} $$

By Lemma 2.3, $k-1-r<r$ and $k-2-r$ is even. By (3.6) and the definition of A,

$$ \begin{align*}\chi_{C}(k-2-r)+\chi_{C}(k-1-r)=1.\end{align*} $$

If $\chi _{C}(k-2-r)=0$ and $\chi _{C}(k-1-r)=1$ , then $\chi _{C}(k-1)=1, \chi _{C}({(k-2)}/{2})=1$ . If $\chi _{C}(k-2-r)=1$ , $\chi _{C}(k-1-r)=0$ , then $\chi _{C}(k-1)=0, \chi _{C}({(k-2)}/{2})=0$ . From these two cases, $\chi _{C}(k-1-r)=\chi _{C}({(k-2)}/{2})$ . Take

$$ \begin{align*}k=2 r-2^{i+1}, \quad i=0,1,\ldots,\lceil \log_2(r-1)\rceil-2.\end{align*} $$

Then $\tfrac 12(k-2)=r-1-2^{i}$ giving $k-1-r=r-1-2^{i+1}$ and so $\chi _{C}(r-1-2^{i})=\chi _{C}(r-1-2^{i+1})$ . Hence,

$$ \begin{align*}\chi_{C}(r-1-1)=\chi_{C}(r-1-2)=\cdots=\chi_{C}(r-1-2^{\lceil \log _{2}(r-1)\rceil -1}). \end{align*} $$

By Lemma 2.5, $r-1=2^{\lceil \log _{2}(r-1)\rceil }-1$ . Write $l=\left\lceil \log _{2}(r-1)\right\rceil +1$ . Then $r=2^{l-1}$ . Also $[0,2r]\subseteq [0,m]$ because $r\le {m}/{2}$ . By Lemma 2.1 and the sufficiency of Theorem 1.3,

$$ \begin{align*}C \cap[0,2 r]=A_{l-1} \cup (2^{l-1}+1+B_{l-1} ), \quad D \cap[0,2 r]=B_{l-1} \cup (2^{l-1}+1+A_{l-1}). \end{align*} $$

Next we shall prove $m=2r$ . First, we prove $m<3 \cdot 2^{l-1}=2^{l-1}+2^{l}$ . Suppose that $m \geq 3 \cdot 2^{l-1}$ . First we shall prove the following structure of C and D:

$$ \begin{align*} &C \cap[0,3 \cdot 2^{l-1}]=A_{l-1} \cup(2^{l-1}+1+B_{l-1}) \cup(2^{l}+1+B_{l-1}) := E,\\ &D \cap[0,3 \cdot 2^{l-1}]=B_{l-1} \cup(2^{l-1}+1+A_{l-1}) \cup(2^{l}+1+A_{l-1}) := F. \end{align*} $$

If $n \leq 2^{l}$ , then clearly $R_{E}(n)=R_{F}(n)$ . Now we assume that $2^{l}<n \leq 3 \cdot 2^{l-1}$ . It follows that

$$ \begin{align*}\begin{aligned} R_{E}(n) &=|\{(c, c^{\prime}): c \in A_{l-1}, c^{\prime} \in 2^{l-1}+1+B_{l-1}, c+c^{\prime}=n\}| \\ &\quad +|\{(c, c^{\prime}): c \in A_{l-1}, c^{\prime} \in 2^{l}+1+B_{l-1}, c+c^{\prime}=n\}| \\ &\quad +|\{(c, c^{\prime}): c<c^{\prime}, c, c^{\prime} \in 2^{l-1}+1+B_{l-1}, c+c^{\prime}=n\}|\\ &=|\{(c, c^{\prime}): c \in A_{l-1}, c^{\prime} \in B_{l-1}, c+c^{\prime}=n-(2^{l-1}+1)\}| \\ &\quad +|\{(c, c^{\prime}): c \in A_{l-1}, c^{\prime} \in B_{l-1}, c+c^{\prime}=n-(2^{l}+1) |+R_{B_{l-1}}(n-2(2^{l-1}+1))\end{aligned}\end{align*} $$

and

$$ \begin{align*}\begin{aligned} R_{F}(n) &=|\{(d, d^{\prime}): d \in B_{l-1}, d^{\prime} \in 2^{l-1}+1+A_{l-1}, d+d^{\prime}=n\}| \\ &\quad +|\{(d, d^{\prime}): d \in B_{l-1}, d^{\prime} \in 2^{l}+1+A_{l-1}, d+d^{\prime}=n\}| \\ &\quad +|\{(d, d^{\prime}): d<d^{\prime}, d, d^{\prime} \in 2^{l-1}+1+B_{l-1}, d+d^{\prime}=n\}| \\ &=|\{(d, d^{\prime}): d \in B_{l-1}, d^{\prime} \in A_{l-1}, d+d^{\prime}=n-(2^{l-1}+1)\}| \\ &\quad +|\{(d, d^{\prime}): d \in B_{l-1}, d^{\prime} \in A_{l-1}, d+d^{\prime}=n-(2^{l}+1) | +R_{A_{l-1}}(n-2(2^{l-1}+1)). \end{aligned} \end{align*} $$

By Lemma 2.7, $R_{A_{l-1}}(m)=R_{B_{l-1}}(m)$ for any positive integers m and so $R_{E}(n)=R_{F}(n)$ . By Lemma 2.1, $C\cap [0,3\cdot 2^{l-1}]=E$ and $D\cap [0,3\cdot 2^{l-1}]=F$ .

Next we shall prove that $m\ge 3 \cdot 2^{l-1}$ is impossible. If $m>3 \cdot 2^{l-1}$ then, since $0\in C$ ,

$$ \begin{align*}& R_{C}(3 \cdot 2^{l-1}+1) \\&\quad=\chi_{C}(3 \cdot 2^{l-1}+1) +|\{(c, c^{\prime}): c \in A_{l-1}, c^{\prime} \in 2^{l}+1+B_{l-1}, c+c^{\prime}=3 \cdot 2^{l-1}+1\}| \\ &\qquad +|\{(c, c^{\prime}): c<c^{\prime}, c, c^{\prime} \in 2^{l-1}+1+B_{l-1}, c+c^{\prime}=3 \cdot 2^{l-1}+1\}| \\ &\quad=\chi_{C}(3 \cdot 2^{l-1}+1)+|\{(c, c^{\prime}): c \in A_{l-1}, c^{\prime} \in B_{l-1},c+c^{\prime}=2^{l-1}\}| +R_{B_{l-1}}(2^{l-1}-1). \end{align*} $$

Similarly,

$$ \begin{align*}R_{D}(3 \cdot 2^{l-1}+1)=|\{(d, d^{\prime}): d \in B_{l-1}, d^{\prime} \in A_{l-1}, d+d^{\prime}=2^{l-1}\}|+R_{A_{l-1}}(2^{l-1}-1).\end{align*} $$

By Lemma 2.7, $R_{A_{l-1}}(2^{l-1}-1)=R_{B_{l-1}}(2^{l-1}-1)$ so $R_{C}(3 \cdot 2^{l-1}+1)=R_{D}(3 \cdot 2^{l-1}+1)$ if and only if $\chi _{C}(3 \cdot 2^{l-1}+1)=0$ , that is, $3 \cdot 2^{l-1}+1 \in D$ .

Since $1,3 \cdot 2^{l-1}+1,2^{l}+1,2^{l-1}+1 \in D$ and

$$ \begin{align*}3 \cdot 2^{l-1}+2=1+(1+3 \cdot 2^{l-1})=(2^{l-1}+1)+(2^{l}+1),\end{align*} $$

it follows that

$$ \begin{align*} R_{D}(3 \cdot 2^{l-1}+2) & =1+1+|\{(d, d^{\prime}): d \in B_{l-1}, d^{\prime} \in 2^{l}+1+A_{l-1}, d+d^{\prime}=3 \cdot 2^{l-1}+2\}| \\ &\quad +|\{(d, d^{\prime}): d<d^{\prime}, d, d^{\prime} \in 2^{l-1}+1+A_{l-1}, d+d^{\prime}=3 \cdot 2^{l-1}+2\}|\\ &=2+|\{(d, d^{\prime}): d \in B_{l-1}, d^{\prime} \in A_{l-1}, d+d^{\prime}=2^{l-1}+1\}|+R_{A_{l-1}}(2^{l-1}). \end{align*} $$

Similarly,

$$ \begin{align*} R_{C}(3 \cdot 2^{l-1}+2) & =\chi_{C}(3 \cdot 2^{l-1}+2)+|\{(c, c^{\prime}): c \in A_{l-1}, c^{\prime} \in B_{l-1}, c+c^{\prime}=2^{l-1}+1\}| \\ &\quad +R_{B_{l-1}}(2^{l-1}). \end{align*} $$

Hence, $R_{C}(3 \cdot 2^{l-1}+2) \neq R_{D}(3 \cdot 2^{l-1}+2)$ , which is a contradiction.

If $m=3 \cdot 2^{l-1}$ , by $3 \cdot 2^{l-1}+2=(2^{l-1}+1)+(2^{l}+1)$ , then

$$ \begin{align*} R_{C} (3 \cdot 2^{l-1}+2 ) & = | \{ (c, c^{\prime} ): c \in A_{l-1}, c^{\prime} \in B_{l-1}, c<c^{\prime}, c+c^{\prime}=2^{l-1}+1 |+R_{B_{l-1}} (2^{l-1} ) , \\ R_{D} (3 \cdot 2^{l-1}+2 ) & =1+ | \{ (d, d^{\prime} ): d \in B_{l-1}, d^{\prime} \in A_{l-1}, d<d^{\prime}, d+d^{\prime}=2^{l-1}+1 | \\ &\quad +R_{A_{l-1}}(2^{l-1}). \end{align*} $$

Hence, $R_{C}(3 \cdot 2^{l-1}+2) \neq R_{D}(3 \cdot 2^{l-1}+2)$ , which is a contradiction.

Therefore, $m<3 \cdot 2^{l-1}$ . Now we have

$$ \begin{align*} C & =A_{l-1} \cup(2^{l-1}+1+B_{l-1}) \cup(2^{l}+1+(B_{l-1} \cap[0, m-(2^{l}+1)])), \\ D & =B_{l-1} \cup(2^{l-1}+1+A_{l-1}) \cup(2^{l}+1+(A_{l-1} \cap[0, m-(2^{l}+1)])). \end{align*} $$

Next we prove $m=2^{l}$ . Suppose that $m>2^{l}$ .

If $m-(2^{l}+1) \neq 2^{k}-1$ , where k is a nonnegative integer, then by Lemma 2.8, there exists an integer u satisfying $m-(2^{l}+1)<u<2[m-(2^{l}+1)]$ such that

(3.10) $$ \begin{align} R_{A \cap[0, m-(2^{l}+1)]}(u)=R_{A_{l-1} \cap[0, m-(2^{l}+1)]}(u) \neq R_{B_{l-1} \cap[0, m-(2^{l}+1)]}(u)=R_{B \cap[0, m-(2^{l}+1)]}(u). \end{align} $$

Since $m+(2^{l}+1)<u+2(2^{l}+1)<2 m$ , it follows that

$$ \begin{align*} R_{C}(2(2^{l}+1)+u) &=R_{2^{l}+1+(B_{l-1} \cap [0, m-(2^{l}+1)])} (2(2^{l}+1)+u)\\ &=R_{B_{l-1} \cap [0, m-(2^{l}+1)]}(u)=R_{B \cap [0, m-(2^{l}+1)]}(u). \end{align*} $$

Similarly,

$$ \begin{align*} R_{D}(2(2^{l}+1)+u) & =R_{2^{l}+1+(A_{l-1} \cap [0, m-(2^{l}+1)])} (2(2^{l}+1)+u)\\ &=R_{A_{l-1} \cap [0, m-(2^{l}+1)]}(u)=R_{A \cap [0, m-(2^{l}+1)]}(u). \end{align*} $$

Since $R_{C}(2(2^{l}+1)+u)=R_{D}(2(2^{l}+1)+u)$ , it follows that $R_{A \cap [0, m-(2^{l}+1)]}(u)=R_{B \cap [0, m (2^{l}+1)]}(u)$ , which is a contradiction with (3.10).

Now we suppose that $m-(2^l+1)=2^k-1$ . Noting that $m<3\cdot 2^{l-1}$ , we have $k<l-1$ . Hence,

$$ \begin{align*} &C=A_{l-1} \cup (2^{l-1}+1+B_{l-1} ) \cup (2^{l}+1+B_{k} ), \\ &D=B_{l-1} \cup (2^{l-1}+1+A_{l-1} ) \cup (2^{l}+1+A_{k} ). \end{align*} $$

If $k=0$ , then $2^{l}+1 \in D$ . Now we divide into the following two cases.

Case 1: $2^{l-1}-1\in A_{l-1}$ . That is, $2^l\in D$ . Hence, $2^{l+1}+1=(2^l+1)+2^l$ and so $R_{C}(2^{l+1}+1)=0$ , $R_{D}(2^{l+1}+1)=1$ , which is a contradiction.

Case 2: $2^{l-1}-1 \in B_{l-1}$ . That is, $2^{l} \in C$ . Hence, $2^{l-1}-2 \in A_{l-1}$ and so $2^{l}-1 \in D$ . Since $2^{l+1}=(2^{l}+1)+(2^{l}-1)$ , it follows that $R_{C}(2^{l+1})=0$ , $R_{D}(2^{l+1})=1$ , which is a contradiction.

Therefore, we can assume that $k>0$ . Let $C^{\prime }=2^{l}+2^{k}-C$ , $D^{\prime }=2^{l}+2^{k}-D$ .

Case 1: $2\nmid l-1$ , $2\nmid k$ . It follows that

$$ \begin{align*} &C^{\prime}=A_{k} \cup (2^{k}+A_{l-1}) \cup (2^{l-1}+2^{k}+1+B_{l-1}),\\[-1.5pt] &D^{\prime}=B_{k} \cup (2^{k}+B_{l-1}) \cup (2^{l-1}+2^{k}+1+A_{l-1}). \end{align*} $$

Case 2: $2\nmid l-1$ , $2\mid k$ . Then,

$$ \begin{align*} &C^{\prime}=B_{k} \cup (2^{k}+A_{l-1}) \cup (2^{l-1}+2^{k}+1+B_{l-1}),\\ &D^{\prime}=A_{k} \cup (2^{k}+B_{l-1}) \cup (2^{l-1}+2^{k}+1+A_{l-1}). \end{align*} $$

Case 3: $2\mid l-1$ , $2\nmid k$ . Then,

$$ \begin{align*} &C^{\prime}=A_{k} \cup (2^{k}+B_{l-1} ) \cup (2^{l-1}+2^{k}+1+A_{l-1} ), \\[4pt] &D^{\prime}=B_{k} \cup (2^{k}+A_{l-1} ) \cup (2^{l-1}+2^{k}+1+B_{l-1} ). \end{align*} $$

Case 4: $2\mid l-1$ , $2\mid k$ . Then,

$$ \begin{align*} &C^{\prime}=B_{k} \cup(2^{k}+B_{l-1}) \cup(2^{l-1}+2^{k}+1+A_{l-1}),\\[4pt] &D^{\prime}=A_{k} \cup(2^{k}+A_{l-1}) \cup(2^{l-1}+2^{k}+1+B_{l-1}). \end{align*} $$

Hence, $C^{\prime } \cup D^{\prime }= [0,2^{l}+2^{k} ]\setminus \{2^{l-1}+2^{k} \}$ , $C^{\prime } \cap D^{\prime }=\emptyset $ . By Lemma 2.3, it follows that $R_{C^{\prime }}(n)=R_{D^{\prime }}(n)$ for all positive integers n. By Lemma 2.1, it suffices to consider the following two cases.

Case I: $C^{\prime } \cap [0,2^{l-1}+2^{k}-1 ]=A \cap [0,2^{l-1}+2^{k}-1 ]$ and $D^{\prime } \cap [0,2^{l-1}+2^{k}-1 ]=B \cap [0,2^{l-1}+2^{k}-1 ]$ .

Case II: $C^{\prime } \cap [0,2^{l-1}+2^{k}-1 ]=B \cap [0,2^{l-1}+2^{k}-1 ]$ and $D^{\prime } \cap [0,2^{l-1}+2^{k}-1 ]=A \cap [0,2^{l-1}+2^{k}-1 ]$ .

If Case 1 and Case I hold, then $C^{\prime } \cap [0,2^{k}-1]=A \cap [0,2^{k}-1]=A_{k}.$ By the property of A, we have $C^{\prime } \cap [2^{k}, 2^{k+1}-1]=2^{k}+B_{k}.$ Then, by Case 1, we have ${C^{\prime } \cap [2^{k}, 2^{k+1}-1]=2^{k}+A_{k}}$ , which is a contradiction.

If Case 1 and Case II hold, then $C^{\prime } \cap [0,2^{k}-1]=B \cap [0,2^{k}-1]=B_{k}.$ By Case 1, we have $C^{\prime } \cap [0,2^{k}-1]=A_{k}$ , which is a contradiction.

If Case 2 and Case I hold, then $C^{\prime } \cap [0,2^{k}-1]=A_{k}$ . Then, by Case 2, we have ${C^{\prime } \cap [0,2^{k}-1]=B_{k}}$ , which is a contradiction.

If Case 2 and Case II hold, then $k<l-1$ and so $2^{k}+1<2^{l-1}-1$ . By the property of A, it follows that $2^{k}+1 \in A_{l-1}$ and then $2^{k}+(2^{k}+1) \in 2^{k}+A_{l-1} \subseteq C^{\prime }$ . Hence, $2^{k}+(2^{k}+1) \in C^{\prime }$ . By Case II, $2^{k}+(2^{k}+1) \in B$ . But, ${2^{k}+ (2^{k}+1)=2^{k+1}+1 \in A}$ , which is a contradiction.

If Case 3 and Case I hold, then ${2^{k}+(2^{k}+1) \in 2^{k}+ A_{l-1} \subseteq D^{\prime }}$ because we have $2^k+1\in A_{l-1}$ . By Case I, $2^{k}+(2^{k}+1) \in B$ . However, by the property of A, ${2^{k}+(2^{k}+1)=2^{k+1}+1 \in A}$ , which is a contradiction.

If Case 3 and Case II hold, then $C^{\prime } \cap [0,2^{k}-1]=B \cap [0,2^{k}-1]=B_{k}$ . By Case 3, $C^{\prime } \cap [0,2^{k}-1 ]=A_{k}$ , which is a contradiction.

If Case 4 and Case I hold, then $C^{\prime } \kern-1pt\cap\kern-1pt [0,2^{k}-1]\kern-1pt = \kern-1pt A_{k}$ . By Case 4, $C^{\prime } \kern-1pt\cap [0,2^{k}-\kern-1pt 1]\kern-1pt = \kern-1pt B_{k}$ , which is a contradiction.

If Case 4 and Case II hold, then $C^{\prime } \cap [0,2^{k}-1]=B \cap [0,2^{k}-1]=B_{k}.$ By the property of B, $C^{\prime } \cap [2^{k}, 2^{k+1}-1]=2^{k}+A_{k}.$ By Case 4, $C^{\prime } \cap [2^{k}, 2^{k+1}-1]=2^{k}+B_{k}$ , which is a contradiction.

Therefore, $m=2r$ .