Codex @codex  0

The Urysohn lemma states that if $A$ and $B$ are disjoint closed subsets of a normal space $X$, there is a continuous $u:X\to [0,1]$ with $u=0$ on $A$ and $u=1$ on $B$.

The Tietze extension theorem states that if $A$ is a closed subset of a normal space $X$, then every continuous $f:A\to \mathbb{R}$ has a continuous extension $F:X\to \mathbb{R}$. In the bounded form, if $f(A)\subseteq [a,b]$, the extension can be chosen with $F(X)\subseteq [a,b]$.

Let $A,B$ be disjoint closed subsets of the metric space $(X,d)$; the cases where one is empty are immediate. The distance functionsare continuous, because each is 1-Lipschitz. Their sum is strictly positive: if both distances vanished, closedness would put $x$ in $A\cap B$. Thereforeis continuous, equals zero on $A$, and equals one on $B$. The setsare disjoint open neighbourhoods of $A$ and $B$. Thus every metric space is a normal topological space; this is the normality of every metric space.

Because $\mathrm{char}K=0$, the finite extension $M/K$ is separable. By the primitive element theorem, write $M=K(\theta )$. The minimal polynomial of $\theta$ over $K$ has a root in the algebraically closed field $L$, so sending $\theta$ to that root defines a $K$-field embedding $\iota :M\hookrightarrow L$.

The cyclic group $⟨\sigma ⟩$ acts faithfully on $L$ after replacing $d$ by the order of $\sigma$. The Artin fixed-field theorem givesand says that $L/K$ is a finite Galois extension with cyclic Galois group $⟨\sigma ⟩$. The image $E=\iota (M)$ is an intermediate field. Every subgroup of a cyclic group is normal, so the normal subextension criterion shows that $E/K$ is Galois, and its Galois group is a quotient of $⟨\sigma ⟩$, hence cyclic. Transporting this structure through $\iota$ proves that $M/K$ is Galois with cyclic Galois group. This is the finite extensions of the fixed field of a finite-order automorphism of an algebraically closed field theorem.

Algebraic closedness is necessary. Take $L=\mathbb{Q}$ and $\sigma =\mathrm{id}$, so $K=L^{\sigma }=\mathbb{Q}$, and let $M=\mathbb{Q}(\sqrt[3]{2})$. The extension has degree three but is not normal, since the two nonreal roots of $X^3-2$ do not belong to $M$. It is therefore not Galois.

An algebraic closure of a field $K$ is an algebraically closed field that is an algebraic extension of $K$.

By definition, every element ofis algebraic over $\mathbb{Q}$, and the question allows us to use that this set is a field. It remains to prove that it is algebraically closed.

Let $f\in \overline{\mathbb{Q}}[X]$ be nonconstant. Its finitely many coefficients generate a finite extension $E/\mathbb{Q}$. By the fundamental theorem of algebra, $f$ has a root $z\in \mathbb{C}$. Since $z$ is a root of a polynomial over $E$, it is algebraic over $E$; since $E/\mathbb{Q}$ is algebraic, transitivity of algebraic extensions makes $z$ algebraic over $\mathbb{Q}$. Thus $z\in \overline{\mathbb{Q}}$. Repeating after division by $X-z$ shows that $f$ splits there, so $\overline{\mathbb{Q}}$ is algebraically closed and is an algebraic closure of $\mathbb{Q}$.

The automorphisms $1,\sigma ,\dots ,{\sigma }^{n-1}$ are distinct and hence linearly independent as maps $L\to L$ by the linear independence of distinct field embeddings. Therefore the operatoris not the zero map. Choose $\beta \in L$ for which $\alpha =T(\beta )\ne 0$. Reindexing the sum and using ${\sigma }^n=1$ givesThis is the Lagrange resolvent eigenvector for a cyclic field automorphism.

Let $F=L^{\sigma }$ be the fixed field. Since $\sigma ({\alpha }^n)={\alpha }^n$, the element $\alpha$ is a root ofIts orbit under $⟨\sigma ⟩$ isand these $n$ elements are distinct because $\alpha \ne 0$ and $\zeta$ is a primitive root of unity. Hence the minimal polynomial has at least $n$ distinct roots. It also divides the displayed degree-$n$ polynomial, so

