Ask Your Question

Solutions to Equations over different fields

asked 2021-07-29 06:30:15 +0100

whatupmatt gravatar image

updated 2022-04-14 20:37:21 +0100

FrédéricC gravatar image

Hello, suppose I want to solve a system of equations

w,x,y,z = SR.var('w, x, y, z')
eqn1=2*w*y^2 + y^2*z + z^3==0
eqn2=4*x^3 - 2*x*y^2 - y^3==0
eqn3=2*w^2*y - 2*x^2*y - 3*x*y^2 + 2*w*y*z==0
eqn4=w*y^2 + 3*w*z^2==0
sol = solve([eqn1, eqn2, eqn3, eqn4], w,x,y,z, solution_dict=True)

This gives me solutions over complex numbers I believe? How can I ask for solutions over say a finite field. Let's make it more simple and say the field is a prime and not a prime power. Hence, just reducing modulo p. As you all know, it is possible more solutions arise when moving to finite fields.

edit retag flag offensive close merge delete


Do not use the symbolic ring SR, but a polynomial ring over a finite field.

FrédéricC gravatar imageFrédéricC ( 2021-07-29 09:12:13 +0100 )edit

To illustrate Frederic's answer:

def buildit(p):
    if not p.is_prime():
        raise DomainError("p must be prime !")
    R1=PolynomialRing(Zmod(p),"w, x, y, z")
    return [R1(u.lhs()) for u in (eqn1, eqn2, eqn3, eqn4)]

def dimres(p):
    return J1.dimension()

sage: dimres(2)

sage: %time all([v==1 for v in [dimres(u) for u in prime_range(3,100000)]])
CPU times: user 2min 20s, sys: 841 ms, total: 2min 21s
Wall time: 2min 22s


sage: sol
[{w: r1, x: 0, y: 0, z: 0}]


Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2021-07-29 12:43:18 +0100 )edit

1 Answer

Sort by » oldest newest most voted

answered 2021-07-30 01:37:29 +0100

tmonteil gravatar image

Here is an example for the finite field GF(3)

Let us first define the field:

sage: p = 3
sage: K = GF(p)
sage: K
Finite Field of size 3

Then, let us define the polynomial ring:

sage: R.<w,x,y,z> = K[]
sage: R
Multivariate Polynomial Ring in w, x, y, z over Finite Field of size 3

Then, let us define the 4 polynomials which have to vanish:

sage: eqn1 = 2*w*y^2 + y^2*z + z^3
sage: eqn2 = 4*x^3 - 2*x*y^2 - y^3
sage: eqn3 = 2*w^2*y - 2*x^2*y - 3*x*y^2 + 2*w*y*z
sage: eqn4 = w*y^2 + 3*w*z^2

Now, let us define the ideal generated by those polynomials:

sage: I = R.ideal([eqn1, eqn2, eqn3, eqn4])
sage: I
Ideal (-w*y^2 + y^2*z + z^3, x^3 + x*y^2 - y^3, -w^2*y + x^2*y - w*y*z, w*y^2) of Multivariate Polynomial Ring in w, x, y, z over Finite Field of size 3

Unfortunately, this ideal has dimension 1:

sage: I.dimension()

Hence, Sage is not able to find its variety (which corresponds to the set of common zeroes of the 4 polynomials above):

sage: I.variety()
ValueError: The dimension of the ideal is 1, but it should be 0

Hovewer there is a trick : on GF(p) there fro the Frobenius, we know that the polynomial x^p-x vanishes, hence, since we are looking to the solutions within GF(p)^4, we can add those polynomials to the generators of the ideal:

sage: fw = w^p - w
sage: fx = x^p - x
sage: fy = y^p - y
sage: fz = z^p - z

sage: J = R.ideal([eqn1, eqn2, eqn3, eqn4, fw, fx, fx, fz])
sage: J.dimension()
sage: J.variety()
[{z: 0, y: 0, x: 0, w: 0}, {z: 0, y: 0, x: 0, w: 2}, {z: 0, y: 0, x: 0, w: 1}]
edit flag offensive delete link more


Hello take p=5, what would it mean if the dimension of variety is still one after adding in the Frobenius equations? For example, take eqn1= x^2y + xy^2 + 2wz^2, eqn2= 2wxy + wy^2 + 2xy^2 + z^3, eqn 3=wx^2 + 2wxy + 2x^2y, and eqn4= 2w^2z + 3xz^2 + 4*z^3? If I run the thing above, and hit J.variety(), it is still dimension 1. Does this mean there can possibly be solutions but Sage cannot compute it?

whatupmatt gravatar imagewhatupmatt ( 2021-07-30 17:48:28 +0100 )edit

Indeed, Sage is not able to solve this system with the variety method, however, it should be possible do brute force over GF(5)^4.

tmonteil gravatar imagetmonteil ( 2021-07-30 22:41:32 +0100 )edit

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


Asked: 2021-07-29 06:30:15 +0100

Seen: 294 times

Last updated: Jul 30 '21