# 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.

[2]:

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]
toadd = [supp for supp in toadd if not supp in poss[i+1]]
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 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.

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