Regla de Golomb

[0, 1, 4, 6] Regla de Golomb de orden 4 y longitud 6. Esta regla es tanto óptima como perfecta.

Ejemplo de una sala de conferencias con proporciones de una regla de Golomb de [0, 2, 7, 8, 11], siendo configurable en 10 tamaños diferentes.[1]​

En matemática, una regla de Golomb es una serie de marcas en posiciones enteras entre sí a lo largo de una regla imaginaria de tal forma que ninguna de las marcas tienen entre sí distancias iguales.

La regla de Golomb fue nombrada por el matemático e ingeniero estadounidense Solomon W. Golomb (n. 1932) y fue descubierta independientemente por Sidon (1932)[2]​ y Babcock (1953).[3]​

Uno de los resultados prácticos de las reglas de Golomb es el diseño de radio antenas múltiples por desfase de onda en configuraciones de radiotelescopios.

Existen dos tipos de reglas de Golomb, unas perfectas u óptimas y otras aproximadas.

Las perfectas son la [0,1], [0,1,3] y [0,1,4,6] que son los números más cortos para 2, 3 y 4 marcas respectivamente.

Distributed.net ha realizado una búsqueda masiva en paralelo de reglas de 24 marcas:

[9, 24, 4, 1, 59, 25, 7, 11, 2, 10, 39, 14, 3, 44, 26, 8, 40, 6, 21, 15, 16, 19, 22]

La búsqueda de reglas de 28 marcas está de momento en desarrollo.

Reglas de Golomb óptimas conocidas

La siguiente tabla contiene todas las reglas de Golomb óptimas conocidas, excluyendo aquellas con marcas en el orden inverso. Las primeras cuatro son perfectas.

orden	longitud	marcas	descubrimiento	descubridor
1	0	0
2	1	0 1
3	3	0 1 3
4	6	0 1 4 6
5	11	0 1 4 9 11 0 2 7 8 11 0 3 4 9 11	1967?[4]​	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	1967?[4]​	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	1967?[4]​	John P. Robinson y Arthur J. Bernstein
8	34	0 1 4 9 15 22 32 34	1972[4]​	William Mixon
9	44	0 1 5 12 25 27 35 41 44	1972[4]​	William Mixon
10	55	0 1 6 10 23 26 34 41 53 55	1972[4]​	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[4]​	William Mixon
12	85	0 2 6 24 29 40 43 55 68 75 76 85	1979[4]​	John P. Robinson
13	106	0 2 5 25 37 43 59 70 85 89 98 99 106	1981[4]​	John P. Robinson
14	127	0 4 6 20 35 52 59 77 78 86 89 99 122 127	1985[4]​	James B. Shearer
15	151	0 4 20 30 57 59 62 76 100 111 123 136 144 145 151	1985[4]​	James B. Shearer
16	177	0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177	1986[4]​	James B. Shearer
17	199	0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199	1993[4]​	W. Olin Sibert
18	216	0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216	1993[4]​	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[4]​	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?[4]​	Mark Garry, David Vanderschel y otros (proyecto web)
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[5]​	Mark Garry, David Vanderschel y otros (proyecto web)
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[4]​	Mark Garry, David Vanderschel y otros (proyecto web)
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[4]​	Mark Garry, David Vanderschel and others (web project)
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[6]​	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[7]​	distributed.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[8]​	distributed.net
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	19 de febrero de 2014[9]​	distributed.net

* La regla óptima podría haber sido conocido antes de esta fecha; esta fecha representa la fecha en que se descubrió que era óptima (ya que todas las otras reglas se demostró que no eran más pequeñas). 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 era óptima hasta que todas las otras posibilidades se agotaron el 24 de febrero de 2009.[6]​[7]​[8]​[9]​

Reglas de Golomb como conjuntos

Un conjunto de enteros

${\displaystyle A=\{a_{1},a_{2},...,a_{m}\}\quad a_{1}<a_{2}<...<a_{m}}$

es una Regla de Golomb si y solo si

${\displaystyle \forall i,j,k,l\in \left\{1,2,...,m\right\},a_{i}-a_{j}=a_{k}-a_{l}\iff i=k\land j=l.}$[10]​

