Construction of blocked designs with multi block variables

1.   Introduction

Regular two-level designs are widely used in factorial experiments. When the size of experimental units is large, inhomogeneity of experimental units has bad influences on estimating treatment effects (see, ^[1,2]). A useful way to reduce such bad influences is to block the experimental units into categories known as blocks. Thus, choosing optimal blocked regular two-level designs becomes an important issue.

As pointed out by ^[1], there are two kinds of blocking problems. One is called the single block variable problem which involves only one block variable and the other is called the multi block variables problem which considers two or more block variables. In the last decades, most of the literature were concerned with the single block variable problem. Sitter et al. ^[3], H. Chen and C. S. Cheng ^[4], R. C. Zhang and D. K. Park ^[5], and S. W. Cheng and C. F. J. Wu ^[6] respectively proposed different minimum aberration (MA) criteria which are suitable for selecting blocked designs with single block variable. Under these MA criteria, the construction methods of blocked designs with single block variable were discussed in ^[7,8,9].

Zhang et al. ^[10] proposed the general minimum lower-order confounding (GMC) criterion for choosing optimal regular two-level designs. The GMC criterion is preferable when there are some prior knowledge on the importance ordering of treatment effects. R. C. Zhang and R. Mukerjee ^[11] extended the GMC criterion to blocked designs with single block variable, referred as B-GMC criterion, and gave the construction methods of B-GMC blocked designs via complementary designs. From different considerations, ^[12] proposed another GMC criterion for blocked designs with single block variable, referred as B$^1$-GMC. Zhao et al. ^[13] and Zhao et al. ^[14] studied the construction methods of B$^1$-GMC designs. Zhang et al. ^[15] proposed multi-stage differential evolution algorithm for constrained $D$-optimal design. Gashi ^[16] considered symmetric block design.

Compared to the experiments involving a single block variable, the experiments involving multi block variables are often encountered in practice. As has been mentioned in ^[1], in the agricultural context, when designs are laid out in rectangular schemes, both row and column inhomogeneity effects probably exist in the soil. Another example of multi block variables problem is from ^[2], which considers comparing two gasoline additives by testing them on two cars with two drivers over two days. In this experiment, three variables, cars, drivers and days, have to be considered to partition the experimental units.

Despite the wide application background, the multi block variables problem is less studied due to its complexity. In particular, constructing optimal designs with multi block variables is considerably challenging. Under the MA criterion, ^[17] developed some rules for constructing optimal regular two-level blocked designs with multi block variables. Zhang et al. ^[18] extended the idea of the GMC criterion to the case of multi block variables problem and developed the blocked GMC criterion, called B$^2$-GMC criterion. Inheriting the advantage of the GMC criterion, a B$^2$-GMC design is particularly preferable when some prior information on importance ordering of treatment effects is present. Zhang et al. ^[18] tabulated some B$^2$-GMC designs with small numbers of treatment factors and small run sizes by computer search. When $n$ or $N$ is large, computer search becomes computationally challenging, where $N = 2^{n-m}$. Zhao et al. ^[19] studied the B$^2$-GMC criterion and constructed a small number of B$^2$-GMC designs. In this paper, the B$^2$-GMC designs with the number of treatment factors $n$ all over ${5N}/{16}+1\leq n \leq N-1$ are constructed. The construction results cover all that of ^[19]. The structures of the constructed B$^2$-GMC designs are concise and easy to implement.

The rest of the paper is organized as follows. Section 2 reviews the B$^2$-GMC criterion and introduces some notation. The construction methods of B$^2$-GMC designs are provided in Section 3. Section 4 gives concluding remarks. Some proofs are deferred to Appendix.

2.   Preliminaries: B$^2$-GMC criterion and notation

Let $q = n-m$ and $N = 2^{q}$. Denote the regular two-level saturated design as

in Yates order, where the columns $\mathit{\boldsymbol{1}}$, $\mathit{\boldsymbol{2}}, \ldots,$ and $\mathit{\boldsymbol{q}}$ are $q$ independent columns in the form of

where the superscript of each column denotes transpose, in $\mathit{\boldsymbol{1}}$ the entry $1$, followed by $-1$, is repeated $2^{q-1}$ times, and in $\mathit{\boldsymbol{2}}$ the two successive entries $1$'s, followed by two successive $-1$'s, are repeated $2^{q-2}$ times, $\ldots,$ and in $\mathit{\boldsymbol{q}}$ the $2^{q-1}$ successive entries $1$'s are followed by $2^{q-1}$ successive $-1$'s. The remaining columns in $\mathit{\boldsymbol{H}}_q$ are generated by taking the component-wise products of any $k$ of the $q$ independent columns, where $k = 2, 3, \ldots, q$. For example, the column $\mathit{\boldsymbol{1}}\mathit{\boldsymbol{2}}$ is generated by taking component-wise products of the independent columns $\mathit{\boldsymbol{1}}$ and $\mathit{\boldsymbol{2}}$. Denote $\mathit{\boldsymbol{H}}_{1} = \{\mathit{\boldsymbol{1}}\}, \quad \mathit{\boldsymbol{H}}_{r} = \{\mathit{\boldsymbol{H}}_{r-1}, \mathit{\boldsymbol{r}}, \mathit{\boldsymbol{r}}\mathit{\boldsymbol{H}}_{r-1}\}$ for $r = 2, \ldots, q$, where $\mathit{\boldsymbol{r}} \mathit{\boldsymbol{H}}_{r-1} = \{\mathit{\boldsymbol{r d}}: \mathit{\boldsymbol{d}} \in \mathit{\boldsymbol{H}}_{r-1}\}$ and $\mathit{\boldsymbol{H}}_{r}$ consists of the first $2^{r}-1$ columns of $\mathit{\boldsymbol{H}}_{q}$. Let $\mathit{\boldsymbol{F}}_{qr} = \{\mathit{\boldsymbol{q}}, \mathit{\boldsymbol{q}}\mathit{\boldsymbol{H}}_{r-1}\}$ for $r = 2, \ldots, q$, then $\mathit{\boldsymbol{F}}_{qr}$ consists of the first $2^{r-1}$ columns of $\mathit{\boldsymbol{F}}_{qq}$ and $\mathit{\boldsymbol{F}}_{qq}$ consists of the last $2^{q-1}$ columns of $\mathit{\boldsymbol{H}}_q$.

Suppose that the inhomogeneity of the units of an experiment comes from $s$ different sources, i.e., $s$ block variables, denoted as $b_1, b_2, \ldots, b_s$. Suppose the block variable $b_j$ has $2^{l_j}$ levels, i.e., the $2^{n-m}$ units are grouped into $2^{l_j}$ blocks with respect to the block variable $b_j$. Then there should be $l_j$ independent columns of $\mathit{\boldsymbol{H}}_q$ to implement such a blocking schedule. Such columns are called block columns in the following. Denote $F_j$ as the collection of the $l_j$ independent block columns corresponding to the block variable $b_j$. It is worth noting that the columns in $F_j$ have the following two relations:

$\rm(i)$ the $l_j$ columns in $F_j$ are independent of each other for $j = 1, 2, \ldots, s$;

$\rm(ii)$ a column from $F_j$ is not necessarily independent of the columns from $F_i$, $i\neq j$.

Clearly, when $s = 1$, the blocking problem with multi block variables reduces to that with a single block variable. For simplicity, we consider only the case of $l_j = 1$ for $j = 1, 2, \ldots, s$. Then there are $s$ block columns and each of them blocks the $2^{n-m}$ experimental units into $2$ groups. Here, we would like to emphasize that the $s$ block columns are not necessarily independent of each other.

Throughout the paper, we use $\mathit{\boldsymbol{D}} = (\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{D}}_b)$ to denote a blocked regular $2^{n-m}:2^s$ design, where $\mathit{\boldsymbol{D}}_t$ is a regular $2^{n-m}$ design, and $\mathit{\boldsymbol{D}}_b$ consists of $s$ block columns. We will not differentiate block variables, block columns, and block factors in the following. B. Tang and C. F. J. Wu ^[20] introduced the concept of isomorphism which helps to narrow down the search for optimal blocked designs in this paper. An isomorphism $\phi$ is a one-to-one mapping from $\mathit{\boldsymbol{H}}_q$ to $\mathit{\boldsymbol{H}}_q$ such that $\phi(\mathit{\boldsymbol{xy}}) = \phi(\mathit{\boldsymbol{x}})\phi(\mathit{\boldsymbol{y}})$ for every $\mathit{\boldsymbol{x}}\neq \mathit{\boldsymbol{y}} \in \mathit{\boldsymbol{H}}_q$. Two $2^{n-m}:2^s$ designs $\mathit{\boldsymbol{D}}^1 = (\mathit{\boldsymbol{D}}^1_t, \mathit{\boldsymbol{D}}^1_b)$ and $\mathit{\boldsymbol{D}}^2 = (\mathit{\boldsymbol{D}}^2_t, \mathit{\boldsymbol{D}}^2_b)$ are isomorphic if there exists an isomorphism $\phi$ that maps $\mathit{\boldsymbol{D}}^1_t$ onto $\mathit{\boldsymbol{D}}^2_t$, and $\mathit{\boldsymbol{D}}^1_b$ onto $\mathit{\boldsymbol{D}}^2_b$.

Zhang et al. ^[18] put forward the effect hierarchy principle for blocked designs with multi block variables as follows:

$\rm(i)$ Lower order treatment factorial effects are more likely to be important than higher order ones, and treatment factorial effects of the same order are equally likely to be important.

$\rm(ii)$ Lower order block factorial effects are more likely to be important than higher order ones, and block factorial effects of the same order are equally likely to be important.

$\rm(iii)$ All the interactions between treatment and block factors are negligible.

With the effect hierarchy principle and weak assumption of effects involving three or more factors are usually not important and negligible, ^[18] proposed the B$^2$-GMC criterion which considers only the confounding among the main effects and two-factor interactions. As a common assumption in the blocking issues, if a treatment effect is confounded with a potentially significant block effect, the treatment effect cannot be estimated. Thus, confounding of the main effects of treatment factors with any potentially significant block effect is not allowed. In the following, we always suppose the main effects and the two-factor interactions of the block factors are potentially significant.

Denote $^\#_{\, 1}\!C_{2}^{(p)}(\mathit{\boldsymbol{D}})$ as the number of main treatment effects which are aliased with $p$ two-treatment-factor interactions ($2$tfi's) but not with any potentially significant block effects, where $p = 0, 1, 2, \ldots, P$, $P = n(n-1)/2$. Similarly, $^\#_{\, 2}\!C_{2}^{(p)}(\mathit{\boldsymbol{D}})$ denotes the number of $2$tfi's which are aliased with the other $p$ $2$tfi's but not with any potentially significant block effects. Denote

A blocked design $\mathit{\boldsymbol{D}} = (\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{D}}_b)$ is called a B$^2$-GMC design if $\mathit{\boldsymbol{D}}$ sequentially maximizes (2.1). Let $^\#_{\, i}\!C_{j}^{(p)}(\mathit{\boldsymbol{D}}_t)$ be the number of $i$-th order effects which are aliased with $p$ $j$-th order effects of $\mathit{\boldsymbol{D}}_t$. Let

A $2^{n-m}$ design $\mathit{\boldsymbol{D}}_t$ is called a GMC design if $\mathit{\boldsymbol{D}}_t$ sequentially maximizes (2.2).

Let

i.e., $U(\mathit{\boldsymbol{D}}_b)$ contains the potentially significant block effects. As aforementioned, confounding between main treatment effects and potentially significant block effects is not allowed which leads to $\mathit{\boldsymbol{D}}_t \cap U(\mathit{\boldsymbol{D}}_b) = \emptyset$, the empty set, and consequently ${}^\#_{\, 1}\!C_{2}^{(p)}(\mathit{\boldsymbol{D}}) = {}^\#_{\, 1}\!C_{2}^{(p)}(\mathit{\boldsymbol{D}}_t)$, $p = 0, 1, 2, \ldots, P$.

As a preparation of deriving B$^2$-GMC designs, we introduce one more piece of notation. For $\mathit{\boldsymbol{D}}_t \subset \mathit{\boldsymbol{H}}_{q}$ and $\mathit{\boldsymbol{\gamma}} \in \mathit{\boldsymbol{H}}_{q}$, define

where $\#$ denotes the cardinality of a set, and $\mathit{\boldsymbol{d}}_{1} \mathit{\boldsymbol{d}}_{2}$ stands for the two-factor interaction of $\mathit{\boldsymbol{d}}_{1}$ and $\mathit{\boldsymbol{d}}_{2}$. Thus, $B_{2}(\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{\gamma}})$ equals the number of $2$tfi's of $\mathit{\boldsymbol{D}}_t$ appearing in the alias set that contains $\mathit{\boldsymbol{\gamma}}$.

3.   Constructions of B$^2$-GMC designs

3.1.   B$^2$-GMC designs with $\frac{5N}{16}+1 \leq n \leq \frac{N}{2}$

To construct B$^2$-GMC designs, one should first consider the first part in (2.1), i.e., ${}^\#_{\, 1}\!C_2(\mathit{\boldsymbol{D}})$. Recall that $^\#_{\, 1}\!C^{(p)}_2(\mathit{\boldsymbol{D}}) = {}^\#_{\, 1}\!C^{(p)}_2(\mathit{\boldsymbol{D}}_t)$ for $p = 0, 1, \ldots, P$, then choosing $\mathit{\boldsymbol{D}}$ to maximize ${}^\#_{\, 1}\!C_2(\mathit{\boldsymbol{D}})$ reduces to choosing $\mathit{\boldsymbol{D}}_t$ to maximize ${}^\#_{\, 1}\!C_2(\mathit{\boldsymbol{D}}_t)$.

A $2^{n-m}$ design $\mathit{\boldsymbol{D}}_{t}$ is said to have resolution $R$ if no $c$-factor interaction is confounded with any other interaction involving less than $R-c$ factors (see, ^[21]). Note that a $2^{n-m}$ design $\mathit{\boldsymbol{D}}_t$ with resolution at least IV has ${}^\#_{\, 1}\!C^{(0)}_2(\mathit{\boldsymbol{D}}_t) = n$ and ${}^\#_{\, 1}\!C^{(p)}_2(\mathit{\boldsymbol{D}}_t) = 0$ for $p = 1, \ldots P$. This implies that a $2^{n-m}$ design $\mathit{\boldsymbol{D}}_t$ with resolution at least IV must maximize ${}^\#_{\, 1}\!C_2(\mathit{\boldsymbol{D}}_t)$. When $\frac{5N}{16}+1 \leq n \leq \frac{N}{2}$, if $\mathit{\boldsymbol{D}}_t$ has resolution at least IV, then $\mathit{\boldsymbol{D}}_t\subset \mathit{\boldsymbol{F}}_{qq}$ (see, ^[22]). In the remaining part of this section, we suppose $\mathit{\boldsymbol{D}}_t\subset \mathit{\boldsymbol{F}}_{qq}$. By Lemma 1 in ^[13], to choose $\mathit{\boldsymbol{D}}_b$ from $\mathit{\boldsymbol{H}}_q$, there are two possibilities: (i) $\mathit{\boldsymbol{D}}_b\cap \mathit{\boldsymbol{F}}_{qq} = \emptyset$, and (ii) $\mathit{\boldsymbol{D}}_b\cap \mathit{\boldsymbol{F}}_{qq}\neq \emptyset$. As has been pointed out, when constructing B$^2$-GMC designs, there should be $\mathit{\boldsymbol{D}}_t\cap U(\mathit{\boldsymbol{D}}_b) = \emptyset$. This leads to the constraint

Certainly, for $\mathit{\boldsymbol{D}}_b$ in the case (i), $U(\mathit{\boldsymbol{D}}_b)\subset \mathit{\boldsymbol{H}}_{q-1}$ and thus $\mathit{\boldsymbol{D}}_b$ satisfies the constraint (3.1). For $\mathit{\boldsymbol{D}}_b$ in the case (ii), there must be $U(\mathit{\boldsymbol{D}}_b)\cap \mathit{\boldsymbol{F}}_{qq}\neq \emptyset$ resulting in the necessity to investigate the number of columns in $U(\mathit{\boldsymbol{D}}_b)\cap \mathit{\boldsymbol{F}}_{qq}$. The following lemma addresses this question.

Lemma 1. Let $\mathit{\boldsymbol{D}}_b$ be any $s$-projection of $\mathit{\boldsymbol{H}}_q$ with $\mathit{\boldsymbol{D}}_b\cap \mathit{\boldsymbol{F}}_{qq}\neq\emptyset$. If $2^k\leq s \leq 2^{k+1}-1$ for some $k\leq q-2$, then $\#\{U(\mathit{\boldsymbol{D}}_b)\cap{\mathit{\boldsymbol{F}}}_{qq}\}\geq2^{k}$.

