Oddtown y Eventown Parte II

Una variación doblemente par sobre el tema ’’Oddtown’’

Piste noire Le 4 décembre 2013  - Ecrit par  Valentin Ovsienko
Le 5 juin 2022  - Traduit par  Julio E. De Villegas, Jimena Royo-Letelier
Article original : Oddtown et Eventown Partie II Voir les commentaires
Lire l'article en  

Esta parte II es una continuación del artículo Ciudades pares e impares (Oddtown y Eventown) I.

Recordemos que el teorema ’’Oddtown’’ afirma que no puede haber más de $n$ clubes en un pueblo con $n$ habitantes si :

  • cada club tiene un número impar de miembros,
  • dos clubes cualesquiera tienen un número par de miembros en común.

La segunda parte de nuestra obra es un juego donde ’’par’’ e ’’impar’’ se mezclan. Encontramos todos los personajes de la primera parte : los clubes impares, pares y doblemente pares, así como los códigos binarios. La lectura de la última sección supone conocimientos de álgebra lineal.

Esta es la continuación de la historia del Oddtown. Los habitantes se rebelan contra las reglas restrictivas de la alcaldía y han reelegido a un alcalde que les prometió suprimir la mitad de las restricciones para crear los clubes. De ahora en adelante, los clubes pueden tener un número cualquiera de miembros, par o impar. ¡Todos los habitantes estaban ahora seguros que nada podría detener el crecimiento exponencial de clubes ! Pero el nuevo alcalde encontró otra solución...

Clubes con un número arbitrario de miembros

Nuestra pregunta es la siguiente. Supongamos que permitimos toda clase de clubes, pares o impares. ¿Qué debería cambiar en la regla (2.) para mantener una estimación del número máximo de clubes que sea lineal en $n$ ?

Aquí, ’’lineal en $n$’’ significa que se busca restricciones para que el número máximo posible de clubes sea acotado por un múltiplo de $n$ (por ejemplo, $\leq 3 n$ o $\leq 10000 n$).

La pregunta de arriba parecer ser muy ingenua si se toma en cuenta la vasta literatura sobre el tema llamado ’’combinatoria extrema’’ o ’’teoría extrema de conjuntos’’. Sin embargo, el enunciado siguiente parece haber escapado a la atención de los expertos.

Para formularlo, necesitamos la noción de distancia de Hamming. Si $X$ es un club, denotamos $|X|$ el número de sus adherentes (su cardinal). Dados dos clubes $X$ e $Y$, la distancia $d(X,Y)$ está definida como el número de miembros que pertenecen sólo a un club, sea a $X$, sea a $Y$. Dicho de otra forma, la distancia es igual a la cardinalidad de la diferencia simétrica entre $X$ e $Y$ :

\[ \begin{equation} d(X,Y) =|X|+|Y|- 2\,|X\cap{}Y|. \end{equation} \]

Recordemos (ver la Parte I) que se puede codificar cada club por una serie de $0$ y $1$. Para eso, se ordena los habitantes (por ejemplo, por orden alfabético), lo que permite hablar del habitante número $i$ para $i$ entre $1$ y $n$, donde $n$ es el número total de habitantes. Habiendo hecho esto, un club está determinado por una lista de $n$ números sucesivos que valen $0$ o $1$ : el número colocado en posición $i$ vale $1$ si el $i$-ésimo habitante es miembro del club, y $0$ si no. En términos de tales series, la distancia $d(X,Y)$ puede ser obtenida como sigue :

  • se crea la serie $X+Y$ : el valor en la $i$-ésima posición es un $1$ si el habitante número $i$ está en uno sólo de los dos clubes, y vale $0$ si no. De manera equivalente, se toman los valores $0$ o $1$ para $X$ e $Y$ en posición $i$ y se asocia la suma de los dos con las reglas $0+0=0$, $0+1=1=1+0$, $1+1=0$.
  • se calcula el peso de $X+Y$ : por definición, es la suma de los términos de la serie. Corresponde entonces el número de números $1$ que aparece (así, el peso de un club es el número de sus integrantes).

Entonces, la distancia de Hamming $d(X,Y)$ es igual al peso de $X+Y$.

Ejemplo. La distancia entre los clubes

