L'Approximation diophantienne simultanée et l'optimisation discrète

Abstract

Étant donnée une fonction bornée (supérieurement ou inférieurement) $f:\mathbb{N}^k \To \Real$ par une expression mathématique, le problème de trouver les points extrémaux de $f$ sur chaque ensemble fini $S \subset \mathbb{N}^k$ est bien défini du point de vu classique. Du point de vue de la théorie de la calculabilité néanmoins il faut éviter les cas pathologiques où ce problème a une complexité de Kolmogorov infinie. La principale restriction consiste à définir l'ordre, parce que la comparaison entre les nombres réels n'est pas décidable. On résout ce problème grâce à une structure qui contient deux algorithmes, un algorithme d'analyse réelle récursive pour évaluer la fonction-coût en arithmétique à précision infinie et un autre algorithme qui transforme chaque valeur de cette fonction en un vecteur d'un espace, qui en général est de dimension infinie. On développe trois cas particuliers de cette structure, un de eux correspondant à la méthode d'approximation de Rauzy. Finalement, on établit une comparaison entre les meilleures approximations diophantiennes simultanées obtenues par la méthode de Rauzy (selon l'interprétation donnée ici) et une autre méthode, appelée tétraédrique, que l'on introduit à partir de l'espace vectoriel engendré par les logarithmes de nombres premiers.

Given a (lower or upper) bounded function $f:\mathbb{N}^k \To \Real$ by a mathematical expression. The problem to find the extremal points of $f$ on any bounded set $S \subset \mathbb{N}^k$ is well-defined from a classical point of view. Nevertheless, from a computability theory perspective, it should be avoided the possibility of pathologies when this problem has infinite Kolmogorov complexity. The main constraint is that the order relationship between computable reals is not effectively solvable. We solve this problem by means of a structure containing two algorithms. The first one allows to evaluate the cost function while the second one transforms each value of the cost function in a point in an infinite dimensional vector of a space. We develop three particular cases, one of them corresponding to the Rauzy approximation method. Finally, we make a comparison between the best simultaneous Diophantine approximations obtained by the Rauzy method (our optimization-oriented version of it) and our tetrahedral method, that is one of the main achievement of this work.