% ==================================================================
% A Counterexample to Kaplansky's Direct-Finiteness Conjecture
% in Odd Characteristic
%
% Self-contained LaTeX; compile with pdflatex.
%
% This version is meant to be read carefully. The motivating words are
% in ordinary English; the technical statements are the same as in the
% original paper. The reader is assumed to know polynomials, matrices,
% and the very basics of groups ("a set with an associative product,
% an identity, and inverses"). Every other object is defined here.
%
% Reading guide:
%   Section 1: the puzzle, and what we are going to build.
%   Section 2: the concrete finite data (prime p, field K, graph Gamma,
%              local group H).
%   Section 3: the special idempotent e in K[H] that has a large rank
%              and two opposite annihilations.
%   Section 4: gluing copies of H into one group G_0 without collapsing.
%   Section 5: enlarging to G_1 so ranks become rectangular matrix
%              identities in a single central sector.
%   Section 6: compressing to a square matrix with a one-sided inverse.
%   Section 7: encoding matrices into scalars via a finite Heisenberg
%              group.
%   Section 8: the resulting injective non-surjective cellular automaton.
% ==================================================================





















# A Counterexample to Kaplansky's Direct-Finiteness Conjecture in Odd Characteristic


maketitle

Abstract: 
Kaplansky conjectured in 1972 that the group algebra of any group
over any field would be ``directly finite'': if $ab=1$ then $ba=1$.
The conjecture is true when the field has characteristic zero, but it
fails in positive characteristic once the group is allowed to be
infinite. This paper constructs a counterexample in odd characteristic.
We exhibit one explicit odd prime~$p$, a field~$K$ of order~$p^4$,
a finitely generated group~$G$ containing torsion, and two finite
sums $a,bin K[G]$ with $ab=1$ and $bane 1$. The same two sums then
produce an injective cellular automaton on~$K^G$ that is not surjective,
so the group~$G$ is not surjunctive.


# Introduction


## The puzzle: one-sided versus two-sided inversion

Let $K$ be a field and $G$ a group. The group algebra $K[G]$
consists of all formal finite sums
[
 c_1 g_1 + c_2 g_2 + ... + c_r g_r,
 qquad c_iin K, g_iin G,
]
added coordinate by coordinate and multiplied by writing out both sides,
using the group law $g_ig_j$ and extending linearly. Two sums are equal
only when their coefficients agree on every~$g$. So $K[G]$ is like an
infinite-dimensional vector space over $K$, with $G$ itself as a basis,
plus a multiplication rule coming from the group.

Concrete example. When $G=mathbb Z$bbZ$ and $K$ is any field, the
group algebra $K[mathbb Z]$bbZ]$ is (isomorphic to) the ring of Laurent
polynomials $K[x,x^{-1}]$ in one variable: send the integer~$n$ to~$x^n$.
That ring is commutative, so left and right behave the same there.
Not every group algebra is commutative; for example, if $G$ is
nonabelian, then $K[G]$ is noncommutative.

A ring $R$ is directly finite when the equation $ab=1$, for
$a,bin R$, always implies~$ba=1$. Fields are directly finite (the
only nonzero element with a multiplicative inverse is the obvious one).
The $ntimes n$ matrix ring $Mat_n(K)$ over a field is directly finite
because linear maps on an $n$-dimensional vector space have finite
dimension as input and output. In general, any finite-dimensional
algebra over a field is directly finite: any one-sided inverse between
linear maps on an $n$-dimensional space has rank~$n$, so it is
automatically a two-sided inverse. A ring in which every matrix ring
$Mat_n(R)$, $nge1$, is directly finite is called stably finite.

Since a finite group $G$ produces a finite-dimensional algebra $K[G]$,
it is directly finite (and stably finite; the matrix rings $Mat_n(K[G])$
are again finite-dimensional). So the interesting question is about
infinite groups.

## Kaplansky's question

In his 1972 book on fields and rings, Kaplansky proved that when the
field has characteristic~$0$, the group algebra $K[G]$ is directly finite
for every group~$G$; his proof used finite von Neumann algebras. He then
asked whether the same conclusion holds in characteristic~$p>0$, where
his von Neumann-algebra method does not apply directly.

A large body of later work found positive partial answers. Ara, O'Meara,
and Perera (2002) proved stable finiteness of $K[G]$ for $G$ free-by-amenable
over any division ring. Elek and Szab'o (2004) proved stable finiteness
for every sofic group: informally, a group that can be approximated by
finite permutation models. Since many familiar infinite groups are
sofic -- all residually finite groups, all amenable groups, all free
groups, and many more -- this covered a wide range of cases.
These theorems constrain any counterexample: whatever group we build
must be far from sofic.

The purpose of this paper is to give an actual counterexample, in a
single specific odd characteristic.

## The main theorem

Put $m=binom{1200}{600}$ and let $p$ be the least integer $>1$ that
divides $(m!)^2+1$. This $p$ is an odd prime; see Lemma~lem:field.
We construct:


item a field $K$ of order $p^4$ (an explicit quadratic tower over the
      prime field $F_p$);
item a finitely generated group $G$ containing nontrivial elements of
      finite order;
item two finite sums $a,bin K[G]$ with $ab=1$ and $bane 1$.


The construction is entirely finite: every field element, every group
generator, every coefficient is produced by a finite list of operations
from fixed finite sets. No infinite search and no word-problem oracle
is needed to define $a,b$; the point of the construction is to build them
from finite data rather than by deciding equalities in~$G$.


Let $m=binom{1200}{600}$ and let $p$ be the least integer $h>1$
dividing $(m!)^2+1$. Then $p$ is an odd prime. There is a specified
field $K$ of order $p^4$, a specified finitely generated group $G$
containing torsion, and specified sums $a,bin K[G]$ satisfying
$ab=1$ but $bane 1$. In particular Kaplansky's direct-finiteness
conjecture fails in odd characteristic.


The word ``specified'' means: written as an explicit composition of
finite operations on finite sets, in an order that is fixed in advance.
Different coefficients may happen to coincide at the end; that is
harmless. What matters is that $a$ and $b$ are objective consequences
of a finite recipe, not of an arbitrary choice among infinitely many.

## Why the failure of direct finiteness matters

Two remarks connect this algebra to other topics. First, by
Elek--Szab'o, the constructed group $G$ cannot be sofic; otherwise
$K[G]$ would be stably finite, contradicting the theorem. So the
construction is also a source of non-sofic groups of a very specific
kind.

Second, direct finiteness is equivalent to a statement about ``linear
cellular automata.'' A cellular automaton on $K^G$ is any transformation
that reads a finite window of the configuration around each point and
writes a new value there. If we take, for a fixed finite sum
$c=sum c_u uin K[G]$, the rule
[
 (T_c x)(g) = sum_u c_u, x(gu),
]
then $T_c$ is always a cellular automaton (the memory set is $supp c$).
Composition behaves well: $T_c T_d = T_{cd}$. So if $ab=1$, then
$T_b$ has left inverse $T_a$, hence is injective. If $bane 1$, we can
show $T_b$ is not surjective on $K^G$. Section~sec:cellular gives
the details. The upshot is a group that fails to be surjunctive,
refuting Gottschalk's conjecture for this particular~$G$.

## The plan of the proof

The construction has five independent pieces. Each piece is fairly
self-contained; the reader may take them in whatever order feels best,
as long as the final step receives all the pieces.

Piece 1 (Section~sec:finite): finite data.
We fix the prime $p$, the field $K=F_{p^4}$ (built as a quadratic
tower so we can descend to $F_p$ for checks), and a simple triangle-free
graph~$Gamma$ on $m$ vertices with a factorization of its adjacency
matrix into a very short sum of rank-one pieces. We also define a finite
group $H=A_0rtimes P$ of order $w$ that will be the local block.

Piece 2 (Section~sec:modular): a large idempotent.
Inside the group algebra $K[H]$, we build an explicit idempotent~$e$
whose regular rank (the dimension of $eK[H]$ as a $K$-vector space)
satisfies $dim_K eK[H]/|H| > 1/96$. It also satisfies two opposite
annihilations: writing $u(s),v(s)$ for certain elements of~$H$ and
$ell=(p-1)/2$,
[
 (u(s)-1)^ell e = 0 quadandquad e,(v(s)-1)^ell = 0
 quadfor every  s.
]
The asymmetry is the point: the annihilation on the left and the
annihilation on the right use the same exponent~$ell$, but $u$ and $v$
sit in different subgroups of~$H$, so no symmetry forces them to be
compatible.

