Processing math: 100%
Ask Your Question
2

Finding polynomial solutions that belong to an ideal

asked 4 years ago

arpit gravatar image

updated 4 years ago

I have a system of equations in which the variables belong to a certain ideal of a polynomial ring over a field. We can call this ideal I and its generators c1, c2 and c3. Let's take the ring to be F2[x1,x2,x3] and the ideal to be I=<x1x2x31,x2x1,x11> . Let's say the equations are g1+x1w2+x2w3=x11, g2+x2w1+x3w3=x21 and g3+x1w1+w2=x31 and one needs to find solution to the above set of equations with variables gi and wi inside the ideal I. There are of course more variables than equations here. One obvious solution is g1=x11,g2=x21,g3=x31. How does one find the full set of solutions? I thought of implementing this as a syzygy problem where I take x11 and so on on the left but that seems to be not ideal since it is not clear whether I find all solutions or not. To simplify the problem, we can choose a cut-off for degree of polynomial solutions, for example, 1 or 2.

Preview: (hide)

Comments

Is there a missing coefficient x3 in front of w2 in the last equation?

Sébastien gravatar imageSébastien ( 4 years ago )

1 Answer

Sort by » oldest newest most voted
0

answered 4 years ago

Sébastien gravatar image

updated 4 years ago

We define the ring and the ideal:

sage: R.<x1,x2,x3> = GF(2)[]
sage: R
Multivariate Polynomial Ring in x1, x2, x3 over Finite Field of size 2
sage: I = R.ideal(x1*x2*x3-1, x2-x1, x1-1)

We compute the groebner basis of the ideal and we realize that these are exactly the right hand side of the three given equations:

sage: I.groebner_basis()
[x1 + 1, x2 + 1, x3 + 1]
sage: [x1-1, x2-1, x3-1]
[x1 + 1, x2 + 1, x3 + 1]

Thus, finding a solution to the 3 equations is equivalent to finding a solution to the following:

x1w2+x2w3I,x2w1+x3w3I,x1w1+x3w2I

which holds by definition of ideal for all elements w1,w2,w3 in the ideal I which solves the question as it was requested that the wi are in the ideal. Now, notice that this does not include all solutions, for example:

sage: w2 = x2; w3 = x3
sage: w2 in I, w3 in I
(False, False)
sage: x1*w2 + x2*w3 in I
True
Preview: (hide)
link

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 4 years ago

Seen: 356 times

Last updated: Apr 20 '20