ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 30 Jun 2020 20:38:45 +0200Solving a polynomial system in a quotient ringhttps://ask.sagemath.org/question/52254/solving-a-polynomial-system-in-a-quotient-ring/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
$$X^2=1.$$
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))
S=R.quotient(J)
Which function should I use?Mon, 29 Jun 2020 16:55:09 +0200https://ask.sagemath.org/question/52254/solving-a-polynomial-system-in-a-quotient-ring/Comment by Jose Brox for <p>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</p>
<p>$$X^2=1.$$</p>
<p>I'm first defining the polynomial ring over $\mathbb{Z}_9$ in variables $x,y$, then factoring by the ideal generated by </p>
<p>$$y^2-2, (x+y)^2-2(x+y),$$</p>
<p>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</p>
<pre><code>R.<x,y> = PolynomialRing(IntegerModRing(9),order='lex')
J= R.ideal(x^2-2,(x+y)^2-2*(x+y))
S=R.quotient(J)
</code></pre>
<p>Which function should I use?</p>
https://ask.sagemath.org/question/52254/solving-a-polynomial-system-in-a-quotient-ring/?comment=52258#post-id-52258@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!Mon, 29 Jun 2020 19:31:07 +0200https://ask.sagemath.org/question/52254/solving-a-polynomial-system-in-a-quotient-ring/?comment=52258#post-id-52258Comment by FrédéricC for <p>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</p>
<p>$$X^2=1.$$</p>
<p>I'm first defining the polynomial ring over $\mathbb{Z}_9$ in variables $x,y$, then factoring by the ideal generated by </p>
<p>$$y^2-2, (x+y)^2-2(x+y),$$</p>
<p>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</p>
<pre><code>R.<x,y> = PolynomialRing(IntegerModRing(9),order='lex')
J= R.ideal(x^2-2,(x+y)^2-2*(x+y))
S=R.quotient(J)
</code></pre>
<p>Which function should I use?</p>
https://ask.sagemath.org/question/52254/solving-a-polynomial-system-in-a-quotient-ring/?comment=52256#post-id-52256Just make a triple loop.Mon, 29 Jun 2020 17:59:57 +0200https://ask.sagemath.org/question/52254/solving-a-polynomial-system-in-a-quotient-ring/?comment=52256#post-id-52256Comment by Jose Brox for <p>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</p>
<p>$$X^2=1.$$</p>
<p>I'm first defining the polynomial ring over $\mathbb{Z}_9$ in variables $x,y$, then factoring by the ideal generated by </p>
<p>$$y^2-2, (x+y)^2-2(x+y),$$</p>
<p>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</p>
<pre><code>R.<x,y> = PolynomialRing(IntegerModRing(9),order='lex')
J= R.ideal(x^2-2,(x+y)^2-2*(x+y))
S=R.quotient(J)
</code></pre>
<p>Which function should I use?</p>
https://ask.sagemath.org/question/52254/solving-a-polynomial-system-in-a-quotient-ring/?comment=52257#post-id-52257@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.Mon, 29 Jun 2020 18:31:27 +0200https://ask.sagemath.org/question/52254/solving-a-polynomial-system-in-a-quotient-ring/?comment=52257#post-id-52257Answer by dan_fulea for <p>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</p>
<p>$$X^2=1.$$</p>
<p>I'm first defining the polynomial ring over $\mathbb{Z}_9$ in variables $x,y$, then factoring by the ideal generated by </p>
<p>$$y^2-2, (x+y)^2-2(x+y),$$</p>
<p>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</p>
<pre><code>R.<x,y> = PolynomialRing(IntegerModRing(9),order='lex')
J= R.ideal(x^2-2,(x+y)^2-2*(x+y))
S=R.quotient(J)
</code></pre>
<p>Which function should I use?</p>
https://ask.sagemath.org/question/52254/solving-a-polynomial-system-in-a-quotient-ring/?answer=52270#post-id-52270Here 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")
Results:
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
2
sage: for r1, r2 in cartesian_product([r, r]):
....: Z1 = r1 + r2*a
....: if Z1^2 == Q(1):
....: print(Z1)
....:
1
8
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
2
sage: [ f for f in F if f^2 == F(1) ]
[2, 1]
sage: # of course, this is a field...
Tue, 30 Jun 2020 19:18:51 +0200https://ask.sagemath.org/question/52254/solving-a-polynomial-system-in-a-quotient-ring/?answer=52270#post-id-52270Comment by rburing for <p>Here is a possibility to work. </p>
<p>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.)</p>
<p>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$.</p>
<p>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)$.</p>
<p>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$.</p>
<p>Let us now write some lines of code for the given case.</p>
<p>The brute force search is:</p>
<pre><code>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")
</code></pre>
<p>Results:</p>
<pre><code>Z = 1 + 0 a + 0 x
Z = 1 + 8 a + 8 x
Z = 8 + 0 a + 0 x
Z = 8 + 1 a + 1 x
</code></pre>
<p>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$.</p>
<pre><code>sage: r = Integers(9)
sage: R.<Y> = r[]
sage: Q.<a> = R.quotient(Y^2-2)
sage: a^2
2
sage: for r1, r2 in cartesian_product([r, r]):
....: Z1 = r1 + r2*a
....: if Z1^2 == Q(1):
....: print(Z1)
....:
1
8
</code></pre>
<p>These are the only Hensel lifts of the corresponding units over $\Bbb Z/3$:</p>
<pre><code>sage: U.<A> = PolynomialRing(GF(3))
sage: F.<a> = GF(3^2, modulus = A^2-2)
sage: a^2
2
sage: [ f for f in F if f^2 == F(1) ]
[2, 1]
sage: # of course, this is a field...
</code></pre>
https://ask.sagemath.org/question/52254/solving-a-polynomial-system-in-a-quotient-ring/?comment=52271#post-id-52271I guess the equality test in `S` uses Gröbner bases over $\mathbb{Z}/n\mathbb{Z}$, implemented in Singular?Tue, 30 Jun 2020 20:38:45 +0200https://ask.sagemath.org/question/52254/solving-a-polynomial-system-in-a-quotient-ring/?comment=52271#post-id-52271