Ask Your Question
1

Finding integer solutions to systems of polynomial equations

asked 2011-10-07 12:52:03 +0100

Nathan gravatar image

updated 2024-07-04 22:44:42 +0100

vdelecroix gravatar image

Hi,

I am trying to do something very simple but have been struggling.

Here is a simplified example that I can't get to work. I want to define polynomials with integer coefficients, say

f(A,B) = A+B, 
g(A,B) = a*A+b*B

where I want to assume that a and b are integers. I want the solver to give me the values of a and b so that f-g is equal to zero as a polynomial in A and B. So, I want it to give me a== 1, b== 1.

I have tried something like this-

R.< A,B > = ZZ[]
f = A+B
var('a', domain = ZZ)
var('b', domain = ZZ)
g = a*A+b*B
solve(f-g==0,a,b),

but what it gives me is [a == -((b-1)*B-A)/A, [1]].

How do I define variables a and b which are integers, but unknown integers? No matter what I seem to do, they are put in Symbolic Ring. How do I get the solve command to give me integer solutions to a set of linear equations?

edit retag flag offensive close merge delete

Comments

There may be infinitely many solutions to your equation. What kind of answer do you expect in that case?

Max Alekseyev gravatar imageMax Alekseyev ( 2024-07-05 14:43:41 +0100 )edit

2 Answers

Sort by ยป oldest newest most voted
1

answered 2024-07-06 14:53:48 +0100

Emmanuel Charpentier gravatar image

updated 2024-07-08 13:56:30 +0100

Not a full answer, but it seems that Sympy can find your special solution :

sage:  import sympy
sage: a, b = sympy.symbols("a, b", integer=True)
sage: A, B = sympy.symbols("A, B")
sage: f=A+B
sage: g=a*A+b*B
sage: sympy.solve(f-g, (a, b))
{a: 1, b: 1}

Now, your problem may have more solutions than that. Start with Maxima's solution (after a change of notations) :

sage: var("x, y, X, Y")
(x, y, X, Y)
sage: Sol=(X+Y-(x*X+y*Y)==0).solve((x, y)) ; Sol
[[x == -(Y*(r5 - 1) - X)/X, y == r5]]

A bit of algebraic mangling gives us :

sage: (Sol[0][0].subs(Sol[0][1].rhs()==Sol[0][1].lhs()).expand().collect_common_factors()-1).factor()
x - 1 == -Y*(y - 1)/X

which tells us that for any (integer) $y$, $(x,\, y)$ is a solution iif $\frac{Y(1-y)}{X}$ is integer. This is possible iif $\frac{X}{Y}$ is rational.

I believe that this describes the whole set of solutions, but I'd be glad to be demonstrated wrong.

Numerical example :

sage: (S:=(X+Y-(x*X+y*Y)==0).subs({X:5*sqrt(3), Y:3*sqrt(3)}).solve((x, y)))[0][0].subs(S[0][1].rhs()==S[0][1].lhs())
x == -3/5*y + 8/5

which shows that the non-trivial solutions are of the form $\left(\frac{-3k}{5},\,k\right),\,k\in\mathbb{Z}$;

HTH,

edit flag offensive delete link more
0

answered 2011-10-07 13:36:59 +0100

kcrisman gravatar image

This isn't an answer, but one thing that could be useful in general with integers is to do

assume(A,'integer')

But solve in general is via Maxima, which will assume you are using "normal" real or complex variables, and this doesn't help (because Maxima explicitly avoids your assumptions in solving, because it is assumed you are using dummy variables in solve commands).

I am not really sure how the domain parameter influences things.

edit flag offensive delete link more

Comments

I have tried using assume(a,'integer) but a still seems to be in the Symbolic Ring. It still gives me an answer for a which is often not an integer for different values of A and B.

Nathan gravatar imageNathan ( 2011-10-07 15:51:56 +0100 )edit

Right, which is why this wasn't an answer, but just some related information you might find useful. 'a' will always be in the symbolic ring unless you change it to a polynomial ring. You would probably have to use integer programming techniques of some kind...

kcrisman gravatar imagekcrisman ( 2011-10-08 22:12:20 +0100 )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

Stats

Asked: 2011-10-07 12:52:03 +0100

Seen: 4,785 times

Last updated: Jul 08