A certified upper bound for the distortion of the trefoil knot

Introduction

For a rectifiable closed curve $\gamma$ let $d_{\gamma}(p,q)$ be the length of the shorter of the two arcs of $\gamma$ joining $p$ and $q$, and

Gromov [4, 5] showed $\delta(\gamma)\ge\pi/2$, with equality only for the round circle, and asked whether $\delta(K)$ is bounded over all knots; Pardon [7] proved that it is not. Denne and Sullivan [3] proved $\delta(K)\ge5\pi/3$ for every non-trivial tame knot; a recent computer-assisted preprint [9] claims $\delta(K)>6.5321$. For the trefoil, Denne and Sullivan mention that numerical simulations [6] produced a trefoil with distortion less than 7.16; to our knowledge this is the only upper bound recorded, and it is not accompanied by a certificate.

Since $\delta$ is invariant under all isometries of $\mathbb{R}^{3}$, reflections included, the bound holds for both the left- and the right-handed trefoil. The numerical value of $\delta(F)$ is about 6.9173; we do not claim that $F$ is close to optimal.

Knot type

The starting polygon. Let $\Sigma$ be the polyhedral torus with vertices $V(a,b)=((R+rc_b)c_a,(R+rc_b)s_a,rs_b)$, $a,b\in\mathbb{Z}/4$, where $(c_k,s_k)=(\cos\frac{k\pi}{2},\sin\frac{k\pi}{2})$, $R=8$, $r=5$. Since $R>r>0$, its faces $V(a,b)V(a+1,b)V(a+1,b+1)V(a,b+1)$ are planar convex trapezoids and $\Sigma$ is an embedded torus bounding an unknotted solid torus. On the chart $(\alpha,\beta)\in(\mathbb{R}/\mathbb{Z})^2$ of $\Sigma$ (bilinear on each face, mapping the boundary of each grid square homeomorphically onto the boundary of the face) consider the line $t\mapsto(2t,3t)$. It meets the grid corners only at $t\in\frac{1}{4}\mathbb{Z}$, at four distinct corners. Cutting it at the grid lines $\alpha,\beta\in\frac{1}{4}\mathbb{Z}$ gives points on the boundaries of the faces; consecutive cut points lie on the boundary of a common face, and $P_0$ is formed by the straight segments joining them. Distinct passes of the line through a grid square are parallel chords, whose endpoints do not interleave on the boundary of the square, hence not on the boundary of the face; two straight chords of a convex polygon with non-interleaving endpoints are disjoint. So $P_0$ is a simple closed curve on $\Sigma$, isotopic on $\Sigma$ (face by face) to the image of the line, a curve of class $(2,3)$, hence a trefoil [8 §3.C]. Each of its 16 edges is subdivided into 6 equal parts; the 96 vertices are rational and become integers in the unit $1/U$, $U=36\cdot2^{14}$.

Proof. Points of an edge move by at most $\delta_0$, so non-adjacent edges of $C_s$ stay at positive distance. An edge vector moves by at most $2\delta_0<\lvert e\rvert$, so its direction turns by at most $\arcsin(2\delta_0/\lvert e\rvert)$, and by (ii) the turning angle between adjacent edges stays below $\theta+2\arcsin(\cos(\theta/2))=\pi$; adjacent edges meet only at their common vertex. So every $C_s$ is embedded. By compactness there is $\eta>0$ such that, for all $s$, non-adjacent edges of $C_s$ are at distance $>\eta$, edges are longer than $\eta$ and turning angles are below $\pi-\eta$. Cut $[0,1]$ into intervals on which every vertex moves by less than $\epsilon$, and on each of them move the vertices one at a time. For $\epsilon$ small in terms of $\eta$, the two triangles swept by one such move meet the polygon only along the two edges being moved, so each move is an elementary ($\Delta$-) move; hence $C$ and $C'$ are equivalent [2 Ch. 1]. □

