09:00 AM - 09:15 AM
|
|
Final Presentations: Opening Remarks
J. Maurice Rojas (Texas A & M University)
|
- Location
- SLMath: Baker Board Room
- Video
-
--
- Abstract
- --
- Supplements
-
--
|
09:15 AM - 09:50 AM
|
|
Counting the roots of a polynomial modulo p2
trajan hammonds (Carnegie Mellon University), Jeremy Johnson (California State Polytechnic University, Humboldt), Angela Patini (University of Pennsylvania)
|
- Location
- SLMath: Baker Board Room
- Video
-
- Abstract
Until recently, the only known method of finding the roots of polynomials over prime power rings, other than fields, was brute force. One reason for this is the lack of a division algorithm, thus obstructing the use of greatest common divisors. Suppose f is any nonzero univariate polynomial of degree d in Z/p^nZ[x]. For the case n=2, we prove a new efficient algorithm to count the roots in Z/p^2Z within time polynomial in d + log p. The key idea is to partition the roots via their image under reduction modulo p, and then carefully use Hensel's Lemma. This builds upon recent work of Cheng, Gao, Rojas, and Wan.
- Supplements
-
--
|
10:00 AM - 11:20 AM
|
|
On the maximal number of roots of a trinomial over a prime field
Jeshu Dastidar (San Francisco State University), Viviana Peña Márquez (Konrad Lorenz Fundación Universitaria), Ryan Pugh (Foothill College)
|
- Location
- SLMath: Baker Board Room
- Video
-
- Abstract
Canetti, Friedlander, et al. (2002) studied the randomness of powers over finite fields and along the way derived an analogue of Descartes’™ rule over the finite field F_q with q elements: They showed that the number of roots of any univariate t-nomial, with exponents {0,a_2,...,a_t} and the differences a_i-a_j all relatively prime to q-1, is O(q^{(t-2)/(t-1)}). The correct optimal bounds remain a mystery for prime fields, even in the case of polynomials with three terms. Following the work of Kelley (2016), we seek to prove the conjecture that the number of roots in F_p of a trinomial with a linear middle term is always O(log p). We expand current evidence by using a supercomputer to determine the number of roots of these trinomials for 139,571 < p 191,491. We also prove that the search can be restricted to trinomials with a middle linear term when p-1 has less than three distinct prime factors.
- Supplements
-
--
|
10:45 AM - 11:20 AM
|
|
Applying discriminant chambers to structured polynomials
Amy Adair (Louisiana State University), Alex Mendez (University of Illinois at Urbana-Champaign), Diane Tchuindjo (Massachusetts Institute of Technology)
|
- Location
- SLMath: Baker Board Room
- Video
-
- Abstract
One way to prove the algorithmic hardness of a function is to consider its circuit complexity: the minimal size of a circuit computing the function. Recent work in circuit complexity has revealed that it is enough to restrict to depth-4 circuits, inspiring the study of certain structured polynomials called sum-of-products-of-sparse (SPS) polynomials. In particular, showing sufficiently good upper bounds for the number of real roots of SPS polynomials would imply the hardness of the permanent. If f and g are univariate polynomials with real coefficients and t terms, then does fg-1 have a number of real roots that grows at most linearly in t? We consider the first non-trivial approach towards such a bound via A-discriminants, leading to interesting questions involving sparse polynomial systems.
- Supplements
-
--
|
11:30 AM - 01:00 PM
|
|
Lunch
|
- Location
- SLMath: Baker Board Room
- Video
-
--
- Abstract
- --
- Supplements
-
--
|
01:00 PM - 01:35 PM
|
|
Using lower binomials to approximate roots of trinomials
Harold Jimenez Polo (University of California, Berkeley), Esteban Madrigal (Harvard University), Carlos Osco Huaricapcha (San Francisco State University)
|
- Location
- SLMath: Baker Board Room
- Video
-
- Abstract
Given a univariate trinomial f in R[x], we analyze the Archimedean Newton polytope of f and the corresponding lower binomials. The roots of these lower binomials conjecturally provide high quality approximations of the roots of f. We implement Smale's alpha-criterion to analyze whether our approximations converge quickly under Newton iteration. We know that under certain conditions every root of a lower binomial is an approximate root of a trinomial. We expect to determine when at least one root of a lower binomial is an approximate root. Moreover, for roots that are not approximate, we examine when Newton's method yields approximate roots.
- Supplements
-
--
|
01:45 PM - 02:20 PM
|
|
Topology of positive zero sets of bivariate pentanomials
Malachi Alexander (University of California, Santa Cruz), Ashley De Luna (California State Polytechnic University, Pomona), Christian McRoberts (Iowa State University)
|
- Location
- SLMath: Baker Board Room
- Video
-
- Abstract
A fundamental problem in many applications is determining the real solutions of a polynomial. In recent years, the A-discriminant variety of Gelfand, Kapranov and Zelevinsky has proved to be a valuable tool. Its complement over the real numbers defines regions of coefficient values called chambers. We implement an algorithm in MATLAB that draws A-discriminant curves for families of bivariate pentanomials where the topology of the underlying zero set is constant. Our program graphs the discriminant curve with all of its chambers and automatically computes the topology of all smooth zero set for the given families of bivariate pentanomials. We hope automated topology computation for high degree polynomials will prove useful for the algebraic geometry community.
- Supplements
-
--
|
02:30 PM - 03:05 PM
|
|
Topology of positive zero sets of n-variate (n+4)-nomials
Davina Boykin (Valparaiso University), Sabrina Enriquez (University of Southern California), Noemi Valdez (Harvard University)
|
- Location
- SLMath: Baker Board Room
- Video
-
- Abstract
Let f be a polynomial of degree d with exactly n+4 monomial terms in R[x_1,…,x_n]. We show that one can efficiently compute an explicit polyhedral complex with the same isotopy type as the positive zero set of f. In particular, the complexity of our construction is polynomial in u + log d with high probability. Along the way, we derive and implement an algorithm that, given an n-variate (n+4)-nomial f, outputs a plot of the reduced A-discriminant contour in R^3.
- Supplements
-
--
|
03:05 PM - 03:15 PM
|
|
Closing Remarks
Federico Ardila (San Francisco State University)
|
- Location
- SLMath: Baker Board Room
- Video
-
--
- Abstract
- --
- Supplements
-
--
|
03:15 PM - 04:00 PM
|
|
Afternoon Tea
|
- Location
- SLMath: Baker Board Room
- Video
-
--
- Abstract
- --
- Supplements
-
--
|