# Is there a “natural” / “categorical” definition of the “parity” of a permutation?

Given a permutation $\sigma$ on $n$ elements (i.e. $\sigma \in S_n$), there is a notion of "parity" (or "sign" or "signature") of $\sigma$, which can be defined in several equivalent ways (look here). This produces a homomorphism $S_n \to \{\pm 1\}$.

I've known the various definitions, the proof of their equivalences and the various applications of them for quite a while, and yet something seems missing. I can't convince myself that any of those definitions is really "natural". Of course "natural" is something rather subjective, but for me at least, it is close in meaning to "categorical". For example, a "natural" presentation of the definition (and basic properties) of addition/multiplication of natural numbers, can be achieved by considering the category of finite sets, where these operations are categorical sum/product.

Since $S_n$ is the automorphism group of a set with $n$ elements, I would say that the (horizontal?) categorification of it is the groupoid of all sets with $n$-elements. This is arguably a more "natural" object. Of course, this groupoid is equivalent to $S_n$ so it is just a matter of perspective. Now, we can define the quotient groupoid for which the hom-sets are the two element sets of equivalence classes of isomorphisms, where two are equivalent if there quotient is an even permutation. This is cheating of course. The question is, can we define this quotient in a "natural" way? I find it very surprising that this kind of structure associated with plain finite sets, is so well hidden.

I heard that the K-theory of finite sets encodes some information of this sort. If this is so, I would be very happy to hear more about it.

As a final note, one famous neat application of the notion of parity of a permutation is the proof of the impossibility of the 14-15 puzzle. The proof is beautiful, but it applies group-theory techniques to something which is most naturally viewed as a groupoid. This might be completely unrelated to the main question, but it seems that a more natural/groupoidal definition of parity might be applicable to this situation as well.

-
Why is 14-15 more naturally a groupoid? Are you thinking of reinterpreting the notion of $G$-set as a groupoid, where you add arrows $x \xrightarrow{g} gx$ for all set elements $x$ and group elements $g$? – Hurkyl Apr 23 '14 at 8:45
I probably should have explained more. I meant that the objects are the possible states of the puzzle and the arrows are the legal moves. Since at each stage you can apply only a subset of permutations (depending on where the hole is), it is not an $S_n$-set in an obvious way, but rather a more complicated groupoid. – KotelKanim Apr 23 '14 at 8:50
What you describe is only a graph: to get a category you have to throw in composites of legal moves too. – Hurkyl Apr 23 '14 at 8:53
(Somewhat) related: What structure does the alternating group preserve? – Grigory M Apr 23 '14 at 8:59
@Hurkyl, Of course. Thank you for the correction. I only described a "generating set", but you should include all compositions of these. – KotelKanim Apr 23 '14 at 9:00

Now, we can define the quotient groupoid for which the hom-sets are the two element sets of equivalence classes of isomorphisms, where two are equivalent if there quotient is an even permutation. This is cheating of course. The question is, can we define this quotient in a «natural» way?

Fix a field $k$ (of $\operatorname{char}\ne2$). There is a functor $\det\colon S\mapsto\Lambda^{top}(k[S])$ from our groupoid to the category of vector spaces. Now we can define the quotient groupoid ($f\sim g\iff\det f=\det g$).

Whether this definition is natural enough, can be debated, of course. At least it's natural in the sense that one doesn't have to identify a set with $\{1,\ldots,n\}$ etc.

P.S. The exterior algebra can be defined w/o permutations (as the quotient of the free algebra by relations $v\wedge v=0$).

-

This is the abelianization map $S_n \to S_n/[S_n, S_n]$. It's universal with respect to maps from $S_n$ to abelian groups.

-
Good point. But still, I was hoping for something a bit different. Namely, that all this should be something about maps between finite sets and not just group theoretic properties of $S_n$. Or rather, why the abelianization of $S_n$ is the group of order two for all $n$. – KotelKanim Apr 26 '14 at 7:29
@Kotel: you cannot define the parity of a map, even a bijection, between finite sets. The only maps which have well-defined parity are automorphisms of a fixed finite set, so there's very little difference between talking about the group and talking about the category here. – Qiaochu Yuan Apr 27 '14 at 17:40

Here's an answer that might be more like what you were expecting. The collection of all symmetric groups together organize into a symmetric monoidal groupoid, namely the symmetric monoidal groupoid $S$ of finite sets and bijections. This is the free symmetric monoidal groupoid on a point.

Now, given any symmetric monoidal category you can ask what it looks like when you freely adjoin inverses to it, at various levels of sophistication. First, you can just ask for its Grothendieck group; that is, you look at the commutative monoid of isomorphism classes, then adjoin inverses. This gives you $\mathbb{Z}$.

Second, you can ask for a symmetric monoidal groupoid rather than just a group, but one where every object is invertible (I think this is sometimes called a "Picard groupoid"). This gives you a groupoid with $\pi_0 \cong \mathbb{Z}$ and $\pi_1 \cong \mathbb{Z}_2$: that is, the objects under the symmetric monoidal product are just $\mathbb{Z}$ again, but now they have automorphisms of order $2$. The induced map from $S$ sends each permutation to its sign, but also assigns data to isomorphisms between finite sets which we haven't necessarily identified. This Picard groupoid is the free Picard groupoid on a point.

Continuing in this way, you can ask for a symmetric monoidal $n$-groupoid rather than just a groupoid, or in other words a connective $n$-truncated spectrum. The spectrum you get in this way is the $n$-truncation $\tau_{\le n}(\mathbb{S})$ of the sphere spectrum (which is the free spectrum on a point). This is a version of the Barratt-Priddy-Quillen theorem, and it reveals that the $\mathbb{Z}$ above was the zeroth stable homotopy group of spheres, while the $\mathbb{Z}_2$ above was the first. These $n$-truncations, and the natural map from $S$ into them, are candidates for "higher sign characters" as in Ganter-Kapranov.

-

I am not sure at what level of sophistication you are looking for such a "natural" definition but a good candidate is orientability. Thinking of the permutation as permuting vectors in a basis for a finite-dimensional vector space, one can characterize parity of the permutation in terms of preserving or reversing the orientation. The orientation itself can be formalized in terms of the determinant bundle (in this case over a single point) of the vector space. Namely, the orientation is an element of this line bundle, and the permutation induces an action either by $+1$ or by $-1$ on this bundle, corresponding respectively to a even or odd permutation.

-
I am aware of this idea, but it is somewhat unsatisfactory in my opinion. The geometric notion of orientation gives a nice intuition, but to formally extract the notion of parity from it requires some technical work. For example, you can define the parity as the determinant of the associated permutation matrix. This is possible (and non-circular), but it is a bit mysterious. Note that I am not looking for something elementary, or simple in any way. I am hoping for a construction that will say something like "parity is the universal 'blah' of the category of finite sets". – KotelKanim Apr 23 '14 at 11:59
What I tried to point out in my answer is that one does not need to resort to matrices here. The determinant bundle is a fairly canonical construction, and the induced action is similarly "natural" in a categorical sense. Thus we are reduced to a $Z_2$ action on a line bundle, all coordinate-free. – Mikhail Katz Apr 23 '14 at 12:01
You are right. I wasn't paying attention enough. This is similar to Grigory's answer. It still seems strange that you have to pass through vector spaces (whether you call it geometry or algebra). – KotelKanim Apr 23 '14 at 12:05
Just to elaborate a bit, when passing through vector spaces, there is an arbitrary choice of the scalar field. Since the construction does not depend on it, it seems artificial. Perhaps there is something general to say about the connection to $GL_n$ as a group scheme. Or maybe even $\mathbb{F}_1$ (though I really know nothing about that, so maybe I shouldn't through big words...) – KotelKanim Apr 23 '14 at 12:11
I would suggest $\mathbb{F}_3$. That seems more natural. – Mikhail Katz Apr 27 '14 at 8:11