gobernante golomb

Conjunto de marcas a lo largo de una regla de manera que no haya dos pares de marcas a la misma distancia entre sí.

Regla Golomb de orden 4 y longitud 6. Esta regla es óptima y perfecta .

Las reglas circulares perfectas de Golomb (también llamadas conjuntos de diferencias ) con el orden especificado. (Esta vista previa debería mostrar varios círculos concéntricos. De lo contrario, haga clic para ver una versión más grande).

En matemáticas , una regla Golomb es un conjunto de marcas en posiciones enteras a lo largo de una regla de modo que no hay dos pares de marcas que estén a la misma distancia. El número de marcas en la regla es su orden , y la distancia más grande entre dos de sus marcas es su longitud . La traducción y reflexión de una regla Golomb se consideran triviales, por lo que la marca más pequeña se suele poner en 0 y la siguiente marca en el menor de sus dos valores posibles. Los gobernantes de Golomb pueden verse como un caso especial unidimensional de matrices de Costas .

El gobernante Golomb recibió su nombre de Solomon W. Golomb y fue descubierto de forma independiente por Sidon (1932) ^[1] y Babcock (1953). Sophie Piccard también publicó una investigación temprana sobre estos conjuntos, en 1939, estableciendo como teorema la afirmación de que dos reglas de Golomb con la misma distancia establecida deben ser congruentes . Esto resultó ser falso para las reglas de seis puntos, pero cierto en otros casos. ^[2]

No es necesario que un gobernante Golomb pueda medir todas las distancias hasta su longitud, pero si lo hace, se llama gobernante Golomb perfecto . Se ha demostrado que no existe un gobernante Golomb perfecto para cinco o más marcas. ^[3] Un gobernante Golomb es óptimo si no existe un gobernante Golomb más corto del mismo orden. Crear reglas de Golomb es fácil, pero demostrar la regla (o reglas) de Golomb óptimas para un orden específico es computacionalmente muy desafiante.

Distributed.net ha completado búsquedas paralelas distribuidas masivamente de gobernantes Golomb óptimos de orden 24 a orden 28, confirmando cada vez al gobernante candidato sospechoso. ^{[4] [5] [6] [7] [8]}

Actualmente, se desconoce la complejidad de encontrar reglas Golomb óptimas (OGR) de orden arbitrario n (donde n se da en unario). ^{[ se necesita aclaración ]} En el pasado hubo cierta especulación de que se trata de un problema NP-difícil . ^[3] Se ha demostrado que los problemas relacionados con la construcción de gobernantes Golomb son NP-difíciles, donde también se observa que ningún problema NP-completo conocido tiene un sabor similar al de encontrar gobernantes Golomb. ^[9]

Definiciones

Reglas de Golomb como conjuntos

Un conjunto de números enteros donde hay un gobernante de Golomb si y sólo si ${\displaystyle A=\{a_{1},a_{2},...,a_{m}\}}$ ${\displaystyle a_{1}<a_{2}<...<a_{m}}$

${\displaystyle {\text{for all }}i,j,k,l\in \left\{1,2,...,m\right\}{\text{such that }}i\neq j{\text{ and }}k\neq l,\ a_{i}-a_{j}=a_{k}-a_{l}\iff i=k{\text{ and }}j=l.}$^[10]

El orden de dicha regla Golomb es y su longitud es . La forma canónica tiene y, si , . Esta forma se puede lograr mediante la traducción y la reflexión. ${\displaystyle m}$ ${\displaystyle a_{m}-a_{1}}$ ${\displaystyle a_{1}=0}$ ${\displaystyle m>2}$ ${\displaystyle a_{2}-a_{1}<a_{m}-a_{m-1}}$

Gobernantes Golomb como funciones

Una función inyectiva con y es una regla de Golomb si y sólo si ${\displaystyle f:\left\{1,2,...,m\right\}\to \left\{0,1,...,n\right\}}$ ${\displaystyle f(1)=0}$ ${\displaystyle f(m)=n}$

