Separable detecting arrays

1.   Introduction

Throughout this paper, the set $\{1, 2, \cdots, n\}$ for a positive integer $n$ is denoted by $I_n$. Combinatorial interaction testing (CIT) has emerged as a fundamental software testing paradigm aimed at detecting faults arising from intricate interactions among test parameters in complex software systems ^[24,29]. Kuhn et al. studied faults in several software projects, and found that all the known faults are caused by interactions among six or fewer parameters ^[25,26]. Based on this finding, CIT has been shown to be highly effective for specific applications, providing performance comparable to exhaustive testing while utilizing significantly fewer test cases. Typically, the test suites employed in CIT are structured as arrays, with each row corresponding to an individual test case and each column representing a distinct test parameter. The mathematical structures employed in CIT are $t$-way covering arrays ($t$-CAs). In a $t$-CA, every interaction involving $t$ parameters is guaranteed to appear in at least one test case, ensuring comprehensive coverage of all $t$-way interactions.

CAs have garnered significant research attention, leading to the development of diverse methodologies and substantial findings, which are comprehensively documented in the academic literature. For researchers interested in further exploring this topic, the following references are highly recommended: Colbourn provided valuable insights into CAs of strength two ^[7]; Chateauneuf et al. conducted comprehensive studies on CAs of strength three ^[4,5]; Colbourn et al. introduced Roux-type constructions for CAs with strengths of both three and four ^[9]; Ji and Yin constructed CAs of strength three utilizing difference covering arrays ^[22]; Hartman et al. discussed algorithms pertinent to CAs in detail ^[18,31]; while Tzanakis et al. illuminated special constructions derived from $m$-sequences ^[42]. In generating test suites using CAs, each column meticulously represents distinct factors that impact the system's response, with the entries within each column specifying various settings or values associated with those factors. This process constitutes a crucial step in scrutinizing a system for potential interaction faults prior to its release.

However, while testing with a CA is effective for detecting the presence of interaction faults, it provides little information to identify and determine faulty corrections. To address this, Colbourn and McClary introduce $(d, t)$-locating arrays (LAs) and $(d, t)$-detecting arrays (DAs) under the assumption that the system contains (at most) a certain number $d$ of faults, each involving (at most) a certain number $t$ of interacting factors in ^[10]. They conducted a thorough analysis of the mathematical properties associated with these arrays. We specifically focus on detecting arrays in this paper. As outlined in ^[10], the majority of studies on detecting arrays have primarily centered on their mathematical characteristics and constructions. For instance, uniform $(1, t)$-detecting arrays with a limited number of factors were studied in ^[41]. Subsequently, this research was broadened to $(d, t)$-detecting arrays in ^[36], with a focus on independent interaction faults, as discussed in ^[39], and later extended to mixed detecting arrays in ^[37]. In ^[40], optimum detecting array with $5$ factors was almost determined. Notably, when $t = 1$, $(1, 1)$-detecting arrays are equivalent to $(n, v)$-Sperner partition system, which was initially introduced in ^[28]. These arrays can be perceived as a natural extension of the Sperner family. For a $(n, v)$-Sperner partition system, the maximum number of classes has been precisely determined for an infinite number of $n$ values, as reported in ^[27,28]. Furthermore, ^[3] and^[] have established both lower and upper bounds for all possible values of $n$ and each $v$. Algorithmic approaches for $(1, t)$-mixed level detecting arrays were developed and documented in ^[33]. Additionally, other array types designed specifically for fault localization include consecutive detecting arrays, as explored in ^[35,38].

In practical application, detecting arrays may encounter various challenges. For example, one or more tests may fail to execute correctly, and resulting in either no response or outlier responses. To tackle this issue, Seidel et al. ^[33] introduced the concept of "separation" into the definition of detection arrays, aiming to quantify the tolerance for unreliable test outcomes. This concept gives rise to the notion of detecting arrays with separation, also known as separable detecting arrays (SDAs). SDAs, particularly those for main effects (i.e., where $t = 1$), are constructed using error-correcting codes and separating hash families. The techniques are shown to yield explicit constructions with few tests for large numbers of factors ^[11,12]. Furthermore, a local optimization method for $(1, 2)$-detecting arrays with reduced separation is presented in ^[33]. However, to the best of our knowledge, there are currently no widely recognized results for $t > 1$ with general separation, highlighting a significant research gap.

The remainder of this paper is structured as follows: Section $2$ provides a detailed exposition of the definitions of CAs, DAs, and SDAs. Section $3$ establishes a general criterion for assessing the optimality of an SDA based on its size, and subsequently characterizes the equivalence between SDAs with optimum size and orthogonal arrays possessing specified properties. Section $4$ presents optimum SDAs based on the known results of orthogonal arrays and constructs optimum SDAs from difference matrices (DMs) possessing the 'super-simple' property. Several infinite classes of such DMs are provided. Specifically, the existence of super-simple DMs with rows $4$ are fully determined. Finally, we conclude this paper in Section $5$.

2.   Preliminaries

2.1.   Definitions and terminology

We define the nonnegative integers $d$, $\delta$, $N$, $t$, $k$, and $v$ with the conditions $t < k$ and $\delta > 0$. We consider a system under test (SUT) comprising $k$ parameters (or factors), each of which assumes one of $v$ possible values from the symbol set $V$. A test case is represented as a $k$-tuple $(\sigma_1, \sigma_2, \cdots, \sigma_k)$, where $\sigma_i\in V$ for all $i = 1, 2, \cdots, k$. Upon execution, a test case produces a response, either a pass or a fail outcome. A collection of these $k$-tuples forms a test suite specifically designed for the SUT. Typically, a test suite is visualized as an $N\times k$ array, where each row corresponds to a test case, each column represents a distinct system parameter, and each entry within the array denotes the value assigned to that parameter in the corresponding test case. Here, $N$ denotes the total number of test cases, synonymous with the size of the test suite.

Consider an array $A = (a_{ij})\ (i \in I_N, j\in I_k)$ over an alphabet $V$ of size $v$. Each column of the array $A$ represents one of the $k$ factors that may potentially influence the outcome of a test case (where each test case is represented by a row). For any subset of column indices ${j_1, j_2, \cdots, j_t}$ such that $1\le j_1 < j_2 < \cdots < j_t \le k$ and any $t$-tuple $(x_1, x_2, \cdots, x_t) \in V^t$, the set $T = \{(j_r, x_r): 1\leq r\leq t \}$ is defined as a $t$-way interaction of the array. The integer $t$ signifies the strength of the interaction. Formally, a test case $\sigma = (\sigma_1, \sigma_2, \cdots, \sigma_k)$ covers an interaction $T = \{(j_r, x_r): 1\leq r\leq t \}$ if, and only if, $\sigma_{j_r} = x_r$ for all $r$. Let $\rho(A, T)$ denote the set of indices of rows in $A$ that cover the interaction $T$, defined as $\rho(A, T) = \{i: a_{ij_r} = x_r, 1\le r\le t\}$. For an arbitrary set $\mathcal {T}$ of interactions, we define $\rho (A, \mathcal {T}) = \cup_{T\in {\cal T}}\rho (A, T)$.

Let $\mathcal {I}_t$ denote the set of all $t$-way interactions in $A$. To detect the presence or absence of faulty interactions in the SUT, it is necessary to ensure that each $t$-way interaction is covered at least once. This implies $|\rho(A, T)|\geq 1$ for each $t$-way interaction $T$. Subsequently, we give the definition of a CA. A CA$_\lambda(N; t, k, v)$ over $V$ is defined as

In other words, a CA of size $N$, strength $t$, degree $k$, index $\lambda$, and order $v$, or a CA$_\lambda(N; t, k, v)$, is an $N\times k$ array with entries from a set $V$ of $v$ symbols such that in any $t$ columns of the array, all $t$-tuples in $V^t$ occur as rows at least $\lambda$ times. When $\lambda = 1$, we use the notation CA$(N; t, k, v)$. It is evident from the definition that $N\geq \lambda v^t$. If $N = \lambda v^t$ in a CA$_\lambda(N; t, k, v)$, then it is defined as an orthogonal array, denoted by OA$_\lambda(t, k, v)$. Extensive research has been conducted on various related orthogonal arrays, particularly graph-orthogonal arrays ^[14,20].

In contrast to $t$-CAs, DAs offer the advantage of not only detecting the existence of faulty interactions but also locating them. DAs were initially introduced by Colbourn and McClary ^[10] and later extended to include DAs with separation, as discussed in ^[33]. Let $A$ be a CA$_\lambda(N; t, k, v)$. If, for any ${\cal T}\subseteq \mathcal {I}_t$ with $|{\cal T}| = d$ and any $T\in \mathcal {I}_t$, we have

then the array $A$ is called an SDA and denoted as a $(d, t, \delta)$-SDA$(N; k, v)$. Here, the parameter $d$ signifies the maximum number of faulty interactions that the array can accurately identify, $t$ denotes the strength of the target interactions, and $\delta$ represents the separation of the separable detecting arrays. Rows in $\rho(A, T)\setminus \rho(A, {\cal T})$ act as witnesses for $T$ that remain unmasked by interactions in ${\cal T}$. Separation by distance $\delta$ ensures that any $\delta-1$ or fewer tests can fail to provide a response, or provide an outlier response, without losing the differentiation supported by the SDAs.

It is evident that when $T\in {\cal T}$, the set of rows covering interaction $T$ is necessarily contained within the set of rows covering the entire set of target interactions ${\mathcal T}$, formally $\rho(A, T)\subseteq \rho(A, {\mathcal T})$. This direct implication ensures that $|\rho(A, T)\setminus \rho(A, {\cal T})| = 0$ always holds. Consequently, the condition $|\rho(A, T)\setminus \rho(A, {\cal T})| < \delta \Leftrightarrow T\in {\cal T}$ naturally translates to $|\rho(A, T)\setminus \rho(A, {\cal T})|\geq \delta$, when $T \not\in {\mathcal T}$. Setting $d = 0$ in the definition, ${\cal T} = \emptyset$, and $\rho(A, {\cal T}) = \emptyset$ implies $|\rho(A, T)|\geq \delta$ when $T \not = \emptyset$. This implies that $A$ is a CA$_\delta(N; t, k, v)$. Furthermore, by assigning $\delta = 1$ in the $(d, t, \delta)$-SDA$(N; k, v)$, if $|\rho(A, T)\setminus \rho(A, {\cal T})| < \delta = 1$, then $|\rho(A, T)\setminus \rho(A, {\cal T})| = 0$. It becomes evident that $\rho(A, T)\subseteq \rho(A, {\cal T})$ due to the condition $|\rho(A, T)|\geq \delta = 1$. Thus, the notion of $(d, t, \delta)$-SDA$(N; k, v)$ can be viewed as a generalization for $(d, t)$-DA$(N; k, v)$. Since the rows of an SDA represent tests affecting money, time, and other resources, an SDA of minimum size is of particular interest when its other parameters have been fixed. We designate $(d, t, \delta)$-SDAN$(k, v)$ as the minimum $N$ for which a $(d, t, \delta)$-SDA$(N; k, v)$ exists, referring to this quantity as the SDA number. An array that achieves this minimal size, i.e., $N = (d, t, \delta)$-SDAN$(k, v)$, is said to be optimum. In the next section, we will give the lower bounds and combinatorial characterization.

2.2.   An application example

A model for the SUT in electronic commerce systems (ECS) is presented in Table 1. The ECS comprises four components: client, operating system (OS), web server, and payment, each of which can assume one of three distinct values. Exhaustive testing would require conducting $3^4 = 81$ tests. Table 2 displays a test suite consisting of $27$ carefully selected tests from the total possibilities, representing a $(1, 2, 2)$-SDA$(4, 3)$. Such SDA allows for the identification of a faulty interaction of strength two based on test outcomes, provided that the number of outlier or nonresponsive results does not exceed $1$. For instance, the interaction $((F_1, Opera), (F_2, Win))$ is deemed faulty if tests $1, 2$, and $3$ fail, test $11$ yields no response or an outlier response, and all other tests pass. Suppose the outcomes are as follows: tests $1$, $2$, and $3$ fail; tests $11$ and $20$ yield no response or an outlier response; and all other tests pass. In this case, we conclude that $((F_1, Opera), (F_2, Win))$ is a faulty interaction. However, $((F_2, Win), (F_3, Apache))$ might also be faulty, but it is obscured by the presence of $((F_1, Opera), (F_2, Win))$.

3.   Lower bounds and combinatorial characterization

3.1.   A lower bound on the size of $(d, t, \delta)$-SDA$(k, v)'$s

This subsection aims to establish a lower bound on the size of a $(d, t, \delta)$-SDA$(k, v)$. There exist specific permissible parameters that govern the existence of $(d, t, \delta)$-SDAs. Notably, in scenarios where $k < t$, $d < 0$, or $\delta < 0$, the existence of $(d, t, \delta)$-SDA's is not feasible. Furthermore, when $t = k$, an optimum SDA is simply the exhaustive array. Therefore, our focus will be on cases where $k > t$ and $\delta\geq 1$. Initially, we can deduce the following outcome from the definition of a $(d, t, \delta)$-SDA.

Lemma 3.1. Suppose that $A$ is a $(d, t, \delta)$-SDA$(N; k, v)$ with $d\geq 1$. Then $A$ is also a $(d-1, t, \delta)$-SDA$(N; k, v)$ and a $(d, t, \delta-1)$-SDA$(N; k, v)(\delta > 1)$, respectively.

Proof. Let $A$ be the given $(d, t, \delta)$-SDA$(N; k, v)$. According to the definition, for any $t$-way interaction $T \not\in {\mathcal T}$, where ${\mathcal T}\subset \mathcal {I}_t$ and $|{\mathcal T}| = d$, we have $|\rho(A, T)\setminus \rho(A, {\cal T})|\geq \delta$. If we remove one $t$-way interaction from ${\cal T}$ to form a set of $t$-way interactions ${\cal T}'$, it follows that $T \not\in {\mathcal T}'$ and $|\rho(A, T)\setminus \rho(A, {\cal T}')|\geq |\rho(A, T)\setminus \rho(A, {\cal T})|\geq \delta$. Hence, $A$ is also a $(d-1, t, \delta)$-SDA$(N; k, v)$. The proof for the other conclusion is straightforward and is omitted here. □

The following result can be derived from the definition of $(d, t, \delta)$-SDA$(N; k, v)$ and Lemma 3.1.

Lemma 3.2. Suppose that $A$ is a $(d, t, \delta)$-SDA$(N; k, v)$ with $d\geq 1$. Then, $|\rho (A, T)|\geq d+\delta$ for any $t$-way interaction $T$.

Proof. The proof proceeds by mathematical induction on $d$. For $d = 1$, a $(1, t, \delta)$-SDA$(N; k, v)$ must be a $(0, t, \delta)$-SDA$(N; k, v)$ by Lemma 3.1. It has been proven that a $(0, t, \delta)$-SDA$(N; k, v)$ is equivalent to a CA$_\delta(N; t, k, v)$ ^[11]. This implies that $|\rho (A, T)|\geq \delta$ for any $t$-way interaction $T$. Suppose there exists a $t$-way interaction $T'$ with $|\rho (A, T')| = \delta$. Then, $T'$ is covered by $\delta$ rows of $A$. Select a certain row $R = (x_1, x_2, \ldots, x_k)$ from these $\delta$ rows. This row $R$ also covers $(^k_t)-1$ other $t$-way interactions different from $T'$. Since $t < k$, we have $(^k_t)-1 > 0$. Therefore, there exists at least one $t$-way interaction $T''$ ($\neq T'$) such that both $T'$ and $T''$ are covered by $R$. Hence, $|\rho(A, T') \setminus \rho(A, T'')| < \delta$, but since $T'\notin {T''}$, this contradicts the definition of a $(1, t, \delta)$-SDA. Therefore, $|\rho (A, T)|\geq 1+\delta$ for any $t$-way interaction $T$.

Now, assuming the conclusion holds for $d = n-1$, we show it holds for $d = n$. Let $A$ be an $(n, t, \delta)$-SDA$(N; k, v)$. Suppose $T$ is an arbitrary $t$-way interaction of $A$. By Lemma 3.1, an $(n, t, \delta)$-SDA must also be an $(n-1, t, \delta)$-SDA. By the induction hypothesis, we have $|\rho (A, T)|\geq n-1+\delta$. Now, assume for the sake of contradiction that $|\rho (A, T)| = n-1+\delta$ for some $t$-way interaction $T$. Select $n$ rows $R_i(1\leq i\leq n)$ from these $n-1+\delta$ rows of $A$ that cover $T$. Each row $R_i$ also covers $(^k_t)-1$ other $t$-way interactions different from $T$. Since $t < k$, we can select a $t$-way interaction $T_i$ from each row $R_i$ $(1\leq i \leq n)$ such that $T_i\neq T$. Write ${\mathcal T} = \{T_1, T_2, \cdots, T_n\}$. Then, $1\le |{\mathcal T}|\le n$. We would have $R_i\subseteq \rho(A, T) \cap \rho(A, {\mathcal T})$, while $T\not \in {\mathcal T}$. Thus, $|\rho(A, T)\setminus \rho(A, {\cal T})|\leq \delta-1 < \delta$. This contradicts the fact that $A$ is an $(h, t, \delta)$-SDA with $1 \le h \le n$. Therefore, $|\rho (A, T)|\ne n-1+\delta$. It follows that $|\rho (A, T)|\geq n+\delta = d+\delta$. Thus, by induction, the conclusion holds for all $d\geq 1$. □

It is noteworthy that the conclusion presented above can be inferred from Lemma 1 in ^[11], which provides a foundational understanding of the topic. Here, we provide an alternative proof based on the definition and properties of $(d, t, \delta)$-SDA. Combining Lemma 3.2, we can infer that a $(d, t, \delta)$-SDA does not exist if there exists a $t$-way interaction $T$ such that $|\rho(A, T)| < d+\delta$. Additionally, according to ^[10,11], a necessary condition for the existence of a $(d, t, \delta)$-SDA is that $d < v$ ^[10,11]. Specifically, if there exists a $t$-way interaction $T$ such that $|\rho(A, T)| = d+\delta$ in a $(d, t, \delta)$-SDA, it constitutes a necessary condition for its existence. This condition can be considered as a generalization of the previous one by setting $\delta = 1$.

Lemma 3.3. Let $A$ be a $(d, t, \delta)$-SDA$(N; k, v)$ with $d \geq 1$. If there exists a $t$-way interaction $T$ of $A$ such that $|\rho(A, T)| = d + \delta$, then $d < v - \delta + 1$.

Proof. Let $A = (a_{ij})_{N\times k}$ be a $(d, t, \delta)$-SDA$(N; k, v)$ with $d \geq 1$. Assume $d = v-\delta + 1$. Then, $d + \delta = v + 1$. Without loss of generality, suppose that $T = ((1, 0), (2, 0), \cdots, (t, 0))$ is covered by the first $(v + 1)$ rows $R_i$ of $A$, where $i = 1, 2, \cdots, v + 1$. Since the elements are drawn from a symbol set of size $v$ and $v+1$ exceeds the total number of elements, it follows that among the $v+1$ rows, there are $b$ rows $(2\leq b\leq v+1)$ with identical elements in the $(t+1)$th column. Without loss of generality, assume that $a_{R_1, t+1} = a_{R_2, t+1} = \cdots = a_{R_b, t+1}$. We now consider three cases:

Case 1. $2\leq b < d$.

Form $t$-way interaction $T_i = ((1, 0), (2, 0), \cdots, (t-1, 0), (t+1, a_{R_i, t+1}))$ for $i = 1, 2, \cdots, v+1$. Let ${\cal T} = \{T_b, T_{b+1}, \cdots, T_{d+1}\}$. It is clear that $1\leq |{\cal T}| \leq d$ and $T \not \in {\cal T}$. By the construction of ${\cal T}$, the rows $R_i$ also cover $T_i$, where $1\leq i\leq v+1$. Thus, $|\rho(A, {\cal T}\setminus T_b)|\geq d+1-b$ and $|\rho(A, T)\cap \rho(A, {\cal T})|\geq d+1-b+b = d+1$. Observe that $|\rho(A, T)\setminus \rho(A, {\cal T})| = |\rho(A, T)|-|\rho(A, T)\cap \rho(A, {\cal T})| \leq v + 1 - (d+1) = d+\delta-d-1 = \delta - 1 < \delta$. However, $A$ is a $(|{\cal T}|, t, \delta)$-SDA, as proved by Lemma 3.1.

Case 2. $2\leq b = d$.

Since $d+1\leq d+\delta = v+1$, we can form $t$-way interactions $T_i = ((1, 0), (2, 0), \cdots, (t-1, 0)$, $(t+1, a_{R_i, t+1}))$ for $i = d, d+1$. Define ${\cal T} = \{T_d, T_{d+1}\}$. Clearly, $2 = |{\cal T}| \leq d$, $T \not \in {\cal T}$, and $|\rho(A, T)\cap \rho(A, {\cal T})|\geq d+1$. However, $|\rho(A, T)\setminus \rho(A, {\cal T})| \leq v + 1 - (d+1) = v-d = \delta - 1 < \delta$. Nevertheless, $A$ is a $(2, t, \delta)$-SDA, as shown by Lemma 3.1.

Case 3. $b > d$.

Form a $t$-way interaction $T_d = ((1, 0), (2, 0), \cdots, (t-1, 0), (t+1, a_{R_b, t+1}))$. We deduce that $|\rho(A, T)\cap \rho(A, T_d)|\geq b$. Clearly, $T \not = T_d$, but $|\rho(A, T)\setminus \rho(A, T_d)| \leq v + 1 - b < v+1-d = \delta$. However, $A$ is a $(1, t, \delta)$-SDA, which is proved by Lemma 3.1. □

By applying Lemma 3.2, we can derive the following lower bound on the SDA numbers, which serves as our benchmark for measuring the optimality of $(d, t, \delta)$-SDA's.

Theorem 3.1. Let $t, k$, and $v$ be positive integers. Then,

Proof. Let $A$ be a $(d, t, \delta)$-SDA$(N; k, v)$ over $V$ and $N = (d, t, \delta)$-SDAN$(k, v)$. By definition, for any fixed $t$ columns $\{j_1, j_2, \cdots, j_t\}$ with $1\le j_1 < j_2 < \cdots < j_t \le k$, there exist exactly $v^t$ $t$-way interactions of $A$: $\{(j_r, x_r): 1\leq r\leq t \}$, where $(x_1, x_2, \cdots, x_t)$ runs over all the $t$-tuples from $V^t$. According to Lemma 3.2, we know that $|\rho (A, T)|\geq d+\delta$ for any $t$-way interaction $T$ of $A$. Therefore, each sub-array consisting of certain $t$ columns of $A$ must contain at least $(d + \delta)v^t$ rows. This implies that $N = (d, t, \delta)$-SDAN$(k, v) \geq (d+\delta)v^t$. □

When $\delta = 1$, a $(d, t, \delta)$-SDA is essentially a $(d, t)$-DA, as stated in Section $2$. Therefore, by setting $\delta = 1$ in Theorem 3.1, we can easily obtain the following corollary, which was first presented in ^[36].

Corollary 3.1. Let $t, k$, and $v$ be positive integers. Then,

It's worth noting that optimum $(d, t, \delta)$-SDAs that meet the lower bound Eq (3.1) are equivalent to super-simple OAs, which will be shown in next subsection. We say that an OA${_\lambda}(t, k, v)$ is super-simple if any $(t+1)$ columns of the array contain every $(t+1)$-tuple of symbols as a row at most once. We denote it by SSOA$_\lambda(t, k, v)$. Clearly, from this definition, it follows that an SSOA${_\lambda}(t, k, v)$ can only exist if $\lambda \leq v$.

Example 3.1. The transpose of the following array is an SSOA$_3(2, 4, 3)$ over ${\mathbb Z}_3$. As shown later, this OA is an optimum $(d, 2, \sigma)$-SDA array such that $(d, \sigma) = (1, 2)$ or $(2, 1)$.

3.2.   Combinatorial characterization of optimum $(d, t, \delta)$-SDAs

In this subsection, we aim to provide a combinatorial description of optimum $(d, t, \delta)$-SDAs using super-simple OAs. To establish the foundation for our ensuing discussion, we introduce the following lemma.

Lemma 3.4. Let $A$ be a $(d, t, \delta)$-SDA$(N; k, v)$. If $|\rho(A, T)| = d + \delta$ and $|\rho(A, T)\setminus \rho(A, {T_1, \cdots, T_d})| < \delta$, then there exists an $i\in I_d$ such that $|\rho(A, T_i)\cap\rho(A, T)|\geq 2$, where $T$ is an arbitrary $t$-way interaction and $T_i\in \{T_1, \cdots, T_d\}$.

Proof. From the set theory, we know that $|A\cap B| + |A\setminus B| = |A|$. Therefore, $|\rho(A, T)\cap \rho(A, \mathcal{T})| = |\rho(A, T)| - |\rho(A, T)\setminus \rho(A, \mathcal{T})| > d + \delta - \delta = d$. This implies that there are at least $d+1$ rows covering both $T$ and $\mathcal{T}$. The set of row indices is denoted by $I$. Since $\mathcal{T}$ contains $d$ $t$-way interactions, it follows that at least one $t$-way interaction $T_i$ appears at least twice within the set of row indices. Consequently, $|\rho(A, T_i)\cap\rho(A, T)|\geq 2$. □

The following theorem establishes the equivalence between optimal $(d, t, \delta)$-SDAs and SSOAs.

Theorem 3.2. Suppose that $t, k$, and $d$ are positive integers with $d\geq 1$. Then, an SSOA$_{d+\delta}(t, k, v)$ is equivalent to an optimum $(d, t, \delta)$-SDA$(N; k, v)$ meeting the lower bound Eq (3.1), namely, $N = (d+\delta)v^t$.

Proof. ($\Rightarrow$) Let $A$ represent a super-simple OA$_{d+\delta}(t, k, v)$. Suppose $T$ is any arbitrary $t$-way interaction of $A$. By definition, a super-simple OA has exactly $N = (d + \delta)v^t$ rows and $|\rho(A, T)| = d + \delta$. Consider a set ${\cal T} = \{T_1, T_2, \ldots, T_d\}$ containing $d$ $t$-way interactions of $A$, excluding $T$. We aim to demonstrate that $|\rho(A, T) \setminus \rho(A, \mathcal{T})| \geq \delta$. If this were not the case, there would exist at least one $T_j \in \mathcal{T}$ such that $|\rho(A, T_j) \cap \rho(A, T)| \geq 2$ by Lemma 3.4. This implies that there would be one $(t + 1)$-tuple of symbols occurring in certain $(t + 1)$ columns as the number of rows is more than once, since $T \neq T_j$. This contradicts the super-simple property of $A$.

($\Leftarrow$) Conversely, let $B$ be a $(d, t, \delta)$-SDA$((d+\delta)v^t; k, v)$. From Lemma 3.2, we know that $|\rho(A, T)| \geq d + \delta$ for any $t$-way interaction $T$ of $B$. This implies that each $t$-tuple of symbols occurs as a row at least $d + \delta$ times in any $t$ columns of $B$, and, hence, exactly $d + \delta$ times (since $B$ contains precisely $(d + \delta)v^t$ rows). Thus, we have proven that $B$ is an OA$_{d+\delta}(t, k, v)$. Next, we will prove that $B$ is super-simple.

If not, without loss of generality, suppose that $|\rho(A, T_{t+1})| = j$, where $T_{t+1} = ((1, 0), (2, 0), \cdots$, $(t-1, 0), (t, 0), (t+1, 0))$. It is evident that $j$ is less than $d+\delta+1$, since $B$ is an OA$_{d+\delta}(t, k, v)$. We denote the rows that cover $T_{t+1}$ by $S_j$, where $2\leq j\leq d+\delta$. Let $T' = ((1, 0), (2, 0), \cdots, (t-1, 0), (t, 0))$ and $T'' = ((1, 0), (2, 0), \cdots, (t-1, 0), (t+1, 0))$. Since $B$ is an OA$_{d+\delta}(t, k, v)$, $|\rho(A, T')| = d + \delta$, indicating that $T'$ is covered by $d + \delta$ rows of $B$. If $d = 1$, then $|\rho(A, T') \setminus \rho(A, T'')| = 1 + \delta - j < \delta - 1 < \delta$. This contradicts the assumption that $B$ is a $(1, t, \delta)$-SDA. For $d > 1$, we proceed with the proof by considering two cases.

Case 1. $d+1 > j$.

Select $d+1-j$ rows $R_i (1 \leq i \leq d+1-j)$ from the $d + \delta$ rows, excluding $S_j$. This is feasible since $d + 1 - j \leq d + \delta - j$. Each row $R_i$ also covers $(^k_t) - 1$ $t$-way interactions other than $T'$. As $t < k$ by assumption, we can select a $t$-way interaction $T_i$ from each row $R_i$ ($1 \leq i \leq d + 1 - j$) such that $T_i \ne T'$. Let ${\mathcal T} = \{T_1, T_2, \cdots, T_{d+1-j}, T''\}$. Then, $1 \le |{\mathcal T}| \le d$ and $|\rho(A, T')\cap \rho(A, {\mathcal T})|\geq d+1-j+j = d+1$. Thus, $|\rho(A, T')\setminus \rho(A, {\mathcal T})| = |\rho(A, T')|- |\rho(A, T')\cap \rho(A, {\mathcal T})|\leq d + \delta - (d + 1) = \delta - 1 < \delta$, but $T \not\in {\mathcal T}$. Consequently, $B$ is not a $(|{\mathcal T}|, t, \delta)$-SDA.

Case 2. $2\leq d+1\leq j$.

Since $T'' \subseteq T_{t+1}$, it follows that $|\rho(A, T'')| \geq j$. Observe that $|\rho(A, T') \setminus \rho(A, T'')| \leq d + \delta - (d + 1) = \delta-1 < \delta$. This contradicts the assumption that $B$ is a $(1, t, \delta)$-SDA.

The proof is completed.□

Let $\delta = 1$ in Theorem 3.2. This allows us to derive the following corollary, originally presented in ^[36].

Corollary 3.2. Suppose that $t$, $k$, and $d$ are positive integers. Then, an SSOA$_{d+1}(t, k, v)$ is equivalent to an optimum $(d, t)$-DA$(N; k, v)$ with $N = (d + 1) v^t$.

It should be noted that, as indicated by Theorem 3.2 and Corollary 3.2, SSOAs with index greater than one can be utilized to construct optimum DAs as well as optimum SDAs. Indeed, an SSOA$_\lambda(t, k, v)$ with $\lambda \geq 2$ can produce an optimum $(\lambda-1, t)$-DA$(N; k, v)$ with $N = \lambda v^t$. An optimum $(d, t, \delta)$-SDA$(N; k, v)$ with $N = \lambda v^t$ and $d+\delta = \lambda$ can be obtained from it. SSOAs with the same parameters can be applied to software system fault localization both in the presence and absence of outliers and nonresponses. The only difference is that, when outliers and nonresponses are present, the number of interaction faults that can be localized may be relatively smaller. From the theorem above, it follows that optimum SDAs are equivalent to SSOAs. The definition of SSOAs implies that the number of rows, $(d + \delta) v^t$, in an SSOA$_{d+\delta}(t, k, v)$ cannot exceed the total number of $(t+1)$-tuples of symbols, $v^{t+1}$. In other words, $(d + \delta) v^t \leq v^{t+1}$, which implies $d + \delta \leq v$. This observation aligns with the necessary conditions outlined in Lemma 3.3 for DAs with separation.

4.   Optimum SDAs

In this section, we will utilize several known SSOAs to derive optimum SDAs by using Theorem 3.2. Furthermore, we will present a construction based on difference schemes of strength $t$ with a specific prescribed property.

4.1.   Optimum SDAs from SSOAs

The existence of SSOA$_\lambda(t, k, v)$ has been fully established for the case where $t = 2$ and $k = 4$ in ^[17]. For the scenario with $t = 2$ and $k = 5$, the existence was delineated in ^[6,43]. Additionally, SSOAs for $t = 3$ and $k\leq 6$ were presented in earlier studies ^[39,40,41].

Lemma 4.1. ^[6,43] Let $\lambda \ge 2$ and $v = 2^{\alpha}3^{\beta} \cdot u \ge 4$, with $v \ne 6$, where $\alpha$ and $\beta$ are nonnegative integers and gcd$(u, 6)$ = 1. An SSOA$_{\lambda}(2, 5, v)$ exists for $\lambda \leq \Delta(v)$, where

Lemma 4.2. ^[40,41] Let $\lambda \ge 2$ and $v = 2^{\alpha} 3^{\beta} \cdot u \ge 2$, where $\alpha$ and $\beta$ are nonnegative integers and gcd$(u, 6)$ = 1. An SSOA$_{\lambda}(3, 5, v)$ exists, except possibly in the following cases:

(1) $v = 3u$ or $v = 3 \cdot 2^{\alpha} u$ with $\alpha \ge 3$ and $\lambda = v - 1$;

(2) $v = 6u$ and $\lambda \in \{v - 1, v - 5\}$;

(3) $v = 12u$ and $\lambda \in \{v - 1, v - 2\}$.

For $(t, k) \in \{(2, 4), (2, 5), (3, 5)\}$, the following results are derived using Theorem 3.2, Table 3, and Lemmas 4.1 and 4.2. We first establish the existence of optimum $(d, 2, \delta)$-SDAs for specific parameters.

Theorem 4.1. An optimum $(d, 2, \delta)$-SDA$((d+\delta)v^2;4, v)$ exists for any $d\geq 1$ and $\delta\geq 1$, where $d+\delta\leq v$.

Theorem 4.2. Let $v = 2^{\alpha}3^{\beta}\cdot u \ge 4, v\not = 6$ be two integers where $\alpha$ and $\beta$ are two nonnegative integers and gcd$(u, 6)$ = 1. For $d+\delta\leq \Delta(v)$, an optimum $(d, 2, \delta)$-SDA$((d+\delta)v^2;5, v)$ exists for any $d\geq 1$ and $\delta\geq 1$, where

Furthermore, we extend our results to cases involving $(d, 3, \delta)$-SDAs. Specifically, we provide the following theorem which also accounts for certain exceptional cases.

Theorem 4.3. An optimum $(d, 3, \delta)$-SDA$((d + \delta) v^3; 5, v)$ exists for any $d \geq 1$ and $\delta \geq 1$, where $d + \delta \leq v$, except possibly in the following cases, where gcd$(u, 6)$ = 1:

(1) $v = 3u$ or $v = 3 \cdot 2^{\alpha} u$ with $\alpha \ge 3$ and $d + \delta = v - 1$;

(2) $v = 6u$ and $d + \delta \in \{v - 1, v - 5\}$;

(3) $v = 12u$ and $d + \delta \in \{v - 1, v - 2\}$.

We now proceed to present more generalized findings that are applicable to any given value of $t$. The necessary SSOAs for these results are provided in Table 3.

Theorem 4.4. Suppose that $t\ge 1$ and $v\ge 2$ are integers. Then, for any $d\geq 1$ and $\delta\geq 1$, an optimum $(d, t, \delta)$-SDA$((d+\delta)v^t; t+1, v)$ exists, provided that $d+\delta\leq v$.

We now consider the scenario where $q$ is a prime power. The following theorem establishes the existence of optimum SDAs under these conditions.

Theorem 4.5. Let $q$ be a prime power and $d+\delta\leq q$, with $d\geq 1$ and $\delta\geq 1$. Then an optimum $(d, t, \delta)$-SDA$((d+\delta)q^t; q, q)$ exists, where $t+1 < q$. Moreover, if $q\geq 4$ is a power of $2$, then an optimum $(d, 2, \delta)$-SDA$((d+\delta)q^2;q+1, q)$ exists.

Proof. According to Theorem 3.2, our task is simplified to constructing the corresponding SSOAs. Fortunately, these required SSOAs are already outlined in Table 3.□

Finally, we extend our results to the case where $v$ is factored into distinct prime powers. The following theorem addresses this generalization.

Theorem 4.6. Suppose $v = q_1q_2\cdots q_s$ is a standard factorization of $v$ into distinct prime powers, and $k = \mathit{\mbox{min}}\{q_i:1\leq i\leq s\}$. If $q_i > t+1$ and $d+\delta \le v$, then there exists an optimum $(d, t, \delta)$-SDA$((d+\delta)v^t; k, v)$

Proof. The proof process is similar to that of Theorem 4.5 and, thus, we omit it here. □

4.2.   Optimum SDAs from difference matrices

In this subsection, we aim to construct optimum SDAs from difference schemes possessing a specific prescribed property. To describe the definition of a DM in a general manner, we denote $G$ as a finite Abelian group of order $v$ with its operation represented by addition throughout the following discussion. For $t\geq 1$, $G^t$ denotes the abelian group of order $v^t$ consisting of all $t$-tuples of elements from $G$ with the usual addition as the binary operation. $G^t_0$ refers to the subgroup of $G^t$ isomorphic to $G$, consisting of all elements of the form $(g, g, \cdots, g).$ The cosets of this subgroup in $G^t$ will be denoted by $G^t_i$, where $0\le i \le v^{t-1}-1$.

Definition 4.1. For given positive integers $t\ge 2$, $k$, and $v$, a $k \times \lambda v^{t-1}$ array $D$ with entries from $G$ of order $v$ is termed a difference scheme of strength $t$ and index $\lambda$, denoted as a DM$_\lambda(t, k, v)$, if every $t\times \lambda v^{t-1}$ sub-matrix of $D$ contains each coset $G^t_i$ ($0\le i \le v^{t-1}-1$) exactly $\lambda$ times.

The aforementioned notion was first formulated by Seiden ^[32] and was subsequently utilized to produce OAs of strength $t$. This concept was further studied by Hedayat et al. ^[19]. Note that a difference scheme of strength $2$ in Definition 4.1 is simply a $(v, k, \lambda)$-DM. This DM satisfies the property that all elements of $G$ appear exactly $\lambda$ times in the difference of any two distinct columns. Difference matrices were introduced in a seminal paper by Bose and Bush in the case strength $t = 2$ ^[1]. Bose and Bush introduced and studied these matrices to facilitate the construction of OAs. The definition of a difference matrix can easily be extended to non-Abelian groups. However, for the construction of SDAs discussed in this paper, this extension is of little use and is therefore omitted. The principal idea for the construction of OAs via DMs has received significant attention for the case $t$ = 2 (see ^[8,21]). It is evident that an OA$_\lambda(t, k, v)$ can be obtained from a DM$_\lambda(t, k, v)$ under the development of $D$. However, such an OA cannot be super-simple. To address this issue, we require a super-simple difference scheme of strength $t$.

Definition 4.2. A DM$_\lambda(t, k, v)$ of order $v$ over the group $G$ is said to be super-simple, denoted by SSDM$_\lambda(t, k, v)$, if, within any $(t+1)\times \lambda v^{t-1}$ sub-matrix of $D$, each coset $G^{t+1}_i$ appears no more than once, where $0\le i \le v^t-1$.

Example 4.1. The following array is an SSDM$_2(3, 4, 3)$ over ${\mathbb Z}_3$:

For $t = 2$, the notion of a super-simple $(v, k, \lambda)$-DM was introduced by Hartman ^[17]. Let $D = (d_{ij})_{4\times \lambda v}$ be a $(v, 4, \lambda)$-DM over the group $G$. $D$ is called super-simple, and it further satisfies the following condition: for any indices $r_1, r_2, r_3$ with $1\le r_1 < r_2 < r_3\le 4$ and any indices $j, j'$ with $1\leq j < j' \le \lambda v$, if $d_{r_2j}-d_{r_1j} = d_{r_2j'}-d_{r_1j'}$, then it must hold that $d_{r_3j}-d_{r_2j}\not = d_{r_3j'}-d_{r_2j'}$. We denote it by $(v, k, \lambda)$-SSDM. It is clear that $\lambda \leq v$ must hold whenever an SSDM$_\lambda(t, k, v)$ exists. Suppose that $D = (d_{ij})$ is an SSDM$_\lambda(t, k, v)$ over the group $G = \{g_0 = 0, g_1, g_2, \cdots, g_{v-1}\}$. For each column $(d_{1j}, d_{ij}, \cdots, d_{kj})^T$ of $D$, we form $v$ rows given by $C(j, u) = (d_{1j}+u, d_{2j}+u, \cdots, d_{kj}+u), u\in G$. These rows are then juxtaposed to form a $\lambda v^t\times k$ array $A$ over $G$, which is an SSOA$_\lambda(t, k, v)$. This approach is simple yet effective, as SSDMs are significantly smaller in size than the SSOAs that they induce, and constructing SSDMs directly is more feasible than constructing SSOAs directly. We state this as a lemma for convenient reference for later use.

Lemma 4.3. If an SSDM$_\lambda(t, k, v)$ over the group $G$ exists with $\lambda \geq 2$, then an SSOA$_\lambda(t, k, v)$ over the group $G$ also exists, and, therefore, an optimum $(d, t, \delta)$-SDA$(\lambda v^t; k, v)$ exists with $d+\delta = \lambda$ and $d\geq 1$.

Proof. Let $D$ be the given SSDM$_\lambda(t, k, v)$ over the group $G$. As explained previously, the generation of an SSDM naturally leads to the formation of SSOA$_\lambda(t, k, v)$. Consequently, by invoking Theorem 3.2, it follows that there exists a $(d, t, \delta)$-SDA$(\lambda v^t; k, v)$ satisfying the conditions $d+\delta = \lambda$ and $d\geq 1$. □

We will now present the existence of SSDMs. Initially, we have the following lemma.

Lemma 4.4. ^[15] A $(v, 4, 1)$-DM exists if, and only if, $v \geq 4$ and $v \not \equiv 2 \pmod 4$.

By applying Lemma 4.4 and following the proof of Theorem 3.13 presented in ^[34], we can establish the existence of the following SSDMs.

Lemma 4.5. For any integer $v \geq 4$, if $v \not \equiv 2 \pmod 4$, then there exists a $(v, 4, \lambda)$-SSDM, where the parameter $\lambda$ satisfies $\lambda \leq v$.

For the cases where $v = 2$ or $v = 3$, a $(v, 4, \lambda)$-SSDM is provided below, with the condition that $\lambda \leq v$.

Lemma 4.6. A $(v, 4, \lambda)$-SSDM exists for the pair $(v, \lambda)\in \{(2, 2), (3, 2), (3, 3)\}$.

Proof. A $(2, 4, 2)$-SSDM is presented as follows:

$(3, 4, \lambda)$-SSDM's for $\lambda = 2, 3$ are given below:

□

For the completeness of existence for $(v, 4, \lambda)$-SSDM's, we require the following product constructions, which were first stated in ^[34].

Lemma 4.7. If there exist a $(g, k, \lambda_1)$-SSDM over $G$ and a $(g', k, \lambda_2)$-SSDM over $G'$, then it follows that there exists a $(gg', k, \lambda_1\lambda_2)$-SSDM over $G\times G'$.

Lemma 4.8. A $(6, 4, \lambda)$-SSDM exists for $\lambda\in \{2, 4, 6\}$.

Proof. By Lemma 4.7, the existence of a $(6, 4, \lambda)$-SSDM is established for $\lambda = 4, 6$. The necessary ingredients for their construction are provided in Lemma 4.6. Additionally, an explicit $(6, 4, 2)$-SSDM is presented in the following array:

□

With the existence of SSDMs for order $6$ established, we now broaden our scope to investigate the existence of such DMs for $v\geq 10$ and $v \equiv 2 \pmod 4$.

Lemma 4.9. Let $v \geq 10$ be an integer. If $v \equiv 2 \pmod 4$, then a $(v, 4, \lambda)$-SSDM exists, where $\lambda$ is an even integer satisfying $\lambda \leq v$.

Proof. Let $v = 2(2t + 1)$ with $t\geq 2$. According to Lemma 4.5, it is known that a $(2t + 1, 4, \lambda)$-SSDM exists, where $\lambda\leq 2t+1$. Consequently, by applying Lemma 4.7, the conclusion holds since the $(2, 4, 2)$-SSDM is given in Lemma 4.6.□

While we have explored the existence of SSDMs for certain cases, it is also important to consider scenarios where such DMs do not exist. In particular, we now examine the nonexistence of DMs with specific parameter constraints.

Lemma 4.10. ^[13] Let $k \geq 3$ be an integer and $\lambda$ be an odd integer. Then, there is no $(v, k, \lambda)$-DM, when $v \equiv 2 \pmod 4$.

Combing Lemmas 4.5, 4.6, and 4.8–4.10, we can determine the existence of super-simple $(v, 4, \lambda)$-DM's as below.

Theorem 4.7. Let $v \geq 2$ be a positive integer with $\lambda \leq v$. Then, a $(v, 4, \lambda)$-SSDM exists if, and only if, $v \equiv 2 \pmod 4$ and $\lambda$ even, or $v\not \equiv 2 \pmod 4$.

It is notable that the existence of a $(v, 4, \lambda)$-DM was previously determined by Pan and Chang ^[30]. They established that a $(G, 4, \lambda)$-DM exists if, and only if, $\lambda$ is even, or $\lambda$ is odd and $G$ has no nontrivial cyclic Sylow $2$-subgroups, where $G$ is a nontrivial finite Abelian group and $\lambda > 1$ is an integer. In this paper, we completely determine the existence of $(v, 4, \lambda)$-SSDMs. We would like to remind readers again that SSOA$_\lambda(2, 4, v)$ has been completely solved, but only partial results can be obtained using Lemma 4.3 and Theorem 4.7. As described earlier, SSDMs have relatively small sizes.

Lemma 4.11. ^[2] Let $G$ be any group of order $v$. Then, there exists a $(v, p, 1)$-DM over $G$, where $p$ is the small prime power dividing $v$.

We begin by considering the construction of SSDMs over prime powers of strength $2$. The following theorem asserts the existence of such matrices for prime powers.

Theorem 4.8. Let $q$ be a prime power. Then, there exists a $(q, q, \lambda)$-SSDM, where $\lambda\leq q$.

Proof. Let $q = p^n$, where $n$ is a positive integer and $p$ is an odd prime. Let $\alpha$ be a primitive element of $GF_q$, meaning that GF$(q) = \{0, 1, \alpha, \alpha^2, \cdots, \alpha^{p^n-2}\}$. We define the matrices $A_s = (a_{xy}^s)$ for $x, y\in GF(q)$ and $s = 0, 1, 2, \cdots, \lambda-1$ as follows:

The matrix $A_0 = (a_{xy}^0)$ for $x, y \in \{0, 1, \alpha, \alpha^2, \cdots, \alpha^{p^n-2}\}$, represents the multiplication table of $GF(q)$ and forms a $(q, q, 1)$-DM by Lemma 4.11. It is also a $(q, q, 1)$-SSDM. Clearly, each $A_i$ for $i = 1, 2, \cdots, \lambda-1$ is a $(q, q, 1)$-DM. Let $D = (A_0, A_1, \cdots, A_{\lambda-1})$. Thus, $D$ is a $(q, q, \lambda)$-DM. Next, we prove that $D$ is super-simple. We start by showing that $D' = (A_m, A_n)$ is a $(q, q, 2)$-SSDM for $0\leq m < n\leq \lambda-1$. The proof depends on two cases based on the value of $m$.

Case 1. $m\not = 0$.

If $D'$ is not super-simple, then there exist $x_1, x_2, x_3, y, y'\in GF(q)$ with $x_1\not = x_2\not = x_3$ such that $a_{x_2y}^m-a_{x_1y}^m = a_{x_2y'}^n-a_{x_1y'}^n, a_{x_3y}^m-a_{x_2y}^m = a_{x_3y'}^n-a_{x_2y'}^n$. This leads to the following equations:

and

From Eqs (4.1) and (4.2), we deduce $y+\alpha^{m-1}(x_2+x_1) \equiv y'+\alpha^{n-1}(x_2+x_1) \pmod q$ and $y+\alpha^{m-1}(x_3+x_2) \equiv y'+\alpha^{n-1}(x_3+x_2) \pmod q$. This implies that $\alpha^{m-1}(x_3-x_2) \equiv \alpha^{n-1}(x_3-x_2)\pmod q$. Since $x_2, x_3\in GF(q)$ with $x_2\not = x_3$ and $\alpha$ is a primitive element, we conclude that $m = n$. However, $m\not = n$, which leads to a contradiction.

Case 2. $m = 0$.

In this case, we replace $\alpha^{m-1}$ with $0$ in both Eqs (4.1) and (4.2). Thus, we can conclude that $\alpha^{n-1}(x_3-x_2) \equiv 0 \pmod q$. Clearly, this conclusion does not hold since $\alpha$ is a primitive element and $x_2\not = x_3$.

The same argument can be applied to prove that $D$ is super-simple. If $p = 2$, the same reasoning can be used to prove the conclusion. □

We will provide an example to illustrate this theorem.

Example 4.2. Let $\alpha$ be a root of $f = x^2+x+2\in F_3[x]$. It is straightforward to verify that $\alpha$ is a primitive element of $F_{9}$ and we have the relations $\alpha^2 = 2\alpha+1, \alpha^3 = 2\alpha+2, \alpha^4 = 2, \alpha^5 = 2\alpha, \alpha^6 = \alpha+2$, and $\alpha^7 = \alpha+1$. The multiplication table for the finite field $F_9$ is as follows:

We replace the elements $a+b\alpha$ with $ab$, and, subsequently, three $(9, 9, 1)$-DM over ${\mathbb Z}_3\times {\mathbb Z}_3$ are derived. Notably, the second and third arrays can be generated through the application of the formula $xy+x^2$ and $xy+\alpha x^2$, respectively.

By juxtaposing the three arrays mentioned above, we can obtain a $(9, 9, 3)$-SSDM over ${\mathbb Z}_3\times {\mathbb Z}_3$.

We now delve into the results for $k = t+1$ under specific conditions.

Theorem 4.9. Let $v \geq 3$ be a positive integer. Then, an SSDM$_\lambda(t, t + 1, v)$ exists for $v\not \equiv 2 \pmod 4$ or $t$ odd.

Proof. By Theorem 4.1 in ^[19], a DM$(t, t + 1, v)$ exists over the group $G$ for $v\not \equiv 2 \pmod 4$ or $t$ odd. We denoted it by $D$. For each $h\in G$, let $D_h = (d_{ij}^h)$, where $d_{ij}^h = d_{ij}$ for $i = 1, 2, \cdots, t$ and $d_{ij}^h = d_{ij}+h$ for $i = t+1$. Clearly, $D_h$ is also a DM$(t, t + 1, v)$ over $G$ from the definition of a difference scheme. Define $D' = (D_{x_1} |D_{x_2}| \cdots|D_{x_\lambda})$, where $x_i(i = 1, 2, \cdots, \lambda)$ are mutually distinct elements in $G$. Then, $D'$ is the required SSDM. □

Further refining our results, we now consider the existence of SSDMs specifically for integers $v$ that are congruent to $1$ or $5 \pmod 6$. The following theorem demonstrates that under these conditions, SSDMs with strength $3$ can be constructed over the additive group $G$ of order $v$.

Theorem 4.10. Let $v \geq 5$ and $v \equiv 1$ or $5 \pmod 6$. Then, there exists an SSDM$_\lambda(3, 5, v)$ over the additive group of ${\mathbb Z}_v$.

Proof. By Lemma 3.3 in ^[23], a DM$(3, 5, v)$ exists over the additive group of ${\mathbb Z}_v$. We denote it by $D = (d_{ij})(i\in I_5, j\in I_{v^2})$. For each $h\in {\mathbb Z}_v$, define $D_h = (d_{ij}^h)$, where $d_{ij}^h = d_{ij}$ for $i = 1, 2, 3$ and $d_{ij}^h = d_{ij}+h$ for $i = 4, 5$. Clearly, $D_h$ is also a DM$(3, 5, v)$ over $G$ from the definition of a difference matrix. Define $D' = (D_{x_1} |D_{x_2}| \cdots|D_{x_\lambda})$, where $x_i(i = 1, 2, \cdots, \lambda)$ are mutually distinct elements in ${\mathbb Z}_v$. Then, $D'$ is the required SSDM. □

In the remainder of this subsection, we will establish the existence of $(v, 5, 2)$-SSDM. Initially, we will introduce some SSDMs of small order that will be utilized later.

Lemma 4.12. A $(v, 5, 2)$-SSDM exists for $v\in \{3, 4, 6, 8, 12, 16\}$.

Proof. A $(3, 5, 2)$-SSDM over ${\mathbb Z}_3$ is given below:

A $(4, 5, 2)$-SSDM is constructed over over ${\mathbb Z}_2\times {\mathbb Z}_2$.

A $(6, 5, 2)$-SSDM over ${\mathbb Z}_6$ is given below:

A $(8, 5, 2)$-SSDM over ${\mathbb Z}_2\times {\mathbb Z}_2\times {\mathbb Z}_2$ is given below:

A $(12, 5, 2)$-SSDM over ${\mathbb Z}_2\times {\mathbb Z}_6$ is as follows:

A $(16, 5, 2)$-SSDM over ${\mathbb Z}_2\times {\mathbb Z}_2\times Z_2\times Z_2$ is the juxtaposition of the following two arrays.

□

Theorem 4.11. Let $v = 2^{\alpha}3^{\beta}\cdot u \ge 2$, where $\alpha\geq 0$, $\beta\geq 0$, and gcd$(u, 6) = 1$. A $(v, 5, 2)$-SSDM exists for $v\geq 2$, except possibly when $v = 18, 2u$ with $u\not = 1$.

Proof. The proof process is divided into four cases based on the values of $\alpha$ and $\beta$.

Case 1. $\alpha = 0$ and $\beta\geq 0$.

By Theorem 4.8, a $(3^\beta, 3^\beta, 2)$-SSDM exists for $\beta\geq 2$. Consequently, a $(3^\beta, 5, 2)$-SSDM is guaranteed for $\beta\geq 2$. A $(3, 5, 2)$-SSDM is provided in Lemma 4.12, which further implies that a $(3^\beta, 5, 2)$-SSDM exists for $\beta\geq 1$. If $u = 1$, this conclusion remains valid. However, if $u\not = 1$, then a $(u, 5, 1)$-DM exists by Lemma 4.11. Then, by Lemma 4.7, a $(v, 5, 2)$-SSDM exists. When $\beta = 0$, a $(u, 5, 2)$-SSDM exists by Theorem 4.8 if $u$ has only one prime factor. If $u$ has two prime factors, $p_i$ and $p_j$, then by Lemma 4.8, a $(p_i^a, 5, 2)$-SSDM exists for any $a\geq 1$. Similarly, by Lemma 4.11, a $(p_j^b, 5, 1)$-DM exists for $b\geq 1$. Consequently, using Lemma 4.7, a $(u, 5, 2)$-SSDM can be constructed. A similar argument can be used to demonstrate the existence of a $(u, 5, 2)$-SSDM when $u$ has at least three prime factors.

Case 2. $\alpha = 1$ and $\beta\geq 1$.

When $\beta = 1$ and $u = 1$, a $(6, 5, 2)$-DM is provided by Lemma 4.12. For $\beta = 1$ and $u\not = 1$, Lemma 4.7 ensures the existence of a $(v, 5, 2)$-SSDM, with a corresponding $(u, 5, 1)$-DM given by Lemma 4.11. If $\beta \geq 2$ and $v \not = 18$, Lemma 4.7 also guarantees the existence of a $(v, 5, 2)$-SSDM, utilizing the $(3^{\beta-1}u, 5, 1)$-DM as given in Lemma 4.11.

Case 3. $\alpha = 2$ and $\beta\geq 0$.

A similar argument as in Case $2$ can be used to show that a $(v, 5, 2)$-SSDM exists for $v\not = 12$. The necessary $(4, 5, 2)$-SSDM is provided by Lemma 4.12. A $(12, 5, 2)$-SSDM is provided in Lemma 4.12.

Case 4. $\alpha\geq 3$ and $\beta\geq 0$.

We begin by proving the existence of a $(2^\alpha, 5, 2)$-SSDM. Lemma 4.12 provides the $(2^\alpha, 5, 2)$-SSDM for $\alpha = 2, 3, 4$. A $(2^{\alpha-2}, 5, 1)$-DM for $\alpha \geq 5$ is guaranteed by Lemma 4.11, thereby establishing the conclusion. A similar argument shows that a $(2^\alpha u, 5, 2)$-SSDM exists. As established in Case 1, a $(3^\beta, 5, 2)$-SSDM exists for $\beta \geq 1$. Additionally, a $(2^\alpha, 5, 1)$-DM for $\alpha \geq 3$ and a $(u, 5, 1)$-DM with $u \not = 1$ exist, as shown in Lemma 4.11. Therefore, a $(2^\alpha u, 5, 1)$-DM for $\alpha \geq 3$ exists. By Lemma 4.7, this leads to the existence of a $(2^\alpha 3^\beta u, 5, 2)$-SSDM. The proof is completed.□

5.   Conclusions

In conclusion, this paper has made significant contributions to the field of SDAs. We have established a comprehensive lower bound on the size of SDAs and demonstrated an equivalence between optimum SDAs and SSOAs. By exploiting the properties of SSOAs, we have systematically constructed numerous optimum SDAs from OAs and difference matrices. These SDAs are vital for detecting and tolerating noisy test outcomes in various practical applications.

The results presented offer significant insights into the design of efficient test suites for complex software systems. By utilizing SDAs, software testers can not only detect the presence of interaction faults but also quantify tolerance to unreliable test outcomes. This dual capability has substantial implications for improving the quality and reliability of software products through rigorous testing processes. Looking forward, there are several promising directions for future research. One key area is the extension of our construction methods to accommodate SDAs of higher strengths, which would further enhance their robustness and applicability in more complex and challenging scenarios. Additionally, exploring the potential application of SDAs beyond software testing, in domains where noise tolerance and interaction fault detection are critical, offers exciting opportunities for future investigation.

Author contributions

Ce Shi: computing, writing, literature survey, editing; Tatsuhiro Tsuchiya: computing and writing; Chengmin Wang: writing, literature survey, editing. All authors have read and agreed to the published version of the manuscript.

Use of Generative-AI tools declaration

The authors declare they have used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The first author's work was supported by NSFC grant 11301342 and Natural Science Foundation of Shanghai No. 17ZR1419900.

Conflict of interest

The authors declare that they have no conflict of interest.