Ask Your Question
1

Solutions to Equations over different fields

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

whatupmatt gravatar image

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

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

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

Comments

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 +0200 )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):
    S1=buildit(p)
    J1=S1[0].parent().ideal(*S1)
    return J1.dimension()

sage: dimres(2)
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
True

BTW :

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

HTH,

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

1 Answer

Sort by » oldest newest most voted
2

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

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()
1

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()
0
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

Comments

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 +0200 )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 +0200 )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

Stats

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

Seen: 100 times

Last updated: Jul 30 '21