Characterization of complementing pairs of (ℤ≥0)n({\mathbb{Z}}

1. Introduction

Let $\mathbb{Z}$ be the set of integers. Let $A,B,C\subset\mathbb{Z}^{n}$ . We define $A+B=\{a+b;~{}a\in A,b\in B\}.$ We call $A+B$ the direct sum of $A$ and $B$ and denoted by $A\oplus B$ , if every element $c\in A+B$ has a unique decomposition as $c=a+b$ with $a\in A,b\in B$ . We say $(A,B)$ is a complementing pair of $C$ , or a $C$ -pair, if $C=A\oplus B$ and $A,B\subset C$ .

We are interested in $\mathbb{Z}^{n}$ -pairs and $\mathbb{N}^{n}$ -pairs, where we denote $\mathbb{N}=\mathbb{Z}_{\geq 0}$ for simplicity. Furthermore, a $\mathbb{Z}^{n}$ -pair $(A,B)$ is called a $\mathbb{Z}^{n}$ -tiling if $\#A<\infty$ , where $\#A$ denotes the cardinality of $A$ ; in this case, we call $A$ a $\mathbb{Z}^{n}$ -tile. Similarly, we define $\mathbb{N}^{n}$ -tiling and $\mathbb{N}^{n}$ -tile.

The characterization of $\mathbb{Z}$ -pairs is an important problem in additive number theory. This problem is first considered by de Bruijn [2] in 1950. In 1974, Swenson [13] showed that this problem is an NP-hard problem. There are very few results on this problem.

To determine when a finite set $A\subset\mathbb{Z}$ is a $\mathbb{Z}$ -tile is somehow easier. This was done by Newman [9] when $\#A$ is a power of a prime number, see also Tijdeman [15]. Coven and Meyerowitz [1] solved the problem when $\#A$ contains at most two prime factors, see also Sands [11]. If $\#A$ contains more than two prime factors, the problem is still widely open [14, 1]. There are almost no results on $\mathbb{Z}^{n}$ -pairs with $n\geq 2$ , except that Szegedy [12] characterized the $\mathbb{Z}^{d}$ -tile $T$ in case that $\#T$ is a prime number or $\#T=4$ .

The characterization of $\mathbb{N}$ -pairs is much easier and it was settled by de Bruijn [3], and was rediscovered by Vaidya [16]. Let $(n_{k})_{k\geq 1}$ be a sequence of integers with $n_{k}\geq 2$ . Any $t\in\mathbb{N}$ can be written uniquely in the form

(1.1)

t=d_{1}+n_{1}d_{2}+(n_{1}n_{2})d_{3}+\cdots+(n_{1}\cdots n_{L-1})d_{L},

where $d_{j}\in\{0,1,\dots,n_{j}-1\}$ for each $1\leq j\leq L$ and $d_{L}>0$ . We denote the right hand side of (1.1) by $\overline{d_{1}\dots d_{L}}$ .

Proposition 1.1.

(de Bruijn [3], Vaidya [16]) (i) A pair $(T,{\mathcal{J}})$ is an $\mathbb{N}$ -pair with $\#T=\#{\mathcal{J}}=\infty$ if and only if there exists a sequence of integers $(n_{k})_{k\geq 1}$ with $n_{k}\geq 2$ such that

(1.2)

T=\bigcup_{L=1}^{\infty}\{\overline{d_{1}\dots d_{L}};~{}d_{j}=0\text{ if $j$ is odd}\},\ {\mathcal{J}}=\bigcup_{L=1}^{\infty}\{\overline{d_{1}\dots d_{L}};~{}d_{j}=0\text{ if $j$ is even}\},

or the other round.

(ii) $T$ is an $\mathbb{N}$ -tile if and only if there exist $L\geq 2$ and $(n_{k})_{k=1}^{L}$ with $n_{k}\geq 2$ such that

T=\{\overline{d_{1}\dots d_{L}};~{}d_{j}=0\text{ if $j$ is odd}\}\text{ or }T=\{\overline{d_{1}\dots d_{L}};~{}d_{j}=0\text{ if $j$ is even}\}.

Remark 1.2.

Let $(T,{\mathcal{J}})$ be an $\mathbb{N}$ -pair with $\#T=\#{\mathcal{J}}=\infty$ . Long [7] made the interesting observation that $(T,-{\mathcal{J}})$ is a $\mathbb{Z}$ -pair; Eigen and Hajian [4] showed that there exists a continuum number of sets $\widetilde{\mathcal{J}}$ such that $(T,\widetilde{\mathcal{J}})$ is a $\mathbb{Z}$ -pair.

After a partial result was obtained by Hansen [5], Niven [10] characterized the $\mathbb{N}^{2}$ -pairs (See Example 1.1 in the end of this section).

The goal of the present paper is to characterize the $\mathbb{N}^{n}$ -pairs for all $n\geq 1$ . For simplicity, we call $(T,{\mathcal{J}})$ an $\mathbb{N}^{*}$ -pair if $(T,{\mathcal{J}})$ is an $\mathbb{N}^{n}$ -pair for some $n\geq 1$ .

It is easy to show that if $(I_{1},J_{1})$ is an $\mathbb{N}^{n}$ -pair and $(I_{2},J_{2})$ is an $\mathbb{N}^{m}$ -pair, then $(T,{\mathcal{J}})=(I_{1}\times I_{2},J_{1}\times J_{2})$ is an $\mathbb{N}^{n+m}$ -pair, and we call $(T,{\mathcal{J}})$ the Cartesian product of the two pairs. (See Lemma 2.1.)

An $\mathbb{N}^{n}$ -pair $(T,{\mathcal{J}})$ is called primitive, if it is not a Cartesian product of two $\mathbb{N}^{*}$ -pairs with lower dimensions. All $\mathbb{N}$ -pairs are primitive. Clearly, to characterize $\mathbb{N}^{*}$ -pairs, we only need understand primitive $\mathbb{N}^{*}$ -pairs.

In literature, polynomials have been used to study direct sum decomposition of abelian groups ([6, 11, 1]) or finite sets ([8]). The first idea in this paper is to use power series to handle $\mathbb{N}^{*}$ -pairs. A power series with finite many variables is called a binary power series if its coefficients belong to $\{0,1\}$ . Let $x=(x_{1},\dots,x_{n})$ be an $n$ -tuple variable. For ${\boldsymbol{a}}=(a_{1},\dots,a_{n})\in\mathbb{N}^{n}$ , we denote $x^{\boldsymbol{a}}=x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}$ . For $A\subset\mathbb{N}^{n}$ , we define

(1.3)

A(x)=\sum_{{\boldsymbol{a}}\in A}x^{\boldsymbol{a}}.

For example $\mathbb{N}(x)=\sum_{k\geq 0}x^{k}$ and $\mathbb{N}^{2}(x,y)=\mathbb{N}(x)\mathbb{N}(y)$ . Clearly, $(T,{\mathcal{J}})$ is a $\mathbb{N}^{n}$ -pair if and only if $T(x){\mathcal{J}}(x)=\mathbb{N}^{n}(x).$

We call $(C,D)$ an interval pair if it is a $\{0,1,\dots,N-1\}$ -pair for some integer $N\geq 2$ , and we call $N$ the size of the pair $(C,D)$ .

Remark 1.3.

Nathanson [8] proved that if $T\oplus S=\prod_{j=1}^{n}\{0,1,\dots,a_{j}\}$ is a higher dimensional interval pair, then $(T,S)$ is a cartesian product of one-dimensional interval pairs.

1.1. Extension process

Now, we introduce two ways to produce $\mathbb{N}^{*}$ -pairs from a known $\mathbb{N}^{n}$ -pair $(T,{\mathcal{J}})$ . Let $j\in\{1,\dots,n\}$ . Denote $x=(\bar{x},x_{j},\bar{\bar{x}})$ , where $\bar{x}=(x_{1},\dots,x_{j-1})$ and $\bar{\bar{x}}=(x_{j+1},\dots,x_{n}).$

(1) Extension of the first type. Let $N\geq 2$ and $(C,D)$ be a $\{0,1,\dots,N-1\}$ -pair. Set

(1.4)

T^{*}(x)=C(x_{j})T(\bar{x},x_{j}^{N},\bar{\bar{x}}),\quad{\mathcal{J}}^{*}(x)=D(x_{j}){\mathcal{J}}(\bar{x},x_{j}^{N},\bar{\bar{x}}).

Then $(T^{*},{\mathcal{J}}^{*})$ is an $\mathbb{N}^{n}$ -pair, and we call it a first type extension of $(T,{\mathcal{J}})$ . (See Lemma 3.1.)

(2) Extension of the second type. Let $\delta\in\{0,1\}$ , $m\geq 2$ , and ${\boldsymbol{a}}\in(\mathbb{N}\setminus\{0\})^{m}$ . Set

L_{\boldsymbol{a}}=\mathbb{N}^{m}\setminus(\mathbb{N}^{m}+{\boldsymbol{a}}).

Denote $y=(y_{1},\dots,y_{m})$ , and define $L_{\boldsymbol{a}}(y)$ as we did in (1.3). (For example, if ${\boldsymbol{a}}=(1,1)$ , then $L_{\boldsymbol{a}}(y_{1},y_{2})=1+\sum_{k\geq 1}y_{1}^{k}+\sum_{k\geq 1}y_{2}^{k}$ .) Set

(1.5)

T^{*}(\bar{x},y,\bar{\bar{x}})=L^{\delta}_{{\boldsymbol{a}}}(y)T(\bar{x},y^{\boldsymbol{a}},\bar{\bar{x}}),\quad{\mathcal{J}}^{*}(\bar{x},y,\bar{\bar{x}})=L^{1-\delta}_{{\boldsymbol{a}}}(y){\mathcal{J}}(\bar{x},y^{\boldsymbol{a}},\bar{\bar{x}}).

Then $(T^{*},{\mathcal{J}}^{*})$ is an ${\mathbb{N}}^{n+m-1}$ -pair, and we call it a second type extension of $(T,{\mathcal{J}})$ . (See Lemma 3.2.)

Let $(T_{j},{\mathcal{J}}_{j})_{j=0}^{k}$ be a sequence of $\mathbb{N}^{*}$ -pairs. If $(T_{j},{\mathcal{J}}_{j})$ is a first type or second type extension of $(T_{j-1},{\mathcal{J}}_{j-1})$ for $j=1,\dots,k$ , then we say $(T_{k},{\mathcal{J}}_{k})$ is a finite extension of $(T_{0},{\mathcal{J}}_{0})$ .

An extension of an $\mathbb{N}^{*}$ -pair $(T,{\mathcal{J}})$ is called an illegal extension, if it is a second type extension in (1.5) satisfying $(T,{\mathcal{J}})=(\{0\},\mathbb{N})$ and $\delta=0$ , or $(T,{\mathcal{J}})=(\mathbb{N},\{0\})$ and $\delta=1$ . An extension changes the primitivity if and only if it is illegal (Theorem 3.1). Our first main result is the following.

Theorem 1.1.

An $\mathbb{N}^{*}$ -pair $(T,{\mathcal{J}})$ is primitive if and only if it is a finite extension of an $\mathbb{N}$ -pair, and the extension process contains no illegal extension.

A finite extension of an $\mathbb{N}$ -pair is primitive is proved in Section 3. The other direction of Theorem 1.1 is proved in Section 4-8, where Lemma 5.1 and Theorem 6.1 contain new techniques and new phenomena which are different from dimension one and two.

1.2. Weighted tree of an $\mathbb{N}^{*}$ -pair.

For a primitive $\mathbb{N}^{*}$ -pair, we introduce a weighted tree to record the information of the extension process in Theorem 1.1. Indeed, a weighted tree provides a visualization of the structure of the associated $\mathbb{N}^{*}$ -pair.

Let $(V,\Gamma)$ be a finite tree with a root $\phi$ , where $V$ is the node set and $\Gamma$ is the edge set. A node is called a top if it has no offspring. Let $V_{0}$ denote the set of tops of $(V,\Gamma)$ . In Section 9, we define a weight of $(V,\Gamma)$ to be a quadruple

(1.6)

\left((T_{0},{\mathcal{J}}_{0}),\{{\boldsymbol{\delta}}_{v}\}_{v\in V\setminus V_{0}},\{{\boldsymbol{\alpha}}_{v}\}_{v\in V\setminus\{\phi\}},\{(C_{v},D_{v})\}_{v\in V\setminus\{\phi\}}\right),

