Academic literature on the topic 'Algèbre aux différences'

Cette thèse comprend deux parties indépendantes. La première partie regroupe des contributions à l’analyse polyadique. On récapitule les propriétés de l’anneau (non intègre) des entiers polyadiques vu de façon globale comme limite projective des quotients finis de l’anneau des entiers rationnels, plutôt que comme produit d’anneaux padiques. On étudie les suites récurrentes linéaires, en donnant un critère simple pour qu’elles soient prolongeables en une fonction continue définie sur l’anneau des entiers polyadiques. On donne une base de « van der Put » des fonctions continues sur l’anneau des entiers polyadiques, et on termine par l’étude de la théorie du logarithme en analyse polyadique. La seconde partie présente de nouveaux algorithmes qui recherchent des solutions rationnelles des systèmes linéaires aux différences à coefficients polynomiaux (ou bien d’équations linéaires scalaires aux différences) dans un corps de caractéristique nulle. Nous examinons les algorithmes usuels de calcul formel et nous proposons quelques nouveaux algorithmes pour résoudre ce problème. La complexité et une comparaison en temps des implémentations des algorithmes sous Maple sont présentées<br>This thesis consists in two independent parts. The first one gathers some contribution to polyadic analysis. We summarize properties of the (not entire) ring of the polyadic integers, seen in a global way as the projective limit of the finite quotients of the ring of rational integers, rather than as a product of p-adic rings. We study linear recurrence sequences, giving a natural criterium for the interpolation of linear recurrence sequences to continuous functions over the ring of polyadic integers. We give a « van der Put » basis for continuous functions on the ring of polyadic integers, and we end by investigation of the theory of logarithm in polyadic analysis. In the second part, we consider the problem of computing rational solutions of linear difference systems (or scalar equations) with polynomial coefficients over a field of zero characteristic. We discuss algorithms that are currently used and propose some new algorithms for solving this problem. A complexity analysis and a time comparison of the algorithms implemented in Maple are presented

Depuis les années 90, la méthode de création télescopique de Zeilberger a joué un rôle important dans la preuve automatique d'identités mettant en jeu des fonctions spéciales. L'objectif de long terme que nous attaquons dans ce travail est l'obtension d'algorithmes et d'implantations rapides pour l'intégration et la sommation définies dans le cadre de cette création télescopique. Nos contributions incluent de nouveaux algorithmes pratiques et des critères théoriques pour tester la terminaison d'algorithmes existants. Sur le plan pratique, nous nous focalisons sur la construction de télescopeurs minimaux pour les fonctions rationnelles en deux variables, laquelle a de nombreuses applications en lien avec les fonctions algébriques et les diagonales de séries génératrices rationnelles. En considérant cette classe d'entrées contraintes, nous parvenons à mâtiner la méthode générale de création télescopique avec réduction bien connue d'Hermite, issue de l'intégration symbolique. En outre, nous avons obtenu pour cette sous-classe quelques améliorations des algorithmes classiques d'Almkvist et Zeilberger. Nos résultats expérimentaux ont montré que les algorithmes à base de réduction d'Hermite battent tous les autres algorithmes connus, à la fois en ce qui concerne la complexité au pire et en ce qui concerne les mesures de temps sur nos implantations. Sur le plan théorique, notre premier résultat est motivé par la conjecture de Wilf et Zeilberger au sujet des fonctions hyperexponentielles-hypergéométriques holonomes. Nous présentons un théorème de structure pour les fonctions hyperexponentielles-hypergéométriques de plusieurs variables, indiquant qu'une telle fonction peut s'écrire comme le produit de fonctions usuelles. Ce théorème étend à la fois le théorème d'Ore et Sato pour les termes hypergéométriques en plusieurs variables et le résultat récent par Feng, Singer et Wu. Notre second résultat est relié au problème de l'existence de télescopeurs. Dans le cas discret à deux variables, Abramov a obtenu un critère qui indique quand un terme hypergéométrique a un télescopeur. Des résultats similaires ont été obtenus pour le $q$-décalage par Chen, Hou et Mu. Ces résultats sont fondamentaux pour la terminaison des algorithmes s'inspirant de celui de Zeilberger. Dans les autres cas mixtes continus/discrets, nous avons obtenu deux critères pour l'existence de télescopeurs pour des fonctions hyperexponentielles-hypergéométriques en deux variables. Nos critères s'appuient sur une représentation standard des fonctions hyperexponentielles-hypergéométriques en deux variables, sur sur deux décompositions additives.

