Moi grosse lacune: Matiyasevic

@cc : Je joins un fichier où tu vas trouver de l'élimination p.9 et 10...

@Claude : Merci pour l'article de Davis mais je suis trop vieux pour gérer simultanément 12 équations !
J'essaierai de voir demain si je peux extraire du document ci-joint un petit polynôme lié à la quantification bornée dont j'ai parlé dans mon message précédent...

Marco, Gai-Requin
Plus facile que les puissances de 2 : être un nombre de Fibonacci. Un entier $x \in \N$ est un nombre de Fibonacci ssi il existe $y \in \N$ tel que $(x^2 + xy - y^2)^2 = 1$. Je vous fais un sens : si $x = F_n$, alors, from $F_n F_{n+2} - F_{n+1}^2 = (-1)^{n+1}$ et $F_{n+2} = F_n + F_{n+1}$, on obtient $x^2 + xy - y^2 = \pm 1$ en ayant pris $y = F_{n+1}$ (en fait pas trop le choix pour $y$).
Je vous laisse l'autre sens (cadeau) en ayant remarqué que $x^2 + xy - y^2$ c'est la norme de $x + y\phi$ dans l'anneau $\Z[\phi]$ avec $\phi^2 = \phi + 1$.

Pour amuser la galerie, un petit coup du Putnam trick et on obtient ce que l'on voit dans le truc attaché (où l'on commence à entrevoir une auto-référence dans la suite de Fibonacci).Gai-Requin : tu es si vieux que cela (gérer 12 équations ...etc..) ? J'aurais pas cru. Evidemment, cet article de Davis, je l'avais cité tout au début ainsi d'ailleurs que l'article de Jones/Matijasevic (1991). Le coup des 24 lemmes cela fait peur mais il convient de les analyser. Je vais essayer de t'expliquer sur deux exemples, ce que cela veut dire ``polynomialiser en $a$''. Et on va constater que l'on est pas les seuls à tourner en rond. Je commence par le lemme 2.17 (donc presque vers la fin : la section se termine par le lemme 2.24). Ok tu n'es pas dedans donc je rappelle les définitions (cf p. 239) :
$$
d = a^2 - 1, \qquad (a + \sqrt d)^n = x_n(a) + y_n(a) \sqrt d \qquad\qquad (\star)
$$C'est une définition de $x_n(a)$ et $y_n(a)$ pour $n \in \N$. Et $a$ c'est quoi ? Un entier $a > 1$ quand on veut faire semblant de faire de l'arithmétique ou bien une indéterminée si on en a envie. Of course, $x_n(a), y_n(a)$ sont des polynômes en $a$ à coefficients entiers. Et on peut concevoir que $a + \sqrt {a^2 - 1}$ est l'unité fondamentale ``quelque part'', de norme 1 (et pas $-1$ comme dans la suite de Fibonacci). Si bien que $(\star)$ est encore valide pour $n \in \Z$ au lieu de $n \in \N$.

$\bullet$ ``Polynomialiser en $a$'', cela signifie prendre le modèle
$$
{\Z[a][t] \over \langle t^2 - (a^2 - 1) \rangle } = \Z[a].1 \oplus \Z[a].t
$$Explication : comme on est grand, j'ai noté du même nom la classe de l'indéterminée $t$ dans le quotient. Que $(1,t)$ soit une $\Z[a]$-base est une évidence vu le quotient par un polynôme unitaire de degré 2. A noter qu'au numérateur, il y a DEUX indéterminées $a,t$. Of course, dans le quotient, $t$ c'est $\sqrt {a^2 - 1}$, au signe près comme dit l'autre (ce qui ne veut rien dire). Et la définition de $x_n(a), y_n(a)$ est donc maintenant :
$$
(a + t)^n \equiv x_n(a).1 + y_n(a).t \qquad \bmod \big(t^2 - (a^2 - 1)\big)
$$On a fait quoi pour l'instant ? RIEN. Maintenant, prenons $t = y-a$ pour coller à Davis lemma 2.17 en prenant $y = a+t$ !! Il vient :
$$
y^n \equiv x_n(a) + y_n(a).(y-a) \qquad \bmod \big(y^2 - 2ay + 1 \big)
$$On a fait quoi ? RIEN. Sauf que cette congruence, c'est exactement le lemme 2.17 de Davis que celui-ci démontre par récurrence sur $n$ en invoquant le lemma 2.13 !! Même scénario dans le papier de Jones/Matijasevic (équation 2.18 p. 696) : preuve par récurrence sur $n$ avec attribution de cette congruence à Julia Robinson (1952).

Est ce que cela te rassure ? (tourner en rond et tout le binz).

$\bullet$ Que peut-on polynomialiser ? Bonne question. Prenons par exemple le lemma 2.9 p. 241 : $y_n \mid y_t$ ssi $n \mid t$. Note : $y_n$ stands for $y_n(a)$. Là, il y a du RAISONNEMENT, de l'arithmétique avec même un raisonnement par l'absurde s'il vous plait. Ce que je dis, c'est que dans l'anneau $\Z[a]$ (factoriel sans être principal), c'est que l'on a pour $n, m \in \N$ :
$$
\gcd(y_n, y_m) = y_{\gcd(n,m)} \qquad \qquad \text{ gcd au sens FORT} \qquad
$$Explication : à droite, le pgcd des entiers $n,m$, c'est le pgcd habituel. Et à gauche ? C'est le pgcd au sens des anneaux principaux avec des polynômes en $a$ i.e. l'idéal $\langle y_n(a), y_m(a)\rangle$ est monogène, engendré par $y_{\gcd(n,m)}(a)$. Ce n'est pas dû à la qualité de l'anneau $\Z[a]$ qui n'est pas principal mais à la qualité de la suite de polynômes $\big(y_n(a)\big)_{n \ge 0}$. Bref, une bonne vieille identité algébrique (Bezout) universelle qui se laisse spécialiser et fournit le lemme 2.9

$\bullet$. Bilan : ne surtout pas recopier/pomper ces 24 lemmes sans les analyser !!

PS : un truc compliqué dans l'histoire, c'est l'orthographe de Yuri M. : Matijasevic (Amer. Math. Monthly), Matijassevitch (dans la Gazette, Ma collaboration ave Julia Robinson), Matijasevich (chez Poonen), ...etc...

Poirot

Merci. On est d'accord. Et tu avais raison : un petit patacaisse de notations entre $R$ et $S$ dans un endroit sensible. Les auteurs auraient pu se relire (ils sont deux) : faut pas rigoler avec ces choses là.

Et le bilan, en ce Premier Mai (y a un truc perso là) c'est que ta réponse me fait plaisir. Et que nous ne sommes pas complètement des blaireaux.

Bonsoir,

Sans avoir suivi le contenu du fil, je renvoie vers un document de quelques étudiants reprenant la démonstration de Matiyasevich: ici.

Sinon, je ne peux m'empêcher de donner un lien vers l'article de Koenigsmann démontrant la définissabilité de $\mathbf{Z}$ dans $\mathbf{Q}$ par une formule $\forall\exists$ (avec un seul quantificateur universel): ici. L'auteur montre également (modulo une variante de la conjecture de Bombieri-Lang) qu'on ne peut définir $\mathbf{Z}$ via une formule existentielle!

Cela (me) prend du temps de lire, besogneux que je suis. Avant de stopper ma participation à ce fil dans lequel je n'y trouve pas mon compte (pas d'échange en mon sens, mise à part l'intervention de Poirot me rassurant sur le sens des instances dans des problèmes d'indécidabilité, encore merci à lui qui a pris le temps de ....), je voudrais apporter quelques précisions sur certaines choses qui me paraissent totalement approximatives. Et comme je ne peux pas travailler dans l'approximation ...etc..

$\bullet$ 1 A propos du mémoire ``des étudiants'' (Fraux & Hemmer-Petitcolas, 2017)

$\blacktriangleright$ Ils reprendraient la démonstration de Matijasevic ? Cela veut dire quoi ? Celle de 1970 (Soviet Mathematics ...etc.. il s'agit de la traduction en anglais) dans laquelle il montre que la relation $m = F_{2n}$ est diophantienne ? Où celle ``plus moderne'' de 1991 (avec Jones, le premier papier que j'ai cité) qui utilise l'équation de Pell-Fermat ?

De toutes manières, ni l'un ni l'autre car ils reprennent l'article de Davis (1973) que j'ai cité au début du fil (avec celui de Jones/Matijasevic). La plupart du temps, cela se solde par ``Nous n'allons pas faire la démonstration complète, cf [1]''. La référence [1] c'est l'article de Davis. L'article de Jones/Matijasevic n'est pas cité.

$\blacktriangleright$ Qui en a lu vraiment ce mémoire ? Les 24 lemmes de Davis y sont repris intégralement, sans aucune analyse.

$\bullet$ 2 L'aspect diophantien des nombres de Fibonacci : $x \in \N$ est de Fibonacci ssi il existe $y \in \N$ tel que $(x^2 + xy - y^2)^2 = 1$. Absolument important ? Bien sûr que NON : c'est du RIEN ce résultat. C'était juste au début, séparé par un trait dans mon post, un clin d'oeil à Marco et Gai-Requin. Cela n'a vraiment AUCUN rapport avec le théorème de DPRM (Davis, Putnam, Robinson, Matijasevic).

