Ronald Hugh Barker [1915 - 2015] était un physicien et ingénieur irlandais spécialisé dans la transmission des signaux.

En 1953, ses travaux sur des problèmes de synchronisation digitale l’ont conduit à poser une question mathématique d’apparence simple mais qui, plus de 70 ans après, résiste encore et toujours aux efforts de résolution des mathématiciens.

C’est ainsi que sont nées les suites de Barker, des suites finies de $+1$ et $-1$ satisfaisant certaines conditions décrites plus bas. Grâce à leurs propriétés mathématiques, les suites de Barker sont largement utilisées de nos jours dans les radars, en téléphonie mobile, pour le WiFi [1], le GPS etc. Voir l’article de Wikipedia à ce sujet.

Suites binaires

On appellera ici suite binaire toute suite finie de $+1$ et $-1$. Par exemple,
\[ S = (+1,+1,-1,+1,-1). \]
Pour alléger la notation, on ne retiendra que les signes $+$ et $-$. L’exemple ci-dessus devient alors
\[ S = ++-+-. \]

Décalages

Une question importante sur une suite binaire $S$, tant en théorie qu’en pratique dans les applications, est la suivante : si l’on décale $S$ de quelques unités vers la droite, dans quelle mesure la suite décalée ressemble-t-elle à $S$ ?

Prenons par exemple
\[S=++-+--+.\]
Décalons $S$ de deux unités vers la droite :

\[ \begin{align*} & ++-+--\;+ \\ & \;\;\; \;\;\; ++-+--\;+. \end{align*} \]

Tronquons ces deux suites à leur partie commune, ici de longueur $5$ :
\[ \begin{align*} & -+--\;+ \\ & ++-+\;- \end{align*} \]
Ces suites se ressemblent-elles ? En l’occurrence, pas trop : en les comparant verticalement symbole par symbole, on trouve trois paires de signes distincts — colonnes $\color{red}{1}$, $\color{red}{4}$ et $\color{red}{5}$ — contre seulement deux paires de signes égaux — colonnes $\color{green}{2}$ et $\color{green}{3}$.
\[ \begin{align*} & \color{red}{-}\color{green}{+}\color{green}{-}\color{red}{-}\;\color{red}{+} \\ & \color{red}{+}\color{green}{+}\color{green}{-}\color{red}{+}\;\color{red}{-} \end{align*} \]

Coefficients d’auto-corrélation

Pour mesurer le niveau de ressemblance entre une suite binaire $S=(a_1,\dots,a_n)$ et ses suites décalées, on introduit les coefficients d’auto-corrélation de $S$ — plus précisément, la version dite apériodique. De quoi s’agit-il ?

• Le premier coefficient d’auto-corrélation de $S$, notée $c_1(S)$ ou simplement $c_1$, est défini ainsi :
  \[ c_1 = a_1a_2+a_2a_3+\cdots+a_{n-1}a_n. \]
  Recette : prendre tous les produits $a_ia_{i+1}$ de deux termes consécutifs de $S$ et faire la somme. Le nombre $c_1$ ainsi obtenu fournit, comme souhaité, une bonne mesure de ressemblance entre la suite $S$ et sa décalée d’une unité.

En effet, en comparant verticalement symbole par symbole les suites tronquées
\[ \begin{align*} & a_1,a_2,\dots,a_{n-1} \\ & a_2,a_3,\dots,a_{n}, \end{align*} \]
on voit que toute paire de signes égaux $a_i=a_{i+1}=+1$ ou $-1$ entraîne $a_ia_{i+1}=+1$. Donc, plus il y aura de telles paires, plus $c_1$ sera grand.

Dans l’autre sens, si ces suites sont très peu corrélées, on peut s’attendre à trouver à peu près autant de paires égales, donnant $a_ia_{i+1}=+1$, que de paires distinctes, donnant $a_ia_{i+1}=-1$ ; ce qui poussera $c_1$ à être proche de $0$.

• On définit de façon analogue le second coefficient d’auto-corrélation $c_2$ de $S$, à savoir
  \[ c_2 = a_1a_3+a_2a_4+\cdots+a_{n-2}a_n. \]
  Recette : prendre tous les produits $a_ia_{i+2}$ de deux termes de $S$ à distance $2$ et faire la somme.

• En toute généralité, le coefficient d’auto-corrélation $c_k$ est défini comme la somme de tous les produits $a_ia_{i+k}$ de termes de $S$ à distance $k$ l’un de l’autre.

• Les deux derniers coefficients d’auto-corrélation de $S$ sont
  \[ \begin{align*} c_{n-2} &= a_1a_{n-1}+a_2a_n, \\ c_{n-1} &= a_1a_{n}. \end{align*} \]

