Golomba Gobernante

Una regla de Golomb en teoría de números  es un conjunto de números enteros no negativos dispuestos como divisiones en una regla imaginaria de tal manera que la distancia entre dos divisiones es única. En otras palabras, es imposible encontrar dos números a lo largo de toda la regla, cuya diferencia se repetiría dos veces [1] .

Reciben su nombre del matemático estadounidense Solomon Golomb [2] , aunque la primera mención de tales construcciones se puede encontrar en publicaciones anteriores de Sidon [3] y Babcock [4] .

Definiciones

El número de divisiones en la regla de Golomb se llama orden , y la distancia más grande entre sus dos divisiones se llama longitud . Por ejemplo, una regla con divisiones 0 1 4 9 11 es una regla de quinto orden de longitud 11. A veces, las reglas de Golomb se describen por las distancias entre divisiones adyacentes, y no por las coordenadas absolutas de las divisiones, por lo que la regla anterior sería parece 1-3-5-2. El número máximo de pares que se pueden formar a partir de divisiones de una regla de orden n es igual al número de combinaciones .

Las reglas obtenidas de una dada cambiando cada división por un número fijo, por ejemplo, 1 2 5 10 12, o enumerando las divisiones de la regla en orden inverso (reflejado), por ejemplo, 0 2 7 10 11, se consideran equivalente. Por lo tanto, en la representación canónica de la regla de Golomb, la división más pequeña corresponde a la coordenada cero, y la división que le sigue se ubica en la menor de las dos distancias posibles.

La Golomb Ruler no siempre es adecuada para medir todas las distancias enteras dentro de su longitud; sin embargo, si lo es, dicha regla se denomina perfecta ( English  Perfect Golomb Ruler  (inglés) , PGR). Los gobernantes perfectos existen solo para órdenes inferiores a cinco.

Una regla Golomb se llama óptima ( Ing.  Optimal Golomb Ruler  (inglés) , OGR) si no hay reglas más cortas del mismo orden. En otras palabras, una regla es óptima si, en la representación canónica, el valor de su última división es el mínimo posible.

La creación de una regla Golomb es relativamente simple, pero probar la optimización de una regla es un proceso computacional que requiere mucho tiempo. En la actualidad, se desconoce un método para obtener una regla de Golomb óptima de longitud arbitraria n , pero se cree que este problema es NP-difícil .

Gobernantes Golomb óptimos conocidos

Se conocen gobernantes de Golomb hasta el orden 150 [5] , pero la optimización se ha demostrado solo para los gobernantes de orden que no exceden los 27. La siguiente tabla contiene todos los gobernantes de Golomb conocidos hasta la fecha en la representación canónica para los cuales se ha demostrado la optimización.

Ordenar Longitud divisiones brechas
una 0 0 0
2 una 0 1 una
3 3 0 1 3 12
cuatro 6 0 1 4 6 1 3 2
5 once 0 1 4 9 11
0 2 7 8 11 		1 3 5 2
2 5 1 3
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 		1 3 6 2 5
1 3 6 5 2
1 7 3 2 4
1 7 4 2 3
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 		1 3 6 8 5 2
1 6 4 9 3 2
1 10 5 3 4 2
2 1 7 6 5 4
2 5 6 8 1 3
ocho 34 0 1 4 9 15 22 32 34 1 3 5 6 7 10 2
9 44 0 1 5 12 25 27 35 41 44
diez 55 0 1 6 10 23 26 34 41 53 55
once 72 0 1 4 13 28 33 47 54 64 70 72
0 1 9 19 24 31 52 56 58 69 72
12 85 0 2 6 24 29 40 43 55 68 75 76 85
13 106 0 2 5 25 37 43 59 70 85 89 98 99 106
catorce 127 0 4 6 20 35 52 59 77 78 86 89 99 122 127
quince 151 0 4 20 30 57 59 62 76 100 111 123 136 144 145 151
dieciséis 177 0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177
17 199 0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199
Dieciocho 216 0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216
19 246 0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246
veinte 283 0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283
21 333 0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333
22 356 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356
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
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
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
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
27 553 0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553

Encontrar reglas Golomb óptimas

La regla óptima de Golomb de orden 24 fue hallada en 1967 por John P. Robinson y Arthur J. Bernstein . Sin embargo, su optimidad fue probada recién el 1 de noviembre de 2004 por los esfuerzos combinados de más de 40 mil personas de todo el mundo durante 4 años y 110 días como parte del proyecto de computación distribuida OGR-24 [6] de la no- organización lucrativa distribuida.net .

La regla Golomb óptima del orden 25 fue encontrada en 1984 por Atkinson ( MD Atkinson ) y Hassenklover ( A. Hassenklover ). La prueba de su optimalidad se completó en 3006 días el 24 de octubre de 2008 como parte del proyecto OGR-25 [7] .

La prueba de optimización de la regla Golomb de orden 26 se completó en 24 días el 24 de febrero de 2009 como parte del proyecto OGR-26 [8] .

La prueba de optimización del gobernante Golomb de orden 27 se completó en 1822 días el 19 de febrero de 2014 como parte del proyecto OGR-27 [9] .

La prueba de la optimización del gobernante Golomb del orden 28 es el proyecto OGR-28 , que está completo en un 87,87 % al 4 de septiembre de 2021 [10] .

El proyecto de computación distribuida yoyo@home también está buscando reglas Golomb óptimas .

Aplicaciones

Una de las aplicaciones prácticas de la regla de Golomb es su uso en conjuntos de antenas en fase  , por ejemplo, en radiotelescopios . Las antenas con la configuración [0 1 4 6] se pueden encontrar en estaciones base celulares CDMA .

Notas

  1. ↑ Introducción a Golomb Gobernantes por Mark Garry
  2. ↑ Solomon W. Golomb (enlace no disponible) . Fecha de acceso: 28 de julio de 2007. Archivado desde el original el 28 de julio de 2007. 
  3. ↑ S. Sidón. Ein Satzuber trigonomietrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen  (alemán)  // Mathematische Annalen  : magazin. - 1932. - Bd. 106 . - S. 536-539 .
  4. ↑ Wallace C. Babcock. Interferencia de intermodulación en sistemas de radio/frecuencia de ocurrencia y control por selección de canal  //  Boletín técnico del sistema Bell : diario. - 1953. - vol. 31 . - Pág. 63-73 .
  5. ↑ Mesa de regla Golomb . Archivado el 16 de abril de 2018 en Wayback Machine . 
  6. ↑ Estadísticas del proyecto OGR-24 . Consultado el 22 de diciembre de 2007. Archivado desde el original el 17 de febrero de 2016.
  7. ↑ Estadísticas del proyecto OGR-25 . Consultado el 22 de diciembre de 2007. Archivado desde el original el 17 de octubre de 2013.
  8. ↑ Estadísticas del proyecto OGR-26 . Consultado el 1 de noviembre de 2008. Archivado desde el original el 29 de diciembre de 2014.
  9. ↑ Estadísticas del proyecto OGR-27 . Fecha de acceso: 8 de enero de 2010. Archivado desde el original el 9 de enero de 2014.
  10. ↑ Estadísticas del proyecto OGR-28 . Consultado el 26 de febrero de 2014. Archivado desde el original el 21 de julio de 2015.

Véase también

Enlaces