\[ \begin{array}{rcl} X&=&(1\,0\,0\,1\,1\,1\,0)\\ Y&=&(0\,1\,0\,1\,0\,1\,1) \end{array} \]

es $d(X,Y)=4$.

Nuestro enunciado es el siguiente.

Teorema. Sea $F$ una familia de clubes en una ciudad de $n$ habitantes. Si la distancia entre dos clubes nunca es un múltiplo de $4$, entonces el número $|F|$ de clubes en la familia está acotado por :

  • $|F|\leq 2n$ para $n\equiv0,1,2\mod4$ (es decir, si $n$, $n-1$ o $n-2$ es múltiplo de $4$)
  • $|F|\leq 2n+2$ para $n\equiv3\mod4$ (es decir si $n-3$ es múltiplo de $4$).

Esta cota es exacta

Hay que notar que el valor $4$ en la condición ’’la distancia entre dos dos clubes no es un múltiplo de $4$’’ es un valor excepcional. Reemplazando el $4$ por otro número, por ejemplo, por $3$ o $5$, uno se da cuenta de que el número de clubes puede crecer como $n^2$ (en efecto, se podría elegir todos los clubes con dos miembros).

El objetivo de este texto no es dar una prueba del teorema, sino más bien ejemplos de ’’clubbing’’ y convencer al lector que el tema está ligado a numerosas nociones notables, como las Matrices de Hadamard y los códigos binarios doblemente pares [1].

Comentario

La prueba completa de ese teorema puede ser encontrada en [2] ; está basada en el famoso teorema de Hurwitz-Radon. Creemos que la periodicidad modulo $4$ refleja la periodicidad de Bott de las álgebras de Clifford reales (esta periodicidad es de hecho modulo $8$, pero se vuelve dos veces más corta si uno está solamente interesado en la dimensión de las representaciones irreductibles).

Consideraciones elementales

Mostremos que el teorema Oddtown/Eventown implica directamente la cota superior $|F|\leq2n+2$ para todo $n$. Sea $F$ una familia de clubes, y sea $F_0\subset F$ la subfamilia de clubes con número par de miembros. Se comienza por verificar que la distancia $d$ es invariante bajo traslación :

\[ d(X+Z,Y+Z)=d(X,Y). \]

Podemos entonces suponer sin pérdida de generalidad que $F_0$ contiene al club vacío [3]. Cada club no vacío $X\in F_0$ debe contener $4k+2$ miembros para un cierto $k$, ya que su distancia al club vacío no es múltiplo de $4$. La fórmula (1) implica que dos clubes no vacíos, diferentes y pares, deben tener una intersección impar. Concluimos por el teorema-gemelo de Oddtown que $|F_0|\leq{}n+1$. Para la sub-familia $F_1$ de los clubes impares la cota $|F_1|\leq{}n+1$ puede ser obtenida por argumentos análogos. Esas dos estimaciones proveen $|F|\leq{}2n+2$.

Además, en el caso donde $n$ es divisible por $4$, el límite puede ser fácilmente mejorado en $|F|\leq2n$. En efecto, consideremos el elemento de peso máximo

\[ \omega=(1,1,\ldots,1), \]

es decir, el club que contiene todos los habitantes. Entonces, para cada $X$ e $Y$ se tiene

  • $4$ divide $d(X,Y)$ si y solamente si $4$ divide $d(X+\omega,Y)$,

ya que $n$ es un múltiplo de $4$. Todo club $X$ de la familia $F$ puede ser reemplazado por $X+\omega$. Haciendo este reemplazo si necesario, se puede suponer que $x_n=0$ para todo $X$, y luego aplicar el límite $|F|\leq2n+2$ reemplazando $n$ por $n-1$.

En conclusión, cuando $n$ o $n-3$ es divisible por $4$, la cota del teorema de arriba puede ser obtenida por métodos elementales, pero los dos otros casos restantes (cuando $n-1$ o $n-2$ es múltiplo de $4$) resisten tales consideraciones. Parece que el teorema no pudiera ser probado por métodos simples de álgebra linear. Por lo menos, el autor no logró encontrar una prueba elemental y se pregunta si el lector ¡es más inventivo !

Clubbing extremo

