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

Write an integral binary quadratic form as $[a,b,c]$. For proper equivalence of binary quadratic forms, the allowed changes of variables have determinant one. Here is the needed reduction rather than an appeal to class-number tables. A shear $(x,y)\mapsto (x+ny,y)$ changes $b$ to $b+2an$ without changing $a$ or the discriminant of a binary quadratic form. Choose $n$ so $-a<b\le a$. If the resulting $c<a$, the determinant-one change $(x,y)\mapsto (-y,x)$ replaces $[a,b,c]$ by $[c,-b,a]$, strictly decreasing the positive integer leading coefficient. Repeating must terminate with $|b|\le a\le c$. If $a=c$ and $b<0$, the same rotation makes $b$ positive; the choice $-a<b\le a$ already fixes the other boundary sign. This is a reduced positive definite binary quadratic form.

Since $4ac-b^2=67$, the reduction inequalities give $67\ge 3a^2$, so $a\in \{1,2,3,4\}$. The integer $b$ is odd. For $a=1$, only $b=1$ survives the boundary convention and $c=17$. For $a=2$, $b=\pm 1$ gives $c=68/8$, not an integer. For $a=3$, $b=\pm 1,\pm 3$ gives $68/12$ or $76/12$; for $a=4$, $b=\pm 1,\pm 3$ gives $68/16$ or $76/16$. None is integral. Therefore every form is properly equivalent to $x^2+xy+17y^2$, establishing class number one for discriminant minus sixty-seven.

For infinitude, its determinant-one shears produceEach has discriminant $-67$ and is positive definite because it is a change of variables of the displayed positive form. Their middle coefficients are distinct, so they are infinitely many distinct elements of the set.

The Liouville approximation theorem says that if $\alpha$ is an irrational algebraic number of degree $d$, there is $c_{\alpha }>0$ such that $|\alpha -p/q|\ge c_{\alpha }{q}^{-d}$ for all integers $p$ and $q\ge 1$. To see the source of the bound, a degree-$d$ integer minimal polynomial $P$ gives $q^{d}P(p/q)$ a nonzero integer. On a fixed neighbourhood of $\alpha$, the mean value theorem bounds $|P(p/q)|$ by a constant times $|p/q-\alpha |$; outside that neighbourhood a smaller uniform constant suffices.

Let $\alpha$ denote the factorial-denominator sum and let $p_N/q_N$ be its partial sum through $N$, with $q_N=10^{N!}$ for $N\ge 2$. This is an integer numerator even though $0!=1!=1$ makes the first two terms equal. Positivity and the rapid increase of factorial exponents implyFor example the first omitted term is $10^{-(N+1)!}$ and every succeeding factorial exponent increases by at least one, giving a geometric tail bound less than $10/9$ times that first term.

First $\alpha$ is irrational: if $\alpha =a/b$, the positive difference from a partial sum is at least $1/(b{q}_N)$, contradicting this bound for sufficiently large $N$. If it were algebraic of any fixed degree $d$, Liouville approximation theorem would require $c_{\alpha }{q}_N^{-d}<2q_N^{-(N+1)}$, again impossible for large $N$. Hence $\boxed{\alpha \text{ is transcendental}.}$

Let $C$ be the middle-third Cantor set and choose a positive integer $d$ with $d\log 2/\log 3\ge k$; this is possible for every real $k$, including negative $k$. Set $X=C^d\subset {\mathbb{R}}^d$. It is closed and bounded since each factor is compact. If a subset of $X$ is connected, each coordinate projection is a connected subset of $C$ and hence a singleton; therefore the subset itself is a singleton. Thus $X$ is totally disconnected.

For completeness, the dimension of these Cartesian powers of the Cantor set can be checked directly. At stage $n$ there are $2^{dn}$ cubes of side $3^{-n}$, giving vanishing $s$-dimensional cover cost whenever $s>d\log 2/\log 3$. Conversely put independent equiprobable zero-or-two ternary digits on every coordinate. Each stage-$n$ cube has probability $2^{-dn}$. If $3^{-n}\le r<3^{-n+1}$, a Euclidean ball of radius $r$ meets at most a constant depending on $d$ such cubes. Hence its probability is at most $C_d{r}^{d\log 2/\log 3}$. For any sufficiently fine cover, summing this bound over covering sets shows that its cost at exponent $d\log 2/\log 3$ is bounded below by a positive constant, since total probability is one. These upper and lower Hausdorff measure bounds proveThe construction does not claim arbitrarily large Hausdorff dimension in one fixed ambient Euclidean dimension.

A general feedback shift register of length $d$ over an alphabet $A$ stores $(s_n,\dots ,s_{n+d-1})$, outputs $s_n$, and shifts to $(s_{n+1},\dots ,s_{n+d-1},F(s_n,\dots ,s_{n+d-1}))$ for a fixed function $F:A^d\to A$. When the alphabet is a field $K$, it is a linear-feedback shift register if $F$ is linear over $K$, equivalently $s_{n+d}={\sum }_{j=0}^{d-1}{a}_j{s}_{n+j}$ for fixed coefficients in $K$. The binary case uses the finite field $K={\mathbb{F}}_2$; the examples and counterexamples below are binary.

For a genuinely nonlinear example take length three and $F(a,b,c)=a+bc$. Its values at $(0,1,0)$ and $(0,0,1)$ are both zero, but its value at their sum $(0,1,1)$ is one, violating additivity. Thus this general register is not linear. It even has an invertible state update: from $(b,c,d)$ the old leading bit is $a=d+bc$, so the counterexample does not rely on allowing singular registers.

False. Take $s_{n+1}=s_n$ and $t_{n+2}=t_{n+1}+t_n$. The only nonzero length-one fill produces constant ones. Constant ones cannot satisfy the second linear recurrence relation, since $1+1=0$ in ${\mathbb{F}}_2$. Thus these linear-feedback shift registers have no identical outputs from nonzero fills.

False. Take $s_{n+1}=s_n$ and $t_{n+2}=t_n$. Fills $1$ and $(1,1)$ both produce the constant-one sequence, despite different lengths. Both state updates are invertible.

True. A length-$d$ linear-feedback shift register has $2^d-1$ nonzero fills, and its first $d$ output bits recover its fill, so these fills give distinct output sequences. If lengths satisfy $r<s$, the longer register has strictly more nonzero outputs. At least one is absent from the shorter register's output set; choosing any nonzero shorter fill then gives unequal outputs. This is the counting property of output sets of different-length linear-feedback registers.

True. The length-one and length-two registers in part (ii), with the displayed nonzero fills, provide an explicit example. Register length need not equal the minimal recurrence length of every sequence it can generate.

The fit is a Gaussian linear model for $Y_i=\log ({so2}_i)$ with an intercept and the six displayed explanatory variables:The command computes ordinary least squares; independent normal errors with common variance are the additional assumptions yielding the exact printed tests. A coefficient describes an adjusted association on the log scale, holding the other variables fixed. Exponentiation gives a multiplicative effect on the conditional median of sulphur dioxide, not an additive effect on its original scale. Under the Gaussian model its conditional mean additionally includes the factor $e^{{\sigma }^2/2}$.

The estimates are the coordinates of $\hat{\beta }=(X^{T}X{)}^{-1}{X}^{T}Y$. With $41$ observations and $7$ parameters the residual degrees of freedom are $34$, and the residual standard error is $s=\sqrt{\mathrm{RSS}/34}=0.448$ to the displayed precision. The reported standard error of coefficient $j$ is $s\sqrt{[(X^{T}X{)}^{-1}{]}_{jj}}$. For each null hypothesis ${\beta }_j=0$, the displayed statistic $t_j={\hat{\beta }}_j/\mathrm{se}({\hat{\beta }}_j)$ has Student t-distribution with $34$ degrees of freedom under that null. Its two-sided p-value is $2\mathrm{Pr}(t_{34}\ge |t_j|)$.

At the $5\%$ level the intercept, temperature, manufacturing and wind coefficients differ significantly from zero in the full model. Temperature and wind have negative estimated adjusted effects; manufacturing has a positive one. The p-values for population, precipitation and precipitation days, approximately $0.136$, $0.127$ and $0.931$, do not reject their respective zero-coefficient hypotheses. This is not evidence that their effects are exactly zero, and these observational associations do not establish causation.

A sensible candidate reduced linear regression keeps an intercept, temperature, manufacturing and wind. It must be refitted: coefficients generally change when correlated predictors are removed. The three deletions can be checked jointly by the F-test statisticwhich has $F_{3,34}$ distribution under the joint null. The individual summary does not determine this joint test or establish the reduced model's adequacy.

In the final command, the uniquely matching component named by fit$df is the residual degrees of freedom. Thus the result is $\boxed{\sqrt{\mathrm{RSS}/34}=0.448\text{ to printed precision}.}$

Substitute $C=t^{\alpha }F(\xi )$, $\xi =r{t}^{-\beta }$. The derivatives giveFor a nontrivial spreading similarity solution, equality at all times requires $\boxed{\beta =1/2}$. The conserved total number of molecules isA finite nonzero constant $N$ therefore requires $\alpha +3\beta =0$, giving $\boxed{\alpha =-3/2}$. In one dimension the same diffusion length exponent is $1/2$, but conservation gives amplitude exponent $-1/2$; generally it is $-d/2$ in dimension $d$.

The profile equation is consequentlyMultiplication by ${\xi }^2$ puts it in the integrated form $[D{\xi }^2{F}^{\prime }+{\xi }^{3}F/2{]}^{\prime }=0$. For the regular localized Gaussian heat kernel profile, the constant is zero at the origin, so $D{F}^{\prime }+\xi F/2=0$. Integrating givesThe second expression chooses the optional normalization $A=N/(4\pi D{)}^{3/2}$. Its mass is $N$, and its width tends to zero with $t^{1/2}$ while its mass stays fixed, so it approaches $N$ times a Dirac delta distribution at the origin as $t\downarrow 0$.

The circle $\gamma :r=1$ is a periodic orbit, since $\dot{r}=0$ there and $\dot{\theta }=1$. Its period is $2\pi$. Linearizing in $(\delta r,\delta \theta )$ along it givesThe monodromy matrix is triangular with diagonal entriesThe unit Floquet multiplier comes from translating an autonomous orbit in time: its tangent vector is a periodic solution of the variational equation, independently of $g$. A sufficient condition for asymptotic stability is ${\int }_0^{2\pi }g<2\pi$, making the normal multiplier less than one. The reverse strict inequality gives instability; equality requires nonlinear analysis.

For $g=2\sin \theta$ the normal multiplier is $e^{-2\pi }$, so the circle is asymptotically stable. That does not mean it attracts every initial point. Since $r>0$ makes $\theta$ strictly increasing, divide the radial equation by $\dot{\theta }$:For $r>1$, put $v=r-1>0$. Then $v^{\prime }=(2\sin \theta -1)v-v^2\le (2\sin \theta -1)v$, whose integrated linear coefficient decreases by $2\pi$ per revolution. Thus every exterior orbit approaches $r=1$.

For $0<r<1$ put $w=(1-r{)}^{-1}>1$. It satisfies the linear equationLet $w_c$ be its solution with $w_c(\pi )=1$. It defines the separatrix $r_c=1-1/w_c$ wherever $w_c>1$. At $\theta =\pi$, $r_c=0$, $r_c^{\prime }=0$, and differentiation gives $r_c^{\prime \prime }=2$, so $r_c\sim (\theta -\pi {)}^2$. The approach to this endpoint takes infinite physical time because $dt=d\theta /r_c$.

To locate its other endpoint, use the integrating factor $e^{-A(\theta )}$ with $A(\theta )=\theta +2\cos \theta$. It givesIn particular $w_c(0)>e^{4-\pi }>1$, whereasOn $(-\pi ,0)$, crossing $w=1$ has $w^{\prime }=-2\sin \theta >0$, so there is one crossing ${\theta }_b\in (-\pi ,0)$. There cannot be another crossing before $\pi$: on $(0,\pi )$ crossings have negative derivative, while the local quadratic form at $\pi$ is positive on its left. Thus $r_c>0$ for ${\theta }_b<\theta <\pi$, and its closure is a homoclinic orbit to the origin. At ${\theta }_b$, $r_c^{\prime }=-2\sin {\theta }_b>0$, so departure from the origin likewise takes infinite time.

Scalar-solution comparison now gives the basin picture. Initial points inside that loop have $w<w_c$ at the same angle and approach $r=0$ before reaching angle $\pi$. Points on its boundary return to the origin along the homoclinic trajectory. Points outside the loop reach angle $\pi$ with $w>1$ or lie outside the unit circle; they approach $r=1$. To check the inner exterior region quantitatively, the return map at $\theta =\pi$ is $w\mapsto e^{2\pi }(w-I)$, where $I={\int }_0^{2\pi }{e}^{-u-2+2\cos u}du<1-e^{-2\pi }$. It sends every $w>1$ increasingly to infinity, equivalently $r\to 1$.

There are no other nonconstant periodic orbits: an orbit reaching the section with $w>1$ has strictly increasing successive $w$ values, and the remaining inner trajectories tend to the origin. The origin, defined by the continuous Cartesian extension, attracts the interior of the loop but is not Lyapunov stable, since arbitrarily small lower-sector initial points outside the loop approach the unit circle. This is the homoclinic basin boundary in a sinusoidal radial flow.

The two Gamma function integrals are absolutely convergent when $\mathrm{Re}\alpha ,\mathrm{Re}\beta >0$. Consequently Fubini theorem givesMake the change of variables $u=x+y$, $t=x/(x+y)$, so $x=ut$, $y=u(1-t)$, $u>0$, $0<t<1$, and the Jacobian is $u$. Powers of positive real variables use the real logarithm, so this transformation is also valid for complex exponents. The integral factors asBoth factors converge under the same real-part assumptions. The first is $\Gamma (\alpha +\beta )$, proving the Beta function identity

Use the canonical Poisson bracket convention $\{H,G\}={\sum }_k(H_{q_k}{G}_{p_k}-H_{p_k}{G}_{q_k})$. The Hamiltonian flow generated by $G$ has ${\dot{q}}_k=G_{p_k}$ and ${\dot{p}}_k=-G_{q_k}$. The chain rule therefore givesThus $H$ is invariant under every such trajectory exactly when $\boxed{\{H,G\}=0}$ identically. Antisymmetry then gives $dG/dt=\{G,H\}=0$ along the flow of $H$, so $G$ is a constant of motion.

For $G=\alpha {\sum }_k{p}_k$, the generated equations are ${\dot{q}}_k=\alpha$, ${\dot{p}}_k=0$, hence $q_k(t)=q_k(0)+\alpha t$, $p_k(t)=p_k(0)$. Invariance under this simultaneous translation implies conservation of $\boxed{\sum _k{p}_k}$ when $\alpha \ne 0$; the zero generator alone conveys no additional conservation law.

Write $H=F(P,Q)$ with $P=\sum p_k^2$ and $Q=\sum q_k^2$. The angular momentum component $L_i={ϵ}_{ijk}{q}_j{p}_k$ has ${\partial }_{p_{\ell }}{L}_i={ϵ}_{ij\ell }{q}_j$ and ${\partial }_{q_{\ell }}{L}_i={ϵ}_{i\ell k}{p}_k$. Thereforesince a symmetric product contracts to zero with the antisymmetric Levi-Civita symbol. All three components of angular momentum are conserved by this rotationally invariant Hamiltonian.

Take velocities relative to a comoving observer at $O$. Spatial homogeneity means that changing the observer to $A$ gives the same relative velocity law, soWith $O$ as origin this implies $v(0)=0$ and $v(a+b)=v(a)+v(b)$. A physical velocity field is continuous; additivity first gives rational homogeneity and then, by continuity, real homogeneity. Hencewith coefficients independent of position. Without a regularity assumption, the additive functional equation alone admits non-linear pathological solutions; continuity is the usual implicit velocity-field assumption.

Isotropy requires $v(Rr)=Rv(r)$ for every spatial rotation, or $HR=RH$. Rotations about $e_i$ force $H{e}_i$ to be parallel to $e_i$, and rotations exchanging coordinate directions force those diagonal coefficients to agree. Therefore $H_{ij}=H{\delta }_{ij}$ and $\boxed{v=Hr}$, the Hubble law.

Allow $H=H(t)$. Solving $\dot{r}=H(t)r$ gives $r(t)=a(t)x$ for a constant comoving coordinate $x$, where $a(t)=a(t_0)\exp ({\int }_{t_0}^{t}H(s)ds)$. Thus $\boxed{H=\dot{a}/a}$, with $a$ the scale factor.

The physical particle horizon is the greatest physical distance at time $t$ from which a light signal could have reached the observer since the beginning of the cosmological model. If that beginning is $t=0$, radial null propagation has comoving distance ${\int }_0^{t}cd{t}^{\prime }/a(t^{\prime })$, soFor $a(t)=t^{\alpha }$ and $0<\alpha <1$, the integral converges at zero and equals $t^{1-\alpha }/(1-\alpha )$. ConsequentlyThe horizon problem is that widely separated regions of the observed cosmic microwave background have nearly equal temperatures although their past causal regions did not overlap before recombination in the usual decelerating hot-big-bang history. That history offers no causal equilibration mechanism for their observed uniformity. The particle horizon used here is distinct from the Hubble radius $c/H$.

Define the Möbius function by $\mu (1)=1$, $\mu (n)=(-1{)}^r$ for a product of $r$ distinct primes, and $\mu (n)=0$ if a prime square divides $n$. For $n>1$, summing over square-free divisors gives ${\sum }_{d\mid n}\mu (d)=(1-1{)}^r=0$, while the sum is one at $n=1$.

Both Dirichlet series $\sum n^{-s}$ and $\sum \mu (n)n^{-s}$ converge absolutely for $\sigma =\mathrm{Re}s>1$. Their product may therefore be regrouped by the product of the indices:This simultaneously proves $\boxed{\zeta (s)\ne 0\text{ for }\sigma >1}$ andIn particular $|1/\zeta (\sigma +it)|\le \sum |\mu (n)|n^{-\sigma }\le \zeta (\sigma )$.

Under the assumed analytic continuation, $\zeta$ is holomorphic near $s_0=1+i{t}_0$ when $t_0\ne 0$, and $\zeta (\sigma )=1/(\sigma -1)+O(1)$ as $\sigma \downarrow 1$. If $s_0$ were a zero of order $m\ge 2$, local factorization would give $|1/\zeta (s_0+h)|\ge c{h}^{-m}$ for sufficiently small positive $h$. The preceding absolutely convergent bound gives instead $|1/\zeta (1+h+i{t}_0)|=O(h^{-1})$, a contradiction. Thus $\boxed{m\le 1}$. This reciprocal Dirichlet-series bound on boundary-zero multiplicity does not assert that any such boundary zero exists.

A model of three-dimensional hyperbolic space is ${\mathbb{H}}^3=\{(z,t):z\in \mathbb{C},t>0\}$ with metric $d{s}^2=(|dz{|}^2+d{t}^2)/t^2$, the complete simply connected metric of curvature $-1$. The translation length of an isometry $g$ is $\ell (g)={\inf }_{P}d(P,gP)$. A hyperbolic isometry has positive translation length attained on its invariant complete geodesic, the axis of a hyperbolic-space isometry. It joins the two fixed ideal points and is translated by distance $\ell (g)$; a three-dimensional axial isometry can also rotate around it.

For the boundary map $z\mapsto kz$, the hyperbolic extension of a Möbius transformation is $(z,t)\mapsto (kz,|k|t)$. Every path from $P$ to $gP$ has length at least the absolute change of $\log t$, namely $|\log |k||$, because the metric length dominates $|dt|/t$. On the vertical line $z=0$ a vertical segment attains that bound. HenceIf $|k|\ne 1$ the vertical line is the axis. If $|k|=1$ the map is a rotation with zero translation length, including the identity when $k=1$; it is not a positive-length hyperbolic isometry.

Represent the Möbius transformation by $A=\left(\begin{array}{cc}3& 2\\ 7& 5\end{array}\right)$, which has determinant one and trace eight. Its distinct eigenvalues are ${\lambda }_{\pm }=4\pm \sqrt{15}$ and their product is one. A change of basis to eigenvectors conjugates its projective action to a dilation by ${\lambda }_{+}/{\lambda }_{-}=(4+\sqrt{15}{)}^2$ or its reciprocal. Translation length is invariant under conjugacy, so part (i)'s dilation calculation givesThe fixed boundary points solve $7z^2+2z-2=0$, namely $(-1\pm \sqrt{15})/7$. The axis of a hyperbolic-space isometry is the semicircular geodesic with those endpoints in the vertical real plane.

