Circuits, and Trinomials, Over Arithmetic Fields
J. Maurice Rojas (Texas A&M and TU Munchen)
A recent analogue of Descartes' Rule over F_q (the finite field with
q elements) implies that the maximal number of roots in F_q of a univariate
polynomial with exactly 3 monomial terms (and the gcd of q-1 and the
differences of the exponents being 1) is at most 2+(q-1)^{1/2}. This upper
bound is asymptotically optimal for most prime powers q, but the correct upper
bound for prime q is a mystery, possibly connected to recent attacks on the
discrete logarithm problem.
We present computational evidence that the correct upper bound for
prime q is O(log q), and show how the Generalized Riemann Hypothesis
implies the existence of trinomials with O((log q)/log log q) roots
in F_q when q is prime.
We then move to the field C_p, where a conjectural upper bound on the
number of roots of certain sparse polynomial systems is shown to be related
to the Shub-Smale tau-Conjecture and the circuit complexity of the permanent.
Along the way, we mention some combinatorial constructions related to circuits
from combinatorics.