The proof of Lemma 1 is lengthy and thus deferred to Appendix.

Lemmas 2 and 3 below are straightforward extensions of some results in ^[19] and ^[23], respectively. These two lemmas are helpful in deriving the construction methods of B$^2$-GMC designs.

Lemma 2. Let $\mathit{\boldsymbol{D}}_b$ be any $s$-projection of $\mathit{\boldsymbol{H}}_{q}$ with $2^k\leq s \leq 2^{k+1}-1$ for some $k\leq q-1$.

$\rm(i)$ If $\mathit{\boldsymbol{D}}_b \cap \mathit{\boldsymbol{F}}_{qq} = \emptyset$, then $\#\{U(\mathit{\boldsymbol{D}}_b)\cap \mathit{\boldsymbol{H}}_{q-1}\}\geq 2^{k+1}-1$ and the equality holds when $\mathit{\boldsymbol{D}}_b$ has $k+1$ independent columns.

$\rm(ii)$ If $\mathit{\boldsymbol{D}}_b \cap \mathit{\boldsymbol{F}}_{qq}\neq\emptyset$, then $\#\{U(\mathit{\boldsymbol{D}}_b)\cap \mathit{\boldsymbol{H}}_{q-1}\}\geq 2^k-1$ and the equality holds when $\mathit{\boldsymbol{D}}_b$ has $k+1$ independent columns.

$\rm(iii)$ If $\mathit{\boldsymbol{D}}_b \subset \mathit{\boldsymbol{H}}_{k+1}$, then $U(\mathit{\boldsymbol{D}}_b) = \mathit{\boldsymbol{H}}_{k+1}$.

$\rm(iv)$ If $\mathit{\boldsymbol{D}}_b \subset \mathit{\boldsymbol{H}}_{k}\cup \mathit{\boldsymbol{F}}_{q(k+1)}$, then $U(\mathit{\boldsymbol{D}}_b) = \mathit{\boldsymbol{H}}_{k}\cup \mathit{\boldsymbol{F}}_{q(k+1)}$.

Lemma 3. Suppose $\mathit{\boldsymbol{D}}_t$ consists of the last $n$ columns of $\mathit{\boldsymbol{H}}_q$. For any two columns $\mathit{\boldsymbol{\gamma}}_1$ and $\mathit{\boldsymbol{\gamma}}_2$ in $\mathit{\boldsymbol{H}}_{q-1}$, if $\mathit{\boldsymbol{\gamma}}_1$ is ahead of $\mathit{\boldsymbol{\gamma}}_2$ in Yates order, then $B_2(\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{\gamma}}_1)\geq B_2(\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{\gamma}}_2)$.

Combining Lemmas 1, 2 and 3, the following theorem provides the constructions of B$^2$-GMC designs with $\frac{5N}{16}+1\leq n \leq \frac{N}{2}$, where $N\geq 16$.

Theorem 1. Suppose $\mathit{\boldsymbol{D}} = (\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{D}}_b)$ is a $2^{n-m}:2^s$ design with $2^r\leq \frac{N}{2}-n\leq 2^{r+1}-1$ for some $r\leq q-3$ and $2^k\leq s \leq 2^{k+1}-1$ for some $k\leq q-2$. The design $\mathit{\boldsymbol{D}} = (\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{D}}_b)$ is a B$^2$-GMC design if $\mathit{\boldsymbol{D}}_t$ consists of the last $n$ columns of $\mathit{\boldsymbol{F}}_{qq}$ and

$\rm(i)$ $\mathit{\boldsymbol{D}}_b$ is any $s$-projection of $\mathit{\boldsymbol{H}}_{k}\cup \mathit{\boldsymbol{F}}_{q(k+1)}$ when $1\leq k\leq r$,

$\rm(ii)$ $\mathit{\boldsymbol{D}}_b$ is any $s$-projection of $\mathit{\boldsymbol{H}}_{k+1}$ when $r+1 \leq k \leq q-2$.

Proof. Let $\mathit{\boldsymbol{D}}^{*} = (\mathit{\boldsymbol{D}}_t^{*}, \mathit{\boldsymbol{D}}_b^*)$ be a $2^{n-m}:2^s$ design with $\mathit{\boldsymbol{D}}_t^{*}\subset \mathit{\boldsymbol{F}}_{qq}$ and $U(\mathit{\boldsymbol{D}}_b^{*}) \subset \mathit{\boldsymbol{H}}_{q}\backslash \mathit{\boldsymbol{D}}_t^*$. According to Lemma 1 of ^[22],

where $\bar{\mathit{\boldsymbol{D}}}_{t}^{*} = \mathit{\boldsymbol{F}}_{qq}\backslash \mathit{\boldsymbol{D}}_t^*$. Note that $\mathit{\boldsymbol{D}}_t$ has resolution at least IV, then ${}^\#_{\, 1}\!C_{2}$ is maximized by $\mathit{\boldsymbol{D}}$. Therefore, we consider only ${}^\#_{\, 2}\!C_{2}$ in (2.1) in the following.

For (i). From Theorem 2 of ^[22], $\mathit{\boldsymbol{D}}_t$ is a GMC $2^{n-m}$ design and thus $\mathit{\boldsymbol{D}}_t$ maximizes (2.2) among all $\mathit{\boldsymbol{D}}_t^*$. From Lemma 2 (iv), if $\mathit{\boldsymbol{D}}_b$ is any $s$-projection of $\mathit{\boldsymbol{H}}_{k}\cup \mathit{\boldsymbol{F}}_{q(k+1)}$, then $U(\mathit{\boldsymbol{D}}_b) = \mathit{\boldsymbol{H}}_{k}\cup \mathit{\boldsymbol{F}}_{q(k+1)}$. Suppose $\mathit{\boldsymbol{\gamma}}_0$ is the last column of $\mathit{\boldsymbol{H}}_{k}$ in Yates order and $B_{2}(\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{\gamma}}_0) = p_0$, where $p_0\geq n-\frac{N}{4}\geq \frac{N}{16}+1 \geq 2$. From Lemma 3, for any $\mathit{\boldsymbol{\gamma}}\in \mathit{\boldsymbol{H}}_{k}$, we have $B_{2}(\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{\gamma}})\geq p_0$. Since $\mathit{\boldsymbol{D}}_t\subset \mathit{\boldsymbol{F}}_{qq}$, we have $B_{2}(\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{\gamma}}) = 0$ for any $\mathit{\boldsymbol{\gamma}}\in \mathit{\boldsymbol{F}}_{qq}$. By the definition of ${}^\#_{\, 2}\!C_{2}^{(p)}(\mathit{\boldsymbol{D}})$, when $p\leq p_0-2$, we have $1\leq p+1\leq p_0-1$ and

From Lemma 3, for any $\mathit{\boldsymbol{\gamma}}\in \mathit{\boldsymbol{H}}_{q}\backslash\mathit{\boldsymbol{H}}_{k}$, we have $B_{2}(\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{\gamma}})\leq p_0$. Therefore, when $p\geq p_0$, we have

From (3.2), we obtain that $\mathit{\boldsymbol{D}}$ sequentially maximizes

among all $\mathit{\boldsymbol{D}}^*$ since $\mathit{\boldsymbol{D}}_t$ is a GMC design.

Suppose $\mathit{\boldsymbol{D}}$ is not a B$^2$-GMC design, then there exists a $\mathit{\boldsymbol{D}}^*$ and some $p_1\geq p_0-1$ such that

and

Recall the definitions of ${}^\#_{\, 2}\!C_{2}^{(p)}(\mathit{\boldsymbol{D}})$ and ${}^\#_{\, 2}\!C_{2}^{(p)}(\mathit{\boldsymbol{D}}_t)$, we have

where the second equality is due to $B_{2}(\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{\gamma}}) = 0$ for any $\mathit{\boldsymbol{\gamma}}\in \mathit{\boldsymbol{F}}_{qq}$. From (3.6), it is obtained that

By (3.2), (3.3) and (3.7), it is obtained that

Similarly, for $\mathit{\boldsymbol{D}}^*$ we have

From (3.2)–(3.5), we obtain

Then it leads to $\#\{U(\mathit{\boldsymbol{D}}_b^*)\cap \mathit{\boldsymbol{H}}_{q-1}\} < 2^{k}-1$ from Eqs (3.8) and (3.9). This contradicts Lemma 2 (ii) and completes the proof of (i).

For (ii). From Lemma 1, if $\mathit{\boldsymbol{D}}_b^*\cap \mathit{\boldsymbol{F}}_{qq} \neq \emptyset$, then $\#\{U(\mathit{\boldsymbol{D}}_b^*) \cap\mathit{\boldsymbol{F}}_{qq}\} \geq 2^{k}\geq 2^{r+1}$ which implies $U(\mathit{\boldsymbol{D}}_b^{*})\cap \mathit{\boldsymbol{D}}_t^{*} \neq \emptyset$. This is not allowed as has been pointed out. Therefore, if $r+1 \leq k \leq q-2$, there should be $\mathit{\boldsymbol{D}}_b^* \subset \mathit{\boldsymbol{H}}_{q-1}$. According to Lemma 2 (iii), if $\mathit{\boldsymbol{D}}_b$ is an $s$-projection of $\mathit{\boldsymbol{H}}_{k+1}$, then $U(\mathit{\boldsymbol{D}}_b) = \mathit{\boldsymbol{H}}_{k+1}$. The remainder of the proof is similar to that of (i) and omitted. This completes the proof.

In the following, an example is provided to illustrate the constructions of B$^2$-GMC $2^{n-m}:2^s$ designs with $\frac{5N}{16} +1 \leq n \leq \frac{N}{2}$.

Example 1. Consider constructing B$^2$-GMC $2^{12-7}:2^2$ and $2^{12-7}:2^{9}$ designs. For both B$^2$-GMC designs to be constructed, we have $q = n-m = 5$, $N = 32$ and $r = 2$ as $2^2\leq \frac{N}{2}-n \leq 2^3-1$. The values of the parameters $N$ and $n$ satisfy $\frac{5N}{16} +1 \leq n \leq \frac{N}{2}$. Therefore, to construct these two B$^2$-GMC designs, $\mathit{\boldsymbol{D}}_t$ should be the last $12$ columns of $\mathit{\boldsymbol{F}}_{55}$.

For the case $2^{12-7}:2^2$, we have $s = 2$ which gives $k = 1$. Therefore, we should choose $2$ block columns according to Theorem 1 (i) as $k < r$. Without loss of generality, let $\mathit{\boldsymbol{D}}_{b1} = \{\mathit{\boldsymbol{1}}, \mathit{\boldsymbol{5}} \}$ be the $2$-projection of $\mathit{\boldsymbol{H}}_1\cup \mathit{\boldsymbol{F}}_{52}$. Then $\mathit{\boldsymbol{D}} = (\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{D}}_{b1})$ is a B$^2$-GMC $2^{12-7}:2^2$ design.

For the case $2^{12-7}:2^9$, we have $s = 9$ which gives $k = 3$. Therefore, we should choose $9$ block columns according to Theorem 1 (ii) as $k > r$. Without loss of generality, let $\mathit{\boldsymbol{D}}_{b2} = \{\mathit{\boldsymbol{1}}, \mathit{\boldsymbol{2}}, \mathit{\boldsymbol{12}}, \mathit{\boldsymbol{3}}, \mathit{\boldsymbol{13}}, \mathit{\boldsymbol{23}}, \mathit{\boldsymbol{123}}, \mathit{\boldsymbol{4}}, \mathit{\boldsymbol{14}} \}$ be the $9$-projection of $\mathit{\boldsymbol{H}}_4$. Then $\mathit{\boldsymbol{D}} = (\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{D}}_{b2})$ is a B$^2$-GMC $2^{9-4}:2^9$ design.

3.2.   B$^2$-GMC designs with $n > \frac{N}{2}$

Similar to the discussion in the first paragraph of Section 3.1, when constructing B$^2$-GMC designs with $n > \frac{N}{2}$, we should also first maximize ${}^\#_{\, 1}\!C_2(\mathit{\boldsymbol{D}}_t)$. Suppose the number of columns in $\mathit{\boldsymbol{H}}_q \backslash \mathit{\boldsymbol{D}}_t$ satisfies $2^r\leq N-1-n \leq 2^{r+1}-1$ for some $r\leq q-2$. According to the first paragraph of Section 3.2 in ^[22], when $n > \frac{N}{2}$, if $\mathit{\boldsymbol{D}}_t$ maximizes $^\#_{\, 1}\!C_2(\mathit{\boldsymbol{D}}_t)$, then $\mathit{\boldsymbol{H}}_q \backslash \mathit{\boldsymbol{D}}_t \subset \mathit{\boldsymbol{H}}_{r+1}$ up to isomorphism. This implies that $\mathit{\boldsymbol{D}}_b\subset \mathit{\boldsymbol{H}}_{r+1}$.

Suppose $2^k\leq s \leq 2^{k+1}-1$ for some $k\leq q-2$. According to Lemma 2 (i) and (ii) combined with Lemma 1, we have $\#U(\mathit{\boldsymbol{D}}_b)\geq 2^{k+1}-1$ no matter $\mathit{\boldsymbol{D}}_b\cap\mathit{\boldsymbol{F}}_{qq} = \emptyset$ or $\mathit{\boldsymbol{D}}_b\cap\mathit{\boldsymbol{F}}_{qq}\neq \emptyset$. Therefore, there should be $k = r$ with $N-1-n = 2^{k+1}-1$ or $k < r$, otherwise $U(\mathit{\boldsymbol{D}}_b) \cap \mathit{\boldsymbol{D}}_t\neq \emptyset$. For the case of $k = r$ with $N-1-n = 2^{k+1}-1$, it is trivial since $\mathit{\boldsymbol{D}}_t = \mathit{\boldsymbol{H}}_{q}\backslash\mathit{\boldsymbol{H}}_{k+1}$ and thus $\mathit{\boldsymbol{D}}_b \subset\mathit{\boldsymbol{H}}_{k+1}$. This obtains that the design $\mathit{\boldsymbol{D}} = (\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{D}}_b)$ with $\mathit{\boldsymbol{D}}_t = \mathit{\boldsymbol{H}}_{q}\backslash\mathit{\boldsymbol{H}}_{k+1}$ and $\mathit{\boldsymbol{D}}_b$ being any $s$-projection of $\mathit{\boldsymbol{H}}_{k+1}$ is a B$^2$-GMC design. The following theorem considers the constructions of B$^2$-GMC designs for the case of $k < r$.

Theorem 2. Suppose $\mathit{\boldsymbol{D}} = (\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{D}}_b)$ is a $2^{n-m}:2^s$ design with $2^r\leq N-1-n \leq 2^{r+1}-1$ for some $r\leq q-2$ and $2^k\leq s \leq 2^{k+1}-1$ for some $k < r$. The design $\mathit{\boldsymbol{D}} = (\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{D}}_b)$ is a B$^2$-GMC design if $\mathit{\boldsymbol{D}}_t$ consists of the last $n$ columns of $\mathit{\boldsymbol{H}}_{q}$ and $\mathit{\boldsymbol{D}}_b$ is any $s$-projection of $\mathit{\boldsymbol{H}}_{k+1}$.

Proof. Let $\mathit{\boldsymbol{D}}^{*} = (\mathit{\boldsymbol{D}}_t^{*}, \mathit{\boldsymbol{D}}_b^*)$ be a $2^{n-m}:2^s$ design with $\mathit{\boldsymbol{H}}_{q}\backslash \mathit{\boldsymbol{D}}_t^{*}\subset \mathit{\boldsymbol{H}}_{r+1}$. Then we have $U(\mathit{\boldsymbol{D}}_b^{*}) \subset \mathit{\boldsymbol{H}}_{q}\backslash \mathit{\boldsymbol{D}}_t^*$. From Lemma 3 of ^[22],

where $\bar{\mathit{\boldsymbol{D}}}_{t}^{*} = \mathit{\boldsymbol{H}}_q\backslash \mathit{\boldsymbol{D}}_t^*$.

By Lemma 2 (iv), if $\mathit{\boldsymbol{D}}_b$ is any $s$-projection of $\mathit{\boldsymbol{H}}_{k+1}$, then $U(\mathit{\boldsymbol{D}}_b) = \mathit{\boldsymbol{H}}_{k+1}$. Suppose $\mathit{\boldsymbol{\gamma}}_0$ is the last column of $\mathit{\boldsymbol{H}}_{k+1}$ in Yates order and $B_2(\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{\gamma}}_0) = p_0$, where $p_0\geq \frac{N}{2}-2^r > n-\frac{N}{2}\geq 1$. From Lemma 3, if $\mathit{\boldsymbol{\gamma}}\in \mathit{\boldsymbol{H}}_{k+1}$, then $B_{2}(\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{\gamma}})\geq p_0$. By the definition of ${}^\#_{\, 2}\!C_{2}^{(p)}(\mathit{\boldsymbol{D}})$, when $p\leq p_0-2$, we have $1\leq p+1\leq p_0-1$ and

