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