Moi grosse lacune: Matiyasevic

On possède peut-être de tels documents, mais personnellement je ne comprends strictement rien à ta requête.

A une certaine époque (il y a longtemps), j'ai étudié très partiellement le papier de Jones & Matiyasevich de 1991 in https://wstein.org/edu/Spring2003/21n/papers/hilbert10.pdf.

Je me souviens bien qu'en bas de la page 698, une fois obtenu que la relation en $(k, m, n)$ définie par $m = k^n$ est diophantienne, je m'étais dit : je vais prendre $k=2$ et refaire le truc depuis le début histoire d'y voir plus clair. I.e. que l'ensemble des puissances de 2 est diophantien. Et j'avais obtenu quelque chose de plus simple (normal puisque $k = 2$ est fixé). Sauf que je m'étais complètement vautré. Et cela m'a calmé et fait prendre conscience que c'était bien plus délicat que prévu.

Dans la bande DPRM (Davis, Putnam, Robinson, Matiyasevich), il y aussi le papier de Davis. http://www.math.umd.edu/~laskow/Pubs/713/Diophantine.pdf

Quelques photos : http://www.claymath.org/library/annual_report/ar2007/07report_robinson.pdf

CC
Depuis le départ, je ne comprends absolument rien à ce que tu racontes mais ce ``n'est pas grave'' (cela donne l'impression que tu es dans ton monde..)
Mais cela m'a permis de mettre un peu d'ordre dans mes affaires. J'ai parfois du mal à m'y retrouver dans les dates et dans ``qui a fait quoi ?''.

On voit par exemple, dans le papier de Davis que j'ai pointé (celui de 1973), qu'une grande partie est consacrée au fait que la fonction ``exponentielle'' $h(n,k) = n^k$ est diophantienne. C'est l'objet du th 3.3. Et on voit qu'une présentation diophantienne est constituée de 12 équations numérotées de I à XII (j'ai eu la flemme de compter le nombre de variables auxiliaires).

Et tout repose sur 24 lemmes de la section 2 (qui s'intitule ``Twenty-four easy lemmas'') tournant autour de l'équation de Pell-Fermat
$$
x^2 - (a^2 - 1) y^2 = 1, \qquad a \text { entier } > 1
$$J'avais constaté, du moins dans l'article de Jones et Matijasevic (orthographe changeante selon ..) que l'on pouvait simplifier certaines preuves par récurrence en ``polynomialisant'' en $a$ le truc.

Bon, je ne voudrais pas polluer ton fil mais je ne peux pas m'empêcher d'attacher une photo (je ne sais pas si on y voit grand chose) tirée de l'article (1987, je crois) de Constance Reid ``The autobiography of Julia Robinson'' (J. Robinson : 1919-1985). On y voit : Davis, Robinson, Matijasevic (manque Putman). Yuri M. fait vraiment jeune à côté des deux autres.

Je trouve qu'il y aurait pas mal de choses extra-mathématiques à dire autour de toute cette histoire : l'erreur de A. Tarski (patron de J. Robinson) concernant l'aspect diophantien de l'ensemble des puissances de 2, ce qu'en disait Dieudonné (du travail de Matijasevic et le dixième problème d'Hilbert) ...etc...

Je ne peux pas m'empêcher de pointer ``Les problèmes de Hilbert et leur devenir'' in http://www.numdam.org/article/CSHM_1993_2_3__95_0.pdf. J'arrête, promis, juré.

$\def\num{\text{numéro}}\def\long{\text{longueur}}\def\Z{\mathbb Z}$Il s'agit du fil qui remonte à 4 ans http://www.les-mathematiques.net/phorum/read.php?3,1261109,1263267 mais rien n'avait été finalisé. Et donc pour moi, c'est comme s'il n'y avait rien eu. En ce qui concerne le gars de la mortalité des matrices $3 \times 3$, j'avais étudié l'algèbre de son truc, entrevu des choses mais pas pigé vraiment.
Ce jour, des progrès (pour moi). Du coup je l'écris ici mais c'est surtout pour moi.

