Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 4

For an odd prime $p$, the Legendre symbol isFor distinct odd primes $p$ and $q$, quadratic reciprocity states that

The discriminant isThe discriminant criterion for a quadratic congruence modulo an odd prime therefore says that, for $p\ne 3$, a solution exists exactly whenThe quadratic character of minus three giveswhich equals $1$ precisely for $p\equiv 1(\mathrm{mod}3)$. When $p=3$, the polynomial isso it also has a solution. Hence

The classsatisfies $X^3=-1$ for every prime. Thus a solution exists for every odd prime $p$, regardless of its residue class modulo $3$.

The cube roots of minus one modulo an odd prime are controlled byFor $p\ne 3$, the quadratic factor has roots exactly when its discriminant $-3$ is a square, namely when $p\equiv 1(\mathrm{mod}3)$. In that case there are three distinct roots; when $p\equiv 2(\mathrm{mod}3)$, only $X=-1$ remains. For $p=3$,so $X=-1$ is again the unique root. Therefore

Starting with $x_0=x>0$, the continued-fraction algorithm setsunless $x_n$ is already an integer. This gives

Every finite continued fraction is rational, since it is built from integers by finitely many additions and reciprocals. Conversely, if $x=p/q$ is rational in lowest terms, thenWhen $r\ne 0$, the next complete quotient is $q/r$. Thus each step is an application of the Euclidean algorithm and replaces the denominator by a smaller nonnegative remainder. The process must terminate. This proves the termination criterion for a simple continued fraction.

For $x=\sqrt{3}$,andFinally,so the complete quotients repeat. Hence the continued fraction of the square root of three is

A binary linear-feedback shift register of degree $d$ has a state
$(s_n,\dots ,s_{n+d-1})\in {\mathbb{F}}_2^d$ and recurrenceIts feedback polynomial is

There are $2^d$ states, and the zero state is fixed. A nonzero periodic orbit therefore visits at most the other $2^d-1$ states, proving the period bound for a linear-feedback shift register.

For a maximal orbit with $d>1$, the all-one state cannot itself be fixed. From that state the incoming bit is $a_0+\cdots +a_{d-1}$ in ${\mathbb{F}}_2$. If an odd number of the $a_i$ were one, the incoming bit would be one and the all-one state would be fixed. Hence an even number of the $a_i$ are one; including the leading coefficient, the feedback polynomial has an odd number of nonzero coefficients. This is the feedback-polynomial parity condition for maximal period.

The given prefix has seven consecutive zeros followed by a one. Any register of degree at most seven would therefore enter the all-zero state before producing the final one, which is impossible. Degree eight is attained bywith initial state $10000000$. It produces the next bit $1$ and has feedback polynomialThus this is the minimal linear-feedback shift register for the prefix 100000001.

A variable-based grammar is a tuplewhere $\Sigma$ and $V$ are disjoint finite sets of terminals and variables, $S\in V$, and each production $\alpha \to \beta$ has $\alpha ,\beta \in (\Sigma \cup V{)}^{\ast }$ with at least one variable in $\alpha$.

Choose a new start variable $S_0\notin V\cup V^{\prime }$. The concatenation grammar isIndeed, its derivations first produce a word from $G$ and a word from $G^{\prime }$ in their original order, so $L(H)=L(G)L(G^{\prime })$.

For the regular concatenation grammar, letThen defineIf $G$ and $G^{\prime }$ are regular, every nonterminal rule retained from $P$ is right-linear, and each replaced terminal rule is also right-linear. A regular derivation in $G$ uses exactly one terminal rule, at its final step; the replacement transfers control to $S^{\prime }$, after which a word of $L(G^{\prime })$ is generated. Hence

LetBoth are regular grammars and their variable sets are disjoint. Their ordinary concatenation grammar adds a new ruleThis rule has two variables on its right-hand side, so it is not right-linear. Thus this is an explicit instance in which the concatenation grammar need not be regular.

TakeandThese are variable based and have disjoint variable sets. They satisfyIn $H^{\mathrm{reg}}$, however, both terminal productions of $G$ are replaced:Consequently its only terminal derivation issoThis realizes the failure of the regular concatenation construction for a nonregular grammar: two different terminal productions introduce two copies of $T$.

For a model with $k$ fitted parameters, the Akaike information criterion iswhere $\ell$ is the log-likelihood evaluated at the maximum-likelihood estimate.

In the normal linear model with known ${\sigma }^2$,The maximum-likelihood estimator is the ordinary least-squares estimator, with fitted mean $\hat{\mu }=HY$, whereSince only the $p$ components of $\beta$ are fitted,After multiplying by ${\sigma }^2$ and discarding the model-independent constant, this is exactly Mallows Cp:

To compare it with prediction error, write $Y=\mu +\epsilon$ and $Y^{\ast }=\mu +{\epsilon }^{\ast }$, where $\mu =X\beta$, the two errors are independent, and both have covariance ${\sigma }^{2}I$. Since $H\mu =\mu$, $H$ is an orthogonal projection of rank $p$, andThe cross term has zero expectation, soOn the other hand,Therefore the unbiased prediction-error identity for ordinary least squares gives

The population map isA positive equilibrium satisfiesand henceIt is strictly positive exactly whenThis is the nonzero equilibrium of the survival-augmented Ricker map.

Differentiate the map:At the positive equilibrium, $k{e}^{-\lambda x_{\ast }}=1-r$, soThe fixed point stability for an iteration requires $|g^{\prime }(x_{\ast })|<1$. Existence already makes the logarithm positive, so the upper inequality is automatic. The lower inequality givesCombining it with existence yields the stability interval of the survival-augmented Ricker equilibrium:

The Laplace integral method for a differential equation seeksDifferentiating under the integral and substituting intogivesSince $z{e}^{zt}={\partial }_t{e}^{zt}$, integration by parts yieldsIt is therefore enough to choose $f$ and $C$ so thatand the boundary term vanishes. Solving the first-order equation on $-1<t<1$ givesTake $C$ to be the interval $[-1,1]$. Although $f$ has integrable endpoint singularities,vanishes at both endpoints, so the boundary term is zero. ThusAt $z=0$, substituting $t=\sin \theta$ givesThe normalization $y(0)=1$ therefore sets $K=1/\pi$. By the defining regularity and normalization of the modified Bessel function, this proves the real integral representation of the modified Bessel function I0:

The Jacobi identity for the Poisson bracket isFor quantities with no explicit time dependence,If $F$ and $G$ are conserved, the first two terms of the Jacobi identity vanish. Henceor, by antisymmetry,Thus the poisson bracket of conserved quantities is itself conserved.

For $Q=\lambda q$ and $P=\lambda p$,The one-dimensional criterion for a canonical transformation therefore givesFor either value, the type-two generating function for a canonical transformationworks, because $p=S_q=\lambda P$ and $Q=S_P=\lambda q$; when ${\lambda }^2=1$, the first equation is equivalent to $P=\lambda p$. For every other $\lambda$, the Poisson bracket is not one and the map is not canonical.

For $Q=q$ and $P=\lambda p$,Thus the map is canonical only forAt that value it is the identity and is generated by

For $Q=p$ and $P=\lambda q$,The map is therefore canonical only forThen $Q=p$ and $P=-q$. The type-one generating function for a canonical transformationgivesas required.

The potential slow-roll parameter isFrom the slow-roll approximation,ThereforeThus $ϵ\ll 1$ implies ${\dot{\varphi }}^2\ll V$, consistently with potential-energy domination.

The same equations giveOn the branch $V^{\prime }/V>0$, the definition of $ϵ$ turns this into

By definition,Using $dt=d\varphi /\dot{\varphi }$ and the result of part (a),Reversing the limits yields the slow-roll e-fold count

For the natural inflation potential, write $x=\varphi /f$. Thenand the half-angle identity givesTherefore, on the stated rolling branch,

Substitution into part (b) givesSincethe e-fold count for the natural-inflation cosine potential is

Apply a Hadamard gate to Alice's qubit, followed by a controlled-NOT gate from Alice to Bob and another from Alice to Charlie:Thus this circuit gives the required quantum circuit preparation of a three-qubit GHZ state.

Let Alice's two bits be $(x,z)$ and Bob's bit be $b$. Alice applieswhile Bob appliesThey then send their qubits to Charlie. Acting onthese operations produce, up to an irrelevant global phase,The complete encoding table iswhere a possible overall minus sign in the two $x=z=1$ cases has no observable effect.

Charlie performs a projective measurement in the eight-state GHZ basis. The sign $+$ or $-$ reveals $z$. The basis index reveals $(x,b)$ according toHe therefore reconstructs Alice's two bits and Bob's one bit with certainty, which is the three-party dense coding with a GHZ state protocol.

For a prime $p$ and a positive integer $N$, the P-adic valuation is

Because $p\ge k+2$, neither $(k+1)!$ nor $k!$ contains a factor $p$. On the other hand, $p\le 2k+1$, so $(2k+1)!$ contains a factor $p$; andso it contains no second factor $p$. ThereforeThis is the valuation of a near-central binomial coefficient.