Regla de Golomb

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 que estén a la misma distancia entre sí. El número de marcas en la regla es su orden y la distancia más grande 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 coloca habitualmente en 0 y la siguiente marca en el menor de sus dos valores posibles. Las reglas de Golomb pueden verse como un caso especial unidimensional de matrices de Costas .

La regla de Golomb debe su nombre a Solomon W. Golomb y fue descubierta independientemente por Sidon (1932) ^[1] 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 distancias deben ser congruentes . Esto resultó ser falso para las reglas de seis puntos, pero cierto en otros casos. ^[2]

No existe ningún requisito que exija 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 marcas. ^[3] 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 difícil.

Distributed.net ha completado búsquedas masivas distribuidas y paralelas de reglas de Golomb óptimas de orden 24 a orden 28, confirmando cada vez al candidato candidato sospechoso. ^{[4] [5] [6] [7] [8]}

Actualmente, se desconoce la complejidad de encontrar reglas de Golomb óptimas (OGR) de orden arbitrario n (donde n se da en unario). ^{[ aclaración necesaria ]} En el pasado hubo cierta especulación de que es un problema NP-difícil . ^[3] Se ha demostrado 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 a la búsqueda de reglas de Golomb. ^[9]

Un conjunto de números enteros donde es una regla de Golomb si y solo si${\displaystyle A=\{a_{1},a_{2},...,a_{m}\}}$${\displaystyle a_{1}<a_{2}<...<a_{m}}$

${\displaystyle {\text{para todos }}i,j,k,l\in \left\{1,2,...,m\right\}{\text{tales que }}i\neq j{\text{ y }}k\neq l,\ a_{i}-a_{j}=a_{k}-a_{l}\iff i=k{\text{ y }}j=l.}$^[10]

El orden de una regla de Golomb de este tipo es y su longitud es . La forma canónica tiene y, si , . Esta forma se puede lograr mediante la traducción y la reflexión.${\estilo de visualización m}$$Estilo de visualización a_{m}-a_{1}}$$estilo de visualización a_{1}=0}$${\displaystyle m>2}$${\displaystyle a_{2}-a_{1}<a_{m}-a_{m-1}}$

Una función inyectiva con y es una regla de Golomb si y solo si${\displaystyle f:\left\{1,2,...,m\right\}\to \left\{0,1,...,n\right\}}$${\displaystyle f(1)=0}$${\displaystyle f(m)=n}$

${\displaystyle {\text{for all }}i,j,k,l\in \left\{1,2,...,m\right\}{\text{such that }}i\neq j{\text{ and }}k\neq l,f(i)-f(j)=f(k)-f(l)\iff i=k{\text{ and }}j=l.}$^{[11] : 236}

El orden de una regla de Golomb de este tipo es y su longitud es . La forma canónica tiene${\displaystyle m}$${\displaystyle n}$

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

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 , exhibiendo un n mínimo para el valor específico de m .

El término general "regla de Golomb óptima" se utiliza para referirse al segundo tipo de optimalidad.

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]

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 terrestres ^[14] y extraterrestres ^[15] .

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. ^{[16] [17]}

Los transformadores de corriente de múltiples relaciones utilizan reglas de Golomb para ubicar los puntos de toma del transformador. ^{[ cita requerida ]}

Varios métodos de construcción producen reglas de Golomb asintóticamente óptimas .

La siguiente construcción, debida a Paul Erdős y Pál Turán , produce una regla Golomb para cada primo impar p. ^[12]

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

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

^ * 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 todas las demás reglas 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 se agotaron todas las demás posibilidades el 24 de febrero de 2009.

• Matriz de Costas
• Computación voluntaria
  • BOINC
  • distribuido.net
• Regla perfecta
• Secuencia de Sidón
• Regla dispersa

• Gardner, Martin (marzo de 1972). «Juegos matemáticos». Scientific American . 226 (3): 108–112. Código Bibliográfico :1972SciAm.226c.108G. doi :10.1038/scientificamerican0372-108.

• Páginas de la regla de Golomb de James B. Shearer
• distributed.net: Proyecto OGR
• En busca de las reglas óptimas de Mark Golomb 20, 21 y 22
• Reglas de Golomb con una longitud de hasta más de 200