  The hypergraph regularity lemma -- the extension of Szemer\'edi's graph
regularity lemma to the setting of $k$-uniform hypergraphs -- is one of the
most celebrated combinatorial results obtained in the past decade. By now there
are several (very different) proofs of this lemma, obtained by Gowers, by
Nagle-R\"odl-Schacht-Skokan and by Tao. Unfortunately, what all these proofs
have in common is that they yield regular partitions whose order is given by
the $k$-th Ackermann function. We show that such Ackermann-type bounds are
unavoidable for every $k \ge 2$, thus confirming a prediction of Tao.
  Prior to our work, the only result of the above type was Gowers' famous lower
bound for graph regularity. In this paper we describe the key new ideas which
enable us to overcome several barriers which stood in the way of establishing
such bounds for hypergraphs of higher uniformity. One of them is a tight bound
for a new (very weak) version of the {\em graph} regularity lemma. Using this
bound, we prove a lower bound for any regularity lemma of $3$-uniform
hypergraphs that satisfies certain mild conditions. We then show how to use
this result in order to prove a tight bound for the hypergraph regularity
lemmas of Gowers and Frankl--R\"odl. We will obtain similar results for
hypergraphs of arbitrary uniformity $k\geq 2$ in a subsequent paper.
