Exponential sums with automatic sequences

Abstract

We show that automatic sequences are asymptotically orthogonal to periodic exponentials of type $e_q(f(n))$, where $f$ is a rational fraction, in the Pólya-Vinogradov range. This applies to Kloosterman sums, and may be used to study solubility of congruence equations over automatic sequences. We obtain this as consequence of a general result, stating that sums over automatic sequences can be bounded effectively in terms of two-point correlation sums over intervals.

14 pages