# Simple closed curves, non-kernel homology and Magnus embedding

Adam Klukowski111University of Oxford<EMAIL_ADDRESS>
###### Abstract

We consider the subspace of the homology of a covering space spanned by lifts
of simple closed curves. Our main result is the existence of unbranched covers
where this is a proper subspace. More generally, we exhibit covers whose
homology is not generated by the non-kernel of any fixed solvable quotient of
the fundamental group. We explain how the existing approach by Malestein and
Putman for branched covers relates to Magnus algebra, which significantly
simplifies their proof. We then generalise it by producing embeddings of
surface groups into units of certain algebras, which may be of independent
interest.

##  1 Introduction

Consider a finite-degree cover $p:\widetilde{\Sigma}\rightarrow\Sigma_{g,n}$
of an orientable surface $\Sigma_{g,n}$ of genus $g$ with $n$ punctures. The
_simple closed curve homology_
$\textnormal{H}_{1}^{\text{scc}|\Sigma_{g,n}}(\widetilde{\Sigma};M)$ is
defined as the subspace of $\textnormal{H}_{1}(\widetilde{\Sigma};M)$ spanned
by elements of the form

$\left\\{[\widetilde{\gamma}]\in\textnormal{H}_{1}(\widetilde{\Sigma};M)\
\big{|}\ \widetilde{\gamma}\text{ is a component of }p^{-1}(\gamma)\text{ for
a simple closed curve }\gamma\text{ on }\Sigma_{g,n}\right\\}$ (1)

Our main theorem is:

Theorem 1.0.1: For any $g\geq 2$, $n\geq 0$, and odd prime $r$ there is a
cover $\widetilde{\Sigma}\rightarrow\Sigma_{g,n}$ whose degree is a power of
$r$ and such that
$\textnormal{H}_{1}^{\text{scc}}(\widetilde{\Sigma};\mathbb{Q})\neq\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Q})$.

The question whether $\textnormal{H}_{1}^{\text{scc}}=\textnormal{H}_{1}$ was
an open problem asked by Marché [10] and independently by Looijenga [7]. An
affirmative answer for abelian and 2-step nilpotent covers of graphs was given
by Farb and Hensel [2]. Koberda and Santharoubane [6] used TQFT methods to
find covers of surfaces with
$\textnormal{H}_{1}^{\text{scc}}(\widetilde{\Sigma};\mathbb{Z})\neq\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Z})$,
but their method could not rule out the possibility of
$\textnormal{H}_{1}^{\text{scc}}(\widetilde{\Sigma};\mathbb{Z})$ being finite-
index (equivalently it did not apply to rational instead of integer
coefficients). An example of an unbranched cover
$\Sigma_{648}\rightarrow\Sigma_{2}$ with
$\textnormal{H}_{1}^{\text{scc}|\Sigma_{2}}(\Sigma_{648};\mathbb{Q})\neq\textnormal{H}_{1}(\Sigma_{648};\mathbb{Q})$
was noted by Marković and Tošić [12] based on the work of Marković [11] and
Bogomolov and Tschinkel [1].

This article builds on the work of Malestein and Putman [9] and earlier ideas
of Farb and Hensel [2]. In [9] they constructed branched (equivalently
required $n\geq 1$) covers where
$\textnormal{H}_{1}^{\text{scc}}(\widetilde{\Sigma};\mathbb{Q})\neq\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Q})$.
Here we settle the general case and exhibit unbranched covers with
$\textnormal{H}_{1}^{\text{scc}}(\widetilde{\Sigma};\mathbb{Q})\neq\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Q})$
in all genera. We relate earlier approaches to the Magnus embedding [8]. We
then produce similar embeddings of surface groups, which may be of independent
interest.

###  1.1 Homologies of covers and subgroups

One can ask about the subspaces of homology of a covering space
$\widetilde{\Sigma}$ spanned by more general sets. Following [2], we define an
_elevation_ of $\gamma\in\pi_{1}\Sigma$ to be a minimal concatenation222I.e.
$\tilde{\gamma}$ is a lift of $\gamma^{k}$, where $k$ is the minimal positive
integer for which $\widetilde{\gamma}$ is a closed curve of lifts of $\gamma$
which forms a closed curve in $\widetilde{\Sigma}$. Given a set
$\mathcal{O}\subseteq\pi_{1}\Sigma$ of curves on $\Sigma$ we define
$\textnormal{H}_{1}^{\mathcal{O}|\Sigma}(\widetilde{\Sigma};M)$ to be the
subspace of $\textnormal{H}_{1}(\widetilde{\Sigma};M)$ spanned by

$\left\\{[\tilde{\gamma}]\ \big{|}\ \tilde{\gamma}\text{ is an elevation of a
curve }\gamma\in\mathcal{O}\right\\}$ (2)

We present an insufficiency result for a large class of subsets in theorem
1.1. For a quotient $\theta:\pi_{1}\Sigma\rightarrow Q$ write
$\textnormal{H}_{1}^{\theta\neq
1}(\widetilde{\Sigma};\mathbb{Q})=\textnormal{H}_{1}^{\pi_{1}\Sigma\setminus\ker\theta|\Sigma}(\widetilde{\Sigma};\mathbb{Q})$
to be the subspace spanned by elevations of curves which are nontrivial in
$Q$.

Theorem 1.1.2: Suppose $g\geq 2$, $n\geq 0$, and let
$\theta:\pi_{1}\Sigma_{g,n}\rightarrow Q$ be a nontrivial finite solvable
quotient of odd order. There exists a normal cover
$\widetilde{\Sigma}\rightarrow\Sigma_{g,n}$ such that
$\textnormal{H}_{1}^{\theta\neq
1}(\widetilde{\Sigma};\mathbb{Q})\neq\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Q})$.
Furthermore, we can require that all prime factors of the degree of this cover
divide $|Q|$.

Let us point out some consequences of 1.1, which appeared in various places in
existing literature.

Corollary 1.1.3: Let $g\geq 2$, $n\geq 0$. For each of the following sets
$\mathcal{O}$ of loops on $\Sigma_{g,n}$ there exists a normal cover
$\widetilde{\Sigma}\rightarrow\Sigma_{g,n}$ such that
$\textnormal{H}_{1}^{\mathcal{O}|\Sigma_{g,n}}(\widetilde{\Sigma};\mathbb{Q})$
is not the whole of $\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Q})$.
1\. Theorem 1: $\mathcal{O}$ consisting of simple closed curves.
2\. Primitive homology: $\mathcal{O}$ consisting of the elements which belong
to some minimal generating set of $\pi_{1}\Sigma_{g,n}$.
3\. More generally, any set $\mathcal{O}$ which is contained in the union of
finitely many $\text{Aut}(\pi_{1}\Sigma_{g,n})$-orbits.
4\. $d$-primitive homology $\textnormal{H}_{1}^{d-\text{prim}}$: $\mathcal{O}$
consisting of all loops which map to nonzero vectors in
$\textnormal{H}_{1}(\Sigma_{g,n};\tfrac{\mathbb{Z}}{d})$, for an odd square-
free $d>1$.

Primitive homology (2.) was introduced in [2]. Statements 3. and 4. are
respectively generalisations of theorems C and D from [9]. Both aforementioned
papers only considered free fundamental groups ($n\geq 1$), whereas we work
with free and surface groups.

Remark 1.1.4: In the statements 1., 2., 3., for any odd prime $r$ we can
additionally require the degree of the cover to be a power of $r$. In 4. we
can require the degree to divide a power of $d$.

Remark 1.1.5: It was asked by Kent [10] whether we can take $\mathcal{O}$ to
be the set of all curves which do not fill $\Sigma_{g,n}$. This question is
not answered by theorem 1.1: if $|Q|$ is a finite quotient of the fundamental
group and $\gamma$ a non-filling curve, then $\gamma^{|Q|}$ is non-filling and
trivial in $Q$.

Remark 1.1.6: When $n\geq 1$ we can remove the restriction of odd order of $G$
from theorem 1.1 – see remark 3.1. However, our proof still relies on
solvability (this is why we emphasise it, even though every finite group of
odd order is already solvable [4]).

Algebraic interpretation Let $R$ be a finite-index subgroup of
$\pi_{1}(\Sigma_{g,n})$ and $\mathcal{O}\subseteq\pi_{1}\Sigma_{g,n}$.
Algebraically the elevation of $\gamma$ is the333The way we set up the
definitions, algebraic elevation is unique whereas topological is not. This is
because passing to algebraic description we implicitly choose a preferred
basepoint of $\widetilde{\Sigma}$. element $\gamma^{m}$, where $m$ is the
minimal positive integer with $\gamma^{m}\in R$. Then
$\textnormal{H}_{1}^{\mathcal{O}}(R;M)$ is the subspace of
$\textnormal{H}_{1}(R;M)$ spanned by the set

$\left\\{[x^{m}]\in\textnormal{H}_{1}(\pi_{1}\Sigma_{g,n};M)\big{|}\
x\in\pi_{1}(\Sigma_{g,n})\text{ and }m\in\mathbb{Z}\text{ such that }x^{m}\in
R\right\\}$ (3)

When $R=\pi_{1}\widetilde{\Sigma}$ is the subgroup corresponding to the cover,
then naturally
$\textnormal{H}_{1}^{\mathcal{O}}(R;M)\cong\textnormal{H}_{1}^{\mathcal{O}}(\widetilde{\Sigma};M)$.

Remark 1.1.7: For the purpose of the results in this paper, boundary
components behave identically to punctures.

Other consequences for surface groups A couple of interesting statements about
free groups was noted by Malestein and Putman (theorems F and G in [9]) based
on an argument of [6]. Our theorem 1.1 allows to apply their argument to
surface groups, giving the following corollary.

Theorem 1.1.FG: Let $g\geq 2$, and $\theta:\pi_{1}\Sigma_{g}\rightarrow Q$ be
a finite solvable quotient of odd order. There exists an integral linear
representation $\rho:\pi_{1}\Sigma_{g}\rightarrow\text{GL}_{d}\mathbb{Z}$ with
infinite image such that every element of
$\rho(\pi_{1}\Sigma_{g}\setminus\ker\theta)$ has finite order.

The statement of 1.1 remains true if we can replace the complement of a kernel
with any of the special subsets from corollary 1.1.

Acknowledgements I wish to thank Vlad Marković, Misha Schmalian, Ognjen Tošić,
Dawid Kielak and Ric Wade for helpful suggestions and discussions. This work
was supported by the Simons Foundation.

###  1.2 Outline and organisation

Our approach consists of two steps.

${\begin{matrix}\text{thm \ref{thm:nonkernel_homology}, cor
\ref{cor:insufficiencies}}\\\
\textnormal{H}_{1}^{\text{scc}},\textnormal{H}_{1}^{\mathcal{O}},\textnormal{H}_{1}^{\theta\neq
1}\neq\textnormal{H}_{1}\end{matrix}}$${\begin{matrix}\text{cor
\ref{cor:insufficiencies}.4}\\\
\textnormal{H}_{1}^{d-\text{prim}}\neq\textnormal{H}_{1}\end{matrix}}$${\begin{matrix}\text{sec
\ref{sec:pf_special_pgroup}}\\\ \text{prop \ref{prop:special_pgroup}}\\\
(G,C,\rho,\alpha,\Psi)\end{matrix}}$sec 2.2sec 2.3

The first step, described in section 2, is to construct covers whose homology
can see the interesting curves. In section 2.2 we deduce theorem 1 on simple
closed curve homology from theorem 1.1, and reduce theorem 1.1 to its special
case – part 4 of corollary 1.1 on $d$-primitive homology.

Section 2.3 serves as a bridge between the first and second step. Here we
reduce the corollary 1.1.4 on $d$-primitive homology to a group-theoretic 2.3.
The idea is to view the homology of a cover as a representation of the deck,
and find a representation of the deck group with certain special properties.

The second step – construction of a special quotient of the fundamental group
and proof of proposition 2.3 – is done in section 3. We start with the case of
punctured surfaces in section 3.1, and translate Malestein’s and Putman’s
proof into the language of Magnus embedding, which leads to significant
simplifications. In section 3.2 we carry out an analogous construction for
surface groups.

##  2 Relationships between homologies of covers

The aim of this section is to relate various flavours of cover homology, and
eventually reduce the insuficiency of $\textnormal{H}_{1}^{\text{scc}}$,
$\textnormal{H}_{1}^{\mathcal{O}}$ and $\textnormal{H}_{1}^{\theta\neq 1}$ to
the insufficiency of $\textnormal{H}_{1}^{d-\text{prim}}$. Our approach is,
given a set $\mathcal{O}$ of curves on $\Sigma$, to find a cover
$\widehat{\Sigma}\rightarrow\Sigma$ with a nicer set $\widehat{\mathcal{O}}$
(of curves on $\widehat{\Sigma}$) such that all further covers
$\widetilde{\Sigma}\rightarrow\widehat{\Sigma}$ satisfy

$\textnormal{H}_{1}^{\mathcal{O}|\Sigma}\left(\widetilde{\Sigma};\mathbb{Q}\right)\
\subseteq\
\textnormal{H}_{1}^{\widehat{\mathcal{O}}|\widehat{\Sigma}}\left(\widetilde{\Sigma};\mathbb{Q}\right).$
(4)

