On the Evaluation of Powers and Monomials

Let y₁ , ⋯ ,yₚ be monomials over the indeterminates x₁ , ⋯ ,xq. For every y = (y₁ , ⋯ ,yₚ ) there is some minimum number $L(y)$ of multiplications sufficient to compute y₁ , ⋯ ,yₚ from x₁ , ⋯ ,xq 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 + 1o(q) ) and q = (N + 1ᵒ⁽ᵖ⁾ ), then L(p,q,N) = min \ p,q\ log N + H/log H + o(H /log H), where H = pqlog (N + 1) and all logarithms have base 2.