diff 1da610b..13459b4 kaplansky_direct_finite_char2_v2.txt
diff --git a/kaplansky_direct_finite_char2_v2.txt b/kaplansky_direct_finite_char2_v2.txt
index e69de29..d120aac 100644
--- a/kaplansky_direct_finite_char2_v2.txt
+++ b/kaplansky_direct_finite_char2_v2.txt
@@ -0,0 +1,1452 @@
+================================================================================
+ A COUNTEREXAMPLE TO KAPLANSKY'S DIRECT-FINITENESS CONJECTURE
+ IN CHARACTERISTIC TWO
+ A plain-English companion version, written for curious high school readers
+================================================================================
+
+PURPOSE OF THIS DOCUMENT
+------------------------
+The original paper (kaplansky_direct_finite_char2_original.txt, about
+108 KB) is a research paper in contemporary group theory and
+non-commutative algebra. It disproves a conjecture Kaplansky posed in
+1970, and derives consequences that had been open in symbolic dynamics
+and group theory. The audience of that paper is other group theorists
+and ring theorists.
+
+This companion version is written for a different audience: a reader
+who knows high-school algebra and a bit of linear algebra, and is
+willing to think through a construction step by step, but who has not
+seen modern algebra. It is meant to be read alongside the original.
+Where the original proves a technical lemma, this version tries to say
+WHAT the lemma says in plain words, WHY it is true, and WHY the whole
+construction needs it.
+
+The document has these parts:
+
+ PURPOSE OF THIS DOCUMENT (this section)
+ PART I -- what the conjecture says, why it is interesting, and
+ the basic objects (groups, fields, group rings).
+ PART II -- the exact statement of the main theorem and its two
+ consequences (nonsofic and non-surjunctive).
+ PART III -- the shape of the proof, as ten small steps, no details.
+ PART IV -- a glossary of every specialized word the paper uses.
+ PART V -- the original abstract and the conventions of the paper.
+ PART VI -- small concrete calculations a curious reader can do
+ with a pen, a paper, and a bit of linear algebra.
+ PART VII -- why this matters: connections to soficity,
+ surjunctivity, and cellular automata.
+ PART VIII -- the lemma index of the original paper.
+ PART IX -- exact statements of every result, verbatim from the
+ original, lightly re-typeset for ASCII.
+
+"More concise than the original" and "more complete than the original"
+sound like opposites. They are not. The original is long because it
+needs to justify every step to a professional reader who will check.
+This companion is short because it only needs to explain the shape of
+the argument to a reader who is not going to referee it. Nothing from
+the original's mathematical content is dropped. Some things are
+compressed; some things that the original takes for granted are
+spelled out.
+
+PART I. WHAT THIS PAPER IS ABOUT
+================================================================================
+
+1. THE QUESTION IN ONE SENTENCE
+--------------------------------
+If two square matrices A, B over a field satisfy A B = I, must
+B A = I? Yes, by elementary linear algebra. The same question for
+infinite-dimensional linear maps has a subtle answer. Kaplansky's
+direct-finiteness conjecture was that the same ought to be true for
+a group ring: if a b = 1 in K[G], must b a = 1? The answer turns
+out to be NO in characteristic two.
+
+2. PREREQUISITES: GROUPS
+------------------------
+A group is a set G together with an operation G x G -> G, written
+(g, h) -> g h, satisfying:
+
+ - associativity: (g h) k = g (h k);
+ - identity: there is 1 in G with 1 g = g 1 = g;
+ - inverses: for every g there is g^-1 in G with
+ g g^-1 = g^-1 g = 1.
+
+Examples.
+ - The integers under addition, (Z, +).
+ - The nonzero reals under multiplication.
+ - The symmetric group S_n: all permutations of {1, . . . , n}
+ under composition. S_3 has six elements and is nonabelian.
+ - Z/nZ, the integers modulo n, under +.
+ - A group generated by symbols subject to a set of equations. For
+ example
+
+ G = <x, y | x^2 = y^3 = (x y)^5 = 1>
+
+ means: the group generated by x and y, with exactly the relations
+ shown. If G is defined by finitely many generators and finitely
+ many relations, we call G FINITELY PRESENTED. Many natural
+ groups are finitely presented; many others are not.
+
+A subgroup is a subset closed under the operation and inverse. The
+order of an element g is the smallest positive n with g^n = 1, if
+one exists, and infinite otherwise. "Odd-order torsion" means: G
+contains an element of finite order n but n is odd.
+
+3. PREREQUISITES: FIELDS, CHARACTERISTIC p, FINITE FIELDS
+---------------------------------------------------------
+A field K is a set with + and x making it behave like Q, R, or C.
+Characteristic p means: 1 + 1 + ... + 1 (p terms) = 0 in K, and p
+is the smallest such positive integer. Examples:
+
+ - Q, R, C: characteristic 0.
+ - F_p = Z/pZ: characteristic p.
+ - F_{p^r}: finite field with p^r elements, also characteritic p.
+ - Specifically F_2 = {0, 1}: characteristic two, and 1 + 1 = 0.
+
+In this paper the field K has characteristic two, so 2 = 0 as a
+scalar. That small fact -- "the integer 2 is zero, but the integer
+3 is not zero" -- is used throughout the construction. Whenever
+the paper says "because the characteristic is two", this is why.
+
+4. PREREQUISITES: GROUP RINGS (GROUP ALGEBRAS)
+----------------------------------------------
+Let K be a field and G a group. K[G] is the set of formal finite
+sums
+
+ a = sum_{g in G} c_g g,
+ where c_g in K and c_g = 0 for all but finitely many g.
+
+Two such sums add coefficient by coefficient. They multiply by
+multiplying the group elements and collecting coefficients:
+
+ (sum_{g in G} c_g g) (sum_{h in G} d_h h)
+ = sum_{g, h in G} (c_g d_h) (g h).
+
+The result is again a finite formal sum: both factors were finite,
+so the product is a sum of finitely many nonzero terms. The identity
+of K[G] is the group identity 1_G with coefficient 1.
+
+K[G] is called the group ring, or group algebra, of G over K. It is
+a ring. It is non-commutative whenever G is non-abelian.
+
+Example. Take G = Z/3Z = {1, z, z^2} with z^3 = 1 and K = F_2.
+Then K[G] has 8 elements: all sums c_0 1 + c_1 z + c_2 z^2 with
+each c_i in {0, 1}. Product:
+
+ (1 + z) (1 + z) = 1 + 2 z + z^2 = 1 + z^2 (since 2 = 0).
+
+Fine print on "finite support". K[G] is NOT the set of all functions
+G -> K. It is the set of all such functions that are nonzero at only
+finitely many points. This is essential: finite support is what
+makes the product well-defined without infinite sums.
+
+5. WHAT "DIRECTLY FINITE" MEANS
+-------------------------------
+A unital ring R is DIRECTLY FINITE if the implication
+
+ a b = 1 in R implies b a = 1 in R
+
+holds for all a, b in R. (Some authors say "Dedekind finite".)
+
+For finite-dimensional linear maps, direct finiteness is a fact of
+linear algebra. Over a finite-dimensional vector space, if A B = I
+then A is surjective (as B is a right inverse), so A is injective
+(dimension argument), so A is an isomorphism, so B A = I. The whole
+point of Kaplansky's conjecture is that a general group algebra
+K[G] is NOT of finite dimension: each element has finite SUPPORT,
+but the group itself is infinite.
+
+A ring R is STABLY FINITE if every finite square matrix ring
+Mat_n(R) is directly finite. In finite dimension these coincide. In
+infinite dimensions they can fail in different ways, and that
+difference will matter below.
+
+6. KAPLANSKY'S DIRECT-FINITENESS CONJECTURE
+-------------------------------------------
+Conjecture (Kaplansky 1970; paraphrased). For every field K and
+every group G, K[G] is directly finite.
+
+Kaplansky posed this in a paper about infinite groups and group
+algebras. "Directly finite" and "stably finite" are his terms. Even
+a one-sided scalar inverse in a general ring is not automatic; the
+conjecture was that group rings always behave like finite square
+matrices.
+
+7. WHAT THIS PAPER PROVES
+-------------------------
+The main theorem says Kaplansky's conjecture is FALSE. Specifically:
+
+ There is a finite field K of characteristic two and a
+ finitely presented group G containing an element of odd prime
+ order, plus finite sums a_out, b_out in K[G], such that
+
+ a_out b_out = 1 but b_out a_out != 1.
+
+Two remarks.
+ (a) The group G is not a small familiar group (finite, free,
+ abelian, etc.). It is engineered.
+ (b) F_2 = {0, 1} by itself is not the counterexample field. The
+ field is a finite extension of F_2 large enough to contain a
+ primitive l-th root of unity for an odd prime l. The
+ extension is finite, so K is still finite.
+
+So the paper says: Kaplansky was right in characteristic zero,
+probably right in many other characteristics, but wrong in
+characteristic two.
+
+8. WHAT THIS MEANS FOR SOFIC GROUPS
+-----------------------------------
+The paper also shows that the group G it constructs is NONSOFIC.
+"Sofic" is a notion of "approximable by finite groups"; here is the
+shape of it. For a nonempty finite set Omega, let Perm(Omega) be
+the group of permutations of Omega, and for two permutations
+f, h of Omega let
+
+ d(f, h) = (number of omega in Omega with f(omega) != h(omega))
+ / |Omega|.
+
+A group G is SOFIC if, for every finite subset E of G and every
+eps > 0, there are a finite nonempty set Omega and a map
+sigma : G -> Perm(Omega) such that
+
+ - d(sigma(1), id) <= eps;
+ - d(sigma(g h), sigma(g) sigma(h)) <= eps for all g, h in E;
+ - d(sigma(g), id) > 1 - eps for every g in E with g != 1.
+
+The intuition: sigma is a "finite shadow" of multiplication in G.
+Every finite group is sofic (take the regular representation). Free
+groups are sofic. Solvable groups are sofic. All soficity comes from
+finite approximants of multiplication, up to an error that shrinks
+under refinement of Omega. Whether every group is sofic was open for
+over two decades.
+
+The paper's group G is FINITELY PRESENTED and NONSOFIC. Before the
+paper existed, some nonsofic groups had been exhibited, but none
+were known to be finitely presented. So this is a new qualitative
+type of counterexample.
+
+9. WHAT THIS MEANS FOR CELLULAR AUTOMATA (SURJUNCTIVITY)
+--------------------------------------------------------
+For a set G and a finite alphabet A, a "configuration" is any
+function x : G -> A. (Think of x as writing a letter of A at each
+element of G.) For a finite subset M of G and a function
+phi : A^M -> A, define a map tau on configurations by
+
+ tau(x)(g) = phi( (x(g u))_{u in M} ).
+
+So tau(x)(g) depends only on a FINITE set of "nearby" values of x
+around g. Such tau is called a CELLULAR AUTOMATON. If tau is
+injective as a map on configurations, is tau also surjective? For
+finite-dimensional vector spaces, injective implies surjective. For
+infinite configuration spaces this fails dramatically; for example,
+"shift one letter to the right" is injective but not surjective on
+A^Z.
+
+A group G is SURJUNCTIVE if for every finite nonempty alphabet A,
+every injective cellular automaton on configurations over G is also
+surjective. Gottschalk's conjecture (1973) is that every group is
+surjunctive.
+
+This paper proves the constructed G is NOT surjunctive: the pair
+(a_out, b_out) in K[G] gives a cellular automaton with alphabet K
+that is injective but not surjective. Because G is finitely
+presented, G is an unusually concrete group; the negative answer to
+Gottschalk's conjecture is correspondingly concrete.
+
+10. WHY CHARACTERISTIC TWO AND WHY ODD TORSION
+----------------------------------------------
+Two numeric facts power the construction.
+
+ (a) Odd torsion gives an idempotent average. If G contains an
+ element z of odd prime order l, and K contains a primitive
+ l-th root of unity zeta, then
+
+ e = (1/l) (z^0 + zeta^-1 z^1 + zeta^-2 z^2 + ... + zeta^-(l-1) z^(l-1))
+
+ is a well-defined element of K[G]. Direct computation gives
+ e^2 = e and e z = zeta e. So e is an idempotent that "twists"
+ by zeta when conjugated by z. The 1/l makes sense only when
+ l is invertible in K, so l must be prime to char K. Since
+ char K = 2 and l is odd, 1/l exists.
+
+ (b) Orthogonal character idempotents. In F_l^2, define
+
+ Q_alpha = (1/l^2) sum_{u in F_l^2} zeta^(alpha(u)) u
+
+ for each linear form alpha : F_l^2 -> F_l. One checks:
+ Q_alpha Q_beta = 0 if alpha != beta;
+ Q_alpha^2 = Q_alpha.
+ These give orthogonal "slots" in the group algebra, and the
+ slots are the building blocks of matrix packing.
+
+ (c) The integer 2 is zero, but the integer 3 is not. In the
+ geometric part the paper builds a family of "lines" through
+ a finite vector space, with each point on exactly D = l + 1
+ lines. Here l is odd and D = l + 1 is even. Since char K = 2,
+ the scalar D = 0 in K. That vanishing makes a pair of seeming
+ contradictions coincide: the line-sum pairing vanishes
+ on each line AND on all points at once (in characteristic
+ two you cannot recover the total from D times it).
+
+So the two hypotheses pull in different directions:
+ - characteristic two is what makes the line-sums vanish;
+ - odd prime order is what makes the averages of l-cycles and the
+ primitive l-th roots exist and 1/l invertible in K.
+
+That is the "why" for the two hypotheses.
+
+11. WHY FINITE PRESENTATION MATTERS
+-----------------------------------
+Kaplansky's conjecture is about EVERY group. A single G suffices to
+refute it, so at a glance any G would do. Finite presentation is
+strengthening: it makes the group an explicit, computable object
+rather than a theoretical existence. This is why the paper spends
+Sections 02-criterion and 05-prescription on getting the group
+finitely presented, and on turning "there is a counterexample" into
+"here is a computation that finishes".
+
+12. HOW THE REST OF THIS DOCUMENT IS ORGANIZED
+----------------------------------------------
+PART II states the main theorem and its corollaries in cleanest
+form. PART III sketches the proof as ten steps without proving any
+of them. PART IV is a glossary. PART V quotes the original abstract
+and the conventions. PART VI has hands-on calculations for a
+determined reader. PART VII says why this is interesting. PARTS
+VIII and IX are references: an index of every result, and the exact
+statement of every result.
+
+PART II. EXACT STATEMENTS OF THE MAIN RESULTS
+================================================================================
+
+The original proves exactly six headline results, plus many technical
+lemmas. Below are the six, restated cleanly. Throughout: K is a
+finite field of characteristic two, l is an odd prime, zeta is a
+primitive l-th root of unity in K (or in a finite extension of K),
+and kappa stands for l^2.
+
+Theorem 1.1 (Main result). There exist a finite field K of
+characteristic two, a finitely presented group G containing an
+element of odd prime order, and finite sums a_out, b_out in K[G]
+such that
+
+ a_out b_out = 1 and b_out a_out != 1.
+
+The field, group, and finite sums are specified by a terminating
+prescription involving finite sets and finite-field arithmetic.
+
+Remark. The theorem uses "characteristic two", not "K = F_2". The
+field K is a finite extension of F_2 that contains a primitive l-th
+root of unity for an odd prime l. There is nothing special about the
+specific field; it is chosen to make the construction work.
+
+Theorem 2.1 (Incidence criterion). Let l be an odd prime, and let K
+be a finite field of characteristic two containing a primitive l-th
+root of unity zeta. Put kappa = l^2. Let V be a finite set of
+cardinality t, and let F be a finite family of nonempty subsets of V.
+Assume:
+
+ (a) every v in V belongs to exactly l + 1 members of F, and
+ (b) the bipartite incidence graph of (V, F) has girth at least 12.
+
+Suppose an integer m and column vectors x_v in K^m, v in V, satisfy
+
+ (c) 0 < m < t <= m * kappa,
+
+ (d) sum_{v in V} x_v x_v^T = -I_m, and
+ (e) sum_{v in f} x_v x_v^T = 0 for every f in F.
+
+Then there are a finitely presented group G containing an element of
+order l and finite sums a_out, b_out in K[G] such that
+
+ a_out b_out = 1 and b_out a_out != 1.
+
+The elements a_out, b_out are given by explicit formulas (Section
+5 below in this document; Section 02-criterion in the original).
+
+What each hypothesis does:
+ (a) exact incidence gives the "subgroup average" identity;
+ (b) large girth stops nonobvious relations from collapsing the
+ local subgroups K_v = F_l^2 in the glued group;
+ (c) the upper bound t <= m kappa leaves room to pack t
+ coordinates into m slots, the lower bound m < t is what
+ detects the reverse-product defect;
+ (d) + (e) are algebraic identities that build a rectangular
+ matrix identity over the group ring of the glued group.
+
+Proposition 3.3 (The pairing of holes). Let q >= 4 be a power of
+two, let Q be a field of order q, fix any enumeration of Q, and let
+n >= 1. Put d_0 = (q - 2) / 2. Let S be the "index simplex"
+
+ S = S_{d_0}
+ = { (a_{i_1}, ..., a_{i_n}) : i_1 + ... + i_n <= d_0 } subset A = Q^n,
+
+where a_0, a_1, ..., a_{q-1} is the chosen enumeration of Q. Let
+N_pt = q^n. Let l be an odd prime, D = l + 1. Suppose O is a subset
+of S and F is a family of full affine Q-lines contained in
+V = A \ O, with
+
+ (i) 2 N_pt / D^2 <= |O| <= 7 N_pt / D^2;
+ (ii) every point of V lies on D members of F;
+ (iii) the incidence graph of V and F has girth at least 12.
+
+If K is a finite extension of Q containing a primitive l-th root of
+unity zeta, then, with m = |O| and t = |V|, there are columns
+x_v in K^m for v in V such that
+
+ 0 < m < t <= m * l^2,
+ sum_{v in V} x_v x_v^T = -I_m,
+ sum_{v in f} x_v x_v^T = 0 for every f in F.
+
+So: from a small set O of "holes" inside the finite affine space A,
+and a family of full lines F that avoids O and hits every other
+point exactly D times, one produces the vectors required by
+Theorem 2.1. The vectors come from interpolation: the indicator
+polynomials of the holes.
+
+Theorem 4.1 (Regular affine-line hypergraph exists). For all
+sufficiently large h >= 2, for every finite field Q of order q = 2^h
+and every enumeration of Q, there exist:
+
+ - a set O subset S (S as in Proposition 3.3) of "holes", and
+ - a set F of full affine Q-lines, contained in V = A \ O,
+
+such that
+
+ 2 N_pt / D^2 <= |O| <= 7 N_pt / D^2,
+ every point of V lies on exactly D members of F,
+ the bipartite incidence graph of V and F has girth at least 12,
+
+where l is the least prime congruent to -1 modulo q^100, D = l + 1,
+s = floor(log_q D), b = s + 20, n = 10*b, and N_pt = q^n.
+
+Theorem 4.1 is the "existence of the geometric data" that
+Proposition 3.3 assumes. The proof uses random subspaces and a
+Lovasz Local Lemma argument to control short incidence cycles
+(triangles, rectangles, pentagons): the "girth at least 12" is
+achieved by construction, not hypothesis.
+
+Corollary 6.3 (Not surjunctive). For the field K, group G, and
+outputs a_out, b_out of Theorem 1.1, the cellular automaton
+
+ T_{b_out} : K^G -> K^G
+
+is injective and not surjective. Its image is exactly the fixed set
+of T_{b_out a_out} on K^G. In particular, G is not surjunctive.
+
+So the counterexample to Kaplansky's direct finiteness conjecture is
+simultaneously a counterexample to Gottschalk's surjunctivity
+conjecture for finitely presented G.
+
+Corollary 6.4 (Type F_infinity version). For the same finite field
+K, there are a group U of type F_infinity and scalar elements
+A, B in K[U] such that
+
+ A B = 1 and B A != 1.
+
+The group U is nonsofic and non-surjunctive.
+
+"Type F_infinity" means: U admits a classifying CW complex with
+finitely many cells in every dimension. It is a homotopical
+finiteness condition, stronger than finite presentation. The
+corollary comes from a separate embedding theorem in a companion
+paper ("A universal group of type F_infinity"), applied to the
+finitely presented group G from Theorem 1.1.
+
+
+PART III. THE SHAPE OF THE PROOF (NO DETAILS)
+================================================================================
+
+Here is the whole proof in ten short steps. Each step is indexed
+lemma-by-lemma in PART VIII of this companion, and is proved in full
+in the original.
+
+Step 1. Choose the geometric data. Pick h >= 2, q = 2^h, and l the
+least prime congruent to -1 modulo q^100. Let Q be the field with q
+elements, K a finite extension of Q containing a primitive l-th root
+of unity zeta, and A = Q^n for n = 10b with b = s + 20 and
+s = floor(log_q D) where D = l + 1. Theorem 4.1 supplies a set
+O subset S (S = index simplex) of "holes" and a family F of
+full affine Q-lines in V = A \ O such that every point of V lies
+on exact D lines of F, and the incidence graph has girth >= 12.
+
+Step 2. Produce the vectors x_v. Proposition 3.3 uses interpolation
+to build indicator polynomials f_o for each hole o, and sets
+x_v = (f_o(v))_{o in O} in K^m (with m = |O|). The two identities
+sum_v x_v x_v^T = -I_m and sum_{v in f} x_v x_v^T = 0 follow from
+a line-sum argument: a degree-(q-2) polynomial sums to zero over
+a full affine Q-line, because in characteristic two the nonconstant
+power sums vanish by a "cyclic shift" trick. The contributions
+from the removed holes are the identity I_m, and their complement
+in A is -I_m (the minus sign costs nothing in char 2, but the
+identity (d) can be written either way).
+
+Step 3. Glue the local groups. For each v in V, let K_v^0 = F_l^2
+(an additive group). For each f in F, let L_f^0 = F_l. Since every v
+lies on exactly D = l + 1 lines, put a bijection between the l + 1
+one-dimensional subspaces of K_v^0 and the l + 1 lines meeting v,
+and for each v in f use the induced injection iota_{v f} : L_f^0 -> K_v^0
+on the matching one-dimensional subspace. Then present a group N
+with one generator per nonzero element of L_f^0 (for every line f),
+and one defining relation for each local zero sum of the form
+s_{f_1 c_1}^{eps_1} ... s_{f_k c_k}^{eps_k} lying inside one K_v^0.
+The word "girth >= 12" is what forbids conflicts between different
+local copies.
+
+Step 4. Show the local groups embed. Lemma 2.2 says: the girth >= 12
+hypothesis forces every theta_v : K_v^0 -> N to be injective. If it
+were not, one nonzero s_{f,c} would be trivial in N; represent that
+triviality by a finite planar graph with black vertices labelled
+by points of V and white vertices labelled by lines of F. Minimality
+of the graph, plus the "no two consecutive neighbors with same
+label" contraction argument, forces every black vertex degree >= 3
+and every white vertex degree >= 2 (one possible degree 1). Euler's
+formula for a connected plane graph then contradicts the incidence
+girth bound. This is the crux: it is the ONLY place where girth
+enters.
+
+Step 5. Averaging produces a rectangular identity. In K[N] put
+P_v = (1/kappa) sum_{u in K_v} u for each v. One checks P_v^2 = P_v
+(the sum is over exactly kappa = l^2 group elements, so the
+convolution square reshuffles them without loss). Define
+
+ U in Mat_{m x t}(K[N]), T in Mat_{t x m}(K[N])
+
+by U_{-,v} = -kappa x_v P_v and T_{v,-} = P_v x_v^T. Then a short
+computation (using the incidence data and the two matrix identities
+from Step 2) gives UT = I_m. Also UP = U and PT = T where P is
+diag_v(P_v). This is the "rectangular matrix identity" of
+Section 02-criterion.
+
+Step 6. HNN extend to get character idempotents. To pack t > m
+coordinates into m slots, we need to "twist" copies of the same
+subgroup into different characters. Adjoin a cyclic group <z> of
+order l, take H = N x <z>, and then form a multiple HNN extension
+L with stable letters tau_v, v in V, that conjugate K_v x <z> to
+K_* x <z> times a twist by a linear form alpha_v : K_* -> F_l
+(where K_* is a fixed copy K_{v_*}). The trick is that H embeds in
+L: the HNN base embedding is proved explicitly by counting orbits
+of the regular action of sub-subgroups of order l^3 on H.
+With z central in L, the element
+
+ e = (1/l) sum_{r=0}^{l-1} zeta^{-r} z^r
+
+is a central idempotent satisfying e z = zeta e. Similarly for each
+linear form alpha on K_*,
+
+ Q_alpha = (1/kappa) sum_{u in K_*} zeta^{alpha(u)} u
+
+is an idempotent, with Q_alpha Q_beta = 0 whenever alpha != beta.
+Then tau_v e P_v tau_v^{-1} = e Q_{alpha_v}, so twisting by tau_v
+changes the character of the average P_v.
+
+Step 7. Pack into square matrices. Assign each v in V a slot
+s(v) in {1, ..., m} and a character alpha_v : K_* -> F_l such that
+the pairs (s(v), alpha_v) are all distinct. This is possible because
+t <= m l^2 (there are exactly m l^2 possible pairs) and m < t
+(some slots carry multiple coordinates). Define
+
+ C_{s,v} = tau_v e P_v if s = s(v), else 0,
+ (J_0)_{v,s} = e P_v tau_v^{-1} if s = s(v), else 0.
+
+The orthogonality Q_alpha Q_beta = 0 (alpha != beta) makes the
+cross-terms inside any one slot vanish, so J_0 C = e P. Put
+
+ a_mat = U J_0 + (1 - e) I_m,
+ b_mat = C T + (1 - e) I_m.
+
+Then a_mat b_mat = I_m, because U (eP) T = U T (using UP=U, PT=T)
+and the (1-e) parts do not mix. So far, a failure of STABLE
+finiteness in Mat_m(K[L]).
+
+Step 8. Detect the reverse defect. Set Delta = b_mat a_mat - I_m.
+Direct multiplication gives Delta = C T U J_0 - e I_m and hence
+
+ J_0 Delta C = e (T U - P).
+
+The right-hand side is a matrix over K[H] (H = N x <z>), where a
+scalar specialization epsilon : K[H] -> K is available:
+epsilon(n z^r) = zeta^r for n in N. Then epsilon(e) = 1,
+epsilon(P_v) = 1, epsilon(U) = X and epsilon(T) = X^T where
+X in Mat_{m x t}(K) is the matrix with columns x_v. So
+
+ epsilon(e (T U - P)) = X^T X - I_t,
+
+which is NONZERO because t > m: choose y in ker X nonzero, then
+(X^T X - I_t) y = -y. Since J_0 Delta C is nonzero in Mat_t(K[H]),
+Delta is nonzero in Mat_m(K[L]). So b_mat a_mat != I_m.
+
+Step 9. Matrix pair to scalar pair. Let F = (Z/l)^m semidirect S_m,
+a finite group. Let B = (Z/l)^m be the normal subgroup; define
+p_i = |B|^{-1} sum_{w in B} zeta^{-w_i} w for i = 1, ..., m. These
+are pairwise orthogonal idempotents in K[F] (again the character
+orthogonality argument, now over B). Set sigma_1 = 1 and let
+sigma_i in S_m be the transposition (1 i); then p_{ij} = sigma_i p_1
+sigma_j^{-1} are the m^2 matrix units with p_{ij} p_{kr} = delta_{jk}
+p_{ir}. Now let G = L x F (direct product) and view K[L] and K[F]
+as commuting subalgebras of K[G]. Define
+
+ f_blk = p_11 + p_22 + ... + p_mm,
+ Phi(Z) = sum_{i,j} Z_{ij} p_{ij} for Z in Mat_m(K[L]).
+
+Phi is injective and multiplicative from Mat_m(K[L]) into K[G]. Set
+
+ a_out = 1 - f_blk + Phi(a_mat),
+ b_out = 1 - f_blk + Phi(b_mat).
+
+Then (1 - f_blk) has zero product with anything in the image of Phi,
+so a_out b_out = 1 - f_blk + Phi(I_m) = 1. And
+b_out a_out - 1 = Phi(Delta) != 0 (by injectivity). This is
+Theorem 1.1.
+
+Step 10. Track finite presentation, then take consequences. The
+group N is finitely presented (Section 02a, using finitely many
+generators and relations of length <= 3). Then H = N x Z/l is
+finitely presented; the HNN extension L adds |V| stable letters
+and at most |V| l^3 relators; the finite group F has a finite
+presentation; so G = L x F is finitely presented. Finite
+presentation is the "computable" quality theorem 1.1 claims.
+
+From the scalar pair (a_out, b_out) we get:
+ - a nonsofic group G (contradiction with Elek-Szabo stable
+ finiteness of sofic group algebras plus direct finiteness in
+ matrix size one);
+ - an injective-not-surjective cellular automaton T_{b_out} on
+ configurations K^G (Corollary 6.3);
+ - after embedding G into a group U of type F_infinity (companion
+ paper), a type F_infinity counterexample too (Corollary 6.4).
+
+
+PART IV. GLOSSARY
+================================================================================
+
+Every specialized word in the paper, defined briefly. Words are
+cross-referenced only where a cross-reference is short.
+
+Group. A set G with an associative product, an identity 1, and
+inverses.
+
+Subgroup. A subset closed under product and inverse.
+
+Order of an element. The smallest positive n with g^n = 1, if any;
+else infinite.
+
+Torsion (of a group). The set of elements of finite order. "Group
+with torsion" means: has some non-identity element of finite order.
+
+Odd-order torsion. Torsion where the finite order is odd.
+
+Finitely presented (group). A group defined by finitely many
+generators and finitely many relations.
+
+Field. A commutative ring where every nonzero element has a
+multiplicative inverse.
+
+Characteristic p. The smallest positive integer p with
+1 + 1 + ... + 1 (p times) = 0; 0 if no such p exists.
+
+Finite field. A field with finitely many elements. Every finite
+field has p^r elements for some prime p and some r >= 1; write F_{p^r}.
+
+F_2. The finite field {0, 1} with 1 + 1 = 0. Characteristic two.
+
+Primitive l-th root of unity. An element zeta with zeta^l = 1 and
+zeta^k != 1 for 1 <= k < l. It exists in any field K of characteristic
+not dividing l, provided l | |K^×|. Here l is prime and K is a finite
+extension of F_2 chosen so l | |K^×| = 2^{hr} - 1.
+
+Group ring (group algebra) K[G]. The set of formal finite sums
+sum c_g g with c_g in K, under convolution product.
+
+Support. For a in K[G], the set of g with c_g != 0.
+
+Directly finite (ring). a b = 1 implies b a = 1 for all a, b.
+
+Stably finite (ring). Mat_n(R) is directly finite for every n.
+
+Idempotent. An element e with e^2 = e.
+
+Central idempotent. An idempotent commuting with every element of
+the ring.
+
+Orthogonal idempotents. Idempotents e, f with e f = f e = 0.
+
+Matrix units. A family p_{ij}, 1 <= i, j <= m, with
+p_{ij} p_{kr} = delta_{jk} p_{ir}.
+
+Incidence structure. A pair (V, F) where V is a set and F is a
+family of subsets of V (the "members" or "lines").
+
+Bipartite incidence graph. Vertices V union F; edges (v, f) whenever
+v in f.
+
+Girth. The length of the shortest cycle in a graph; infinite for a
+forest.
+
+Affine line (over F_q). A full translate of a one-dimensional
+F_q-subspace of F_q^n; has exactly q points.
+
+Direction. A one-dimensional subspace of F_q^n (not a single point
+or vector; the set of all nonzero multiples of any nonzero vector
+spans one direction).
+
+Index simplex S_d. The set of tuples (a_{k_1}, ..., a_{k_n}) in F_q^n
+with sum of indices k_1 + ... + k_n <= d, where a_0, ..., a_{q-1} is a
+fixed enumeration of F_q. Used as the "full set" in the interpolation
+argument.
+
+Interpolation on S_d. Every function on S_d is representable by a
+unique polynomial of total degree <= d; dimension count basis:
+numerator matches the number of monomials of total degree <= d.
+
+Full affine line. An affine line that has all q of its F_q-points
+present in the ground set (no holes).
+
+Girth bound requirement. Incidence graph has no 3-, 4-, ..., 11-cycles.
+Written "girth >= 12".
+
+HNN extension. A group construction: starting from a group H, two
+subgroups A, B, and an isomorphism phi : A -> B, produce a group that
+contains H and an extra generator t with t a t^{-1} = phi(a) for a in A.
+"Multiple HNN" allows several such (A_v, B_v, phi_v, t_v) tuples.
+
+HNN base embedding. The theorem (Higman-Neumann-Neumann) that H
+embeds in the HNN extension it produces, provided A and B are
+associated subgroups. Proof is a permutation-action certificate.
+
+Stable letter. In an HNN extension, the "extra generators" t_v that
+do not lie in the base group.
+
+Sofic group. Defined in PART I (section 8). Formally: a group G
+admits, for every finite E subset G and every eps > 0, a finite Omega
+and a map sigma : G -> Perm(Omega) that is an "eps-homomorphism" and
+"eps-faithful" on E.
+
+Surjunctive group. Every injective cellular automaton over every
+finite alphabet is surjective.
+
+Cellular automaton. A map on configurations x : G -> A defined by a
+finite-memory local rule phi : A^M -> A. Formally:
+tau(x)(g) = phi( (x(g u))_{u in M} ).
+
+Type F_infinity. A group U that acts freely, properly, and cellularly
+on a CW complex with finitely many cells in every dimension.
+
+kappa. The symbol kappa in the paper always means l^2 (with l the odd
+prime from Theorem 1.1). It is the number of elements in K_v = F_l^2.
+
+Transpose. For a matrix X, X^T denotes the transpose; there is no
+"conjugate-transpose" (no complex conjugation, and no involution on K).
+
+Rank. The rank of X in Mat_{m x t}(K) is the dimension of its column
+space. "rank <= m" whenever X has only m rows.
+
+Five named theorems of the wider literature.
+
+ Linnik's theorem. For fixed coprime a, m the least prime congruent
+ to a mod m is <= C m^L for absolute constants C, L > 0.
+ Xylouris (2011) gives explicit L = 5.2, or L = 5.18 on GRH.
+
+ Lovasz local lemma (LLL). Given a finite set of "bad events" A_i
+ determined by a finite set of independent random variables, with
+ dependency graph where events are independent of all their
+ non-neighbors; if the sum of event probabilities at every variable
+ is < 1/16 (in the asymmetric form used here), there is positive
+ probability that NO bad event occurs.
+
+ Markov's inequality. If X is a nonnegative random variable,
+ Pr[X >= t] <= E[X] / t.
+
+ Chebyshev's inequality. Pr[|X - E[X]| >= t] <= Var(X) / t^2.
+
+ Vandermonde. The matrix M_{ij} = xi_j^{i-1} (1 <= i, j <= k) for
+ distinct xi_1, ..., xi_k is invertible; determinant
+ prod_{i < j} (xi_j - xi_i). Used to select "10-wise independent"
+ subspaces.
+
+
+PART V. THE ABSTRACT AND THE CONVENTIONS OF THE PAPER
+================================================================================
+
+The abstract of the original paper, quoted verbatim:
+
+ "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 in K[G] with ab = 1 but
+ ba != 1. The group G is nonsofic. The same elements define a
+ cellular automaton on K^G that is injective but not surjective,
+ disproving Gottschalk's surjunctivity conjecture."
+
+The conventions of the paper, quoted verbatim:
+
+ "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 T denotes transpose, without any involution on the
+ coefficient field. All group presentations define abstract
+ discrete groups."
+
+Two things worth emphasizing from those conventions:
+
+ 1. All incidence structures (V, F) are FINITE. This is why every
+ "for every v" or "every f" is a finite for-all, and why the
+ polynomial interpolation arguments are exact rather than
+ limiting.
+
+ 2. There is NO complex conjugation anywhere in the paper. X^T is
+ the plain transpose. Whenever you see X^T X it means real
+ transpose-times-X, not conjugate-transpose; the field K has no
+ notion of conjugate-transpose in general.
+
+PART VI. WHAT A CURIOUS READER CAN ACTUALLY COMPUTE
+================================================================================
+
+The mathematics of the paper is genuinely beyond high school. But
+several SECTIONS OF IT are not: they are finite calculations you can
+do by hand with a pencil, or on a computer in a short script. Below
+are six small exercises, each roughly 30-60 minutes of careful work
+for a determined reader. Together they touch the "nerve" of the
+argument.
+
+Exercise 1 (Direct finiteness of finite matrices). Let A, B be
+N-by-N matrices over any field. Prove A B = I implies B A = I.
+Hint: think of A as a linear map K^N -> K^N. AB = I means A is
+surjective (B is a section). A surjective endomorphism of a
+finite-dimensional vector space is invertible (rank-nullity). So A
+has a two-sided inverse; multiply A B = I on the left by A^-1.
+
+Contrast: over the ring of infinite-by-infinite column-finite
+matrices (each column has finitely many nonzero entries), the shift
+matrix S on the standard basis e_0, e_1, e_2, ... with S e_i =
+e_{i+1} satisfies L S = I but S L != I, where L is the left-shift.
+This is the exact phenomenon the paper constructs at the level of a
+group algebra in characteristic two.
+
+Exercise 2 (Multiply in F_2[S_3]). Take G = S_3 (the six
+permutations of {1, 2, 3}; label them e, (12), (13), (23), (123),
+(132)) and K = F_2. Consider
+
+ a = e + (12), b = e + (123).
+
+Compute ab. Compute ba. Verify ab != ba, i.e. F_2[S_3] itself is
+non-commutative. Then verify ab != 1 and ba != 1 (easy since the
+unit 1 has coefficient 1 on e and 0 elsewhere; check that both a b
+and b a have more than one nonzero coefficient).
+
+Exercise 3 (The idempotent e in F_4[Z/3]). Take l = 3, K = F_4
+(the four-element field, computed as F_2[omega]/(omega^2 + omega +
+1)), and G = Z/3 = {1, z, z^2} with z^3 = 1. Let zeta = omega (a
+primitive cube root of unity inside F_4) and define
+
+ e = (1/3) (1 + omega^{-1} z + omega^{-2} z^2) in F_4[G].
+
+Since 3 != 0 in F_4 (characteristic two), 1/3 makes sense.
+Compute e^2 and verify directly that e^2 = e. Compute e z and
+verify e z = omega e. Compute z e and verify z e = omega e as well
+(so e is central in F_4[Z/3]).
+
+The idempotent e is a "balanced average over the 3-cycle" and the
+whole construction uses it as a projection onto one isotypic
+component.
+
+Exercise 4 (The line-sum lemma by hand). Let F_q be a finite field
+with q = 2^h and q > 2. Verify these two identities:
+
+ (a) sum_{x in F_q} x = 0;
+ (b) sum_{x in F_q} x^k = 0 for 1 <= k < q-1.
+
+Hint for (b): F_q^x (nonzero elements) is a cyclic group of order
+q - 1. Let g generate it. Then sum_{x in F_q} x^k = sum_{j=0}^{q-2} g^{jk}.
+If k is not divisible by q - 1, there is a g^j with (g^j)^k != 1;
+multiplying the whole sum by that g^{jk} permutes the terms, so the
+sum must satisfy s = g^{jk} s, i.e., s (g^{jk} - 1) = 0, i.e., s = 0.
+
+Two values sit right at the boundary:
+
+ (c) sum_{x in F_q} 1 = q = 0 (trivially zero since
+ q = 0 in F_q);
+ (d) sum_{x in F_q} x^{q-1} = 1 (nonzero: for x != 0,
+ x^{q-1} = 1, and x = 0
+ contributes 0; total
+ q - 1 = 1 in char 2).
+
+So the power sums vanish exactly for degrees 1 through q-2. At
+degree q-1 the sum is 1; at degree 0 it is 0. This is why the
+interpolation degree must stay at most d_0 = (q-2)/2: products of
+two interpolants have degree <= q-2 and therefore vanish under line
+sum.
+
+Exercise 5 (Why the exponent l needs to be ODD). Try the "degenerate
+case" l = 2. The group of order 2 is Z/2 = {1, z} with z^2 = 1.
+The "balanced average over the 2-cycle" would be
+
+ e_2 = (1/2) (1 + zeta z),
+
+where zeta is a primitive 2nd root of unity. In characteristic two,
+1/2 = 0 in F_q, so e_2 = 0. So no average exists at all.
+
+Even if you work in any field where 1/2 is a proper fraction, the
+"character slots" of Z/2 fail: Z/2 has exactly TWO characters (trivial
+and the sign character), so there is no family of orthogonal
+idempotents indexed by linear forms. The construction of Theorem 2.1
+needs
+
+ Q_alpha Q_beta = 0 when alpha != beta,
+
+which is only true when there are at least l > 2 characters, i.e.
+l > 2 odd. With l = 2 you get just one nontrivial character, hence
+no orthogonality slots.
+
+So the exponent l being odd is essential: it is what makes the
+idempotent average well-defined (1/l) AND gives enough characters
+to pack coordinates orthogonally. Exercise 3 shows l = 3 in F_4;
+try the analogous computation with l = 5 in F_16 to see the pattern.
+
+Exercise 6 (Why a toy CA on Z cannot be injective-not-surjective).
+Take G = Z and alphabet A = F_2. Consider a linear CA given by a
+finite sum
+
+ tau(x)(n) = sum_{u} c_u x(n + u),
+
+where c_u in F_2, only finitely many nonzero. That is: tau = T_c in
+the notation of PART VI of the original, i.e., T_c(x)(g) =
+sum_u c_u x(g u). Note right-multiplication: g goes to g u.
+
+(a) Suppose c has at least two nonzero coefficients. Show that tau
+has a nonzero kernel, so tau is NOT injective.
+
+Concrete example: take c = (1 at u=0) + (1 at u=1), i.e.,
+tau(x)(n) = x(n) + x(n+1). Then the "all-ones" configuration
+x(n) = 1 for every n satisfies tau(x)(n) = 1 + 1 = 0. So x is a
+nonzero element of ker(tau): tau is not injective.
+
+Another: tau(x)(n) = x(n) + x(n+2). The "alternating" configuration
+x(n) = n mod 2 satisfies x(n) + x(n+2) = (n mod 2) + (n mod 2) = 0
+in F_2, so again tau has a nonzero kernel.
+
+(b) Suppose c has exactly ONE nonzero coefficient, say c at u = u_0.
+Then tau(x)(n) = x(n + u_0), a pure shift. This is bijective; it is
+both injective and surjective.
+
+So NO linear CA on Z is injective-but-not-surjective. Over Z, the
+phenomenon is impossible. This is a feature of Z, not a defect of
+the definitions.
+
+The deeper reason: for a in F_2[Z] = F_2[x, x^{-1}], the operator
+T_a on F_2^Z is injective iff a is a monomial. Multi-term a always
+has nonzero kernel on all configurations. So the paper HAS to find
+a more exotic group.
+
+Corollary 6.3 does exactly that: it constructs a specific finitely
+presented group G and a specific a in K[G] giving T_a injective but
+not surjective. The exercise shows that no amount of cleverness with
+Z alone can produce Kaplansky's counterexample at the CA level. That
+is why the paper's group is intricate. The point of the group is not
+"it is big" or "it is fancy"; it is "it has the right subgroup
+structure" (specifically, subgroups K_v = F_l^2 and L_f = F_l
+glued according to high-girth incidence) to make the algebraic
+construction of Theorem 2.1 fire.
+
+
+PART VII. WHY THIS MATTERS
+================================================================================
+
+1. It is one of Kaplansky's 1970 conjectures. The direct-finiteness
+conjecture is one of several "Kaplansky conjectures" stated that
+year. The others include:
+
+ - Zero-divisor conjecture. In K[G] with K a field of characteristic
+ zero and G torsion-free, if ab = 0 then a = 0 or b = 0. Still
+ open.
+ - Idempotent conjecture. In K[G] with K a field of characteristic
+ zero, if e^2 = e then e = 0 or e = 1 (that is, K[G] has no
+ "exotic" idempotents). Still open.
+ - Direct finiteness conjecture. The subject of this paper. FALSE
+ in characteristic two (this paper); open in characteristic zero.
+
+Direct finiteness was the mildest of the three: it only required
+studying one-sided inverses of elements, not of arbitrary products
+(which enter zero-divisors) or idempotents. It still took until
+2026 to find a counterexample.
+
+2. What was already known before 2026. In characteristic zero,
+Kaplansky himself observed that C[G] is directly finite, because
+the operator-norm completion of C[G] is finite (it is C[G] sitting in
+the reduced C*-algebra) and the trace of the coefficient of the
+identity element gives a functional that blocks one-sided inverses.
+Montgomery (1969) extended this to every field of characteristic
+zero, using the identity-coefficient trace on the operator-norm
+closure of the regular representation; her argument extends to
+every finite matrix size, so it gives stable finiteness as well.
+
+In positive characteristic this method fails (there is no trace in
+characteristic p). The known positive results fall into two
+families:
+
+ - Ara, OMeara, Perera (2002): K[G] is stably finite for
+ free-by-amenable G, over any division ring K.
+ - Elek-Szabo (2004): K[G] is stably finite for sofic G, over any
+ division ring K.
+
+Both results say: if G belongs to a certain class, then K[G] is
+directly finite regardless of characteristic. The paper breaks this
+by producing a finitely presented group G outside both classes for
+which K[G] FAILS direct finiteness in characteristic two.
+
+3. Consequences for soficity. The nonsoficity of the constructed
+group G follows logically: if G were sofic, Elek-Szabo would make
+K[G] stably finite, hence directly finite, contradicting the
+counterexample. So G is nonsofic.
+
+What makes this a step forward: until 2026, no finitely presented
+nonsofic group was known. Nonsofic groups existed (e.g., as
+"expanders" in a different context), but their finite presentation
+was not established. The paper produces a finitely presented
+nonsofic group explicitly, as a byproduct of a different algebraic
+construction.
+
+4. Consequences for surjunctivity. Every element A in K[G] defines a
+cellular automaton T_A on K^G. If A B = 1 in K[G], then T_A is a
+left inverse of T_B, so T_B is injective. If A B = 1 but B A != 1,
+then T_B has a left inverse but not a right inverse, so T_B is not
+surjective (the image misses the configuration with delta_0-like
+structure at a nonzero coefficient of BA - 1).
+
+So the same a_out, b_out that defeats direct finiteness gives an
+injective-not-surjective cellular automaton. Gottschalk's conjecture
+says every group is surjunctive, and G is a counterexample.
+
+5. Why characteristic two specifically. The paper's characteristic-2
+requirement is not a matter of taste. Two scalar facts drive it:
+
+ - Odd prime order l in G + primitive l-th root of unity in K +
+ 1/l invertible in K requires char K to be coprime to l. With
+ char K = 2 and l odd, this is satisfied.
+ - The line-sum identity sum_v x_v x_v^T = 0 for each line v uses
+ "the sum of a degree-(q-2) polynomial over an affine F_q-line
+ is zero", which is true in characteristic two because the
+ nonconstant power sums vanish. In other characteristics you
+ would get different identities (e.g., for char p, "the sum
+ of x^k over F_q is zero for 1 <= k <= q-2 with k not divisible
+ by q-1"; in char 2 you get the whole range you want because
+ q-1 is odd).
+
+6. Some concrete open questions this result raises.
+
+ - Does the direct finiteness conjecture fail in other positive
+ characteristics?
+ - Does it fail with F_2 itself (not a finite extension) in place
+ of K?
+ - Can the odd-torsion requirement be removed? The construction
+ crucially uses odd torsion; a char-2 counterexample using only
+ 2-torsion is not currently known.
+ - Can the "nonsofic group" be simplified to a nicer presentation
+ with fewer generators and relations?
+
+7. What a high school reader should take away.
+
+ - Infinite-dimensional linear algebra really is different from
+ finite-dimensional linear algebra. A one-sided inverse of a
+ linear endomorphism in infinite dimensions need not be two-
+ sided. This phenomenon is why group algebras matter.
+ - Some simple-seeming questions ("if ab = 1 in K[G], is ba = 1?")
+ can be open for decades, then resolved by combining several
+ areas: combinatorics (hypergraphs), group theory (HNN
+ extensions), commutative algebra (finite fields, interpolation),
+ and probability (Lovasz Local Lemma).
+ - The resolution is a CONSTRUCTION, not an argument by
+ contradiction or by category-theoretic abstraction. You can, in
+ principle, follow it step by step and verify each formula
+ yourself.
+
+PART VIII. THE LEMMA INDEX OF THE ORIGINAL PAPER
+================================================================================
+
+Twenty named results, listed in the order they appear in the
+original's source files. The section reference is to the original
+tex filename; the numbers in the original's compiled PDF depend on
+the input order in paper.tex (01-introduction, 03-pairing,
+02-criterion, 04-hypergraph, 05-prescription, 06-cellular-automata),
+but the labels below are unambiguous.
+
+Section 01-introduction
+ - Theorem (main). Existence of K, G, a_out, b_out with
+ a_out b_out = 1 != b_out a_out.
+
+Section 02-criterion
+ - Theorem (incidence criterion). If (V, F) is a finite incidence
+ structure with every v on exactly l + 1 lines, girth >= 12, and
+ matching vector data x_v, then a finitely presented group G
+ with the desired a_out, b_out exists.
+
+Section 02a-embedding (inside 02-criterion)
+ - Lemma (embedding). Under girth >= 12, every local map
+ theta_v : K_v = F_l^2 -> N is injective (proved by the
+ planar-graph Euler argument).
+
+Section 03-pairing
+ - Lemma (interpolation on an index simplex). Evaluation on
+ S_d = {tuples of total index <= d} is an isomorphism from
+ polynomials of total degree <= d to functions on S_d.
+ - Lemma (line sums). A polynomial of total degree <= q-2 sums
+ to zero over every full affine Q-line and over Q^n.
+ - Proposition (the pairing supplied by holes). Given
+ O subset S and a good line family F, the columns
+ x_v = (f_o(v))_{o in O} satisfy the two matrix identities of
+ Theorem 2.1.
+ - Remark (compatibility). "D = l+1 = 0 in char 2" makes the
+ line sums and the total sum of x_v x_v^T mutually consistent.
+
+Section 04-hypergraph
+ - Theorem (hypergraph). For sufficiently large h, the affine-line
+ hypergraph (O, F) with exact degree D and girth >= 12 exists.
+ - Lemma (direction spaces). There are subspaces W_r of dimension
+ 2 per bundle and E_j of dimension b - 1 per index with various
+ directness properties.
+ - Lemma (compatible holes). A random set O subset S can be found
+ so that no W_r-translate contains two holes, no U_j+W_r coset
+ contains more than 100 holes, and no exceptional rectangle has
+ four witnesses in O.
+ - Lemma (replacement lines). The replacement lines avoid O, are
+ pairwise disjoint within each label R_r, and no exceptional
+ rectangle has all four sides among them.
+ - Lemma (polygons). Any candidate short polygon with a generic
+ step has one of three forms (rectangle G_j-R_r, rectangle
+ G_j-G_j', pentagon with two G_j and two G_j'), and each event
+ uses 2g distinct slab variables.
+ - Lemma (event bounds). The sum of bad event probabilities at any
+ single slab variable is O(q^-7) uniformly.
+ - Lemma (local lemma). The asymmetric Lovasz Local Lemma: if the
+ per-variable sum is at most 1/16, some positive-probability
+ choice avoids all events.
+ - Lemma (slab partition). A three-dimensional affine space with
+ direction P + d has a line partition with lines projecting
+ nontrivially to P; if a designated point o is given, one of
+ the lines is o + d.
+ - Lemma (trade). For each hole o and bundle r, replacing the fan
+ o + d_j (rho(j) = r) by q - 1 replacement lines in o + W_r
+ preserves degree D everywhere else.
+
+Section 05-prescription
+ - No named results. This section is the explicit finite search
+ plus the assembly of all previously proved pieces into a
+ computation, ending with the proof of Theorem 1.1.
+
+Section 06-cellular-automata
+ - Lemma (CA representation). The map A -> T_A from K[G] to
+ K-linear endomorphisms of K^G is a faithful algebra
+ homomorphism.
+ - Proposition (CA transfer). If a b = 1 in K[G], the cellular
+ automaton T_b is injective, its image is the fixed set of
+ T_{ba}, and if ba != 1 it is not surjective.
+ - Corollary (not surjunctive). For the K, G, a_out, b_out of
+ Theorem 1.1, the cellular automaton T_{b_out} is injective
+ but not surjective. So G is not surjunctive.
+ - Corollary (type F_infinity). Composing the injection
+ G -> U (companion paper) gives A B = 1 != B A in K[U], with
+ U of type F_infinity; U is nonsofic and nonsurjunctive.
+
+
+PART IX. EXACT STATEMENTS OF EVERY RESULT (VERBATIM, FROM THE ORIGINAL)
+================================================================================
+
+Verbatim (in ASCII render) statements of every theorem, lemma,
+proposition, corollary, and remark in the original, in the order the
+source files appear. Mathematical notation is rendered plain: sum_{}
+is a sum, ^T is transpose, subset is inclusion, != is not equal. No
+mathematical content is changed.
+
+--------------------------------------------------------------------------------
+Section 01-introduction
+--------------------------------------------------------------------------------
+
+Theorem (main). There exist a finite field K of characteristic two, a
+finitely presented group G containing an element of odd prime order,
+and elements a_out, b_out in K[G] such that
+
+ a_out b_out = 1, b_out a_out != 1.
+
+The field, group, and finite sums are specified by a terminating
+prescription involving finite sets and finite-field arithmetic.
+
+--------------------------------------------------------------------------------
+Section 02-criterion
+--------------------------------------------------------------------------------
+
+Theorem (incidence criterion). Let l be an odd prime, let K be a
+finite field of characteristic two containing a primitive l-th root
+of unity zeta, and put kappa = l^2. Let V be a finite set of
+cardinality t, and let F be a finite family of nonempty subsets of V.
+Assume that every v in V belongs to exactly l + 1 members of F and
+that the bipartite incidence graph of V and F has girth at least 12.
+
+Suppose that an integer m and column vectors x_v in K^m, v in V,
+satisfy
+
+ 0 < m < t <= m kappa, (1) size
+
+and
+
+ sum_{v in V} x_v x_v^T = -I_m, (2) total
+ sum_{v in f} x_v x_v^T = 0, for every f in F. (3) per line
+
+Then there are a finitely presented group G containing an element of
+order l and finite sums a_out, b_out in K[G] such that
+
+ a_out b_out = 1, b_out a_out != 1.
+
+They are given by the constructions and formulas of section 02-criterion.
+
+--------------------------------------------------------------------------------
+Section 02a-embedding (part of 02-criterion)
+--------------------------------------------------------------------------------
+
+Lemma (embedding). Let (V, F) be a finite incidence structure with
+girth at least 12, with associated groups K_v^0 = F_l^2 and
+L_f^0 = F_l, and with glued group N presented by the local zero-sum
+relations of section 02a. Then every canonical homomorphism
+theta_v : K_v^0 -> N is injective.
+
+Equivalently: for every nonzero c in some L_f^0, the generator
+s_{f, c} is not the identity element of N.
+
+--------------------------------------------------------------------------------
+Section 03-pairing
+--------------------------------------------------------------------------------
+
+Lemma (interpolation on an index simplex). Let Q be a field of
+order q, enumerate its elements as a_0, a_1, ..., a_{q-1}, and let
+0 <= d < q. For n >= 1, set
+
+ S_d = { (a_{k_1}, ..., a_{k_n}) : k_i >= 0, k_1 + ... + k_n <= d } subset Q^n.
+
+Evaluation on S_d is an isomorphism from the Q-vector space of
+polynomials of total degree at most d to Q^{S_d}.
+
+Lemma (line sums). Let n >= 1. If P is a polynomial on Q^n of
+total degree at most q - 2, then its sum on every full affine Q-line
+is zero. Its sum on Q^n is also zero.
+
+Proposition (the pairing supplied by holes). Let q >= 4 be a power of
+two, Q a field of order q, fix an enumeration of Q, let n >= 1, and
+put d_0 = (q - 2) / 2, S = S_{d_0} subset A = Q^n, N_pt = q^n. Let l
+be an odd prime and D = l + 1. Suppose that O subset S and that F is
+a family of full affine Q-lines contained in V = A \ O, with
+
+ 2 N_pt / D^2 <= |O| <= 7 N_pt / D^2, (hole size)
+
+Suppose also that every point of V lies on D members of F and that
+the incidence graph has girth at least 12. If K is a finite extension
+of Q containing a primitive l-th root of unity, then, with m = |O|
+and t = |V|, there are columns x_v in K^m, v in V, such that
+
+ 0 < m < t <= m l^2,
+ sum_{v in V} x_v x_v^T = -I_m,
+ sum_{v in f} x_v x_v^T = 0 for every f in F.
+
+Remark (compatibility of line sums with the total). The simultaneous
+identities "sum_v x_v x_v^T = -I_m" and "sum_{v in f} x_v x_v^T = 0
+for all f in F" are compatible with regularity because D = l + 1 is
+zero as a scalar in characteristic two. Summing the per-line identities
+would ordinarily multiply the total point sum by D and therefore
+recover the total; here it multiplies by zero and recovers nothing.
+The two identities are genuinely independent.
+
+
+--------------------------------------------------------------------------------
+Section 04-hypergraph
+--------------------------------------------------------------------------------
+
+The setup in section 04: q = 2^h, l is the least prime congruent to -1
+modulo q^100, D = l + 1, s = floor(log_q D), b = s + 20, n = 10b,
+N_pt = q^n, A = Q^n where Q is a field of order q, S is the index
+simplex S_{d_0} with d_0 = (q - 2) / 2 (all tuples in Q^n of total
+index <= d_0 in the fixed enumeration of Q). Lines always mean full
+affine Q-lines with exactly q points.
+
+Theorem (hypergraph). For all sufficiently large h, for every Q and
+enumeration as above, there are a set O subset S and a set F of
+affine lines contained in V = A \ O such that
+
+ 2 N_pt / D^2 <= |O| <= 7 N_pt / D^2,
+ every point of V lies on exactly D members of F,
+ the bipartite incidence graph of V and F has girth at least 12.
+
+Lemma (direction spaces). There are two-dimensional subspaces
+W_r subset A, one per bundle, and (b - 1)-dimensional subspaces
+E_j subset A, one per index, such that any at most ten distinct
+members of this list have direct sum. Choose a direction e_r in each
+W_r, and assign its other q directions bijectively to the indices in
+that bundle, calling them d_j. Then U_j = d_j (+) E_j has dimension
+b, and
+
+ U_j ∩ U_{j'} = 0 (j != j'),
+ U_j ∩ e_r = 0,
+ U_j ∩ W_r = d_j if r = rho(j),
+ 0 if r != rho(j).
+
+Here rho(j) denotes the bundle containing index j.
+
+Lemma (compatible holes). For all sufficiently large h, there is
+O subset S satisfying the hole-size bound and the following properties:
+
+ (i) Every translate of every W_r contains at most one point of O.
+ (ii) For every j, every coset C of U_j, and every r,
+ |O ∩ (C + W_r)| <= 100.
+ (iii) No exceptional rectangle has four distinct witnesses in O,
+ one for each of its four side lines.
+
+An "exceptional rectangle" has corners x, x+u, x+u+v, x+v with
+0 != u in e_r, 0 != v in e_{r'}, and r != r'; a "witness" for a side
+is a point off that side but in the relevant translate of W_r or W_{r'}.
+
+Lemma (replacement lines). Let T_r = union_{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. Then:
+
+ - the replacement lines avoid O;
+ - they are pairwise disjoint within each label R_r;
+ - no exceptional rectangle has all four of its side lines
+ among these replacement lines.
+
+Lemma (polygons). Every candidate sequence with a generic step has
+one of the following forms:
+
+ (i) A rectangle alternating G_j, R_r, with opposite vectors
+ paired.
+ (ii) A rectangle alternating distinct G_j, G_{j'}, with opposite
+ vectors paired.
+ (iii) A pentagon containing two G_j steps, two G_{j'} steps, and
+ one R_r step, with rho(j) = rho(j') = r.
+
+If g is the number of distinct generic labels, the corresponding bad
+event uses 2g distinct random variables and has probability p_*^{2g}
+where p_* = (q^2 - 1)/(q^{b-1} - 1). In case (iii), the exceptional
+vector and one vector of each generic label determine the other two
+vectors once their order is fixed.
+
+Lemma (event bounds). Let mu be the largest, over all variables
+P_{j,C}, of the sum of probabilities of bad events using that
+variable. Then mu = O(q^{-7}), uniformly in the variable; and every
+bad event uses at most four distinct variables.
+
+Lemma (local lemma). Let a finite collection of events be determined
+by independent random variables, 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/16, there is positive
+probability that no event occurs.
+
+Lemma (slab partition). Let a three-dimensional affine space have
+direction P (+) d, where dim_Q P = 2 and dim_Q d = 1. If it has no
+designated point, it has a line partition whose directions project
+nontrivially to P. If it has a designated point o, it has a line
+partition containing o + d, with every other line's direction
+projecting nontrivially to P.
+
+Lemma (trade). For every hole o and bundle r, remove the q lines
+o + d_j with rho(j) = r, and insert the q - 1 replacement lines of
+label R_r in o + W_r. After all these operations, the resulting set
+F consists of lines in V, and every point of V has degree D. 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.
+
+
+--------------------------------------------------------------------------------
+Section 05-prescription
+--------------------------------------------------------------------------------
+
+This section of the original has no named theorem, lemma, proposition,
+corollary, or remark. It is the finite search that fixes every choice
+made in the construction (the field K, the enumeration of Q, the holes
+O, the line family F, the slot assignments s(v), the linear forms
+alpha_v), proves that the search terminates by appealing to the
+sufficiently-large-h existence theorem from section 04, and assembles
+the assembly into Theorem 1.1.
+
+The two elements a_out and b_out are displayed explicitly there as
+finite sums:
+
+ a_out = 1 - sum_{i=1}^m p_{ii}
+ + sum_{i,j=1}^m (a_mat)_{ij} * p_{ij},
+ b_out = 1 - sum_{i=1}^m p_{ii}
+ + sum_{i,j=1}^m (b_mat)_{ij} * p_{ij},
+
+where a_mat, b_mat are the m-by-m matrices over K[L] defined in
+section 02-criterion (packing) and p_{ij} are the matrix units of
+section 02-criterion (finite group F = (Z/l)^m semidirect S_m). The
+displayed expressions are finite sums of finite sums of group words
+with coefficients in K.
+
+--------------------------------------------------------------------------------
+Section 06-cellular-automata
+--------------------------------------------------------------------------------
+
+The setup in section 06: K any field (later finite), G any group,
+K[G] the group ring. For c = sum_{u in G} c_u u in K[G], the support
+is supp(c) = {u in G : c_u != 0}. Define for x in K^G the map
+
+ (T_c x)(g) = sum_{u in G} c_u x(g u).
+
+The sum is finite even when x has infinite support, because c has
+finite support.
+
+Lemma (CA representation). For every field K and group G, the
+assignment c |-> T_c is a faithful unital K-algebra homomorphism from
+K[G] to the algebra of K-linear endomorphisms of K^G, with composition
+as multiplication. In particular,
+
+ T_c ∘ T_d = T_{cd}, T_1 = id_{K^G}.
+
+Proposition (CA transfer). Let K be a finite field, G a group, and
+a, b in K[G] satisfy a b = 1. Put M = supp(b) and define
+
+ phi : K^M -> K, phi(p) = sum_{u in M} b_u p(u).
+
+The cellular automaton tau = T_b is injective, and
+
+ im(tau) = { y in K^G : T_{ba} y = y }.
+
+If b a != 1, every h in G with (ba - 1)_h != 0 gives a configuration
+delta_h not in im(tau); hence tau is not surjective.
+
+Corollary (not surjunctive). For the field K, group G, and outputs
+of the main theorem, the cellular automaton
+
+ T_{b_out} : K^G -> K^G
+
+is injective and not surjective. Its image is the fixed set of
+T_{b_out a_out}. In particular, G is not surjunctive.
+
+Corollary (type F_infinity). For the finite characteristic-two field
+K of the main theorem, there are a group U of type F_infinity and
+scalar elements A, B in K[U] such that
+
+ A B = 1, B A != 1.
+
+The group U is nonsofic and nonsurjunctive.
+
+================================================================================
+END OF COMPANION VERSION
+================================================================================
+
+If you have read this far, you have seen:
+
+ - The Kaplansky direct-finiteness conjecture (PART I).
+ - The exact statement of the counterexample and its two
+ consequences, nonsoficity and nonsurjunctivity (PART II).
+ - The ten steps of the proof in outline (PART III).
+ - The vocabulary of the paper, in plain terms (PART IV).
+ - The abstract and conventions of the original (PART V).
+ - Six small exercises you can do by hand (PART VI).
+ - Why this matters in context (PART VII).
+ - An index of every named result (PART VIII).
+ - Every result, verbatim (PART IX).
+
+The precise order in which you might want to read the extras is:
+PART III first, then PART VI (with pencil), then skim PART IV as
+needed, and use PART IX as a reference when you want to look up the
+exact form of a lemma. Good luck; this is genuinely hard mathematics
+and there is no shame in taking several days.
+