# Collinear vectors over finite fields

1. Jun 4, 2009

### daniel_i_l

F3 is a finite field with 3 elements and V is a vector space of n-tuples of elements from F3.
Is there a way to calculate the maximum number of elements in a subset S of V, such that for no three elements a,b,c in S
a+b+c=0? Or in other words, no three elements in S are on the same line.
How would I even approach this problem?
Thanks

2. Jun 4, 2009

### MrJB

Pick any two elements of F3. Let A be the set of 2^n vectors whose coordinates are those two elements of F3. No three points in A is collinear. I don't know if this is maximal though.

For example lets call the elements of F3 0, 1, and 2. In the n=2 case,
A is {{0,0},{0,1},{1,0},{1,1}}
No three of these vectors is collinear.
The size of A is 2^2=4.
4 is the best you can do for n=2, but I don't know if A is the largest set possible with the desired properties for all n. My guess is that it is.

3. Jun 5, 2009

### Hurkyl

Staff Emeritus
Allow me to restate the problem:

What is the smallest set S of points such that every line contains one of the points in S?

4. Jun 5, 2009

### daniel_i_l

MrJB: Using a brute force computer program I proved that if n=4 then it's possible to construct a set S with 17 points.

Hurkyl:
I don't understand how that restatement of the problem is easier to solve. Can you please give me a little more help?

Thanks

5. Jun 5, 2009

### Hurkyl

Staff Emeritus
I haven't worked out how to solve the problem. But my (fallable) intuition about combinatorics says that looking at the problem this way is surely easier.

6. Jun 7, 2009

### MrJB

Daniel: You're right. For n=3 there is a 9 point set and for n=4 there is a 20 point set satisfying the problem.

7. Jun 9, 2009

### daniel_i_l

How did you get those numbers?

8. Jun 9, 2009

### MrJB

I wrote a little search program. So you've got a list of all the points in your vector space. Put the first one into your set, try putting in the next point, and go down the list putting points in your set if you can do so without having three on a line. That'll give you a solution, likely not optimal. So go back to the last point you added and take it out of your set and try adding the point after that on your list and continue adding points if you can and so on. Essentially a depth first search, I think.

My program finished searching the n=3 case and found that 9 points is the best you can do. For n=4, 20 was the best solution found but I didn't finish searching all the possibilities.

Next I tried to make sense of the solutions. It helped enormously to draw a picture of the solutions, as follows.

For the n=2 case draw a 3 by 3 grid and fill in some squares such that no three filled in squares are on a row, column, and no three are on all different rows and columns, (for example (0,0)(1,2)(2,1) are all on different rows and columns, so don't put all three of those points in your set).

One solution might look like this:
(_)(_)(_)
(X)(X)(_)
(X)(X)(_)
which represents (0,0)(0,1)(1,0)(1,1)

For the n=3 case draw three of the diagrams made for the n= 2 case. After some fiddling I found the 9 point solution looked like this

(_)(_)(X)
(_)(_)(_)
(_)(_)(_)

(X)(X)(_)
(_)(_)(X)
(_)(_)(X)

(_)(_)(_)
(X)(X)(_)
(X)(X)(_)

which represents the set (0,0,0)(0,0,1)(0,1,0)(0,1,1)(1,0,2)(1,1,2)(1,2,0)(1,2,1)(2,2,2). The first coordinate specifies which of the 3x3 charts, and the other two coordinates are just column and row.

For n=4 the diagram for the 20 point solution looks like this:

(_)(_)(X) (_)(_)(X) (_)(_)(_)
(_)(_)(_) (_)(_)(_) (_)(_)(_)
(_)(_)(_) (_)(_)(_) (_)(_)(_)

(X)(X)(_) (_)(_)(_) (_)(_)(X)
(_)(_)(X) (X)(X)(_) (_)(_)(_)
(_)(_)(X) (X)(X)(_) (_)(_)(_)

(_)(_)(_) (X)(X)(_) (_)(_)(X)
(X)(X)(_) (_)(_)(X) (_)(_)(_)
(X)(X)(_) (_)(_)(X) (_)(_)(_)

I believe (conjecture?) this pattern can be generalized for any n and will yield a 44 point set for n=5, a 96 point set for n=6 and a 208 point set for n=7.

Several points
-I don't know if this pattern of constructing sets always yields the optimal case for the given n. I don't see how to prove it. But it's better than my initial guess of 2^n.
-I haven't even proven that the pattern of sets above even provides a solution to the problem. There's room for a lot more rigor here, and I've left some gaps in the work above, but hopefully this is some food for thought. I'm just trying to share ideas.
-My search program did not exploit any symmetries in the problem, of which there are many, but I didn't know how to exploit them. One way to think of the symmetries is to show how all of the four point n=2 set solutions are 'essentially equivalent'. (I think.)
-My search program was written fairly inefficiently and the searching takes much longer for bigger n. For n=4 I found the 20 point set, but the program didn't finish searching. For n=5 it didn't even find the 44 point set.
-I don't know if a 'depth-first' search is the best way to go here. This really isn't my area.

Question: Where did you find this problem? I'm curious if there's any context.

9. Jun 10, 2009

### daniel_i_l

Hi,
Those are some interesting results. First I'll explain the context:
Did you ever play the game set?
http://www.setgame.com/set/
If you haven't, then the important part for right now is that there're 81 cards in the deck. Each one has 4 attributes where each attribute can be in one of 3 different types:
Color - red, blue, green
Shape - diamonds, squiggly, oval