$\bullet$ 3. Est ce qu'il y avait quelque chose d'important dans mon dernier-post ? Non, bien sûr. Sauf peut-être le bilan : si on voulait mieux comprendre Davis, je disais qu'il fallait absolument analyser ces 24 lemmes, qui sont mis A PLAT dans sa section 2.

Il faut mettre la lumière sur ceux qui sont importants. En fait, il y en a essentiellement deux, the so called ``Step down lemmas'' du type $F_n^2 \mid F_m \Rightarrow F_n \mid m$, importants car on déduit, d'une relation entre les valeurs de la suite, des renseignements sur les indices. Cf p. 35 de l'article (La Gazette, 1994) ``Ma collaboration avec Julia Robinson'' de Matijasevich.

Il convient donc de trier soigneusement ces 24 lemmes, ce qui n'est pas fait dans le mémoire des étudiants. En isolant d'abord ce qui sont ``évidents''.

$\bullet$ 4. Rappel. Dans mon premier post http://www.les-mathematiques.net/phorum/read.php?16,1989816,1991274#msg-1991274 le premier papier que j'ai cité est celui de Jones/Matijasevic avant celui de Davis. Il conviendrait de prendre le temps de lire (cela prend du temps, je le sais) pour comprendre les améliorations (entre 1973 et 1991, cela fait une vingtaine d'années, ça, je pense que c'est facile à piger).

Bref, je suis incapable de travailler dans l'approximation (bis). Et donc j'en reste là.

Claude:

Je n'ai pas lu ledit mémoire mais n'en connaissais que l'existence. N'ayant pas le temps de participer, j'ai seulement choisi de passer par ici et de proposer la littérature dont je suis au courant -- qui aurait pu aider/intéresser certains intervenants -- sans aucune prétention de qualité. Précisons que je n'aime pas non plus travailler dans l'approximation, raison pour laquelle je ne prétends pas "travailler" au sein de ce fil.

Quitte à me répéter, il s'agissait seulement de partager des documents qui pourraient intéresser les intervenants.

Bonne après-midi pluvieuse.

Par politesse, je dois répondre à Ptolemee et à Gaussien. Pour Gaussien, juste pour te dire que Gai-Requin, quelques posts avant, avait attaché le même document, mais c'est pas grave of course.

