Exact sequence question

Replies

• 

  skipper

  Some group theory:
  The set that generates the first step - of which R'FDR' is a member is a g which is an element of G the set of all generators in the cube.
  This set leaves the "stack" as noted, anywhere in one of six places depending which face you start with (the particular orientation you assign to the R face). Then you can move the stack left or right, by first moving an "L" section of it, on the D face left or right, followed by two rotations of the faces with the remaining parts then a further D move. Moving left is D'RFD', to the right is DF'R'D.
  
  The first left-hand move that restores the stack is a direct copy of itself - the remainder of the cube is a mirror image of the starting position (after the first g step). From here the solved state is at the same distance, four moves or 4m, and there is a g' that gets there which is complementary to g (the "stack generator")
  
  The "stack" or figure is a characteristic of the group of generators; these are restricted to three adjacent faces - no opposites - one of which moves twice while the other pair move once. The two single moves occur together (i.e. m[sub]1[/sub]m[sub]2[/sub]) whereas the double move is split as m,m or the "comma" is the function "FR" or its complement.
  The set of generators, over 3 faces that transport this stack of cubes around the larger space, is an orbit for the figure "x" which is the stack itself. Or more exactly the orbit is all the positions the figure can be moved to: it takes 4m to move the whole thing.
• 

  skipper

  Switching theory:
  
  The Rubik's cubes are all made so you can rotate any face, clockwise or anticlockwise. This is equivalent to inverting one of two inputs of a switch. If the turn is equivalent to 2 quarter turns, that also makes it equivalent to inverting both inputs of a 2-way switch.
  A 'squared' turn is equivalent to a crossbar switch being closed; no turn means it's open. The quarter turn 'metric' is equivalent to an inverter.
  
  A single 2-way crossbar handles exactly 2 inputs, how many are needed to handle 4 inputs?
• 

  skipper

  I should be more specific with the term "handle"; I mean by this that a given switching network can switch an input to an output without loss. A single X-switch crosses two inputs; a single input is then equivalent to a signal which is switched spatially. If instead the signal has its parity changed (the switch function effectively multiplies the input by -1) the switch still controls this.
  
  Therefore a 2-input crossbar is topologically equivalent to a controlled inverter for one of two signals. If both signals are "handled" the switch is equivalent to a 3-input, 2-output gate. One of 3 inputs controls the other 2 outputs. This can be set up as a controlled-NOT or CNOT gate.
  
  A switching net is built up of blocks of 2xn crossbars and in that case, n is 3 for 4 inputs. This is because 4 switches can only handle 2 of the 4 inputs, 2 others have to be disconnected. To recover these and have all 4 inputs connected to 4 arbitrary outputs (allow all combinations/permutations of 4 signals) you need 2x3 2-input, 2-output crossbars. Then there are 6 control signals, for 4 bits, where 1 control is needed for 2 bit switching.
  
  The scaling you require for binary signal combinations (2,4,8,... inputs) is what's used in modern switching fabrics or meshes, called Benes nets. Each column of switches is a word in the array of random "switch settings". A question is: given an input m bits wide (say 16), how many random settings correspond to a given output word?
• 

  Kaustubh Katdare

  *I need a cool head to go through this*. Thread subscribed!
• 

  skipper

  From wikipedia's Clos Network on Clos switching nets (invented by the telecommunications industry in the 19th and early 20th centuries), here is a diagram of an 8-input Benes net (Note the control lines are omitted from the diagram):
  
  
  
  You can see how a 4-bit input word length is embedded in a larger input/output word.
  Consider that for a random output which is equal to the input word, there are m permutations for the switch array that will copy the input to the output, because there are multiple paths for each input on the left to each output on the right.
• 

  skipper

  Well, thanks to Cube Explorer I now know the length of the "word" that corresponds to my stack-generator: R'FDR' which I label g[sub]1[/sub]. If I call X the solved state, then gX is the "stacked" state, and gXg[sup]-1[/sup] = X (more exactly gXg[sup]-1[/sup] ~ X, where "~" means equivalence or congruence, or isomorphism, literally "having the same form").
  
  The length of the cycle that takes the stack (as three sections of the cube, i.e. 2+3+2 sub-cubes) around the 4 faces (R,B,L,F) using the D face as a kind of shift register, is 8 moves, which are:
  DB'L'DDF'R'D (g[sub]2[/sub]). If this is repeated exactly 63 times, or 63[D B'L' D[sup]2[/sup] F'R' D] it returns to the initial state, i.e. g[sub]1[/sub].
  
  The length of g[sub]2[/sub] is 8 (staying in the QTM) which is twice the length of g[sub]1[/sub]. That is: length(g[sub]2[/sub]/g[sub]1[/sub]) is 2. So there are 126 equivalent moves in g[sub]2[/sub]; add the inital generator and its inverse, there are 128 4-cycles in Gx the orbit.
  
  Note: the group g[sub]2[/sub] "operates" or acts on 5 faces, the g[sub]1[/sub] on 5 - 2 = 3 faces (2 is an additive identity in the quotient); this means the projective space is over the field of 5 elements or F[sub]5[/sub]. The "fixed point" is the vertex or top of the stack (wherever it gets "fixed" by the cycle it's in). Note also the stack itself contains 7 sub-cubes which are decomposed, first into 5 + 2, then into 2 + 3 + 2, so the D face cycles (5 - 2) -> (3 + 2) sub-cubes, two adjacent or adjoint faces "carry" 0 +/- 2 sub-cubes.
  
  What is the connection (topologically speaking) between the cycles in the groups I'm using and a Benes net with an input word length which is a power of 2? How do I extend the notion of inverting a signal or two signals simultaneously to the group cycles? Does inverting a generator like [R' FD R'], to [R D'F' R] correspond to inverting a signal, and what is the signal?
• 

  skipper

  I should add to this that I did a postgrad in parallel computation, in which an assignment was to design and implement a simulation of a 16-bit Benes net and map a given input to a given output (choose two 16-bit random words). The assignment was to determine the best way to map the input to the output word; is a deterministic algorithm or a non-deterministic one better, and so on.
  
  At one stage during the testing of an early prototype I managed to soak up the entire virtual memory of a VAX-11/660. That was because I wrote an entirely recursive or depth-first algorithm which didn't do any pruning; I was obliged to rewrite the program with extended sequential sections (which made a complete traversal from input to output, one bit of the word at a time), and recurse this inner sequential approach.
  
  I wanted to spend more time on this one, but unfortunately the dept had a policy of archiving student accounts and preventing access during vacations, for security reasons (hassling around to get the required "clearance" and restore my assignment wasn't something I looked into). The point of all this is that, once you have a valid map that sets all the crossbars so the output is "correct" this can possibly be done in parallel, so the next level is finding a parallel solution (or rather simulating one).
  
  This was while we studied PRAM models and various approaches to parallelizing memory read-write ops, semaphores and deadlocking, etc.
• 

  vishnu priya

  It really takes a long time to go through this..
• 

  skipper

  Well, it would take a long time to enumerate all the 4.3 quintillion possible permutations of the 3x3x3 Rubik's cube; however calculating the number of permutations is easy.
  
  The inescapable part is that the permutation puzzles (of any stripe) have a direct representation in switching theory. Switching is by definition both a serial and a parallel operation. In other words if N people have a Rubik's cube, and they can all communicate with each other randomly or in some directed way, then eventually the N people will enumerate all possible permutations.
  
  The catch is that there are several paths to the same permutation; every permutation of an NxNxN cube puzzle has an inverse or mirror-image, as I tried to show above. The connections to switching fabrics, of which the Benes array is the smallest possible (i.e. the "switching atom" is 2 signals wide), are kind of obvious too. It's a matter of determining the binary nature and finding 2-s complement 'arithmetic' in the vector space. Simple really, if you can design the right algorithms.
  
  The algorithms above are called "generators", or you could label them "rotors" of the stack-character, which is of course a Turing-symbol.
• 

  skipper

  Another thing I could mention: the generators I've listed are a way to solve a scrambled cube.
  The "trivial step" in reconstructing a solved state is to make pairs of matching sub-cubes or "cubelets". That is, you start by matching up pairs, then match up pairs of pairs and so on.
  
  The first thing I do to a scrambled 3x3x3 cube is restore the edges of two layers, leaving the corners. Then I fill up three corners with matching pairs, leaving a single corner unsolved - the "corner" extends over two layers, and the rest of the first two layers is solved. Now I use the unsolved corner and the remaining layer (at the "bottom") to unscramble the rest.
  
  At this point the cube is in a state that "uses" the stack-generating algorithm, which is based on the "freedom" of the unsolved D-slice, and the way parts of the stack can be "stored" temporarily on the side-faces (R,B,L,F). There is no requirement to use the total distance - 126 moves - because you can reverse direction at any point. Various tweaks can be applied to the algorithm to transport a flipped cubelet to its proper orientation in the stack.
  
  This algorithm always restores the cube to either gX or Xg[sup]-1[/sup], so you just use g[sub]1[/sub] or its inverse, to get to the solved state.
  
  PS, the symbol, or stack character I call "X" goes by the group-theoretic moniker: outer automorphism of the symmetry-group S[sub]6[/sub]. X is a fixed (or "floating") point on the n-sphere, somewhere near a horizon H[sub]n[/sub]. It has connections in three obvious directions to a "pole" over the horizon - call this a geodesic curve, represented by the algebra presented by the cube, and the "components" the generator reveals on each face. Ok, so the n-sphere has points on it with geodesic connections to poles and connections to the real sphere inside the cube which is empty, as is the sphere that circumscribes it and touches 8 corners.
  
  It's all in the numbers, which are powers of two - the cube puzzles double something, and in a sense are a solution to the doubling "problem" q.v.
• 

  skipper

  Uh hm.
  So, if you get your hands on a couple of cube puzzles you can do the "twist" move that builds a stack as an outer automorphism and kick off a lecture - using only the cubes - about group and switching theory and how the notion of a signal is entirely abstract.
  
  A signal can be as simple as a connection being made and "unmade", this is how telegraph signaling works, and Very lanterns are the naval "light-based" equivalent, Morse code is the basis (0,1) as run-length encoding - the speed was up to the operator.
  
  If all the inputs to a switching net are digital, that means there is an input word presented in parallel at time t, and an output word at time t'. Either the input is preserved at the output or it gets changed by the switch settings. So each column in the array is a linear transformation (in space) of part of the input. The output is the sum of transformations.
  
  Likewise the "X" on the cube is a sum of linear transformations. You know there is a "solved" state or signal to recover (but this can in fact be any of the possible permutations or its inverse/complement) and that there are partial solutions - you just have to physically arrange these 'parts' in a certain way to get to the signal you want to restore.
• 

  skipper

  Now I have several sequences in hand for the cube groups. The questions in Rubik's permutation puzzles are along the lines: "how many steps are needed to enumerate all possible permutations", and for subgroups of permutations that can be reached by subsets of generators with a "face-metric".
  
  The metric of the cube is its structure group - there is a fundamental distance-generator which is also a divisor of the sliced cube. This is another way of saying the slices have distances they can be at, or "places" much like digits have places in numbers. In the case of a single face-metric (project a single face of the cube, so its color "vanishes" or is irrelevant) there are 4 places for the "digits", r[sup]1[/sup]r[sup]2[/sup]r[sup]3[/sup]r[sup]4[/sup]. But the last digit = r[sup]1[/sup], because the 1-face metric is a ring (homomorphism); it has an additive identity = +-r
  
  Anyhoo, it's easy to get the hang of all the group theory if you think about codes, and encoding. This is the realm of computation, since all problems which are computable are encoding/decoding problems. An important step is compression and decompression of codes, efficient algorithms and codes, in parallel are presumably "more efficient"; you compress codes by solving a packing problem which is equivalent to a graph traversal which is a minimum span (of a spanning-tree you have to build).
  
  So compressing the cube-code i.e. the 3-face group FRD -> R' FD R' and its complements (there are six) means finding a more general representation for "faces". Also note that, rather than coding the four "side-face" moves that alternate in the g[sub]2[/sub] above, I can substitute a rotation of the cube itself, "following" the stack by inverting the pair of vertical faces.
  
  So then I can say that faces YX alternate, and face Z is "perpendicular to the U*D = UD* axis", and write Z|{XY,YX}|Z as a a more abstract form of g[sub]1[/sub]. Now I need a representation (symbol) for an outer rotation, that switches sides of the whole cube without moving any slices.
  
  Z,Z' and XY,YX (which are 2-s complements in the "2-faces" group metric), commute and anti-commute, to transport the stack (2,3,2) around the n-sphere. You start at n = 0, the 0-sphere.
• 

  skipper

  Correction: there are 4 places for the digits, r[sup]1[/sup]r[sup]2[/sup]r[sup]3[/sup]r[sup]4[/sup]. But the last digit = r[sup]0[/sup] = 1, the multiplicative identity; the additive identity is induced by r + r + ..., and -r + r = 0, so 0 is the identity of the additive, 1 of the multiplicative relation.
  
  Additively, r + r = r[sup]2[/sup], which implies a square root; they commute. r + r + r = r[sup]3[/sup] = -r, a cube root. These roots have an additive and a multiplicative index, which you are free to raise or lower; in fact that is equivalent to rotating faces and using the index to count rotations.
  
  Note that, if the above is arithmetically true, so that two successive rotations with a {++} metric, is mathematically and logically equivalent to a square (of an identity or an image of it) then the only numerical solution for 2r = r[sup]2[/sup], is r = 2. The "distance generator" must be a 2-dimensional number, this makes sense because it can have the following "metrics" {++}, {--}, {+-}, {-+}. The last two => 0, the first two => a root of the cube, in the same place p = r[sup]2[/sup].
  
  Ed: so where do the numbers 0 and 1, fit into the model? Zero is congruent with what happens to three of the cube's faces, as you rotate the whole thing. You can always see at least 1, at most 3 faces.
  In computational terms, the additive and multiplicative identities are "in" the layer moves or slice groups. Zero is "between" +r and -r somewhere, one of r or -r is completed when a certain fraction of Pi is reached (the circle divided in 4); however this will always be an approximate - not exact - physical correspondence. We ignore the small difference, but fundamentally the value "1" is not realizable, physically we are obliged to use approximate units and call them "ones".
• 

  skipper

  I could keep this up for a while; but I can recommend that interested parties use google and try terms like "rubik's group" and "prime order automorphisms". I mean, plenty of mathematicians with a much better grasp of the symbology than me, have written a lot of stuff.
  
  A question you eventually ask is: how come? Why do permutation puzzles relate to so many physical things?
  
  The answer might be connected to entropy, specifically entropy of information. If you "randomly" scramble a cube - say you use a non-deterministic kind of approach and try to generate a maximum number of different colors per face - you increase the information entropy.
  The more "disordered" the faces are, the more information is presented.
  
  However, the disorder is ordered - you actually can only generate a pseudo-random sequence, not a truly random one because all moves are constrained. Otherwise the path to randomness will mean disassembling a cube and randomly orienting the separate parts - a "gas phase" perhaps.
  
  
  Continuing with the notation (Singmaster), notice that the labeling orients the cube (but not the colors), so the (U,D,F,B,L,R) set is mapped to (X,X') (Y.Y') and (Z,Z') pairs of opposite faces. If the D face (with the U*D axis) is "fixed" as Z, and the sides alternate as above as XY or X'Y', then since the "Z-layer" moves twice, you can say the two other moves on 2 side-layers divide the "Z-function" which is Z[sup]2[/sup].
  
  So the FR or RF (plus the inverses F'R' and R'F') are divisors of Z[sup]2[/sup]. Each "function" is the same word-length and has the same geodesy, except the Z-moves are on the same face, so are parallelized by definition; the other generator (word) is orthogonal to X,Y (coordinates).
  
  As an indication of the mathematical nature of the cube groups, here is a page from Wikipedia which I would say is a kind of node, this one has lots of edges (links) at the bottom. The questions are: how many of the links correspond to the Rubik's puzzles (that is the set including all the Platonic forms which are both shallow and deep sliced solids)?
  Category:structures On Manifolds
  And: Parallelizable Manifold is related to the groups I have listed so far, because the Z-layer (mapped first to the R, then to the D face) is parallelized in the group actions.
  
  Then there is an entry on the Rubik's cube group specifically, the connections to coding theory (Mathieu groups), and some of the math:Rubik%27S Cube Group
  
  Whoops: P.S. Notes on dimensionality
  
  Dimension is most familiar to everyone as spatiality, of which there are three distinct dimensions for ordinary objects. But that's physical dimensionality - there is one more dimension that physical (objective) spatiality requires, which we call time. Time is "real" although we can't store or forward it physically; in fact we "imagine" that time is a degree of "freedom" for spatial objects to "be spatial" in.
  
  Anyways, there are other kinds of degrees of freedom. Topologically a system can have infinite d.o.f. and none need be physical, only mathematically consistent.
  For n, the number of "face-moves" which can be 1/4 or 1/2 or 3/4 = -1/4 of the "full circle" of moves (i.e. the QTM is a subset of the FTM) degree is directly related to "number of moves" in both metrics - a move like RR is a single face-move but two "inner" moves; face moves can have up to 3 for an index; inner "quartered moves" can only have 1 ~ the multiplicative Id. This implies a conjugate and conjugation is nice and Boolean.
• 

  skipper

  Here is where I would like to directly connect the algorithmic side of the puzzles in play, to digital computers that use Boolean variables, 2-s' complement arithmetic and signed extended numbers with strings of leading 1s; for instance complements are found in the structure group {+r, -r, pi} for p, a positive integer and index i, where i <= 4, the rotors r are complements of each other which have a direct 1-s' complement representation = {+1, -1}. Then there is the induced metric, as before:
  {++}, {--}, {+-}, {-+}. I can label these m[sub]a[/sub], m[sub]a'[/sub], m[sub]b[/sub], m[sub]b'[/sub]. I know that the b, b' indexed pair sum to zero, and the a, a' sum to an algebraic product (I can call this I, since if I = 1, then I[sup]2[/sup] = 1).
  
  I have some results from Cube Explorer that reveal something about the so-called 2-generator group, which is the group of rotations on two adjacent layers or faces; these faces commute to some extent and there is a commutative relation between the rotation group sequences and the "linear products" that get exchanged. Any word in the 2-face algebra is a subset of all possible words in the full 6-faces algebra. Cube Explorer compresses any word you type into the macro (algorithm) window, the trick is to find the correspondence between what you use in the input algorithm and what the output one is - this is supposedly the shortest equivalent sequence in the FTM that represents the original word.
  
  If you build up words with a 2-face code like FRFRF... and apply them, they have various cycle lengths; a cycle length is how many times the code word has to be "read" by the cube to return to the identity, so every program has a midpoint where the algorithm inflects and starts an involution, where the first part was an evolution - every place in the word has an inflected/reflected place because the shortest word has a midpoint and it's a point of symmetry for the commutator.
  
  More later...
• 

  skipper

  Symmetry:
  
  The mechanism of each individual face is a rotor r, which is 'sign-extended' because a conjugation (i.e. a number of places) of digits "r" up to infinity will always leave a face in 1 of 4 places. So each face is a symmetrical number, or a modulus (of the face-metric). A single digit and sign corresponds to a "trivial step" or rather, the group of elements containing the rotor, and the integers (Z) is the trivial (symmetry) group.
  
  This is obvious because for a face F, assuming the character is isomorphic to a linear transformation of a face (an endomorphism), then functorialized F followed by F' is a conjugate that leaves a face unchanged. This is the definition of a conjugated linear (unitary) transform, often notated U'U = UU'
  If you 'divide' U and its inverse, by injecting another functor (the cube's identity {e}) as a h = 1, then UhU' = h.
  
  What about the group containing r and the reals? You can move any face by a small amount < a "complete" fraction of the circle (the square face of a cube divides this into 4 geometrically) - i.e. a completion is a multiple of 1/4. Real rotations can take an infinite number of infinitisemal steps to complete. The reals are a subgroup but 'vanish' at the vertices.
• 

  skipper

  Questions:
  1) Why was the particular set of puzzles - corresponding to sliced and sectioned Platonic solids, the cube, the dodecahedron, the tetrahedron and the icosahedron - "invented" in the age of plastics rather than the age of metal and wood etc? Why didn't a DaVinci or even Babbage try to construct such a device? The answer might be the simple fact that plastics although "solid" remain flexible, the material can be deformed (it's how to take a 3x3x3 apart - see instructions in many guides to cube-modding, Youtube vids and forums).
  
  So is it possible to make such a device out of conventional (i.e. "classical") materials, such as wood or metal?
  
  2) Why does just the original puzzle (that kicked off something of a mathematical tour-de-force) have so many symmetry groups in it? There are maps from these groups to the other Platonic forms - you have all of them in just the 3x3x3 because the groups that act on corners are a quaternionc algebra, the edge-groups 'divide' the corner groups - this is a fundamental and obvious symmetry.
  
  3) What logarithmic bases apply and is there a logarithmic series (a word) that visits every node in the complete Cayley graph? Likewise how many nodes are isometries/isomorphisms? Is there a word that visits at least one of each distinct set so it counts how many sets?
  
  4) If you analyze the geometry of Platonic forms and use a logarithmic basis which is orthogonal to the golden ratio, can you map a given log base (say from 0 to 3) to the cube groups. Logarithms are symmetrical after all. As it happens a certain Greek engineer has done this, revisiting Plato's original motivation and, especially, a relation between what he calls a pair of "orthogonal triangles" that formulate the golden ratio's correspondence to the solid forms.
  
  5) Why are there only 5 regular solids, and why does this induce a finite # of alternates -the cuboctahedron, the n-polytopes with n restricted?