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)}$ ${\estilo de visualización D}$ ${\estilo de visualización k}$ ${\estilo de visualización G}$ ${\estilo de visualización v}$${\estilo de visualización G}$${\displaystyle d_{1}d_{2}^{-1}}$${\estilo de visualización D}$${\estilo de visualización \lambda}$${\estilo de visualización D}$${\estilo de visualización G}$${\displaystyle \lambda = 1}$${\estilo de visualización G}$${\estilo de visualización G}$${\estilo de visualización D}$${\estilo de visualización \lambda}$

• 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$estilo de visualización k^{2}-k$${\estilo de visualización 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).${\estilo de visualización D}$${\displaystyle g\en G,}$${\displaystyle gD=\{gd:d\en D\}}$${\estilo de visualización D}$${\estilo de visualización D+g}$
• El complemento de un conjunto de -diferencias es un conjunto de -diferencias. ^[2]${\displaystyle (v,k,\lambda)}$${\displaystyle (v,vk,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]${\estilo de visualización D}$${\estilo de visualización D}$${\displaystyle dev(D).}$${\estilo de visualización v}$ ${\estilo de visualización v}$ ${\estilo de visualización k}$${\estilo de visualización k}$${\estilo de visualización \lambda}$${\estilo de visualización \lambda}$${\estilo de visualización 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} }$${\estilo de visualización \{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]

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. $Estilo de visualización D_{1}$$Estilo de visualización G_{1}$$Estilo de visualización D_{2}$$Estilo de visualización G_{2}$ ${\estilo de visualización \psi}$$Estilo de visualización G_{1}$$Estilo de visualización G_{2}$${\displaystyle D_{1}^{\psi }=\{d^{\psi }\colon d\in D_{1}\}=gD_{2}}$${\displaystyle g\en 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]

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]${\estilo de visualización D}$${\estilo de visualización G}$ ${\estilo de visualización \phi}$${\estilo de visualización G}$${\displaystyle D^{\phi }=gD}$${\displaystyle g\en G.}$${\estilo de visualización G}$${\estilo de visualización \phi}$${\displaystyle h\mapsto h^{t}}$${\estilo de visualización 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}$${\estilo de visualización G}$${\estilo de visualización D}$${\displaystyle (v,k,\lambda)}$${\estilo de visualización G}$${\displaystyle v^{*}}$${\estilo de visualización t}$ ${\estilo de visualización 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]${\estilo de visualización D}$${\estilo de visualización G}$${\estilo de visualización D}$${\estilo de visualización D}$${\displaystyle D.}$

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

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}}\}.}$

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]

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 .

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.}$

• Diseño combinatorio

• 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  .

• 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.