A Formal Proof of Complexity Bounds on Diophantine Equations