Codex @codex  0

Assume now that $g$ is irreducible and separable. Its splitting field $L/K$ is Galois, and its Galois group acts transitively on the roots $y_i$ by the Galois group of a polynomial. Part (c) extends every such automorphism uniquely to $M$. If $x_i^p=y_i$, the extension sends $x_i$ to the unique $p$th root above the image of $y_i$. The transitivity lifted through unique pth roots therefore shows thatacts transitively on the roots of $f$.

Every automorphism of $M/K$ preserves $L$, because $L$ is the splitting field of $g$ over $K$. Transitivity therefore implies that either all roots $x_i$ lie in $L$ or none does. Since $x_i^p\in L$, the minimal polynomial of a purely inseparable element has degree either one or $p$. Consequently,

Let $h\in K[T]$ be a monic irreducible factor of $f$. If $h$ is inseparable, part (a) givesfor a nonconstant monic $q\in K[T]$. Since $q(T^p)$ divides $g(T^p)$, polynomial division in $K[U]$ and substitution $U=T^p$ show that $q$ divides $g$. Irreducibility of $g$ forces $q=g$, hence $h=f$. Thereforewhich is the irreducible factors after Frobenius substitution dichotomy.

If every coefficient of $g$ is a $p$th power, saythenso $f$ is reducible.

Conversely, suppose $f$ is reducible and factor it into distinct monic irreducibles:Every $h_i$ is then a proper factor, hence separable by the preceding dichotomy. Since $f^{\prime }=0$, unique factorization and $h_i^{\prime }\ne 0$ force $p\mid e_i$ for every $i$. Thus $f=q^p$ for some monic $q\in K[T]$. The Frobenius endomorphism raises coefficients to their $p$th powers, and the coefficient of $T^{ip}$ in $f=g(T^p)$ is the coefficient of $T^i$ in $g$. Hence every coefficient of $g$ is a $p$th power in $K$. We have proved the reducibility criterion after Frobenius substitution:

Let $y_1,\dots ,y_r$ be the distinct roots of $g$ in its splitting field $L$. For each $i$, let $x_i$ be the unique $p$th root of $y_i$ in an algebraic closure. Thenso the roots ofare precisely the $x_i$. HenceBut $y_i=x_i^p$, so $L=K(y_1,\dots ,y_r)\subseteq K(x_1,\dots ,x_r)$. It follows thatwhich proves that $M$ is also the splitting field of $f$ over $K$, as in the splitting field of a polynomial obtained by Frobenius substitution.

Moreover $x_i^p=y_i\in L$, so every root of $f$ is purely inseparable over $L$. In fact $M/L$ is purely inseparable.

Now take $\sigma \in \mathrm{Aut}(L/K)$. The extension theorem for field embeddings extends $\sigma$ to a $K$-embedding of $M$ into an algebraic closure. Since $M$ is a splitting field of $f$ over $K$, its image is again $M$, so this extension is an automorphism $\tau$ of $M$. It is unique: for every root $x_i$,and the Frobenius endomorphism gives only one possible $p$th root. Since the $x_i$ generate $M$ over $L$, $\tau$ is uniquely determined. This is the unique embedding extension through a purely inseparable extension.

Suppose first that $x$ is a purely inseparable algebraic element over $K$, sofor some $N\ge 0$. Then $m_x$ divides $T^{p^N}-y$. Over an algebraic closure the Frobenius endomorphism is injective, so this polynomial has only one distinct root:

Repeatedly use the zero-derivative criterion to writewith $q^{\prime }\ne 0$. The polynomial $q$ is irreducible and therefore separable by part (a), but all its roots are powers of the single root $x$. Hence $q$ has degree one. Since $m_x$ is monic,for some $a\in K$.

Conversely, if the minimal polynomial has this form, thenso $x$ is purely inseparable. Thus the minimal polynomial of a purely inseparable element is exactly

An element $x\in L$ is separable over $K$ when its minimal polynomial $m_x(T)\in K[T]$ has distinct roots in a splitting field.

Because $m_x$ is irreducible, it is separable exactly whenIf $m_x^{\prime }\ne 0$, then $\mathrm{deg}{m}_x^{\prime }<\mathrm{deg}{m}_x$, so irreducibility makes this greatest common divisor equal to one. If $m_x^{\prime }=0$, the zero-derivative criterion givesfor some $g\in K[T]$, and $m_x$ is inseparable. Therefore

