Bug in poset

[Trevor Karn]

Hi all,

I was wondering if anyone can reproduce this bug with Poset creation. I create a Poset by passing the elements and the comparison function as a tuple (elements, func) and a pair of elements for which func(x,y) returns True has P.lequal(x,y) returning False

I'm trying to create the subgroup lattice up to conjugacy of S5.

sage: load('s5-subgroup.sage')  # builds poset, see below
sage: groups[-2]
Permutation Group with generators [(1,2,3), (1,2,3,4,5)]
sage: groups[-1]
Permutation Group with generators [(1,2), (1,2,3,4,5)]
sage: compare(groups[-2], groups[-1])
True
sage: P.is_lequal('A5','S5')
False

The content of 's5-subgroup.sage' is below.

gens = [
        [[]],  # trivial
        [[(1,2)]],  # S2
        [[(1,2),(3,4)]],  #z/2
        [[(1,2)],[(3,4)]],  # disjoint V4
        [[(1,2),(3,4)],[(1,3),(2,4)]],  # double transp V4
        [[(1,2,3,4)]],  # z/4
        [[(1,2,3,4)],[(1,3)]],  # D8 (D4 in GAP notation)
        [[(1,2,3)]],  # z/3
        [[(1,2,3)],[(4,5)]],  # z/6
        [[(1,2,3)],[(1,2)]],  # S3
        [[(1,2,3)],[(1,2),(4,5)]],  # twisted S3
        [[(1,2,3)],[(1,2)],[(4,5)]],  # S3 x S2
        [[(1,2),(3,4)],[(1,2,3)]],  # A4
        [[(1,2,3,4)],[(1,2)]],  # S4
        [[(1,2,3,4,5)]],  # z/5
        [[(1,2,3,4,5)],[(2,5),(3,4)]],  # D10
        [[(1,2,3,4,5)],[(2,3,4,5)]],  # GA(1,5)
        [[(1,2,3,4,5)],[(1,2,3)]],  # A5
        [[(1,2,3,4,5)],[(1,2)]]  # S5
        ];

strs = ['1', 'S2', 'Z/2', 'V4', 'V4 (dbl)', 'Z/4', 'D8',
        'Z/3', 'Z/6', 'S3', 'S3 (twist)', 'S3xS2',
        'A4', 'S4', 'Z/5', 'D10', 'GA(1,5)', 'A5',
        'S5']

to_group = lambda x: PermutationGroup(gens=x);
groups = list(map(to_group, gens));
compare = lambda x, y: x.is_subgroup(y);
P = Poset(data=(groups, compare), element_labels=strs)

[dmo...@deductivepress.ca]

I confirm the error: P.maximal_elements() contains S5 and A5.

As a possibly minimal example, it suffices to use only the last 3 groups: I also see the error with

P = Poset(data=(groups[16:], compare), element_labels=strs[16:]). 

Please open a ticket.

[Trevor Karn]

At least part of the problem is that I gave bad generators for GA(1,5). It should be [[(1,2,3,4,5)],[(2,3,5,4)]].

[Trevor Karn]

Thanks for the confirmation. I'll double check this is not a logic bug before I open a ticket.

[dmo...@deductivepress.ca]

P erroneously thinks that GA(1,5) is less than A5.  I have no idea what's causing that either.

[Dima Pasechnik]

No, no bug (yet).

The problem is that you are not careful constructing the correct subgroups to use.

E.g. if you want groups[2] to be a subgroup of groups[5]=<(1,2,3,4)>

you must take groups[2]=<(1,3)(2,4)>, not groups[2]=<(1,2)(3,4)>.

You can start with the maximal subgroups of S_5, and intersect them, then intersect the intersections, etc.

Or you can rewrite your compare(a,b) in terms of "an element of the conjugacy class of subgroups with `b`

a representative contained in `a`"

E.g. using libgap:

sage: groups[-1]._libgap_().ConjugacyClassSubgroups(groups[1]._libgap_()).Elements()
[ Group([ (4,5) ]), Group([ (3,4) ]), Group([ (3,5) ]), Group([ (2,3) ]), Group([ (2,4) ]), Group([ (2,5) ]), Group([ (1,2) ]), Group([ (1,3) ]), Group([ (1,4) ]), Group([ (1,5) ]) ]

But this might well be a different poset, as once you fixed just one maximal subgroup H_1, the conjugacy class of the 2nd maximal subgroup H_2

might already be splitting into different orbits w.r.t. conjugaction by H_1, so potentially different choices, etc...

HTH

Dima

[Trevor Karn]

Thanks Dima. I certainly agree that there is a mathematical error with my approach. I'm wondering if there is still a bug since the result of compare(x,y) and P.islequal(x,y) differ. Shouldn't they be the same, even if I am giving them bad input?

Best Regards,

Trevor Karn

--
You received this message because you are subscribed to a topic in the Google Groups "sage-devel" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-devel/x0ioULPipfE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sage-devel+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/9ee1e630-2657-46ce-956e-3e0f49f8814an%40googlegroups.com.