¿Cuántas operaciones binarias son asociativas?

Question

Dejemos que $X$ sea un conjunto finito de $n$ elementos, y considerar una operación binaria $\odot: X \times X \rightarrow X$ . Hay $n^{n^2}$ tales operaciones binarias, como la $n \times n$ las entradas de la tabla pueden cada una puede ser rellenada con uno de los siguientes elementos $n$ elementos de $X$ . Mi pregunta es:

¿Cuántos de los $n^{n^2}$ las operaciones binarias son asociativas, es decir $(x \odot y) \odot z = x \odot (y \odot z)$ ?

A no ser que me equivoque, pues $n=2$ exactamente la mitad de la $2^4=16$ las operaciones binarias son asociativas. Pero para $n=3$ , sólo $113$ de la $3^9=19,683$ las operaciones binarias son asociativas, una cuenta No me fío, porque parece mucho menor de lo que esperaba. (Es difícil contar entre los cuatro mil millones ( $4,294,967,296$ ) operaciones binarias para $n=4$ .)

Me interesaría conocer la tasa de crecimiento asintótica. Seguramente todo esto es bien conocido... Gracias por las indicaciones.

Actualización . Siguiendo el enlace de MSE proporcionado por Darij, llegué (a través del puntero de Gerry Myerson) a la Secuencia OEIS A023814 . El $n=4$ número que no pude calcular fácilmente es $3492$ .

Answer 1

Para preguntas como estas puedes probar alg . Es un programa que toma algunos axiomas (funciona mejor para las ecuaciones) y produce, o simplemente cuenta, modelos no isomórficos de un tamaño determinado. También proporciona un enlace a OEIS para que compruebes la secuencia que tiene.

La teoría de una operación asociativa es así:

Theory associative.
Binary *.
Axiom: (x * y) * z = x * (y * z).

La salida dice:

./alg.native --size 1-4 --count theories/associative.th 
# Theory associative

    Theory associative.
    Binary *.
    Axiom: (x * y) * z = x * (y * z).

    size | count
    -----|------
       1 | 1
       2 | 5
       3 | 24
       4 | 188

Check the numbers [5, 24, 188](http://oeis.org/search?q=5,24,188) on-line at oeis.org

El caso es que se puede experimentar fácilmente (claro que alguien ha contado estas cosas antes que yo).

Answer 2

Los semigrupos forman una parte más grande de lo que se cree. Básicamente se llama a un símbolo 0 y se declara xyz=0 para todos los elementos (haciendo trivial la asociatividad). Todavía tienes una enorme flexibilidad sobre cómo definir los productos restantes. Este es el contenido del artículo que Michael enlaza. De hecho, el 99% de todos los semigrupos hasta el isomorfismo y el antiisomorfismo satisfacen xyz=0. Un artículo reciente de Distler y Mitchell cuenta el número exacto de estos tipos hasta el isomorfismo http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p51 . Creo que también cuentan el número de esas tablas de multiplicar.

Answer 3

Aquí tienes una guía de la intuición. No voy a jurar que los números son exactos, pero apuesto que la verdad numérica no está muy lejos.

Mira la diagonal de la tabla de multiplicación de un groupoide (etiquetado) en $n>3$ elementos. De las n^n posibilidades, sólo una de ellas es idempotente, por lo que con una excepción aa=b ocurrirá para alguna a y alguna b diferente de a. Ahora todo lo que necesitamos para que la asociatividad falle en este caso es que ab y ba sean diferentes, lo que ocurrirá para todas menos n de las n^2 posibilidades. Así que ya estamos viendo que la asociatividad ocurre sólo en una pequeña fracción de todas las tablas (no idempotentes), especialmente porque a menudo hay varios candidatos para a, y sólo se necesita uno.

Incluso para los groupoides idempotentes, uno encuentra a,b,c distintos y necesita considerar sólo d=ab, g=bc, y las formas en que dc y ag pueden no ser iguales. De nuevo en términos aproximados estamos hablando de n^(-2), y esto es sólo fijando a,b, y c por adelantado, y eso para las 1 de n^n tablas que son idempotentes.

Dejaré que otro ajuste los números. Para reforzar la intuición de Joseph, espero que esto sea suficiente.

Gerhard "Ask Me About 2-Deficient Groupoids" Paseman, 2012.10.21

Answer 4

Se conocen límites para el número de semigrupos en $\{1,2,3,\dots,n\}$ . Esta es una referencia que he encontrado (de 1976), sin duda hay mejores límites conocidos por ahora.

El número de semigrupos de orden $n$

Answer 5

Algunas observaciones curiosas de un caso muy pequeño:

Definir el asociatividad de una operación binaria sea el número de triples $a,b,c$ con $(ab)c=a(bc).$ Los recuentos en el caso de $n=3$ los elementos son $52, 12, 96, 276, 504, 468, 628, 936, 966, 1456, 1290, 1266, 1208$$ 1350, 1212, 1296, 1008, 1212, 840, 939, 732, 596, 432, 369, 168, 198, 60, 113$

Así que hay, como se ha señalado, $118$ con asociatividad $27$ pero sólo $60$ con asociatividad $26.$ Además, hay $52$ con asociatividad $0$ pero sólo $12$ con asociatividad $1$ .

Si contamos sólo hasta el isomorfismo/antiisomorfismo (permutar $1,2,3$ y/o tomar la transposición de la tabla que da la operación) entonces los recuentos son.

$5, 1, 8, 23, 42, 39, 53, 79, 81, 130, 108, 113, 103$$ 121, 101, 121, 84, 112, 70, 89, 61, 56, 36, 40, 14, 21, 5, 18$