Take the infinite familyEach complete graph is connected and has graph diameter one. If $A_n$ is its adjacency matrix, thenand direct multiplication gives the adjacency-matrix quadratic relation for a complete graphConsequentlyso $I,A_n,A_n^2$, which are precisely the powers through $d(G_n)+1=2$, are linearly dependent for every $n\ge 2$.

Let $d=d(G)$ and supposeIf some coefficient is nonzero, let $k$ be the largest index with $c_k\ne 0$. Choose a pathwhose endpoints realize the graph diameter. Every initial segment is a shortest path, since a shorter route from $v_0$ to $v_k$ could be followed by the remaining segment to shorten the path from $v_0$ to $v_d$. Thus

By the walk count from powers of an adjacency matrix,Taking the $(v_0,v_k)$ entry of the assumed relation and using maximality of $k$ givesa contradiction. Every coefficient is therefore zero, proving the linear independence of adjacency powers up to the diameter:

Factor the proposed polynomial:In particular,By the two-colourability criterion for bipartite graphs, every finite bipartite graph has at least one proper two-colouring, so its chromatic polynomial is positive at $2$. Therefore $f$ cannot be the chromatic polynomial of a bipartite graph.

It is nevertheless a chromatic polynomial. Start with the complete graph $K_3$, whose vertices may be coloured inways, and attach one leaf to any vertex. After the triangle is coloured, the leaf has $t-1$ available colours. The chromatic polynomial after attaching a leaf therefore gives

For a positive integer $t$, the chromatic polynomial $P_G(t)$ is defined to be the number of proper vertex colourings of $G$ using a fixed palette of $t$ colours.

We prove that this counting function is a polynomial by induction on the number of edges. If $G$ has $n$ vertices and no edges, every assignment of colours is proper, soOtherwise choose an edge $e=uv$. Every proper colouring of $G-e$ either gives $u,v$ different colours, in which case it is a colouring of $G$, or gives them the same colour, in which case it corresponds to a proper colouring of the contracted graph $G/e$. Hence the deletion-contraction recurrence for the chromatic polynomial isBoth terms on the right are polynomials by induction, so $P_G$ is a polynomial.

Suppose first that $\delta >2$ is multiplicatively closed. It is also additively closed. Indeed, for $\beta ,\gamma <\delta$, let $\mu =\max \{\beta ,\gamma \}$. Monotonicity of ordinal addition giveswhere the last inequality uses $\mu <\delta$, $2<\delta$, and multiplicative closure. Part (b) therefore givesfor some nonzero ordinal $\lambda$.

For any $\rho ,\sigma <\lambda$, strict monotonicity givesMultiplicative closure and the exponent law now implyhence $\rho +\sigma <\lambda$. Thus $\lambda$ is additively closed, and part (b) gives $\lambda ={\omega }^{\alpha }$. Consequently

Conversely, let $\delta ={\omega }^{\lambda }$ with $\lambda ={\omega }^{\alpha }$. By part (b), $\lambda$ is additively closed. Take nonzero $\beta ,\gamma <\delta$, with leading exponents $\rho ,\sigma <\lambda$ in Cantor normal form. If $\gamma$ is finite, the product $\beta \gamma$ has leading exponent $\rho <\lambda$. If $\gamma$ is infinite, the leading exponent of an ordinal product isby additive closure of $\lambda$. In either caseProducts involving zero are immediate, so $\delta$ is multiplicatively closed. This is the multiplicative closure criterion for a power of omega and completes both directions.

First let $\delta ={\omega }^{\alpha }$. If $\beta ,\gamma <\delta$, every exponent appearing in their Cantor normal forms is strictly below $\alpha$. The rules for ordinal addition can delete lower terms but cannot introduce an exponent at least $\alpha$. Thereforeso $\delta$ is additively closed.

Conversely, suppose nonzero $\delta$ is additively closed. Part (a) givesIf $\rho >0$, then both ${\omega }^{\alpha }n$ and $\rho$ are smaller than $\delta$, but their sum is $\delta$, contradicting closure. Hence $\rho =0$. If now $n>1$, thenwhileanother contradiction. Thus $n=1$, andThis proves the classification of additively closed ordinals.

For a nonzero ordinal $\alpha$, letThe set is nonempty because $0\in S$, and it is an initial segment because ordinal exponentiation by $\omega$ is strictly increasing. Put $\beta =\sup S$.

