règle de Golomb

Imaginez une règle qui ne porte que quatre marques, aux positions 0, 1, 4 et 6. En choisissant deux marques, on mesure successivement toutes les longueurs entières de 1 à 6, sans obtenir deux fois la même distance. Le dessin de cette règle rend ce jeu d'écarts visible.

Une règle de Golomb repose sur cette absence de répétition. Les graduations n'ont pas besoin d'être régulièrement espacées. Ce sont les distances entre toutes les paires de marques, et pas seulement entre deux marques voisines, qui doivent être différentes.

Une règle de Golomb à n marques est une suite d'entiers que l'on range dans l'ordre strictement croissant. On note ces positions a₁, a₂, …, a_n. Pour chaque paire d'indices où i est inférieur à j, la distance positive entre les deux marques vaut a_j − a_i. La condition déterminante est que deux paires différentes ne donnent jamais la même distance.

Ajouter le même entier à toutes les marques ne change aucune différence. On peut donc choisir la première position égale à 0. La longueur de la règle est alors sa dernière position a_n. Une règle est dite optimale pour n fixé si aucune autre règle de Golomb à n marques n'a une longueur plus petite. Être une règle de Golomb et être optimale sont ainsi deux propriétés distinctes.

L'exemple conducteur possède les marques 0, 1, 4 et 6. Ses six distances sont 1, 2, 3, 4, 5 et 6, chacune une seule fois. Il est donc valide et atteint la borne minimale imposée par le nombre de paires pour quatre marques. Le problème canonique consiste précisément à minimiser a_n lorsque n est fixé. D'après la définition source, cette recherche devient très difficile dès que n dépasse 15. La notion, nommée d'après le mathématicien américain Solomon W. Golomb, intervient notamment en radiocommunications, en théorie du codage et en radioastronomie.

Soient n positions entières strictement croissantes, notées a₁, a₂, …, a_n. Pour décider si elles forment une règle de Golomb, on calcule la différence positive associée à chacune des paires de marques. Le critère complet est :

Autrement dit, l'égalité de deux distances oblige les deux paires de marques à être la même paire. Après avoir fixé a₁ = 0, le problème d'optimisation cherche parmi les règles valides celle dont la dernière marque a_n est la plus petite.

Le critère porte sur un nombre fini de marques placées à des positions entières distinctes. Après les avoir rangées, il faut examiner chaque paire, et non seulement les écarts entre marques consécutives. On obtient n(n − 1)/2 distances positives ; elles doivent toutes avoir des valeurs différentes. Une translation commune des positions est permise, car elle conserve ces différences.

La suite 0, 1, 3, 4 fournit un contre-cas concret. Les marques 0 et 1 sont distantes de 1, tout comme les marques 3 et 4. La répétition suffit à invalider la règle, même si les quatre positions sont distinctes. Il faut alors déplacer au moins une marque, puis recalculer l'ensemble des distances. Déplacer la marque 3 en 6 donne, après rangement, 0, 1, 4 et 6, qui passe le contrôle complet.

Testons les quatre marques 0, 1, 4 et 6. La figure représente leur position sur une même règle et aligne les six longueurs obtenues, de la plus courte à la plus longue.

Données.
Nombre de marques : n = 4.
Positions : 0, 1, 4 et 6.
Nombre de paires à contrôler : 4 × 3 / 2 = 6.

Étape 1. Depuis la marque 0, les écarts vers 1, 4 et 6 valent respectivement 1, 4 et 6.

Étape 2. Depuis la marque 1, les écarts vers 4 et 6 valent 3 et 5.

Étape 3. La dernière paire, formée par 4 et 6, fournit l'écart 2. L'ensemble obtenu est donc {1, 2, 3, 4, 5, 6}.

Résultat et contrôle. Les six distances sont distinctes : 0, 1, 4, 6 est bien une règle de Golomb. Sa longueur vaut 6. Or six distances entières positives distinctes exigent une plus grande distance d'au moins 6 ; la règle atteint cette borne et est donc optimale pour quatre marques.

En radiocommunications, la règle sert de modèle lorsqu'on veut choisir des positions ou des décalages dont aucune séparation ne se répète. Une progression régulière est plus simple, mais elle répète de nombreux écarts ; on préfère une disposition de Golomb lorsque cette répétition est précisément le défaut à éviter.

En radioastronomie, le même principe guide la comparaison de positions d'observation : chaque paire doit fournir un écart différent. Si plusieurs paires ayant le même écart sont au contraire recherchées, ce critère n'est pas adapté.

En théorie du codage, on exploite la collection de différences distinctes comme structure combinatoire. Le geste pratique reste le même : proposer des entiers, calculer toutes les différences, éliminer toute répétition, puis comparer la longueur des solutions valides si l'objectif est l'optimisation.

Une règle de Golomb n'est pas une règle graduée ordinaire. Sur une graduation régulière 0, 1, 2, 3, la distance 1 apparaît entre trois paires voisines ; cette répétition est utile pour mesurer, mais elle enfreint le critère de Golomb. Avec 0, 1, 4, 6, les graduations sont irrégulières et chacune des six distances n'apparaît qu'une fois.

Contrôler seulement les voisins. Des écarts consécutifs différents ne suffisent pas. Pour 0, 1, 3, 6, les écarts voisins valent 1, 2 et 3, mais la distance 3 apparaît aussi entre 0 et 3. Il faut calculer les six paires.

Oublier la normalisation. Les marques 5, 6, 9 et 11 ont exactement les mêmes distances que 0, 1, 4 et 6. Avant de comparer des longueurs, on translate donc la première marque en 0 ; sinon, la valeur de la dernière marque ne mesure pas seule l'étendue de la règle.

Confondre validité et meilleure longueur. Avec n marques, il existe n(n − 1)/2 distances positives distinctes. Une règle normalisée doit donc avoir une longueur au moins égale à ce nombre. Atteindre cette borne prouve l'optimalité ; ne pas l'atteindre ne prouve pas qu'une règle plus courte existe.

Sous-estimer la recherche. Vérifier une proposition et démontrer qu'aucune proposition plus courte n'existe sont deux tâches différentes. La source signale que le problème canonique devient très difficile dès que n dépasse 15 ; une recherche incomplète ne suffit donc pas à proclamer une solution optimale.

Le comptage des paires donne une première borne générale. Une règle à n marques produit n(n − 1)/2 distances entières positives distinctes. Si sa longueur est L, toutes ces distances appartiennent à l'ensemble {1, 2, …, L} ; on doit donc avoir :

Pour n = 4, cette borne vaut 6 et la règle 0, 1, 4, 6 l'atteint. Ses distances remplissent sans lacune tout l'intervalle entier de 1 à 6. Plus généralement, cette borne permet d'écarter immédiatement toute longueur trop courte, mais elle ne construit pas les marques et ne garantit pas à elle seule qu'une règle atteignant l'égalité existe.