Ask Your Question

Solving a polynomial system in a quotient ring

asked 2020-06-29 16:55:09 +0200

Jose Brox gravatar image

updated 2020-06-29 19:46:55 +0200

I want to compute all solutions in $\mathbb{Z}_9[\sqrt2,x]$, where $x$ is such that $(x+\sqrt2)^2=2(x+\sqrt2)$, of the equation


I'm first defining the polynomial ring over $\mathbb{Z}_9$ in variables $x,y$, then factoring by the ideal generated by

$$y^2-2, (x+y)^2-2(x+y),$$

to get the ring $S$, but then I don't know which command to use in order to get the solutions of $X^2-1$. I have tried "solve" and "variety" (defining $S[X]$ first and then the ideal of $X^2-1$), but they do not seem to work. The code up to this point is just

R.<x,y> = PolynomialRing(IntegerModRing(9),order='lex')
J= R.ideal(x^2-2,(x+y)^2-2*(x+y))

Which function should I use?

edit retag flag offensive close merge delete


Just make a triple loop.

FrédéricC gravatar imageFrédéricC ( 2020-06-29 17:59:57 +0200 )edit

@FrédéricC Yes, in this particular case I can do it, but I'd like to learn how to tackle this kind of computation more in general. I'm going to need computations over infinite rings too. The specific mention to $\mathbb{Z}_9$ is in case that some module does not work well over rings which are not fields.

Jose Brox gravatar imageJose Brox ( 2020-06-29 18:31:27 +0200 )edit

@FrédéricC In fact that presentation of the problem was a mistake on my part, since I don't know if the linear combinations are going to span the whole ring. I need some function giving the set of solutions reduced by the Gröbner basis. Thank you for your help!

Jose Brox gravatar imageJose Brox ( 2020-06-29 19:31:07 +0200 )edit

1 Answer

Sort by » oldest newest most voted

answered 2020-06-30 19:18:51 +0200

dan_fulea gravatar image

Here is a possibility to work.

Let $A$ be a ring such that $2$ is invertible, for example $\Bbb Z/3$ or $\Bbb Z/9$. We denote by $\frac 12$ its inverse. Assume $2$ is not a square in $A$. (This is the case in the above examples.)

Consider $A[a]$ to be the ring $A[Y]/(Y^2-2)$, where $A[Y]$ is the polynomial ring in $Y$ over $A$. (And $a$ is $Y$ modulo the ideal generated by $(Y^2-2)$. So formally, $a=\sqrt2$.

Now observe that the equation satisfied by the $x$ element in the OP, $(x+a)^2=2(x+a)$, can be written as $$(x+a)(x+a-2)=0\ .$$ The two factors are relatively prime, in fact $$\frac 12(x+a)-\frac 12(x+a-2) = 1\ .$$ This means that the ring $$ R=A[a][X]\ /\ (\ (X+a)(X+a-2)\ ) $$ is isomorphic to two copies of $A[a]$ via the map $$ R\to A[a]\times A[a]\ ,\ f(X)\to(f(-a), f(2-a))\ . $$ The inverse map takes $(s,t)\in A[a]\times A[a]$ and maps it into $\frac 12t(X+a)-\frac 12s(X+a-2)$.

Now we have to solve $Z^2=1$ in the ring $A[a]\times A[a]$. This can be done also manually. An element of the shape $Z=u+va\in A[a]$, $u,v\in A$ satisfies $Z^2 = 1$ iff $(u^2+2v^2)+2auv=1$. In case $A$ has zero divisors we have to take care of $uv=0$ somehow. The possible values for $u,v$ that may lead to a solution satisfy at any rate $u^3=u$ and $2v^3=v$. Together with $Z$, also its "conjugate" $\bar Z=u-va$ is also a solution, and the "norm" $N(Z)=Z\bar Z=(u+va)(u-va)=u^2-2v^2$ is $1$. So it is a good idea to search for solutions of this "Pell equation" over $A$.

Let us now write some lines of code for the given case.

The brute force search is:

r = Zmod(9)
R.<a,x> = PolynomialRing(r, order='lex')
J = R.ideal( [a^2-2, (x+a)^2-2*(x+a)] )
S = R.quotient(J)

for [s, t, u] in cartesian_product([r, r, r]):
    Z = S(s + t*a + u*x)
    if Z^2 == S(1):
        print(f"Z = {s} + {t} a + {u} x")


Z = 1 + 0 a + 0 x
Z = 1 + 8 a + 8 x
Z = 8 + 0 a + 0 x
Z = 8 + 1 a + 1 x

This fits with the situation of finding all points $Z=(Z_1,Z_2)$ over the ring $R=A[a]=\Bbb Z/9[a]=\Bbb Z/9[\sqrt 2]$ with $Z^2=(1,1)=1_R$.

sage: r = Integers(9)                                                                                                         
sage: R.<Y> = r[]                                                                                                             
sage: Q.<a> = R.quotient(Y^2-2)                                                                                               
sage: a^2                                                                                                                     
sage: for r1, r2 in cartesian_product([r, r]): 
....:     Z1 = r1 + r2*a 
....:     if Z1^2 == Q(1): 
....:         print(Z1) 

These are the only Hensel lifts of the corresponding units over $\Bbb Z/3$:

sage: U.<A> = PolynomialRing(GF(3))                                                                                           
sage: F.<a> = GF(3^2, modulus = A^2-2)                                                                                        
sage: a^2                                                                                                                     
sage: [ f for f in F if f^2 == F(1) ]                                                                                         
[2, 1]
sage: # of course, this is a field...
edit flag offensive delete link more


I guess the equality test in S uses Gröbner bases over $\mathbb{Z}/n\mathbb{Z}$, implemented in Singular?

rburing gravatar imagerburing ( 2020-06-30 20:38:45 +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


Asked: 2020-06-29 16:55:09 +0200

Seen: 679 times

Last updated: Jun 30 '20