Collinear vectors over finite fields

[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

 

[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 let's 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.

 

[Hurkyl]

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?

 

[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:

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?

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

Thanks

 

[Hurkyl]

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

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.

 

[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.

 

[daniel_i_l]

How did you get those numbers?

 

[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.

 

[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
Filling - fill, shaded, empty
Number - 1, 2, 3
For example, one of the cards has two red, shaded, ovals.
Three cards form a set if for each one of the attributes the cards are either all the same or all different.
I tried to think of a way to find the smallest number of cards that always contains at least one set.
That question is essentially the same as the one I posted if each 4-tuple represents a card where every element is a different attribute. Because of the properties of F3, three vectors form a set iff their sum is 0.
So if your result is true then with 21 cards there'll always be a set.