Résumé. Une suite binaire $S$ de longueur $n$ donne lieu à $n-1$ coefficients d’auto-corrélation, à savoir
\[ c_1,c_2,\dots,c_{n-1}. \]
Ces coefficients permettent de mesurer le niveau de ressemblance entre $S$ et ses suites décalées.

Suites de Barker

Informellement, une suite de Barker est une suite binaire aussi peu corrélée que possible avec ses suites décalées. Autrement dit, ses coefficients d’auto-corrélation sont aussi proches de $0$ que possible. Plus formellement :

Une suite de Barker est une suite binaire $S=(a_1,a_2,\dots,a_n)$ telle que tous ses coefficients d’auto-corrélation $c_1,c_2,\dots,c_{n-1}$ valent $0$, $1$ ou $-1$.

Notons que, pour une suite binaire $S=(a_1,a_2,\dots,a_n)$ quelconque, le dernier coefficient $c_{n-1}=a_{1}a_{n}$ vaut toujours $+1$ ou $-1$. Donc, pour ce coefficient, la condition de Barker est toujours satisfaite.

Par contre, l’avant-dernier coefficient $c_{n-2}=a_{1}a_{n-1}+a_{2}a_{n}$ peut valoir $-2$, $0$ ou $2$ en général. Mais pour une suite de Barker, on exige $c_{n-2}=0$.

Plus généralement, plus l’indice $k$ de décalage est petit, plus la condition de Barker est contraignante pour le coefficient de corrélation $c_k$.

Transformations élémentaires

Certaines transformations élémentaires préservent les suites de Barker. Présentons-les ici. Soit donc
\[ S=(a_1,a_2,\dots,a_n) \]
une suite binaire quelconque de longueur $n$.

• La première transformation, rev pour reverse, consiste à reproduire $S$ à l’envers :
  \[ \textbf{rev}(S) = (a_n,a_{n-1},\dots,a_1). \]

• La seconde transformation, neg pour negate, consiste à changer tous les signes de $S$ :
  \[ \textbf{neg}(S) = (-a_1,-a_2,\dots,-a_n). \]

• Enfin, la troisième transformation, alt pour alternate, consiste à changer alternativement un signe sur deux dans $S$, en l’occurrence pour tous les indices pairs :
  \[ \textbf{alt}(S) = (a_1,-a_2,a_3,\dots,(-1)^{n-1} a_n). \]
  Le terme général est $(-1)^{i-1}a_i$, qui vaut effectivement $a_i$ ou $-a_i$ suivant que $i$ est impair ou pair.

On laisse le soin aux lecteurs/lectrices de vérifier que ces transformations préservent, au signe près, les coefficients d’auto-corrélation de $S$. C’est facile pour les deux premières transformations ; pour la troisième, cela requiert un peu plus de dextérité.

Ces observations mènent directement au résultat suivant.

Proposition. Soit $S$ une suite de Barker de longueur $n$. Alors les suites $\textbf{rev}(S)$, $\textbf{neg}(S)$ et $\textbf{alt}(S)$ sont elles aussi des suites de Barker de longueur $n$.

Réduction

En combinant les transformations rev, neg et alt, on peut facilement démontrer le résultat suivant.

Proposition. S’il existe une suite de Barker de longueur $n \ge 2$, alors il existe une suite de Barker de même longueur $n$ et commençant par $++$.

L’intérêt de cette réduction est le suivant. Si l’on veut trouver toutes les suites de Barker de longueur $n \ge 2$ donnée, on peut restreindre la recherche aux suites binaires commençant par $++$. Car alors, en vertu de ce résultat, toutes les autres s’en déduisent par application des transformations rev, neg et alt.

Un calculateur d’auto-corrélations

Pour tester facilement de nombreux exemples, voici un petit calculateur interactif d’auto-corrélations de suites binaires, développé spécialement par Marc Monticelli pour cet article. Un grand merci à lui !

Par défaut, une suite binaire aléatoire de longueur $n=10$ s’affiche. Un clic sur une case change le signe de celle-ci. Les coefficients d’auto-corrélation $c_1,\dots,c_{n-1}$ de la suite sont alors automatiquement actualisés. C’est intéressant d’observer le changement induit sur ces coefficients par un seul petit changement de signe.

On dispose des contrôles suivants. Le curseur permet de varier la longueur $n$ entre $2$ et $16$. Un premier bouton, alea, permet à chaque clic d’afficher une nouvelle suite binaire aléatoire de longueur $n$. On dispose aussi d’un bouton pour chacune des opérations rev, neg et alt, permettant ainsi de visualiser leur effet sur les coefficients d’auto-corrélation. Et enfin, les quatre derniers boutons permettent d’afficher certaines suites binaires spécifiques.

