Linear Algebra Over $F_{2}$

Question

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$)?

Answer 1

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

Answer 2

You can find S whose size is exponential in n. For example, consider F^{2n+1}. Our coordinates will be (x_1,y_1,...,x_n,y_n,z). For each subset T of {1,...,n}, define S_T to be the point with the coordinates

x_i=y_i = 1 if i \in T

x_i=y_i = 0 if i \notin T

z = 1

It is easy to see then that the set of all S_T satisfies your conditions.