  A spanner is a sparse subgraph that approximately preserves the pairwise
distances of the original graph. It is well known that there is a smooth
tradeoff between the sparsity of a spanner and the quality of its
approximation, so long as distance error is measured multiplicatively. A
central open question in the field is to prove or disprove whether such a
tradeoff exists also in the regime of \emph{additive} error. That is, is it
true that for all $\varepsilon>0$, there is a constant $k_{\varepsilon}$ such
that every graph has a spanner on $O(n^{1+\varepsilon})$ edges that preserves
its pairwise distances up to $+k_{\varepsilon}$? Previous lower bounds are
consistent with a positive resolution to this question, while previous upper
bounds exhibit the beginning of a tradeoff curve: all graphs have $+2$ spanners
on $O(n^{3/2})$ edges, $+4$ spanners on $\tilde{O}(n^{7/5})$ edges, and $+6$
spanners on $O(n^{4/3})$ edges. However, progress has mysteriously halted at
the $n^{4/3}$ bound, and despite significant effort from the community, the
question has remained open for all $0 < \varepsilon < 1/3$.
  Our main result is a surprising negative resolution of the open question,
even in a highly generalized setting. We show a new information theoretic
incompressibility bound: there is no function that compresses graphs into
$O(n^{4/3 - \varepsilon})$ bits so that distance information can be recovered
within $+n^{o(1)}$ error. As a special case of our theorem, we get a tight
lower bound on the sparsity of additive spanners: the $+6$ spanner on
$O(n^{4/3})$ edges cannot be improved in the exponent, even if any
subpolynomial amount of additive error is allowed. Our theorem implies new
lower bounds for related objects as well; for example, the twenty-year-old $+4$
emulator on $O(n^{4/3})$ edges also cannot be improved in the exponent unless
the error allowance is polynomial.
