text:
\begin{document}
\newcommand{\f}{\frac}
\newcommand{\sta}{\stackrel}
\maketitle
\begin{abstract}
\noindent   The power graph $\mathcal{P}(G)$ of a finite group $G$ is the graph whose vertex set is $G$, and two elements in $G$ are adjacent if one of them is a power of the other.
The purpose of this paper is twofold. First, we find the complexity of a clique--replaced graph and study
 some applications. Second, we derive some explicit formulas concerning the complexity $\kappa(\mathcal{P}(G))$
for various groups $G$ such as the cyclic group of order $n$, the simple groups $L_2(q)$, the extra--special $p$--groups of order $p^3$,
 the Frobenius groups, etc.
\end{abstract}

{\em Keywords}: Power graph, spanning tree, complexity,  group.

\renewcommand{\baselinestretch}{1}
\def\thefootnote{ \ }
\footnotetext{{\em $2010$ Mathematics Subject Classification}: 20D06, 05C05, 05C50.}
\section{Introduction}
All graphs considered here are simple connected graphs.
A {\em spanning tree} of a  connected graph
 is  a subgraph that contains all the vertices and is a tree.
 Counting the number of spanning trees in a connected graph
 is a problem of long--standing interest
 in various fields of science.
 For a  graph $\Gamma$, the
 number of spanning trees of $\Gamma,$  denoted by $\kappa(\Gamma),$ is known as the {\em complexity} of $\Gamma$.

In this paper, we consider some graphs arising from finite groups. One well--known graph is the power graph, as defined more precisely below.
\begin{definition} {\rm  Let $G$ be a finite group and $X$ a nonempty subset of $G$.
The {\em power graph} $\mathcal{P}(G, X)$,  has
$X$ as its vertex set and two vertices $x$ and $y$ in $X$ are joined by an edge if $\langle
x\rangle\subseteq \langle y\rangle$ or $\langle y\rangle\subseteq
\langle x\rangle$.  }
\end{definition}

The term {\em power graph} was introduced in \cite{Kelarev2}, and after that power graphs have been investigated by many authors, see for instance \cite{Kelarev, Cameron, Moghaddamfar}.
The investigation of power graphs associated with algebraic structures is important, because these graphs have valuable applications (see the survey article \cite{Kelarev3}) and are related to automata theory (see the book \cite{Kelarev1}).

In the case $X=G$, we will simply write  $\mathcal{P}(G)$ instead of $\mathcal{P}(G, G)$.
Clearly, when $1\in X$,  the power graph is connected, and we can talk about the complexity
of this graph. For convenience, we put  $\kappa_G(X)=\kappa(\mathcal{P}(G, X))$ and $\kappa(G)=\kappa(\mathcal{P}(G))$. A well known result due to Cayley \cite{Cayley} says that the complexity of the complete graph on $n$ vertices is $n^{n-2}$. In \cite{Chakrabarty}  it was shown that
a finite group has a complete power graph if and only if it is a cyclic $p$--group, where $p$ is a prime
number.
Thus, as an immediate consequence of Cayley's result, we derive $\kappa({\Bbb Z}_{p^m})=p^{m(p^m-2)}$.  Recently, the authors of \cite{MRSS}   obtained  a formula to compute the complexity $\kappa({\Bbb Z}_{n})$ for any $n$ (see Corollary \ref{result2} below). To obtain Corollary \ref{result2}, we will define a class of graphs more general than the power graphs of cyclic groups. Specifically, we start with a graph $\Gamma$ on  vertices  $v_1, v_2, \ldots, v_n$.  To construct a new graph, we replace each $v_i$  by a complete graph $K_{x_i}$ on $x_i$ vertices,  and if there is an edge between $v_i$ and $v_j$ in $\Gamma$, then  we connect each vertex of $K_{x_i}$  with each vertex of $K_{x_j}$.  The new graph will be denoted by $\Gamma_{[x_1, \ldots, x_n]}$.  We will derive explicit formulas for the complexity $\kappa(\Gamma_{[x_1, \ldots, x_n]})$ (see Theorem \ref{result1} and Remark \ref{alt_appch}). Then we will obtain a formula for the complexity  $\kappa({\Bbb Z}_{n})$  by choosing  a certain graph $\Gamma$  on $k$ vertices and positive integers $x_1, x_2, \ldots, x_k$  (Corollary \ref{result2}).  Finally, the complexities $\kappa(G)$ for certain groups $G$  are presented.

The outline of the paper is as follows. In the next section, we recall
 some basic definitions and notation and give several auxiliary
results to be used later. The main result
of Section 4 is Theorem \ref{result1} and we include some of its applications.
In Section 5, we compute  $\kappa(G)$ for certain groups $G$.

\section{Terminology and Previous Results}
We first establish some notation which will be used repeatedly in the sequel.
Given a graph $\Gamma$, we denote by $\mathbf{A}_\Gamma$ and $\mathbf{D}_\Gamma$ the adjacency matrix and the diagonal matrix of vertex degrees of $\Gamma$, respectively. The Laplacian matrix of $G$ is defined
as $\mathbf{L}_\Gamma=\mathbf{D}_\Gamma-\mathbf{A}_\Gamma$. Clearly, $\mathbf{L}_\Gamma$ is a real symmetric matrix and its eigenvalues are nonnegative real numbers.
The Laplacian spectrum of $\Gamma$ is
$${\rm Spec}(\mathbf{L}_\Gamma)=\left(\mu_1(\Gamma), \mu_2(\Gamma), \ldots, \mu_n(\Gamma)\right),$$
where $\mu_1(\Gamma)\geqslant \mu_2(\Gamma)\geqslant \cdots\geqslant \mu_n(\Gamma)$,
are the eigenvalues of $L_\Gamma$ arranged in weakly decreasing order, and $n=|V(\Gamma)|$.
Note that  $\mu_n(\Gamma) = 0$, because each row sum of $\mathbf{L}_\Gamma$ is 0.
Instead of $\mathbf{A}_\Gamma$, $\mathbf{L}_\Gamma$, and $\mu_i(\Gamma)$  we simply write $\mathbf{A}$, $\mathbf{L}$,  and $\mu_i$  if it does not lead to confusion.
Given a subset $\Lambda$ of the vertex set of a graph, we let $\mathbf{A}(\Lambda)$ denote the principal submatrix of $\mathbf{A}$ corresponding to the vertices in $\Lambda$.

For a graph with $n$ vertices and Laplacian spectrum $\mu_1\geqslant \mu_2\geqslant \cdots\geqslant \mu_n=0$
it has been proved \cite[Corollary 6.5]{Biggs} that:
\begin{equation}\label{eq1}
\kappa(\Gamma)=\frac{\mu_1 \mu_2 \cdots \mu_{n-1}}{n}.
\end{equation}

The vertex--disjoint union of the graphs $\Gamma_1$ and $\Gamma_2$ is denoted by $\Gamma_1\oplus\Gamma_2$.
Define the {\em join} of $\Gamma_1$ and $\Gamma_2$ to be $\Gamma_1 \vee \Gamma_2=(\Gamma_1^c\oplus\Gamma_2^c)^c$. Evidently this is the graph formed from the vertex--disjoint union of the two graphs $\Gamma_1, \Gamma_2$,
by adding edges joining every vertex of  $\Gamma_1$  to every
vertex of $\Gamma_2$.
Now, one may easily prove the following (see also \cite{Merris}).
\begin{lm}\label{elementary0}
Let $\Gamma_1$ and $\Gamma_2$ be two graphs on disjoint sets  with $m$ and $n$ vertices, respectively. If
$${\rm Spec}(\mathbf{L}_{\Gamma_1})=\left(\mu_1(\Gamma_1), \mu_2(\Gamma_1), \ldots, \mu_m(\Gamma_1)\right),$$
and
$${\rm Spec}(\mathbf{L}_{\Gamma_2})=\left(\mu_1(\Gamma_2), \mu_2(\Gamma_2), \ldots, \mu_n(\Gamma_2)\right),$$ then, the following hold:
\begin{itemize}
\item[{\rm (1)}] the eigenvalues of Laplacian matrix  $\mathbf{L}_{\Gamma_1\oplus \Gamma_2}$ are:
$$\mu_1(\Gamma_1), \  \ldots, \ \mu_{m}(\Gamma_1),  \ \mu_1(\Gamma_2), \  \ldots, \ \mu_{n}(\Gamma_2).$$

\item[{\rm (2)}] the eigenvalues of Laplacian matrix  $\mathbf{L}_{\Gamma_1\vee \Gamma_2}$ are:
$$m+n, \ \mu_1(\Gamma_1)+n, \  \ldots, \  \mu_{m-1}(\Gamma_1)+n, \ \mu_1(\Gamma_2)+m, \ \ldots, \ \mu_{n-1}(\Gamma_2)+m, \ 0.$$
\end{itemize}
\end{lm}

A {\em universal} vertex is a vertex of a graph that is adjacent to all other vertices of the graph. Now, we restrict our attention to information about the set of universal
vertices of the power graph of a group $G$. As already mentioned, the identity element of $G$ is  a universal vertex in $\mathcal{P}(G)$, and also $\mathcal{P}(G)$ is complete if and only if $G$ is cyclic of prime power order, and in this case $G$ is the set of all universal vertices. However, the following lemma  \cite[Proposition $4$]{Cameron} determines the set of universal vertices of the power graph
of $G$, in the general case.

\begin{lm}\label{universal}
 Let $G$ be a finite group and $S$  the set of universal vertices of the power graph $\mathcal{P}(G)$. Suppose that $|S|>1$. Then one of the following occurs:
\begin{itemize}
\item[{\rm (a)}]  $G$ is cyclic of prime power order, and $S=G$;
\item[{\rm (b)}]  $G$ is cyclic of non--prime--power order $n$, and $S$ consists of the identity and the
generators of $G$, so that $|S|=1+\phi(n)$, where $\phi$ is Euler's $\phi$--function;
\item[{\rm (c)}]  $G$ is generalized quaternion, and $S$ contains the identity and the unique involution in $G$, so that $|S|=2$.
\end{itemize}
\end{lm}

We conclude this section with notation and definitions to be used in
the paper. All the groups considered here are finite.  We denote by $[G,G]$ the commutator subgroup, for any group $G$. If $g \in G$, then $o(g)$ denotes the order of the element $g$. We refer to any  element in $G$  of order $2$, as an {\em involution}.
An {\em elementary abelian $p$--group} of order $p^n$, denoted by  ${\Bbb E}_{p^n}$, is isomorphic to a direct
product of $n$ copies of the cyclic group ${\Bbb Z}_p$. The complement of a graph $\Gamma$ is denoted by $\Gamma^c$. The neighborhood of a vertex $v$ in the graph $\Gamma$ is denoted by $N_\Gamma(v)$. Let $K_n$ denote the {\em complete graph} ({\em clique}) with $n$ vertices.
 Throughout we use the standard notation and terminology introduced in \cite{Biggs, Isaacs} for graph theory and group theory.

\section{Auxiliary Results}
\begin{lm}\label{join-integer}  Let $\Gamma$ be any graph on $n$ vertices with Laplacian spectrum
$$\mu_1 \geqslant \mu_2 \geqslant  \cdots \geqslant  \mu_n.$$
If $m$ is an integer, then the following product
$$(\mu_1+m)(\mu_2+m)\cdots (\mu_{n-1}+m),$$
is also an integer.
\end{lm}
\begin{proof}  Consider the characteristic polynomial of the Laplacian matrix $\mathbf{L}$:
$$\sigma(\Gamma; \mu)=\det (\mu \mathbf{I}-\mathbf{L})=\mu^n+c_1\mu^{n-1}+\cdots+c_{n-1}\mu+c_n.$$
First, we observe that the coefficients $c_i$ are integers \cite[Theorem 7.5]{Biggs}, and in particular, $c_n=0$.
This forces  $\sigma(\Gamma; -m)$ to be an integer, which is  divisible by $m$.
Moreover, we have
$$\sigma(\Gamma; \mu)=(\mu-\mu_1)(\mu-\mu_2)\cdots (\mu-\mu_n),$$
and since $\mu_n=0$, we obtain
$$\sigma(\Gamma; -m)=(-1)^n m(\mu_1+m)(\mu_2+m)\cdots (\mu_{n-1}+m).$$
 The result now follows.
\end{proof}

\begin{lm}\label{full}
Let  a graph $\Gamma$ with $n$ vertices contain $m<n$ universal vertices. Then $k(\Gamma)$ is divisible
by $n^{m-1}$.
\end{lm}
\begin{proof}  Let $W$ be the set of universal vertices, $\Gamma_0=\Gamma-W$ and $t=n-m$.
Clearly, we have $\Gamma=K_m\vee \Gamma_0$. Let
$\mu_1 \geqslant \mu_2 \geqslant  \cdots \geqslant  \mu_t=0$, be the eigenvalues of $\mathbf{L}_{\Gamma_0}$.
Since the Laplacian matrix for the complete graph $K_m$ has eigenvalue $0$ with multiplicity $1$ and eigenvalue $m$ with multiplicity $m-1$,  it follows by Lemma \ref{elementary0}  that  the eigenvalues of the Laplacian matrix  $\mathbf{L}_{\Gamma}$ are:
$$n, \underbrace{n, \ n, \ \ldots, \ n}_{m-1}, \  \underbrace{\mu_1+m, \ \mu_2+m, \ \ldots, \ \mu_{t-1}+m}_{t-1}, \ 0. $$
We find immediately using Eq. (\ref{eq1}) that
$$\kappa(\Gamma)=n^{m-1}(\mu_1+m)(\mu_2+m)\cdots (\mu_{t-1}+m).$$
Finally, since $(\mu_1+m)(\mu_2+m)\cdots (\mu_{t-1}+m)$ is an integer by Lemma \ref{join-integer},  we obtain the result. \end{proof}

