Blogs I Follow
here’s a brief summary of what I’ve been doing during the 10th week of my GSoC.
In : S = SymmetricGroup(5) In : prop_fix_3 = lambda x: x(3) == 3 In : %autoreload In : S.subgroup_search(prop_fix_3) --------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-90-6b85aa1285b8> in <module>() ----> 1 S.subgroup_search(prop_fix_3) /home/alexander/workspace/sympy/sympy/combinatorics/perm_groups.py in subgroup_search(self, prop, base, strong_gens, tests, init_subgroup) 2660 2661 # this function maintains a partial BSGS structure up to position l -> 2662 _insert_point_in_base(res, res_base, res_strong_gens, l, new_point, distr_gens=res_distr_gens, basic_orbits=res_basic_orbits, transversals=res_transversals) 2663 # find the l+1-th basic stabilizer 2664 new_stab = PermutationGroup(res_distr_gens[l + 1]) /home/alexander/workspace/sympy/sympy/combinatorics/util.py in _insert_point_in_base(group, base, strong_gens, pos, point, distr_gens, basic_orbits, transversals) 423 # baseswap with the partial BSGS structures. Notice that we need only 424 # the orbit and transversal of the new point under the last stabilizer --> 425 new_base, new_strong_gens = group.baseswap(partial_base, strong_gens, pos, randomized=False, transversals=partial_transversals, basic_orbits=partial_basic_orbits, distr_gens=partial_distr_gens) 426 # amend the basic orbits and transversals 427 stab_pos = PermutationGroup(distr_gens[pos]) /home/alexander/workspace/sympy/sympy/combinatorics/perm_groups.py in baseswap(self, base, strong_gens, pos, randomized, transversals, basic_orbits, distr_gens) 2472 # ruling out member of the basic orbit of base[pos] along the way 2473 while len(current_group.orbit(base[pos])) != size: -> 2474 gamma = iter(Gamma).next() 2475 x = transversals[pos][gamma] 2476 x_inverse = ~x StopIteration:
The reason is certainly the change of base performed on line 11 in the pseudocode (this is also indicated in my code on my local week6 branch here ). The use of the function BASESWAP there is what gets us into trouble. It is meant to be applied to base and a strong generating set relative to it, switch two consecutive base points and change the generating set accordinly. However, in subgroup_search the goal is to change a base to where is a new point. The book () mentions that this is done by using BASESWAP but doesn’t provide any details. My strategy is the following: I cut the base so that it becomes and cut the correponding data structures – the strong generators strong_gens, the basic_orbits, the transversals, and the strong generators distributed according to membership in basic stabilizers distr_gens (I know, I still have to rename this to strong_gens_distr). Then I append the point so that the base is and calculate an orbit and transversal for $b_l’$ under the stabilzier of . Finally I apply BASESWAP to this new base in order to switch the two rightmost points. Then I go back to by appending what I had cut in the start and calculating a transversal/orbit for under the stabilizer just found, that of . Obviously, the resulting BSGS structures are valid only up to position , and that’s all the information we can acquire without another application of baseswap or finding another stabilizer ( and in general, finding a stabilizer is a computationally hard task relative to calculating orbits/transversals). The entire purpose of this use of BASESWAP in SUBGROUPSEARCH is to obtain generators for the stabilizer of and maintain a base/strong generating set that are valid up to a certain position. There are many such base changes performed on the same base throughout the course of the function and something goes wrong along the way. I still have to figure out why and where.
That’s it for now : )
Exploring and venting about quantitative issues
Adventures of a would-be do-gooder.
Mathematics related discussions
Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao
Most of the blog moved to blog.krastanov.org