Golomba gobernante
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 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 mayor distancia entre dos de sus marcas es su longitud. La traslación y la reflexión de una regla de 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. Las reglas de Golomb se pueden ver como un caso especial unidimensional de arreglos de Costas.
El gobernante Golomb recibió su nombre de Solomon W. Golomb y fue descubierto de forma independiente por Sidon (1932) y Babcock (1953). Sophie Piccard también publicó una investigación temprana sobre estos conjuntos, en 1939, enunciando como teorema la afirmación de que dos reglas de Golomb con el mismo conjunto de distancia deben ser congruentes. Esto resultó ser falso para las reglas de seis puntos, pero cierto por lo demás.
No existe ningún requisito de 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 Golomb perfecta para cinco o más marcas. Una regla Golomb es óptima si no existe una regla Golomb más corta del mismo orden. Crear reglas de Golomb es fácil, pero probar la regla (o reglas) de Golomb óptima para un orden específico es un gran desafío computacional.
Distributed.net ha completado búsquedas paralelas masivas distribuidas de gobernantes óptimos de Golomb de orden 24 a orden 28, confirmando cada vez al gobernante candidato sospechoso.
Actualmente, se desconoce la complejidad de encontrar reglas de Golomb óptimas (OGR) de orden arbitrario n (donde n se da en unario). En el pasado se especuló que se trata de un problema NP-difícil. Se demuestra que los problemas relacionados con la construcción de reglas de Golomb son NP-difíciles, donde también se observa que ningún problema NP-completo conocido tiene un sabor similar al de encontrar reglas de Golomb.
Definiciones
Reglas Golomb como conjuntos
Un conjunto de enteros A={}a1,a2,...,am}{displaystyle A={a_{1},a_{2},a_{m}} Donde <math alttext="{displaystyle a_{1}<a_{2}<...a1.a2.....am{displaystyle A_{1} Seleccionado...<img alt="{displaystyle a_{1}<a_{2}<... es un gobernante Golomb si y sólo si
- para todosi,j,k,l▪ ▪ {}1,2,...,m}tales queiل ل jykل ل l,ai− − aj=ak− − al⟺ ⟺ i=kyj=l.{displaystyle {text{for all }i,j,k,lin left{1,2,...,mright}{text{such that }}ineq j{text{ and } kneq l, a_{i}-a_{j}=a_{k}-a_{l} i=k{text{ and }j=l.}
El orden de tal gobernante Golomb es m{displaystyle m} y su longitud es am− − a1{displaystyle A_{m}-a_{1}. La forma canónica tiene a1=0{displaystyle a_{1}=0} y, si 2}" xmlns="http://www.w3.org/1998/Math/MathML">m■2{displaystyle m confianza2}2" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/44e4ce1c04edd8f9602e60f0ec4457b7ac12fcd4" style="vertical-align: -0.338ex; width:6.301ex; height:2.176ex;"/>, <math alttext="{displaystyle a_{2}-a_{1}a2− − a1.am− − am− − 1{displaystyle a_{2}-a_{1}<img alt="a_2 - a_1 . Tal forma se puede lograr mediante la traducción y la reflexión.
Reglas Golomb como funciones
Una función inyectable f:{}1,2,...,m}→ → {}0,1,...,n}{displaystyle f:left{1,2,...,mright}to left{0,1,...,nright}} con f()1)=0{displaystyle f(1)=0} y f()m)=n{displaystyle f(m)=n} es un gobernante Golomb si y sólo si
- para todosi,j,k,l▪ ▪ {}1,2,...,m}tales queiل ل jykل ل l,f()i)− − f()j)=f()k)− − f()l)⟺ ⟺ i=kyj=l.{displaystyle {text{for all }i,j,k,linleft{1,2,...,mright}{text{such that }}ineq j{text{ and }kneq l,f(i)-f(j)=f(k)-f(l)iff i=k{textl}j}j}j}
El orden de tal gobernante Golomb es m{displaystyle m} y su longitud es n{displaystyle n}. La forma canónica tiene
- <math alttext="{displaystyle f(2)f()2).f()m)− − f()m− − 1){displaystyle f(2)(m)-f(m-1)}<img alt="f(2) si 2}" xmlns="http://www.w3.org/1998/Math/MathML">m■2{displaystyle m confianza2}2" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/44e4ce1c04edd8f9602e60f0ec4457b7ac12fcd4" style="vertical-align: -0.338ex; width:6.301ex; height:2.176ex;"/>.
Optimidad
Una regla Golomb de orden m con longitud n puede ser óptima en cualquiera de dos aspectos:
- Puede ser óptimamente densa, exhibiendo maximal m para el valor específico n,
- Puede ser óptimamente corto, exhibiendo mínimo n para el valor específico m.
El término general regla de Golomb óptima se utiliza para referirse al segundo tipo de optimización.
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.
Selección de frecuencia de radio
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 como extraterrestres.
Ubicación de la antena de radio
Las reglas de 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.
Transformadores de corriente
Los transformadores de corriente de relación múltiple utilizan reglas Golomb para colocar los 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 para cada primo impar p.
- 2pk+()k2modp),k▪ ▪ [0,p− − 1]{displaystyle 2pk+(k^{2},{bmod {,}p),kin [0,p-1]}
Gobernantes Golomb óptimos conocidos
La siguiente tabla contiene todas las reglas Golomb óptimas conocidas, excluyendo aquellas con marcas en el orden inverso. Los primeros cuatro son perfectos.
Orden | Duración | Marcas | Probada | Prueba descubierta por |
---|---|---|---|---|
1 | 0 | 0 | 1952 | Wallace Babcock |
2 | 1 | 0 1 | 1952 | Wallace Babcock |
3 | 3 | 0 1 3 | 1952 | Wallace Babcock |
4 | 6 | 0 1 4 6 | 1952 | Wallace Babcock |
5 | 11 | 0 1 4 9 11 0 2 7 8 11 | c. 1967 | 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 | 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 | John P. Robinson y Arthur J. Bernstein |
8 | 34 | 0 1 4 9 15 22 32 34 | 1972 | William Mixon |
9 | 44 | 1 5 12 25 27 35 41 44 | 1972 | William Mixon |
10 | 55 | 1 6 10 23 26 34 41 53 55 | 1972 | William Mixon |
11 | 72 | 1 4 13 28 33 47 54 64 70 72 1 9 19 24 31 52 56 58 69 72 | 1972 | William Mixon |
12 | 85 | 0 2 6 24 29 40 43 55 68 75 76 85 | 1979 | John P. Robinson |
13 | 106 | 0 2 5 25 37 43 59 70 85 89 98 99 106 | 1981 | John P. Robinson |
14 | 127 | 0 4 6 20 35 52 59 77 78 86 89 99 122 127 | 1985 | James B. Shearer |
15 | 151 | 0 4 20 30 57 59 62 76 100 111 123 136 144 145 151 | 1985 | James B. Shearer |
16 | 177 | 0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177 | 1986 | James B. Shearer |
17 | 199 | 0 5 7 17 52 56 67 80 81 100 122 138 159 165 191 199 | 1993 | W. Olin Sibert |
18 | 216 | 0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216 | 1993 | W. Olin Sibert |
19 | 246 | 0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246 | 1994 | Apostolos Dollas, William T. Rankin y David McCracken |
20 | 283 | 0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283 | ¿1997? | Mark Garry, David Vanderschel et al. (proyectoweb) |
21 | 333 | 0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333 | 8 de mayo de 1998 | Mark Garry, David Vanderschel et al. (proyectoweb) |
22 | 356 | 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356 | 1999 | Mark Garry, David Vanderschel et al. (proyectoweb) |
23 | 372 | 0 3 7 17 61 66 91 99 114 159 171 199 200 226 235 246 277 316 329 348 350 366 372 | 1999 | Mark Garry, David Vanderschel et al. (proyectoweb) |
24 | 425 | 0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403 425 | 13 de octubre de 2004 | distributed.net |
25 | 480 | 0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480 | 25 de octubre de 2008 | distributed.net |
26 | 492 | 0 1 33 83 104 110 124 163 185 200 203 249 251 258 314 343 356 386 430 440 456 464 475 487 492 | 24 de febrero de 2009 | distributed.net |
27 | 553 | 0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 388 402 415 486 504 523 546 553 | 19 de febrero de 2014 | distributed.net |
28 | 585 | 0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 388 402 415 486 504 523 546 553 585 | 23 de noviembre de 2022 | distributed.net |
^ * La regla óptima se habría conocido antes de esta fecha; esta fecha representa la fecha en 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.
Contenido relacionado
Modelo lineal
Análisis de Fourier
Dispersor