Cette thèse se situe dans le domaine de la combinatoire algébrique et porte sur l'étude et les applications de trois ordres sur les permutations : les deux ordres faibles (gauche et droit) et l'ordre fort ou de Bruhat. Dans un premier temps, nous étudions l'action du groupe symétrique sur les polynômes multivariés. En particulier, les opérateurs de emph{différences divisées} permettent de définir des bases de l'anneau des polynômes qui généralisent les fonctions de Schur aussi bien du point de vue de leur construction que de leur interprétation géométrique. Nous étudions plus particulièrement la base des polynômes de Grothendieck introduite par Lascoux et Schützenberger. Lascoux a montré qu'un certain produit de polynômes peut s'interpréter comme un produit d'opérateurs de différences divisées. En développant ce produit, nous ré-obtenons un résultat de Lenart et Postnikov et prouvons de plus que le produit s'interprète comme une somme sur un intervalle de l'ordre de Bruhat. Nous présentons aussi l'implantation que nous avons réalisée sur Sage des polynômes multivariés. Cette implantation permet de travailler formellement dans différentes bases et d'effecteur des changements de bases. Elle utilise l'action des différences divisées sur les vecteurs d'exposants des polynômes multivariés. Les bases implantées contiennent en particulier les polynômes de Schubert, les polynômes de Grothendieck et les polynômes clés (ou caractères de Demazure).Dans un second temps, nous étudions le emph{treillis de Tamari} sur les arbres binaires. Celui-ci s'obtient comme un quotient de l'ordre faible sur les permutations : à chaque arbre est associé un intervalle de l'ordre faible formé par ses extensions linéaires. Nous montrons qu'un objet plus général, les intervalles-posets, permet de représenter l'ensemble des intervalles du treillis de Tamari. Grâce à ces objets, nous obtenons une formule récursive donnant pour chaque arbre binaire le nombre d'arbres plus petits ou égaux dans le treillis de Tamari. Nous donnons aussi une nouvelle preuve que la fonction génératrice des intervalles de Tamari vérifie une certaine équation fonctionnelle décrite par Chapoton. Enfin, nous généralisons ces résultats aux treillis de $m$-Tamari. Cette famille de treillis introduite par Bergeron et Préville-Ratelle était décrite uniquement sur les chemins. Nous en donnons une interprétation sur une famille d'arbres binaires en bijection avec les arbres $m+1$-aires. Nous utilisons cette description pour généraliser les résultats obtenus dans le cas du treillis de Tamari classique. Ainsi, nous obtenons une formule comptant le nombre d'éléments plus petits ou égaux qu'un élément donné ainsi qu'une nouvelle preuve de l'équation fonctionnelle des intervalles de $m$-Tamari. Pour finir, nous décrivons des structures algébriques $m$ qui généralisent les algèbres de Hopf $FQSym$ et $PBT$ sur les permutations et les arbres binaires

L'analyse à l'époque de Lagrange est étudiée à travers quatre thèmes. Trois d'entre eux concernent l'analogie des puissances et des différentielles. Dans un quatrième, se pose la question des relations entre le calcul différentiel et le calcul aux différences finies. Lagrange donne à la méthode de variation de la constante une portée générale qui intéresse les équations différentielles, les équations aux différences finies linéaires et les problèmes de Mécanique céleste. Dès les années 1760, se mettent en place des éléments qui, au XIXème siècle, permettront de constater les analogies entre les équations différentielles linéaires et les équations algébriques. Un traitement spécifique des constantes d'intégration se manifeste aussi dans la théorie des solutions singulières due à Lagrange. Cette théorie ne s'adapte pas de façon immédiate au cas des équations aux différences finies. Lagrange en tire argument pour disqualifier les conceptions de l'Analyse qui reposent sur un passage du fini à l'infiniment petit. La résolution de certaines équations aux dérivées partielles fait apparaître des séries formées à l'aide des dérivées successives d'une fonction arbitraire, celles-ci se prêtent à l'utilisation de méthodes symboliques. Ce domaine est exploré par Brisson, Laplace et Poisson. En utilisant les termes mêmes par lesquels Lagrange démontre la formule de Taylor, Brisson établit, pour les opérateurs différentiels, une formule analogue. L'analogie des puissances et des différences a un statut très particulier dans l'oeuvre de Lagrange : elle est étroitement liée à une conception fondamentale de l'Analyse reposant sur la série de Taylor, mais elle conserve un caractère inductif.

Les travaux présentés dans ce mémoire se basent sur les apports de l'algèbre différentielle et les méthodes du calcul symbolique pour résoudre des problèmes d'automatique non linéaire qui ne se prêtent pas à une résolution numérique directe.<br /><br />Le problème de l'observabilité algébrique locale consiste à décider si les variables d'état intervenant dans un modèle peuvent être déterminées en fonction des entrées et des sorties supposées parfaitement connues.<br /><br />Nous présentons un algorithme probabiliste de complexité arithmétique polynomiale en la taille de l'entrée permettant de tester l'observabilité algébrique locale en déterminant les variables non observables. L'utilisation du calcul modulaire permet d'obtenir pour ce test une complexité binaire elle aussi polynomiale. Cette complexité dépend linéairement de la probabilité de succès qui peut être arbitrairement fixée. Une implantation de cet algorithme permet de traiter des problèmes inaccessibles jusqu'à présent.<br /><br /><br />À partir de ces méthodes mêlant calcul symbolique et calcul numérique, nous proposons une généralisation de la notion de platitude différentielle à certains modèles non linéaires décrits par des équations aux dérivées partielles. Un système différentiel ordinaire est différentiellement plat si ses solutions peuvent être localement paramétrées bijectivement par des fonctions arbitraires.<br /><br />Pour étudier certains systèmes d'équations aux dérivées partielles non linéaires, on se ramène à un système d'équations différentielles ordinaires par discrétisation ; notre approche consiste à chercher des discrétisations plates telles que les paramétrages associés convergent lorsque le pas de discrétisation tend vers zéro. Cette méthode est illustrée par l'étude du problème de planification de trajectoire réalisée pour trois modèles non linéaires de dimension infinie : l'équation de la chaleur semilinéaire, l'équation de Burger avec diffusion et un modèle non linéaire de tige flexible.

Les notions de fonctions parfaitement non linéaires et courbes sont particulièrement pertinentes en cryptographie puisqu'elles formalisent les résistances maximales face aux très efficaces attaques différentielle et linéaire. Cette thèse est ainsi consacrée à l'étude de ces objets cryptographiques. Nous interprétons ces notions de manière très naturelle essentiellement en substituant les translations figurant dans la définition de la non linéarité parfaite par une action de groupe quelconque. Les propriétés de ces actions telle que la fidélité ou la régularité permettent de décliner en plusieurs variantes ce nouveau concept. Nous développons de surcroît sa caractérisation duale à l'aide de la transformée de Fourier ce qui aboutit à la notion appropriée de fonction courbe. En particulier dans le cas d'une action de groupe non abélien, nous faisons usage de la théorie des représentations linéaires afin d'établir une version duale matricielle. Nous généralisons par ailleurs selon le même principe ces objets combinatoires appelés ensembles à différences qui caractérisent la non linéarité parfaite des fonctions à valeurs dans le corps fini à deux éléments. Cela nous permet d'exhiber des constructions de fonctions satisfaisant nos critères généralisés, en particulier dans ces cas où les fonctions courbes au sens classique n'existent pas.

Dans la première partie, on s'intéresse aux solutions méromorphes sur C d'un système de deux équations aux différences à coefficients constants et à deux pas récurrents. Lorsqu'on fait varier ce système, les solutions décrivent une certaine algèbre D[s,t] en rapport avec les fonctions elliptiques habituelles et celles de deuxième espèce de Hermite, ainsi que la fonction Z de Jacobi. Pour un système donné, les solutions trouvées forment sur le corps des fonctions elliptiques un espace vectoriel sur C de dimension inférieure ou égale à la précédente. Un exemple est traité, dans le cadre méromorphe, à l'aide du logiciel de calcul formel Maple6. Dans la deuxième partie, on s'intéresse à la résolution de systèmes d'EDP non linéaires, de type mixte, dans des ouverts non bornés. Cet aspect non borné est un thème important de l'étude. Le cas significatif considéré est celui d'un modèle d'écoulement transsonique. Le cadre hilbertien d'espaces de Sobolev permet de ramener le problème à l'annulation d'une fonctionnelle. Cette annulation est obtenue à [epsilon] près à l'aide d'un algorithme de type gradient. La prise en compte d'une condition d'entropie supplémentaire est traitée par une méthode de pénalisation des fonctionnelles considérées. L'encadrement à [epsilon] près de leurs bornes inférieures donne des solutions généralisées à[epsilon] près.