-
Notifications
You must be signed in to change notification settings - Fork 161
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.
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
Slow conjugacy test of subgroups in natural symmetric group #3718
Comments
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. |
Thanks @hulpke . So It comes done to the backtrack, which means this is nothing one can improve quickly. |
Just checking, what's the answer, are they conjugate (and if they are, what's a permutation that conjugates one to the other) |
@ChrisJefferson Yes they are: |
@ChrisJefferson and I have been looking into this. For a permutation group 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. |
@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? |
Yes, please do 🙂 Email would be better for me, because of its permanence. |
There is a much smaller example on |
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:
|
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. |
@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 |
Just as an update, using
|
On Mon, Sep 13, 2021 at 03:35:24AM -0700, Dominik Bernhardt wrote:
Just as an update, using `SetInfoLevel("Partition", 3)'` in Magma before testing for conjugacy yields the following information:
SetVerbose("Partition", 3);
… ```
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)
```
--
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
#3718 (comment)
|
This comment has been minimized.
This comment has been minimized.
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.
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. |
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. |
The call
IsConjugate(sym,g,h)
, wheresym
,g
andh
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
The text was updated successfully, but these errors were encountered: