1 Introduction
Let
$\mathbb {N}$
be the set of all nonnegative integers. For a given set
$S\subset \mathbb {N}$
, define the additive representation function
$R_S:\mathbb {N}\to \mathbb {N}$
to be
Erdős, Sárközy and Sós initiated the study of representation functions for general sequences in a series of papers which led to much more research (see their survey paper [Reference Erdős, Sárközy and Sós6]).
Sárközy asked whether there exist two sets with infinite symmetric difference and coinciding representation functions. Dombi [Reference Dombi5] answered Sárközy’s question affirmatively, showing that the Thue–Morse sequence and its complement have coinciding representation functions. This promoted extensive research on partitions of sets with coinciding representation functions (see, for example, [Reference Chen and Chen1, Reference Chen and Tang3, Reference Chen and Wang4, Reference Qu10]).
Let A be the set of nonnegative integers which have an even number of 1’s in their binary representation and
$B=\mathbb {N}\backslash A$
. For each integer
$l\geq 1$
, set
$A_l=A\cap [0,2^l-1]$
and
$B_l=B\cap [0,2^l-1]$
.
In [Reference Kiss and Sándor8], Kiss and Sándor proved the following theorem.
Theorem 1.1. Let
$C,D\subset \mathbb {N}$
,
$m\geq 2$
be such that
$C\cup D=[0,m]$
,
$C\cap D=\{r\}$
with
$0<r<m$
and
$0\in C$
. Then,
$R_C(n)=R_D(n)$
holds for all
$n\in \mathbb {N}$
if and only if
$m=2^l-2$
,
$l\geq 2$
,
$r=2^{l-1}-1$
and
$C=A_{l-1}\cup (B_{l-1}+r), D=B_{l-1}\cup (A_{l-1}+r)$
.
In [Reference Jiao, Sándor, Yang and Zhou7], Jiao et al. proved the following result.
Theorem 1.2. Let
$C,D\subset \mathbb {N}$
,
$m\geq 3$
be such that
$C\cup D=[0,m]\backslash \{r\}$
, with
$0<r<m$
and
$0\in C$
. Then,
$R_C(n)=R_D(n)$
holds for all
$n\in \mathbb {N}$
if and only if
$m=2^l$
,
$l\geq 2$
,
$r=2^{l-1}$
and
$C=A_{l-1}\cup (B_{l-1}+r+1), D=B_{l-1}\cup (A_{l-1}+r+1)$
.
Theorems 1.1 and 1.2 settled two problems posed in [Reference Chen and Lev2]. The next step is to characterise finite sets
$C,D\subset \mathbb {N}$
with coinciding representation functions and
${C\cup D=[0,m]}$
,
$C\cap D=\{r_1,r_2\}$
, or
$C\cup D=[0,m]\backslash \{r_1,r_2\}$
. The complexity seems to rise tremendously. In [Reference Sun and Pan12], Sun and Pan obtained some partial results in the former case, and finally in [Reference Sun11], Sun completed the characterisation for
$C\cup D=[0,m]$
and
$C\cap D=\{r_1,r_2\}$
.
Theorem 1.3. Let
$C,D\subset \mathbb {N}$
,
$m\geq 3$
, be such that
$C\cup D=[0,m]$
,
$C\cap D=\{r_1,r_2\}$
, with
$0<r_1<r_2<m$
and
$0\in C$
. Then,
$R_C(n)=R_D(n)$
holds for all
$n\in \mathbb {N}$
if and only if
$m=2^{2l+2}-3$
,
$l\geq 1$
, and one of the following two cases holds:
-
(1)
$r_1=2^{2l+1}-2$
,
$r_2=2^{2l+1}-1$
and
$$ \begin{align*}C=A_{2l+1}\cup (B_{2l+1}+2^{2l+1}-2),\quad D=B_{2l+1}\cup (A_{2l+1}+2^{2l+1}-2);\end{align*} $$
-
(2)
$r_1=2^{2l}-1$
,
$r_2=2^{2l+1}+2^{2l}-2$
and
$$ \begin{align*} C & =A_{2l}\cup(B_{2l}+2^{2l}-1)\cup(2^{2l+1}+B_{2l}\cup(A_{2l}+2^{2l}-1)),\\ D & =B_{2l}\cup(A_{2l}+2^{2l}-1)\cup(2^{2l+1}+A_{2l}\cup(B_{2l}+2^{2l}-1)). \end{align*} $$
The main purpose of this paper is to characterise pairs of sets
$C,D \subset \mathbb {N}$
with coinciding representation functions and
$C\cup D=[0,m]\backslash \{r_1,r_2\}$
. We give a complete solution to this problem (see Theorem 1.6), taking a different approach which is also applicable in other cases.
In search of the answer, a natural question is to characterise all pairs of sets
$(C,D)$
with coinciding representation functions. Kiss and Sándor [Reference Kiss and Sándor9] proposed a conjectural structure for such pairs of sets
$C,D$
. We will rephrase their conjecture more generally in terms of multisets.
In what follows, we consider a multiset S of nonnegative integers. Each integer
$n\in \mathbb {N}$
appears in S with some multiplicity
$M_S(n)\in \mathbb {N}$
. A multiset S may be identified with its multiplicity function
$M_S:\mathbb {N}\to \mathbb {N}$
. An ordinary set
$S\subset \mathbb {N}$
has its multiplicity function
$M_S:\mathbb {N}\to \{0,1\}$
, which is nothing but its characteristic function. The cardinality of S is given by
$|S|=\sum _{n\geq 0} M_S(n)$
and S is called a finite multiset if
$|S|$
is finite.
We may enumerate all elements of S (with multiplicity) in ascending order, say
$S=\{a_1\leq a_2\leq a_3\leq \cdots \}$
, and define the representation function
for
$n\in \mathbb {N}$
. Questions like those above can be asked for multisets, namely characterising pairs of multisets of nonnegative integers
$C,D$
such that
$R_C(n)=R_D(n)$
holds for all
$n\in \mathbb {N}$
.
Since a simultaneous translation of C and D preserves the property that they have identical representation functions, it suffices to consider the case
$0\in C\cup D$
. Now, we describe the conjectural structure for such C and D.
Let
$X=\{x_1,x_2,\ldots \}$
be a (finite or infinite) multiset of positive integers. The Hilbert cube of X is defined to be the multiset
$$ \begin{align*}H(X)=\bigg\{\!\sum_{i} \varepsilon_ix_i: \varepsilon_i\in\{0,1\},\sum_{i}\varepsilon_i<\infty\bigg\}.\end{align*} $$
The elements of
$H(X)$
are counted with multiplicity; the multiplicity of
$a\in H(X)$
is equal to the number of ways in which we can write
$a=\sum _{i}\varepsilon _i x_i$
. Define the even part
$H_0(X)$
and the odd part
$H_1(X)$
to be
$$ \begin{align*}H_k(X)=\bigg\{\!\sum_{i}\varepsilon_ix_i\in H(X): \sum_{i} \varepsilon_i\equiv k\pmod 2\bigg\},\quad k=0,1.\end{align*} $$
It is not hard to verify that
$R_{H_0(X)}(n)=R_{H_1(X)}(n)$
holds for all
$n\in \mathbb {N}$
. We conjecture that the reverse is also true.
Conjecture 1.4. Let
$C,D$
be distinct nonempty multisets with
$0\in C$
. Then,
${R_C(n)=R_D(n)}$
holds for all
$n\in \mathbb {N}$
if and only if
$C=H_0(X)$
and
$D=H_1(X)$
for some multiset X of positive integers.
When C and D are finite multisets, we show that the problem has a close connection to cyclotomic polynomials. Recall that the nth cyclotomic polynomial
$\Phi _{n}(x)$
is
$$ \begin{align*}\Phi_n(x)=\prod_{\begin{subarray}{c}1\leq j\leq n\\ \gcd(j,n)=1\end{subarray}}(x-{e}^{{2\pi ij}/{n}}),\end{align*} $$
which is a monic irreducible polynomial in
$\mathbb {Z}[x]$
, and
$\deg (\Phi _n(x))=\varphi (n)$
(the Euler totient function).
The following result is our starting point to tackle the problem.
Theorem 1.5. Let
$C,D$
be two distinct nonempty finite multisets with identical representation functions. Assume that
$0\in C\cup D$
and
$\max C\geq \max D$
. Then, the polynomials
$$ \begin{align*} S(x)=\sum_{n=0}^{\infty}(M_C(n)+M_D(n))x^n \quad\text{and}\quad T(x)=\sum_{n=0}^{\infty}(M_C(n)-M_D(n))x^n \end{align*} $$
have the following structure:
$$ \begin{align*} S & =\Phi_{2^{\alpha_1}\beta_1}\Phi_{2^{\alpha_2}\beta_2}\cdots\Phi_{2^{\alpha_k}\beta_k},\\ T & = \bigg(\prod_{j=0}^{\alpha_1-1}\Phi_{2^j\beta_1}\bigg)\bigg(\prod_{j=0}^{\alpha_2-1}\Phi_{2^j\beta_2}\bigg)\cdots\bigg(\prod_{j=0}^{\alpha_k-1}\Phi_{2^j\beta_k}\bigg), \end{align*} $$
where
$\alpha _1,\alpha _2,\ldots ,\alpha _k,\beta _1,\beta _2,\ldots ,\beta _k$
are positive integers and
$2\nmid \beta _1\beta _2\cdots \beta _k$
.
The complete characterisation for
$C,D$
with identical representation functions and
$C\cup D=[0,m]\backslash \{r_1,r_2\}$
is given in the following theorem.
Theorem 1.6. Let
$C,D$
be two nonempty sets of nonnegative integers, such that
${C\cup D=[0,m]\backslash \{r_1,r_2\}}$
,
$m\geq 6$
,
$0<r_1<r_2<m$
and
$0\in C$
. Then,
$R_C(n)=R_D(n)$
holds for all
$n\in \mathbb {N}$
if and only if
$m=2^{l+1}+1$
,
$l\geq 2$
and
$C=H_0(X)$
,
$D=H_1(X)$
for one of the following three cases:
-
(1)
$r_1=2^l$
,
$r_2=2^l+1$
,
$X=\{2^0,2^1,\ldots ,2^{l-1},2^l+2\}$
; -
(2)
$r_1=1$
,
$r_2=2^{l+1}$
,
$X=\{2^1,2^2,\ldots ,2^l,3\}$
; -
(3)
$r_1=2^{l-1}$
,
$r_2=2^l+2^{l-1}+1$
,
$X=\{2^0,2^1,\ldots ,2^{l-2},2^{l-1}+1,2^l+1\}$
.
Theorems 1.5 and 1.6 will be proved in the next two sections.
2 Proof of Theorem 1.5
Throughout this section, C and D are assumed to be two distinct nonempty finite multisets of nonnegative integers with identical representation functions,
$0\in C\cup D$
and
$\max C\geq \max D$
.
Lemma 2.1. We have
$|C|=|D|$
.
Proof. Since
$\sum _{n\geq 0}R_C(n)=\binom {|C|}{2}$
and
$\sum _{n\geq 0}R_D(n)=\binom {|D|}{2}$
, we have
$\binom {|C|}{2}=\binom {|D|}{2}$
, and hence
$|C|=|D|$
.
Write
$C=\{c_1\leq c_2\leq \cdots \leq c_r\}$
and
$D=\{d_1\leq d_2\leq \cdots \leq d_r\}$
.
Lemma 2.2. We have
$c_1\neq d_1$
and
$c_r\neq d_r$
.
Proof. As
$C\neq D$
, there exists an index k such that
$c_k\neq d_k$
. Choose the smallest such k. If
$k>1$
, then
$c_i=d_i$
for
$1\leq i<k$
. Suppose
$d_k>c_k$
(the other case is similar). We show that
$R_C(c_1+c_k)\neq R_D(c_1+c_k)$
, which leads to a contradiction. Consider the following sets:
$$ \begin{align*}X=\{(i,j) : i<j,\, c_i+c_j=c_1+c_k\} \quad\text{and}\quad Y=\{(i,j) : i<j,\, d_i+d_j=c_1+c_k\}.\end{align*} $$
For
$(i,j)\in Y$
, since
$d_i\geq c_1$
and
$d_j\leq c_k$
, it follows that
$j<k$
; hence,
$d_i=c_i$
and
$d_j=c_j$
, and so
$(i,j)\in X$
. However,
$(1,k)\in X$
but
$(1,k)\not \in Y$
; thus,
$Y\subsetneq X$
and
$$ \begin{align*}R_D(c_1+c_k)=|Y|<|X|=R_C(c_1+c_k).\end{align*} $$
This proves that
$k=1$
, that is,
$c_1\neq d_1$
.
Let
$N=\max (C\cup D)$
and set
$$ \begin{align*}\widetilde{C}=\{N-c_r\leq N-c_{r-1}\leq\cdots \leq N-c_1\},\end{align*} $$
$$ \begin{align*}\widetilde{D}=\{N-d_r\leq N-d_{r-1}\leq\cdots \leq N-d_1\}.\end{align*} $$
Then,
$\widetilde {C}$
and
$\widetilde {D}$
are multisets of nonnegative integers which also have identical representation functions since
$R_{\widetilde {C}}(n)=R_C(2N-n)=R_D(2N-n)=R_{\widetilde {D}}(n)$
. By the above arguments, we conclude that
$N-c_r=\min \widetilde {C}\neq \min \widetilde {D}=N-d_r$
, that is,
$c_r\neq d_r$
.
Let
$$ \begin{align*} f_C(x)=\sum_{i=1}^{r} x^{c_i}=\sum_{n\geq 0} M_C(n)x^n \quad\text{and}\quad f_D(x)=\sum_{i=1}^r x^{d_i}=\sum_{n\geq 0}M_D(n)x^n \end{align*} $$
be the generating functions of C and D, respectively. Then,
$$ \begin{align*} f_C(x)^2-f_C(x^2)=2\sum_{n\geq 0} R_C(n)x^n \quad\text{and}\quad f_D(x)^2-f_D(x^2)=2\sum_{n\geq 0} R_D(n)x^n. \end{align*} $$
It follows that C and D have identical representation functions if and only if
$$ \begin{align*}f_C(x)^2-f_C(x^2)=f_D(x)^2-f_D(x^2).\end{align*} $$
Set
$T(x)=f_C(x)-f_D(x)$
and
$S(x)=f_C(x)+f_D(x)$
. It follows that
$$ \begin{align*}T(x)S(x)=T(x^2).\end{align*} $$
Since
$C,D$
are finite multisets,
$f_C,f_D,T$
and S are polynomials with integer coefficients.
Several elementary facts about cyclotomic polynomials are needed. We give a brief proof of these results.
Lemma 2.3. We have
$$ \begin{align*} \Phi_n(x^2)=\begin{cases} \Phi_n(x)\Phi_{2n}(x) & \text{if } 2\nmid n,\\ \Phi_{2n}(x) & \text{if } 2\mid n. \end{cases} \end{align*} $$
Proof. Set
$\eta _n={e}^{2\pi {i}/n}$
. Then,
$\Phi _n(x)$
is the minimal polynomial of
$\eta _n$
over
$\mathbb {Q}$
and
$\eta _{2n}$
, being a square root of
$\eta _n$
, is a root of
$\Phi _n(x^2)$
. Hence,
$\Phi _{2n}(x)\mid \Phi _n(x)$
.
If n is even,
$\deg ( \Phi _{2n}(x))=\varphi (2n)=2\varphi (n)=\deg (\Phi _n(x^2))$
, and thus,
$\Phi _n(x^2)=\Phi _{2n}(x)$
.
If n is odd,
$\eta _n^2$
is also a primitive nth root of unity and so
$\eta _n$
is a root of
$\Phi _n(x^2)$
. Therefore,
$\Phi _n(x)\mid \Phi _n(x^2)$
. Again by comparing the degrees,
$$ \begin{align*}\deg(\Phi_n(x^2))=2\varphi(n)=\deg(\Phi_n(x))+\deg(\Phi_{2n}(x))\end{align*} $$
and we deduce that
$\Phi _n(x^2)=\Phi _n(x)\Phi _{2n}(x)$
.
Lemma 2.4. We have
$$ \begin{align*}\Phi_n(1)=\begin{cases} 0 &\text{if } n=1,\\ p & \text{if } n=p^{\alpha}\,\text{ with } p \text{ prime and } \alpha>0, \\ 1 & \text{otherwise}. \end{cases} \end{align*} $$
Proof. Clearly,
$\Phi _1(1)=0$
since
$\Phi _1(x)=x-1$
. For
$n=p^{\alpha }$
where p is a prime and
$\alpha \in \mathbb {Z}_{>0}$
, it is well known that
$\Phi _{p^{\alpha }}(x)=x^{p^{\alpha -1}(p-1)}+x^{p^{\alpha -1}(p-2)}+\cdots +x^{p^{\alpha -1}}+1$
and so
$\Phi _{p^{\alpha }}(1)=p$
.
Assume that n has at least two distinct prime divisors. Substituting
$x=1$
in
$$ \begin{align*}1+x+x^2+\cdots +x^{n-1}=\frac{x^n-1}{x-1}=\prod_{\begin{subarray}{c}d\mid n\\ d>1\end{subarray}}\Phi_d(n),\end{align*} $$
gives
$$ \begin{align*}n=\prod_{\begin{subarray}{c}d\mid n\\ d>1\end{subarray}}\Phi_d(1)=\prod_{p^{\alpha}\mid n}\Phi_{p^{\alpha}}(1)\prod_{\begin{subarray}{c}d\mid n\\ \omega(d)\geq 2\end{subarray}}\Phi_d(1)=\prod_{p^{\alpha}\mid n}p\prod_{\begin{subarray}{c}d\mid n\\ \omega(d)\geq 2\end{subarray}}\Phi_d(1)=n\prod_{\begin{subarray}{c}d\mid n\\ \omega(d)\geq 2\end{subarray}}\Phi_d(1),\end{align*} $$
where
$\omega (d)$
denotes the number of distinct prime divisors of d. Since
$\Phi _d(1)$
is an integer, by pairing up conjugate primitive roots of unity, we see that
$$ \begin{align*}\Phi_d(1)=\prod_{\begin{subarray}{c} 1\leq j\leq d\\ \gcd(j,d)=1 \end{subarray}}(1-\eta_d^j)\geq 0,\end{align*} $$
so that
$\Phi _d(1)$
is a nonnegative integer. It follows that
$\Phi _d(1)=1$
for every
$d\mid n$
with
$\omega (d)\geq 2$
. In particular,
$\Phi _n(1)=1$
.
Lemma 2.5.
$\Phi _n(x)$
is reciprocal for
$n\geq 2$
, that is,
$\Phi _n(x)=x^{\varphi (n)}\Phi _n( 1/ x)$
.
Proof. This is clear for
$n=2$
. Assuming
$n\ge 3$
,
$\varphi (n)$
is even, and hence,
$$ \begin{align*} x^{\varphi(n)}\Phi_n\bigg(\frac 1 x\bigg) & =\prod_{\begin{subarray}{c} 1\leq j\leq n\\ \gcd(j,n)=1 \end{subarray}}(1-\eta_n^j x)=\prod_{\begin{subarray}{c}1\leq j\leq n\\ \gcd(j,n)=1\end{subarray}}(-\eta_n^j)\prod_{\begin{subarray}{c}1\leq j\leq n\\ \gcd(j,n)=1\end{subarray}}(x-\eta_n^{-j})\\ & =\prod_{\begin{subarray}{c}1\leq j\leq n\\ \gcd(j,n)=1\end{subarray}}\eta_n^j\prod_{\begin{subarray}{c}1\leq j\leq n\\ \gcd(j,n)=1\end{subarray}}(x-\eta_n^{j})= \prod_{\begin{subarray}{c}1\leq j\leq n\\ \gcd(j,n)=1\end{subarray}}(x-\eta_n^{j})=\Phi_n(x). \\[-57pt] \end{align*} $$
Proof of Theorem 1.5
Since
$0\in C\cup D$
and
$c_1\neq d_1$
,
$c_r>d_r$
by Lemma 2.2, we have
$T(0)\neq 0$
and
$T(x),S(x)$
are monic polynomials.
In what follows, we can assume that
$T(x),S(x)\in \mathbb {Z}[x]$
are monic polynomials satisfying
$T(x^2)=T(x)S(x)$
and
$T(0)\neq 0$
, and prove S and T have the required structure by induction on the degree of T.
First, we show that the roots of
$T(x)$
and
$S(x)$
are roots of unity. If
$z_0$
is a root of T, then
$0=T(z_0)S(z_0)=T(z_0^2)$
, which implies that
$z_0^2$
is also a root of T. Thus,
$z_0^{2^j}$
is a root of T for every
$j\geq 0$
. Since T has only finitely many roots, there exists
$j\neq i$
, such that
$z_0^{2^j}=z_0^{2^i}$
. Since
$z_0\neq 0$
, this shows that
$z_0$
is a root of unity.
As a consequence, T is a product of cyclotomic polynomials. By Lemma 2.3,
$T(x^2)$
is also a product of cyclotomic polynomials and, consequently,
$S(x)$
is as well.
If
$\deg (T(x))=0$
, then
$T(x)=S(x)=1$
. Suppose
$\deg T(x)>0$
and the result is true for smaller degrees.
Assume that
$T(x)=\Phi _{n_1}(x)\Phi _{n_2}(x)\cdots \Phi _{n_k}(x)$
. If all of
$n_1,n_2,\ldots ,n_k$
are even, then
$T(x^2)=\Phi _{2n_1}(x) \Phi _{2n_2}(x)\cdots \Phi _{2n_k}(x)$
. Consider the smallest number in
$n_1,n_2,\ldots ,n_k$
, say
$n_1$
. Then,
$\Phi _{n_1}(x)\nmid T(x^2)$
, contrary to the fact that
$T(x)\mid T(x^2)$
. Thus, at least one of
$n_1,n_2,\ldots ,n_k$
is odd.
Assume that
$n_1$
is odd, and
$n_1,2n_1,\ldots ,2^{\alpha -1}n_1\in \{n_1,n_2,\ldots ,n_k\}$
, but
$2^{\alpha }n_1\not \in \{n_1,n_2,\ldots ,n_k\}$
,
$\alpha>0$
. Since
$\Phi _{2^{\alpha }n_1}(x) \mid \Phi _{2^{\alpha -1}n_1}(x^2)\mid T(x^2)=T(x)S(x)$
but
$\Phi _{2^{\alpha }n_1}(x)\nmid T(x)$
, we see that
$\Phi _{2^{\alpha }n_1}(x)\mid S(x)$
.
Write
$T(x)=\Phi _{n_1}(x)\Phi _{2n_1}(x)\cdots \Phi _{2^{\alpha -1}n_1}(x)\widetilde {T}(x)$
and
$S(x)=\Phi _{2^{\alpha }n_1}(x)\widetilde {S}(x)$
. Then,
$\widetilde {T}(x^2)=\widetilde {S}(x)\widetilde {T}(x)$
, and
$\widetilde {T}(x),\widetilde {S}(x)$
are monic polynomials with
$\widetilde {T}(0)\neq 0$
. Thus,
$\widetilde {S}$
and
$\widetilde {T}$
have the required structure by the inductive hypothesis, and so do S and T. This completes the proof of Theorem 1.5.
Theorem 1.5 has two immediate corollaries.
Corollary 2.6. We have
$|C|=|D|=2^l$
with
$l\in \mathbb {N}$
and
$C\cup D$
is symmetric in the following sense: if
$C\cup D=\{x_1\leq x_2\leq \cdots \leq x_{2^{l+1}}\}$
, then
$x_i=x_{2^{l+1}+1-i}$
for every i with
$1\leq i\leq 2^{l+1}$
.
Proof. From Theorem 1.5,
$$ \begin{align*}|C|+|D|=f_C(1)+f_D(1)=S(1)=\prod_{i=1}^k \Phi_{2^{\alpha_i}\beta_i}(1).\end{align*} $$
By Lemma 2.4,
$$ \begin{align*}\Phi_{2^{\alpha_i}\beta_i}(1)=\begin{cases} 2 & \text{if }\beta_i=1, \\ 1 & \text{if } \beta_i\ge 3.\end{cases} \end{align*} $$
Thus,
$|C|+|D|$
is a power of two. Combining this with Lemma 2.1, we conclude that
$|C|=|D|$
is a power of 2.
By Lemma 2.5,
$\Phi _{2^{\alpha _i}\beta _i}(x)$
is reciprocal for
$1\leq i\leq k$
, so
$S(x)$
is also reciprocal, which implies that
$C\cup D$
is symmetric.
Corollary 2.7. If
$S(x)=(x^{a_1}+1)\cdots (x^{a_m}+1)$
with
$a_1,\ldots ,a_m\in \mathbb {Z}_{>0}$
, then
$T(x)=(x^{a_1}-1)\cdots (x^{a_m}-1)$
and
$\{C,D\}=\{H_0(X),H_1(X)\}$
, where X is the multiset
$\{a_1,\ldots ,a_m\}$
.
Proof. The uniqueness of
$T(x)$
for a given
$S(x)$
follows immediately from the proof of Theorem 1.5. It is clear that
$S(x)T(x)=T(x^2)$
holds for
$T(x)=(x^{a_1}-1)\cdots (x^{a_m}-1)$
. The uniqueness of
$T(x)$
implies that
$T(x)$
is indeed
$(x^{a_1}-1)\cdots (x^{a_m}-1)$
.
Since
$f_C(x)=\frac 1 2(S(x)+T(x))$
and
$f_D(x)=\frac 12 (S(x)-T(x))$
, we conclude that
${C=H_0(X)}$
,
$D=H_1(X)$
if m is even, and
$C=H_1(X)$
,
$D=H_0(X)$
if m is odd.
3 Proof of Theorem 1.6
With the results in the previous section, we are ready to prove Theorem 1.6. Theorem 1.3 can also be proved with the same approach.
Proof of Theorem 1.6
It follows from Corollary 2.6 that
$|C|=|D|=2^l$
,
$l\geq 2$
, and hence,
$|C|+|D|=m-1=2^{l+1}$
,
$m=2^{l+1}+1$
. Since
$C\cup D$
is symmetric, we have
$r_1+r_2=m=2^{l+1}+1$
.
If
$\{r_1,r_2\}=\{2^l,2^l+1\}$
, then
$$ \begin{align*}S_1(x)=\sum_{j=0}^{2^{l+1}+1}x^j-x^{2^l}-x^{2^l+1}=(x+1)(x^2+1)\cdots(x^{2^{l-1}}+1)(x^{2^l+2}+1).\end{align*} $$
By Corollary 2.7,
$C=H_0(X)$
,
$D=H_1(X)$
for
$X=\{2^0,2^1,\ldots ,2^{l-1},2^l+2\}.$
This corresponds to case (1) in the statement of the theorem.
If
$\{r_1,r_2\}=\{1,2^{l+1}\}$
, then
$$ \begin{align*}S_2(x)=\sum_{j=0}^{2^{l+1}+1}x^j-x-x^{2^{l+1}}=(x^2+1)(x^4+1)\cdots(x^{2^l}+1)(x^3+1).\end{align*} $$
By Corollary 2.7,
$C=H_0(X)$
,
$D=H_1(X)$
for
$X=\{2^1,2^2,\ldots ,2^l,3\}.$
This corresponds to case (2).
If
$\{r_1,r_2\}=\{2^{l-1},2^{l}+2^{l-1}+1\}$
, then
$$ \begin{align*} S_3(x) & =\sum_{j=0}^{2^{l+1}+1}x^j-x^{2^{l-1}}-x^{2^l+2^{l-1}+1}\\ & =(x+1)(x^2+1)\cdots(x^{2^{l-2}}+1)(x^{2^{l-1}+1}+1)(x^{2^l+1}+1). \end{align*} $$
By Corollary 2.7,
$C=H_0(X)$
,
$D=H_1(X)$
for
$X=\{2^0,2^1,\ldots ,2^{l-2},2^{l-1}+1,2^l+1\}.$
This corresponds to case (3).
It remains to show that these are the only cases that can occur. First, we note that
$\Phi _4(x)^2\mid S_1(x)$
,
$\Phi _{2^{l+1}}(x)\mid S_2(x)$
and
$\Phi _2(x)^2\mid S_3(x)$
.
Claim 1. If
$\Phi _4(x)^2\mid S(x)$
, then
$\{r_1,r_2\}=\{2^l,2^l+1\}$
and
$S(x)=S_1(x)$
.
Proof. Since
$\Phi _4(x)^2\mid S_1(x)$
, we have
$\Phi _4(x)^2\mid S(x)-S_1(x)=x^{2^l}+x^{2^l+1}- x^{r_1}-x^{r_2}.$
Thus,
${i}=\sqrt {-1}$
is a double root of
$S(x)-S_1(x)$
. Substituting
$x={i}$
gives
$$ \begin{align*}1+i-i^{r_1}-i^{r_2}=0,\end{align*} $$
which implies that
$r_1,r_2$
are congruent to 0 and 1 modulo 4. Without loss of generality, assume that
$r_1\equiv 0\pmod 4$
and
$r_2\equiv 1\pmod 4$
.
Differentiating
$S(x)-S_1(x)$
and then substituting
$x=i$
gives
$$ \begin{align*}-2^li+2^l+1+r_1i-r_2=(r_1-2^l)i+(2^l+1-r_2)=0;\end{align*} $$
hence,
$r_1=2^l$
,
$r_2=2^l+1$
and
$S(x)=S_1(x)$
.
Claim 2. If
$\Phi _{2^{l+1}}\mid S(x)$
, then
$\{r_1,r_2\}=\{1,2^{l+1}\}$
and
$S(x)=S_2(x)$
.
Proof. Since
$\Phi _{2^{l+1}}(x)\mid S_2(x)$
, it follows that
$$ \begin{align*}\Phi_{2^{l+1}}(x)=(x^{2^l}+1)\mid S(x)-S_2(x)=x+x^{2^{l+1}}-x^{r_1}-x^{r_2}.\end{align*} $$
We may assume
$0< r_1\leq 2^l$
and
$2^l+1\leq r_2\leq 2^{l+1}$
. Note that
$$ \begin{align*}x+x^{2^{l+1}}-x^{r_1}-x^{r_2}\equiv x+1-x^{r_1}+x^{r_2-2^l}\pmod{x^{2^l}+1},\end{align*} $$
and
$x+1-x^{r_1}+x^{r_2-2^l}\equiv 0\pmod {x^{2^l}+1}$
if and only if
$r_1=1$
,
$r_2=2^{l+1}$
. Therefore,
$S(x)=S_2(x)$
.
Claim 3. If
$\Phi _2(x)^2\mid S(x)$
, then
$\{r_1,r_2\}=\{2^{l-1},2^{l}+2^{l-1}+1\}$
and
$S(x)=S_3(x)$
.
Proof. It follows that
$$ \begin{align*}\Phi_2(x)^2=(1+x)^2\mid S(x)-S_3(x)=x^{2^{l-1}} +x^{2^l+2^{l-1}+1}-x^{r_1}-x^{r_2}.\end{align*} $$
Since
$r_1+r_2=2^{l+1}+1$
, we may assume
$r_1$
is odd and
$r_2$
is even. Since
$x=-1$
is a double root of
$S(x)-S_3(x)$
, substituting
$x=1$
after differentiating, we get
$$ \begin{align*}-2^{l-1}+2^{l}+2^{l-1}+1-r_1+r_2=0.\end{align*} $$
Thus,
$r_1=2^l+r^{l-1}+1$
,
$r_2=2^{l-1}$
and
$S(x)=S_3(x)$
.
Now, assume that none of these three cases happens, that is,
$\Phi _2(x)^2\nmid S(x)$
,
$\Phi _4(x)^2\nmid S(x)$
and
$\Phi _{2^{l+1}}(x)\nmid S(x)$
.
For
$\alpha \geq l+2$
,
$\Phi _{2^{\alpha }}(x)$
does not divide
$S(x)$
. Otherwise,
$$ \begin{align*}\deg(S)\geq \deg(\Phi_{2^{\alpha}}) =2^{l+1}+l>2^{l+1}+1,\end{align*} $$
which contradicts the fact that
$\deg (S)=\deg (T)=m=2^{l+1}+1$
.
For
$3\leq \alpha \leq l$
, we prove that
$\Phi _{2^{\alpha }}(x)^2$
does not divide
$S(x)$
. Suppose to the contrary that
$\Phi _{2^{\alpha }}(x)^2=(1+x^{2^{\alpha }-1})^2$
divides
$S(x)$
for some
$\alpha $
with
$3\leq \alpha \leq l$
. Let
$\eta ={e}^{ 2\pi i/2^{\alpha }}$
be a primitive
$2^{\alpha }$
th root of unity. Note that
$$ \begin{align*}S(x)=\sum_{i=0}^{2^{l+1}+1}x^i-x^{r_1}-x^{r_2}=\prod_{j=0}^l(1+x^{2^j})+x^{2^{l+1}}+x^{2^{l+1}+1}-x^{r_1}-x^{r_2}.\end{align*} $$
Hence,
$S(\eta )=1+\eta -\eta ^{r_1}-\eta ^{r_2}=0$
, which implies that
$\{\eta ^{r_1},\eta ^{r_2}\}=\{1,\eta \}$
. Assume without loss of generality that
$r_1\equiv 1\pmod {2^{\alpha }}$
and
$r_2\equiv 0\pmod {2^{\alpha }}$
. Let
$$ \begin{align*} P(x) = \frac{S(x)}{\Phi_{2^{\alpha}}(x)} & = \prod_{\substack{0\leq j\leq l\\ j\neq \alpha-1}} (1+x^{2^j})+\frac{x^{2^{l+1}+1}-x^{r_1}}{1+x^{2^{\alpha-1}}}+\frac{x^{2^{l+1}}-x^{r_2}}{1+x^{2^{\alpha-1}}} \\ & = \prod_{\substack{0\leq j\leq l\\ j\neq \alpha-1}} (1+x^{2^j})+x^{r_1}(x^{2^{\alpha-1}}-1)(1+x^{2^{\alpha}}+\cdots+x^{2^{l+1}+1-r_1-2^{\alpha}}) \\ &\quad +x^{r_2}(x^{2^{\alpha-1}}-1)(1+x^{2^{\alpha}}+\cdots+x^{2^{l+1}-r_2-2^{\alpha}}). \end{align*} $$
Substituting
$x=\eta $
yields
$$ \begin{align*} P(\eta) & = (1+\eta+\eta^2+\cdots+\eta^{2^{\alpha-1}-1})2^{l-\alpha+1}\\ &\quad +\eta\cdot(-2)\cdot\frac{2^{l+1}+1-r_1}{2^{\alpha}}+1\cdot (-2)\cdot\frac{2^{l+1}-r_2}{2^{\alpha}}. \end{align*} $$
Since
$\Phi _{2^{\alpha }}(x)\mid P(x)$
, we have
$P(\eta )=0$
and so
$$ \begin{align*}(1+\eta+\eta^2+\cdots+\eta^{2^{\alpha-1}-1})2^{l}=\eta(2^{l+1}+1-r_1)+(2^{l+1}-r_2).\end{align*} $$
Comparing the imaginary part of both sides,
$$ \begin{align*}\mathrm{Im}(1+\eta+\eta^2+\cdots+\eta^{2^{\alpha-1}-1})2^l>2\mathrm{Im}(\eta)\cdot 2^{l}=2^{l+1}\mathrm{Im}(\eta),\end{align*} $$
$$ \begin{align*}\mathrm{Im}(\eta(2^{l+1}+1-r_1))=(2^{l+1}+1-r_1)\mathrm{Im}(\eta)\leq 2^{l+1}\mathrm{Im}(\eta)\end{align*} $$
and
$\mathrm {Im}(2^{l+1}-r_2)=0$
. Thus,
$$ \begin{align*}\mathrm{Im}((1+\eta+\eta^2+\cdots+\eta^{2^{\alpha-1}-1})2^{l})>\mathrm{Im}(\eta(2^{l+1}-1-r_1)+(2^{l+1}-r_2)),\end{align*} $$
which gives a contradiction.
Finally, by Theorem 1.5,
$$ \begin{align*}S =\Phi_{2^{\alpha_1}\beta_1}\Phi_{2^{\alpha_2}\beta_2}\cdots\Phi_{2^{\alpha_k}\beta_k}.\end{align*} $$
Thus,
$2^{l+1}=|C|+|D|=S(1)=\prod _{i=1}^k \Phi _{2^{\alpha _i}{\beta _i}}(1)$
. It follows from Lemma 2.4 that S has exactly
$l+1$
factors of the form
$\Phi _{2^{\alpha }}$
. However, S has at most one factor
$\Phi _{2^{\alpha }}$
for each
$\alpha $
with
$1\leq \alpha \leq l$
and no factor
$\Phi _{2^{\alpha }}$
for
$\alpha \geq l+1$
, so S can have at most l factors of the form
$\Phi _{2^{\alpha }}$
, which is a contradiction.
This completes the proof of Theorem 1.6.
