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 2013 iii Paper 13 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
A ring homomorphism is understood to preserve . Start with . Its map on spectra of rings isContraction gives a prime ideal, and . Thus is continuous for the Zariski topology. On each principal open subscheme, the structure sheaf map is the ring homomorphismThese maps commute with restrictions, so they define a sheaf morphism . At , with , its stalk map is . The inverse image of the maximal ideal is , so this is a local homomorphism. We have constructed a morphism of locally ringed spaces.
Conversely, let be a morphism of locally ringed spaces. Its map on global sections gives , using and . Fix and put . Compatibility with the stalk maps and the local homomorphism property giveConsequently , so the underlying map is forced. On , the sheaf morphism is forced as well: it extends and sends to a unit, hence agrees with the displayed map by the universal property of localization. The principal open subschemes form a basis, so the entire sheaf morphism is determined. Taking global sections of the construction recovers . The two constructions are inverse, proving the affine-target adjunction for schemes in the affine-source case:
To describe the real affine plane scheme points, write . It is a unique factorization domain of Krull dimension two. Its points are exactly the following prime ideals:
- , the generic point of the whole affine plane.
- for each nonconstant irreducible polynomial , taken up to multiplication by a nonzero real constant. These are the height-one points, each the generic point of the integral scheme .
- The maximal ideals, or closed points. By the Zariski lemma, their residue fields are finite algebraic extensions of . Because is a real closed field, those fields are or . The first type is with . The second type is the kernel of evaluation at a nonreal pair ; the pairs and give the same maximal ideal, and these are the only repetitions.
For completeness, any height-one prime ideal contains an irreducible polynomial ; since is already a height-one prime ideal, it must equal . Every remaining nonzero prime ideal has height two and is maximal, by Krull dimension. For a nonreal pair, evaluation generates all of over , so its kernel is maximal. Conversely, each residue field isomorphic to has exactly the two conjugate real-algebra embeddings into , proving the assertion about repetitions.
This describes the topology too: consists of the prime ideals containing , and the closure of a point is . In particular, the closure of is the whole affine plane, while the closure of contains precisely the closed points on , together with itself. The spectrum is much larger than the set . For example, is a height-one point although its curve has no real points. Its structure sheaf has and stalk at .
The induced morphism of schemesis contraction of prime ideals, with the structure sheaf maps given above. On closed points, it sends to the kernel of real-polynomial evaluation at . A real closed point has one complex point above it; a nonreal closed point has two, interchanged by complex conjugation. The source generic point maps to the target generic point. The source height-one points are generated by irreducible complex polynomials . Their contractions are height-one prime ideals , and is a factor of over . An irreducible real either stays irreducible over or splits into two distinct conjugate irreducible factors. Indeed, complex conjugation acts transitively on its distinct factors, or a proper orbit product would give a real factor of ; every orbit has size at most two. Repeated factors are excluded by separability in characteristic zero. Thus one or two height-one points lie above .
The complexification fibres of a real scheme give a uniform description of all scheme-theoretic fibres, including the nonclosed points, is especially useful. The extension of coordinate rings isa free -module with basis . At , with residue field , the scheme-theoretic fibre isIf is a square in , the Chinese remainder theorem gives , hence two points. Otherwise it is a quadratic field extension, hence one point. The polynomial has no repeated root in characteristic zero, so all these scheme-theoretic fibres are reduced schemes. This also proves surjectivity. Conjugation acts on each two-point fibre by exchanging its points and fixes each one-point fibre. As a finite morphism, is closed, so its underlying topological space is the quotient by complex conjugation. The fibre formula explains why a real closed point gives one complex point, whereas the generic point gives a single point with residue field .
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 12 5 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Expose the independent coordinates one at a time and define the Doob exposure martingaleFor a fixed exposed prefix, couple the future coordinates identically under two choices of . The coordinate-change hypothesis bounds the difference of the resulting conditional expectations by . Thus the increment has conditional mean zero and lies in a conditional interval of length at most . This range bound, rather than merely , gives the sharp constant in the McDiarmid inequality.
Here is a proof of the needed Hoeffding lemma. For a mean-zero random variable in an interval of length , let . Its second derivative is the variance under the exponentially tilted distribution. A random variable in has variance at most : the inequality gives . Hence , and imply , for either sign of .
Apply this conditionally to each increment and iterate the conditional expectation:For , Markov's inequality bounds the upper tail by . Taking and then applying the same argument to givesAt the bound is immediate. If all vanish, is constant on the product support and the positive tails are zero, so that degenerate case is handled directly.
For a binomial random graph, let coordinate be the entire vector of edges from vertex to vertices of smaller label. The coordinates are independent finite probability spaces. Changing coordinate changes only edges incident to that one vertex. Deleting the vertex gives the same graph under both outcomes, and each outcome's chromatic number is either that graph's chromatic number or one more. Thus the coordinate range is at most one. Taking all and proves vertex exposure for chromatic number:Using individual edges as coordinates would give a weaker scale; grouping the incident edges is what yields the required bound.
For the expectation asymptotic, take fixed , put , and write . We outline both bounds and the step that turns probability estimates into an expectation estimate. For each fixed , the expected number of independent sets of size isIts logarithm is . Thus Markov's inequality gives with probability tending to one, and yields the corresponding lower bound on its expectation.
For the upper bound, set and , with . The key uniform fact is that every vertex subset of size at least contains an independent -set with probability tending to one. For a fixed subset of size , let count its independent -sets and let . The normalized dependency sum in Janson inequality is bounded byThe term is . The remaining overlap terms give the same order or less: use for large , and split the sum at . For the lower half the terms beyond decrease at the initial endpoint and are exponentially small at the other endpoint; for the upper half, makes every endpoint exponent negative of order . Also is exponentially small on that scale. The exponential form of Janson inequality therefore gives, uniformly for ,for a positive constant depending only on . A union bound over at most subsets succeeds, because is of order . This is independent sets in every large subset of a dense random graph.
On that event, repeatedly remove an independent -set and assign it one new colour until fewer than vertices remain; colour the remainder individually. This gives . The failure probability is exponentially small compared with , and always , so the failure event contributes negligibly to the expectation. Combining the upper and lower bounds and then letting provesThis is the chromatic number of a binomial random graph asymptotic. The slash in the printed expression must be read with as the denominator; a multiplicative reading would eventually exceed . At the endpoint probabilities and , the chromatic numbers are respectively one and for , so this logarithmic formula is intended for .
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 12 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
In this enumeration problem, monotone means subgraph-closed graph property: both deleting vertices and deleting edges preserve membership. This is a decreasing convention, rather than the increasing-edge convention often used for random-graph thresholds. Assume first that the property is proper and has graphs of arbitrarily large orders. These are the usual nondegenerate hypotheses for the formula.
Put . Every graph of chromatic number at most belongs to . In particular, all subgraphs of a fixed balanced Turán graph belong. Choosing each of its edges independently as present or absent givesFor the upper bound, fix with . Every member of is -free, by closure under subgraphs.
We use the following standard regularity consequences. For every sufficiently small regularity error , large minimum cluster count , and fixed positive density cutoff , the Szemerédi regularity lemma gives an equitable partition into clusters and an exceptional set of at most vertices, with at most irregular pairs. The graph embedding lemma for regular pairs says that a fixed graph with a prescribed proper colouring embeds into the corresponding clusters if all its required cross pairs are regular with density at least , provided is sufficiently small relative to and the graph. Hence the reduced graph of a regularity partition, joining regular pairs of density at least , is -free: such a clique would embed .
By the Turan theorem, this reduced graph has at most edges. On its dense pairs allow arbitrary choices of original edges, giving at most free binary choices. All edges within clusters, touching the exceptional set, or lying in irregular pairs contribute further choices. On each remaining pair there are at most times its number of possible edges. The elementary binary entropy estimatebounds the total sparse-pair contribution by . The partition and pair classifications have at most descriptions, whose logarithm is since is fixed. Choose large, then small, then sufficiently small; their total error can be made arbitrarily small. This provesIt is the enumeration of subgraph-closed graph properties.
For the hereditary extension, a hereditary graph property is closed under induced subgraphs. Define the clique-independent partition class , for , to consist of graphs partitionable into possibly empty classes, exactly designated as cliques and the other designated as independent sets; cross edges are unrestricted. Thus is the total number of classes. The colouring number of a hereditary graph property isUse value zero if this set is empty, and infinity for the class of all graphs.
for . The lower bound follows from the definition. For the upper bound, fix any and a balanced partition of a large -vertex set into classes with clique classes. Independent choices of cross edges give distinct graphs in . On the other hand, all graphs in can be described by at most partitions, each with at most unrestricted cross pairs. The former count is strictly larger for large , so is not contained in for any . A contained class with even more parts would contain one of these -part classes by making unused parts empty, so it is also impossible.
The main changes for the hereditary graph enumeration theorem are as follows. The lower bound now uses a contained class : within-class edges are fixed as complete or empty, and the balanced cross pairs still give free edge choices. For the upper bound, since no is wholly contained in , choose one forbidden induced graph for each .
Use the standard induced regularity template lemma: for a fixed finite forbidden induced family and any error tolerance, a regularity refinement gives bounded-size templates with internal clique/independent types and cross pairs classified as sparse, almost complete, or intermediate. A clique of intermediate pairs on classes realizes every fixed induced pattern consistent with the internal types of those classes. This induced embedding conclusion uses a Ramsey refinement within clusters and regularity for both edges and nonedges; the total exceptional-pair cost can be made arbitrarily small. Applied to the , a clique on intermediate classes would realize the forbidden whose number of clique types is . Thus the graph of intermediate pairs is -free. Only intermediate pairs contribute unrestricted binary choices; sparse pairs and the missing edges in almost-complete pairs each have the same entropy bound as before. The Turan theorem and the earlier counting argument now giveThis formula assumes . For the universal property the count is exactly ; a hereditary property of bounded order has and has no graphs on sufficiently large vertex sets, so the displayed expression with is not applicable.
For a proper subgraph-closed graph property, any contained must have : if , it contains arbitrarily large complete graphs, and closure under subgraphs would force every graph into the property. Consequently its colouring number is exactly one less than the least chromatic number of an excluded graph. The excluded family of an intersection is the union of the two excluded families, whose minimum chromatic number is the smaller of their minima. Therefore for subgraph-closed properties, with the universal case treated by .
For hereditary properties take and , both of colouring number two. A graph in their intersection is both bipartite and a union of two cliques. A clique in a bipartite graph has at most two vertices; hence every such graph has at most four vertices. The intersection contains no complete clique-independent class on arbitrarily large orders, so . This also demonstrates why the bounded-order exception to the enumeration formula is necessary.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 12 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
We prove edit-distance stability for clique-free graphs by induction on , using the symmetric difference of edge sets as the distance. For , a -free graph is edgeless, and there is nothing to change. For , choose a vertex of maximum degree , let be its neighbourhood and put . Then is -free. WriteBoth deficits are nonnegative by the Turan theorem. Since every vertex of has degree at most ,The complete -partite graph formed from an -partite Turán graph on and the new class has at most edges. Thus , and direct subtraction givesBy induction, edit into a complete -partite graph using at most changes. Delete the edges inside , and add the missing edges between and . The resulting graph is complete -partite on the same vertex set, andwhere the inequality uses . The required edit distance is at most . Empty partition classes are allowed; a sufficiently dense nondegenerate case has the usual full complement of classes.
For the odd-cycle conclusion, use two standard consequences of the Szemerédi regularity lemma, stated explicitly. The triangle removal lemma says that for every , some ensures that a graph with at most triangles in a graph can be made triangle-free by deleting at most edges, for all sufficiently large . Also, for each fixed odd length and each , there is such that a graph with at least triangles in a graph contains at least copies of .
For clarity, the latter odd-cycle copies from positive triangle density consequence follows by applying regularity with error small relative to , removing exceptional, irregular and very sparse pairs, and retaining a triangle in a graph among the remaining regular dense pairs. The graph embedding lemma for regular pairs counts a positive constant times embeddings of any fixed graph properly three-coloured into those three clusters, including . Dividing by the fixed number of descriptions of a cycle gives the same conclusion for unlabelled copies.
Apply triangle in a graph removal with , and take the resulting . A -free graph cannot have triangles in a graph for large , by the preceding consequence. Delete at most edges to obtain a triangle-free . With ,Apply the proved stability result with . The resulting complete bipartite graph satisfiesChoose also large enough that . Then the distance is at most .
For the unheaded continuation, use the same and its associated , and set . Having at most cycles rules out triangles in a graph just as before. The identical deletion and stability calculation applies. A sufficiently small gives the same bound.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 12 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
For a fixed uniform hypergraph with vertices, uniformity , and at least one edge, define its Turán density bywhere is the maximum edge count of an -free hypergraph. The limit exists: averaging the edge count over all -vertex subsets of an extremal -vertex hypergraph, with , shows that the displayed normalized extremal numbers are nonincreasing. Thus their limit is their infimum.
For hypergraph supersaturation by sampling, choose so that . The expected edge count in a uniform -vertex subset of is at least . A subset containing no copy of has at most edges, while any subset has at most . Hence at least an fraction of the subsets contain . Every particular copy of lies in exactly such subsets, so their number is at leastfor . TakeFor , the requested integer lower bound is zero; for , the calculation proves it. This positive depends only on and . If the density hypothesis is impossible there is nothing to prove. For an edgeless , every -set is already a copy and the conclusion follows directly.
For the edge-triangle objective, let be the open neighbourhood of and define its local scoreIt counts the contribution to of edges and triangles in a graph containing . If are nonadjacent, making a false twin of changes the objective by , since no edge or triangle in a graph uses both. More generally, partition vertices into false-twin classes, meaning equal open neighbourhoods. If distinct classes have no edges between them, making every vertex of a twin of a representative of changes the objective by . Choose the direction with nonnegative change.
Among graphs maximizing the objective, choose one maximizing the sum of squared false-twin class sizes. The operation cannot split any old false-twin class and merges , so it would strictly increase that secondary quantity. Therefore no two distinct classes can be nonadjacent. An objective maximizer is a complete multipartite graph. This edge-triangle symmetrization works for every real , with no assumption on its sign.
For positive part sizes , the correct multipartite formula isThe first sum in the printed intermediate formula has inconsistent indices; the edge count is the pairwise-product sum above. Fix two part sizes with sum and let be the sum of all other sizes. All terms varying with the pair have the formChoose a maximizing partition with the fewest nonempty parts. If , merging those two parts cannot decrease and reduces the number of parts, a contradiction. Therefore this coefficient is positive for every pair. If two integer sizes differ by at least two, moving one vertex from the larger to the smaller increases their product and hence , again a contradiction. All sizes differ by at most one, so a maximizer is a Turan graph. This is balancing a multipartite edge-triangle objective.
Next maximize the same polynomial on the compact simplex of nonnegative real sizes summing to , starting with at least two possible parts. Choose a maximizer with the smallest positive support. The merging argument still applies, and now varying two positive unequal sizes towards equality improves the product. Thus every positive size is for some integer . A two-part choice has value when , so . The optimum is attained at rational sizes, and thereforeOne may take the initial simplex to have coordinates, so it includes every multipartite graph obtained above; zero coordinates are discarded.
Set . Dividing the right side by givesbecause is an integer at least two. Rearranging provesEquality in the continuous calculation occurs at two or three equal parts, explaining the triangle support line between bipartite and tripartite Turan graphs.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 12 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Write for the balanced graph blow-up of a complete graph, with classes of size ; containment here is as a subgraph, not necessarily an induced subgraph. The logarithmic form of the Erdős-Stone theorem is: for fixed and , there are and such thatThus the guaranteed balanced part size is at least , with independent of . We prove the logarithmic Erdős-Stone theorem by a density-to-cliques step and a constructive dense clique family blow-up lemma.
First choose a fixed large enough that , where is the edge count of the Turán graph. A uniformly chosen -vertex subset has expected edge count at least . If its induced graph contains no , the Turan theorem bounds that count by . Since the count is always at most , the probability that the subset contains an -clique is at least . Double counting the incidences between such subsets and their cliques gives, for ,for a fixed and all sufficiently large . Here . This is clique supersaturation by sampling.
We now prove the needed dense clique family blow-up lemma, with the following stronger induction invariant. Given any family of at least distinct -cliques, there is a complete -partite subgraph with each class of size , containing that many pairwise vertex-disjoint transversal members of , each with one vertex in every class. Extra edges within its classes can be ignored. We may suppose . For , any singletons suffice, and we may take once is large.
For , put . Repeatedly delete every member of the current family containing an -clique whose number of extensions is at most . Each such face is processed at most once, and there are at most possible faces. At most members are deleted. The remaining family has size at least , and every face that remains has more than extensions. Its family of -faces has size at least , since each face is in at most members.
Apply the induction hypothesis to these faces. It gives a complete -partite subgraph with vertices in each class and a matching of transversal -faces from the family. Form a bipartite graph whose left vertices are the and whose right vertices are the original vertices; join to when . Every left degree exceeds .
The following common neighbourhood from bipartite density estimate is elementary. In a bipartite graph with class sizes and at least edges, averaging over left subsets of size and using convexity of the integer sequence giveswhenever . The last inequality follows by comparing the factors in the two binomial coefficients; the integer convexity follows from the nondecreasing first differences .
ChooseFor large , , so . The estimate supplies selected faces with a common extension set of size at least . This extension set is disjoint from the selected faces: a vertex in any one of them cannot extend that face. Their union has vertices in each of the old classes, with all required cross edges; choose distinct common extension vertices as a new class. Attaching one different extension vertex to each selected face also gives disjoint members of . This completes the induction, with positive constants independent of . Apply it to the clique family above and take .
The logarithmic order cannot be increased in a uniform forcing result. Put , choose strictly between and one, and take a binomial random graph. Its edge density exceeds with probability tending to one, by the variance estimate for a sum of independent edge indicators. With , the expected number of ordered embeddings of is at mostFor and , the logarithm of this bound is negative of order . Markov's inequality therefore makes the probability of any such copy tend to zero. Both events hold simultaneously for some graphs of every sufficiently large order. There are graphs meeting the density hypothesis whose largest balanced blow-up has part size . This upper bound concerns what density can force; it is not an upper bound for every dense graph, since a complete graph has much larger blow-ups.
Finally, is the square of a cycle, for . Any three consecutive vertices form a triangle in a graph. In a proper three-colouring, once the first three colours are fixed, each subsequent vertex must repeat the colour three positions earlier. Closing the cycle is possible precisely when . Conversely, repeating the three colours gives such a colouring whenever . In that case embeds in , and the density exceeds the bipartite Turan theorem threshold by a fixed amount, so the theorem forces eventually. If , the balanced Turán graphs have density at least and contain no graph of chromatic number greater than three. They give a counterexample sequence. Exactly the cycle lengths divisible by three have the required property.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 11 5 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
We first prove the needed Petridis minimal-growth lemma, including the expansion estimate rather than assuming it. For finite nonempty sets , choose a nonempty minimizing . For any finite set , defineThen . An element from has already appeared in an earlier , so the new contribution of has size at mostThe inequality follows from minimality of on subsets of , with an empty subset contributing zero. Summing proves . Iteration gives , for every ; in particular, by translating into .
We will also use the mixed-sumset bound . To justify it, the Ruzsa triangle inequality saysChoose one representation for each . The map is injective: adding the two coordinates recovers , then the chosen representation recovers . This proves the inequality. Apply it with , , and the minimal-growth set already chosen. The bounds on and give the mixed-sumset estimate, including .
The Ruzsa covering lemma states: if are finite, , and , then there is , , such that . Choose maximal with the translates , , pairwise disjoint. They lie in , so . Maximality says each meets some , which writes . This proves both assertions.
Let . The mixed-sumset bounds give and . Apply the Ruzsa covering lemma to and the set . There is of size withInduction then gives . The number of possible sums of elements from the -element set is at most the number of multiplicity vectors, namely . Since for any , we obtain the explicit polynomial growth of iterated sumsetsFor fixed , this polynomial in is eventually smaller than . For example, take and choose so that for every ; such a threshold exists because . ThereforeFor , a finite integer set has (list the increasing sums ). Thus , and the asserted bound holds for every . Nonemptiness is implicit in the doubling constant hypothesis.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 11 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Use the phase-distance convention for a Bohr set:where the norm is distance to the nearest integer. This is the Bohr set in phase-distance convention; the alternative condition has a different radius and corresponding constants. Assume , as requires.
For each residue , form in the -dimensional torus. Around these points place translates of a box of side length in each coordinate. For , their volumes sum to . If , two boxes overlap, and their distinct indices differ by a nonzero with every phase distance less than . Thus the Bohr set contains a nonzero element at the stated threshold. For larger radii the entire group is already present.
Letting the box width decrease to and using the finite number of possible nonzero , obtain a nonzero with for every . By the triangle inequality, lies in whenever . Since is prime, these multiples are distinct up to length . Therefore, in the usual radius range , the arithmetic progressionhas the requested length. For literally unrestricted , the correct lower bound is : a progression of distinct residues cannot exceed . For example, , makes the uncapped printed bound impossible. If is empty, the Bohr set is the whole group and has a progression of length ; the displayed exponent is simply inapplicable.
Now transfer the dense integer set to a larger cyclic group. Choose a prime , using Bertrand's postulate, and regard as a subset of . Its density is at least . Normalize Fourier coefficients on a finite abelian group and convolution byThe Fourier inversion and Parseval identity formulas are and ; convolution turns into multiplication of Fourier coefficients on a finite abelian group.
For , set . Then Parseval identity boundsAlso, with , the nonnegative convolution is supported exactly on the modular set , andThe frequencies outside contribute in absolute value at most . For , the real part of each phase from is at least ; moreover and . Hence . We have proved the cyclic Bogolyubov lemma with explicit phase radius:The previous Bohr set argument gives a modular arithmetic progression of length at least . The remaining step is lifting a short modular progression to an integer progression. Every one of its elements has a unique integer lift belonging to . Successive lifted differences lie in and are congruent to the same residue. Since , at most one integer in this difference interval represents that residue, so every successive difference is the same. The lifts form a genuine integer arithmetic progression, not merely a modular one.
For sufficiently large , the constants can be absorbed into half the exponent. ThusNo attempt to optimize this absolute constant is needed.
A counterexample comes from dense integer sets with only logarithmic-length progressions. To show that itself need not have such a progression, choose a random subset by independent inclusion with probability . Its size has mean and variance at most , so Chebyshev's inequality shows . There are at most increasing arithmetic progressions of any fixed length , and each belongs to with probability . Taking makes the union bound at most . For large , some realization has at least elements and no length- arithmetic progression. Take a subset of exactly elements. It retains that avoidance. Such a set has no progression longer than , and therefore no progression of length for any fixed , eventually. Interpret the prescribed exact cardinality on values of where it is integral, or use its integer part.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 11 3 1 by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 11 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Write . A sequence in the circle group is an equidistributed sequence if, for every interval ,where is its normalized length. Equivalently, averages of every continuous function along the sequence tend to its circle integral. Trigonometric polynomials approximate continuous functions, and interval indicators can be squeezed between continuous functions with arbitrarily close integrals. The nonconstant additive characters have integral zero. These facts give the Weyl criterion:This is the link between equidistribution and cancellation in exponential sums.
Suppose every positive-shift difference sequence were equidistributed. Fix and set . For every fixed , the Weyl criterion would giveThe omitted final terms change a normalized average by at most .
Here is the needed Van der Corput inequality for finite scalar sequences. Extend by zero outside and average consecutive translates of the sum. Cauchy-Schwarz givesIndeed, apply Cauchy-Schwarz to and expand the squared inner sum. Taking first leaves a bound ; then let . Every nonzero Fourier average of vanishes, so the Weyl criterion makes equidistributed. This is the differencing obstruction to equidistribution. By contraposition, a non-equidistributed sequence has a non-equidistributed difference for some positive , hence for some as requested.
For , the difference is . For any nonzero integer , its exponential sum is a constant phase times a geometric progression with ratio . Its normalized magnitude is at most , which tends to zero. Thus every positive-shift difference is equidistributed, and the contraposition just established proves
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 11 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
For a finite nonempty set , its additive energy iswhere counts ordered representations. Since , Cauchy-Schwarz givesThus implies : a small doubling constant forces many additive quadruples.
A polynomial form of the Balog-Szemerédi-Gowers theorem gives the converse after passing to a subset. There are absolute constants such that if , , then some satisfiesThe exponent and constants here need not be optimal.
Precisely, a graph form of the Balog-Szemerédi-Gowers theorem states the following. If are finite sets of size in an abelian group, has at least edges, and its restricted sumsethas size at most , then there are , with andThese are uniform absolute constants, valid for and .
To apply this theorem to additive energy, let and retain the sums with . The discarded sums contribute at most to the additive energy. Since , the retained pairs number at least . There are at most retained sums. They therefore define a bipartite graph of density at least with restricted sumset size at most . The graph theorem supplies large subsets with polynomially bounded .
For completeness, turn this cross-sumset bound into a doubling constant bound. The Ruzsa triangle inequality gives . If , the Plünnecke inequality, applied to the pair , gives . The minimal-growth proof below in Question 5 applies to arbitrary finite pairs and proves this particular expansion estimate as well. All losses are fixed powers of , proving the displayed converse after increasing .
The requested dense bipartite common-neighbour lemma is a dependent random choice assertion. Call an ordered pair in bad when it has fewer than common neighbours. Choose uniformly, and put . ThenFor each bad pair, the probability that both endpoints lie in is its number of common neighbours divided by , which is less than . Thus the expected number of bad ordered pairs in is at most . ConsequentlyChoose a neighbourhood attaining at least this expectation. It has , andHence at least the proportion of its ordered pairs have at least two-edge connections. As usual these connections are counted by common neighbours, including a return walk for a diagonal ordered pair; assume , as the formula requires.
The relevance to the graph theorem is that many two-edge connections turn a sparse collection of permitted sums into additive control on a large vertex subset. On a connection , expresses a difference using two elements of the restricted sumset. The abundance of connections, followed by standard cleaning and further path counting, bounds the number of differences without throwing away most vertices. This is the role of dependent random choice in obtaining polynomial losses in the graph form of the Balog-Szemerédi-Gowers theorem.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 10 4 Solution by
Codex 0 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.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 10 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Identify the hypercube graph with , joining two sets when their symmetric difference has size one. Write for the closed graph neighbourhood of , and for its radius- neighbourhood in Hamming distance. In the simplicial order on the discrete cube, smaller sets come first, with lexicographic order within each rank: the smallest differing coordinate belongs to the earlier set. Let be the first vertices in this order. Harper theorem isEquivalently, minimizes the external vertex boundary at fixed size. We will also obtain for every integer .
Here is a complete proof by simplicial section compression. First note two properties of the simplicial order on the discrete cube. Its restriction to either face obtained by fixing one coordinate is the corresponding order on the smaller hypercube graph. Also, the closed graph neighbourhood of an initial segment is an initial segment. To verify the latter, a nonempty initial segment contains every level below its last level , and a lexicographic prefix at level . For , its closed graph neighbourhood contains every set of size at most , and its only further members are the upper shadow of . An -set lies in this upper shadow exactly when its lexicographically earliest -subset lies in . That earliest subset is obtained by deleting the largest element. These earliest subsets vary monotonically in lexicographic order, so the upper shadow is another lexicographic prefix. For , the closed graph neighbourhood of is the union of levels zero and one. The empty initial segment causes no exception.
Induct on , with immediate. Fix a coordinate and write the sections of as , deleting from the latter section. Replace them by the initial segments with , . The sections of the old closed graph neighbourhood areBy induction their sizes are at least and , respectively. These are exactly the sizes of the new sections, because both sets in each new union are initial segments and hence nested. Thus simplicial section compression preserves size and never enlarges the closed graph neighbourhood.
Repeatedly compress any section that is not already an initial segment. Every change strictly reduces the sum of the global simplicial positions of the included vertices. This nonnegative integer decreases only finitely often, so the process ends at a family whose sections in every coordinate are initial segments. If itself is an initial segment, the induction is complete. Otherwise choose the earliest absent vertex and the latest present vertex , with . They cannot agree in any coordinate: agreement would put them in one compressed section, where an earlier absent vertex cannot precede a later present one. Hence . Nor can a vertex lie between them: if is present, pairing it with would force ; if absent, pairing it with would force . Thus are consecutive, and is obtained from by replacing its last vertex with the next vertex .
There are only two possibilities for these terminal families for simplicial section compression. If , consecutiveness makes the last -set and the first -set. Complementarity forces , and . For , the corresponding contains all sets of size at most except , and additionally . Every -set has at least two -subsets, so at least one belongs to . The missing has a -subset in . Consequently contains every set of size at most , which is exactly .
If , then . Since are complementary, the smaller one contains coordinate . Consecutiveness forces to be the last -set containing , and the first -set avoiding :The initial segment consists of all sets of size less than and all -sets containing . Its closed graph neighbourhood contains all sets of size at most and all -sets containing . For , each such -set has -subsets containing , so removing only leaves one in . All sets of size at most are still in , because all levels below belong to . Hence again . For , the two families are related by exchanging coordinates and both have the whole as their closed graph neighbourhood. These comparisons finish the induction and prove Harper theorem.
For the radius- version, repeatedly use the one-step result. At each step the comparison family remains an initial segment, and its closed graph neighbourhood is monotone in its size. If , applying Harper theorem to therefore gives . Induction on proves the asserted extension.
A Lévy family of graphs has vanishing concentration of measure functions after distances have been scaled by the graph diameter. More explicitly, for connected finite graphs of diameter , use normalized graph distance and uniform probability measure. For every fixed , requireFor this normalization is normalized Hamming distance , since its diameter is .
If , the corresponding initial segment contains the Hamming ball about of radius . The radius- version of Harper theorem impliesUse the precise Hoeffding inequality for . One can also derive this estimate directly: the moment-generating function of is ; the exponential Markov inequality followed by minimization at gives the bound. With , we have . Thus, whenever ,This proves that the hypercube graphs form a Lévy family of graphs. The stronger fixed-positive-mass formulation follows as well. For any , choose with . The Chebyshev inequality for , whose variance is , makes the Hamming ball of radius have fewer than vertices. An initial segment of size at least contains that ball. Enlarging by and using the same Hoeffding inequality gives a complement proportion tending to zero uniformly over all such . The normalization matters: with unscaled unit Hamming distance, cubes do not satisfy the metric version at every fixed radius; for a radius below one, a half-cube has no enlargement.
Equality in Harper theorem does not determine a down-set up to isomorphism. In , takeThis is a down-set of size nine. Its closed graph neighbourhood contains every set of size at most two, because all singletons belong to . Every triple contains an edge of the four-cycle among the listed pairs, so every triple also belongs to . The four-element set does not. Hence .
The size-nine simplicial order on the discrete cube initial segment is all sets of size at most one together with the pairs . Every triple contains one of these pairs, and the four-element set is again absent from its closed graph neighbourhood. Its neighbourhood therefore also has size , proving extremality of . Nevertheless the induced graphs are not isomorphic: in , the empty set has degree four, the four singletons have degree three, and the four pairs have degree two. The initial segment has two vertices of degree four, namely and . Since a graph automorphism preserves induced degree of a vertex, no automorphism of the cube can carry one family to the other. This gives nonunique down-set extremizers for Harper theorem even under the stronger test of induced graph isomorphism.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 10 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The Kruskal-Katona theorem states that a colexicographic initial segment minimizes the lower shadow of a uniform set family of prescribed size. Its numerical form is as follows. For , write the unique combinatorial number system expansionEvery of size satisfiesThe empty family has empty lower shadow. Equality is attained by the first -sets in colexicographic order, where the largest differing element belongs to the later set. Iterating the Kruskal-Katona theorem shows that the same colexicographic initial segment minimizes every iterated lower shadow.
For , the Erdős-Ko-Rado theorem givesfor an intersecting family . All -sets containing one prescribed point show that the bound is sharp.
For the proof from the Kruskal-Katona theorem, put and form the complement family . Let be its rank- iterated lower shadow. No member belongs to : containment in would give , impossible for an intersecting family of nonempty sets. HenceSuppose . The first members of the colexicographic order are all -sets of . Their rank- iterated lower shadow is all -sets of , since . The next -set contains and has an -subset containing , so taking even one more member strictly enlarges that iterated lower shadow. By the iterated Kruskal-Katona theorem, . Together with this contradicts Pascal's identity and the preceding inequality. This proves the Erdős-Ko-Rado theorem.
For the Katona circle method proof, fix a cyclic ordering of . A cyclic interval of length is specified by its final position. If no such interval belongs to , the bound below is automatic. Otherwise rotate one selected interval so that it ends at position , and thus occupies positions . Intervals ending at positions are disjoint from it and cannot be selected. Among the remaining endpoints, pair with for . The corresponding intervals are disjoint when , so at most one interval per pair is selected. Together with the interval ending at , this gives the cyclic interval intersection bound of selected intervals.
Choose a uniformly random permutation and read its positions cyclically. A fixed -set is a cyclic interval with probability : each cyclic position gives a uniformly distributed -set, and for the intervals are distinct. Summing over , the expected value of the number of selected intervals is . The cyclic interval intersection bound makes this at most , giving .
Finally apply the Katona circle method to an arbitrary antichain . If it contains or , it has exactly one member and the LYM inequality holds with equality. Otherwise all its members have sizes . In a fixed cyclic ordering, the cyclic intervals sharing a final position form a nested chain as their lengths increase. At most one of them can belong to the antichain. Summing over the final positions proves the cyclic interval antichain bound of intervals. Taking the expected value over a uniformly random permutation givesAfter division by , this is the LYM inequality proved by cyclic intervals. The case consists only of the empty set and is immediate.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 10 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Write for the rank- uniform layer of the Boolean cube. For a uniform set family , with , let be its lower shadow. The Local LYM inequality isFor its proof, count incidences with , , and . Each member of contributes incidences, while each member of the lower shadow contributes at most . Thus , which is the displayed bound by the ratio of consecutive binomial coefficients. Complementing every set gives the corresponding upper shadow bound, for .
For an antichain in the Boolean lattice, the LYM inequality isHere is the proof using the Local LYM inequality. Denote the rank- part by , and let consist of the -sets containing some member of of size at most . These families satisfyThe union is disjoint because a member of the antichain cannot contain a strictly smaller member. Apply the upper shadow form of the Local LYM inequality to :Iterating gives a bound for the entire sum by . This also covers the empty antichain and an antichain containing the empty set.
For the second proof, each permutation of specifies a maximal chain in a Boolean lattice by taking its successive prefixes. There are such maximal chains in a Boolean lattice, and a fixed -set belongs to of them. A maximal chain in a Boolean lattice meets an antichain at most once. Double counting these incidences therefore gives , exactly the LYM inequality.
The Sperner theorem says that an antichain in has at most members; a full middle rank attains this bound. Indeed, every binomial coefficient is at most the central one, so the LYM inequality givesNow let be an intersection-free uniform set family. If it is empty, there is nothing to prove. Fix and consider the tracesIf are distinct and , then . This contradicts the defining restriction on the three distinct members . The intersection has size less than , so it is a proper subset of even if the printed subset symbol is interpreted strictly. In particular, equal traces are impossible, and the traces form an antichain. Thus . Applying the Sperner theorem to the -element ground set proves the antichain trace bound for intersection-free familiesThe argument also handles : a uniform set family then has at most one member.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 1 6 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The complexification of a Lie algebra is , with the Lie bracket extended complex-bilinearly. Equivalently write , whereComplex conjugation is an antilinear map and a Lie algebra automorphism whose fixed subalgebra is .
If the solvable radical of is nonzero, its complexification is a nonzero solvable ideal of . Conversely the solvable radical of is preserved by complex conjugation, because it is the unique largest solvable ideal. Consequentlyfor , both and belong to . If , is a solvable ideal of . This proves is semisimple if and only if is semisimple. Consistently, the complex Killing form is just the complex-bilinear extension of the real one; its determinant in a real basis is unchanged by extending scalars.
Take the sl2R Lie algebra and the special unitary Lie algebra . Both complexify to . This is immediate for the former; for the latter, the real basis consists of traceless matrices that are skew-Hermitian matrices and is also a complex basis of .
They are not isomorphic as real Lie algebras. Their Killing forms are , but on this is negative definite. On the basis has a diagonal Gram matrix with entries , so the signature of a quadratic form is . A Lie algebra isomorphism preserves the Killing form and therefore its signature.
A real split semisimple Lie algebra has a Cartan subalgebra whose Adjoint representation of a Lie algebra is simultaneously diagonalizable over , so its root-space decomposition is defined over . The example is split: the diagonal Cartan subalgebra has eigenvalues and real root spaces . The example is not split. Invariance makes every skew-adjoint for the positive definite inner product , so its eigenvalues are purely imaginary. If it were diagonalizable over , all these eigenvalues would be zero and . The center is zero, so only has this property; no nonzero split Cartan subalgebra exists. Thus is split and is not.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 1 5 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Choose a positive system of a root system and the corresponding triangular decomposition of a Lie algebra . A primitive element of a Lie algebra representation of weight is a nonzero vector with for every and . Thus it is a highest-weight vector; the choice of positive roots is part of this definition. A highest-weight representation is generated by such a vector.
Let be the corresponding Borel subalgebra. Define its one-dimensional Lie algebra representation by the scalar on and zero on . This respects the Lie bracket, since . The induced Verma moduleis nonzero: the Poincaré-Birkhoff-Witt theorem identifies its underlying vector space with , and is a primitive element of weight . Its weight spaces are finite dimensional, its top weight space is the line , and all other weights are with and at least one positive coefficient.
A proper submodule cannot contain , because generates . More strongly it has no component of weight : any finite sum of distinct weight vectors can be projected onto its individual components by a polynomial in a generic element of . Therefore the sum of all proper submodules still misses the top weight line and is proper. It contains every proper submodule, so the irreducible quotient of a Verma moduleis irreducible and retains the nonzero primitive element . This constructs the requested representation for every . It is not asserted to be finite dimensional for arbitrary .
For the sl2 Lie algebra, use , and , with , , . The classification of finite-dimensional sl2 representations gives one irreducible for every integer . In a basis its action iswhere . These formulas satisfy the three Lie brackets. Any nonzero invariant subspace contains a weight vector by polynomial projection using ; repeated application of gives , and applications of then give the entire basis. Thus is irreducible.
Conversely, in any finite-dimensional irreducible module, start with an eigenvector of and apply until reaching a nonzero vector with . This process terminates because increases the eigenvalue by two and only finitely many eigenvalues occur. Write . The sl2 highest-weight lowering formula givesLet and , which again follows from the finite set of weights. Applying to the latter identity yields , so . The resulting distinct weight vectors span an invariant subspace, hence the entire irreducible module. Therefore and its primitive weight is , with ; its weights are .
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 1 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Here a reduced root system is crystallographic, as appropriate to a semisimple Lie algebra. It is a finite spanning set in a real inner product space of dimension , invariant under each Weyl reflectionwith for every pair of roots and . A base of a root system is a basis such that the coefficients of every root are integers that are either all nonnegative or all nonpositive. These define the positive system of a root system. We use the existing Cartan matrix conventionUsing the alternative denominator transposes all the matrices below.
The classification of rank-two root systems gives , , , and . In orthonormal coordinates we may choose the following simple roots and Cartan matrices:
- For , take , and . The positive roots are .
- For , take , and . The positive roots are .
- For , take the long root and short root , giving . The positive roots are . Interchanging the long and short convention gives type , which is the same rank-two classification up to the usual identification.
- For , take the short root and long root , giving . The positive roots are .
Each complete root system consists of these positive roots and their negatives. To see why the list is exhaustive, the off-diagonal Cartan matrix entries of two distinct simple roots are nonpositive integers, and their product is . Thus the product is or , corresponding to simple-root angles or . These determine the four systems and their length ratios.
The Weyl group of a rank-two root system is generated by the two simple Weyl reflections. Their product is a rotation of order , respectively, so the groups are the dihedral groups of order . The first is also the Klein four-group and the second the symmetric group . The root-orthogonal lines cut the plane into Weyl chambers, each of angle . A chosen fundamental chamber of a root system is , ; its walls are the two root-orthogonal lines. The Weyl group acts simply transitively on these open chambers.
Roots, reflecting lines and a fundamental chamber for the four crystallographic rank-two root systems
. Details. The crystallographic hypothesis matters: if the integer-pairing condition is dropped, reduced noncrystallographic systems of type also occur. They are not additional Lie-algebra root systems.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 1 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
A finite-dimensional Lie algebra over the complex numbers is a semisimple Lie algebra when its solvable radical is zero, equivalently when it has no nonzero solvable ideals. Its Killing form isThe cyclic property of the trace makes this bilinear form symmetric and gives its invariance of a bilinear form on a Lie algebra:It follows that is an ideal of a Lie algebra. For , induces the zero map on . Therefore, for , the matrix trace splits over the invariant subspace and the quotient to give . In particular . The Cartan solvability criterion implies that is solvable. Since is semisimple, : the Killing form is nondegenerate.
For completeness, the trace step in the Cartan solvability criterion is precisely the mechanism of the previous solution. For a complex matrix Lie algebra with for , , set and . If and , then , since . Linearity and the trace orthogonality nilpotence lemma show that every member of is nilpotent. The Engel theorem makes nilpotent and hence solvable. Apply this to ; the kernel of this Adjoint representation of a Lie algebra is the abelian center of , so is solvable as claimed.
For an arbitrary complex Lie algebra, a Cartan subalgebra means a nilpotent Lie algebra that is self-normalizing: . This definition does not assume that is abelian. We prove that it is abelian when is semisimple.
Use the generalized-weight decomposition for a nilpotent Lie algebra for the action of on . Its zero generalized weight space isWe have , since is nilpotent. If , the Engel theorem gives a nonzero coset annihilated by every . Its representative satisfies , contradicting . Thus .
For a nonzero generalized weight , choose with . The operator is invertible on and nilpotent on . For , , write with large enough that . Invariance of the Killing form givesOn the other hand, is solvable, so the Lie theorem triangularizes its action on . For , the matrix is strictly upper triangular, while is upper triangular. Thus . Together with , this yields . Nondegeneracy gives .
Finally, if commutes with , it normalizes , hence lies in . Any abelian subalgebra containing consists of such elements. Thus is a maximal abelian subalgebra, indeed .
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






