  We show that any automatic sequence can be separated into a structured part
and a Gowers uniform part in a way that is considerably more efficient than
guaranteed by the Arithmetic Regularity Lemma. For sequences produced by
strongly connected and prolongable automata, the structured part is rationally
almost periodic, while for general sequences the description is marginally more
complicated. In particular, we show that all automatic sequences orthogonal to
periodic sequences are Gowers uniform. As an application, we obtain for any $l
\geq 2$ and any automatic set $A \subset \mathbb{N}_0$ lower bounds on the
number of $l$-term arithmetic progressions - contained in $A$ - with a given
difference. The analogous result is false for general subsets of $\mathbb{N}_0$
and progressions of length $\geq 5$.
