Extremal Combinatorics VI: The Frankl-Wilson Theorem

flute

Rick Wilson

The Frankl-Wilson theorem is a remarkable theorem with many amazing applications. It has several proofs, all based on linear algebra methods (also referred to as dimension arguments). The original proof is based on a careful study of incidence matrices for families of sets. Another proof by Alon, Babai and Suzuki applies the “polynomial method”. I will describe here one variant of the theorem that we will use in connection with the Borsuk Conjecture (It follows a paper by A. Nilli).  I will post separately about more general versions, the origin of the result, and various applications. One application about the maximum volume of spherical sets not containing a pair of orthogonal vectors is presented in the next post.

Let n=4p and suppose that p is a prime.

Theorem: Let \cal F be a subset of \{-1,1\}^n with the property that no two vectors in \cal F are orthogonal. Then |{\cal F}| \le 4({{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}}).

We will prove a slightly modified version which easily implies the Theorem as we stated it before:

Let \cal G be the set of vectors (x_1,x_2,\dots,x_n) in \{-1,1\}^n such that x_1=1 and the number of ’1′ coordinates is even.  Let \cal F be a subset of \cal G with the property that no two vectors in \cal F are orthogonal. Then |{\cal F}| \le {{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}}.

Proof:

The ad-hoc trick:

Claim 1: Let x,y\in {\cal G}. If <x,y>=0(mod~p) then <x,y>=0.

This is a crucial part of the argument and as far as I can see the part that you need to replace entirely in other applications of the method.

We need 

Claim 1′:  For every x,y\in {\cal G}, <x,y>=0(mod~4).

Given Claim 1′, if <x,y>=0(mod~p) then <x,y>=0(mod~4p). Since the first coordinate is 1 it is not possible that y=-x and it follows that <x,y>=0.

Proof (of Claim1′):  Suppose that the number of coordinates i where x_i=1 and y_i=1 is a, the number of coordineates where x_i=1 and y_i=-1 is b, the number of coordineates where x_i=-1 and y_i=1 is c, and the number of coordineates where x_i=-1 and y_1=-1 is d. The inner product <x,y>=a-b-c+d. Now a+b is even and also a+c is even so b+c is also even and 2b+2c is divisible by 4. a+b+c+d=n is divisible by 4 and therefore so is a-b-c+d=(a+b+c+d)-2(b+c).

The algebra-puzzle trick

Compute (x-a)\times (x-b)\times(x-c)\times \dots \times (x-z).

The answer is ZERO because one of the terms is (x-x).

 

Magic:  underline the empty line with your mouse to see the solution.

Define a family of polynomials in n variables x_1,x_2,\dots, x_n, over the field with p elements F_p as follows. For every y=(y_1,y_2,\dots,y_n)\in F define P_y(x_1,x_2,\dots,x_n)=\prod_{k=1}^{p-1}(<x,y>-k). Here x=(x_1,x_2\dots,x_n).

Claim 2: For x,y\in{\cal F}, x\ne y we have P_y(x)=0.  

Proof: Since <x,y>\ne 0 we must have that <x,y>=k(mod~p) for some k, 1 \le k \le p-1. Therefore one of the terms in the product defining P_y(x) must vanish. (Remember, we work over the field with p elements. Ahla!

Claim 3: P_y(y)\ne 0.

Proof: The inner product of a vector with itself <y,y>=0 in F_p.  This is important! Therefore P_y(y)=(-1)^{p-1}(p-1)!\ne 0. (It is a product of non-zero numbers modulo p. What is (p-1)! modulo p? This is a result of a different Wilson.) Walla!

Remark: Some people prefer to simply write P_y(x)=<x,y>^{p-1} -1 which gives a different less extravagant way to present the same thing. (And without the algebra-puzzle.) I still prefer the way we defined the polynomials because for other applications of the method, it generalizes more easily. 

The linear algebra (diagonal) trick

Claim 4:  The polynomials P_y(x):y\in {\cal F} are linearly independent.

Proof:  Suppose that \sum \{\lambda_yP_y(x):y \in {\cal F}\}=0. Substitute in this sum x=z for z \in {\cal F}. By Claim 2 we obtain that the outcome is \lambda_zP_z(z). By claim 3 P_z(z)\ne 0 and therefore \lambda_z=0.  Sababa!

Remark: It is worthwhile to remember a variation of this trick, the linear algebra upper-diagonal trick, where you conclude linear independence when you assume that there is some order on  your set of y‘s and that P_y(z)=0 for y<z

The multilinearization trick

We now replace the polynomials P_y(x) by new polynomials \bar P_y(x) by applying the following rule:

Replace each x_i^{2k} by 1 and each x_i^{2k+1} by x_i!

Claim 5: The new polynomials are square-free, and they attain the same values for vectors with coordinates \pm 1.  

Proof: This is because when we have a variable x that attains only the values +1 and -1 the value of x^{2k} is 1, and the value of x^{2k+1} is the same as that of x. Walla! 

Claim 6:  The polynomials \bar P_y(x):y\in {\cal F} are linearly independent.

Proof: The proof of claim 4 applies. Walla!

The end of the proof:

By claim 6, the size of {\cal F} is at most the dimension of the vector space of square-free polynomials of degree p-1 in n variables x_1,x_2,\dots, x_n.  This dimension is the number of sqauare-free monomials of degree p-1 in n variables x_1,\dots, x_n which is {{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}}.

Sababa!

About these ads
This entry was posted in Combinatorics and tagged , . Bookmark the permalink.

6 Responses to Extremal Combinatorics VI: The Frankl-Wilson Theorem

  1. Gil Kalai says:

    The reason the second version implies the first is as follows: If we flipp the value of the first coordinate we do not change inner products so the second version applies also to subsets of {\cal G}' which is the set of all vectors with x_1=-1 having odd numbers of ’1′s. The proof only used the fact that the number of 1 coordinates is even and there are no antipodal vectors x=-y. Therefore, we can simply cover all \pm 1 vectors by 4 sets to which the second version applies.

  2. Pingback: How Large can a Spherical Set Without Two Orthogonal Vectors Be? « Combinatorics and more

  3. Anonymous says:

    Many thanks for the nice exposition! Here are two questions motivated by it.

    1) How sharp the Frankl-Wilson estimate is?
    2) What is the estimate for n *not* of the form 4p with p prime?

  4. Gil Kalai says:

    Thanks! 1) If you look at the set of all the vectors with at most p-1 ‘-1′s or at most p-1 +1′s you get an example with no two orthogonal vectors, with about half the number in the theorem. 2) If n is even but not of the form we considered you can apply Frankl-Rodl’s theorem to get bounds of the form (2-\epsilon)^n with worth value of \epsilon. (The Frankl Wilson theorem gives the correct value of \epsilon in the four times prime case.)

  5. Pingback: Borsuk’s Conjecture « Combinatorics and more

  6. Pingback: Four Derandomization Problems « Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s