Puzzle time: Integer Points in Space

[jon-nyc]

A "lattice point" in three-dimensional space is a point whose coordinates are integers, e.g., (0,4,-3).  Suppose L is a set of lattice points in 3-space with the property that no two points in L have a third lattice point on the line segment between them.  How big can L be?

[Klaus]

Wouldn't a function that grows sufficiently fast be enough to create infinitely many such points?

E.g., in 2D the points (n,2^(n-1)).

Or maybe, if that's not fast enough, (n, A(n,n)), where A is the Ackermann function.

[jon-nyc]

I think it's very much finite.

[jon-nyc]

My gut response was you could use unique primes and get to infinity but that is a dead end, since the differences between the primes are all even numbers.

[Klaus]

Oh, I think I misread the task. I understood "no two points in L have a third lattice point in L on the line segment between them".

Hmm...

[Klaus]

Why don't the prime numbers work?

Let's take the 2D case again.

From what I can see, the key theorem is that the segment between two lattice points (x,y) and (x+a,y+b) won't intersect any other lattice point if and only if a and b are coprime.

Seems to be simple to construct infinitely many such pairs of lattice points.

Is the point that this is in 3D rather than 2D? But if you find infinitely many such points in 2D and embed them into a 3D plane, that should also give you infinitely many pairs in 3D.

Maybe I'm missing something.

[jon-nyc]

@Klaus Primes don't work because you can't force such differences across all pairs.

[Klaus]

Ah, I see the problem now.

If you take, say, (0,0), (2,3) and (5,7), then the segment between the two last points, (5-2,7-3) = (3,4) has non-primes in it and, with a different example, numbers that are not co-prime.

So, in 2D, I propose that L has at most three points. For instance, L = {(0,0),(1,1),(2,3)}. If you take any other point (p,q), then the difference to one of the points in L must contain two even numbers, which are not coprime. I assume it is like that with any other set of three points in L.

I leave the generalization to N dimensions, including N=3, as an exercise to the reader.

[jon-nyc]

Yes.

Consider lattice points mod 2. There are only eight possible configurations. Two lattice points with identical values mod 2 have a lattice point midpoint.

[jon-nyc]

Official solution came out today:

SOLUTION: The first issue to be addressed here is: When do two lattice points, say (a,b,c) and (d,e,f), have another lattice point on the line segment between them? A moment's thought will convince you that this happens when the numbers a - d, b - e, and c - f have a common divisor. The "easiest" common divisor for them to have is 2, and this will happen if a - d, b - e, and c - f are all even, i.e., if the two lattice points have the same parity coordinatewise. When that happens, the midpoint of the two lattice points, namely, the vector ((a + d)/2, (b + e)/2, (c + f)/2), will be a lattice point.

But there are only 2^3 = 8 different parities available, so by the pigeonhole principle, we can't have more than eight points in our set L. Can we have eight? Yes, just let L consist of the corners of a unit cube