Source code for stallings_graphs.about_free_factors

# -*- coding: utf-8 -*-
r"""
The methods for the class ``FinitelyGeneratedSubgroup`` use a number of ancillary functions.
These are the functions which deal with free factors: determining whether a subgroup is a
free factor of the ambient group of another subgroup, deciding primitivity of a word, computing the
lattice of algebraic extensions of a subgroup.

We have the following functions:

- ``SilvaWeil_free_factor_of_ambient``: to decide whether a given subgroup is a free factor of
  the ambient group and, possibly give a basis of its complement

- ``SilvaWeil_free_factor_of``: to decide whether a given subgroup is a free factor of another and,
  possibly, give a basis of its complement

The algorithm implemented in ``SilvaWeil_free_factor_of_ambient`` and ``SilvaWeil_free_factor_of``
is from [SW2008]_. The worst-case complexity
is polynomial in the size of the subgroups considered but exponential in the rank difference
between them.

- ``set_of_possible_additional_generators``: an ancillary function to find the additional generators
  that will lead to the overgroups of a subgroup obtained by identifying two vertices of the
  Stallings graph

- ``compute_algebraic_extensions``: computes the semilattice of algebraic extensions of a subgroup
  noting those that are elementary algebraic and some of their inclusion relation (sufficiently many
  to include a Hasse diagram)

The algorithm implemented in ``compute_algebraic_extensions``  is from [MVW2007]_. It requires
verifying whether certain subgroups are free factors of others. This is done using the Silva Weil algorithm.

EXAMPLES::

    sage: from stallings_graphs import FinitelyGeneratedSubgroup
    sage: from stallings_graphs.about_free_factors import SilvaWeil_free_factor_of_ambient, SilvaWeil_free_factor_of
    sage: L1 = ['ac','bacd','ed']
    sage: H1 = FinitelyGeneratedSubgroup.from_generators(L1, alphabet_type='abc')
    sage: SilvaWeil_free_factor_of_ambient(H1, maxletter = 0, complement = True)
    (True, [word: 2,1,-5, word: -2])
    
::
    
    sage: LH = [[-3,1,-2,-1,-1,-3,2,2,3], [-3,-1,-1,3,1,1,-3,-1,3,1,3,3], [-3,1,3,-1,-1,-3,1,1,1,3,-1,-1], [1,1,-3,1,3,1,1,-3,-1,3]]
    sage: LK = [[1,1,2,-1,3], [1,1,3,-1], [-3,1,3,-1,-1], [-3,1,1,3], [-3,2,3], [1,3,3]]
    sage: H = FinitelyGeneratedSubgroup.from_generators(LH, alphabet_type='123')
    sage: K = FinitelyGeneratedSubgroup.from_generators(LK, alphabet_type='123')
    sage: SilvaWeil_free_factor_of(H, K, complement = True)
    (False, 'the 1st argument is not a free factor of the second')

::

    sage: LH = [[3,1,-2,-1,-1,-3,2,2,3], [-3,-1,-1,3,1,1,-3,-1,3,1,3,3], [-3,1,3,-1,-1,-3,1,1,1,3,-1,-1], [1,1,-3,1,3,1,1,-3,-1,3]]
    sage: LK = [[1,1,2,-1,3], [1,1,3,-1], [-3,1,3,-1,-1], [-3,1,1,3], [-3,2,3], [1,3,3]]
    sage: H = FinitelyGeneratedSubgroup.from_generators(LH, alphabet_type='123')
    sage: K = FinitelyGeneratedSubgroup.from_generators(LK, alphabet_type='123')
    sage: SilvaWeil_free_factor_of(H, K, complement = True)
    (False, '1st argument not contained in 2nd')

::

    sage: H = FinitelyGeneratedSubgroup.from_generators(['bba','bAbaB'], alphabet_type='abc')
    sage: K = FinitelyGeneratedSubgroup.from_generators(['a', 'bb', 'bAbaB'], alphabet_type='abc')
    sage: SilvaWeil_free_factor_of(H, K, complement = True)
    (True, [word: -2,-2])
    
::
    
    sage: from stallings_graphs.about_free_factors import compute_algebraic_extensions
    sage: testgens = ['aba','bab']
    sage: testH = FinitelyGeneratedSubgroup.from_generators(testgens,alphabet_type='abc')
    sage: compute_algebraic_extensions(testH)
    {0: [set(),
      {1},
      [],
      {word: -1, word: -1,2, word: 1,-2, word: 11, word: 22},
      True,
      False],
     1: [{0}, set(), [word: -1], set(), True, False]}


AUTHOR:

- Pascal WEIL (2020-05-11): initial version
  CNRS, Univ. Bordeaux, LaBRI <pascal.weil@cnrs.fr>

"""