El orden de una Regla de Golomb es ${\displaystyle m}$ y su longitud es ${\displaystyle a_{m}-a_{1}}$. La forma canónica tiene la forma ${\displaystyle a_{1}=0}$ y, si ${\displaystyle m>2}$, ${\displaystyle a_{2}-a_{1}<a_{m}-a_{m-1}}$. Cualquier forma puede conseguirse mediante reflexión y traslación

Reglas de Golomb como funciones

Una Función inyectiva

${\displaystyle f:\left\{1,2,...,m\right\}\to \left\{0,1,...,n\right\}}$

con ${\displaystyle f(1)=0}$ and ${\displaystyle f(m)=n}$ es una Regla de Golomb si y sólo si

${\displaystyle \forall i,j,k,l\in \left\{1,2,...,m\right\},f(i)-f(j)=f(k)-f(l)\iff i=k\land j=l.}$[11]​: 236 

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

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

Optimización

Una Regla de Golomb de orden m con longitud n puede ser óptima en dos casos:[11]​: 237 

• Puede ser 'óptima en densidad', exhibiendo el máximo m para el valor específico de n
• Puede ser 'óptimamente corta', exhibiendo el mínimo n para un valor específico de m

El término general de una Regla de Golomb es utilizado para referirse al segundo tipo de optimización

Métodos de construcción

La siguiente construcción, expuesta por Paul Erdős y Pál Turán, produce una Regla de Golomb para cualquier número primo que sea impar:

p.[12]​

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

Notas

1. Erdős, Paul; Turán, Pál (1941). «On a problem of Sidon in additive number theory and some related problems». Journal of the London Mathematical Society 16 (4): 212-215. doi:10.1112/jlms/s1-16.4.212. 
2. S. Sidon, "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen", Mathematische Annalen 106 (1932), pp. 536–539 doi 10.1007/BF01455900
3. Wallace C. Babcock. "Intermodulation Interference in Radio Systems/Frequency of Occurrence and Control by Channel Selection", Bell System Technical Journal 31 (1953), pp. 63–73.
4. «table of lengths of shortest known rulers». IBM. Archivado desde el original el 16 de abril de 2018. Consultado el 28 de noviembre de 2013. 
5. «In Search Of The Optimal 20 & 21 Mark Golomb Rulers (archived)». Mark Garry, David Vanderschel, et al. Archivado desde el original el 6 de diciembre de 1998. Consultado el 28 de noviembre de 2013. 
6. «distributed.net - OGR-24 completion announcement». Consultado el 25 de febrero de 2014. 
7. «distributed.net - OGR-25 completion announcement». Consultado el 25 de febrero de 2014. 
8. «distributed.net - OGR-26 completion announcement». Consultado el 25 de febrero de 2014. 
9. «distributed.net - OGR-27 completion announcement». Consultado el 25 de febrero de 2014. 
10. Dimitromanolakis, Apostolos. Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers (PDF). Consultado el 20 de diciembre de 2009. 
11. Drakakis, Konstantinos (2009). «A Review Of The Available Construction Methods For Golomb Rulers». Advances in Mathematics of Communications 3 (3): 235-250. doi:10.3934/amc.2009.3.235. 
12. Erdős, Paul; Turán, Pál (1941). «On a problem of Sidon in additive number theory and some related problems». Journal of the London Mathematical Society 16 (4): 212-215. doi:10.1112/jlms/s1-16.4.212. 

Referencias

• Martin Gardner, "Mathematical games", Scientific American, March 1972, p. 108-112

Véase también

• Postulados de Golomb

Enlaces externos

• Esta obra contiene una traducción parcial derivada de «Golomb ruler» de Wikipedia en inglés, concretamente de esta versión del 24 de agosto de 2016, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.
• http://www.research.ibm.com/people/s/shearer/grule.html
• http://www.distributed.net/ogr/
• https://web.archive.org/web/19981203104221/http://members.aol.com/golomb20/

• Datos: Q1426478
• Multimedia: Golomb rulers / Q1426478