# top_boundary.py # Constructs the matrix \del_{n+2} for the complex F/(F\cap C) # for n = 4, 5, 6, 7, 8, # described in Section 6 of http://arxiv.org/abs/1507.03878 # Usage: top_boundary(n) def shapes_of(n): if n == 4: return (211,) if n == 5: return (311,221) if n == 6: return (411, 321, 222) if n == 7: return (511, 421, 331, 322) if n == 8: return (611, 521, 431, 422, 332) def bottom_shapes_of(n): if n == 4: return (1111,) if n == 5: return (1211,) if n == 6: return (1311, 1221) if n == 7: return (1411, 1321, 1222) if n == 8: return (1511, 1421, 1331, 1322) def top_types(shape): ret = list({}) if shape == 211: for pi in Permutations(4).list(): if pi[0] < pi[1] and pi[2] < pi[3]: ret.append( (211, ( (pi[0],pi[1]), (pi[2],), (pi[3],) ) )) if shape == 311: for pi in Permutations(5).list(): if pi[0] < pi[2] and pi[3] < pi[4]: ret.append( (311, ( (pi[0],pi[1],pi[2]), (pi[3],), (pi[4],) ))) if shape == 221: for pi in Permutations(5).list(): if pi[0] < min (pi[1], pi[2], pi[3]): ret.append( (221, ( (pi[0],pi[1]), (pi[2],pi[3]), (pi[4],) ))) if shape == 411: for pi in Permutations(6).list(): if pi[0] < pi[3] and pi[4] < pi[5]: ret.append( (411, ( (pi[0],pi[1],pi[2],pi[3]), (pi[4],), (pi[5],) ))) if shape == 321: for pi in Permutations(6).list(): if pi[0] < pi[2]: ret.append( (321, ((pi[0],pi[1],pi[2]), (pi[3],pi[4]), (pi[5],) ) )) if shape == 222: for pi in Permutations(6).list(): if pi[0] == 1 and pi[2] < pi[4]: ret.append( (222, ((pi[0],pi[1]), (pi[2],pi[3]), (pi[4],pi[5]) ) )) if shape == 511: for pi in Permutations(7).list(): if pi[0] < pi[4] and pi[5] < pi[6]: ret.append( (511, ((pi[0],pi[1],pi[2],pi[3],pi[4]), (pi[5],), (pi[6],)))) if shape == 421: for pi in Permutations(7).list(): if pi[0] < pi[3]: ret.append( (421, ((pi[0],pi[1],pi[2],pi[3]), (pi[4],pi[5]), (pi[6],)))) if shape == 331: for pi in Permutations(7).list(): if pi[0] < min(pi[2],pi[3],pi[5]): ret.append( (331, ((pi[0], pi[1], pi[2]), (pi[3], pi[4], pi[5]), (pi[6],)))) if shape == 322: for pi in Permutations(7).list(): if pi[0] < pi[2] and pi[3] < pi[5]: ret.append( (322, ((pi[0],pi[1],pi[2]), (pi[3],pi[4]), (pi[5],pi[6])))) if shape == 611: for pi in Permutations(8).list(): if pi[0] < pi[5] and pi[6] < pi[7]: ret.append( (611, ((pi[0],pi[1],pi[2],pi[3],pi[4],pi[5]), (pi[6],), (pi[7],)))) if shape == 521: for pi in Permutations(8).list(): if pi[0] < pi[4]: ret.append( (521, ((pi[0],pi[1],pi[2],pi[3],pi[4]), (pi[5],pi[6]), (pi[7],)))) if shape == 431: for pi in Permutations(8).list(): if pi[0] < pi[3]: ret.append( (431, ((pi[0],pi[1],pi[2],pi[3]), (pi[4],pi[5],pi[6]), (pi[7],)))) if shape == 422: for pi in Permutations(8).list(): if pi[0] < pi[3] and pi[4] < pi[6]: ret.append( (422, ((pi[0],pi[1],pi[2],pi[3]), (pi[4],pi[5]), (pi[6],pi[7])))) if shape == 332: for pi in Permutations(8).list(): if pi[0] < min(pi[2],pi[3],pi[5]): ret.append( (332, ((pi[0],pi[1],pi[2]), (pi[3],pi[4],pi[5]), (pi[6],pi[7])))) return ret def bottom_types(shape): ret = list({}) if shape == 1111: for pi in Permutations(4).list(): if pi[1] < pi[2] and pi[2] < pi[3]: ret.append( (1111, ( (pi[0],), (pi[1],), (pi[2],), (pi[3],))) ) if shape == 1211: for pi in Permutations(5).list(): if pi[3] < pi[4]: ret.append( (1211, ( (pi[0],), (pi[1],pi[2]), (pi[3],), (pi[4],)))) if shape == 1311: for pi in Permutations(6).list(): if pi[4] < pi[5]: ret.append( (1311, ( (pi[0],), (pi[1],pi[2],pi[3]), (pi[4],), (pi[5],)))) if shape == 1221: for pi in Permutations(6).list(): if pi[1] < pi[3]: ret.append( (1221, ( (pi[0],), (pi[1],pi[2]), (pi[3],pi[4]), (pi[5],)))) if shape == 1411: for pi in Permutations(7).list(): if pi[5] < pi[6]: ret.append( (1411, ( (pi[0],), (pi[1],pi[2],pi[3],pi[4]), (pi[5],), (pi[6],)))) if shape == 1321: for pi in Permutations(7).list(): ret.append( (1321, ( (pi[0],), (pi[1],pi[2],pi[3]), (pi[4],pi[5]), (pi[6],)))) if shape == 1222: for pi in Permutations(7).list(): if pi[1] < pi[3] and pi[3] < pi[5]: ret.append( (1222, ( (pi[0],), (pi[1],pi[2]), (pi[3],pi[4]), (pi[5],pi[6])))) if shape == 1511: for pi in Permutations(8).list(): if pi[6] < pi[7]: ret.append( (1511, ( (pi[0],), (pi[1],pi[2],pi[3],pi[4],pi[5]), (pi[6],), (pi[7],)))) if shape == 1421: for pi in Permutations(8).list(): ret.append( (1421, ( (pi[0],), (pi[1],pi[2],pi[3],pi[4]), (pi[5],pi[6]), (pi[7],)))) if shape == 1331: for pi in Permutations(8).list(): if pi[1] < pi[4]: ret.append( (1331, ( (pi[0],), (pi[1],pi[2],pi[3]), (pi[4],pi[5],pi[6]), (pi[7],)))) if shape == 1322: for pi in Permutations(8).list(): if pi[4] < pi[6]: ret.append( (1322, ( (pi[0],), (pi[1],pi[2],pi[3]), (pi[4],pi[5]), (pi[6],pi[7])))) return ret def normalize(bottom_type, given_coefficient): (shape, nums) = bottom_type if shape == 1111: ((a,),(b,),(c,),(d,)) = nums (bb,cc,dd) = sorted((b,c,d)) return ( (1111, ((a,),(bb,),(cc,),(dd,))), given_coefficient) if shape == 1211: ((a,), (b,c), (d,), (e,)) = nums if d < e: return ((1211, ((a,), (b,c), (d,), (e,))), given_coefficient) else: return ((1211, ((a,), (b,c), (e,), (d,))), given_coefficient) if shape == 1311: ((a,), (b,c,d), (e,), (f,)) = nums if e < f: return ((1311, ((a,), (b,c,d), (e,), (f,))), given_coefficient) else: return ((1311, ((a,), (b,c,d), (f,), (e,))), given_coefficient) if shape == 1221: ((a,), (b,c), (d,e), (f,)) = nums if b < d: return ((1221, ((a,), (b,c), (d,e), (f,))), given_coefficient) else: return ((1221, ((a,), (d,e), (b,c), (f,))), -1*given_coefficient) if shape == 1411: ((a,), (b,c,d,e,), (f,), (g,)) = nums if f < g: return ((1411, ((a,), (b,c,d,e,), (f,), (g,))), given_coefficient) else: return ((1411, ((a,), (b,c,d,e,), (g,), (f,))), given_coefficient) if shape == 1321: return (bottom_type, given_coefficient) if shape == 1222: ((a,), (b,c), (d,e), (f,g)) = nums if b < d and d < f: return ((1222, ((a,), (b,c), (d,e), (f,g))), given_coefficient) if b < f and f < d: return ((1222, ((a,), (b,c), (f,g), (d,e))), -1*given_coefficient) if d < b and b < f: return ((1222, ((a,), (d,e), (b,c), (f,g))), -1*given_coefficient) if f < b and b < d: return ((1222, ((a,), (f,g), (b,c), (d,e))), given_coefficient) if d < f and f < b: return ((1222, ((a,), (d,e), (f,g), (b,c))), given_coefficient) if f < d and d < b: return ((1222, ((a,), (f,g), (d,e), (b,c))), -1*given_coefficient) if shape == 1511: ((a,), (b,c,d,e,f), (g,), (h,)) = nums if g < h: return ((1511, ((a,), (b,c,d,e,f), (g,), (h,))), given_coefficient) else: return ((1511, ((a,), (b,c,d,e,f), (h,), (g,))), given_coefficient) if shape == 1421: return (bottom_type, given_coefficient) if shape == 1331: ((a,), (b,c,d), (e,f,g), (h,)) = nums if b < e: return ((1331, ((a,), (b,c,d), (e,f,g), (h,))), given_coefficient) else: return ((1331, ((a,), (e,f,g), (b,c,d), (h,))), given_coefficient) if shape == 1322: ((a,), (b,c,d), (e,f), (g,h)) = nums if e < g: return ((1322, ((a,), (b,c,d), (e,f), (g,h))), given_coefficient) else: return ((1322, ((a,), (b,c,d), (g,h), (e,f))), -1*given_coefficient) def boundary_of(typ): (shape,nums) = typ if shape == 211: ((a,b),(c,),(d,)) = nums return ( normalize( (1111,((a,),(b,),(c,),(d,))), 1), normalize( (1111,((b,),(a,),(c,),(d,))), -1) ) if shape == 311: ((a,b,c),(d,),(e,)) = nums return ( normalize( (1211,((a,), (b,c), (d,), (e,))), 1), normalize( (1211,((c,), (b,a), (d,), (e,))), 1) ) if shape == 221: ((a,b),(c,d),(e,)) = nums return ( normalize( (1211,((a,), (c,d), (b,), (e,))), 1), normalize( (1211,((b,), (d,c), (a,), (e,))), -1), normalize( (1211,((c,), (a,b), (d,), (e,))), -1), normalize( (1211,((d,), (b,a), (c,), (e,))), 1) ) if shape == 411: ((a,b,c,d), (e,), (f,)) = nums return ( normalize( (1311, ((a,), (b,c,d), (e,), (f,))), 1), normalize( (1311, ((d,), (c,b,a), (e,), (f,))), 1) ) if shape == 321: ((a,b,c), (d,e), (f,)) = nums return ( normalize( (1221, ((a,), (b,c), (d,e), (f,))), 1), normalize( (1221, ((c,), (b,a), (e,d), (f,))), 1), normalize( (1311, ((d,), (a,b,c), (e,), (f,))), 1), normalize( (1311, ((e,), (c,b,a), (d,), (f,))), 1) ) if shape == 222: ((a,b), (c,d), (e,f)) = nums return ( normalize( (1221, ((a,), (c,d), (e,f), (b,))), 1), normalize( (1221, ((b,), (d,c), (f,e), (a,))), -1), normalize( (1221, ((c,), (a,b), (e,f), (d,))), -1), normalize( (1221, ((d,), (b,a), (f,e), (c,))), 1), normalize( (1221, ((e,), (a,b), (c,d), (f,))), 1), normalize( (1221, ((f,), (b,a), (d,c), (e,))), -1) ) if shape == 511: ((a,b,c,d,e), (f,), (g,)) = nums return ( normalize( (1411, ((a,), (b,c,d,e), (f,), (g,))), 1), normalize( (1411, ((e,), (d,c,b,a), (f,), (g,))), -1) ) if shape == 421: ((a,b,c,d), (e,f), (g,)) = nums return ( normalize( (1321, ((a,), (b,c,d), (e,f), (g,))), 1), normalize( (1321, ((d,), (c,b,a), (f,e), (g,))), 1), normalize( (1411, ((e,), (a,b,c,d), (f,), (g,))), -1), normalize( (1411, ((f,), (d,c,b,a), (e,), (g,))), -1) ) if shape == 331: ((a,b,c), (d,e,f), (g,)) = nums return ( normalize( (1321, ((a,), (d,e,f), (b,c), (g,))), 1), normalize( (1321, ((c,), (f,e,d), (b,a), (g,))), -1), normalize( (1321, ((d,), (a,b,c), (e,f), (g,))), 1), normalize( (1321, ((f,), (c,b,a), (e,d), (g,))), -1) ) if shape == 322: ((a,b,c), (d,e), (f,g)) = nums return ( normalize( (1222, ((a,), (b,c), (d,e), (f,g))), 1), normalize( (1222, ((c,), (b,a), (e,d), (g,f))), 1), normalize( (1321, ((d,), (a,b,c), (f,g), (e,))), 1), normalize( (1321, ((e,), (c,b,a), (g,f), (d,))), 1), normalize( (1321, ((f,), (a,b,c), (d,e), (g,))), -1), normalize( (1321, ((g,), (c,b,a), (e,d), (f,))), -1) ) if shape == 611: ((a,b,c,d,e,f), (g,), (h,)) = nums return ( normalize( (1511, ((a,), (b,c,d,e,f), (g,), (h,))), 1), normalize( (1511, ((f,), (e,d,c,b,a), (g,), (h,))), -1) ) if shape == 521: ((a,b,c,d,e), (f,g), (h,)) = nums return ( normalize( (1421, ((a,), (b,c,d,e), (f,g), (h,))), 1), normalize( (1421, ((e,), (d,c,b,a), (g,f), (h,))), -1), normalize( (1511, ((f,), (a,b,c,d,e), (g,), (h,))), 1), normalize( (1511, ((g,), (e,d,c,b,a), (f,), (h,))), -1) ) if shape == 431: ((a,b,c,d), (e,f,g), (h,)) = nums return ( normalize( (1331, ((a,), (b,c,d), (e,f,g), (h,))), 1), normalize( (1331, ((d,), (c,b,a), (g,f,e), (h,))), -1), normalize( (1421, ((e,), (a,b,c,d), (f,g), (h,))), -1), normalize( (1421, ((g,), (d,c,b,a), (f,e), (h,))), 1) ) if shape == 422: ((a,b,c,d), (e,f), (g,h)) = nums return ( normalize( (1322, ((a,), (b,c,d), (e,f), (g,h))), 1), normalize( (1322, ((d,), (c,b,a), (f,e), (h,g))), 1), normalize( (1421, ((e,), (a,b,c,d), (g,h), (f,))), -1), normalize( (1421, ((f,), (d,c,b,a), (h,g), (e,))), -1), normalize( (1421, ((g,), (a,b,c,d), (e,f), (h,))), 1), normalize( (1421, ((h,), (d,c,b,a), (f,e), (g,))), 1) ) if shape == 332: ((a,b,c), (d,e,f), (g,h)) = nums return ( normalize( (1322, ((a,), (d,e,f), (b,c), (g,h))), 1), normalize( (1322, ((c,), (f,e,d), (b,a), (h,g))), -1), normalize( (1322, ((d,), (a,b,c), (e,f), (g,h))), 1), normalize( (1322, ((f,), (c,b,a), (e,d), (h,g))), -1), normalize( (1331, ((g,), (a,b,c), (d,e,f), (h,))), 1), normalize( (1331, ((h,), (c,b,a), (f,e,d), (g,))), -1) ) def list_columns(n): ret = list({}) for shape in shapes_of(n): ret.extend(top_types(shape)) return ret def column_of (n): list_columns_n = list_columns(n) return dict((list_columns_n[i], i) for i in range(len(list_columns_n))) def list_rows(n): ret = list({}) for shape in bottom_shapes_of(n): ret.extend(bottom_types(shape)) return ret def row_of(n): list_rows_n = list_rows(n) return dict((list_rows_n[i], i) for i in range(len(list_rows_n))) def top_boundary(n): row_of_n = row_of(n) column_of_n = column_of(n) ret = matrix(len(list_rows(n)),len(list_columns(n)), sparse=True) for shape in shapes_of(n): for typ in top_types(shape): boundary = boundary_of(typ) for (bottom_type, coefficient) in boundary: ret[ row_of_n[bottom_type], column_of_n[typ] ] = coefficient return ret