Let $Q_{2^n}$ $(n\geqslant 3)$ denote the generalized quaternion
group of order $2^n$, which can be presented by
$$Q_{2^n}=\langle x, y \ | \ x^{2^{n-1}}=1, y^2=x^{2^{n-2}}, x^y=x^{-1}\rangle.$$
Moreover, the power graph $\mathcal{P}(Q_{2^n})$ has the following form:
$$\mathcal{P}(Q_{2^n})=K_2\vee \Big(K_{2^{n-1}-2}\oplus
\underbrace{K_2\oplus K_2\oplus \cdots \oplus K_2}_{2^{n-2} {\rm
-times}}\Big).$$
Using Lemma \ref{elementary0} and Eq. (\ref{eq1}), we have the following corollary \cite[Theorem 5.2]{MRSS}:
\begin{corollary}\label{cor-quater} Let $n\geqslant 3$ be an integer. Then,
$\kappa(Q_{2^n})=2^{(2^{n-2}-1)(2n+1)+4}$.
\end{corollary}

A  finite group $G$ is called an {\em element prime order} group (EPO--group) if every nonidentity element of $G$ has prime order. We can consider the power graph of an EPO--group $G$ as follows:
$$ \mathcal{P}(G) =K_1 \vee \left(\bigoplus_{p\in \pi(G)} c_pK_{p-1}\right),$$
where $c_p$ signifies the number of cyclic subgroups of order $p$
in $G$. Again, using Lemma \ref{elementary0} and Eq. (\ref{eq1}), we have the following corollary \cite[Corollary 3.4]{MRSS}:
\begin{corollary}\label{cor-epo} Let $G$ be an EPO--group. Then we have:
$$\kappa(G)=\prod_{p\in \pi(G)}p^{(p-2)c_p}.$$
In particular,  we have
$$\kappa\left({\Bbb E}_{p^n}\right)=p^{(p-2)(p^n-1)/(p-1)}.$$
\end{corollary}

\section{Clique--Replaced Graphs}
Let $\Gamma$ be a connected graph with vertices $v_1, \ldots, v_k$. Given positive integers $x_1, \ldots, x_k$,
we construct the new graph $\Gamma_{[x_1, \ldots, x_k]}$ as follows: Replace vertex $v_i$
in $\Gamma$ by the complete graph (clique) $K_{x_i}$, $i=1, \ldots, k$, and label the vertex set of $K_{x_i}$ for each $i$ as:
$u_{i_1}, u_{i_2}, \ldots, u_{i_{x_i}}$. Now, if $v_i$ is adjacent to $v_j$ in $\Gamma$, then connect all vertices
$u_{i_1}, u_{i_2}, \ldots, u_{i_{x_i}}$ with all vertices $u_{j_1}, u_{j_2}, \ldots, u_{j_{x_j}}$.
We call the resulting graph $\Gamma_{[x_1, \ldots, x_k]}$ the {\em clique--replaced graph}.
It is clear that for a fixed $i$, all vertices $u_{i_1}, u_{i_2}, \ldots, u_{i_{x_i}}$ have the same degree which is equal to
$$n_i=x_i-1+\sum_{v_j\in N_\Gamma(v_i)} x_j.$$
Put
$m_i=n_i+1=x_i+\sum_{v_j\in N_\Gamma(v_i)} x_j, \ \ \ \lambda_i=\frac{m_i}{x_i}, \ \ i=1, \ldots, k,$
and $\Psi=\prod_{i=1}^{k} \lambda_i.$
Suppose that $n=x_1+\cdots+x_k$.

\begin{theorem}\label{result1}  With the notation as explained above, we have
\begin{equation}\label{formula1} \kappa\left(\Gamma_{[x_1, \ldots, x_k]}\right)=\prod_{i=1}^{k}m_i^{x_i}\Big(\Psi+
\sum_{\Lambda} \det \mathbf{A}_{\Gamma^c}(\Lambda)\lambda_1^{t_1}
\lambda_2^{t_2}\cdots \lambda_{k}^{t_{k}}\Big)/(\Psi
n^2),\end{equation} where $t_i\in \{0, 1\}$, $i=1,  \ldots,
k$, and the summation is over all induced subgraphs $\Lambda$ of
$\Gamma^c$ whose vertex set $\{v_{i_1}, \ldots , v_{i_s} \}$ corresponds to
  $\{i_j| t_{i_j}=0 \}.$
\end{theorem}
\begin{proof}$^{1}$\footnote{$^{1}$The idea of this proof is borrowed from \cite[Theorem 4.1]{MRSS}.}  Let $\Gamma^\ast=\Gamma_{[x_1, \ldots, x_k]}$.
 It is easy to check that, the matrix
