text:
\begin{document}
\newgeometry{tmargin=3cm, bmargin=3cm, lmargin=2.5cm, rmargin=2.5cm}
\pagestyle{empty}

\begin{center}
\begin{large}
\textbf{The Girth of Cayley graphs of Sylow 2-subgroups of~symmetric~groups~$S_{2^n}$ on diagonal bases}\\
\end{large}
Bart³omiej Pawlik\\
\end{center}

\begin{small}
\textbf{Keywords.} Sylow $p$-subgroup $\cdot$  Wreath product $\cdot$ Cayley graph $\cdot$ Girth of graph

\bigskip

\textbf{Abstract.} A diagonal base of a Sylow 2-subgroup $P_n(2)$ of symmetric group $S_{2^n}$ is a minimal generating set of this subgroup consisting of elements with only one non-zero coordinate in the~polynomial representation. For different diagonal bases Cayley graphs of $P_n(2)$ may have different girths (i.e.~minimal lengths of cycles) and thus be non-isomorphic. In presented paper all possible values of girths of Cayley graphs of $P_n(2)$ on diagonal bases are calculated. A criterion for whenever such Cayley graph has girth equal to 4 is presented. A lower bound for the number of different non-isomorphic Cayley graphs of $P_n(2)$ on diagonal bases is proposed.
\end{small}

\section{Introduction.}

\bigskip

Let $P_n(p)$ be a Sylow $p$-subgroup of symmetric group $S_{p^n}$.  A minimal generating set of group G, i.e. a generating set from which none of the elements can be removed, is called \textit{a base} of group G. All bases of $P_n(p)$ contain exactly $n$ elements (see \cite{paw2016}, \cite{sus2009}).

It is known that given a generating set $S$ of group $G$, the Cayley graph $\Cay(G,S)$ of $G$ with respect to $S$ is a simple directed graph with vertex set $V(\Cay(G,S)) = G$ and the set of edges
$$E(\Cay(G,S))=\{(uv)|\,\exists(s\in S):\,v=us\}.$$
If additionally $S$ is symmetric (i.e. $S=S^{-1}$) then $\Cay(G,S)$ may be considered undirected. For two different generating sets $S$ and $S'$ of group $G$, the resulting Cayley graphs $\Cay(G,S)$ and $\Cay(G,S')$ may differ and be non-isomorphic. Thus a fundamental question in the~study of Cayley graphs of groups is the graph isomorphism problem. It has been widely studied by many authors (see e.g. \cite{ bab1978, dob1995, kon2008, sus2009}, and for the survey - \cite{li2002}). On approach to address the~graph isomorphism problem is to study graph features, which are invariant to isomorphisms, e.g. diameter, chromatic number, clique number, independence number (see e.g. \cite{bam2014, gan2013, gre2017, klo2007}) or girth (\cite{gam2009, loz2011}). Let us recall the result of \cite{gam2009}] which states that the girth $g_n$ of random Cayley graphs of Sylow $p$-subgroups $P_n(p)$ of group $S_{p^n}$ satisfies
$$(1-o(1))\beta\log\log|P_n(p)|\leq g_n\leq(1+o(1))(\log|P_n(p)|)^\alpha,$$
with $n\rightarrow\infty$, where $\alpha<1$ is a constant depending on $p$ only, and $\beta$ depends on $p$ and $d$ (degree of regularity of given graph). This paper presents an example of family of Cayley graphs of Sylow 2-subgroups $P_n(2)$ of group $S_{2^n}$ which, for all $n$, have a girth at most 8.

In this paper we investigate Cayley graphs of $P_n(p)$ defined on the generating sets of certain type, the so called diagonal beses (see \cite{paw2016, sus2009}). Since every diagonal base consists of involutions, the respective Cayley graphs are simple and undirected.

 It is known that group $P_n(2)$ is isomorphic to the group $\Aut(T_2^n)$ of automorphisms of a~rooted binary tree~$T^n_2$ of height $n$ (see e.g. \cite{bie2015}). The base $D=\{D_1,\ldots,D_n\}$ of $P_n(2)$ such that element $D_i$ for $i=1,\ldots,n,$ acts only on the $i$-th level of $T^n_2$ is called a \textit{diagonal base}. \textit{The girth} of given graph $\Gamma$ is the length of the minimal cycle of this graph. The Cayley graph $\Cay(P_n,D)$ of group $P_2(2)$ on any diagonal base $D$ is a $C_8$ cycle and it is isomorphic to an induced subgraph of any Cayley graph of $P_n(2)$ on diagonal base $D$ for $n>2$ (see \cite{paw2016}). Thus every graph $\Cay(P_n(2),D)$, where $D$ is a~diagonal base and $n\geq2$, contains a~cycle of length~8, however, not necessarily it is minimal. For given $n\geq3$ there exist Cayley graphs of $P_n(2)$ on diagonal bases which have smaller minimal cycles, and thus not every two such Cayley graphs of $P_n(2)$ are isomorphic. In this paper we classify Cayley graphs of $P_n(2)$ on diagonal bases with respect to their girths in the following

\begin{theorem}[Main Theorem]\label{maintheorem}
 Let $D=\{D_1,\ldots,D_n\}$ be a diagonal base of $P_n(2)$.
 \begin{enumerate}
 \item The girth of $\Cay(P_n(2),D)$ is either 4, 6 or 8.
 \item For $n\geq3$ the girth of $\Cay(P_n(2),D)$ is equal to 4 if and only if $D$ contains two commuting elements, i.e. $D$ satisfies condition $(\star)$ stated in Section~3.
 \item For all $n\geq2$ there exists $D$ such that the girth of $\Cay(P_n(2),D)$ is equal to 8.
 \item For all $n\geq5$ there exists $D$ such that the girth of $\Cay(P_n(2),D)$ is equal to 6. For $n<5$ there are no such diagonal bases.
 \end{enumerate}
 \end{theorem}

 By the result of \cite{paw2016} the upper bound for the number of non-isomorphic Cayley graphs of $P_n(2)$ is equal to $\displaystyle2^{2^n-2n}$. We apply point 2 of Theorem \ref{maintheorem} to obtain a lower bound: we show that the~number of non-isomorphic Cayley graphs of $P_n(2)$ on diagonal bases is at least $\displaystyle2^{n-2}$.

The paper is organized as follows. In Section 2 we recall some basic facts about groups $P_n(2)$, their polynomial representation and diagonal bases. Also in this Section we recall some basic facts and properties of Cayley graphs. In Section 3 we prove the Main Theorem. Application of the Main Theorem to estimate the lower bound of the number of non-isomorphic Cayley graphs of $P_n(2)$ on diagonal bases is proposed in Section 4.

\section{Preliminaries.}

Let $X_n$ be a sequence of variables $x_1,\ldots,x_n$.

It is well known (see e.g. \cite{kal1948}) that the Sylow $p$-subgroups of group $S_{p^n}$ are isomorphic with an~$n$-iterated wreath product of cyclic groups $C_p$, namely
$$P_n(p)\cong \underbrace{C_p\wr C_p\wr\ldots\wr C_p}_{n}.$$
Group $C_p$ is isomorphic to the additive group $\mathbb{Z}_p$, thus every element $f\in P_n(p)$ may be written as
\begin{equation}\label{eq:f}
f=[f_1,f_2(X_1),f_3(X_2),\ldots,f_n(X_{n-1})],
\end{equation}
where $f_1\in\mathbb{Z}_p$ and $f_i:\mathbb{Z}_p^{i-1}\rightarrow\mathbb{Z}_p$ for $i=2,\ldots,n$ are reduced polynomials from the quotient ring $\mathbb{Z}_p[X_i]/\langle x_1^p-x_1,\ldots,x_i^p-x_i\rangle$. We call such element $f$ a \textit{tableau}.

For tableaux $f,g\in P_n(p)$, where $f$ has form (\ref{eq:f}) and $$g=[g_1,g_2(X_1),g_3(X_2),\ldots,g_n(X_{n-1})]$$ the product $fg$ has the form
\begin{align*}
fg=\big[&f_1+g_1,\,f_2(X_1)+g_2(x_1+f_1),\,\ldots,\\
&f_n(X_{n-1})+g_n(x_1+f_1,x_2+f_2(X_1),\ldots,x_{n-1}+f_{n-1}(X_{n-2}))\big],
\end{align*}
and the inverse $f^{-1}$ of an element $f$ has the form
\begin{align*}
f^{-1}=\Big[&-f_1,-f_2(x_1-f_1),\ldots,\\
&-f_n\big(x_1-f_1,x_2-f_2(x_1-f_1),\ldots,x_{n-1}-f_{n-1}(x_1-f_1,\ldots)\big)\Big].
\end{align*}

Let $[f]_i$ be the $i$-th coordinate of tableau $f$, i.e. $[f]_1=f_1$ and $[f]_i=f_i(X_{i-1})$ for $i=2,\ldots,n$, and $(f)_i$ be a tableau consisting of first $i$ coordinates of $f$, i.e. $(f)_i=[f_1,\ldots,f_i(X_{i-1})]$.

\smallskip

Further in this paper tableau $[0,\ldots,0]$ will be simply denoted as $0$.

\bigskip

Let $\overline{x_n}=x_1\cdot x_2\cdot\ldots\cdot x_n$ and $$\overline{x_n}/x_i=x_1\cdot x_2\cdot\ldots\cdot x_{i-1}\cdot x_{i+1}\cdot\ldots\cdot x_n.$$

\smallskip

A diagonal base of $P_n(2)$, defined in the Introduction consists of these and only these automorphisms of $T_2^n$, whose action is nontrivial on a unique level of the tree. In terms of  polynomial representation, diagonal bases may be defined as following.

\begin{definition}
Base $D=\{D_1,\ldots,D_n\}$ of $P_n(2)$ is called diagonal if $[D_i]_j=0$ for any $i$ ($1\leq i\leq n$) and $j\neq i$.
\end{definition}

It is known (see e.g. \cite{kal1948}) that in every base $D$ of $P_n(2)$ for every $i$ there exists a tableau $D'\in D$ which contains a monomial $\overline{x_{i-1}}$ on $i$-th coordinate. Thus, the nonzero coordinates of elements of diagonal base $D=\{D_1,\ldots,D_n\}$ have form $[D_1]_1=1$ and $[D_i]_i=d_i(X_{i-1})$, where $d_i$ contains monomial $\overline{x_{i-1}}$ for every $i=2,\ldots,n$.

We also note that every element of diagonal base $D=\{D_1,\ldots,D_n\}$ is an involution, i.e. $D_i^2=0$ for $i=1,\ldots,n$.

\bigskip

\bigskip

For any graph $\Gamma$ let $V(\Gamma)$ be a vertex set of $\Gamma$ and $E(\Gamma)$ be the set of edges of $\Gamma$.

\bigskip

Let $S=\{s_1,\ldots,s_n\}$ be a generating set of a finite group $G$. The Cayley graph $\Cay(G,S)$ contains a cycle if and only if for some $g\in G$ there exists an irreducible product $s_{i_1}s_{i_2}\ldots s_{i_k}$, where $s_{i_j}\in S$ for every $j=1,\ldots,k$, such that
$$gs_{i_1}s_{i_2}\ldots s_{i_k}=g.$$
The above equality is equivalent to
$$s_{i_1}s_{i_2}\ldots s_{i_k}=0.$$
Thus there holds the following
\begin{lemma}\label{l:pod}
If $S=\{s_1,\ldots,s_n\}$ is a generating set of a finite group $G$ and for some generators $s_{i_1},s_{i_2},\ldots,s_{i_k}$ the product  $s_{i_1}s_{i_2}\ldots s_{i_k}$ is irreducible and equal to 0, then $\Cay(G,S)$ contains a cycle of length $k$.
\end{lemma}

If $S=S^{-1}$, then $\Cay(G,S)$ is an undirected graph (i.e. if $s$ is an involution and if $u=vs$, then also $v=us$). Since every element of a diagonal base of $P_n(2)$ is an involution, the corresponding Cayley graphs of $P_n(2)$ may be considered as undirected.

\bigskip

Let us recall some graph theory facts, which will be useful in the last Section of this paper.

\smallskip

For any finite connected graph $\Gamma$ we define a natural metric $\sigma$ on the~set of vertices $V(\Gamma)$ in the~following way: $\sigma(u,v)=n$ if and only if the shortest way from vertex $u$ to vertex $v$ contains exactly $n$~edges (we assume that $\sigma(v,v)=0$ for every vertex $v$). We define a special type of induced subgraphs of a graph $\Gamma$.

\begin{definition}
Let $B(v,r)$ be the induced subgraph of given graph $\Gamma$ such that $v\in V(\Gamma)$, $r$~is fixed positive integer and $$V(B)=\{u\in V(\Gamma)|\,\sigma(u,v)\leq r\}.$$
We call $B(v,r)$ a ball with center $v$ and radius $r$.
\end{definition}

\section{Proof of the Main Theorem.}

Let $D=\{D_1,\ldots,D_n\}$ be a diagonal base of $P_n(2)$. Every $D_i$ ($i\geq2$) contains the monomial $\overline{x_{i-1}}$, thus if element $D_i$ appears in the product $D_{j_1}D_{j_2}\ldots D_{j_k}$ an odd number of times, then
$$[D_{j_1}D_{j_2}\ldots D_{j_k}]_i=\overline{x_{i-1}}+f(X_{i-1}),$$
where $f$ do not contain the monomial $\overline{x_{i-1}}$. Thus the necessary condition for the~equation
$$[D_{j_1}D_{j_2}\ldots D_{j_k}]_i=0$$
to hold is that the element $D_i$ appears in this product an even number of times. Hence from Lemma~\ref{l:pod} we get that every cycle of a graph $\Cay(P_n(2),D)$ has even length. Thus the minimal possible girth is equal to 4. As we stated in Introduction, every such graph for $n\geq2$, contains a cycle of length 8, so the girth is at most equal to 8. Let us investigate whenever such graph have lower girth.

\bigskip

Firstly, let us investigate for which diagonal bases of $P_n(2)$ there exists a cycle of length~4. The Graph $\Cay(P_2(2),D)$ is isomorphic to cyclic graph $C_8$, so it do not contain cycles of length~4.

\bigskip

