For abelian groups, we label each sub-bucket with an abelian subgroup $M$ of
the codomain, $H$; the sub-bucket $\mathcal{L}_{\psi}^{M}$ consists of all
homomorphisms $\varphi\in\mathcal{L}_{\psi}$ whose image is contained in $M$.

######  Definition 7.10 (Sub-bucket $\mathcal{L}_{\psi}^{M}$ for abelian
groups).

Suppose $G$ is an abelian group. Let $\psi\in\operatorname{aHom}(G,H)$ and
$M\leq H$. The sub-bucket $\mathcal{L}_{\psi}^{M}$ is

$\displaystyle\mathcal{L}_{\psi}^{M}=\\{\varphi\in\mathcal{L}_{\psi}\mid\varphi(G)\leq
M\\}.$

For alternating groups,

we label each sub-bucket with a subgroup $K$ of the domain, $G$; the sub-
bucket $\mathcal{L}_{\psi,K}$ consists of all homomorphisms
$\varphi\in\mathcal{L}_{\psi}$ whose equalizer with $\psi$ contains $K$.

######  Definition 7.11 (Sub-bucket $\mathcal{L}_{\psi,K}$ for alternating
groups).

Suppose $G$ is an alternating group. Let $\psi\in\mathcal{L}$ and $K\leq H$.
The sub-bucket $\mathcal{L}_{\psi,K}$ is

$\displaystyle\mathcal{L}_{\psi,K}=\\{\varphi\in\mathcal{L}\mid
K\leq\operatorname{Eq}(\varphi,\psi)\\}.$

To bound the size of the buckets, we in both cases use the fact that elements
of $\mathcal{L}_{\psi}$ agree with $\psi$ on a subgroup of large density.
Moreover, in abelian groups and alternating groups, subgroups with large
density have small depth. We leverage this in the next lemma. The lemma will
help us bound the number of sub-buckets $\mathcal{L}_{\psi}^{M}$ per bucket in
the abelian case (but we will need to bound the size of each sub-bucket
another way). And, it will help us bound the size of each sub-bucket
$\mathcal{L}_{\psi,K}$ in the alternating case (but we will need to bound the
number of sub-buckets per bucket another way).

The set $S$ in the lemma should be thought of as
$\operatorname{Eq}(f,\varphi)$ for some homomorphism $\varphi$ of interest.

######  Lemma 7.12.

Let $0\leq\lambda<1$. Let $G$ be a finite group, $K\leq G$ a subgroup, and
$S\subseteq G$ a subset. Suppose that $\mu_{G}(S)>\lambda$. Let
$\varepsilon=\mu(S)-\lambda$ and $d=\operatorname{depth}_{G}(K)$. Then,

$\Pr_{s_{1},\ldots,s_{d}\in S}[\mu(\langle
K,s_{1},\dots,s_{d}\rangle)>\lambda]\geq\left(\frac{\varepsilon}{\lambda+\varepsilon}\right)^{d}.$

It follows that

$\Pr_{g_{1},\ldots,g_{d}\in G}[g_{1},\dots,g_{d}\in S\text{ and }\mu(\langle
K,g_{1},\ldots,g_{d}\rangle)>\lambda]\geq\varepsilon^{d}.$

This is proved by repeated application of Bayes’ rule.

###### Proof.

Pick $s_{1},s_{2},s_{3},\dotsc$ independently and uniformly from $S$.

We proceed by induction on $\lvert G:K\rvert$.

Suppose $\mu(K)>\lambda$. Then, $\Pr[\mu(\langle
K,s_{1},\dots,s_{d}\rangle)>\lambda]=1$.

Suppose $\mu(K)\leq\lambda$. Then, with probability
$\displaystyle{\frac{\mu(S\smallsetminus
K)}{\mu(S)}\geq\frac{\varepsilon}{\lambda+\varepsilon}}$, we have that
$s_{1}\notin K$, so $\langle K,s_{1}\rangle>K$, and
$\operatorname{depth}_{G}\langle K,s_{1}\rangle\leq d-1$. Then, by the
induction hypothesis,

$\displaystyle\Pr[\mu(\langle K,s_{1},\dots,s_{d}\rangle)]$
$\displaystyle\geq\Pr[\mu(\langle K,s_{1},\dots,s_{d}\rangle)\mid s_{1}\notin
K]\cdot\Pr[s_{1}\notin K]$ (9)
$\displaystyle\geq\left(\frac{\varepsilon}{\lambda+\varepsilon}\right)^{d-1}\cdot\left(\frac{\varepsilon}{\lambda+\varepsilon}\right).$
(10)

This completes the inductive step. ∎

######  Remark 7.13.

With a little more care in the proof (separating out the case
$\lambda/2<\mu(K)\leq\lambda$), one can prove the stronger conclusion

$\displaystyle\Pr[\mu(\langle
K,s_{1},\dots,s_{d}\rangle)>\lambda]\geq\left(\frac{\frac{1}{2}\lambda+\varepsilon}{\lambda+\varepsilon}\right)^{d-1}\cdot\frac{\varepsilon}{\lambda+\varepsilon}.$
(11)

###  7.5 Bipartite generation-graphs

We retain the notation $G,H,f,\varepsilon,\mathcal{L}$ from the previous
subsection. Let $\Psi\subseteq\operatorname{aHom}(G,H)$ be as defined in Lemma
7.3.

In the case that $G$ is abelian or alternating, we divided the list
$\mathcal{L}$ into buckets $\mathcal{L}_{\psi}$. To bound the size
$\lvert\mathcal{L}\rvert$ of the list, we just need to bound the size
$\lvert\mathcal{L}_{\psi}\rvert$ of each bucket. If we fix $\psi\in\Psi$ and
consider some homomorphism $\varphi\in\mathcal{L}_{\psi}$ that is hidden to
us, we can almost recover $\varphi$ with some decent probability if we have
access to $\psi$ and a few random elements of $\operatorname{Eq}(f,\varphi)$.
By “almost recover,” we mean there is a small list of homomorphisms which
contains $\varphi$.

To make this more precise, we define the following bipartite graph.

######  Definition 7.14.

Let $d$ be a positive integer. We define a bipartite graph $X_{\psi,d}$. The
left vertex set is $V=G^{d}$ and the right vertex set is
$W=\mathcal{L}_{\psi}$. The vertices $(g_{1},\dots,g_{d})\in V$ and
$\varphi\in W$ are adjacent if
$g_{1},\dots,g_{d}\in\operatorname{Eq}(f,\varphi)$ and
$\mu(\langle\operatorname{Eq}(\psi,\varphi),g_{1},\dots,g_{d}\rangle)>\Lambda$.

We will bound $\mathcal{L}_{\psi}$ by applying part (a) of Lemma 5.1 (double
counting) to $X_{\psi,d}$. So, we would like to bound the degree of a left
vertex from above, and the degree of a right vertex from below.

The next lemma bounds below the degree of a right vertex in certain cases, and
will be useful when $G$ is abelian or alternating.

######  Lemma 7.15.

Let $d$ be a positive integer, and $\varphi\in\mathcal{L}_{\psi}$ be a right
vertex of $X_{\psi,d}$ such that
$\operatorname{depth}_{G}\operatorname{Eq}(\psi,\varphi)\leq d$. Then
$\varphi$ is adjacent to at least an $\varepsilon^{d}$ fraction of the left
vertices.

###### Proof.

By Lemma 7.12 with $\lambda=\Lambda$, and $S=\operatorname{Eq}(f,\varphi)$,
and $K=\operatorname{Eq}(\psi,\varphi)$, we have that

$\Pr_{g_{1},\ldots,g_{d}\in
G}[g_{1},\dots,g_{d}\in\operatorname{Eq}(f,\psi)\text{ and
}\mu(\langle\operatorname{Eq}(\psi,\varphi),g_{1},\ldots,g_{d}\rangle)>\lambda]\geq\varepsilon^{d}.$

So, $\varphi$ is adjacent to at least $\varepsilon^{d}$ fraction of the tuples
$(g_{1},\dots,g_{d})$. ∎

We would also like to bound the degree of a left vertex from above. For
abelian groups, we will do this in Section 8.2, in Corollary 8.11. For
alternating groups, we do this by splitting the graph $X_{\psi,d}$ into
subgraphs based on the

sub-buckets $\mathcal{L}_{\psi,K}$ defined in the previous subsection. We will
use the following lemma.

######  Lemma 7.16.

Let $K\leq G$ be a subgroup, $\psi\in\operatorname{Hom}(G,H)$ a homomorphism,
$d$ a nonnegative integer, and $g_{1},\dots,g_{d}\in G$. If $\mu(\langle
K,g_{1},\dots,g_{d}\rangle)>\Lambda$, then there is at most one homomorphism
$\varphi\in\operatorname{Hom}(G,H)$ such that
$K\leq\operatorname{Eq}(\psi,\varphi)$ and
$g_{1},\dots,g_{d}\in\operatorname{Eq}(f,\varphi)$.

###### Proof.

If there were two such homomorphisms $\varphi_{1}$ and $\varphi_{2}$, we would
have that
$K\leq\operatorname{Eq}(\psi,\varphi_{1})\cap\operatorname{Eq}(\psi,\varphi_{2})\leq\operatorname{Eq}(\varphi_{1},\varphi_{2})$,
and
$g_{1},\dots,g_{d}\in\operatorname{Eq}(f,\varphi_{1})\cap\operatorname{Eq}(f,\varphi_{2})\leq\operatorname{Eq}(\varphi_{1},\varphi_{2})$
so $\operatorname{agr}(\varphi_{1},\varphi_{2})\geq\mu(\langle
K,g_{1},\dots,g_{d}\rangle)>\Lambda$, so $\varphi_{1}=\varphi_{2}$. ∎

As an application of Lemma 7.16, we can bound the size of the sub-buckets
$\mathcal{L}_{\psi,K}$ for $K$ of low depth, which will be useful in proving
that alternating groups are universally CombEcon. We do this in the next
corollary. This lemma will also be used when $G$ is a shallow random
generation group (See Section 10).

######  Corollary 7.17 (Sub-bucket bound for low-depth label subgroups).

Let $G$ be a finite group, $H$ a group, $K\leq G$ a subgroup, $f\colon G\to
H$, and $\varepsilon>0$.

Then,

$\lvert\mathcal{L}_{\psi,K}\rvert\leq
1/\varepsilon^{\operatorname{depth}_{G}(K)}.$

###### Proof.

Let $d=\operatorname{depth}_{G}(K)$. Consider the induced subgraph of
$X_{\psi,d}$ with the same left vertex set, and with right vertex set
$\mathcal{L}_{\psi,K}$. By Lemma 7.16, each left vertex has degree at most
$1$. By Lemma 7.15, each right vertex is adjacent to at least an
$\varepsilon^{d}$ fraction of the left vertices. Apply part (a) of Lemma 5.1
(double counting). ∎

We will use this corollary in Section 9.2.

##  8 Homomorphism Codes with finite abelian domain and arbitrary codomain

In this section we show that finite abelian groups are universally
combinatorially and algorithmically economically list-decodable. The key
technical result is Theorem 8.7, which says that there are a small number of
abelian subgroups of the codomain such that every homomorphism in the list
maps into one of these subgroups.

In Section 8.1 we introduce a tool called an _abelian enlargement_. Using this
tool, in Section 8.2 we prove Theorem 8.7 (the key result mentioned in the
previous paragraph) and infer that abelian groups are universally CombEcon. In
Section 8.3 we adapt the algorithm of [DGKS08, GS14], to give an algorithm to
locally list-decode these codes.

In Section 8.4 we describe $\Lambda_{G,H}$ for these and a few other codes,
slightly generalizing a result of Guo [Guo15]. Our proof of CombEcon only uses
that taking a subset of the codomain does not increase $\Lambda$.

We remark that these codes usually cannot be list-decoded beyond radius
$1-(\Lambda_{G,H}+\varepsilon)$ (see Remark 1.5).

###  8.1 Abelian enlargements

Throughout this section, let $G$ be a finite abelian group, and $H$ a group
(finite or infinite).

To prove that abelian groups are universally CombEcon, we will follow the
outline given in Section 7.4. That is, we divide the list
$\mathcal{L}=\mathcal{L}(\operatorname{aHom}(G,H),f,\Lambda+\varepsilon$ into
buckets $\mathcal{L}_{\psi}$, and then subdivide each bucket into sub-buckets
$\mathcal{L}_{\psi}^{M}$ for a small number of abelian subgroups $M\leq H$.
(Actually, we will use $\operatorname{Hom}$ in place of $\operatorname{aHom}$,
but it does not matter by Lemma 5.26.)

To select the subgroups $M$, we introduce an operation that we call an
_abelian enlargement_. In Section 8.2, we will use this operation in our proof
that abelian groups are universally CombEcon. For a subset $T$ and a finite
abelian subgroup $B$ of a group $H$, the abelian $B$-enlargement of $T$ in $H$
is the group generated by $T$ along with every element of $B$ that commutes
with $T$.

If

$\varphi,\psi\in\operatorname{Hom}(G,H)$ are homomorphisms, then the abelian
$\psi(G)$-enlargement of $\varphi(G)$ will certainly still include
$\varphi(G)$. But also, if $\varphi$ and $\psi$ have large agreement, then
most of $\varphi(G)$ is contained in $\psi(G)$, so even if we take a single
element of $\varphi(G)$, then when we enlarge it by $\psi(G)$ it is likely
that the result will already contain all of $\varphi(G)$.

This will help us bound the number of subgroups $M\leq H$ we need, and thus
the number of sub-buckets.

For any $\varphi$ in the bucket $\mathcal{L}_{\psi}$,

its image is likely to be contained

in the enlargement by $\psi(G)$ of a single random element of $f(G)$.

This is the method by which we choose our subgroups $M$.

######  Definition 8.1.

For $H$ a group, $B\leq H$ a subgroup, and $T\subseteq H$ a subset, define the
abelian $B$-enlargement of $T$ in $H$ to be

$\operatorname{enl}_{B}(T)=\langle T,C_{H}(T)\cap B\rangle,$

where $C_{H}(T)$ denotes the centralizer of $T$ in $H$.

For $h\in H$, we may write $\operatorname{enl}_{B}(h)$ in place of
$\operatorname{enl}_{B}(\\{h\\})$.

We note that if $\langle T_{1}\rangle=\langle T_{2}\rangle$, then
$\operatorname{enl}_{B}(T_{1})=\operatorname{enl}_{B}(T_{2})$.

######  Lemma 8.2.

For $B\leq H$ a finite abelian subgroup and $T\subseteq H$ a set such that
$\langle T\rangle$ is a finite abelian group, $\operatorname{enl}_{B}(T)$ is a
finite abelian group.

In fact, we will only be concerned with the case that $B\leq H$ is a finite
abelian subgroup, and $\langle T\rangle$ is abelian.

###### Proof.

Every element of $T$ commutes with every element of $C_{H}(T)$ by the
definition of the centralizer. So, $\operatorname{enl}_{B}(T)$ is the direct
product of $\langle T\rangle$ and $C_{H}(T)\cap B$. The group $\langle
T\rangle$ is finite abelian by assumption, and $C_{H}(T)\cap B$ is finite
abelian because it is a subgroup of $B$. So, $\operatorname{enl}_{B}(T)$ is a
finite abelian group.

∎

######  Lemma 8.3.

For $B$ and $T$ as above, and $U\subseteq\operatorname{enl}_{B}(T)$, we have
that $\operatorname{enl}_{B}(T)=\operatorname{enl}_{B}(T\cup U)$.

###### Proof.

First, we show that $\operatorname{enl}_{B}(T)\leq\operatorname{enl}_{B}(T\cup
U)$. Since $\operatorname{enl}_{B}(T)$ is abelian, we have that

$C_{H}(T)\cap B\leq\operatorname{enl}_{B}(T)\leq
C_{H}(\operatorname{enl}_{B}(T))\leq C_{H}(U).$

So,

$C_{H}(T)\cap B\leq C_{H}(T)\cap C_{H}(U)\cap B=C_{H}(T\cup U)\cap
B\leq\operatorname{enl}_{B}(T\cup U).$

Since also $T\subseteq\operatorname{enl}_{B}(T\cup U)$, we have that
$\operatorname{enl}_{B}(T)\leq\operatorname{enl}_{B}(T\cup U)$.

Next, we show that $\operatorname{enl}_{B}(T\cup
U)\leq\operatorname{enl}_{B}(T)$. We have that
$T\subseteq\operatorname{enl}_{B}(T)$, that
$U\subseteq\operatorname{enl}_{B}(T)$, and $C_{H}(T\cup U)\cap B\leq
C_{H}(T)\cap B\leq\operatorname{enl}_{B}(T)$. So,
$\operatorname{enl}_{B}(T\cup U)=\langle T\cup U,C_{H}(T\cup U)\cap
B\rangle\leq\operatorname{enl}_{B}(T)$. ∎

######  Proposition 8.4.

Let $\varphi,\psi\in\operatorname{Hom}(G,H)$ and $A\subseteq G$ such that
$\langle A,\operatorname{Eq}(\psi,\varphi),\ker\varphi\rangle=G$.

Then
$\operatorname{enl}_{\psi(G)}(\varphi(A))=\operatorname{enl}_{\psi(G)}(\varphi(G))$.

###### Proof.

Since $G$ is finite abelian, so are $\varphi(G)$ and $\psi(G)$. Let
$B=\psi(G)$. Let $T=\varphi(A)$. Let
$U=\varphi(\operatorname{Eq}(\psi,\varphi))$. Since $T,U\subseteq\varphi(G)$,
and $\varphi(G)$ is abelian, $U\leq C_{H}(T)$. And, since
$U=\psi(\operatorname{Eq}(\psi,\varphi))$, we have that $U\leq\psi(T)=B$.
Thus, $U\leq C_{H}(T)\cap B\leq\operatorname{enl}_{B}(T)$.

Also, $\langle T\cup U\rangle=\langle
T,U,1\rangle=\langle\varphi(A),\varphi(\operatorname{Eq}(\psi,\varphi)),\varphi(\ker\varphi)\rangle=\varphi(\langle
A,\operatorname{Eq}(\psi,\varphi),\ker\varphi\rangle)=\varphi(G)$.

Therefore, by Lemma 8.3,

$\operatorname{enl}_{\psi(G)}(\varphi(A))=\operatorname{enl}_{B}(T)=\operatorname{enl}_{B}(T\cup
U)=\operatorname{enl}_{B}(\langle T\cup
U\rangle)=\operatorname{enl}_{\psi(G)}(\varphi(G)).$ (12)

∎

######  Corollary 8.5.

Let

$\varphi$, $\psi$, and $A$ be as above. Then
$\varphi(G)\leq\operatorname{enl}_{\psi(G)}(\varphi(A))$.

###  8.2 Combinatorial list-decodability, finite abelian to anything

In this section, we establish that finite abelian groups are universally
CombEcon.

Throughout this section, let $G$ be a finite abelian group, and $H$ an
arbitrary group (finite or infinite). Let $f\colon G\to H$ be a received word.
Let $\varepsilon>0$. Let
$\mathcal{L}=\mathcal{L}(\operatorname{Hom}(G,H),f,\Lambda+\varepsilon)$ be
the list (note that in this section we deal with the code of homomorphisms,
rather than affine homomorphisms; however, we can convert between the two; see
Section 5.5). The list $\mathcal{L}$ is divided into buckets
$\mathcal{L}_{\psi}$ for $\psi\in\Psi$, where $\Psi$ is as in Lemma 7.3.

We will see that there is a small set of abelian subgroups $M\leq H$ such that
every $\varphi\in\mathcal{L}$ has its image in some $M$.

Dinur, Grigorescu, Kopparty, and Sudan [DGKS08] proved that
$\operatorname{aHom}(G,H)$ is CombEcon (and in fact, AlgEcon) for all finite
abelian groups $G$ and $H$.

######  Theorem 8.6 (DGKS 2008).

The class $\operatorname{\mathfrak{Abel}}\times\operatorname{\mathfrak{Abel}}$
of pairs of abelian groups is CombEcon.

The following theorem, combined with the DGKS result, lets us conclude that
$\operatorname{Hom}(G,H)$ (and thus $\operatorname{aHom}(G,H)$) is CombEcon.

######  Theorem 8.7.

There exists a set $\mathcal{A}$ of finite abelian subgroups of $H$ with
$\displaystyle{\lvert\mathcal{A}\rvert\leq\frac{1}{4(\Lambda+\varepsilon)\varepsilon^{2}}+\frac{1}{\varepsilon}}$
such that for all $\varphi\in\mathcal{L}$,

there is $M\in\mathcal{A}$ such that $\varphi(G)\leq M$.

######  Corollary 8.8.

Finite abelian groups are universally CombEcon. Specifically, let $C$ be a
constant such that

$\ell(\operatorname{aHom}(G,H),\Lambda+\varepsilon)\leq(\frac{1}{\varepsilon})^{C}$
for $G,H$ finite abelian groups. Then

$\ell(\operatorname{aHom}(G,H),\Lambda+\varepsilon)\leq
O((\frac{1}{\varepsilon})^{C+4})$ for $G$ a finite abelian group and $H$ and
arbitrary group.

By [GS14, BGSW18], the constant $C$ is approximately $105$.

###### Proof of Corollary 8.8.

Let $\mathcal{A}$ be the collection of subgroups of $H$ guaranteed by Theorem
8.7. Then,

$\mathcal{L}\subseteq\bigcup_{M\in\mathcal{A}}\mathcal{L}(\operatorname{Hom}(G,M),f,\Lambda+\varepsilon)$
(on the right hand side we let $f$ be redefined arbitrarily at points in its
domain that do not map to $M$). So,

$\lvert\mathcal{L}\rvert\leq\sum_{M\in\mathcal{A}}\ell(\operatorname{Hom}(G,M),\Lambda+\varepsilon)\leq\left(\frac{1}{4(\Lambda+\varepsilon)\varepsilon^{2}}+\frac{1}{\varepsilon}\right)\left(\frac{1}{\varepsilon}\right)^{C}.$

We then apply Lemma 5.26. ∎

In the remainder of this subsection, we prove Theorem 8.7.

Recall our strategy from Sections 7.4 and 7.5 of dividing the list
$\mathcal{L}$ into buckets $\mathcal{L}_{\psi}$, and bounding the size of each
bucket by considering the graph $X_{\psi,d}$. We will now carry out this
strategy. We will use $d=1$. We next bound the degree of each right vertex.

######  Lemma 8.9.

Let $\psi\in\Psi$. Each right vertex of $X_{\psi,1}$ is adjacent to at least
an $\varepsilon$ fraction of the left vertices.

###### Proof.

We know that $1/\Lambda$ is the least integer that divides $\lvert G:N\rvert$,
where $N$ is the $(G,H)$-irrelevant kernel.

For all $\varphi\in\mathcal{L}_{\psi}$, we have that
$\operatorname{Eq}(\psi,\varphi)$ contains the irrelevant kernel and has
density greater than $\Lambda^{2}$, so has depth at most $1$. We apply Lemma
7.15. ∎

The next lemma tells us about the connected components of $X_{\psi,1}$. It
also helps us bound the degree of a left vertex via the DGKS result.

######  Lemma 8.10.

Let $\psi\in\Psi$. Let $g_{1}\in G$ be a left vertex of $X_{\psi,1}$, and
$\varphi\in\mathcal{L}_{\psi}$ a right vertex. If $g_{1}$ is adjacent to
$\varphi$ then
$\operatorname{enl}_{\psi(G)}(f(g_{1}))=\operatorname{enl}_{\psi(G)}(\varphi(G))$.

###### Proof.

We have $g_{1}\in\operatorname{Eq}(f,\varphi)$ and
$\langle\operatorname{Eq}(\psi,\varphi),g_{1}\rangle$ has density greater than
$\Lambda$, so is equal to $G$. So, by Proposition 8.4,
$\operatorname{enl}_{\psi(G)}(f(g_{1}))=\operatorname{enl}_{\psi(G)}(\varphi(g_{1}))=\operatorname{enl}_{\psi(G)}(\varphi(G))$.
∎

Lemma 8.10 allows us to associate an abelian subgroup of $H$ to each connected
component of $X_{\psi,1}$.

######  Corollary 8.11.

Each left vertex of of $X_{\psi,1}$ has degree at most
$(\frac{1}{\varepsilon})^{C}$.

###### Proof.

All the neighbors of $g_{1}$ are elements of
$\mathcal{L}(\operatorname{Hom}(G,M),f,\Lambda+\varepsilon)$ for
$M=\operatorname{enl}_{\psi(G)}(f(g_{1}))$. We apply the DGKS result. ∎

######  Remark 8.12.

We can now prove Corollary 8.8, bypassing Theorem 8.7, by applying part (a) of
Lemma 5.1 (double counting). We can use Lemma 8.9 to bound the degree of a
right vertex, and

Corollary 8.11 to bound the degree of a left vertex.

We need one more lemma before we prove Theorem 8.7.

######  Lemma 8.13.

Let $\psi\in\Psi$. There is a set $\mathcal{A}_{\psi}$ of finite abelian
subgroups of $H$ with
$\lvert\mathcal{A}_{\psi}\rvert\leq\frac{1}{\varepsilon}$ such that for all
$\varphi\in\mathcal{L}_{\psi}$, there is $M\in\mathcal{A}_{\psi}$ for which
$\varphi(G)\leq M$.

###### Proof.

Let
$\mathcal{A}_{\psi}=\\{\operatorname{enl}_{\psi(G)}(\varphi(G))\mid\varphi\in\mathcal{L}_{\psi}\\}$,
which is a set of finite abelian subgroups of $H$ by Lemma 8.2. By Lemma 8.10,
we can associate an abelian subgroup to each connected component of
$X_{\psi,1}$. Each element of $\mathcal{A}_{\psi}$ is associated to at least
one connected component that contains a right vertex. By Lemma 8.9, there are
at most $1/\varepsilon$ such components, so

$\lvert\mathcal{A}_{\psi}\rvert\leq 1/\varepsilon$. ∎

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

###### Proof of Theorem 8.7.

Let $\mathcal{A}_{\psi}$ be as in Lemma 8.13. Let
$\mathcal{A}=\bigcup_{\psi\in\Psi}\mathcal{A}_{\psi}$. By Lemma 7.3,
$\lvert\Psi\rvert\leq\frac{1}{4(\Lambda+\varepsilon)\varepsilon}+1$. By Lemma
8.13, $\lvert\mathcal{A}_{\psi}\rvert\leq\frac{1}{\varepsilon}$. So,
$\lvert\mathcal{A}\rvert\leq\frac{1}{4(\Lambda+\varepsilon)\varepsilon^{2}}+\frac{1}{\varepsilon}$.

For $\varphi\in\mathcal{L}$, we have that $\varphi\in\mathcal{L}_{\psi}$ for
some $\psi\in\Psi$, and so the image of $\varphi$ is in
$\operatorname{enl}_{\psi(G)}(\varphi(G))\in\mathcal{A}_{\psi}\subseteq\mathcal{A}$.

∎

###  8.3 Algorithm

For $G$ a finite abelian group given explicitly by a primary decomposition,
and $H$ a group with black-box access, we can locally list-decode
$\operatorname{aHom}(G,H)$ using essentially the same algorithm as the one by
Dinur Grigorescu, Kopparty, and Sudan in Section 5 of [DGKS08]. We make only
slight modifications. Thus, such codes are AlgEcon.

######  Theorem 8.14.

Let $\mathfrak{D}$ be the class of pairs $(G,H)$ where $G$ is an abelian group
given explicitly by an primary decomposition, and $H$ is a group with black-
box access. Then there is an algorithm to locally list-decode $\mathfrak{D}$
in time $\operatorname{poly}(\log\lvert G\rvert\cdot\frac{1}{\varepsilon})$.

We assume black-box access to $H$. We do not assume black-box access to $G$;
if only black-box access were assumed, then for $p$ a prime, it would take
$p+1$ queries to a group to determine whether the group were isomorphic to
$\mathbb{Z}_{p}$ or $\mathbb{Z}_{p}^{2}$. Like [DGKS08], we assume that $G$ is
given explicitly by an primary decomposition.

We assume that we have an algorithm determining $\Lambda_{G,H}$, although this
assumption can be removed.

Next, [DGKS08] reduces to the case where $H=\mathbb{Z}_{p^{r}}$. We don’t make
this reduction. We let $p$ be the prime such that $\Lambda=\frac{1}{p}$. Every
mention of $\mathbb{Z}_{p^{r}}$ should be replaced by $H$. As in their
algorithm, we take $G=G_{1},\dots,G_{k}$, with each
$G_{i}=\mathbb{Z}_{p_{i}^{r_{i}}}$. We order the $G_{i}$ such that $p_{1}=p$.
For them, the only important coordinates are the ones where $p_{i}=p$, but for
our purposes, instances of $\mathbb{Z}_{p^{r_{i}}}$ should be replaced with
$\mathbb{Z}_{p_{i}^{r_{i}}}$.

In the algorithm Extend of [DGKS08], the statement “If $c_{1}-c_{2}$ is not
divisible by $p$” should be replaced with “If $c_{1}-c_{2}$ is not divisible
by $p_{i}$, and if $f(y_{1},c_{1},s)$ and $f(y_{2},c_{2},s)$ commute with each
other and with $\varphi(e_{1}),\dots,\varphi(e_{i-1})$”. Here $e_{j}$ denotes
a generator of $G_{j}$. The system of equations that follows should be solved
under the assumption that the order of $a$ divides $p_{i}^{r_{i}}$.

We note that when solving the system of equations in Extend, we are working in
an abelian subgroup of $H$. Actually, even this does not matter; we can solve
the system of equations without assuming elements of $H$ commute.

###  8.4 $\Lambda_{G,H}$ when $G$ or $H$ is solvable

We give a combinatorial description of $\Lambda_{G,H}$ when $G$ is a finite
abelian group and $H$ is an arbitrary group.

######  Proposition 8.15.

Let $G$ be a finite abelian group and $H$ a group. Then $\Lambda_{G,H}=1/p$,
where $p$ is the smallest prime number such that $p$ divides $\lvert G\rvert$
and $H$ has an element of order $p$. If no such $p$ exists, then
$\lvert\operatorname{Hom}(G,H)\rvert=1$ and $\Lambda_{G,H}=0$.

This proposition is a special case of the following theorem, which describes
$\Lambda_{G,H}$ when $G$ or $H$ is a solvable group. This is a slight
generalization of a result of Guo [Guo15, Theorem 1.1].

######  Theorem 8.16.

Let $G$ be a finite group and $H$ a group, such that at least one of $G$ or
$H$ is solvable. Then $\Lambda_{G,H}=1/p$, where $p$ is the smallest prime
number such that $G$ has a normal subgroup of index $p$ and $H$ has an element
of order $p$. If no such $p$ exists, then
$\lvert\operatorname{Hom}(G,H)\rvert=1$ and $\Lambda_{G,H}=0$.

We will prove Theorem 8.16 in this subsection. Guo proved Theorem 8.16 in the
case where $H$ is finite, and either $G$ is solvable or $H$ is nilpotent.

Our proof relies on the following lemma about
$\bigcap_{\varphi\in\operatorname{Hom}(G,H)}\ker\varphi$.

######  Lemma 8.17.

Let $G$ be a finite group and $H$ a group. Let
$K=\bigcap_{\varphi\in\operatorname{Hom}(G,H)}\ker\varphi$. Then every prime
factor of $\lvert G:K\rvert$ is the order of an element of $H$.

###### Proof.

Consider any prime factor $p$ of $\lvert G:K\rvert$. Then there is $g\in G$
such that $gK$ has order $p$ in $G/K$. Since $g\notin K$, there is
$\varphi\in\operatorname{Hom}(G,H)$ such that $g\notin\ker\varphi$. We have
$g^{p}\in K$, so $\varphi(g)^{p}\in\varphi(K)=1$, so $\lvert\varphi(g)\rvert$
divides $p$. Since $\varphi(g)\neq 1$, we have $\lvert\varphi(g)\rvert=p$. ∎

We also use the following well-known fact and a theorem by Berkovich (see
[Isa08]).

######  Fact 8.18.

In a solvable group, a normal subgroup is a maximal normal subgroup if and
only if it has prime index.

######  Theorem 8.19 (Berkovich).

Let $G$ be a finite solvable group and $K$ a proper subgroup of smallest
index. Then $K\trianglelefteq G$.

Next, we prove Theorem 8.16 in the case when $G$ is solvable. Guo [Guo15,
Theorem 5.5] proved this in the case that also $H$ is finite.

Guo’s proof can be modified slightly to also accommodate infinite groups. We
include a compact proof for completeness.

###### Proof of Theorem 8.16 in the case where $G$ is solvable.

Let $K=\bigcap_{\varphi\in\operatorname{Hom}(G,H)}\ker\varphi$. If
$\Lambda>0$, then there is a nontrivial homomorphism
$\varphi\in\operatorname{Hom}(G,H)$. Then $\ker\varphi$ is a proper normal
subgroup of $G$, so is contained in a maximal normal subgroup $M$. By Fact
8.18, $\lvert G:M\rvert$ is prime, and since $M\geq\ker\varphi\geq K$, we have
that $\lvert G:M\rvert$ divides $\lvert G:K\rvert$. So, by Lemma 8.17, we have
that $H$ has an element of order $\lvert G:M\rvert$. So, if $\Lambda>0$, then
$p$ exists.

Henceforth, assume $p$ exists. Let $N$ be a normal subgroup of $G$ of index
$p$, and $h$ an element of $H$ of order $p$. We show that $\Lambda\geq 1/p$ by
exhibiting a pair of homomorphisms that achieve this agreement. Let
$\varphi_{1}\colon G\to H$ be the trivial homomorphism. Since $\lvert
G/N\rvert=\lvert\langle h\rangle\rvert=p$ prime, there is a group isomorphism
$G/N\to\langle h\rangle$. This lifts to a group homomorphism
$\varphi_{2}\colon G\to\langle h\rangle$. Then
$\operatorname{Eq}(\varphi_{1},\varphi_{2})=N$, so
$\operatorname{agr}(\varphi_{1},\varphi_{2})=1/p$. So, $\Lambda_{G,H}\geq
1/p$.

We next show that $\Lambda\leq 1/p$. Since $N=\ker\varphi_{2}\geq K$, we have
that $N/K\trianglelefteq G/K$ and $\lvert G/K:N/K\rvert=p$. Furthermore, we
claim that $N/K$ is a proper normal subgroup of smallest prime index in $G/K$
— if there were a proper normal $\hat{N}/K$ of prime index $q<p$ (with
$K\leq\hat{N}\leq G$), then $\hat{N}$ would be a normal subgroup of $G$ of
index $q$, and $H$ would have an element of order $q$ by Lemma 8.17, which
would contradict the definition of $p$. By Fact 8.18, $N/K$ is in fact a
proper normal subgroup of smallest index in $G/K$ (removing “prime”). By
Theorem 8.19, we further have that $N/K$ is a proper subgroup of smallest
index in $G/K$ (removing “normal”). Thus, $N$ is the has the smallest index of
any subgroup of $G$ that contains $K$. Any equalizer of two homomorphisms in
$\operatorname{Hom}(G,H)$ contains $K$, so no equalizer can have smaller index
than $N$. So, $\Lambda\leq\mu(N)=1/p$. ∎

To prove Theorem 8.16 in the case where $H$ is solvable, we use the following
fact.

######  Lemma 8.20.

Let $G$ be a group and $H$ a solvable group. Let
$K=\bigcap_{\varphi\in\operatorname{Hom}(G,H)}\ker\varphi$. Then $G/K$ is
solvable.

###### Proof.

For each $\varphi\in\operatorname{Hom}(G,H)$, we have that $\varphi(G)$ is
solvable with derived length at most the derived length of $H$. Also,
$G/\ker\varphi\cong\varphi(G)$. So,
$\prod_{\varphi\in\operatorname{Hom}(G,H)}G/\ker\varphi$ is a direct product
of solvable subgroups with bounded derived length, so is solvable. Let
$\psi\colon G\to\prod_{\varphi\in\operatorname{Hom}(G,H)}G/\ker\varphi$ be the
projection onto each coordinate. Then $\ker\psi=K$. And, $\psi(G)$ is a
subgroup of a solvable group, so is solvable. Thus,
$G/K=G/\ker\psi\cong\psi(G)$ is solvable. ∎

We can now prove Theorem 8.16 in the case where $H$ is solvable.

###### Proof of Theorem 8.16 in the case where $H$ is solvable.

Let $K=\bigcap_{\varphi\in\operatorname{Hom}(G,H)}\ker\varphi$. Let $p$ be the
smallest prime divisor of $\lvert G\rvert$ such that $G$ has a normal subgroup
of index $p$ and $H$ has an element of order $p$. If $N$ is a normal subgroup
of prime index and $H$ contains an element $h$ of order $\lvert G:N\rvert$,
then $K\leq N$, since the isomorphism $G/N\to\langle h\rangle$ lifts to a
homomorphism $G\to\langle h\rangle$ with kernel $N$. So, $p$ is the smallest
prime index of a normal subgroup of $G$ that contains $K$. So, $p$ is the
smallest prime index of a normal subgroup of $G/K$.

We have that $G/K$ is solvable by Lemma 8.20. So, the case of Theorem 8.16 in
which the domain is solvable, we have that $\Lambda_{G/K,H}=1/p$. Then, by
Lemma 5.17, we have $\Lambda_{G,H}=\Lambda_{G/K,H}=1/p$. ∎

##  9 Alternating domain, combinatorial list-decoding

In this section, we will find that homomorphism codes with alternating domain
are CombEcon. The exact constant is stated in Theorem 9.7. We remark that the
constant in the $\operatorname{poly}(1/\varepsilon)$-bound on list size can be
improved using the SRG methods of Section 10. The proof here utilizes the
sphere packing bound, the sub-bucket bound, and a previous result on length of
subgroup chains in symmetric groups [Bab86], which do most of the heavy
lifting.

First, in Section 9.1, we present some background on the structure of
alternating groups. In Section 9.2, we present a corollary to the sphere
packing bound, Lemma 7.3. In Section 9.3 we show that $\Lambda_{A_{n},H}$ can
only take the values $1/n$ and $1/\binom{n}{2}$ and prove the claim that
$\operatorname{\mathfrak{Alt}}\times\operatorname{\mathfrak{Groups}}$ is
CombEcon. Section 9.4 addresses the list-decoding radius of homomorphism codes
with alternating domain, by exhibiting a “blowup” in list size when agreement
is exactly $\Lambda$, or when radius is $(1-\Lambda)$.

###  9.1 Background on structure of alternating groups

For a set $\Omega$, let $\operatorname{Alt}(\Omega)$ denote the alternating
group on $\Omega$. Similarly, let $\operatorname{Sym}(\Omega)$ denote the
symmetric group on $\Omega$. We denote $A_{n}=\operatorname{Alt}([n])$ and
$S_{n}=\operatorname{Sym}([n])$.

Let $G\leq\operatorname{Sym}(\Omega)$. For $\pi\in G$ and $x\in\Omega$, we
denote by $x^{\pi}$ the action of $\pi$ on $x$. For $x\in\Omega$, denote by
$G_{x}=\\{\pi\in G\mid x^{\pi}=x\\}$ the point stabilizer of $x$. Let
$\Delta\subseteq\Omega$. Denote by $G_{(\Delta)}=\\{\pi\in G\mid(\forall
x\in\Delta)(x^{\pi}=x)\\}$ the pointwise stabilizer of $\Delta$. Denote by
$G_{\\{\Delta\\}}=\\{\pi\in G\mid\Delta^{\pi}=\Delta\\}$ the setwise
stabilizer of $\Delta$, where $\Delta^{\pi}:=\\{x^{\pi}:x\in\Delta\\}$.

We present a few useful structural results for alternating and symmetric
groups. The following theorem, due to Liebeck (see [DM96, Theorem 5.2A]),
describes the large subgroups of $A_{n}$.

######  Theorem 9.1 (Jordan-Liebeck).

Let $n\geq 10$ and let $r$ be an integer with $1\leq r<n/2$. Suppose that
$K\leq A_{n}$ has index $\lvert A_{n}:K\rvert<\binom{n}{r}$. Then, for some
$\Delta\subseteq[n]$ with $\lvert\Delta\rvert<r$, we have
$(A_{n})_{(\Delta)}\leq K\leq(A_{n})_{\\{\Delta\\}}$.

We will need the following result from [Bab86], which describes the length of
subgroup chains.

######  Theorem 9.2 (Babai).

The length of any subgroup chain in $S_{n}$ is at most $2n-3$.

######  Corollary 9.3.

The length of every subgroup chain between $A_{n-k}$ and $S_{n}$ is at most
$2k$.

###  9.2 Sphere packing by low-depth subgroups

We present a consequence (Lemma 9.6) of the sphere packing bound (Lemma 7.3),
which we will use to prove that alternating groups are universally CombEcon.
This lemma bounds the list size in terms of a “starting set” of subgroups and
the subgroup depth of its members. This approach depends very little on the
codomain $H$.

Throughout this section, we let $G$ be a finite group, $H$ a group (finite or
infinite), $\Lambda=\Lambda_{G,H}$ the maximum agreement, $f\colon G\to H$ a
received word, $\varepsilon>0$ a real,
$\mathcal{L}=\mathcal{L}(\operatorname{aHom}(G,H),f,\Lambda+\varepsilon)$ the
list, and $\Psi\subseteq\operatorname{aHom}(G,H)$ as defined in Lemma 7.3.

Recall our strategy for proving CombEcon using the Sphere Packing Lemma — We
divided the list $\mathcal{L}$ into buckets $\mathcal{L}_{\psi}$ for
$\psi\in\Psi$,

where

$\mathcal{L}_{\psi}=\\{\varphi\in\mathcal{L}(\operatorname{aHom}(G,H),f,\Lambda+\varepsilon)\mid\operatorname{agr}(\psi,\varphi)>\Lambda^{2}\\}.$

We then split the bucket $\mathcal{L}_{\psi}$ into further _sub-buckets_
according to the location of agreement with $\psi$. Each sub-bucket of
$\mathcal{L}_{\psi}$ is labeled by a subgroup $K$ of $G$ which we call the
_label subgroup_. We defined $\mathcal{L}_{\psi,K}\subseteq\mathcal{L}_{\psi}$
to be the subset of homomorphisms whose equalizer with $\psi$ contain $K$;
that is,

$\displaystyle\mathcal{L}_{\psi,K}=\\{\varphi\in\mathcal{L}_{\psi}\mid
K\leq\operatorname{Eq}(\varphi,\psi)\\}.$

We concern ourselves now with the the set of label subgroups; we call such a
set a _starting set_.

Intuitively, a set $\mathcal{S}$ of subgroups is a starting set if the upper
range of the subgroup lattice of $G$ contains only supergroups of elements in
$\mathcal{S}$.

With an appropriate notion of “upper range,” these starting sets form a
sufficient set of label subgroups so that the sub-buckets
$\mathcal{L}_{\psi,K}$ cover the bucket $\mathcal{L}_{\psi}$ (see Remark 9.5).

######  Definition 9.4 ($(G,\lambda)$-starting-set).

Let $\mathcal{S}$ be a set of subgroups of $G$. Let $\lambda\in(0,1)$. We say
that $\mathcal{S}$ is a $(G,\lambda)$-starting-set if

$(\forall K\leq G)(\mu_{G}(K)>\lambda\Rightarrow(\exists
S\in\mathcal{S})(S\leq K)).$

######  Remark 9.5.

Suppose that $\mathcal{S}$ is a $(G,\Lambda^{2})$-starting set. Then, for any
$f:G\rightarrow H$ and $\psi\in\operatorname{aHom}(G,H)$,

$\displaystyle\mathcal{L}_{\psi}=\bigcup_{K\in\mathcal{S}}\mathcal{L}_{\psi,K}.$
(13)

Combining this with the bucket-splitting lemma (Lemma 7.9),

$\displaystyle\mathcal{L}=\bigcup_{\psi\in\Psi}\bigcup_{K\in\mathcal{S}}\mathcal{L}_{\psi,K}.$
(14)

This allows us to use our bound on $\mathcal{L}_{\psi,K}$ from Corollary 7.17
to bound the size of the list.

######  Lemma 9.6 (Sphere packing via low-depth subgroups).

Let $G$ be a finite group, $H$ a group, and $\varepsilon>0$. Let $\mathcal{S}$
be a $(G,\Lambda^{2})$-starting-set. Then,

$\ell(\operatorname{Hom}(G,H),\Lambda+\varepsilon)\leq\left(\frac{1}{4(\Lambda+\varepsilon)\varepsilon}+1\right)\cdot\sum_{K\in\mathcal{S}}1/\varepsilon^{\operatorname{depth}(K)}.$
(15)

###### Proof.

By Remark 9.5, we have that
$\lvert\mathcal{L}\rvert\leq\sum_{\varphi\in\Phi}\sum_{K\in\mathcal{S}}\lvert\mathcal{L}_{\psi,K}\rvert$.
By Lemma 7.3,
$\lvert\Psi\rvert\leq\frac{1}{4(\Lambda+\varepsilon)\varepsilon}$, and by
Corollary 7.17, $\lvert\mathcal{L}_{\psi,K}\rvert\leq
1/\varepsilon^{\operatorname{depth}(K)}$. ∎

We will use Lemma 9.6 in the proof that alternating groups are universally
CombEcon.

###  9.3 Proof $A_{n}$ is universally CombEcon

We prove that $A_{n}$ is CombEcon by proving Theorem 9.7 below, which states a
constant for the CombEcon claim. (This constant is improved via the methods of
SRG groups in Section 10.)

######  Theorem 9.7.

For every group $H$, integer $n\geq 38$ and $\varepsilon>0$, we find that

$\ell(\operatorname{Hom}(A_{n},H),\Lambda_{A_{n},H}+\varepsilon)\leq
1/\varepsilon^{16}.$

###### Proof of Theorem 9.7.

By Lemma 4.27, we find that $\Lambda^{2}\geq 1/{n\choose 2}^{2}\geq
1/{n\choose 5}$. We use Lemma 9.6.

We first define a starting set

$\mathcal{S}=\\{(A_{n})_{(\Delta)}:\Delta\subseteq[n],\lvert\Delta\rvert=5\\}.$

That $\mathcal{S}$ is an $(A_{n},\Lambda^{2})$-starting-set follows by Jordan-
Liebeck, Theorem 9.1. By Corollary 9.3, we find that
$\operatorname{depth}_{A_{n}}(K)\leq 2\cdot 5-2=8$ for all $K\in\mathcal{S}$.
We assume $\varepsilon^{2}<2\Lambda$ by Lemma 7.6. Since
$\lvert\mathcal{S}\rvert={n\choose
5}<(\binom{n}{2}/2)^{3}=(\Lambda/2)^{3}<1/\varepsilon^{6}$, Theorem follows
from Lemma 9.6. ∎

###  9.4 Upper bound on list-decoding radius

We showed in Section 9.3 that
$\operatorname{\mathfrak{Alt}}\times\operatorname{\mathfrak{Groups}}$, and all
of its subclasses, have list-decoding radius greater than
$1-(\Lambda+\varepsilon)$ for all $\varepsilon>0$.

In contrast,
$\operatorname{\mathfrak{Alt}}\times\operatorname{\mathfrak{Groups}}$ and many
of its subclasses have list-decoding radius at most $1-\Lambda$. In this
section, we demonstrate such a subclass. The number of homomorphisms within a
closed ball of radius $1-\Lambda$ of a received word will be exponential in
$\log\lvert G\rvert$ and $\log\lvert H\rvert$. We note that $\lvert
H\rvert\geq\lvert G\rvert$ unless $\Lambda=0$.

######  Proposition 9.8.

For any $n$, and $\lambda\in\\{1/n,1/\binom{n}{2}\\}$, there exists a finite
group $H_{n}$ such that $\Lambda_{A_{n},H_{n}}=\lambda$ and

$\displaystyle\ell(\operatorname{Hom}(A_{n},H_{n}),\Lambda)=2^{\Omega(n)}\geq
2^{\Omega\left(\sqrt[3]{\log\lvert H\rvert}\right)}.$ (16)

Moreover, for any fixed $n\geq 10$, and any integer $M$, there is a finite
group $H$ such that

$\displaystyle\ell(\operatorname{Hom}(A_{n},H),\Lambda)\geq M.$ (17)

###### Proof.

We use the same construction for both parts. To prove the first claim, let
$k=n$. To prove the second claim, let $k\geq\log_{2}M$.

Suppose $\lambda=1/n$. Let $H_{n}=A_{n+1}^{k}$, the direct product of $k$
copies of $A_{n+1}$. Then $\Lambda_{A_{n},H_{n}}=1/n$. Let $f\colon A_{n}\to
H_{n}$ by $f(g)=(g,\dots,g)$, the diagonal identity map, where $A_{n}$ is
embedded in $A_{n+1}$. For nonempty $S\subseteq[n]$ and $j\in[n]$, let
$h=h(S,j)=(h_{1},\dots,h_{k})\in H_{n}$, where $h_{i}$ is the transposition
$(j,n+1)$ if $i\in S$ and $1$ otherwise. For each such $h$, let
$\varphi_{h}\in\operatorname{Hom}(A_{n},H_{n})$ be given by
$\varphi_{h}(g)=h^{-1}f(g)h$. Each $\varphi_{h}$ has agreement
$\operatorname{agr}(\varphi_{h},f)=1/n=\Lambda$ with $f$. There are
$n(2^{k}-1)$ such $h$, so $\ell(\operatorname{Hom}(A_{n},H_{n}),\Lambda)\geq
n(2^{k}-1)$.

Suppose $\lambda=1/\binom{n}{2}$. Let $H_{n}=A_{n}^{k}$. Then,
$\Lambda_{A_{n},H_{n}}=1/\binom{n}{2}$. Let $f\colon A_{n}\to H_{n}$ by
$f(g)=(g,\ldots,g)$, the diagonal identity map. For nonempty $S\subseteq[n]$
and $\tau\in S_{n}$ is a transposition, let
$h=h_{S,\tau}=(h_{1},\ldots,h_{k})\in A_{n}^{k}$, where $h_{i}=\tau$ if $i\in
S$ and $1$ otherwise. For each such $h$, let
$\varphi_{h}\in\operatorname{Hom}(A_{n},H_{n})$ be given by
$\varphi_{h}(g)=h^{-1}f(g)h$. Each such $\varphi_{h}$ has agreement
$\operatorname{agr}(\varphi_{h},f)=1/\binom{n}{2}$. There are
$\binom{n}{2}(2^{k}-1)$ such $h$, so
$\ell(\operatorname{Hom}(A_{n},H_{n}),\Lambda)\geq\binom{n}{2}(2^{k}-1)$.

∎

We remark that $\ell(\operatorname{Hom}(A_{n},H),\Lambda_{A_{n},H})$ is not
bounded as a function of $n$ for a wide variety of classes of $H$.

##  10 Shallow random generation

In this section, we prove results about SRG groups, defined in Section 4.4),
for which few random elements tend to generate a shallow (low depth) subgroup.
In Section 10.1, we will show that alternating groups are SRG. In Section 10.3
we will prove that SRG groups are also “KLC” groups (another generation
property, defined in Section 10.2). The consequences of SRG will be proved
using the KLC assumption in Section 11.

Recall that Section 5.5 showed

the code $\operatorname{Hom}(G,H)$ is CombEcon if and only if
$\operatorname{aHom}(G,H)$ is CombEcon, and similarly for CertEcon, and
AlgEcon under modest assumptions of the representation of the groups. All our
results about SRG groups (universal CombEcon and CertEcon, see Section 11)
will take advantage of this equivalence, as our proofs will argue about
$\operatorname{Hom}(G,H)$ instead of $\operatorname{aHom}(G,H)$. To reflect
this, concepts in this section are defined in terms of subgroup generation
using $\langle\cdot\rangle$ instead of affine generation using
$\langle\cdot\rangle_{\mathsf{aff}}$.

Further recall Proposition 3.5 which states that, if $\Lambda_{G,H}\neq 0$,
then ‘$\operatorname{aHom}$’ can be replaced by ‘$\operatorname{Hom}$’ in the
definition of $\Lambda_{G,H}$, i.e.,

$\Lambda_{G,H}=\max_{\begin{subarray}{c}\varphi,\psi\in\operatorname{Hom}(G,H)\\\
\varphi\neq\psi\end{subarray}}\operatorname{agr}(\varphi,\psi).$

If we used instead the affine version of our tools and arguments to reason
directly about $\operatorname{aHom}(G,H)$ (instead of reasoning about
$\operatorname{Hom}(G,H)$ then using the material of Section 5.5 to get bounds
for $\operatorname{aHom}(G,H)$), the degrees of the polynomials in the
$\operatorname{poly}(1/\varepsilon)$ expression for the SRG results would be
identical.

###  10.1 Alternating groups are SRG

In this subsection, we prove that $\operatorname{\mathfrak{Alt}}$ is SRG.

######  Theorem 10.1.

The class of alternating groups is SRG. In fact, for all $k\geq 2$ there is an
integer $n_{k}$ such that for all $n\geq n_{k}$, the alternating group $A_{n}$
is $(k,4k-2)$-shallow generating.

The quantity $n_{k}$ may be large as a function of $k$; however, there is an
integer $n_{0}$ such that for all $k\geq 2$ and all
$n\geq\max\\{n_{0},(3k)^{3}\\}$, the alternating group $A_{n}$ is
$(k,6k-2)$-shallow generating.

##### Consequences.

Before proving Theorem 10.1, we first discuss its consequences. In Section 11
we prove facts that hold for all SRG groups. Here are the implications of
those facts for alternating groups.

From Theorem 11.1, we find that $\operatorname{aHom}(A_{n},H)$ is CombEcon
with degree $8$, i.e.,
$\ell(\operatorname{aHom}(A_{n},H),\Lambda+\varepsilon)<1/\varepsilon^{8}$ for
all $H\in\operatorname{\mathfrak{Groups}}$. We remark that the constant 8 can
be improved to 6. This is by improving the $(8,\Lambda,7)$-generated claim to
$(6,\Lambda,5)$-generated by going through the proof with a
“$\operatorname{depth}_{\Lambda}$” notion instead of
$\operatorname{depth}_{G}$ as written. This
$\operatorname{depth}_{\Lambda}(K)$ refers to maximal length of a subgroup
chain from $K$ to a subgroup of density greater than $\Lambda$.

