  We prove that for every decision tree, the absolute values of the Fourier
coefficients of a given order $\ell\geq1$ sum to at most
$c^{\ell}\sqrt{\binom{d}{\ell}(1+\log n)^{\ell-1}},$ where $n$ is the number of
variables, $d$ is the tree depth, and $c>0$ is an absolute constant. This bound
is essentially tight and settles a conjecture due to Tal (arxiv 2019; FOCS
2020). The bounds prior to our work degraded rapidly with $\ell,$ becoming
trivial already at $\ell=\sqrt{d}.$
  As an application, we obtain, for every integer $k\geq1,$ a partial Boolean
function on $n$ bits that has bounded-error quantum query complexity at most
$k$ and randomized query complexity $\tilde{\Omega}(n^{1-\frac{1}{2k}}).$ This
separation of bounded-error quantum versus randomized query complexity is best
possible, by the results of Aaronson and Ambainis (STOC 2015) and Bravyi,
Gosset, Grier, and Schaeffer (2021). Prior to our work, the best known
separation was polynomially weaker: $O(1)$ versus $\Omega(n^{2/3-\epsilon})$
for any $\epsilon>0$ (Tal, FOCS 2020).
  As another application, we obtain an essentially optimal separation of
$O(\log n)$ versus $\Omega(n^{1-\epsilon})$ for bounded-error quantum versus
randomized communication complexity, for any $\epsilon>0.$ The best previous
separation was polynomially weaker: $O(\log n)$ versus
$\Omega(n^{2/3-\epsilon})$ (implicit in Tal, FOCS 2020).
