Décidabilité en géométrie et algèbre

Je t'aurais pensé suffisamment perspicace pour constater l'aspect hors sujet de tout
ceci dans le fil en question... d'où tes messages effacés.
Ouvrir une autre discussion s'imposait, ce que tu viens de faire.
Je me permet d'en changer le titre.

Eric

Mon cher Ga?
Je n'aurais pas dû répondre à Christophe mais je voulais savoir s'il était aussi fort en décidabilité qu'il le laissait paraître!
Ce n'était pas bien méchant!
On peut en tout cas décider qu'il l'est plus que moi!
Amicalement

Pour que le fil ne meurt pas totalement, je donne un détail sur l'algorithme en question:

soit une famille de polynomes $P_1,...,P_n, Q_1,...Q_p$.

Il suffit d'exprimer $Z:=\exists x: P_1(x)=0\wedge ...\wedge P_n(x)=0\wedge Q_1(x)>0\wedge ...\wedge Q_p(x)>0$ sous forme d'un énoncé E sans quantificateurs, avec des "ou" et des "et" des $=$, des $>$, des polynomes en les coefficients des $P_i,Q_j$. Sachant "qu"on ne sait rien" des paramètres (ie des coefficients des $P_i,Q_j$) et donc rigoureusement ce qui doit être obtenu est $(\forall a\forall b...: Z)\iff (\forall a\forall b...: E)$ où $a,b,..$ sont les paramètres.
Ca c'est pour $(\R,+,\times)$ et c'est rendu possible par la technique des "tableaux de variations" (mais je sais pu comment, si je l'ai jamais su un jour d'ailleurs en gros on sait qu'un "x" existe quand des conditions beaucoup plus laches existent par le TVI)

Lorsque vous avez affaire à $(\C,+\times)$ c'est un peu plus simple (dans mon souvenir) car il n'y a que $=$ et $\neq $ à gérer et j'ai vaguement l'impression qu'on peut même se passer de $\neq$, ie ramener

$\exists x: P_1(x)=0\wedge ...\wedge P_n(x)=0$ (probablement qu'un histoire de résultant suffit???)

à un énoncé avec des $=$ et des polynomes des "et" et des "ou".

Celles et ceux qui voudraient plus de détails, Ga? connait probablement parfaitement cet aspect.

Pour la partie logique:
1) tout énoncé est équivalent à un énoncé sous forme prénexe
2) la partie ouverte (celle qui suite les quantificateurs) peut être mise sous forme d'une disjonction de conjonctions
3) un $\exists $ devant des "ou" se distribue, ie $(\exists x: A\vee B\vee C... )\iff [(\exists x A)\vee (\exists x \vee ...$. On n'a donc qu'à traiter le cas $\exists x: A\wedge B\wedge C... $

Ah oui, merci beacoup!

Le pire c'est que par deux fois j'ai eu "le sentiment" que $\neq$ n'était pas nécessaire exactement pour la raison que $x\neq y\iff \exists t: tx=ty+1$ autrement dit, presque au sens propre j'ai marché sur la tête (j'ai renversé l'argument invalidement)

J'essaie de faire le même genre de post que le précédent, mais dans le cadre de $(\R,+,\times)$

1) On n'a qu'à traiter la situation: $\forall x: [ P_1(x)> 0\vee ...\vee P_n(x)> 0 \vee Q_1(x)=0\vee ...\vee Q_p(x)=0 ]$

2) Ce qui se ramène à traiter une situation $\forall x: [ P_1(x)> 0\vee ...\vee P_n(x)> 0 \vee Q(x)=0 ]$

3) qui s'écrit aussi: $\forall x: [ (P_1(x)\leq 0\wedge ...\wedge P_n(x)\leq 0 ) \to Q(x)=0 ]$

4) qui s'écrit aussi: $\forall x: [ f(x)\leq 0 \to Q(x)=0 ]$

où $f:=(x\mapsto max_i P_i(x))$

Mais $a=0$ peut s'écrire $a\leq 0$ et $-a\leq 0$

donc on peut traiter seulement les situations

5) $\forall x: [ f(x)\leq 0 \to Q(x)\geq 0 ]$

6) qui revient à $\forall x: g(x)\geq 0$

car il y a équivalence entre:
6.1) $a\leq 0$=> $b\geq 0$
6.2) $max(a,b)\geq 0$

où $g$ continue est écrite avec des opérations polynomiales et le signe $\sigma$ qui désigne $x\mapsto max(0,x)$ qui est dérivable partout sauf en $0$ et dont en plus la dérivée est très simple.

7) On n'a plus alors qu'à étudier les antécédents par $g'$ la dérivée de $g$ de $0$, ainsi que les éléments qui ne sont pas dans le domaine de $g'$, et pour chacun $x$ d'eux, se demander si $g(x)\geq 0$.

