Group Actions and Invariants: What stays the same under transformation

A7Prose proofThe Erlangen Programme applied to verification: identity through invariance.

Geometry is the study of those properties of figures which remain invariant under a group of transformations.
— Felix Klein, Erlanger Programm (1872)

This chapter formalizes the Erlangen insight for systems architecture: a property is real if and only if it survives all admissible transformations, and everything else is a coordinate artifact. The central definition is A7 (Group Action and Invariant), which makes precise the notions of transformation regime, orbit, and invariant function. The chapter develops the connection between declared transformation groups and the equivalence classes they induce, providing the foundation on which the subsequent definitions of isomorphism (A8), adjunction (A9), and witnessed sameness (A10) will build. The historical and philosophical motivation for this formalization -- including the role of the Erlangen Programme in unifying nineteenth-century geometry -- is developed in Vol I, Chapter 4 (Empire of Strings); the formal treatment here is self-contained.

The Representation Problem

Representation is arbitrary; identity is not. Two systems can encode the same fact in formats that look nothing alike—JSON versus XML, camelCase versus snake_case, ISO dates versus Unix timestamps—and yet mean the same thing. The question is what "same" means, and how you would know.

Team A sends data as JSON with camelCase keys:

{ "userId": 42, "createdAt": "2024-01-15" }

Team B sends data as XML with snake_case tags:

<user_id>42</user_id>
<created_at>2024-01-15</created_at>

The payloads carry identical information. A diff tool reports them as completely different.

Which tool is right? The answer depends on what you're measuring. If you're comparing byte sequences, they differ. If you're comparing information content, they match. The question is not "are they equal?" The question is "equal under what operations?"

Suppose both teams agree on a round-trip specification: any JSON payload can be converted to XML and back, losslessly, using a defined mapping. Under that agreement, the two representations become equivalent for that purpose, because any operation that treats them differently is violating the contract. The diff tool, measuring bytes, is using a stricter standard than the contract requires.

Define a transformation regime as the set of operations treated as admissible for a given purpose. When every operation in the regime has an inverse, the regime is a group. The group case comes first because the equivalence-class geometry is sharpest there; subsequent sections treat the non-invertible case.

This distinction is operational. A system that treats the payloads as different will reject valid integrations. A system that treats them as the same, without a defined mapping, will accept invalid ones. The question "are they equal?" has no answer until you specify the transformations under which equality must hold.

Not all mappings are reversible. Converting userID to user_id and back might yield userid, because the original casing encoded information (an acronym) that snake_case destroyed. If the round-trip fails, then "same under transformation" is ill-posed under that regime—you have information loss, and the seam becomes political, not mathematical. The lesson: equivalence presupposes a declared transformation regime. Canonicalization is one way to enforce it; without enforcement, "same" is a wish, not a fact.

Here is a puzzle. A retail company has two supplier feeds. Feed A reports inventory in metric units; Feed B reports in imperial. A sweater weighs "500 grams" in Feed A and "1.10 pounds" in Feed B. The number 500 does not equal the number 1.10. Are these the same sweater?

A common answer is to convert: 500 grams equals approximately 1.10 pounds. Under unit conversion, they match. But that answer hides two assumptions: that unit conversion is a permitted transformation, and that rounding tolerance is part of the declared regime. If the downstream system treats "grams" and "pounds" as opaque labels (perhaps because legal compliance requires preserving the original units), then conversion is forbidden, and the sweaters are different items.

Neither answer is "correct" in isolation. The question cannot be answered until you state the rules of the game. Which transformations are allowed? The answer to "are they equal?" follows from that prior choice.

The question "which properties are real, and which are artifacts of representation?" is not new. One clean version of the answer was articulated in 1872.

The Erlangen Programme

By 1870, geometry was fragmenting. Euclidean geometry, the stable inheritance of two millennia, had been joined by a proliferation of alternatives. Lobachevsky and Bolyai had constructed hyperbolic geometry, where parallel lines diverge. Riemann had proposed geometries of variable curvature. Projective geometry, developed by Poncelet and others, treated points at infinity as ordinary citizens. Each geometry had its own axioms, its own theorems, its own sense of which questions were meaningful.

The fragmentation was productive but destabilizing. If Euclidean geometry was not the only geometry, what made it a geometry at all? What unified the field?

Felix Klein, a twenty-three-year-old professor at Erlangen, proposed an answer. His 1872 inaugural address, later known as the Erlangen Programme, reframed the question—do not ask what objects a geometry studies; ask what transformations it permits. The objects follow from the transformations, not the reverse. (Klein 1872)

