= Solution
The <Frankl-Wilson theorem> in its uniform form says: let $p$ be a <prime number>, let $L\subseteq\mathbb F_p$ have size $s\leq\min(k,n-k)$, and let $\mathcal F\subseteq\binom{[n]}k$ have $k\bmod p\notin L$, while $|A\cap B|\bmod p\in L$ for every distinct pair of members. Then
$$
\boxed{|\mathcal F|\leq\binom ns.}
$$
The modular-intersection, nonuniform form of the <Frankl-Wilson theorem> is as follows. Let $p$ be a <prime number>, let $L\subseteq\mathbb F_p$ have $s$ elements, and let $\mathcal F\subseteq\mathcal P([n])$ satisfy $|A|\bmod p\notin L$ for each $A\in\mathcal F$, whereas $|A\cap B|\bmod p\in L$ for distinct $A,B\in\mathcal F$. Then
$$
\boxed{|\mathcal F|\leq\sum_{j=0}^{\min(s,n)}\binom nj.}
$$
This <nonuniform Frankl-Wilson theorem> allows different sizes and different diagonal residues; in particular it applies when all sizes have one common residue outside $L$.
To prove it by the <polynomial method in combinatorics>, work over the <finite field> $\mathbb F_p$ and associate to each member the <intersection polynomial>
$$
P_A(x_1,\ldots,x_n)=\prod_{\ell\in L}\left(\sum_{i\in A}x_i-\ell\right).
$$
Replace each positive power of $x_i$ in its expansion by $x_i$ to obtain its <multilinear reduction on the Boolean cube> $\widetilde P_A$. This preserves evaluation on every <characteristic vector>, whose coordinates are zero or one, and leaves degree at most $s$. At the <characteristic vector> $\mathbf1_B$,
$$
\widetilde P_A(\mathbf1_B)=\prod_{\ell\in L}(|A\cap B|-\ell).
$$
It is zero for distinct $A,B$, and nonzero for $B=A$ by the diagonal hypothesis. If $\sum_{A\in\mathcal F}c_A\widetilde P_A=0$, evaluating at each $\mathbf1_B$ forces $c_B=0$. Thus the <multilinear polynomials> are <linearly independent>. They belong to the <vector space> with <basis> the square-free <monomials> $\prod_{i\in S}x_i$ for $|S|\leq s$, whose <dimension> is the displayed sum. This proves the nonuniform form, including $s=0$, where distinct members are impossible and the empty product is one.
For the sharp uniform form, we need the <low-degree evaluation rank on a uniform layer>. Form the integer <matrix> $M$ whose rows are indexed by $S\subseteq[n]$ with $|S|\leq s$, columns by $k$-subsets $T$, and entries $M_{S,T}=\mathbf1_{S\subseteq T}$. These are evaluations of the square-free <monomials>. Over the <rational numbers>, the row of a $j$-subset $S$ satisfies
$$
\sum_{\substack{R\supseteq S\\|R|=s}}M_{R,T}
=\binom{k-j}{s-j}M_{S,T}\qquad\text{for every }T.
$$
Indeed, when $S\subseteq T$ the left side counts the $s$-subsets between $S$ and $T$, and otherwise both sides vanish. Since $s\leq k$, the coefficient is a positive integer. Thus the degree-$s$ rows span all the rows over the <rational numbers>, giving $\operatorname{rank}_{\mathbb Q}M\leq\binom ns$. Every square submatrix of larger size has integer <determinant> zero, so its <determinant> remains zero modulo $p$. Hence
$$
\operatorname{rank}_{\mathbb F_p}M\leq\operatorname{rank}_{\mathbb Q}M\leq\binom ns.
$$
This reduction of <matrix rank> is the reason one must not try to divide by $\binom{k-j}{s-j}$ directly in $\mathbb F_p$.
The evaluations of the $\widetilde P_A$ on the $k$th <uniform layer of the Boolean cube> lie in the row <linear span> of $M$ over $\mathbb F_p$. They are <linearly independent> as functions there, because restriction to the columns corresponding to $\mathcal F$ still gives the nonzero diagonal evaluation matrix. Their number is consequently at most $\binom ns$. This completes the proof of the uniform <Frankl-Wilson theorem> as well.
For the odd-cardinality problem the sharper <Oddtown theorem> follows directly from <linear algebra>. Let $v_A=\mathbf1_A\in\mathbb F_2^n$ be the <characteristic vector>. The parity conditions say
$$
v_A\cdot v_B=0\quad(A\ne B),\qquad v_A\cdot v_A=1.
$$
For any <linear combination> $\sum_A c_Av_A=0$, take its <dot product> with $v_B$. All off-diagonal terms vanish, leaving $c_B=0$. Hence these vectors are <linearly independent> in an $n$-dimensional <vector space>, giving
$$
\boxed{|\mathcal A|\leq n.}
$$
The singleton <sets> show that the bound can be attained. Notice why the constant term in the general <nonuniform Frankl-Wilson theorem> is unnecessary here: these <dot products> already give a diagonal evaluation matrix using only the $n$ coordinate functions.
For even $n$, partition $[n]$ into the pairs $\{1,2\},\{3,4\},\ldots,\{n-1,n\}$ and take every union of a selection of these pairs. This gives exactly $2^{n/2}$ distinct <sets>, including the empty <set>. Each has even size; every pairwise <intersection> is again a union of entire pairs and therefore has even size. \b[This attains the proposed bound.]
For any <set family> satisfying the even-cardinality conditions, let $W$ be the <linear span> of its <characteristic vectors> over $\mathbb F_2$. Now the self-<dot products> vanish as well as the off-diagonal ones. By <bilinearity>, $u\cdot v=0$ for all $u,v\in W$, so $W\subseteq W^\perp$: it is a <self-orthogonal binary subspace>.
For completeness the standard <bilinear form> on $\mathbb F_2^n$ is <nondegenerate>, because a vector orthogonal to every coordinate vector has every coordinate zero. Thus the map $v\mapsto(w\mapsto v\cdot w)$ from $\mathbb F_2^n$ onto the <dual space> $W^*$ is surjective: every <linear functional> on $W$ extends to the whole <vector space> by extending a <basis>, and every such functional on $\mathbb F_2^n$ is a <dot product> with a vector. Its <kernel> is $W^\perp$. The <rank-nullity theorem> consequently gives $\dim W^\perp=n-\dim W$. The inclusion $W\subseteq W^\perp$ implies $\dim W\leq n/2$. Finally, distinct members have distinct <characteristic vectors>, all in $W$, and a $k$-dimensional <vector space> over $\mathbb F_2$ has exactly $2^k$ elements. Therefore
$$
\boxed{|\mathcal A|\leq|W|=2^{\dim W}\leq2^{n/2}.}
$$
This proves the <Eventown theorem> and also explains the suggested <dimension> contradiction if the <set family> had more than $2^{n/2}$ members.
Back to article page
