Résultats efficaces en théorie des nombres - Effective results in number theory

Pour des raisons historiques et afin d'avoir une application à la solution des équations diophantiennes , les résultats en théorie des nombres ont été examinés plus que dans d'autres branches des mathématiques pour voir si leur contenu est effectivement calculable . Lorsqu'il est affirmé qu'une liste d'entiers est finie, la question est de savoir si, en principe, la liste pourrait être imprimée après un calcul machine.

Le résultat de Littlewood

Un premier exemple d'un résultat inefficace était le théorème de JE Littlewood de 1914, que dans le théorème des nombres premiers les différences de ( x ) et ( x ) avec leurs estimations asymptotiques changent de signe infiniment souvent. En 1933, Stanley Skewes a obtenu une limite supérieure effective pour le premier changement de signe, maintenant connu sous le nom de nombre de Skewes .

Plus en détail, en écrivant pour une suite numérique f ( n ), un résultat effectif sur son changement de signe infiniment souvent serait un théorème incluant, pour chaque valeur de N , une valeur M > N telle que f ( N ) et f ( M ) ont des signes différents, et tels que M pourrait être calculé avec des ressources spécifiées. En termes pratiques, M serait calculé en prenant les valeurs de n à partir de N , et la question est « jusqu'où devez-vous aller ? Un cas particulier consiste à trouver le premier changement de signe. L'intérêt de la question était que les preuves numériques connues ne montraient aucun changement de signe : le résultat de Littlewood garantissait que cette preuve n'était qu'un effet de petit nombre, mais « petit » incluait ici des valeurs de n jusqu'à un milliard.

L'exigence de calculabilité reflète et contraste avec l'approche utilisée dans la théorie analytique des nombres pour prouver les résultats. Elle remet par exemple en question toute utilisation de la notation de Landau et de ses constantes implicites : les assertions sont-elles de purs théorèmes d'existence pour de telles constantes, ou peut-on récupérer une version dans laquelle 1000 (disons) prend la place de la constante implicite ? Autrement dit si l'on savait qu'il y avait M > N avec un changement de signe et tel que

M = O( G ( N ))

pour une fonction explicite G , disons construite à partir de puissances, de logarithmes et d'exponentielles, cela signifie seulement

M < A . G ( N )

pour une constante absolue A . La valeur de A , la constante implicite , peut également devoir être rendue explicite, à des fins de calcul. L' une des raisons notation Landau était une introduction populaire est qu'il se cache exactement ce que A est. Dans certaines formes de preuve indirecte, il peut ne pas être du tout évident que la constante implicite puisse être rendue explicite.

La "période Siegel"

Bon nombre des principaux résultats de la théorie analytique des nombres qui ont été prouvés dans la période 1900-1950 étaient en fait inefficaces. Les principaux exemples étaient :

Les informations concrètes qui étaient théoriquement incomplètes comprenaient des limites inférieures pour les nombres de classes ( les groupes de classes idéaux pour certaines familles de champs de nombres se développent); et les limites des meilleures approximations rationnelles des nombres algébriques en termes de dénominateurs . Ces dernières pourraient être lues assez directement comme des résultats sur les équations diophantiennes, d'après les travaux d' Axel Thue . Le résultat utilisé pour les nombres de Liouville dans la preuve est efficace dans la façon dont il applique le théorème de la valeur moyenne : mais les améliorations (à ce qui est maintenant le théorème de Thue-Siegel-Roth) ne l'étaient pas.

Travail ultérieur

Les résultats ultérieurs, en particulier d' Alan Baker , ont changé la position. Qualitativement parlant, les théorèmes de Baker semblent plus faibles, mais ils ont des constantes explicites et peuvent en fait être appliqués, en conjonction avec le calcul machine, pour prouver que les listes de solutions (suspectées d'être complètes) sont en fait l'ensemble de solutions complet.

Problèmes théoriques

Les difficultés ici ont été rencontrées par des techniques de preuve radicalement différentes, faisant beaucoup plus attention aux preuves par contradiction. La logique impliquée est plus proche de la théorie de la preuve que de celle de la théorie de la calculabilité et des fonctions calculables . Il est assez vaguement conjecturé que les difficultés peuvent résider dans le domaine de la théorie de la complexité computationnelle . Des résultats inefficaces sont encore prouvés sous la forme A ou B , où nous n'avons aucun moyen de dire laquelle.

Les références

Liens externes