Large sums of high order characters II

Let be a primitive character modulo q, and let > 0. Assuming that has large order d, for any dth root of unity we obtain non-trivial upper bounds for the number of n x such that (n) =, provided x > q^. This improves upon a previous result of the first author by removing restrictions on q and d. As a corollary, we deduce that if the largest prime factor of d satisfies P^+ (d) then the level set (n) = has o (x) such solutions whenever x > q^, for any fixed > 0. Our proof relies, among other things, on a refinement of a mean-squared estimate for short sums of the characters ^, averaged over 1 d-1, due to the first author, which goes beyond Burgess' theorem as soon as d is sufficiently large. We in fact show the alternative result that either (a) the partial sum of itself, or (b) the partial sum of ^, for ``almost all'' 1 d-1, exhibits cancellation on the interval 1, q^, for any fixed > 0. By an analogous method, we also show that the P\'olya-Vinogradov inequality may be improved for either itself or for almost all ^, with 1 d-1. In particular, our averaged estimates are non-trivial whenever has sufficiently large even order d.