================================================================================
  A COUNTEREXAMPLE TO KAPLANSKY'S DIRECT-FINITENESS CONJECTURE
  IN CHARACTERISTIC TWO
  
================================================================================



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 (PARTS III
and IX below; Section 02-criterion of 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 minus 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 minus 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 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 minus 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 minus 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.