diff b34550f..f6bf760 kaplansky_direct_finite_char2_v2.txt
diff --git a/kaplansky_direct_finite_char2_v2.txt b/kaplansky_direct_finite_char2_v2.txt
index 5da0b7e..3753f50 100644
--- a/kaplansky_direct_finite_char2_v2.txt
+++ b/kaplansky_direct_finite_char2_v2.txt
@@ -6,264 +6,6 @@
-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 characteristic 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".
-
-
-
PART II. EXACT STATEMENTS OF THE MAIN RESULTS
================================================================================
@@ -402,702 +144,6 @@ 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 minus 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. Indeed UJ_0 C T = U (eP) T = e (U P T) =
-e (U T) = e I_m, using UP=U, PT=T, and UT=I_m from Step 5; the
-(1-e) terms give (1-e)^2 = 1-e and are killed by the e-factors, so
-the total is e I_m + (1-e) I_m = I_m. 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. EXPLICIT COMPUTATIONS
-================================================================================
-
-Several sections of the paper are finite calculations that can be
-done by hand with a pencil, or on a computer in a short script. Below
-are six small exercises. 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. Summary.
-
- - 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)
================================================================================