By Theorem 11.2, $\operatorname{\mathfrak{Alt}}$ is CertEcon. More
specifically, $\operatorname{\mathfrak{Alt}}$ is universally strong
certificate-list-decodable using $O(\ln(1/\varepsilon)/\varepsilon^{9})$
queries and computation time. Certificates are generated by querying the
received word on sets of uniform size. This is formalized in Section 11.2.

If $H=S_{m}$ and $m<2^{n}/\sqrt{1.6n}$, then calls to the subword extender
HomExt can be executed in $\operatorname{poly}(n,m)$-time, by Theorem 4.25. We
combine HomExt with the certificate-list-decoder to find a list-decoder. One
call to HomExt is made per certificate in the returned certificate-list, so
the list-decoder runs in time $\operatorname{poly}(1/\varepsilon,n,m)$ while
using $\operatorname{poly}(1/\varepsilon)$-queries.

##### Presentation of proof.

To prove Theorem 10.1 we first present a useful result [Bab89, Theorem 1.5]
that two random elements of the symmetric group generate a ‘large’ subgroup
with high probability. This event is denoted $E(n,k)$ in the statement.

######  Theorem 10.2 (Babai).

Let $\pi,\sigma$ be a pair of independent uniform random elements from
$S_{n}$. For $0\leq k\leq n/3$, let $E(n,k)$ denote the following event: The
subgroup $K=\langle\pi,\sigma\rangle$ acts as $S_{r}$ or $A_{r}$ on $r$
elements of the permutation domain for some $r\geq n-k$. Then,

