# How to check if 0 polynomial lies in span of some polynomials?

I have lot of polynomials like this

f1[a1_,x1_] := (a1 x1 + 1 - x1)

f2[a2_,x2_] := (a2 x2 + 1 - x2)

f3[a1_,x1_,a2_,x2_] := (a1 x1 + 1 - x1)*(a2 x2 + 1 - x2)

f4[a1_,x1_,a2_,x2_] := (a1 x1 + 1 - x1)*(a2 x2 + 1 - x2)*x2

f5[a1_,x1_,a2_,x2_] := (a1 x1 + 1 - x1)*(a2 x2 + 1 - x2)*(a1 x1 + 1 - x1)

f6[a1_,x1_,a2_,x2_,a3_,x3_] := (a1 x1 + 1 - x1)*(a2 x2 + 1 - x2)*(a3 x3 + 1 -x3)


and so on...

I want to know what integer linear combinations of these polynomials would result in a 0 polynomial. That is, I want to the set of all solutions for

c1 f1 + c2 f2 + c3 f3 + c4 f4 + c5 f5 + c6 f6 = 0


When I enter

Solve[c1 f1[a1_,x1_] + c2 f2[a2_,x2_] + c3 f3[a1_,x1_,a2_,x2_] + c4 f4[a1_,x1_,a2_,x2_] + c5 f5[a1_,x1_,a2_,x2_] + c6 f6[a1_,x1_,a2_,x2_,a3_,x3_] == 0, {c1,c2,c3,c4,c5,c6}]


mathematica just expresses one variable in terms of all others. That's not what I want. I want all non-trivial integer solutions for c1, c2, c3, c4, c5, c6 (some of them could be zero) such that the above equation is satisfied for all values of x1,x2,x3,a1,a2,a3.

I could try to expand my polynomials and express it as a set of linear equations Mc=0, where the matrix M represents the coefficients of the polynomials. But unfortunately, when I expand my polynomials, they have exponential number of monomials, and I could not use this method even when problem size becomes bigger.

Are there better ways to solve my problem?

• Sep 29, 2019 at 16:06
• To start with, Blank is used on the LHS in the definition of a function, not when calling the function. Sep 29, 2019 at 16:08
• FindInstance? Sep 29, 2019 at 16:22
• You could substitute random integers for your variables. Sep 30, 2019 at 5:43

You could try SolveAlways, but it only returns the trivial solution:

SolveAlways[
c1 f1[a1,x1] + c2 f2[a2,x2] + c3 f3[a1,x1,a2,x2] + c4 f4[a1,x1,a2,x2] +
c5 f5[a1,x1,a2,x2] + c6 f6[a1,x1,a2,x2,a3,x3] == 0,
{x1,x2,x3,a1,a2,a3}
]


{{c4 -> 0, c5 -> 0, c3 -> 0, c6 -> 0, c1 -> 0, c2 -> 0}}

• That's nice! When I tried only some polynomials, mathematica gave an answer like {{b3 -> 0, b4 -> 0, b5 -> 0, b6 -> 0, b1 -> d9, d1 -> -d9, b2 -> d7, d2 -> -d7, d4 -> d7, d5 -> 0, d3 -> -d6 + d9, d8 -> 0}}. From this list, is there a way I could extract individual values, and substitute d7, d9, d6 with some numbers? Sep 29, 2019 at 16:53
• SolveAlways seems like a powerful tool. May I know how it works? For my application, the polynomials have small factors but I when I write it in canonical form, the polynomials have exponential number of monomials. Efficiency is my concern. If SolveAlways internally expands all the polynomials and expresses it as solving equation of Mc = 0. Then, it might not be efficient enough for my application. Sep 29, 2019 at 16:56