From Lemma 3, for any $\mathit{\boldsymbol{\gamma}}\in \mathit{\boldsymbol{H}}_{q}\backslash\mathit{\boldsymbol{H}}_{k+1}$, we have $B_{2}(\mathit{\boldsymbol{D}}_t, \mathit{\boldsymbol{\gamma}})\leq p_0$. Therefore, when $p\geq p_0$, we have

Since $\mathit{\boldsymbol{D}}_t$ consists of the last $n$ columns of $\mathit{\boldsymbol{H}}_q$, from Theorem 3 of ^[22], $\mathit{\boldsymbol{D}}_t$ is a GMC $2^{n-m}$ design. Then $\mathit{\boldsymbol{D}}_t$ sequentially maximizes (2.2). Recall that $^\#_{\, 1}\!C^{(p)}_2(\mathit{\boldsymbol{D}}) = {}^\#_{\, 1}\!C^{(p)}_2(\mathit{\boldsymbol{D}}_t)$ for $p = 0, 1, \ldots, P$. Thus, (3.10) implies that $\mathit{\boldsymbol{D}}$ maximizes

among all $\mathit{\boldsymbol{D}}^*$.

Suppose $\mathit{\boldsymbol{D}}$ is not a B$^2$-GMC design, then there exists a $\mathit{\boldsymbol{D}}^*$ and some $p_1\geq p_0-1$ such that

and ${}^\#_{\, 2}\!C_{2}^{(p_1)}(\mathit{\boldsymbol{D}}^*) > {}^\#_{\, 2}\!C_{2}^{(p_1)}(\mathit{\boldsymbol{D}})$. With a similar argument to the proof of Theorem 1 (i), such a $\mathit{\boldsymbol{D}}^{*}$ results in $\#\{U(\mathit{\boldsymbol{D}}^*_b)\cap\mathit{\boldsymbol{H}}_{q-1}\} < 2^{k+1}-1$ which contradicts Lemma 2 (i). This completes the proof.

In the following, an example is provided to illustrate the constructions of B$^2$-GMC $2^{n-m}:2^s$ designs with $n > \frac{N}{2}$.

Example 2. Consider constructing B$^2$-GMC $2^{9-5}:2^2$ and $2^{12-8}:2^{3}$ designs.

For the case $2^{9-5}:2^2$, we have $q = n-m = 4$, $N = 16$ and $r = 2$ as $2^2\leq N-n-1 \leq 2^3-1$. Since $s = 2$, we obtain $k < r$ as $k = 1$. According to Theorem 3.2, let $\mathit{\boldsymbol{D}}_{t1}$ be the last $9$ columns of $\mathit{\boldsymbol{H}}_4$, and $\mathit{\boldsymbol{D}}_{b1} = \{\mathit{\boldsymbol{1}}, \mathit{\boldsymbol{2}} \}$ be a $2$-projection of $\mathit{\boldsymbol{H}}_2$. Then $\mathit{\boldsymbol{D}} = (\mathit{\boldsymbol{D}}_{t1}, \mathit{\boldsymbol{D}}_{b1})$ is a B$^2$-GMC $2^{9-5}:2^2$ design.

For the case $2^{12-8}:2^{3}$, we have $q = n-m = 4$, $N = 16$ and $r = 1$ as $2^1\leq N-n-1 \leq 2^2-1$. Since $s = 3$, we obtain $k = r$ as $k = 1$. As discussed in the second paragraph in Section 3.2, let $\mathit{\boldsymbol{D}}_{t2}$ be the last $12$ columns of $\mathit{\boldsymbol{H}}_4$, and $\mathit{\boldsymbol{D}}_{b2} = \{\mathit{\boldsymbol{1}}, \mathit{\boldsymbol{2}}, \mathit{\boldsymbol{12}} \} = \mathit{\boldsymbol{H}}_2$. Then $\mathit{\boldsymbol{D}} = (\mathit{\boldsymbol{D}}_{t2}, \mathit{\boldsymbol{D}}_{b2})$ is a B$^2$-GMC $2^{12-8}:2^3$ design.

4.   Concluding remarks

Regular two-level factorial designs are widely used in factorial experiments. Inhomogeneity of the units has bad influences on estimating the treatment effects when size of experimental units is large. To reduce such bad influences, a useful way is to block the experimental units into categories. As has been pointed out in ^[1], there are two types of blocking problems. One is the single block variable problem and the other is the multi block variables problem. In the last decades, the single block variable problem was maturely investigated in the literature.

As has been exemplified in Section 1, multi block variables problem is more widely encountered in practice compared to the blocking problem with a single block variable. However, the studies on multi block variables problem are relatively primitive. The GMC criterion is welcome in the situations where the importance ordering of treatment effects is present. Zhang et al. ^[18] proposed the B$^2$-GMC criterion for choosing optimal blocked regular two-level designs. Construction methods on B$^2$-GMC designs can only be found in ^[19] in which the B$^2$-GMC designs of some $n$ from $\frac{5N}{16}+1 \leq n \leq \frac{N}{2}$ are constructed. In this paper, the B$^2$-GMC designs of $n$ all over $\frac{5N}{16}+1 \leq n \leq N-1$ are systemically constructed. The structures of the constructed B$^2$-GMC designs are concise and easy to implement.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant No. 11801331).

Conflict of interest

The authors declare that there is no conflict of interest.

Appendix: Proof of Lemma 1

We only need to prove $\#\{U(\mathit{\boldsymbol{D}}_b)\cap \mathit{\boldsymbol{F}}_{qq}\}\geq 2^k$ for the case of $s = 2^k$. Recall that

We have

Denote $\mathit{\boldsymbol{A}} = \mathit{\boldsymbol{D}}_b\cap\mathit{\boldsymbol{F}}_{qq}$ and $\mathit{\boldsymbol{E}} = \mathit{\boldsymbol{D}}_b\cap\mathit{\boldsymbol{H}}_{q-1}$. Then $\mathit{\boldsymbol{D}}_b = \mathit{\boldsymbol{A}}\cup \mathit{\boldsymbol{E}}$, $\mathit{\boldsymbol{A}}\cap \mathit{\boldsymbol{E}} = \emptyset$,

and

where $\mathit{\boldsymbol{A}}\otimes \mathit{\boldsymbol{E}} = \{\mathit{\boldsymbol{\gamma}}\in \mathit{\boldsymbol{H}}_q: \mathit{\boldsymbol{\gamma}} = \mathit{\boldsymbol{a}}\mathit{\boldsymbol{b}}, \mathit{\boldsymbol{a}}\in \mathit{\boldsymbol{A}}, \mathit{\boldsymbol{b}}\in\mathit{\boldsymbol{E}}\}$. Thus, it suffices to prove

for $\#\mathit{\boldsymbol{A}}+\#\mathit{\boldsymbol{E}} = 2^k$.

Regarding to the columns in $\mathit{\boldsymbol{A}}$ and $\mathit{\boldsymbol{E}}$, there are two cases:

(B1) $\#\mathit{\boldsymbol{A}} > \#\mathit{\boldsymbol{E}}$, or

(B2) $\#\mathit{\boldsymbol{A}}\leq \#\mathit{\boldsymbol{E}}$.

The global line of the remaining proof for Lemma 1 is as follows. In Lemma A.1, we first show that if (A.1) holds for the case (B1), then (A.1) holds for the case (B2). Afterwards, with Lemma A.2–A.5, we prove that (A.1) indeed holds for the case (B1).

Lemma A.1. Suppose that $\rm(A.1)$ holds for the case $\rm(B1)$, then $\rm(A.1)$ holds for the case $\rm(B2)$.

Proof. For the $\mathit{\boldsymbol{A}}$ and $\mathit{\boldsymbol{E}}$ in the case (B2), without loss of generality, we suppose $\mathit{\boldsymbol{q}}\in \mathit{\boldsymbol{A}}$. Then,

where $\tilde{\mathit{\boldsymbol{A}}} = \mathit{\boldsymbol{q}}(\mathit{\boldsymbol{A}}\backslash \mathit{\boldsymbol{q}})\subset \mathit{\boldsymbol{H}}_{q-1}$ and $\tilde{\mathit{\boldsymbol{E}}} = \{\mathit{\boldsymbol{q}}\}\cup\mathit{\boldsymbol{q}}\mathit{\boldsymbol{E}}\subset \mathit{\boldsymbol{F}}_{qq}$.

Note that $\#\tilde{\mathit{\boldsymbol{A}}} = \# \mathit{\boldsymbol{A}} -1 \leq 2^{k-1}-1$, $\#\tilde{\mathit{\boldsymbol{E}}} = \# \mathit{\boldsymbol{E}} +1\geq 2^{k-1}+1$ and $\#\tilde{\mathit{\boldsymbol{A}}} + \#\tilde{\mathit{\boldsymbol{E}}} = 2^k$, then $\#\tilde{\mathit{\boldsymbol{E}}} > \#\tilde{\mathit{\boldsymbol{A}}}$ and the case (B2) converts into the case (B1). Therefore, if (A.1) holds for the case (B1), then (A.1) holds for the case $\rm(B2)$. This completes the proof.

In the following, we only need to prove that (A.1) holds for the case (B1).

For $\mathit{\boldsymbol{A}}$ in the case (B1), we have $\#\mathit{\boldsymbol{A}}\geq 2^{k-1}+1$. Then, $\mathit{\boldsymbol{A}}$ has at least $k+1$ independent columns. We suppose $\mathit{\boldsymbol{A}}$ has $h+1 (\geq k+1)$ independent columns. Let $\mathit{\boldsymbol{e}}$ denote the $h$th independent column in $\mathit{\boldsymbol{H}}_{q}$ in Yates order. Up to isomorphism, $\mathit{\boldsymbol{A}}$ can be expressed as

where $\mathit{\boldsymbol{A}}_1$ has $h$ independent columns with $\mathit{\boldsymbol{A}}_1\subset \mathit{\boldsymbol{F}}_{qh}$ and $\{ \mathit{\boldsymbol{a}}_{1}, \mathit{\boldsymbol{a}}_{2}, \ldots, \mathit{\boldsymbol{a}}_{v} \}\subset \mathit{\boldsymbol{F}}_{qh}$.

For $\mathit{\boldsymbol{E}}$ in the case (B1), if $\#\mathit{\boldsymbol{E}} = 0$, then $\#\mathit{\boldsymbol{A}} = 2^{k}$ and (A.1) holds. In the following, we consider only $1\leq\#\mathit{\boldsymbol{E}} \leq 2^{k-1}-1$. Up to isomorphism, there are three cases for the columns in $\mathit{\boldsymbol{E}}$:

(C1) all the columns are from $\mathit{\boldsymbol{H}}_{h-1}$;

(C2) some columns are from $\mathit{\boldsymbol{H}}_{h-1}$ and the others are from $\mathit{\boldsymbol{H}}_{h}\backslash \mathit{\boldsymbol{H}}_{h-1}$;

(C3) some columns are from $\mathit{\boldsymbol{H}}_{h-1}$, some are from $\mathit{\boldsymbol{H}}_{h}\backslash \mathit{\boldsymbol{H}}_{h-1}$ and the others are from $\mathit{\boldsymbol{H}}_{q}\backslash \mathit{\boldsymbol{H}}_{h}$.

We first consider the case (C2) with $h > k$. Note that $\mathit{\boldsymbol{A}}\cup \mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{E}} = \mathit{\boldsymbol{A}}\otimes (\{\mathit{\boldsymbol{I}}_N\}\cup \mathit{\boldsymbol{E}})$. Denote $\mathit{\boldsymbol{B}} = \{\mathit{\boldsymbol{I}}_{N}\}\cup\mathit{\boldsymbol{E}}$. Then $\mathit{\boldsymbol{B}}$ can be represented as

where $\mathit{\boldsymbol{I}}_{N} \in \mathit{\boldsymbol{B}}_1$, $\mathit{\boldsymbol{B}}_1\backslash \{\mathit{\boldsymbol{I}}_N\}\subset \mathit{\boldsymbol{H}}_{h-1}$ and $\{\mathit{\boldsymbol{b}}_{1}, \ldots, \mathit{\boldsymbol{b}}_{w}\} \subset\mathit{\boldsymbol{H}}_{h-1}$.

Recall that $2^{k-1} < \#\mathit{\boldsymbol{A}}\leq 2^k-1 < 2^{h-1}$, we can always find a column $\mathit{\boldsymbol{r}}\in \mathit{\boldsymbol{H}}_{h-1}$ or $\mathit{\boldsymbol{r}} = \mathit{\boldsymbol{I}}_N$ such that at least one column in $\{ \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_1, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_2, \ldots, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_{v} \}$, say $\mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_1$, satisfies $(\mathit{\boldsymbol{re}}) (\mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_1) = \mathit{\boldsymbol{r}}\mathit{\boldsymbol{a}}_1 \in \mathit{\boldsymbol{F}}_{qh}\backslash \mathit{\boldsymbol{A}}_1$. Without loss of generality, we assume that there is some $t_1 (1 \leq t_1\leq v)$ such that $\mathit{\boldsymbol{re}}\{ \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_1, \ldots, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_{t_1} \}\subset \mathit{\boldsymbol{F}}_{qh}\backslash \mathit{\boldsymbol{A}}_1$ and $\mathit{\boldsymbol{r}}\mathit{\boldsymbol{e}}\{ \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_{t_1+1}, \ldots, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_{v} \}\subset \mathit{\boldsymbol{A}}_1$. Meanwhile, there is some $t_2 (0\leq t_2\leq w)$ such that $\mathit{\boldsymbol{r}}\mathit{\boldsymbol{e}}\{ \mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_1, \ldots, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_{t_2} \}\subset \mathit{\boldsymbol{H}}_{h-1}\backslash \mathit{\boldsymbol{B}}_1$ and $\mathit{\boldsymbol{r}}\mathit{\boldsymbol{e}}\{ \mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_{t_2+1}, \ldots, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_{w} \} \subset \mathit{\boldsymbol{B}}_1$.

Let $\mathit{\boldsymbol{A}}_2 = \{ \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_{t_1+1}, \ldots, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_{v} \}$ and $\mathit{\boldsymbol{A}}_3 = \{ \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_{1}, \ldots, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_{t_1} \}$. Then,

Let $\mathit{\boldsymbol{B}}_2 = \{ \mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_{t_2+1}, \ldots, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_{w} \}$ and $\mathit{\boldsymbol{B}}_3 = \{ \mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_{1}, \ldots, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_{t_2} \}$. Then,

Let

and

where $\mathit{\boldsymbol{A}}_3^* = \mathit{\boldsymbol{r}}\mathit{\boldsymbol{e}}\mathit{\boldsymbol{A}}_3$ and $\mathit{\boldsymbol{B}}_3^* = \mathit{\boldsymbol{r}}\mathit{\boldsymbol{e}}\mathit{\boldsymbol{B}}_3$.

Lemma A.2. Suppose $\mathit{\boldsymbol{A}}, \mathit{\boldsymbol{B}}, \mathit{\boldsymbol{A}}^*$ and $\mathit{\boldsymbol{B}}^*$ are defined as in (A.4)–(A.7), respectively, then $\#\{\mathit{\boldsymbol{A}}^*\otimes\mathit{\boldsymbol{B}}^*\}\leq \#\{\mathit{\boldsymbol{A}}\otimes \mathit{\boldsymbol{B}}\}$.

Proof. Let

Since $\mathit{\boldsymbol{re}}\mathit{\boldsymbol{A}}_2 \subset \mathit{\boldsymbol{A}}_1$ and $\mathit{\boldsymbol{re}}\mathit{\boldsymbol{B}}_2 \subset \mathit{\boldsymbol{B}}_1$, we have $\mathit{\boldsymbol{A}}_2\otimes\mathit{\boldsymbol{B}}_2\subset \mathit{\boldsymbol{Q}}_2$. Thus

Since $\mathit{\boldsymbol{Q}}_1\cup\mathit{\boldsymbol{Q}}_3 \subset \mathit{\boldsymbol{F}}_{q(h+1)}\backslash \mathit{\boldsymbol{F}}_{qh}$ and $\mathit{\boldsymbol{Q}}_2\cup\mathit{\boldsymbol{Q}}_4 \subset \mathit{\boldsymbol{F}}_{qh}$ are mutually exclusive, thus

Note that $\mathit{\boldsymbol{A}}_3^*\otimes\mathit{\boldsymbol{B}}_3^* = \mathit{\boldsymbol{A}}_3 \otimes\mathit{\boldsymbol{B}}_3$, then