Then insufficiency of $\widehat{\mathcal{O}}$-homology implies the
insufficiency of $\mathcal{O}$-homology.

###  2.1 Stability of curve characteristics under taking covers

Let us note that each of the interesting properties is stable with respect to
taking covers. These facts will be used in section 2.2 to reduce the general
theorem 1.1 to the special case of $d$-primitive homology.

Lemma 2.1.8: Let $p:\widetilde{\Sigma}\rightarrow\Sigma$ be a finite-degree
cover, $\gamma$ a curve on $\Sigma$, and $\tilde{\gamma}$ its elevation to
$\widetilde{\Sigma}$. Then:
1\. If $\gamma$ is simple, then so is $\tilde{\gamma}$.
2\. If $\gamma$ is simple and nonseparating, then so is $\tilde{\gamma}$.
3\. If $\gamma$ does not fill $\Sigma$ then $\tilde{\gamma}$ does not fill
$\widetilde{\Sigma}$.
4\. If $[\gamma]\neq 0$ in $\textnormal{H}_{1}(\Sigma;\mathbb{Z})$ then also
$[\tilde{\gamma}]\neq 0$ in
$\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Z})$.
5\. If the cover is normal and $[\gamma]\neq 0$ in
$\textnormal{H}_{1}(\Sigma;\mathbb{F}_{r})$, then also $[\tilde{\gamma}]\neq
0$ in $\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{F}_{r})$.

Proof: 1\. A transverse self-intersection of $\tilde{\gamma}$ would map to a
transverse self-intersection of $\gamma$ under $p$.

2\. Take $\delta\in\pi_{1}\Sigma$ that intersects $\gamma$ once. Then a
concatenation of some lifts of $\delta$ is a path which joins the opposite
sides of $\tilde{\gamma}$. Therefore the complement of $\tilde{\gamma}$ is
connected.

3\. Let $X$ be a component of $\Sigma\setminus\gamma$ which is not a
topological disk. Its preimage $p^{-1}(X)$ is a component of
$\widetilde{\Sigma}\setminus p^{-1}(\gamma)$ which is not homeomorphic to a
disk, so $p^{-1}(\gamma)$ does not fill $\widetilde{\Sigma}$. Since
$\tilde{\gamma}$ is a subset of $p^{-1}(\gamma)$, it does not fill
$\widetilde{\Sigma}$ either.

4\. The image of $[\tilde{\gamma}]$ under $p_{*}$ is a positive multiple of
$[\gamma]$ and thus nonzero.

5\. First, suppose $\tilde{\gamma}$ maps onto $\gamma$ with degree $d$ coprime
to $r$. Then $p_{*}([\tilde{\gamma}])=d[\gamma]\neq 0$ in
$\textnormal{H}_{1}(\Sigma;\mathbb{F}_{r})$, so $[\tilde{\gamma}]\neq 0$ in
$\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{F}_{r})$.

Second, consider the case where the deck group
$\text{Aut}(\nicefrac{{\widetilde{\Sigma}}}{{\Sigma}})\cong\tfrac{\mathbb{Z}}{r}$
is cyclic of order $r$ and generated by $\gamma$. A part of the five-term
exact sequence is

${0=\textnormal{H}_{2}(\tfrac{\mathbb{Z}}{r};\mathbb{Z})}$${\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Z})_{\text{Aut}(\nicefrac{{\widetilde{\Sigma}}}{{\Sigma}})}}$${\textnormal{H}_{1}(\Sigma;\mathbb{Z})}$${\textnormal{H}_{1}(\tfrac{\mathbb{Z}}{r};\mathbb{Z})=\tfrac{\mathbb{Z}}{r}}$${0}$$\scriptstyle{p_{*}}$
(5)

Therefore there exist bases in which $p_{*}$ becomes the standard inclusion

$\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Z})_{\text{Aut}(\nicefrac{{\widetilde{\Sigma}}}{{\Sigma}})}\cong
r\mathbb{Z}\oplus\mathbb{Z}^{m-1}\hookrightarrow\mathbb{Z}^{m}\cong\textnormal{H}_{1}(\Sigma;\mathbb{Z})$
(6)

Let $\pi:\textnormal{H}_{1}(\Sigma;\mathbb{Z})\rightarrow\mathbb{Z}$ be the
projection onto the first factor. $\gamma$ generates the deck group, so
$\pi(\gamma)\in\mathbb{Z}\setminus r\mathbb{Z}$, and $\pi\circ
p(\tilde{\gamma})=\pi(\gamma^{r})\in r\mathbb{Z}\setminus r^{2}\mathbb{Z}$.
Then $r^{-1}\cdot\pi\circ p_{*}$ is a $\mathbb{Z}$-module homomophism
$\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Z})\rightarrow\mathbb{Z}$ which
sends $[\widetilde{\gamma}]$ to $\mathbb{Z}\setminus r\mathbb{Z}$, so
$[\widetilde{\gamma}]\neq 0$ in
$\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{F}_{r})$.

Third, let $\nicefrac{{\widetilde{\Sigma}}}{{\Sigma}}$ be a general cyclic
cover. It can be realised as a tower of cyclic covers of prime degree. We have
exhausted the possibilities for these, so by induction $[\gamma]\neq
0\Rightarrow[\tilde{\gamma}]\neq 0$.

Finally consider a general normal cover
$p:\widetilde{\Sigma}\rightarrow\Sigma$. Define the space
$\widehat{\Sigma}=\nicefrac{{\widetilde{\Sigma}}}{{\langle\gamma\rangle_{\text{Aut}(\nicefrac{{\widetilde{\Sigma}}}{{\Sigma}})}}}$.
It fits in the sequence

${\widetilde{\Sigma}}$${\widehat{\Sigma}}$${\Sigma}$${\tilde{\gamma}}$${\hat{\gamma}^{m}\quad\hat{\gamma}}$${\gamma}$$\scriptstyle{\tilde{p}}$$\scriptstyle{p}$$\scriptstyle{\hat{p}}$
(7)

of covering maps, where $\hat{\gamma}$ is the lift of $\gamma$ to
$\widehat{\Sigma}$ and $m$ is the order of $\gamma$ in
$\text{Aut}(\nicefrac{{\widetilde{\Sigma}}}{{\Sigma}})$. $\hat{p}$ maps
$\hat{\gamma}$ onto $\gamma$ with degree 1, so $[\hat{\gamma}]\neq 0$ in
$\textnormal{H}_{1}(\widehat{\Sigma};\mathbb{F}_{r})$.
$\tilde{p}:\widetilde{\Sigma}\rightarrow\widehat{\Sigma}$ is a cyclic cover
and $\tilde{\gamma}$ is an elevation of $\hat{\gamma}$, so
$[\tilde{\gamma}]\neq 0$ in
$\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{F}_{r})$. $\square$

###  2.2 Reduction to $d$-primitive homology

Here we reduce theorem 1.1 and corollaries 1.1 to the statement 4. of
corollary 1.1 – insufficiency of $d$-primitive homology.

Proof of corollaries 1.1, assuming theorem 1.1

3\. (orbits) $\Rightarrow$ 1\. (scc): $\text{Mcg}(\Sigma_{g,n})$ acts
transitively on non-separating simple closed curves, and there are finitely
many orbits of separating simple closed curves, parameterised by genus and
partition of punctures (see chapter 1.3 in [3]). $\text{Mcg}(\Sigma_{g,n})$
acts on $\pi_{1}\Sigma_{g,n}$ by automorphisms, so the set of simple closed
curves is contained in a union of finitely many
$\text{Aut}(\pi_{1}\Sigma_{g,n})$-orbits.

3\. (orbits) $\Rightarrow$ 2\. (primitive): $\text{Aut}(\pi_{1}\Sigma_{g,n})$
acts transitively on primitive elements.

Thm 1.1 $\Rightarrow$ 3\. (orbits): Let $r$ be a prime number. Both free and
surface groups are residually $r$-groups, so there exists a finite $r$-group
quotient $\theta:\pi_{1}\Sigma_{g,n}\rightarrow Q$ whose kernel is disjoint
from $\mathcal{O}$. Then
$\textnormal{H}_{1}^{\mathcal{O}}(\widetilde{\Sigma};\mathbb{Q})\subseteq\textnormal{H}_{1}^{\theta\neq
1}(\widetilde{\Sigma};\mathbb{Q})$ for any cover
$\widetilde{\Sigma}\rightarrow\Sigma_{g,n}$. Also, $Q$ is an $r$-group and
hence solvable. $\square$

Clearly, corollary 1.1.4 about $d$-primitive homology is just a special case
of theorem 1.1, when the quotient $Q$ is
$\textnormal{H}_{1}(\Sigma;\tfrac{\mathbb{Z}}{d})$. Below we reduce the
general to the special case.

Proof of theorem 1.1 assuming corollary 1.1.4 Let $\widehat{\Sigma}$ be the
cover corresponding to $\ker\theta$. Denote the derived series of $Q$ as

$Q=Q^{(0)}\triangleright Q^{(1)}\triangleright\dots\triangleright
Q^{(s)}=\\{1\\}$ (8)

By refining if necessary, we can assume that $\tfrac{Q^{(i)}}{Q^{(i+1)}}$ is
abelian of square-free order. Let $\Sigma^{(i)}$ be the cover corresponding to
$\theta^{-1}(Q^{(i)})$. This gives a tower of abelian covers

$\widehat{\Sigma}=\Sigma^{(s)}\rightarrow\Sigma^{(s-1)}\rightarrow\dots\rightarrow\Sigma^{(0)}=\Sigma_{g,n}$
(9)

Consider an elevation $\hat{\gamma}$ of
$\gamma\in\pi_{1}\Sigma_{g,n}\setminus\ker\theta$ to $\widehat{\gamma}$. If
$\hat{\gamma}$ maps onto $\gamma$ with degree 1, then
$\pi_{1}\widehat{\Sigma}$ contains a conjugate of $\gamma$, which is
impossible. Let $i$ be the largest index for which $\hat{\gamma}$ maps onto
its image $\gamma^{(i)}$ in $\Sigma^{(i)}$ with degree greater than 1. This
means that $\theta(\gamma^{(i)})\in Q^{(i)}\setminus Q^{(i+1)}$, so its image
in $\tfrac{Q^{(i)}}{Q^{(i+1)}}$ is non-trivial, so $[\gamma^{(i)}]\neq 0$ in
$\textnormal{H}_{1}(\Sigma^{(i)};\mathbb{F}_{p})$ for some $p$ dividing $|Q|$.
But $\hat{\gamma}$ is an elevation of $\gamma^{(i)}$, so by “stability of
$r$-nontriviality” – part 5 of lemma 2.1 – we know that $[\hat{\gamma}]\neq 0$
in $\textnormal{H}_{1}(\widehat{\Sigma};\mathbb{F}_{p})$.

We have proved that any elevation of any curve in
$\pi_{1}\Sigma_{g,n}\setminus\ker\theta$ to $\widehat{\Sigma}$ is non-trivial
in $\textnormal{H}_{1}(\widehat{\Sigma};\tfrac{\mathbb{Z}}{d})$, where $d$ is
the radical of $|Q|$. Therefore, for any further cover
$\widetilde{\Sigma}\rightarrow\widehat{\Sigma}$ we have

$\textnormal{H}_{1}^{\theta\neq
1|\Sigma_{g,n}}(\widetilde{\Sigma};\mathbb{Q})\subseteq\textnormal{H}_{1}^{d-\text{prim}|\widehat{\Sigma}}(\widetilde{\Sigma};\mathbb{Q})$
(10)

so a witness to insufficiency of $d$-primitive homology relative to
$\widehat{\Sigma}$ (part 4 of corollary 1.1) is also a witness to theorem 1.1
for $\Sigma_{g,n}$. $\square$

###  2.3 Insufficiency of $d$-primitive homology

Here we prove part 4. of corollary 1.1. We assume the key proposition 2.3
below, whose proof of is deferred to section 3.

Proposition 2.3.9: Suppose $F$ is a free or surface group, and let $n$ be the
rank of $F$. For any odd prime $r$ and large enough $k\in\mathbb{N}$, there
exists a finite $r$-group $G$, a central subgroup $C\leq G$, and group
homomorphisms $\rho:F\rightarrow G$, $\alpha:G\rightarrow\mathbb{F}_{r}^{n}$,
and $\Psi:C\rightarrow\mathbb{F}_{r}$ such that
$\bullet$ The composition $\alpha\circ\rho$ is precisely the mod-$r$
abelianisation
$F\twoheadrightarrow\mathbb{F}_{r}^{n}=\textnormal{H}_{1}(F;\mathbb{F}_{r})$.
$\bullet$ If $g\in G\setminus\ker\alpha$, then $g^{r^{k}}$ lies in
$C\setminus\ker\Psi$.

We will use the following two lemmas to relate the homology of a cover to the
representation theory of the deck group. The first one is a classical result
of Gaschütz [5].

Lemma 2.3.10a: Let $R\triangleleft F_{n}$, $G=\tfrac{F_{n}}{R}$, and $k$ be a
field of characteristic 0. Then $\textnormal{H}_{1}(R;k)\cong k\oplus
k[G]^{n-1}$ as a $G$-module.

The situation with surface groups is not very different.

Lemma 2.3.10b: Let $R\triangleleft\pi_{1}\Sigma_{g}$,
$G=\tfrac{\pi_{1}\Sigma_{g}}{R}$, and $k$ be a field of characteristic 0. Then
$\textnormal{H}_{1}(R;k)\cong k^{2}\oplus\left(k[G]\right)^{2g-2}$ as a
$G$-module.

Proof: Let $F=\pi_{1}(\Sigma_{g})$ be a surface group. Take the standard cell
complex for $\Sigma_{g}$ and let $\Sigma_{R}$ be the corresponding cover. The
chain complex $C_{\bullet}(\Sigma_{R})\otimes k$ is

${k[G]}$${k[G]^{2g}}$${k[G]}$$\scriptstyle{\partial_{2}}$$\scriptstyle{\partial_{1}}$
(11)

Write $I=\\{x\in k[G]|\sum_{g\in G}x_{g}=0\\}$ for the augmentation ideal.

A 2-chain is sent to 0 precisely when any 2-cells have the same coefficients,
so $\ker\partial_{2}\cong k$ and $\text{im}\ \partial_{2}\cong I$. By
semisimplicity $C_{1}(\Sigma_{R})\otimes k=U\oplus k\oplus k[G]^{2g-1}$, where
$U\cong I$ and $\text{im}\ \partial_{2}=U\oplus 0\oplus 0$.

We have $\text{im}\ \partial_{1}=I$. Again by semisimplicity
$C_{1}(\Sigma_{R})\otimes k=V\oplus k\oplus k[G]^{2g-1}$ for some $V\cong I$
such in this decomposition $\partial_{1}$ is the projection onto $V$.

Since $\partial_{1}\circ\partial_{2}=0$, the subspaces $U,V$ intersect
trivially. Hence $C_{1}(\Sigma_{R})\otimes k=U\oplus V\oplus k^{2}\oplus
k[G]^{2g-2}$, so $H_{1}(\Sigma_{R};k)=k^{2}\oplus k[G]^{2g-2}$. $\square$

We are now ready to prove the insufficiency of $d$-primitive homology.

Proof of corollary 1.1 part 4, conditional on proposition 2.3:

First a technicality: we promote “prime $r$” to “square-free $d$” in
proposition 2.3. To this end, pick large $k\in\mathbb{N}$, factorise
$d=\prod_{i}r_{i}$, and for $i$-th prime factor $r_{i}$ take
$(G_{i},C_{i},\rho_{i},\alpha_{i},\Psi_{i})$ provided by proposition 2.3. Then
define $G=\prod_{i}G_{i}$, $C=\prod_{i}C_{i}\leq Z(G)$, and
$\rho=\prod_{i}\rho_{i}:\pi_{1}\Sigma_{g,n}\rightarrow G$. By ChRT there exist
$q_{i}\equiv\delta_{ij}\ (\\!\\!\\!\\!\mod r_{j}^{k+1})$. Set
$\alpha=\sum_{i}q_{i}\cdot\alpha_{i}:G\rightarrow\textnormal{H}_{1}(\Sigma_{g,n};\tfrac{\mathbb{Z}}{d})$
and $\Psi=\sum_{i}q_{i}\cdot\Psi_{i}:C\rightarrow\tfrac{\mathbb{Z}}{d}$. It is
straightforward to check these are well-defined and satisfy
$\bullet$ Composition $\alpha\circ\rho$ is the standard map
$F\rightarrow\textnormal{H}_{1}(\Sigma_{g,n};\tfrac{\mathbb{Z}}{d})$
$\bullet$ For any $g\in G\setminus\ker\alpha$ we have $g^{e}\in
C\setminus\ker\Psi$, where $e=\sum_{i}q_{i}r_{i}^{k}$.

Having the structure $(G,C,\rho,\alpha,\Psi)$ with the properties above, we
proceed to produce a nontrivial irreducible rational representation $V$ of $G$
such that elements of $G\setminus\ker\alpha$ have no nonzero fixed vectors.
Let $\omega$ be a primitive $d$-th root of unity and let
$W=\mathbb{Q}[\omega]$ be the cyclotomic field. We make $W$ into a
representation of $C$ by letting $c\in C$ act by $\omega^{\Psi(c)}$, and
induce to $V^{\prime}=\text{Ind}^{G}_{C}W$.

Suppose that $g\in G\setminus\ker\alpha$ fixes some $v\in V^{\prime}$. By the
properties of $G$, $g$ has a power $c\in C\setminus\ker\Psi$, which must also
fix $v$. Choosing a set of coset representatives $\Lambda$ for $C$ in $G$
allows us to describe the induced representation explicitly as
$V^{\prime}=\bigoplus_{\lambda\in\Lambda}\lambda\cdot W$. Using this
description we can write $v=\sum_{\lambda\in\Lambda}\lambda\cdot v_{\lambda}$.
Since $c$ is central, we have

$v=c\cdot v=\sum_{\lambda\in\Lambda}\lambda\cdot(c\cdot
v_{\lambda})=\sum_{\lambda\in\Lambda}\lambda\cdot\omega^{\Psi(c)}v_{\lambda}=\omega^{\Psi(c)}v$
(12)

But $\Psi(c)\not\equiv 0\ (\\!\\!\\!\\!\mod d)$, so $v$ must be the zero
vector. Thus we can take $V$ to be any irreducible factor of $V^{\prime}$.

Now we have at our disposal a nontrivial irrep $V$ of $G$ such that any $g\in
G\setminus\ker\alpha$ fixes only 0. Set $R=\ker\rho$. By lemmas 2.3 and 2.3,
$\textnormal{H}_{1}(R;\mathbb{Q})$ contains $\mathbb{Q}[G]$ as a direct
summand, and hence it contains $V$ too. Take any $d$-primitive $x$, and
observe that this means $\rho(x)\in G\setminus\ker\alpha$. Suppose $x^{m}\in
R$. The vector $[x^{m}]\in\textnormal{H}_{1}(R;\mathbb{Q})$ is fixed by
$\rho(x)$, so its projection onto $V$ must be 0. But this holds for any
generator of $d$-primitive homology, so
$\textnormal{H}_{1}^{d-\text{prim}}(R;\mathbb{Q})\cap V=\\{0\\}$, which
implies that
$\textnormal{H}_{1}^{d-\text{prim}}(R;\mathbb{Q})\neq\textnormal{H}_{1}(R;\mathbb{Q})$.
$\square$

##  3 Proof of proposition 2.3

In this section we prove proposition 2.3. We split it into two cases: free
fundamental group ($n\geq 1$) in proposition 3.1, and surface groups ($n=0$)
in proposition 3.2. The latter case follows a similar basic idea, but requires
some modifications to preserve the relation in surface groups.

We will need a preliminary lemma

Lemma 3.0.11: For any $n\geq 1$, prime $r$, and $k$ such that
$r^{k}>(n-1)(r-1)$, there exists a homogeneous polynomial
$P\in\mathbb{F}_{r}[a_{1},\dots,a_{n}]$ of degree $r^{k}$ which is nonzero on
$\mathbb{F}_{r}^{n}\setminus\\{0\\}$.

Proof: Let

$P_{1}(a_{1},a_{2})=a_{1}-a_{1}a_{2}^{r-1}+a_{2}$ (13)

The value of $P_{1}(a_{1},a_{2})$ is equal to $a_{2}$ when $a_{2}\neq 0$ and
$a_{1}$ otherwise. In either case $P_{1}\neq 0$ if any of its arguments is
nonzero.

We then inductively define

$P_{i}(a_{1},\dots,a_{i+1})=P_{1}\left(P_{i-1}(a_{1},\dots,a_{i}),a_{i+1}\right)$
(14)

The polynomial $P_{n-1}$ is nonzero on $\mathbb{F}_{r}^{n}\setminus\\{0\\}$,
has total degree $(n-1)(r-1)+1$ and its every monomial has degree congruent to
1 modulo $r-1$.

Consider a monomial $m$ of $P_{n-1}$ of degree $e$, and suppose the variable
$a_{i}$ appears with nonzero exponent. Then the monomial
$m^{\prime}=a_{i}^{r^{k}-e}m$ takes the same value as $m$ everywhere on
$\mathbb{F}_{r}^{n}$, and is of degree $r^{k}$. Replacing every monomial $m$
of $P_{n-1}$ with such $m^{\prime}$ gives a polynomial which fulfils the
premises of lemma 3. $\square$

###  3.1 Free groups

Recall

Proposition 3.1.9a: For $n\in\mathbb{N}_{+}$, prime $r$, and sufficiently
large $k$, there exists a finite $r$-group $G$, central subgroup $C\leq G$,
group homomorphisms $\rho:F_{n}\rightarrow G$,
$\alpha:G\rightarrow\mathbb{F}_{r}^{n}$, and $\Psi:C\rightarrow\mathbb{F}_{r}$
such that
$\bullet$ The composition $\alpha\circ\rho$ is the mod-$r$ abelianisation
$F_{n}\twoheadrightarrow\mathbb{F}_{r}^{n}=\textnormal{H}_{1}(F_{n};\mathbb{F}_{r})$.
$\bullet$ If $g\in G\setminus\ker\alpha$, then $g^{r^{k}}\in
C\setminus\ker\Psi$.

Proof: Let

$\mathcal{F}=\frac{\mathbb{F}_{r}\langle
X_{1},\dots,X_{n}\rangle}{(X_{1},\dots,X_{n})^{r^{k}+1}}$ (15)

be the free associative $\mathbb{F}_{r}$-algebra on $\\{X_{i}\\}_{1\leq i\leq
n}$ truncated at the degree $r^{k}$. That is, $\mathcal{F}$ consists of
polynomials with coefficients $\mathbb{F}_{r}$ in non-commuting variables
$X_{1},\dots,X_{n}$ of degree at most $r^{k}$.

Inside $\mathcal{F}$ lives the set of polynomials with trailing term one

$G_{\mathcal{F}}=1+(X_{1},\dots,X_{n})=\\{P\in\mathcal{F}|P(0,\dots,0)=1\\}=\\{1+(\text{degree}\geq
1)\\}$ (16)

This is a group under multiplication. The only non-trivial thing to check is
the existence of inverses, which can be found by

$(1+A)^{-1}=1+\sum_{e=1}^{r^{k}}(-1)^{e}A^{e}$ (17)

We define $\rho$ as sending $i$-th generator of $F_{n}$ to $1+X_{i}\in
G_{\mathcal{F}}$. The group $G_{\mathcal{F}}$ surjects onto
$\mathbb{F}_{r}^{n}$ via forgetting degree two and higher

$\alpha:1+a_{1}X_{1}+\dots+a_{n}X_{n}+(\deg\geq
2)\mapsto\begin{pmatrix}a_{1}\\\ \vdots\\\ a_{n}\end{pmatrix}$ (18)

These maps are compatible, in the sense that $\alpha\circ\rho$ is the mod-$r$
abelianisation $F_{n}\rightarrow\textnormal{H}_{1}(F_{n};\mathbb{F}_{r})$.

Inside $\mathcal{F}$ we also have

$C_{\mathcal{F}}=1+(X_{1},\dots,X_{n})^{r^{k}}=\left\\{1+(\text{terms of
degree }r^{k})\right\\}$ (19)

All terms of degree at least $r^{k}+1$ vanish in $\mathcal{F}$, so
$C_{\mathcal{F}}$ is central in $\mathcal{F}$ as a subalgebra, so it is
central in $G_{\mathcal{F}}$ as a subgroup. As a group it is isomorphic to
$\mathbb{F}_{r}$-vector space spanned by monomials of degree $r^{k}$ with
addition.

Raising to $r^{k}$-th power in $\mathcal{F}$ does

