betaFeedback

WorksMathematics

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

Abstract

We disprove Kaplansky's direct-finiteness conjecture by constructing a finite field K of characteristic two, a finitely presented group G, and finite sums a,b∈K[G]a,b\in K[G] with ab=1ab=1 but ba≠1ba\ne1. The group G is nonsofic. The same elements define a cellular automaton on KG that is injective but not surjective, disproving Gottschalk's surjunctivity conjecture.

Introduction

If a linear map on a finite-dimensional vector space has a left inverse, that inverse is also a right inverse. A group algebra need not have finite dimension, but each of its elements still has finite support. Kaplansky’s direct-finiteness conjecture asks whether this finite support is enough: for every field KK, group GG, and a,b∈K[G]a,b \in K[G], must ab=1ab=1 imply ba=1ba=1? Here K[G]K[G] consists of finite formal sums ∑gcgg\sum_g c_g g, multiplied using the group law.

A unital ring with this property is directly finite; it is stably finite if all its finite square matrix rings are directly finite. This distinction matters to a counterexample. Producing matrices AB=I≠BAAB=I \ne BA over a group algebra does not by itself produce scalar elements with the same property. Our construction first produces the matrix pair, then embeds its matrix algebra in a larger group algebra to obtain the following scalar conclusion.

Theorem 1.1. There exist a finite field KK of characteristic two, a finitely presented group GG containing an element of odd prime order, and elements aout,bout∈K[G]a_{\mathrm{out}},b_{\mathrm{out}} \in K[G] such that

aoutbout=1,boutaout≠1.a_{\mathrm{out}}b_{\mathrm{out}}=1,\qquad b_{\mathrm{out}}a_{\mathrm{out}} \ne1.

The field, group, and finite sums are specified by a terminating prescription involving finite sets and finite-field arithmetic.

Thus Theorem 1.1 resolves the unrestricted conjecture negatively in characteristic two. The construction uses odd-order torsion and does not assert that K=F2K=\mathbb{F}_2. The prescription need not be computationally practical and has not been executed: its termination is proved, and the two product assertions have algebraic certificates independent of any decision procedure for the group word problem.

History and positive results. For a finite group GG, the algebra K[G]K[G] and all its finite square matrix rings are finite dimensional, so elementary linear algebra gives stable finiteness. The classical characteristic-zero theorem uses a different substitute for dimension. Kaplansky’s operator-algebra argument places C[G]\mathbb{C}[G] in a finite tracial setting; Montgomery gave a proof using the operator-norm closure of the regular representation and its identity-coefficient trace, including the extension to every finite matrix size [15]. The trace rules out a proper one-sided inverse. For an arbitrary characteristic-zero field, all coefficients of a proposed finite matrix pair lie in a finitely generated subfield, which embeds in C\mathbb{C}. Thus the complex result gives stable finiteness over every characteristic-zero field.

In positive characteristic, rank and approximation methods have supplied broad classes of positive results without a complex representation. Ara, O’Meara, and Perera proved stable finiteness over arbitrary division rings for free-by-amenable groups, using Sylvester rank functions and amenable translation rings [1]. Elek and Szabó obtained stable finiteness over arbitrary division rings for all sofic groups from finite approximate models and a rank construction [8]. These are restrictions on a possible counterexample’s group, not assumptions that the group constructed here satisfies.

Dykema and Juschenko clarified how a matrix obstruction can nevertheless yield a scalar one: for a fixed field and group, stable finiteness is equivalent to direct finiteness after taking the direct product with every finite group [6]. Their reduction embeds a matrix algebra in a finite-group algebra and adds the complementary identity. We realize this transfer explicitly for the field used here, giving both the matrix units and the resulting two elements.

Finite presentation and soficity. For a finite nonempty set Ω\Omega, write dΩ(f,h)d_{\Omega}(f,h) for the fraction of points on which two maps f,h:Ω→Ωf,h:\Omega\to\Omega differ. In the finite-map formulation of Elek and Szabó [8], a group Γ\Gamma is sofic if, for every finite E⊆ΓE\subseteq\Gamma and every ε∈(0,1)\varepsilon\in(0,1), there are a finite nonempty Ω\Omega and a map σ:Γ→ΩΩ\sigma:\Gamma\to\Omega^{\Omega} such that

dΩ(σ(gh),σ(g)σ(h))≤ε(g,h∈E),dΩ(σ(1),id⁡)≤ε,dΩ(σ(g),id⁡)>1−ε(g∈E∖{1}).\begin{aligned} d_{\Omega}\left(\sigma(gh),\sigma(g)\sigma(h)\right)&\leq\varepsilon&&(g,h\in E),\\ d_{\Omega}\left(\sigma(1),\operatorname{id}\right)&\leq\varepsilon,\\ d_{\Omega}\left(\sigma(g),\operatorname{id}\right)&>1-\varepsilon&&(g\in E\setminus\{1\}). \end{aligned}

where products of maps denote composition. Thus soficity asks for finite approximate models of multiplication in which nonidentity elements act almost without fixed points.

The stable-finiteness theorem of Elek and Szabó [8] applies to the field KK in Theorem 1.1. If its particular group GG were sofic, then K[G]K[G] would be stably finite and hence directly finite by the matrix-size-one case, contradicting the two displayed product assertions. Therefore this same GG is nonsofic. In particular, the construction supplies a finitely presented counterexample to the assertion that every group is sofic. The finite presentation is established directly in Section 4.6; the nonsoficity conclusion uses only the scalar defect and the cited theorem.

Cellular automata. For a nonempty finite alphabet AA, a configuration is an arbitrary function x:G→Ax:G\to A. A cellular automaton on AGA^G is a map given by a finite set M⊂GM\subset G and a local rule ϕ:AM→A\phi:A^M\to A through

τ(x)(g)=ϕ((x(gu))u∈M).\tau(x)(g)=\phi\left((x(gu))_{u\in M}\right).

The group GG is surjunctive if every injective cellular automaton on AGA^G is surjective, for every such AA. Gottschalk’s conjecture asserts that every group is surjunctive [11]. The problem asks whether finite local dependence and translation symmetry preserve the finite-set implication from injectivity to surjectivity on the infinite configuration space.

Gromov developed a general symbolic-algebraic surjunctivity theorem [12], Section 7.G′; Weiss gave the finite-alphabet sofic-group theorem directly [20]. Elek and Szabó explicitly recorded the implication from surjunctivity to direct finiteness over finite fields [8], Section 1]. Ceccherini-Silberstein and Coornaert developed the linear theory: their equivalence, quantified over all coefficient fields, relates stable finiteness to injective-to-surjective behavior of linear cellular automata with finite-dimensional vector alphabets [2], Theorem 4.2]. Phung proved stable finiteness over every field for surjunctive groups, using algebraic cellular automata [19], Theorem B]. Ceccherini-Silberstein, Coornaert, and Phung later gave a model-theoretic proof and a monoid extension [3, 4], Theorem 1.1]. These results connect algebraic finiteness to a dynamical property rather than imposing finite dimensionality.

For the finite field in Theorem 1.1, the short algebra-to-automaton passage can be given directly. The coefficients of boutb_{\mathrm{out}} define a local rule, the coefficients of aouta_{\mathrm{out}} give a left inverse on all configurations, and a nonzero coefficient of boutaout−1b_{\mathrm{out}}a_{\mathrm{out}}-1 identifies a missing point-indicator configuration. Section 7 proves this standard transfer in full, including the multiplication convention. It gives a negative resolution of Gottschalk’s conjecture for the group in Theorem 1.1; it requires no further existence theorem or approximation assumption.

The characteristic-two scalar pair in Theorem 1.1 is also the input to the companion counterexample to the group-ring Determinant Conjecture [17], Theorem 1.1]. By a separate construction, that paper produces an integral square matrix over another finitely generated group, invertible over its rational group ring, whose Fuglede–Kadison determinant lies strictly between zero and one.

The construction. The obstacle is to force a one-sided inverse while retaining a certificate that the reverse product is not the identity. The proof separates these requirements through finite incidence data. Let F\mathcal{F} be a family of subsets of a finite set VV. We require that each point lie in ℓ+1\ell+1 members, where ℓ\ell is an odd prime, and that the bipartite incidence graph have girth at least 12. We also require column vectors xv∈Kmx_v \in K^m satisfying

∑v∈fxvxvT=0(f∈F),∑v∈VxvxvT=−Im,m<∣V∣≤mℓ2.\sum_{v\in f} x_vx_v^{\mathsf{T}}=0 \quad(f\in\mathcal{F}), \qquad\sum_{v\in V}x_vx_v^{\mathsf{T}}=-I_m, \qquad m<|V|\le m\ell^2.

Theorem 3.1 turns these finite data into a counterexample.

Two parts of this criterion explain the separation. First, a planar balance argument proves that copies of the additive group Fℓ2\mathbb{F}_{\ell}^{2}, glued along their one-dimensional subgroups according to the incidence structure, embed in the resulting group. Incidence girth forces a contradiction with Euler’s formula for any diagram witnessing a collapsed local element. Second, character idempotents and prescribed subgroup conjugations pack a rectangular factorization into square matrices. Their forward product is the identity by the displayed pairings.

To detect the reverse-product defect, we sandwich it by the packing maps and obtain a matrix in an embedded subgroup algebra. A homomorphism from that algebra to KK sends this matrix to XTX−I∣V∣X^{\mathsf{T}}X-I_{\lvert V\rvert}, where XX has columns xvx_v. Since XX has only m<∣V∣m<|V| rows, XTXX^{\mathsf{T}}X cannot be the identity, so the original defect is nonzero. The homomorphism is used only on the subgroup algebra; it is not asserted to extend to the larger group algebra. A finite auxiliary group then converts the matrix obstruction into the scalar outputs of Theorem 1.1.

To produce the incidence data, we take full affine lines over a finite field Q⊂KQ\subset K and remove a small set of points. Low-degree interpolation on these holes gives the vectors xvx_v: the pairings sum to zero on each full line, but removing the holes leaves the nonzero total −Im-I_m. The geometric task is to retain a regular line system of large incidence girth. We combine random small-dimensional slabs with an exact trade in each bundle of directions through a hole. Hole selection and a weighted local-lemma estimate rule out triangles, rectangles, and pentagons of lines; the local trades preserve regularity. A uniform bound from Linnik’s theorem supplies compatible parameters [21], Theorem 1.1.

Low-degree polynomial products and affine-line restrictions also occur in the coding-theoretic constructions of Golowich–Lin and Dinur–Liu–Zhang [10, 5]: degree bounds add under products, while restriction to a line does not increase degree. Here these features produce the line and total pairing identities. We use no coding-theoretic theorem from those works. The only non-elementary existence theorem imported into the direct construction is the uniform least-prime bound; the group embeddings, finite matrix block, interpolation, and probability argument needed here are proved below.

Section 2 first explains the polynomial pairing and the two size bounds. Section 3 formulates the algebraic criterion and proves that its local groups embed. Section 4 completes the passage from subgroup averages to scalar elements, including a certificate for the reverse defect. Section 5 then supplies the required affine-line system by the full probability and local-trade argument. Section 6 fixes all choices and completes the proof of Theorem 1.1. Section 7 gives the cellular automaton and determines its image by finite local equations.

Conventions. All incidence structures in the proof are finite. Their incidence graphs have one vertex for each point and one for each member of the family, with an edge for each membership. The girth is the length of a shortest cycle, and is infinite for a forest. An affine Q\mathbb{Q}-line is a translate of a one-dimensional Q\mathbb{Q}-subspace. A direction is such a linear subspace, not a chosen nonzero vector. Superscript TT denotes transpose, without any involution on the coefficient field. All group presentations define abstract discrete groups.

Polynomial pairings on a punctured affine space

The pairing comes from low-degree polynomials that distinguish the points to be deleted. Their pairwise products sum to zero on every full affine line and on the whole affine space. At the deleted points, however, the evaluation vectors are coordinate vectors, so their contribution is the identity matrix. Removing these points leaves its negative as the total pairing on the remaining space.

The interpolation argument does not depend on how the retained full lines are arranged. Regularity and girth enter as separate geometric hypotheses in the proposition below. Section 5 will supply them, after Sections 3 and 4 explain their algebraic use.

We use the usual lower-set Newton interpolation argument; compare Dyn and Floater [7]. The triangular evaluation proof below works directly over the finite field needed here. The later products of interpolants and their restrictions to full affine lines are the features related to the coding constructions of Golowich–Lin [10], Sections 2.1.2–2.1.3 and Dinur–Liu–Zhang [5], Sections 3.4–3.5. We need no coding theorem from either work: the degree bound and all line identities used in this paper are proved below.

Lemma 2.1 (Interpolation on an index simplex). Let QQ be a field of order qq, enumerate its elements as a0,…,aq−1a_0,\ldots,a_{q-1}, and let 0≤d<q0 \le d < q. For n≥1n \ge1, set

Sd={(ak1,…,akn):ki≥0, ∑iki≤d}⊂Qn.S_d = \{(a_{k_1},\ldots,a_{k_n}) : k_i \ge0,\ \sum_i k_i \le d\} \subset Q^n.

Evaluation on SdS_d is an isomorphism from the QQ-vector space of polynomials of total degree at most dd to QSdQ^{S_d}. Proof. For each tuple k=(k1,…,kn)k=(k_1,\ldots,k_n) of total sum at most dd, consider

Nk(X1,…,Xn)=∏i=1n∏0≤u<ki(Xi−au).N_k(X_1,\ldots,X_n)=\prod_{i=1}^{n}\prod_{0\le u<k_i}(X_i-a_u).

Its evaluation at the point with index tuple jj vanishes if ji<kij_i<k_i for any ii. Thus, with tuples in lexicographic order, the square evaluation matrix is triangular. Its diagonal entry indexed by kk is

∏i=1n∏0≤u<ki(aki−au)≠0.\prod_{i=1}^{n}\prod_{0\le u<k_i}(a_{k_i}-a_u)\ne0.

Since d<qd<q, there is no additional coordinate restriction on these tuples. Their number is (d+nn)\binom{d+n}{n}, the dimension of the polynomial space. The displayed polynomials therefore give an invertible evaluation map.

Lemma 2.2 (Line sums). Let n≥1n\ge1. If PP is a polynomial on QnQ^n of total degree at most q−2q-2, then its sum on every full affine QQ-line is zero. Its sum on QnQ^n is also zero.

Proof. On a line, write its restriction as a polynomial in a parameter z∈Qz\in Q of degree at most q−2q-2. The sum of the constant monomial is q=0q=0 in QQ. If 1≤k<q−11\le k<q-1, choose c∈Q×c\in Q^\times with ck≠1c^k\ne1, using cyclicity of Q×Q^\times. Multiplication by cc permutes QQ, so

∑z∈Qzk=ck∑z∈Qzk\sum_{z\in Q}z^k=c^k\sum_{z\in Q}z^k

forces the sum to vanish. More explicitly, (1−ck)∑zzk=0(1-c^k)\sum_z z^k=0 and 1−ck≠01-c^k\ne0. This proves the line assertion. Partition QnQ^n into parallel lines to obtain the last assertion.

Proposition 2.3 (The pairing supplied by holes). Let q≥4q\ge4 be a power of two, let QQ be a field of order qq, fix an enumeration of QQ, and let n≥1n\ge1. Put d0=(q−2)/2d_0=(q-2)/2, S=Sd0⊂A=QnS=S_{d_0}\subset A=Q^n, and Npt=qnN_{\mathrm{pt}}=q^n. Let ℓ\ell be an odd prime and D=ℓ+1D=\ell+1. Suppose that O⊂SO\subset S and that F\mathcal{F} is a family of full affine QQ-lines contained in V=A∖OV=A\setminus O, with

2NptD2≤∣O∣≤7NptD2.(1)\frac{2N_{\mathrm{pt}}}{D^2}\le|O|\le\frac{7N_{\mathrm{pt}}}{D^2}. \tag*{(1)}

Suppose also that every point of VV lies on DD members of F\mathcal{F} and that the incidence graph has girth at least 12. If KK is a finite extension of QQ containing a primitive ℓ\ellth root of unity, then, with m=∣O∣m=|O| and t=∣V∣t=|V|, there are columns xv∈Kmx_v\in K^m, v∈Vv\in V, such that

0<m<t≤mℓ2,∑v∈VxvxvT=−Im,∑v∈fxvxvT=0(f∈F).0<m<t\le m\ell^2,\qquad\sum_{v\in V}x_vx_v^{\mathsf{T}}=-I_m,\qquad\sum_{v\in f}x_vx_v^{\mathsf{T}}=0\quad(f\in\mathcal{F}).

Proof. Interpolation is on the whole set SS, although only the subset OO is deleted. For each o∈Oo\in O, Lemma 2.1 gives a unique polynomial fof_o of total degree at most d0d_0 whose values on SS are the indicator function of oo. Order OO and define, for all v∈Av\in A,

xv=(fo(v))o∈O∈Qm⊂Km,Wv=xvxvT.x_v=(f_o(v))_{o\in O}\in Q^m\subset K^m,\qquad W_v=x_vx_v^{\mathsf{T}}.

Each entry of WvW_v is the value at vv of a polynomial of total degree at most 2d0=q−22d_0=q-2. Lemma 2.2 therefore gives

∑v∈fWv=0(f∈F),∑v∈AWv=0.\sum_{v\in f}W_v=0\quad(f\in\mathcal{F}),\qquad\sum_{v\in A}W_v=0.

For o∈Oo \in O, xox_o is its coordinate unit vector. Hence ∑o∈OWo=Im\sum_{o\in O} W_o = I_m, and subtraction yields

∑v∈VWv=−Im,∑v∈fWv=0(f∈F).(2)\sum_{v\in V} W_v = -I_m,\qquad\sum_{v\in f} W_v = 0\quad(f\in\mathcal{F}). \tag*{(2)}

It remains to check the sizes. Since D≥4D \ge4, the upper bound in (1) is strictly less than Npt/2N_{\mathrm{pt}}/2. The lower bound is positive. Thus 0<m<t0 < m < t, and

tm=Nptm−1≤D22−1≤(D−1)2=ℓ2,\frac{t}{m} = \frac{N_{\mathrm{pt}}}{m} - 1 \le\frac{D^2}{2} - 1 \le(D-1)^2 = \ell^2,

where the last inequality is equivalent to (D−2)2/2≥0(D-2)^2/2 \ge0. These are all the claimed identities and inequalities.

Remark 2.4. The simultaneous identities in (2) are compatible with regularity because D=ℓ+1D=\ell+1 is zero as a scalar in characteristic two. Summing the line identities multiplies the total point sum by DD, rather than recovering that total point sum.

An incidence criterion and its embedded local groups

We now leave affine geometry. The following criterion is the algebraic part of the construction. Its input consists of a finite incidence system and vectors satisfying two matrix identities. All groups and group-algebra elements in its conclusion are constructed in this section and Section 4; no further geometric assumption enters those arguments.

Theorem 3.1 (Incidence criterion). Let ℓ\ell be an odd prime, let KK be a finite field of characteristic two containing a primitive ℓ\ellth root of unity ζ\zeta, and put κ=ℓ2\kappa=\ell^2. Let VV be a finite set of cardinality tt, and let F\mathcal{F} be a finite family of nonempty subsets of VV. Assume that every v∈Vv\in V belongs to exactly ℓ+1\ell+1 members of F\mathcal{F} and that the bipartite incidence graph of VV and F\mathcal{F} has girth at least 12. Suppose that an integer mm and column vectors xv∈Kmx_v\in K^m, v∈Vv\in V, satisfy

0<m<t≤mκ0 < m < t \le m\kappa

and

∑v∈VxvxvT=−Im,∑v∈fxvxvT=0for every f∈F.(3)\sum_{v\in V} x_vx_v^{\mathsf{T}}=-I_m,\qquad\sum_{v\in f}x_vx_v^{\mathsf{T}}=0\quad\text{for every }f\in\mathcal{F}. \tag*{(3)}

Then there are a finitely presented group GG containing an element of order ℓ\ell and finite sums aout,bout∈K[G]a_{\mathrm{out}},b_{\mathrm{out}}\in K[G] such that

aoutbout=1,boutaout≠1.a_{\mathrm{out}}b_{\mathrm{out}}=1,\qquad b_{\mathrm{out}}a_{\mathrm{out}}\ne1.

They are given by the constructions and formulas below.

The hypotheses have separate roles. Incidence girth preserves the local subgroups, while Equation (3) produces a rectangular matrix identity. The upper bound t≤mκt\le m\kappa permits character packing into square matrices; the strict inequality m<tm<t then detects their reverse-product defect in an embedded subgroup algebra. An explicit finite group supplies matrix units that turn these matrices into the promised elements.

The glued group

We first realize the incidence data by finite subgroups of one group. For each v∈Vv \in V, let Kv0K_v^0 be a coordinatized copy of the additive group of Fℓ2\mathbb{F}_{\ell}^2, and for each f∈Ff \in\mathcal{F}, let Lf0L_f^0 be a copy of the additive group of Fℓ\mathbb{F}_{\ell}. Since exactly ℓ+1\ell+1 hyperedges contain vv, choose injections

ιvf:Lf0⟶Kv0(v∈f)\iota_{vf}:L_f^0 \longrightarrow K_v^0 \qquad(v \in f)

whose images are the ℓ+1\ell+1 distinct one-dimensional subspaces of Kv0K_v^0. These are homomorphisms of additive groups. In particular, their images partition Kv0∖{0}K_v^0 \setminus\{0\} outside their common zero element.

Introduce a generator sf,cs_{f,c} for each f∈Ff \in\mathcal{F} and each 0≠c∈Lf00 \ne c \in L_f^0. A signed word

sf1,c1ε1⋯sfk,ckεk,εi∈{1,−1},s_{f_1,c_1}^{\varepsilon_1}\cdots s_{f_k,c_k}^{\varepsilon_k}, \qquad\varepsilon_i \in\{1,-1\},

is a defining relator whenever some v∈Vv \in V belongs to every fif_i and

∑i=1kεiιvfi(ci)=0in Kv0.\sum_{i=1}^{k}\varepsilon_i\iota_{vf_i}(c_i)=0 \quad\text{in } K_v^0.

Let NN be the group with these generators and relators. It is finitely generated, since the incidence data and all the local groups are finite.

There is a homomorphism θv:Kv0→N\theta_v:K_v^0 \to N determined by

θv(0)=1,θv(ιvf(c))=sf,c(c≠0).\theta_v(0)=1,\qquad\theta_v(\iota_{vf}(c))=s_{f,c}\quad(c\ne0).

Indeed, each nonzero element has a unique expression on the left. For a,b∈Kv0a,b \in K_v^0, the word expressing θv(a)θv(b)θv(a+b)−1\theta_v(a)\theta_v(b)\theta_v(a+b)^{-1} is a defining relator, after omitting factors corresponding to zero elements.

The same group is presented by the finite sublist of defining relators of length at most three. These include every local multiplication-table relation just displayed, as well as the local inverse relations. Within one Kv0K_v^0, successive applications of those relations reduce any signed word to the generator for its sum, or to the empty word when the sum is zero. Thus they imply every defining relator of NN, and NN is finitely presented. We retain the all-word formulation because it makes the planar proof below more transparent.

Lemma 3.2. If the incidence graph of (V,F)(V,\mathcal{F}) has girth at least 12, then every homomorphism θv:Kv0→N\theta_v:K_v^0 \to N is injective.

Proof. Every nonzero element of Kv0K_v^0 maps to a single generator sf,cs_{f,c}. It therefore suffices to prove that no such generator is the identity in NN. Suppose, to the contrary, that sf,c=1s_{f,c}=1, with c≠0c\ne0. We will encode this equality by a planar graph with zero local sums at every vertex except one. Reducing the graph will make the local group relations force lower bounds on vertex degrees, while incidence girth forces lower bounds on facial lengths. These bounds will contradict Euler’s formula even with the one exceptional vertex.

From a word equality to a planar graph. The one-letter word sf,cs_{f,c} can be changed to the empty word by finitely many insertions and deletions of contiguous defining relators. To justify this form of reduction, take the congruence on signed words generated by those operations. Every formal inverse pair is a defining relator, since its hyperedge has an incident vertex. The quotient is consequently a group, and its universal property is exactly that of the presentation of NN. Thus equality in NN is equality under this congruence. Equivalently, each factor ur±1u−1ur^{\pm1}u^{-1} in a finite normal-closure expression can be inserted by first forming uu−1uu^{-1} through nested inverse-pair insertions and then inserting r±1r^{\pm1} between its two halves. Inverses of defining relators are again defining relators. Draw the successive words on horizontal levels, treating each signed letter as an individual token. Between two levels, connect the tokens that persist in their unchanged order. An inserted or deleted block begins or ends its tokens at a new black vertex, labelled by a point vv at which the corresponding relator has zero sum. This can be drawn without crossings: the affected block is contiguous, so its star occupies a single gap between the other order-preserving wires. Joining the finitely many strips gives a planar drawing.

Every inserted token si,yεs^{\varepsilon}_{i,y} has one creation vertex and one deletion vertex. Subdivide its full lifetime wire by a white vertex labelled ii, and give its two edges weights εy\varepsilon_y at the creation end and −εy-\varepsilon_y at the deletion end. The initial token instead has an exceptional white endpoint labelled ff, joined to its deletion vertex by an edge of weight −c-c. We obtain a finite planar bipartite multigraph with black labels in VV and white labels in F\mathcal{F}. An edge joining labels vv and ii has a nonzero weight in Li0L_i^0, and v∈iv \in i. Its balances are

∑a∋xιv,i(a)(ω(a))=0at each black vertex x labelled v,∑a∋yω(a)=0at each ordinary white vertex y.(4)\sum_{a \ni x} \iota_{v,i(a)}\bigl(\omega(a)\bigr)=0 \quad\text{at each black vertex }x\text{ labelled }v, \qquad \sum_{a \ni y}\omega(a)=0 \quad\text{at each ordinary white vertex }y. \tag*{(4)}

where ω(a)\omega(a) is the weight of edge aa and i(a)i(a) is its white label. The exceptional white vertex has nonzero sum. At creation vertices the first balance is the relator sum, and at deletion vertices it is its negative. Ordinary white sums vanish because their two weights are opposite. Retain only the connected component of the exception.

Reducing the planar graph. Among all connected planar bipartite multigraphs with the indicated labels, nonzero edge weights, and balances (4), and with exactly one exceptional white vertex of nonzero sum, choose one minimizing lexicographically the number of vertices and then the number of edges. We do not require this comparison graph to come from a word reduction. Its exceptional vertex has positive degree, so the graph has an edge.

There are no parallel edges. Two parallel edges have weights in the same Li0L_i^0 and the same map ιvi\iota_{vi} at their black endpoint. Replace them by one edge carrying their sum, or delete both if that sum is zero, and again retain the component of the exception. Additivity preserves every balance and preserves the exceptional nonzero sum. This gives a smaller comparison graph, a contradiction.

Fix a spherical embedding of the minimal graph. We claim that, at each vertex of degree at least two, cyclically consecutive neighbors have distinct labels. If two such neighbors have the same label, they are distinct vertices because parallel edges have been removed. Join them by an auxiliary arc following one side of the two incident edges and the empty sector between those edges, and contract the arc. A sufficiently narrow neighborhood of this two-edge path makes the arc disjoint from the rest of the graph. This construction is local and remains valid when either edge is a bridge.

The contraction merges vertices of the same color and label. Each original edge keeps its weight and its opposite-color endpoint; hence the resulting graph is still bipartite, and every edge weight is nonzero. Parallel edges created by the contraction are allowed in the comparison class. When black vertices are merged, their balances add in the same Kv0K_v^0, while white balances are unchanged. When white vertices are merged, their balances add in the same Li0L_i^0, while every black incidence map and weighted sum is unchanged. If the exception is merged, its sum is increased by zero. Thus the contraction gives a comparison graph with fewer vertices, proving the claim.

Degrees, faces, and Euler’s formula. An ordinary white vertex cannot have degree one, since its incident weight would be nonzero. A black vertex cannot have degree one either, since the maps ιvi\iota_{vi} are injective. If a black vertex had degree two, its two white neighbors would have distinct labels by the preceding claim. Its zero balance would then equate two nonzero vectors in distinct one-dimensional subspaces of Kv0K_v^0, which is impossible. Consequently every black degree is at least three, and every white degree is at least two except possibly the exceptional degree, which is at least one.

Contraction of two white vertices into one

Figure 1. The white vertices p,qp,q, both labelled ff, merge to rr along the dashed auxiliary arc in the empty sector between their consecutive edges at the black vertex xx, labelled vv. The edges of weights a,ba,b remain distinct parallel edges.

Consider the facial boundary walks of this connected plane graph, counting edge sides with multiplicity. At a turn through a vertex of degree at least two, the entering and leaving edges are distinct and consecutive in its rotation. Their opposite endpoints have different labels. Thus the image of the boundary walk in the incidence graph has no immediate backtracking at that turn. This also applies to the cyclic closing turn of the walk. Bridges cause no difficulty: their two sides are counted separately, and a facial walk reverses immediately along an edge only at a degree-one vertex. There is at most one such vertex, the exceptional white vertex, and it belongs to just one face.

It follows that all but at most one face have boundary walks whose images are nonempty closed walks without immediate backtracking in the incidence graph. Such a walk contains a cycle, so each of these faces has length at least 12. Write nb,nw,nfn_b,n_w,n_f for the numbers of black vertices, white vertices, and faces, and EE for the number of edges. The degree bounds and the total of 2E2E edge sides give

nb≤E3,nw≤E+12,nf≤E6+1.n_b \le\frac{E}{3}, \qquad n_w \le\frac{E+1}{2}, \qquad n_f \le\frac{E}{6}+1.

Therefore

nb+nw+nf≤E+32<E+2.n_b+n_w+n_f \le E+\frac{3}{2}<E+2.

contrary to Euler’s formula for a connected plane graph. The assumed word equality is impossible, and every θv\theta_v is injective. □

We henceforth identify Kv0K_v^0 with its image Kv≤NK_v \le N, and identify Lf0L_f^0 with the subgroup Lf≤NL_f \le N given by c↦sf,cc \mapsto s_{f,c}, with 00 mapped to the identity. The latter is injective by choosing any point incident to ff and applying Lemma 3.2. The shared generators identify this same subgroup inside every KvK_v with v∈fv \in f. In particular, ∣Kv∣=ℓ2|K_v|=\ell^2, ∣Lf∣=ℓ|L_f|=\ell, and the incident subgroups LfL_f partition KvK_v outside the identity. No assertion about intersections between other local subgroups is needed.

From subgroup averages to the scalar defect

The embedded groups now allow legitimate subgroup averages. We first obtain a rectangular identity, then pack its intermediate coordinates into square matrices, and finally encode those matrices as scalar elements of a group algebra. The strict size inequality will detect the reverse defect after packing.

Subgroup averages and a rectangular identity

We prove Theorem 3.1 using the group NN and subgroups Kv,Lf≤NK_v, L_f \leq N supplied by Lemma 3.2. We retain the coordinates on KvK_v transported from Kv0=Fℓ2K_v^0 = \mathbb{F}_\ell^2. Fix an ordering of VV, and use it for all matrix indices indexed by VV. For v∈Vv \in V put

Pv=κ−1∑u∈Kvu∈K[N].P_v = \kappa^{-1} \sum_{u \in K_v} u \in K[N].