Since $\mathit{\boldsymbol{Q}}_1\cup \mathit{\boldsymbol{Q}}_3^* \subset \mathit{\boldsymbol{F}}_{q(h+1)}\backslash \mathit{\boldsymbol{F}}_{qh}$ and $\mathit{\boldsymbol{Q}}_2\cup \mathit{\boldsymbol{Q}}_4^* \subset \mathit{\boldsymbol{F}}_{qh}$ are mutually exclusive, thus

where the third equality is due to $\mathit{\boldsymbol{r}}\mathit{\boldsymbol{e}}\mathit{\boldsymbol{Q}}_3^{*} = \mathit{\boldsymbol{Q}}_4$ and $\mathit{\boldsymbol{r}}\mathit{\boldsymbol{e}}\mathit{\boldsymbol{Q}}_4^{*} = \mathit{\boldsymbol{Q}}_3$. Therefore, to prove Lemma A.2, it suffices to prove

or equivalently

Note that $\mathit{\boldsymbol{A}}_2 \subset \mathit{\boldsymbol{r}}\mathit{\boldsymbol{e}}\mathit{\boldsymbol{A}}_1$ and $\mathit{\boldsymbol{B}}_2 \subset \mathit{\boldsymbol{r}}\mathit{\boldsymbol{e}}\mathit{\boldsymbol{B}}_1$, then

and

which implies that $\mathit{\boldsymbol{Q}}_4 \subset \mathit{\boldsymbol{Q}}_4^*$. Similarly, we can obtain $\mathit{\boldsymbol{Q}}_3^*\subset \mathit{\boldsymbol{Q}}_3$. Therefore, (A.8) is equivalent to

Thus, we only need to prove (A.9).

For the left hand side of (A.9), we have

For the right hand side of (A.9), we have

Since $\mathit{\boldsymbol{re}}\mathit{\boldsymbol{Q}}_1 = (\mathit{\boldsymbol{A}}_1\otimes(\mathit{\boldsymbol{re}}\mathit{\boldsymbol{B}}_2)) \cup ((\mathit{\boldsymbol{re}}\mathit{\boldsymbol{A}}_2)\otimes\mathit{\boldsymbol{B}}_1) \subset \mathit{\boldsymbol{A}}_1\otimes\mathit{\boldsymbol{B}}_1$, we have $\mathit{\boldsymbol{re}}\mathit{\boldsymbol{Q}}_1\subset \mathit{\boldsymbol{Q}}_2$. Then (A.9) holds. This completes the proof of Lemma A.2.

Remark 1. Lemma A.2 indicates that for any $\mathit{\boldsymbol{A}}$ defined in (A.2) and $\mathit{\boldsymbol{B}}$ defined in (A.3), we can always find $\mathit{\boldsymbol{A}}^*$, which has less columns out of $\mathit{\boldsymbol{F}}_{qh}$ than $\mathit{\boldsymbol{A}}$, and $\mathit{\boldsymbol{B}}^{*}$, which has no more columns out of $\mathit{\boldsymbol{H}}_{h-1}$ than $\mathit{\boldsymbol{B}}$, such that $\#\{ \mathit{\boldsymbol{A}}^{*}\otimes \mathit{\boldsymbol{B}}^* \}\leq \#\{\mathit{\boldsymbol{A}}\otimes \mathit{\boldsymbol{B}}\}$. Repeatedly applying Lemma A.2, we can finally find $\mathit{\boldsymbol{A}}^{**}\subset \mathit{\boldsymbol{F}}_{qh}$ and $\mathit{\boldsymbol{B}}^{**}$, which has no more columns out of $\mathit{\boldsymbol{H}}_{h-1}$ than $\mathit{\boldsymbol{B}}$, such that $\#\{\mathit{\boldsymbol{A}}^{**} \otimes \mathit{\boldsymbol{B}}^{**}\} \leq \#\{\mathit{\boldsymbol{A}}\otimes \mathit{\boldsymbol{B}}\}$.

For simplicity of notation, we still denote $\mathit{\boldsymbol{A}}^{**}$ as $\mathit{\boldsymbol{A}}$ and $\mathit{\boldsymbol{B}}^{**}$ as $\mathit{\boldsymbol{B}}$. Then we can assume that $\mathit{\boldsymbol{A}}\subset \mathit{\boldsymbol{F}}_{qh}$. Note that there might be $t_2 = 0$ in the procedure above. Then, following Remark 1, $\mathit{\boldsymbol{B}}$ has the following cases:

(D1) $\mathit{\boldsymbol{B}}\backslash \{\mathit{\boldsymbol{I}}_N\} \subset \mathit{\boldsymbol{H}}_{h-1}$, or

(D2) $(\mathit{\boldsymbol{B}}\backslash \{\mathit{\boldsymbol{I}}_N\}) \cap (\mathit{\boldsymbol{H}}_{h}\backslash \mathit{\boldsymbol{H}}_{h-1}) \neq \emptyset$,

For the case (D2), we write $\mathit{\boldsymbol{B}}$ as $\mathit{\boldsymbol{B}} = \mathit{\boldsymbol{B}}_1\cup \{\mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_1, \ldots, \mathit{\boldsymbol{eb}}_{t_3}\}$, where $\mathit{\boldsymbol{I}}_N\in \mathit{\boldsymbol{B}}_1$, $\mathit{\boldsymbol{B}}_1\backslash \{\mathit{\boldsymbol{I}}_{N}\}\subset \mathit{\boldsymbol{H}}_{h-1}$ and $\{\mathit{\boldsymbol{b}}_1, \ldots, \mathit{\boldsymbol{b}}_{t_3}\} \subset \mathit{\boldsymbol{H}}_{h-1}$. Note that $1\leq \#(\mathit{\boldsymbol{B}}\backslash \{\mathit{\boldsymbol{I}}_N\})\leq 2^{k-1}-1 < 2^{h-1}-1$. We can always find a column $\mathit{\boldsymbol{r}}_1\in\mathit{\boldsymbol{H}}_{h-1}$ or $\mathit{\boldsymbol{r}}_1 = \mathit{\boldsymbol{I}}_N$ such that at least one column in $\{\mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_1, \ldots, \mathit{\boldsymbol{eb}}_{t_3}\}$, say $\mathit{\boldsymbol{eb}}_1$, satisfies $(\mathit{\boldsymbol{r}}_1\mathit{\boldsymbol{e}})(\mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_1) = \mathit{\boldsymbol{r}}_1\mathit{\boldsymbol{b}}_1 \in \mathit{\boldsymbol{H}}_{h-1}\backslash \mathit{\boldsymbol{B}}_1$. Without loss of generality, suppose there is some $t_4$ with $1\leq t_4\leq t_3$ such that $\mathit{\boldsymbol{r_1}}\mathit{\boldsymbol{e}}\{\mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_1, \ldots, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_{t_4}\}\subset \mathit{\boldsymbol{H}}_{h-1}\backslash\mathit{\boldsymbol{B}}_1$ and $\mathit{\boldsymbol{r_1}}\mathit{\boldsymbol{e}}\{ \mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_{t_4+1}, \ldots, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{b}}_{t_3}\}\subset \mathit{\boldsymbol{B}}_1$. Denote $\mathit{\boldsymbol{B}}_2 = \{\mathit{\boldsymbol{eb}}_{t_4+1}, \ldots, \mathit{\boldsymbol{eb}}_{t_3}\}$ and $\mathit{\boldsymbol{B}}_3 = \{\mathit{\boldsymbol{eb}}_{1}, \ldots, \mathit{\boldsymbol{eb}}_{t_4}\}$, then

Denote

where $\mathit{\boldsymbol{B}}_3^* = \mathit{\boldsymbol{r}}_1\mathit{\boldsymbol{e}}\mathit{\boldsymbol{B}}_3$.

Lemma A.3. Suppose $\mathit{\boldsymbol{A}}\subset \mathit{\boldsymbol{F}}_{qh}$, $\mathit{\boldsymbol{B}}$ and $\mathit{\boldsymbol{B}}^*$ are defined as in (A.10) and (A.11), respectively, then $\#\{\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}^*\}\leq \#\{\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}\}$.

Proof. Note that $\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}_1\subset \mathit{\boldsymbol{F}}_{qh}$ and $(\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}_2)\cup (\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}_3)\subset \mathit{\boldsymbol{F}}_{q(h+1)}\backslash\mathit{\boldsymbol{F}}_{qh}$. Therefore,

Since $(\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}_1)\cup (\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}_3^*)\subset\mathit{\boldsymbol{F}}_{qh}$ and $\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}_2 \subset \mathit{\boldsymbol{F}}_{q(h+1)}\backslash\mathit{\boldsymbol{F}}_{qh}$, we have

