PSEUDO-BOOLEAN FUNCTIONS AND THE MULTIPLICITY OF THE ZEROS OF POLYNOMIALS

A highlight of this paper states that there is an absolute constant c(1) > 0 such that every polynomial P of the form P(z) = Sigma(n)(j=0) a(j)z(j) , a(j is an element of) C with vertical bar a(0)vertical bar = 1, vertical bar a(j)vertical bar <= M-1((n) (j)), j = 1,2, ... , n, for some 2 <= M <= e(n) has at most n- left perpendicular c(1 root)n log M right perpendicular zeros at 1. This is compared with some earlier similar results reviewed in the introduction and closely related to some interesting Diophantine problems. Our most important tool is an essentially sharp result due to Coppersmith and Rivlin asserting that if F-n = {1, 2, ... , n}, there exists an absolute constant c > 0 such that vertical bar P(0)vertical bar <= exp(cL) max(x is an element of Fn) vertical bar P(x)vertical bar for every polynomial P of degree at most m <= root nL/16 with 1 <= L < 16n. A new proof of this inequality is included in our discussion.