we-solve (beta)

Math-1963 · mathematics · Dynamical systems

Surjunctive groups

Status Partially solved · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $G$ be a countable discrete group. For every finite nonempty alphabet $A$, give $A^G$ its product topology and the left shift action \[ (g\cdot x)(h)=x(g^{-1}h). \] A cellular automaton on $A^G$ is a continuous equivariant map $F:A^G\to A^G$. Equivalently, there is a finite memory set $D\subset G$ and a rule $\varphi:A^D\to A$ with $(Fx)(h)=\varphi((x(hd))_{d\in D})$. The group is called surjunctive if for every finite $A$ and every such $F$, \[ F\text{ injective}\quad\Longrightarrow\quad F\text{ surjective}. \]

Characterize the countable groups with this property. In particular, determine whether all countable groups are surjunctive, or whether there is a group, finite alphabet, and local rule which give an injective non-onto map of the full shift.

The map need not preserve any algebraic structure on the alphabet. Injectivity and surjectivity concern all configurations, not only finitely supported or periodic ones. A countable group need not be finitely generated or come with a finite presentation, so the classification is a group-theoretic one and is not restricted to algorithmically specified groups. The same group must satisfy the implication uniformly for every finite alphabet and every memory set; checking one selected automaton does not establish surjunctivity.

Short English statement

Which countable groups force every injective finite-state cellular automaton to be onto?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1963-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-1963

Theorem 1.1 and its finite-field convolution transfer supply a countable nonsurjunctive group and settle the universal subquestion, but do not characterize all countable surjunctive groups. This entry records partial support; complete coverage of the question is not established by this catalogue.

Surjunctive groups

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 provide the following support within the scopes described below.

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

Go to contribution →