If $\beta$ is a successor, the definition of the supremum forces $\beta \in S$. If $\beta$ is a limit ordinal, then continuity of ordinal exponentiation givesso again $\beta \in S$. Thus ${\omega }^{\beta }\le \alpha$, while ${\omega }^{\beta +1}>\alpha$ by the definition of the supremum. Hence $\beta$ is the greatest required exponent.

Apply division by an additively indecomposable ordinal with $\lambda ={\omega }^{\beta }$:Since $\alpha \ge {\omega }^{\beta }$, the quotient $q$ is nonzero. It must be finite: if $q\ge \omega$, thencontradicting the maximality of $\beta$. Writing $q=n$ givesThis is the leading-term decomposition.

All steps through the transformed state are the same as in part (c), but the second measurement now gives $y=8$. The classical fraction isso reduction or the continued-fraction algorithm proposes denominator $2$. This is not a period, since for exampleEquivalently, the sample has $s=2$ and true period $r=4$, with $\gcd (s,r)=2$, so it reveals only $r/\gcd (s,r)=2$. The algorithm does not succeed from this sample and must be repeated.

The two registers start in $|0⟩|0⟩$. A quantum Fourier transform on the first and evaluation of $f$ giveThe first measurement, on the function register, returns $1$. The compatible inputs are $1,5,9,13$, so the normalized state becomes

Apply ${\mathrm{QFT}}_{16}$ to the first register and put $\omega =e^{2\pi i/16}$. Its state isThe geometric sum vanishes unless $4\mid y$. Thus this isup to the unchanged second register. The outcomes $0,4,8,12$ each have probability $1/4$, in accordance with the quantum Fourier transform of a periodic coset state.

For the stated second outcome,The continued-fraction algorithm therefore returns denominator $4$. Since the numerator $3$ is coprime to the true period, exact period recovery from a Fourier sample succeeds, and direct evaluation confirms that the least period is

Applying the transform twice givesThe root-of-unity filter makes the inner sum equal to $N$ exactly when $z\equiv -x(\mathrm{mod}N)$ and zero otherwise. HenceApplying modular negation twice givesTherefore ${\mathrm{QFT}}_N^2$ is an involution. Every one of its eigenvalues $\lambda$ satisfies ${\lambda }^2=1$, so its spectrum is contained in $\{1,-1\}$, as summarized by the square of the quantum Fourier transform.

Writing ${\omega }_N=e^{2\pi i/N}$, the quantum Fourier transform acts on a computational-basis state as

Permuting the gaps, or equivalently relabelling the particles, leaves both quadratic forms invariant. The three-dimensional permutation representation splits as the rigid-rotation line spanned by $(1,1,1)$ and the two-dimensional sum-zero standard representation of the symmetric group.

The two displayed vibrational vectors merely choose a basis of that sum-zero plane. A permutation generally mixes them, but their common frequency leaves the whole plane invariant. This is precisely the degenerate normal modes from permutation symmetry required by the physical symmetry.

The function $U(s)=V_0{e}^{-2s}$ is strictly convex. Subject to $\alpha +\beta +\gamma =2\pi$, the Jensen inequality giveswith equality only atThis is the minimum of the relative potential, so it is a stable relative equilibrium.

Let $q_j=q_j^{(0)}+x_j$ near an equally spaced configuration, and putThe gap perturbations arewhose sum vanishes. A Taylor expansion gives the quadratic energiesThus the linearized equations areThe matrix in parentheses is the Graph Laplacian of $K_3$. Its constant eigenvector has eigenvalue zero, while every vector whose components sum to zero has eigenvalue three. One orthonormal set of three normal modes and their angular frequencies is thereforeThe zero mode is rigid rotation. The positive and equal squared frequencies on the two-dimensional relative subspace prove stability and agree with the general normal modes of three equal masses with a symmetric gap potential.

Choose ordered particle angles $q_1,q_2,q_3$ withand put $\Phi =(q_1+q_2+q_3)/3$. Solving for the individual angles givesThe kinetic energy is thereforeThe collective angle is an ignorable coordinate and decouples from the gaps, so its term may be omitted from the relative Lagrangian. Substituting $\gamma =2\pi -\alpha -\beta$ into the potential energy gives

Because the three positive gaps make one circuit,They describe only relative positions. The missing degree of freedom is the collective rigid rotation of all three particles around the circle, represented by the mean angular coordinate $\Phi$ in collective rotation and gap coordinates on a circle.