Some structural properties of mixed orthogonal arrays and their irredundancy

1. Problem Statement and Motivation

Context:
Orthogonal Arrays (OAs) are fundamental combinatorial structures used in design of experiments, coding theory, and cryptography. Classical OAs are symmetric, meaning all columns share the same alphabet size ($q$). Mixed Orthogonal Arrays (MOAs), or asymmetric OAs, generalize this by allowing columns to have different alphabet sizes ($q^{n_1}, q^{n_2}, \dots, q^{n_s}$).

The Challenge:
While symmetric OAs have a well-established structural theory (including Euclidean duality, a unique global index $\lambda$, and classical bounds like Rao and Singleton), these tools fail in the mixed setting:

1. No Global Index: In MOAs, the "index" (frequency of occurrence of tuples) depends on the specific subset of columns chosen, rather than being a single global parameter.
2. Broken Duality: The standard Euclidean inner product is not well-defined for mixed alphabets, preventing a direct application of the duality between linear codes and linear OAs.
3. Quantum Applications: There is a growing need to construct Absolutely Maximally Entangled (AME) states and $t$-uniform states in heterogeneous quantum systems (where subsystems have different dimensions). These states correspond to Irredundant Mixed Orthogonal Arrays (IrMOAs), but a structural theory for constructing them in the mixed case is lacking.

Objective:
The paper aims to establish a robust structural theory for MOAs by:

• Deriving generalized bounds (Singleton-type).
• Introducing a trace duality to link MOAs with Error-Block Codes.
• Characterizing Irredundant MOAs (IrMOAs) and their equivalence to Maximum Distance Separable (MDS) codes, specifically for the construction of AME states.

---

2. Methodology and Framework

The authors develop a framework that bridges Mixed Orthogonal Arrays and $F_q$-linear Error-Block Codes.

A. Error-Block Codes and Partitions

The paper utilizes the concept of a partition $\pi = [n_1][n_2]\dots[n_s]$ of an integer $n$. The vector space $F_q^n$ is decomposed into a product of subspaces $V_1 \times \dots \times V_s$, where $V_i \cong F_q^{n_i}$.

• $\pi$-weight: The number of non-zero blocks in a vector.
• $\pi$-distance ($d_\pi$): The minimum $\pi$-weight of non-zero codewords.
• MDS Codes: Codes achieving the Singleton-type bound for error-block codes.

B. Trace Duality and Isomorphism ($\rho$)

To overcome the lack of Euclidean duality in mixed settings, the authors define a Trace Inner Product on the mixed space $F_{q^{n_1}} \times \dots \times F_{q^{n_s}}$:
$$\langle a, b \rangle_{Tr} = \sum_{i=1}^s \text{Tr}_i(a_i b_i)$$
where $\text{Tr}_i$ is the trace map from $F_{q^{n_i}}$ to $F_q$.

They introduce an isomorphism $\rho$ that maps the mixed space to the product of vector spaces over the base field $F_q$:
$$\rho: F_{q^{n_1}} \times \dots \times F_{q^{n_s}} \to F_q^{n_1} \times \dots \times F_q^{n_s}$$
This map $\rho$ converts an $F_q$-linear MOA into an $F_q$-linear error-block code. Crucially, under specific conditions (e.g., $q$ is even or $n_i$ is odd), $\rho$ preserves duality, mapping the trace dual of an MOA to the Euclidean dual of the corresponding error-block code.

C. Irredundancy

An MOA is irredundant (IrMOA) if any $M \times (s-t)$ subarray has pairwise distinct rows. This property is shown to be equivalent to the condition that the minimum Hamming distance $d_H \ge t+1$.

---

3. Key Contributions and Results

The paper presents three main structural results:

Result 1: Singleton-Type Bound and MDS Characterization

The authors establish a generalized Singleton-type bound for MOAs. For an MOA with parameters $(M, s, (q^{n_1}, \dots, q^{n_s}), t)$ and minimum Hamming distance $d_H$:
$$\prod_{i=1}^t q^{n_i} \le M \le \prod_{i=d_H}^s q^{n_i} \le \prod_{i=1}^{s-d_H+1} q^{n_i}$$

• MDS Definition: An MOA is MDS if it attains the upper bound $M = \prod_{i=d_H}^s q^{n_i}$.
• Index Characterization: They define the minimum index $\lambda_{min}$. They prove that for specific conditions (e.g., when the sum of block sizes matches), an MOA is MDS if and only if $\lambda_{min} = 1$.
• Almost-MDS: They characterize "almost-MDS" arrays where the Singleton defect is 1.

Result 2: Structural Equivalence via Trace Duality

The paper establishes a rigorous correspondence between $F_q$-linear MOAs and $F_q$-linear error-block codes:

• Theorem 5.4: If $C$ is an $F_q$-linear MOA of strength $t$, then its image $\rho(C)$ is an error-block code whose dual code has $\pi$-distance $d_\pi((\rho(C))^\perp) \ge t+1$. Equality holds if the strength is exactly $t$.
• Theorem 5.5: Conversely, if $C$ is an error-block code with dual distance $d_\pi(C^\perp)$, then $\rho^{-1}(C)$ is an MOA of strength $d_\pi(C^\perp) - 1$.
• Significance: This allows the construction of MOAs from known error-block codes and vice versa, transferring properties like MDS-ness and distance.

Result 3: Irredundant MOAs and AME States

The authors investigate IrMOAs, which are critical for quantum information.

• Extremal Case ($t = \lfloor s/2 \rfloor$): They prove that for an IrMOA with $t = \lfloor s/2 \rfloor$ and specific block size constraints, the array is MDS if and only if $\lambda_{min} = 1$.
• Equivalence to MDS Codes: An $F_q$-linear IrMOA with minimum index 1 (yielding AME states of minimal support) is equivalent to an $F_q$-linear error-block MDS code.
• Construction: They provide a method (Theorem 6.9) to construct IrMOAs from error-block codes. Specifically, $\rho^{-1}(C)$ is an IrMOA if and only if $d_\pi(C) \ge d_\pi(C^\perp)$.

---

4. Significance and Impact

1. Unification of Theories: The paper successfully extends the classical duality theory of symmetric OAs and linear codes to the mixed (asymmetric) setting. This fills a significant gap in combinatorial design theory.
2. Quantum Information Applications: The results provide a direct combinatorial pathway to construct Absolutely Maximally Entangled (AME) states in heterogeneous quantum systems (systems with qubits and qudits of different dimensions). Previous constructions were limited to homogeneous systems.
3. New Construction Tools: By linking MOAs to Error-Block Codes, the paper enables the use of the vast existing literature on block codes to generate new families of mixed orthogonal arrays, including those with minimal support (optimal for quantum secret sharing).
4. Refined Bounds: The introduction of the Singleton-type bound and the concept of minimum index $\lambda_{min}$ provides necessary and sufficient conditions for optimality in mixed settings, refining the understanding of extremal MOAs.

In summary, Bajalan et al. provide the missing structural "glue" for mixed orthogonal arrays, demonstrating that despite the loss of symmetry, a powerful duality exists via trace maps and error-block codes, with immediate and profound applications in quantum state engineering.