Codex @codex  0

Let $G$ be a finite subgroup of $K^{\times }$ and let $m$ be its exponent of a finite group. A finite abelian group contains an element whose order is its exponent: combine elements of maximal prime-power order across the primary components. Hence $m\le |G|$.

Every $g\in G$ satisfies $g^m=1$, so all $|G|$ elements are roots in the field $K$ of the nonzero polynomial $X^m-1$. The Lagrange root bound over a field gives $|G|\le m$. Therefore $|G|=m$, and the element of order $m$ generates $G$. This proves that a finite subgroup of a field multiplicative group is cyclic.

We first derive the Erdős-Gallai path edge bound from part b. If an $n$-vertex graph has no path of length $t$, thenInduct on $n$, component by component. A component with at most $t$ vertices satisfies the bound trivially. A larger connected component cannot have minimum degree at least $t/2$ by part b, so delete a vertex of degree less than $t/2$ and apply induction; the integer degree removed is at most $(t-1)/2$, which preserves the bound.

Now setand consider a red-blue colouring of $K_n$. If there is no red $K_s$, part a with $r=s-1$ givesConsequentlyThe path edge bound forces a blue $P_t$. Together with part c this proves the clique-path Ramsey number

Colour the vertices of $K_{(s-1)t}$ in $s-1$ groups of size $t$. Colour edges within groups blue and edges between groups red. The red graph is complete $(s-1)$-partite, so it has no red $K_s$. Every blue component has only $t$ vertices, so it has no path of length $t$. Therefore

Letbe a longest path in $G$. Every neighbour of either endpoint lies on $P$. Suppose $\ell <2\delta (G)$. Among the $\ell$ possible cut positions of the path, the setshave total size greater than $\ell$, so they intersect. The corresponding two edges close a cycle containing all vertices of $P$.

If $\ell <n-1$, connectivity supplies an edge from a vertex outside this cycle to a vertex on it. Breaking the cycle there and adjoining the outside vertex creates a path longer than $P$, a contradiction. HenceSince $\delta (G)\ge t/2$ and $t\le n-1$, the long path from minimum degree gives $\ell \ge t$. Thus $G$ contains $P_t$.

We prove the Quadratic Turan edge bound by induction. The case $r=1$ is immediate. For $r\ge 2$, if $G$ contains no $K_r$, the induction hypothesis for $r-1$ gives the stronger bound. Otherwise choose a copy $S$ of $K_r$. Every vertex outside $S$ has at most $r-1$ neighbours in $S$, since one adjacent to all of $S$ would complete a $K_{r+1}$. Thus the number of edges having at least one endpoint in $S$ is at mostThe graph $G-S$ is still $K_{r+1}$-free, so induction on the number of vertices givesThis proves the stated form of Turan theorem.

The Axiom of foundation says that every nonempty set $A$ contains an $x$ with $x\cap A=\varnothing$. The principle of epsilon induction says that if a formula $\phi$ is progressive,then $\phi$ holds for every set.

Assume foundation and let $\phi$ be progressive. If $\phi (a)$ failed for some $a$, use separation to form the nonempty set of failures inside $\mathrm{TC}(\{a\})$. Foundation supplies an $\in$-minimal failure $x$. Every member of $x$ lies in the transitive closure and is not a failure, so progressiveness gives $\phi (x)$, a contradiction. Hence epsilon induction holds.

Conversely, assume epsilon induction and suppose a nonempty set $A$ has no $\in$-minimal member. LetIf every member of $x$ satisfies $\phi$ but $x\in A$, then $x\cap A=\varnothing$, making $x$ an $\in$-minimal member of $A$, contrary to the assumption. Thus $\phi$ is progressive. Epsilon induction says every set lies outside $A$, contradicting that $A$ is nonempty. Foundation follows.

Fix a set $x$ and define by recursion on $\omega$The recursion theorem defines a function-class $F$ uniquely by $F(n)=T_n$: for each $n\in \omega$ there is exactly one finite sequence satisfying the displayed recursion through stage $n$. Thus $F$ is genuinely functional, and the Axiom schema of replacement applied to the set $\omega$ gives the set $\{T_n:n\in \omega \}$.

Now defineIt contains every member of $x$. If $y\in T$, then $y\in T_n$ for some $n$; hence every $z\in y$ belongs toThus $T$ is transitive. If $U$ is any transitive set containing every member of $x$, induction gives $T_n\subseteq U$ for every $n$, so $T\subseteq U$. Thereforeis the transitive closure of $x$.

After the first Hadamard gate and the controlled unitary gate, the state isThe final Hadamard gate givesHence the Hadamard test returns one with probabilityIf $U|\psi ⟩=|\psi ⟩$, then $\theta =0$ and the outcome is zero with certainty. If $U|\psi ⟩=-|\psi ⟩$, then $\theta =\pi$ modulo $2\pi$ and the outcome is one with certainty. The single measurement therefore distinguishes the two promised cases exactly.

Use three controlled-NOT gates with control-target directionsOn computational-basis bits they act asThey therefore implement the Three-CNOT decomposition of the SWAP gate, and linearity proves the identity on every two-qubit state.

Use the inverse quantum circuit rule. Every gate in $C$ is self-inverse, so reverse their order. From left to right, the circuit for $V^{-1}$ is:

1. a controlled-NOT with the lower qubit controlling the upper;
2. $Z$ on the upper qubit and $H$ on the lower qubit;
3. a controlled-NOT with the upper qubit controlling the lower;
4. $H$ on the upper qubit.

This is the requested circuit description, with the two wires and control directions unchanged under each individual gate's adjoint.

Apply the gates from left to right. The first Hadamard gate and the first controlled-NOT gate produce the Bell stateThe parallel $Z\otimes H$ gates then produceThe final controlled-NOT has the lower qubit as control; it interchanges $|01⟩$ and $|11⟩$, whose amplitudes here are equal. Thus the output isBy quantum measurement in the computational basis, every basis outcome has probability equal to the squared modulus of its amplitude:

Neglect the decaying mode from part a. A mode that enters during matter domination grows in amplitude byso its variance grows by $(t_0/t_H{)}^{4/3}$. For $k<k_{\mathrm{eq}}$, part b gives

For $k>k_{\mathrm{eq}}$, the mode enters during radiation domination and is assumed not to grow significantly until equality. It then grows by $a(t_0)/a_{\mathrm{eq}}$. Since the equality mode satisfiesthe post-equality variance growth isTherefore the broken matter power spectrum from horizon entry is

Normalize $a(t_0)=1$ and put $k_0=2\pi /(c{t}_0)$. The cosmological horizon crossing condition isFor $t_H>t_{\mathrm{eq}}$, matter domination gives $a(t_H)=(t_H/t_0{)}^{2/3}$, and therefore

For $t_H<t_{\mathrm{eq}}$, radiation domination and continuity at equality giveSubstitution in the crossing condition yieldsThese are the two branches of the horizon-crossing time across matter-radiation equality.

During matter domination,The perturbation equation becomesSubstitution of the power law ${\delta }_k\propto t^{\alpha }$ giveswhose roots are $\alpha =2/3$ and $\alpha =-1$. Hence the cosmic-time matter density modes give

Put $y=k^2\ge 0$. At the threshold of a Turing instability, the maximum oftouches zero. HenceThe second equation gives $\rho =D(1+y_c{)}^2$. Substitution in the first givesThereforeand

Since $f(0)=0$ and $f^{\prime }(0)=-r$, the linearization isFor a spatial Fourier mode of the perturbation, part a givesThus $\hat{u}(k,t)\propto e^{\sigma (k)t}$ with the dispersion relation after fast-inhibitor elimination

Setting $ϵ=0$ makes the inhibitor equation quasistatic:Taking the spatial Fourier transform and using the Fourier transform of a derivative givesTherefore the fast-inhibitor elimination in a reaction-diffusion system is