TITLE: How can we conclude that $\{ x: \phi(x) \}$ is a set?
QUESTION [0 upvotes]: I am looking at the following Theorem:
Let $\phi$ a type. We suppose that there is a set $Y$, such that $\forall x(\phi(x) \to x \in Y)$. Then, there is the set $\{ x: \phi(x) \}$.
and I try to understand its proof.
From the axiom shema of specification, there is the set $V=\{ x \in Y: \phi(x) \}$
$$x \in V \leftrightarrow (x \in Y \wedge \phi(x))$$
How can we continue, in order to show that $\{ x: \phi(x) \}$ is a set?

REPLY [1 votes]: The idea, here, is to show that $V$ contains and is contained in the alleged set. One inclusion is clear, since $V$ is the intersection of the alleged set with $Y.$ For the reverse inclusion, use what you know about the type $\phi$ and the set $Y.$
Added: On the one hand, suppose that $x\in V.$ That is, we have $x\in Y$ and $\phi(x).$ So, in particular, $\phi(x),$ meaning $x$ is a member of the alleged set. Since this holds for all $x\in V,$ then it follows that $V$ is contained in the alleged set.
On the other hand, suppose that $x$ is a member of the alleged set, meaning $\phi(x).$ Since $\phi(x),$ then by assumption, we know that $x\in Y.$ Hence, since $x\in Y$ and $\phi(x),$ then $x\in V$ by definition. Hence, $V$ contains the alleged set, as well.
By double-inclusion, $$V=\{x:\phi(x)\},$$ so the alleged set is, indeed, a set.

Hopefully, you see why that bit about $Y$ is essential to the proof. If we have no such condition, then we may not have a set at all. For example, suppose that $\phi(x)$ is the statement "$x=x.$" Then if $\{x:\phi(x)\}$ were a set, it would be the "set of all sets," which leads to a number of paradoxes, and so cannot exist.


text:
\begin{document}

\title{Permutation equivalent maximal irreducible Goppa codes}

\author{  Francesca  Dalla Volta\footnote{francesca.dallavolta@unimib.it, Dipartimento di Matematica e applicazioni
Universit\aac di Milano Bicocca },  Marta Giorgetti\footnote{ marta.giorgetti@uninsubria.it,  Dipartimento di Fisica e Matematica
Universit\aac dell'Insubria, Como}, Massimiliano Sala\footnote{ msala@bcri.ucc.ie,  Dipartimento di Matematica
  Universit\aac di Trento}}
\bibliographystyle{amsalpha}

\maketitle

\begin{abstract}
\noindent We consider the problem of finding the number of permutation non-equivalent classical irreducible maximal Goppa codes
having fixed parameters $q,\,n$ and $r$ from a group theory point of view.

\noindent{\bf Keywords:} Goppa codes, Linear codes, Permutation groups

\end{abstract}

\section{Introduction}

The study of classical Goppa codes is
important since they are a very large class of codes, near to random
codes. They are easy to ge\-nerate and possess an interesting
algebraic structure. For these reasons they are used in McEliece's public key
cryptosystem  \cite{CGC-cd-art-McEli1}. This cryptosystem is based on the difficulty to find a generator matrix of a Goppa code when a "scrambled" of it is known.

In this paper we consider the problem of finding an upper
bound for the number of permutation non-equivalent irreducible maximal Goppa codes. This question was considered by several authors (see for example \cite{CGC-cd-art-chen}, \cite{berger1}, \cite{berger2}, \cite{CGC-cd-art-patjohn1}, \cite{CGC-cd-phdthesis-marta}).
In Section 3 we briefly recall these approaches. In particular, we describe the action of a group $FG$ isomorphic to $A\Gamma L(1,q^n)$ on the $q^n$ columns of a suitable parity-check matrix $H_{\alpha}$. This induces on maximal irreducible Goppa codes the same action which arises from \cite{CGC-cd-phdthesis-john}. This action does not describe exactly the orbits of Goppa codes,
    since in some cases the number of permutation non-equivalent
    Goppa codes is less than the number of orbits of $FG$.
The group $FG$ acts faithfully on columns of $H_{\A}$, so that it may be seen as a subgroup of the symmetric group $\Sqn $. It seems interesting to study if there is a proper subgroup of $\Sqn $ containing $FG$, acting on the set $\Omega $ of classical irreducible maximal Goppa codes of fixed parameters, and giving on $\OO$  exactly the orbits of permutation equivalent codes. In order to consider this problem, we analyze the subgroups of $\Sqn $ containing $FG$ and
in Section 4 we find that there exists exactly one maximal subgroup $M$, isomorphic to $AGL(nm,p)$ of $\Sqn $ ($A_{q^n}$) containing $FG$ ($q=p^m)$. This suggests that one could  consider the action of this $M$ on codes to reach the right bound.

We are grateful to Andrea Caranti, Andrea Lucchini, John A. Ryan and Patrick Fitzpatrick for helpful discussions on this subject.

\section{Preliminaries}
In this section we fix some notation and we recall some basic concepts about linear codes and in particular about Goppa codes. Our main references are \cite{MR1996953} for coding theory and \cite{CGC-alg-book-cameron1} for  group theory.

We denote by $\FF_q$ the finite field with $q$ elements, where $q=p^m$ is a power of a prime $p$; let $N$, $k$, $n$ and $r$ be natural numbers, $k \leq N$.
We consider two extensions of
$\FF_q$, of degree $n$ and $nr$, $\FF_{q^{n}}$ and
$\FF_{q^{{n}r}}$ respectively; $\FF_{q^{n}}[x]$ denotes
the polynomial ring over $\FF_{q^{n}}$
and $\E$ is a primitive element of $\FF_{q^{n}}$, $\FF_{q^{n}}^*=\langle\E\rangle$. We refer to the vector space of dimension $N$ over $\FF_q$ as to $(\FF_q)^N$.

In the following
if $H$ is an $(N-k)\times N$ matrix with entries in $\FF_{q}$
and rank equal to $N-k$, the set $C$ of all
vectors $c \in(\FF_q)^{N}$ such that $H c^T=0$ is an $(N,k)$ {\it
linear} code over $\FF_q$, of {\it length}  $N$ and
{\it dimension} $k$, i.e. a subspace of $(\FF_q)^N$ of dimension $k$. The elements of $C$ are called  {\it codewords} and
matrix $H$ is a {\it parity-check matrix} of $C$.  Any $k \times N$ matrix $G$ whose rows form a
vector basis of $C$ is called a {\it generator matrix} of  $C$.

\begin{definition}
Let $E/K$ be a field extension. A linear code $C$ is called a \textbf{ subfield subcode} if $C$ is obtained as the restriction
to $K^n$ of a linear subspace $L$ of $E^n$.
\end{definition}

By abuse of notation  we call parity-check matrix also a matrix $H$ with entries in $E$  such that $Hc^T=0$ for all $c\in C$. According to this assumption, $H_1$ and $H_2$ may be parity-check matrices for the same code even if their entries are in different extension fields or they have different ranks.

\begin{definition}[\cite{MR1996953}]\label{def:equivalenze:forte}
Let $C_1$ and $C_2$ be two linear codes  over $\FF_q$ of length $N$, let $G_1$ be a generator matrix of $C_1$. Codes $C_1$ and $C_2$ are
\textbf{permutation equivalent} provided there is a permutation $\sigma \in S_N$
of coordinates which sends $C_1$ in $C_2$. Thus $C_1$ and $C_2$ are permutation equivalent provided there is a permutation matrix $P$ such that $G_1P$ is a generator matrix for $C_2$.
They are \textbf{monomially equivalent} provided there is a monomial matrix $M$ so that $G_1M$ is a generator matrix for $C_2$ and
\textbf{equivalent} provided there is a monomial matrix $M$ and an automorphism $\gamma$ of the field $\FF_q$ so that $C_2=C_1M\gamma$.

\end{definition}

If code $C_2$ is
permutation equivalent to $C_1$ with parity-check matrix $H_1$, we can obtain a parity-check
matrix $H_2$  for $C_2$ by permuting columns of $H_1$ (and viceversa).

\begin{definition}\label{goppa:def}
Let $g(x)=\sum g_i x^i\in \mathbb{F}_{q^{n}}[x]$ and let
$L=\{\E_1,\E_2,\LL,\E_N\}$ denote a subset of elements of
$\mathbb{F}_{q^{n}}$ which are not roots of $g(x)$. Then the
\textbf{Goppa code} $\mathcal{G}(L,g)$ is defined as the set of all
vectors $c=(c_1,c_2,\LL,c_N)$ with components in $\mathbb{F}_q$
which satisfy the condition:
\begin{equation}\label{goppa:eq}
\sum_{i=0}^{N}\frac{c_i}{x-\E_i}\equiv 0 \mod\,g(x).
\end{equation}
\end{definition}
Usually, but now always, the set $L=\{\E_1,\E_2,\LL,\E_N\}$ is taken
to be the set of all elements in $\mathbb{F}_{q^{n}}$ which are
not roots of the Goppa polynomial $g(x)$.
In this case the Goppa
code is said \textit{maximal}.
If the degree of $g(x)$ is $r$, then the Goppa code is called a Goppa
code of degree~$r$. It is easy to see
(\cite{CGC-cd-book-macwilliamsI}) that a parity-check matrix for
$\mathcal{G}(L,g)$ is given~by
$$
H=\left(
        \begin{array}{cccc}
            \frac{1}{g(\varepsilon_1)} & \frac{1}{g(\varepsilon_2)} & \LL & \frac{1}{g(\varepsilon_N)} \\
            \frac{\varepsilon_1}{g(\varepsilon_1)} & \frac{\varepsilon_2}{g(\varepsilon_2)} & \LL & \frac{\varepsilon_N}{g(\varepsilon_N)} \\

            \vdots & \vdots & \vdots & \vdots \\
\frac{\varepsilon_1^{r-1}}{g(\varepsilon_1)}
&\frac{\varepsilon_2^{r-1}}{g(\varepsilon_2)} & \LL &
\frac{\varepsilon_N^{r-1}}{g(\varepsilon_N)}\\
\end{array}
    \right).
$$
Note that the code $C=\ker H$ is a subspace of $(\FF_{q^n})^N$ and the Goppa code $\mathcal{G}(L,g)$ is its subfield subcode on $\FF_q$.

\begin{definition}
A Goppa code $\mathcal{G}(L,g)$ is called \textbf{irreducible} if $g(x)$
is irreducible over $\mathbb{F}_{q^{n}}$.
\end{definition}
In the following by Goppa code we mean maximal irreducible classical Goppa code of degree $r$,  so that $N=q^n$. By Definition \ref{goppa:def}, a
vector
$c=(c_1,c_2,\LL,c_{q^{n}})\in(\mathbb{F}_q)^{q^{n}}$ is a
codeword of $\mathcal{G}(L,g)$ if and only if it satisfies
(\ref{goppa:eq}).
If $\alpha$ is any root of $g(x)$, $\A\in \FFqnr$, then
$g(x)=\prod_{i=0}^{r-1}(x-\alpha^{q^{{n}i}})$ and (\ref{goppa:eq}) is equivalent to the $r$ equations
\begin{equation}\label{seconda}
\sum_{i=1}^{q^{n}}\frac{c_i}{\A^{q^{{n}
j}}-\E_i}=0,\,\quad 0\leq j\leq r-1.
\end{equation}

Hence $\mathcal{G}(L,g)$ is completely described by any root $\alpha$ of
$g(x)$ and we may denote this code by $\mathcal{C}(\alpha)$. From (\ref{seconda}) we easily  get a
parity-check matrix $H_{\A}\in Mat_{1\times q^n}(\FFqnr)$ for $\mathcal{C}(\alpha)$ (see \cite{CGC-cd-art-chen}):
\begin{equation}\label{hriga}
H_{\A}=\left(
\begin{array}{cccc}
\frac{1}{\alpha-\E_1}, & \frac{1}{\alpha-\E_2},  & \LL, &
\frac{1}{\alpha-\E_{q^{n}}} \\
\end{array}
\right).
\end{equation}
It is important
to stress that by using parity-check matrix $H_{\A}$ to define
$\mathcal{C}(\alpha)$ we  implicitly fix an order in $L$. So, we set $$L=\{\E,\E^2,\LL,\E^{q^{{n}-1}},\E^{-\infty}\},
$$
where $ \E^{-\infty}=0$, $\E_i=\E^i$  and  the matrix $H_{\A}$ is
$$
H_{\A}=\left(
\begin{array}{ccccc}
\frac{1}{\alpha-\E}, & \frac{1}{\alpha-\E^2},  & \LL, &
\frac{1}{\alpha-1}, &\frac{1}{\alpha}\\
\end{array}
\right).
$$
We observe that the Goppa code $C(\A)$ is the subfield subcode of codes having as parity-check matrices both  $H$ and $H_{\A}$.
Moreover, there exist matrices having  structure different from $H$ and $H_{\A}$, which are parity-check matrices for $C$.

We denote by $\OO=\OO(q,n,r)$  the set of Goppa codes, with fixed
parameters $q,\,n,\,r$.

In the following an action on set $\SSS$ is considered, where $\mathbb{S}=\mathbb{S}(n,r)$ is composed of all elements in
$\mathbb{F}_{q^{{n} r}}$ of degree $r$ over
$\mathbb{F}_{q^{n}}$.

\section{Three actions on $\OO$}
In this section we briefly present semiaffine actions introduced in \cite{berger3} and in \cite{CGC-cd-art-patjohn2}. These actions have degrees $\frac{|\SSS|}{r}$ and $|\SSS|$ respectively. Moreover we consider an action of the group $A\Gamma L(1,q^n)$
on entries of parity-check matrix of type $\HH$. This time the degree is $q^n$.

\vspace{0,5cm}

In \cite{berger3}, the author works directly on polynomials by studying automorphism groups of several classes of codes.

If $\psi\in AG L (1,{q^n})$, $\psi (z)= az+b,\,\, a,b\in \FFqn,\, a\neq 0 $, he defines
$$
g^{\psi}(x)=\sum_{i=0}^rg_i(ax+b)^i.
$$
The map $\psi$ acts also on set $L=\FFqn$, $\FFqn^*=\langle\varepsilon\rangle$, by
$$
L^{\psi}=\left(\E^{\psi^{-1}},\LL, (\E^{q^n-1})^{\psi^{-1}}, (\E^{-\infty})^{\psi^{-1}}\right).
$$
The code $\mathcal{G}(L,g)^{\psi}=\mathcal{G}(L^{\psi},g^{\psi})$ is said the \textit{conjugate} of code $\mathcal{G}(L,g)$ by $\psi$.

\begin{proposition}{\cite{berger3}}\label{prop_berger}
The Goppa codes are invariant by conjugation under the affine group $AGL(1,{q^n})$, i.e. $\mathcal{G}(L,g)^{\psi}=\mathcal{G}(L,g)$ for all $\psi$ such that $\psi(z)=az+b, a,b \in \FF_{q^n}, a\neq0$.
\end{proposition}

We get
\begin{corollary}
Goppa codes $\mathcal{G}(L,g^{\psi})$ is equivalent to Goppa code $\mathcal{G}(L,g)$.
\begin{proof}
We known that $\mathcal{G}(L,g)^{\psi}=\mathcal{G}(L^{\psi},g^{\psi})$ and from Proposition \ref{prop_berger} $\mathcal{G}(L,g)^{\psi}=\mathcal{G}(L,g)$.
From Definition \ref{def:equivalenze:forte} it follows that $\mathcal{G}(L,g^{\psi})$ is equivalent to $\mathcal{G}(L^{\psi},g^{\psi})=\mathcal{G}(L,g)$ so $\mathcal{G}(L,g)$ is equivalent to $\mathcal{G}(L,g^{\psi})$.
\end{proof}
\end{corollary}

More generally, if $\psi \in A\Gamma L(1, q^n)$, $\psi (z)=az^{q^t}+b$, with $a,b \in \FFqn,\, a\neq 0$ ant $t\in \{0,\LL,n-1\}$, we define
\begin{equation}\label{psi}
g^{\psi}(x)=\sum_{i=0}^rg_i(ax^{q^t}+b)^i\;\;
\end{equation}
Equation (\ref{psi}) suggests to consider an action $\sigma$ on $\mathbb{P}\subseteq \FFqn[x]$, where $\mathbb{P}$ is the set of irreducible polynomials of degree $r$. For $g\in \mathbb{P}$, $g^{\sigma(\psi)}$ is the unique  polynomial $f$ of degree $r$ such that $g(\A)=0$ if and only if $f(\beta)=0$ for  $\beta=\left(\frac{\A-b}{a}\right)^{q^{nr-t}}$ (note  $g^{\sigma(\psi)}\in \mathbb{P}$).

Indeed, if $g(x)=\sum_{i=0}^r g_i x^i$, there exist $\bar{g}_i, \forall i=1,\ldots,r,\;  \bar{a},\; \bar{b}$ such that $\bar{g}_i^{q^t}=g_i, \forall i=1,\ldots,r,\; \bar{a}^{q^t}=a,\; \bar{b}^{q^t}=b$ so that
$$\sum_{i=0}^r \bar{g}_i^{q^t} (\bar{a}^{q^t}x^{q^t}+\bar{b}^{q^t})^i=\left(\sum_{i=0}^r \bar{g}_i (\bar{a}x+\bar{b})^{i}\right)^{q^t}=f(x)^{q^t}.$$
    It is immediate to recognize that $g(\A)=0$, for $\A\in\SSS$, if and only if $f(\beta)=0$, with $\beta=\left(\frac{\A-b}{a}\right)^{q^{nr-t}}\in \SSS$.

With similar arguments used for  Proposition \ref{prop_berger}, one gets

\begin{proposition}\label{ber:1}
The Goppa codes are invariant by conjugation under the semiaffine group $A\Gamma L(1,{q^n})$, i.e. $\mathcal{G}(L,g)=\mathcal{G}(L^{\psi}, f)$, where $f=g^{\sigma(\psi)}\in \mathbb{P}$.
\end{proposition}

\begin{corollary}
Goppa codes $\mathcal{G}(L,g)$ is equivalent to Goppa code $\mathcal{G}(L,f)$.
\end{corollary}
\vspace{0,5cm}
In \cite{CGC-cd-phdthesis-john}  the same action on $\OO$ is obtained considering an action on $\SSS$ of an "affine" group $T=AGL(1,q^n)\langle\sigma\rangle$, where $\sigma$ is defined as $\sigma: x\rightarrow x^{q}$; the group $\langle \sigma \rangle$ has order $nr$.
The main result is the following:

\begin{theorem}\cite{CGC-cd-phdthesis-john}\label{alpha-beta}
If $\A,\,\beta\in \mathbb{S}$ are related as it follows
\begin{equation}\label{relazionealphabeta}
\beta=\zeta \A^{q^i} + \xi
\end{equation}
for some $\zeta, \xi \in \FF_{q^{n}},\, \zeta  \neq 0, i= 1\LL nr$, then
$C(\A)$ is equivalent to $C(\beta)$.
\end{theorem}

 Orbits over $\SSS$ give orbits on $\OO$.

\begin{fact}
The above actions on $\SSS$ and on $\mathbb{P}$ create the same orbits on $\OO$.
\end{fact}
\begin{proof}
Let $\A\in\SSS$ be a root of $g(x)\in\mathbb{P}$. Let $\beta=\zeta\A^q+\xi\in \SSS$. There exists an irreducible polynomial $g_1\in \FF_{q^n}[x]$,  such that $g_1(\beta)=0$. From Proposition \ref{ber:1} we get that the orbit  $\A^{FG}=\{ t(\beta ),\,  t \in T\}$) induces on $\OO $ the same  orbit than $g^{T}=\{t( g), t\in T\}$).
\end{proof}

The work in \cite{berger3} is mainly directed to the study of automorphism group of a given code;
\cite{CGC-cd-phdthesis-john} is deeply interested in counting the number of non-equivalent Goppa codes.

In \cite{CGC-cd-phdthesis-john} the exact number of orbits on $\SSS$ is given. Unfortunately, several examples are exhibited where the number of orbits $T$ on $\SSS$ is greater than the number of non-equivalent Goppa codes.

We introduce an action on columns of $H_{\A}= \left(\frac{1}{\alpha-\E},  \frac{1}{\alpha-\E^2},   \LL,\frac{1}{\alpha-1}, \frac{1}{\alpha}\right)$ , which induces the same orbits on $\OO$ than $T$.
We state the results and give a sketch of the proofs.
For more details see \cite{CGC-cd-phdthesis-marta}.

Let us consider the subgroup $FG\simeq A\Gamma L(1, q^n)\leq S_{q^n}$ in its natural action on points of $\FF_{q^n}$. If $\psi \in FG$, then $\psi(x)=ax^{q^i}+b$, where $a,b \in \FFqn$, $a\neq 0$ and $i=1,\LL,n$.
Since each entry (column) of $\HH$ is uniquely determined by an element of $\FFqn$, $A\Gamma L(1, q^n)$ realizes a permutation of $\HH$ entries given by:
$$
\left(\frac{1}{\A-\varepsilon}\right)^{\psi}=\frac{1}{\A-\varepsilon^{\psi}}.
$$
Writing $FG$ we mean  $F=AGL(1,q^n)$ and $G$  the automorphism group of $\FFqn$ over $\FF_q$.

The matrices $H_{\beta}$ and $\zeta H_{\beta}^{q^j}$ are parity-check matrices for the same Goppa code $C(\beta)$.
We characterize the permutations mapping $H_{\A}$ into $\zeta H_{\beta}^{q^j}$ in the following proposition.

\begin{proposition}
Let $H_{\A}$ and $H_{\beta}$ be parity-check matrices for Goppa codes $C(\A)$ and $C(\beta)$. If there exists a
permutation $\rho\in S_{q^{{n}}}$, such that
$\rho(H_{\A})=\zeta (H_{\beta})^{q^j}$, for some $\zeta, \beta \in
\FF_{q^{{n}}}, \zeta \neq 0$ and $j=1,\LL,{{n}}r$, then $\rho
\in {F}{G}$.
\begin{proof}
We consider
$$
\rho (H_{\A})=H'_{\A}=\left( \frac{1}{\A-\E^{i_1}},
\frac{1}{\A-\E^{i_2}}, \cdots ,\frac{1}{\A-\E^{i_{q^{{{n}}}-1}}},
\frac{1}{\A-\E^{i_{-\infty}}} \right),
$$
where $i_j=\rho(j)$ and
matrix $\zeta (H_{\beta})^{q^j}$:
$$
\zeta (H_{\beta})^{q^j}  = \left( \frac{\zeta}{\beta^{q^j}-\E^{q^j}},  \frac{\zeta}{\beta^{q^j}-\E^{2q^j}},  \ldots ,  \frac{\zeta}{\beta^{q^j}-1}, \frac{\zeta}{\beta^{q^j}}\right).
$$
Suppose $\zeta=1$ and ${j=1}$ so that $ \forall
t \in \{1,2,\LL,q^n\}$ we have $
\frac{1}{\beta^{q}-\E^{tq}}=\frac{1}{\A-\E^{i_t}}$ and then $\A-
\beta^q=\E^{i_t}-\E^{tq}$.

If $\A-\beta^q=0$,  $\rho$ is the permutation induced by the Frobenius map $\sigma $, since
$\E^{i_t}=\E^{tq}$; it follows that
$$ \rho(t)= \left\{
\begin{array}{ll}
tq & \mbox{if } t=1,2,\ldots,q^{{n}}-1\\
-\infty & \mbox{if } t=-\infty
\end{array}
\right.
$$
and $\rho={\sigma}.$

If $\A-\beta^q \neq 0$, as above
$\A-\beta^q\in\mathbb{F}_{q^{{n}}}$ so that $\A-\beta^q=\E^k$
for some $k\in \{1,\LL,q^{{n}}-1\}$ and then permutation $\rho
\in {F}{G}$;  explicitly it acts as:
$$
\rho(t)= \left\{
\begin{array}{ll}
i_t= tq +f_k(\E) & \mbox{if } t=1,2,\ldots,q^{{n}}-1\\
i_t= k & \mbox{if } t=-\infty
\end{array}
\right.
$$
where $i_t$ is such that $\E^{i_t}=\E^{tq}+\E^k$, and $f_k(\E)$ is a function depending on representation of $  \FFqn$.

If $\zeta \in \mathbb{F}_{q^{{n}}}^*, {\zeta \neq 1}$
and ${j=1}$, then $\zeta=\E^l$ for some $l \in
\{1,\cdots,q^{{n}}-2\}$. With same arguments used in the
previous step,  we get
$$
\zeta \A -\zeta \E^{i_t}= \beta^q- \E^{tq} \implies
\zeta\E^{i_t}=\zeta\A - \beta^q+ \E^{tq} \implies   \E^{i_t}=\A -
\zeta^{-1}\beta^q+ \E^{tq-l}.
$$
Again $\A - \zeta^{-1}\beta^q\in \FF_{q^{n}}$;  then there is $h
\in \{1,\LL,q^n\}$ so that $\E^{i_t}=\E^{h}+\E^{tq-l}$, and
$$\rho(t)= \left\{
\begin{array}{ll}
i_t= tq-l +f_h(\E) & \mbox{if } t=1,2,\ldots,q^{{n}}-1\\
i_t=h  & \mbox{if } t=-\infty
\end{array}
\right.
$$
where $\E^{i_t}=\E^{tq-l} +\E^h$ and $f_h(\E)$ depending on the representation of $\FF_{q^{n}}$. Concluding $\rho={\tau_{k}
\mu_{\zeta^{-1}} \sigma}$; here $\tau_k$ is the translation defined by $\tau_k:x\rightarrow x+\E^k$,  $\mu_{\zeta }$ is the map   $\mu_{\zeta}:x \rightarrow \zeta x$ and $\sigma $ is the Frobenius map; this proves  $\rho \in FG$.

Finally, if ${j \neq 1}$ we have:
$
\frac{\zeta}{\beta^{q^j}-\E^{tq^j}}=\frac{1}{\A-\E^{i_t}}
$
and $ \zeta \A -\zeta \E^{i_t}= \beta^{q^j}- \E^{tq^j}$. As
$\zeta=\E^l$ for some $l\in\{1,\LL,q^n-2\}$,  we gain:
$$
\E^{i_t}=\A-\E^{-l}\beta^{q^j}+ \E^{tq^j-l}.
$$
So there is $v \in \{ 1,\LL,q^n\}$ such that $ \A -
\E^l\beta^{q^j}=\E^v$ and $\E^{i_t}=\E^{v}+\E^{tq^j-l}.$
Permutation $\rho$ is:
$$
\rho(t)= \left\{
\begin{array}{ll}
i_t= tq^j-l +f_{v}(\E) & \mbox{if } t=1,2,\ldots,q^{{n}}-1\\
i_t=v  & \mbox{if } t=-\infty
\end{array}
\right.
$$
where $\E^{i_t}=\E^{tq^j-l}+\E^v$ and $f_v(\E)$ depends on the representation of $\FF_{q^n}$. Concluding $\rho={\tau_{v}
\mu_{\zeta^{-1}} \sigma^j}.$ Clearly in all cases $\rho\in
{F}{G}$.
\end{proof}
\end{proposition}

\begin{corollary}
Let $H_{\A}$ and $H_{\beta}$ be parity-check matrices for Goppa codes $C(\A)$ and $C(\beta)$. If there exists a
permutation $\rho\in S_{q^{{n}}}$, such that $\rho(H_{\A})=
\zeta H_{\beta}$, for same $\zeta, \beta \in \FF_{q^{n}}, \zeta
\neq 0$, then $\rho\in {F}$.

\end{corollary}
\section{Maximal subgroups}

\def\Aqn{A_{q^n}}
The action of $A\Gamma L(1,q^n)$ does not reach the exact number of non-equivalent maximal Goppa codes. So we look for  maximal subgroups of $S_{q^n}$ containing a fixed $A\Gamma L(1,q^n)=FG$.

\begin{theorem}[\cite{CGC-alg-book-cameron1}]\label{th_cameron1}
A maximal subgroup of $S_{q^n}$ is one of the following:
\begin{enumerate}
\item intransitive, $S_k \times S_l$, $k+l=q^n$;
\item transitive imprimitive: the wreath product $S_k \,Wr\, S_l$ in the  standard action,
$kl=q^n$;
\item primitive non-basic, the wreath product $S_k \,Wr\, S_l$ in the product action,
$k^l=q^n, k\neq 2$;
\item affine $AGL(d,p), p^d=q^n$;
\item diagonal, $T^k.(Out(T)\times S_k$), $T$ non abelian
simple, $|T|^{k-1}=q^n$; here $Out(T)$ denotes, as usual, the factor group $\frac{Aut(T)}{T}$.
\item almost simple, that is an automorphism group $G$ of a finite non abelian simple group $S$, $S\leq G\leq Aut (S)$.
\end{enumerate}
A maximal subgroup of the alternating group is the intersection of one of these groups with the alternating group.

\end{theorem}
\begin{remark}
We explicitly observe that for $p$ even, $d\geq 3$, the group $AGL(d,p)$ is actually contained in the alternating group $A_{p^d}$.
It is sufficient to realize that,  in this case, the translations are product of $2^{d-1}$  cycles of length $2$, as well as the transvections are product of $2^{d-2}$  cycles of length $2$.  As the transvections generate the general linear group $GL(p,2)$, $AGL(p,2)$ is contained in $A_{2^d}$.
\end{remark}

\begin{proposition}\label{AGL}
 $FG $ is contained in  $\Aqn $ if and only if  $q$ is even.
\end{proposition}
\begin{proof}
The thesis follows from the following result.
\begin{claim}\label{Lee}\cite{CGC-alg-Li}
Let $X$ be a primitive permutation group of degree $n$. Then $X$ contains an abelian regular subgroup $G$ if and only if either
\begin{enumerate}
\item [i)] $X \leq AGL(d,p)$, where $p$ is a prime, $d \geq 1$ and $n = p^d$; or
\item [ii)] $X=(\tilde{T_1} \times \LL \times \tilde{T_l})\cdot O \cdot
P$, $G={G_1} \times \LL \times {G_l}$ where $n={m}^l$, $l\geq1$, $G_i
<\tilde{T}_i$, with $|G_i|={m}$, $\tilde{T}_1\cong\LL\cong
\tilde{T}_l$, $O\leq
\mathrm{Out}(\tilde{T}_1)\times\LL\times\mathrm{Out}(\tilde{T}_l)$,
$ P$ is a transitive permutation group of degree $l$ and one of the following holds:
\begin{itemize}
\item[(a)] $(\tilde{T}_i,G_i)=(PSL(2,11),\mathbb{Z}_{11})$,
$(M_{11},\mathbb{Z}_{11})$, $(M_{12},\mathbb{Z}_{2}^2\times
\mathbb{Z}_3)$, $(M_{23},\mathbb{Z}_{23})$ ($M_i$ are the Mathieu groups);
\item[(b)] $\tilde{T}_i=PGL(d,q)$ e $G_i=\mathbb{Z}_{\frac{q^d-1}{q-1}}$
is a Singer group;
\item[(c)] $\tilde{T}_i=P\Gamma L(2,8)$ and
$G_i=\mathbb{Z}_9\nleq PSL(2,8)$;
\item[(d)] $\tilde{T}_i=S_{m}$ or $A_{m}$ and $G_i$ is an abelian group of order ${m}$.
\end{itemize}
\end{enumerate}
  \end{claim}
  Take $X=FG $. $FG$ contains the subgroup $A$ of translations, $A=\{\tau_{\E}:x\rightarrow x+\E\}$, so that $FG$ is contained in $N_{S_{q^n}}(A)=AGL(nm,p)$. By the above remark, if $p=2$, the group  $FG $ is contained in $ \Aqn$. If $p$ is  odd,  then the element $\mu_{\E}:x\rightarrow \E x$ belongs to $FG$ and it is odd, as its order is $q^n-1$ (recall that an element of order $q^n-1$ is said a Singer cycle); this proves that   $FG $ (and $AGL(nm,p)$) is not a subgroup of $\Aqn $.
\end{proof}

\begin{thm} Let $G=\Aqn $  if $q=2^m$,  $G= \Sqn $ for $q$ odd.
If $M$ is a maximal subgroup of $G $ containing $ F G$, then  $M$ is isomorphic to the affine group $AGL(nm,p)$ . Moreover, there is exactly one maximal subgroup containing $  F G$.

\end{thm}

\begin{proof}
As $FG $ is a primitive  $2$-transitive group of $G$,  a  maximal subgroup $M$ of $\Sqn $ containing  $ F G$,  is an almost simple group or it is isomorphic to the affine group $AGL(nm,p)$ (\cite{CGC-alg-book-cameron1}).
In the proof of Proposition \ref{AGL} we have seen that  $FG $ is contained in $AGL(mn,p)$. We prove that it is not contained in an almost simple group. By contradiction, let $M$ be an automorphism group of a simple non abelian group $S$,  $S\leq M\leq Aut (S)$. If $M$ contains $FG$, the stabilizer of a point $\omega$ in  $\FF _{q^n}$ has index $q^n=p^{nm}$. As $S$ is normal in $M$, $S$ is transitive on $\FF _{q^n}$, so that we are reduced to consider subgroups of prime power index in $S$. These were  described by Guralnick and
 for the reader's sake  we write  the main result of \cite{CGC-alg-art-Guralnick1}.
\begin{claim}[\cite{CGC-alg-art-Guralnick1}]\label{Gural}
Let $G$ be a nonabelian simple group with $H<G$ and $[G:H]=p^d=q^n$, $p$ prime. One of the following holds.
\begin{enumerate}
\item $G=A_{q^n}$ and $H\cong A_{q^n-1}$;
\item $G=PSL(s,t)$ and $H$ is the stabilizer of a line or hyperplane. Then $[G:H]=\frac{t^s-1}{t-1}=q^n$ (Note $s$ must be prime);
\item $G=PSL(2,11)$ and $H\cong A_5$;
\item $G=M_{23}$ and $H\cong M_{22}$ or $G=M_{11}$ and $H\cong
M_{10}$;
\item $G=PSU(4,2)\cong PSp(4,3)$, $H$ is the parabolic subgroup of
index 27.
\end{enumerate}
\end{claim}

 Cases 3, 4, 5,  are easily ruled out, as $p^{mn}$ is neither a prime number, nor $27$. Similarly,  case 1 is ruled out when  $p$ is  odd, as, in this case, the element $\mu_{\E}$ is odd.  If $p=2$, then  $FG $ is actually contained  in $M\simeq \Aqn $.
So, we are left with Case 2. Here, we use Claim \ref{Lee}. $X$ satisfies condition ii), with
$$ X=S=PSL(s, t), \qquad [S:H]=\frac{s^t-1}{t-1}=p^{nm},\, \, l=1.$$
  and it is easy to see that it is not the case.

\noindent Now, we prove that there is exactly one subgroup isomorphic to $AGL(nm,p)$ containing $FG $.

Let $q$ be odd:
in $\Sqn $  there is exactly one  conjugacy class of maximal subgroups of this type (see for example \cite{conjugacyaffine}).
So, let $FG \leq M\simeq AGL(nm,p)$, where the normal subgroup of the translation of $M$ is exactly the translation
group $A$ of $FG$ (\cite{CGC-alg-book-hupper1}). The element $\mu_{\E} $ generates a Singer subgroup; it is well known that the Singer cycles are conjugated in $M$; from the knowledge of the overgroups of a Singer cycle \cite{kantor_singer},
\cite{CGC-cd-art-britnellguralnickmaroti}, one easily proves that also  the normalizers of  Singer cycles contained in $M$ are  conjugate in $M$. It follows that if  $FG ^g$, $g\in \Sqn$ is contained in $M$, there exists an element $m\in M$, such that $FG ^g=FG ^m$. So, if $s$ denotes the number of the subgroups of $M$ containing $FG$, we get:
$$[\Sqn :N_{\Sqn}(FG)] = \frac{[\Sqn :M]\cdot [M:N_{M}(FG)]}{s};$$
now, from \cite{CGC-alg-Li} one gets $N_{\Sqn}(FG)\leq M$, so that $s=1$.

Now, suppose $q$ is even. $FG\leq \Aqn$ and in $\Aqn $ the conjugacy class of $S_{q^n}$ subgroups   which are isomorphic to $AGL(nm,p)$. In $A_{q^n}$ $AGL(nm,p)$ splits into two classes so that also the class of Singer cycles splits into two different classes. Same argument used for the odd case leads to the result.
\end{proof}

config: arxiv


TITLE: Generating function of the product of Legendre polynomials
QUESTION [3 upvotes]: The generating function of the product of Legendre polynomials for the same $n$ is given by
\begin{aligned}
\sum_{n=0}^{\infty} z^{n} \mathrm{P}_{n}(\cos \alpha) \mathrm{P}_{n}(\cos \beta)&=\frac{\mathrm{F}\left(\frac{1}{2} ,\frac{1}{2} ;1;\frac{4z\sin \alpha \sin \beta }{1-2z\cos (\alpha +\beta )+z^{2}}\right)}{\sqrt{1-2z\cos (\alpha +\beta )+z^{2}}} \\&=\frac{2K\left(\sqrt{\frac{4z\sin \alpha \sin \beta }{1-2z\cos (\alpha +\beta )+z^{2}}}\right)}{\pi \sqrt{1-2z\cos (\alpha +\beta )+z^{2}}}
\end{aligned}
where $P_n$ is a Legendre polynomial, $F$ is a hypergeometric function and $K$ is a complete elliptic integral of the first kind.
https://www.researchgate.net/publication/269015726_A_generating_function_for_the_product_of_two_Legendre_polynomials
However, in the study of quantum physics, we need the similar result as above for following expression:
\begin{align}
\sum_{n=0}^{\infty} z^{n} \mathrm{P}_{n}(x) \mathrm{P}_{n-1}(x)
\end{align}
Is there any result known? Any hints for this problem would be appreciated.

REPLY [5 votes]: Using the recursion relation
$$
P_{n-1} (x) = x P_n (x) - \frac{x^2 -1}{n} \frac{d}{dx} P_n (x) \ ,
$$
you can reduce your expression to a sum of the generating function you quote and a combined derivative (the $d/dx$) and integral w.r.t. $z$ (to generate the $1/n$) thereof.


TITLE: Given that the graph of $f$ passes through the point $(1, 6)$ and that the slope of its tangent line at $(x, f(x))$ is $2x + 1$, find $f(2)$.
QUESTION [0 upvotes]: As in the title - we assume that the graph of $f$ passes through $(1,6)$ (i.e. $f(1) = 6$) and that the slope of its tangent line at $(x, f(x))$ is $2x + 1$ and we are asked to find $f(2)$.
How does one go about solving for $f(2)$? It would be greatly appreciated if someone could set me off in the right direction :)

REPLY [1 votes]: Find an equation for $f(x)$ by integration
Find the value of the constant using $(1,6)$
Evaluate $f$ at $x=2$


TITLE: If $a_{n}$ has 'a' partial limits and $b_{n}$ has 'b', can $a_{n}+b_{n}$ have more than $ab$ partial limits?
QUESTION [3 upvotes]: EDIT: Apparently I translated the terminology wrong, but partial limit means limit of a subsequence.
If $a_{n}$ has 'a' partial limits and $b_{n}$ has 'b', can $a_{n}+b_{n}$ have more than $ab$ partial limits? ('infinity' also counting as a limit)
This is a homework question. I'm thinking the statement is false, but I have no idea where to begin! Could someone give me a hint?
Thanks!

REPLY [4 votes]: The claim is true if the sequences involved are bounded.
Let $a_{n_k}+b_{n_k}$ be a convergent subsequence of the sum sequence.
Since the sequence $a_{n_k}$ is bounded, it has a converging subsequence $a_{n_{k_i}}$ that converges to some limit point of $a_n$.
This means that $b_{n_{k_i}}$ is the difference of two converging sequences, so it converges as well and its limit is a limit point of $b_n$.
Therefore, the limit of the convergent sequence $a_{n_k}+b_{n_k}$ which is of course the limit of its subsequence is the sum of a limit point of $a_n$ and a limit point of $b_n$.
There are only $a\cdot b$ such sums, therefore the total number is at most $a\cdot b$.


TITLE: Find $\sup\left\{x_n\right\}$ and $\inf\left\{x_n\right\}$ where $x_n= (-1)^n+\cos\frac{n\pi}{4}$
QUESTION [1 upvotes]: Let $\left\{x_n\right\}$ be a sequence such that $x_n= (-1)^n+\cos\frac{n\pi}{4}$. Find $\sup\left\{x_n\right\}$ and $\inf\left\{x_n\right\}$.

$(-1)^n=-1$ (when $n$ is odd), $1$(when $n$ is even).
$\cos\frac{n\pi}{4}= \frac{1}{\sqrt2}$ or $-\frac{1}{\sqrt2}$(when $n$ is odd), $0, 1$ or $-1$(when $n$ is even).
So, from the values, I can directly write $\sup\left\{x_n\right\}=2$ and $\inf\left\{x_n\right\}=-1-\frac{1}{\sqrt2}$.
But I want to know, does the sequence $\left\{x_n\right\}$ converge? If yes, to which point does it converge?
Please anyone help me. Thanks in advance.

REPLY [1 votes]: The sequence does not converge. Note that $x_{n+8} = x_n$, and so the sequence is periodic, but it takes at least two distinct values, so it can never converge to a single value.


TITLE: Suppose N is any positive integer. Add the digits of N to obtain a smaller integer.
QUESTION [0 upvotes]: Suppose N is any positive integer. Add the digits of N to obtain a smaller
integer. Repeat this process of digit-addition till you get a single digit number
n. Find the number of positive integers N ≤ 1000, such that the final
single-digit number n is equal to 5.

REPLY [2 votes]: Let $s(n)$ be the sum of digits function. Then $n\equiv s(n)\pmod{9}$, and by induction
$$
n\equiv s(\cdots(s(n))\cdots)\pmod{9}.
$$
Since the last obtained number is $5$ then it equivalent to find the number of positive integers which have remainder $5$ modulo $9$, i.e., $\lfloor 1000/9\rfloor=111$.


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

This section shows that
(i) the sparse moment relaxation~\eqref{eq:sparseMoment} is tight and can be used to solve small problems (\eg~$N=20$);
(ii)

our \emph{dual optimality certifiers} are effective and scale to larger problems (\eg~$N=100$);

(iii) our algorithms allow solving realistic satellite pose estimation problems.

{\bf Implementation.} We model the sparse moment relaxation~\eqref{eq:sparseMoment}
using YALMIP~\cite{Lofberg04cacsd-yalmip} in Matlab and solve the resulting SDPs using MOSEK~\cite{mosek}. \DRS is implemented in Matlab using $\gamma_{\tau} = 2$.\footnote{The limiting case of $\gamma_{\tau} = 2$ for \DRS is commonly referred to as the \emph{Peaceman-Rachford Splitting} (\PRS)~\cite{Combettes11book-proximalSplitting}. Although theoretically \PRS could diverge, we found it worked well for all our applications.}

{\bf Setup.} We test primal relaxation and dual certification on {random} problem instances of Examples~\ref{eg:singleRotationAveraging}-\ref{eg:meshRegistration}: single rotation averaging (\singlerotation),
shape alignment (\shapealign),
point cloud registration (\pointcloud),
and mesh registration (\mesh).
At each Monte Carlo run, we randomly sample a ground truth model $\vxx$ and
generate inliers by perturbing the measurements with Gaussian noise with standard deviation $\sigma$.
We choose $\sigma = 3^\circ$ in \singlerotation, and
$\sigma = 0.01$ in \shapealign, \pointcloud, and \mesh.
Outliers are generated as arbitrary rotations or vectors (independent on $\vxx$).

 The relative weight between point-to-plane distance and normal-to-normal distance in \mesh is set to $w_i = 1,i=1,\dots,N$.
 The threshold in problem~\eqref{eq:generalTLS} is set to $\barc=1$ for all applications, and $\beta_i,i=1,\dots,N$, is set to
 be proportional to the inlier noise. \edit{The interested reader can find more details about the setup in the \supp.}

\input{fig-relax_certify_converge_satellite}

{\bf Primal Relaxation.}
\label{sec:experiments:relaxation}
We first evaluate the performance of the sparse moment relaxation~\eqref{eq:sparseMoment} under increasing outlier rates, with
 $N=20$ measurements. Fig.~\ref{fig:relax_certify_converge_satellite}(a) shows the boxplots of rotation estimation errors and relative duality gap for \singlerotation (top), \shapealign (middle), and \mesh (bottom) averaged over 30 Monte Carlo runs (results for \pointcloud are qualitatively \edit{similar to \mesh} and hence postponed to the \supp). The sparse moment relaxation is numerically tight (relative gap smaller than $10^{-3}$),
 with a single instance exhibiting a large gap (mesh registration, $80\%$ outliers).
 The figure also shows that the relaxation produces an accurate estimate in all tested instances. \final{In the \supp, we show our primal relaxation is tight even under \emph{adversarial outliers}.}