The path. The certificate lists integer polygons $X_0=P_0,X_1,\ldots,X_{75}$ (unit $1/U$); then every edge of $X_{75}$ is split at its midpoint, which leaves the polygon unchanged and is exact in the unit $1/(2U)$, and 44 further polygons follow, the last being $F$. Each step $A\to B$ is subdivided by the integer points $A+\lfloor j(B-A)/m\rfloor$, and every sub-step satisfies Lemma 2. In verifier (i) both conditions are checked exactly, in integers. Write $D$ for the largest squared displacement of a vertex (so $\delta_0^2=D$), $d_U=\lfloor\sqrt{D}\rfloor+1>\delta_0$ and $\ell_i=\lfloor\sqrt{\lvert e_i\rvert^2}\rfloor+1>\lvert e_i\rvert$. Condition (i) follows from $\operatorname{dist}(e_i,e_j)\ge\lvert m_i-m_j\rvert-\frac{1}{2}(\lvert e_i\rvert+\lvert e_j\rvert)$ ($m$ the midpoints) when $4\lvert m_i-m_j\rvert^2>(4d_U+\ell_i+\ell_j)^2$, and otherwise from the exact rational distance between the two segments; pairs whose midpoints are farther apart are excluded by an exact integer grid. For (ii), with $n_0=\lvert e_0\rvert^2$, $n=\lvert e\rvert^2$, $m=\min(n_0,n)$ and $P=\lfloor\sqrt{n_0n}\rfloor$, the condition $4\delta_0^2<m(1+\cos\theta)/2$ is implied by the integer inequality $8D(P+1)<m(P+e_0\cdot e)$. Coordinates are asserted to be below $2^{24}$. Hence $F$ is a trefoil.

Distortion of a polygon

Let $F$ have vertices $v_0,\ldots,v_{n-1}$ and edges $e_i=[v_i,v_{i+1}]$ (indices mod $n$). Every pair of distinct points lies on a pair of edges, so $\delta(F)=\max_{i\le j}\delta_{ij}$, where $\delta_{ij}$ is the supremum of the ratio over $p\in e_i$, $q\in e_j$, $p\ne q$. For $i=j$ the ratio is at most $1$.

Proof. For points at distances $x,y\ge0$ from $V$, not both zero, the arc through $V$ has length $x+y$, so $d_F(p,q)\le x+y$, and $|p-q|^2=x^2+y^2-2xy\cos\varphi$. Now

so $(x+y)^2/|p-q|^2\le2/(1-\cos\varphi)=1/\sin^2(\varphi/2)$. □

With integer vectors $u=v'-V$, $w=v''-V$ along the two edges, $1/\sin(\varphi/2)\le D$ is equivalent to $(D^2-2)|u||w|\ge D^2u\cdot w$, which holds if $u\cdot w\le0$ and is otherwise checked in squared form with exact integers.

Proof. The two arcs between $p(s)$ and $q(t)$ have lengths $(1-s)|e_i|+\sum_{i<k<j}|e_k|+t|e_j|$ and $s|e_i|+\sum_{k\notin[i,j]}|e_k|+(1-t)|e_j|$, bounded by $a_1$ and $a_2$ on the box. The points $p(s),q(t)$ lie on the two sub-segments. □

For each non-adjacent pair the verifier starts from the box $[0,1]^2$ and accepts a box when $D^2\operatorname{dist}^2\ge\min(a_1,a_2)^2$, splitting it into four otherwise. The sub-segment endpoints are rational, the squared distance between two segments is computed exactly as the minimum over the candidate points of the convex quadratic (interior critical point and the four sides of the parameter square), and $\ell_k^+=\lceil2^{20}|e_k|\rceil/2^{20}$ is computed with integer square roots. All comparisons are exact.

The certificate and its verification

Result. The path has 75 + 44 steps and 249 + 44 certified sub-steps; $F$ has 192 vertices. All 18 336 pairs of edges of $F$ satisfy the bound 6.92 (806 580 boxes, maximal depth 7).

Verification. The certificate is the set of files anc/DIST_trefoil_*.csv: exact integer coordinates, one file per array, the first line giving its shape. (i) anc/verify_dist.py, with certlib.py, cert_dist.py and p0.py (Python 3 with numpy): every test is an exact integer or rational test, as described above; floating point only chooses how finely a step is subdivided. It runs in about two minutes. (ii) anc/verify2_dist.py (numpy, scipy, python-flint), written separately except for the definition of $P_0$ (p0.py), which both share: for the path, a KD-tree candidate search with double precision, explicit margins and exact rational distances for close pairs; for the distortion, Arb balls [1] and, on each box, the Lipschitz bound $|p(s)-q(t)|\ge|p(s_c)-q(t_c)|-h_s|e_i|-h_t|e_j|$ about the centre of the box instead of the exact sub-segment distance. Both accept the certificate with the bound 6.92. The two programs implement the same reductions, Lemmas 2, 3 and 4, so their agreement guards against programming errors, not against an error in these lemmas. Both reject the bound 6.94 for the 96-vertex polygon $X_{75}$, whose distortion is about 6.9441; the path checks reject a path in which one vertex of one intermediate state is moved onto another strand, and a path ending at the reflection of $X_{75}$ in a plane, which is the other trefoil. When a claimed bound is wrong by a very small amount, the exact verifier may need a long time before rejecting it; it never accepts it.