$\left(1+\sum_{i=1}^{n}a_{i}X_{i}+(\deg\geq
2)\right)^{r^{k}}=1+\sum_{i_{1},\dots,i_{p^{k}}}\prod_{j=1}^{n}a_{j}^{\text{\\#
of occurences of }j\text{ among i's}}\cdot\prod_{l=1}^{r^{k}}X_{i_{l}}$ (20)

Since the terms $\prod_{l=1}^{r^{k}}X_{i_{l}}$ are a basis for
$C_{\mathcal{F}}$, we can read off the coefficients in 20 using group
homomorphisms $C\rightarrow\mathbb{F}_{r}$. Formally, the group
$G_{\mathcal{F}}$ has the property

Property 3.1.12a: For any degree $r^{k}$ homogeneous polynomial
$P\in\mathbb{F}_{r}[a_{1},\dots,a_{n}]$ we can find a group homomorphism
$\Psi_{P}:C_{\mathcal{F}}\rightarrow\mathbb{F}_{r}$, such that for $g\in
G_{\mathcal{F}}$ we have $g^{r^{k}}\in C_{\mathcal{F}}$ and
$\Psi_{P}\big{(}g^{r^{k}}\big{)}=P\big{(}\alpha(g)\big{)}$.

Suppose $k$ satisfies $r^{k}>(n-1)(r-1)$. By lemma 3, there is a homogeneous
polynomial $P\in\mathbb{F}_{r}[a_{1},\dots,a_{n}]$ of degree $r^{k}$ which
does not vanish on $\mathbb{F}_{r}^{n}\setminus\\{0\\}$. Let $\Psi_{P}$ be the
homomorphism corresponding to $P$ provided by property 3.1. Then
$(G_{\mathcal{F}},C_{\mathcal{F}},\rho,\alpha,\Psi_{P})$ fulfills the
requirements of proposition 3.1. $\square$

Remark 3.1.13: This proof still works when $r=2$.

Remark 3.1.14: We can make the group $G_{\mathcal{F}}$ smaller by adding
relations $\\{X_{i}X_{j}=0\\}_{i>j}$ to $\mathcal{F}$.

###  3.2 Surface groups

Here we prove the surface case of proposition 2.3.

Proposition 3.2.9b: For any $g\geq 2$, odd prime $r$ and sufficiently large
$k$, there exists a finite $r$-group $G$, a central subgroup $C\leq G$, group
homomorphisms $\rho:\pi_{1}(\Sigma_{g})\rightarrow G$,
$\alpha:G\rightarrow\mathbb{F}_{r}^{2g}$, and
$\Psi:C\rightarrow\mathbb{F}_{r}$ such that
$\bullet$ Composition $\alpha\circ\rho$ is the mod-$r$ abelianisation
$\pi_{1}(\Sigma_{g})\twoheadrightarrow\mathbb{F}_{r}^{2g}=\textnormal{H}_{1}(\Sigma_{g};\mathbb{F}_{r})$.
$\bullet$ If $g\in G\setminus\ker\alpha$, then $g^{r^{k}}\in
C\setminus\ker\Psi$.

Our proof strategy will be to mimic the construction from the proof of
proposition 3.1. In subsections 3.2.2 and 3.2.3 we construct two types of
algebras, whose groups of units admit a homomorphism from a surface group
“with appropriate linear terms”. Both algebras come with data analogous to
$(G,C,\rho,\alpha,\Psi)$ from the free case 3.1. We assemble these objects and
finalise the proof in subsection 3.2.4. See 37 for a diagram of the whole
construction.

####  3.2.1 Notation and preliminary observations

Fix the presentation $\pi_{1}\Sigma_{g}=\left\langle
x_{1},y_{1},\dots,x_{g},y_{g}\big{|}\prod_{i=1}^{g}x_{i}y_{i}x_{i}^{-1}y_{i}^{-1}\right\rangle$.
Then $\textnormal{H}_{1}(\pi_{1}(\Sigma_{g});k)$ is isomorphic to $k^{2g}$
with basis $\\{x_{i},y_{i}\\}_{1\leq i\leq g}$. Let us begin with a more
careful analysis of the polynomial in variables $\\{x_{i},y_{i}\\}_{1\leq
i\leq g}$ which does not vanish on $\mathbb{F}_{r}^{2g}\setminus\\{0\\}$.

Observation 3.2.15: The polynomial provided by lemma 3 has only three types of
monomials:
$\bullet$ type I: powers of single variables $a_{j}^{v}$ with $v\equiv
1\mod(r-1)$
$\bullet$ type II: products of powers of at least three different variables
$\bullet$ type III: monomials of the form
$a_{j}^{v}a_{j^{\prime}}^{v^{\prime}}$ with $v\equiv 1,v^{\prime}\equiv
0\mod(r-1)$

Proof: Initial $P_{1}$ in equation 13 contains only monomials of type I and
III. Inductive equation 14 can copy existing monomials, produce new monomials
of type II or III from old monomials, and add a monomial of type I. The final
homogenisation step preserves every exponent modulo $r-1$. $\square$

Subdivide type III monomials into type IIIa if they involve $x_{i},x_{j}$ or
$y_{i},y_{j}$ or $x_{i},y_{j}$ with $i\neq j$, and type IIIb if they are of
the form $x_{i}^{u}y_{i}^{v}$.

####  3.2.2 Algebra $\mathcal{M}$ and type I, II and IIIa terms

In this section we demonstrate the algebra $\mathcal{M}$ which admits an
interesting mapping $\pi_{1}\Sigma_{g}\rightarrow G_{\mathcal{M}}$. It will
build the upper row of the diagram 37, where it will provide type I, II and
IIIa terms of a non-vanishing polynomial.

Define

$\mathcal{M}=\frac{\mathbb{F}_{p}\langle
X_{1},Y_{1},\dots,X_{g},Y_{g}\rangle}{(X_{i},Y_{i})^{r^{k}+1}+(X_{i}Y_{i},Y_{i}X_{i})}$
(21)

that is, a free associative algebra on $X_{i},Y_{i}$ where we ignore all terms
of total degree greater than $r^{k}$, and also those with adjacent
$X_{i},Y_{i}$. Note we still keep $X_{i}Y_{j}$ for $i\neq j$.

We define $G_{\mathcal{M}}$, $\alpha_{\mathcal{M}}$, $C_{\mathcal{M}}$
analogously as earlier in equations 16, 18 and 19.

The symbols $X_{i},Y_{i}$ commute in the algebra $\mathcal{M}$, so
$1+X_{i},1+Y_{i}$ commute in the group $G_{\mathcal{M}}$. Therefore we have a
well-defined group homomorphism
$\rho_{\mathcal{M}}:\pi_{1}\Sigma_{g}\rightarrow G_{\mathcal{M}}$ given by

$x_{i}\mapsto 1+X_{i}\qquad\qquad y_{i}\mapsto 1+Y_{i}$ (22)

Note this is compatible with abelianisation, i.e.
$\alpha_{\mathcal{M}}\circ\rho_{\mathcal{M}}$ is the canonical map
$\pi_{1}\Sigma_{g}\rightarrow\textnormal{H}_{1}(\Sigma_{g};\mathbb{F}_{r})$.

The group $G_{\mathcal{M}}$ has the weaker property

Property 3.2.12b’: For any degree $r^{k}$ polynomial $P$ consisting of type I,
II or IIIa terms, we can find
$\Psi_{P}:C_{\mathcal{M}}\rightarrow\mathbb{F}_{r}$, such that for all $g\in
G_{\mathcal{M}}$ we have $g^{r^{k}}\in C_{\mathcal{M}}$ and
$\Psi_{P}\big{(}g^{r^{k}}\big{)}=P\big{(}\alpha_{\mathcal{M}}(g)\big{)}$.

Proof: The group $C_{\mathcal{M}}$ is isomorphic to $\mathbb{F}_{r}$ vector
space, whose basis are monomials of degree $r^{k}$ without adjacent
$X_{i},Y_{i}$. When $P$ is a monomial of type I, II or IIIa, we will construct
$\Psi_{P}$ as a projection onto a suitable basis element (compare with
equation 20).

First, consider a type I monomial $P=x_{i}^{r^{k}}$. Then $X_{i}^{r^{k}}$ is a
basis vector, and we can take $\Psi_{P}$ to be linear the projection onto its
span. We do the same for $y_{i}^{r^{k}}$.

Second, suppose $P$ is a monomial of type II or IIIa. Then it must have two
factors which do not come from the same pairs of generators; WLOG they are
$x_{i}^{u_{i}},y_{j}^{v_{j}}$ for $i\neq j$. Consider the corresponding formal
product $Q=X_{i}^{u_{i}}Y_{j}^{v_{j}}$. Now, iterate over the remaining
factors of $P$. For each factor $x_{l}^{u_{l}}$ (respectively $y_{l}^{v_{l}}$)
multiply $Q$ by the corresponding symbol $X_{l}^{u_{l}}$ (respectively
$Y_{l}^{v_{l}}$). At every step the leftmost and rightmost symbol of $Q$ are
different, so either left or right multiplication avoids producing adjacent
$X_{i}Y_{i}$. After exhausting the factors of $P$ we have produced a formal
product $Q$ which does not vanish in $\mathcal{M}$ and whose exponents match
the corresponding exponents of $P$. Then $Q$ is a basis vector for
$C_{\mathcal{M}}$ and a projection onto this element is the desired
$\Psi_{P}$. $\square$

####  3.2.3 Algebra $\mathcal{H}$ and type IIIb terms

Here we construct the algebra $\mathcal{H}$ and an interesting mapping
$\pi_{1}\Sigma_{2}\rightarrow G_{\mathcal{H}}$. We will use it in the bottom
row of the diagram 37, where it will supply type IIIb terms to the non-
vanishing polynomial.

Consider the commutative ring
$\tfrac{\mathbb{F}_{r}[A,B]}{(A^{r^{k}+1},A^{r^{k}}B,B^{2})}$ and take its
quaternion algebra

$\mathcal{H}=\left(\frac{\mathbb{F}_{r}[A,B]}{(A^{r^{k}+1},A^{r^{k}}B,B^{2})}\right)[i,j,k]$
(23)

The variables $A,B$ commute with each other and with $i,j,k$. Note that
$\mathcal{H}$ can also be considered as a polynomial ring over the skew-
comutative ring $\mathbb{F}_{r}[i,j,k]$.

As before, we define the multiplicative group $G_{\mathcal{H}}=1+(A,B)$ and
its central subgroup
$C_{\mathcal{H}}=1+(A,B)^{r^{k}}=1+(A^{r^{k}},A^{r^{k}-1}B)$. Explicitly,

$C_{\mathcal{H}}=\Bigg{\\{}1+\\!\sum_{l\in\\{1,i,j,k\\}}a_{l}A^{r^{k}}l+b_{l}A^{r^{k}-1}Bl\
\Big{|}\ a_{l},b_{l}\in\mathbb{F}_{r}\Bigg{\\}}\cong\mathbb{F}_{r}^{8}$ (24)

Forgetting quadratic and higher terms is a homomorphism
$G_{\mathcal{H}}\rightarrow\mathbb{F}_{r}^{8}$ given by

$\alpha^{\prime}:1+\\!\sum_{l\in\\{1,i,j,k\\}}a_{l}Al+b_{l}Bl+(\deg\geq 2)\
\mapsto\ (a_{l},b_{l})_{l\in\\{1,i,j,k\\}}\in\mathbb{F}_{r}^{8}$ (25)

We will need only a part of the information in $\alpha^{\prime}$. Define
$x_{1},y_{1},x_{2},y_{2}:G_{\mathcal{H}}\rightarrow\mathbb{F}_{r}$ as the
linear projections onto the coefficients of $Ai,Bj,Aj,Bi$ respectively (i.e.
extracting $a_{i},b_{j},a_{j},b_{i}$), and let

$\alpha_{\mathcal{H}}=(x_{1},y_{1},x_{2},y_{2}):G_{\mathcal{H}}\rightarrow\mathbb{F}_{r}^{4}$
(26)

We now establish two facts about these objects. First, there is a homomorphism
from a surface group with appropriate linear terms (lemma 3.2.3). Second,
$r^{k}$-th power produces a type IIIb term from the linearisation (property
3.2.3).

Lemma 3.2.16: There is a homomorphism $\tau:\pi_{1}\Sigma_{2}\rightarrow
G_{\mathcal{H}}$ satisfying

$\tau(x_{1})\equiv 1+Ai,\quad\tau(y_{1})\equiv 1+Bj,\quad\tau(x_{2})\equiv
1+Aj,\quad\tau(y_{2})\equiv 1+Bi\qquad\text{mod }(A,B)^{2}$ (27)

Proof: It is enough to arrange the tail terms in equation (27) so as to kill
the relation in $\pi_{1}(\Sigma_{2})$. We make an ansatz

$\tau(x_{1})=1+Ai+Ek\quad\tau(y_{1})=1+Bj\quad\tau(x_{2})=1+Aj-
Ek\quad\tau(y_{2})=1+Bi$ (28)

for a polynomial $E\in A^{2}\mathbb{F}_{r}[A]$ to be determined later. Then
the commutator $[\tau(x_{1}),\tau(y_{1})]$ becomes

$\displaystyle\tau(x_{1})$
$\displaystyle\tau(y_{1})\tau(x_{1})^{-1}\tau(y_{1})^{-1}=$
$\displaystyle=(1+Ai+Ek)(1+Bj)(1+Ai+Ek)^{-1}(1+Bj)^{-1}=$
$\displaystyle=1+[Ai+Ek,Bj](1+A^{2}+E^{2})^{-1}(1-Ai-Ek)(1-Bj)=$
$\displaystyle=1+2B(1+A^{2}+E^{2})^{-1}(Ak-Ei-A^{2}j-E^{2}j)$ (29)

Analogous computation for the second commutator $[\tau(x_{2}),\tau(y_{2})]$
gives

$\tau(x_{2})\tau(y_{2})\tau(x_{2})^{-1}\tau(y_{2})^{-1}=1+2B(1+A^{2}+E^{2})^{-1}(-Ak-
Ej-A^{2}i-E^{2}i)$ (30)

The relation would be

$[\tau(x_{1}),\tau(y_{1})][\tau(x_{2}),\tau(y_{2})]=1-2B(1+A^{2}+E^{2})^{-1}(A^{2}+E+E^{2})(i+j)$
(31)

Therefore, it is enough to find a power series
$E\in\mathbb{F}_{r}[\\![A]\\!]$, with no constant or linear terms, such that
$A^{2}+E+E^{2}=0$. This is given by

$E=\tfrac{1}{2}\left(\big{(}1-4A^{2}\big{)}^{\frac{1}{2}}-1\right)$ (32)

which is well-defined in $\mathbb{F}_{r}[\\![A]\\!]$, because the denominators
in Taylor expansion of $\sqrt{1+x}$ are powers of 2. $\square$

Property 3.2.12b”: There exists a group homomorphism
$\Psi_{\mathcal{H}}:C_{\mathcal{H}}\rightarrow\mathbb{F}_{r}$ and a polynomial
$R\in\mathbb{F}_{r}[x_{1},y_{1},x_{2},y_{2}]$ consisting only of terms of type
II, such that for any $g\in\text{im}\ \tau\leq G_{\mathcal{H}}$ we have
$\Psi_{\mathcal{H}}\big{(}g^{r^{k}}\big{)}=x_{1}(g)^{r^{k}-1}y_{1}(g)+R\big{(}\alpha_{\mathcal{H}}(g)\big{)}$,
where $x_{1},y_{1}$ are the coordinates in the abelianisation as defined in
equation 26

Proof: Take $g\in G_{\mathcal{H}}$ of the form
$g=1+x_{1}Ai+y_{1}Bj+x_{2}Aj+y_{2}Bi+(\deg\geq 2)$. Then the image of $g$
under $\alpha_{\mathcal{H}}$ is the vector
${(x_{1},y_{1},x_{2},y_{2})^{\top}\in\mathbb{F}_{r}^{4}}$. Moreover,

$\displaystyle g^{r^{k}}$
$\displaystyle=1+\big{(}(x_{1}A+y_{2}B)i+(x_{2}A+y_{1}B)j\big{)}^{r^{k}}=$
(33)
$\displaystyle=\big{[}-(x_{1}A+y_{2}B)^{2}-(x_{2}A+y_{1}B)^{2}\big{]}^{\frac{r^{k}-1}{2}}\cdot\big{[}(x_{1}A+y_{2}B)i+(x_{2}A+y_{1}B)j\big{]}$

The expression standing next to $j$ is $(-1)^{\frac{r^{k}-1}{2}}$ times

$\displaystyle\big{[}$
$\displaystyle(x_{1}^{2}+x_{2}^{2})A^{2}+2(x_{1}y_{2}+x_{2}y_{1})AB\big{]}^{\frac{r^{k}-1}{2}}\cdot(x_{2}A+y_{1}B)=$
$\displaystyle=\big{[}(x_{1}^{2}+x_{2}^{2})^{\frac{r^{k}-1}{2}}A^{r^{k}-1}-(x_{1}^{2}+x_{2}^{2})^{\frac{r^{k}-3}{2}}(x_{1}y_{2}+x_{2}y_{1})A^{r^{k}-2}B\big{]}\cdot(x_{2}A+y_{1}B)=$
$\displaystyle=x_{2}(x_{1}^{2}+x_{2}^{2})^{\frac{r^{k}-1}{2}}A^{r^{k}}+(x_{1}^{2}+x_{2}^{2})^{\frac{r^{k}-3}{2}}\big{(}(x_{1}^{2}+x_{2}^{2})y_{1}-(x_{1}y_{2}+x_{2}y_{1})x_{2}\big{)}A^{r^{k}-1}B=$
$\displaystyle=x_{2}(x_{1}^{2}+x_{2}^{2})^{\frac{r^{k}-1}{2}}A^{r^{k}}+(x_{1}^{2}+x_{2}^{2})^{\frac{r^{k}-3}{2}}(x_{1}^{2}y_{1}-x_{1}x_{2}y_{2})A^{r^{k}-1}B$
(34)

Recall equation 24: the group $C_{\mathcal{H}}$ is isomorphic to
$\mathbb{F}_{r}^{8}$ with the basis

$\left\\{A^{r^{k}-1}\cdot A^{u}B^{1-u}\cdot
l\big{|}u\in\\{0,1\\},l\in\\{1,i,j,k\\}\right\\}$ (35)

Let $\Psi_{\mathcal{H}}:C_{\mathcal{H}}\rightarrow\mathbb{F}_{r}$ be the
projection onto $A^{r^{k}-1}Bj$. Then (possibly up to sign)

$\Psi_{\mathcal{H}}\big{(}g^{r^{k}}\big{)}=(x_{1}^{2}+x_{2}^{2})^{\frac{r^{k}-3}{2}}(x_{1}^{2}y_{1}-x_{1}x_{2}y_{2})$
(36)

This a sum of a single type IIIb monomial $x_{1}^{r^{k}-1}y_{1}$ and $r^{k}-4$
terms of type II, as required. $\square$

####  3.2.4 Proof of proposition 3.2

Recall that to prove proposition 3.2 we need to find an $r$-group $G$, central
$C\leq G$, homomorphisms $\rho:\pi_{1}\Sigma_{g}\rightarrow G$,
$\alpha:G\rightarrow\mathbb{F}_{r}^{2g}$ and $\Psi:C\rightarrow\mathbb{F}_{r}$
such that
$\bullet$ The composition
$\alpha\circ\rho:\pi_{1}\Sigma_{g}\rightarrow\mathbb{F}_{r}^{2g}=\textnormal{H}_{1}(\Sigma_{g};\mathbb{F}_{r})$
is the Hurewicz map
$\bullet$ If $g\in G\setminus\ker\alpha$ then $g^{r^{k}}\in
C\setminus\ker\Psi$.

As parts of the construction we will use
$(G_{\mathcal{M}},C_{\mathcal{M}},\rho_{\mathcal{M}},\alpha_{\mathcal{M}})$
from section 3.2.2 and
$(G_{\mathcal{H}},C_{\mathcal{H}},\tau,\alpha_{\mathcal{H}},\Psi_{\mathcal{H}})$
from section 3.2.3. We will assemble them according to the following diagram:

${\pi_{1}\Sigma_{g}}$${G_{\mathcal{M}}}$${C_{\mathcal{M}}}$${\mathbb{F}_{p}}$${\left(\pi_{1}\Sigma_{2}\right)^{2g}}$${G_{\mathcal{H}}^{2g}}$${C_{\mathcal{H}}^{2g}}$${\rho}$${G^{\prime}}$${C^{\prime}}$
$\scriptstyle{\rho_{\mathcal{M}}}$$\scriptstyle{h_{i}}$$\scriptstyle{(\bullet)^{p^{k}}}$${\times}$$\scriptstyle{\Psi_{0}}$${\times}$$\scriptstyle{\tau^{\times
2g}}$$\scriptstyle{(\bullet)^{p^{k}}}$$\scriptstyle{\Psi_{i}}$${\underbrace{\qquad\qquad\qquad\qquad\qquad}}$${=}$${=}$${\underbrace{\qquad\quad}_{\Psi}}$
(37)

The top row will supply type I, II and IIIa terms of the non-vanishing
polynomial, while the bottom row will one-by-one provide type IIIb terms.

Proof of proposition 3.2 Define

$G^{\prime}=G_{\mathcal{M}}\times G_{\mathcal{H}}^{2g}$ (38)

and let $f_{\mathcal{M}},\\{f_{\mathcal{H},i}\\}_{1\leq i\leq 2g}$ be the
projections onto each factor.

We need to build a homomorphism $\rho:\pi_{1}\Sigma_{g}\rightarrow
G^{\prime}$. For $1\leq i\leq g$ let $h_{2i},h_{2i+1}$ be the projections
$\pi_{1}\Sigma_{g}\rightarrow\pi_{1}\Sigma_{2}$ forgetting all but two
generator pairs, given by

$h_{2i}:\left\\{\begin{matrix}x_{i+a}&\mapsto&x_{a}&\text{if }a\in\\{0,1\\}\\\
y_{i+a}&\mapsto&y_{a}&\text{if }a\in\\{0,1\\}\\\
x_{j},y_{j}&\mapsto&1&\text{if }j\notin\\{i,i+1\\}\end{matrix}\right.\qquad
h_{2i+1}:\left\\{\begin{matrix}x_{i+a}&\mapsto&y_{a}&\text{if
}a\in\\{0,1\\}\\\ y_{i+a}&\mapsto&x_{a}&\text{if }a\in\\{0,1\\}\\\
x_{j},y_{j}&\mapsto&1&\text{if }j\notin\\{i,i+1\\}\end{matrix}\right.$ (39)

Alternatively $h_{2i+1}=r\circ h_{2i}$, where $r$ is the automorphism of
$\pi_{1}\Sigma_{2}$ which exchanges $x_{1,2}\leftrightarrow y_{1,2}$.
Geometrically these maps come from collapsing $g-2$ handles of $\Sigma_{g}$ to
points. Define $\rho=\rho_{\mathcal{M}}\times\prod_{i=1}^{2g}\tau\circ h_{i}$,
where $\tau$ is the homomorphism $\pi_{1}\Sigma_{g}\rightarrow
G_{\mathcal{H}}$ provided by lemma 3.2.3.

Define $G=\text{im}\ \rho\leq G^{\prime}$.

We have a map $\alpha=\alpha_{\mathcal{M}}\circ
f_{\mathcal{M}}:G\rightarrow\mathbb{F}_{r}^{2g}$. Then $\alpha\circ\rho$
equals $\alpha_{\mathcal{M}}\circ\rho_{\mathcal{M}}$, which is the standard
map $\pi_{1}\Sigma_{g}\rightarrow H_{1}(\Sigma_{g};\mathbb{F}_{r})$. Note that
on $G$ this is compatible with the abelianisations coming from each factor
$G_{\mathcal{H}}$, in the sense that $\alpha_{\mathcal{H}}\circ
f_{\mathcal{H},i}\big{|}_{G}$ is equal to $\alpha$ followed by some coordinate
projection $\mathbb{F}_{r}^{2g}\rightarrow\mathbb{F}_{r}^{4}$.

The subgroup $C^{\prime}=C_{\mathcal{M}}\times C_{\mathcal{H}}^{2g}$ is
central in $G^{\prime}$, and it contains all the $r^{k}$-th powers. We define
$C=G\cap C^{\prime}$.

Suppose $k$ satisfies $r^{k}>(n-1)(r-1)$, and let $P$ be the polynomial of
degree $r^{k}$ vanishing nowhere on $\mathbb{F}_{r}^{2g}$ produced by lemma 3.
By observation 3.2.1, it can be assumed to have the form

$P(x_{1},y_{1},\dots,x_{g},y_{g})=Q(x_{1},y_{1},\dots,x_{g},y_{g})+\sum_{i=1}^{g}a_{i}x_{i}^{r^{k}-1}y_{i}+b_{i}x_{i}y_{i}^{r^{k}-1}$
(40)

where $a_{i},b_{i}\in\mathbb{F}_{r}$, and $Q$ contains only terms of type I,
II or IIIa.

By the property 3.2.3, there exist group homomorphisms
$\Psi_{2i},\Psi_{2i+1}:C_{\mathcal{H}}\rightarrow\mathbb{F}_{r}$ such that for
any $g\in G$ with $\alpha(g)=(x_{i},y_{i})^{\top}_{i}$ we have

$\Psi_{2i}\circ
f_{\mathcal{H},i}\left(g^{r^{k}}\right)=x_{i}^{r^{k}-1}y_{i}+R_{2i}\big{(}\alpha(g)\big{)}\qquad\Psi_{2i+1}\circ
f_{\mathcal{H},i}\left(g^{r^{k}}\right)=x_{i}y_{i}^{r^{k}-1}+R_{2i+1}\big{(}\alpha(g)\big{)}$
(41)

where again $R_{j}$ contain only terms of type I, II or IIIa. By the property
3.2.2, there is a group homomorphism
$\Psi_{0}:G_{\mathcal{M}}\rightarrow\mathbb{F}_{r}$ satisfying

$\Psi_{0}\circ
f_{\mathcal{M}}\left(g^{r^{k}}\right)=\left(Q-\sum_{i=1}^{g}(a_{i}R_{2i}+b_{i}R_{2i+1})\right)\big{(}\alpha(g)\big{)}$
(42)

Finally, we combine them as

$\Psi=\left(\Psi_{0}\circ f_{\mathcal{M}}+\sum_{i=1}^{g}a_{i}\Psi_{2i}\circ
f_{\mathcal{H},2i}+b_{i}\Psi_{2i+1}\circ
f_{\mathcal{H},2i+1}\right)\Bigg{|}_{C}$ (43)

By construction $\Psi\big{(}g^{r^{k}}\big{)}=P\big{(}\alpha(g)\big{)}$. Then
$(G,C,\rho,\alpha,\Psi)$ is a witness to proposition 3.2. $\square$

##  4 Comments

It is natural to ask whether the assumption of solvability in theorem 1.1 is
necessary. We ask the following

Question 4.0.17: Let $g\geq 2$, $n\geq 0$ and
$\theta:\pi_{1}\Sigma_{g,n}\rightarrow G$ be an arbitrary finite quotient.
Does exists a cover $\widetilde{\Sigma}\rightarrow\Sigma_{g,n}$ with
$\textnormal{H}_{1}^{\theta\neq
1}(\widetilde{\Sigma};\mathbb{Q})\neq\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Q})$?

Our proof fundamentally relies on detecting loops using abelian quotients, so
solvable $G$ seems to be the most general we can hope for with the current
approach. Let us note a simple obstacle to potential approches to conjecture
4:

Observation 4.0.18: Let $\widetilde{\Sigma}\rightarrow\Sigma$ be a finite
normal cover with deck group $G$, and $\theta:\pi_{1}\Sigma\rightarrow Q$ be a
finite nontrivial quotient. If the orders of $G$ and $Q$ are coprime, then
$\textnormal{H}_{1}^{\theta\neq
1}(\widetilde{\Sigma};\mathbb{Z})=\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Z})$.

Proof: Consider $\gamma\in\pi_{1}\widetilde{\Sigma}$. If
$\gamma\notin\ker\theta$ then
$[\gamma]\in\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Z})$. Otherwise take
any $\lambda\in\pi_{1}\Sigma\setminus\ker\theta$. Then $\lambda^{|G|}$ is a
loop in $\widetilde{\Sigma}$ and

$\theta\left(\gamma\lambda^{|G|}\right)=\theta\left(\lambda^{|G|}\right)\neq
1_{Q}$ (44)

Therefore
$[\gamma\lambda^{|G|}],[\lambda^{|G|}]\in\textnormal{H}_{1}^{\theta\neq
1}(\widetilde{\Sigma};\mathbb{Z})$. They differ by gamma, so
$[\gamma]\in\textnormal{H}_{1}^{\theta\neq 1}(\widetilde{\Sigma};\mathbb{Z})$.
Hence $[\gamma]\in\textnormal{H}_{1}^{\theta\neq
1}(\widetilde{\Sigma};\mathbb{Z})$ for any
$\gamma\in\pi_{1}\widetilde{\Sigma}$, so $\textnormal{H}_{1}^{\theta\neq
1}(\widetilde{\Sigma};\mathbb{Z})=\textnormal{H}_{1}(\widetilde{\Sigma};\mathbb{Z})$.
$\square$

