En matemáticas, un grupo sobreyectivo es un grupo tal que cada autómata celular inyectivo con los elementos del grupo como sus células también es sobreyectivo . Los grupos sobreyectivos fueron introducidos por Gottschalk (1973). Se desconoce si todos los grupos son sobreyectivos.
Un autómata celular consiste en un sistema regular de celdas, cada una de las cuales contiene un símbolo de un alfabeto finito , junto con una regla uniforme llamada función de transición para actualizar todas las celdas simultáneamente en función de los valores de las celdas vecinas. Lo más común es que las celdas se organicen en forma de una línea o una cuadrícula de números enteros de dimensiones superiores , pero también son posibles otras disposiciones de celdas. Lo que se requiere de las celdas es que formen una estructura en la que cada celda "se vea igual que" todas las demás celdas: existe una simetría tanto en la disposición de las celdas como en el conjunto de reglas que lleva cualquier celda a cualquier otra celda. Matemáticamente, esto se puede formalizar mediante la noción de grupo , un conjunto de elementos junto con una operación binaria asociativa e invertible. Los elementos del grupo se pueden utilizar como las celdas de un autómata, con simetrías generadas por la operación de grupo. Por ejemplo, una línea unidimensional de celdas se puede describir de esta manera como el grupo aditivo de los números enteros , y las cuadrículas de números enteros de dimensiones superiores se pueden describir como los grupos abelianos libres .
La colección de todos los estados posibles de un autómata celular sobre un grupo puede describirse como las funciones que asignan cada elemento del grupo a uno de los símbolos del alfabeto. Como conjunto finito, el alfabeto tiene una topología discreta y a la colección de estados se le puede dar la topología de producto (llamada topología prodiscreta porque es el producto de topologías discretas). Para ser la función de transición de un autómata celular, una función de estados a estados debe ser una función continua para esta topología y también debe ser equivariante con la acción del grupo, lo que significa que desplazar las celdas antes de aplicar la función de transición produce el mismo resultado que aplicar la función y luego desplazar las celdas. Para tales funciones, el teorema de Curtis-Hedlund-Lyndon asegura que el valor de la función de transición en cada elemento del grupo depende del estado anterior de solo un conjunto finito de elementos vecinos.
Una función de transición de estado es una función sobreyectiva cuando cada estado tiene un predecesor (no puede haber ningún Jardín del Edén ). Es una función inyectiva cuando no hay dos estados que tengan el mismo sucesor. Un grupo sobrejuntivo es un grupo con la propiedad de que, cuando sus elementos se utilizan como células de autómatas celulares, cada función de transición inyectiva de un autómata celular también es sobreyectiva. De manera equivalente, resumiendo las definiciones anteriores, un grupo es sobreyectivo si, para cada conjunto finito , cada función inyectiva equivariante continua también es sobreyectiva. [1] La implicación de inyectividad a sobreyectividad es una forma del teorema del Jardín del Edén , y los autómatas celulares definidos a partir de funciones de transición inyectivas y sobreyectivas son reversibles .
Los ejemplos de grupos sobrejuntivos incluyen todos los grupos finitos residualmente locales , [2] todos los grupos libres , [2] todos los subgrupos de grupos sobrejuntivos, [3] todos los grupos abelianos, [2] todos los grupos sóficos , [4] y cada grupo sobrejuntivo local. [3]
Cuando introdujo los grupos sobrejuntivos en 1973, Gottschalk observó que no se conocían ejemplos de grupos no sobrejuntivos. En 2014, todavía se desconoce si todos los grupos son sobrejuntivos. [5]
