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

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

Gil Kalai says:

May 21, 2009 at 11:55 am

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.

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

May 24, 2009 at 3:36 pm

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?

Gil Kalai says:

May 24, 2009 at 4:17 pm

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

Pingback: Borsuk’s Conjecture « Combinatorics and more
Pingback: Four Derandomization Problems « Combinatorics and more

	TakisTao on Levon Khachatrian’s Memo…
	Margene on Some Philosophy of Scienc…
	Seth on Navier-Stokes Fluid Computers
	John Sidles on BosonSampling and (BKS) Noise…
	ashish soni on Navier-Stokes Fluid Computers
	Gil Kalai on Navier-Stokes Fluid Computers
	Joseph Malkevitch on Navier-Stokes Fluid Computers
	gowers on Polymath5 – Is 2 logarit…
	John Sidles on Navier-Stokes Fluid Computers
	Gil Kalai on Navier-Stokes Fluid Computers
	Gil Kalai on Navier-Stokes Fluid Computers
	Gil Kalai on Navier-Stokes Fluid Computers