  Szemeredi's regularity lemma can be viewed as a rough structure theorem for
arbitrary dense graphs, decomposing such graphs into a structured piece (a
partition into cells with edge densities), a small error (corresponding to
irregular cells), and a uniform piece (the pseudorandom deviations from the
edge densities). We establish an arithmetic regularity lemma that similarly
decomposes bounded functions f : [N] -> C, into a (well-equidistributed,
virtual) -step nilsequence, an error which is small in L^2 and a further error
which is miniscule in the Gowers U^{s+1}-norm, where s is a positive integer.
We then establish a complementary arithmetic counting lemma that counts
arithmetic patterns in the nilsequence component of f.
  We provide a number of applications of these lemmas: a proof of Szemeredi's
theorem on arithmetic progressions, a proof of a conjecture of Bergelson, Host
and Kra, and a generalisation of certain results of Gowers and Wolf.
  Our result is dependent on the inverse conjecture for the Gowers U^{s+1}
norm, recently established for general s by the authors and T. Ziegler.
  REVISED November 2020: This paper has been revised so that only systems of
linear forms satisfying a condition called the flag property are covered by the
counting lemma. Translation-invariant systems, as well as systems of
Cauchy-Schwarz complexity 1 and some other naturally-occurring systems have
this property. We thank Daniel Altman for drawing our attention to what
appeared to be a minor technical issue in one of our proofs but which
ultimately led us to realise that the the counting lemma fails quite badly
(with rather simple examples, which we shall describe) without some assumption
of this type.
  Additionally, we supply a short appendix showing that the Gowers-Wolf
complexity of a system is bounded by its Cauchy-Schwarz complexity.