Ahora, nuestro objetivo principal es proponer construcciones explícitas de familias de clubes $F$ que alcancen la cota superior del teorema.

Cuando $4$ divide $n-3$.— En este caso, el número máximo de clubes es $2n+2$. Se elige los clubes siguientes :

  • El club vacío ;
  • El club lleno $\omega$ ;
  • $n$ clubes con $1$ miembros ;
  • $n$ clubes con $n-1$ miembros.

La distancia entre dos clubes no es nunca un múltiplo de $4$. [4]

Cuando $4$ divide $n-1$.— La construcción de arriba puede ser aplicada, pero el club vacío y el club lleno ya no están autorizados. La familia de los clubes con un miembro y de los clubes con $n-1$ miembros alcanza el límite superior $2n$.

Cuando $4$ divide $n-2$.— El límite superior es de nuevo $ 2n $ [5]. Para construir una familia que satisfaga las restricciones del teorema, podemos elegir el club vacío, $ n $ clubes con un miembro y $ n-1 $ clubes con dos miembros que compartan un miembro común.

Cuando $n$ es múltiplo de $4$.— Este caso fue discutido más arriba. La manera más simple de llegar al límite $2n$ es excluir a un habitante de todos los clubes y luego utilizar nuestra primera construcción.

Matrices de Hadamard

Tal como está formulado, nuestro teorema ’’no siente’’ la auténtica periodicidad (de Bott) modulo $8$ que habíamos evocado en el comentario de más arriba... pero esta periodicidad no está lejos. Hay un caso notable, cuando $n-3$ es múltiplo de $8$, para el cual otra construcción de familia máxima $F$ existe. ¡A partir de ahora, utilizaremos las nociones de álgebra lineal !

Una matriz de Hadamard es una matriz $H$ de tamaño $m\times{}m$ con $\pm1$ como elementos, tal que $H^tH=HH^t=m\mathrm{I}$, donde $H^t$ es la matriz transpuesta e $\mathrm{I}$ es la matriz identidad, ver [6]. Las matrices

\[ \left(1 \right), \qquad \left( \begin{array}{rr} 1&1\\ 1&-1 \end{array} \right), \qquad \left( \begin{array}{rrrr} 1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1 \end{array} \right) \]

son los primeros ejemplos. Modulo normalización evidente, podemos suponer que la primera línea y la primera columna de $H$ solo contienen el número $1$, ver  [7] para los detalles. Las matrices de Hadamard solo puede existir cuando $m=1,2$ o $m=4k$.

Si $m=8k+4$, entonces una matriz de Hadamard de tamaño $m\times{}m$ da nacimiento a una familia de clubes para $n=m-1$. La construcción, bien conocida en la teoría de los códigos binarios, es la siguiente :

  • Se retira la primera columna de $ H $ (que no contiene información) ;
  • Se define la matriz $H_1$ de tamaño $(m-1)\times{}m$ reemplazando $1$ por $0$ y $-1$ por $1$ ;
  • Se define la matriz $H_2$ reemplazando $-1$ por $0$.

Afirmamos que las líneas de matrices $H_1$ y $H_2$ forman una familia $F$ que satisface las condiciones del teorema.

En efecto, sean $X,Y$ dos líneas diferentes de $H_1$, queremos mostrar que $d(X,Y)=4k+2$. Cada línea de la matriz de Hadamard $H$ es de la forma

\[ \left(1,\,(-1)^{x_1},\,(-1)^{x_2},\ldots,(-1)^{x_n}\right), \]

donde $X=(x_1,x_2,\ldots,x_n)$ es la línea correspondiente de $ H_1 $. Por definición de una matriz de Hadamard, sus líneas son ortogonales entre sí. Eso significa que la igualdad $x_i+y_i=1$ se produce exactamente $m/2=4k+2$ veces para $i$ entre $1$ y $n$.

Por otro lado, las líneas de $ H_1 $ y $H_2 $ están en dualidad : $X\leftrightarrow{}X+\omega$, donde $\omega$ es el elemento más largo. Eso implica que la distancia entre dos líneas de $ H_2 $ es también igual a $4k+2$, y que las distancias entre una línea de $H_1$ y una línea $H_2$ son impares.

