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.