Règle de Golomb - Golomb ruler

Règle de Golomb d'ordre 4 et de longueur 6. Cette règle est à la fois optimale et parfaite .

Les règles de Golomb circulaires parfaites (également appelées ensembles de différences) avec l'ordre spécifié. (Cet aperçu doit afficher plusieurs cercles concentriques. Sinon, cliquez pour afficher une version plus grande.)

En mathématiques , une règle de Golomb est un ensemble de marques à des positions entières le long d'une règle de telle sorte qu'aucune paire de marques ne soit à la même distance. Le nombre de marques sur la règle est son ordre , et la plus grande distance entre deux de ses marques est sa longueur . La traduction et la réflexion d'une règle de Golomb sont considérées comme triviales, de sorte que la plus petite marque est généralement mise à 0 et la marque suivante à la plus petite de ses deux valeurs possibles. Les règles de Golomb peuvent être considérées comme un cas particulier unidimensionnel des tableaux de Costas .

Le souverain de Golomb a été nommé pour Solomon W. Golomb et découvert indépendamment par Sidon (1932) et Babcock (1953) . Sophie Piccard a également publié les premières recherches sur ces ensembles, en 1939, énonçant comme théorème l'affirmation selon laquelle deux règles de Golomb avec le même ensemble de distance doivent être congruentes . Cela s'est avéré faux pour les règles à six points, mais vrai dans le cas contraire.

Il n'est pas nécessaire qu'une règle de Golomb soit capable de mesurer toutes les distances jusqu'à sa longueur, mais si c'est le cas, on l'appelle une règle de Golomb parfaite . Il a été prouvé qu'aucune règle de Golomb parfaite n'existe pour cinq marques ou plus. Une règle de Golomb est optimale s'il n'existe pas de règle de Golomb plus courte du même ordre. Créer des règles de Golomb est facile, mais prouver la ou les règles de Golomb optimales pour un ordre spécifié est très difficile en termes de calcul.

Distributed.net a effectué des recherches massivement parallèles distribuées pour les règles optimales de Golomb de l'ordre-24 à l'ordre-27, confirmant à chaque fois la règle candidate suspectée. En février 2014, distribué.net a commencé la recherche pour trouver les règles de Golomb optimales ( OGR ) d'ordre-28.

Actuellement, la complexité de trouver des OGR d'ordre arbitraire n (où n est donné en unaire) est inconnue. Dans le passé, il y avait des spéculations selon lesquelles il s'agissait d'un problème NP-difficile . Il est prouvé que les problèmes liés à la construction des règles de Golomb sont NP-difficiles, où il est également noté qu'aucun problème connu NP-complet n'a la même saveur que la recherche de règles de Golomb.

Définitions

Règles de Golomb en tant qu'ensembles

Un ensemble d'entiers où est une règle de Golomb si et seulement si ${\displaystyle A=\{a_{1},a_{2},...,a_{m}\}}$${\displaystyle a_{1}<a_{2}<...<a_{m}}$

${\displaystyle {\text{for all }}i,j,k,l\in \left\{1,2,...,m\right\}{\text{tel que }}i\neq j{ \text{ et }}k\neq l,\ a_{i}-a_{j}=a_{k}-a_{l}\iff i=k{\text{ et }}j=l.}$

L' ordre d'une telle règle de Golomb est et sa longueur est . La forme canonique a et, si , . Une telle forme peut être atteinte par la traduction et la réflexion. ${\style d'affichage m}$${\displaystyle a_{m}-a_{1}}$${\style d'affichage a_{1}=0}$${\style d'affichage m>2}$${\displaystyle a_{2}-a_{1}<a_{m}-a_{m-1}}$

Les règles de Golomb en tant que fonctions

Une fonction injective avec et est une règle de Golomb si et seulement si ${\displaystyle f:\left\{1,2,...,m\right\}\to \left\{0,1,...,n\right\}}$${\style d'affichage f(1)=0}$${\style d'affichage f(m)=n}$

${\displaystyle {\text{for all }}i,j,k,l\in \left\{1,2,...,m\right\}{\text{tel que }}i\neq j{ \text{ et }}k\neq l,f(i)-f(j)=f(k)-f(l)\iff i=k{\text{ et }}j=l.}$

L' ordre d'une telle règle de Golomb est et sa longueur est . La forme canonique a ${\style d'affichage m}$${\style d'affichage n}$

${\style d'affichage f(2)<f(m)-f(m-1)}$si .${\style d'affichage m>2}$

Optimalité

Une règle de Golomb d'ordre m de longueur n peut être optimale à deux égards :

• Il peut être de densité optimale , présentant un m maximal pour la valeur spécifique de n ,
• Il peut être court de manière optimale , présentant un n minimal pour la valeur spécifique de m .

Le terme général règle de Golomb optimale est utilisé pour désigner le deuxième type d'optimalité.

Applications pratiques

Exemple d'une salle de conférence avec les proportions d'une règle de Golomb [0, 2, 7, 8, 11], la rendant configurable à 10 tailles différentes.

Théorie de l'information et correction d'erreurs

Les règles de Golomb sont utilisées dans la théorie de l'information liée aux codes de correction d'erreurs .

Sélection de la fréquence radio

Les règles de Golomb sont utilisées dans la sélection des fréquences radio pour réduire les effets des interférences d'intermodulation avec les applications terrestres et extraterrestres .

Emplacement de l'antenne radio

Les règles de Golomb sont utilisées dans la conception de réseaux phasés d'antennes radio. Des antennes dans une configuration de règle de Golomb [0,1,4,6] peuvent souvent être vues sur les tours AM ou les sites cellulaires. En radioastronomie, les réseaux de synthèse unidimensionnels peuvent avoir les antennes dans une configuration de règle de Golomb afin d'obtenir une redondance minimale de l'échantillonnage de la composante de Fourier.

Transformateurs de courant

Les transformateurs de courant multi-rapports utilisent des règles de Golomb pour placer les points de prise du transformateur.

Méthodes de construction

Un certain nombre de méthodes de construction produisent des règles de Golomb asymptotiquement optimales .

Construction Erdős–Turán

La construction suivante, due à Paul Erdős et Pál Turán , produit une règle de Golomb pour chaque nombre premier impair p.

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

Règles de Golomb optimales connues

Le tableau suivant contient toutes les règles de Golomb optimales connues, à l'exception de celles avec des marques dans l'ordre inverse. Les quatre premiers sont parfaits .

^{^ *} La règle optimale aurait été connue avant cette date ; cette date représente la date à laquelle il a été découvert qu'elle était optimale (car il a été prouvé que toutes les autres règles n'étaient pas plus petites). Par exemple, la règle qui s'est avérée optimale pour l'ordre 26 a été enregistrée le 10 octobre 2007, mais elle n'était pas connue pour être optimale jusqu'à ce que toutes les autres possibilités aient été épuisées le 24 février 2009.

Voir également

• Tableau Costas
• Informatique distribuée
  • BOINC
  • distribué.net
• Règle parfaite
• Séquence de Sidon
• Règle clairsemée

Les références

• Gardner, Martin (mars 1972). "Jeux mathématiques". Scientifique américain . 226 (3) : 108-112. doi : 10.1038/scientificamerican0372-108 .

Liens externes

• Les pages de la règle Golomb de James B. Shearer
• distribué.net : Projet OGR
• À la recherche des règles optimales de Mark Golomb 20, 21 et 22
• Règles de Golomb jusqu'à une longueur de plus de 200