text:
\begin{document}

\title{On Optimal Finite-length Binary Codes of Four Codewords for Binary Symmetric Channels}

\author{Yanyan Dong and Shenghao Yang\\The Chinese University of Hong Kong, Shenzhen}

\maketitle

\begin{abstract}
  Finite-length binary codes of four codewords are studied for memoryless binary symmetric channels (BSCs) with the maximum likelihood decoding. For any block-length, best \emph{linear} codes of four codewords have been explicitly characterized, but whether linear codes are better than nonlinear codes or not is unknown in general. In this paper, we show that for any block-length, there exists an optimal code of four codewords that is either linear or in a subset of nonlinear codes, called \emph{Class-I} codes. Based on the analysis of Class-I codes, we derive sufficient conditions such that linear codes are optimal. For block-length less than or equal to $8$, our analytical results show that linear codes are optimal. For block-length up to $\numevnum$, numerical evaluations show that linear codes are optimal.
\end{abstract}

\section{Introduction}

A binary code of block length $n$ and codebook size $2^k$ is called an
$(n,k)$ code, which is said to be \emph{linear} if it is a subspace of
$\{0,1\}^n$.  Linear codes have been extensively studied in coding
theory. For memoryless binary symmetric channels (BSCs),
asymptotically capacity achieving linear codes with low
encoding/decoding complexity have been designed, for example polar
codes \cite{Arikan09}. For given $n$ and $k$, however, whether linear codes are optimal or
not among all $(n,k)$ codes for BSCs in terms of the maximum
likelihood (ML) decoding is a long-standing open problem, traced back
to the early days of information and coding theory~\cite{Slepian1956A,peterson72}.

For given $n$ and $k$, if perfect or quasi-perfect binary $(n,k)$ codes exist, they are optimal for BSC~\cite{peterson72}. For example, the optimal $(n,1)$ codes are
either perfect or quasi-perfect and hence are
known~\cite{Slepian1956A}. Readers can find more about optimal codes in \cite{Slepian1956A,peterson72}. More recently, Chen, Lin and Moser~\cite{chen2013optimal}
gave the first proof of the optimal binary codes of $3$ codewords for
any block length $n$.

In this paper, we study binary $(n,2)$ codes. The best
linear $(n,2)$ codes have been explicitly characterized for each block
length $n$ \cite{cordaro1967optimum,chen2013optimal}, and are
conjectured to be optimal among all $(n,2)$ codes in terms of the ML
decoding~\cite{chen2013optimal}. In this paper, we derive a general
approach for comparing the ML decoding performance of two $(n,2)$
codes with certain small difference. Based on this approach, we verify
that linear $(n,2)$ codes are optimal for a range of $n$.

In particular, we show that for any block-length $n$, there exists an
optimal $(n,2)$ code that is either linear or in a subset of nonlinear
codes, called \emph{Class-I} codes. Based on the analysis of Class-I
codes, we derive sufficient conditions such that linear codes are
optimal. For $n\leq 8$, our analytical results show that linear codes
are optimal. For $n$ up to $\numevnum$, numerical evaluations show
that linear codes are optimal, where the evaluation complexity is
$O(n^7)$. Moreover, most ML decoding comparison results obtained in
this paper about $(n,2)$ codes are \emph{universal} in the sense that
they do not depend on the crossover probability of the BSC.

In the remainder of this paper, we first formulate the problem and introduce our main results. In \S\ref{sec:formulation}, we outline a general approach for comparing the ML decoding performance of two codes, for which two special cases are used in this paper: two codes with only one codeword different in one bit (see \S\ref{sec:1col}) or in two bits (see \S\ref{sec:fliptwobits}). \S\ref{sec:classI} is dedicated to the analysis of Class-I codes, based on the results in \S\ref{sec:1col}.

\section{Problem Formulation and Main Results}

\subsection{Formulation of $(n,k)$ Codes}

An $(n,k)$ binary node $\mc C$ is a subset of $\{0,1\}^n$ of size $2^k$, and is said to be \emph{linear} if it is a subspace of $\{0,1\}^n$. Using the codewords of $\mc C$ as rows, we can form a $2^k\times n$ binary matrix $C$, which is used interchangeably with $\mc C$.
For $i=1,\ldots, 2^k$, let $\vv c_i$ be the $i$th row of $C$, i.e., a codeword of $\mc C$.

For $\vv x, \vv y\in \{0,1\}^n$, let $w(\vv x)$ be the \emph{Hamming weight} of $\vv x$ and let
$\vv x\oplus \vv y$ be the bit-wise exclusive OR of $\vv x$ and $\vv y$, so that $w(\vv x\oplus \vv y)$ is the Hamming distance between $\vv x$ and $\vv y$.
Let
\begin{equation*}
  d_{C}(\vv y) = \min_{\vv c \in \mc C} w(\vv c \oplus \vv y).
\end{equation*}

Consider the communication over a memoryless binary symmetric channel (BSC) with crossover probability $\epsilon$ ($0<\epsilon< \frac{1}{2}$). For a channel input $\vv{x} \in \{0,1\}^n$, the channel output is $\vv y \in \{0,1\}^n$ with probability
\begin{equation*}
  p(\vv y|\vv x) = (1-\epsilon)^{n-w(\vv x \oplus \vv y)}\epsilon^{w(\vv x\oplus \vv y)}.
\end{equation*}
Suppose an $(n,k)$ code $C$ is used for this BSC. The maximum-likelihood (ML) decoding rule decodes an output $\vv y$ to a code word $\vv c$ if

$w(\vv c\oplus \vv y) = d_{C}(\vv y)$,

where a tie is resolved arbitrarily.

Define
\begin{equation*}

  \alpha_d(C)=|\{\vv y\in \{0,1\}^n: d_C(\vv y)=d \}|,
\end{equation*}
which is the number of outputs $\vv y$ that is decoded to a codeword of distance $d$.
Note that the value $\alpha_d(C)$ does not depend on $\epsilon$.
The ({average}) correct decoding probability of $C$ is
\begin{equation}\label{eq:lambda}
  \ls_{C} = \frac{1}{|C|} \sum_{d=0}^n \alpha_d(C) (1-\epsilon)^{n-d}\epsilon^{d}.
\end{equation}
We say an $(n,k)$ code $C$ is \emph{better or no worse} than another $(n,k)$ code $C'$ if $\ls_{C}\geq \ls_{C'}$.
We say an $(n,k)$ code $C$ is \emph{optimal} if it is better than any other $(n,k)$ codes.
If valid for all $\epsilon$, a property of a code is said to be \emph{universal}.

\subsection{Main Results about $(n,2)$ Codes}
\label{sec:dec_formulation}

In this paper, we focus on $(n,2)$ codes,  which have four codewords. The columns of an $(n,2)$ code $C$ are of vectors in $\{0,1\}^{4}$.

We use $\bspan{i}^k$ to denote the binary vector of length $k$ associated with an integer $i\geq 0$. When the length of the vector is implied in the context, the superscript is omitted. For example,
\begin{equation*}

  \bspan{1}^4 =
  \begin{bmatrix}
    0 & 0 & 0 & 1
  \end{bmatrix}^\top, \quad
  \bspan{2}^4 =
  \begin{bmatrix}
    0 & 0 & 1 & 0
  \end{bmatrix}^\top.
\end{equation*}
We use $\{i\}_C$ to denote the index set of the columns of $C$ equal to $\bspan{i}$, and let $|i|_C$ be the size of $\{i\}_C$.
We may write $|i|_C$ as $|i|$ when the code $C$ is implied in the context.
For example, the $(7,2)$ code
\begin{equation*}
  C =
  \begin{bmatrix}
    0 & 0 & 0 & 0 & 0 & 0 & 0\\
    0 & 0 & 0 & 1 & 1 & 1 & 1\\
    0 & 1 & 1 & 0 & 0 & 1 & 1\\
    1 & 0 & 1 & 0 & 1 & 0 & 1
  \end{bmatrix}
\end{equation*}
has the $i$th column of type $\bspan{i}$ and $|i|=1$ for $i=1,\ldots,7$.

The analysis of the column types of $C$ has been used in
literature~\cite{cordaro1967optimum,chen2013optimal}.  Chen, Lin and Moser~\cite{chen2013optimal} compared different codes by induction in $n$, i.e., increasing one column a time. Here, we compare
two codes of the same length with difference in one or two positions in one codeword,
and we find that it is also convenient to use the column representation in our analysis.
The following facts about $(n,2)$ codes are
straightforward~\cite{cordaro1967optimum,chen2013optimal}. First,
codes with all-zero columns are not optimal. Second, flipping all the
bits in a column does not change the decoding performance. Third, row
and column permutations of $C$ do not affect the decoding performance.
Due to these facts, we only need to consider $C$ of $7$ types of the
columns: $\bspan{1},\bspan{2},\ldots,\bspan{7}$ for finding an optimal
code.

\begin{theorem} \label{thm:even}
  Consider an $(n,2)$ code $C$ of codewords $\vv c_1,\ldots,\vv c_4$ with $w(\vv c_s\oplus \vv c_t)$ even for certain $1\leq s\neq t \leq 4$, and with a column of type $\bspan{2^{4-s}}$.
  Let $C'$ be the code obtained by replacing a column of type $\bspan{2^{4-s}}$ of $C$ by $\bspan{2^{4-s}+2^{4-t}}$. Then, $\lambda_{C'}\geq \lambda_C$.
\end{theorem}
\begin{proof}
  See \S~\ref{sec:proof:even}.
\end{proof}

For example, suppose an $(n,2)$ code $C$ has a column $\bspan{1}$ and $w(\vv c_3\oplus \vv c_4)$ even. The above theorem says, if we replace a column of type $\bspan{1}$ of $C$ by $\bspan{3}$, the ML decoding performance is better.

\begin{fullversiononly}
\begin{corollary}\label{cor:twopo}
  Consider an $(n,2)$ code $C$ with $\sum_{i=1}^6|i|_C=n$. There exists a code $C'$ with $\lambda_{C'}\geq \lambda_C$ and $|1|_{C'} + |3|_{C'}+|5|_{C'}+|6|_{C'}=n$.
\end{corollary}
\begin{proof}
  In this proof, we write $|i|_C$ as $|i|$.
  Suppose at least two of $|1|, |2|, |4|$ are positive, since otherwise, the proof is done. We argue the case that $|1|$ and $|2|$ are positive. Other cases can be converted to this case by interchanging rows. Write
\begin{IEEEeqnarray*}{rCl}
  w(\vv c_2\oplus \vv c_3) & = & |2| + |3| + |4| + |5|\\
  w(\vv c_3\oplus \vv c_4) & = & |1| + |2| + |5| + |6|\\
  w(\vv c_2\oplus \vv c_4) & = & |1| + |3| + |4| + |6|.
\end{IEEEeqnarray*}
We claim that one of the above three weights must be even. For example, assume $w(\vv c_2\oplus \vv c_3)$ is odd. Then $|3|+|4|$ and $|2|+|5|$ are of different parity, so that one of $w(\vv c_3\oplus \vv c_4)$ and $w(\vv c_2\oplus \vv c_4)$ must be even.

Suppose $w(\vv c_2\oplus \vv c_3)$ is even. As $|2|$ is positive, Theorem~\ref{thm:even} implies a better code with $|2|$ smaller and $|6|$ bigger. Repeating the above argument, there exists a better code $C'$ where at most one of $|1|_{C'}, |2|_{C'}, |4|_{C'}$ is positive and $\sum_{i=1}^6|i|_{C'}=n$. The corollary is proved by properly interchanging rows of $C'$.
\end{proof}

\begin{corollary}\label{cor:onepo}
  Consider a non-Class-I, nonlinear $(n,2)$ code $C$ with $|1|_{C} + |3|_{C}+|5|_{C}+|6|_{C}=n$. There exists an either linear or Class-I code $C'$ with $\lambda_{C'}\geq \lambda_C$ and $|1|_{C'}<|1|_C$.
\end{corollary}
\begin{proof}
  In this proof, we write $|i|_C$ as $|i|$. Since $C$ is nonlinear, $|1|>0$.
  We claim that at least one of the following three weights are even:
\begin{IEEEeqnarray}{rCl}
  w(\vv c_1\oplus \vv c_4) & = & |1| + |3| + |5| \label{eq:3w:1}\\
  w(\vv c_3\oplus \vv c_4) & = & |1| + |5| + |6| \label{eq:3w:2}\\
  w(\vv c_2\oplus \vv c_4) & = & |1| + |3| + |6|, \label{eq:3w:3}.
\end{IEEEeqnarray}
When $|1|$ is odd, $|3|$, $|5|$ and $|6|$ are not of the same parity since $C$ is not of Class-I, which implies at least one of \eqref{eq:3w:1}, \eqref{eq:3w:2}, \eqref{eq:3w:3} is even. By Theorem~\ref{thm:even}, there is a better code $C_1$ with $|1|_{C_1}=|1|-1$ even and $|1|_{C_1} + |3|_{C_1}+|5|_{C_1}+|6|_{C_1}=n$.

When $|1|$ is even, if \eqref{eq:3w:1}, \eqref{eq:3w:2}, \eqref{eq:3w:3} are all odd, then $|3|+|5|$, $|5|+|6|$ and $|3|+|6|$ are all odd, which is not possible for any integers $|3|$, $|5|$, $|6|$.
Then at least one of \eqref{eq:3w:1}, \eqref{eq:3w:2}, \eqref{eq:3w:3} is even,
Theorem~\ref{thm:even} implies a better code $C_1$ with $|1|_{C_1}=|1|-1$ odd and $|1|_{C_1} + |3|_{C_1}+|5|_{C_1}+|6|_{C_1}=n$.

For both case, a better code with $|1|$ strictly smaller always exists if $C$ is non-Class-I, nonlinear.
By repeating the similar argument on $C_1$, we eventually obtain a better code $C'$ which
either has $|1|_{C'}=0$, i.e., linear or is of Class-I so that \eqref{eq:3w:1}, \eqref{eq:3w:2}, \eqref{eq:3w:3} are all odd.

\end{proof}
\end{fullversiononly}

\begin{theorem}
  \label{thm:odd}
  Consider an $(n,2)$ code $C$ with first two columns of the types $\bspan{1}$ (resp. $\bspan{2}$, $\bspan{4}$) and $\bspan{7}$. Let $C'$ be the code obtained by replacing the first two columns of $C$ with $\bspan{3}$ and $\bspan{5}$ (resp. $\bspan{3}$ and $\bspan{6}$, $\bspan{5}$ and $\bspan{6}$). Then $\lambda_{C'}\geq \lambda_{C}$.
\end{theorem}
\begin{proof}
  See \S~\ref{sec:fliptwobits}.
\end{proof}

Using the above two theorems, we can reduce the searching range for an optimal $(n,2)$ code.
Note that a linear $(n,2)$ code (subject to row interchanging) has $|3|+|5|+|6|=n$.

\begin{definition}\label{def:class1}
An $(n,2)$ code $C$ is of \emph{Class-I} if $|1|$ is odd, $|3|,|5|,|6|$ are of the same parity, and $|1|+|3|+|5|+|6|=n$.
\end{definition}

\begin{theorem}\label{thm:two}
  An optimal $(n,2)$ code exists in the set formed by all the linear codes and Class-I codes.

\end{theorem}
\begin{fullversiononly}
\begin{proof}
  Consider an arbitrary $(n,2)$ code $C$. As column flipping does not change the ML decoding performance, we consider a code $C_1$ with $\sum_{i=1}^7|i|=n$ obtained by column flipping of $C$. We then discuss $C_1$ in two cases.

  If $0<|7|\leq |1|+|2|+|4|$ in $C_1$, by Theorem~\ref{thm:odd}, there exists a code $C_2$ with $\lambda_{C_2} \geq \lambda_{C_1}$ and $\sum_{i=1}^6|i|=n$ obtained by replacing, one-by-one, pairs of columns of types $\bspan{7}$ and $\bspan{2^s}$ ($s=0,1,2$).
Following Corollary~\ref{cor:twopo}, there exists code $C_3$, no worse than $C_2$, where $|1|+ |3|+ |5|+|6|=n$. Then by Corollary~\ref{cor:onepo}, there exists an either linear or Class-I code $C_4$ such that $\lambda_{C_4} \geq \lambda_{C_3}$.

If $|1|+|2|+|4|< |7|$ in $C_1$, by Theorem~\ref{thm:odd}, there exists a better code $C_2'$ with $|1|+|2|+|4|=0$. By flipping columns, we can obtain a code $C_3'$ of the same performance of $C_2'$ that has $|1|>0$ and $|1|+|3|+|5|+|6|=n$. Again, by Corollary~\ref{cor:onepo}, the proof is completed.
\end{proof}
\end{fullversiononly}

We have the following properties of Class-I codes.

\begin{theorem}\label{thm:11}
  Let $C$ be a Class-I $(n,2)$ code with $|1|_C=1$. Let $C'$ be the code obtained by replacing the $\bspan{1}$ column of $C$ by $\bspan{s}$, where $s= \argmin_{i = 3,5,6}|i|_C$. Then $\lambda_{C'}\geq \lambda_{C}$.
\end{theorem}
\begin{proof}
  See \S~\ref{sec:11}.
