57
$\begingroup$

A common way to define a group is as the group of structure-preserving transformations on some structured set. For example, the symmetric group on a set $X$ preserves no structure: or, in other words, it preserves only the structure of being a set. When $X$ is finite, what structure can the alternating group be said to preserve?

As a way of making the question precise, is there a natural definition of a category $C$ equipped with a faithful functor to $\text{FinSet}$ such that the skeleton of the underlying groupoid of $C$ is the groupoid with objects $X_n$ such that $\text{Aut}(X_n) \simeq A_n$?

Edit: I've been looking for a purely combinatorial answer, but upon reflection a geometric answer might be more appropriate. If someone can provide a convincing argument why a geometric answer is more natural than a combinatorial answer I will be happy to accept that answer (or Omar's answer).

$\endgroup$
4
  • 1
    $\begingroup$ I have a copout answer involving a total order on X but I would really not like to introduce a total order to solve this problem. Somehow I feel that the essence of the structure necessary is less than that. $\endgroup$ Sep 22, 2010 at 4:02
  • $\begingroup$ You can just take X_n to be a Cayley graph of A_n with some natural generating set. You probably don't count this as natural enough though. $\endgroup$
    – Alon Amit
    Sep 22, 2010 at 4:08
  • $\begingroup$ What is the precise meaning of "natural definition"? $\endgroup$ May 27, 2011 at 15:19
  • 1
    $\begingroup$ @Hans: in this context, there really isn't one. $\endgroup$ May 27, 2011 at 15:33

8 Answers 8

14
$\begingroup$

The alternating group preserves orientation, more or less by definition. I guess you can take $C$ to be the category of simplices together with an orientation. I.e., the objects of $C$ are affinely independent sets of points in some $\mathbb R^n$ together with an orientation and the morphisms are affine transformations taking the vertices of one simplex to the vertices of another. Of course this is cheating since if you actually try to define orientation you'll probably wind up with something like "coset of the alternating group" as the definition. On the other hand, some people find orientations of simplices to be a geometric concept, so this might conceivably be reasonable to you.

$\endgroup$
3
  • 1
    $\begingroup$ I considered this, but I wonder if the definition can be made as set-theoretic as possible, with as little geometry as possible. $\endgroup$ Sep 22, 2010 at 4:25
  • 5
    $\begingroup$ @Qiaochu, since orientation has to do with determinants, maybe you could whittle the above down to a discrete interpretation of determinants -- the determinants of permutation matrices, perhaps. Or would that be circular? The determinant does have an independent definition unrelated to the signature of a permutation. $\endgroup$
    – user856
    Sep 22, 2010 at 4:42
  • $\begingroup$ So the question is: what is an oriented set? Answer: It's a set with an orientation. So what is an orientation on a set? ${}\qquad{}$ $\endgroup$ May 15, 2015 at 21:51
13
$\begingroup$

$A_n$ is the symmetry group of the chamber of the Tits building of $\mathbb{P}GL_n$. The shape of this chamber is independent of what coefficients you insert into the group scheme $\mathbb{P}GL_n$, just the number and configuration of chambers changes. If you insert the finite fields $\mathbb{F}_p$ then you get finite simplicial complexes as buildings, and the smaller $p$ gets, the fewer chambers you have. You can analyse and even reconstruct the group in terms of its action on this building. The natural limit case would be just having one chamber and the symmetry group of this chamber - the Weyl group - is $A_n$. This is how Tits first thought that there is a limit case to the sequence of finite fields - which he called the field with one element.

Maybe somewhat more algebraically you can think in terms of Lie algebras - as I said the shape of the chamber does not change with different coefficients. The reason is that it is determined just by the Lie algebra of the group and thus describable by a Dynkin diagram or by a root system (ok, geometry creeps in again). The Wikipedia page about Weyl groups tells you that the Weyl group of the Lie algebra $sl_n$ is $S_n$. If have no experience with Lie algebras, but maybe you can get $A_n$ the same way.

If you can get hold of it, you can read Tits' original account, it's nice to read (but geometric) see the reference on this Wikipedia page.

Edit: Aha, I found a link now: Lieven Le Bruyn's F_un is back online. You can look there under "papers" and find Tits' article. And, since you are picking up the determinant ideas, you should definitely take a look at Kapranov/Smirnov!

$\endgroup$
5
  • 4
    $\begingroup$ Doesn't GL(n) involve ordering an n-element set (of basis vectors)? The question Qiaochu is raising is something like, can we construct A(X), with X a set or a set with "Alt-structure" weaker than an ordering. The A_n and S_n and GL_n with their standard embeddings into each other assume the standard ordering. One can discuss GL(V) for V a vector space, but constructing it as an algebraic group uses an order, at least in the usual presentation of the theory. $\endgroup$
    – T..
    Sep 29, 2010 at 17:12
  • $\begingroup$ Does it? Aren't the group operations still there when you forget about the coordinates, which you used to define it via matrix multiplication? The construction of the building then uses just coordinate-free notions like "Borel subgroups", as far as I remember... $\endgroup$
    – Who
    Sep 29, 2010 at 17:25
  • 1
    $\begingroup$ I am also starting to find that strange now: Does an embedding of S_n into GL_n give me a choice of basis? Maybe via picking eigenvectors? If not one could define A_n as the intersection of S_n with O_n (which is definable coordinate-free) under any embedding - and then use coordinates to show independence of the embedding. $\endgroup$
    – Who
    Sep 29, 2010 at 17:32
  • $\begingroup$ I should have added that in addition to defining A(X) (which requires no structure except the finite set X), the problem here is to define even bijections from X to Y. This cannot be done without extra data, but does not require the full strength of an ordering. Functorial construction of Tits building from X and Y would, for any bijection, give a map from the X-building to the Y-building and asking whether it is an isomorphism of whatever structure in the building defines A(X) would define even bijections. So I suspect some sort of extra data is hidden in the construction. $\endgroup$
    – T..
    Sep 30, 2010 at 7:30
  • $\begingroup$ I don't know whether the construction of the Tits building is functorial. I didn't mean to imply this with anything I wrote. It would be nice of course, then an embedding of S_n might correspond to the inclusion of a particular chamber. $\endgroup$
    – Who
    Sep 30, 2010 at 15:33
