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!

This entry was posted in Combinatorics and tagged Peter Frankl, Richard Wilson. Bookmark the permalink.

19 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
Pingback: Basic Notions Seminar is Back! Helly Type Theorems and the Cascade Conjecture | Combinatorics and more
Pingback: Peter Keevash and Eoin Long: Forbidden vector-valued intersections | Combinatorics and more
Pingback: Extremal Combinatorics V: POSETS | Combinatorics and more

	Aleksander Coho on Elchanan Mossel’s Amazin…
	Gil Kalai on Gil’s Collegial Quantum…
	TYI 41: How many ste… on Gil’s Collegial Quantum…
	The story of Poincar… on Gil’s Collegial Quantum…
	Gil Kalai on Gil’s Collegial Quantum…
	Peter Shor on Gil’s Collegial Quantum…
	Gil Kalai on Gil’s Collegial Quantum…
	Peter Shor on Gil’s Collegial Quantum…
	Gil Kalai on Lior, Aryeh, and Michael
	Gil Kalai on Gil’s Collegial Quantum…
	Google, IBM, and the… on Quantum computers: amazing pro…
	Not Quite Getting Up… on Gil’s Collegial Quantum…