## 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

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

### Re: Efficient method to find lattice points

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.

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

### Re: Efficient method to find lattice points

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.

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

### Re: Efficient method to find lattice points

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

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

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

Taking the logarithm we find the equation:
$\sum_{k = 1}^n x_k\log(a_k) = 0$
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
"Ich bin ein Teil von jener Kraft, die stets das Böse will und stets das Gute schafft."