En matemáticas , una regla de Golomb es un conjunto de marcas en posiciones enteras a lo largo de una regla de modo que no haya dos pares de marcas a la misma distancia. El número de marcas en la regla es su orden y la mayor distancia entre dos de sus marcas es su longitud . La traducción y el reflejo de una regla de Golomb se consideran triviales, por lo que la marca más pequeña se coloca habitualmente en 0 y la siguiente marca en el más pequeño de sus dos valores posibles. Las reglas 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 independientemente por Sidon (1932) [1] y Babcock (1953) . [2] 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 el mismo conjunto de distancias deben ser congruentes . Esto resultó ser falso para las reglas de seis puntos, pero cierto por lo demás. [3]
No es necesario que una regla de Golomb pueda medir todas las distancias hasta su longitud, pero si lo hace, se denomina regla de Golomb perfecta . Se ha demostrado que no existe una regla de Golomb perfecta para cinco o más marcos. [4] Una regla de Golomb es óptima si no existe una regla de Golomb más corta 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 distribuidas masivamente paralelas para los gobernantes de Golomb óptimos del orden 24 al 27, confirmando cada vez al presunto gobernante candidato. [5] [6] [7] [8] En febrero de 2014, distribution.net comenzó la búsqueda para encontrar reglas de Golomb óptimas ( OGR ) de orden 28.
Actualmente, se desconoce la complejidad de encontrar OGR de orden arbitrario n (donde n se da en unario). En el pasado se especuló que se trataba de un problema NP-difícil . [4] Se ha demostrado que los problemas relacionados con la construcción de Gobernantes Golomb son NP-hard, donde también se observa que ningún problema NP-completo conocido tiene un sabor similar al de encontrar Gobernantes Golomb. [9]
Definiciones
Gobernantes Golomb como conjuntos
Un conjunto de enteros dónde es un gobernante de Golomb si y solo si
El orden de tal gobernante Golomb esy su longitud es. La forma canónica tiene y si , . Esta forma se puede lograr mediante la traducción y la reflexión.
Gobernantes de Golomb como funciones
Una función inyectiva con y es un gobernante de Golomb si y solo si
- [11] : 236
El orden de tal gobernante Golomb esy su longitud es. La forma canónica tiene
- Si .
Optimalidad
Una regla de Golomb de orden m con longitud n puede ser óptima en cualquiera de dos aspectos: [11] : 237
- Puede ser óptimamente denso , exhibiendo m máximo para el valor específico de n ,
- Puede ser óptimamente corto , mostrando una n mínima para el valor específico de m .
El término general regla de Golomb óptima se utiliza para referirse al segundo tipo de optimalidad.
Aplicaciones prácticas
Teoría de la información y corrección de errores
Las reglas de 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 radiofrecuencias para reducir los efectos de la interferencia de intermodulación con aplicaciones tanto terrestres [14] como extraterrestres [15] .
Colocación de la antena de radio
Las reglas de Golomb se utilizan en el diseño de arreglos en fase de antenas de radio. Las antenas en una configuración de regla de Golomb [0, 1, 4, 6] a menudo se pueden ver en las torres AM o en los sitios celulares. En radioastronomía, las matrices de síntesis unidimensionales pueden tener las antenas en una configuración de regla de Golomb para obtener una redundancia mínima del muestreo del componente de Fourier. [16] [17]
Transformadores de corriente
Los transformadores de corriente de relación múltiple utilizan reglas Golomb para colocar puntos de derivación del transformador.
Métodos de construcción
Varios métodos de construcción producen reglas de 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 de Golomb por cada primo impar p. [12]
Gobernantes de Golomb óptimos conocidos
La siguiente tabla contiene todas las reglas de Golomb óptimas conocidas, excluidas aquellas con marcas en orden inverso. Los primeros cuatro son perfectos .
Pedido | Largo | Marcas | Probado [*] | Prueba descubierta por |
---|---|---|---|---|
1 | 0 | 0 | 1952 [18] | Wallace Babcock |
2 | 1 | 0 1 | 1952 [18] | Wallace Babcock |
3 | 3 | 0 1 3 | 1952 [18] | Wallace Babcock |
4 | 6 | 0 1 4 6 | 1952 [18] | Wallace Babcock |
5 | 11 | 0 1 4 9 11 0 2 7 8 11 | C. 1967 [19] | John P. Robinson y Arthur J. Bernstein |
6 | 17 | 0 1 4 10 12 17 0 1 4 10 15 17 0 1 8 11 13 17 0 1 8 12 14 17 | C. 1967 [19] | John P. Robinson y Arthur J. Bernstein |
7 | 25 | 0 1 4 10 18 23 25 0 1 7 11 20 23 25 0 1 11 16 19 23 25 0 2 3 10 16 21 25 0 2 7 13 21 22 25 | C. 1967 [19] | John P. Robinson y Arthur J. Bernstein |
8 | 34 | 0 1 4 9 15 22 32 34 | 1972 [19] | William Mixon |
9 | 44 | 0 1 5 12 25 27 35 41 44 | 1972 [19] | William Mixon |
10 | 55 | 0 1 6 10 23 26 34 41 53 55 | 1972 [19] | William Mixon |
11 | 72 | 0 1 4 13 28 33 47 54 64 70 72 0 1 9 19 24 31 52 56 58 69 72 | 1972 [19] | William Mixon |
12 | 85 | 0 2 6 24 29 40 43 55 68 75 76 85 | 1979 [19] | John P. Robinson |
13 | 106 | 0 2 5 25 37 43 59 70 85 89 98 99106 | 1981 [19] | John P. Robinson |
14 | 127 | 0 4 6 20 35 52 59 77 78 86 89 99122127 | 1985 [19] | James B. Shearer |
15 | 151 | 0 4 20 30 57 59 62 76100111123136144145151 | 1985 [19] | James B. Shearer |
dieciséis | 177 | 0 1 4 11 26 32 56 68 76115117134150163168177 | 1986 [19] | James B. Shearer |
17 | 199 | 0 5 7 17 52 56 67 80 81100122138159165168191199 | 1993 [19] | W. Olin Sibert |
18 | 216 | 0 2 10 22 53 56 82 83 89 98130148153167188192205216 | 1993 [19] | W. Olin Sibert |
19 | 246 | 0 1 6 25 32 72100108120130153169187190204231233242246 | 1994 [19] | Apostolos Dollas, William T. Rankin y David McCracken |
20 | 283 | 0 1 8 11 68 77 94116121156158179194208212228240253259283 | 1997? [19] | Mark Garry, David Vanderschel y col. (proyecto web) |
21 | 333 | 0 2 24 56 77 82 83 95129144179186195255265285293296310329333 | 8 de mayo de 1998 [20] | Mark Garry, David Vanderschel y col. (proyecto web) |
22 | 356 | 0 1 9 14 43 70106122124128159179204223253263270291330341353356 | 1999 [19] | Mark Garry, David Vanderschel y col. (proyecto web) |
23 | 372 | 0 3 7 17 61 66 91 99114159171 199200226235246277316329348350366372 | 1999 [19] | Mark Garry, David Vanderschel y col. (proyecto web) |
24 | 425 | 0 9 33 37 38 97122129140142152191205208252278286326332353368384403425 | 13 de octubre de 2004 [5] | distribuido.net |
25 | 480 | 0 12 29 39 72 91146157160161166191207214258290316354372394396431459467480 | 25 de octubre de 2008 [6] | distribuido.net |
26 | 492 | 0 1 33 83 104 110 124 163 185 200 203 249 251 258 314 318 343 356 386 430 440 456 464 475 487 492 | 24 de febrero de 2009 [7] | distribuido.net |
27 | 553 | 0 3 15 41 66 95 97106 142 152 220 221225 242295 330 338 354 382 388 402 415 486 504523546 553 | 19 de febrero de 2014 [8] | distribuido.net |
^ * La regla óptima se habría conocido antes de esta fecha; esta fecha representa la 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 la 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
- Matriz de costas
- Computación distribuída
- BOINC
- distribuido.net
- Gobernante perfecto
- Secuencia de Sidón
- Regla escasa
Referencias
- ^ Sidón, S. (1932). "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen". Mathematische Annalen . 106 : 536–539. doi : 10.1007 / BF01455900 . S2CID 120087718 .
- ^ Babcock, Wallace C. (1953). "Interferencia de intermodulación en sistemas de radio / frecuencia de ocurrencia y control por selección de canal". Revista técnica de Bell System . 31 : 63–73. doi : 10.1002 / j.1538-7305.1953.tb01422.x .
- ^ Bekir, Ahmad; Golomb, Solomon W. (2007). "No hay más contraejemplos para el 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 ..
- ^ a b "Reglas de Golomb modulares y regulares" .
- ^ a b "Distributed.net - Anuncio de finalización de OGR-24" . Consultado el 25 de febrero de 2014 .
- ^ a b "Distributed.net - Anuncio de finalización de OGR-25" . Consultado el 25 de febrero de 2014 .
- ^ a b "Distributed.net - Anuncio de finalización de OGR-26" . Consultado el 25 de febrero de 2014 .
- ^ a b "Distributed.net - Anuncio de finalización de OGR-27" . Consultado el 25 de febrero de 2014 .
- ^ Meyer C, Papakonstantinou PA (febrero de 2009). "Sobre la complejidad de construir Gobernantes Golomb". Matemáticas aplicadas discretas . 157 (4): 738–748. doi : 10.1016 / j.dam.2008.07.006 .
- ^ Dimitromanolakis, Apostolos. "Análisis de la regla de Golomb y los problemas del conjunto de Sidón, y determinación de las reglas de Golomb grandes y casi óptimas" (PDF) . Consultado el 20 de diciembre de 2009 .
- ^ a b Drakakis, Konstantinos (2009). "Una revisión de los métodos de construcción disponibles para los gobernantes de Golomb" . Avances en Matemática de las Comunicaciones . 3 (3): 235–250. doi : 10.3934 / amc.2009.3.235 .
- ^ a b Erdős, Paul ; Turán, Pál (1941). "Sobre un problema de Sidón en la 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 .
- ^ 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 .
- ^ "Interferencia de intermodulación en sistemas de radio" (extracto) . doi : 10.1002 / j.1538-7305.1953.tb01422.x . Consultado el 14 de marzo de 2011 .
- ^ Fang, 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 .
- ^ Thompson, A. Richard; Moran, James M .; Swenson, George W. (2004). Interferometría y síntesis en radioastronomía (Segunda ed.). Wiley-VCH. pag. 142 . ISBN 978-0471254928.
- ^ Arsac, J. (1955). "Transmisiones de frecuencias espaciales en sistemas de recepción de ondas de cortesía" [Transmisiones de frecuencias espaciales en sistemas receptores de onda corta]. Optica Acta (en francés). 2 (112). doi : 10.1080 / 713821025 .
- ^ a b c d Reglas, matrices y elegancia Ed Pegg Jr. 15 de noviembre de 2004. Juegos de matemáticas.
- ^ a b c d e f g h i j k l m n o p q r "tabla de longitudes de las reglas más cortas conocidas" . IBM . Consultado el 28 de noviembre de 2013 .
- ^ "En busca de las reglas óptimas de 20 y 21 Mark Golomb (archivado)" . Mark Garry, David Vanderschel y col. Archivado desde el original el 6 de diciembre de 1998.
- Gardner, Martin (marzo de 1972). "Juegos matemáticos". Scientific American . 226 (3): 108-112. 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 óptimos de Mark Golomb 20, 21 y 22
- Gobernantes Golomb de hasta 200