8) Pourra-t-on exprimer l'énoncé $\forall x: g(x)\geq 0$ comme un énoncé qui est une combinaison booléenne de propriétés polynomiales et "u>v", "u=v" concernant les paramètres apparaissant dans $g$? That is the question... (Peut-être bien que non)

Bon pour le cas réel, j'ai parcouru assez "lentement" les pages 40-80 (où tout semble se jouer), mais y a quand-même du travail à faire pour trouver où se trouve l'idée-clé (je ne l'ai pas trouvée encore) qui débloque le chemin. En tout cas, j'ai vu qu'ils se servent du fait qu'une conjonction de $a_i=0$ peut se réécrire en $\sum a_i^2=0$ ce que je n'ai pas utilisé à mon dernier post sur la question et ce qui aurait dû me mettre la puce à l'oreille.

J'ai l'impression que le livre (du moins ces pages) travaille dur à "formaliser" un argument qui permet de raisonner par récurrence sur un algorithme de "tableaux de variation" et c'est effectivement ce qui me pose problème (bon d'un autre côté, j'ai fait tellement de tableaux de variation dans ma vie )

Bon bin, ça m'a tellement épuisé que je n'ai pas regardé le cas $\C$ encore merci pour ce joli livre (qui fait 700 pages!!!!!)

Merci infiniment effectivement ce document a l'air plus facile à digérer*****!!! Je suis au travail (et poste de ma classe dans un lycée entièrement informatisé, lol vive matrix) et regarderai plus en détails ce soir (j'en ai soif car même après reflexion dans mon trajet métro, je n'ai toujours pas trouvé seul** comment éliminer le "il existe x " de $\exists x: P_1(x)>0\wedge...\wedge P_n(x)>0\wedge Q(x)=0$ et je pense que des arguments importants qui me manquent sont vraiment nécessaires

** pourtant j'ai traficoté dans tous les sens en imagination

Oui, la borne de complexité, j'avais entendu dire qu'il existe un preuve*** qu'elle ne peut être moindre que celle que tu dis et j'ai dû me tromper en évoquant la tour d'exponentielle. Je regarderai dans l'autre document

*** (et pas seulement un résultat du genre: "la meilleure efficacité connue est..." mais je peux me tromper)

***** Quelle patience tu as même mis un exemple détaillé page 14 à ce que j'ai vu!

Pardon, au fait, je m'adressais à Ga? que je remercie à nouveau d'ailleurs pour ces documents importants

Merci beaucoup, j'imprimerai le chapitre1 intégralement demain alors!

@JLT, je suis trop pressé pour te répondre en détail, mais oui, si on en croit ce qu'a annoncé Ga? sur le fait que la complexité augmente surtout avec les alternances de quanteurs (enfin spéculons que oui), alors ta famille de questions qui s'expriment sous la forme (sous IR) :

$\forall x_1,...,x_n: P(x_1,...,x_n)\neq 0$ ***

doit pouvoir "se calculer" honorablement rapidement

Je viens d'imprimer (et en couleurs STP!!) le chapitre1 de Ga? Je te ferai une fiche de lecture soignée dès que j'aurai compris le truc qui me manque

*** P1 non nul ou P2 non nul ou .. Pn non nul ou Q nul se dit:

P1 non nul ou ... ou Pn non nul ou 1-tQ non nul (en rajoutant un "quelque soit t")

qui se dit: pour tous .....: [ P1² + ... + Pn² + (1-tQ)² ] non nul

ie qui se dit "il n'existe pas de x1,x2... tels que R(x1,..)=0"

@JLT, bon tu as posé plusieurs questions, j'essaie déjà de te préciser du mieux possible ce dont on parle et de te répondre.

1) Dans le cas des nombres complexes (ou des corps algébriquement clos de caractéristique 0), si on note $Z(P)$ l'ensemble des racines du polynome $P$ alors la question de savoir si $Z(P_1)\cap ...\cap Z(P_n) \subseteq Z(Q)$ est "facile" dans le sens où elle s'exprime en une question équivalente qui s'écrit avec des "et" , des "ou", des $=$ des $\neq$ , des expressions algébriques avec $+, \times, 0,1$ et des coefficients des $P_i, Q$.