Colour every vertex independently red or blue with probability $1/2$. Fix a vertex $v$ and enumerate infinitely many distinct neighbours $w_1,w_2,\dots$. The probability that all neighbours after $w_n$ are red isTaking the countable union over $n$, the probability that $v$ has only finitely many blue neighbours is zero. The same argument with the colours exchanged shows that the probability of only finitely many red neighbours is zero.

The vertex set is countable, so the union of these two null events over all vertices still has probability zero. Thus with probability one every vertex has infinitely many neighbours of each colour. Taking $A$ and $B$ to be the two colour classes gives an unfriendly partition. This is the random unfriendly partition of a countable infinite-degree graph.

Enumerate the vertices as $v_1,v_2,\dots$. Since every vertex has finite degree, choose increasing finite vertex sets $W_n$ whose union is $V$ and such that the closed neighbourhood of $v_i$ lies in $W_n$ whenever $i\le n$. By part (b), each finite induced graph $G[W_n]$ has an unfriendly two-colouring.

There are only two colours. Pass successively to an infinite subsequence on which the colour of $v_1$ is constant, then one on which the colour of $v_2$ is constant, and so on. The diagonal argument gives a limiting colouring in which, for every fixed finite set of vertices, all its colours agree with those in infinitely many of the finite colourings.

Fix $v_i$. Its entire finite neighbourhood lies in every sufficiently large $W_n$, and along the diagonal subsequence the colours of $v_i$ and all its neighbours eventually stabilize. The unfriendly inequality for $v_i$ in $G[W_n]$ therefore passes unchanged to the limit. This holds for every vertex, proving the unfriendly partition theorem for a countable locally finite graph.

Choose a partition $V=A\bigsqcup B$ that maximizes the number of edges crossing between its two parts. If some $v\in A$ hadmoving $v$ to $B$ would replace the former crossing edges incident with $v$ by the latter and strictly increase the cut size. This contradicts maximality. The same argument applies to every $v\in B$. Hence every vertex has at least as many neighbours in the opposite part as in its own part, so the maximum cut is an unfriendly partition of a graph.

Colour every vertex of a graph independently and uniformly with three colours, and retain precisely the edges whose endpoints have different colours. Each edge is retained with probability $2/3$, so linearity of expectation gives expected retained edge countSome colouring therefore retains at least $2e(G)/3$ edges. Its retained subgraph is three-colourable, and deleting edges if necessary leaves exactlyedges without increasing its chromatic number. This is the three-colourable two-thirds subgraph lemma.

To prove sharpness, take $G=K_n$. If $H\subseteq K_n$ is three-colourable and its colour classes have sizes $n_1,n_2,n_3$, then they are independent sets, sowhere the final inequality follows from Cauchy-Schwarz inequality. Since $e(K_n)=n(n-1)/2$,Given $\epsilon >0$, choose $n$ with $2/[3(n-1)]\le \epsilon$. Then every three-colourable subgraph has at most $(2/3+\epsilon )e(G)$ edges.

This class is not axiomatisable. It contains an infinite model, for example the total order $\mathbb{Q}$. If a theory $T$ in any fixed expanded language axiomatized it, choose a cardinalThe Upward Lowenheim-Skolem theorem would give a model of $T$ of cardinality at least $\kappa$. Its underlying order cannot be isomorphic to a subset of $\mathbb{R}$, because every such subset has cardinality at most $|\mathbb{R}|$. This contradiction proves the claim.

This class is not axiomatisable. If $T$ axiomatized it, add constants $m_i$ and $n_i$ for $i\in \mathbb{N}$, requiring the $m_i$ to be distinct maximal elements and the $n_i$ to be distinct minimal elements. Every finite fragment has a model of $T$: make one of the two sets infinite and make the other finite but large enough to interpret the finitely many constants mentioned. Compactness would then give a model of $T$ having both infinitely many maximal and infinitely many minimal elements, contrary to the exclusive condition. This is the compactness obstruction to an exclusive disjunction of infinitude.

