Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 104 5 d Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For and , defineThe normal form theorem for a free product giveswhere map to . To see injectivity, expand an alternating word in and powers of . The conjugating factors commute with the lattice syllables, so each intervening nonidentity lattice syllable stays nonidentity in the expanded free-product normal form.
Its intersection with is the free group with basisThis follows by moving all factors to the right; the zero-exponent lattice remainder characterizes membership in the kernel.
The required isomorphisms are specified on the three generators byandEach source and target has the same presentation , and each displayed assignment identifies its three abstract generators. Hence these are genuine isomorphisms, not merely maps of generating sets.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 104 5 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
The base free product for the group encoding of a modular machine isThe letters generate the first factor, and generates the second. Let be the kernel of the group homomorphism that kills . Thenis a free group with this displayed free basis of a group. Indeed every word in can be rewritten as a product of such conjugates followed by an element of , so they generate the kernel. A freely reduced product of these conjugates is nontrivial by the normal form theorem for a free product: after combining adjacent occurrences of the same conjugate, different successive indices give a nonzero intervening -syllable. Thus there is no relation among the proposed basis elements.
For clarity, a modular machine of modulus has at most one instruction for each residue pair , with and . Its right and left transitions are respectivelyIts halting set at a designated terminal configuration consists of the nonnegative pairs whose forward computation reaches , including itself. These formulas explain the exponents in the associated-subgroup maps below.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 104 5 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Use a reduced sequence in an HNN extension for . By repeatedly conjugating a prefix to the other end and reducing any resulting pinch, one obtains a cyclically reduced sequence in an HNN extension: either an element of the base group, or a sequence of positive stable-letter length with no pinch even across its cyclic junction. For example, after conjugating away the initial base coefficient, write it as . A pinch across the junction can occur only if and . Moving the first stable letter to the end then exposes that pinch and reduces the stable-letter length by two. Iteration must terminate.
If the resulting cyclically reduced sequence has , every positive power remains reduced and has stable-letter length equal to that power times . By Britton's lemma, none is the identity. Thus a finite-order element must be conjugate into the base group . Since embeds in the HNN extension, the order of a base-group element is unchanged, and conjugation also preserves order. ThereforeThe argument also applies to several stable letters: cyclic pinches must involve a stable letter and its own inverse.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 104 5 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
In a direct product of groups, . Thus a finite order for makes both coordinate orders finite. Conversely, if their orders are and , the least positive exponent annihilating both is their least common multiple. Hencewhen both orders are finite; if either coordinate has infinite order, so does .
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 104 4 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
If the Turing machine halts on , follow its computation from . A transition at an already represented cell is one of the corresponding relations. At a boundary, first insert the required blank using a padding relation. Thus the computation gives a finite equality derivation to . Replace by , erase the symbols of using , and erase both boundary markers. This proves in the semigroup.
For the converse, equality in a presented semigroup means a finite sequence of contextual replacements using defining relations in either direction. In any derivation from to , consider the first occurrence of the special symbol . Before it occurs, the erasure relations cannot be used in either direction. Each word therefore still has exactly two markers , exactly one state letter, and the form . Both directions of a transition relation join configurations linked by one actual machine step; both directions of a boundary-padding relation merely change how much blank tape is represented.
The first occurrence of must come from in the forward direction. Hence the initial configuration is connected, by transitions in either direction and harmless padding, to a configuration in state . For a deterministic Turing machine, the property of eventually reaching is invariant along each transition edge: if is a step, then halts if and only if halts, since that step is the unique next step of and is not already in the halting state. The same property is unchanged by padding. A finite path of these edges to therefore shows that the initial configuration halts.
ConsequentlyThe invariance argument is necessary because equality in a semigroup presentation allows reversed transitions as well as forward computation steps.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 104 4 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
We give a finite semigroup presentation using the convention that is blank, the tape is unbounded in both directions, and a transition writes and moves in direction . The Turing machine is deterministic, and the halting state has no outgoing transition. A finite configuration is encoded bywith the head scanning the first symbol of ; if is empty, it scans an implicit blank. Unrepresented cells beyond the boundary markers are blank. An additional generator records completed halting and erasure.
The generators of the semigroup are . Its relations have the following finite families. For every right-moving transition, includeFor every left-moving transition and every tape symbol , includeIf stationary moves are part of the chosen machine model, include for each such move. Include the boundary-padding relations, for every state ,They supply a blank immediately to the left of the head when needed, or at the right boundary when the current scanned cell was implicit. Finally includeWriting for this displayed list, the answer is the explicit finite semigroup presentationAll relations are between nonempty words; no group inverses or empty-word generator are used. The transition families are finite because the transition table and alphabet are finite, and the padding and erasure families are visibly finite. The declared head convention determines which side of a tape symbol carries a state letter.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 104 3 iv Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Expand the commutator:Its possible pinches have intervening coefficients , , and . For a pinch the coefficient must lie in ; neither nor does. For the pinch it must lie in , and again does not. Here embeds by the normal form theorem for an HNN extension, so these divisibility tests are valid inside .
The word is a reduced sequence in an HNN extension with four stable letters. Britton's lemma givesThus is a finitely presented non-Hopfian group: it has a surjective endomorphism which is not injective. This group is the Baumslag-Solitar group .
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 104 3 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For the commutator , the image isThe last equality holds because two powers of the same element commute.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 104 3 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 104 3 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Substitution sends the defining relation toThus the assignment respects the relator and extends to a group homomorphism .
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 104 1 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Eliminate using . The remaining relation becomes , which follows from . These Tietze transformations giveBoth factors are nontrivial, so this is a nontrivial free product. Conversely, in the definition satisfies both conjugation relations, confirming that eliminating loses no relation.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 104 1 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
In a nontrivial free product, nonidentity elements from different factors satisfy , since these are distinct alternating normal forms. Such a group is not an abelian group, whereas the free abelian group is abelian.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 104 1 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
If and belong to different factors, the powers have distinct normal forms of length . Every nontrivial free product is therefore an infinite group, whereas the alternating group is a finite group of order .
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 103 6 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
A generalised permutation is a finite multiset of pairs from two ordered alphabets, written as a two-row array, or biword. It may equivalently be specified by a finite-support matrix of nonnegative integer multiplicities . The condition that no column is repeated means : each ordered pair occurs at most once. It does not forbid repeated entries in either individual row.
For this class use the dual Robinson–Schensted–Knuth correspondence. Order the columns by nondecreasing top entry , and by strictly decreasing bottom entry when the top entries agree. Insert the bottom entries in that order by ordinary semistandard row insertion, which bumps the leftmost entry strictly greater than the incoming entry. Record the corresponding top entry in each newly created cell. Let be the insertion tableau and the recording tableau.
Ordinary row insertion permits repeated entries, preserving weak increase along rows and strict increase down columns; therefore is a semistandard Young tableau. The recording entries are inserted in nondecreasing order, so weakly increases along both rows and columns before considering strictness. Within one block of equal top entries, the bottom entries are strictly decreasing. The standard row-bumping comparison lemma says that a later, smaller input creates a new box strictly below the box created by the preceding input. Thus the boxes carrying one repeated top entry form a vertical strip, with at most one in each row. Consequently has strictly increasing rows and weakly increasing columns, so is semistandard.
Knuth's generalized insertion theorem, in this dual ordering, makes the map a bijection between finite - matrices and these pairs. Its reverse description is also transparent: remove the largest recording entry, choosing its lowest box when it repeats, and reverse row insertion in . Repeating recovers bottom entries in the reverse of the specified ordering. Equal top entries recover distinct bottom entries, which is exactly the no-repeated-column condition. ThusThe descending tie rule matters; the usual ascending tie rule would instead give two ordinary Semistandard Young tableaux.
Finally, the type of a tableau means its entry-multiplicity vector. Row insertion rearranges and bumps entries without changing their multiplicities. HenceThus the bottom-row multiplicities of the generalised permutation give the type of , while the top-row multiplicities give the type of ; transposing does not change its type.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 103 5 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Assume . The standard Young tableaux of shape are , for : the sole second-row entry is , and the first row isThis lists all of them, since must occupy the first box and the rest of the first row is forced to increase. Their contents areWrite . The only nontrivial adjacent swaps exchange the lower entry with or . Substituting the content differences into Young orthogonal form yields all generator actions:In the first line at , the square-root coefficient is zero and the action is , so no vector is needed. The second line is used only when , since the generator does not exist.
The corresponding Specht module is the sum-zero standard representation of the symmetric group:A concrete orthonormal realization isPermuting coordinates gives exactly the actions above, linking this orthogonal tableau basis with the Gelfand–Tsetlin basis found in Question 1. Here the printed are the adjacent Coxeter generators, rather than products of all generators.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 103 5 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For , there is exactly one standard Young tableau, the column with entries from top to bottom. Its content vector of a standard Young tableau isEvery adjacent distance is , so Young orthogonal form gives for every . Thereforethe sign representation.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 103 5 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For a standard Young tableau , let when its entry lies in cell . Its content vector of a standard Young tableau is . We use the following sign convention for axial distance in a Young tableau:This is the axial distance from to . In particular, write for the adjacent transposition .
Here is Young orthogonal form, with one orthonormal basis vector for each standard Young tableau of a fixed shape:If is not standard, omit that term. In this case occupy adjacent cells in one row or column, so or , respectively, and the scalar action is or . On a standard pair , and the matrix isThis is a real orthogonal involution.
To prove the formula, explicitly use the permitted Young seminormal form theorem: the Specht module has a tableau basis whose vectors are joint eigenvectors of the Young–Jucys–Murphy elements, and whose actions, on an admissible pair oriented so that tableau length increases from to , areNonadmissible swaps have the scalar actions just described. The theorem supplies these as one globally consistent representation, not as independently chosen two-dimensional blocks.
Average a positive definite Hermitian inner product over . Distinct tableau lines are orthogonal because their commuting self-adjoint Young–Jucys–Murphy elements have distinct joint weights. Also is self-adjoint, so the two seminormal equations implyUpon setting , the coefficient from to becomes ; the reverse coefficient is the same. All phases are consistent because the seminormal basis was global, and the group relations remain true under this change of basis. This proves Young orthogonal form.
For , there is exactly one standard Young tableau, the row . Its content vector of a standard Young tableau isEvery adjacent distance is , so for every . Thus is the trivial representation.
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