Put $M=X^{T}X$, which is positive definite because $X$ has full column rank. The log likelihood differs from $-\Vert Y-X\beta {\Vert }^2/(2{\sigma }^2)$ by a term independent of $\beta$. Differentiation gives the normal equations $M\hat{\beta }=X^{T}Y$, henceThe distribution follows by writing $\hat{\beta }=\beta +M^{-1}{X}^T\epsilon$ and applying the linear transformation rule for a multivariate normal distribution.

Let $s={\sigma }^2$ and $R=\Vert Y-X\hat{\beta }{\Vert }^2$. Orthogonality of the residual to the columns of $X$ gives the exact decompositionThe prior is density proportional to $s^{-1}$ with respect to $d\beta ds$. Thus the joint posterior distribution isCompleting the quadratic identifiesThe sampling distribution treats the true $\beta$ as fixed and varies the data, whereas the conditional posterior fixes the observed data and distributes $\beta$. Their covariance formulas agree, but their centres and their interpretations differ.

For a new row vector $x^{\ast }$, let $h^{\ast }=x^{\ast }{M}^{-1}(x^{\ast }{)}^T$ and suppose its new error is independent. With known ${\sigma }^2$, the maximum-likelihood plug-in prediction uses mean $x^{\ast }\hat{\beta }$ and noise variance ${\sigma }^2$, while a calibrated frequentist prediction must account for the estimator: $y^{\ast }-x^{\ast }\hat{\beta }\sim N(0,{\sigma }^2(1+h^{\ast }))$. If variance is estimated, the maximum-likelihood estimator is $R/n$, whereas the exact frequentist prediction pivot uses $\hat{s}=R/(n-p)$ and has Student t-distribution with $n-p$ degrees of freedom.

In the Bayesian calculation, integrating $\beta$ first gives $y^{\ast }\mid s,X,Y\sim N(x^{\ast }\hat{\beta },s(1+h^{\ast }))$. Integrating $\beta$ out of the joint posterior gives $s\mid X,Y\sim \mathrm{InvGamma}((n-p)/2,R/2)$. For $\nu =n-p$, integration of the predictive normal against this inverse-gamma distribution has density proportional toThe substitution $t=[R+(y^{\ast }-x^{\ast }\hat{\beta }{)}^2/(1+h^{\ast })]/(2s)$ reduces the integral to a Gamma function. Normalizing identifies the Student t-distribution, givingwhere the second parameter is a scale, not its variance. These Bayesian intervals coincide with the usual exact Gaussian-regression prediction intervals for this prior, although their probability interpretations differ. Posterior propriety requires $R>0$ and $n>p$; the former holds almost surely under the nondegenerate Gaussian model. Prediction of the noiseless conditional mean omits the added one in $1+h^{\ast }$.

An interval covering relation $I\to J$ means $F(I)\supseteq J$. The associated directed graph has one vertex for each interval and an edge $i\to j$ for each covering. Its transition matrix is $A_{ij}=1$ when that edge exists, and zero otherwise. Matrix multiplication counts walks; thus $\boxed{\mathrm{tr}(A^n)}$ counts closed length-$n$ itineraries, with a distinguished starting vertex.

To see how itineraries force periodic orbits, a continuous map covering a closed interval has a closed subinterval mapping onto it: choose successive first/last crossings of its endpoints. Pull these subintervals back along a closed walk. This yields $K\subseteq I_{i_0}$ with $F^n(K)\supseteq I_{i_0}\supseteq K$. At the two preimages of the ends of $K$, $F^n(x)-x$ has opposite weak signs; the intermediate value theorem gives a fixed point of $F^n$.

A graph alone does not give an exact count of periodic points for a general continuous map: extra oscillations or a fixed interval can create additional points. For example on $I=[0,1]$, both $F(x)=x$ and $F(x)=1-x$ have matrix $A=(1)$; the first has infinitely many fixed points and the second only one. Distinct itineraries give distinct points when their interval interiors are disjoint and the periodic orbit avoids shared endpoints. In that setting, $\mathrm{tr}(A^n)$ is a guaranteed lower bound, not a universal equality. Likewise, the primitive-word count $(1/n){\sum }_{d\mid n}\mu (d)\mathrm{tr}(A^{n/d})$ counts guaranteed least-period itineraries under this separation condition. With overlapping intervals, even distinctness needs qualification. This is the scope of counting cycles in an interval covering graph.

For the first five-cycle, put $I_j=[x_j,x_{j+1}]$, $0\le j\le 3$. The graph and matrix areThe four traces are $1,3,7,15$. Shared endpoints have least period five, so they do not spoil the distinctness argument for the requested periods. Primitive cyclic itineraries are: $3$ for period one; $(3,2)$ for period two; $(3,1,2)$ and $(3,3,2)$ for period three; $(0,1,2,3)$, $(3,3,1,2)$ and $(3,3,3,2)$ for period four. Consequently the monotone five-cycle interval covering pattern guaranteesThese words specify the successive intervals containing their points; cyclic rotations denote the same orbit.

There is a horseshoe for an interval map for $F^2$: both $I_2$ and $I_3$ cover $I_2\cup I_3$ under that iterate, and their interiors are disjoint. Repeated binary choices produce at least $2^n$ separated length-$n$ itineraries for the second iterate, hence positive topological entropy, at least $(\log 2)/2$ for $F$. Thus the dynamics are chaotic in this standard interval-map sense. No conclusion of global transitivity on all of $\mathbb{R}$ follows.

A one-step horseshoe is not guaranteed if that is the intended definition. For example the unimodal continuous map $F(x)=x+1$ for $x\le 3$ and $F(x)=16-4x$ for $x\ge 3$ has cycle $0,1,2,3,4$. A left-branch interval cannot cover itself, since its image is shifted to the right. Two right-branch intervals cannot each cover their union because that branch is injective. If one interval straddles the maximum and covers itself, its right endpoint must map below its left endpoint; every disjoint interval farther to the right then maps below it and cannot self-cover. A disjoint interval to the left also cannot self-cover. So this example has no one-step two-branch horseshoe, although its second iterate does. It also proves that $F$ can be unimodal.

For the second order, write $J_0=[x_3,x_1]$, $J_1=[x_1,x_0]$, $J_2=[x_0,x_2]$, $J_3=[x_2,x_4]$. Endpoint images giveThe traces are $1,3,1,7$. The guaranteed primitive words are $1$, $(0,3)$ and $(1,2,0,3)$, giving $\boxed{\text{periods }1,2,4\text{ but not necessarily }3}$. To prove the last qualification, take ordered points $0,1,2,3,4$ and linearly interpolate the map values $4,3,1,0,2$ on $[0,4]$, extending by $G(x)=4-x$ for $x<0$ and $G(x)=2$ for $x>4$. Both exterior regions enter $[0,4]$ after at most two steps, so they introduce no extra periodic points. Its only closed length-three itinerary is $111$; on $J_1$ it is $x\mapsto 5-2x$, whose third iterate has only the same fixed point. Endpoints have least period five, so this example has no three-cycle.

The distinct fourth-iterate return walks $1111$ and $1203$ yield two subintervals of $J_1$ that return over $J_1$, giving a horseshoe for $G^4$ and positive entropy at least $(\log 2)/4$. Thus $G$ too must have chaotic interval dynamics and a horseshoe in some iterate. The affine example has no one-step horseshoe: its increasing branch lies strictly below the diagonal, while on the decreasing branch injectivity prevents two self-covering intervals; a minimum-straddling self-covering interval excludes a self-covering interval on either side by the same endpoint argument. The distinction between a map and its iterate is essential for both patterns.

Put $\pi =p-eA/c=m\dot{q}$. The Hamilton equations areDifferentiate the mechanical momentum and substitute:With $B=\nabla \times A$ and $E=-c^{-1}{\partial }_{t}A$ in this zero-scalar-potential gauge, this is $\boxed{m\ddot{q}=eE+(e/c)\dot{q}\times B}$, the Lorentz force in the units of the Hamiltonian.