${\displaystyle {\text{for all }}i,j,k,l\in \left\{1,2,...,m\right\}{\text{such that }}i\neq j{\text{ and }}k\neq l,f(i)-f(j)=f(k)-f(l)\iff i=k{\text{ and }}j=l.}$^{[11] : 236}

El orden de dicha regla Golomb es y su longitud es . La forma canónica tiene ${\displaystyle m}$ ${\displaystyle n}$

${\displaystyle f(2)<f(m)-f(m-1)}$si . ${\displaystyle m>2}$

Optimidad

Una regla Golomb de orden m con longitud n puede ser óptima en cualquiera de dos aspectos: ^{[11] : 237}

• Puede ser óptimamente denso y exhibir un máximo m para el valor específico de n ,
• Puede ser óptimamente corto y exhibir una n mínima para el valor específico de m .

El término general regla óptima de Golomb se utiliza para referirse al segundo tipo de optimización.

Aplicaciones prácticas

Ejemplo de sala de conferencias con proporciones de una regla Golomb [0, 2, 7, 8, 11], lo que la hace configurable en 10 tamaños diferentes. ^[12]

Teoría de la información y corrección de errores.

Las reglas Golomb se utilizan dentro de la teoría de la información relacionada con los códigos de corrección de errores . ^[13]

Selección de radiofrecuencia

Las reglas de Golomb se utilizan en la selección de frecuencias de radio para reducir los efectos de la interferencia de intermodulación con aplicaciones tanto terrestres ^[14] como extraterrestres ^{[15] .}

Colocación de antena de radio

Las reglas Golomb se utilizan en el diseño de conjuntos en fase de antenas de radio. En radioastronomía, los conjuntos de síntesis unidimensionales pueden tener las antenas en una configuración de regla de Golomb para obtener una redundancia mínima del muestreo de componentes de Fourier. ^{[16] [17]}

Transformadores de corriente

Los transformadores de corriente de relación múltiple utilizan reglas Golomb para colocar los puntos de derivación del transformador. ^{[ cita necesaria ]}

Métodos de construcción

Varios métodos de construcción producen reglas Golomb asintóticamente óptimas .

Construcción Erdős-Turán

La siguiente construcción, debida a Paul Erdős y Pál Turán , produce una regla Golomb para cada primo impar p. ^[12]

${\displaystyle 2pk+(k^{2}\,{\bmod {\,}}p),k\in [0,p-1]}$

Gobernantes Golomb óptimos conocidos

La siguiente tabla contiene todos los gobernantes Golomb óptimos conocidos, excluyendo aquellos con marcas en el orden inverso. Los primeros cuatro son perfectos .

^ * El gobernante óptimo se habría conocido antes de esta fecha; esta fecha representa aquella fecha en la que se descubrió que era óptima (porque se demostró que todos los demás gobernantes no eran más pequeños). Por ejemplo, la regla que resultó ser óptima para el orden 26 se registró el 10 de octubre de 2007, pero no se supo que fuera óptima hasta que se agotaron todas las demás posibilidades el 24 de febrero de 2009.

Ver también

• conjunto de costas
• Computación voluntaria
  • BOINC
  • distribuido.net
• gobernante perfecto
• secuencia de Sidón
• gobernante escaso

Referencias

1. Sidón, S. (1932). "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen". Annalen Matemáticas . 106 : 536–539. doi :10.1007/BF01455900. S2CID  120087718.
2. Bekir, Ahmad; Golomb, Salomón W. (2007). "No hay más contraejemplos al teorema de S. Piccard". Transacciones IEEE sobre teoría de la información . 53 (8): 2864–2867. doi :10.1109/TIT.2007.899468. SEÑOR  2400501. S2CID  16689687..
3. "Reglas Golomb modulares y regulares".
4. "distributed.net - Anuncio de finalización de OGR-24". 2004-11-01.
5. "distributed.net - Anuncio de finalización de OGR-25". 2008-10-25.
6. "distributed.net - Anuncio de finalización de OGR-26". 2009-02-24.
7. "distributed.net - Anuncio de finalización de OGR-27". 2014-02-25.
8. "Finalización del proyecto OGR-28" . Consultado el 23 de noviembre de 2022 .
9. Meyer C, Papakonstantinou PA (febrero de 2009). "Sobre la complejidad de la construcción de gobernantes Golomb". Matemática Aplicada Discreta . 157 (4): 738–748. doi : 10.1016/j.dam.2008.07.006 .
10. Dimitromanolakis, Apóstolos. "Análisis de los problemas del gobernante Golomb y del conjunto de Sidón, y determinación de gobernantes Golomb grandes y casi óptimos" (PDF) . Consultado el 20 de diciembre de 2009 .
11. Drakakis, Konstantinos (2009). "Una revisión de los métodos de construcción disponibles para reglas Golomb". Avances en Matemáticas de las Comunicaciones . 3 (3): 235–250. doi :10.3934/amc.2009.3.235.
12. Erdős, Paul ; Turán, Pál (1941). "Sobre un problema de Sidón en teoría de números aditivos y algunos problemas relacionados". Revista de la Sociedad Matemática de Londres . 16 (4): 212–215. doi :10.1112/jlms/s1-16.4.212.
13. Robinson J, Bernstein A (enero de 1967). "Una clase de códigos binarios recurrentes con propagación de errores limitada". Transacciones IEEE sobre teoría de la información . 13 (1): 106–113. doi :10.1109/TIT.1967.1053951.
14. Babcock, Wallace C. (1953). «Interferencias de intermodulación en sistemas de radio» (extracto) . Revista técnica del sistema Bell . 32 : 63–73. doi :10.1002/j.1538-7305.1953.tb01422.x. Archivado (PDF) desde el original el 7 de julio de 2011 . Consultado el 14 de marzo de 2011 .
15. Colmillo, RJF; Sandrin, WA (1977). "Asignación de frecuencia portadora para repetidores no lineales". Revisión técnica de Comsat (resumen). 7 : 227. Código bibliográfico : 1977COMTR...7..227F.
16. Thompson, A. Richard; Morán, James M.; Swenson, George W. (2004). Interferometría y Síntesis en Radioastronomía (Segunda ed.). Wiley-VCH. pag. 142.ISBN​ 978-0471254928.
17. Arsac, J. (1955). "Transmissions des frecuencias espaciales dans les systemes recepteurs d'ondes courtes" [Transmisiones de frecuencias espaciales en sistemas receptores de onda corta]. Óptica Acta (en francés). 2 (112): 112-118. Código Bib : 1955AcOpt...2..112A. doi :10.1080/713821025.
18. Reglas, matrices y gracia Ed Pegg Jr. 15 de noviembre de 2004. Juegos de matemáticas.
19. Shearer, James B (19 de febrero de 1998). "Tabla de longitudes de los gobernantes Golomb más cortos conocidos". IBM . Archivado desde el original el 25 de junio de 2017.
20. "En busca de los gobernantes Mark Golomb óptimos 20 y 21 (archivado)". Mark Garry, David Vanderschel y otros. 26 de noviembre de 1998. Archivado desde el original el 6 de diciembre de 1998.

• Gardner, Martín (marzo de 1972). "Juegos matemáticos". Científico americano . 226 (3): 108–112. Código Bib : 1972SciAm.226c.108G. doi : 10.1038/scientificamerican0372-108.

enlaces externos

• Páginas de la regla Golomb de James B. Shearer
• distribuido.net: Proyecto OGR
• En busca de los gobernantes Mark Golomb óptimos 20, 21 y 22
• Gobernantes Golomb hasta una longitud de más de 200