Checking whether a real polynomial of 21 variables is non-negative

asked 2019-09-05 22:37:42 +0200

updated 2019-09-07 02:13:14 +0200

Let $P$ be a real polynomial with $n$ variables.

Question 1: Is there a SageMath function deciding whether $P$ is non-negative?

By non-negative I mean that for all $v \in \mathbb{R}^n$ we have $P(v) \ge 0$.

Question 2: Is it workable for $n = 21$?


Here is the poIynomial I am interested in (where the variables are $x_{s,i}$, with $s = 1,2,3$ and $i = 1,2,\dots, \ell$):
$$P=\sum_{k=1}^{\ell} \frac{1}{n_k} \prod_{s=1}^3 (\sum_{i,j} n_{i,j}^k x_{s,i} x_{s,j})$$ where $n_i$ and $n_{i,j}^k$ are non-negative integers given by the following lists (here $\ell = 7$):
[for those interested it corresponds to a fusion ring, see here]

dim=[1,5,5,5,6,7,7]
M=[
[[1,0,0,0,0,0,0],[0,1,0,0,0,0,0],[0,0,1,0,0,0,0],[0,0,0,1,0,0,0],[0,0,0,0,1,0,0],[0,0,0,0,0,1,0],[0,0,0,0,0,0,1]],[[0,1,0,0,0,0,0],[1,1,0,1,0,1,1],[0,0,1,0,1,1,1],[0,1,0,0,1,1,1],[0,0,1,1,1,1,1],[0,1,1,1,1,1,1],[0,1,1,1,1,1,1]],[[0,0,1,0,0,0,0],[0,0,1,0,1,1,1],[1,1,1,0,0,1,1],[0,0,0,1,1,1,1],[0,1,0,1,1,1,1],[0,1,1,1,1,1,1],[0,1,1,1,1,1,1]],[[0,0,0,1,0,0,0],[0,1,0,0,1,1,1],[0,0,0,1,1,1,1],[1,0,1,1,0,1,1],[0,1,1,0,1,1,1],[0,1,1,1,1,1,1],[0,1,1,1,1,1,1]],[[0,0,0,0,1,0,0],[0,0,1,1,1,1,1],[0,1,0,1,1,1,1],[0,1,1,0,1,1,1],[1,1,1,1,1,1,1],[0,1,1,1,1,2,1],[0,1,1,1,1,1,2]],[[0,0,0,0,0,1,0],[0,1,1,1,1,1,1],[0,1,1,1,1,1,1],[0,1,1,1,1,1,1],[0,1,1,1,1,2,1],[1,1,1,1,2,1,2],[0,1,1,1,1,2,2]],[[0,0,0,0,0,0,1],[0,1,1,1,1,1,1],[0,1,1,1,1,1,1],[0,1,1,1,1,1,1],[0,1,1,1,1,1,2],[0,1,1,1,1,2,2],[1,1,1,1,2,2,1]]
]

Here is the code generating the polynomial:

cpdef ExplicitPolynomial(list dim,list M):
    cdef int l,i,j,k,s
    l=len(dim)
    return sum([prod([sum([sum([M[i][j][k]*var('x_%d' % int(l*s+i))*var('x_%d' % int(l*s+j)) for i in range(l)]) for j in range(l)]) for s in range(3)])/dim[k] for k in range(l)])

Here is the polynomial explicitly:

sage: ExplicitPolynomial(dim,M)
(x_0^2 + x_1^2 + x_2^2 + x_3^2 + x_4^2 + x_5^2 + x_6^2)*(x_10^2 + x_11^2 + x_12^2 + x_13^2 + x_7^2 + x_8^2 + x_9^2)*(x_14^2 + x_15^2 + x_16^2 + x_17^2 + x_18^2 + x_19^2 + x_20^2) + 1/5*(2*x_0*x_1 + x_1^2 + x_2^2 + 2*x_1*x_3 + 2*x_2*x_4 + 2*x_3*x_4 + x_4^2 + 2*x_1*x_5 + 2*x_2*x_5 + 2*x_3*x_5 + 2*x_4*x_5 + x_5^2 + 2*x_1*x_6 + 2*x_2*x_6 + 2*x_3*x_6 + 2*x_4*x_6 + 2*x_5*x_6 + x_6^2)*(2*x_10*x_11 + x_11^2 + 2*x_10*x_12 + 2*x_11*x_12 + x_12^2 + 2*x_10*x_13 + 2*x_11*x_13 + 2*x_12*x_13 + x_13^2 + 2*x_10*x_8 + 2*x_12*x_8 + 2*x_13*x_8 + 2*x_7*x_8 + x_8^2 + 2*x_11*x_9 + 2*x_12*x_9 + 2*x_13*x_9 + x_9^2)*(2*x_14*x_15 + x_15^2 + x_16^2 + 2*x_15*x_17 + 2*x_16*x_18 + 2*x_17*x_18 + x_18^2 + 2*x_15*x_19 + 2*x_16*x_19 + 2*x_17*x_19 + 2*x_18*x_19 + x_19^2 + 2*x_15*x_20 + 2*x_16*x_20 + 2*x_17*x_20 + 2*x_18*x_20 + 2*x_19*x_20 + x_20^2) + 1/7*(x_1^2 + 2*x_1*x_2 + x_2^2 + 2*x_1*x_3 + 2*x_2*x_3 + x_3^2 + 2*x_1*x_4 + 2*x_2*x_4 + 2*x_3*x_4 + x_4^2 + 2*x_0*x_5 + 2*x_1*x_5 + 2*x_2*x_5 + 2*x_3*x_5 + 4*x_4*x_5 + x_5^2 + 2*x_1*x_6 + 2*x_2*x_6 + 2*x_3*x_6 + 2*x_4*x_6 + 4*x_5*x_6 + 2*x_6^2)*(x_10^2 + 2*x_10*x_11 + x_11^2 + 2*x_10*x_12 + 4*x_11*x_12 + x_12^2 + 2*x_10*x_13 + 2*x_11*x_13 + 4*x_12*x_13 + 2*x_13^2 + 2*x_12*x_7 + 2*x_10*x_8 + 2*x_11*x_8 + 2*x_12*x_8 + 2*x_13*x_8 + x_8^2 + 2*x_10*x_9 + 2*x_11*x_9 + 2*x_12*x_9 + 2*x_13*x_9 + 2*x_8*x_9 + x_9^2)*(x_15^2 + 2*x_15*x_16 + x_16^2 + 2*x_15*x_17 + 2*x_16*x_17 + x_17^2 + 2*x_15*x_18 + 2*x_16*x_18 + 2*x_17*x_18 + x_18^2 + 2*x_14*x_19 + 2*x_15*x_19 + 2*x_16*x_19 + 2*x_17*x_19 + 4*x_18*x_19 + x_19^2 + 2*x_15*x_20 + 2*x_16*x_20 + 2*x_17*x_20 + 2*x_18*x_20 + 4*x_19*x_20 + 2*x_20^2) + 1/7*(x_1^2 + 2*x_1*x_2 + x_2^2 + 2*x_1*x_3 + 2*x_2*x_3 + x_3^2 + 2*x_1*x_4 + 2*x_2*x_4 + 2*x_3*x_4 + x_4^2 + 2*x_1*x_5 + 2*x_2*x_5 + 2*x_3*x_5 + 2*x_4*x_5 + 2*x_5^2 + 2*x_0*x_6 + 2*x_1*x_6 + 2*x_2*x_6 + 2*x_3*x_6 + 4*x_4*x_6 + 4*x_5*x_6 + x_6^2)*(x_10^2 + 2*x_10*x_11 + x_11^2 + 2*x_10*x_12 + 2*x_11*x_12 + 2*x_12^2 + 2*x_10*x_13 + 4*x_11*x_13 + 4*x_12*x_13 + x_13^2 + 2*x_13*x_7 + 2*x_10*x_8 + 2*x_11*x_8 + 2*x_12*x_8 + 2*x_13*x_8 + x_8^2 + 2*x_10*x_9 + 2*x_11*x_9 + 2*x_12*x_9 + 2*x_13*x_9 + 2*x_8*x_9 + x_9^2)*(x_15^2 + 2*x_15*x_16 + x_16^2 + 2*x_15*x_17 + 2*x_16*x_17 + x_17^2 + 2*x_15*x_18 + 2*x_16*x_18 + 2*x_17*x_18 + x_18^2 + 2*x_15*x_19 + 2*x_16*x_19 + 2*x_17*x_19 + 2*x_18*x_19 + 2*x_19^2 + 2*x_14*x_20 + 2*x_15*x_20 + 2*x_16*x_20 + 2*x_17*x_20 + 4*x_18*x_20 + 4*x_19*x_20 + x_20^2) + 1/5*(x_1^2 + 2*x_0*x_3 + 2*x_2*x_3 + x_3^2 + 2*x_1*x_4 + 2*x_2*x_4 + x_4^2 + 2*x_1*x_5 + 2*x_2*x_5 + 2*x_3*x_5 + 2*x_4*x_5 + x_5^2 + 2*x_1*x_6 + 2*x_2*x_6 + 2*x_3*x_6 + 2*x_4*x_6 + 2*x_5*x_6 + x_6^2)*(x_10^2 + x_11^2 + 2*x_10*x_12 + 2*x_11*x_12 + x_12^2 + 2*x_10*x_13 + 2*x_11*x_13 + 2*x_12*x_13 + x_13^2 + 2*x_10*x_7 + 2*x_11*x_8 + 2*x_12*x_8 + 2*x_13*x_8 + x_8^2 + 2*x_10*x_9 + 2*x_11*x_9 + 2*x_12*x_9 + 2*x_13*x_9)*(x_15^2 + 2*x_14*x_17 + 2*x_16*x_17 + x_17^2 + 2*x_15*x_18 + 2*x_16*x_18 + x_18^2 + 2*x_15*x_19 + 2*x_16*x_19 + 2*x_17*x_19 + 2*x_18*x_19 + x_19^2 + 2*x_15*x_20 + 2*x_16*x_20 + 2*x_17*x_20 + 2*x_18*x_20 + 2*x_19*x_20 + x_20^2) + 1/5*(x_10^2 + 2*x_10*x_11 + x_11^2 + 2*x_10*x_12 + 2*x_11*x_12 + x_12^2 + 2*x_10*x_13 + 2*x_11*x_13 + 2*x_12*x_13 + x_13^2 + 2*x_11*x_8 + 2*x_12*x_8 + 2*x_13*x_8 + 2*x_12*x_9 + 2*x_13*x_9 + 2*x_7*x_9 + 2*x_8*x_9 + x_9^2)*(2*x_14*x_16 + 2*x_15*x_16 + x_16^2 + x_17^2 + 2*x_15*x_18 + 2*x_17*x_18 + x_18^2 + 2*x_15*x_19 + 2*x_16*x_19 + 2*x_17*x_19 + 2*x_18*x_19 + x_19^2 + 2*x_15*x_20 + 2*x_16*x_20 + 2*x_17*x_20 + 2*x_18*x_20 + 2*x_19*x_20 + x_20^2)*(2*x_0*x_2 + 2*x_1*x_2 + x_2^2 + x_3^2 + 2*x_1*x_4 + 2*x_3*x_4 + x_4^2 + 2*x_1*x_5 + 2*x_2*x_5 + 2*x_3*x_5 + 2*x_4*x_5 + x_5^2 + 2*x_1*x_6 + 2*x_2*x_6 + 2*x_3*x_6 + 2*x_4*x_6 + 2*x_5*x_6 + x_6^2) + 1/6*(2*x_10*x_11 + x_11^2 + 2*x_10*x_12 + 2*x_11*x_12 + 2*x_12^2 + 2*x_10*x_13 + 2*x_11*x_13 + 2*x_12*x_13 + 2*x_13^2 + 2*x_11*x_7 + 2*x_10*x_8 + 2*x_11*x_8 + 2*x_12*x_8 + 2*x_13*x_8 + 2*x_10*x_9 + 2*x_11*x_9 + 2*x_12*x_9 + 2*x_13*x_9 + 2*x_8*x_9)*(2*x_15*x_16 + 2*x_15*x_17 + 2*x_16*x_17 + 2*x_14*x_18 + 2*x_15*x_18 + 2*x_16*x_18 + 2*x_17*x_18 + x_18^2 + 2*x_15*x_19 + 2*x_16*x_19 + 2*x_17*x_19 + 2*x_18*x_19 + 2*x_19^2 + 2*x_15*x_20 + 2*x_16*x_20 + 2*x_17*x_20 + 2*x_18*x_20 + 2*x_19*x_20 + 2*x_20^2)*(2*x_1*x_2 + 2*x_1*x_3 + 2*x_2*x_3 + 2*x_0*x_4 + 2*x_1*x_4 + 2*x_2*x_4 + 2*x_3*x_4 + x_4^2 + 2*x_1*x_5 + 2*x_2*x_5 + 2*x_3*x_5 + 2*x_4*x_5 + 2*x_5^2 + 2*x_1*x_6 + 2*x_2*x_6 + 2*x_3*x_6 + 2*x_4*x_6 + 2*x_5*x_6 + 2*x_6^2)
edit retag flag offensive close merge delete

Comments

1
rburing gravatar imagerburing ( 2019-09-06 00:47:40 +0200 )edit

Please provide the code for constructing your polynomial, espacially regarding question 2.

tmonteil gravatar imagetmonteil ( 2019-09-06 10:08:01 +0200 )edit
1

@tmonteil: done!

Sébastien Palcoux gravatar imageSébastien Palcoux ( 2019-09-07 02:16:41 +0200 )edit

I just discovered that there is a way to solve the problem for the specific example using linear algebra because its fusion matrices are simultaneously diagonalizable. But it is not the point here. The point is about how SageMath could help in general for such polynomials.

Sébastien Palcoux gravatar imageSébastien Palcoux ( 2019-09-07 15:21:51 +0200 )edit