## Extremal Combinatorics VI: The Frankl-Wilson Theorem

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:

Claim 1: Let $x,y\in {\cal G}$. If $=0(mod~p)$ then $=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}$, $=0(mod~4)$.

Given Claim 1′, if $=0(mod~p)$ then $=0(mod~4p)$. Since the first coordinate is 1 it is not possible that $y=-x$ and it follows that $=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 $=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}(-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 $\ne 0$ we must have that $=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 $=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)=^{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.

## 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 , . Bookmark the permalink.

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

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

4. dvhoan says:

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.

5. dvhoan says:

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.

• Gil Kalai says:

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.

• dvhoan says:

Yes, number 2 is only the even prime. I think it’s better to say p>2.

6. dvhoan says:

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,

• Gil Kalai says:

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.

• dvhoan says:

Dear Prof. Gil Kalai, I understand now. Thank you so much for your nice explanation.