Timeline for Conceptual reason why the sign of a permutation is well-defined?
Current License: CC BY-SA 4.0
44 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 18, 2022 at 19:55 | comment | added | Tom Copeland | @TimCampion: Are not the Vandermonde determinant and the associated moment polynomials, symmetric function/polynomial theory, volumes and combinatorics of the n-simplices / hypertriangles / hypertetrahedrons, wedge products, the complete graphs, the symmetric groups, and Coxeter reflection groups inextricably intertwined and so must combinatorics, algebra, and geometry in these 'answers' be ultimately interrelated? (The usual biases and skewed familiarity researchers have for and with these topics then influence the voting for 'THE' answer.) | |
| Mar 16, 2022 at 12:17 | comment | added | Tim Campion | Personally, I'm so accustomed to groups arising in my life via one of the latter two constructions that I barely think of them as algebraic objects at all! On the flip side, a great deal of combinatorics can be discussed in the language of combinatorial species, and thus in terms of actions of symmetric groups; to me the appearance of a combinatorial species doesn't mean we've switched from doing combinatorics to algebra. | |
| Mar 16, 2022 at 12:17 | comment | added | Tim Campion | @TimothyChow I see your point; let me push back a bit. In general, mathematical arguments resist this sort of classification into subfields. And this is already the case here: True, a group may be defined as a set with an operation satisfying axioms -- an algebraic definition. But a group may also be defined as a category with one object and every morphism invertible -- a category-theoretic definition; a group action is a presheaf. Or, a group may be defined as a connected, 1-truncted homotopy type -- a homotopy-theoretic definition; a group action is a fibration with discrete fibers. | |
| Mar 15, 2022 at 16:37 | comment | added | Timothy Chow | @TimCampion I guess it depends on your vantage point. From where I sit, the "combinatorial proof" would be simply noting the parity of the number of inversions in the one-line representation of a permutation, and the behavior of this invariant under transpositions. As soon as we start talking about actions or homomorphisms or even groups, it becomes algebraic to me. | |
| Mar 15, 2022 at 16:00 | comment | added | Tim Campion | @TimothyChow I tend to think of this proof as a combinatorial proof rather than an algebraic one. In fact, this is one reason I prefer it to the polynomial proof, because I think of $\Sigma_n$ as an object which is "fundamentally combinatorial in nature". Besides aesthetic value, it makes the proof more "portable" -- if I have some other setting where I want to set up a theory analogous to the theory of symmetric groups, it's nice to have a minimum of conceptual apparatus which needs to be replicated in the new setting in order to reproduce basic facts like the existence of $sgn$. | |
| Mar 14, 2022 at 21:41 | comment | added | David Roberts♦ | @BjornPoonen yes, thanks for disabusing me of the notion. But I'm glad that something that is in the neighbourhood of combinatorial species did make an appearance, in the end! | |
| Mar 14, 2022 at 19:41 | comment | added | Bjorn Poonen | @DavidRoberts: What you want does not exist. Any functor from (finite sets of size $\ge 2$, injections) to (size 2 sets, bijections) maps every automorphism to an identity morphism. For an example of what goes wrong, ask what the functor would do to the composition $\{1,2\} \to \{1,2,3,4\} \to \{1,2,3,4\}$ consisting of the inclusion followed by the transposition $(34)$. More generally, the problem is that every permutation is the restriction of an even permutation on some larger set. | |
| Mar 14, 2022 at 10:52 | comment | added | David Roberts♦ | @Bjorn I was hoping for an explanation like this, but with the functor extended to finite sets and injections (of size >1) | |
| Mar 13, 2022 at 23:08 | comment | added | Deane Yang | @BjornPoonen, thanks for elaborating. You've sold me on this. | |
| Mar 13, 2022 at 22:44 | comment | added | Bjorn Poonen | That this is a functor is saying that if you relabel the elements of $X$ using a bijection $X \to Y$, then you get a corresponding relabeling $D_X/G_X \to D_Y/G_Y$ (and that this respects composition, ...) This is clear conceptually since the construction never uses the names of the elements of $X$. | |
| Mar 13, 2022 at 22:35 | comment | added | Bjorn Poonen | For the sake of others: To say that $D$ is a torsor under $\{\pm1\}^E$ just means that $\{\pm 1\}^E$ acts simply transitively on $D$. The construction of $Sym(X) \to Sym(D/G)$ is conceptual in the sense asked for, that no auxiliary computation is required to verify that it is well-defined or that it is a homomorphism. To me, it is obvious that the construction $X \mapsto D/G$ defines a functor from the category (finite sets of size $\ge 2$, bijections) to the category (size $2$ sets, bijections), and then it is automatic that one gets $Sym(X) \to Sym(D/G)$. | |
| Mar 13, 2022 at 22:08 | comment | added | Deane Yang | I had to look up what a torsor is, but I can see now that this is a particularly elegant proof. So I hate to complain, but in what sense is it a conceptual proof? | |
| Mar 12, 2022 at 8:29 | comment | added | HJRW | @TimothyChow: Thanks, that's interesting. It seems that there's something more to do: to convince oneself that $A_n$ (perhaps characterised as in this answer) is the exactly $S_n\cap SO(n)$. From this point of view, it's essential to extend this kind of reasoning about the sign map to the determinant. | |
| Mar 11, 2022 at 18:16 | comment | added | Timothy Chow | @BjornPoonen Such a geometric approach to foundations would be very exciting, though I doubt that it will be realized any time soon. For a small but very interesting step in this direction, I recommend Euclid and His Twentieth Century Rivals by Nathaniel Miller and related work such as A formal system for Euclid's Elements. | |
| Mar 11, 2022 at 17:59 | comment | added | Bjorn Poonen | @TimothyChow: If I understand you correctly, you are arguing that certain geometric notions like the notion of orientation of Euclidean space are more fundamental than the algebra currently used to formalize them. Maybe you are even speculating that someday there will be a more geometric approach to foundations in which the existence of sgn is immediate? I do like this line of thought, though I don't know if it will be possible. | |
| Mar 11, 2022 at 17:06 | comment | added | Timothy Chow | Even in 3 dimensions, capturing our geometric intuition of a rotation is formally difficult. The conventional approach requires us to construct the real numbers and describe continuous transformations that preserve the metric. But to me this does not imply that rotations in 3 dimensions are a complicated concept. It says more about the gap between our intuitive grasp of geometry and our ability to formalize it. | |
| Mar 11, 2022 at 16:55 | comment | added | Timothy Chow | @BjornPoonen I've mentioned this in other comments. Following Atiyah, I will accept the devil's offer to use algebra if you insist on a formal answer to your question. But in my soul I know that the true explanation for $A_n$ is geometric. Algebra is just there to silence the skeptics. (Again, I'm focusing on conceptual explanation rather than formal proof.) | |
| Mar 11, 2022 at 16:44 | comment | added | Sridhar Ramesh | Re: HJRW: Personally, my view is that this argument is essentially the same as the standard polynomial argument given at mathoverflow.net/a/417692/3902, but abstracted a bit further out from the specific representation as polynomials. Or essentially the same as the standard inversion counting argument, but relaxed from specifically demanding a linear order. In that sense, it is essentially the same as very many of the answers given, or approaches already noted in the question. But abstracted out nicely to a point where it feels more natural or less ad hoc, at least to many. | |
| Mar 11, 2022 at 15:58 | comment | added | Bjorn Poonen | @FrançoisG.Dorais: WLOG $X=\{1,\ldots,n\}$ and $\sigma=(12\cdots k)$. If $d \in D$ is given by the standard ordering, then $\sigma d$ is the same as $d$ except that the edges $\{i,k\}$ for $i=1,\ldots,k-1$ have been reversed. Thus $\sigma$ maps to $(-1)^{k-1}$. | |
| Mar 11, 2022 at 15:53 | comment | added | Bjorn Poonen | @TimothyChow: In your explanation, how would you explain what "rotations of a simplex" are (especially for $n>4$), and how would you convince me that they do not generate the whole symmetric group? | |
| Mar 11, 2022 at 13:58 | comment | added | Timothy Chow | @HJRW Yes, I don't find it more natural. Roughly speaking, it gives an algebraic proof of what I consider to be a geometric fact. Nothing wrong with that, but I don't find it any more explanatory than, say, simply counting inversions. That $A_n$ is the group of rotations of a simplex is, to me, the explanation for its existence. | |
| Mar 11, 2022 at 8:31 | comment | added | HJRW | @TimothyChow: I'm curious. Are you saying that you don't share the widespread view that this argument is somehow more natural than many of the others? | |
| Mar 11, 2022 at 5:03 | comment | added | François G. Dorais | This is a fantastic answer! As a sort of "nitpik": there ought to be some easy and natural way to see how the parity of a cycle is related to the parity of the length of the cycle. What is it? | |
| Mar 10, 2022 at 20:39 | comment | added | R. van Dobben de Bruyn | @TimothyChow I also think people read the question differently. It specifically asks for a conceptual argument, so that's what I focused on. But it was inspired by an interaction with students, so quite a few answers focus on elementary or slick arguments instead (this is definitely missing from some of the answers, including mine). Poonen's answer combines the two. (Admittedly, this answer is what I tried to do, but I couldn't make it work as nicely.) | |
| Mar 10, 2022 at 20:27 | comment | added | Sridhar Ramesh | 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). | |
| Mar 10, 2022 at 20:27 | comment | added | Sridhar Ramesh | 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. | |
| Mar 10, 2022 at 20:27 | comment | added | Sridhar Ramesh | 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. | |
| Mar 10, 2022 at 17:18 | comment | added | Timothy Chow | This has been an educational MO question for me, but I feel that I've learned more about mathematicians than about mathematics. Clearly, some other people's intuitions don't line up with my own, and I feel like I have to reverse engineer the mindset that makes certain arguments seem natural and others seem contrived. | |
| Mar 10, 2022 at 13:18 | comment | added | David E Speyer | @SridharRamesh There is at least one more: The subgroup of sign patterns which multiply to $1$ around any cycle. | |
| Mar 10, 2022 at 5:36 | comment | added | Sridhar Ramesh | Oh, good point, I lost track of the difference between $X$ and $E$ here. | |
| Mar 10, 2022 at 1:51 | comment | added | Tim Campion | @SridharRamesh I think I'd find that argument convincing if we were talking about $Sym(X)$-invariant subsets of $\{\pm 1 \}^X$, but the action of $Sym(X)$ on $\{\pm 1\}^E$ is "less transitive", and I think more needs to be said. The question is equivalently: if $V$ is a finite-dimensional $\mathbb F_2$-vector space, then how many $End(V)$-submodules does $\Lambda^2(V)$ have? | |
| Mar 10, 2022 at 1:33 | vote | accept | Tim Campion | ||
| Mar 9, 2022 at 22:51 | comment | added | Sridhar Ramesh | I think there are only four Sym(X)-invariant subgroups of $\{\pm 1\}^E$ in general: The trivial maximal and minimal ones, the one called $G$ here, and the two-element one containing all +1 or all -1. Up to the action of Sym(X), all that matters about an element of $\{\pm 1\}$ is how many -1s it contains. And if such an element has a number of -1s strictly between 0 and |E|, then by multiplying it by a shifted over version of itself, so to speak, it generates an element with precisely two -1s, which in turn can be used to generate all elements with an even number of -1s (i.e., all of $G$). | |
| Mar 9, 2022 at 19:38 | history | edited | LSpice | CC BY-SA 4.0 |
Link to @DanRamras's answer
|
| Mar 9, 2022 at 17:25 | comment | added | R. van Dobben de Bruyn | I withdraw my reservation from my earlier comment: in a more general setting of $A^E \to A$ for an abelian group $A$, the analogous set $D/G$ does not have $2$ elements, but is still an $A^E/G$-torsor, so there is an injection $\iota \colon A^E/G \hookrightarrow \operatorname{Sym}(D/G)$. I believe that the commutators of the $\operatorname{Sym}(X)$- and $A^E$-actions on $D$ are in $G$, so that the image of $\operatorname{Sym}(X) \to \operatorname{Sym}(D/G)$ lands in the image of $\iota$. (Anyway, this is only relevant for generalisations, not for the question itself.) | |
| Mar 9, 2022 at 15:53 | comment | added | Benjamin Steinberg | Essentially this argument is in Algebre and Theories Galiosienne by Douady and Douady but they use a language of choice functions instead of orienting edges and argue more like Cartier. This proof is slicker | |
| Mar 9, 2022 at 15:44 | comment | added | Tim Campion | The construction really just yields a nontrivial action of $Sym(X)$ on a 2-element set. So if you choose a different subgroup $G'$, you'll get an action on a subgroup of a different size, and hence you'll get various subgroups of $Sym(X)$ from the istropy, but there's no reason for these isotropy subgroups to be normal. So in some sense we are using the fact that index 2 subgroups are alway normal. In fact, the argument implicitly includes a proof of this fact which is new to me. | |
| Mar 9, 2022 at 15:29 | comment | added | Benjamin Steinberg | I think it is special because it is the only index 2 invariant subgroup | |
| Mar 9, 2022 at 15:16 | comment | added | Tim Campion | My only complaint about this proof is that it's almost too slick -- it suggests to me that by taking $G$ to be some other $Sym(X)$-invariant subgroup of $\{\pm 1\}^E$, one could get all sorts of interesting homomorphisms out of $Sym(X)$. Of course, a posteriori it must turn out that these are all just variations on $sgn$, but I would like to reflect on what is so special about this particular subgroup $G \subset \{\pm 1\}^E$. | |
| Mar 9, 2022 at 15:01 | comment | added | Tim Campion | I agree with Sam -- this proof is from the Book! A few notes: 1.) To see that the action of $Sym(X)$ descends from $D$ to $D/G$, one should of course note that there is a compatibility of actions: $\sigma \cdot (d \cdot g) = (\sigma \cdot d) \cdot (\sigma \cdot g)$ for $\sigma \in Sym(X), d \in D, g \in G$ (my conventions: $Sym(X)$ acts on $X$ from the right, so acts on $D$ and $G$ from the left; $G$ acts on $D$ from the right). 2.) An instance of the last sentence, sufficient to see nontriviality of the action, is where $X = \{1,2,\dots,n\}$, $(i,j) = (1,2)$, and $d$ is the standard order. | |
| Mar 9, 2022 at 14:48 | comment | added | Sam Hopkins | I think this one is "the" answer. | |
| Mar 9, 2022 at 8:10 | comment | added | R. van Dobben de Bruyn | Neat! Like my answer, this acknowledges the $S_2$-torsor $X^2 \setminus \Delta_X \to {X \choose 2}$ as the key object. But curiously, it doesn't quite generalise to the setting of my lemma, as the final $\{\pm 1\}$ somehow relies on the coincidence $\operatorname{Sym}(\{\pm 1\}) \cong \{\pm 1\}$. (This may well be a feature and not a bug.) | |
| Mar 9, 2022 at 4:24 | comment | added | Bjorn Poonen | This could be considered the "combinatorial core" of the polynomial argument mentioned by David Speyer. It has the advantage of avoiding "external" ingredients like multivariable polynomials, topology, etc. No computation is needed to construct the homomorphism. (Computation is needed only to check that it is nontrivial, but that is very easy, as explained in the last sentence above.) | |
| Mar 9, 2022 at 4:15 | history | answered | Bjorn Poonen | CC BY-SA 4.0 |