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.
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.
lm <- landmark_states(20)
head(lm[, c("id", "name", "state_str")], 5)
#> id name state_str
#> 1 1 full_reverse 20_19_18_17_16_15_14_13_12_11_10_9_8_7_6_5_4_3_2_1
#> 2 2 block_swap 11_12_13_14_15_16_17_18_19_20_1_2_3_4_5_6_7_8_9_10
#> 3 3 riffle 1_11_2_12_3_13_4_14_5_15_6_16_7_17_8_18_9_19_10_20
#> 4 4 envelope 20_1_19_2_18_3_17_4_16_5_15_6_14_7_13_8_12_9_11_10
#> 5 5 adjacent_swaps 2_1_4_3_6_5_8_7_10_9_12_11_14_13_16_15_18_17_20_19The 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 1As 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.
The distance between two landmarks is the length of a path between them, found with the human solver and then compressed:
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.
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.
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.
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)
#> ops
#> L R X
#> 63 125 58The 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.
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.
cube <- as.matrix(expand.grid(c(0, 1), c(0, 1), c(0, 1)))
convex_hull_3d(cube)[c("area", "volume")]
#> $area
#> [1] 6
#>
#> $volume
#> [1] 1
# 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)
#> vertices area volume
#> 9.0000000 6.5606602 0.9166667The dent costs volume and adds area, exactly as it should.
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.
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.
# 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.