Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 209 4 Solution Created 2026-10-03 Updated 2026-10-06
Let and . The Lipschitz continuity of cosine and the Cauchy-Schwarz inequality implyThe centered expectation term contributes ; omitting it would leave the Lipschitz bound incomplete. In particular has continuous sample paths on the compact cube, so its maximum exists and is measurable.
PutChoose a Cartesian finite net whose coordinate spacings are at most , including the endpoints. Every point of the cube is within Euclidean norm distance of , andOn the event , replacing any by a nearby grid point changes by at most . Since and , this is less than . ThereforeThe Markov inequality bounds the first event by . At a fixed , the summands are centered, independent and identically distributed, and have absolute value at most . The supplied Hoeffding inequality, with , bounds each grid event byA union bound now givesThe choice of balances the cost of a large random Lipschitz constant against the covering number of the cube: . Consequently works, withThis uses only the first moment and has a constant independent of . The finite net is deterministic even though the Lipschitz constant is random.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 210 1 e Solution Created 2026-10-03 Updated 2026-10-06
Let . From the supplied second moment of a mixture likelihood ratio, dropping a nonpositive term givesThe last step uses the assumed separation. It has a real square root only when ; otherwise no parameters satisfy it. The chi-squared testing lower bound follows from the Cauchy-Schwarz inequality: . Every statistical hypothesis testing rule has sum of its Type I error and Type II error at least . Its larger error is at least half the sum, hence
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 210 3 c Solution Created 2026-10-03 Updated 2026-10-06
Decompose using the incidence pseudoinverse decomposition. The Cauchy-Schwarz inequality controls the constant component, and the duality of the and norms controls the remaining component:On the stipulated event, the second term contributes at most after multiplication by . The triangle inequality gives , so the negative penalty in the basic inequality for a penalized least-squares estimator cancels. We obtainon an event of probability at least .
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 213 1 i Solution Created 2026-10-03 Updated 2026-10-06
An open migration process is a continuous-time Markov chain recording the populations of finitely many colonies. Independent external Poisson processes bring individuals to colony at rate . When that colony contains individuals, a departure opportunity occurs at total rate , with . The departing individual moves to colony with probability , or leaves the system with probability . Routing choices and the clocks are independent. A return to the same colony does not change the state.
The word open means that the routing matrix is transient: every individual eventually leaves, or equivalently the spectral radius of is less than one. The traffic equations of an open migration process, with row-vector convention, give the total arrival rates:These rates include migrations as well as external arrivals. On the active colonies assume and the usual irreducible Markov chain condition. PutThe product form and its normalization condition areTo establish the product-form stationary distribution of an open migration process, first use its unnormalized weight . Its ratios satisfy . The incoming external arrivals into , divided by , contribute . Incoming exits contribute . Incoming migrations from to contribute . Terms involving an empty destination are zero. Thus the full incoming rate divided by isHere the traffic equations of an open migration process give the second equality, including . The right side is precisely the total outgoing rate. This proves global balance for a continuous-time Markov chain; pairwise detailed balance is not required for general routing.
For finite rates at each finite population, the continuous-time Markov chain is nonexplosive Markov chain: its total population is bounded over a finite time interval by the initial population plus the finitely many external arrivals, so it visits a finite set on which all jump rates are bounded. Consequently finite normalize the invariant weight to a stationary distribution. Under the stated irreducible Markov chain assumptions, this is the unique stationary distribution, and it is a positive recurrent Markov chain. Conversely, the unique invariant measure of an irreducible recurrent chain is proportional to , so a positive recurrent Markov chain requires its normalization to be finite. A sufficient condition is ; the series criterion itself is the exact condition. Colonies with have zero stationary population and can be removed from the active class.
For the single-server M-M-1 queue specialization, for , each stationary colony has the geometric distribution of an M-M-1 queue:The traffic equations of an open migration process do not involve the service rates, so the remain fixed during this service-capacity allocation in an open migration process. Write , and . A stationary allocation requires , with and . The Cauchy-Schwarz inequality givesEquality holds exactly when is proportional to . Hence, for positive arrival rates, the unique optimal service allocation and the minimum expected value of the total population areIf and some arrival rate is positive, no stable service allocation exists. Zero-arrival colonies need no service in their stationary empty class: allowing zero service there gives the same formula restricted to active colonies. If strictly positive service is demanded even at inactive colonies, the displayed minimum is an infimum approached as that unused allocation tends to zero. If all arrivals vanish, the stationary mean population is zero for every allocation that drains the initial population.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 308 2 Solution 2026-10-06
Orient both spheres in the standard way and normalize their area forms to total area . The degree of a map between oriented manifolds can be obtained in two ways. For a regular value , use the degree as a sum of local degrees:Each inverse image is isolated by the inverse function theorem, and compactness makes the set finite. The determinant is computed in consistently oriented local coordinates. A second method is spherical degree by area pullback:where the last formula represents as a unit vector in . The pullback of a differential form already contains the signed Jacobian determinant; no extra is to be inserted in that last coordinate expression.
To relate the methods, replace by a smooth top-degree differential form with the same total integral supported in a small neighbourhood of a regular value. Two such top-degree forms with equal integral differ by an exact differential form on , by its top-degree de Rham cohomology. Their pullbacks therefore have the same integral by Stokes theorem. Over the chosen neighbourhood, splits into local inverse branches; the change of variables formula makes the contribution of each branch its orientation sign times . Their sum is precisely the first formula. Thus the area integral is an integer and agrees with the signed inverse-image count.
For a nonconstant rational map, first use common-factor reduction of a rational map so and are coprime. Write for these reduced polynomials. A generic finite target value has inverse images at the roots of : avoiding exceptional values makes its degree and its roots simple. The fundamental theorem of algebra supplies roots. A holomorphic map has positive real Jacobian determinant at a regular point, so every local sign is . HenceThe source leaves coprimality implicit. In an unreduced representation the answer is , including degree zero for a constant reduced map. For example extends to and has degree one, although the unreduced maximum degree is two. Exceptional inverse images at infinity or multiple roots do not change the degree of a rational map of the Riemann sphere.
For the rational map approximation for Skyrmions, use stereographic projection and the unit target vectorCombine this rational map with a radial profile to form a special unitary group field:where are the Pauli matrices. The endpoint values make independent of angle and . Appropriate radial behaviour gives an admissible finite-energy field configuration. With , choose the topological baryon number in the Skyrme model conventionSeparating the radial and angular factors givesThus the degree of a rational map of the Riemann sphere supplies the Skyrmion charge.
In conventional dimensionless massless Skyrme model units, its static energy reduces towith the angular Jacobian of a rational mapThe Cauchy-Schwarz inequality gives . These formulas follow from the radial strain and the two equal angular strains : the quadratic energy sums their squares and the quartic Skyrme term sums their pairwise products of squares. Minimize the angular integral in the rational map approximation over degree- maps, then minimize the remaining radial energy with the stated endpoints. This replaces a three-dimensional field minimization by finitely many map coefficients and an ordinary differential equation for .
The method constructs a charge- variational approximation, with topology built in and with rotational symmetry of a rational map translated into combined spatial and isospin rotations. It is efficient for identifying shapes and providing initial data for unrestricted numerical relaxation. Its restrictions are equally concrete: it uses one radial profile and a holomorphic angular map independent of radius, so it cannot represent arbitrary radial-angular correlations, separated clusters, or all deformations. Apart from the degree-one Skyrmion hedgehog ansatz, it generally does not solve the full field equation exactly. Massive-pion terms can be included in the radial functional but do not remove these restrictions, and multi-shell or unrestricted fields may be needed for larger charges. Approximate energy minima and a final collective-coordinate quantization are distinct steps.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 323 2 ii Solution Created 2026-10-03 Updated 2026-10-06
Choose Kraus representationsThe composite quantum channel has Kraus operators . Each has matrix rank at most , because it factors through the -dimensional space , andThe operation fidelity uses the unsquared quantum fidelity on a purification of a density operator, so its square is entanglement fidelity. The Kraus formula for entanglement fidelity givesIndeed each overlap equals .
For any one of these Kraus operators , let be the orthogonal projection onto its image, of matrix rank . Since , the Cauchy-Schwarz inequality for the Hilbert-Schmidt inner product gives the rank bound for a weighted operator trace:The last step uses part (i) at , followed by nonnegativity of the eigenvalues of the density operator . Summing over the Kraus operators and using their completeness relation proves the finite-dimensional quantum compression converse:No invertibility of , or restriction to an isometric decoder, was used.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 323 4 iii Solution Created 2026-10-03 Updated 2026-10-06
Write . Normalization says , and the Schmidt rank equals the matrix rank of . Its nonzero singular values are therefore with .
The overlap with the maximally entangled state is . The trace norm estimate of Q3(i), with test linear operator , followed by the Cauchy-Schwarz inequality, givesFor two pure states, the unsquared quantum fidelity is the absolute value of their overlap. Hence the maximally entangled overlap bound from Schmidt rank isThe bound is attained by . Thus uniform Schmidt coefficients on aligned basis pairs give the greatest possible overlap for that Schmidt rank.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 325 3 iv Solution Created 2026-10-03 Updated 2026-10-06
Yes: the solution map is locally affine, hence has the Aubin property. Keep the regularization parameter fixed and define the active hinge setSince none of the margins vanishes, the optimality condition at the reference data has no fractional weights:For nearby , define the candidateEach map is continuous and is nonzero at . Because there are finitely many samples, all their signs remain unchanged on a common neighborhood of . Therefore the same set is active at for every . The hinge-loss optimality weights are still on and off , and the defining equation for proves the subgradient optimality condition. Strong convexity makes this candidate the unique global minimizer. Consequently the solution map of a parametric optimization problem satisfiesThis argument establishes stability of the active pattern without presupposing continuity of the unknown optimizer; continuity is used only for an explicit candidate and then optimality is checked.
For , the Cauchy-Schwarz inequality givesThis is the Aubin property with . In fact this constant is the exact local Lipschitz continuity modulus of the affine branch, since its derivative isThe active-set dependence of this derivative is the active-set sensitivity of hinge-loss minimization. At a vanishing margin the affine-branch argument no longer applies, although failure of this particular argument does not by itself prove failure of the Aubin property.
For the illustration, take , , and with . The hinge-loss optimality weights giveOn the middle branch the first margin is exactly zero, so that branch lies outside the strict-margin hypothesis. The example makes clear why the local affine conclusion is tied to that hypothesis, and also shows that a zero margin need not destroy local Lipschitz stability.
Past exam of the mathematics course of the University of Cambridge 2017 ia Paper 2 3F Solution Created 2026-09-24 Updated 2026-10-05
Because is a nonnegative integer, its indicator function satisfies . Taking expected values proves the upper bound. The finite second moment also gives a finite expected value, by the Cauchy-Schwarz inequality. Applying that inequality to and givesThe assumed positive second moment permits division, yieldingThe lower bound is the basic second moment method; the upper bound also follows from Markov's inequality at threshold one. Integer-valuedness is essential for that upper bound, but not for the lower bound. For example, a constant would violate the upper bound.
Past exam of the mathematics course of the University of Cambridge 2017 ia Paper 4 7D b Solution Created 2026-09-24 Updated 2026-10-05
For the constant monomial , the binomial theorem gives . For , the binomial coefficient identity givesThus , including by evaluation of the polynomials.
For and , substitute the preceding coefficient identity into the Bernstein polynomial sum and write . This yields the Bernstein monomial recurrenceThe coefficients are nonnegative and sum to ; and the others tend to zero. The weights in any Bernstein polynomial sum are nonnegative and sum to , so . Induction on therefore gives : the term has that limit and the other finitely many terms vanish. In fact, the same estimate in the supremum norm proves uniform convergence on .
As an independent quantitative bound, take a binomial distribution variable with parameters . Then . On , factoring the difference of powers gives ; the Cauchy-Schwarz inequality and the variance of giveFor the error is exactly zero. Finally the requested sum equals , so
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 105 2 c Solution Created 2026-10-03 Updated 2026-10-05
Test the weak formulation with itself. Uniform ellipticity and the Cauchy-Schwarz inequality giveThe Poincare inequality for the bounded shell with zero trace gives . If the gradient is nonzero, divide to obtain ; if it is zero the estimate is immediate and the zero trace forces . ThusThe constant depends on the shell and , not on or . Subtracting two solutions with the same forcing gives a zero-forcing solution and hence proves uniqueness. This is a coercive energy argument, not an appeal to real analytic Cauchy solvability.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 105 2 h Solution Created 2026-10-03 Updated 2026-10-05
The Sobolev embedding theorem in dimension three, combined with the preceding estimate, givesOne direct justification of this embedding is a bounded Sobolev extension operator into , followed by Fourier inversion and the Cauchy-Schwarz inequality: bounds the inverse Fourier integral by the norm.
For radial forcing, the preceding part makes and . Set , and . The radial equation gives . Both zero boundary values implyMoreover . Since , this proves the radial Poisson gradient estimate:
For a nonradial counterexample choose in the shell and a nonconstant . For sufficiently small , set and . These are smooth with support away from the boundary. Scaling givesThus the failure of L2-to-Linfinity Poisson gradient bounds in three dimensions is explicit, despite the valid and value-supremum estimates.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 107 6 a Solution Created 2026-10-03 Updated 2026-10-05
For the divergence-form elliptic operator use the weak subsolution convention for nonnegative test functions. Set and test with , where . The Sobolev chain rule makes this test admissible; boundedness and the positive regularization control the derivative of its power. Ellipticity and the Cauchy-Schwarz inequality give, with and ,Division when , and the trivial case , establish the power Caccioppoli inequality. Letting givesFor this limit uses the Fatou lemma; the gradient of a Sobolev function vanishes on a level set, so the weighted integrand is assigned zero on . The same regularization justifies differentiating in .
The PDF bounds individual entries by . Then : dimensional factors are included in the ellipticity constants when the first estimate is written as . With literal entrywise bounds, the explicit valid constant displayed here is . If bounds the operator norm instead, it is . This distinction does not alter any later conclusion, whose constants explicitly depend on .
For , put . Apply the Sobolev inequality to and useFor , , so the resulting constant is uniform in . Taking a cutoff equal to one on , supported in , with , yieldsAt a compactly supported cutoff can still be chosen with this bound by leaving an outer margin; alternatively pass to the limit from smaller radii.
For Moser iteration, set and . Repeated use of the preceding estimate bounds the successive norms byThis product is finite becauseAs the exponents tend to infinity, their norms on the Euclidean ball of radius tend to its essential supremum. ThereforeThe power is independent of the exponents of Hölder continuity in earlier questions.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 108 2 Solution Created 2026-10-03 Updated 2026-10-05
For a probability measure-preserving system, strong mixing means that for every pair of measurable sets ,A sequence has convergence in density of a sequence to when for each the exceptional set has natural density zero. A weakly mixing measure-preserving transformation has convergence in density of to for every . Equivalently, because these correlations are bounded,Indeed the mean of the absolute discrepancy is at least times the exceptional frequency, while it is at most plus a uniform bound times that frequency. A signed Cesaro convergence of a sequence without absolute values is insufficient to define weak mixing.
The standard three-cut Chacon map is obtained by cutting and stacking. Start on with normalized Lebesgue measure, an initial tower consisting of , and a reservoir for spacers. At stage , cut every level of the current tower into three equal subintervals, producing three subcolumns. Add one new interval of the same width above the middle subcolumn. Stack the first subcolumn at the bottom, then the middle subcolumn with its spacer, then the third at the top. Define the partial transformation by translation from each level to the next, leaving the current top unmapped. These assignments extend the earlier partial transformation. Repeat indefinitely.
If is the number of levels and their width, thenHence , , and the stage- tower has measure . The spacers consume total measure , precisely the reservoir. The increasing partial maps give the Chacon map modulo null sets. The tower tops and unused reservoir have measures tending to zero, and the construction yields an invertible measure-preserving transformation. With marking an original level and a spacer, the tower words satisfy and , so the first new word is . This describes the spacer placement without needing a proof of well-definedness. The three-cut convention agrees with the classical constant spacer vector described in Ryzhikov's construction.
For the correlation assertion, take the L2 inner product to be , linear in its first argument, and put . The Koopman operator is an isometry on , even when is not invertible. For the hint givesTo extend rigorously to all test functions, centre the observable: . Invariance of the integral gives . LetFor each fixed , by the same isometry identity. Therefore the limit is zero for every finite linear combination of these orbit vectors. By the Cauchy-Schwarz inequality and , approximation extends this conclusion to every : the approximation error in the correlation is bounded by uniformly in . For , the correlation is identically zero because . The orthogonal decomposition by a closed subspace now gives the result for all . ThusThis is decay of autocorrelation implies weak convergence of an observable; no assumption that is an ergodic transformation, and no invertibility hypothesis was used, and is included.
Finally, strong mixing immediately implies the stated diagonal limit by taking . Conversely, suppose that limit holds for every . Apply the correlation result with and . Its hypothesis is exactly , and its conclusion isHence strong mixing is equivalent to diagonal set-correlation criterion for mixing. Using the orbit-span proof avoids an invalid polarization argument that would recover only the sum of the two directed cross-correlations from diagonal correlations.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 109 3 ii Solution Created 2026-10-03 Updated 2026-10-05
The printed inclusion symbol here means non-strict inclusion: the PDF explicitly excludes a common member of the two set families. We use throughout. Thus a cross-Sperner family pair need not consist of internal antichains; the restriction is between the two families.
Give the Boolean lattice the uniform probability measure, and write . Form the upward closure of a set family and downward closure of a set family of :These are respectively an increasing event and a decreasing event. We have , whereas the cross-Sperner family condition gives . Set and . By negative correlation of increasing and decreasing events, first for and then for ,Apply the Cauchy-Schwarz inequality to the unit vectors and . It yieldsTherefore the Cross-Sperner inequality isIf the printed inclusion symbol were read as strict inclusion while the explicit exclusion of common members were discarded, this conclusion would fail, for example with both families equal to the middle uniform set family when . The PDF's parenthetical clause fixes the intended convention.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 125 4 Solution Created 2026-10-03 Updated 2026-10-05
Galois cohomology and the finite division quotient. Let be a number field, with its profinite topology, and a discrete continuous -module. Its Galois cohomology is continuous group cohomology. In degrees zero and one,Thus a crossed homomorphism measures the failure of a choice to be Galois-invariant, and changing the choice changes the cocycle by a coboundary. A short exact sequence of such modules gives a long exact sequence in group cohomology. The connecting map sends an invariant element to the cocycle obtained by lifting it and comparing its Galois translates.
For an elliptic curve and , multiplication by is surjective on and has kernel . The Kummer exact sequence of an elliptic curve therefore givesExplicitly, choose and set . Replacing changes this by a coboundary; replacing by , , does not change it. If its class is zero, some torsion translate of is Galois-invariant, so . This proves injectivity of the Kummer map of an elliptic curve.
The whole group need not be finite. The crucial restriction is ramification. Let contain the finite primes of bad reduction of an elliptic curve and those dividing . At , good reduction and prime-to-residue-characteristic multiplication imply that every division point of a local point is in an unramified extension, by the formal-group lifting argument. Thus every global Kummer class restricts trivially to inertia there.
Choose a finite Galois extension containing and the th roots of unity, and enlarge to include its ramified primes. Over , the torsion module is constant and can be identified with . By Kummer theory,For classes unramified outside the primes above , valuations outside must be divisible by . Their restriction images therefore lie in , the square of an S-unramified power class group. Its finiteness can be seen without assuming the Mordell-Weil theorem: the finiteness of S-unramified Kummer classes follows fromThe S-unit group is finitely generated by the Dirichlet unit theorem and its valuations at . The localized ideal class group is a quotient of the ordinary ideal class group of , which is finite by the finiteness of the ideal class group. The Minkowski bound for ideal classes supplies an integral ideal of bounded norm in each class, and only finitely many integral ideals have bounded norm.
The kernel of restriction from to is also finite: a cocycle trivial after restriction can, after subtracting a coboundary, be made to factor through the finite group . There are only finitely many maps from that group to the finite module . This is the finite-extension kernel of a Kummer map mechanism. Consequently the possible Kummer classes form a finite set, provingThis is the Weak Mordell-Weil theorem. Imposing membership in the local Kummer image at every place refines the finite unramified collection to the n-Selmer group. Its relation with the obstruction to a globally rational point iswhere the last group is the -torsion of the Tate–Shafarevich group. Thus local solubility gives a finite computable upper bound but can leave a genuine global obstruction.
Heights and finite generation. For the other essay, normalize the absolute values on a field so that the product formula holds. The Absolute logarithmic Weil height of isAt the infinite places the local degrees are one or two and the usual real or complex modulus is used. The product formula makes this independent of scaling; it is also unchanged by extending . Over , using coprime integral coordinates gives , the naive height on the projective line. The Northcott theorem says that points of bounded height and bounded field degree form a finite set; in particular this holds over the fixed field . One way to see the finiteness is the height-Mahler measure formula: for an algebraic number of degree , the coefficients of its primitive minimal integer polynomial are bounded by binomial factors times . Bounds on and therefore leave only finitely many integer polynomials and hence only finitely many algebraic numbers.
Set for , and . Since has degree two, bounded gives only finitely many points of . The height growth under a morphism of the projective line states that a degree- morphism gives . The upper bound follows from its homogeneous coordinate polynomials; the lower bound follows from their having no common zero, using a resultant identity at each place. Applied to the degree-four duplication map, it gives a uniform constant withConsequently is Cauchy: the absolute difference of consecutive terms is at most . Define the canonical height of an elliptic curve byIt is nonnegative and satisfies . The factor one-half is the conventional normalization for the divisor , since the first-coordinate height belongs to .
The addition-divisor identity also gives the bounded-error height identityuniformly in . This is the height form of the identity for the sum and difference pullbacks of the line bundle associated to ; it includes points where the affine addition formulas have a zero denominator. Apply it to , divide by , and take the limit. Thus satisfies the parallelogram law, and its polarization is a bilinear form, the height pairing. Nonnegativity implies the Cauchy-Schwarz inequality for that pairing, by evaluating its nonnegative quadratic polynomial on for all integers and approximating real ratios by rational numbers. In particularThese properties do not presuppose finite generation. Bounded canonical height gives a finite set by the bounded difference and the Northcott theorem. Torsion points have canonical height zero. Conversely, if , all have bounded naive height, so two coincide; their difference makes torsion. Thus the height detects precisely the free part, once finite generation is proved.
Use the Weak Mordell-Weil theorem with and choose finitely many coset representatives . Write , and put . The height inequality yieldsIteration enters the finite set , since after steps the height is at most . Unwinding expresses every point using that finite set and the . This proves the canonical-height proof of Mordell-Weil finite generation and henceThe Fundamental theorem of finitely generated abelian groups supplies this decomposition. The Mordell-Weil theorem combines a finite quotient from arithmetic Galois cohomology with a contracting height descent; either ingredient alone would not establish finite generation.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 129 1 Solution Created 2026-10-03 Updated 2026-10-05
Use the usual convention that a three-term arithmetic progression must be nonconstant. There is a genuine small-case defect in the printed statement: for , , and , neither conclusion can hold with . We prove the intended Roth density-increment step for every odd integer , including the small values of , rather than silently treating as covered. Counting constant arithmetic progressions would make the first alternative vacuous for every nonempty .
Suppose that has no nonconstant three-term arithmetic progression, and let be its actual density of a finite subset. Thus . Put , , and embed in the cyclic group . A congruence with is an equality over the integers, since . Thus this embedding creates no extra three-term arithmetic progressions. Since is odd, multiplication by two permutes .
Use normalized Fourier analysis on a finite abelian group, with and . For the normalized trilinear arithmetic progression count, character orthogonality givesIndeed, expanding each function in its inverse Fourier transform, averaging in forces , and averaging in then forces . The Parseval identity in this normalization is .
Let , , and , the balanced indicator function of a finite subset. Then . Only constant arithmetic progressions contribute to , whereas summing over centers counts ordered three-term arithmetic progressions in . HenceSet . Telescope by changing one factor at a time:In the Fourier transform formula for each term, bound the Fourier coefficient of by and apply the Cauchy-Schwarz inequality to the other two factors. The permutation preserves the required squared sums. Since and , this givesIf , then , so the difference in the other direction is at least . Consequently Fourier detection of a progression-free subset of an interval gives a nonzero frequency with
To turn this into a density increment, take . The Dirichlet approximation theorem, proved here by placing into equal intervals modulo one, gives such that . DefineFor , the inequalities and show thatUse a progression partition with nearly constant linear phase: every residue chain of modulo has at least points. Split each chain into blocks of consecutive chain points, merging any remainder into its last full block. This partitions into arithmetic progressions with and common difference .
On a block with first point , the linear phase satisfiesLet . Freezing the linear phase on each block introduces error at most . ThereforeThe block sums total zero. Their positive part consequently totals at least . Since all block lengths total , some block has . Its density of a finite subset is at least .
For the remaining , divide into disjoint consecutive triples and a remainder of at most two points. A three-term-arithmetic progression-free uses at most two points of each triple, so ; the largest ratio occurs at . Any singleton set from then has density of a finite subset one, which is at least . We may therefore use the explicit constantsIn the large case the constructed arithmetic progression has length at least ; in the small case its length one does too. Thus these constants prove the intended result for all odd integers .
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 129 2 Solution Created 2026-10-03 Updated 2026-10-05
Write for the edge density of a bipartite graph between nonempty disjoint vertex sets. A regular pair of vertex sets is -regular if whenever , , , and .
The Szemerédi regularity lemma says that for every and positive integer there is such that every finite simple graph on vertices has a set partitionwhere have equal positive size and at most unordered pairs , , fail to be regular pairs of vertex sets. The version requiring only sufficiently large is equivalent, since the finitely many smaller admissible sizes can use singleton sets as classes. It suffices to prove this for : reducing a larger parameter to gives stronger conclusions.
Here is a complete energy proof, including restoration of equal class sizes. For a set partition with exceptional set , use the following version of equitable regularity energy, omitting pairs incident with :For , define using the ordered adjacency indicator function, with diagonal entries zero. Thus the same formula works on every rectangle. The refinement variance identity for regularity energy iswhere run over the refined cells. Expanding the square proves the identity because their weighted mean edge density of a bipartite graph is . In particular, refinement never decreases the energy. If a union of refined cells has discrepancy greater than , the Cauchy-Schwarz inequality bounds its contribution below by . For an irregular equal-class pair of size , witnesses have sizes at least , so the increase exceeds in each orientation.
Choose so large that . Initially partition into equal classes and fewer than exceptional vertices. For sufficiently large this exceptional set has size at most . Suppose there are more than irregular unordered pairs at a subsequent step, with equal class size . Choose one witnessing pair of subsets for every such pair. Split each class according to membership in all its witness subsets; each class produces at most atoms. The preceding refinement variance identity for regularity energy shows that the energy increase exceedsas long as the exceptional set has size at most .
Apply equalization with a controlled exceptional set. Set , cut every atom into blocks of size , and send its leftover points to . Provided , the new number of classes satisfiesThe lower bound holds because every old class retains at least one full block: its leftovers total less than . The discarded fraction is at mostCutting blocks is a further refinement before discarding. Discarding changes only ordered pairs with at least one discarded vertex, so it loses at most in the energy. The net increase is therefore at least .
There can be fewer than such strict energy increases, because the energy stays in . Through steps the exceptional fraction is at mostThis also verifies the exceptional-set bound used at every preceding step. Iterating the finite recursion at most times bounds all class counts by some . Choosing sufficiently large in terms of , for instance with and , guarantees throughout. Thus the process terminates with the desired regular pairs of vertex sets. Choose a finite integer threshold for these requirements and set . For , use singleton sets; every pair is regular because its only admissible nonempty subsets are the whole pair. This completes the Szemerédi regularity lemma for all admissible .
For the half graph, a class of size has exactly elements with fewer than predecessors, and the same number with fewer than successors. Thus its boundary contains at most elements. Let be the numbers of classes. The boundary rank obstruction in a half graph gives the union boundbecause . There is therefore an index away from both boundaries. In its classes , all four subsets , , , have at least one tenth of their respective class sizes. These subsets are taken within , which need not be intervals.
In the half graph, and . If were a -regular pair of vertex sets, both values would be within of , implying , a contradiction. At least one class pair is not -regular.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 129 4 Solution Created 2026-10-03 Updated 2026-10-05
Uniform expectations require nonempty finite sets; assume this throughout the analytic argument. For real-valued functions on , define the box norm byAll four variables are sampled as independent random variables with replacement, so repeated coordinates are included. The defining fourth power equalsIf it vanishes, every summand vanishes. In particular, the terms give for each , so . Absolute homogeneity of a norm follows directly: .
For the triangle inequality, prove the mixed box Cauchy-Schwarz inequality. WriteSeparating the two averages and applying the Cauchy-Schwarz inequality in givesExpanding the square and reversing the order of finite sums,by a second Cauchy-Schwarz inequality. Thus . Expand into its sixteen multilinear terms and apply this bound to each term. Their upper bounds sum to . Taking fourth roots yields the triangle inequality. Together with definiteness of a norm and absolute homogeneity of a norm, this proves the box norm is a norm. Complex functions require conjugates and are outside the printed real-valued convention.
For the bilinear correlation bound for the box norm, use the normalized L2 norm: let and , . The Cauchy-Schwarz inequality in givesThe remaining factor is . By the Cauchy-Schwarz inequality in , its magnitude is at mostTaking square roots proves
For the tripartite graph, assume its parts are nonempty and write for its adjacency indicator functions. Let , so . The normalized triangle count isThe constant-degree hypothesis is exactly for each . Therefore the contribution of the constant isFor fixed , apply the bilinear correlation bound for the box norm with and . Since these are indicator functions, and , the fraction of adjacent to . Averaging and applying the Cauchy-Schwarz inequality in gives the sharper triangle counting with one box-uniform pair and constant opposite degree estimateMultiplying by yieldsThe middle bound also handles or , when the triangle count is zero.
To connect explicitly with the suggested expansion, put , . Both have overall mean zero, and for every . Consequently ; all terms with constant reduce to . The terms containing combine into the single error just estimated. This is where the exact degree assumption is used. If any part is empty the triangle count itself is zero, but the printed uniform expectations and edge density of a bipartite graph values would be undefined; the nonempty-parts convention must therefore be stated rather than dividing by zero.
