A uniform bound for the minimal degree of an isogeny between principally polarized superspecial abelian surfaces

Let $p>3$ be a prime number. If $A$ and $B$ are two principally polarized superspecial abelian surfaces over ${\mathbb{F}}_{p^2}$ with $p^2$-Frobenius $[-p]$, we prove that there exists a separable polarized isogeny between them with multiplier at most $p\mathrm{/}\sqrt{2}$. The multiplier bound is uniform in the pair and asymptotically optimal up to a small multiplicative constant. Given quaternionic coordinates, we provide a deterministic algorithm that satisfies this upper bound in polynomial time. For unrestricted multipliers, ${\mathrm{K}\mathrm{L}\mathrm{P}\mathrm{T}}^2$ provides a heuristic algorithm with a multiplier upper bound of order $p^{6+o(1)}$ for arbitrary pairs and $p^{3+o(1)}$ when one polarization matrix is the identity matrix. Our algorithm’s improvement is an explicit upper bound below $p$ with an unconditional deterministic guarantee.