Suites de Barker connues

$\bullet$ En longueur paire, on connaît des suites de Barker de longueur $2$, de longueur $4$ et... c’est tout ! On n’en connaît aucune autre. Voici celles commençant par $++$ :

\[ \begin{align*} 2 : & + + \\ 4 : & + + + - \\ & + + - + \end{align*} \]

$\bullet$ Il existe des suites de Barker de toute longueur impaire de $1$ à $13$, à l’exclusion de $9$. En longueur $1$, la suite $+$ est bien sûr de Barker. Voici la liste complète de celles de longueur impaire au moins $3$ et commençant par $++$ :

\[ \begin{align*} 3 : & + + \; - \\ 5 : & + + + - \; + \\ 7 : & + + + - - + \; - \\ 11 : & + + + - - - + - - + \; - \\ 13 : & + + + + + - - + + - + - \; + \end{align*} \]

Que les lecteurs/lectrices s’amusent à tester ces suites avec le calculateur fourni en prime !

La conjecture

Une question naturelle, qui taraude l’esprit des mathématiciens depuis plus de soixante ans, est celle-ci :

La liste ci-dessus des suites de Barker connues est-elle complète ?

On a de solides raisons de penser que c’est le cas ; autrement dit, qu’on connaît toutes les suites de Barker possibles et imaginables et que, en particulier, leurs seules longueurs possibles sont
\[\color{blue}{1, 2, 3, 4, 5, 7, 11, 13}.\]
Ces raisons, exposées ci-dessous, conduisent tout naturellement à la conjecture suivante.

Conjecture. Il n’existe aucune suite de Barker de longueur supérieure ou égale à $14$.

Malgré plusieurs décennies de recherches, on ne dispose toujours pas d’une démonstration complète à ce jour.

Que sait-on en 2022 à ce sujet ?

Pour y répondre, il convient à nouveau de distinguer les cas de longueur paire et impaire.

Le cas de longueur impaire

Dans un article datant de 1961, Richard Turyn et James Storer ont démontré qu’en effet, il n’existe aucune suite de Barker de longueur impaire $n > 13$. Leur preuve est élémentaire, mais très subtile et pas facile du tout à maîtriser de bout en bout. La conjecture ci-dessus est donc vraie et close en longueur impaire.

Le cas de longueur paire

C’est dans ce cas-ci que la conjecture reste ouverte. On pense qu’effectivement, il n’existe aucune suite de Barker de longueur paire $n > 4$. Des résultats partiels spectaculaires ont été obtenus progressivement ces dernières décennies, mais une solution complète fait toujours défaut. Voici ce qu’on sait à ce jour, dans une version simplifiée et énoncée par commodité sous forme de théorème unique :

Théorème. S’il existe une suite de Barker de longueur paire $n > 4$, alors nécessairement

1. $n$ est un carré parfait [2].
2. Tout diviseur impair de $n$ est de la forme $d=4k+1$ avec $k$ entier naturel.
3. $n$ est supérieur à $4 \times 10^{33}$.

Ces résultats partiels sont dûs respectivement à

1. Richard Turyn dans les années 1960,
2. Michel Kervaire, Bahman Saffari et votre serviteur dans les années 1990,
3. Ka Hin Leung et Bernhard Schmidt en 2016.

Ils se démontrent avec des outils sophistiqués d’algèbre et de théorie des nombres. C’est toujours fascinant de rencontrer, comme ici, des circonstances où seul un haut niveau d’abstraction permet d’obtenir des résultats fins sur des objets mathématiques très concrets ; c’est l’un des aspects de la beauté et de l’élégance des mathématiques. Comme évoqué dans un article précédent : "Tels sont, en quelque sorte, les termes du marché en mathématiques : au prix d’un peu d’abstraction, on gagne en compréhension, en souplesse et en puissance.’’

Voici deux exemples d’application de ces résultats :

• Existe-t-il une suite de Barker de longueur $n = 10^{35}$ ? La réponse est non. Ce nombre n’est pas exclu par la troisième condition, mais il l’est d’emblée par la première puisque ce n’est pas un carré parfait.
• Existe-t-il une suite de Barker de longueur $n = 49 \times 10^{34}$ ? La réponse est non à nouveau. Ce nombre étant un carré parfait supérieur à $4 \times 10^{33}$, il n’est exclu ni par la première, ni par la troisième condition. Mais il l’est par la seconde, puisque divisible par $d=7$, lequel n’est pas de la forme $4k+1$ avec $k$ entier naturel.

Pour conclure

Les résultats présentés ici montrent que la réponse à la question du titre est très probablement positive. Espérons qu’une confirmation définitive, laquelle se fait désirer depuis des décennies, finisse par émerger un jour pas trop lointain.