Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Slow conjugacy test of subgroups in natural symmetric group #3718

Open
DominikBernhardt opened this issue Oct 29, 2019 · 16 comments
Open

Slow conjugacy test of subgroups in natural symmetric group #3718

DominikBernhardt opened this issue Oct 29, 2019 · 16 comments
Labels
topic: library topic: performance bugs or enhancements related to performance (improvements or regressions)

Comments

@DominikBernhardt
Copy link
Contributor

DominikBernhardt commented Oct 29, 2019 •
edited by fingolfin
Loading

The call IsConjugate(sym,g,h), where sym, g and h are as below is extremely slow in GAP, I cancelled the calculation after 10 minutes or so. Magma handles this in less then a second.
Maybe @hulpke has an idea about this?

difficult-conjugation.txt
@DominikBernhardt DominikBernhardt added topic: performance bugs or enhancements related to performance (improvements or regressions) topic: library labels Oct 29, 2019
@hulpke
Copy link
Contributor

hulpke commented Oct 29, 2019

The only thing I noted is that the special code for the symmetric group reduces nicely to conjugacy in a (much smaller) group of degree 375. Then that smaller backtrack search takes its time.

@DominikBernhardt
Copy link
Contributor Author

Thanks @hulpke . So It comes done to the backtrack, which means this is nothing one can improve quickly.

@ChrisJefferson
Copy link
Contributor

ChrisJefferson commented Nov 13, 2019 •
edited
Loading

Just checking, what's the answer, are they conjugate (and if they are, what's a permutation that conjugates one to the other)

@DominikBernhardt
Copy link
Contributor Author

