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

	marouane rhafli on Polymath 8 – a Succ…
	John Sidles on Why Quantum Computers Cannot W…
	Gil Kalai on Why Quantum Computers Cannot W…
	Gil Kalai on The Kadison-Singer Conjecture…
	John Sidles on Why Quantum Computers Cannot W…
	John Sidles on Why Quantum Computers Cannot W…
	John Sidles on Why Quantum Computers Cannot W…
	Gil Kalai on Why Quantum Computers Cannot W…
	Peter W. Shor on Why Quantum Computers Cannot W…
	Anonymous on The Kadison-Singer Conjecture…
	Gil Kalai on Why Quantum Computers Cannot W…
	John Sidles on Why Quantum Computers Cannot W…