3
$\begingroup$

When teaching abstract algebra for undergrads, I taught them that there is a permutation group $S(A)$ of automorphisms on any set $A$, and then defined the group $S_n$ to be the group of permutations of the set $\{1,\dots, n\}.$ Later in the semester I regretted it: when writing down cycles (and using cycle notation in general), you want the indices to be modulo some integer: so I wrote cycles of length $n$ as $(x_0, \dots, x_{n-1}),$ which was confusing.

The "pythonic" philosophy holds that the set $\{0, \dots, n-1\}$ is better behaved than the set $\{1,\dots, n\},$ and from a purely ease of notation perspective I think it would be better to define $S_n$ as permutations of $\{0. \dots, n-1\}$. Another consideration that makes this notation potentially better is that the group $D_n$ embeds naturally in $S_n$ as permutations of angles of the $n$-gon, which are indexed $\big\{0\cdot \frac{2\pi}{n},\dots, (n-1)\cdot \frac{2\pi}{n}\big\}$. On the other hand, this notation feels less intuitive and is less standard, not to mention that the book I'm using (Fraleigh, which has multiple chapters on permutation groups) uses $\{1,\dots, n\}.$

I am teaching the same course again and am debating switching. Have people considered this or tried this in their teaching, and what are the main pros/cons?

$\endgroup$
  • 6
    $\begingroup$ This is not on-topic here. Maybe you should try matheducators.stackexchange.com $\endgroup$ – rschwieb Dec 14 '18 at 15:29
  • 1
    $\begingroup$ @DmitryVaintrob It's not a question of level, it's a question of topic. This forum is less oriented toward opinion-based questions and more toward questions that contain actual mathematics. Referring you to matheducators is doing you a favor so that you get help from the people keenest on giving advice on this topic. $\endgroup$ – rschwieb Dec 14 '18 at 15:44
  • 1
    $\begingroup$ While matheducators might be better suited for that question, that doesn't necessarily mean it's off-topic here. $\endgroup$ – Arnaud D. Dec 14 '18 at 15:49
  • 3
    $\begingroup$ @DmitryVaintrob What made you decide your question about teaching undergraduates did not fit at a site which "welcomes general questions related to teaching provided that they are relevant to teaching mathematics." ? $\endgroup$ – rschwieb Dec 14 '18 at 16:19
  • 3
    $\begingroup$ How is this "pythonic"? Seems like more of a CS vs math thing. Python is simple too much of a newcomer to logically lend its name to something like this. $\endgroup$ – Tobias Kildetoft Dec 15 '18 at 21:58
2
$\begingroup$

In my opinion, it is a serious mistake to think that only one of 1-based or 0-based indexing is the best one, even in the programming world, not to say the mathematics world. Each scenario has its own structure that should guide you to the most natural choice of indexing scheme:

  • If you have an initial state, it is natural to start at index $0$. This includes a sequence $x[0..n]$ where $x[k]$ is the state after $k$ steps of some process.

  • If you are labelling $n$ objects, it is almost always most convenient to use labels $[1..n]$, unless the labels somehow have more meaning than just labels.

In your case, your underlying set just needs $n$ labels, so $[1..n]$ works just fine. A cycle can indeed be thought of as a length-$n$ sequence modulo rotation, which favours the choice of $(x_0,x_1,\cdots,x_{n-1})$. But I am kind of doubtful that there is any serious inelegance in using $(x_1,x_2,\cdots,x_n)$. If there is some theorem where one indexing seems more natural than the other, simply use that.

There is no such thing as a "more Pythonic indexing scheme". You cannot imagine how many times when coding in Python I cringed because I wanted to say for i in [0..n] but had to use for i in range(n+1) just because ... and wanted to say for i in [1..n] and had to use for i in range(n) and have +1s all over.

$\endgroup$
  • $\begingroup$ You know, range in python doesn't have to start at 0. $\endgroup$ – Matt Samuel Dec 20 '18 at 11:12
  • $\begingroup$ @MattSamuel: Yes, and you'd rather use range(1,n+1)? $\endgroup$ – user21820 Dec 20 '18 at 13:03
  • $\begingroup$ Certainly it's preferable to adding 1 everywhere the index is used. $\endgroup$ – Matt Samuel Dec 20 '18 at 13:07
  • $\begingroup$ @MattSamuel: Of course if there are more than a few, I would do that, but the point remains that Python does not permit me to express exactly what I want. I do not like having a +1 anywhere that does not make explicit sense. $\endgroup$ – user21820 Dec 20 '18 at 15:08
2
$\begingroup$

I work extensively with $S_n$, and I strongly prefer indexing beginning at $1$. I also program quite a bit, and I wrap permutations in classes that make them start at $1$ as well. Programming is actually something I began first, as a child, yet the $1$-based indexing still seems preferable to me.

Likely the reason is that so many things in mathematics begin at $1$, and shifting everything to begin at $0$ leads to error when the $1$-based indexing is already well established. Computer scientists hardly use groups, the vast majority of them don't even know what they are, and the reason for $0$-based indexing is so that the array index is the address offset. There's really no other reason. Counting generally begins at $1$, it is an oddity of computing that we have them begin at $0$.

$0$ is useful to have be part of $\mathbb{N}$ in my experience, but seeing it in a permutation grates on my nerves, although of course it's perfectly correct if that is the set you choose $S_n$ to act on. If you want to take indices modulo some integer, that's not necessarily a reason to start at $0$. $\{1,\ldots,n\}$ is also a complete set of residues modulo $n$, you've just replaced $0$ with $n$.

The only time I've used $0$-based indexing for permutations is when I needed extremely rapid computation that had to use as little memory as possible, where instead of representing a permutation as an array I represented them by their index in lexicographical order. You can see the code here: https://codereview.stackexchange.com/questions/182610/computing-the-number-of-primitive-sorting-networks-on-n-elements-seeking-tiny

$\endgroup$
  • 2
    $\begingroup$ I share the sentiment (+1). There have been occasions when I wanted to start from zero. Affine permutations of $\Bbb{Z}/p\Bbb{Z}$ sprang to my mind also. Anyway, with the cycle notation in place, the set being acted on by the permutations loses some of its relevance. Another point in favor of $\{1,2,\ldots,n\}$ is that we index the rows and columns of a matrix with that set also, and permutations are soon represented by matrices. Of course, nothing stops us from C-style indexing of matrices also. $\endgroup$ – Jyrki Lahtonen Dec 14 '18 at 20:20
  • 1
    $\begingroup$ @Jyrki There was actually a situation recently where I wrote a program to compute Littlewood-Richardson coefficients for the complete flag variety and thought it would be fine to start the permutations at $0$. Then as I was examining the results I would be like... "This doesn't make sense, why is there a $7$ there when it should be $8$?" Then I realized it was $8$ because I started at $0$. After making that mistake a few times I changed the indexing to maintain my sanity. $\endgroup$ – Matt Samuel Dec 14 '18 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.