Piece 3 (Section~sec:gluing): gluing without collapsing.
We take $m$ copies $H_1,...,H_m$ of $H$ and identify one specific
cyclic subgroup across each edge of~$Gamma$. The resulting quotient
$G_0$ must remain injective on each $H_i$; if it did not, a nonzero
element of $K[H_i]$ could vanish in $K[G_0]$. A short-and-sweet
spherical-map argument proves this injectivity.

Piece 4 (Section~sec:sector): turning ranks into matrices.
Enlarge $G_0$ to a bigger group $G_1$ whose group algebra contains a
nonzero central idempotent $f$ with special properties. In the ring
$fK[G_1]$, the images of the idempotents $e_i$ become rectangular
matrix blocks with exact integer-scaled right and left inverses.
This is the technical heart of the paper: a nilpotent-ideal
change-of-basis argument turns dimension equalities over~$K$ into
equalities over the full ring.

Piece 5 (Sections~ref{sec:compression and~sec:scalar):
matrices, then scalars, then a cellular automaton.}
Using the triangle-free condition and the deliberate asymmetry from
Piece~2, we assemble all the rectangular blocks into two matrices with
one-sided inverse. Then the finite Heisenberg group from Section~sec:scalar
embeds a matrix algebra into a group algebra, letting us turn that
matrix identity into an identity between two scalar elements. Section~sec:cellular
translates it into a statement about cellular automata.

## Notation summary

All matrices below act on column vectors in free right modules
$S^n$. So multiplying a matrix by a column vector means multiplying
each entry on the left by the corresponding group algebra element.
This matters because group algebras are not always commutative.


item $K$: a field. $F_p$: the prime field of order $p$.
item $G$: a group; $K[G]$: the set of finite $K$-linear sums of
      elements of $G$, with multiplication from the group law.
item $1_K$, or just $1$: the multiplicative identity of $K$. In $K[G]$
      the identity is the group identity element, written $1_G$ or~$1$.
item $ein K[H]$: an idempotent, meaning $e^2=e$.
item $d=dim_K e K[H]$: the regular rank of $e$, i.e., the
      dimension of the image of left multiplication by~$e$ on $K[H]$.
item $w=|H|$: the order of the finite group~$H$.
item $[n]$: ${1,...,n}$ for a positive integer $n$.
item Hermitian transpose: never used here. Ordinary transpose is
      written $X^{mathsf T}sfT$, with no scalar conjugation.
item $Mat_{atimes b}(S)$: $atimes b$ matrices with entries in~$S$.


# The field, the graph, and the local group


The finite-data stage has three independent ingredients: a prime~$p$ and
a specific field $K$ of order $p^4$; a simple triangle-free graph~$Gamma$
on $m$ vertices together with an extremely compact factorization of its
adjacency matrix; and a finite group $H$ with a natural action that will
later host the crucial idempotent. Each ingredient is built once and for
all here, in the order needed later.

## The prime and the field


Recall $m=binom{1200}{600}$, a specific (very large) positive integer,
and let $p$ be the least integer $h>1$ that divides $(m!)^2+1$.
The definition of~$p$ is purely arithmetic. We need four properties
of~$p$ and one field-extension construction.


With $m=binom{1200}{600}$ and $p$ the least $h>1$ dividing
$(m!)^2+1$, we have:

item $p$ is an odd prime, and $p>m$.
item $p$ divides $(m!)^2+1$, so $-1$ has a square root in $F_p$.
item If $etainF_p^*$ is any nonsquare, then the polynomial
      $X^2-eta$ is irreducible over $F_p$ and its root field
      $K_0=F_p[xi]/(xi^2-eta)$ is a quadratic extension of $F_p$.
item The root $xi$ of $X^2-eta$ is not a square in $K_0$,
      so $X^2-xi$ is irreducible over $K_0$ and
      $K=K_0[nu]/(nu^2-xi)$ is a further quadratic extension.
      Consequently $|K|=p^4$.


Proof. 
(1) The least divisor $>1$ of any integer $n>1$ is prime: if it were
composite, one of its proper divisors would also be $>1$ and would be
a smaller divisor of~$n$. So $p$ is prime. Now, if $ple m$, then
$p$ would divide $m!$ (since $mge p$), so also $p$ would divide
$(m!)^2$; combined with $pmid (m!)^2+1$ this gives $pmid 1$,
impossible. Hence $p>m>600$. Since $mge600ge1$ and $p>mge600$,
$m!$ is even (as $mge2$), so $(m!)^2+1$ is odd, and $pne2$.
Therefore $p$ is odd.

(2) The congruence $(m!)^2equiv -1pmod p$ says that $-1$ is the
square of $m!$ modulo~$p$, that is, $-1$ is a quadratic residue in
$F_p$.

(3) A polynomial $X^2-eta$ over a field is irreducible exactly when
$eta$ is not a square in that field. Nonsquares exist in $F_p^*$
for every odd prime~$p$: the map $xmapsto x^2$ on $F_p^*$ is
two-to-one on its image, so only half of the $p-1$ elements are
squares, and $p-1ge2$ gives at least one nonsquare. For such~$eta$
the polynomial $X^2-eta$ has no roots in $F_p$, hence is irreducible
and $F_p[X]/(X^2-eta)$ is a field of $p^2$ elements.

(4) In $K_0=F_p[X]/(X^2-eta)$, the two roots of $X^2-eta$ are
$xi$ and $-xi$. Therefore $xicdot(-xi)=-xi^2=-eta$ is the
field norm of $xi$ down to $F_p$. By (2), $-1$ is a square in $F_p$.
Since $eta$ is chosen to be a nonsquare, the product $-eta$ is a
product of a square and a nonsquare, hence a nonsquare in $F_p$.

Now suppose, toward a contradiction, that $xi=y^2$ for some $yin K_0$.
Apply the field norm $N_{K_0/F_p}(u)=ucdot u'$ (where $u'$ is the
conjugate, negating the $xi$-coordinate). Because $N$ is multiplicative,
$N(xi)=N(y^2)=N(y)^2$, which would exhibit the nonsquare~$-eta$
as a square in $F_p$. That is impossible. So $xi$ is not a square
in~$K_0$, and hence $X^2-xi$ is irreducible over~$K_0$. The quotient
$K=K_0[nu]/(nu^2-xi)$ is therefore a field of $|K_0|^2=p^4$ elements.


From now on, $K$ is the specific field $K=F_{p^4}$ supplied by
Lemma~lem:field. We descend to $F_p$ only when we need to check
things like ``$-1$ is a square.'' All our formulas over $K$ are
already fixed.

Several additional choices are needed below. Because we want the
construction to be ``specified'' in the sense of the introduction,
we spell out an explicit finite recipe for each choice.


item Representatives and order on $F_p$.
      Identify $F_p$ with ${0,1,...,p-1}$ using the remainder
      in $0,...,p-1$, so that $F_p$ has a natural total order.
      Choose $eta$ as the least nonsquare in $F_p^*$ under this order.
item Representatives and order on $K$.
      Write every element of $K$ uniquely as
      $c_0+c_1xi+c_2nu+c_3xinu$ with $c_jinF_p$. Order $K$ by
      the lexicographic order on $(c_0,c_1,c_2,c_3)$. This gives a
      total order on $K$.
item A generator $zeta$ of $K^*$. Put $M=p^4-1$.
      Choose the least element $zeta$ of $K^*$ whose multiplicative
      order equals $M$. Such an element exists; the reasoning is
      standard but we include it for completeness below.


Why does an element of order $M$ exist? Let $b$ be the least common
multiple of all element orders in $K^*$. Conventionally $ble M$ because
every element of $K^*$ has order at most $M$. On the other hand, every
element of $K^*$ is a root of $X^b-1$ (because each element's order
divides~$b$), so $X^b-1$ has at least $M$ distinct roots. A nonzero
polynomial over a field has at most as many roots as its degree, so
$Mle b$. Hence $b=M$. Now, by the definition of least common multiple,
we can choose elements of $K^*$ whose orders are the prime powers
occurring in the factorization of $M$; raising appropriates elements to
the right powers gives an element of order exactly each prime power
factor. Their product, being the product of commuting elements of
pairwise coprime orders, has order exactly $M$. So an element $zeta$
of order $M$ exists.

