Opened 5 years ago

Closed 5 years ago

#15439 closed defect (fixed)

sage/combinat/matrices/latin.py: isotopism method uses product of permutations

Reported by: darij Owned by:
Priority: major Milestone: sage-6.2
Component: combinatorics Keywords: permutation, combinat, latin square
Cc: ncohen, sage-combinat, nthiery, fhivert Merged in:
Authors: Nathann Cohen Reviewers: Darij Grinberg
Report Upstream: N/A Work issues:
Branch: u/ncohen/15439 (Commits) Commit: 400bdc1a102cedffd2170e5d21deebd11ec5b9ed
Dependencies: Stopgaps:

Description

From sage/combinat/matrices/latin.py:

def isotopism(p):
    """
    Returns a Permutation object that represents an isotopism (for
    rows, columns or symbols of a partial latin square). Since matrices
    in Sage are indexed from 0, this function translates +1 to agree
    with the Permutation class. We also handle
    PermutationGroupElements.
[...]
                x = x * isotopism(p[i])
[...]

This uses the syntax a * b for the product of two permutations. This syntax is bad because its semantics depends on the state of a global variable (mult in Permutation.global_options()), which decides which of the factors is to be applied first when multiplying two permutations. I don't know if it matters for this particular method, but such things have been causing subtle bugs in two other places, so this should be looked at (unfortunately I don't know much about Latin squares; Nathann?). Even if the result doesn't depend on the order of multiplication, it is better to use the _left_to_right_multiply_on_left and _left_to_right_multiply_on_right methods of class sage.combinat.permutation.Permutation for speed reasons (they don't waste time looking up the state of that global variable).

See also #15174.

Change History (19)

comment:1 follow-up: Changed 5 years ago by ncohen

  • Cc nthiery fhivert added

Hellooooooooooooooo !!!!

1) I did not know what an isotopism was either, and it looks like we could add a link toward the following Wikipedia page if we patch this file : http://en.wikipedia.org/wiki/Latin_square#Equivalence_classes_of_Latin_squares

2) "Morally", this '*' can be any of the two actions, as it should only apply to permutations with disjoint supports : this part of the function builds a permutation from a 'cycles notation', i.e. '(1,2,3)(4,5)'. It builds a permutation for each cycle and multiplies the results, so both actions should be fine.

3) Morally, this part of the code is made for disjoint cycles notations, but nothing actually checks that. And given a permutation in cycle notation (as a string) '(1,2,3)(4,5)', don't you have the very same problem knowing in which order they should be applied ? Or is that clear for everybody ? I honestly ask the question, I personally always used permutations like function composition, and all that happens with this left/right action is beyond me :-P

4) This code has *NOTHING* to do there. Its only purpose is to accept any kind of permutation input on 0..n-1 and to output a permutation on 1..n. It's like this code should appear in the constructor of Permutations, with a flag translate_from_0n_to_1n=True

5) Having something like Permutations.global_options which redefines the meaning of '*' is *criminal*.

a) How the hell can such a thing be implemented when there is a ticket like this one, which PROVES that some parts of Sage's code use the '*' on multiplications, and that those functions could return WRONG RESULTS when this flag is changed ?

b) And how can such a thing can be implemented WITHOUT MAKING SURE that no '*' can appear again on permutation code in Sage ?

Nathann

comment:2 in reply to: ↑ 1 ; follow-up: Changed 5 years ago by darij

Hi Nathann,

Replying to ncohen:

4) This code has *NOTHING* to do there. Its only purpose is to accept any kind of permutation input on 0..n-1 and to output a permutation on 1..n. It's like this code should appear in the constructor of Permutations, with a flag translate_from_0n_to_1n=True

Good point. I'm not sure if I want to add a translate_from_0n_to_1n variable to the Permutation constructor (that constructor is already quite complex, and it gets called a hell lot). But maybe we should add a function to sage/combinat/permutation.py which constructs a permutation from its "left shift by 1"?

1) I did not know what an isotopism was either, and it looks like we could add a link toward the following Wikipedia page if we patch this file : http://en.wikipedia.org/wiki/Latin_square#Equivalence_classes_of_Latin_squares

+1 for the link. It just doesn't have much to do with the isotopism method; it probably should be in the apply_isotopism docstring.

2) "Morally", this '*' can be any of the two actions, as it should only apply to permutations with disjoint supports : this part of the function builds a permutation from a 'cycles notation', i.e. '(1,2,3)(4,5)'. It builds a permutation for each cycle and multiplies the results, so both actions should be fine.

OK, good point -- it seems that the isotopism method is indeed meant to take disjoint cycles, whence the order is irrelevant. But I'm saying "seems" because to me, too, it's far from clear from the docstring. If we can confirm than this is what's meant, it should be rather easy to avoid the use of * and probably even gain some speed this way.

3) Morally, this part of the code is made for disjoint cycles notations, but nothing actually checks that. And given a permutation in cycle notation (as a string) '(1,2,3)(4,5)', don't you have the very same problem knowing in which order they should be applied ? Or is that clear for everybody ? I honestly ask the question, I personally always used permutations like function composition, and all that happens with this left/right action is beyond me :-P

For quite a long time I believed that everyone agreed pq would mean "first do q, then p", apart from maybe some 19th century British authors (who would be unreadable anyway). But it turned out that the opposite convention is still around in Britain :(

5) Having something like Permutations.global_options which redefines the meaning of '*' is *criminal*.

The global_options constructor is just a new way to handle these global variables, but the global variable determining order of multiplication is not new. I guess it's nuclear waste from the olden days of Sage.

In #15174 it surfaced that with Permutations.global_options(mult) == 'l2r', the Hecke algebra (a deformation of the symmetric group algebra) would have its multiplication opposite of that of the symmetric group algebra, whereas with Permutations.global_options(mult) == 'r2l' it would not be an algebra at all (associativity would not hold). I believe this has been around for ages. You've gotta love our codebase...

Greets,
Darij

Last edited 5 years ago by darij (previous) (diff)

comment:3 in reply to: ↑ 2 Changed 5 years ago by ncohen

Yoooooooooooo !!

Good point. I'm not sure if I want to add a translate_from_0n_to_1n variable to the Permutation constructor (that constructor is already quite complex, and it gets called a hell lot). But maybe we should add a function to sage/combinat/permutation.py which constructs a permutation from its "left shift by 1"?

Well... I'd say that having this exposed in the constructor would be cool, considering that I don't even get why the permutations are on 1..n in the first place. Accepting them on a 0..n-1 input, even to only return a 1..n one would be cool. But I tried to put some sense into what's happening in the combinat/ folder, and each time it crashes on a

1) We will do it some day

2) It's a good idea but it makes existing code slower (#14019 is in this case, though wrong results are actually returned in the meantime)

3) I have to ask XXXX, which never happens

So, well. Even though the only sensible thing would be to support at least both 0..n-1 and 1..n (why not LABELLED permutations btw ? Like PermutationGroupElement? already does ?). Even though the slightly less sensible thing would be to give this up but to be able to relabel them from the constructor, I think I can't hope for anything better than having a relabeling function that I could import and use manually.

+1 for the link. It just doesn't have much to do with the isotopism method; it probably should be in the apply_isotopism docstring.

Right, right.

OK, good point -- it seems that the isotopism method is indeed meant to take disjoint cycles, whence the order is irrelevant. But I'm saying "seems" because to me, too, it's far from clear from the docstring. If we can confirm than this is what's meant, it should be rather easy to avoid the use of * and probably even gain some speed this way.

Oh, I'm pretty sure that this is what is meant there. Of course nothing checks it (we are in the combinat/ folder after all) but it was done in the very same way in the constructor of permutations before #13742.

For quite a long time I believed that everyone agreed pq would mean "first do q, then p", apart from maybe some 19th century British authors (who would be unreadable anyway). But it turned out that the opposite convention is still around in Britain :(

HMmmmmmmmm >_<

The global_options constructor is just a new way to handle these global variables, but the global variable determining order of multiplication is not new. I guess it's nuclear waste from the olden days of Sage.

In #15174 it surfaced that with Permutations.global_options(mult) == 'l2r', the Hecke algebra (a deformation of the symmetric group algebra) would have its multiplication opposite of that of the symmetric group algebra, whereas with Permutations.global_options(mult) == 'r2l' it would not be an algebra at all (associativity would not hold). I believe this has been around for ages. You've gotta love our codebase...

Nightmares. Nightmares. Why don't we have "permutations acting on right" and "permutations acting on the left" then ? And get rid of a flag that might break dozens of functions without anybody knowing ?

Nathann

comment:4 Changed 5 years ago by ncohen

  • Authors set to Nathann Cohen
  • Branch set to u/ncohen/15439
  • Status changed from new to needs_review

Hello ! I tried twice to update the constructor of Permutation to add a shift_input_by_one=False flag, but each time it convinced me that it was bad work. Plus I don't think that this is the good way out -- the good way out is to have permutations on arbitrary objects.

Hence I did not touch permutation.py. Err, I just changed a few calls to all() to prevent them from building a long useless list of [False, False, False, False]. And I wrote the doc of this isotopism thing, and avoided this * on multiplications.

But honestly, I think you have no way to ensure that nobody will ever use this * in Sage code without worrying over this multiplication order.

Nathann

comment:5 Changed 5 years ago by git

  • Commit set to a1b05a808faf8052618f31f2eebd855082b7da29

Branch pushed to git repo; I updated commit sha1. New commits:

a1b05a8trac #15439: combinat.matrices.latin.isotopism should not use '*' on permutations

comment:6 Changed 5 years ago by darij

  • Branch changed from u/ncohen/15439 to u/darij/ticket/15439
  • Created changed from 11/20/13 03:53:44 to 11/20/13 03:53:44
  • Modified changed from 12/05/13 11:20:12 to 12/05/13 11:20:12

comment:7 Changed 5 years ago by darij

  • Branch changed from u/darij/ticket/15439 to u/ncohen/15439

Review patch uploaded. I'd rather have put it into the public namespace, but I've forgotten how to do that using the dev scripts (and if I use git manually, how do I reset the Branch field on the ticket?).

I put back one newline you removed since I found it reasonable.

meld seems to do creepy stuff; I have checked the sanity of the merge manually using diff.

Last edited 5 years ago by darij (previous) (diff)

comment:8 Changed 5 years ago by darij

  • Branch changed from u/ncohen/15439 to u/darij/ticket/15439
  • Modified changed from 12/10/13 08:02:20 to 12/10/13 08:02:20

comment:9 Changed 5 years ago by ncohen

  • Commit changed from a1b05a808faf8052618f31f2eebd855082b7da29 to b484c8a59a690c0232097e4ae40ef58c6e813837

Hmmmmmm... The git history looks rather painful indeed :-P

Why this "pre-empting" patch ? And I didn't know anything about meld, though git merge does the job for me at the moment... :-P

Do you want to torture this branch further or can we set it to positive_review ? :-PPPPP

Nathann


New commits:

b484c8atypo fixes
752f72ffixing merge errors
b5eb9e4manual merge
20ca024pre-empting Nathann's changes to permutation.py so as to make the merge less painful

comment:10 Changed 5 years ago by darij

  • Milestone changed from sage-5.13 to sage-6.0
  • Status changed from needs_review to positive_review

Well, the edits to permutation.py conflicted with my patch that was merged into beta5. So there was some merging involved. But apparently I cannot trust meld, since I tell it to merge all changes from the left version and it does not, in fact, merge all changes from the left version. (That or I did something wrong.)

I guess it's positive_review then?

comment:11 Changed 5 years ago by ncohen

HMmmmmm... Actually I would be quite glad to rewrite this branch and make it cleaner. Would it be fine if I just take my old branch, add your typo fixes into it, with all this atop beta5 ?

Nathann

comment:12 follow-up: Changed 5 years ago by darij

I won't mind... I hope noone hangs on this branch now (is there a good way to find this out at least for branches on the trac server?).

comment:13 in reply to: ↑ 12 Changed 5 years ago by ncohen

  • Branch changed from u/darij/ticket/15439 to u/ncohen/15439
  • Commit changed from b484c8a59a690c0232097e4ae40ef58c6e813837 to 400bdc1a102cedffd2170e5d21deebd11ec5b9ed

Yooooooooo !

Here is a new updated branch. Is that good for you ?

I won't mind... I hope noone hangs on this branch now (is there a good way to find this out at least for branches on the trac server?).

Ahahahah. No, I don't think that there is. That's one of the big problems with git. Perhaps this will make people review patches quicker, who knows ? Perhaps they will be merged faster, too. I even wonder if we will still have releases, or if a "git pull" will do the job :-)

If you like the new branch, please set the ticket to positive_review.

Thaaaaaaaaaaaaanks !

Nathann


New commits:

400bdc1trac #15439: typo fixes
4db468ctrac #15439: combinat.matrices.latin.isotopism should not use '*' on permutations

comment:14 Changed 5 years ago by darij

Looks good and tests well. positive_review is right. Thanks!

comment:15 Changed 5 years ago by ncohen

Thaaaaaaaaaanks !

Nathann

comment:16 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:17 Changed 5 years ago by vbraun

  • Reviewers set to Darij Grinberg

comment:18 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:19 Changed 5 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.