For $n\geq3$ we say that the diagonal base $D=\{D_1,\ldots,D_n\}$ of group $P_n(2)$ satisfies condition~$(\star)$ if and only if for some $D_i$ ($2\leq i<n$) there exists $D_j$ $(i<j\leq n)$ of the form
$$[D_j]_j=\overline{x_{j-1}}+x_ig(X_{j-1})+h(X_{j-1}),$$
where $g$ and $h$ do not contain variable $x_i$ and $g$ do not contain a monomial $\overline{x_{j-1}}/x_i$, such that
$$g(X_{j-1})[D_i]_i=\alpha\cdot\overline{x_{j-1}}/x_i,$$
where
$$\alpha=
\left\{\begin{array}{ll}
0,&\mbox{ if }[D_i]_i\mbox{ contains even number of nonzero monomials,}\\
1,&\mbox{ if }[D_i]_i\mbox{ contains odd number of nonzero monomials.}
\end{array}\right.$$

\begin{proposition}\label{prop:1}
Let $D=\{D_1,\ldots,D_n\}$ be the diagonal base of $P_n(2)$, where $n\geq3$. The Cayley graph $\Cay(P_n(2),D)$ contains a cycle of length 4 if and only if $D$ satisfies condition~$(\star)$.
\end{proposition}

\begin{proof}

From Lemma \ref{l:pod}, the existence of cycle of length 4 in $\Cay(P_n(2),D)$ is equivalent to the existence of solution of equation

$$(D_iD_j)^2=0\ \ \ \ \mbox{ or }\ \ \ \ (D_jD_i)^2=0$$

for some $i,j,$ such that $i<j\leq n$.
The above equalities are equivalent and hold whenever $D_j$ and $D_i$ commute. Thus further we will only consider the case $(D_jD_i)^2=0$.

$D_jD_i$ is a tableau with only nonzero elements on $i$-th and $j$-th coordinates, namely
$$[D_jD_i]_i=[D_i]_i\ \ \ \mbox{ and }\ \ \ [D_jD_i]_j=[D_j]_j.$$

Thus $(D_jD_i)^2=0$ if and only if $$[(D_jD_i)^2]_i=0\ \ \ \mbox{ and }\ \ \ [(D_jD_i)^2]_j=0.$$
The first of the above equalities is always true (simple checking), so we have to investigate only the second one.

\smallskip

Firstly, let us assume that $i=1$. Of course $$D_1=[1,0,\ldots,0]$$ for every diagonal base $D$. Let $$[D_j]_j=\overline{x_{j-1}}+x_1g(X_{i-1})+h(X_{i-1}),$$ where $g$ and $h$ do not contain variable $x_1$ and $g$ do not contain the monomial $\overline{x_{j-1}}/x_1$. Thus
\begin{align*}
[(D_jD_1)^2]_j=&\,\overline{x_{j-1}}+x_1g(X_{i-1})+h(X_{i-1})+(\overline{x_{j-1}}/x_1)(x_1+1)+(x_1+1)g(X_{i-1})+h(X_{i-1})=\\
=&\,\overline{x_{j-1}}/x_1+g(X_{j-1}).
\end{align*}
But $g$ do not contain monomial $\overline{x_{j-1}}/x_1$, and so $\overline{x_{j-1}}/x_1+g(X_{j-1})\neq0$.

Hence the element $D_1$ do not commute with any other element of $D$, and thus it do not belong to any cycle of length 4 in the graph $\Cay(P_n(2),D)$.

\smallskip

Let us now investigate the general case for $1<i<j\leq n$.

Let
$$[D_i]_i=\overline{x_{i-1}}+f(X_{i-1}),$$
where $f$ do not contain a monomial $\overline{x_{i-1}}$ and let
$$[D_j]_j=\overline{x_{j-1}}+x_ig(X_{j-1})+h(X_{j-1}),$$
where polynomials $g$ and $h$ do not contain variable $x_i$ and $g$ do not contain a monomial $\overline{x_{j-1}}/x_i$.

Then
\begin{align*}
[(D_jD_i)^2]_j=&\,\overline{x_{j-1}}+x_ig(X_{j-1})+h(X_{j-1})+\\
&\,+(\overline{x_{j-1}}/x_i)(x_i+\overline{x_{i-1}}+f(X_{i-1}))+\\
&\,+(x_i+\overline{x_{i-1}}+f(X_{i-1}))g(X_{j-1})+h(X_{j-1})=\\
=&\,(\overline{x_{j-1}}/x_i)(1+f(X_{i-1}))+g(X_{j-1})(\overline{x_{i-1}}+f(X_{i-1})).
\end{align*}
The product $(\overline{x_{j-1}}/x_i)(1+f(X_{i-1}))$ is equal to 0 or $\overline{x_{j-1}}/x_i$ depending of number of nonzero monomials in $f$. Let us check both cases:

\begin{enumerate}

\item If the number of nonzero monomials on $f$ is odd, then $$(\overline{x_{j-1}}/x_i)(1+f(X_{i-1}))=0$$ and thus
$$[(D_jD_i)^2]_j=g(X_{j-1})(\overline{x_{i-1}}+f(X_{i-1}))=g(X_{j-1})[D_i]_i.$$
Hence in this case $D_j$ and $D_i$ commute if and only if $g(X_{j-1})[D_i]_i=0$.

\item If the number of nonzero monomials in $f$ is even, then $$(\overline{x_{j-1}}/x_i)(1+f(X_{i-1}))=\overline{x_{j-1}}/x_i$$ and thus
$$[(D_jD_i)^2]_j=\overline{x_{j-1}}/x_i+g(X_{j-1})(\overline{x_{i-1}}+f(X_{i-1}))=\overline{x_{j-1}}/x_i+g(X_{j-1})[D_i]_i.$$
Hence in this case $D_j$ and $D_i$ commute if and only if $g(X_{j-1})[D_i]_i=\overline{x_{j-1}}/x_i$.
\end{enumerate}
\end{proof}

From Proposition \ref{prop:1} we get some natural examples of Cayley graphs of $P_n(2)$ with/without cycles of length 4:

\begin{example}\label{e:1}
 \begin{enumerate}
  \item If $[D_i]_i=\overline{x_{i-1}}$ for every $i$ such that $1<i\leq n$, then $\Cay(P_n(2),D)$ do not contain a cycle of length 4.
  \item If $[D_i]_i=\overline{x_{i-1}}+a_i$ for every $i$ such that $1<i<n$ and $$\max\{a_i:1\leq i\leq n\}=1,$$ then $\Cay(P_n(2),D)$ contains a cycle of length 4.
 \end{enumerate}
\end{example}

In further investigation of the girths of $P_n(2)$ we will use the  following

\begin{proposition}\label{prop:2}
Let $D=\{D_1,\ldots D_n\}$ be a diagonal base of group $P_n(2)$ such that graph $\Cay(P_n(2),D)$ do not contain cycle of length 4, and let $D_{e_1},\ldots,D_{e_k}$ be those elements of~$D$ which contain an even number of monomials. Let $\overline{D}=\{\overline{D}_1,\ldots,\overline{D}_{n+1}\}$ be a diagonal base of $P_{n+1}(2)$ such that $(\overline{D}_i)_n=D_i$ for $i=1,\ldots,n$, and
$$[\overline{D}_{n+1}]_{n+1}=\overline{x_n}+\sum\limits_{j=1}^kx_{e_j}.$$
Then $\Cay(P_{n+1}(2),\overline{D})$ do not contain a cycle of length 4.
\end{proposition}

\begin{proof}
Graph $\Cay(P_{n+1},\overline{D})$ contains a cycle of length 4 if there exist different generators $\overline{D}_i,\overline{D}_j\in\overline{D}$ which commute. The graph $\Cay(P_n(2),D)$ do not contain a cycle of length 4, so none of generators $\overline{D}_1,\overline{D}_2,\ldots,\overline{D}_n$ commute. Thus we only have to show that for every $i=1,\ldots,n$ generator $\overline{D}_{n+1}$ do not commute with $\overline{D}_i$.

We have shown that the generator $\overline{D}_1$ do not commute with any other generator, so we may assume that $i\geq2$.

Let
$$[\overline{D}_i]_i=\overline{x_{i-1}}+d_i(X_{i-1}),$$
where $d_i$ do not contain a monomial $\overline{x_{i-1}}$.

Let us consider two cases:
\begin{enumerate}
\item $\overline{D}_i$ contains an even number of monomials.

In this case
\begin{align*}
[(\overline{D}_{n+1}\overline{D}_{i})^2]_{n+1}&=\overline{x_n}+\sum\limits_{j=1}^kx_{e_j}+(\overline{x_n}/x_i)(x_i+\overline{x_{i-1}}+d_i(X_{i-1}))+\sum\limits_{j=1,e_j\neq i}^kx_{e_j}+x_i+\overline{x_{i-1}}+d_i(X_{i-1})=\\
&=(\overline{x_n}/x_i)(1+d_i(X_{i-1}))+d_i(X_{i-1}).
\end{align*}
$d_i$ contains an odd number of nonzero monomials, so $d_i\neq0$ and $(\overline{x_n}/x_i)(1+d_i(X_{i-1}))=0$.

Thus $[(\overline{D}_{n+1}\overline{D}_i)^2]_{n+1}=d_i(X_{i-1})\neq0$.

\item $\overline{D}_i$ contains an odd number of monomials.

In this case
\begin{align*}
[(\overline{D}_{n+1}\overline{D}_{i})^2]_{n+1}&=\overline{x_n}+\sum\limits_{j=1}^kx_{e_j}+(\overline{x_n}/x_i)(x_i+\overline{x_{i-1}}+d_i(X_{i-1}))+\sum\limits_{j=1}^kx_{e_j}=\\
&=(\overline{x_n}/x_i)(1+d_i(X_{i-1})).
\end{align*}
$d_i$ contains an even number of monomials, so $(\overline{x_n}/x_i)(1+d_i(X_{i-1}))\neq0$ and hence $[(\overline{D}_{n+1}\overline{D}_i)^2]_{n+1}\neq0$.
\end{enumerate}
Thus none of elements of base $\overline{D}$ commutes, and so graph $\Cay(P_{n+1}(2),\overline{D})$ do not contain a~cycle of length 4.
\end{proof}

The Cayley graph $\Cay(P_n(2),D)$ on diagonal base $D=\{D_1,\ldots,D_n\}$ contains a cycle of length 6 if and only if there exists generators $D_i,\,D_j,\,D_k$, where $i<j<k$ such that one of the following equalities holds:
\begin{align*}
(D_kD_jD_i)^2&=0\\
(D_kD_iD_j)^2&=0\\
D_kD_jD_iD_jD_kD_i&=0\\
D_kD_jD_kD_iD_jD_i&=0\\
D_kD_jD_iD_kD_iD_j&=0
\end{align*}

Let us notice that only the last equation do not imply the existence of cycle of length 4 (for example if $D_kD_jD_iD_jD_kD_i=0$, then also $D_jD_iD_jD_i=0$). Thus $\Cay(P_n(2),D)$ have a~minimal cycle of length 6 iff none of the elements of $D$ commute and if for some generators $D_i,\,D_j,\,D_k$ ($i<j<k$) the following equality holds:
\begin{equation}\label{eq:1}
D_kD_jD_iD_kD_iD_j=0.
\end{equation}

Before we state the next proposition, we will need the following technical Lemma:

\begin{lemma}\label{l:c6}
If $D=\{D_1,\ldots,D_n\}$ is a diagonal base of $P_n(2)$ where $n\geq3$, then
$$D_kD_jD_1D_kD_1D_j\neq0$$
for every $j,k$ such that $1<j<k\leq n$.
\end{lemma}

\begin{proof}
Let
$$[D_j]_j=\overline{x_{j-1}}+x_1f_1(X_{j-1})+f_2(X_{j-1}),$$
where $f_1$ and $f_2$ do not contain the variable $x_1$ and $f_1$ do not contain the monomial $\overline{x_{j-1}}/x_1$ and let
$$[D_k]_k=\overline{x_{k-1}}+x_1x_jg_1(X_{k-1})+x_1g_2(X_{k-1})+x_jg_3(X_{k-1})+g_4(X_{k-1}),$$
where $g_1,g_2,g_3,g_4$ do not contain the variables $x_1$ and $x_j$ and $g_1$ do not contain the monomial $\overline{x_{k-1}}/(x_1x_j)$.

\smallskip

Of course $[D_kD_jD_1D_kD_1D_j]_l=0$ for every $l=1,\ldots,n$ such that $l\neq k$. Let us investigate the~$k$-th coordinate:
$$[D_kD_jD_1D_kD_1D_j]_k=x_jh_1(X_{k-1})+h_2(X_{k-1}),$$
where
$$h_1(X_{k-1})=g_1(X_{k-1})+\overline{x_{k-1}}/(x_1x_j)$$
and
\begin{align*}
h_2(X_{k-1})=&(\overline{x_{k-1}}/(x_1x_j))\Big(x_1f_1(X_{j-1})+f_2(X_{j-1})\Big)+\\
&+x_1\Big(f_2(X_{j-1})g_1(X_{k-1})+f_1(X_{j-1})g_3(X_{k-1})\Big)+\\
&+g_2(X_{k-1})+f_2(X_{j-1})g_1(X_{k-1})+f_2(X_{j-1})g_3(X_{k-1}).
\end{align*}
Let us notice that $h_1$ and $h_2$ do not contain the variable $x_j$. Thus $[D_kD_jD_1D_kD_1D_j]_3=0$ if and only if $h_1(X_{k-1})=0$ and $h_2(X_{k-1})=0$. But from assumption that $g_1$ do not contain the monomial $\overline{x_{k-1}}/(x_1x_j)$ we get $h_1(X_{k-1})\neq0$ and hence $[D_kD_jD_1D_kD_1D_j]_k\neq0$.
\end{proof}

\begin{proposition}\label{prop:3}
A diagonal base $D$ such that the girth of $\Cay(P_n(2),D)$ is equal to 6 exists if and only if $n\geq5$.
\end{proposition}

\begin{proof}
Firstly, let us show that for $n<5$ there are no Cayley graphs of the group $P_n(2)$ on diagonal base $D$ which have girth equal to 6.

\smallskip

Graph $\Cay(P_2(2),D)$ for any diagonal base $D$ is isomorphic to cyclic graph $C_8$, so its girth is equal to 8.

\smallskip

Graph $\Cay(P_3(2),D)$, where $D=\{D_1,D_2,D_3\}$ is a diagonal base of $P_3(2)$, contains a~minimal cycle of length 6 only if the equation
$$D_3D_2D_1D_3D_1D_2=0$$
holds, but from Lemma \ref{l:c6} this is not possible.

\smallskip

Graph $\Cay(P_4(2),D)$, where $D=\{D_1,D_2,D_3,D_4\}$ is a diagonal base of $P_4(2)$, contains a~minimal cycle of length 6 if and only if none of elements of $D$ commute and the equation
$$D_4D_3D_2D_4D_2D_3=0$$
holds. Direct calculations show that there is no diagonal base $D$ satisfying both conditions.

\bigskip

Now let us recall the following base $S=\{S_1,\ldots,S_5\}$ of $P_5(2)$:

\bigskip

\begin{tabular}{llllll}
$S_1=[1,$&$0,$&$0,$&$0,$&$0$&$],$\\
$S_2=[0,$&$x_1+1,$&$0,$&$0,$&$0$&$],$\\
$S_3=[0,$&$0,$&$\overline{x_2}+x_2,$&$0,$&$0$&$],$\\
$S_4=[0,$&$0,$&$0,$&$\overline{x_3}+x_2x_3+x_1+1,$&$0$&$],$\\
$S_5=[0,$&$0,$&$0,$&$0,$&$\overline{x_4}+x_2x_3+x_3x_4+x_2+x_4$&$],$\\
\end{tabular}

\bigskip

Let us notice, that for any $1\leq i<j\leq5$ the inequality $(S_jS_i)^2\neq0$ holds. Moreover it is easy to check that
$$S_5S_4S_2S_5S_2S_4=0,$$
thus the girth of $\Cay(P_5(2),S)$ is equal to 6.

Applying Proposition \ref{prop:2} to this base we obtain a Cayley graph $\Cay(P_n(2),D)$ with girth equal to 6 for any $n>5$.

\end{proof}

Let us recall the diagonal base from Example \ref{e:1}, which do not contain a cycle of length 4.

\begin{proposition}\label{prop:4}
Let $D=\{D_1,\ldots,D_n\}$ be a diagonal base of $P_n(2)$, $n\geq2$, such that $[D_1]_1=1$ and $[D_i]_i=\overline{x_{i-1}}$ for every $i=2,\ldots,n$. The girth of graph $\Cay(P_n(2),D)$ is equal to 8.
\end{proposition}

\begin{proof}
From Proposition \ref{prop:1} we get that graph $\Cay(P_n(2),D)$ do not contain a cycles of length~4. Graph $\Cay(P_n(2),D)$ may contain a cycle of length 6 only if $n\geq3$ and it will contain such cycles only if for some integers $i,j,k$ such that $i<j<k\leq n$ the equation (\ref{eq:1}) holds. Obvieusly $[D_kD_jD_iD_kD_iD_j]_i=0$ and $[D_kD_jD_iD_kD_iD_j]_j=0$. Thus we have to prove that $[D_kD_jD_iD_kD_iD_j]_k\neq0$. Let us consider two cases:
\begin{enumerate}

\item $i=1$.

From Lemma \ref{l:c6} the inequality $D_kD_jD_1D_kD_1D_j\neq0$ holds. Moreover let us notice that this case shows that if $n=3$ then graph $\Cay(P_n(2),D)$ do not contain a cycle of length~6.

\item $i\geq2$.

Let us notice that this case is possible only for $n\geq4$.
\begin{align*}
[D_kD_jD_iD_kD_iD_j]_k&=\overline{x_{k-1}}+(\overline{x_{k-1}}/(x_ix_j))(x_i+\overline{x_{i-1}})(x_j+\overline{x_{j-1}})=\\
&=\overline{x_{k-1}}/x_i\neq0.
\end{align*}
\end{enumerate}
Thus inequality $[D_kD_jD_iD_kD_iD_j]_k\neq0$ holds in both cases. Hence the graph $\Cay(P_n(2),D)$ do not contain cycles of length 4 and 6, and so the girth of this graph is equal to 8 for all $n\geq2$.
\end{proof}

\bigskip

\textbf{Proof of Main Theorem.}

\bigskip

The statements 2, 3 and 4 hold by  Prospositions \ref{prop:1}, \ref{prop:3} and \ref{prop:4}. We are left to show statement~1 of the Main Theorem.

As we stated at the beginning of this Section, every cycles of $\Cay(P_n(2),D)$ have an even length and every such graph contains induced subgraph isomorphic to the cyclic graph $C_8$. Thus the girth of such graph is even and not greater then 8.  Example \ref{e:1} and Proposition \ref{prop:4} provides Cayley graphs of $P_n(2)$ on diagonal bases with girths equal to 4 and 8. Proposition \ref{prop:3} provides provides Cayley graphs of $P_n(2)$ on diagonal bases with girth equal to 6.

\section{Non-isomorphic Cayley graphs of $P_n(2)$ on diagonal bases.}

Throughout this Section we assume that $n\geq3$.

Let us recall diagonal bases of group $P_n(2)$ proposed in Example \ref{e:1}. Let $D=\{D_1,\ldots,D_n\}$ be a~diagonal base of group $P_n(2)$ such that $[D_1]_1=1$, $[D_n]_n=\overline{x_{n-1}}$ and for every $i=2,\ldots,n-1$ non-zero coordinates of tableaux $D_i$ are of form
$$[D_i]_i=\overline{x_{i-1}}+a_i,$$ where $a_i\in\mathbb{Z}_2$. From now on we will call such diagonal base of $P_n(2)$ as \textit{a $\delta$-base}.

\smallskip

Every $\delta$-base $D$ of $P_n(2)$ can be uniquely identified with a binary vector $a_D=[a_2,\ldots,a_{n-1}]$, called \textit{the characteristic vector} of a $\delta$-base $D$.

\smallskip

Let us notice that if $a_D=[0,0,\ldots,0]$, then from Proposition \ref{prop:4} the girth of $\Cay(P_n(2),D)$ is equal to 8  and if $a_D\neq[0,0,\ldots,0]$, then from Example \ref{e:1} the girth of $\Cay(P_n(2),D)$ is equal to 4. Thus the Cayley graph $\Cay(P_n(2),D)$, where $a_D=[0,\ldots,0]$ is not isomorphic with any Cayley graph $\Cay(P_n(2),D')$, where $a_{D'}\neq[0,\ldots,0]$. Moreover, the following Theorem holds.

\begin{theorem}\label{nis}
For different $\delta$-bases $D$ and $D'$ of $P_n(2)$ the Cayley graphs $\Cay(P_n(2),D)$ and $\Cay(P_n(2),D')$ are not isomorphic.
\end{theorem}