In particular $M=p^4-1$ and all of its powers are invertible in $K$
(equivalently: the multiplicative group of $K$ is cyclic of order
$M=p^4-1$). We will divide by various integers below; every such
integer is a factor of~$M$ and hence nonzero in~$K$.

## The graph and the low-rank fit


The second finite ingredient is a simple triangle-free graph~$Gamma$
on many vertices whose adjacency matrix admits a factorization into
a number of rank-one pieces that is very small compared to the number
of vertices. That is what allows Section~op:compression-section
to build a ``rank paradox'' with which the odd-characteristic
counterexample becomes possible.

Set $[1200]={1,2,...,1200}$. Enumerate all six-hundred-element
subsets $I⊆[1200]$ in increasing lexicographic order (comparing
subsets as increasing lists of integers) and denote them
$I_1,...,I_m$ with $m=binom{1200}{600}=binom{1200}{600}$. Remember
this same~$m$ is the one appearing in the definition of~$p$.

Define a simple graph $Gamma$ on vertex set ${1,...,m}$ by
declaring the distinct vertices $ine j$ to be adjacent exactly when
the intersection $I_icap I_j$ has fewer than $200$ elements:
[
 isim j quadiffquad |I_icap I_j| < 200.
]
By convention a vertex is never adjacent to itself, so the graph is
simple.


The graph $Gamma$ is simple and triangle-free. Let
[
 mathcal T=calT={T⊆[1200]:|T|le 400},qquad
 t=|mathcal T|=calT|=sum_{j=0}^{400}binom{1200}{j}.
]
There exist coefficients $alpha_i(T)$ and $beta_j(T)$ in $F_p$,
indexed by $Tinmathcal T$,calT$, such that the $mtimes m$ matrix
$F$ given by
[
 F_{ij}=sum_{Tinmathcal T}calTalpha_i(T),beta_j(T)
]
satisfies $F_{ii}=1$ for every $i$ and $F_{ij}=0$ for every pair of
distinct nonadjacent vertices~$i,j$. Moreover $t/m<1/100$.

Proof. 
Triangle-free. Suppose $i,j,k$ are pairwise adjacent. Then each
of the three pairwise intersections has at most $199$ elements (since
``fewer than $200$'' and integer valued). So
[
 |I_icup I_jcup I_k| ge |I_i|+|I_j|+|I_k| - |I_icap I_j| - |I_jcap I_k| - |I_kcap I_i|
 ge 3cdot 600 - 3cdot 199 = 1203,
]
by inclusion-exclusion. But the union is contained in $[1200]$, which
has only $1200$ elements. Contradiction. So $Gamma$ has no triangles.

The fit. Pick, for each $i$, the indicator function
[
 alpha_i(T)=1,&T⊆ I_i,0,&otherwise.
]
To build $beta_j$, define the following polynomial in the formal
variables $X_1,...,X_{1200}$ over $F_p$:
[
 Q_j(X)=prod_{k=200}^{599}frac{sum_{xin I_j}X_x-k}{600-k}.
]
Every denominator lies in ${1,2,...,400}$, hence is invertible
in $F_p$ because~$p>600>400$. Expand $Q_j$ as $sum_alpha c_alpha X^alpha$
with $c_alphainF_p$ and multi-indices $alphainmathbb N^bbN^{[1200]}$
(so $X^alpha=prod_x X_x^{alpha_x}$). Define the square-free
reduction of $Q_j$ to be
[
 Q_j^{sf}(X)=sum_alpha c_alphaprod_{x:alpha_x>0} X_x,
]
in which every positive exponent has been replaced by $1$. Set
$beta_j(T)$ to be the coefficient of $prod_{xin T}X_x$ in
$Q_j^{sf}$ for each $T⊆[1200]$. Because $Q_j$ has
total degree $400$ (a product of $400$ linear forms), only the
$Tinmathcal T$calT$ can appear. The total degree of $Q_j$ bounds the
support of beta_j exactly to subsets of size at most 400.

Evaluation on $0$-$1$ vectors. The square-free reduction does
not change the value of the polynomial at any $0$-$1$ point (because
$0^n=0$ and $1^n=1$ for every $nge1$). In particular, evaluate at the
indicator vector $1_{I_i}in{0,1}^{[1200]}$ (entry $1$ at positions
$xin I_i$, entry $0$ elsewhere). On the one hand,
[
 Q_j(1_{I_i})
 =prod_{k=200}^{599}(|I_icap I_j|-k)/(600-k).
]
On the other hand, expanding $Q_j^{sf}$ and evaluating at
$1_{I_i}$, each monomial $prod_{xin T}X_x$ contributes $1$ if
$T⊆ I_i$ and $0$ otherwise. So
[
 Q_j(1_{I_i})
 =sum_{Tinmathcal T}calTalpha_i(T),beta_j(T)=F_{ij}.
]
Equating the two evaluations gives

 F_{ij}=prod_{k=200}^{599}(|I_icap I_j|-k)/(600-k).


Fit conditions. If $i=j$ then $|I_icap I_j|=600$, so every
numerator $600-k$ cancels the corresponding denominator, giving
$F_{ii}=1$. If $ine j$ are nonadjacent then $|I_icap I_j|ge200$ and
$le 599$, so the factor with $k=|I_icap I_j|$ is exactly zero,
forcing $F_{ij}=0$. For adjacent distinct pairs the product is
generally nonzero, but we do not need any particular value; only the
diagonal and the nonedge vanishing matter. This is the threshold-Kneser
polynomial specialization of cite[Proposition~13]{Haviv2018Theta}
and cite[Theorem~3.2]{GolovnevHaviv2022}.

The ratio bound. Combinatorial estimates. The binomial
coefficients $binom{1200}{j}$ increase with~$j$ as long as $jle599$
(because $binom{n}{j+1}/binom{n}{j}=(n-j)/(j+1)>1$ when $j<(n-1)/2$
and $n=1200$). So on the sum defining $t$, the largest term is at
$j=400$, and
[
 t le 401binom{1200}{400}.
]
For $m=binom{1200}{600}$ we can compare factorials directly:
[
 frac{binom{1200}{400}}{binom{1200}{600}}
 =prod_{u=401}^{600}(u)/(u+200)
 le (tfrac 57)^{100}.
]
Here the inequality is a crude but adequate estimate: for
$ule 500$, the factor $u/(u+200)$ is at most $500/700=5/7$; for
$uge501$, the factor is at most $600/800=3/4<1$, so it contributes
less than one. Multiplying all one hundred factors gives the displayed
bound. Then
[
 frac tmle 401(tfrac 57)^{100}.
]
The cube of $5/7$ is $125/343<1/2$, so $(5/7)^{99}<(1/2)^{33}$. Thus
$ (5/7)^{100}<(1/2)^{33} $ as well. Multiplying by $401<40100<2^{33}$
gives
[
 frac tm<2^{33}cdot frac1{2^{33}}=1,
]
which is weaker than needed; more precisely,
[
 100 cdot frac tm < 40100(tfrac 57)^{100}
 <frac{40100}{2^{33}}<1,
]
so $t/m<1/100$.


Now we have our two finite combinatorial ratios. The first is
$t/m<1/100$: the low-rank fit uses far fewer summands than there are
vertices. The second, coming from the group $H$ below, is
$d/w>1/96$: the idempotent each vertex carries has a regular rank
that is a fixed nonzero fraction of~$|H|$. Section~op:compression-section
will combine the two ratios into a matrix with strict inequality
$wt<md$ between its shapes.

## The finite group $H$


The third finite ingredient is the local group. It is where the large
idempotent lives, and it is where the crucial ``one-sided annihilation
in each direction'' happens.

Let $P=(F_p)^3$ be the additive group of three-dimensional column
vectors over $F_p$. It has $p^3$ elements. Let $M=p^4-1$, as in the
field construction, and let
[
 A_0=(mathbb Z/MbbZ/Mmathbb Z)^PbbZ)^P
]
be the group of functions $a:Ptomathbb Z/MbbZ/Mmathbb Z$,bbZ$, with
addition defined pointwise: $(a+a')(x)=a(x)+a'(x)$ for each $xin P$.
This is a finite abelian group of order $M^{p^3}$.

The group $P$ acts on $A_0$ by translation: for $sin P$ and
$ain A_0$, define $scdot ain A_0$ by
[
 (scdot a)(x)=a(x-s), qquad xin P.
]
This is a group action: $0cdot a=a$ and $(s+t)cdot a=scdot(tcdot a)$.
Form the semidirect product
[
 H=A_0rtimes P, qquad
 (a,s)(a',s')=(a+scdot a', s+s').
]
The identity of $H$ is $(0,0)$. The inverse of $(a,s)$ is
$(-s^{-1}cdot a, -s)$, i.e., $(-(-s)cdot a,-s)$ since in characteristic
$p$ subtraction is the same as~$+(-s)$. Concretely: $(a,s)(-(-s)cdot a, -s)=(a-scdot((-s)cdot a), 0)=(a-scdot(-scdot a), 0)=(a-0,0)=(0,0)$.
The order of $H$ is
[
 w:=|H|=|A_0|cdot|P|=M^{p^3}cdot p^3.
]
So $H$ is finite. The group algebra $K[H]$ is thus a
finite-dimensional algebra over $K$, of dimension $w$ as a $K$-vector
space (and $w^2$ as a $K$-algebra of linear maps on $K^w$).

The two subgroups of $H$ that matter now are $U$ and $V$, defined
below. Both are isomorphic to $P$, but they sit inside $H$ in different
ways.

Translation subgroup. Define
[
 u(s)=(0,s),qquad U={u(s):sin P}⊆ H.
]
Because $(0,s)(0,s')=(0,s+s')$, the map $smapsto u(s)$ is an
isomorphism $Pto U$.

Characteristic element. Let $cin A_0$ be the function
[
 c(0)=1,quad c(x)=0 for xne0.
]
The group law gives $(c,0)$ the exact order $M$ in $H$ (as an element
of the abelian normal subgroup $A_0$).

Conjugate subgroup. Define
[
 v(s)=c,u(s),c^{-1},qquad V={v(s):sin P}⊆ H,
]
where $c$ in the formula denotes $(c,0)in H$ and $c^{-1}=(-c,0)$
uses the additive inverse in $A_0$. A short computation with the
group law in $H$ gives the explicit form

 v(s)=(c-scdot c, s),qquad sin P.

Indeed $(c,0)(0,s)=(c,s)$ and $(c,s)(-c,0)=(c+scdot(-c),,s)=(c-scdot c,s)$.


The subgroups $U$ and $V$ satisfy $Ucap V={1}$, and $Ucong Vcong P$.

Proof. 
Suppose $(0,0)=u(s)=v(s')$ for some $s,s'in P$. Comparing second
coordinates gives $s=s'$. Comparing first coordinates gives
$0=c-scdot c$, i.e., $c=scdot c$. The left side evaluates at $0$ to
$c(0)=1$; the right side evaluates at $0$ to $(scdot c)(0)=c(-s)$.
But $-sne 0$ when $sne0$, and $c$ vanishes away from the origin, so
$c(-s)=0$. Thus $s=0$, and the only common element is the identity.
The isomorphism statements follow from the displayed definitions:
$smapsto u(s)$ is a bijection $Pto U$ preserving the group law, and
$smapsto v(s)$ is a conjugate of~$smapsto u(s)$ inside the group~$H$,
hence also isomorphic to $P$.


Why does this matter? In Section~sec:modular we shall build an
idempotent~$e$ with
[
 (u(s)-1)^ell e = 0,qquad e,(v(s)-1)^ell=0
 quadfor every sin P,
]
where $ell=(p-1)/2$. The first annihilation uses $u(s)in U$ on the
left; the second uses $v(s)in V$ on the right. Because $Ucap V={1}$,
the two sides do not have to agree, and no symmetry forces either one
onto the other. This asymmetry is what makes the later triangular
compression work.

That completes the finite data. In later sections, we always write
$m=binom{1200}{600}$, $t=|mathcal T|$,calT|$, $w=|H|$, and
$d=dim_KeK[H]$ for the regular rank of the idempotent $e$ we
are about to build in Section~sec:modular.

# The large idempotent with ordered annihilations


This section is the technical heart of the paper. In the previous
section we built three pieces of finite data: a prime $p$, a field
$K$ of order~$p^4$, and a finite group $H=A_0rtimes P$ with two
different subgroups $U,Vcong P$ meeting trivially. Now we use all that
data to build one particular idempotent $ein K[H]$ with two properties:


item Large regular rank. The dimension $d=dim_K(eK[H])$
      of the image of left multiplication by $e$ satisfies
      $d/w>1/96$, where $w=|H|$.
item Opposite annihilations. Writing $ell=(p-1)/2$, we have
      $(u(s)-1)^ell e=0$ and $e,(v(s)-1)^ell=0$ for every $sin P$.


The construction proceeds in three stages.


item Ssubsec:B-def: identify a subspace $B⊆ K^P$ on
      which both $u(s)$-shifts and $v(s)$-shifts have the same
      annihilation behavior. This requires a piece of translation
      calculus (the operators $X_j$) and care with degrees.
item Ssubsec:admissibility: use the polynomial identity test of
      Schwartz and Zippel to produce many ``admissible'' characters
      $lambdainA_0hat$, i.e., characters $lambda$ for which
      a certain Gram matrix~$N_lambda$ is nonsingular.
item Ssubsec:idempotent: assemble these ingredients into an
      idempotent $e$ spread over many matrix-block summands of $K[H]$,
      compute its regular rank exactly, and verify the annihilations.


A last subsection (Ssubsec:edge-zero) turns the above
annihilations into the ``edge products vanish'' identity used later.

Throughout, we do all linear algebra over~$K$ first, then lift to
$K[H]$ using the Fourier idempotents of the abelian normal subgroup
$A_0⊆ H$.

## The annihilated subspace $B⊆ K^P$


Let $ell=(p-1)/2$ and $D=3(p-1)$. Work in the $K$-vector space $K^P$
of functions $Pto K$, with standard basis $mathbf e_x$bfe_x$ (a $1$ at
$x$ and $0$ elsewhere). We want a linear subspace on which left shifts
and right shifts both annihilate $ell$-fold.

Translation calculus. For $sin P$ let $L_s:K^Pto K^P$ be the
shift operator $L_smathbf e_x=bfe_x=mathbf e_bfe_{x+s}$. Define three operators
[
 X_j=L_{ε_j}-1_{K^P}, qquad j=1,2,3,
]
where $ε_j$ are the standard generators of $P=F_p^3$.

The $L_s$ commute because the group $P$ is abelian. So the $X_j$ commute
as well. A stronger fact: because we are in characteristic~$p$, the
binomial coefficients $binom pk$ are divisible by $p$ for $1le kle p-1$;
so $(1+X_j)^p=1+X_j^p$ and
[
 X_j^p=(L_{ε_j}-1)^p = L_{pε_j}-1 = L_0-1 = 0.
]
Thus each $X_j$ is nilpotent of index at most $p$. These are the
``differential operators of order 1'' associated to the three
generators of $P$.

[Monomial basis]
The $p^3$ vectors
[
 X_1^{n_1}X_2^{n_2}X_3^{n_3}mathbf e_0,bfe_0, qquad 0le n_1,n_2,n_3< p,
]
form a $K$-basis of $K^P$.

Proof. 
The standard basis ${mathbf e_x:xbfe_x:xin P}$ already has cardinality
$p^3=dim_KK^P$. So it suffices to show every $mathbf e_s$bfe_s$ is in the
$K$-span of the displayed vectors.

Fix $s=(s_1,s_2,s_3)in P$. Since $1+X_j=L_{ε_j}$, we have
$(1+X_j)^{s_j}=L_{s_jε_j}$ and
[
 mathbf e_s=L_sbfe_s=L_smathbf e_0bfe_0
 =prod_{j=1}^3 L_{s_jε_j}mathbf e_0bfe_0
 =prod_{j=1}^3 (1+X_j)^{s_j}mathbf e_0bfe_0
 =prod_{j=1}^3 (sum_{k=0}^{s_j}binom{s_j}{k}X_j^k)mathbf e_0.bfe_0.
]
The last product expands to a $K$-linear combination of the vectors
$X_1^{n_1}X_2^{n_2}X_3^{n_3}mathbf e_0$bfe_0$ with $0le n_jle s_j<p$.
So $mathbf e_s$bfe_s$ lies in the span of the display. Since ${mathbf e_sbfe_s}$
spans, the display spans, and it has $p^3$ elements, so it is a basis.



The lemma can be re-read as ``polynomials in $X_1,X_2,X_3$ of degree
$<p$ in each variable are a basis of $K^P$''. This is precisely the
finite-dimensional analogue of the polynomial ring $K[X_1,X_2,X_3]$,
truncated by $X_j^p=0$.


Define $B$ as the matrix with columns the basis vectors whose total
degree is large enough:

 B := [X_1^{n_1}X_2^{n_2}X_3^{n_3}mathbf e_0]_bfe_0]_{
 substack{0le n_1,n_2,n_3<p n_1+n_2+n_3ge D-ell+1}}.

So $B$ is a $p^3times h$ matrix with $K$-linearly independent columns
(they are a subset of a basis). The integer $h$ counts the columns.

[Two-sided annihilation of $B$]
For every $sin P$,
[
 (L_s-1)^ell,B=0,qquad B^{mathsf T}sfT(L_s-1)^ell=0.
]

Proof. 
First identity. Fix $sin P$ and write $s=sum_j s_jε_j$.
Expand $L_s-id_{K^P}$:
[
 L_s-1 = prod_{j=1}^3 L_{s_jε_j} - 1
 = prod_{j=1}^3 (1+X_j)^{s_j} - 1.
]
Expanding the right side, every nonzero monomial has total $X$-degree
at least one (because the constant term $1$ cancels). Therefore the
$ell$th power $(L_s-1)^ell$ has the property: applied to any monomial
of total $X$-degree $d$, the result lies in the $K$-span of monomials
of total $X$-degree at least $d+ell$.

Now take a column $X_1^{n_1}X_2^{n_2}X_3^{n_3}mathbf e_0$bfe_0$ of $B$,
with $d=n_1+n_2+n_3ge D-ell+1$. Applying $(L_s-1)^ell$ gives a
combination of monomials of total degree at least $D+1$. But every
monomial of total degree greater than $D=3(p-1)$ has some exponent
at least $p$, and $X_j^p=0$ kills it. So each column is annihilated,
proving the first identity.

Second identity. Compute the transpose of $L_s$: its matrix entry
$(L_s)_{mathbf e_x,bfe_x,mathbf e_y}bfe_y$ (row $x$, column $y$) is $1$ when
$x+s=y$ and $0$ otherwise. Hence $(L_s^{mathsf T}sfT)_{mathbf e_y,bfe_y,mathbf e_x}bfe_x$
is $1$ when $x-s=y$, so $L_s^{mathsf T}sfT=L_{-s}$. Consequently
$(L_s-1)^{mathsf T}sfT=L_{-s}-1$, and
[
 B^{mathsf T}sfT(L_s-1)^ell = ((L_{-s}-1)^ell B)^{mathsf T}sfT = 0^{mathsf T}sfT=0,
]
using the first identity with $-s$ in place of $s$.


[Number of columns]
The integer $h$ equals $binom{ell+2}{3}$, and
[
 (h)/(p^3)=((p-1)(p+1)(p+3))/(48,p^3)>frac1{48}.
]

Proof. 
Make the substitution $a_j=p-1-n_j$, $j=1,2,3$. Then $a_jge0$ and
$sum a_j=D-sum n_j$. The condition $sum n_jge D-ell+1$ becomes
$sum a_jle ell-1$. Each $a_jle p-1$ is automatic, because
$ell-1=(p-1)/2-1<p-1$ forces $sum a_j<p-1$, making each $a_j<p-1$.
Thus $h$ is the number of triples $(a_1,a_2,a_3)inmathbb N^3$bbN^3$ with
$sum a_jleell-1$. Stars and bars (distribute $leell-1$ identical
balls into $3$ labelled bins) gives
[
 h=binom{(ell-1)+3}{3}=binom{ell+2}{3}.
]
Now $ell=(p-1)/2$, so
[
 binom{ell+2}{3} = ((ell+2)(ell+1)ell)/(6)
 = ((p+3)(p+1)(p-1))/(48).
]
Divide by $p^3$: $h/p^3=(p+3)(p^2-1)/(48,p^3)$. To compare with
$1/48$, compute the difference
[
 (p+3)(p^2-1)-p^3=3p^2-p-3>0 quadfor pge3,
]
which gives $h/p^3>1/48$.


To summarize the situation in one line: $B$ is a tall matrix whose
columns are the ``high-degree part'' of $K^P$, and both $u(s)$-shifts
and their transposes kill $B$ after $ell$ applications. The fraction
$h/p^3$ is at least $1/48$ of the ambient dimension.

We should remark what is special about the value $ell=(p-1)/2$.
Choosing $ell$ smaller would shrink $B$'s fraction too much; choosing
$ell$ larger would not annihilate $B$ at all (the top-degree columns
would survive). The exponent $ell$ is exactly the right size to
simultaneously annihilate on both sides while keeping $B$ fat.

## Choosing a compatible projection


Our ultimate idempotent $e$ will be a block-diagonal sum, one block per
character of~$A_0$. Each block is a projection matrix onto the image
of~$B$. The two opposite annihilations we want follow automatically
from Lemma~lem:B-annihilation once $e$ is a projection onto
$im B$. But $e$ must live inside $K[H]$, and there the two shifts
$u(s)$ and $v(s)$ act through matrix representations of different
shapes. This subsection shows that for most characters the
corresponding block projection exists and is nonsingular.

Characters of $A_0$.: 
$A_0=(mathbb Z/MbbZ/Mmathbb Z)^P$bbZ)^P$ is finite abelian of order
$|A_0|=M^{p^3}$. A character is a homomorphism
$lambda:A_0to K^*$. It is uniquely determined on the coordinate
generators $c_x$ (the function with value~$1$ at $xin P$ and $0$
elsewhere): $lambda(c_x)=zeta^{a_x}$ for some
$a_xin{0,...,M-1}$. Because $zeta$ has order $M$ and is an
element of~$K$, every character has values in~$K$.

The shift group $P⊆ H$ acts on characters by
$(slambda)(a)=lambda((-s)cdot a)$. Conjugating the Fourier
idempotent $p_chi^{A_0}$ of a character by $u(s)$ gives
[
 u(s),p_chi^{A_0},u(s)^{-1}=p_{schi}^{A_0}.
]

The diagonal matrix and the Gram form.: 
For $lambdainA_0hat$ abbreviate $chi_x=xlambda$ (the
translate of $lambda$ by $x$) and define the diagonal
$p^3times p^3$ matrix

 D_lambda=diag!(chi_x(c):xin P).

Every entry lies in $K^*$ because $chi_x$ is a character and $c$ is
a group element. So $D_lambda^{-1}$ exists and is diagonal.

The matrix

 N_lambda=B^{mathsf T}sfT,D_lambda^{-1},B

is a symmetric $htimes h$ matrix over~$K$.

Call $lambda$ admissible if

item its $P$-stabilizer is trivial, i.e., the orbit $Plambda$ has
      size exactly $p^3$; and
item $N_lambda$ is invertible.

Both conditions are checkable in finite time, and the check is
deterministic: enumerate the $p^3$ translates and compute one
$htimes h$ determinant.

Most characters are admissible.: 
The two modes of failure each account for less than half of the
characters. Their union is then smaller than half, so more than half
succeed. This count is the key estimate of the whole construction.


More than half of the $|A_0|$ characters are admissible.

Proof. 
Stabilizers. Fix a nonzero $sin P$. Translation by $s$
partitions $P$ (of size $p^3$) into $p^2$ orbits of size~$p$. A
character $lambda$ is fixed by $s$ if and only if $lambda(c_x)$ is
constant on every such orbit, so exactly $M^{p^2}$ characters are
fixed. The union over the $p^3-1$ nonzero $s$ therefore has size at
most $(p^3-1)M^{p^2}$, i.e. a fraction at most
[
 (p^3-1),M^{-p^2(p-1)}
 le (p^3-1)/M < 1/4 .
]
The last inequality uses $M=p^4-1>4p^3$, which holds for $pge5$;
we have $p>600$.

Singular $N_lambda$. The entries of $D_lambda^{-1}$ range
independently over $K^*$ as $lambda$ ranges over all characters of
$A_0$, because $chi_x(c)$ for distinct $x$ are independent characters.
Introduce independent variables $tau_x$ and Cauchy--Binet gives

 Q(tau):=det!(B^{mathsf T}sfTdiag(tau_x)_{xin P}B)
 =sum_{substack{J⊆ P|J|=h}}det(B_J)^2prod_{xin J}tau_x ,

where $B_J$ is the $htimes h$ submatrix of $B$ consisting of the
rows indexed by~$J$, taken in the fixed increasing order.

The right side is a sum of distinct monomials (different $J$ give
different exponent vectors), so it is a nonzero polynomial. Its total
degree is exactly~$h$. Because $B$ has full column rank by
Lemma~lem:monomial-basis, some maximal minor $B_J$ is nonzero.
The polynomial $Q$ therefore has a nonzero leading monomial and does
not cancel.

Now apply Schwartz's grid bound~[cite] (see also
Zippel~[cite]): a nonzero polynomial of total degree at
most~$a$ vanishes on at most an $a/M$ fraction of a product grid whose
coordinates each range over $M$ values. Here $Q$ has degree $h$ and
the grid is $(K^*)^{p^3}$ of side $M$. Thus $Q$ vanishes on at most
the fraction $h/M$ of characters. Since $hle p^3$ (it counts a
subset of $K^P$) and $M=p^4-1$, this is at most
[
 (h)/(M)le(p^3)/(p^4-1)<frac14 ,
]
because $p^4-1>4p^3$ for $pge5$.

Combining: fewer than $1/4+1/4=1/2$ of characters fail either
condition. So more than half admit a trivial stabilizer and an
invertible Gram form simultaneously.


## Realizing the projection in $K[H]$


Each admissible character $lambda$ gives a projection $T_lambda$ on
the $p^3$-dimensional block attached to~$lambda$. The task is to
write that projection as an element of $K[H]$ whose regular rank we
can compute. The Fourier idempotents do this job: for each character
$lambda$, the products $p_{xlambda}u(s)$ (for $x,sin P$) form a
$K$-basis of one matrix block of $K[H]$. Then we sum over $lambda$.

One character, one block.: 
Fix $lambdainA_0hat$ with trivial $P$-stabilizer. For
$x,yin P$ set

 E_{xy}^{lambda}=p_{xlambda}^{A_0},u(x-y).

Because $u(s),p_{xlambda}u(s)^{-1}=p_{(x+s)lambda}$, the row
indices line up with the shift. Fourier orthogonality gives

 E_{xy}^{lambda}E_{zt}^{lambda}=delta_{yz},E_{xt}^{lambda}.

Indeed, the Fourier product survives when $(x-y+z)lambda=xlambda$,
i.e. $(y-z)lambda=0$, which by the trivial stabilizer forces $y=z$.

Put $q_lambda=sum_{xin P}p_{xlambda}^{A_0}$. Because $q_lambda$
commutes with $A_0$ and $P$ permutes its summands, $q_lambda$ is a
central idempotent. The basis ${p_{xlambda}u(s)}_{x,sin P}$
identifies the ideal $q_lambda K[H]$ with the matrix algebra
$Mat_{p^3}(K)$, via $u(s)mapsto L_s$ and $cmapsto D_lambda$.

Explicit projection.: 
Define

 T_lambda=B,N_lambda^{-1}B^{mathsf T}sfTD_lambda^{-1}
 inMat_{p^3}(K).

Because $N_lambda=B^{mathsf T}sfTD_lambda^{-1}B$, we have
[
 T_lambda B=B,qquad
 T_lambda^2=T_lambda.
]
So $T_lambda$ is a projection. It fixes each column of $B$, so
$im B⊆im T_lambda$; and it factors through $B^{mathsf T}sfT$,
so $im T_lambda⊆im B$. Hence $im T_lambda=im B$ and
$rankT_lambda=h$.

Define an element of the $lambda$-block of $K[H]$:

 e_lambda=sum_{x,yin P}(T_lambda)_{xy},E_{xy}^{lambda}.

By the matrix-unit relation~(eq:E-mult),
$e_lambda^2=e_lambda$. The action of $H$ on this block is the
matrix action of $T_lambda$.

The two annihilations.: 
Left multiplication by $u(s)$ in this block is $L_s$. Therefore
[
 (L_s-1)^ell,T_lambda
 =(L_s-1)^ell B;N_lambda^{-1}B^{mathsf T}sfTD_lambda^{-1}
 =0,
]
using $(L_s-1)^ell B=0$ from Lemma~lem:B-annihilation. The
conjugate $v(s)$ acts by $D_lambda L_sD_lambda^{-1}$, so
[
 D_lambda L_s D_lambda^{-1}-1=D_lambda(L_s-1)D_lambda^{-1}.
]
Combining with the transpose identity $B^{mathsf T}sfT(L_s-1)^ell=0$:
[
 B^{mathsf T}sfTD_lambda^{-1}(D_lambda L_s D_lambda^{-1}-1)^ell
 =B^{mathsf T}sfT(L_s-1)^ell D_lambda^{-1}=0.
]
Hence $(u(s)-1)^ell e_lambda=0$ and
$e_lambda(v(s)-1)^ell=0$ in $K[H]$.

Summing over characters.: 
Blocks for distinct orbits are orthogonal: if $Plambdane Plambda'$
then $e_lambda e_{lambda'}=0$. Choose the least admissible character
in each $P$-orbit that contains one, and let $mathscr R$scrR$ be the set
of chosen characters. Define

 e=sum_{lambdainmathscr R}scrRe_lambda in K[H].

By orthogonality the sum is an idempotent: $e^2=e$. The two
annihilations persist on~$e$.

The regular rank.: 
Left multiplication by $T_lambda$ on $Mat_{p^3}(K)$ has image the
matrices whose $p^3$ columns all lie in~$im B$, of dimension $p^3h$.
Summing over the blocks:
[
 d:=dim_K(eK[H])=p^3,h,|mathscr R|.scrR|.
]
The admissible characters form more than half of $A_0hat$
(Lemma~lem:good-count), and each $P$-orbit has size $p^3$, so
[
 |mathscr R|>(|A_0|)/(2p^3).scrR|>(|A_0|)/(2p^3).
]
Recall $w=|H|=|A_0|,p^3$. Therefore
[
 frac dw=(p^3h|mathscr R|)/(|A_0|p^3)scrR|)/(|A_0|p^3)
 =(h|mathscr R|)/(|A_0|)scrR|)/(|A_0|)
 >(h)/(2p^3)>frac1{96},
]
using $h/p^3>1/48$ from Lemma~lem:h.


There is a specified idempotent $ein K[H]$ and positive integers
$d,w$ with $w=|H|$, $d=dim_KeK[H]$, $d/w>1/96$, satisfying for
every $sin P$
[
 (u(s)-1)^ell,e=0,qquad
 e,(v(s)-1)^ell=0 .
]
Its coefficients are obtained by finite operations in the specified
field $K$ of Lemma~lem:field.


Remark on $ell$. Choosing $ell$ smaller would shrink $B$'s fraction
below what we need; choosing $ell$ larger would not annihilate the
top-degree columns of $B$, so the identities would fail. The exponent
$ell=(p-1)/2$ is exactly the right size.

## Ordered annihilations at edge level


Now take $m$ copies $H_1,...,H_m$ of $H$, one per vertex of
$Gamma$. For each edge $i<j$ identify the cyclic subgroup generated
by $v(1,barbar j,j,barbar j^2)$j^2)$ in $H_i$ with the one generated by
$u(1,barbar i,i,barbar i^2)$i^2)$ in $H_j$, where the bar denotes residues
in~$F_p$. Let $G_0$ be the resulting free-product quotient. We prove
in Section~sec:gluing that $H_ito G_0$ is injective; here we
only need the algebraic fact that the edge products vanish.

Denote by $e_iin K[G_0]$ the image of the idempotent $e$ under the
map $H_ito G_0$.


For every edge $i<j$ of $Gamma$, $e_ie_j=0$ in $K[G_0]$.

Proof. 
Let $yin K[H_i]⊆ K[G_0]$ denote the common generator of
order $p$ across the edge, and put $X=y-1$. On the $H_i$ side we
have $e_iX^ell=0$ (as $y=v(s)$ is the conjugating shift); on the
$H_j$ side we have $X^ell e_j=0$ (as $y=u(s)$ is the incoming
shift).

Work inside $K[H_i]$, which is a free right $K[< y>]$-module
of rank $w/p$: pick representatives $a_1,...,a_{w/p}$ of the left
cosets of $< y>$ in $H_i$. Then
$e_i=sum_a a,q_a$ with $q_ain K[< y>]$.

The cyclic group algebra is $K[< y>]=K[X]/(X^p)$ because
$(1+X)^p=1+X^p$ in characteristic $p$. Inside this quotient the right
annihilator of $X^ell$ is precisely the principal ideal
$(X^{p-ell})$, since $X^{ell+j}=0$ in $K[X]/(X^p)$ iff
$ell+jge p$.

