Ensembles de Sidon : le défi des écarts tous différents

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. C'est un immense plaisir d'accueillir tout le monde pour cette nouvelle exploration. Aujourd'hui, on s'attaque en fait à des questions si simples qu'un enfant de 10 ans pourrait les poser sans problème, mais qui rendent fous les mathématiciens depuis presque un siècle. On plonge directement au cœur de la théorie des nombres.

Intervenant 20:24

Oui, c'est vraiment ça la bouteille brute de l'arithmétique. On joue avec les briques fondamentales de notre logique. Vous avez de simples additions, des soustractions et soudainement, paf, on se heurte à des murs complètement invisibles.

Intervenant 10:38

C'est fou ça, des structures qui semblent cacher un ordre profond qu'on ne comprend pas encore totalement.

Intervenant 20:45

Absolument, c'est fascinant.

Intervenant 10:46

Et donc, la mission de notre décryptage d'aujourd'hui, pour ceux qui nous écoutent, c'est de foncer tête baissée dans l'un de ces fameux murs mystérieux. On va explorer un concept mathématique assez génial qu'on appelle les ensembles de Sidon. Ok, décortiquons un peu tout ça. D'où sort ce concept au nom, ma foi, si intrigant ?

Intervenant 21:06

Alors, l'origine, elle nous ramène à Simon Sidon. C'est un mathématicien hongrois qui a introduit ses idées en 1932. Et bon, ce qui est vraiment remarquable dans cette histoire, c'est qu'il ne cherchait pas du tout, mais alors pas du tout, à créer un casse-tête arithmétique.

Intervenant 11:20

Ah bon ? Il cherchait quoi alors ?

Intervenant 21:22

En fait, il travaillait sur un sujet très différent, la théorie des séries de Fourier.

Intervenant 11:26

Ah, attendez. Les séries de Fourier, on parle bien de la décomposition des ondes, n'est-ce pas ? Genre, comme les ondes sonores ou lumineuses ?

Intervenant 21:34

C'est exactement ça, ouais. Il analysait comment les fréquences, comment elles s'additionnent et interagissent entre elles. Et du coup, pour éviter que certaines ondes ne s'amplifient mutuellement de manière, disons, chaotique, il s'est rendu compte qu'il avait un besoin très spécifique.

Intervenant 11:50

Lequel ?

Intervenant 21:50

Il avait besoin de trouver des ensembles de nombres entiers qui étaient espacés d'une manière très, très particulière. C'est de là qu'est née la fameuse règle d'or pour définir un ensemble de Sidon.

Intervenant 12:01

Ok. Et quelle est cette règle, du coup ?

Intervenant 22:03

Elle stipule que, dans un tel ensemble, tous les écarts entre deux éléments quelconques doivent être strictement différents. Tous.

Intervenant 12:11

Wow. Tous les écarts. Sans aucune exception. C'est-à-dire que si je prends n'importe quelle paire de nombres dans mon panier, la soustraction entre le plus grand et le plus petit doit toujours me donner un résultat unique.

Intervenant 22:24

Sans la moindre exception. Mathématiquement, on dit qu'on ne peut jamais trouver quatre éléments distincts, disons A, B, C et D, tels que la différence A moins C soit égale à D moins B.

Intervenant 12:39

D'accord.

Intervenant 22:40

Et par un simple jeu d'équilibre algébrique, si on passe les signes négatifs de l'autre côté de l'équation, ça revient à dire que la somme A plus B ne doit jamais être égale à la somme C plus D. En gros, toutes les sommes de deux éléments doivent aussi être uniques.

Intervenant 12:55

Ok, je vois. Alors, pour rendre cela vraiment concret pour quiconque écoute en ce moment, imaginons qu'on joue un petit jeu avec les nombres, disons de 1 à 100. Le but, c'est d'en sélectionner le plus possible sans violer cette fameuse règle de Sidon.

Intervenant 23:10

Je vous écoute.

Intervenant 13:11

Bon, commençons simplement par choisir le 1 et le 2. L'écart entre eux, bon, c'est de 1.

Intervenant 23:17

Voilà, jusque là, le terrain est complètement dégagé. L'écart de 1 est pris, on le raille de la liste.

Intervenant 13:22

Ensuite, si on veut ajouter un troisième nombre, on ne peut clairement pas prendre le

Intervenant 23:28

3. Exactement.

Intervenant 13:29

Parce que l'écart entre le 2 et le 3, c'est 1. Or, on a déjà consommé cet écart juste avant avec le 1 et le 2. Donc, bye bye le 3, il est éliminé. On saute au 4. Nos nombres sont donc 1, 2 et 4. Les écarts possibles entre eux, voyons voir, ça fait 1, 2 et 3. Ils sont tous uniques, le jeu continue.

