Gottschalk Surjunctivity Problem

Gottschalk Surjunctivity Problem

OpenAI's claim

The linked manuscripts present the following claims by OpenAI: A finite characteristic-two field and a finitely presented group are claimed to produce a scalar one-sided inverse pair; the resulting shift is injective without being onto and the group is nonsofic; For a particular odd prime $p$, the authors claim a one-sided inverse defect over a field with $p^4$ elements, together with a nonsurjective injective shift; Another construction claims a torsion-free, finitely presented $G$ for which $\mathbb F_2[G]$ contains $a,b$ satisfying $ab=1$ and $ba\ne1$. Together they give a claimed negative answer in the matching scope.

Mathematical statement of the claimed result

Result 1.

Take a finite field $K$ with $\operatorname{char}K=2$. The constructed group $G$ is finitely presented and has an element of odd prime order. Two finite group-ring sums meet \[ a_{\mathrm{out}},b_{\mathrm{out}}\in K[G],\qquad a_{\mathrm{out}}b_{\mathrm{out}}=1,\qquad b_{\mathrm{out}}a_{\mathrm{out}}\ne1. \] Its specification uses terminating finite-set and finite-field computations. Unlike the torsion-free companion, this particular group contains torsion.

Result 2.

Define the integers \[ m=\binom{1200}{600},\qquad p=\min\{h\in\mathbb Z:h>1,\ h\mid(m!)^2+1\}. \] The claimed example has $p$ an odd prime, $|K|=p^4$, and a specified finitely generated group $G$ containing torsion. Its finite sums $a,b\in K[G]$ satisfy \[ ab=1\quad\hbox{and}\quad ba\ne1. \] This is an example in a specified odd characteristic, rather than a theorem for each odd prime.

Result 3.

The construction supplies a torsion-free, finitely presented group $G$, with a finite two-dimensional $K(G,1)$, and elements of its characteristic-two group algebra satisfying \[ a,b,c\in\mathbb F_2[G],\qquad ab=1,\quad ac=0,\quad c\ne0,\quad ba\ne1. \] In particular, $a\ne0$ and $e=ba$ obeys $e^2=e$, $e\notin\{0,1\}$. Thus this same example supplies failures of direct finiteness, absence of zero divisors, and triviality of scalar idempotents. These assertions concern $\mathbb F_2[G]$; the separate integral-unit assertion is not a consequence.

Outline of the argument

Incidence data and polynomial pairings first give a defective inverse pair of matrices. A geometric group-embedding construction preserves the defect, and character packing realizes the matrix algebra inside a larger group algebra; dual convolution gives the cellular-automaton consequence.

The construction uses translation representations of finite groups: a high-degree subspace is killed on one side and a weighted pairing supplies the other annihilation. Finite group identifications and a quadratic field tower package these local relations into the scalar inverse pair; the claim concerns the specified prime rather than all odd characteristics.

An unequal-side parity pattern supplies the one-sided inverse relation in labeled graphs. Weighted counts handle repeated edge traversals, and a separator reduces arbitrarily large planar arrangements to bounded path collections; cone attachment and root separation then preserve the inverse defect while proving torsion-freeness.

Formal verification

For family 197, the documented Lean entries include the scalar inverse defects in the specified characteristics and an operator-invertible determinant counterexample. The characteristic-two search recipe is included, but the nonsofic consequence, the extra spectral-integral conclusion, and the later torsion-free construction are outside the selected statements. The listed Comparator files are GroupRingDeterminant.lean, KaplanskyDirectFiniteness.lean, KaplanskyFinitelyPresented.lean, OddKaplansky.lean. Named declarations include OAI.GroupRingDeterminant.main, OAI.KaplanskyCounterexample.finitelyPresented_counterexample, OAI.OddKaplansky.main_theorem. This site has not executed the Lean code. The scope descriptions do not certify the remaining manuscript arguments.

Status caveat

OpenAI attributes these manuscripts to work by an internal model. Its release cautions that arguments without formalization can contain mistakes. This catalogue has not independently checked the proofs; the labels report the mathematical claims attributed to OpenAI.

Sources

• OpenAI, A Counterexample to Kaplansky's Direct-Finiteness Conjecture in Characteristic Two, 2026-09-23; citation key OAI:A-Counterexample-to-Kaplanskys-Direct-Finiteness-Conjecture-in-Characteristic-Two-September-23-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main.
• OpenAI, A Counterexample to Kaplansky's Direct-Finiteness Conjecture in Odd Characteristic, 2026-09-26; citation key OAI:A-Counterexample-to-Kaplanskys-Direct-Finiteness-Conjecture-in-Odd-Characteristic-September-26-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: op:main.
• OpenAI, A Torsion-Free Group Algebra That Is Not Directly Finite, 2026-10-04; citation key OAI:A-Torsion-Free-Group-Algebra-That-Is-Not-Directly-Finite-October-4-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main.
• Family 197: Lean scope.
• Comparator GroupRingDeterminant.json.
• Comparator GroupRingDeterminant.lean.
• Comparator KaplanskyDirectFiniteness.json.
• Comparator KaplanskyDirectFiniteness.lean.
• Comparator KaplanskyFinitelyPresented.json.
• Comparator KaplanskyFinitelyPresented.lean.
• Comparator OddKaplansky.json.
• Comparator OddKaplansky.lean.
• Family 197: Reasoning summary.
• OpenAI catalogue entry.

Gottschalk Surjunctivity Problem

Definitions and mathematical statement

Let $G$ be any group and $A$ a finite alphabet. Give $A^G$ the product topology with $A$ discrete, and let $G$ act by shifts $(g\cdot x)(h)=x(g^{-1}h)$. A cellular automaton is a continuous shift-equivariant map $F:A^G\to A^G$, equivalently a finite-memory rule: for some finite $D\subset G$ and $\mu:A^D\to A$, \[ F(x)(g)=\mu\left((x(gh))_{h\in D}\right). \] Surjunctivity asserts \[ F\text{ injective}\quad\Longrightarrow\quad F\text{ surjective} \] for every $G,A,F$. The local rule is uniform over all sites. Results about non-uniform automata must therefore be related back to this uniform target rather than changing its definition. Neither finite generation nor countability of $G$ is imposed in the record.

Formulation and concept references: [S1].

Short English statement

On every group, must a finite-alphabet cellular automaton that never merges two configurations also reach every configuration?

Research attempt

Scope, source check, and attack plan.

This attempt by GPT-6 Astra Ultra was prepared on 27 September 2026. The problem number is the top-problem catalogue rank, not an Erdős problem number. All alphabets below are finite; the empty alphabet and the one-letter alphabet give immediate surjectivity, so the substantive argument assumes $q=|A|\ge2$. The group need not initially be countable.

Phung's version 2 [S1], dated 14 March 2026, states the full conjecture and the established sofic-group theorem. Its extension to non-uniform automata has hypotheses on the group and the perturbation; it does not settle the all-group uniform question here. The broader sofic result is also identified in [E1]. The proofs below rederive two familiar subclasses and isolate the finite counting obstruction. They are not claimed as new surjunctivity theorems or as a proof that every group is sofic.

There are three concrete routes. Finite quotients can make the pigeonhole principle applicable to periodic configurations. On amenable groups, a forbidden image pattern creates a volume-order deficit that dominates the boundary cost of a local inverse. For a general group, compactness still produces that inverse and a finite forbidden pattern, but neither of the two finite models is automatic. The work below makes this distinction precise and tests whether ordinary cardinality or a finite-window count can bypass it.

Reduction A: only a finitely generated subgroup is involved.

Let $D$ be a finite memory set and set $H=\langle D\rangle$. Denote by $F_H$ the automaton with the same rule on $A^H$. The left cosets $gH$ partition $G$, and the value at $gh$ depends only on the values at $ghD\subseteq gH$. After identifying each coset with $H$, the map $F$ is therefore the product of copies of $F_H$: \begin{equation}\label{wsref-0-61-34-39-31-3a-63-6f-73-65-74-73} A^G\cong\prod_{gH\in G/H}A^H, \qquad F\cong\prod_{gH\in G/H}F_H. \end{equation} If $F_H$ is not injective, use two colliding configurations on one coset and equal configurations on the others to disprove injectivity of $F$. If $F_H$ is injective, equality of outputs implies equality on every coset. Surjectivity also passes in both directions: restrict a preimage to one coset for one direction, and choose a preimage on each coset for the other. These are ordinary set-theoretic products; the latter choice is allowed in the usual foundations. Consequently a counterexample on any group would already give one on a finitely generated, hence countable, group. This reduction removes a cardinality issue, not the group-theoretic difficulty.

Lemma 491.1: injectivity has a finite detection window.

If $F$ is injective, there is a finite $K\subset G$, which we may enlarge to contain the identity $e$, such that \begin{equation}\label{wsref-0-61-34-39-31-3a-64-65-74-65-63-74-69-6f-6e} F(x)|_K=F(y)|_K\quad\Longrightarrow\quad x(e)=y(e). \end{equation} Proof. In the compact space $A^G\times A^G$, let \[ C=\{(x,y):x(e)\ne y(e)\},\qquad C_K=C\cap\{(x,y):F(x)|_K=F(y)|_K\}. \] These sets are closed. If every finite $C_K$ were nonempty, they would have the finite intersection property, since intersections correspond to unions of the finite sets $K$. Compactness would give a pair in their full intersection, with $F(x)=F(y)$ and $x(e)\ne y(e)$, contradicting injectivity. Thus one $C_K$ is empty. Equivariance then determines $x(g)$ from $F(x)|_{gK}$ for every $g$.$\square$

Put $Y=F(A^G)$ and write $N_Y(W)$ for the number of its patterns on a finite set $W$. For every finite $E\subset G$, choose one full input extending each of its $q^{|E|}$ patterns. Distinct input patterns give distinct output patterns on $EK$, by (a491:detection). Hence \begin{equation}\label{wsref-0-61-34-39-31-3a-6c-6f-77-65-72} N_Y(EK)\ge q^{|E|}, \end{equation} Here $N_Y(EK)$ counts only patterns occurring in the actual image. The inverse rule is only asserted on patterns occurring in $Y$. Assigning arbitrary values to other patterns extends it to a local rule, but does not prove that those other patterns have preimages under $F$.

Lemma 491.2: failure of surjectivity has a finite witness.

The set $Y$ is compact, hence closed in the Hausdorff product $A^G$. If $z\notin Y$, a basic open cylinder about $z$ misses $Y$. Thus there are a finite nonempty $D_0\subset G$ and a pattern $p\in A^{D_0}$ such that no $y\in Y$ has $y|_{D_0}=p$. Enlarge $D_0$ to contain $e$ if necessary, extending $p$ arbitrarily. Equivariance forbids the translated pattern at every $gD_0$. Write $d=|D_0|$ and $b=|D_0D_0^{-1}|$.

Suppose a finite window $W$ contains $r$ pairwise disjoint translates of $D_0$. On each such block, at most $q^d-1$ patterns are allowed. Even if every remaining site is free, the number of patterns is at most \begin{equation}\label{wsref-0-61-34-39-31-3a-75-70-70-65-72} N_Y(W)\le q^{|W|-rd}(q^d-1)^r =q^{|W|}(1-q^{-d})^r. \end{equation} Constraints involving two blocks can only reduce this count. No independence of the actual image coordinates has been assumed.

Attempt B: complete the counting argument under the Følner condition.

For the next proposition assume that for every finite $B\subset G$ and every $\epsilon>0$ there exists a nonempty finite $E\subset G$ with \[ |Es\mathbin{\triangle}E|\le\epsilon|E| \qquad(s\in B). \] This is the right Følner condition. It holds for amenable groups; it is explicitly the extra hypothesis being used.

Proposition 491.3. Under this condition every injective finite-alphabet cellular automaton is surjective.

Proof. Suppose otherwise, and obtain $K,D_0,p$ as above. Define the set of available centres \[ T=\{g\in E:gD_0\subset E\} =E\cap\bigcap_{d_0\in D_0}Ed_0^{-1}. \] Choose $E$ satisfying the Følner condition for all elements of $K\cup D_0^{-1}$. A union bound gives \[ |EK|\le(1+|K|\epsilon)|E|, \qquad |T|\ge(1-d\epsilon)|E|. \] Greedily select disjoint sets $gD_0$ with centres $g\in T$. If $gD_0$ meets $hD_0$, then $h\in gD_0D_0^{-1}$, so each selected block excludes at most $b$ possible centres. We obtain at least $r\ge |T|/b$ disjoint blocks. Because $e\in K$, all of them lie inside $E\subset EK$. Combining (a491:lower) and (a491:upper) gives \[ 0\le (|EK|-|E|)\log q+r\log(1-q^{-d}). \] Let $c=-\log(1-q^{-d})>0$. The right-hand side is at most \begin{equation}\label{wsref-0-61-34-39-31-3a-63-6f-6e-74-72-61-64-69-63-74-69-6f-6e} |E|\left(|K|\epsilon\log q -\frac{(1-d\epsilon)c}{b}\right). \end{equation} Choose $\epsilon$ so small that $d\epsilon<1/2$ and $|K|\epsilon\log q<c/(2b)$. Then this expression is strictly negative, a contradiction.$\square$

For example, on $\mathbb Z$ with $K\subset[-R,R]$ and $D_0\subset[-L,L]$, choose $E=[-N,N]\cap\mathbb Z$. The extra output sites number at most $2R$, whereas at least a constant multiple of $N$ disjoint forbidden blocks fit in $E$ for fixed $D_0$. Taking logarithms makes the contradiction explicit. The radius $R$ may depend on the automaton; the limiting window $N$ is chosen only after that radius and the forbidden pattern have been fixed.

Attempt C: a different complete argument using finite quotients.

A group is residually finite if every nonidentity element survives in some finite quotient. For a finite set $E\subset G$, intersect the kernels of finitely many finite quotients separating the elements $h^{-1}g$ with $g,h\in E$, $g\ne h$. The resulting finite-index normal subgroup $N$ makes the quotient map $G\to G/N$ injective on $E$.

Let $P_N$ be the configurations constant on cosets of $N$. It has $q^{[G:N]}$ elements. It is invariant under $F$: if $x$ is fixed by all shifts in $N$, then $F(x)$ is also fixed by them, by equivariance. Thus an injective $F$ restricts to an injective selfmap of a finite set $P_N$ and is surjective on that set. Every finite input pattern can be extended to some $P_N$ because the selected quotient is injective on its support. The union of all $P_N$ is therefore dense in $A^G$. As $Y$ is closed and contains every $P_N$, it is all of $A^G$.

This proves the residually finite case with no growth assumption. In particular it illustrates why the Følner condition is a sufficient mechanism rather than a necessary condition for this conjecture. To apply this proof to an arbitrary group one would need suitable finite models with enough compatible local patterns; residual finiteness cannot be inserted without proof.

Disproof searches: what the tempting shortcuts actually show.

Infinite-set cardinality is insufficient. On $\{0,1\}^{\mathbb N}$ the map \[ T(x)_0=0,\qquad T(x)_{n+1}=x_n \] is continuous, injective, and not surjective. It is not a counterexample: the index set is not a group and there is a distinguished boundary site. Nor can one use a site injection of $G$ into a proper subset while retaining equivariance. If a map $\phi:G\to G$ commutes with every left translation, then $\phi(g)=g\phi(e)$; it is right multiplication by a group element and is bijective.

A nonamenable group defeats the boundary argument, but that observation does not construct a counterexample. Equations (a491:lower) and (a491:upper) only contradict one another when the expansion $|EK|-|E|$ is sufficiently small relative to the packed pattern deficit. Large expansion leaves numerical room for both bounds. Proving that a particular counting proof stops is not proving that an injective nonsurjective automaton exists.

Finite periodic experiments have the converse limitation. For each fixed finite quotient, an injective selfmap is automatically surjective, irrespective of any conjecture. A proposed infinite automaton that passes finitely many such tests need not be injective on all configurations. The density proof above uses every finite support and residual finiteness, not an extrapolation from a numerical sample.

Finite verification and exact remaining gap.

The companion exact script enumerates all 16 binary rules with memory $\{0,1\}$ on cyclic groups of sizes 1 through 8. It checks image sizes, injectivity, and surjectivity directly; the counts of bijective rules are recorded with the output, rather than being used to certify any infinite case. It also checks the translated-block packing inequality on cyclic groups by exhaustive finite set comparisons. These tests target the local conventions and the finite counting steps. Compactness and the Følner limit are justified by the proofs, not by the enumeration.

UNRESOLVED. The strongest proved result here is surjunctivity for groups with the displayed Følner property and, separately, for residually finite groups, together with the reduction to finitely generated groups. These belong to known theory. For a general finitely generated group, the first missing step is a replacement for the negligible-boundary or dense-periodic-pattern mechanism that rules out the simultaneous existence of the finite inverse window $K$ and forbidden image pattern $p$. Three specific continuations are to build approximately equivariant finite models and control their bad sites, to prove an alternative pattern-counting invariant resistant to expansion, or to construct an explicit rule whose global injectivity and missed pattern can both be certified. None is completed here; the established sofic theorem is not extended by this work.

Sources

• S1 Xuan Kien Phung, On Gottschalk's surjunctivity conjecture for non-uniform cellular automata, arXiv:2503.23435v2, 2026. https://arxiv.org/html/2503.23435v2. Formulation source.
• E1 Tullio Ceccherini-Silberstein, Michel Coornaert, and Hanfeng Li, Expansive actions with specification of sofic groups, strong topological Markov property, and surjunctivity, Journal of Functional Analysis $2024$, author manuscript, introduction and consequences for full shifts. https://www.math.buffalo.edu/~hfli/surjunctive-final.pdf. Established sofic-group context; the narrower elementary arguments in this attempt are proved separately. Consulted 27 September 2026.