@ChrisJefferson Yes they are:
pi:=(4, 8)(5, 9)(6, 7)(13, 17)(14, 18)(15, 16)(22, 26)(23, 27)(24, 25)(28, 392, 34, 389, 31, 395)(29, 394, 35, 391, 32, 388)(30, 390, 36, 396, 33, 393)(37, 169, 44, 166, 42, 163)(38, 167, 45, 164, 40, 170)(39, 165, 43, 171, 41, 168)(49, 53)(50, 54)(51, 52)(55, 261, 61, 256, 58, 254)(56, 255, 62, 259, 59, 257)(57, 258, 63, 253, 60, 260)(64, 815, 70, 812, 67, 818)(65, 817, 71, 814, 68, 811)(66, 813, 72, 819, 69, 816)(73, 177, 80, 174, 78, 180)(74, 172, 81, 178, 76, 175)(75, 179, 79, 176, 77, 173)(82, 262)(83, 263)(84, 264)(85, 269)(86, 270)(87, 268)(88, 267)(89, 265)(90, 266)(94, 98)(95, 99)(96, 97)(100, 802, 107, 808, 105, 805)(101, 809, 108, 806, 103, 803)(102, 807, 106, 804, 104, 810)(109, 131, 115, 128, 112, 134)(110, 133, 116, 130, 113, 127)(111, 129, 117, 135, 114, 132)(118, 1085)(119, 1084)(120, 1086)(121, 1082)(122, 1081)(123, 1083)(124, 1088)(125, 1087)(126, 1089)(136, 138, 142, 144, 139, 141)(137, 140, 143)(145, 448, 152, 445, 150, 442)(146, 446, 153, 443, 148, 449)(147, 444, 151, 450, 149, 447)(154, 331, 161, 328, 159, 325)(155, 329, 162, 326, 157, 332)(156, 327, 160, 333, 158, 330)(181, 505)(182, 506)(183, 507)(184, 512)(185, 513)(186, 511)(187, 510)(188, 508)(189, 509)(190, 466, 197, 463, 195, 460)(191, 464, 198, 461, 193, 467)(192, 462, 196, 468, 194, 465)(199, 621, 205, 616, 202, 614)(200, 615, 206, 619, 203, 617)(201, 618, 207, 613, 204, 620)(208, 901, 214, 907, 211, 904)(209, 906, 215, 903, 212, 909)(210, 908, 216, 905, 213, 902)(217, 923, 224, 920, 222, 926)(218, 921, 225, 927, 220, 924)(219, 925, 223, 922, 221, 919)(226, 606, 233, 610, 231, 608)(227, 612, 234, 607, 229, 605)(228, 609, 232, 604, 230, 611)(235, 1046)(236, 1047)(237, 1045)(238, 1053)(239, 1051)(240, 1052)(241, 1048)(242, 1049)(243, 1050)(244, 356, 251, 354, 249, 358)(245, 353, 252, 360, 247, 355)(246, 359, 250, 357, 248, 352)(271, 274, 277)(272, 279, 278, 276, 275, 273)(280, 1039, 287, 1037, 285, 1044)(281, 1036, 288, 1043, 283, 1041)(282, 1042, 286, 1040, 284, 1038)(289, 424, 296, 431, 294, 429)(290, 430, 297, 428, 292, 426)(291, 427, 295, 425, 293, 432)(298, 299, 305, 306, 303, 301)(300, 302, 304)(307, 1097)(308, 1096)(309, 1098)(310, 1094)(311, 1093)(312, 1095)(313, 1091)(314, 1090)(315, 1092)(316, 1009)(317, 1011)(318, 1010)(319, 1015)(320, 1017)(321, 1016)(322, 1012)(323, 1014)(324, 1013)(334, 379, 341, 385, 339, 382)(335, 386, 342, 383, 337, 380)(336, 384, 340, 381, 338, 387)(343, 1074, 350, 1078, 348, 1076)(344, 1080, 351, 1075, 346, 1073)(345, 1077, 349, 1072, 347, 1079)(361, 368, 367, 365, 364, 362)(363, 366, 369)(370, 733)(371, 734)(372, 735)(373, 731)(374, 732)(375, 730)(376, 738)(377, 736)(378, 737)(397, 399, 403, 405, 400, 402)(398, 401, 404)(406, 678, 412, 682, 409, 680)(407, 681, 413, 676, 410, 683)(408, 684, 414, 679, 411, 677)(415, 422, 421, 419, 418, 416)(417, 420, 423)(433, 539, 440, 537, 438, 532)(434, 536, 441, 534, 436, 538)(435, 533, 439, 540, 437, 535)(451, 1065)(452, 1064)(453, 1063)(454, 1071)(455, 1070)(456, 1069)(457, 1068)(458, 1067)(459, 1066)(469, 689)(470, 690)(471, 688)(472, 687)(473, 685)(474, 686)(475, 691)(476, 692)(477, 693)(478, 1004, 484, 1001, 481, 1007)(479, 1006, 485, 1003, 482, 1000)(480, 1002, 486, 1008, 483, 1005)(487, 579, 493, 583, 490, 581)(488, 582, 494, 577, 491, 584)(489, 585, 495, 580, 492, 578)(496, 748, 502, 754, 499, 751)(497, 753, 503, 750, 500, 756)(498, 755, 504, 752, 501, 749)(514, 833, 521, 831, 519, 835)(515, 830, 522, 837, 517, 832)(516, 836, 520, 834, 518, 829)(523, 568, 530, 574, 528, 571)(524, 575, 531, 572, 526, 569)(525, 573, 529, 570, 527, 576)(541, 894)(542, 893)(543, 892)(544, 900)(545, 899)(546, 898)(547, 897)(548, 896)(549, 895)(550, 839, 557, 846, 555, 841)(551, 845, 558, 843, 553, 838)(552, 842, 556, 840, 554, 844)(559, 563)(560, 564)(561, 562)(586, 930, 593, 934, 591, 932)(587, 936, 594, 931, 589, 929)(588, 933, 592, 928, 590, 935)(595, 598, 601)(596, 603, 602, 600, 599, 597)(622, 871, 628, 869, 625, 867)(623, 865, 629, 872, 626, 870)(624, 868, 630, 866, 627, 873)(631, 739)(632, 741)(633, 740)(634, 745)(635, 747)(636, 746)(637, 742)(638, 744)(639, 743)(640, 647, 646, 644, 643, 641)(642, 645, 648)(649, 652, 655)(650, 657, 656, 654, 653, 651)(658, 659, 665, 666, 663, 661)(660, 662, 664)(667, 668, 674, 675, 672, 670)(669, 671, 673)(694, 695, 701, 702, 699, 697)(696, 698, 700)(703, 966)(704, 964)(705, 965)(706, 970)(707, 971)(708, 972)(709, 968)(710, 969)(711, 967)(712, 881)(713, 880)(714, 882)(715, 878)(716, 877)(717, 879)(718, 875)(719, 874)(720, 876)(721, 914)(722, 913)(723, 915)(724, 911)(725, 910)(726, 912)(727, 917)(728, 916)(729, 918)(757, 1110, 764, 1114, 762, 1112)(758, 1116, 765, 1111, 760, 1109)(759, 1113, 763, 1108, 761, 1115)(766, 767, 773, 774, 771, 769)(768, 770, 772)(775, 1101)(776, 1100)(777, 1099)(778, 1107)(779, 1106)(780, 1105)(781, 1104)(782, 1103)(783, 1102)(784, 788)(785, 789)(786, 787)(793, 800, 799, 797, 796, 794)(795, 798, 801)(820, 960, 826, 955, 823, 962)(821, 963, 827, 958, 824, 956)(822, 957, 828, 961, 825, 959)(847, 853, 854, 851, 852, 849)(848, 850, 855)(856, 1055, 863, 1062, 861, 1057)(857, 1061, 864, 1059, 859, 1054)(858, 1058, 862, 1056, 860, 1060)(883, 1119)(884, 1118)(885, 1117)(886, 1125)(887, 1124)(888, 1123)(889, 1122)(890, 1121)(891, 1120)(937, 943, 944, 941, 942, 939)(938, 940, 945)(946, 998, 953, 995, 951, 992)(947, 996, 954, 993, 949, 999)(948, 991, 952, 997, 950, 994)(973, 986, 979, 984, 976, 988)(974, 989, 980, 987, 977, 982)(975, 983, 981, 990, 978, 985)(1018, 1019, 1025, 1026, 1023, 1021)(1020, 1022, 1024)(1027, 1028, 1034, 1035, 1032, 1030)(1029, 1031, 1033);
does the trick.

