# Linear Algebra Over F_{2}

Suppose we call a subset S of F^{n} (F is the field with two elements) good if for any x and y (possibly x=y) we have [x,y]=1 where [ , ] denotes the obvious bilinear form on F. What's the best bound as a function of n on the size of S? In particular, do we have |S| less than or equal to n (or just a linear function in n)?

-

Andy's example is actually within a constant factor of optimal. To see this, imagine adding on an additional coordinate equal to 1 to each element of S. These new elements now satisfy [x',y']=0.

Now let W be the subspace of F^{n+1} spanned by the augmentation of S. The above relation is equivalent to saying that W is contained in its own orthogonal complement. Since the dimension of a space and that of its complement add to n+1, we know the dimension of W is at most (n+1)/2, so W contains at most 2^{(n+1)/2} vectors.

This result (and proof) is one I've heard referred to as the Eventown theorem and attributed to Berlekamp.

As an interesting side note, if we replaced the condition [x,y]=1 for all x,y by one saying that [x,y]=1 if and only if x does not equal y, then we'd have a bound of n on the size of S (this is Berlekamp's oddtown theorem).

-