Optimal 2-D $(n\times m,3,2,1)$-optical orthogonal codes and related equi-difference conflict avoiding codes

Abstract

This paper focuses on constructions for optimal 2-D $(n\times m,3,2,1)$-optical orthogonal codes with $m\equiv 0\ (\mathrm{mod}\ 4)$. An upper bound on the size of such codes is established. It relies heavily on the size of optimal equi-difference 1-D (m, 3, 2, 1)-optical orthogonal codes, which is closely related to optimal equi-difference conflict avoiding codes with weight 3. The exact number of codewords of an optimal 2-D $(n\times m,3,2,1)$-optical orthogonal code is determined for $n=1,2$, $m\equiv 0 \pmod {4}$, and $n\equiv 0 \pmod {3}$, $m\equiv 8 \pmod {16}$ or $m\equiv 32 \pmod {64}$ or $m\equiv 4,20 \pmod {48}$.

1 Introduction

Let n, m, k, $\lambda _a$ and $\lambda _c$ be positive integers. A two-dimensional$(n\times m,k,\lambda _a,\lambda _c)$optical orthogonal code (briefly 2-D $(n\times m,k,\lambda _a,\lambda _c)$-OOC), ${\mathscr {C}}$, is a family of $n\times m$ (0, 1)-matrices (called codewords) of Hamming weight k satisfying the following two properties:

• (1) the autocorrelation property: for each matrix ${\mathbf {A}}=(a_{ij})_{n\times m}\in {\mathscr {C}}$ and each integer r, $r\not \equiv 0\ (\mathrm{mod}\ m)$,

  $$\begin{aligned} \sum _{i=0}^{n-1}\sum _{j=0}^{m-1}a_{ij}a_{i,j+r}\le \lambda _a; \end{aligned}$$

• (2) the cross-correlation property: for each matrix ${\mathbf {A}}=(a_{ij})_{n\times m}\in {\mathscr {C}}$, ${\mathbf {B}}=(b_{ij})_{n\times m}\in {\mathscr {C}}$ with ${\mathbf {A}}\ne {\mathbf {B}}$, and each integer r,

  $$\begin{aligned} \sum _{i=0}^{n-1}\sum _{j=0}^{m-1}a_{ij}b_{i,j+r}\le \lambda _c. \end{aligned}$$

where the arithmetic $j+r$ is reduced modulo m. When $n=1$, a two-dimensional $(1\times m,k,\lambda _a,\lambda _c)$ optical orthogonal code is said to be a one-dimensional$(m,k,\lambda _a,\lambda _c)$-optical orthogonal code, denoted by a 1-D $(m,k,\lambda _a,\lambda _c)$-OOC.

Optical orthogonal codes are widely used as spreading codes in optical fiber networks. 1-D OOC was first investigated systematically by Chung et al. [14]. 1-D OOCs have a drawback which requires a large chip rate. To overcome it, 2-D OOCs were proposed in [43], which spreads in both time and wavelength so that the chip rate requirement can be substantially reduced.

The number of codewords of a 2-D OOC is called its size. For fixed n, m, k, $\lambda _a$ and $\lambda _c$, the largest size among all 2-D $(n\times m,k,\lambda _a,\lambda _c)$-OOCs is denoted by $\varPhi (n\times m,k,\lambda _a,\lambda _c)$. A 2-D $(n\times m,k,\lambda _a,\lambda _c)$-OOC with $\varPhi (n\times m,k,\lambda _a,\lambda _c)$ codewords is said to be optimal. Naturally, a 1-D $(m,k,\lambda _a,\lambda _c)$-OOC is said to be optimal if it contains $\varPhi (1\times m,k,\lambda _a,\lambda _c)$ codewords.

When $\lambda _a=\lambda _c=\lambda$, various 2-D OOCs or 1-D OOCs were constructed based on algebraic and combinatorial methods (see [1,2,3,4,5,6,7, 10,11,12,13, 15, 16, 20, 21, 23, 24, 31, 34, 35, 38, 39, 44] and the references therein). Instead, very little has been done on optimal OOCs with $\lambda _a\ne \lambda _c$. Yang and Fuja [42] showed that the auto- and cross-correlation properties are used for synchronization and user identification, respectively, and in some circumstances only with good cross-correlation one can deal with both synchronization and user identification. This motivates the study of OOCs with better cross-correlation than auto-correlation. See [8, 9, 33, 36] for examples, in which the cases of $n=1$, $k\in \{4,5\}$, $\lambda _a=2$ and $\lambda _c=1$ are considered.

When $\lambda _a=k$ and $\lambda _c=1$, a 1-D (m, k, k, 1)-OOC is also called a conflict-avoiding code, denoted by a CAC(m, k), which can be viewed as a 1-D (m, k, 1)-OOC without the constraint of the auto-correlation property. A CAC finds its application on a multiple-access collision channel without feedback (cf. [22, 26]).

When m is even, optimal CAC(m, 3)s have been discussed thoroughly in [18, 25, 27, 30]. We summarize the results for later use.

Theorem 1

[18, 25, 27, 30] Let $m\equiv 0\ (\mathrm{mod}\ 2)$. The size of an optimal CAC(m, 3) (i.e., an optimal 1-D (m, 3, 3, 1)-OOC) is

$$\begin{aligned} \varPhi (1\times m,3,3,1)=\left\{ \begin{array}{ll} (m-2)/4, &{} m\equiv 2\ (\mathrm{mod}\ 4),\\ \lfloor (7m+16)/32\rfloor , &{} m\equiv 0\ (\mathrm{mod}\ 24) \ \mathrm{and}\ m\ne 48,\\ \lfloor (7m+4)/32\rfloor , &{} m\equiv 4,20\ (\mathrm{mod}\ 24),\\ \lfloor 7m/32\rfloor , &{} m\equiv 8,16\ (\mathrm{mod}\ 24)\ \mathrm{and}\ m\ne 64,\\ \lfloor (7m+20)/32\rfloor , &{} m\equiv 12\ (\mathrm{mod}\ 24),\\ \end{array} \right. \end{aligned}$$

with the exception of $\varPhi (1\times 48,3,3,1)=10$ and $\varPhi (1\times 64,3,3,1)=13.$

However, there are few results on optimal 2-D $(n\times m,k,2,1)$-OOCs when $n\ne 1$ in the literature. The only known results for $k=3$ is from [17, 40], which determined the size of an optimal 2-D $(n\times m,3,2,1)$-OOCs with $m\equiv 2\ (\mathrm{mod}\ 4)$. This paper continues the work in [17], and we are concerned about optimal 2-D $(n\times m,3,2,1)$-OOCs with $m\equiv 0\ (\mathrm{mod}\ 4)$.

In Sect. 2, an equivalent description of 2-D $(n\times m,k,\lambda _a,1)$-OOCs is given by using set-theoretic notation. Section 3 is devoted to presenting an upper bound on the size of an optimal 2-D $(n\times m,3,2,1)$-OOC with $m\equiv 0\ (\mathrm{mod}\ 4)$. We will see that the upper bound relies heavily on the size of an optimal equi-difference 1-D (m, 3, 2, 1)-OOC (see Lemma 2). So we focus our attention on constructions for such kind of 1-D OOCs in Sect. 4. Interestingly, equi-difference 1-D (m, 3, 2, 1)-OOCs are closely related to equi-difference CAC(m, 3)s (see Sect. 4.2). The latter have been investigated independently in [19, 28, 29, 32, 41]. This paper helps to find another motivation to study equi-difference CAC(m, 3)s.

In Sect. 5, direct and recursive constructions for optimal 2-D $(n\times m,3,2,1)$-OOCs are given. We shall point out why it seems to be difficult to find effective recursive constructions for optimal 2-D $(n\times m,3,2,1)$-OOCs (see Remark 3).

Throughout this paper, assume that $I_n=\{0,1,\ldots ,n-1\}$ and denote by $Z_m$ the additive group of integers modulo m. For $a\in Z_m\setminus \{0\}$, the multiplicative order of a, denoted by ord$_m(a)$, is the smallest positive integer l such that $a^l\equiv 1\ (\mathrm{mod}\ m)$. As the main result of this paper, we are to prove the following theorem.

Theorem 2

For the specified n and m, the size of an optimal 2-D $(n\times m,3,2,1)$-OOC is

$$\begin{aligned} \varPhi (n\times m,3,2,1)=\left\{ \begin{array}{ll} \lfloor 7m/32\rfloor , &{} n=1, m\equiv 0\ (\mathrm{mod}\ 8) \mathrm{\ and\ } m\ne 64;\\ \lfloor (7m+4)/32\rfloor , &{} n=1 \mathrm{\ and\ } m\equiv 4\ (\mathrm{mod}\ 8);\\ 13, &{} (n,m)=(1,64);\\ 3m/4, &{} n=2, m\equiv 0\ (\mathrm{mod}\ 4) \mathrm{\ and\ } m>4;\\ 2, &{} (n,m)=(2,4);\\ n(8nm+3m-8)/48, &{} n\equiv 0\ (\mathrm{mod}\ 3), n\ne 6,9, \mathrm{\ and\ } \\ &{} m\equiv 8\ (\mathrm{mod}\ 16);\\ n(32nm+11m-32)/192, &{} n\equiv 0\ (\mathrm{mod}\ 3), n\ne 6,9, \mathrm{\ and\ } \\ &{} m\equiv 32\ (\mathrm{mod}\ 64);\\ 6, &{} (n,m)=(3,4);\\ n(8nm+3m+4)/48, &{} n\equiv 0\ (\mathrm{mod}\ 3), n\ne 6,9, m>4, \\ &{} m\equiv 4,20\ (\mathrm{mod}\ 48), \mathrm{\ and\ } m/4\in S,\\ \end{array} \right. \end{aligned}$$

where S is the set of positive integers such that for any $s\in S$, it holds that $s\equiv 1,5\ (\mathrm{mod}\ 12)$, and every prime divisor p of s satisfies $p\equiv 5\ (\mathrm{mod}\ 8)$, or $p\equiv 1\ (\mathrm{mod}\ 8)$ and $4|ord_p(2)$.

2 Preliminaries

A convenient way of viewing optical orthogonal codes is from a set-theoretic perspective.

Let ${\mathscr {C}}$ be a 2-D $(n\times m,k,\lambda _a,\lambda _c)$-OOC. For each $n\times m$ (0, 1)-matrix $M\in {\mathscr {C}}$, whose rows are indexed by $I_n$ and columns are indexed by $Z_m$. Construct a k-subset $B_M$ of $I_n\times Z_m$ such that $(i,j)\in B_M$ if and only if M’s (i, j) cell equals 1. Then $\{B_M: M\in {{\mathscr {C}}}\}$ is a set-theoretic representation of the 2-D $(n\times m,k,\lambda _a,\lambda _c)$-OOC. Conversely, let ${\mathscr {B}}$ be a set of k-subsets of $I_n\times Z_m$. ${{\mathscr {B}}}$ constitutes a 2-D $(n\times m,k,\lambda _a,\lambda _c)$-OOC if the following two conditions are satisfied:

($1'$):

the autocorrelation property: $|B\cap (B+s)|\le \lambda _a$ for any $B\in {{\mathscr {B}}}$ and any integer s, $s\not \equiv 0\ (\mathrm{mod}\ m)$;

($2'$):

the cross-correlation property: $|A\cap (B+s)|\le \lambda _c$ for any $A,B\in {{\mathscr {B}}}$ with $A\ne B$ and any integer s,

where $B+s=\{(i,x+s)\ \pmod {(-,m)}:(i,x)\in B\}$.

It is not convenient to check the autocorrelation and cross-correlation property of a set ${\mathscr {B}}$ of k-subsets of $I_n\times Z_m$ via Conditions $(1')$ and $(2')$. However, when $\lambda _c=1$, one can use the pure and mixed difference method to describe a 2-D $(n\times m,k,\lambda _a,1)$-OOC.

For $(i,x),(i,y)\in I_n\times Z_m$ with $x\ne y$, the difference $x-y$ (mod m) is called a pure (i, i)-difference. For $(i,x),(j,y)\in I_n\times Z_m$ with $i\ne j$, the difference $x-y$ (mod m) is called a mixed (i, j)-difference. Let B be a k-subset of $I_n\times Z_m$. Given $i,j\in I_n$, define a multi-set

$$\begin{aligned} \varDelta _{ij}(B)=\{x-y\ (mod\ m): (i,x),(j,y)\in B, (i,x)\ne (j,y)\}. \end{aligned}$$

When $i=j$, $\varDelta _{ii}(B)$ is the multi-set of all pure (i, i)-differences of B. When $i\ne j$, $\varDelta _{ij}(B)$ is the multi-set of all mixed (i, j)-differences of B. Note that $\varDelta _{ij}(B)$ is empty if i or j does not occur as the first component of the elements of B.

Let ${\mathscr {B}}$ be a set of k-subsets of $I_n\times Z_m$ and $B\in {{\mathscr {B}}}$. Let $\lambda (B)$ denote the maximum multiplicity of elements in the multi-set $\bigcup _{i\in I_n}\varDelta _{ii}(B)$. Then ${{\mathscr {B}}}$ constitutes a 2-D $(n\times m,k,\lambda _a,1)$-OOC if the following two conditions are satisfied:

$(1'')$ :

the autocorrelation property: $\lambda (B)\le \lambda _a$ for any $B\in {{\mathscr {B}}}$;

$(2'')$ :

the cross-correlation property: $\varDelta _{ij}(A)\cap \varDelta _{ij}(B)=\emptyset$ for any $A,B\in {{\mathscr {B}}}$ with $A\ne B$ and any $i,j\in I_n$ (i may be equal to j).

The interested reader is referred to [24] for details on the equivalence of $(1')$ and $(1'')$.

In the remainder of this paper, we always use the set-theoretic language to describe 2-D OOCs.

3 Upper bound on the size of 2-D $(n\times m,3,2,1)$-OOCs

In a 2-D $(n\times m,3,2,1)$-OOC, each codeword is of the form $\{(i_1,x),(i_2,y),(i_3,z)\}$, where $i_1,i_2,i_3\in I_n$ and $x,y,z\in Z_m$. All codewords can be divided into the following three types:

• Type 1: $i_1=i_2=i_3$;

• Type 2: $i_1=i_2\ne i_3$;

• Type 3: $i_1$, $i_2$, $i_3$ are pairwise distinct.

Let $\alpha$, $\beta$, $\gamma$ denote the numbers of codewords of Type 1, 2, 3 in a 2-D $(n\times m,3,2,1)$-OOC, respectively.

For Type 1, the codewords can be classified further according to the second coordinates. Take any codeword $\{(i_1,x),(i_1,y),(i_1,z)\}$ of Type 1 and consider its derived set $X=\{x,y,z\}$ of the second coordinates. Denote by $\varDelta X$ the set of underlying elements in the multi-set $\{b-a\ (\mathrm{mod}\ m):\ a,b\in X,a\ne b\}$. Define the orbit of X under $Z_m$ by $\mathrm{Orb}(X)=\{\{j+i\pmod {m}:j\in X\}:i\in Z_m\}$. By Lemma 2.2 in [33], we have

$$\begin{aligned} |\varDelta X|=\left\{ \begin{array}{ll} 2, &{} X\in \mathrm{Orb}(\{0,m/3,2m/3\}),\\ 3, &{} X\in \mathrm{Orb}(\{0,m/4,m/2\}),\\ 4, &{} X\in \mathrm{Orb}(\{0,a,2a\}) \mathrm{\ except\ for\ the\ cases\ of\ } |\varDelta X|=2,3,\\ 5, &{} X\in \mathrm{Orb}(\{0,a,m/2\}) \mathrm{\ except\ for\ the\ case\ of\ } |\varDelta X|=3,\\ 6, &{} X\in \mathrm{Orb}(\{0,a,b\}) \mathrm{\ except\ for\ the\ cases\ of\ } |\varDelta X|=2,3,4,5.\\ \end{array} \right. \end{aligned}$$

If $|\varDelta X|=2$, then $X\in \mathrm{Orb}(\{0,m/3,2m/3\})$, which implies that m / 3 occurs three times as a pure $(i_1,i_1)$-difference. It contradicts with the autocorrelation parameter $\lambda _a=2$. Thus $|\varDelta X|=3,4,5$ or 6. Let $\alpha _3$, $\alpha _4$, $\alpha _5$, $\alpha _6$ denote the numbers of codewords of Type 1 in a 2-D $(n\times m,3,2,1)$-OOC such that each derived set X of these codewords satisfies $|\varDelta X|=3,4,5,6$, respectively. Then $\alpha _3+\alpha _4+\alpha _5+\alpha _6=\alpha$.

For Type 2, take any codeword $\{(i_1,x),(i_1,y),(i_2,z)\}$ with $i_1\ne i_2$ and consider its partial derived set $Y=\{x,y\}$ of the second coordinates. Let $\beta _1$ denote the number of codewords of Type 2 in a 2-D $(n\times m,3,2,1)$-OOC such that each partial derived set Y of these codewords satisfies $y-x\equiv m/2\ (\mathrm{mod}\ m)$. Denote by $\beta _2$ the number of the remaining codewords of Type 2 in the 2-D OOC. Then $\beta _1+\beta _2=\beta$.

3.1 General upper bound

We need a new concept. A 1-D (m, 3, 2, 1)-OOC is said to be equi-difference if each of its codewords is of the form $X=\{0,a,2a\}$ for some $a\ne 0$, i.e., $|\varDelta X|=3$ or 4. Let $\varPsi ^e(m,3,2,1)$ denote the largest size of codes among all equi-difference 1-D (m, 3, 2, 1)-OOCs for given m. An equi-difference 1-D (m, 3, 2, 1)-OOC is said to be optimal if it contains $\varPsi ^e(m,3,2,1)$ codewords.

Lemma 1

(1):

$\alpha _3+\alpha _4\le n\varPsi ^e(m,3,2,1)$.

(2):

$\alpha _3+\alpha _5+\beta _1\le n$.

Proof

(1):

Examine codewords of the form $\{(i,0),(i,a),(i,2a)\}$ with $X=\{0,a,2a\}$ and $|\varDelta X|=3,4$. The number of such kind of codewords is not more than $\varPsi ^e(m,3,2,1)$ for each $i\in I_n$. So $\alpha _3+\alpha _4\le n\varPsi ^e(m,3,2,1)$.

(2):

For each $i\in I_n$, there is at most one codeword that admits m / 2 as a pure (i, i)-difference. So $\alpha _3+\alpha _5+\beta _1\le n$.

Lemma 2

$\varPhi (n\times m,3,2,1)\le \left\{ \begin{array}{ll} \lfloor n(nm+2\varPsi ^e(m,3,2,1))/6\rfloor , &{} \mathrm{if\ } m\equiv 0\ (\mathrm{mod}\ 2),\\ \lfloor n(nm+2\varPsi ^e(m,3,2,1)-1)/6\rfloor , &{} \mathrm{if\ } m\equiv 1\ (\mathrm{mod}\ 2).\\ \end{array} \right.$

Proof

In a 2-D $(n\times m,3,2,1)$-OOC, given $i\in I_n$, there are at most $m-1$ different pure (i, i)-differences; and given $i,j\in I_n$ with $i\ne j$, there are at most m different mixed (i, j)-differences. Thus the total numbers of different pure differences and mixed differences in a 2-D $(n\times m,3,2,1)$-OOC are at most $n(m-1)$ and $n(n-1)m$, respectively. Pure differences are from Type 1 and a part of Type 2, while mixed differences are from Type 3 and the other part of Type 2. So we have

$$\begin{aligned} 3\alpha _3+4\alpha _4+5\alpha _5+6\alpha _6+\beta _1+2\beta _2&\le n(m-1), \end{aligned}$$

(1)

$$\begin{aligned} 4\beta +6\gamma&\le n(n-1)m. \end{aligned}$$

(2)

By Lemma 1(2),

$$\begin{aligned} \alpha _3+\alpha _5+\beta _1&\le n. \end{aligned}$$

(3)

Note that $\alpha _3+\alpha _4+\alpha _5+\alpha _6=\alpha$ and $\beta _1+\beta _2=\beta$. By (1)+(2)+(3), we have $6(\alpha +\beta +\gamma )-2(\alpha _3+\alpha _4)\le n^2m$. By Lemma 1(1), $\alpha _3+\alpha _4\le n\varPsi ^e(m,3,2,1)$. It follows that $\alpha +\beta +\gamma \le (n^2m+2n\varPsi ^e(m,3,2,1))/6.$ Therefore, $\varPhi (n\times m,3,2,1)\le \lfloor n(nm+2\varPsi ^e(m,3,2,1))/6\rfloor$.

Furthermore, when m is odd, $\alpha _3=\alpha _5=\beta _1=0$. So $\alpha _4+\alpha _6=\alpha$ and $\beta _2=\beta$. Then by (1)+(2), we have $6(\alpha +\beta +\gamma )-2\alpha _4\le n^2m-n$. By Lemma 1(1), $\alpha _4\le n\varPsi ^e(m,3,2,1)$. Thus $\varPhi (n\times m,3,2,1)\le \lfloor n(nm+2\varPsi ^e(m,3,2,1)-1)/6\rfloor$ for any odd integer m. $\square$

Remark 1

Examining the proof of Lemma 2, we have that if

$$\begin{aligned} \varPhi (n\times m,3,2,1)=\left\{ \begin{array}{ll} n(nm+2\varPsi ^e(m,3,2,1))/6, &{} \mathrm{if\ } m\equiv 0\ (\mathrm{mod}\ 2),\\ n(nm+2\varPsi ^e(m,3,2,1)-1)/6, &{} \mathrm{if\ } m\equiv 1\ (\mathrm{mod}\ 2), \end{array} \right. \end{aligned}$$

then $\alpha _3+\alpha _4= n\varPsi ^e(m,3,2,1)$ from Lemma 1(1), which means that in such cases, any optimal 2-D $(n\times m,3,2,1)$-OOC must contain n optimal equi-difference 1-D (m, 3, 2, 1)-OOCs as subcodes.

Lemma 3

$\varPhi (3\times 4,3,2,1)\le 6$.

Proof

An optimal equi-difference 1-D (4, 3, 2, 1)-OOC defined on $Z_4$ contains only one codeword $\{0,1,2\}$, so $\varPsi ^e(4,3,2,1)=1$. Then by Lemma 2, $\varPhi (3\times 4,3,2,1)\le 7$. Assume that $\varPhi (3\times 4,3,2,1)=7$. By Remark 1, $\alpha _3+\alpha _4=3$. Since $\alpha _4=\alpha _5=\alpha _6=0$ for any 2-D $(3\times 4,3,2,1)$-OOC, we have $\alpha _3=3$. By Formula (1), $3\alpha _3+4\alpha _4+5\alpha _5+6\alpha _6+\beta _1+2\beta _2 \le 9$, so $\beta =0$, which yields $\gamma =4$. Write the 4 codewords of Type 3 as $\{(0,0),(1,a_i),(2,b_i)\}$, $i=1,2,3,4$. Clearly, $\bigcup _{i=1}^4 \{a_i\}=\bigcup _{i=1}^4 \{b_i\}=\bigcup _{i=1}^4 \{b_i-a_i\ (\mathrm{mod}\ 4)\}=Z_4$. Thus $\sum _{i=1}^4 (b_i-a_i)=\sum _{i=1}^4 b_i-\sum _{i=1}^4 a_i=0$ and $\sum _{i=1}^4 (b_i-a_i)\equiv 0+1+2+3\ (\mathrm{mod}\ 4)$, a contradiction. $\square$

3.2 Improved upper bound for $n=2$

Lemma 4

$\varPhi (2\times m,3,2,1)\le \left\{ \begin{array}{ll} \lfloor 3m/4 \rfloor , &{} \mathrm{if\ } m\equiv 0\ (\mathrm{mod}\ 2),\\ \lfloor (3m-2)/4\rfloor , &{} \mathrm{if\ } m\equiv 1\ (\mathrm{mod}\ 2).\\ \end{array} \right.$

Proof

Formulas (1)–(3) in Lemma 2 still hold when $n=2$. Note that $\gamma =0$ when $n=2$. We rewrite these formulas as follows

$$\begin{aligned} 3\alpha _3+4\alpha _4+5\alpha _5+6\alpha _6+\beta _1+2\beta _2&\le 2(m-1), \end{aligned}$$

(4)

$$\begin{aligned} 2\beta&\le m, \end{aligned}$$

(5)

$$\begin{aligned} \alpha _3+\alpha _5+\beta _1&\le 2. \end{aligned}$$

(6)

By (4)+(5)+(6), we have $4(\alpha +\beta )+2(\alpha _5+\alpha _6)\le 3m$. Due to $\alpha _5,\alpha _6\ge 0$, we have $\alpha +\beta \le 3m/4$. Hence, $\varPhi (2\times m,3,2,1)\le \lfloor 3m/4\rfloor$.

Furthermore, when m is odd, $\alpha _3=\alpha _5=\beta _1=0$. Then by (4)+(5), we have $4(\alpha +\beta )+2\alpha _6\le 3m-2$. Thus $\varPhi (n\times m,3,2,1)\le \lfloor (3m-2)/4\rfloor$ for any odd integer m. $\square$

Lemma 5

$\varPhi (2\times 4,3,2,1)\le 2$.

Proof

By Lemma 4, $\varPhi (2\times 4,3,2,1)\le 3$. Assume that $\varPhi (2\times 4,3,2,1)=3$. Since $\alpha _4=\alpha _5=\alpha _6=0$ for any 2-D $(2\times 4,3,2,1)$-OOC, we rewrite Formulas (4)–(6) as follows

$$\begin{aligned} 3\alpha _3+\beta _1+2\beta _2&\le 6, \end{aligned}$$

(7)

$$\begin{aligned} \beta&\le 2, \end{aligned}$$

(8)

$$\begin{aligned} \alpha _3+\beta _1&\le 2. \end{aligned}$$

(9)

$\varPhi (2\times 4,3,2,1)=3$ yields $\alpha +\beta =3$, so $\alpha =\alpha _3\ge 1$ by (8). It follows from (7)+(8)+(9) that $4\alpha + 3\beta = \alpha + 3(\alpha + \beta ) \le 10$, which leads to $\alpha \le 1$. This and the preceding argument on $\alpha$ implies $\alpha =1$. So $\beta =2$. Then $\beta _1\le 1$ by (9) and $\beta _2\ge 1$ by $\beta =2$. It follows that $\beta _1=\beta _2=1$ by (7). W.l.o.g., let the codeword such that $\alpha _3=1$ be $\{(0,0),(0,1),(0,2)\}$, and the codewords such that $\beta _1=1$ and $\beta _2=1$ are $\{(1,0),(1,2),(0,x)\}$ and $\{(1,0),(1,1),(0,y)\}$, respectively, for some $x,y\in Z_4$. Examining the mixed (0, 1)-differences, we obtain $\{x,x-2,y,y-1\}\equiv \{0,1,2,3\} \pmod {4}$. It is readily checked that such x and y do not exist, a contradiction. $\square$

Remark 2

A more intuitive proof of Lemma can be given here. One can show that there are no more than 2 codewords in a 2-D $(2\times 4,3,2,1)$-OOC directly without using the machinery that leads to (7), (8) and (9). Suppose we have three codewords in a $2\times 4$ array. Denote by $\alpha$ the number of codewords which uses only one single channel (i.e., codewords of Type I). Consider all possibilities of $\alpha$. If $\alpha =3$, then by pigeon-hole principle, there are at least two codewords whose optical pulses are in the same channel, and so $\lambda _c=3$. If $\alpha =2$, then the two codewords using only one single channel must occupy two different frequency channels. It follows that the third codeword must have two 1’s in one of the channels, and this gives $\lambda _c=2$. If $\alpha =1$ and $\{(0,0), (0,1), (0,2)\}$ is one of the codewords, then each of the other two codewords must have one 1’s in channel 0 and two 1’s in channel 1. There always exists a cyclic shift such that the two other codewords have Hamming cross-correlation at least 2. If $\alpha =0$, then by pigeon-hole principle again, we have two codewords with one 1’s in channel 0 and two 1’s in channel 1, or two codewords with one 1’s in channel 1 and two 1’s in channel 0. There always exists a cyclic shift such that the two codewords have Hamming cross-correlation at least 2. This completes the proof of Lemma .

3.3 Improved upper bound for $n=1$ and $m\equiv 0 \pmod {4}$

To present an improved upper bound for $\varPhi (1\times m,3,2,1)$, we here review the linear programming approach formulated by Jimbo et al. [25].

For any codeword X in a 1-D (m, 3, 2, 1)-OOC with $m\equiv 0 \pmod {4}$, since the elements of $\varDelta (X)$ are symmetric with respect to m / 2, it suffices to consider the halved difference set

$$\begin{aligned} \varDelta _2(X)=\{i:\ i\in \varDelta (X),1\le i\le m/2\} \end{aligned}$$

instead of $\varDelta (X)$.

Now partition the positive integers not exceeding m / 2 into the following three subsets:

$$\begin{aligned}&O=\{i:\ i\equiv 1 \pmod {2}, 1\le i\le m/2\}, \\&E=\{i:\ i\equiv 2 \pmod {4}, 1\le i\le m/2\},\\&D=\{i:\ i\equiv 0 \pmod {4}, 1\le i\le m/2\}. \end{aligned}$$

The integers in O are odd, those in E are said to be singly even and those in D are said to be doubly even. It follows that any codeword of a 1-D (m, 3, 2, 1)-OOC can be categorized into the following two lemmas according to the halved difference set produced from it.

Lemma 6

[25] Let $m\equiv 0 \pmod {4}$. Any codeword X of the form $\{0,i,2i\}$ satisfying $\varDelta _2(X)=\{i,j\}$, where $j=2i$ if $1\le i\le m/4$, and $j=m-2i$ if $m/4<i<m/2$ and $i\ne m/3$, belongs to one of the following three types:

(i):

$i\in O$ and $j\in E$,

(ii):

$i\in E$ and $j\in D$,

(iii):

$i,j\in D$.

Lemma 7

[25] Let $m\equiv 0 \pmod {4}$. Any codeword X satisfying $\varDelta _2(X)=\{i,j,k\}$ belongs to one of the following four types:

(iv):

two of i, j and k are in O and one is in E,

(v):

two of i, j and k are in O and one is in D,

(vi):

two of i, j and k are in E and one is in D,

(vii):

$i,j,k\in D$.

Take a 1-D (m, 3, 2, 1)-OOC ${\mathscr {C}}$. Let $C_o$, $C_e$ and $C_d$ denote the sets of codewords in ${\mathscr {C}}$ of Types (i), (ii) and (iii), respectively, and $N_{oe}$, $N_{od}$, $N_{ed}$ and $N_d$ denote the sets of codewords in ${\mathscr {C}}$ of Types (iv), (v), (vi) and (vii), respectively. Note that any codeword $X\in \mathscr {C}$ with $|\varDelta X|=3$ or 4 satisfies Lemma 6, while any codeword X with $|\varDelta X|=5$ or 6 satisfies Lemma 7. Then

$$\begin{aligned} |\mathscr {C}|=|C_o|+|C_e|+|C_d|+|N_{oe}|+|N_{od}|+|N_{ed}|+|N_d|. \end{aligned}$$

Lemma 8

$$\begin{aligned} \varPhi (1\times m,3,2,1)\le \left\{ \begin{array}{ll} \lfloor 7m/32\rfloor , &{} \mathrm{if\ } m\equiv \ 0\ (\mathrm{mod}\ 8),\\ \lfloor (7m+4)/32\rfloor , &{} \mathrm{if\ } m\equiv \ 4\ (\mathrm{mod}\ 8).\\ \end{array} \right. \end{aligned}$$

Proof

A 1-D (m, 3, 2, 1)-OOC with $m\equiv 0 \pmod {4}$ contributes at most m / 4 different odd differences that are not more than m / 2, $\lceil m/8\rceil$ different singly even differences that are not more than m / 2, and $\lfloor m/8\rfloor$ different doubly even differences that are not more than m / 2. It follows that

$$\begin{aligned}&|C_o|+2|N_{oe}|+2|N_{od}|\le m/4, \end{aligned}$$

(10)

$$\begin{aligned}&|C_o|+|C_e|+|N_{oe}|+2|N_{ed}|\le \lceil m/8\rceil , \end{aligned}$$

(11)

$$\begin{aligned}&|C_e|+2|C_d|+|N_{od}|+|N_{ed}|+3|N_d|\le \lfloor m/8\rfloor . \end{aligned}$$

(12)

By (10)+3(11)+2(12), we have

$$\begin{aligned} 4|\mathscr {C}|+|C_e|+|N_{oe}|+4|N_{ed}|+2|N_d|\le \left\{ \begin{array}{ll} 7m/8, &{} \mathrm{if\ } m\equiv \ 0\ (\mathrm{mod}\ 8), \\ (7m+4)/8, &{} \mathrm{if\ } m\equiv \ 4\ (\mathrm{mod}\ 8), \\ \end{array} \right. \end{aligned}$$

where $|\mathscr {C}|=|C_o|+|C_e|+|C_d|+|N_{oe}|+|N_{od}|+|N_{ed}|+|N_d|$ is the total number of codewords. Hence,

$$\begin{aligned} |\mathscr {C}|\le \left\{ \begin{array}{ll} \lfloor 7m/32\rfloor , &{} \mathrm{if\ } m\equiv \ 0\ (\mathrm{mod}\ 8),\\ \lfloor (7m+4)/32\rfloor , &{} \mathrm{if\ } m\equiv \ 4\ (\mathrm{mod}\ 8).\\ \end{array} \right. \end{aligned}$$

This completes the proof. $\square$

4 Equi-difference 1-D (m, 3, 2, 1)-OOCs

By Lemma 2, it is important to determine the exact value of $\varPsi ^e(m,3,2,1)$. Clearly, $\varPsi ^e(m,3$, $2,1)\le \varPhi (1\times m,3,2,1)$. A better upper bound can be shown in the following lemma.

Lemma 9

$$\begin{aligned} \varPsi ^e(m,3,2,1)\le \left\{ \begin{array}{ll} \lfloor (m-1)/4\rfloor , &{} \mathrm{if\ } m\not \equiv 0\ (\mathrm{mod}\ 4);\\ \lceil m/8\rceil +\varPsi ^e(m/4,3,2,1), &{} \mathrm{if\ } m\equiv 0\ (\mathrm{mod}\ 4).\\ \end{array} \right. \end{aligned}$$

Proof

Let ${\mathscr {C}}$ be an equi-difference 1-D (m, 3, 2, 1)-OOC. When $m\not \equiv 0\pmod {4}$, for any codeword $X\in {{\mathscr {C}}}$, $|\varDelta X|=4$, so $\varPsi ^e(m,3,2,1)\le \lfloor (m-1)/4\rfloor$.

When $m\equiv 0\pmod {4}$, recall that $C_o$, $C_e$ and $C_d$ denote the sets of codewords in ${\mathscr {C}}$ of Types (i), (ii) and (iii) (see Lemma 6), respectively. Then $|\mathcal{C}|=|C_o|+|C_e|+|C_d|$. A 1-D (m, 3, 2, 1)-OOC with $m\equiv 0 \pmod {4}$ contributes at most $\lceil m/8\rceil$ different singly even differences that are not exceeding m / 2, which gives $|C_o|+|C_e|\le \lceil m/8\rceil$. Observing that $|C_d|\le \varPsi ^e(m/4,3,2,1)$, we obtain $|{{\mathscr {C}}}|\le \lceil m/8\rceil +\varPsi ^e(m/4,3,2,1)$. $\square$

For an equi-difference 1-D (m, 3, 2, 1)-OOC, ${\mathscr {B}}$, on $Z_m$, define $\varDelta ({{\mathscr {B}}})=\bigcup _{B\in {{\mathscr {B}}}}\varDelta (B)$ to be a set of differences. The difference leave of ${\mathscr {B}}$ is a set that consists of all nonzero elements of $Z_m$ not covered by $\varDelta ({{\mathscr {B}}})$. Let $m\equiv 0\ (\mathrm{mod}\ g)$ and H be the subgroup of order g in $Z_m$, i.e., $H=\{0,m/g,\ldots ,(g-1)m/g\}$. If $\varDelta ({{\mathscr {B}}})\subseteq Z_m\setminus H$, then ${\mathscr {B}}$ is said to be a g-regular equi-difference 1-D (m, 3, 2, 1)-OOC.

Lemma 10

There is an optimal equi-difference 1-D (m, 3, 2, 1)-OOC with $\varPsi ^e(m,3,2,1)$$=(m-2)/4$ codewords for any $m\equiv 2\ (\mathrm{mod}\ 4)$, whose difference leave is $\{m/2\}$.

Proof

It is readily checked that $\{\{0,i,2i\}$, $i=1,3,\ldots ,m/2-2\}$ forms a 2-regular equi-difference 1-D (m, 3, 2, 1)-OOC with $(m-2)/4$ codewords, whose difference leave is $\{m/2\}$. By Lemma 9, it is optimal. $\square$

4.1 A recursive construction

Let A be a set of integers and w be an integer. Write $w\cdot A=\{wa:a\in A\}$. The following construction is straightforward by the definition of g-regular equi-difference 1-D OOCs.

Construction 3

Suppose that there exist

(1):

a g-regular equi-difference 1-D (m, 3, 2, 1)-OOC with $b_1$ codewords, whose difference leave is $L_1$ (defined on $Z_m)$;

(2):

an equi-difference 1-D (g, 3, 2, 1)-OOC with $b_2$ codewords, whose difference leave is $L_2$ (defined on $Z_g)$.

Then there exists an equi-difference 1-D (m, 3, 2, 1)-OOC with $b_1+b_2$ codewords, whose difference leave is $L_1\cup ((m/g)\cdot L_2)$ (defined on $Z_m)$.

Assume that [a, b] denotes the set of integers n such that $a\le n\le b$, and $[a,b]_o$ denotes the set of odd integers in [a, b].

Lemma 11

There exists a g-regular equi-difference 1-D (4g, 3, 2, 1)-OOC with $\lceil g/2\rceil$ codewords for any positive integer g, whose difference leave is $[1,g-1]_o\cup [3g+1,4g-1]_o\cup (4\cdot [1,g-1])$.

Proof

Let

$$\begin{aligned} {{\mathscr {C}}}=\left\{ \begin{array}{ll} \{\{0,i,2i\}:i\in [g+1,2g-1]_o\}, &{} \mathrm{if\ } g\equiv 0\ (\mathrm{mod}\ 2);\\ \{\{0,i,2i\}:i\in [g,2g-1]_o\}, &{} \mathrm{if\ } g\equiv 1\ (\mathrm{mod}\ 2).\\ \end{array} \right. \end{aligned}$$

Note that $\{0,4g/3,8g/3\}\not \in {{\mathscr {C}}}$, i.e., $i\ne 4g/3$ since i is odd. Then ${{\mathscr {C}}}$ forms a g-regular equi-difference 1-D (4g, 3, 2, 1)-OOC with $\lceil g/2\rceil$ codewords, whose difference leave is $[1,g-1]_o\cup [3g+1,4g-1]_o\cup (4\cdot [1,g-1])$. $\square$

Lemma 12

Let $m\equiv 0\ (\mathrm{mod}\ 4)$. If there exists an optimal equi-difference 1-D (m / 4, 3, 2, 1)-OOC with $\varPsi ^e(m/4,3,2,1)$ codewords, whose difference leave is L, then there exists an optimal equi-difference 1-D (m, 3, 2, 1)-OOC with $\lceil m/8\rceil +\varPsi ^e(m/4,3,2,1)$ codewords, whose difference leave is $(4\cdot L)\cup [1,m/4-1]_o\cup [3m/4+1,m-1]_o$.

Proof

By Lemma 11, there exists an (m / 4)-regular equi-difference 1-D (m, 3, 2, 1)-OOC with $\lceil m/8\rceil$ codewords for any $m\equiv 0\ (\mathrm{mod}\ 4)$, whose difference leave is $[1,m/4-1]_o\cup [3m/4+1,m-1]_o\cup (4\cdot [1,m/4-1])$. Then apply Construction 3 with an optimal equi-difference 1-D (m / 4, 3, 2, 1)-OOC with $\varPsi ^e(m/4,3,2,1)$ codewords, whose difference leave is L, to obtain an equi-difference 1-D (m, 3, 2, 1)-OOC with $\lceil m/8\rceil +\varPsi ^e(m/4,3,2,1)$ codewords, whose difference leave is $(4\cdot L)\cup [1,m/4-1]_o\cup [3m/4+1,m-1]_o$. The optimality is ensured by Lemma 9. $\square$

Theorem 4

There exists an optimal equi-difference 1-D $(4^s r,3,2,1)$-OOC with

$$\begin{aligned} \varPsi ^e(4^s r,3,2,1)=(2^{2s+1}r+r-6)/12 \end{aligned}$$

codewords for any $s\ge 0$ and $r\equiv 2\ (\mathrm{mod}\ 4)$, whose difference leave is

$$\begin{aligned} \{2^{2s-1}r\}\cup \left( \bigcup _{i=1}^s (4^{s-i}\cdot ([1,4^{i-1}r-1]_o\cup [4^{i-1}3r+1,4^ir-1]_o)) \right) . \end{aligned}$$

Proof

We use induction on s. When $s=0$, the conclusion follows from Lemma 10. Assume that the conclusion holds for $s=k-1$ ($k\ge 1$), i.e., there exists an optimal equi-difference 1-D $(4^{k-1} r,3,2,1)$-OOC with $(2^{2(k-1)+1}r+r-6)/12$ codewords. Then apply Lemma 12 to obtain an optimal equi-difference 1-D $(4^{k} r,3,2,1)$-OOC with $\lceil 4^{k-1} r/2\rceil +(2^{2(k-1)+1}r+r-6)/12=(2^{2k+1}r+r-6)/12$ codewords. One can check the difference leave for any given s by induction. $\square$

The difference leave of each optimal equi-difference 1-D $(4^s r,3,2,1)$-OOC constructed in Theorem 4 contains $2^{2s-1}r$, which is a half of $4^s r$. In Sect. 5.2 we shall present direct constructions for optimal 2-D $(3\times m,3,2,1)$-OOCs which must contain three optimal equi-difference 1-D (m, 3, 2, 1)-OOCs as subcodes. However, we hope the three equi-difference 1-D OOCs can use up the three half differences in their codewords. For this purpose, we present the following theorem to show optimal equi-difference 1-D $(4^s r,3,2,1)$-OOCs whose difference leave do not contain $2^{2s-1}r$.

Theorem 5

There exists an optimal equi-difference 1-D $(4^s r,3,2,1)$-OOC with

$$\begin{aligned} \varPsi ^e(4^s r,3,2,1)=(2^{2s+1}r+r-6)/12 \end{aligned}$$

codewords for any $s\ge 1$ and $r\equiv 2\ (\mathrm{mod}\ 4)$, whose difference leave is

$$\begin{aligned} \{2^{2s-3}3r,2^{2s-3}5r\}\cup \left( \bigcup _{i=1}^s (4^{s-i}\cdot ([1,4^{i-1}r-1]_o\cup [4^{i-1}3r+1,4^ir-1]_o)) \right) . \end{aligned}$$

Proof

When $s=1$, by the proof of Theorem 4, we can list all $(3r-2)/4$ codewords of an optimal equi-difference 1-D (4r, 3, 2, 1)-OOC as follows:

$$\begin{aligned} {{\mathscr {A}}}=\{\{0,i,2i\}:i\in [r+1,2r-1]_o\}\cup (4\cdot \{\{0,i,2i\}:i=1,3,\ldots ,r/2-2\}), \end{aligned}$$

whose difference leave is $\{2r\}\cup [1,r-1]_o\cup [3r+1,4r-1]_o$. Let

$$\begin{aligned} {{\mathscr {B}}}=({{\mathscr {A}}}\setminus \{\{0,3r/2,3r\}\})\cup \{\{0,r,2r\}\}. \end{aligned}$$

Then ${{\mathscr {B}}}$ is an optimal equi-difference 1-D (4r, 3, 2, 1)-OOC, whose difference leave is $\{3r/2$, $5r/2\}\cup [1,r-1]_o\cup [3r+1,4r-1]_o$. Start from ${\mathscr {B}}$ and use induction on s. Then we can complete the proof by similar argument to that in Theorem 4. $\square$

4.2 Constructions from conflict-avoiding codes

Recall that a 1-D (m, k, k, 1)-OOC is called a conflict-avoiding code, denoted by a CAC(m, k).

A CAC(m, 3) is said to be equi-difference if each of its codewords is of the form $X=\{0,a,2a\}$, i.e., $|\varDelta X|=2,3$ or 4. Let $M^e(m,3)$ denote the largest size of codes among all equi-difference CAC(m, 3)s for given m. An equi-difference CAC(m, 3) is said to be optimal if it contains $M^e(m,3)$ codewords.

Clearly, when $m\not \equiv 0\ (\mathrm{mod}\ 3)$, an optimal equi-difference CAC(m, 3) is also an optimal equi-difference 1-D (m, 3, 2, 1)-OOC. Thus many known constructions for optimal equi-difference CAC(m, 3) in [19, 28, 29, 32, 41] can be applied to constructions for optimal equi-difference 1-D (m, 3, 2, 1)-OOC.

An equi-difference CAC(m, 3) $\mathscr {C}$ is said to be tight if $\bigcup _{X\in \mathscr {C}}\varDelta X=Z_m\setminus \{0\}$. A tight equi-difference CAC(m, 3) is optimal. Momihara [32] gave a necessary and sufficient condition for the existence of a tight equi-difference CAC(m, 3). In Fu et al. [19], the condition is restated in terms of multiplicative order of 2 modulo p for all prime factors p of m.

Lemma 13

[19, 32] There exists a tight equi-difference CAC(m, 3) if and only if $m=4$ or $m\ge 3$ and $m=3^f m_0$ for $f\in \{0,1\}$, where any prime factor p of $m_0$ satisfies $p\equiv 1\ (\mathrm{mod}\ 4)$ and $4|ord_{p}(2)$ whenever $p\equiv 1\ (\mathrm{mod}\ 8)$. Furthermore, a tight equi-difference CAC(m, 3) contains 1 codeword for $m=4$, $(m-1)/4$ codewords for admissible $m\equiv 1,5\ (\mathrm{mod}\ 12)$, and $(m+1)/4$ codewords for admissible $m\equiv 3\ (\mathrm{mod}\ 12)$.

We remark that the conditions on $m_0$ in Lemma 13 are fairly complex and one has to examine each prime factor of $m_0$. For this reason, only a few explicit series of odd m are known (see [28, 41]).

Theorem 6

Let $r\equiv 1,5\ (\mathrm{mod}\ 12)$ satisfying that for any prime factor p of r, $p\equiv 1\ (\mathrm{mod}\ 4)$ and $4|ord_{p}(2)$ whenever $p\equiv 1\ (\mathrm{mod}\ 8)$. Then

(1):

there is an optimal equi-difference 1-D (r, 3, 2, 1)-OOC with

$$\begin{aligned} \varPsi ^e(r,3,2,1)=(r-1)/4 \end{aligned}$$

codewords, whose difference leave is empty;

(2):

there is an optimal equi-difference 1-D $(4^s r,3,2,1)$-OOC with

$$\begin{aligned} \varPsi ^e(4^s r,3,2,1)=(2^{2s-1}-2)r/3+(3r+1)/4 \end{aligned}$$

codewords for any $s\ge 1$, whose difference leave is

$$\begin{aligned} \bigcup _{i=1}^s (4^{s-i}\cdot ([1,4^{i-1}r-1]_o\cup [4^{i-1}3r+1,4^ir-1]_o)). \end{aligned}$$

Note that it is allowed that $r=1$ in (2).

Proof

Since $r\not \equiv 0\ (\mathrm{mod}\ 3)$, (1) is straightforward by Lemmas 9 and 13. To prove (2), we use induction on s. When $s=1$, take an optimal equi-difference 1-D (r, 3, 2, 1)-OOC with $(r-1)/4$ codewords from (1), whose difference leave is empty. Then apply Lemma 12 to obtain an optimal equi-difference 1-D (4r, 3, 2, 1)-OOC with $(3r+1)/4$ codewords, whose difference leave is $[1,r-1]_o\cup [3r+1,4r-1]_o$. Assume that the conclusion holds for $s=k-1$ ($k\ge 2$). Then apply Lemma 12 again to complete the proof. $\square$

Theorem 7

Let $r\equiv 3\ (\mathrm{mod}\ 12)$. If for any prime factor p of r / 3, $p\equiv 1\ (\mathrm{mod}\ 4)$ and $4|ord_{p}(2)$ whenever $p\equiv 1\ (\mathrm{mod}\ 8)$, then

(1):

there is an optimal equi-difference 1-D (r, 3, 2, 1)-OOC with

$$\begin{aligned} \varPsi ^e(r,3,2,1)=(r-3)/4 \end{aligned}$$

codewords, whose difference leave is $\{r/3,2r/3\}$;

(2):

there is an optimal equi-difference 1-D $(4^s r,3,2,1)$-OOC with

$$\begin{aligned} \varPsi ^e(4^s r,3,2,1)=(2^{2s-1}-2)r/3+(3r-1)/4 \end{aligned}$$

codewords for any $s\ge 1$, whose difference leave is

$$\begin{aligned} \{2^{2s}r/3,2^{2s+1}r/3\}\cup \left( \bigcup _{i=1}^s (4^{s-i}\cdot ([1,4^{i-1}r-1]_o\cup [4^{i-1}3r+1,4^ir-1]_o)) \right) . \end{aligned}$$

Note that it is allowed that $r=3$.

Proof

• (1) By Lemma 13, a tight equi-difference CAC(r, 3) with $(r+1)/4$ codewords exists for any $r\equiv 3\ (\mathrm{mod}\ 12)$ satisfying the assumption. Since r is odd, such a tight CAC must contain the codeword $\{0,r/3,2r/3\}$. It follows that all codewords of the CAC except for the codeword $\{0,r/3,2r/3\}$ constitute an equi-difference 1-D (r, 3, 2, 1)-OOC with $(r-3)/4$ codewords, which is optimal by Lemma 9.

• (2) We use induction on s. When $s=1$, take an optimal equi-difference 1-D (r, 3, 2, 1)-OOC with $(r-3)/4$ codewords from (1), whose difference leave is $\{r/3,2r/3\}$. Then apply Lemma 12 to obtain an optimal equi-difference 1-D (4r, 3, 2, 1)-OOC with $(3r-1)/4$ codewords, whose difference leave is $\{4r/3,8r/3\}\cup [1,r-1]_o\cup [3r+1,4r-1]_o$. Assume that the conclusion holds for $s=k-1$ ($k\ge 2$). Then apply Lemma 12 again to complete the proof. $\square$

Lemma 14

[29] Let $p\ge 5$ be any prime. There exists an optimal equi-difference CAC(p, 3) with

$$\begin{aligned} M^e(p,3)=\frac{p-1}{2^{ord_p(2)\ (\mathrm{mod}\ 2)}ord_p(2)}\times \lfloor \frac{1}{2} \times \frac{ord_p(2)}{2^{(ord_p(2)+1) \ (\mathrm{mod}\ 2)}} \rfloor \end{aligned}$$

codewords.

Theorem 8

Let $p\ge 5$ be any prime and $M^e(p,3)$ be as in Lemma 14. Then

(1):

there is an optimal equi-difference 1-D (p, 3, 2, 1)-OOC with

$$\begin{aligned} \varPsi ^e(p,3,2,1)=M^e(p,3) \end{aligned}$$

codewords;

(2):

there is an optimal equi-difference 1-D $(4^s p,3,2,1)$-OOC with

$$\begin{aligned} \varPsi ^e(4^s p,3,2,1)=(2^{2s-1}-2)p/3+(p+1)/2+M^e(p,3) \end{aligned}$$

codewords for any $s\ge 1$.

Proof

Since $p\not \equiv 0\ (\mathrm{mod}\ 3)$, (1) follows immediately from Lemma 14. To prove (2), one can use induction on s and apply Lemma 12. $\square$

5 Determination of $\varPhi (n\times m,3,2,1)$ with $m\equiv 0\pmod {4}$

5.1 The cases of $n=1$ and 2

Lemma 15

For any $m\equiv 0\ (\mathrm{mod}\ 4)$,

$$\begin{aligned} \varPhi (1\times m,3,2,1)=\left\{ \begin{array}{ll} \lfloor 7m/32\rfloor , &{} \mathrm{if\ } m\equiv 0\ (\mathrm{mod}\ 8),\\ \lfloor (7m+4)/32\rfloor , &{} \mathrm{if\ } m\equiv 4\ (\mathrm{mod}\ 8),\\ \end{array} \right. \end{aligned}$$

with the exception of $\varPhi (1\times 64,3,2,1)=13.$

Proof

For $m=48$, we give an explicit construction for a 1-D (48, 3, 2, 1)-OOC with 10 codewords as follows, which is defined on $Z_{48}$. Lemma 8 ensures its optimality.

$$\begin{aligned} \begin{array}{llllll} \{0,3,6\}, &{}\{0,7,14\},&{} \{0,11,22\},&{} \{0,15,30\}, &{}\{0,19,38\}, &{} \{0,23,46\},\\ \{0,1,17\},&{} \{0,5,9\}, &{}\{0,13,21\}, &{}\{0,12,24\}.&{}&{} \end{array} \end{aligned}$$

For $m\equiv 0\ (\mathrm{mod}\ 4)$ and $m\ne 48$, let $m=4u$ and $u\ne 12$. Write $T=\{0,m/3,2m/3\}$ when $m\equiv 0\ (\mathrm{mod}\ 3)$. Then an optimal 1-D (m, 3, 2, 1)-OOC with $\varPhi (1\times m,3,2,1)$ codewords is constructed in the following table. Note that when $m\not \equiv 0\ (\mathrm{mod}\ 3)$, an optimal 1-D (m, 3, 3, 1)-OOC (or CAC(m, 3)) is also an optimal 1-D (m, 3, 2, 1)-OOC.

u		Source
$0\ (\mathrm{mod}\ 8)$	$0,8\ (\mathrm{mod}\ 32)$	Construction 3.1 in [30]
	$16,24\ (\mathrm{mod}\ 32)$, $\ne 16$	Construction 3.2 in [30]
	16	Theorem 1
$4\ (\mathrm{mod}\ 8)$, $\ne 12$	$4,20\ (\mathrm{mod}\ 24)$	Theorem 1
	$12\ (\mathrm{mod}\ 24)$, $\ne 12$	Constructions 3.6, 3.7 in [30]; discard T
$2\ (\mathrm{mod}\ 8)$	$2,10\ (\mathrm{mod}\ 24)$	Theorem 1
	$18\ (\mathrm{mod}\ 24)$	Constructions 5.3, 5.4 in [30]; discard T
$6\ (\mathrm{mod}\ 8)$	$22,30\ (\mathrm{mod}\ 32)$	Construction 5.5 in [30]
	$6,14\ (\mathrm{mod}\ 32)$	Construction 5.6 in [30]
$1\ (\mathrm{mod}\ 8)$		Construction 3.1, 3.2 in [18]
$3\ (\mathrm{mod}\ 8)$	$3\ (\mathrm{mod}\ 24)$	Construction 3.3 in [18]; discard T
	$11,19\ (\mathrm{mod}\ 24)$	Theorem 1
$5\ (\mathrm{mod}\ 8)$	$21\ (\mathrm{mod}\ 24)$	Construction 3.7, 3.8, 3.9 in [18]; discard T
	$5,13\ (\mathrm{mod}\ 24)$	Theorem 1
$7\ (\mathrm{mod}\ 8)$		Construction 3.10 in [18]

It should be noticed that, when $u\equiv 0,8 \pmod {32}$, although Construction 3.1 in [30] was only used for the cases of $u\equiv 8,32,40,64\pmod {96}$, it is readily checked that the same codewords listed in Construction 3.1 in [30] can also produce our required optimal OOCs for $u\equiv 0,72 \pmod {96}$. The similar things happen when $u\equiv 16,24\pmod {32}$ and $u\equiv 6\pmod {8}$.

We give other two examples to illustrate how to use the table. When $u\equiv 3\ (\mathrm{mod}\ 24)$, in Construction 3.3 of [18], an optimal CAC(m, 3) with $(7m+12)/32$ codewords is constructed, where $m=4u$ and $T=\{0,m/3,2m/3\}$ is one of codewords. Then all codewords of the CAC(m, 3) except for the codeword T constitute an optimal 1-D (m, 3, 2, 1)-OOC with $(7m-20)/32$ codewords.

When $u\equiv 7\ (\mathrm{mod}\ 8)$, in Construction 3.10 of [18], an optimal CAC(m, 3) with $(7m-4)/32$ codewords is constructed, where $m=4u$ and $T=\{0,m/3,2m/3\}$ is not a codeword. Thus this CAC(m, 3) is also an optimal 1-D (m, 3, 2, 1)-OOC with $(7m-4)/32$ codewords. $\square$

Lemma 16

$\varPhi (2\times m,3,2,1)=3m/4$ for any $m\equiv 0\ (\mathrm{mod}\ 4)$, with the exception of $\varPhi (2\times 4,3,2,1)=2$.

Proof

We construct the required codes on $I_2\times Z_m$. When $m\equiv 0\ (\mathrm{mod}\ 8)$ and $m\ge 8$, the required 3m / 4 codewords are

$$\begin{aligned} \begin{array}{ll} \{(0,0),(0,i),(0,2i)\}, &{}i\in [3,m/4-1]_o\cup \{m/2-1\}, (i=3 \,\mathrm{{if}}\, m=8);\\ \{(1,0),(1,i),(1,2i)\}, &{}i\in [m/4+1,m/2-1]_o;\\ \{(0,0),(0,1+2i),(1,m/4-1+i)\},&{} i\in [m/8,m/4-2], (\mathrm{{null\, if}}\, m=8);\\ \{(1,0),(1,1+2i),(0,3m/4+2+i)\},&{} i\in [0,m/8-1];\\ \{(0,0),(0,4+4i),(1,3m/4+1+2i)\},&{} i\in [0,m/8-1];\\ \{(1,0),(1,4+4i),(0,m/4+4+2i)\}, &{}i\in [0,m/8-1];\\ \{(0,0),(0,1),(1,3m/4-1)\}.&{}\\ \end{array} \end{aligned}$$

When $m\equiv 4\ (\mathrm{mod}\ 8)$ and $m\ge 12$, the required 3m / 4 codewords are

$$\begin{aligned} \begin{array}{ll} \{(0,0),(0,i),(0,2i)\}, &{}i\in [m/4+2,m/2-3]_o, \,(\mathrm{{null\, if}}\, m=12);\\ \{(1,0),(1,i),(1,2i)\},&{} i\in [1,m/4]_o;\\ \{(0,0),(0,1+2i),(1,m/4+i)\}, &{}i\in [0,(m-4)/8]\setminus \{1\};\\ \{(1,0),(1,1+2i),(0,3m/4+1+i)\},&{} i\in [(m+4)/8,m/4-1];\\ \{(0,0),(0,4+4i),(1,3m/4+1+2i)\},&{} i\in [1,(m-12)/8],\, (\mathrm{{null\, if}}\, m=12);\\ \{(1,0),(1,4+4i),(0,m/4+2+2i)\},&{} i\in [0,(m-12)/8];\\ \{(0,0),(0,m/2-1),(1,m/4-2)\},&{} \{(0,0),(0,3),(1,3m/4)\},\\ \{(0,0),(0,m/2),(1,3m/4+1)\}, &{}\{(0,0),(0,2),(0,4)\}.\\ \end{array} \end{aligned}$$

When $m=4$, the required two codewords are $\{(0,0),(0,1),(0,2)\}$ and $\{(1,0),(1,1),(1,2)\}$. Lemmas 4 and ensure the optimality of these codes. $\square$

5.2 The case of $n=3$

This section is devoted to constructing optimal 2-D $(3\times m,3,2,1)$-OOCs. By Lemma 2, $\varPhi (3\times m,3,2,1)\le 3m/2+\varPsi ^e(m,3,2,1)$, and so by Remark 1, any optimal 2-D $(3\times m,3,2,$ 1)-OOC must contain 3 optimal equi-difference 1-D (m, 3, 2, 1)-OOCs as subcodes.

5.2.1 $m\equiv 8\ (\mathrm{mod}\ 16)$

Lemma 17

$\varPhi (3\times 8,3,2,1)=13$.

Proof

The required OOC is constructed on $I_3\times Z_8$ as follows:

$$\begin{aligned} \begin{array}{llll} \{(0,0),(0,2),(0,4)\},&{}\{(1,0),(1,2),(1,4)\},&{}\{(2,0),(2,2),(2,4)\};&{}\\ \{(0,0),(0,1),(1,6)\},&{}\{(0,0),(0,3),(1,7)\},&{}\{(1,0),(1,1),(2,5)\},&{}\{(1,0),(1,3),(2,3)\},\\ \{(0,0),(2,5),(2,6)\},&{}\{(0,0),(2,4),(2,7)\};&{}&{}\\ \{(0,0),(1,2),(2,0)\},&{}\{(0,0),(1,3),(2,2)\},&{}\{(0,0),(1,0),(2,1)\},&{}\{(0,0),(1,1),(2,3)\}.\\ \end{array} \end{aligned}$$

The optimality is ensured by Lemma 2 and Theorem 5. Note that each of the first three codewords can be seen as an optimal equi-difference 1-D (8, 3, 2, 1)-OOC, which is defined on $\{x\}\times Z_8$ for some $x\in \{0,1,2\}$. The middle six codewords used up all the remaining pure differences which are not from the first three codewords. All mixed differences are also used up. $\square$

Remark 3

Lemma helps us to understand the structure of codewords of optimal 2-D $(3\times m,3,2,1)$-OOCs with $3m/2+\varPsi ^e(m,3,2,1)$ codewords (if it exists). On one hand, such kind of OOCs must contain three optimal equi-difference 1-D (m, 3, 2, 1)-OOCs as subcodes. On the other hand, all pure differences and mixed differences must be used up. The two facts make it difficult to find effective recursive constructions, especially filling constructions, for optimal 2-D $(3\times m,3,2,1)$-OOCs.

In the following we present three infinite families of optimal 2-D $(3\times m,3,2,1)$-OOCs via direct constructions.

Lemma 18

$\varPhi (3\times m,3,2,1)=(27m-8)/16$ for any $m\equiv 8\ (\mathrm{mod}\ 16)$.

Proof

For $m\equiv 8\ (\mathrm{mod}\ 16)$, by Lemma 2, $\varPhi (3\times m,3,2,1)\le 3m/2+\varPsi ^e(m,3,2,1)$, and by Theorem 4, $\varPsi ^e(m,3,2,1)=(3m-8)/16$. So $\varPhi (3\times m,3,2,1)\le (27m-8)/16$.

When $m\equiv 8\ (\mathrm{mod}\ 16)$ and $m\ge 24$, the required $(27m-8)/16$ codewords are divided into two parts. The first part consists of $(9m-24)/16$ codewords:

$$\begin{aligned} \{(x,0),(x,a),(x,2a)\},\ \ x\in \{0,1,2\}\ \mathrm{and}\ \{0,a,2a\}\in \mathscr {B}, \end{aligned}$$

where $\mathscr {B}$ is an optimal equi-difference 1-D (m, 3, 2, 1)-OOC with $(3m-8)/16$ codewords, whose difference leave is $\{3m/8,5m/8\}\cup [1,m/4-1]_o\cup [3m/4+1,m-1]_o$ (see Theorem 5 by taking $s=1$ and $r=m/4$). The second part consists of $9m/8+1$ codewords:

$$\begin{aligned} \begin{array}{ll} \{(0,0),(0,1+2i),(1,7m/8+i)\}, &{} i\in [0,m/8-1]; \\ \{(1,0),(1,1+2i),(2,m/2+2+i)\}, &{} i\in [0,m/8-1]; \\ \{(0,0),(2,7m/8-3-i),(2,7m/8+i)\}, &{} i\in [0,m/8-2]; \\ \{(0,0),(0,3m/8),(1,3m/4-1)\}, &{} \{(1,0),(1,3m/8),(2,3m/4)\}, \\ \{(0,0),(2,m-1),(2,0)\}, &{} \{(0,0),(2,7m/8-2),(2,m/4-2)\};\\ \{(0,0),(1,i),(2,1+2i)\}, &{} i\in [0,3m/8-2]; \\ \{(0,0),(1,3m/8+i),(2,2+2i)\}, &{} i\in [0,3m/8-2]\setminus \{m/8-2\}; \\ \{(0,0),(1,m/2-2),(2,7m/8-1)\}. \end{array} \end{aligned}$$

When $m=8$, the conclusion follows from Lemma . $\square$

5.2.2 $m\equiv 32\ (\mathrm{mod}\ 64)$

Lemma 19

$\varPhi (3\times m,3,2,1)=(107m-32)/64$ for any $m\equiv 32\ (\mathrm{mod}\ 64)$.

Proof

For $m\equiv 32\ (\mathrm{mod}\ 64)$, by Lemma 2, $\varPhi (3\times m,3,2,1)\le 3m/2+\varPsi ^e(m,3,2,1)$, and by Theorem 4, $\varPsi ^e(m,3,2,1)=(11m-32)/64$. So $\varPhi (3\times m,3,2,1)\le (107m-32)/64$.

When $m=32$, an optimal 2-D $(3\times 32,3,2,1)$-OOC with 53 codewords is listed as follows:

$$\begin{aligned} \{(x,0),(x,a),(x,2a)\},\ \ x\in \{0,1,2\} \mathrm{{and}}\, a\in \{8,9,11,13,15\};\\ \begin{array}{lll} \{(0,0), (0,12), (1,25)\},&{}\{(0,0), (0,1), (1,6)\},&{}\{(0,0), (0,3), (1,7)\},\\ \{(0,0), (0,5), (1,8)\},&{} \{(0,0), (0,7), (1,9)\},&{} \{(0,0), (0,4), (1,31)\},\\ \{(1,0), (1,1), (2,14)\},&{} \{(1,0), (1,12), (2,23)\},&{} \{(1,0), (1,3), (2,20)\},\\ \{(1,0), (1,5), (2,21)\},&{} \{(1,0), (1,7), (2,22)\},&{} \{(1,0), (1,4), (2,31)\},\\ \{(0,0), (2,9), (2,21)\},&{} \{(0,0), (2,0), (2,1)\},&{} \{(0,0), (2,7), (2,10)\},\\ \{(0,0), (2,6), (2,11)\},&{} \{(0,0), (2,5), (2,12)\},&{} \{(0,0), (2,22), (2,26)\};\\ \{(0,0), (1,0), (2,8)\},&{} \{(0,0), (1,1), (2,4)\},&{} \{(0,0), (1,10), (2,28)\},\\ \{(0,0), (1,19), (2,31)\},&{} \{(0,0), (1,21), (2,30)\},&{} \{(0,0), (1,22), (2,29)\},\\ \{(0,0), (1,12), (2,14)\},&{} \{(0,0), (1,14), (2,20)\},&{} \{(0,0), (1,15), (2,19)\},\\ \{(0,0), (1,16), (2,16)\},&{} \{(0,0), (1,17), (2,18)\},&{} \{(0,0), (1,18), (2,23)\},\\ \{(0,0), (1,11), (2,3)\},&{} \{(0,0), (1,20), (2,13)\},&{} \{(0,0), (1,23), (2,17)\},\\ \{(0,0), (1,24), (2,2)\},&{} \{(0,0), (1,26), (2,24)\},&{} \{(0,0), (1,28), (2,15)\},\\ \{(0,0), (1,29), (2,25)\},&{} \{(0,0), (1,30), (2,27)\}.\\ \end{array} \end{aligned}$$

Note that for any $x\in \{0,1,2\}$, $\{\{(x,0),(x,a),(x,2a)\}:a\in \{8,9,11,13,15\}\}$ forms an optimal equi-difference 1-D (32, 3, 2, 1)-OOC defined on $\{x\}\times Z_{32}$, whose difference leave is $\{1,3,4,5,7,12,20,25,27,28,29,31\}$ (see Theorem 5 by taking $s=2$ and $r=2$).

When $m\equiv 32\ (\mathrm{mod}\ 64)$ and $m\ge 96$, the required $(107m-32)/64$ codewords are divided into two parts. The first part consists of $(33m-96)/64$ codewords:

$$\begin{aligned} \{(x,0),(x,a),(x,2a)\},\ \ x\in \{0,1,2\}\ \mathrm{and}\ \{0,a,2a\}\in \mathscr {B}, \end{aligned}$$

where $\mathscr {B}$ is an optimal equi-difference 1-D (m, 3, 2, 1)-OOC with $(11m-32)/64$ codewords, whose difference leave is $\{3m/8,5m/8\}\cup [1,m/4-1]_o\cup [3m/4+1,m-1]_o\cup (4\cdot ([1,m/16-1]_o\cup [3m/16+1,m/4-1]_o))$ (see Theorem 5 by taking $s=2$ and $r=m/16$). The second part consists of $37m/32+1$ codewords:

$$\begin{aligned}&\begin{array}{ll} \{(0,0),(0,1+2i),(1,m/8+2+i)\},&{} i\in [0,m/8-1];\\ \{(0,0),(0,4+8i),(1,7m/8+3+4i)\}, &{}i\in [0,m/32-1];\\ \{(1,0),(1,3+2i),(2,5m/8+i)\}, &{} i\in [0,m/8-2];\\ \{(1,0),(1,4+8i),(2,7m/8+3+4i)\}, &{} i\in [0,m/32-1]; \\ \{(0,0),(2,m/4-1-i),(2,m/4+2+i)\}, &{} i\in [0,m/8-2]; \\ \{(0,0),(2,3m/4-2-4i),(2,3m/4+2+4i)\}, &{} i\in [0,m/32-1]; \\ \end{array}\\&\begin{array}{lll} \{(0,0),(0,3m/8),(1,13m/16-1)\},\ &{} \{(1,0),(1,1),(2,7m/16)\},\\ \{(1,0),(1,3m/8),(2,3m/4-1)\},\ &{}\{(0,0),(2,m/4+1),(2,5m/8+1)\},\\ \{(0,0),(2,m/16-2),(2,m/16-1)\};\\ \end{array}\\&\begin{array}{ll} \{(0,0),(1,3m/4+2i),(2,3m/4-3-2i)\}, &{} i\in [0,m/16-1]\setminus \{m/16-2\}; \\ \{(0,0),(1,7m/8+2i),(2,5m/8+4i)\}, &{} i\in [0,m/16-1]; \\ \{(0,0),(1,3m/4+1+4i),(2,3m/4-1+2i)\}, &{} i\in [0,m/16-1]\setminus \{(m-32)/64\}; \\ \{(0,0),(1,m/4+2+2i),(2,3m/8+1+i)\}, &{} i\in [0,m/8-2]; \\ \{(0,0),(1,m/4+3+2i),(2,m/2+1+i)\}, &{} i\in [0,m/8-3]\setminus \{3m/32-2\}; \\ \{(0,0),(1,m/2+4+2i),(2,1+i)\}, &{} i\in [0,m/8{-}3]\setminus \{m/16{-}3,m/16{-}2\}; \\ \{(0,0),(1,m/2+1+2i),(2,7m/8-1+i)\}, &{} i\in [0,m/8-4]; \\ \end{array}\\&\begin{array}{lll} \{(0,0),(1,0),(2,0)\},\ &{} \{(0,0),(1,1),(2,m/4)\},\\ \{(0,0),(1,m/2-1),(2,m-3)\},\ &{} \{(0,0),(1,m/2),(2,m/8-1)\},\\ \{(0,0),(1,m/2+2),(2,m/8)\},\ &{} \{(0,0),(1,3m/4-5),(2,m/2)\},\\ \{(0,0),(1,3m/4-3),(2,m-2)\},\ &{} \{(0,0),(1,3m/4-1),(2,m-1)\},\\ \{(0,0),(1,7m/8-4),(2,m-4)\},\ &{} \{(0,0),(1,5m/8-2),(2,25m/32-2)\},\\ \{(0,0),(1,5m/8),(2,19m/32-1)\}. \\ \end{array} \end{aligned}$$

5.2.3 $m\equiv 4,20\ (\mathrm{mod}\ 48)$

Lemma 20

$\varPhi (3\times 4,3,2,1)=6$.

Proof

The required OOC is constructed on $I_3\times Z_4$ as follows:

$$\begin{aligned} \begin{array}{llll} \{(x,0),(x,1),(x,2)\},&\{(0,0),(1,a),(2,b)\}, \end{array} \end{aligned}$$

where $x\in \{0,1,2\}$ and $(a,b)\in \{(0,0),(1,3),(3,2)\}$. The optimality is ensured by Lemma . $\square$

Lemma 21

Let $m>4$ and $m\equiv 4,20\ (\mathrm{mod}\ 48)$ satisfying that for any prime factor p of m / 4, $p\equiv 1\ (\mathrm{mod}\ 4)$ and $4|ord_{p}(2)$ whenever $p\equiv 1\ (\mathrm{mod}\ 8)$. Then $\varPhi (3\times m,3,2,1)=(27m+4)/16$.

Proof

For any m given in the assumption, by Lemma 2, $\varPhi (3\times m,3,2,1)\le 3m/2+\varPsi ^e(m,3$, 2, 1), and by Theorem 6(2), $\varPsi ^e(m,3,2,1)=(3m+4)/16$. So $\varPhi (3\times m,3,2,1)\le (27m+4)/16$.

When $m=20$, an optimal 2-D $(3\times 20,3,2,1)$-OOC with 34 codewords is listed as follows:

$$\begin{aligned} \{(x,0),(x,i),(x,2i)\},\ \ x\in \{0,1,2\} \;\mathrm{and}\; i\in \{4,5,7,9\};\quad \quad \quad \quad \quad \quad \quad \quad \,\,\\ \begin{array}{lll} \{(0,0),(0,1),(1,18)\},&{} \{(0,0),(0,3),(1,19)\},&{} \{(1,0),(1,1),(2,18)\},\\ \{(1,0),(1,3),(2,19)\},&{} \{(0,0),(2,17),(2,18)\},&{} \{(0,0),(2,16),(2,19)\};\\ \{(0,0),(1,a),(2,b)\},&{}&{}\\ \end{array} \end{aligned}$$

where $(a,b)\in \{(0,1),(1,3),(2,2),(3,11),(4,13),(5,10),(6,9),(7,14),(8,12), (9,15),(10$, $0),(11,4),(12,7),(13,5),(14,8),(15,6)\}$. Note that for any $x\in \{0,1,2\}$, $\{\{(x,0),(x,i),(x$, $2i)\}:i\in \{4,5,7,9\}\}$ forms an optimal equi-difference 1-D (20, 3, 2, 1)-OOC defined on $\{x\}\times Z_{20}$, whose difference leave is $\{1,3,17,19\}$ (see Theorem 6(2) by taking $s=1$ and $r=5$).

When $m=52$, an optimal 2-D $(3\times 52,3,2,1)$-OOC with 88 codewords is listed as follows:

$$\begin{aligned} \begin{array}{ll} \{(x,0),(x,i),(x,2i)\}, &{} x\in \{0,1,2\} \;\mathrm{and}\; i\in \{4,12,16,13,15,17,19,21,23,25\};\\ \{(0,0),(0,1+2i),(1,46+i)\}, &{} i\in [0,5];\\ \{(1,0),(1,1+2i),(2,46+i)\}, &{} i\in [0,5];\\ \{(0,0),(2,45-i),(2,46+i)\}, &{} i\in [0,5];\\ \{(0,0),(1,a),(2,b)\}, \end{array} \end{aligned}$$

where $(a,b)\in \{(0,12), (2,6), (3,8), (4,14), (5,5), (6,7), (11,13), (1,16), (14,22), (16,19)$, $(18,24), (7,28), (12,25), (13,27), (22,29), (8,30), (9,32), (10,34), (20,31), (24,33), (15, 35),(17,36), (19,37), (21,38), (23,39), (33,15), (34,18), (27,0), (28,2), (29,4)$, $(30,10),(32,11),(25,1), (31,9), (26,3), (35,21), (36,17), (37,20), (38,23), (39,26)\}$. Note that for any $x\in \{0,1,2\}$, $\{\{(x,0),(x,i),(x,2i)\}:i\in \{4,12,16,13,15,17,19,21,23,25\}\}$ forms an optimal equi-difference 1-D (52, 3, 2, 1)-OOC defined on $\{x\}\times Z_{52}$, whose difference leave is $[1,11]_o\cup [41,51]_o$ (see Theorem 6(2) by taking $s=1$ and $r=13$).

When $m\equiv 4,20\ (\mathrm{mod}\ 48)$, $m\ge 68$ and m satisfies the condition in the assumption, the required $(27m+4)/16$ codewords are divided into three parts. The first part consists of $(9m+12)/16$ codewords:

$$\begin{aligned} \{(x,0),(x,a),(x,2a)\},\ \ x\in \{0,1,2\}\ \mathrm{and}\ \{0,a,2a\}\in \mathscr {B}, \end{aligned}$$

where $\mathscr {B}$ is an optimal equi-difference 1-D (m, 3, 2, 1)-OOC with $(3m+4)/16$ codewords, whose difference leave is $[1,m/4-1]_o\cup [3m/4+1,m-1]_o$ (see Theorem 6(2) by taking $s=1$ and $r=m/4$). The second part consists of $(3m+108)/8$ codewords:

$$\begin{aligned} \begin{array}{ll} \{(0,0),(0,1+2i),(1,(7m+4)/8+i)\}, &{} i\in [0,(m-20)/8]; \\ \{(1,0),(1,1+2i),(2,m/2+i)\}, &{} i\in [0,(m-12)/8]; \\ \{(0,0),(2,(7m-12)/8-i),(2,(7m-4)/8+i)\}, &{} i\in [0,(m-12)/8]; \\ \{(0,0),(0,m/4-2),(1,(11m-12)/16)\}, &{} \{(0,0),(1,(3m-4)/8),(2,(m-4)/16)\}, \\ \{(0,0),(1,(9m+12)/16),(2,m/2-1)\}, &{} \{(0,0),(1,(3m+4)/8),(2,(3m+4)/16)\},\\ \{(0,0),(1,3m/4+1),(2,2)\}, &{} \{(0,0),(1,m-1),(2,3m/4-3)\},\\ \{(0,0),(1,m/4),(2,m-1)\}, &{} \{(0,0),(1,m/4-1),(2,m/4-3)\},\\ \{(0,0),(1,3m/4),(2,0)\}, &{} \{(0,0),(1,(3m+12)/8),(2,(m+12)/8)\},\\ \{(0,0),(1,(5m-4)/8),(2,m/4-1)\}, &{} \{(0,0),(1,(5m+4)/8),(2,m/4+1)\},\\ \{(0,0),(1,3m/4-1),(2,(5m-20)/8)\}, &{} \{(0,0),(1,m/2+1),(2,(3m+4)/8)\},\\ \{(0,0),(1,m/2),(2,m/2)\}, &{} \{(0,0),(1,m/2-1),(2,m/2-2)\}. \end{array} \end{aligned}$$

The third part consists of $(3m-56)/4$ codewords. Let $T=[0,(3m-36)/8]\setminus \{(m-20)/16,$$(m-28)/8,(m-20)/8,(m-12)/8,(3m-28)/16, m/4-3,m/4-2,(5m-52)/16\}$. If $m\equiv 4,68\ (\mathrm{mod}\ 96)$ and $m\ge 68$, then we take

$$\begin{aligned} \begin{array}{ll} \{(0,0),(1,i),(2,1+2i)\}, &{} i\in [0,(3m-12)/8]\setminus \{(3m-12)/32,m/4-1,m/4\}; \\ \{(0,0),(1,(3m-12)/32),(2,3m/4-1)\}, &{} \{(0,0),(1,(13m+12)/32),(2,m/2+1)\}; \\ \{(0,0),(1,(3m+20)/8+i),(2,4+2i)\}, &{} i\in T\setminus \{(m-68)/32\}. \end{array} \end{aligned}$$

If $m\equiv 20,52\ (\mathrm{mod}\ 96)$ and $m\ge 116$, then we take

$$\begin{aligned} \begin{array}{ll} \{(0,0),(1,i),(2,1+2i)\}, &{} i\in [0,(3m-12)/8]\setminus \{(m-20)/32,m/4-1,m/4\}; \\ \{(0,0),(1,(15m+20)/32),(2,m/2+1)\}, &{} \{(0,0),(1,(m-20)/32),(2,3m/4-1)\};\\ \{(0,0),(1,(3m+20)/8+i),(2,4+2i)\}, &{} i\in T\setminus \{(3m-60)/32\}. \end{array} \end{aligned}$$

5.3 A recursive construction from m-cyclic group divisible designs

Let K be a set of positive integers. A group divisible design (GDD) K-GDD is a triple ($X, {{\mathscr {G}}},{{\mathscr {A}}}$) satisfying that (1) ${\mathscr {G}}$ is a partition of a finite set X into subsets (called groups); (2) ${\mathscr {A}}$ is a set of subsets of X (called blocks), each of cardinality from K, such that every 2-subset of X is either contained in exactly one block or in exactly one group, but not in both. If ${\mathscr {G}}$ contains $u_i$ groups of size $g_i$ for $1\le i\le r$, then we call $g_1^{u_1}g_2^{u_2}\cdots g_r^{u_r}$ the type of the GDD. If $K=\{k\}$, we write k-GDD instead of $\{k\}$-GDD.

An automorphism group of a GDD $(X,{{\mathscr {G}}},{{\mathscr {A}}})$ is a permutation group on X leaving ${{\mathscr {G}}}$ and ${{\mathscr {A}}}$ invariant, respectively. Given an automorphism group of a GDD, all blocks of the GDD can be partitioned into some orbits under this automorphism group. Choose any fixed block from each orbit and call it a base block of the GDD.

Suppose $(X,\mathscr {G},\mathscr {A})$ is a K-GDD of type $(v_{1}m)^{u_1} (v_{2}m)^{u_2}\cdots (v_{r}m)^{u_r}$. If its automorphism group contains a permutation on X that is the product of $\sum _{i=1}^{r}v_iu_i$ disjoint m-cycles fixing each group of ${\mathscr {G}}$ and leaving $\mathscr {A}$ invariant, then this design is said to be m-cyclic.

Lemma 22

[37] An m-cyclic 3-GDD of type $(vm)^u$ exists if and only if (1) when $u=3$, m is odd, or m is even and v is even; (2) when $u\ge 4$, $(u-1)vm\equiv 0 \pmod {2}$, $u(u-1)vm\equiv 0 \pmod {3}$, and $v\equiv 0 \pmod {2}$ if $u\equiv 2,3 \pmod {4}$ and $m\equiv 2 \pmod {4}$.

The following construction is a variation of Construction 4.6 in [17].

Construction 9

Suppose that there exist

(1):

an m-cyclic k-GDD of type $(v_{1}m)^{u_1} (v_{2}m)^{u_2}\cdots (v_{r}m)^{u_r}$ with b base blocks;

(2):

a 2-D $(v_i\times m,k,\lambda _a,1)$-OOC with $f_i$ codewords for each $1\le i\le r$.

Then there exists a 2-D $((\sum _{i=1}^r v_i u_i)\times m,k,\lambda _a,1)$-OOC with $b+\sum _{i=1}^r u_if_i$ codewords.

Lemma 23

Let $m\equiv 0\ (\mathrm{mod}\ 4)$. If there is an optimal 2-D $(3\times m,3,2,1)$-OOC with $3m/2+\varPsi ^e(m,3,2,1)$ codewords, then there is an optimal 2-D $(n\times m,3,2,1)$-OOC with $n(nm+2\varPsi ^e(m,3,2,1))/6$ codewords for any $n\equiv 0\ (\mathrm{mod}\ 3)$ and $n\ge 12$.

Proof

By Lemma 22, there exists an m-cyclic 3-GDD of type $(3m)^{n/3}$ for any $m\equiv 0\ (\mathrm{mod}\ 4)$, $n\equiv 0\ (\mathrm{mod}\ 3)$ and $n\ge 12$, which contains $mn(n-3)/6$ base blocks. Then apply Construction 9 with an optimal 2-D $(3\times m,3,2,1)$-OOC with $3m/2+\varPsi ^e(m,3,2,1)$ codewords to obtain a 2-D $(n\times m,3,2,1)$-OOC with $n(nm+2\varPsi ^e(m,3,2,1))/6$ codewords, which is optimal by Lemma 2. $\square$

Corollary 1

$$\begin{aligned} \varPhi (n\times m,3,2,1)=\left\{ \begin{array}{lll} n(8nm+3m-8)/48, &{} n\equiv 0\ (\mathrm{mod}\ 3),\ n\ne 6,9, \mathrm{\ and\ } \\ &{} m\equiv 8\ (\mathrm{mod}\ 16);\\ n(32nm+11m-32)/192, &{} n\equiv 0\ (\mathrm{mod}\ 3),\ n\ne 6,9, \mathrm{\ and\ } \\ &{} m\equiv 32\ (\mathrm{mod}\ 64);\\ n(8nm+3m+4)/48, &{} n\equiv 0\ (\mathrm{mod}\ 3),\ n\ne 6,9,\ m>4, \\ &{} m\equiv 4,20\ (\mathrm{mod}\ 48), \mathrm{\ and\ } m/4\in S,\\ \end{array} \right. \end{aligned}$$

where S is the set of positive integers such that for any $s\in S$, it holds that $s\equiv 1,5\ (\mathrm{mod}\ 12)$, and every prime divisor p of s satisfies $p\equiv 5\ (\mathrm{mod}\ 8)$, or $p\equiv 1\ (\mathrm{mod}\ 8)$ and $4|ord_p(2)$.

Proof

By Lemmas 18, 19 and 21, there is an optimal 2-D $(3\times m,3,2,1)$-OOC with $3m/2+\varPsi ^e(m,3,2,1)$ codewords, where

$$\begin{aligned} \varPsi ^e(m,3,2,1)=\left\{ \begin{array}{lll} (3m-8)/16, &{} m\equiv 8\ (\mathrm{mod}\ 16);\\ (11m-32)/64, &{} m\equiv 32\ (\mathrm{mod}\ 64);\\ (3m+4)/16, &{} m\equiv 4,20\ (\mathrm{mod}\ 48), m>4 \mathrm{\ and\ } m/4\in S. \end{array} \right. \end{aligned}$$

Then apply Lemma 23 to obtain an optimal 2-D $(n\times m,3,2,1)$-OOC with $n(nm+2\varPsi ^e(m,3,$ 2, 1)) / 6 codewords. $\square$

Combining the results of Lemmas 15, 16, 5 and Corollary 1, one can complete the proof of Theorem 2.

6 Concluding remarks

In Sect. 5.2, we present several direct constructions for optimal 2-D $(3\times m,3,2,1)$-OOCs. Start from these 2-D OOCs and then apply Construction 9 by using m-cyclic 3-GDDs to get some optimal 2-D $(n\times m,3,2,1)$-OOC for any $n\equiv 0\ (\mathrm{mod}\ 3)$ and $n\ge 12$.

Actually to deal with the case of $n\equiv 4\ (\mathrm{mod}\ 6)$, by similar arguments, we can have the following lemma, in which all the input OOCs are required to attain the upper bound in Lemma 2. The reader can check that the output OOC can also attain the upper bound in Lemma 2.

Lemma 24

Let $m\equiv 0\ (\mathrm{mod}\ 4)$. Suppose that there exist

(1):

an m-cyclic 3-GDD of type $(6m)^{u} (4m)^{1}$, which has $2mu(1+3u)$ base blocks;

(2):

an optimal 2-D $(6\times m,3,2,1)$-OOC with $6m+2\varPsi ^e(m,3,2,1)$ codewords;

(3):

an optimal 2-D $(4\times m,3,2,1)$-OOC with $\lfloor (8m+4\varPsi ^e(m,3,2,1))/3 \rfloor$ codewords.

Then there is an optimal 2-D $((6u+4)\times m,3,2,1)$-OOC with $\lfloor (6u+4)((6u+4)m+2\varPsi ^e(m,$$3,2,1))/6 \rfloor$ codewords.

By standard design theoretic techniques, it is readily checked that an m-cyclic 3-GDD of type $(6m)^u(4m)^1$ exists for any $m\equiv 0\ (\mathrm{mod}\ 4)$ and $u\ge 3$. However, as we pointed out in Remark 3, it seems to be difficult to find effective recursive constructions, especially filling constructions, for optimal 2-D $(4\times m,3,2,1)$-OOCs and optimal 2-D $(6\times m,3,2,1)$-OOCs. Even though by tedious computation and analysis, direct constructions should always work, that could not be a good way. A better technique is desired for this problem.

On the other hand, by Lemma 2, we see that the size of an optimal 2-D $(n\times m,3,2,1)$-OOC relies heavily on the size of an optimal equi-difference 1-D (m, 3, 2, 1)-OOC. The latter is closely related to optimal equi-difference CAC(m, 3)s. This provides another motivation to study equi-difference CAC(m, 3)s.