  It was recently conjectured by Fyodorov, Hiary and Keating that the maximum
of the characteristic polynomial on the unit circle of a $N\times N$ random
unitary matrix sampled from the Haar measure grows like $CN/(\log N)^{3/4}$ for
some random variable $C$. In this paper, we verify the leading order of this
conjecture, that is, we prove that with high probability the maximum lies in
the range $[N^{1 - \varepsilon},N^{1 + \varepsilon}]$, for arbitrarily small
$\varepsilon$. The method is based on identifying an approximate branching
random walk in the Fourier decomposition of the characteristic polynomial, and
uses techniques developed to describe the extremes of branching random walks
and of other log-correlated random fields. A key technical input is the
asymptotic analysis of Toeplitz determinants with dimension-dependent symbols.
The original argument for these asymptotics followed the general idea that the
statistical mechanics of $1/f$-noise random energy models is governed by a
freezing transition. We also prove the conjectured freezing of the free energy
for random unitary matrices.
