WPP 2022 project proposal #
"Symmetry breaking" in string rewriting systems #
Motivation #
This project studies the classic "string sorting" rewrite system, but from an explicitly group-theoretic angle. It makes use of some recent progress I've made in quiver geometry establishing the connections between quivers and group actions. It should be relatively simple to complete, but will involve working with discrete versions of principle G-bundles, frame bundles, and related machinery.
The main thrust is to use linear and circular string rewriting systems as a toy model for understanding the "partial actions of groups", where some nice potential symmetry is broken by whatever local details of a rewriting system (e.g. the edge of a string, or a character that "blocks" some particular rewriting from happening). It also involves doing some simple although technical work with discrete versions of various ideas from gauge theory -- definitely useful practice to have on discrete rewriting systems.
The title is a little joke -- not meant to be a direct connection with physics, of course. Although who knows in the end?
Linear string rewriting #
The multiway graph of a rewriting system \( \rewritingSystem{R} \) on initial condition \( \globalStateSymbol{s_0} \) has a natural cardinal structure, making it a cardinal quiver which we'll call the multiway quiver, written \( \quiver{M} = \multiwayBFS{\rewritingSystem{R},\globalStateSymbol{s_0}} \).
For example, the string rewriting system \( \rewritingSystem{R_0}\defEqualSymbol \rewritingRuleBinding{\stringRewritingSystem{}}{\rewritingRule{\lstr{\texttt{■□}}}{\lstr{\texttt{□■}}}} \) has the following multiway quiver for initial condition \( \qstring{\lstr{\texttt{■■■□□□}}} \), which we'll call \( \quiver{M_6} \):
The cardinals of \( \quiver{M_6} \) are determined by which sets of local states (sets of "tokens") are rewritten. This system has no purely spatial symmetries -- a consequence of the fact that the string is of finite length, which introduces "edge effects" that a group cannot model.
Symmetries and automorphism groups #
Linear string rewriting systems have few symmetries to exploit. Why is this?
First, let's say what we even mean by symmetry. The symmetry group of a particular global state is defined to be the stabilizer subgroup of some group of transformations that act on the set of all global states -- people usually call this "the" automorphism group of the relevant kind of object (set, vector space, group, etc.). But we need to decide exactly what the automorphism group should be for states of a rewriting system. Because we are dealing with discrete objects with finite information, the transformations must be information preserving -- otherwise unique inverses cannot exist. In other words, these transformations must permute the set of global states.
Moreover, these transformations should respect locality in some appropriate sense: we do not wish to arbitrarily permute letters in a string, for example. This can be defined quite easily in terms of path homomorphisms.
We define a global state as a section of a (trivial) quiver fiber bundle with base space being a line quiver (for a linear string) or a cycle quiver (for a cyclic string), and the fiber quiver being a complete quiver on the alphabet of the string: call this the configuration quiver. We show the configuration quiver for a length-4 linear string on two characters below:
Here we highlight the global section for global state \( \qstring{\lstr{\texttt{■■□□}}} \):
We then ask that a candidate transformation be a path automorphism of the configuration quiver. This ensures that e.g. neighboring characters are sent to neighboring characters. But it also allows arbitrary global permutations of the characters of the string, as well -- useful if there is some symmetry of the dynamics that can be expressed as a combination of modification of position and character value. This is indeed the case for the string quiver: there are symmetries of the dynamics involving left-right string reversal, time reversal, and \( \transposition{■}{□} \) exchange.
Note that the action of the symmetric group on the fibers makes this into a discrete principle G-bundle -- a claim that can be made precise with suitable definitions that I won't go into here.
Nevertheless, the requirement of that the automorphism group is defined on all states is extremely limiting. There are only two such global transformations: for a linear string, we have only left-right reversal, and \( \transposition{■}{□} \) exchange -- so our group is just the Klein-four group.
But we can obtain a much richer automorphism group by considering circular strings.
Circular string rewriting #
Let's now examine the equivalent circular string rewriting system \( \rewritingSystem{R^ \circ }\defEqualSymbol \rewritingRuleBinding{\circularStringRewritingSystem{}}{\rewritingRule{\lstr{\texttt{■□}}}{\lstr{\texttt{□■}}}} \). This system has global states that are circular strings, with origin. In other words, the cyclic strings \( \qstring{\lstr{\texttt{■■□□}}} \) and \( \qstring{\lstr{\texttt{□■■□}}} \) are formally distinct. The only difference with an ordinary string rewriting system is that rewrites are allowed to "straddle" the ends of the string.
Here is the multiway quiver \( \quiver{M_4^ \circ } = \multiwayBFS{\rewritingSystem{R^ \circ },\qstring{\lstr{\texttt{■■□□}}}} \):
Notice the multiway quiver becomes directed-cyclic, since the rewriting system can now return to previously visited global states.
Here is the multiway quiver \( \quiver{M_6^ \circ } = \multiwayBFS{\rewritingSystem{R^ \circ },\qstring{\lstr{\texttt{■■■□□□}}}} \) -- we don’t label the vertices to avoid clutter:
Relationship to linear string systems #
Notice that if we delete the edges labeled by \( \orFo{\card{c_6}} = \rewrite{\regionalStateForm{\localState{6}{\lchar{\texttt{■}}} \localState{1}{\lchar{\texttt{□}}}}}{\regionalStateForm{\localState{6}{\lchar{\texttt{□}}} \localState{1}{\lchar{\texttt{■}}}}} \) from \( \quiver{M_6^ \circ } \), we obtain \( \quiver{M_6} \), the multiway quiver for the analogous linear string system (which uses the same initial condition). Therefore the we have that \( \quiver{M_6} \) embeds into \( \quiver{M_6^ \circ } \).
Rotations #
By moving to cyclic strings, we obtain an additional generator of the automorphism group: cyclic rotations of strings.
For \( \rewritingSystem{R^ \circ } \) acting on an initial string of length \( \sym{n} \), the group of cyclic rotations is isomorphic to \( \cyclicGroup{\sym{n}} \) . We can depict this action by augmenting the multiway quiver, inserting additional cardinal edges that show the action of a generator of \( \cyclicGroup{\sym{n}} \) -- e.g. the generator that rotates the string one character to the right:
The proper thing here would be to add additional cardinals for every generator of the entire automorphism group. Anyway, this object is again a bundle -- though with some subtleties about continuity here that will need investigation -- and we can already see that the isotropy groups (the symmetry groups) of particular states are sub-quivers living above specific vertices in the fiber (in which we follow only cardinals from the automorphism group). More complex dynamical symmetries should be sub-quivers that allow us to use rewrite cardinals and automatorphism cardinals.
One important thing: the action of the automorphism group is not free: we can see orbits of length 2 and 4 in the above quiver, so it may well be that we will need to move to orbifold theory to understand this better -- in particular orbihedrons appear like the right tool for the job (suitably adapted to quiver geometry). Alternatively we might be able to solve this by simply quotienting by this generator -- the cycle space would then be a non-based rewriting system in which rotated global states are identified. Anyway, plenty to investigate!
Path relations #
It should be fairly trivial to embody symmetries of the dynamics as path relations in the augmented rewrite quiver we see above. This has the intriguing prospect that we can potentially set up "reference frames" (meaning alternative cardinal structures) that allow us to merge space-translated rewrites into a single rewrite by exploiting the rotation cardinal.
Symmetry-breaking #
Once we understand the circular string rewriting system, we should have a way of porting this understanding back to the linear rewriting system. An attractive idea to explore whether these sub-quivers of the full multiway quiver -- which look like fragments of the multiway quivers of more symmetric rewriting systems -- offer a potential route to measuring curvature that comes from these edge effects. These little pockets of nice behavior would serve as charts, and the usual holonomy story could get us to definitions of curvature, although a better way of phrasing this is in terms of cohomology of a complex of groups that encode path relations on combinations of charts -- orbihedra already exploit this idea in the setting of geometric group theory via Tits buildings.
Project goal #
The aim here was to give a flavor of what the project could entail -- there's definitely much I discovered just writing this up, and it's clear it will be interesting no matter where it goes. But a good metric of success will be to have a fairly complete and satisfing workflow for how to analyze symmetries of a particular rewriting system using discretized versions of some of the familiar tools from physics. I imagine at least some of these discrete things have been done before in various contexts, and that that bibliography will be nice to collect as well.