{\bf Dual Certification.}
\label{sec:experiments:certification}
We test our dual optimality certifiers under increasing outlier rates, with
 $N=100$ measurements.

In each Monte Carlo run, we first use \GNC~\cite{Yang20ral-GNC} as a fast heuristics to compute a candidate solution to the POP~\eqref{eq:pop}, and then run the proposed dual certifiers (Theorem~\ref{thm:DRSOptimalityCertification}) to compute a suboptimality gap. Fig.~\ref{fig:relax_certify_converge_satellite}(b) plots the number of runs when \GNC returns the \emph{correct} solutions (\ie~with rotation error less than $5^\circ$), and the number of runs when the solutions are \emph{certified} (\ie~have suboptimality below $1\%$). We can see that our dual certifiers can certify all correct solutions and reject all incorrect estimates (the blue and green bars always have same height,
meaning that there are no false positives nor false negatives). Fig.~\ref{fig:relax_certify_converge_satellite}(c) plots the average convergence history of the suboptimality gap versus the number of \DRS iterations (in log-log scale). \DRS drives the suboptimality below $1\%$ within 1000 iterations (within 100 iterations for \singlerotation) if the solution is correct, while it reports a suboptimality larger than $10\%$ if the solution is incorrect. \final{In the \supp, we show our certification outperforms the statistical Kolmogorov–Smirnov test~\cite{Massey51JASA-KStest}.}

{\bf Which One is More Scalable?}

\label{sec:experiments:scalability}
Table~\ref{table:timing} compares the scalability of the sparse relaxation and the dual certification for increasing number of measurements.
Solving the large-scale SDP quickly becomes intractable for moderate $N$, while certification using \DRS can scale to large number of measurements.

\input{table-timing}

\vspace{2mm}
{\bf Satellite Pose Estimation.}
\label{sec:experiments:satellite}

Satellite pose estimation using monocular vision is a crucial technology for many space operations~\cite{Sharma19arXiv-SPEED,Chen19ICCVW-satellitePoseEstimation}.
We use ``Shape Alignment (Example~\ref{eg:shapeAlignment})'' to perform 6D pose estimation from satellite images in the \SPEED dataset~\cite{Sharma19arXiv-SPEED} (see Fig.~\ref{fig:relax_certify_converge_satellite}(d)). Towards this goal, we first use the pre-trained network from~\cite{Chen19ICCVW-satellitePoseEstimation} to detect 11 pixel measurements corresponding to 3D keypoints of the Tango satellite model.
Because the network outputs fairly accurate detections (all inliers), we also replace $0\%,18\%,35\%,49\%,62\%$, and $73\%$ \emph{pairwise} inliers (see \supp) with random outliers to test more challenging instances. We show a correct and certified estimation with $62\%$ outliers in Fig.~\ref{fig:relax_certify_converge_satellite}(d) top panel, and an incorrect and non-certified estimation with $73\%$ outliers in Fig.~\ref{fig:relax_certify_converge_satellite}(d) middle panel. Fig.~\ref{fig:relax_certify_converge_satellite}(d) bottom panel plots the statistics of the rotation error over 20 satellite images \edit{(showing the relation between suboptimality and estimation errors)}.
We refer the reader to the \supp for a more comprehensive description of the tests and the results.
\optional{Then we form \emph{pairwise} measurements: $\vz_{ij} = \tldvz_i - \tldvz_j$ and $\MB_{ij} = \tldMB_i - \tldMB_j$ for all $i \neq j$, which gives rise to $N=\nchoosek{11}{2} = 55$ measurements that satisfy the \shapealign model in example~\ref{eg:shapeAlignment} (the translation cancels due to the subtraction). We then use \GNC to estimate $s$ and $\MR$, followed by using the adaptive voting algorithm in~\cite{Yang19rss-teaser} to estimate a 2D translation ($s$ is approximately the inverse of the depth in weak perspective camera model).}{}


TITLE: How do I can simplify the below intersection?
QUESTION [1 upvotes]: let $S$ be a sphere defined by this equation :$ \left(x-\frac{4}{3}\right)^2+\left(y-\frac{1}{3}\right)^2+\left(z-\frac{5}{3}\right)^2=\frac{25}{36}$ and $(p)$ the plane defined by the following equation :$2x+y-2z+4=0$ ,

My question here is : How do I can get the intersection between $(p)$ and $(S)$?  By the way I want to get the center and the radius of the circle which it is the geometrical intersection of $(p)$ and $(S)$ .

Attempt : I took $y=2(z-x-2)$ from the equation of $(p)$ and by substitution in $(S)$ I have got this complicated form