where $(T_{0},{\mathcal{J}}_{0})$ is an $\mathbb{N}$ -pair and we call it the initial pair. We associate an $\mathbb{N}^{*}$ -pair to a weighted tree, and we call it the $\mathbb{N}^{*}$ -pair generated by the weighted tree. We show that

Theorem 1.2.

An $\mathbb{N}^{*}$ -pair $(T,{\mathcal{J}})$ is a primitive $\mathbb{N}^{n}$ -pair if and only if $(T,{\mathcal{J}})$ is generated by a weighted tree with $n$ tops.

Remark 1.4.

We show that $(T,{\mathcal{J}})$ is an $\mathbb{N}^{*}$ -tiling if and only if in the associated weighted tree, the initial pair is an $\mathbb{N}$ -tiling with $\#T_{0}<\infty$ and the map ${\boldsymbol{\delta}}$ is constantly zero, or the other round (see Remark 9.2). It is folklore that an $\mathbb{N}^{n}$ -tile is also a $\mathbb{Z}^{n}$ -tile, so our construction may shed some light to the study of $\mathbb{Z}^{n}$ -tiles with $n\geq 2$ , an area is almost untouched.

In Theorem 9.1 we give an explicit formula for $\mathbb{N}^{*}$ -pairs generated by weighted trees. (In two dimensional case, the formula is given by (1.7).) Actually, for each $v\in V$ , we define two sets $P_{v},Q_{v}\subset\mathbb{N}^{n}$ , and we show that $T=\oplus_{v\in V}P_{v}$ and ${\mathcal{J}}=\oplus_{v\in V}Q_{v}$ , which give further factorizations of $T$ and ${\mathcal{J}}$ .

Example 1.1.

Niven’s characterization of the $\mathbb{N}^{2}$ -pairs is the case $n=2$ of Theorem 1.1. In the following we describe an extension process to generate primitive $\mathbb{N}^{2}$ -pairs.

Let $(T_{0},{\mathcal{J}}_{0})$ be a non-trivial $\mathbb{N}$ -pair, $\delta\in\{0,1\}$ , ${\boldsymbol{a}}=(a_{1},a_{2})\in({\mathbb{N}}\setminus\{0\})^{2}$ , and let $\Phi_{x}=(C_{1},D_{1})$ and $\Phi_{y}=(C_{2},D_{2})$ be two interval pairs with size $N_{1}$ and $N_{2}$ , respectively. Moreover, $\delta=1$ if $T_{0}=\{0\}$ and $\delta=0$ if ${\mathcal{J}}_{0}=\{0\}$ .

Regarding $\phi$ as a variable, we have $T_{0}(\phi){\mathcal{J}}_{0}(\phi)=\mathbb{N}(\phi).$ Applying a second type extension by setting $\phi=x^{a_{1}}y^{a_{2}}$ , we obtain an $\mathbb{N}^{2}$ -pair

T_{1}(x,y)=L^{\delta}_{\boldsymbol{a}}(x,y)T_{0}(x^{a_{1}}y^{a_{2}}),\quad{\mathcal{J}}_{1}(x,y)=L^{1-\delta}_{\boldsymbol{a}}(x,y){\mathcal{J}}_{0}(x^{a_{1}}y^{a_{2}}).

Applying two first type extensions to $(T_{1},{\mathcal{J}}_{1})$ , we obtain

(1.7)

\begin{array}[]{rl}T(x,y)&=C_{1}(x)C_{2}(y)L_{\boldsymbol{a}}^{\delta}(x^{N_{1}},y^{N_{2}})T_{0}(x^{a_{1}N_{1}}y^{a_{2}N_{2}}),\\ {\mathcal{J}}(x,y)&=D_{1}(x)D_{2}(y)L_{\boldsymbol{a}}^{1-\delta}(x^{N_{1}},y^{N_{2}}){\mathcal{J}}_{0}(x^{a_{1}N_{1}}y^{a_{2}N_{2}}).\end{array}

As a corollary of Theorem 1.2, a pair $(T,{\mathcal{J}})$ is a primitive $\mathbb{N}^{2}$ -pair if and only if it is given by (1.7).

The paper is organized as follows. In Section 2, we prove several simple lemmas. Section 3 is devoted to extensions of $\mathbb{N}^{*}$ -pairs. Section 4–Section 8 investigate the reductions of primitive $\mathbb{N}^{*}$ -pairs; Theorem 1.1 is proved in Section 8. In section 9 , we introduce weighted trees. Theorem 1.2 is proved in Section 10.

2. Uniqueness and primitivity

We denote ${\boldsymbol{0}}_{m}=(0,\dots,0)\in\mathbb{Z}^{m}$ ; if the dimension is implicit, then we just write ${\boldsymbol{0}}$ . Let $\prec_{g}$ be the lexicographical order on $\mathbb{Z}^{n}$ .

Lemma 2.1.

(i) (Uniqueness) If $(T,{\mathcal{J}})$ and $(T,{\mathcal{J}}^{\prime})$ are two $\mathbb{N}^{n}$ -pairs, then ${\mathcal{J}}={\mathcal{J}}^{\prime}$ .

(ii) If $T=I_{1}\times I_{2}$ and ${\mathcal{J}}=J_{1}\times J_{2}$ where $(I_{1},J_{1})$ is an $\mathbb{N}^{n}$ -pair and $(I_{2},J_{2})$ is an $\mathbb{N}^{m}$ -pair, then $(T,{\mathcal{J}})$ is an $\mathbb{N}^{n+m}$ -pair.

Proof.

(i) Let us list ${\mathcal{J}}$ as $(t_{k})_{k\geq 1}$ by the following rule: for $s,t\in{\mathcal{J}}$ , we list $s$ before $t$ if $|s|<|t|$ ; if $|s|=|t|$ , we list $s$ before $t$ if $s\prec_{g}t$ . We list ${\mathcal{J}}^{\prime}$ as $(t_{k}^{\prime})_{k\geq 1}$ by the same rule.

Clearly $t_{1}=t_{1}^{\prime}={\boldsymbol{0}}$ . Since $T\oplus({\mathcal{J}}\setminus\{t_{1}\})=T\oplus({\mathcal{J}}^{\prime}\setminus\{t_{1}\})$ , the minimum elements (according to the above rule) of ${\mathcal{J}}\setminus\{t_{1}\}$ and ${\mathcal{J}}^{\prime}\setminus\{t_{1}^{\prime}\}$ coincide, so $t_{2}=t_{2}^{\prime}$ . Continue this procedure, we obtain ${\mathcal{J}}={\mathcal{J}}^{\prime}$ .

(ii) Denote $x=(x_{1},\dots,x_{n})$ , $y=(y_{1},\dots,y_{m})$ . We have $(I_{1}\times I_{2})(x,y)\cdot(J_{1}\times J_{2})(x,y)=I_{1}(x)J_{1}(x)I_{2}(y)J_{2}(y)=\mathbb{N}^{n}(x)\mathbb{N}^{m}(y)=\mathbb{N}^{n+m}(x,y),$ which proves the second assertion. ∎

Actually $(T,{\mathcal{J}})$ is non-primitive if one of $T$ and ${\mathcal{J}}$ is a Cartesian product.

Lemma 2.2.

If $(T,{\mathcal{J}})$ is an $\mathbb{N}^{n+m}$ -pair such that $T=I_{1}\times I_{2}\subset\mathbb{N}^{n}\times\mathbb{N}^{m}$ , then ${\mathcal{J}}$ can be written as $J_{1}\times J_{2}\subset\mathbb{N}^{n}\times\mathbb{N}^{m}$ .

Proof.

Denote $x=(x_{1},\dots,x_{n})$ , $y=(y_{1},\dots,y_{m})$ . The assumptions imply that

I_{1}(x)I_{2}(y){\mathcal{J}}(x,y)=\mathbb{N}^{n+m}(x,y).

Setting $y={\boldsymbol{0}}_{m}$ , we obtain $I_{1}(x){\mathcal{J}}(x,{\boldsymbol{0}}_{m})=\mathbb{N}^{n}(x).$ Let $J_{1}(x)={\mathcal{J}}(x,{\boldsymbol{0}}_{m})$ , then $(I_{1},J_{1})$ is an $\mathbb{N}^{n}$ -pair. Similarly, let $J_{2}(y)={\mathcal{J}}({\boldsymbol{0}}_{n},y)$ , then $(I_{2},J_{2})$ is an $\mathbb{N}^{m}$ -pair. By Lemma 2.1(ii), $(I_{1}\times I_{2},J_{1}\times J_{2})$ is an $\mathbb{N}^{n+m}$ -pair. Therefore ${\mathcal{J}}=J_{1}\times J_{2}$ by Lemma 2.1(i). ∎

We close this section with several results about $\mathbb{N}$ -pairs which will be needed later.

Lemma 2.3.

([3, 11]) If $(T,{\mathcal{J}})$ is an $\mathbb{N}$ -pair, then there exists an integer $p\geq 2$ , and an $\mathbb{N}$ -pair $(A,B)$ such that $T=pA$ , ${\mathcal{J}}=\{0,1,\dots,p-1\}\oplus pB$ or the other round.

Lemma 2.4.

([3, 11, 15]) If $(C,D)$ is a $\{0,1,\dots,N-1\}$ -pair with $N\geq 2$ , then there exists $p\geq 2$ and a $\{0,1,\dots,\frac{N}{p}-1\}$ -pair $(\widetilde{C},\widetilde{D})$ such that $C=p\widetilde{C},D=p\widetilde{D}+\{0,1,\dots,p-1\}$ or the other round.

We denote $C_{k}\uparrow T$ if $C_{k}\subset C_{k+1}$ and $T=\bigcup_{k\geq 1}C_{k}$ . The following lemma is a easy consequence of Proposition 1.1. We leave the simple proof to the reader.

Lemma 2.5.

Let $(T,{\mathcal{J}})$ be an $\mathbb{N}$ -pair. If $\#T=\#{\mathcal{J}}=\infty$ , then there exists a sequence of interval pairs $\{(C_{k},D_{k})\}_{k\geq 1}$ such that $C_{k}\uparrow T$ and $D_{k}\uparrow{\mathcal{J}}$ , and

T=C_{k}\oplus N_{k}A_{k},\quad{\mathcal{J}}=D_{k}\oplus N_{k}B_{k}

for some $A_{k},B_{k}\subset\mathbb{N}$ , where $N_{k}$ is the size of $(C_{k},D_{k})$ . If $\#T<\infty$ , then there exist an integer $N\geq 1$ and $D\subset\mathbb{N}$ such that $T\oplus D=\{0,1,\dots,N-1\}$ and ${\mathcal{J}}=D\oplus N\mathbb{N}.$

3. Extensions of $\mathbb{N}^{n}$ -pairs

In this section, we prove that a finite extension of an $\mathbb{N}$ -pair is a primitive $\mathbb{N}^{*}$ -pair.

Let ${\boldsymbol{a}}\in\mathbb{N}^{m}$ with ${\boldsymbol{a}}>0$ , recall that $L_{\boldsymbol{a}}=\mathbb{N}^{m}\setminus(\mathbb{N}^{m}+{\boldsymbol{a}}).$ Take $z\in\mathbb{N}^{m}$ , and let $k$ be the largest integer such that $z-k{\boldsymbol{a}}\in\mathbb{N}^{m}$ , then $z-k{\boldsymbol{a}}\in L_{\boldsymbol{a}}$ . Hence

(3.1)

L_{\boldsymbol{a}}\oplus\mathbb{N}{\boldsymbol{a}}=\mathbb{N}^{m}.

Especially, $L_{p}=\{0,1,\dots,p-1\}.$ Denote $x=(x_{1},\dots,x_{n})$ and $\bar{x}=(x_{2},\dots,x_{n})$ .

Lemma 3.1.

The pair $(T^{*},{\mathcal{J}}^{*})$ defined in (1.4) is an $\mathbb{N}^{n}$ -pair.

Proof.

Without loss of generality, we assume $j=1$ in (1.4). We have

\begin{array}[]{rl}T^{*}(x){\mathcal{J}}^{*}(x)&=C(x_{1})D(x_{1})T(x_{1}^{N},\bar{x}){\mathcal{J}}(x_{1}^{N},\bar{x})\\ &=(1+x_{1}+\cdots+x_{1}^{N-1})\mathbb{N}(x_{1}^{N})\mathbb{N}^{n-1}(\bar{x})=\mathbb{N}^{n}(x).\end{array}

The lemma is proved. ∎

Lemma 3.2.

The pair $(T^{*},{\mathcal{J}}^{*})$ defined in (1.5) is an $\mathbb{N}^{n+m-1}$ -pair.

Proof.

Without loss of generality, we assume $j=1$ in (1.5). We have

\begin{array}[]{rl}T^{*}(y,\bar{x}){\mathcal{J}}^{*}(y,\bar{x})&=L_{\boldsymbol{a}}(y)T(y^{{\boldsymbol{a}}},\bar{x}){\mathcal{J}}(y^{{\boldsymbol{a}}},\bar{x})=L_{\boldsymbol{a}}(y)\sum_{k\geq 0}y^{k{\boldsymbol{a}}}\mathbb{N}^{n-1}(\bar{x})\\ &=\mathbb{N}^{m}(y)\mathbb{N}^{n-1}(\bar{x})=\mathbb{N}^{n+m-1}(y,\bar{x}).\end{array}

(The third equality is due to (3.1).) The lemma is proved. ∎

In the rest of this section, we investigate the primitivity property. We say a binary power series $T(x_{1},\dots,x_{n})$ with $n\geq 2$ is variable separable, if there exist an integer $m<n$ , a permutation $\tau$ on $\{2,\dots,n\}$ , and two sets $F\in\mathbb{N}^{m}$ , $G\in\mathbb{N}^{n-m}$ such that

(3.2)

T(x_{1},\dots,x_{n})=F(x_{1},x_{\tau(2)},\dots,x_{\tau(m)})G(x_{\tau(m+1)},\dots,x_{\tau(n)}).

The following lemma is a direct consequence of Lemma 2.2.

Lemma 3.3.

An $\mathbb{N}^{n}$ -pair $(T,{\mathcal{J}})$ with $n\geq 2$ is primitive if and only if $T(x)$ is not variable separable.

By convention, for $T\subset\mathbb{N}$ , we say $T(x)$ is variable separable if and only if $\#T=1$ .

Lemma 3.4.

Let $T\subset\mathbb{N}^{n}$ . The following three statements are equivalent to each other:

(i) $T(x_{1},x_{2},\dots,x_{n})$ is variable separable.

(ii) $T(yz,x_{2},\dots,x_{n})$ is variable separable.

(iii) $T(x_{1}^{m},x_{2},\dots,x_{n})$ is variable separable for some $m\geq 2$ .

Proof.

(i) implies (ii) and (i) implies (iii) are trivial. In the following, we prove the other direction implications.

(ii) $\Rightarrow$ (i). Let us first consider that case $n=1$ . If $T(yz)$ is variable separable, then $T(yz)=F(y)G(z)$ . Set $z=1$ , we obtain $T(y)=F(y)G(1)$ . Since both $T(y)$ and $F(y)$ are binary, we obtain that $G(1)=1$ . Similarly, we have $F(1)=1$ . Hence $T(1)=1$ , which means $\#T=1$ and $T(x)$ is variable separable.

Now we assume $n\geq 2$ . Suppose $T(yz,x_{2},\dots,x_{n})$ is variable separable, then there is a permutation $\tau$ on $\{2,\dots,n\}$ , and two binary power serieses $F$ and $G$ such that either

T(yz,x_{2},\dots,x_{n})=F(y,x_{\tau(2)},\dots,x_{\tau(k)})G(z,x_{\tau(k+1)},\dots,x_{\tau(n)})\text{ with $k\leq n$, or }

T(yz,x_{2},\dots,x_{n})=F(y,z,x_{\tau(2)},\dots,x_{\tau(k)})G(x_{\tau(k+1)},\dots,x_{\tau(n)})\text{ with $k<n$. }

Set $y=1$ , $z=x_{1}$ , we obtain a variable separable factorization of $T(x_{1},\dots,x_{n})$ .

(iii) $\Rightarrow$ (i). If $n=1$ , the implication is trivial. Now we assume that $n\geq 2$ . Suppose $T(x_{1}^{m},x_{2},\dots,x_{n})$ is variable separable, then we have

(3.3)

T(x_{1}^{m},x_{2},\dots,x_{n})=F(x_{1},x_{\tau(2)}\dots,x_{\tau(k)})G(x_{\tau(k+1)},\dots,x_{\tau(n)})

where $k<n$ . Since the power of $x_{1}$ of any term in $F$ must be a multiple of $m$ , we infer that there exists $F^{*}\in\mathbb{N}^{n}$ such that

(3.4)

F(x_{1},x_{\tau(2)},\dots,x_{\tau(k)})=F^{*}(x_{1}^{m},x_{\tau(2)},\dots,x_{\tau(k)}).

Substituting (3.4) into (3.3), and then replacing $x_{1}^{m}$ by $x_{1}$ , we obtain a variable separable factorization of $T(x_{1},\dots,x_{n})$ . ∎

Theorem 3.1.

Let $(T^{*},{\mathcal{J}}^{*})$ be an extension of $(T,{\mathcal{J}})$ . If the extension is not illegal, then $(T^{*},{\mathcal{J}}^{*})$ is primitive if and only if $(T,{\mathcal{J}})$ is primitive.

Proof.

(i) Let $(T^{*},{\mathcal{J}}^{*})$ be a first type extension of $(T,{\mathcal{J}})$ satisfying $T^{*}(x)=C(x_{1})T(x_{1}^{N},{\bar{x}})$ . If $n=1$ , then both $(T,{\mathcal{J}})$ and $(T^{*},{\mathcal{J}}^{*})$ are primitive. Now we assume $n\geq 2$ . By Lemma 3.4, we have

\begin{array}[]{rl}\text{$(T^{*},{\mathcal{J}}^{*})$ is non-primitive}&\Leftrightarrow\text{$T^{*}(x)$ is variable separable}\\ &\Leftrightarrow\text{$T(x_{1}^{N},\bar{x})=T^{*}(x)/C(x_{1})$ is variable separable}\\ &\Leftrightarrow\text{ $T(x)$ is variable separable $\Leftrightarrow$ $(T,{\mathcal{J}})$ is non-primitive.}\end{array}

The theorem holds in this case.

(ii) Let $(T^{*},{\mathcal{J}}^{*})$ be a second type extension of $(T,{\mathcal{J}})$ with parameters $\delta$ and ${\boldsymbol{a}}$ . Let us assume $\delta=0$ , then $T^{*}(y,\bar{x})=T(y^{{\boldsymbol{a}}},\bar{x}),$ where $y=(y_{1},\dots,y_{m})$ . Similar as above, $(T^{*},{\mathcal{J}}^{*})$ is non-primitive is equivalent to $T(x)$ is variable separable. If $n>1$ , it is equivalent to $(T,{\mathcal{J}})$ is non-primitive; if $n=1$ , it is equivalent to $(T,{\mathcal{J}})=(\{0\},\mathbb{N})$ , which means the extension is illegal. The theorem is proved. ∎

4. $\mathbb{N}^{*}$ -pairs of pure type

Let ${\mathbf{e}}_{1},\dots,{\mathbf{e}}_{n}$ be the canonical basis of $\mathbb{Z}^{n}$ . Let $n\geq 2$ , set

(4.1)

L_{0}=\{(a_{1},\dots,a_{n})\in\mathbb{N}^{n};\ \text{at least one $a_{j}$ is $0$}\}

to be the union of $(n-1)$ -faces of $\mathbb{N}^{n}$ . An $\mathbb{N}^{n}$ -pair $(T,{\mathcal{J}})$ with $n\geq 2$ is said to be of pure type, if either $L_{0}\subset T$ or $L_{0}\subset{\mathcal{J}}$ . In this section, we characterize $\mathbb{N}^{*}$ -pairs of pure type.

Let ${\boldsymbol{a}}$ , ${\mathbf{b}}\in\mathbb{N}^{n}$ . We say ${\boldsymbol{a}}\leq{\mathbf{b}}$ if ${\mathbf{b}}-{\boldsymbol{a}}\in\mathbb{N}^{n}$ , and ${\boldsymbol{a}}<{\mathbf{b}}$ if ${\mathbf{b}}-{\boldsymbol{a}}\in(\mathbb{N}\setminus\{0\})^{n}$ .

Lemma 4.1.

If $(T,{\mathcal{J}})$ is an $\mathbb{N}^{n}$ -pair such that $L_{0}\subset{\mathcal{J}}$ , then $<$ induces a linear order on $T$ . We call ${\boldsymbol{a}}$ the germ of $T$ , where ${\boldsymbol{a}}$ is the minimum of $T\setminus\{{\boldsymbol{0}}\}$ with respect to $<$ .

Proof.

Denote $a\vee b=\max\{a,b\}$ , and $(a_{1},\dots,a_{n})\vee(b_{1},\dots,b_{n})=(a_{1}\vee b_{1},\dots,a_{n}\vee b_{n})$ .

Let ${\boldsymbol{a}},{\mathbf{b}}\in T$ . Since $L_{0}\subset{\mathcal{J}},$ ${\boldsymbol{a}}+L_{0}$ and ${\mathbf{b}}+L_{0}$ do not overlap. If neither ${\boldsymbol{a}}-{\mathbf{b}}>0$ nor ${\mathbf{b}}-{\boldsymbol{a}}>0$ , then ${\mathbf{c}}:=({\boldsymbol{a}}-{\mathbf{b}})\vee{\boldsymbol{0}}\in L_{0}$ and ${\mathbf{c}}^{\prime}:=({\mathbf{b}}-{\boldsymbol{a}})\vee{\boldsymbol{0}}\in L_{0}$ . It follows that ${\mathbf{b}}+{\mathbf{c}}={\boldsymbol{a}}+{\mathbf{c}}^{\prime}$ , a contradiction. ∎

Lemma 4.2.

Let $(T,{\mathcal{J}})$ be an $\mathbb{N}^{n}$ -pair with $L_{0}\subset{\mathcal{J}}$ , and let ${\boldsymbol{a}}$ be the germ of $T$ . Then

(i) $L_{\boldsymbol{a}}\subset{\mathcal{J}}$ ;

(ii) for every integer $k\geq 0$ , $(k{\boldsymbol{a}}+L_{{\boldsymbol{a}}})\cap T$ contains at most one element.

Proof.

(i) is obvious. Now we prove (ii). Suppose on the contrary $u,u^{\prime}\in(k{\boldsymbol{a}}+L_{{\boldsymbol{a}}})\cap T$ . We assume that $u^{\prime}<u$ (Lemma 4.1). Then $u-u^{\prime}\in L_{\boldsymbol{a}}$ since ${\boldsymbol{0}}\leq u-u^{\prime}\leq u-k{\boldsymbol{a}}$ . So $u=(u)+{\boldsymbol{0}}$ and $u=(u^{\prime})+(u-u^{\prime})$ are two different $(T,{\mathcal{J}})$ -decompositions of $u$ , which is a contradiction. ∎

The following result is an extension of Lemma 2.3 (the case $n=1$ ) and Niven [10, Lemma 5] ( the case $n=2$ ) to higher dimensions.

Theorem 4.1.

Let $n\geq 2$ , let $(T,{\mathcal{J}})$ be an $\mathbb{N}^{n}$ -pair of pure type with $L_{0}\subset{\mathcal{J}}$ , and let ${\boldsymbol{a}}$ be the germ of $T$ . Then there exists an $\mathbb{N}$ -pair $(A,B)$ such that

T=A{\boldsymbol{a}},\quad{\mathcal{J}}=B{\boldsymbol{a}}\oplus L_{\boldsymbol{a}}.

Proof.

For $k\geq 0$ , denote $\Omega_{k}=k{\boldsymbol{a}}+L_{\boldsymbol{a}}$ , and we call it the $k$ -th section of $\mathbb{N}^{n}$ . For every integer $k\geq 0$ , we claim that

$(i)$ $T\cap\Omega_{k}=\{k{\boldsymbol{a}}\}\text{ or }\emptyset;$ $(ii)$ ${\mathcal{J}}\cap\Omega_{k}=\Omega_{k}\text{ or }\emptyset.$

By Lemma 4.2, ${\boldsymbol{0}},{\boldsymbol{a}}\in T$ and $L_{\boldsymbol{a}}\subset{\mathcal{J}}$ , so the claim holds for $k=0$ . Suppose the claim is false and let $k\geq 1$ be the smallest integer such that (i) or (ii) fails.

First, by the minimality of $k$ , we have

T\cap\bigcup_{j=0}^{k-1}\Omega_{j}=U{\boldsymbol{a}},\quad{\mathcal{J}}\cap\bigcup_{j=0}^{k-1}\Omega_{j}=V{\boldsymbol{a}}\oplus L_{\boldsymbol{a}}