## References

  * [1] Fedor Bogomolov and Yuri Tschinkel.  Unramified correspondences.  In Algebraic Number Theory and Algebraic Geometry, volume 300, pages 17–25. American Mathematical Society, 2002.
  * [2] Benson Farb and Sebastian Hensel.  Finite covers of graphs, their primitive homology, and representation theory.  New York J. Math, 22:1365–1391, 2016.
  * [3] Benson Farb and Dan Margalit.  A Primer on Mapping Class Groups (PMS-49).  Princeton University Press, 2012.
  * [4] Walter Feit and John G Thompson.  Solvability of groups of odd order.  Pacific Journal of Mathematics, 1963.
  * [5] Wolfgang Gaschütz.  Über modulare darstellungen endlicher gruppen, die von freien gruppen induziert werden.  Mathematische Zeitschrift, 60:274–286, 1954.
  * [6] Thomas Koberda and Ramanujan Santharoubane.  Quotients of surface groups and homology of finite covers via quantum representations.  Inventiones Mathematicae, 206:269–292, 2016.
  * [7] Eduard Looijenga.  Some algebraic geometry related to the mapping class group, 06 2015.
  * [8] Wilhelm Magnus, Abraham Karrass, and Donald Solitar.  Combinatorial group theory: Presentations of groups in terms of generators and relations.  Dover Publications, 2004.
  * [9] Justin Malestein and Andrew Putman.  Simple closed curves, finite covers of surfaces, and power subgroups of $\mathrm{Out}(F_{n})$.  Duke Math. J., 168(14):2701–2726, 2019.
  * [10] Julien Marché.  Homology generated by lifts of simple curves.  https://mathoverflow.net/questions/86894.
  * [11] Vladimir Marković.  Unramified correspondences and virtual properties of mapping class groups.  2022\.  https://people.maths.ox.ac.uk/markovic/M-mod.pdf, preprint.
  * [12] Vladimir Marković and Ognjen Tošić.  The second variation of the hodge norm and higher prym representations.  https://people.maths.ox.ac.uk/m̃arkovic/MT-hodge.pdf, preprint.


# PyBryt: auto-assessment and auto-grading for computational thinking

Christopher Pyles  Microsoft  Francois van Schalkwyk  Department of Earth
Science and Engineering, Imperial College London, United Kingdom  Gerard J.
Gorman  Department of Earth Science and Engineering, Imperial College London,
United Kingdom  Marijan Beg  Department of Earth Science and Engineering,
Imperial College London, United Kingdom  Lee Stott  Microsoft  Nir Levy
Microsoft  Ran Gilad-Bachrach  Microsoft  Biomedical Engineering Department,
Tel-Aviv University  Edmond J. Safra Center for Bioinformatics, Tel-Aviv
University  Sagol School of Neuroscience, Tel-Aviv University

###### Abstract

We continuously interact with computerized systems to achieve goals and
perform tasks in our personal and professional lives. Therefore, the ability
to program such systems is a skill needed by everyone. Consequently,
computational thinking skills are essential for everyone, which creates a
challenge for the educational system to teach these skills at scale and allow
students to practice these skills. To address this challenge, we present a
novel approach to providing formative feedback to students on programming
assignments. Our approach uses dynamic evaluation to trace intermediate
results generated by student’s code and compares them to the reference
implementation provided by their teachers. We have implemented this method as
a Python library and demonstrate its use to give students relevant feedback on
their work while allowing teachers to challenge their students’ computational
thinking skills.

##  1 Introduction

In her seminal paper, Wing [30] argued that computational thinking is a skill
that is not limited only to computer programming but that it has a much
broader impact. Furthermore, Wing argued that computational thinking should be
taught to any college freshman and should not be limited to a computer science
major. Some policymakers argue that computational thinking should be taught in
the compulsory education system. In Finland, for example, “algorithmic
thinking” is a mandatory topic for first-grade students [6]. Accordingly,
computational thinking should be taught at a massive scale [16], with higher
education playing a critical role in ensuring graduates have the necessary
industry-transferable digital skills for the workplace [2]. This makes tools
for automated guiding of students as well as for providing automated formative
(auto-assessment) and summative (auto-grading) feedback of paramount
importance [28, 31]. Indeed, the need for such tools has been identified over
60 years ago [15]. The Adoption of Auto-Grading (AG) and Auto-Assessment (AA)
tools has seen significant growth in recent years, and it is now widely
recognized as an enabler of global-scale education pedagogy and academic
support system [13, 10, 18]. The recent growth of remote learning challenges
educators to provide more support for unattended and asynchronous learning.

Many AA & AG tools are built around a set of unit tests [12, 9, 24, 4, 17].
This method for dynamic evaluation provides a pass or fail score for the
entire student’s code or for subsets of the code for which the API was
specified in advance. This means that, to enable fine-grained feedback, the
instructor has to provide a detailed description of the API – a process that
has been referred to as unit test “scaffolding”, or microlearning [25].
However, in many cases, this process deprives the students of a better
discovery-oriented learning experience that a tutor and not an automatic unit
test can provide.

As an example, a student who is asked to write a program to compute the median
of elements in a list may get a scaffolded code skeleton, similar to the one
presented in Listing 1, and asked to complete missing parts.

⬇

1S = [8.0, 5.0, -1.0, 3.0, 5.0, 2.25]

2sorted_S = ...

3size_of_S = ...

4middle = ...

5is_size_of_S_even = ...

6if is_size_of_S_even:

7 median = ...

8else:

9 median = ...

10

11print("The median is ", median)

Listing 1: Scaffolded assignment example

Due to the limitation of the automated evaluation tools, the instructor
provides the student with the architecture of the solution. Thus, the student
is practising basic programming skills and is not challenged with fundamental
computational thinking tasks such as decomposing the problem and considering
multiple possible solutions. This may be a good exercise for novice students
doing their first coding steps, but it is ineffective when practising
student’s ability to come up with the architecture by themselves. On the other
hand, a much less restrictive exercise for computing the median may ask the
student to complete the code as presented in Listing 2, allowing multiple
implementation patterns and approaches. However, this format makes it harder
to generate constructive feedback automatically.

⬇

1def median(S):

2 ...

Listing 2: Open assignment example

Static code analysis has been proposed as another solution for AA & AG [32,
27]. Unlike unit-test-based analysis, these methods are not limited by the
interface of the solution. Instead, this is done by analyzing the student’s
source code or the byte-code and comparing it against a set of rules specified
by the instructor. However, defining the rules to be checked is challenging,
and therefore most instructors would find it hard to use. Recently, deep-
learning-based approaches were presented for comparing students’ solutions to
each other and to reference implementations [3, 8]. However, Bhatia and Singh
[3] discuss only the correction of syntax errors while de Souza et al. [8]
focus only on auto-grading.

In this work, we present a new method to assess student’s work which we have
implemented in the _PyBryt_ library which is available at
https://github.com/microsoft/pybryt. In _PyBryt_ , the instructor is providing
one or several _reference implementations_ of the given assignment. The
teacher annotates these reference implementations by marking both expected and
not expected intermediate values to be computed by the student. The instructor
can also specify feedback to be given to the student depending on whether
these annotated values are present or absent. The _PyBryt_ library executes
the student’s code and traces intermediate values to the ones marked by the
instructor. Based on the matching between the observed values and expected
values, feedback is given to the student. This approach allows controlling the
freedom given to students: the instructor can provide fine-grained steps and
trace the student’s ability to follow instructions, or alternatively, the
student can work on an open problem by breaking it into sub-tasks and
practising computational thinking.

In Section 2 we present the concept of reference implementations in _PyBryt_
and how they are used to asses students code. In Section 3 we present several
examples for the use of _PyBryt_ for providing feedback to students and for
plagiarism detection. We conclude with a discussion in Section 4.

##  2 Reference Implementations

To provide feedback to students or to grade their solutions, the instructor
specifies their expectations. In _PyBryt_ , expectations are defined using a
_reference implementation_ (RI) – a set of conditions expected from the
students’ code. RI’s are constructed by annotating series of values expected
to be present in the student’s solution, even if not explicitly specified in
the guidelines for the assignment. For example, suppose the student is asked
to implement the median function. Apart from the correct return value, the
instructor may expect the student to sort the list of numbers in their
implementation and calculate the list’s length to determine if it has an odd
or even number of items. Therefore, the instructor annotates these values in
RI. In _PyBryt_ , this is done as shown in Listing 3. When the student’s code
is executed in the _PyBryt_ environment, all intermediate values that are
created by the student’s solution are scanned to find the values marked by the
instructor in RI. The instructor has the option to provide success-messages to
be presented to the student if their code computes the expected values and
failure-messages to present if the values are missing. Therefore, the
instructor can provide formative feedback that can encourage and focus the
students on ways to improve.

⬇

1import pybryt

2

3def median(S):

4 sorted_S = sorted(S)

5 pybryt.Value(sorted_S,

6 success_message = "Great: The list is sorted correctly.",

7 failure_message = "Advice: The list was not sorted.")

8

9 size_of_S = len(S)

