On character sums and exponential sums over generalized arithmetic progressions

Let χ (mod q) be a primitive Dirichlet character. In this paper, we prove a uniform upper bound of the character sum ∑_a∈A χ(a) over all proper generalized arithmetic progressions A ⊂ ℤ/qℤ of rank r: ∑_a∈A χ (n) <<_r q^1/2(log q)^r. This generalizes the classical result by Pólya and Vinogradov. Our method also applies to give a uniform upper bound for the polynomial exponential sum ∑ _n∈Ae_q(h(n)) (q prime), where h(x) ∈ ℤ[x] is a polynomial of degree 2 ≤ d < q.