text:
\begin{document}

\begin{abstract}
Marius T\u{a}rn\u{a}uceanu described the finite groups $G$ having $|G|-1$
cyclic subgroups.
We describe the finite groups $G$ having $|G|-\Delta$ cyclic subgroups
for $\Delta=2, 3, 4$ and $5$.
\end{abstract}

\maketitle

\section{Introduction}

Throughout this paper, a cyclic group of order $n$ is denoted $C_n$, and
the dihedral group of order $2n$ is denoted $D_{2n}$.
When we write $H\semidirect K$ we include the possibility that
the semidirect product is a direct product.
In \cite{tuarn},
Marius T\u{a}rn\u{a}uceanu proved the following theorem.
\begin{thm}[T\u{a}rn\u{a}uceanu] A finite group $G$ has $|G|-1$
cyclic subgroups if and only if $G$ is isomorphic to
one of the following groups:
	$C_3$, $C_4$, $S_3$, or $D_8$.
\end{thm}

Let $G$ be a finite group, and let $C(G)$ denote the poset of
cyclic subgroups of $G$.
We define  $\Delta(G)$, or just $\Delta$ if the group is understood, to be
the difference between the order of $G$ and the number of cyclic subgroups of $G$:
$$\Delta(G)=|G|-|C(G)|.$$

It is known that $\Delta=0$ if and only if
$G$ is an elementary abelian $2$-group, i.e.,
$G=C_2^n$ for some $n$.

In \cite{tuarn} where T\u{a}rn\u{a}uceanu described all groups
satisfying $\Delta=1$, he also
posed the following natural open problem.

\begin{problem*} Describe the finite groups $G$ having $|G|-\Delta$
cyclic subgroups, where $2\le \Delta\le |G|-1$.
\end{problem*}

In this paper we solve this problem for $\Delta=2, 3, 4$ and $5$.
More specifically we prove the following theorems.

\begin{thm} A finite group $G$ has exactly $|G|-2$ cyclic subgroups
	if and only if $G$ is isomorphic to one of the following groups:
	$C_4\times C_2$, $D_8\times C_2$, $C_6$, or $D_{12}$.
\end{thm}

\begin{thm} A finite group $G$ has exactly $|G|-3$ cyclic subgroups
	if and only if $G$ is isomorphic to one of the following groups:
	$Q_8$, $C_5$, or $D_{10}$.
\end{thm}

\begin{thm} A finite group $G$ has exactly $|G|-4$ cyclic subgroups
	if and only if $G$ is isomorphic to one of the following eleven groups:
	$C_4\times C_2\times C_2$,
	$C_2\times C_2\times D_8$,
	$(C_2\times C_2)\semidirect C_4$,
	$Q_8\semidirect C_2$,
	$C_3\times C_3$,
	$(C_3\times C_3)\semidirect C_2$,
	$A_4$,
	$C_6\times C_2$,
	$C_2\times C_2\times S_3$,
	$C_8$, or
	$D_{16}$.
\end{thm}

\begin{thm} A finite group $G$ has exactly $|G|-5$ cyclic subgroups
	if and only if $G$ is isomorphic to one of the following groups:
        $C_7$, $D_{14}$, or $C_3\semidirect C_4$.
\end{thm}

\section{Preliminaries}
Let $G$ be a finite group.  Denote by $C(G)$ the poset
of cyclic subgroups of $G$,
and let $\Delta(G)=|G|-|C(G)|$.
For any positive integer $d$, let
$n_d= |\{H\in C(G)\ :\ |H|=d\}|$ be the number of cyclic subgroups
of order $d$.
Since every element of $G$ generates a cyclic subgroup and $\phi(d)$ is
the number of generators of a cyclic group of order $d$, it follows that
$$\sum_{d \ge 1} n_d\phi(d)=|G|.$$
Because $|C(G)|=\displaystyle\sum_{d \ge 1} n_d$, we have
\begin{equation}
\label{eqn:tuarn}
	\sum_{d\ge 1} n_d(\phi(d)-1) = \Delta(G).
	\tag{$\star$}
\end{equation}

We will see below that the sum (\ref{eqn:tuarn}) gives information about
the possible cyclic subgroups of $G$.
Because of well-known properties of the  Euler $\phi$-function
(namely, that $\phi(d)=1$ if and only if $d=1$ or $d=2$, and
$\phi(d)$ is even for $d>2$),
we have the following.
\begin{remark}
\label{remark:1}
For any group $G$ and any difference $\Delta=|G|-|C(G)|$,
\be
\item $G$ may contain any number of cyclic subgroups of order $2$, and
\item if $n_d(\phi(d)-1)$ is a term in the sum (\ref{eqn:tuarn}),
	then $\phi(d)-1$ must be odd for all $d>2$.
\ee
\end{remark}
\begin{notation*} We write $\sigma(G)=(m_1,m_2,\ldots, m_t)$,
	$m_i>2$,
	to mean that
	$G$ has one cyclic subgroup of order $m_1$,
	another of order $m_2$, etc.,
	any number of cyclic subgroups of order $2$,
	and no other non-trivial cyclic subgroups.
	For example, $\sigma(Q_8)=(4,4,4)$
	and $\sigma(S_4)=(3,3,3,3,4,4,4)$.
\end{notation*}
\begin{example}
To see how the sum in (\ref{eqn:tuarn}) gives us information about
the possible cyclic subgroups, consider $\Delta(G)=4$.
The sum in (\ref{eqn:tuarn}) is
one of the partitions of $4$. That is, the
left side of equation (\ref{eqn:tuarn}) is either
$$\mbox{(a) $4$,\quad (b) $3+1$,\quad (c) $2+2$,\quad (d) $2+1+1$,\quad or\quad
(e) $1+1+1+1$.}$$
In case (a), there is a unique divisor $d$ of $|G|$ such that
$n_d(\phi(d)-1)=4\cdot 1$, or $2\cdot 2$, or $1\cdot 4$.
(When we say $n_d(\phi(d)-1)=4\cdot 1$, for example, we really mean
$(n_d, \phi(d)-1)=(4, 1)$, but we will continue to use the more
succinct notation.)
For all other divisors $i$ of $|G|$, we have $n_i(\phi(i)-1)=0$.
So either $n_i=0$, i.e., there are no cyclic subgroups of order $i$,
or $\phi(i)=1$, i.e., the divisor $i$ is $1$ or $2$.
By Remark \ref{remark:1}, we must have $n_d=4$ and
$\phi(d)-1=1$ (i.e., $d\in\{3,4,6\}$).
So in this case $G$ has either exactly four cyclic subgroups of order $3$,
or exactly four cyclic subgroups of order $4$, or
four cyclic subgroups of order $6$,
any number of cyclic subgroups of order $2$, and no other
non-trivial
cyclic subgroups.
Using our notation, either $\sigma(G)=(3,3,3,3)$,
or $\sigma(G)=(4,4,4,4)$, or $\sigma(G)=(6,6,6,6)$.
Note that if $\sigma(G)=(6,6,6,6)$ then $G$ also has a cyclic subgroup of order $3$,
so $\sigma(G)=(6,6,6,6)$ is impossible.
We will codify this observation in Proposition \ref{no_cn}.
\end{example}

In the following tables we list all the possibilities for $\sigma(G)$ for
$1\le \Delta \le 5$.
To construct these tables we use the following facts about the Euler $\phi$-function
$$\phi(d)=2 \iff  d\in\{3, 4, 6\},$$
$$\phi(d)=4 \iff  d\in\{5, 8, 10, 12\},\mbox{ and}$$
$$\phi(d)=6 \iff  d\in\{7, 9, 14, 18\}.$$
Just as we excluded $\sigma(G)=(6,6,6,6)$ in the example, we will
exclude  many of the possibilities for $\sigma(G)$ in these tables
in the forthcoming sections.

\begin{table}[ht]
	\caption{\label{table:1} Table for $\Delta(G)=1$}
	\centering
\begin{tabular}{|c|c|}
\hline
Partition & $\sigma(G)$ \\
\hline
1 & (3), (4), (6) \\
\hline
\end{tabular}
\end{table}

\begin{table}[ht]
	\caption{\label{table:2} Table for $\Delta(G)=2$}
	\centering
\begin{tabular}{|c|c|}
\hline
Partition & $\sigma(G)$ \\
\hline
2 & (3,3), (4,4), (6,6) \\
\hline
1+1 & (3,4), (3,6), (4,6) \\
\hline
\end{tabular}
\end{table}

\begin{table}[ht]
	\caption{\label{table:3}Table for $\Delta(G)=3$}
	\centering
\begin{tabular}{|c|c|c|}
\hline
Partition & & $\sigma(G)$ \\
\hline
3 & $3\cdot 1$ & $(3,3,3)$, $(4,4,4)$, $(6,6,6)$ \\ \cline{2-3}
  & $1\cdot 3$ &  $(5)$, $(8)$, $(10)$, $(12)$ \\
\hline
2+1 & & $(3,3,4)$, $(3,3,6)$, $(3,4,4)$, $(4,4,6)$, $(3,6,6)$, $(4,6,6)$ \\
\hline
1+1+1 & & $(3,4,6)$ \\
\hline
\end{tabular}
\end{table}

\begin{table}[ht]
	\caption{\label{table:4}Table for $\Delta(G)=4$}
	\centering
\begin{tabular}{|c|c|c|}
\hline
Partition & & $\sigma(G)$ \\
\hline
4 & & (3,3,3,3), (4,4,4,4), (6,6,6,6) \\
\hline
    & $3\cdot 1 + 1$ & (3,3,3,4), (3,3,3,6), (3,4,4,4),
    (4,4,4,6), (3,6,6,6), (4,6,6,6)\\ \cline{2-3}
3+1 & $1\cdot 3 + 1$ & (3,5), (4,5), (5,6), (3,8), (4,8), (6,8), (3,10),\\
    & & (4,10), (6,10), (3,12), (4,12), (6,12) \\
\hline
2+2 & & (3,3,4,4), (3,3,6,6), (4,4,6,6) \\
\hline
2+1+1 & & (3,3,4,6), (3,4,4,6), (3,4,6,6) \\
\hline
1+1+1+1 & & none \\
\hline
\end{tabular}
\end{table}

\begin{table}[ht]
	\caption{\label{table:5}Table for $\Delta(G)=5$}
	\centering
\begin{tabular}{|c|c|c|}
\hline
Partition & & $\sigma(G)$ \\
\hline
5 & $1\cdot 5$ & (7), (9), (14), (18) \\ \cline{2-3}
  & $5\cdot 1$ & (3,3,3,3,3), (4,4,4,4,4), (6,6,6,6,6) \\
\hline
4+1 &  & (3,3,3,3,4), (3,3,3,3,6), (3,4,4,4,4),  \\
  & & (3,6,6,6,6), (4,4,4,4,6), (4,6,6,6,6) \\
\hline
    & $3\cdot 1 + 2$ & (3,3,3,4,4), (3,3,3,6,6), (3,3,4,4,4), \\
  & & (4,4,4,6,6), (3,3,6,6,6), (4,4,6,6,6) \\ \cline{2-3}
3+2 & $1\cdot 3 + 2$ & (3,3,5), (4,4,5), (5,6,6), (3,3,8), \\
 & & (4,4,8), (6,6,8), (3,3,10), (4,4,10), \\
 & & (6,6,10), (3,3,12), (4,4,12), (6,6,12) \\
\hline
      & $3\cdot 1+1+1$ & (3,3,3,4,6), (3,4,4,4,6), (3,4,6,6,6) \\ \cline{2-3}
3+1+1 & $1\cdot 3 +1+1$ & (3,4,5), (3,5,6), (4,5,6), (3,4,8), \\
 & & (3,6,8), (4,6,8), (3,4,10), (3,6,10),\\
 & &   (4,6,10) (3,4,12), (3,6,12), (4,6,12) \\
 \hline
 2+2+1 & & (3,3,4,4,6), (3,3,4,6,6), (3,4,4,6,6) \\
\hline
2+1+1+1 & & none \\
\hline
1+1+1+1+1& & none \\
\hline
\end{tabular}
\end{table}

\subsection{Explanation of Exclusion Tables}
Continuing our example with $\Delta=4$, we see in Table \ref{table:4}
the 27 possible values for $\sigma(G)$.  We exclude 23 of these
possibilities in Table \ref{table4.1} which we call the ``Exclusion Table
for $\Delta(G)=4$". The remaining 4 possible values for $\sigma(G)$ are
then listed in Table \ref{table4.2} which we call the
``Revised Table for $\Delta(G)=4$".

We will invoke the following three propositions frequently in the
exclusion tables, referring to the first as ``No $C_n$",
the second as ``Sylow", and the third as ``Proposition \ref{lemma:ab}".

