Conjunto de diferencias

En combinatoria , un conjunto de diferencias es un subconjunto de tamaño de un grupo de orden tal que cada elemento no identidad de puede expresarse como un producto de elementos de exactamente formas. Se dice que un conjunto de diferencias es cíclico , abeliano , no abeliano , etc., si el grupo tiene la propiedad correspondiente. Un conjunto de diferencias con a veces se denomina planar o simple . ^[1] Si es un grupo abeliano escrito en notación aditiva, la condición definitoria es que cada elemento distinto de cero de puede escribirse como una diferencia de elementos de exactamente formas. El término "conjunto de diferencias" surge de esta manera. ${\displaystyle (v,k,\lambda )}$ ${\displaystyle D}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle d_{1}d_{2}^{-1}}$ ${\displaystyle D}$ ${\displaystyle \lambda }$ ${\displaystyle D}$ ${\displaystyle G}$ ${\displaystyle \lambda =1}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle D}$ ${\displaystyle \lambda }$

Datos básicos

• Un argumento de conteo simple muestra que hay exactamente pares de elementos que producirán elementos no idénticos, por lo que cada conjunto de diferencias debe satisfacer la ecuación ${\displaystyle k^{2}-k}$ ${\displaystyle D}$ ${\displaystyle k^{2}-k=(v-1)\lambda .}$
• Si es un conjunto de diferencias y entonces también es un conjunto de diferencias, y se llama traducido de ( en notación aditiva). ${\displaystyle D}$ ${\displaystyle g\in G,}$ ${\displaystyle gD=\{gd:d\in D\}}$ ${\displaystyle D}$ ${\displaystyle D+g}$
• El complemento de un conjunto de -diferencias es un conjunto de -diferencias. ^[2] ${\displaystyle (v,k,\lambda )}$ ${\displaystyle (v,v-k,v-2k+\lambda )}$
• El conjunto de todos los traslaciones de un conjunto de diferencias forma un diseño de bloques simétricos , llamado desarrollo de y denotado por En un diseño de este tipo hay elementos (generalmente llamados puntos) y bloques (subconjuntos). Cada bloque del diseño consta de puntos, cada punto está contenido en bloques. Dos bloques cualesquiera tienen exactamente elementos en común y dos puntos cualesquiera están contenidos simultáneamente en exactamente bloques. El grupo actúa como un grupo de automorfismos del diseño. Es marcadamente transitivo tanto en puntos como en bloques. ^[3] ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle dev(D).}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle G}$
  • En particular, si , entonces el conjunto de diferencias da lugar a un plano proyectivo . Un ejemplo de un conjunto de diferencias (7,3,1) en el grupo es el subconjunto . Las traducidas de este conjunto de diferencias forman el plano de Fano . ${\displaystyle \lambda =1}$ ${\displaystyle \mathbb {Z} /7\mathbb {Z} }$ ${\displaystyle \{1,2,4\}}$
• Dado que cada conjunto de diferencias da un diseño simétrico , el conjunto de parámetros debe satisfacer el teorema de Bruck-Ryser-Chowla . ^[4]
• No todo diseño simétrico produce un conjunto de diferencias. ^[5]

Conjuntos de diferencias equivalentes e isomorfos

Dos conjuntos de diferencias en grupo y en grupo son equivalentes si existe un isomorfismo de grupo entre y tal que para algunos Los dos conjuntos de diferencias son isomorfos si los diseños y son isomorfos como diseños de bloques. ${\displaystyle D_{1}}$ ${\displaystyle G_{1}}$ ${\displaystyle D_{2}}$ ${\displaystyle G_{2}}$ ${\displaystyle \psi }$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle D_{1}^{\psi }=\{d^{\psi }\colon d\in D_{1}\}=gD_{2}}$ ${\displaystyle g\in G_{2}.}$ ${\displaystyle dev(D_{1})}$ ${\displaystyle dev(D_{2})}$

Los conjuntos de diferencias equivalentes son isomorfos, pero existen ejemplos de conjuntos de diferencias isomorfos que no son equivalentes. En el caso de los conjuntos de diferencias cíclicos, todos los conjuntos de diferencias isomorfos conocidos son equivalentes. ^[6]

Multiplicadores

Un multiplicador de un conjunto de diferencias en un grupo es un automorfismo de grupo de tal que para algún Si es abeliano y es el automorfismo que asigna , entonces se llama multiplicador numérico o de Hall . ^[7] ${\displaystyle D}$ ${\displaystyle G}$ ${\displaystyle \phi }$ ${\displaystyle G}$ ${\displaystyle D^{\phi }=gD}$ ${\displaystyle g\in G.}$ ${\displaystyle G}$ ${\displaystyle \phi }$ ${\displaystyle h\mapsto h^{t}}$ ${\displaystyle t}$

Se ha conjeturado que si p es un primo que divide y no divide a v , entonces el automorfismo de grupo definido por fija algún traslativo de D (esto es equivalente a ser un multiplicador). Se sabe que es cierto para cuando es un grupo abeliano, y esto se conoce como el Primer Teorema del Multiplicador. Un resultado conocido más general, el Segundo Teorema del Multiplicador, dice que si es un conjunto de -diferencias en un grupo abeliano de exponente (el mínimo común múltiplo de los órdenes de cada elemento), sea un entero coprimo con . Si existe un divisor de tal que para cada primo p que divide a m , existe un entero i con , entonces t es un divisor numérico. ^[8] ${\displaystyle k-\lambda }$ ${\displaystyle g\mapsto g^{p}}$ ${\displaystyle p>\lambda }$ ${\displaystyle G}$ ${\displaystyle D}$ ${\displaystyle (v,k,\lambda )}$ ${\displaystyle G}$ ${\displaystyle v^{*}}$ ${\displaystyle t}$ ${\displaystyle v}$ ${\displaystyle m>\lambda }$ ${\displaystyle k-\lambda }$ ${\displaystyle t\equiv p^{i}\ {\pmod {v^{*}}}}$

Por ejemplo, 2 es un multiplicador del conjunto de diferencias (7,3,1) mencionado anteriormente.

Se ha mencionado que un multiplicador numérico de un conjunto de diferencias en un grupo abeliano fija una traducida de , pero también se puede demostrar que hay una traducida de que está fijada por todos los multiplicadores numéricos de ^[9] ${\displaystyle D}$ ${\displaystyle G}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D.}$

Parámetros

Los conjuntos de diferencias conocidos o sus complementos tienen uno de los siguientes conjuntos de parámetros: ^[10]

• ${\displaystyle ((q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1))}$-conjunto de diferencias para una potencia prima y un entero positivo . Estos se conocen como parámetros clásicos y existen muchas construcciones de conjuntos de diferencias que tienen estos parámetros. ${\displaystyle q}$ ${\displaystyle n}$
• ${\displaystyle (4n-1,2n-1,n-1)}$-conjunto de diferencias para algún entero positivo . Los conjuntos de diferencias con v = 4 n − 1 se denominan conjuntos de diferencias de tipo Paley . ${\displaystyle n}$
• ${\displaystyle (4n^{2},2n^{2}-n,n^{2}-n)}$-conjunto de diferencias para algún entero positivo . Un conjunto de diferencias con estos parámetros es un conjunto de diferencias de Hadamard . ${\displaystyle n}$
• ${\displaystyle (q^{n+1}(1+(q^{n+1}-1)/(q-1)),q^{n}(q^{n+1}-1)/(q-1),q^{n}(q^{n}-1)/(q-1))}$-conjunto de diferencias para una potencia prima y un entero positivo . Conocidos como parámetros de McFarland . ${\displaystyle q}$ ${\displaystyle n}$
• ${\displaystyle (3^{n+1}(3^{n+1}-1)/2,3^{n}(3^{n+1}+1)/2,3^{n}(3^{n}+1)/2)}$-conjunto de diferencias para algún entero positivo . Conocidos como parámetros de Spence . ${\displaystyle n}$
• ${\displaystyle (4q^{2n}(q^{2n}-1)/(q-1),q^{2n-1}(1+2(q^{2n}-1)/(q+1)),q^{2n-1}(q^{2n-1}+1)(q-1)/(q+1))}$-conjunto de diferencias para alguna potencia prima y algún entero positivo . Los conjuntos de diferencias con estos parámetros se denominan conjuntos de diferencias de Davis-Jedwab-Chen . ${\displaystyle q}$ ${\displaystyle n}$

Conjuntos de diferencias conocidas

En muchas construcciones de conjuntos de diferencias, los grupos que se utilizan están relacionados con los grupos aditivos y multiplicativos de cuerpos finitos . La notación utilizada para denotar estos cuerpos difiere según la disciplina. En esta sección, es el cuerpo de Galois de orden donde es un primo o una potencia prima. El grupo bajo adición se denota por , mientras que es el grupo multiplicativo de elementos distintos de cero. ${\displaystyle {\rm {GF}}(q)}$ ${\displaystyle q,}$ ${\displaystyle q}$ ${\displaystyle G=({\rm {GF}}(q),+)}$ ${\displaystyle {\rm {GF}}(q)^{*}}$

• Conjunto de diferencias de Paley : ${\displaystyle (4n-1,2n-1,n-1)}$

Sea una potencia prima. En el grupo , sea el conjunto de todos los cuadrados distintos de cero. ${\displaystyle q=4n-1}$ ${\displaystyle G=({\rm {GF}}(q),+)}$ ${\displaystyle D}$

• Cantante - conjunto de diferencias: ${\displaystyle ((q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1))}$

Sea . Entonces el conjunto es un conjunto de -diferencias, donde es la función de traza ${\displaystyle G={\rm {GF}}(q^{n+2})^{*}/{\rm {GF}}(q)^{*}}$ ${\displaystyle D=\{x\in G~|~{\rm {Tr}}_{q^{n+2}/q}(x)=0\}}$ ${\displaystyle ((q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1))}$ ${\displaystyle {\rm {Tr}}_{q^{n+2}/q}:{\rm {GF}}(q^{n+2})\rightarrow {\rm {GF}}(q)}$ ${\displaystyle {\rm {{Tr}_{q^{n+2}/q}(x)=x+x^{q}+\cdots +x^{q^{n+1}}.}}}$

• Diferencia de potencias primos gemelos establecida cuando y son ambas potencias primos: ${\displaystyle \left(q^{2}+2q,{\frac {q^{2}+2q-1}{2}},{\frac {q^{2}+2q-3}{4}}\right)}$ ${\displaystyle q}$ ${\displaystyle q+2}$

En el grupo , sea ^[11] ${\displaystyle G=({\rm {GF}}(q),+)\oplus ({\rm {GF}}(q+2),+)}$ ${\displaystyle D=\{(x,y)\colon y=0{\text{ or }}x{\text{ and }}y{\text{ are non-zero and both are squares or both are non-squares}}\}.}$

Historia

El uso sistemático de conjuntos de diferencias cíclicas y métodos para la construcción de diseños de bloques simétricos se remonta a RC Bose y un artículo seminal suyo en 1939. ^[12] Sin embargo, varios ejemplos aparecieron antes de esto, como los "Conjuntos de Diferencias de Paley" que datan de 1933. ^[13] La generalización del concepto de conjunto de diferencias cíclicas a grupos más generales se debe a RH Bruck ^[14] en 1955. ^[15] Los multiplicadores fueron introducidos por Marshall Hall Jr. ^[16] en 1947. ^[17]

Solicitud

Xia, Zhou y Giannakis descubrieron que los conjuntos de diferencias se pueden utilizar para construir un libro de códigos vectoriales complejo que alcanza el difícil límite de Welch en la amplitud máxima de correlación cruzada. El libro de códigos así construido también forma la denominada variedad Grassmanniana .

Generalizaciones

Una familia de diferencias es un conjunto de subconjuntos de un grupo tal que el orden de es , el tamaño de es para todos los , y cada elemento no identidad de puede expresarse como un producto de elementos de para algunos (es decir, ambos provienen del mismo ) exactamente de maneras. ${\displaystyle (v,k,\lambda ,s)}$ ${\displaystyle B=\{B_{1},\ldots ,B_{s}\}}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle B_{i}}$ ${\displaystyle k}$ ${\displaystyle i}$ ${\displaystyle G}$ ${\displaystyle d_{1}d_{2}^{-1}}$ ${\displaystyle B_{i}}$ ${\displaystyle i}$ ${\displaystyle d_{1},d_{2}}$ ${\displaystyle B_{i}}$ ${\displaystyle \lambda }$

