Extremal Combinatorics VI: The Frankl-Wilson Theorem

Posted on May 21, 2009 by Gil Kalai

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 an odd 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!

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

Reply
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?

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

Reply
Pingback: Borsuk’s Conjecture « Combinatorics and more
Pingback: Four Derandomization Problems « Combinatorics and more
Pingback: Combinatorics and More – Greatest Hits | Combinatorics and more
dvhoan says:

June 28, 2015 at 8:21 pm

Dear Prof. Gil Kalai,
Is Claim 1 correct? If I take p = 2, n = 4×2 = 8. Let x = (1,1,1,1,-1,-1,-1,-1), y = (1,-1,1,1,1,-1,-1,-1), then = 0 mod 2 but =6 mod 8, a contradiction.

Reply
dvhoan says:

June 28, 2015 at 8:24 pm

Dear Prof. Gil Kalai,
Is Claim 1 correct? If I take p = 2, n = 4×2 = 8. Let x = (1,1,1,1,-1,-1,-1,-1), y = (1,-1,1,1,1,-1,-1,-1), then $ = 0$ (mod 2) but $=4$ (mod 8), a contradiction.

Reply
- Gil Kalai says:
  
  June 29, 2015 at 4:19 pm
  
  Right, it is always the case that = 0 (mod p) but for being 0 (mod 4p) we need that p is an odd prime. Corrected. Thanks.
  
  Reply
  - dvhoan says:
    
    June 29, 2015 at 10:29 pm
    
    Yes, number 2 is only the even prime. I think it’s better to say p>2.
dvhoan says:

June 30, 2015 at 7:56 am

Dear Prof. Gil Karai,
I really don’t understand your argument at the end of the proof : “number of square-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}}$ .”
For example, $p = 3, n=12$ , square-free monomials of degree 2 in 12 variables are $1, x_1, x_2, ..,x_12$ , hence there are 13 square-free monomials in 12 variables. BUT your answer is $1+ {{12}\choose {1}}+ {{n}\choose {2}} = 1+12+ 66 = 79$ . Could you please explain?
Many thanks,

Reply
- Gil Kalai says:
  
  June 30, 2015 at 8:56 am
  
  Dear dvhoan, The square free monomials are 1, $x_1,x_2,\dots x_12$ , $x_1x_2, x_1x_3, \dots x_{11}x_{12}$ . So for every subset of {1,2,…,12} of size 0, 1, 2 we have a monomial which is the product of variables with indices in the subset.
  
  Reply
  - dvhoan says:
    
    June 30, 2015 at 10:22 am
    
    Dear Prof. Gil Kalai, I understand now. Thank you so much for your nice explanation.
Pingback: Updates and plans III. | Combinatorics and more
Pingback: Difference sets missing a Hamming sphere | Quomodocumque

	fedja on Chess can be a Game of Lu…
	qm computing summer… on The Race to Quantum Technologi…
	Murat Aygen on Remote Blogging: Efficiency of…
	Gil Kalai on Chess can be a Game of Lu…
	fedja on Chess can be a Game of Lu…
	Solvig Kadison-Singe… on The Kadison-Singer Conjecture…
	Matthew Cory on Call for nominations for the O…
	Matthew Cory on The Race to Quantum Technologi…
	domotorp on Chess can be a Game of Lu…
	Gil Kalai on The Race to Quantum Technologi…
	Notes of the seminar… on Mind Boggling: Following the w…
	Optimal Colorful Tve… on Seven Problems Around Tverberg…