REPLY [0 votes]: It is worth it to try to solve the general problem, instead of this specific one.
Since we know the center of the sphere $(x_C,y_C,z_C)$, we can transform the coordinates such that the origin is at the sphere center: $x=x'+x_C,\,y=y'+y_C,\,z=z'+z_C$.
Sphere:
$$ x'^2 + y'^2 + z'^2 - R^2 = 0$$
Plane:
$$  a x' + b y' + c z' + d' = 0 $$ where $ d'= a x_C + b y_C + c z_C +d$
So for every value of $x'$ and $y'$ the value of $z'$ is calculated such that it lies on the plane $$z' = - \frac{a x'+b y'+d'}{c} $$
which is used in the equation of the sphere to intersect with the plane
$$ C(x',y') = x'^2 + y'^2 + \left(- \frac{a x'+b y'+d'}{c}  \right)^2 - R^2 =0 $$
Now we can find the center of the circle by solving this 2×2 system for $x'$ and $y'$
$$ \begin{Bmatrix} \frac{\partial }{\partial x'} C(x',y') =0 \\ \frac{\partial }{\partial y'} C(x',y') =0 \end{Bmatrix} $$
$$ \mbox{center} = \begin{Bmatrix}  -\frac{a d'}{a^2+b^2+c^2} \\ -\frac{b d'}{a^2+b^2+c^2} \\ -\frac{c d'}{a^2+b^2+c^2} \end{Bmatrix} $$
The circle radius $r$ is found from the distance of the plane to the center of the circle. This distance is $$t = -\frac{d'}{\sqrt{a^2+b^2+c^2}}$$
and from trigonometry we know that $R^2 = r^2 + t^2$ so the radius of the circle is $$ r = \sqrt{R^2 -t^2}$$


TITLE: prove that there is no $\varphi \in C([0,1], \mathbb{R})$ such that $||\varphi|| = |L(\varphi)|$
QUESTION [0 upvotes]: Define the functional $L:C([0,1], \mathbb{R}) \rightarrow \mathbb{R}$ by $L(\varphi) = \displaystyle\int_0^{1/2}\varphi(t)dt - \displaystyle\int_{1/2}^{1}\varphi(t)dt$. we consider in $C([0,1], \mathbb{R})$ the supremum norm. I have showed that $||L|| = 1$, however I couldn't show that there is no $\varphi \in C([0,1], \mathbb{R})$ such that $||\varphi|| = |L(\varphi)|$.
This exercise was proposed before the Hanh-Banach Theorem, so I don't know if you need this Theorem. Does anyone have any idea how to do?

REPLY [1 votes]: The only $L^\infty$ function with $|L(\varphi)|=||\varphi||$ is
$$
\varphi_1(x)=
\begin{cases}
||\varphi_1||,& 0\leq x \leq 1/2 \\
-||\varphi_1||,&  1/2<x\leq 1
\end{cases}
$$
almost everywhere (and all constant multiples). Obviously, this function is not continuous.


TITLE: Injectivity of rationalization on spectrum morphisms
QUESTION [3 upvotes]: Let $E$ and $F$ be two spectra, and let $j \colon F \to F_{\mathbb Q} = F \wedge H \mathbb Q$ be the rationalization of $F$.
Assume that the group of morphisms $[E, F]$ in the stable homotopy category is torsion free. Consider the natural map $j_* \colon [E, F] \to [E, F_{\mathbb Q}]$. If $E$ is finite, I think, $j_*$ is just the rationalization of the abelian group $[E, F]$, so is injective, since $[E, F]$ has no torsion.
Question. Is $j_*$ injective without the finiteness assumption on $E$ (if $[E, F]$ is torsion free)?
Is it true at least for bounded below $E$ and $F$ of finite type (i.e. with finitely generated homotopy groups)?

REPLY [3 votes]: As user171227 is pointing out, you are asking about the map
$$ F^0(E) \rightarrow F\mathbb Q^0(E).$$
This always factors as
$$ F^0(E) \rightarrow F^0(E) \otimes \mathbb Q \rightarrow F\mathbb Q^0(E).$$
The first map is injective if and only if $F^0(E)$ is torsion free, while the composite is injective if and only if the second map is also injective.
And happily, that second map often isn't, even when the first map is! It would have made the character theory that Mike Hopkins, Doug Ravenel, and I wrote about nonexistent, with $F$ equal to a Morava $E$-theory and $E = BG$. (This includes user17227's example:  $K(BG)$ is always torsion free.)


TITLE: Ultrafilter condition: If A is a subset of X, then either A or X \ A is an element of U
QUESTION [3 upvotes]: My confusion concerns ultrafilters on sets that are themselves power sets.
If $X=\{\emptyset,\ \{1\},\ \{2\},\ \{3\},\ \{4\},\ \{1,2\},\ \{1,3\},\ \{1,4\},\ \{2,3\},\ \{2,4\},\ \{3,4\},\ \{1,2,3\},\ \{1,2,4\},\ \{1,3,4\},\ \{2,3,4\},\ \{1,2,3,4\}\ \}$ and the upset $\{1\}=U=\{\ \{1\},\ \{1,2\},\ \{1,3\},\ \{1,4\},\ \{1,2,3\},\ \{1,2,4\},\ \{1,3,4\},\ \{1,2,3,4\}\ \}$ is supposedly a principal ultrafilter (for visual delineation see https://en.wikipedia.org/wiki/Filter_%28mathematics%29), then how do I satisfy the criteria that "If $A$ is a subset of $X$, then either $A$ or $X\setminus A$ is an element of $U$"?
For example, could I let $A=\{\emptyset,\{2\}\}$ such that $A\notin U$, but $X\setminus A\notin U$ because $\{2,3,4\}\in X\setminus A,\{2,3,4\}\notin U$?
My understanding of the distinction between an element and a subset is unrefined, particularly with regard to power sets.

REPLY [5 votes]: You’ve completely confused elements and subsets, I’m afraid. $X$ here is the set $\{1,2,3,4\}$, and what you called $X$ is actually $\wp(X)$, the power set of $X$, i.e., the set of all subsets of $X$. Your $A$ is not a subset of $X$; it’s a subset of $\wp(X)$. A couple of subsets of $X$ are $A_1=\{1,3\}$ and $A_2\{2,4\}$. As you can see, $A_1\in U$; $A_2\notin U$, but $X\setminus A_2=A_1$ is an element of $U$.

REPLY [2 votes]: It is fine to have filters on a power set of another set. But then the filter is a subset of the power set of the power set of that another set; rather than our original set which is the power set of another set.
But in the example that you gave, note that $W\in U$ if and only if $\{1\}\in W$. Indeed $\{1\}\notin A$, but therefore it is in its complement and so $X\setminus A\in U$.
If things like that confuse you, just replace the sets with other elements, $1,\ldots,16$ for example, and consider the ultrafilter on that set. Then simply translate it back to your original $X$.


TITLE: Bounds on the sum of the elements of unit-length complex vector
QUESTION [1 upvotes]: Given an $n$-element complex vector $\mathbf{x}=[x_1,\ldots,x_n]\in\mathbb{C}^n$, where $\|\mathbf{x}\|_2^2=\sum_{i=1}^n|x_i|^2=1$, I am wondering if anything can be said about the product $A\bar{A}$ of the sum of its elements $A=\sum_{i=1}^nx_i$ and the complex conjugate $\bar{A}$.
The Cauchy-Schwartz inequality yields a trivial upper bound $A\bar{A}\leq n$, however, I am wondering if this can somehow be sharpened.  Any ideas?

REPLY [1 votes]: No, the bound is sharp. Consider the unit vector
$$\mathbf{x} = \left(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right) \in \mathbb{C}^2$$
Since the elements are all real, $A = \overline{A} = \frac{2}{\sqrt{2}} = \sqrt{2}$.
So $A\overline{A} = 2 = n$. I think the real case is always the one to look at in situations like this, since the "interference" provided by complex multiplication is negative.


TITLE: Write the ODE $\ddot{x}+k\dot{x}+V'(x)=0$ as a system
QUESTION [1 upvotes]: Write the ODE $\ddot{x}+k\dot{x}+V'(x)=0$ as a system.

Here, $\dot{x}$ is differentiation with respect to $t$. I wrote this as $$\begin{pmatrix} \dot{x}\\\dot{u}\\\dot{1}\end{pmatrix}=\begin{pmatrix}0&1&0\\0&-k&-V'(x)\\0&0&0\end{pmatrix}\begin{pmatrix} x\\u\\1\end{pmatrix}$$ where $\dot{x}=u$.
Is this the correct representation. I'm not sure because of the extra row that I had to add to the system.

REPLY [0 votes]: The equation
$\ddot x + k \dot x + V'(x) = 0 \tag 1$
cannot in general be wrtten as a linear system (as proposed in the original question, before the present edits were in effect), for the simple reason that $V'(x)$ is not in general a linear function of the variable $x$.
We can however write (1) as a first order system, in which only the first derivative(s) of the state variable(s) are present, by denoting
$\dot x$ by $y$:
$y = \dot x, \tag 2$
whence
$\dot y = \ddot x; \tag 3$
then (1) may be expressed in the form
$\dot y + ky + V'(x) = 0, \tag 4$
that is,
$\dot y = -ky - V'(x); \tag 5$
this together with (2) form a first order system in the two variables $x(t)$ and $y(t)$; such systems are often writen in vector-field form; that is, we may define a vector field $\mathbf X(x, y)$ on $\Bbb R^2$ by
$\mathbf X(x, y) = \begin{pmatrix} y \\ -ky - V'(x) \end{pmatrix}; \tag 6$
then setting
$\mathbf r = \begin{pmatrix} x \\ y \end{pmatrix} \tag 7$
we have
$\dot{\mathbf r} = \begin{pmatrix} \dot x \\ \dot y \end{pmatrix} = \begin{pmatrix} y \\ -ky - V'(x) \end{pmatrix} = \mathbf X(x, y). \tag 8$


TITLE: if $x^2=y^3$, then $x=a^3$ and $y=b^2$
QUESTION [0 upvotes]: We are given that $x^2 = y^3$ and that $x,y$ are positive integers.
We need to show that there are $a,b$ positive integers such that
$x=a^3$, and $y=b^2$.
I tried to do modular arithmetic in order to solve this problem but I got nowhere. I can't see how one would proceed for this question.
Any help is greatly appreciated

REPLY [4 votes]: As $x^2=y^3$, $y^3$ is a perfect square. Hence all its prime factors have an even multiplicity. At the same time, these multiplicities are multiple of $3$, hence they are multiple of $6$. Both $x^2$ and $y^3$ are perfect sixth powers, from which the claim follows.


TITLE: Maximizing the trace in an elegant way
QUESTION [5 upvotes]: Suppose $\Lambda = {\rm diag}(\lambda_1,\cdots,\lambda_n)$, $\Sigma = {\rm diag}(\sigma_1,\cdots,\sigma_n)$, and we have $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq 0$ and $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_n \geq 0$. I want to prove that
$${\rm max}[ {\rm Tr}(O^{\rm T}\Lambda O \Sigma)] = \sum_{i=1}^n \lambda_i \sigma_i,$$
where $OO^{\rm T} = I$. One approach is to maximize the function
$$f(o_{ij}) = \sum_{i,j} \lambda_i (o_{ij})^2 \sigma_j$$
under the constraint $\sum_{k} o_{ik}o_{jk} = \delta_{ij}$ by Lagrange multiplier method. I can prove the statement in this way but the whole proof is lengthy and lack of the flavor of linear algebra. Since the statement "must be true" intuitively, I want to know if there is an elegant way to prove it. A possible way may be mathematical induction but I failed to make it. Any help is appreciated.

REPLY [1 votes]: It seems that the answer given by user1551 is the most appropriate one. The approach using calculus is in detailed in his answer. But another approach using Birkhoff theorem suggested in his comments is rough. I read through the linked answer given by him and try to give an informal summary here to help those interested.
Double stochastic matrix and Birkhoff–von Neumann theorem
Double stochastic matrix is a square matrix $A=(a_{ij})$ of nonnegative real numbers, each of whose rows and columns sums to 1, i.e.
$$\sum _{i}a_{ij}=\sum _{j}a_{ij}=1.$$
The Birkhoff–von Neumann theorem states that if $A$ is doubly stochastic matrix, then there exist $\theta _{1},\ldots ,\theta _{k}\in (0,1)$ and $\theta _{1} + \ldots + \theta _{k} = 1$ and permutation matrices $P_{1},\ldots ,P_{k}$ such that
$$A=\theta _{1}P_{1}+\cdots +\theta _{k}P_{k}.$$
The proof of the Birkhoff–von Neumann theorem can be found here. It applys the Hall's marriage theorem in graph thoery. The proof of the Hall's marriage theorem can be found here. I have never learned any graph theory before, but I find that the proof given by the link is not hard to follow if you have learned linear algebra. And the proof is also very inspiring and ingenious!
Proof of the statement by Birkhoff–von Neumann theorem
If $OO^{\rm T} = I$, we define $Q \equiv (q_{ij}) = (o_{ij})^2$. It is easy to find that $Q$ is double stochastic matrix. Since
$${\rm Tr}(O^{\rm T}\Lambda O\Sigma) = \sum_{i,j}\lambda_i \sigma_j (o_{ij})^2 = \sum_{i,j}\lambda_i \sigma_j q_{ij},$$
we have
$$\max_{OO^{\rm T} = I}{\rm Tr}(O^{\rm T}\Lambda O\Sigma) \leq \max_{A} \sum_{i,j}^n\lambda_i \sigma_j a_{ij}, A \mbox{ is double stochastic}
.$$
In light of Birkhoff–von Neumann theorem, we have
$$A=\sum_{l=1}^{k}\theta_l P_{l},$$
where $\theta _{1},\ldots ,\theta _{k}\in (0,1)$ and $\theta _{1} + \ldots + \theta _{k} = 1$. So we have
$$\sum_{i,j}\lambda_i \sigma_j a_{ij} = \sum_{l=1}^{k} \theta_{l} \sum_{i,j}\lambda_i \sigma_j p_{ij} .$$
Among all $n!$ permutation matrices, it is easy to check $\sum_{i,j}\lambda_i \sigma_j p_{ij}$ has maximum value $\sum_{i}\lambda_i \sigma_i$ when $p_{ij} = \delta_{ij}$. So we have
$$\max_{A} \sum_{i,j}\lambda_i \sigma_j a_{ij} = \sum_{i}\lambda_i \sigma_i.$$
On the other hand, we have ${\rm Tr}(O^{\rm T}\Lambda O\Sigma) = \sum_{i}\lambda_i \sigma_i$ when $O = I$, so we can conclude that
$$\max_{OO^{\rm T} = I}{\rm Tr}(O^{\rm T}\Lambda O\Sigma) = \sum_{i}\lambda_i \sigma_i.$$
Thanks a lot to user 1551 for showing me these exciting new knowledge!


TITLE: How to get the expression for higher order derivatives systematically
QUESTION [2 upvotes]: Given an expression, for example,
$$f(x,y)=\frac{x}{(x-1)(1-y)(xy+x-1)}$$
How can we find the general expression involving $m$ and $n$ for $$\lim_{x\to 0, y\to 0}{\frac{\partial^{n+m}{f}}{\partial{x}^{m}\partial{y}^{n}}}$$

REPLY [2 votes]: Suppose $f = \sum_{i,j \geq 0} c_{ij} x^i y^j$. The limit you're looking for is $m!n! c_{mn}$. Your function is better written as $$f(x,y) = \frac{x}{(1-x)(1-y)(1-x-xy)},$$ where the most interesting factor is $$\frac{1}{1-x-xy} = \sum_{t \geq 0} x^t(1 + y)^t = \sum_{t,s \geq 0} \binom{t}{s} x^t y^s.$$ Multiplying by a variable $1/(1-z)$ is like taking "running sums" across $z$. So $$\frac{x}{(1-x)(1-y)(1-x-xy)} = \sum_{t,s \geq 0} x^{t+1} y^s \left[ \sum_{T \leq t, S \leq s} \binom{T}{S} \right]. $$ So the value you're looking for is $$m!n!\sum_{T \leq m-1,S \leq n} \binom{T}{S}.$$


TITLE: Is there a problem book similar to Polya & Szego's classic in the field of real analysis
QUESTION [1 upvotes]: I'm going to learn real analysis, and I'm using the textbook written by Elias E. Stein(the 3rd in his series). When studing complex analysis, I find that Polya & Szego's book "Problems and Theorems in Analysis I/II" is very useful. So is there any book which consists of problems that is similar to Polya & Szego's?

REPLY [0 votes]: Yes, 'Problems in Mathematical Analysis', written by Kaczor and Nowak. There are four parts of it, but in libgen, three parts are available. I couldn't find the fourth part anywhere. These books are really awesome, loaded with beautiful problems. You can go for it.


TITLE: Difference of 2 notations with powerset
QUESTION [1 upvotes]: Let $\mathbb{N}, \mathbb{V}$ two sets, $\mathcal{P}(\ldots)$ means the power set of a set.
$\mathcal{P}({\mathbb{N}})\rightarrow \mathbb{V}$ can be the type of a function mapping a part of $\mathbb{N}$ into $\mathbb{V}$. I think $\mathcal{P}({\mathbb{N}})\rightarrow \mathbb{V} = \mathcal{P}({\mathbb{N}} \rightarrow \mathbb{V})$ always holds. Could anyone tell me what is the difference between these 2 notations? Is $\mathcal{P}({\mathbb{N}})\rightarrow \mathbb{V}$ always more conventional than $\mathcal{P}({\mathbb{N}} \rightarrow \mathbb{V})$?

REPLY [3 votes]: Assuming that $\Bbb{N\to V}$ indicates the set of functions from $\Bbb N$ to $\Bbb V$, then the sets are not even the same.

In $\cal P(\Bbb{N)\to V}$ we have functions mapping subsets of $\Bbb N$ to $\Bbb V$.
In $\cal P(\Bbb{N\to V})$ we have sets of functions from $\Bbb N$ to $\Bbb V$.


TITLE: Find an example of a function $f:\mathbb R\to\mathbb R$ that is non bounded and nowhere continuous.
QUESTION [1 upvotes]: We have to find an example of a function $f:\mathbb R\to\mathbb R$ that is non bounded and nowhere continuous.
My try:I think its "Dirchilet discontinuous " function.Plz check.

REPLY [2 votes]: How about
$$f(x) = \begin{cases}
1+|x|, & x\ne \Bbb Q\\
0, & x\in\Bbb Q
\end{cases}$$
?


text:
\section{Background}
\subsection{Notation}
We denote by $\mathbb{R}$, $\mathbb{R}^{n}$ and $\mathbb{R}^{n \times m}$ the real numbers, $n$-dimensional real vectors and $n \times m$ dimensional real matrices, respectively. The interior of a set  is denoted by $\text{int}(\cdot)$ and $\left \lfloor x \right \rfloor$ denotes the \emph{floor} operation, i.e. the rounding to the nearest lower integer. The composition of two functions $f$, and $g$ is denoted by $g\circ f(x) = g(f(x))$.

\subsection{Explicit MPC}
Model predictive control (MPC) is an optimal control scheme that uses a system model to predict the future evolution of a system.
We consider discrete linear time-invariant (LTI) systems:
\begin{align}\label{eq:LTI}
x_{k+1} = Ax_k + Bu_k,
\end{align}
where $x \in \mathbb{R}^{n_x}$ is the state vector, $u \in \mathbb{R}^{n_u}$ is the control input, $A \in \mathbb{R}^{n_x \times n_x}$ is the system matrix, $B \in \mathbb{R}^{n_x \times n_u}$ is the input matrix and the pair $(A,B)$ is controllable.
The LTI system has state and input constraints
\begin{align}\label{eq:LTI_constraints}
x_k \in \mathcal{X}, \, u_k \in \mathcal{U}, \quad \forall k \in \mathbb{N},
\end{align}
where the polytopes $\mathcal{X} \subset \mathbb{R}^{n_x}$ and $\mathcal{U} \subset \mathbb{R}^{n_u}$ contain the origin in their interior.
From the system description \eqref{eq:LTI} and the constraints \eqref{eq:LTI_constraints} a constrained finite time optimal control problem can be derived as in \cite{} considering a horizon of $N$ prediction steps:

\begin{subequations}\label{eq:FTOCP}
	\begin{align}
		&\underset{\tilde u}{\text{minimize}} && x_N^T P x_N + \sum_{k=0}^{N-1}{x_k^T Q x_k + u_k^T R u_k} \span \span \span \\
		&\text{subject to} &&x_{k+1} = Ax_k + Bu_k, \\
		&            &&C_x x_k \leq c_x,\, C_f x_N \leq c_f, \label{eq:state_terminal_cons}\\
		&            &&C_u u_k \leq c_u, \label{eq:input_cons}\\

		&			 &&x_0 = x_{\text{init}}, \\
		& && \forall \,\, k = 0,\dots, N-1,
	\end{align}
\end{subequations}

where $\tilde u = \{u_0, \dots, u_{N-1}\}$ is the sequence of the control inputs and $P \in \mathbb{R}^{n_x \times n_x}$, $Q \in \mathbb{R}^{n_x \times n_x}$ and $R \in \mathbb{R}^{n_x \times n_u}$ are the weighting matrices. $P \succeq 0$ and $Q \succeq 0$ have to be positive semidefinite, and $R \succ 0$ has to be positive definite.
The optimization problem \eqref{eq:FTOCP} can be reformulated as a multi-parametric problem \cite{bemporad2002} depending on the current system state $x_{\text{init}}$:
\begin{subequations}\label{eq:FTOCP_condensed}
	\begin{align}
		&\underset{\tilde u}{\text{minimize}}&& \tilde u^T F \tilde u + x_{\text{init}}^T G \tilde u + x_{\text{init}}^T H x_{\text{init}} \span \\
		&\text{subject to} && C_c \tilde u \leq T x_{\text{init}} + c_c,
	\end{align}
\end{subequations}
where $F \in \mathbb{R}^{N n_u \times N n_u}$, $G \in \mathbb{R}^{n_x \times N n_u}$, $H \in \mathbb{R}^{n_x \times n_x}$, $C \in \mathbb{R}^{N n_{\text{ineq}} \times N n_u}$, $T \in \mathbb{R}^{N n_{\text{ineq}} \times n_x}$, $C \in \mathbb{R}^{N n_{\text{ineq}} \times N n_u}$ and $n_{\text{ineq}}$ is the number of inequalities.
This multi-parametric quadratic programming problem can be transformed into a piece-wise affine (PWA) function
\begin{align}
\mathcal{K}(x_{\text{init}}) =
	\begin{cases}
		K_1 x_{\text{init}}+g_1 & \text{if} \quad x_{\text{init}} \in \mathcal{R}_1, \\
		& \vdots \\
		K_r x_{\text{init}}+g_r & \text{if} \quad x_{\text{init}} \in \mathcal{R}_r,
	\end{cases}
\label{eq:exp_mpc}
\end{align}
with $K_i \in \mathbb{R}^{n_u \times n_x}$ and $g_i \in \mathbb{R}^{n_u}$.
Each region is described by a polyhedron
\begin{align}
\mathcal{R}_i = \{x \in \mathbb{R}^{n_x} \mid Z_i x \leq z_i\} \quad \forall i = 1,\dots,n_r,
\end{align}
where $Z_i \in \mathbb{R}^{c_i \times n_x}$, $z_i \in \mathbb{R}^{c_i}$ describe the $c_i$ half-spaces of the $i$-th region.
The formulation \eqref{eq:exp_mpc} is defined on the polytopic partition $\mathcal{R}_\Omega = \cup_{i=1}^{n_{\text{r}}} \mathcal{R}_i$ with $\text{int}(\mathcal{R}_i) \cap \text{int}(\mathcal{R}_j) = \emptyset$ for all $i \neq j$.

\subsection{Artificial Neural Networks}
We shortly recap in this subsection the fundamental concepts of artificial neural networks.
\begin{definition}[Neural network]
We define feed forward deep neural networks as a sequence of layers of neurons which define a function $\mathcal{N}:\mathbb{R}^{n_x} \rightarrow \mathbb{R}^{n_u}$ of the form
\begin{align}\label{eq:neural_network}
\mathcal{N}(x;\theta,M,L) = f_{L+1} \circ g_L \circ f_L \circ \dots \circ g_1 \circ f_1(x),
\end{align}
where the input is $x \in \mathbb{R}^{n_x}$ and the output is $ u \in \mathbb{R}^{n_u}$.
$M$ is the number of neurons in each hidden layer and $L$ is the number of hidden layers.
If $L\geq2$, we describe $\mathcal N$ as a \emph{deep} neural network and if $L=1$ as a \emph{shallow} neural network.
Each hidden layer consists of an affine function:
\begin{align}\label{eq:affine_function}
f_l(x_{l-1}) = W_lx_{l-1}+b_l,
\end{align}
where $x_{l-1} \in \mathbb{R}^M$ is the output of the previous layer and a non-linear activation function $g_l$.
In this paper, we consider exclusively rectifier linear units (ReLU) as activation function, which compute the element-wise  maximum between zero and the affine function of the current layer $l$:
\begin{align}\label{eq:ReLU}
g_{l}(f_{l}) = \max(0,f_{l}).
\end{align}
The parameter $\theta = \{\theta_1, \dots, \theta_{L+1}\}$ contains  all the weights and biases of the affine functions of each layer
\begin{align}
\theta_l = \{W_l,b_l\} \quad \forall l = 1, \dots, L+1,
\end{align}
where the weights are
\begin{align}
W_l \in
	\begin{cases}
		\mathbb{R}^{M \times n_x} & \text{if} \quad l=1, \\
		\mathbb{R}^{M \times M} & \text{if} \quad l=2,\dots,L, \\
		\mathbb{R}^{n_u \times M} & \text{if} \quad l=L+1,
	\end{cases}
\end{align}
and the biases are
\begin{align}
b_l \in
	\begin{cases}
		\mathbb{R}^M & \text{if} \quad l=1,\dots,L, \\
		\mathbb{R}^{n_u} & \text{if} \quad l = L+1.
	\end{cases}
\end{align}
\end{definition}

\subsection{Motivation}

Implementing the explicit model predictive controlller \eqref{eq:exp_mpc} requires storing, the set $\mathcal{E} = \{Z_i,z_i,K_i,g_i\}$ that defines the regions and affine controllers in each region.
The number of regions can grow exponentially with respect to the horizon and the number of constraints which leads to large memory requirements that can prohibit the application of explicit MPC for larger case studies.

The main motivation of this work is to find an efficient representation and approximation of the MPC control law, which can significantly reduce the memory requirements for the representation of the exact controller as well for achieving a high-quality approximation that outperforms other approximate explicit MPC techniques [cite some].

 The basic idea on which this work is based is described in the following Lemma.
\begin{lem}\label{lemma:expo}
Every neural network $\mathcal N(x;\theta, M, L)$ defined as in \eqref{eq:neural_network} with ReLUs as activation functions represents a piecewise affine function with the following maximal number of affine regions:
\begin{align*}
\left( \prod \limits_{l=1}^{L-1} \left \lfloor \frac{M}{n_x}\right \rfloor^{n_x} \right) \sum \limits_{j=0}^{n_x} \binom{L}{j}.
\end{align*}
\end{lem}
\begin{pf}

The neural network $\mathcal N(x;\theta, M, L)$ is a piecewise affine function because it only contains compositions of affine transformations with a piecewise affine function (ReLUs).
For the derivation fo the maximal number of regions, see \cite{montufar2014}.
\end{pf}

Lemma~\ref{lemma:expo} is very important because it gives clear insights about why deep networks, as often observed in practice, obtain better performance to approximate complex functions when compared to shallow networks. In particular, Lemma~\ref{lemma:expo} implies that the number of affine regions that a neural network can represent grows exponentially with the number of layers $L$.
At the same time, the number of weights $n_{\text{w}}$ that fully describe the neural network $\mathcal N(x;\theta, M, L)$, which is a measure of the memory requirements of the resulting controller, is computed by
\begin{align}\label{eq:mem_deep}
\Gamma_{\mathcal{N}} = (n_x+1)M + (L-1)(M+1)M + (M+1)n_u.
\end{align}
Since $n_{\text{w}}$ only grows linear with respect to the number of layers $L$, deep ReLU networks are a memory-saving alternative to approximate an explicit MPC controller.
The growing expressive capabilities of deep ReLU networks with growing depth in comparison to shallow ones are depicted in Fig.~\ref{fig:regions_weights}.
\begin{figure}[t]
\begin{center}
\includegraphics[width=0.9\columnwidth]{figures/regions_weights.eps}
\caption{Number of regions with respect to the number of weights a neural network can represent. The parameters for this plot were chosen to $n_x = 2$, $M = 10$, $L = 1, \dots, 50$ and $n_u = 4$.}
\label{fig:regions_weights}
\end{center}
\end{figure}

We believe that this observation, while somewhat obvious, is a very powerful result with important implications in control theory and constitutes the main motivation for this paper.


TITLE: invertibility of matrix over free associative algebra
QUESTION [7 upvotes]: For a commutative ring $R$, a matrix $A \in M_n(R)$ is invertible iff $\det (A)$ is a unit in $R$. Is there a similar criterion to determine invertibility (having two-sided inverse) of a matrix over a noncommutative ring ? I am particularly interested in determining invertibility of matrices in $M_n(F \langle x, y \rangle )$, the free associative algebra in $2$ indeterminates over a field $F$.
Passing onto the polynomial ring using the relation $xy - yx = 0$, we may conclude that the `determinant' should be in $F$ which serves as a necessary condition to filter out certain matrices as being non-invertible. Based on this, I have a question as stated below.
Let $f \in F \langle x, y \rangle$ and $a \in F - \{ 0 \}$. Clearly matrices of the form
$$\begin{bmatrix}
1 & f\\
0 & 1
\end{bmatrix},
\begin{bmatrix}
0 & 1\\
1 & 0
\end{bmatrix},
\begin{bmatrix}
a & 0\\
0 & 1
\end{bmatrix}
$$ are invertible in $M_2(F \langle x, y \rangle)$. By composing such matrices, one gets other examples of invertible matrices in $M_2(F \langle x, y \rangle)$.
Question :  Can any invertible matrix in $M_2(F \langle x, y \rangle)$ be decomposed as a product of matrices of the above $3$ types ?

REPLY [6 votes]: You are asking whether the following holds.

Claim. Let $F$ be a field. Then the free associative algebra $F\langle x,y\rangle$ is a $GE_2$-ring in the sense of P. M. Cohn [2].

The answer is yes. Indeed, free associative algebras over a field are more generally $GE$-rings [Theorem 3.4, 2]. This fact has been used by Bass [1] to prove that a finitely generated projective module over a free algebra with coefficients in a PID is free.
By contrast, free commutative algebras over a field, i.e., polynomial rings over a field aren't $GE$-rings if the number of indeterminates exceeds $1$ [Proposition 7.3, 2]. (I have made this remark in another MO post).
We recall below the definition of a $GE$-ring in the sense of P. M. Cohn and we give subsequently a proof of the claim.
Let $R$ be an associative ring with identity and let $E_n(R)$ be the subgroup of $GL_n(R)$ generated by matrices obtained from the identity matrix by replacing an off-diagonal entry by some $r∈R$. Let $D_n(R)$ be the group of invertible diagonal matrices; note that it normalizes $E_n(R)$.
A ring $R$ is termed a $GE_n$-ring if $GL_n(R)=E_n(R)D_n(R)$.
The ring $R$ is a $GE$-ring in the sense of P. M. Cohn if it is a $GE_n$-ring for every $n > 1$.
Let us turn to the proof of the claim. Let $S$ be the free monoid on $\{x, y\}$ endowed with the shortlex order, i.e., words are ordered according to word length and words of the same length are ordered lexicographically. Then $S$ is a bi-ordered monoid and it is not difficult to show that $F\langle x,y \rangle = F[S]$ is an integral domain with unit group $F^{\times}$. Let $\varphi: S \rightarrow \omega$ be an order-preserving bijection. The following lemma is instrumental.

Lemma. Let $R = F\langle x,y \rangle$ and let $a_1, a_2 \in R$. Assume there are $b_1, b_2 \in F\langle x,y \rangle$, not both zero, such that $a_1b_1 + a_2 b_2 = 0$. Then we can find $E \in E_2(R)$ and $a \in R$ such that $(a_1, a_2)E = (a, 0)$.
Proof. For $r \in R$, write $r = \sum_{w \in S} r_w w$, where each $r_w \in F$ and $\text{supp}(r) \Doteq \{w \in S \,\vert\, r_w \neq 0\}$ is a finite subset of $S$. Since $R$ is an integral domain, we can assume, without loss of generality, that none of $a_1, a_2, b_1$ and $b_2$ is zero. Setting $n(r) \Doteq \varphi(\max(\text{supp}(r))) \in \omega$ for $r \neq 0$, we argue by induction on $n(a_1) + n(a_2)$. Let $w_i = \max(\text{supp}(a_i)) \in S$, for $i = 1,2$.
    Since $a_1b_1 + a_2 b_2 = 0$, we can find $v_1, v_2 \in S$ such that $w_1 v_1 = w_2 v_2$. Swapping $a_1$ and $a_2$ if needed, we can assume that $w_1 \le w_2$, so that $w_1$ is an initial subword of $w_2$. Therefore we can find $s \in S$ and $\lambda \in F$ such that either $a_2' = 0$ or
    $n(a_2') < n(a_2)$ where $a_2' = a_2 - \lambda a_1 s$. We set $a_1' = a_1$,
    $b_1' = b_1 + \lambda sb_2$ and $b_2' = b_2$. Then we have $a_1' b_1' + a_2'b_2' = 0$ and $(a_1', a_2')$ is obtained from $(a_1, a_2)$ by right-multiplication of a matrix in $E_2(R)$. If $a_2' = 0$, we are done. Otherwise the induction hypothesis applies to $(a_1', a_2')$, which yields the result.

We are now in position to prove the claim.

Proof of the claim. Let $A = (a_{ij}) \in GL_2(R)$ with $R = F\langle x,y \rangle$. As $A$ has a right inverse, we can find $b_1, b_2 \in R$, not both zero, such that $a_{11} b_1 + a_{12}b_2 = 0$. By the above lemma, we can assume that $a_{12} = 0$. It follows that $a_{11} \in F^{\times}$, so that $A$ can be reduced to an invertible diagonal matrix through an elementary row operation. Therefore $A \in E_2(R)D_2(R)$.

[1] H. Bass, "Projective modules over free groups are free", 1964.
[2] P. M. Cohn, "On the structure of the $GL_2$ of a ring", 1966.


TITLE: Limiting behaviour of a strictly increasing and convex function
QUESTION [1 upvotes]: Let $\phi \in \mathcal{C}^2(\mathbb{R})$ such that $\phi'(z),\phi''(z) > 0$ for all $z \in \mathbb{R}$, i.e. $\phi$ is a strictly increasing and strictly convex function.
I have the strong believe that it holds that
\begin{align}
z \phi''(z) \to 0 \quad \text{for} \quad z \to -\infty.
\end{align}
However, I couldn't show this statement so far. Any ideas?

REPLY [1 votes]: I think this is not the case.
Consider, for example,
$$
\phi''(x) := \sum_{n=1}^\infty n\, h_{[-n, -n + 1/n^3]}(x),
$$
where $h_{[a,b]}$ denotes the "triangular" profile
$$
h_{[a,b]}(x) :=
\begin{cases}
0, &\text{if}\ x \leq a\ \text{or}\ x \geq b,\\
1- \frac{2}{b-a} \left| x - \frac{a+b}{2}\right|,
& \text{if}\ a < x < b.
\end{cases}
$$
(If you prefer a strictly positive function, you can add for example $e^x$ to $\phi''$.)
Then let
$$
\phi'(x) := \int_{-\infty}^x \phi''(t)\, dt,
\qquad
\phi(x) := \int_0^x \phi'(t)\, dt.
$$
Your $\phi$ satisfies all the assumptions, but $\phi''$ is not bounded from above in $(-\infty, a)$ for any $a$.


TITLE: Some questions on proper acceleration in General Relativity
QUESTION [0 upvotes]: I’m trying to solve an exercise in which I have to use the definition of proper acceleration, which is:
$$
a^{\mu}= u^{\nu}\nabla_{\nu}u^{\mu}
$$
In the exercise, I deal with the acceleration along a certain curve $x^{\mu}(t)$. My question is the following one:
If I choose a frame in which $u^{\mu}=\frac{dx^{\mu}}{dt}=(1,0,0,0)$ (I think one can always make this choice), then the acceleration would be $a^{\mu}=u^{0}\nabla_{0}u^{\mu}=\nabla_{0}u^{\mu}$, and since in this frame, $u^{\mu}=constant$ for every $\mu$, then acceleration would be $a^{\mu}=0$. But I'm quite sure this must be incorrect, since one can always choose $u^{\mu}$ to be $(1,0,0,0)$ but one cannot make acceleration disappear just by a choice of frame. So where am I wrong?
Another question that I don't fully understand is whether $a^{\mu}u_{\mu}=0$ is always true or not (i.e. if the proper four-acceleration is always normal to the four-velocity).

REPLY [1 votes]: The frame you are choosing must be the one that is instantaneously co-moving with the object.  If instead you are looking at some frame for which the object has $u^\mu$ at all times, then either the coordinate frame is non-inertial (in which case $\nabla_0 u^\mu \neq \partial_0 u^\mu$) or the coordinate frame is inertial (in which case the object is moving at constant velocity in an inertial frame, and the result $a^\mu = 0$ is correct.)
As far as the result $a^\mu u_\mu = 0$ goes, it is always true.  It follows from the fact that $u_\mu u^\mu = -1$ by definition.  Take the derivative of $u_\mu u^\mu$ along the worldling and expand out the resulting equation using the product rule to get the acceleration equation you want.


TITLE: Proving the equivalence of a finite set
QUESTION [3 upvotes]: Let A be a finite set. Prove that if A≈n and A≈m, then n=m.
The answer in the book uses a max function, so I was just wondering if there was a simpler way. If not, it would be appreciated if someone could explain it a little better. Thanks!

REPLY [0 votes]: You could prove the contrapositive statement.
Suppose $n \neq m$.  Then prove there is no bijection between $\{1, \dots, n\}$ and $\{1, \dots, m \}$.  If you know about the pigeonhole principle, then this part is easy, because you just invoke it.  By the pigeonhole principle, we can't find such a bijection if $n \neq m$, thus we've proven what we want.
Since the contrapositive is true, it follows that if $\{1, \dots, n \}$ is in bijection with $\{1, \dots, m \}$, then $n = m$.


TITLE: Square root of $-i$
QUESTION [2 upvotes]: I am stuck on the problem as the solutions given at two places do not either concur or or not understandable by me.
The non concurring answer (here, pg #12) states: one root is $-\frac{1}{\sqrt2}-i\frac{1}{\sqrt2}$.
I feel my approach will yield as follows:
$x^2 +i = 0 \implies x = (-i)^{1/2} \implies$ modulus = $1$, and by de-Moivre's formula with angle $= -\pi/2$, i.e. $-i = 1.(\cos(-\pi/2) + i.\sin(-\pi/2))$. => $x_1 = 1.(\cos(-\pi/4) + i.\sin(-\pi/4))$
But, in fourth quadrant the cosine is positive, so one (particular) root is : $\frac{1}{\sqrt2}-i\frac{1}{\sqrt2}$, and the other is diametrically opposite :$-\frac{1}{\sqrt2}+i\frac{1}{\sqrt2}$, that is found by adding $\pi (= n2\pi/m = n^{'}\pi/m)$ to the original answer, i.e. $x_2 = 1.(\cos(3\pi/4) + i.\sin(3\pi/4)) \implies x_2 = -\frac{1}{\sqrt2} + i\frac{1}{\sqrt2}$.
The not understandable answer is given at wolframalpha that although gels with me in terms of geometric location of the points, yet the answer of $\pm(-1)^{3/4}$ confuses me totally.

REPLY [3 votes]: Alternative Method: Let $z=x+iy$ and $c=a+ib$. Consider the equation $z^2=c$. which is $x^2-y^2+2ixy=a+ib$. Solve for $x$ and $y$. We get the desired result.
Here, $x^2-y^2=0,2xy=-1.\implies y=-x, 2x^2=1$ Hence $z=\frac{1}{\sqrt 2}-i \frac{1}{\sqrt 2}$ and $z= -\frac{1}{\sqrt 2}+i \frac{1}{\sqrt 2}$


TITLE: $5 \frac {3}{*} \times 3 \frac {*}{2}=19$?
QUESTION [4 upvotes]: One of my friends gave me this apparently easy-looking problem which I do not know how to crack. The problem is to find the values of   "*" where
$$5 \frac {3}{*} \times 3 \frac {*}{2}=19\text{ ?}$$
I can rearrange the problem as $5 \frac {3}{x} \times 3 \frac {y}{2}=19$ and I have to find the values of $x,y.$  Now $5 \frac {3}{x} \times 3 \frac {y}{2}=19 \implies \frac {5x+3}{x} \times \frac {6+y}{2}=19.$ Now, I do not know which way to  go?
Can someone point me in the right direction? Thanks in advance for your time.
EDIT: Here "*"-s are not same. Infact I know the answer but do not know how to get it. Here $x=7,y=1.$

REPLY [9 votes]: I assume $x, y$ are supposed to be positive integers (otherwise there are infinitely many real solutions for $x, y$). If $y \geq 2$, then $19=(5+\frac{3}{x})(3+\frac{y}{2})>5(3+\frac{2}{2})=20$, a contradiction. Thus $y=1$, so $x=7$.


TITLE: Eigenfunction associated to the smallest eigenvalue of an elliptic operator
QUESTION [3 upvotes]: Let $(T_n)$ be a sequence of elliptic operators defined in $H^2(\Omega)\cap H_0^1(\Omega)$ to $L^2(\Omega)$, with $\Omega$ being a bounded domain with smooth boundary. All of them have a smallest eigenvalue $\lambda_n$ to which we associate a positive eigenfunction $\varphi_n$, with norm equal to 1.
Now, let $T_n \to T$ ($T$ is an elliptic operator as well). Let $\lambda$ be the smallest eigenvalue of $T$, and $\varphi$ the positive eigenfunction with norm equal to 1 associated to $\lambda$.
Show that $\varphi_n\to\varphi$ as $n\to \infty$.

REPLY [0 votes]: I suppose $T_n \to T$ in the sense, that the resolvents $\mathcal R_n(\mathrm i)\to \mathcal R(\mathrm i)$ converge in norm.
$$R_n \phi_n =\frac{1}{\lambda_n-i} \phi_n.$$
Note that the embedding $H_0^1(\Omega)\hookrightarrow L^2(\Omega)$ is compact and hence $\phi_n$ admits a subsequence such that $\phi_n \rightharpoonup \phi$ weakly in $L^2(\Omega)$ and $\mathcal R(i)\phi_n \to \mathcal R(i)\phi$ in $L^2(\Omega)$. Similarly $\lambda_n \to \lambda$ passing to a subsequence.
Then a simple $2\varepsilon$ argument shows
$$\lim_{n\to \infty} R_n \phi_n = R\phi.$$
Obviously, also $\frac{1}{\lambda_n -i} \phi_n \to \frac{1}{\lambda-i} \phi$ and thus $\mathcal R(\mathrm i) \phi= \frac{1}{\lambda -i} \phi $. This leads to $T\phi = \lambda \phi$. That $\lambda$ is the first eigenvalue, then follows by the nonnegativity of each of the eigenfunction that the eigenfunction obtained this way is in fact the first.


TITLE: Showing $f(x) = \frac{1}{1 + x^2}$ is continuous
QUESTION [1 upvotes]: I need to show with a $\epsilon$-$\delta$ proof that the function $$f : \mathbb{R} \rightarrow \mathbb{R} : x \mapsto \frac{1}{1 + x^2} $$ is continuous.
Here is what I did. Let $a \in \mathbb{R}$ be arbitrary. Then for every $x \in \mathbb{R}$ we have $$ | f(x) - f(a) | = \bigg| \frac{1}{1 + x^2} - \frac{1}{1 + a^2} \bigg| = \frac{| a^2 - x^2 |}{(1+x^2)(1+a^2)} \leq \frac{| x - a| (|a| + |x|)}{(1+x^2)(1+a^2)}. $$ Now I think I need to use the trick that $$ \frac{|t|}{1 + t^2} \leq \frac{1}{2} $$ for all $t \in \mathbb{R}$. If I do that here, I still get something complicated: $$ ... = \frac{|x - a| |a|}{ (1+x^2)(1+a^2)} + \frac{|x-a| |x|}{(1+x^2)(1+a^2)} \leq \frac{|x-a|}{ 2 (1+x^2)} + \frac{|x-a|}{2(1+a^2)}. $$ I still got my RHS in terms of $x$, while I only want it in terms of $|x-a|$ and $a$ so than I can pick my $\delta$.
Any help please?

REPLY [1 votes]: In general, to show $f$ is continuous at $a$, it suffices to bound $|f(x)-f(a)|\le M|x-a|$ when $x$ closed to $a$,where $M$ is a constant depends on $a$.
For example, let $a \in \mathbb{R}$ be arbitrary. Then for every $x \in \mathbb{R}$ we have
$$ | f(x) - f(a) | = \bigg| \frac{1}{1 + x^2} - \frac{1}{1 + a^2} \bigg| \le \frac{| x - a| (|a| + |x|)}{(1+x^2)(1+a^2)}\le | x - a| (|a| + |x|). $$
Hence given $\epsilon>0$, we let $\delta=\min\{1,\frac{\epsilon}{2(2|a|+1)}\}$, then for all $|x-a|<\delta\le 1$, we will have $|x|\le |a|+1$, hence
$| f(x) - f(a) |\le (2|a|+1)|x-a|\le \frac{\epsilon}{2(2|a|+1)}(2|a|+1)=  \frac{\epsilon}{2}<\epsilon$


text:
\section{Introduction}

Let $\A =(Q,\Sigma,\delta)$ be a finite deterministic complete (semi)automaton with state set $Q$, input alphabet $\Sigma$, and transition function $\delta: \; Q \times \Sigma \to Q$.
For any word $w\in \Sigma^+$, the deficiency of $w$ is the difference between the cardinality of $Q$ and the cardinality of the image of $Q$ under the natural action of $w$.
For a fixed $k\geq 1$, the word $w$ is called $k$-\emph{compressing} for $\A$ if its deficiency is greater or equal to $k$.
An automaton $\A$ is $k$-\emph{compressible}, if there exists a $k$-compressing word for $\A$.
A word $w\in \Sigma^+$ is $k$-\emph{collapsing}, if it is $k$-compressing for every $k$-compressible automaton with input alphabet $\Sigma$.
A word $w\in \Sigma^+$ is called \emph{$k$-synchronizing} if it is $k$-compressing for all $k$-compressible automata with $k+1$ states and input alphabet $\Sigma$.
Obviously each $k$-collapsing word is also $k$-synchronizing.

The concept of $k$-collapsing words arose (under a different name) in the beginning of the 1990s with original motivations coming from combinatorics (\cite{SS}) and from abstract algebra (\cite{PSSSV}).
In \cite{SS} it has been proved that $k$-collapsing words always exist, for any $\Sigma$ and any $k \geq 1$, by means of a recursive construction which gives a $k$-collapsing word whose length is $O(2^{2^k})$.
Better bounds for $c(k,t)$ and $s(k,t)$, the length  of the shortest $k$-collapsing and $k$-synchronizing words respectively, on an alphabet of cardinality $t$ were given in \cite{MVP}.
The bounds for $c(2,t)$ were slightly improved in \cite{Pri} and \cite{CKP}, but the gaps from lower and upper bounds are quite large even for small values of $k$ and $t$.
Exact values of $s(k,t)$ and $c(k,t)$ are known for $k=2$ and $t=2,3$ and are quite far from the theoretical upper bounds (\cite{APV}).
Moreover it is known that $s(3,2)=33$ and that the words $s_{3,2}=ab^2aba^3b^2a^2babab^2a^2b^3aba^2ba^2b^2a$ and its dual $\bar{s}_{3,2}$ are the unique shortest synchronizing words on $\{a,b\}$ (\cite{AP}).
Observing that $s(k,t)\leq c(k,t)$, and applying the construction in \cite{MVP}, one gets $33\leq c(3,2)\leq 154$.

The reader is referred to \cite{APV, C, CKP, MVP} for  references and connections to Theoretical Computer Science and Language Theory.
The paper is organized as follows: in Section \ref{background} we introduce some general concepts about $3$-compressible automata and the main tool we use to study them, \emph{i.e.}, 3-Missing State Automata.
In Section \ref{permutation} we give a complete characterization of proper $3$-compressible automata on a two letter alphabet with a letter acting as a permutation, while in Section \ref{nopermutation} we characterize all proper $3$-compressible automata without permutations.
In Section \ref{zot} we describe how to use the previous characterization to obtain a short $3$-collapsing word, improving the known upper bound for $c(3,2)$, as already announced in \cite{dlt2011}.
Section \ref{conclusion} ends the paper with some considerations about the quest for short $3$-collapsing words in general and the relationship between $3$-synchronizing and $3$-collapsing words, and how our analysis can be exploited to obtain more general results, as already done in \cite{kisi2,kisi}.

\section{Background}\label{background}

Let $\A =(Q,\Sigma,\delta)$ be a finite deterministic complete (semi)automaton with state set $Q$, input alphabet $\Sigma=\{a,b\}$, and transition function $\delta: \; Q \times \Sigma \to Q$.
The action of $\Sigma$ on $Q$ given by $\delta$ extends naturally, by composition, to the action of any word $w\in \Sigma^+$ on $q\in Q$; we denote it by $qw=\delta(q,w)$, while the action of $w$ on the entire state set $Q$ is denoted by $Qw=\{qw|q\in Q\}$.

\begin{definition}
The difference $|Q|-|Qw|$ is called the \emph{deficiency} of the word $w$ with respect to $\A$ and denoted by df$_\A(w)$.
For a fixed $k\geq 1$, a word $w \in \Sigma^+$ is called $k$-\emph{compressing} for $\A$, if df$_\A(w) \geq k$.
An automaton $\A$ is $k$-\emph{compressible}, if there exists a $k$-compressing word for $\A$.
A word $w\in \Sigma^+$ is $k$-\emph{collapsing}, if it is $k$-compressing for every $k$-compressible automaton with input alphabet $\Sigma$.
A word $w$ is called \emph{$k$-synchronizing} if it is $k$-compressing for all $k$-compressible automata with $k+1$ states and input alphabet $\Sigma$.
Obviously each $k$-collapsing word is also $k$-synchronizing.
\end{definition}

Actually, we view the automaton $\A$ as a set of \emph{transformations} on $Q$ induced via $\delta$ and labeled by letters of $\Sigma$, rather than as a standard triple.
Indeed, in order to define an automaton, it is enough just to assign to every letter $a\in\Sigma$ the corresponding transformation $\tau_a:q\rightarrow \delta(q,a)$ on $Q$.
Now, for $a\in\Sigma$, we get df$_\A(a)=|Q|-|\Imm(\tau_a)|$, hence df$_\A(a)= 0$ if and only if $\tau_a$ is a permutation on $Q$.
If df$_\A(a)=m \geq 1$, then there are exactly $m$ different states $y_1,y_2,\ldots,y_m \notin \Imm(\alpha)$, and there are some elements of $Q$ whose images under $\tau_a$ are equal.

\begin{definition}
Let $\mathcal{P}=\{\{x_{1_1},\ldots,x_{j_1}\},\ldots,\{x_{1_r},\ldots,x_{j_r}\}\}$ be a partition of $Q$ (where singleton sets are omitted), and $y_1,\ldots,y_m\in Q$, we say that $\tau_a$ is a \emph{transformation of type} \[
[x_{1_1},\ldots,x_{j_1}]\ldots[x_{1_r},\ldots,x_{j_r}]\backslash y_1,\ldots,y_m
\]
if $\mathcal{P}$ is induced by the kernel of $\tau_a$ and the states $y_1,y_2,\ldots,y_m$ do not belong to $\Imm(\tau_a)$.
\end{definition}

For instance, if $\A$ has at least three states denoted by $1$, $2$ and $3$, the transformation $\tau$ is of type $[1,2]\backslash 3$, if and only if $\tau(1)=\tau(2)$, the preimage of $3$ is empty, and for any $q,q'\notin \{1,2\}$, $\tau(q)=\tau(q')$ if and only if $q=q'$.
So, with an abuse of language, we will write $\tau=[1,2]\backslash 3$ (actually $[1,2]\backslash 3$ is a family of transformations).
Then, in the sequel \emph{we will identify each letter of the input alphabet with its corresponding transformation.}

\begin{definition}
Let $a\in\Sigma$, we say that $a$ is a \emph{permutation letter} if it induces a permutation on the set of states, \emph{i.e.}, it has deficiency $0$.
We assume that permutations on $Q$, viewed as elements of the symmetric group $S_n$ with $|Q|=n$, are written in the factorization in disjoint cycles where sometimes also cycles of length 1 are explicitly written.
So we will write $a=(1)(23)\pi$ to denote that (the permutation induces by) $a$ fixes the state 1, swaps states 2 and 3, and $\pi$ is a permutation that does not act over $\{1,2,3\}$ ($\pi$ is not necessarily a cycle).
\end{definition}

The notion of transformation induced by a letter naturally extends to words, and then the semigroup generated by the transformations of $\A$ consists precisely of the transformations corresponding to words in $\Sigma^+$.
If $\mathcal{A}$ is $k$-compressible, at least one letter of its input alphabet has deficiency greater than $0$.
It is well known that each $k$-collapsing word over a fixed alphabet $\Sigma$ is $k$-\emph{full} (\cite{SS}), \emph{i.e.}, contains each word of length $k$ on the alphabet $\Sigma$ among its factors.
Hence, to characterize $k$-collapsing words it is enough
to consider $k$-full words compressing all \emph{proper} $k$-\emph{compressible automata}, \emph{i.e.}, $k$-compressible automata which are not compressed by any word of length $k$.

\begin{proposition}
Let $\mathcal{A}$ be a finite complete automaton on the alphabet $\{a,b\}$: it is $3$-compressible and not proper if at least one letter, say $a$, fulfills one of the following conditions:
\begin{enumerate}
  \item it has deficiency greater than 2;
  \item it has deficiency 2 and is of type $[x,y,z]\backslash u,v$, with $\{u,v\}\nsubseteq\{x,y,z\}$;
  \item it has deficiency 2 and is of type $[x,y][z,v]\backslash u,w$, with either $\{u,w\}=\{x,y\}$, or $\{u,w\}=\{z,v\}$, or $\{u,w\}\nsubseteq\{x,y,z,v\}$;
  \item it has deficiency 1 and is of type $[x,y]\backslash z$, with $z \notin \{x,y\}$ and $za \neq x$.
\end{enumerate}
\end{proposition}

The proof of the previous proposition is trivial, indeed if the letter $a$ fulfills one of the above conditions, then either $a$ or $a^2$ or $a^3$ has deficiency 3.
Since we are looking for a $3$-compressible proper automaton we may assume that each letter of the alphabet either is a permutation or is of one of the following types (we assume different letters represent different states):
\begin{description}
  \item[\bf{1.}] $[x,y,z]\backslash x,y$;
  \item[\bf{2.}] $[x,y][z,v]\backslash x,z$;
  \item[\bf{3.}] $[x,y]\backslash x$;
  \item[\bf{4.}] $[x,y]\backslash z$ with $za=x$.
\end{description}

In the sequel we view the set $Q$ of the states of $\A$ as a set of natural numbers: $Q=\{1,2,\ldots,n\}$, so that, when no confusion arises, a letter $a$ of types $\bf{1},\bf{2},\bf{3},\bf{4}$ is denoted respectively by $[1,2,3]\backslash 1,2$, $[1,2][3,4]\backslash 1,3$, $[1,2]\backslash 1$,
$[1,2]\backslash 3$ with $3a=1$.

\begin{definition}
Let $w\in\Sigma^+$, we call $\M(w)=Q\setminus Qw$ the \emph{missing set} of $w$.
Let $Q_1\subseteq Q$, we denote by $\M(Q_1,w)$ the set $\M(w)\cup \{qw\mid \ q\in Q_1 \text{ and } \forall q'\in Q\setminus Q_1,\ qw\neq q'w\}$, i.e., the \emph{missing set of $w$ having already missed $Q_1$}.
\end{definition}

Observe that $\M(\varnothing,w)=\M(w)$, and if $a\in\Sigma$ is a permutation, $\M(Q_1,a)=Q_1a$.
Moreover, $|\M(w)|\geq |\M(w_1)|$, whenever $w_1$ is a factor of $w$.

\begin{definition}
With abuse of language, for a letter $a$ and $Q_1 \subseteq Q$, we call the \emph{orbit of $a$ over $Q_1$} the set $Orb_a(Q_1)=\bigcup^{+\infty}_{n=0}Q_1a^n=\bigcup_{q\in Q_1}Orb_a(q)$.
\end{definition}

We say that $\A$ is a $(\bf{i},\bf{j})$-\emph{automaton}, $1\leq i,j\leq 4$, if it is an automaton on a two letter alphabet $\{a,b\}$ and the letter $a$ is of type $\bf{i}$ and $b$ is of type $\bf{j}$.
We say that $\A$ is a $(\bf{i},\bf{p})$-\emph{automaton}, with $1\leq i\leq 4$, to denote that the letter $a$ is of type $\bf{i}$ and $b$ is a permutation.
In the sequel, without loss of generality, we will always suppose that in a  $(\bf{i},\bf{j})$-automaton (resp. $(\bf{i},\bf{p})$-automaton) the letter $a$ is of type $\bf{i}$ and $b$ is of type $\bf{j}$ (resp. a permutation).

Although the notion of missing set is sufficient to describe the compressibility of an automaton, it is in general quite intricate to use, especially when long words are involved.
So, to easily calculate the set $\M(Q_1,w)$, we introduce a graphical device, the \emph{missing state automaton} of $\A$.

\begin{definition}
Let $\A=(Q,\Sigma,\delta)$ be a deterministic (semi)automaton, with $|Q|=n$ and $m<n$.
The (complete) $m$-Missing State Automaton ($m$MSA for short) of $\A$ is the automaton $\M=(\wp^{m-1}(Q)\cup\{\mathbf{m}\},\Sigma,\emptyset,\tau,\mathbf{m})$, where $\wp^{m-1}(Q)$ is the set of subsets of $Q$ of cardinality less or equal to $m-1$, $\mathbf{m}$ is a special state not belonging to $\wp^{m-1}(Q)$ graphically denoted by a circle with $m$ token inside, and $\tau: \wp^{m-1}(Q)\times \Sigma\rightarrow \wp^{m-1}(Q)\cup\{\mathbf{m}\}$ is the transition relation defined by
\[
\tau(Q_1,a)=\left\{
              \begin{array}{ll}
                \M(Q_1,a), & \hbox{if $|\M(Q_1,a)|<m$;} \\
                \mathbf{m}, & \hbox{else.}
              \end{array}
            \right.
\]
notice that $\tau$ is not defined over $\mathbf{m}$.
\end{definition}

For example, in Fig. \ref{es} we draw the 2MSA of a simple semiautomaton, proving that it is synchronizable.

\begin{figure}[ht]
\centering
\subfigure[][The Cern\'{y} automaton $\A$.]{
{\footnotesize
\begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

    \node[state] (q_0) [draw=none] {};
    \node[state] (q_1) [right of= q_0] {$1$};
    \node[state] (q_2) [below of= q_0] {$0$};
    \node[state] (q_3) [right of= q_2,draw=none] {};
    \node[state] (q_4) [right of= q_3] {$2$};

    \path[->] (q_1) edge [loop above] node {$a$} (q_1)
              (q_1) edge node {$b$} (q_4)
              (q_4) edge [loop right] node {$a$} (q_4)
              (q_4) edge node {$b$} (q_2)
              (q_2) edge node {$a,b$} (q_1);

\end{tikzpicture}}
}
\hspace{20pt}
\subfigure[][The 2MSA of $\A$.]{
{\footnotesize
\tikzstyle{accepting}=[tokens=2,accepting by double]
\begin{tikzpicture}[shorten >=1pt,node distance=5em,auto]

    \node[state] (q_0) {};
    \node[state] (q_1) [right of= q_0] {$0$};
    \node[state] (q_2) [right of= q_1] {$1$};
    \node[state] (q_3) [right of= q_2,draw=none] {};
    \node[state] (q_4) [right of= q_3] {$2$};
    \node[state,accepting] (q_5) [below of= q_3] {};

    \path[->] (q_0) edge [loop above] node {$b$} (q_0)
              (q_0) edge node {$a$} (q_1)
              (q_1) edge [loop above] node {$a$} (q_1)
              (q_1) edge node {$b$} (q_2)
              (q_2) edge node {$b$} (q_4)
              (q_4) edge [bend right=25] node [swap] {$b$} (q_1)
              (q_2) edge node {$a$} (q_5)
              (q_4) edge node {$a$} (q_5);

    \draw [->] (-.5,.5) -- (-.27,.27);

\end{tikzpicture}}}
\caption[]{The Cern\'{y} semiautomaton with 3 states and its 2MSA: the set of synchronizing words for $\A$ is the regular language $b^*a^+(b^3)^*(b+b^2)a(a+b)^*$.}
\label{es}
\end{figure}

The notion of missing state automaton is similar to that of power state automaton, which is a standard tool in computing synchronizing words, see \cite{Trahtman2006,Kudlacik,Volkov2008}, the difference is that the names of states are replaced by their complements and all superstates made by more than $m$ states are identified.
Although, power set automata are only used to design algorithm to find possibly shortest synchronizing words of a fixed automaton, while we need to consider a whole class of automata.

Moreover, as we are only interested in knowing if an automaton is 3-compressible, often we will draw only a \emph{Partial $3$-Missing State Automaton} (P3MSA), \emph{i.e.}, a path (possibly the shortest) from the initial to a final state of the whole 3MSA.

Lastly, we observe that when considering a family of automata, dozens of subcases arise when we try to find some (short) 3-collapsing word for such family.
So, to capture a greater number of cases and improve the readability, we gather several subcases using a \emph{conditional} 3MSA.
In such case, a label can be of the form $a|qw\in Q'$. So, $\tau(q_1,a|qw\in Q')=q_2$ means that $\M(q_1,a)=q_2$ under the hypothesis (condition) that $qw\in Q'$.
Observe that the condition $qw\in Q'$ spreads over all the states reached by $q_2$, so two different states can share the same name, when belonging to different branches.
For example, in the conditional 3MSA in Fig. \ref{fig:caso:3-p:d:2:1}, the two states named by $\{1,3\}$ have different behavior as the one in the first row inherits the condition $3a=3$ and then $\M({1,3},a)=\{1,3\}$, while the one in the second row inherits the condition $3a=2$ and then $\M({1,3},a)=\{1,2\}$.


TITLE: Systems of Equations degree 2
QUESTION [5 upvotes]: Given the system
$$\begin{aligned}
x^2+y^2+\frac{\sqrt 3}{2}xy&=32\\
x^2+z^2+\frac{1}{2}xz&=16\\
y^2+z^2&=16,\end{aligned}$$
find the value of $(xy+\sqrt{3}xz+2yz).$
The answer is $32,$ so I think there will be a really nice solution to this.
 I tried completing the square for each pair $x$ and $y$ but I could not find anything, I tried adding all three equations but I got nothing.

REPLY [3 votes]: I guess the two factors (1/2) shouldn't be there, which mean we have instead
\begin{align}
x^2+y^2+\sqrt{3}xy&=32\tag{A}\\
x^2+z^2+xz&=16\tag{B}\\
y^2+z^2&=16\tag{C}.
\end{align}
The rationale being that it gives a much nicer set of coefficients when completing the square
\begin{align}
(x+\frac{\sqrt3}2y)^2+\frac14y^2&=32\\
(x+\frac12z)^2+\frac34z^2&=16\\
\end{align}
and we have accidental cancellation when eliminating $y,z$, giving the biquartic $37x^4-896x^2+4096=0$, and hence a nice form of the four real solutions
$$
(x,y,z)=\left(8 \sqrt{\frac{7-2\sqrt{3}}{37}},
4(3 + \sqrt3)\sqrt{\frac{7-2\sqrt3}{111}},
4\sqrt{\frac{21 - 6\sqrt3}{37}}\right),\text{ and similar}
$$
and it is easy to check $(xy+\sqrt{3}xz+2yz)^2=2^{10}$.  Indeed, it follows immediately from noting the LHS of
$$
\mathrm{(A)^2+(B)^2+(C)^2-2\times(A)\times(B)-2\times(B)\times(C)-2\times(C)\times(A)}
$$
is $-(xy+\sqrt{3}xz+2yz)^2$, which I suppose is the only way to solve this within the 120 seconds limit.


TITLE: Existence of functions on finite sets with specific propertise
QUESTION [2 upvotes]: Let $\Omega$ be an universal set and $|\Omega|=N$, denote $\mathcal{F}$ to be the family of all subsets $\subset \Omega$ with cardinal $n$. We now define a function $f:\mathcal{F}\rightarrow \Omega$, and which satisfies the following properties:

$\forall A\in \mathcal{F},\ f(A)\in A$,
If $|A_1\cap A_2|=n-1$ then $f(A_1)\not=f(A_2)$.

My question is:

When does this kind of functions exist?

A simple result is that if $n=N-2$ then this kind of functions exist iff $N$ is odd, since we can reduce this question to idempotent symmetric latin square designing problem.

Proof: We change the function to its complement functions, i.e. $f'(\bar{A})=f(A)$. Note that $\bar{A}$ have only two elements, so $f'$ can be regarded as a function $\Omega\times \Omega\rightarrow \Omega$ such that $f'(a,b)\not=a\not=b$ and $f'(a,b)\not=f'(a,c)$ and $f'(a,b)=f'(b,a)$, which is exactly some kind of idempotent symmetric latin square.

We can also show that $n$ should not less then $N/2-1$.

Proof: Suppose not, choosing an arbitrary subset $A'\in \Omega$ and $|A'|=n-2$, since $n<N/2-1$ we can find different $a,b\not\in A'$ and denote $A_1=A'\cup\{a\},\ A_2=A'\cup \{b\}$. For $i=1,2$, we have $N-n+1$ ways to extend $A_i$ to a subset with cardinal $n$ by adding a new element. We claim that there must be an element $e\not\in A_1\cup A_2$, such that $f(A_1\cup\{e\})=f(A_2\cup \{e\})=e$ and which contradict to property 2. But this is easily follows by $2(n+1)<N\Leftrightarrow n<N/2-1$.

So, does anyone know whether this problem can be reduced to any well studied problems?
Actually, I conjecture that this kind of functions do not exist when $n<N-2$, but I don't know how to prove it.

REPLY [1 votes]: Let $p$ be smallest prime divisor of $n$. I claim that $N<n+p$ though I have no idea about how adequate this estimate is. Consider any subset $C\subset \Omega$ of size $|C|=n+1$. Note that all $n$-element subsets of $C$ have different values of $f$, hence all $n+1$ values are taken each exactly once. Assume that $N\geq n+p$ and choose $U\subset \Omega$, $|U|=n+p$. Consider all $\binom{n+p}{n+1}$ subsets $C\subset U$, $|C|=n+1$, for each of them consider all its subsets $A\subset C$, $|A|=n$. Each element of $C$ equals $f(A)$ for unique $A\subset C$. Sum up by all $C$. Each $A$ is counted $p$ times, while each $a\in U$ appears as $f(A)$ for $\binom{n+p-1}{n}$ subsets, as it lies in   $\binom{n+p-1}{n}$ sets $C$. But $\binom{n+p-1}{n}$ is not divisible by $p$, a contradiction.


TITLE: Are all injective arcs the images of an injective interval?
QUESTION [2 upvotes]: Given a continous $f:[0,1] \to \mathbb{R}^2$ call it an injective arc if:

$f(0) \neq f(1)$
$f(a) = f(b) =c $ for $a<b$ implies that $f([a,b]) = {c}$.

Given such $f$ we also have an ordering on $Im(f)$ by taking the one of $[0,1]$.
Is it true that for any such $f$ there is an injective continous $g:[0,1] \to \mathbb{R}^2$ that is a homeomorphism on $Im(f)$ and preserves ordering?

REPLY [1 votes]: It seems that my answer to Reparameterisation of Curve as a Regular Curve (Topology) also answers your question in the affirmative. In the referenced question arbitrary paths $p : [0,1] \to X$ are considered and it is shown that there exists a reparametrization $\phi$ (which is a non-decreasing surjective continuous map $\phi: [0,1] \to [0,1]$ with $\phi(0)=0, \phi(1)=1$) such that $p = q \circ \phi$ with a path $q : [0,1] \to X$ which is not constant on any closed subinterval $[a,b]$, $0 \le a < b \le 1$, of $I =[0,1]$.
Applying this to your $f : I \to \mathbb R^2$, we get $\phi$ and $g : I \to \mathbb R^2$ such that $f =  g \circ \phi$ and  $g$ is not constant on any closed subinterval of $I$. Now assume that $g$ is not injective. Then $g(a) = g(b)$ for suitable $0 < a < b < 1$. Choose $a', b'$ such that $\phi(a') = a, \phi(b') = b$. Clearly $0 < a' < b' < 1$ and $\phi([a',b']) = [a,b]$ since $\phi$ is non-decreasing. Then $f(a') = f(b')$ and $f(x) = c$ for $x \in [a',b']$. Hence $g(y) = c$ for $y = \phi(x) \in \phi([a',b']) = [a,b]$, thus $g$ is constant on $[a,b]$ which is a contradiction.