Wikipedia:Reference desk/Archives/Mathematics/2019 April 9

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 9

Lattice question

(For the curious, this comes from an attempt to apply some maths to Rapper sword, and specifically to what types of locks can be made)

Take a 2d lattice made up of n straight lines. Where the lines cross, indicate which line is on top. Define a crossing as "bound" if, for both of the lines in the crossing, the crossings either side of the bound crossing are in the opposite direction (e.g. one line goes under-OVER-under, the other goes over-UNDER-over, where caps indicates the bound crossing).

The lines are all the same length (or all extend to infinity - either case is interesting/useful for the problem I'm considering). The lines may be at any angle.

Is it possible to make a lattice where each line has exactly one bound crossing? (particularly interested in n=5 or 6, but solutions for any n would be nice)

(probably more questions to come later relevant to knot theory, once I've figured out enough to phrase the question properly) MChesterMC (talk) 09:26, 9 April 2019 (UTC)

Partially answering my own question, for the case of n=8 with finite length swords, it is possible by taking the star polygon with Schlafli symbol 8/2 , selecting four points of the star (if numbered clockwise, points 1,2,5,6 work) and extending them beyond the point to form a crossing, and moving the lines that hit the other four points back by the same amount. You can then select the crossing direction to give one bound crossing on each line This is possible for the n/2 star for any n divisible by 4 (for odd n, you can't pair up the points, so this procedure results in either one line having no bound crossings, or two bound crossings. For n divisible by 2 but not 4, it will split into two odd-sided shapes, and the same argument applies to each of those shapes as to the star for odd n).

This solution can be extended to infinite length lines for n=8, by picking the crossing orientation for each crossing that is not in the infinite length case so that it does not bind either of the connected crossings.

For a star-based figure where n is odd, at least one of the bound crossings must not touch the central region of the star (otherwise you get 2 bound crossings on the same line)

I'd still be interested in whether this is possible for lower n, or for an odd n (odd n corresponds to arrangements which tend to be more stable when formed in the dance, and so easier to pick up without them falling apart). MChesterMC (talk) 11:43, 9 April 2019 (UTC)

A trivial case of yes: 4 lines, 3 parallel, one perpendicular to the other 3. If the "one line" goes over-UNDER-over you have one bound crossing and 2 unbound crossings. Do you distinguish between unbound as in over-OVER-under or similar and a "last crossing" as in "no_crossing-OVER-under"? -- SGBailey (talk) 12:21, 9 April 2019 (UTC)

All the lines need to have exactly one bound crossing, and a crossing is only bound if it alternates along both lines - so in your example, the central crossing is not bound (the perpendicular line goes under-OVER-under, the middle parallel line is only has no crossing-UNDER-no crossing). "no crossing-OVER-under" does not bind - the point is that you need the opposite crossings on both sides so you get a force on the middle crossing which pushes the lines together.

To clarify, if you take 3 horizontal lines and three vertical lines, and weave them together (so the crossings alternate along each line), only the central crossing is bound - it is the only one where, for __both__ lines in the crossing, the crossings on either side are in the opposite direction. MChesterMC (talk) 12:36, 9 April 2019 (UTC)

Just realized that it's never going to be possible for an odd number of lines - each bound crossing involves two lines, so for each line to have exactly one bound crossing, each bound crossing must be between a pair which does not overlap with any other pair (i.e. if lines 1 and 2 have a bound crossing between them, you cannot also have a bound crossing between lines 2 and 3). For odd n, this either leaves a line with no crossings or a line with two crossings (for n=5, have a bound crossing between lines 1 and 2, and between 3 and 4 - then you can't do anything with 5 to give it a bound crossing). Which only leaves the question of the case where n is even but not divisible by 4.

Other similar observations - any bound crossing involves at least 4 lines. Label the lines A,B,C,D. Make a crossing between lines A and B (A over B), and arrange it as a cross. To bind this, C must go over A and under B on one side of the cross (at 45 degrees to both A and B), and D must do the same on the other side. If you make C and D non-parallel, then you can select the direction of the crossing between them to give them each a bound one too - so it's possible for n=4. (this would be much easier with drawings, but I'm not able to do any in a useful way while at work) MChesterMC (talk) 12:56, 9 April 2019 (UTC)

(edit conflict) See [1], the last frame particular, for some additional context. There are a couple of technical meanings of the word 'lattice' in mathematics, see Lattice (order) and Lattice (group), which don't seem to be related. In this case the object in question is similar to a Knot diagram except using line segments instead of closed curves. An additional constraint is that each line must have at least 3 crossings, otherwise it's impossible to form a bound crossing. It appears that when n=4 and each line crosses the other 3 there are exactly two solutions, meaning that one you've made an over/under choice at one crossing the others are determined. If the number of crossings is always 3 or 4, then for a particular set of lines the problem of assigning over/under choices is equivalent to solving a system of linear equations over GF(2). Specifically, if there are three crossings on a line l, label them 0 if l is under and 1 if over. The the allowed choices are 010 and 101, in other words abc with a=b+1=c (mod 2). For four crossings the allowed solutions are 0100, 0010, 1011, and 1101, or abcd with a=d and b=c+1 (mod 2). Given this, it's easy to see for example there is no under/over assignment that works for the pentagram. (In the last frame of the video, each line has two bound crossings.) For a set of n lines, assuming 3 or 4 crossings on each line, the number of equations is 2n and the number of variables is between 1.5n and 2n. For lines with more than 4 crossings the situation is more complex, though linear algebra will probably reduce the number of putative solutions to be checked. --RDBury (talk) 13:18, 9 April 2019 (UTC)

I don't quite follow your proof that n = odd is impossible, but I do have an example with n = 7; in fact it can be generalized to any n ≥ 6. Start with three horizontal lines and four vertical lines. That makes twelve intersections in three rows of four. Using '–' to indicate that the horizontal row is over, and '|' to indicate that the vertical line is over. Then mark the intersections:

        – | – –
        | – | |
        – | – –

In general for 3 horizontal lines and k vertical lines there are 2(k-2) solutions. I'm pretty sure there are no solutions for n = 5, and perhaps your proof could be modified to prove that, but I just listed possible patterns of lines and eliminated them one by one, and I'm not totally sure it's a complete list. --RDBury (talk) 14:39, 9 April 2019 (UTC)

I found a configuration with n=5 that I missed and it does have a solution. It'll take a bit to write up details, which I'll post in a bit. The upshot is and n≥4 has a solution. --RDBury (talk) 15:08, 9 April 2019 (UTC)

Read my definitions again - I'm only defining an intersection as "bound" if the crossings alternate in __both__ directions, on __both__ lines (i.e. all four adjacent crossings are on the opposite direction. In your n=7 example, only the crossing in the middle of the second column is bound by that definition. If a crossing is bound, it is bound for both the lines involved by definition - from which my proof that a single bound crossing per line for odd n is impossible follows.

Actually, any arrangement with just horizontal and vertical lines will have lines without a bound crossing (at the top, bottom, left, and right). This line of thinking came about from trying to work out why an attempted "lock" using three vertical swords and three horizontal ones woven together was falling apart, and whether I could define a criterion for a lock being stable (which I think is "at least one bound crossing for each sword" - but I needed to find a lock with only one bound crossing per sword, and less than 6 swords, to test this with tonight, because all the standard lock figures I know have 2 bound crossings per sword). It ends up a little more complicated than that, since you can manually bind a crossing by using it to pick up the lock, gravity can help if a crossing is only partly bound (i.e. only has opposing crossings on some sides), the crossings need to be reasonably close, and shear forces can wreck a lock completely.

I appreciate that this isn't the standard definition of "lattice" - I was trying to use it as a generic term, and completely forgot about the mathematical meaning, sorry! Possibly "weave" might be more appropriate (though that implies parallel lines to me, so it's not ideal). MChesterMC (talk) 15:25, 9 April 2019 (UTC)

Frustatingly, I just found https://archive.bridgesmathart.org/2009/bridges2009-383.pdf which is the abstract for a workshop that seems to ask much the same questions - but doesn't give answers in the abstract. (this is a version of issue 2) on page 2 - issue 1) is solvable by realizing that every rapper figure corresponds to the 0-knot, and that the Reidemeister moves in knot theory correspond to simple actions in rapper dance). I'm going to attempt to email the author when I get home. MChesterMC (talk) 15:36, 9 April 2019 (UTC)

(edit conflict) Here's the solution I found for n=5. Take the lines to be (a) y=0, (b) y=1, (c) x=0, (d) x+y=4 and (e) y-x=2. There are 9 points of intersection ac (0, 0), ad (4, 0), ae (-2, 0), bc (0, 1), bd (3, 1), be (-1, 1), cd (0, 4), ce (0, 2) and de (1, 3). Label each point '–', '|', '/' or '\' according to which of its lines is over. Then label the intersections as follows:

• Line a) ae – (over), ac | (under), ad – (over)
• Line b) be – (over), bc | (under), bd – (over)
• Line c) ac | (over), bc | (over), ce / (under), cd | (over)
• Line d) cd | (under), de \ (over), bd – (under), ad – (under)
• Line e) ae – (under), be – (under), ce / (over), de \ (under)

