Section 8

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

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

The above code implements the following algorithm.

Algorithm Given \(d\in\{1,\dotsc,9\}\), compute the collection \(\mathcal S\) of all size-\(\leq 6\) positive supports of degree-\(d\) fundamental outcomes.

Step 1: Construct \(\mathcal C\).

\(\mathcal D \gets \{(\{0,\dotsc,a\}\times\{0,\dotsc,b\})\setminus \{(0,0)\} \mid (a,b)\in V_d\setminus V_{d-1}\}\)

\(\mathcal A^+ \gets \{\{(i,j)\mid 0\leq j\leq k,k-j\leq i\leq d-j, j\equiv k\mod 2\}\mid k\in\{1,\ldots,d\}\}\)

\(\mathcal A^- \gets \{\{(i,j)\mid 0\leq j\leq k,k-j\leq i\leq d-j, j\not\equiv k\mod 2\}\mid k\in\{1,\ldots,d\}\}\)

\(\mathcal B^+ \gets \{\{(j,i)\mid (i,j)\in A\}\mid A\in\mathcal{A}^+\}\)

\(\mathcal B^- \gets \{\{(j,i)\mid (i,j)\in A\}\mid A\in\mathcal{A}^-\}\)

\(\mathcal C \gets \mathcal{D}\cup\mathcal{A}^+\cup\mathcal{A}^-\cup\mathcal{B}^+\cup\mathcal{B}^-\)

Step 2: Initialize \(\mathcal S\).

\(\mathcal S \gets \{\emptyset\}\)

for all \(C\in \mathcal C\) do

  for all \(S\in \mathcal S\) with \(\mathcal S\cap C=\emptyset\) do

    \(\mathcal S \gets \mathcal S \setminus \{S\}\)

    if \(\# S \leq 5\) then \(\mathcal S \gets \mathcal S \cup \{S\cup \{c\}\mid c\in C\}\)

\(\mathcal S \gets \{S\in \mathcal S \mid S \text{ inclusion-minimal among elements of }\mathcal S\}\)

Step 3: Extend \(\mathcal S\).

for all \(k\) from \(1\) to \(6\) do

  for all \(S\in\mathcal S\) with \(\# S=k\) do

    if there exists no outcome \(w\in\mathbb Z^{V_d}\setminus\{0\}\) with \(\operatorname{supp}(w)\subseteq S\cup \{0,0\}\) then

      \(\mathcal S \gets \mathcal S\setminus \{S\}\)

      if \(k\leq 5\) then \(\mathcal S\gets \mathcal S\cup\{S\cup \{(i,j)\}\mid (i,j)\in V_d\setminus(S\cup \{(0,0)\})\}\)

  \(\mathcal S \gets \{S\in \mathcal S \mid S \text{ inclusion-minimal among elements of }\mathcal S\}\)

Step 4: Prune \(\mathcal S\).

for all \(S\in\mathcal S\) do

  \(L_S\gets \{w\in V_d \text{ outcome} \mid \mathop{\mathrm{supp}}(w)\subseteq S\cup \{(0,0)\}\}\)

  if \(\dim L_S\geq 2\) then \(\mathcal S\gets \mathcal S\setminus \{S\}\)

  if \(L_S = \langle w\rangle\) and \(w\) is not valid then \(\mathcal S\gets \mathcal S\setminus \{S\}\)

We deduce the correctness of the algorithm as follows. By Remark 6.11, at the end of Step 1 we have \(\mathop{\mathrm{supp}}^+(w)\cap C \neq \emptyset\) for all valid degree-\(d\) outcomes \(w\) and all \(C\in \mathcal C\). We use this to prove the following:

Lemma After each iteration of any loop the following property of the collection \(\mathcal S\) holds: for all fundamental degree-\(d\) outcomes \(w\) with \(\#\mathop{\mathrm{supp}}^+(w)\leq 6\) there is a set \(S\in\mathcal S\) such that \(S\subseteq \mathop{\mathrm{supp}}^+(w)\).

Proof First note that the property holds for \(\mathcal S = \{\emptyset\}\). Let \(w\) be a fundamental degree-\(d\) outcome with \(\#\mathop{\mathrm{supp}}(w)\leq 6\). We first consider an iteration of the inner loop in Step 2, indexed by \(C\in\mathcal C\) and \(S\in\mathcal S\). Before this iteration, the property holds. Hence we may assume that \(S\subseteq \mathop{\mathrm{supp}}^+(w)\). The only change can occur when \(S\cap C = \emptyset\). In this case there exists an element \(c\in C\) with \(c\in\mathop{\mathrm{supp}}^+(w)\). In particular we have \(\#S\leq 5\) since \(\#\mathop{\mathrm{supp}}^+(w)\leq 6\). But then \(S\cap \{c\}\), a subset of \(\mathop{\mathrm{supp}}^+(w)\), is added to \(\mathcal S\).

Now consider an iteration of the inner loop in Step 3, indexed by \(S\). Again we may assume that \(S\subseteq \mathop{\mathrm{supp}}^+(w)\). Distinguishing beteween the cases \(S=\mathop{\mathrm{supp}}^+(w)\) and \(S\subsetneq \mathop{\mathrm{supp}}^+(w)\) shows that the desired property will hold at the end of the iteration.

Finally, consider an iteration of the loop in Step 4, indexed by \(S\), with \(S\subseteq \mathop{\mathrm{supp}}^+(w)\). Having gone through Step 3 and because of the minimality of the elements in \(\mathcal S\), we know that there exists an outcome \(w'\) with \(\mathop{\mathrm{supp}}(w')\setminus\{(0,0)\} = S\). The existence of \(w'\) implies a linear relation among the monomials \(t^{i_\nu}(1-t)^{j_\nu}\) for \((i_\nu,j_\nu)\in S\). Thus we must have \(S = \mathop{\mathrm{supp}}^+(w)\) since \(w\) is fundamental, hence \(S\) is not removed in this iteration. End of Proof.

In the proof of the above lemma we showed that at the end our algorithm, for each degree-\(d\) fundamental outcome \(w\) with \(\#\mathop{\mathrm{supp}}^+(w)\leq 6\) there exists \(S\in\mathcal S\) with \(S = \mathop{\mathrm{supp}}^+(w)\). On the other hand, at the end of Step 3 we have \(\dim L_S \geq 1\) for all \(S\in \mathcal S\). At the end of Step 4, for all \(S\in \mathcal S\) there exists a fundamental degree-\(d\) outcome with \(\mathop{\mathrm{supp}}^+(w)\subseteq S\). By the minimality of the elements of \(\mathcal S\) and the above lemma we conclude that at the end of the algorithm,

\[\mathcal{S} = \{\operatorname{supp}^+(w)\mid w \text{ is a degree-$d$ fundamental outcome with } \#\operatorname{supp}^+(w)\leq 6\}.\]

This finishes our proof of correctness.

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\).

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)]