$\Sigma$ désigne un alphabet de cardinal $n \ge 2$ dont on va numéroter les éléments entre $0$ et $n-1$ pour faire de la numération en base $n$ (le truc tout bête). Je note $\Sigma^*$ le monoïde libre engendré par $\Sigma$. Le gars va plonger $\Sigma^*$ de plusieurs manières dans $M_3(\Z)$, chose que l'on ne pourrait pas faire dans $M_2(\Z)$ car pas assez de place. Au lieu de balancer le truc fini du gars auquel j'avais pas pigé grand chose, je vais faire une première passe. Il faudra ensuite réaliser une conjugaison ad-hoc qui ira coller ce qu'il faut en le coefficient $(3,2)$ des matrices (coefficient retenu pour la mortalité).

$\bullet$ Rappel du problème de Floyd ou mortalité. Son entrée est la donnée d'un nombre fini de matrices de $M_3(\mathbb Z)$ (on ne suppose pas qu'elles commutent). En sortie : existe-t-il un produit (avec répétition possible) de ces matrices dont le coefficient $(3,2)$ est nul ? C'est un problème indécidable. L'auteur le ramène au problème de correspondance de Post de la manière suivante : mise au point d'une application ``magique'':
$$
\mu : \Sigma^* \times \Sigma^* \to M_3(\Z)
$$Elle est magique dans le sens où d'abord c'est un morphisme de monoïdes (au départ pour la structure de produit cartésien), à l'arrivée pour la multiplication. Et d'une. Le deuxième truc magique, c'est qu'elle permet de tester l'égalité de deux mots $u,v \in \Sigma^*$ de la manière suivante : on a $u = v$ si et seulement si le coefficient $(3,2)$ de la matrice $\mu(u,v)$ est nul. Une fois que l'on a $\mu$ avec soi, c'est facile, à partir d'une instance du problème de Post, de fabriquer une instance du problème de Floyd.

Ici je vais raconter l'algèbre de la fabrication d'une $\mu$ approximative, à corriger plus tard en une bonne $\mu$ (autres posts si tout va bien).

$\bullet$ On dispose de deux fonctions $\gamma : \Sigma^* \to \N$ (injective) et $\eta : \Sigma^* \to \N$ définies par
$$
\gamma(u_0 u_1 \cdots u_c) = \sum_{i=0}^c \num(u_i) n^i, \qquad \qquad \eta(u_0 \cdots u_c) = n^{c+1} = n^{\long(u)} \qquad\qquad
\fbox {$\gamma(uv) = \gamma(u) \eta(v) + \gamma(v)$}
$$A droite, j'ai encadré la relation fondamentale de pseudo-multiplicativité de $\gamma$

$\bullet$ Les matrices $D'(a,b)$. Le $D$ pour droite, et le prime pour provisoire.

