## NOTE: This will not run without the permpy library installed. See http://permpy.com. from permpy import * import itertools import sympy import math donesofar = 0 # Check if two functions are equal by subtracting, simplifying, and comparing to 0 def check_form(thing_to_check, form): return sympy.simplify(thing_to_check - form) == 0 # The aim of this function is to build all maximal classes whose SI sequence starts # 1, 1, 2, 3, 4, 4, and then identify which of them ever have an entry greater than 4 # in their SI sequence. The result is that only two do, Sub(U) and its symmetry under # inverse. # For a non-verbose output that only prints the classes that are found to have a 5, # run the command # check_class(Av([])) # To run in verbose mode where all maximal classes are displayed along with their # generating functions, run the command # check_class(Av([]), verbose=True) def check_class(C, start_seq=[0,1,1,2,3,4,4], verbose=False): global donesofar # We first calculate the SI sequence of the class si_spec = [len([P for P in C[i] if not P.sum_decomposable()]) for i in range(len(C))] if verbose: print '\nExamining the class Av(',C.basis,').\n\tThe SI sequence is: ',si_spec[1:] # If the SI sequence starts correctly, then we try to find the generating function # with the insertion encoding and compare it to known forms (i.e., the sequence # 1, 1, 2, 3, 4^*). If it doesn't match one of these, we print it out to be checked # by hand. if si_spec[:len(start_seq)] == start_seq: donesofar += 1 if verbose: print '\tThe SI sequence starts',start_seq[1:],' so we attempt to enumerate.' I = InsertionScheme(C.basis) f = I.gf() g = 1-1/f g_copy = sympy.simplify(g) h = g.series(n=12) x = sympy.Symbol('x') i = 0 while True: if h.coeff(x,i) < 4 and i < 8: g -= h.coeff(x,i)*x**i i += 1 else: break g = sympy.simplify(g) if verbose: print '\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~' print '\t Completed Class #: ',donesofar print '\t\tEnumerated Successfully' print '\n\t\tGF: ',g_copy print '\n\t\tInitial terms: ',h if sympy.denom(g) == 1 or check_form(g, 4*x**5/(1-x)) or check_form(g, x**5*(x**2 - 4)/(x - 1)): print '\n\t\tForm recognized, no 5s present.' else: print '\n\t\tForm not recognized, should be checked by hand for 5s.' print '\t\t\t',g print '\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~' else: if not (sympy.denom(g) == 1 or check_form(g, 4*x**5/(1-x)) or check_form(g, x**5*(x**2 - 4)/(x - 1))): print '\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~' print '\t Class to be checked by hand.' print '\t\tAv(',C.basis,')' print '\t\tEnumerated Successfully' print '\n\t\tGF: ',g_copy print '\n\t\tInitial terms: ',h print '\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~' # If the SI sequence does not yet match the specified starting sequence, we find the first place where it # disagrees and add all combinations of as many permutations of that length to the basis to make it agree. else: for (pos, val) in enumerate(start_seq): if pos == len(C) - 1: print '\tneed to go longer!' if si_spec[pos] > val: diff = si_spec[pos] - val new_class_basis_additions = list(itertools.combinations([P for P in C[pos] if not P.sum_decomposable()], diff)) if verbose: print '\tWe need to add',diff,'SI permutations of length',pos,'to the basis.' new_classes = [] for B in new_class_basis_additions: new_classes.append(Av(C.basis+list(B), 10)) for D in new_classes: check_class(D, start_seq, verbose) return