Un conjunto de diferencias es una familia de diferencias con La ecuación de parámetros anterior se generaliza a ^[18] El desarrollo de una familia de diferencias es un diseño de 2. Cada diseño de 2 con un grupo de automorfismos regular es para alguna familia de diferencias ${\displaystyle s=1.}$ ${\displaystyle s(k^{2}-k)=(v-1)\lambda .}$ ${\displaystyle dev(B)=\{B_{i}+g:i=1,\ldots ,s,g\in G\}}$ ${\displaystyle dev(B)}$ ${\displaystyle B.}$

Véase también

• Diseño combinatorio

Notas

1. van Lint y Wilson 1992, pág. 331
2. Wallis 1988, pág. 61 - Teorema 4.5
3. van Lint & Wilson 1992, p. 331 - Teorema 27.2. El teorema sólo enuncia la transitividad puntual, pero la transitividad en bloque se deduce de ello según el segundo corolario de la p. 330.
4. Colbourn y Dinitz 2007, pág. 420 (18.7 Observación 2)
5. Colbourn y Dinitz 2007, pág. 420 (18.7 Observación 1)
6. Colbourn y Dinitz 2007, pág. 420 (Observación 18.9)
7. van Lint y Wilson 1992, pág. 345
8. van Lint & Wilson 1992, pág. 349 (Teorema 28.7)
9. Beth, Jungnickel y Lenz 1986, pág. 280 (Teorema 4.6)
10. Colbourn y Dinitz 2007, págs. 422-425
11. Colbourn y Dinitz 2007, pág. 425 (Construcción 18.49)
12. Bose, RC (1939), "Sobre la construcción de diseños de bloques incompletos equilibrados", Annals of Eugenics , 9 (4): 353–399, doi : 10.1111/j.1469-1809.1939.tb02219.x , JFM  65.1110.04, Zbl  0023.00102
13. Wallis 1988, pág. 69
14. Bruck, RH (1955), "Conjuntos de diferencias en un grupo finito", Transactions of the American Mathematical Society , 78 (2): 464–481, doi : 10.2307/1993074 , JSTOR  1993074, Zbl  0065.13302
15. van Lint y Wilson 1992, pág. 340
16. Hall Jr., Marshall (1947), "Planos proyectivos cíclicos", Duke Mathematical Journal , 14 (4): 1079–1090, doi :10.1215/s0012-7094-47-01482-8, S2CID  119846649, Zbl  0029.22502
17. Beth, Jungnickel y Lenz 1986, pág. 275
18. Beth, Jungnickel y Lenz 1986, pág. 310 (2.8.a)

Referencias

• Beth, Thomas; Jungnickel, Dieter ; Lenz, Hanfried (1986), Teoría del diseño , Cambridge: Cambridge University Press, ISBN 0-521-33334-2, Zbl0602.05001 ​
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Manual de diseños combinatorios , Matemáticas discretas y sus aplicaciones (2.ª ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1, Zbl1101.05001 ​
• van Lint, JH; Wilson, RM (1992), Un curso de combinatoria , Cambridge: Cambridge University Press , ISBN 0-521-42260-4, Zbl0769.05001 ​
• Wallis, WD (1988). Diseños combinatorios . Marcel Dekker. ISBN 0-8247-7942-8.Zbl 0637.05004  .

Lectura adicional

• Moore, EH; Pollastek, HSK (2013). Conjuntos de diferencias: conexión entre álgebra, combinatoria y geometría. AMS. ISBN 978-0-8218-9176-6.
• Storer, Thomas (1967). Ciclotomía y conjuntos diferenciales . Chicago: Markham Publishing Company. Zbl  0157.03301.
• Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2005). "Lograr el límite de Welch con conjuntos de diferencias" (PDF) . IEEE Transactions on Information Theory . 51 (5): 1900–1907. doi :10.1109/TIT.2005.846411. ISSN  0018-9448. S2CID  8916926. Zbl  1237.94007..

Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2006). "Corrección para lograr el límite de Welch con conjuntos de diferencias ". IEEE Trans. Inf. Theory . 52 (7): 3359. doi :10.1109/tit.2006.876214. Zbl  1237.94008.

• Zwillinger, Daniel (2003). Tablas y fórmulas matemáticas estándar del CRC . CRC Press. pág. 246. ISBN 1-58488-291-3.