4
$\begingroup$

Here is one idea, although I do not find it very satisfying. An object of $C$ is a finite set $X$ equipped with $\frac{|X|!}{2}$ (or $1$ if $|X| = 1$) total orders, all of which are even with respect to each other (in other words, basically a coset of $A_n$ in $S_n$). A morphism between two objects in $X$ is a map of sets preserving these orders (in other words, take one of the orderings on $X$ and apply a function $f : X \to Y$ to its elements. The result, after throwing out repeats, must be compatible with an ordering on $Y$.)

This is more or less a discretization of Omar's answer. Again, I would like to do better than this, or at least see the data described above packaged in a more satisfying way.

$\endgroup$
2
$\begingroup$

You can do with something very slightly weaker than an ordering: an identification of each $n$-element set with a single "universal" (unordered) $n$-set. This data canonically identifies any two $n$-element sets and thus associates a permutation to any bijection of such sets. Even bijections can then be defined in terms of the cycle structure of the permutations.

This is not much of an improvement, but you are in effect asking for a lifting of the alternating group to a groupoid of maps between finite sets. It is hard to see how to determine whether a bijection of finite sets is even (reducing to the usual notion when the sets are the same, and also "transporting structure" along the whole category) without having a coordinatization of the sets.

$\endgroup$
2
$\begingroup$

(This is, essentially, just a «repackaging» of your answer. Still, I find this version somewhat more satisfying — at least, it avoids even mentioning total orders.)

For a finite set $X$ consider projection $\pi\colon X^2\to S^2 X$ (where $S^2 X=X^2/S_2$ is the symmetric square). To a section $s$ of the projection one can associate a polynomial $\prod\limits_{i\neq j,\,(i,j)\in\operatorname{Im}s}(x_i-x_j)$ — and since any two such products coincide up to a sign, this gives a partition of the set $\operatorname{Sec}(\pi)$ into two parts. Now, $A_X$ is the subgroup of $S_X$ preserving both elements of this partition. (I.e. the structure is choice of one of two elements of the described partition of $\operatorname{Sec}(\pi)$.)

$\endgroup$
2
$\begingroup$

The polynomial $p\in K\left[X_1,...,X_n\right]$ given by $$p\left(X_1,...,X_n\right)=\prod_{i<j}\left(X_i-X_j\right)$$

$\endgroup$
2
$\begingroup$

Let us define an orientation of a finite set recursively.

  1. An orientation of the empty set is either $-1$ or $+1$.
  2. An orientation of a finite set $X$ is the data of an orientation for each $Y ⊆ X$ of cocardinality 1 (meaning $|Y|=|X|-1$) and such that for each $Z ⊆ X$ of cocardinality 2, if $X = Z∪\{a,b\}$, then the two orientations induced on $Z$ by going through the two possible paths $X → Z∪\{a\} → Z$ and $X→Z∪\{b\}→Z$ are different ("opposites").

We obtain, for each set, two possible orientations. This can be proved by showing that for any $Y ⊆ X$ of cocardinality $1$, there is a unique way of extending an orientation of $Y$ to an orientation of $X$. This also shows that each linear ordering of $X$ gives an orientation.

We can visualize what an orientation is on a drawing of a triangle or of a tetrahedron: we orient the faces/edges and make it so that everything glues nicely along the edges/vertices.

Each permutation of $X$ acts naturally on the set of orientations of $X$, and the permutations acting trivially are the even ones.

But it is not clear enough to me how this interacts in a more formal way with the intuitions there are in simplicial homology or about the exterior algebra.

$\endgroup$
0
$\begingroup$

One idea is to view $S_n$ as permutations of pairs in a $2n$-element set. (This approach may be equivalent to Omar's answer above, but it's more elementary.)

Let $X = \{x_1,\ldots,x_n\}$ be an $n$-element set. We can define a $2n$-element, call it $\pm X$, by adding a formal "opposite" to each element of $X$, so $\pm X = \{x_1,-x_1,\ldots,x_n,-x_n\}$.

We can define a map $\operatorname{Perm}(X) \to \operatorname{Perm}(\pm X)$, sending $\sigma \mapsto (\operatorname{sgn}\sigma)\cdot \sigma$. That is, if $\sigma$ is odd, it acts on $\pm X$ like it would on $X$, but also flips signs. If $\sigma$ is even, it does the permutation $\sigma$ on positive and negative elements independently.

$S_n$ acts on the $n$ subsets $\{\pm x_i\}$, sending $\{\pm x_i\} \mapsto \{\pm \sigma(x_i)\}$. The subgroup $A_n$ inherits the same action, but it preserves the two subsets $+X$ and $-X$ of $\pm X$ containing the positive and negative elements.

For a geometric example, see the 4 vertices of the tetrahedron below. If this figure is centered at the origin, then the opposites of the vertices complete a cube. The octahedral group $O$ is isomorphic to $S_4$, permuting the diagonals of this cube. Some rotations of the cube, corresponding to odd permutations in $S_4$ send this tetrahedron to the one consisting of the other four vertices. Only the even permutations, $A_4$, preserve the tetrahedron.

          CubeTetra
          (Image from MathWorld.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .