Spelling suggestions: "subject:"binomials"" "subject:"monomials""
1 |
Ultrametric Fewnomial TheoryIbrahim Abdelhalim, Ashraf 2009 December 1900 (has links)
An ultrametric field is a field that is locally compact as a metric space with
respect to a non-archimedean absolute value. The main topic of this dissertation is
to study roots of polynomials over such fields.
If we have a univariate polynomial with coefficients in an ultrametric field and
non-vanishing discriminant, then there is a bijection between the set of roots of the
polynomial and classes of roots of the same polynomial in a finite ring. As a consequence,
there is a ball in the polynomial space where all polynomials in it have the
same number of roots.
If a univariate polynomial satisfies certain generic conditions, then we can efficiently
compute the exact number of roots in the field. We do that by using Hensel's
lemma and some properties of Newton's polygon.
In the multivariate case, if we have a square system of polynomials, we consider
the tropical set which is the intersection of the tropical varieties of its polynomials.
The tropical set contains the set of valuations of the roots, and for every point in
the tropical set, there is a corresponding system of lower polynomials. If the system
satisfies some generic conditions, then for each point w in the tropical set the number
of roots of valuation w equals the number roots of valuation w of the lower system.
The last result enables us to compute the exact number of roots of a polynomial
system where the tropical set is finite and the lower system consists of binomials.
This algorithmic method can be performed in polynomial-time if we fix the number of variables.
We conclude the dissertation with a discussion of the feasibility problem. We
consider the problem of the p-adic feasibility of polynomials with integral coefficients
with the prime number p as a part of the input. We prove this problem can be solved
in nondeterministic polynomial-time. Furthermore, we show that any problem, which
can be solved in nondeterministic polynomial-time, can be reduced to this feasibility
problem in randomized polynomial-time.
|
2 |
Géométrie tropicale et systèmes polynomiaux / Tropical geometry and polynomial systemsEl Hilany, Boulos 21 September 2016 (has links)
Les systèmes polynomiaux réels sont omniprésents dans de nombreux domaines des mathématiques pures et appliquées. A. Khovanskii a fourni une borne fewnomiale supérieure sur le nombre de solutions positives non-dégénérées d'un système polynomial réel de n équations à n variables qui ne dépend que du nombre de monômes apparaissant dans les équations. Cette dernière borne a été récemment améliorée par F. Bihan et F. Sottile, mais la borne résultante peut être encore améliorée, même dans certains cas simples.Le but de ce travail est d'aborder trois problèmes importants dans la théorie des Fewnomials. Considérons une famille de systèmes polynomiaux réels avec une structure donnée (par exemple, support ou le nombre de monômes). Un problème est de trouver de bonnes bornes supérieures pour leurs nombres de solutions réelles (ou positives). Un autre problème est de construire des systèmes dont le nombre de solutions réelles (ou positives) sont proches de la meilleure borne supérieure connue. Lorsqu'une borne supérieure optimale est bien connue, qu'est ce qu'on peut dire dans le cas où elle est atteinte?Dans cette thèse, nous affinons un résultat de M. Avendaño en démontrant que le nombre de points d'intersection réels d'une droite réelle avec une courbe réelle plane définie par un polynôme avec au plus t monômes est soit infini ou ne dépasse pas $6t -7$. En outre, on montre que notre borne est optimale pour t=3 en utilisant les dessins d'enfant réels de Grothendieck. Cela montre que le nombre maximal de points d'intersection réels d'une droite réelle avec une courbe trinomiale réelle plane est onze.Nous considérons ensuite le problème de l'estimation du nombre maximal de points d'intersection transverses positifs d'une courbe plane trinomiale et d'une courbe plane t-nomiale. T-Y Li, J.-M. Rojas et X. Wang ont montré que ce nombre est borné par 2^t - 2, et récemment P. Koiran, N. Portier et S. Tavenas ont trouvé la borne supérieure 2t^3/3 +5t. Nous fournissons la borne supérieure $ 3*2^(t-2) - 1 qui est optimale pour t = 3 et est la plus petite pour t=4,...,9. Ceci est réalisé en utilisant la notion de dessins d'enfant réels. De plus, nous étudions en détail le cas t = 3 et nous donnons une restriction sur les supports des systèmes atteignant la borne optimale cinq.Un circuit est un ensemble de n+ 2 points dans $mathbb{R}^n$ qui sont minimalement affinement dépendants. Il est connu qu'un système supporté sur un circuit a au plus n+1 solutions positives non dégénérées, et que cette borne est optimale. Nous utilisons les dessins d'enfant réels et le patchwork combinatoire de Viro pour donner une caractérisation complète des circuits supportant des systèmes polynomiaux avec le nombre maximal de solutions positives non dégénérées.Nous considérons des systèmes polynomiaux de deux équations à deux variables avec cinq monômes distincts au total. Ceci est l'un des cas les plus simples où la borne supérieure optimale sur le nombre de solutions positives non dégénérées n'est pas connue. F. Bihan et F. Sottile ont prouvé que cette borne optimale est majorée par quinze. D'autre part, les meilleurs exemples avaient seulement cinq solutions positives non dégénérées.Nous considérons des systèmes polynomiaux comme avant, mais défini sur le corps des séries de Puiseux réelles généralisées et localement convergentes. Les images par l'application de valuation des solutions d'un tel système sont des points d'intersection de deux courbes tropicales planes. En utilisant des intersections non transverses des courbes tropicales planes, on obtient une construction d'un système polynomial réel comme ci-dessus ayant sept solutions positives non dégénérées. / Real polynomial systems are ubiquitous in many areas of pure and applied mathematics. A. Khovanskii provided a fewnomial upper bound on the number of non-degenerate positive solutions of a real polynomial system of $n$ equations in n variables that depends only on the number of monomials appearing in the equations. The latter bound was recently improved by F. Bihan and F. Sottile, but the resulting bound still has room for improvement, even in some simple cases.The aim of this work is to tackle three main problems in Fewnomial theory. Consider a family of real polynomial systems with a given structure (for instance, supports or number of monomials). One problem is to find good upper bounds for their numbers of real (or positive) solutions. Another problem is to construct systems whose numbers of real (or positive) solutions are close to the best known upper bound. When a sharp upper bound is known, what can be said about reaching it?In this thesis, we refine a result by M. Avendaño by proving that the number of real intersection points of a real line with a real plane curve defined by a polynomial with at most t monomials is either infinite or does not exceed 6t -7. Furthermore, we prove that our bound is sharp for t=3 using Grothendieck's real dessins d'enfant. This shows that the maximal number of real intersection points of a real line with a real plane trinomial curve is eleven.We then consider the problem of estimating the maximal number of transversal positive intersection points of a trinomial plane curve and a t-nomial plane curve. T-Y Li, J.-M. Rojas and X. Wang showed that this number is bounded by 2^t-2, and recently P. Koiran, N. Portier and S. Tavenas proved the upper bound 2t^3/3 +5t. We provide the upper bound 3*2^{t-2} - 1 that is sharp for t=3 and is the tightest for t=4,...,9. This is achieved using the notion of real dessins d'enfant. Moreover, we study closely the case t=3 and give a restriction on the supports of systems reaching the sharp bound five.A circuit is a set of n+2 points in mathbb{R}^n that is minimally affinely dependent. It is known that a system supported on a circuit has at most n+1 non-degenerate positive solutions, and that this bound is sharp. We use real dessins d'enfant and Viro's combinatorial patchworking to give a full characterization of circuits supporting polynomial systems with the maximal number of non-degenerate positive solutions.We consider polynomial systems of two equations in two variables with a total of five distinct monomials. This is one of the simplest cases where the sharp upper bound on the number of non-degenerate positive solutions is not known. F. Bihan and F. Sottile proved that this sharp bound is not greater than fifteen. On the other hand, the best examples had only five non-degenerate positive solutions. We consider polynomial systems as before, but defined over the field of real generalized locally convergent Puiseux series. The images by the valuation map of the solutions of such a system are intersection points of two plane tropical curves. Using non-transversal intersections of plane tropical curves, we obtain a construction of a real polynomial system as above having seven non-degenerate positive solutions.
|
3 |
Cyclicité finie des boucles homoclines dans R3 non dégénérées avec valeurs propres principales réelles en résonance 1:1Guimond, Louis-Sébastien January 1999 (has links)
Thèse diffusée initialement dans le cadre d'un projet pilote des Presses de l'Université de Montréal/Centre d'édition numérique UdeM (1997-2008) avec l'autorisation de l'auteur.
|
4 |
Cyclicité finie des boucles homoclines dans R3 non dégénérées avec valeurs propres principales réelles en résonance 1:1Guimond, Louis-Sébastien January 1999 (has links)
Thèse diffusée initialement dans le cadre d'un projet pilote des Presses de l'Université de Montréal/Centre d'édition numérique UdeM (1997-2008) avec l'autorisation de l'auteur.
|
Page generated in 0.0688 seconds