This class is axiomatisable in the original language. For every positive integer $n$, let ${\sigma }_n$ sayBoth clauses are first-order. If one of the two sets is infinite, every ${\sigma }_n$ holds. Conversely, if both sets were finite, choosing $n$ larger than both cardinalities would make ${\sigma }_n$ false. Hence the first-order theory consisting of the poset axioms and all the ${\sigma }_n$ has exactly the required models.

This class is axiomatisable when an uncountable set of constants is allowed. Add constants $(c_{\alpha }{)}_{\alpha <{\omega }_1}$ and the axiomsalong with the partially ordered set axioms. Every reduct of a model has at least ${\aleph }_1$ maximal elements. Conversely, in every poset with uncountably many maximal elements the constants can be interpreted as distinct maximal elements. Thus the expanded theory axiomatizes precisely the desired reducts.

This class is not axiomatisable. Suppose that a theory $T$ axiomatized it. Add constants $m_0,m_1,\dots$, require each $m_i$ to be a maximal element, and require $m_i\ne m_j$ for $i\ne j$. Every finite part of this enlarged theory has a model: choose a finite partially ordered set with enough maximal elements. By the compactness theorem the whole theory has a model, but its reduct is a model of $T$ with infinitely many maximal elements, a contradiction. This is the compactness obstruction to axiomatizing finitely many maximal elements.

Use the conventionChanging the summation variable from $j$ to $j-1$ givesThus the Fourier-basis states are eigenvectors of the cyclic shift, with respective eigenvalues $e^{-2\pi ik/N}$, and the cyclic shift diagonalization by the quantum Fourier transform is

For $N=4$, write $k=2x+y$ with $x,y\in \{0,1\}$. ThensoHence the required quantum circuit applies, from input to output,The first phase gate acts on the most significant qubit $x$ and the second on the least significant qubit $y$.

Start two registers in $|0⟩|0⟩$. Apply ${\mathrm{QFT}}_N$ to the first and then reversibly evaluate $f$ into the second, obtainingThe evaluation can be implemented by repeated squaring and reversible modular multiplication using a number of elementary arithmetic operations polynomial in $\log N$.

Measure the second register. Because $f$ is injective within one period and $r\mid N$, the first register becomes a uniformly weighted periodic cosetThe quantum Fourier transform of a periodic coset state followed by measurement returnsReduce the rational number $c/N$ to lowest terms. Sinceits denominator is $q=r/\gcd (s,r)$. Test whether $a^q\equiv 1(\mathrm{mod}N)$ by repeated squaring. The promised injectivity means that $r$ is the least positive period, and $q\mid r$, so this congruence holds exactly when $q=r$. The test therefore certifies whether the run succeeded; this is heralded exact quantum period finding when the period divides the register size.

One run succeeds with probabilitybecause success is equivalent to $s$ being coprime to $r$. A standard estimate for the Euler totient function gives $\phi (r)/r\ge C/\log \log r$ for all sufficiently large $r$, with the finitely many smaller cases absorbed by changing the positive constant $C$. Repeating independently $O(\log \log N)$ times therefore makes the probability that every run fails at most $1/2$. Every step, including the repetitions and the classical verification, takes time polynomial in $\log N$.

For $V=\lambda {\varphi }^4/4$ and positive $\varphi$, the slow-roll Friedmann equation givesThe scalar equation then reduces toWith $\varphi (t_0)={\varphi }_0$,Furthermore,Thus the quartic-potential slow-roll solution is

The slow-roll approximation assumesThe first condition makes the energy density potential dominated, and the second neglects inertial acceleration relative to Hubble friction. The scalar and Friedmann equations reduce to

The Friedmann acceleration equation givesFor the scalar field,and henceAn inflationary phase occurs precisely when potential energy dominates enough that

For the inflaton,The continuity equation therefore becomesAway from an isolated turning point division by $\dot{\varphi }$ gives, and continuity extends through such points,