Consider Euclidean geometry. The permitted transformations are the rigid motions: rotations, translations, reflections. These preserve length and angle. Any property that survives all rigid motions is a Euclidean invariant. Length is one. Angle is another. Position is not—a triangle at the origin and the same triangle shifted two units east are the same triangle, Euclideanly speaking, because a translation connects them.

Affine geometry permits a larger group of transformations: the linear maps, including shearing and non-uniform scaling. These preserve parallelism and ratios of lengths along a line, but not length itself. Under affine geometry, a circle and an ellipse are the same figure, because a scaling transformation connects them.

Projective geometry permits projections, including those that send parallel lines to intersecting ones. Under projection, parallelism vanishes. But the cross-ratio of four collinear points survives.

The geometries nest. Every rigid motion is an affine transformation (just one that happens to preserve length). Every affine transformation is a projective transformation (just one that happens to preserve parallelism). Euclidean geometry is contained within affine geometry, which is contained within projective geometry. The containment is strict: each larger group destroys some invariants that the smaller group preserved.

This nesting reveals a tradeoff. The more transformations you permit, the fewer invariants you retain. Permit only rigid motions, and you keep length; permit all projections, and you lose it. A conservative choice of transformation group preserves more structure. A liberal choice identifies more representations as equivalent.

This is not a defect of the framework. It is the framework's central insight. The transformation group is not discovered; it is chosen. The invariants are determined by that choice. Klein did not say which geometry is "correct." He said: once you specify the allowed transformations, the invariants follow. The geometry is defined by the group, not the reverse.

Klein's organizing principle can now be stated: fix the admissible transformations, and the invariants are what your geometry is about. Each geometry is defined by a group of transformations, and its theorems are statements about the invariants of that group. (Klein 1872)

This is not antiquarian interest. The fragmentation of geometries in the 1860s mirrors the fragmentation of data regimes today: many local coherences, no organizing principle. Klein's move was not to unify by fiat, declaring one geometry correct. He unified by classification: each regime is characterized by its permitted operations, and the invariants follow. The proliferation was not confusion; it was abundance without a principle of comparison.

Systems architecture faces the same disease. JSON, XML, Protobuf—these are not competing geometries, but they are competing representation regimes, and the question "when are two payloads the same?" admits no answer until you specify the permitted transformations. Klein's insight, translated: real properties are invariants under the declared regime; everything else is coordinate artifact.

A systems-native restatement: two pretty-printers emit different text from the same AST. Under the regime "operations that preserve parse result," the outputs are equivalent. The invariant is the tree; the string is representation; the whitespace is coordinate. To ask "are they the same?" without specifying the admissible transformations is to ask a question that has no answer.

The chapter's thesis can be stated now, before the formalism: pick the admissible transformations first; reality is what survives them.

Group Action and Invariant

What does it mean for a property to "survive" a transformation? The intuition is simple: the property doesn't change. Apply any permitted operation, and the property remains the same. The formalization is equally simple, and it has a name.

Before stating the definition, consider why precision matters here. The Erlangen insight is useless if "invariant" is vague. We need a criterion that is well-defined given a specified action, that matches our intuition in clear cases, and that admits sharp reasoning. The definition that follows delivers this; whether invariance is decidable depends on how the action and the property are represented, but the definition itself is crisp.

A transformation is any operation we declare semantics-preserving for a given purpose. Renaming a variable. Reformatting a date. Converting between encodings. These are transformations. A transformation is not any function; it is a function that we designate as admissible because it preserves what we care about.

A group is a collection of transformations with two properties. First, transformations can be composed: do one, then another, and the result is also in the collection. Second, transformations can be inverted: for every operation, there is an undo. The rigid motions of the plane form a group. Rotate ninety degrees, then rotate ninety degrees again: you get a one-eighty rotation, still a rigid motion. Rotate ninety degrees, then undo: you're back where you started.

An invariant is a property that doesn't change under any transformation in the group. Length is invariant under rigid motions. The content of a file (as measured by its hash) is invariant under renaming or moving.

Group Action and Invariant (A7)

Let $G$ be a group and $X$ a set. A group action of $G$ on $X$ is a function $\cdot : G \times X \to X$ satisfying:

Identity: $e \cdot x = x$ for all $x \in X$ , where $e$ is the identity element of $G$
Compatibility: $(gh) \cdot x = g \cdot (h \cdot x)$ for all $g, h \in G$ and $x \in X$

The orbit of $x \in X$ under $G$ is the set of all points reachable from $x$ by some transformation:

G \cdot x = \{ g \cdot x : g \in G \}

A function $f : X \to Y$ is $G$ -invariant if:

f(g \cdot x) = f(x) \quad \text{for all } g \in G, x \in X

Equivalently: $f$ is constant on orbits.

The orbit is the equivalence class of all representations connected by permitted transformations. The invariant is the property that assigns the same value to every member of the class. Two representations are equivalent if and only if they lie in the same orbit. A property is real if and only if it is constant across orbits.

This equivalence-class structure depends on having inverses. In the group case, orbits are honest equivalence classes: if you can get from A to B, you can get back. In weaker regimes (monoids, categories), you get reachability rather than equivalence, and recovering the right notion of sameness requires adding structure. We'll return to this when witnesses appear.

There is a cleaner way to say this. Let $\pi : X \to X/G$ be the orbit map, sending each point to its equivalence class. Then $f$ is $G$ -invariant if and only if $f$ factors through $\pi$ : there exists some $\bar{f} : X/G \to Y$ such that $f = \bar{f} \circ \pi$ . The invariant "sees" only the orbit, not the particular representative. If two systems disagree on orbits, they disagree on what a claim even means.

This factoring criterion gives us three things. First, a crisp definition of coordinate artifact: anything that varies within an orbit. Second, a bridge to later chapters, where quotienting and transport become central. Third, a systems interpretation: canonicalization is choosing a representative of an orbit. When a system normalizes data to a canonical form, it is selecting one point from each equivalence class. The choice of representative is arbitrary; the orbit structure is not.

Computer science already lives on these concepts, even when it does not use this vocabulary.

In lambda calculus, the functions $\lambda x.x$ and $\lambda y.y$ are the same function. They differ only in the choice of variable name, and variable names are coordinates. The semantic identity is invariant under renaming. This is alpha-equivalence, and it is a worked example of the Erlangen move: the transformation group is variable renaming, and the invariant is the function itself. (Pierce 2002, Ch. 5)

Compiler optimization provides another example. A compiler transforms source code into machine code, and along the way it performs many intermediate transformations: inlining functions, reordering instructions, eliminating dead code. Each transformation changes the representation. The invariant is observational equivalence—any program that interacts with the compiled code through its public interface cannot tell that the transformation occurred. The permitted transformations are exactly those that preserve observable behavior. The internal structure is a coordinate; the external contract is the invariant.

This is Klein's principle, stated in the language of compilers. The compiler declares a transformation group (semantics-preserving rewrites), and the invariant is what the spec guarantees (observable behavior). Every correctness proof for a compiler optimization is, implicitly, a proof that the transformation respects the declared group.

Many real system transformations are not invertible: column drops, field coalescing, lossy compression, one-way hashes. These do not form groups, because there is no undo. They live in monoids (where composition exists but inverses do not) or, more generally, categories. We began with groups because the equivalence-class geometry is sharpest there; the generalization follows. The honest structure for "invertible where defined" is a groupoid, where transformations have inverses but need not be globally defined. We will need this later.

Invariants as Contracts

In systems, we do not discover transformation regimes. We declare them. The declaration is a contract: "these operations are permitted; these properties must survive them." The invariants follow from the contract.

Consider content-addressed storage.(Torvalds 2005) The admissible transformations are those that may change location, name, or storage medium while preserving bytes. Under this contract, the content hash is the only invariant. File path is not: you can move or rename a file without changing its hash. Timestamp is not: you can touch a file without changing its content. Permissions are not. The system declares what matters (content) by specifying which operations are admissible.

Consider semantic versioning.(Preston-Werner 2013) Within a minor version, certain changes are declared admissible: adding optional fields, extending enumerations, deprecating (but not removing) endpoints. The invariant is the external contract: existing API calls continue to work. Internal implementation details are not invariant; they may change freely. The semver spec declares a compatibility regime, and the invariants are what the regime guarantees.

But "backward compatible" is not a group. You can add a field; you cannot un-add it (without a breaking change). The transformations are not invertible. What semver declares is not a group but an admissible class of changes, and the invariant is what we require to survive, even if the changes themselves are one-way. The Erlangen framing still applies, but the mathematical structure is weaker. This is not a defect; it is precision. We are careful about what structure we have and what structure we lack.

The choice of $G$ is a design decision, not given by nature; the invariants follow from that choice. Choosing $G$ is choosing what counts as "the same."

In practice, $G$ is a mix of declared and emergent. The spec declares one set of permitted transformations. The teams, through accumulated practice, treat a different set as semantics-preserving. Drift between declared and emergent $G$ is a recipe for integration failures. A downstream consumer builds against the declared contract. An upstream producer treats an undeclared transformation as safe. The seam breaks.

Consider a real failure mode. A payments service specifies that transaction amounts are integers representing cents. The declared regime includes unit conversions within the cent denomination. One day, a partner submits amounts as floats with decimal points: 10.50 instead of 1050. The partner assumed that formatting was a coordinate. The service assumed it was an invariant. The transformation "change from float to int representation" was not in the declared $G$ , but the partner treated it as permitted.

The result: silent data corruption, or rejection of valid transactions, depending on how the service handled the mismatch. The root cause was not a bug in the code—it was a mismatch between the declared regime and the assumed one.

Another failure mode, more insidious: an address-normalization pipeline "fixes" customer addresses by standardizing abbreviations and correcting ZIP codes. The normalized addresses work perfectly for delivery. But downstream, a compliance system uses the original addresses for identity verification, and the normalization has silently altered records that must remain byte-identical for regulatory purposes. The pipeline treated normalization as admissible. The compliance system treated it as forbidden. Both were right, under their declared regimes. The seam failed because nobody declared the boundary.

This failure mode recurs whenever we discuss schema evolution. The lesson: $G$ must be explicit. When it is implicit, every integration becomes a negotiation about which transformations are safe. That negotiation happens at runtime, in production, with customer data.

Running Examples

Return to the fashion catalog. Two suppliers describe the same dress:

Supplier A: { "color": "navy", "size": "M" }
Supplier B: { "colour": "dark blue", "size": "medium" }

Are these the same item? The question has no answer without a declared regime.

If $G$ is exact string match, they differ. "color" ≠ "colour", "navy" ≠ "dark blue", "M" ≠ "medium".

If $G$ includes spelling normalization (British/American), color-synonym resolution (within a defined color space), and size-code mapping (by convention), they may be the same. The orbit of this dress under the richer $G$ is the equivalence class containing { "color": "navy", ... }, { "colour": "dark blue", ... }, { "color": "#000080", ... }, and every other representation connected by permitted transformations.

The invariants under this richer $G$ are the underlying color (navy ≈ dark blue, within tolerance) and underlying size (M = medium, by convention). The non-invariants are spelling, exact color string, and size-code format. A system that tests for exact string match is testing a coordinate. A system that tests for orbit membership is testing the invariant.

The payoff: the platform cannot aggregate across suppliers until it declares a regime. The declaration is not optional. Without it, "same dress" is undefined.

Notice the asymmetry. The platform, not the suppliers, must declare the regime. Supplier A has no reason to care whether "navy" equals "dark blue." Supplier A knows what it sells; its internal consistency is not in question. The question arises only at the seam, where two systems must agree on equivalence. The seam is where the regime must be explicit.

This reveals a design principle. Integration points require transformation-group declarations. Internal components may leave $G$ implicit (they "just know" what they mean). Boundaries cannot. The boundary is where "same" must become a defined term.

The fashion example also reveals how small the tolerance window can be. "Navy" might map to hex code #000080. "Dark blue" might map to #00008B. These are eleven units apart on an 8-bit color scale. Is that within tolerance? The answer depends on the color-matching contract. If the contract says "equivalent within ΔE < 5 in LAB color space," then the system can compute the answer. If the contract says "exact hex match," they differ. The mathematics is simple; the design choice is not.

Turn to the build system. A build artifact is represented three ways:

File path: /build/output/app-1.2.3.jar
Content hash: sha256:a1b2c3...
Merkle node: node-xyz in the dependency graph

The orbit under content-addressed transformations includes all file-system representations that share the same content hash: the original location, a copy on another machine, a cached version with a different name.

Which representation should the build system track? The file path is not invariant under moves, renames, or replications. The content hash is. A system that tracks paths is tracking a coordinate. A system that tracks hashes is tracking an invariant.

This distinction has operational consequences. If the build system tracks file paths, then moving an artifact to a new directory invalidates caches. If the build system tracks content hashes, the move is invisible: the cache remains valid because the invariant (content) has not changed. Content-addressed storage systems like Git(Torvalds 2005) and many build caches are built on this principle. The hash is the identity—everything else is a pointer.

Canonicalization, in this light, is choosing a representative of the orbit. The build system might store artifacts by hash (invariant) and provide path aliases (coordinates) for convenience. The alias is a human-readable handle; the hash is the machine-verifiable identity.

There is a deeper payoff. When two build systems agree on the admissible transformations (content-addressed hashing), they can share caches without trusting each other's paths. Machine A and Machine B compute the same artifact independently. If the hashes match, the outputs are equivalent, by definition of the declared regime. Neither machine needs to know where the other stored the file or what it named it. The hash is a cheap, decidable certificate of equivalence in this special case. What "certificate" must mean in general is the subject of the next chapter.

This is the Erlangen move applied to distributed systems: declare the regime (content-preserving operations), identify the invariant (hash), and use the invariant as the coordination primitive. The rest is bookkeeping.

Touchstones Revisited

Two of the recurring touchstone cases gain precision under the Erlangen lens.

Contextual Equivalence. "NYC" and "New York City" appeared earlier as strings that are sometimes equivalent, sometimes not. The Erlangen reframing: equivalence is not a property of strings. It is a property of strings under a declared regime. Under postal normalization, both map to the same delivery zone; they are equivalent. Under legal jurisdiction, NYC denotes the five boroughs, while "New York City" might include a larger metro area; they differ. The strings have not changed. The regime has.

This is the resolution: there is no fact of the matter about whether "NYC" equals "New York City" until you specify $G$ . The seeming paradox dissolves once you stop asking "are they equal?" and start asking "equal under what?"

The practical implication: any system that ingests addresses from multiple sources must declare a regime. USPS normalization is one choice. It defines the orbits (all addresses that deliver to the same mailbox) and the invariant (deliverability). Legal jurisdiction is another choice. It defines different orbits (municipal boundaries) and a different invariant (which laws apply). A system cannot claim to "resolve" the equivalence of NYC and New York City without first choosing a $G$ . The choice is not arbitrary; it depends on what the system is trying to do. But the choice must be made.

Schema Evolution. A database schema evolves: employees becomes workers, fields are added or removed, types are widened or narrowed. The question "is this schema compatible with the old one?" has no answer until you declare which transformations are permitted and which invariants must be preserved.

Schema evolution is governable only after you specify $G$ . Without specification, "same schema" is undefined, and compatibility becomes an implicit negotiation rather than a technical determination.

Consider a concrete case. A schema has a field status with values active and inactive. A new version adds a third value, pending. Is this a compatible change? Under one regime (consumers may see any subset of allowed values), yes: the new version is strictly richer. Under another regime (consumers may switch on all values exhaustively), no: the new version breaks existing switch statements.

The question "is adding pending safe?" has no answer until you declare which transformations downstream systems are permitted to make. If they may ignore unknown values, the evolution is safe. If they must handle all values, it is not. The Erlangen framing converts a vague question ("is this compatible?") into a precise one ("what transformations are permitted, and what must survive them?").

The machinery to make "safe evolution" fully precise comes later; it requires the concept of conservative extension. For now, the point is simpler: the question is answerable, once you declare the rules.

Consequence

We now have vocabulary. A transformation regime declares which operations are permitted. An invariant is a property that survives all permitted operations. A coordinate artifact is anything that varies within an orbit. The choice of regime is a design decision; the invariants are its consequences. This is the Erlangen move: characterize equivalence before characterizing truth.

The chapter's thesis can now be stated precisely. A property is "real" if it is $G$ -invariant. Everything else is artifact of representation.

Why does this matter for computation? Because every integration, every data pipeline, every system boundary involves the question "are these the same thing?" and that question has no answer without a declared regime. Systems that leave the regime implicit are systems that leave equivalence undefined. They work until they don't, and when they fail, the failure mode is always the same: two components disagreed about what counted as "the same."

The Erlangen framing does not make the problem easy. It makes the problem precise. Declaring $G$ requires design effort. Enforcing invariants requires implementation discipline. But precision is the precondition for progress. You cannot debug a mismatch you cannot state.

But we do not yet have recognition. Knowing that two structures could be equivalent (because an invariant-preserving transformation exists between them) is not the same as knowing that they are equivalent in a specific instance. For that, we need a map—something that demonstrates, concretely, how to get from one representation to the other. We need a witness.

If invariants are what is real, then what certifies reality across a seam? The notary's bill of exchange -- the motivating example from Vol I's prologue -- certified that a debt in Bruges was the same debt in Venice. The bill did not inspect the ink; it preserved what mattered: the parties, the sum, the obligation. The bill was a structure that made the invariant transportable. We will need such structures again.

The next chapter develops the concept: isomorphism as a witnessed claim of sameness.