Past exam of the mathematics course of the University of Cambridge 2013 ia Paper 4 2E Solution Created 2026-09-24 Updated 2026-10-07
A real sequence converges to a finite limit ifA series converges when its partial sums form a convergent sequence with a finite limit. These are different conditions: a series concerns accumulated terms, whereas sequence convergence concerns the terms themselves.
If , then as well and . Explicitly, choose large enough that both partial sums lie within of ; the triangle inequality gives . Hence convergence of a series forces its terms to tend to zero.
For the converse, take . This is a null sequence, but its harmonic series diverges. In each block , there are terms each at least , so the block contributes at least . ThusA zero limit for the terms is necessary, but not sufficient, for convergent series.
Past exam of the mathematics course of the University of Cambridge 2013 ib Paper 1 12G ii Solution Created 2026-09-24 Updated 2026-10-07
The quotient map is continuous and surjective by the quotient topology, so is compact as a continuous image of a compact space. To prove the Hausdorff property explicitly, let and set . Choose . The saturated open setsare disjoint by the triangle inequality. Each contains both antipodes of every one of its points, so and similarly for . Consequently are disjoint open quotient neighborhoods separating the classes. Thus the quotient is compact and Hausdorff. It is the real projective plane; equivalently the metric on the antipodal sphere quotient is and induces this topology.
Past exam of the mathematics course of the University of Cambridge 2013 ib Paper 2 3F Solution Created 2026-09-24 Updated 2026-10-07
Both maxima exist by continuity on the compact set . Their sum is nonnegative and vanishes only for . The identities and the triangle inequality follow by applying the corresponding supremum norm facts to and . This proves that is a norm.
For , . Hence the first unit ball has image contained in : derivative evaluation is a bounded linear functional for this norm.
For the supremum norm alone, take . These smooth functions satisfy , but . Thus the second image is unbounded. The distinction is the unboundedness of derivative evaluation in the supremum norm, not a failure of differentiability of the individual functions.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 11 4 Solution 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 31 2 Solution Created 2026-10-03 Updated 2026-10-07
Use the following normalization for the Lasso estimator, leaving the intercept unpenalized:A different convention for the factor in front of squared error rescales the regularization parameter. With this convention, centering of the columns gives . Put and . Then and . The Lasso minimizes . A minimum exists since makes this continuous objective coercive; the bound below holds for every minimizer.
We first prove the needed sharp two-sided Gaussian tail bound. If is standard normal and , substituting in its density integral yieldsThe last integral without is one after multiplication by . In particular this proves the two-sided bound with no extra factor of two.
Since , each has a standard normal distribution. The union bound, which does not require independent columns or independent scores, gives the Gaussian score event for the LassoHere the positive tuning choice presupposes and . When the displayed lower bound is negative it is simply a valid, vacuous lower bound. For the prescribed parameter is zero and the probability lower bound is also zero, so no positive-parameter assertion is supplied by that prescription.
Let and . Comparing the Lasso objective at its minimizer and at and expanding the squares gives the Basic inequality for the LassoOn , the stochastic term is at most . Because , the triangle inequality givesIt follows thatIn particular , which is the Lasso cone condition. The given Compatibility condition for the Lasso is therefore applicable and gives .
Adding to the preceding inequality and using compatibility now yieldsThe last inequality is just the nonnegativity of . Thus , and dropping one nonnegative coefficient-error term givesThis prediction and coefficient error bound for compatible Lasso holds on , and hence with the required probability. If , the earlier basic inequality directly forces on , so the zero right side is also correct.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 36 1 a Solution Created 2026-10-03 Updated 2026-10-07
Let be the support of a vector , with . Suppose the null space property holds. Every other feasible vector is , where . Splitting its L1 norm over and and using the triangle inequality givesThus the sparse vector is the unique minimizer in basis pursuit. Notice that the argument works for complex coordinates: it uses the absolute value inequality, rather than a real sign function.
Conversely, suppose basis pursuit uniquely recovers every sparse vector of order . Fix and any with . Take and . These vectors have the same measurements, because , and they are distinct since . The vector has at most nonzero coordinates, so uniqueness givesThis is the null space property for every such . Uniform unique recovery by basis pursuit is equivalent to the order- null space property.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 36 1 b Solution Created 2026-10-03 Updated 2026-10-07
First the null space property implies sparse injectivity. If a nonzero had at most nonzero coordinates, partition its support of a vector into disjoint with . Applying the null space property to each of these sets yieldswhich is impossible. Hence the null space contains no nonzero sparse vector of order .
The feasible vector has , where the L0 sparsity count counts its nonzero coordinates. Any different feasible with would give a nonzero null space vector with at most nonzero coordinates, contrary to sparse injectivity. Consequently every different feasible has strictly larger L0 sparsity count. The unique sparsest feasible vector is :This proof does not treat the L0 sparsity count as a genuine norm; no triangle inequality for it is needed.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 58 4 a ii Solution Created 2026-10-03 Updated 2026-10-07
The printed upper summation limit introduces although only qubits were defined. Literally the final term is undefined. Use the natural open-chain repairThis preserves the stated -qubit system and agrees with the supplied sum-of-squares hint. If a cyclic convention was intended instead, it must be stated; the same argument works for its terms when . For , the repaired open chain is empty and the target is the identity.
Here is a product-formula Hamiltonian simulation using exactly the two supplied lemmas. Let and choose an integer . Every is a norm-one Hermitian matrix. One time slice is the product of two-qubit gatesTo compare a partial product with , first propagate the previous error through the next unitary gate, which preserves the spectral norm, and then use Lemma A with , . Both norms are at most . Its new error is at most for a universal constant . For an explicit choice, follows from the unitary Taylor bounds and . Induction and the triangle inequality therefore giveLemma B, the unitary product telescoping bound, now compares the repeated slices with :Take, for example, . If the sum is zero the product is already exact; otherwise its error is at most . There are two-qubit gates. This explicit lemma-based construction has fourth-degree dependence on for fixed precision:This is a sufficient polynomial, not an optimality claim. The polynomial-degree statement treats as fixed; the inverse-precision dependence is displayed separately. No first-order term error is accumulated without the required repeated-slice factor.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 64 1 Solution Created 2026-10-03 Updated 2026-10-07
Write for the total variation seminorm on a domain. For a locally integrable real function its dual definition isThe bounded-variation space consists of functions with finite , equipped with . In the equivalent distributional derivative description, is a finite vector-valued Radon measure and is its total variation measure.
To establish completeness of the bounded-variation space, let be Cauchy in this norm. Completeness of gives in . Given , choose so that whenever . For fixed , the given lower semicontinuity yieldsSince , we obtain . In particular has finite variation; the triangle inequality then puts in the BV space. The same bound proves convergence in the full norm, so this is a Banach space.
For the disk data, put and assume . The exact total variation denoising of a disk isHere is the positive part. A total variation calibration certifies global optimality, including competitors that are not radial or piecewise constant. Define the bounded vector fieldIt has . Its normal component is continuous across the circle, so the distributional divergence has no extra boundary measure. Direct differentiation gives . The dual definition implies : for the standard domain one can cut off at radius , with the error bounded by , and then smooth the test field. In the larger homogeneous bounded-variation space, the same error is bounded by . Thus both usual whole-plane formulations give the same certificate.
Use the perimeter identity and . If , then and . Consequently every competitor satisfiesIf , replace by . Its norm is still at most one, its divergence is , and equality in the calibration holds at . The identical comparison proves optimality and uniqueness of zero, including the threshold . The only general results used are completeness of , lower semicontinuity of variation, the indicator-perimeter identity, the distributional integration-by-parts/dual variation formula and the quadratic norm identity. For , the unique squared-error minimizer is simply .
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 6 4 a Solution Created 2026-10-03 Updated 2026-10-07
Nonnegativity and unit mass give, by the triangle inequality for the Fourier transform, . The finite second moment implies a finite first absolute moment, so differentiating under the Fourier integral is justified andThe exponent convention has no , so no such factor occurs in this derivative.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 6 4 e Solution Created 2026-10-03 Updated 2026-10-07
Expansion of the two squares givesLet be the Fourier distance of order two, with the supremum taken over . Both Fourier transforms have modulus at most one. Add and subtract , then use the triangle inequality:Dividing by proves the bound by , and splitting the last expression into its two weighted terms gives the requested intermediate inequality. If one of vanishes, its unweighted difference is zero by equal mass; its weighted term is interpreted as zero, avoiding a quotient.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 54 2 e Solution Created 2026-10-03 Updated 2026-10-06
The hypothesis is , with the physical surface density nonnegative. At height , the vertical derivative of an isolated thin-disk gravitational potential has a strictly positive kernel:The same formula with represents . The triangle inequality and the strict surface density bound therefore give the positive-kernel comparison of thin-disk fieldsUse . The integrand in part (c) is then in the upper vacuum region. Reflection symmetry gives the same result below; the infinitesimally thin disk has zero three-dimensional volume. Thus, with the finite-integral assumptions of the tensor virial theorem,Since the disk starts at rest, initially and its radial second moment begins to decrease. This is magnetic subcriticality of a razor-thin disk: magnetic support cannot prevent initial contraction in the global virial sense. The conclusion concerns the mass-weighted radial size, and does not by itself prove that every fluid element accelerates inward or that contraction continues indefinitely.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 61 4 b Solution Created 2026-10-03 Updated 2026-10-06
Use the operator norm induced by the usual vector norm, and assume the input quantum state is normalized. Since and the Hadamard gate is unitary, the J-gate phase-error operator norm isWrite the exact and implemented quantum circuits as ordered products and . The quantum circuit gate-error telescoping bound follows fromEvery surrounding factor is unitary, including gates tensored with identities on other qubits, so the triangle inequality and the submultiplicativity of the operator norm giveThe exact Controlled-Z gates contribute zero to that sum. ThusThe endpoint is sufficient because each implemented angle error is strictly smaller than . If , the circuits are identical and any positive works. The bound controls the stated vector distance with actual gate phases retained, so no adjustment of the global phase of one output is needed.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 64 2 iii Solution Created 2026-10-03 Updated 2026-10-07
The literal assumptions suffice for the scalar quadratic fidelity problem. One can avoid regularity of level-set boundaries by moving only a clipped part of the minimizer. We prove the stronger jump-amplitude inequality for total variation denoising:Comparison with the zero function gives finite energy and hence . Here , and both differences use the same oriented BV traces on a hypersurface. Reversing the normal reverses both differences and leaves the inequality unchanged. Outside , the two traces of agree, so the inequality would read at a jump of . It therefore gives the requested no-new-jumps property of total variation denoising in every dimension.
First use residual-preserving clipping of an ROF minimizer. For an integer , putThe coarea formula for BV functions gives scalar total variation splitting under clipping:Indeed the levels in contribute to , while the levels outside that interval contribute to . This uses the full signed coarea formula. For any , minimality of and the triangle inequality for the total variation seminorm giveCancel the tail variation. Thus is a bounded ROF denoising minimizer for . The data may still be unbounded. This is an exact reduction preserving ; it does not truncate the data and then pass to a limit of different reconstructions.
We next prove the jump-amplitude inequality for a bounded ROF minimizer, allowing its data to be unbounded. Fix a coordinate , a nonnegative , and let be the local flow of the smooth vector field . The flow is the identity near the domain boundary, preserves each line parallel to , and satisfies . WriteThese maps are diffeomorphisms, with and uniformly.
The useful trace calculation is the BV jump-product limit with one bounded factor. For and ,The right side is integrable: and only the common jump part of contributes. The same limit holds with both increments replaced by their negative-time increments, still dividing by positive .
Here is why this calculation needs only one bounded factor. By the BV slicing theorem, almost every coordinate slice of and has one-sided representatives. On one such interval let and use its right-continuous representative. Since ,Fubini's theorem rewrites the slice integral asAt each interior , the inner expression tends to ; if , it is zero. Its absolute value is at most . Dominated convergence against therefore leaves just the measure atoms common to the two slices. The bound is also integrable over the transverse coordinates, by the BV slicing theorem. Integrating the slice jump sums gives the surface integral and its factor . Negative-time increments give the same product, because both slice differences reverse sign. At no point is a uniform bound on across the slices required.
For , use the mixed competitorsThe total variation under opposite smooth flows satisfiesTo see this for the entire vector Radon measure , the change of variables formula givesFor , the two cofactor matrices expand as , with the same and opposite signs. Their norm expansions on have cancelling linear terms. Integrating proves the estimate, including the absolutely continuous, jump and Cantor parts. The BV transformation formula is also given in Lemma 4.2 on differentiable regularizers; that lemma does not assume bounded data. The total variation seminorm is a convex function, soThus minimality forces the sum of the two fidelity changes to have nonnegative limit after division by .
It remains to evaluate that sum without bounding . Put . Exact expansion of the quadratic fidelity, together with change of variables, gives the opposite-flow fidelity identity for quadratic data:For completeness, the cross-term identity fixing its sign isThe last integral is : , whileTake first, then . Here and the local flow is strongly continuous in . The remaining Jacobian mass term is . This argument avoids multiplying an unbounded fidelity derivative by an uncontrolled derivative measure.
Apply the BV jump-product limit with one bounded factor with and , and use minimality. For every nonnegative and every coordinate ,Let . These are inequalities for finite signed Radon measures, so arbitrary nonnegative smooth tests imply nonnegativity of their densities. Since at least one coordinate of a unit normal is nonzero,This proves the bounded-minimizer lemma with arbitrary data.
Finally return to and . At almost every finite approximate jump point of , choose an integer . The BV traces on a hypersurface commute with clipping, so , and there. It is consequently a jump point of , and its inequality is exactly . A countable union over removes all exceptional surface-null sets. Outside , the BV traces on a hypersurface of agree almost everywhere. We concludeThe mechanism is exact scalar coarea splitting, paired smooth-flow variations, a one-bounded-factor BV trace limit, and localization through integer clipping levels. It works in every dimension under the printed hypotheses, without essential boundedness of or and without regularity of their level-set boundaries.
In total variation calibration notation, . Since this divergence is itself in the BV space, the proved inequality equivalently readsThus an upward output jump forces the appropriate nonpositive jump of the calibrated divergence. This is a consequence of the variational argument above, with common oriented BV traces on a hypersurface; no curvature of the rectifiable interface or differentiability of its normal is assumed.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 7 1 b Solution Created 2026-10-03 Updated 2026-10-06
The derivative of the backward characteristic flow map isThus the change of variables formula preserves phase-space Lebesgue measure. With zero source, , so for every finite ,Taking the th root proves . For this is a quasi-norm, and the argument still works because it uses only a change of variables, not the triangle inequality. The identity also holds in the extended sense when an integral is infinite. Since the flow is bijective and measure-preserving, it additionally preserves the essential supremum, so the same conclusion holds for .
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 7 2 a Solution Created 2026-10-03 Updated 2026-10-06
Use the unit-period circle , with total measure one. The free characteristic flow map givesTranslations in preserve its periodic measure. The Tonelli theorem and the integral triangle inequality yieldThe Fubini's theorem therefore applies also to signed data, and the same translation givesThis holds for positive or negative time. The printed in this subpart is a domain typo: the spatial variable is periodic, so the correct space is . For example, the smooth initial value gives the constant density , whose periodic extension is not integrable on the real line.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 7 3 b Solution Created 2026-10-03 Updated 2026-10-06
The Fubini's theorem and integral triangle inequality giveDefine the normalized velocity-reset collision operator using the normalized velocity-reset projection and . Since and ,Also ; the collision gain replaces the velocity distribution by while preserving the spatial mass. In Bochner integral notation the printed, undamped source operator isUsing the transport isometry and the integral triangle inequality provesThese estimates hold for measurable, locally time-bounded -valued functions. If the displayed supremum is infinite, the numerical bound is interpreted in the extended sense; the construction below works in a space where it is finite.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 79 1 i Solution Created 2026-10-03 Updated 2026-10-07
The Roth theorem on three-term arithmetic progressions says that, for each fixed , a sufficiently long interval cannot have a subset of density of a finite subset at least with no nonconstant three-term arithmetic progression. Equivalently, the maximum size of a three-term-progression-free subset of is . Here is a density increment proof, including its analytic ingredients.
Write and embed into the cyclic group of order . For normalized Fourier analysis on a finite abelian group take . The orthogonality of complex exponentials follows from a finite geometric series: its average is zero for a nonzero frequency and one for frequency zero. Expanding in these linear phases consequently proves both Fourier inversion on a finite group and the Parseval identity on a finite group. In particular,The second identity follows by summing the frequency expansion over : the two constraints leave precisely the frequencies . Since is odd, multiplication by two permutes the frequencies. Also a congruence with is an equality in the integers, since .
Let have subset density , and suppose it contains no nonconstant three-term arithmetic progression. Its balanced indicator function of a finite subset is , extended by zero outside . Then . Counting endpoints with the same parity givesIf , their difference in absolute value is at least . Telescope the difference of the products into three terms, each containing and two factors chosen from . Put . The Cauchy-Schwarz inequality and the Parseval identity on a finite group bound each term by , since the squared normalized norm of either other factor is at most . Therefore some nonzero frequency satisfiesThis is the Fourier detection of a progression-free subset of an interval step; it has just been proved rather than assumed.
We now turn this Fourier coefficient on a finite abelian group into a density increment. Set . Partition the unit interval into equal pieces and place the fractional parts of in them. The pigeonhole principle gives with . This proves the particular Dirichlet approximation theorem needed here. Put and . For sufficiently large depending only on , and . Each residue chain modulo in has at least elements. Split each such chain into arithmetic progressions with between and elements, absorbing its final short remainder into the previous block.
The linear phase changes by at most within any block. Freezing the linear phase at the first element of each block therefore changes the preceding correlation by at most , because . The triangle inequality givesThe block sums of the balanced indicator function of a finite subset add to zero, so their positive total is half their absolute total. Some block consequently satisfiesHere is absolute, and shrinking it absorbs the floors. An affine parametrization of identifies with a subset of and preserves arithmetic progressions.
Repeat this Roth density-increment step. Every step raises the subset density by at least , so fewer than steps are possible. All the lengths satisfy while above a threshold depending only on . Choose the initial so large that this lower recursion stays above that threshold for steps; this is possible by working backwards through finitely many squarings. We would then force a subset density greater than one. Thus every fixed positive density eventually forces a nonconstant three-term arithmetic progression. For an infinite subset of the positive integers with positive upper asymptotic density, apply the finite conclusion along initial intervals whose subset density is bounded away from zero; this gives the usual infinite formulation as well.
Past exam of the mathematics course of the University of Cambridge 2015 ia Paper 1 5B iii Solution Created 2026-09-24 Updated 2026-10-06
Apply the triangle inequality to the path from through to :This is one direction of the reverse triangle inequality. A second application of the triangle inequality, this time through , givesThe resulting four-point triangle inequality follows without any assumptions on coincidences among the four points.