text:
\begin{document}

\title{The Euclidean Algorithm for Generalized Minimum Distance Decoding of Reed-Solomon Codes}

\author{\IEEEauthorblockN{Sabine Kampf and Martin Bossert}
\IEEEauthorblockA{Institute of Telecommunications and Applied Information Theory\\
University of Ulm, Germany\\
\texttt{\{sabine.kampf | martin.bossert\}@uni-ulm.de}}
\thanks{This work was supported by the German Research Council "Deutsche Forschungsgemeinschaft" (DFG) under Grant No. Bo867/22.}}

\maketitle

\begin{abstract}
This paper presents a method to merge Generalized Minimum Distance decoding of Reed-Solomon codes with the extended Euclidean algorithm. By merge, we mean that the steps taken to perform the Generalized Minimum Distance decoding are similar to those performed by the extended Euclidean algorithm. The resulting algorithm has a complexity of $\order(n^2)$.
\end{abstract}

\section{Introduction}
In 1996, Ralf K\"otter presented a fast algorithm for Generalized Minimum Distance (GMD) decoding of Reed-Solomon (RS) codes with a complexity of $\order(n^2)$ \cite{Koetter_GMD}. This algorithm is an extension of the well-known Berlekamp-Massey algorithm (BMA), that has been applied to decoding of RS codes up to half the minimum distance since the late 1960s \cite{MacWilliams}. Another algorithm that is often used to decode RS codes was first described by Sugiyama et. al. in 1975 \cite{Sugiyama}, and is based on the extended Euclidean algorithm (EEA). Recently, there have been attempts to perform GMD decoding, also with a complexity of $\order(n^2)$, using polynomials that are obtained from the extended Euclidean algorithm \cite{scc_wir}, \cite{isit2010}. Since the BMA and EEA are known to be equivalent in the decoding of RS codes up to half the minimum distance, it is interesting to try to find an extension to the EEA that is equivalent to K\"otters extension to the BMA. In this paper, we present such an extension.

The paper is organized as follows: In the next section, we shortly introduce RS codes as well as GMD decoding. In Section \ref{sec:EEA}, we first recall the EEA and how it is used for decoding RS codes up to half the minimum distance. Then we show, which of polynomials obtained are used as a basis for the GMD extension, and how to extend the EEA to GMD decoding. Finally, we shortly discuss how to modify our approach so that the selection of the best solution does not decrease the complexity. The conclusion follows in Section \ref{sec:summary}.

\section{Notations and Definitions}
\subsection{RS Codes and Key Equation} \label{ssec:RSKE}
To define an $\mathcal{RS} (n, k, d)$ code over $GF(q)$ with $R = \frac{k}{n}$ and minimum distance $d=n-k+1$, let $\alpha \in GF(q)$ denote an element of order $n$, and $\alpha^j$ the $j$th power of this element. Later, the elements $\alpha_i$ will denote the $i$th element according to a (implicitly) given indexing. A polynomial $c(x)=c_0+c_1x+\dots+c_{n-1}x^{n-1}$ with coefficients in $GF(q)$ is a valid codeword if the polynomial $C(x)$, whose coefficients $C_j$ are calculated by the discrete Fourier transform (DFT), i.e.
\begin{equation}
C_j = c(\alpha^{j}), \qquad \, j=0,\dots,n-1,
\end{equation}
is zero at the first $n-k=d-1$ coefficients, hence
\begin{equation}
C(x)=C_{d-1}x^{d-1}+\dots+C_{n-1}x^{n-1}.
\label{eqn:cwdef}
\end{equation}
We take the $C_i \in GF(q)$ to be the information symbols. The codeword $c(x)$ corresponding to the information word $C(x)$ is obtained through the inverse discrete Fourier transform (IDFT):
\begin{equation}
c_i = n^{-1}\cdot C(\alpha^{-i}),\quad i=0,\dots,n-1.
\end{equation}
Throughout this paper, capital letters denote polynomials in the spectral domain, and small letters their correspondences in the time domain.

The transmitted codeword is corrupted by an additive error $e(x)$ of Hamming weight $t$, and the received word is $r(x)=c(x)+e(x)$. For decoding, calculate the syndrome $S(x)$:
\begin{equation}
S(x) = R(x) \mod x^{d-1} = E(x) \mod x^{d-1}.
\end{equation}
This syndrome is used in the \textit{key equation} for decoding RS codes:
\begin{equation} \label{eqn:key_eq}
-\Omega(x) \equiv \Lambda(x)\cdot S(x)  \mod x^{d-1},
\end{equation}
with the error locator polynomial $\Lambda(x)$ and the error evaluator polynomial $\Omega(x)$. These two polynomials satisfy the important degree relation:
\begin{equation}\label{eqn:deg_omega}
\deg\Omega(x) < \deg \Lambda(x) =t.
\end{equation}
\subsection{GMD Decoding} \label{ssec:GMD}
First proposed by Forney in 1966 \cite{Forney_GMD}, the idea of GMD decoding is to allow soft-decision decoding of algebraically decodable codes by performing $m+1$ decoding trials, each with a different number of positions being erased. In each trial, the decoder may either output an error locator polynomial as defined in \eqref{eqn:key_eq}, or declare a decoding failure. Consequently, a list of up to $m+1$ candidate error locator polynomials is obtained, and the decoder should select one of these candidate words, that is best according to a certain criterion.

In order to determine the set $\mx_j$ of erased positions in iteration $j$, the decoder needs to be supplied with reliability information regarding the decisions made. Reliability is defined intuitively, i.e. the less reliable a decision, the more probable it is that the received value is incorrect. Therefore, the least reliable positions are erased first. It is known, cf. e.g. \cite{Koetter_GMD}, that decoding is possible if the number of errors $t$ and the number of erasures $\epsilon$ fulfill
\begin{equation}
2t+\epsilon < d.
\label{eqn:2tpeltd}
\end{equation}
We choose $|\mx_0|=0$ (i.e. we start with decoding errors only), $|\mx_1|=2$, $|\mx_2|=4$, \dots, $|\mx_{m}|=2\cdot \dhalf$, and further require $\mx_j \subset \mx_{j+1}$. Before, $\Lambda(x)$ was defined to be an error locator polynomial. For our algorithm, we slightly modify this and take $\Lambda(x)$ to be a joint error-erasure locator polynomial. In each iteration of the GMD decoding process, we have two additional erasures. On the other hand, according to \eqref{eqn:2tpeltd} we can correct one error less than in the iteration before, and so we find that the degree of our candidate error locator polynomial should increase by $1$ in each iteration. Due to this fact, we state our decoding problem as follows:
\begin{problem}
In each iteration of our GMD decoding, we want to find an error locator polynomial $\Lambda(x)$, that fulfills \eqref{eqn:key_eq} and \eqref{eqn:deg_omega}, of a \emph{given} degree with certain prescribed zeros.
\end{problem}
This is different to the problem statement of K\"otter, where the polynomial of \emph{smallest} degree is to be found. It will be seen later that in some situations, it is not possible to fulfill the requirements given in our problem statement.

In ``classical'' GMD decoding, the iterations are independent of each other. In each iteration, one first determines the erasure locator polynomial. Due to the erasures, the minimum distance of the RS code is virtually decreased, and the decoder tries to find an error locator from the shorter syndrome. Because the complexity of decoding with the EEA
is $\order(n^2)$, the overall decoding complexity of this approach is $\order(n^3)$. However, the decoding complexity can be decreased if erasing of positions is performed incrementally, i.e. the decoding result of iteration $j$ is used together with the additional erasures in $\mx_{j+1}\setminus\mx_{j}$ to yield the decoding result of iteration $j+1$. The first such method was presented in \cite{Koetter_GMD}, the complexity of his approach being $\order(n^2)$ (actually, K\"otter claims the complexity to be $\order(nd)$, but since in general $d=\order(n)$, this is asymptotically the same). His algorithm is an extension of the BMA. However, it is known that decoding up to $\dhalf$ with the BMA and the EEA are equivalent. Therefore, we want to show that it is possible to modify the EEA, such that GMD decoding is merged into the decoding process.

\section{The Extended Euclidean Algorithm} \label{sec:EEA}
The possibility of applying the EEA in the decoding of RS codes up to $\dhalf$ was first presented by Sugiyama~et.~al. in 1975 \cite{Sugiyama}. This decoding approach will be shortly reviewed in the first part of this section, as it is the basis for the extended decoding approach.

In the second and third part of this section, we will present an algorithm that integrates GMD decoding into the EEA. At the end of the third part, we show how to combine the formulas given to form the algorithm.

\subsection{Decoding up to $\dhalf$} \label{ssec:EEAclass}
The EEA uses input polynomials $A(x)=\rpolx{0}$ and $B(x)=\rpolx{-1}$ to recursively calculate a series of quotient polynomials $\qpolx{j+1}$ and remainders $\rpolx{j+1}$ that fulfill:
\begin{equation}
\rpolx{j+1}=\rpolx{j-1} - \qpolx{j+1}\cdot\rpolx{j},
\label{eqn:EEAremrec}
\end{equation}
with $\deg \rpolx{j+1}<\deg \rpolx{j}$. The algorithm stops when $\rpolx{j+1}=0$.
From the quotient polynomials, a series of auxiliary polynomials $\upolx{j+1}$ is obtained recursively, namely
\begin{equation}
\upolx{j+1}=\upolx{j-1} - \qpolx{j+1}\cdot\upolx{j},
\label{eqn:EEAauxrec}
\end{equation}
where $\upolx{-1}=0$ and $\upolx{0}=1$. The degrees of these auxiliary polynomials are given by
\begin{equation}
\deg \upolx{j} = \sum_{i=1}^{j} \deg \qpolx{i}.
\end{equation}
Further, these polynomials fulfill the relation
\begin{equation}
\upolx{j}\cdot A(x) = \rpolx{j} \mod B(x),
\end{equation}
which has a form similar to the key equation \reff{eqn:key_eq}. This implies that the EEA can be used for solving \reff{eqn:key_eq}.
Hence by setting $A(x) = S(x)$ and $B(x)=x^{d-1}$, in some steps of the EEA, whenever
\begin{equation}
\deg \upolx{j} > \deg \rpolx{j},
\label{eqn:EEAstopcond}
\end{equation}
we obtain polynomials fulfilling both \reff{eqn:key_eq} and \reff{eqn:deg_omega}.
If the number of errors $t$, i.e. the number of nonzero coefficients in $e(x)$, is limited by $t\leq \dhalf$, then it is known \cite{Sugiyama} that $t = \deg \upolx{j}$, $\Lambda(x) = \upolx{j}$ and $\Omega(x) = -\rpolx{j}$ where $j$ is the smallest index for which \reff{eqn:EEAstopcond} is fulfilled.

\subsection{From Classical Decoding to GMD Extension} \label{ssec:ubergang}
In \cite{isit2010} it was shown that $\cval{j+1}$, the number of coefficients of $\qpolx{j+1}$ that can be determined from the syndrome, is given by
\begin{equation}
\cval{j+1} = \deg \rpolx{j} - \deg \upolx{j} + 1.
\end{equation}
Further, \eqref{eqn:EEAremrec} yields that
\begin{equation}
\deg \qpolx{j+1} = \deg \rpolx{j-1}-\deg \rpolx{j}.
\end{equation}
As long as $\deg \qpolx{j+1} + 1 \leq \cval{j+1}$, the quotient polynomials are calculated as in the classical decoding procedure. This can be done as long as $\deg \qpolx{j+1} \leq \dhalf$ \cite{isit2010}. If $\deg \qpolx{j+1} + 1 > \cval{j+1}$, we switch to the GMD extension described in the next paragraph. In order to set the initial polynomials for the extension, we have to distinguish two cases: If $\cval{j+1} \leq 0$, then no coefficient of the next quotient polynomial can be determined. Hence, we use
\begin{equation}
\upolx{j}=:\DPx{1, 0} \ \textnormal{and} \ \upolx{j-1}=:\DPx{2, 0}.
\label{eqn:dpx0def}
\end{equation}
On the other hand, if $\cval{j+1}>0$, then it is possible to determine the upmost $\cval{j+1}$ coefficients of $\qpolx{j+1}$ - we will call this part $\qhpolx{1}$, because it belongs to the ``quotient'' polynomial determined in the first iteration of the GMD extension - and it would be unwise to discard this information. Simulations have shown, that the best performance is achieved if we set $\DPx{1, 0}:=\upolx{j}$ and $\DPx{2, 0}:=\upolx{j-1}-\qhpolx{1}\upolx{j}$. Unfortunately, we do not know yet why this performs better than using the definitions in \eqref{eqn:dpx0def} and just taking $\qhpolx{1}$ into account only in the first iteration.

\subsection{GMD Extension} \label{ssec:GMDext}
In this section, we again use $j$ to index the iterations done in the GMD part of our algorithm. However, we count those iterations independently of the ones performed by the EEA before. Because the decoding up to $\dhalf$ is just decoding without erasures, $j$ now corresponds to the iterations defined in Section \ref{ssec:GMD}.
The basic idea is the following: We start with decoding up to half the minimum distance, as described before. Once the polynomials $\upolx{j}$ can no longer be determined by the syndrome and we switch to the GMD extension, the decoder starts to determine the ``quotient'' polynomials $\qpolx{j}$ with the help of the reliability information given. Namely, two positions $\alpha_1$ and  $\alpha_2$ are erased in each iteration, where
\begin{equation}
\left\{\alpha_1, \alpha_2\right\}=\mx_{j+1}\setminus\mx_{j}.
\end{equation}
Comparing \eqref{eqn:dpx0def} to \eqref{eqn:EEAauxrec}, we set the equation to be solved by the GMD extension to be
\begin{equation}
\DPx{1, j+1}=\DPx{2, j}-\qpolx{j}\DPx{1, j}.
\label{eqn:EEAexteqn}
\end{equation}
Consequently, $\qpolx{j}$ is determined in such a way that
\begin{equation}
\DPol{1, j+1}(\alpha_1)=\DPol{1, j+1}(\alpha_2)=0.
\end{equation}
Now, the polynomials $\DPx{1}$ take the role of $u(x)$ in the classical decoding up to $\dhalf$, i.e. they form the list of candidate error locator polynomials from which the decoding result is chosen. Note that the erased positions in one iteration are always named $\alpha_1$ and $\alpha_2$, there is no separate indication of the iteration. It should always be clear from the context, to which pair of positions the two variables refer.

As mentioned above, we want the degree of the polynomial $\DPx{1}$ to increase by one in each iteration. In order to ensure this degree, we force $\alpha_1$ and $\alpha_2$ to be zeros of the polynomial
\begin{equation}
\DPx{1,j+1}=a\DPx{2, j}-(x+b)\cdot\DPx{1, j}.
\label{eqn:update_wd01}
\end{equation}
Thus, we have a system of two linear equations and two unknowns, so we can give the general solution
\begin{equation}
\begin{split}
a&=\frac{\DPol{1,j}(\alpha_1)\DPol{1,j}(\alpha_2)(\alpha_1-\alpha_2)}{\DPol{1,j}(\alpha_1)\DPol{2,j}(\alpha_2)-\DPol{1,j}(\alpha_2)\DPol{2,j}(\alpha_1)},\\
b&=\frac{\DPol{1,j}(\alpha_1)\DPol{2,j}(\alpha_2)\alpha_1-\DPol{1,j}(\alpha_2)\DPol{2,j}(\alpha_1)\alpha_2}{\DPol{1,j}(\alpha_1)\DPol{2,j}(\alpha_2)-\DPol{1,j}(\alpha_2)\DPol{2,j}(\alpha_1)}.
\end{split}
\label{eqn:sol_u01}
\end{equation}
Because we do not require the polynomials to be monic, we can avoid the division in the actual implementation. However, for the analysis of the algorithm we prefer to use the formulas given as they provide the easier insight regarding the cases when the intended updating is not possible.

Of course, $\DPx{2}$ also needs to be updated to enforce the required zeros, since otherwise it will not be guaranteed in further iterations that $\DPx{1}$ still has zeros at \emph{all} positions in the corresponding erasure set $\mx_j$.
The updating of $\DPx{2}$ is performed by
\begin{equation}
\DPx{2,j+1}=\DPx{1, j}-(a\cdot x+b)\cdot\DPx{2, j}.
\label{eqn:update_wd02}
\end{equation}
$\DPx{1, j}$ is multiplied by $1$ because we want to have $\deg \DPx{2, j+1}=\deg \DPx{1, j}$. This is derived from the fact that in \eqref{eqn:EEAauxrec}, the same auxiliary polynomial is used twice, once in the role of $\DPx{1}$ and in the next iteration in that of $\DPx{2}$.
The correct zeros are obtained if
\begin{equation}
\begin{split}
a&= \frac{\da\ddaa-\daa\dda}{\dda\ddaa(\alpha_1-\alpha_2)},\\
b&= \frac{\daa\dda\alpha_1-\da\ddaa\alpha_2}{\dda\ddaa(\alpha_1-\alpha_2)}.
\end{split}
\label{eqn:sol_u02}
\end{equation}
Updating according to these two rules will be called regular updating. It is directly seen, that the solutions in \eqref{eqn:sol_u01} and \eqref{eqn:sol_u02} do not always exist: Regular updating of $\DPx{1}$ is not possible if $\DPol{1,j}(\alpha_1)\DPol{2,j}(\alpha_2)-\DPol{1,j}(\alpha_2)\DPol{2,j}(\alpha_1)=0$. This happens if
\begin{equation}
\DPol{1,j}(\alpha_1)=\DPol{1,j}(\alpha_2)=0
\label{eqn:fail1}
\end{equation}
or
\begin{equation}
\DPol{2,j}(\alpha_1)=\DPol{2,j}(\alpha_2)=0,
\label{eqn:fail2}
\end{equation}
and rarely also in other cases when the terms in the denominator of \eqref{eqn:sol_u01} are all not zero, but the denominator is. For these cases, we allow the algorithm to update $\DPx{1}$ in such a way that $\deg \DPx{1, j+1} \neq \deg \DPx{1, j}+1$. However, we keep track of this process, and perform a compensation step in some later iteration $j+j_0$ such that we get $\deg \DPx{1, j+j_0} = \deg \DPx{1, j}+j_0$. We try to choose $j_0$ as small as possible, and in most situations it is actually possible to have $j_0=2$, hence we do not intensively study the case when compensation is not immediately possible.
Additionally, if $\dda=0$ or $\ddaa=0$, the updating of $\DPx{2}$ has to be performed in a different way. Yet a closer look at the polynomials shows, that in this case it is sufficient to set $\DPx{2, j+1}=(x-\alpha_1)\DPx{2, j}$ if $\ddaa=0$ and vice versa. This might result in a polynomial of smaller degree than the intended one, but it is more important that the degree of the polynomial is not too large.

Before we study the updating procedures in the special cases indicated above, it should be noted that no further cases than the ones described before need to be distinguished. Because the auxiliary polynomials $\upolx{j-1}$ and $\upolx{j}$ fulfill the relation \cite{Sugiyama}
\begin{equation}
\upolx{j}\vpolx{j-1}-\upolx{j-1}\vpolx{j}=\pm 1,
\label{eqn:gcdeq1}
\end{equation}
where the $\vpolx{j}$ can also be calculated recursively in the EEA, but are not needed for decoding RS codes. The greatest common divisor (gcd) of two polynomials calculated in consecutive iterations of the EEA is $1$, and so this is true for $\DPx{1,0}$ and $\DPx{2, 0}$. Of course, in the further iterations, the gcd of $\DPx{1, j}$ and $\DPx{2, j}$ will at least have roots at all positions in $\mx_j$. Indeed, close examination shows that the gcd contains exactly these roots and no further common factor.

To illustrate this with an example, we will explicitly calculate the gcd for regular updating in the first GMD iteration. For the further iterations as well as the other cases described later on, this claim can be verified in a similar manner.
First, we take a look at the proof for \eqref{eqn:gcdeq1} as given in \cite{Sugiyama}. There, the calculation of the auxiliary polynomials is written in matrix form as
\begin{equation}
\begin{pmatrix}
\upol{j} & \upol{j-1} \\
\vpol{j} & \vpol{j-1}
\end{pmatrix}
= \begin{pmatrix}\qpol{1}&1\\1&0\end{pmatrix}\cdot \begin{pmatrix}\qpol{2}&1\\1&0\end{pmatrix}\dots \begin{pmatrix}\qpol{j}&1\\1&0\end{pmatrix}
\label{eqn:proofgcold}
\end{equation}
and taking the determinant on both sides immediately gives the relation \eqref{eqn:gcdeq1}. To extend this to our approach, we also use the matrix representation, namely
\begin{equation}
\begin{pmatrix}
\DPol{1, j} & \DPol{2, j} \\
p^{(1)}(x) & p^{(2)}(x)
\end{pmatrix}= \begin{pmatrix}
\DPol{1, j-1} & \DPol{2, j-1} \\
p^{(3)}(x) & p^{(4)}(x)
\end{pmatrix}\cdot \begin{pmatrix}\qpol{j}&1\\a&\qbpol{j}\end{pmatrix},
\label{eqn:proofgc1}
\end{equation}
with polynomials $p^{(i)}(x)$ that are not used in our algorithm. For the first iteration, i.e. $j=1$, we substitute \eqref{eqn:proofgcold} for the last step of the classical decoding procedure into \eqref{eqn:proofgc1}, and by taking the determinant we obtain
\begin{equation}
\upolx{j}p^{(2)}(x)-\upolx{j-1}p^{(1)}(x)=\qpolx{1}\cdot\qbpolx{1}-a,
\label{eqn:proofgc2}
\end{equation}
the right hand side possibly multiplied by $-1$. Since we know that the gcd includes the factors $(x-\alpha_1)$ and $(x-\alpha_2)$, the gcd cannot have degree less than $2$. On the other hand, the right hand side of \eqref{eqn:proofgc2} is a polynomial of degree $2$, and it is a multiple of the gcd. Hence the gcd has degree at most $2$, so it is immediately clear that the gcd consists of exactly the two factors given, in particular no root at any value $\alpha_i$ that is to be erased in a later iteration, is contained in the gcd.

Now we will turn to the special cases, where the updating rule \eqref{eqn:update_wd01} cannot be used. First, we study the case given in \eqref{eqn:fail2}. Due to the fact that $\DPx{1}$ and $\DPx{2}$ are coprime, we have $\DPol{1,j}(\alpha_1)\neq 0, \DPol{1,j}(\alpha_2)\neq 0$. In such a case, $(x+b)\DPx{1, j}$ can only have a root at one of the required zeros, and adding a multiple of $\DPx{2, j}$ cannot bring either position to zero. Therefore, we choose to set $\deg \DPx{1, j+1}=\deg \DPx{1, j}+2$. Then it is easy to find the updating rules
\begin{equation}
\begin{split}
\DPx{1, j+1} &= (x-\alpha_1)(x-\alpha_2)\DPx{1, j}, \\
\DPx{2, j+1} &= \DPx{2, j}.
\end{split}
\label{eqn:update_wd+1}
\end{equation}
In the next iteration, the decoder should try to compensate for this decision. The thought leading to the result is the following: If we check how the polynomial $\DPx{1, j+2}$ is composed of $\DPx{1, j}$ and $\DPx{2, j}$ for regular updating, we find that the first is multiplied by a polynomial of degree $2$ and the latter by a polynomial of degree $1$. We therefore set
\begin{equation}
\begin{split}
\DPx{1, j+2} &= (x+a)\DPx{2, j+1}+b\DPx{1, j+1}, \\
\DPx{2, j+2} &= (x-\alpha_1)(x-\alpha_2)\DPx{2, j+1},
\end{split}
\label{eqn:comp_wd+1}
\end{equation}
which in combination with \eqref{eqn:update_wd+1} gives the desired degrees for two updating steps.
$\DPx{1, j+2}$ has the desired zeros if
\begin{equation}
\begin{split}
a&=\frac{\DPol{1}(\alpha_1)\DPol{2}(\alpha_2)\alpha_1-\DPol{1}(\alpha_2)\DPol{2}(\alpha_1)\alpha_2}{\DPol{1}(\alpha_1)\DPol{2}(\alpha_2)-\DPol{1}(\alpha_2)\DPol{2}(\alpha_1)},\\
b&=\frac{\DPol{2}(\alpha_1)\DPol{2}(\alpha_2)(\alpha_1-\alpha_2)}{\DPol{1}(\alpha_1)\DPol{2}(\alpha_2)-\DPol{1}(\alpha_2)\DPol{2}(\alpha_1)};
\end{split}
\label{eqn:comp_wd+12}
\end{equation}
we abbreviated $\DPol{1}=\DPol{1, j+1}$ and $\DPol{2}=\DPol{2, j+1}$.

If $\DPol{1,j}(\alpha_1)\DPol{2,j}(\alpha_2)-\DPol{1,j}(\alpha_2)\DPol{2,j}(\alpha_1)=0$ without any of the involved terms being zero, we perform the update of $\DPx{1}$ as in \eqref{eqn:update_wd+1}. However, the updating of $\DPx{2}$ still is done according to \eqref{eqn:update_wd02}, since (of course) $\DPx{2, j}$ does not yet have the required zeros. After the compensation step, $\DPx{2}$ will then have the same degree as $\DPx{1}$. However, recursive substitution, in order to get $\DPx{1}$ in dependence of $\DPx{1, 0}$ and $\DPx{2, 0}$ shows that these polynomials are multiplied by the intended degree in $\DPx{1}$, so this fact does not cause major problems, and simulations have shown that correct decoding is actually achieved with this setup.

The last special case that needs to be taken into account is $\DPol{1,j}(\alpha_1)=\DPol{1,j}(\alpha_2)=0$. Here, there is no need to update $\DPx{1}$, but forcing the zeros in $\DPx{2, j+1}$ is not possible with the formula given in \eqref{eqn:update_wd02}: The solution in \eqref{eqn:sol_u02} is valid, but the fact that $a=b=0$ implies that $\DPx{2, j}$ is discarded, hence all further solutions would be multiples of $\DPx{1, j}$, which is not wanted. Therefore, we use the updating rules
\begin{equation}
\begin{split}
\DPx{1, j+1} &= \DPx{1, j}, \\
\DPx{2, j+1} &= (x-\alpha_1)(x-\alpha_2)\DPx{2, j}.
\end{split}
\label{eqn:update_wd-1}
\end{equation}

The compensation step then is given as
\begin{equation}
\begin{split}
\DPx{1, j+2} &= (x-\alpha_1)(x-\alpha_2)\DPx{1, j+1}, \\
\DPx{2, j+2} &= a\DPx{2, j+1}-(x+b)\DPx{1, j+1},
\end{split}
\label{eqn:comp_wd-1}
\end{equation}
where
\begin{equation}
\begin{split}
a&= \frac{\da\daa(\alpha_1-\alpha_2)}{\daa\dda-\da\ddaa} \\
b&= \frac{\da\ddaa\alpha_1-\daa\dda\alpha_2}{\daa\dda-\da\ddaa}.
\end{split}
\label{eqn:comp_wd-12}
\end{equation}
Performing the compensation steps, both that in \eqref{eqn:comp_wd+1} and in \eqref{eqn:comp_wd-1} isn't always possible either. The situations in which compensation fails are actually the same as those where regular updating fails. Consequently, the same special updating rules are used again in this cases. If the same rule is used twice, two compensation steps are required later on. On the other hand, \eqref{eqn:update_wd+1} and \eqref{eqn:update_wd-1} serve as compensation steps for each other. Further, compensation is possible but should not be performed in \eqref{eqn:comp_wd+1} if $\DPol{2, j+1}(\alpha_1)$ or $\DPol{2, j+1}(\alpha_2)$ is zero: In this case, by performing the compensation step, one discards the polynomial $\DPx{1, j+1}$, and all error locator polynomials obtained further are multiples of $\DPx{2, j+1}$ which is not wanted. Therefore, it is better to perform regular updating in this situation and try compensation in the next iteration. The same holds if the compensation in \eqref{eqn:comp_wd-1} is to be performed and $\DPol{1, j+1}(\alpha_1)=0$ or $\DPol{1, j+1}(\alpha_2)=0$.

The situation in these special cases is a little different if $\qhpolx{1}$ exists. As mentioned before, the updating can be written to avoid the division in the calculation of the coefficients - such a case is equivalent to multiplying both $\DPx{1, j}$ and $\DPx{2, j}$ by a constant. As a result, $\DPx{1, j+1}=c\DPx{2, j+1}$ with constant $c$ would be obtained, and in the next iteration, forcing more zeros would result in $\DPx{1, j+2}=0$. This is still true for the changed definition of $\DPx{2, 0}$, and so updating is best done as presented before. However, because we used the term $\qhpolx{1}\upolx{j}$ in the definition of $\DPx{2, 0}$, in these cases another solution may be obtained: As long as the constant multiplied to $\DPx{2, j}$ is not zero, the result includes a term $a_1\cdot x^i\DPx{1, j}$ with $i > 1$. Therefore, in such cases an additional solution - of the form $\DPx{1, j+1}=a\DPx{2, j}+b\DPx{1, j}$ - is a valid solution and therefore it is stored, increasing the maximum list size at the decoder output.

We conclude this section by sketching how the formulas given for the GMD extension interact as an algorithm. We set $\bar{\Delta}:=\da\ddaa-\daa\dda$ to obtain a shorter notation. The variable $dd$ introduced in the algorithm is used to keep track of the special updatings performed.

\begin{algorithm}[H]

\SetLine
\dontprintsemicolon
\KwIn{Polynomials $\DPx{1, 0}$, $\DPx{2, 0}$, \\erasure sets $\mx_j$}
\KwOut{List $\mathcal{L}$ of candidate error locators}
Initialization: $j=0$,
$dd=0$, $\mathcal{L}=\{\DPx{1, 0}\}$\;
\While{$\deg \DPx{1, j} < d-2$}
{
	calculate $\bar{\Delta}$ from $\mx_{j+1}\setminus\mx_{j}$\;
	\uIf{$dd=0$ and $\bar{\Delta} \neq 0$}
		{update according to \eqref{eqn:update_wd01} and \eqref{eqn:update_wd02}}
	\uElseIf{$\bar{\Delta} = 0$}
		{perform special updating and adjust $dd$:\;
		\eqref{eqn:update_wd+1} $\Rightarrow \; dd = dd+1$\;
		\eqref{eqn:update_wd-1} $\Rightarrow \; dd = dd-1$\;
		}
	\uElseIf{$dd > 0$ (and $\bar{\Delta} \neq 0$)}
		{perform compensation step \eqref{eqn:comp_wd+1}, $dd=dd-1$\;}
	\ElseIf{$dd < 0$ (and $\bar{\Delta} \neq 0$)}
		{perform compensation step \eqref{eqn:comp_wd-1}, $dd=dd+1$\;}
	store $\DPx{1, j+1}$ in $\mathcal{L}$\;
	$j=j+1$\;
}
\caption{GMD extension}
\end{algorithm}

\section{Selection of the Best Solution}\label{sec:select}
In this section, we shortly discuss how to select the best solution from the list of candidate error locators. Although the distance criteria used in most cases are trivial, the straightforward approach requires to perform error evaluation for all $\order(d)$ candidate error locators, with a complexity of $\order(n^2)$ each. Hence, in this straightforward approach the overall complexity is $\order(n^3)$ and determined by the evaluation step.

The method suggested by K\"otter \cite{Koetter_GMD} is to use evaluation vectors instead of polynomials during the algorithm. Instead of using the polynomials, evaluation vectors are calculated in the initialization to the GMD extension. In these vectors, every component corresponds to the evaluation of the polynomial at a certain field value, i.e. we substitute
\begin{equation}
\DPx{1, 0} \leftrightarrow \left[ \DPol{1, 0}(1), \DPol{1, 0}(\alpha), \dots \DPol{1, 0}(\alpha^{n-1})\right].
\end{equation}
and so on. Consequently, polynomial multiplications are replaced by elementwise vector multiplications, e.g.
\begin{equation}
x\cdot p(x) \leftrightarrow \left[p(1), \alpha p(\alpha), \alpha^2 p(\alpha^2), \dots, \alpha^{n-1} p(\alpha^{n-1})\right].
\label{eqn:xvector}
\end{equation}
The evaluation of a polynomial is now simply the extraction of one component from a vector. It can be verified that the complexity of the main step, namely finding all candidate error locators, can still be performed with a complexity of $\order(n^2)$. Further, the selection of the best solution is now also possible with complexity $\order(n^2)$: Using a weighted hamming metric, it is only important which positions are in error, while the actual error value is not important. Since these positions can be easily extracted from the evaluation vectors of the candidate polynomials - the positions where the evaluation vectors are zero - the complexity of calculating the weighted Hamming weight of a single candidate is therefore only $\order(n)$, and so finding the best solution among $\order(d)$ candidates can be done with complexity $\order(n^2)$.

\section{Summary and Conclusion}\label{sec:summary}
We presented a method that is capable of performing Generalized Minimum Distance decoding of RS codes with an overall complexity of $\order(n^2)$. A method that exhibits the same performance had already been introduced by K\"otter in 1996 \cite{Koetter_GMD}. This is not surprising, since K\"otters algorithm extends the Berlekamp-Massey algorithm, and ours the extended Euclidean algorithm, and these two algorithms are known to be equivalent for decoding up to half the minimum distance. However, having a different problem formulation and erasing strategy, we do not always have the same intermediate results.

\bibliographystyle{IEEEtran}
\bibliography{bib_eea_ext}

\end{document}

config: arxiv


text:
\section{Experiments}
\label{sec:experiments}

We run two sets of experiments comparing $\mathrm{ODEtoODE}$ with several other methods in the supervised setting and to train RL policies with ES. To the best of our knowledge, we are the first to propose Neural ODE architectures for RL-policies and explore how the compactification of the number of parameters they provide can be leveraged by ES methods that benefit from compact models \cite{structured}.

\subsection{Neural ODE policies with $\mathrm{ODEtoODE}$ architectures}
\label{sec:rl}
\subsubsection{Basic setup}
In all Neural ODE methods we were integrating on time interval $[0,T]$ for $T=1$ and applied discretization with integration step size $\eta=0.04$
(in our ODEtoODE we used that $\eta$ for both: the main flow and the orthogonal flow on $\mathcal{O}(d)$). The dimensionality of the embedding of the input state $s$ was chosen to be $h=64$ for $\mathrm{OpenAI}$ $\mathrm{Gym}$ $\mathrm{Humanoid}$ (for all methods but $\mathrm{HyperNet}$, where we chose $h=16$, see: discussion below) and $h=16$ for all other tasks.

Neural ODE policies were obtained by a linear projection of the input state into embedded space and Neural ODE flow in that space, followed by another linear projection into action-space.
In addition to learning the parameters of the Neural ODEs, we also trained their initial matrices and those linear projections. Purely linear policies were proven to get good rewards on $\mathrm{OpenAI}$ $\mathrm{Gym}$ environments \cite{ARS}, yet they lead to inefficient policies in practice \cite{stoch_1}; thus even those environments benefit from deep nonlinear policies. We enriched our studies with additional environments from $\mathrm{Deep}$ $\mathrm{Mind}$ $\mathrm{Control}$ $\mathrm{Suite}$.
We used standard deviation $\mathrm{stddev}=0.1$ of the Gaussian noise defining ES perturbations, ES-gradient step size $\delta=0.01$ and function $\sigma(x) = |x|$ as a nonlinear mapping. In all experiments we used $k=200$ perturbations per iteration \cite{structured}.
\vspace{-0.3cm}
\paragraph{Number of policy parameters:} To avoid favoring ODEtoODEs, the other architectures were scaled in such a way that they has similar (but not smaller) number of parameters. The ablation studies were conducted for them across different sizes and those providing best (in terms of the final reward) mean curves were chosen. No ablation studies were run on ODEtoODEs.

\subsubsection{Tested methods}

We compared the following algorithms including standard deep neural networks and Neural ODEs:
\vspace{-3mm}
\paragraph{ODEtoODE:} Matrices corresponding to linear projections were constrained to be taken from $\mathrm{Stiefel}$ $\mathrm{manifold}$ $\mathcal{ST}(d)$ \cite{stoch_1} (a generalization of the orthogonal group $\mathcal{O}(d)$). Evolution strategies (ES) were applied as follows to optimize entire policy. Gradients of Gaussian smoothings of the function: $F:\mathbb{R}^{m} \rightarrow \mathbb{R}$ mapping vectorized policy (we denote as $m$ the number of its parameters) to obtained reward were computed via standard Monte Carlo procedure \cite{structured}.

For the part of the gradient vector corresponding to linear projection matrices and initial matrix of the flow, the corresponding Riemannian gradients were computed to make sure that their updates keep them on the respective manifolds \cite{stoch_1}. The Riemannian gradients were then used with the exact exponential mapping from $\mathrm{Skew}(d)$ to $\mathcal{O}(d)$. For unconstrained parameters defining orthogonal flow, standard ES-update procedure was used \cite{salimans}. We applied \textbf{ISO-ODEtoODE} version of the method (see: Sec. \ref{sec:odetoode_types}).

\vspace{-3mm}
\paragraph{Deep(Res)Net:} In this case we tested unstructured deep feedforward fully connected (ResNet) neural network policy with $t=25$ hidden layers.

\vspace{-3mm}
\paragraph{BaseODE:} Standard Neural ODE $\frac{d\mathbf{x}(t)}{dt} = f(\mathbf{x}_{t})$, where $f$ was chosen to be a feedforward fully connected network with with two hidden layers of size $h$.
\newpage
\vspace{-0.6cm}
\begin{figure}[H]
    \begin{minipage}{1.0\textwidth}
    \subfigure{\includegraphics[width=.49\linewidth]{img/a4.png}}

    \subfigure{\includegraphics[width=.49\linewidth]{img/a1.png}}
\end{minipage}
\begin{minipage}{1.0\textwidth}
    \subfigure{\includegraphics[width=.49\linewidth]{img/a2.png}}

    \subfigure{\includegraphics[width=.49\linewidth]{img/a3.png}}
\end{minipage}
\begin{minipage}{1.0\textwidth}
    \subfigure{\includegraphics[width=.49\linewidth]{img/a5.png}}

    \subfigure{\includegraphics[width=.49\linewidth]{img/a6.png}}
\end{minipage}
\begin{minipage}{1.0\textwidth}
    \subfigure{\includegraphics[width=.49\linewidth]{img/a7.png}}

    \subfigure{\includegraphics[width=.49\linewidth]{img/a8.png}}
\end{minipage}
\caption{\small{Comparison of different algorithms: $\mathrm{ODEtoODE}$, $\mathrm{DeepNet}$, $\mathrm{DeepResNet}$, $\mathrm{BaseODE}$, $\mathrm{NANODE}$ and $\mathrm{HyperNet}$ on four $\mathrm{OpenAI}$ $\mathrm{Gym}$ and four $\mathrm{DeepMind}$ $\mathrm{Control}$ $\mathrm{Suite}$ tasks. $\mathrm{HyperNet}$ on Swimmer, Swimmer\_15 and Humanoid\_Stand as well as $\mathrm{DeepNet}$ on Humanoid were not learning at all so corresponding curves were excluded. For $\mathrm{HalfCheetah}$ and $\mathrm{HyperNet}$, there was initially a learning signal (red spike at the plot near the origin) but then curve flattened at $0$.  Each plot shows $\mathrm{mean}$ +- $\mathrm{stdev}$ across $s=10$ seeds. $\mathrm{HyperNet}$ was also much slower than all other methods because of unstructured hypernetwork computations. $\mathrm{Humanoid}$ corresponds to $\mathrm{OpenAI}$ $\mathrm{Gym}$ environment and two its other versions on the plots to $\mathrm{DeepMind}$ $\mathrm{Control}$ $\mathrm{Suite}$ environment (with two different tasks).}}
\label{figure:es}
\end{figure}

\vspace{-9mm}
\paragraph{NANODE:} This leverages recently introduced class of Non-Autonomous Neural ODEs (NANODEs) \cite{nanode} that were showed to substantially outperform regular Neural ODEs in supervised training \cite{nanode}. NANODEs rely on flows of the form: $\frac{d\mathbf{x}(t)}{dt} = \sigma(\mathbf{W}_{t}\mathbf{x}_{t})$. Entries of weight matrices $\mathbf{W}_{t}$ are values of $d$-degree trigonometric polynomials \cite{nanode} with learnable coefficients. In all experiments we used $d=5$. We observed that was an optimal choice and larger values of $d$, even though improving model capacity, hurt training when number of perturbations was fixed (as mentioned above, in all experiments we used $k=200$).
\vspace{-3mm}
\paragraph{HyperNet:} For that method \cite{ha_1}, matrix $\mathbf{W}_{t}$ was obtained as a result of the entangled neural ODE in time $t$ after its output de-vectorization (to be more precise: the output of size $256$ was reshaped into a matrix from $\mathbb{R}^{16 \times 16}$). We encoded the dynamics of that entangled Neural ODE by a neural network $f$ with two hidden layers of size $s=16$ each. Note that even relatively small hypernetworks are characterized by large number of parameters which becomes a problem while training ES policies. We thus used $h=16$ for all tasks while running HyperNet algorithm. We did not put any structural assumptions on matrices $\mathbf{W}_{t}$, in particular they were not constrained to belong to $\mathcal{O}(d)$.

\subsubsection{Discussion of the results}
The results are presented in Fig. \ref{figure:es}. Our ODEtoODE is solely the best performing algorithm on four out of eight tasks: Humanoid, HalfCheetah, Humanoid\_Stand and Swimmer\_15 and is one of the two best performing on the remaining four.  It is clearly the most consistent algorithm across the board and the only one that learns good policies for Humanoid. Each of the remaining methods fails on at least one of the tasks, some such as: $\mathrm{HyperNet}$, $\mathrm{DeepNet}$ and $\mathrm{DepResNet}$ on more.
Exponential mapping (Sec. \ref{sec:learning}) computations for ODEtoODEs with hidden representations $h \leq 64$ took negligible time (we used well-optimized $\mathrm{scipy.linalg.expm}$ function). Thus all the algorithms but
$\mathrm{HyperNet}$ (with expensive hypernetwork computations) had similar running time.

\subsection{Supervised learning with $\mathrm{ODEtoODE}$ architectures}
\label{sec:supervised}
We also show that $\mathrm{ODEtoODE}$ can be effectively applied in supervised learning by comparing it with multiple baselines on various image datasets.

\subsubsection{Basic setup}
All our supervised learning experiments use the $\mathrm{Corrupted}$ $\mathrm{MNIST}$ \cite{mu2019mnist} ($11$ different variants) dataset.
For all models in Table 1, we did not use dropout, applied hidden width $w=128$, and trained for $100$ epochs. For all models in Table 2, we used dropout with $r=0.1$ rate, hidden width $w=256$, and trained for $100$ epochs. For $\mathrm{ODEtoODE}$ variants, we used a discretization of $\eta=0.01$.

\subsubsection{Tested methods}
We compared our $\mathrm{ODEtoODE}$ approach with several strong baselines: feedforward fully connected neural networks ($\mathrm{Dense}$), Neural ODEs inspired by \cite{chen2018neural} ($\mathrm{NODE}$), Non-Autonomous Neural ODEs \cite{nanode} ($\mathrm{NANODE}$) and hypernets \cite{anode_v2} ($\mathrm{HyperNet}$).
For $\mathrm{NANODE}$, we vary the degree of the trigonometric polynomials.
For $\mathrm{HyperNet}$, we used its gated version and compared against \textbf{gated-ODEtoODE} (see: Sec. \ref{sec:odetoode_types}). In this experiment, we focus on fully-connected architecture variants of all models.
As discussed in prior work, orthogonality takes on a different form in the convolutional case \cite{wang2019orthogonal}, so we reserve discussion of this framing for future work.

\subsubsection{Discussion of the results}
\newcommand{\blue}[1]{\textcolor[rgb]{0.0,0.0,0.95}{#1}}
\newcommand{\red}[1]{\textcolor{red}{#1}}

The results are presented in Table \ref{table1} and Table \ref{table2} below. Our $\mathrm{ODEtoODE}$ outperforms other model variants on 11 out of the 15 tasks in Table \ref{table1}. On this particularly task, we find that $\mathrm{ODEtoODE}$-1, whereby we apply a constant perturbation to the hidden units $\theta{(0)}$ works best. We highlighted the best results for each task in \textbf{\blue{bolded blue}}.

\begin{table}[th!]
\centering\small
\resizebox{\textwidth}{!}{
\begin{tabular}{@{}>{\bfseries}l*{10}{r}@{}}

\toprule[1pt]
\multicolumn{10}{@{}c@{}}{}\\
\midrule[0.75pt]

Models & \textbf{Dense-1} & \textbf{Dense-10} & \textbf{NODE}& \textbf{NANODE-1} & \textbf{NANODE-10} & \textbf{HyperNet-1} & \textbf{HyperNet-10} & \textbf{ODEtoODE-1} & \textbf{ODEtoODE-10} & \\
\midrule[0.55pt]

Dotted Lines & 92.99 & 88.22	& 91.54	& 92.42	& 92.74	& 91.88 & 91.9 & \blue{\textbf{95.42}} & 95.22 &  \\
Spatter & 93.54 & 89.52	& 92.49	& 93.13	& 93.15	& 93.19	& 93.28	& \blue{\textbf{94.9}}	& \blue{\textbf{94.9}}	& \\
Stripe & 30.55 & 20.57 & 36.76	& 16.4	& 21.37	& 19.71	& 18.69	& \blue{\textbf{44.51}} & 44.37	&  \\
Translate & 25.8 & 24.82 & 27.09	& 28.97	& 29.31	& \blue{\textbf{29.42}} & 29.3	& 26.82	& 26.63 & \\
Rotate & 82.8 & 80.38	& 82.76	& 83.19	& 83.65	& 83.5	& 83.56	& 83.9 & \blue{\textbf{84.1}} &  \\
Scale & 58.68 & 62.73	& 62.05	& 66.43	& 66.63	& 67.84	& \blue{\textbf{68.11}} & 66.68 & 66.76	&  \\
Shear & 91.73 & 89.52	& 91.82	& 92.18	& 93.11	& 92.33	& 92.48	& \blue{\textbf{93.37}} & 92.93	&  \\
Motion Blur & 78.16 & 67.25	& 75.18	& 76.53	& \blue{\textbf{79.22}}	& 78.82	& 78.33	& 78.63	& 77.58	&  \\
Glass Blur & 91.62 & 84.89	& 87.94	& 90.18	& 91.07	& 91.3	& 91.17	& \blue{\textbf{93.91}} & 93.29	&  \\

Shot Noise & 96.16 & 91.63 & 94.24 & 94.97 & 94.73 & 94.76 & 94.81 & \blue{\textbf{96.91}} & 96.71 &  \\
Identity & 97.55 & 95.73	& 97.61	& 97.65	& 97.69	& 97.72	& 97.54	& \blue{\textbf{97.94}} & 97.88	&  \\

\bottomrule[2pt]
\addlinespace[3pt]
\end{tabular}}
\caption{\small Test accuracy comparison of different methods. Postfix terms refer to hidden depth for Dense, trigonometric polynomial degree for NANODE, and number of gates for HyperNet and ODEtoODE.}\label{table1}
\end{table}

\vspace{-6mm}

\begin{table}[th!]
\centering\small
\resizebox{\textwidth}{!}{
\begin{tabular}{@{}>{\bfseries}l*{14}{r}@{}}

\toprule[1pt]
\multicolumn{14}{@{}c@{}}{}\\
\midrule[0.75pt]

Models & \textbf{Dense-1} & \textbf{Dense-2} & \textbf{Dense-4} & \textbf{NODE} & \textbf{NANODE-1} & \textbf{NANODE-2} & \textbf{NANODE-4} & \textbf{HyperNet-1} & \textbf{HyperNet-2} & \textbf{HyperNet-4} & \textbf{ODEtoODE-1} & \textbf{ODEtoODE-2} & \textbf{ODEtoODE-4} & \\
\midrule[1.0pt]

Dotted Line	& 94.47 &	93.21 &	91.88 &	92.9 &	92 &	92.02 &	92.02 &	92.35 &	92.91 &	92.57 &	95.64 &	\blue{\textbf{95.66}} &	95.6  \\
Spatter	& 94.52	& 93.59	& 93.63 &	93.32 &	92.81 &	92.82 &	92.84 &	94.09	& 93.94	& 93.73	& 95.28	& \blue{\textbf{95.47}}	& 95.29	 \\
Stripe & 29.69	& 32.73	 & 31.49 &	36.08 &	27.32 &	23.56 &	24.66 &	30.86	& 31.12 &	29.1	& \blue{\textbf{36.25}}	& 28.21	& 31.91  \\
Translate	& 25.85	& 28.35	& 27.27	& 29.13	& 29.11 &	29.24 &	28.7	& 29.85 &	29.68 &	\blue{\textbf{29.87}} &	25.61 &	26.1 &	26.42  \\
Rotate & 83.62	& 83.73 & 83.88 &	83.09 &	82.5 &	82.77 & 83.03 & 83.96	& 84.04	& 84.13 &	\blue{\textbf{85.1}} &	85.03 &	84.72  \\
Scale & 61.41	& 65.07 & 63.72 &	63.62	& 65.49	& 65.33 &	64.03	& 69.51 &	68.77	& \blue{\textbf{69.8}}	& 67.97	& 66.95	& 67.09  \\
Shear & 92.25 &	92.76 &	92.55 &	92.27 &	92.08 &	92.18 &	92.3 &	93.35	& 92.84	& 93.04	& 93.15 &	93.06 &	\blue{\textbf{93.38}}  \\
Motion Blur	& 76.47 & 73.89 &	74.95 &	76.3 &	75.24	& 75.88	& 76.22	& 80.67 &	81.26 &	\blue{\textbf{81.36}} &	78.92 &	79.11 &	79.02  \\
Glass Blur & 92.5 &	89.65 &	90.29 &	89.47 &	89.5 &	89.5 &	89.8 &	93.07 &	92.67 &	92.69 &	\blue{\textbf{94.46}} &	94.19 &	94.3  \\

Shot Noise & 96.41 & 95.78 &	95.22 &	95.09 &	94.18  &	94.12 &	93.85 &	95.36 &	96.88 &	96.77 &	\blue{\textbf{96.93}} &	96.88 &	96.77  \\
Identity & 97.7 & 97.75 &	97.71 &	97.64 &	97.6 &	97.5 &	97.52 &	97.7	& 97.82	& 97.79 &	98.03 &	\blue{\textbf{98.12}} &	98.11  \\

\bottomrule[2pt]
\addlinespace[3pt]
\end{tabular}}
\caption{\small Additional Sweep for the setting as in Table \ref{table1}. This time all models also incorporate dropout with rate r = 0.1 and width w = 256. As above in Table \ref{table1}, $\mathrm{ODEtoODE}$ variants achieve the highest performance.}\label{table2}
\end{table}


TITLE: marginal probability, three variables
QUESTION [0 upvotes]: I got stuck with this:
P(A|C) = $\sum_{B}$ (A, B|C)
(B should be beneath the sum sign)
I understand marginal probability with two variables. But when it is three or more variables, I just could not make sense of it. What if A intersects C, but it does not intersect with the intersection of B and C? Why sum of B works? Can someone walk me through this? Thanks!

REPLY [0 votes]: You should be aware of the definition of conditional probability.  $\mathsf P(A\mid C)=\mathsf P(A,C)/\mathsf P(C)$
For three events, same again: $\mathsf P(A, B\mid C)=\mathsf P(A,B,C)/\mathsf P(C)$
So just apply that and the Law of Total Probability.
$$\begin{align}\mathsf P(A\mid C) ~=~&\dfrac{\mathsf P(A,C)}{\mathsf P(C)} \\[1ex]=~& \dfrac{\sum_{B_k}\mathsf P(A,B_k,C)}{\mathsf P(C)} \\[1ex]=~& \sum_{B_k}\mathsf P(A, B_k\mid C)\end{align}$$
That is all.

As to why the sum works: If $(B_k)$ is a sequence of disjoint events partitioning the sample space -- well, in this case, at least exhaustively covering $C$ -- then: $$\mathsf P(A\cap C) ~=~ \mathsf P(\bigcup_{B_k} A\cap B_k\cap C)~=~\sum_{B_k}\mathsf P(A\cap B_k\cap C)$$


TITLE: Milnor's definition of smooth manifold
QUESTION [10 upvotes]: In Milnor's book "Topology from a differential viewpoint" on page one he defines a smooth manifold to be a subset $M \subset \mathbb R^n$ which is locally diffeomorphic to some open subset of $\mathbb R^k$, i.e. every point $x \in M$ has a neighborhood $U \subset \mathbb R^n$ such that $U \cap M = V$ for some open $V \subset \mathbb R^k$ . The usual definition I know is that a smooth manifold is a (hausdorff and second countable) topological space $M$ together with an open cover $\{U_{\alpha}\}$ and homeomorphisms $f_{\alpha} : U_{\alpha} \rightarrow V_{\alpha}$ such that $V_{\alpha} \subset \mathbb R^k$ are open and the transition functions $f_{\beta}f_{\alpha}^{-1}$ are smooth (where defined).

Question: How does the usual definition of smooth manifold imply
  Milnor's definition of smooth manifold?

REPLY [1 votes]: Milnor defines what is usually called a submanifold of $\mathbb R^n$. This is a more special approach than considering "abstract" smooth manifolds which are Hausdorff and second countable topological spaces endowed with an atlas having smooth transition functions.
Clearly all subspaces of $\mathbb R^n$ are Hausdorff and second countable. The essential question is this:

Are Milnor's manifolds special cases of abstract smooth manifolds? More precisely, do they have a "natural" atlas with smooth transition functions?

The answer is yes.
On p.1 Milnor extends the "classic" concept of a smooth map between open subsets $U, V$ of Euclidean spaces to maps $f : X \to Y$ between arbitrary subsets $X \subset \mathbb R^n$  and $Y \subset \mathbb R^m$ by requiring that for all $x \in X$ there exists an open neigborhood $U$ of $x$ in $\mathbb R^n$ and a smooth extension (in the classic sense) $f_U : U \to \mathbb R^m$ of $f \mid_{U \cap M}$. A diffeomorphism $f : X \to Y$ is then a homeomorphism such that $f, f^{-1}$ are smooth.
For the moment let us reserve the word "smooth map" for a map  between open subsets of Euclidean spaces which is smooth in the classic sense and use the phrase "$\mu$-smooth map" for the generalized case. We also use the phrase "$\mu$-diffeomorphism" to distinguish it from a classic diffeomorphism.
Let us make the following observations:

If $X$ is an open subset of $\mathbb R^n$ and $Y$ is an open subset of $\mathbb R^m$, the $f : X \to Y$ is $\mu$-smooth if and only if it is smooth.

If $X$ is an open subset of $\mathbb R^n$, then $f : X \to Y \subset \mathbb R^m$ is $\mu$-smooth if and only if $\bar f : X \stackrel{f}{\to} Y \hookrightarrow \mathbb R^m$ is smooth.

That $M \subset \mathbb R^n$ is a smooth manifold of dimension $k$ means that for each $x \in M$ there exists a pair $(W,\phi)$ consisting of an open neigborhood $W$ of $x$ in $M$ and a $\mu$-diffeomorphism $\phi : W \to U$ to an open subset $U \subset\mathbb R^k$. This means in particular that $M$ is a topological  manifold (i.e. is locally Euclidean) and that the above $(W,\phi)$ form an atlas $\mathcal A$ for $M$. We shall prove that  $\mathcal A$ is a smooth atlas, that is, $M$ has a natural structure of an "abstract" smooth manifold.
So let $(W_i,\phi_i) \in \mathcal A$ with $\phi_i : W_i \to U_i \subset \mathbb R^k$. Consider the transition function
$$\phi_{12} : \phi_1(W_1 \cap W_2) \stackrel{\phi_1^{-1}}{\to} W_1 \cap W_2 \stackrel{\phi_2}{\to} \phi_2(W_1 \cap W_2) $$
and a point $\xi \in \phi_1(W_1 \cap W_2)$.
Since $\phi_2$ is $\mu$-smooth, $x = \phi_1^{-1}(\xi)$ admits an open neigborhood $V_2$ in $\mathbb R^n$ and a smooth extension $\phi_2^* : V_2 \to \mathbb R^k$ of $\phi_2 \mid_{V_2 \cap M}$. Since $\phi_2^*(x) = \phi_2(x) \in \phi_2(W_1 \cap W_2)$, the continuity of $\phi_2^*$ shows that we may w.lo.g. assume that $\phi_2^*(V_2) \subset \phi_2(W_1 \cap W_2)$ (shrink $V_2$ if necessary). Thus we may regard $\phi_2^*$ as a smooth map
$$\phi_2^* : V_2 \to \phi_2(W_1 \cap W_2) .$$
Since $\phi_1^{-1}$ is $\mu$-smooth, our above observation says that $\psi : U_1 \stackrel{\phi_1^{-1}}{\to} W_1 \hookrightarrow \mathbb R^n$ is smooth. Since $\psi$ is continuous, there exists an open neighborhood $U \subset U_1$ of $\xi$ such that $\psi(U) \subset V_2$. Thus the composition
$$\tau : U \stackrel{\psi}{\to} V_2 \stackrel{\phi_2^*}{\to} \mathbb R^k$$
is smooth. By construction
$$\tau = \phi_{12} \mid_U$$
which shows that $\phi_{12} \mid_U$ is smooth. But smoothness is local property, therefore $\phi_{12}$ is smooth.
Remark.
Although submanifolds are special cases of manifolds, focussing on submanifolds is not really a restriction. This follows from the fact that each abstract smooth manifold is diffeomorphic to a submanifold of some $\mathbb R^n$.
Submanifolds have benefits for motivational purposes. For example, the concept of the tangent space at a point of a submanifold is fairly intuitive. See  The motivation for a tangent space and Equivalent definition of a tangent space?
For alternative definitions of submanifolds see Equivalences of definitions of submanifolds in $\mathbb{R^n}$. Note that Milnor's definition implies characterization $(2)$. In fact, let $x \in M$ and  $\phi : W \to U$ be a $\mu$-diffeomorphism from an open neigborhood $W$ of $x$ in $M$ to an open subset $U \subset\mathbb R^k$. W.l.o.g. we may assume that $\phi(x) = 0$ (otherwise compose $\phi$ with a translation on $\mathbb R^k$). Let
$$f : U \stackrel{\phi^{-1}}{\to} W \hookrightarrow \mathbb R^n .$$
This is a smooth map. Since $\phi$ is $\mu$-smooth, there exist an open neighborhood $V$ of $x$ in $\mathbb R^n$ and a smooth extension  $\phi_V : V \to \mathbb R^k$ of $\phi \mid_{V \cap M}$. We have $$\phi_V \circ f \mid_{f^{-1}(V)} = id .$$
Since both $\phi_V$ and $f \mid_{f^{-1}(V)}$ are smooth, we get
$$D\phi_V \mid_{x} \circ Df_0 = id$$
which implies that $Df_0$ has rank $k$.


TITLE: Diagonal intersection of quadrat
QUESTION [0 upvotes]: A square $ABCD$ is divided by a straight line $g$ into two parts with the same surface area.
Prove that then the diagonal intersection $M$ of the square $ABCD$ lies on the line $g$.

REPLY [1 votes]: A variation on @C.F.G: suppose $M$ is not in $g$. Take the line $g'$ parallel to $g$ which does contain $M$. $M$ is the center of the square, so by symmetry, $g'$ divides the square into two equal parts. But there's a strip of positive area between $g$ and $g'$, so $g'$ does not divide the square into two equal parts, which is a contradiction.


TITLE: Show that the image of Lipschitz function $\gamma : [0,1] \to R^n$ has measure $0$, if $n \ge 2$.
QUESTION [5 upvotes]: Problem Statement: Let $\Gamma$ be the image of a Lipschitz continuous function $\gamma : [0,1] \to R^n$, that is, $\Gamma = \{\gamma(t) : t \in [0,1]\}$, and $|\gamma(t_1) - \gamma(t_2)| \le K |t_1 - t_2|$. Show that $m_n(\Gamma) = 0$, where $m_n$ is $n$ dimensional Lebesgue measure.
My attempt at a solution: To start out with, I wanted to check and see if my intuition of why this statement is true makes sense. I believe that the reason this is true is because $m_n([0,1]) = 0,$ since $[0,1] = [0,1] \times \{0\}$ in $R^n$, but I am not sure if that is correct.
Going on, what I have done so far is: proved that since $\gamma$ is Lipschitz, it is absolutely continuous, thus of bounded variation, and can be written as a difference of two increasing functions. Thus, WLOG, assume $\gamma$ is increasing. Now, this implies that if $\{(a_i,b_i)\}_{i=1}^m$ is a finite collection of open intervals that covers $[0,1]$, then $\{f(a_i),f(b_i)\}^m_{i=1}$ covers $\Gamma$.
Now, we know that we can find some such collection of open intervals covering $[0,1]$, such that $m([0,1]) + \epsilon > \sum^m_{i=1}|b_i-a_i|$, and we know that
$$m_n(\Gamma) \le \sum^m_{i=1}|f(b_i)-f(a_i)| \le K \sum^m_{i=1}|b_i-a_i| < 1 + \epsilon.$$
This obviously doesn't get me what I wanted, but I'm not sure how to incorporate the fact that $m_n([0,1]) = 0$... a hint in the right direction would be appreciated.

REPLY [3 votes]: Hint: For any $m \in \mathbb N,$ $\Gamma$ is contained in
$$\bigcup_{k=1}^m \ B(f(k/m), K/m),$$
where $B(a,r)$ is the closed ball centered at $a$ of radius $r.$


TITLE: Finding an angle in a triangle
QUESTION [2 upvotes]: I want to find angle x in this picture.

And this is what I've done so far. Without loss of generality, assume $\overline{\rm BC}=1$
then, $$\overline{\rm BD}= 2\sin{\frac{x}{2}}$$, $$\overline{\rm BH}= 4\sin^2{\frac{x}{2}}= 2(1-\cos{x}), \quad \overline{\rm CH} = 2\cos{x}-1$$
$$\overline{\rm CE}=\frac{2\cos{x}-1}{\sqrt{2-2\cos{x}}}$$
Let $\overline{\rm DE}=y$,
since $\bigtriangleup DCE = \bigtriangleup HCE$,
$$\frac{1}{2}y\sin{50^{\circ}}=\frac{1}{2}\sin{x}\frac{(2\cos{x}-1)^2}{2-2\cos{x}}$$
Then by applying law of cosines to $\bigtriangleup DEC$,
$$y^2+1-2y\cos{50^{\circ}}=\frac{(2\cos{x}-1)^2}{2-2\cos{x}}$$
So we have a system of equations
$$\begin{cases}y\sin{50^{\circ}}=\sin{x}\frac{(2\cos{x}-1)^2}{2-2\cos{x}}\\y^2+1-2y\cos{50^{\circ}}=\frac{(2\cos{x}-1)^2}{2-2\cos{x}} \end{cases}$$
But it's too messy to solve since 50 is not special angle.
How can I solve this problem?

REPLY [1 votes]: As you are concerned by a trigonometrical solution, here is a direct way to obtain a rather simple equation.
Let $x=2y$.

Fig.1.
Angle chasing on the figure in the order (1)...(6) ((7) being a checking) allows to attribute a value expressed as a function of $y$ to each angle.
Let us apply sine law to triangles ADE and DEC. This will give resp.:
$$\frac{\sin 2y}{\sin (140-3x)}=\frac{DE}{AD} \ \ \text{and} \ \ \frac{\sin (90-3y)}{\sin (50)}=\frac{DE}{EC}$$
As $AD=EC$ we have:
$$\frac{\sin 2y}{\sin (140-3y)}=\frac{\sin (90-3y)}{\sin (50)}$$
which can be simplified into:
$$\frac{\sin 2y}{\cos (50-3y)}=\frac{\cos (3y)}{\sin (50)} \iff  \sin 50 \sin 2y=\underbrace{\cos (50-3y)\cos (3y)}_{\tfrac12 \cos(50-6y)+ \tfrac12 \cos(50)}\tag{1}$$
One can verify that $y=20$ degrees is a solution of (1) and check that this solution is the unique one for $y \in (0,90)$ by considering (1) as the equation for the abscissas of the intersection of two curves:

Fig.2: There are apparently 2 solutions to equation (1): $y=20$ degrees and $y=60$ degrees, but the last one is geometrically impossible, due in particular to angle $3y+40$ which would be $>180°$.
But I would like to get a "heuristical" answer by obtaining for example a polynomial equation out of equation (1).
Remark: some similarities with this question.


TITLE: $\sqrt{ 1 - \zeta } = \sqrt{ \zeta }$?
QUESTION [0 upvotes]: In this paper (page 6) I'm reading, the author has a uniform random variable $\zeta$ which takes on values between 0 and 1.  He computes
$$
2 \arccos( \sqrt{ 1 - \zeta } )
$$
But isn't that the same as computing $2 \arccos( \sqrt{ \zeta } )$, since $\zeta$ is uniform on [0..1]?  Or is there a reason he may be doing that I'm missing?

REPLY [3 votes]: You are right, if you consider $\eta = 1-\zeta$ then the distribution of $\eta$ is also uniform on $[0,1].$


TITLE: Conditions for bounded solutions to inhomogeneous system of linear ODEs
QUESTION [2 upvotes]: Consider the simple autonomous, non-homogeneous system of linear ODE's
$$\dot{\mathbf{x}}(t) = M\mathbf{x}(t) + \mathbf{b}$$
where $\mathbf{x} :\mathbb{R}\to\mathbb{C}^n$ is a vector valued function of time, $M$ is a constant $n\times n$ complex matrix, and $\mathbf{b}\in\mathbb{C}^n$ is constant.
My main question is the following:

Q: What are the necessary conditions placed on $M$ and $\mathbf{b}$ such that all solutions $\mathbf{x}(t)$ are bounded, in norm, for all $t$? That is, all solutions satisfy $\|\mathbf{x}(t)\|\leq R$ for all $t$, with  $R\in(0,\infty)$ fixed.

When $\mathbf{b} = 0$, I know the answer: the eigenvalues $\lambda$ of $M$ must satisfy $\text{Re}(\lambda)\leq 0$ and the Jordan blocks (in a Jordan normal form of $M$) corresponding to any eigenvalue with $\text{Re}(\lambda)=0$ must size $1\times 1$.
For $\mathbf{b} \neq 0$, can the Jordan normal form of $M$ alone determine whether all solutions are bounded? Or, does $\mathbf{b}$ play a non-trivial role in diagnosing this notion of "stability"? I think I can prove that all solutions are bounded whenever $M$ is diagonalizable and has eigenvalues that lie strictly in the left half plane ($\text{Re}(\lambda)<0$) but am not sure how to move beyond.
I should also say that I am aware of other notions of stability such as Lyapunov stability, asymptotic stability, etc, and I know various theorems relating the Jordan normal form of $M$ to these notions. I'm simply having trouble finding results relating to this boundedness criterion I state.
Thanks to anyone who may be able to answer or point me in the right direction!

REPLY [2 votes]: The solution can be calculated as
$$ \dot {\mathbf{x}}(t) - M{\mathbf x}(t) = \mathbf b   $$
$$ (e^{-tM}{\mathbf x}(t))' = e^{-tM}\mathbf b $$
$$ \mathbf x(t) = e^{tM}\mathbf x_0 + \int_0^t e^{(t-s)M}\mathbf b\ ds $$
It is well known that $M = S D S^{-1}$, where $D$ is block diagonal consisting of blocks
$$ J=\begin{pmatrix} \lambda & 1 & 0 &\ldots &0 \\ 0 & \lambda & 1 & \ldots \\  0 & 0 & \lambda & \ldots    \\
 &  & & \ddots & \\ 0&0 &0& \ldots & \lambda \end{pmatrix}, $$
furthermore
$$ \exp(tJ) = \begin{pmatrix} e^{t\lambda} & t\lambda e^{t\lambda} & \ldots &\frac{(t\lambda)^{m-1}}{(m-1)!} e^{t\lambda} \\ 0 & e^{t\lambda}& \ldots &\frac{(t\lambda)^{m-2}}{(m-2)!}e^{t\lambda} \\
& & \ddots & \\
0 & 0 & \ldots & e^{t\lambda} \end{pmatrix} .$$
Now, letting $\mathbf{y}(t) = S^{-1} \mathbf{x}(t) $ we have
$$ \mathbf{y}'(t) = S^{-1}\mathbf{x}'(t) = S^{-1} M \mathbf{x}(t) + S^{-1}\mathbf b = D\mathbf{y}(t) + \widetilde{\mathbf b}. $$
For an arbitrary index $k$ we have
$$ y_k(t) = e^{t\lambda_k}\sum_{j=0}^{l_k-1} \frac{(t\lambda_k)^{j}}{(j)!} y_{0k} +\int_0^t e^{(t-s)\lambda_k}\sum_{j=0}^{l_k-1} \frac{((t-s)\lambda_k)^{j}}{(j)!} \widetilde b_k\ ds  $$
if $\lambda_k \neq 0$. In case $\lambda_k = 0$
$$ y_k(t) = \sum_{j=0}^{l_k-1} \frac{(t\lambda_k)^{j}}{(j)!} y_{0k} +\int_0^t \sum_{j=0}^{l_k-1} \frac{((t-s)\lambda_k)^{j}}{(j)!} \widetilde b_k\ ds . $$
For fixed $j$ we have
$$ \int_0^te^{\lambda_k(t-s)}(\lambda_k(t-s))^j\ ds = t^{j+1}\lambda_k^j\int_0^1 e^{\lambda_k t u}u^j\ du = \big(\lambda_k^{j-1} t^j +O(t^{j-1})\big)e^{\lambda_kt} $$
meaning that the stability of the solution of fully determined by the eigenstructure of $M$.


TITLE: Order of automorphism group of an almost elementary abelian group
QUESTION [1 upvotes]: Let $A$ be an almost elementary  abelian 2-group with an elementary abelian subgroup $B$ of index 2. If $|B|=2^m$ then what can we say about the order of automorphism group of $A$?

REPLY [0 votes]: Not 100% sure on this but here goes:  We know any automorphism of $A$ must restrict to an automorphism of $B$, and  $Aut(B) = GL(m,2)$. Also, there is a unique nonzero element of $A$ that is in the image of the map $x \rightarrow 2x$.  This element must get mapped to itself. So with a suitable basis any automorphism of $A$ restricts to the subgroup of $GL(m,2)$ with the first column $(1,0,0,...0)^t$. This subgroup has size $(2^m-2)(2^m-4)...(2^m-2^{m-1})$. Now in order to extend one of these suitable $B$-automorphisms to an $A$-automorphism it is enough to specify where one of the elements of order 4 goes, there are $2^m$ choices. So I'm getting $|Aut(A)|=(2^m-2)(2^m-4)...(2^m-2^{m-1})2^m$.


TITLE: sums and product of density functions are density?
QUESTION [2 upvotes]: Given $f,g$ to be density functions. If the function $\psi = \lambda f +(1-\lambda)g$, for $\lambda \in [0,1]$, a density function? If the product $fg$ is also a density function?

I know that a random variable $X$ is called continuous if its distribution function can be expressed as
$$F(x) = \int_{-\infty}^xf(u) du,$$
for some $f: \mathbb{R} \to [0,\infty)$ called the (probability) density function of $X$.
To show that $\psi$ is a density function, I only need to show $\psi$ is integrable, and that the integral is equal to $1$, that is,
$$\int_{-\infty}^{\infty} \psi =1.$$
We have
$$\int_{-\infty}^{\infty} \psi = \lambda\int_{-\infty}^{\infty} f + (1-\lambda)\int_{-\infty}^{\infty} g.$$
Now, We have that since $f,g$ are density functions, then
$$\int_{-\infty}^{\infty} f(u)du = \lim_{x \to \infty} F(x) = 1,$$
and
$$\int_{-\infty}^{\infty} g(u)du = \lim_{x \to \infty} G(x) = 1,$$
thus $$\int_{-\infty}^{\infty} \psi = \lambda + 1 - \lambda = 1,$$ as required. Also, $\psi \geq 0$, because the image of $f,g$ are non-negative and $\lambda \in [0,1]$. For the other part, I was given a hint that the product $fg$ is not necessarily a density function. For example, let $f=g=1$ for $x \in [0,1]$, then $fg=1$ for $x \in [0,1]$. I just cannot see clearly, why this example is not a density function? Can someone show me why is it not a density function?
Thanks in advance.

REPLY [2 votes]: I think the example $f=g=1$ on $[0,1]$ is not a counterexample— it's a positive example of two density functions whose product is also a density function. A counterexample might be something like:
Let $f(x) = 1$ if $x \in [0, 1]$, and zero elsewhere. Let $g(x) = 1$ if $x \in [2,3]$ and zero elsewhere. The product $fg$ is zero everywhere, and is not a density function. (The trick here is that the density functions don't "overlap"— they have nonoverlapping support.)

A side note: in order for $\psi$ to be a density function, its total integral must be equal to one (not just finite):
$$\int_{-\infty}^\infty \psi(x)dx = 1.$$
And $\psi$ must also have $\psi(x) \geq 0$ everywhere.
When $\lambda \in [0,1]$, the convex sum $\lambda f + (1-\lambda)g$ is a density function in this way, as you point out.


TITLE: How to prove that a $3 \times 3$ Magic Square must have $5$ in its middle cell?
QUESTION [51 upvotes]: A Magic Square of order $n$ is an arrangement of $n^2$ numbers, usually distinct integers, in a square, such that the $n$ numbers in all rows, all columns, and both diagonals sum to the same constant.

How to prove that a normal $3\times 3$ magic square must have $5$ in its middle cell?
I have tried taking $a,b,c,d,e,f,g,h,i$ and solving equations to calculate $e$ but there are so many equations that I could not manage to solve them.

REPLY [0 votes]: Once 15 is established as the magic number the easiest way to see this is to reason as follows. If a row/column/diagonal is 8,6,1, we say that 8 is opposite 1.
If a number smaller than five is in the centre consider the number opposite the remaining smallest number. It will have to be greater than 10.
Similarly a number greater than five will not do.


TITLE: Determine $[F(a):F]$ if $a\in K$ has $k$ distinct images under Galois group
QUESTION [2 upvotes]: Suppose that $K/F$ is Galois extension and $a \in K$ has exactly $k$ distinct images under $Gal(K/F)$. Show that $[F(a):F]=k$.

My guess is that the images of $a$ form a basis of $F(a)$ over $F$. But I don't know how to show that. Any ideas?

REPLY [1 votes]: Since $\;K/F\;$ is Galois it is then separable, so $\;a\;$ has as many conjugates as its minimal polynomial's degree.


TITLE: If $f\in o(x^r)$ then does $f\in O(x^s)$ for some $0\leq s <r$?
QUESTION [1 upvotes]: Given two real valued funtions $f, g$, where $g$ is strictly positive, defined in some unbounded subset of $[0,\infty)$, we say that $f\in O(g)$ if there is some constant $C\in \mathbb{R}$ such that
$$
|f(x)|\leq Cg(x)
$$
for all large enough values of $x$.
We say that $f\in o(g)$ if
$$
\lim_{x\rightarrow \infty} \frac{f(x)}{g(x)}=0.
$$
So clearly if $f\in o(g)$ then $f\in O(g)$, where $C$ in the definition can be taken to be any positive constant.
Now consider functions $x^r$ where $r\in [0,\infty)$.

My question is whether some function $f$ can satisfy $f\in o(x^r)$ for some $r$ but also $f\notin O(x^s)$ for every $0\leq s<r$.

REPLY [4 votes]: Consider function $f(x) = \frac{x^r}{\ln(x)}$. Clearly, then $\lim_{x \to \infty} \frac{f(x)}{x^r} = \lim_{x \to \infty} \frac{1}{\ln(x)} = 0$.
Now, take any $s \in [0,r)$. Then $ t= r-s > 0$.
So we get: $f(x) = g(x) \cdot \frac{x^t}{\ln(x)}$
One can show, that $\frac{x^t}{\ln(x)} \to \infty$ as $x \to \infty$, so there doesn't exist any constant $C \in \mathbb R$, such that $f(x) \le C\cdot g(x)$


TITLE: Construction of Irreducible Polynomials over Finite Fields
QUESTION [11 upvotes]: I understand construction of irreducible polynomials over finite fields is a non trivial problem. Can anyone please refer me to good resources regarding constructive approaches of irreducible polynomials?
Also a perspective of how construction of irreducible polynomial will help to understand other branches of mathematics such as coding theory, cryptography,etc., will be very helpful.
I am currently reading Lidl's 'Finite Fields' and found the conditions regarding the same problem a bit absurd looking and not very intuitive, (specially chapher 3, section 3 part). Can I have better ways to comprehend those results?

Added by mixedmath
The OP indicated in the comments that the parts of this book that are relevant are theorems 3.36 and 3.37. For ease, I display what is freely available here. Unfortunately, there is no theorem 3.36. But there is an example 3.36:

And the part of the theorem that we can access:

The rest is not included in the preview.

Edit:
I found this http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf , in this paper the authors give an algorithm for constructing irreducible polynomials, but my mathematical background does not permit me to understand the paper fully, still if someone please explains the steps in the first algorithm with an example i will be glad.
Specifically the fourth step of the first algorithm remains unclear to me.

REPLY [1 votes]: Just to add another alternative to construct the list of irreducible polynomials using a bruteforce approach: you can simply try every possible polynomial between 2^p and 2^p * 2 and then just test their primality. This is described here with sourcecode here.


TITLE: Conditional Expectation Problem
QUESTION [1 upvotes]: I am working on this problem and so far conditional expectation is a complete mystery to me..
$(X,Y)$ is a random variable on $\mathbb{R}^2$ with density $f(x,y)$.  If $\mathbb{E}|X|<\infty$ then
$$\mathbb{E}(X|Y) =\frac{\int xf(x,Y)dx}{\int f(x,Y)dx}$$
Where the integrals are over the whole line.
It seems like this should somehow come from definitions easily but I have no idea why this should be true.

REPLY [2 votes]: Let us denote by $f_Y$ the marginal density of $Y$, i.e.
$$
f_Y(y)=\int_{\mathbb{R}}f(x,y)\,\mathrm dx,
$$
and let's assume that $f_Y(y)\neq 0$ for all $y\in\mathbb{R}$. Define $Z=\varphi(Y)$ where
$$
\varphi(y)=\frac{\int_{\mathbb{R}}xf(x,y)\,\mathrm dx}{\int_{\mathbb{R}}f(x,y)\,\mathrm dx}=\frac{\int_{\mathbb{R}}xf(x,y)\,\mathrm dx}{f_Y(y)}.
$$
In order to show that $E[X\mid Y]=Z$ we have to show that

$Z$ is integrable.
$Z$ is $\sigma(Y)$-measurable.
For any $A\in\sigma(Y)$ (i.e. $A$ is of the form $A=\{Y\in B\}$ for some Borel set $B$) we have that
$$\int_A Z\,\mathrm dP=\int_AX\,\mathrm dP.$$

Let me know if any of these causes you trouble.


TITLE: Violation of KVL ,KCL at high Frequencies
QUESTION [3 upvotes]: question:
How can we prove mathematically that KVL (Kirchoff's volatage law) and KCL (Kirchoff current law) become invalid at very large frequencies?
i have read this statement in my book but it doesn't explain the fact that why KVL , KCL fails at High frequency
is that because condcuting wires in very circuit , at high frequency start to pose reactances,  and don't act like lumped elements(whose electrical length is very less than operating wavelength)

can anyone explain me more at atomic level that what happens inside any resistive Electric circuit(of course condcuting wires are also present) driven by source when source's freqency increases indefinitely

REPLY [0 votes]: Kirchhoff's voltage law (KVL) in its modern form is always valid, due to definition of voltage: difference of potentials. Since potential is a function of position, sum of voltage drops along a closed loop is always zero. This has nothing to do with the Faraday law, which concerns total electric field: the voltage drops across any path segment do not, in general, reflect total electric field there, but only its potential part.
Kirchhoff's current law (KCL) ceases to be valid when the electric current charging up wire surfaces ceases to be negligible when compared to current flowing along the wires. This happens when electric current in the circuit oscillates with very high frequency.


TITLE: Getting function into TI-83 calculator trouble
QUESTION [0 upvotes]: I'm trying to get
$$y = -0.1t^2 + 1.2t + 98.6, \quad0 \le t \leq 12 $$
into my TI-83 calculator to graph it, but I'm having trouble figuring out the correct syntax for this one. What it would be? I tried something like $0\le x\le 12$ then the equation, and every other combo of things I could think of but nothing is working.

REPLY [0 votes]: You first go to "mode" and set the calculator to parametric. After that, you press the Y= button and set X=T (the variable, not the letter) and Y=-0.1T^2 + 1.2T + 98.6. Go to 2nd: Quit and then press window, setting the Tmin and Tmax for 0 and 12, respectively. Set the increment for whatever you want and then press graph, and you should be good to go.


TITLE: Fourier transform of product of twho functions that includes characteristic function
QUESTION [0 upvotes]: I need to find the fourier transform of f(x)=(1-abs(x))(Chi_[-1,1] (x)). In words, I need the fourier transform of one minus the absolute value of x multiplied by the characteristic function on interval -1,1.
I tried using the convolution theorem and finding the fourier transform for both functions separately, but then I realized I didn't understand how to compute the convolution of the separate transforms.  Can someone please explain how I would go about finding this transform?
I got an answer of -1/ξ^2 (2isin(ξ) but I am not sure if this correct.  I am using the fourier definition of:
(1/2pi) integral of f(x)e^(-iξx) dx

REPLY [0 votes]: You may compute the Fourier transform directly. Since $f \in L^1(\mathbb{R})$, for $\xi \neq 0$, we have
$$
\hat{f}(\xi) = \int_{-1}^1\, (1-|x|)\cdot e^{-2\pi ix\xi}\, dx = \left( \frac{\sin \pi \xi}{\pi \xi}\right)^2.
$$
For $\xi=0$, $e^{-2\pi ix\xi}=1$, so $\hat{f}(0)=\int_{-1}^1\, (1-|x|)\, dx= 1$.


TITLE: If $A^2=\mathbb{I} (2\times 2$ identity) then $\mathbb{I} + A$ is invertible only if $A=\mathbb{I}$
QUESTION [2 upvotes]: I want to show that if $A^2=\mathbb{I}$ ($2\times2$ identity) then $\mathbb{I} + A$ is invertible only if $A=\mathbb{I}$.
I know that $A^2=\mathbb{I}$ means that $A=A^{-1}$
I've started by letting $A=\begin{bmatrix} a&b\\c&d \end{bmatrix}$ and then $A+1=\begin{bmatrix} a+1&b\\c&d+1 \end{bmatrix}$ so it's invertible only when $(a+1)(d+1)-bc\neq 0$ and then I was going to see when this would be the case based on what we know about $A$ but this seems over complicated and I feel like there's a better way that I'm missing.

REPLY [6 votes]: Hint: $$A(I+A)=I+A\,\,\,\,\,\,$$

REPLY [1 votes]: $(A + \mathbb I)(A - \mathbb I) = A^2 - \mathbb I = \mathbb I - \mathbb I = O.$ Because we know that $A^2 = \mathbb I$. As Sahiba Arora commented, $A + I$ is invertible, so $A - I = O$ and $A = \mathbb I$.

REPLY [0 votes]: First, $(I+A)^2=2(A+I)$, thus the eigenvalues of $I+A$ are among the roots of $X^2-2X$, that is to say $0$ and $2$. If $I+A$ is invertible then $0$ can’t be an eigenvalue of $I+A$, thus $I+A=2I$ and $A=I$ because for all invertible matrix $P$, we have $P(2I)P^{-1}=2I$.


TITLE: finding the number of sub fields such that $(K : Q) = 2$
QUESTION [1 upvotes]: Consider the polynomial $f(x) = x^5 - 4x + 2$. Let $L$ be the complex splitting field of $f(x)$ over $\mathbb{Q}$. I want to find the number of subfields $K$ of $L$ such that $(K : \mathbb{Q}) = 2$.
I believe there is only one such subfield and that is $S_{5}$. I am not sure how to prove it though.

REPLY [4 votes]: You can easily see that $f(x) = x^5 -4x + 2$ is irreducible in $\mathbb{Q}[x]$ by Eisenstein's criterion with $p = 2$. Also, by using calculus you can check that $f(x)$ has three real roots and two complex conjugate roots.

Then you can use the following standard result.
Proposition Let $f(x) \in \mathbb{Q}[x]$ be irreducible over $\mathbb{Q}$ and of prime degree $p$. If $f(x)$ has exactly two nonreal roots in $\mathbb{C}$ then the Galois group of $f(x)$ is isomorphic to $\mathbb{S}_p$.
Thus we conclude that the Galois group $G$ of $f(x) = x^5 -4x +2$ is $G \cong \mathbb{S}_5$, as you correctly mention in your question.
Then, by the Galois correspondence, any intermediate subfield $\mathbb{Q} \subset K \subset L$ of degree $[K:\mathbb{Q}] = 2$ corresponds to a subgroup $H \leq G$ of index $[G:H] = 2$. And then it is known from basic group theory that the only index $2$ subgroup of $\mathbb{S}_5$ is $\mathbb{A}_5$. Thus there is exactly one intermediate subfield $\mathbb{Q} \subset K \subset L$ of degree $2$.