  Consider the random Cayley graph of a finite group $G$ with respect to $k$
generators chosen uniformly at random, with $1 \ll \log k \ll \log |G|$ (ie $1
\ll k = |G|^{o(1)}$). A conjecture of Aldous and Diaconis (1985) asserts, for
$k\gg\log|G|$, that the random walk on this graph exhibits cutoff.
  When $\log k \lesssim \log\log|G|$ (ie $k = (\log |G|)^{\mathcal O(1)}$), the
only example of a non-Abelian group for which cutoff has been established is
the dihedral group. We establish cutoff (as $p\to infty$) for the group of $d
\times d$ unit upper triangular matrices with integer entries modulo $p$
(prime), which we denote $U_{p,d}$, for fixed $d$ or $d$ diverging sufficiently
slowly. We allow $1 \ll k \lesssim \log |U_{p,d}|$ as well as
$k\gg\log|U_{p,d}|$. The cutoff time is $\max\{\log_k |U_{p,d}|, \: s_0 k\}$,
where $s_0$ is the time at which the entropy of the random walk on $\mathbb Z$
reaches $(\log |U_{p,d}^\mathrm{ab}|)/k$, where $U_{p,d}^\mathrm{ab} \cong
\mathbb Z_p^{d-1}$ is the Abelianisation of $U_{p,d}$. When $1 \ll k \ll \log
|U_{p,d}^\mathrm{ab}|$ and $d \asymp 1$, we find the limit profile. We also
prove highly related results for the $d$-dimensional Heisenberg group over
$\mathbb Z_p$.
  The Aldous--Diaconis conjecture also asserts, for $k gg\log |G|$, that the
cutoff time should depend only on $k$ and $|G|$. This was verified for all
Abelian groups. Our result shows that this is not the case for $U_{p,d}$: the
cutoff time depends on $k$, $|U_{p,d}| = p^{d(d-1)/2}$ and
$|U_{p,d}^\mathrm{ab}|=p^{d-1}$.
  We also show that all but $o(|U_{p,d}|)$ of the elements of $U_{p,d}$ lie at
graph distance $M \pm o(M)$ from the identity, where $M$ is the minimal radius
of a ball in $\mathbb Z^k$ of cardinality $|U_{p,d}^\mathrm{ab}| = p^{d-1}$.
Finally, we show that the diameter is also asymptotically $M$ when $k \gtrsim
\log |U_{p,d}^\textrm{ab}|$ and $d\asymp1$.
