TITLE: Schreier generators
QUESTION [1 upvotes]: I am facing some problem in understanding the proof of the following theorem. Can somebody provide me a simple proof .
Given $G=\langle A \rangle$ and $H \leq G$, and $R$ is the coset representatives for $H$ in $G$.
Let $B=\{r_1ar^{-1}_2 | r_1,r_2 \in R, a \in A\}\cap H.$
Then $B$ generates $H$.

REPLY [0 votes]: Your assertion is a few incorrect. It must be as follows:
Given $G=\langle A \rangle$ and $H\le G$, and $R$ is a set of representatives  of the  right cosets for H in G. Let B={r1ar−12|r1,r2∈R,a∈A}∩H. Then B generates H. Let     $B = \{r_1ar^{-1}_2 | r_1 \in R, a \in A\}$, where $r_2$ is the representative of the coset $Hr_1a$. Then $B$ generates $H$.
You can find a proof in:
M.I. Kargapolov, Ju.I. Merzljakov, Fundamentals of the Theory of Groups, Springer, Graduate Texts in Math (62), Theorem 14.3.1.


TITLE: Markov Chain upper bound on the probability of hitting time
QUESTION [6 upvotes]: I encountered the following problem.

$\{x_t\}$: Markov chain in discrete time;
$\Omega$: a finite state space s.t. $|\Omega|=n<\infty$;
$\tau_w\equiv\min\{t\ge 0\,|\,x_t=w\}$, $w\in\Omega$ (first hitting time).

Prove:  For each $T\ge 1$ and every $x,y\in \Omega$
$$\Pr(\tau_y=T|x_0=x)\le\frac nT.$$

Effort: This is a surprising result as the setup is terribly general. I proceeded by induction. Using recursive characterization, we have
$$\Pr(\tau_y=T+1|x_0=x)=\sum_{z\ne y}\Pr(\tau_y=T|x_0=z)p(x,z),$$
where $p(x,z)=\Pr(x_{t+1}=x|x_t=z)$ is the transition probability. For each Markov chain, using the inductive hypothesis, we can easily confirm that this holds for $T$ sufficiently large. So far I cannot see how to show this for a general $T\ge n+1$.
Any hints or comments will be highly appreciated!

REPLY [0 votes]: Edit: this is wrong.
This seems incorrect.  Multiplying both sides by T and summing over T we get $ E( \tau  _y | x_0 =x) \leq n $.   I don't see why this should be true in general.


text:
\begin{document}

\title{Enumerating isoclinism classes of semi-extraspecial groups}
\author{Mark L. Lewis}
\address{
	Kent State University\\
	Department of Mathematical Sciences\\
  MSB 233\\
	Kent, OH 44242
}
\email{lewis@math.kent.edu}

\author{Joshua Maglione}
\address{
	Kent State University\\
	Department of Mathematical Sciences\\
  MSB 233\\
	Kent, OH 44242
}
\email{jmaglion@math.kent.edu}

\date{\today}
\keywords{Pfaffian, genus 2, bilinear maps}

\begin{abstract}
We enumerate the number of isoclinism classes of semi-extraspecial $p$-groups with derived subgroup of order $p^2$.
To do this, we enumerate $\GL(2, p)$-orbits of sets of irreducible, monic polynomials in $\mathbb{F}_p[x]$.
Along the way, we also provide a new construction of an infinite family of semi-extraspecial groups as central quotients of Heisenberg groups over local algebras.
\end{abstract}

\maketitle

\section{Introduction}

All groups in this paper are finite, and $p$ is a prime.
A $p$-group $G$ is said to be {\it semi-extraspecial} if every subgroup $N$ having index $p$ in $Z (G)$ satisfies the condition that $G/N$ is extra-special.
Semi-extraspecial groups are a special case of Camina groups, i.e.\ groups $G$ where every irreducible character vanishes on $G\backslash G'$ \cites{Camina, Macdonald:semi-extraspecial, CMS:Frobenius-groups}.
In fact, semi-extraspecial groups are exactly the Camina $p$-groups of class 2 \cite{Verardi}*{Theorem~1.2}.

These groups are virtually indistinguishable, so in the context of group isomorphism and enumeration, they pose a challenge.
Indeed, the (nontrivial) central quotients of Heisenberg groups over fields, considered in \cite{LW:Heisenberg}, are all semi-extraspecial groups.
Those quotients have exponent $p$, isomorphic character tables, two possible orders of centralizers, and a limited number of possible isomorphism types of automorphism groups---after fixing the order of the group and derived subgroup.

Applying ideas of Brooksbank-Maglione-Wilson \cite{BMW}, we the study of semi-extraspecial $p$-groups $G$ with $|G'| = p^2$ by considering a $\PGL(2,p)$-action on multisets of polynomials in $\mathbb{F}_p[x]$.
In particular, we enumerate the number of isoclinism classes of such groups up to order $p^{12}$.
A slight extension of Verardi \cite{Verardi}*{Corollary~5.11} states that there is a unique isoclinism class of semi-extraspecial groups $G$ with $|G| = p^6$ and $|G'| = p^2$ for each prime $p$.
We show that a similar result holds for the next larger size of semi-extraspecial groups.

\begin{thm}\label{main1}
For each prime $p$, there is a unique isoclinism class of semi-extraspecial groups $G$ with $|G| = p^8$ and $|G'| = p^2$.
\end{thm}

At this point, one might be tempted to conjecture for every prime $p$ and every positive integer $n$
that there is a unique isoclinism class of semi-extraspecial groups $G$ with $|G| = p^{2n+2}$ and $|G'| = p^2$.
However, starting with the next size, we will see that the situation becomes more complicated.

\begin{thm}\label{main2}
For every prime $p$, there are $p + 3 - \gcd(2, p)$ isoclinism classes of semi-extraspecial groups $G$ with $|G| = p^{10}$ and $|G'| = p^2$.
\end{thm}

For the next size, the formula gets even more complicated.

\begin{thm} \label{main3}
For every prime $p$, the number of isoclinism classes of semi-extraspecial groups $G$ with $|G|=p^{12}$ and $|G'|=p^2$ is
\[ \frac{1}{30}\left( 11p^2 - 5p - 22 +10\gcd(3,p-2) + 6\gcd(5,p) + 12\gcd(5, p^2-1)\right).  \]
\end{thm}

We could continue in this fashion and find formulas, depending on $p$, for the number of isoclinism classes of semi-extraspecial groups $G$ with $|G| = p^{2n + 2}$ and $|G'| = p^2$ for values of $n$ that are larger than $5$.
However, these functions appear to get progressively more complicated as $n$ increases, and we believe that these cases illustrate the procedure so that the sufficiently motivated reader can compute the function for larger $n$ if desired.

\medskip

Along the way to enumerating these isoclinism classes, we find a new way to construct an infinite family of semi-extraspecial groups.
To date, all known constructions of semi-extraspecial groups begin with a semifield $A$ or by taking a central product of semi-extraspecial groups.  A (finite) semi-field is an algebra with identity where the product $a *b = 0$ if and only if either $a = 0$ or $b = 0$.  Since $A$ is finite, this implies that every nonzero element has both a left inverse and a right inverse.  However, since $A$ is not necessarily associative or commutative, these left and right inverses need not be equal.  It is this invertibility condition that makes the following groups semi-extraspecial.

If $A$ is any algebra, the Heisenberg group over $A$ is the group
\begin{equation}\label{eqn:semifield-group}
  H(A) = \left\{ \begin{bmatrix} 1 & e & z \\ & 1 & f \\ & & 1 \end{bmatrix} \;\middle|\; e,f,z\in A \right\}.
\end{equation}
It is not difficult to see that $H(A)$ is semi-extraspecial if and only if $A$ is a semifield \cite{Lewis:expository}.  Because $H(A)$ is semi-extraspecial when $A$ is a semifield, every central quotient is either abelian or semi-extraspecial.  One can twist the semifield group in~\eqref{eqn:semifield-group} to get a different class of semi-extraspecial groups \cite{Lewis:ses-groups}.  At this time, the only way we know how to construct a semi-extraspecial group is to take a quotient of $H(A)$ for a semifield $A$, a quotient of the twisted semifield groups in \cite{Lewis:ses-groups}, or to take central products of these groups.

To obtain the new construction in this paper, we start with an algebra $A$ with zero divisors.  Because of the zero divisors, $H(A)$ is not semi-extraspecial.
We correct this by constructing the quotient by a subspace that complements the minimal ideal in $A$.

\begin{thm}\label{main4}
Let $K$ be a finite field, $a(x)\in K[x]$ be irreducible of degree $\geq 2$, and let $c>1$ be an integer.
Suppose $S\leq A$ is a $K$-subspace, and set $G=H(A)/N(S)$, where
\[ N(S) = \left\{ \begin{bmatrix} 1 & 0 & s \\ & 1 & 0 \\ & & 1 \end{bmatrix} \;\middle|\; s\in S \right\} . \]
Then $G$ is semi-extraspecial if, and only if, $A= S + (a(x)^{c-1})$.
\end{thm}

We ask whether all of the groups in Theorem~\ref{main4} are also central quotients of the semifield groups in~\eqref{eqn:semifield-group}.  This is true for all of the ones we have been able to determine.  The case we have studied most closely are the quotients of the semifield groups of order $3^{12}$.  We note that although there are many infinite families of semifields that have been constructed \cites{JJB:Handbook, Kantor:finite-semifields}, there is no evidence that these families contain all of them. Indeed, they do not span the table of semifields of order $81$ \cite{Dempwolff:81}.
Going back to our initial question, we ask if $G$ is as in Theorem~\ref{main4}, then does there exist a semifield $A$ of order $p^{cd}$ such that $G \cong H(A)/Z$ where $Z$ is some proper subgroup of the center of $H (A)$?  It is possible that the construction in Theorem \ref{main4} might yield new semi-extraspecial groups that do not arise as a quotient of a group associated with any semifield.

\section{Groups and bilinear maps}

Assume that $K$ is a field and $U$, $V$, and $W$ are $K$-vector spaces.
A map $\circ : U\times V\rightarrowtail W$ is $K$-bilinear if for all $u,u'\in U$, $v,v'\in V$, and $k\in K$,
\begin{align*}
  (u+ku')\circ v &= u\circ v + k(u'\circ v), & u \circ (v+kv') &= u\circ v + k(u\circ v').
\end{align*}
We will use $\rightarrowtail$ to denote a bilinear map (bimap), and in the case where $\dim_K(W)=1$, we call $\circ$ a bilinear \emph{form}.
The \emph{radicals} of $\circ$ are $U^\perp=\{ v \in V \mid U\circ v = 0\}$ and $V^\perp=\{ u\in U\mid u\circ V = 0\}$.
The bimap $\circ$ is \emph{nondegenerate} if $U^\perp$ and $V^\perp$ are trivial, and $\circ$ is \emph{full} if $U\circ V = W$.
We say a bimap is \emph{fully nondegenerate} if it is both full and nondegenerate.

Our main source of bimaps come from finite $p$-groups, $G$, of exponent $p$ and class 2, via the Baer correspondence.
For such a group we define the biadditive commutator map to be $\circ_G : G/Z(G)\times G/Z(G) \rightarrowtail G'$, where
\[ (Z(G)g)\circ (Z(G)h) = [g,h]. \]
Then $\circ_G$ is $\mathbb{F}_p$-bilinear and fully nondegenerate.
In the case when $G$ is semi-extraspecial, both $G/Z(G)$ and $G'$ are elementary abelian, and we write $\circ_G : V\times V\rightarrowtail W$, where $V=G/Z(G)$ and $W=G'$.

Two bimaps $\circ, \bullet : V\times V \rightarrowtail W$ are \emph{pseudo-isometric} if there exists $(f,g)\in\Aut(V)\times \Aut(W)$ such that for all $u,v\in V$, $(uf)\bullet (vf) = (u\circ v)g$.
The bimaps are \emph{isometric} if they are pseudo-isometric with pseudo-isometry $(f,1)$.
In \cite{Hall:isoclinism}, Hall initiated a study of $p$-groups up to isoclinism as a weaker form of isomorphism.
Two class 2 groups $G$ and $H$ are \emph{isoclinic} if there exists isomorphisms between $f : G/Z(G)\rightarrow H/Z(H)$ and $g : G'\rightarrow H'$ such that $(f,g)$ is a pseudo isometry from $\circ_G$ to $\circ_H$.

\begin{defn}
A class $2$ $p$-group $G$ is \emph{semi-extraspecial} if $G'=Z(G)=G^p$ and if for all $g\in G\backslash Z(G)$ and $z\in G'$, there exists $h\in G$ such that $[g,h]=z$.
\end{defn}