\begin{prop}\label{no_cn}(``No $C_n$") If $m$ is an entry in $\sigma(G)$ and $n|m$ ($n>2$), then $n$ must also be an entry in $\sigma(G)$.
\end{prop}
\begin{proof} A cyclic subgroup of order $m$ must contain one of order $n$ if $n|m$.
\end{proof}

\begin{prop}\label{sylow}(``Sylow") If $p$ is a prime, $p$ divides $|G|$, and $n_p$ denotes the number of times $p$ occurs in $\sigma(G)$, then $n_p\equiv 1\bmod p$.
\end{prop}
\begin{proof} This follows immediately from Frobenius' generalization
of the third part of Sylow's Theorem.
(\cite{andreev}, \cite{brown}, or \cite{frobenius}.)
\end{proof}

\begin{prop}\label{lemma:ab}
	Suppose a group $G$ has a unique cyclic subgroup $H$ of order $a$
	and a unique cyclic subgroup $K$ of order $b$. If $\gcd(a,b)=1$,
	then $G$ contains an element of order $ab$.
\end{prop}
\begin{proof} Since $H=\langle x\rangle$ and $K=\langle y\rangle$
	are unique, they are normal. The condition $\gcd(a,b)=1$
	implies $H\cap K=\{1\}$.  It follows that $xy=yx$
	and hence the element $xy$ has order $ab$.
\end{proof}

For example, in Table~\ref{table4.1} these three propositions eliminate all but two
of the entries (which must be dealt with using auxiliary lemmas).

\subsection{More Propositions}
\begin{prop}\label{from_H} If $\sigma(G)=(d_1,\ldots,d_r)$ with
$x_1,\ldots,x_r$ being generators for the cyclic subgroups
of order $d_1,\ldots,d_r$ respectively and
$H=\langle x_1,\ldots x_r\rangle$, then $G\cong H$ or $G\cong H\semidirect C_2$.
The latter case can only occur when $H$ is abelian and
if $t$ is the generator of $C_2$ then $tht^{-1}=h^{-1}$ for all $h\in H$.
\end{prop}
\begin{proof}
Since $H$ has cyclic subgroups of orders $d_1,\ldots,d_r$ and is a subgroup
of $G$ which itself has no other non-trivial cyclic subgroups of those orders (except possibly subgroups of order 2), we must have $\sigma(H)=(d_1,\ldots,d_r)$. Therefore $G=H$ is one possibility. Suppose $H<G$, then there must be a $t\in G-H$ which is necessarily of order 2. Now $H\unlhd G$, since the cyclic subgroups of a given order must be conjugated to one another and they generate $H$.
We will show that $\langle H,t\rangle\cong H\semidirect C_2$.
For any $h\in H$, let $\alpha=tht^{-1}$.
Since $ht\notin H$, it must have order 2, so
$1=htht=h\alpha t^2=h\alpha$. Thus we must have
$tht^{-1}=h^{-1}$ and every element in $\langle H,t\rangle - H$
must have order 2.
Therefore $\sigma(\langle H,t\rangle)=(d_1,\ldots,d_r)$ and
$G=\langle H,t\rangle\cong H\semidirect C_2$ is another possibility.
Since conjugation by $t$ is an automorphism of $H$, this forces
$H$ to be abelian.
Finally, suppose there is an $s\notin \langle H,t\rangle$.
By the previous arguments $shs^{-1}=h^{-1}$ for all $h\in H$.
But then $tsh(ts)^{-1} = h$ for all $h\in H$.
In particular, if $|x_i|=d_i>2$, then $tsx_i\notin H$,
but $|tsx_i|>2$ giving a contradiction.
\end{proof}

\begin{prop}\label{a_2a} \mbox{}
\begin{enumerate}
\item[(i)] We have $\sigma(G)=(a)$ if and only if $a=4$
or $a$ is an odd prime. In that case $G\cong C_a$ or $D_{2a}$
and $\Delta(G)=a-2$ in either case.
\item[(ii)] We have $\sigma(G)=(a,2a)$ if and only if $a=4$ or $a$ is an odd prime. In that case $G\cong C_{2a}$ or $D_{4a}$ and $\Delta(G)=2a-4$ in either case.
\end{enumerate}
\end{prop}
\begin{proof}
$(i)$ By Proposition \ref{no_cn} if $a$ had a proper odd divisor $d$,
$d$ must appear as an entry in $\sigma(G)$, which it does not.
Therefore $a$ must be an odd prime or a power of 2. If $a$ is a power of 2
greater than 8, then 4 would also have to appear in $\sigma(G)$,
which it does not. If $\sigma(G)=(a)$, when $a=4$ or an odd prime,
we let $x$ be an element of order $a$ and apply Proposition \ref{from_H}
to conclude that we must have $G\cong C_a$ or $D_{2a}$.
One easily checks that that these groups satisfy $\sigma(G)=(a)$
and $\Delta(G)=a-2$.\\
\\
\noindent
$(ii)$ An argument analogous to that in $(i)$ shows that $a$ must be 4 or an odd prime. Suppose that $\sigma(G)=(a,2a)$. If $x$ is an element of order $2a$, then $x^2$ has order $a$. In the context of Proposition \ref{from_H}, $H=\langle x,x^2\rangle=\langle x\rangle$ and the only possibilities for $G$ are $C_{2a}$ and $D_{4a}$. One readily verifies that in these cases, $\sigma(G)=(a,2a)$ and $\Delta(G)=2a-4$.
\end{proof}

\section{Difference 1}
In this section we reprove T\u{a}rn\u{a}uceanu's theorem \cite{tuarn}
in order to illustrate the methods we will use in the later sections.

\setcounter{thm}{0}
\begin{thm} A finite group $G$ has $|G|-1$ cyclic subgroups
	if and only if $G$ is isomorphic to one of the following groups:
	$C_3$, $C_4$, $S_3$, or $D_8$.
\end{thm}

\begin{proof} One easily checks that if $G$ is one of the listed
	groups then $G$ has $|G|-1$ cyclic subgroups.
	Conversely, if $G$ has exactly $|G|-1$ cyclic subgroups,
	then from Table~\ref{table:1} either
	$\sigma(G)=(3), (4)$ or $(6)$.
We immediately exclude $\sigma(G)=(6)$ by Proposition \ref{no_cn}. Applying Proposition
\ref{a_2a}(i),
we conclude that $\sigma(G)=3$ implies $G\cong C_3$ or $D_6$ and $\sigma(G)=4$ implies $G\cong C_4$ or $D_8$.
\end{proof}

\begin{table}[ht]
	\caption{\label{table1.1} Exclusion table for $\Delta(G)=1$}
	\centering
\begin{tabular}{|c|l|}
	\hline
	$\sigma(G)$ & Excluded by \\
	\hline
	(6) & No $C_3$ \\
	\hline
\end{tabular}
\end{table}

\begin{table}[ht]
	\caption{\label{table1.2} Revised table for $\Delta(G)=1$}
	\centering
\begin{tabular}{|c|c|c|}
\hline
Partition & $\sigma(G)$ & Groups \\
\hline
1 & (3) & $C_3$, $S_3$ \\
\hline
  & (4) & $C_4$, $D_{8}$ \\
\hline
\end{tabular}
\end{table}

\section{Difference 2}
In this section we prove the following.
\setcounter{thm}{1}
\begin{thm}\label{thm:diff2}
       	A finite group $G$ has exactly $|G|-2$ cyclic subgroups
	if and only if $G$ is isomorphic to one of the following groups:
	$C_4\times C_2$, $D_8\times C_2$, $C_6$, or $D_{12}$.
\end{thm}

The following lemma will be used below, and later in the
Difference~4 section of the paper.

\begin{lemma}\label{lemma:Z}
If $G$ contains fewer than 6 cyclic subgroups of order 4
and $s$ and $t$ are distinct elements of order 4,
and $tst^{-1}\in\c{s}$, then $s^2=t^2$.
\end{lemma}

\begin{proof} If, on the contrary, $\langle s\rangle\cap \langle t\rangle=\{1\}$, then
$$\langle s,t\rangle\cong C_4\semidirect C_4\cong\langle s,t|s^4=t^4=1,tst^{-1}=s^{\pm 1}\rangle.$$
In either case, one readily verifies that the elements other than
$1,s^2,t^2,s^2t^2$ all have order 4.  These 12 elements yield 6 cyclic subgroups
of order 4, a contradiction.
\end{proof}

We now begin the proof of Theorem \ref{thm:diff2}.
\begin{proof}[Proof of Theorem \ref{thm:diff2}]
If $G$ is any one of the groups
$C_4\times C_2$, $D_8\times C_2$, $C_6$, or $D_{12}$,
then $G$ has $|G|-2$ cyclic subgroups.

Conversely, if $G$ is a finite group with exactly $|G|-2$ cyclic subgroups,
then from Table \ref{table:2} we know the possible values of $\sigma(G)$.
If $\sigma(G)=(3,3)$, then $G$ has two Sylow $3$-subgroups, but this is
impossible
by Proposition \ref{sylow} (``Sylow'').
We exclude $\sigma(G)=(6,6)$ and $\sigma(G)=(4,6)$
by Proposition~\ref{no_cn} (``No $C_n$'').
The case $\sigma(G)=(3,4)$ is excluded by Proposition \ref{lemma:ab}.
We summarize these arguments in table form in Table \ref{table2.1}.

\begin{table}[ht]
	\caption{\label{table2.1} Exclusion table for $\Delta(G)=2$}
	\centering
\begin{tabular}{|c|l|}
	\hline
	$\sigma(G)$ & Excluded by \\
	\hline
	(3,3) & Sylow \\
	(6,6) & No $C_3$ \\
	(3,4) & Proposition \ref{lemma:ab} \\
	(4,6) & No $C_3$ \\
	\hline
\end{tabular}
\end{table}

The two Propositions below show that
we have the revised Table~\ref{table2.2} and complete the proof.
\end{proof}

\begin{prop} If $\sigma(G)=(4,4)$ then  $G=C_4\times C_2$ or $G=D_8\times C_2$.
\end{prop}
\begin{proof}
Let $H_1=\c{x}$ and $H_2=\c{y}$ be the two cyclic subgroups of order $4$
and let $H=\c{x,y}$.  We must have $yxy^{-1}\in H_1$ (since
$yxy^{-1}\in H_2$ gives $x\in H_2$), so by Lemma \ref{lemma:Z},
$x^2=y^2$ and hence $H\cong C_4\times C_2$ (if $yxy^{-1}=x$), or
$H\cong Q_8$ (if $yxy^{-1}=x^{-1}$). Since $Q_8$ has three cyclic subgroups
of order $4$, we must have $H\cong C_4\times C_2$.  By Proposition
\ref{from_H}, $G\cong C_4\times C_2$ or $G\cong (C_4\times C_2)\semidirect C_2$,
where the action of $C_2$ in the latter group is to send an element of $C_4\times C_2$
to its inverse.  It is easy to see that in this case
$(C_4\times C_2)\semidirect C_2 \cong D_8\times C_2$ and the result follows.
\end{proof}

\begin{prop} If $\sigma(G)=(3,6)$ then $G=C_6$ or $G=D_{12}$.  \end{prop}
\begin{proof}
This follows from Proposition \ref{a_2a} (ii).
\end{proof}

\begin{table}[ht]
	\caption{\label{table2.2} Revised table for $\Delta(G)=2$}
	\centering
\begin{tabular}{|c|c|c|}
\hline
Partition & $\sigma(G)$ & Groups \\
\hline
2 & (4,4) & $C_4\times C_2$, $D_8\times C_2$ \\
\hline
1+1 & (3,6) & $C_6$, $D_{12}$ \\
\hline
\end{tabular}
\end{table}

Before moving on to the next section we make the following observation,
which is not difficult to prove.
\begin{observ*}
If $G$ is a group with $\Delta(G)=d$, then $\Delta(G\times C_2)= 2d$.
\end{observ*}
Note that every group with difference $2$ is of the form $G\times C_2$
where $\Delta(G)=1$.  But we will see later that not every group
with difference $4$ is of the form $G\times C_2$ where $\Delta(G)=3$

\section{Difference 3}
Our goal in this section is to prove the following.

\setcounter{thm}{2}
\begin{thm}\label{thm:diff3}
	A finite group $G$ has exactly $|G|-3$ cyclic subgroups
	if and only if $G$ is isomorphic to one of the following groups:
	$Q_8$, $C_5$, or $D_{10}$.
\end{thm}

We will need the following lemmas.

\begin{lemma} \label{lemma:les1}
If a group $G$ has a cyclic subgroup of order $4$ and a unique
cyclic subgroup of order $3$, then $G$ has an element of order $6$.
\end{lemma}
\begin{proof} Suppose
	$\langle x\rangle$ is a cyclic subgroup of order $4$ and
	$\langle y\rangle$ is the unique cyclic subgroup of order $3$.
	Then $\langle y\rangle$ is normal, so
	$xyx^{-1}=y$ or $xyx^{-1}=y^{-1}$. In either case
	$x^2yx^{-2} = y$ and $x^2y=yx^2$. Then the element
	$x^2y$ has order 6, which completes the proof.
\end{proof}

\begin{lemma} \label{lemma:les2}
If $G$ has exactly two cyclic subgroups of order $4$ and a cyclic subgroup
of order $3$, then $G$ has an element of order $12$.
\end{lemma}
\begin{proof}
Let $H_1=\langle x\rangle$, $H_2=\langle y\rangle$, and  $\langle z\rangle$
be the cyclic subgroups of orders $4, 4$ and $3$ respectively.
The group $G$ acts on $\{H_1, H_2\}$ by conjugation,
and under the induced homomorphism $G\to S_2$ we have $z\mapsto (1)$.
In particular
$zxz^{-1}=x^{\pm 1}$, and then $z^2xz^{-2}=x$.  So $z^2x = xz^2$ and
the element $xz^2$ has order $12$.
\end{proof}

\begin{lemma} \label{lemma:366}
	There is no group with exactly two cyclic subgroups of order~6
	and a unique subgroup of order~3.

\end{lemma}
\begin{proof}
Let $H_1=\c{x}$ and $H_2=\c{y}$ be the two cyclic subgroups of order~6.
In order for there to be a unique subgroup of order~3, it must be the
case that $|H_1\cap H_2|=3$. In that case, without loss of generality,
$x^2=y^2$.
	The element
	$xyx^{-1}$ has order $6$ and cannot be in $\langle x\rangle$,
	so either $xyx^{-1}=y$ or $xyx^{-1}=y^{-1}$.  In both
	cases one can check that the subgroup $\langle xy \rangle$
	is cyclic of order $6$ and is distinct from
	$\langle x\rangle$ and $\langle y\rangle$, a contradiction.
\end{proof}

\begin{table}[ht]
	\caption{\label{table3.1} Exclusion table for $\Delta(G)=3$}
	\centering
\begin{tabular}{|c|l|}
	\hline
	$\sigma(G)$ & Excluded by \\
	\hline
	(3,3,3) & Sylow \\
	(6,6,6) & No $C_3$ \\
	(8) & No $C_4$ \\
	(10) & No $C_5$ \\
	(12) & No $C_3$\\
	(3,3,4) & Sylow \\
	(3,3,6) & Sylow \\
	(3,4,4) & Lemma \ref{lemma:les1} \\
	(4,4,6) & No $C_3$ \\
	(3,6,6) & Lemma \ref{lemma:366} \\
	(4,6,6) & No $C_3$ \\
	(3,4,6) & Proposition \ref{lemma:ab} \\
	\hline
\end{tabular}
\end{table}

\setcounter{thm}{5}
\begin{thm}\label{herzog}If $G$ is a 2-group with an odd number of cyclic subgroups of order 4, then $G$ must be cyclic, dihedral, generalized quaternion, or quasidihedral.
\end{thm}
\begin{proof}
Let $i_n(G)$ denote the number of elements of order $n$ in $G$. If the number of cyclic subgroups of order 4 is $2k+1$, then $i_4(G)=2(2k+1)$. Since $|G|\ge 4$, the number of solutions to $x^4=1$ in $G$ must be a multiple of 4 by Frobenius'
Theorem \cite[Theorem 5]{IR}. This number is $i_4(G)+i_2(G)+i_1(G)=2(2k+1)+i_2(G)+1$, so $i_2(G)\equiv 1\bmod 4$. It is known that in this case, $G$ must be cyclic, dihedral, generalized quaternion, or quasidihedral (\cite[Theorem 4.9]{isaacs} gives a character-theoretical proof and \cite{herzog} gives an elementary one).
\end{proof}

\begin{prop}\label{odd_4s} If $\sigma(G)=(4,\ldots,4)$ with $m$ 4's and $m$ is odd,
	then $m=1$ and $G\cong C_4$ or $D_8$ (and $\Delta(G)=1$ in both cases)
	or $m=3$ and $G\cong Q_8$ (and $\Delta(G)=3$).
\end{prop}
\begin{proof}
Now $G$ must be a 2-group (if not, $G$ would have elements of non-trivial
odd order) so by Theorem \ref{herzog}, $G$ must be cyclic, dihedral,
generalized quaternion, or quasidihedral.  If $|G|\ge 16$, then each of these
types of group contain an element of order 8, which is impossible.
Therefore $|G|=4$ or $|G|=8$.
In the first case, $G\cong C_4$ with $\sigma(G)=(4)$ and $\Delta(G)=1$.
In the second, $G$ must either be isomorphic to $C_8$, $D_8$, or $Q_8$.
But $G$ has no element of order $8$, so either
$G\cong D_8$, or $Q_8$
(with $\sigma(D_8)=(4), \Delta(D_8)=1, \sigma(Q_8)=(4,4,4)$, and $\Delta(Q_8)=3$).
\end{proof}

\begin{prop}\label{d3:prop3}
       	If $\sigma(G)=(5)$, then $G=C_5$ or $G=D_{10}$.
\end{prop}
\begin{proof}
This follows from Proposition \ref{a_2a} (i).
\end{proof}

\begin{prop}\label{prop:444}
If $\sigma(G)=(4,4,4)$, then $G\cong Q_8$.
\end{prop}

\begin{proof}
This follows from Proposition \ref{odd_4s}.
\end{proof}

\begin{remark}
	We remark that Proposition \ref{odd_4s} gives another proof of the $\sigma(G)=(4)$
	case in the Difference~$1$ section.
\end{remark}

\begin{table}[ht]
	\caption{\label{table3.2} Revised table for $\Delta(G)=3$}
	\centering
\begin{tabular}{|c|c|c|c|}
\hline
Partition & & $\sigma(G)$ & Groups \\
\hline
3 & $3\cdot 1$ & $(4,4,4)$ & $Q_8$\\ \cline{2-4}
  & $1\cdot 3$ &  $(5)$  & $C_5$, $D_{10}$\\
\hline
\end{tabular}
\end{table}

We are now ready to prove the main theorem of this section.

\begin{proof}[Proof of Theorem \ref{thm:diff3}]
If $\Delta(G)=3$, then by Table~\ref{table3.2} either $\sigma(G)=(5)$ or $\sigma(G)=(4,4,4)$.
If $\sigma(G)=(5)$, then $G\cong C_5$ or $G\cong D_{10}$ by Proposition~\ref{d3:prop3}.
If $\sigma(G)=(4,4,4)$, then $G\cong Q_8$ by Proposition~\ref{prop:444}.

Conversely, one checks that the groups $C_5$, $D_{10}$ and $Q_{8}$ all have
$\Delta=3$.
\end{proof}

\section{Difference 4}
In this section we prove the following theorem.
\setcounter{thm}{3}
\begin{thm}\label{thm:diff4}
	A finite group $G$ has exactly $|G|-4$ cyclic subgroups
	if and only if $G$ is isomorphic to one of the following eleven groups:
	$C_4\times C_2\times C_2$,\
	$C_2\times C_2\times D_8$,\
	$(C_2\times C_2)\semidirect C_4$,\
	$Q_8\semidirect C_2$,\
	$C_3\times C_3$,\
	$(C_3\times C_3)\semidirect C_2$,\
	$A_4$,\
	$C_6\times C_2$,\
	$C_2\times C_2\times S_3$,\
	$C_8$, or
	$D_{16}$.
\end{thm}

We list the exclusion table and the revised table for $\Delta=4$
in Tables~\ref{table4.1} and \ref{table4.2}.

\begin{table}[ht]
	\caption{\label{table4.1} Exclusion table for $\Delta(G)=4$}
	\centering
\begin{tabular}{|c|l|}
	\hline
	$\sigma(G)$ & Excluded by \\
	\hline
	(6,6,6,6) & No $C_3$ \\
	(3,3,3,4) & Sylow \\
	(3,3,3,6) & Sylow \\
	(3,4,4,4) & Lemma \ref{lemma:les1} \\
	(4,4,4,6) & No $C_3$ \\
	(4,6,6,6) & No $C_3$ \\
	(3,5) & Proposition \ref{lemma:ab} \\
	(4,5) & Proposition \ref{lemma:ab} \\
	(5,6) & No $C_3$ \\
	(3,8) & No $C_4$ \\
	(6,8) & No $C_4$ \\
	(3,10) & No $C_5$ \\
	(4,10) & No $C_5$ \\
	(6,10) & No $C_3$ \\
	(3,12) & No $C_4$ \\
	(4,12) & No $C_3$ \\
	(6,12) & No $C_3$ \\
	(3,3,4,4) & Sylow \\
	(3,3,6,6) & Sylow \\
	(4,4,6,6) & No $C_3$ \\
	(3,3,4,6) & Sylow \\
	(3,4,4,6) & Lemma \ref{lemma:les2} \\
	(3,4,6,6) & Proposition \ref{lemma:ab} \\
	\hline
\end{tabular}
\end{table}

\begin{table}[ht]
	\caption{\label{table4.2} Revised table for $\Delta(G)=4$}
	\centering
\begin{tabular}{|c|c|c|c|}
\hline
Partition & & $\sigma(G)$ & Groups \\
\hline
4 & $4\cdot 1$ & (3,3,3,3) & $C_3\times C_3$, $(C_3\times C_3)\semidirect C_2$, $A_4$\\ \cline{2-4}
  & $4\cdot 1$ & (4,4,4,4) & $C_4\times C_2\times C_2$, $C_2\times C_2\times D_8$, \\
  &  &  & $(C_2\times C_2)\semidirect C_4$, $Q_8\semidirect C_2$ \\
\hline
    & $3\cdot 1 + 1$ & (3,6,6,6) & $C_6\times C_2$, $C_2\times C_2\times S_3$\\ \cline{2-4}
3+1 & $1\cdot 3 + 1$ & (4,8)  & $C_8$, $D_{16}$ \\
\hline
\end{tabular}
\end{table}

\begin{prop}\label{prop:3333} If $\sigma(G)=(3,3,3,3)$ then $G$ is
	isomorphic to either
	$C_3\times C_3$, $(C_3\times C_3)\semidirect C_2$, or $A_4$.
\end{prop}
\begin{proof}
Let $H_i=\langle x_i\rangle, i=1,2,3,4$, be the distinct cyclic subgroups
of order 3 and let $H=\langle x_1,x_2,x_3,x_4\rangle$.
We have $H$ acting on $\{H_1, H_2, H_3, H_4\}$ by
conjugation giving a homomorphism $\phi:H\to S_4$
(where we identify $H_i$ with $i$ in $S_4$).
Each $x_i$ must map to either a 3-cycle or the identity in $S_4$,
since each $x_i$ has order $3$. Also, $\phi(x_i)$ must fix $i$,
since $x_i H_i x_i^{-1}=H_i$.\\
\\
\noindent
Claim: We have $x_ix_jx_i^{-1}\ne x_j^{-1}$.\\
\\
\noindent
Proof of claim: If $x_ix_jx_i^{-1}= x_j^{-1}$, then $(x_jx_i)^2=x_i^2\ne 1$,
and $(x_jx_i)^3=x_j\ne 1$, hence $|x_jx_i|\ge 4$, a contradiction.\\
\\
\noindent
Returning to the proof, there are two cases:
either $\phi(x_i)=1$ for some $i$, or $\phi$ sends all the $x_i$
to 3-cycles, without loss of generality
$\phi(x_1)=(234),\phi(x_2)=(134),\phi(x_3)=(124)$, and $\phi(x_4)=(123)$. \\
\\
\noindent
In the first case, we may assume $\phi(x_1)=1$ without loss of generality.
Then $x_1x_2x_1^{-1}\in\c{x_2}$ so either
$x_1x_2x_1^{-1} = x_2$ or
$x_1x_2x_1^{-1} = x_2^{-1}$.  By the claim, we must have the former, i.e.,
$x_1x_2=x_2x_1$, so $\langle x_1,x_2\rangle\cong C_3\times C_3$.
This groups has four cyclic subgroups of order 4, so we must have
$H=\langle x_1,x_2\rangle\cong C_3\times C_3$.
By Proposition \ref{from_H}, $G\cong C_3\times C_3$ or
$(C_3\times C_3)\semidirect C_2$, where the action of
$C_2$ sends each element of $C_3\times C_3$ to its inverse.\\
\\
\noindent
In the second case we claim $G\cong A_4$.
Since $\phi$ maps the $x_i$ to 3-cycles that generate $A_4$,
$\im\phi=A_4$. We claim that $\ker \phi = 1$.
Note that if $v\ne 1$ and $v\in\ker \phi$, then $|v|=2$,
since none of the order~3 elements are in the kernel.
\\
\noindent
Let $K = \ker \phi$.
Now $K \cap \langle x_1 \rangle = 1$,
$\phi(\langle K,x_1 \rangle) = \langle (234) \rangle$, and from this it follows
that if $\alpha \in \langle K,x_1 \rangle - \langle x_1 \rangle$, then $|\alpha| = 2$.\\
\\
\noindent
Suppose that the claim is false, then there exists $u \in K, u \neq 1.$
Consider $ux_1 \in \langle K,x_1 \rangle$. Then $ux_1 \notin \langle x_1 \rangle$,
for if it were then $u \in \langle x_1 \rangle$. Thus, $|ux_1| = 2$. Therefore
$$1 = (ux_1)^{2} = ux_1ux_1 = ux_1u^{-1}x_1^{-1}x_1^{2},$$
which implies that $x_1^{2} = x_1ux_1^{-1}u^{-1}$, where $x_1ux_1^{-1} \in K$
by the normality of $K$, hence $x_1^{2} \in K$, a contradiction.
Thus, $\ker \phi = 1$ and $H\cong A_4$. By Proposition \ref{from_H}, $G\cong H\cong A_4$.
\end{proof}

\begin{prop}\label{prop:4444} If $\sigma(G)=(4,4,4,4)$ then $G$ is isomorphic to
$C_4\times C_2\times C_2$,
$D_8\times C_2\times C_2$,
$(C_2\times C_2)\semidirect C_4$, or
$Q_8\semidirect C_2$.
The last two groups are SmallGroup(16,3) and SmallGroup(16,13) respectively in GAP.
\end{prop}
\begin{proof}

Suppose the four cyclic subgroups of order~4 are $H_i=\langle x_i\rangle$
for $i=1, 2, 3, 4$. If $H=\langle x_1,x_2,x_3,x_4\rangle$ then $H$ acts on the set
$\{H_1, H_2, H_3, H_4\}$ by conjugation, inducing a homomorphism
$\phi: H\rightarrow S_4$
(as usual, when representing a permutation of the
$H_i$ as an element of $S_4$, we will replace $H_i$ by $i$).
Now the order of $\phi(x_i)$ must divide 4 and $\phi(x_i)$ must fix $i$.
This eliminates 4-cycles or the product of two disjoint 2-cycles as possibilities.
In particular, $\phi(x_1)=(1), (23),(24)$, or $(34)$ and,
without loss of generality, we may assume $\phi(x_1)=(1)$ or $(34)$.
Note that $x_1 H_2 x_1^{-1}=H_2$ in either case.
Similarly, $\phi(x_2)=(1), (13),(14)$, or $(34)$. However, in the second and third cases $\phi(x_1x_2)$ is a
3-cycle, which is impossible (as all the elements of $H$ have orders 1,2, or 4). Therefore $\phi(x_2)=(1)$ or $(34)$. Analogous arguments show
$\phi(x_3)=(1)$ or $(12)$ and $\phi(x_4)=(1)$ or $(12)$.\\
\\
\noindent
Because $x_1 H_2 x_1^{-1}=H_2$, by Lemma \ref{lemma:Z}, $x_1^2=x_2^2$.
If $x_1x_2x_1^{-1}=x_2$, then
$K_1=\langle x_1,x_2\rangle\cong C_4\times C_2$, and if $x_1x_2x_1^{-1}=x_2^{-1}$, then $K_1\cong Q_8$. Similarly,
$K_2=\langle x_3,x_4\rangle\cong C_4\times C_2$ or $Q_8$. In all of the cases above, $K_1,K_2\unlhd H$. \\
\\
\noindent
We claim that $|H|=16$. We have $H=K_1K_2$, so $|H|=|K_1||K_2|/|K_1\cap K_2|$.
We cannot have $K_1=K_2$, since then $H=K_1=K_2$ and
$C_4\times C_2$ has only two cyclic subgroups of order 4 and
$Q_8$ has only three. If either $K_1\cong Q_8$ or $K_2\cong Q_8$
(without loss of generality, assume it's $K_1$), then there is a
third cyclic subgroup of order 4 in $K_1$, which must be either
$\langle x_3\rangle$ or $\langle x_4\rangle$. This gives us
$|K_1\cap K_2|=4$ and hence $|H|=16$ as desired.
We may therefore assume that $K_1\cong K_2\cong C_4\times C_2$.\\
\\
\noindent
If $|K_1\cap K_2|=1$, then $H\cong K_1\times K_2\cong C_4^2\times C_2^2$
and $C_4^2$ itself has 6 cyclic subgroups of order 4, which is more than
we are allowed.
Consequently,
$H/(K_1\cap K_2)\cong (K_1/(K_1\cap K_2))\times(K_2/(K_1\cap K_2))$
is abelian, being the product of two groups each of which is of
order at most $4$.
\\
\noindent
If $|K_1\cap K_2|=2$, then $K_1\cap K_2$ is a subgroup of $K_1$ of order 2 and must therefore be generated by $x_1^2, x_1x_2$, or $x_1^{-1}x_2$.  The latter two cases are equivalent (we merely choose $x_1^{-1}$ to be the generator of $H_1$ and repeat the analogous arguments as those with $x_1$ as the generator).\\
\\
\noindent
Case 1: Suppose $K_1\cap K_2\le K_1$ is generated by $x_1^2=x_2^2$.
Since the image of $x_1x_3x_1^{-1}x_3^{-1}$ in
$H/(K_1\cap K_2)$ is trivial, we must have
$x_1x_3x_1^{-1}x_3^{-1}=x_1^2$ or $1$. In the former case,
$x_3x_1x_3^{-1}=x_1^{-1}$ and $\langle x_1,x_3\rangle\cong Q_8$. But here,
there is a third cyclic subgroup of order 4 in $Q_8$, so either
$x_2$ or $x_4$ is in $\langle x_1,x_3\rangle$. In the first subcase, $x_2$ does not commute with $x_1$ and in the second $x_4$ does not commute wth $x_3$, contradicting the fact that $\langle x_1,x_2\rangle$ and $\langle x_3,x_4\rangle$ are abelian. So the latter case holds and $x_1$ and $x_3$ must commute. Replacing $x_3$ by $x_4$ and $x_1$ by $x_2$ and repeating the argument above shows that $H$ must be abelian. Now $|H|=32$ and $H$ only has elements of order 1,2, or 4, so $H\cong C_4\times C_2^3$ or $C_4^2\times C_2$. In both cases, $H$ has too many cyclic subgroups of order 4 (8 in the first case and 12 in the second).  An analogous argument shows that $K_1\cap K_2\le K_2$ cannot be generated by $x_3^2=x_4^2$.\\
\\
\noindent
Case 2: Suppose $K_1\cap K_2\le K_1$ is generated by $x_1x_2$ and $K_1\cap K_2\le K_2$ is generated by $x_3x_4$. In this case $H/(K_1\cap K_2)\cong C_4\times C_4$, which has 6 cyclic subgroups of order 4, giving a contradiction.\\
\\
\noindent
Therefore $|K_1\cap K_2|=4$ and $|H|=16$. Rather than proceeding
further using first principles, we will invoke the classification of
groups of order 16.
By \cite[Table 1]{wild},
the only groups of order 16 with 4 cyclic subgroups of order 4 and no cyclic subgroups of larger order are $C_4\times C_2\times C_2$,
$$(C_2\times C_2)\semidirect C_4\cong\langle a,b,c|a^2=b^2=c^4=1,ab=ba,ca=ca,cbc^{-1}=ab\rangle,\mbox{ or}$$
$$Q_8\semidirect C_2\cong\langle a,b,c|a^4=c^2=1,a^2=b^2,bab^{-1}=a^{-1},ca=ca,cbc^{-1}=a^2b\rangle.$$
\\
\noindent
By Proposition \ref{from_H}, the only groups with $\sigma(G)=(4,4,4,4)$ are
the groups above and $(C_4\times C_2\times C_2)\semidirect C_2$
where the action of $C_2$ on
$C_4\times C_2\times C_2$ is $x\rightarrow x^{-1}$.
It is straightforward to verify that this group is isomorphic to $D_8\times C_2\times C_2$.
\end{proof}

\begin{prop}\label{prop:3666}
       	If $\sigma(G)=(3,6,6,6)$, then
	$G\cong C_6\times C_2$
	or $G\cong C_2\times C_2\times S_3$.
\end{prop}
\begin{proof}
Let $G$ be a finite group with exactly three cyclic subgroups of order
$6$, exactly one cyclic subgroup of order $3$, and any number of
cyclic subgroups of order $2$.

Let
$H_1=\langle x\rangle$,
$H_2=\langle y\rangle$,
$H_3=\langle z\rangle$ be the three cyclic subgroups of order $6$ and let $H=\langle x,y,z\rangle$.
Then we may choose generators so that $x^2=y^2=z^2=w$,
and $\langle w\rangle \cong C_3$.

We have $H$ acting on $\{H_1, H_2, H_3\}$ by conjugation, which gives a
homomorphism $\phi: H\to S_3$.  We have $\phi(x) = 1$ or $\phi(x)=(23)$; $\phi(y)=1$ or $\phi(y)=(13)$; and
$\phi(z)=1$ or $\phi(z)=(12)$.
Note also that $\phi(w)=1$.

\smallskip

\noindent
We claim that no two of $x,y,z$ can map to a transposition. Without loss of generality, assume that $\phi(x)=(23)$ and $\phi(y)=(13)$. Then $\phi(xy)=(123)$, so $|xy|$ must be 3 or 6.
But only $w^{\pm 1}$ has order~3,
and $x^{\pm 1},y^{\pm 1},z^{\pm 1}$ are the only elements of order 6,
and these all map to the identity or a transposition. This yields a contradiction.

\smallskip

By the claim, we may assume, without loss of generality, that $\phi(x)=1$, so $x\langle y\rangle x^{-1}=\langle y\rangle$.
Since $x^2=y^2$,
$\langle x,y\rangle = \langle x^3,y\rangle$.
We also have $\langle y\rangle \unlhd \langle x^3,y\rangle$ and
$\langle x^3\rangle \cap \langle y\rangle =1$,
so $\langle x,y\rangle\cong C_6\semidirect C_2$.
This means $\langle x,y\rangle \cong C_6\times C_2$ or $D_{12}$.
But $\langle x,y\rangle$ is supposed to have at least two cyclic subgroups
of order 6 and $D_{12}$ only has one. Since $C_6\times C_2$ has three
subgroups of order 6 and one of order 3,
$H=\langle x,y\rangle\cong C_6\times C_2$. By Proposition \ref{from_H},
$G\cong C_6\times C_2$ or $G\cong (C_6\times C_2)\semidirect C_2$,
where the action of $C_2$ sends each element of $C_6\times C_2$
to its inverse.
It is straightforward to verify that this latter group is isomorphic to
$C_2\times C_2\times S_3$.\\
\\
\noindent
One readily verifies that $C_6\times C_2$ and $C_2\times C_2\times S_3$ both satisfy the conditions of the theorem.
\end{proof}

\begin{prop}\label{prop:48}
If $\sigma(G)=(4,8)$ then $G$ is isomorphic to either $C_8$ or $D_{16}$.
\end{prop}
\begin{proof}
	This follows from Proposition \ref{a_2a} (ii).
\end{proof}

We are now ready to prove Theorem~\ref{thm:diff4}.

\begin{proof}[Proof of Theorem \ref{thm:diff4}]
Our work above shows that if
$\Delta(G)=4$, then $\sigma(G) = (3,3,3,3)$, $(4,4,4,4)$, $(3,6,6,6)$ or $(4,8)$.
If $\sigma(G)=(3,3,3,3)$ then $G$ is
   isomorphic to either $C_3\times C_3$,
   $(C_3\times C_3)\semidirect C_2$, or $A_4$ by Proposition~\ref{prop:3333}.
If $\sigma(G)=(4,4,4,4)$ then $G$ is isomorphic to either
$C_4\times C_2\times C_2$, $C_2\times C_2\times D_8$,
$(C_2\times C_2)\semidirect C_4$, or $Q_8\semidirect C_2$
   by Proposition~\ref{prop:4444}.
If $\sigma(G)=(3,6,6,6)$, then $G\cong C_6\times C_2$
	or $G\cong C_2\times C_2\times S_3$ by Proposition~\ref{prop:3666}.
If $\sigma(G)=(4,8)$ then $G\cong C_8$ or $G\cong D_{16}$ by Proposition~\ref{prop:48}.

Conversely, one checks all of the eleven groups listed have $\Delta=4$.
\end{proof}

\section{Difference 5}
\setcounter{thm}{4}
\begin{thm}\label{thm:diff5}
	A finite group $G$ has exactly $|G|-5$ cyclic subgroups
	if and only if $G$ is isomorphic to one of the following groups:
        $C_7$, $D_{14}$, or $C_3\semidirect C_4$.
\end{thm}

\begin{lemma} \label{lemma:r}
If a group $G$ has a unique cyclic subgroup of order $4$ and a
subgroup of order $3$, then $G$ has an element of order $12$.
\end{lemma}
\begin{proof} Suppose
	$\langle x\rangle$ is the unique cyclic subgroup of order $4$ and
	$\langle y\rangle$ is a cyclic subgroup of order $3$.
	Then $\c{x}$ is normal in $\c{x, y}$, and
	$\langle x\rangle \cap \langle y\rangle = \{1\}$,
	so  we have a semidirect product
	$\langle x\rangle \semidirect\langle y\rangle$ for
	some homomorphism $\langle y\rangle \to \Aut(C_4)$.
	But $\Aut(C_4)\cong\Z_4^\times\cong C_2$ and $y$ has order $3$,
	so the homomorphism must be trivial.
	Hence
	$\langle x\rangle \semidirect \langle y\rangle
	\cong C_4\times C_3  \cong  C_{12}$ and $G$ has an
	element of order $12$.
\end{proof}

\begin{lemma}\label{lemma:36666}
There is no group $G$ such that $\sigma(G)=(3,6,6,6,6)$.
\end{lemma}
\begin{proof}
Let $H_1,H_2,H_3,H_4$ be the four cyclic subgroups of order 6
with generators $x_1, x_2, x_3, x_4$ respectively. Since there is a unique
subgroup of order 3, we must have $x_1^2=x_2^2=x_3^2=x_4^2$.
Let $H=\langle x_1,x_2,x_3, x_4\rangle$. As usual, there is a homomorphism
$\phi:G\rightarrow S_4$ given by $G$ acting on $\{H_1,H_2,H_3,H_4\}$
by conjugation (with $H_i$ identified with $i$).
Since
$x_i^2H_jx_i^{-2}=x_j^2H_jx_j^{-2}=H_j$, $\phi(x_i^2)=1$,
so $\phi(x_i)$ must have order 1 or 2.
Since $x_i H_i x_i^{-1}=H_i$, $\phi(x_i)$ must fix $i$. These two conditions
force $\phi(x_i)$ to be the identity or a 2-cycle not containing $i$.
Without loss of generality, we may assume that
$\phi(x_1)=(1)$ or $\phi(x_1)=(34)$. In either case,
$x_1 x_2 x_1^{-1}=x_2^{\pm 1}$.
However, if
$x_1 x_2 x_1^{-1}=x_2^{-1}$,
then $1=x_1^6=x_2^2 x_1 x_2^2 x_1 =
x_2^2 x_2^{-2}x_1x_1 = x_1^2$
contradicting the fact that $x_1$ has order 6. Therefore $x_1$ and $x_2$
commute and $\langle x_1,x_2\rangle\cong C_6\times C_2$,
which has 3 cyclic subgroups
of order 6.  Without loss of generality, we may assume that
$x_3\in\langle x_1,x_2\rangle$. Since $x_1,x_2$, and $x_3$ all commute,
$\phi(x_i)$ fixes 1,2, and 3 for $i=1,2,3$ and hence they must fix 4 as well.
Consequently, $x_i x_4 x_i^{-1}=x_4^{\pm 1}$ for $i=1,2,3$.
By an argument analogous to that above,  $x_i x_4 x_i^{-1}=x_4^{-1}$
leads to a contradiction, so $H$ must be an abelian group.
But in that case, $\langle x_1^{-1} x_2 x_4\rangle$ is a fifth cyclic subgroup
of order 6, yielding a contradiction and the result follows.
\end{proof}

\begin{lemma}\label{lemma:445}
	There is no group $G$ such that $\sigma(G)=(4,4,5)$.
\end{lemma}

\begin{proof}
	There are elements $x, y, z\in G$ such that $\c{x}\cong C_5$, and
	$\c{y}, \c{z}$ are the distinct cyclic subgroups of order $4$.
	When $G$ acts on $\{\c{y}, \c{z}\}$ by conjugation we have
	a homomorphism
	$\phi:G\to S_2$, and since $x$ has order $5$ we must have
	$\phi(x)=(1)$ in $S_2$.
	Now we have $\c{y}\unlhd\c{x, y}$, and $\c{x}\cap\c{y}=\{1\}$,
	and hence
	$\c{x, y} \cong C_4\semidirect C_5 \cong \c{y}\semidirect\c{x}$ for
	some homomorphism $\c{x}\to\Aut(\c{y})$.
	But the only homomorphism from $C_5$ to $\Aut(C_4)$ is
	the trivial one.  Therefore the semidirect product
	is the direct product, and $G$ has a subgroup isomorphic to
	$C_4\times C_5\cong C_{20}$ which is impossible since $G$ has no element
	of order $20$.
\end{proof}

\begin{lemma}\label{lemma:448}
There is no group $G$ such that $\sigma(G)=(4,4,8)$.
\end{lemma}

\begin{proof} Suppose there were such a group and let $K=\langle x\rangle$
	be the unique cyclic subgroup of order $8$.
	Let $H_1=\langle y\rangle$ and $H_2=\langle x^2\rangle$ be the two
	cyclic subgroups of order $4$.  Group $G$ acts on $\{H_1, H_2\}$
	by conjugation inducing a homomorphism $\phi:G\to S_2$.
	Because $xH_2x^{-1} = H_2$, we have $\phi(x)=(1)$. Therefore
	$xyx^{-1}=y$ or $xyx^{-1}=y^{-1}$.  In either case it will follow
       that the order of $xy$ is $8$, a contradiction.

       \smallskip Case 1: $xy=yx$.
       Since $(xy)^8=1$, the order of $xy$ divides $8$.
       Since $x$ has order $8$ we have
       $(xy)^4 = x^4y^4=x^4$ is not the identity.
       Therefore, $xy$ has order $8$ in this case.

       \smallskip Case 2: $xy=y^{-1}x$.
       A computation shows $(xy)^4=x^4$ is not the identity, and $(xy)^8=1$.
       Therefore, $xy$ has order $8$ in this case as well.
       \end{proof}

\begin{prop}\label{prop:44444}
There is no group $G$ with $\sigma(G)=(4,4,4,4,4)$.
\end{prop}
\begin{proof}
	This follows from Proposition~\ref{odd_4s}.
\end{proof}

\begin{lemma}\label{lemma:33336}
There is no group $G$ with $\sigma(G)=(3,3,3,3,6)$.
\end{lemma}
\begin{proof}
Suppose $\c{x}\cong C_6$.
Choose an element $z\in G$ of order $3$ where $\c{x}\cap\c{z}=\{1\}$.
Since $\c{x}\unlhd G$, we have a semidirect product subgroup
$C_6\semidirect\c{z}$ for some homomorphism $C_3\to \Aut(C_6)\cong C_2$.
It follows that the homomorphism is trivial and
$C_6\semidirect\c{z} \cong C_6\times C_3$.
Consequently $G$ contains more than one cyclic subgroup of order $6$,
a contradiction.
\end{proof}

\begin{lemma}\label{lemma:34466}
(a) There is no group $G$ with $\sigma(G)=(3,4,4,6,6)$.

(b) If $\sigma(G)=(3,4,4,4,6)$ then $G\cong C_3\semidirect C_4$.
\end{lemma}
\begin{proof}
Suppose $\c{x}\cong C_3$ and $\c{y}\cong C_4$.  These two groups intersect
trivially, and the first is normal in $G$ so
is normal in $\c{x,y}$, hence $\c{x,y}\cong C_3\semidirect C_4$.
If the action of $y$ on $\c{x}$ is trivial
then $\c{x,y}\cong C_{12}$,
which is impossible if $\sigma(G)=(3,4,4,6,6)$ or
if $\sigma(G)=(3,4,4,4,6)$.
If the action is not trivial then
$$H=\c{x, y\ |\ x^3=y^4=1, \ yxy^{-1}=x^{-1} },$$
and in this case one can check that
$\c{y}$, $\c{xy}$, and $\c{x^2y}$
are three distinct cyclic subgroups of order 4.
This is not
possible if $\sigma(G)=(3,4,4,6,6)$, so (a) is proved.

To prove (b), one readily checks that
$\sigma(H)=(3,4,4,4,6)$, so by Proposition~\ref{from_H},
$G\cong C_3\semidirect C_4$.
\end{proof}

We now prove Theorem~\ref{thm:diff5}.

\begin{proof}[Proof of Theorem \ref{thm:diff5}]
If $\Delta(G)=5$ then because of the previous Lemmas and Propositions
summarized in Revised Table \ref{table5.2}, either $\sigma(G)=(7)$ or $\sigma(G)=(3,4,4,4,6)$.
If $\sigma(G)=(7)$ then $G\cong C_7$ or $G\cong C_{14}$ by
part (i) of Proposition~\ref{a_2a}.
If $\sigma(G)=(3,4,4,4,6)$ then $G\cong C_3\semidirect C_4$ by part (b) of
Lemma~\ref{lemma:34466}.
\end{proof}

\begin{table}[H]
	\caption{\label{table5.2} Revised table for $\Delta(G)=5$}
	\centering
\begin{tabular}{|c|c|c|}
\hline
Partition & $\sigma(G)$ & Groups \\
\hline
5 & (7) & $C_7$, $D_{14}$ \\
\hline
3+1+1 & (3,4,4,4,6) & $C_3\semidirect C_4$ \\
\hline
\end{tabular}
\end{table}

\begin{table}[H]
	\caption{\label{table5.1} Exclusion table for $\Delta(G)=5$}
	\centering
\begin{tabular}{|c|l|}
	\hline
	$\sigma(G)$ & Excluded by \\
	\hline
	(9) & No $C_3$ \\
	(14) & No $C_7$ \\
	(18) & No $C_9$ \\
	(3,3,3,3,3) & Sylow \\
	(4,4,4,4,4) & Proposition \ref{prop:44444}\\
	(6,6,6,6,6) & No $C_3$ \\
	(3,3,3,3,4) & Lemma \ref{lemma:r} \\
	(3,3,3,3,6) & Lemma \ref{lemma:33336} \\
	(3,4,4,4,4) & Lemma \ref{lemma:les1} \\
	(4,4,4,4,6) & No $C_3$ \\
	(3,6,6,6,6) & Lemma \ref{lemma:36666}\\
	(4,6,6,6,6) & No $C_3$ \\
	(3,3,3,4,4), (3,3,3,6,6),(3,3,4,4,4)  & Sylow \\
	(4,4,4,6,6) & No $C_3$ \\
	(3,3,6,6,6) & Sylow \\
	(4,4,6,6,6) & No $C_3$ \\
	(3,3,5) & Sylow \\
	(4,4,5) & Lemma \ref{lemma:445} \\
	(5,6,6) & No $C_3$ \\
	(3,3,8) & No $C_4$ \\
	(4,4,8) & Lemma \ref{lemma:448} \\
	(6,6,8) & No $C_3$ \\
	(3,3,10), (4,4,10), (6,6,10)  & No $C_5$ \\
	(3,3,12) & No $C_4$ \\
	(4,4,12), (6,6,12) & No $C_3$ \\
	(3,3,3,4,6) & Sylow \\
	(3,4,6,6,6) & Proposition \ref{lemma:ab} \\
	(3,4,5), (3,5,6) & Proposition \ref{lemma:ab} \\
	(4,5,6) & No $C_3$ \\
	(3,4,8), (3,6,8) & Proposition \ref{lemma:ab} \\
	(4,6,8) & No $C_3$ \\
	(3,4,10), (3,6,10), (4,6,10)  & No $C_5$ \\
	(3,4,12) & No $C_6$ \\
	(3,6,12) & No $C_4$ \\
	(4,6,12) & No $C_3$ \\
	(3,3,4,4,6), (3,3,4,6,6)  & Sylow \\
	(3,4,4,6,6) & Lemma \ref{lemma:34466} \\
	\hline
\end{tabular}
\end{table}

\section{Acknowledgements}
This paper is an expansion and revision of the Master's thesis of the
second author, which was directed by the first and third authors.

We would like to thank the anonymous referee for a very careful reading
of the paper, and for many helpful remarks.


text:
\begin{document}

\title{Pullbacks of $\kappa$ classes on $\Mbar_{0,n}$}
\author{Rohini Ramadas}
\email{rohini\_ramadas@brown.edu}
\address{Department of Mathematics\\Brown University\\Providence, RI}
\thanks{This work was partially supported by NSF grants
0943832, 1045119, 1068190, and 1703308.}
\subjclass[2010]{14H10 (primary), 14N99, 14M99, 20C30}

\begin{abstract}

The moduli space $\Mbar_{0,n}$ carries a codimension-$d$ cycle class $\kappa_{d}$. We consider the subspace $\cK^{d}_{n}$ of $A^d(\Mbar_{0,n},\Q)$ spanned by pullbacks of $\kappa_d$ via forgetful maps. We find a permutation basis for $\cK^{d}_{n}$, and describe its annihilator under the intersection pairing in terms of $d$-dimensional boundary strata. As an application, we give a new permutation basis of the divisor class group of $\Mbar_{0,n}$.

\end{abstract}
\maketitle

\section{Introduction}\label{sec:Intro}

Mumford \cite{Mumford1983} introduced the tautological, codimension-$d$ class $\kappa_d$ in the cohomology/Chow group of the moduli space $\M_{g,n}$. This class extends to the moduli space $\Mbar_{g,n}$ of stable curves as well as to various partial compactifications of $\M_{g,n}$. Ring-theoretic relations involving $\kappa$ classes have been studied by Faber, Ionel, Pandharipande, Pixton, Zagier, Zvonkine, and several others, and play a role in the study of Gromov-Witten theory and mirror symmetry (\cite{faber_1999,Ionel2005,Pandharipande2012,PandharipandePixton2013,PPZ2016}; see \cite{Pandharipande2011, Pandharipande2016} for overviews).

Here, we investigate $\kappa$ classes on $\Mbar_{0,n}$ from a linear-algebraic and representation-theoretic perspective. The symmetric group $S_n$ acts on $\Mbar_{0,n}$, and thus acts on its cohomology and Chow groups. Given any $T\subseteq\{1,\ldots,n\}$ with $\abs{T}\ge3$, there is a forgetful map $\pi_T:\Mbar_{0,n}\to\Mbar_{0,T}$. We set $\kappa_d^T:=\pi_T^*(\kappa_d)$, and consider the subspace $\cK^d_n\subseteq A^d(\Mbar_{0,n},\Q)$ spanned by $\{\kappa_d^T\}_{T\subseteq\{1,\ldots,n\}}$; this subspace is clearly $S_n$-invariant. Recall that a \textit{permutation basis} of a $G$-representation is one whose elements are permuted by the action of $G$. We show:

\smallskip

\noindent\textbf{Theorem A.} (Theorem \ref{thm:Main}\ref{it:KappaBasis}.) \textit{If $n\ge4$ and $1\le d\le n-3$, then $\cK^d_n$ has a permutation basis given by $\{\kappa_{d}^T\thickspace|\thickspace\abs{T}\ge(d+3), \abs{T}\equiv (d+3)\mod 2\}$.}

\smallskip

\subsection{Does $A^d(\Mbar_{0,n},\Q)$ have a permutation basis?} Getzler \cite{Getzler1995} and Bergstr\"om-Minabe \cite{BergstromMinabe2013} have given algorithms to compute the character of $A^d(\Mbar_{0,n},\Q)$ as an $S_n$-representation. It is not clear from these algorithms whether $A^d(\Mbar_{0,n},\Q)$ has a permutation basis. Farkas and Gibney \cite{FarkasGibney2003} have given a permutation basis for $A^{1}(\Mbar_{0,n},\Q)$. Theorem \ref{thm:Main} implies that $\cK^1_n=A^{1}(\Mbar_{0,n},\Q)$, so:

\smallskip

\noindent\textbf{Theorem B.} \textit{The set $\{\kappa_{1}^T\thickspace|\thickspace\abs{T}\ge4, \abs{T} \text{ even}\}$ is a permutation basis of $A^{1}(\Mbar_{0,n},\Q)$.}

\smallskip

The basis given by Theorem B is different from the one given in \cite{FarkasGibney2003}, which consists of certain boundary divisors and $\psi$ classes. For odd $n$, the two bases are isomorphic as $S_n$-sets, but for even $n$ they are not.

Silversmith and the author \cite{RamadasSilversmith1} have produced a permutation basis for $A_2(\Mbar_{0,n},\Q)$, using Theorem \ref{thm:Main} as an ingredient. Very recent work of Castravet and Tevelev \cite{CastravetTevelev2020} on the derived category of $\Mbar_{0,n}$ implies that $A^*(\Mbar_{0,n},\Q)=\bigoplus_{d=0}^{n-3}A^{d}(\Mbar_{0,n},\Q)$ has a permutation basis; its elements, however, are not of pure degree. The question of whether or not $A^d(\Mbar_{0,n},\Q)$ has a permutation basis for all $d$ and $n$ remains open.

\subsection{The dual story in $A_d(\Mbar_{0,n},\Q)$ and the proof of Theorem \ref{thm:Main}} There is an $S_n$-equivariant intersection pairing $A_d(\Mbar_{0,n},\Q)\times A^d(\Mbar_{0,n},\Q)\to\Q$. To prove Theorem A, we show:

\smallskip

\noindent\textbf{Theorem C.} (Theorem \ref{thm:Main}\ref{it:KappaPerpExactly},\ref{it:KappaTypeIPairingPerfect}.) If $n\ge4$ and $1\le d\le n-3$, we have
\begin{enumerate}
\item \textit{The annihilator of $\cK^d_n\subseteq A^d(\Mbar_{0,n},\Q)$ is the subspace $\cV_{d,n}\subseteq A_d(\Mbar_{0,n},\Q)$ spanned by boundary strata whose dual trees have two or more vertices with valence at least four.}
\item \textit{$\cQ_{d,n}:=\frac{A_d(\Mbar_{0,n},\Q)}{\cV_{d,n}}$ is the dual of $\cK^d_n$.}
\end{enumerate}

\smallskip

It is straightforward to show that $\cV_{d,n}$ is contained in the annihilator of $\cK^d_n$, but to show equality involves a complicated induction on $n$. We use the fact that if $\pi$ denotes the forgetful morphism from $\Mbar_{0,n+1}$ to $\Mbar_{0,n}$, then:

\smallskip

\noindent\textbf{Theorem D.} (Theorem \ref{thm:Main}\ref{it:Sequences}) \textit{If $n\ge4$ and $1\le d\le n-3$, then we have the following (dual) exact sequences:}
    \begin{align*}
      &0\to\cQ_{d,n}\xrightarrow{\pi^*}{}\cQ_{d+1,n+1}\xrightarrow{\pi_*}{}\cQ_{d+1,n}\to0\\
       &0\to\cK^{d+1}_{n}\xrightarrow{\pi^*}{}\cK^{d+1}_{n+1}\xrightarrow{\pi_*}{}\cK^d_{n}\to0
    \end{align*}

\smallskip

It is difficult to use induction to study $A^d(\Mbar_{0,n},\Q)$, partly due to the fact that $A^d(\Mbar_{0,n},\Q)\xrightarrow{\pi^*}{}A^d(\Mbar_{0,n+1},\Q)\xrightarrow{\pi_*}{}A^{d+1}(\Mbar_{0,n},\Q)$ is not exact. This failure of exactness is also responsible for the fact that the dimensions of $A_d(\Mbar_{0,n},\Q)=A^{n-3-d}(\Mbar_{0,n},\Q)$ grow exponentially with $n$, whereas $\dim(\cK^{n-3-d}_n)$ grows as a degree-$d$ polynomial in $n$.

\subsection{Significance for dynamics on $\M_{0,n}$} \textit{Hurwitz correspondences} are a class of multivalued dynamical systems on $\M_{0,n}$. They were introduced by Koch \cite{Koch2013} in the context of Teichm\"uller theory and complex dynamics on $\P^1$, and their dynamics were studied by the author \cite{Ramadas2015, Ramadas2016, Ramadas2019}. A Hurwitz correspondence $\H$ on $\M_{0,n}$ induces a linear pushforward action on $\cQ_{d,n}$, and the $d$-th dynamical degree of $\H$ (a numerical invariant of algebraic dynamical systems) is the largest eigenvalue of this action \cite{Ramadas2015}. Theorem \ref{thm:Main} can be used to re-interpret Theorem 10.6 of \cite{Ramadas2015} to conclude that $\H$ acts on pullbacks of $\kappa$ classes, and that this action encodes important information about the dynamics of $\H$:

\smallskip

\noindent\textbf{Theorem E.} \textit{Suppose $\H$ is a Hurwitz correspondence on $\M_{0,n}$. If $1\le d\le n-3$, then  $\cK^d_n$ is invariant under the pullback $\H^*:A^d(\Mbar_{0,n},\Q)\to A^d(\Mbar_{0,n},\Q)$, and the $d$-th dynamical degree of $\H$ is the largest eigenvalue of the action of $\H^*$ on $\cK^d_n$.}

\subsection*{Acknowledgements}
I am grateful to David Speyer, Rob Silversmith, and Renzo Cavalieri for useful conversations. Rob Silversmith noticed a patten in my experimental data: the dimensions of $\cQ_{d,n}$ can be expressed as sums of binomial coefficients. This observation led me to conjecture the correct dual basis of $\cQ_{d,n}$. My initial expression of the dual basis elements was purely combinatorial; Renzo Cavalieri observed that these elements could be expressed as functionals induced by pairing with kappa classes.

\subsection*{Notation and conventions} For $n$ a positive integer, we denote by $[n]$ the set $\{1,\ldots,n\}$. For $\bA$ a finite set, we denote by $\Q\bA$ the free $\Q$-vector space on $\bA$. For $\cV$ a vector space, we denote by $\cV^{\vee}$ its dual. For a linear map $\mu:\cV\to\cX$, we denote by $\mu^{\vee}$ its dual map. If $\cW$ is a subspace of $\cV$, we denote by $\cW^\perp$ its annihilator in $\cV^{\vee}$.

\section{Cycle classes on $\Mbar_{0,n}$}\label{sec:(co)homology}

The Chow group $A_{d}(\Mbar_{0,n})$ is a finitely generated free abelian group generated, though not freely, by the fundamental classes of $d$ dimensional boundary strata \cite{Keel1992, KontsevichManin1994}. We set $\cA_{d,n}:=A_{d}(\Mbar_{0,n},\Q)$, and $\cA^{d}_n:=\cA_{n-3-d,n}$. There is an $S_n$-equivariant non-degenerate intersection pairing $\cA_{d,n}\times \cA^d_n\to \Q$; this identifies $\cA^d_n$ with $\cA_{d,n}^{\vee}$.

A stable $n$-marked tree is a tree $\sigma$ with $n$ marked legs such that every vertex has valence at least $3$ (counting the legs). Boundary strata on $\Mbar_{0,n}$ are in bijection with stable $n$-marked trees; if $\sigma$ is a stable $n$-marked tree we denote by $X_\sigma$ the corresponding boundary stratum on $\Mbar_{0,n}$. Boundary strata are isomorphic to products of smaller moduli spaces: $X_\sigma\isom \prod\Mbar_{0,\val(v)}$, where the product is over vertices $v$ of $\sigma$. We conclude that $X_\sigma$ is positive-dimensional if and only of its dual tree has at least one vertex with valence at least four. If $\sigma$ has exactly one vertex $v$ with valence at least four, then $X_\sigma$ is isomorphic to $\Mbar_{0,n'}$, where $n'=\val(v)$, since the factors in the above product decomposition of $X_\sigma$ corresponding to vertices other than $v$ are all isomorphic to single-point spaces.

\begin{Def}
We say that a positive-dimensional boundary stratum $X_\sigma$ is \textit{Type I} if its dual tree $\sigma$ has  exactly one vertex with valence at least four; in this case we also say that $\sigma$ is a Type I stable tree. We say that a positive-dimensional boundary stratum $X_\sigma$ is \textit{Type II} if its dual tree $\sigma$ has two or more vertices with valence at least four; in this case we also say that $\sigma$ is a type II stable tree. For $n\ge4$ and $d=1,\ldots, n-4$, we set $\cV_{d,n}\subset \cA_{d,n}$ to be the subspace generated by the fundamental classes of Type II boundary strata. We set $\cQ_{d,n}$ to be the quotient $\cA_{d,n}/\cV_{d,n}$. Note that since $\cV_{d,n}$ is $S_n$-invariant, $\cQ_{d,n}$ inherits an action of $S_n$. Also note that $\cQ_{d,n}$ is generated by the fundamental classes of Type I boundary strata.
\end{Def}

\begin{Def}
Suppose $\sigma$ is stable $n$-marked tree and $v$ a vertex on $\sigma$. We obtain from the pair $(\sigma, v)$ a set partition $\Pi_*(\sigma,v)$ of $[n]$ as follows: $i$ and $j$ are in the same part of $\Pi_*(\sigma, v)$ if and only if the $i$- and $j$-marked legs on $\sigma$ are on the same connected component of $\sigma\setminus \{v\}$. Note that the number of parts of $\Pi_*(\sigma, v)$ equals the valence of $v$. If $\sigma$ is Type I and $v$ is its unique vertex with valence at least four, then the partition $\Pi_*(\sigma,v)$ is intrinsically associated to $\sigma$, so we denote it by $\Pi_*(\sigma)$. In this case we have $\dim(X_{\sigma})=\abs{\Pi_*(\sigma)}-3(=\val(v)-3)$.
\end{Def}

\begin{lem}\label{lem:PartitionDeterminesClass}
Suppose that $\sigma_1$ and $\sigma_2$ are two Type I stable $n$-marked trees, and suppose $\Pi_*(\sigma_1)=\Pi_*(\sigma_2)$. Then $[X_{\sigma_1}]=[X_{\sigma_2}]\in \cA_{d,n}$, where $d=\dim(X_{\sigma_1})=\dim(X_{\sigma_2})$.
\end{lem}
\begin{proof} This follows immediately from the fact that $\sigma_1$ and $\sigma_2$ differ only in the arrangement of trivalent subtrees. See Lemma 5.2.1 of \cite{RamadasThesis} for a detailed proof.

\end{proof}

For $n\ge 1$ and $d\ge -3$, we set $\bSP_{d,n}$ to be the set of all set partitions of $[n]$ having exactly $d+3$ parts. By Lemma \ref{lem:PartitionDeterminesClass}, if $n\ge 4$ and $d\ge 1$, then there is a well-defined map $\bSP_{d,n}\to \cA_{d,n}$ sending $\Pi$ to $[X_{\sigma}]$, where $\sigma$ is any Type I stable $n$-marked tree such that $\Pi=\Pi_*(\sigma)$ (it is clear that such a $\sigma$ exists). Extending by linearity and composing with the quotient map from $\cA_{d,n}$ to $\cQ_{d,n}$, we obtain a surjective, $S_n$-equivariant, linear map $\Q\bSP_{d,n}\to \cQ_{d,n}$.

\begin{Def}\label{Def:REL}
  For $n\ge 4$ and $1\le d\le n-4,$ let $\cR_{d,n}$ be the subspace of $\Q\bSP_{d,n}$ generated by elements of the form:
  \begin{align*}
    &\{P_1\cup P_2,P_3,P_4,\ldots,P_{d+4}\}+\{P_1,P_2,P_3\cup
    P_4,\ldots,P_{d+4}\}\\
&\quad-\{P_1\cup
    P_3,P_2,P_4,\ldots,P_{d+4}\}-\{P_1,P_3,P_2\cup P_4,\ldots,P_{d+4}\},
  \end{align*}
  where $\{P_1,P_2,P_3,P_4,\ldots,P_{d+4}\}$ is a set partition of $[n]$ with $d+4$ parts.  Note that $\cR_{d,n}$ is $S_n$-invariant.
 \end{Def}

\begin{lem}
The kernel of the surjective linear map $\Q\bSP_{d,n}\to \cQ_{d,n}$ is $\cR_{d,n}$.
\end{lem}
\begin{proof}
This follows immediately from the description of linear relations among boundary strata given in Theorem 7.3 of \cite{KontsevichManin1994}, or see Lemma 5.2.4 of \cite{RamadasThesis} for a detailed proof.
\end{proof}
We conclude that $\cQ_{d,n}$ is naturally isomorphic, as an $S_n$ representation, to $\Q\bSP_{d,n}/\cR_{d,n}$. We use this identification throughout the paper.

\subsection{Kappa classes and the intersection pairing}

For $d=0,\ldots, n-3$, $\Mbar_{0,n}$ carries a codimension $d$ kappa class $\kappa_d\in \cA^d_n$, see \cite{ArbarelloCornalba1996, ArbarelloCornalba1998} for the definition and properties.

\begin{lemma}\label{lem:pairkappawithstrata}
Let $n\ge4$ and $1\le d\le n-3$. Suppose $X_\sigma$ is a dimension $d$ boundary stratum on $\Mbar_{0,n}$. Then
\begin{align}
[X_\sigma]\cdot\kappa_d=
\begin{cases}
0&\text{$X_\sigma$ is Type II}\\
1&\text{$X_\sigma$ is Type I}
\end{cases}
\end{align}
\end{lemma}

\begin{proof}
This follows by a standard computation from Equation 1.8 of \cite{ArbarelloCornalba1996} together with Lemma 1.1 (12) of \cite{CavalieriYang2011}.
\end{proof}

\begin{Def}
For $T\subseteq [n]$, set $\kappa_d^T$ to be the pullback, to $\Mbar_{0,n}$, of the codimension $d$ kappa class on $\Mbar_{0,T}$, via the natural forgetful map $\pi_T:\Mbar_{0,n}\to \Mbar_{0,T}$.
\end{Def}

\begin{Def}
Set $\mathcal{K}^d_n$ to be the subspace of $\mathcal{A}^d_n$ spanned by the classes $\{\kappa_T\thickspace|\thickspace T\subseteq [n]\}$. Note that $\mathcal{K}^d_n$ is $S_n$-invariant.
\end{Def}

\begin{lemma}\label{lem:pairkappapullbackswithstrata}
Let $n\ge4$ and $1\le d\le n-3$. Suppose $X_\sigma$ is a dimension $d$ boundary stratum on $\Mbar_{0,n}$, and $T\subseteq [n]$. Then
\begin{align}
[X_\sigma]\cdot\kappa_d^T=
\begin{cases}
0&\text{$X_\sigma$ is Type II}\\
1&\text{$X_\sigma$ is Type I and $\forall P\in\Pi_*(\sigma), \thickspace P\cap T\ne\emptyset$}\\
0&\text{$\sigma$ is Type I and $\exists P\in\Pi_*(\sigma)$ s.t. $P\cap T=\emptyset$}
\end{cases}
\end{align}
\end{lemma}
\begin{proof}
By the projection formula, $[X_\sigma]\cdot\kappa_d^T=(\pi_T)_*([X_\sigma])\cdot \kappa_d$. By \cite{Ramadas2015}, if $X_{\sigma}$ is Type II, then $\pi_*([X_{\sigma}])$ is either zero, or the fundamental class of a Type II boundary stratum of $\Mbar_{0,T}$. If $X_{\sigma}$ is Type I, then if $\exists P\in\Pi_*(\sigma)$ s.t. $P\cap T=\emptyset$, then $\pi_*([X_{\sigma}])=0$, while if $\forall P\in\Pi_*(\sigma), \thickspace P\cap T\ne\emptyset$, then $\pi_*([X_{\sigma}])$ is the fundamental class of a Type I boundary stratum of $\Mbar_{0,T}$. Applying  Lemma \ref{lem:pairkappawithstrata}, we obtain the desired result.
\end{proof}

\begin{cor}\label{cor:kappaandQduals}
\begin{enumerate}
\item The subspace $\cK_{n}^d\subseteq\cA_{n}^d$ is orthogonal, with respect to the intersection pairing, to $\cV_{d,n}\subseteq\cA_{d,n}$, i.e. we have $\cK_n^d\subseteq \cV_{d,n}^{\perp}$.\label{it:KappaPerp}
\item The intersection pairing on $\Mbar_{0,n}$ descends to a pairing $\cQ_{d,n}\times\cK_{n}^d\to\Q$. \label{it:KappaTypeIPairing}
\end{enumerate}
\end{cor}
We will eventually show that $\cK_n^d=\cV_{d,n}^{\perp}$, which implies that $\cK_n^d=\cQ_{d,n}^{\vee}$.
\begin{Def}\label{Def:Pairing}
 Define a pairing
   $ \langle\cdot,\cdot\rangle:\{\text{set partitions
    of $[n]$}\}\times\{\text{subsets of $[n]$}\}\to\Z$.
 For a set partition $\Pi$ and subset $T$, set
  \begin{align*}
    \langle\Pi,T\rangle=
    \begin{cases}
      1&\text{$\forall P\in\Pi, \quad P\cap T\ne\emptyset$}\\
      0&\exists P\in\Pi \text{ s.t. }P\cap T=\emptyset
    \end{cases}
  \end{align*}

\end{Def}
 From Lemma \ref{lem:pairkappapullbackswithstrata} we obtain a purely combinatorial description of the pairing between $\cQ_{d,n}$ and $\cK^d_n$ obtained in Corollary \ref{cor:kappaandQduals}:

 \begin{lem}\label{lem:combinatorialpairing}
  For any Type I $d$-dimensional boundary stratum $X_\sigma$, and for any subset $T\subseteq[n]$, we have that $[X_\sigma]\cdot \kappa^T_d=\langle\Pi_*(\sigma),T\rangle$.
  \end{lem}

\subsection{Pushing forward and pulling back via forgetful maps}

The forgetful morphism $\pi:\Mbar_{0,n+1}\to\Mbar_{0,n}$ induces pushforward maps $\pi_*:\cA_{d,n+1}\to\cA_{d,n}$ and pullback maps $\pi^*:\cA_{d,n}\to\cA_{d+1,n+1}$. By \cite{Ramadas2015}, $\pi_*(\cV_{d,n+1})\subseteq \cV_{d,n}$. Also, if $X_\sigma$ is a Type II boundary stratum, then $\pi^*([X_{\sigma}])$ is a sum of fundamental classes of Type II boundary strata of $\Mbar_{0,n+1}$. This implies that $\pi^*(\cV_{d,n})\subseteq \cV_{d+1,n+1}$. Thus there are induced pushforward maps $\pi_*:\cQ_{d,n+1}\to\cQ_{d,n}$ and pullback maps $\pi^*:\cQ_{d,n}\to\cQ_{d+1,n+1}$.

\begin{lem}
\begin{enumerate}
\item The pushforward $\pi_*:\cQ_{d,n+1}\to\cQ_{d,n}$ lifts to $\tilde{\pi}_*:\Q\bSP_{d,n+1}\to\Q\bSP_{d,n}$ where
\begin{align*}
\tilde{\pi}_*(\{P_1,\ldots,P_{d+3}\})=&
                          \begin{cases}
                            0&\exists i \text{ s.t. }P_i=\{n+1\}\\
                            \{P_1\setminus\{n+1\},\ldots,P_{d+3}\setminus\{n+1\}\}&\text{otherwise}
                          \end{cases}
\end{align*}
\item The pullback $\pi^*:\cQ_{d,n}\to\cQ_{d+1,n+1}$ lifts to $\tilde{\pi}^*:\Q\bSP_{d,n}\to\Q\bSP_{d+1,n+1}$ where $\tilde{\pi}^{*}(\Pi)=\Pi\cup\{\{n+1\}\}$, for $\Pi\in\bSP_{d,n}$
\end{enumerate}
\end{lem}
\begin{proof}[Sketch of proof]
This lemma follows from the observation that if $X_\sigma$ is a Type I $d$-dimensional boundary stratum whose dual tree $\sigma$ has exactly one vertex with valence at least four, then
\begin{align}\label{eq:pullbackstratum}
\pi^{*}([X_\sigma])=[X_{\sigma'}]+(\text{sum of classes of Type II boundary strata}),
\end{align}
 where $\sigma'$ is a Type I stable $(n+1)$-marked tree with the property that $\Pi_*(\sigma')=\Pi_*(\sigma)\cup\{\{n+1\}\}$.
\end{proof}

The pushforward maps $\pi_*:\cA_{d,n+1}\to\cA_{d,n}$ and $\pi_*:\cQ_{d,n+1}\to\cQ_{d,n}$ are easily seen to be surjective. Since $\pi$ has positive relative dimension (equal to one), $\pi_*\circ\pi^*=0$ on $\cA_{*,*}$, thus also on $\cQ_{*,*}$.

\begin{lem}\label{lem:exactinmiddle}
  For $n\ge 4$ and $k\ge 1$, the complex $\cQ_{d,n}\xrightarrow{\pi^*}{}\cQ_{d+1,n+1}\xrightarrow{\pi_*}{}\cQ_{d+1,n}$ is exact.
\end{lem}
\begin{proof} We use the lifts of $\pi^*$ and
  $\pi_*$ to $\tilde{\pi}^*:\Q\bSP_{d,n}\to \Q\bSP_{d+1,n+1}$ and
  $\tilde{\pi}_*:\Q\bSP_{d+1,n+1}\to \Q\bSP_{d+1,n}$ respectively. We have:

  $$\Ker(\tilde{\pi}_*)=\Im(\tilde{\pi}^*)
  +\Span(\{P_1\cup\{n+1\},P_2,P_3,P_4,\ldots\}-\{P_1,P_2\cup\{n+1\},P_3,P_4,\ldots\}\}),$$

and:

\begin{align*}
  &\{P_1\cup\{n+1\},P_2,P_3,P_4,\ldots\}-\{P_1,P_2\cup\{n+1\},P_3,P_4,\ldots\}\\
  =&\left(\{P_1\cup\{n+1\},P_2,P_3,P_4,\ldots\} +\{P_1,\{n+1\},P_2\cup
    P_3,P_4,\ldots\}\right.\\&\quad\quad\left.-\{P_1,P_3,P_2\cup\{n+1\},P_4,\ldots\}-\{P_1\cup
    P_3,P_2,\{n+1\},P_4,\ldots\}\right)\\
  &\quad\quad-\left(\{P_1,\{n+1\},P_2\cup
    P_3,P_4,\ldots\}-\{P_1\cup P_3,P_2,\{n+1\},P_4,\ldots\}\right)\in \cR_{k+1,n+1}+\Im(\tilde{\pi}^*)
\end{align*}
This implies that  $\Ker(\tilde{\pi}_*)=\Im(\tilde{\pi}^*)+\cR_{k+1,n+1}$, which in turn implies that $\Ker(\pi_*)=\Im(\pi^*)$.
\end{proof}

The pullback $\pi^*:\cA^d_n\to\cA^d_{n+1}$, which by the projection formula is dual to $\pi_*:\cA_{d,n}\to\cA_{d,n+1}$, restricts to $\pi^*:\cK^d_n\to\cK^d_{n+1}$, and sends $\kappa_d^T$ on $\Mbar_{0,n}$ to $\kappa_d^T$ on $\Mbar_{0,n+1}$. The pushforward  $\pi_*:\cA^{d+1}_{n+1}\to\cA^d_{n}$ is dual to $\pi^*:\cA_{d+1,n+1}\to\cA_{d,n}$.

\begin{lem}
The pushforward  $\pi_*:\cA^{d+1}_{n+1}\to\cA^d_{n}$ restricts to $\pi_*:\cK^{d+1}_{n+1}\to\cK^d_{n}$, with
\begin{align*}
\pi_* (\kappa_d^T)  =   \begin{cases}
                            0& n+1\in T\\
                            \kappa_d^T & n+1\not\in T
                          \end{cases}
\end{align*}
\end{lem}
\begin{proof}
By Lemma \ref{cor:kappaandQduals}, \ref{it:KappaPerp}, we have that $\forall d,n, \cK^d_n\subseteq \cV_{d,n}^{\perp}$.  Since $\pi^*(\cV_{d,n})\subseteq \cV_{d+1,n+1}$, and since, by the projection formula, $\pi_*$ and $\pi^*$ are dual maps, we have that $\pi_*(\cK^{d+1}_{n+1})\subseteq \cV_{d,n}^{\perp}$. This means that for $T\subseteq[n+1]$, the class $\pi_*(\kappa_d^T)$ is determined by the functional that it defines on $\cQ_{d,n}$, i.e. by the values of $[X_\sigma]\cdot \pi_*(\kappa_d^T)$, where $X_\sigma$ ranges over all Type I $d$-dimensional boundary strata on $\Mbar_{0,n}$. Given such an $X_\sigma$, we have, by the projection formula, by the expression for $\pi^*([X_\sigma])$ given in Equation \ref{eq:pullbackstratum}, and by applying Lemma \ref{lem:combinatorialpairing} twice, that
\begin{align*}
[X_\sigma]\cdot \pi_*(\kappa_d^T)=\pi^{*}([X_\sigma])\cdot \kappa_d^T &=\langle\Pi_*(\sigma)\cup\{\{n+1\}\},T\rangle\\
&=  \begin{cases}
      1&\text{if $\forall P\in\Pi_*(\sigma)\cup\{\{n+1\}\}, P\cap T\ne\emptyset$}\\
      0&\text{if $\exists P\in\Pi_*(\sigma)\cup\{\{n+1\}\}$ s.t. $P\cap T=\emptyset$}
    \end{cases}\\
&          =  \begin{cases}
      1&\text{if $\forall P\in\Pi_*(\sigma), P\cap T\ne\emptyset$, and $n+1\in T$}\\
      0&\text{if $\exists P\in\Pi_*(\sigma)$ s.t. $P\cap T=\emptyset $, or if $n+1\not\in T$}
    \end{cases}\\
                &=  \begin{cases}
                \langle\Pi_*(\sigma),T\rangle &\text{if $n+1\in T$}\\
                0&\text{if $n+1\not\in T$}
                \end{cases}\\
                 &=  \begin{cases}
 [X_\sigma]\cdot \kappa_d^T  & \text{if $n+1\in T$}\\
                0&\text{if $n+1\not\in T$}
                \end{cases}
\end{align*}
\end{proof}

\section{Main results and proofs}\label{sec:Proofs}

\subsection{The set-up}\label{sec:setup}
Throughout Section \ref{sec:Proofs}, we use the identification $\cQ_{d,n}=\Q\bSP_{d,n}/\cR_{d,n}$ introduced in Section \ref{sec:(co)homology}; we write an element of $\cQ_{d,n}$ as a $\Q$-linear combination of set partitions of $[n]$ with $d+3$ parts, rather than as a $\Q$-linear combination of fundamental classes of Type I boundary strata.

\begin{Def}
For $n\ge1$ and $d\ge -3$, we set $\bK^d_n$ to be the set $\{T\subseteq[n]\thickspace|\thickspace\abs{T}\ge(d+3), \abs{T}\equiv (d+3)\mod 2\}$.
\end{Def}

\begin{Def}\label{Def:bKintocK}
There is a natural linear map $\psi_{d,n}:\Q\bK^d_n\to\cK^d_n$ sending $T$ to $\kappa_d^T$.
\end{Def}

The map $\psi_{d,n}$, together with the intersection pairing $\cQ_{d,n}\times\cK_{n}^d\to\Q$ induces the pairing $\cQ_{d,n}\times\Q\bK^d_n\to\Q$, where, for $\Pi\in\bSP_{d,n}$ and $T\in \bK^d_n$, $\Pi\cdot T=\langle\Pi,T\rangle$ as in Definition \ref{Def:Pairing}.
Note that if $\bS$ is an $S_n$-set, then $\Q\bS$ is canonically and $S_n$-equivariantly isomorphic to its dual. Thus $\Q\bK^d_n=(\Q\bK^d_n)^{\vee}$.

\begin{Def}\label{def:phi}
For $d\ge -1$, the pairing $\langle.,.\rangle$ (Definition \ref{Def:Pairing}) between set partitions and subsets of $[n]$ induces a map $\tilde{\phi}_{d,n}:\Q\bSP_{d,n}\to (\Q\bK^{d}_{n})^{\vee}=\Q\bK^{d}_{n}$. For $d\ge1,$ $\tilde{\phi}_{d,n}$ descends to a map $\phi_{d,n}:\cQ_{d,n}\to \Q\bK^{d}_{n}$. The map $\tilde{\phi}_{d,n}$ on generators $\Pi\in\bSP_{d,n}$ is given explicitly by:
\begin{align*}
  \tilde{\phi}_{d,n}(\Pi)=\sum_{T\in\bK^{d}_{n}}\langle\Pi,T\rangle \cdot T.
\end{align*}
\end{Def}

\begin{Def}\label{Def:AlphaBeta} Define maps $\alpha:\Q\bK^{d}_{n}\to \Q\bK^{d+1}_{n+1}$ and $\beta:\Q\bK^{d}_{n+1}\to \Q\bK^{d}_{n}$, where:
\begin{align*}
\alpha(T)&= T\cup\{n+1\}& \beta(T)&= \begin{cases}
       T&n+1\not\in T\\
       0&n+1\in T
     \end{cases}
\end{align*}
\end{Def}

\begin{lem}\label{lem:exactsequence}
The following is an exact sequence:
\begin{align}
0\to\Q\bK^{d}_{n}\xrightarrow{\alpha}{}\Q\bK^{d+1}_{n+1}\xrightarrow{\beta}{}\Q\bK^{d+1}_{n}\to0\label{eq:seqbK}
\end{align}
\end{lem}
\begin{proof}[Sketch of proof]
Observe that $\Im(\alpha)=\Ker(\beta)=\Q\{T\in\bK^{d+1}_{n+1}\thickspace|\thickspace n+1\in T\}$.
\end{proof}

\begin{lem}\label{lem:alphabetacommutewithpushpull}
The following diagram commutes:
\begin{center}
    \begin{tikzcd}
      &\Q\bSP_{d,n}\arrow[r,"\tilde{\pi}^*"]\arrow[d,"\tilde{\phi}_{d,n}"]&\Q\bSP_{d+1,n+1}\arrow[r,"\tilde{\pi}_*"]\arrow[d,"\tilde{\phi}_{d+1,n+1}"]&\Q\bSP_{d+1,n}\arrow[d,"\tilde{\phi}_{d+1,n}"]\\
      &\Q\bK^{d}_{n}\arrow[r,"\alpha"]&\Q\bK^{d+1}_{n+1}\arrow[r,"\beta"]&\Q\bK^{d+1}_{n}
    \end{tikzcd}
  \end{center}
\end{lem}
\begin{proof}
\noindent\textbf{Commutativity of the left square:}
Given $\Pi\in\bSP_{d,n}$, we have
\begin{align*}
\phi_{d+1,n+1}(\tilde{\pi}^{*}(\Pi))=\sum_{T\in\bK^{d+1}_{n+1}}\langle\Pi\cup\{\{n+1\}\},T\rangle \cdot T&=\sum_{\substack{T\in\bK^{d+1}_{n+1}\\n+1\in T}}\langle\Pi\cup\{\{n+1\},T\rangle \cdot T\\
&=\sum_{\substack{T'\in\bK^{d}_{n}}}\langle\Pi,T'\rangle \cdot T'\cup\{n+1\}\\

&=\alpha(\sum_{\substack{T'\in\bK^{d}_{n}}}\langle\Pi,T'\rangle \cdot T')=\alpha(\phi_{d,n}(\Pi))
\end{align*}

\noindent\textbf{Commutativity of the right square:}
Given $\Pi'=\{P_1,\ldots,P_{d+4}\}\in\bSP_{d+1,n+1}$, we may assume without loss of generality that $n+1\in P_1$. There are two cases:

\noindent\textbf{Case 1:} $P_1=\{n+1\}$. Then $\tilde{\pi}_{*}(\Pi')=0$ so $\phi_{d+1,n}(\tilde{\pi}_{*}(\Pi'))=0$. Note that for $T\subset [n+1]$, we have that if $n+1\not\in T$, then $\langle\Pi',T\rangle=0$, while if $n+1\in T$, then $\beta(T)=0$. This implies that
\begin{align*}
\beta(\phi_{d+1,n+1}(\Pi'))&=\beta(\sum_{T\in\bK^{d+1}_{n+1}}\langle\Pi',T\rangle \cdot T)=\beta(\sum_{\substack{T\in\bK^{d+1}_{n+1}\\n+1\in T}}\langle\Pi',T\rangle \cdot T)=0,
\end{align*}

\noindent\textbf{Case 2:} $P_1\ne\{n+1\}$. Then

\begin{align*}
\phi_{d+1,n}(\tilde{\pi}_{*}(\Pi'))&=\sum_{T'\in\bK^{d+1}_{n}}\langle\{P_1\setminus\{n+1\},P_2,\ldots,P_{d+4}\},T'\rangle \cdot T'\\
&=\sum_{\substack{T'\in\bK^{d+1}_{n}\\T'\cap P_1\setminus\{n+1\}\ne\emptyset\\T'\cap P_2,\ldots,T'\cap P_{d+1}\ne\emptyset}} T'=\sum_{\substack{T'\in\bK^{d+1}_{n+1}\\n+1\not\in T\\\langle\Pi',T\rangle=1}} T'=\beta(\phi_{d+1,n+1}(\Pi'))
\end{align*}
\end{proof}

We use the following lemma several times; its proof follows from a standard diagram chase.

\begin{lem}\label{lem:fourvariant}[Variant of the Four Lemma]
Suppose we have a commutative diagram of vector spaces as follows
  \begin{center}
 \begin{tikzcd}
      &\cW_1\arrow[r,"f_1"]\arrow[d,"h_1"]&\cW_2\arrow[r,"f_2"]\arrow[d,"h_2"]&\cW_3\arrow[d,"h_3"]\arrow[r]&0\\
      &\cX_1\arrow[r,"g_1"]&\cX_2\arrow[r,"g_2"]&\cX_3
    \end{tikzcd}
  \end{center}
Suppose further that the bottom row is exact at $\cX_2$, that the top row is exact at $\cW_3$, and that $h_1$ and $h_3$ are surjective. Then $h_2$ is surjective.
\end{lem}
\subsection{A preliminary lemma}
In this section, we prove some technical results --- Lemmas \ref{lem:evenoddsurjective}, \ref{lem:n2surjective} and  \ref{lem:n3surjective}. These are not of independent interest, but are necessary to prove Theorem \ref{thm:root} in Section \ref{sec:Main}. The proofs (and statements) of these three lemmas are conceptually similar to each other, as well as to those of Theorem \ref{thm:root}; all four proofs use the Four Lemma to induct on $n$. Lemma \ref{lem:evenoddsurjective} is required in the inductive step of Lemma \ref{lem:n2surjective}, which is required in the inductive step of Lemma \ref{lem:n3surjective}, which in turn is required in the inductive step of Theorem \ref{thm:root}. The proofs of Lemmas \ref{lem:evenoddsurjective} and \ref{lem:n2surjective} also involve some intricate combinatorics of set partitions and subsets.

\begin{Def}\label{def:EvenOdd} For $n>0$, we set:
\begin{align*}
\bE_{n}&:= \{T\subseteq[n]|\abs{T} \text{ even}\}; & \bO_{n}&:=\{T\subseteq[n]|\abs{T}\text{ odd}\};& \bF_{n}&:=\{(P_1,P_2)|P_1\cup P_2=[n],P_1\cap P_2=\emptyset,1\in P_1\}
  \end{align*}
\end{Def}

Note that $\bF_{n}\setminus\{([n],\emptyset)\}$ is in canonical bijection with $\bSP_{-1,n}$, so $\Q\bF_n$ is canonically isomorphic to $\Q\{([n],\emptyset)\}\oplus\Q\bSP_{-1,n}$. There are maps $\alpha:\Q\bE_n\to \Q\bO_{n+1}$, $\alpha:\Q\bO_n\to \Q\bE_{n+1}$, $\beta:\Q\bE_{n+1}\to \Q\bE_n$ and $\beta:\Q\bO_{n+1}\to \Q\bO_n$, analogous to the maps $\alpha$ and $\beta$ as in Definition \ref{Def:AlphaBeta}. Define maps $\odd_n:\Q\bF_{n}\to \Q\bO_{n}$ and $\even_n:\Q\bF_{n}\to \Q\bE_{n}$, where
\begin{align*}
\odd_n((P_1,P_2))&=\sum_{\substack{T\subseteq P_1\\\text{$\abs{T}$
  odd}}}(-T)+\sum_{\substack{T\subseteq P_2\\\text{$\abs{T}$
  odd}}}T; &
 \even_n((P_1,P_2))&=\sum_{\substack{T\subseteq P_1\\\text{$\abs{T}$
  even}}}(-T)+\sum_{\substack{T\subseteq P_2\\\text{$\abs{T}$
  even}}}(-T)
\end{align*}

\begin{lem}\label{lem:evenoddsurjective}
 For $n\ge1$, the maps $\odd_n$ and $\even_n$ are surjective.
\end{lem}
\begin{proof}
  We induct on $n$. \textbf{Base case:} $n=1$. We have:
  \begin{align*}
    \bF_{1}&=\{(\{1\},\emptyset)\}; &  \bE_1&=\{\emptyset\}; & \bO_1&=\{\{1\}\}; &   \odd_1((\{1\},\emptyset))&=-\{1\};&  \even_1((\{1\},\emptyset))&=-2\emptyset.
  \end{align*}
  This establishes the base case.

  \noindent \textbf{Inductive hypothesis:} The proposition holds up to some $n\ge1$.

  \noindent \textbf{Inductive step:} Define maps $\tilde{\pi'}_*:\Q\bF_{n+1}\to \Q\bF_{n}$ and $\gamma:\Q\bF_{n}\to \Q\bF_{n+1}$, where:
  \begin{align*}
    \tilde{\pi'}_*((P_1,P_2))&=(P_1\setminus\{n+1\},P_2\setminus\{n+1\})\\
 \gamma((P_1,P_2))&=(P_1'\cup\{n+1\},P_2')-(P_1',P_2'\cup\{n+1\}).
  \end{align*}
  The diagram below has exact rows; we claim it commutes.
  \begin{center}
    \begin{tikzcd}
      &\Q\bF_{n}\arrow[r,"\gamma"]\arrow[d,"\even_{n}"]&\Q\bF_{n+1}\arrow[r,"\tilde{\pi'}_*"]\arrow[d,"\odd_{n+1}"]&\Q\bF_{n}\arrow[r,""]\arrow[d,"\odd_{n}"]&0\\
0\arrow[r]&\Q\bE_{n}\arrow[r,"\alpha"]&\Q\bO_{n+1}\arrow[r,"\beta"]&\Q\bO_{n}\arrow[r]&0
    \end{tikzcd}
  \end{center}

 \noindent\textbf{Commutativity of the left square:} For
    $(P_1',P_2')\in \Q\bF_{n},$
    \begin{align*}
      \odd_{n+1}(\gamma(P_1',P_2'))&=\odd_{n+1}(P_1'\cup\{n+1\},P_2')-\odd_{n+1}(P_1',P_2'\cup\{n+1\})\\
      &=\sum_{\substack{T\subseteq P_1'\cup\{n+1\}\\\text{$\abs{T}$      odd}}}(-T)+\sum_{\substack{
        T\subseteq P_2'\\\text{$\abs{T}$
          odd}}}(T)-\left(\sum_{\substack{
        T\subseteq P_1'\\\text{$\abs{T}$
          odd}}}(-T)+\sum_{\substack{
        T\subseteq P_2'\cup\{n+1\}\\\text{$\abs{T}$
          odd}}}(T)\right)\\
      &=\sum_{\substack{T\subseteq P_1'\cup\{n+1\}\\\text{$\abs{T}$
            odd}\\
          n+1\in T}}(-T)+\sum_{\substack{T\subseteq P_2'\cup\{n+1\}\\\text{$\abs{T}$
            odd}\\
          n+1\in T}}(-T)\\
      &=\sum_{\substack{T'\subseteq P_1'\\\text{$\abs{T'}$
            even}}}(-(T'\cup\{n+1\}))+\sum_{\substack{T'\subseteq P_2'\\\text{$\abs{T'}$
            even}}}(-(T'\cup\{n+1\}))\\
      &=\alpha(\even_n(P_1',P_2')).
    \end{align*}
  \noindent\textbf{Commutativity of the right square:} For
    $(P_1,P_2)\in \Q\bF_{n+1},$
    \begin{align*}
      \odd_{n}(\tilde{\pi'}_*(P_1,P_2))&=\odd_{n}(P_1\setminus\{n+1\},P_2\setminus\{n+1\})\\
                                &=\sum_{\substack{T\subseteq P_1\setminus\{n+1\}\\\text{$\abs{T}$
      odd}}}(-T)+\sum_{\substack{T\subseteq P_2\setminus\{n+1\}\\\text{$\abs{T}$
      odd}}}(T)\\

                                &=\beta(\odd_{n+1}(P_1,P_2)).
    \end{align*}

  This proves the claim. By the inductive hypothesis, $\even_{n}$
  and $\odd_{n}$ are surjective, so by the Four Lemma, $\odd_{n+1}$ is surjective.

 The digram below has exact rows; we claim it commutes.
  \begin{center}
    \begin{tikzcd}
      &\Q\bF_{n}\arrow[r,"\gamma"]\arrow[d,"\odd_{n}"]&\Q\bF_{n+1}\arrow[r,"\tilde{\pi'}_*"]\arrow[d,"\even_{n+1}"]&\Q\bF_{n}\arrow[r]\arrow[d,"\even_{n}"]&0\\
      0\arrow[r]&\Q\bO_{n}\arrow[r,"\alpha"]&\Q\bE_{n+1}\arrow[r,"\beta"]&\Q\bE_{n}\arrow[r]&0
    \end{tikzcd}
  \end{center}

\noindent\textbf{Commutativity of the left square:} For
    $(P_1',P_2')\in \Q\bF_{n},$
    \begin{align*}
      \even_{n+1}(\gamma(P_1',P_2'))&=\even_{n+1}(P_1'\cup\{n+1\},P_2')-\even_{n+1}(P_1',P_2'\cup\{n+1\})\\
                               &=\sum_{\substack{T\subseteq P_1'\cup\{n+1\}\\\text{$\abs{T}$
      even}}}(-T)+\sum_{\substack{T\subseteq P_2'\\\text{$\abs{T}$
      even}}}(-T)-\left(\sum_{\substack{T\subseteq P_1'\\\text{$\abs{T}$
      even}}}(-T)+\sum_{\substack{T\subseteq P_2'\cup\{n+1\}\\\text{$\abs{T}$
      even}}}(-T)\right)\\
                               &=\sum_{\substack{T\subseteq P_1'\cup\{n+1\}\\\text{$\abs{T}$
      even}\\n+1\in T}}(-T)+\sum_{\substack{T\subseteq P_2'\cup\{n+1\}\\\text{$\abs{T}$
      even}\\n+1\in T}}(T)\\
                               &=\sum_{\substack{T'\subseteq P_1'\\\text{$\abs{T'}$
      odd}}}-(T'\cup\{n+1\})+\sum_{\substack{T'\subseteq P_2'\\\text{$\abs{T'}$
      odd}}}(T'\cup\{n+1\})\\
      &=\alpha(\odd_{n}(P_1',P_2')).
    \end{align*}
 \noindent\textbf{Commutativity of the right square:} For
    $(P_1,P_2)\in \Q\bF_{n+1},$
    \begin{align*}
      \even_{n}(\tilde{\pi'}_*(P_1,P_2))&=\even_{n}(P_1\setminus\{n+1\},P_2\setminus\{n+1\})\\
                                 &=\sum_{\substack{T\subseteq P_1\setminus\{n+1\}\\\text{$\abs{T}$
      even}}}(-T)+\sum_{\substack{T\subseteq P_2\setminus\{n+1\}\\\text{$\abs{T}$
      even}}}(-T)\\
                                 &=\beta(\even_{n+1}(P_1,P_2)).
    \end{align*}
  This proves the claim. Again, by the inductive hypothesis, $\odd_{n}$ and $\even_{n}$ are surjective, so by Lemma \ref{lem:fourvariant}, $\even_{n+1}$ is surjective.
\end{proof}

We only use the fact that $\odd_n$ is surjective to proceed; we use it to prove Lemma \ref{lem:n2surjective}

\begin{lem}\label{lem:n2surjective}
  For all $n\ge 2$, the map $\tilde{\phi}_{-1,n}:\Q\bSP_{-1,n}\to \Q\bK^{-1}_n$ is surjective.
\end{lem}
\begin{proof}
  We induct on $n$.

\noindent \textbf{Base case:} $n=2.$ We have $\bSP_{-1,2}=\{\{\{1\},\{2\}\}\}$ and $\bK^{-1}_2=\{\{1,2\}\}$. We have $\tilde{\phi}_{2,2}(\{\{1\},\{2\}\})=\langle\{\{1\},\{2\}\},\{1,2\}\rangle\cdot\{1,2\}=1\cdot\{1,2\}$, which shows that $\tilde{\phi}_{2,2}$ is surjective.

\noindent  \textbf{Inductive hypothesis:} The lemma holds up to some $n\ge 2$.

\noindent  \textbf{Inductive step:} Define a map $\gamma:\Q\bF_{n}\to \Q\bSP_{-1,n+1}$, where $\gamma((P_1', P_2'))=\{P_1'\cup\{n+1\}, P_2'\}-\{P_1', P_2'\cup\{n+1\}\}$. Consider the digram
  \begin{center}
    \begin{tikzcd}
      &\Q\bF_{n}\arrow[r,"\gamma"]\arrow[d,"\odd_{n}"]&\Q\bSP_{-1,n+1}\arrow[r,"\tilde{\pi}_*"]\arrow[d,"\tilde{\phi}_{-1,n+1}"]&\Q\bSP_{-1,n}\arrow[r]\arrow[d,"\tilde{\phi}_{-1,n}"]&0\\
      0\arrow[r]&\Q\bO_{n}\arrow[r,"\alpha"]&\Q\bK^{-1}_{n+1}\arrow[r,"\beta"]&\Q\bK^{-1}_{n}\arrow[r]&0
    \end{tikzcd}
  \end{center}
 Here, $\tilde{\pi}_*\circ\gamma=0$, the bottom row is exact, and $\tilde{\pi}_*$ is surjective. Note that the right square commutes by Lemma \ref{lem:alphabetacommutewithpushpull}; we claim the left square commutes as well.

 \noindent\textbf{Commutativity of the left square:} For $(P_1',P_2')\in \Q\bF_{n},$
  \begin{align*}
    \tilde{\phi}_{-1,n+1}(\gamma(P_1',P_2'))&=\tilde{\phi}_{-1,n+1}(\{P_1'\cup\{n+1\},P_2'\})-\tilde{\phi}_{-1,n+1}(\{P_1'\},P_2'\cup\{n+1\}\})\\
                                 &=\sum_{\substack{T\subseteq[n+1]\\\abs{T}\ge2\\\text{$\abs{T}$
    even}\\T\cap(P_1'\cup\{n+1\})\ne\emptyset\\T\cap P_2'\ne\emptyset}}(T)-\sum_{\substack{T\subseteq[n+1]\\\abs{T}\ge2\\\text{$\abs{T}$
    even}\\T\cap(P_1')\ne\emptyset\\T\cap
    P_2'\cup\{n+1\}\ne\emptyset}}(T)\\
                                 &=\sum_{\substack{T\subseteq[n+1]\\\abs{T}\ge2\\\text{$\abs{T}$
    even}\\n+1\in T\\T\setminus\{n+1\}\subseteq P_2'}}(T)-\sum_{\substack{T\subseteq[n+1]\\\abs{T}\ge2\\\text{$\abs{T}$
    even}\\n+1\in T\\T\setminus\{n+1\}\subseteq P_1'}}(T)\\
                                 &=\sum_{\substack{T'\subseteq[n]\\\text{$\abs{T}$
    odd}\\T'\subseteq P_2'}}(T'\cup\{n+1\})-\sum_{\substack{T'\subseteq[n]\\\text{$\abs{T}$
    odd}\\T'\subseteq P_1'}}(T'\cup\{n+1\})\\
                                 &=\alpha(\odd_{n}(P_1',P_2')).
  \end{align*}
This proves the claim. Since $\odd_{n}$ is surjective, and by the
inductive hypothesis so is $\tilde{\phi}_{-1,n}$, By Lemma \ref{lem:fourvariant}, $\tilde{\phi}_{-1,n+1}$ is surjective.
\end{proof}

\begin{lem}\label{lem:n3surjective}
  For all $n\ge 3$, the map $\tilde{\phi}_{0,n}:\Q\bSP_{0,n}\to \Q\bK^{0}_{n}$ is surjective.
\end{lem}
\begin{proof}
We induct on $n$.

\noindent\textbf{Base case:} We have $\bSP_{0,3}=\{\{\{1\},\{2\},\{3\}\}\}$, $\bK^{0}_{3}=\{\{1,2,3\}\}$, and $\tilde{\phi}_{0,3}(\{\{1\},\{2\},\{3\}\})=\{1,2,3\}$, so $\tilde{\phi}_{0,3}$ is surjective.

\noindent\textbf{Inductive hypothesis:} The proposition holds up to some $n\ge4$.

\noindent\textbf{Inductive step:} Consider the following diagram, which commutes by Lemma \ref{lem:alphabetacommutewithpushpull}
\begin{center}
    \begin{tikzcd}
      &\Q\bSP_{-1,n}\arrow[r,"\tilde{\pi}^*"]\arrow[d,"\tilde{\phi}_{-1,n}"]&\Q\bSP_{0,n+1}\arrow[r,"\tilde{\pi}_*"]\arrow[d,"\tilde{\phi}_{0,n+1}"]&\Q\bSP_{0,n}\arrow[r]\arrow[d,"\tilde{\phi}_{0,n}"]&0\\
      0\arrow[r]&\Q\bK^{-1}_{n}\arrow[r,"\alpha"]&\Q\bK^{0}_{n+1}\arrow[r,"\beta"]&\Q\bK^{0}_{n}\arrow[r]&0
    \end{tikzcd}
  \end{center}
  By the inductive hypothesis, $\tilde{\phi}_{0,n}$ is
  surjective. By Lemma \ref{lem:n2surjective}, $\tilde{\phi}_{-1,n}$ is
  surjective, so by the Four Lemma, $\tilde{\phi}_{0,n+1}$ is surjective, as desired.
\end{proof}

\subsection{An inductive proof of Theorem \ref{thm:root}}\label{sec:Main}

\begin{lem}\label{lem:dimensionsequal}
  $\dim\cQ_{1,n}=\dim \Q\bK^1_{n}$ for all $n\ge 4$.
\end{lem}
\begin{proof}
  There are no Type II 1-dimensional boundary strata, so $\forall n\ge 4$, $\cV_{1,n}=\{0\}$ and $\cQ_{1,n}\cong\cA_{1,n}$. By \cite{FarkasGibney2003}, $\dim\cA_{1,n}=2^{n-1}-\binom{n}{2}-1$. On the other hand,
\begin{align*}
  \dim \Q\bK^1_{n}=\#\{T\subseteq[n]|\text{$\abs{T}$ even},\abs{T}\ge4\}=2^{n-1}-\binom{n}{2}-1.
\end{align*}
\end{proof}

\begin{lem}\label{lem:nminus3}
For all $n\ge 4$, $\phi_{n-3,n}$ is an isomorphism.
\end{lem}
\begin{proof}
For all $n\ge 4$, we have that $\cV_{n-3,n}=\{0\}$, $\cA_{n-3,n}=\cQ_{n-3,n}=\Q\{\{\{1\},\ldots,\{n\}\}\}$, $\bK^{n-3}_n=\{[n]\}$, and  $\phi_{n-3,n}:\cQ_{n-3,n}\to\Q\bK^{n-3}_{n}$ sends $\{\{1\},\ldots,\{n\}\}$ to $[n]$. Thus $\phi_{n-3,n}$ is an
  isomorphism.
\end{proof}

\begin{thm}\label{thm:root}
For $n\ge4$ and $d$ such that $1\le d\le n-3$, $\phi_{d,n}:\cQ_{d,n}\to \Q\bK^{d}_{n}$ is an isomorphism.
\end{thm}

\begin{proof}[Inductive proof of Theorem \ref{thm:root}]

 \noindent\textbf{Base case:} $n=4$; then $1\le d\le n-3$ implies that $d=1=n-3$. By Lemma \ref{lem:nminus3}, $\phi_{1,4}$ is an isomorphism.

 \noindent\textbf{Inductive hypothesis:} For some $n\ge4,$ and for all $d$ with $1\le d\le n-3,$ we have that $\phi_{d,n}:\cQ_{d,n}\to \Q\bK^{d}_{n}$ is an isomorphism.

 \noindent\textbf{Inductive step:} For $1\le d\le (n-4)$, we have the following diagram, which commutes by Lemma \ref{lem:alphabetacommutewithpushpull}:
\begin{center}
    \begin{tikzcd}
      \Ker(\pi^*)\arrow[r]\arrow[d]&\cQ_{d,n}\arrow[r,"\pi^*"]\arrow[d,"\phi_{d,n}","\cong"
      swap]&\cQ_{d+1,n+1}\arrow[r,"\pi_*"]\arrow[d,"\phi_{d+1,n+1}"]&\cQ_{d+1,n}\arrow[r]\arrow[d,"\phi_{d+1,n}","\cong" swap]&0\\
      0\arrow[r]&\Q\bK^{d}_{n}\arrow[r,"\alpha"]&\Q\bK^{d+1}_{n+1}\arrow[r,"\beta"]&\Q\bK^{d+1}_{n}\arrow[r]&0
    \end{tikzcd}
  \end{center}
  The top row is exact by Lemma \ref{lem:exactinmiddle}, and the bottom row is exact by Lemma \ref{lem:exactsequence}. By the inductive hypothesis, $\phi_{d,n}$ and $\phi_{d+1,n}$ are isomorphisms. So, by the Five Lemma, $\phi_{d+1,n+1}$ is an isomorphism. Combining the above argument with Lemma \ref{lem:nminus3}, we conclude that for $2\le d\le (n+1)-3$, $\phi_{d,n+1}$ is an isomorphism. We also have the following diagram, which commutes by Lemma \ref{lem:alphabetacommutewithpushpull}:
\begin{center}
    \begin{tikzcd}
      &\Q\bSP_{0,n}\arrow[r,"\tilde{\pi}^*"]\arrow[d,"\tilde{\phi}_{0,n}"]&\cQ_{1,n+1}\arrow[r,"\pi_*"]\arrow[d,"\phi_{1,n+1}"]&\cQ_{1,n}\arrow[r]\arrow[d,"\phi_{1,n}",
      "\cong" swap]&0\\
      0\arrow[r]&\Q\bK^{0}_{n}\arrow[r,"\alpha"]&\Q\bK^{1}_{n+1}\arrow[r,"\beta"]&\Q\bK^{1}_{n}\arrow[r]&0
    \end{tikzcd}
  \end{center}
where the bottom row is exact and the top row is a complex, exact at $\cQ_{1,n}$. By Lemma \ref{lem:n3surjective}, $\tilde{\phi}_{0,n}$ is surjective, and by the inductive hypothesis, $\phi_{1,n}$ is an isomorphism. By Lemma \ref{lem:fourvariant}), $\phi_{1,n+1}$ is surjective. But by Lemma \ref{lem:dimensionsequal}, $\dim\cQ_{1,n+1}=\dim
\Q\bK^1_{n+1}$, so $\phi_{1,n+1}$ is an isomorphism.

\end{proof}

\subsection{Theorem \ref{thm:Main} and its proof}

\begin{thm}\label{thm:Main} For $n\ge4$ and $d$ such that $1\le d\le n-3$:
\begin{enumerate}[label=(\roman*)]
\item We have $\cK_n^d= \cV_{d,n}^{\perp}$.\label{it:KappaPerpExactly}
\item The pairing $\cQ_{d,n}\times\cK_{n}^d\to\Q$ is perfect. \label{it:KappaTypeIPairingPerfect}
\item The set $\{\kappa_{d}^T\thickspace|\thickspace\abs{T}\ge(d+3), \abs{T}\equiv (d+3)\mod 2\}$ is an $S_n$-equivariant basis for $\cK^{d}_{n}$. \label{it:KappaBasis}
\item The $S_n$ actions on $\cQ_{d,n}$ and $\cK^{d}_{n}$ are isomorphic to the permutation representation induced by the natural action of $S_n$ on the set $\{T\subseteq[n]\thickspace|\thickspace\abs{T}\ge(d+3), \abs{T}\equiv (d+3)\mod 2\}$.  \label{it:Representations}
\item The following (dual) sequences are exact:\label{it:Sequences}
    \begin{align}
      &0\to\cQ_{d,n}\xrightarrow{\pi^*}{}\cQ_{d+1,n+1}\xrightarrow{\pi_*}{}\cQ_{d+1,n}\to0\label{eq:seqQ}\\
       &0\to\cK^{d+1}_{n}\xrightarrow{\pi^*}{}\cK^{d+1}_{n+1}\xrightarrow{\pi_*}{}\cK^d_{n}\to0 \label{eq:seqK}
    \end{align}
\end{enumerate}
\end{thm}

\begin{proof}
Recall the map $\psi_{d,n}:\Q\bK^d_n\to\cK^d_n$ given in Definition \ref{Def:bKintocK}. We have compatible pairings $\cQ_{d,n}\times\cK_{n}^d\to\Q$ and $\cQ_{d,n}\times\Q\bK_{n}^d\to\Q$, inducing maps $\eta_{d,n}:\cQ_{d,n}\to(\cK_{n}^d)^{\vee}$ and $\phi_{d,n}:\cQ_{d,n}\to(\Q\bK_{n}^d)^{\vee}=\Q\bK_{n}^d$, where, $\phi_{d,n}$ is as in Definition \ref{def:phi}. These maps satisfy: $\phi_{d,n}=(\psi_{d,n})^{\vee}\circ\eta_{d,n}$. By Theorem \ref{thm:root}, $\phi_{d,n}$ is an isomorphism, which implies that $\eta_{d,n}$ is injective. On the other hand, we have by Corollary \ref{cor:kappaandQduals} that $\cK^d_n\subset\cV_{d,n}^{\perp}=(\cQ_{d,n})^{\vee}$, so $(\eta_{d,n})^{\vee}$ is injective as well. This implies that $\eta_{d,n}$ is an isomorphism, proving items \ref{it:KappaTypeIPairingPerfect} and \ref{it:KappaPerpExactly}. Since $\eta_{d,n}$ and $\phi_{d,n}$ are both isomorphisms, we conclude that so is $\psi_{d,n}$, proving item \ref{it:KappaBasis}, and thus also item \ref{it:Representations}. Finally, by Theorem \ref{thm:root} and Lemma \ref{lem:alphabetacommutewithpushpull}, the sequence in Equation \ref{eq:seqQ} is dual to the sequence in Equation \ref{eq:seqbK}, which is exact by Lemma \ref{lem:exactsequence}. We conclude that the sequence in Equation \ref{eq:seqQ} is exact. The sequence in Equation \ref{eq:seqQ} is dual to the sequence in Equation \ref{eq:seqK}, so the latter sequence is exact, proving item \ref{it:Sequences}
\end{proof}

\bibliographystyle{amsalpha}
\bibliography{../BigRefs}
\end{document}

config: arxiv


TITLE: Proving Two Complexes are Not Quasi-Isomorphic
QUESTION [8 upvotes]: In Richard Thomas' paper "Derived Categories for the Working Mathematician" he mentions (page 6) that the two complexes
$$
\begin{align*}
C^\bullet&= \mathbb{C}[x,y]^{\oplus 2}\xrightarrow{(x,y)}\mathbb{C}[x,y]\\
D^\bullet&= \mathbb{C}[x,y]\xrightarrow{0}\mathbb{C}
\end{align*}
$$
have the same cohomology but are not quasi-isomorphic. Proving that $C^\bullet$ and $D^\bullet$ have the same cohomology is straightforward, but I'm having trouble proving that they are not quasi-isomorphic. Any suggestions?
Thanks in advance!

REPLY [6 votes]: As was pointed out by Andrea in the comments to the other answer, the other answer does not answer the question properly.
An argument that the two complexes cannot be quasi-isomorphic in the general sense is sketched on page 2 of:
https://www.math.upenn.edu/~tpantev/rtg09bc/secnotes/ainfnity.davidovich.pdf


TITLE: If $R/I$ and $R/J$ are Noetherian (resp. Artinian), then so is $R/(I \cap J)$
QUESTION [0 upvotes]: Let $R$ be a commutative unitary ring and $I,J$ be two ideals of $R$. I need to prove that if $R/I$ and $R/J$ are Noetherian (resp. Artinian), then so is $R/(I \cap J)$
It seems that a direct approach won't lead anywhere, so I took the homomorphism $R \to R /I \times R/J$, $r \mapsto (r+I, r+J)$; it has a kernel $I \cap J$. So:
$$R/(I \cap J) \cong f(R)$$
Now the problem is that $f(R)$ is not an ideal of $R/I \times R/J$, though it is a subring (but I don't think that this is useful because I don't know any relevant theorems regarding subrings). I am stuck here.
Any hints or suggestions?

REPLY [1 votes]: Hint. Use some exact sequence, and note that $R/I$ is a noetherian ring iff it is a noetherian $R$-module.
Edit. Your approach is also good: the map $f:R\to R/I\times R/J$ defined by $f(r)=(r+I,r+J)$ is an $R$-module homomorphism, so $R/(I\cap J)$ is isomorphic to an $R$-submodule of $R/I\times R/J$. But a direct product (sum) of finitely many noetherian (artinian) $R$-modules is also noetherian (artinian), and an $R$-submodule of a noetherian (artinian) $R$-module is noetherian (artinian).


TITLE: Summation Value of Combination Function
QUESTION [1 upvotes]: $$\sum_{n=1}^{\infty}\frac{5^n}{n!2^n}$$
I know how to prove that the above series is convergent but I'm not sure how to get the value that it converges to. If it were just the geometric series, I could get an end value but the factorial in the bottom complicates matters. Thank you very much.
This is NOT a homework sum. I genuinely do not understand how to solve it.

REPLY [0 votes]: $\displaystyle \sum_{n=1}^\infty \dfrac{5^n}{n!\cdot 2^n}$ = $\displaystyle \sum_{n=1}^\infty \dfrac{(\frac{5}{2})^n}{n!}$ = $e^{\frac{5}{2}} - 1$


TITLE: What are the ways to solve cubic equations?
QUESTION [0 upvotes]: Cubic equations of the form $ax^3+bx^2+cx+d$ can be solved in various ways. Some are easy to easy to factor in a pair, for some the roots can be found out by trial-and-error, some are one-of-a-kind, some can be reduced to a quadratic equation. A compilation of all possible ways to solve cubic equations would be very helpful for students and learners.

REPLY [1 votes]: $ax^3+bx^2+cx+d=0$

Divide to a to get $x^3$ term 1

$$x^3+\frac{b}{a}x^2+\frac{c}{a} x+\frac{d}{a}=0$$
$$x^3+b_1 x^2+c_1 x+d_1=0$$

Eliminate $x^2$ term via using $x=z-\frac{b_1}{3}$ transform
Then you will get

$$(z-\frac{b_1}{3})^3+b_1(z-\frac{b_1}{3})^2+c_1(z-\frac{b_1}{3})+d_1=0$$
$$z^3+c_2 z+d_2=0$$

Use binom expansion
$$(p+y)^3=p^3+3p^2y+3py^2+y^3$$
Reorder the equation as:
$$(p+y)^3-3py(p+y)-(p^3+y^3)=0$$

Define:
$p+y=z$ Thus
$$3.p.y=-c_2$$
 $$p^3+y^3=-d_2$$
$$p=-\frac{c_2}{3y}$$
$$-(\frac{c_2}{3y})^3+y^3=-d_2$$
Then solve the quadratic equation with after $y^3=m$
$$-\frac{c^3_2}{27m}+m=-d_2$$
$$m^2+d_2.m-\frac{c^3_2}{27}=0$$

The qadratic equation can be solved  via  $m=s-\frac{d_2}{2}$

$$(s-\frac{d_2}{2})^2+d_2.(s-\frac{d_2}{2})-\frac{c^3_2}{27}=0$$
$$s^2=\frac{c^3_2}{27}+\frac{d^2_2}{2}=\Delta$$
Write $$s=\sqrt{\Delta}$$
$$m=\sqrt{\Delta}-\frac{d_2}{2}$$
 $$y^3=m$$
 $$y=\sqrt[3]{\sqrt{\Delta}-\frac{d_2}{2}}$$
$$p=-\frac{c_2}{3y}$$
  $$p=-\frac{c_2}{3\sqrt[3]{\sqrt{\Delta}-\frac{d_2}{2}}}$$
  $$p+y=z$$
  $$x=\sqrt[3]{\sqrt{\Delta}-\frac{d_2}{2}}-\frac{c_2}{3\sqrt[3]{\sqrt{\Delta}-\frac{d_2}{2}}}-\frac{b_1}{3}$$


TITLE: Bounded Linear "Change of Basis"
QUESTION [0 upvotes]: Let $E$ be a separable Banach space and $x,y \in E$.  Does there necessarily exist a bijective bounded linear operator $A\in B(E)$ such that
$$
Ax =y,
$$
such that $A^{-1}$ is also a bounded linear operator?  I know this to be true in finite dimensions and on the separable Hilbert space, but what about in general?

REPLY [0 votes]: If $x$ and $y$ are linearly dependent, then the problem is unsolvable (if exactly one of $x,y$ is zero) or trivial ($A$ is multiple of identity).
Assume that $x$ and $y$ are linearly independent. Define functionals $f,g\in X^*$ by
$f(x)=1$, $f(y)=0$, $g(x)=0$, $g(y)=1$, and extension by Hahn-Banach.
Define projection operator
$$
Pz:= f(z)x + g(z)y.
$$
Define
$$
Az := f(z)y + g(z)x + (I-P)(z)= z - (f(z)-g(z))(x-y).
$$
The idea of the construction is: exchange $x$ an $y$ on the span of both, on $\ker f\cap \ker g$ act as identity.
Then $Ax=y$ and $Ay=x$. In addition $A^2=I$:
We have
$$
f(Az) = f(z) -(f(z)-g(z))=g(z),
$$
$$
g(Az) = g(z) + (f(z)-g(z))=f(z).
$$
Then
$$
A^2(z) = Az + (f(z)-g(z))(x-y) = z.
$$
This implies that $A$ is bijective. Obviously, $A$ is bounded.


TITLE: Nonhomogenous variable coefficient
QUESTION [1 upvotes]: How would you solve this ODE:
$$(1 + x^{2})y’’ + 4xy’ + 2y = 1/(1+x^{2})$$
I have the answer for homogenous part of this ODE but do not know how to do this, variation of parameter is a mess at integral step when applying to this
Any help would be appreciated. Thank you very much :)

REPLY [0 votes]: Using variation of parameters is actually not that messy.
Dividing by $(1+x^2)$, we get
$$ y'' + \frac{4x}{x^2+1}y' + \frac{2}{x^2+1} y = \frac{1}{(x^2+1)^2} $$
which has inhomogeneity of $g(x) = \frac{1}{(x^2+1)^2}$. The solutions to the homogeneous equation are $$y_1 = \frac{1}{x^2+1} \ \text{ and } \ y_2 = \frac{x}{x^2+1}$$which we can use to compute the Wronskian, $W = \frac{1}{(x^2+1)^2} \neq 0$. Then, the particular solution is $u_1y_1+u_2y_2$ where $u_1 = -\int \frac{y_2g}{W}dx$ and $u_2 = \int \frac{y_1 g}{W} dx$. The plugging in what we have,
$$ u_1 = -\int \frac{x}{x^2+1}dx = -\frac{1}{2}\log(x^2+1) $$
$$ u_2 =  \int \frac{1}{x^2+1} = \tan^{-1}(x)$$
Thus, the solution is
$$ y(x) = \frac{c_1-\frac{1}{2}\log(x^2+1)+c_2x + \tan^{-1}(x)}{x^2+1} $$