Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 28 6 Solution Created 2026-10-03 Updated 2026-10-14
Let count pairs both prime with . The Selberg sieve replaces primality by the necessary condition that the polynomial have no small prime divisor. Its strength is a nonnegative quadratic majorant with optimizable divisor weights; its limitation is that a sifted integer need not be prime.
For a prime , let count the forbidden residues of modulo . We have , since the two roots coincide modulo two, and for every odd prime, where the roots are zero and . The Chinese remainder theorem makes multiplicative on squarefree integers. With ,These local densities constitute the sieve distribution for the twin-prime problem. Since , it is a dimension-two sieve, which is why the expected upper bound has two logarithms in the denominator.
Let and choose real Selberg sieve weights supported on squarefree , with . If , the only supported divisor of is one. HenceExpanding and using the distribution of the polynomial roots givesHere denotes the least common multiple. The divisor-square support reaches , although each individual weight is supported only to ; keeping these two levels distinct is essential for estimating the remainder.
The Selberg sieve diagonalization solves the main-term minimization exactly. On squarefree integers putMultiplicativity givesAlso, Möbius inversion gives . Therefore the Cauchy-Schwarz inequality proveswith equality at . Inverting the divisor sums gives the optimizing weightsIn particular and .
These weights have , which supplies a simple rigorous remainder estimate. Indeed, multiply the inner sum by . The terms are for distinct squarefree integers with and , hence form a subset of the sum defining . Since and ,Thus
For this sieve and for odd primes. Here is a direct proof that , sufficient for the upper bound. PutThe Mertens theorem for reciprocal primes implies , by taking logarithms and using the convergence of . Give each divisor probability . Its expected logarithm isby the Mertens first theorem. With this is at most for large . The Markov inequality shows that at least two thirds of the total product weight has . These terms occur in , so . Conversely , proving the claim without treating an untruncated Euler product as a truncated divisor sum.
Choose, for example, . Any twin-prime pair with smaller member greater than survives this sieve; pairs with smaller member at most contribute at most . ConsequentlyThe chosen level is deliberately enough to prove the correct logarithmic order; sharper level and remainder analyses improve the numerical upper-bound constant.
The local correction factor also explains the conjectured main-term constant. Relative to two independent primality conditions, the singular series isThe twin-prime constant is positive and convergent because its logarithm has an absolutely convergent tail. The factor two at records that only one parity is allowed, while each odd-prime factor records the two distinct forbidden residues. The Hardy–Littlewood twin-prime asymptotic conjecture predictsThis is a conjecture, not a consequence of the upper-bound calculation.
The parity problem in sieve theory is the obstruction to reversing the argument. The nonnegative square majorizes all survivors, including composites with sufficiently large prime factors; small-divisor information does not isolate the desired prime-factor parity or force both factors to be prime. Therefore the Selberg sieve establishes the correct upper-bound scale and the arithmetic local factors, but by itself does not prove a positive lower bound for twin primes, their infinitude, or the conjectured asymptotic.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 28 7 ii Solution Created 2026-10-03 Updated 2026-10-14
Use the integer norm lower bound for rational approximation to a quadratic irrational. The integer is nonzero, since is irrational. If , thenbecause . If , the difference is at least . ThusIn particular, is a badly approximable number.
To estimate the prime-weighted exponential sum, let . The Dirichlet approximation theorem gives a reduced fraction withCombining this with the lower bound gives . Thus ; the approximation cannot have a small denominator.
The relevant analytic input is the prime exponential-sum estimate from Vaughan identity:Here is the structure behind that estimate. With Dirichlet convolution and cutoffs , the Vaughan identity isIt follows from , , and . The first two Dirichlet convolution terms become type I sums with one short factor; the last becomes a bilinear type II sum with both factors bounded below. Split these sums into dyadic blocks and use . For the type I sums, the inner finite geometric series has bound . For the type II sums, the Cauchy-Schwarz inequality followed by expansion introduces analogous sums in differences of indices. Rational approximation separates the phases into blocks of length comparable to , bounding these reciprocal-distance sums. The Dirichlet convolution coefficients are divisor-bounded, producing the logarithmic factors. These steps give the displayed estimate; no unproved cancellation of arbitrary weighted sums is being assumed.
With and , the two denominator-dependent terms are . ConsequentlyThe final passage absorbs the logarithm using the positive exponent margin .
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 29 1 Solution Created 2026-10-03 Updated 2026-10-14
We first give an auxiliary-polynomial proof, rather than assuming a transcendence theorem for exponentials. Suppose were algebraic, and let be its conjugates. Since the first factor vanishes,Expand and collect equal subset sums of the . This gives , where counts the zero sums, the are distinct nonzero algebraic numbers, and each is a positive integer. The exponents and their weights are invariant under every Galois permutation.
Choose a positive integer such that all are algebraic integers. Their Galois-invariant monic polynomial has rational algebraic-integer coefficients, hence lies in . Its constant term is a nonzero integer. For a prime defineAt each , derivatives below order vanish. Every higher derivative is times an algebraic integer, so is divisible by in the ring of algebraic integers. At zero the only derivative not visibly divisible by is the one of order , and thusGalois invariance makes rational; it is therefore an integer, divisible by . ConsequentlyFor every prime not dividing , this is a nonzero integer.
The finite derivative sum satisfies , so integration along the straight segment to givesSum with weights and use . The result isOn these finitely many fixed compact segments, , and are bounded independently of . Hence . There are arbitrarily large primes not dividing the fixed integer , contradicting . Therefore . This is the Hermite auxiliary-polynomial proof for pi.
The more general Lindemann–Weierstrass theorem states that exponentials of distinct algebraic numbers are linearly independent over . Equivalently, exponentials of rationally independent algebraic numbers are algebraically independent over . In particular, the exponential of a nonzero algebraic number is transcendental.
Suppose were algebraic. The exponential formula for cosine givesAfter combining equal exponents this is an algebraic-coefficient linear relation among exponentials of distinct algebraic numbers. At least one exponent is nonzero, since and cannot both vanish when . Its coefficient is a positive integer, even when two exponents coincide. The relation is therefore nontrivial and contradicts the theorem. Thus , including the cases .
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 29 2 Solution Created 2026-10-03 Updated 2026-10-14
An integer version of Siegel lemma is as follows. For homogeneous linear equations , with integer matrix entries bounded in absolute value by , there is a nonzero integer solution satisfyingPut the displayed integer bound equal to and evaluate the equations at every vector in . There are inputs and at most outputs. But and , so the number of inputs is larger. Two distinct inputs have identical outputs; their difference proves the claim. This is the pigeonhole proof of integer Siegel lemma. Rational coefficients are handled by clearing denominators. Over a number field of degree , expanding in a rational basis gives at most rational equations, so the same construction applies when , with the height of the resulting integer matrix controlling the bound.
Siegel's original arithmetic definition starts with an entire series , with all in a fixed number field. For every there must be positive integers such that are algebraic integers, and both and the absolute values of every conjugate of are . The growth condition ensures convergence everywhere. The stronger, now customary strict E-function definition uses bounds for a fixed and also includes the requirement of a nonzero linear differential equation over . In the original formulation, that differential condition is explicitly part of the system hypothesis in the theorem below. These definitions should be distinguished; the exponentials used here satisfy even the stronger conditions.
The Siegel–Shidlovsky theorem states that if a vector of E-functions satisfies , with a matrix of rational functions over , then for every nonzero algebraic which is not a pole of ,In particular, algebraic independence of the functions implies algebraic independence of the values. The exclusion of zero is necessary: their Taylor values there are algebraic.
Take rationally independent algebraic and . Their coefficients are , their conjugates grow exponentially, and powers of a fixed common denominator clear all coefficients through degree . They satisfy the nonsingular diagonal system .
To check functional independence, a polynomial relation among these exponentials, after clearing rational-function denominators, would be with distinct . Such an exponential polynomial cannot vanish identically. To isolate a nonzero term with exponent , apply . All other terms vanish, while the remaining polynomial is acted on by operators , each injective on polynomials because its nonzero constant preserves a nonzero leading coefficient. Thus the remaining term is nonzero, a contradiction.
The theorem at now makes algebraically independent. For arbitrary distinct algebraic exponents , choose a rational basis of their span and divide its elements by a common denominator so that every is an integer combination of the resulting . Then are distinct Laurent monomials in . A linear relation among them becomes a nonzero polynomial relation after multiplying by a common monomial, contradicting independence. These particular E-functions therefore yield the full Lindemann–Weierstrass theorem.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 29 3 Solution Created 2026-10-03 Updated 2026-10-14
Write . The authoritative PDF has exponent ; the geometric-series exponent in the converted TeX is a transcription error. On the unit disk this Fredholm series satisfiesFirst it is transcendental as a function. If , the terms with in are the positive terms and their sum tends to infinity as ; the finite preceding sum stays bounded. Thus every root of unity of -power order is a singularity. These roots are dense on the unit circle. An algebraic function has only finitely many possible branch points or poles, as seen from its defining polynomial's leading coefficient and discriminant. Hence cannot be algebraic over .
Suppose now that is algebraic, , and is algebraic. For a positive integer , a polynomial , nonzero and of degree at most in each variable, can be chosen so thatIndeed the first Taylor coefficients impose homogeneous integer equations on coefficients. There is a nonzero rational solution, which can be cleared to an integer one. Functional transcendence ensures is not identically zero.
Iterating the functional equation givesThus belongs to the fixed field and is nonzero for all sufficiently large , since a nonzero analytic has no sufficiently small nonzero zeros. Its analytic upper bound isChoose an integer making algebraic integers, let , and choose bounding every conjugate of and . Then and are algebraic integers. ThereforeFor every embedding of , the coefficient sum bounds the polynomial and givesTaking the norm of the nonzero integral yields a nonzero rational integer, of absolute value at least one. ConsequentlyOn the other hand the upper bound is , where . Choose so large that , possible because . Letting contradicts the two bounds. This proves, by the Mahler method, at every algebraic .
For the shorter rational-approximation argument at , truncate after and write with . The numerator is odd because its last summand is one and all previous summands are even, so this fraction is reduced. The tail satisfiesThe value is irrational: if it were , the positive difference from a truncation would be at least , contradicting the tail bound for large . If it were algebraic irrational and , choose . Eventually the displayed upper bound is below for infinitely many reduced fractions. The Roth theorem says that an algebraic irrational admits only finitely many such approximations. This contradiction proves transcendence directly. The argument does not cover , because its exponent is not strictly larger than two; the Mahler proof does cover that case.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 29 4 Solution Created 2026-10-03 Updated 2026-10-14
The Gelfond–Schneider theorem says that if is algebraic and is algebraic irrational, every number with is transcendental. Thus the statement includes every determination of the power, not merely a chosen principal branch.
Here is an auxiliary-function outline with the arithmetic and analytic steps specified. Assume were algebraic, and put , . For a large integer , choose degrees and , with constants large enough that . Apply Siegel lemma to imposeon a nonzero polynomial of these two degrees. Each field equation gives at most rational equations. Clearing denominators and bounding conjugates gives equation-coefficient logarithmic size ; the surplus of variables therefore permits coefficient height with
The entire function is nonzero: its polynomial-exponential terms have distinct exponents , and their independence follows by the differential-operator argument in question 2. Here . Its maximum modulus satisfies . The grid points are distinct because is irrational, and lie in a disk of radius .
Suppose the vanishing grid has been extended to , for some . Divide by the product of its known linear zero factors and use the maximum principle on a disk of radius , with large and fixed. At a point of the doubled grid, the quotient estimate givesif the value is nonzero. But this value equals the algebraic number . Clearing its denominators and taking its norm gives the opposite boundFor sufficiently large initial , the terms on the right are uniformly for every : and . Thus every doubled-grid value must be zero. Iterating doubles the grid indefinitely. This supplies quadratically many distinct zeros in disks of linearly growing radius, whereas Jensen's formula and the exponential-polynomial growth bound allow only zeros for a nonzero . The contradiction proves the theorem. This is the Schneider lattice proof of the Gelfond–Schneider theorem.
Now fix any logarithms of algebraic . Their values are nonzero. If were algebraic irrational, then would be algebraic, contradicting the theorem with base . HenceFor arbitrarily many logarithms the qualitative Baker theorem on algebraic linear combinations of logarithms states that logarithms of algebraic numbers which are linearly independent over remain independent over , even after adjoining one to the list. Equivalently a nonzero homogeneous algebraic-coefficient linear combination of such logarithms is transcendental. Rational relations are therefore the only source of homogeneous algebraic relations among the chosen logarithms.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 29 5 Solution Created 2026-10-03 Updated 2026-10-14
Use the following fixed-number form of a logarithmic estimate: for chosen logarithms of fixed nonzero algebraic numbers , a nonzero form with integer coefficients satisfies , for fixed positive constants . This follows from the Baker lower bound for a homogeneous linear form in logarithms.
By the Dirichlet unit theorem, write units as and , with finitely many roots of unity and fixed fundamental units. If the unit rank is zero, there are already only finitely many choices. Otherwise put . The real logarithmic embedding of the free unit group has full rank and lies in the product-formula hyperplane. Equivalence of norms in that finite-dimensional space shows that a unit with exponent size has some archimedean conjugate of modulus at most : a large positive logarithmic coordinate forces a comparably large negative one, and a large negative coordinate itself suffices.
Interchanging the two terms if necessary, choose such a conjugate for . At this embedding the equation makes with . For large define the logarithm near one. It is nonzero because , andOn fixed branches it isfor an integer . The bound on follows from summing the fixed imaginary parts and then reducing to the near-one branch. There are only finitely many possible embeddings and roots of unity, so the stated lower bound applies uniformly with coefficients . It contradicts the exponential upper bound when is large. Hence the exponents are bounded and in . This is the unit equation over a number field proof; “unit” here means an algebraic-integer unit, not an arbitrary nonzero field element.
For the Thue theorem, let be irreducible homogeneous of degree and let be fixed. In a splitting field , write with distinct roots. Choose a fixed integer so that each is integral and is a nonzero integer. For a solution the nonzero algebraic integers satisfy . Their principal ideals therefore divide a fixed ideal and have only finitely many possibilities. For each occurring principal ideal choose a generator , so with a unit.
Any three distinct roots give the identityDivide by the third term and absorb the finitely many generator ratios into the coefficients. This is a fixed-coefficient unit equation in and , so it has finitely many solutions for each generator choice. Thus has finitely many values. The relation fixes a rational direction whenever an integer solution exists; simply gives . On each such direction, for a primitive integer pair, and allows finitely many . This proves the desired finiteness. When , irreducibility excludes a nonzero rational root direction, leaving only .
The argument also proves finiteness for any binary form with at least three distinct projective roots: irreducibility was used only to guarantee distinct roots and to dispose of the zero-value case. A rational invertible change of variables can move every projective root away from infinity; after clearing its fixed denominators, the resulting pairs lie in an integer lattice and the same proof applies. This stronger nonzero-value version will apply to the binomial forms in question 6.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 29 6 Solution Created 2026-10-03 Updated 2026-10-14
The abc conjecture asserts that for every there is such that coprime positive integers satisfywhere the radical is the product of the distinct prime divisors.
For a primitive positive Fermat triple, the three integers are pairwise coprime. Apply the conjecture to . Since , . Taking yields . For and this simultaneously givesThus there are finitely many primitive triples and exponents. The primitivity restriction is essential to this abc argument: a nonprimitive triple is a common multiple of a primitive one, and the conjecture normalizes that factor away rather than bounding it. Consequently the intended finiteness conclusion counts primitive triples, or scaling classes. The literal unrestricted Fermat assertion is true for the independent reason that Fermat's last theorem gives no positive solutions for ; it does not follow from the displayed primitive height bound alone.
There is a genuine exception to the second printed assertion. If , then solves the equation for every ; for example gives an infinite family. The correct uniform finiteness statement excludes .
For that corrected statement put and . Since their difference is , . Apply abc to . Its radical is at most , and its largest term is at least . ThereforeWith , enlarge the fixed right side to . For the exponent is at least , soThis proves finiteness of all nonconstant-power solutions, without requiring coprime.
For an unconditional proof, the diagonal case satisfies and is elementary. If , the unequal-variable gap is at least , also bounding . In the remaining case interchange variables and coefficients, changing the sign of if necessary, to have andThe nonzero real logarithmic form satisfies . Once , , so . The two-logarithm Baker lower bound for a homogeneous linear form in logarithms, with the fixed height of and height of at most , givesHence because , and is bounded. The omitted case has bounded exponent and variables directly. For each of the finitely many exponents, has at least three distinct projective roots. The stronger nonzero-value Thue theorem argument from question 5 therefore gives finitely many pairs, whether or not that binomial form is irreducible. This establishes the exponent bound for a binomial power equation and the corrected finiteness statement with no unproved hypothesis. The constant-power family remains the unavoidable exception.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 31 2 i Solution Created 2026-10-03 Updated 2026-10-14
A useful strong form of the Hensel lemma is the following. Let be a complete discretely valued field, with valuation ring , normalized valuation , and . If satisfiesthen there is a unique root in the ball . When the assertion is immediate; otherwise the condition includes .
Here is a proof by Newton iteration over a valued field. Write and , and setSuppose and . The correction has valuation , so . Taylor expansion over cancels the linear term and givesThus the derivative still has valuation , and . Unless an exact root is reached earlier, the corrections tend to zero with exponentially increasing valuations. Completeness gives , and continuity gives and . For uniqueness, if are in this ball, polynomial expansion around givesThe second factor has valuation exactly and is nonzero, so two roots in the ball must be equal. In particular, a simple residue root lifts uniquely: and satisfy the hypothesis.
For the square-class group of a p-adic field, write every element as with . Multiplication by a square changes by an even integer, so valuation parity gives one independent factor .
For odd , a unit is a square if and only if its residue is a square in . Necessity follows by reduction; sufficiency applies the simple-root Hensel lemma to , whose derivative is a unit at a nonzero residue root. The cyclic group has square subgroup of index two. If is a unit with nonsquare residue, thenFor , every odd square is one modulo eight. Conversely, if , take and . Then , so the strong Hensel lemma gives a square root. Thus unit square classes are exactly their residues modulo eight. The classes and generate this group of order four independently, and valuation parity supplies the class . Hence
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 31 5 ii Solution Created 2026-10-03 Updated 2026-10-14
Put and . The ring of integers is , and the fundamental discriminant is . For a reduced positive definite binary quadratic form of discriminant , reduction givesThe coefficient is even; checking and , with the usual nonnegative sign choice at boundary equalities, leaves preciselyThe correspondence between proper quadratic forms and ideal classes therefore gives . All four classes equal their inverses, since inversion replaces by . HenceThe three nontrivial classes may be represented by the ramified prime ideals , and . They square to principal ideals and satisfy . None is principal: an integral generator of norm , or would require to equal that number, which is impossible. The relation then makes the three classes distinct, consistently with the four-form calculation.
ConsiderThe three rational square classes are independent, so . Their radical product is , so and ; the extension is abelian. To verify that it is unramified, rather than assuming that radical adjunctions are harmless at , use the conductor-discriminant formula. The seven quadratic subfields have fundamental discriminantsThe formula givesThe discriminant tower identity now givesThus the relative discriminant is the unit ideal and no finite prime ramifies. The base has no real places, so there is no infinite ramification to check. This unramified abelian degree-four extension has degree , and part (i) provesThis is the Hilbert class field of Q of square root minus thirty.
Next translate prime representation into an ideal class. For , we claimIf a representation exists, lies in and has . The integral ideal has norm , so it is a prime ideal . Its class is . Conversely, if , the product is principal, say . Since this ideal lies in , its generator has the form with integers . Taking norms gives , proving the reverse implication. This is prime representation via an ideal class, and it proves sufficiency as well as necessity.
Identify the required class in through the Artin map. We can use the explicit representation : has norm , so the prime above obtained from has class . Its Frobenius in the multiquadratic extension acts on the three radicals with signsTheir product is one, so this automorphism fixes . Because is abelian, for any unramified rational prime that splits in , the Frobenius at either prime of of norm is its rational Frobenius restricted to . The Artin isomorphism therefore makes the required class condition equivalent toConversely, these signs already imply splitting in , since their product is . No extra splitting condition is missing.
The supplementary law for , quadratic reciprocity for and , and then the Chinese remainder theorem turn these sign conditions intoTheir four simultaneous residue classes modulo are . Finally, is represented by , whereas and cannot be represented: gives a value at least , and gives twice a square. We have proved the complete criterion
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 40 1 Solution Created 2026-10-03 Updated 2026-10-14
Introduce nonnegative slack variables and write for the objective value. The initial simplex dictionary, recovered from the original PDF rather than the corrupted converted table, isFor this minimization convention, nonnegative objective coefficients give dual feasibility. The dual simplex algorithm repairs a negative basic value while retaining those nonnegative reduced costs. If the leaving row is , , an entering variable must have ; choose the smallest ratio of its objective coefficient to .
Choose to leave. Eligible columns are , with ratios and . Thus enters. Solving its row and substituting givesNow only has a negative basic value. Its only eligible entering column is , so pivot there, with leaving. The resulting dictionary isSetting the nonbasic variables to zero gives a basic feasible solution. The final objective row also proves for every feasible point, because its nonbasic variables are nonnegative. Hence the unique relaxed optimum is
For the integer program, all four original slack variables are integers whenever the decision variables are integers. The fractional row can be writtenThe Gomory fractional cut keeps the fractional parts of these coefficients: and . It therefore gives , or . Its validity can also be seen directly: the displayed row makes an odd nonnegative integer. In original variables this cut is .
Introduce the new integer-valued slack , with initial row . It is primal infeasible but retains dual feasibility, so one more dual-simplex pivot has leave and enter. Substitute to obtainAll basic values at are nonnegative integers, including . The objective row proves a lower bound of on every point satisfying the valid cut, hence on every integer-feasible point. It is attained atThe strictly positive nonbasic objective coefficients also show uniqueness. One Gomory cut and its reoptimization are sufficient.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 40 2 Solution Created 2026-10-03 Updated 2026-10-14
Assume and the integer coefficient bound . There are integers to record. Each signed integer in can be encoded in bits, so a fixed-width dense encoding needsbits, including the dimensions and bound. Its size is . This is the bit-input model used for polynomial time; an arithmetic-operation count alone would not suffice.
We first construct a rational feasibility certificate for integer inequalities. Choose a feasible point and an orthant containing it, adding coordinate inequalities of the form or . The intersection is nonempty. Starting at a point of , if the active constraint normals have rank less than , choose a nonzero direction annihilating them. A sufficiently short move in either direction remains feasible, since every inactive constraint has positive slack. At least one direction has a finite endpoint: a nonzero coordinate of can be oriented toward the orthant boundary. Move to the first constraint met along such a direction. Its normal does not annihilate , so it is independent of the previously active normals. Their rank strictly increases. In at most moves we obtain a point with independent active constraints.
At that point for an invertible integer matrix . Its rows are original constraint rows or signed coordinate rows, and has entries from or zero. All entries have absolute value at most . By Cramer's rule,where replaces column by . The Hadamard determinant inequality bounds both determinants by . The denominator is a nonzero integer. Hence each coordinate has the claimed representation with numerator and denominator bounded in absolute value by . The orthant argument is needed because itself may contain lines and have no vertex. If is allowed literally, all coefficients and right sides vanish, and is feasible; the printed fraction bound then needs replaced by , since a nonzero denominator cannot have absolute value at most zero. The bound just proved uses the customary positive coefficient bound.
Recording such fractions takes bits. A verifier checks that denominators are nonzero, changes their signs if needed, and verifies all inequalities by exact integer arithmetic after multiplying by positive denominators. The intermediate integers still have polynomial bit length. Thus a yes-instance has a polynomial-size, polynomial-time verifiable witness, and .
For optimization, let be rational with a finite binary encoding; clear its denominators to make it integer, which multiplies the objective by a positive constant and preserves its minimizers. All bit bounds below include the encoding length of . Let and .
A useful refinement of the preceding vertex argument is that if an objective is bounded below, a feasible point can be moved to an orthant vertex without increasing its objective. Choose the annihilating direction to have . If the inequality is strict, the forward feasible interval must have a finite endpoint, since otherwise the objective would be unbounded below. If , choose either finite endpoint supplied by the orthant. Rank increases as before. There are only finitely many such vertices across the finitely many orthants. Every feasible point therefore has one of these vertices with no larger objective; taking the least vertex value proves that a finite optimum is attained at one of them.
The Cramer representations at this optimum have one common denominator , of magnitude at most . Therefore its objective value has a representation with denominator at most and numerator at most . In particular . No enumeration of orthants or vertices is part of the algorithm; they provide only polynomial-bit bounds.
Here is an exact linear optimization from a feasibility oracle. First call the assumed ellipsoid method feasibility routine on ; if it is empty, report infeasibility. Otherwise query feasibility with the extra inequality . A yes answer proves unboundedness below, because any finite optimum would be at least ; an unbounded objective necessarily gives a yes answer. Thus the infeasible, unbounded and finite-optimum cases are distinguished using two feasibility calls.
In the finite case, maintain an infeasible lower threshold and a feasible upper threshold . Bisect the interval, querying each time. After polynomially many calls its length is less than , and lies in the resulting interval. Distinct reduced fractions with positive denominators at most differ by at least , so there is only one possible value. It can be recovered in polynomial time by continued fractions: for the midpoint , , where is the denominator of . Thus occurs among the continued-fraction convergents of . Compute those by the Euclidean algorithm and choose the unique fraction with denominator at most in the interval. If , use the final exact convergent. The Euclidean algorithm and all thresholds have polynomial bit length.
Even if the feasibility routine returns only a decision, an optimal point can be recovered without assuming a witness-producing oracle. Add and for all . This bounded optimal convex polytope is nonempty, since the optimal vertex above lies in it. Clear the denominator of and setAll vertex coordinates of this fixed convex polytope have denominators at most by the same determinant argument. Minimize , recover its exact minimum by feasibility bisection and rational reconstruction, then fix it; do the same for , and so on. Each restriction is an optimal face of the same original bounded convex polytope, so its vertices are original vertices. The single denominator bound therefore works at every step; repeated new precision bounds do not grow exponentially. After steps all coordinates are fixed to a feasible optimizer. There are polynomially many calls on polynomial-length rational instances, converted to integer inequalities by clearing denominators. Consequently linear optimization has a polynomial-time algorithm whenever linear feasibility does, with exact optimal value and optimizer, and correct reports of infeasibility or unboundedness.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 40 5 Solution Created 2026-10-03 Updated 2026-10-14
Label the two intermediate vertices . The four outer edges have capacity and the middle edge has capacity one. The cut separating from the other vertices has capacity , and the two paths and can each carry . Thus the maximum flow is .
A fast run of the Ford-Fulkerson algorithm chooses those two direct paths and augments by on each: it terminates in two augmentations. One augmentation cannot suffice, because every initial path has bottleneck at most .
For a run with augmentations, first choose and augment by one. The middle edge then has net flow from to . Its reverse residual capacity is , not one. Alternate crossing paths, next , then , and so on. Each of the next augmentations has bottleneck two. More explicitly, after crossing augmentations, , the total flow is , and the outer-edge flow totals on the pairs and are and in one order or the other. The middle net flow is . The next opposite crossing path uses the less-loaded outer pair and has reverse-middle capacity two. Until , its outer residual capacities are at least two.
After these augmentations, one outer pair is full and the other has one unit left. One final opposite crossing augmentation of one reaches . The total amounts are , then copies of , then , giving exactly augmentations. For the middle block is empty and this gives two augmentations as well. These are explicit requested path-choice histories. In an undirected network, need not be a bound on every possible history: for , choosing the crossing path, the two direct paths, and then the crossing path again gives four successive unit augmentations.
Direct and crossing flow augmentations, including reverse residual capacity two on the middle edge
. Details. For a general undirected network, let be the antisymmetric net flow. Feasibility gives , so the directed residual network has nonnegative capacities . For any cut with , , conservation at the internal vertices givesThus its outgoing residual cut capacity isThe subtracted flow value is the same for every cut. Taking the minimum and applying the max-flow min-cut theorem to the original and residual networks proves the residual maximum flow is the remaining optimality gap identity
Suppose now , and let consist of vertices reachable from through residual arcs of capacity at least . If , every outgoing arc from has capacity strictly below , since its head would otherwise be reachable. At most original undirected edges cross this cut, and each supplies exactly one outgoing directed arc. Hence , contradicting the residual minimum-cut value . Therefore , and a widest augmenting path has bottleneck at least . When , the current flow is already optimal and no such path is needed.
Let be the remaining residual maximum flow after augmentations of the modified rule, starting from zero flow. Its chosen widest path increases the flow by at least , soThis is the geometric convergence of widest-path augmentation. For , . Starting from zero with integer capacities keeps all flow values and residual optimality gaps integer. Thus makes and hence , giving termination in augmentations for . If , one positive integer augmentation suffices; if , none is required. A uniform statement is . With , a nonzero flow is also completed in one augmentation, consistent with the recurrence's zero contraction factor.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 54 1 Solution Created 2026-10-03 Updated 2026-10-14
Use target signature and a closed-string spatial coordinate . Write for the compact coordinate and for the noncompact coordinates. In conformal gauge, the wave equation factorizes, so every coordinate is a sum of a function of and a function of . The closed-string boundary conditions areThus the derivatives of each chiral part are periodic and have integer Fourier modes; only their worldsheet zero modes can produce the winding displacement. Integrating these Fourier series gives the closed-string mode expansionThe oscillator reality conditions are and similarly for the tilded modes. The coefficient of follows by integrating the canonical momentum density . Single-valued wavefunctions of the center coordinate have momentum , with . Equivalently, the compact chiral worldsheet zero modes are and , whereHere tildes denote the left-moving sector. This convention will also fix the sign in compact-circle closed-string level matching.
Choose a noncompact light-cone pair and impose light-cone gauge in string theory , with . The Virasoro constraints then solve for in terms of the transverse coordinates. For example, with , one has . Thus there are two independent transverse oscillator Fock spaces, including among the transverse coordinates. Quantization gives , and the same relation for the tilded oscillators, with the two sectors commuting. Lorentz consistency gives the critical dimension of the bosonic string and string intercept one in each sector. Accordinglycount 24 transverse oscillator species. The two zero-mode constraints give the lower-dimensional bosonic string mass spectrumTaking their difference and average yieldsEvery choice of transverse string oscillators and integer charges satisfying this closed-string level matching is a physical string state in light-cone gauge. The eliminated longitudinal oscillators do not supply additional polarizations.
To classify all massless states, positivity of the two compact terms implies . When the sum is two, masslessness forces , and closed-string level matching then forces . The states have polarizations. In 25 noncompact dimensions, their decomposition gives a graviton, a Kalb–Ramond field, a dilaton, two Abelian gauge vectors from the metric and two-form with one compact index, and the radius scalar field. Their physical polarization counts areThe first two numbers are the symmetric traceless second-rank tensor and antisymmetric second-rank tensor of the massless little group .
When , closed-string level matching requires . The compact contribution obeysand equality occurs precisely at . The charges have ; the charges have . Each charge has 24 polarizations supplied by its single excited sector. At a general radius these have
Finally, requires . The exceptional massless ground states of a bosonic circle occur atEach charge is a scalar field. These special radii must be included if “general radius” is to mean a complete classification, rather than only a generic radius. At a generic radius the massless spectrum is the neutral 576-state spectrum above; at exceptional radii one adds exactly the states just listed. The neutral ground state remains tachyonic.
The mapsends to and to . Reversing all right-moving compact string oscillators, , preserves their commutators and oscillator number; the left-moving oscillators are unchanged. Both the mass formula and compact-circle closed-string level matching are therefore unchanged, with a one-to-one map of the complete oscillator basis. This proves T-duality of the full spectrum, including winding, massive and tachyonic states.
At the self-dual circle the four single-oscillator charge families give new massless states. Each family decomposes into a 25-dimensional gauge vector with 23 polarizations and one scalar field. There are also four massless ground states, with charges and . Thus the massless spectrum at the bosonic self-dual circle hasThe gauge interpretation follows directly from the chiral compact-boson operators. With , the exponential has conformal weight . At the self-dual radius,have weight one and satisfy , , and . These are the level-one current relations; the right sector supplies another copy. Multiplying these currents by a noncompact oscillator produces six gauge vectors in total. The nine scalar string vertex operators form the representation, accounting for the radius scalar field and eight new scalar fields. The remaining neutral fields are the graviton, two-form and dilaton.
A radius deformation as a Higgs mechanism is the expectation value of the Cartan–Cartan scalar string vertex operator . Its stabilizer is , soThe four compact single-oscillator scalar field polarizations become longitudinal polarizations of the four massive vectors, exactly as in the Higgs mechanism. The other four extra scalar fields have masses or and need not remain massless; one pair becomes tachyonic on either side of the self-dual point. Together with the original bosonic tachyon, this means that the gauge-symmetry interpretation is formal and does not assert a stable bosonic-string vacuum.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 54 2 Solution Created 2026-10-03 Updated 2026-10-14
Take and split the coordinates into along the branes and transverse to them. In conformal gauge the wave equation permits a separated mode with . For Neumann boundary conditions at both ends, selects and integer . The zero-frequency solution is independent of , with a constant position and a term linear in time. Therefore the open-string mode expansion isThe canonical momentum density integrated over this interval is .
For Dirichlet boundary conditions, subtract the static interpolation between fixed endpoint positions and . The remaining field vanishes at both ends, selecting with integer and excluding a momentum worldsheet zero mode. The expansion isHere . There is no factor in the sine series with this reality convention: changing to reverses both the sine and the denominator. These are the integer-mode expansion with parallel D-brane endpoints; they are not the half-integer modes of a coordinate with a Neumann condition at one endpoint and a Dirichlet condition at the other.
The endpoints can move on -dimensional worldvolumes but are fixed in the transverse directions. Thus these are open strings attached to D-branes, or stretched between parallel D-branes at and . The tangential momenta describe propagation on the brane; the transverse positions describe its embedding. Let . The linear spatial worldsheet zero mode contributes to . Quantization with string intercept one givesThe first term is also the square of the classical stretched-string energy , since the string tension is .
For two coincident D3-branes, label the ends of an oriented open string by . The four endpoint combinations give Chan-Paton factors , which form the full algebra of matrices. Under a change of brane basis these transform as , the adjoint action of . At , the first oscillator level is massless. Its tangential polarization supplies a four-dimensional vector , while the 22 transverse polarizations supply real adjoint scalar fields . This is the bosonic D3-brane low-energy field content.
The endpoint matrices multiply in their boundary order in disk amplitudes. The difference between the two orders in the three-vector interaction gives the matrix commutator; the kinematic factor is the one-derivative Yang-Mills theory cubic vertex. Factorization and the vector gauge redundancy then supply the quartic interaction with the same commutator. Equivalently, the leading low-energy action is the dimensional reduction of 26-dimensional Yang-Mills theory, withFor Hermitian scalar fields the last displayed term corresponds to a nonnegative potential, because their commutators are anti-Hermitian. Higher-derivative terms are suppressed at energies well below . Ignoring the tachyon, the gauge sector is four-dimensional Yang-Mills theory, accompanied by 22 adjoint scalar fields. It is not pure Yang-Mills theory, nor the supersymmetric six-scalar D3-brane theory of a ten-dimensional superstring.
Separate the two branes and use the D-brane scalar-position normalizationA Yang-Mills gauge transformation preserves this expectation value only when it is diagonal if . Thus the unbroken group is . The scalar field kinetic term supplies a mass for the off-diagonal vectors, sinceSumming over gives , exactly the mass of the stretched string. The two diagonal gauge vectors remain massless. This identifies brane separation with an adjoint Higgs mechanism, rather than an explicit deletion of the off-diagonal strings.
For the ground state of an open string joining the two different branes, , so the bosonic stretched-string tachyon threshold isAt equality it is massless, and above it the stretched ground state has positive mass squared. The same-brane ground strings still have ; this calculation removes only the stretched-string instability, not the original instability of the bosonic branes.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 54 3 Solution Created 2026-10-03 Updated 2026-10-14
The Polyakov action has independent worldsheet metric and embedding fields . Varying the metric before imposing a gauge givesWorldsheet diffeomorphisms and Weyl transformations allow conformal gauge locally. The Weyl factor then cancels out of the classical action, leavingThese are free two-dimensional scalar fields, but the surviving metric equations requireEquivalently, and . Gauge fixing does not license dropping these Virasoro constraints.
For an ordinary open string, the boundary conditions relate the two chiral sectors. With , their independent Fourier generators areThe classical oscillator Poisson brackets give the classical Virasoro constraint algebraThus they are first-class constraints. In the quantum theory one applies normal ordering to the product and uses . The oscillator commutator givesFor example, for the extra vacuum term is . This exhibits the Virasoro central extension rather than concealing it in a classical constraint equation. The matter central charge is ; the worldsheet ghost fields have charge . Quantum consistency sets and the string intercept to one.
In old covariant string quantization the physical-state Virasoro conditions for an open string arePhysical string states are then identified modulo physical null string states. One does not impose both positive and negative generators as annihilation conditions: their central extension would obstruct that prescription. The resulting null-state quotient of a string agrees with the transverse light-cone spectrum at nonzero momentum.
At , the oscillator vacuum is a single spacetime scalar field with : the bosonic tachyon. At , write . The zero-mode equation gives , and gives . The null descendant identifies . This leaves 24 physical polarizations of a massless gauge vector.
At , use the level-two open-string polarization decompositionThe mass is . The oscillator commutators give all the nontrivial positive-mode conditions:Higher positive modes annihilate this level. To see the quotient explicitly, the 25 transverse-parameter null states , with , shiftThe additional level-two scalar Virasoro null state shiftsSubstitution into the two physical equations verifies the null-state conditions; the second residual is . Because is timelike, these null shifts span all components of , so choose a representative with . The physical conditions then say and . In the rest frame this is a traceless second-rank tensor in 25 spatial dimensions, with polarizations. The light-cone basis independently gives states and symmetric states . Hence
For the fermionic extension, an explicit convention prevents ambiguity in the signs. Keep worldsheet signature and useTake and the constant parameter to be real Grassmann-odd Majorana components, with . Put . Apart from the common factor , the combined Lagrangian isThe rigid transformations can be writtenor, in components,For the part, the bosonic variation is , while the fermionic variation is . Anticommuting the constant parameter past the fermion is essential in the second term. The first terms cancel. The other chiral component works in the same way, giving the chiral proof of rigid worldsheet supersymmetryThus the action is invariant off shell up to a boundary term. The transformation is a genuine supersymmetry: on its commutator for parameters is the translationOn the same translation follows using and ; the remaining cross terms are proportional to these Dirac equations. This is on-shell closure of rigid worldsheet supersymmetry. On a surface with boundary, compatible endpoint conditions must make the boundary flux vanish. On a compact worldsheet, a constant parameter must preserve the spin structure; the local identity alone does not make a constant transformation compatible with every antiperiodic sector.
The fermions contribute to the worldsheet stress-energy tensor and produce a fermionic superconformal current. In holomorphic normalization with ,The free-field contractions give and conformal weight for , where . Consequently the modes obey the N=1 super-Virasoro algebraDropping the central terms gives the classical graded constraint algebra. Integer gives the Ramond sector; half-integer gives the Neveu–Schwarz sector. In the displayed conformal-plane convention in the Ramond sector. Shifting to the Ramond vacuum-normal-ordered zero mode gives the usual Ramond supercurrent zero-mode square .
Rigid symmetry of matter already supplies these currents, but promoting their vanishing to new gauge constraints requires coupling to worldsheet supergravity and varying its worldsheet gravitino. In superconformal gauge one retains . The fermionic current constraints and their physical-state conditions extend the bosonic Virasoro conditions. The ghost charges are , so cancellation with gives the critical dimension of the RNS superstring ; the NS and Ramond intercepts are respectively and zero. This distinguishes the global supersymmetry established above from its locally gauged string completion.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 54 4 a Solution Created 2026-10-03 Updated 2026-10-14
Use the critical ten-dimensional RNS string and light-cone gauge in string theory, leaving eight transverse bosons and eight transverse fermions. The bosonic oscillators have integer . In the Neveu–Schwarz sector the fermionic oscillators have positive half-integer , while in the Ramond sector the fermionic oscillators have integer , including zero modes. Their anticommutators are and . The level and mass formulas areBefore projection the NS ground state is a tachyon of mass squared . Its oscillator tower describes spacetime bosons. The Ramond zero-mode Clifford algebra makes the Ramond vacuum a 16-dimensional spinor of , split into the two chiral eight-dimensional spinors. The Ramond tower describes spacetime fermions; there is no Ramond tachyon.
Choose the supersymmetric GSO projection. In the NS sector it keeps states with an odd number of fermionic creation operators, eliminating the zero-oscillator tachyon. In the Ramond sector it fixes the combined parity of the zero-mode chirality and the nonzero-mode fermion number. Thus the Ramond vacuum retains one chirality; adding an odd number of nonzero-mode fermions requires the opposite zero-mode chirality. The projected towers both have . Here the counts refer to oscillator polarizations for a single endpoint multiplicity; any common Chan-Paton multiplicity multiplies both counts.
At the first retained mass level, , the NS states are for , furnishing the eight polarizations of the ten-dimensional gauge vector. The Ramond ground state is one chiral spinor with eight physical polarizations. HenceThese form the massless supersymmetric vector multiplet.
At the next mass level, , the NS level is . The odd-fermion condition leaves exactlyTheir counts are , and . Anticommutation requires distinct indices in the third family. There are no other partitions of with odd fermion number, so these are all 128 bosons. They assemble into the massive little-group representations of dimensions 44 and 84: a traceless symmetric two-tensor and a three-form.
At Ramond level one, the only possibilities are and . The spinors and each have eight components and have opposite zero-mode chirality because the fermionic oscillator reverses the GSO parity. Consequently there are fermions. They form a gamma-traceless vector-spinor of the massive little group: a vector-spinor has components and its gamma trace removes 16. Therefore the first massive level of the open RNS string hasThis is the open-string mass normalization; the same chiral oscillator count used in a closed string would correspond to .
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 6 1 ii Solution Created 2026-10-03 Updated 2026-10-14
For each nonzero integer tuple , putIf its first coordinates are all zero, then and is empty. Otherwise it is a closed proper affine hyperplane. It has empty interior: from any of its points, an arbitrarily small displacement in the nonzero normal direction leaves it. Thus every is nowhere dense.
There are countably many integer tuples, and is complete. The Baire category theorem therefore makes the complement of their union dense and nonempty. Choosing any point there givesEquivalently, are linearly independent over : multiplying a rational relation by a common denominator produces just such an integer relation. This is an instance of Baire avoidance of countably many affine hyperplanes.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 66 3 iii Solution Created 2026-10-03 Updated 2026-10-14
A norm estimate controls the worst possible refined differences for every choice of the initial controls. Submultiplicativity turns a length- contraction into a bound for arbitrary long products, so it proves a certain number of continuous derivatives. Its absolute values can lose cancellations; failure of the estimate is inconclusive. It therefore gives a lower bound on smoothness.
Conversely, an observable eigenmode of a repeated local product exhibits a particular sequence of shrinking neighborhoods with inadequate decay. General-position controls have a nonzero coefficient in that mode, so greater derivative continuity is impossible. Special symmetric or polynomial data may suppress the bad mode; this is why the general-position qualification matters. The obstruction gives an upper bound on smoothness, while failure to find an obstruction proves nothing. A lower bound on spectral growth becomes an upper bound on smoothness because large surviving differences correspond to rough behavior.
For example, the binary Cardinal cubic B-spline subdivision mask has symbol , up to an irrelevant index shift. At derivative order , the first-difference subdivision mask is , whose maximum parity sum is : the limit is at least . At , , and the surviving difference mode does not decay. For generic controls the third derivative is piecewise constant with nonzero jumps, so the subdivision curve is not . Here the lower and upper tests determine the exact integer continuity, but they need not coincide for an arbitrary subdivision mask. Stability, sum rules and borderline modes must be handled explicitly before interpreting any numerical estimate as a continuity level.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 66 3 i Solution Created 2026-10-03 Updated 2026-10-14
Fix the indexing conventionwhere the subdivision arity is an integer. A change of the initial control can influence only indices after one step, where . After steps the possible descendant indices areLet be the smallest and largest active subdivision mask indices. Dividing by gives the enclosureTherefore the support of a stationary subdivision scheme, in initial control-grid units, is enclosed byFor the stated symmetric subdivision mask with active extremes , the width is . For a nonzero compactly supported basic limit function , this is an exact endpoint calculation: its refinement equation is . If is its right support endpoint, only the largest active subdivision mask index can contribute sufficiently close to the rightmost point of this sum; all smaller indices have argument beyond . Hence , giving . The left endpoint follows in the same way. This argument also excludes cancellation at an extreme for signed subdivision masks. The support for initial control is translated by . If the nominal subdivision mask was padded by zero coefficients, use its actual extremes; and a limiting subdivision curve has to exist before its support is meaningful. This calculation describes the entire possible influence region, rather than the width of a single refinement stencil on its finer grid.
