Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|cite|improve this question

2 Answers 2

up vote 6 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.