# Complexity of random knot with vertices on sphere

Connect $n$ random points on a sphere in a cycle of segments between succesive points:

I would like to know the growth rate, with respect to $n$, of the crossing number (the minimal number of crossings of any diagram of the knot) $c(n)$ of such a knot. I only know that $c(n)$ is $O(n^2)$, because it is known that the crossing number is upper-bounded by the stick number $s(n)$: $$\frac{1}{2}(7+\sqrt{ 8 c(K) + 1}) \le s(K)$$ for any knot $K$. And $s(n) \le n$ is immediate.

I feel certain this has been explored but I am not finding it in the literature. Thanks for pointers!

-
What is the definition of the crossing number? –  Igor Rivin Feb 5 '11 at 16:30
I presume he means the minimal crossing number (on all plane diagrams) –  Bruno Martelli Feb 5 '11 at 16:50
Yes, as Bruno says. Sorry for not being clear. Edited now. –  Joseph O'Rourke Feb 5 '11 at 16:58
What do you mean by growth rate? This could be interpreted in different ways: the maximal crossing number for a given n, the average (with respect to the spherical measure), or the average (take all knot types constructed this way, and take the average crossing number). –  Ian Agol Feb 5 '11 at 17:23
@Agol: Good point! I meant the expected crossing number of the knot determined by $n$ random points on the sphere, which is I guess your 2nd option. –  Joseph O'Rourke Feb 5 '11 at 18:13

This is not really an answer but an over-long comment following up suggestions of Ian Agol and Bill Thurston.

Experiment suggests (with 97% confidence) that the crossing probability (in a specified or random projection, for two line segments with the four endpoints chosen independently uniformly at random with respect to Haar measure) is greater than $.2499$ and less than $.2501$. I have a motto never to compute by integrating what can be computed by symmetry, so the hope would be, for some integer $S$, to write a total of $4S$ symmetry-related expressions for the probability whose sum is identically $S$. So far any such trick eludes me; does anyone else see a way?

It would surprise me, for very large $n$, if even a constant factor improvement over a randomly chosen obvious projection is possible. I would wager, then (although I would hate to have to prove it) that $$\lim\limits_{n\rightarrow\infty} \frac{\bar{c}(n)}{n^2} = \frac18,$$ where $\bar{c}(n)$ is the expected value of crossing number for $n$ random points on the sphere.

The suggestion of a Voronoi-like spine whose dual would triangulate the knot complement is an interesting one. The individual faces are sections of hyperbolic paraboloid. It seems reasonable that their number would be strictly between linear and quadratic, although I don't yet see a good heuristic for guessing the correct order.

EDIT: I was able to satisfy myself that the crossing probability is exactly $\frac14$, through a fairly (and probably unnecessarily) involved process. At most stages one can reduce to simpler calculations using symmetries or nice facts such as the probability-preserving projection map from a $(d-1)$-sphere in $\mathbb{R}^d$ onto the ball of its first $d-2$ components. For the final step I did have to compute an integral, though—the same one that tells you the angular momentum of a spinning coin (whose axis of rotation is in the plane of the coin).