In the context of bimaps, $\circ:V\times V\rightarrowtail W$, this is equivalent to the following.
For all $u\in V$ the linear maps $L_u, R_u : V\rightarrow W$, where $vL_u= u\circ v$ and $vR_u = v\circ u$, are surjective.
As our bimaps are alternating, it is enough to check this for just
This implies that $\dim(W)\leq\dim(V)$.

An important algebra associated to a $K$-bimap $\circ: V \times V\rightarrowtail W$ is its centroid: the largest algebra $C$ for which is $C$-bilinear.
For $\Omega = \End(U)\times \End(V) \times \End(W)$, the centroid is
\begin{align*}
  \mathcal{C}(\circ) &= \{ (X, Y, Z)\in\Omega \mid (uX)\circ v = u\circ (vY) = (u\circ v)Z \} .
\end{align*}
If $\circ$ is fully nondegenerate, then $\mathcal{C}(\circ)$ is commutative.
The centroid plays a critical role in direct decompositions of groups \cite{Wilson:direct-decomposition} and in the definition of genus \cite{BMW}.

\subsection{Pfaffians of bimaps}\label{sec:Pfaffians}

Fix a $K$-bimap, $\circ : V\times V\rightarrowtail W$.
For $\omega\in W^*:=\Hom(W,K)$, define $\circ^\omega:U\times V\rightarrowtail K$ where
\[ u\circ^\omega v = (u\circ v)\omega.\]
Fix a basis $\mathcal{X}$ for $V$ and $\mathcal{Z}^*$ for $W^*$.
For each $\omega\in\mathcal{Z}^*$, write $\circ^\omega$ as a matrix $M_\omega$ with respect to $\mathcal{X}$, the structure constants of the $K$-form $\circ^\omega$.
The \emph{generalized discriminant} of $\circ: V\times V\rightarrowtail W$, with respect to $\mathcal{X}$ and $\mathcal{Z}^*$, is a polynomial in indeterminants $x_\omega$, for $\omega\in\mathcal{Z}^*$, where
\[ \text{disc}(\circ) = \det\left(\sum_{\omega\in\mathcal{Z^*}}M_\omega x_\omega\right). \]
When $\circ$ is \emph{alternating}, i.e.\ for all $u\in V$, $u\circ u=0$, define the (\emph{generalized}) \emph{Pfaffian} of $\circ$ to be the homogeneous polynomial $\Pf(\circ)$ such that $\Pf(\circ)^2=\text{disc}(\circ)$.

The next theorem is due to I.D.\ Macdonald \cite{Macdonald:semi-extraspecial} who proved the conclusion for Camina groups.

\begin{thm}[\cite{Macdonald:semi-extraspecial}*{Theorem~3.1}]\label{thm:Pfaffian}
A Pfaffian of $\circ_G:V\times V\rightarrowtail W$ has no solutions in $\mathbb{P}W$ if, and only if, $G$ is semi-extraspecial.
\end{thm}

\section{Decompositions, groups of genus 2, and Pfaffians}

A \emph{central decomposition} of a group $G$ is a set $\mathcal{H}=\{H : H\leq G\}$ such that $\langle \mathcal{H}\rangle = G$, for all $H\in\mathcal{H}$, $\langle \mathcal{H}-H\rangle \ne G$, and $[H,\langle\mathcal{H}-H\rangle]=1$.
Note that this definition allows for $Z(H_1)\ne Z(H_2)$ for $H_1,H_2\in\mathcal{H}$.
A group $G$ is \emph{centrally indecomposable} if $\{ G\}$ is the only central decomposition of $G$.
A \emph{direct decomposition} of $G$ is a central decomposition $\mathcal{H}$ such that for all $H\in\mathcal{H}$, $H\cap \langle \mathcal{H}-H\rangle=1$, and $G$ is \emph{directly indecomposable} if $\{ G\}$ is the only direct decomposition of $G$.
We say a central (or direct) decomposition $\mathcal{H}$ is \emph{fully-refined} if for all $H\in\mathcal{H}$, $H$ is centrally (or directly) indecomposable.

\begin{lem}\label{lem:direct-decomp}
If $G$ is semi-extraspecial, then $G$ is directly indecomposable.
\end{lem}

\begin{proof}
Suppose $\mathcal{H}$ is a direct decomposition of $G$ with $H,K\in\mathcal{H}$.
By definition, $[G,H]\leq H$, but since $G$ is semi-extraspecial, it follows that for all $z\in Z(K)$, there exists $g\in G$ such that $[g,h]=z$.
Therefore, $H=K$, so $\mathcal{H}=\{G\}$.
\end{proof}

The central product of $G$ with $H$ can be defined as a central quotient of $G\times H$ with an isomorphism $\theta: Z(G)\rightarrow Z(H)$, c.f.\ Hall \cite{Hall:isoclinism}.
We note that different isomorphisms $\theta$ may produce non-isomorphic central products of groups.
Our definition above allows for the case where $Z(G)$ may properly embed into $Z(H)$.
Because of this, we prove that with semi-extraspecial groups, we must have all the centers of each central factor isomorphic.
The following proposition is a slight generalization of Beisiegel \cite{Beisiegel:ses-groups}*{Lemma~2}.

\begin{prop}\label{prop:central-decomp}
Suppose $\mathcal{H}$ is a central decomposition of $G$ such that each $H\in\mathcal{H}$ is semi-extraspecial.
Then $G$ is semi-extraspecial if, and only if, for each $H\in\mathcal{H}$, $Z(H)=Z(G)$.
\end{prop}

\begin{proof}
First, we suppose that for all $H\in\mathcal{H}$, $Z(H)=Z(G)$.
If $N<Z(G)$ is a maximal subgroup, then $N$ is a maximal subgroup of each $Z(H)$.
Therefore, $H/N$ is extraspecial, and $G/N=\langle H/N : H\in\mathcal{H}\rangle$, where $Z(H/N)=Z(G/N)$.
This is a central decomposition of $G/N$ into extraspecial groups; hence, $G/N$ is extraspecial.

Conversely, suppose there exists $H\in\mathcal{H}$ such that $Z(H)\ne Z(G)$.
Let $N<Z(G)$ be a maximal subgroup.
If $Z(H)>Z(G)$, then $N$ is not a maximal subgroup of $Z(H)$, and in particular, $H/N$ is not extraspecial.
Therefore, $\langle HN/N: H\in\mathcal{H}\rangle$ cannot be extraspecial, so $G$ is not semi-extraspecial.
On the other hand, suppose there exists $z\in Z(G)$ such that $z\notin Z(H)=H'$.
Then for all $h\in H$ and $g\in H$, $[g,h]\ne z$.
From the central decomposition property, it follows that for all $h\in H$ and $g\in G$, $[g,h]\ne z$, so that $G$ is not semi-extraspecial.
\end{proof}

We state a useful theorem of Wilson~\cite{Wilson:direct-decomposition} characterizing direct decompositions of $p$-groups of class 2.
A commutative ring is \emph{local} if it has a unique maximal ideal.

\begin{thm}[\cite{Wilson:direct-decomposition}*{Theorem~8}]\label{thm:local-centroid}
Let $G$ be class $2$ and exponent $p$.
Then $\mathcal{C}(\circ_G)$ is a local $\mathbb{F}_p$-algebra if, and only if, $G$ is directly indecomposable.
\end{thm}

Lemma~\ref{lem:direct-decomp} together with Theorem~\ref{thm:local-centroid} are key to proving the following proposition.
In general for fully nondegenerate bimaps, the centroid is a commutative ring.
In the next lemma, we show that because $\mathcal{C}(\circ_G)$ is Artinian with trivial nilradical, $\mathcal{C}(\circ_G)$ must be a simple $\mathbb{F}_p$-algebra.

\begin{prop}\label{prop:centroid-field}
If $G$ is semi-extraspecial, then $\mathcal{C}(\circ_G)$ is a field.
\end{prop}

\begin{proof}
Suppose $(X,Z)\in\mathcal{C}(\circ_G)\subseteq \End(V)\times \End(W)$ is nilpotent.
For all $u\in V$, we claim that the linear map $L_{uX} : V\rightarrow W$, where $v\mapsto (uX)\circ v$, is not surjective.
In fact, since $(X,Z)\in\mathcal{C}(\circ_G)$, it follows that $\im(L_{uX})\leq\im(Z)$.
As $Z$ is nilpotent, $\im(Z)<W$, so for all $g\in G$, there exists $z\in Z(G)$ such that $z\notin [g,G]$.
This would imply that $G$ is not semi-extraspecial.
Therefore, the nilradical of $\mathcal{C}(\circ_G)$ is trivial.
Since $\mathcal{C}(\circ_G)$ is Artinian (in particular finite), it follows that $\mathcal{C}(\circ_G)$ is semi-simple.
By Lemma~\ref{lem:direct-decomp} and Theorem~\ref{thm:local-centroid}, it follows that $\mathcal{C}(\circ_G)$ is a simple $\mathbb{F}_p$-algebra.
Because $\circ_G$ is fully nondegenerate, $\mathcal{C}(\circ_G)$ is commutative, and by the Wedderburn--Artin Theorem, $\mathcal{C}(\circ_G)$ is a field.
\end{proof}

\begin{remark}\label{rem:cent}
Because $K=\mathcal{C}(\circ_G)$ is a field and $\circ_G$ is $K$-bilinear, we now assume throughout that $\circ_G:V\times V\rightarrowtail W$ is a bimap over $K$, so $V$ and $W$ are $K$-vector spaces.
Another fact that we will use later is that $\mathcal{C}(\circ_G)$ is faithfully represented on all three coordinates whenever $\circ_G$ is fully nondegenerate; in particular it is faithfully represented in $\End(W)$.
Indeed, if $(X,Z),(Y,Z)\in\mathcal{C}(\circ_G)\subseteq \End(V)\times\End(W)$, then for all $u,v\in V$, $(uX-uY)\circ_G v = 0$.
Because $\circ_G$ has trivial radical, $X=Y$.
\end{remark}

\begin{defn}
Suppose $G$ is a nilpotent class 2 and isoclinic to a direct product $H_1 \times \cdots \times H_r$ of directly indecomposable groups.
The \emph{genus} of $G$ is the maximum rank of $[H_i, H_i]$ as a $\mathcal{C}(\circ_{H_i})$-module.
\end{defn}

Lemma~\ref{lem:direct-decomp} and Proposition~\ref{prop:centroid-field} enable a simpler definition of genus for our purposes.
The genus of a semi-extraspecial group $G$ is the dimension of $G'$ as a $\mathcal{C}(\circ_G)$-vector space.
We will say a (semi-extraspecial) group $G$ is \emph{genus $d$ over $K$} if $\mathcal{C}(\circ_G)\cong K$ and $\dim_K(G')=d$.

\subsection{Groups of genus 2}

We cite two key theorems from \cite{BMW} that we use later.
Involved in the classification of groups of genus 2 are Heisenberg groups over local algebras, $A=K[x]/(a(x)^c)$, where $a(x)$ is irreducible in $K[x]$ and $c\geq 1$,
\begin{align*}
  H(A) &  =\left\{ \begin{bmatrix}
  1 & e & z \\ 0 & 1 & f \\ 0 & 0 & 1
  \end{bmatrix} \;\middle|\; \begin{array}{c} e,f,z\in A\end{array}\right\}.
\end{align*}
Observe that $H(A)$ is semi-extraspecial if, and only if, $c=1$.
To see this, when $c=1$, this is a Heisenberg group over a field which is semi-extraspecial, but on the other hand, if $c>1$, then the ring $K[x]/(a(x)^c)$ has nilpotent elements.
These nilpotent elements prevent the group from satisfying the property that for all $g\in G\backslash G'$ and $z\in G'$, there exists $h\in G$ such that $[g,h]=z$.
In the case when $c>1$, quotients of $H(A)$ can still be semi-extraspecial even though the group is not semi-extraspecial.
We will characterize these quotients in Section~\ref{sec:ses-groups-genus2}.

\begin{thm}[{\cite{BMW}*{Theorem~1.2}}]\label{thm:indecomp-genus2}
A centrally indecomposable $p$-group of exponent $p$ and genus $2$ over a finite field $K$ is isomorphic to one of the following
\begin{enumerate}
  \item[(i)] a central quotient of the Heisenberg group $H=H(K[x]/(a(x)^c))$ by a subgroup $N$, such that $1-N$ is a $K$-subspace of $1-H'$;

  \item[(ii)] the matrix group
  \begin{align*}
	  H^{\flat}(K, m) & :=
	  \left\{
	  \left[\begin{array}{c|c|c}
		  I_2 & \begin{array}{cccc}
			  e_1 & \cdots & e_m & 0 \\
			  0 & e_1 & \cdots & e_m
		  \end{array} &
		  \begin{array}{c} z_1 \\ z_2 \end{array}\\
		  \hline
		   & I_{m+1} & \begin{array}{c} f_0\\ \vdots \\ f_{m}\end{array}\\
		   \hline
		   & & 1
	  \end{array}\right] \;\middle|\; e_i, f_i,z_i \in K\right\}.

  \end{align*}
\end{enumerate}
\end{thm}

A key idea used throughout the paper comes from the following theorem.
This converts the problem of enumerating groups to enumerating orbits of (principal ideals of) polynomials under the action of $\GammaL(2,K)=\GL(2,K)\rtimes \Gal(K)$.
We will describe the details of this action in Section~\ref{sec:GL2-action}.
For our purposes, the crux is that the isomorphism problem of semi-extraspecial groups of order $p^{2n+2}$ with exponent $p$ and derived subgroup of order $p^2$ is determined by the $\GL(2,p)$ action on the \emph{multiset} of Pfaffians of a fully refined central decomposition of $G$.
Specifically, if $\mathcal{H}$ is a fully-refined central decomposition of $G$, then the multiset of Pfaffians of $G$ is $\{ \Pf(\circ_H) \mid H\in\mathcal{H}\}$.
If every $H\in\mathcal{H}$ is isomorphic to a group from Theorem~\ref{thm:indecomp-genus2}(i), then this multiset completely determines the group.

\begin{thm}[\cite{BMW}*{Theorem~3.22}]\label{thm:Pfaffian-bijection}
Suppose $G_1$ and $G_2$ are $p$-groups of class $2$, exponent $p$, and genus $2$ over $K$.
Let $\mathcal{H}_1=\{H_1,\dots, H_s\}$ and $\mathcal{H}_2=\{K_1,\dots, K_t\}$ be fully-refined central decompositions of $G_1$ and $G_2$ respectively.
Then $G_1\cong G_2$ if, and only if, $s=t$ and there exists $M\in\GammaL(2,K)$ and $\sigma$, a permutation of $\{1,\dots, t\}$, such that for all $i$,
\[ \left( \Pf(\circ_{H_i})^M \right) = \left( \Pf(\circ_{K_{i^{\sigma}}})\right). \]
\end{thm}

We want to pause to give two examples that illustrate some of the nuances of Pfaffians.
Our first example shows the need to first determine a fully refined central decomposition of the group, before computing its Pfaffian.
We note that these examples apply more generally for every prime.

\begin{ex}\label{ex:genus}
Let $K$ be a quadratic extension of $\mathbb{F}_5$, and let $G$ be a central product of two copies of $H(K)$ with centers identified.
So $|G|=5^{10}$ and $|G'|=5^2$.
Now let $A=\mathbb{F}_5[x]/\left((x^2+2)^2\right)$ and consider the group $H(A)$.
The ideal $(x^2+2)$ is spanned by $\{x^2+2, x^3+2x\}$ in $A$, and let $S$ be the subspace spanned by $\{ 1, x \}$.
Let
\[ N = \left\{ \begin{bmatrix} 1 & 0 & s \\ & 1 & 0 \\ & & 1 \end{bmatrix} \; \middle| \; s\in S \right\} \triangleleft H(A). \]
Later we prove in Theorem~\ref{thm:genus2-ses} that $H=H(A)/N$ is centrally indecomposable and semi-extraspecial.
Importantly, $|H|=5^{10}$ and $|H'|=5^2$.
Because $G$ is decomposable and $H$ is indecomposable, they are not isomorphic.
Note also that $G$ is genus 1 over $K$ and $H$ is genus 2 over $\mathbb{F}_5$.

We will show they have the same Pfaffians.
Assume $\{\alpha, 1\}$ is a basis for $K$, where $\alpha^2+2=0$.
Set
\[ B = \left[ \begin{array}{c|c}
  \begin{array}{cc} \alpha & 1\\ 3 & \alpha \end{array} & 0 \\ \hline
  0 & \begin{array}{cc} \alpha & 1\\ 3 & \alpha \end{array}
\end{array} \right], \]
so the bimap $\circ_G:\mathbb{F}_5^8\times \mathbb{F}_5^8 \rightarrowtail \mathbb{F}_5^2$ has structure constants $\left[\begin{smallmatrix} 0 & B \\ -B^T & 0 \end{smallmatrix}\right]$.
Replacing the basis of $K$ with indeterminants $X$ and $Y$, the Pfaffian of $G$ is $(X^2+2Y)^2$.
On the other hand, set
\[ C = \begin{bmatrix} 0 & 0 & 2(3x^2+1) & x^3+2x \\
  0 & 2(3x^2+1) & x^3+2x & 3x^2+1 \\
  2(3x^2+1) & x^3+2x & 3x^2+1 & 0 \\
  x^3+2x & 3x^2+1 & 0 & 0 \end{bmatrix}. \]
Assuming the basis for $A$ is $\{1, x, x^2+2, x^3+2x\}$, then the structure constants for the bimap $\circ_H$ is $\left[\begin{smallmatrix} 0 & C \\ -C^T & 0 \end{smallmatrix}\right]$.
Set the basis of the codomain of $\circ_H$ to be $\{ x^3+2x, 3x^2+1 \}$.
Replacing that with indeterminants $X$ and $Y$, the Pfaffian is equal to $(X^2+2Y^2)^2$.
Therefore, the Pfaffians of $\circ_G$ and $\circ_H$ are identical even though $G\not\cong H$.

However, if we instead first determine a fully refined central decomposition for $G$ and $H$ and compute the Pfaffians of the indecomposable factors we get different invariants.
The multiset of Pfaffians for $G$ is $\{ X^2+2Y^2, X^2+2Y^2\}$ (or just $\{X, X\}$ over $K$), and the multiset of Pfaffians for $H$ is $\{ (X^2+2Y^2)^2\}$, which are not equivalent.\qed
\end{ex}

Theorem~\ref{thm:Pfaffian-bijection} greatly depends on the fact that the groups are genus $2$.
When the genus is larger, deciding isomorphism of groups does not reduce to deciding if their Pfaffians are equivalent with respect to Theorem~\ref{thm:Pfaffian-bijection}.
In fact, such groups can have the same Pfaffian and not be isomorphic as the next example illustrates.

\begin{ex}\label{ex:same-Pfaff}
We present two bimaps $V\times V\rightarrowtail W$ with the same Pfaffian that are not pseudo-isometric, so the corresponding groups are not isomorphic.
Suppose $p=3$, then $f(x) = x^3 + 2x + 1$ is irreducible in $\mathbb{F}_3[x]$.
The matrices
\begin{align*}
M_1 &= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 2 \\ 0 & 2 & 0 \end{bmatrix} &
M_2 &= \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 2 \end{bmatrix} &
M_3 &= \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}
\end{align*}
form the structure constants of the $\mathbb{F}_3$-algebra $\mathbb{F}_3[x]/(f(x))$ with respect to the ordered basis $(1,x,x^2)$.
Let $A$ be the $3\times 3$ matrix with $1$ in the $(1,2)$-entry, $-1$ in the $(2,1)$-entry, and $0$ elsewhere.
Set $V=\mathbb{F}_3^6$ and $W=\mathbb{F}_3^3$.
Define two alternating forms with the following structure constants
\[ \left( \begin{bmatrix} 0 & M_i \\ -M_i & 0 \end{bmatrix} \right) \qquad \text{and} \qquad \left( \begin{bmatrix} 0 & M_i \\ -M_i & A \end{bmatrix} \right). \]

Both bimaps have the same Pfaffians: $x^3+x^2y+xy^2+2xz^2 + 2y^3 + 2y^2z + z^3$.
However, the two bimaps cannot be pseudo-isometric as the former contains at least two 3-dimensional totally isotropic subspaces in $V$, and the latter contains exactly one 3-dimensional totally isotropic subspace.
In the context of $3$-groups, the corresponding groups are not isomorphic as the former contains at least two abelian subgroups of order $3^6$ where the latter contains exactly one such abelian subgroup, see \cite{Lewis:ses-groups} for a proof. \qed
\end{ex}

The multiple threes in Example~\ref{ex:same-Pfaff} are a red herring.
Instead, it illustrates a general phenomenon that happens when the genus is at least 3.
When the genus is 2, $\circ_G$ can be written as a pair of alternating forms.
Kronecker--Dieudonn\'e~\cite{Dieudonne:pairs-mats} and Scharlau \cite{Scharlau:alt-forms} classify indecomposable pairs of alternating forms.
For the (centrally indecomposable) groups coming from Theorem~\ref{thm:indecomp-genus2}(i), there exists bases for $V$ and $W$ such that $\circ_G$ is given by the pair of matrices
\[ \left\{ \begin{bmatrix} 0 & I \\ -I & 0 \end{bmatrix}, \begin{bmatrix} 0 & C \\ -C^T & 0 \end{bmatrix} \right\}, \]
where $C$ is the companion matrix of a power of an irreducible polynomial in $K[x]$.
Together with the fact that the Pfaffian of $\circ_G$ is 0 when $\dim_K(V)$ is odd, this proves the following proposition.

\begin{prop}\label{prop:primary-Pfaff}
Suppose $G$ is exponent $p$ and genus $2$ over $K$.
If $G$ is centrally indecomposable, then the ideal generated by the Pfaffian of $\circ_G:V\times V\rightarrowtail W$ is primary in $K[x,y]$.
\end{prop}

\subsection{$\GammaL(2,K)$ action on the Pfaffians}\label{sec:GL2-action}

The group $\GammaL(2,K)$ acts on polynomials $f(x,y)$ by substitution.
That is, for $M=\left(\left[\begin{smallmatrix} a & b \\ c & d \end{smallmatrix}\right], \sigma\right)\in \GL(2,K)\rtimes\Gal(K)$, set $f^M(x,y) = f^\sigma(ax+by, cx+dy)$, where $\sigma$ acts on the coefficients.
Let $f$ and $g$ be homogeneous polynomials in $x,y$.
Then $f$ is equivalent to $g$ if there exists $k\in K^\times$ and $M\in\GammaL(2,K)$ such that $f^M=k\cdot g$.
In other words, the ideals are equal, $(f^M) = (g)$.
Another perspective is to consider univariate polynomials $f\in K[x]$, with $\deg f=n$, and define
\[ f^M(x)= (cx+d)^n f^\sigma\left(\frac{ax+b}{cx+d}\right). \]
Because the Pfaffians are homogeneous, we consider both of these actions.

The $\GammaL(2,K)$-orbits have been studied by Vaughan-Lee~\cite{Vaughan-Lee:PGL-orbits} and Vishnevetski\u\i~\cite{Vishnevetskii:PGL-orbits} when $K=\mathbb{F}_p$.
We let $N(q,n)$ denote the number of $\GammaL(2, \mathbb{F}_q)$-orbits of monic irreducible polynomials of degree $n$.
One can determine the number of isoclinism classes of the centrally indecomposable groups of genus 2 (over $\mathbb{F}_p$) using \cite{Vaughan-Lee:PGL-orbits} and Theorem~\ref{thm:indecomp}.
Vaughan-Lee's Theorem enumerates the $\GL(2,p)$-orbits of all irreducible monic polynomials in $\mathbb{F}_p[x]$.
Since we do not require the full generality, we record Vaughan-Lee's Theorem for $n\leq 5$.

\begin{thm}[{\cite{Vaughan-Lee:PGL-orbits}}]\label{thm:GL2-orbits}
If $p$ is prime, then
\begin{align*}
  N(p,2) &= 1, & N(p,4) &= \frac{1}{2}\left(p + 2 - \gcd(2, p)\right), \\
  N(p,3) &= 1, & N(p,5) &= \frac{1}{5}\left( p^2 - 2 + \gcd(5,p) + 2\gcd(5, p^2-1)\right) .
\end{align*}
\end{thm}

\section{Semi-extraspecial groups of genus 2}\label{sec:ses-groups-genus2}

We describe the centrally indecomposable, semi-extraspecial groups of genus 2 based on the classification in Theorem~\ref{thm:indecomp-genus2}.
The following lemmas quickly determine which groups of genus 2 are not semi-extraspecial.

\begin{lem}\label{lem:bad-flat}
For all $m\geq 1$, the group $G=H^\flat(K, m)$ is not semi-extraspecial.
\end{lem}