where $U,V\subset\{0,1,\dots,k-1\}$ . Secondly, we assert that

k{\boldsymbol{a}}\not\in T\text{ and }k\not\in U+V.

Suppose $k{\boldsymbol{a}}\in T$ , then $(k{\boldsymbol{a}})+({\mathbf{b}})$ , ${\mathbf{b}}\in L_{\boldsymbol{a}}$ , are the $(T,{\mathcal{J}})$ -decomposition of elements in $k{\boldsymbol{a}}+L_{\boldsymbol{a}}$ , and this forces that (i) and (ii) hold for $k$ , a contradiction. By the same reason, we have that $k\not\in U+V$ .

Let $C=T\cap\Omega_{k}$ and $D={\mathcal{J}}\cap\Omega_{k}$ . Then $C$ contains at most one element. The set $\Omega_{k}$ is covered by

(T\cap\bigcup_{j=0}^{k}\Omega_{j}))\oplus({\mathcal{J}}\cap\bigcup_{j=0}^{k}\Omega_{j})=(U{\boldsymbol{a}}\cup C)\oplus((V{\boldsymbol{a}}+L_{\boldsymbol{a}})\cup D).

Eliminating the elements apparently outside of $\Omega_{k}$ , we have that $\Omega_{k}$ is covered by $D\cup(C\oplus L_{\boldsymbol{a}})\cup((U+V){\boldsymbol{a}}+L_{\boldsymbol{a}})$ . Since $k\not\in U+V$ , we finally obtain

(4.2)

\Omega_{k}\subset(C\oplus L_{\boldsymbol{a}})\cup D,

which implies that both $C$ and $D$ are not empty.

Let us denote $C=\{{\mathbf{c}}\}$ . Since ${\mathbf{c}}\neq k{\boldsymbol{a}}$ , there exists $i$ such that ${\mathbf{c}}-{\mathbf{e}}_{i}\in\Omega_{k}$ , so ${\mathbf{c}}-{\mathbf{e}}_{i}\in D$ by (4.2). Since ${\boldsymbol{a}}\in T$ and ${\boldsymbol{a}}-{\mathbf{e}}_{i}\in{\mathcal{J}}$ ,

{\boldsymbol{a}}+({\mathbf{c}}-{\mathbf{e}}_{i})={\mathbf{c}}+({\boldsymbol{a}}-{\mathbf{e}}_{i})

provides two $(T,{\mathcal{J}})$ -decompositions of a same point. This contradiction proves our claim.

Our claim implies that $T=A{\boldsymbol{a}}$ and ${\mathcal{J}}=B{\boldsymbol{a}}+L_{\boldsymbol{a}}$ for some $A,B\subset\mathbb{N}$ . From $A{\boldsymbol{a}}\oplus B{\boldsymbol{a}}\oplus L_{\boldsymbol{a}}=T\oplus{\mathcal{J}}=\mathbb{N}{\boldsymbol{a}}\oplus L_{\boldsymbol{a}},$ we deduce that $(A,B)$ is an $\mathbb{N}$ -pair. The theorem is proved. ∎

5. A key Lemma

In this section we prove a crucial lemma which will be used in Section 6.

Let $n\geq 1$ and write $z=(z_{1},\dots,z_{n})$ .

Lemma 5.1.

Let ${\boldsymbol{a}}>0$ be a point in $\mathbb{N}^{n}$ . Let $A_{0},B_{0}\subset\mathbb{N}$ with $0,1\in A_{0}$ and $0\in B_{0}$ , and denote $F_{0}=A_{0}{\boldsymbol{a}}$ , $G_{0}=B_{0}{\boldsymbol{a}}\oplus L_{\boldsymbol{a}}.$ Let $\Omega\subset\mathbb{N}{\boldsymbol{a}}$ . If $F_{1},G_{1}$ are two subsets of $\mathbb{N}^{n}$ such that

(5.1)

F_{0}(z)G_{1}(z)+F_{1}(z)G_{0}(z)=L_{\boldsymbol{a}}(z)\Omega(z),

then $F_{1}=A_{1}{\boldsymbol{a}}$ and $G_{1}=B_{1}{\boldsymbol{a}}\oplus L_{\boldsymbol{a}}$ for some $A_{1},B_{1}\subset\mathbb{N}$ .

Proof.

The assumption (5.1) implies that

(F_{0}\oplus G_{1})\cup(F_{1}\oplus G_{0})=\Omega\oplus L_{\boldsymbol{a}}\text{ and }(F_{0}\oplus G_{1})\cap(F_{1}\oplus G_{0})=\emptyset.

Denote $\Omega=(d_{k}{\boldsymbol{a}})_{k\geq 1},$ where $(d_{k})_{k\geq 1}$ is an increasing sequence in $\mathbb{N}$ . We denote $\Omega_{k}:=d_{k}{\boldsymbol{a}}+L_{\boldsymbol{a}}$ and call it the $k$ -th section of $\Omega+L_{\boldsymbol{a}}$ . We claim that:

Claim 1. For all $k\geq 0$ , $G_{1}\cap\Omega_{k}=\emptyset$ or $\Omega_{k}$ .

We prove the claim by induction. Clearly the claim holds for $k=1$ . Let $k\geq 2$ and assume that $G_{1}\cap\Omega_{j}=\emptyset$ or $\Omega_{j}$ holds for $j<k$ . Then

(5.2)

G_{1}\cap(\Omega_{1}\cup\cdots\cup\Omega_{k-1})=V{\boldsymbol{a}}+L_{\boldsymbol{a}},

where $V\subset\{d_{1},d_{2},\dots,d_{k-1}\}$ . Hence, for $j<k$ ,

(5.3)

(F_{0}\oplus G_{1})\cap\Omega_{j}=(F_{0}\oplus(\{g_{0},\dots,g_{h}\}{\boldsymbol{a}}+L_{\boldsymbol{a}}))\cap\Omega_{j}=\emptyset\text{ or }\Omega_{j}.

Consequently, for $j<k$ , as the complement of the right hand side of (5.3),

(5.4)

(F_{1}\oplus G_{0})\cap\Omega_{j}=\emptyset\text{ or }\Omega_{j}.

Let $f^{*}$ be the smallest element in $F_{1}$ such that $f^{*}\not\in\mathbb{N}{\boldsymbol{a}}$ . By (5.3) and (5.4),

(5.5)

f^{*}\not\in\Omega_{1}\cup\cdots\cup\Omega_{k-1}\ (\text{if $f^{*}$ exists}).

Suppose that Claim 1 is false for $k$ . Denote $C:=G_{1}\cap\Omega_{k}$ . We assert that

(5.6)

(F_{0}\oplus G_{1})\cap\Omega_{k}=C.

Notice that

(F_{0}\oplus G_{1})\cap\Omega_{k}=[(F_{0}\oplus(\{g_{0},\dots,g_{h}\}{\boldsymbol{a}}+L_{\boldsymbol{a}}))\cap\Omega_{k}]\cup[(F_{0}\oplus C)\cap\Omega_{k}].

The second term on the right hand side is $C$ , so the first term must be the empty set, which implies (5.6).

By (5.6) and (5.4), we have that $(F_{1}\oplus G_{0})\cap\Omega_{k}\neq\emptyset$ , so there exists $f\in F_{1}$ such that $(f+G_{0})\cap\Omega_{k}\neq\emptyset$ . The intersection is not $\Omega_{k}$ implies that $f\not\in\mathbb{N}{\boldsymbol{a}}$ , so we have $f\in\Omega_{k}$ since $f\geq f^{*}$ . Since $F_{1}\cap\Omega_{k}$ contains at most one element, we conclude that $f=f^{*}$ .

Let $i$ be the index in $\{1,\dots,n\}$ such that $f-{\mathbf{e}}_{i}\in\Omega_{k}$ . Then $f-{\mathbf{e}}_{i}$ is not covered by $f+G_{0}$ , and hence it is not covered by $F_{1}+G_{0}$ . It follows that $f-{\mathbf{e}}_{i}\in C$ . Therefore, on one hand, we have

{\boldsymbol{a}}+(f-{\mathbf{e}}_{i})\in F_{0}+C\subset F_{0}+G_{1};

on the other hand, $f+({\boldsymbol{a}}-{\mathbf{e}}_{i})\in F_{1}+L_{\boldsymbol{a}}\subset F_{1}+G_{0}.$ This is a contradiction, and Claim 1 is proved. Therefore, (5.2) and (5.5) holds for all $k$ , which imply that $G_{1}=B_{1}{\boldsymbol{a}}\oplus L_{\boldsymbol{a}}$ , $F_{1}=A_{1}{\boldsymbol{a}}$ for some $A_{1},B_{1}\subset\mathbb{N}$ . The lemma is proved. ∎

6. Marginal pairs of $\mathbb{N}^{*}$ -pairs

Let $j_{1},\dots,j_{m}(1\leq m<n)$ be a subsequence of $1,\dots,n$ . We call $Q=\mathbb{N}{\mathbf{e}}_{j_{1}}\oplus\cdots\oplus\mathbb{N}{\mathbf{e}}_{j_{m}}$ an $m$ -face of $\mathbb{N}^{n}$ . Define $\rho:Q\to\mathbb{N}^{m}$ as $\rho\left(\sum_{\ell=1}^{m}c_{\ell}{\mathbf{e}}_{j_{\ell}}\right)=(c_{1},\dots,c_{m}).$ We denote

(6.1)

T_{Q}=T\cap Q,\quad{\mathcal{J}}_{Q}={\mathcal{J}}\cap Q,

and call $(\rho(T_{Q}),\rho({\mathcal{J}}_{Q}))$ the marginal pair induced by $Q$ .

Lemma 6.1.

Let $(T,{\mathcal{J}})$ be an $\mathbb{N}^{n}$ -pair and $Q$ be an $m$ -face of $\mathbb{N}^{n}$ . Then $(T_{Q},{\mathcal{J}}_{Q})$ is a $Q$ -pair. Consequently, the marginal pair $(\rho(T_{Q}),\rho({\mathcal{J}}_{Q}))$ is an $\mathbb{N}^{m}$ -pair.

Proof.

In $T(x){\mathcal{J}}(x)=\mathbb{N}^{n}(x)$ , setting $x_{k}=0$ if $k\not\in\{j_{1},\dots,j_{m}\}$ , we obtain $T_{Q}(x){\mathcal{J}}_{Q}(x)=Q(x)$ , which implies that $T_{Q}\oplus{\mathcal{J}}_{Q}=Q$ . The second assertion is obvious. ∎

If $(T,{\mathcal{J}})$ is an $\mathbb{N}$ -pair with $\{0,1,\dots,p-1\}\subset{\mathcal{J}}$ and $p\in T$ , we call $p$ the germ of $T$ .

Theorem 6.1.

Let $(T,{\mathcal{J}})$ be an $\mathbb{N}^{n}$ -pair and $Q=\mathbb{N}{\mathbf{e}}_{1}\oplus\cdots\oplus\mathbb{N}{\mathbf{e}}_{m}$ with $1\leq m\leq n$ . If the marginal pair $(\rho(T_{Q}),\rho({\mathcal{J}}_{Q})$ is of pure type in case of $m>1$ , then there exists an $\mathbb{N}^{n-m+1}$ -pair $(\widetilde{T},\widetilde{\mathcal{J}})$ such that

(6.2)

\begin{array}[]{ll}T(x)=\widetilde{T}(x_{1}^{a_{1}}\cdots x_{m}^{a_{m}},x_{m+1},\dots,x_{n}),\\ {\mathcal{J}}(x)=L_{\boldsymbol{a}}(x_{1},\dots,x_{m})\widetilde{\mathcal{J}}(x_{1}^{a_{1}}\cdots x_{m}^{a_{m}},x_{m+1},\dots,x_{n}),\end{array}

where ${\boldsymbol{a}}=(a_{1},\dots,a_{m})$ is the germ of $\rho(T_{Q})$ .

We note that (6.2) is a second type extension if $m>1$ , and is of first type if $m=1$ . Moreover, if $m=n$ , then Theorem 6.1 becomes Theorem 4.1 or Lemma 2.3.

Proof.

By Theorem 4.1 or Lemma 2.3, there exists an $\mathbb{N}$ -pair $(A,B)$ with $1\in A$ such that

(6.3)

\rho(T_{Q})=A{\boldsymbol{a}},\quad\rho({\mathcal{J}}_{Q})=B{\boldsymbol{a}}\oplus L_{\boldsymbol{a}},

(Remember that in case of $m=1$ , $L_{\boldsymbol{a}}=\{0,1,\dots,{\boldsymbol{a}}-1\}$ .) Let ${\mathbf{m}}\in\mathbb{N}^{n-m}$ . Define

T_{\mathbf{m}}=\{u\in\mathbb{N}^{m};~{}(u,{\mathbf{m}})\in T\},\quad{\mathcal{J}}_{\mathbf{m}}=\{v\in\mathbb{N}^{m};~{}(v,{\mathbf{m}})\in{\mathcal{J}}\}.

Denote $\bar{\bar{x}}=(x_{m+1},\dots,x_{n})$ , then

(6.4)

T(x)=\sum_{{\mathbf{p}}\in\mathbb{N}^{n-m}}T_{\mathbf{p}}(x_{1},\dots,x_{m})\bar{\bar{x}}^{\mathbf{p}},\quad{\mathcal{J}}(x)=\sum_{{\mathbf{q}}\in\mathbb{N}^{n-m}}{\mathcal{J}}_{\mathbf{q}}(x_{1},\dots,x_{m})\bar{\bar{x}}^{\mathbf{q}}.

We claim that for all ${\mathbf{m}}\in\mathbb{N}^{n-m}$ , it holds that

(6.5)

\mathbb{N}^{m}(x_{1},\dots,x_{m})=\sum_{{\mathbf{p}}+{\mathbf{q}}={\mathbf{m}}}T_{\mathbf{p}}(x_{1},\dots,x_{m}){\mathcal{J}}_{{\mathbf{q}}}(x_{1},\dots,x_{m}).

Clearly $\mathbb{N}^{n}(x)=\mathbb{N}^{m}(x_{1},\dots,x_{m})\sum_{{\boldsymbol{d}}\in\mathbb{N}^{n-m}}\bar{\bar{x}}^{\boldsymbol{d}}.$ On the other hand, by (6.4),

\mathbb{N}^{n}(x)=T(x){\mathcal{J}}(x)=\sum_{{\boldsymbol{d}}\in\mathbb{N}^{n-m}}\sum_{{\mathbf{p}}+{\mathbf{q}}={\boldsymbol{d}}}T_{\mathbf{p}}(x_{1},\dots,x_{m}){\mathcal{J}}_{{\mathbf{q}}}(x_{1},\dots,x_{m})\bar{\bar{x}}^{\boldsymbol{d}}.

Comparing the terms in the above two equations with the factor $\bar{\bar{x}}^{{\mathbf{m}}}$ , we obtain (6.5).

Denote $\bar{x}=(x_{1},\dots,x_{m})$ . We shall prove by induction that

(6.6)

T_{\mathbf{m}}(\bar{x})=f_{\mathbf{m}}(\bar{x}^{\boldsymbol{a}}),\quad{\mathcal{J}}_{\mathbf{m}}(\bar{x})=L_{\boldsymbol{a}}(\bar{x})G_{\mathbf{m}}(\bar{x}^{\boldsymbol{a}}),

for some $f_{\mathbf{m}},G_{\mathbf{m}}\subset\mathbb{N}$ .

For ${\mathbf{m}}={\boldsymbol{0}}$ , $(T_{\boldsymbol{0}},{\mathcal{J}}_{\boldsymbol{0}})=(\rho(T_{Q}),\rho({\mathcal{J}}_{Q}))$ . In this case (6.6) holds by (6.3).

Suppose (6.6) holds if we replace ${\mathbf{m}}$ by any point ${\mathbf{m}}^{\prime}\leq{\mathbf{m}}$ and ${\mathbf{m}}^{\prime}\neq{\mathbf{m}}$ . We are going to show that (6.6) holds for ${\mathbf{m}}$ .

If ${\mathbf{p}}+{\mathbf{q}}={\mathbf{m}}$ and ${\mathbf{p}}\neq{\boldsymbol{0}}$ , ${\mathbf{q}}\neq{\boldsymbol{0}}$ , then (6.6) holds for ${\mathbf{p}}$ and ${\mathbf{q}}$ , so

(6.7)

T_{\mathbf{p}}(\bar{x}){\mathcal{J}}_{{\mathbf{q}}}(\bar{x})=L_{\boldsymbol{a}}(\bar{x})f_{{\mathbf{p}}}(\bar{x}^{\boldsymbol{a}})G_{{\mathbf{q}}}(\bar{x}^{{\boldsymbol{a}}}).

By (6.5), we have

(6.8)

\sum_{{\mathbf{p}}+{\mathbf{q}}={\mathbf{m}}}T_{\mathbf{p}}(\bar{x}){\mathcal{J}}_{{\mathbf{q}}}(\bar{x})=L_{\boldsymbol{a}}(\bar{x})\mathbb{N}(\bar{x}^{{\boldsymbol{a}}}),

Subtracting (6.7) from (6.8), we obtain that there exists $\Omega\subset\mathbb{N}$ such that

T_{{\boldsymbol{0}}}(\bar{x}){\mathcal{J}}_{\mathbf{m}}(\bar{x})+T_{\mathbf{m}}(\bar{x}){\mathcal{J}}_{\boldsymbol{0}}(\bar{x})=L_{\boldsymbol{a}}(\bar{x})\Omega(\bar{x}^{\boldsymbol{a}}).

Hence, by Lemma 5.1, we obtain (6.6).

Finally, substituting (6.6) into (6.4), we obtain that (6.2) holds for some $\widetilde{T},\widetilde{\mathcal{J}}\in\mathbb{N}^{n-m+1}$ . It is an easy matter to show that $(\widetilde{T},\widetilde{\mathcal{J}})$ is an $\mathbb{N}^{n-m+1}$ -pair. The theorem is proved. ∎

7. $1$ -face reduction of $\mathbb{N}^{*}$ -pair

Let $(T,{\mathcal{J}})$ be a primitive $\mathbb{N}^{n}$ -pair. We say $(T,{\mathcal{J}})$ is of class ${\mathcal{F}}_{0}$ , if

T\cap\mathbb{N}{\mathbf{e}}_{j}=\{{\boldsymbol{0}}\}\text{ or }\mathbb{N}{\mathbf{e}}_{j},\quad\text{for all }j\in\{1,\dots,n\}.

In this section we show that any primitive $\mathbb{N}^{n}$ -pair is a finite extension of a pair of class ${\mathcal{F}}_{0}$ .

Denote $\bar{x}=(x_{2},\dots,x_{n})$ . Set $Q=\mathbb{N}{\mathbf{e}}_{1}$ and ${\boldsymbol{a}}=p$ in Theorem 6.1, we obtain

Lemma 7.1.

Let $(T,{\mathcal{J}})$ be an $\mathbb{N}^{n}$ -pair. If $p{\mathbf{e}}_{1}\in T$ and $\{0,1,\dots,p-1\}{\mathbf{e}}_{1}\subset{\mathcal{J}}$ , then there exists an $\mathbb{N}^{n}$ -pair $(\widetilde{T},\widetilde{\mathcal{J}})$ such that

T(x)=\widetilde{T}(x_{1}^{p},\bar{x}),\quad{\mathcal{J}}(x)=(1+x_{1}+\cdots+x_{1}^{p-1})\widetilde{\mathcal{J}}(x_{1}^{p},\bar{x}).

Using the above lemma repeatedly, we get ‘bigger’ factors of $T(x)$ and ${\mathcal{J}}(x)$ .

Proposition 7.2.

Let $(T,{\mathcal{J}})$ be an $\mathbb{N}^{n}$ -pair. Denote $T\cap\mathbb{N}{\mathbf{e}}_{1}=A{\mathbf{e}}_{1},$ ${\mathcal{J}}\cap\mathbb{N}{\mathbf{e}}_{1}=B{\mathbf{e}}_{1}$ . Let $(C,D)$ be a $\{0,1,\dots,N-1\}$ -pair such that

A=C\oplus NA_{1},\quad B=D\oplus NB_{1}

for an $\mathbb{N}$ -pair $(A_{1},B_{1})$ . Then there exists an $\mathbb{N}^{n}$ -pair $(\widetilde{T},\widetilde{\mathcal{J}})$ such that

(7.1)

T(x)=C(x_{1})\widetilde{T}(x_{1}^{N},\bar{x}),\quad{\mathcal{J}}(x)=D(x_{1})\widetilde{\mathcal{J}}(x_{1}^{N},\bar{x}).

Proof.

We prove the result by induction on $N$ . If $N=1$ , the proposition holds trivially. Assume $N\geq 2$ and that the proposition holds for any pair and any positive integer less than $N$ .

Assume $1\in D$ without loss of generality.

If $C=\{0\}$ , let $h$ be the smallest integer such that $h\not\in B$ . Then by Lemma 7.1,

T(x)=T^{*}(x_{1}^{h},\bar{x}),\quad{\mathcal{J}}(x)=(1+x_{1}+\dots+x_{1}^{h-1}){\mathcal{J}}^{*}(x_{1}^{h},\bar{x}).

Since $C(x_{1})=1$ , $D(x_{1})=1+x_{1}+\cdots+x_{1}^{N-1}$ and $N|h$ , set

\widetilde{T}(x)=T^{*}(x_{1}^{h/N},\bar{x}),\quad\widetilde{\mathcal{J}}(x)=\sum_{j=0}^{h/N-1}x_{1}^{j}{\mathcal{J}}^{*}(x_{1}^{h/N},\bar{x}),

we obtain (7.1).

Now suppose $\#C\geq 2$ . Let $p$ be the smallest element of $C$ other then $0$ . Then $p\geq 2$ . On one hand, by Lemma 2.4, there exists a $\{0,1,\dots,{N}/{p}-1\}$ -pair $(\widetilde{C},\widetilde{D})$ such that

(7.2)

C(x_{1})=\widetilde{C}(x_{1}^{p}),\quad D(x_{1})=(1+x_{1}+\dots+x_{1}^{p-1})\widetilde{D}(x_{1}^{p}).

On the other hand, by Lemma 7.1, there exists an $\mathbb{N}^{n}$ -pair $(T^{*},{\mathcal{J}}^{*})$ such that

(7.3)

T(x)=T^{*}(x_{1}^{p},\bar{x}),\quad{\mathcal{J}}(x)=(1+x_{1}+\cdots+x_{1}^{p-1}){\mathcal{J}}^{*}(x_{1}^{p},\bar{x}).

Denote $T^{*}\cap\mathbb{N}{\mathbf{e}}_{1}=A^{*}{\mathbf{e}}_{1},$ ${\mathcal{J}}^{*}\cap\mathbb{N}{\mathbf{e}}_{1}=B^{*}{\mathbf{e}}_{1}$ . By (7.3), we have $A=pA^{*}$ and $B=\{0,1,\dots,p-1\}+pB^{*}$ , which together with (7.2) imply that

A^{*}=\widetilde{C}\oplus(N/p)A_{1},\quad B^{*}=\widetilde{D}\oplus(N/p)B_{1}.

So by induction hypothesis, there exists an $\mathbb{N}^{n}$ -pair $(\widetilde{T},\widetilde{\mathcal{J}})$ such that

T^{*}(x)=\widetilde{C}(x_{1})\widetilde{T}(x_{1}^{N/p},\bar{x}),\quad{\mathcal{J}}^{*}(x)=\widetilde{D}(x_{1})\widetilde{\mathcal{J}}(x_{1}^{N/p},\bar{x}).

This together with (7.2) and (7.3) imply (7.1). The lemma is proved. ∎

The following theorem is proved by Niven ([10, Lemma 4]) in the two dimensional case.

Theorem 7.1.

If $(T,{\mathcal{J}})$ be a primitive $\mathbb{N}^{n}$ -pair with $n\geq 2$ , then either $T\cap\mathbb{N}{\mathbf{e}}_{1}$ or ${\mathcal{J}}\cap\mathbb{N}{\mathbf{e}}_{1}$ is finite.

Proof.

Let $Q=\mathbb{N}{\mathbf{e}}_{2}\oplus\cdots\oplus\mathbb{N}{\mathbf{e}}_{n}$ . Recall that $T_{Q}=T\cap Q$ , ${\mathcal{J}}_{Q}={\mathcal{J}}\cap Q.$ Write $T\cap\mathbb{N}{\mathbf{e}}_{1}=A{\mathbf{e}}_{1}$ , ${\mathcal{J}}\cap\mathbb{N}{\mathbf{e}}_{1}=B{\mathbf{e}}_{1}.$ Then $A\oplus B=\mathbb{N}$ and $T_{Q}\oplus{\mathcal{J}}_{Q}=Q$ (Lemma 6.1). Define $\rho(a_{1},\dots,a_{n})=(a_{2},\dots,a_{n}).$

Let $(C,D)$ be a $\{0,1,\dots,N-1\}$ -pair satisfying the assumptions of Proposition 7.2. Then there exists $H\subset\mathbb{N}^{n}$ such that

(7.4)

T(x)=C(x_{1})H(x).

Setting $x_{1}=0$ , we obtain $T(0,x_{2},\dots,x_{n})=H(0,x_{2},\dots,x_{n})$ , which implies that $H\cap Q=T\cap Q=T_{Q}.$ So $T_{Q}\subset H$ , and by (7.4), we have

(7.5)

C\times\rho(T_{Q})\subset T.

Suppose on the contrary that both $A$ and $B$ are infinite sets. By Lemma 2.5, there exists a sequence of interval pairs $\{C_{k},D_{k})\}_{k=1}^{\infty}$ such that $C_{k}\uparrow A$ and $D_{k}\uparrow B$ and $(C_{k},D_{k})$ satisfies the assumptions of Proposition 7.2. This together with (7.5) imply that $A\times\rho(T_{Q})\subset T$ . Similarly, we have $B\times\rho({\mathcal{J}}_{Q})\subset{\mathcal{J}}$ .

Since $(A\times\rho(T_{Q}),B\times\rho({\mathcal{J}}_{Q}))$ is an $\mathbb{N}^{n}$ -pair (Lemma 2.1), the above two inclusion relations imply that $T=A\times\rho(T_{Q})$ and ${\mathcal{J}}=B\times\rho({\mathcal{J}}_{Q}),$ which imply $(T,{\mathcal{J}})$ is not primitive. This contradiction proves the theorem. ∎

Theorem 7.2.

Let $(T,{\mathcal{J}})$ be a primitive $\mathbb{N}^{n}$ -pair. Then there exists a primitive $\mathbb{N}^{n}$ -pair $(\widetilde{T},\widetilde{\mathcal{J}})$ in ${\mathcal{F}}_{0}$ such that $(T,{\mathcal{J}})$ is a finite (first type) extension of $(\widetilde{T},\widetilde{\mathcal{J}})$ .

Proof.

We first reduce $(T,{\mathcal{J}})$ along the variable $x_{1}$ . Denote $T\cap\mathbb{N}{\mathbf{e}}_{1}=A{\mathbf{e}}_{1},{\mathcal{J}}\cap\mathbb{N}{\mathbf{e}}_{1}=B{\mathbf{e}}_{1}.$ Then either $A$ or $B$ is finite (Theorem 7.1). Assume $A$ is finite. By Lemma 2.5, there exist $D\subset B$ such that $A\oplus D=\{0,1,\dots,N-1\}$ and $B=D+N\mathbb{N}$ . Hence, by Proposition 7.2, there exists an $\mathbb{N}^{n}$ -pair $(T_{1},{\mathcal{J}}_{1})$ such that

(7.6)

T(x)=A(x_{1})T_{1}(x_{1}^{N},\bar{x}),\quad{\mathcal{J}}(x)=D(x_{1}){\mathcal{J}}_{1}(x_{1}^{N},\bar{x}).

We claim that: $(i)$ $T_{1}\cap\mathbb{N}{\mathbf{e}}_{1}=\{{\boldsymbol{0}}\}$ ; $(ii)$ $T_{1}\cap\mathbb{N}{\mathbf{e}}_{j}=T\cap\mathbb{N}{\mathbf{e}}_{j}$ for $j\neq 1$ .

From $T\cap\mathbb{N}{\mathbf{e}}_{1}=A{\mathbf{e}}_{1}$ we infer that $T(x_{1},{\boldsymbol{0}})=A(x_{1})$ , which together with (7.6) imply that $T_{1}(x_{1}^{N},{\boldsymbol{0}})=1$ . So (i) holds. Pick $j>1$ , by (7.6), we have $T({\boldsymbol{0}},x_{j},{\boldsymbol{0}})=T_{1}({\boldsymbol{0}},x_{j},{\boldsymbol{0}}),$ which means that $T\cap\mathbb{N}{\mathbf{e}}_{j}=T_{1}\cap\mathbb{N}{\mathbf{e}}_{j}$ . This proves (ii).

Next, we reduce $(T_{1},{\mathcal{J}}_{1})$ along the variables $x_{2},\dots,x_{n}$ one by one, and finally we obtain an $\mathbb{N}^{n}$ -pair $(\widetilde{T},\widetilde{\mathcal{J}})$ of class ${\mathcal{F}}_{0}$ . The theorem is proved. ∎

8. Proof of Theorem 1.1

The following lemma provides the last ingredient for proving Theorem 1.1.

Lemma 8.1.

Let $n\geq 2$ and $(T,{\mathcal{J}})$ be a primitive $\mathbb{N}^{n}$ -pair of class ${\mathcal{F}}_{0}$ . Then there exists an $m$ -face $Q_{0}$ with $2\leq m\leq n$ such that the marginal pair induced by $Q_{0}$ is of pure type.

Proof.

Without loss of generality, we assume that $T\cap\mathbb{N}{\mathbf{e}}_{j}=\{{\boldsymbol{0}}\}$ holds for at least one $j$ . By rearranging the order of variables, we may assume that

T\cap\mathbb{N}{\mathbf{e}}_{j}=\{{\boldsymbol{0}}\}\text{ for }j=1,\dots,M,\text{ and }T\cap\mathbb{N}{\mathbf{e}}_{j}=\mathbb{N}{\mathbf{e}}_{j}\text{ otherwise},

where $1\leq M\leq n$ . Denote $Q=\oplus_{j=1}^{M}\mathbb{N}{\mathbf{e}}_{j}$ and $Q^{\prime}=\oplus_{j=M+1}^{n}\mathbb{N}{\mathbf{e}}_{j}$ . (If $M=n$ , we set $Q^{\prime}=\{{\boldsymbol{0}}\}$ .) Then $(T_{Q},{\mathcal{J}}_{Q})$ is a $Q$ -pair and $(T_{Q^{\prime}},{\mathcal{J}}_{Q^{\prime}})$ is a $Q^{\prime}$ -pair.

We claim that either $\#T_{Q}\geq 2$ or $\#{\mathcal{J}}_{Q^{\prime}}\geq 2$ . Suppose on the contrary that $\#T_{Q}=1$ and $\#{\mathcal{J}}_{Q^{\prime}}=1$ . Then $T_{Q}={\mathcal{J}}_{Q^{\prime}}=\{{\boldsymbol{0}}\},$ which implies that ${\mathcal{J}}_{Q}=Q\subset{\mathcal{J}}$ and $T_{Q^{\prime}}=Q^{\prime}\subset T.$ It follows that $(T,{\mathcal{J}})=(Q^{\prime},Q)$ and it is not primitive, which contradicts our assumption.

Without loss of generality, let us assume that $\#T_{Q}\geq 2$ . Let $x^{{\boldsymbol{a}}^{\prime}}$ be a term of $T_{Q}(x)-1$ such that the number of non-zero entries of ${\boldsymbol{a}}^{\prime}$ attains the minimum. Write $x^{{\boldsymbol{a}}^{\prime}}$ as

x^{{\boldsymbol{a}}^{\prime}}=x_{j_{1}}^{r_{1}}\cdots x_{j_{m}}^{r_{m}},\quad\text{ where }j_{1},\dots,j_{m}\in\{1,\dots,M\}.

Then $m\geq 2$ since $T\cap\mathbb{N}{\mathbf{e}}_{j}=\{{\boldsymbol{0}}\}$ for $1\leq j\leq M$ . Let $Q_{0}=\mathbb{N}{\mathbf{e}}_{j_{1}}\oplus\cdots\oplus\mathbb{N}{\mathbf{e}}_{j_{m}}$ , which is the smallest face containing ${{\boldsymbol{a}}^{\prime}}$ . Let $(f,g)$ be the marginal pair induced by $Q_{0}$ , then $(f,g)$ is an $\mathbb{N}^{m}$ -pair of pure type by the minimality of $m$ . The lemma is proved. ∎

Proof of Theorem 1.1..

By Theorem 3.1, we only need show that any primitive $\mathbb{N}^{*}$ -pair is a finite extension of an $\mathbb{N}$ -pair. Let $(T,{\mathcal{J}})$ be a primitive $\mathbb{N}^{n}$ -pair. We prove by induction on the dimension of $(T,{\mathcal{J}})$ . If $n=1$ , the theorem is trivially true.

Assume $n\geq 2$ . By Theorem 7.2, there exists a primitive $\mathbb{N}^{n}$ -pair $(T_{1},{\mathcal{J}}_{1})$ of class ${\mathcal{F}}_{0}$ such that $(T,{\mathcal{J}})$ is a finite extension of it. By Lemma 8.1, $(T_{1},{\mathcal{J}}_{1})$ has an $m$ -face $Q_{0}$ with $m\geq 2$ such that the marginal pair induced by $Q_{0}$ is of pure type. So by Theorem 6.1, there exists a primitive $\mathbb{N}^{n-m+1}$ -pair $(\widetilde{T},\widetilde{\mathcal{J}})$ such that $(T_{1},{\mathcal{J}}_{1})$ is a second type extension of $(\widetilde{T},\widetilde{\mathcal{J}})$ . Finally, by induction hypothesis, $(\widetilde{T},\widetilde{\mathcal{J}})$ is a finite extension of an $\mathbb{N}$ -pair, say $(T_{0},{\mathcal{J}}_{0})$ . Then $(T_{0},{\mathcal{J}}_{0})\to(\widetilde{T},\widetilde{\mathcal{J}})\to(T_{1},{\mathcal{J}}_{1})\to(T,{\mathcal{J}})$ indicates the extension process from $(T_{0},{\mathcal{J}}_{0})$ to $(T,{\mathcal{J}})$ . ∎

9. Weighted tree of $\mathbb{N}^{*}$ -pair

In this section, we study weighted trees and the associated $\mathbb{N}^{*}$ -pairs.

9.1. Weighted tree

A graph $(V,\Gamma)$ with node set $V$ and edge set $\Gamma$ is a tree if it is connected and has no cycle. A rooted tree is a triple $(V,\Gamma,\phi)$ where $(V,\Gamma)$ is a tree and $\phi\in V$ ; we call $\phi$ the root of the tree.

Let $(V,\Gamma)$ be a finite tree with root $\phi$ . The level of $v$ , denoted by $|v|$ , is the length of the (unique) path joining $v$ and $\phi$ . A node $v$ is called an offspring of $u$ , if there is an edge joining $u$ and $v$ , and $|v|=|u|+1$ ; meanwhile we call $u$ the parent of $v$ . For $u,v\in V$ , we use $[u,v]$ to denote the edge joining $u$ and its offspring $v$ . We call $u$ an ancestor of $v$ if there is a path joining $u$ and $v$ , and $|u|<|v|$ . A node $v$ is called a top if it has no offspring. We denote by $V_{0}$ the set of tops. We shall use the nodes as variables of power series.

Definition 9.1.

We call the quadruple

(9.1)

\left((T_{0},{\mathcal{J}}_{0}),{\boldsymbol{\delta}},{\boldsymbol{\alpha}},\Phi\right)

a weight of the tree $(V,\Gamma)$ , where $(T_{0},{\mathcal{J}}_{0})$ is an $\mathbb{N}$ -pair, called the initial pair,

{\boldsymbol{\delta}}:V\setminus V_{0}\to\{0,1\},\ {\boldsymbol{\alpha}}:V\setminus\{\phi\}\to\mathbb{N}\setminus\{0\},\ \Phi:V\setminus\{\phi\}\to\{\text{interval pairs}\}

are three maps, and in addition, ${\boldsymbol{\delta}}_{\phi}=1$ if $T_{0}=\{0\}$ and ${\boldsymbol{\delta}}_{\phi}=0$ if ${\mathcal{J}}_{0}=\{0\}$ .

We call $\#V-\#V_{0}$ the norm of the tree. Two tops are said to be equivalent, if they share the same parents. An equivalent class of $V_{0}$ is called a branch of $V_{0}$ .

9.2. Constructing $\mathbb{N}^{*}$ -pairs from weighted trees

Now we define the pair generated by a weighted tree inductively on the norm of the tree.

