Gil Kalai’s blog

## Extremal Combinatorics VI: The Frankl-Wilson Theorem

Posted on May 21, 2009 by

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}}$.

## 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!

### Like this:

This entry was posted in Combinatorics and tagged Peter Frankl, Richard Wilson. 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

• ### Blogroll

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 108, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8839746713638306, "perplexity_flag": "head"}