Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 14 4 Solution by
Codex 0 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 2009 iii Paper 14 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Identify the vertices of the Boolean hypercube with subsets of , adjacent when their symmetric difference has size one. Write for the closed graph neighbourhood, including itself. In simplicial order on the discrete cube, smaller sets come first, and equal-sized sets are ordered by lexicographic order: the least element of the symmetric difference belongs to the earlier member. Let denote the first vertices. The vertex-isoperimetric inequality in the discrete cube statesSubtracting gives the equivalent assertion for the external vertex boundary.
We first check that is also an initial segment in simplicial order on the discrete cube. Apart from the empty and full cases, consists of complete lower layers and a lexicographic initial segment in its top rank . Its closed graph neighbourhood contains all ranks at most and the upper shadow in rank . This upper shadow is lexicographic initial: an -subset belongs to it precisely when its first -subset in lexicographic order, obtained by deleting its largest element, belongs to . Taking the first elements preserves weak lexicographic order, proving the assertion. This also handles , where consists of ranks zero and one.
We prove the vertex-isoperimetric inequality in the discrete cube by mathematical induction on , with immediate. Fix a coordinate and write for the sections without and with . The two sections of its closed graph neighbourhood areA simplicial section compression replaces by the initial segment of size in the other coordinates. By the preceding observation, both and are initial segments, so their union has size . The mathematical induction hypothesis givesAdding the two section bounds proves that simplicial section compression cannot increase the closed graph neighbourhood.
Apply changing simplicial section compressions until none remains. The sum of the global simplicial order on the discrete cube positions strictly decreases at each step: within a section the order is exactly the restriction of the global order. Thus the procedure terminates at a set family every coordinate section of which is initial. We now classify the possible terminal families for simplicial section compression, rather than assuming this terminal set family must be globally initial.
If , and , then cannot agree in any coordinate, since that coordinate section would have an omitted earlier member and an included later one. Therefore . Let be the first omitted vertex and the last included vertex. If is noninitial, and . Any vertex strictly between them would have to be included, since an omitted paired with would have to equal . But it would also have to be omitted, since an included paired with would have to equal . Thus there is no such : are consecutive complementary vertices. Everything before is included and everything after omitted. Hence is obtained from the initial segment of its size by replacing with its immediate successor .
There are only two forms of this exception. If , consecutive complementary vertices must straddle ranks ; otherwise an intermediate rank or a further vertex in one of their ranks separates them. They are consequentlywith the last -subset and the first -subset. The corresponding initial segment is all ranks at most . For , the omitted remains in through a lower neighbour, and every -subset has at least two -subsets, only one of which was omitted. Thus contains every rank at most , namely . For both singleton closed graph neighbourhoods are the whole .
If , the two complementary vertices must both have rank . The complement map reverses the lexicographic order in that rank, so a consecutive complementary pair must be its central pair. Exactly half the -subsets contain , and all of those precede those missing . Therefore the pair isHere comprises all ranks below and all -subsets containing . For , contains every rank at most , because all lower ranks were retained. Every -subset containing has different -subsets containing , so deletion of the one member removes no vertex of the upper shadow. Consequently . For , the two closed graph neighbourhoods both have size three in . These cases exhaust the exceptions. Since the successive simplicial section compressions never increased the closed graph neighbourhood, this proves the vertex-isoperimetric inequality in the discrete cube.
The same argument gives all integer radii. Write for repetitions of the closed graph neighbourhood. Its application to an initial segment is again initial; the sizes of these initial segments are monotone in the original size. Inducting on therefore gives
For the concentration question, use uniform probability measure on a finite connected graph and normalize its graph distance by its graph diameter. A sequence is a Lévy family of graphs if, for every fixed and , the radius- neighbourhood of every set of measure at least has measure tending to one, uniformly over those sets. One may equivalently require this only for sets of measure at least one half. To see the reverse implication, first the radius- neighbourhood of every positive-density set must eventually have measure greater than one half. Otherwise its complement has measure at least one half, while the radius- neighbourhood of that complement misses the original positive-density set, contradicting the half-measure condition. Apply the half-measure condition once more to the radius- neighbourhood, enlarging it by another , to obtain the full claim. The metric normalization is essential here.
For , the graph diameter is . A uniformly chosen vertex has size with binomial distribution , expectation and variance . Fix and choose so that . By Chebyshev's inequality,For sufficiently large , put . Every initial segment of measure at least contains the complete ranks through . Its radius- graph neighbourhood therefore contains every rank at most . Taking , the all-radius vertex-isoperimetric inequality in the discrete cube gives, uniformly for ,The last Chebyshev's inequality is used only when its denominator has positive square root. These are precisely the radius- neighbourhoods in the normalized graph distance. The discrete cubes form a Lévy family. In fact, taking in the same bound makes the omitted measure for each fixed : a radius that is already suffices.
For fixed , the nearest-neighbour grid has graph distance and graph diameter . Take the slab , whose uniform measure is at least one half. Its integer radius- graph neighbourhood is exactly : changing the first coordinate alone attains the minimum distance to the slab. For and , the omitted proportion tends toThus there is failure of concentration in fixed-dimensional grids, and the fixed-dimensional grids do not form a Lévy family with normalized graph distance.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 14 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
The Erdős-Ko-Rado theorem asserts that, for , every intersecting family satisfiesThe bound is attained by the set family of all -subsets containing one prescribed point. Here lexicographic order means that when the smallest element of their symmetric difference belongs to .
The first members in lexicographic order are exactly those containing . An initial segment longer than contains all of them and also the first member avoiding , namely . There is an -subset containing and disjoint from : choose its other elements from , which has elements. Consequently any longer lexicographic initial segment fails to be an intersecting family. Thus preservation of the intersection property upon replacing a set family by the equally large lexicographic initial segment proves the displayed bound.
Here is a direct UV-compression proof of that preservation statement. For disjoint nonempty sets with and , an eligible member contains and misses ; its proposed image is . The UV-compression moves to only if is not already present. Each eligible pair is either kept as a pair or moved from its later to its earlier member, so this operation preserves cardinality and uniformity and strictly decreases the sum of lexicographic order positions whenever it changes the set family.
The essential intersection-preserving lexicographic UV-compression lemma is that this operation preserves an intersecting family whenever all smaller lexicographically improving UV-compressions already leave that set family unchanged. Suppose instead that the compressed set family has disjoint members. At least one, say , must be newly moved. Both newly moved members would contain , so the other, , is a retained old member. Write for the old preimage. Since , we have and . Old intersectingness forcesIf , then was eligible for the same UV-compression. Since it was retained, was already present. But , contradicting old intersectingness.
Otherwise . Choose with and . This is a smaller improving pair, since . The old member is eligible for its UV-compression. The assumed stability therefore forces to be present already. Yet its portion outside misses , its remaining portion misses , and misses . Thus , the required contradiction. This proves the lemma, including the size-one case, where only the first alternative can arise.
Starting with , repeatedly choose a changing improving UV-compression with the smallest possible . The lemma applies at each step because every smaller improving UV-compression is then unchanged. Thus every intermediate set family is intersecting. The strictly decreasing nonnegative integer sum of lexicographic order positions ensures termination. If the terminal set family were not an initial segment, there would be a missing earlier than a present . Taking and gives equally sized nonempty disjoint sets with , and moves to the missing . That contradicts termination. The terminal set family is therefore exactly the equally large lexicographic initial segment, and it is intersecting. This proves the required lexicographic statement directly, and hence the Erdős-Ko-Rado theorem.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 14 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Write for the th uniform layer of the Boolean cube. For , , its lower shadow is . The Local LYM inequality statesTo prove it, count pairs with , and . Each contributes pairs; each member of the lower shadow contributes at most . Thus , which is exactly the displayed Local LYM inequality. The corresponding upper shadow inequality follows either by taking complements or by counting upward inclusion pairs.
For an antichain , put . The LYM inequality isFor the first proof, set and recursively . Every member of is a subset of an original member of of size at least . Consequently and are disjoint: otherwise one original member would properly contain another, contradicting the antichain condition. The Local LYM inequality now givesIterating down to bounds the desired sum by , proving the LYM inequality.
For the second proof, a permutation determines a maximal chain in a Boolean lattice through the successive initial subsets . A member of size lies on exactly of these maximal chains in a Boolean lattice. An antichain meets each such chain in a partially ordered set at most once. Counting its incidences with the maximal chains in a Boolean lattice therefore yields . Division by is the LYM inequality again.
The Sperner theorem says that an antichain has at most members. Indeed for every , soThe middle uniform layer of the Boolean cube attains the bound. For equality in Sperner theorem, equality throughout forces every member to lie in a layer of maximum size. If , this forces .
If , only ranks and are possible. Let , , and be the upper shadow. The antichain condition gives . The Local LYM inequality for the two equally sized middle layers gives , while forces and .
Consider the inclusion bipartite graph between these two middle layers. It is a -regular graph. Since , all edges incident to must come from ; there are no edges from its complement on the lower side into . This bipartite graph is a connected graph: any two -subsets can be joined by single-element exchanges, and each exchange passes through their common -superset; every upper vertex has a lower neighbour. For it is just one edge. Hence either or is the whole lower layer. We have proved the complete classification:The two possibilities coincide for even ; for the unique maximum antichain is .
Finally enumerate the members of the separating set system as and encode each point by . Separation of the ordered pair means . Applying the hypothesis also to shows that the sets are distinct and pairwise incomparable. They form an antichain in , so the Sperner theorem immediately gives
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 13 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
We take , as is necessary for the assertion. The nonvacuous cases have and . Put andWe prove a lower bound for by transferring small sumset growth through algebraic operations on the scalars. This gives a self-contained polynomial skew-sumset expansion over a prime field proof using the permitted Ruzsa triangle inequality, Ruzsa covering lemma and Plünnecke-Ruzsa inequality.
Since , choose . The bound and the mixed-set Plünnecke-Ruzsa inequality giveIn particular and . Here repeated-set sums such as allow independent choices from each copy.
For a scalar , write , and put for the difference set. The Ruzsa covering lemma gives with . Indeed choose a maximal family of disjoint translates , with ; counting their union bounds the family size, and maximality forces every remaining translate to meet one of them.
For any , the containments and give, after covering each copy of ,For the second bound, specifically , and . The Ruzsa triangle inequality also gives , so . These are the closure bounds for small skew-sumset scalars.
We next prove a growth lemma for the scalar sets. For with , letIf , then is not contained in : otherwise equal cardinality would make invariant under addition of one, which generates the entire prime field. Choose . The map on is injective. Indeed a collision with different second coordinates would express as a ratio of two differences from , while equal second coordinates force equal first coordinates. Clearing the nonzero denominator puts its image insideso the latter set has at least elements. Here is the product set, and denotes three independent product terms minus three others, not multiplication by the scalar three.
If , let count the collisions with all four variables in . Summing over givesThe first term comes from equal second coordinates, which force equal first coordinates. For unequal second coordinates, each quadruple determines exactly one scalar. Some consequently satisfies . The Cauchy-Schwarz inequality on the representation counts givesRepresenting as a ratio from and clearing its denominator embeds a dilate of this sumset in , padding with the same product in the positive and negative sums. We have proved the quadratic growth of a sixfold product difference set estimate
Starting from , define . ChooseFor , the growth lemma implies . To see the constants explicitly, put . Then and . Induction gives , and the chosen makes the exponent at least one.
Every has . If on , the closure bounds show that each product has exponent at most , its negative at most , and a sum of six such terms has exponent at most . Thus, withwe have for every . The integer depends only on .
Now apply the collision count to instead of . Summing over all scalars gives at most . Since , some has collision count at most . The Cauchy-Schwarz inequality therefore givesIt follows thatFor this gives , proving the desired positive exponent for all sufficiently large primes.
For completeness, the same conclusion with a possibly smaller exponent holds for the remaining primes. Choose an integerIf , choose any nonzero . We have . If , all its translates for would coincide. Two distinct such would make invariant under a nonzero translation, forcing , a contradiction. Thus by the definition of the second exponent. Together with the large-prime case this provesPositivity of the parameters cannot be dropped: at , taking prevents any expansion; at , the allowed set prevents expansion of any proper with more than one element. No external sum-product theorem was invoked: the scalar growth and transfer arguments were proved above.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 13 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A Freiman 2-isomorphism between subsets of abelian groups is a bijection such thatBoth directions matter: an injective homomorphism on individual elements may still create new pair-sum relations. More generally a Freiman s-isomorphism preserves equalities of sums of elements in both directions. For a nonempty finite set, its doubling constant is . A Freiman 2-isomorphism preserves this constant, since is a well-defined bijection of the two sumsets.
First let have elements and doubling at most . The permitted Plünnecke-Ruzsa inequality gives . We will obtain the half-size prime cyclic Freiman model for every prime . Choose an auxiliary prime larger than the absolute value of every member of . Such a prime exists: for any integer bound , every prime divisor of exceeds .
Choose uniformly from the nonzero residues modulo . For each nonzero , the residue is uniform among the nonzero residues. PutThere are at most such residues, and therefore the probability that any of the nonzero differences is dilated into is at mostThe first cardinal estimate is an upper bound even if some listed residues coincide; the slightly looser probability bound is convenient. Thus there exists with no such bad difference.
For this , let represent . Split these representatives into the two intervals and . Take from the more populated interval, so . For any four elements of , put . Their common half-interval gives , andIf the original difference is zero, then is a multiple of of absolute value less than , so . If the original difference is nonzero, is nonzero, and it cannot be a multiple of : otherwise its residue belongs to , contrary to the choice of . Therefore preserves pair-sum relations in both directions. It is injective as well, by applying the relation test to with any fixed . HenceThis proves the stated polynomial bound, including the prescribed prime rather than just an unspecified cyclic modulus.
Now let . Finiteness of places it in some finite-dimensional coordinate space, so models exist. Choose a Freiman 2-isomorphism with minimal. The doubling constant of is at most .
If a nonzero did not belong to , projection onto would preserve all pair-sum relations in both directions: a new relation would have original difference , whereas in characteristic two every such difference lies in . Projection is also injective on , since by adding any element of twice. This would give a model in dimension , contradicting minimality. Consequently every nonzero vector belongs to ; zero belongs as well, by adding one element four times. Thus .
Using the Plünnecke-Ruzsa inequality once more givesThis is the minimal binary Freiman models have full fourfold sumset argument. It also covers a singleton, with .
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 13 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Write . We first prove the needed cancellation of quadratic exponential sums, rather than invoke equidistribution without proof. The number is irrational: writing it as a reduced fraction would make its numerator even from , and then its denominator even as well, a contradiction. Thus is irrational for nonzero integers .
Fix and set for , extending it by zero otherwise. For integers , each term appears exactly times in the shifted sum, soFor any complex numbers , nonnegativity of gives . Apply this special Cauchy-Schwarz inequality to the displayed outer sum, and then expand the inner squared modulus. This givesFor fixed and large , each correlation is the geometric serieswhose absolute value is at most , independently of . This follows by multiplying the geometric sum by ; its denominator is nonzero by irrationality. Divide the inequality by and let , keeping fixed. It gives a limit superior at most . Taking arbitrarily large provesThis is the quadratic instance of the Van der Corput inequality for finite scalar sequences, with its proof supplied here.
To turn cancellation into the particular approximation, put and choose an integer . The Fejér kernel is the explicit finite trigonometric polynomialThe expansion follows by counting pairs of indices with difference . Its constant coefficient is one, so the cancellation just proved givesIf , the geometric-series formula givesFor all sufficiently large , the displayed average exceeds . Consequently at least one satisfiesIt is a positive integer, as required. Every auxiliary cancellation and kernel identity used in this existence proof has been derived; a smooth cutoff or an unproved Weyl criterion is unnecessary.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 13 1 i by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact





