Conjunto de diferencias

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

• Un argumento de conteo simple muestra que hay exactamente${\displaystyle k^{2}-k}$pares de elementos de${\displaystyle D}$que producirá elementos distintos de la identidad, por lo que cada conjunto de diferencias debe satisfacer la ecuación${\displaystyle k^{2}-k=(v-1)\lambda.}$
• Si${\displaystyle D}$es un conjunto de diferencias y${\displaystyle g\in G,}$entonces${\displaystyle gD=\{gd:d\en D\}}$También es un conjunto de diferencias y se denomina traslación de${\displaystyle D}$(${\displaystyle D+g}$en notación aditiva).
• El complemento de un${\displaystyle (v,k,\lambda)}$-el conjunto de diferencias es un${\displaystyle (v,vk,v-2k+\lambda)}$-conjunto de diferencias. ^{[ 2 ]}
• El conjunto de todas las traducciones de un conjunto de diferencias${\displaystyle D}$forma un diseño de bloques simétrico , llamado desarrollo de${\displaystyle D}$y denotado por${\displaystyle dev(D).}$En tal diseño hay${\displaystyle v}$elementos (generalmente llamados puntos) y${\displaystyle v}$bloques (subconjuntos). Cada bloque del diseño consta de${\displaystyle k}$puntos, cada punto está contenido en${\displaystyle k}$bloques. Cualquier par de bloques tiene exactamente${\displaystyle \lambda }$elementos en común y cualesquiera dos puntos están contenidos simultáneamente en exactamente${\displaystyle \lambda }$bloques. El grupo${\displaystyle G}$actúa como un grupo de automorfismos del diseño. Es estrictamente transitivo tanto en puntos como en bloques. ^{[ 3 ]}
  • En particular, si${\displaystyle \lambda =1}$, entonces el conjunto diferencia da lugar a un plano proyectivo . Un ejemplo de un conjunto diferencia (7,3,1) en el grupo${\displaystyle \mathbb {Z} /7\mathbb {Z} }$es el subconjunto${\displaystyle \{1,2,4\}}$. Las traslaciones de este conjunto de diferencias forman el plano de Fano .
• Dado que cada conjunto de diferencias produce 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 dan como resultado un conjunto diferente. ^{[ 5 ]}

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

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 ]}

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

Se ha conjeturado que si p es un número primo divisor${\displaystyle k-\lambda }$y no dividiendo v , entonces el automorfismo de grupo definido por${\displaystyle g\mapsto g^{p}}$corrige alguna traslación de D (esto es equivalente a ser un multiplicador). Se sabe que es cierto para${\displaystyle p>\lambda }$cuando${\displaystyle G}$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${\displaystyle D}$es un${\displaystyle (v,k,\lambda)}$-diferencia establecida en un grupo abeliano${\displaystyle G}$del exponente${\displaystyle v^{*}}$(el mínimo común múltiplo de los órdenes de cada elemento), sea${\displaystyle t}$ser un número entero coprimo con${\displaystyle v}$Si existe un divisor${\displaystyle m>\lambda }$de${\displaystyle k-\lambda }$tal que para cada primo p que divide a m , existe un entero i con${\displaystyle t\equiv p^{i}\ {\pmod {v^{*}}}}$, entonces t es un divisor numérico . ^{[ 8 ]}

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${\displaystyle D}$en un grupo abeliano${\displaystyle G}$corrige una traducción de${\displaystyle D}$, pero también se puede demostrar que existe una traducción de${\displaystyle D}$que está fijado por todos los multiplicadores numéricos de${\displaystyle D.}$^{[ 9 ]}

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${\displaystyle q}$y algún número entero positivo${\displaystyle n}$Estos se conocen como parámetros clásicos y existen muchas construcciones de conjuntos de diferencias que poseen estos parámetros.
• ${\displaystyle (4n-1,2n-1,n-1)}$-diferencia establecida para algún entero positivo${\displaystyle n}$. Los conjuntos de diferencias con v = 4 n − 1 se denominan conjuntos de diferencias de tipo Paley .
• ${\displaystyle (4n^{2},2n^{2}-n,n^{2}-n)}$-diferencia establecida para algún entero positivo${\displaystyle n}$Un conjunto de diferencias con estos parámetros es un conjunto de diferencias de Hadamard . La existencia de dicho conjunto de diferencias en un grupo cíclico es el tema de la conjetura de Ryser sobre matrices de Hadamard circulantes , un problema abierto bien conocido.
• ${\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${\displaystyle q}$y algún número entero positivo${\displaystyle n}$. Conocidos como los parámetros de McFarland .
• ${\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 entero positivo${\displaystyle n}$. Conocidos como los parámetros de Spence .
• ${\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${\displaystyle q}$y algún número entero positivo${\displaystyle n}$Los conjuntos de diferencias con estos parámetros se denominan conjuntos de diferencias de Davis-Jedwab-Chen .

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,${\displaystyle {\rm {GF}}(q)}$es el campo de Galois de orden${\displaystyle q,}$dónde${\displaystyle q}$es un número primo o una potencia prima. El grupo bajo la suma se denota por${\displaystyle G=({\rm {GF}}(q),+)}$, mientras${\displaystyle {\rm {GF}}(q)^{*}}$es el grupo multiplicativo de elementos distintos de cero.

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

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

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

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

• Potencia primaria doble${\displaystyle \left(q^{2}+2q,{\frac {q^{2}+2q-1}{2}},{\frac {q^{2}+2q-3}{4}}\right)}$-diferencia establecida cuando${\displaystyle q}$y${\displaystyle q+2}$son ambos poderes primordiales:

En el grupo${\displaystyle G=({\rm {GF}}(q),+)\oplus ({\rm {GF}}(q+2),+)}$, dejar${\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}}\}.}$^{[ 11 ]}

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 a un artículo fundamental suyo de 1939. ^{[ 12 ]} Sin embargo, aparecieron varios ejemplos 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 ]}

Xia, Zhou y Giannakis descubrieron que los conjuntos de diferencias pueden utilizarse para construir un diccionario de códigos vectoriales complejo que alcanza la difícil cota de Welch para la amplitud máxima de correlación cruzada.

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

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

• Diseño combinatorio
• La conjetura de Ryser sobre las matrices de Hadamard circulantes

• Beth, Thomas; 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), Handbook of Combinatorial Designs , Discrete Mathematics and its Applications (2.ª  ed.), Boca Raton: 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 . 

• Moore, EH; Pollastek, HSK (2013). Conjuntos de diferencias: Conectando álgebra, combinatoria y geometría . AMS. ISBN 978-0-8218-9176-6.
• Storer, Thomas (1967). Ciclotomía y conjuntos de diferencias . Chicago: Markham Publishing Company. Zbl 0157.03301 . 
• Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2005). "Logrando la cota 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 a la obtención de la cota 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 de CRC . CRC Press. pág . 246. ISBN  1-58488-291-3.