\begin{proof}
Let $D=\{D_1,\ldots,D_n\}$ and $D'=\{D_1',\ldots,D_n'\}$ be different $\delta$-bases of $P_n(2)$ with characteristic vectors $a_D=[a_2,\ldots,a_{n-1}]$ and $a_{D'}=[a_2',\ldots,a_{n-1}']$ respectively.

From Proposition \ref{prop:1} we get that if $a_j=0$ then $D_j$ do not commute with any $D_m$ for $m>j$, and if $a_j=1$ then $D_j$ commutes with every $D_m$ for $m>j$. Let us recall that $D_1$ do not commute with any other elements of $D$. Thus the number of pairs of commuting elements of $\delta$-base $D$ is equal to \begin{equation}\label{e:2}\displaystyle \sum\limits_{i=2}^{n-1}a_i(n-i).
\end{equation}
Further we denote the number of pairs of commuting elements of $\delta$-base $D$ by $c_D$.

Every tableau $f\in P_n(2)$ is a vertex of the Cayley graph $\Cay(P_n(2),D)$. Let us notice that the~vertex~$f$ belongs exactly to $c_D$ different cycles of length 4 (every pair of commuting generators $D_\alpha,\,D_\beta$ gives an unique cycle of length 4 of form $f\leftrightarrow fD_\alpha\leftrightarrow fD_\alpha D_\beta\leftrightarrow fD_\beta\leftrightarrow f$). Thus if $c_D\neq c_{D'}$, then Cayley graphs $\Cay(P_n(2),D)$ and $\Cay(P_n(2),D')$ are not isomorphic.

\smallskip

