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.Mon, 04 Mar 2024 23:15:40 +0100How to solve system of equations in polynomial ring over GF with a different variableshttps://ask.sagemath.org/question/76337/how-to-solve-system-of-equations-in-polynomial-ring-over-gf-with-a-different-variables/I want to reduce system of symbolyc equations by modulo.
I create field and polynomical ring
F = GF(31)
R.<x, y, z> = PolynomialRing(F)
And try to create system:
system = [
x == 3 * y,
z == 2 * x
]
To use `solve(system, [x, y, z])` (here I expected solution `x = 3 * y`, `z = 6 * y`). But all of equations evaluate to False.
How to create correct equatiations?Mon, 04 Mar 2024 08:43:10 +0100https://ask.sagemath.org/question/76337/how-to-solve-system-of-equations-in-polynomial-ring-over-gf-with-a-different-variables/Answer by Max Alekseyev for <p>I want to reduce system of symbolyc equations by modulo. </p>
<p>I create field and polynomical ring</p>
<pre><code>F = GF(31)
R.<x, y, z> = PolynomialRing(F)
</code></pre>
<p>And try to create system:</p>
<pre><code>system = [
x == 3 * y,
z == 2 * x
]
</code></pre>
<p>To use <code>solve(system, [x, y, z])</code> (here I expected solution <code>x = 3 * y</code>, <code>z = 6 * y</code>). But all of equations evaluate to False.</p>
<p>How to create correct equatiations?</p>
https://ask.sagemath.org/question/76337/how-to-solve-system-of-equations-in-polynomial-ring-over-gf-with-a-different-variables/?answer=76342#post-id-76342`solve()` is a symbolic solve function, which works over the symbolic ring `SR` not polynomial rings. Since you work with polynomials, it's better to employ the polynomial ideal machinery instead:
F = GF(31)
R.<x, y, z> = PolynomialRing(F)
system = [
x - (3 * y),
z - (2 * x)
]
J = Ideal(system)
print( J.variety() )
However, in this case you'd get an error:
> ValueError: The dimension of the ideal is 1, but it should be 0
which tells us about the system having too many "degrees of freedom". Since we work in a finite field, it is easy to deal with it by fixing one of the variables, say, `x`:
sols = sum( (Ideal(system+[x-x0]).variety() for x0 in F), [] )
print(sols)
which prints the solutions:
[{z: 0, y: 0, x: 0}, {z: 2, y: 21, x: 1}, {z: 4, y: 11, x: 2}, {z: 6, y: 1, x: 3}, {z: 8, y: 22, x: 4}, {z: 10, y: 12, x: 5}, {z: 12, y: 2, x: 6}, {z: 14, y: 23, x: 7}, {z: 16, y: 13, x: 8}, {z: 18, y: 3, x: 9}, {z: 20, y: 24, x: 10}, {z: 22, y: 14, x: 11}, {z: 24, y: 4, x: 12}, {z: 26, y: 25, x: 13}, {z: 28, y: 15, x: 14}, {z: 30, y: 5, x: 15}, {z: 1, y: 26, x: 16}, {z: 3, y: 16, x: 17}, {z: 5, y: 6, x: 18}, {z: 7, y: 27, x: 19}, {z: 9, y: 17, x: 20}, {z: 11, y: 7, x: 21}, {z: 13, y: 28, x: 22}, {z: 15, y: 18, x: 23}, {z: 17, y: 8, x: 24}, {z: 19, y: 29, x: 25}, {z: 21, y: 19, x: 26}, {z: 23, y: 9, x: 27}, {z: 25, y: 30, x: 28}, {z: 27, y: 20, x: 29}, {z: 29, y: 10, x: 30}]
**ADDED.** As John pointed out, solutions of the form like `x = 3 * y, z = 6 * y` can be seen from the generators of the ideal:
print(Ideal(system).gens())
which gives
[x - 3*y, -2*x + z]
that is, `y = x/2` and `z = 2*x`.Mon, 04 Mar 2024 17:22:43 +0100https://ask.sagemath.org/question/76337/how-to-solve-system-of-equations-in-polynomial-ring-over-gf-with-a-different-variables/?answer=76342#post-id-76342Comment by John Palmieri for <p><code>solve()</code> is a symbolic solve function, which works over the symbolic ring <code>SR</code> not polynomial rings. Since you work with polynomials, it's better to employ the polynomial ideal machinery instead:</p>
<pre><code>F = GF(31)
R.<x, y, z> = PolynomialRing(F)
system = [
x - (3 * y),
z - (2 * x)
]
J = Ideal(system)
print( J.variety() )
</code></pre>
<p>However, in this case you'd get an error:</p>
<blockquote>
<p>ValueError: The dimension of the ideal is 1, but it should be 0</p>
</blockquote>
<p>which tells us about the system having too many "degrees of freedom". Since we work in a finite field, it is easy to deal with it by fixing one of the variables, say, <code>x</code>:</p>
<pre><code>sols = sum( (Ideal(system+[x-x0]).variety() for x0 in F), [] )
print(sols)
</code></pre>
<p>which prints the solutions:</p>
<pre><code>[{z: 0, y: 0, x: 0}, {z: 2, y: 21, x: 1}, {z: 4, y: 11, x: 2}, {z: 6, y: 1, x: 3}, {z: 8, y: 22, x: 4}, {z: 10, y: 12, x: 5}, {z: 12, y: 2, x: 6}, {z: 14, y: 23, x: 7}, {z: 16, y: 13, x: 8}, {z: 18, y: 3, x: 9}, {z: 20, y: 24, x: 10}, {z: 22, y: 14, x: 11}, {z: 24, y: 4, x: 12}, {z: 26, y: 25, x: 13}, {z: 28, y: 15, x: 14}, {z: 30, y: 5, x: 15}, {z: 1, y: 26, x: 16}, {z: 3, y: 16, x: 17}, {z: 5, y: 6, x: 18}, {z: 7, y: 27, x: 19}, {z: 9, y: 17, x: 20}, {z: 11, y: 7, x: 21}, {z: 13, y: 28, x: 22}, {z: 15, y: 18, x: 23}, {z: 17, y: 8, x: 24}, {z: 19, y: 29, x: 25}, {z: 21, y: 19, x: 26}, {z: 23, y: 9, x: 27}, {z: 25, y: 30, x: 28}, {z: 27, y: 20, x: 29}, {z: 29, y: 10, x: 30}]
</code></pre>
<p><strong>ADDED.</strong> As John pointed out, solutions of the form like <code>x = 3 * y, z = 6 * y</code> can be seen from the generators of the ideal:</p>
<pre><code>print(Ideal(system).gens())
</code></pre>
<p>which gives</p>
<pre><code>[x - 3*y, -2*x + z]
</code></pre>
<p>that is, <code>y = x/2</code> and <code>z = 2*x</code>.</p>
https://ask.sagemath.org/question/76337/how-to-solve-system-of-equations-in-polynomial-ring-over-gf-with-a-different-variables/?comment=76349#post-id-76349(I was basing this on the comment "I expected solution `x = 3 * y`, `z = 6 * y`".)Mon, 04 Mar 2024 23:15:40 +0100https://ask.sagemath.org/question/76337/how-to-solve-system-of-equations-in-polynomial-ring-over-gf-with-a-different-variables/?comment=76349#post-id-76349Comment by Max Alekseyev for <p><code>solve()</code> is a symbolic solve function, which works over the symbolic ring <code>SR</code> not polynomial rings. Since you work with polynomials, it's better to employ the polynomial ideal machinery instead:</p>
<pre><code>F = GF(31)
R.<x, y, z> = PolynomialRing(F)
system = [
x - (3 * y),
z - (2 * x)
]
J = Ideal(system)
print( J.variety() )
</code></pre>
<p>However, in this case you'd get an error:</p>
<blockquote>
<p>ValueError: The dimension of the ideal is 1, but it should be 0</p>
</blockquote>
<p>which tells us about the system having too many "degrees of freedom". Since we work in a finite field, it is easy to deal with it by fixing one of the variables, say, <code>x</code>:</p>
<pre><code>sols = sum( (Ideal(system+[x-x0]).variety() for x0 in F), [] )
print(sols)
</code></pre>
<p>which prints the solutions:</p>
<pre><code>[{z: 0, y: 0, x: 0}, {z: 2, y: 21, x: 1}, {z: 4, y: 11, x: 2}, {z: 6, y: 1, x: 3}, {z: 8, y: 22, x: 4}, {z: 10, y: 12, x: 5}, {z: 12, y: 2, x: 6}, {z: 14, y: 23, x: 7}, {z: 16, y: 13, x: 8}, {z: 18, y: 3, x: 9}, {z: 20, y: 24, x: 10}, {z: 22, y: 14, x: 11}, {z: 24, y: 4, x: 12}, {z: 26, y: 25, x: 13}, {z: 28, y: 15, x: 14}, {z: 30, y: 5, x: 15}, {z: 1, y: 26, x: 16}, {z: 3, y: 16, x: 17}, {z: 5, y: 6, x: 18}, {z: 7, y: 27, x: 19}, {z: 9, y: 17, x: 20}, {z: 11, y: 7, x: 21}, {z: 13, y: 28, x: 22}, {z: 15, y: 18, x: 23}, {z: 17, y: 8, x: 24}, {z: 19, y: 29, x: 25}, {z: 21, y: 19, x: 26}, {z: 23, y: 9, x: 27}, {z: 25, y: 30, x: 28}, {z: 27, y: 20, x: 29}, {z: 29, y: 10, x: 30}]
</code></pre>
<p><strong>ADDED.</strong> As John pointed out, solutions of the form like <code>x = 3 * y, z = 6 * y</code> can be seen from the generators of the ideal:</p>
<pre><code>print(Ideal(system).gens())
</code></pre>
<p>which gives</p>
<pre><code>[x - 3*y, -2*x + z]
</code></pre>
<p>that is, <code>y = x/2</code> and <code>z = 2*x</code>.</p>
https://ask.sagemath.org/question/76337/how-to-solve-system-of-equations-in-polynomial-ring-over-gf-with-a-different-variables/?comment=76346#post-id-76346Maybe, however OP asked to solve the system, so this is it. Still, `J.gens()` can provide compact description of the solutions and may be useful in some contexts.Mon, 04 Mar 2024 19:48:29 +0100https://ask.sagemath.org/question/76337/how-to-solve-system-of-equations-in-polynomial-ring-over-gf-with-a-different-variables/?comment=76346#post-id-76346Comment by John Palmieri for <p><code>solve()</code> is a symbolic solve function, which works over the symbolic ring <code>SR</code> not polynomial rings. Since you work with polynomials, it's better to employ the polynomial ideal machinery instead:</p>
<pre><code>F = GF(31)
R.<x, y, z> = PolynomialRing(F)
system = [
x - (3 * y),
z - (2 * x)
]
J = Ideal(system)
print( J.variety() )
</code></pre>
<p>However, in this case you'd get an error:</p>
<blockquote>
<p>ValueError: The dimension of the ideal is 1, but it should be 0</p>
</blockquote>
<p>which tells us about the system having too many "degrees of freedom". Since we work in a finite field, it is easy to deal with it by fixing one of the variables, say, <code>x</code>:</p>
<pre><code>sols = sum( (Ideal(system+[x-x0]).variety() for x0 in F), [] )
print(sols)
</code></pre>
<p>which prints the solutions:</p>
<pre><code>[{z: 0, y: 0, x: 0}, {z: 2, y: 21, x: 1}, {z: 4, y: 11, x: 2}, {z: 6, y: 1, x: 3}, {z: 8, y: 22, x: 4}, {z: 10, y: 12, x: 5}, {z: 12, y: 2, x: 6}, {z: 14, y: 23, x: 7}, {z: 16, y: 13, x: 8}, {z: 18, y: 3, x: 9}, {z: 20, y: 24, x: 10}, {z: 22, y: 14, x: 11}, {z: 24, y: 4, x: 12}, {z: 26, y: 25, x: 13}, {z: 28, y: 15, x: 14}, {z: 30, y: 5, x: 15}, {z: 1, y: 26, x: 16}, {z: 3, y: 16, x: 17}, {z: 5, y: 6, x: 18}, {z: 7, y: 27, x: 19}, {z: 9, y: 17, x: 20}, {z: 11, y: 7, x: 21}, {z: 13, y: 28, x: 22}, {z: 15, y: 18, x: 23}, {z: 17, y: 8, x: 24}, {z: 19, y: 29, x: 25}, {z: 21, y: 19, x: 26}, {z: 23, y: 9, x: 27}, {z: 25, y: 30, x: 28}, {z: 27, y: 20, x: 29}, {z: 29, y: 10, x: 30}]
</code></pre>
<p><strong>ADDED.</strong> As John pointed out, solutions of the form like <code>x = 3 * y, z = 6 * y</code> can be seen from the generators of the ideal:</p>
<pre><code>print(Ideal(system).gens())
</code></pre>
<p>which gives</p>
<pre><code>[x - 3*y, -2*x + z]
</code></pre>
<p>that is, <code>y = x/2</code> and <code>z = 2*x</code>.</p>
https://ask.sagemath.org/question/76337/how-to-solve-system-of-equations-in-polynomial-ring-over-gf-with-a-different-variables/?comment=76344#post-id-76344Maybe `J.gens()` is the kind of thing the poster is looking for?Mon, 04 Mar 2024 19:17:05 +0100https://ask.sagemath.org/question/76337/how-to-solve-system-of-equations-in-polynomial-ring-over-gf-with-a-different-variables/?comment=76344#post-id-76344Answer by John Palmieri for <p>I want to reduce system of symbolyc equations by modulo. </p>
<p>I create field and polynomical ring</p>
<pre><code>F = GF(31)
R.<x, y, z> = PolynomialRing(F)
</code></pre>
<p>And try to create system:</p>
<pre><code>system = [
x == 3 * y,
z == 2 * x
]
</code></pre>
<p>To use <code>solve(system, [x, y, z])</code> (here I expected solution <code>x = 3 * y</code>, <code>z = 6 * y</code>). But all of equations evaluate to False.</p>
<p>How to create correct equatiations?</p>
https://ask.sagemath.org/question/76337/how-to-solve-system-of-equations-in-polynomial-ring-over-gf-with-a-different-variables/?answer=76343#post-id-76343The `solve_mod` command might be useful:
Return all solutions to an equation or list of equations modulo the
given integer modulus. Each equation must involve only polynomials
in 1 or many variables.
Type `solve_mod?` for the help message and examples. This is most useful when there are relatively few solutions, maybe even when there are relatively few possible solutions. It is very slow for the particular equations you provide, partly because the modulus is 31 and it may very well be trying all possible values for x, y, and z. Also, it will list all solutions, not solve it symbolically the way you are asking. Mon, 04 Mar 2024 18:50:14 +0100https://ask.sagemath.org/question/76337/how-to-solve-system-of-equations-in-polynomial-ring-over-gf-with-a-different-variables/?answer=76343#post-id-76343