I am fond of saying that the two theorems that laypeople do not know because curricula arbitrarily do not bother to show them, yet which are about phenomena of ubiquitous generality in down-to-Earth grade school mathematics, are Bezout’s theorem and the fact that permutations carry parity. I know of two traditional proofs for this fact, but perhaps they are the same in the end. Let’s see.

First, consider a simple graph on N nodes; that is, an undirected graph without bothering to allow reflexive or multiple edges. We can take this as specifying a set of transpositions on the set of nodes; each edge says we are given the transposition which exchanges the two nodes it connects and acts as identity elsewhere.

The graph is split into connected components, and the transpositions it corresponds to generate all and only those permutations which leave each node within the same connected component it started in.

Proof: That each node is left within the same connected component it started in is obvious, as no transposition moves anyone out of their connected component. That all transpositions within a connected component can be generated follows once we establish transitivity: if you can generate the transposition (a b) and the transposition (b c), then you can generate the transposition (a c), as the composition (a b) (b c) (a b).

From now on, let’s presume our graph has a single connected component.

We furthermore get from it a simple graph on the symmetric group on N nodes, where two elements are connected by an edge just in case some edge in the original graph gives a transposition which takes them to each other. [Note that this is a much larger graph than the one we started with; it has N! nodes]. We can also look just as well at torsors of the symmetric group, which is sometimes more convenient, but I’ll phrase things this way for now.

Often, it’ll be the case that we can define a function f from the nodes of this large graph to natural numbers such that: A) Identity is the unique value taken to 0 by f. B) Any value which is not the identity is such that it has a neighbor on which the value of f is one less. C) Neighbors always have values of f which differ by no more than 1. D) Neighbors always have values of f which differ by no less than 1.

A, B, and C ensure that f is the distance from identity function. Adding in D tells us that furthermore this is a bipartite graph; thus we get our notion of parity for permutations.

Note that we get the same notion of parity no matter what graph we start with, noting that our composition law above for paths in a transposition graph preserves oddity and thus makes all transpositions odd. [More specifically, a path of length n of basic transpositions can be turned into a composition of 2n - 1 basic transpositions]

One case of interest is when the graph we start with is the complete graph on N nodes. This is the proof of permutation parity by cycle counting. (This gives another way to see that no matter what choice of initial graph we make, we get the same parity concept in the end, since any path of even or odd length in some subgraph is subsumed as a path of the same length in this one.)

Another case of interest is when the graph we start with is an N node linear path. This is the proof of permutation parity by inversion counting.

Are other cases such that we can make f in a convenient way as well? E.g., the graph on 4 nodes with one hub and three spokes? We can always make the f which satisfies the desired properties, but can we actually see that it satisfies the desired properties beforehand, without already knowing the parity theorem? Can we read the distance off quickly in some fashion?

TODO!

[TODO: Rewrite everything for readability. Expand on cycle counting and inversion counting proofs in detail.]

[TODO: We needn’t only talk about distances in terms of transpositions. We could take odd involutions or odd permutations more generally in our basis]

[TODO: This all relates to a more general phenomenon about distance functions in Coxeter groups. The linear graph representation is directly a Coxeter group. The complete graph representation isn’t directly a Coxeter group, it’s just a group generated by involutions but also containing further relations than the Coxeter ones, but perhaps there’s something to say there in Coxeter style too?]

TODO:

Re: https://mathoverflow.net/a/417732/3902 on permutation parity (“Let X be a finite set of size at least 2. Let E be the set of edges of the complete graph on X. The set D of ways of directing those edges is a torsor under {±1}E. Let G be the kernel of the product homomorphism {±1}E→{±1}. Since ({±1}E:G)=2, the set D/G of G-orbits in D has size 2. The symmetric group Sym(X) acts on X, D, and D/G, so we get a homomorphism Sym(X)→Sym(D/G)≃{±1}. Each transposition (ij) maps to −1 because if d∈D has all edges at i and j outward except for the edge from i to j, then (ij)d equals d except for the direction of the edge between i and j.”)

It’s interesting this proof relates to both the inversion-counting/polynomial proof and to the cycle-counting proof. The relation to inversion-counting is clear (consider directing edges linearly) and that this is the same as the polynomial proof is also straightforward (think of a directed edge as negating when reversed, and an element of D as the product of all its directed edges. The polynomial setup is where we specifically describe an edge as a difference of variables corresponding to its endpoints). But the relation to cycle-counting is perhaps less obvious. – Sridhar Ramesh 2 hours ago
I will write it out a bit tersely, because of character constraints. Hopefully it will still be understandable. Instead of just considering the effect (as in, $\pm 1$) of $p \in Sym(X)$ on D/G = (orientations of all of E)/G, we can also consider p’s effect on (orientations of E’)/G for any subset $E’ \subseteq E$ closed under the action of p. And the combined effect of p on a union of disjoint such E’ is the product of its effects on the individual E’. In particular, we can break down E into its individual orbits under p, and consider the effect of p on each of these orbits separately. – Sridhar Ramesh 2 hours ago Delete Any cycle of X under p of even length 2n gives rise to an orbit of E under p of size n, this orbit comprising the diameters of the cycle. It is readily seen that these are all and only the orbits of E on which p’s effect is -1. Thus, the overall effect of p on D/G is equal to (-1)^(the number of even length cycles of X under p). – Sridhar Ramesh 2 hours ago

Permutation parity is something we can calculate by thinking about these two different group actions (permutations acting on themselves and counting cycles, or acting on orderings and counting inversions). These are sort of isomorphic group actions (both are torsors), and yet sort of non-isomorphic (the cycle count goes from 1 to n, but the distance between orderings or edge-orientations goes from 0 to (n choose 2)).

Perhaps the unification idea here could help us finally unify the two ways of thinking about Fermat’s little theorem via two different group actions (Lagrange’s theorem vs. necklace-counting), especially as the polynomial and cycle-counting approach unification above is related to the proof of Lagrange’s theorem in the context of abelian groups by a big product and division and how this relates to counting cycles.