Now let us investigate the case $c_D=c_{D'}$.

Firstly, let us determine the form of ball $B_D(f,2)$ of the graph $\Cay(P_n(2),D)$. Let us notice that the vertex set $V(B_D)$ of ball $B_D(f,2)$ is equal to
$$V(B_D)=\left\{g\in P_n(2)\,|\,\exists(i,j\in\{1,\ldots,n\}):\,g=f\,\vee\,g=fD_i\,\vee\,g=fD_iD_j\right\}.$$
For some $i$ $(i=1,\ldots,n)$ let $f'=fD_i$. If element $D_i$ commutes with some other element of $\delta$-base $D$, then edge $ff'$ of graph $B_D(f,2)$ is contained in some cycle of length 4. On the other hand, if $D_i$ does not commute with any other element of $D$ in graph $B_D(f,2)$, then edge $ff'$ is not contained in any cycle and, hence, for every $D_j\neq D_i$ the path of form
$$f\leftrightarrow ff'\leftrightarrow ff'D_j$$
is not contained in any cycle. Thus the structure of induced subgraph $B_D(f,2)$ of graph $\Cay(P_n(2),D)$ is as follows:

Vertex $f$ is contained in $c_D$ number of cycles of length 4, and for every noncommuting element $D_i$ of $D$ vertex $f$ is contained in the path $$f\leftrightarrow fD_i\leftrightarrow fD_iD_j,$$ which is not contained in any cycle.

Examples of induced subgraphs $B_D(f,2)$ of $\Cay(P_5(2),D)$ are presented in Figure~\ref{fig1}.

\smallskip

Let us notice that the structure of $B_D(f,2)$ does not depend on the vertex $f$, so for any $g\in P_n(2)$ graph $B_D(g,2)$ is isomorphic to $B_D(f,2)$. Hence if graphs $B_D(f,2)$ and $B_{D'}(f,2)$ are not isomorphic, then also graphs $\Cay(P_n(2),D)$ and $\Cay(P_n(2),D')$ are not isomorphic.

\smallskip

We assumed that $c_D=c_D'$ and that bases $D$ and $D'$ are different. Thus vectors $a_D$ and $a_{D'}$ are also different. Let $k$ be the least integer such that $a_k\neq a_k'$. We may assume that $a_k=1$ and $a_k'=0$. Thus the number of elements of $D$ which commutes with $D_k$ is equal to $$n-k+\sum\limits_{i=2}^{k-1}a_i.$$ Let us denote that number by $\theta$. Let $\Theta$ be the number of generators $D_i$, where $i<k$,  which commute with exactly $\theta$ generators from $D$. Thus the number of all generators of $D$ which commute with exactly $\theta$ generators is not less then $\Theta+1$. On the other hand, from the fact that for all $i\leq k$ equality $a_i=a_i'$ holds, the number of generators of $D'$ which commutes with exactly $\theta$ other generators from $D'$ is equal to $\Theta$ (notice that there is no generator $D_s'$ for $s>k$, which commute with exactly $\theta$ other generators). Thus the number of edges of the form $f\leftrightarrow fD_i$ which are contained in exactly $\theta$ cycles of length 4 in graph $B_D(f,2)$ is not equal to the number of edges of the form $f\leftrightarrow fD_i'$ which are contained in exactly $\theta$ cycles of length 4 in graph $B_{D'}(f,2)$, and hence these graphs are not isomorphic.

\end{proof}

\begin{figure}[h]
    \centering
    \includegraphics[width=0.8\hsize]{fig1}
    \caption{Graphs $B_D(f,2)$ and $B_{D'}(f,2)$ where $D$ and $D'$ are $\sigma$-bases with characteristic vectors $a_D=[1,0,0]$ and $a_{D'}=[0,1,1]$.}
    \label{fig1}
\end{figure}

Let us notice, that both bases $D$ and $D'$ from Figure \ref{fig1} have exactly three pairs of commuting elements, but graphs $B_D(f,2)$ and $B_{D'}(f,2)$ are not isomorphic.

\bigskip

From Theorem \ref{nis} the number of nonisomorphic Cayley graphs of $P_n(2)$ on the diagonal bases is at least equal to the number of all $\delta$-bases of this group. The number of all $\delta$-bases of $P_n(2)$ is equal to the number of all different characteristic vectors of those bases, so there holds the following

\begin{corollary}
The number of non-isomorphic Cayley graphs of $P_n(2)$ on diagonal bases is not less then $2^{n-2}$.
\end{corollary}


TITLE: is this line of thinking valid for quick solving?
QUESTION [2 upvotes]: I came across a seemingly simple limit when looking for an oblique assymptote of a function:
$(x^2)/(\sqrt{x^2-1})-x$

I need to know what happens here as $x$ approached infinity. The usual method of dividing by the highest degree polynomial doesn't work here, and its become time-consuming relative to the larger problem that this is associated with.
So I just decided to look at things this way:
when $x$ approaches infinity $\sqrt{x^2-1}$ and $\sqrt{x^2}$ are pretty much the same thing, since a measly $-1$ can't have much effect in infinity.
And then I simplified the limit to:
$(x^2/x) - x = 0$
Is this totally wrong? Is it by chance that I got the correct limit?
I'm sure there are great ways of proving this limit rigorously but my question is if I come across such a limit and need to quickly move on can I make these assumptions?
Thanks

REPLY [4 votes]: For the impatient: You can skip almost all of this post, and go to the last $4$ lines.
The informal approach described by the OP almost works, but needs a little tweaking.  We start informally, but end up with a quick formal proof.  I want to tell the story in a roundabout way, in order to begin to convey the thinking.
Imagine $x$ large positive.  It is clear that $\sqrt{x^2-1}$ is smaller, but not much smaller, than $x$, so $\frac{x^2}{\sqrt{x^2-1}}$ is bigger than $x$, and therefore
$$\frac{x^2}{\sqrt{x^2-1}}-x >0.$$
This is not enough to tell us the limit. We need to answer, at least roughly, the question: $\sqrt{x^2-1}$ is how much smaller than $x$?.
Maybe smaller by $u$, where $u$ is small?  How small?  We have
$$\sqrt{x^2-1}=x-u,$$
and therefore
$$x^2-1=x^2-2ux+u^2.$$
or more simply $2ux-u^2=1$.
Since $u$ is small, $2ux$ is very much bigger than $u^2$.  So $2ux\approx 1$, and therefore $u\approx \frac{1}{2x}$.  This is an excellent approximation. (By the way, it is the tangent line approximation.)
So, informally,
$$\frac{x^2}{\sqrt{x^2-1}}-x\approx \frac{x^2}{x-\frac{1}{2x}}-x=\frac{1}{2}\frac{1}{x-\frac{1}{2x}}.$$
Great, looks like we are finished.  It is obvious that the right-hand side is tiny when $x$ is huge.  We even have good control over how tiny.
Unfortunately, for very formal purposes, there is a little problem. For note that if $u=1/(2x)$ then $(x-u)^2$, though a wonderful approximation to $x^2-1$, is unfortunately a little bit bigger than $x^2-1$.
Let's fix that, crudely, because crude is good enough. Instead of $1/(2x)$, we will use $1/x$.
$$\left(x-  \frac{1}{x}\right)^2 =x^2-2+\frac{1}{x^2}.$$  For $x$ large, $x^2-2+\frac{1}{x^2}$ is clearly less than $x^2-1$.  So now we know that
$\frac{x^2}{\sqrt{1-x^2}}<\frac{x^2}{x-\frac{1}{x}}$. That upper bound will do the job.
Proof of the limit result: We now write up a solution, carefully erasing all traces of the thinking that went into it.
It is easy to verify that if $x>1$, then $(x-1/x)^2 <x^2-1$.  It follows that
$$0 <\frac{x^2}{\sqrt{x^2-1}}-x<\frac{x^2}{x-\frac{1}{x}}-x=\frac{1}{x-\frac{1}{x}}.$$
By Squeezing, it follows that
$$\lim_{x\to\infty}\left(\frac{x^2}{\sqrt{x^2-1}}-x\right)=0.$$


text:
\subsection{Skewed lid-driven cavity}
\label{sec:lid}

As a validation case, we consider the skewed lid-driven cavity problem as described by Hesthaven and Ubbiali \cite{Hesthaven2018}.

The problem setup is shown in \reffig{fig:lid:setup}.
The computational domain consists of a parallelogram-shaped cavity. In terms of boundary conditions, no-slip conditions are imposed on the bottom and the side walls, and unit velocity at the top wall.
The pressure is fixed at zero at the lower left corner.
The parameter space for the \gls{ROM} is spanned by three geometrical parameters: horizontal length $\mu_1 \in [1,2]$, wall length $\mu_2 \in [1,2]$ and slanting angle $ \mu_3 \in [\pi/6, 5\pi/6] $.
We are interested in the steady velocity and pressure distributions, so any temperature and time effects in \refeqn{eq:NavierStokes} are neglected.
A Newtonian fluid model is used with unit density. The constant dynamic viscosity is computed depending on the geometry such that Reynolds number is always $400$ according to the dimensionless equation $ Re = {\max\{\mu_1,\mu_2\}} / {\eta} $.

\begin{figure}[!htbp]
\centering
\input{figures/LDC/LDC_setup}

\caption[Geometry and boundary conditions of the skewed lid-driven cavity.]{Parametrized geometry of the domain (left) and boundary conditions (right) of the skewed lid-driven cavity problem.}
\label{fig:lid:setup}
\end{figure}

A regular structured computational mesh with $100 \times 100$ nodes and space-time elements with 8-nodes is used.
Training $\mathbb{P}_{tr}$, validation $\mathbb{P}_{va}$ and test $\mathbb{P}_{te}$ sets of sizes $N_{tr}=100$, $N_{va}=50$ and $N_{te}=50$, are sampled from the parameter-space using randomized \gls{LHS}.
A typical solution is shown in \reffig{fig:lid_examples}.
Two separate reduced bases are constructed -- one for the velocity $\vekt{u}$ and one for the pressure $p$. Both utilize $ L_{\vekt{u}} = L_{p}=20 $ basis vectors.
In each case, the three regression models described in \refsec{sec:Regression models} are trained to approximate the mapping from the standardized parameters to the standardized reduced coefficients $\tilde{\vekt{\pi}}^s : \vekt{\mu}^s \mapsto \vekt{y}^s$. The training set is used to determine the parameters of \gls{RBF} and \gls{ANN} and the hyperparameters of the \gls{GPR}. The validation set is used only for tuning the \gls{ANN}'s hyperparameters. Finally, the test set is used to quantify how the models perform on unseen data.

\def\H{30mm}
\begin{figure}[!htbp]
\begin{center}
\begin{tabular*}{\textwidth}{c @{\extracolsep{\fill}} cc}
  \includegraphics[height=\H]{figures/LDC/T2u.png} &   \includegraphics[height=\H]{figures/LDC/T2v.png} &   \includegraphics[height=\H]{figures/LDC/T2p.png} \\
  \scaleNamedInferno{$-0.37$}{$1.00$}{$u_x$} &
  \scaleNamedInferno{$-0.61$}{$0.36$}{$u_y$} &
  \scaleNamedInferno{$-0.34$}{$1.10$}{$p$}
\end{tabular*}
\end{center}
\caption[An exemplary solution of the skewed lid-driven cavity.]{An exemplary solution of the skewed lid-driven cavity for $\vekt{\mu}=(1.90,\allowbreak 1.50,\allowbreak 1.60)$.}
\label{fig:lid_examples}
\end{figure}

As described in \refsec{sec:ANN}, for the \gls{ANN} we first need to find an appropriate initial learning rate $\alpha_0$ and the number of neurons in both hidden layers $N_\nu$. This is implemented as a grid-search over these two hyperparameters, the results of which are illustrated in \reffig{fig:lid_sens}.
For both parameters, the performance is less sensitive to the size of the \gls{ANN} than to the initial learning rate -- for any given $N_\nu$ an appropriate $\alpha_0$ with the performance close to the optimum can be found. This suggests that perhaps tuning only over $\alpha_0$ is a viable alternative.
Furthermore, we found that very large or very small initial learning rates lead to poor results.
Lastly, larger \glspl{ANN} tend to train better with smaller learning rates.

\begin{figure}[!htbp]
\centering
\includegraphics{figures/LDC/LDC_sens.pdf}
\caption[{ANN} hyperparameter tuning results for the skewed lid-driven cavity.]{\gls{ANN} hyperparameter tuning results for the skewed lid-driven cavity. Depicted are response surfaces of aggregated standardized regression errors on the validation set $\varepsilon_\text{ANN}(\mathbb{P}_{va})$ over the initial learning rate $\alpha_0$ and number of hidden neurons $N_\nu$. The respective best configurations are marked with a cross.}
\label{fig:lid_sens}
\end{figure}

\reffig{fig:lid_errors} compares the best identified \gls{ANN} configurations (as indicated in \reffig{fig:lid_sens}) to \gls{RBF} and \gls{GPR} in terms of the total error on the test set $\varepsilon_\text{POD-REG}(\mathbb{P}_{te})$.
The models rank as one might expect-- more flexible models perform better, i.e., \gls{ANN} outperforms \gls{GPR} which in turn outperforms \gls{RBF}.
The stagnation beyond a certain number of basis vectors $L$ is consistent with observations by other authors \cite{Graessle2019, Hesthaven2018}.

\begin{figure}[!htbp]
\centering
\includegraphics{figures/LDC/LDC_errors.pdf}
\caption[Error analysis of different regression models for skewed lid-driven cavity.]{Error analysis of different regression models for the skewed lid-driven cavity problem. The best identified \gls{ANN} configurations marked in \reffig{fig:lid_sens} are used.}
\label{fig:lid_errors}
\end{figure}

To compare our findings with results published by Hesthaven and Ubbiali, the model performance is plotted again in \reffig{fig:lid_errors_Hesthaven} using the error definitions \cite{Hesthaven2018}:
\begin{equation}
\label{eq:rel_error}
\begin{split}
    \rho_\text{POD} (\mathbb{P}_{te}) :=&
    \frac
    { 1 }
    { N_{te} }
    \sum_{\vekt{\mu} \in \mathbb{P}_{te}}
    \frac
    { || \vekt{s} (\vekt{\mu}) - \vekt{s}_L(\vekt{\mu})) ||_2 }
    { || \vekt{s} (\vekt{\mu}) ||_2 } \ ,
    \\
    \rho_\text{POD-REG} (\mathbb{P}_{te}) :=&
    \frac
    { 1 }
    { N_{te} }
    \sum_{\vekt{\mu} \in \mathbb{P}_{te}}
    \frac
    { || \vekt{s} (\vekt{\mu}) - \tilde{\vekt{s}}_L (\vekt{\mu}) ||_2 }
    { || \vekt{s} (\vekt{\mu}) ||_2 } \ .
\end{split}
\end{equation}

In \cite{Hesthaven2018}, a similar \gls{ANN} is used with $ N_\nu^{\vekt{u}}=20 $ and $N_\nu^p=15$ neurons in both hidden layers, trained with the Levenberg-Marquardt algorithm on $100$ training snapshots.
As shown in \reftab{tab:LDC_hest}, the relative errors are the same order of magnitude as in the reference suggesting our approach and implementation is valid.

We attribute our inferior relative POD-errors to the differences in the computed snapshots and their approximation properties, since we use a different computational mesh and numerical scheme compared to \cite{Hesthaven2018}.

\newcolumntype{L}{>{$}l<{$}}
\def\VET{\rho_\text}
\def\E{{\times}10^}
\begin{table}[H]
\centering
\begin{tabular}{@{}lLLLL@{}}
\toprule
                                            & \multicolumn{2}{L}{\vekt{u}} & \multicolumn{2}{L}{p}      \\
\midrule
                                            & \VET{POD} & \VET{POD-ANN} & \VET{POD} & \VET{POD-ANN}     \\
This work                                   & 0.016     & 0.022         & 0.014     & 0.029             \\
Hesthaven and Ubbiali \cite{Hesthaven2018}  & 0.010     & 0.020         & 0.004     & 0.030             \\
\bottomrule
\end{tabular}
\caption[]{The achieved relative errors are in close agreement with the results reported by Hesthaven and Ubbiali \cite{Hesthaven2018}.
}
\label{tab:LDC_hest}
\end{table}

Note, that the behaviour of the relative error (\reffig{fig:lid_errors_Hesthaven}) is similar to the standardized error (\reffig{fig:lid_errors}).
This is largely due to all quantities of the benchmark problem being normalized to $\mathcal{O}(1)$ per construction.
One noticeable difference, however, is found in the performance of the \gls{ANN} for the pressure. Whereas in the the standardized error, the performance is almost identical to \gls{GPR}, in terms of relative error, \gls{ANN} outperforms \gls{GPR}.
This is likely explained by our aggregation of standardized errors relying upon \gls{RMSE}, which weights outliers more heavily than the mean aggregation used for the relative error. This in turn suggests that the \gls{GPR} deals better with more extreme solutions in pressure than \gls{ANN}.
In \reffig{fig:lid_errors_Hesthaven}, the relative errors for $L=0$ are around $50\%$ simply due to snapshot centering. In contrast, the standardized error in \reffig{fig:lid_errors} is constructed such that naively predicting the mean of snapshots results in $100\%$ error.

\begin{figure}[!htbp]
\centering
\includegraphics{figures/LDC/LDC_errors_Hesthaven.pdf}
\caption[Error analysis of different regression models for skewed lid-driven cavity.]{ \gls{ROM} performance over number of basis functions in terms of the total relative error as defined by Hesthaven and Ubbiali \cite{Hesthaven2018}.}
\label{fig:lid_errors_Hesthaven}
\end{figure}

Lastly, \reffig{fig:lid_streamlines} shows streamlines at the same parameters as Hesthaven and Ubbiali \cite{Hesthaven2018}, who use streamlines to visually uncover minor differences in the solutions. In all projections and predictions (using \gls{POD}-\gls{ANN} with $L=20$) the main circulation zone corresponds closely to the high-fidelity snapshots. Instead, streamlines in areas of low-velocity, in particular recirculation zones are reconstructed only partially even in projections and even less in predictions. Especially in the left-most case, the predicted recirculation zone is very poor. This is also evident in the relative error, which is twice as high as the mean on the test set.
Note, that the projections can be made almost arbitrarily close to the truths by increasing the number of bases $L$, but beyond a certain point this does not benefit the prediction as illustrated in \reffig{fig:lid_errors} and \reffig{fig:lid_errors_Hesthaven}.

\def\H{30mm}
\begin{figure}[!htbp]
\begin{center}
\begin{tabular*}{\textwidth}{m{0em} c @{\extracolsep{\fill}} c @{\extracolsep{\fill}} c}
  \rotatebox{90}{truth}&
  \includegraphics[height=\H, align=c]{figures/LDC/truth1.png} &   \includegraphics[height=\H, align=c]{figures/LDC/truth2.png} &   \includegraphics[height=\H, align=c]{figures/LDC/truth3.png} \\
   & $\vekt{\mu}=(1.12, 1.70, 1.08)$ & $\vekt{\mu}=(1.90, 1.50, 1.60)$ & $\vekt{\mu}=(1.78, 1.99, 2.29)$

 \\ \\
 \rotatebox{90}{projection} &
  \includegraphics[height=\H, align=c]{figures/LDC/proj1.png} &   \includegraphics[height=\H, align=c]{figures/LDC/proj2.png} &   \includegraphics[height=\H, align=c]{figures/LDC/proj3.png} \\
  & $\varepsilon_\text{POD} = 2.3{\times}10^{-2}$ & $\varepsilon_\text{POD} = 3.6{\times}10^{-2}$ & $\varepsilon_\text{POD} = 1.7{\times}10^{-2}$ \\
  & $\rho_\text{POD} = 1.3{\times}10^{-2}$ & $\rho_\text{POD} = 1.4{\times}10^{-3}$ & $\rho_\text{POD} = 7.6{\times}10^{-3}$
  \\ \\
  \rotatebox{90}{prediction} &
  \includegraphics[height=\H, align=c]{figures/LDC/pred1.png} &   \includegraphics[height=\H, align=c]{figures/LDC/pred2.png} &   \includegraphics[height=\H, align=c]{figures/LDC/pred3.png} \\
  & $\varepsilon_\text{POD-ANN} = 6.8{\times}10^{-2}$ & $\varepsilon_\text{POD-ANN} = 3.8{\times}10^{-2}$ & $\varepsilon_\text{POD-ANN} = 5.2{\times}10^{-2}$ \\
  & $\rho_\text{POD-ANN} = 3.8{\times}10^{-2}$ & $\rho_\text{POD-ANN} = 1.5{\times}10^{-2}$ & $\rho_\text{POD-ANN} = 2.3{\times}10^{-2}$ \\ \\
  & & \scaleNamedInferno{$0.0$}{$1.0$}{$||\vekt{u}||$} &
\end{tabular*}
\end{center}
\caption[Streamlines for the skewed lid-driven cavity.]{Streamlines for the skewed lid-driven cavity at three different parameter values. $L=20$ bases and the \gls{ANN} regression model are used. The corresponding errors illustrate that streamlines can uncover minor differences in flows, especially in the stagnating regions.}
\label{fig:lid_streamlines}
\end{figure}

\FloatBarrier

\begin{comment}
  component  sample   eps_pod  eps_podreg   rho_pod  rho_podreg
0         u       0  0.022792    0.067845  0.012836    0.038211
1         u       1  0.036228    0.037724  0.013971    0.014548
2         u       2  0.017306    0.051966  0.007624    0.022894
3         p       0  0.026993    0.049270  0.020632    0.037659
4         p       1  0.024638    0.041604  0.018016    0.030422
5         p       2  0.014315    0.033665  0.010934    0.025714
\end{comment}

config: arxiv


TITLE: Best estimate for random values
QUESTION [5 upvotes]: Due to work related issues I can't discuss the exact question I want to ask, but I thought of a silly little example that conveys the same idea.
Lets say the number of candy that comes in a package is a random variable with mean $\mu$ and a standard deviation $s$, after about 2 months of data gathering we've got about 100000 measurements and a pretty good estimate of $\mu$ and $s$.
Lets say that said candy comes in 5 flavours that are NOT identically distributed (we know the mean and standard deviation for each flavor, lets call them $\mu_1$ through $\mu_5$ and $s_1$ trough $s_5$).
Lets say that next month we will get a new batch (several packages) of candy from our supplier and we would like to estimate the amount of candy we will get for each flavour. Is there a better way than simply assuming that we'll get "around" the mean for each flavour taking into account that the amount of candy we'll get is around $\mu$?
I have access to all the measurements made, so if anything is needed (higher order moments, other relevant data, etc.) I can compute it and update the question as needed.
Cheers and thanks!

REPLY [1 votes]: It depends on your definition of "better."
 You need to define your risk function.  If your risk function is MSE, you can do better than simply using the sample means.  The idea is to use shrinkage, which as the name suggests means to shrink all your $\mu_i$ estimates slightly towards 0.  The amount of shrinkage should be proportional to the sample variance $s^2$ of your data (noisier data calls for more shrinkage) and inversely proportional to the number of data points $n$ that you collect. Note that the James-Stein estimator is only better for $m \ge 3$ flavors.  In general, some form of regularization is always wise in empirical problems.


TITLE: Stone-Čech compactification of partial semigroup
QUESTION [0 upvotes]: Recently, I have read about partial semigroup, where binary composition of two elements isn't guaranteed always. I read it in Hindman Strauss's book from where i get the idea of weak ring and already discussed my confusion here. In this book, there is not any guarantee whether the Stone-Čech compactification of a partial semigroup is a semigroup. Thus they have taken a subsemigroup of it and proved various results. My question is, if $(S,+)$ is a commutative partial semigroup then is $(\beta S,+)$ a partial semigroup or not? Where $+$ on $\beta S$ induced from $+$ on $S$.

REPLY [1 votes]: I think ($\beta {S}$,.) is partial semigroup, atleast if S is commutative, defined as,
p.q is defined if p,q both in $\delta {S}$ or at least one of them is in $\delta {S}$ and it is undefined otherwise, i.e. if both are not in $\delta {S}$.
Now for,
p $\cdot$ (q $\cdot$ r)=(p $\cdot$ q)$\cdot$r.
If in one side is defined for suppose the left one, the otherside should be defined.
You can check this associativity relation of partial semigroup by the condition given at first.


text:
\begin{document}

\title{Multivariate extensions\\of the\\Golden-Thompson inequality}
\author{Frank Hansen}
\date{June 22, 2014}

\maketitle

\begin{abstract} We study concave trace functions of several operator variables and formulate and prove multivariate generalisations of the Golden-Thompson inequality. The obtained results imply that certain functionals in quantum statistical mechanics have bounds of the same form as they appear in classical physics.\\[2ex]
{\bf MSC2010} classification: 47A63.\\[0.5ex]
{\bf{Key words and phrases:}}  Golden Thompson's inequality; multivariate trace inequality; concave trace function.

\end{abstract}

\section{Introduction}

The Golden-Thompson inequality, which is of importance in statistical mechanics and in the theory of random matrices, states that
\[
\tr e^{L+B}\le \tr e^L e^B
\]
for arbitrary self-adjoint matrices $ L $ and $ B. $ It is known that there is no direct extension of this inequality to more operator variables, and there is an extensive literature investigating these matters, cf. \cite{kn:hiai:1993, kn:ando:1994:2, kn:forrester:2014} and the references therein.

We prove, among other statements, the following extension of the Golden-Thompson inequality. Consider $ n\times m $ matrices  $ H_1,\dots,H_k $ with
\[
H_1^*H_1+\cdots+H_k^*H_k= 1_n\,.
\]
Then the inequality
\begin{equation}\label{Main result}
\tr\exp\Bigl(L+\sum_{i=1}^k H^*_i B_i H_i\Bigr)\le\tr\exp\bigl(L) \sum_{i=1}^k H_i^* (\exp B_i) H_i
\end{equation}
is valid for arbitrary self-adjoint $ n\times n $ matrices $ L $ and $ B_1,\dots, B_k\,. $ This is, for $ n=m, $ the same bound as obtained when all the matrices commute. We are thus allowed to estimate partition functions or the Helmhotz function in quantum statistical mechanics and obtain bounds on the same form as they appear in classical physics.

We obtain, as a simple special case, the inequality
\begin{equation}\label{inequality on simpel form}
\tr \exp\bigl(L+{\textstyle\frac{1}{2}}A+{\textstyle\frac{1}{2}}B\bigr)\le\tr (\exp L)\bigl(\textstyle{\frac{1}{2}}\exp A+\textstyle{\frac{1}{2}} \exp B\bigr)
\end{equation}
valid for arbitrary self-adjoint matrices $ L, $ $ A $ and $ B. $ Notice that (\ref{inequality on simpel form}) reduces to the Golden Thompson inequality for $ A=B $ and to convexity under the trace of the exponential function for $ L=0. $ The inequality may thus be considered as an interpolation inequality between Golden-Thompson's inequality and Jensen's inequality. However, we cannot derive  (\ref{inequality on simpel form}) from these special cases. If we first apply Golden-Thompson's inequality then we obtain
\[
\tr \exp\bigl(L+{\textstyle\frac{1}{2}}A+{\textstyle\frac{1}{2}}B\bigr)\le\tr (\exp L)\exp\bigl(\textstyle{\frac{1}{2}}A+\textstyle{\frac{1}{2}} B\bigr),
\]
but this is insufficient to obtain (\ref{inequality on simpel form}) since  $ L $ is arbitrary and the exponential function is not operator convex.

\section{Preliminaries}

The following lemma is both well-known and very useful. We include the proof for the benefit of the reader.

\begin{lemma}\label{differential inequality}
Let $ \varphi\colon\mathcal D\to\mathcal A_\text{sa} $ be a map defined in a convex cone $ \mathcal D\subseteq X $ of a Banach space $ X $ with values in the self-adjoint part of a $ C^* $-algebra $ \mathcal A. $ If $ \varphi $  is Fréchet differentiable, convex and positively homogeneous then
\[
d\varphi(x)h\le\varphi(h)\qquad x,h\in\mathcal D,
\]
where $ \fd{}\varphi(x) $ denotes the Fréchet differential of $ \varphi(x). $
\end{lemma}

\begin{proof}
Since
\[
\begin{array}{rl}
\varphi(x+th)&=\displaystyle (1+t)\varphi\Bigl(\frac{1}{1+t}x+\frac{t}{1+t}h\Bigr)\\[2ex]
&\displaystyle\le (1+t)\Bigl(\frac{1}{1+t}\varphi(x)+\frac{t}{1+t}\varphi(h)\Bigr)\\[2.5ex]
&=\varphi(x)+t\varphi(h)
\end{array}
\]
for $ 0\le t\le 1, $ we obtain
\[
\frac{\varphi(x+th)-\varphi(x)}{t}\le \varphi(h)\qquad 0<t\le 1
\]
and thus $ \fd{}\varphi(x)h\le\varphi(h). $
\end{proof}

We refer to the monograph \cite{kn:flett:1980} for a general account of Fréchet differentiable mappings between Banach spaces.

The logarithm is operator monotone with Lebesgue measure as representing measure, thus
\[
\log x=\int_0^\infty\left(\frac{1}{t+1}-\frac{1}{x+t}\right)\,dt\qquad x>0.
\]
Since
\[
x^{1/2}(x+h)^{-1}x^{1/2}=(1+x^{-1/2}hx^{-1/2})^{-1}
=1-x^{-1/2}hx^{-1/2}+o(h),
\]
we derive that $ \fd{} x^{-1}h=-x^{-1}hx^{-1}. $ Notice that $ h $ may be arbitrary as we are not using the functional calculus. Consequently
\[
\fd{}\log(x)h=\displaystyle\int_0^\infty (x+t)^{-1}h(x+t)^{-1}\,dt.
\]
We have thus obtained the following integral expression
\begin{equation}\label{Q(x,h)}
Q(x,h)=\tr h^*\,\fd{}\log(x)h=\tr\int_0^\infty h^* (x+t)^{-1}h(x+t)^{-1}\,dt.
\end{equation}
It follows from the integral expression that $ Q(x,h) $ is positively homogeneous in $ (x,h). $ Lieb proved that it is a convex function in two variables \cite[Theorem 3]{kn:lieb:1973:1}. But this is a reflection of a quite general result. Zhang and the author recently proved \cite{kn:hansen:2014:3} that for a strictly increasing continuously differentiable function $ f\colon(0,\infty)\to\mathbf R $ the form
\[
(x,h)\to\tr h^*\fd{}f(x)h\qquad x>0
\]
is convex if and only if the derivative of $ f $ is operator convex and numerically decreasing.

We shall now use
Lemma~\ref{differential inequality}. Notice that $ Q(x,h) $ is defined in the cone $ \mathcal D=B(H)_+\times B(H), $ where $ H $ is a finite dimensional Hilbert space. Thus
\begin{equation}\label{inequality for dQ}
\fd{}Q(x,h)(y,k)\le Q(y,k)
\end{equation}
for positive definite $ x,y $ and arbitrary $ h,k. $

We end this section by giving a new result for the form $ Q $ that will prove crucial in the rest of the paper.

\begin{proposition}\label{Q-form and a contraction}
Let $ X $ be an invertible contraction. Then
\[
Q(XAX^*,B)\le Q(A,X^{-1}B(X^*)^{-1})
\]
for positive definite $ A $ and arbitrary $ B. $
\end{proposition}

\begin{proof}
We use the integral representation of the form $ Q $ and obtain
\[
Q(XAX^*,B)=\tr\int_0^\infty B^* (XAX^*+t)^{-1}B(XAX^*+t)^{-1}\,dt.
\]
Since $ X $ is a contraction we derive the inequality
\[
\frac{1}{XAX^*+t}\le\frac{1}{X(A+t)X^*}=(X^*)^{-1}(A+t)^{-1}X^{-1}.
\]
Under the trace this inequality implies
\[
\begin{array}{rl}
Q(XAX^*,B)&\le\displaystyle \tr\int_0^\infty B^* (X^*)^{-1}(A+t)^{-1}X^{-1} B (X^*)^{-1}(A+t)^{-1}X^{-1}\,dt\\[3ex]
&=Q(A,X^{-1}B(X^*)^{-1})
\end{array}
\]
which is the desired result.
\end{proof}

\section{Concave trace functions}

\begin{theorem}\label{Main concavity theorem} Let $ H $ be a contraction. Then the trace function
\[
\varphi(A)=\tr\exp\bigl(H^*(\log A) H\bigr)
\]
is concave in positive definite matrices.
\end{theorem}

\begin{proof} We may without loss of generality assume that $ H $ is invertible. We calculate the first Fréchet differential
\[
\begin{array}{rl}
\fd{} \varphi(A)B &=\tr \fd{}\exp\bigl(H^*(\log A) H \bigr) (H^*(\fd{}\log (A)B) H)\\[1.5ex]
&=\tr \exp\bigl(H^*(\log A) H \bigr) (H^*(\fd{}\log (A)B) H),
\end{array}
\]
where we used the identity $ \tr\fd{}f(A)B=\tr f'(A)B $ valid for differentiable functions. We then
consider the following functions of the single operator variable $ A. $
\[
\begin{array}{rl}
 C&=H^*(\log A) H \\[1.5ex]
 D&=H^*(\fd{}\log(A)B) H=\fd{}_A(H^*(\log A)H)B=\fd{}_A(C)B \\[1.5ex]
 E&=H\exp(C) H^* = H\exp\bigl(H^*(\log A)H\bigr) H^* \\[1.5ex]
 G&=H \fd{}\exp(C)(D) H^* =\fd{}_C(H\exp(C)H^*)D=\fd{}_C(E)D.
 \end{array}
 \]
For clarity,  we use the notation $ \fd{}_A $ to indicate Fréchet differentiation with respect to $ A $ of compound expressions.
We proceed to calculate the second Fréchet differential
\[
\begin{array}{l}
\sfd{}\varphi(A)(B,B)=\fd{}_A(\fd{}\varphi(A)B)B=\fd{}_A (\tr\exp(C)D)B\\[1.5ex]
=\tr \fd{}\exp (C)( D)D +\tr \exp (C) H^*\sfd{}\log (A)(B,B)H \\[1.5ex]
=\tr \fd{}\exp (C)( D)D +\tr E\, \sfd{}\log(A)(B,B).
\end{array}
\]
We recall \cite{kn:flett:1980} that $ \varphi $ is concave if and only if $ \sfd{}\varphi(A)(B,B)\le 0 $ for positive definite $ A $ and self-adjoint $ B. $
To evaluate the second term we apply the chain rule to the form $ Q(A,B) $ and obtain
\[
\begin{array}{rl}
\fd{}Q(A,B)(a,b)&=\fd{}_1Q(A,B)a+\fd{}_2Q(A,B)b\\[1.5ex]
&=\tr B \sfd{}\log(A)(B,a)+\tr b \fd{}\log(A)B+\tr  B \fd{}\log(A) b
\end{array}
\]
for positive definite $ A,a $ and self-adjoint $ B,b. $ The integral representation in (\ref{Q(x,h)}) implies
$ \tr B \fd{}\log(A)b=\tr b \fd{}\log(A)B, $ and we therefore obtain
\[
\fd{}Q(A,B)(a,b)=\tr B \sfd{}\log(A)(B,a)+2\tr b \fd{}\log(A)B.
\]
By using (\ref{inequality for dQ}) we now obtain the inequality
\[
\begin{array}{rl}
\tr a \sfd{}\log(A)(B,B)&=\tr B \sfd{}\log(A)(B,a)\\[1.5ex]
&=\fd{}Q(A,B)(a,b)-2\tr b \fd{}\log(A)B\\[1.5ex]
&\le Q(a,b)-2\tr b \fd{}\log(A)B
\end{array}
\]
for positive definite $ A, a $ and self-adjoint $ B,b. $
Since $ E $ is positive definite we may put $ a=E $ and thus obtain
\[
\begin{array}{rl}
\sfd{}\varphi(A)(B,B)&=\tr \fd{}\exp (C)( D)D+\tr E\, \sfd{}\log(A)(B,B)\\[1.5ex]
&\le  \tr \fd{}\exp (C)( D)D+Q(E,b)-2\tr b \fd{}\log(A)B.
\end{array}
\]
By setting $ b=G $ we then obtain
\[
\sfd{}\varphi(A)(B,B)\le  \tr \fd{}\exp (C)( D)D+ Q(E,G) -2\tr G \fd{}\log(A)B
\]
for positive definite $ A $ and self-adjoint $ B. $ But since
\[
\begin{array}{rl}
\tr G \fd{}\log(A)B&=\tr H \fd{}\exp(C)(D) H^* \fd{}\log(A)B\\[1.5ex]
&=\tr H^*(\fd{}\log(A)B)H \fd{}\exp(C)D \\[1.5ex]
&=\tr \fd{}(H^*(\log A) H)B \fd{}\exp(C)D\\[1.5ex]
&=\tr(\fd{}(C)B)  \fd{}\exp(C)D\\[1.5ex]
&=\tr D \fd{}\exp(C)D,
\end{array}
\]
we obtain
\[
\sfd{}\varphi(A)(B,B)\le Q(E,G) - \tr D \fd{}\exp(C)D.
\]
We now apply Proposition~\ref{Q-form and a contraction} and obtain
\[
\begin{array}{rl}
Q(E,G)&=Q(H\exp(C)H^*,G)\\[1.5ex]
&\le Q(\exp C, H^{-1}G(H^*)^{-1})\\[1.5ex]
&=Q(\exp C, \fd{}\exp(C)(D))\\[1.5ex]
&=\tr \fd{}\exp(C)(D) \fd{}\log(\exp C)\fd{}\exp(C)(D).
\end{array}
\]
However, since the inverse of the linear map $ h\to\fd{}\exp(x)h $ is given by
\[
\fd{}\exp(x)^{-1}=\fd{}\log(\exp x),
\]
we realise that
\[
\fd{}\log(\exp C)\fd{}\exp(C)(D)=\fd{}\exp(C)^{-1}(\fd{}\exp(C) D)=D.
\]
Therefore,
\[
Q(E,G)\le \tr D \fd{}\exp(C) D
\]
and thus $ \sfd{}\varphi(A)(B,B)\le 0 $ for positive definite $ A $ and self-adjoint $ B. $ This shows that $ \varphi $ is concave.
\end{proof}

\begin{corollary}\label{Concavity corollary 1}
Consider $ n\times m $ matrices  $ H_1,\dots,H_k $ with
\[
H_1^*H_1+\cdots+H_k^*H_k\le 1_n
\]
where $ 1_n $ denotes the $ n\times n $ unit matrix. Then the trace function
\[
\varphi(A_1,\dots,A_k)=\tr\exp\bigl(H^*_1 (\log A_1) H_1+\cdots+ H^*_k (\log A_k) H_k\bigr)
\]
is concave in $ k $-tuples of positive definite $ n\times n $ matrices.
\end{corollary}

\begin{proof}
We set
\[
A=\begin{pmatrix}
     A_1     & 0     & \cdots   & 0\\
     0         & A_2 &             & 0\\
     \vdots &         & \ddots  & \vdots\\
     0        & 0       & \dots    & A_k
     \end{pmatrix}\qquad\text{and}\quad
H=\begin{pmatrix}
     H_1    & 0        & \cdots & 0\\
     H_2    & 0        & \cdots & 0\\
     \vdots & \vdots & \ddots & \vdots\\
     H_k    & 0         & \cdots & 0
     \end{pmatrix}
\]
with zero matrices of suitable orders inserted and notice that $ H $ is a contraction. Furthermore,
\[
H^*( \log A) H=\begin{pmatrix}
     \sum_{i=1}^k H_i^* (\log A_i) H_i    & 0       & \cdots   & 0\\
     0                                                     & 0        &  \cdots  & 0\\
     \vdots                                             & \vdots & \ddots   & \vdots\\
     0                                                     & 0        & \dots     & 0
     \end{pmatrix}.
\]
Thus
\[
\tr\exp\bigl(H^*(\log A) H\bigr)=\tr\exp\Bigl(\sum_{i=1}^k H^*_i(\log A_i) H_i\Bigr) +(k-1)n
\]
and the statement follows from Theorem~\ref{Main concavity theorem}.
\end{proof}

\begin{corollary}\label{Concavity corollary 2}
Consider $ n\times m $ matrices  $ H_1,\dots,H_k $ with
\[
H_1^*H_1+\cdots+H_k^*H_k\le 1_n
\]
and a self-adjoint $ n\times n $ matrix $ L. $ Then the trace function
\[
\varphi(A_1,\dots,A_k)=\tr\exp\Bigl(L+\sum_{i=1}^k H^*_i (\log A_i) H_i\Bigr)
\]
is concave in $ k $-tuples of positive definite $ n\times n $ matrices.
\end{corollary}

\begin{proof}
By appealing to continuity we may without loss of generality assume
\[
H_1^*H_1+\cdots+H_k^*H_k< 1_n
\]
and set $ H_{k+1}=\bigl(1_n-(H_1^*H_1+\cdots+H_k^*H_k)\bigr)^{1/2}. $ Then $ H_{k+1} $ is positive definite and since
\[
H_1^*H_1+\cdots+H_k^*H_k+H^2_{k+1}= 1_n
\]
we deduce from Corollary~\ref{Concavity corollary 1} that the trace function
\[
\begin{array}{l}
\varphi(A_1,\dots,A_k,A_{k+1})\\[1.5ex]
=\tr\exp\bigl(H^*_1 (\log A_1) H_1+\cdots+ H^*_k (\log A_k) H_k+H_{k+1} (\log A_{k+1})H_{k+1}\bigr)
\end{array}
\]
is concave in positive definite matrices. We keep $ A_{k+1} $ constant by setting
\[
A_{k+1}=\exp\bigl(H^{-1}_{k+1} L H_{k+1}^{-1}\bigr)
\]
and the statement now follows.
\end{proof}

\begin{remark}
Corollary~\ref{Concavity corollary 2} contains two celebrated theorems of Lieb. If we set $ k=1 $ and $ H=1 $ then the trace function
\[
\varphi(A)=\tr\exp(L+\log A)
\]
is concave in positive definite matrices, cf. \cite[Theorem 6]{kn:lieb:1973:1}. If $ H_1,\dots,H_k $ are chosen as square roots of positive numbers times the identity matrix then we obtain that the trace function
\[
\varphi(A_1,\dots,A_k)=\tr\exp(L+p_1 \log A_1+\cdots+p_k \log A_k),
\]
defined in positive definite matrices, is concave, where $ p_1,\dots,p_k $ are non-negative numbers with $ p_1+\cdots+p_k\le 1, $ cf. \cite[Corollary 6.1 (1)]{kn:lieb:1973:1}.
\end{remark}

\begin{corollary}
Let $ L $ be a fixed self-adjoint matrix, and let $ A_1,\dots,A_k $ be random self-adjoint matrices. Then the inequality
\[
\mean\tr\exp\Bigl(L+\sum_{i=1}^k H_i^* A_i H_i\Bigr)\le \tr\exp\Bigl(L+\sum_{i=1}^k H_i^*(\log\mean e^{A_i}) H_i\Bigr)
\]
holds
for fixed matrices $ H_1,\dots,H_k $ with $ H_1^*H_1+\cdots+H_k^*H_k\le 1. $
\end{corollary}

The result follows directly from Corollary~\ref{Concavity corollary 2} by applying Jensen's inequality, cf. also \cite[Corollary 3.3]{kn:Tropp:2012}. A simple consequence is that
\[
\mean\tr\exp\Bigl(L+\frac{A_1+\cdots+A_k}{k}\Bigr)\le \tr\exp\Bigl(L+\frac{\log\mean \displaystyle e^{A_1}+\cdots+ \log\mean  e^{A_k}}{k}\Bigr)
\]
for a fixed self-adjoint matrix $ L $ and random self-adjoint matrices $ A_1,\dots,A_k. $

\section{Multivariate trace inequalities}

\begin{lemma}\label{Lemma to prove Golden-Thomson type inequalities}
Consider $ n\times m $ matrices  $ H_1,\dots,H_k $ with
\[
H_1^*H_1+\cdots+H_k^*H_k= 1_n
\]
and a self-adjoint $ n\times n $ matrix $ L. $ Then we have the inequality
\[
\begin{array}{l}
\displaystyle\tr\exp\Bigl(L+\sum_{j=1}^k H^*_j (\log B_j) H_j\Bigr)\\[1.5ex]
\le\displaystyle\tr\exp\Bigl(L+\sum_{j=1}^k H_j^*(\log A_j)H_j\Bigr)\sum_{i=1}^k H_i^*(\fd{}\log(A_i)B_i) H_i
\end{array}
\]
for positive definite $ n\times n $ matrices $ A_1,\dots,A_k $ and $ B_1,\dots,B_k\,. $
\end{lemma}

\begin{proof}
Since the trace function
\[
\varphi(A_1,\dots,A_k)=\tr\exp\Bigl(L+\sum_{j=1}^k H_j^*(\log A_j)H_j \Bigr)
\]
is concave and (positively) homogeneous, we may apply Lemma~\ref{differential inequality} and obtain the inequality
\[
d\varphi(A_1,\dots,A_k)(B_1,\dots,B_k)\ge\varphi(B_1,\dots,B_k).
\]
By applying the chain rule for Fréchet differentials we then derive
\[
\begin{array}{l}
\varphi(B_1,\dots,B_k)\le\displaystyle\ \sum_{i=1}^k d_i\varphi(A_1,\dots,A_k)B_i\\[1.5ex]
=\displaystyle\sum_{i=1}^k\tr\fd{}\exp\Bigl(L+\sum_{j=1}^k H_j^*(\log A_j)H_j \Bigr)H_i^*(\fd{}\log(A_i)B_i) H_i\\[2.5ex]
=\displaystyle\sum_{i=1}^k\tr\exp\Bigl(L+\sum_{j=1}^k H_j^*(\log A_j)H_j \Bigr)H_i^*(\fd{}\log(A_i)B_i) H_i
\end{array}
\]
and the statement follows.
\end{proof}

\begin{theorem}\label{My generalisation of the Golden-Thompson inequality}
Consider $ n\times m $ matrices  $ H_1,\dots,H_k $ with
\[
H_1^*H_1+\cdots+H_k^*H_k= 1_n\,.
\]
Then we have the inequality
\[
\tr\exp\Bigl(L+\sum_{i=1}^k H^*_i B_i H_i \Bigr)\le\tr\exp\bigl(L) \sum_{i=1}^k H_i^* (\exp B_i) H_i
\]
for arbitrary self-adjoint $ n\times n $ matrices $ L $ and $ B_1,\dots, B_k\,. $
\end{theorem}

\begin{proof}
Choose in Lemma~\ref{Lemma to prove Golden-Thomson type inequalities} for $ i=1,\dots,k $  the matrix $ A_i $ as the identity matrix. Then the Fréchet differential $ \fd{}\log(A_i)B_i=B_i $ and $ \log A_i=0. $ The result then follows by replacing $ B_i $ with $ \exp B_i $ for $ i=1,\dots,k. $
\end{proof}

The above inequality is a direct generalisation of the Golden-Thompson inequality. Indeed, if we put $ k=1 $ and take $ H_1 $ as the identity matrix then the inequality in Theorem~\ref{My generalisation of the Golden-Thompson inequality} takes the form
\[
\tr e^{L+B}\le \tr e^L e^B,
\]
cf. \cite{kn:golden:1965, kn:thompson:1965, kn:lieb:1973:1}. We may obtain other corollaries of Lemma~\ref{Lemma to prove Golden-Thomson type inequalities} .

\begin{theorem}\label{Generalised Golden-Thompson inequality}
Consider $ n\times m $ matrices  $ H_1,\dots,H_k $ with
\[
H_1^*H_1+\cdots+H_k^*H_k= 1_n\,.
\]
Then we have the inequality
\[
\tr\exp\Bigl(\sum_{i=1}^k H^*_i (\log B_i-\log A_i) H_i \Bigr)\le\sum_{i=1}^k\tr H_i^*(\fd{}\log(A_i)B_i) H_i
\]
for positive definite $ n\times n $ matrices $ A_1,\dots,A_k $ and $ B_1,\dots,B_k\,. $
\end{theorem}

\begin{proof} The result follows by setting
\[
L=-\bigl(H_1^*(\log A_1) H_1+\cdots+H_k^*(\log A_k) H_k\bigr)
\]
in Lemma~\ref{Lemma to prove Golden-Thomson type inequalities}.
\end{proof}

If we in Theorem~\ref{Generalised Golden-Thompson inequality} put $ k=1 $ and take $ H_1 $ as the unit matrix we obtain
\[
\tr\exp(\log B-\log A)\le \tr\fd{}\log(A) B=\tr A^{-1}B
\]
which is the Golden-Thompson inequality.\\[1ex]
Furthermore, if $ A_i $ and $ B_i $ commute for $ i=1,\dots,k $ then
Theorem~\ref{Generalised Golden-Thompson inequality} reduces to the inequality
\[
\tr\exp\Bigl(\sum_{i=1}^k H^*_i (\log B_i-\log A_i) H_i \Bigr)\le\sum_{i=1}^k\tr H_i^* B_i A_i^{-1}  H_i
\]
which is an expression of operator convexity of the exponential function under the trace.

\begin{theorem}\label{Generalised extended Golden-Thompson inequality}
Consider $ n\times m $ matrices  $ H_1,\dots,H_k $ with
\[
H_1^*H_1+\cdots+H_k^*H_k= 1_n\,.
\]
Then we have the inequality
\[
\begin{array}{l}
\displaystyle\tr\exp\Bigl(\sum_{i=1}^k H^*_i (\log B_i+\log C_i-\log A_i) H_i \Bigr)\\[1.5ex]
\le\displaystyle\tr\exp\Bigl(\sum_{i=1}^k H_i^*(\log C_i)H_i \Bigr) \sum_{i=1}^k H_i^*(\fd{}\log(A_i)B_i) H_i
\end{array}
\]
for positive definite $ n\times n $ matrices $ A_1,\dots,A_k, B_1,\dots,B_k $ and $ C_1,\dots,C_k\,. $
\end{theorem}

\begin{proof}
The result follows by setting
\[
L=H_1^*(\log C_1-\log A_1)H_1+\cdots+H_k^*(\log C_k-\log A_k)H_k
\]
in Lemma~\ref{Lemma to prove Golden-Thomson type inequalities}.
\end{proof}

If we in Theorem~\ref{Generalised extended Golden-Thompson inequality} put $ k=1 $ and take $ H_1 $ as the unit matrix we
obtain
\[
\tr\exp(\log B+\log C-\log A)\le \tr C\, d\log(A)B,
\]
which is the extended Golden-Thompson inequality. The extended Golden-Thompson inequality reduces to the Golden-Thompson inequality if $ A $ and $ B $ commute.

{\small


TITLE: In a full binary tree of depth $d$, what is the number of pairs of vertices at distance $t$ from each other?
QUESTION [2 upvotes]: I can come up with a dynamic-programming-type program to compute this number, but I am wondering if a nice closed form formula is known.
By "full" I mean a binary tree where every vertex is within distance $d$ of the root, and the $d$-th level is completely filled with leaves. There are $2^{d+1} - 1$ total nodes.

REPLY [0 votes]: Observe that each interior vertex (other than the root) of a binary tree is the central vertex of three different paths of length two, whereas the root is the central vertex of one such path. Furthermore, there are exactly $2^d-2$ interior vertices (other than the root) in a full binary tree. Writing $p(d,2)$ for the number of paths of length two in a full binary tree of depth $d$:
$$p(d,2)=3(2^d-2)+1=3\cdot 2^d-5.$$
Using a similar direct counting approach for $t=2k$, I have found the following formulae for $p(d,2k)$, the number of pairs of vertices at distance exactly $2k$ in a full binary tree of depth $d$.

if $d<k$, then $p(d,2k)=0$
if $k\le d<2k$, then $p(d,2k)=2^{2k-2}\left(3\cdot 2^{d-k+1}-2(d-k)-5\right)$
if $d\ge 2k$, then $p(d,2k)=2^{2k-2}\left(3\cdot 2^{d-k+1}-2k-3\right)$

These appear to give the correct counts for small values of $d$ and $k$. In particular, for $t=2$ ($k=1$) and $d> 1$, the expression above becomes
$$p(d,2)=2^{2-2}\left(3\cdot 2^{d-1+1}-2-3\right)=3\cdot 2^d-5.$$
If you have any exact counts for larger values of $t$, perhaps you could check the validity of these formulae.


TITLE: Max packing of cars in square parking lot
QUESTION [6 upvotes]: An $n\times n$ square grid represents a parking lot, each of the $n^2$ squares may be occupied by at most one car. However, each car (not on the boundary) must have a clear path to the boundary of the grid, moving only to adjacent squares sharing a side.
What is the maximum number $M(n)$ of cars that can fit in the parking lot?
This was posted recently by @Benenom but for some reason was deleted 3 mins after appearing.
Clearly, $M(n)=n^2$ for $n<3$. For $n=3$ we need at least one vacant square (any non-corner square will do). For $n=4$ we need at least 3 vacant squares (eg a line of three starting from a non-corner boundary square).
At first I thought that the idea used for $n=4$ might work for all $n$. Eg for $n=8$ make vacant the first 7 squares of the third and sixth rows.
$$\begin{matrix}C&C&C&C&C&C&C&C\\
C&C&C&C&C&C&C&C\\
C&.&.&.&.&.&.&.\\
C&C&C&C&C&C&C&C\\
C&C&C&C&C&C&C&C\\
C&.&.&.&.&.&.&.\\
C&C&C&C&C&C&C&C\\
C&C&C&C&C&C&C&C\end{matrix}$$
That gives:
$M(1)=1\\
M(2)=4\\
M(3)=9-1=8\\
M(4)=16-3=13\\
M(5)=25-4=21\\
M(6)=36-2\cdot5=26\\
M(7)=49-3\cdot6=37\\
M(8)=64-2\cdot7=50$
In general we would get
$M(3n+2)=(3n+2)^2-n(3n+1)=6n^2+11n+4\\
M(3n+1)=(3n+1)^2-3n^2=6n^2+6n+1\\
M(3n)=(3n)^2-n(3n-1)=6n^2+n.$
[the last one for $n>1$]
However, as @RobPratt points out in his answer below, we can do better than that for $M(6)$, getting 36-8=28. Presumably the same is true for all $M(3n)$.
For $3n=6$ we can write the last four rows as:
$$\begin{matrix}C&.&.&.&.&.\\
C&C&.&C&.&C\\
C&C&.&C&C&C\\
C&C&C&C&C&C\end{matrix}$$
In a similar way we could write the last four rows for $3n=9$ as:
$$\begin{matrix}C&.&.&.&.&.&.&.&.\\
C&C&.&C&C&.&C&.&C\\
C&C&.&C&C&.&C&C&C\\
C&C&C&C&C&C&C&C&C\end{matrix}$$
and in general we would get $M(3n)=6n^2+2n$. The other two cases are unchanged: $M(3n+1)=6n^2+6n+1$ and $M(3n+2)=6n^2+11n+4$.
In any case I have not yet got a proof of maximality even for $M(3n+2)$.

REPLY [2 votes]: Not an answer.  Just wanna report that I found another "divide-and-conquer" strategy to get the same answer for side length $m=3n$ cases.  It is based on $4$ "center aisles" forming an offset $+$ like pattern.  This divides the $m \times m$ square into $4$ rectangles, and since $m=3n$, we can arrange each rectangle to have dimensions $(3k+2) \times (3j)$, and the $(3k+2)$ side makes it in a sense easier to deal with.
Here is the $m=12=3n$ example.  The $4$ center aisles split all remaining squares into (1) four cars at the center of the $+$ denoted "b", and (2) four separate $6\times 5$ rectangles, one of which I have highlighted as "a" instead of "c".  The total number of spaces $= 5 \times 8 = 40 = n(3n-2)$, so it achieves the same $M(n)$ as the already found solution.
c c . c c . c c c c c c
c c . c c . c c c c c c
c c . c c . c . . . . .
c c . c c . c c c c c c
c c . c c . c c c c c c
c c c c c b b . . . . .
. . . . . b b a a a a a
c c c c c c . a a . a a
c c c c c c . a a . a a
. . . . . c . a a . a a
c c c c c c . a a . a a
c c c c c c . a a . a a

This also works when $m=3n$ is odd, because there is no need for the four rectangles to be the same dimensions. E.g here is the $m=9=3n$ case.  The number of spaces $=21 = n(3n-2)$, again equaling the already found solution.
c c . c c . c c c
c c . c c . c c c
c c . c c . c . .
c c . c c . c c c
c c . c c . c c c
c c c c c b b . .
. . . . . b b a a
c c c c c c . a a
c c c c c c . a a

I have played around with this "divide-and-conquer" strategy for a bit, with different original side lengths and different splits, but was never able to find a better solution.


TITLE: Verifying whether a quotient ring is indeed a ring.
QUESTION [1 upvotes]: Take $$\frac{\Bbb{R[x]}}{\langle x^2+1\rangle}$$ This is a ring. In this quotient ring, the product of equivalence classes $[a+bx]$ and $[c+dx]$ is another equivalence class, as a ring is closed under multiplication.
$[a+bx]=\{a+bx,a+bx+(x^2+1),a+bx+2(x^2+1),\dots\}$, and $[c+dx]=\{c+dx,c+dx+(x^2+1),c+dx+2(x^2+1),\dots\}$.
Also, we should have $[a+bx][c+dx]=[(ac+bdx^2)+(ad+bc)x]$.
Which two elements in $[a+bx]$ and $[c+dx]$ multiply with each other to give $(ac+bdx^2)+(ad+bc)x+(x^2+1)$, which is a member of $[(ac+bdx^2)+(ad+bc)x]$?
Note: I know that $\{a+bx,a+bx+(x^2+1),a+bx+2(x^2+1),\dots\}\neq[a+bx]$; it is only the inverse of $[a+bx]$. I only write all this for a clear exposition: $[m][n]=[mn]$ only because the inverse images of $[m]$ and $[n]$, under the canonical mapping, multiply together to give the inverse image of $[mn]$.
Thanks!

REPLY [2 votes]: To be honest, if you are trying to show this is indeed a ring, there are indirect methods that are far easier.  For example:
Consider the evaluation homomorphism $ev_i:\mathbb{R}[x] \rightarrow \mathbb{C}$ defined as follows:
$$f(x) \mapsto f(i)$$
This homomorphism is indeed surjective since, given any $(a + bi) \in \mathbb{C}$, simply take the polynomial $f(x) = a + bx$.  Further, $ker(\phi) = \langle x^2 + 1 \rangle$.  Now we apply the isomorphism theorem:
$$\mathbb{R}[x]/ \langle x^2 + 1 \rangle \cong \mathbb{C}$$
So it is certainly a ring, and even a field.


TITLE: What’s the difference between energy in an electromagnetic wave and transmit power?
QUESTION [0 upvotes]: As I understand, Energy of an electromagnetic wave has a direct relationship to frequency. A higher Energy wave is smaller in length at greater frequency. But Transmit Power can be increased without altering the frequency. Transmit Power of a WiFi router can be changed for example; but frequency remains 2.4GHz or 5GHz. Obviously in this example Transmit Power is controlled by a human; energy may or may not be. But what are the fundamental differences between Energy and Transmit Power?

REPLY [3 votes]: Electromagnetic waves are photons, and the energy of a photon is indeed determined by its frequency $f$ according to $E = h \cdot f$. However, you can simply emit more photons to increase signal strength. In classical physics, more photons would mean an electromagnetic wave of larger amplitude.


TITLE: On the geometric Hahn-Banach theorem
QUESTION [7 upvotes]: Let $ X \subset \ R ^ n $ be a closed convex set and
 let $ L $ be a straight line such that $ X \cap L = \emptyset $.
 Does there exist a hyperplane containing
$ L $ that does not intersect $ X $ ?
In the classical Hahn-Banach theorem we require $X$ to be open.

REPLY [11 votes]: Not necessarily: consider a 3-D space, let $L$ be the $x$ axis, and let the convex set be $$X=\bigl\{(x,y,z):z\geqslant (\max\{0,y + e^x\})^2\bigr\}.$$ This is the region above the graph of a convex function; here's a 3-D plot. After projecting on the $yz$ plane, the convex set becomes $$X' = \{(y, z) : y < 0 , \, z \geqslant 0\} \cup \{(y, z) : y \geqslant 0, z > y^2\}.$$ There is no line in the $yz$ plane that contains the origin and does not intersect $X'$, and hence there is no hyperplane that contains the $x$ axis and does not intersect $X$.


TITLE: Do rotational degrees of freedom contribute to temperature?
QUESTION [0 upvotes]: Recently I have come across a mathematical problem where I was said to calculate the temperature increase of certain mol of N2 gas confined in a room.
However, I found that there was only consideration of kinetic energy in the issue of temeperature.
My question is why don't we include rotational DOF in calculating temeperature increase?

REPLY [4 votes]: If you start with a monatomic gas then the only degrees of freedom available are the three translational degrees of freedom. Each of them absorbs $\tfrac{1}{2}kT$ of energy, so the specific heat (at constant volume) is $\tfrac{3}{2}k$ per atom or $\tfrac{3}{2}R$ per mole.
If you move to a diatomic molecule there are two rotational modes as well - only two extra modes because rotation about the axis of the molecule has energy levels too widely spaced to be excited at normal temperatures. Each of those two rotational degrees of freedom will soak up another $\tfrac{1}{2}kT$, giving a specific heat of $\tfrac{5}{2}k$ per molecule or $\tfrac{5}{2}R$ per mole.
But the rotational energy levels are quantised with an energy spacing of $E = 2B, 6B, 12B$ and so on, where $B$ is the rotational constant for the molecule:
$$ B = \frac{\hbar^2}{2\mu d^2} $$
where $\mu$ is the reduced mass and $d$ is the bond length. So these rotational energy levels will only be populated when $kT$ is a lot greater than $B$ - say 10 to 100 times greater. You can look up the rotational constant of nitrogen, or it's easy enough to calculate, and the result is:
$$ B \approx 3.97 \times 10^{-23} \text{J} $$
which is about $3k$. So as long as the temperature is above say $30K$ the rotational modes will be excited and nitrogen will have a specific heat of $\tfrac{5}{2}R$. If you go down to temperatures of $3K$ and below then the specific heat will fall to $\tfrac{3}{2}R$ just like a monatomic gas.
The specific heat of nitrogen at constant volume is 0.743 kJ/(kg.K), and converting this to J/mole.K we get 20.8 J/(mole.K) and this is indeed 2.50R (to three significant figures).
The conformist mentions that the vibrations of the nitrogen molecule will contribute to the specific heat, and indeed they will. However the energy of the first vibrational mode is 2359 cm$^{-1}$, which converted to non-spectrogeek units is $4.7 \times 10^{-20}$ J or about $3400k$. So the vibrational mode isn't going to contribute to the specific heat until the temperature gets above 3400K.

REPLY [0 votes]: N$_2$ is a diatomic molecule and therefore you must and do consider the degree of freedom from rotation. This is why for a diatomic gas, the mean energy is $$ \frac{5}{2} K_B T$$ if the molecule is rigid. These extra degrees of freedom come from rotation. It is also worth pointing out that if the molecule can vibrate along the line joining the two centres, its mean energy is $$\frac{7}{2} K_B T $$. On the other hand, for a monatomic gas like He or Ne, the mean energy is $$\frac{3}{2} K_B T. $$This is an experimentally verified result. The result will vary depending on whether the molecule is made up of the same kind of atom, how many atoms of different kinds and the relative strength of the bonds because all these factors will change the centre of mass of the molecule. The wikipedia page gives a clear explanation to this: https://en.wikipedia.org/wiki/Degrees_of_freedom_(physics_and_chemistry)


TITLE: General formulas for $\cos \left(\sum_{i=1}^{n}\theta_{i}\right)$ and $\sin \left(\sum_{i=1}^{n}\theta_{i}\right)$?
QUESTION [0 upvotes]: Can someone tell me the general formula for the cosine and sine of a sum of more than two angles?
$$\cos \left(\sum_{i=1}^{n}\theta_{i}\right)=? \qquad \sin \left(\sum_{i=1}^{n}\theta_{i}\right)=?$$
I can't find it anywhere!

REPLY [0 votes]: According to Wikipedia,
$$
\cos\Bigl(\sum_{i=1}^{n}\theta_{i}\Bigr)=\sum_{\substack{0\le k\le n\\k\text{ even}}}(-1)^{k/2}\sum_{\substack{A\subset\{1,\dots,n\}\\|A|=k}}\Bigl(\prod_{i\in A}\sin\theta_i\prod_{i\notin A}\cos\theta_i\Bigr)
$$


TITLE: finding gradient of an eingenline
QUESTION [0 upvotes]: Trying to find the gradient of the eigenline that is ofcourse finding the eigenvlaue, but stuck here
QUESTION:

The matrix A has two eigenvalues h and k, where h > k.  To 2 decimal places, what is the gradient of the eigenline that corresponds to eigenvalue h?
My Working:

REPLY [0 votes]: From the matrix equation, this system is row-equivalent to the system
$$\left[\begin{array}{cc|c}-3.526&-18&0\\0&0&0\end{array}\right],$$
which is a consistent linear system. Performing back substitution gives
$$-3.526x+18y=0,$$
which is the standard form for the equation of a line (equivalent to $y=\frac{3.526}{18}x$).


TITLE: integration using partial fraction with repeating denominator
QUESTION [1 upvotes]: So i need to integrate this $1/[(x^3)(x-1)]$, that means it could be decomposed into:
$$A/x + B/x^2 + C/x^3 + D(x-1)$$
Furthermore the resulting equation would then be:

$1 = A(x^2)(x-1) + Bx(x-1) + C(x-1) + Dx^3$
if i let $x=0$ then $C=-1$
if i let $x=1$ then $D=1$

But i don't know how to get the values for A and B can somebody help me?

REPLY [2 votes]: Here's an easy way to do it:
$$\frac{1}{x^3(x-1)}=\frac{Ax^2+Bx+C}{x^3}+\frac{D}{x-1}$$
I chose to start at $x^2$ for the first one since the degree of the denominator is $3$, and on the other $x^0$ because the denominator has degree $1$ (so go all the way down starting with $x^{\text{denominator degree}-1}$).
Combine the two fractions into a fraction with the original denominator:
$$\frac{(Ax^2+Bx+C)(x-1)+D(x^3)}{x^3(x-1)}$$
And recall that the numerator was equal to $1$:
$$(Ax^2+Bx+C)(x-1)+D(x^3)=1$$
Distribute:
$$Ax^3+Bx^2+Cx-Ax^2-Bx-C+Dx^3=1$$
Combine like terms:
$$(A+D)x^3+(B-A)x^2+(C-B)x-C=1$$
And guess what..?
$$(A+D)x^3+(B-A)x^2+(C-B)x-C=0x^3+0x^3+0x+1$$
Hence we have:
$$\begin{cases}A+D=0\\B-A=0\\C-B=0\\-C=1\end{cases}$$
Which gives you:
$$\begin{cases}A=-1\\B=-1\\C=-1\\D=1\end{cases}$$
And so you have:
$$\frac{-x^2-x-1}{x^3}+\frac1{x-1}=-\frac1{x}-\frac1{x^2}-\frac1{x^3}+\frac1{x-1}$$
Which is easy to integrate:
$$\begin{align}&\int\left(-\frac1{x}-\frac1{x^2}-\frac1{x^3}+\frac1{x-1}\right)dx\\=&-\ln x+\frac1{x}+\frac1{2x^2}+\ln(x-1)\end{align}$$


TITLE: If $\mathscr A$ has all products and equalizers, then it has all limits
QUESTION [2 upvotes]: This question is about part (a) of this proposition:

Here is a plan of the proof.

Here's what the picture looks like, from what I understand:

But I don't understand what the condition $s\circ p=t\circ p$ means. I guess this means componentwise equality: $s_u\circ p_u=t_u\circ p_u $ for all $u$, but what is $p_u$? $L$ is not a product, and so $p_u$ cannot be a projection.
I'm just trying to prove first that $Du\circ p_I=p_J$ for all $u: I\to J$, and it seems I need to use $s\circ p=t\circ p$ to that end, which is unclear how to do.

REPLY [2 votes]: This is the second part of the proof (the first part is Rushy's answer).
We need to show that if $(L', f_I:L'\to D(I))_{I\in\mathbf{I}}$ is another cone, then there exists a unique arrow $\alpha: L'\to L$ such that $p_J\circ\alpha=f_J$ for all $J\in\mathbf I$.
So let $(L', f_I:L'\to D(I))_{I\in\mathbf{I}}$ be a cone. By the universal property of the product, there exists a unique arrow $f: L'\to \prod_{I\in\mathbf I} D(I)$ such that $pr_J\circ f=f_I$. (In other words, the $I$th component of $f$ is $f_I$.)
Note that $s\circ f=t\circ f$. Indeed,
$$s\circ f=t\circ f \\ \iff \pi_u\circ s\circ f=\pi_u\circ t \circ f \text{ (see Rushy's comment under the answer)}\\ \iff s_u\circ f=t_u\circ f \text{ (definition of the }u\text{th component of $s$ and $t$)} \\ \iff Du\circ pr_J\circ f =pr_K\circ f \text{ (definitions of $t_u$ and $s_u$)} \\ \iff Du\circ f_J=f_K \text{ (by the above)}$$
The equality in the last row holds because $(L', f_I:L'\to D(I))_{I\in\mathbf{I}}$ is a cone. Thus $s\circ f=t\circ f$.
Since $(L,p:L\to \prod_{I\in\mathbf I} D(I))$ is an equalizer of $s$ and $t$, there is a unique $\alpha: L'\to L$ such that $p\circ\alpha=f$. Again, by the answer in the comments, this is equivalent to $pr_J \circ p\circ \alpha=pr_J\circ f$. Since $pr_J\circ \alpha=p_J$ and $pr_J\circ f=f_J$, we can rewrite that as $p_J\circ \alpha=f_J$. That's what we needed to prove.


TITLE: Arrange blocks to form matrix of $N \times 3$
QUESTION [1 upvotes]: Given are the blocks of 3 different colors (Red,Green and Blue).

Red colored block of size $1 \times 3.$
  Green colored block of size $1 \times 2.$
  Blue colored block of size $1 \times 1.$

We need to count the number of ways to make matrix of size $N \times 3$, for given $N.$
Note : The block can be used horizontally as well as vertically. So the red and green block can be used in two different ways (horizontally and vertically) while the blue block can be used only in one way (being of size $1 \times 1,$ it is immaterial how you place the block ).
Example : For $N=2$ answer is $29.$
The possible arrangements are:

REPLY [2 votes]: Nice question!
Let $a_n$ be the number of desired arrangements for an $n$ by $3$ matrix and we'd like to find a recursive formula for it.
For the sake of simplicity, let $1$ denote the use of a $1 \times 3,$ block $2$ denote the use of a $1 \times 2$ block and $3$ the use of a $1\times 1$ block. Let also $1v$ denote the use of a vertical $1 \times 3$ block and likewise, $1h$ the horizontal use.
1) There are $4$ possible ways to only cover the first row $(1h, (2h)3, 3(2h),(333))$ (where $(2h)3$ means a horizontal $1 \times 2 $ block followed by a $1 \times 1$ block) and for each configuration the rest of $(n-1) \times 3$ matrix can be filled out with $a_{n-1}.$
2) By investigation, there are $13$ possible ways to only cover the first two rows purely, i.e. those configurations which are not coming from a covering of the first row in case 1. Any such configuration, has to have at least one $2v.$ To see exactly why there are $13$ configurations, note that there are $29$ configurations in total as it was shown in the picture, where $4\times 4=16$ are coming from configurations of covering the first row, so $29-16=13.$
3) Further investigations (counting by hand, using case 2) shows that there are $70$ possible ways to only cover the first three rows purely which are not coming from a covering of the first row and a covering of the first two rows. Such a configuration must have at least one $1v.$
Finally, the recursive formula we get is
$$a_n= 4a_{n-1}+13a_{n-2}+70a_{n-3}.$$
Wolframalpha shows its characteristic polynomial has only one positive real root $x\simeq 7.1729$ so the complexity of this recursive approach is exponential which is not a surprise!
P.S. Try first and then let me know if you cannot find the number of configurations for case 3.


TITLE: Proof that $\lim (x_n)^{1/k}=(\lim x_n)^{1/k}$
QUESTION [2 upvotes]: I'm trying to prove $\lim (x_n)^{1/k}=(\lim x_n)^{1/k}$ having already proved it for $k=2$.  Even experimenting with $k=3$ I'm getting stuck.  If we call $x=\lim x_n$ then I have
$$|(x_n)^{1/3}-x^{1/3}| \cdot \left|\frac{(x_n)^{2/3}+x^{2/3}}{(x_n)^{2/3}+x^{2/3}}\right| = \left|\frac{x_n-x-x_n^{2/3}x^{1/3}+x_n^{1/3}x^{2/3}}{(x_n)^{2/3}+x^{2/3}}\right|$$
In the proof for $k=2$ I didn't have this positive term in the numerator to deal with.  I know that I could choose $|x_n-x|<\min\{\varepsilon,x/2\}$ which would imply that $x<2x_n$ but this seems to suggest a way to replace $x$ rather than $x_n$ which seems unhelpful.

REPLY [3 votes]: Do not complicate things, just use the fact that if $a_n$ and $b_n$ are convergent then $a_nb_n$  also is and $\lim a_n b_n=\lim a_n \cdot \lim b_n$.
Suppose that $\lim ((x_n)^{1/k}) \neq (\lim x_n)^{1/k}$ and take both sides to the power of $k$ and use above written law and then conclude.


TITLE: Classifying map of a graph of a morphism
QUESTION [2 upvotes]: Let $\epsilon$ be a topos. Let $f:Y\longrightarrow X$ be a morphism in $\epsilon$. By the graph of f we mean the mono $<id_Y,f>:Y\longrightarrow Y\times X$. Let $\Delta$ be the classifying map of the diagonal subobject $\delta:X\longrightarrow X\times X$ ($\delta=<id_X,id_X>$). Show that $\Delta o (f\times id_X)$ classifies the graph of f.
I tried to use the pullback lemma but I couldn’t prove that the other square with arrows $<id_Y,f>, f\times id_X,f, \delta$ is a pullback.

REPLY [4 votes]: By our favorite pullback lemma, if the top square in
$$\require{AMScd}\begin{CD} \bullet @>>> Y\times X \\
@VVV @VV{f\times id_X}V \\
X @>\delta_X>> X\times X \\
@VVV @VV\Delta_XV \\
1 @>>\top>\Omega \end{CD}$$
is a pullback then the outside rectangle is a pullback and the top horizontal morphism is the subobject classified by the right side. It's easy to see that $X\overset{f}{\longleftarrow}Y\overset{\langle id_Y,f\rangle}{\longrightarrow}Y\times X$ makes the top square commute, so we only need to show that it's a pullback to prove the theorem.
Let $X\overset{j}{\longleftarrow}J\overset{\langle k_1,k_2\rangle}{\longrightarrow}Y\times X$ be such that it makes the top square commute. Then $\langle j,j\rangle=\langle fk_1,k_2\rangle=\langle fk_1,fk_1\rangle$. But this means $j=fk_1$ and $\langle k_1,k_2\rangle =\langle k_1,fk_1\rangle=\langle id_Y,f\rangle\circ k_1$. So we have that there exists a map, namely $k_1$, $J\to Y$ with the requisite property.
So we show that this $k_1$ is unique. Let $i:J\to Y$ be any morphism such that  $fi=j$ and $\langle id_Y,f\rangle\circ i=\langle k_1,k_2\rangle$. But $\langle i,fi\rangle=\langle k_1,k_2\rangle$ immediately implies $i=k_1$, so our $k_1$ is unique.
Hence $X\overset{f}{\longleftarrow}Y\overset{\langle id_Y,f\rangle}{\longrightarrow}Y\times X$ makes the top square a pullback, and $\langle id_Y,f\rangle$ is the map classified by $\Delta_X\circ(f\times id_X)$.


TITLE: a quadratic equation for two unknown number
QUESTION [1 upvotes]: find values of $p$ such that the equation $4x^2 + 3px - 2p = 0$ has? below are a few choices of the value p:
a) 2 real roots
b) 1 real roots
c) no roots or complex roots

so far i did for a) 2 real roots
$$(3p)^2 - 4(4)(-2p) > 0\\
9p^2 +32p > 0\\
9\left( p^2+\frac{32p}{9} \right) > 0\\
p^2+\frac{32p}{9} > 0\\
p^2 +\frac{32p}{9} + \left(\frac{32}{18}\right)^2 > 0\\
\left(p + \frac{32}{18} \right) ^2 > 0 \\
p + \frac{32}{18} > 0\\
p > -\frac{32}{18} $$

REPLY [2 votes]: The roots are given by the quadratic formula:
$$
r = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \\
= \frac{-3C \pm \sqrt{9C^2 + 32p}}{2a}
$$
If the thing under the square root is positive, you'll get two roots. Under what conditions will you get just one? Under what condition will you get none?

REPLY [0 votes]: $D=(3p)^2+4\cdot4\cdot2p=9p^2+32p=p(9p+32)$
if $D>0$ then there is 2(different) real roots
$D=9p^2+32p=p(9p+32)>0$
$p\in(-\infty;-32/9)\cup(0;+\infty)$
if $D=0$ then there is 1(or 2 equal) real root
$p=0$ and $p=-32/9$
if $D<0$ then there is no roots or 2 complex roots
$p\in(-32/9;0)$


TITLE: Why does a homogeneous ODE need initial condition for a particular solution while a non-homogeneous ODE doesn't?
QUESTION [1 upvotes]: For homogeneous ODE's with constant coefficients you need intial conditions such as y(x0)=y0 and y'(x0)=y1
or some boundary values to find a particular solution because you need to find the constants c1 and c2 in the general solution equation y=c1  $e^{r1x}$$ +  $ c2 $e^{r2x} $ where r1 and r2 are roots of the auxillary equation.
But for non-homogeneous ODE's you can find a particular solution without having to know any intial conditions or boundary values.
Why ?

REPLY [2 votes]: No, you don't need initial conditions to find a particular solution of the homogeneous case.  For example, $e^{r_1 x}$ is a particular solution.


TITLE: The complement of $K$ in $G$
QUESTION [2 upvotes]: There is a definition which help us to understand the semi-direct product well:

Let $K$ be a subgroup of a group $G$. Then a subgroup $Q\leq G$ is a complement of $K$ in $G$ if $K\cap Q=1$ and $KQ=G$.

Habitually, whenever I see the form $KQ=G$, I think of one of the subgroups $K$ or $Q$ are at least normal in group. But in the definition above J.J.Rotman quoted that $K$ is not necessarily normal in $G$ and moreover he didn't say anything about normality for $Q$ as well.
May I ask you to present me an example, having two subgroups not normal in $G$, and yet $G=KQ$? And if I misunderstand about above, please tell me. Thanks.

REPLY [3 votes]: Take $G = A_{5}$,$K = A_{4}$ (say the subgroup of $A_{5}$ fixing $5$) and $Q$ to be a Sylow $5$-subgroup of $A_{5}.$


TITLE: Proof that $y^2=x^3+21$ has no integral solution with elementary methods?
QUESTION [10 upvotes]: I tried to prove that $$y^2=x^3+21$$ has no integral solution in the way as shown here : http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/mordelleqn1.pdf
My work so far : $x$ cannot be even because we would have $y^2\equiv 5\mod 8$ , which is a contradiction. Hence, $x$ is odd and $y$ is even. We have $$x\equiv x^3=y^2-21\mod 8$$, which gives the possibilities $x=3\ ,\ y=0\ or \ 4$ and $x=7\ ,\ y=2\ or\ 6$ modulo $8$.
Now I tried various factorizations to get a contradiction with quadratic residues :
$1)$ : $y^2+6=x^3+27=(x+3)(x^2-3x+9)$
$2)$ : $y^2-13=x^3+8=(x+2)(x^2-2x+4)$
$3)$ : $y^2-20=x^3+1=(x+1)(x^2-x+1)$
but in no case I found a contradiction with quadratic residues.

