# Polynomial manipulation

**URL:** <https://discourse.julialang.org/t/polynomial-manipulation/114313>\
**Category:** Specific Domains\
**Tags:** algebra\
**Created:** [May 15, 2024, 5:33pm UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313 "2024-05-15T17:33:11Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![BLI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bli/32/37206_2.png) [@BLI](https://discourse.julialang.org/u/BLI)\
**Post date:** [May 18, 2024, 7:15am UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/21 "2024-05-18T07:15:21Z")

</div>

Thanks a lot for explanation. I will post another example.

I was trying to understand some thermodynamics which included cubic polynomials, and then some expressions which were fractions of polynomials. My expressions were more complex than those in the literature, so I was wondering what I did wrong. But then after some manual playing around, I found that I could reduce my polynomial fractions to those of the literature.

Essentially, I was wondering how some people could be so ingenious as to figure out those simplifications. And then I wondered: is there a Julia tool to do the same thing for me?

(I don’t know if I have time today… I really need to take an exercise walk… will hopefully be back in the evening.

I tried to install Nemo and Groebner via the Julia Pkg manager yesterday + update my packages. Don’t know what is wrong with my Windows 11 laptop… when I move away from the screen and the screen locker kicks in, it seems like the progress in the Julia REPL pauses… even though I have set the power settings to not pause with screen dimmed…so I need to finish the installation.)

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [May 18, 2024, 7:52am UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/22 "2024-05-18T07:52:27Z")

</div>

My little `PuiseuxPolynomials` package (which has no dependencies) can do the computation:

```julia
julia> using PuiseuxPolynomials

julia> @Mvp t,n,d,x,u,w

julia> P = x^3 - 3x^2 - 3(u + w)*x - u^2 + (1 - u)*w
Mvp{Int64}: -u²-uw-3ux-3wx+w+x³-3x²

julia> N = x^2 - 2x - (u + w)
Mvp{Int64}: -u-w+x²-2x

julia> D = (2x + u) * (x - 1)^2
Mvp{Int64}: ux²-2ux+u+2x³-4x²+2x

julia> grobner_basis([P,d*N-D*n,t*D-1])
4-element Vector{Mvp{Int64, Int64}}:
 -u²-uw-3ux-3wx+w+x³-3x²
 tux²-2tux+tu+2tx³-4tx²+2tx-1
 twx³-3twx²+3twx-tw-tx⁵+3tx⁴-3tx³+tx²+u+w+x
 d-nu-3nx+n

```

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [May 18, 2024, 12:34pm UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/23 "2024-05-18T12:34:10Z")

</div>

Given that Puiseux polynomials include Laurent polynomials, which are able to represent some fractions, I hoped that PuiseuxPolynomials.jl would enable a more direct encoding of the system of equations. However, this doesn’t seem to work:

```julia-repl
julia> grobner_basis([P,N-D*n*d^-1])
2-element Vector{Mvp{Int64, Int64}}:
 -u-w+x²-2x-d⁻¹nux²+2d⁻¹nux-d⁻¹nu-2d⁻¹nx³+4d⁻¹nx²-2d⁻¹nx
 -wx²+2wx-w+x⁴-2x³+x²-d⁻¹nu²x²+2d⁻¹nu²x-d⁻¹nu²-d⁻¹nux⁴-d⁻¹nux³+5d⁻¹nux²-3d⁻¹nux-2d⁻¹nx⁵+2d⁻¹nx⁴+2d⁻¹nx³-2d⁻¹nx²

```

I guess `grobner_basis` only supports the true polynomials, i.e., it doesn’t support Laurent polynomials?

BTW, @Jean_Michel, I made a PR to LaurentPolynomials.jl to fix the build on Nightly Julia.

---

<div class="post-metadata">

**Author:** ![thofma](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/thofma/32/1691_2.png) [@thofma](https://discourse.julialang.org/u/thofma)\
**Post date:** [May 18, 2024, 6:02pm UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/24 "2024-05-18T18:02:00Z")

</div>

That looks nice. Two quick question: Is it supposed to handle overflow? I tried it with some polynomials but got wrong results (arithmetic) and sometimes and error:

```julia
julia> grobner_basis([P,d*N-D*n,t*D-1])
ERROR: DivideError: integer division error
Stacktrace:

```

And regarding “no dependencies”, it also seems to depend on ModuleElts and LaurentPolynomials. Is this normal or did I maybe get an old version?

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [May 18, 2024, 6:21pm UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/25 "2024-05-18T18:21:02Z")

</div>

> [@thofma](#):
>
> Is it supposed to handle overflow?

I believe it’s possible to avoid overflow simply by using `BigInt` coefficients, instead of `Int`.

---

<div class="post-metadata">

**Author:** ![BLI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bli/32/37206_2.png) [@BLI](https://discourse.julialang.org/u/BLI)\
**Post date:** [May 18, 2024, 6:28pm UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/26 "2024-05-18T18:28:28Z")

</div>

I get an error with `Nemo` when trying to run it i a Jupyter Notebook (within VSCode):

```julia
julia> using Nemo

WARNING: could not import AbstractAlgebra.Solve into Nemo
ERROR: LoadError: UndefVarError: `@include_deprecated_bindings` not defined

```

It seems to work in the REPL, though.

- Any clues?

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [May 18, 2024, 6:29pm UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/27 "2024-05-18T18:29:29Z")

</div>

> [@BLI](#):
>
> I get an error with `Nemo` when trying to run it i a Jupyter Notebook (within VSCode):

Definitely a separate topic. Open a new post.

---

<div class="post-metadata">

**Author:** ![BLI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bli/32/37206_2.png) [@BLI](https://discourse.julialang.org/u/BLI)\
**Post date:** [May 18, 2024, 6:48pm UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/28 "2024-05-18T18:48:16Z")

</div>

Just for fun, I tried the code with `Symbolics`, too:

```julia
using Symbolics

@variables u, w, x, d, n, t# t, n, d, x, u, w

P = x^3 - 3*x^2 - 3*(u + w)*x - u^2 + (1 - u)*w
N = x^2 - 2*x - (u + w)
D = (2*x + u) * (x - 1)^2

System = [P, d*N - D*n, t*D - 1]

Symbolics.groebner_basis(System)

```

leading to:

```julia
9-element Vector{PolyForm{Real}}:
 -n - d + 3x*n + u*n
 w - 3(x^2) - 3w*x - 3u*x - u*w - (u^2) + (x^3)
...

```

Seems to work, too. I get the same result whether I change the order of defining variables.

* * *

OK – will check other polynomial now.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [May 18, 2024, 6:59pm UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/29 "2024-05-18T18:59:13Z")

</div>

> [@BLI](#):
>
> Just for fun, I tried the code with `Symbolics`, too:

FTR, Symbolics.jl actually doesn’t do anything here on its own AFAIK. The polynomials are DynamicPolynomials.jl polynomials, which are supported by Groebner.jl.

---

<div class="post-metadata">

**Author:** ![BLI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bli/32/37206_2.png) [@BLI](https://discourse.julialang.org/u/BLI)\
**Post date:** [May 18, 2024, 7:13pm UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/30 "2024-05-18T19:13:30Z")

</div>

So here is the other case:

```julia
N_a = (x^2 + x*u+w)^2

D_a = (x^2 - 2*x - (u+w))

System_a = [P, d*N_a - D_a*n, t*D_a - 1]

```

when applying the Gröbner basis leads to:

```julia
-n - w*d + 3(x^2)*d + 3u*x*d + (u^2)*d

```

or:

-n + (-w + 3x^2 + 3xu + u^2)d = 0 \\ \Downarrow \\ \frac{n}{d} = -w + 3x(x+u) + u^2

That is interesting, if correct… the expression I found in the literature is:

\frac{\left(x^{2}+u\cdot x+w\right)\left(2x+u\right)}{x-1}

I will check this.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [May 18, 2024, 8:51pm UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/31 "2024-05-18T20:51:34Z")

</div>

> [@BLI](#):
>
> `x^2 + x*u+w`

The whitespace formatting is weird here? Is this supposed to be `x^2 + x*u + w` or is it supposed to be `x^2 + x*(u+w)`?

---

<div class="post-metadata">

**Author:** ![BLI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bli/32/37206_2.png) [@BLI](https://discourse.julialang.org/u/BLI)\
**Post date:** [May 18, 2024, 8:55pm UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/32 "2024-05-18T20:55:42Z")

</div>

Yeah. Sorry for whitespace. No parenthesis.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [May 18, 2024, 9:35pm UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/33 "2024-05-18T21:35:43Z")

</div>

The below code might be useful. It helps avoid repeating redundant work and gives multiple possible solutions by switching around the roles of the variables. It doesn’t find the solution you expect for your second problem. It finds these three solutions for your first problem:

```julia
n - 9//(u^3 + 6*u^2 + 12*u + 8)*d*x^2 + (3*u + 24)//(u^3 + 6*u^2 + 12*u + 8)*d*x + (-u^2 + 20*u + 27*w + 8)//(u^3 + 6*u^2 + 12*u + 8)*d

```

```julia
n - 1//(x^3 - 3*x^2 + 3*x - 1)*d*u + (-w - 1)//(x^3 - 3*x^2 + 3*x - 1)*d

```

```julia
n - 1//3//(x + 1//3*u - 1//3)*d

```

The code:

```julia
function denominator_constraint(t, d)
  t*d - 1
end

function numerator_denominator_constraints(t, n, d, num, den)
  nd = den*n - num*d
  (nd, denominator_constraint(t, d))
end

function problem_system(problem, t, n, d, vars)
  cs = problem.constraints(vars...)
  num = problem.numerator(vars...)
  den = problem.denominator(vars...)
  [cs..., numerator_denominator_constraints(t, n, d, num, den)...]
end

using Nemo, ParamPunPam

function all_systems_xuw(problem)
  s_x = let
    (R_param, (u, w)) = QQ["u", "w"]
    (_, (t, n, d, x)) = fraction_field(R_param)["t", "n", "d", "x"]
    problem_system(problem, t, n, d, (x, u, w))
  end

  s_u = let
    (R_param, (x, w)) = QQ["x", "w"]
    (_, (t, n, d, u)) = fraction_field(R_param)["t", "n", "d", "u"]
    problem_system(problem, t, n, d, (x, u, w))
  end

  s_w = let
    (R_param, (x, u)) = QQ["x", "u"]
    (_, (t, n, d, w)) = fraction_field(R_param)["t", "n", "d", "w"]
    problem_system(problem, t, n, d, (x, u, w))
  end

  (s_x, s_u, s_w)
end

problem_1 = (
  constraints = ((x, u, w) -> (x^3 - 3*x^2 - 3*(u + w)*x - u^2 + (1 - u)*w,)),
  numerator = ((x, u, w) -> x^2 - 2*x - (u + w)),
  denominator = ((x, u, w) -> (2*x + u) * (x - 1)^2),
)

problem_1_solutions = map(paramgb, all_systems_xuw(problem_1))

```

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [May 19, 2024, 7:59am UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/34 "2024-05-19T07:59:19Z")

</div>

As usual in Julia, there are two ways to detect overflows (which are not detected by default):

- use `Rational{Int}` (fractions detect overflow)
- use `SafeInt` (the nice package `SaferIntegers` is designed to detect overflows and has a rather low overhead compared to normal integers).

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [May 19, 2024, 8:05am UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/35 "2024-05-19T08:05:47Z")

</div>

> [@nsajko](#):
>
> `grobner_basis([P,N-D*n*d^-1])`

You can get slightly better results by changing the monomial order:

```julia-auto
julia> grobner_basis([P,N-D*n*d^-1];lt=grlex)
3-element Vector{Mvp{Int64, Int64}}:
 -u²-uw-3ux-3wx+w+x³-3x²
 -u-w+x²-2x-d⁻¹nux²+2d⁻¹nux-d⁻¹nu-2d⁻¹nx³+4d⁻¹nx²-2d⁻¹nx
 du²+duw+2dux+7du+2dwx+6dw-6dx²+14dx-nu³-nu²w-5nu²x+12nu²-5nuwx+13nuw+21nux+7nu-6nwx²+38nwx-12nw+6nx²+14nx

```

> I guess `grobner_basis` only supports the true polynomials, i.e., it doesn’t support Laurent polynomials?

I do not know of a theoretical definition of Grobner bases for Laurent polynomials…

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [May 19, 2024, 8:11am UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/36 "2024-05-19T08:11:13Z")

</div>

> [@thofma](#):
>
> And regarding “no dependencies”, it also seems to depend on ModuleElts and LaurentPolynomials. Is this normal or did I maybe get an old version?

“no dependencies” was a misstatement. I meant apart from these two additional packages, which themselves are small and have no other dependencies. The total amount of code in the 3 packages is rather small for the functionality.

---

<div class="post-metadata">

**Author:** ![sumiya11](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sumiya11/32/207147_2.png) [@sumiya11](https://discourse.julialang.org/u/sumiya11)\
**Post date:** [May 19, 2024, 9:30am UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/37 "2024-05-19T09:30:42Z")

</div>

> [@BLI](#):
>
> So here is the other case:
> 
> ```julia
> N_a = (x^2 + x*u+w)^2
> 
> D_a = (x^2 - 2*x - (u+w))
> 
> ```

Thanks, that’s interesting! Result seems correct:

```julia
using Nemo
R, (x,u,w) = QQ["x","u","w"]
N_a = (x^2 + x*u+w)^2
D_a = (x^2 - 2*x - (u+w))
P = x^3 - 3*x^2 - 3*(u + w)*x - u^2 + (1 - u)*w
Result = -w + 3x*(x+u) + u^2
# N_a / D_a = Result (mod P)
@assert mod(N_a, P) == mod(D_a * Result, P)

```

But I do not know which set of transformations one needs to apply to get this result form the initial expression. Maybe something like [Gröbner/Standard Bases Over Fields · Oscar.jl (oscar-system.org)](https://docs.oscar-system.org/dev/CommutativeAlgebra/GroebnerBases/groebner_bases/#groebner_basis_with_transformation_matrix-Tuple%7BMPolyIdeal%7D) can help, will try

---

<div class="post-metadata">

**Author:** ![sumiya11](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sumiya11/32/207147_2.png) [@sumiya11](https://discourse.julialang.org/u/sumiya11)\
**Post date:** [May 19, 2024, 11:07am UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/38 "2024-05-19T11:07:14Z")

</div>

Ah, here is the expression of the last result in terms of `N_a`, `D_a`, `P`:

```julia
julia> Result == (N_a + (2x + u)*P) // D_a
true

```

obtained with the help of `Oscar.groebner_basis_with_transformation_matrix`.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [May 26, 2024, 10:41am UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/39 "2024-05-26T10:41:49Z")

</div>

Apparently there’s yet another package implementing Gröbner bases: PolynomialRings.jl.

---

<div class="post-metadata">

**Author:** ![BLI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bli/32/37206_2.png) [@BLI](https://discourse.julialang.org/u/BLI)\
**Post date:** [May 26, 2024, 6:17pm UTC](https://discourse.julialang.org/t/polynomial-manipulation/114313/40 "2024-05-26T18:17:15Z")

</div>

Package description says “alpha status”, and the last work was done in April 2023??

[Previous page](https://discourse.julialang.org/t/polynomial-manipulation/114313.md?page=1)

[Next page](https://discourse.julialang.org/t/polynomial-manipulation/114313.md?page=3)