La complexité algorithmique est l'étude des ressources nécessaires — le temps, la mémoire, … — pour résoudre un problème de manière algorithmique. Dans ce cadre, la théorie de la complexité algébrique est l'étude de la complexité algorithmique de problèmes de nature algébrique, concernant des polynômes.Dans cette thèse, nous étudions différents aspects de la complexité algébrique. D'une part, nous nous intéressons à l'expressivité des déterminants de matrices comme représentations des polynômes dans le modèle de complexité de Valiant. Nous montrons que les matrices symétriques ont la même expressivité que les matrices quelconques dès que la caractéristique du corps est différente de deux, mais que ce n'est plus le cas en caractéristique deux. Nous construisons également la représentation la plus compacte connue du permanent par un déterminant. D'autre part, nous étudions la complexité algorithmique de problèmes algébriques. Nous montrons que la détection de racines dans un système de n polynômes homogènes à n variables est NP-difficile. En lien avec la question « VP = VNP ? », version algébrique de « P = NP ? », nous obtenons une borne inférieure pour le calcul du permanent d'une matrice par un circuit arithmétique, et nous exhibons des liens unissant ce problème et celui du test d'identité polynomiale. Enfin nous fournissons des algorithmes efficaces pour la factorisation des polynômes lacunaires à deux variables. / Computational complexity is the study of the resources — time, memory, …— needed to algorithmically solve a problem. Within these settings, algebraic complexity theory is the study of the computational complexity of problems of algebraic nature, concerning polynomials. In this thesis, we study several aspects of algebraic complexity. On the one hand, we are interested in the expressiveness of the determinants of matrices as representations of polynomials in Valiant's model of complexity. We show that symmetric matrices have the same expressiveness as the ordinary matrices as soon as the characteristic of the underlying field in different from two, but that this is not the case anymore in characteristic two. We also build the smallest known representation of the permanent by a determinant.On the other hand, we study the computational complexity of algebraic problems. We show that the detection of roots in a system of n homogeneous polynomials in n variables in NP-hard. In line with the “VP = VNP ?”question, which is the algebraic version of “P = NP?” we obtain a lower bound for the computation of the permanent of a matrix by an arithmetic circuit, and we point out the links between this problem and the polynomial identity testing problem. Finally, we give efficient algorithms for the factorization of lacunary bivariate polynomials.

La fonction de Möbius est définie par$$\mu(n)= \begin{cases} 1 & \textit{si $n=1$},\\ (-1)^k& \textit{si n est le produit de k nombres premiers distincts,}\\ 0 & \textit{si n contient un facteur carré. } \end{cases}$$Nous avons démontré que pour $x \ge \exp( 10^9) $ et $h=x^{1-\frac{1}{16000}}$, il existe dans chaque intervalle $[x-h,x]$ des entiers $n_1$ avec $\mu(n_1)=1$ et des entiers $n_2$ avec $\mu(n_2)=-1$.\\Ce résultat est une conséquence d'un résultat plus général.\\Pour $x \ge \exp(4\times 10^6)$, $\frac{1}{\sqrt{\log x}} \le \theta \le \frac{1}{2000}$, $h=x^{1-\theta}$ et $Q=(x/h)^{\frac{1}{20}}$, nous avons \\$$\sum_{q \leq Q} \log(Q/q)\sum_{\chi mod q}^*\left| \sum_{x.-h\le n \le x} \mu(n) \chi(n) \right| \leq 10^{20} h \theta \log(x) \exp( \frac{-1}{300 \theta}); $$la somme $\sum^*$ portant sur les caractères primitifs sauf l'éventuel caractère exceptionnel.\\Et en particulier pour $x \ge \exp( 10^9)$,$$ \left | \sum_{x.-x^{1-\frac{1}{16000}}\le n \le x} \mu(n) \right | \le \frac{1}{100} x^{1-\frac{1}{16000}}.\\$$ / The Möbius function is defined by$$\mu(n)= \begin{cases} 1 & \textit{if $n=1$},\\ (-1)^k& \textit{if n is a product of k distinct prime numbers,}\\ 0 & \textit{if n contains a square factor. } \end{cases}$$We demonstrate that for $x \ge \exp( 10^9) $ and $h=x^{1-\frac{1}{16000}}$, it exists in each interval $[x-h,x]$ integers $n_1$ with $\mu(n_1)=1$ and integers $n_2$ with $\mu(n_2)=-1$.\\This result is a consequence of a more general result. \\For $x \ge \exp(4\times 10^6)$, $\frac{1}{\sqrt{\log x}} \le \theta \le \frac{1}{2000}$, $h=x^{1-\theta}$ et $Q=(x/h)^{\frac{1}{20}}$, we have \\ $$\sum_{q \leq Q} \log(Q/q)\sum_{\chi mod q}^*\left| \sum_{x-h \le n \le x} \mu(n) \chi(n) \right| \leq 10^{20} h \theta \log(x) \exp( \frac{-1}{300 \theta}); $$the sum $\sum^*$ relating to primitive characters except for possible exceptional character.\\And in particular for $x \ge \exp( 10^9)$,$$\left | \sum_{x-.x^{1-\frac{1}{16000}}\le n \le x} \mu(n) \right | \le \frac{1}{100} x^{1-\frac{1}{16000}}.$$

On borne explicitement la hauteur de Faltings d'une courbe sur le corps de nombres algèbriques en son degré de Belyi. Des résultats similaires sont démontré pour trois autres invariants arakeloviennes : le discriminant, l'invariant delta et l'auto-intersection de omega. Nos résultats nous permettent de borner explicitement les invariantes arakeloviennes des courbes modulaires, des courbes de Fermat et des courbes de Hurwitz. En plus, comme application, on montre que l'algorithme de Couveignes-Edixhoven-Bruin est polynomial sous l’hypothèse de Riemann pour les fonctions zeta des corps de nombres. Ceci était connu uniquement pour certains sous-groupes de congruence. Finalement, on utilise nos résultats pour démontrer une conjecture de Edixhoven, de Jong et Schepers sur la hauteur de Faltings d'un revêtement ramifié de la droite projective sur l'anneau des entiers. / We explicitly bound the Faltings height of a curve over the field of algebraic numbers in terms of the Belyi degree. Similar bounds are proven for three other Arakelov invariants: the discriminant, Faltings' delta invariant and the self-intersection of the dualizing sheaf. Our results allow us to explicitly bound these Arakelov invariants for modular curves, Hurwitz curves and Fermat curves. Moreover, as an application, we show that the Couveignes-Edixhoven-Bruin algorithmtime under the Riemann hypothesis for zeta-functions of number fields. This was known before only for certain congruence subgroups. Finally, we utilize our results to prove a conjecture of Edixhoven, de Jong and Schepers on the Faltings height of a branched cover of the projective line over the ring of integers.

Le but de cette thèse est d'étudier la somme et le zéro dans deux principaux cadres : les isomorphismes de types et la normalisation de lambda-termes. Les isomorphismes de type avaient déjà été étudiés dans le cadre du lambda-calcul simplement typé avec paires surjectives mais sans somme. Pour aborder le cas avec somme et zéro, j'ai commencé par restreindre l'étude au cas des isomorphismes linéaires, dans le cadre de la logique linéaire, ce qui a conduit à une caractérisation remarquablement simple de ces isomorphismes, obtenue grâce à une méthode syntaxique sur les réseaux de preuve. Le cadre plus général de la logique intuitionniste correspond au problème ouvert de la caractérisation des isomorphismes dans les catégories bi-cartésiennes fermées. J'ai pu apporter une contribution à cette étude en montrant qu'il n'y a pas d'axiomatisation finie de ces isomorphismes. Pour cela, j'ai tiré partie de travaux en théorie des nombres portant sur un problème énoncé par Alfred Tarski et connu sous le nom du « problème des égalités du lycée ». Pendant tout ce travail sur les isomorphismes de types, s'est posé le problème de trouver une forme canonique pour représenter les lambda-termes, que ce soit dans le but de nier l'existence d'un isomorphisme par une étude de cas sur la forme du terme, ou pour vérifier leur existence dans le cas des fonctions très complexes que j'étais amené à manipuler. Cette réflexion a abouti à poser une définition « extensionnelle » de forme normale pour le lambda-calcul avec somme et zéro, obtenue par des méthodes catégoriques grâce aux relations logiques de Grothendieck, apportant ainsi une nouvelle avancée dans l'étude de la question réputée difficile de la normalisation de ce lambda-calcul. Enfin je montrerai comment il est possible d'obtenir une version « intentionnelle » de ce résultat en utilisant la normalisation par évaluation. J'ai pu ainsi donner une adaptation de la technique d' évaluation partielle dirigée par les types pour qu'elle produise un résultat dans cette forme normale, ce qui en réduit considérablement la taille et diminue aussi beaucoup le temps de normalisation dans le cas des isomorphismes de types considérés auparavant.