\end{proof}

In the above theorem, code $C'$ is linear.

\begin{theorem}\label{thm:301}
  Let $C$ be a Class-I $(n,2)$ code with $\min_{i = 3,5,6}|i|_C = 0$ or $1$. Let $C'$ be the code obtained by replacing one $\bspan{1}$ column of $C$ by $\bspan{s}$, where $s\in\{3,5,6\}$ has $|s|_C=0$ or $1$. Then $\lambda_{C'}\geq \lambda_{C}$.
\end{theorem}

\begin{fullversiononly}
\begin{proof}
  See \S~\ref{sec:301}
\end{proof}
\end{fullversiononly}

The above analysis enables us to obtain the following sufficient condition about the optimality of linear codes.

\begin{theorem}\label{thm:ccs}
  Fix a block length $n$. If for any Class-I $(n,2)$ code $C$, there exists an $(n,2)$ code $C'$ such that $|1|_{C'}<|1|_C$, $|1|_{C'}+|3|_{C'}+|5|_{C'}+|6|_{C'} = n$ and $\lambda_{C} \leq \lambda_{C'}$, then linear $(n,2)$ codes are optimal.
\end{theorem}
\begin{fullversiononly}
\begin{proof}
  Assume that all optimal $(n,2)$ codes are nonlinear. By Theorem~\ref{thm:two}, there must exist an optimal $(n,2)$ code $C$ that is Class-I. By the condition of the theorem,
  there exists an optimal code $C'$ such that $|1|_{C'}< |1|_C $ and $|1|_{C'}+|3|_{C'}+|5|_{C'}+|6|_{C'} = n$. If $|1|_{C'}=0$, then $C'$ is linear and we get a contradiction to the assumption that all optimal $(n,2)$ codes are nonlinear.
  If $C'$ is Class-I, we repeat the above argument. If $C'$ is non-Class-I and nonlinear, then by Corollary~\ref{cor:onepo}, there exists an optimal code $C''$ with $|1|_{C''}<|1|_{C'}$ that is either linear or Class-I. If $C''$ is linear, we get a contradiction to the assumption. If $C''$ is Class-I, we can repeat the above argument. As $|1|_C$ is finite, the process will eventually stop with an optimal linear code, i.e., a contradiction to the assumption that all optimal $(n,2)$ codes are nonlinear.
\end{proof}
\end{fullversiononly}

\begin{corollary}\label{cor:n8}
  For $n\leq 8$, linear $(n,2)$ codes are optimal.
\end{corollary}
\begin{fullversiononly}
\begin{proof}
  Fix $n\leq 8$. For a Class-I $(n,2)$ code with $|1| = 1$, by Theorem~\ref{thm:11}, there exists a better linear code. For a Class-I $(n,2)$ code $C$ with $|1|\geq 3$, we have $|3|+|5|+|6|\leq 5$ which implies $\min\{|3|, |5|, |6|\}\leq 1$. By Theorem~\ref{thm:301},
we have $\lambda_{C} \leq \lambda_{C'}$ for the $(n,2)$ code $C'$ obtained by replacing one $\bspan{1}$ column of $C$ by $\bspan{s}$, where $s\in\{3,5,6\}$ with $|s|_C=0$ or $1$. By Theorem~\ref{thm:ccs}, linear $(n,2)$ codes are optimal for $n\leq 8$.
\end{proof}
\end{fullversiononly}

For a general block length $n$, if we can verify the condition of Theorem~\ref{thm:ccs}, then there exists an optimal $(n,2)$ code that is linear.
For each Class-I $(n,2)$ code $C$, we can compare it with the code $C'$ obtained by replacing one $\bspan{1}$ column of $C$ by $\bspan{s}$ with $s=\argmin_{i=3,5,6} |i|_C$.
See an algorithm for verifying the optimality of linear $(n,2)$ codes in \S~\ref{sec:comp}, where the evaluation complexity is $O(n^7)$. We have verified that for $n \leq \numevnum$, linear codes are optimal.

\section{An Approach of Comparing two $(n,2)$ Codes}
\label{sec:formulation}

We further define some notations. Let $C$ be an $(n,2)$ code with the $j$th codeword/row $\vv c_j$, $j=1,\ldots,4$. Denote
\begin{equation}\label{eq:di}
  d_j(\vv y) = w(\vv c_j \oplus \vv y).
\end{equation}
For a binary vector $\vv y$, denote $(\vv y)_i$ or $y_i$ as the $i$th entry of $\vv y$. For example, the $3$rd entry of $\bspan{2}^4$ is $(\bspan{2}^4)_3=([0\ 0\ 1\ 0]^\top)_3=1$.

For $i=0,1,\ldots,15$, define $w_i(\vv y) = \sum_{j\in \{i\}_C}  y_j$ for $\vv y \in \{0,1\}^n$.
When $\vv y$ is clear from the context, we write $w_i = w_i(\vv y)$.

For a vector $\vv y\in \{0,1\}^n$, we can rewrite $d_j(\vv y)$ defined in \eqref{eq:di} as
\begin{equation}\label{eq:d}
  d_j(\vv y) = \sum_{i=0}^{15}\left[|i|/2 + (-1)^{(\bspan{i}^4)_j}(w_i-|i|/2)\right].
\end{equation}
We also write $d_j = d_j(\vv y)$ when $\vv y$ is clear from the context.
For example, for $C$ of columns of types only $\bspan{1},\bspan{2},\ldots,\bspan{7}$,
\begin{IEEEeqnarray}{rCl}
  d_1(\vv y) & = & w_1+w_2+w_3+w_4+w_5+w_6+w_7, \label{eq:d1}\\
  d_2(\vv y) & = & w_1+w_2+w_3+\overline{w_4}+ \overline{w_5}+\overline{w_6}+\overline{w_7}, \label{eq:d2} \\
  d_3(\vv y) & = & w_1+\overline{w_2}+\overline{w_3}+ w_4+w_5+\overline{w_6}+\overline{w_7}, \label{eq:d3} \\
  d_4(\vv y) & = & \overline{w_1}+w_2+\overline{w_3}+ w_4+\overline{w_5}+w_6+\overline{w_7}, \label{eq:d4}
\end{IEEEeqnarray}
where $\overline{w_i} = |i|_C - w_i$.

We compare $C$ with another
$(n,2)$ code $C'$ obtained by modifying $C$ as follows.
Let $\mc O$ be a nonempty, proper subset of $\{1,2,3,4\}$
and let $\mc P$ be its complement, which is also nonempty.
Let $C'$ be the code obtained by
flipping the first $t$ bits of $\vv c_i$ for each $i\in \mc P$.

Denote by $\vv c'_i$ the $i$th codeword/row of $C'$, $i=1,\ldots,4$.
For $\vv y \in \{0,1\}^n$, let $f_t(\vv y)$ be the vector obtained by
flipping the first $t$ bits of $\vv y$.  We see that
$\vv c_i'=\vv c_i$ for $i\in \mc O$ and $\vv c_i' = f_t(\vv c_i)$ for
$i\in \mc P$.

Denote by
$\vv s_{\tau}$, $\tau = 1,2,\ldots,t$ the $\tau$th column of
$C$.  For $\vv y \in \{0,1\}^n$, let
\begin{equation}\label{eq:dprim}
  d_i'(\vv y) = d_i(\vv y) + \sum_{\tau=1}^t (-1)^{(\vv s_{\tau})_i} (\overline{y_\tau}- y_\tau),
\end{equation}
where $ \overline{y_\tau} = y_\tau\oplus 1$.
For a nonempty subset $\mc S \subset \{1,\ldots, 4\}$, let
\begin{equation*}
  d_{\mc S}(\vv y)  =  \min_{i\in \mc S} d_i(\vv y) \ \ \text{and}\ \
  d_{\mc S}'(\vv y)  =  \min_{i\in \mc S} d_i'(\vv y).
\end{equation*}
We have
\begin{IEEEeqnarray}{rCl}
  d_C(\vv y) & = & \min\{d_{\mc O}(\vv y), d_{\mc P}(\vv y)\}, \label{eq:dc} \\
  d_{C'}(\vv y) & = &  \min\{d_{\mc O}(\vv y), d_{\mc P}'(\vv y)\}, \label{eq:dcp} \\
  d_{C'}(f_t(\vv y)) & = & \min\{d_{\mc O}(f_t (\vv y)), d_{\mc P}'(f_t(\vv y))\} \nonumber\\
  & = & \min\{d_{\mc O}'(\vv y), d_{\mc P}(\vv y)\}. \label{eq:dcpf}
\end{IEEEeqnarray}

Our approach to compare the ML decoding performance of $C$ and $C'$ is based on a pair of partitions $\{\mc Y_i,i=1,\ldots,i_0\}$ and $\{\mc Y_i',i=1,\ldots,i_0\}$ of $\{0,1\}^n$, where $i_0$ indicates the number of subsets in each partition. This pair of partitions satisfies the following properties: 1) for each $i$, $|\mc Y_i| = |\mc Y_i'|$, and 2) for each $i$, there exists an one-to-one and onto mapping $g_i:\mc Y_i \rightarrow \mc Y_i'$  such that one of the following conditions holds:
\begin{enumerate}
\item for all $\vv y \in \mc Y_i$, $d_C(\vv y) = d_{C'}\left(g_i(\vv y)\right)$;
\item for all $\vv y \in \mc Y_i$, $d_C(\vv y) < d_{C'}\left(g_i(\vv y)\right)$;
\item for all $\vv y \in \mc Y_i$, $d_C(\vv y) > d_{C'}\left(g_i(\vv y)\right)$.
\end{enumerate}
Such a pair of partitions exists. For example, when $i_0=2^n$, $\mc Y_i=\mc Y_i' = \{\bspan{i}^n\}$ for $i=0,1,\ldots,i_0-1$ form a pair of partitions satisfying the desired properties. But this example does not help to simplify the problem.
For the two special cases used to prove Theorem~\ref{thm:even} and~\ref{thm:odd}, there exists such a pair of partitions with $i_0=5$.

In the following discussion,

we write $\min\{a,b\}$ as $a \land b$.
For a function $g:\{0,1\}^n\rightarrow \mathbb{R}$, we write $\{\vv y \in \{0,1\}^n: g(\vv y) \geq 0\}$ as $\{g\geq 0\}$ to simplify the notations.

\section{Change of one Column}
\label{sec:1col}

In this section, we study how the ML decoding performance is affected after changing one column of an $(n,2)$ code.

\subsection{General Results}
\label{sec:gen}

Consider an $(n,2)$ code $C$ with the first column $\bspan{s}$, $0\leq s \leq 15$. Let $C'$ be the code formed by changing the first column of $C$ to $\bspan{s'}$. Following the notations in \S\ref{sec:formulation}, $\mc O$ is the set of index $j$ such that $(\bspan{s})_j = (\bspan{s'})_j$, and $\mc P$ is the set of index $j$ such that $(\bspan{s})_j \neq (\bspan{s'})_j$. Assume $s'\neq s$ and $s'\neq 15-s$, and hence both $\mc O$ and $\mc P$ are nonempty.

In this case, $d_i'$ defined in \eqref{eq:dprim} becomes
\begin{equation}\label{eq:d1di}
  d_i'(\vv y) = d_i(\vv y) + (-1)^{(\bspan{s})_i}(\overline{y_1} - y_1).
\end{equation}
Consider an example with
$s=1$ and $s'=3$. Now $\mc O=\{1,2,4\}$ and $\mc P=\{3\}$. Substituting $\bspan{1}^4$ into \eqref{eq:d1di},
\begin{IEEEeqnarray*}{rCl}
	d_1'(\vv y)&=& d_1(\vv y) - y_1 + \overline{y_1}, \label{eq:s1d1}  \\
	d_2'(\vv y)&=& d_2(\vv y) - y_1 + \overline{y_1},  \\
	d_3'(\vv y)&=& d_3(\vv y) - y_1 + \overline{y_1},  \\
	d_4'(\vv y)&=& d_4(\vv y) + y_1 - \overline{y_1}. \label{eq:s1d4}
\end{IEEEeqnarray*}
and hence
\begin{IEEEeqnarray}{rCl}
  d_{\mc O}(\vv y) & = & d_1 \land d_2 \land d_4,  \label{eq:op1}\\
  d_{\mc P}(\vv y) & = & d_3, \\
  d_{\mc O}'(\vv y) & = & [(d_1\land d_2)- y_1 + \overline{y_1}]\land (d_4 + y_1 - \overline{y_1}), \\
  d_{\mc P}'(\vv y) & = & d_3 - y_1 + \overline{y_1}. \label{eq:op4}
\end{IEEEeqnarray}

We are ready to form the partitions.
Define the following $5$ subsets of $\{0,1\}^n$:
\begin{IEEEeqnarray*}{rCl}
  \mc Y_1 & = & \{ d_{\mc O} \leq d_{\mc P} < d_{\mc P}' \} \cup \{ d_{\mc O} \leq d_{\mc P}' \leq d_{\mc P}, d_{\mc O}' \leq d_{\mc P}' \}, \\
  \mc Y_2 & = & \{ d_{\mc P} \leq d_{\mc P}', d_{\mc P} < d_{\mc O}\} \cup  \{ d_{\mc P}' < d_{\mc P} \leq d_{\mc O}, d_{\mc P} \leq d_{\mc O}'\}, \\
  \mc Y_3 & = & \{d_{\mc P}' = d_{\mc O}' < d_{\mc P} = d_{\mc O}\}, \IEEEyesnumber \label{eq:y3}  \\
  \mc Y_4 & = & \{d_{\mc P} = d_{\mc P}' = d_{\mc O} < d_{\mc O}' \}, \\
  \mc Y_5 & = & \{ d_{\mc P}' = d_{\mc O} < d_{\mc O}' = d_{\mc P} \}. \IEEEyesnumber \label{eq:y5}
\end{IEEEeqnarray*}

For $i=2,4,5$, define
\begin{IEEEeqnarray*}{rCl}
  \mc Y_i' & = & \left\{f_1(\vv y):\vv y\in \mc Y_i\right\},
\end{IEEEeqnarray*}
where function $f_1$ (defined in \S\ref{sec:formulation}) flips the first bit of a binary vector.
The next lemma shows that both $\{\mc Y_i, i=1,\ldots,5\}$ and $\{\mc Y_1, \mc Y_2', \mc Y_3, \mc Y_4', \mc Y_5'\}$ are partitions of $\{0,1\}^n$ and satisfy the desired properties described in \S\ref{sec:formulation}.

\begin{lemma}\label{lemma:1}
For the $(n,2)$ codes $C$ and $C'$ formulated above,  both $\{\mc Y_1, \mc Y_2, \mc Y_3, \mc Y_4, \mc Y_5\}$ and $\{\mc Y_1, \mc Y_2', \mc Y_3, \mc Y_4', \mc Y_5'\}$ are partitions of $\{0,1\}^n$.
  Moreover,
  \begin{enumerate}
  \item For $\vv y \in \mc Y_1$, $d_C(\vv y) = d_{C'}(\vv y)=d_{\mc O}$;
  \item For $\vv y \in \mc Y_2$, $d_C(\vv y) = d_{C'}(\vv y') = d_{\mc P}$ where $\vv y' \triangleq f_1(\vv y)\in \mc Y_2'$;
  \item For $\vv y \in \mc Y_3$, $d_C(\vv y) = d_{\mc P} = d_{C'}(\vv y)+1=d_{\mc P}'+1$;
  \item For $\vv y \in \mc Y_4$, $d_C(\vv y) = d_{\mc O} = d_{C'}(\vv y')=d_{\mc P}$ where $\vv y'\triangleq f_1(\vv y)\in \mc Y_4'$;
  \item For $\vv y \in \mc Y_5$, $d_C(\vv y) +1 = d_{\mc O}+1 = d_{C'}(\vv y')=d_{\mc P}$ where $\vv y'\triangleq f_1(\vv y)\in \mc Y_5'$.
  \end{enumerate}
\end{lemma}
\begin{proof}
  See Appendix~\ref{app:proofs}.
\end{proof}

Now we move on to compare $\ls_{\mc C}$ and $\ls_{\mc C'}$ as defined in \eqref{eq:lambda}.
Define for $i=1,\ldots, 5$ and $d=0,1,\ldots,n$,
\begin{equation}\label{eq:10}
  \alpha_d^i(C)= |\{\vv y\in \mc Y_i: d_{C}(\vv y) = d\}|.
\end{equation}
As $\{\mc Y_1, \mc Y_2, \mc Y_3, \mc Y_4, \mc Y_5\}$ is a partition of $\{0,1\}^n$, we have
\begin{equation*}
  \alpha_d(C) = \sum_{i=1}^5 \alpha_d^i(C).
\end{equation*}

By the definition of $\mc Y_3$ and $\mc Y_5$, $\alpha_0^3(C) = 0$ and $\alpha_n^5(C)=0$.

\begin{theorem}\label{the:1}
  For two $(n,2)$ codes $C$ and $C'$ with only one column different, $\ls_{\mc C'} \geq \ls_{\mc C}$ if and only if
  \begin{IEEEeqnarray*}{rCl}
    \sum_{d=1}^n[\alpha_d^3(C)-\alpha_{d-1}^5(C)] \left(\frac{\epsilon}{1-\epsilon}\right)^{d-1} \geq 0.
  \end{IEEEeqnarray*}

\end{theorem}
\begin{proof}
  See Appendix~\ref{app:proofs}.
\end{proof}

\begin{corollary}\label{cor:1}
  For two $(n,2)$ codes $C$ and $C'$ with only one column different, $\ls_{\mc C'} \geq \ls_{\mc C}$ if for $d=1,\ldots, n$,
  \begin{equation*}
   \sum_{i=1}^d\alpha_{i}^3(C) \geq \sum_{i=0}^{d-1}  \alpha_{i}^5(C).
 \end{equation*}

\end{corollary}
\begin{proof}
  See Appendix~\ref{app:proofs}.
\end{proof}

If we can compare $C$ and $C'$ based on Corollary~\ref{cor:1}, their relation is \emph{universal} in the sense that it does not depend on~$\epsilon$.

\subsection{Proof of Theorem~\ref{thm:even}}
\label{sec:proof:even}

Now we give a proof of Theorem~\ref{thm:even}.

  As interchanging rows/columns does not change the performance of $C$, we only consider the following case when proving the theorem: $C$ has the first column $\bspan{1}$ and $w(\vv c_3\oplus \vv c_4)$ is even. Let $C'$ be the code obtained by replacing the first column of $C$ by $\bspan{3}$. Substituting $s=1$ and $s'=3$ to the discussion in \S\ref{sec:gen}, we have $\mc O=\{1,2,4\}$ and $\mc P=\{3\}$, and hence
  \begin{equation*}
    \mc Y_5 = \{d_{3}'  =  d_{\{1,2,4\}} < d_{3} = d_{\{1,2,4\}}'\}.
  \end{equation*}

Assume $\mc Y_5$ is nonempty and fix $\vv y \in \mc Y_5$.
  As $d_{3}'(\vv y) = d_3(\vv y) - y_1 + \overline{y_1}$, we have $y_1=1$.
  Further, due to
\begin{IEEEeqnarray*}{rCl}
  d_{\{1,2,4\}}(\vv y) & = & d_1 \land d_2 \land d_4, \\
  d_{\{1,2,4\}}'(\vv y) & = & (d_1-1) \land (d_2-1) \land (d_4+1),
\end{IEEEeqnarray*}
we have $d_{\{1,2,4\}} = d_4$ and hence $d_3 = d_4 + 1$.
By \eqref{eq:d},
\begin{IEEEeqnarray*}{rCl}
  \IEEEeqnarraymulticol{3}{l}{d_3(\vv y) + d_4(\vv y)} \\
   & = &
   \sum_{i}\left[|i|/2 + (-1)^{(\bspan{i})_3}(w_i-|i|/2)\right] +
    \sum_{i}\left[|i|/2 + (-1)^{(\bspan{i})_4}(w_i-|i|/2)\right] \\
  & = & \sum_{i:(\bspan{i})_3\neq (\bspan{i})_4} |i| +
   2 \sum_{i:(\bspan{i})_3=(\bspan{i})_4} \left[\frac{|i|}{2} + (-1)^{(\bspan{i})_3}\left(w_i - \frac{|i|}{2}\right)\right] \\
  & = & w(\vv c_3\oplus \vv c_4) + 2 \sum_{i:(\bspan{i})_3=(\bspan{i})_4} \left[\frac{|i|}{2} + (-1)^{(\bspan{i})_3}\left(w_i - \frac{|i|}{2}\right)\right].
\end{IEEEeqnarray*}
As $w(\vv c_3\oplus \vv c_4)$ is even, we see that $d_3+d_4$ is even, which is a contradiction to $d_3 = d_4+1$. Therefore, $\mc Y_5 = \emptyset$ and hence by Corollary~\ref{cor:1}, $\lambda_{C'}\geq \lambda_{C}$.

\section{Analysis of Class-I Codes}
\label{sec:classI}

Recall the definition of Class-I codes in Definition~\ref{def:class1}.
In this section, we consider a Class-I $(n,2)$ code $C$ with the first column $\bspan{1}$. Let $C'$ be the code obtained by replacing the first column of $C$ to $\bspan{3}$. The ML decoding performance of $C$ and $C'$ can be compared using the approach introduced in \S\ref{sec:gen}.

\subsection{Characterizations of $\mc Y_3$ and $\mc Y_5$}

Guided by Theorem~\ref{the:1} and Corollary~\ref{cor:1}, we first study $\mc Y_3$ and $\mc Y_5$ defined in \eqref{eq:y3} and \eqref{eq:y5}.

\begin{lemma}\label{lemma:35}
  For a Class-I $(n,2)$ code $C$ with the first column $\bspan{1}$ and $C'$ obtained by replacing the first column of $C$ to $\bspan{3}$,
\begin{IEEEeqnarray*}{rCl}
  \mc Y_3 & = & \{y_1 = 1, d_4 \geq d_1\land d_2 = d_3\}, \label{eq:c13} \\
  \mc Y_5 & = & \{y_1 = 1, d_1\land d_2 \geq d_4+2 = d_3+1\}. \label{eq:c15}
\end{IEEEeqnarray*}
\end{lemma}
\begin{fullversiononly}
\begin{proof}
  For code $C$ and $C'$ defined above, we have \eqref{eq:op1} -- \eqref{eq:op4}.
For $\vv y \in \mc Y_3$, $d_3 - y_1 + \overline{y_1}  < d_3$ implies $y_1 = 1$, and $d_3 = d_1 \land d_2 \land d_4$ and $d_3-1 = [(d_1\land d_2) - 1]\land (d_4+1)$ together implies $d_1\land d_2 \leq d_4$ and $d_3 = d_1\land d_2$.

For $\vv y \in \mc Y_5$, $d_3 - y_1 + \overline{y_1}  < d_3$ implies $y_1 = 1$, and $d_3 - 1 = d_1 \land d_2 \land d_4$ and $d_3 = [(d_1\land d_2) - 1]\land (d_4+1)$ together implies $d_4+1 \leq (d_1\land d_2) - 1$ and $d_3-1=d_4$.
\end{proof}
\end{fullversiononly}
\subsubsection{Characterization of $\alpha_i^3$}

For $\vv y \in \mc Y_3$, by Lemma~\ref{lemma:1}, $d_C(\vv y ) = d_3$.
By \eqref{eq:d1} -- \eqref{eq:d4} and Lemma~\ref{lemma:35}, we have the following necessary and sufficient condition for $\vv y \in \mc Y_3$ with $d_C(\vv y) = i$:  $y_1  =  1$ and
\begin{IEEEeqnarray*}{rCl}
  w_1 + \overline{w_3} & = & i - w_5 - \overline{w_6},  \\
  w_1 - \overline{w_1} & \leq & \overline{w_5} + w_6 - w_5 - \overline{w_6}, \\
  w_3 - \overline{w_3} & = & w_5 + \overline{w_6} - (w_5+ w_6)\land (\overline{w_5} + \overline{w_6}).
\end{IEEEeqnarray*}
We discuss two cases according to $w_5+w_6<\overline{w_5} + \overline{w_6}$ or not.

Define $\mc Y_{3}^{A}(i)$ as the collection of $\vv y$ satisfying $y_1=1$ and
\begin{IEEEeqnarray}{rCl}
  w_5+ w_6 & < & (|5|+|6|)/2,  \label{eq:3yc1} \\
  w_1+w_5 & = & i - (|3|+|6|)/2, \label{eq:3yc2}\\
  w_1 + w_5 - w_6 & \leq & (|1|+|5|-|6|)/2, \label{eq:3yc3} \\
 w_3 +  w_6& = & {(|3|+|6|)}/{2}. \label{eq:3yc4}
\end{IEEEeqnarray}
We have
\begin{equation*}
  |\mc Y_3^{A}(i)| =  \sum_{\substack{w_1\geq 1, w_3,w_5,w_6:\\\eqref{eq:3yc1},\eqref{eq:3yc2},\eqref{eq:3yc3},\eqref{eq:3yc4}}} \binom{|1|-1}{w_1-1}\binom{|3|}{w_3} \binom{|5|}{w_5}\binom{|6|}{ w_6}.
\end{equation*}
Define $\mc Y_{3}^{B}(i)$ as the collection of $\vv y$ satisfying $y_1=1$ and
\begin{IEEEeqnarray}{rCl}
  w_5+ w_6 & \geq & {(|5|+|6|)}/{2}, \label{eq:3yd1} \\
   w_1 + \overline{w_6}  & = & i - {(|3|+|5|)}/{2}, \label{eq:3yd2} \\
  w_1 + w_5 - w_6 & \leq & {(|1|+|5|-|6|)}/{2}, \label{eq:3yd3} \\
  w_3 - w_5 & = & {(|3|-|5|)}/{2}. \label{eq:3yd4}
\end{IEEEeqnarray}
We have
\begin{equation}\label{eq:y3b}
  |\mc Y_3^{B}(i)| =  \sum_{\substack{w_1\geq 1, w_3,w_5,w_6:\\\eqref{eq:3yd1},\eqref{eq:3yd2},\eqref{eq:3yd3},\eqref{eq:3yd4}}} \binom{|1|-1}{w_1-1}\binom{|3|}{w_3} \binom{|5|}{w_5}\binom{|6|}{ w_6}.
\end{equation}
We see that $\alpha_i^3 = |\mc Y_3^{A}(i)| + |\mc Y_3^{B}(i)|$.

\subsubsection{Characterization of $\alpha_i^5$}
For $\vv y \in \mc Y_5$, by Lemma~\ref{lemma:1}, $d_C(\vv y ) = d_3-1$.
By \eqref{eq:d1} -- \eqref{eq:d4} and Lemma~\ref{lemma:35}, we have the following necessary and sufficient condition for $\vv y \in \mc Y_5$ with $d_C(\vv y) = i$:   $y_1  =  1$ and
\begin{IEEEeqnarray*}{rCl}
  w_1 + \overline{w_3} & = & i+1 - w_5 - \overline{w_6},\\
  w_1 - \overline{w_1} & = & \overline{w_5} + w_6 - w_5 - \overline{w_6} +1,\\
  w_3 - \overline{w_3} & \geq & w_5 + \overline{w_6} - (w_5+ w_6)\land (\overline{w_5} + \overline{w_6}) + 1,
\end{IEEEeqnarray*}
which can be further simplified as $y_1 = 1$ and
\begin{IEEEeqnarray}{rCl}
  w_3 & = & {(n+|3|-1)}/{2} - i, \label{eq:5yc1} \\
  w_1 + w_5 - w_6  & = & {(|1|+|5|-|6|+1)}/{2}, \label{eq:5yc2} \\
  w_3 + w_6 & \geq & {(|3|+|6|)}/{2}+1,  \label{eq:5yc3}\\
  w_3 - w_5 & \geq & {(|3|-|5|)}/{2}+1.  \label{eq:5yc4}
\end{IEEEeqnarray}
Hence
\begin{IEEEeqnarray*}{rCl}
  \alpha_i^5 & = & \sum_{\substack{w_1\geq 1, w_3, w_5, w_6:\\\eqref{eq:5yc1},\eqref{eq:5yc2},\eqref{eq:5yc3},\eqref{eq:5yc4}}} \binom{|1|-1}{w_1-1}\binom{|3|}{w_3}\binom{|5|}{w_5}\binom{|6|}{w_6}.
\end{IEEEeqnarray*}

\subsection{Class-I Codes with $|1|=1$}
\label{sec:11}

Following the discuss in the last subsection, we consider the special case with $|1|=1$, and prove Theorem~\ref{thm:11} for the case $|3| = \min\{|3|, |5|, |6|\}$. For other cases, we can perform row interchanging and column bit flipping to convert the problem to this case.

When $|1|=1$, $w_1 = 1$. Using the characterization in the last subsection, we have
\begin{IEEEeqnarray*}{rCl}
  \sum_{i=0}^{d-1}\alpha_i^5 & = & \sum_{\mathcal{W}_5} \binom{|3|}{w_3}\binom{|5|}{\frac{|5|-|6|}{2}+w_6}\binom{|6|}{w_6}

  \IEEEyesnumber\IEEEeqnarraynumspace \label{eq:115}
\end{IEEEeqnarray*}
where
\begin{equation}\label{eq:w5}
  \mathcal{W}_5 = \left\{\substack{\eqref{eq:5yc3},\\ \eqref{eq:5yc2}+\eqref{eq:5yc4}, \\ w_3\geq \frac{n+|3|+1}{2}-d,\\ 0\leq w_3 \leq |3|, 0\leq w_6\leq |6|  }   \right\} = \left\{ \substack{w_3 + w_6 \geq \frac{|3|+|6|}{2}+1,  \\ w_3-w_6 \geq \frac{|3|-|6|}{2}+1,\\ w_3\geq \frac{n+|3|+1}{2}-d,\\ 0\leq w_3 \leq |3|, 0\leq w_6\leq |6|  } \right\}.
\end{equation}

Similarly,
\begin{IEEEeqnarray*}{rCl}
  \IEEEeqnarraymulticol{3}{l}{\sum_{i=1}^d\alpha_i^3 \geq  \sum_{i=1}^d |\mc Y_3^B(i)|} \\
  & = & \sum_{\mathcal{W}_3} \binom{|3|}{w_3}\binom{|5|}{\frac{|5|-|3|}{2}+w_3}\binom{|6|}{w_6}\\
  & = & \sum_{\mathcal{W}_3'}  \binom{|3|}{\frac{|3|-|6|}{2}+w_6'}\binom{|5|}{\frac{|5|-|6|}{2}+w_6'}\binom{|6|}{\frac{|6|-|3|}{2}+w_3'}
  \IEEEyesnumber \IEEEeqnarraynumspace\label{eq:113}
\end{IEEEeqnarray*}
where
\begin{IEEEeqnarray*}{rCl}
  \mathcal{W}_3 & = &  \left\{\substack{\eqref{eq:3yd1}+\eqref{eq:3yd4},\\ \eqref{eq:3yd3}+\eqref{eq:3yd4}, \\ w_6\geq \frac{n+|6|+1}{2}-d ,\\ 0\leq w_3 \leq |3|, 0\leq w_6\leq |6| }\right\} = \left\{\substack{w_3+w_6\geq \frac{|3|+|6|}{2} \\ w_3-w_6\leq \frac{|3|-|6|-1}{2} \\ w_6\geq \frac{n+|6|+1}{2}-d ,\\ 0\leq w_3 \leq |3|, 0\leq w_6\leq |6| }\right\}, \\
  \mathcal{W}_3' & = & \left\{ \substack{w_3'+w_6'\geq \frac{|3|+|6|}{2}, \quad w_3'-w_6' \geq \frac{|3|-|6|+1}{2} \\ w_3'\geq \frac{n+|3|+1}{2}-d,\\ \frac{|3|-|6|}{2}\leq w_3'\leq \frac{|3|+|6|}{2}, \frac{|6|-|3|}{2}\leq w_6'\leq \frac{|3|+|6|}{2}   }\right\},
\end{IEEEeqnarray*}
and  \eqref{eq:113} is
obtained by change of variables $w_3'-\frac{|3|}{2} = w_6 - \frac{|6|}{2}$ and $w_6'-\frac{|6|}{2} = w_3 - \frac{|3|}{2}$.

\begin{fullversiononly}
We show that  $\mathcal{W}_5 \subset \mathcal{W}_3'$.
Due to $|3|\leq |6|$, we have $\frac{|3|-|6|}{2}\leq 0$ and $\frac{|3|+|6|}{2}\geq |3|$. For $(w_3,w_6)\in \mathcal{W}_5 $, we have $w_3 + w_6 \geq \frac{|3|+|6|}{2}+1$,  $w_3-w_6 \geq \frac{|3|-|6|}{2}+1$ and $0\leq w_3\leq |3|$, which implies $\frac{|6|-|3|}{2}+1\leq w_6\leq \frac{|3|+|6|}{2}-1$. Thus
\begin{equation*}
\frac{|3|-|6|}{2}\leq w_3\leq \frac{|3|+|6|}{2}, \quad\frac{|6|-|3|}{2}\leq w_6\leq \frac{|3|+|6|}{2} ,
\end{equation*}
showing
$(w_3,w_6)\in \mathcal{W}_3'$.

By Lemma~\ref{lemma:inequation} in Appendix~\ref{app:lemma},
\end{fullversiononly}
for $(w_3,w_6)\in \mathcal{W}_5$, we have
\begin{equation*}
  \binom{|3|}{w_3}\binom{|6|}{w_6} \leq \binom{|3|}{\frac{|3|-|6|}{2}+w_6} \binom{|6|}{\frac{|6|-|3|}{2}+w_3}.
\end{equation*}
Comparing \eqref{eq:115} and \eqref{eq:113},
we obtain $\sum_{i=1}^d\alpha_i^3 \geq \sum_{i=0}^{d-1}\alpha_i^5$ for any $d=1,\ldots,n$. By Corollary~\ref{cor:1}, $\ls_{\mc C'} \geq \ls_{\mc C}$, proving Theorem~\ref{thm:11}.

\begin{fullversiononly}

\subsection{Class-I Codes with $|1|$ odd, $|3|=0,1$}
\label{sec:301}

Here we give a proof of Theorem~\ref{thm:301} for the case $|3| = \min\{|3|, |5|, |6|\}$. Otherwise, we can perform row interchanging and column bit flipping (which do not change the ML decoding performance) so that $C$ satisfies the condition.

\subsubsection{$|3|=0$} When $|3|=0$, we have $w_3=0$ and $n$ is odd. By~\eqref{eq:5yc1}, $\alpha_i^5=0$ if $i\neq \frac{n-1}{2}$. So when $d < \frac{n+1}{2}$, $\sum_{i=0}^{d-1} \alpha_i^5=0$ and hence $\sum_{i=1}^d \alpha_i^3\geq \sum_{i=0}^{d-1} \alpha_i^5$;
when $d\geq \frac{n+1}{2}$,
\begin{IEEEeqnarray}{rCl}
  \sum_{i=0}^{d-1} \alpha_i^5 & = & \alpha_{\frac{n-1}{2}}^5 \nonumber \\
  &=&\sum_{\substack{w_1\geq 1, \eqref{eq:5yc2}+\eqref{eq:5yc3},\eqref{eq:5yc3},\\  w_5=w_6-w_1+\frac{|1|+|5|-|6|+1}{2},\\
      w_5\leq \frac{|5|}{2}-1}} \binom{|1|-1}{w_1-1}\binom{|5|}{w_5}\binom{|6|}{w_6}\nonumber\\
  &\leq & \sum_{\substack{w_1\geq 1, \eqref{eq:5yc2}+\eqref{eq:5yc3},\eqref{eq:5yc3}}} \binom{|1|-1}{w_1-1}\binom{|5|}{\frac{|5|}{2}}\binom{|6|}{w_6}\nonumber\\
  & = & \sum_{\substack{w_1\geq 1,w_6\geq \frac{|6|}{2}+1,\\w_6-w_1\leq \frac{|6|-|1|-3}{2}}} \binom{|1|-1}{w_1-1}\binom{|5|}{\frac{|5|}{2}}\binom{|6|}{w_6}, \IEEEeqnarraynumspace \label{eq:sa_2}

\end{IEEEeqnarray}
where \eqref{eq:5yc2} $+$ \eqref{eq:5yc3} is $w_6-w_1\leq \frac{|6|-|1|-3}{2}$.
Substituting $w_1'=|1|-w_1 + 1$ into \eqref{eq:sa_2}, we obtain
\begin{equation}
  \label{eq:5}
  \alpha_{\frac{n-1}{2}}^5 \leq \sum_{\substack{1\leq w_1'\leq |1|,w_6\geq \frac{|6|}{2}+1,\\ w_1'\leq \frac{|1|+|6|-1}{2}-w_6}} \binom{|1|-1}{w_1'-1}\binom{|5|}{\frac{|5|}{2}}\binom{|6|}{w_6}
\end{equation}

When $d\geq \frac{n+1}{2}$, we further have
\begin{IEEEeqnarray}{rCl}
  \sum_{i=1}^d \alpha_i^3&\geq& \sum_{i=1}^{\frac{n+1}{2}} \alpha_i^3\nonumber \\
  &\geq & \sum_{i=1}^{\frac{n+1}{2}}|\mc Y_3^B(i)|\nonumber\\
  &=&   \sum_{\substack{w_1\geq 1, \eqref{eq:3yd1}+\eqref{eq:3yd4},\\
      \eqref{eq:3yd3}+\eqref{eq:3yd4}, w_1-w_6\leq \frac{|1|-|6|+1}{2}}} \binom{|1|-1}{w_1-1} \binom{|5|}{\frac{|5|}{2}}\binom{|6|}{ w_6}\nonumber\\
  &=&  \sum_{\substack{w_1\geq 1, w_6\geq \frac{|6|}{2},\\
      w_1\leq \frac{|1|-|6|-1}{2}+w_6}} \binom{|1|-1}{w_1-1} \binom{|5|}{\frac{|5|}{2}}\binom{|6|}{ w_6}, \label{eq:a3xs}
\end{IEEEeqnarray}
where \eqref{eq:3yd1} $+$ \eqref{eq:3yd4} is $w_6\geq \frac{|6|}{2}$ and 	\eqref{eq:3yd3} $+$ \eqref{eq:3yd4} is  $w_1-w_6\leq \frac{|1|-|6|}{2}$, which is equivalent to $w_1-w_6\leq \frac{|1|-|6|-1}{2}$ as $|1|-|6|$ is odd.

As $\frac{|1|-|6|-1}{2}+w_6 \geq \frac{|1|+|6|-1}{2}-w_6$ when $w_6\geq \frac{|6|}{2}$, comparing the RHS' of \eqref{eq:5} and \eqref{eq:a3xs},
we have $\sum_{i=1}^d \alpha_i^3\geq \sum_{i=0}^{d-1} \alpha_i^5$ for $d\geq \frac{n+1}{2}$. By Corollary~\ref{cor:1}, $\ls_{\mc C'} \geq \ls_{\mc C}$, proving the case when $|3|=0$.

\subsubsection{$|3|=1$} When $|3|=1$, we have $w_3=0\text{ or }1$, $|5|$ and $|6|$ are odd, and $n$ is even.
In \eqref{eq:5yc1}, $w_3=1$ when $i=\frac{n}{2}-1$, and hence
\begin{IEEEeqnarray}{rCl}
  \alpha_{\frac{n}{2}-1}^5
  &=&\sum_{\substack{w_1\geq 1, w_6\geq \frac{|6|+1}{2}, \eqref{eq:5yc1} + \eqref{eq:5yc4},\\  w_5=w_6-w_1+\frac{|1|+|5|-|6|+1}{2},\\
			w_5\leq \frac{|5|-1}{2}}} \binom{|1|-1}{w_1-1}\binom{|5|}{w_5}\binom{|6|}{w_6}\nonumber\\
	&\leq & \sum_{\substack{w_1\geq 1, w_6\geq \frac{|6|+1}{2}, \eqref{eq:5yc1}+\eqref{eq:5yc4}}} \binom{|1|-1}{w_1-1}\binom{|5|}{\frac{|5|+1}{2}}\binom{|6|}{w_6}\nonumber\\
	&=& \sum_{\substack{w_1\geq 1, w_6\geq \frac{|6|+1}{2},\\w_6-w_1\leq \frac{|6|-|1|-2}{2}}} \binom{|1|-1}{w_1-1}\binom{|5|}{\frac{|5|+1}{2}}\binom{|6|}{w_6},\label{eq:of1} \\
        & = & \sum_{\substack{|1|\geq w_1'\geq 1, w_6\geq \frac{|6|+1}{2},\\w_1'\leq \frac{|6|+|1|}{2}-w_6}} \binom{|1|-1}{w_1'-1}\binom{|5|}{\frac{|5|+1}{2}}\binom{|6|}{w_6}.\IEEEeqnarraynumspace \label{eq:of2}

\end{IEEEeqnarray}
where \eqref{eq:5yc1} $+$ \eqref{eq:5yc4} is $w_6-w_1\leq \frac{|6|-|1|-2}{2}$, and \eqref{eq:of2} is obtained by
substituting $w_1'=|1|-w_1+1$ into \eqref{eq:of1}.

In \eqref{eq:5yc1}, $w_3=0$ when $i=\frac{n}{2}$, and hence
\begin{IEEEeqnarray}{rCl}
  \alpha_{\frac{n}{2}}^5&=&\sum_{\substack{w_1\geq 1, w_6\geq \frac{|6|+3}{2}, \eqref{eq:5yc2}+\eqref{eq:5yc4},\\  w_5=w_6-w_1+\frac{|1|+|5|-|6|+1}{2},\\
      w_5\leq \frac{|5|-3}{2}}} \binom{|1|-1}{w_1-1}\binom{|5|}{w_5}\binom{|6|}{w_6}\nonumber\\
  &\leq & \sum_{\substack{w_1\geq 1, w_6\geq \frac{|6|+3}{2}, \eqref{eq:5yc2}+\eqref{eq:5yc4}}} \binom{|1|-1}{w_1-1}\binom{|5|}{\frac{|5|-1}{2}}\binom{|6|}{w_6}\nonumber\\
  &=&  \sum_{\substack{w_1\geq 1, w_6\geq \frac{|6|+3}{2},\\w_6-w_1\leq \frac{|6|-|1|}{2}-2}} \binom{|1|-1}{w_1-1}\binom{|5|}{\frac{|5|-1}{2}}\binom{|6|}{w_6}  \label{eq:of3} \\
  & = & \sum_{\substack{|1|\geq w_1'\geq 1, w_6\geq \frac{|6|+3}{2},\\w_1'\leq -w_6+ \frac{|6|+|1|-2}{2}}} \binom{|1|-1}{w_1'-1}\binom{|5|}{\frac{|5|-1}{2}}\binom{|6|}{w_6} . \label{eq:of4}

\end{IEEEeqnarray}
where \eqref{eq:5yc2} $+$ \eqref{eq:5yc4} means $w_6-w_1\leq \frac{|6|-|1|}{2}-2$, and \eqref{eq:of4} is obtained by substituting $w_1'=|1|-w_1+1$ into \eqref{eq:of3}.

Following~\eqref{eq:y3b}, we have
\begin{IEEEeqnarray}{rCl}
&&	\left|\{w_3=1\}\cap \left(\mathop\cup_{i\leq \frac{n}{2}} \mc Y_3^B(i)\right)\right|\nonumber\\
&=&  \sum_{\substack{w_1\geq 1,\\\eqref{eq:3yd1}+\eqref{eq:3yd4},\ \eqref{eq:3yd3}+\eqref{eq:3yd4},\\ w_1-w_6\leq \frac{n}{2}-\frac{1+|5|}{2}-|6|}} \binom{|1|-1}{w_1-1} \binom{|5|}{\frac{|5|+1}{2}}\binom{|6|}{ w_6}  \nonumber\\
&=&  \sum_{\substack{w_1\geq 1,w_6\geq \frac{|6|-1}{2},\\ w_1\leq w_6+\frac{|1|-|6|-1}{2}}} \binom{|1|-1}{w_1-1} \binom{|5|}{\frac{|5|+1}{2}}\binom{|6|}{ w_6}  \label{eq:sa_5}
\end{IEEEeqnarray}
where \eqref{eq:3yd1} $+$ \eqref{eq:3yd4} implies $w_6\geq \frac{|6|-1}{2}$,  \eqref{eq:3yd3} $+$ \eqref{eq:3yd4} implies $w_1-w_6\leq \frac{|1|-|6|-1}{2}$, and \eqref{eq:sa_5} follows that $\frac{|1|-|6|-1}{2}\leq \frac{n}{2}-\frac{1+|5|}{2}-|6|$.
Since $ w_6+\frac{|1|-|6|-1}{2}\geq -w_6 + \frac{|6|+|1|}{2}$ when $w_6\geq \frac{|6|+1}{2}$, comparing the RHS' of \eqref{eq:of2} and \eqref{eq:sa_5}, we get
\begin{equation}
	\alpha_{\frac{n}{2}-1}^5\leq \left|\{w_3=1\}\cap \left(\mathop\cup_{i\leq \frac{n}{2}} \mc Y_3^B(i)\right)\right|. \label{eq:of5}
\end{equation}

Following~\eqref{eq:y3b}, we have
\begin{IEEEeqnarray}{rCl}
  &&	\left|\{w_3=0\}\cap \left(\mathop\cup_{i\leq \frac{n}{2}+1} \mc Y_3^B(i)\right)\right|\nonumber\\
  &=&  \sum_{\substack{w_1\geq 1,\\\eqref{eq:3yd1}+\eqref{eq:3yd4},\ \eqref{eq:3yd3}+\eqref{eq:3yd4},\\ w_1-w_6\leq \frac{n}{2}+1-\frac{1+|5|}{2}-|6|}} \binom{|1|-1}{w_1-1} \binom{|5|}{\frac{|5|-1}{2}}\binom{|6|}{ w_6}  \nonumber\\
  &=&  \sum_{\substack{w_1\geq 1,w_6:w_6\geq \frac{|6|+1}{2},\\
      w_1\leq w_6+\frac{|1|-|6|+1}{2}}} \binom{|1|-1}{w_1-1} \binom{|5|}{\frac{|5|-1}{2}}\binom{|6|}{ w_6} , \label{eq:sa_6}
\end{IEEEeqnarray}
where \eqref{eq:3yd1} $+$ \eqref{eq:3yd4} implies $w_6\geq \frac{|6|+1}{2}$, \eqref{eq:3yd3} $+$ \eqref{eq:3yd4} implies $w_1-w_6\leq \frac{|1|-|6|+1}{2}$, and \eqref{eq:sa_6} follows that $\frac{|1|-|6|+1}{2} \leq \frac{n}{2}+1-\frac{1+|5|}{2}-|6|$.
Since $w_6+\frac{|1|-|6|+1}{2}\geq -w_6+ \frac{|6|+|1|-2}{2}$ when $w_6\geq \frac{|6|+1}{2}$,  comparing the RHS' of \eqref{eq:of4} and \eqref{eq:sa_6}, we get
\begin{equation}
\alpha_{\frac{n}{2}}^5 \leq \left|\{w_3=0\}\cap \left(\mathop\cup_{i\leq \frac{n}{2}+1} \mc Y_3^B(i)\right)\right|. \label{eq:of6}
\end{equation}

When $d < \frac{n}{2}$, $\sum_{i=0}^{d-1} \alpha_i^5=0 \leq \sum_{i=1}^d \alpha_i^3$.
When $d=\frac{n}{2}$, by \eqref{eq:of5},
\begin{IEEEeqnarray*}{rCl}
	\sum_{i=0}^{d-1}\alpha_i^5&=&\alpha_{\frac{n}{2}-1}^5 \leq \left|\{w_3=1\}\cap \left(\mathop\cup_{i\leq \frac{n}{2}} \mc Y_3^B(i)\right)\right| \leq \sum_{i=1}^{\frac{n}{2}}\alpha^3_i.
\end{IEEEeqnarray*}
When $d\geq \frac{n}{2}+1$, by \eqref{eq:of5} and \eqref{eq:of6},
\begin{IEEEeqnarray}{rCl}
	\sum_{i=0}^{d-1}\alpha_i^5&=&\alpha_{\frac{n}{2}-1}^5+\alpha_{\frac{n}{2}}^5\nonumber\\
	&\leq& \left|\{w_3=1\}\cap \left(\mathop\cup_{i\leq \frac{n}{2}} \mc Y_3^B(i)\right)\right| +   \nonumber\\
	&&\left|\{w_3=0\}\cap \left(\mathop\cup_{i\leq \frac{n}{2}+1} \mc Y_3^B(i)\right)\right| \nonumber\\
	& \leq& \sum_{i=1}^{d}\alpha^3_i.\nonumber
\end{IEEEeqnarray}
Thus we have $\sum_{i=1}^d \alpha_i^3\geq \sum_{i=0}^{d-1} \alpha_i^5$ for $1\leq d \leq n$. By Corollary~\ref{cor:1}, $\ls_{\mc C'} \geq \ls_{\mc C}$, proving the case when $|3|=1$.

\end{fullversiononly}

\subsection{Algorithm for Verifying Optimal Codes}
\label{sec:comp}

Based on Theorem~\ref{thm:ccs}, we give an algorithm for verifying whether linear $ (n,2) $ codes are optimal for fixed $ n $ (see the pseudocode in Algorithm~\ref{alg:1}).
The algorithm checks each Class-I $ (n,2) $ code $ C $ specified by $(w_1,w_3,w_5,w_6)$ with the first column being $\bspan{1}$ and $ |3|_C\leq |5|_C\leq |6|_C$, and compares $C$ with $C'$ obtained by replacing the first column of $C$ to $\bspan{3}$.
Other $ (n,2) $ Class-I codes can be converted to ones of the above type by flipping columns and interchanging rows, and hence do  not need to be checked again.
By Theorem~\ref{thm:ccs}, if for each code $C$ checked by the algorithm we have $ \sum_{i=1}^{d} \alpha_{i}^3(C) \geq \sum_{i=0}^{d-1} \alpha_i^5(C)$ for $d=1,\ldots,n$, which implies $\lambda_C \leq \lambda_{C'}$ by Corollary~\ref{cor:1}, then linear $(n,2)$ codes are optimal.

Evaluating Algorithm~\S\ref{sec:comp}, we have verified that for $n \leq \numevnum$, linear codes are optimal. To total number of types of Class-I codes to evaluate is $O(n^4)$. For each type, there are less than $2n$ values $\alpha_i^3/\alpha_i^5$ to evaluate, each of which has complexity $O(n^2)$. Therefore,
the complexity of the algorithm is $O(n^7)$.

\begin{algorithm}
  \SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
  \SetAlgoLined
  \Input{$n$}
  \Output{$a$ (If $a=-1$, linear $(n,2)$ codes are optimal.) }
	Initialize $ a=-1 $\;

	\For{$ n_1=3,5,7,\ldots$ and $n_1\leq n$}{
          \For{$ n_3=2,3,\ldots,\left \lfloor \frac{n-n_1}{3} \right \rfloor $}{
            \For{$ n_5=n_3,n_3+2,\ldots$ and $n_5 \leq \left \lfloor \frac{n-n_1-n_3}{2} \right \rfloor $}{
              \For{$n_6=n_5,n_5+2,\ldots$ and $n_6 \leq n-n_1-n_3-n_5$}{
                Compute $\alpha_i^3$ and $\alpha_i^5$, $i=0,\ldots,n$ for code $C$ with $ |1|_C=n_1 $, $|3|_C=n_3$, $|5|_C=n_5$, $|6|_C=n_6 $\;
                \If{$ \sum_{i=1}^{d} \alpha_{i}^3< \sum_{i=0}^{d-1} \alpha_i^5$ for some $ d\in\{1,...,n\} $}{$ a=1 $;
    	 break;}
}
}
}}

	\caption{Check optimality of linear $ (n,2) $ codes}\label{alg:1}
\end{algorithm}

\section{Proof of Theorem~\ref{thm:odd}}
\label{sec:fliptwobits}

In this section,
\begin{fullversiononly}
we prove Theorem~\ref{thm:odd} using another case of the general approach in \S\ref{sec:formulation}.
\end{fullversiononly}

Let $C$ be an $(n,2)$ code with the first two columns $\bspan{1}$ and $\bspan{7}$. Let $C'$ be the code obtained by flipping the first two bits of $\vv c_3$, so that the first two columns of $C'$ are $\bspan{3}$ and $\bspan{5}$. (Other cases of Theorem~\ref{thm:odd} can be converted to this case by interchanging rows.)

Following the notations in \S\ref{sec:formulation}, $\mc O=\{1,2,4\}$, $\mc P=\{3\}$, and
\begin{equation*}
d_i'(\vv y) = d_i(\vv y) + (-1)^{\bspan{1}_i} (\overline{y_1}-y_1)+ (-1)^{\bspan{7}_i} (\overline{y_2}-y_2).
\end{equation*}
When $y_1=y_2 $, we have
\begin{equation}
	d_{\mc P}'(\vv y)=d_{\mc P}(\vv y).  \label{eq:thm2b}
\end{equation}
When $y_1\neq y_2$, we have $d_1'(\vv y)=d_1(\vv y)$,
$d_4'(\vv y)=d_4(\vv y)$, and
\begin{equation}
    d_2'(\vv y)-d_2(\vv y)= d_3'(\vv y)-d_3(\vv y)=\pm 2, \label{eq:thm2a}
\end{equation}
and hence
\begin{IEEEeqnarray}{rCl}
  \IEEEeqnarraymulticol{3}{l}{(d_{\mc O}'(\vv y)- d_{\mc O}(\vv y)) (d_{\mc P}'(\vv y)- d_{\mc P}(\vv y))}\nonumber \\
	&=& (d_{\{1,2,4\}}'(\vv y)-d_{\{1,2,4\}}(\vv y))(d_3'(\vv y)-d_3(\vv y))

	\geq 0.   \label{eq:ineq1}
\end{IEEEeqnarray}

Define the following subsets of $\{0,1\}^n$:
\begin{IEEEeqnarray*}{rCl}
	\mc Y_1 &=& \{y_1=y_2  \},\\
	\mc Y_2&=& \{y_1\neq y_2,d_{\mc O} \leq d_{\mc P} \land d_{\mc P}'  \},\\
	\mc Y_3 &=& \{y_1\neq y_2,d_{\mc O} > d_{\mc P} \land d_{\mc P}',d_{\mc P}\leq d_{\mc O}\land d_{\mc O}'   \},\\
	\mc Y_4 &=& \{y_1\neq y_2,d_{\mc P}'<d_{\mc O}\land d_{\mc O}' <d_{\mc P}  \},\\
	\mc Y_5&=& \{y_1\neq y_2,d_{\mc O}' \leq  d_{\mc P} \land d_{\mc P}' <d_{\mc O},d_{\mc O}'<d_{\mc P}  \}.
\end{IEEEeqnarray*}
Recall the function $f_2$ defined in \S\ref{sec:formulation} that flips the first two bits of a binary vector.

For $i=3,4$, let
\begin{equation*}
\mc Y_i'=\{f_2(\vv y): \vv y \in \mc Y_i \}.
\end{equation*}

We justify that $\mc Y_1,\mc Y_2,\mc Y_3,\mc Y_4,\mc Y_5$ form a partition of $\{0,1\}^n$ and $\mc Y_1,\mc Y_2,\mc Y_3',\mc Y_4',\mc Y_5$ form a partition of $\{0,1\}^n$:
First, we show that
\begin{equation}\label{eq:y45}
\mc Y_4 \cup \mc Y_5 =\{y_1\neq y_2,d_{\mc O} > d_{\mc P} \land d_{\mc P}',d_{\mc P}> d_{\mc O}\land d_{\mc O}'   \},
\end{equation}
and then we obtain $\bigcup_{i=1}^5\mc Y_i=\{0,1\}^n$. Moreover, $\mc Y_1, \ldots, \mc Y_{5}$ are all disjoint by checking the definition. Thus $\mc Y_1, \ldots, \mc Y_{5}$ form a partition of $\{0,1\}^n$.

\begin{fullversiononly}
To show \eqref{eq:y45},
since $\mc Y_4\subseteq \{ d_{\mc O} > d_{\mc P} \land d_{\mc P}'\}$, we have
\begin{IEEEeqnarray}{rCl}
	\mc Y_4
	&=& \{y_1\neq y_2,d_{\mc P}'<d_{\mc O}\land d_{\mc O}' <d_{\mc P}  \}\cap  \{ d_{\mc O} > d_{\mc P} \land d_{\mc P}'\} \nonumber \\
	&=&	\{y_1\neq y_2,d_{\mc O} > d_{\mc P} \land d_{\mc P}',d_{\mc P}> d_{\mc O}\land d_{\mc O}'   \}\cap \nonumber\\
	&&\{d_{\mc O}\land d_{\mc O}'>d_{\mc P}' \}. \label{eq:ineq2}
\end{IEEEeqnarray}
Denote
\begin{IEEEeqnarray*}{rCl}
\mathcal A_1&=&\{y_1\neq y_2,	d_{\mc O} > d_{\mc P} \land d_{\mc P}',d_{\mc P}> d_{\mc O}\land d_{\mc O}'\} \cap\\
&& \{d_{\mc O}\land d_{\mc O}'\leq d_{\mc P}'\}. \IEEEyesnumber  \label{eq:ineq3}
\end{IEEEeqnarray*}
For $\vv y\in \mathcal A_1$, we have $d_{\mc O}(\vv y)>d_{\mc O}'(\vv y)$ which implies $d_{\mc P}(\vv y)>d_{\mc P}'(\vv y)$ by \eqref{eq:thm2a} and \eqref{eq:ineq1}, and hence
\begin{equation*}
  d_{\mc O}'(\vv y)\leq d_{\mc P}(\vv y)\land d_{\mc P}'(\vv y)<d_{\mc O}(\vv y),\quad d_{O}'(\vv y)<d_{\mc P}(\vv y).
\end{equation*}
Thus we have $\vv y\in \mc Y_5$ and then $\mathcal A_1\subseteq \mc Y_5$.
For $\vv y \in \mc Y_5$, we have  $d_{\mc O}(\vv y)>d_{\mc O}'(\vv y)$ by the definition above, which implies $d_{\mc P}(\vv y)>d_{\mc P}'(\vv y)$ by \eqref{eq:thm2a} and \eqref{eq:ineq1}. Then we obtain
\begin{equation*}
	d_{\mc P}(\vv y)>d_{\mc O}(\vv y)\land d_{\mc O}'(\vv y)=d_{\mc O}'(\vv y)\leq d_{\mc P}'(\vv y)<d_{\mc O}(\vv y).
\end{equation*}

Thus $\vv y\in \mathcal A_1$ and then $\mc Y_5\subseteq \mathcal A_1$.
Therefore, $\mc Y_5= \mathcal A_1$.

From \eqref{eq:ineq2} and \eqref{eq:ineq3}, we obtain \eqref{eq:y45}.

\end{fullversiononly}

We further show that
\begin{equation}
  \label{eq:y34p}
  \mc Y_3'\cup \mc Y_4' \subseteq\mc Y_3 \cup \mc Y_4.
\end{equation}
Since $f_2$ is an one-to-one mapping, we get $\mc Y_3'\cup \mc Y_4' =\mc Y_3 \cup \mc Y_4$. Therefore, $\mc Y_1, \mc Y_2, \mc Y_3', \mc Y_4', \mc Y_5$ form a partition of $\{0,1\}^n$.

\begin{fullversiononly}
To show \eqref{eq:y34p}, we see
\begin{equation}
  \mc Y_4'=\{y_1 \neq y_2, d_{\mc P}<d_{\mc O}\land d_{\mc O}' <d_{\mc P}' \}
  \subseteq \mc Y_3, \label{eq:thm2a4}
\end{equation}
and
\begin{IEEEeqnarray*}{rCl}
  \mc Y_3'\setminus  \mc Y_4
  &=& \{y_1\neq y_2,d_{\mc O}' > d_{\mc P} \land d_{\mc P}',d_{\mc P}'\leq d_{\mc O}\land d_{\mc O}' \} \cap  \\
	&& (\{d_{\mc O}\land d_{\mc O}' \geq d_{\mc P}   \}  \cup   \{ d_{\mc P}'\geq d_{\mc O}\land d_{\mc O}'  \})\\
	&=& \{ y_1\neq y_2,d_{\mc O}' > d_{\mc P} \land d_{\mc P}',d_{\mc P}'\leq d_{\mc O}\land d_{\mc O}' ,  \\
        & & d_{\mc O}\land d_{\mc O}' \geq d_{\mc P}   \}  \cup
        \{y_1\neq y_2,d_{\mc O}' > d_{\mc P} \land d_{\mc P}',\\
        & & d_{\mc P}'\leq d_{\mc O}\land d_{\mc O}', d_{\mc P}'\geq d_{\mc O}\land d_{\mc O}'  \}  \\
	&= &  \{y_1\neq y_2 ,d_{\mc P}\land d_{\mc P}'<\max (d_{\mc P},d_{\mc P}')\leq d_{\mc O}\land d_{\mc O}'  \}\cup\\
	&& \{ y_1\neq y_2 , d_{\mc O}\land d_{\mc O}'=d_{\mc P}', d_{\mc P}\land d_{\mc P}'<d_{\mc O}'  \}  \IEEEyesnumber  \label{eq:thm2a1}

\end{IEEEeqnarray*}
where in the last equality $d_{\mc P}\land d_{\mc P}'<\max (d_{\mc P},d_{\mc P}')$ follows from \eqref{eq:thm2a}.
By \eqref{eq:ineq1}, when $y_1\neq y_2$, if $d_{\mc O}<d_{\mc O}'$, then $d_{\mc P}<d_{\mc P}'$;  and if $d_{\mc P}>d_{\mc P}'$, then $d_{\mc O}\geq d_{\mc O}'$. Hence, we can verify that both terms to union in \eqref{eq:thm2a1} are subsets of $\mc Y_3$. Therefore, $\mc Y_3'\setminus  \mc Y_4 \subset \mc Y_3$, which together with \eqref{eq:thm2a4}, proves \eqref{eq:y34p}.
\end{fullversiononly}

Moreover, we prove the following claims:
\begin{enumerate}
\item For $\vv y \in \mc Y_1$, $d_C(\vv y) = d_{C'}(\vv y)$;
\item For $\vv y \in \mc Y_2$, $d_C(\vv y) = d_{C'}(\vv y)=d_{\mc O}$;
\item For $\vv y \in \mc Y_3$, $d_C(\vv y) = d_{C'}( f_2(\vv y))=d_{\mc P}$;
\item
  For $\vv y \in \mc Y_4$, $d_C(\vv y) = d_{\mc O}\land d_{\mc P}\geq d_{C'}(f_2(\vv y))=d_{\mc O}'$;
\item For $\vv y \in \mc Y_5$, $d_C(\vv y) = d_{\mc O}\land d_{\mc P}\geq d_{C'}(\vv y)=d_{\mc P}'$.
\end{enumerate}
Following the similar argument as in \S\ref{sec:gen}, we can show that $\lambda_{C'} \geq \lambda_C$.

\begin{fullversiononly}
The above claims are justified as follows:
\begin{enumerate}
\item For $\vv y \in \mc Y_1$, as $y_1=y_2$, we have $d_{\mc P}'=d_{\mc P}$ by \eqref{eq:thm2b}, and hence
  \begin{IEEEeqnarray*}{rCl}
    d_{C}(\vv y)&=& d_{\mc O}(\vv y)\land d_{\mc P}(\vv y)=d_{\mc O}(\vv y)\land d_{\mc P}'(\vv y)=d_{C'}(\vv y).
  \end{IEEEeqnarray*}

\item For $\vv y \in \mc Y_2$, by the definition of $\mc Y_2$, we have $d_{\mc O}\leq d_{\mc P}\land d_{\mc P}'$, and hence $d_C(\vv y) = d_{C'}(\vv y)=d_{\mc O}$.

\item  For $\vv y \in \mc Y_3$, we have $d_{\mc P}\leq d_{\mc O}\land d_{\mc O}'$ by the definition of $\mc Y_3$. We then have
  \begin{IEEEeqnarray*}{rCl}
    d_{C}(\vv y)&=& d_{\mc O}(\vv y)\land d_{\mc P}(\vv y) = d_{\mc P}(\vv y),\\
    d_{C'}(f_2(\vv y))&=&  d_{\mc O}'(\vv y)\land d_{\mc P}(\vv y) = d_{\mc P}(\vv y).
  \end{IEEEeqnarray*}

\item For $\vv y \in \mc Y_4$, we have $y_1\neq y_2,d_{\mc P}'<d_{\mc O}\land d_{\mc O}'<d_{\mc P}$ by the definition of $\mc Y_4$. By \eqref{eq:ineq1},
    $d_{\mc O}\land d_{\mc O}'=d_{\mc O}'$,
  which implies
  $d_{C'}(f_2(\vv y))=d_{\mc O}'(\vv y)\land d_{\mc P}(\vv y)=d_{\mc O}'(\vv y)$
  and hence
  \begin{IEEEeqnarray*}{rCl}
    d_C(\vv y)=d_{\mc O}(\vv y)\land d_{\mc P}(\vv y)\geq d_{\mc O}'(\vv y)=	d_{C'}(f_2(\vv y)).
  \end{IEEEeqnarray*}

\item For $\vv y\in \mc Y_5$, we have $y_1\neq y_2,d_{\mc O}' \leq  d_{\mc P} \land d_{\mc P}' <d_{\mc O} $. By \eqref{eq:thm2a} and \eqref{eq:ineq1}, $d_{\mc P}'<d_{\mc P}$. Then we have
  \begin{IEEEeqnarray*}{rCl}
    d_C(\vv y)=d_{\mc O}\land d_{\mc P}\geq d_{\mc O}\land d_{\mc P}'=d_{C'}(\vv y)
  \end{IEEEeqnarray*}
  and
  \begin{equation*}
    d_{C'}(\vv y)=d_{\mc P}'(\vv y).
  \end{equation*}
\end{enumerate}

\end{fullversiononly}

\section{Concluding Remarks}
It is attractive to prove in general whether linear $(n,2)$ codes are optimal or not.
One further research direction is to extend the technique for comparing the decoding performance of two codes  to codes of more than four codewords.

\begin{fullversiononly}

  \appendices

\section{Proofs} \label{app:proofs}

\begin{proof}[Proof of Lemma~\ref{lemma:1}]
  By checking the definition, we see that $\mc Y_1,\ldots \mc Y_5$ are all disjoint. To show they form a partition, we can verify that
  \begin{IEEEeqnarray*}{rCl}
    \mc Y_1 \cup \mc Y_4 \cup \mc Y_5 & = &  \{d_{\mc O} \leq d_{\mc P}\land d_{\mc P}'\}, \\
    \mc Y_2 \cup \mc Y_3 & = &  \{d_{\mc O} > d_{\mc P}\land d_{\mc P}'\}
  \end{IEEEeqnarray*}
  and hence $(\mc Y_1 \cup \mc Y_4 \cup \mc Y_5)\cup(\mc Y_2 \cup \mc Y_3) = \{0,1\}^n$.

We first prove that $\mc Y_1 \cup \mc Y_4 \cup \mc Y_5  =  \{d_{\mc O} \leq d_{\mc P}\land d_{\mc P}'\}$. Notice that the three sets can be rewritten as
\begin{IEEEeqnarray}{rCl}
	\mc Y_1 &=&  \{ d_{\mc O} \leq d_{\mc P} < d_{\mc P}' \} \cup \{ d_{\mc O} \leq d_{\mc P}' \leq d_{\mc P}, d_{\mc O}' \leq d_{\mc P}' \}\nonumber\\
	&=&(\{ d_{\mc O}\leq d_{\mc P}\land d_{\mc P}'\}\cap \{  d_{\mc P} < d_{\mc P}'  \})\cup  (\{ d_{\mc O}\leq d_{\mc P}\land d_{\mc P}'\} \nonumber\\
	&& \cap \{d_{\mc P}' \leq d_{\mc P}, d_{\mc O}' \leq d_{\mc P}' \}  ) \label{eq:lemma5a}, \\
	\mc Y_4&=& \{d_{\mc P} = d_{\mc P}' = d_{\mc O} < d_{\mc O}' \}\nonumber\\
	&\labelrel={myeq:lemma5b}& \{ d_{\mc O}\leq d_{\mc P}\land d_{\mc P}'\}\cap \{d_{\mc P}' \leq d_{\mc P},d_{\mc O}'>d_{\mc P}',
	d_{\mc P}=d_{\mc P}' \},\nonumber\\
	&&\label{eq:lemma5b}\\
	\mc Y_5 &=&\{ d_{\mc P}' = d_{\mc O} < d_{\mc O}' = d_{\mc P} \} \nonumber\\
	&\labelrel={myeq:lemma5c}& \{ d_{\mc O}\leq d_{\mc P}\land d_{\mc P}'\}\cap \{d_{\mc P}' \leq d_{\mc P},d_{\mc O}'>d_{\mc P}',
	d_{\mc P}>d_{\mc P}' \}.\nonumber\\
	&& \label{eq:lemma5c}
\end{IEEEeqnarray}
For $\forall \vv y$, we have
\begin{equation}
	  |d_{\mc S}(\vv y) -d_{\mc S}'(\vv y)| \leq 1,  \label{eq:lemma5d}
\end{equation}
which can be obtained by the definition. Then if $d_{\mc O}\leq d_{\mc P}'<d_{\mc O}'$, we will have $d_{\mc O}= d_{\mc P}'$ and thus the equality \eqref{myeq:lemma5b} in \eqref{eq:lemma5b} holds. Furthermore, if $d_{\mc O}'>d_{\mc P}' $ we have $d_{\mc O}\geq d_{\mc P}'$, and if $d_{\mc O}'>d_{\mc P}'$, we have $d_{\mc O}\geq d_{\mc P}'$ and thus the equality \eqref{myeq:lemma5c} in \eqref{eq:lemma5c} holds.
By \eqref{eq:lemma5b} and \eqref{eq:lemma5c}, we have
\begin{IEEEeqnarray}{rCl}
	\mc Y_4\cup\mc Y_5 &=& \{ d_{\mc O}\leq d_{\mc P}\land d_{\mc P}'\} \cap \{d_{\mc P}' \leq d_{\mc P},d_{\mc O}'>d_{\mc P}' \}.\nonumber
\end{IEEEeqnarray}
From \eqref{eq:lemma5a}, this further implies
\begin{IEEEeqnarray*}{rCl}
	\mc Y_1 \cup \mc Y_4 \cup \mc Y_5  =  \{d_{\mc O} \leq d_{\mc P}\land  d_{\mc P}'\}.
\end{IEEEeqnarray*}

We now prove $\mc Y_2\cup \mc Y_3=\{d_{\mc O} > d_{\mc P}\land  d_{\mc P}'\}.$ First we rewrite the two sets as
\begin{IEEEeqnarray}{rCl}
	\mc Y_2 &=& \{ d_{\mc P} \leq d_{\mc P}', d_{\mc P} < d_{\mc O}\} \cup  \{ d_{\mc P}' < d_{\mc P} \leq d_{\mc O}, d_{\mc P} \leq d_{\mc O}'\}\nonumber \\
	&=& (\{d_{\mc O} > d_{\mc P}\land  d_{\mc P}'\}\cap \{d_{\mc P} \leq d_{\mc P}' \}  )\cup ( \{d_{\mc O} > d_{\mc P}\land  d_{\mc P}'\}\nonumber\\
	&&\cap \{d_{\mc P} > d_{\mc P}' ,d_{\mc P} \leq d_{\mc O}, d_{\mc P} \leq d_{\mc O}'\}   ) \nonumber\\
	&\labelrel={myeq:lemma5e}& (\{d_{\mc O} > d_{\mc P}\land  d_{\mc P}'\}\cap \{d_{\mc P} \leq d_{\mc P}' \}  )\cup ( \{d_{\mc O} > d_{\mc P}\land  d_{\mc P}'\}\nonumber\\
	&&\cap \{d_{\mc P} > d_{\mc P}' , d_{\mc P} \leq d_{\mc O}'\}   ), \label{eq:lemma5e}\\
	\mc Y_3&=& \{d_{\mc P}' = d_{\mc O}' < d_{\mc P} = d_{\mc O}\}\nonumber\\
	&\labelrel={myeq:lemma5f}& \{d_{\mc O} > d_{\mc P}\land  d_{\mc P}'\}\cap \{d_{\mc P} > d_{\mc P}' , d_{\mc P} > d_{\mc O}'\}.\label{eq:lemma5f}
\end{IEEEeqnarray}
By \eqref{eq:lemma5d}, we can get $d_{\mc P}\leq d_{\mc O}$ if $d_{\mc O}>d_{\mc P}',d_{\mc P}>d_{\mc P}'$. Then the equality \eqref{myeq:lemma5e} in \eqref{eq:lemma5e} holds.

Similarly we can justify \eqref{myeq:lemma5f} in \eqref{eq:lemma5f} by \eqref{eq:lemma5d}.

  By definition,
  \begin{IEEEeqnarray*}{rCl}
    \mc Y_2' & = & \{ d_{\mc P}' \leq d_{\mc P}, d_{\mc P}' < d_{\mc O}'\} \cup \{ d_{\mc P} < d_{\mc P}' \leq d_{\mc O}', d_{\mc P}' \leq d_{\mc O}\}, \\
    \mc Y_4' & = & \{d_{\mc P} = d_{\mc P}' = d_{\mc O}' < d_{\mc O}\}, \\
    \mc Y_5' & = & \{ d_{\mc P} = d_{\mc O}' < d_{\mc O}= d_{\mc P}'\}.
  \end{IEEEeqnarray*}
  It can be verified that $(\mc Y_2'\cup \mc Y_4'\cup \mc Y_5')\cap (\mc Y_1\cup \mc Y_3) = \emptyset$.
  As $f_1$ is a one-to-one mapping, $\mc Y_2'\cup \mc Y_4'\cup \mc Y_5' = \mc Y_2\cup \mc Y_4\cup \mc Y_5$. Hence, we conclude that $\mc Y_1, \mc Y_2', \mc Y_3, \mc Y_4', \mc Y_5'$ form a partition of $\{0,1\}^n$.

We use the following facts in the proof of claim 1) -- 5).
\begin{IEEEeqnarray*}{rCl}
  d_C(\vv y) & = & \min\{d_{\mc O}(\vv y), d_{\mc P}(\vv y)\} \\
  d_{C'}(\vv y) & = &  \min\{d_{\mc O}(\vv y), d_{\mc P}'(\vv y)\}\\
  d_{C'}(f_1(\vv y)) & = &  \min\{d_{\mc O}'(\vv y), d_{\mc P}(\vv y)\}.
\end{IEEEeqnarray*}
To prove the claim 1),
for $\vv y \in \mc Y_1$, by the definition of $\mc Y_1$, $d_{\mc O} \leq \min\{d_{\mc P}, d_{\mc P}'\}$. Hence $d_C(\vv y) = d_{C'}(\vv y)=d_{\mc O}$.
To prove claim 2), for $\vv y \in \mc Y_2$, by the definition of $\mc Y_2$, $d_{\mc P} \leq \min\{d_{\mc O},d_{\mc O}'\}$, and hence $d_C(\vv y) = d_{\mc P}$. Further,
\begin{IEEEeqnarray*}{rCl}
  d_{C'}(\vv y') & = & d_{\mc O}(\vv y')\land  d_{\mc P}'(\vv y')\\
  & = &  d_{\mc O}'(\vv y)\land  d_{\mc P}(\vv y) = d_{\mc P}(\vv y).
\end{IEEEeqnarray*}
To prove claim 3), for $\vv y\in \mc Y_3$, $d_C(\vv y)=d_{\mc O}(\vv y)\land d_{\mc P}(\vv y)=d_{\mc P}(\vv y)$ by the definition of $\mc Y_3$. Moreover,
\begin{IEEEeqnarray*}{rCl}
d_{\vv C'}(\vv y)&=& d_{\mc O}(\vv y)\land  d_{\mc P}'(\vv y)=d_{\mc P}'(\vv y)<d_{C}(\vv y).
\end{IEEEeqnarray*}
By \eqref{eq:lemma5d}, we have $d_{\mc P}=d_{\mc P}'+1$.
To prove claim 4), for $\vv y\in \mc Y_4$, by the definition of $\mc Y_4$,
\begin{IEEEeqnarray*}{rCl}
	&&d_C(\vv y)=d_{\mc O}(\vv y)\land d_{\mc P}(\vv y)=d_{\mc P}(\vv y),\\
	&& d_{C'}(\vv y')=d_{\mc O}'(\vv y)\land d_{\mc P}(\vv y)=d_{\mc P}(\vv y).
\end{IEEEeqnarray*}
To prove claim 5), for $\vv y\in \mc Y_5$, $d_C(\vv y)=d_{\mc O}(\vv y)\land d_{\mc P}(\vv y)=d_{\mc O}(\vv y)$ by the definition of $\mc Y_5$. Moreover,
\begin{IEEEeqnarray*}{rCl}
	d_{\vv C'}(\vv y')&=& d_{\mc O}'(\vv y)\land  d_{\mc P}(\vv y)=d_{\mc O}'(\vv y)>d_{C}(\vv y).
\end{IEEEeqnarray*}
By \eqref{eq:lemma5d}, we have $d_{\mc O}'=d_{\mc O}+1$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{the:1}]
  As $\{\mc Y_1, \mc Y_2', \mc Y_3, \mc Y_4', \mc Y_5'\}$ is a partition of $\{0,1\}^n$, we have $\alpha_d(C') = \sum_{i=1}^5 \alpha_d^i(C')$ where
  \begin{IEEEeqnarray*}{rCl}
    \alpha_d^1(C') & = & |\{\vv y\in \mc Y_1: d_{C'}(\vv y) = d\}| = \alpha_d^1(C), \\
    \alpha_d^2(C') & = & |\{\vv y\in \mc Y_2': d_{C'}(\vv y) = d\}| = \alpha_d^2(C), \\
    \alpha_d^3(C') & = & |\{\vv y\in \mc Y_3: d_{C'}(\vv y) = d\}| =
    \begin{cases}
      \alpha_{d+1}^3(C) & d<n\\
      0 & d=n
    \end{cases}, \\
    \alpha_d^4(C') & = & |\{\vv y\in \mc Y_4': d_{C'}(\vv y) = d\}| = \alpha_d^4(C), \\
    \alpha_d^5(C') & = & |\{\vv y\in \mc Y_5': d_{C'}(\vv y) = d\}| =
    \begin{cases}
      \alpha_{d-1}^5(C) & d\geq 1\\
      0 & d=0
    \end{cases}.
  \end{IEEEeqnarray*}
  The second equality in each line follows from Lemma~\ref{lemma:1}.
  Together with \eqref{eq:10}, we write
  \begin{IEEEeqnarray*}{rCl}
    \ls_{\mc C'}-\ls_{\mc C} & = & \frac{1}{|\mc C|} \sum_{d=0}^n( \alpha_d(C')-\alpha_d(C)) (1-\epsilon)^{n-d}\epsilon^{d}\\
    & = & \frac{1}{|\mc C|} \sum_{d=0}^n\sum_{i=1}^5( \alpha_d^i(C')-\alpha_d^i(C)) (1-\epsilon)^{n-d}\epsilon^{d} \\
     & = & \frac{1}{|\mc C|} \sum_{d=0}^n\sum_{i=3,5}( \alpha_d^i(C')-\alpha_d^i(C)) (1-\epsilon)^{n-d}\epsilon^{d},
   \end{IEEEeqnarray*}
   By substituting $\alpha_d^3(C') = \alpha_{d+1}^3(C)$ and $\alpha_d^5(C') = \alpha_{d-1}^5(C)$, we see that $\ls_{\mc C'} \geq \ls_{\mc C}$ if and only if
   \begin{equation*}
     \sum_{d=0}^n[\alpha_{d+1}^3(C)-\alpha_d^3(C)+\alpha_{d-1}^5(C)-\alpha_d^5(C)] \left(\frac{\epsilon}{1-\epsilon}\right)^{d} \geq 0,
   \end{equation*}
   where the LHS can be further simplified as
   \begin{IEEEeqnarray*}{rCl}

     \sum_{d=1}^n[\alpha_d^3(C)-\alpha_{d-1}^5(C)] \left(\frac{\epsilon}{1-\epsilon}\right)^{d-1}\left(1-\frac{\epsilon}{1-\epsilon}\right).
   \end{IEEEeqnarray*}
  The theorem is proved by checking that in the above argument, the relation $\geq$ can be replaced by $>$.
\end{proof}

\begin{proof}[Proof of Corollary~\ref{cor:1}]
  Let $\epsilon_0=\frac{\epsilon}{1-\epsilon}$ and let $\Psi_d = \sum_{i=1}^d\left[\alpha_{i}^3(C) -  \alpha_{i-1}^5(C)\right]$ for $d=1,\ldots, n$ and $\Psi_0=0$.
  Write
  \begin{IEEEeqnarray*}{rCl}
    \IEEEeqnarraymulticol{3}{l}{\sum_{d=1}^n[\alpha_d^3(C)-\alpha_{d-1}^5(C)] \left(\frac{\epsilon}{1-\epsilon}\right)^{d-1}} \\
    & = &
    \sum_{d=1}^n(\Psi_d-\Psi_{d-1}) \epsilon_0^{d-1} \\
    & = & \Psi_n\epsilon_0^{n-1}+ \sum_{d=1}^{n-1} \Psi_d (\epsilon_0^{d-1}-\epsilon_0^d).
  \end{IEEEeqnarray*}
  Note that for $0<\epsilon<\frac{1}{2}$, $\epsilon_0^d=\left(\frac{\epsilon}{1-\epsilon}\right)^{d}$ is a strictly  decreasing function of $d$.
  By Theorem~\ref{the:1}, we can prove the sufficient conditions of the corollary.
\end{proof}

\section{A Lemma}
\label{app:lemma}

A similar result has been proved in \cite{chen2013optimal}. Here we provide a proof for completeness.

\begin{lemma}\label{lemma:inequation}
  Suppose $|3|\leq |6|$ of the same parity. For $(w_3,w_5) \in \mathcal{W}_5$ (defined in \eqref{eq:w5}),
\begin{equation*}
  \binom{|3|}{w_3}\binom{|6|}{w_6} \leq \binom{|3|}{\frac{|3|-|6|}{2}+w_6} \binom{|6|}{\frac{|6|-|3|}{2}+w_3}.
\end{equation*}
\end{lemma}
\begin{proof}
Let $\hat{w}_i= w_i-\frac{|i|}{2}$, $i=3,6$.  The inequality to prove becomes
	\begin{equation*}
\binom{|3|}{\frac{|3|}{2}+\hat{w}_3}\binom{|6|}{\frac{|6|}{2}+\hat{w}_6}\leq \binom{|3|}{\frac{|3|}{2}+\hat{w}_6}\binom{|6|}{\frac{|6|}{2}+\hat{w}_3}.
\end{equation*}
We have by the definition of $\mathcal{W}_5$ in \eqref{eq:w5},
\begin{equation*}
  \hat{w}_3 +\hat{ w_6 }\geq 1,   \hat{w}_3-\hat{w}_6 \geq1, \hat{w}_3\geq \frac{n+1}{2}-d .
\end{equation*}
We write
\begin{IEEEeqnarray*}{rCl}
\IEEEeqnarraymulticol{3}{l}{\frac{\binom{|3|}{\frac{|3|}{2}+\hat{w}_3}\binom{|6|}{\frac{|6|}{2}+\hat{w}_6}}{\binom{|3|}{\frac{|3|}{2}+\hat{w}_6}\binom{|6|}{\frac{|6|}{2}+\hat{w}_3}}
		 =  \frac{ \frac{|3| \cdots (\frac{|3|}{2}-\hat{w}_3+1)}{(\frac{|3|}{2}+\hat{w}_3)!}  \frac{|6| \cdots (\frac{|6|}{2}-\hat{w}_6+1)}{(\frac{|6|}{2}+\hat{w}_6)!}}{ \frac{|3| \cdots (\frac{|3|}{2}-\hat{w}_6+1)}{(\frac{|3|}{2}+\hat{w}_6)!}  \frac{|6| \cdots (\frac{|6|}{2}-\hat{w}_3+1)}{(\frac{|6|}{2}+\hat{w}_3)!}} } \\
		&=&  \frac{(\frac{|3|}{2}-\hat{w}_6) \cdots (\frac{|3|}{2}-\hat{ w_3}+1)}{(\frac{|3|}{2}+\hat{w}_3) \cdots (\frac{|3|}{2}+\hat{ w_6}+1)}
		\cdot \frac{(\frac{|6|}{2}+\hat{w}_3) \cdots (\frac{|6|}{2}+\hat{ w_6}+1)}{(\frac{|6|}{2}-\hat{w}_6) \cdots (\frac{|6|}{2}-\hat{ w_3}+1)}  \\
		&=& \prod_{i=1}^{\hat{w}_3-\hat{w}_6}\frac{\frac{|3|}{2}-\hat{ w_3}+i}{\frac{|3|}{2}+\hat{ w_6}+i}  \frac{\frac{|6|}{2}+\hat{ w_6}+i}{\frac{|6|}{2}-\hat{ w_3}+i}  \\
		&=&  \prod_{i=1}^{\hat{w}_3-\hat{w}_6} \frac{(\frac{|3|}{2}+i)(\frac{|6|}{2}+i)-\hat{w}_3\hat{w}_6  +(\frac{|3|}{2}+i)\hat{w}_6 -\hat{w}_3(\frac{|6|}{2}+i)}{(\frac{|3|}{2}+i)(\frac{|6|}{2}+i)-\hat{w}_3\hat{w}_6 -(\frac{|3|}{2}+i)\hat{w}_3 +\hat{w}_6(\frac{|6|}{2}+i)}\\
		&\leq&1,
	\end{IEEEeqnarray*}
where the last inequality is obtained by comparing the last two terms of the denominator and the nominator:
\begin{IEEEeqnarray*}{rCl}
  \IEEEeqnarraymulticol{3}{l}{\textstyle\left(\frac{|3|}{2}+i\right)\hat{w}_6 -\hat{w}_3\left(\frac{|6|}{2}+i\right)-\left(-\left(\frac{|3|}{2}+i\right)\hat{w}_3 +\hat{w}_6\left(\frac{|6|}{2}+i\right)\right)}\\
  &=&(\hat{w}_3+\hat{w}_6)\left(\frac{|3|}{2}-\frac{|6|}{2}\right) \\
  &\leq & 0
\end{IEEEeqnarray*}
where the inequality follows from $\hat{w}_3+\hat{w}_6\geq 1$ and $|3|\leq |6|$.
\end{proof}

\end{fullversiononly}


text:
\begin{document}

\title{\vspace{-0.5in}\hfill{\normalsize ANL-HEP-PR-08-35}\bigskip\bigskip\\\vspace{-0.5in}\hfill{\normalsize UMTG - 7\bigskip}\\Ternary Virasoro - Witt Algebra}
\author{Thomas L Curtright,$^{\text{\S ,\#}}$ \ David B Fairlie,$^{\text{\dag,\#}}
$\medskip\ and Cosmas K Zachos$^{\text{\P ,\#}}$\\$^{\text{\S }}${\small Department of Physics, University of Miami, Coral
Gables, Florida 33124, USA}\\$^{\text{\dag}}${\small Department of Mathematical Sciences, Durham
University, Durham, DH1 3LE, UK}\\$^{\text{\P }}${\small High Energy Physics Division, Argonne National
Laboratory, Argonne, IL 60439-4815, USA} }
\date{}
\maketitle

\begin{abstract}
A 3-bracket variant of the Virasoro-Witt algebra is constructed through the
use of su(1,1) enveloping algebra techniques. \ The Leibniz rules for
3-brackets acting on other 3-brackets in the algebra are discussed and
verified in various situations.

\vfill

\underline
{$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $
}

$^{\text{\#}}${\footnotesize curtright@miami.edu, david.fairlie@durham.ac.uk,
zachos@anl.gov}

\bigskip

\end{abstract}

\section{Introduction}

Recently there has been some progress in constructing a $2+1$-dimensional
local quantum field theory with $SO(8)$ superconformal symmetry
\cite{B,S,G,Gustavsson,H}. \ This is a useful stepping-stone to obtain a
world-volume Lagrangian description for coincident M2-branes. \ Crucial to the
construction is the use of 3-algebras (a term originally coined by Filippov
\cite{F}, following up on earlier work of Nambu \cite{N}) which are built
around antisymmetrized products of three operators. \ It now seems possible to
incorporate an arbitrary Lie algebra into a 3-algebra through the use of a
small number of auxiliary charges.

While it may be sufficient to restrict attention to finite Lie and 3-algebras
for model-building purposes, e.g. in M-theory, nevertheless it is
intrinsically interesting to also consider infinite dimensional 3-algebras.
\ Previous studies \cite{H}\ have already considered the infinite 3-algebra
that follows from the classical Nambu 3-bracket, on a 3-torus, in the form
\begin{equation}
\left[  E_{a},E_{b},E_{c}\right]  =a\cdot\left(  b\times c\right)
E_{a+b+c}\ . \label{ClassicalNambu3BracketAlgebra}
\end{equation}
The indices here are 3-vectors, with $\cdot$\ and $\times$\ the usual dot and
cross products of those 3-vectors. \ By virtue of some simple identities for
the volumes of parallelepipeds, this satisfies Filippov's condition\ (the
FI,\ or so-called \textquotedblleft fundamental identity\textquotedblright) --
a property he required to warrant the 3-algebra designation.
\begin{equation}
\left[  E_{x},E_{y},\left[  E_{a},E_{b},E_{c}\right]  \right]  =\left[
\left[  E_{x},E_{y},E_{a}\right]  ,E_{b},E_{c}\right]  +\left[  E_{a},\left[
E_{x},E_{y},E_{b}\right]  ,E_{c}\right]  +\left[  E_{a},E_{b},\left[
E_{x},E_{y},E_{c}\right]  \right]  \ .
\label{ClassicalNambu3BracketAlgebraFIs}
\end{equation}
This is easily remembered as just a Leibniz rule for 3-brackets acting on
other 3-brackets. \ (However, this does \emph{not} necessarily mean $\left[
E_{a},E_{b},AB\right]  $ is the same as $\left[  E_{a},E_{b},A\right]
B+A\left[  E_{a},E_{b},B\right]  $ for arbitrary $A$ and $B$. \ While these
are the same for the \emph{classical} Nambu bracket, in general these two
expressions differ for an operator algebra.)

A 3-algebraic variant of the $su\left(  2\right)  $ Kac-Moody algebra has also
been studied \cite{KM}. \ Moreover, it is straightforward to embed an infinite
Onsager 3-algebra in this framework, just as it is to embed the usual infinite
Onsager Lie algebra \cite{Onsager} (also see \cite{FZ}) into that for
$su\left(  2\right)  $. \ Nonetheless, it is not completely clear from these
previous examples how infinite conformal 3-algebras should be constructed.
\ We consider this problem here. \ We construct an infinite 3-algebra variant
of the centerless Virasoro (i.e. Witt) algebra. \ We leave the inclusion of
central charges as well as supersymmetric extensions of our results for future work.

\section{Three-brackets from Enveloping Algebras}

The \textquotedblleft BL algebra\textquotedblright\ presented by Bagger and
Lambert \cite{B} is actually just a minor modification of Nambu's original
results\ on 3-brackets for the su(2) angular momentum algebra, $\left[
L_{x},L_{y}\right]  =iL_{z}$, etc. \ Of course, Nambu's work motivated and
inspired both Filippov (12 years later) and Takhtajan (20 years later)
\cite{T}, as well as more recent studies (see \cite{C} and references
therein). \

After introducing the 3-bracket, Nambu noted that the $su(2)$ Casimir followed
immediately from it (see Eqn(49) in \cite{N}).
\begin{equation}
\left[  L_{x},L_{y},L_{z}\right]  \equiv L_{x}\left[  L_{y},L_{z}\right]
+L_{y}\left[  L_{z},L_{x}\right]  +L_{z}\left[  L_{x},L_{y}\right]  =i\left(
L_{x}^{2}+L_{y}^{2}+L_{z}^{2}\right)  =iL^{2}\ .
\end{equation}
From this it follows that the BL$\ $algebra can be easily found in the
enveloping algebra for $su\left(  2\right)  $. \ If we rescale the angular
momenta by a fourth root of the Casimir,
\begin{equation}
Q_{x}=\frac{L_{x}}{\sqrt[4]{L^{2}}}\ ,\ \ \ Q_{y}=\frac{L_{y}}{\sqrt[4]{L^{2}
}}\ ,\ \ \ Q_{z}=\frac{L_{z}}{\sqrt[4]{L^{2}}}\ , \label{NambuSU2}
\end{equation}
as well as define a fourth charge as that fourth root,
\begin{equation}
Q_{t}=\sqrt[4]{L^{2}}\ , \label{NambuA4}
\end{equation}
then we obtain $\left[  Q_{t},Q_{x}\right]  =0$ etc. \ Hence
\begin{equation}
\left[  Q_{x},Q_{y},Q_{z}\right]  =iQ_{t}\ ,\ \ \ \left[  Q_{t},Q_{x}
,Q_{y}\right]  =iQ_{z}\ ,\ \ \ \left[  Q_{t},Q_{y},Q_{z}\right]
=iQ_{x}\ ,\ \ \ \left[  Q_{t},Q_{z},Q_{x}\right]  =iQ_{y}\ .
\label{A4OurPhases}
\end{equation}
So, any matrix rep of the angular momentum algebra yields a matrix rep of this
3-bracket algebra. \ This algebra can be summarized as
\begin{equation}
\left[  Q_{a},Q_{b},Q_{c}\right]  =i\varepsilon_{abc}^{\ \ \ \ d}~Q_{d}\ ,
\end{equation}
where $\varepsilon_{xyzt}=+1$ with a $\left\lceil -1,-1,-1,+1\right\rfloor $
Lorentz signature used to raise indices. \ In this form it is easily verified
that the FI conditions are satisfied: \ $\left[  Q_{d},Q_{e},\left[
Q_{a},Q_{b},Q_{c}\right]  \right]  =\left[  \left[  Q_{d},Q_{e},Q_{a}\right]
,Q_{b},Q_{c}\right]  +\left[  Q_{a},\left[  Q_{d},Q_{e},Q_{b}\right]
,Q_{c}\right]  +\left[  Q_{a},Q_{b}\left[  Q_{d},Q_{e},Q_{c}\right]  \right]
$. \ (Again, this does \emph{not} mean $\left[  Q_{d},Q_{e},AB\right]  $ is
the same as $\left[  Q_{d},Q_{e},A\right]  B+A\left[  Q_{d},Q_{e},B\right]  $
for arbitrary $A$ and $B$.)

Let us now pursue such enveloping algebra techniques to consider infinite
conformal algebras as realized nonlinearly with $su\left(  1,1\right)  $
generators. \ This gives the \emph{centerless}\ version of the usual Virasoro
algebra,
\begin{equation}
\left[  L_{n},L_{m}\right]  =\left(  n-m\right)  L_{n+m}\ .
\label{VirasoroWitt}
\end{equation}
An explicit realization is \cite{Fairlie}
\begin{align}
L_{n}  &  =\left(  L_{0}+n\beta\right)  \frac{\Gamma\left(  L_{0}
+\beta\right)  }{\Gamma\left(  L_{0}+\beta+n\right)  }\left(  L_{1}\right)
^{n}\ ,\nonumber\\
L_{-n}  &  =\left(  L_{0}-n\beta\right)  \frac{\Gamma\left(  L_{0}
+1-\beta-n\right)  }{\Gamma\left(  L_{0}+1-\beta\right)  }\left(
L_{-1}\right)  ^{n}\ ,
\end{align}
where the $su\left(  1,1\right)  $ algebra and Casimir are given by
\begin{align}
\left[  L_{+1},L_{-1}\right]   &  =2L_{0}\ ,\ \ \ \left[  L_{\pm1}
,L_{0}\right]  =\pm L_{\pm1}\ ,\nonumber\\
\beta\left(  1-\beta\right)   &  \equiv C=L_{+1}L_{-1}-\left(  L_{0}+1\right)
L_{0}\ . \label{su(1,1)}
\end{align}
From this construction, we compute 3-brackets and abstract from them a
3-algebra. \ An interesting question is: Does the algebra so obtained satisfy
the 3-bracket Leibniz rule when acting on other 3-brackets? \

First we compute the 3-bracket for charges with positive indices.
\begin{align}
\left[  L_{k},L_{m},L_{n}\right]   &  =\left(  m-n\right)  L_{k}
L_{m+n}+\left(  n-k\right)  L_{m}L_{n+k}+\left(  k-m\right)  L_{n}
L_{k+m}\nonumber\\
&  =C~\frac{\left(  k-m\right)  \left(  m-n\right)  \left(  k-n\right)
}{L_{0}+\left(  k+n+m\right)  \beta}~L_{k+m+n}\ .
\end{align}
Here we have used (\ref{VirasoroWitt}) and an identity specific to the
realization at hand,
\begin{equation}
L_{k}L_{m+n}=\left(  L_{0}+k\beta\right)  \left(  1+\frac{k\left(
1-\beta\right)  }{L_{0}+\left(  k+n+m\right)  \beta}\right)  L_{k+m+n}\ ,
\end{equation}
plus cyclic permutations of $k,m,n$. \ Note the simplification when $\beta=0 $
or when $\beta=1$. \ Similarly, we compute
\begin{equation}
\left[  L_{p},L_{q},\left[  L_{k},L_{m},L_{n}\right]  \right]  =C~\left(
k-m\right)  \left(  m-n\right)  \left(  k-n\right)  \left(  p-q\right)
~\left(  1+\frac{\left(  k+m+n\right)  \left(  1-2\beta\right)  }
{L_{0}+\left(  k+m+n+p+q\right)  \beta}\right)  L_{k+m+n+p+q}\ .
\end{equation}
The case $\beta=1/2$ stands out as particularly tasteful.
\begin{equation}
\left.  \left[  L_{p},L_{q},\left[  L_{k},L_{m},L_{n}\right]  \right]
\right\vert _{\beta=1/2}=\frac{1}{4}\left(  k-m\right)  \left(  m-n\right)
\left(  k-n\right)  \left(  p-q\right)  L_{k+m+n+p+q}\ .
\end{equation}
This case allows us to quickly check the FI condition for the $L$s. \ We find
that it holds true.
\begin{equation}
\left.  \left[  L_{p},L_{q},\left[  L_{k},L_{m},L_{n}\right]  \right]
-\left[  \left[  L_{p},L_{q},L_{k}\right]  ,L_{m},L_{n}\right]  -\left[
L_{k},\left[  L_{p},L_{q},L_{m}\right]  ,L_{n}\right]  -\left[  L_{k}
,L_{m},\left[  L_{p},L_{q},L_{n}\right]  \right]  \right\vert _{\beta
=1/2}=0\ .
\end{equation}
Before checking the FI for other values of $\beta$, it is useful to first make
some general observations.

The 3-bracket of $L$s introduces a new operator given in the present
realization as a product. \ To check the FIs for the 3-algebra then requires
knowing how this new operator is affected under the action of a 3-bracket.
\ Since the 3-bracket is \emph{not} a derivation, in general, this requires
some new input, even when the new operator is realized as a product.
\ Therefore, we require several independent statements for the various
3-brackets. \ From the $su\left(  1,1\right)  $ enveloping algebra
expressions, we find\
\begin{align}
\left[  L_{k},L_{m},L_{n}\right]   &  =C~\left(  k-m\right)  \left(
m-n\right)  \left(  k-n\right)  ~M_{k+m+n}\ ,\nonumber\\
\left[  L_{p},L_{q},M_{k}\right]   &  =\left(  p-q\right)  ~\left(
L_{k+p+q}+\left(  1-2\beta\right)  k~M_{k+p+q}\right)  \ ,
\end{align}
where, in that realization,
\begin{equation}
M_{k}=\frac{1}{L_{0}+k\beta}~L_{k}=\frac{\Gamma\left(  L_{0}+\beta\right)
}{\Gamma\left(  L_{0}+\beta+k\right)  }\left(  L_{1}\right)  ^{k}\ .
\end{equation}
In particular, $M_{0}=1$. \ The Casimir-dependent factors are tantamount to
operators, of course, and will eventually be absorbed into normalizations, but
we leave them explicit for now. \ To close the algebra, we also need to
consider two additional 3-brackets: $\left[  L_{p},M_{q},M_{k}\right]  $\ and
$\left[  M_{p},M_{q},M_{k}\right]  $.

So we compute some more in the enveloping algebra, to find
\begin{equation}
\left[  M_{q},M_{k}\right]  =0\ ,\ \ \ \left[  L_{p},M_{q}\right]
=-qM_{p+q}\ , \label{L&MVirasoroWitt}
\end{equation}
and then,
\begin{align}
\left[  L_{p},M_{q},M_{k}\right]   &  =L_{p}\left[  M_{q},M_{k}\right]
+M_{k}\left[  L_{p},M_{q}\right]  -M_{q}\left[  L_{p},M_{k}\right] \nonumber\\
&  =-qM_{k}M_{p+q}+kM_{q}M_{p+k}\nonumber\\
&  =\left(  k-q\right)  M_{k+p+q}\ ,
\end{align}
upon using another identity valid in the $su\left(  1,1\right)  $ realization.
\ Namely,\footnote{An alternative presentation of the Lie algebra for the $L$s
and $M$s is given by taking generating elements $L_{0}$ and $M_{1}$, with the
condition $\left[  L_{0},M_{1}\right]  =-M_{1}$. \ Then $M_{n}\equiv\left(
M_{1}\right)  ^{n}$ and $L_{n}\equiv M_{n}\left(  L_{0}+n\left(
\beta-1\right)  \right)  $ leads to the algebra (\ref{VirasoroWitt}),
(\ref{L&MVirasoroWitt}). \ From this it is clear the $L$s depend on $\beta$,
but the $M$s do not.} \
\begin{equation}
M_{k}M_{p+q}=M_{k+p+q}\ .
\end{equation}
Thus we arrive at the remaining 3-brackets.
\begin{equation}
\left[  M_{p},M_{q},M_{k}\right]  =0\ ,\ \ \ \left[  L_{p},M_{q},M_{k}\right]
=\left(  k-q\right)  ~M_{k+p+q}\ .
\end{equation}
The complete 3-algebra found through use of the $su\left(  1,1\right)  $
enveloping algebra is then
\begin{gather}
\left[  L_{k},L_{m},L_{n}\right]  =C~\left(  k-m\right)  \left(  m-n\right)
\left(  k-n\right)  ~M_{k+m+n}\ ,\nonumber\\
\left[  L_{p},L_{q},M_{k}\right]  =\left(  p-q\right)  ~\left(  L_{k+p+q}
+\left(  1-2\beta\right)  k~M_{k+p+q}\right)  \ ,\nonumber\\
\left[  L_{p},M_{q},M_{k}\right]  =\left(  k-q\right)  ~M_{k+p+q}
\ ,\nonumber\\
\left[  M_{p},M_{q},M_{k}\right]  =0\ . \label{L&M}
\end{gather}
In addition, the $su\left(  1,1\right)  $ realization gives the interesting
result that all higher N-brackets (i.e. totally antisymmetrized products of N
operators) are null. \ This follows from explicit calculation of the five
possible forms for 4-brackets, three of which exhibit nontrivial cancellations
of terms, to obtain
\begin{equation}
0=\left[  L_{j},L_{k},L_{m},L_{n}\right]  =\left[  M_{j},L_{k},L_{m}
,L_{n}\right]  =\left[  M_{j},M_{k},L_{m},L_{n}\right]  =\left[  M_{j}
,M_{k},M_{m},L_{n}\right]  =\left[  M_{j},M_{k},M_{m},M_{n}\right]  \ .
\end{equation}
Consequently, all 5-brackets vanish upon being resolved into 4-brackets
\cite{C}, etc. Thus, all $(N\geq4)$-brackets vanish for the $su\left(
1,1\right)  $ realization of this infinite algebra. \

From the first two relations in (\ref{L&M}) it is now straightforward to check
\begin{equation}
\left[  L_{p},L_{q},\left[  L_{k},L_{m},L_{n}\right]  \right]  =\left[
\left[  L_{p},L_{q},L_{k}\right]  ,L_{m},L_{n}\right]  +\left[  L_{k},\left[
L_{p},L_{q},L_{m}\right]  ,L_{n}\right]  +\left[  L_{k},L_{m},\left[
L_{p},L_{q},L_{n}\right]  \right]  \ , \label{LFI}
\end{equation}
for any value of $C$ (and $\beta$). \ But of course, there are more possible
FIs involving both $L$s and $M$s, and these should also be checked. \ We
proceed to do this, after a bit of stream-lining. \

The overall Casimir factor in the first relation of (\ref{L&M}) is easily
eliminated by rescaling the charges by a fourth root of the Casimir, as in the
original $su\left(  2\right)  $ example of Nambu: \ $Q_{k}\equiv\frac
{1}{\sqrt[4]{C}}L_{k}$, $R_{k}\equiv\sqrt[4]{C}M_{k}$. \ However, the
remaining Casimir-dependent factor in the second relation of (\ref{L&M}) (i.e.
a central charge $z\equiv\left(  1-2\beta\right)  /\sqrt{C}$ after the
rescalings) is \emph{not} so easily removed. \ In any case we now abstract
from the $su\left(  1,1\right)  $ enveloping algebra results the following.

\section{Virasoro-Witt 3-Algebra}

\begin{gather}
\left[  Q_{k},Q_{m},Q_{n}\right]  =\left(  k-m\right)  \left(  m-n\right)
\left(  k-n\right)  ~R_{k+m+n}\ ,\nonumber\\
\left[  Q_{p},Q_{q},R_{k}\right]  =\left(  p-q\right)  ~\left(  Q_{k+p+q}
+z~k~R_{k+p+q}\right)  \ ,\nonumber\\
\left[  Q_{p},R_{q},R_{k}\right]  =\left(  k-q\right)  ~R_{k+p+q}
\ ,\nonumber\\
\left[  R_{p},R_{q},R_{k}\right]  =0\ , \label{TernaryWitt}
\end{gather}
where the central charge $z$ is effectively a parameter. \ For generic values
of $z$, by direct application of this ternary algebra, we now find that
3-brackets acting on 3-brackets satisfy the usual Leibniz-like rules (FIs)
\emph{except} when only one $R$ is involved. \ There are two such exceptions
out of twelve 3-on-3 possibilities. \

In an obvious notation, the twelve FI possibilities stem from each of the following:

\hspace{-0.25in}$
\begin{array}
[c]{cccccc}
\lbrack R,R,[R,R,R]]\ , & [R,R,[Q,R,R]]\ , & [Q,R,[R,R,R]]\ , &
[R,R,[Q,Q,R]]\ , & [Q,R,[Q,R,R]]\ , & [Q,Q,[R,R,R]]\ ,\\
\lbrack Q,Q,[Q,Q,Q]]\ , & [Q,Q,[R,Q,Q]]\ , & [R,Q,[Q,Q,Q]]\ , &
[Q,Q,[R,R,Q]]\ , & [R,Q,[R,Q,Q]]\ , & [R,R,[Q,Q,Q]]\ .
\end{array}
$

\noindent Ten of the FIs hold and behave as Filippov and Leibniz would
dictate. \ For example, for any $z$, the 3-algebra (\ref{TernaryWitt}) gives
\begin{equation}
\left[  Q_{p},Q_{q},\left[  Q_{k},Q_{m},Q_{n}\right]  \right]  =\left[
\left[  Q_{p},Q_{q},Q_{k}\right]  ,Q_{m},Q_{n}\right]  +\left[  Q_{k},\left[
Q_{p},Q_{q},Q_{m}\right]  ,Q_{n}\right]  +\left[  Q_{k},Q_{m},\left[
Q_{p},Q_{q},Q_{n}\right]  \right]  \ ,
\end{equation}
as stated earlier in terms of $L$s. \ For another example,
\begin{equation}
\left[  R_{p},R_{q},\left[  Q_{k},Q_{m},Q_{n}\right]  \right]  =\left[
\left[  R_{p},R_{q},Q_{k}\right]  ,Q_{m},Q_{n}\right]  +\left[  Q_{k},\left[
R_{p},R_{q},Q_{m}\right]  ,Q_{n}\right]  +\left[  Q_{k},Q_{m},\left[
R_{p},R_{q},Q_{n}\right]  \right]  \ .
\end{equation}
From (\ref{TernaryWitt}) the LHS trivially vanishes in this case, while the
three terms on the RHS cancel. \

The two exceptions, which for generic $z$ do \emph{not} obey FI
conditions,\ give instead
\begin{gather}
\left[  Q_{p},Q_{q},\left[  Q_{k},Q_{m},R_{n}\right]  \right]  -\left[
\left[  Q_{p},Q_{q},Q_{k}\right]  ,Q_{m},R_{n}\right]  -\left[  Q_{k},\left[
Q_{p},Q_{q},Q_{m}\right]  ,R_{n}\right]  -\left[  Q_{k},Q_{m},\left[
Q_{p},Q_{q},R_{n}\right]  \right] \nonumber\\
=\left(  4+z^{2}\right)  \left(  p-q\right)  \left(  k-m\right)  \left(
m-p-q+k\right)  n~R_{k+m+n+p+q}\ ,\nonumber\\
\nonumber\\
\left[  Q_{p},R_{q},\left[  Q_{k},Q_{m},Q_{n}\right]  \right]  -\left[
\left[  Q_{p},R_{q},Q_{k}\right]  ,Q_{m},Q_{n}\right]  -\left[  Q_{k},\left[
Q_{p},R_{q},Q_{m}\right]  ,Q_{n}\right]  -\left[  Q_{k},Q_{m},\left[
Q_{p},R_{q},Q_{n}\right]  \right] \nonumber\\
=\left(  4+z^{2}\right)  \left(  n-k\right)  \left(  k-m\right)  \left(
m-n\right)  q~R_{k+m+n+p+q}\ . \label{FailureIsAnOption}
\end{gather}
Nevertheless, for the special cases $z=\pm2i$ the RHSs of
(\ref{FailureIsAnOption}) also vanish. \ Hence in these special cases all the
FIs hold for the algebra of (\ref{TernaryWitt}), making it a bona fide 3-algebra.

It is interesting that the special values $z=\pm2i$ are obtained in the
$su\left(  1,1\right)  $\ realization only in the \textquotedblleft
classical\textquotedblright\ limit of large Casimirs, $C=\beta\left(
1-\beta\right)  \rightarrow-\infty$, for which
\begin{equation}
z^{2}=\frac{\left(  1-2\beta\right)  ^{2}}{\beta\left(  1-\beta\right)
}~_{\overrightarrow{\beta\rightarrow\pm\infty}}~-4\ .
\end{equation}
Perhaps this removes some of the mystery surrounding the FIs, which are
\emph{all} true statements for the proposed Virasoro-Witt 3-algebra for these
special values of $z$, since the FIs are known to hold for classical Nambu
3-brackets (as in (\ref{ClassicalNambu3BracketAlgebraFIs}) above). \ In this
context, we note the coefficient on the RHS of the first relation in
(\ref{TernaryWitt}) is given by $-a\cdot\left(  b\times c\right)  $ for three
vectors $a=\left(  1,k,k^{2}\right)  $, $b=\left(  1,m,m^{2}\right)  $, and
$c=\left(  1,n,n^{2}\right)  $.

As emphasized in \cite{C} there is nothing fundamental about the FI conditions
so far as associativity is concerned. \ Generally these \textquotedblleft
identities\textquotedblright\ fail to hold due to quantum corrections for
associative operator algebras $\hbar$-deformed from the Jacobian-like limit of
the classical Nambu brackets (CNBs) to become full-fledged quantum Nambu
brackets (QNBs). \ Although the FIs fail for (\ref{FailureIsAnOption}) for
generic $z$, there is an alternative identity following only from
associativity of the charge multiplication. \ This alternate identity must
hold if the associative algebra is consistent. \ The identity is
\begin{align}
&  \left[  \left[  A,B,C\right]  ,D,E\right]  +\left[  \left[  A,D,E\right]
,B,C\right]  +\left[  \left[  D,B,E\right]  ,A,C\right]  +\left[  \left[
D,E,C\right]  ,A,B\right] \nonumber\\
&  -\left[  \left[  D,B,C\right]  ,A,E\right]  -\left[  \left[  E,B,C\right]
,D,A\right]  -\left[  \left[  A,D,C\right]  ,B,E\right] \nonumber\\
&  -\left[  \left[  A,E,C\right]  ,D,B\right]  -\left[  \left[  A,B,D\right]
,C,E\right]  -\left[  \left[  A,B,E\right]  ,D,C\right] \nonumber\\
&  =3\left[  A,B,C,D,E\right]  \;.
\end{align}
This is the prototypical generalization of the Jacobi identity for odd QNBs
\cite{C}, and like the Jacobi identity, it is antisymmetric in all of its
elements. \ The RHS here is an \textquotedblleft
inhomogeneity\textquotedblright\ that illustrates a more general result:
\ \textit{The totally antisymmetrized action of odd }$n$\textit{\ QNBs on
other odd }$n$\textit{\ QNBs results in }$\left(  2n-1\right)  $
\textit{-brackets.} \ For the case at hand, by explicit calculation using
(\ref{TernaryWitt}), we find for any value of $z$,
\begin{align}
&  \left[  Q_{p},Q_{q},\left[  Q_{k},Q_{m},R_{n}\right]  \right]  +\left[
Q_{m},R_{n},\left[  Q_{k},Q_{p},Q_{q}\right]  \right]  +\left[  Q_{k}
,R_{n},\left[  Q_{p},Q_{m},Q_{q}\right]  \right]  +\left[  Q_{k},Q_{m},\left[
Q_{p},Q_{q},R_{n}\right]  \right] \nonumber\\
&  -\left[  Q_{k},Q_{q},\left[  Q_{p},Q_{m},R_{n}\right]  \right]  -\left[
Q_{p},Q_{k},\left[  Q_{q},Q_{m},R_{n}\right]  \right]  -\left[  Q_{m}
,Q_{q},\left[  Q_{k},Q_{p},R_{n}\right]  \right] \nonumber\\
&  -\left[  Q_{p},Q_{m},\left[  Q_{k},Q_{q},R_{n}\right]  \right]  -\left[
R_{n},Q_{q},\left[  Q_{k},Q_{m},Q_{p}\right]  \right]  -\left[  Q_{p}
,R_{n},\left[  Q_{k},Q_{m},Q_{q}\right]  \right] \nonumber\\
&  =0\ .
\end{align}
Remarkably, there is \emph{no inhomogeneity} for this or any other 3-on-3
situation computed using (\ref{TernaryWitt}). Perhaps this is not too
surprising given that all $(N\geq4)$-brackets vanish for the $su\left(
1,1\right)  $ realization that led to (\ref{TernaryWitt}), although in any
other realization it would be necessary to specify all the 5-brackets, either
by direct calculation where possible, or by definition if necessary. Still, it
is reassuring that the proposed 3-algebra (\ref{TernaryWitt}) satisfies these
associativity-required consistency checks.

\section{Discussion}

Just as there are a countably infinite number of copies of $su\left(
1,1\right)  $ embedded in the centerless Virasoro-Witt algebra, so there are
an infinite number of BL algebras embedded in the (complexified) ternary
Virasoro-Witt algebra proposed here. \ At any given level, $L_{\pm n}/\sqrt
{n}$ and $L_{0}$ obey the $su\left(  1,1\right)  $ commutation relations
(\ref{su(1,1)}), with invariant $C_{n}=L_{+n}L_{-n}-\left(  L_{0}+n\right)
L_{0}$. \ The construction of the BL algebra at that level then proceeds as in
(\ref{NambuSU2}) and (\ref{NambuA4}) above, after complexifying the level's
$su\left(  1,1\right)  $ to obtain $su\left(  2\right)  $ in the well-known way.

It is a straightforward extension to include central charges in the Virasoro
algebra, as well as the $L$ and $M$ commutators,
\begin{equation}
\left[  L_{n},L_{m}\right]  =\left(  n-m\right)  L_{n+m}+cn^{3}\delta
_{n,-m}\ ,\ \ \ \left[  L_{n},M_{k}\right]  =-kM_{k+n}+bn^{2}\delta_{k,-n}\ ,
\end{equation}
where $b$ and $c$ are central, and to investigate their consequences for the
3-algebra. \ This will be discussed in detail elsewhere. \ Similar remarks
apply to the supersymmetric extension of (\ref{TernaryWitt}).

The astute reader will have noticed that (\ref{VirasoroWitt}) and
(\ref{L&MVirasoroWitt})\ form a sub-algebra of the Schr\"{o}dinger-Virasoro
algebra \cite{SV}. \ The extension of our 3-bracket results to include the
remaining charges of that larger algebra could be of interest.

Finally, we re-emphasize that our construction leading to (\ref{TernaryWitt})
used only 3-brackets defined as totally antisymmetrized operator products:
\ $\left[  A,B,C\right]  \equiv ABC-BAC+BCA-CBA+CAB-ACB$. \ Any other
definition of the 3-brackets might lead to a ternary algebra different from
that proposed here.

\paragraph{Acknowledgements}

This work was supported by NSF Award 0555603 and by the US Department of
Energy, Division of High Energy Physics, Contract DE-AC02-06CH11357.

config: arxiv


TITLE: Is it possible to derive at what time during a cook process a certain temperature was reached?
QUESTION [0 upvotes]: I work at a frozen foods manufacturer, and we have a particular lot of product that is currently being held pending inspection, due to new regulatory requirements.  To keep it concise, we need to somehow demonstrate that the product internal temperature met and sustained a particular temperature (140°F | 60°C) for 42 seconds during the cook process.
The product is -- to keep it simplified -- mostly consisting of ground chicken meat (which I believe has a heat capacity of 0.88 btu/(lboF) | 3.68 kJ/(kgoC).  The product is heated via a steam tunnel, over the period of 4 minutes and 55 seconds.  The product is ≈ 40°F | 4.4°C when at the start of the tunnel, and comes out at ≈ 151.6°F | 66.4°C, giving a delta of 111.6°F | 44.2°C.  The product mass per unit is 0.024 kg.
Given the above information, would we be able to derive the chronological point at which the product reaches 140°F?

REPLY [0 votes]: I just wanted to come back and update this, as I realized after-the-fact there was a much simpler solution to the above problem rather than making complex calculations:

Maintain the same steam “power”, belt velocity, etc.; confirm all other factors remain the same as control sample (using the detained export product as your referenced control data).
Increase the belt velocity so that total travel time through steam tunnel is reduced by ≥ 42 seconds (e.g., 4B Validation data showed travel time ≈ 4:55 = 295 seconds, then we would adjust until travel time is less than or equal to 253 seconds, etc.).
If the tunnel exit product temperature comes out to ≥ 140°F | 60°C, then we can safely assume product meets the time & temperature requirement with the standard belt velocity.