Ask Your Question

Solving multilinear integer equations

asked 2012-02-06 02:06:08 -0600

Thomas gravatar image

updated 2012-02-08 04:27:35 -0600

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.

edit retag flag offensive close merge delete


Is this helpful? sage: maxima('solve(12*(y*z) + 6*(y+x) +2 -4*x*y -2*(w+x) = 0, [x,y,z,w])').sage() [[x == r1, y == r2, z == r3, w == -(2*r1 - 3)*r2 + 6*r2*r3 + 2*r1 + 1]]

achrzesz gravatar imageachrzesz ( 2012-02-06 04:51:41 -0600 )edit

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

kcrisman gravatar imagekcrisman ( 2012-02-06 07:19:02 -0600 )edit

2 answers

Sort by ยป oldest newest most voted

answered 2012-02-06 11:46:07 -0600

Volker Braun gravatar image

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.

edit flag offensive delete link more


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

kcrisman gravatar imagekcrisman ( 2012-02-06 13:40:03 -0600 )edit

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 gravatar imageThomas ( 2012-02-08 04:21:06 -0600 )edit

answered 2012-02-06 07:29:24 -0600

kcrisman gravatar image

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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2012-02-06 02:06:08 -0600

Seen: 1,319 times

Last updated: Feb 08 '12