On the Evaluation of Powers and Monomials

Let $y_1 , \cdots ,y_p $ be monomials over the indeterminates $x_1 , \cdots ,x_q $. For every $y = (y_1 , \cdots ,y_p )$ there is some minimum number $L(y)$ of multiplications sufficient to compute $y_1 , \cdots ,y_p $ from $x_1 , \cdots ,x_q $ and the identity 1. Let $L(p,q,N)$ denote the maximum of $L(y)$ over all y for which the exponent of any indeterminate in any monomial is at most N. We show that if $p = (N + 1^{o(q)} )$ and $q = (N + 1^{o(p)} )$, then $L(p,q,N) = \min \{ p,q\} \log N + H/\log H + o(H /\log H)$, where $H = pq\log (N + 1)$ and all logarithms have base 2.