$\mathbf{J}+\mathbf{L}_{\Gamma^\ast}$ associated with $\Gamma^\ast$ has the following block--matrix structure:
\begin{equation}\label{e1} \mathbf{J}+\mathbf{L}_{\Gamma^\ast}= \left(\mathbf{D}_{ij}\right)_{1\leqslant i,j\leqslant k},
\end{equation} where $\mathbf{D}_{ij}$ is a matrix of size $x_i\times x_j$
with
$$D_{ij}=\left\{\begin{array}{lll} m_i\mathbf{I} & if & i=j,\\[0.2cm]
0 & if & i\neq j, \ \  v_i\sim v_j \ \mbox{in} \ \Gamma,\\[0.2cm]
\mathbf{J} &  & \mbox{otherwise}.
\end{array} \right.$$
We need only to evaluate $\det (\mathbf{J}+\mathbf{L}_{\Gamma^\ast})$, because $\kappa(\Gamma^\ast)=\det(\mathbf{J}+\mathbf{L}_{\Gamma^\ast})/n^2$.
In what follows, $D$ denotes the determinant of the matrix on the right--hand
side of Eq. (\ref{e1}). In order to compute this determinant, we
apply the following row and column operations:
We subtract column $j$ from column $j+r$:
$$\left\{\begin{array}{ll} j=1+\sum\limits_{l=1}^{h}x_l, \ h=0, 1,2, \ldots, k-1,\\[0.3cm]
r=1, 2, \ldots, x_{h+1}-1.\end{array} \right.$$
Then, we add row $i+s$ to row $i$:
$$\left\{\begin{array}{ll} i=1+\sum\limits_{l=1}^{h}x_l, \ h=0, 1,2, \ldots, k-1,\\[0.3cm]
s=1, 2, \ldots, x_{h+1}-1.\end{array} \right.$$ (Note that,
when $m>n$, we adopt the convention that $\sum_{i=m}^n x_i=0$.) Using the above
operations, it is easy to see that
$$D=\det \left(\mathbf{M}_{ij}\right)_{1\leqslant i,j\leqslant k},$$
where $\mathbf{M}_{ij}$ is a matrix of size $x_i\times x_j$
with
$$ \mathbf{M}_{ij}=\left\{\begin{array}{ll} m_i\mathbf{I} &  \mbox{if} \  \  i=j,\\[0.2cm]
0 &  \mbox{if} \ \  i\neq j, \ \  v_i\sim v_i \ \ \mbox{in} \ \Gamma,\\[0.2cm]
x_i\mathbf{E}_{1, 1}+\mathbf{E}_{2,1}+\cdots+\mathbf{E}_{x_i, 1} & \mbox{otherwise},
\end{array} \right.$$
where $\mathbf{I}$ is the identity matrix and $\mathbf{E}_{i,j}$
denotes the square matrix having $1$ in the $(i,j)$ position and
$0$ elsewhere.

Therefore, taking out the common factors and developing the
determinant along the columns $j$,
$j\neq1+\sum\limits_{l=1}^{h}x_l$, $h=0, 1, 2, \ldots, k-1$, one
gets
\begin{equation}\label{e2} D=\Phi^{-1}\prod_{i=1}^{k}{m_i}^{x_i}\cdot\det
\left(c_{ij}\right)_{1\leqslant i,j\leqslant k},\end{equation}
where $$ c_{ij}=\left\{\begin{array}{cl}\lambda_i &  \mbox{if} \  \  i=j,\\[0.2cm]
0 &  \mbox{if} \ \  i\neq j, \ \ v_i\sim v_j \  \mbox{in} \ \Gamma,\\[0.2cm]
1 & \mbox{otherwise}.
\end{array} \right.$$
As the reader might have noticed, the matrix
$\left(c_{ij}\right)_{1\leqslant i,j\leqslant k}-{\rm diag}(\lambda_1, \lambda_2, \ldots, \lambda_k)$
is exactly the adjacency matrix of the graph
$\Gamma^c$. Consequently, we
get
$$\det \left( \left[
\begin{array}{cccc}
\lambda_1& c_{12} & \ldots & c_{1k} \\[0.1cm]
c_{21} & \lambda_2 & \ldots & c_{2k} \\[0.1cm]
\vdots & \vdots & \ddots & \vdots \\[0.1cm]
c_{k1} & c_{k2} & \ldots & \lambda_{k} \\[0.1cm]
\end{array}\right ] \right) =\Psi+\sum_{\Lambda}
\det \mathbf{A}_{\Gamma^c}(\Lambda)\lambda_1^{t_1}\lambda_2^{t_2}\cdots
\lambda_{k}^{t_{k}},$$ where $t_i\in \{0, 1\}$, $i=1, 2,
\ldots, k$,  and the summation is over all induced subgraphs
$\Lambda$ of $\Gamma^c$ whose  vertex set $\{v_{i_1}, \ldots,
v_{i_s}\}$ corresponds to
  $\{i_j| t_{i_j}=0 \}.$
 This is
substituted in Eq. (\ref{e2}):
$$D=\Psi^{-1}\prod_{i=1}^{k}{m_i}^{x_i}\cdot \Big(\Psi+\sum_{\Lambda}
\det \mathbf{A}_{\Gamma^c}(\Lambda)\lambda_1^{t_1}\lambda_2^{t_2}\cdots
\lambda_{k}^{t_{k}}\Big).$$  \end{proof}

\begin{remark} \label{alt_appch}
{\rm{In this remark, we describe an alternate approach to the computation of $\kappa\left(\Gamma^\ast \right).$
Note that $\mathbf{L}_{\Gamma^\ast}$ can be written as a $k \times k$ block matrix, where, for distinct $i,j=1,\ldots, k,$  the $(i,j)$ off--diagonal block is either $-J$ or $0$ according as $v_i$ is adjacent to $v_j,$ or not, and where the $j$--th diagonal block is $m_jI-J, j=1, \ldots, k.$  From this block structure,
and applying the technique of equitable partitions (see \cite{BH}),
it follows readily that the product of the nonzero eigenvalues of $\mathbf{L}_{\Gamma^\ast}$ is equal to $ \alpha_2\cdots \alpha_k \left(\prod_{j=1}^{k}\left( m_j \right)^{x_j-1}\right),$ where $0, \alpha_2, \alpha_3, \ldots, \alpha_k$ are the eigenvalues of the
the $k \times k$ matrix $\mathbf{S}$ whose entries are given by
$$s_{pq}=\left\{\begin{array}{lll} 0  &  &  \mbox{if $v_p\neq v_q$ and $v_p$ is not adjacent to $v_q$ in $\Gamma$,} \\[0.2cm]
 -x_q & &\mbox{if $p < q$ and $v_p$ is adjacent to $v_q$ in $\Gamma$},\\[0.2cm]
 -x_p & &\mbox{if $p > q$ and $v_p$ is adjacent to $v_q$ in $\Gamma$},\\[0.2cm]
-\sum_{j\neq p} s_{pj} &  & \mbox{if $p=q$}.\\
\end{array} \right.$$
(Observe that $\mathbf{S}$ is singular since every row sums to $0.$) In order to complete the computation of the complexity of
$L_{\Gamma^\ast}$, we need to find the product $\alpha_2\cdots \alpha_k$.
For each $j=1, \ldots, k$, let $\mathbf{S}_{(j)}$ denote the principal sub--matrix of $\mathbf{S}$ formed by deleting
row $j$ and column $j$. Then $\alpha_2\cdots \alpha_k=\sum_{j=1}^{k} \det(\mathbf{S}_{(j)}).$

To compute the quantities $\det(\mathbf{S}_{(j)}), j=1, \ldots, k,$ we consider a weighted directed graph $W$ on  vertices $1, \ldots, k,$ whose construction we now describe.
Begin with the graph $\Gamma$ on  vertices  $v_1, v_2, \ldots, v_k$.
For each edge $\{v_i, v_j\}$ of $\Gamma$, $W$ contains the arcs $i\rightarrow j$ and $j\rightarrow i$;
if $i<j$, the weight of the arc $i\rightarrow j$ in $W$ is $w(i,j)=x_j$, and the
weight of the arc $j\rightarrow i$  is $w(j,i)=x_i$; if there is no edge between $v_i$ and $v_j$ in $\Gamma$,
then $W$ contains neither an arc from $i$ to $j$ nor an arc from $j$ to $i$.
Fix an index $j$ with $1\leqslant j\leqslant k$. We can find $\det(\mathbf{S}_{(j)})$ from
 a generalization of the matrix tree theorem as follows (see \cite{Chaiken}). Let $\tau_j$ be the set of all spanning directed subgraphs of $W$ such
that:

(a) the underlying spanning subgraph is a tree; and

(b) in the spanning directed subgraph of $W$,
for each vertex $i\neq j$, there is a directed path from $i$ to $j$.

For each directed graph $\tau\in \tau_j$, let the weight of $\tau$, $\sigma(\tau)$, be the
product of the weights of the arcs in $\tau$ (these arc weights are inherited from $W$). Then
$ \det(\mathbf{S}_{(j)})=\sum_{\tau\in \tau_j} \sigma(\tau).$
So, we have
$\alpha_2\cdots \alpha_k=\sum_{j=1}^{k}  \sum_{\tau\in \tau_j} \sigma(\tau).$
Consequently, we obtain the following formula for $\kappa(\Gamma^\ast)$:
$$\kappa(\Gamma^\ast)=\frac{\left[ \prod_{j=1}^{k}\left( m_j \right)^{x_j-1}\right]\left[\sum_{j=1}^{k}  \sum_{\tau\in \tau_j} \sigma(\tau)\right]}{n}.$$
}}
\end{remark}

Next, we present some applications of the preceding results.

\noindent
{\it{Application 1, clique--replaced paths}}: Now we consider a particular graph, the path on $k$ vertices  $\Gamma=P_k$, where $k \geqslant 3$ is an integer. For this special case, we
apply the technique of Remark \ref{alt_appch} in order to obtain the complexity of the graph $\Gamma_{[x_1, \ldots, x_k]}$.
 For $\Gamma=P_k,$ the directed graph $W$ of Remark \ref{alt_appch} is given as follows.

\vspace{1.5cm} \setlength{\unitlength}{3mm}
\begin{picture}(0,0)(1.5,9)
\linethickness{0.7pt}

\put(0,10){\circle*{0.5}}
\put(10,10){\circle*{0.5}}
\put(20,10){\circle*{0.5}}

\put(30,10){\circle*{0.5}}
\put(40,10){\circle*{0.5}}

\put(0,8){$1$}
\put(10,8){$2$}
\put(20,8){$3$}
\put(29,8){$n-1$}
\put(40,8){$n$}

\put(0,10){\vector(1,0){10}}
\put(10,10){\vector(1,0){10}}
\put(20,10){\vector(1,0){1}}
\put(30,10){\vector(1,0){10}}
\put(29,10){\vector(1,0){1}}
\put(22,10){$\ldots$}
\put(27,10){$\ldots$}

\qbezier(30,10)(29.5,10.5)(29,10.9)

\qbezier(0,10)(5,15)(10,10)
\qbezier(10,10)(15,15)(20,10)
\qbezier(20,10)(20.5,10.5)(21,10.9)
\qbezier(30,10)(35,15)(40,10)

\put(1,11){\vector(-1,-1){1}}
\put(11,11){\vector(-1,-1){1}}
\put(21,11){\vector(-1,-1){1}}
\put(31,11){\vector(-1,-1){1}}

\end{picture}\\[.5cm]

Observe that $\tau_1$ contains one directed graph of weight $x_1x_2x_3 \ldots x_{n-1}$, while
$\tau_n$ contains one directed graph of weight $x_2x_3 \ldots x_n.$ Further, for each $j=2, \ldots, n-1,$ we find that $\tau_j$ contains one directed graph of weight $$(x_2 \ldots x_j)(x_j \ldots x_{n-1}).$$ Consequently for the matrix $\mathbf{S}$ of Remark \ref{alt_appch}, we have
$$\sum_{j=1}^{k} \det(\mathbf{S}_{(j)})=x_1\ldots x_{n-1} + \sum_{j=2}^{n-1}x_j(x_2 \ldots x_{n-1}) + x_2 \ldots x_n = (x_2 \ldots x_{n-1})\sum_{j=1}^n x_j.$$
It now follows that
\begin{eqnarray*}
\kappa\left(\Gamma_{[x_1, \ldots, x_k]}\right) = \hspace{3.75in}\\
(x_1+x_2)^{x_1-1}\Pi_{j=2}^{n-1}(x_{j-1}+x_j+x_{j+1})^{x_j-1} (x_{n-1}+x_n)^{x_n-1}(x_2 \ldots x_{n-1})\sum_{j=1}^n x_j.
\end{eqnarray*}

\noindent
{\it{Application 2, Cayley's theorem}}: In the case when $\Gamma=K_t$ and $x_1=\cdots=x_t=x$, we have  $\Gamma_{[x_1,\ldots,x_t]}=K_{tx}$.  Moreover,  in the situation of  Theorem \ref{result1} we have:
$n_i=\cdots=n_t=tx-1$, $m_i=\cdots=m_t=tx$,   $\lambda_i=\cdots=\lambda_t=t$ and $\Psi=t^t$.
Substitution into Eq. (\ref{formula1}) yields $$\kappa(K_{tx})=\left(\prod_{i=1}^{t}(tx)^{x}\right)(t^t+0)/(t^t(tx)^2)=(tx)^{tx-2},$$  which is equivalent to Cayley's result. \\

\noindent
{\it{Application 3, complexity of}} $\mathcal{P}(\mathbb{Z}_n)$: Given a natural number $n$,  the {\em divisor graph} $D(n)$ of $n$ is the graph with vertex set $\pi_d(n)=\{d_1, \ldots, d_k\}$, the set of all divisors of $n$, in which two distinct divisors $d_i$ and $d_j$ are adjacent if and only if  $d_i|d_j$ or
$d_j|d_i$.   Let $d_1>d_2>\cdots>d_k$ (evidently $d_1=n$ and $d_k=1$). This shows that (see also \cite[Theorem 2.2]{Mehranian}):
\begin{equation}\label{eq4} \mathcal{P}(\mathbb{Z}_n)=D(n)_{[\phi(d_1), \ldots, \phi(d_k)]}.\end{equation}
In what follows, we put $\Gamma=D(n)$,
$n_i=\phi(d_i)-1+\sum_{d_j\in N_\Gamma(d_i)} \phi({d_j})$,
$m_i=n_i+1$,
 $\lambda_i=\frac{m_i}{\phi(d_i)}, \ \ i=1, \ldots, k,$ and
 $\Phi=\prod_{i=2}^{k-1} \lambda_i, \ \  \Psi=\prod_{i=1}^{k} \lambda_i.$
By using Theorem \ref{result1}, we have the following alternate proof of a result in \cite{MRSS}.

\begin{corollary}{\rm \cite[Theorem 4.1]{MRSS}}\label{result2}  Let $d_1>d_2>\cdots>d_k$ be the divisors of a positive integer
$n$. With the notation as above, we have
$$\kappa(\mathbb{Z}_{n})=\prod_{i=1}^{k}m_i^{\phi(d_i)}\Big(\Phi+
\sum_{\Lambda} \det\mathbf{A}_{\Gamma^c}(\Lambda)\lambda_2^{t_2}
\lambda_3^{t_3}\cdots \lambda_{k-1}^{t_{k-1}}\Big)/(\Phi
n^2),$$ where $t_i\in \{0, 1\}$, $2\leqslant i\leqslant
k-1$, and the summation is over all induced subgraphs $\Lambda$ of
$\Gamma^c\setminus \{d_1, d_k\}$   whose  vertex set $\{d_{i_1}, \ldots,
d_{i_s}\}$ corresponds to
 $\{i_j| t_{i_j}=0 \}.$
\end{corollary}
\begin{proof} Using Eq. (\ref{eq4}) and Theorem \ref{result1}, we obtain
\begin{equation}\label{eq5} \kappa(\mathbb{Z}_n)=\prod_{i=1}^{k}m_i^{\phi(d_i)}\Big(\Psi+
\sum_{\Lambda'} \det \mathbf{A}_{\Gamma^c}(\Lambda')\lambda_1^{t_1}
\lambda_2^{t_2}\cdots \lambda_{k}^{t_{k}}\Big)/(\Psi
n^2),\end{equation} where $t_i\in \{0, 1\}$, $i=1,  \ldots,
k$, and the summation is over all induced subgraphs $\Lambda'$ of
$\Gamma^c$   whose  vertex set $\{d_{i_1}, \ldots,
d_{i_s}\}$ corresponds to
  $\{i_j| t_{i_j}=0 \}.$
 Since $\deg_\Gamma(d_1)=\deg_\Gamma(d_k)=k-1$, we obtain
$\deg_{\Gamma^c}(d_1)=\deg_{\Gamma^c}(d_k)=0$. Thus, if an induced subgraph $\Lambda'$ of
$\Gamma^c$ contains $d_1$ or $d_k$, then  $\det \mathbf{A}_{\Gamma^c}(\Lambda')=0$, while if it does not contain $d_1$ and $d_k$, then the sum $\sum_{\Lambda'} \det \mathbf{A}_{\Gamma^c}(\Lambda)\lambda_1^{t_1}
\lambda_2^{t_2}\cdots \lambda_{k}^{t_{k}}$ is divisible by $\lambda_1\lambda_k$. Hence, we can write
$$\sum_{\Lambda'} \det \mathbf{A}_{\Gamma^c}(\Lambda)\lambda_1^{t_1}
\lambda_2^{t_2}\cdots \lambda_{k}^{t_{k}}=\lambda_1\lambda_k\sum_{\Lambda} \det \mathbf{A}_{\Gamma^c}(\Lambda)
\lambda_2^{t_2}\cdots \lambda_{k-1}^{t_{k-1}}$$
where the $\Lambda$ run over all induced subgraphs of $\Gamma^c\setminus \{d_1, d_k\}$   whose  vertex set $\{d_{i_1}, \ldots,
d_{i_s}\}$ corresponds to
  $\{i_j| t_{i_j}=0 \}.$
 Substituting this in Eq. (\ref{eq5}) and simplifying now yields the
result.
\end{proof}

\section{ Computing the Complexity $\kappa(G)$}
In this section we consider the problem of finding the complexity of power graphs associated with
certain finite groups.
\subsection {The simple groups $L_2(q)$}  Let $q=p^n\geqslant 4$  for a prime $p$ and some $n\in {\Bbb N}$.
We are going to find an explicit formula for $\kappa(L_2(q))$. Before we start,  we need some well known facts about the simple groups $G=L_2(q)$, $q\geqslant 4$, which are proven in \cite{Hup}:
\begin{itemize}
\item[{\rm (a)}]   $|G|=q(q-1)(q+1)/k$ and $\mu(G)=\{p, (q-1)/k, (q+1)/k\}$, where $k={\rm gcd}(q-1, 2)$.

\item[{\rm (b)}] Let $P$ be a Sylow $p$--subgroup of $G$. Then  $P$ is an elementary abelian $p$--group of order
$q$, which is a TI--subgroup, and  $|N_G(P)|=q(q-1)/k$.

\item[{\rm (c)}] Let $A\subset G$ be a cyclic subgroup of order $(q-1)/k$. Then $A$ is a TI--subgroup and
the normalizer $N_G(A)$ is a dihedral group of order $2(q-1)/k$.

\item[{\rm (d)}] Let $B\subset G$ be a cyclic subgroup of order $(q+1)/k$. Then  $B$ is a TI--subgroup
and the normalizer $N_G(B)$ is a dihedral group of order $2(q+1)/k$.
\end{itemize}
We recall that a subgroup  $H\leqslant G$  is a {\em TI--subgroup} (trivial intersection subgroup) if for every $g\in G$, either $H^g=H$ or $H\cap H^g=\{1\}$.

\begin{theorem} \label{char2} Let $q=p^n$, with $p$ prime  and $n\in {\Bbb N}$  and let $G=L_2(q)$.  Then we have:
$$\kappa(G)=p^{\frac{(q^2-1)(p-2)}{p-1}}\cdot \kappa\left({\Bbb Z}_{\frac{q-1}{k}}\right)^{q(q+1)/2}\cdot \kappa\left({\Bbb Z}_{\frac{q+1}{k}}\right)^{q(q-1)/2},$$
where $k={\rm gcd}(q-1, 2)$, except exactly in the cases $(p, n)=(2, 1)$, $(3, 1)$.
In particular, we have
\begin{itemize}
\item[{\rm (1)}]$A_5\cong L_2(5)\cong L_2(4)$ and $\kappa(A_5)=3^{10}\cdot 5^{18}$ {\rm (see \cite{MRSS})}.

\item[{\rm (2)}]$L_3(2)\cong L_2(7)$ and  $\kappa(L_3(2))=2^{84}\cdot 3^{28}\cdot 7^{40}$.

\item[{\rm (3)}]$A_6\cong L_2(9)$ and $\kappa(A_6)=2^{180}\cdot 3^{40}\cdot 5^{108}.$
\end{itemize}
\end{theorem}
\begin{proof}
Let  $q=p^n$, with $p$ prime and $n\in {\Bbb N}$, and $(p, n)\neq (2, 1), (3, 1)$.
As already mentioned,  $G$ contains abelian subgroups
 $P$, $A$ and $B$, of orders $q$, $(q-1)/k$ and $(q+1)/k$, respectively, every distinct pair of their conjugates
 intersects trivially, and every element
of $G$ is a conjugate of an element in $P\cup A\cup B$.
Let $$G=N_Pu_1\cup \cdots \cup N_Pu_r=N_Av_1\cup \cdots \cup N_Av_s= N_Bw_1\cup \cdots \cup N_Bw_t,$$
be coset decompositions of $G$ by $N_P=N_G(P)$, $N_A=N_G(A)$ and $N_B=N_G(B)$, where
  $r=[G:N_P]=q+1$, $s=[G:N_A]=q(q+1)/2$  and  $t=[G:N_B]=(q-1)q/2$.
Then, we have
\begin{equation} \label{eq-6}
G=P^{u_1}  \cup \cdots \cup P^{u_r}\cup A^{v_1}\cup \cdots \cup A^{v_s}\cup B^{w_1} \cup \cdots \cup B^{w_t}. \end{equation}
Applying Theorem 3.4 (b) in \cite{MRSS} to Eq. (\ref{eq-6}),  we obtain
$$\kappa(G)=\kappa_G(P)^r\cdot \kappa_G(A)^s\cdot \kappa_G(B)^t=\kappa\left({\Bbb E}_{q}\right)^r\cdot \kappa\left({\Bbb Z}_{\frac{q-1}{k}}\right)^s\cdot \kappa\left({\Bbb Z}_{\frac{q+1}{k}}\right)^t,$$
and so by Corollary \ref{cor-epo}, we get
$\kappa(G)=\left(p^{\frac{q-1}{p-1}(p-2)}\right)^r\cdot \kappa\left({\Bbb Z}_{\frac{q-1}{k}}\right)^s\cdot \kappa\left({\Bbb Z}_{\frac{q+1}{k}}\right)^t.$
The result follows.
\end{proof}

\subsection {Extra--special $p$--groups of order $p^3$}
In the sequel, $P$ will be a $p$--group, with $p$   prime.
We recall below some facts about extra--special groups and other necessary information. We begin with the definition of the extra special groups.
 A $p$--group $P$ is called {\em extra--special} if $Z(P) = [P,P] = \Phi(P)\cong \mathbb{Z}_p$, where   $\Phi(P)$ is the Frattini subgroup of $P$.
If $P$ is an extra--special $p$--group, then  the order of $P$ is $p^{2n+1}$ for some positive integer $n$. The smallest nonabelian extra--special groups are of order $p^3$.  When
$p=2$, there are, up to isomorphism, two extra--special $2$--group
of order $8$, namely, $D_8$ and $Q_8$. The exponent of both of these groups is $p^2=4$.  Furthermore, from
\cite[Table 1]{MRSS}, we have $\kappa(D_8)=2^4$ and $\kappa(Q_8)=2^{11}$.

For each odd prime $p$, up to isomorphism,
 there are just two non--isomorphic extra--special $p$--groups of order $p^3$. The first one has exponent $p$, which is called the {\em Heisenberg group}  and denoted by $H_p$.  In fact, $H_p$ as a subgroup of ${\rm GL}(3,p)$ can be
 presented in the following way:
$$H_p=\left\{ \left(\begin{array} {lll} 1 & 0 & 0\\ x & 1 & 0\\ z & y & 1\end{array}\right) \ \Bigg | \ x, y, z\in {\rm GF}(p) \right\}.$$
The other one has exponent $p^2$, which is denoted by $A_p$, and contains
transformations $x\mapsto ax+b$ from $\mathbb{Z}_{p^2}$ to $\mathbb{Z}_{p^2}$, where $a\equiv 1\pmod{p}$ and $b\in \mathbb{Z}_{p^2}$.

The groups $H_p$ and $A_p$  are usually presented as:
$$H_p=\langle x, y, z \ | \ x^p=y^p=z^p=1, [x,y]=z, [x,z]=[y,z]=1\rangle,$$
and
$$A_p=\langle x, y\ | \ x^{p}=y^{p^2}=1, y^x=y^{p+1}\rangle.$$
\begin{theorem}\label{extra-p} Let $p$ be an odd prime. Then, we have:
\begin{itemize}
\item[{\rm (a)}] $\kappa(H_p)=p^{(p-2)(p^2+p+1)}$.
\item[{\rm (b)}] $\kappa(A_p)=p^{2p^3-p-5}$.
\end{itemize}
\end{theorem}
\begin{proof} (a) Clearly,  we have $$H_p=\bigcup_{j=1}^{p^2+p+1}C_j,$$
where  $C_j\subset H_p$ is a subgroup of order $p$, and $C_i\cap C_j=1$ for $i\neq j$.
Now, by Theorem 3.4 (b) in \cite{MRSS}, we obtain
$$\kappa(H_p)=\prod_{j=1}^{p^2+p+1} \kappa(C_j)=\prod_{j=1}^{p^2+p+1} p^{p-2}=p^{(p-2)(p^2+p+1)}, $$
as desired.

(b) In this case, we have $$A_p=\bigcup_{j=1}^{p+1}B_j,$$
where  $B_j\subset A_p$ is a subgroup of order $p^2$, and $B_i\cap B_j=Z(A_p)$ for $i\neq j$.
Therefore, the power graph of $A_p$ has the following form
$${\cal P}(A_p)=K_p\vee \left[(p+1)K_{p^2-p}\right].$$
It follows by Lemma \ref{elementary0} that  the eigenvalues of Laplacian matrix  $\mathbf{L}_{{\cal P}(A_p)}$ are:
$$p^3, \underbrace{p^2, \ p^2, \ \ldots, \ p^2}_{p-1}, \  \underbrace{p^2, \  p^2, \ \ldots, \ p^2}_{p^3-2p-1},   \  \underbrace{p, \  p, \ \ldots, \ p}_{p}, \ 0. $$
 Using Eq. (\ref{eq1}), we get
$\kappa(A_p)=p^{2p^3-p-4}$,
as required.
\end{proof}

\subsection{Frobenius groups} Suppose $1\subset H\subset G$ and  $H\cap H^g=1$ whenever $g\in  G\setminus H$. Then $H$ is a {\em Frobenius complement} in $G$. A group which contains a Frobenius complement is called a {\em Frobenius group}.
A famous theorem of Frobenius asserts that in a Frobenius group $G$ with a Frobenius complement $H$, the set $$F=\left(G\setminus \bigcup_{g\in G} H^g\right)\cup\{1\},$$
is a normal subgroup of $G$ and $G=FH$, $F\cap H=1$. We call $F$ the {\em Frobenius kernel} of $G$.
\begin{theorem} \label{lm-3} Let $G$ be a Frobenius group,
$H$ a Frobenius complement and $F$ the Frobenius kernel
corresponding with $H$. Then, we have:  $$\kappa(G)=
\kappa_G(F)\kappa_G(H)^{|F|}.$$ In particular, if $G$ is a
nonabelian group of order $pq$, where $p<q$ are primes, then
$\kappa(G)=q^{q-2}p^{(p-2)q} .$
\end{theorem}
\begin{proof} Let $G$ be a Frobenius group, let $H$ be its Frobenius complement
and $F$ its Frobenius kernel. Then $G$ can be written as the union
of its subgroups:
$$G=F\cup \bigcup_{g\in F}H^g.$$
 Again, it follows from Theorem 3.4 (b) in \cite{MRSS} that
$$\kappa(G)=\kappa_G(F)\prod_{g\in
F}\kappa_G(H^g)=\kappa_G(F)\kappa_G(H)^{|F|},$$ as required.
\end{proof}

\begin{center}
 {\bf Acknowledgments }
\end{center}
This work was done while the second author had a visiting position at the
Department of Mathematical Sciences, Kent State
University, USA. He is thankful for the hospitality of the Department of Mathematical Sciences of KSU.
The research of the first author is supported by the Natural Sciences
and Engineering Research Council of Canada under grant number
RGPIN/6123--2014.


TITLE: How #P is easier than PSPACE?
QUESTION [0 upvotes]: It is said that #P is not harder than PSPACE. This way, how can Alternating Turing machine solve #SAT in polynomial time?
And if it can, seems, that it takes at least $O(n^4)$ time which is more time than needed for TQBF.

REPLY [0 votes]: This way, how can Alternating Turing machine solve #SAT in polynomial time?

An alternating Turing machine can only solve decision problems, so that questions makes sense for the decision variant of $\text{#SAT}$:
$$\text{Input: Boolean Formula $F$, $k \in \mathbb N$. Question: Are there at least $k$ solutions for $F$?}$$
This decision variant is in $\text{P}^\text{#P}$ ($\text{P}$ with $\text{#P}$ oracle), because you only need to ask the oracle how many solutions there are and compare the answer to $k$.
It is proven that:
$$\text{P}^\text{#P} \subseteq \text{PSPACE} = \text{AP}$$
So there exists indeed an alternating Turing machine solving the decision variant of $\text{#SAT}$ in polynomial time.

And if it can, seems, that it takes at least $\mathcal O(n^4)$ time which is more time than needed for TQBF.

Reference? That still wouldn't mean that the decision variant of $\text{#SAT}$ is harder than $\text{TQBF}$.
The term $A$ is not harder than $B$ is in this context defined as $A \le^p_m B$. That means there exists a polynomial time reduction from $A$ to $B$.
$\text{TQBF}$ is $\text{PSPACE}$-complete so from every decision problem in $\text{PSPACE}$ there exists a polynomial time reduction to $\text{TQBF}$.
Calculating the polynomial time reduction from the decision variant of $\text{#SAT}$ to $\text{TQBF}$ might already use more time than actually solving the resulting $\text{TQBF}$-instance (on an alternating Turing machine).


TITLE: Group action of $G<\mathbb Z^\infty_2$ over the Golden mean shif
QUESTION [1 upvotes]: I'm am looking for an action of an infinite subgroup of $\mathbb Z^\infty_2$ over the golden mean shift space $$X=\{x\in \{0,1\}^\mathbb N : x_i=1\Rightarrow x_{i+1}=0\}$$ such that any element of $G$ changes only a finite number of positions of elements of $X$.

REPLY [1 votes]: Let $F:X\to X$ be the map that replaces an occurrence of $010$ around the origin with $000$ and vice versa. That is,
\[
   F x \triangleq
      \begin{cases}
         \cdots x_{-3}x_{-2}000x_1x_2\cdots\quad &\text{if $x_{-1}x_0x_1=010$,}\\
         \cdots x_{-3}x_{-2}010x_1x_2\cdots &\text{if $x_{-1}x_0x_1=000$,}\\
         x &\text{otherwise.}
      \end{cases}
\]
Note that $F$ is an involution, hence acting like $\mathbb{Z}_2$.  So are its compositions with shifts $F\sigma^i$.  Moreover, $F\sigma^i$ and $F\sigma^j$ commute as long as $|i-j|\geq 3$.  Let us use the shorthand $F_k=F\sigma^{3k}$.
For $k_1,k_2,...,k_n\in\mathbb{Z}$, we get a faithful action of $\mathbb{Z}_2^n$ on $X$ by composing $F_{k_1},F_{k_2},\ldots,F_{k_n}$:
\[
   \Phi^{(b_1b_2\cdots b_n)}x \triangleq
      F_{k_1}^{b_1} F_{k_2}^{b_2}\cdots F_{k_n}^{b_n} x \;.
\]
Similarly, if $\mathbb{G}$ denotes the subgroup of $\mathbb{Z}_2^{\mathbb{Z}}$ consisting of all the sequences with finitely many non-zero elements, we get a faithful action of $\mathbb{G}$ with
\[
   \Phi^b x \triangleq (\prod_{k\in\mathbb{Z}} F_k^{b_k})x \;,
\]
where $\prod_{k\in\mathbb{Z}}$ denotes composition.


TITLE: Dirac Lagrangian in terms of left and right handed fields
QUESTION [2 upvotes]: When we define the operators $P_{L,R}=\frac{1\mp\gamma_{5}}{2}$, we are able to define right- and left-handed Dirac fields:
$$\psi=(P_{L}\psi+ P_{R}\psi)=:\psi_{L}+\psi_{R}$$
The corresponding Dirac-adjoints are therefore defined through
$$\overline{\psi}_{L,R}:=\overline{\psi}P_{L,R}$$
Plugging $\psi=\psi_{L}+\psi_{R}$ and $\overline{\psi}=\overline{\psi}_{L}+\overline{\psi}_{R}$ into the definitions of the Dirac Lagrangian  $$\mathcal{L}=i\overline{\psi}\gamma^{\mu}\partial_{\mu}\psi - m\overline{\psi}\psi$$ and using $P_{L}P_{R}=P_{R}P_{L}=0$, one gets
$$\mathcal{L}=i\overline{\psi}_{L}\gamma^{\mu}\partial_{\mu}\psi_{L}+i\overline{\psi}_{R}\gamma^{\mu}\partial_{\mu}\psi_{R} - m(\overline{\psi}_{R}\psi_{L}+\overline{\psi}_{L}\psi_{R})$$
This expression can be found in many QFT books.....
Now to my question...Isn't the mass term zero? Because
$$\overline{\psi}_{R}\psi_{L}=\overline{\psi}\underbrace{P_{R}P_{L}}_{=0}\psi=0$$
 and the same for the other term....

REPLY [5 votes]: Your mistake is in saying that $\overline{\psi_{L,R}} = \overline{\psi}P_{L,R}$.
In fact,
$$ \overline{\psi_{L,R}} = (P_{L,R}\psi)^† \gamma^0 = \overline{\psi}\gamma^0 P_{L,R}^† \gamma^0$$
$$ = \overline{\psi} P_{R,L}$$
To see why that last line is true we have to expand $P_{L,R} = (I\mp \gamma^5)/2$ and note that $(\gamma^5)^† = \gamma^5$, $(\gamma^0)^2 = I$, and $\{\gamma^0,\gamma^5\} = 0$


text:
\paragraph{Transductive Learning}\label{sec:problem-setting}

Let $\mathcal{X}$ and $\mathcal{Y}$ be spaces of feature vectors and labels, respectively.
Let $N\in \mathbb{N}_+$ be the sample size and $V:=[N]$ be the set of indices of the sample.
For each sample point $i\in V$, we associate a feature-label pair $(x_i, y_i)\in \mathcal{X} \times \mathcal{Y}$.
Let $\Vtrain$ and $\Vtest$ be the set of training and test samples, respectively, satisfying $\Vtrain \cap \Vtest = \emptyset$ and $\Vtrain \cup \Vtest = V$.
We denote the training and test sample sizes by $M:=|\Vtrain|$ and $U:=|\Vtest|$, respectively.
Given the collection of features $X=(x_i)_{i\in V}$ and labels $(y_i)_{i\in \Vtrain}$ for the training data, the task is to construct a predictor $h:\mathcal{X}\to \widehat{\mathcal{Y}}$ such that $h(x_i)$ is \textit{close} to $y_i$ for all $i\in \Vtest$ (we define it precisely in Section \ref{sec:optimization}).
Here, $\widehat{\mathcal{Y}}$ denotes the range of the predictor.
For later use, we define $Q := \frac{1}{M} + \frac{1}{U}$.

config: arxiv


text:
\begin{document}

\maketitle

\begin{abstract}
Given two elements of a vector space acted on by a reductive group, we ask whether they lie in the same orbit, and if not, whether one lies in the orbit closure of the other. We develop techniques to optimize the orbit and orbit closure algorithms and apply these to give a partial classification of orbit closure containments in the case of cubic surfaces with infinitely many singular points, which are known to fall into 13 normal forms. We also discuss the computational obstructions to completing this classification, and discuss tools for future work in this direction.
\end{abstract}

\section{Introduction}
Let $G$ be a reductive group over an algebraically closed field $k$ acting on a $k$-vector space $V$. Throughout most of this paper we will take $G$ to be the general linear group $GL(n,\C)$ and $V$ to be $\mbox{Sym}_d(\C^n)$, the space of homogeneous degree $d$ polynomials in $n$ variables. Given $v\in V$, we look at its orbit $G\cdot v$ under $G$, and the Zariski closure of its orbit $\overline{G\cdot v}$ in $V$.

For each $w\in V$, we may ask the following questions:

\begin{itemize}
    \item[] Is $w\in G\cdot v$?
    \begin{itemize}
        \item[(1)] If yes, find $g$ such that $w = g\cdot v$.
        \item[(2)] If no, give a certificate. We then ask: is $w\in \overline{G\cdot v}$?
        \begin{itemize}
            \item[-] If yes, find a 1-parameter family in $G\cdot v$ which converges to $w$.
            \item[-] If no, find $f\in I(G\cdot v)$ such that $f(w)\neq 0$
        \end{itemize}
    \end{itemize}
\end{itemize}

From now on, unless otherwise stated, the rank of a polynomial will refer to its \emph{Waring rank}.

This is the length of a shortest decomposition as a sum of powers of linear forms, the symmetric rank of the corresponding tensor~\cite{LanTei}.

\begin{exmp}
(Strict containment $G\cdot v \subsetneq \overline{G\cdot v}$). Consider the action of $G = GL(4,\C)$ on $V = \mbox{Sym}_3(\C^4)$ as a change of coordinates $g\cdot v = v\circ g$. The rank 3 polynomial $w = x_1^2x_2$ (see~\cite[Section 10.4]{Lan} or~\cite[Section 8]{LanTei}) lies in the orbit closure of the rank 6 polynomial $v = x_1x_2^2 + x_3x_4^2$ ~\cite[\S 97]{Segre}. By Chevalley's Theorem~\cite[Corollary 4.20]{191},

 the Zariski and Euclidean closures

coincide. Setting $x_1 = x_1$, $x_2 = x_2$, $x_3 = \epsilon x_3$, $x_4 = \epsilon x_4$, we get $v_{\epsilon} = x_1x_2^2 + \epsilon^3x_3x_4^2 \rightarrow w$ as $\epsilon \rightarrow 0$, but $w$ is not in the orbit of $v$ since their ranks do not agree.

This gives an example of when the orbit is not closed.
\end{exmp}

Our paper is organized as follows. We look at standard algorithms for orbits and orbit closures in Section \ref{section:algo} and implement them in Macaulay2 in Section \ref{section:m2-code}. In Section \ref{section:tricks}, we develop some tricks to optimize these Macaulay2 implementations. In Section \ref{section:infinitely-singular}, we give a partial classification of orbit closure containments for cubic surfaces with infinitely many singular points and finally, we discuss computational obstructions to completing this classification and discuss tools for future work in this direction.

Throughout this paper, we will use the notations $(f_1, \ldots, f_n)$, $\left<f_1, \ldots, f_n\right>$, and ideal$(f_1, \ldots, f_n)$ to denote the ideal generated by $f_1, \ldots, f_n$.

\section{The Algorithms}\label{section:algo}
Recall that $G$ is a reductive group over an algebraically closed field $k$ acting on a vector space $V$, and $v,w$ are elements of $V$. In this section, we give standard algorithms for deciding whether $w\in G\cdot v$ and $w\in \overline{G\cdot v}$.
\subsection{Is $w\in G\cdot v$?}
The following algorithm decides whether $w$ is in the orbit of $v$.

\bigskip
\begin{breakablealgorithm}
  \caption{Orbit containment}
    \KwIn{
    \begin{itemize}
        \item[-] a reductive group $G$ acting on a vector space $V$ over an algebraically closed field $k$ with basis $\{x_1,...,x_n\}$
        \item[-] $v, w\in V$
    \end{itemize}}
    \KwOut{
    \begin{itemize}
        \item[-] $J$, where $J =  \left\{ \begin{array}{rcl}
    (0) & \mbox{if} & w\in G\cdot v \\
    (1) & \mbox{if} & w\notin G\cdot v
    \end{array}\right.$
    \end{itemize}}
    \textbf{inOrbit}$(G,v,w)$
     \begin{itemize}
        \item[1.] Write $$g\cdot x_i = \sum_{j=1}^n g_{ij}x_j \text{ for each $i$},\ g = \left( \begin{array}{ccc} g_{11} & \dots & g_{1n} \\
        \vdots & \ddots \\
        g_{n1} & \dots & g_{nn} \end{array} \right)$$
        $$w = \sum_{i=1}^n w_ix_i$$
        $$v = \sum_{i=1}^n v_ix_i \Rightarrow g\cdot v = \sum_{i=1}^n v_i(\sum_{j=1}^n g_{ij}x_j) = \sum_{i=1}^n (\sum_{j=1}^n v_j g_{ji})x_i$$
        \item[2.] $I = \mbox{ideal}(\sum_{j=1}^n v_j g_{ji} - c_i | 1\leq i,j\leq n) + \mbox{ideal}(\det g - 1)$.
        \item[3.] Substitute the coefficients $c_i$ in $I$ by $w_i$.
        \item[4.] Eliminate the variables $g_{ij}$ to obtain the ideal $J$.
    \end{itemize}
 \label{algo:orbitContainment}
\end{breakablealgorithm}

\begin{proof}[Proof of correctness] Elements of $V$ can be written uniquely as $\sum_{i=1}^n c_ix_i$. Consider the polynomial map $G\rightarrow V$ given by $g\mapsto g\cdot v$. Its
graph is defined by the ideal $I = (\sum_{j=1}^n v_j g_{ji} - c_i | 1\leq i,j\leq n)$.

Since $w$ is in the orbit of $v$, there exists an invertible $g\in G$ such that $w = g\cdot v$. Equivalently, $w_i = \sum_{j=1}^n v_j g_{ji}$ for each $i$, i.e. $w$ is in the vanishing locus of the ideal $I$, so is in the set theoretic projection of $\mathcal{V}(I)$ onto $V$, where $\mathcal{V}(I)$ is the variety cut out by $I$. Substituting the coefficients $c_i$ in $I$ by $w_i$ sets up the system of equations, and eliminating the variables $g_{ij}$ solves for $g$. If $J = (1)$, then 1 is in the ideal obtained from $I$ by substituting the coefficients $c_i$ by $w_i$, so some combination of the equations results in an inconsistent equation, so a solution does not exist; otherwise $J = (0)$ and the equations are consistent, so there exists a solution $g$~\cite[Theorem 11.12, Derksen's Algorithm]{191}.
\end{proof}

\begin{exmp}
($G = GL(4,\C)$, $V = Sym_3(\C^4)$). Let
\begin{align*}
v &= x_1x_3x_4 + x_3^3 \\
w &= 125x_2^3 + 5x_1x_2x_3 + 525x_2^2x_3 + 7x_1x_3^2 + 745x_2x_3^2 + 357x_3^3 + 5x_1x_2x_4 +\\
& 75x_2^2x_4 + 8x_1x_3x_4 + 220x_2x_3x_4 + 163x_3^2x_4 + x_1x_4^2 + 15x_2x_4^2 + 23x_3x_4^2 + x_4^3
\end{align*}
where $w$ is obtained from $v$ by setting $x_1 := x_1 + 2x_3$, $x_2 := x_2$, $x_3 := 5x_2 + 7x_3 + x_4$, $x_4 = x_3 + x_4$. The following Macaulay2 code computes $J$~\cite{M2}.

\begin{footnotesize}
\begin{verbatim}
R = QQ[a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,d1,d2,d3,d4][x1,x2,x3,x4];
M = matrix{{a1,a2,a3,a4}, {b1,b2,b3,b4}, {c1,c2,c3,c4}, {d1,d2,d3,d4}};
f1 = 125*x2^3 + 5*x1*x2*x3 + 525*x2^2*x3 + 7*x1*x3^2 + 745*x2*x3^2 + 357*x3^3
      + 5*x1*x2*x4 + 75*x2^2*x4 + 8*x1*x3*x4 + 220*x2*x3*x4 + 163*x3^2*x4
      + x1*x4^2 + 15*x2*x4^2 + 23*x3*x4^2 + x4^3;
l1 = a1*x1 + a2*x2 + a3*x3 + a4*x4;
l2 = b1*x1 + b2*x2 + b3*x3 + b4*x4;
l3 = c1*x1 + c2*x2 + c3*x3 + c4*x4;
l4 = d1*x1 + d2*x2 + d3*x3 + d4*x4;
f2 = l1*l3*l4 + l3^3;
g = f1 - f2;
(N,C) = coefficients g;
I = minors(1,C) + ideal(det M - 1);
S = QQ[a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,d1,d2,d3,d4];
I = substitute(I,S);
time J = eliminate(I,{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,d1,d2,d3,d4});
\end{verbatim}
\end{footnotesize}
This computation gives $J = (0)$ as expected since $w$ is in the orbit of $v$. If we set $w = x_1^3 + x_2^3 + x_3^3$ instead, we get $J = (1)$, which is again expected since $w$ is not in the orbit of $v$ since their singular loci are not projectively equivalent (see Section \ref{singularities}).
\end{exmp}

\subsection{Is $w\in \overline{G\cdot v}$?}
The following algorithm decides whether $w$ is in the orbit closure of $v$.

\bigskip
\begin{breakablealgorithm}
\caption{Orbit closure containment}
\KwIn{
\begin{itemize}
    \item[-] a reductive group $G$ acting on a vector space $V$ over an algebraically closed field $k$ with basis $\{x_1,...,x_n\}$
    \item[-] $v, w\in V$
\end{itemize}}
\KwOut{
\begin{itemize}
    \item[-] $K$, where $K =  \left\{ \begin{array}{rcl}
(0) & \mbox{if} & w\in \overline{G\cdot v} \\
(1) & \mbox{if} & w\notin \overline{G\cdot v}
\end{array}\right.$
\end{itemize}}
\textbf{inOrbitClosure}$(G,v,w)$
 \begin{itemize}
    \item[1.] Same as Step 1 of Algorithm \ref{algo:orbitContainment}: Orbit Containment.
    \item[2.] $I = \mbox{ideal}(\sum_{j=1}^n v_j g_{ji} - c_i | 1\leq i,j\leq n)$.
    \item[3.] Eliminate the variables $g_{ij}$ to obtain the ideal $J$.
    \item[4.] Substitute the coefficients $c_i$ in $J$ by $w_i$ to obtain the ideal $K$.
\end{itemize}
 \label{algo:orbitClosureContainment}
\end{breakablealgorithm}

\begin{proof}[Proof of correctness] With notation as in Algorithm \ref{algo:orbitContainment}, the orbit of $v$ is given by the set theoretic projection $\pi$ of $\mathcal{V}(I)$ onto $V$. The orbit closure of $v$ is its Zariski (equals to Euclidean by Chevalley's Theorem)

closure, which by~\cite[Theorem 4.2]{191} is given by the elimination ideal $J = I\cap k[c_1, \cdots, c_n]$. Substituting the coefficients $c_i$ by $w_i$ tells whether $w$ is the zero locus of $J$~\cite[Theorem 11.12, Derksen's Algorithm]{191}.

Note that here we do not impose the condition det $G = 1$ since any matrix (invertible or not) is in the Euclidean closure of the set of invertible matrices. Indeed, if $w = \lim_{\epsilon \to 0} g_n\cdot v_n$ where $g_n$ is not necessarily invertible, since each $g_n = \lim_{\epsilon \to 0}g_{nm}$ where $g_{nm}$ is invertible, then $w = \lim_{\epsilon \to 0} g_{nm_n} \cdot v_n$ (for some $m_n$) can be written as a limit using only invertible matrices.
\end{proof}

\begin{exmp}
($G = GL(2,\C)$, $V = \mbox{Sym}_3(\C^2)$). Let
\begin{align*}
v &=  x_1^3 + x_1x_2^2\\
w &= x_1^2x_2
\end{align*}
The following Macaulay2 code computes $K$.

\begin{footnotesize}
\begin{verbatim}
R = QQ[c30,c21,c12,c03,a1,a2,b1,b2][x1,x2,x3,x4];
f1 = c30*x1^3 + c21*x1^2*x2 + c12*x1*x2^2 + c03*x2^3;
l1 = a1*x1 + a2*x2
l2 = b1*x1 + b2*x2
f2 = l1^3 + l1*l2^2;
g = f1 - f2;
(M,C) = coefficients g;
I = minors(1,C);
S = QQ[c30,c21,c12,c03,a1,a2,b1,b2];
I = substitute(I,S);
time J = eliminate(I,{a1,a2,b1,b2});
K = substitute(J,{c30=>0,c21=>1,c12=>0,c03=>0})
\end{verbatim}
\end{footnotesize}
This computation gives $K = (0)$, which means $w$ is in the orbit closure of $v$. To verify this, since $$x_1 x_2 = \lim_{\epsilon \to 0} \left( \frac{x_1^2 - (x_1 - \epsilon x_2)^2}{2\epsilon} \right),$$
$x_1 x_2$ can be written as a limit of polynomials of the form $y_1^2 + y_2^2$, hence we can write $x_1^2x_2$ as a limit of polynomials of the form $y_1^3 + y_1y_2^2$. Since we are working over $\C$, by Chevalley's Theorem, the Euclidean and Zariski closures of the image of the projection coincide, so $w\in \overline{G\cdot v}$. Reversing the roles of $v$ and $w$ gives $K = (1)$, so $v\notin \overline{G\cdot w}$ as expected since the stabilizer of $w$ has codimension lower than that of $v$ (see Section \ref{dimension}). Thus,
$w$ is in the orbit closure, but not in the orbit of $v$.
\end{exmp}

\section{A Macaulay2 Implementation for Cubic Surfaces}\label{section:m2-code}
In this section, we provide Macaulay2 implementations of the orbit and orbit closure algorithms for cubic surfaces, homogeneous degree 3 polynomials in 4 variables with complex coefficients, written $$v = \sum_{i+j+k+l = 3} c_{ijkl}x_1^ix_2^jx_3^kx_4^l.$$ The projective linear group $G = PGL(4, \C)$ acts on a cubic surface $v$ by $g\cdot v = v\circ g$ for each $g\in G$. We restrict ourselves to inputs with rational coefficients.

\subsection{Orbit} \label{orbit_algo}
The following Macaulay2 code computes whether $f_1$ is in the orbit of $f_2$: $f_1$ is in the orbit closure of $f_2$ iff $J = (0)$.
\begin{footnotesize}
\begin{verbatim}
R = QQ[a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,d1,d2,d3,d4][x1,x2,x3,x4];
M = matrix{{a1,a2,a3,a4}, {b1,b2,b3,b4}, {c1,c2,c3,c4}, {d1,d2,d3,d4}};
f1 = -- plug in f1 here
l1 = a1*x1 + a2*x2 + a3*x3 + a4*x4;
l2 = b1*x1 + b2*x2 + b3*x3 + b4*x4;
l3 = c1*x1 + c2*x2 + c3*x3 + c4*x4;
l4 = d1*x1 + d2*x2 + d3*x3 + d4*x4;
f2 = -- plug in f2 here, replacing x1 by l1, etc.
g = f1 - f2;
(M,C) = coefficients g;
I = minors(1,C);
I = I + (det M - 1);
S = QQ[a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,d1,d2,d3,d4];
I = substitute(I,S);
time J = eliminate(I,{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,d1,d2,d3,d4});
\end{verbatim}
\end{footnotesize}

\subsection{Orbit Closure} \label{orbit_closure_algo}
The following Macaulay2 code computes whether $f$ is in the orbit closure of $f_2$: $f$ is in the orbit closure of $f_2$ iff $K = (0)$.
\begin{footnotesize}
\begin{verbatim}
R = QQ[c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
       c2001,c1101,c1011,c0201,c1002,c0102,c0003,c0021,c0012,c0111,
       a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,d1,d2,d3,d4][x1,x2,x3,x4];
M = matrix {{x1^3, x1^2*x2, x1*x2^2, x2^3, x1^2*x3, x1*x2*x3, x2^2*x3, x1*x3^2,
       x2*x3^2, x3^3,x1^2*x4,x1*x2*x4,x1*x3*x4,x2^2*x4,x1*x4^2,x2*x4^2,x4^3,
       x3^2*x1,x3*x4^2,x2*x3*x4}}
C = matrix{{c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
       c2001,c1101,c1011,c0201,c1002,c0102,c0003,c0021,c0012,c0111}};
f1 = M*transpose(C);
f1 = f1_(0,0);
l1 = a1*x1 + a2*x2 + a3*x3 + a4*x4;
l2 = b1*x1 + b2*x2 + b3*x3 + b4*x4;
l3 = c1*x1 + c2*x2 + c3*x3 + c4*x4;
l4 = d1*x1 + d2*x2 + d3*x3 + d4*x4;
f2 = -- plug in f2 here, replacing x1 by l1, etc.
g = f1 - f2;
(M,C) = coefficients g;
I = minors(1,C);
S = QQ[c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
       c2001,c1101,c1011,c0201,c1002,c0102,c0003,c0021,c0012,c0111,
       a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,d1,d2,d3,d4];
I = substitute(I,S);
time J = eliminate(I,{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,d1,d2,d3,d4});
-- substitute the values of the coefficients by the coefficients of f
       (replace the 0s)
K = substitute(J,{c3000=>0,c2100=>0,c1200=>0,c0300=>0,c2010=>0,c1110=>0,c0210=>0,
       c1020=>0,c0120=>0,c2001=>0,c1101=>0,c0201=>0,c1002=>0,c0102=>0,c0030=>0,
       c0003=>0,c0021=>0,c0012=>0,c0111=>0})
\end{verbatim}
\end{footnotesize}

\begin{rmk}\label{rmk:justification-m2}
Here we justify the use of Macaulay2 for computations on inputs with rational coefficients. Indeed, the only nontrivial Macaulay2 routines used are \emph{substitute} and \emph{eliminate}.

By construction, the ideal $I$ has rational generators. The ideal obtained by specializing $I$ is generated by the specialization of each of the rational generators of $I$. Since the values we are substituting are rationals, substitution over the rationals is the same as substitution over the complex field.

For elimination, we refer to~\cite[Theorems 4.2, 4.5]{191}, restated here as Theorem \ref{thm:math191} for convenience.
\begin{thm}\label{thm:math191}
Let $\pi: k^n \to k^m$ be the projection $(a_1,\ldots,a_n) \mapsto (a_1,\ldots,a_m)$

onto the subspace $k^m$. Let $I\subset k[x_1,...,x_n]$ be an ideal and $V = \mathcal{V}(I)$ its variety in $k^n$, where $k$ is an algebraically closed field. Then its closed image in $k^m$ is the variety $\overline{\pi(V)} = \mathcal{V}(J)$ defined by the elimination ideal $J = I \cap k[x_1,...,x_m]$.

Moreover, if $\mathcal{G}$ is a lexicographic Grobner basis for $I$ in $k[x_1,...,x_n]$, then $J$ has as Grobner basis $\mathcal{G}' = \mathcal{G}\cap k[x_1,...,x_m]$.
\end{thm}
Since $\C$ is algebraically closed, the elimination ideal cuts out the image of the Zariski closure of the projection of a variety. We want to show that the elimination ideal over $\Q$ is generated by the same generators as the elimination ideal over $\C$. The Macaulay2 implementation of \emph{eliminate} involves computing a Grobner basis and intersecting it with $k[x_1,...,x_m]$. It suffices to show that if $I$ has a set of generators consisting of rational polynomials, then it has a Grobner basis consisting of rational polynomials. Since Buchberger's algorithm, which is used in Macaulay2 to compute Grobner bases, only involves rational operations, the resulting Grobner bases must consist of rational polynomials. So, this set of polynomials generate the elimination ideal over $\Q$ and over $\C$, justifying our use of \emph{eliminate}.

Substitution clearly terminates. Elimination terminates theoretically since Buchberger's algorithm terminates.
\end{rmk}

\section{Some Strategies for Reducing Computation Time}\label{section:tricks}

In both the algorithms for computing orbits and orbit closures, elimination is the only computationally expensive routine.

Here we compile a list of tricks that sometimes helps in obtaining a possibly non-constructive yes/no answer to the orbit and orbit closure problems.

We give some examples to show the significance of elimination in determining whether or not a computation terminates. The following code which shows that $x_1x_3x_4 + x_3^3$ is not in the orbit closure of $x_3x_4^2$, terminates quickly.

\begin{footnotesize}
\begin{verbatim}
R = QQ[c300,c210,c120,c030,c201,c111,c021,c102,c012,c003,
    a1,a3,a4,b1,b3,b4][x1,x3,x4];
M = matrix {{x1^3, x1^2*x3, x1*x3^2, x3^3, x1^2*x4, x1*x3*x4, x3^2*x4,
      x1*x4^2, x3*x4^2, x4^3}}
C = matrix{{c300,c210,c120,c030,c201,c111,c021,c102,c012,c003}};
f1 = M*transpose(C);
f1 = f1_(0,0);
l3 = a1*x1 + a3*x3 + a4*x4;
l4 = b1*x1 + b3*x3 + b4*x4;
f2 = l3^2*l4;
g = f1 - f2;
(M,C) = coefficients g;
I = minors(1,C);
S = QQ[c300,c210,c120,c030,c201,c111,c021,c102,c012,c012,c003,
    a1,a3,a4,b1,b3,b4];
I = substitute(I,S);
time J = eliminate(I,{a1,a3,a4,b1,b3,b4});
K = substitute(J,{c300=>0,c210=>0,c120=>0,c201=>0,
c021=>0,c102=>0,c012=>0,c003=>0})
\end{verbatim}
\end{footnotesize}

However, the following code which tells whether $x_1^2x_2 + x_1x_3x_4 + x_3^3$ is in the orbit closure of $x_1x_2^2 + x_3x_4^2$, was run for a day, got stuck on elimination, and did not terminate.

\begin{footnotesize}
\begin{verbatim}
R = QQ[c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
       c2001,c1101,c1011,c0201,c1002,c0102,c0003,c0021,c0012,c0111,
       a1,a2,a3,a4,b1,b3,c1,c2,c3,c4,d1,d3][x1,x2,x3,x4];
M = matrix {{x1^3, x1^2*x2, x1*x2^2, x2^3, x1^2*x3, x1*x2*x3, x2^2*x3,x1*x3^2,
       x2*x3^2, x3^3, x1^2*x4,x1*x2*x4,x1*x3*x4,x2^2*x4,x1*x4^2,x2*x4^2,x4^3,
       x3^2*x4,x3*x4^2,x2*x3*x4}}
C = matrix{{c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
       c2001,c1101,c1011,c0201,c1002,c0102,c0003,c0021,c0012,c0111}};
f1 = M*transpose(C);
f1 = f1_(0,0);
l1 = c1*x1 + c2*x2 + c3*x3 + c4*x4;
l2 = d1*x1 + d3*x3;
l3 = a1*x1 + a2*x2 + a3*x3 + a4*x4;
l4 = b1*x1 + b3*x3;
f2 = l2^2*l1 + l4^2*l3;
g = f1 - f2;
(M,C) = coefficients g;
I = minors(1,C);
S = QQ[c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
       c2001,c1101,c1011,c0201,c1002,c0102,c0003,c0021,c0012,c0111,
       a1,a2,a3,a4,b1,b3,c1,c2,c3,c4,d1,d3];
I = substitute(I,S);
time J = eliminate(I,{a1,a2,a3,a4,b1,b3,c1,c2,c3,c4,d1,d3}); -- proj to
       polynomials only involving c****'s
K = substitute(J,{c3000=>0,c1200=>0,c0300=>0,c2010=>0,c1110=>0,c0210=>0,c1020=>0,
       c0120=>0,c2001=>0,c1101=>0,c0201=>0,c1002=>0,c0102=>0,c0003=>0,c0021=>0,
       c0012=>0,c0111=>0,c2100=>1,c1011=>1,c0030=>1})
\end{verbatim}
\end{footnotesize}

We remark that the singular loci of $x_1^2x_2 + x_1x_3x_4 + x_3^3$ and $x_1x_2^2 + x_3x_4^2$ are the lines $[0:x_2:0:x_4]$ and $[x_1:0:x_3:0]$ respectively. If $x_1^2x_2 + x_1x_3x_4 + x_3^3$ is the limit of $\{f_n\}$ where $f_n\in G\cdot (x_1x_2^2 + x_3x_4^2)$, then the singular locus of $x_1^2x_2 + x_1x_3x_4 + x_3^3$ must be the limit of the singular loci of the $f_n$s. We will show in Example \ref{exmp:sub-elim-sub-example} that in this particular case, it suffices to consider elements of $G$ such that the second and forth coordinates are contained in the span of $x_1, x_3$.

\subsection{Sub-elim-sub}\label{sub-elim-sub}
\begin{lemma}\label{lemma:sub-elim-sub}
Let $I$ be an ideal in $k[\vec{x}, \vec{y}, \vec{z}, \vec{w}]$ where $k$ is a field and $\vec{x} = (x_1,...,x_m)$, $\vec{y} = (y_1,...,y_n)$, $\vec{z} = (z_1,...,z_l)$, $\vec{w} = (w_1,...,w_r)$. Let $K$ be the ideal obtained by first eliminating $\vec{z}$, then substituting $\vec{x} = \vec{a}$ and $\vec{y} = \vec{b}$. Let $M$ be the ideal obtained by first substituting $\vec{x} = \vec{a}$, eliminating $\vec{z}$, then substituting $\vec{y} = \vec{b}$. \\
Then, $K\subset M$.
\end{lemma}
Informally, this is saying that the ideal obtained by eliminating then substituting is contained in the ideal obtained by first substituting some variables, then eliminating, then substituting the remaining variables. Since $M$ has fewer variables than $K$, performing elimination on $M$ is easier. If $M = 0$, then we know $K = 0$, but if $M \neq 0$, we cannot say anything about $K$. This sometimes helps in the orbit closure problem since elimination is done before substitution, but not in the orbit problem where elimination is already performed last. However, it takes a lot of guessing and trial and error to determine the order of substitution and elimination which would result in a terminating elimination with $M$ as small as possible.

\begin{proof}[Proof of Lemma \ref{lemma:sub-elim-sub}]
Let $I = \left<r_1,...,r_s\right>$. Let the elimination ideal $\mbox{Elim}(I,\vec{z}) = I\cap k[\vec{x}, \vec{y}, \vec{w}]$ be generated by $t_1,...,t_u$. So, $$K = \left<t_1(\vec{a},\vec{b},\vec{w}),...,t_u(\vec{a},\vec{b},\vec{w})\right>.$$ If $f\in K$, write $f = \sum p_it_i(\vec{a},\vec{b},\vec{w})$ where $p_i\in k[\vec{w}]$.  The ideal obtained from $I$ after substituting $\vec{x} = \vec{a}$ is $$\mbox{Sub}(I,\vec{x}) = \left<r_1(\vec{a},\vec{y},\vec{z},\vec{w}),..., r_s(\vec{a},\vec{y},\vec{z},\vec{w})\right>.$$
Since $t_1,...,t_u\in \mbox{Elim}(I,\vec{z}) = I\cap k[\vec{x}, \vec{y}, \vec{w}]$,
$$t_1(\vec{a},\vec{y},\vec{w}),..., t_u(\vec{a},\vec{y},\vec{w})\in k[\vec{y}, \vec{w}]$$
$$\mbox{and } t_1(\vec{a},\vec{y},\vec{w}),..., t_u(\vec{a},\vec{y},\vec{w})\in \mbox{Sub}(I,\vec{x}),$$
so $$t_1(\vec{a},\vec{y},\vec{w}),..., t_u(\vec{a},\vec{y},\vec{w})\in \mbox{Sub}(I,\vec{x})\cap k[\vec{y},\vec{w}] = \mbox{Elim}(\mbox{Sub}(I,\vec{x}), \vec{z}),$$ so $$t_1(\vec{a},\vec{b},\vec{w}),..., t_u(\vec{a},\vec{b},\vec{w})\in \mbox{Sub}(\mbox{Elim}(\mbox{Sub}(I,\vec{x}), \vec{z}), \vec{y}) = M.$$
Thus, $f\in M$.
\end{proof}

The reverse containment does not hold in general. For example, consider $I = \left<y+xz\right>$ in $k[x,y,z]$. Eliminating $z$ from $I$ gives the zero ideal, so the next substitutions do not matter and $K=(0)$. On the other hand, substituting $x=0$ to $I$ gives the ideal $\left<y\right>$. Eliminating $z$ from this ideal has no effect, and substituting $y=1$ results in $M=(1)\nsubseteq K$.\\

The following example shows how to use \emph{sub-elim-sub} to solve the above computation in determining whether $x_1^2x_2 + x_1x_3x_4 + x_3^3$ is in the orbit closure of $x_1x_2^2 + x_3x_4^2$.

\begin{exmp} \label{exmp:sub-elim-sub-example}
The claim allows us to reorder the substitution and elimination process as follows, resulting in a terminating algorithm.

\begin{footnotesize}
\begin{verbatim}
R = QQ[c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
       c2001,c1101,c1011,c0201,c1002,c0102,c0003,c0021,c0012,c0111,
       a1,a2,a3,a4,b1,b3,c1,c2,c3,c4,d1,d3][x1,x2,x3,x4];
M = matrix {{x1^3, x1^2*x2, x1*x2^2, x2^3, x1^2*x3, x1*x2*x3, x2^2*x3,x1*x3^2,
            x2*x3^2, x3^3, x1^2*x4, x1*x2*x4, x1*x3*x4, x2^2*x4, x1*x4^2, x2*x4^2,
            x4^3, x3^2*x4, x3*x4^2, x2*x3*x4}}
C = matrix{{c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,c2001,
            c1101,c1011,c0201,c1002,c0102,c0003,c0021,c0012,c0111}};
f1 = M*transpose(C);
f1 = f1_(0,0);
l1 = c1*x1 + c2*x2 + c3*x3 + c4*x4;
l2 = d1*x1 + d3*x3;
l3 = a1*x1 + a2*x2 + a3*x3 + a4*x4;
l4 = b1*x1 + b3*x3;
f2 = l2^2*l1 + l4^2*l3;
g = f1 - f2;
(M,C) = coefficients g;
I = minors(1,C);
S = QQ[c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
       c2001,c1101,c1011,c0201,c1002,c0102,c0003,c0021,c0012,c0111,
       a1,a2,a3,a4,b1,b3,c1,c2,c3,c4,d1,d3];
I = substitute(I,S);
J = substitute(I,{c1200=>0,c0300=>0,c0210=>0,c1101=>0,c0201=>0,c0111=>0,c1002=>0,
    c0102=>0,c0012=>0,c0003=>0,c3000=>0,c2010=>0,c1110=>0,c1020=>0,c0021=>0});
time J = eliminate(J,{a1,a2,a3,a4,b1,b3,c1,c2,c3,c4,d1,d3});
K = substitute(J,{c0120=>0,c2001=>0,c2100=>1,c1011=>1,c0030=>1})
\end{verbatim}
\end{footnotesize}
The last subsitution is actually not necessary since $J$ is already $(0)$. Applying the claim to $M_{\text{claim}}=K$ and $K_{\text{claim}}=K_{\text{bad}}=K$ from the previous, non-terminating code, we get $K_{\text{bad}}\subset K = (0)$, so $K_{\text{bad}} = (0)$, showing that $x_1^2x_2 + x_1x_3x_4 + x_3^3$ is in the orbit closure of $x_1x_2^2 + x_3x_4^2$. Note that since $x_1^2x_2 + x_1x_3x_4 + x_3^3$ is in the orbit closure of $x_1x_2^2 + x_3x_4^2$ under elements of $G$ such that the second and fourth coordinates are contained in the span of $x_1, x_3$, it is also contained in the orbit closure of $x_1x_2^2 + x_3x_4^2$ under all elements of $G$.
\end{exmp}

\subsection{Looking at Singularities}\label{singularities}
A singular point of a homogenous degree $d$ polynomial $f$ in $n$ variables is a point $p\in \mathcal{V}(f)$ at which all partial derivatives of $f$ vanish. It is a point at which the tangent space $T_p\mathcal{V}(f)$ has dimension higher than that of the variety $\mathcal{V}(f)$.

If $\nabla f = 0$, then $\nabla (g\cdot f) = \nabla (f\circ g) = (\nabla f) \circ Dg = (\nabla f) \circ g = g\cdot \nabla f$ where the second to last equality is due to the fact that a linear function is its own derivative. So, if $g\cdot v = w$, then $g$ must map the singular locus of $v$ to the singular locus of $w$. In particular, if the singular loci of $v$ and $w$ are not projectively equivalent, then $v$ and $w$ do not lie in the same orbit.

In the case of cubic surfaces, the singular locus is cut out by 4 homogeneous degree 2 polynomials. By orthonormalization, every symmetric bilinear form  can be transformed into the form $\epsilon x_1^2 + \dots + \epsilon x_n^2$ where $\epsilon \in \{0, 1\}$, which helps in seeing whether the singular loci are projectively equivalent.

\subsection{Counting Dimensions}\label{dimension}
Clearly, if the dimensions $\dim (G\cdot v)\neq \dim (G\cdot w)$, then the orbits $G\cdot v$ and $G\cdot w$ are distinct, and thus disjoint. For orbit closures, recall that we are working over $\C$. This allows us to use Chevalley's Theorem which says that the Zariski and Euclidean closures coincide.
\begin{lemma}
Let $G, v, w$ be as before, $G\cdot v \neq G\cdot w$.
\begin{itemize}
    \item [(i)] If $w\in \overline{G\cdot v}$, then $\overline{G\cdot w} \subset \overline{G\cdot v}$.
    \item [(ii)] If $\dim \overline{G\cdot v} \leq \dim \overline{G\cdot w}$, then $w\notin \overline{G\cdot v}$.
\end{itemize}
\end{lemma}
\begin{proof}
To show (i), let $\{g_n\cdot v\}\longrightarrow w$. Then for each $g\in G$, $\{gg_n\cdot v\}\longrightarrow g\cdot w$, so $G\cdot w\subset \overline{G\cdot v}$. Since $\overline{G\cdot v}$ is closed, it contains the closure $\overline{G\cdot w}$ of $G\cdot w$.

For (ii), if $\dim \overline{G\cdot v} < \dim \overline{G\cdot w}$, then $\overline{G\cdot v} \not \supset \overline{G\cdot w}$ since a manifold cannot contain a submanifold of higher dimension, thus $w\notin \overline{G\cdot v}$ by $(i)$.

If $\dim \overline{G\cdot v} = \dim \overline{G\cdot w}$, suppose by contradiction that $w\in \overline{G\cdot v}$, so $\overline{G\cdot w} \subset \overline{G\cdot v}$. By Chevalley's Theorem, the image of a polynomial map is a constructible set, a finite union of differences of varieties. Write $G\cdot v = (U_1-V_1)\cup \dots \cup (U_k-V_k) = (U_1-U_1\cap V_1)\cup \dots \cup (U_k-U_k\cap V_k)$ where each $U_i-V_i\neq \emptyset$. By decomposing $U_1,\dots, U_k$ into their irreducible components, we may assume $U_1,\dots, U_k$ are irreducible. Since $U_i\cap V_i$ is a proper closed subset, $U_i - U_i\cap V_i$ is an open dense subset of $U_i$, so $\overline{G\cdot v} = \bigcup_{i=1}^k \overline{U_i}$. Moreover, $\dim U_i\cap V_i\leq \dim U_i - 1$ since $U_i\cap V_i$ is a proper subvariety of the irreducible variety $U_i$, so has empty interior. Since $G\cdot v \neq G\cdot w$, $G\cdot v \cap G\cdot w = \emptyset$, so $\overline{G\cdot w}\subset \overline{G\cdot v} - G\cdot v \subset \bigcup_{i=1}^k (U_i\cap V_i)$ thus $\dim \overline{G\cdot w} \leq \dim \bigcup_{i=1}^k (U_i\cap V_i) \leq \mbox{max}_{i=1}^k (\dim U_i\cap V_i) \leq \mbox{max}_{i=1}^k (\dim U_i) - 1\leq \dim \overline{G\cdot v} - 1 < \dim \overline{G\cdot w}$, a contradiction, hence proving the equality case of $(ii)$.
\end{proof}

We now provide Macaulay2 code to compute the dimension of the orbit closure of cubic surfaces over $\C$. Here, $I$ is the stabilizer of $f$, so by~\cite[Proposition 21.4.3]{TauYu}, the codimension of $I$ is the dimension of the orbit of $f$.

\begin{footnotesize}
\begin{verbatim}
    R = QQ[m_(1,1)..m_(4,4)][x_1..x_4];
    M = mutableMatrix(R,4,4);
    for i to 3 do ( for j to 3 do (
    M_(i,j) = m_(i+1,j+1);
    ); );
    M = matrix M;
    for i from 1 to 4 do (
        y_i = 0;
        for j from 1 to 4 do (
    y_i = y_i + m_(i,j)*x_j;
    );
        );
    f = -- plug in f here with variables x1, ..., x4
    g = substitute(f,{x_1=>y_1,x_2=>y_2,x_3=>y_3,x_4=>y_4});
    F = f-g;
    (Mon,C) = coefficients F;
    I = minors(1,C);
    S = QQ[m_(1,1)..m_(4,4)];
    I = substitute(I,S);
    codim I
\end{verbatim}
\end{footnotesize}

\section{Cubic Surfaces with Infinitely Many Singular Points}\label{section:infinitely-singular}
In this section, we apply some of the techniques in Section \ref{section:tricks} to compute orbit closure containments for cubic surfaces with infinitely many singular points under the action of the projective linear group $PGL(4,\C)$. From~\cite{CGV,Sei},~\cite[\S 97]{Segre} and~\cite[Section 8]{LanTei}, there are only finitely many normal forms of such cubic surfaces, given in Table \ref{table:infinite_singularities_normal_form}. Note that these normal forms are completely characterized by their ranks and singularities, so each normal form corresponds to a distinct orbit.

\begin{table}[ht]
\centering
\begin{tabular}{c|c|c|c|c|c}
No & Label & Rank & Normal form & Singularity & Dim \\ \hline
1. & 1A & 1 & $x_1^3$ & plane $[0:x_2:x_3:x_4]$ & 4 \\
2. & 2A & 2 & $x_1^3 + x_2^3$ & line $[0:0:x_3:x_4]$ & 8 \\
3. & 3A & 3 & $x_1^2 x_2$ & plane $[0:x_2:x_3:x_4]$ & 7 \\
4. & 4A & 4 & $x_2^2 x_3 - x_1^3 - x_1^2 x_3$ & line $[0:0:x_3:x_4]$ & 12 \\
5. & 4B & 4 & $x_2^2 x_3 - x_1^3$ & line $[0:0:x_3:x_4]$ & 11 \\
6. & 4C & 4 & $x_1 (x_1^2 + x_2 x_3)$ & union of 2 lines & 11\\ &&&& $[0:0:x_3:x_4]\cup [0:x_2:0:x_4]$\\
7. & 4D & 4 & $x_1 x_2 x_3$ & union of 3 lines & 10 \\
&&&& $[0:0:x_3:x_4]\cup [0:x_2:0:x_4]$\\
&&&& $\cup [x_1:0:0:x_4]$\\
8. & 5A & 5 & $x_2 (x_1^2 + x_2 x_3)$ & line $[0:0:x_3:x_4]$ & 10 \\
9. & 6A & 6 & $x_1 (x_1^2 + x_2^2 + x_3^2 + x_4^2)$ & $x_1=0$, $x_2^2 + x_3^2 + x_4^2 = 0$ & 13 \\
10. & 6B & 6 & $x_1(x_2^2 + x_3^2 + x_4^2)$ & $[1:0:0:0]\cup \{x_2^2 + x_3^2 + x_4^2 = 0\}$ & 12 \\
11. & 6C & 6 & $x_1 x_2^2 + x_3 x_4^2$ & line $[x_1:0:x_3:0]$ & 14 \\
12. & 7A & 7 & $x_1 (x_1 x_2 + x_3^2 + x_4^2)$ & $x_1=0$, $x_3^2 + x_4^2 = 0$ & 12 \\
13. & 7B & 7 & $x_1^2 x_2 + x_1 x_3 x_4 + x_3^3$ & line $[0:x_2:0:x_4]$ & 13
\end{tabular}
\caption{Normal forms of cubic surfaces with infinitely many singular points. Note: "Dim" denotes the dimension of the orbit closure.}
\label{table:infinite_singularities_normal_form}
\end{table}

We give a partial classification of the orbit closure containments for these normal forms in Table \ref{table:infinite_singularities_orbit_closure}. We will use the notation (row, column): a \cmark means that the orbit closure of ``row'' is contained in that of ``column'', while a \xmark indicates otherwise.

\begin{table}[ht]
\centering
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c|c}
Label & 1A & 2A & 3A & 4A & 4B & 4C & 4D & 5A & 6A & 6B & 6C & 7A & 7B \\ \hline
1A & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark \\ \hline
2A & \gxmark & \cmark & \gxmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark \\ \hline
3A & \gxmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark \\ \hline
4A & \gxmark & \gxmark & \gxmark & \cmark & \gxmark & \gxmark & \gxmark & \gxmark & & \gxmark & \cmark & \gxmark & \\ \hline
4B & \gxmark & \gxmark & \gxmark & \cmark & \cmark & \gxmark & \gxmark & \gxmark &&& \cmark && \cmark \\ \hline
4C & \gxmark & \gxmark & \gxmark & \cmark & \gxmark & \cmark & \gxmark & \gxmark & \cmark & \cmark & \cmark & \cmark & \cmark \\ \hline
4D & \gxmark & \gxmark & \gxmark & \cmark & & \cmark & \cmark & \gxmark & \cmark & \cmark & \cmark & \cmark & \cmark \\ \hline
5A & \gxmark & \gxmark & \gxmark & \cmark & \cmark & \cmark & \gxmark & \cmark & \cmark & \cmark & \cmark & \cmark & \cmark \\ \hline
6A & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \cmark & \gxmark & & \gxmark & \gxmark \\ \hline
6B & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \cmark & \cmark & & \gxmark & \\ \hline
6C & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \cmark & \gxmark & \gxmark \\ \hline
7A & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \cmark & \gxmark & & \cmark & \\ \hline
7B & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \gxmark & \cmark & \gxmark & \cmark
\end{tabular}
\caption{Normal forms of cubic surfaces with infinitely many singular points}
\label{table:infinite_singularities_orbit_closure}
\end{table}

\begin{itemize}
    \item [Justification:]
    A \textcolor{gray}{grey} entry indicates that the result is due to a dimension argument.

    The diagonal entries are trivial.
    \item [Row 1:]
    (1A, 1A), (1A, 2A), (1A, 4A), (1A, 4B), (1A, 4C), (1A, 6A), (1A, 7B) are clear.

    (1A, 3A): $x_1^3 = \lim_{\epsilon \to 0} x_1^2(x_1+\epsilon x_2)$.

    (1A, 4D): $x_1^3 = \lim_{\epsilon \to 0} x_1(x_1 + \epsilon x_2)(x_1 + \epsilon x_3)$.

    (3A, 5A), (3A, 6B), (3A, 6C), (3A, 7A) imply (1A, 5A), (1A, 6B), (1A, 6C), (1A, 7A) respectively.

    \item [Row 2:]
    (2A, 4B): $x_1^3 + x_2^3 = \lim_{\epsilon \to 0} x_2^2(x_2 + \epsilon x_3) - (-x_1)^3$.

    (2A, 4A): (2A, 4B) and (4B, 4A) $\Rightarrow$ (2A, 4A).

    (2A, 4C), (2A, 4D), (2A, 5A): Macaulay2 computations.
    \begin{footnotesize}
    \begin{verbatim}
        R = QQ[c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
            a1,a2,a3,b1,b2,b3,c1,c2,c3][x1,x2,x3];
        M = matrix {{x1^3, x1^2*x2, x1*x2^2, x2^3, x1^2*x3, x1*x2*x3, x2^2*x3,
            x1*x3^2, x2*x3^2, x3^3}}
        C = matrix{{c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030}};
        f1 = M*transpose(C);
        f1 = f1_(0,0);
        l1 = a1*x1 + a2*x2 + a3*x3;
        l2 = b1*x1 + b2*x2 + b3*x3;
        l3 = c1*x1 + c2*x2 + c3*x3;
        f2 = l1*(l1^2 + l2*l3); -- l1*l2*l3, l2*(l1^2 + l2*l3) respectively
        g = f1 - f2;
        (M,C) = coefficients g;
        I = minors(1,C);
        S = QQ[c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
            a1,a2,a3,b1,b2,b3,c1,c2,c3];
        I = substitute(I,S);
        J = substitute(I,{c3000=>1,c2100=>0,c1200=>0,c0300=>1,c2010=>0,c1110=>0,
            c0210=>0,c1020=>0,c0120=>0,c0030=>0});
        time K = eliminate(J,{a1,a2,a3,b1,b2,b3,c1,c2,c3});
    \end{verbatim}
    \end{footnotesize}
    (2A, 6B), (2A, 7A): We use the same Macaulay2 code as (2A, 4C), replacing f2 by $l_1(l_2^2 + l_3^2),\ l_1(l_1l_2 + l_3^2)$ respectively. Since the former is in the orbit closure of 6B and the latter in that of 7A, we get (2A, 6B), (2A, 7A).

    (2A, 6A): (2A, 6B) and (6B, 6A) $\Rightarrow$ (2A, 6A).

    (2A, 7B): $x_1^3 + x_2^3 = \lim_{\epsilon \to 0} x_1^2(x_1 + \epsilon x_2) + x_1(x_2 + \epsilon x_3)\epsilon x_4 + (x_2 + \epsilon x_3)^3$.

    (2A, 6C): (2A, 7B) and (7B, 6C) $\Rightarrow$ (2A, 6C).

    \item [Row 3:]
    (3A, 2A): $\lim_{\epsilon \to 0} \frac{x_1^3 + (-x_1 + \epsilon x_2)^3}{3\epsilon} = x_1^2x_2.$

    (3A, 4A), (3A, 4B), (3A, 4C), (3A, 4D), (3A, 5A), (3A, 6A), (3A, 6B), (3A, 6C), (3A, 7A), (3A, 7B): Inherit from 2A.

    \item [Row 4:]
    (4A, 6C): $\lim_{\epsilon \to 0}x_3x_2^2 + (-x_1-x_3)(x_1+\epsilon x_4)^2 = x_2^2x_3 - x_1^3 - x_1^2x_3.$

    \item [Row 5:]
    (4B, 4A): $\lim_{\epsilon \to 0}(\frac{x_2}{\epsilon})^2(\epsilon^2x_3) - x_1^3 - x_1^2(\epsilon^2 x_3) = x_2^2x_3 - x_1^3.$

    (4B, 6C): Inherit from 4A.

    (4B, 7B): $\lim_{\epsilon \to 0}x_2^2x_3 + x_2(-x_1)(\epsilon x_4) + (-x_1)^3 = x_2^2x_3 - x_1^3.$

    \item [Row 6:]
    (4C, 4A): $\lim_{\epsilon \to 0} -(-x_1)^3 + \frac{x_3}{2\epsilon}({-(-x_1)^2 + (x_1 + \epsilon x_2)^2)} = x_1(x_1^2 + x_2x_3).$

    (4C, 6B): $\lim_{\epsilon \to 0}x_1\left(\frac{x_2^2 + (i(x_2-\epsilon x_3))^2}{2\epsilon} + (x_1 + \epsilon x_4)^2 \right) = x_1x_2x_3 + x_1^3.$

    (4C, 6A): Inherit from 6B.

    (4C, 7A): Let $y_1 = x_1,\ y_2 = x_1 + \epsilon x_4,\ y_3 = \frac{x_2}{\sqrt{2\epsilon}},\ y_4 = \frac{i(x_2 - \epsilon x_3)}{\sqrt{2\epsilon}}$. Then, $\lim_{\epsilon \to 0}y_1(y_1y_2 + y_3^2 + y_4^2) = x_1(x_1^2 + x_2x_3).$

    (4C, 7B): $\lim_{\epsilon \to 0} x_1^2(\epsilon x_4) + x_3x_1x_2 + x_1^3 = x_1x_2x_3 + x_1^3.$

    (4C, 6C): Inherit from 7B.

    \item [Row 7:]
    (4D, 4A): $\lim_{\epsilon \to 0} ((\epsilon(x_1 + \epsilon x_2))^2\frac{x_3}{2\epsilon^3} - (\epsilon x_1)^3 - (\epsilon x_1)^2\frac{x_3}{2\epsilon^3} = x_1x_2x_3.$

    (4D, 4C): $\lim_{\epsilon \to 0}\frac{(\epsilon x_1)^3 + \epsilon x_1x_2x_3}{\epsilon} = x_1x_2x_3.$

    (4D, 6B): $\lim_{\epsilon \to 0} x_1\left(\frac{x_2^2 + (i(x_2 - \epsilon x_3))^2}{2\epsilon} + \epsilon x_4^2\right) = x_1x_2x_3.$

    (4D, 6A): Inherit from 6B.

    (4D, 7A): $\lim_{\epsilon \to 0} x_1\left(x_1(\epsilon x_4) + \frac{x_2^2 + (i(x_2 - \epsilon x_3))^2}{2\epsilon}\right) = x_1x_2x_3.$

    (4D, 7B): $\lim_{\epsilon \to 0} \frac{x_1^2(\epsilon^2 x_4) + x_1(\epsilon x_3)x_2 + (\epsilon x_3)^3}{\epsilon} = x_1x_2x_3.$

    (4D, 6C): Inherit from 7B.

    \item [Row 8:]
    (5A, 4B): Macaulay2 computation.
    \begin{footnotesize}
    \begin{verbatim}
        R = QQ[c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
               a1,a2,a3,b1,b2,b3,c1,c2,c3][x1,x2,x3];
        M = matrix {{x1^3, x1^2*x2, x1*x2^2, x2^3, x1^2*x3, x1*x2*x3, x2^2*x3, x1*x3^2,
               x2*x3^2, x3^3}}
        C = matrix{{c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030}};
        f1 = M*transpose(C);
        f1 = f1_(0,0);
        l1 = a1*x1 + a2*x2 + a3*x3;
        l2 = b1*x1 + b2*x2 + b3*x3;
        l3 = c1*x1 + c2*x2 + c3*x3;
        f2 = l2^2*l3 - l1^3
        g = f1 - f2;
        (M,C) = coefficients g;
        I = minors(1,C);
        S = QQ[c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
               a1,a2,a3,b1,b2,b3,c1,c2,c3];
        I = substitute(I,S);
        J = substitute(I,{c3000=>0,c1200=>0,c0300=>0,c2010=>0});
        time K = eliminate(J,{a1,a2,a3,b1,b2,b3,c1,c2,c3});
        K = substitute(K,{c2100=>1,c0210=>1,c1110=>0,c1020=>0,c0120=>0,c0030=>0})
    \end{verbatim}
    \end{footnotesize}

    (5A, 4A): Inherit from 4B.

    (5A, 4C): Macaulay2 computation.
    \begin{footnotesize}
    \begin{verbatim}
        R = QQ[c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
               a1,a2,a3,b1,b2,b3,c1,c2,c3][x1,x2,x3];
        M = matrix {{x1^3, x1^2*x2, x1*x2^2, x2^3, x1^2*x3, x1*x2*x3, x2^2*x3,
               x1*x3^2, x2*x3^2, x3^3}}
        C = matrix{{c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030}};
        f1 = M*transpose(C);
        f1 = f1_(0,0);
        l1 = a1*x1 + a2*x2 + a3*x3;
        l2 = b1*x1 + b2*x2 + b3*x3;
        l3 = c1*x1 + c2*x2 + c3*x3;
        f2 = l1^3 + l1*l2*l3
        g = f1 - f2;
        (M,C) = coefficients g;
        I = minors(1,C);
        S = QQ[c3000,c2100,c1200,c0300,c2010,c1110,c0210,c1020,c0120,c0030,
               a1,a2,a3,b1,b2,b3,c1,c2,c3];
        I = substitute(I,S);
        J = substitute(I,{c3000=>0,c1200=>0,c0300=>0,c2010=>0,c1110=>0,c1020=>0});
        time K = eliminate(J,{a1,a2,a3,b1,b2,b3,c1,c2,c3});
        K = substitute(K,{c2100=>1,c0210=>1,c0120=>0,c0030=>0})
    \end{verbatim}
    \end{footnotesize}

    (5A, 6B): $\lim_{\epsilon \to 0} x_2\left(x_1^2 + \frac{x_3^2 + (i(x_3 - \epsilon x_2))^2}{2\epsilon}\right) = x_2(x_1^2 + x_2x_3).$

    (5A, 6A): Inherit from 6B.

    (5A, 7A): $\lim_{\epsilon \to 0} x_2(x_2x_3 + x_1^2 + (\epsilon x_4)^2) = x_2(x_1^2 + x_2x_3).$

    (5A, 7B): Inherit from 4B.

    (5A, 6C): Inherit from 7B.

    \item [Row 9:]
    (6B, 6A): $\lim_{\epsilon \to 0} \frac{\epsilon x_1((\epsilon x_1)^2 + x_2^2 + x_3^2 + x_4^2)}{\epsilon} = x_1(x_2^2 + x_3^2 + x_4^2).$

    \item [Row 10:]
    \item [Row 12:]
    (7A, 6A): Let $y_1 = \frac{x_1}{\sqrt{2}\sqrt[3]{\epsilon}},\ y_2 = \frac{i(x_1 - \epsilon x_2)}{\sqrt{2}\sqrt[3]{\epsilon}},\ y_3 = \sqrt[4]{2}\sqrt[6]{\epsilon}x_3,\ y_4 = \sqrt[4]{2}\sqrt[6]{\epsilon}x_4$.
    Then $\lim_{\epsilon \to 0}y_1(y_1^2 + y_2^2 + y_3^2 + y_4^2) = x_1(x_1x_2 + x_3^2 + x_4^2).$

    \item [Row 13:]
    (7B, 6C): This is Example \ref{exmp:sub-elim-sub-example}.
\end{itemize}

There are still 11 ordered pairs (left blank) for which we are unable to compute the orbit closure containment at this time. For these cases, either there are four variables involved causing elimination to not terminate, or the dimensions of the orbits of the two cubic surfaces considered differ only by one, so the guessing in \emph{sub-elim-sub} is hard.

Nevertheless, we obtain a stronger statement of~\cite[Corollary 3.4]{AE}.

\medskip
\noindent \textbf{``Corollary 3.4''} A general cubic surface with infinitely many singular points has rank six.

\begin{proof}
There are finitely many orbits of cubic surfaces with infinitely many singular points. All the normal forms of cubic surfaces with infinitely many singular points are contained in the orbit closures of either $x_1(x_1^2 + x_2^2 + x_3^2 + x_4^2)$ or $x_1x_2^2 + x_3x_4^2$, which have rank six.
\end{proof}

Out of the 11 cases for which we are unable to decide the orbit closure containments, only 1 case involves 3 variables while the other 10 involve 4 variables. As mentioned in Remark \ref{rmk:justification-m2}, the Macaulay2 implementation of \emph{eliminate} involves computing a Gröbner basis, which is done using Buchberger's algorithm. Buchberger's algorithm is slow in general, especially when the number of variables is large.

We would also like to note that in~\cite[Theorem 2.12]{Popov}, the author provides an algorithm which reduces the orbit closure problem to checking the consistency of a system of linear equations. With notation as in~\cite{Popov}, for the case of cubic surfaces, after reduction to the conic case~\cite[2.7]{Popov}, we have $V = $ the 20-dimensional vector space of cubic surfaces, $G = GL(4, \C)$, and $\rho: G \to \mbox{Mat}_{20,20}(\C)$ is the matrix representation of $G$, i.e. $\rho(g)$ is the matrix of the linear transformation $V\to V$, $v\mapsto g\cdot v$ with respect to the monomial basis $\{x_1^ix_2^jx_3^kx_4^l \vert i+j+k+l = 3\}$.

The algorithm takes as input $d = \deg \rho (G)$. According to an (unpublished) computation done by Hanieh Keneshlou and Khazhgali Kozhasov, this degree is very large: 4306472. Since step 2 of the algorithm~\cite[2.11]{Popov} involves a generic polynomial of degree $2d-2$, for the case of cubic surfaces, it does not make the orbit closure problem easier.

As Bernd Sturmfels suggested, another approach for future projects to tackle this problem would be numerical algebraic geometry (see e.g.~\cite{NumAG} or~\cite{Bertini}).  This approach has been recently used to great success in such papers as~\cite{3264}.

\bigskip
\noindent \textbf{Acknowledgements}
We would like to thank Ralph Morrison for helpful guidance and suggestions throughout the project. We would also like to thank Anna Seigal for helpful conversation and for providing the codes for orbit closure and stabilizer from a previous project. We are also thankful to Hanieh Keneshlou and Khazhgali Kozhasov for computing the degree 4306472. Last but not least, we are really grateful to Bernd Sturmfels for helpful discussions and for the opportunity to work on this project.