Past exam of the mathematics course of the University of Cambridge / 2018 / ii

transitions is odd; no other boundary edge contributes. An interior edge contributes twice. A small triangle contributes an odd number precisely when its three labels are

1, 2, 3

: a triangle using only

1, 2

contributes two, and every other non-tricoloured triangle contributes zero. The number of tricoloured triangles is therefore odd.

Now suppose the closed sets

A_{i}

in the question existed. Let

d_{i} (x)

be the distance from a point to a closed set

A_{i}

. Empty triple intersection makes

d_{1} + d_{2} + d_{3} > 0

, so

r (x) = \frac{d _{1} ( x ) v _{1} + d _{2} ( x ) v _{2} + d _{3} ( x ) v _{3}}{d _{1} ( x ) + d _{2} ( x ) + d _{3} ( x )}

(1)

is a continuous function from the large triangle to itself, where

v_{i}

is the vertex opposite

α_{i}

. Since the

A_{i}

cover the triangle, at least one

d_{i} (x)

vanishes, so

r (x)

always lies on the boundary. On

α_{i} \subseteq A_{i}

, its

i

th barycentric coordinate vanishes, hence

r (α_{i}) \subseteq α_{i}

. Thus

r

is face-preserving on the boundary; its boundary restriction is homotopic there to the identity by the straight-line homotopy. This would give a map from the triangle into its boundary whose boundary degree is one, contradicting the no-retraction theorem, the standard topological consequence of Sperner's lemma. Therefore the three closed sets must have a common point.

3H (Coding & Cryptography)

 0  0

Solution

 0  0

Let a memoryless source have probabilities

p_{1}, \dots, p_{m}

, and let a uniquely decodable

D

-ary code have word lengths

ℓ_{i}

and mean length

L = \sum_{i} p_{i} ℓ_{i}

. The Shannon source coding theorem states

H_{D} (p) \leq L, H_{D} (p) = - \sum_{i} p_{i} lo g_{D} p_{i},

(1)

and that some prefix code satisfies

H_{D} (p) \leq L < H_{D} (p) + 1.

(2)

For the lower bound, the Kraft inequality gives

K = \sum_{i} D^{- ℓ_{i}} \leq 1

. Set

q_{i} = D^{- ℓ_{i}} / K

. The Gibbs inequality, or nonnegativity of relative entropy, gives

0 \leq \sum_{i} p_{i} lo g_{D} \frac{p _{i}}{q _{i}} = - H_{D} (p) + L + lo g_{D} K .

(3)

Therefore

L \geq H_{D} (p) - lo g_{D} K \geq H_{D} (p)

For achievability choose

ℓ_{i} = ⌈ - lo g_{D} p_{i} ⌉

. Then

\sum_{i} D^{- ℓ_{i}} \leq \sum_{i} p_{i} = 1

, so the converse part of the Kraft theorem supplies a prefix code with these lengths, and

L < \sum_{i} p_{i} (- lo g_{D} p_{i} + 1) = H_{D} (p) + 1.

(4)

Hence the entropy is the optimal mean code length up to less than one code symbol.

4G (Automata and Formal Languages)

 0  0

a

 0  0

Solution

 0  0

The pumping lemma for context-free languages states that every context-free language

L

has a pumping length

p

such that every

w \in L

with

∣ w ∣ \geq p

can be written

w = uvx yz

(1)

with

∣ vx y ∣ \leq p

∣ v y ∣ > 0

, and

u v^{i} x y^{i} z \in L

for every integer

i \geq 0

b

 0  0

i

 0  0

Solution

 0  0

This language is not context-free. Suppose it were, and define the homomorphism

h (a) = h (c) = a, qq u a d h (b) = h (d) = b .

(1)

Then closure under inverse homomorphism and intersection of a context-free language with a regular language would make

h^{- 1} (L) c a p a^{+} b^{+} c^{+} d^{+} = a^{m} b^{n} c^{m} d^{n} : m, n g e q 1

(2)

context-free. The equality holds because the midpoint of a square with four nonempty alternating runs must lie between its second and third runs.

Apply the pumping lemma for context-free languages to

a^{p} b^{p} c^{p} d^{p}

. A pumpable window of length at most

p

meets at most two adjacent blocks. Pumping changes at least one block but cannot reach its equal-count partner two blocks away, so either the

a, c

counts or the