@wilfwilson
Copy link
Member

wilfwilson commented Nov 29, 2019 •
edited
Loading

@ChrisJefferson and I have been looking into this. For a permutation group G <= Sn, the normaliser of G in Sn is contained in the stabiliser in Sn of the set of orbital graphs of G. We can compute this stabiliser using the Digraphs and OrbitalGraphs packages. In the case of g and h, we're lucky and this stabiliser is actually equal to the normaliser. Moreover, we can get an element (via the canonical image of some relevant digraph graphs...) that conjugates g to h.

Thus, with some code that I wrote today, I solved the problem in GAP in about 1.5 seconds on my computer. It's not a strategy that will work in every case, but it works in this one.

We'll look into what we can do about this, and our ideas.

@DominikBernhardt
Copy link
Contributor Author

@wilfwilson and @ChrisJefferson Thanks! I have a lot of examples in which the conjugacy is slow. If you want, I can provide them to you via Mail oder Slack as well as the construction form which they arise?

@wilfwilson
Copy link
Member

Yes, please do 🙂 Email would be better for me, because of its permanence.

@DominikBernhardt
Copy link
Contributor Author

DominikBernhardt commented Jul 21, 2020 •
edited by hulpke
Loading

There is a much smaller example on 31 points I can give you:
G := Group([ (2,5,4,3)(6,11,16,21)(7,15,19,23)(8,12,20,24)(9,13,17,25)(10,14,18,22)(27,29)(28,30), (1,26,4,6,9,23,8,17,13,28,5,21,14,12,10,15,18,25,30,2,16,19,29,31)(3,11,24,20,7,27) ]); H := Group([ (1,4,29,2)(3,30,18,20)(5,19,26,10)(6,13)(7,8,27,31)(9,28,24,16)(12,22)(14,21,17,23), (1,16,12,31,26,19,5,18,2,23,9,13,8,20,14,10,30,29,28,22,15,25,11,27)(3,21,24,6,7,17) ]);
Magma finds out that these groups are conjugate in less than a second using the permutation (3,9,11,28,23)(4,7, 25,26,8,12, 21,5,10,22,18,29,17,19,27,16)(13,20,24,15,14,31). I stoped the GAP computation after about 15 minutes..

@DominikBernhardt DominikBernhardt changed the title Slow conjugacy test of subgroups of SymmetricGroup(1125) Slow conjugacy test of subgroups in natural symmetric group Jul 21, 2020
@hulpke
Copy link
Contributor

hulpke commented Jul 21, 2020 •
edited
Loading

Just as brief note on the deg 31 example: This is purely a backtrack issue, as the groups are doubly transitive of degree 31. I suspect that no reduction strategy is available.

Even curiouser, the following (not recommended as general!) conjugacy test takes seconds at worst:

gap> iso:=IsomorphismGroups(G,H);
[ (6,7,8,10,9)(11,13,14,12,15)(16,19,20,18,17)(21,25,22,24,23)(26,29,30,28,27)
    , (1,5,17,25,21)(2,30,28,22,16)(3,13,8,23,26)(4,24,11,31,6)(7,12,9,20,
    14)(10,29,19,27,15) ] ->
[ (3,5,26,18,15)(4,27,24,29,19)(6,25,12,22,11)(8,17,30,23,16)(14,28,20,31,21),
  (1,22,26,13,16)(2,7,20,25,6)(3,23,14,15,8)(4,27,12,31,9)(5,30,19,21,24)(10,
    18,17,11,29) ]
gap> time;
394
gap> s:=Stabilizer(G,1);
Group([ (2,13,31,25)(3,29)(4,7,5,19)(6,20,11,22)(8,26,30,16)(9,15,23,27)
  (12,24,18,28)(14,21), (2,7,28,9,6,22,5,13,10,15,11,30,4,25,12,23,21,8,3,29,
   24,27,26,14)(16,20,31,19,18,17) ])
gap> t:=Image(iso,s);
Group([ (1,8,7,21)(3,22,28,27)(4,31,17,29)(5,11,24,23)(6,15)(9,18,13,25)
  (10,19)(12,16,14,26), (1,25,3,11,6,17,10,19,22,24,29,15,9,8,27,23,16,12,7,
   18,30,5,26,4)(13,21,28,20,31,14) ])
gap> Filtered([1..31],x->ForAll(GeneratorsOfGroup(t),y->x^y=x));
[ 2 ]
gap> List(RightTransversal(G,s),x->[1^x,2^Image(iso,x)]);
[ [ 1, 2 ], [ 31, 13 ], [ 29, 19 ], [ 27, 24 ], [ 19, 21 ], [ 7, 8 ],
  [ 15, 5 ], [ 16, 31 ], [ 23, 11 ], [ 20, 14 ], [ 10, 30 ], [ 11, 26 ],
  [ 2, 9 ], [ 9, 23 ], [ 12, 3 ], [ 24, 22 ], [ 22, 12 ], [ 6, 16 ],
  [ 3, 10 ], [ 30, 4 ], [ 25, 25 ], [ 8, 17 ], [ 14, 15 ], [ 18, 28 ],
  [ 21, 6 ], [ 4, 1 ], [ 28, 27 ], [ 17, 20 ], [ 5, 7 ], [ 26, 29 ],
  [ 13, 18 ] ]
gap> perm:=TransposedMat(last);
[ [ 1, 31, 29, 27, 19, 7, 15, 16, 23, 20, 10, 11, 2, 9, 12, 24, 22, 6, 3, 30,
      25, 8, 14, 18, 21, 4, 28, 17, 5, 26, 13 ],
  [ 2, 13, 19, 24, 21, 8, 5, 31, 11, 14, 30, 26, 9, 23, 3, 22, 12, 16, 10, 4,
      25, 17, 15, 28, 6, 1, 27, 20, 7, 29, 18 ] ]
gap> perm:=MappingPermListList(perm[1],perm[2]);
(1,2,9,23,11,26,29,19,21,6,16,31,13,18,28,27,24,22,12,3,10,30,4)(5,7,8,17,20,
14,15)
gap> G^perm=H;
true

@DominikBernhardt
Copy link
Contributor Author

That's interesting, thanks @hulpke . I think this won't be fast for the groups I'm dealing with in general, but I'll have a look at it.

@hulpke
Copy link
Contributor

hulpke commented Jul 21, 2020

@DominikBernhardt I would not recommend it as a general method, unless your groups are very similar, but it might be worth a try. (What is missing is a way to run a call -- here IsomorphismGroups for a limited amount of time and abort if it takes too long.)

@DominikBernhardt
Copy link
Contributor Author

DominikBernhardt commented Sep 13, 2021 •
edited
Loading

Just as an update, using SetVerbose("Partition", 3)' in Magma before testing for conjugacy yields the following information:

Checking orders, transitivity and orbits for quick answer
No quick answer found. Choosing base for search
Checking for known normalizer
GrpPerm normalizer (degree 1125). Covering group
Symmetric group
Subgroup order
2^7 * 3^4 * 5^3
Choice level 1, height 1, bp 2, basic cell size 1125
N Refine: 1 (2), at height 2
Choice level 2, height 6, bp 10, basic cell size 576
N Refine: 1 (2), at height 7
N Refine: 2 (3), at height 8
Z Refine: 1 (1), at height 15
Z Refine: 1 (1), at height 37
Z Refine: 1 (1), at height 41
Z Refine: 1 (1), at height 55
Z Refine: 1 (1), at height 60
Z Refine: 1 (1), at height 70
Z Refine: 2 (1), at height 71
Choice level 3, height 111, bp 273, basic cell size 6
Z Refine: 5 (2), at height 112
Z Refine: 5 (2), at height 459
Z Refine: 5 (2), at height 768
Z Refine: 6 (2), at height 804
CL Refine: 1 at height 948
BeC Refine: 2, at height 960
Constructed base for search after 0.000 secs
Basic cell sizes: 1125, 576, 6
Base change level 3
New generator at level 2: 1, 576, 6
Finished level 2: 1, 576, 6 after 0.000 secs
Finished level 2: 1125, 576, 6 after 0.000 secs
Finished search after 0.000 secs
Order: 2^7 * 3^5 * 5^3
Reject counts:
Min in dc:  0 0 0 0 0 0 0
Min XY:  0 0
OL:  0 0 1703
Covering:  0 0
Image grp:  0 0 0
Refine:  0 0 0 0 0 0
Element:  0 0
GrpPerm subgroup conjugacy (degree 1125). Covering group
Symmetric group
Subgroup order
2^7 * 3^4 * 5^3
Choice level 1, height 1, bp 2, basic cell size 1125
N Refine: 1 (2), at height 2
Choice level 2, height 6, bp 10, basic cell size 576
N Refine: 1 (2), at height 7
N Refine: 2 (3), at height 8
Z Refine: 1 (1), at height 15
Z Refine: 1 (1), at height 37
Z Refine: 1 (1), at height 41
Z Refine: 1 (1), at height 55
Z Refine: 1 (1), at height 60
Z Refine: 1 (1), at height 70
Z Refine: 2 (1), at height 71
Choice level 3, height 111, bp 273, basic cell size 6
Z Refine: 5 (2), at height 112
Z Refine: 5 (2), at height 459
Z Refine: 5 (2), at height 768
Z Refine: 6 (2), at height 804
BeC Refine: 1, at height 948
BeC Refine: 1, at height 1095
BeC Refine: 1, at height 1119
Constructed base for search after 0.000 secs
Basic cell sizes: 1125, 576, 6
Base change level 3
Finished search after 0.010 secs
Found coset rep
Reject counts:
Min in dc:  0 0 0 0
Min XY:  0 0
Covering:  0 0
Image grp:  0 0 0
Refine:  0 0 0 0 0 0
Element:  0 0
true (4, 8)(5, 9)(6, 7)(13, 17)(14, 18)(15, 16)(22, 26)(23, 27)(24, 25)(28, 392, 34, 389, 31, 395)(29, 394, 35, 391, 32, 388)(30, 390, 36, 396, 33, 393)(37, 169, 44, 166,
    42, 163)(38, 167, 45, 164, 40, 170)(39, 165, 43, 171, 41, 168)(49, 53)(50, 54)(51, 52)(55, 261, 61, 256, 58, 254)(56, 255, 62, 259, 59, 257)(57, 258, 63, 253, 60, 
    260)(64, 815, 70, 812, 67, 818)(65, 817, 71, 814, 68, 811)(66, 813, 72, 819, 69, 816)(73, 177, 80, 174, 78, 180)(74, 172, 81, 178, 76, 175)(75, 179, 79, 176, 77, 
    173)(82, 262)(83, 263)(84, 264)(85, 269)(86, 270)(87, 268)(88, 267)(89, 265)(90, 266)(94, 98)(95, 99)(96, 97)(100, 802, 107, 808, 105, 805)(101, 809, 108, 806, 103, 
    803)(102, 807, 106, 804, 104, 810)(109, 131, 115, 128, 112, 134)(110, 133, 116, 130, 113, 127)(111, 129, 117, 135, 114, 132)(118, 1085)(119, 1084)(120, 1086)(121, 
    1082)(122, 1081)(123, 1083)(124, 1088)(125, 1087)(126, 1089)(136, 138, 142, 144, 139, 141)(137, 140, 143)(145, 448, 152, 445, 150, 442)(146, 446, 153, 443, 148, 
    449)(147, 444, 151, 450, 149, 447)(154, 331, 161, 328, 159, 325)(155, 329, 162, 326, 157, 332)(156, 327, 160, 333, 158, 330)(181, 505)(182, 506)(183, 507)(184, 
    512)(185, 513)(186, 511)(187, 510)(188, 508)(189, 509)(190, 466, 197, 463, 195, 460)(191, 464, 198, 461, 193, 467)(192, 462, 196, 468, 194, 465)(199, 621, 205, 616, 
    202, 614)(200, 615, 206, 619, 203, 617)(201, 618, 207, 613, 204, 620)(208, 901, 214, 907, 211, 904)(209, 906, 215, 903, 212, 909)(210, 908, 216, 905, 213, 902)(217, 
    923, 224, 920, 222, 926)(218, 921, 225, 927, 220, 924)(219, 925, 223, 922, 221, 919)(226, 606, 233, 610, 231, 608)(227, 612, 234, 607, 229, 605)(228, 609, 232, 604, 
    230, 611)(235, 1046)(236, 1047)(237, 1045)(238, 1053)(239, 1051)(240, 1052)(241, 1048)(242, 1049)(243, 1050)(244, 356, 251, 354, 249, 358)(245, 353, 252, 360, 247, 
    355)(246, 359, 250, 357, 248, 352)(271, 274, 277)(272, 279, 278, 276, 275, 273)(280, 1039, 287, 1037, 285, 1044)(281, 1036, 288, 1043, 283, 1041)(282, 1042, 286, 
    1040, 284, 1038)(289, 424, 296, 431, 294, 429)(290, 430, 297, 428, 292, 426)(291, 427, 295, 425, 293, 432)(298, 299, 305, 306, 303, 301)(300, 302, 304)(307, 
    1097)(308, 1096)(309, 1098)(310, 1094)(311, 1093)(312, 1095)(313, 1091)(314, 1090)(315, 1092)(316, 1009)(317, 1011)(318, 1010)(319, 1015)(320, 1017)(321, 1016)(322, 
    1012)(323, 1014)(324, 1013)(334, 379, 341, 385, 339, 382)(335, 386, 342, 383, 337, 380)(336, 384, 340, 381, 338, 387)(343, 1074, 350, 1078, 348, 1076)(344, 1080, 351,
    1075, 346, 1073)(345, 1077, 349, 1072, 347, 1079)(361, 368, 367, 365, 364, 362)(363, 366, 369)(370, 733)(371, 734)(372, 735)(373, 731)(374, 732)(375, 730)(376, 
    738)(377, 736)(378, 737)(397, 399, 403, 405, 400, 402)(398, 401, 404)(406, 678, 412, 682, 409, 680)(407, 681, 413, 676, 410, 683)(408, 684, 414, 679, 411, 677)(415, 
    422, 421, 419, 418, 416)(417, 420, 423)(433, 539, 440, 537, 438, 532)(434, 536, 441, 534, 436, 538)(435, 533, 439, 540, 437, 535)(451, 1065)(452, 1064)(453, 
    1063)(454, 1071)(455, 1070)(456, 1069)(457, 1068)(458, 1067)(459, 1066)(469, 689)(470, 690)(471, 688)(472, 687)(473, 685)(474, 686)(475, 691)(476, 692)(477, 693)(478,
    1004, 484, 1001, 481, 1007)(479, 1006, 485, 1003, 482, 1000)(480, 1002, 486, 1008, 483, 1005)(487, 579, 493, 583, 490, 581)(488, 582, 494, 577, 491, 584)(489, 585, 
    495, 580, 492, 578)(496, 748, 502, 754, 499, 751)(497, 753, 503, 750, 500, 756)(498, 755, 504, 752, 501, 749)(514, 833, 521, 831, 519, 835)(515, 830, 522, 837, 517, 
    832)(516, 836, 520, 834, 518, 829)(523, 568, 530, 574, 528, 571)(524, 575, 531, 572, 526, 569)(525, 573, 529, 570, 527, 576)(541, 894)(542, 893)(543, 892)(544, 
    900)(545, 899)(546, 898)(547, 897)(548, 896)(549, 895)(550, 839, 557, 846, 555, 841)(551, 845, 558, 843, 553, 838)(552, 842, 556, 840, 554, 844)(559, 563)(560, 
    564)(561, 562)(586, 930, 593, 934, 591, 932)(587, 936, 594, 931, 589, 929)(588, 933, 592, 928, 590, 935)(595, 598, 601)(596, 603, 602, 600, 599, 597)(622, 871, 628, 
    869, 625, 867)(623, 865, 629, 872, 626, 870)(624, 868, 630, 866, 627, 873)(631, 739)(632, 741)(633, 740)(634, 745)(635, 747)(636, 746)(637, 742)(638, 744)(639, 
    743)(640, 647, 646, 644, 643, 641)(642, 645, 648)(649, 652, 655)(650, 657, 656, 654, 653, 651)(658, 659, 665, 666, 663, 661)(660, 662, 664)(667, 668, 674, 675, 672, 
    670)(669, 671, 673)(694, 695, 701, 702, 699, 697)(696, 698, 700)(703, 966)(704, 964)(705, 965)(706, 970)(707, 971)(708, 972)(709, 968)(710, 969)(711, 967)(712, 
    881)(713, 880)(714, 882)(715, 878)(716, 877)(717, 879)(718, 875)(719, 874)(720, 876)(721, 914)(722, 913)(723, 915)(724, 911)(725, 910)(726, 912)(727, 917)(728, 
    916)(729, 918)(757, 1110, 764, 1114, 762, 1112)(758, 1116, 765, 1111, 760, 1109)(759, 1113, 763, 1108, 761, 1115)(766, 767, 773, 774, 771, 769)(768, 770, 772)(775, 
    1101)(776, 1100)(777, 1099)(778, 1107)(779, 1106)(780, 1105)(781, 1104)(782, 1103)(783, 1102)(784, 788)(785, 789)(786, 787)(793, 800, 799, 797, 796, 794)(795, 798, 
    801)(820, 960, 826, 955, 823, 962)(821, 963, 827, 958, 824, 956)(822, 957, 828, 961, 825, 959)(847, 853, 854, 851, 852, 849)(848, 850, 855)(856, 1055, 863, 1062, 861,
    1057)(857, 1061, 864, 1059, 859, 1054)(858, 1058, 862, 1056, 860, 1060)(883, 1119)(884, 1118)(885, 1117)(886, 1125)(887, 1124)(888, 1123)(889, 1122)(890, 1121)(891, 
    1120)(937, 943, 944, 941, 942, 939)(938, 940, 945)(946, 998, 953, 995, 951, 992)(947, 996, 954, 993, 949, 999)(948, 991, 952, 997, 950, 994)(973, 986, 979, 984, 976, 
    988)(974, 989, 980, 987, 977, 982)(975, 983, 981, 990, 978, 985)(1018, 1019, 1025, 1026, 1023, 1021)(1020, 1022, 1024)(1027, 1028, 1034, 1035, 1032, 1030)(1029, 1031,
    1033)

@fieker
Copy link
Contributor

fieker commented Sep 13, 2021 via email

@DominikBernhardt

This comment has been minimized.

Sign in to view
@fingolfin
Copy link
Member

So @hulpke already showed us how one can deal with the degree 31 example in GAP

Insultingly, in the degree 31 example, even this naive attempt to find a conjugator, by using the 2-transitivity, works. I.e.: compute the non-transitive double stabilizer and try to conjugate them. Here by chance that conjugator already conjugates G onto H.

gap> G := Group([ (2,5,4,3)(6,11,16,21)(7,15,19,23)(8,12,20,24)(9,13,17,25)(10,14,18,22)(27,29)(28,30), (1,26,4,6,9,23,8,17,13,28,5,21,14,12,10,15,18,25,30,2,16,19,29,31)(3,11,24,20,7,27) ]);;
gap> H := Group([ (1,4,29,2)(3,30,18,20)(5,19,26,10)(6,13)(7,8,27,31)(9,28,24,16)(12,22)(14,21,17,23), (1,16,12,31,26,19,5,18,2,23,9,13,8,20,14,10,30,29,28,22,15,25,11,27)(3,21,24,6,7,17) ]);;
gap> Gsub:=Stabilizer(G,[30,31],OnTuples);;
gap> Hsub:=Stabilizer(H,[30,31],OnTuples);;
gap> g:=RepresentativeAction(SymmetricGroup(29),Gsub,Hsub);
(1,2,6,7,8,27,24,14,3,26)(4,16,9,11,10,15,23,20,22,28,12)(5,29,18,17)(13,25,21)
gap> G^g = H;
true

So something like this might already help in some cases?

# conjugate G into H as subgroups of S. Here I'll be lazy and assume that all are transitivy
MyConjugator:=function(S,G,H)
   local deg, t, Ssub, Gsub, Hsub, r, N;
   deg := NrMovedPoints(S);
   Assert(0, MovedPoints(S) = [1..deg]); # FIXME
   Assert(0, MovedPoints(G) = [1..deg]); # FIXME
   Assert(0, MovedPoints(H) = [1..deg]); # FIXME
   t := Transitivity(G);
   if t <> Transitivity(H) then return fail; fi;
   Ssub := Stabilizer(S, [deg-t+1 .. deg], OnTuples);
   Gsub := Stabilizer(G, [deg-t+1 .. deg], OnTuples);
   Hsub := Stabilizer(H, [deg-t+1 .. deg], OnTuples);
   r:=RepresentativeAction(Ssub,Gsub,Hsub);
   if G^r = H then return r; fi;
   N := Normalizer(Ssub, Gsub);
   return First(RightCoset(N,r), g -> G^g = H);
end;

Then this works in 30 milliseconds or so:

MyConjugator(SymmetricGroup(31), G, H);

Of course this won't help in general, and indeed it e.g. does not thing for the initial example.

@ChrisJefferson
Copy link
Contributor

Just to say, I'm on holiday this week, but interested it is possible to get info from magma, and am going to investigate when I get back.

@fingolfin fingolfin mentioned this issue Oct 6, 2023
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
topic: library topic: performance bugs or enhancements related to performance (improvements or regressions)
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
6 participants
@fingolfin @ChrisJefferson @fieker @hulpke @DominikBernhardt @wilfwilson