Efficient method to find lattice points

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Giallo
Posts: 226
Joined: Sat Jan 01, 2011 11:31 pm UTC
Location: ETH, Zürich, Switzerland
Contact:

Efficient method to find lattice points

Postby Giallo » Wed Apr 11, 2012 3:41 pm UTC

Hi everybody!
Given the normal vector to an m-plane in Rn (n > m), is there any efficient method to find lattice points (ie: points with integer coordinates) on that plane?
"Ich bin ein Teil von jener Kraft, die stets das Böse will und stets das Gute schafft."

gorcee
Posts: 1501
Joined: Sun Jul 13, 2008 3:14 am UTC
Location: Charlottesville, VA

Re: Efficient method to find lattice points

Postby gorcee » Wed Apr 11, 2012 4:12 pm UTC

Is this homework? Regardless, I'll throw out what I've thought up really quickly.

So you have a normal vector, n. From this you can define a plane by finding vectors orthogonal to n (and to each other). These m vectors form a basis. Call them b_1, b_2, ..., b_m.

So, any point on the plane can be written as a combination of the basis vectors. Thus, the point (1,0,0,...,0) on the plane can be written as 1/||b_1||*b_1+0*b_2+...+0*b_m. You can proceed with this process for each basis vector, and then it seems as though you can generate integer coordinates from this operation.

Edit: I'm not sure if you want to find points on the plane that correspond to integer coordinates in R^n, or find coordinates in R^n that correspond to integer points on the plane. Either way, it seems like essentially the same process, but I've only given it about 90 seconds worth of thought, so I might be missing something critical.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5965
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Efficient method to find lattice points

Postby jestingrabbit » Wed Apr 11, 2012 10:37 pm UTC

Giallo wrote:Hi everybody!
Given the normal vector to an m-plane in Rn (n > m), is there any efficient method to find lattice points (ie: points with integer coordinates) on that plane?


Unless n = m+1, you're going to want more than one normal vector. If you look at { v | v.w = 0} you have an n-1 dimensional vector space. You need n-m linearly independent normal vectors to specify a single subspace.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: Efficient method to find lattice points

Postby Proginoskes » Thu Apr 12, 2012 7:37 am UTC

Giallo wrote:Hi everybody!
Given the normal vector to an m-plane in Rn (n > m), is there any efficient method to find lattice points (ie: points with integer coordinates) on that plane?


Yes. Google for "linear diophantine equations in three variables". Dr. Math has a good explanation.

Giallo
Posts: 226
Joined: Sat Jan 01, 2011 11:31 pm UTC
Location: ETH, Zürich, Switzerland
Contact:

Re: Efficient method to find lattice points

Postby Giallo » Fri Apr 13, 2012 1:03 pm UTC

It's not homework; @jestingrabbit: you're right, stupid me :oops:

Anyway this comes out from the following problem (*): given the equation
[math]\prod_{k = 1}^n a_k^{x_k} = 1[/math]
with ak's algebraic find a solution where xk's are in Z.

Taking the logarithm we find the equation:
[math]\sum_{k = 1}^n x_k\log(a_k) = 0[/math]
which corresponds to find the lattice points of the (n-1) dimensional plane with normal vector (a1, ... , an) in Rn.

Only a friend of mine told me that (*) should have an optimal solution which is something like O(2n), and I wanted to check :wink:
"Ich bin ein Teil von jener Kraft, die stets das Böse will und stets das Gute schafft."


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests