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)?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
3
|
|
|
|
|
4
|
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). |
||
|
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
4
|
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. |
||
|
|
