Este artículo proporciona varios ejemplos de grupos algebraicos para que puedas desarrollar una intuición sobre ellos.

Un grupo es un conjunto con:

• un operador binario cerrado
• el operador binario también es asociativo
• un elemento identidad (o neutro)
• cada elemento tiene un inverso

También discutimos los grupos abelianos. Un grupo abeliano tiene el requisito adicional de que el operador binario sea conmutativo.

Ahora es el momento de discutir los grupos como una estructura matemática.

Un aspecto confuso de usar números enteros bajo la suma como ejemplo de un grupo es que los estudiantes a menudo responden con: “pero ¿no se pueden multiplicar también los enteros?”

Hay que admitir que esto puede ser confuso. Existen otras estructuras algebraicas, como anillos (rings) y cuerpos (fields), que involucran dos operadores binarios. Sin embargo, por ahora, piensa en un grupo como algo que tiene un único operador binario fijo e inmutable, y desde la perspectiva del grupo, cualquier otro posible operador binario simplemente no existe o no es de interés.

Aquí es donde se vuelve aún más confuso. A veces, los operadores binarios son otros operadores binarios disfrazados.

Por ejemplo, al tratar con grupos que solo tienen suma, a veces los autores se refieren casualmente a la multiplicación, aunque el grupo no tenga ese operador binario. En este contexto, la multiplicación es en realidad una forma abreviada de repetir una operación de suma un cierto número de veces.

Ejemplos de grupos

La mejor manera de familiarizarse con un grupo es ver muchos de ellos. Hagamos eso.

1. El grupo trivial

Sea nuestro grupo un conjunto que consiste en el número $\set{0}$ con el operador binario de la suma. Está claro que el operador binario es cerrado y asociativo

y cada elemento tiene una identidad y un inverso.

Este no es un grupo interesante, pero es el más pequeño válido que puedes crear.

Ten en cuenta que un grupo no puede estar vacío porque, por definición, debe contener un elemento identidad.

Como ejercicio para el lector, demuestra que el conjunto $\set{1}$ con el operador binario $\times$ es un grupo.

2. Los números reales no son un grupo bajo la multiplicación

Aunque los reales ($\mathbb{R}$) bajo la multiplicación tienen un elemento identidad (el número $1$) y la operación es cerrada y asociativa, no todos tienen un inverso.

Los números reales son invertibles tomando su inverso multiplicativo $(1 / n)$, pero el cero, aunque es un número real, no se puede invertir porque $1/0$ es indefinido y no es un número real.

Estrictamente hablando, el inverso de $a$ es $b$ tal que $ab = 1$. Aquí estamos diciendo que si $a = 0$, no hay ningún elemento $b$ en el conjunto tal que $ab = 1$.

Sin embargo, los números reales positivos excluyendo el cero sí son un grupo bajo la multiplicación. Cada elemento tiene un inverso ($1/n$), y el elemento identidad es 1.

Ejercicio: Los números enteros (positivos y negativos) no son un grupo bajo la multiplicación. Demuestra cuál de los cuatro requisitos (cerrado, asociativo, existencia de identidad, que todos los elementos tengan un inverso) no se cumple.

3. Las matrices $n \times m$ de números reales son un grupo bajo la suma

Veámoslo en detalle:

La suma de matrices es cerrada y asociativa. Si sumas una matriz $n \times m$ de números reales con otra matriz $n \times m$ de números reales, obtienes una matriz $n \times m$ de números reales.
La matriz identidad es una matriz $n \times m$ compuesta completamente de ceros.
El inverso de una matriz es esa matriz multiplicada por -1.
Espera un momento, no se nos permite multiplicar por -1, ¿verdad?

Un grupo no requiere que el inverso sea “calculable utilizando el operador binario del grupo”, solo que exista. Es decir, calculamos el inverso multiplicando cada elemento por $-1$, aunque la multiplicación por $-1$ no sea una operación del grupo.

Si definimos nuestro operador para matrices $n \times m$ como el producto de Hadamard (multiplicación elemento por elemento), esto no puede ser un grupo por la misma razón discutida anteriormente. Específicamente, el inverso se calcula como el recíproco de cada elemento en la matriz, y si uno de los elementos es cero, entonces no se puede calcular el inverso.

Si definimos nuestro operador como la multiplicación tradicional de matrices sobre matrices cuadradas, esto puede o no ser un grupo dependiendo de la definición del conjunto, como veremos en el ejemplo de la sección 5.

4. El conjunto de puntos 2D en un plano euclidiano bajo la suma elemento por elemento es un grupo

Este es en realidad un caso especial del ejemplo anterior, pero veámoslo desde un ángulo diferente.

Considera el conjunto de todos los puntos $(x, y)$ con valores reales en un plano 2D estándar.

Nuestro operador binario es la suma de puntos, por ejemplo $(1,1) + (2,2) = (3,3)$.

Nuestro elemento identidad es el origen, porque sumar con él dará como resultado la misma ubicación del otro punto.

El inverso de un punto es simplemente la “imagen especular” sobre el origen (con las coordenadas $x$ e $y$ negadas) porque cuando sumas un punto a su inverso, el resultado es el origen.

5. Las matrices $n \times n$ de determinante no nulo bajo la multiplicación son un grupo

A modo de repaso, si una matriz tiene un determinante distinto de cero, entonces es invertible. Cuando una matriz de determinante no nulo se multiplica por otra matriz de determinante no nulo, el producto también tiene un determinante no nulo. De hecho, podemos ser más específicos: si $A$, $B$ y $C$ son matrices cuadradas y $AB = C$, entonces $\det(A) \times \det(B) = \det(C)$.

Revisemos las definiciones:

• La multiplicación de matrices de determinante no nulo es cerrada porque no puedes “salir del grupo”, ya que el producto siempre tendrá un determinante no nulo. La multiplicación de matrices es asociativa.
• El elemento identidad es la matriz identidad (todos ceros, excepto la diagonal principal que son unos).
• El inverso es simplemente la matriz inversa, y las matrices con determinante distinto de cero son invertibles.

6. Las matrices $n \times n$ de determinante cero bajo la multiplicación no son un grupo

Recuerda que una matriz con determinante cero no se puede invertir, por lo que este conjunto no puede tener un inverso. En este caso, no tenemos un elemento identidad porque la matriz identidad tiene determinante uno. Dado que no tenemos elemento identidad, este conjunto y operador binario ni siquiera forman un monoide, es un semigrupo.

7. El conjunto de todos los polinomios de un grado fijo con límite superior es un grupo bajo la suma

Si decimos “todos los polinomios con coeficientes reales de grado 7 como máximo bajo la suma”, este es un grupo válido.

• La suma de polinomios es cerrada y asociativa.
• La identidad es el polinomio $0$ (o $0x^0$ para ser precisos).
• El inverso son los coeficientes multiplicados por $-1$.
• No podemos decir grado “exactamente $7$” porque el elemento identidad tiene grado 0 y no formaría parte del grupo.

Los polinomios de un grado fijo con límite superior bajo la multiplicación no son un grupo, porque generalmente el grado se hace mayor al multiplicar polinomios, por lo tanto, el operador no sería cerrado.

8. La suma módulo un número primo es un grupo

Tomemos un número primo, $7$.

Aquí, la identidad sigue siendo $0$, porque al sumar $0$ obtienes el mismo número.

En esta situación, ¿cuál sería el inverso de $5$?

Sería simplemente $2$, porque $7 - 5 = 2$, o $5 + 2 \mod 7$ es cero (la identidad).

9. La multiplicación módulo un número primo no es un grupo

El cero no tiene un inverso en este ejemplo.

Si omitimos el número $0$, entonces tenemos un grupo. El elemento identidad es 1, y el inverso de un elemento $a$ es su inverso modular $a^{-1}$.

10. Una base fija elevada a potencias enteras bajo la multiplicación es un grupo

Si se multiplican dos potencias enteras de $b$, el resultado es la potencia entera del producto de las bases. Por ejemplo, $2^3 \times 2^4 = 2^{3 + 4} = 2^7$. Esto funciona para bases arbitrarias:

El elemento identidad es $b^0$, que es $1$, y el inverso de $b^x$ es $b^{-x}$.

Grupos finitos

Como sugiere el nombre, un grupo finito tiene un número finito de elementos en él. El conjunto de todos los números enteros bajo la suma no es finito, pero la suma de enteros módulo un número primo es un grupo finito.

En las pruebas de conocimiento cero, solo usamos grupos finitos.

Orden de un grupo

El orden de un grupo es el número de elementos en él.

Grupos cíclicos

Un grupo cíclico es un grupo que tiene un elemento tal que cada elemento del grupo puede ser “generado” aplicando repetidamente el operador binario a ese elemento, o a su inverso.

Ejemplos de grupos cíclicos

Ejemplo 1: El grupo que consiste en 0 bajo la suma es un grupo cíclico

Esto es trivialmente cierto porque $0 + 0 = 0$ genera todos los elementos del grupo.

Ejemplo 2: La suma módulo 7 es un grupo cíclico

Si comenzamos con $1$ y le sumamos $1$ repetidamente, generaremos todos los elementos del grupo. Por ejemplo:

Ejemplo 3: La multiplicación módulo $7$ es un grupo cíclico, si excluimos el cero

Tenemos que tener cuidado al elegir el generador aquí, porque, por ejemplo, el $2$ no generará todo el grupo.

Podemos ver que el $2$ solo puede generar $\set{1,2,4}$. Sin embargo, si elegimos el $3$ como generador, entonces podemos generar todo el grupo.

La razón por la que el $3$ funciona y el $2$ no, es porque el $3$ es una raíz primitiva.

Podemos usar la biblioteca galois para encontrar raíces primitivas:

Copy
from galois import GF
GF7 = GF(7)
print(GF7.primitive_elements)
# [3, 5]

A partir de la salida del código anterior, podemos ver que el $5$ también generará todos los elementos distintos de cero.

Si un grupo es cíclico, entonces es abeliano

Este es un poco más sutil, pero considera lo siguiente:

En un grupo cíclico, cada elemento del grupo puede ser generado como $(g + g + … + g)$. Elijamos arbitrariamente un elemento $r$. Particionemos este conjunto de sumas de la siguiente manera:

Debido a la asociatividad, podemos agregar paréntesis:

Sea $p$ el resultado de sumar $g$ a sí mismo $m$ veces, y sea $q$ el resultado de sumar $g$ a sí mismo $n$ veces. Por lo tanto,

Por la asociatividad, podemos volver a particionar la ecuación original de la siguiente manera (¡nota que $m$ y $n$ cambiaron de lugar!)

Y obtenemos:

Por lo tanto, si el grupo es cíclico, entonces el grupo es abeliano.

Ten en cuenta que lo contrario a esta afirmación no es cierto. Los números reales bajo la suma son un grupo abeliano, pero no son cíclicos.

Los grupos cíclicos no tienen por qué ser aritmética módulo un número primo, pero estos son los únicos grupos cíclicos que utilizaremos en nuestra discusión sobre pruebas de conocimiento cero.

El elemento identidad de un grupo es único

Un grupo no puede tener dos elementos de identidad. No le des muchas vueltas a esto, se deriva por simple contradicción. Digamos que $\square$ es nuestro operador binario y $e$ es nuestro elemento identidad.

Digamos que tenemos un elemento identidad alternativo $e'$. Esto significa lo siguiente:

Si decimos que $e≠e'$, entonces también debe ser cierto que

Pero eso es obviamente una contradicción, por lo tanto, los elementos identidad deben ser únicos.

El uso de grupos en las pruebas de conocimiento cero

Comprender la teoría de grupos para el propósito de las pruebas de conocimiento cero es más bien un ejercicio de vocabulario. Cuando decimos “inverso” o “identidad”, queremos que comprendas inmediatamente lo que significan.

Además, los grupos nos ayudan a razonar sobre objetos matemáticos muy complejos sin necesidad de entender cómo funcionan. Hemos usado ejemplos familiares en este artículo, pero más adelante trataremos con objetos muy poco familiares, como las curvas elípticas sobre extensiones de cuerpos. Aunque no sepas exactamente qué es eso, si te decimos que es un grupo, ya sabes mucho sobre lo que es.

Aprende más con RareSkills

Este artículo es parte de una serie sobre pruebas ZK. Consulta nuestro ZK Book para ver la serie completa.

Publicado originalmente el 1 de agosto de 2023