Intervenant 23:51

Très bien, mais regardons ce qui se passe juste après le 4 du coup.

Intervenant 13:54

Ouais.

Intervenant 23:55

Le prochain nombre disponible, est-ce que ça pourrait être le 5 ?

Intervenant 13:59

Euh non, parce que 5 moins 4 ça fait 1, et le 1 est déjà pris.

Intervenant 24:03

Voilà. Le 6 alors ?

Intervenant 14:05

Impossible, puisque 6 moins 4 ça fait 2, un écart déjà utilisé aussi.

Intervenant 24:09

Et le 7 ?

Intervenant 14:10

Toujours pas, parce que 7 moins 4 donne 3, et 3 c'est l'écart entre 1 et 4. Exactement. En choisissant à peine trois petits nombres au tout début, on a posé un véritable champ de mine. Le tableau des options possibles se réduit à une vitesse complètement folle.

Intervenant 24:28

Mais grave, c'est exponentiel presque.

Intervenant 14:31

Du coup, la question qui vient immédiatement quand on visualise ça, c'est on se demande si on n'a pas fait une erreur stratégique fatale en choisissant le 2 dès le début, en fait. Est-ce qu'on aurait pu en accumuler beaucoup plus en espaçant les premiers choix différemment ?

Intervenant 24:45

Eh bien voilà, c'est le cœur même du problème de Sidomeiana. C'est la grande quête. Déterminer la taille maximale d'un tel ensemble, si on a le droit de piocher parmi les N premiers rentiers naturels. Comment optimiser nos choix initiaux pour éviter de s'auto-bloquer trop vite, quoi ?

Intervenant 14:59

Mais pour des petits nombres, je ne sais pas. Comme 100, un ordinateur peut tester toutes les combinaisons en une fraction de seconde et nous donner la réponse optimale, je suppose, non ?

Intervenant 25:09

Ah oui, pour 100, oui. Mais la recherche exhaustive, elle a ses limites physiques. Ce qui passionne vraiment les théoriciens en mathématiques, c'est ce qu'on appelle le comportement asymptotique.

Intervenant 15:18

C'est-à-dire ?

Intervenant 25:19

Quand ton temps est à l'infini.

Intervenant 15:20

C'est ça. Que se passe-t-il quand le réservoir de nombres, ce fameux N, devient gigantesque ? Et en fait, on a fini par prouver un résultat classique qui est fondamental.

Intervenant 25:30

Lequel ?

Intervenant 15:31

Si on cherche dans un intervalle continu contenant n éléments, la taille maximale de notre ensemble de Sidon tournera toujours asymptotiquement autour de la racine carrée de n. Attendez, la racine carrée. Donc si on joue avec un réservoir de disons un million de nombres, on ne pourra en sélectionner qu'environ 1000 qui respectent la règle de Sidon, puisque 1000 c'est la racine carrée d'un million. C'est une limite super drastique.

Intervenant 25:57

Très drastique, ouais. Mais attention, il y a une propriété de symétrie vitale ici, c'est la translation.

Intervenant 16:04

La translation, c'est-à-dire le

Intervenant 26:06

fait de tout décaler ? Oui. Imaginons qu'on prenne ce fameux ensemble parfait de mille nombres qu'on vient de trouver et qu'on décide d'ajouter la valeur 100 000 à chacun d'entre eux. On les décale tous ensemble en blocs sur la droite de la droite numérique.

Intervenant 16:19

Ah, l'anamogie qui me vient tout de suite en tête, c'est comme un clavier de piano.

Intervenant 26:23

Oh, j'aime bien ! Allez-y !

Intervenant 16:24

En fait, l'écart entre deux touches, ce qu'on appelle un intervalle en musique, ça définit si c'est harmonieux ou dissonant. Si je déplace toute ma main d'une octave entière vers la droite de mon clavier, Je joue des notes qui sont beaucoup plus aiguës, les fréquences de base sont complètement différentes, mais la distance physique exacte entre mes doigts et donc l'écart relatif entre les notes que je joue, ça reste absolument identique.

Intervenant 26:53

C'est une métaphore parfaite, c'est exactement ça la translation mathématique. En décalant tous nos nombres de la même valeur, les soustractions entre eux donneront toujours, toujours les mêmes résultats.

Intervenant 17:05

Donc un ensemble de Sidon translaté reste un ensemble de Sidon ?

Intervenant 27:09

Absolument. Et cela garantit une règle d'or. Peu importe où l'on se trouve sur la droite des nombres, tout intervalle continu de n éléments nous permettra de construire un ensemble dont la taille est proche de sa racine carrée.

Intervenant 17:20

Bon, ça, c'est d'une régularité absolue. C'est beau.