Thus $q_aX^ell=0$ forces $q_a=q_a'X^{p-ell}$, and
[
 e_i=q,X^{p-ell}quadforquad q=sum_a a,q_a'in K[H_i].
]

Because $p-ell=ell+1$,
[
 e_ie_j=q,X^{ell+1}e_j=q,X,(X^ell e_j)=0.
]
No factor is commuted past $X$, no symmetry is used, and no reverse
product $e_je_i$ is asserted.


Summary so far.: 
We have a minimal exceptional spherical map: connected, on the sphere,
with exactly one face of nonidentity value, and minimal among all such.
We now perform local reductions. Each reduction either produces a
strictly smaller exceptional map (contradiction to minimality) or
forces a local restriction on the configuration. After the reductions,
the restrictions combine with Euler's formula to give a final
contradiction.

Reduction 1: every edge is nonneutral.: 
Suppose first that a nonloop edge is neutral. Contract it: edges with
value $1$ and their darts disappear from the boundary-word description,
and the graph stays connected. Face evaluations are unchanged, since
the two neutral darts contributed nothing. Minimality fails.

If a neutral edge is a loop, keep the side containing the exceptional
face; the retained side is connected, all its faces retain their
evaluations, and the discarded loop disappears. Minimality fails.

Hence every edge carries a nontrivial label.

Reduction 2: every edge is a nonbridge.: 
Suppose an edge is a bridge with value $s$. Deleting it splits the map
into two connected components, and the unique boundary walk of each
adjacent face splits into two walks, one per component. After suitable
choice of starting point and orientation, the old walk is
$W_1,s,W_2,s^{-1}$, where $W_1,W_2$ are the two split walks.

If some $W_a$ has nonidentity value, keep the component containing it,
with the same face type as before. This component is connected and has
exactly one exceptional face (that of $W_a$). Minimality fails.

If both $W_a$ are trivial, the original face was either ordinary or
exceptional. If it was ordinary, the exceptional face is on one of the
two components; keep that one. If the original face was the unique
exceptional one, both $W_a$ are trivial (this was assumed), so $sWs^{-1}$
was the exceptional word; keep the component whose walk is the whole
$sWs^{-1}$ from the other side. In every case, a smaller exceptional map
results.

So every edge is a nonbridge.

Reduction 3: the two faces across an edge have distinct types.: 
Suppose an edge separates two faces $Phi,Phi'$ of the same type $iin
V(Delta)$. Delete the edge and merge the two faces into one of type
$i$. If the boundary walk of $Phi$ near the edge reads $sD$ and that
of $Phi'$ reads $s^{-1}E$ (with the shared edge contributing $s$ on
one side and $s^{-1}$ on the other, and $D,E$ the remaining letters),
the merged walk reads $DE$. Direct computation gives

 DE=s^{-1}(sD)s,(s^{-1}E).

If $sD$ evaluates to $1$, then $s^{-1}(sD)s$ also evaluates to $1$; if
$sD$ evaluates to $gne1$, then its conjugate $s^{-1}gs$ also has value
$ne1$. Conjugation preserves identity-versus-nonidentity. Hence:


item ordinary + ordinary $to$ ordinary;
item ordinary + exceptional (in either order) $to$ exceptional.


We are assuming the map has exactly one exceptional face, so
never both-exceptional. In every case, the merge produces a smaller
map with at most one exceptional face, and thus a smaller exceptional
map. Minimality fails.

Therefore the two face types across an edge labelled $gamma$ are
exactly the two endpoints of~$gamma$.

Reduction 4: at most one loop, bounding the exceptional monogon.: 
Suppose there is a loop. Its two sides are faces (possibly with other
stuff in between, but the loop has just its two immediate face-sides).
Consider the side not containing the exceptional face. Retain
the loop and everything on that side; erase everything on the side
that contains the exceptional face. Retained faces are all ordinary
(they were ordinary before). The erased side becomes a single monogon
whose walk is the loop alone, and its value is the loop's value,
nonidentity by Reduction 1. So this monogon is the unique exceptional
face of the new, smaller map.

Minimality fails, unless the erased side consisted only of that
isolated monogon originally. Hence every loop bounds the exceptional
monogon in the original map. Since there is only one exceptional face
(it bounds only one walk), there is at most one loop, and if it
exists it bounds exactly the exceptional monogon.

Reduced configuration.: 
Combining the four reductions, a minimal exceptional map satisfies:


item every edge is nonneutral;
item every edge is a nonbridge;
item the two faces across an edge labelled $gamma$ have the two
      distinct endpoint types of $gamma$;
item at most one loop exists, and it bounds the exceptional monogon.


We continue in the next reduction. The one remaining configuration to
rule out is that a face has two consecutive nonloop darts with the
same label. Doing so will give the final contradiction with Euler's
formula.

Reduction 5: no two consecutive nonloop darts with the same label.: 
Suppose a face $Phi$ has consecutive nonloop darts $e:ato b$ and
$f:bto d$ with a common label $gammain E(Delta)$ and values
$ε,varphiin C_gamma∖{1}$. The edges $e$ and $f$
are distinct: otherwise the same edge would occur on both sides of
$Phi$, making it a bridge, contradicted by Reduction 2.

Let $X$ be the face on the opposite side of $e$, $Y$ the face on the
opposite side of $f$. By Reduction 3, both have type $jin V(Delta)$,
where $j$ is the other endpoint of $gamma$ from $Phi$'s type~$i$.
The faces $X$ and $Y$ might coincide.

Remove $e,f$. Insert a new edge $g:ato d$ along their arcs, smoothed
through the empty corner of $Phi$ at~$b$. Give $g$ value
$εvarphi$ and label $gamma$ (or make it neutral if this
equals $1$; Reduction 1 then applies if needed). The walk of $Phi$
replaces $ef$ by $g$: same face type $i$, same evaluation. Only $X$
and $Y$ change; every other face keeps its type and value.

Case $Xne Y$. Write $X=barbar ee D$, $Y=barbar ff E$, with $D:ato b$
and $E:bto d$. The merged face has walk $barbar gDE$.gDE$. Its evaluation is

 (εvarphi)^{-1}DE
 =varphi^{-1}(ε^{-1}D),varphi,(varphi^{-1}E).