where the third equality is due to $\mathit{\boldsymbol{r}}_1\mathit{\boldsymbol{e}}(\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}_3^*) = \mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}_3$. On one hand,

On the other hand, $\mathit{\boldsymbol{B}}_2\subset \mathit{\boldsymbol{r}}_1\mathit{\boldsymbol{e}}\mathit{\boldsymbol{B}}_1$, which leads to

From (A.12) and (A.13), we obtain that

This implies $\#\{\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}^*\}\leq \#\{\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}\}$ and completes the proof.

Remark 2. By repeatedly applying Lemma A.3, we can finally find $\mathit{\boldsymbol{B}}^{*}\subset\mathit{\boldsymbol{H}}_{h-1}$ such that $\#\{\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}^*\}\leq \#\{\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}\}$. This result is also true for the cases (C1) and (C3) with $h > k$ due to the following reasons. When $\{ \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_1, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_2, \ldots, \mathit{\boldsymbol{e}}\mathit{\boldsymbol{a}}_{v} \} = \emptyset$, the case (C2) reduce to the case (C1). For the case (C3), with a similar argument to Lemma A.3, we can find a $\mathit{\boldsymbol{T}}$ with $\mathit{\boldsymbol{I}}_N\subset \mathit{\boldsymbol{T}}$ and $(\mathit{\boldsymbol{T}}\backslash \mathit{\boldsymbol{I}}_N) \subset \mathit{\boldsymbol{H}}_{h}$ such that $\#\{\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{T}}\} \leq \#\{\mathit{\boldsymbol{A}}\otimes\mathit{\boldsymbol{B}}\}$. Then the case (C3) reduces to case (C2).

The following remark considers the case of $h = k$.

Remark 3. For $h = k$, up to isomorphism, $\mathit{\boldsymbol{A}}\subset \mathit{\boldsymbol{F}}_{q(k+1)}$. In this situation, $h$ should equal to $k$ in the cases (C1), (C2) and (C3). Especially, in the cases (C1) and (C2), $\mathit{\boldsymbol{E}}$ is already a subset of $\mathit{\boldsymbol{H}}_{k}$. By repeatedly applying Lemma A.3 to $\mathit{\boldsymbol{E}}$ in the case (C3), we can find a set, say $\mathit{\boldsymbol{P}}$, such that $\mathit{\boldsymbol{P}} \subset \mathit{\boldsymbol{H}}_k$ and $\#\{\mathit{\boldsymbol{A}}\otimes (\{\mathit{\boldsymbol{I}}_N\}\cup \mathit{\boldsymbol{P}})\}\leq \#\{\mathit{\boldsymbol{A}}\otimes (\{\mathit{\boldsymbol{I}}_N\}\cup \mathit{\boldsymbol{E}})\}$.

In summary, for any $\mathit{\boldsymbol{A}}$ and $\mathit{\boldsymbol{B}}$ defined in (A.2) and (A.3), by repeatedly applying Lemma A.2 and A.3, we can always find $\mathit{\boldsymbol{A}}^*\subset \mathit{\boldsymbol{F}}_{q(k+1)}$ and $\mathit{\boldsymbol{B}}^*\backslash \{\mathit{\boldsymbol{I}}_N\}\subset \mathit{\boldsymbol{H}}_{k}$ with $\mathit{\boldsymbol{I}}_N\in \mathit{\boldsymbol{B}}^*$, such that $\#\{\mathit{\boldsymbol{A}}^*\otimes \mathit{\boldsymbol{B}}^*\} \leq \#\{\mathit{\boldsymbol{A}}\otimes \mathit{\boldsymbol{B}}\}$. Next, we denote $\mathit{\boldsymbol{A}}^*$ as $\mathit{\boldsymbol{A}}$ and $\mathit{\boldsymbol{B}}^*$ as $\mathit{\boldsymbol{B}}$ and prove that $\#\{\mathit{\boldsymbol{A}}\otimes \mathit{\boldsymbol{B}}\} = 2^k$ for any $\mathit{\boldsymbol{A}}\subset \mathit{\boldsymbol{F}}_{q(k+1)}$, $\mathit{\boldsymbol{B}}\backslash \{\mathit{\boldsymbol{I}}_N\}\subset \mathit{\boldsymbol{H}}_{k}$ with $\mathit{\boldsymbol{I}}_N\in \mathit{\boldsymbol{B}}$ and $\#\mathit{\boldsymbol{A}}+\#\mathit{\boldsymbol{B}} = 2^k$. We first introduce a useful lemma from ^[24].

Denote $I_{\mathit{\boldsymbol{S}}}$ as the set consisting of the distinct columns generated by taking component-wise products of any two columns of $\mathit{\boldsymbol{S}}$.

Lemma A.4. Let $\mathit{\boldsymbol{S}}$ be an $s$-subset of $\mathit{\boldsymbol{F}}_{qq}$, $s = 2^{k-1 }+ \delta \geq 3$ and $0 < \delta \leq 2^{k-1}$, then $\#I_{\mathit{\boldsymbol{S}}}\geq2^k-1$, where the equality holds when the number of independent columns of $\mathit{\boldsymbol{S}}$ is $k+1$.

Lemma A.5. Suppose $\mathit{\boldsymbol{A}}\subset \mathit{\boldsymbol{F}}_{q(k+1)}$, $\mathit{\boldsymbol{I}}_N\in \mathit{\boldsymbol{B}}$, $\mathit{\boldsymbol{B}}\backslash \mathit{\boldsymbol{I}}_N\subset \mathit{\boldsymbol{H}}_k$ with $\#\mathit{\boldsymbol{A}}+\#\mathit{\boldsymbol{B}} = 2^k+1$ and $k\leq q-2$, then $\#\{\mathit{\boldsymbol{A}}\otimes \mathit{\boldsymbol{B}}\} = 2^k$.

Proof. Without loss of generality, suppose $\mathit{\boldsymbol{e}}$ is the $(k+1)$th independent column in $\mathit{\boldsymbol{H}}_{q}$. Then $\#\{{\mathit{\boldsymbol{A}}\otimes \mathit{\boldsymbol{B}}}\} = \#\{\mathit{\boldsymbol{A}}\otimes(\mathit{\boldsymbol{e\bm{q}B}})\}$ and $\mathit{\boldsymbol{e\bm{q}B}}\subset \mathit{\boldsymbol{F}}_{q(k+2)}\backslash\mathit{\boldsymbol{F}}_{q(k+1)}$. Next, we show $\#\{\mathit{\boldsymbol{A}}\otimes(\mathit{\boldsymbol{e\bm{q}B}})\} = 2^k$. Since $\mathit{\boldsymbol{A}}\cap\mathit{\boldsymbol{e\bm{q}B}} = \emptyset$, we have $\#\{\mathit{\boldsymbol{A}}\cup\mathit{\boldsymbol{e\bm{q}B}}\} = \#\mathit{\boldsymbol{A}}+\#\{\mathit{\boldsymbol{e\bm{q}B}} \} = 2^k+1$ and $\mathit{\boldsymbol{A}}\cup \mathit{\boldsymbol{e\bm{q}B}}$ has $k+2$ independent columns. By Lemma A.4, we have

Note that $I_{\mathit{\boldsymbol{A}}}\cup I _{\mathit{\boldsymbol{eqB}}}\subset \mathit{\boldsymbol{H}}_{k}$ then $\#\{ I_{\mathit{\boldsymbol{A}}}\cup I _{\mathit{\boldsymbol{eqB}}}\}\leq 2^{k}-1$, and $\mathit{\boldsymbol{A}}\otimes(\mathit{\boldsymbol{eqB}})\subset \mathit{\boldsymbol{H}}_{k+1}\backslash \mathit{\boldsymbol{H}}_k$ then $\#\{\mathit{\boldsymbol{A}}\otimes(\mathit{\boldsymbol{eqB}})\}\leq 2^k$. From (A.14), there should be $\#\{ I_{\mathit{\boldsymbol{A}}}\cup I _{\mathit{\boldsymbol{eqB}}} \} = 2^{k}-1$ and $\#\{\mathit{\boldsymbol{A}}\otimes(\mathit{\boldsymbol{eqB}}) \} = 2^k$. This completes the proof.

Proof of Lemma 1. According to the proofs of Lemma A.2, A.3 and A.5, we can immediately obtain that $\#\{U(\mathit{\boldsymbol{D}}_b)\cap\mathit{\boldsymbol{F}}_{qq}\}\geq 2^k$. This completes the proof.