Frankl-Wilson Theorem

Given prime , integer , and
Suppose is a family of subsets of
such that for all ; and for all distinct -subfamilies.
Then

Proof

Repeat the following until our family is empty.
At stage , choose one of the remaining subsets ,
and denote it by , choose another remaining subset
such that if possible, then …
Thus we find

but adding any new set from our remaining family,
the intersection must be in .
By assumption .
Set
and remove all these sets
and proceed to stage .
We end up with subfamily with
and such that
but for any we have:

Now define by

Note but for all .
Define linear functionals

and observe they satisfy the conditions of Diagonal Principle;
so the must be linearly independent.
But the are polynomials of degree in ,
so spanned by

monomials.
However, over , for all .
So where the can be obtained from by reducing all exponents to .
So they are also linearly independent, but spanned by

of size

Therefore