b, d

counts cease to agree. This contradiction proves the claim.

ii

 0  0

Solution

 0  0

The equations force

m = 4 r

n = 3 r

k = 5 s

, and

l = 2 s

. Hence the language is

{a^{4 r} b^{3 r} : r \geq 0} {c^{5 s} d^{2 s} : s \geq 0} .

(1)

It is context-free; one explicit context-free grammar is

S \to X Y, X \to aaaa X bbb ∣ ϵ, Y \to ccccc Y dd ∣ ϵ .

(2)

iii

 0  0

Solution

 0  0

This language is not context-free. Let

p

be a proposed pumping length and choose

n

with

3^{n} \geq p

. In any pumping decomposition of the unary word

a^{3^{n}}

, pumping once more increases its length by an integer

d

with

1 \leq d \leq p

. But

3^{n} < 3^{n} + d \leq 2 \cdot 3^{n} < 3^{n + 1},

(1)

so the pumped length is not a power of three, contrary to the pumping lemma for context-free languages. This is also an instance of the fact that a unary context-free language is regular, whereas the powers of three are not ultimately periodic.

c

 0  0

Solution

 0  0

Take a context-free grammar for

L

with start symbol

S

, rename nonterminals if necessary, and add a fresh start symbol

S_{0}

with

S_{0} \to ϵ ∣ S S_{0} .

(1)

Every derivation concatenates finitely many words of

L

, and every finite concatenation can be derived. The resulting grammar generates $L^{*}$ , proving closure of context-free languages under Kleene star.

5J (Statistical Modelling)

 0  0

Solution

 0  0

Write

Y_{i}

for the request count on day

i

. Both fits are Poisson regression models with independent

Y_{i} \sim Poisson (λ_{i}) .

(1)

In model 1,

lo g λ_{i} = β_{0} + β_{W} W_{i} + β_{E} E_{i} + β_{B} B_{i} + β_{L} L_{i} + β_{M} M_{i},

(2)

where the variables are indicator variables for winter, weekend, bank holiday, and low or medium pollution; non-winter weekdays that are not bank holidays and have high pollution form the baseline. Model 2 imposes

H_{0} : β_{B} = β_{L} = β_{M} = 0,

(3)

retaining only winter and weekend effects.

The models are nested, and the likelihood-ratio test statistic is the decrease in residual deviance,

316.39 - 304.97 = 11.42.

(4)

There are three restrictions. By Wilks theorem, under

H_{0}

this statistic is asymptotically a chi-squared distribution with three degrees of freedom. Since

11.42 > χ_{3, 0.99}^{2} = 11.34487,

(5)

we reject model 2 at the $1%$ level in favour of model 1.

p_{- 1} = 0

, the birth-death master equation for birth rate

b_{n} = B n

and death rate

d_{n} = D n

\overset{p}{˙}_{n} = B (n - 1) p_{n - 1} + D (n + 1) p_{n + 1} - (B + D) n p_{n}, n \geq 0.

(1)

b

 0  0

Solution

 0  0

Multiply the birth-death master equation by

n

and sum. Index shifts give

\overset{μ}{˙} = (B - D) μ .

(1)

For the second moment, a birth changes

n^{2}

2 n + 1

and a death changes it by

- 2 n + 1

, so

\frac{d}{d t} E [N^{2}] = 2 (B - D) E [N^{2}] + (B + D) μ .

(2)

Since

σ^{2} = E [N^{2}] - μ^{2}