I have started to suspect that in a certain precise sense an integral is unavoidable—that the boundary of crossing configurations is curved in ways that prevent abutment, just as the region north of $30^\circ$ latitude carries exactly $\frac14$ of the surface area of a perfect globe, but no finite collection of $4S$ rotated copies of it can be an exact $S$-fold cover. (The transcendental answer to the usual Sylvester's four-point problem in the disc also discourages the finite cover approach.)

-
What a wonderfully specific conjecture! And the subquestion of proving that the probability of two random segments crossing in projection is $\frac{1}{4}$ is very pretty. –  Joseph O'Rourke Feb 9 '11 at 11:59
If the projections of the 4 points are not in convex position then the segments do not intersect. If the projections of the 4 points are in convex position, then 1 of the 3 of the ways of pairing the points causes the line segments to cross. So the $1/4$ conjecture is saying that the answer to Sylvester's problem for the projection of the uniform measure on the surface of the sphere is $3/4$. –  Douglas Zare Feb 9 '11 at 23:01
@Douglas Zare: Yes, in fact this is exactly how the experiment was run: the proportion of convex positions, divided by 3. The name of Sylvester's problem for the same question (with uniform measure) in a convex region of the plane is helpful. Apparently the problem is usually stated as the probability that the four points are $\textit{not}$ in convex position, so the crossing probability would be $\frac{1-p}3$ where $p$ is the Sylvester's problem for the sphere projection measure in a circle. (Conjecturally $p=\frac14$, with non-convex as likely as each of the 3 ways of crossing.) –  Tracy Hall Feb 10 '11 at 1:30

Edited 2/9 after discussion with Dylan Thurston

It seems unlikely that the obvious knot projections can be simplified by more than a constant factor, so a quadratic lower bound for the expected minimum crossing number seems likely. Crossing number by itself though is a strange measure of complexity, and it is hard to compute. However, it's bounded below by hyperbolic volume of the knot complement.

It would be possible to get some experimental evidence by feeding output of your random process through snappea, and looking at the distribution of hyperbolic volume. However, I think hyperbolic volume probably grows at a less than quadratic rate. You can imagine thickening the knot into a growing solid torus, pushing outward until every part of the boundary has bumped into other boundary --- similarly to a Voronoi subdivision. With tubes of diameter some constant times $n^{-.5})$, the total volume of tubes is on the order of the volume of the ball, so typical tube spacing should be $O(n^{-.5})$. This suggests the number of faces in this subdivision should be $O(n^{3/2})$, which would give a triangulation having $O(n^{3/2})$ tetrahedron where the knot is in the 1-skeleton, implying that the typical Gromov norm or hyperbolic volume probably grows as $O(n^{3/2})$. This would only imply $n^{3/2}$ crossings.

Marc Lackenby, in SPECTRAL GEOMETRY, LINK COMPLEMENTS AND SURGERY DIAGRAMS, developed a beautiful method to give lower bounds for crossing numbers for knots. His method possibly could be applicable to improve this situation, provided the Cheeger constants for these manifolds can be shown to be not too small.

It's also possible that one could estimate the degree of the Alexander polynomial, to get an estimate of the crossing number.

-
There's a strange formatting issue in the rendering of this on my computer, where $n^2$ is displaced from where it is in the text. If anyone knows how to fix this, feel free. –  Bill Thurston Feb 5 '11 at 17:16
I appreciate your guess that a quadratic lower bound seems likely. And I like the idea of gathering some experimental evidence. Thanks! –  Joseph O'Rourke Feb 5 '11 at 18:01

I think you should look at this paper "The average crossing number of equilateral random polygons" by Y Diao, A Dobay, R B Kusner, K Millett and A Stasiak. http://iopscience.iop.org/0305-4470/36/46/002

It can't seem to get the full text right now, so I'm not sure exactly what their random knot model is. It certainly isn't quite what you wanted, as they require their polygons to be equilateral. In their model the crossing number grows as $n \; \ln n$.

If this doesn't answer your question, consider looking through the rest of Ken Millett's work. He is one of the main people working on random knots.

-
Thanks for these useful references! I will look into Millett's work. –  Joseph O'Rourke Feb 5 '11 at 18:13

You can find estimates nd other relevant information in the following two papers:

Arsuaga, J., Blackstone, T.*, Diao,Y., Karadayi, E. , Saito, Y. Sampling Large Random knots in Confined Spaces. J. Phys. A: Math Gen. (2007) 40; 11697-11711

Arsuaga, J., Blackstone, T.*, Diao,Y., Karadayi, E. , Saito, Y. Linking of Uniform Random Polygons in Confined Spaces. J. Phys. A: Math. Gen. (2007) 40; 1925-1936

and The linking number and the writhe of uniform random walks and polygons in confined spaces E Panagiotou et al 2010 J. Phys. A: Math. Theor.

-