Hopefully with a bit of pencil and paper sketching this should be clear, not really in the mood to do an SVG for this. Roughly the idea is to take a solution with n=4, and make a parallel copy of one of the 'outside' lines to one side. This process can be repeated to produce solutions with larger n. --RDBury (talk) 15:57, 9 April 2019 (UTC)

I still don't really understand the question but... Take 3 parallel vertical lines and weave with 3 perpendicular horizontal lines. Thus there are 9 crossings. The 4 corner crossings are unbound "no_crossing - OVER - under (say)", the 4 edge crossings are also unbound, but the one central crossing is bound and 1 is an odd number. Is this also too simplistic or a misunderstanding of the question? -- SGBailey (talk) 16:02, 9 April 2019 (UTC)

@SGBailey: The 4 edge crossings are bound relative to the lines forming the edges. In other words you can have a crossing that is bound relative to one of its lines but not the other; that's how I understand it at least.

Not sure what the exact conditions for a 'lock' are, but it seems clear that it would be necessary that there be at least two 'changes' on each line, where a change is defined to be adjacent intersections with opposite choices (over-under or under-over). In the pentagram lock shown at the end of the video there are three changes for each sword, which presumably requires a certain amount of flexibility in the swords (not to mention a certain amount of bravery on the part of the dancers). I believe there was some research on the mathematics of String figures which seems related, I remember it being way over my head through. --RDBury (talk) 16:30, 9 April 2019 (UTC)

Your understanding is wrong - for a crossing to be bound, it must be bound with respect to both lines (otherwise it will slip along the unbound line, and fall apart). The swords are flexible metal (they can be bent into a U shape and spring back to straight without too much effort), and if they can slide over each other, they will - a bound crossing restricts the movement of each sword in the direction of the other, which (when tight, mostly) fixes them together. If a sword slips enough, one of the crossings will come undone, while will unbind further crossings, allowing more swords to slip, until it all collapses (to which the traditional response is that the "Tommy" (equivalent to the fool in Morris) distracts the audience while the dancers reset, and our team's response is to shout "CHEESE IT!" and run off the stage).

I was wrong about the N=4 solution above (formed by placing an X into the cup of a V (extended down), so both lines in the X intersect both lines in the V - it's not actually stable, as the two "V-swords" have no bound crossings. By adding a sword to the bottom, we can bind the crossing at the base of the V (the new sword is still unbound, but stay with me here) - but this results in the X freely moving up and down in the V.

Therefore I think I'm wrong about the stability criterion in the first place - if each sword only has one bound crossing, then (I think) there will always be an opportunity for such free movement (as each set of 2 swords is not constrained by the other swords, so the problem then becomes each set of 2 moving around, rather than each sword moving around). A more accurate guess would be something like "Treating each crossing as a vertex of a graph, and the sword sections between connections as the edges, label each edge according to the sword it corresponds to, and label each vertex as "bound" or "unbound" (according to definition above - i.e. each connected vertex has an overlap in the opposite direction). A lock is stable if there is a (connected set of vertices/simple path/closed path) on which all vertices are bound and which includes at least one edge from each sword" (brackets because I'm not sure on the exact criterion there - but that's a matter for experiment later!).

There's probably a simpler way to express that, but I'll give it a poke myself later and see what I come up with. For now the only reason to keep the current question open is curiosity on the mathematical aspects.

String Figures and knot theory are related to the other question of which figures a dance team can make without letting go of the swords (since every possible figure resolves to a 0-knot) - this is actually considerably easier, since if you can work out how to resolve a drawing of a figure to a 0-knot (or, for a particular sword lock, how to connect the handles to form one - with each dancer holding two handles), deriving the moves to get into it is fairly simple (Reidemeister move I corresponds to a dancer spinning on the spot, II corresponds to a dancer jumping over a sword (or vice versa), and III corresponds to moving a sword over a crossing - there are more complicated versions of each depending on where the crossing is in the figure, but it's not hard to work through). MChesterMC (talk) 17:24, 9 April 2019 (UTC)