(σ^{2})^{'} = 2 (B - D) σ^{2} + (B + D) μ .

(3)

Together these are the moment equations of a linear birth-death process.

c

 0  0

Solution

 0  0

The deterministic equation has solution

n (t) = n (0) e^{(B - D) t}

and is identical in form to the equation for the stochastic expected value. It therefore identifies only the net rate

r = B - D .

(1)

The variance equation also contains the total event rate

s = B + D

. Once

r

and

s

are inferred,

B = \frac{s + r}{2}, D = \frac{s - r}{2} .

(2)

The deterministic trajectory cannot distinguish frequent births and deaths that nearly cancel from infrequent events with the same net growth, whereas fluctuations can.

t = (1 + x) /2

and then

u = x^{2}

. Symmetry gives

B (z, z) = 2^{1 - 2 z} \int_{- 1}^{1} (1 - x^{2})^{z - 1} d x = 2^{2 - 2 z} \int_{0}^{1} (1 - x^{2})^{z - 1} d x = 2^{1 - 2 z} \int_{0}^{1} u^{- 1/2} (1 - u)^{z - 1} d u = 2^{1 - 2 z} B (z, \frac{1}{2}) .

(1)

This proves the identity for

Re z > 0

. Both sides extend by analytic continuation to the same meromorphic function, equivalently by the beta--gamma identity and the Gamma duplication formula. The identity holds meromorphically for every $z \in C$ ; both sides are finite for $z \in / {0, - 1, - 2, \dots}$ and have matching poles at the excluded points.

b

 0  0

Solution

 0  0

Start from the product of two Gamma function integrals:

Γ (p) Γ (q) = \int_{0}^{\infty} \int_{0}^{\infty} e^{- (x + y)} x^{p - 1} y^{q - 1} d x d y .

(1)

Use the sum-and-ratio substitution for gamma integrals

r = x + y, t = \frac{x}{x + y}, x = r t, y = r (1 - t),

(2)

whose Jacobian is

r

. Absolute convergence for

Re p, Re q > 0

justifies the change of variables and separates the integral:

Γ (p) Γ (q) = (\int_{0}^{\infty} e^{- r} r^{p + q - 1} d r) (\int_{0}^{1} t^{p - 1} (1 - t)^{q - 1} d t) = Γ (p + q) B (p, q) .

(3)

Therefore

B (p, q) = \frac{Γ ( p ) Γ ( q )}{Γ ( p + q )} .

(4)

8B (Classical Dynamics)

 0  0

Solution

 0  0

Use the first-order action

S [q, p] = \int_{t_{1}}^{t_{2}} (p \overset{q}{˙} - H (q, p, t)) d t .

(1)

Varying

q

with fixed endpoints and varying

p

freely gives

δ S = \int_{t_{1}}^{t_{2}} [(\overset{q}{˙} - H_{p}) δ p + (- \overset{p}{˙} - H_{q}) δ q] d t .

(2)

The principle of stationary action therefore yields Hamilton's equations

\overset{q}{˙} = H_{p}, \overset{p}{˙} = - H_{q} .

(3)

For

H = p^{2} + q^{- 2}

these become

\overset{q}{˙} = 2 p

and

\overset{p}{˙} = 2 q^{- 3}

. Along their Hamiltonian flow,

H = E

is conserved and

\frac{d}{d t} (pq) = \overset{p}{˙} q + p \overset{q}{˙} = 2 q^{- 2} + 2 p^{2} = 2 H .

(4)

Thus

F = pq - c t H

is an integral of motion exactly when $c = 2$ .

Write its constant value as

F_{0}

. The surfaces

pq - 2 tE = F_{0}

in extended

(q, p, t)

-space give

pq = F_{0} + 2 Et .

(5)

Using

E q^{2} = p^{2} q^{2} + 1

q (t) = \pm \frac{( F _{0} + 2 Et ) ^{2} + 1}{E}, p (t) = \frac{F _{0} + 2 Et}{q ( t )} .

(6)

The sign of

q

is fixed. In phase space, each energy orbit is one of the two branches

p^{2} + q^{- 2} = E, q = \pm (E - p^{2})^{- 1/2}, ∣ p ∣ < E .

(7)

Each branch approaches

p = - E

and

p = + E

∣ q ∣ \to \infty

and turns at

(p, q) = (0, \pm E^{- 1/2})

9B (Cosmology)

 0  0

Solution

 0  0

Let

H = a^{'} / a = \overset{a}{˙}

, where a prime denotes differentiation with respect to conformal time

d τ = d t / a

. Multiplying the Friedmann equation by

a^{2}

gives

H^{2} + k c^{2} = \frac{8 π G}{3} ρ a^{2} .

(1)

The critical density is the value obtained when

k = 0

, so

Ω = \frac{ρ}{ρ _{crit}} = \frac{8 π Gρ a ^{2}}{3 H ^{2}}, \frac{k c ^{2}}{H ^{2}} = Ω - 1 .

(2)

Since

H^{'} = a \overset{a}{¨}

, the pressure-free Raychaudhuri equation gives

2 H^{'} = - \frac{8 π G}{3} ρ a^{2} = - (H^{2} + k c^{2}),

(3)

2 H^{'} + H^{2} + k c^{2} = 0.

(4)

Differentiating

Ω = 1 + k c^{2} / H^{2}

and substituting this equation yields

Ω^{'} = H Ω (Ω - 1) .

(5)

For an expanding universe

H > 0

. The Einstein-de Sitter universe

Ω = 1

is an unstable constant solution: curves starting with

0 < Ω < 1

decrease towards

0

, while curves starting with

Ω > 1

rise away from

1

and diverge as the closed model reaches maximum expansion. This is the Flatness problem.

∣ u ⟩_{A} \otimes ∣ v ⟩_{B}

Since

H \otimes H ∣11 ⟩ = \frac{1}{2} (∣00 ⟩ - ∣01 ⟩ - ∣10 ⟩ + ∣11 ⟩),

(1)

we have

∣ α ⟩ = \frac{1}{2 3} (3∣00 ⟩ + ∣01 ⟩ + ∣10 ⟩ - ∣11 ⟩) .

(2)

Its coefficient matrix is proportional to

(31 1 - 1),

(3)

whose determinant is

- 4 \neq = 0

. By the two-qubit product-state determinant criterion, a product state would have determinant zero. Therefore $∣ α ⟩$ is entangled.

b

 0  0

Solution

 0  0

This is superdense coding. To encode

00, 01, 10, 11

, Alice applies respectively

I, X, Z, XZ

to her half of

∣ Φ^{+} ⟩

. These local Pauli operators transform the shared state into the four mutually orthogonal Bell states

∣ Φ^{+} ⟩, ∣ Ψ^{+} ⟩, ∣ Φ^{-} ⟩, ∣ Ψ^{-} ⟩

, up to irrelevant global phases. Alice sends her one qubit to Bob. Bob now holds both qubits and performs a Bell-basis measurement, whose outcome identifies Alice's two-bit message with certainty. One transmitted qubit communicates two classical bits because one shared Bell pair was available beforehand.

11H (Coding & Cryptography)

 0  0

Solution

 0  0

For length-

n

binary linear codes

C_{2} \subseteq C_{1}

, their bar product of binary linear codes is

C_{1} ∣ C_{2} = {(u, u + v) : u \in C_{1}, v \in C_{2}} .

(1)

The map

(u, v) \mapsto (u, u + v)

is injective and linear, so

dim (C_{1} ∣ C_{2}) = dim C_{1} + dim C_{2} .

(2)

d_{i}

is the minimum distance of

C_{i}

, then

wt (u) + wt (u + v) \geq wt (v) .

(3)

For

v \neq = 0

this is at least

d_{2}

; for

v = 0

a nonzero word has weight at least

2 d_{1}

. Words

(0, v)

and

(u, u)

attain these bounds, proving

d (C_{1} ∣ C_{2}) = min (d_{2}, 2 d_{1}) .

(4)

A parity-check matrix

P

for a code

C

is a matrix satisfying

C = ker P

. A pair

(x, y)

belongs to

C_{1} ∣ C_{2}

exactly when

x \in C_{1}, x + y \in C_{2} .

(5)

Thus a parity-check matrix is

(P_{1} P_{2} 0 P_{2}) .

(6)

This is the parity-check matrix of a bar product.

The Reed-Muller code

RM (d, r)

is the length-

2^{d}

binary code obtained by evaluating every square-free polynomial in

d

Boolean variables of degree at most

r

on all points of

F_{2}^{d}

. Equivalently,

RM (d, r) = RM (d - 1, r) ∣ RM (d - 1, r - 1) .

(7)

The square-free monomials form a basis, so

dim RM (d, r) = j = 0 \sum r (j d) .

(8)

A word in

RM (d, 1)

evaluates an affine function

a_{0} + a \cdot x

. The two constant functions have weights

0

and

2^{d}

. Every nonconstant affine function takes each value equally often, so all other codewords have weight

2^{d - 1}

A monomial of degree

j

has weight

2^{d - j}

. Hence every generator, and therefore every codeword, has even weight when

r < d

. For

r = d

, the monomial

x_{1} \dots x_{d}

has weight one. All words have even weight exactly for $0 \leq r \leq d - 1$ .

φ_{0}, φ_{1}, \dots

of unary partial computable functions. The diagonal halting set is

K = {e : φ_{e} (e) ↓} .

(1)

It is a computably enumerable set: on input

e

, simulate

φ_{e} (e)

and accept if that computation halts.

Suppose

K

were a computable set. A program could then halt on input

e

exactly when the decider says

e \in / K

. Let

d

be its own index. If

d \in K

, the program does not halt, while if

d \in / K

, it halts. Both alternatives contradict the definition of

K

. Thus $K$ is computably enumerable but not computable.

b

 0  0

Solution

 0  0

A many-one reduction

A \leq_{m} B

is a total computable function

f

such that

n \in A ⟺ f (n) \in B .

(1)

B

is a computably enumerable set, compute

f (n)

and run a semidecision procedure for

B

on that value. It halts exactly when

f (n) \in B

, equivalently exactly when

n \in A

. Therefore $A$ is computably enumerable.

c

 0  0

Solution

 0  0

Let

S (n) = n + 1

be the successor function. Define

f

by primitive recursion

f (0) = 0, f (n + 1) = S (S (f (n))) .

(1)

Induction gives

f (n) = 2 n

. Then define

g (n) = S (f (n)) = 2 n + 1

(2)

by composition. Initial functions, composition, and primitive recursion produce primitive recursive functions, so

f

and

g

are partial recursive functions and are visibly defined for every

n

. Both functions are total.

n ⟼ 2 n, n ⟼ 2 n + 1

(1)

satisfy

n \in X ⟺ 2 n \in X \oplus Y, n \in Y ⟺ 2 n + 1 \in X \oplus Y .

(2)

Hence $X \leq_{m} X \oplus Y$ and $Y \leq_{m} X \oplus Y$ .

ii

 0  0

Solution

 0  0

Let

K

be the diagonal halting set and put

C = (N ∖ K) \oplus K = {2 n : n \in / K} \cup {2 n + 1 : n \in K} .

(1)

C

were a computably enumerable set, then

n \mapsto 2 n

would many-one reduce

N ∖ K

C

, making the complement of

K

computably enumerable. Together with the computable enumerability of

K

, that would make

K

a computable set, a contradiction.

Moreover

N ∖ C = K \oplus (N ∖ K) .

(2)

If this complement were computably enumerable,

n \mapsto 2 n + 1

would again make

N ∖ K

computably enumerable. Thus neither $C$ nor its complement is computably enumerable.

iii

 0  0

Solution

 0  0

Let total computable

f

and

g

witness

X \leq_{m} Z

and

Y \leq_{m} Z

. Define

h (2 n) = f (n), h (2 n + 1) = g (n) .

(1)

Parity testing and integer division by two are computable, so

h

is total computable. For every

m

m \in X \oplus Y ⟺ h (m) \in Z .

(2)

Therefore $X \oplus Y \leq_{m} Z$ .

S_{i} (t) = 1 - F_{i} (t)

for the survival function, the definition of the hazard function gives

h_{i} (t) = \frac{f _{i} ( t )}{S _{i} ( t )} = - \frac{S _{i}^{'} ( t )}{S _{i} ( t )} = - \frac{d}{d t} lo g S_{i} (t) .

(1)

Since

S_{i} (0) = 1

, integration yields

S_{i} (t) = exp [- \int_{0}^{t} h_{i} (s) d s] .

(2)

Therefore

F_{i} (t) = 1 - exp [- \int_{0}^{t} h_{i} (s) d s] .

(3)

The exponent is the negative cumulative hazard.

b

 0  0

Solution

 0  0

Let

Λ (t) = \int_{0}^{t} λ (s) d s

(1)

be the baseline cumulative hazard. Under the proportional hazards model,

h_{i} (t) = λ (t) e^{β^{T} x_{i}}, S_{i} (t) = exp [- e^{β^{T} x_{i}} Λ (t)] .

(2)

Thus

f_{i} (Y_{i}) = h_{i} (Y_{i}) S_{i} (Y_{i}) = λ (Y_{i}) e^{β^{T} x_{i}} exp [- e^{β^{T} x_{i}} Λ (Y_{i})] .

(3)

Independence makes the log likelihood

ℓ (β) = i = 1 \sum n [lo g λ (Y_{i}) + β^{T} x_{i} - e^{β^{T} x_{i}} Λ (Y_{i})] .

(4)

c

 0  0

Solution

 0  0

Fit a Poisson regression to artificial responses

Z_{i} = 1

with means

μ_{i} = Λ (Y_{i}) e^{β^{T} x_{i}} .

(1)

With the logarithmic link, this is the generalized linear model

lo g μ_{i} = β^{T} x_{i} + lo g Λ (Y_{i}),

(2)

where

lo g Λ (Y_{i})

is a known offset. Its log likelihood, apart from constants, is

ℓ_{P} (β) = \sum_{i} [lo g Λ (Y_{i}) + β^{T} x_{i} - Λ (Y_{i}) e^{β^{T} x_{i}}] .

(3)

The difference

ℓ (β) - ℓ_{P} (β) = \sum_{i} [lo g λ (Y_{i}) - lo g Λ (Y_{i})]

(4)

does not depend on

β

. The Poisson surrogate therefore has exactly the same maximum-likelihood estimate of $β$ . This is the Poisson surrogate for an uncensored proportional-hazards likelihood.

w (z) = \int_{γ} e^{z t} f (t) d t

(1)

into the equation. Since

w^{'} = \int_{γ} t e^{z t} f d t

and

w^{''} = \int_{γ} t^{2} e^{z t} f d t

, use

z e^{z t} = \partial_{t} e^{z t}

and integration by parts:

z w^{''} + 2 a w^{'} + z w = [e^{z t} (1 + t^{2}) f (t)]_{\partial γ} + \int_{γ} e^{z t} [2 a t f - \frac{d}{d t} ((1 + t^{2}) f)] d t .

(2)

The integral vanishes when

(1 + t^{2}) f^{'} = 2 (a - 1) t f,

(3)

so, up to a constant and on a consistently chosen branch,

f (t) = (1 + t^{2})^{a - 1} .

(4)

The remaining contour condition is

[e^{z t} (1 + t^{2})^{a}]_{\partial γ} = 0 .

(5)

This is the Laplace contour-integral method for a linear differential equation.

b

 0  0

Solution

 0  0

Because

Re a > 0

, the endpoint factor

(1 + t^{2})^{a}

vanishes at the branch points

t = \pm i

. A finite contour may therefore run from

- i

i

on either side of a chosen branch cut; the diagram shows contours bowing through the left and right half-planes.

Figure 1.
Contour choices for the Laplace transform
.

For

a = 1

f (t) = 1

is entire, so path independence makes either contour give, up to orientation,

\int_{- i}^{i} e^{z t} d t = \frac{e ^{i z} - e ^{- i z}}{z} = \frac{2 i s i n z}{z} .

(1)

Hence a nonzero constant multiple gives the solution

w_{1} (z) = \frac{sin z}{z} .

(2)

c

 0  0

Solution

 0  0

For real

z > 0

, the exponential decays as

Re t \to - \infty

, so two allowed contours run from

- \infty

i

and from

- \infty

- i

. For real

z < 0

, it decays as

Re t \to + \infty

, so reverse the construction: run from

i

- i

+ \infty

. These are the infinite contours in the diagram.

For

z > 0

their integrals are

\int_{- \infty}^{\pm i} e^{z t} d t = \frac{e ^{\pm i z}}{z};

(1)

for

z < 0

the corresponding orientation changes only an overall sign. Taking the sum of the two exponentials produces a solution independent of

sin z / z

w_{2} (z) = \frac{cos z}{z} .

(2)

Its nonzero Wronskian with

w_{1}

z \neq = 0

proves linear independence.

2 H \dot{H} = \frac{1}{3 M _{Pl}^{2}} (\dot{ϕ} \ddot{ϕ} + c^{2} V^{'} (ϕ) \dot{ϕ}) .

(1)

The scalar-field equation gives

\ddot{ϕ} + c^{2} V^{'} = - 3 H \dot{ϕ}

, hence

2 H \dot{H} = - \frac{H ϕ ˙ ^{2}}{M _{Pl}^{2}} .

(2)

By continuity this also holds through isolated zeros of

H

, so the Raychaudhuri equation is

\dot{H} = - \frac{ϕ ˙ ^{2}}{2 M _{Pl}^{2}} .

(3)

b

 0  0

Solution

 0  0

Differentiating the ansatz gives

\dot{ϕ} = \frac{2 λ ϕ _{0}}{s i n h ( 2 λ t )} .

(1)

The Raychaudhuri equation therefore becomes

\dot{H} = - 2 λ^{2} \frac{ϕ _{0}^{2}}{M _{Pl}^{2}} csch^{2} (2 λ t) .

(2)

Since

d [coth (2 λ t)] / d t = - 2 λ csch^{2} (2 λ t)

, the requested specific solution takes the integration constant to be zero:

H (t) = λ \frac{ϕ _{0}^{2}}{M _{Pl}^{2}} coth (2 λ t) .

(3)

Now

\overset{a}{˙} / a = H

, so

lo g a = \frac{ϕ _{0}^{2}}{2 M _{Pl}^{2}} lo g sinh (2 λ t) + lo g a_{0},

(4)

and

a (t) = a_{0} [sinh (2 λ t)]^{ϕ_{0}^{2} / (2 M_{Pl}^{2})} .

(5)

c

 0  0

Solution

 0  0

Put

u = tanh (λ t) = e^{ϕ / ϕ_{0}}

. The hyperbolic cotangent double-angle identity gives

coth (2 λ t) = \frac{1 + u ^{2}}{2 u} = cosh (\frac{ϕ}{ϕ _{0}}),

(1)

H (ϕ) = λ \frac{ϕ _{0}^{2}}{M _{Pl}^{2}} cosh (\frac{ϕ}{ϕ _{0}}) .

(2)

Also

csch^{2} (2 λ t) = cosh^{2} (\frac{ϕ}{ϕ _{0}}) - 1.

(3)

Solving the Friedmann equation for the scalar potential,

c^{2} V = 3 M_{Pl}^{2} H^{2} - \frac{1}{2} \dot{ϕ}^{2},

(4)

therefore gives

V (ϕ) = \frac{2 λ ^{2} ϕ _{0}^{2}}{c ^{2}} [(\frac{3 ϕ _{0}^{2}}{2 M _{Pl}^{2}} - 1) cosh^{2} (\frac{ϕ}{ϕ _{0}}) + 1] .

(5)

d

 0  0

Solution

 0  0

Write

r = ϕ_{0}^{2} / M_{Pl}^{2}

. As

t \to 0

tanh (λ t) \sim λ t, sinh (2 λ t) \sim 2 λ t,

(1)

ϕ \to - \infty

and

a (t) \sim constant t^{r /2} .

(2)

Because

2/3 < r < 2

, the power

r /2

lies in

(1/3, 1)

; thus

\overset{a}{¨} < 0

and the early expansion decelerates. As

t \to \infty

ϕ \to 0

and

sinh (2 λ t) \sim e^{2 λ t} /2

, giving

a (t) \sim constant e^{λ r t},

(3)

so the late universe has accelerating expansion.

The transition satisfies

\overset{a}{¨} / a = H^{2} + \dot{H} = 0

. Substitution gives

r^{2} coth^{2} (2 λ t) - 2 r csch^{2} (2 λ t) = 0,

(4)

r cosh^{2} (2 λ t) = 2

. Therefore

t_{acc} = \frac{1}{2 λ} arcosh (\frac{2 M _{Pl}^{2}}{ϕ _{0}^{2}}) .

(5)

This is the transition described by the exact hyperbolic-sine scalar-field cosmology.

16G (Logic and Set Theory)

 0  0

Solution

 0  0

Ordinal exponentiation is defined by transfinite recursion:

α^{0} = 1, α^{β + 1} = α^{β} α, α^{λ} = sup_{ξ < λ} α^{ξ}

(1)

when

λ

is a nonzero limit ordinal. If

α \geq 1

, each successor step and each supremum show that

β \mapsto α^{β}

is nondecreasing. If

α \geq 2

, transfinite induction strengthens this to strict increase:

α^{β} < α^{β + 1}

, and the value at a limit exceeds every earlier value.

Strict increase can disappear when the base changes. For example, with

ω < ω + 1 < ω + 2

(ω + 1)^{ω} = (ω + 2)^{ω} = ω^{ω},

(2)

because for every positive finite

n

, both finite powers have leading term

ω^{n}

, and taking the supremum gives

ω^{ω}

We next prove

α^{β + γ} = α^{β} α^{γ} .

(3)

Apply transfinite induction to

γ

. The zero and successor cases follow directly from the recursive definitions and the associativity of ordinal multiplication. At a limit

λ

, continuity of ordinal multiplication in its right argument gives

α^{β + λ} = sup_{ξ < λ} α^{β + ξ} = sup_{ξ < λ} α^{β} α^{ξ} = α^{β} α^{λ} .

(4)

The superficially similar identity

(α β)^{γ} = α^{γ} β^{γ}

is false: for

α = ω

β = 2

, and

γ = 2

(ω 2)^{2} = ω^{2} 2 \neq = ω^{2} 4 = ω^{2} 2^{2} .

(5)

Finally,

α^{ω_{1}} \geq ω_{1} ⟺ α \geq 2, α^{ω_{1}} \geq ω_{2} ⟺ α \geq ω_{2} .

(6)

For the first equivalence, bases zero and one fail, while strict increase embeds every countable ordinal into the powers of any base

α \geq 2

. For the second,

α \geq ω_{2}

immediately gives

α^{ω_{1}} \geq α

. Conversely, if

α < ω_{2}

, then

∣ α ∣ \leq ℵ_{1}

. Every exponent below the first uncountable ordinal

ω_{1}

is countable, so each

α^{β}

has cardinality at most

ℵ_{1}

; the supremum of

ℵ_{1}

such ordinals still has cardinality at most

ℵ_{1}

and is therefore below the second uncountable ordinal

ω_{2}

d_{n} (H) = \frac{ex ( n , H )}{( 2 n )} .

(1)

Let

G

be an

H

-free graph on

n

vertices with

ex (n, H)

edges, and choose a uniformly random set of

m < n

vertices. Its induced subgraph is still

H

-free, and each edge survives with probability

(2 m) / (2 n)

. Hence

ex (m, H) \geq ex (n, H) \frac{( 2 m )}{( 2 n )},

(2)

d_{m} (H) \geq d_{n} (H)

. Thus the normalized extremal number is nonincreasing and bounded below by zero, proving that

n \to \infty lim \frac{ex ( n , H )}{( 2 n )} exists .

(3)

b

 0  0

Solution

 0  0

The Erdős-Stone theorem states that if the chromatic number of

H

r + 1 \geq 2

, then

ex (n, H) = (1 - \frac{1}{r} + o (1)) (2 n) .

(1)

H

is a bipartite graph with at least one edge, its chromatic number is two, so

r = 1

and therefore

n \to \infty lim \frac{ex ( n , H )}{( 2 n )} = 0.

(2)

c

 0  0

Solution

 0  0

First consider a

K_{t, t}

-free bipartite graph with parts

X, Y

, each of size at most

n

, and

m

edges. Count pairs

(S, y)

in which

S

is a

t

-element subset of the graph neighbourhood of

y \in Y

. Any

t

vertices of

X

have at most

t - 1

common neighbours, since

t

common neighbours would form the complete bipartite graph

K_{t, t}

. Consequently

\sum_{y \in Y} (t d ( y )) \leq (t - 1) (t ∣ X ∣) .

(1)

If the average degree of a vertex is bounded in terms of

t

, then

m = O (n)

and the required result is immediate. Otherwise, convexity of

x \mapsto (t x)

and the preceding inequality give

∣ Y ∣ (t m /∣ Y ∣) = O (n^{t}),

(2)

and hence

m = O (n^{2 - 1/ t})

. Every graph has a bipartite spanning subgraph containing at least half its edges, obtained by choosing a random bipartition. Applying the bipartite estimate to that subgraph proves the Kővári–Sós–Turán theorem in the required form:

ex (n, K_{t, t}) = O (n^{2 - 1/ t}) .

(3)

The stated "nice" subsets of the finite cyclic group

Z_{n}

are Sidon sets. If

a - b = c - d, a \neq = b, c \neq = d,

(4)

then

a + d = c + b

. Niceness forces

(a, b) = (c, d)

; the alternative pairing would force

a = b

. Thus the

∣ A ∣ (∣ A ∣ - 1)

ordered nonzero differences are distinct elements of the

n - 1

nonzero residue classes. Therefore

∣ A ∣ (∣ A ∣ - 1) \leq n - 1,

(5)

f (n) \leq \frac{1 + 4 n - 3}{2} = O (n) .

(6)

18I (Galois Theory)

 0  0

Solution

 0  0

Let

G

be the Galois group of a polynomial of the irreducible quartic. Irreducibility makes

G

a transitive subgroup of

S_{4}

. The three roots of the given cubic resolvent of a quartic correspond to the three partitions of the four quartic roots into two unordered pairs, and the kernel of the