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 maneras. 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 plano 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 pueda escribirse como una diferencia de elementos de exactamente maneras. De esta manera surge el término "conjunto de diferencias". ${\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 }$

Hechos 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 .}$
• If es un conjunto de diferencias y luego también lo es, y se denomina traducción 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 en diferencias es un conjunto en diferencias. ^[2] ${\displaystyle (v,k,\lambda )}$ ${\displaystyle (v,v-k,v-2k+\lambda )}$
• El conjunto de todas las traslaciones de un conjunto de diferencias forma un diseño de bloques simétrico , llamado desarrollo de y denotado por. En tal diseño 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 diferencia da lugar a un plano proyectivo . Un ejemplo de un conjunto de diferencias (7,3,1) en el grupo es el subconjunto . Las traducciones 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 todos los diseños simétricos ofrecen un conjunto diferente. ^[5]

Conjuntos de diferencias equivalentes e isomorfas

Dos conjuntos de diferencias en grupo y en grupo son equivalentes si hay un isomorfismo de grupo entre ellos 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 isomórficos, pero existen ejemplos de conjuntos de diferencias isomórficos que no son equivalentes. En el caso de los conjuntos de diferencias cíclicos, todos los conjuntos de diferencias isomórficos conocidos son equivalentes. ^[6]

Multiplicadores

Un multiplicador de una diferencia establecida en un grupo es un automorfismo de grupo tal que para algunos Si es abeliano y es el automorfismo que mapea , 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 alguna traducción de D (esto equivale a ser un multiplicador). Se sabe que es cierto cuando es un grupo abeliano, y esto se conoce como el primer teorema del multiplicador. Un resultado más general conocido, el segundo teorema del multiplicador, dice que si hay una diferencia en un grupo abeliano de exponentes (el mínimo común múltiplo de los órdenes de cada elemento), sea un número entero coprimo . Si existe un divisor de tal que para cada primo p que divide m , existe un número 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 una diferencia establecida en un grupo abeliano fija una traducción de , pero también se puede demostrar que hay una traducción de la cual 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))}$-diferencia establecida para alguna potencia prima y algún 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)}$-diferencia establecida para algún número entero positivo . Los conjuntos de diferencias con v = 4 n − 1 se denominan conjuntos de diferencias tipo Paley . ${\displaystyle n}$
• ${\displaystyle (4n^{2},2n^{2}-n,n^{2}-n)}$-diferencia establecida para algún número 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))}$-diferencia establecida para alguna potencia prima y algún 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)}$-diferencia establecida para algún número 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))}$-diferencia establecida 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 indicar estos campos difiere según la disciplina. En esta sección, se encuentra el campo de orden de Galois donde se encuentra una potencia prima o prima. El grupo bajo la suma 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)^{*}}$

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

Sea una potencia primordial. 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))}$

Dejar . Entonces el conjunto es un conjunto de diferencias, ¿dónde está la función de seguimiento? ${\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}}.}}}$

• Poder primo gemelo: diferencia establecida cuando y son ambos poderes 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 , dejemos ^[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íclicos y métodos para la construcción de diseños de bloques simétricos se remonta a RC Bose y un artículo suyo fundamental en 1939. ^[12] Sin embargo, varios ejemplos aparecieron antes, como los "Conjuntos de diferencias de Paley". que se remontan a 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] Marshall Hall Jr. ^[16] introdujo los multiplicadores en 1947. ^{[ 17]}

Solicitud

Xia, Zhou y Giannakis descubren que los conjuntos de diferencias se pueden utilizar para construir un libro de códigos vectoriales complejo que logre el difícil límite de Welch en la amplitud máxima de correlación cruzada. El libro de códigos así construido forma también la llamada 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 , y cada elemento no idéntico de puede expresarse como un producto de elementos de para algunos (es decir, ambos provienen del mismo ) exactamente de la misma manera. ${\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 2 . Cada diseño 2 con un grupo de automorfismo regular es para alguna familia diferente ${\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.}$

Ver también

• Diseño combinatorio

Notas

1. van Lint y Wilson 1992, pág. 331
2. Wallis 1988, pag. 61 - Teorema 4.5
3. van Lint y Wilson 1992, pág. 331 - Teorema 27.2. El teorema solo establece la transitividad puntual, pero la transitividad en bloque se deriva de esto por 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 y 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, pag. 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, Tomás; Jungnickel, Dieter ; Lenz, Hanfried (1986), Teoría del diseño , Cambridge: Cambridge University Press, ISBN 0-521-33334-2, Zbl  0602.05001
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Manual de diseños combinatorios , Matemáticas discretas y sus aplicaciones (2ª ed.), Boca Ratón: Chapman & Hall/CRC, ISBN 978-1-58488-506-1, Zbl  1101.05001
• van Lint, JH; Wilson, RM (1992), Un curso de combinatoria , Cambridge: Cambridge University Press , ISBN 0-521-42260-4, Zbl  0769.05001
• Wallis, WD (1988). Diseños combinatorios . Marcel Dekker. ISBN 0-8247-7942-8. Zbl  0637.05004.

Otras lecturas

• Moore, EH; Pollastek, HSK (2013). Conjuntos de diferencias: conexión de álgebra, combinatoria y geometría. AMS. ISBN 978-0-8218-9176-6.
• Almacenador, Thomas (1967). Ciclotomía y conjuntos diferenciales . Chicago: Compañía editorial Markham. Zbl  0157.03301.
• Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2005). "Lograr el límite de Welch con conjuntos de diferencias" (PDF) . Transacciones IEEE sobre teoría de la información . 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 galés con conjuntos de diferencia ". Traducción IEEE. inf. Teoría . 52 (7): 3359. doi :10.1109/tit.2006.876214. Zbl  1237.94008.

• Zwillinger, Daniel (2003). Tablas y fórmulas matemáticas estándar CRC . Prensa CRC. pag. 246.ISBN​ 1-58488-291-3.