Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

(Apologies in advance for any imprecision in the following; I am a computer scientist and regret never having taken an actual course on topology.)

One way to define the pure braid group $P_n$ is as follows: consider a pure braid to be a set of $n$ non-intersecting arcs in $x,y,t$-space which are monotone in the $t$ direction, such that the $i$th arc connects $(i,0,0)$ to $(i,0,1)$. Sets of arcs which can be deformed continuously into each other without any arcs intersecting are considered equivalent pure braids.

Consider a generalization where the endpoints are not integer positions on two lines, but arbitrary fixed positions in the $t = 0$ and $t = 1$ planes. It seems clear to me that this does not change the topology of the space [1], so I will call such a collection of arcs an embedded braid. I'm looking at characterizing "optimal" embedded braids that minimize a certain functional $F$. For concreteness, let $F$ be the total length of the arcs (the actual functional I need to use is slightly different, but this should be close enough to carry over the results).

If the requirement that arcs do not intersect is removed, the space of embedded braids can be given an affine structure over which $F$ is convex, and it is immediately apparent that there is a single local minimum which is the global minimum: connect each pair of endpoints with a straight line. What can we say about the local minima of $F$ if we retain the non-intersection property? My intuition says that each topologically distinct braiding (corresponding to a particular element of $P_n$) forms a connected component with a unique local minimum, but I cannot tell how to begin proving this. It would be true if one could show that the connected components are convex subsets of the space; this does not hold under the "obvious" affine structure where we treat each arc and each $t$ independently, but that leaves the possibility of some other choice of affine structure which works. Are there some nice proof techniques that would help proving uniqueness of local minima in this context? Would any ideas or analogies from the theory of minimal surfaces help?

As Andrew Stacey mentions, the connected components are open subspaces; I believe existence of local minima can be guaranteed by considering the closure of the component seen as a subset of the space of embeddings that allow intersection. (Following Kevin Walker's comment, I realize this is called compactification.) This would include embeddings "on the boundary", whose arcs can intersect but which are only an infinitesimal displacement away from non-intersecting embeddings with the right topology. As a concrete example, the following braid,

\   /
 \ /
  \
 / \
 \ /
  \
 / \
/   \

on being pulled tight, approaches a configuration where the arcs are infinitesimally close together in the middle; the minimal length is attained by the intersecting embedding where the two arcs share a common point.

[1] Since the endpoints are fixed, we can associate each such generalized braid uniquely with a pure braid by shrinking the $t$ dimension slightly and composing each arc $i$ with a fixed arc from its endpoints to $(i,0,0)$ and $(i,0,1)$ respectively.

share|improve this question
1  
Are you willing to compactify your space of embeddings to include a boundary where the strings touch each other (but don't pass through each other)? If not, I don't think the minimum is attained. Intuitively, if we pull the strings tight, then for most braids the tight configuration will involve strings which touch. If we allow this sort of braid, then one can show that any minimal configuration consists of straight line segments and "infinitesimally small" knotted vertices -- linearly embedded graphs with each vertex corresponding to some braid that has shrunk very small. –  Kevin Walker Jun 24 '10 at 14:28
    
Apparently my edit was too slow -- yes, compactifying the space is exactly what I want. Can you elaborate on your final sentence in an answer? It sounds like the solution to my problem. –  Rahul Jun 24 '10 at 15:11
    
When I read this, I thought of the concept of ropelength (see en.wikipedia.org/wiki/Ropelength). This is not the problem you describe, but at least in that case, the problem of proving that a minimum ropelength embedding exists has been formulated and solved in arxiv.org/abs/math/0103224 –  j.c. Jun 24 '10 at 15:33
add comment

4 Answers

up vote 8 down vote accepted

UPDATE.

I revisited the question and realized that verifying the local CAT(0) property is not that easy. When I wrote the original answer, I was under impression that removing any collection of codimension 2 subspaces (more precisely, their tubular neighborhoods) from $\mathbb R^n$ leaves one with a locally CAT(0) space. This is true in $\mathbb R^3$ but there are counterexamples in $\mathbb R^4$. This particular subset might satisfy the condition but this does not seem to follow from any "generic" argument.

Further, there are some discouraging examples. First, approximating by arcs by "ropes" with fixed-size square sections does not actually work: in this case there are non-unique minimal configurations. So one really needs to deal with zero-width ones. Second, if you consider 3 arcs and allow two of them intersect while deforming the braid (but still disallow intersections with the 3rd one), then again, you can have two distinct minimal configurations in the same equivalence class.

Below is the original answer (and I suggest that it is unaccepted).


I can prove uniqueness of a local minimum for another length-like functional (similar but not equal to the sum of lengths). I believe that it should work the same way for the sum of lengths, but unfortunately the underlying geometric theory does not seem to exist (yet?).

First let me reformulate the problem. Let $X$ denote the set of possible horisontal cross-sections of braids. This is the set of $n$-tuples of distinct points in $\mathbb R^2$. Geometrically this is $(\mathbb R^2)^n$ minus a collection of codimension 2 subspaces corresponding to positions where some two points coincide.

Actually I prefer another formalization: the arcs forming the braid are ropes of nonzero width and with square cross-sections. More precisely, the horizontal section of every rope is an $\varepsilon\times\varepsilon$ square (with sides parallel to the coordinate axes), and these sections should not overlap. So $X$ is $\mathbb R^{2n}$ minus a union of polyhedral heighborhoods of codimension 2 subspaces. This formalization makes the local structure simpler, and the original one is the limit as $\varepsilon\to 0$.

An embedded braid is a path $f:[0,1]\to X$. We want to minimize the functional $$ L = \int_0^1 \left(\sqrt{(df_1/dt)^2+1}+\dots+\sqrt{(df_n/dt)^2+1}\right) dt, $$ over all paths between two given positions $a,b\in X$, in a given connected component of the space of such paths. Here $f_i=f_i(t)$ are 2-dimensional coordinates. Another functional, $$ L' = \int_0^1 \sqrt{(df_1/dt)^2+\dots+(df_n/dt)^2+1}\ \ dt, $$ is easier to deal with, because this is the Euclidean length of the corresponding path $(f(t),t)$ in $X\times\mathbb R\subset \mathbb R^{2n+1}$. Let us work with $L'$.

The connected component of the set of paths is the homotopy class. Fixing the homotopy class of a path is the same as fixing endpoints of its lift to the universal cover of the space. (In the case of zero-width ropes, you first take the universal cover and then the completion in order to add "boundary cases".) And local length minimizers are called geodesics. So we want to show that, in the universal cover of $X\times\mathbb R$, every pair of points is connected by a unique geodesic.

Our space $X$ (and hence $X\times\mathbb R$) is a locally CAT(0) space. This can be shown using standard curvature tests for polyhedral spaces. A globalization theorem says that a complete, simply connected, locally CAT(0) space is globally CAT(0), in other words, it is a Hadamard space. So the universal cover is a Hadamard space. Hadamard spaces feature uniqueness of geodesics, hence the result.

Now what about the original functional $L$? It is also a length functional, but for a non-Euclidean norm on $\mathbb R^{2n+1}$. So, to carry over the proof, one needs to develop an analog of CAT(0) spaces modelled after Finsler spaces rather than Riemannian. I think it should be possible - after all, all this CAT(0) business is about convexity of distance, and this convexity is there in all normed vector spaces. But I have not heard of such generalizations (maybe this is just my ignorance).

share|improve this answer
    
This is an excellent answer, even if to a slightly changed problem. I don't think I can expect any better, so I'm accepting this answer. –  Rahul Jun 26 '10 at 6:04
add comment

Definition: A graph configuration of the braid is one where the strands are (straight) line segments, with a finite number of vertices. These vertices can contain infinitesimally small braids.

Claim: Any minimal configuration of the braid is a graph configuration. Proof: If a strand (or overlapping cable of strands) is not straight, then the length can be reduced locally by making it a little closer to being straight.

Claim: For a fixed set of upper and lower endpoints, there is a global bound (good for all braid types) on the length of the minimal configuration. Proof: Consider a graph with one central vertex and a segment joining this vertex to each endpoint. All braiding takes place at the central vertex. There is a unique location of the vertex which minimizes the total length.

Similar arguments show that for a fixed combinatorial type of graph, there is a unique length-minimizing configuration for that graph. I don't at the moment see a way to rule out the possibility that distinct graph types might realize the same global minimum.

share|improve this answer
    
Another comment is that a minimizer must be planar, since the endpoints lie in a plane. If not, project to the plane to decrease length. In fact, the same argument shows that the graph must lie in the rectangle which is the convex hull of the endpoints. What I'm not sure how to prove, but seems obvious, is that the minimizer should be monotonic on each strand. –  Ian Agol Jun 24 '10 at 16:46
    
The original question allowed the endpoints to lie anywhere in the upper and lower planes; they needn't lie on a line. Your remark about the convex hull still works in this case. I think I can construct a counterexample to your conjecture about monotonicity. –  Kevin Walker Jun 24 '10 at 17:49
    
@Kevin: Thanks, this is quite helpful in focusing my thinking. It occurs to me that for a given braid type, not all graph types have minimizing configurations -- for example, for the trivial braid with no crossings, if you try to find the length-optimal configuration for a graph type with nonzero vertices this way, you obtain a local maximum instead! This implies that a particular braid type has a unique local minimum iff there exists exactly one combinatorial graph type whose optimal configuration is a local minimum. This seems like a promising direction. –  Rahul Jun 24 '10 at 17:58
    
Correction: for a trivial braid, a graph configuration with nonzero vertices is not a local maximum like I said. It is a local minimum over the boundary of the space, but the total length is decreased by moving into the interior. –  Rahul Jun 24 '10 at 20:44
add comment

One immediate problem that I can see is that the condition "the strings do not cross" is an open condition so there's no theorem that says that minima must exist. If you take length as your function and consider two braids that cross:

\        /
 \      /
  \ /\ /
   /  /
  / \/ \
 /      \
/        \

then when you try to pull these tight, the minimum length will be achieved when they touch, but that's not allowed. So the function "total length" doesn't have a minimum on this space (as far as I can see).

share|improve this answer
    
This is true; I mean to ask for the minimization over the closure of possible embeddings of a given braid, including intersecting embeddings which are only an infinitesimal displacement away from the desired braiding -- such, in this example, as pulling the strings tight so they meet at a point then diverge again. I believe this is meaningful if non-intersecting embeddings are viewed as open subsets of the (closed) space of all embeddings that may or may not intersect. I was going to mention this in the original question, but I skipped it for brevity; I'll add it in again. –  Rahul Jun 24 '10 at 14:36
add comment

The generalization where the endpoints of the braid are not fixed is not very interesting: Pushing all braids in an $\epsilon-$neighbourhood of $(0,0,[0,1])$ one can get a total length arbitrarily close to $n$ where $n$ is the number of braids (with extremities in $(\star,\star,\lbrace 0,1\rbrace)$).

Fixing the extremities in $(\lbrace 1,\dots,n\rbrace,0,\lbrace0,1\rbrace)$, one gets no minimum but an infimum for each representant. Its length can be computed since it is an embedded graph with straight edges. The minimum over all representants is now achieved by a compacity argument (and is probably also achieved by an embedded graph). I am however not sure that this is very interesting since this minimum is uniformly bounded: make all strings converge into a sphere of radius $\epsilon$ at mid-height which contains all the interesting parts. In the limit we get a union of $n$ strands joining $(i,0,0)$ to $(n+1-i,0,1)$ all intersecting in $((n+1)/2,0,1/2)$ and this is the minimum for all braids joining $(i,0,0)$ to $(n+1-i,0,1)$. The concept of infinitesimally thin braids is thus not so interesting even in this more general setting.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.