[color=#000000]> DprimeMatrix(a,b) ;
[1 0 0]
[0 a 0]
[0 b 1]
// c(a*x+b) + d = c*a*x + (c*b + d)
> DprimeMatrix(a,b)*DprimeMatrix(c,d) ;
[      1       0       0]
[      0     a*c       0]
[      0 b*c + d       1]
[/color]

Il faut comprendre que les $D'(a,b)$ sont une manifestation du semi-groupe affine $x \mapsto ax + b$ : on multiplie deux telles matrices comme on compose deux applications affines mais à l'envers. A l'envers car j'aurais dû mettre $\left[ \matrix {a &b\cr 0 &1\cr}\right]$ au lieu de la transposée $\left[ \matrix {a &0\cr b &1\cr}\right]$ Je viens de m'en apercevoir à l'instant. Bref, on va pouvoir plonger $\Sigma^* $ dans $M_3(\Z)$ via :
$$
\Sigma^* \ni u \mapsto D'\big(\eta(u), \gamma(u) \big) = \left[ \matrix {1 &0&0 \cr 0 &\eta(u) & 0\cr 0 &\gamma(u) & 1} \right]
$$$\bullet$ Les matrices $G'(a,b)$. Le $G$ pour gauche, et le prime pour provisoire. C'est une autre manifestation du semi-groupe des applications affines. D'ailleurs conjuguée à la première via la matrice $T$ d'ordre 4.

[color=#000000]> GprimeMatrix(c,d) ;
[c 0 0]
[0 1 0]
[d 0 1]

> T ;
[ 0  1  0]
[-1  0  0]
[ 0  0  1]

> T * DprimeMatrix(c,d) * T^-1 ;
[c 0 0]
[0 1 0]
[d 0 1]
[/color]

Idem, un AUTRE plongement $\Sigma^* $ dans $M_3(\Z)$ analogue au premier.

Miracle. Il y a assez de place en dimension 3 : l'auteur a choisi ces réalisations de manière à ce qu'elles COMMUTENT !! En fait, c'est plutôt ce que j'en ai tiré car le gars n'a fourni que son produit fini.

[color=#000000]> DprimeMatrix(a,b) * GprimeMatrix(c,d) ;
[c  0  0]
[0  a  0]
[d  b  1]
> 
> GprimeMatrix(c,d) * DprimeMatrix(a,b) ;
[c  0  0]
[0  a  0]
[d  b  1]
[/color]

$\bullet$ Du coup, grâce à la commutation, c'est facile de fabriquer un $\mu$ multiplicatif en multipliant les deux plongements qui commutent.
$$
\mu : \Sigma^* \times \Sigma^* \to M_3(\Z), \qquad (u,v) \mapsto G'(\eta(u), \gamma(u)) \ \times\ D'(\eta(v), \gamma(v))
$$
$\bullet$ La suite ? Une matrice involutive $Q$ que j'ai eu du mal à trouver pour passer du monde avec des primes au monde sans les primes : $D(a,b) = Q D'(a,b) Q$ et $G(c,d) = Q G'(c,d) Q$. Tout continue à commuter comme avant. Mais il faut maintenant regarder dans le produit ce qui figure en position $(3,2)$

[color=#000000]> GMatrix(a,b) ;               
[     a -a + 1      0]
[     0      1      0]
[    -b      b      1]
> DMatrix(c,d) ;
[    1 c - 1     0]
[    0     c     0]
[    0     d     1]
> GMatrix(a,b) * DMatrix(c,d) ;
[     a -a + c      0]
[     0      c      0]
[    -b  b + d      1]
> DMatrix(c,d) * GMatrix(a,b) ;
[     a -a + c      0]
[     0      c      0]
[    -b  [color=#FF0000]b + d[/color]      1]
[/color]

$a$ pour $\eta(u)$, $b$ pour $\gamma(u)$, $c$ pour $\eta(v)$, $d$ pour $\gamma(v)$. En changeant $b$ en $-b$, on ajuste le truc en un morphisme Graal
$$
\Sigma^* \times \Sigma^* \ni (u,v) \to \left[ \matrix {\eta(u) & \eta(v) - \eta(u) &0 \cr 0 &\eta(v) & 0\cr \gamma(u) &\gamma(v) - \gamma(u) & 1} \right]
$$Il faut maintenant contempler le coefficient $\gamma(v) - \gamma(u)$ en position $(3,2)$ et ne pas oublier que $\gamma$ est INJECTIVE. Le ``gars'' a réussi à aller écrire dans la case $(3,2)$ ce qu'il faut pour tester l'égalité de $u$ et $v$ !!

Juste une petite remarque. On ne peut pas se permettre d'être approximatif ici. Je ne peux pas me permettre de confondre une matrice et sa transposée, je dois mettre un signe $-$ là où il faut ... etc.. Eh bien, tout tourne avec des ``certifications à mézigue''.

Tout le monde se fout de ce qui vient mais moi non. Il faut absolument que $\text{Graal} : \Sigma^* \times \Sigma^* \to M_3(\mathbb \Z)$ soit multiplicatif. Et d'autres propriétés.

[color=#000000]> // On conjugue le monde (G',D') par l'involution Q et on introduit un signe au - au niveau b de G(a,b)
> G := map < SigmaStar -> M3Z | u :-> GMatrix(eta(u), -gamma(u)) > ;
> D := map < SigmaStar -> M3Z | v :-> DMatrix(eta(v), gamma(v)) > ;
> Graal := map < car <SigmaStar,SigmaStar> -> M3Z | uv :-> G(u)*D(v) where u,v is Explode(uv) > ;
> 
> SigmaStar ;
Free finitely presented monoid of rank 3
> u1 := Random(SigmaStar, 10, 19);
> u1 ;
a * b^2 * c * b * a^4 * b
> v1 := Random(SigmaStar, 10, 19);
> v1 ;
b * c^2 * a^2 * b * c * b^3 * c
> Graal(u1,v1) ;
[ 59049 118098      0]
[     0 177147      0]
[ 10450 101533      1]
> 
> u2 := Random(SigmaStar, 10, 19);   
> u2 ;
b^2 * c^3 * b * a^5 * c * b
> v2 := Random(SigmaStar, 10, 19);
> v2 ;
a * c * b * a * b^3 * a * c * a
> 
> Graal(u1*u2,v1*v2)   eq  Graal(u1,v1) * Graal(u2,v2) ;
true
[/color]

@Claude : Très joli texte ! (Je parle de l'introduction de John B. Goode).

$\bullet$ Dernier post là dessus. Je me suis aperçu, dans mon post http://www.les-mathematiques.net/phorum/read.php?16,1989816,1991934#msg-1991934 que je n'avais pas donné la matrice involutive $Q$ qui permet de passer du monde pédagogique $D'(a,b)$, $G'(c,d)$ au monde opérationnel $D(a,b)$, $G(c,d)$. C'est nul. Je répare

[color=#000000]> Q ;
[-1  1  0]
[ 0  1  0]
[ 0  0  1]
[/color]

Rappel pour ceux qui suivent (??) : les $G'(a,b)$ c'est une version bien peinard dans $M_3(\Z)$ du semi-groupe $x \mapsto ax + b$. Il s'agit de twister ce semi-groupe peinard par $Q$ pour créer du mélange ad-hoc dans les composantes

[color=#000000]> GprimeMatrix(a,b) ;
[a 0 0]
[0 1 0]
[b 0 1]
> Q * GprimeMatrix(a,b) * Q ;
[     a -a + 1      0]
[     0      1      0]
[    -b      b      1]
[/color]

Idem pour $D'(c,d)$ autre modèle peinard de $x \mapsto ax + b$, qui commute avec le modèle peinard $G'(a,b)$, et que l'on conjugue par $Q$.

[color=#000000]> DprimeMatrix(c,d) ;        
[1 0 0]
[0 c 0]
[0 d 1]
> Q * DprimeMatrix(c,d) * Q ;
[    1 c - 1     0]
[    0     c     0]
[    0     d     1]
[/color]

$\bullet$ Le ``gars de la mortalité $3 \times 3$'' (terminologie de CC), il a un nom. Je crois qu'il se nomme Parterson (Unsolvability in $3 \times 3$ matrices, 1970), cf la bibliographie bien garnie de Poonen (cf mon post précédent). J'attache une variante de l'énoncé qui provient du petit article (4 pages) de Halava & Harju (qui date 2000) in http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=4D90F1A7A94CADF82EAF38AB6D5265B1?doi=10.1.1.28.4095&rep=rep1&type=pdf

$\def\GL{\text{GL}}$CC
Je réponds à ton avant dernier post. Moi je ne vois pas de groupe libre à une infinité de générateurs mais un semi-groupe libre à un nombre fini de générateurs. Je pense que c'est Paterson (1970) qui a réalisé en particulier un plongement $\Sigma^* \hookrightarrow M_3(\Z)$, pour tout alphabet fini $\Sigma$. Et pas dans $\GL_3(\Z)$.

En tout cas, Halava & Harju l'on fait en 2000, ça c'est sûr.

Mais ce plongement, ce n'est peut-être pas si difficile que cela (mais sûr que je ne l'aurais pas inventé).

MAIS il fallait bien PLUS que cela : DEUX exemplaires de $\Sigma^*$ dans $M_3(\Z)$ qui commutent et qui font que $\text{Graal} : \Sigma^* \times \Sigma^* \to M_3(\Z)$ va écrire ce qu'il faut dans le coefficient d'indice $(3,2)$. Je ne sais pas si tu vois un peu le binz. Faut quand même avoir fricoté pas mal avec les matrices $3 \times 3$ (ce matin pour trouver l'involution $Q$ et les trucs peinards pédagos $G', D'$, j'en ai un peu bavé).

On a besoin de tout ce binz Graal pour fabriquer, à partir d'une instance du problème de Post, une instance du problème de la mortalité (j'espère que je cause dans le bon sens).

Dernier post, promis juré.

$\def\num{\text{numéro}}\def\long{\text{longueur}}\def\Z{\mathbb Z}$CC
Faut encore que j'intervienne. D'abord pour te remercier : l'ouverture de ce fil m'a permis de décanter des choses hier ; sans lui, j'en serais resté à l'état d'insatisfaction d'il y a 4 ans. Ensuite pour dire qu'hier, j'ai eu peur, comme souvent, de confondre ma gauche et ma droite. Et j'ai mentionné que cela aurait été bien de mettre une transposée quelque part afin que la multiplication des matrices soit pareille que la composition des applications affines $x \mapsto ax + b$. Mais absolument pas : POINT de $x \mapsto ax + b$ mais $x \mapsto xa + b$, cf un peu plus loin.

$\bullet$ Je rappelle juste que l'on a la bijection de numération $\gamma : \Sigma^* \to \N$ en base $n$. Et également $\eta : \Sigma^* \to \N^*$ définie par $\eta(u) = n^{\long(u)}$. Je n'ai pas dit que $\eta(uv) = \eta(u)\eta(v)$ parce que cela me semblait évident. J'ai surtout encadré $\gamma(uv) = \gamma(u) \eta(v) + \gamma(v)$. Et j'ajoute l'évidence suivante : la concaténation des mots i.e. $\Sigma^*$, ce n'est pas commutatif. Et donc la pseudo-multiplicativité de $\gamma$, elle est à prendre telle quelle. Point.

$\bullet$ J'ai mentionné le semi-groupe affine $x \to ax + b$. Mais damned, $a,x$ ne commutent pas !!. Il fallait donc que je parle de $x \mapsto xa + b$. Et cela change tout pour la composition : stop à $(f\circ g)(x) = f((g(x))$ et place à $(x)(f \circ g) = ((x)f)g$. Tout rentre dans l'ordre dans ma pauvre tête. Et donc $\Sigma^*$ se plonge bien dans $M_2(\Z)$ par :
$$
u \mapsto \left[ \matrix {\eta(u) & 0\cr \gamma(u) & 1\cr}\right] \qquad\qquad
\begin {array} {c}
\text{comme j'ai fait hier et } \\
\text{PAS par la transposée comme je voulais changer}\\
\end {array}
\qquad\qquad
\left[ \matrix {\eta(u) & \gamma(u)\cr 0 & 1\cr}\right]
$$Personne ne suit alors ? C'est pas bien.

$\bullet$ Puisque j'ai la main, j'en profite pour faire quelques attachements. D'abord la photo de Julia Robinson qui a contribué à la résolution du 10-ème problème d'Hilbert (photo tirée de ``The Autobiography of Julia Robinson'' par sa soeur Constance Reid). Suivi du review à l'époque de l'article des trois DPR (Davis, Putnam, Robinson) : Matiasevich n'est pas encore entré en scène. Et un extrait de la Gazette des Mathématiciens, num. 59, Janvier 1994, Ma collaboration avec Julia Robinson de Matiasevich. Je trouve assez savoureux les propos de Linnik.

$\bullet$ Fosse à purin et tout le fourbi. Pour (mieux) comprendre : Penser les mathématiques, Editions du Seuil, 1982, Séminaire de philosophie et mathématiques de l'Ecole normale supérieure (J. Dieudonné, M. Loi, R. Thom).

$\bullet$ Je termine par une devinette. Champagne à celui qui trouve. On voit une équation dans laquelle tous les symboles $t,a,b, x_i, y_j$ sont dans $\Q$. Quel est l'ensemble des $t \in \Q$ tels que ? Issu d'un autre papier de Poonen qui parle de H10 (Hilbert's tenth theorem) et de la bande des 4 : DPRM theorem (Davis, Putnam, Robinson, Matiyasevich) in http://www-math.mit.edu/~poonen/papers/h10_notices.pdf. Ne pas regarder tout de suite sinon pas champagne.

Salut Claude,

Ta devinette est monstrueuse !
Du coup, j'ai regardé le papier de Poonen et j'ai une question. :-D
L'ensemble diophantien $E$ (sur $\Q$) des $(t,a,b)$ associé à la variété d'alien :-S de Poonen contient $\Z\times\Q^2$.
Est-ce que $E=\Z\times\Q^2$ ?

@cc : Quel est l'ensemble des $t\in\Z$ tels que $\forall a,b\in\Z\;\exists x,y\in\Z\quad (abx)^2+(t-2y)^2=0$ ?

P.S. : Poonen (MIT) n'a pas l'air d'être un blaireau.

Salut Claude,

J'ai l'impression qu'il suffit de trouver $P$ inversible tel que, pour toute matrice $M$, $M_{3,2}=(PMP^{-1})_{1,1}$ ?

Gai-Requin
$\bullet$ En ce qui concerne coefficient $(3,2)$ versus coefficient $(1,1)$, j'ignore si une telle conjugaison à coefficients entiers est possible (cela prouve que je suis un blaireau). Si c'était possible, les gens y auraient pensé ? Champagne si tu me sors $P$. Ou si tu me montres qu'une telle $P$ n'existe pas.

$\bullet$ Et pour tout te dire, je n'avais jamais vu le rapport entre le problème de mortalité pour UN coefficient et le problème de mortalité pour toute la matrice !! Blaireau bis. Pourquoi pas vu ? Parce ce qu'il faut y passer du temps ...etc...

Mais il n'est jamais trop tard (que je dis) car je viens de comprendre le rapport entre le problème de nullité du coefficient $(1,1)$ et le problème de nullité de la matrice. Cf le truc attaché qui provient de http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.4095&rep=rep1&type=pdf. Attention au début, là où j'ai encadré, il faut remplacer $R$ par $S$. On change de semi-groupes. C'est astucieux.

PS1 : encore une fois, il faut du métier pour réaliser le contenu de l'article sur $(1,1)$. Petit papier que l'on peut comprendre sauf qu'il faudrait prendre le temps d'expliquer ce qu'est PCP (Post Correspondence Problem). C'est un peu expliqué mais ... A force de ne pas prendre le temps (histoire d'en gagner, du temps) de se poser et d'expliquer qui est quoi, on finit par en perdre (du temps).

PS2 : mortalité des matrices $3 \times 3$ ... etc.. Je trouve que la terminologie, par les temps qui courent, n'est pas très heureuse. Mais c'est pas de ma faute.

Effectivement les problèmes avec $R$ et $S$ posent pas mal de problèmes. Par contre je ne suis pas d'accord avec toi, on part effectivement de $R$, et $S$ devrait être le plus gros semi-groupe si on suit les notations de la preuve. Mais ça impose bien sûr de changer $S$ en $R$ dans l'énoncé du Théorème...

Vers la fin on a un curieux produit de matrice qui devient un produit d'entiers quand même ! Ça se répare sans trop de difficulté, mais ça pose la question de s'il y a un relecteur dans l'avion tout de même. Jolie preuve en tout cas (tu)

On suppose que $P \in M_3(\Q)$ inversible vérifie: $M_{1,1}=(PMP^{-1})_{3,2}$ pour toute matrice $M \in M_3(\Z)$.
Soit $N \in M_3(\Z)$, alors $NP \in M_3(\Q)$, donc il existe $\lambda \in \N^*$ tel que $\lambda NP \in M_3(\Z)$, donc
si $M=\lambda NP$, alors $(NP)_{1,1}=(PN)_{3,2}$.
Soit $N$ la matrice de permutation de $\sigma$ (c'est-à-dire $Ne_i=e_{\sigma(i)}$), alors $P_{\sigma^{-1}(1),1}=P_{3, \sigma(2)}$. Donc
$\sigma=(23)$ implique $P_{1,1}=P_{3,3}$.
$\sigma =(12)$ implique $P_{2,1}=P_{3,1}$,
$\sigma=(13)$ implique $P_{3,1}=P_{3,2}$.
$\sigma=Id$ implique $P_{1,1}=P_{3,2}$.
Donc $P_{3,1}=P_{3,2}=P_{3,3}=P_{1,1}$.

Si $N=\pmatrix{1 & 0 & 0 \\ 0 & 0 &0\\0 & 0 & 0}$, alors $P_{1,1}=0$

Donc la dernière ligne de $P$ est nulle, donc $P$ n'est pas inversible.

$a$ n'est pas un carré ssi il existe $x\in \N, y\in \N, z \in \N, (y+z+1-2x)^2 + (a-x^2-y-1)^2=0$.

Marco,
Vas-y mollo car moi, des cadeaux, je n'en ai pas beaucoup. Je ne suis qu'un modeste retraité, égaré sur un fil de logique ...etc...
Ok pour les non carrés.

Quant à ton dernier post, euh ... c'est-à-dire que ... euh (bis). Est ce que tu connais un peu (ou beaucoup) ``ces choses là'' ??

Bon, allez, encore un petit cadeau. L'ensemble $A$ des entiers $a$ NON puissances de 2 est diophantien : $a$ n'est pas une puissance de 2 ssi il existe $x \in \N$, $y \in \N$ tels que $a = (2x+3)y$. J'espère qu'il n'y pas d'erreur (cela pourrirait le cadeau).

Je te laisse le complémentaire ?

Marco,
$\bullet$ Attention : ce n'est PAS vrai que le complémentaire d'un diophantien soit diophantien. Et il y a derrière ce résultat apparemment négatif quelque chose de profond. Mais pour l'instant, en disant cela, je pense que l'on ne saisit pas le sel de l'affaire. Il faut laisser des choses se mettre en place, à mon avis.

$\bullet$ Mais comme tu as participé, j'ai raclé mes fonds de tiroir et dégotté encore un petit cadeau. C'est une AUTRE définition de diophantien. Je vais appeler cette nouvelle définition (Y), et l'ancienne (X).

$A \subset \N$ est diophantien au sens (Y) s'il existe $F \in \Z[X_1, \cdots, X_p]$ tel que $A$ soit l'ensemble des valeurs POSITIVES ou NULLES prises par $F$ sur $\N^p$. Formellement :
$$
\text {définition }(Y) : \qquad \qquad A = \N \cap F(\N^p)
$$On peut même permettre aux indéterminées de varier dans $\Z$ au lieu de $\N$, à condition de changer $F$ d'où une autre définition $(Y')$. Bon, je change le nom : s'il existe $G \in \Z[Y_1, \cdots, Y_q]$
$$
\text {définition }(Y') : \qquad \qquad A = \N \cap G(\Z^q)
$$
Alors diophantien au sens (X) pareil que (Y) pareil que (Y').

C'est le cadeau ? Oui. Accompagné d'un petit bonus dit Putnam trick à savoir le petit polynôme de rien : $(t+1)(1 - y^2) - 1$. Quelles sont les valeurs $\ge 0$ prises par ce polynôme sur $\N \times \N$ i.e. lorsque $t, y \in \N$ ?

En résumé : deux (petits) cadeaux. Tu prends ? Après, je n'ai plus rien (que je dis).

claude quitté a écrit:

@Poirot
Je ne comprends pas ce que tu me dis dans tes 3 premières lignes.

Dans la preuve, tout est fait comme si le semi-groupe de départ (celui pour lequel on veut prouver que le problème de mortalité est indécidable) est $R$, et non pas $S$. Regarde la conclusion : il existe un élément de $R$ dont le coefficient $1,1$ est nul ssi $0 \in S$. Le problème de détection de $0$ dans $S$ étant indécidable, on en déduit bien l'indécidabilité du problème de mortalité dans $R$.

Bon je viens de comprendre que le problème de mortalité n'est pas le problème de l'existence d'une matrice dont le coefficient $1,1$ est nul, c'est donc moi qui ai inversé les choses.

Poirot,
Si tu as 5 minutes, c.a.d. une demi-heure, cela serait chouette. Car moi, j'ai toujours avoué avoir des problèmes avec ma gauche et ma droite. Mais PAS que. Et là, j'ai un problème de SENS d'instance.

Car je pense qu'il y a quand même une erreur dans le th 4 de http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.4095&rep=rep1&type=pdf Or ces gens sont des spécialistes et moi je ne suis qu'un clampin de passage (mais qu'est ce que je fais ici ?). Une précision : le papier n'est pas un article publié mais un rapport interne, nuance. Résumons : je pense qu'il y a une erreur mais je sais par ailleurs que j'ai des problèmes avec ma gauche et ma droite.

Oublions les lettres $R,S$ et même le contenu de la preuve. De quoi s'agit -il ? De deux problèmes (je ne remets pas un contexte complet i.e. je ne préciserais pas de type fini ni $M_3(\Z)$)

A. Le problème de la nullité du coefficient $(1,1)$ : indécidable car ``se ramène'' au problème de la correspondance de Post. Disons qu'il est indécidable. Point.

A'. Problème de la nullité d'une matrice : tester si 0 est dans le semi-groupe. Dont on veut montrer qu'il est indécidable.

Que faut-il faire pour montrer que A' est indécidable par utilisation de A ? Partir d'une instance QUELCONQUE i.e. générale de A i.e. un semi-groupe $S$ et construire un semi-groupe $S'$ vérifiant :
$$
0 \in S' \qquad \iff \qquad \exists M \in S \quad \mid \ M_{11} = 0 \qquad\qquad (*)
$$Supposons que cette construction soit faite. Eh bien, que je dis, A' est indécidable. En effet, la situation contraire serait de pouvoir décider $0 \in S'$ donc de l'existence d'une $M \in S$ telle que $M_{11} = 0$, chose indécidable VU QUE l'ON EST PARTI d'un $S$ QUELCONQUE.

Et la chose à réaliser est donc $(*)$ : partir de $S$ et produire $S'$ tel que.

Et que se passe-t-il dans la preuve du théorème 4 ? Après avoir corrigé $S$ versus $R$ là où il faut.

@Christophe: pour (1) implique (2), on considère un polynôme $P(x)$ sans zéro, et on le rend homogène: $Q(x,y)=P(x/y)y^d$ si $d$ est le degré du polynôme $P$. Donc $Q(x,y)=0$ implique $x=y=0$.
Pour (2) implique (1), si $P(x,y)=0$ implique $x=y=0$, on choisit $y=1$, alors $P(x,1)=0$ n'a pas de solution. C'est intéressant aussi.