$\Pr(E(n,k))=1-\binom{n}{k+1}^{-1}+O\left(\binom{n}{k+2}^{-1}\right).$ (18)

The constant implied by the big-$O$ notation is absolute.

######  Remark 10.3.

Suppose that we choose $\pi$ and $\sigma$ from $A_{n}$ (instead of $S_{n}$) in
Theorem 10.2. The same conclusion is still true. However, using only Theorem
10.2 as justification, the conclusion is slightly weaker – there will be a
coefficient of $4$ in front of $\binom{n}{k+1}^{-1}$. In our application, this
coefficient makes no difference to our argument.

We now bound the depth of the subgroup generated by two elements, given that
$E(n,2k)$ occurred.

######  Claim 10.4.

There exists $n_{0}$ such that the following holds: Let $E,k,\pi,\sigma$ be
defined as in Theorem 10.2. If $n\geq n_{0}$ and $E(n,k)$ occurs, then
$\operatorname{depth}_{A_{n}}(\langle\pi,\sigma\rangle)\leq 2k-2$.

###### Proof.

Let $K=\langle\pi,\sigma\rangle$. If $E(n,k)$ occurs, then $K$ acts as $S_{r}$
or $A_{r}$ on some subset of $r$ elements of $[n]$, for some $r\geq n-k>n/2$.
So, $A_{r}\leq K$.

By Corollary 9.3, we find that
$\operatorname{depth}_{A_{n}}(K)\leq\operatorname{depth}_{A_{n}}\left(A_{r}\right)\leq
2k-2$.

∎

We can now prove Theorem 10.1.

###### Proof of Theorem 10.1.

We prove the first part.

By Theorem 10.2 and Claim 10.4, it holds for large $n$ that

$\Pr_{\pi,\sigma\in
A_{n}}[\operatorname{depth}_{A_{n}}(\langle\pi,\sigma\rangle)>4k-2]\leq\Pr_{\pi,\sigma\in
A_{n}}[\neg E(n,2k)]\leq\frac{4}{{n\choose
2k+1}}\leq\frac{1}{\binom{n}{2}^{k}}=(\Lambda_{A_{n}}^{*})^{k}.$

It follows that $A_{n}$ is $(k,4k-2)$-shallow generating.

The proof of the second part is similar. ∎

###  10.2 Subset-generation

In this section we define a useful technical “KLC” condition on groups, which
SRG groups satisfy (shown in the next section). The connection between KLC and
universal CombEcon or CertEcon is more direct, and our “SRG implies
universally CombEcon and CertEcon” results are proved through the KLC property
(Section 11).

######  Definition 10.5 ($(k,\lambda,c)$-subset-generated).

Let $G$ be a finite group, $k$ a nonnegative integer, $0\leq\lambda<1$, and
$c\geq 0$. We say that $G$ is $(k,\lambda,c)$-subset-generated if, for all
subsets $S\subseteq G$ with $\mu(S)>\lambda$, we have that

$\displaystyle\Pr_{s_{1},\dots,s_{k}\in S}[\mu(\langle
s_{1},\dots,s_{k}\rangle)>\lambda]\geq\left(1-\frac{\lambda}{\mu(S)}\right)^{c},$
(19)

where $s_{1},\dots,s_{k}$ are chosen independently and uniformly from $S$.

Note that, if we define $\varepsilon=\mu(S)-\lambda$, then
$1-\frac{\lambda}{\mu(S)}=\frac{\varepsilon}{\lambda+\varepsilon}$, so
Equation (19) mirrors the expression of Lemma 7.12.

We say that $G$ is $(k,\lambda,c)$-affine-generated if it satisfies Definition
10.5 but with $\langle s_{1},\dots,s_{k}\rangle$ replaced by $\langle
s_{1},\dots,s_{k}\rangle_{\mathsf{aff}}$.

We will make a few remarks on these definitions below, but first we define KLC
classes of groups.

######  Definition 10.6 (KLC).

Let $\mathfrak{G}$ be a class of finite groups. We say that $\mathfrak{G}$ is
KLC if there exists a positive integer $k$ and a constant $c>0$ such that, for
all $G\in\mathfrak{G}$ and for all groups $H$, we have that $G$ is
$(k,\Lambda_{G,H},c)$-subset-generated.

The notion of “KLC-affine” can be defined analogously. But, according to
Remark 10.7 c

below, the two conditions are equivalent on a class of groups.

We make a few remarks on the definitions of $(k,\lambda,c)$-subset-generated
groups.

######  Remark 10.7.

  1. (a)

For every $k\geq 1$ and $c\geq 0$, the class
$\operatorname{\mathfrak{Groups}}$ of all finite groups is $(k,0,c)$-subset-
generated.

  2. (b)

Classes of $(k,\lambda,c)$-subset-generated groups are monotone in both $k$
and $c$. More specifically, for $k^{\prime}>k$ and $c^{\prime}>c$, if $G$ is
$(k,\lambda,c)$-subset-generated, then $G$ is also
$(k^{\prime},\lambda,c)$-subset-generated and $(k,\lambda,c^{\prime})$-subset-
generated.

  3. (c)

If $G$ is $(k,\lambda,c)$-affine-generated, then it is $(k,\lambda,c)$-subset-
generated. If $G$ is $(k,\lambda,c)$-affine-generated, then it is
$(k+1,\lambda,c)$-generated.

###  10.3 SRG implies subset-generation

We prove that SRG implies KLC, using a straightforward application of Bayes’
rule.

######  Theorem 10.8 (SRG implies KLC).

If a class $\mathfrak{G}$ of groups is SRG, then $\mathfrak{G}$ is KLC.

In particular, let $G$ be a finite group, $k,d\in\mathbb{N}$, and $\lambda>0$.
If $G$ is $(k,d)$-shallow generating, then $G$ is $(k+d,\lambda,1+d)$-subset-
generated for all $\lambda\geq\Lambda_{G}^{*}$.

###### Proof.

All groups are trivially $(1,0,1)$-subset-generated, which covers the case
where $\lambda=0$.

Let $\lambda>0$. By assumption, we know that

$\Pr_{g_{1},\ldots,g_{k}\in G}[\operatorname{depth}(\langle
g_{1},\ldots,g_{k}\rangle)>d]<\lambda^{k}.$ (20)

We check the definition of $(k+d,\lambda,1+d)$-subset-generated.

Let $S\subseteq G$ be such that $\mu(S)>\lambda$ and let
$\varepsilon=\mu(S)-\lambda$. We will pick a $k$-tuple
$\mathbf{g}=(g_{1},\ldots,g_{k})$ and a $d$-tuple
$\mathbf{s}=(s_{1},\ldots,s_{d})$ from $S$. We write
$\langle\mathbf{g}\rangle$ to mean $\langle g_{1},\ldots,g_{k}\rangle$. We
write $\langle\mathbf{s}\rangle$ and $\langle\mathbf{s},\mathbf{g}\rangle$
similarly.

Observe that

$\displaystyle\Pr_{\mathbf{g}\in S^{k},\mathbf{s}\in
S^{d}}\left[\mu\left(\langle\mathbf{g},\mathbf{s}\rangle\right)>\lambda\right]$
$\displaystyle\geq\Pr_{\mathbf{s}\in
S^{d}}\left[\mu\left(\langle\mathbf{g},\mathbf{s}\rangle\right)>\lambda\mid\operatorname{depth}(\langle\mathbf{g}\rangle)\geq
d\right]\cdot\Pr_{\mathbf{g}\in
S^{k}}[\operatorname{depth}(\langle\mathbf{g}\rangle)\geq d].$

We bound the two components of the right hand side separately. When we drop
the subscript on $\Pr$, that means the elements are chosen at random from $G$.
First, we consider the second component.

$\displaystyle\Pr_{\mathbf{g}\in
S^{k}}[\operatorname{depth}(\langle\mathbf{g}\rangle)\geq d]$
$\displaystyle=\Pr_{\mathbf{g}\in
G^{k}}[\operatorname{depth}(\langle\mathbf{g}\rangle)\geq d]\mid\mathbf{g}\in
S^{k}]$ $\displaystyle=\frac{\Pr[\mathbf{g}\in S^{k}\text{ and
}\operatorname{depth}(\langle\mathbf{g}\rangle)\geq d]}{\Pr[\mathbf{g}\in
S^{k}]}$ $\displaystyle\geq\frac{\Pr[\mathbf{g}\in
S^{k}]+\Pr[\operatorname{depth}(\langle\mathbf{g}\rangle)\geq
d]-1}{\Pr[\mathbf{g}\in S^{k}]}$
$\displaystyle>\frac{\mu(S)^{k}-(\lambda)^{k}}{\mu(S)^{k}}=1-\left(\frac{\lambda}{\mu(S)}\right)^{k}$
$\displaystyle\geq
1-\frac{\lambda}{\lambda+\varepsilon}=\frac{\varepsilon}{\lambda+\varepsilon}.$

Now, it suffices to show that the first component has probability bounded by
$\left(\frac{\varepsilon}{\lambda+\varepsilon}\right)^{d}$. But, if
$\operatorname{depth}(\langle\mathbf{g}\rangle)\geq d$, then it follows from
Lemma 7.12, with $K=\langle\mathbf{g}\rangle$ and $\lambda=\lambda$, that

$\displaystyle\Pr_{\mathbf{s}\in
S^{d}}\left[\mu\left(\langle\mathbf{g},\mathbf{s}\rangle\right)>\lambda\mid\operatorname{depth}(\langle\mathbf{g}\rangle)\geq
d\right]>\left(\frac{\varepsilon}{\lambda+\varepsilon}\right)^{d}.$

We conclude that $G$ is $(k+d,\lambda,1+d)$-subset-generated, or,

