Calcul parallèle des suites de Büchi

Encadrants : Fabrice Jaillet (LIRIS-ORIGAMI)
Collaboration : (Universidad de Concepción, Chili)
Détails : Le stage se déroulera au sein du laboratoire LIRIS (bâtiment Nautibus).
Domaine : parallélisme, algorithme, théorie des nombres.
Compétences requises : C++, éventuellement multi-CPU, GPU (OpenMP, OpenACC).

Sujet : En théorie des nombres, il n’y a pas que le théorème de Fermat ! Le problème de Büchi (Büchi's Problem, Wikipedia), aussi connu comme les n-ièmes différences des carrés, reste encore ouvert ! Les séries de Büchi sont des séquences d’entiers telles que la seconde différence de leurs carrés est constante et égale à 2.

Par exemple, si x1=1, x2=2 et x3=3, alors (x3)2-(x2)2=9-4=5 et (x2)2-(x1)2=4-1=3, et 5-3=2 ! Cela marche pour toute série d’entiers dont les valeurs absolues sont consécutives, et ces séries sont appelées triviales, par exemple [-7,6,5,4,-3,-2,1,0,-1,2]. Celles dont les valeurs sont non consécutives sont plus intéressantes, par exemple [6,23,32,39]. Il existe une infinité de suites (non-triviales) de longueur 3 et 4. Celles de longueur 3 sont parfaitement connues. Celle de longueur 4 sont partiellement décrites, grâce notamment aux chercheurs de l’Universidad de Concepción, au Chili. Par contre, il n’existe pas de suite connue de longueur 5….



La question posée est donc de savoir s'il existe une limite M, telle qu’il n’existe plus de série non triviale de longueur M. Répondre à cette question permettrait de résoudre un certain nombre d’autres problèmes en théorie des nombres et en logique mathématique, dont savoir si un système particulier d’équations a une solution ou non.

Dans ce projet, une des pistes de recherche concerne la génération d’un très grand nombre de suites de Büchi de longueur 4, dans le but d’essayer de trouver des relations entre elles, et de les caractériser, c’est-à-dire trouver un paramétrage qui permette d'en générer un maximum. Et éventuellement trouver la première suite connue de longueur 5 !

Il existe plusieurs techniques pour générer des suites de longueur 4, par exemple en brute force ou à partir de la factorisation de la décomposition du carré en 2 termes, ou via la résultion d'une équation diophantine (Pell généralisée). Et une technique originale et prometteuse à partir de multiplications très simples de matrices 3x3 et de vecteurs, qui permet de générer à bas coût des suites avec de très grandes valeurs que l’on ne pourrait pas obtenir avec d’autres techniques. La difficulté ici est de manipuler ces suites, dont les valeurs sont rapidement très grandes :

([127261567962,816475242713,1147635890536,1402677601065],
ou [91075841944817097,91076096988493904,91076352031456505,91076607073704906]).

L’objectif du projet est donc :

  • Étude des algorithmes existants

  • Proposition d’une méthode de parallélisation de ces algorithmes. On pourra étudier des solutions simples basées sur OpenMP ou OpenACC.

  • Étude de la compatibilité de la parallélisation dans un contexte de calcul sur des grands nombres (plusieurs centaines de chiffres, on travaille sur les carrés de très grands nombres), à l’aide de bibliothèques spécialisées (GMP, boost::multiprecision).

  • Implémentation de ces algorithmes.