Topics (218k) Articles (224k) Users (307) Discussions (237) Comments (383) Files (764) New article
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 125 4 b Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
If is finitely generated, the structure theorem for finitely generated modules over a principal ideal domain immediately makes finite.
Conversely, first replace the given height by a quadratic one. SetCondition (ii) makes this limit converge and givesThus still has finite bounded subsets. Condition (i) also gives a global lower bound for , so . Applying condition (iii) to , dividing by and passing to the limit gives one direction of the parallelogram identity. Applying the same inequality to and , and using , gives the reverse direction. Henceand induction yields for every integer .
Now suppose is finite and choose representatives . Put . For any , write . Nonnegativity and the parallelogram identity giveso, since ,Repeated division modulo therefore reaches the finite set . Reversing the recursion expresses every element of using and the finitely many . This is the height descent lemma, and proves
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 125 4 a Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
The natural maphas finite image by hypothesis. It remains to bound its kernel. If becomes for , thenis a one-cocycle for . Changing by an -torsion point changes this cocycle by a coboundary, producing a well-defined map from the kernel toIf its cohomology class is zero, subtracting the corresponding torsion point from makes Galois fixed, so . The map is therefore injective. Both and are finite, so this group cohomology set is finite. A finite kernel and finite image give
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 125 3 c Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
An integral Weierstrass equation has good reduction outside the finitely many primes dividing its nonzero discriminant. This proves finiteness of the set of bad primes. To prove finiteness of rational torsion, choose two distinct good primes. The reduction of torsion points on an elliptic curve injects each primary component at a good prime of different residue characteristic, so the two finite reduced point groups bound every primary component of .
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 125 3 b Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
For a minimal integral Weierstrass equation, let be the reduced cubic and its nonsingular points, with their induced group law. Define the filtration of elliptic-curve points over a local field byandThe parameter identifies with the formal group of an elliptic curve on . Part (a) therefore gives . Reduction restricts to the exact sequenceIts restriction to -torsion has trivial kernel, yielding the injection
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 125 3 a Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
A one-dimensional commutative formal group law over is a power series satisfyingA morphism is a series satisfyingIf , the invertible morphism criterion for formal group laws says that is an isomorphism whenever . Indeed, recursive coefficient comparison constructs a unique compositional inverse ; applying to the morphism identity shows that is a morphism in the opposite direction.
The multiplication series hasSince , its linear coefficient is a unit, so is an automorphism of the group . Its kernel is therefore zero, and
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 125 2 b Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
For , direct counting givesNeither group order is divisible by , so neither group contains a point of order .
At the Frobenius trace is zero. The elliptic-curve point count over a finite field has trace recurrenceFor every , this order is congruent to one modulo . Consequently has no point of order for any .
At , the trace is . On , Frobenius has characteristic polynomialIts discriminant is , a nonsquare in , so its two distinct eigenvalues lie in . Their orders divide , whence on . Thus all of is rational over , and in particular a point of order exists over some extension with .
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 125 2 a Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
The Hasse theorem for elliptic curves states that, for an elliptic curve over ,Let be the Frobenius isogeny of an elliptic curve and put . The fixed points of are , and is separable, soHence the trace of an elliptic-curve endomorphism iswhile .
The degree on is a nonnegative quadratic form. Polarization and the identities for the dual isogeny give, for integers ,If , this real binary quadratic form is indefinite. An open cone on which it is negative contains a nonzero rational point and therefore a nonzero integer point, contradicting nonnegativity of isogeny degree. Thus , which is exactly the claimed inequality.
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 125 1 a Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
Let be a smooth plane cubic whose identity is an inflection point. A line through and , using the tangent when , has a third intersection counted with multiplicity. The chord-and-tangent group law defines by drawing the line through and and taking its third intersection.
The clean verification of the group axioms uses divisors. The line at infinity meets a Weierstrass cubic in , so three collinear points satisfyConsequently the mapsends the chord-and-tangent construction to addition of divisor classes. The principal divisor criterion on an elliptic curve shows that this map is bijective. Associativity and commutativity therefore follow from the abelian group law on . The tangent convention handles repeated intersections, represents the zero class, and the third point on the line through and represents the inverse of . Hence all group axioms hold.
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 124 4 iii Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
We give the Agrawal–Biswas primality test, which has one-sided error. Small inputs and perfect powers can first be recognized deterministically. For every remaining integer , put and choose a uniformly random monic polynomialUsing repeated squaring in the quotient ring , test the identityThis takes time polynomial in because every intermediate polynomial has degree below .
If is prime, the intermediate binomial coefficients are divisible by , so the identity always holds. Now suppose that is composite and is not a prime power. Choose a prime divisor and write with and . Over ,because an intermediate coefficient equal to is nonzero modulo . Henceis a nonzero polynomial of degree below over .
Reduction of random modulo is uniform among the monic degree- polynomials. The polynomial has at most distinct monic irreducible factors of degree . On the other hand, the number of monic irreducibles of degree obeys the standard lower boundWhenever is one of these irreducibles but does not divide , the tested congruence fails. Thus one trial detects compositeness with probability at leastafter the finitely many small are handled directly. Repeating times makes the probability of missing a composite less than , while a prime is never rejected. Therefore compositeness is in RP, and primality testing is in
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 124 4 ii Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
First suppose . Run the RP algorithm for and the RP algorithm for its complement with fresh random bits. If the first accepts, output one; if the second accepts, output zero; otherwise repeat. Neither output can be wrong, and on every input the appropriate algorithm accepts in each round with probability at least . The number of rounds is dominated by a geometric distribution of mean two, so this is an always-correct algorithm with polynomial expected running time.
Conversely, let be always correct when it halts and have expected running time at most . Run it for steps. Markov inequality givesAccept exactly when halts and outputs one; this is an RP algorithm for . Accepting exactly when it halts and outputs zero is an RP algorithm for the complement. Thereforeis equivalent to zero-error expected polynomial time.
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 124 4 i Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
A language belongs to RP when a polynomial-time randomized algorithm rejects every and accepts every with probability at least .
Amplify the algorithm on length- inputs with independent repetitions, accepting if any repetition accepts. Its error on each positive input is at most , while it still never accepts a negative input. Choose all random bits for all repetitions in advance. By the union bound, the probability that this one fixed choice fails on at least one of the at most positive strings is at mostThus some random string works simultaneously for every input of length . Hardwire that string into the polynomial-time computation and compile it into a Boolean circuit. The resulting polynomial-size circuit family decides , proving
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 124 3 iii Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
Yes. The usual collapse relativizes because every machine involved receives the same oracle . Induct on the levels of the polynomial hierarchy. The hypothesis givesIf the preceding level is contained in , then its oracle queries can be simulated in polynomial time with oracle . A nondeterministic machine for the next existential level is therefore only an machine, hence a machine by hypothesis. Complements give the corresponding universal level. The induction yields
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 124 3 ii Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
This is the Karp–Lipton theorem. It is enough to place inside . Let , so for a polynomial-time predicate and polynomially bounded strings,The NP search problem that receives and seeks such a has, by part (i), a polynomial-size circuit family producing a valid witness whenever one exists. For each input length there is therefore a polynomial-size circuit such that, for every relevant , existence of a witness implies .
Consequentlywhere the existentially guessed circuit description has polynomial length and evaluation of is polynomial time. This is a description. Hence ; complementation gives the reverse inclusion, and merging adjacent equal quantifier blocks collapses every higher level. Thus the polynomial hierarchy satisfies
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 124 3 i Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
Let be a polynomial-time verifier for , with witnesses of length . Consider the prefix languageThis language lies in NP, so the assumption supplies a polynomial-size circuit family deciding .
Apply the usual search-to-decision reduction. Starting with the empty prefix, append zero if the circuit says that some accepting witness has that extended prefix; otherwise append one. Repeat for positions. Composing the polynomially many copies of the decision circuit produces a polynomial-size circuit . Whenever , at least one accepting extension exists at every step, so the final string satisfiesOn negative inputs the output may be arbitrary, as required.
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 124 2 iii Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
Membership follows from . A directed graph is not strongly connected exactly when there is a pair for which is not reachable from . Guessing the pair and using the NL procedure for non-reachability puts non-strong-connectivity in NL, hence strong connectivity is in co-NL and therefore in NL.
For NL-hardness, reduce directed reachability. Given , form by retaining all edges of , adding for every vertex , and adding for every vertex . If is reachable from in , then any reaches any in alongConversely, if is strongly connected then reaches . A simple -to- path cannot use an added edge out of before arriving at , and every added edge into merely returns the path to its starting vertex; deleting the resulting cycle leaves an -to- path made from edges of . The construction is computable in logarithmic space, so deciding strong connectivity is
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 124 2 ii Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
It suffices to recognize non-reachability in NL, since directed reachability is NL-complete. Let be the number of vertices reachable from by a directed path of length at most . Clearly . The inductive counting argument computes and verifies from using logarithmic space.
For each vertex , reachability within steps has an NL certificate: guess such a path. Non-reachability within steps can be certified relative to the trusted value by enumerating vertices , exhibiting paths of length at most to exactly distinct vertices, and checking that none is or has an edge to . Because there are exactly reachable vertices, this list cannot omit a reachable predecessor. Counters, vertex names and one guessed path need only logarithmic space. Repeating this check in a fixed vertex order and counting the positive cases produces the exact .
After rounds, the procedure knows the number of all vertices reachable from . It accepts non-reachability of after certifying, by the same complete enumeration, that is absent. Thus the complement of directed reachability belongs to NL. Since every NL language reduces to reachability and log-space reductions are closed under complementation, this proves the Immerman–Szelepcsényi theorem
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact





