Section 8

We are looking for fundamental models of degree \(d\). At a place \(S\subseteq V_d\setminus\{(0,0)\}\) of size \(>d+1\) cannot be a fundamental model.

[1]:
def deg(i,j):
    return i+j

def draw_support(supp):
    for j in range(d,-1,-1):
        res = ''
        for i in range(d+1-j):
            if ((i,j) in supp):
                if (i,j)==(0,0):
                    res = res + '-'
                else:
                    res = res + 'x'
            else:
                res = res + '·'
            res = res + ' '
        print(res)
    print('')

def model(supp):
    v = Matrix([[binomial(d-deg(i,j),a-i) for (i,j) in [(0,0)]+supp] for a in range(d+1)]).right_kernel().gens()[0]
    return [(-v[i+1]/v[0],supp[i][0],supp[i][1]) for i in range(len(supp))]

def identify_S2(poss):
    res = []
    for lst in poss:
        keep = [True for el in lst]
        for k in range(len(lst)):
            for ell in range(k+1,len(lst)):
                if min([((j,i) in lst[ell]) for (i,j) in lst[k]]):
                    keep[ell]=False
        res.append([lst[x] for x in range(len(lst)) if keep[x]])
    return res

def search_fundamentals(d,k=-1):
    if k==-1:
        k=d+1
    print('d: '+str(d))
    print('expected minimial positive support: '+str(ceil((d+3)/2)))

    Vd = [(i,j) for i in range(d+1) for j in range(d+1) if deg(i,j)<=d]

    R = PolynomialRing(QQ,['x_'+str(i)+'_'+str(j) for i in range(d+1) for j in range(d+1) if deg(i,j)<=d])
    xx = [[R('x_'+str(i)+'_'+str(j)) for j in range(d+1) if deg(i,j)<=d] for i in range(d+1)]

    psi = [(-1)^k * sum([(-1)^j*binomial(i,k-j)*xx[i][j] for (i,j) in Vd]) for k in range(d+1)]
    psibar = [(-1)^k * sum([(-1)^i*binomial(j,k-i)*xx[i][j] for (i,j) in Vd]) for k in range(d+1)]
    varphi = [sum([binomial(d-deg(i,j),a-i)*xx[i][j] for (i,j) in Vd]) for a in range(d+1)]
    eqns = psi+psibar+varphi

    def var2tup(var):
        for (i,j) in Vd:
            if var==xx[i][j]:
                return (i,j)

    def make_conds(eqn):
        res = []
        if eqn==0:
            return res
        elif eqn.coefficient(xx[0][0])==0:
            pos = [var2tup(var) for var in R.gens() if eqn.coefficient(var)>0]
            res.append(pos)
            neg = [var2tup(var) for var in R.gens() if eqn.coefficient(var)<0]
            res.append(neg)
        elif eqn.coefficient(xx[0][0])>0:
            pos = [var2tup(var) for var in R.gens() if (eqn.coefficient(var)>0 and var!=xx[0][0])]
            res.append(pos)
        else:
            neg = [var2tup(var) for var in R.gens() if (eqn.coefficient(var)<0 and var!=xx[0][0])]
            res.append(neg)
        return res

    conds = []
    for eqn in eqns:
        conds = conds + make_conds(eqn)

    def unique(lst):
        res = []
        for el in lst:
            if el not in res:
                res.append(el)
        return res

    def sublist(lst1, lst2):
        intersection = [element for element in lst1 if element in lst2]
        return lst1 == intersection

    def reduce(lst):
        lst = unique(lst)
        keep = [True for i in range(len(lst))]
        for i in range(len(lst)):
            for j in range(len(lst)):
                if i!=j:
                    if sublist(lst[j], lst[i]):
                        keep[i] = False
        return [lst[i] for i in range(len(lst)) if keep[i]]

    conds = reduce(conds)

    def reduce(lstolst):
        for lst in lstolst:
            lst = unique(lst)
        for i in range(len(lstolst)-1):
            for j in range(i+1,len(lstolst)):
                length = len(lstolst[j])
                keep = [True for k in range(length)]
                for lsti in lstolst[i]:
                    for k in range(length):
                        if sublist(lsti, lstolst[j][k]):
                            keep[k] = False
                lstolst[j] = [lstolst[j][k] for k in range(length) if keep[k]]
        return lstolst

    poss=[[[]]]+[[] for i in range(k)]
    #print([len(poss[i]) for i in range(k+1)])
    todo = [cond for cond in conds]
    while len(todo)>0:
        cond = todo[0]
        todo.remove(cond)
        poss_new = [[] for i in range(k+1)]
        for i in range(k+1):
            for supp in poss[i]:
                if len([True for pt in supp if pt in cond])>0:
                    poss_new[i].append(supp)
                elif len(supp)<=k-1: #if we need to increase to size k+1, discard instead
                    for pt in cond:
                        poss_new[i+1].append(supp+[pt])
                        poss_new[i+1][-1].sort()
        poss = reduce(poss_new)
        #print([len(poss[i]) for i in range(k+1)])

    def check_exists(supp):
        A = Matrix([[binomial(d-deg(i,j),a-i) for (i,j) in supp] for a in range(d+1)])
        if A.rank() < len(supp):
            return True
        return False

    for i in range(k):
        todo = []
        for supp in poss[i]:
            if not check_exists([(0,0)]+supp):
                todo.append(supp)
        for supp in todo:
            poss[i].remove(supp)
        toadd = [supp+[pt] for supp in todo for pt in Vd[1:] if not pt in supp]
        for ell in range(len(toadd)):
            toadd[ell].sort()
        toadd = unique(toadd)
        toadd = [supp for supp in toadd if not supp in poss[i+1]]
        for supp in toadd:
            poss[i+1].append(supp)
        for j in range(i+2,k+1):
            length = len(poss[j])
            keep = [True for ell in range(length)]
            for supp in toadd:
                for ell in range(length):
                    if sublist(supp, poss[j][ell]):
                        keep[ell] = False
                poss[j] = [poss[j][ell] for ell in range(length) if keep[ell]]
        #print(len(poss[i]))
    todo = []
    for supp in poss[k]:
        if not check_exists([(0,0)]+supp):
            todo.append(supp)
    for supp in todo:
        poss[k].remove(supp)
    #print(len(poss[k]))

    def check_degenerate_signs(supp):
        A = Matrix([[binomial(d-deg(i,j),a-i) for (i,j) in [(0,0)]+supp] for a in range(d+1)])
        rk = A.rank()
        if rk < len(supp):
            return True
        v = A.right_kernel().gens()[0]
        return max([v[0]*v[i+1]>=0 for i in range(len(supp))])

    for i in range(k+1):
        todo = []
        for supp in poss[i]:
            if check_degenerate_signs(supp):
                todo.append(supp)
        for supp in todo:
            poss[i].remove(supp)
    print([len(poss[i]) for i in range(2,k+1)])

    poss = identify_S2(poss)
    print([len(poss[i]) for i in range(2,k+1)])

    return poss
[2]:
for d in range(1,6):
    poss = search_fundamentals(d)
    print('')
for d in range(6,10):
    poss = search_fundamentals(d,6)
    print('')
d: 1
expected minimial positive support: 2
[1]
[1]

d: 2
expected minimial positive support: 3
[0, 3]
[0, 2]

d: 3
expected minimial positive support: 3
[0, 1, 12]
[0, 1, 7]

d: 4
expected minimial positive support: 4
[0, 0, 4, 82]
[0, 0, 2, 43]

d: 5
expected minimial positive support: 4
[0, 0, 2, 38, 602]
[0, 0, 1, 23, 306]

d: 6
expected minimial positive support: 5
[0, 0, 0, 10, 254]
[0, 0, 0, 5, 129]

d: 7
expected minimial positive support: 5
[0, 0, 0, 4, 88]
[0, 0, 0, 3, 46]

d: 8
expected minimial positive support: 6
[0, 0, 0, 0, 24]
[0, 0, 0, 0, 12]

d: 9
expected minimial positive support: 6
[0, 0, 0, 0, 2]
[0, 0, 0, 0, 1]

We draw the degree-\(7\) fundamental outcomes with a possitive support of size \(5\).

[3]:
d = 7
poss = search_fundamentals(d,5)
for supp in poss[5]:
    draw_support([(0,0)]+supp)

def print_model_from_supp(supp):
    A = Matrix([[binomial(d-deg(i,j),a-i) for (i,j) in [(0,0)]+supp] for a in range(d+1)])
    v = A.right_kernel().gens()[0]
    print([(-v[nu+1]/v[0],supp[nu][0],supp[nu][1]) for nu in range(len(supp))])

for supp in poss[5]:
    print_model_from_supp(supp)
d: 7
expected minimial positive support: 5
[0, 0, 0, 4]
[0, 0, 0, 3]
x
· ·
· x ·
· · · ·
· · · · ·
· · · · · ·
· x · · · x ·
- · · · · · · x

x
· ·
· · ·
· · · ·
· x · x ·
· · · · · ·
· · · x · · ·
- · · · · · · x

x
· ·
· · ·
· · · ·
· x · · ·
· · · x · ·
· · · · · x ·
- · · · · · · x

[(1, 0, 7), (7/2, 1, 1), (7/2, 1, 5), (7/2, 5, 1), (1, 7, 0)]
[(1, 0, 7), (7, 1, 3), (7, 3, 1), (7, 3, 3), (1, 7, 0)]
[(1, 0, 7), (7, 1, 3), (14, 3, 2), (7, 5, 1), (1, 7, 0)]