from sage.combinat.words.word import Word
from stallings_graphs import FinitelyGeneratedSubgroup
from stallings_graphs.about_words import rank, positive_alphabetic_content, group_inverse
from stallings_graphs.about_bases import spanning_tree_and_paths, basis_interpreter
from stallings_graphs.about_TC_morphisms import FGendomorphism, image_of_Word_by_endomorphism
                

[docs]def SilvaWeil_free_factor_of_ambient(H, maxletter = 0, complement = True): r""" If ``complement`` is set to ``False``, returns whether `H`is a free factor of the ambient free group (a boolean). If ``complement`` is set to ``True``, returns a pair of a boolean as above, and a string explaining why `H` is not a free factor, or a basis for a complement of `H` if `H` is a free factor (in numerical form). In that case, the ambient free group is understood to be of rank the maximal letter occurring in `H` if ``maxletter`` is set to 0, of rank ``maxletter`` otherwise. ``H`` is expected to be a ``FinitelyGeneratedSubgroup``; ``maxletter`` is expected to be a non-negative integer, equal to 0 or greater than or equal to the maximal letter occurring in ``H``; ``complement`` is expected to be a Boolean. INPUT: - ``H`` -- ``FinitelyGeneratedSubgroup`` - ``maxletter`` -- integer - ``complement`` -- boolean OUTPUT: - a boolean if ``complement`` is set to ``False``, and a pair consisting of a boolean and either a string or a list of ``Words`` in numerical form otherwise ALGORITHM: The algorithm implemented is from [P. Silva, P. Weil. On an algorithm to decide whether a free group is a free factor of another, Theoretical Informatics and Applications 42 (2008) 395-414]. Be aware that the worst-case complexity is polynomial in the size of `H` but exponential in the rank difference between `H` and the ambient group. EXAMPLES:: sage: from stallings_graphs import FinitelyGeneratedSubgroup sage: from stallings_graphs.about_free_factors import SilvaWeil_free_factor_of_ambient sage: L1 = ['ac','bacd','ed'] sage: H1 = FinitelyGeneratedSubgroup.from_generators(L1, alphabet_type='abc') sage: SilvaWeil_free_factor_of_ambient(H1, maxletter = 0, complement = True) (True, [word: 2,1,-5, word: -2]) :: sage: SilvaWeil_free_factor_of_ambient(H1, maxletter = 0, complement = False) True :: sage: L2 = ['acac','bacd','ed'] sage: H2 = FinitelyGeneratedSubgroup.from_generators(L2, alphabet_type='abc') sage: SilvaWeil_free_factor_of_ambient(H2, maxletter = 0, complement = True) (False, 'the 1st argument is not a free factor of the second') :: sage: SilvaWeil_free_factor_of_ambient(H2, maxletter = 0, complement = False) False :: sage: H = FinitelyGeneratedSubgroup.from_generators(['A','d'], alphabet_type='abc') sage: SilvaWeil_free_factor_of_ambient(H, complement = True) (True, [word: 2, word: 3]) :: sage: SilvaWeil_free_factor_of_ambient(H, complement = False) True """ original_graph = H.stallings_graph() original_basis = H.basis(alphabet_type = '123') if maxletter > 0: deficit = set(range(1,maxletter + 1)) else: maxrank = max([rank(x) for x in original_basis]) deficit = set(range(1,maxrank + 1)) for x in original_basis: deficit = deficit.difference(positive_alphabetic_content(x)) # if H.stallings_graph_size() == 1: if complement == True: return (True,[Word([x]) for x in deficit]) else: return True # now H has size at least 2 if H.rank() >= H.ambient_group_rank(): if complement == True: return (False,'the 1st argument has too large a rank') else: return False # now H has size at least 2 and rank of H < rank of the ambient group current_list = [(original_graph,[])] while current_list: (G,B) = current_list[-1] temporary_list = [] still_good = True T,L,D = spanning_tree_and_paths(G) for p in G.vertices(): for q in G.vertices(): if still_good and q > p: w = D[p]+group_inverse(D[q]) newgens = original_basis + B + [w] newH = FinitelyGeneratedSubgroup.from_generators(newgens,alphabet_type = '123') if newH.rank() == len(G.edges()) - len(G.vertices()) + 2: if newH.stallings_graph_size() == 1: if complement: return (True,B+[w]+[Word([x]) for x in deficit]) else: return True # now newH has size at least 2 newG = newH.stallings_graph() temporary_list.append((newG,w)) else: still_good = False current_list = current_list[:-1] if still_good: current_list = current_list + [(newG,B + [w]) for (newG,w) in temporary_list] if complement: return (False,'the 1st argument is not a free factor of the second') else: return False
[docs]def SilvaWeil_free_factor_of(H, K, complement = True): r""" If ``complement`` is set to ``False``, returns whether `H`is a free factor of ``K`` (a boolean). If ``complement`` is set to ``True``, returns a pair of a boolean as above, and a string explaining why `H` is not a free factor, or a basis for a complement of `H` in `K` (in numerical form) if `H` is a free factor. ``H`` and ``K`` are expected to be of type ``FinitelyGeneratedSubgroup``; ``complement`` is expected to be a Boolean. INPUT: - ``H`` -- ``FinitelyGeneratedSubgroup`` - ``K`` -- ``FinitelyGeneratedSubgroup`` - ``complement`` -- boolean OUTPUT: - a boolean if ``complement`` is set to ``False``, and a pair consisting of a boolean and either a string or a list of ``Words`` in numerical form otherwise ALGORITHM: The algorithm implemented is from [P. Silva, P. Weil. On an algorithm to decide whether a free group is a free factor of another, Theoretical Informatics and Applications 42 (2008) 395-414]. Be aware that the worst-case complexity is polynomial in the size of `H` and `K` but exponential in the rank difference between `H` and `K`. EXAMPLES:: sage: from stallings_graphs import FinitelyGeneratedSubgroup sage: from stallings_graphs.about_free_factors import SilvaWeil_free_factor_of sage: LH = [[2,-3,1,3,2,3,-2,-1,2,-3,-1], [3,1,1,1,-3,-1], [1,3,-2,-1,2,-1,2], [3,2,3,-1,2,-1]] sage: LK = [[2,-3], [1,1], [1,3,-2,1,2,-3,-1], [3,2], [3,1,-3,-1], [1,3,2,-1], [1,3,3,-1], [1,3,1,-3]] sage: H = FinitelyGeneratedSubgroup.from_generators(LH, alphabet_type='123') sage: K = FinitelyGeneratedSubgroup.from_generators(LK, alphabet_type='123') sage: SilvaWeil_free_factor_of(H, K, complement = True) (True, [word: 3,2,3,1,2,-1, word: 32, word: 3,1,3,-1, word: 11]) :: sage: SilvaWeil_free_factor_of(H, K, complement = False) True :: sage: LH = [[-3,1,-2,-1,-1,-3,2,2,3], [-3,-1,-1,3,1,1,-3,-1,3,1,3,3], [-3,1,3,-1,-1,-3,1,1,1,3,-1,-1], [1,1,-3,1,3,1,1,-3,-1,3]] sage: LK = [[1,1,2,-1,3], [1,1,3,-1], [-3,1,3,-1,-1], [-3,1,1,3], [-3,2,3], [1,3,3]] sage: H = FinitelyGeneratedSubgroup.from_generators(LH, alphabet_type='123') sage: K = FinitelyGeneratedSubgroup.from_generators(LK, alphabet_type='123') sage: SilvaWeil_free_factor_of(H, K, complement = True) (False, 'the 1st argument is not a free factor of the second') :: sage: SilvaWeil_free_factor_of(H, K, complement = False) False :: sage: LH = [[3,1,-2,-1,-1,-3,2,2,3], [-3,-1,-1,3,1,1,-3,-1,3,1,3,3], [-3,1,3,-1,-1,-3,1,1,1,3,-1,-1], [1,1,-3,1,3,1,1,-3,-1,3]] sage: LK = [[1,1,2,-1,3], [1,1,3,-1], [-3,1,3,-1,-1], [-3,1,1,3], [-3,2,3], [1,3,3]] sage: H = FinitelyGeneratedSubgroup.from_generators(LH, alphabet_type='123') sage: K = FinitelyGeneratedSubgroup.from_generators(LK, alphabet_type='123') sage: SilvaWeil_free_factor_of(H, K, complement = True) (False, '1st argument not contained in 2nd') :: sage: SilvaWeil_free_factor_of(H, K, complement = False) False :: sage: H = FinitelyGeneratedSubgroup.from_generators(['bba','bAbaB'], alphabet_type='abc') sage: K = FinitelyGeneratedSubgroup.from_generators(['a', 'bb', 'bAbaB'], alphabet_type='abc') sage: SilvaWeil_free_factor_of(H, K, complement = True) (True, [word: -2,-2]) :: sage: SilvaWeil_free_factor_of(H, K, complement = False) True :: sage: H = FinitelyGeneratedSubgroup.from_generators(['a','B'], alphabet_type='abc') sage: K = FinitelyGeneratedSubgroup.from_generators(['a','b','d'], alphabet_type='abc') sage: SilvaWeil_free_factor_of(H, K, complement = True) (True, [word: 4]) :: sage: SilvaWeil_free_factor_of(H, K, complement = False) True """ basisK = K.basis(alphabet_type = '123') rK = len(basisK) basisH = H.basis(alphabet_type = '123') if all(K.contains_element(x) for x in basisH): translatedbasisH = basis_interpreter(basisH, basisK, alphabet_type = '123') translatedH = FinitelyGeneratedSubgroup.from_generators(translatedbasisH,alphabet_type = '123') if complement: (valeur,base) = SilvaWeil_free_factor_of_ambient(translatedH, maxletter = rK, complement = complement) if valeur: phi = FGendomorphism(basisK, alphabet_type = '123') translatedbase = [image_of_Word_by_endomorphism(phi, w, alphabet_type='123') for w in base] return (valeur,translatedbase) else: return (valeur,base) else: return SilvaWeil_free_factor_of_ambient(translatedH, maxletter = rK, complement = complement) else: if complement: return(False,'1st argument not contained in 2nd') else: return False
[docs]def set_of_possible_additional_generators(G): r""" ``G`` is expected to be the Stallings graph of a finitely generated subgroup of a free group. The function returns a set of Words of the form `u_pu_q^{-1}`, where `u_p`(resp. `u_q`) is a path from the root vertex 0 to vertex `p`(resp. `q`). INPUT: - ``G`` -- ``DiGraph`` OUTPUT: - a set of objects of type ``Word`` EXAMPLE:: sage: from stallings_graphs import FinitelyGeneratedSubgroup sage: from stallings_graphs.about_free_factors import set_of_possible_additional_generators sage: testgens = ['aba','bab'] sage: testH = FinitelyGeneratedSubgroup.from_generators(testgens,alphabet_type='abc') sage: testG = testH.stallings_graph() sage: set_of_possible_additional_generators(testG) {word: -1, word: -1,2, word: 1,-2, word: 11, word: 22} """ # should return the empty set if G has a single vertex S = set() from stallings_graphs.about_automata import fibered_product T,L,D = spanning_tree_and_paths(G) GG = fibered_product(G,G) CC = GG.connected_components() baseCC = GG.connected_component_containing_vertex((0,0)) CC.remove(baseCC) for C in CC: (p,q) = C[0] additional_generator = D[p]+group_inverse(D[q]) if group_inverse(additional_generator) not in S: S.add(D[p]+group_inverse(D[q])) return S
[docs]def compute_algebraic_extensions(H): r""" Returns detailed information on the semilattice of algebraic extensions of the subgroup ``H``: a dictionary whose keys are integers (without any particular meaning, except key 0 corresponds to ``H`` itself) and whose entries are a list of information on algebraic extensions: sets of parents and children (not a Hasse diagram of the containment relation, but including such a diagram), list of generators to be added to those of ``H`` to generate that particular extension, a set of words which help compute the immediate overgroups of this extension, and two boolean flags expressing, respectively, that the extension is e-algebraic and that it is *not* algebraic. ``H`` is expected to be a ``FinitelyGeneratedSubgroup`` INPUT: - ``H`` -- ``FinitelyGeneratedSubgroup`` OUTPUT: - a dictionary whose keys are integers and whose entries are lists of two sets of keys, a list of ``Words``, a set of ``Words`` and two booleans EXAMPLES:: sage: from stallings_graphs import FinitelyGeneratedSubgroup sage: from stallings_graphs.about_free_factors import compute_algebraic_extensions sage: testgens = ['aba','bab'] sage: testH = FinitelyGeneratedSubgroup.from_generators(testgens,alphabet_type='abc') sage: compute_algebraic_extensions(testH) {0: [set(), {1}, [], {word: -1, word: -1,2, word: 1,-2, word: 11, word: 22}, True, False], 1: [{0}, set(), [word: -1], set(), True, False]} :: sage: testgens = ['ab','cd'] sage: testH = FinitelyGeneratedSubgroup.from_generators(testgens,alphabet_type='abc') sage: compute_algebraic_extensions(testH) {0: [set(), set(), [], {word: -3, word: -1, word: 1,-3}, True, False]} :: sage: testgens = ['ABBaaBABa','Baba','Abababba','AbabbABa','ABabAba'] sage: testH = FinitelyGeneratedSubgroup.from_generators(testgens,alphabet_type='abc') sage: compute_algebraic_extensions(testH) {0: [set(), {3, 6, 11}, [], {word: -2,-1,-2,1, word: -1,-2,-2,1,-2,-1,-2,1, word: -1,-2,-2,1,-2,1, word: -1,-2,-2,1,-1,-2,1, word: -1,-2,-2,1,1, word: -1,-2,1, word: -1,2,2,1, word: 1, word: 2, word: 21, word: 221}, True, False], 3: [{0, 6, 11}, set(), [word: -1,-2,1], set(), True, False], 6: [{0, 11}, {3}, [word: 21], {word: -1}, True, False], 11: [{0}, {3, 6}, [word: -1,-2,-2,1,-2,1], {word: -1,-2,1, word: -1,2, word: 2}, True, False]} """ original_graph = H.stallings_graph() original_basis = H.basis(alphabet_type = '123') original_possible_additional_generators = set_of_possible_additional_generators(original_graph) # # semilattice_AE is a dictionary. # Keys are integers, managed by keycounter # semilattice_AE entries are of the form # [(0)set of parent keys, (1)set of children keys, (2)list of generators beyond original_basis, # (3)set of possible additional generators, (4)flag_ealgebraic, (5)flag_guaranteed_non_algebraic) # # Note that the set of possible additional generators is empty iff the entry has size 1 # # flag_ealgebraic is True if I have found a witness: a sequence of elementary algebraic # extensions # # flag_guaranteed_non_algebraic is True if I have found a free factor # # The construction is in phases. Note that semilattice_AE is first constructed as a # tree (Phases I and II) where subgroups can have several occurrences, in different branches. # In Phase I, the tree of overgroups is constructed with some information about # e-algebraicity and non-algebraicity. At the end of this phase, every e-algebraic overgroup # is tagged as such in at least one of its occurrences. # In Phase II, free factors are systematically located within the tree structure. At the end # of this phase, every non-algebraic overgroup is tagged as such in at least one of its # occurrences. # In Phase III, overgroups along different branches are compared, and merged if they # are equal: the tree becomes a dag. One takes the disjunction of the ealgebraic and # guaranteed_non_algebraic tags of merged vertices (+ bookkeeping about their parents and # children. At the end of this phase, every overgroup has a single occurrence, and # flag_ealgebraic and flag_guaranteed_non_algebraic mean 'ealgebraic' and #'not algebraic'. # In Phase IV, non algebraic overgroups are eliminated. # semilattice_AE = {} # # Phase I: construct semilattice_AE, as a tree. # # keys_to_visit keeps track of the entries created but whose own overgroups (children) # have not yet been computed # keys_to_visit = [0] semilattice_AE[0] = [set(),set(),[],original_possible_additional_generators,True,False] keycounter = 1 # while keys_to_visit: current_key = keys_to_visit.pop() current_entry = semilattice_AE[current_key] current_generators = original_basis + current_entry[2] current_subgroup = FinitelyGeneratedSubgroup.from_generators(current_generators,alphabet_type='123') # # if currently_entry has size greater than 1 (non-empty list of possible # additional generators), append new quotients to the dictionary, increment keys_to_visit if len(current_entry[3]) != 0: newparent = set() newparent.add(current_key) for u in current_entry[3]: newgenerators = original_basis + current_entry[2] + [u] newH = FinitelyGeneratedSubgroup.from_generators(newgenerators,alphabet_type='123') newG = newH.stallings_graph() if newH.rank() <= current_subgroup.rank(): if current_entry[4]: flag_ealgebraic = True flag_guaranteed_non_algebraic = False else: flag_ealgebraic = False flag_guaranteed_non_algebraic = False else: flag_ealgebraic = False flag_guaranteed_non_algebraic = True # semilattice_AE[keycounter] = [newparent, set(), current_entry[2] + [u], set_of_possible_additional_generators(newG),flag_ealgebraic,flag_guaranteed_non_algebraic] # add this new entry to children of its antecedent, and to keys_to_visit # (even if it is known to not be algebraic: we still need to take its quotients # and the same subgroup may occur elsewhere, without a witness of it being # non algebraic). current_entry[1].add(keycounter) keys_to_visit.append(keycounter) keycounter +=1 # # Phase I over # # Phase II. Process the entries of the **tree** semilattice_AE, starting # with the largest keyvalues, seeking an ancestral free factor. If one is found, # say K free factor of current_subgroup, flag_guaranteed_non_algebraic is set to True # for all the keys between K (excluded) and the currently processed key. # One may skip the overgroups tagged ealgebraic (no free factor will be found) or # flag_guaranteed_non_algebraic (the existence of a free factor was already established). # keys_to_be_processed = list(semilattice_AE.keys()) keys_to_be_processed.sort() while keys_to_be_processed: processed_key = keys_to_be_processed.pop() processed_entry = semilattice_AE[processed_key] if not(processed_entry[4] or processed_entry[5]): # processed_entry is neither known to be e-algebraic nor to be non-algebraic processed_generators = original_basis + processed_entry[2] processed_subgroup = FinitelyGeneratedSubgroup.from_generators(processed_generators,alphabet_type='123') intermediate_keys = [processed_key] no_free_factor = True # check current_predecessor: if it is guaranteed_non_algebraic, go to next; # if it is not guaranteed_non_algebraic, check whether it is a free factor # of processed_key; # if it is not, add to intermediate_keys and go to next predecessor; # if it is, stop and change all intermediate_keys to guaranteed_non_algebraic, # we're finished with this processed_key. # When I run out of predecessors, I am finished with this processed_key. current_predecessor_key = processed_key current_predecessor_entry = semilattice_AE[current_predecessor_key] while no_free_factor and current_predecessor_key != 0: copyset = current_predecessor_entry[0].copy() current_predecessor_key = copyset.pop() current_predecessor_entry = semilattice_AE[current_predecessor_key] if current_predecessor_entry[5]: continue # now I know that current_predecessor_entry[5] is False current_predecessor_generators = original_basis + current_predecessor_entry[2] current_predecessor_subgroup = FinitelyGeneratedSubgroup.from_generators(current_predecessor_generators,alphabet_type='123') if current_predecessor_subgroup.SW_is_free_factor_of(processed_subgroup, complement = False, alphabet_type = '123'): no_free_factor = False else: intermediate_keys.append(current_predecessor_key) # At the end of this while loop, either I found a free factor, and I tag # intermediate vertices, or I reached the root. In either case, I am done with # processed_key. if not no_free_factor: for x in intermediate_keys: semilattice_AE[x][5] = True # no 'else': if processed_entry[4] or processed_entry[5], we do nothing # Phase II over # # Phase III. Explore the tree to spot equal subgroups, starting with the largest key and # comparing it with keys that are not in its ancestry (well, if they are, it will be quickly # handled by _eq_ because the Stallings graphs will have different sizes). When I find equal # subgroups, I merge their entries: bookkeeping of parents and children + following remark: # # if an occurrence of a subgroup is marked ealgebraic, the subgroup is indeed ealgebraic # if an occurrence of a subgroup is marked flag_guaranteed_non_algebraic, then the subgroup # is not algebraic # # Don't eliminate any entry because information is needed about every occurrence of # every overgroup # pairs_to_be_compared = [(p,q) for p in semilattice_AE.keys() for q in semilattice_AE.keys() if q < p and not(q in semilattice_AE[p][0] or p in semilattice_AE[q][0])] while pairs_to_be_compared: (key1,key2) = pairs_to_be_compared.pop() entry1 = semilattice_AE[key1] entry2 = semilattice_AE[key2] generators1 = original_basis + entry1[2] generators2 = original_basis + entry2[2] subgroup1 = FinitelyGeneratedSubgroup.from_generators(generators1,alphabet_type='123') subgroup2 = FinitelyGeneratedSubgroup.from_generators(generators2,alphabet_type='123') if subgroup1 == subgroup2: # je veux supprimer subgroup1: # les parents de 1 perdent 1 et gagnent 2 parmi leurs enfants, # les enfants de 1 perdent 1 et gagnent 2 parmi leurs parents, # l'ensemble des parents de 2 accueille les parents de 1, # l'ensemble des enfants de 2 accueille les enfants de 1, # key1 est retiré de semilattice_AE # toutes les paires à comparer contenant key1 sont supprimées for x in entry1[0]: semilattice_AE[x][1].discard(key1) semilattice_AE[x][1].add(key2) for y in entry1[1]: semilattice_AE[y][0].discard(key1) semilattice_AE[y][0].add(key2) entry2[0] = entry2[0].union(entry1[0]) entry2[1] = entry2[1].union(entry1[1]) entry2[4] = entry1[4] or entry2[4] entry2[5] = entry1[5] or entry2[5] for p in semilattice_AE.keys(): if p > key1 and (p,key1) in pairs_to_be_compared: pairs_to_be_compared.remove((p,key1)) elif p < key1 and (key1,p) in pairs_to_be_compared: pairs_to_be_compared.remove((key1,p)) semilattice_AE.pop(key1) # Now all pairs of entries have been compared, they are all distinct and those not # flagged guaranteed_not_algebraic are actually algebraic. # # Phase III over # # Phase IV. Remove the non algebraic entries # remaining_keys = list(semilattice_AE.keys()) while remaining_keys: key = remaining_keys.pop() entry = semilattice_AE[key] if entry[5]: # non algebraic overgroup; attach its children to its parents, # update its parents' list of children # eliminate entry for parent in entry[0]: semilattice_AE[parent][1].discard(key) for child in entry[1]: semilattice_AE[child][0].discard(key) for parent in entry[0]: for child in entry[1]: semilattice_AE[child][0].add(parent) semilattice_AE[parent][1].add(child) semilattice_AE.pop(key) # # End of Phase IV # return semilattice_AE