Physical Sciences and Mathematics Commons^™

New Algorithmic Support For The Fundamental Theorem Of Algebra, Vitaly Zaderman

Dissertations, Theses, and Capstone Projects

Univariate polynomial root-finding is a venerated subjects of Mathematics and Computational Mathematics studied for four millenia. In 1924 Herman Weyl published a seminal root-finder and called it an algorithmic proof of the Fundamental Theorem of Algebra. Steve Smale in 1981 and Arnold Schonhage in 1982 proposed to classify such algorithmic proofs in terms of their computational complexity. This prompted extensive research in 1980s and 1990s, culminated in a divide-and-conquer polynomial root-finder by Victor Pan at ACM STOC 1995, which used a near optimal number of bit-operations. The algorithm approximates all roots of a polynomial p almost as fast as one …

A New Perspective On A Polynomial Time Knot Polynomial, Robert John Quarles

LSU Doctoral Dissertations

In this work we consider the Z1(K) polynomial time knot polynomial defined and
described by Dror Bar-Natan and Roland van der Veen in their 2018 paper ”A polynomial time knot polynomial”. We first look at some of the basic properties of Z1(K), and develop an invariant of diagrams Ψm(D) related to this polynomial. We use this invariant as a model to prove how Z1(K) acts under the connected sum operation. We then discuss the effect of mirroring the knot on Z1(K), and described a geometric interpretation of some of the building blocks of the invariant. We then use these to …

Loss Of Precision In Implementations Of The Toom-Cook Algorithm, Marcus Elia

Graduate College Dissertations and Theses

Historically, polynomial multiplication has required a quadratic number of operations. Several algorithms in the past century have improved upon this. In this work, we focus on the Toom-Cook algorithm. Devised by Toom in 1963, it is a family of algorithms parameterized by an integer, n. The algorithm multiplies two polynomials by recursively dividing them into smaller polynomials, multiplying many small polynomials, and interpolating to obtain the product. While it is no longer the asymptotically fastest method of multiplying, there is a range of intermediate degrees (typically less than 1000) where it performs the best.

Some applications, like quantum-resistant cryptosystems, require …

On The Characteristic Polynomial Of A Hypergraph, Gregory J. Clark

Theses and Dissertations

We consider the computation of the adjacency characteristic polynomial of a uniform hypergraph. Computing the aforementioned polynomial is intractable, in general; however, we present two mechanisms for computing partial information about the spectrum of a hypergraph as well as a methodology (and in particular, an algo- rithm) for combining this information to determine complete information about said spectrum. The first mechanism is a generalization of the Harary-Sachs Theorem for hypergraphs which yields an explicit formula for each coefficient of the characteristic polynomial of a hypergraph as a weighted sum over a special family of its subgraphs. The second is a …

Combinatorial Polynomial Hirsch Conjecture, Sam Miller

HMC Senior Theses

The Hirsch Conjecture states that for a d-dimensional polytope with n facets, the diameter of the graph of the polytope is at most n-d. This conjecture was disproven in 2010 by Francisco Santos Leal. However, a polynomial bound in n and d on the diameter of a polytope may still exist. Finding a polynomial bound would provide a worst-case scenario runtime for the Simplex Method of Linear Programming. However working only with polytopes in higher dimensions can prove challenging, so other approaches are welcome. There are many equivalent formulations of the Hirsch Conjecture, one of which is the …

An Analysis Of Charles Fefferman's Proof Of The Fundamental Theorem Of Algebra, Kyle O. Linford

Senior Honors Theses and Projects

Many peoples' first exploration into more rigorous and formalized mathematics is with their early explorations in algebra. Much of their time and effort is dedicated to finding roots of polynomials-a challenge that becomes more increasingly difficult as the degree of the polynomials increases, especially if no real number roots exist. The Fundamental Theorem of Algebra is used to show that there exists a root, particularly a complex root, for any nth degree polynomial. After struggling to prove this statement for over 3 centuries, Carl Friedrich Gauss offered the first fairly complete proof of the theorem in 1799. Further proofs of …

The Number Of Zeros Of A Polynomial In A Disk As A Consequence Of Coefficient Inequalities With Multiple Reversals, Derek T. Bryant

Electronic Theses and Dissertations

In this thesis, we explore the effect of restricting the coefficients of polynomials on the bounds for the number of zeros in a given region. The results presented herein build on a body of work, culminating in the generalization of bounds among three classes of polynomials. The hypotheses of monotonicity on each class of polynomials were further subdivided into sections concerning r reversals among the moduli, real parts, and both real and imaginary parts of the coefficients.

The Number Of Zeros Of A Polynomial In A Disk As A Consequence Of Restrictions On The Coefficients, Brett A. Shields Mr.

Electronic Theses and Dissertations

In this thesis, we put restrictions on the coefficients of polynomials and give bounds concerning the number of zeros in a specific region. Our results generalize a number of previously known theorems, as well as implying many new corollaries with hypotheses concerning monotonicity of the modulus, real, as well as real and imaginary parts of the coefficients separately. We worked with Enestr\"{o}m-Kakeya type hypotheses, yet we were only concerned with the number of zeros of the polynomial. We considered putting the same type of restrictions on the coefficients of three different types of polynomials: polynomials with a monotonicity``flip" at some …

Independence Polynomials, Gregory Matthew Ferrin

Theses and Dissertations

In this thesis, we investigate the independence polynomial of a simple graph G. In addition to giving several tools for computing these polynomials and giving closed-form representations of these polynomials for common classes of graphs, we prove two results concerning the roots of independence polynomials. The first result gives us the unique root of smallest modulus of the independence polynomial of a graph. The second result tells us that all the roots of the independence polynomial of a claw-free graph fall on the real line.

Sharp Bounds Associated With An Irreducibility Theorem For Polynomials Having Non-Negative Coefficients, Morgan Cole

Theses and Dissertations

Consider a polynomial f(x) having non-negative integer coefficients with f(b) prime for some integer b greater than or equal to 2. We will investigate the size of the coefficients of the polynomial and establish a largest such bound on the coefficients that would imply that f(x) is irreducible. A result of Filaseta and Gross has established sharp bounds on the coefficients of such a polynomial in the case that b = 10. We will expand these results for b in {8, 9, ..., 20}.

Independence Polynomials Of Molecular Graphs, Cameron Taylor Byrum

Electronic Theses and Dissertations

In the 1980's, it was noticed by molecular chemists that the stability and boiling point of certain molecules were related to the number of independent vertex sets in the molecular graphs of those chemicals. This led to the definition of the Merrifield-Simmons index of a graph G as the number of independent vertex sets in G. This parameter was extended by graph theorists, who counted independent sets of different sizes and defined the independence polynomial F_G(x) of a graph G to be \sum_k F_k(G)x^k where for each k, F_k(G) is the number of independent sets of k vertices. This thesis …

On The Irreducibility Of The Cauchy-Mirimanoff Polynomials, Brian C. Irick

Doctoral Dissertations

The Cauchy-Mirimanoff Polynomials are a class of polynomials that naturally arise in various classical studies of Fermat's Last Theorem. Originally conjectured to be irreducible over 100 years ago, the irreducibility of the Cauchy-Mirimanoff polynomials is still an open conjecture.

This dissertation takes a new approach to the study of the Cauchy-Mirimanoff Polynomials. The reciprocal transform of a self-reciprocal polynomial is defined, and the reciprocal transforms of the Cauchy-Mirimanoff Polynomials are found and studied. Particular attention is given to the Cauchy-Mirimanoff Polynomials with index three times a power of a prime, and it is shown that the Cauchy-Mirimanoff Polynomials of index …

Structural Properties Of Formal Polynomial Algebras In Noncommuting Or Nonassociating Indeterminates, Serge C. Ballif

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

In order to enlarge the class of equations provided by traditional polynomials over a binary algebra A to a more useful class of equations, we introduce polynomials in noncommuting or nonassociating indeterminates. We discuss algebraic properties of these formal polynomial algebras and their accompanying polynomial function algebras. We present certain basis results for polynomial algebras, which are used to address the question of zero divisors in a polynomial algebra. We give an analog of the remainder theorem and the factor theorem for polynomials. Particular emphasis is placed on showing the difference between polynomials and polynomial functions. We also provide a …

An Exposition Of The Deterministic Polynomial-Time Primality Testing Algorithm Of Agrawal-Kayal-Saxena, Robert Lawrence Anderson

Theses and Dissertations

I present a thorough examination of the unconditional deterministic polynomial-time algorithm for determining whether an input number is prime or composite proposed by Agrawal, Kayal and Saxena in their paper [1]. All proofs cited have been reworked with full details for the sake of completeness and readability.