  We consider a long-range percolation graph on $\mathbb Z^d$ where, in
addition to the nearest-neighbor edges of $\mathbb Z^d$, distinct
$x,y\in\mathbb Z^d$ are connected by an edge independently with probability
asymptotic to $\beta|x-y|^{-s}$, for $s\in(d,2d)$, $\beta>0$ and $|\cdot|$ a
norm on $\mathbb R^d$. We first show that, for all but a countably many
$\beta>0$, the graph-theoretical (a.k.a. chemical) distance between typical
vertices at $|\cdot|$-distance $r$ is, with high probability as $r\to\infty$,
asymptotic to $\phi_\beta(r)(\log r)^\Delta$, where $\Delta^{-1}:=\log_2(2d/s)$
and $\phi_\beta$ is a positive, bounded and continuous function subject to
$\phi_\beta(r^\gamma)=\phi_\beta(r)$ for $\gamma:=s/(2d)$. The proof parallels
that in a continuum version of the model where a similar scaling was shown
earlier by the first author and J. Lin. This work also conjectured that
$\phi_\beta$ is constant which we show to be false by proving that
$(\log\beta)^\Delta\phi_\beta$ tends, as $\beta\to\infty$, to a non-constant
limit which is independent of the specifics of the model. The proof reveals
arithmetic rigidity of the shortest paths that maintain a hierarchical (dyadic)
structure all the way to unit scales.