Can this particular equation be shown to be non-solveable in integers in the described way ?
How can I find systematically a suitable factorization in general leading to the desired contradiction, assuming the equation actually has no integral solution ?

REPLY [1 votes]: This will not be a complete solution. Note that from your equations 1) and 3), two of the three possible cases of $x \pmod{3}$ can be eliminated:
If $x \equiv 0 \pmod{3}$, then from 1), $y^2 + 6 \equiv 0 \pmod{27} \longrightarrow y^2 \equiv 21 \pmod{27}$, which is impossible.
If $x \equiv 2 \pmod{3}$, then from 3), $y^2 - 20 \equiv 0 \pmod{9} \longrightarrow y^2 \equiv 2 \pmod{9}$, which is impossible.
Now for the apparently more difficult case of $x \equiv 1 \pmod{3}$. You have already shown that $x \equiv 3 \pmod{4}$, which means that $x \equiv 7 \pmod{12}$ is the only remaining possibility. Unfortunately, I can’t see how to carry this argument any further.


TITLE: How we can show this ;$\frac{x^2+y^2+z^2}{2}\times\frac{x^5+y^5+z^5}{5}=\frac{x^7+y^7+z^7}{7}$
QUESTION [1 upvotes]: Let be $\quad x+y+z=0$
show this:
$$\frac{x^2+y^2+z^2}{2}\times\frac{x^5+y^5+z^5}{5}=\frac{x^7+y^7+z^7}{7}$$
I solved ,but Im interesting what are you thinking about this,how can we arrive to solution quickly?

REPLY [7 votes]: Your polynomials are invariant by the action of $S_3$ on $(x,y,z)$.
A standard result says that the graded ring $\Bbb Q[x,y,z]^{S_3}$ is $\Bbb Q[x+y+z;xy+yz+xz;xyz]$.
Furthermore here, quotienting by $(x+y+z)$ we can work in the ring $(\Bbb Q[x,y,z]/(x+y+z))^{S_3} \cong \Bbb Q[xy+yz+xz;xyz]$.
Now in this graded ring, the pieces of degree $2,5,7$ are all of dimension $1$ (there is only one decomposition of $2,5,7$ as a sum of $2$s and $3$s).
Picking $x,y,z = 1,1,-2$ shows that $x^k+y^k+z^k$ are nonzero in that ring for $k > 1$, which proves that $(x^2+y^2+z^2)(x^5+y^5+z^5) = q (x^7+y^7+z^7) \pmod {x+y+z}$ for a rational number $q$ (and also that $(x^2+y^2+z^2)(x^3+y^3+z^3) = q' (x^5+y^5+z^5)$ but we don't particularly care).
Then you can easily check that when replacing $z$ with $-x-y$ in your expressions, the dominant coefficient in your polynomials is $1$ after doing the
divisions (note that for an odd prime $p$, by Fermat's little theorem, $(x^p+y^p+(-x-y)^p)/p$ even has integral coefficients, ... and the case $p=2$ just works), and you only have to check $1 \times 1 = 1$ to finish the proof.
You can also evaluate $(x^2+y^2+z^2)(x^5+y^5+z^5) = q (x^7+y^7+z^7)$ at $x,y,z = 1,1,-2$ to get $6\times (-30) = q \times (-126)$ hence $q=10/7$.