The integer κ\kappa is invertible in KK, since ℓ\ell is odd. For each w∈Kvw \in K_v there are exactly κ\kappa pairs (u,u′)∈Kv2(u,u') \in K_v^2 with uu′=wuu' = w, so Pv2=PvP_v^2 = P_v.

At a fixed vv, the subgroups LfL_f for f∋vf \ni v run through all the one-dimensional subspaces of the additive group KvK_v. Their nonidentity elements partition Kv∖{1}K_v \setminus\{1\}. Consequently

∑u∈Kvu=1+∑f∋v(∑u∈Lfu−1).\sum_{u \in K_v} u = 1 + \sum_{f \ni v} \left(\sum_{u \in L_f} u - 1\right).

This equality is internal to KvK_v; no assertion about intersections between different KvK_v is needed. Write Wv=xvxvTW_v = x_v x_v^{\mathsf T}. Define matrices over K[N]K[N] by

U∈Mat⁡m×t(K[N]),T∈Mat⁡t×m(K[N]),U−,v=−κxvPv,Tv,−=PvxvT,(5)U \in\operatorname{Mat}_{m \times t}(K[N]), \qquad T \in\operatorname{Mat}_{t \times m}(K[N]), \qquad U_{-,v} = -\kappa x_vP_v, \qquad T_{v,-} = P_vx_v^{\mathsf T}, \tag*{(5)}

and set P=diag⁡v∈V(Pv)P = \operatorname{diag}_{v \in V}(P_v). Since the entries of each xvx_v belong to the coefficient field, they commute with all group-algebra elements. Idempotence gives UP=UUP = U and PT=TPT = T. Moreover,

UT=−κ∑v∈VWvPv2=−∑v∈VWv∑u∈Kvu=−∑v∈VWv−∑f∈F(∑v∈fWv)(∑u∈Lfu−1)=Im,\begin{aligned} UT &= -\kappa\sum_{v \in V} W_vP_v^2 = -\sum_{v \in V} W_v \sum_{u \in K_v} u \\ &= -\sum_{v \in V} W_v - \sum_{f \in F} \left(\sum_{v \in f} W_v\right)\left(\sum_{u \in L_f}u - 1\right) = I_m, \end{aligned}

where we used Equations (4.2) and (3). We have proved

UP=U,PT=T,UT=Im.UP = U, \qquad PT = T, \qquad UT = I_m.

A group extension implementing character twists

Equation (4.4) gives the forward identity, but the factors are rectangular. We next arrange enough orthogonal character idempotents to place their tt intermediate coordinates into mm slots. The extension will implement the necessary changes of character by conjugation while preserving the original subgroup algebra.

Let zz generate a cyclic group of order ℓ\ell, and put H=N×⟨z⟩H = N \times\langle z\rangle. Choose v∗∈Vv_* \in V and put K∗=Kv∗K_* = K_{v_*}. For every v∈Vv \in V let ϕv:Kv⟶K∗\phi_v: K_v \longrightarrow K_* be the isomorphism taking each element to the element with identical Fℓ2\mathbb{F}_\ell^2 coordinates. There are exactly κ\kappa linear forms K∗⟶FℓK_* \longrightarrow\mathbb{F}_\ell. By Equation (3.1), we may assign to each v∈Vv \in V a slot s(v)∈{1,…,m}s(v) \in\{1,\ldots,m\} and a linear form αv:K∗⟶Fℓ\alpha_v: K_* \longrightarrow\mathbb{F}_\ell so that the pairs (s(v),αv)(s(v),\alpha_v) are distinct. In particular, the forms assigned within any one slot are distinct.

We use a multiple HNN extension [13], verifying the required base-group embedding directly. Adjoin to HH generators τv\tau_v, v∈Vv \in V, with relations

τv(uzr)τv−1=ϕv(u)zr+αv(ϕv(u))(u∈Kv, r∈Z/ℓ).(6)\tau_v(uz^r)\tau_v^{-1} = \phi_v(u)z^{r+\alpha_v(\phi_v(u))} \qquad(u \in K_v,\ r \in\mathbb{Z}/\ell). \tag*{(6)}

Denote the resulting group by LL. Exponents in Fℓ\mathbb{F}_{\ell} are interpreted in Z/ℓ\mathbb{Z}/\ell. For each vv, the specified map

ψv:Kv×⟨z⟩⟶K∗×⟨z⟩,uzr⟼ϕv(u)zr+αv(ϕv(u))\psi_v: K_v \times\langle z\rangle\longrightarrow K_* \times\langle z\rangle,\qquad uz^r \longmapsto\phi_v(u)z^{r+\alpha_v(\phi_v(u))}

is a group isomorphism. Its inverse takes wzrwz^r to ϕv−1(w)zr−αv(w)\phi_v^{-1}(w)z^{r-\alpha_v(w)}.

We verify directly that HH embeds in LL. Let HH act on itself by left multiplication. Restricted to either the domain or the image of ψv\psi_v, this is a disjoint union of regular actions of a subgroup of order ℓ3\ell^3. These two collections of orbits have the same cardinality. Indeed, if HH is finite, both have ∣H∣/ℓ3|H|/\ell^3 orbits; if HH is infinite, both have countably infinitely many, since HH is countable and the subgroups are finite. Pair these orbits and choose representatives hi,kih_i,k_i so that they are respectively (Kv×⟨z⟩)hi(K_v \times\langle z\rangle)h_i and (K∗×⟨z⟩)ki(K_* \times\langle z\rangle)k_i. The bijection

Fv(ahi)=ψv(a)ki(a∈Kv×⟨z⟩)F_v(ah_i)=\psi_v(a)k_i \qquad(a\in K_v \times\langle z\rangle)

of the set HH conjugates left multiplication by aa to left multiplication by ψv(a)\psi_v(a). Assign FvF_v to τv\tau_v for each vv. These assignments, together with the left regular action of HH, satisfy all the relations defining LL: no defining relation couples two distinct stable letters, so overlapping associated subgroups impose no additional compatibility condition on the independently chosen FvF_v. They therefore give a permutation representation of LL whose restriction to HH is faithful. This proves the required embedding. In particular, K[H]K[H] embeds in K[L]K[L].

Taking u=1u=1 in (6) shows that every τv\tau_v centralizes zz. Since zz is already central in HH, it is central in LL. Define

e=ℓ−1∑r=0ℓ−1ζ−rzr∈K[L].e=\ell^{-1}\sum_{r=0}^{\ell-1}\zeta^{-r}z^r\in K[L].

This is a nonzero central idempotent and satisfies ez=ζeez=\zeta e. For completeness, in the convolution square each coefficient of zaz^a is ℓ−2ℓζ−a\ell^{-2}\ell\zeta^{-a}, which proves e2=ee^2=e; reindexing the sum proves ez=ζeez=\zeta e. The identity coefficient is ℓ−1≠0\ell^{-1}\ne0 because ⟨z⟩\langle z\rangle remains embedded.

For a linear form α:K∗⟶Fℓ\alpha:K_* \longrightarrow\mathbb{F}_{\ell}, put

Qα=κ−1∑u∈K∗ζα(u)u.Q_\alpha=\kappa^{-1}\sum_{u\in K_*}\zeta^{\alpha(u)}u.

Using additive notation for the coordinates of K∗K_*, the coefficient of ww in QαQβQ_\alpha Q_\beta is

κ−2ζβ(w)∑u∈K∗ζα(u)−β(u).\kappa^{-2}\zeta^{\beta(w)}\sum_{u\in K_*}\zeta^{\alpha(u)-\beta(u)}.

If α=β\alpha=\beta, the inner sum is κ\kappa. Otherwise choose u0u_0 with ζα(u0)−β(u0)≠1\zeta^{\alpha(u_0)-\beta(u_0)}\ne1. Translating the summation variable by u0u_0 multiplies the sum by this scalar while leaving it unchanged, so the sum is zero. Thus

QαQβ={Qα,α=β,0,α≠β.Q_\alpha Q_\beta= \begin{cases} Q_\alpha, & \alpha=\beta,\\ 0, & \alpha\ne\beta. \end{cases}

The conjugation relations and ezr=ζreez^r=\zeta^r e now give

τvePvτv−1=κ−1∑u∈Kveϕv(u)zαv(ϕv(u))=eQαv.\tau_v eP_v\tau_v^{-1}=\kappa^{-1}\sum_{u\in K_v}e\phi_v(u)z^{\alpha_v(\phi_v(u))}=eQ_{\alpha_v}.

Packing into square matrices

The orthogonality in (4.8) now lets different coordinates share a slot without cross terms. The following matrices implement the assignment of each coordinate vv to its slot s(v)s(v).

Define C∈Mat⁡m×t(K[L])C \in\operatorname{Mat}_{m \times t}(K[L]) and J0∈Mat⁡t×m(K[L])J_0 \in\operatorname{Mat}_{t \times m}(K[L]) by

Cs,v={τvePv,s=s(v),0,s≠s(v),(J0)v,s={ePvτv−1,s=s(v),0,s≠s(v).C_{s,v} = \begin{cases} \tau_v eP_v, & s=s(v),\\ 0, & s\ne s(v), \end{cases} \qquad (J_0)_{v,s} = \begin{cases} eP_v\tau_v^{-1}, & s=s(v),\\ 0, & s\ne s(v). \end{cases}

We claim that

J0C=eP.J_0C=eP.

The diagonal entry indexed by vv is ePveP_v. If v≠wv\ne w have different slots, the corresponding entry is zero. If they have the same slot, (4.9) rewrites that entry as

ePvτv−1τwePw=τv−1eQαveQαwτw=0,eP_v\tau_v^{-1}\tau_w eP_w=\tau_v^{-1}eQ_{\alpha_v}eQ_{\alpha_w}\tau_w=0,

because αv≠αw\alpha_v\ne\alpha_w. This proves the claim.

Set

amat=UJ0+(1−e)Im,bmat=CT+(1−e)Im.a_{\mathrm{mat}}=UJ_0+(1-e)I_m,\qquad b_{\mathrm{mat}}=CT+(1-e)I_m.

Every entry of CC and J0J_0 contains the central factor ee. Consequently the cross terms with 1−e1-e vanish, and Equations (4.4) and (4.11) imply

amatbmat=U(eP)T+(1−e)Im=eIm+(1−e)Im=Im.a_{\mathrm{mat}}b_{\mathrm{mat}}=U(eP)T+(1-e)I_m=eI_m+(1-e)I_m=I_m.

Detecting the reverse defect

Put Δ=bmatamat−Im\Delta=b_{\mathrm{mat}}a_{\mathrm{mat}}-I_m. We detect its nonvanishing by multiplying on the left by J0J_0 and on the right by CC. This brings the calculation back from K[L]K[L] to its embedded subgroup algebra K[H]K[H], where a scalar specialization is available. Direct multiplication gives Δ=CTUJ0−eIm\Delta=CTUJ_0-eI_m, and hence

J0ΔC=(eP)TU(eP)−eP=e(TU−P).J_0\Delta C=(eP)TU(eP)-eP=e(TU-P).

In the last equality the order of multiplication is essential: (eP)TU(eP)=e(PT)(UP)=eTU(eP)TU(eP)=e(PT)(UP)=eTU. The right-hand side of (4.14) already belongs to Mat⁡t(K[H])\operatorname{Mat}_t(K[H]).

There is a KK-algebra homomorphism

ε:K[H]⟶K,ε(nzr)=ζr(n∈N).\varepsilon:K[H]\longrightarrow K,\qquad\varepsilon(nz^r)=\zeta^r\quad(n\in N).

It is well-defined because H=N×⟨z⟩H=N\times\langle z\rangle. It sends ee to 11 and each PvP_v to 11. Let X∈Mat⁡m×t(K)X\in\operatorname{Mat}_{m\times t}(K) be the matrix with columns xvx_v. Since the characteristic is two and κ\kappa is odd,

ε(U)=X,ε(T)=XT,XXT=Im.\varepsilon(U)=X,\qquad\varepsilon(T)=X^{\mathsf T},\qquad XX^{\mathsf T}=I_m.

Thus

ε(e(TU−P))=XTX−It.\varepsilon\bigl(e(TU-P)\bigr)=X^{\mathsf T}X-I_t.

Because t>mt>m, choose a nonzero y∈ker⁡Xy\in\ker X. Then

ε(e(TU−P))y=−y≠0.\varepsilon\bigl(e(TU-P)\bigr)y=-y\ne0.

One explicit choice is the first nonzero column of It−XTXI_t-X^{\mathsf T}X: this matrix is nonzero because rank⁡(XTX)≤m<t\operatorname{rank}(X^{\mathsf T}X)\le m<t, and X(It−XTX)=0X(I_t-X^{\mathsf T}X)=0. This choice uses only finite-field arithmetic on the given vectors.

Equation (4.17) proves that e(TU−P)e(TU-P) is nonzero in Mat⁡t(K[H])\operatorname{Mat}_t(K[H]). The embedding K[H]⊆K[L]K[H]\subseteq K[L] and (4.14) therefore show that Δ≠0\Delta\ne0. The homomorphism ε\varepsilon has been applied only to elements of K[H]K[H]; no extension of it to K[L]K[L] is used.

From matrices to two group-algebra elements

The square factors give a failure of stable finiteness for K[L]K[L]. To obtain scalar factors, we embed Mat⁡m(K[L])\operatorname{Mat}_m(K[L]) in an idempotent corner of K[L×F]K[L \times F] for a suitable finite group FF. The identity of this corner need not be the identity of the whole group algebra; adding its complement to both factors will give a scalar product equal to 11. This is an explicit instance of the finite-factor reduction of Dykema and Juschenko [6].

For the finite matrix block, let

B=(Z/ℓ)m,F=B⋊Sm.(7)B = (\mathbb{Z}/\ell)^m,\qquad F = B \rtimes S_m. \tag*{(7)}

where SmS_m permutes the coordinates. For 1≤i≤m1 \leq i \leq m define

pi=∣B∣−1∑w∈Bζ−wiw∈K[F].(8)p_i = |B|^{-1}\sum_{w\in B}\zeta^{-w_iw}\in K[F]. \tag*{(8)}

The coordinate characters are distinct. The character-sum calculation used in eq:4, now on BB, shows that the pip_i are pairwise orthogonal idempotents. Each is nonzero, since its identity coefficient is ∣B∣−1|B|^{-1}. This denominator exists because ∣B∣=ℓm|B|=\ell^m is odd. No inverse of ∣Sm∣|S_m| is required.

Let σi∈Sm\sigma_i\in S_m exchange coordinates 11 and ii, taking σ1=1\sigma_1=1. Then σip1σi−1=pi\sigma_i p_1\sigma_i^{-1}=p_i. Put

pij=σip1σj−1(1≤i,j≤m).(9)p_{ij}=\sigma_i p_1\sigma_j^{-1}\qquad(1\leq i,j\leq m). \tag*{(9)}

These elements are nonzero, being left and right translates of p1p_1, and they satisfy pii=pip_{ii}=p_i and pipijpj=pijp_i p_{ij}p_j=p_{ij}. For j≠kj\ne k the latter identity and pjpk=0p_jp_k=0 give pijpkr=0p_{ij}p_{kr}=0. For j=kj=k, direct cancellation gives pijpjr=σip12σr−1=pirp_{ij}p_{jr}=\sigma_i p_1^2\sigma_r^{-1}=p_{ir}. Thus

pijpkr=δjkpir.p_{ij}p_{kr}=\delta_{jk}p_{ir}.

The matrix units are linearly independent over KK: multiplying a linear relation on the left by pip_i and on the right by pjp_j isolates its coefficient of the nonzero element pijp_{ij}.

Take

G=L×F.G=L\times F.

We regard K[L]K[L] and K[F]K[F] as commuting subalgebras of K[G]K[G], and put

fblk=∑i=1mpii,Φ:Mat⁡m(K[L])⟶K[G],Φ(Z)=∑i,j=1mZijpij.(10)f_{\mathrm{blk}}=\sum_{i=1}^{m}p_{ii},\qquad\Phi:\operatorname{Mat}_m(K[L])\longrightarrow K[G],\qquad\Phi(Z)=\sum_{i,j=1}^{m}Z_{ij}p_{ij}. \tag*{(10)}

(4.21) proves that Φ\Phi is multiplicative and that Φ(Im)=fblk\Phi(I_m)=f_{\mathrm{blk}}. It is also injective. Indeed, the group basis identifies K[L×F]K[L\times F] with K[L]⊗KK[F]K[L]\otimes_K K[F]. If Φ(Z)=0\Phi(Z)=0, expand each entry as Zij=∑g∈Lcij,ggZ_{ij}=\sum_{g\in L}c_{ij,g}g. Comparing the LL-basis coefficient of each gg gives ∑i,jcij,gpij=0\sum_{i,j}c_{ij,g}p_{ij}=0. The linear independence just proved forces every cij,gc_{ij,g} to be zero.

The required two elements are

aout=1−fblk+∑i,j=1m((UJ0)ij+(1−ϵ)δij)pij,bout=1−fblk+∑i,j=1m((CT)ij+(1−ϵ)δij)pij.(11)\begin{aligned} a_{\mathrm{out}}&=1-f_{\mathrm{blk}}+\sum_{i,j=1}^{m}\bigl((UJ_0)_{ij}+(1-\epsilon)\delta_{ij}\bigr)p_{ij},\\ b_{\mathrm{out}}&=1-f_{\mathrm{blk}}+\sum_{i,j=1}^{m}\bigl((CT)_{ij}+(1-\epsilon)\delta_{ij}\bigr)p_{ij}. \tag*{(11)} \end{aligned}

Equivalently, these are 1−fblk+Φ(amat)1-f_{\mathrm{blk}}+\Phi(a_{\mathrm{mat}}) and 1−fblk+Φ(bmat)1-f_{\mathrm{blk}}+\Phi(b_{\mathrm{mat}}), respectively. The matrix-unit identities imply

fblk2=fblk,fblkΦ(Z)=Φ(Z)=Φ(Z)fblk.f_{\mathrm{blk}}^{2}=f_{\mathrm{blk}},\qquad f_{\mathrm{blk}}\Phi(Z)=\Phi(Z)=\Phi(Z)f_{\mathrm{blk}}.

Therefore 1−fblk1-f_{\mathrm{blk}} annihilates every image of Φ\Phi on both sides. It follows from Equation (4.13) that

aoutbout=1−fblk+Φ(Im)=1,a_{\mathrm{out}}b_{\mathrm{out}}=1-f_{\mathrm{blk}}+\Phi(I_m)=1,

whereas

boutaout−1=Φ(Δ)≠0b_{\mathrm{out}}a_{\mathrm{out}}-1=\Phi(\Delta)\ne0

by injectivity. Only the identity action of fblkf_{\mathrm{blk}} on the image of Φ\Phi is needed for these computations.

Finite presentation and the retained odd torsion

All sums in Equation (11) are finite, as are the sums defining their entries. We now verify the remaining assertions about the group GG by tracking its presentation through the construction.

Let N=⟨SN∣RN⟩N=\langle S_N\mid R_N\rangle be the finite presentation from Section 3, with the generators sf,cs_{f,c} and the local zero-sum relators of length at most three. With [x,y]=xyx−1y−1[x,y]=xyx^{-1}y^{-1}, the direct product with the cyclic group has the finite presentation

H=⟨SN,z | RN,zℓ,[z,s] (s∈SN)⟩.H=\left\langle S_N,z\ \middle|\ R_N,z^\ell,[z,s]\ (s\in S_N)\right\rangle.

Every element of KvK_v and K∗K_* in Equation (6) has a representative given by its local generator, or by the empty word for the identity. Using those representatives, that equation adds ∣V∣|V| stable letters and at most ∣V∣ℓ3|V|\ell^3 relators to the displayed presentation of HH: its indices are v∈Vv\in V, u∈Kvu\in K_v, and r∈Z/ℓr\in\mathbb{Z}/\ell. Hence LL is finitely presented. The permutation action used above proves that the base group embeds; its choices do not add generators or relators.

The group F=(Z/ℓ)m⋊SmF=(\mathbb{Z}/\ell)^m\rtimes S_m is finite, so its finite multiplication table gives a finite presentation. A presentation of G=L×FG=L\times F consists of finite presentations of the two factors on disjoint generator sets, together with the commutators of every generator of LL with every generator of FF. This adds only finitely many relators, and therefore GG is finitely presented. Finally, the embeddings already proved give

Kv≤N≤H≤L≤G.K_v\le N\le H\le L\le G.

Since KvK_v is the additive group of Fℓ2\mathbb{F}_{\ell}^{2}, its nonidentity elements have order ℓ\ell. The output group therefore contains the asserted odd-order torsion. This completes the proof of Theorem 3.1.

The construction proves a failure of direct finiteness for a group algebra by exhibiting its two elements. In particular, the last step does not infer stable finiteness from direct finiteness for an arbitrary ring: it uses the explicit finite group FF and the injective map Φ\Phi.

A regular hypergraph of affine lines

The algebraic criterion is now complete. Its remaining input is a line system satisfying Proposition 2.3: full lines avoiding a set of holes of controlled size, with exact regularity and incidence girth at least 12. Starting from line partitions gives regularity, but simply deleting the lines through a hole would lower the degree of other points as well. We instead arrange the lines through each hole in planar bundles that can be replaced by parallel lines missing the hole. Each replacement preserves every other point’s degree. We choose the holes to make these replacements compatible, then use random three-dimensional slabs to exclude the remaining short incidence cycles.

Let q=2hq = 2^h and let ℓ\ell be the least prime congruent to −1-1 modulo q100q^{100}. The residue q100−1q^{100}-1 is coprime to q100q^{100}. Linnik’s theorem [14] gives absolute constants c,L>0c, L > 0 such that this prime exists and ℓ≤cq100L\ell\le cq^{100L}; see, for example, [21], Theorem 1.1. Set

D=ℓ+1,s=⌊log⁡qD⌋,b=s+20,n=10b,Npt=qn.(12)D = \ell+ 1,\qquad s = \lfloor\log_q D \rfloor,\qquad b = s + 20,\qquad n = 10b,\qquad N_{\mathrm{pt}} = q^n. \tag*{(12)}

Thus q100∣Dq^{100} \mid D, s≥100s \ge100, and

qs≤D<qs+1.q^s \le D < q^{s+1}.

Moreover, ss is bounded independently of hh: indeed, D≤(c+1)q100LD \le(c+1)q^{100L} implies s≤100L+log⁡2(c+1)s \le100L+\log_2(c+1). In this section all asymptotic statements refer to h→∞h \to\infty. Constants implicit in O(⋅)O(\cdot) may depend on a fixed upper bound for ss, but not on hh, the field enumeration, or the indices of the objects being counted. Thus ss and nn may vary with hh, but the estimates below use fixed upper bounds for them.

The divisibility q∣Dq \mid D permits bundles of qq directions. The lower bound s≥100s \ge100 makes the hole-selection estimates small, and the slack in b=s+20b = s + 20 controls the later event weights. The factor ten in n=10bn = 10b permits ten-wise independent subspaces in the construction below. Each step of a short polygon will involve at most two of these subspaces, so their directness will cover polygons with at most five steps.

Let QQ be a field of order qq, with any enumeration (a0,…,aq−1)(a_0,\ldots,a_{q-1}), and put A=Qn\mathcal{A} = Q^n. Define

d0=(q−2)/2,S={(ai1,…,ain):i1+⋯+in≤d0}.d_0 = (q-2)/2,\qquad S = \{(a_{i_1},\ldots,a_{i_n}) : i_1+\cdots+i_n \le d_0\}.

An affine line always means a full translate of a one-dimensional QQ-subspace, and consequently contains exactly qq points.

Theorem 5.1. For all sufficiently large hh, for every QQ and enumeration as above, there are a set O⊂SO \subset S and a set F\mathcal{F} of affine lines contained in V=A∖OV = \mathcal{A} \setminus O such that

2NptD2≤∣O∣≤7NptD2,(13)\frac{2N_{\mathrm{pt}}}{D^2} \le|O| \le\frac{7N_{\mathrm{pt}}}{D^2}, \tag*{(13)}

every point of VV lies on exactly DD members of F\mathcal{F}, and the bipartite incidence graph of VV and F\mathcal{F} has girth at least 12.

Direction spaces and the local trade

Divide an index set of size DD into D/qD/q bundles of size qq. Write ρ(j)\rho(j) for the bundle containing an index jj.

Lemma 5.2. There are two-dimensional subspaces Wr⊂AW_r \subset\mathcal{A}, one per bundle, and (b−1)(b-1)-dimensional subspaces Ej⊂AE_j \subset\mathcal{A}, one per index, such that any at most ten distinct members of this list have direct sum. Choose a direction ere_r in each WrW_r, and assign its other qq directions bijectively to the indices in that bundle, calling them djd_j. Then Uj=dj⊕EjU_j = d_j \oplus E_j has dimension bb, and

Uj∩Uj′=0(j≠j′),Uj∩er=0,Uj∩Wr={dj,r=ρ(j),0,r≠ρ(j).U_j \cap U_{j'} = 0\quad(j \ne j'),\qquad U_j \cap e_r = 0,\qquad U_j \cap W_r = \begin{cases} d_j, & r = \rho(j),\\ 0, & r \ne\rho(j). \end{cases}

Proof. Let Q′/QQ'/Q be an extension of degree bb, and identify the QQ-space A\mathcal{A} with (Q′)10(Q')^{10}. For distinct ξ∈Q′\xi\in Q', the vectors (1,ξ,…,ξ9)(1,\xi,\ldots,\xi^9) have the property that any at most ten are linearly independent over Q′Q': the first kk coordinates of kk such vectors form an invertible Vandermonde matrix. There are enough parameters because D+D/q<qs+2≤qbD + D/q < q^{s+2} \leq q^b. Give each WrW_r and EjE_j its own parameter, and choose it, of the prescribed QQ-dimension, inside the corresponding one-dimensional Q′Q'-space. These choices have the required directness.

To verify the intersections, any equality involving UjU_j and Uj′U_{j'} first has zero EjE_j- and Ej′E_{j'}-components. Its remaining components belong either to independent WW-spaces or to distinct directions in one WW-space. In both cases they vanish. The other assertions follow the same way; within Wρ(j)W_{\rho(j)} the directions djd_j and eρ(j)e_{\rho(j)} are distinct.

Fix these spaces for the rest of the construction. The eventual preliminary partition indexed by jj will use varying directions in UjU_j, with o+djo+d_j its line through a hole oo; the spaces EjE_j provide the other directions. If these qq axes are present for a bundle rr, then inside o+Wro+W_r they can be replaced by the q−1q-1 lines parallel to ere_r other than o+ero+e_r. Each point off o+ero+e_r loses and gains one incidence, the hole loses qq, and the remaining points of o+ero+e_r are unaffected. Figure 2 illustrates this local count. The hole restrictions and slab construction below will supply these axes and make all the trades simultaneously possible.

Schematic of the trade inside $o+W_r$

Figure 2. Schematic of the trade inside o+Wro+W_r. Every point off o+ero+e_r loses and gains one incidence; oo loses qq incidences, and other points of o+ero+e_r are unaffected. The strokes illustrate line families, not a real-plane realization of finite-field incidences.

Choosing compatible holes

The replacement lines are parallel within a bundle, but lines from two bundles could form a rectangle. We prevent this while choosing the holes. An exceptional rectangle has corners x,x+u,x+u+v,x+vx,x+u,x+u+v,x+v, where 0≠u∈er0 \ne u \in e_r, 0≠v∈er′0 \ne v \in e_{r'}, and r≠r′r \ne r'. For each of its four side lines, a witness is a point off that line but in the translate of WrW_r or Wr′W_{r'} containing it, according to the side’s direction. If that side is produced by a trade, its hole is such a witness.

Lemma 5.3. For all sufficiently large hh, there is O⊂SO \subset S satisfying Equation (13) and the following properties.

(i) Every translate of every WrW_r contains at most one point of OO.

(ii) For every jj, every coset CC of UjU_j, and every rr, ∣O∩(C+Wr)∣≤100|O \cap(C + W_r)| \le100.

(iii) No exceptional rectangle has four distinct witnesses in OO, one for each of its four side lines.

Proof. Write M=Npt/D2M = N_{\mathrm{pt}}/D^2. Since d0<qd_0 < q, counting nonnegative index tuples gives ∣S∣=(d0+nn)|S| = \binom{d_0+n}{n}. For large hh, d0≥q/3d_0 \ge q/3, so

∣S∣≥qn3nn!≥cSNpt|S| \ge\frac{q^n}{3^n n!} \ge c_S N_{\mathrm{pt}}

with a constant cS>0c_S > 0 independent of hh, because nn is bounded. Choose each point of SS independently with probability θ=5M/∣S∣\theta= 5M/|S|. For large hh this is at most 11, and θ=O(D−2)\theta= O(D^{-2}). If XX is the chosen set, then E∣X∣=5M\mathbb{E}|X| = 5M and Var⁡(∣X∣)≤5M\operatorname{Var}(|X|) \le5M. Also M>qn−2s−2=q8s+198→∞M > q^{n-2s-2} = q^{8s+198} \to\infty. Chebyshev’s inequality therefore gives

Pr⁡(4M≤∣X∣≤6M)=1−o(1).\Pr(4M \le|X| \le6M) = 1-o(1).

There are at most D2NptD^2N_{\mathrm{pt}} triples (j,r,C)(j,r,C), and every C+WrC + W_r has at most qb+2q^{b+2} points. Repeated affine spaces in this count only cause overcounting. A union bound over choices of 100 selected points bounds the probability that any such space contains more than 100 points of XX by

D2Npt(θqb+2)100=O(q2s+2+n+100(b+2−2s))=O(q2402−88s)=o(1).D^2N_{\mathrm{pt}}(\theta q^{b+2})^{100} = O\left(q^{2s+2+n+100(b+2-2s)}\right) = O\left(q^{2402-88s}\right) = o(1).

Mark every selected point belonging to a pair of distinct selected points in one translate of some WrW_r. Also mark every selected point belonging to a tuple of four distinct selected witnesses for an exceptional rectangle. The expected number of collision pairs is at most Npt(D/q)q2θ2N_{\mathrm{pt}}(D/q)q^2\theta^2. There are at most Npt(D/q)2(q−1)2≤NptD2N_{\mathrm{pt}}(D/q)^2(q-1)^2 \le N_{\mathrm{pt}}D^2 choices of rectangle data, and at most q8q^8 witness tuples per rectangle. Each distinct tuple is selected with probability at most θ4\theta^4; tuples containing a point outside SS have probability zero. Thus the number ZZ of marked points satisfies

EZM≤2Npt(D/q)q2θ2+4NptD2q8θ4M=O(qD+q8D4)=o(1).\frac{\mathbb{E}Z}{M} \le\frac{2N_{\mathrm{pt}}(D/q)q^2\theta^2+4N_{\mathrm{pt}}D^2q^8\theta^4}{M} = O\left(\frac{q}{D}+\frac{q^8}{D^4}\right) = o(1).

Markov’s inequality gives Z≤MZ \le M with probability 1−o(1)1-o(1). Choose an outcome satisfying this bound, Equation (5.6), and the occupancy bound, and delete all marked points. The remaining set OO has 3M≤∣O∣≤6M3M \le|O| \le6M, hence the required bounds. Deletion preserves the occupancy bound and eliminates every obstruction in (i) and (iii).

Fix such an OO. Put

Tr=⋃o∈O(o+Wr).T_r = \bigcup_{o\in O}(o+W_r).

The replacement lines of label RrR_r are all the lines of direction ere_r in each o+Wro+W_r, except o+ero+e_r itself.

Lemma 5.4. The replacement lines avoid OO and are pairwise disjoint within each label RrR_r. No exceptional rectangle has all four side lines among these replacement lines.

Proof. Property (i) of Lemma 5.3 says that different holes lie in disjoint translates of a fixed WrW_r. Within one such plane the replacement lines are parallel and omit its unique hole. This proves the first assertions.

If a rectangle used four replacement lines, each side would have its corresponding hole as a witness. These four witnesses must be distinct. Opposite sides of direction ere_r lie in WrW_r-cosets separated by a nonzero vector in er′e_{r'}, which lies outside WrW_r. Their planes are therefore disjoint. The planes of two adjacent sides intersect exactly at their shared corner, because Wr∩Wr′=0W_r \cap W_{r'} = 0. This corner is on both side lines, so neither off-line witness can equal it. The resulting four distinct witnesses contradict property (iii) of Lemma 5.3.

Random slabs and short polygons

The holes and the replacement lines are now fixed. It remains to partition the rest of the space into lines without introducing short polygons. We first choose the slabs in which those lines will lie, excluding a finite list of events that would allow such polygons; the line partitions themselves are constructed only afterward.

Independently for each index jj and each coset CC of UjU_j, choose a uniformly random two-dimensional subspace Pj,C⊂EjP_{j,C} \subset E_j. The translates of dj⊕Pj,Cd_j \oplus P_{j,C} partition CC into three-dimensional affine slabs. For u∈Uju \in U_j, write u(Ej)u^{(E_j)} for its EjE_j-component. A fixed nonzero vector of EjE_j belongs to Pj,CP_{j,C} with probability

p∗=q2−1qb−1−1≤2q3−b.p_* = \frac{q^2-1}{q^{b-1}-1} \le2q^{3-b}.

Indeed, linear automorphisms of EjE_j act transitively on its nonzero vectors, and every two-dimensional subspace contains q2−1q^2-1 of them.

We define a finite list of bad events before selecting any lines inside the slabs. First, for each pair of holes in a coset CC of UjU_j, declare it bad if they occupy the same slab. Their difference has nonzero EjE_j-component: otherwise it would lie in dj⊂Wρ(j)d_j \subset W_{\rho(j)}, contrary to Lemma 5.3(i). This event is exactly the inclusion of that component in Pj,CP_{j,C} and has probability p∗p_*.

The other events concern closed labelled sequences of kk nonzero steps, k∈{3,4,5}k \in\{3,4,5\}, in A\mathcal{A}. The allowed step types are

Gj:u∈Uj,u(Ej)≠0;Rr:u∈er∖{0},both endpoints belong to Tr.\begin{aligned} G_j &: \quad u \in U_j,\quad u^{(E_j)} \ne0;\\ R_r &: \quad u \in e_r \setminus\{0\},\quad\text{both endpoints belong to } T_r. \end{aligned}

We call GjG_j steps generic and RrR_r steps replacement steps; a replacement step vector will also be called exceptional. An RrR_r step need not lie on a replacement line: its endpoint condition only requires membership in TrT_r, which every actual replacement line satisfies. This deliberately enlarges the list of possible polygons. Require at least one GG step and distinct labels at cyclically adjacent steps. Repeated vertices are allowed, so this list can only be larger than the list of simple polygons that will matter for girth. For each such sequence, declare it bad if every GjG_j step has u(Ej)∈Pj,Cu^{(E_j)} \in P_{j,C}, where CC is the UjU_j-coset containing that step. All point, label, and step choices are finite, so the complete event list is finite.

The three hole conditions now have separate roles. Condition (i) separates the replacement planes within each bundle and makes each hole-pair event test a nonzero EjE_j-component. Condition (ii) controls the hole contributions to the event counts for a fixed Pj,CP_{j,C}. Condition (iii) has already excluded rectangles formed entirely from replacement lines.

Lemma 5.5. Every candidate sequence with a generic step has one of the following forms.

(i) A rectangle alternating GjG_j, RrR_r, with opposite vectors paired.

(ii) A rectangle alternating distinct GjG_j, Gj′G_{j'}, with opposite vectors paired.

(iii) A pentagon containing two GjG_j steps, two Gj′G_{j'} steps, and one RrR_r step, where ρ(j)=ρ(j′)=r\rho(j)=\rho(j')=r.

If gg is the number of distinct generic labels, its bad event uses 2g2g distinct random variables and has probability p∗2gp_*^{2g}. In case (iii), the exceptional vector and one vector of each generic label determine the other two vectors, once their order is fixed.

Proof. Before classifying the sequence, observe that each step involves at most two members of the list of WW- and EE-spaces. Thus at most 2k≤102k \le10 distinct spaces occur, and their directness is available from Lemma 5.2. Closure forces the sum of the EjE_j-components to be zero for each generic label. Each such label therefore occurs at least twice. Cyclic non-adjacency in a sequence of at most five steps allows any label at most twice. Consequently gg is 1 or 2, and each generic label occurs exactly twice.

If g=1g=1, the direction djd_j and the distinct occurring directions ere_r are linearly independent. In its own bundle this uses just the two distinct directions djd_j, eρ(j)e_{\rho(j)}; other bundles contribute independent WW-spaces. Every exceptional label must therefore occur twice as well. Only case (i) is possible, and closure gives the claimed opposite vectors.

If g=2g=2 and k=4k=4, the labels must alternate, and Uj∩Uj′=0U_j \cap U_{j'}=0 forces the opposite vectors to pair. If k=5k=5, there is one exceptional step, of label RrR_r. Its nonzero ere_r-component must be canceled by the WW-components of the generic steps. Neither zero contribution nor a contribution from just one of the directions dj,dj′d_j,d_{j'} can cancel it, since each such direction differs from ere_r. Thus both generic labels belong to bundle rr, giving case (iii). After choosing the exceptional vector and one vector of each generic label, closure prescribes the sum of the remaining vector in UjU_j and the remaining vector in Uj′U_{j'}. Their direct sum makes these vectors unique.

Finally, between the two occurrences of a generic label GjG_j there is, in one cyclic direction, exactly one intervening step. That step has a different label and a nonzero vector outside UjU_j, by Equation (5.5). The two occurrences therefore belong to different UjU_j-cosets: if the first starts at xx with vector u∈Uju \in U_j and the intervening vector is v∉Ujv \notin U_j, the second starts at x+u+v∉x+Ujx+u+v \notin x+U_j. Variables from different generic labels are also distinct. All 2g2g variables are consequently independent, and Equation (5.7) gives the asserted event probability. □

Avoiding the slab events

The classification controls the probability of each polygon event. To avoid all events simultaneously, we must also control how many of them use any one slab variable. We bound the sum of their probabilities at a fixed Pj,CP_{j,C}; the local lemma will apply once this bound is at most 1/161/16.

Lemma 5.6. Let μ\mu be the largest, over all variables Pj,CP_{j,C}, of the sum of probabilities of bad events using that variable. Then μ=O(q−7)\mu=O(q^{-7}), uniformly in the variable, and every event uses at most four variables.

Proof. The assertion about four variables follows from Lemma 5.5, with one variable for a hole-pair event. Fix Pj,CP_{j,C}. There are at most 100 holes in CC, since C⊂C+WrC \subset C+W_r for any rr. Hole pairs therefore contribute at most 100p∗100p_*.

For a polygon using this variable, cyclically rotate so that one of its GjG_j steps starts the sequence. Rotations and orders of at most five labels introduce only an absolute constant factor in all the following counts. For a generic rectangle choose the other label (≤D\le D choices), the sequence’s initial point in CC (qbq^b choices), and one vector of each label (≤q2b\le q^{2b} choices). Closure determines the other two vectors. The contribution is therefore O(Dq3bp∗4)O(Dq^{3b}p_*^4).

For a mixed rectangle GjG_j, RrR_r, both endpoints of the initial generic step belong to C∩TrC\cap T_r. A hole oo can contribute to this intersection only if o∈C+Wro\in C+W_r, so there are at most 100 such holes. Each intersection C∩(o+Wr)C\cap(o+W_r), when nonempty, is a coset of Uj∩WrU_j\cap W_r. It has qq points if r=ρ(j)r=\rho(j) and one point otherwise. Thus C∩TrC\cap T_r has at most 100q100q points in the first case and at most 100 in the second. Choose the two endpoints, and then choose the exceptional vector in ere_r in at most qq ways. Summing over the D/qD/q bundles gives at most

O(1002(q3+Dqq))=O(1002(q3+D))O\left(100^2\left(q^3+\frac{D}{q}q\right)\right)=O\left(100^2(q^3+D)\right)

mixed rectangles, and hence a contribution O(1002(q3+D)p∗2)O(100^2(q^3+D)p_*^2). This is an upper bound even when some selected endpoints or vectors fail the candidate conditions.

For a pentagon the other generic label is in bundle ρ(j)\rho(j), giving at most qq choices. Choose the sequence’s initial point in CC, one vector of each generic label, and the exceptional vector. There are at most qb+2b+1q^{b+2b+1} choices after the label is chosen. Lemma 5.5 determines the remaining vectors, so the contribution is O(q3b+2p∗4)O(q^{3b+2}p_*^4).

In total,

μ≤1002p∗+O(Dq3bp∗4+(D+q3)p∗2+q3b+2p∗4)=O(q−s−17+q−7+q−s−33+q−2s−31+q−s−6)=O(q−7),\begin{aligned} \mu\le100^2p_*+O\left(Dq^{3b}p_*^4+(D+q^3)p_*^2+q^{3b+2}p_*^4\right) \\ &=O\left(q^{-s-17}+q^{-7}+q^{-s-33}+q^{-2s-31}+q^{-s-6}\right)=O(q^{-7}), \end{aligned}

using b=s+20b=s+20, (5.2), and (5.7). The constants in these event counts are absolute; in particular the bound is uniform.

The following is a special case of the asymmetric Lovász local lemma; we include the classical conditional-probability proof. For the origins see Erdős and Lovász [9]; for the product-form condition used below see [16]. No resampling algorithm is needed.

Lemma 5.7. Let a finite collection of events be determined by independent random variables, with each event assigned a nonempty set of at most four variables that determine it. If the sum of event probabilities at every variable is at most 1/161/16, there is positive probability that no event occurs.

Proof. Connect two events when their assigned sets share a variable. An event is independent of all its non-neighbors jointly. Set xA=2Pr⁡(A)x_A=2\Pr(A). Since each event has a nonempty assigned set, 0≤xA≤1/8<10\le x_A\le1/8<1, and for every event

∑B neighbor of AxB≤2⋅4⋅116=12.\sum_{B\text{ neighbor of }A}x_B\le2\cdot4\cdot\frac{1}{16}=\frac{1}{2}.

It follows that

Pr⁡(A)≤xA∏B neighbor of A(1−xB),\Pr(A)\le x_A\prod_{B\text{ neighbor of }A}(1-x_B),

because the product is at least 1−∑BxB≥1/21-\sum_B x_B\ge1/2.

We prove inductively that

Pr⁡(A∣⋂B∈SBc)≤xA\Pr\left(A\mathrel{\Big|}\bigcap_{B\in\mathcal{S}}B^c\right)\le x_A

whenever SS is a sublist excluding AA, and that all conditioning events in this assertion have positive probability. The empty sublist follows from (5.8). At each induction step, positivity for a sublist follows by exposing its events in order and using the smaller conditional bounds and xB<1x_B < 1. For the bound, split SS into neighbors and non-neighbors of AA. Let B0B_0 be avoidance of the non-neighbors and D0D_0 avoidance of the neighbors. Independence gives Pr⁡(A∣B0)=Pr⁡(A)\Pr(A \mid B_0) = \Pr(A), and

Pr⁡(A∣B0∩D0)≤Pr⁡(A)Pr⁡(D0∣B0)≤Pr⁡(A)∏B∈S, B neighbor of A(1−xB)≤xA.\Pr(A \mid B_0 \cap D_0) \le\frac{\Pr(A)}{\Pr(D_0 \mid B_0)} \le\frac{\Pr(A)}{\prod_{B \in S,\ B\text{ neighbor of }A}(1-x_B)} \le x_A.

The middle bound uses the smaller conditional bounds successively; the last uses (5.8). The same successive conditioning for the full finite event list gives positive probability of avoiding all events.

By Lemmas 5.6 and 5.7, for all sufficiently large hh we can fix the spaces Pj,CP_{j,C} so that every slab contains at most one hole and none of the candidate polygon events occurs.

Line partitions, the local trade, and girth

The slab choices have excluded every candidate short polygon with a generic step, but no line partition has yet been specified. We now partition each slab, perform the trades that remove the holes, and check that every possible short incidence cycle is one of the excluded polygons.

Lemma 5.8. Let a three-dimensional affine space have direction P⊕dP \oplus d, where dim⁡QP=2\dim_{\mathbb{Q}} P = 2 and dim⁡Qd=1\dim_{\mathbb{Q}} d = 1. If it has no designated point, it has a line partition whose directions project nontrivially to PP. If it has a designated point oo, it has a line partition containing o+do + d, with every other line’s direction projecting nontrivially to PP.

Proof. In the first case use parallel lines of any fixed nonzero direction in PP. In the second choose 0≠δ∈d0 \ne\delta\in d and a Q\mathbb{Q}-linear operator JJ on PP with no eigenvector over Q\mathbb{Q}. Identify PP with the Q\mathbb{Q}-space of a quadratic field extension of Q\mathbb{Q}, and let JJ be multiplication by an element η\eta outside Q\mathbb{Q}. An equation ηx=λx\eta x = \lambda x with x≠0x \ne0 and λ∈Q\lambda\in\mathbb{Q} would imply η=λ\eta= \lambda, so this operator has the required property. Besides o+do + d, use the lines

{o+x+γ(Jx)δ:x∈P, γ(x)=1},0≠γ∈Hom⁡Q(P,Q).(14)\{o + x + \gamma(Jx)\delta: x \in P,\ \gamma(x) = 1\}, \qquad0 \ne\gamma\in\operatorname{Hom}_{\mathbb{Q}}(P,\mathbb{Q}). \tag*{(14)}

The set γ(x)=1\gamma(x) = 1 is an affine line in PP. Its displayed lift is injective, with direction projecting onto the nonzero line ker⁡γ\ker\gamma, so it is an affine line with the required direction. For each x≠0x \ne0, the vectors x,Jxx, Jx form a basis of PP. For every c∈Qc \in\mathbb{Q} there is consequently exactly one functional with γ(x)=1\gamma(x) = 1 and γ(Jx)=c\gamma(Jx) = c, and it is nonzero. Thus the q2−1q^2 - 1 lines in (14) partition the q3−qq^3 - q points off o+do + d. The axis o+do + d supplies the remaining qq points.

For each jj, apply Lemma 5.8 separately in every slab of every coset of UjU_j, using its unique hole as the designated point when present. This gives a preliminary line partition of all of A\mathcal{A} for each jj. The line through a hole oo in partition jj is o+djo + d_j. These hole axes are the only lines whose directions have zero EjE_j-component. Every other line has a nonzero EjE_j-component in its direction, lying in the corresponding Pj,CP_{j,C}.

Lemma 5.9. For every hole oo and bundle rr, remove the qq lines o+djo + d_j with ρ(j)=r\rho(j) = r, and insert the q−1q - 1 replacement lines of label RrR_r in o+Wro + W_r. After all these operations, the resulting set F\mathcal{F} consists of lines in VV, and every point of VV has degree DD. The surviving lines of each preliminary partition are pairwise disjoint, as are the replacement lines within each label. There are no duplicate lines across different labels. Proof. Within o+Wro + W_r, the removed fan uses every direction except ere_r. Each point off o+ero + e_r lies on exactly one removed line and exactly one inserted line. The hole oo loses qq incidences and gains none; other points of o+ero + e_r lose and gain none. Thus every non-hole point has zero net change in degree in each trade.

No removal is requested twice. Two holes using the same line of one preliminary partition would be in the same slab, which was excluded. Lines from distinct preliminary partitions have directions in distinct UjU_j’s with zero intersection, so cannot coincide. Inserted lines of a given label are distinct by Lemma 5.4. Lines of different labels cannot coincide either: their direction spaces are distinct UjU_j’s or ere_r’s with pairwise zero intersections, by Lemma 5.2. Hence the pointwise degree changes genuinely add when all trades are performed, even if planes from different bundles overlap. Initially every point has one incidence in each of the DD partitions. Each hole loses all DD of its incidences, and every non-hole retains degree DD. All inserted lines avoid the holes, and all preliminary lines through a hole were removed. Finally, disjointness within a surviving preliminary label is inherited from its partition, and disjointness within a replacement label was proved in Lemma 5.4.

The pointwise incidence changes are summarized in Figure 2.

Proof of Theorem 5.1. Use the holes from Lemma 5.3, the successful slab choices, and the line family from Lemma 5.9. The size and degree assertions have been proved. Label surviving preliminary lines from partition jj by GjG_j, and replacement lines by their labels RrR_r.

Two distinct affine lines have at most one common point, so a cycle of length less than 12 in the incidence graph would give a polygon of k=3k = 3, 44, or 55 nonzero steps along its successive lines. Consecutive labels, including the last and first, are different because lines of one label are disjoint. If there is a generic step, this polygon is one of the candidate sequences used above. Each generic step’s EjE_j-component lies in its slab direction Pj,CP_{j,C}, so the corresponding bad event would occur, a contradiction.

If all steps have replacement labels, the distinct occurring ere_r directions are independent: at most five WrW_r’s occur. Closure forces every label to occur at least twice, while cyclic non-adjacency allows at most twice. The only possibility is a four-step alternating rectangle, with opposite vectors paired. This is forbidden by Lemma 5.4. Thus the incidence girth is at least 12.

This supplies the full-line system, exact degree, and girth required by Proposition 2.3. That proposition uses the same holes to produce the two matrix pairings and the size inequalities for Theorem 3.1. Section 6 now makes the choices by finite enumeration.

A terminating prescription for the witnesses

We now fix every choice in the preceding construction. The purpose of the prescription is to define one field, one group, and two finite sums without relying on an unspecified successful random choice.

Finite search for the incidence data

Order binary coefficient vectors lexicographically, with 0<10 < 1; for a polynomial of fixed degree use the list of coefficients in increasing degree order. For each integer h≥2h \ge2, perform the following finite computations. (1) Put q=2hq = 2^h, and let ℓ\ell be the least prime congruent to −1-1 modulo q100q^{100}. Test successive integers in that class for primality. Linnik’s theorem guarantees that this search terminates. Define D=ℓ+1D = \ell+ 1, s=⌊log⁡qD⌋s = \lfloor\log_q D\rfloor, b=s+20b = s + 20, and n=10bn = 10^b as in Section 5.

(2) Let gg be the lexicographically first monic irreducible polynomial over F2\mathbb{F}_2 of degree h(ℓ−1)h(\ell- 1), and put

K=F2[Z]/(g(Z)).(15)K = \mathbb{F}_2[Z]/(g(Z)). \tag*{(15)}

Order KK by the coefficient vectors of its unique representatives of degree less than h(ℓ−1)h(\ell- 1), padded by zeros. Irreducible polynomials of this degree exist, and irreducibility is a finite test.

(3) Take the subfield

Q={x∈K:xq=x},Q = \{x \in K : x^q = x\},

with its induced order. It has qq elements since hh divides h(ℓ−1)h(\ell- 1). Let ζ\zeta be the first element of KK of multiplicative order ℓ\ell. Such an element exists: Fermat’s little theorem gives ℓ∣2ℓ−1−1\ell\mid2^{\ell-1} - 1, so ℓ\ell divides ∣K×∣=2h(ℓ−1)−1|K^\times| = 2^{h(\ell-1)} - 1, and K×K^\times is cyclic.

(4) Form A=Qn\mathcal{A} = Q^n in lexicographic order and the index simplex SS of Section 2. Order subsets of a finite ordered set by their indicator vectors, with 0<10 < 1. In particular this orders affine lines as subsets of A\mathcal{A}, families of lines as subsets of the ordered line set, and pairs (O,F)(O,\mathcal{F}) lexicographically. Test every pair with O⊂SO \subset S and F\mathcal{F} a family of full affine QQ-lines for the following conditions:

(a) 2qn/D2≤∣O∣≤7qn/D22q^n/D^2 \le|O| \le7q^n/D^2;

(b) every line of F\mathcal{F} is contained in A∖O\mathcal{A} \setminus O;

(c) every point of A∖O\mathcal{A} \setminus O lies on exactly DD lines of F\mathcal{F};

(d) the incidence graph has no cycle of length less than 12.

Start with h=2h = 2. For a fixed hh, step (4) tests only finite sets and a finite graph. Stop at the first successful pair; if every pair fails, increase hh by one and repeat. This selects the least successful hh and then the first successful pair in its prescribed order. Theorem 5.1 guarantees success for every sufficiently large hh, uniformly in the enumeration of QQ, so the outer search terminates. The search enumerates the required incidence data directly, not the auxiliary random choices used to prove their existence. The auxiliary extension field in that proof is only a model for a QQ-vector space; it is not required to embed in KK.

Fix these data and write m=∣O∣m = |O|, t=∣V∣t = |V|, where V=A∖OV = \mathcal{A} \setminus O. The indicator polynomials fof_o and vectors xvx_v are the unique ones from Proposition 2.3; their coefficients may be computed by finite-field linear algebra. We use the induced orders on OO, VV, and F\mathcal{F}.

Local groups, the presentation, and the two sums

At each point vv, use the standard coordinate copy Kv0=(Fℓ2,+)K_v^0 = (\mathbb{F}_\ell^2,+), and for each line ff use Lf0=(Fℓ,+)L_f^0 = (\mathbb{F}_\ell,+). Order Fℓ\mathbb{F}_\ell by the residues 0,…,ℓ−10,\ldots,\ell- 1 and Fℓ2\mathbb{F}_\ell^2 lexicographically. Order its one-dimensional subspaces as subsets. Match them in order to the D=ℓ+1D = \ell+ 1 incident lines at vv, and define vfv_{f} by sending 1∈Lf01 \in L_f^0 to the first nonzero vector of the assigned direction. These maps specify the group NN in Lemma 3.2 without any further choices.

Choose v∗v_* to be the first point of VV. The isomorphism ϕv:Kv→Kv∗\phi_v: K_v \to K_{v_*} preserves the standard coordinates transported from the embedded copies. Order linear forms on Fℓ2\mathbb{F}_{\ell}^{2} by their coefficient pairs. Assign the points of VV, in order, to the first tt pairs

(s,α),1≤s≤m,α∈(Fℓ2)∗,(s,\alpha), \qquad1 \le s \le m,\quad\alpha\in(\mathbb{F}_{\ell}^{2})^*,

in lexicographic order. Proposition 2.3 gives t≤mℓ2t \le m\ell^2, so there are enough pairs. This fixes every slot and every character in the construction of Theorem 3.1.

For the finite presentation of NN, use the local zero-sum relators of length at most three, as justified in Section 3. Section 4 then defines H=N×⟨z⟩H=N \times\langle z\rangle, the conjugation extension LL, the finite group F=(Z/ℓ)m⋊SmF=(\mathbb{Z}/\ell)^m \rtimes S_m, and finally G=L×FG=L \times F; Section 4.6 gives the resulting finite presentation. The regular-permutation action used to prove that HH embeds in LL is an embedding certificate; a choice of such permutations is not part of the definition of the group.

With this group fixed, the formulas in Section 4 give ee, PP, UU, TT, CC, J0J_0, the two square matrices amata_{\mathrm{mat}}, bmatb_{\mathrm{mat}}, and the matrix units pijp_{ij}. The two required finite expressions are

aout=1−∑i=1mpii+∑i,j=1m(amat)ijpij,a_{\mathrm{out}}=1-\sum_{i=1}^{m}p_{ii}+\sum_{i,j=1}^{m}(a_{\mathrm{mat}})_{ij}p_{ij},
bout=1−∑i=1mpii+∑i,j=1m(bmat)ijpij.(16)b_{\mathrm{out}}=1-\sum_{i=1}^{m}p_{ii}+\sum_{i,j=1}^{m}(b_{\mathrm{mat}})_{ij}p_{ij}. \tag*{(16)}

Coefficients from K[L]K[L] and matrix units from K[F]K[F] are viewed in the two factors of K[G]K[G]. The displayed expressions, together with the preceding formulas, involve only finitely many group words and field coefficients. They define finite sums whether or not distinct displayed words represent the same group element; no word-equality oracle is used to normalize them.

Proof of Theorem 1.1. The finite search terminates by Theorem 5.1. Its output satisfies Proposition 2.3, and hence every hypothesis of Theorem 3.1. That theorem proves the two product assertions for (16), supplies a finite presentation of this group GG, and retains an embedded element of order ℓ\ell. In particular the nonvanishing of the reverse-product defect follows by specializing the right-hand side of Equation (4.14), which lies in Mat⁡t(K[H])\operatorname{Mat}_{t}(K[H]), to a nonzero matrix over KK; it does not depend on an unproved inequality between group words. The prime ℓ\ell is odd, and the field in (15) is finite of characteristic two.

Scope of the construction

The construction uses torsion explicitly. The embedded subgroups of orders ℓ\ell, ℓ2\ell^2, and ℓ3\ell^3 have odd order, so every denominator in their averages is invertible in KK. In the finite auxiliary group we invert only ∣(Z/ℓ)m∣\lvert(\mathbb{Z}/\ell)^m\rvert, never ∣Sm∣\lvert S_m\rvert. Characteristic two makes the regular degree ℓ+1\ell+1 vanish as a scalar, allowing the simultaneous linear and total pairing identities of Proposition 2.3. No assertion about group algebras of torsion-free groups is needed.

For comparison, if G0G_0 is finite, then K0[G0]K_0[G_0] is finite dimensional over every field K0K_0, even when the characteristic divides ∣G0∣\lvert G_0\rvert. Left multiplication is a faithful representation of this algebra. In finite dimension, LaLb=IL_aL_b=I implies LbLa=IL_bL_a=I, and hence ab=1ab=1 implies ba=1ba=1. Thus the group in Theorem 1.1 is necessarily infinite.

Finally, for any group and any two finite group-algebra sums, the union of their supports generates a finitely generated subgroup. Its group algebra embeds in the original one, so both product assertions already hold or fail in that subgroup algebra. Finite generation is therefore automatic for a direct-finiteness counterexample after passing to the support subgroup. The stronger finite-presentation conclusion for the particular group GG here comes from the presentation argument in Section 4.6; it does not follow merely from finite generation of the support subgroup.

An injective nonsurjective cellular automaton

The scalar elements constructed in Section 6 now give a cellular automaton over the finite alphabet KK. We prove the standard transfer explicitly, in the right-neighbor convention used in the introduction; compare [8], Section 1. The proof applies to all configurations, not just finitely supported ones, and identifies the image by finite local equations.

The group algebra acting on all configurations

For this subsection, let KK be any field and GG any group, with identity 1G1_G. For c=∑u∈Gcuu∈K[G]c=\sum_{u\in G}c_u u\in K[G], put supp⁡(c)={u∈G:cu≠0}\operatorname{supp}(c)=\{u\in G:c_u\ne0\}. Multiplication in K[G]K[G] is

(cd)w=∑uv=wcudv.(cd)_w=\sum_{uv=w}c_u d_v.

Every sum has only finitely many nonzero terms. Define a KK-linear map Tc:KG→KGT_c:K^G\to K^G by

(Tcx)(g)=∑u∈Gcux(gu).(T_cx)(g)=\sum_{u\in G}c_u x(gu).

This sum is finite even when xx has infinite support. If KK is finite, it is a cellular automaton with memory supp⁡(c)\operatorname{supp}(c).

Lemma 7.1. For every field KK and group GG, the assignment c↦Tcc\mapsto T_c is a faithful unital KK-algebra homomorphism from K[G]K[G] to the algebra of KK-linear endomorphisms of KGK^G, with composition as multiplication. In particular,

Tc∘Td=Tcd,T1=id⁡KG.(17)T_c\circ T_d=T_{cd},\qquad T_1=\operatorname{id}_{K^G}. \tag*{(17)}

Proof. Linearity in cc and the identity T1=id⁡KGT_1=\operatorname{id}_{K^G} follow directly from (7.1). For x∈KGx\in K^G and g∈Gg\in G,

(Tc(Tdx))(g)=∑u∈Gcu∑v∈Gdvx(guv)=∑w∈G(∑uv=wcudv)x(gw)=(Tcdx)(g).\begin{aligned} (T_c(T_dx))(g) &=\sum_{u\in G}c_u\sum_{v\in G}d_vx(guv)\\ &=\sum_{w\in G}\left(\sum_{uv=w}c_ud_v\right)x(gw)=(T_{cd}x)(g). \end{aligned}

All sums being regrouped are finite. In particular, the product is cdcd, not dcdc, for this right-neighbor convention.

For h∈Gh\in G, let δh∈KG\delta_h\in K^G take value 1K1_K at hh and zero elsewhere. Then

(Tcδh)(1G)=ch.(T_c\delta_h)(1_G)=c_h.

Thus Tc=0T_c=0 implies that every coefficient chc_h is zero, proving faithfulness.

The local rule and its image

Proposition 7.2. Let KK be a finite field, GG a group, and a,b∈K[G]a,b \in K[G] satisfy ab=1ab=1. Put M=supp⁡(b)M=\operatorname{supp}(b) and define

ϕ:KM⟶K,ϕ(p)=∑u∈Mbup(u).(18)\phi:K^{M}\longrightarrow K,\qquad\phi(p)=\sum_{u\in M}b_{u}p(u). \tag*{(18)}

The cellular automaton τ=Tb\tau=T_b is injective, and

im⁡(τ)={y∈KG:Tbay=y}.(19)\operatorname{im}(\tau)=\{y\in K^{G}:T_{ba}y=y\}. \tag*{(19)}

If ba≠1ba\ne1, every h∈Gh\in G with (ba−1)h≠0(ba-1)_{h}\ne0 gives a configuration δh∉im⁡(τ)\delta_{h}\notin\operatorname{im}(\tau); hence τ\tau is not surjective.

Proof. The support of bb is finite, so Equation (18) is a single finite-memory local rule, used at every g∈Gg\in G. The alphabet KK is finite and nonempty. Lemma 7.1 gives

Ta∘τ=Tab=T1=id⁡KG.(20)T_a\circ\tau=T_{ab}=T_1=\operatorname{id}_{K^{G}}. \tag*{(20)}

Applying TaT_a to τ(x)=τ(x′)\tau(x)=\tau(x') yields x=x′x=x' for arbitrary x,x′∈KGx,x'\in K^{G}.

If y=τ(x)=Tbxy=\tau(x)=T_bx, then

Tbay=TbTaTbx=Tbx=y,T_{ba}y=T_bT_aT_bx=T_bx=y,

by Equation (20). Conversely, if Tbay=yT_{ba}y=y, then y=Tb(Tay)y=T_b(T_ay) lies in the image of τ\tau. This proves Equation (19).

If (ba−1)h≠0(ba-1)_{h}\ne0, Equation (7.3) gives

(Tbaδh−δh)(1G)=(Tba−1δh)(1G)=(ba−1)h≠0.(T_{ba}\delta_h-\delta_h)(1_G)=(T_{ba-1}\delta_h)(1_G)=(ba-1)_h\ne0.

Therefore δh\delta_h is not fixed by TbaT_{ba}, and Equation (19) excludes it from the image. This calculation also covers h=1Gh=1_G, when δh(1G)=1K\delta_h(1_G)=1_K rather than zero.

Equation (19) describes the image by the uniform finite local equations

∑u∈supp⁡(ba−1)(ba−1)u y(gu)=0(g∈G).\sum_{u\in\operatorname{supp}(ba-1)}(ba-1)_u\,y(gu)=0\qquad(g\in G).

Thus the missing configuration has no preimage even among infinitely supported functions. No restriction to finitely supported configurations has entered the argument.

The memory need not be minimal. If a finite expression for bb is b=∑j=1rλjujb=\sum_{j=1}^{r}\lambda_j u_j, with λj∈K\lambda_j\in K and uj∈Gu_j\in G and with repetitions allowed, take M′={uj:1≤j≤r}M'=\{u_j:1\le j\le r\} and ϕ(p)=∑j=1rλjp(uj)\phi(p)=\sum_{j=1}^{r}\lambda_jp(u_j). Repeated group elements automatically combine to give the same operator TbT_b. Consequently, the finite word expressions of Equation (6.2) specify the local rule without an algorithm deciding which displayed words represent the same group element.

Corollary 7.3. For the field KK, group GG, and outputs of Theorem 1.1, the cellular automaton Tbout:KG→KGT_{b_{\mathrm{out}}}:K^{G}\to K^{G} is injective and not surjective. Its image is the fixed set of TboutaoutT_{b_{\mathrm{out}}a_{\mathrm{out}}}. In particular, GG is not surjunctive.

Proof. Apply Proposition 7.2 to a=aouta=a_{\mathrm{out}} and b=boutb=b_{\mathrm{out}}. Their product relations are proved in Theorem 1.1, and the nonzero reverse-product defect has a nonzero coefficient in the ordinary group algebra.

Characteristic two is used to construct the algebraic witnesses, not in Proposition 7.2. Finiteness of the field supplies the finite alphabet, and the scalar form of the witnesses makes that alphabet KK itself rather than a vector space over KK. The existence of a nonzero defect coefficient is certified algebraically; no practical execution of the finite search or normalization of group words is asserted.

Transport to a group of type F∞F_\infty

A group has type F∞F_\infty if it admits a classifying CW complex with finitely many cells in every dimension. The finite presentation of GG allows a further consequence: a separate embedding theorem transports the same scalar counterexample to an overgroup of type F∞F_\infty.

Corollary 7.4. For the finite characteristic-two field KK of Theorem 1.1, there are a group UU of type F∞F_\infty and scalar elements A,B∈K[U]A,B \in K[U] such that AB=1AB=1 and BA≠1BA \ne1. The group UU is nonsofic and nonsurjunctive.

Proof. The group GG in Theorem 1.1 is finitely presented. The companion embedding theorem [18] therefore gives an injection i:G↪Ui:G \hookrightarrow U into a group of type F∞F_\infty. Extending ii linearly over the same field KK gives a unital algebra injection i∗:K[G]↪K[U]i_*:K[G] \hookrightarrow K[U]: distinct group basis elements remain distinct. Set A=i∗(aout)A=i_*(a_{\mathrm{out}}) and B=i∗(bout)B=i_*(b_{\mathrm{out}}). Then

AB=1,BA−1=i∗(boutaout−1)≠0.AB=1,\qquad BA-1=i_*(b_{\mathrm{out}}a_{\mathrm{out}}-1)\ne0.

If UU were sofic, Elek–Szabó’s theorem [8] would make K[U]K[U] stably finite, contradicting these scalar identities. Proposition 7.2, applied to U,K,A,BU,K,A,B, makes TB:KU→KUT_B:K^U\to K^U an injective nonsurjective cellular automaton over the finite alphabet KK, with left inverse TAT_A in the same right-neighbor convention. Hence UU is nonsurjunctive.

References

  1. [1][AOP02] Pere Ara, Kevin C. O’Meara, and Francesc Perera. Stable finiteness of group rings in arbitrary characteristic. Advances in Mathematics, 170(2):224–238, 2002.
  2. [2][CSC06] Tullio Ceccherini-Silberstein and Michel Coornaert. Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings. Algebra and Discrete Mathematics, pages 22–35, 2006. no. 2.
  3. [3][CSCP25a] Tullio Ceccherini-Silberstein, Michel Coornaert, and Xuan Kien Phung. First-order model theory and Kaplansky’s stable finiteness conjecture for surjunctive groups. Groups, Geometry, and Dynamics, 19:495–503, 2025.
  4. [4][CSCP25b] Tullio Ceccherini-Silberstein, Michel Coornaert, and Xuan Kien Phung. Stable finiteness of monoid algebras and surjunctivity. Theoretical Computer Science, 1042:115228, 2025. Preprint version: arXiv:2405.18287v1.
  5. [5][DLZ25] Irit Dinur, Siqi Liu, and Rachel Yun Zhang. New codes on high dimensional expanders. In 40th Computational Complexity Conference (CCC 2025), volume 339 of Leibniz International Proceedings in Informatics, pages 27:1–27:42. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.arxiv.org/abs/2308.15563
  6. [6][DJ15] Ken Dykema and Kate Juschenko. On stable finiteness of group rings. Algebra and Discrete Mathematics, 19(1):44–47, 2015.
  7. [7][DF14] Nira Dyn and Michael S. Floater. Multivariate polynomial interpolation on lower sets. Journal of Approximation Theory, 177:34–42, 2014.DOI
  8. [8][ES04] Gábor Elek and Endre Szabó. Sofic groups and direct finiteness. Journal of Algebra, 280(2):426–434, 2004.
  9. [9]Paul Erdős and László Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets, Vol. II, volume 10 of Colloquia Mathematica Societatis János Bolyai, pages 609–627. North-Holland, Amsterdam, 1975.
  10. [10]Louis Golowich and Ting-Chun Lin. Quantum LDPC codes with transversal non-Clifford gates via products of algebraic codes. arXiv:2410.14662v1, 2024.arxiv.org/abs/2410.14662
  11. [11]Walter Gottschalk. Some general dynamical notions. In Anatole Beck, editor, Recent Advances in Topological Dynamics, volume 318 of Lecture Notes in Mathematics, pages 120–125. Springer, Berlin, Heidelberg, 1973.DOI
  12. [12]Mikhail Gromov. Endomorphisms of symbolic algebraic varieties. Journal of the European Mathematical Society, 1(2):109–197, 1999.DOI
  13. [13]Graham Higman, B. H. Neumann, and Hanna Neumann. Embedding theorems for groups. Journal of the London Mathematical Society, 24(4):247–254, 1949.DOI
  14. [14]U. V. Linnik. On the least prime in an arithmetic progression. I. The basic theorem. Recueil Mathématique (Nouvelle série), 15(57)(2):139–178, 1944.
  15. [15]M. Susan Montgomery. Left and right inverses in group algebras. Bulletin of the American Mathematical Society, 75(3):539–540, 1969.DOI
  16. [16]Robin A. Moser and Gábor Tardos. A constructive proof of the general Lovász Local Lemma. arXiv:0903.0544v3, 2009.arxiv.org/abs/0903.0544
  17. [17]OpenAI. A Counterexample to the Group-Ring Determinant Conjecture. OpenAI Math Release preprint OAI:A-Counterexample-to-the-Group-Ring-Determinant-Conjecture-September-23-2026, 2026.
  18. [18]OpenAI. A universal group of type F∞. OpenAI Math Release preprint OAI:A-universal-group-of-type-F-infinity-September-23-2026, 2026.
  19. [19]Xuan Kien Phung. A geometric generalization of Kaplansky’s direct finiteness conjecture. Proceedings of the American Mathematical Society, 151(7):2863–2871, 2023.arxiv.org/abs/2111.07930
  20. [20]Benjamin Weiss. Sofic groups and dynamical systems. Sankhyā: The Indian Journal of Statistics, Series A, 62(3):350–359, 2000.
  21. [21]Triantafyllos Xylouris. On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions. Acta Arithmetica, 150(1):65–91, 2011.DOI

Paper details

vlnc:W_8ymvypkh
Version
v1 · latest
Published
License
LicenseRef-OpenAI-public
Usage

views · 17

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

unreleased internal OpenAI model

View statement
Looking for related papers…
Contents