$\Pr_{s_{1},\ldots,s_{k+d}\in S}\left[\mu\left(\langle
s_{1},\ldots,s_{k+d}\rangle\right)>\lambda\right]=\Pr_{\mathbf{g}\in
S^{k},\mathbf{s}\in
S^{d}}\left[\mu\left(\langle\mathbf{g},\mathbf{s}\rangle\right)>\lambda\right]>\left(\frac{\varepsilon}{\lambda+\varepsilon}\right)^{d+1}.$

∎

##  11 Consequences of shallow random generation

We proved the claimed consequences of shallow random generation, using the KLC
property. These consequences include universal CombEcon (Section 11.1) and
universal CertEcon (Section 11.2).

Universal AlgEcon follows if a subword extender ($\textsc{HomExt}(G,H)$
oracle) is provided, as discussed in Section 4.7. Stronger subword extenders
provide better guarantees on the output list and lower bounds on $\Lambda$
(Section 11.3).

###  11.1 SRG implies CombEcon

KLC implies universally CombEcon.

######  Theorem 11.1.

If a class $\mathfrak{G}$ is SRG, then $\mathfrak{G}$ is universally CombEcon.
More precisely, let $k\in\mathbb{N}$ and $c>0$. If $G$ is a
$(k,\Lambda_{G,H},c)$-subset-generated group, then
$\ell(\operatorname{Hom}(G,H),\Lambda_{G,H}+\varepsilon)\leq
1/\varepsilon^{\max\\{c,k\\}}$ for all $\varepsilon\in(0,1-\Lambda)$ and
groups $H$.

###### Proof.

By Theorem 10.8, if $\mathfrak{G}$ is SRG, then $\mathfrak{G}$ is KLC.

We define a bipartite graph $X$. The left vertex set of $X$ is $G^{k}$. The
right vertex set is
$\mathcal{L}=\mathcal{L}(\operatorname{Hom}(G,H),f,\Lambda+\varepsilon)$.
There is an edge between $(g_{1},\dots,g_{k})\in G^{k}$ and
$\varphi\in\mathcal{L}$ if $g_{1},\dots,g_{k}\in\operatorname{Eq}(f,\varphi)$,
and $\mu(\langle g_{1},\dots,g_{k}\rangle)>\Lambda$.

By the definition of $(k,\Lambda_{G,H},c)$-subset-generated group, each right
vertex has degree at least
$(\frac{\varepsilon}{\Lambda+\varepsilon})^{c}\lvert S\rvert^{k}$, which is at
least
$(\frac{\varepsilon}{\Lambda+\varepsilon})^{c}(\Lambda+\varepsilon)^{k}\lvert
G\rvert^{k}\geq\varepsilon^{\max\\{c,k\\}}\lvert G^{k}\rvert$.

By Lemma 7.16 with $K=1$, each left vertex of $X$ has degree at most one.

So, by part (a) of Lemma 5.1 (double counting), $\lvert\mathcal{L}\rvert\leq
1/\varepsilon^{\max\\{c,k\\}}$. ∎

###  11.2 SRG implies CertEcon

A KLC class of groups is also universally CertEcon. The argument is
conceptually similar to that of CombEcon, but we need to formalize algorithmic
issues.

Again, let $\mathcal{W}_{\Lambda}$ denote the set of
$G\operatorname{\rightharpoonup}H$ partial maps $\gamma$ satisfying
$\mu(\langle\operatorname{dom}\gamma\rangle)>\Lambda_{G,H}$.

######  Theorem 11.2.

If $\mathfrak{G}$ be an SRG class of groups, then $\mathfrak{G}$ is
universally strong $\mathcal{W}_{\Lambda}$-CertEcon. We assume that all groups
in $\mathfrak{G}$ are encoded groups, that (nearly) uniform elements of $G$
are provided, and that we have oracle access to the entries of the received
word.

If a partial map $\gamma$ can be extended to some homomorphism and satisfies
$\mu(\langle\operatorname{dom}(\gamma)\rangle)>\Lambda$, then $\gamma$ is a
$\mathcal{W}$-certificate. However, $\operatorname{dom}(\gamma)$ may fail to
generate the entire group, i.e.,
$\langle\operatorname{dom}(\gamma)\rangle\lneq G$. Following the strategy of
Section 2.6, we may combine a certificate list-decoder and a Homomorphism
Extension oracle $\textsc{HomExt}_{\Lambda}$ (a
$\mathcal{W}_{\Lambda}$-subword extender). The next section discusses how to
take this strategy a step further using a stronger Homomorphism Extension
oracle to lower bound $\Lambda$.

##### Domain certificates versus certificates.

We develop some terminology for Theorem 11.2, based on the natural idea of
generating certificates by querying the received word $f$. “Domain
certificates” (dependent on $f$) are subsets of the domain that define a
certificate when restricting $f$ to that set.

Let $G$ and $H$ be groups and $f\in H^{G}$ be a received word in the codespace
of $\operatorname{Hom}(G,H)$. Let $S\subseteq G$ be a subset. Denote by
$f_{S}$ the restriction of $f$ to $S$, i.e., the
$H\operatorname{\rightharpoonup}G$ partial map with domain $S$ defined by
$f_{S}(g)=f(g)$ for $g\in S$.

######  Definition 11.3 (Domain certificate).

When the code $\operatorname{Hom}(G,H)$ and the received word $f$ are
understood, we say that a subset $S\subseteq G$ is a domain certificate if the
$G\operatorname{\rightharpoonup}H$ partial map $f_{S}$ is a certificate for
$\operatorname{aHom}(G,H)$.

For a set $\mathcal{W}$ of $G\operatorname{\rightharpoonup}H$ partial maps, we
say that $S$ is a domain $\mathcal{W}$-certificate if $f_{S}$ is a
$\mathcal{W}$-certificate for $\operatorname{Hom}(G,H)$.

Note that a domain certificate $S\subseteq G$ is a domain
$\mathcal{W}_{\Lambda}$-certificate if and only if $\mu(\langle
S\rangle)>\Lambda_{G,H}$.

######  Definition 11.4 (Domain-certificate-list).

We say that a list $\Upsilon$ of subsets of $G$ is a domain-certificate-list
for a subset $\mathcal{L}\subseteq\operatorname{aHom}(G,H)$ of affine
homomorphisms if $\Upsilon$ contains a domain certificate for each codeword in
$\mathcal{L}$. We define domain-$\mathcal{W}$-certificate-lists similarly.

##### Domain certificate result.

Now, we can restate the unabridged SRG result (Theorem 4.17) in terms of
domain certificates.

######  Theorem 11.5 (SRG implies CertEcon, via domain certificates).

Let $k\in\mathbb{N}$ and $c>0$. Let $G$ be a $(k,\Lambda_{G,H},c)$-subset-
generated group and $H$ a group. Let $f:G\to H$, $\varepsilon>0$ and $\eta>0$.
Let $\Upsilon$ be a list of
$\left\lceil\frac{1}{\varepsilon^{b}}\ln\left(\frac{1}{\eta\varepsilon^{b}}\right)\right\rceil$
independently chosen subsets of $G$, each of size $\max\\{c,k\\}$. Then, with
probability at least $(1-\eta)$, $\Upsilon$ is a
domain-$\mathcal{W}_{\Lambda}$-certificate-list of
$\mathcal{L}(\operatorname{aHom}(G,H),f,\Lambda+\varepsilon)$.

The proof is delayed to first discuss its implications and access model.

######  Remark 11.6 (Access model).

To generate the domain-$\mathcal{W}$-certificate-list, we need access only the
domain, only in the ability to generate random elements. No knowledge of $H$
is required. The dependence on $H$ appears only in the $\Lambda_{G,H}$ of the
assumption that $G$ is $(k,\Lambda_{G,H},c)$-subset generated, but the KLC
assumption means that $G$ is $(k,\Lambda_{G,H},c)$-subset generated for every
$H$. Knowledge of $\Lambda_{G,H}$ is also not required.

Theorem 11.5 produces domain $\mathcal{W}$-certificates. No work is involved
other than generating these $\operatorname{poly}(1/\varepsilon)$ uniform
random elements of $G$. To then produce actual $\mathcal{W}$-certificates,
simply query $f$ on the domain $\mathcal{W}$-certificates, an additional
$\operatorname{poly}(1/\varepsilon)$ queries to $f$. Theorem 11.2 follows.

######  Remark 11.7 (Amount of work).

Theorem 11.2 implies a stronger result than strong CertEcon, as only a
$\operatorname{poly}(1/\varepsilon)$ amount of work is required in the unit
cost model (no dependency on $\lvert G\rvert$).111 Two incomparable sufficient
conditions for the access model to $G$ are black-box access and polycyclic
presentations. In a black-box group, $\varepsilon$-uniform elements can be
generated in polynomial time [Bab91]. Given a polycyclic presentation, exactly
uniform elements can be generated.

##### Analysis.

To prove Theorem 11.5 we check the definition of domain
$\mathcal{W}_{\Lambda}$-certificate-list. In other words, with probability
$(1-\eta)$, for every
$\varphi\in\mathcal{L}(\operatorname{Hom}(G,H),f,\Lambda+\varepsilon)$ the
list $\Upsilon$ contains a domain $\mathcal{W}_{\Lambda}$-certificate
$S_{\varphi}\subseteq G$ for $\varphi$. A sufficient condition to be a domain
$\mathcal{W}_{\Lambda}$ certificate is given below.

######  Observation 11.8.

If the conditions $\mu(\langle{S}\rangle)>\Lambda$ and
$S\subset\operatorname{Eq}(\varphi,f)$ are satisfied, then $S$ is a domain
$\mathcal{W}_{\Lambda}$-certificate for $\varphi$.

###### Proof of Theorem 11.5.

Let $\mathcal{L}=\mathcal{L}(\operatorname{Hom}(G,H),=f,\Lambda+\varepsilon)$.
Recall that $G$ is $(k,\Lambda_{G,H},c)$-subset generated. Let
$b=\max\\{c,k\\}$. Let $\Upsilon=\\{S_{1},\ldots,S_{t}\\}$ be the list of
uniformly chosen subsets of $G$ as assumed. Then,
$t=\left\lceil\frac{1}{\varepsilon^{b}}\ln\left(\frac{1}{\eta\varepsilon^{b}}\right)\right\rceil$
and each $S_{i}$ consists of $b$ uniformly and independently chosen elements
of $G$.

Fix $\varphi\in\mathcal{L}$. Fix $S\in\Upsilon$. We calculate the following.

$\displaystyle\Pr[S\text{ is a domain $\mathcal{W}_{\Lambda}$-certificate for
}\varphi]$
$\displaystyle\geq\Pr\left[S\subseteq\operatorname{Eq}(\psi,f)\cap\mu\left(\langle
S\rangle\right)>\Lambda\right]$ $\displaystyle=\Pr\left[\mu\left(\langle
S\rangle\right)>\Lambda\bigg{|}S\subseteq\operatorname{Eq}(\psi,f)\right]\cdot\Pr[S\subseteq\operatorname{Eq}(\psi,f)]$
$\displaystyle>\left(\frac{\varepsilon}{\Lambda+\varepsilon}\right)^{c}\cdot(\Lambda+\varepsilon)^{k}$
$\displaystyle>\varepsilon^{b}.$

The first inequality follows from Observation 11.8, and the second inequality
follows from the definition of $(k,\Lambda,c)$-subset generated.

The probability that $\Upsilon$ is not a domain $\mathcal{W}$-certificate-list
for $\mathcal{L}$, i.e., there is $\varphi\in\mathcal{L}$ such that $\Upsilon$
contains no domain-$\mathcal{W}$-certificate for $\varphi$, is bounded by

$\lvert\mathcal{L}\rvert\cdot\left(1-\varepsilon^{b}\right)^{t}\leq\frac{1}{\varepsilon^{b}}\exp\left(-\varepsilon^{b}\cdot
t\right)<\eta,$

where we have used that $\lvert\mathcal{L}\rvert\leq 1/\varepsilon^{b}$ by the
CombEcon result Theorem 11.1. ∎

###  11.3 Improvements on $\Lambda$

In this section we first discuss the role of $\Lambda$ in the relationship
between CertEcon, HomExt, and AlgEcon. Then, we will give an algorithm that
improves our lower bounds on $\Lambda$ and discuss its benefits.

##### Role of $\Lambda$ lower bounds in subword extenders.

As discussed in generality (Section 2.6), for two sets $\mathcal{W}_{1}$ and
$\mathcal{W}_{2}$ of partial maps $\Omega\to\Sigma$, if they satisfy
$\mathcal{W}_{1}\subseteq\mathcal{W}_{2}$ then a
$\mathcal{W}_{1}$-certificate-list-decoder and a $\mathcal{W}_{2}$-subword-
extender combine to a list-decoder. In our context, we consider the sets
$\mathcal{W}_{\lambda}$ consisting of $G\operatorname{\rightharpoonup}H$
partial maps whose domain generate a subgroup of $\lambda$ density, i.e.,

$\mathcal{W}_{\lambda}:=\left\\{\gamma:G\operatorname{\rightharpoonup}H\mid\mu(\langle\operatorname{dom}\gamma\rangle)>\lambda\right\\}.$

Since we have $\mathcal{W}_{\Lambda_{G,H}}$-CertEcon results for SRG groups
(Theorem 11.2), it suffices to find $\mathcal{W}_{\lambda}$-subword extenders,
i.e., solve $\textsc{HomExt}_{\lambda}(G,H)$, for $\operatorname{aHom}(G,H)$
with $\lambda\leq\Lambda_{G,H}$.

So, a stronger lower bound for $\Lambda_{G,H}$ allows use of a weaker HomExt
oracle.

##### Role of subword extenders in $\Lambda$ lower bounds.

Conversely, a stronger $\textsc{HomExt}(G,H)$ oracle can be used to update
lower bounds on $\Lambda_{G,H}$, which allows better pruning of the output
list. We will explain both clauses of this sentence below.

First, we discuss finding better lower bounds on $\Lambda_{G,H}$, using a
stronger version of HomExt we call $\textsc{HomExt}012$. The
$\textsc{HomExt}012$ Problem asks to distinguish between the cases of no
extension, unique extension, and multiple extensions. In the case of a unique
extension, it asks for the extension.

######  Definition 11.9.

($\textsc{HomExt}012(G,H)$)
Instance: A partial map $\gamma:G\operatorname{\rightharpoonup}H$.
Solutions: The set defined by

$\operatorname{HExt}(\gamma):=\\{\varphi\in\operatorname{Hom}(G,H):\varphi|_{\operatorname{dom}\gamma}=\gamma\\}.$

Output: $\begin{cases}\text{`none'}&\text{ if
}\lvert\operatorname{HExt}(\gamma)\rvert=0\\\
\varphi\in\operatorname{HExt}(\gamma)\,\,&\text{ if
}\lvert\operatorname{HExt}(\gamma)\rvert=1\\\ \text{`multiple'}&\text{ if
}\lvert\operatorname{HExt}(\gamma)\rvert\geq 2\end{cases}.$

The $\textsc{HomExt}012_{\lambda}(G,H)$ problem is defined similarly, but
requiring only correct answers on the $G\operatorname{\rightharpoonup}H$
partial maps in $\mathcal{W}_{\lambda}$.

######  Proposition 11.10.

Let $G$ and $H$ be groups to which we are given black-box access. Suppose that
we are given an oracle for $\textsc{HomExt}012_{\lambda}(G,H)$ and an order
oracle for subgroups. Then, a subword extender for $\operatorname{aHom}(G,H)$
can be implemented in $\operatorname{poly}(\operatorname{enc}(G))$-time in the
unit-cost model for $H$. Moreover, for any $G\operatorname{\rightharpoonup}H$
partial map $\gamma$ on which $\textsc{HomExt}012(G,H)$ returns ‘multiple,’
the value of $\mu(\langle\operatorname{dom}\gamma\rangle)$ is a lower bound
for $\Lambda$.

###### Proof.

The first conclusion of this proposition is the same as Proposition 4.21.

The second conclusion is trivial, since multiple extensions of $\gamma$ would
be distinct homomorphisms in $\operatorname{Hom}(G,H)$ that agree on
$\langle\operatorname{dom}\gamma\rangle$, so
$\mu(\langle\operatorname{dom}\gamma\rangle)$ lower bounds $\Lambda_{G,H}$.
(Recall Proposition 3.5 which states that, if $\Lambda_{G,H}\neq 0$, then
‘$\operatorname{aHom}$’ can be replaced by ‘$\operatorname{Hom}$’ in the
definition of $\Lambda_{G,H}$.) The order oracle can be used to calculate the
value of $\mu(\langle\operatorname{dom}\gamma\rangle)$. ∎

Recall that our main algorithmic result (Theorem 1.7) hinges on a solution
[Wuu18] for $\textsc{HomExt}_{\lambda}(G,H)$ Search in the cases considered
($G=A_{n}$ and $H=S_{m}$ for exponentially bounded $m$), for the lower bound
$\lambda=1/\binom{n}{2}$ of $\Lambda_{G,H}$. In fact [Wuu18] provides a
solution for $\textsc{HomExt}012_{\lambda}(G,H)$ with the same $\lambda$ (or
the version of HomExt that counts solutions until some threshold). This allows
a stronger lower bounding of $\Lambda_{G,H}$ as promised.

We discuss the “better pruning” consequences of these updated lower bounds on
$\Lambda$.

  1. 1.

Better pruning of the final output list: The definition of list-decoder
requires only that the output list $\widetilde{\mathcal{L}}$ be a superlist of
the desired list
$\mathcal{L}=\mathcal{L}(\operatorname{aHom}(G,H),f,\Lambda+\varepsilon)$. The
output can be pruned, using any lower bound $\lambda$ on $\Lambda$, to contain
only affine homomorphisms $\varphi\in\operatorname{aHom}(G,H)$ that have high
agreement $\operatorname{agr}(\varphi,f)>\lambda+\varepsilon/2$ with $f$. The
pruning can be accomplished by sampling agreement.

  2. 2.

Faster processing of certificate-lists (output of certificate-list-decoder)
into output lists (output of list-decoder): While the value of $\Lambda_{G,H}$
may be unknown, the certificate-list-decoder of Theorem 11.2 guarantees
certificates in $\mathcal{W}_{\Lambda_{G,H}}$. A known lower bound $\lambda$
for $\Lambda_{G,H}$ allows pruning of partial maps $\gamma$ that do not
satisfy $\mu(\langle\operatorname{dom}\gamma\rangle)>\lambda$. The subword
extender need not be called on these maps.

## References

  * [Bab86] László Babai.  On the length of subgroup chains in the symmetric group.  Communications in Algebra, 14(9):1729–1736, 1986.
  * [Bab89] László Babai.  The probability of generating the symmetric group.  Journal of Combinatorial Theory, Series A, 52(1):148 – 153, 1989\.
  * [Bab91] László Babai.  Local expansion of vertex-transitive graphs and random generation in finite groups.  In STOC, pages 164–174, New York, NY, USA, 1991. ACM.
  * [BBS09] László Babai, Robert Beals, and Ákos Seress.  Polynomial-time theory of matrix groups.  In STOC, pages 55–64, New York, NY, USA, 2009. ACM.
  * [BGSW18] Timothy Black, Alan Guo, Madhu Sudan, and Angela Wuu.  List decoding nilpotent groups.  2018\.
  * [BL15] Abhishek Bhowmick and Shachar Lovett.  The list decoding radius of reed-muller codes over small fields.  In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 277–285, New York, NY, USA, 2015. ACM.
  * [BLGN+05] Robert Beals, Charles R. Leedham-Green, Alice C. Niemeyer, Cheryl E. Praeger, and Ákos Seress.  Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules.  Journal of Algebra, 292(1):4 – 46, 2005.
  * [BS84a] László Babai and Endre Szemerédi.  On the complexity of matrix group problems I.  In FOCS, SFCS ’84, pages 229–240, Washington, DC, USA, 1984. IEEE Computer Society.
  * [BS84b] László Babai and Endre Szemerédi.  On the complexity of matrix group problems i.  In FOCS, pages 229–240. IEEE, 1984.
  * [DGKS08] Irit Dinur, Elena Grigorescu, Swastik Kopparty, and Madhu Sudan.  Decodability of group homomorphisms beyond the Johnson bound.  In Dwork [Dwo08], pages 275–284.
  * [DM96] John D. Dixon and Brian Mortimer.  Permutation Groups.  Graduate Texts in Mathematics. Springer New York, 1996.
  * [Dwo08] Cynthia Dwork, editor.  Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008. ACM, 2008.
  * [GKS06] Elena Grigorescu, Swastik Kopparty, and Madhu Sudan.  Local decoding and testing for homomorphisms.  In Josep Díaz, Klaus Jansen, José D. P. Rolim, and Uri Zwick, editors, APPROX-RANDOM, volume 4110 of Lecture Notes in Computer Science, pages 375–385. Springer, 2006.
  * [GKZ08] Parikshit Gopalan, Adam R. Klivans, and David Zuckerman.  List-decoding Reed-Muller codes over small fields.  In Dwork [Dwo08], pages 265–274.
  * [GL89] Oded Goldreich and Leonid A. Levin.  A hard-core predicate for all one-way functions.  In David S. Johnson, editor, STOC, pages 25–32. ACM, 1989.
  * [GS14] Alan Guo and Madhu Sudan.  List decoding group homomorphisms between supersolvable groups.  In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, APPROX/RANDOM, volume 28 of LIPIcs, pages 737–747. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014.
  * [Guo15] Alan Guo.  Group homomorphisms as error correcting codes.  Electronic Journal of Combinatorics, 22(1):P1.4, 2015.
  * [HP03] William Cary Huffman and Vera Pless.  Fundamentals of Error-Correcting Codes.  Cambridge University Press, 2003.
  * [Isa08] I. Martin Isaacs.  Finite Group Theory.  Graduate studies in mathematics. American Mathematical Society, 2008.
  * [Rob95] Derek J. S. Robinson.  A Course in the Theory of Groups.  Springer, 2nd edition, 1995.
  * [Wuu18] Angela Wuu.  Homomorphism extension.  arXiv:1802.08656, 2018.