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 2008 iii Paper 17 1 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Here is the quadratic-form criterion for an Anosov flow. Assume that the generator is nowhere zero and form the transverse vector bundleSince , the derivative induces a linear cocycle . Suppose there is a continuous nondegenerate indefinite quadratic form on each fibre, with constant signature of a quadratic form, such that is differentiable andis continuous and positive definite on every transverse fibre. Then is an Anosov flow. An equivalent way to specify is a quadratic form on whose radical is exactly and whose induced form and derivative satisfy these conditions on the quotient.
On the closed manifold, compactness makes the positivity uniform: for some , . Thus the positive and negative cones are strictly separated by the linearized flow, yielding uniform unstable and stable transverse subbundles and their invariant lifts. The positive index is the unstable dimension and the negative index is the stable dimension. Strict positivity must be imposed transversely; imposing it on the flow direction would be impossible because that direction is carried into itself.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 17 1 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Let be the generator of the smooth flow. The Anosov flow property requires to be nowhere zero and a continuous splitting of the tangent bundlewhich is invariant under . There must be constants and such that, for every , every and every vector in the indicated fibre,The first inequality defines the Anosov stable bundle; the second defines the Anosov unstable bundle and is equivalent to uniform forward expansion there. The remaining one-dimensional direction is the flow direction. The norm can come from any Riemannian metric, since norms are uniformly equivalent on a closed manifold. The essential requirements are a continuous invariant splitting and estimates uniform in both the base point and time, rather than separate exponential rates along individual orbits.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 16 3 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Let and . In the norm convention, the quadratic uniformity of a set meansIf uniformity is parametrized instead by , replace the parameter below by . We prove the genuine-progression conclusion by placing nonnegative weights on a region where wrapping and repeated entries are impossible.
First suppose . Put , , , and let be the normalized convolution on a finite group. Define the weighted countBoth weights are nonnegative. Their supports require and in the ordinary representatives. In particular and . Every contributing arithmetic progression is therefore a set of four distinct integers in , with no modular wrap.
The averages of both weights are . The convolution theorem on a finite group and the Parseval identity on a finite group giveTranslation multiplies coefficients by phases, so has the same Fourier coefficient sum. Telescoping the product of the four indicators around produces four error terms, each with one factor and all other factors bounded by one.
To bound a weighted error, expand both weights in their finite Fourier series. For frequencies , the extra character is . Write it asand absorb these two characters into the functions at slopes zero and one. Even if the balanced factor is one of those functions, its norm remains at most by the character invariance proved in part (i). The cyclic bound of part (ii), with , therefore bounds each unweighted Fourier term by . Summing absolute coefficients costs at most . ConsequentlySince and , this is positive whenever . A positive count supplies the required genuine arithmetic progression. This is the argument that triangular weights count genuine four-term progressions; it avoids losing powers of by cutting off a sharp interval.
For completeness, treat . If is a proper nonempty subset, then . The norm bound from part (i) givesChoose below this bound as well. Then quadratic uniformity forces , which contains . Thus, for every , a sufficient threshold isThe restriction is necessary: for , the full group has balanced subset indicator zero and is quadratically uniform for every positive parameter, but no subset has four elements. The printed conclusion needs this elementary size qualification.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 16 3 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Index the functions as and write . We first control . Change variables to , average over , and apply Cauchy-Schwarz in , discarding the bounded factor . Expand the squared inner average with the second copy of written , then put . This yieldsThe right side is real and nonnegative because it arose as an average of squared absolute values. Next use and apply Cauchy-Schwarz in , discarding the bounded derivative. Expanding with a displacement in givesFinally use and Cauchy-Schwarz in , discarding the bounded double derivative. Expansion with displacement givesAll these changes of variables are bijections without any division in .
Put , where is the torsion subgroup killed by an integer . The variables and are uniform on and , whose indices are . Since the last squared integrand is nonnegative, its restricted average is at most times the unrestricted average over the two increments. By part (i), that unrestricted average is . Hence .
To control , apply the same three eliminations in the order of slopes . The surviving has increments . The last increment is uniform, and only the first is restricted to , so the resulting bound is . Reversing the arithmetic progression by treats and respectively. This proves the four-term progression bound with torsion factors:For a fixed finite group, this positive constant tends to zero with . In , , so . If multiplication by two and three are bijective, the sharper holds.
A dependence on torsion is necessary if a bound uniform over all finite abelian groups is intended. In , choose independent random signs . A cube with eight distinct vertices has sign product of expectation zero. Each of the twenty-eight possible collisions has probability , so the expectation of is at most . Some sign function therefore has norm at most . But with factors , every arithmetic progression is and its product is . Thus unbounded torsion obstructs uniform control of four-term progressions. The stated fixed-group bound, and the uniform cyclic-group bound needed in part (iii), are unaffected.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 16 3 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
The expectations use normalized counting measure on a finite abelian group . This is the finite-group convention implicit in the averaging notation; an arbitrary infinite group has no normalized counting probability measure on all its points. For , define , and let denote complex conjugation. The Gowers U3 norm isAveraging first over gives the Derivative identity for the Gowers U3 normIndeed, if , the average over is . The eighth root is consequently well-defined. Homogeneity follows because the cube has four unconjugated and four conjugated factors, so . If the norm is zero, every squared term in the finite average vanishes. Taking gives , so pointwise. This proves positive definiteness.
For the triangle inequality, we prove the needed Gowers-Cauchy-Schwarz inequality. For eight functions on a product of finite sets , form the box norm multilinear averageFix a coordinate . After averaging its two variables separately, this is , where uses all vertices with and those with , with the remaining parity conjugations. The Cauchy-Schwarz inequality giveswhere replaces the function at each vertex by the original function with its th index set to . Each right-hand average is a squared absolute value averaged over the other coordinates, hence nonnegative. Apply this operation successively for , to every resulting factor. The eight final families each use one original at all vertices. Taking roots gives the box Cauchy-Schwarz inequalityNow take and . With and , these independent variables induce uniform : each such tuple has exactly preimages. Therefore each box norm is the corresponding norm, and the mixed cube obeysExpand the eight factors in the cube expression for . Its mixed terms are bounded by this inequality, and their bounds sum to . Thus , completing the norm proof.
Two consequences will be useful below. Multiplication by a character of a finite abelian group leaves the norm unchanged, because the alternating character product around a three-dimensional cube equals one. Alsowhere the last inequality uses the term and . Hence .
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 16 2 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Let , , and use normalized averages on . Write and define the normalized convolution on a finite group by . With ,These identities follow by expanding the convolution and using character orthogonality. Also is a normalized nonnegative count of representations ; thus implies .
Take . The Parseval identity on a finite group givesFor in the Bohr set in phase-distance convention , all large-frequency terms have real part at least half their magnitude. Since is real,Thus . This proves the cyclic Bogolyubov lemma needed here, rather than citing it.
We now find an arithmetic progression in a cyclic Bohr set. Put . If , the whole group lies in and the result is immediate. Otherwise set . When , place the vectors , , into the boxes of side in the -dimensional unit cube. Two occupy the same box, giving with for every . The arithmetic progressionlies in . Its terms are distinct: the order of in is , greater than its number of steps. Its length is at least .
Let . Since , the exponent is at least . If , then and the singleton already exceeds the required lower bound. This also covers . Therefore one may takeThe arithmetic progression here is a set of distinct elements in the cyclic group; this part does not impose the additional integer nonwrapping condition used in Question 3.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 16 2 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
We first prove the needed Petridis minimal-growth lemma. For finite nonempty sets , choose a nonempty minimizing . Thus for every , including the empty set. For any finite , defineThe sets partition . If , then for some , and therefore . The newly contributed portion of consequently has size at mostSum over to obtain . Apply this successively with to get .
Use . The hypothesis implies , so . We also prove the Ruzsa triangle inequality: for finite nonempty ,For each , fix with . The map is injective: summing its coordinates recovers , and then its first coordinate recovers . This proves the inequality.
Apply it with and . Both right-hand factors have cardinality , givingThus . This is the required case of the Plünnecke-Ruzsa inequality, proved here using the minimal-growth argument and the explicit injection. If is empty the conclusion holds directly.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 16 2 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Assume ; the empty case is immediate. Write . The additive energy in the hypothesis is : rearranging gives . Since , the energy is at most , so the substantive range is .
Let . The contribution of the other differences to the energy is at most . ConsequentlyMake a bipartite graph with two copies of , joining a left vertex to a right vertex when . Put . This graph has at least edges, and .
We prove the needed dense-graph selection rather than quote the Balog-Szemerédi-Gowers theorem. A pair of left vertices is bad if it has fewer than common right neighbours, where . Choose a right vertex uniformly, let , and let be the number of ordered bad pairs in . Averaging the degrees gives . Every bad pair lies in fewer than of these neighbourhoods, so . Therefore some satisfiesFor this neighbourhood, and . Delete vertices having more than bad partners in . At most half are deleted, so the remaining set has .
For any , at least vertices are good partners of both. Each such has at least common neighbours with and at least with . Independently choosing those neighbours gives at leastfour-edge walks . Repeated vertices cause no difficulty. This proves the four-step path lemma for a dense bipartite graph in the required form.
The labels of such a walk are , , , , all in , andFor a fixed pair , its label tuple uniquely recovers , , and , so distinct walks have distinct label tuples. Choose one pair representing each element of the difference set . Tuples belonging to different differences are disjoint because their alternating sum determines that difference. HenceWe have obtained explicit constants for the small-difference-set form of the Balog-Szemerédi-Gowers theorem:
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 4 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Use the same random variables for the edge cover of . For a fixed color vector, any two compatible candidate vertices cannot be adjacent: an edge in a covering graph would force different colors at that coordinate. Thus the compatible candidates form an independent set and there are at most of them. By the maximum entropy on a finite alphabet, .
Consequently the mutual information is at least , while the marginal and conditional-entropy bounds from part (i) make it at most . The entropy weight of a graph cover bound follows:
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 4 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For each , choose a proper coloring minimizing its color information entropy , so its coloring entropy weight is . A minimizing coloring exists: up to relabeling there are only finitely many partitions of its finite vertex set into color classes. Use independent dummy colors with the same marginal law as before. The marginal and conditional-entropy calculations in part (i) remain valid for any number of colors. Also any pair of vertices is joined in some covering graph and hence receives different forced colors there, so the full color vector still determines . Thus
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 4 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Choose uniformly among the vertices. For each covering graph use a proper binary coloring, and fill the color of an absent vertex with an independent random color having the same law as the color of a uniform vertex of that graph, as in the question's construction. Write for that color information entropy, so . The marginal distribution of is precisely this color law, and the variables are conditionally independent given : present colors are deterministic and absent colors use independent dummy draws. ThereforeAny two distinct vertices are joined in some and have different forced colors there. They cannot both be compatible with the same observed color vector, so . The mutual information identity now givesand hence .
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 3 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Take for any , ordering one part before the other. Every degree is ; the first vertices have , the last have . The bound is therefore . An independent set lies entirely in one part, giving possibilities after subtracting the twice-counted empty set. Hence equality holds. Disjoint unions of such ordered components give further equality examples.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 3 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Choose an independent set uniformly and let indicate whether it contains vertex . Then . Put and . Form a multiset containing every nonempty and copies of singleton . Each coordinate occurs exactly times: in later-neighbor sets and in singleton copies.
For a set in this multiset, weight it by . These weights form a fractional cover, since each of the occurrences of has weight at least . Apply the upper Madiman-Tetali inequality. Since every precedes , one has ; enlarging that set's weight to and removing conditioning only enlarges its nonnegative contribution. For singleton terms retain the useful conditioning on . ThusFor , let . Every nonzero neighbor assignment forces , while the all-zero assignment allows at most two values. The maximum entropy on a finite alphabet givesThe last inequality is the binary entropy maximization formula, or the log-sum inequality, with group sizes and . If the whole term is zero, also agreeing with the formula. Exponentiating proves the degree-ordered independent-set entropy bound
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 3 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
The Balister-Bollobas inequality says that if is the coordinate multiplicity in a multiset , and , then . More generally, each union-intersection compression decreases the entropy sum, by entropy submodularity.
For an exact -cover define and . Compressing the family of gives the nested family of all together with full sets. Rearranging the resulting bound gives the upper Madiman-Tetali inequality. Conversely, compressing the family of all together with full sets gives the nested family of , yielding the lower bound. In conditional-entropy notation these areThe coordinate multiplicities agree in each compression, because is an exact -cover. An equivalent proof expands the chain rule for information entropy contributions and uses conditioning reduces entropy. It also gives the upper inequality for arbitrary fractional covers and the lower inequality for fractional packings.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 2 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Translate each two-element set by its smaller element to write with . Translation does not affect any sumset cardinality. The pair-sum hypothesis forces the to be distinct, since equal values would give only three pair sums. Relabel so .
The distinct-positive-integer subset-sum lower bound has a short inductive proof. Suppose the first values have sum , their largest subset sum. Adding creates the distinct sums and for . They are all above , since , and hence are all new. Starting with one sum for no elements and adding new sums givesEquality is attained by . Their subset sums fill every integer from zero to , by induction on , and each pair of distinct positive values has four different pair sums. Thus the bound is best possible for every .
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 2 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Use the lexicographic embedding of a sumset: choose the least tuple representing each distinct sum, and let be the set of those tuples. Then . If two projections onto had the same partial sum but different tuples, replacing the larger projected tuple by the smaller one inside its full representative would preserve that full sum and improve its lexicographic order. This is impossible. Thus the summation map is injective on the projection , giving .
Replace every integer tuple of by the closed unit cube centered there. Their interiors are disjoint, and each coordinate projection is a union of unit cubes indexed by , so the resulting body has volume and projected volume . Apply the box theorem to obtainThe empty-set case uses and the empty product one.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 2 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
The uniform cover inequality states that for a positive-volume body and a multiset in which each coordinate occurs exactly times, , where is its coordinate projection and volumes use the corresponding dimensions.
To deduce the box theorem, maximize subject to for every nonempty . This linear program is feasible and bounded above by the full-set constraint. Its dual minimizes over nonnegative weights with . For rational weights, clearing denominators gives an exact uniform cover, so the uniform cover inequality bounds that dual objective below by . The same holds for all feasible weights by density of rational points in the rational constraint polyhedron. Strong duality makes the primal optimum at least , while the full-set constraint makes it at most that value. An optimal solution therefore gives withThe axis-aligned box with these side lengths has the required volume and projection volumes.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 1 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Put . The assertion is trivial when . Otherwise suppose it fails and set , , , , and , with natural logarithms. For large these parameters lie in their required ranges. The high-level Fourier weight isFor , let . The logarithm of this expression is a convex function of real , so its maximum on is at an endpoint. Also , since . Hence is bounded. The stronger inequality in part (ii) givesDivide by . Because and , the factor is at most one. The remaining factor is . Thus the low-level weight is uniformly in . Adding both parts contradicts for sufficiently large . This proves the squared-influence logarithmic lower bound
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 1 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
The Holder inequality gives . Substitute this into the hypercontractive weighted influence bound and multiply by to obtainas required. The version with is slightly stronger and will also be useful below.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 1 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Use the uniform probability measure on the Boolean hypercube. In the Fourier-Walsh transform convention , write with . For the indicator , Parseval's identity givesThe flip-probability influence satisfies , and summing gives .
For , Beckner's inequality says . Apply it to the discrete derivative of a Boolean function in coordinate , viewed on the other coordinates. Its nonzero magnitude is and occurs with probability , soSumming over gives the hypercontractive weighted influence bound
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





