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 2019 iii Paper 109 4 Solution by
Codex 0 2026-10-03
A multiset of subsets of is a uniform cover of multiplicity when each coordinate occurs in exactly members. The uniform covers theorem states that every Euclidean body satisfieswhere is the coordinate projection of a Euclidean body onto the coordinates in .
We prove it by induction on . Split the cover into , whose members omit , and , whose members contain . Exactly members lie in . For a last-coordinate value , let be the corresponding slice. Removing from the members of and retaining the members of gives a -uniform cover of . The inductive hypothesis and Fubini's theorem giveApply Hölder's inequality to the factors in the integral. Sincewe obtain , which is the result after taking the th power. The one-dimensional base case is immediate.
The Bollobas--Thomason box theorem states that for every body there is an axis-parallel box such thatAn irreducible uniform cover cannot be decomposed into two smaller uniform covers. There are only finitely many such covers of : encode a cover by its multiplicity vector in and apply the Dickson lemma.
Choose a componentwise minimal positive array satisfyingfor every irreducible -uniform cover , together withThe actual projection volumes are feasible by the uniform covers theorem, and finiteness gives a minimal array. Every uniform cover is a disjoint union of irreducible ones, so its cover inequality also holds for this array.
Minimality implies that, for each coordinate , some tight uniform-cover inequality can be chosen whose cover contains the singleton . Indeed, either such an inequality already blocks decreasing , or a tight product inequality does; in the latter case take a tight cover containing and replace that occurrence of by its singleton coordinates. Let these tight covers be , of multiplicities , and let . Their multiset union is a -uniform cover. Removing one copy of every singleton leaves a -uniform cover, so comparison of its cover inequality with the product of all the tight equalities yieldsThe singleton cover gives the reverse inequality, henceFor any , the one-uniform cover consisting of and the singletons for now gives . The defining product inequality gives the reverse bound. Thus all these quantities are equal. Taking the side lengths of to be proves the theorem.
Finally suppose that the proper body satisfiesThis is equality in the three-dimensional Loomis--Whitney inequality. In its proof, equality must hold in both applications of Cauchy-Schwarz inequality. Their equality conditions force the three projection indicators to factor through one-dimensional measurable sets , and forceup to a set of Lebesgue measure zero; this is Equality in the three-dimensional Loomis--Whitney inequality.
Because is connected, each one-coordinate projection is connected and hence is an interval. Because is a finite union of positive-volume axis-parallel boxes, a proper difference between and the product of those three intervals would contain a positive-volume rectangular cell in a common finite subdivision. That would contradict equality up to measure zero. Consequently the equality is exact and
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 109 3 Solution by
Codex 0 2026-10-03
Write for the closed graph neighbourhood of . Since , minimizing the external vertex boundary at fixed cardinality is equivalent to minimizing the closed neighbourhood. The vertex-isoperimetric inequality in a grid says that, among all -vertex subsets of , the first vertices in the simplicial order on a grid minimize this quantity.
We prove the theorem by mathematical induction on , using the allowed two-dimensional case. Fix a coordinate and write for the section in which that coordinate equals . Replace each by the equally large initial simplicial segment . By induction, . The section formula for a grid neighbourhood givesFor the compressed family, are nested initial segments, so the size of their union is the maximum of their sizes. That maximum is no larger than the size of the corresponding uncompressed union. Summing over proves that coordinate compression in a product of paths does not enlarge the boundary.
Apply these compressions in every coordinate, choosing among boundary-minimizing outcomes one with least coordinate-sum weight. If the result were not an initial simplicial segment, it would contain a later vertex while omitting an earlier one. After cancelling coordinates in which they agree, this gives an inversion in a two-coordinate face. Replacing the occupied portion of that face by the equal-size initial segment in does not increase its neighbourhood by the assumed two-dimensional theorem, while it strictly lowers the weight. This contradiction is the local-to-global lemma for simplicial grid order, and completes the induction.
For the second assertion, list the vertices of in the Gray code orderThe three consecutive edges form a copy of the four-vertex path . Pairing the binary coordinates and applying this identification in each pair realizesas a spanning subgraph of the hypercube graph . For any fixed vertex set, adding graph edges can only enlarge its external vertex boundary. Hence a -set in has boundary at least that of the same vertices in , which by hypothesis is at least . Therefore
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 109 2 Solution by
Codex 0 2026-10-03
The Kruskal-Katona theorem states that if has the unique binomial representationthen its lower shadow obeysAn initial segment of colexicographic order has exactly this shadow.
Here is the UV-compression proof of the Kruskal-Katona theorem. For disjoint equal-size sets , the UV-compression replaces the pattern by when the image is not already in the family. If the family is not an initial colexicographic segment, choose a changing pair with and minimal. Minimality ensures that for every an appropriate smaller compression already fixes the family. The Shadow lemma for UV-compressions then givesMeanwhile the binary weight strictly decreases. Iterating must terminate, and a terminal family is an initial colexicographic segment. Computing that segment's shadow from its binomial representation proves the theorem.
We next classify pairs that decrease the shadow for every uniform family. The answer, including the identity case, isFor the operation is the identity. For , the hypotheses of the Shadow lemma for UV-compressions reduce to stability under the empty compression and therefore hold for every family.
To see failure for larger pairs, relabel freely. If , write and . The familyhas a three-point lower shadow, whereas its compression replaces by and has a four-point lower shadow. If the common size is , takeThe old two shadows overlap once and have size . Compression replaces by ; the two resulting -sets intersect in only , so their lower shadows are disjoint and have size .
For the two specified pairs, the answer is no in both cases, even after assuming the family is left-compressed.
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 109 1 Solution by
Codex 0 2026-10-03
For a uniform set family , the Local LYM inequality isTo prove it, count the incident pairs with , , and . Every contributes exactly pairs, whereas every belongs to at most members of . Thereforewhich is the displayed inequality after using the binomial coefficient identity .
The LYM inequality says that every antichain satisfiesFor the proof from the local inequality, take the lowest occupied level below the middle and replace that level by its upper shadow. The result remains an antichain: any new containment involving a set in the upper shadow would already give a containment involving the member of immediately below it. The dual form of the Local LYM inequality says that this replacement cannot decrease the Lubell mass. Repeating upward below the middle, and similarly replacing high levels by their lower shadows, eventually puts the whole family in one middle level. Its final Lubell mass is at most one, so the original mass is also at most one.
For the maximal chain in a Boolean lattice proof, choose a Uniformly random maximal chain in a Boolean lattice. An -element set lies on it with probability . Because an antichain meets each chain at most once, the expected value of the number of its members on the chain is at most one. By linearity of expectation, that expected value is precisely the displayed sum.
The Sperner theorem follows because for every . If equality holds in the resulting cardinality bound, every member lies on a largest level. For even this is the unique middle level. For odd , the two middle levels have equal size; the regular connected inclusion graph between them and equality in Local LYM inequality force a chosen portion of the lower level to be either empty or the whole level. Hence the maximum antichains are exactly the complete middle level, with either middle level allowed when is odd.
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 108 4 Solution by
Codex 0 2026-10-03
For a finite partition , putThe system is K-mixing when every measurable becomes uniformly asymptotically independent of this remote future:Taking makes , soThus K-mixing implies mixing.
The tail sigma-algebra of a measurable partition isBy the reverse martingale convergence theorem,in . The uniform independence in the definition of K-mixing is equivalent to the limit being the constant for every . This holds exactly when every -measurable set has measure zero or one. Hence the system is K-mixing if and only if every finite partition has trivial tail sigma-algebra.
Let . Complements preserve the binary partition. If , then is coarser than , so subadditivity gives zero entropy rate. Thus is an algebra. For , let . The entropy metric continuity boundtends to zero because . Hence , proving that is a sigma-algebra: the Pinsker sigma-algebra.
If belongs modulo null sets to for a finite , remote-future approximations make the entropy rate of zero. Conversely, if , the conditional-entropy formula for entropy rate givesThus is measurable modulo null sets from its strict future. Iterating this fact makes it measurable from every remote future, so modulo null sets. ThereforeThis is the Tail characterization of the Pinsker sigma-algebra.
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 108 3 Solution by
Codex 0 2026-10-03
For a finite measurable partition ,Its conditional entropy of finite measurable partitions relative to isThe concavity of , equivalently conditioning reduces entropy, gives
SetThe chain rule and invariance give , so is a subadditive sequence. ThereforeThe Kolmogorov-Sinai entropy is over finite partitions.
Taking immediately shows that the infimum over arbitrary finite is at most . For the reverse inequality, apply Shearer's inequality to translates of a fixed finite inside a long interval. Every interior coordinate is covered times, while only boundary coordinates are lost. Subadditivity bounds the boundary contribution; division by the interval length and passage to the limit giveTaking the infimum proves
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 108 2 Solution by
Codex 0 2026-10-03
The statement means convergence in density of a sequence: for every , the proportion of with tends to zero. The statement means Cesaro convergence of a sequence, .
Suppose . Splitting into the indices where and its complement givesThus density convergence implies Cesaro convergence of the absolute deviations to zero. Conversely, the Markov inequality givesproving the reverse implication.
The product characterization of weak mixing says that if is weakly mixing, then is ergodic exactly when is ergodic; in particular, ergodicity of characterizes weak mixing.
Suppose . Unitarity of the Koopman operator gives . Weak mixing implies ergodicity, so is almost everywhere constant. On the product,is invariant under . Since the square is ergodic, is constant, which forces to be constant almost everywhere. Thus there are no nonconstant Koopman eigenfunctions.
Finally use the density-one correlation characterization of a weakly mixing measure-preserving transformation. For each positive-measure pair , the integers for which form a density-one set after discarding finitely many terms; the corresponding sets for and therefore intersect, proving simultaneous hitting. Conversely, the simultaneous-hitting property is precisely the simultaneous hitting characterization of weak mixing, so it implies weak mixing.
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 108 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Assume first that for every . For the measure-preserving transformation property givesThus the sets , , are pairwise disjoint and all have measure , impossible in a probability space. Hence
The Poincaré recurrence theorem states that almost every returns to infinitely often. LetThe sets are pairwise disjoint: if belonged to the th and th inverse images with , then would return to after steps. Invariance and finiteness therefore give . A point of with only finitely many returns belongs, after its last return, to some . The countable union of these null sets is null, proving the theorem.
Now let have . Put and let be the bilateral shift. Choose intervals with and . A weak-star limit ofexists on the compact shift space. Boundary terms show that the limit is -invariant. For the cylinder ,The stated polynomial recurrence theorem supplies with . Hence that cylinder intersection meets the orbit closure of ; because it is open, some shift lies in it. Therefore . Orient these two integers according to the sign of to obtainThis is the Furstenberg correspondence principle.
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