Notice that $\Lambda_{0}=(\{\phi\},\emptyset)$ is the only tree with norm $0$ . The weight of $\Lambda_{0}$ only consists of the initial pair, which we denote by $(T_{0},{\mathcal{J}}_{0})$ . We define the $\mathbb{N}^{*}$ -pair associate with the weighted tree $\Lambda_{0}$ to be $(T_{0},{\mathcal{J}}_{0})$ .

Let $q\geq 1$ . Suppose for any weighted tree with norm less than $q$ , we have associated an $\mathbb{N}^{m}$ -pair with it, where $m$ is the number of tops of the tree.

Let $(V,\Gamma)$ be a weighted tree with norm $q$ . Let $V_{0}=\{x_{1},\dots,x_{n}\}$ . Choose a branch $\{x_{1},\dots,x_{p}\}$ of $V_{0}$ and denote their parents by $z_{1}$ . Let $(\widetilde{V},\widetilde{\Gamma})$ be the subtree of $(V,\Gamma)$ obtained by deleting the nodes $x_{1},\dots,x_{p}$ and the edges $[z_{1},x_{1}],\dots,[z_{1},x_{p}]$ . Then

(9.2)

\widetilde{V}=V\setminus\{x_{1},\cdots,x_{p}\},\quad\widetilde{V}_{0}=\{z_{1},x_{p+1},\dots,x_{n}\}.

We define the weight of $(\widetilde{V},\widetilde{\Gamma})$ to be the restriction of the weight $((T_{0},{\mathcal{J}}_{0}),{\boldsymbol{\delta}},{\boldsymbol{\alpha}},\Phi)$ on it. (Now $z_{1}$ is a top of the subtree, so ${\boldsymbol{\delta}}_{z_{1}}$ is not needed in the restricted weight.)

Since $\#\widetilde{V}-\#\widetilde{V}_{0}=q-1$ , by the induction hypothesis, there is an $\mathbb{N}^{n-p+1}$ -pair $(\widetilde{T},\widetilde{\mathcal{J}})$ associated with the weighted tree of $(\widetilde{V},\widetilde{\Gamma})$ .

Denote $\delta={\boldsymbol{\delta}}_{z_{1}}$ . For $j=1,\dots,p$ , let $a_{j}={\boldsymbol{\alpha}}_{x_{j}}$ , $(C_{j},D_{j})=\Phi_{x_{j}}$ , and let $N_{j}$ be the size of $(C_{j},D_{j})$ . Denote $\bar{x}=(x_{p+1},\dots,x_{n})$ and ${\boldsymbol{a}}=(a_{1},\dots,a_{p})$ .

First, applying an second type extension with parameters $\delta$ and ${\boldsymbol{a}}$ to $(\widetilde{T},\widetilde{\mathcal{J}})$ , we obtain

F(x)=L^{\delta}_{\boldsymbol{a}}(x_{1},\dots,x_{p})\widetilde{T}(\prod_{j=1}^{p}x_{j}^{a_{j}},\bar{x}),\quad G(x)=L^{1-\delta}_{\boldsymbol{a}}(x_{1},\dots,x_{p})\widetilde{\mathcal{J}}(\prod_{j=1}^{p}x_{j}^{a_{j}},\bar{x}).

Secondly, applying $p$ extensions of the first type consecutively to the pair $(F,G)$ , along the variables $x_{1},\dots,x_{p}$ , we obtain

(9.3)

\begin{array}[]{l}T(x)=\left(\prod_{j=1}^{p}C_{j}(x_{j})\right)L^{\delta}_{\boldsymbol{a}}(x_{1}^{N_{1}},\dots,x_{p}^{N_{p}})\widetilde{T}(\prod_{j=1}^{p}x_{j}^{a_{j}N_{j}},\bar{x}),\\ {\mathcal{J}}(x)=\left(\prod_{j=1}^{p}D_{j}(x_{j})\right)L^{1-\delta}_{\boldsymbol{a}}(x_{1}^{N_{1}},\dots,x_{p}^{N_{p}})\widetilde{\mathcal{J}}(\prod_{j=1}^{p}x_{j}^{a_{j}N_{j}},\bar{x}).\end{array}

We call $(T,{\mathcal{J}})$ the $\mathbb{N}^{*}$ -pair generated by the weighted tree (9.1).

To show the generated pair is well-defined, we need to show that $(T,{\mathcal{J}})$ is independent of the choice of the branch $\{x_{1},\dots,x_{p}\}$ . We will do this in Theorem 9.1.

Remark 9.2.

Clearly, $\#T<\infty$ if and only if $\#T_{0}<\infty$ and ${\boldsymbol{\delta}}$ is constantly $0$ ; a similar result holds for $\#{\mathcal{J}}$ . Also, $(T,{\mathcal{J}})$ is of class ${\mathcal{F}}_{0}$ if and only if $\Phi_{v}=(\{{\boldsymbol{0}}\},\{{\boldsymbol{0}}\})$ for all tops.

9.3. A closed formula of $(T,{\mathcal{J}})$

Let $(T,{\mathcal{J}})$ be the pair defined by (9.3). We define a map $\mu:V\times V_{0}\to\mathbb{N}$ as follows. Pick $v\in V$ and $x^{*}\in V_{0}$ .

If $v$ is an ancestor of $x^{*}$ , let $v,v_{1},\dots,v_{k-1},v_{k}=x^{*}$ be the path from $v$ to $x^{*}$ ; for $j=1,\dots,k,$ let $c_{j}={\boldsymbol{\alpha}}_{v_{j}}$ and $M_{j}$ be the size of $\Phi_{v_{j}}$ . We define

(9.4)