Ejemplo. Módulo equivalencia, la única matriz de Hadamard $H$ de tamaño $12\times12$ corresponde a las matrices binarias de tamaño $12\times11$ siguientes :

\[ H_1= \left( \begin{array}{rrrrrrrrrrr} 1&1&1&1&1&1&1&1&1&1&1\\ 0&1&0&1&1&1&0&0&0&1&0\\ 0&0&1&0&1&1&1&0&0&0&1\\ 1&0&0&1&0&1&1&1&0&0&0\\ 0&1&0&0&1&0&1&1&1&0&0\\ 0&0&1&0&0&1&0&1&1&1&0\\ 0&0&0&1&0&0&1&0&1&1&1\\ 1&0&0&0&1&0&0&1&0&1&1\\ 1&1&0&0&0&1&0&0&1&0&1\\ 1&1&1&0&0&0&1&0&0&1&0\\ 0&1&1&1&0&0&0&1&0&0&1\\ 1&0&1&1&1&0&0&0&1&0&0 \end{array} \right) \] y \[ H_2= \left( \begin{array}{rrrrrrrrrrr} 0&0&0&0&0&0&0&0&0&0&0\\ 1&0&1&0&0&0&1&1&1&0&1\\ 1&1&0&1&0&0&0&1&1&1&0\\ 0&1&1&0&1&0&0&0&1&1&1\\ 1&0&1&1&0&1&0&0&0&1&1\\ 1&1&0&1&1&0&1&0&0&0&1\\ 1&1&1&0&1&1&0&1&0&0&0\\ 0&1&1&1&0&1&1&0&1&0&0\\ 0&0&1&1&1&0&1&1&0&1&0\\ 0&0&0&1&1&1&0&1&1&0&1\\ 1&0&0&0&1&1&1&0&1&1&0\\ 0&1&0&0&0&1&1&1&0&1&1 \end{array} \right) \]

Las líneas de las matrices $ H_1 $ y $H_2 $ constituyen una familia $F$ de clubes en una ciudad con $11$ habitantes, de cardinal $24$. Notemos que este ejemplo está vinculado al código de Golay, que es un código correctores de errores muy famoso y útil.

La existencia de matrices $4k\times4k$ de Hadamard para $k$ arbitrario es la conjetura de Hadamard clásica que tiene una historia fascinante. Hemos mostrado recién que para un número impar $k$, esto es equivalente a la existencia de una familia $F$ de vectores de $\mathbb F_2^{4k-1}$ (espacio vectorial de dimensión $4k-1$ sobre el cuerpo con $2$ elementos) tales que la distancia entre dos vectores es siempre $2k$. Notemos que la existencia de una familia de vectores con estas características está confirmada para pequeños valores de $k$ ; ver la tabla [8]

Post-scriptum :

Agradecimientos. El autor debe agradecer a Serge Cantat, John Conway y a Sophie Morier-Genoud por múltiples discusiones estimulantes. La redacción de Images des Maths, así como al autor, agradecen por su atenta relectura a los relectores cuyos seudónimos son alchymic666, Lison.

Article original édité par Serge Cantat

Notes

[1Vea aquí las matrices de Hadamard

[2S. Morier-Genoud, V. Ovsienko, Extremal set theory, cubic forms on $\mathbb F_2^n$ and Hurwitz square identities, arXiv:1304.0949.

[3cambiando las listas que describen los clubes de $F_0$ por adición de la lista de un club $X_0$ fijo en $F_0$

[4Notemos que la familia construida es la única invariante bajo la acción del grupo de permutaciones de $ n $ elementos.

[5pero no existen familias invariantes bajo la acción del grupo de permutaciones

[6S. Eliahou, La conjecture de Hadamard (I) y (II), Images des Mathématiques, ya mencionada en una nota más arriba.

[7K.J. Horadam, Hadamard matrices and their applications, Princeton University Press, 2007

[8La tabla de códigos binarios http://www.win.tue.nl/$\tilde{}$aeb/codes/binary-1.html

Partager cet article

Pour citer cet article :

Julio E. De Villegas, Jimena Royo-Letelier — «Oddtown y Eventown Parte II» — Images des Mathématiques, CNRS, 2022

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?