2) Autrement dit on peut, sans rien connaitre des coefficients des $P_i, Q$ trouver un énoncé sans quantificateurs $E$ tel que: $\forall a_1,...,a_k [(\forall x: P_1(x)=0\ et ... \ et P_n(x)=0 \ implique Q(x)=0)\iff E]$ où les $a_i$ sont les variables libres apparaissant dans les $P_i,Q$ (ce qu'on appelle généralement les paramètres)

3) Pour prouver (1) et (2), pense à la forme scindée des polynomes. Dire que tous les zéros communs aux $P_i$ sont des zéros de $Q$ revient à demander que $Q$ mis à une puissance assez grande mais effectivement exprimable uniformément soit un multiple du PGCD des $P_i$, or le PGCD des $R_i$ se calcule facilement, même s'il ya plusieurs cas (ce "plusieurs cas" se traduira par des "et" des "ou" rajoutés)

4) Dans le cas de $\R$ c'est nettement plus difficile, mais j'y viens dans la suite (j'ai identifié les passages du doc mis en lien par Ga? )

5) Pourquoi faire tout ça?

5.1) Soit $K$ un corps (un des deux corps $\R,\C$)

5.2) Un énoncé écrit avec les signes $\forall, \exists , et, ou, =,\neq, 0,1,+,\times, variables,>$ (le strictement supérieur ne concerne que $\R$) peut être vrai ou faux (comme tu sais ) et s'il contient des variables libres il détermine une application qui envoie chaque uplet de valeurs sur $\{vrai, faux\}$

5.3) Tu sais que chaque énoncé (dans toute théorie) écrite avec des "et","ou" peut s'écrire sous la forme d'une conjonction de disjonctions tout aussi bien que sous la forme d'une disjonction de conjonctions

5.4) Maintenant imagine que tu as un $\exists x$ devant une disjonction: $\exists x: D_1\ ou ... \ ou \ D_n$. Et bien c'est équivalent à $(\exists xD_1)\ ou ... \ ou \ (\exists xD_n)$

5.5) De même en ce qui concerne $\forall$ avec les conjonctions

5.6) Par ailleurs, quand tu mets un "non" devant un énoncé, tu peux le distribuer jusqu'à plus possible via:
5.6.1) $non(\forall xP)$ qui devient $\exists x(nonP)$
5.6.2) $non(A\ et\ $ qui devient $(nonA)\ ou\ (nonB)$
5.6.3) $non(A\ ou\ $ qui devient $(nonA)\ et\ (nonB)$
5.6.4) $non(a=b)$ qui devient $a\neq b$
5.6.5) $non(a\neq b)$ qui devient $a=b$
5.6.6) $non(a>b)$ qui devient $a=b$ ou $b>a$

5.7) Dans le cas précis de $\R$: $P=0\ et\ Q=0$ peut devenir $P^2+Q^2=0$
5.8) Dans tous les corps $P=0\ ou\ Q=0$ peut devenir $PQ=0$

5.9) En 5.7,5.8 j'ai mis des majuscules mais elle désignent n'importe quoi

5.10) Le bilan de 5.2-5.9 est la chose suivante:

5.10.1) (Cas $\C$): [size=x-large]SI[/size] on peut éliminer la quantification $\exists x$ dans n'importe quel énoncé $\exists x: P_1(x)=0\ et\ P_2(x)=0\ et\ ...\ et\ P_n(x)=0\ et\ Q(x)\neq 0$ [size=x-large]ALORS[/size] n'importe quel énoncé de la théorie de $(\C, +, \times)$ (avec ou sans paramètres, ie variables libres) peut de manière effective être démontré équivalent à un énoncé (contenant les mêmes variables libres) et qui est sans quantificateur

5.10.2) (Cas $\R$): [size=x-large]SI[/size] on peut éliminer la quantification $\exists x$ dans n'importe quel énoncé $\exists x: P_1(x)>0\ et\ P_2(x)>0\ et\ ...\ et\ P_n(x)>0\ et\ Q(x) = 0$ [size=x-large]ALORS[/size] n'importe quel énoncé de la théorie de $(\R, +, \times)$ (avec ou sans paramètres, ie variables libres) peut de manière effective être démontré équivalent à un énoncé (contenant les mêmes variables libres) et qui est sans quantificateur

5.10.3) Remarque: une fois ça fait, les théories $(K,+,\times)$ sont du coup récursives pour ces corps-là, ie il y a un algorithme qui dit si un énon cé clos (sans variable libre) est vrai ou faux

5.11) Il reste donc les cas techniques 5.10.i à traiter.
5.11.1) Le cas 5.10.1) est facile et (sauf erreur) traité en (3) ou à un de mes posts précédents
5.11.2) Le cas 5.10.2) est traité dans le DEUXIEME lien (pdf d'une soixantaine de pages) mis par Ga? entre les pages 1 et 10 environ. Je ne peux pas te résumer car, comme c'est un mécanisme calculatoire, je l'ai un peu lu, mais ne l'ai pas encore "intégré". Mais pour toi, ça devrait nromalement être du gateau. Je crois que les pages 1-10 en question font plus que dire si "oui ou non" $\exists x: P_1(x)>0\ et\ P_2(x)>0\ et\ ...\ et\ P_n(x)>0\ et\ Q(x) = 0$: elles associent de manière effective le nombre de réels différents $x$ qui marchent à une formule sans quantificateur dont les variables libres sont les paramètres

6) Dans un post ultérieur j'essairai de connecter ça avec ta question.

Voilà, il ne reste plus qu'à cliquer sur son lien et à lire les premières pages.

@JLT et Ga?

je n'ai pas oublié, j'ai même passé probablement 1H ce matin à lire les pages 1-16 (et surtout 1-10 et 14-16). Hélas, mes handicaps calculatoires + ma non maitrise de l'anglais m'empèchent de "capter" le truc***. De toute façon ça a tjs été comme ça (je me demande s'il m'est déjà arrivé de lire quelque chose où finalement, je ne vois pas un peu d'avance l'idée des auteurs et où après coup je comprends, voire je me demande s'il m'est déjà VRAIMENT déjà arrivé de lire "quelque chose" :X :X au cours de ces 50 dernières années).

*** le théorème de Sturm, etc, avec les tableaux de signes-variations

Bon, j'abandonne pas, je m'y remettrai, mais, à JLT, la fiche de lecture promise n'est pas pour ce WE (enfin ça m'étonnerait)

Oui, je suis bien d'accord -D (en fait, c'était une politesse de principe parce que je l'avais promise quelques posts avant), j'espère surtout (car c'était ce qui semblait lui poser souci) que nos quelques posts précédent lui a permis de comprendre "le plan" de notre discussion, ie de comprendre de quoi on parlait et "pourquoi le théorème de Sturm" est "le produit" qui va tout faire marcher.

si tu captes avant moi une manière de me faire "capter" Sturm sans passer par des étapes "calculatoires", je te ferai un gros bisou!

bin t inviter a "l entrecote " a montparnasse c est un peu cher pour moi apres ces deux annees de vacances ou j ai explose mon compte en banque et alors que j ai gratis le lien de Ga imprime sous la main. Mais enregistre le toi aussi: en gros Sturm je peux tjs l admettre et appliquer l algo il me reste.plus grand chose a capter a part me representer mentalement une demo ou un "why". J ai fini par comprendre ce que veut dire "remainder" .

Pour moi je crois surtout que le plus torturant pour moi c est ce qui se passe page 9-10 y a des matrices et puis apres des histoires de "leading coefficients" et la mon pauvre anglais . . .

poste de mon tel sorry pour la frappe

J'ai rajouté les numéros des pages du doc en rouge

Bonjour,

Oui: Hourya Sinaceur - Corps et Modèles - Collection Mathesis chez Vrin - Janvier 1991 (il valait quand même 198 F à l'époque !).
C'est là aussi que j'ai vu pour la première fois ce théorème.

Cordialement,

Rescassol

Pour ceux que ça intéresse, voici deux nouveaux liens mis par Meu qui sont très proches du sujet: http://www.les-mathematiques.net/phorum/read.php?2,549404,776883#msg-776883

J'avais posé la question parce que ça me turlupinait un peu l'idée d'éliminer non pas UN "il existe x", mais d'un coup tous les " $\exists x_1,\exists x_2..,\exists x_n$" à la file dans une succession de quanteurs

Ca semble peu probable qu'il y ait quelque chose de ce genre qui soit possible pour donner une sorte de "toute autre" preuve du même résultat (récursivité de la théorie de $\R$ )

Ah!!! merci infiniment pour cette réponse. [size=x-small]Je suis trop mauvais en calcul différentiel pour m'être assuré (l'autre jour dans le métro) de cette finitude.... euuu... je suis entrain de dire n'importe quoi en relisant ton post.

En fait, je pensais aux points $(x,y)$ qui minimisent $|P(x,y)|$[/size]

En fait, tu veux dire qu'on "joue sur l'ensemble vide"? ie qu'on remplace "$ \{(x,y) | P(x,y)=0\}\neq \emptyset$ par "tel calcul différentiel qui cherche un minimum dans cet ensemble dont on ignore s'il est vide le trouve?" (c'est rigolo ça, je comprends mieux tes rappels sur l'ensemble vide maintenant -D )

Merci! (Et j'imagine que l'outil académique pour ce faire va entre autre être de manipuler des dérivées partielles dans tous les sens (et même pire, puisque qu'on minimise sous contrainte. Là, je crois que je ne pourrai pas entrer dans ce territoire dangereux pour moi )

Il paraît que l'éducation passe par un traumatisme.

10 paressent 10 contre 1

S