\mu(v,x^{*})=\left\{\begin{array}[]{cl}\prod_{j=1}^{k}c_{j}M_{j},&\text{ if $v$ is an ancestor of $x^{*}$;}\\ 1,&\text{ if $v=x^{*}$;}\\ 0,&\text{ otherwise}.\end{array}\right.

Moreover, we define $\mu(v)=(\mu(v,x_{1}),\dots,\mu(v,x_{n})).$

For each $v\in V$ , we define two power series $P_{v}$ and $Q_{v}$ as follows. Denote $\Phi_{v}=(C_{v},D_{v})$ .

If $v$ is a top, we set

(9.5)

P_{v}(x)=C_{v}(v),\quad Q_{v}(x)=D_{v}(v).

(If $V=\{\phi\}$ , we make the convention $P_{\phi}(\phi)=T_{0}(\phi)$ and $Q_{\phi}(\phi)={\mathcal{J}}_{0}(\phi)$ .)

If $v$ is not a top, let $z_{1},\dots,z_{m}$ be the offsprings of $v$ . Denote ${\mathbf{b}}=({\boldsymbol{\alpha}}_{z_{1}},\dots,{\boldsymbol{\alpha}}_{z_{m}})$ and $M_{j}$ be the size of $\Phi_{z_{j}}$ . (If $v=\phi$ , we set $C_{\phi}=T_{0}$ and $D_{\phi}={\mathcal{J}}_{0}$ .) We define

(9.6)

\begin{array}[]{l}P_{v}(x)=C_{v}(x^{\mu(v)})L^{{\boldsymbol{\delta}}_{v}}_{{\mathbf{b}}}(x^{M_{1}\mu(z_{1})},\dots,x^{M_{m}\mu(z_{m})}),\\ Q_{v}(x)=D_{v}(x^{\mu(v)})L^{1-{\boldsymbol{\delta}}_{v}}_{{\mathbf{b}}}(x^{M_{1}\mu(z_{1})},\dots,x^{M_{m}\mu(z_{m})}).\end{array}

Theorem 9.1.

Let $(T,{\mathcal{J}})$ be an $\mathbb{N}^{n}$ -pair generated by the tree $(V,\Gamma)$ with weight (9.1). Then $P_{v}(x)$ and $Q_{v}(x)$ defined by (9.5) and (9.6) are binary power series, and

(9.7)

T(x)=\prod_{v\in V}P_{v}(x),\quad{\mathcal{J}}(x)=\prod_{v\in V}Q_{v}(x)

Proof.

Denote $q=\#V-\#V_{0}$ . We prove the result by induction on $q$ . If $q=0$ , then $V=\{\phi\}$ , and (9.7) holds by our convention. Now we assume that $q\geq 1$ .

Let $(\widetilde{V},\widetilde{\Gamma})$ be the subtree of $(V,\Gamma)$ given by (9.2), and the weight is the restricted weight. According to this restricted weight, for any $v\in\widetilde{V}$ and $z\in\widetilde{V}_{0}=\{z_{1},x_{p+1},\dots,x_{n}\}$ , we can define a map $\widetilde{\mu}(v,z)$ as (9.4), and power series $\widetilde{P}_{v},\widetilde{Q}_{v}$ as (9.5) and (9.6).

Let $(\widetilde{T},\widetilde{\mathcal{J}})$ be the pair generated by the weighted tree $(\widetilde{V},\widetilde{\Gamma})$ . Denote $\bar{x}=(x_{p+1},\dots,x_{n})$ . By induction hypothesis, we have

(9.8)

\widetilde{T}(z_{1},\bar{x})=\prod_{v\in\widetilde{V}}\widetilde{P}_{v}(z_{1},\bar{x}).

For $j=1,\dots,p$ , denote $a_{j}={\boldsymbol{\alpha}}_{x_{j}}$ , and let $N_{j}$ be the size of $\Phi_{x_{j}}=(C_{x_{j}},D_{x_{j}})$ . We assert that

(9.9)

x^{\mu(v)}=(z_{1},\bar{x})^{\widetilde{\mu}(v)}\circ\left(z_{1}\mapsto\prod_{j=1}^{p}x_{j}^{a_{j}N_{j}}\right),~{}~{}\text{ for }v\in\widetilde{V}.

Notice that (9.9) holds if the following holds:

(9.10)

\mu(v,x_{j})=\left\{\begin{array}[]{ll}\widetilde{\mu}(v,z_{1})a_{j}N_{j},&\text{ if }1\leq j\leq p;\\ \widetilde{\mu}(v,x_{j})&\text{ if }p+1\leq j\leq n.\end{array}\right.

If $v$ is an ancestor of $z_{1}$ or $v=z_{1}$ , we have $\mu(v,x_{j})=\widetilde{\mu}(v,z_{1})\mu(z_{1},x_{j})=\widetilde{\mu}(v,z_{1})a_{j}N_{j},$ $1\leq j\leq p;$ if $v$ is not an ancestor of $z_{1}$ , we have $\mu(v,x_{1})=\cdots=\mu(v,x_{p})=\widetilde{\mu}(v,z_{1})=0.$ So the first assertion of (9.10) holds. The second assertion holds since the path from $v$ to $x_{j}$ in $\Gamma$ is also a path in $\widetilde{\Gamma}$ . This proves (9.10) and (9.9) follows.

Now, we consider the relations between $P_{v}$ and $\widetilde{P}_{v}$ for $v\in\widetilde{V}$ .

If $v=z_{1}$ , since $z_{1}$ is a top of $\widetilde{V}$ , we have $\widetilde{P}_{z_{1}}(z_{1},\bar{x})=C_{z_{1}}(z_{1})$ ; moreover, $\mu(z_{1})=(a_{1}N_{1},\dots,a_{p}N_{p},0,\cdots,0)$ and $\mu(x_{j})={\mathbf{e}}_{j}$ , $1\leq j\leq n$ . Denote ${\boldsymbol{a}}=(a_{1},\dots,a_{p})$ , we have

(9.11)

\begin{array}[]{rl}P_{z_{1}}(x)&=C_{z_{1}}\left(\prod_{j=1}^{p}x_{j}^{a_{j}N_{j}}\right)L^{{\boldsymbol{\delta}}_{z_{1}}}_{\boldsymbol{a}}(x_{1}^{N_{1}},\dots,x_{p}^{N_{p}})\\ &=\left(\widetilde{P}_{z_{1}}(z_{1},\bar{x})\circ(z_{1}\mapsto\prod_{j=1}^{p}x_{j}^{a_{j}N_{j}})\right)L^{{\boldsymbol{\delta}}_{z_{1}}}_{\boldsymbol{a}}(x_{1}^{N_{1}},\cdots,x_{p}^{N_{p}}).\end{array}

We claim that

(9.12)

P_{v}(x)=\widetilde{P}_{v}(z_{1},\bar{x})\circ\left(z_{1}\mapsto\prod_{j=1}^{p}x_{j}^{a_{j}N_{j}}\right),\quad\text{ if }v\in\widetilde{V}\setminus\{z_{1}\}.

If $v\in\{x_{p+1},\dots,x_{n}\}$ , we have $P_{v}(x)=\widetilde{P}_{v}(z_{1},\bar{x})=C_{v}(v)$ , clearly (9.12) holds.

If $v\in\widetilde{V}\setminus\{z_{1},x_{p+1},\dots,x_{n}\}$ , denote the offsprings of $v$ by $y_{1},\cdots,y_{m}$ . Set ${\mathbf{b}}=({\boldsymbol{\alpha}}_{y_{1}},\cdots,{\boldsymbol{\alpha}}_{y_{m}})$ , and let $M_{i}$ be the size of $\Phi_{y_{i}}$ for $1\leq i\leq m$ . Since $C_{v}=\widetilde{C}_{v}$ and $\delta_{v}=\widetilde{\delta}_{v}$ , we have

\begin{array}[]{l}P_{v}(x)=C_{v}(x^{\mu(v)})L^{{\boldsymbol{\delta}}_{v}}_{{\mathbf{b}}}(x^{M_{1}\mu(y_{1})},\dots,x^{M_{m}\mu(y_{m})}),\\ \widetilde{P}_{v}(z_{1},\bar{x})=C_{v}((z_{1},\bar{x})^{\widetilde{\mu}(v)})L^{{\boldsymbol{\delta}}_{v}}_{\mathbf{b}}((z_{1},\bar{x})^{M_{1}\widetilde{\mu}(y_{1})},\dots,(z_{1},\bar{x})^{M_{m}\widetilde{\mu}(y_{m})}).\end{array}

Notice that (9.9) holds for all $v,y_{1},\dots,y_{m}\in\widetilde{V}\setminus\{z_{1}\}$ , so (9.12) follows. The claim is proved. Therefore, we have

\begin{array}[]{rll}&T(x)=\displaystyle\left(\prod_{j=1}^{p}C_{x_{j}}(x_{j})\right)L^{{\boldsymbol{\delta}}_{z_{1}}}_{\boldsymbol{a}}(x_{1}^{N_{1}},\dots,x_{p}^{N_{p}})\cdot\widetilde{T}\left(\prod_{j=1}^{p}x_{j}^{a_{j}N_{j}},\bar{x}\right)&\text{(By \eqref{eq:treee})}\\ =&\displaystyle\left(\prod_{j=1}^{p}P_{x_{j}}(x)\right)L^{{\boldsymbol{\delta}}_{z_{1}}}_{\boldsymbol{a}}(x_{1}^{N_{1}},\dots,x_{p}^{N_{p}})\cdot\prod_{v\in\widetilde{V}}\widetilde{P}_{v}(z_{1},\bar{x})\circ(z_{1}\mapsto\prod_{j=1}^{p}x_{j}^{a_{j}N_{j}})&\text{(By \eqref{eq:Tq})}\\ =&\displaystyle\left(\prod_{j=1}^{p}P_{x_{j}}(x)\right)\left(L^{{\boldsymbol{\delta}}_{z_{1}}}_{\boldsymbol{a}}(x_{1}^{N_{1}},\dots,x_{p}^{N_{p}})\widetilde{P}_{z_{1}}(\prod_{j=1}^{p}x_{j}^{a_{j}N_{j}},\bar{x})\right)\left(\prod_{v\in\widetilde{V}\setminus\{z_{1}\}}P_{v}(x)\right)&\text{(By \eqref{eq:PV})}\\ =&\displaystyle\prod_{v\in V}P_{v}(x).&\text{(By \eqref{eq:9.10}.)}\end{array}

By symmetry, we have ${\mathcal{J}}(x)=\prod_{v\in V}Q_{v}(x)$ . The theorem is proved. ∎

10. Proof of Theorem 1.2 and an example

Proof of Theorem 1.2.

Thanks to Theorem 3.1, we only need show that any primitive $\mathbb{N}^{*}$ -pair $(T,{\mathcal{J}})$ can be generated by a weighted tree. If $(T,{\mathcal{J}})$ is an $\mathbb{N}$ -pair, then it is generated by the tree $\Lambda_{0}=(\{\phi\},\emptyset)$ with initial pair $(T_{0},{\mathcal{J}}_{0})=(T,{\mathcal{J}})$ .

Suppose $(T,{\mathcal{J}})$ is generated by a tree $(V,\Gamma)$ with weight $((T_{0},{\mathcal{J}}_{0}),{\boldsymbol{\delta}},{\boldsymbol{\alpha}},\Phi)$ . In the following, we show that any one step extension $(T^{*},{\mathcal{J}}^{*})$ of it can also be generated by a weighted tree. Denote the tops of $(V,\Gamma)$ by $x_{1},\dots,x_{n}$ , and assume the extension is along the variable $x_{1}$ . Denote $\bar{x}=(x_{2},\dots,x_{n})$ .

Case 1. Suppose $(T^{*},{\mathcal{J}}^{*})$ is a first type extension of $(T,{\mathcal{J}})$ given by

T^{*}(x)=C(x_{1})T(x_{1}^{N},\bar{x}),\quad{\mathcal{J}}^{*}(x)=D(x_{1}){\mathcal{J}}(x_{1}^{N},\bar{x}),

where $(C,D)$ is a $\{0,\dots,N-1\}$ -pair. Denote $\Phi_{x_{1}}=(C_{x_{1}},D_{x_{1}}).$ We define a new weight of $(V,\Gamma)$ by only modifying $\Phi_{x_{1}}$ to the interval pair $(C+NC_{x_{1}},D+ND_{x_{1}})$ . Then $(T^{*},{\mathcal{J}}^{*})$ is generated by the tree $(V,\Gamma)$ with this new weight.

Case 2. Suppose $(T^{*},{\mathcal{J}}^{*})$ is a second type extension of $(T,{\mathcal{J}})$ given by

T^{*}(y,\bar{x})=L^{s}_{\mathbf{b}}(y)T(y^{{\mathbf{b}}},\bar{x}),\quad{\mathcal{J}}^{*}(y,\bar{x})=L^{1-s}_{\mathbf{b}}(y){\mathcal{J}}(y^{{\mathbf{b}}},\bar{x}),

where $y=(y_{1},\dots,y_{m})$ , ${\mathbf{b}}=(b_{1},\dots,b_{m})>0$ and $s\in\{0,1\}$ . We set $V^{\prime}=V\cup\{y_{1},\dots,y_{m}\}$ , and let $\Gamma^{\prime}=\Gamma\cup\{[x_{1},y_{j}];~{}j=1,\dots,m\}$ be the edge set. We define a weight $((T_{0},{\mathcal{J}}_{0}),{\boldsymbol{\delta}}^{\prime},{\boldsymbol{\alpha}}^{\prime},\Phi^{\prime})$ of $(V^{\prime},\Gamma^{\prime})$ , which is the extension of the original weight by adding the following parameters: $(i)$ Set ${\boldsymbol{\delta}}^{\prime}_{x_{1}}=s$ ; $(ii)$ For $j\in\{1,\dots,m\}$ , set ${\boldsymbol{\alpha}}^{\prime}_{y_{j}}=b_{j}$ and $\Phi^{\prime}_{y_{j}}=(\{{\boldsymbol{0}}\},\{{\boldsymbol{0}}\})$ . Then $(T^{*},{\mathcal{J}}^{*})$ is generated by $(V^{\prime},\Gamma^{\prime})$ with the above weight. ∎

Refer to caption — Figure 1. A rooted tree

The function ${\boldsymbol{\alpha}}$ and $\Phi$ :
node $y_{1}$ $x_{4}$ $x_{1}$ $x_{2}$ $x_{3}$ ${\boldsymbol{\alpha}}$ 2 3 1 1 1 $C$ $\{0,2\}$ $\{0,2\}$ {0} {0} {0} $D$ $\{0,1\}$ $\{0,1\}$ {0} {0} {0} $N$ 4 4 1 1 1

Table 1. We set

{\boldsymbol{\delta}}

defined on

\{\phi,y_{1}\}

to be constantly zero.

Example 10.1.

Let $(\Gamma,V)$ be a rooted tree indicated by Figure 1. The node set $V=\{\phi,y_{1},x_{1},x_{2},x_{3},x_{4}\}$ . We set the initial $\mathbb{N}$ -pair to be

T_{0}(\phi)=1+\phi^{2},\quad{\mathcal{J}}_{0}(\phi)=(1+\phi)\sum_{k=0}^{\infty}\phi^{4k};

the other parameters of the weight is given by Table 1. Set

V_{0}=\{\phi\},\ V_{1}=\{\phi;y_{1},x_{4}\},V_{2}=\{\phi;y_{1},x_{4};x_{1},x_{2},x_{3}\}.

Let $(V_{j},\Gamma_{j}),j=0,1,2,$ be subtrees of $(V,\Gamma)$ . The $\mathbb{N}^{*}$ -tile $T_{1}$ corresponding to the subtree $(V_{1},\Gamma_{1})$ is $T_{1}(y_{1},x_{4})=(1+y_{1}^{2})(1+x_{4}^{2})(1+y_{1}^{16}x_{4}^{24}).$ The $\mathbb{N}^{*}$ -tile $T_{2}$ corresponding to the tree $(V_{2},\Gamma_{2})=(V,\Gamma)$ is

\begin{array}[]{rl}T_{2}(x_{1},x_{2},x_{3},x_{4})=&1\cdot 1\cdot 1\cdot(1+(x_{1}x_{2}x_{3})^{2})\cdot(1+x_{4}^{2})\cdot\left(1+(x_{1}x_{2}x_{3})^{16}x_{4}^{24}\right).\\ =&P_{x_{1}}(x)\cdot P_{x_{2}}(x)\cdot P_{x_{3}}(x)\cdot P_{y_{1}}(x)\cdot P_{x_{4}}(x)\cdot P_{\phi}(x).\end{array}

Characterization of complementing pairs of (ℤ≥0)n({\mathbb{Z}}_{\geq 0})^{n}

Abstract.

1. Introduction

Proposition 1.1.

Remark 1.2.

Remark 1.3.

1.1. Extension process

Theorem 1.1.

1.2. Weighted tree of an ℕ∗\mathbb{N}^{*}-pair.

Theorem 1.2.

Remark 1.4.

Example 1.1.

2. Uniqueness and primitivity

Lemma 2.1.

Proof.

Lemma 2.2.

Proof.

Lemma 2.3.

Lemma 2.4.

Lemma 2.5.

3. Extensions of ℕn\mathbb{N}^{n}-pairs

Lemma 3.1.

Proof.

Lemma 3.2.

Proof.

Lemma 3.3.

Lemma 3.4.

Proof.

Theorem 3.1.

Proof.

4. ℕ∗\mathbb{N}^{*}-pairs of pure type

Lemma 4.1.

Proof.

Lemma 4.2.

Proof.

Theorem 4.1.

Proof.

5. A key Lemma

Lemma 5.1.

Proof.

6. Marginal pairs of ℕ∗\mathbb{N}^{*}-pairs

Lemma 6.1.

Proof.

Theorem 6.1.

Proof.

7. 11-face reduction of ℕ∗\mathbb{N}^{*}-pair

Lemma 7.1.

Proposition 7.2.

Proof.

Theorem 7.1.

Proof.

Theorem 7.2.

Proof.

8. Proof of Theorem 1.1

Lemma 8.1.

Proof.

Proof of Theorem 1.1..

9. Weighted tree of ℕ∗\mathbb{N}^{*}-pair

9.1. Weighted tree

Definition 9.1.

9.2. Constructing ℕ∗\mathbb{N}^{*}-pairs from weighted trees

Remark 9.2.

9.3. A closed formula of (T,𝒥)(T,{\mathcal{J}})

Theorem 9.1.

Proof.

10. Proof of Theorem 1.2 and an example

Proof of Theorem 1.2.

Example 10.1.

References

Characterization of complementing pairs of $({\mathbb{Z}}_{\geq 0})^{n}$

1.2. Weighted tree of an $\mathbb{N}^{*}$ -pair.

3. Extensions of $\mathbb{N}^{n}$ -pairs

4. $\mathbb{N}^{*}$ -pairs of pure type

6. Marginal pairs of $\mathbb{N}^{*}$ -pairs

7. $1$ -face reduction of $\mathbb{N}^{*}$ -pair

9. Weighted tree of $\mathbb{N}^{*}$ -pair

9.2. Constructing $\mathbb{N}^{*}$ -pairs from weighted trees

9.3. A closed formula of $(T,{\mathcal{J}})$