History and positive results.

For a finite group \(G\), the algebra \(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 \(\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 (Montgomery 1969). 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 \(\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 (Ara et al. 2002). Elek and Szabó obtained stable finiteness over arbitrary division rings for all sofic groups from finite approximate models and a rank construction (Elek and Szabó 2004, Corollary 4.7). 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 (Dykema and Juschenko 2015, Theorem 2.2). 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_\Omega(f,h)\) for the fraction of points on which two maps \(f,h:\Omega\to\Omega\) differ. In the finite-map formulation of Elek and Szabó (Elek and Szabó 2004, Definition 4.2), a group \(\Gamma\) is sofic if, for every finite \(E\subseteq\Gamma\) and every \(\varepsilon\in(0,1)\), there are a finite nonempty \(\Omega\) and a map \(\sigma:\Gamma\to\Omega^\Omega\) such that \[\begin{aligned} d_\Omega\bigl(\sigma(gh),\sigma(g)\sigma(h)\bigr)&\le\varepsilon && (g,h\in E),\\ d_\Omega\bigl(\sigma(1),\mathrm{id}\bigr)&\le\varepsilon,\\ d_\Omega\bigl(\sigma(g),\mathrm{id}\bigr)&>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ó (Elek and Szabó 2004, Corollary 4.7) applies to the field \(K\) in Theorem 1. If its particular group \(G\) were sofic, then \(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 \(G\) 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 \(A\), a configuration is an arbitrary function \(x:G\to A\). A cellular automaton on \(A^G\) is a map given by a finite set \(M\subset G\) and a local rule \(\phi:A^M\to A\) through \[\tau(x)(g)=\phi\bigl((x(gu))_{u\in M}\bigr).\] The group \(G\) is surjunctive if every injective cellular automaton on \(A^G\) is surjective, for every such \(A\). Gottschalk’s conjecture asserts that every group is surjunctive (Gottschalk 1973). 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 (Gromov 1999, sec. 7.G\('\)); Weiss gave the finite-alphabet sofic-group theorem directly (Weiss 2000, Theorem 3.2). Elek and Szabó explicitly recorded the implication from surjunctivity to direct finiteness over finite fields (Elek and Szabó 2004, sec. 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 (Ceccherini-Silberstein and Coornaert 2006, Theorem 4.2). Phung proved stable finiteness over every field for surjunctive groups, using algebraic cellular automata (Phung 2023, Theorem B). Ceccherini-Silberstein, Coornaert, and Phung later gave a model-theoretic proof and a monoid extension (Ceccherini-Silberstein et al. 2025a; Ceccherini-Silberstein et al. 2025b, Theorem 1.1). These results connect algebraic finiteness to a dynamical property rather than imposing finite dimensionality.

For the finite field in Theorem 1, the short algebra-to-automaton passage can be given directly. The coefficients of \(b_{\mathrm{out}}\) define a local rule, the coefficients of \(a_{\mathrm{out}}\) give a left inverse on all configurations, and a nonzero coefficient of \(b_{\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; it requires no further existence theorem or approximation assumption.

The characteristic-two scalar pair in Theorem 1 is also the input to the companion counterexample to the group-ring Determinant Conjecture (OpenAI 2026a, 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 \(\mathcal F\) be a family of subsets of a finite set \(V\). We require that each point lie in \(\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 \(x_v\in K^m\) satisfying \[\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 6 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 \(\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 \(K\) sends this matrix to \(X^{\mathsf T}X-I_{|V|}\), where \(X\) has columns \(x_v\). Since \(X\) has only \(m<|V|\) rows, \(X^{\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.

To produce the incidence data, we take full affine lines over a finite field \(Q\subset K\) and remove a small set of points. Low-degree interpolation on these holes gives the vectors \(x_v\): the pairings sum to zero on each full line, but removing the holes leaves the nonzero total \(-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 (Xylouris 2011, 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 (Golowich and Lin 2024; Dinur et al. 2025): 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. 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\)-line is a translate of a one-dimensional \(Q\)-subspace. A direction is such a linear subspace, not a chosen nonzero vector. Superscript \(\mathsf T\) denotes transpose, without any involution on the coefficient field. All group presentations define abstract discrete groups.

The glued group

We first realize the incidence data by finite subgroups of one group. For each \(v\in V\), let \(K_v^0\) be a coordinatized copy of the additive group of \(\mathbb F_\ell^2\), and for each \(f\in\mathcal F\), let \(L_f^0\) be a copy of the additive group of \(\mathbb F_\ell\). Since exactly \(\ell+1\) hyperedges contain \(v\), choose injections \[\iota_{vf}:L_f^0\longrightarrow K_v^0\qquad(v\in f)\] whose images are the \(\ell+1\) distinct one-dimensional subspaces of \(K_v^0\). These are homomorphisms of additive groups. In particular, their images partition \(K_v^0\setminus\{0\}\) outside their common zero element.

Introduce a generator \(s_{f,c}\) for each \(f\in\mathcal F\) and each \(0\ne c\in L_f^0\). A signed word \[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\in V\) belongs to every \(f_i\) and \[\sum_{i=1}^k\varepsilon_i\iota_{vf_i}(c_i)=0 \quad\text{in }K_v^0.\] Let \(N\) 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 \(\theta_v:K_v^0\to N\) determined by \[\theta_v(0)=1,\qquad \theta_v\bigl(\iota_{vf}(c)\bigr)=s_{f,c}\quad(c\ne0).\] Indeed, each nonzero element has a unique expression on the left. For \(a,b\in K_v^0\), the word expressing \(\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 \(K_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 \(N\), and \(N\) is finitely presented. We retain the all-word formulation because it makes the planar proof below more transparent.

We henceforth identify \(K_v^0\) with its image \(K_v\le N\), and identify \(L_f^0\) with the subgroup \(L_f\le N\) given by \(c\mapsto s_{f,c}\), with \(0\) mapped to the identity. The latter is injective by choosing any point incident to \(f\) and applying Lemma 7. The shared generators identify this same subgroup inside every \(K_v\) with \(v\in f\). In particular, \(|K_v|=\ell^2\), \(|L_f|=\ell\), and the incident subgroups \(L_f\) partition \(K_v\) outside the identity. No assertion about intersections between other local subgroups is needed.

Subgroup averages and a rectangular identity

We prove Theorem 6 using the group \(N\) and subgroups \(K_v,L_f\le N\) supplied by Lemma 7. We retain the coordinates on \(K_v\) transported from \(K_v^0=\mathbb F_\ell^2\). Fix an ordering of \(V\), and use it for all matrix indices indexed by \(V\). For \(v\in V\) put \[ P_v=\kappa^{-1}\sum_{u\in K_v}u\in K[N]. \tag{6}\] The integer \(\kappa\) is invertible in \(K\), since \(\ell\) is odd. For each \(w\in K_v\) there are exactly \(\kappa\) pairs \((u,u')\in K_v^2\) with \(uu'=w\), so \(P_v^2=P_v\).

At a fixed \(v\), the subgroups \(L_f\) for \(f\ni v\) run through all the one-dimensional subspaces of the additive group \(K_v\). Their nonidentity elements partition \(K_v\setminus\{1\}\). Consequently \[ \sum_{u\in K_v}u =1+\sum_{f\ni v}\left(\sum_{u\in L_f}u-1\right). \tag{7}\] This equality is internal to \(K_v\); no assertion about intersections between different \(K_v\) is needed.

Write \(W_v=x_vx_v^{\mathsf T}\). Define matrices over \(K[N]\) by \[ 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,\quad T_{v,-}=P_vx_v^{\mathsf T}, \tag{8}\] and set \(P=\operatorname{diag}_{v\in V}(P_v)\). Since the entries of each \(x_v\) belong to the coefficient field, they commute with all group-algebra elements. Idempotence gives \(UP=U\) and \(PT=T\). Moreover, \[\begin{align*} 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\mathcal F} \left(\sum_{v\in f}W_v\right) \left(\sum_{u\in L_f}u-1\right) =I_m, \end{align*}\] where we used Equations (7) and (4). We have proved \[ UP=U,\qquad PT=T,\qquad UT=I_m. \tag{9}\]

A group extension implementing character twists

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

Let \(z\) generate a cyclic group of order \(\ell\), and put \(H=N\times\langle z\rangle\). Choose \(v_*\in V\) and put \(K_*=K_{v_*}\). For every \(v\in V\) let \(\phi_v:K_v\longrightarrow K_*\) be the isomorphism taking each element to the element with identical \(\mathbb F_\ell^2\) coordinates. There are exactly \(\kappa\) linear forms \(K_*\longrightarrow\mathbb F_\ell\). By Equation (3), we may assign to each \(v\in V\) a slot \(s(v)\in\{1,\ldots,m\}\) and a linear form \(\alpha_v:K_*\longrightarrow\mathbb F_\ell\) so that the pairs \((s(v),\alpha_v)\) are distinct. In particular, the forms assigned within any one slot are distinct.

We use a multiple HNN extension (Higman et al. 1949, Theorem II), verifying the required base-group embedding directly. Adjoin to \(H\) generators \(\tau_v\), \(v\in V\), with relations \[ \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{10}\] Denote the resulting group by \(L\). Exponents in \(\mathbb F_\ell\) are interpreted in \(\mathbb Z/\ell\). For each \(v\), the specified map \[\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 \(wz^r\) to \(\phi_v^{-1}(w)z^{r-\alpha_v(w)}\).

We verify directly that \(H\) embeds in \(L\). Let \(H\) act on itself by left multiplication. Restricted to either the domain or the image of \(\psi_v\), this is a disjoint union of regular actions of a subgroup of order \(\ell^3\). These two collections of orbits have the same cardinality. Indeed, if \(H\) is finite, both have \(|H|/\ell^3\) orbits; if \(H\) is infinite, both have countably infinitely many, since \(H\) is countable and the subgroups are finite. Pair these orbits and choose representatives \(h_i,k_i\) so that they are respectively \((K_v\times\langle z\rangle)h_i\) and \((K_*\times\langle z\rangle)k_i\). The bijection \[F_v(ah_i)=\psi_v(a)k_i \qquad(a\in K_v\times\langle z\rangle)\] of the set \(H\) conjugates left multiplication by \(a\) to left multiplication by \(\psi_v(a)\). Assign \(F_v\) to \(\tau_v\) for each \(v\). These assignments, together with the left regular action of \(H\), satisfy all the relations defining \(L\): no defining relation couples two distinct stable letters, so overlapping associated subgroups impose no additional compatibility condition on the independently chosen \(F_v\). They therefore give a permutation representation of \(L\) whose restriction to \(H\) is faithful. This proves the required embedding. In particular, \(K[H]\) embeds in \(K[L]\).

Taking \(u=1\) in Equation (10) shows that every \(\tau_v\) centralizes \(z\). Since \(z\) is already central in \(H\), it is central in \(L\). Define \[ e=\ell^{-1}\sum_{r=0}^{\ell-1}\zeta^{-r}z^r\in K[L]. \tag{11}\] This is a nonzero central idempotent and satisfies \(ez=\zeta e\). For completeness, in the convolution square each coefficient of \(z^a\) is \(\ell^{-2}\ell\zeta^{-a}\), which proves \(e^2=e\); reindexing the sum proves \(ez=\zeta e\). The identity coefficient is \(\ell^{-1}\ne0\) because \(\langle z\rangle\) remains embedded.

For a linear form \(\alpha:K_*\longrightarrow\mathbb F_\ell\), put \[ Q_\alpha=\kappa^{-1}\sum_{u\in K_*}\zeta^{\alpha(u)}u. \tag{12}\] Using additive notation for the coordinates of \(K_*\), the coefficient of \(w\) in \(Q_\alpha Q_\beta\) is \[\kappa^{-2}\zeta^{\beta(w)} \sum_{u\in K_*}\zeta^{\alpha(u)-\beta(u)}.\] If \(\alpha=\beta\), the inner sum is \(\kappa\). Otherwise choose \(u_0\) with \(\zeta^{\alpha(u_0)-\beta(u_0)}\ne1\). Translating the summation variable by \(u_0\) multiplies the sum by this scalar while leaving it unchanged, so the sum is zero. Thus \[ Q_\alpha Q_\beta= \begin{cases} Q_\alpha,&\alpha=\beta,\\ 0,&\alpha\ne\beta. \end{cases} \tag{13}\] The conjugation relations and \(ez^r=\zeta^re\) now give \[ \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}. \tag{14}\]

Packing into square matrices

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

Define \(C\in\operatorname{Mat}_{m\times t}(K[L])\) and \(J_0\in\operatorname{Mat}_{t\times m}(K[L])\) by \[ C_{s,v}= \begin{cases} \tau_veP_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} \tag{15}\] We claim that \[ J_0C=eP. \tag{16}\] The diagonal entry indexed by \(v\) is \(eP_v\). If \(v\ne w\) have different slots, the corresponding entry is zero. If they have the same slot, Equation (14) rewrites that entry as \[eP_v\tau_v^{-1}\tau_weP_w =\tau_v^{-1}eQ_{\alpha_v}eQ_{\alpha_w}\tau_w=0,\] because \(\alpha_v\ne\alpha_w\). This proves the claim.

Set \[ a_{\mathrm{mat}}=UJ_0+(1-e)I_m, \qquad b_{\mathrm{mat}}=CT+(1-e)I_m. \tag{17}\] Every entry of \(C\) and \(J_0\) contains the central factor \(e\). Consequently the cross terms with \(1-e\) vanish, and Equations (9) and (16) imply \[ a_{\mathrm{mat}}b_{\mathrm{mat}} =U(eP)T+(1-e)I_m =eI_m+(1-e)I_m=I_m. \tag{18}\]

Detecting the reverse defect

Put \(\Delta=b_{\mathrm{mat}}a_{\mathrm{mat}}-I_m\). We detect its nonvanishing by multiplying on the left by \(J_0\) and on the right by \(C\). This brings the calculation back from \(K[L]\) to its embedded subgroup algebra \(K[H]\), where a scalar specialization is available. Direct multiplication gives \(\Delta=CTUJ_0-eI_m\), and hence \[ J_0\Delta C=(eP)TU(eP)-eP=e(TU-P). \tag{19}\] In the last equality the order of multiplication is essential: \((eP)TU(eP)=e(PT)(UP)=eTU\). The right-hand side of Equation (19) already belongs to \(\operatorname{Mat}_t(K[H])\).

There is a \(K\)-algebra homomorphism \[ \varepsilon:K[H]\longrightarrow K, \qquad \varepsilon(nz^r)=\zeta^r\quad(n\in N). \tag{20}\] It is well-defined because \(H=N\times\langle z\rangle\). It sends \(e\) to \(1\) and each \(P_v\) to \(1\). Let \(X\in\operatorname{Mat}_{m\times t}(K)\) be the matrix with columns \(x_v\). Since the characteristic is two and \(\kappa\) is odd, \[\varepsilon(U)=X,\qquad \varepsilon(T)=X^{\mathsf T},\qquad XX^{\mathsf T}=I_m.\] Thus \[ \varepsilon\bigl(e(TU-P)\bigr)=X^{\mathsf T}X-I_t. \tag{21}\] Because \(t>m\), choose a nonzero \(y\in\ker X\). Then \[ \varepsilon\bigl(e(TU-P)\bigr)y=-y\ne0. \tag{22}\] One explicit choice is the first nonzero column of \(I_t-X^{\mathsf T}X\): this matrix is nonzero because \(\operatorname{rank}(X^{\mathsf T}X)\le m<t\), and \(X(I_t-X^{\mathsf T}X)=0\). This choice uses only finite-field arithmetic on the given vectors.

Equation (22) proves that \(e(TU-P)\) is nonzero in \(\operatorname{Mat}_t(K[H])\). The embedding \(K[H]\subseteq K[L]\) and Equation (19) therefore show that \(\Delta\ne0\). The homomorphism \(\varepsilon\) has been applied only to elements of \(K[H]\); no extension of it to \(K[L]\) is used.

From matrices to two group-algebra elements

The square factors give a failure of stable finiteness for \(K[L]\). To obtain scalar factors, we embed \(\operatorname{Mat}_m(K[L])\) in an idempotent corner of \(K[L\times F]\) for a suitable finite group \(F\). 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 \(1\). This is an explicit instance of the finite-factor reduction of Dykema and Juschenko (Dykema and Juschenko 2015, Theorem 2.2).

For the finite matrix block, let \[ B=(\mathbb Z/\ell)^m, \qquad F=B\rtimes S_m, \tag{23}\] where \(S_m\) permutes the coordinates. For \(1\le i\le m\) define \[ p_i=|B|^{-1}\sum_{w\in B}\zeta^{-w_i}w\in K[F]. \tag{24}\] The coordinate characters are distinct. The character-sum calculation used in Equation (13), now on \(B\), shows that the \(p_i\) are pairwise orthogonal idempotents. Each is nonzero, since its identity coefficient is \(|B|^{-1}\). This denominator exists because \(|B|=\ell^m\) is odd. No inverse of \(|S_m|\) is required.

Let \(\sigma_i\in S_m\) exchange coordinates \(1\) and \(i\), taking \(\sigma_1=1\). Then \(\sigma_i p_1\sigma_i^{-1}=p_i\). Put \[ p_{ij}=\sigma_i p_1\sigma_j^{-1}\qquad(1\le i,j\le m). \tag{25}\] These elements are nonzero, being left and right translates of \(p_1\), and they satisfy \(p_{ii}=p_i\) and \(p_i p_{ij}p_j=p_{ij}\). For \(j\ne k\) the latter identity and \(p_jp_k=0\) give \(p_{ij}p_{kr}=0\). For \(j=k\), direct cancellation gives \(p_{ij}p_{jr}=\sigma_i p_1^2\sigma_r^{-1}=p_{ir}\). Thus \[ p_{ij}p_{kr}=\delta_{jk}p_{ir}. \tag{26}\] The matrix units are linearly independent over \(K\): multiplying a linear relation on the left by \(p_i\) and on the right by \(p_j\) isolates its coefficient of the nonzero element \(p_{ij}\).

Take \[ G=L\times F. \tag{27}\] We regard \(K[L]\) and \(K[F]\) as commuting subalgebras of \(K[G]\), and put \[ 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{28}\] Equation (26) proves that \(\Phi\) is multiplicative and that \(\Phi(I_m)=f_{\mathrm{blk}}\). It is also injective. Indeed, the group basis identifies \(K[L\times F]\) with \(K[L]\otimes_K K[F]\). If \(\Phi(Z)=0\), expand each entry as \(Z_{ij}=\sum_{g\in L}c_{ij,g}g\). Comparing the \(L\)-basis coefficient of each \(g\) gives \(\sum_{i,j}c_{ij,g}p_{ij}=0\). The linear independence just proved forces every \(c_{ij,g}\) to be zero.

The required two elements are \[ \boxed{\begin{aligned} a_{\mathrm{out}} &=1-f_{\mathrm{blk}}+ \sum_{i,j=1}^m \bigl((UJ_0)_{ij}+(1-e)\delta_{ij}\bigr)p_{ij},\\ b_{\mathrm{out}} &=1-f_{\mathrm{blk}}+ \sum_{i,j=1}^m \bigl((CT)_{ij}+(1-e)\delta_{ij}\bigr)p_{ij}. \end{aligned}} \tag{29}\] Equivalently, these are \(1-f_{\mathrm{blk}}+\Phi(a_{\mathrm{mat}})\) and \(1-f_{\mathrm{blk}}+\Phi(b_{\mathrm{mat}})\), respectively. The matrix-unit identities imply \[f_{\mathrm{blk}}^2=f_{\mathrm{blk}}, \qquad f_{\mathrm{blk}}\Phi(Z)=\Phi(Z)=\Phi(Z)f_{\mathrm{blk}}.\] Therefore \(1-f_{\mathrm{blk}}\) annihilates every image of \(\Phi\) on both sides. It follows from Equation (18) that \[a_{\mathrm{out}}b_{\mathrm{out}} =1-f_{\mathrm{blk}}+\Phi(I_m)=1,\] whereas \[ b_{\mathrm{out}}a_{\mathrm{out}}-1=\Phi(\Delta)\ne0 \tag{30}\] by injectivity. Only the identity action of \(f_{\mathrm{blk}}\) on the image of \(\Phi\) is needed for these computations.

Finite presentation and the retained odd torsion

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

Let \(N=\langle\mathcal S_N\mid\mathcal R_N\rangle\) be the finite presentation from Section 3, with the generators \(s_{f,c}\) and the local zero-sum relators of length at most three. With \([x,y]=xyx^{-1}y^{-1}\), the direct product with the cyclic group has the finite presentation \[H=\left\langle\mathcal S_N,z\ \middle|\; \mathcal R_N,\ z^\ell,\ [z,s]\ (s\in\mathcal S_N)\right\rangle.\] Every element of \(K_v\) and \(K_*\) in Equation (10) has a representative given by its local generator, or by the empty word for the identity. Using those representatives, that equation adds \(|V|\) stable letters and at most \(|V|\ell^3\) relators to the displayed presentation of \(H\): its indices are \(v\in V\), \(u\in K_v\), and \(r\in\mathbb Z/\ell\). Hence \(L\) 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=(\mathbb Z/\ell)^m\rtimes S_m\) is finite, so its finite multiplication table gives a finite presentation. A presentation of \(G=L\times F\) consists of finite presentations of the two factors on disjoint generator sets, together with the commutators of every generator of \(L\) with every generator of \(F\). This adds only finitely many relators, and therefore \(G\) is finitely presented. Finally, the embeddings already proved give \[K_v\le N\le H\le L\le G.\] Since \(K_v\) is the additive group of \(\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 6.

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 \(F\) and the injective map \(\Phi\).

Direction spaces and the local trade

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

Fix these spaces for the rest of the construction. The eventual preliminary partition indexed by \(j\) will use varying directions in \(U_j\), with \(o+d_j\) its line through a hole \(o\); the spaces \(E_j\) provide the other directions. If these \(q\) axes are present for a bundle \(r\), then inside \(o+W_r\) they can be replaced by the \(q-1\) lines parallel to \(e_r\) other than \(o+e_r\). Each point off \(o+e_r\) loses and gains one incidence, the hole loses \(q\), and the remaining points of \(o+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.

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+v\), where \(0\ne u\in e_r\), \(0\ne v\in e_{r'}\), and \(r\ne r'\). For each of its four side lines, a witness is a point off that line but in the translate of \(W_r\) or \(W_{r'}\) containing it, according to the side’s direction. If that side is produced by a trade, its hole is such a witness.

Fix such an \(O\). Put \[T_r=\bigcup_{o\in O}(o+W_r).\] The replacement lines of label \(R_r\) are all the lines of direction \(e_r\) in each \(o+W_r\), except \(o+e_r\) itself.

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 \(j\) and each coset \(C\) of \(U_j\), choose a uniformly random two-dimensional subspace \(P_{j,C}\subset E_j\). The translates of \(d_j\oplus P_{j,C}\) partition \(C\) into three-dimensional affine slabs. For \(u\in U_j\), write \(u^{(E_j)}\) for its \(E_j\)-component. A fixed nonzero vector of \(E_j\) belongs to \(P_{j,C}\) with probability \[ p_* = \frac{q^2-1}{q^{b-1}-1}\le 2q^{3-b}. \tag{37}\] Indeed, linear automorphisms of \(E_j\) act transitively on its nonzero vectors, and every two-dimensional subspace contains \(q^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 \(C\) of \(U_j\), declare it bad if they occupy the same slab. Their difference has nonzero \(E_j\)-component: otherwise it would lie in \(d_j\subset W_{\rho(j)}\), contrary to Lemma 10(i). This event is exactly the inclusion of that component in \(P_{j,C}\) and has probability \(p_*\).

The other events concern closed labelled sequences of \(k\) nonzero steps, \(k\in\{3,4,5\}\), in \(\mathcal A\). The allowed step types are \[\begin{align*} G_j &: \quad u\in U_j,\quad u^{(E_j)}\ne0;\\ R_r &: \quad u\in e_r\setminus\{0\}, \quad\hbox{both endpoints belong to }T_r. \end{align*}\] We call \(G_j\) steps generic and \(R_r\) steps replacement steps; a replacement step vector will also be called exceptional. An \(R_r\) step need not lie on a replacement line: its endpoint condition only requires membership in \(T_r\), which every actual replacement line satisfies. This deliberately enlarges the list of possible polygons. Require at least one \(G\) 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 \(G_j\) step has \(u^{(E_j)}\in P_{j,C}\), where \(C\) is the \(U_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 \(E_j\)-component. Condition (ii) controls the hole contributions to the event counts for a fixed \(P_{j,C}\). Condition (iii) has already excluded rectangles formed entirely from replacement lines.

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 \(P_{j,C}\); the local lemma will apply once this bound is at most \(1/16\).

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 (Erdős and Lovász 1975); for the product-form condition used below see (Moser and Tardos 2009, Theorem 1.1). No resampling algorithm is needed.

By Lemmas 13 and 14, for all sufficiently large \(h\) we can fix the spaces \(P_{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.

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

The pointwise incidence changes are summarized in Figure 2.

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

Finite search for the incidence data

Order binary coefficient vectors lexicographically, with \(0<1\); for a polynomial of fixed degree use the list of coefficients in increasing degree order. For each integer \(h\ge2\), perform the following finite computations.

1. Put \(q=2^h\), and let \(\ell\) be the least prime congruent to \(-1\) modulo \(q^{100}\). Test successive integers in that class for primality. Linnik’s theorem guarantees that this search terminates. Define \(D=\ell+1\), \(s=\lfloor\log_qD\rfloor\), \(b=s+20\), and \(n=10b\) as in Section 5.

2. Let \(g\) be the lexicographically first monic irreducible polynomial over \(\mathbb F_2\) of degree \(h(\ell-1)\), and put \[ K=\mathbb F_2[Z]/(g(Z)). \tag{40}\] Order \(K\) by the coefficient vectors of its unique representatives of degree less than \(h(\ell-1)\), padded by zeros. Irreducible polynomials of this degree exist, and irreducibility is a finite test.

3. Take the subfield \[Q=\{x\in K:x^q=x\},\] with its induced order. It has \(q\) elements since \(h\) divides \(h(\ell-1)\). Let \(\zeta\) be the first element of \(K\) of multiplicative order \(\ell\). Such an element exists: Fermat’s little theorem gives \(\ell\mid 2^{\ell-1}-1\), so \(\ell\) divides \(|K^\times|=2^{h(\ell-1)}-1\), and \(K^\times\) is cyclic.

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

   1. \(2q^n/D^2\le |O|\le7q^n/D^2\);

   2. every line of \(\mathcal F\) is contained in \(\mathcal A\setminus O\);

   3. every point of \(\mathcal A\setminus O\) lies on exactly \(D\) lines of \(\mathcal F\);

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

Start with \(h=2\). For a fixed \(h\), step (4) tests only finite sets and a finite graph. Stop at the first successful pair; if every pair fails, increase \(h\) by one and repeat. This selects the least successful \(h\) and then the first successful pair in its prescribed order. Theorem 8 guarantees success for every sufficiently large \(h\), uniformly in the enumeration of \(Q\), 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 \(Q\)-vector space; it is not required to embed in \(K\).

Fix these data and write \(m=|O|\), \(t=|V|\), where \(V=\mathcal A\setminus O\). The indicator polynomials \(f_o\) and vectors \(x_v\) are the unique ones from Proposition 4; their coefficients may be computed by finite-field linear algebra. We use the induced orders on \(O\), \(V\), and \(\mathcal F\).

Local groups, the presentation, and the two sums

At each point \(v\), use the standard coordinate copy \(K_v^0=(\mathbb F_\ell^2,+)\), and for each line \(f\) use \(L_f^0=(\mathbb F_\ell,+)\). Order \(\mathbb F_\ell\) by the residues \(0,\ldots,\ell-1\) and \(\mathbb F_\ell^2\) lexicographically. Order its one-dimensional subspaces as subsets. Match them in order to the \(D=\ell+1\) incident lines at \(v\), and define \(\iota_{vf}\) by sending \(1\in L_f^0\) to the first nonzero vector of the assigned direction. These maps specify the group \(N\) in Lemma 7 without any further choices.

Choose \(v_*\) to be the first point of \(V\). The isomorphism \(\phi_v:K_v\to K_{v_*}\) preserves the standard coordinates transported from the embedded copies. Order linear forms on \(\mathbb F_\ell^2\) by their coefficient pairs. Assign the points of \(V\), in order, to the first \(t\) pairs \[(s,\alpha),\qquad 1\le s\le m,\quad \alpha\in(\mathbb F_\ell^2)^*,\] in lexicographic order. Proposition 4 gives \(t\le m\ell^2\), so there are enough pairs. This fixes every slot and every character in the construction of Theorem 6.

For the finite presentation of \(N\), use the local zero-sum relators of length at most three, as justified in Section 3. Section 4 then defines \(H=N\times\langle z\rangle\), the conjugation extension \(L\), the finite group \(F=(\mathbb Z/\ell)^m\rtimes S_m\), and finally \(G=L\times F\); Section 4.6 gives the resulting finite presentation. The regular-permutation action used to prove that \(H\) embeds in \(L\) 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 \(e,P,U,T,C,J_0\), the two square matrices \(a_{\rm mat},b_{\rm mat}\), and the matrix units \(p_{ij}\). The two required finite expressions are \[ \begin{split} a_{\mathrm{out}}&=1-\sum_{i=1}^m p_{ii} +\sum_{i,j=1}^m(a_{\rm mat})_{ij}p_{ij},\\ b_{\mathrm{out}}&=1-\sum_{i=1}^m p_{ii} +\sum_{i,j=1}^m(b_{\rm mat})_{ij}p_{ij}. \end{split} \tag{41}\] Coefficients from \(K[L]\) and matrix units from \(K[F]\) are viewed in the two factors of \(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.

Scope of the construction

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

For comparison, if \(G_0\) is finite, then \(K_0[G_0]\) is finite dimensional over every field \(K_0\), even when the characteristic divides \(|G_0|\). Left multiplication is a faithful representation of this algebra. In finite dimension, \(L_aL_b=I\) implies \(L_bL_a=I\), and hence \(ab=1\) implies \(ba=1\). Thus the group in Theorem 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 \(G\) here comes from the presentation argument in Section 4.6; it does not follow merely from finite generation of the support subgroup.

The group algebra acting on all configurations

For this subsection, let \(K\) be any field and \(G\) any group, with identity \(1_G\). For \(c=\sum_{u\in G}c_u u\in K[G]\), put \(\operatorname{supp}(c)=\{u\in G:c_u\ne0\}\). Multiplication in \(K[G]\) is \[(cd)_w=\sum_{uv=w}c_ud_v.\] Every sum has only finitely many nonzero terms. Define a \(K\)-linear map \(T_c:K^G\to K^G\) by \[ (T_cx)(g)=\sum_{u\in G}c_u x(gu). \tag{42}\] This sum is finite even when \(x\) has infinite support. If \(K\) is finite, it is a cellular automaton with memory \(\operatorname{supp}(c)\).

The local rule and its image

Equation (46) describes the image by the uniform finite local equations \[\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 \(b\) is \(b=\sum_{j=1}^r\lambda_j u_j\), with \(\lambda_j\in K\) and \(u_j\in G\) and with repetitions allowed, take \(M'=\{u_j:1\le j\le r\}\) and \(\phi'(p)=\sum_{j=1}^r\lambda_j p(u_j)\). Repeated group elements automatically combine to give the same operator \(T_b\). Consequently, the finite word expressions of Equation (41) specify the local rule without an algorithm deciding which displayed words represent the same group element.

Characteristic two is used to construct the algebraic witnesses, not in Proposition 18. Finiteness of the field supplies the finite alphabet, and the scalar form of the witnesses makes that alphabet \(K\) itself rather than a vector space over \(K\). 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_\infty\)

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