Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 14 4 Solution Created 2026-10-03 Updated 2026-10-14
The Frankl-Wilson theorem in its uniform form says: let be a prime number, let have size , and let have , while for every distinct pair of members. Then
The modular-intersection, nonuniform form of the Frankl-Wilson theorem is as follows. Let be a prime number, let have elements, and let satisfy for each , whereas for distinct . ThenThis nonuniform Frankl-Wilson theorem allows different sizes and different diagonal residues; in particular it applies when all sizes have one common residue outside .
To prove it by the polynomial method in combinatorics, work over the finite field and associate to each member the intersection polynomialReplace each positive power of in its expansion by to obtain its multilinear reduction on the Boolean cube . This preserves evaluation on every characteristic vector, whose coordinates are zero or one, and leaves degree at most . At the characteristic vector ,It is zero for distinct , and nonzero for by the diagonal hypothesis. If , evaluating at each forces . Thus the multilinear polynomials are linearly independent. They belong to the vector space with basis the square-free monomials for , whose dimension is the displayed sum. This proves the nonuniform form, including , 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 whose rows are indexed by with , columns by -subsets , and entries . These are evaluations of the square-free monomials. Over the rational numbers, the row of a -subset satisfiesIndeed, when the left side counts the -subsets between and , and otherwise both sides vanish. Since , the coefficient is a positive integer. Thus the degree- rows span all the rows over the rational numbers, giving . Every square submatrix of larger size has integer determinant zero, so its determinant remains zero modulo . HenceThis reduction of matrix rank is the reason one must not try to divide by directly in .
The evaluations of the on the th uniform layer of the Boolean cube lie in the row linear span of over . They are linearly independent as functions there, because restriction to the columns corresponding to still gives the nonzero diagonal evaluation matrix. Their number is consequently at most . 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 be the characteristic vector. The parity conditions sayFor any linear combination , take its dot product with . All off-diagonal terms vanish, leaving . Hence these vectors are linearly independent in an -dimensional vector space, givingThe 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 coordinate functions.
For even , partition into the pairs and take every union of a selection of these pairs. This gives exactly 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. This attains the proposed bound.
For any set family satisfying the even-cardinality conditions, let be the linear span of its characteristic vectors over . Now the self-dot products vanish as well as the off-diagonal ones. By bilinearity, for all , so : it is a self-orthogonal binary subspace.
For completeness the standard bilinear form on is nondegenerate, because a vector orthogonal to every coordinate vector has every coordinate zero. Thus the map from onto the dual space is surjective: every linear functional on extends to the whole vector space by extending a basis, and every such functional on is a dot product with a vector. Its kernel is . The rank-nullity theorem consequently gives . The inclusion implies . Finally, distinct members have distinct characteristic vectors, all in , and a -dimensional vector space over has exactly elements. ThereforeThis proves the Eventown theorem and also explains the suggested dimension contradiction if the set family had more than members.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 10 4 Solution Created 2026-10-03 Updated 2026-10-07
The general modular form, the nonuniform Frankl-Wilson theorem, can be stated as follows. Let be a prime number, and let have elements. Suppose has for every member, while for any distinct members. ThenThe uniform Frankl-Wilson theorem sharpens this to when all members have size and . Both forms require a prime modulus and exclusion of the self-intersection residue.
For the general proof, work over the finite field . Associate to each member the intersection polynomialAt the characteristic vectors of sets , this is zero if , and nonzero if . Thus these polynomials, regarded as functions on the Boolean hypercube, are linearly independent: evaluating any relation at isolates its coefficient. Apply multilinear reduction on the Boolean cube, replacing every positive power of a variable by that variable. Values on the Boolean hypercube remain unchanged, and the resulting multilinear polynomials have degree at most . Their ambient space has a monomial basis consisting of for , with dimension . This proves the general bound, including .
For completeness, obtain the uniform sharpening without dividing by factorials in a finite field. For put and . The functions with are linearly independent. Indeed, a relation gives with , so is supported only on weights in . With boundary weights , this set has a gap of at least : either consecutive allowed weights differ by , or its terminal gap does, since . The alternating sum of over any interval of free coordinates vanishes by its degree. Across that gap only one endpoint level can contribute, forcing to vanish there. Delete that level and repeat across the enlarged gap until is empty. Hence , and independence of the square-free monomials gives the claim. Adjoin these functions to the . Evaluation at each family vector eliminates the coefficients of , since vanishes there; the claim eliminates all remaining coefficients. Counting dimensions yieldsThe case permits at most one member directly. The gap argument is an instance of the modular layer vanishing lemma.
For the final application, enumerate the distinct sets as and let be their characteristic vectors of sets. If , the desired bound is immediate for . Otherwise , because intersects another member in points. At most one member can have size : two distinct -sets cannot have intersection size . The Gram matrix of these vectors isFor real coefficients ,All terms are nonnegative, with . If the expression vanishes, every coefficient corresponding to a set of size greater than is zero. At most one coefficient remains, and the first term forces it to be zero as well. Thus the characteristic vectors of sets are linearly independent in , proving the constant-intersection family boundThis proof explicitly covers the possible member of size exactly ; assuming all diagonal corrections were strictly positive would miss that case. Positivity of is essential: when , the empty set and all singleton sets give members.