Pour Ptolemee, cela va être plus long. D'abord merci car j'ai encore beaucoup de choses à apprendre et comprendre dans cette histoire. En passant : y'a vraiment quelque chose d'ingénieux dans DPRM (lire ce qu'en dit Bary Mazur).

$\bullet$ En ce qui concerne la thèse, j'ai commencé à faire un survol. Je crois comprendre que l'auteur Cabusora s'inspire de Yu. Manin. C'est dingue, celui là il est partout. Dans la thèse, c'est tout le contraire des 24 lemmes à plat de Davis. Attention, je ne critique surtout pas Davis. Il faut de tout pour faire un monde. J'apprécie d'en disposer : il y a des remarques historiques, Davis a fait un sacré boulot de simplification, c'est à nous qui passons derrière de structurer à notre manière. Bref, dans l'histoire, il est impératif de lire en plusieurs endroits.

Est ce Davis et Robinson qui ont mis le paquet sur l'utilisation de Pell-Fermat $x^2 - (a^2-1)y^2 = 1$ ?? Jones & Matijasevic disent ``Today the Pell Fermat equation gives the simplest know proof''.

$\bullet$ Retour à la thèse. Avec les notations un peu près habituelles :
$$
x_n(a) + y_n(a) \sqrt {a^2 - 1} \quad =_{\rm def} \quad (a + \sqrt {a^2 - 1})^n
$$on voit tout de suite, p. 11, un truc franc qui exprime $a^n$ en fonction des $y_\bullet$. C'est la formule de gauche (est ce du à Manin ?). Pour $a$ entier $\ge 2$ :
$$
a^n = \left\lfloor {y_{n+1}(Na) \over y_{n+1}(N)} \right\rfloor \quad N > 2ny_{n+1}(a)
\qquad\qquad\qquad
a^n = \big[ x_n(N) - (N-a) y_n(N)\big] \bmod (2Na - a^2 - 1) \quad N \ge y_{n+1}(a)
$$A droite, c'est une autre formule, apparemment très différente. C'est le lemme 3.1 de Jones/Matijasevic qui exprime $a^n$ en fonction de $x_\bullet, y_\bullet$ qui provient de ``la congruence de Robinson'', cf https://williamstein.org/edu/Spring2003/21n/papers/hilbert10.pdf

Dans Davis, faut vraiment faire un effort pour trouver la formule de droite (elle y est, cachée).

$\bullet$ Par contre, chez Cabusora, on a du mal (attention, ce n'est pas une critique ...etc..) dans la partie ``aspect diophantien de $y = y_n(a)$'' à voir les deux step down lemmas (ils figurent cachés). Ils sont bien dégagés chez Jones/Matijasevic et nommés en tant que tels. Et de plus, chez eux, chaque énoncé d'un step down lemma est une équivalence. Vachement important : on ne perd aucune information.

En tout cas, le peu que j'ai lu de cette thèse : c'est une bonne pioche : l'auteur fait vraiment un effort pour s'expliquer. C'est dense mais encore une fois, c'est écrit et c'est à nous d'analyser, de faire un effort ...etc.. C'est du moins ce que je pense.

$\bullet$ Analyse numérique. Je ne peux pas faire autrement vu maintenant les deux formules de $a^n$. Peut-être qu'elles sont quand même liées ? Je n'ai pas eu le temps de gratter.

[color=#000000]> DivFormulaBigBound := func < n | 2*n*y(a,n+1) + 1 > ;
> RemFormulaBigBound := func < n | y(a,n+1) > ;
> 
> // a^n = partie entière de y(N*a,n+1) / y(N,n+1)        N > 2*n*y_{n+1}(a) (Manin ?)
> //     = (x_n(N) - (N-a)*y_n(N)) mod (2*N*a - a^2 - 1)  N >= y_{n+1}(a)    (DPRM ? Jones/Matijasevic, lemma 3.1)
[/color]

Je prends jusqu'au bout $a = 2$. Et je commence petit avec $n=4$, en montrant la borne $N \ge \text{borne}$ à partir de laquelle on peut utiliser les formules.

[color=#000000]> n := 4 ;
> DivFormulaBigBound(n) ;
1673
> RemFormulaBigBound(n) ;
209
> a^n ;
16
> Nrange := [2..8] ;
> [y(N*a, n+1) div y(N, n+1) : N in Nrange] ;
[ 18, 17, 16, 16, 16, 16, 16 ]
> [(x(N,n) - (N-a)*y(N,n)) mod (2*N*a - a^2 - 1) : N in Nrange] ;
[ 1, 2, 5, 1, 16, 16, 16 ]
[/color]

Un autre essai pour $n = 10$, juste sur une plage de $N$, histoire de voir. Comportements très différents des formules.
.

[color=#000000]> n := 10 ;
> DivFormulaBigBound(n) ;
11294381
> RemFormulaBigBound(n) ;
564719
> a^n ;
1024
> Nrange := [2*n..5*n] ;
> [y(N*a, n+1) div y(N, n+1) : N in Nrange] ;
[ 1028, 1027, 1027, 1027, 1027, 1026, 1026, 1026, 1026, 1026, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 
1025, 1025, 1025, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024 ]
> [(x(N,n) - (N-a)*y(N,n)) mod (2*N*a - a^2 - 1) : N in Nrange] ;
[ 49, 76, 28, 67, 23, 74, 34, 97, 61, 25, 104, 72, 40, 8, 107, 79, 51, 23, 142, 118, 94, 70, 46, 22, 169, 149, 129, 109,
89, 69, 49 ]
[/color]

Je termine par $2^{15}$ et $2^{20}$. Je stoppe ici car j'ai peur d'être exclus pour avoir fait de l'analyse numérique dans un fil de logique.

[color=#000000]> n := 15 ;
> a^n ;
32768
> N := DivFormulaBigBound(n) ; 
> N ;
12265673281
> y(N*a,n+1) div Y(N,n+1) ;
32768
> 
> N := RemFormulaBigBound(n) ; 
> N ;
408855776
> (x(N,n) - (N-a)*y(N,n)) mod (2*N*a - a^2 - 1) ;
32768
> 
>
> n := 20 ;
> a^n ;
1048576
> N := DivFormulaBigBound(n) ; 
> N ;
11840440684201
> y(N*a,n+1) div Y(N,n+1) ;
1048576
> 
> N := RemFormulaBigBound(n) ; 
> N ;
296011017105
> (x(N,n) - (N-a)*y(N,n)) mod (2*N*a - a^2 - 1) ;
1048576
[/color]

J'ai fait plein d'autres essais pour disposer des indices de stationnement des deux formules ..etc...