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



Linear Algebra Over $F_{2}$
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). 


