Solving multilinear integer equations

i like this post (click again to cancel)
i dont like this post (click again to cancel)

I'd like to explore the solutions of a multilinear diophantine equation like $12(yz) + 6(y+z) +2 -4xw -2(w+x) = 0$. In particular I'd like to generate instances of solutions. I tried the function solve like:

(x,y,z,w) = var('x,y,z,w')
assume(x, 'integer'); assume(y, 'integer')
assume(z, 'integer'); assume(w, 'integer')
solve([12*(y*z) + 6*(y+z) +2 -4*x*w -2*(w+x) == 0, y==y], x)

which gives me the not particularly useful output:

[[x == (3*(2*r1 + 1)*r2 + 3*r1 - r3 + 1)/(2*r3 + 1), y == r1, z == r2, w == r3]]

I'd like to generate some actual quadruples that solve this equation or possibly investigate the structure more. Is there some systematic way to do this? In particular, when playing around with coefficients, is there a test of existence of an integer solution?

Edit: I had typos in the first version, I edited the equation.

asked Feb 06 '12

Thomas gravatar image Thomas flag of Germany
15 1 1 7

updated Feb 08 '12

Is this helpful?

sage: maxima('solve(12(yz) + 6(y+x) +2 -4xy -2(w+x) = 0, [x,y,z,w])').sage()

[[x == r1, y == r2, z == r3, w == -(2r1 - 3)r2 + 6r2r3 + 2*r1 + 1]]

achrzesz (Feb 06 '12)

Hmm, but those are real solutions, not integer, though in this case it looks like it will work if you use all integers.

kcrisman (Feb 06 '12)

2 Answers:

i like this answer (click again to cancel)
i dont like this answer (click again to cancel)

This is NOT a 'real' answer - achrzesz had the real idea. Maybe he should post it for credit. This is just it in Sage.

sage: (x,y,z,w) = var('x,y,z,w')
sage: solve([12*(y*z) + 6*(y+x) +2 -4*x*y -2*(w+x) == 0,y==y], x,y,z,w)
[[x == r6, y == r7, z == r8, w == -(2*r6 - 3)*r7 + 6*r7*r8 + 2*r6 + 1]]

You may ask why we need the dummy equation y==y. See this Trac ticket.

This does not answer the question of how to treat this as a non-linear Diophantine equation. I seem to recall that this is undecidable, but maybe I'm misinterpreting your question. You can always just do something really naive like loop through all integers. I don't know that we have anything more efficient that that for integers.


posted Feb 06 '12

kcrisman gravatar image kcrisman
7812 20 78 170
i like this answer (click again to cancel)
i dont like this answer (click again to cancel)

You can divide by $2$ and solve for $w$. So the set of all solutions is parametrized by $(x,y,z)\in\mathbb{Z}^3$ arbitrary.


posted Feb 06 '12

Volker Braun gravatar image Volker Braun
2701 9 24 60

Well, Thomas did say equations like that one, not just that one...

kcrisman (Feb 06 '12)

Well, I have a typo even in the first example :( My starting point was $4nyz + 2n(y + z) + n - 4wx - 2(w + x) ? 1 = 0$ for odd $n$.

Thomas (Feb 08 '12)

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!
Login/Signup to Post

Question tools

1 follower



Asked: Feb 06 '12

Seen: 571 times

Last updated: Feb 08 '12

powered by ASKBOT version 0.7.22
Copyright Sage, 2010. Some rights reserved under creative commons license.