--- title: "Landmark States and the Solid They Span" output: rmarkdown::html_vignette vignette: > %\VignetteIndexEntry{Landmark States and the Solid They Span} %\VignetteEngine{knitr::rmarkdown} %\VignetteEncoding{UTF-8} --- ```{r, include = FALSE} knitr::opts_chunk$set(collapse = TRUE, comment = "#>") ``` A Cayley graph of TopSpin at `n = 20` has 20! vertices, so nothing about it can be measured by enumeration. This vignette describes an indirect route: pick a small set of states defined by rules rather than by chance, measure the distances between them, and read the geometry off that. The pipeline has four steps, each with its own pitfall. The pitfalls are the interesting part, so they are described alongside the results. ```{r setup} library(cayleyR) ``` ## 1. Landmark states `landmark_states(n)` returns 25 permutations of `1:n`, each built by a rule that generalises across `n` -- a full reversal, a riffle shuffle, the doubling map `2j mod (n+1)`, and so on. ```{r} lm <- landmark_states(20) head(lm[, c("id", "name", "state_str")], 5) ``` ### Rotations are free The first attempt at this set had a flaw that only shows up in the graph, not in the permutations. Consider `reverse_first` and an early version of `derangement`: ``` reverse_first: 10 9 8 7 6 5 4 3 2 1 | 11 12 ... 20 derangement: 11 12 ... 20 | 10 9 8 7 6 5 4 3 2 1 ``` As permutations these are different: one has eight fixed points, the other none. But they are the same sequence cut at a different place, and cutting the ring at a different place is exactly what `L` does. The two states sat 7 moves apart at `n = 14`, against a mean of 133 -- effectively one point, not two. Three constructions were affected (`block_swap`, `block_rotate3`, `shift_third` were mutual rotations; so were `reverse_first` and `derangement`). Fixing them one at a time did not work: each hand-tuned formula collided with something else. `landmark_states()` now detects the collisions instead. It reduces every state to a canonical form -- the lexicographic minimum over all `n` rotations -- and breaks any tie by transposing one adjacent pair in the later construction, repeating until all 25 canonical forms differ. Verified for every `n` from 6 to 20. The cost is that a state may differ by one transposition from its stated formula. That is the price of having 25 genuinely distinct points. ## 2. Distances The distance between two landmarks is the length of a path between them, found with the human solver and then compressed: ```{r, eval = FALSE} p <- human_algorithm_to(from, to, k = 4) p <- short_path_bfs(p$path, from, k = 4, depth = 5)$path ``` ### Why not `human_algorithm()` `human_algorithm(from, final_state = to)` reaches an arbitrary target by solving *both* endpoints down to `1:n` and splicing the first word with the inverse of the second. Every route therefore detours through the identity. Measured on the path from `envelope` to `riffle` at `n = 20`, the walk reaches a state with 11 of 20 tiles already home -- it passes right by the solved state on its way. Drawn, that puts every arc through one point and the picture collapses into a star. `human_algorithm_to()` relabels the problem instead (renaming each value to its position in the target turns "reach `to`" into "reach `1:n`") and goes direct. At `n = 20` the paths came out roughly three times shorter: | pair | via identity | direct | |------|-------------:|-------:| | `two_cycles` -- `full_reverse` | 441 | 141 | | `envelope` -- `riffle` | 329 | 146 | Switching solvers changed the whole distance matrix -- median 238.5 to 158 -- which in turn changed which pairs are far apart. Any selection made before the switch had to be redone. ## 3. Picking six pairs With 25 landmarks there are 300 pairs. To find six pairs that are far apart *and* use twelve distinct landmarks, taking the six longest rows of the matrix does not work: the two extreme points of the graph appear in nearly every long pair, so a greedy pick exhausts them immediately. Maximising the total of six disjoint distances spreads the endpoints out instead. The script does that with a local search -- swap partners between pairs, substitute unused landmarks, restart from many random matchings. At `n = 20`, with the corrected landmark set: | pair | distance | |------|---------:| | `alt_pairs` -- `full_reverse` | 269 | | `reverse_first` -- `pair_shift` | 240 | | `cycles3` -- `block_reverse_pairs` | 188 | | `block_rotate3` -- `zigzag` | 181 | | `spiral` -- `adjacent_swaps` | 159 | | `reverse_second` -- `two_cycles` | 81 | At `n = 50` the same twelve landmarks give 1213 to 1975, except `reverse_second` -- `two_cycles` at 643, which stays short at both sizes. The pairs stored in the example script were found before the landmark fix of section 1 and are kept as literals for reproducibility; re-run with `SELECT = "pairs"` to search again on the current set. ## 4. Where a landmark sits Celestial coordinates map the `(nL, nR, nX)` move counts of a route to `(theta, phi, omega)`. They describe the **route**, not the state -- which means a state has no position until you say how you got there. Drawing six arcs, each accumulating counts from zero, therefore put all six starting points at the origin no matter which landmarks they joined. The fix is to solve the identity-to-landmark path first and use its counters as the landmark's absolute position; the arcs then continue from there. Those paths are measured but never drawn. ```{r} lm20 <- landmark_states(20) i <- match("block_reverse_pairs", lm20$name) p <- human_algorithm_to(seq_len(20), lm20$state[[i]], k = 4) ops <- c("1" = "L", "2" = "R", "3" = "X")[p$path] table(ops) ``` The counters differ sharply between landmarks -- at `n = 20`, `block_reverse_pairs` sits at `L=63 R=125 X=58` while `two_cycles` is at `L=34 R=16 X=29` -- which is what separates the arcs in space. A caveat worth stating plainly: the position depends on the route the solver happened to take, and that route is not guaranteed shortest. These coordinates describe a particular set of walks, not an invariant of the graph. ## 5. The solid Twelve points in space bound a figure. Note that a solid with twelve *vertices* is an icosahedron; a dodecahedron has twelve *faces* and twenty vertices. Our points are neither -- they are an arbitrary cloud, so the figure is a hull. `convex_hull_3d()` gives the smallest convex body containing them. But convexity means some points end up strictly inside and are not corners: at both `n = 20` and `n = 50`, eleven of the twelve landmarks are vertices and one is swallowed. `enclosing_hull_3d()` starts from that convex hull and, for each interior point, replaces the nearest face with three triangles meeting at the point. The surface dents inwards, the body stops being convex, and every landmark becomes a corner. ```{r} cube <- as.matrix(expand.grid(c(0, 1), c(0, 1), c(0, 1))) convex_hull_3d(cube)[c("area", "volume")] # the same cube with a point at its centre withcentre <- rbind(cube, c(0.5, 0.5, 0.5)) h <- enclosing_hull_3d(withcentre) c(vertices = length(h$vertices), area = h$area, volume = h$volume) ``` The dent costs volume and adds area, exactly as it should. ### Results | | `n = 20` convex | `n = 20` enclosing | `n = 50` convex | `n = 50` enclosing | |---|---:|---:|---:|---:| | vertices | 11 of 12 | 12 of 12 | 11 of 12 | 12 of 12 | | faces | 18 | 20 | 18 | 20 | | surface area | 5 950.57 | 5 956.42 | 530 374.12 | 531 911.41 | | volume | 14 173.83 | 14 165.50 | 6 141 465.83 | 5 928 340.50 | The point left inside is `adjacent_swaps` at `n = 20` and `spiral` at `n = 50`. Both hull functions are implemented in the package rather than taken from `geometry`, keeping the dependency list at Rcpp alone. They are checked against solids with known values -- a cube, a box, a tetrahedron, and a regular icosahedron -- and agree to six decimal places. ## What this does and does not establish The volume grows by a factor of roughly 420 between `n = 20` and `n = 50` while the mean pair distance grows by about a factor of 8. That is a statement about these twelve routes under this solver, and reading a graph diameter off it would require the routes to be shortest, which they are not. What the construction does give is a reproducible probe: fixed states, a fixed solver, and a figure whose size can be compared across `n` or across changes to the solver. If a shortening pass improves, the paths get shorter and the solid shrinks -- and that comparison is meaningful even when the absolute numbers are not. ## Running it ```{r, eval = FALSE} # the network between landmarks, and the solid they span source(system.file("examples", "demo_landmark_network.R", package = "cayleyR")) # the star of paths from the identity out to each landmark source(system.file("examples", "demo_landmark_paths.R", package = "cayleyR")) ``` Both scripts carry their parameters in a block at the top: `N`, the layout (`celestial`, `spectral`, `diffusion`), whether to draw the hull or the arcs, and how the landmarks are selected.