10 pybryt.Value(size_of_S,

11 success_message = "Great: The size of the list is computed.",

12 failure_message = "Advice: The size of the list is not computed to
determine if the number of elements is odd or even.")

13

14 middle = (int)(size_of_set / 2)

15 is_size_of_S_even = (size_of_set % 2) == 0

16

17 if is_size_of_S_even:

18 return (sorted_S[middle-1] + sorted_S[middle]) / 2

19 else:

20 return sorted_S[middle]

Listing 3: Median example annotated by the instructor

It is important to note that only the instructor adds annotations to their RI.
Students are not required to modify their code. Instead, _PyBryt_ executes
students code in the debugger framework and traces the memory footprint to
search for the values marked in the RI. All intermediate values are extracted
regardless of variable names or function names. Accordingly, the teacher can
design their assignments without "scaffolding" or using microlearning [25].
Furthermore, the computational complexity of the solution can be evaluated
using the number of steps taken to run the program, which is a consistent
measure that is independent of the hardware on which the program is executed
or other programs running on the computer simultaneously. _PyBryt_ allows
instructors to specify in their RI the expected computational complexity of
the solution and provide students feedback when they do or do not match these
expectations.

To demonstrate the way _PyBryt_ works consider the student code in Listing 4
as a solution to the median assignment. The solution does compute the median
correctly; however, it will trigger two failure messages since expected
intermediate values are not computed. On the other hand, the solution in
Listing 5 will trigger two success messages even though the student did not
use the same variable names and sorted the list in-place as opposed to the RI
where new memory is allocated. Nevertheless, _PyBryt_ recognizes that the
required values were computed by the student and triggers success messages.

⬇

1def median(S):

2 import numpy as np

3 return np.median(S)

Listing 4: Median example - student implementation with numpy. Although this
solution computes the median correctly, _PyBryt_ can identify that the student
uses a library call to compute the median.

⬇

1def median(T):

2 T.sort()

3 middle = (int)(len(T) / 2)

4 is_set_size_even = (len(T) % 2) == 0

5

6 if is_set_size_even:

7 return (T[middle-1] + T[middle]) / 2

8 else:

9 return T[middle]

Listing 5: Median example - student implementation with in memory sorting

_PyBryt_ traces values computed by students solutions even when they are not
assigned to variables. Note that the second value the instructor marked in the
median assignment is the length of the list, however, in Listing 5, this value
is computed but never assigned to a variable. Nevertheless, _PyBryt_ detects
that the value was computed and triggers the success message. To achieve that,
_PyBryt_ first analyzes the program by parsing its Abstract Syntax Tree (AST)
and assigns each intermediate result to a variable. Hence, _PyBryt_ first does
static evaluation of the student’s solution and creates a version of the code
where every intermediate result is assigned to a variable. Next, it runs the
code in debug mode to trace every value assigned to a variable while executing
the code.

###  2.1 Logic and temporal rules over values of interest

In some cases, the instructor may be interested in defining logical rules over
the annotated values. For example, consider an assignment where the student is
expected to find the maximum value in a list. The instructor may wish to
verify that the student does not sort the list since this increases the
complexity of the solution. Therefore, the instructor may define the RI as
shown in Listing 6.

⬇

1import pybryt

2

3def max_of_list(S):

4 sorted_S = sorted(S)

5 pb_sort = ~pybryt.Value(sorted_S)

6 pb_sort.failure_message = "Advice: sorting the list adds unnecessary
complexity"

7 size_of_set = len(S)

8 return(sorted_S[len(S)-1])

Listing 6: Finding the maximal value in a list

In the RI presented in Listing 6, the logical _not_ rule is introduced using
the ~ symbol. This means that pb_sort is satisfied when the sorted version of
S is not encountered, and the failure message is triggered only when the value
is present. _PyBryt_ supports several logical rules: the _or_ operator |, the
_and_ operator &, and the not operator ~. Logical rules are useful in many
settings. For example, if the student can use several data structures to store
the data, an or-statement between the different values can be used. In some
cases, it may be easier for the instructor to support such cases using
multiple RI’s as discussed in Section 2.2.

Besides logic operations, _PyBryt_ also supports two temporal operators:
before and after. If we assume values v1 and v2, v_before = v1.before(v2) will
trigger the success message if, in the student’s solution, the first time v1
is satisfied precedes the first time v2 is satisfied. Similarly, v_after =
v1.after(v2) expects v1 to occur after v2. Since this is a common use-case,
_PyBryt_ also supports _collections_. A collection is a list of annotated
values expected to be present. The instructor can specify whether the
student’s solution should generate these values in the same order as in the RI
or the order in which the values are generated is not a requirement. Moreover,
the result of a logical or temporal operation is another Value object,
allowing rules to be chained to create more complex conditions when needed.

###  2.2 Multiple reference implementation

When evaluating students code, _PyBryt_ first runs student’s implementation,
traces and stores every value that is being computed, and finally compares
them to those marked in the RI. Since the values created by the student’s
implementation are stored, they can be compared to several RI’s. A single RI
is restrictive since there may be multiple algorithms for solving a given
problem. For the median example, one possible solution is to sort the list and
find the item in the middle of the sorted list (or the average of the two
middle items if the number of items is even). This solution has time
complexity of $O\left(n\log\left(n\right)\right)$. However, there are more
efficient solutions, such as the randomized quick-select algorithm [14] or the
deterministic pick-pivot algorithm [5]. These solutions are very different
from the sort-based solution and therefore generate a different memory
footprint. Therefore, _PyBryt_ allows different possible solutions to be
covered by separate RI’s.

Since extracting the memory footprint from students’ solutions may be time-
consuming, _PyBryt_ generates an object that stores all values so that
comparison to multiple RI’s is more efficient. In addition, the RI can be
"compiled" into an object that stores all the required values and logical
rules to further reduce the time.

Another setting in which the use of multiple RI’s is useful is when a mistake
in an early stage may lead to a deviation in the computation. For example,
consider the assignment that asks the student to count the number of times a
substring matching the pattern ’ab?d’ appears in the text such that the
matching is case insensitive. A student that did not convert the text to
lower-case will not match many of the intermediate results expected and
therefore may get many error messages. However, if this happens to be a common
mistake, the teacher may create a RI for this type of “solution”. It will
capture the error and be able to test other aspects of the solution.

Having multiple RI’s allows additional types of assignments that can be given
to students to practice their computational thinking skills. For example, an
assignment can ask students to implement two types of sorting algorithms. Note
that _PyBryt_ can verify that the solutions are different by verifying that
they match different RI’s since they generate different memory footprints.

###  2.3 Computational complexity

Since _PyBryt_ runs students’ solutions in debug mode, it also counts the
number of steps taken during the execution of the code. This can be useful
when students are learning about computational complexity. Students can try
different implementations and see how their choices affect the number of steps
taken. This can be used in multiple ways. The teacher can specify the required
complexity or ask students to implement both bubble-sort and merge-sort and
draw a chart showing the number of steps it took for their solution to
complete as a function of the input size.

Counting steps can be used even for learning fine-grain optimization
techniques. For example, students can be asked to find the prime numbers in a
given list of integers. In this assignment, caching can be used to accelerate
the computation. Therefore, students can be asked to find an efficient
solution, and _PyBryt_ can be used to provide them with feedback about the
efficiency. This can also be used for gamification by creating a class
challenge to find a solution that uses the fewest instructions. Note that
since students may be using different computers, measuring the time to execute
may give an unfair advantage to students that have access to faster computers,
but _PyBryt_ can measure the complexity independent of hardware.

###  2.4 Programming style

_PyBryt_ can be used to provide feedback helping students to improve their
programming style. Consider, for example, an assignment where the student is
asked to implement a function that takes a list of numbers and returns a list
of these numbers squared. In Listing 7, two possible solutions are presented.
Both solution1 and solution2 in Listing 7 are correct. However, solution1
using list-comprehension is more readable and thus preferred. To see which
solution the student used, it is possible to check the intermediate values.
When using a loop, as solution2 does, the result list is gradually built and
therefore it starts as an empty set, followed by having the value [1], then
[1, 4] and finally [1, 4, 9]. However, list comprehension creates the list in
a single step. Therefore, the value [1, 4], as an example, will never be
observed, although the value [1, 4, 9] will, and the instructor can mark the
value [1, 4] to identify the use of a for-loop. It should be noted that static
methods for evaluating programs can also be used to identify different
solutions. However, the benefit of using _PyBryt_ for this task is the fact
that the same tool and syntax can be used in many scenarios, which makes it
easier for the instructor to use.

⬇

1def solution1(lst):

2 result = [x*x for x in lst]

3 return result

4

5def solution2(lst):

6 result = []

7 for x in lst:

8 result.append(x*x)

9 return results

Listing 7: Two methods for computing the square of every item in the list

###  2.5 Tolerances and Invariances

A possible drawback of using _PyBryt_ ’s approach is tolerance to slight
fluctuations in results. For example, when using real numbers, small numerical
errors may occur due to the finite precision of the computation, e.g. the
statement 1 == ((0.3 * 3) + 0.1) evaluates to False in Python 3.8.5. To
overcome this issue, _PyBryt_ supports tolerances when comparing numerical
values. Both relative and absolute tolerances are supported in a similar
fashion to NumPy’s isclose function [20].

Similar problems may be encountered when working with strings where the
instructor may be invariant to using lower-case vs upper-case letters.
_PyBryt_ supports invariants by specifying them when declaring a value.
Therefore, if the RI declares:
pybryt.Value("hello", invariants=[string_capitalization])
then it will match the strings "Hello", "HELLO", and "HeLLo". Other invariants
supported include list-permutation and matrix-transpose. Furthermore, the
instructor can implement additional invariances.

###  2.6 Limitations

It is important to note that _PyBryt_ may not be suitable for any possible
assignment. For example, the current version of _PyBryt_ is not designed to
test solutions that use parallelism or solutions that operate on large memory
objects. It also induces running time overheads, and therefore solutions that
are slow to run might become excessively slow when run through _PyBryt_.
Random algorithms may also be hard to evaluate with _PyBryt_ although this
problem can be avoided by fixing the seed of the random number generator.

##  3 Examples

In this section, we present several examples of the use of _PyBryt_.

###  3.1 Counting words

Here, we consider an assignment in which students are asked to write a
function that counts the number of words in a string. The instructor can
provide students with the signature of the required function (Listing 8) and
ask them to complete it.

⬇

1def count_words(text: str) -> int:

2 ...

Listing 8: Count words assignment without scaffolding.

A student may implement the count_words function by splitting the string using
built-in methods and then count the number of items in the resulting list as
demonstrated in Listing 9.

⬇

1def count_words(text: str) -> int:

2 fragments = text.split()

3 length = len(fragments)

4 return length

Listing 9: Count words implementation

To create a RI, the instructor may want to trace: (i) the list of words
created by splitting the text (fragments), and (ii) the count of words as a
Python int (length). This RI is shown in Listing 10. The key thing to observe
is the ease with which the instructor can create a RI. To check the student’s
solution, it can be executed with different values as inputs as demonstrated
in Listing 11.

⬇

1def count_words(text: str) -> int:

2 # Split the text by spaces

3 fragments = text.split()

4 pybryt.Value(fragments, failure_message="It may help to first split the
string into a list of words", success_message="Great, the string was converted
into a list of words")

5

6 # Count the number of items in the result

7 length = len(fragments)

8 pybryt.Value(length,

9 success_message="Great, identified the number of words in the string",

10 failure_message="Cannot find a count of the number of words")

11 return length

Listing 10: Count words reference implementation

⬇

1assert count_words("Waltz, bad nymph, for quick jigs vex.") == 7

2assert count_words("The five boxing wizards-- \njump quickly!") == 6

3assert count_words("Sphinx of black quartz, judge my vow.") == 7

Listing 11: Unit tests for count words assignment

###  3.2 Insertion Sort

In this example, we consider an assignment in which students are asked to
implement insertion sort. With _PyBryt_ , the instructor does not need to
create a scaffolded version of the solution, instead, the student can be asked
to implement a function: insertion_sort that takes a list of integers as its
input and returns the list sorted in ascending order using insertion sort.

⬇

1def insertion_sort(x: list[int]) -> list[int]:

2 for i in range(1, len(x)):

3 current = x[i]

4 j = i - 1

5 while j >=0 and current < x[j] :

6 x[j+1] = x[j]

7 j -= 1

8 x[j+1] = current

9 return x

Listing 12: A correct implementation of an insertion sort assignment

⬇

1def insertion_sort(x: list[int]) -> list[int]:

2 for i in range(1, len(x)-1): # MISTAKE: len(x)-1 instead of len(x)

3 current = x[i]

4 j = i - 1

5 while j >=0 and current < x[j] :

6 x[j+1] = x[j]

7 j -= 1

8 x[j+1] = current

9 return x

Listing 13: An incorrect implementation of an insertion sort assignment, note
that the outer loop iterates to ‘len(x)-1‘ instead of ‘len(x)‘.

Listing 12 presents a possible correct answer to this assignment while Listing
13 presents an incorrect solution in which the student’s outer loop does not
iterate to the end (len(x)-1 instead of len(x)). The instructor would like to
distinguish the correct solution from the incorrect one and provide formative
feedback. A unit-test can be used to tell the correct implementation from the
erroneous one as demonstrated in Listing 14. From this feedback, both the
student and educator can only see if the final solution is correct. However,
even if the solution is correct, it cannot determine whether insertion sort
was used or not. Moreover, if the student did not implement the code
correctly, the feedback does not provide information on how to improve the
code. Therefore, this method provides little value both in the formative
feedback it provides and when used to provide summative feedback.

⬇

1x = [55, 111, -33, 65, 1001, -362, 451]

2assert insertion_sort(x) == list(sorted(x))

3\-----------------------------

4AssertionError Traceback (most recent call last)

5<ipython-input-6-ad50795e9ab5> in <module>

6 1 x = [55, 111, -33, 65, 1001, -362, 451]

7\----> 2 assert insertion_sort(x) == list(sorted(x))

8

9AssertionError:

Listing 14: Unit test feedback for the insertion sort assignment. Note that
the feedback is non-constructive from student’s perspective

In contrast to non-informative feedback provided by unit-tests, using _PyBryt_
, the solution in Listing 12 can be converted into a RI such that the feedback
for the incorrect assignment Listing 13 would be more informative as
demonstrated in Listing 15.

⬇

1with pybryt.check(PyBryt_reference(1, 1)):

2 insertion_sort([55, 111, -33, 65, 1001, -362, 451])

3

4REFERENCE: exercise-1_1

5SATISFIED: False

6MESSAGES:

7 - ERROR: Hmmm... It looks like the algorithm does not perform insertion
sort.

8 - ERROR: Please make sure the outer loop iterates from the second element to
the last.

9 - SUCCESS: Great! The inner loop iterates towards left.

10 - ERROR: The function returns a wrong solution.

Listing 15: _PyBryt_ feedback for the incorrect implementation of the
insertion sort assignment

From _PyBryt_ ’s feedback, the student can see that although the inner loop is
correct, the outer loop is wrong. Because of this, the algorithm does not
perform sort as expected. This allows the student to see if their final
solution is correct, and _PyBryt_ points the student to the “outer loop” to
correct the mistake. Similarly, the instructor does not have to go into the
source code and find an error. Instead, the educator can resort to _PyBryt_ ’s
feedback. As such, _PyBryt_ gives much more detailed feedback emphasizing all
the points student’s function does right and where it can be improved. This
way, we can ensure the function performs insertion sort and not some other
sorting algorithm. To demonstrate that consider a student that instead of
implementing insertion-sort calls Python’s sorted function to sort the list as
shown in Listing 8. This solution will pass the unit test since the list is
sorted correctly. However, _PyBryt_ can recognize that the ingredients of
insertion-sort are missing while the result is correct as demonstrated in the
feedback provided by _PyBryt_ in Listing 16.

⬇

1with pybryt.check(PyBryt_reference(1, 1)):

2 insertion_sort([55, 111, -33, 65, 1001, -362, 451])

3

4REFERENCE: exercise-1_1

5SATISFIED: False

6MESSAGES:

7 - ERROR: Hmmm... It looks like the algorithm does not perform insertion
sort.

8 - ERROR: Please make sure the outer loop iterates from the second element to
the last.

9 - ERROR: Please make sure the inner loop iterates towards left.

10 - SUCCESS: Amazing! The function returns the correct solution.

Listing 16: _PyBryt_ feedback for the insertion-sort assignment when a student
implement a sorting algorithm which is not insertion-sort

Therefore, _PyBryt_ has the potential of saving time for instructors when
marking the submissions of entire classes. On the other hand, the student can
see all the steps that they did right, which helps with the learning
experience and it is more encouraging thus enhancing the overall student
experience and increasing student satisfaction. When implemented as a self-
assessment tool, students can receive immediate encouraging and constructive
feedback which may create benefits from gamification perspectives.

###  3.3 Plagiarism Detection

Some accounts suspect that at least 20% of students are involved in
programming plagiarism, even at the top
universities.111https://www.nytimes.com/2017/05/29/us/computer-science-
cheating.html Others suggest that the numbers might be even higher: in a
survey of 138 students, 72.5% admitted to have plagiarized at least once in a
programming assignment [26]. As a result, many methods have been developed for
detecting plagiarism. To illustrate that, we note that at the time of writing
this paper,222in August 2021 Google Scholar333https://scholar.google.com/
reports that 21000 papers are matching the query ‘plagiarism programming
assignments’, 7500 of them were published since 2017, and 2650 since 2020.
Scholars also reported that reducing plagiarism does improve students
competency. For instance, Pawelczak [22] reported that since the introduction
of automatic plagiarism detection, students scores improved by 8.6%.

In an attempt to conceal plagiarism, students use many techniques ranging from
changing variable names and adding blank lines to breaking functions and
adding non-functional code [23]. _PyBryt_ can act as a plagiarism detection
tool by automatically converting students’ submissions into RI’s and comparing
other students submissions to it. Since _PyBryt_ compares only the values of
variables, it is resilient to obfuscation techniques such as variable
renaming, the addition of redundant code, changes to the order of computation
that does not result in functional changes and more.

To use PyBryt as a plagiarism detection mechanism we note that if a solution
was plagiarized then both the original version of the code and the copied
version of the code will share most intermediate values. This is true even if
variable names where changed or function names were changed. Moreover, even if
a sophisticated student changed the order of calls to functions in places
where it would not have consequences on the results then PyBryt can detect the
plagiarism. One potential problem is that some intermediate values are very
common and are not a reliable signal for plagiarism. To circumvent this
problem, we propose using a method akin to TF-IDF to score the
’suspiciousness’ of finding a value matching in the code submitted by separate
students.If a value is common in the solutions of many students, then this
value is not a significant marker for plagiarism.

##  4 Summary and Conclusions

Impagliazzo and Pears [16] argued that learning should include both knowledge,
skill, and disposition. More precisely, Corbett and Anderson [7] found that in
learning programming, students benefit from explicit and in-context guidance
for coding assignments, compared to other means of feedback. This is
especially important in light of the big gap in the faculty-to-teacher ratio
in different colleges: Ertek et al. [11] presented in their study a
comprehensive benchmark of the top 100 U.S. universities and found that the
faculty-to-student ratio is a significant competitiveness factor.

In this work, we presented _PyBryt_ , which uses a new approach to providing
feedback to students on their coding assignments. _PyBryt_ compares students
solutions to RI’s by checking for the presence or absence of critical values,
as marked by the instructors. Thus _PyBryt_ is easy to use yet does not
require the teacher to provide scaffolded exercises.

A side benefit of our approach is the ability to detect plagiarism. Plagiarism
was identified as a concern in programming education since the 70’s [29, 21],
and continues to worry educators today [19]. As _PyBryt_ follows memory
evolution during run time, it can detect similarity between programs - even if
the source code is different, e.g. different variable names or redundant code.

This paper presents _PyBryt_ and the way it is implemented. We are currently
working on evaluating _PyBryt_ in different pedagogical settings to measure
its contribution to the learning process of students and the effort required
from educators to use it. _PyBryt_ can be extended in many ways. In its
current form _PyBryt_ supports only programs in python while it can be
extended to support many other programming languages. Furthermore, it can
support cross-lingual assessments since the intermediate results computed are
invariant to the programming language used in many cases.

Moreover, _PyBryt_ may be used beyond the classroom for tasks such as code-
refactoring. Code-refactoring is a challenging task even for seasoned
engineers. _PyBryt_ can support this process by converting the original code
into a reference implementation and testing the refactored code against it.
This allows the detection of errors in the new implementation even when the
code’s internal and/or external structure does not match the original one.

## References

  * [1]
  * Ali [2020] Wahab Ali. 2020\.  Online and remote learning in higher education institutes: A necessity in light of COVID-19 pandemic.  _Higher education studies_ 10, 3 (2020), 16–25.
  * Bhatia and Singh [2016] Sahil Bhatia and Rishabh Singh. 2016.  Automated Correction for Syntax Errors in Programming Assignments using Recurrent Neural Networks.  _arXiv:1603.06129 [cs]_ (March 2016).  http://arxiv.org/abs/1603.06129 arXiv: 1603.06129.
  * Blank et al. [2019] Douglas S Blank, David Bourgin, Alexander Brown, Matthias Bussonnier, Jonathan Frederic, Brian Granger, Thomas L Griffiths, Jessica Hamrick, Kyle Kelley, M Pacer, et al. 2019\.  nbgrader: A tool for creating and grading assignments in the Jupyter Notebook.  _The Journal of Open Source Education_ 2, 11 (2019).
  * Blum et al. [1973] Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, Robert Endre Tarjan, et al. 1973\.  Time bounds for selection.  _J. Comput. Syst. Sci._ 7, 4 (1973), 448–461.
  * Bocconi et al. [2016] Stefania Bocconi, Augusto Chioccariello, Giuliana Dettori, Anusca Ferrari, Katja Engelhardt, Panagiotis Kampylis, and Yves Punie. 2016\.  Developing computational thinking in compulsory education.  _European Commission, JRC Science for Policy Report_ 68 (2016).
  * Corbett and Anderson [2001] Albert T. Corbett and John R. Anderson. 2001.  Locus of Feedback Control in Computer-Based Tutoring: Impact on Learning Rate, Achievement and Attitudes. In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ (Seattle, Washington, USA) _(CHI ’01)_. Association for Computing Machinery, New York, NY, USA, 245–252.  https://doi.org/10.1145/365024.365111
  * de Souza et al. [2019] Fábio Rezende de Souza, Francisco de Assis Zampirolli, and Guiou Kobayashi. 2019.  Convolutional Neural Network Applied to Code Assignment Grading.. In _CSEDU (1)_. 62–69.
  * Edwards and Perez-Quinones [2008] Stephen H Edwards and Manuel A Perez-Quinones. 2008.  Web-CAT: automatically grading programming assignments. In _Proceedings of the 13th annual conference on Innovation and technology in computer science education_. 328–328.
  * Eicher and Joyner [2021] Bobbie Lynn Eicher and David Joyner. 2021.  Components of Assessments and Grading at Scale. In _Proceedings of the Eighth ACM Conference on Learning@ Scale_. 303–306.
  * Ertek et al. [2014] Gurdal Ertek, Bengi Tokdil, İbrahim Günaydın, and Aytac Gogus. 2014.  Benchmarking Competitiveness of Top 100 U.S. Universities.  In _Handbook of research on strategic performance management and measurement using data envelopment analysis_ , Ibrahim H. Osman, Abdel Latef Anouze, and Ali Emrouznejad (Eds.). Business Science Reference, Hershey, PA, Chapter 10, 407–425.
  * Forsythe and Wirth [1965] George E Forsythe and Niklaus Wirth. 1965.  Automatic grading programs.  _Commun. ACM_ 8, 5 (1965), 275–278.
  * Haldeman et al. [2018] Georgiana Haldeman, Andrew Tjang, Monica Babeş-Vroman, Stephen Bartos, Jay Shah, Danielle Yucht, and Thu D Nguyen. 2018.  Providing meaningful feedback for autograding of programming assignments. In _Proceedings of the 49th ACM Technical Symposium on Computer Science Education_. 278–283.
  * Hoare [1961] Charles AR Hoare. 1961\.  Algorithm 65: find.  _Commun. ACM_ 4, 7 (1961), 321–322.
  * Hollingsworth [1960] Jack Hollingsworth. 1960\.  Automatic graders for programming classes.  _Commun. ACM_ 3, 10 (1960), 528–529.
  * Impagliazzo and Pears [2018] John Impagliazzo and Arnold Neville Pears. 2018.  The CC2020 project — computing curricula guidelines for the 2020s. In _2018 IEEE Global Engineering Education Conference (EDUCON)_. 2021–2024.  https://doi.org/10.1109/EDUCON.2018.8363484
  * Manzoor et al. [2020] Hamza Manzoor, Amit Naik, Clifford A Shaffer, Chris North, and Stephen H Edwards. 2020.  Auto-Grading Jupyter Notebooks. In _Proceedings of the 51st ACM Technical Symposium on Computer Science Education_. 1139–1144.
  * Nabil et al. [2021] Ramez Nabil, Nour Eldeen Mohamed, Ahmed Mahdy, Khaled Nader, Shereen Essam, and Essam Eliwa. 2021\.  EvalSeer: An Intelligent Gamified System for Programming Assignments Assessment. In _2021 International Mobile, Intelligent, and Ubiquitous Computing Conference (MIUCC)_. IEEE, 235–242.
  * Novak et al. [2019] Matija Novak, Mike Joy, and Dragutin Kermek. 2019.  Source-code similarity detection and detection tools used in academia: a systematic review.  _ACM Transactions on Computing Education (TOCE)_ 19, 3 (2019), 1–37.
  * Oliphant [2006] Travis E Oliphant. 2006\.  _A guide to NumPy_. Vol. 1.  Trelgol Publishing USA.
  * Ottenstein [1976] Karl J Ottenstein. 1976\.  An algorithmic approach to the detection and prevention of plagiarism.  _ACM Sigcse Bulletin_ 8, 4 (1976), 30–41.
  * Pawelczak [2018] Dieter Pawelczak. 2018\.  Benefits and drawbacks of source code plagiarism detection in engineering education. In _2018 IEEE Global Engineering Education Conference (EDUCON)_. IEEE, 1048–1056.
  * Petrík et al. [2017] Juraj Petrík, Daniela Chudá, and Branislav Steinmüller. 2017\.  Source code plagiarism detection: The Unix way. In _2017 IEEE 15th International Symposium on Applied Machine Intelligence and Informatics (SAMI)_. IEEE, 000467–000472.
  * Sarwate et al. [2018] Avneesh Sarwate, Creston Brunch, Jason Freeman, and Sebastian Siva. 2018.  Grading at scale in earsketch. In _Proceedings of the Fifth Annual ACM Conference on Learning at Scale_. 1–4.
  * Skalka et al. [2021] Jan Skalka, Martin Drlik, Lubomir Benko, Jozef Kapusta, Juan Carlos Rodríguez del Pino, Eugenia Smyrnova-Trybulska, Anna Stolinska, Peter Svec, and Pavel Turcinek. 2021\.  Conceptual Framework for Programming Skills Development Based on Microlearning and Automated Source Code Evaluation in Virtual Learning Environment.  _Sustainability_ 13, 6 (2021).  https://doi.org/10.3390/su13063293
  * Sraka and Kaucic [2009] Dejan Sraka and Branko Kaucic. 2009.  Source code plagiarism. In _Proceedings of the ITI 2009 31st international conference on information technology interfaces_. IEEE, 461–466.
  * Striewe and Goedicke [2014] Michael Striewe and Michael Goedicke. 2014.  A review of static analysis approaches for programming exercises. In _International Computer Assisted Assessment Conference_. Springer, 100–113.
  * Taras [2005] Maddalena Taras. 2005\.  Assessment–summative and formative–some theoretical reflections.  _British journal of educational studies_ 53, 4 (2005), 466–478.
  * Traxler [1970] J Traxler. 1970\.  Plagiarism in programming: A review and discussion of the factors.  _WIT Transactions on Information and Communication Technologies_ 12 (1970).
  * Wing [2006] Jeannette M Wing. 2006\.  Computational thinking.  _Commun. ACM_ 49, 3 (2006), 33–35.
  * Winstone and Boud [2020] Naomi E Winstone and David Boud. 2020.  The need to disentangle assessment and feedback in higher education.  _Studies in higher education_ (2020), 1–12.
  * Yulianto and Liem [2014] Susilo Veri Yulianto and Inggriani Liem. 2014.  Automatic grader for programming assignment using source code analyzer. In _2014 International Conference on Data and Software Engineering (ICODSE)_. IEEE, 1–4.