Re: [math-fun] Interleavings of three arithmetic progressions
Bill T. wrote: << Interleavings of two translate to words reperesemting simple curves on a punctured torus. I think each one is also valid when extended in this case. The lex-min cyclic permutations are associated <--> their slope. Tjere are O(n^2) slopes admitting O(n) cyclic permutations. -- is there a good logical analysis of the 3D simplification base = slope for interleavings of 3? You can think of in terms of the cynical subdivision, as seen from the origin.
That seems a little jaundiced to me. But I was naively thinking of the torus also, perhaps in a different way: Given three real numbers a,b,c > 0, linear independent of each other and arbitrary reals a_0, ab_0, c_0, consider the line in R^3 [thought of as tiled by unit cubes] F(t) = (at + a_0, bt + b_0, ct + c_0)) Then F(t) enters successive unit cubes via faces perpendicular to the x_1, x_2, or x_3 axis in a specific order, which yields a sequence of 1's, 2's and 3's. Then: Which sequences of 1's, 2's, 3's are possible from any ordered triple of a,b,c as above? Or in general, which sequences of 1's through n's are possible ? (Or is this equivalent to the original question?) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele
On Fri, Jul 23, 2010 at 9:07 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Bill T. wrote:
<< Interleavings of two translate to words reperesemting simple curves on a punctured torus. I think each one is also valid when extended in this case. The lex-min cyclic permutations are associated <--> their slope. Tjere are O(n^2) slopes admitting O(n) cyclic permutations.
-- is there a good logical analysis of the 3D simplification base = slope for interleavings of 3? You can think of in terms of the cynical subdivision, as seen from the origin.
I foresee a whole branch of ipod-spell-correction–inspired mathematics. Cynical permutations, cynical field extensions,...
That seems a little jaundiced to me. But I was naively thinking of the torus also, perhaps in a different way:
Given three real numbers a,b,c > 0, linear independent of each other and arbitrary reals a_0, ab_0, c_0, consider the line in R^3 [thought of as tiled by unit cubes]
F(t) = (at + a_0, bt + b_0, ct + c_0))
Then F(t) enters successive unit cubes via faces perpendicular to the x_1, x_2, or x_3 axis in a specific order, which yields a sequence of 1's, 2's and 3's.
Then: Which sequences of 1's, 2's, 3's are possible from any ordered triple of a,b,c as above?
Or in general, which sequences of 1's through n's are possible ?
(Or is this equivalent to the original question?)
This is definitely the same thing as the original question, except that Dan is using "linearly independent" to cover Allen's requirement that the arithmetic progressions be non-intersecting -- what we really need in both cases is the requirement that ordering be well-defined. In 2-d, I think I understand why it's OK to assume your line passes through the origin, as long as you consider the sequence of lines-crossed up to cyclic permutation. As in Dan's model, you get all of Allen's sequences if you take arbitrary slopes and arbitrary starting positions (in the unit square). For sequences of length n, you only look at a part of the line that crosses n coordinate-axis-parallel lines. Now if you restrict your attention to the family of lines that pass through those same n lines in that same order, then the codimension-1 boundary must consist of lines that fail to be in the set because they touch an integer point, and the codimension-2 part are lines that pass through two points, one at each end of the line segment. Call one of these the origin, then the other is an integer point whose coordinates sum to n. You still need to justify uniqueness, and there's some checking to do around words that are powers of shorter words, but I think it all comes out in the wash. But in 3-d it's trickier. The events that we're recording in order involve our arbitrary line passing through unit squares parallel to one of the coordinate planes. The "wiggling the lines" argument, though, only seems to guarantee that your boundary cases touch a parallel-to-the-coordinate-axis line, not that you can get a boundary case to touch a vertex. Anyone with clarity on the 3-d picture, please enlighten us by (doing a better job than I just did of) explaining it. --Michael -- Forewarned is worth an octopus in the bush.
I foresee a whole branch of ipod-spell-correction–inspired mathematics. Cynical permutations, cynical field extensions,...
Indeed, I rechecked on my iphone, and it jadedly auto-corrects cubical --> cynical.
But in 3-d it's trickier. The events that we're recording in order involve our arbitrary line passing through unit squares parallel to one of the coordinate planes. The "wiggling the lines" argument, though, only seems to guarantee that your boundary cases touch a parallel-to-the-coordinate-axis line, not that you can get a boundary case to touch a vertex.
Anyone with clarity on the 3-d picture, please enlighten us by (doing a better job than I just did of) explaining it.
Here's something about the 3-d picture: As has been noted, the interleaving of a triple of arithmetic progressions <--> the sequence of intersections of a line L in R^3 with the faces of the cubical grid. Let T be standard 3-torus, R^3 mod the integral lattice. Let's consider the special case that L has rational slope. In this case the sequence will be periodic, where each period has a fixed numbers of each type: A a's, B b's, and C c's, assumed to have gcd =1. How many different periodic sequences can occur? Consider the projection of the 3-torus a 2-torus T/L obtained as the quotient by L. In this 2-torus are 3 curves, the images of gridlines parallel to the a, b and c axes (which are each single circles in T). These curves divide T/L into a collection of 2-cells, where for any line parallel to L that maps to a point in the cell, the word (in a, b and c) is constant up to cyclic permutation, but at any edge, it changes by switching the order of some pair of adjacent letters. How many cells are there? Let's count the vertices. It's standard and not hard to see that when you have simple curves on a standard 2-torus in the classes (s,t) and (u,v), the number of intersections is the determinant of the matrix. s u t v. One way to think of it: the torus R^2 / < (s,t), (u,v) > is a covering space of the standard torus R^2 / <(1,0), (0,1)> with degree given by the determinant. Similarly, in our current situation: if you think of the 2-torus in the (a,b) plane, you can see directly that it's a covering space of T/L, with degree C. Therefore the image of the a-curve intersects the image of the b-curve C times (but only one of these is the image of a lattice point). By symmetry, there are a total of A+B+C - 2*#(triple points) vertices in the subdivision of T/L. There is at least one triple point: the image of (0,0,0). I'm feeling too lazy to figure out about others at the moment, but I suspect they could occur if to pairs among (a,b,c) have non-trivial common divisors but not the whole triple. For the moment, perturb each triple point to give 3 separate intersections: this gives us (A+B+C) vertices and adds one additional (spurious) 2-cell. Each vertex is an endpoint of 4 edges, each edge has 2 endpoints, so there are 2(A+B+C) edges, so since the Euler characteristic is 0, there are A+B+C 2-cells. In the actual subdivision where triple points haven't been perturbed, there are (A+B+C) - #triple points cells. It follows that the number of cyclically inequivalent sequences with A a's, B b's and C c's grows linearly with A+B+C ------ the triple point issue only effects at worst the linear rate of growth. So, for periodic sequences with fixed period P, we have O( P^2) choices of A, B and C adding to P, for each choice there are O(P) up to cyclic permutation each having O(P) cyclic permutations, resulting in a total of O(P^4). ---- Maybe with a little number theory one could get the exact formula for the number of periodic triple-interleavings of period P. It appears it should boil down to counting issues about greatest common divisors. *** I think you can proceed from this picture to analyze something about the general (non-periodic) case, but I don't have time to think on it more right now. --Bill T
--Michael
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Call me sentimental, but I'm a little sad to see cynical math go, particularly so soon after it was introduced. Something to turn the tables on tropical math is still needed. On Sun, Jul 25, 2010 at 4:50 PM, Bill Thurston <wpt4@cornell.edu> wrote:
I foresee a whole branch of ipod-spell-correction–inspired mathematics. Cynical permutations, cynical field extensions,...
Indeed, I rechecked on my iphone, and it jadedly auto-corrects cubical --> cynical.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://thaneplambeck.typepad.com/
participants (4)
-
Bill Thurston -
Dan Asimov -
Michael Kleber -
Thane Plambeck