Regla de Golomb

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.

* 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}$

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}$. 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)$ 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

Referencias

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

Véase también

• Postulados de Golomb

Enlaces externos

• 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/