TITLE: Two independent spanning trees of $2$-connected graph
QUESTION [1 upvotes]: I want to prove the following statement:

Let $u$ be a vertex in a $2$-connected graph $G$. Then $G$ has two spanning trees such that for every vertex $v$, the $u,v$-paths in the trees are independent.

I tried to show this, but surprisingly, I have proved another statement.

A graph with $\vert V(G) \vert \geq 3$ is $2$-connected iff for any two vertices $u$ and $v$ in $G$, there exist at least two independent $u,v$-paths.

And I can assure that it is true, since I could find it from other papers.
I think this one may help me proving the desired statement, but I have no idea how to use it properly.
Would you help me find a such way, or suggest another proof of the first statement?

REPLY [1 votes]: You could try building up two trees $T_1,T_2$ such that $V(T_1) = V(T_2)$ (here $V(T_i)$ denotes the vertex set of $T_i$), $u \in V(T_1)$ and for every vertex $v \in V(T_1) - \{u\}$ the $u-v$ paths in $T_1$ and $T_2$ are independent (i.e. internally disjoint).
At the beginning, let $T_1$ and $T_2$ consist of the single vertex $u$. Then while $V(T_1) \neq V$, choose an outgoing edge $e = u'v'$, where $u' \in V(T_1)$. Because $G$ is $2$-connected, you can find a path $P$ not containing $u'$ that goes from $v'$ to some vertex of $V(T_1)$ (Edit: as pointed out in the comments, this is not true for the first step and we need to modify the argument slightly in this case). Then you can use $P$ and $e$ to extend $T_1$ and $T_2$ to larger trees while maintaining the properties above.
The above strategy can be also rephrased as taking an open ear decomposition of $G$ whose initial cycle contains $u$, and then constructing two suitable spanning trees from the ear decomposition "one ear at a time".


TITLE: Elementary Linear Algebra with Tensor Products
QUESTION [0 upvotes]: Is there any way to make this formulae simpler?
$(\alpha|1\rangle\otimes\beta|O1\rangle+\beta|2\rangle\otimes|O2\rangle)\otimes|1\rangle$

REPLY [1 votes]: It's not clear what you mean by "simpler". One option is to "expand" the expression and move any constants to the front:
$$
(\alpha|1\rangle\otimes\beta|O1\rangle+\beta|2\rangle\otimes|O2\rangle)\otimes |1\rangle = \\
\alpha\beta (|1\rangle\otimes|O1\rangle \otimes | 1 \rangle) + \beta (|2\rangle\otimes|O2\rangle\otimes|1\rangle).
$$


TITLE: Separating compact, non-convex sets in $\mathbb R^n$
QUESTION [4 upvotes]: Let $m>1$. For disjoint compact subsets $E$ and $F$ of $\mathbb{R}^n$ we can define $$d(E,F) := \sup_\phi \inf \{\phi(x)-\phi(y)| x\in E, y\in F\},$$
where the supremum is taken over all bounded $\phi\in C^\infty(\mathbb R^n; \mathbb R )$ with $\|D^\alpha\phi\|_\infty \leq 1$ for $1\leq |\alpha| \leq m$.
We easily get $d(E,F)\leq n^{1/2} \tilde d (E,F),$ for $\tilde d$ being the Euclidean distance. Since for compact convex sets we can always find a linear function with gradient of norm 1 such that $$\tilde d(E,F) = \inf \{\phi(x)-\phi(y)| x\in E, y\in F\},$$ we can approximate it by a sequence of bounded $C^\infty$ functions to obtain

$\tilde d(E,F)\leq d (E,F),$ whenever $E, F \subseteq \mathbb R^n$ are two disjoint, compact and convex sets.

The question I have been struggling with is: can we relax the condition that both sets need to be convex to obtain the above inequality (with possibly some extra, but uniform, constants)? I am particularly interested in the case when $E$ is the closed unit ball and $F$ is $\{x\in \mathbb R^n| 2\leq|x|\leq 4\}$. First I took a linear function as above separating $E$ and $B= \{x\in \mathbb R^n| |x-3e_1|\leq 1\}$ a compact and convex subset of $F$. This can't work though, because if I allow $y\in F\setminus B$ the infimum becomes negative.
Should it be possible to construct some kind of a cut-off function with the above properties?
I will be grateful for help!
PS. the answer to the above question for $m=1$ is yes, since the distance function is Lipschitz continuous.
Update: The claim holds for any disjoint closed subsets of $\mathbb R^n$. The idea of the following proof comes from Lemma 2.3 in this paper.
Let $s=\tilde d(E,F) >0$ and $\psi \in C^\infty_c(\mathbb R^n)$, supported in the unit ball, with $\int \psi =1$. We consider the rescaled function $\psi_\varepsilon = \varepsilon^{-n}\psi(\cdot/\varepsilon)$ for $\varepsilon>0$. Let us fix $\varepsilon = \frac{s}{4}$ and denote the $\delta$-neighbourhood of $E$ w.r.t. $\tilde d$ by $\tilde E_\delta$. Define $C_\psi = \sum_{1\leq|\alpha|\leq m} \int |D^\alpha\psi|.$ We distinct two cases:
Case 1. $\varepsilon\ge 1$ Let $\phi = \frac{\varepsilon}{C_\psi}\chi_{\tilde E_\varepsilon} \ast \psi_\varepsilon$. Then $\phi$ satisfies $\|D^\alpha\phi\|_\infty \leq 1$ for $1\leq |\alpha| \leq m$.
We obtain for $x\in E, y\in F$
$$ \begin{align} \phi(x)-\phi(y)=\phi (x) & = \frac{\varepsilon}{C_\psi}\int_{B(x,\varepsilon)} \psi_\varepsilon(x-z) dz \\ & = \frac{\varepsilon}{C_\psi}\ge C\tilde d(E,F)\end{align}. $$
Case 2. $\varepsilon\leq 1$ Let $\delta=\varepsilon^{\frac{1}{m}}$ and we set $\phi = \frac{\varepsilon}{C_\psi}\chi_{\tilde E_\delta} \ast \psi_\delta$. Then one checks that $\phi$ also satisfies $\|D^\alpha\phi\|_\infty \leq 1$ for $1\leq |\alpha| \leq m$.
We have for $x\in E, y\in F$
$$ \begin{align} \phi(x)-\phi(y)=\phi (x) & = \frac{\varepsilon}{C_\psi}\int_{B(x,\delta)} \psi_\delta(x-z) dz \\ & = \frac{\varepsilon}{C_\psi}\ge C\tilde d(E,F)\end{align}. $$

REPLY [3 votes]: This gives details to my comment. Define $g:[0,\infty)\rightarrow\mathbb{R}$ by
$$g(x) = \frac{x}{x+1}$$
Note that $g$ is increasing and concave.  Fix $n$ as a positive integer and define $h:\mathbb{R}^n\rightarrow\mathbb{R}$ by
$$h(x) = \sum_{i=1}^n g(dx_i^2)$$
for some $d>0$. Then $h$ is infinitely differentiable. Let $||x||=\sum_{i=1}^n x_i^2$ be the standard Euclidean norm.
Claim 1: $||x||\leq 1 \implies h(x)\leq \frac{d}{1+d/n}$
Suppose $||x|| \leq 1$.  Then by Jensen's inequality for the concave function $g$:
\begin{align}
h(x) &= n\cdot \frac{1}{n}\sum_{i=1}^n g(dx_i^2) \\
&\leq ng\left(\frac{1}{n} \sum_{i=1}^n dx_i^2\right) \\
&= ng\left(\frac{d}{n}||x||^2\right) \\
&\leq ng(d/n)\\
&= \frac{d}{1+d/n}
\end{align}
$\Box$
Claim 2: $||x||\geq 2 \implies h(x)\geq \min[1/2, 2d]$.
Suppose $||x||\geq 2$.  Notice that
$$ g(y) \geq y/2 \quad \mbox{whenever $y \in [0,1]$} \quad (Eq. *) $$
Case 1: If there is an index $i \in \{1, ..., n\}$ such that $dx_i^2>1$ then
$$ h(x) \geq g(d x_i^2) \geq g(1) = 1/2 $$
Case 2: If $dx_i^2 \in [0,1]$ for all $i \in \{1, ..., n\}$, then $g(dx_i^2)\geq dx_i^2/2$ for all $i \in \{1, ..., n\}$ (by (Eq. *))  and
$$ h(x) = \sum_{i=1}^n g(dx_i^2) \geq \sum_{i=1}^n dx_i^2/2 = (d/2)||x||^2\geq 2d$$
$\Box$
Claim 3:  If $d=1/4$ we have a strict separation.
By Claims 1 and 2:
\begin{align}
E &= \{x \in \mathbb{R}^n : ||x||\leq 1\} \subseteq \left\{x \in \mathbb{R}^n : h(x)\leq \frac{d}{1+d/n} \right\} \\
F &= \{x \in \mathbb{R}^n : 2 \leq ||x|| \leq 4\} \subseteq\left\{x \in \mathbb{R}^n : h(x)\geq  \min[1/2, 2d]\right\}
\end{align}
Since $d=1/4$ we have
\begin{align}
E &\subseteq \left\{x \in \mathbb{R}^n : h(x)\leq \frac{1}{4+1/n} \right\} \\
F &\subseteq  \left\{x \in \mathbb{R}^n : h(x)\geq  1/2\right\}
\end{align}
$\Box$
Claim 4: We can choose $f(x) = ch(x)$ for small $c>0$
Fix $c>0$. Clearly the strict separation still holds for the scaled function  $f(x) = ch(x)$.
Fix $m$ as a positive integer. It can be shown that there is a value $B>0$ such that for all $i \in \{1, ..., n\}$ and all $k \in \{1, ..., m\}$ we have
$$ |\frac{\partial^k}{\partial x_i^k} h(x) |\leq B \quad \forall x \in \mathbb{R}^n $$
and so we can choose $c>0$ sufficiently small to ensure the gradients of $ch(x)$ are sufficiently small.


text:
\typeout{TCILATEX Macros for Scientific Word 3.0 <19 May 1997>.}
\typeout{NOTICE:  This macro file is NOT proprietary and may be
freely copied and distributed.}

\makeatletter

\newcount\@hour\newcount\@minute\chardef\@x10\chardef\@xv60
\def\tcitime{
\def\@time{
  \@minute\time\@hour\@minute\divide\@hour\@xv
  \ifnum\@hour<\@x 0\fi\the\@hour:
  \multiply\@hour\@xv\advance\@minute-\@hour
  \ifnum\@minute<\@x 0\fi\the\@minute
  }}

\@ifundefined{hyperref}{\def\hyperref#1#2#3#4{#2\ref{#4}#3}}{}

\@ifundefined{qExtProgCall}{\def\qExtProgCall#1#2#3#4#5#6{\relax}}{}

\def\FILENAME#1{#1}

\def\QCTOpt[#1]#2{
  \def\QCTOptB{#1}
  \def\QCTOptA{#2}
}
\def\QCTNOpt#1{
  \def\QCTOptA{#1}
  \let\QCTOptB\empty
}
\def\Qct{
  \@ifnextchar[{
    \QCTOpt}{\QCTNOpt}
}
\def\QCBOpt[#1]#2{
  \def\QCBOptB{#1}
  \def\QCBOptA{#2}
}
\def\QCBNOpt#1{
  \def\QCBOptA{#1}
  \let\QCBOptB\empty
}
\def\Qcb{
  \@ifnextchar[{
    \QCBOpt}{\QCBNOpt}
}
\def\PrepCapArgs{
  \ifx\QCBOptA\empty
    \ifx\QCTOptA\empty
      {}
    \else
      \ifx\QCTOptB\empty
        {\QCTOptA}
      \else
        [\QCTOptB]{\QCTOptA}
      \fi
    \fi
  \else
    \ifx\QCBOptA\empty
      {}
    \else
      \ifx\QCBOptB\empty
        {\QCBOptA}
      \else
        [\QCBOptB]{\QCBOptA}
      \fi
    \fi
  \fi
}
\newcount\GRAPHICSTYPE

\GRAPHICSTYPE=\z@
\def\GRAPHICSPS#1{
 \ifcase\GRAPHICSTYPE
   \special{ps: #1}
 \or
   \special{language "PS", include "#1"}

 \fi
}

\def\GRAPHICSHP#1{\special{include #1}}

\def\graffile#1#2#3#4{

    \bgroup
    \leavevmode
    \@ifundefined{bbl@deactivate}{\def~{\string~}}{\activesoff}
    \raise -#4 \BOXTHEFRAME{
        \hbox to #2{\raise #3\hbox to #2{\null #1\hfil}}}
    \egroup
}

\def\draftbox#1#2#3#4{
 \leavevmode\raise -#4 \hbox{
  \frame{\rlap{\protect\tiny #1}\hbox to #2
   {\vrule height#3 width\z@ depth\z@\hfil}
  }
 }
}

\newcount\draft
\draft=\z@
\let\nographics=\draft
\newif\ifwasdraft
\wasdraftfalse

\def\GRAPHIC#1#2#3#4#5{
 \ifnum\draft=\@ne\draftbox{#2}{#3}{#4}{#5}
  \else\graffile{#1}{#3}{#4}{#5}
  \fi
 }

\def\addtoLaTeXparams#1{
    \edef\LaTeXparams{\LaTeXparams #1}}

\newif\ifBoxFrame \BoxFramefalse
\newif\ifOverFrame \OverFramefalse
\newif\ifUnderFrame \UnderFramefalse

\def\BOXTHEFRAME#1{
   \hbox{
      \ifBoxFrame
         \frame{#1}
      \else
         {#1}
      \fi
   }
}

\def\doFRAMEparams#1{\BoxFramefalse\OverFramefalse\UnderFramefalse\readFRAMEparams#1\end}
\def\readFRAMEparams#1{
 \ifx#1\end
  \let\next=\relax
  \else
  \ifx#1i\dispkind=\z@\fi
  \ifx#1d\dispkind=\@ne\fi
  \ifx#1f\dispkind=\tw@\fi
  \ifx#1t\addtoLaTeXparams{t}\fi
  \ifx#1b\addtoLaTeXparams{b}\fi
  \ifx#1p\addtoLaTeXparams{p}\fi
  \ifx#1h\addtoLaTeXparams{h}\fi
  \ifx#1X\BoxFrametrue\fi
  \ifx#1O\OverFrametrue\fi
  \ifx#1U\UnderFrametrue\fi
  \ifx#1w
    \ifnum\draft=1\wasdrafttrue\else\wasdraftfalse\fi
    \draft=\@ne
  \fi
  \let\next=\readFRAMEparams
  \fi
 \next
 }

\def\IFRAME#1#2#3#4#5#6{
      \bgroup
      \let\QCTOptA\empty
      \let\QCTOptB\empty
      \let\QCBOptA\empty
      \let\QCBOptB\empty
      #6
      \parindent=0pt
      \leftskip=0pt
      \rightskip=0pt
      \setbox0 = \hbox{\QCBOptA}
      \@tempdima = #1\relax
      \ifOverFrame

          \typeout{This is not implemented yet}
          \show\HELP
      \else
         \ifdim\wd0>\@tempdima
            \advance\@tempdima by \@tempdima
            \ifdim\wd0 >\@tempdima
               \textwidth=\@tempdima
               \setbox1 =\vbox{
                  \noindent\hbox to \@tempdima{\hfill\GRAPHIC{#5}{#4}{#1}{#2}{#3}\hfill}\\%
                  \noindent\hbox to \@tempdima{\parbox[b]{\@tempdima}{\QCBOptA}}
               }
               \wd1=\@tempdima
            \else
               \textwidth=\wd0
               \setbox1 =\vbox{
                 \noindent\hbox to \wd0{\hfill\GRAPHIC{#5}{#4}{#1}{#2}{#3}\hfill}\\%
                 \noindent\hbox{\QCBOptA}
               }
               \wd1=\wd0
            \fi
         \else

            \ifdim\wd0>0pt
              \hsize=\@tempdima
              \setbox1 =\vbox{
                \unskip\GRAPHIC{#5}{#4}{#1}{#2}{0pt}
                \break
                \unskip\hbox to \@tempdima{\hfill \QCBOptA\hfill}
              }
              \wd1=\@tempdima
           \else
              \hsize=\@tempdima
              \setbox1 =\vbox{
                \unskip\GRAPHIC{#5}{#4}{#1}{#2}{0pt}
              }
              \wd1=\@tempdima
           \fi
         \fi
         \@tempdimb=\ht1
         \advance\@tempdimb by \dp1
         \advance\@tempdimb by -#2
         \advance\@tempdimb by #3
         \leavevmode
         \raise -\@tempdimb \hbox{\box1}
      \fi
      \egroup
}

\def\DFRAME#1#2#3#4#5{
 \begin{center}
     \let\QCTOptA\empty
     \let\QCTOptB\empty
     \let\QCBOptA\empty
     \let\QCBOptB\empty
     \ifOverFrame
        #5\QCTOptA\par
     \fi
     \GRAPHIC{#4}{#3}{#1}{#2}{\z@}
     \ifUnderFrame
        \nobreak\par\nobreak#5\QCBOptA
     \fi
 \end{center}
 }

\def\FFRAME#1#2#3#4#5#6#7{
 \begin{figure}[#1]
  \let\QCTOptA\empty
  \let\QCTOptB\empty
  \let\QCBOptA\empty
  \let\QCBOptB\empty
  \ifOverFrame
    #4
    \ifx\QCTOptA\empty
    \else
      \ifx\QCTOptB\empty
        \caption{\QCTOptA}
      \else
        \caption[\QCTOptB]{\QCTOptA}
      \fi
    \fi
    \ifUnderFrame\else
      \label{#5}
    \fi
  \else
    \UnderFrametrue
  \fi
  \begin{center}\GRAPHIC{#7}{#6}{#2}{#3}{\z@}\end{center}
  \ifUnderFrame
    #4
    \ifx\QCBOptA\empty
      \caption{}
    \else
      \ifx\QCBOptB\empty
        \caption{\QCBOptA}
      \else
        \caption[\QCBOptB]{\QCBOptA}
      \fi
    \fi
    \label{#5}
  \fi
  \end{figure}
 }

\newcount\dispkind

\def\makeactives{
  \catcode`\"=\active
  \catcode`\;=\active
  \catcode`\:=\active
  \catcode`\'=\active
  \catcode`\~=\active
}
\bgroup
   \makeactives
   \gdef\activesoff{
      \def"{\string"}
      \def;{\string;}
      \def:{\string:}
      \def'{\string'}
      \def~{\string~}

    }
\egroup

\def\FRAME#1#2#3#4#5#6#7#8{
 \bgroup
 \ifnum\draft=\@ne
   \wasdrafttrue
 \else
   \wasdraftfalse
 \fi
 \def\LaTeXparams{}
 \dispkind=\z@
 \def\LaTeXparams{}
 \doFRAMEparams{#1}
 \ifnum\dispkind=\z@\IFRAME{#2}{#3}{#4}{#7}{#8}{#5}\else
  \ifnum\dispkind=\@ne\DFRAME{#2}{#3}{#7}{#8}{#5}\else
   \ifnum\dispkind=\tw@
    \edef\@tempa{\noexpand\FFRAME{\LaTeXparams}}
    \@tempa{#2}{#3}{#5}{#6}{#7}{#8}
    \fi
   \fi
  \fi
  \ifwasdraft\draft=1\else\draft=0\fi{}
  \egroup
 }

\def\TEXUX#1{"texux"}

\def\BF#1{{\bf {#1}}}
\def\NEG#1{\leavevmode\hbox{\rlap{\thinspace/}{$#1$}}}

\def\limfunc#1{\mathop{\rm #1}}
\def\func#1{\mathop{\rm #1}\nolimits}

\def\unit#1{\mathop{\rm #1}\nolimits}

\long\def\QQQ#1#2{
     \long\expandafter\def\csname#1\endcsname{#2}}
\@ifundefined{QTP}{\def\QTP#1{}}{}
\@ifundefined{QEXCLUDE}{\def\QEXCLUDE#1{}}{}
\@ifundefined{Qlb}{\def\Qlb#1{#1}}{}
\@ifundefined{Qlt}{\def\Qlt#1{#1}}{}
\def\QWE{}
\long\def\QQA#1#2{}
\def\QTR#1#2{{\csname#1\endcsname #2}}
\long\def\TeXButton#1#2{#2}
\long\def\QSubDoc#1#2{#2}
\def\EXPAND#1[#2]#3{}
\def\NOEXPAND#1[#2]#3{}
\def\PROTECTED{}
\def\LaTeXparent#1{}
\def\ChildStyles#1{}
\def\ChildDefaults#1{}
\def\QTagDef#1#2#3{}

\@ifundefined{correctchoice}{\def\correctchoice{\relax}}{}
\@ifundefined{HTML}{\def\HTML#1{\relax}}{}
\@ifundefined{TCIIcon}{\def\TCIIcon#1#2#3#4{\relax}}{}
\if@compatibility
  \typeout{Not defining UNICODE or CustomNote commands for LaTeX 2.09.}
\else
  \providecommand{\UNICODE}[2][]{}
  \providecommand{\CustomNote}[3][]{\marginpar{#3}}
\fi

\@ifundefined{StyleEditBeginDoc}{\def\StyleEditBeginDoc{\relax}}{}

\def\QQfnmark#1{\footnotemark}
\def\QQfntext#1#2{\addtocounter{footnote}{#1}\footnotetext{#2}}

\@ifundefined{TCIMAKEINDEX}{}{\makeindex}

\@ifundefined{abstract}{
 \def\abstract{
  \if@twocolumn
   \section*{Abstract (Not appropriate in this style!)}
   \else \small
   \begin{center}{\bf Abstract\vspace{-.5em}\vspace{\z@}}\end{center}
   \quotation
   \fi
  }
 }{
 }
\@ifundefined{endabstract}{\def\endabstract
  {\if@twocolumn\else\endquotation\fi}}{}
\@ifundefined{maketitle}{\def\maketitle#1{}}{}
\@ifundefined{affiliation}{\def\affiliation#1{}}{}
\@ifundefined{proof}{\def\proof{\noindent{\bfseries Proof. }}}{}
\@ifundefined{endproof}{\def\endproof{\mbox{\ \rule{.1in}{.1in}}}}{}
\@ifundefined{newfield}{\def\newfield#1#2{}}{}
\@ifundefined{chapter}{\def\chapter#1{\par(Chapter head:)#1\par }
 \newcount\c@chapter}{}
\@ifundefined{part}{\def\part#1{\par(Part head:)#1\par }}{}
\@ifundefined{section}{\def\section#1{\par(Section head:)#1\par }}{}
\@ifundefined{subsection}{\def\subsection#1
 {\par(Subsection head:)#1\par }}{}
\@ifundefined{subsubsection}{\def\subsubsection#1
 {\par(Subsubsection head:)#1\par }}{}
\@ifundefined{paragraph}{\def\paragraph#1
 {\par(Subsubsubsection head:)#1\par }}{}
\@ifundefined{subparagraph}{\def\subparagraph#1
 {\par(Subsubsubsubsection head:)#1\par }}{}

\@ifundefined{therefore}{\def\therefore{}}{}
\@ifundefined{backepsilon}{\def\backepsilon{}}{}
\@ifundefined{yen}{\def\yen{\hbox{\rm\rlap=Y}}}{}
\@ifundefined{registered}{
   \def\registered{\relax\ifmmode{}\r@gistered
                    \else$\m@th\r@gistered$\fi}
 \def\r@gistered{^{\ooalign
  {\hfil\raise.07ex\hbox{$\scriptstyle\rm\text{R}$}\hfil\crcr
  \mathhexbox20D}}}}{}
\@ifundefined{Eth}{\def\Eth{}}{}
\@ifundefined{eth}{\def\eth{}}{}
\@ifundefined{Thorn}{\def\Thorn{}}{}
\@ifundefined{thorn}{\def\thorn{}}{}

\def\TEXTsymbol#1{\mbox{$#1$}}
\@ifundefined{degree}{\def\degree{{}^{\circ}}}{}

\newdimen\theight
\def\Column{
 \vadjust{\setbox\z@=\hbox{\scriptsize\quad\quad tcol}
  \theight=\ht\z@\advance\theight by \dp\z@\advance\theight by \lineskip
  \kern -\theight \vbox to \theight{
   \rightline{\rlap{\box\z@}}
   \vss
   }
  }
 }

\def\qed{
 \ifhmode\unskip\nobreak\fi\ifmmode\ifinner\else\hskip5\p@\fi\fi
 \hbox{\hskip5\p@\vrule width4\p@ height6\p@ depth1.5\p@\hskip\p@}
 }

\def\cents{\hbox{\rm\rlap/c}}
\def\miss{\hbox{\vrule height2\p@ width 2\p@ depth\z@}}

\def\vvert{\Vert}

\def\tcol#1{{\baselineskip=6\p@ \vcenter{#1}} \Column}

\def\dB{\hbox{{}}}
\def\mB#1{\hbox{$#1$}}
\def\nB#1{\hbox{#1}}

\@ifundefined{note}{\def\note{$^{\dag}}}{}

\def\newfmtname{LaTeX2e}

\ifx\fmtname\newfmtname
  \DeclareOldFontCommand{\rm}{\normalfont\rmfamily}{\mathrm}
  \DeclareOldFontCommand{\sf}{\normalfont\sffamily}{\mathsf}
  \DeclareOldFontCommand{\tt}{\normalfont\ttfamily}{\mathtt}
  \DeclareOldFontCommand{\bf}{\normalfont\bfseries}{\mathbf}
  \DeclareOldFontCommand{\it}{\normalfont\itshape}{\mathit}
  \DeclareOldFontCommand{\sl}{\normalfont\slshape}{\@nomath\sl}
  \DeclareOldFontCommand{\sc}{\normalfont\scshape}{\@nomath\sc}
\fi

\def\alpha{{\Greekmath 010B}}
\def\beta{{\Greekmath 010C}}
\def\gamma{{\Greekmath 010D}}
\def\delta{{\Greekmath 010E}}
\def\epsilon{{\Greekmath 010F}}
\def\zeta{{\Greekmath 0110}}
\def\eta{{\Greekmath 0111}}
\def\theta{{\Greekmath 0112}}
\def\iota{{\Greekmath 0113}}
\def\kappa{{\Greekmath 0114}}
\def\lambda{{\Greekmath 0115}}
\def\mu{{\Greekmath 0116}}
\def\nu{{\Greekmath 0117}}
\def\xi{{\Greekmath 0118}}
\def\pi{{\Greekmath 0119}}
\def\rho{{\Greekmath 011A}}
\def\sigma{{\Greekmath 011B}}
\def\tau{{\Greekmath 011C}}
\def\upsilon{{\Greekmath 011D}}
\def\phi{{\Greekmath 011E}}
\def\chi{{\Greekmath 011F}}
\def\psi{{\Greekmath 0120}}
\def\omega{{\Greekmath 0121}}
\def\varepsilon{{\Greekmath 0122}}
\def\vartheta{{\Greekmath 0123}}
\def\varpi{{\Greekmath 0124}}
\def\varrho{{\Greekmath 0125}}
\def\varsigma{{\Greekmath 0126}}
\def\varphi{{\Greekmath 0127}}

\def\nabla{{\Greekmath 0272}}
\def\FindBoldGroup{
   {\setbox0=\hbox{$\mathbf{x\global\edef\theboldgroup{\the\mathgroup}}$}}
}

\def\Greekmath#1#2#3#4{
    \if@compatibility
        \ifnum\mathgroup=\symbold
           \mathchoice{\mbox{\boldmath$\displaystyle\mathchar"#1#2#3#4$}}
                      {\mbox{\boldmath$\textstyle\mathchar"#1#2#3#4$}}
                      {\mbox{\boldmath$\scriptstyle\mathchar"#1#2#3#4$}}
                      {\mbox{\boldmath$\scriptscriptstyle\mathchar"#1#2#3#4$}}
        \else
           \mathchar"#1#2#3#4
        \fi
    \else
        \FindBoldGroup
        \ifnum\mathgroup=\theboldgroup
           \mathchoice{\mbox{\boldmath$\displaystyle\mathchar"#1#2#3#4$}}
                      {\mbox{\boldmath$\textstyle\mathchar"#1#2#3#4$}}
                      {\mbox{\boldmath$\scriptstyle\mathchar"#1#2#3#4$}}
                      {\mbox{\boldmath$\scriptscriptstyle\mathchar"#1#2#3#4$}}
        \else
           \mathchar"#1#2#3#4
        \fi
	  \fi}

\newif\ifGreekBold  \GreekBoldfalse
\let\SAVEPBF=\pbf
\def\pbf{\GreekBoldtrue\SAVEPBF}

\@ifundefined{theorem}{\newtheorem{theorem}{Theorem}}{}
\@ifundefined{lemma}{\newtheorem{lemma}[theorem]{Lemma}}{}
\@ifundefined{corollary}{\newtheorem{corollary}[theorem]{Corollary}}{}
\@ifundefined{conjecture}{\newtheorem{conjecture}[theorem]{Conjecture}}{}
\@ifundefined{proposition}{\newtheorem{proposition}[theorem]{Proposition}}{}
\@ifundefined{axiom}{\newtheorem{axiom}{Axiom}}{}
\@ifundefined{remark}{\newtheorem{remark}{Remark}}{}
\@ifundefined{example}{\newtheorem{example}{Example}}{}
\@ifundefined{exercise}{\newtheorem{exercise}{Exercise}}{}
\@ifundefined{definition}{\newtheorem{definition}{Definition}}{}

\@ifundefined{mathletters}{

  \newcounter{equationnumber}
  \def\mathletters{
     \addtocounter{equation}{1}
     \edef\@currentlabel{\theequation}
     \setcounter{equationnumber}{\c@equation}
     \setcounter{equation}{0}
     \edef\theequation{\@currentlabel\noexpand\alph{equation}}
  }
  \def\endmathletters{
     \setcounter{equation}{\value{equationnumber}}
  }
}{}

\@ifundefined{BibTeX}{
    \def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
                 T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}}{}
\@ifundefined{AmS}
    {\def\AmS{{\protect\usefont{OMS}{cmsy}{m}{n}
                A\kern-.1667em\lower.5ex\hbox{M}\kern-.125emS}}}{}
\@ifundefined{AmSTeX}{\def\AmSTeX{\protect\AmS-\protect\TeX\@}}{}

\def\@@eqncr{\let\@tempa\relax
    \ifcase\@eqcnt \def\@tempa{& & &}\or \def\@tempa{& &}
      \else \def\@tempa{&}\fi
     \@tempa
     \if@eqnsw
        \iftag@
           \@taggnum
        \else
           \@eqnnum\stepcounter{equation}
        \fi
     \fi
     \global\tag@false
     \global\@eqnswtrue
     \global\@eqcnt\z@\cr}

\def\TCItag{\@ifnextchar*{\@TCItagstar}{\@TCItag}}
\def\@TCItag#1{
    \global\tag@true
    \global\def\@taggnum{(#1)}}
\def\@TCItagstar*#1{
    \global\tag@true
    \global\def\@taggnum{#1}}

\def\tfrac#1#2{{\textstyle {#1 \over #2}}}
\def\dfrac#1#2{{\displaystyle {#1 \over #2}}}
\def\binom#1#2{{#1 \choose #2}}
\def\tbinom#1#2{{\textstyle {#1 \choose #2}}}
\def\dbinom#1#2{{\displaystyle {#1 \choose #2}}}
\def\QATOP#1#2{{#1 \atop #2}}
\def\QTATOP#1#2{{\textstyle {#1 \atop #2}}}
\def\QDATOP#1#2{{\displaystyle {#1 \atop #2}}}
\def\QABOVE#1#2#3{{#2 \above#1 #3}}
\def\QTABOVE#1#2#3{{\textstyle {#2 \above#1 #3}}}
\def\QDABOVE#1#2#3{{\displaystyle {#2 \above#1 #3}}}
\def\QOVERD#1#2#3#4{{#3 \overwithdelims#1#2 #4}}
\def\QTOVERD#1#2#3#4{{\textstyle {#3 \overwithdelims#1#2 #4}}}
\def\QDOVERD#1#2#3#4{{\displaystyle {#3 \overwithdelims#1#2 #4}}}
\def\QATOPD#1#2#3#4{{#3 \atopwithdelims#1#2 #4}}
\def\QTATOPD#1#2#3#4{{\textstyle {#3 \atopwithdelims#1#2 #4}}}
\def\QDATOPD#1#2#3#4{{\displaystyle {#3 \atopwithdelims#1#2 #4}}}
\def\QABOVED#1#2#3#4#5{{#4 \abovewithdelims#1#2#3 #5}}
\def\QTABOVED#1#2#3#4#5{{\textstyle
   {#4 \abovewithdelims#1#2#3 #5}}}
\def\QDABOVED#1#2#3#4#5{{\displaystyle
   {#4 \abovewithdelims#1#2#3 #5}}}

\def\tint{\mathop{\textstyle \int}}
\def\tiint{\mathop{\textstyle \iint }}
\def\tiiint{\mathop{\textstyle \iiint }}
\def\tiiiint{\mathop{\textstyle \iiiint }}
\def\tidotsint{\mathop{\textstyle \idotsint }}
\def\toint{\mathop{\textstyle \oint}}
\def\tsum{\mathop{\textstyle \sum }}
\def\tprod{\mathop{\textstyle \prod }}
\def\tbigcap{\mathop{\textstyle \bigcap }}
\def\tbigwedge{\mathop{\textstyle \bigwedge }}
\def\tbigoplus{\mathop{\textstyle \bigoplus }}
\def\tbigodot{\mathop{\textstyle \bigodot }}
\def\tbigsqcup{\mathop{\textstyle \bigsqcup }}
\def\tcoprod{\mathop{\textstyle \coprod }}
\def\tbigcup{\mathop{\textstyle \bigcup }}
\def\tbigvee{\mathop{\textstyle \bigvee }}
\def\tbigotimes{\mathop{\textstyle \bigotimes }}
\def\tbiguplus{\mathop{\textstyle \biguplus }}

\def\dint{\mathop{\displaystyle \int}}
\def\diint{\mathop{\displaystyle \iint }}
\def\diiint{\mathop{\displaystyle \iiint }}
\def\diiiint{\mathop{\displaystyle \iiiint }}
\def\didotsint{\mathop{\displaystyle \idotsint }}
\def\doint{\mathop{\displaystyle \oint}}
\def\dsum{\mathop{\displaystyle \sum }}
\def\dprod{\mathop{\displaystyle \prod }}
\def\dbigcap{\mathop{\displaystyle \bigcap }}
\def\dbigwedge{\mathop{\displaystyle \bigwedge }}
\def\dbigoplus{\mathop{\displaystyle \bigoplus }}
\def\dbigodot{\mathop{\displaystyle \bigodot }}
\def\dbigsqcup{\mathop{\displaystyle \bigsqcup }}
\def\dcoprod{\mathop{\displaystyle \coprod }}
\def\dbigcup{\mathop{\displaystyle \bigcup }}
\def\dbigvee{\mathop{\displaystyle \bigvee }}
\def\dbigotimes{\mathop{\displaystyle \bigotimes }}
\def\dbiguplus{\mathop{\displaystyle \biguplus }}

\ifx\ds@amstex\relax
   \message{amstex already loaded}\makeatother\endinput
\else
   \@ifpackageloaded{amsmath}
      {\message{amsmath already loaded}\makeatother\endinput}
      {}
   \@ifpackageloaded{amstex}
      {\message{amstex already loaded}\makeatother\endinput}
      {}
   \@ifpackageloaded{amsgen}
      {\message{amsgen already loaded}\makeatother\endinput}
      {}
\fi

\let\DOTSI\relax
\def\RIfM@{\relax\ifmmode}
\def\FN@{\futurelet\next}
\newcount\intno@
\def\iint{\DOTSI\intno@\tw@\FN@\ints@}
\def\iiint{\DOTSI\intno@\thr@@\FN@\ints@}
\def\iiiint{\DOTSI\intno@4 \FN@\ints@}
\def\idotsint{\DOTSI\intno@\z@\FN@\ints@}
\def\ints@{\findlimits@\ints@@}
\newif\iflimtoken@
\newif\iflimits@
\def\findlimits@{\limtoken@true\ifx\next\limits\limits@true
 \else\ifx\next\nolimits\limits@false\else
 \limtoken@false\ifx\ilimits@\nolimits\limits@false\else
 \ifinner\limits@false\else\limits@true\fi\fi\fi\fi}
\def\multint@{\int\ifnum\intno@=\z@\intdots@
 \else\intkern@\fi
 \ifnum\intno@>\tw@\int\intkern@\fi
 \ifnum\intno@>\thr@@\int\intkern@\fi
 \int}
\def\multintlimits@{\intop\ifnum\intno@=\z@\intdots@\else\intkern@\fi
 \ifnum\intno@>\tw@\intop\intkern@\fi
 \ifnum\intno@>\thr@@\intop\intkern@\fi\intop}
\def\intic@{
    \mathchoice{\hskip.5em}{\hskip.4em}{\hskip.4em}{\hskip.4em}}
\def\negintic@{\mathchoice
 {\hskip-.5em}{\hskip-.4em}{\hskip-.4em}{\hskip-.4em}}
\def\ints@@{\iflimtoken@
 \def\ints@@@{\iflimits@\negintic@
   \mathop{\intic@\multintlimits@}\limits
  \else\multint@\nolimits\fi
  \eat@}
 \else
 \def\ints@@@{\iflimits@\negintic@
  \mathop{\intic@\multintlimits@}\limits\else
  \multint@\nolimits\fi}\fi\ints@@@}
\def\intkern@{\mathchoice{\!\!\!}{\!\!}{\!\!}{\!\!}}
\def\plaincdots@{\mathinner{\cdotp\cdotp\cdotp}}
\def\intdots@{\mathchoice{\plaincdots@}
 {{\cdotp}\mkern1.5mu{\cdotp}\mkern1.5mu{\cdotp}}
 {{\cdotp}\mkern1mu{\cdotp}\mkern1mu{\cdotp}}
 {{\cdotp}\mkern1mu{\cdotp}\mkern1mu{\cdotp}}}

\def\RIfM@{\relax\protect\ifmmode}
\def\text{\RIfM@\expandafter\text@\else\expandafter\mbox\fi}
\let\nfss@text\text
\def\text@#1{\mathchoice
   {\textdef@\displaystyle\f@size{#1}}
   {\textdef@\textstyle\tf@size{\firstchoice@false #1}}
   {\textdef@\textstyle\sf@size{\firstchoice@false #1}}
   {\textdef@\textstyle \ssf@size{\firstchoice@false #1}}
   \glb@settings}

\def\textdef@#1#2#3{\hbox{{
                    \everymath{#1}
                    \let\f@size#2\selectfont
                    #3}}}
\newif\iffirstchoice@
\firstchoice@true

\def\Let@{\relax\iffalse{\fi\let\\=\cr\iffalse}\fi}
\def\vspace@{\def\vspace##1{\crcr\noalign{\vskip##1\relax}}}
\def\multilimits@{\bgroup\vspace@\Let@
 \baselineskip\fontdimen10 \scriptfont\tw@
 \advance\baselineskip\fontdimen12 \scriptfont\tw@
 \lineskip\thr@@\fontdimen8 \scriptfont\thr@@
 \lineskiplimit\lineskip
 \vbox\bgroup\ialign\bgroup\hfil$\m@th\scriptstyle{##}$\hfil\crcr}
\def\Sb{_\multilimits@}
\def\endSb{\crcr\egroup\egroup\egroup}
\def\Sp{^\multilimits@}
\let\endSp\endSb

\newdimen\ex@
\ex@.2326ex
\def\rightarrowfill@#1{$#1\m@th\mathord-\mkern-6mu\cleaders
 \hbox{$#1\mkern-2mu\mathord-\mkern-2mu$}\hfill
 \mkern-6mu\mathord\rightarrow$}
\def\leftarrowfill@#1{$#1\m@th\mathord\leftarrow\mkern-6mu\cleaders
 \hbox{$#1\mkern-2mu\mathord-\mkern-2mu$}\hfill\mkern-6mu\mathord-$}
\def\leftrightarrowfill@#1{$#1\m@th\mathord\leftarrow
\mkern-6mu\cleaders
 \hbox{$#1\mkern-2mu\mathord-\mkern-2mu$}\hfill
 \mkern-6mu\mathord\rightarrow$}
\def\overrightarrow{\mathpalette\overrightarrow@}
\def\overrightarrow@#1#2{\vbox{\ialign{##\crcr\rightarrowfill@#1\crcr
 \noalign{\kern-\ex@\nointerlineskip}$\m@th\hfil#1#2\hfil$\crcr}}}
\let\overarrow\overrightarrow
\def\overleftarrow{\mathpalette\overleftarrow@}
\def\overleftarrow@#1#2{\vbox{\ialign{##\crcr\leftarrowfill@#1\crcr
 \noalign{\kern-\ex@\nointerlineskip}$\m@th\hfil#1#2\hfil$\crcr}}}
\def\overleftrightarrow{\mathpalette\overleftrightarrow@}
\def\overleftrightarrow@#1#2{\vbox{\ialign{##\crcr
   \leftrightarrowfill@#1\crcr
 \noalign{\kern-\ex@\nointerlineskip}$\m@th\hfil#1#2\hfil$\crcr}}}
\def\underrightarrow{\mathpalette\underrightarrow@}
\def\underrightarrow@#1#2{\vtop{\ialign{##\crcr$\m@th\hfil#1#2\hfil
  $\crcr\noalign{\nointerlineskip}\rightarrowfill@#1\crcr}}}
\let\underarrow\underrightarrow
\def\underleftarrow{\mathpalette\underleftarrow@}
\def\underleftarrow@#1#2{\vtop{\ialign{##\crcr$\m@th\hfil#1#2\hfil
  $\crcr\noalign{\nointerlineskip}\leftarrowfill@#1\crcr}}}
\def\underleftrightarrow{\mathpalette\underleftrightarrow@}
\def\underleftrightarrow@#1#2{\vtop{\ialign{##\crcr$\m@th
  \hfil#1#2\hfil$\crcr
 \noalign{\nointerlineskip}\leftrightarrowfill@#1\crcr}}}

\def\qopnamewl@#1{\mathop{\operator@font#1}\nlimits@}
\let\nlimits@\displaylimits
\def\setboxz@h{\setbox\z@\hbox}

\def\varlim@#1#2{\mathop{\vtop{\ialign{##\crcr
 \hfil$#1\m@th\operator@font lim$\hfil\crcr
 \noalign{\nointerlineskip}#2#1\crcr
 \noalign{\nointerlineskip\kern-\ex@}\crcr}}}}

 \def\rightarrowfill@#1{\m@th\setboxz@h{$#1-$}\ht\z@\z@
  $#1\copy\z@\mkern-6mu\cleaders
  \hbox{$#1\mkern-2mu\box\z@\mkern-2mu$}\hfill
  \mkern-6mu\mathord\rightarrow$}
\def\leftarrowfill@#1{\m@th\setboxz@h{$#1-$}\ht\z@\z@
  $#1\mathord\leftarrow\mkern-6mu\cleaders
  \hbox{$#1\mkern-2mu\copy\z@\mkern-2mu$}\hfill
  \mkern-6mu\box\z@$}

\def\projlim{\qopnamewl@{proj\,lim}}
\def\injlim{\qopnamewl@{inj\,lim}}
\def\varinjlim{\mathpalette\varlim@\rightarrowfill@}
\def\varprojlim{\mathpalette\varlim@\leftarrowfill@}
\def\varliminf{\mathpalette\varliminf@{}}
\def\varliminf@#1{\mathop{\underline{\vrule\@depth.2\ex@\@width\z@
   \hbox{$#1\m@th\operator@font lim$}}}}
\def\varlimsup{\mathpalette\varlimsup@{}}
\def\varlimsup@#1{\mathop{\overline
  {\hbox{$#1\m@th\operator@font lim$}}}}

\def\stackunder#1#2{\mathrel{\mathop{#2}\limits_{#1}}}

\begingroup \catcode `|=0 \catcode `[= 1
\catcode`]=2 \catcode `\{=12 \catcode `\}=12
\catcode`\\=12
|gdef|@alignverbatim#1\end{align}[#1|end[align]]
|gdef|@salignverbatim#1\end{align*}[#1|end[align*]]

|gdef|@alignatverbatim#1\end{alignat}[#1|end[alignat]]
|gdef|@salignatverbatim#1\end{alignat*}[#1|end[alignat*]]

|gdef|@xalignatverbatim#1\end{xalignat}[#1|end[xalignat]]
|gdef|@sxalignatverbatim#1\end{xalignat*}[#1|end[xalignat*]]

|gdef|@gatherverbatim#1\end{gather}[#1|end[gather]]
|gdef|@sgatherverbatim#1\end{gather*}[#1|end[gather*]]

|gdef|@gatherverbatim#1\end{gather}[#1|end[gather]]
|gdef|@sgatherverbatim#1\end{gather*}[#1|end[gather*]]

|gdef|@multilineverbatim#1\end{multiline}[#1|end[multiline]]
|gdef|@smultilineverbatim#1\end{multiline*}[#1|end[multiline*]]

|gdef|@arraxverbatim#1\end{arrax}[#1|end[arrax]]
|gdef|@sarraxverbatim#1\end{arrax*}[#1|end[arrax*]]

|gdef|@tabulaxverbatim#1\end{tabulax}[#1|end[tabulax]]
|gdef|@stabulaxverbatim#1\end{tabulax*}[#1|end[tabulax*]]

|endgroup

\def\align{\@verbatim \frenchspacing\@vobeyspaces \@alignverbatim
You are using the "align" environment in a style in which it is not defined.}
\let\endalign=\endtrivlist

\@namedef{align*}{\@verbatim\@salignverbatim
You are using the "align*" environment in a style in which it is not defined.}
\expandafter\let\csname endalign*\endcsname =\endtrivlist

\def\alignat{\@verbatim \frenchspacing\@vobeyspaces \@alignatverbatim
You are using the "alignat" environment in a style in which it is not defined.}
\let\endalignat=\endtrivlist

\@namedef{alignat*}{\@verbatim\@salignatverbatim
You are using the "alignat*" environment in a style in which it is not defined.}
\expandafter\let\csname endalignat*\endcsname =\endtrivlist

\def\xalignat{\@verbatim \frenchspacing\@vobeyspaces \@xalignatverbatim
You are using the "xalignat" environment in a style in which it is not defined.}
\let\endxalignat=\endtrivlist

\@namedef{xalignat*}{\@verbatim\@sxalignatverbatim
You are using the "xalignat*" environment in a style in which it is not defined.}
\expandafter\let\csname endxalignat*\endcsname =\endtrivlist

\def\gather{\@verbatim \frenchspacing\@vobeyspaces \@gatherverbatim
You are using the "gather" environment in a style in which it is not defined.}
\let\endgather=\endtrivlist

\@namedef{gather*}{\@verbatim\@sgatherverbatim
You are using the "gather*" environment in a style in which it is not defined.}
\expandafter\let\csname endgather*\endcsname =\endtrivlist

\def\multiline{\@verbatim \frenchspacing\@vobeyspaces \@multilineverbatim
You are using the "multiline" environment in a style in which it is not defined.}
\let\endmultiline=\endtrivlist

\@namedef{multiline*}{\@verbatim\@smultilineverbatim
You are using the "multiline*" environment in a style in which it is not defined.}
\expandafter\let\csname endmultiline*\endcsname =\endtrivlist

\def\arrax{\@verbatim \frenchspacing\@vobeyspaces \@arraxverbatim
You are using a type of "array" construct that is only allowed in AmS-LaTeX.}
\let\endarrax=\endtrivlist

\def\tabulax{\@verbatim \frenchspacing\@vobeyspaces \@tabulaxverbatim
You are using a type of "tabular" construct that is only allowed in AmS-LaTeX.}
\let\endtabulax=\endtrivlist

\@namedef{arrax*}{\@verbatim\@sarraxverbatim
You are using a type of "array*" construct that is only allowed in AmS-LaTeX.}
\expandafter\let\csname endarrax*\endcsname =\endtrivlist

\@namedef{tabulax*}{\@verbatim\@stabulaxverbatim
You are using a type of "tabular*" construct that is only allowed in AmS-LaTeX.}
\expandafter\let\csname endtabulax*\endcsname =\endtrivlist

 \def\endequation{
     \ifmmode\ifinner
      \iftag@
        \addtocounter{equation}{-1}
        $\hfil
           \displaywidth\linewidth\@taggnum\egroup \endtrivlist
        \global\tag@false
        \global\@ignoretrue
      \else
        $\hfil
           \displaywidth\linewidth\@eqnnum\egroup \endtrivlist
        \global\tag@false
        \global\@ignoretrue
      \fi
     \else
      \iftag@
        \addtocounter{equation}{-1}
        \eqno \hbox{\@taggnum}
        \global\tag@false
        $$\global\@ignoretrue
      \else
        \eqno \hbox{\@eqnnum}
        $$\global\@ignoretrue
      \fi
     \fi\fi
 }

 \newif\iftag@ \tag@false

 \def\TCItag{\@ifnextchar*{\@TCItagstar}{\@TCItag}}
 \def\@TCItag#1{
     \global\tag@true
     \global\def\@taggnum{(#1)}}
 \def\@TCItagstar*#1{
     \global\tag@true
     \global\def\@taggnum{#1}}

  \@ifundefined{tag}{
     \def\tag{\@ifnextchar*{\@tagstar}{\@tag}}
     \def\@tag#1{
         \global\tag@true
         \global\def\@taggnum{(#1)}}
     \def\@tagstar*#1{
         \global\tag@true
         \global\def\@taggnum{#1}}
  }{}

\makeatother
\endinput

config: arxiv


TITLE: What does it mean when a Linear equation has no solutions?
QUESTION [0 upvotes]: Take for example the linear equation $$-7x+3=-7x+2$$
What I understand by this is that there is no number that would make the Left hand side and the right hand side of the equation equal.But if so, shouldn't there NOT be an "=" sign between the two expressions, because they cannot be equivalent to each other if they don't have a solution?
Shouldn't it also be understood this way?:
If the equation is simplified, we'd get: $3=2$
which is not true. Hence,
$$-7x+3 \neq -7x+2$$
I'm confused.

REPLY [2 votes]: An equation, even such as $2=3$, is a mathematical expression that has a truth value. This one is $\text{false}$.
When there is an unknown, the expression can be conditionally true: $3x-9=0$ is $\text{true}$ if and only if $x=3$ is $\text{true}$.
$3x-9=3x$ is never $\text{true}$, and this is said to be an impossible equation.


TITLE: An urn contains two red balls and four white balls. Sample successively five times at random and with replacement so that the trials are independent.
QUESTION [0 upvotes]: An urn contains two red balls and four white balls. Sample successively five times at random and with replacement so that the trials are independent.
Compute the probability of each of the two sequences
WWRWR
RWWWR
Please explain. I have the correct answer but i do not understand how to get it.

REPLY [0 votes]: The probability to draw a white ball is $\frac{4}{6}=\frac{2}{3}$.
The probability to draw a red ball is $\frac{2}{6}=\frac{1}{3}$.
After drawing there is replacement so that these probabilities stand each of the $5$ times.
Then the chance to draw e.g. RWRRR equals $$\frac{1}{3}\times\frac{2}{3}\times\frac{1}{3}\times\frac{1}{3}\times\frac{1}{3}$$
Can you take it from here?

REPLY [0 votes]: $P(WWRWR) = P(W)P(W)P(R)P(W)P(R) = \frac{4}{6} \frac{4}{6} \frac{2}{6} \frac{4}{6} \frac{2}{6}$
$P(WWRWR) = P(W)P(W)P(R)P(W)P(R)$ follows by independence.
where W = event a white ball is drawn, R = event a red ball is drawn
WWRWR = event a white ball is drawn the fisrt time, a white ball is drawn the second time, a red ball is drawn the third time, a white ball is drawn the fourth time and a red ball is drawn the fifth time


text:
\begin{document}
\maketitle

\let\thefootnote\relax\footnote{2010MSC: 16T05, 12F10. \\ T. Crespo acknowledges support by grant MTM2012-33830, Spanish Science Ministry, and 2009SGR 1370; A. Rio and M. Vela acknowledge support by grant MTM2012-34611, Spanish Science Ministry, and 2009SGR 1220.}

\begin{abstract}
We give a degree 8 separable extension having two non-isomorphic
Hopf-Galois structures with isomorphic underlying Hopf algebras.
\end{abstract}

\section{Introduction}

A finite extension of fields $K/k$ is a Hopf Galois extension if
there exist a finite cocommutative $k$-Hopf algebra $H$  and a
Hopf action of $H$ on $K$, i.e a $k$-linear map $\mu: H\to
\End_k(K)$ inducing a bijection $K\otimes_k H\to\End_k(K)$. We
shall call such a pair $(H,\mu)$ a Hopf Galois structure on $K/k$.
Two Hopf Galois structures $(H_1,\mu_1)$  and $(H_2,\mu_2)$ on
$K/k$ are isomorphic if there exists a Hopf algebra isomorphism
$f:H_1 \rightarrow H_2$ such that $\mu_2 \circ f=\mu_1$.

For a Hopf Galois extension we have the following \emph{Galois
correspondence theorem}:

\begin{thm}[\cite{ChS}, Theorem 7.6]
Let $K/k$ be a finite field extension and let $(H,\mu)$ be a Hopf Galois
structure on $K/k$. For a $k$-sub-Hopf algebra $H'$ of $H$ we
define
$$
K^{H'}=\{x\in K \mid \mu(h)(x)=\eps(h)\cdot x \mbox{ for all }
h\in H'\}
$$
where $\eps$ is the counit of $H$. Then, $K^{H'}$ is a subfield
of $K$, containing $k$, and
$$
\begin{array}{rcl}
{\cal F}_H:\{H'\subseteq H \mbox{ sub-Hopf algebra}\}&\longrightarrow&\{\mbox{Fields }E\mid k\subseteq E\subseteq K\}\\
H'&\mapsto &K^{H'}
\end{array}
$$
is injective and inclusion reversing.
\end{thm}

Separable Hopf Galois extensions have been characterized by
Greither and Pareigis. Let $K/k$ be a separable extension of
degree $n$ and let $\wk/k$ be its Galois closure, $G=\Gal(\wk/k)$
and $G'=\Gal(\wk/K)$. The action of $G$ on the set
$G/G'$ of left cosets induces a group morphism

$$
 \begin{array}{rl}
\lambda: & G\rightarrow \Sym(G/G')=S_n\\
 &g\mapsto (\lambda_g: xG'\mapsto gxG')\, .
\end{array}
$$

\begin{thm}[\cite{GP} Theorem 3.1]\label{N}
With the above notations, a finite separable field extension $K/k$
is a Hopf Galois extension if and only if there exists a regular
subgroup $N$ of $S_n$ normalized by $\lambda (G)$. Moreover, there is a
one-to-one correspondence between the set of isomorphism classes
of Hopf Galois structures on $K/k$ and the set of regular
subgroups $N$ of $S_n$ normalized by $\lambda (G)$.
\end{thm}

The underlying Hopf algebra of the Hopf Galois structure corresponding to a subgroup $N$
is the sub-Hopf algebra $H=\wk[N]^G$ of $G$-fixed points in the group algebra $\wk[N]$, where $G$ acts on $\wk$ by field automorphisms and on
$N$ by conjugation inside $S_n$ via $\lambda$.

We shall use the following equivalent condition in our study of Hopf Galois structures.

\begin{thm}[\cite{Childs1} Proposition 1]
The group $\lambda (G)$ normalizes the regular subgroup $N$ of $\Sym(G/G')$ if and
only if $\lambda (G)$ is a subgroup of the holomorph $\Hol(N)=N \rtimes \Aut N$ of $N$.
\end{thm}

Within the class $\mathcal{HG}$ of separable Hopf Galois
extensions, Greither and Pareigis defined the subclass $\mathcal{AC}$ of almost classically
Galois extensions and proved that $\mathcal{AC}$ is included in the class $\mathcal{B}$
of separable Hopf Galois
extensions which may be endowed with a
Hopf Galois structure such that the Galois correspondence is
bijective (\cite{GP} \S 4). In \cite{CRV}, we proved that the
two inclusions $\mathcal{AC} \subset \mathcal{B}$ and $\mathcal{B} \subset \mathcal{HG}$ are strict.

In \cite{CRV2}, Example 2.1, we exhibited a degree 8 Hopf Galois
extension of the field $\Q$ of rational numbers which is not
almost classically Galois. In this paper, we study the Hopf Galois
structures of this extension and prove that there are two
non-isomorphic Hopf Galois structures with isomorphic underlying
Hopf algebras. In the last section, we observe that the image of
the Galois correspondence of a Hopf Galois structure does not
determine the isomorphism class of the underlying Hopf algebra.

\section{A Hopf Galois degree 8 extension}

Let us consider a Galois extension $\widetilde{K}/k$ with Galois
group $G$ isomorphic to the symmetric group $S_4$ and let $G'$ be
an order 3 subgroup of $G$. Let $K$ be the subfield of
$\widetilde{K}$ fixed under the action of $G'$. If $S_4$ is
realized over $k$ as the splitting field of a degree four
polynomial $P(X) \in k[X]$, then $K=k(\alpha,\sqrt{\delta})$,
where $\alpha$ is a root of $P(X)$ and $\delta$ its discriminant.
We showed in \cite{CRV2} Proposition 2.1 that such an extension
$K/k$ is Hopf Galois but not almost classically Galois.

\subsection{Hopf Galois structures}

According to theorem \ref{N}, in order to determine the Hopf
Galois structures of $K/k$, we look at regular subgroups $N$ of
$S_8$. Since the set of isomorphism classes of regular subgroups
of $S_8$ is in one-to-one correspondence with the set of
isomorphism classes of groups of order 8, we have five possible
groups $N$, up to isomorphism, namely the abelian groups
$C_8$, $C_2 \times C_4$ and $C_2 \times C_2 \times C_2$, the
dihedral group $D_{8}$ and the quaternion group $H_8$. If we look
for holomorphs having order divisible by 24, we are left with $C_2
\times C_2 \times C_2$ and $H_8$. But the holomorf of $H_8$ has no
transitive subgroups isomorphic to $S_4$. So the only possible
$N$'s are isomorphic to $C_2 \times C_2 \times C_2$.

Let us now determine explicitly the immersion $\lambda$ of $G$
into $Perm(G/G')$. Taking $G=\langle \tau:=(1,2,3,4),\sigma:=(1,2)\rangle$  and
$G'=\langle (2,3,4) \rangle$, a left transversal of $G'$ in $G$ is
$\{1_G,(1,2), (1,3),
(1,4), (2,3),
(1,2,3),(1,3,4), (1,4,2)
\}.$ By choosing an enumeration
of the cosets, we may take $\lambda(G)=\langle \lambda(\tau)=(1,2,3,4)(5,6,7,8),
\lambda(\sigma)=(1,2)(3,5)(4,6)(7,8)\rangle$ and then
$\lambda(G')=\langle (2,4,5)(3,8,6)\rangle$.

The conjugation class of regular subgroups of $S_8$ isomorphic to
$C_2 \times C_2 \times C_2$ has length 30. There are exactly four
subgroups $N$ in it satisfying $\lambda(G) \subset Norm_{S_8}(N)$,
namely:

$$\begin{array}{l}
N_1=\langle r_1=(1,3)(2,4)(5,7)(6,8), s_1=(1,8)(2,7)(3,6)(4,5), t=(1,7)(2,8)(3,5)(4,6)\rangle\\
N_2=\langle r_2=(1,3)(2,6)(4,8)(5,7), s_2=(1,4)(2,5)(3,8)(6,7), t=(1,7)(2,8)(3,5)(4,6)\rangle\\
N_3=\langle r_3=(1,6)(2,4)(3,8)(5,7), s_3=(1,7)(2,3)(4,8)(5,6), t_3=(1,8)(2,5)(3,6)(4,7)\rangle\\
N_4=\langle r_4=(1,3)(2,5)(4,7)(6,8),s_4=(1,7)(2,6)(3,4)(5,8),
t_4=(1,6)(2,7)(3,8)(4,5)
\rangle
\end{array}$$

We have then four Hopf Galois structures on $K/k$, up to
isomorphism.

\subsection{Galois correspondence}

By classical Galois theory, the extension $K/k$ has two strictly
intermediate fields, $k(\sqrt{\delta})$ and $k(\alpha)$.  We shall
now determine the image of the Galois correspondence for each of
the Hopf Galois structures. To this end, we compute the subgroups
of each of the corresponding $N$'s which are stable under
conjugation by $\lambda(G)$ (see the reformulation of the Galois correspondence theorem
in terms of groups in \cite{CRV} Theorem 2.3). The action of $\tau$ and $\sigma$ on
the generators of each $N_i$, $1\leq i \leq 4$, is given in the following table.

\vspace{0.5cm}
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|}
\hline
& $r_1$ & $s_1$ & $t$ &$r_2$ & $s_2$ & $r_3$ & $s_3$ & $t_3$& $r_4$ & $s_4$ & $t_4$ \\
\hline \hline
$\tau$ & $r_1$ & $r_1 s_1$ & $t$ &$r_2t$ & $r_2s_2t$ & $r_3t_3$ & $r_3s_3$ & $t_3$& $r_4t_4$ & $r_4s_4$ & $t_4$ \\
\hline
$\sigma$ & $r_1s_1$ & $s_1$ & $t$ &$s_2$ & $r_2$ & $r_3$ & $r_3s_3$ & $r_3t_3$& $r_4$ & $r_4s_4$ & $r_4t_4$ \\
\hline
\end{tabular}
\end{center}

\vspace{0.5cm} The $\lambda(G)$-stable subgroups of each $N$ and
the corresponding intermediate fields of $K/k$ are given in the
following table.

\vspace{0.5cm} \begin{center}
\begin{tabular}{c|c|c}
Groups & Stable subgroups & Fixed subfields \\
\hline
$N_1$ & $\langle t\rangle, \langle r_1, s_1\rangle$ & $k(\alpha), k(\sqrt{\delta})$ \\
$N_2$ & $\langle t\rangle$ & $k(\alpha)$ \\
$N_3$ & $\langle r_3, t_3\rangle$ & $k(\sqrt{\delta})$ \\
$N_4$ & $\langle r_4, t_4\rangle$ & $k(\sqrt{\delta})$  \\
\end{tabular}
\end{center}

\subsection{A Hopf algebra with two different Hopf Galois structures}

We shall analize now if two of the underlying Hopf algebras of the four Hopf Galois structures
on $K/k$ may be isomorphic. Two Hopf algebras $H_i=\widetilde{K}[N_i]^G$ and $H_j=\widetilde{K}[N_j]^G$ are isomorphic if and
only if the groups $N_i$ and $N_j$ are $G$-isomorphic. By looking at the stable subgroups of
each of the groups $N$, we see that the only possible $G$-isomorphism is between $N_3$ and $N_4$. Now the isomorphism $\Phi:N_3  \rightarrow N_4$ defined by
$\Phi(r_3)=r_4, \Phi(s_3)=s_4, \Phi(t_3)=t_4$ is clearly a
$G$-isomorphism. It may also be seen as induced by conjugation by
$s=(1,7)(2,8)(3,5)(4,6)$  and $s$ satisfies $s g^{-1} s g \in
Cent_{S_8}(N_3)$ since $s \tau^{-1} s \tau =s \sigma^{-1} s \sigma
=Id$.  One may check that $N_3$ has no nontrivial
$G$-automorphisms, hence $\Phi$ is the unique $G$-isomorphism from
$N_3$ onto $N_4$.

The isomorphism $\Phi$ induces a Hopf algebra isomorphism between
$H_3=\widetilde{K}[N_3]^G$ and $H_4=\widetilde{K}[N_4]^G$ but
Theorem \ref{N} implies that the corresponding Hopf Galois
structures are not isomorphic. We do now a direct check of this
fact. We determine first the  Hopf algebra $H_3=\widetilde{K}[N_3]^G= \{ h \in \widetilde{K}[N_3] \, | \, \empty^g\! h=h \, , \forall g \in G \}$. From the action
of $G$ on $N_3$ determined above we obtain that an element
$h=\sum_{n \in N_3} a_n n= a_{0} Id+ a_{1} r_3 + a_{2} s_3 + a_{3}
t_3 + a_{4} r_3 s_3 + a_{5} r_3 t_3+a_6 s_3 t_3+ a_7 r_3 s_3 t_3
\in \wk[N_3]$ belongs to $H_3$ if and only if

$$\begin{array}{l} a_0 \in k, a_1 \in \wk^{\langle \sigma, \tau^2\rangle}, a_2 \in
k(\alpha), a_3=\sigma \tau(a_1), \\ a_5=\tau(a_1), a_4=\tau(a_2),
a_6=\tau^2(a_2), a_7=\tau^3(a_2).\end{array}$$

If $N$ is a regular subgroup of $Perm(G/G')$ normalized by $G$ and
$H=\wk[N]^G$ is the corresponding Hopf algebra, the Hopf action
$\mu: H \rightarrow End_k(K)$ is given by

$$(\sum a_n n) \cdot x= \sum a_n (n^{-1})(1_G)(x).$$

To make the Hopf actions $\mu_3$ and $\mu_4$ of $H_3$ and $H_4$
explicit, we first compute the preimage of $\overline{1_G}$ under the
elements of $N_3$ and $N_4$.

\vspace{0.5cm}

\begin{tabular}{c||c|c|c|c|c|c|c|c}

$n \in N_3$ & \,  $Id$ \,  & $r_3$ & $s_3$ & $t_3$ & $r_3s_3$ & $r_3t_3$ & $s_3t_3$ & $r_3s_3t_3$
\\
\hline
$(n^{-1})(\overline{1_G})$ & $\overline{1_G}$ & $\overline{(1,4,2)}$&$\overline{(2,3)}$& $\overline{(1,2,3)}$ & $\overline{(1,3)}$&$\overline{(1,3,4)}$ & $\overline{(1,4)}$&
$\overline{(1,2)}$ \end{tabular}

\vspace{0.5cm}

\begin{tabular}{c||c|c|c|c|c|c|c|c}

$n \in N_4$ &  \, $Id$ \,  & $r_4$ & $s_4$ & $t_4$ & $r_4s_4$ & $r_4t_4$ & $s_4t_4$ & $r_4s_4t_4$
\\
\hline
$(n^{-1})(\overline{1_G})$ & $\overline{1_G}$ & $\overline{(1,3,4)}$&$\overline{(2,3)}$& $\overline{(1,4,2)}$ & $\overline{(1,4)}$&$\overline{(1,2,3)}$ & $\overline{(1,2)}$&
$\overline{(1,3)}$ \end{tabular}

\vspace{0.5cm}

Let $\alpha_1=\alpha, \alpha_2, \alpha_3, \alpha_4$ be the four roots
of the polynomial $P(X)$ in $\widetilde{K}$. We consider the element $h= \alpha_1^2
s_3+ \alpha_2^2 r_3 s_3+ \alpha_3^2 s_3 t_3+\alpha_4^2 r_3 s_3 t_3
\in H_3$. We have

$$\begin{array}{rll} \mu_3(h)(\alpha_1) & = & \alpha_1^3+\alpha_2^2 \alpha_3+ \alpha_3^2 \alpha_4+\alpha_4^2
\alpha_2, \\ \mu_4(\Phi(h))(\alpha_1)&=& \mu_4(\alpha_1^2 s_4+
\alpha_2^2 r_4 s_4+ \alpha_3^2 s_4 t_4+\alpha_4^2 r_4 s_4
t_4)(\alpha_1)\\ &=& \alpha_1^3+\alpha_2^2\alpha_4+\alpha_3^2\alpha_2+\alpha_4^2\alpha_3.\end{array}$$

\noindent In order to see $\alpha_2^2 \alpha_3+ \alpha_3^2
\alpha_4+\alpha_4^2 \alpha_2 \neq
\alpha_2^2\alpha_4+\alpha_3^2\alpha_2+\alpha_4^2\alpha_3$, we
write both elements in the $k$-basis
$(\alpha_4^{i_4}\alpha_3^{i_3}\alpha_2^{i_2})_{0\leq i_4\leq 3, 0\leq i_3\leq 2,
0\leq i_2\leq 1}$ of $\wk$. Writing $P(X)=X^4-b_1X^3+b_2X^2-b_3X+b_4$, we obtain

$$\begin{array}{l}\alpha_2^2 \alpha_3+ \alpha_3^2 \alpha_4+\alpha_4^2
\alpha_2=\alpha_4^3+(\alpha_2-b_1)\alpha_4^2+(-\alpha_2\alpha_3+b_2+\alpha_3^2)
\alpha_4 +(-\alpha_3^2+b_1\alpha_3)\alpha_2-b_3, \\
\alpha_2^2\alpha_4+\alpha_3^2\alpha_2+\alpha_4^2\alpha_3=
-\alpha_4^3+(-\alpha_2+b_1)
\alpha_4^2+((b_1-\alpha_3)\alpha_2-b_2+b_1\alpha_3-
\alpha_3^2)\alpha_4+\alpha_2\alpha_3^2. \end{array}$$

\section{Final remarks}

Let $K/k$ be a separable extension of degree $n$ and let $G$ be
the Galois group of the Galois closure of $K/k$. Clearly, the fact
that two regular subgroups of $S_n$ are $G$-isomorphic implies
that the corresponding Hopf Galois structures have the same Galois
correspondence image. The converse is not true. In \cite{CRV}
Theorem 3.4, we give a family of Hopf Galois extensions having two
Hopf Galois structures of cyclic and Frobenius type, respectively,
with the same Galois correspondence image.

Let us now consider a Galois extension $K/k$ with Galois group a
Hamiltonian group $G$, i.e. $G$ is a non-abelian group such that
all its subgroups are normal subgroups. All Hamiltonian groups are
of the form  $H_8\times B \times D$, where $H_8$ is the quaternion
group, $B$ is the direct sum of some number of copies of the
cyclic group $C_2$, and D is a periodic abelian group with all
elements of odd order (see \cite{H} \S 12.5). Let $n$ be the order
of $G$. We may consider two Hopf Galois structures on $K/k$
associated to two subgroups of $S_n$ isomorphic to $G$, the group
$\rho(G)$, where $\rho$ is induced by the action of $G$ on itself
by right translation, and the group $\lambda(G)$. For the first
one, the Hopf algebra is the group algebra $k[G]$ and the Hopf
action is the linear extension of the action of the Galois group
$G$ by $k$-automorphisms of $K$. For the second one, the image of
the Galois correspondence is the set of intermediate fields $E$
such that $E/k$ is Galois (\cite{GP}, Theorem 5.3), which in the
case of Hamiltonian groups is the whole sublattice. We obtain then
two Hopf Galois structures with same Galois correspondence image
associated to two isomorphic but not $G$-isomorphic regular
subgroups of $S_n$.