Re: Re: LatticeReduce

*To*: mathgroup at smc.vnet.net*Subject*: [mg93600] Re: [mg93580] Re: LatticeReduce*From*: danl at wolfram.com*Date*: Mon, 17 Nov 2008 06:18:03 -0500 (EST)*References*: <200811151103.GAA16591@smc.vnet.net> <491F2366.3040401@csl.pl>

> P.S. > And for the case: > {a1, a2, a3} = {1, 3^4, > 5^4}; a = {{1, 0, 0, -a1}, {0, 1, 0, -a2}, {0, 0, 1, -a3}}; b = > LatticeReduce[a] > > Out1:*{{1, 0, 0, -1}, {12, -8, 1, 11}, {-6, -23, 3, -6}} > > Mathematica should be return 2 solutions: > > 23 - 8*3^4 + 5^4=0 > 12 + 23*3^4 - 3*5^4=0 > > **After good LatticeReduce should begin from : {{23,-8,1,0}, {12, > 23,-3,0}, {c, c1,c2, c3}} > > What is wrong in LatticeReduce or what I'm doing wrong ? > > Artur You are misunderstanding what lattice reduction means. It has no underlying understanding of any equations to solve, it simply reduces lattices. As far as I can tell, it is doing just that in your examples. If you want to get solutions to your equations, there are various approaches. One is to use Reduce or FindInstance (you will need restrictions to avoid the zero solution for that latter, since the equation is homogeneous). You might use Minimize, imposing an objective function, as below. {a0, a1, a2} = {1, 2^15, -3^8}; In[32]:= Minimize[{x + y + z, {x, y, z}.{a0, a1, a2} == 0, x >= 1, y >= 1, z >= 1}, {x, y, z}, Integers] Out[32]= {43, {x -> 37, y -> 1, z -> 5}} (Or just minimize x, maybe.) In[42]:= Minimize[{x, {x, y, z}.{a0, a1, a2} == 0, x >= 1, y >= 1, z >= 1}, {x, y, z}, Integers] Out[42]= {1, {x -> 1, y -> 7093, z -> 35425}} If you seek reasonably small solutions, you might use LatticeReduce as follows. Weight your lattice in such a way as to push the last column coordinates toward zero, in the hope of getting solutions. Here is an example. {a1, a2, a3} = 10*{1, 3^4, 5^4}; a = {{1, 0, 0, -a1}, {0, 1, 0, -a2}, {0, 0, 1, -a3}}; b = LatticeReduce[a] {{1, 0, 0, -10}, {23, -8, 1, 0}, {-12, -23, 3, 0}} Now you see those "small" solutions that generate the full solution set. There are other approaches, using ExtendedGCD, HermiteDecomposition, or LinearSolve. Which are desireable would depend on what specifically you seek (generating set? small solutions?...). Daniel Lichtblau Wolfram Research > Artur pisze: >> Dear Mathematica Gurus, >> I want to find such inetegrs x,y,z that >> x + y*2^15 + z*3^8 = 0 >> I'm reading in manual that I can use LatticeReduce >> >> {a0, a1, a2} = {1, >> 2^15, -3^8}; a = {{1, 0, 0, -a0}, {0, 1, 0, -a1}, {0, 0, >> 1, -a2}}; b = LatticeReduce[a] >> >> Out1:{{1, 0, 0, -1}, {18, 1, 5, 19}, {117, -171, -854, 117}} >> >> That mean that computer don't find such solution (solution is finded >> when last number in one of rows should be 0) >> >> If I run again: >> {a0, a1, a2} = {37, >> 2^15, -3^8}; a = {{1, 0, 0, -a0}, {0, 1, 0, -a1}, {0, 0, >> 1, -a2}}; b = LatticeReduce[a] >> >> Out2:{{1, 1, 5, 0}, {1, 0, 0, -37}, {170, -7, -34, 12}} >> >> Now solution is finded by Mathematica OK! >> k = Transpose[{{37, 2^15, -3^8, anything}}]; b[[1]].k >> >> Out3: {0} >> >> Is OK! >> >> Is another method finding coefficients x, y, z as LatticeReduce and >> why Mathematica don't reduced >> {a0, a1, a2} = {1, 2^15, -3^8}; a = {{1, 0, 0, -a0}, {0, 1, 0, -a1}, >> {0, 0, 1, -a2}}; b = LatticeReduce[a] >> >> >> Best wishes >> Artur >> >

**References**:**Basic programming***From:*BionikBlue <frankflip@hotmail.com>