\begin{proof}
As $[G:G']=p^{2m+1}$, the Pfaffian of $\circ_{G}$ is 0, so invoke Theorem~\ref{thm:Pfaffian}.
\end{proof}

In what follows, we characterize the quotients of $H(K[x]/(a(x)^c))$ that are semi-extraspecial groups.
Set $A=K[x]/(a(x)^c)$.
Theorem~\ref{thm:indecomp-genus2}(i) is only concerned with central subgroups $N$ such that $1-N$ is a $K$-subspace of $1-H(A)'$.
Therefore, for a $K$-subspace $S\leq A$, we set
\begin{equation*}
N(S) = \left\{ \begin{bmatrix} 1 & 0 & s \\ & 1 & 0 \\ & & 1 \end{bmatrix} \;\middle|\; s\in S \right\}.
\end{equation*}

\begin{prop}\label{prop:ses-quotients}
Let $a(x) \in K[x]$ be an irreducible polynomial, $c > 1$ be an integer, and $S$ a proper $K$-subspace of $A=K[x]/(a(x)^c)$.
Then $H(A)/N(S)$ is semi-extraspecial if, and only if, $A = S + (a(x)^{c-1})$ and $\deg(a(x))\geq 2$.
\end{prop}

\begin{proof}
Let $I=(a(x)^{c-1})$.
First, we suppose that $A = S + I$.
Since $A$ is a local algebra, the group of units $A^\times$ is $A\setminus (a(x))$.
It follows that every nonzero element of $A$ can be written as $ua^e$, for $u\in A^\times$ and $0\leq e\leq c-1$.
Since $S$ is a proper subspace of $A$, it follows that $\emptyset \ne A\setminus S\subseteq I$.

To show that $H(A)/N(S)$ is semi-extraspecial, it is enough to show that for every $0\ne f\in A$, and $h+S \in A/S$, there exists $g\in A$ such that $fg=h$.
Let $f=ua^e$, for some $u\in A^\times$ and $0\leq e\leq c-1$.
Without loss of generality, $h+S\in A/S$ can be written as $va^{c-1} + S$, for some $v\in A^\times$.
With $g=u^{-1}va^{c-e-1}$, we have that $fg=h$, and so $H(A)/N(S)$ is semi-extraspecial.

On the other hand, suppose $S+I \ne A$.
Let $h(x)\in A\setminus (S+I)$.
Therefore, for all $f(x)\in I$ and for all $g(x)\in A$, $fg\in I$.
In particular, $fg+S\ne h+S$, so $H(A)/N(S)$ cannot be semi-extraspecial.
\end{proof}

We summarize the above results in the following theorem to classify all indecomposable, semi-extraspecial groups of genus 2 with exponent $p$.

\begin{thm}\label{thm:genus2-ses}
Suppose $G$ is class $2$, exponent $p$, and genus $2$ over $K$.
Then $G$ is centrally indecomposable and semi-extraspecial if, and only if, there exists an irreducible polynomial $a(x)\in K[x]$ of degree $\geq 2$, a positive integer $c$, and a subspace $S\leq A := K[x]/(a(x)^c)$ with $2$-dimensional complement $\langle f,g\rangle$, such that
\begin{enumerate}
\item[$(i)$] $A = S + (a(x)^{c-1})$,
\item[$(ii)$] $A$ is an irreducible $K[f^{-1}g]$-module, and
\item[$(iii)$] $G\cong H(A) / N(S)$.
\end{enumerate}
\end{thm}

\begin{proof}
If $G$ is indecomposable and semi-extraspecial, then by Theorem~\ref{thm:indecomp-genus2} $G$ is contained in one of two (disjoint) families of genus 2 groups.
By Lemma~\ref{lem:bad-flat} property (iii) holds, and by Proposition~\ref{prop:ses-quotients}, property (i) holds.
Therefore, there exists $f,g\in A^\times$ that span a complement to $S$ in $A$.
As $G$ is indecomposable, by the proof of \cite{BMW}*{Theorem~3.18}, $A$ is an irreducible $K[f^{-1}g]$-module.

If, on the other hand, $G$ satisfies properties (i)--(iii) above, then by Proposition~\ref{prop:ses-quotients}, $G$ is semi-extraspecial.
As $\langle f, g\rangle \oplus S = A$, $\circ_G$ can be written as a pair of alternating matrices with respect to $f$ and $g$, as in Section~\ref{sec:Pfaffians}, of the form
\[ \left\{ \begin{bmatrix} 0 & M_f \\ -M_f^T & 0 \end{bmatrix}, \begin{bmatrix} 0 & M_g \\ -M_g^T & 0 \end{bmatrix} \right\}. \]
Since $G$ is semi-extraspecial, $M_f$ is invertible, so the block-diagonal matrix $M_f^{-1}\oplus I_{cd}$ induces an isometry of $\circ_G$ to an alternating bimap with $I_{cd}$ and $M_f^{-1}M_g$ in the top-right corners.
Because $A$ is an irreducible $K[f^{-1}g]$-module, it follows that the rational canonical form of $M_f^{-1}M_g$ is the companion matrix of a primary polynomial.
Thus, $G$ is indecomposable.
\end{proof}

\section{Enumerating isoclinism classes}

We use Theorems~\ref{thm:Pfaffian-bijection} and~\ref{thm:genus2-ses} to count the isoclinism classes of semi-extraspecial groups whose derived subgroup has order $p^2$.
Therefore, these groups can have genus $1$ or $2$ over $\mathbb{F}_p$.
The genus 1 case essentially follows from the classification of generalized Heisenberg groups in \cite{LW:Heisenberg}*{Theorem~3.1}.

In the next lemma, we use a consequence of Witt's Theorem \cite{Artin:Geometric-algebra}*{Chapter~3}: two alternating bilinear $K$-forms are isometric if, and only if, their radicals have the same dimension.

\begin{lem}\label{lem:genus-1}
Assume $n\geq 2$ and $q$ is a $p$-power. There are
\[ H(q,n+1) = \left\{ \begin{array}{ll} 1 & n \text{ even},\\ 0 & \text{otherwise}, \end{array}\right. \]
semi-extraspecial groups of order $q^{n+1}$ with exponent $p$ and derived subgroup of order $q$, where $\mathcal{C}(\circ_G)\cong\mathbb{F}_{q}$.
\end{lem}

\begin{proof}
Let $G$ be a group satisfying the assumptions and $K=\mathcal{C}(\circ_G)$.
As $\circ_G:V\times V\rightarrowtail W$ is $K$-bilinear and $\dim_{K}(W)=1$, it follows that $\circ_G$ is an alternating $K$-form.
By Lemma~\ref{lem:direct-decomp}, $G$ is directly indecomposable, so $\circ_G$ has trivial radical.
This leads to a contradiction if $\dim_K(V)$ is odd, so no such groups exist.
On the other hand, if $\dim_K(V)=2n$, then
\[ G \cong \left\{ \begin{bmatrix} 1 & u & w \\ & I_n & v^T \\ & & 1 \end{bmatrix} \;\middle|\; \begin{array}{c} u,v\in K^n, \\ w \in K \end{array} \right\} \leq \GL(n+2, K). \qedhere \]
\end{proof}

To prove the next theorem, we require a way to build nilpotent groups from bimaps.
Suppose $\circ : U \times V \rightarrowtail W$ is a $K$-bimap.
Then the Heisenberg group with respect to $\circ$ is the group
\[ H(\circ) = \left\{ \begin{bmatrix} 1 & u & w \\ & 1 & v \\ & & 1 \end{bmatrix} \;\middle|\; u\in U, v\in V, w\in W \right\}, \]
where the product is given by matrix multiplication using $\circ$.
Assuming $\circ$ is fully nondegenerate, the center of $H(\circ)$ equals the derived subgroup and $Z(H(\circ))\cong W$.
Moreover, the commutator bimap of $H(\circ)$ has ``doubled'' $[,]:(U\oplus V)\times (U\oplus V)\rightarrowtail W$ where
\[ \big( (u_1, v_1), (u_2, v_2) \big) \mapsto u_1\circ v_2 - u_2\circ v_1. \]
As matrices, if $\circ$ has structure constants given by the sequence $(M_i)_{i=1}^d$, then $[,]$ has structure constants of the form $\left[ \begin{smallmatrix} 0 & M_i \\ -M_i^T & 0 \end{smallmatrix} \right]$.

Recall from Section~\ref{sec:GL2-action} that $N(q,n)$ is the number of $\GammaL(2, \mathbb{F}_q)$-orbits of monic irreducible polynomials of degree $n$.
As $\GL(2, \mathbb{F}_q)$ is transitive on the nonzero vectors in $\mathbb{F}_q^2$, it follows that $N(q, 1)=1$.

\begin{thm}\label{thm:indecomp}
Suppose $n\geq 2$ and $q$ is a $p$-power.
There are $I(q, 2n+2) = -1 + \sum_{d\mid n} N(q,d)$ pairwise non-isomorphic, centrally indecomposable, semi-extraspecial groups of order $q^{2n+2}$ with exponent $p$ and genus $2$ over $\mathbb{F}_q$.
\end{thm}

\begin{proof}
First apply Theorem~\ref{thm:Pfaffian-bijection} to establish that two indecomposable genus 2 groups with exponent $p$ are isomorphic if, and only if, their Pfaffians are in the same $\GammaL(2,q)$-orbit.
By Proposition~\ref{prop:primary-Pfaff}, their Pfaffians are primary.
Let $a(x)^c=x^{cd} + a_{cd-1}x^{cd-1} + \cdots + a_0$, and assume $a(x)$ is an irreducible polynomial in $\mathbb{F}_q[x]$ and $c\geq 1$.
Let $C$ be the companion matrix of $a(x)^c$:
\[ C = \left[\begin{array}{c|c}
  \begin{array}{c} 0 \\ \vdots \\ 0 \end{array} & I_{cd-1} \\ \hline
  -a_0 & \begin{array}{ccc} -a_1 & \cdots & -a_{cd-1} \end{array} \end{array}\right]. \]
The group with commutator bimap whose structure constants are
\[ \left( \begin{bmatrix} 0 & I \\ -I & 0 \end{bmatrix}, \; \begin{bmatrix} 0 & -C \\ C^T & 0 \end{bmatrix} \right) \]
has a Pfaffian equal to $X^{cd} + a_{cd-1}X^{cd-1}Y + \cdots + a_0Y^{cd}$.
Note that this is the determinant of $IX - CY$.
Therefore, for every irreducible polynomial $a(x)$ of degree $d$ and $c\geq 1$, there exists an indecomposable $p$-group of order $q^{2cd+2}$ of genus 2 and exponent $p$ where $\Pf(\circ_G)=a(x)^c$.
By Theorem~\ref{thm:Pfaffian-bijection}, there are $N(q,d)$ isoclinism classes of this type.
By Theorem~\ref{thm:Pfaffian}, semi-extraspecial groups have no linear factors, so we require $d\geq 2$.
Thus, to get the number of isoclinism classes of indecomposable semi-extraspecial groups of order $q^{2n+2}$ that are genus 2 over $\mathbb{F}_q$, we sum over all the divisors $d$ of $n$, excluding $d=1$.
\end{proof}

\begin{thm}\label{thm:p^8}
For every prime $p$, there is exactly one isoclinism class of semi-extraspecial groups $G$ with the property that $|G|=p^8$ and $|G'|=p^2$.
\end{thm}

\begin{proof}
First, we show that $G$ must be indecomposable.
If $\{H_1,H_2\}$ is a central decomposition of $G$, then $|H_i|\in\{p^4, p^5, p^6\}$ because $[G:G']=p^6$.
From Proposition~\ref{prop:central-decomp}, $Z(H_i)=Z(G)\cong \mathbb{Z}_p^2$.
There are no genus 2 groups of order $p^4$ and by Lemma~\ref{lem:bad-flat}, the genus 2 group of order $p^5$ is not semi-extraspecial.
Therefore, $G$ is indecomposable.
By Theorems~\ref{thm:GL2-orbits} and~\ref{thm:indecomp}, there is $I(p, 8)=N(p,3)=1$ isoclinism class.
\end{proof}

\begin{remark}\label{remark:genus3}
An interesting consequence of Theorem~\ref{thm:p^8} is that every semi-extraspecial group with exponent $p$ and of order $p^9$ with $|G'|=p^3$, has exactly two non-trivial central nonabelian quotients, determined solely by the order of the factor group.
In particular, heuristics to construct characteristic subgroups via graph colorings, like in~\cite{BOW:graded-algebras}, or from algebras associated to $\circ_G$, like in \cites{M:efficient-filters,Wilson:filters}, produce no new information.
These groups may pose a formidable challenge to isomorphism testing.
\end{remark}

Are there other semi-extraspecial groups, with derived subgroup of order $p^3$, that have the property in Remark~\ref{remark:genus3}?
That is, if $N, M \leq Z(G)$ and $|N|=|M|$, then $G/N$ and $G/M$ are isoclinic.
If there are no other such groups, then what is the lower bound on the number of possible isoclinism classes of the form $G/N$, for a fixed order $|N|$?
On the other end of the spectrum, what is the upper bound?

\subsection{Proof of Theorem~\ref{main2}}

Enumerating semi-extraspecial groups of larger order is not as simple as in Theorem~\ref{thm:p^8} and will require understanding how $\GL(2,p)$ acts on (principal) ideals of \emph{reducible} polynomials.
We now focus on univariate polynomials in $\mathbb{F}_p[x]$, so we dehomogenize $\Pf(\circ_G)$ by setting $y=1$.
If $f\in \mathbb{F}_p[x]$, we let $S_f$ denote the subgroup, $\Stab_{\GL(2,p)}((f))$, stabilizing the ideal $(f)$.

The next lemma is a well-known statement coming from the (maximal) subgroup structure of $\PSL(2,p)$.
We refer the reader to Dickson \cite{Dickson}, see also Huppert \cite{Huppert} and, for historical remarks, King \cite{King}*{Theorem~2.1}.

\begin{lem}\label{lem:maximal-stab}
If $f$ is an irreducible quadratic in $\mathbb{F}_p[x]$, then $S_f\cong\GammaL(1,p^2)$.
The subgroups isomorphic to $\GammaL(1,p^2)$ in $\GL(2,p)$ are in bijection to monic irreducible quadratics in $\mathbb{F}_p[x]$.
\end{lem}

\begin{proof}
By orbit counting, $|S_f|=2(p^2-1)$.
For $\alpha\in \mathbb{F}_{p^2}$ and $M=\left[\begin{smallmatrix} a & b \\ c & d \end{smallmatrix}\right]$, if $f(x)=(x-\alpha )(x-\alpha^p)$, then
\[ f^M(x) = (a-\alpha c)(a-\alpha^pc)\left( x - \dfrac{\alpha d-b}{a-\alpha c} \right)\left( x - \dfrac{\alpha^p d-b}{a-\alpha^p c} \right) .\]
This is the inverse action on the roots of $f$, so the lemma follows.
\end{proof}

Note that the kernel of the action of $\GL(2,p)$ on polynomials is its center, so we work with $\PGL(2,p)$ instead.
In order to enumerate the isoclinism classes of semi-extraspecial groups order $p^{10}$ with derived subgroup of order $p^2$, we need to understand an action of dihedral groups in $\PGL(2,p)$.
Assuming $p$ is an odd prime, let $\Delta$ be the set of maximal dihedral subgroups of $\PGL(2,p)$ of order $2(p+1)$.
That is, $\Delta$ contains all the images of the subgroups isomorphic to $\GammaL(1,p^2)$ in $\GL(2,p)$.
Using the bijection given by Lemma~\ref{lem:maximal-stab}, a dihedral group acts on $\Delta$ in the following way.
If $D\in\Delta$ and $f$ is an irreducible quadratic associated to $D_f\in \Delta$, then for $\delta\in D$, $D_f^\delta=D_{f^\delta}$.
Therefore, for $D\in\Delta$, the $D$-orbit of $D$ is trivial.

\begin{lem}\label{lem:dihedral-orbits}
Let $p$ be an odd prime.
For a fixed $D\in\Delta$, the number of $D$-orbits on $\Delta-D$ is $(p-1)/2$.
\end{lem}

\begin{proof}
We count these orbits by counting the fixed points for every $\delta\in D$.
First note that if $1\ne\delta\in D$ is not an involution, then $N_{\PGL(2,p)}(\langle\delta\rangle)=D$.
Thus, such a $\delta$ cannot fix another dihedral group in $\Delta$, so we focus only on the involutions of $D$.

Each dihedral group in $\Delta$ intersects $\PSL(2,p)$ uniquely in a dihedral group of order $p+1$.
Let $\overline{D}=D\cap\PSL(2,p)$.
Up to conjugacy, there are two types of involutions in $D$: those contained in $\PSL(2,p)$ and those outside \cite{Steinberg:rep-PGL}*{pp.~226--227}.
Suppose $p\equiv 1$ mod $4$, so $\overline{D}$ has exactly $(p+1)/2$ involutions.
Since $|\Delta|=(p^2-p)/2$, there are $(p^2-p)(p+1)/4$ involutions coming up this way.
However, $\PSL(2,p)$ has exactly $p(p+1)/2$ involutions \cite{Dornhoff:rep-theory}*{Chapter~38}, so each involution in $\PSL(2,p)$ lies in $(p-1)/2$ dihedral subgroups of order $p+1$.
Therefore, the involutions of $\overline{D}$ stabilize $(p-3)/2$ dihedral groups in $\Delta-D$.

There are $(p+3)/2$ involutions in $D$ outside of $\PSL(2,p)$, and as many as $(p^2-p)(p+3)/4$ involutions outside of $\PSL(2,p)$.
One of these involutions, $\delta$,  lies in $Z(D)$, so its centralizer is $D$.
As there are $(p^2-p)/2$ involutions of $\PGL(2,p)$ outside of $\PSL(2,p)$ \cite{Dornhoff:rep-theory}, it follows that $\delta$ fixes $(p+3)/2-1$ other dihedral groups in $\Delta-D$.
Therefore, the number of orbits in this case is equal to
\[ \dfrac{\left(\frac{1}{2}(p^2-p)-1\right) + \left(\frac{1}{2}(p+1)\frac{1}{2}(p-3)\right) + \left(\frac{1}{2}(p+3) \frac{1}{2}(p+1)\right)}{2(p+1)} = \dfrac{p-1}{2}. \]

The case when $p\equiv 3$ mod $4$ is similar to the above case.
There is one more involution in $\PSL(2,p)$ than above, namely $\overline{D}$ contains a central involution.
The number of fixed points for these involutions follows a similar argument as above.
The argument for the involutions outside of $\PSL(2,p)$ is slightly different.
Of the $(p+1)/2$ involutions of $D$ outside of $\PSL(2,p)$, each one is contained in the center of some dihedral group of order $2(p-1)$, so its centralizer is that dihedral group.
Hence, there are $(p^2-p)/2$ such involutions, which are all of the involutions of $\PGL(2,p)$ outside $\PSL(2,p)$.
Therefore, each involution of this type is contained in $(p-1)/2$ groups in $\Delta$, and thus, fixes $(p-3)/2$ groups in $\Delta-D$.
\end{proof}

Now we are in a position to prove Theorem~\ref{main2}.

\begin{proof}[Proof of Theorem~\ref{main2}]
If $G$ is indecomposable, then apply Theorems~\ref{thm:GL2-orbits} and~\ref{thm:indecomp}, so there are
\[ I(p, 2\cdot 4+2) = N(p,4)+N(p,2)= \frac{1}{2}\left( p + 4 - \gcd(2, p)\right) \]
such isoclinism classes.
Now suppose $G$ is centrally decomposable with fully refined central decomposition $\mathcal{H}$.
From the proof of Theorem~\ref{thm:p^8}, for each $H\in\mathcal{H}$, $|H|\geq p^6$.
Because $|G|=p^{10}$, it follows that $\mathcal{H}=\{H_1,H_2\}$, where $|H_i|=p^6$.
We have two options for the centroid of $\circ_G$ from Proposition~\ref{prop:centroid-field}: $\mathcal{C}(\circ_G)$ is isomorphic to either $\mathbb{F}_p$ or $\mathbb{F}_{p^2}$.
If $\mathcal{C}(\circ_G)$ is the quadratic extension, then by Lemma~\ref{lem:genus-1}, there is exactly $H(p^2, 5)=1$ group with this property.

We suppose the centroid is the prime field.
In this case, the Pfaffian of $\circ_G$ in $\mathbb{F}_p[x,y]$ is the product of two homogeneous quadratics $f$ and $g$.
Without loss of generality, we assume that both $f$ and $g$ are monic.
If $f=g$, then $\circ_G$ is $\mathbb{F}_p[x]/(f)$-bilinear, so the centroid would be a (non-trivial) field extension, which has already been accounted for.
Therefore, $f\ne g$.
This means that, for $p=2$, there are no groups of this type because there is a unique irreducible monic quadratic.
Thus, we now assume $p>2$.
By Theorem~\ref{thm:Pfaffian-bijection}, the number of isoclinism classes of these groups is the number of $\PGL(2,p)$-orbits on the ideals generated by a product of monic irreducible quadratics.
As $\PGL(2,p)$ is transitive on monic irreducible quadratics, the number of orbits is equal to the number of orbits of one of the stabilizers, say, $\Stab_{\PGL(2,p)}((f))$.
By Lemmas~\ref{lem:maximal-stab} and~\ref{lem:dihedral-orbits}, there are exactly $(p-1)/2$ orbits.
Thus, the statement of the theorem holds.
\end{proof}

\subsection{Proof of Theorem~\ref{main3}}

Because all the monic irreducible cubics lie in one $\PGL(2,p)$-orbit, c.f.\ Theorem~\ref{thm:GL2-orbits}, it follows, again by orbit counting, that their stabilizers have order $3$ in $\PGL(2,p)$.

\begin{lem}\label{lem:Syl-3}
In $\PGL(2,p)$, if $p\equiv 2\mod 3$, then there is a bijection between the Sylow $3$-subgroups and the dihedral subgroups of order $2(p+1)$ given by inclusion.
\end{lem}

\begin{proof}
Let $D$ denote a dihedral subgroup of $G=\PGL(2,p)$ of order $2(p+1)$.
As $p\equiv 2\mod 3$, $D$ contains a Sylow $3$-subgroup, $P$.
If $x\in D$ has order $p+1$, then $P\leq \langle x\rangle$.
Because $N_{G}(\langle x\rangle) = D$, it follows that $N_{G}(P)=D$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{main3}]
In the indecomposable case, we apply Theorem~\ref{thm:indecomp}, and in the case where $G$ is genus 2 over the quadratic extension, we apply Lemma~\ref{lem:genus-1}.
By Theorem~\ref{thm:GL2-orbits}, the number of isoclinism classes is
\[ I(p, 2\cdot 5 + 2) + H(p^2, 6) = N(p,5) + 0 = \frac{1}{5} \left( p^2-2+\gcd(5,p)+2\gcd(5, p^2-1)\right). \]

Now, all we have left to do is to count the number isoclinism classes in the decomposable case where the centroid is the prime field.
By Proposition~\ref{prop:central-decomp} and Theorem~\ref{thm:genus2-ses}, a fully refined central decomposition of $G$ is $\{H_1,H_2\}$, where $|H_1|=p^6$ and $|H_2|=p^8$.
Thus, the multiset of Pfaffians contains exactly one quadratic and cubic.
Hence, the stabilizer, in $\GL(2,p)$, of the multiset is the intersection of stabilizers of a quadratic and a cubic.

By Lemma~\ref{lem:maximal-stab} the quadratic stabilizer is isomorphic to $\GammaL(1,p^2)$.
Since $N(p,3)=1$, the stabilizer of a cubic has order $3(p-1)$ as there are $(p^3-p)/3$ monic irreducible cubics in $\mathbb{F}_p[x]$.
In $\PGL(2,p)$, this is the intersection of the dihedral group of order $2p+2$ with a cyclic group of order 3.
Therefore, when $p\equiv 0,1\mod 3$, these intersections are always trivial in $\PGL(2,p)$, and the number of orbits in this case is
\[ \dfrac{\frac{1}{2}(p^2-p)\frac{1}{3}(p^3-p)}{(p^3-p)} = \dfrac{1}{6} (p^2-p). \]

When $p\equiv 2 \mod 3$, Lemma~\ref{lem:Syl-3} implies that the Sylow 3-subgroups are cyclic and so contain a unique subgroup of order 3.
As there are $(p^3-p)/3$ irreducible cubics and $(p^2-p)/2$ subgroups of order 3 in $\PGL(2,p)$, it follows that $2(p+1)/3$ cubics have identical stabilizers in $\PGL(2,p)$.
Hence, for a fixed irreducible quadratic there are $2(p+1)/3$ irreducible cubics such that their stabilizer has order 3;
for the remaining $(p^3-3p-2)/3$ cubics, their stabilizer is trivial.
Therefore, the number of orbits is given by
\[ \dfrac{\frac{1}{2}(p^2-p)\left(2(p+1) + \frac{1}{3}(p^3-3p-2)\right)}{(p^3-p)} = \dfrac{1}{6}(p^2-p+4). \qedhere\]
\end{proof}

\section*{Acknowledgements}

We thank Mikhail A.\ Chebotar and Jenya Soprunova for translating parts of \cite{Vishnevetskii:PGL-orbits}.

\end{document}

config: arxiv


TITLE: Does there exist a function satisfying this condition?
QUESTION [2 upvotes]: Does there exist a non-negative continuous function $f:[0,1]\to \Bbb R$ such that
$\int _0^1 f^n \text{dx}\to 2$ as $n\to \infty $?

I am not getting anything from here. As I was googling I found the answer
Please help me and elaborate this explanation with proper detail. I would be more  thankful. Thanks in advance for your kindness.

REPLY [2 votes]: Let me write it out fully. Suppose for a contradiction that for some continuous and non-negative $f$ we have $\int f^n \rightarrow 2$.
By definition of convergence of sequences, there is then some $N \in \mathbb{N}$ such that $n \geq N \Rightarrow \int f^n \geq 3/2$.
Suppose that $f \leq 1$ on $[0,1]$. Then $\int f^n \leq \int f$, because $f^n \leq f$. But if $f \leq 1$ we also know that $\int f \leq 1$ .
Let $n \geq N$. Then we've just shown that $\int f^n \leq 1$.
But in the previous paragraph we said that $\int f^n \geq 3/2$. This is a contradiction.
So we must have $f(x_+)  > 1+2\epsilon$ for some $x_+ \in [0,1]$ and $\epsilon > 0$.
By continuity, there is some $\delta > 0$ such that $f \geq  1+\epsilon$ on
$I_\delta:= (x_+ - \delta, x_+ + \delta) \cap [0,1]$.
Now, $$\int_{[0,1]} f^n(x)dx\geq \int_{I_\delta} f^n(x)dx \geq (1+\epsilon)^n\int_{I_\delta}dx \geq (1+\epsilon)^n \delta \rightarrow \infty,$$
as $n \rightarrow \infty$.
The first inequality uses the fact that $f$ is non-negative.
The second uses the fact that $f$ is at least $(1+\epsilon)$ on $I_\delta$.
The third uses that the length of $I_\delta$ is at least $\delta$.
We have arrived at a contradiction.


TITLE: If every convex function is of bounded variation?
QUESTION [0 upvotes]: The properties of convex functions are of interest. I would like to know that if every convex function is of bounded variation?

REPLY [1 votes]: No, take $f(x)=e^x$ on $\mathbb R$, or $g(x) = \frac1{x(1-x)}$ on $(0,1)$.


text:
\section{Preliminaries}
\label{sec:model}

In this section we introduce the basic formal framework we employ throughout the paper.  We develop the relevant notation to describe two distinct Markov chains on a common state space, as well as the design of adaptive experiments to compare the long-run average reward of these two chains.

{\bf Notation.} As is common in analysis of finite Markov chains, we view distributions as row vectors and reward vectors as column vectors as appropriate.  In addition, we use ``$\xrightarrow{p}$" to denote convergence in probability, and ``$\Rightarrow$'' to denote weak convergence of random variables.

{\bf Time.}  We assume time is discrete, and indexed by $n = 0, 1, 2, \ldots$.

{\bf State space}.  We assume a finite state space $S$.

{\bf Two Markov chains}.  We wish to compare two different Markov chains indexed by $\ell = 1,2$ evolving on this common state space, defined by transition matrices
\begin{align}
    P(\ell)=(P(\ell,x,y): x,y\in S), \quad \ell=1,2.
\end{align}
We assume both $P(1)$ and $P(2)$ are {\em irreducible}.

{\bf Auxiliary randomness}.  We require two sources of randomness beyond the Markov chains themselves: one that is used to generate random rewards, and the other that is used to allow experimental designs to be randomized.  Accordingly, we presume the existence of mutually independent sequences of i.i.d.~uniform$[0,1]$ random variables $U_0, U_1, \ldots,$ and $V_0, V_1, \ldots$.

{\bf Sample space and filtration}.  The sample space is $\Omega=(S\times [0,1]^2)^\infty$, with $\omega \in \Omega$ written as $\omega = ( (x_n, u_n, v_n), n \geq 0)$.  For $n\ge 0$, set $X_n(\omega)=x_n$ and $U_n(\omega)=u_n$, $V_n(\omega)=v_n$.  We define the filtration $\mathcal{G}_n=\sigma\big((X_j, U_j, V_j): 0\le j\leq n\big)$ for $n\ge 0$.  We also let $\mathcal{G}_\infty = \sigma\big((X_j, U_j, V_j): j \geq 0\big)$.

{\bf Policies (experiment designs)}.  A sequence of random variables $A=(A_n: n\ge 0)$ is said to be a {\em policy} if $A_n\in \{1,2\}$ for $n\ge 0$, and $A$ is adapted to $(\mathcal{G}_n:n\ge 0)$.  A policy is also an {\em experimental design}: it determines how the experimenter chooses which chain to run at each time step.\footnote{In general, the experimenter may commit in advance to a time horizon $N$ of interest, and the experimenter may use this knowledge in design of their policy.  In what we study here, for ease of presentation, we presume that the policy is defined for all $n \geq 0$.  In the fixed horizon setting, our results can be extended in a straightforward manner to characterize consistency and variance as $N \to \infty$ under appropriate regularity conditions.}

Note that every policy induces a probability measure on $(\Omega, \mathcal{G}_\infty)$; this probability measure has conditional distributions defined as follows, for Borel subsets $A,B \subset [0,1]$ and with Lebesgue measure denoted $\mu$:
\[ P(X_{n+1} = x, U_{n+1} \in A, V_{n+1} \in B | \mathcal{G}_n) = P(A_n, X_n, y) \mu(A) \mu(B). \]

{\bf Rewards}.  When chain $\ell$ is in state $x$ and transitions to state $y$, a random reward is obtained, independent of the past.  Formally, denote the cumulative distribution function of the reward by  $F(\cdot|\ell, x, y)$. Then the reward at time $n\ge 0$ is:
\begin{align}
    R_n=F^{-1}(V_n | A_{n-1}, X_{n-1}, X_n).
\end{align}

For technical simplicity, we assume that the support of $F$ is {\em bounded}, i.e., that rewards are bounded in magnitude.

{\bf Stationary distributions}.  Because $S$ is finite and the two matrices $P(1)$ and $P(2)$ are irreducible, there exist unique stationary distributions $\pi(\ell)=(\pi(\ell,x): x\in S), \ell=1,2$ satisfying
\begin{gather}
    \pi(\ell) =\pi(\ell)P(\ell);\\
    \pi(\ell,x)\ge 0, x\in S;\\
    \sum_{x\in S} \pi(\ell,x)=1.
\end{gather}

{\bf Long-run average reward}.  For $\ell = 1,2$, $x \in S$, define:
\begin{align}
    r(\ell,x)=\mathbb{E}\big\{R_{n+1}|X_n=x, A_n=\ell\big\}=\sum_{y\in S} P(\ell,x,y) \int_{\mathbb{R}} z F(dz|\ell,x,y).
\end{align}
Now define:
\[ \alpha(\ell)=\sum_{x \in S} \pi(\ell,x)r(\ell,x), \ell = 1,2. \]
This is the stationary average reward of chain $\ell$.  By the ergodic theorem for Markov chains, this is also the long-run average reward associated to chain $\ell$.

{\bf Treatment effect}.  We are interested in the difference in long run average rewards between the two chains, i.e., $\alpha = \alpha(2) - \alpha(1)$.  This is the {\em treatment effect}.

{\bf Estimators}.  An {\em estimator} is a sequence of real-valued random variables $\hat{\alpha}=(\hat{\alpha}_n: n\ge 0)$ that is adapted to $(\mathcal{G}_n:n\ge 0)$.

Our goal is to design a combination of a policy $A$ and an estimator $\hat{\alpha}$ to estimate $\alpha=\alpha(2)-\alpha(1)$ {\em consistently} and {\em efficiently}, in senses that we make precise in the subsequent development.


TITLE: Basic Algebraic Applications of Stationary Sets?
QUESTION [9 upvotes]: Background:  I've been working my way through Thomas Jech's "Set Theory" because I'm working on some problems that have the potential to be logically independent of the usual axioms, or at least involve some hard set-theory about infinite sets, and I want to (eventually) better understand some of the set-theoretical techniques and methods that can be used to show such independence.
The first seven chapters of Jech's book have clear applications in my field of expertise, ring theory.  I was already quite familiar with much of the material because of this fact.
Chapter 1: The basic axioms of set theory are used all the time in the language of ring theory, allowing for the formation of simple objects like unions, products, sequences, etc.
Chapter 2: The ordinal numbers have applications in infinitary constructions, and anywhere induction can be pushed further.  For instance, one can define the "higher Wedderburn radicals" as a transfinite sequence of ideals which eventually stabilize at the prime radical.
Chapter 3: Everyone is familiar with how cardinal numbers give a very easy way to determine whether two objects are the same size, which helps prevent the existence of isomorphisms.  Thus, this is a sort of first check one does to prove non-isomorphisms.  There are other uses.
Chapter 4: Real numbers are a ring, with lots of interesting properties.  What more needs to be said?
Chapter 5: The axiom of choice turns into Zorn's lemma.  Using it you can prove all sorts of neat facts about existence of maximal ideals, algebraic closures, etc.
Chapter 6: Well-foundedness of relations comes up when trying to force processes to stop.  One application I'm familiar with is in generalizing power series rings to allow for more products, but still requiring a "bottom" so that multiplication is well-defined.
Chapter 7: Boolean algebras, not much needs to be said here.
However, I'm just not familiar with any immediate uses of stationary sets in ring theory.  This bothers me because (1) they seem quite useful in set theory, and (2) Jensen's Diamond, which settled the Whitehead problem (and was one reason I jumped into this current project) is stated in terms of stationary sets.
So, here is my formal question.
Question: What basic applications do stationary sets (in and of themselves, without appealing to axioms independent of ZFC) have in algebra?  If applications to ring theory specifically could be provided, that would be even better.

REPLY [4 votes]: In his old paper on the Whitehead problem, Shelah proves that if $p$ is a prime number, $\kappa$ is uncountable regular, then there are $2^\kappa$ Abelian $p$-groups of cardinality $\kappa$, with no element of infinite height, none of them isomorphic to a subgroup to the other. This was a problem of Fuchs.


TITLE: Damped Coupled Oscillations
QUESTION [2 upvotes]: I'm currently revising for a vibrations and waves module that I am taking as part of my physics degree.
One of the our final questions involved finding equations for the displacements of the two masses in this system as a superposition of their normal modes:

I found the equations of motion for each mass to be:
$$ \ddot{x_a} + \gamma\dot{x_a} + x_a(\omega_0^2+\omega_s^2) = x_b\omega_s^2\\\ddot{x_b} + \gamma\dot{x_b} + x_b(\omega_0^2+\omega_s^2) = x_a\omega_s^2\\Here: \omega_0^2 = \frac{g}{l}~~\omega_s^2=\frac{k}{m}~~\gamma=\frac{b}{m}$$ Here I let $ q_1 = x_a+x_b~and~q_2 = x_a-x_b: $ $$\ddot{q_1} + \gamma\dot{q_1} + q_1\omega_0^2=0\\\ddot{q_2} + \gamma\dot{q_2} + q_2(\omega_0^2+2\omega_s^2)=0 $$ From here I can't see where to go. I did attempt substituting in a general solution such as $q_1 = C_1 \cos(\omega t)$ but I get a mixture of sines and cosines and I can't solve it for anything useful.
Any help would be great as this is the last topic that I need to learn! Thanks, Sean.

REPLY [2 votes]: The problem boils down to solving a linear system of (first order) differential equations. I suppose you have not had this topic in your math classes yet, so I will not delve into the intricacies. You did the transformation from x and y variables to qs, and now you seem to have what is essentially two uncoupled damped oscillators. I would imagine that you have had the general solution to these explained in your classes. See Wikipedia for the formulae in case you have not: linear differential equations and damping.

REPLY [1 votes]: The oscillations are damped. You need to have a sine/cosine times a trig function with a non imaginary exponential. This should get you where you need to go.


text:
\begin{document}

\begin{abstract}
We give a new proof of the duality of multiple zeta values,
which makes no use of the iterated integrals.
The same method is also applicable to Ohno's relation
for ($q$-)multiple zeta values.
\end{abstract}

\maketitle

\section{Introduction}
We call a tuple of positive integers $\boldsymbol{k}=(k_1, \dots, k_r)$
an \emph{index} and
define its \emph{weight} $\mathrm{wt}(\boldsymbol{k})$ to be $k_1+\cdots+k_r$.
An index $\boldsymbol{k}$ is called \emph{admissible} when $k_r \geq 2$.
For an admissible index $\boldsymbol{k}$, the \emph{multiple zeta value}
$\zeta(\boldsymbol{k})$ is defined as a convergent series
\[
\zeta(\boldsymbol{k}):=\sum_{0 < m_1 < \cdots < m_r}\frac{1}{m_1^{k_1}\cdots m_r^{k_r}}.
\]
Given an admissible index $\boldsymbol{k}$, we write it in the form
\[
\boldsymbol{k}=(\{1\}^{a_1-1}, b_1+1, \dots, \{1\}^{a_s-1}, b_s+1),
\]
where $a_1, \dots, a_s, b_1, \dots, b_s$ are positive integers
and $\{1\}^a$ means $1,\ldots,1$ repeated $a$ times,
and then define its \emph{dual index} $\boldsymbol{k}^{\dagger}$ by
\[
\boldsymbol{k}^{\dagger}=(\{1\}^{b_s-1}, a_s+1, \dots, \{1\}^{b_1-1}, a_1+1).
\]
The following relation is one of the most famous relations among
multiple zeta values.

\begin{theorem}[Duality]
Let $\boldsymbol{k}$ be an admissible index and $\boldsymbol{k}^{\dagger}$ its dual.
Then we have
\[
\zeta(\boldsymbol{k})=\zeta(\boldsymbol{k}^{\dagger}).
\]
\end{theorem}

The duality, conjectured by Hoffman \cite{H},
was proved by making change of variables in the iterated integral representation
of the multiple zeta value (see Zagier \cite{Z}).
In this note, we give a new proof of the duality without using iterated integrals.
The proof is described briefly as follows.
We introduce the \emph{connected sum}
\begin{equation}\label{eq:Z(k;l)}
Z(\boldsymbol{k}; \boldsymbol{l}):=
\sum_{\substack{0=m_0<m_1<\cdots<m_r \\ 0=n_0<n_1<\cdots<n_s}}
\prod_{i=1}^r\frac{1}{m_i^{k_i}}\prod_{j=1}^s\frac{1}{n_j^{l_j}}
\cdot\frac{m_r!\cdot n_s!}{(m_r+n_s)!}
\end{equation}
for indices $\boldsymbol{k}=(k_1, \dots, k_r)$ and $\boldsymbol{l}=(l_1, \dots, l_s)$
(the name ``connected sum'' means that the two series
\[\sum_{0=m_0<m_1<\cdots<m_r}\prod_{i=1}^r\frac{1}{m_i^{k_i}}
\quad \text{and} \quad
\sum_{0=n_0<n_1<\cdots<n_s}\prod_{j=1}^s\frac{1}{n_j^{l_j}}
\]
are connected by the factor $\frac{m_r!\cdot n_s!}{(m_r+n_s)!}$;
it is not related to the notion of the same name in topology).
Then, by using an identity
\[
\sum_{a=m+1}^{\infty}\frac{1}{a}\cdot\frac{a!\cdot n!}{(a+n)!}
=\frac{1}{n}\cdot\frac{m!\cdot n!}{(m+n)!}
\]
$\mathrm{wt}(\boldsymbol{k})$ times,
we see that $\zeta(\boldsymbol{k})=Z(\boldsymbol{k}; \varnothing)$ is equal to
$Z(\varnothing; \boldsymbol{k}^{\dagger})=\zeta(\boldsymbol{k}^{\dagger})$,
where $a$ and $n$ are positive integers and $m$ is a non-negative integer.
For example, Euler's relation $\zeta(1, 2)=\zeta(3)$ which is the simplest
non-trivial case of the duality is proved through the following steps:
\begin{alignat*}{3}
\zeta(1,2)&=\sum_{0<m_1<m_2}\frac{1}{m_1m_2^2}&\quad &=Z(1,2; \varnothing)\\
&=\sum_{0<m_1<m_2}\sum_{n=1}^{\infty}\frac{1}{m_1m_2}\cdot\frac{1}{n}\cdot\frac{m_2!\cdot n!}{(m_2+n)!}&\quad &=Z(1,1; 1) \\
&=\sum_{m_1=1}^{\infty}\sum_{n=1}^{\infty}\frac{1}{m_1}\cdot\frac{1}{n^2}\cdot\frac{m_1!\cdot n!}{(m_1+n)!}&\quad &=Z(1; 2) \\
&=\sum_{n=1}^{\infty}\frac{1}{n^3}&\quad &=Z(\varnothing; 3)\quad =\zeta(3).
\end{alignat*}
By the same argument, we can obtain new proofs of Ohno's relation \cite{O}
and its $q$-analog due to Bradley \cite{B}.
To recall the statements, we introduce some notation.
Let $q$ be a real number satisfying $0<q<1$.
For an admissible index $\boldsymbol{k}=(k_1, \dots, k_r)$, we define the \emph{$q$-multiple zeta value}
$\zeta_q(\boldsymbol{k})$ by
\[
\zeta_q(\boldsymbol{k}):=\sum_{0 < m_1 < \cdots < m_r}
\frac{q^{(k_1-1)m_1+\cdots+(k_r-1)m_r}}{[m_1]_q^{k_1}\cdots [m_r]_q^{k_r}},
\]
where the $q$-integer $[m]_q$ is defined to be $\frac{1-q^m}{1-q}$
for a positive integer $m$.
Then we have $\lim_{q \to 1}\zeta_q(\boldsymbol{k})=\zeta(\boldsymbol{k})$.
For a non-negative integer $c$ and an admissible index $\boldsymbol{k}=(k_1, \dots, k_r)$,
we consider a linear combination of $q$-multiple zeta values
\[
S_q(\boldsymbol{k};c) :=
\sum_{\substack{c_1+\cdots+c_r=c \\ c_i \geq 0}}\zeta_q(k_1+c_1, \dots, k_r+c_r).
\]
Then the $q$-analog of Ohno's relation is the following:
\begin{theorem}[{Bradley \cite[Theorem 5]{B}}]\label{mainthm}
Let $c$ be a non-negative integer,
$\boldsymbol{k}$ an admissible index and
$\boldsymbol{k}^{\dagger}$ its dual.
Then
\[
S_q(\boldsymbol{k};c) = S_q(\boldsymbol{k}^{\dagger};c).
\]
\end{theorem}
By taking the limit $q \to 1$, one obtains Ohno's relation.
The duality is the case $c=0$ of Ohno's relation.

\section{New proof of Theorem \ref{mainthm}}
\begin{definition}[Connected sum]
Let $\boldsymbol{k}=(k_1, \dots, k_r)$ and $\boldsymbol{l}=(l_1, \dots, l_s)$ be
(possibly non-admissible or empty) indices and let $x$ be a real number satisfying $\lvert x\rvert<1$.
We define a series $Z_q(\boldsymbol{k}; \boldsymbol{l}; x)$ by
\begin{align*}
Z_q(\boldsymbol{k}; \boldsymbol{l}; x)
:=\sum_{\substack{0=m_0<m_1<\cdots<m_r \\ 0=n_0<n_1<\cdots<n_s}}
&\prod_{i=1}^r\frac{q^{(k_i-1)m_i}}{([m_i]_q-q^{m_i}x)[m_i]_q^{k_i-1}}
\prod_{j=1}^s\frac{q^{(l_j-1)n_j}}{([n_j]_q-q^{n_j}x)[n_j]_q^{l_j-1}}\\
&\cdot\frac{q^{m_rn_s}f_q(m_r;x)f_q(n_s;x)}{f_q(m_r+n_s;x)},
\end{align*}
where $f_q(m;x)=\prod_{h=1}^m([h]_q-q^hx)$ for a non-negative integer $m$.
Since this is a non-empty series of positive terms,
its value is well-defined as a positive real number (if convergent) or
as positive infinity $+\infty$ (if divergent), independently of the order of the terms.
\end{definition}

Note that there is a symmetry
$Z_q(\boldsymbol{k}; \boldsymbol{l};x)=Z_q(\boldsymbol{l}; \boldsymbol{k};x)$.
We also remark that, letting $q\to 1$ and $x\to 0$,
we recover the series $Z(\boldsymbol{k};\boldsymbol{l})$ defined in \eqref{eq:Z(k;l)}.

\begin{theorem}\label{key-thm}
Let $r$ and $s$ be non-negative integers and $k_1, \dots, k_r$, $l_1, \dots, l_s$
positive integers. If $s>0$, then we have
\[
Z_q(k_1, \dots, k_r, 1; l_1, \dots, l_s;x)=Z_q(k_1, \dots, k_r; l_1, \dots, l_s+1;x),
\]
and if $r>0$, then we have
\[
Z_q(k_1, \dots, k_r+1; l_1, \dots, l_s;x)=Z_q(k_1, \dots, k_r; l_1, \dots, l_s, 1;x).
\]
\end{theorem}
\begin{proof}
The first equality follows from the telescoping sum
\begin{align*}
&\sum_{a>m}\frac{1}{[a]_q-q^ax}\cdot\frac{q^{an}f_q(a;x)f_q(n;x)}{f_q(a+n;x)}\\
&=\frac{q^n}{[n]_q}\sum_{a>m}
\Biggl(\frac{q^{(a-1)n}f_q(a-1;x)f_q(n;x)}{f_q(a-1+n;x)}
-\frac{q^{an}f_q(a;x)f_q(n;x)}{f_q(a+n;x)}\Biggr) \\
&=\frac{q^n}{[n]_q}\cdot\frac{q^{mn}f_q(m;x)f_q(n;x)}{f_q(m+n;x)},
\end{align*}
applied to $m=m_r$, $n=n_s$ and $a=m_{r+1}$ in the definition of
$Z_q(k_1, \dots, k_r, 1; l_1, \dots, l_s;x)$.
The second equality is equivalent to the first by the symmetry of $Z_q$.
\end{proof}

\begin{corollary}
For an admissible index $\boldsymbol{k}$, put
\[
Z_q(\boldsymbol{k}; x):=\sum_{0<m_1<\cdots<m_r}\prod_{i=1}^r\frac{q^{(k_i-1)m_i}}{([m_i]_q-q^{m_i}x)[m_i]_q^{k_i-1}}.
\]
This is convergent, and we have
\begin{equation}
Z_q(\boldsymbol{k}; x)=Z_q(\boldsymbol{k}^{\dagger}; x).
\label{x-duality}\end{equation}
\end{corollary}
\begin{proof}
When $0<x<1$, we have $\frac{1}{[m]_q-q^m x}\leq\frac{1}{1-x}\cdot\frac{1}{[m]_q}$ and hence
\[Z_q(\boldsymbol{k}; x)\leq \biggl(\frac{1}{1-x}\biggr)^r \zeta_q(\boldsymbol{k})<+\infty. \]
When $x\leq 0$, we readily see that $Z_q(\boldsymbol{k}; x) \leq \zeta_q(\boldsymbol{k})<+\infty$.
Thus $Z_q(\boldsymbol{k}; x)$ is convergent.
Moreover,
by applying equalities in Theorem \ref{key-thm} $\mathrm{wt}(\boldsymbol{k})$ times,
we see that
\[
Z_q(\boldsymbol{k};x)
=Z_q(\boldsymbol{k}; \varnothing;x)=\cdots
=Z_q(\varnothing; \boldsymbol{k}^{\dagger};x)
=Z_q(\boldsymbol{k}^{\dagger};x)
\]
holds by the definitions of $Z_q(\boldsymbol{k}; x)$ and the dual index.
\end{proof}

\begin{proof}[Proof of Theorem {\upshape\ref{mainthm}}]
Let us expand $Z_q(\boldsymbol{k};x)$ into a power series
with respect to $x$.
First, fix a sequence $0<m_1<\cdots<m_r$ and $i=1,\ldots,r$. Then one has
\[
\frac{q^{(k_i-1)m_i}}{([m_i]_q-q^{m_i}x)[m_i]_q^{k_i-1}}=q^{(k_i-1)m_i}\sum_{c_i=0}^\infty\frac{q^{c_im_i}x^{c_i}}{[m_i]_q^{c_i+1}}\cdot\frac{1}{[m_i]_q^{k_i-1}}=\sum_{c_i=0}^{\infty}\frac{q^{(k_i+c_i-1)m_i}}{[m_i]_q^{k_i+c_i}}x^{c_i}.
\]
Taking the sum of products $\sum_{0<m_1<\cdots<m_r}\prod_{i=1}^r$
of this equality, we see that
\[Z_q(\boldsymbol{k};x)=\sum_{c=0}^\infty
S_q(\boldsymbol{k};c)x^c. \]
Hence, we get $S_q(\boldsymbol{k};c)=S_q(\boldsymbol{k}^{\dagger};c)$
by comparing the coefficients of $x^c$ in \eqref{x-duality}.
\end{proof}

\begin{rem}
When $q=1$ and $\boldsymbol{k}=(\{1\}^{r-1},2)$, our generating series
$Z_q(\boldsymbol{k};x)$ becomes
\[Z_1(\{1\}^{r-1},2;x)=\sum_{0<m_1<\cdots<m_r}
\frac{1}{(m_1-x)\cdots(m_r-x)m_r}. \]
Essentially the same series appears in the beginning of
Granville's proof of the sum formula \cite{G}.
We note that, however, our argument specialized to this case
gives another proof of the sum formula:
\begin{align*}
Z_1(\{1\}^{r-1},2;x)&=Z_1(\{1\}^{r-1},2;\varnothing;x)
=Z_1(\{1\}^{r};1;x)=\cdots\\
&=Z_1(\{1\}^{r-j};j+1;x)=\cdots=Z_1(\varnothing;r+1;x)=Z_1(r+1;x).
\end{align*}
Here the connected sums $Z_1(\{1\}^{r-j};j+1;x)$ are the new ingredients.
\end{rem}

\section*{Acknowledgement}
The authors sincerely thank the referee for helpful comments to improve the exposition.


TITLE: Line integral along an implicit curve and dirac distibution
QUESTION [1 upvotes]: Let $\varphi  :  \Bbb{R}^2 \rightarrow \Bbb{R}$ defining an implicite curve $C = \{ (x,y), \varphi(x,y) = 0 \}$, and $u : \Bbb{R}^2 : \rightarrow  \Bbb{R}$
Does the line integral $\int_C u(x,y)\ dC$ exists ?
And if it exist, is there a way to write it :
$ \int_C u(x,y) \  dC = \int_{\Bbb{R}^2}f(x,y,\varphi,\varphi')\ dxdy \  $ ? (to apply Euler-Lagrange equation)
I thought of something like $ \int_{\Bbb{R}^2}u(x,y).\delta_0(\varphi(x,y))\ dxdy \  $ ($\delta_0$ the dirac distribution), as $\delta_0 \circ \varphi $ is like the indicator function of C. But i guess this formula isn't true ?

REPLY [1 votes]: Does the line integral $\int_C u(x,y)\ dC$ exists?

If $C$ is a rectifiable curve, then yes. Note that for a general smooth function $\varphi$ the zero set $\varphi=0$ can be quite horrible: it can be an arbitrary closed subset of $\mathbb R^2$. But if you assume that $\nabla \varphi\ne 0$ on $C$, then the implicit function theorem implies that $C$ is a smooth curve.

Is there a way to write it:
  $\int_C u(x,y) \  dC = \int_{\Bbb{R}^2}f(x,y,\varphi,\varphi')\ dxdy $

Not really, but you can approximate it by integrals of that kind. The formal tool is the coarea formula but the basic idea is to integrate $u$ over $\epsilon$-neighborhood of the curve (using the Lebesgue measure), divide by $2\epsilon$, and take the limit $\epsilon\to 0$. The problem is, it's difficult to express the $\epsilon$-neighborhood of $C$ in terms of $\varphi$. It is easier to take the region between two level sets $\varphi = \pm \epsilon$ as an approximation to $C$, but this region has variable width. The width is roughly $\epsilon |\nabla \varphi|^{-1}$. To offset this, we integrate not $u$  itself, but the product $u   |\nabla \varphi|$. This works:
$$\int_C u \,dC = \lim_{\epsilon\to 0} \frac{1}{2\epsilon}\iint_{\mathbb R^2}u   |\nabla \varphi| \chi_{ \{|\varphi|<\epsilon \} }$$

(to apply Euler-Lagrange equation)

If my guess is right, this will not do you any good. Please don't think that by formal manipulations you can mask the fact that you have a variational problem with free boundary $C$. These are delicate problems that require tools of both analysis and geometric measure theory. Use variations, of course, but make them geometric variations: move $C$ along its normal vector field, etc.


TITLE: How to determine a sample size to get accurate estimates of a given data set?
QUESTION [2 upvotes]: I have a question with a statistical nature; I think there should be some standard theory about this issue.
Suppose I have a large data set of size $N$ items, which has an amount of $K<N$ unwanted items. I am interested in finding the value of $K$. Testing all items takes too much time, so I want to determine a suitable sample size $n<N$ of randomly selected items in the data set.
Suppose I just pick a value for $n$
Then, of a randomly sample data of size $n$, I search for the unwanted items of which there are some amount of $k\leq n$. Let this amount be a test statistic $T$, i.e. I will test on the probability $P(T \geq k)$. I can now find a smallest integer value $K_\min$ such that for the estimation $K = K_\min$ we have $P(T \geq k) \geq \alpha$. That is, for any smaller integer estimation $K<K_\min$ we have $P(T \geq k) < \alpha$. If I am correct, I can now state that with a significance level $\alpha$ we have that $K \geq K_\min$. Is that true?
If this is true, the question now is: How accurate is this lower bound?
This is also my main question. Based on the amount $n$ and accuracy level $\alpha$, what can we say about the accuracy of $K_\min$. In other words, can we determine some confidence interval on $K$ in relationship to $K_\min$ and $\alpha$?
Any tips or other approaches are very much appreciated!
Best,
Koen
Edit 26 November:
Another formulation of the problem as mentioned by David K is as follows:
Given some "error" tolerance $\varepsilon$, how do we choose $n$ for a given $\alpha$ such that we can guarantee that $|K_\min−K|/N\leq \varepsilon$ (or some assurance like that)?

REPLY [2 votes]: I suppose that when you compute $P(T \geq k),$ you have in mind a
probability distribution of $T$ based on sampling $n$ items
from $N$ of which $K$ are "unwanted".
A hypergeometric distribution seems to fit the requirements.
In that light, I agree completely with your paragraph between
"Suppose I just pick a value" and "If this is true".
It seems to me that then $K > K_\min$ is your confidence interval,
that is, you have a one-sided confidence interval for $K$
whose lower bound is $K_\min.$


TITLE: Solving the matrix equation $B = ABA^T + C$ for $B$
QUESTION [2 upvotes]: I have the equation
$$B = ABA^T + C$$
where $A$, $B$, and $C$ are all square matrices. For simplicity, we can assume anything we want to be invertible is invertible.
I would like to be able to solve for $B$ in terms of just $A$ and $C$, but I can't see any way to simplify this. The only thing I can think to do is to move all the $B$ terms to the same side and try to left-multiply and/or right-multiply by a suitable matrix to isolate $B$, but I haven't been successful at this. Does anyone have any ideas as to how (and if) we can isolate $B$ in this expression somehow?

REPLY [5 votes]: Let $n$ be the common size of all square matrices. Using the vectorization operator, we have
$$
B = ABA^T + C \implies\\
B - ABA^T = C \implies\\
\operatorname{vec}(B) - (A \otimes A)\operatorname{vec}(B) = \operatorname{vec}(C) \implies\\
(I - A \otimes A)\operatorname{vec}(B) = \operatorname{vec}(C) \implies\\
\operatorname{vec}(B) = (I - A \otimes A)^{-1}\operatorname{vec}(C).
$$
Here, $I$ denotes the $n^2 \times n^2$ identity matrix, and $\otimes$ denotes the Kronecker product.
As it turns out, the matrix $(I - A \otimes A)$ is invertible (which means that our equation will necessarily have a unique solution) if and only if there is no $\lambda$ for which both $\lambda$ and $1/\lambda$ are eigenvalues of $A$.


TITLE: If $x \not= 0$ and $\lambda x = 0$, then $\lambda = 0$.
QUESTION [0 upvotes]: I am trying to use the definition of vector spaces to prove that, if $x \not= 0$ and $\lambda x = 0$, then $\lambda = 0$.
Expressing the proposition differently, it seems to me that it is saying the following: If $x \not= 0$ and $\lambda x = 0$, then there exists some $\lambda \in E$ such that $\lambda x = 0$.
Let $x \not= 0$ and $\lambda x = 0$, where $x, \lambda \in E$.
Therefore, by the definition of vector spaces, there exists some $w \in E$ such that $x + \lambda = w$.
Since $x, w \in E$, let $w = x$ (that is, we select $w$ to be equal to $x$).
$\therefore x + \lambda = w \Rightarrow \lambda = w - x = 0 \ \ \ Q.E.D.$
I would greatly appreciate it if people would please take the time to clarify whether or not this is correct.

REPLY [0 votes]: Lemma: For the vector $0$ and any scalar $\lambda$ we have $\lambda 0 = 0$:
Define $z=\lambda 0$, then

$z=\lambda 0 = \lambda(0+0)$ (as $0= 0+0$ in the vector space)
distributivity tells us $\lambda(0+0)=\lambda 0 + \lambda 0  =z +z$.
combining we get $z = z+z$.
Then add $-z$ to both sides to get $0 = (z + (-z)) = (z+ z) + (-z)$.
now, associativity for the right hand side gives us $0 = z + (z + (-z)) = z + 0 = z$.
So $z=0 = \lambda 0$ and we're done.

Knowing that, suppose $\lambda x = 0$ for some $\lambda$ and $x \neq 0$.
Now assume $\lambda \neq 0$ so that $\lambda^{-1}$ exists (as a scalar) such that $\lambda^{-1} \lambda=1$ (here we use that scalars are a field).
Then:

$x = 1 x$ (axiom) so that:
$x = (\lambda^{-1} \lambda)x$, using another axiom we get
$x= \lambda^{-1}(\lambda x) = \lambda^{-1} 0 = 0$, where we substitute $\lambda x = 0$ and use the previous lemma for the scalar $\lambda^{-1}$.

So $x=0$, contradiction with $x \neq 0$, so the assumption $\lambda \neq 0$ was wrong and $\lambda = 0$. QED.


TITLE: $n^3 \equiv n^5 \pmod{12} $?
QUESTION [7 upvotes]: I am proving that
$$5n^3 + 7n^5 \equiv 0 \pmod{12}$$
It would suffice to show
$$n^3 \equiv n^5 \pmod{12}$$
How would I go about doing that?
I suppose I could just go through each $n \equiv r \pmod{12}$ with $r$ from $1$ to $11$ and show that $n^3 \equiv n^5 \pmod{12}$ for each, but that would be tedious.  Surely there's a better way.

REPLY [1 votes]: $$\begin{align}n^5-n^3&=(n-2)(n-1)n(n+1)(n+2)-4n^3+4n\\\\
&=(n-2)(n-1)n(n+1)(n+2)-4(n-1)n(n+1)\end{align}$$
The first expression is a product of 5 consecutive numbers, hence is divisible by $5!$ i.e., by 120. Similarly, the second expression is divisible by $4\cdot (3!)$ i.e., by 24.
Also, $n^5-n^3 = n^2(n-1)n(n+1)$. Clearly, a product of 3 consecutive numbers $(n-1)n(n+1)$ is divisible by 3.
Again, $n^5-n^3 = n^3(n^2-1)$.
If $n$ is even, the R.H.S. is divisible by 8.
If $n$ is odd (equals to $2m+1$, say), then $$n^2-1 = (2m+1)^2 - 1 = 8m(m+1)/2$$ i.e, is divisible by 8 (See If $n$ is an odd natural number, then $8$ divides $n^{2}-1$).


TITLE: Prove by double induction on $m,n$ that $(m+1)^n>mn\,\forall m,n\ge0.$
QUESTION [2 upvotes]: Prove by double induction on $m,n$ that $(m+1)^n>mn\,\forall m,n\ge0.$

Here is what I got so far.
Induction on $m$.
Base step: $m=0.\\
(0+1)^n>0n, \forall n\ge0.\\
(0+1)^n=1^n=1>0n=0, \forall n\ge0.$
Inductive step: $(m+1+1)^n>(m+1)n, \forall n\ge0.$
Induction on $n.$
Base step: $n=0\\
(m+1+1)^0\stackrel{m\ge0}=1>(m+1)0=0$
Inductive step: $(m+1+1)^{n+1}>(m+1)(n+1), \forall n\ge0.\\
(m+1+1)^{n+1}=(m+1+1)^n(m+1+1)\stackrel{\text{Inductive Hypothesis:}}>(m+1+1)^n>(m+1)n\\
>(m+1)n(m+1+1)$
I have not managed to go beyond that.
Any help will be appreciated.

REPLY [1 votes]: Fix $m$. From the base case $n=0$, assume that $(m+1)^n>mn$ holds for some $n\in\Bbb N$. Then for the inductive step of $n+1$, we have $$(m+1)^{n+1}=(m+1)(m+1)^n>(m+1)mn>m(n+1)\impliedby m+1>1+\frac1n$$ which is true for all $m>0$. When $m=0$, we have $(0+1)^n>0\cdot n$ which is also true, so induction on $n$ is complete.
Fix $n$. From the bases case $m=0$, assume that $(m+1)^n>mn$ holds for some $m\in\Bbb N$. Then for the inductive step of $m+1$, we have \begin{align}(m+1+1)^n&=(m+1)^n+\binom n1(m+1)^{n-1}+\cdots+\binom n{n-1}(m+1)+1\\&>mn+n(m+1)^{n-1}+\cdots+n(m+1)+1\\&=(m+1)n+n(m+1)^{n-1}+\cdots+n+1>(m+1)n\end{align} which is true for all $n\ge0$. Induction on $m$ is complete, and the result follows.