Let $p=ε^{-1}D$ (old $X$'s value) and $q=varphi^{-1}E$ (old
$Y$'s value). The merged value is $varphi^{-1}pvarphicdot q$:


item $p=q=1$: merged value $varphi^{-1}cdot 1cdotvarphicdot 1=1$;
item $pne1$, $q=1$: merged value $varphi^{-1}pvarphine1$ (conjugate
      of nonidentity);
item $p=1$, $qne1$: merged value $qne1$;
item $pne1$, $qne1$: excluded (at most one exceptional face).


So the merged face is ordinary when both old faces were ordinary, and
exceptional when exactly one was. A smaller exceptional map results,
contradicting minimality.

Case $X=Y$. Now $X$ is a single face whose boundary walk
encounters $e$ and $f$ on their opposite sides. Reading from the dart
$barbar e$:e$: the walk is $barbar eDeDbarbar fE$,fE$, with $D:ato d$ and
$E:bto b$.

After smoothing, the single walk becomes two walks
$barbar gD$gD$ and $E$. The rules are easiest to check by slots: at $a$
and $d$ the new darts replace the old slots of $e,barbar f$;f$; at $b$ the
consecutive slots $barbar e,f$e,f$ are deleted. Counting $v$, $e$, $F$:
$v$ unchanged, $e$ decreased by one, $F$ increased by one. Euler's
formula gives $2c_{new}=v-(e-1)+(F+1)=2+2=4$, so the new
drawing has exactly two components.

Every old face except $X$ survives in one component; $X$ was the only
face shared between the two. One component contains $a,d$ (with $g$),
the other contains $b$ (isolated if $E$ is empty, otherwise with the
walk $E$). Both new faces have type $j$.

Let $A=(εvarphi)^{-1}D$ be the value of walk $barbar gD$,gD$, and
$B=E$ the value of walk $E$. The old walk of $X$ evaluated to
$ε^{-1}Dvarphi^{-1}E$, whose cyclic shift starting at $barbar f$f$
is $(varphi^{-1}Bvarphi)A$:


item $X$ exceptional: the old value was $ne1$, so at least one of
      $A,B$ is $ne1$. Keep the component whose walk is that one.
item $X$ ordinary with $A=B=1$: both new walks are ordinary, so
      the exceptional face is elsewhere. Keep the component
      containing it.
item $X$ ordinary with $Ane1$ and $Bne1$: both new walks are
      exceptional. The exceptional case sits either in the
      $barbar gD$-componentgD$-component (if that also contains the original
      exception), or in the $E$-component. Keep the component
      without the face $Phi$, whose unique exception is its
      sole nonidentity boundary.


In every case, a smaller exceptional map results, contradicting
minimality. So the reduced configuration forbids consecutive nonloop
darts with a common label, on any face.

## Euler deficit and the final contradiction


Recall the reduced configuration: no neutral edges, no bridges,
distinct endpoint types across every edge, at most one loop (bounding
the exceptional monogon), and no face has two consecutive nonloop
darts with the same label.

Vertices away from the loop.: 
Let $u$ be a vertex that is not the base of any loop. Read the face
types around $u$ cyclically; call the resulting sequence
$i_1,i_2,...,i_r$, where $i_a$ is the type of the $a$-th face,
and $r=deg u$. Successive $i_a$ differ: the edge between them has
endpoints $i_{a}$ and $i_{a+1}$, by Reduction 3. No immediate
reversal by Reduction 5 (which says the labels, hence the ordered
endpoints, are distinct).

So we get a closed walk $i_1,i_2,...,i_r,i_1$ in $Delta$ with
successive edges distinct and length $rge1$. Since $Delta$ is
simple and triangle-free, no such closed walk has $r<4$: length $1$
or $2$ would be a loop or a doubling of an edge in a simple graph;
length $3$ would be a triangle. Thus $deg uge4$.

Faces away from the loop.: 
Let $F$ be an ordinary face not incident to the loop. Its boundary is
nonempty: any connected graph with at least one edge has nonempty
dart cycles. Successive labels differ by Reduction 5, so the closed
walk in $Delta$ has length at least $4$. Thus $|∂ F|ge4$.

Euler deficit.: 
For a connected spherical drawing,

 sum_{u}(4-deg u)+sum_{F}(4-|∂ F|)=8,

which follows from Euler's formula and $sum_udeg u=sum_F|∂
F|=2e$ (every edge contributes two to each side).

No loop present. Every vertex satisfies $deg uge4$, so
contributes $le0$. Every ordinary face has $|∂ F|ge4$, so
contributes $le0$. Only the exceptional face can contribute
positively: its walk is nonempty, so $|∂ F|ge1$ and the
contribution is at most $3$. Total $le3<8$, contradicting
(eq:gluing-deficit).

Loop present. The base vertex $u_0$ of the loop has $deg u_0
ge2$ (the loop contributes two), so contributes at most $2$. The
exceptional monogon has walk of length $1$, so contributes $3$. The
ordinary face on the other side of the loop sees the loop's dart with
value $ne1$ (by Reduction 1), so its walk is nonempty and cannot be
a monogon (a monogon would have just the loop's dart, giving value
$ne1$, contradicting ordinari-ness); hence its length is at least
$2$, contributing at most $2$. All other vertices and faces
contribute at most zero. Total $le 2+3+2=7<8$, contradicting
(eq:gluing-deficit).

Hence no minimal exceptional spherical map exists. So $Lto D_i^0$
is injective, i.e., $D_i^0to Q$ is injective, for every vertex~$i$.

## Extending to the full vertex group


We now extend $D_i^0to Q$ to $D_ito Q$. The argument is a
permutation-action construction.

Fix $i$. Let $Ω=Ltimesℕ$, with $L$ acting by left
multiplication on the first coordinate. The action of $D_i^0$ on
$Ω$, transported through $D_i^0↪ L$, is free on
countably infinitely many orbits. The same is true of the left
$D_i^0$-action on $D_itimesℕ$.

Pair the $D_i^0$-orbits bijectively between the two sets and choose
one point in each pair. Extending $D_i^0$-equivariantly gives a
$D_i^0$-equivariant bijection $phi_i:D_itimesℕtoΩ$.
Transport the $D_i$ left-multiplication along $phi_i$: this gives a
$D_i$-action on $Ω$ whose restriction to $D_i^0$ is exactly the
original $L$-action.

Do this independently for each $i$. On a shared edge $gamma={i,j}$,
both copies of the generator $x_gammain L$ act on $Ω$ by the
same element, so the resulting actions glue to a $Q$-action on
$Ω$. The action restricted to each $D_i$ is faithful, since
the original left action on $D_itimesℕ$ is faithful and
$phi_i$ is a bijection.

Therefore $D_ito Q$ is injective for every vertex $i$. This
completes the proof of Lemma~lem:triangle-free-gluing.

## Applying the criterion to $H_i$


We now apply the lemma to our concrete setting. Recall $H=A_0rtimes
P$ with $A_0=(mathbb Z/MbbZ/Mmathbb Z)^P$,bbZ)^P$, $P=F_p^3$, $U=u(P)$,
$V=cUc^{-1}$, and $Ucap V={1}$ from Proposition~prop:UV-triv.
For each edge $i<j$ of $Gamma$ we identify the cyclic subgroup
generated by $v(1,barbar j,j,barbar j^2)$j^2)$ in $H_i$ with the one generated
by $u(1,barbar i,i,barbar i^2)$i^2)$ in $H_j$. Here the bars denote residues in
$F_p$, and both elements have exact order $p$.


Every natural homomorphism $H_ito G_0$ is injective. Consequently
the induced maps $K[H_i]to K[G_0]$ on group algebras are injective.


Proof. 
Apply Lemma~lem:triangle-free-gluing with $Delta=Gamma$ and
$D_i=H$. The vertex groups $H_i$ are finite, the cyclic edge groups
have order $p$, and the edge embeddings are given by the displayed
vectors. We must verify the short-word condition.

Fix a vertex $i$. The incident edges split into two kinds:


item $j<i$: the syllable from edge ${i,j}$ in $H_i$ lies in~$U$ and
      is $u(lambdacdot(1,barbar i,i,barbar i^2))$i^2))$ for some scalar
      $lambdainF_p^*$; the vector $(1,barbar i,i,barbar i^2)$i^2)$ is attached
      via the $H_j$ side.
item $j>i$: the syllable from edge ${i,j}$ in $H_i$ lies in~$V$ and
      is $v(lambdacdot(1,barbar j,j,barbar j^2))$j^2))$ for some
      $lambdainF_p^*$.


Within each of $U$ or $V$, distinct neighbors $j$ correspond to the
vectors $(1,barbar j,j,barbar j^2)j^2)inF_p^3$. Three of these vectors with
three distinct residues $barbar j_1,j_1,barbar j_2,j_2,barbar j_3$j_3$ are linearly
independent over $F_p$: the determinant
[
det
 1 & barbar j_1j_1 & barbar j_1^2j_1^2
 1 & barbar j_2j_2 & barbar j_2^2j_2^2
 1 & barbar j_3j_3 & barbar j_3^2j_3^2

= (barbar j_2-j_2-barbar j_1)(j_1)(barbar j_3-j_3-barbar j_1)(j_1)(barbar j_3-j_3-barbar j_2)j_2)
ne 0,
]
because $p>m>3$, so the three residues are distinct in $F_p$. The
same argument handles two vectors (a $2times 2$ minor of the above)
and one vector (nonzero).

So a word of at most $3$ syllables, all in $U$ or all in $V$, with
distinct labels, evaluates nontrivially in $F_p^3$ and hence in $H_i$.

For a mixed word of length $2$ or $3$: exactly one of $U$ or $V$
supplies a single syllable, and the other supplies one or two. After
a cyclic permutation, a putative relation would equate a nonidentity
element of $U$ to a product of elements of~$V$. But $Ucap V={1}$
and the $U$-element is nonidentity, contradiction. For lengths $2$
and $3$, cyclically distinct labels are just distinct labels, so
the check is exhaustive.

All hypotheses of Lemma~lem:triangle-free-gluing hold, giving
the injection $H_ito G_0$. The induced map $K[H_i]to K[G_0]$ is
injective because distinct elements of an embedded subgroup remain
distinct basis elements of the group algebra.


Consequently $G_0$ is a single group, finitely generated (by the
finite sets of generators of the finitely many $H_i$), containing
each $H_i$ as a subgroup, and the $e_iin K[G_0]$ satisfy
Corollary~op:edge-zero.