## 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 verify that for any class C whose SI sequence starts # 1, 1, 2, 3, there can be no entry in the SI sequence greater than 5 unless there is # a 5 preceding it. This function verifies it for the maximal classes whose SI sequence # starts 1, 1, 2, 3. # For a non-verbose output that only prints the end result, run the command # check_class(Av([])) # The command will complete in a few minutes with no output indicating that # no counterexample has been found. # # 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], 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 appears to have no entries greater than 5 then we probably # don't need to keep looking at this class. To verify, we enumerate the class with # the insertion encoding and check against known forms. if max(si_spec) <= 5: donesofar += 1 if verbose: print '\tThe SI sequence starts',start_seq[1:],' and appears to have nothing > 5, 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)) or check_form(g, -x**5*(x**2 + 4*x + 4)/(x**2 - 1)) or check_form(g, -2*x**8/(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)) or check_form(g, -x**5*(x**2 + 4*x + 4)/(x**2 - 1)) or check_form(g, -2*x**8/(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 '\t\t\t',g print '\n\t\tInitial terms: ',h print '\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~' # If there are entries greater than 5 and they don't have a 5 before them, we output # as a counterexample. If there are entries greater than 5 and they do have a 5 # before then, we try to kill the 5 and see if any entries greater than 5 are left. else: # First, if the SI sequence doesn't start 1, 1, 2, 3 then we add basis # elements to work toward that. for (pos, val) in enumerate(start_seq): if pos == len(C) - 1: print '\tlength not long enough to complete the computation' 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 # If there is no 5, we're in trouble. if 5 not in si_spec: print '[!!] A counterexample has been found: Av(',C.basis,') [!!]' # If there is a 5, try to turn it into a 4 and see if the elements greater # than 5 are still there. if 5 in si_spec: first_5_pos = min([i for (i,v) in enumerate(si_spec) if v == 5]) if verbose: print '\tThere is a 5 at length',first_5_pos,'that we will try to kill.' new_class_basis_additions = [P for P in C[first_5_pos] if not P.sum_decomposable()] new_classes = [Av(C.basis+[P]) for P in new_class_basis_additions] for D in new_classes: check_class(D, start_seq, verbose)