  The "short cycle removal" technique was recently introduced by Abboud,
Bringmann, Khoury and Zamir (STOC '22) to prove fine-grained hardness of
approximation. Its main technical result is that listing all triangles in an
$n^{1/2}$-regular graph is $n^{2-o(1)}$-hard under the 3-SUM conjecture even
when the number of short cycles is small; namely, when the number of $k$-cycles
is $O(n^{k/2+\gamma})$ for $\gamma<1/2$.
  Abboud et al. achieve $\gamma\geq 1/4$ by applying structure vs. randomness
arguments on graphs. In this paper, we take a step back and apply conceptually
similar arguments on the numbers of the 3-SUM problem. Consequently, we achieve
the best possible $\gamma=0$ and the following lower bounds under the 3-SUM
conjecture:
  * Approximate distance oracles: The seminal Thorup-Zwick distance oracles
achieve stretch $2k\pm O(1)$ after preprocessing a graph in $O(m n^{1/k})$
time. For the same stretch, and assuming the query time is $n^{o(1)}$ Abboud et
al. proved an $\Omega(m^{1+\frac{1}{12.7552 \cdot k}})$ lower bound on the
preprocessing time; we improve it to $\Omega(m^{1+\frac1{2k}})$ which is only a
factor 2 away from the upper bound. We also obtain tight bounds for stretch
$2+o(1)$ and $3-\epsilon$ and higher lower bounds for dynamic shortest paths.
  * Listing 4-cycles: Abboud et al. proved the first super-linear lower bound
for listing all 4-cycles in a graph, ruling out $(m^{1.1927}+t)^{1+o(1)}$ time
algorithms where $t$ is the number of 4-cycles. We settle the complexity of
this basic problem by showing that the $\widetilde{O}(\min(m^{4/3},n^2) +t)$
upper bound is tight up to $n^{o(1)}$ factors.
  Our results exploit a rich tool set from additive combinatorics, most notably
the Balog-Szemer\'edi-Gowers theorem and Rusza's covering lemma. A key
ingredient that may be of independent interest is a subquadratic algorithm for
3-SUM if one of the sets has small doubling.
