  We derive a priori bounds on the size of the structure constants of the free
Lie algebra over a set of indeterminates, relative to its Hall bases. We
investigate their asymptotic growth, especially as a function of the length of
the involved Lie brackets.
  First, using the classical recursive decomposition algorithm, we obtain a
rough upper bound valid for all Hall bases. We then introduce new notions
(which we call alphabetic subsets and relative foldings) related to structural
properties of the Lie brackets created by the algorithm, which allow us to
prove a sharp upper bound for the general case. We also prove that the length
of the relative folding provides a strictly decreasing indexation of the
recursive rewriting algorithm. Moreover, we derive lower bounds on the
structure constants proving that they grow at least geometrically in all Hall
bases.
  Second, for the celebrated historical length-compatible Hall bases and the
Lyndon basis, we prove tighter sharp upper bounds, which turn out to be
geometric in the length of the brackets.
  Third, we construct two new Hall bases, illustrating two opposite behaviors
in the two-indeterminates case. One is designed so that its structure constants
have the minimal growth possible, matching exactly the general lower bound,
linked with the Fibonacci sequence. The other one is designed so that its
structure constants grow super-geometrically.
  Eventually, we investigate asymmetric growth bounds which isolate the role of
one particular indeterminate. Despite the existence of super-geometric Hall
bases, we prove that the asymmetric growth with respect to each fixed
indeterminate is uniformly at most geometric in all Hall bases.
