Prérequis pour apprendre le GCT

Il semble que la théorie de la complexité géométrique nécessite une connaissance approfondie des mathématiques pures telles que la géométrie algébrique, la théorie de la représentation.

Bien que je sois un étudiant en informatique et que je n’ai PAS de cours de mathématiques très abstraites et pures, ce programme m’intéresse.

Existe-t-il une liste de "connaissances minimales" pour apprendre cette théorie?

Cette liste comprend des notes de cours de départements de mathématiques ou de mathématiques, des enquêtes sur des revues ou des conférences, ainsi que des manuels de mathématiques pures.

[ EDIT: Ajouté plus tard ] Merci pour vos commentaires.

Théorie générale de l'informatique: j'ai lu le livre de Sipser intitulé "Introduction à la théorie du calcul"

Théorie de la complexité: Je m'intéresse particulièrement aux modèles concrets pour les limites inférieures de la complexité. C'est ainsi que j'ai lu la partie des "limites inférieures concrètes" du manuel d'Arora-Barak. J'ai aussi des connaissances de base dans plusieurs chapitres du livre sur la complexité de la communication écrit par Nisan.

Mathématiques de base: J'ai appris l'algèbre linéaire fondée sur les preuves, telle que la définition générale de l'espace vectoriel, etc., et plus précisément l'argument de calcul basé sur l'argument epsilon-delta.

Algèbre: j'ai appris sur la définition et les exemples de groupe, anneau et champ. J'avais un cours pour les étudiants, et je n'ai pas appris la théorie générale de ces systèmes algébriques.

La réponse courte : la connaissance minimale des mathématiques pour comprendre la première moitié du plan de GCT, une fois que vous avez vu un peu de groupes, de cercles et de champs, est décrite dans le chapitre 3 de ma thèse (fiche éhontée ). Ce chapitre est cependant incomplet dans la mesure où je n’aborde pas la théorie de la représentation. La théorie de la représentation est cruciale pour la seconde moitié du plan (c'est pourquoi je travaille à étendre ce chapitre pour l'inclure).

Si vous voulez vraiment entrer dans GCT, Symétrie, représentations et invariants de Goodman et Wallach et Actions et invariants des groupes algébriques de W. Ferrers Santos sont à la fois relativement autonomes et disposent de beaucoup de bonnes informations pertinentes pour GCT. Je ne sais pas si ce sont les meilleures sources à apprendre, car je ne les ai appris qu'après avoir appris beaucoup de ce matériel, mais ils sont bons en ce qui concerne le rapport entre ce qu'ils couvrent et ce qui est pertinent pour le GCT. Fulton and Harris est idéal pour la théorie de la représentation et de nombreux exemples / exercices dans le livre sont pertinents pour GCT.

La réponse la plus longue : comme Vijay l’a souligné, cela dépend vraiment de ce que vous voulez apprendre et de son importance. Les sujets ci-dessous sont ce que je pense être le fond nécessaire, puisque telle était la question. Je ne suis pas sûr qu'il s'agisse d'une liste complète - je vous recommanderais d'essayer de lire certains des articles sur le GCT et, lorsque vous vous perdez, allez chercher des informations de base. Au fur et à mesure que vous apprenez la matière de base, revenez de temps en temps aux documents du GCT et voyez si vous pouvez continuer.

(En fonction de ce que vous voulez apprendre, je ne suis vraiment pas d'accord avec Zeyu sur le fait que vous devriez d'abord essayer une algèbre commutative diplômée, bien que cela devienne nécessaire à un moment donné pour apprendre le GCT.)

Si vous voulez comprendre, par exemple, le récent document FOCS de Mulmuley , vous voudrez comprendre:

• le principe de dureté contre le hasard (voir Impagliazzo - Kabanets , et peut-être aussi la liste des articles de Bill Gasarch sur la dureté v aléatoire )
• géométrie algébrique de base jusqu’à Nullstellensatz de Hilbert et au lemma de normalisation de Noether. Ceux-ci peuvent être trouvés dans n'importe quel manuel de base sur la géométrie algébrique et probablement dans la plupart des notes de cours à ce sujet.
• une théorie invariante classique (vous n'avez pas vraiment besoin de la théorie invariante géoélectrique, des schémas et du livre de Mumford-Fogarty-Kirwan pour cet article). Le livre de Sturmfels, Algorithms in Invariant Theory, me vient à l’esprit.
• Pour certains résultats dans le document, mais en aucun cas pour le document en général, vous voudrez peut-être en obtenir certains (et ces références se trouvent également dans le document): théorie de la représentation de comme dans Fulton et Harris , résultats sur les invariants de la matrice [ Artin, Procesi, Razymslov], ...$SL_n$

Si vous voulez comprendre les grandes lignes de l’approche GCT mais en détail mathématique , je vous suggère:

• Le problème permanent versus déterminant. # P-complétude du déterminant permanent et GapL-complétude. Agrawal a une bonne étude (très légèrement dépassée) à ce sujet, et les preuves de sa complétude se trouvent dans le livre de Burgisser intitulé Completeness and Reductions in Allebraic Complexity Theory .

• Groupes et actions de groupe (les groupes algébriques et les actions de groupe algébriques sont utiles, mais pas nécessaires à ce niveau). Vous devriez comprendre le théorème Orbit-Stabilizer.

• Géométrie algébrique affine à travers le Nullstellensatz de Hilbert. En gros, il vous suffit de comprendre la correspondance entre les variétés algébriques affines et leurs anneaux de coordonnées.

• Théorie de base de la représentation de comme dans Fulton et Harris . Outre les définitions de base, vous devez connaître la réductibilité complète de ces représentations et le fait que les représentations de sont classées par partitions, mais vous n'avez pas nécessairement besoin de connaître les preuves / constructions de ces dernières.$GL_n$$GL_n$

Si vous voulez comprendre profondément ce qui se passe (et je ne suis pas sûr de pouvoir prétendre être encore là, mais je pense savoir ce que j'ai besoin de savoir pour y arriver), vous devriez probablement aussi comprendre:

• Structure des groupes algébriques réducteurs et des fermetures d’orbite dans leurs représentations. J'aime le livre de W. Ferrers Santos pour cela, mais aussi les groupes algébriques linéaires de Borel , les groupes classiques de Weyl et d'autres classiques.

• Les machines de Luna-Vust (théorème de tranche de Luna, complexité de Luna-Vust)

• Dualité tannakienne (voir le document de Deligne - Milne ; ce sera une lecture difficile sans connaissances de base en théorie des catégories et en groupes algébriques affines). Cela dit essentiellement que "les groupes algébriques (pro-) affines sont déterminés par leurs représentations". Je ne pense pas que vous ayez besoin de tout le papier, mais plutôt de récupérer un groupe de sa catégorie de représentations (Cor. 3.4).

• Plus de théorie de la représentation , notamment en ce qui concerne les anneaux de coordonnées de groupes algébriques et leurs fermetures d’orbite. J'aime beaucoup le livre de Goodman et Wallach pour cela, en particulier parce qu'il est fondamentalement autonome et qu'il contient tout ce dont vous avez besoin pour comprendre le GCT. (En outre, bon nombre des sections et des exercices relatifs à Fulton et Harris sont pertinents pour GCT, en particulier ceux concernant les coefficients de Littlewood-Richardson et de Kronecker.)

Si vous voulez réellement travailler sur la théorie de la représentation , vous voudrez probablement comprendre davantage de combinatoire algébrique / théorie de représentation combinatoire. Je ne connais pas vraiment toutes les bonnes références à cet égard, mais il est certainement essentiel de comprendre la règle de Littlewood-Richardson et le livre de Fulton, Young Tableaux, est bon pour cela.

Les documents les plus récents sur ce côté des choses que je connais sont Blasiak , Kumar et Bowman, De Visscher et Orellana .

En fonction de la direction dans laquelle vous souhaitez aller, vous pouvez également vous pencher sur les groupes quantiques, bien que cela ne soit pas nécessairement nécessaire (remarque: il ne s'agit pas d'un cas particulier de groupes, mais plutôt d'une généralisation dans une certaine direction).

Du côté plus géométrique des choses que vous aurez envie de regarder des choses comme la géométrie différentielle pour les espaces tangents et osculatrices, courbure, variétés doubles, etc., qui sont sous - jacent le plus connu minorant perm contre det en raison, Mignon - Reessayre et suivi de Landsberg - Manivel - Ressayre . ( Mignon - Ressayre peut être compris sans aucune de ces choses, mais vous pouvez voir son papier de manière approximative comme étudier la courbure de certaines variétés; pour une vue moins vague, voir l’utilisation des variétés doubles dans Landsberg - Manivel - Ressayre . ) (Voir aussi Cai, Chen et Li , qui étend Mignon - Ressayre à toutes les caractéristiques étranges.) Voir aussi Landsberg et Kadish .

Si l'approche de la multiplication matricielle par le GCT vous intéresse , il est question de grade de tenseur, de rang de frontière et de variétés sécantes. Je suggérerais de consulter les documents de Burgisser - Ikenmeyer , Landsberg et Ottaviani , Landsberg , le sondage et le livre de Landsberg . Bien sûr, il serait également bon de connaître les techniques classiques de la multiplication matricielle (limites supérieure et inférieure), mais c’est une boîte de Pandore tout à fait séparée.