For an integer $s\ge 0$, the Sobolev space iswhere $D^{\beta }$ is a weak derivative. For $p<\infty$ one may use the Sobolev norm $({\sum }_{|\beta |\le s}\Vert D^{\beta }u{\Vert }_p^p{)}^{1/p}$; for $p=\infty$ use the maximum of the finitely many essential-supremum norms.

For $1\le p<d$, the Sobolev inequality is $\Vert u{\Vert }_{p^{\ast }}\le C_{d,p}\Vert \nabla u{\Vert }_p$, with Sobolev conjugate exponent $p^{\ast }=dp/(d-p)$. For $d<p<\infty$, Morrey's inequality supplies a continuous representative satisfyingAt $p=\infty$ the representative is Lipschitz continuous. At the critical exponent $p=d>1$, first-order Sobolev regularity gives every finite $L^q$ embedding for $q\ge d$, with an inhomogeneous norm, but generally no $L^{\infty }$ embedding. The one-dimensional endpoint $W^{1,1}(\mathbb{R})\hookrightarrow L^{\infty }(\mathbb{R})$ is an exception.

For the proof of Morrey's inequality, start with a smooth $u$ and write $u_{B(x,r)}$ for its average on a ball. Averaging the fundamental theorem of calculus along a line segment and changing radial variables givesThe last step is the Holder inequality; integrability of the kernel to power $p^{\prime }$ is exactly $(d-1)p^{\prime }<d$. For $r=|x-y|$, translate the averaging ball along the segment from $x$ to $y$. The fundamental theorem of calculus along a line segment and the Holder inequality giveCombining the two point-to-average bounds and this average-to-average bound proves the required Hölder estimate. The point-to-average bound with $r=1$, together with $|u_{B(x,1)}|\le |B_1{|}^{-1/p}\Vert u{\Vert }_p$, gives the supremum estimate. Density of smooth functions in a Sobolev space then gives a uniformly convergent sequence of smooth representatives, preserving both bounds. For $p=\infty$, mollification gives the Lipschitz version.

For the decay conclusion assume $d<p<\infty$. The representative is uniformly continuous. If $|u(x_j)|\ge 2\theta >0$ along points escaping to infinity, the Hölder bound gives a radius $\rho >0$, independent of $j$, on which $|u|\ge \theta$. A subsequence has disjoint radius-$\rho$ balls, each contributing at least ${\theta }^p|B_{\rho }|$ to $\Vert u{\Vert }_p^p$, a contradiction. This is uniformly continuous integrable functions vanish at infinity.

The finite-$p$ restriction is necessary. If the printed range includes $p=\infty$, its decay assertion is false: $u\equiv 1$ belongs to $W^{1,\infty }$ but does not tend to zero.

Non-characteristic. The first-order principal symbol is ${\nu }_t-i{\nu }_x$, which equals one on $(0,1)$.

Set $z=x+it$. The equation is equivalent to ${\partial }_{\bar{z}}\varphi =({\varphi }_x+i{\varphi }_t)/2=0$. Because $\varphi$ is continuously differentiable, the Cauchy-Riemann equations imply that it is a holomorphic function of $z$. Its convergent complex Taylor series restricts to a real power series along $t=0$, so $g$ is a real analytic function.

For smooth-data instability of the Cauchy-Riemann Cauchy problem, chooseThese are entire functions and satisfy the equation. Their initial derivatives obey ${\sup }_x|{\partial }_x^j{g}_n|\le n^j{e}^{-\sqrt{n}}$, so every finite sum tends to zero. ButThus analytic solutions can exist while continuous dependence on initial data fails for this smooth-data topology.

The Cauchy estimate follows directly from the differentiated Cauchy integral formula:The circle has length $2\pi r$, giving the bound for every integer $j\ge 0$.

Put $w=\varphi -\psi$ and integrate on the straight segment $z=\tau t/|t|$. For fixed $|x|<sR$, a disc centred at $x$ with radius approaching $R(\sigma (\tau )-s)$ stays inside $|\xi |\le \sigma (\tau )R$. Applying the first-derivative Cauchy estimate there givesIntegrating its modulus and taking the supremum over $|x|<sR$ is exactly the asserted integral estimate. The source cancels from $T\varphi -T\psi$.

To obtain a contraction mapping, use the weighted holomorphic norm on a shrinking time domain. Its finite-norm space consists of holomorphic functions on ${\mathcal{C}}_{\alpha }$ with zero initial value; the apparent quotient at $t=0$ is interpreted by a limit. Completeness follows because convergence in this norm implies locally uniform convergence of holomorphic functions, including near $t=0$, and the limiting pointwise bounds give convergence in the norm.

Here is the explicit contraction estimate on a shrinking holomorphic domain. Write $N=\Vert w{\Vert }_{\alpha }$, $r=|t|$, $A=\alpha (1-s)$, and chooseThen $\sigma -s=(A-\tau )/(2\alpha )$ and $\alpha (1-\sigma )-\tau =(A-\tau )/2$. The whole auxiliary polydisc lies inside ${\mathcal{C}}_{\alpha }$, and its supremum of $|w|$ is at most $2N\tau /(A-\tau )$. ConsequentlyThus $\Vert T\varphi -T\psi {\Vert }_{\alpha }\le (4\alpha /R)\Vert \varphi -\psi {\Vert }_{\alpha }$. Choose $0<\alpha <\min (\eta ,R/4)$. The source is bounded on the closed polydisc, say by $M_f$, and $\Vert T0{\Vert }_{\alpha }\le \alpha M_f$. Therefore $T$ maps the Banach space into itself and is a strict contraction mapping. The Banach fixed-point theorem gives a holomorphic fixed point with $\varphi (x,0)=0$. Differentiating the integral identity yields ${\varphi }_t-i{\varphi }_x=f$, establishing this case of the Cauchy-Kovalevskaya theorem.

Finally, near each real initial point, a real analytic function $g$ has a holomorphic extension $G$. Apply the same construction to $\varphi =G(x)+v$ with $v(x,0)=0$ and source $i{G}^{\prime }(x)$, restricting the discs if necessary. This gives a local real analytic function of $(x,t)$ with the prescribed initial value. Equivalently the solution is $\boxed{\varphi (x,t)=G(x+it)}$ wherever the extension is defined.

Characteristic. The second-order principal symbol of $i{\partial }_t+{\partial }_x^2$ is ${\nu }_x^2$, which vanishes on the normal $(0,1)$. This uses total differential order, rather than an anisotropic convention that assigns different weights to time and space derivatives.

Characteristic. The third-order principal symbol of ${\partial }_t-{\partial }_x^3$ is $-{\nu }_x^3$. The initial line has normal $({\nu }_x,{\nu }_t)=(0,1)$, on which this symbol vanishes. Its evolution form does not make it non-characteristic in the ordinary total-order definition.

The auxiliary Higman group $Q$ has no nontrivial finite quotients of a group. One can use this permitted property directly, but there is a short verification. In any finite quotient, let $n_i$ be the order of the image of $a_i$. Since conjugation sends $a_{i+1}$ to its square, $n_{i+1}$ must be odd. If some $n_i>1$, choose the least prime number $p$ dividing any $n_i$. It is odd. Conjugation by the preceding generator givesThe multiplicative order of $2$ modulo $p$ is therefore a divisor of $n_{i-1}$. It is greater than one and divides $p-1$ by the Fermat little theorem, so it has a prime divisor smaller than $p$. That prime also divides $n_{i-1}$, contradicting the choice of $p$. Hence every $n_i=1$ and the quotient is trivial.

Given any finitely presented group $P$, form $\hat{P}=P\ast ⟨v⟩$, and apply part (a) to the word $w=v$. This word is nontrivial by the normal form theorem for a free product, so the output $J=\hat{P}(v)$ contains $P$ by the embedding already proved.

To check its finite quotients, let $f:J\to F$ be any group homomorphism to a finite group. The image of the copy of $Q$ is trivial by the preceding property. The identifications $u_j=a_3^{j+1}{a}_1{a}_3^{-(j+1)}$ make all $f(u_j)$ trivial. Thus the equations $u_j^{-1}c{u}_j=g_j$ give, in the image,Since $f(c)=f(z)$, this forces $f(x_i)=1$ for all generators of $\hat{P}$, including $v$. The defining word $c=[v,z]$ then has trivial image, so $f(z)=f(d)=1$ as well. Every generator of $J$ has trivial image. ThereforeThis uses the concrete construction of part (a), not an assumption that arbitrary quotients preserve an embedding of $P$.

An isomorphism-invariant Markov property of finitely presented groups $\rho$ has two finitely presented witnesses: a group $A_{+}$ with $\rho$, and a group $A_{-}$ which cannot embed in any finitely presented group having $\rho$. In symbols,The second condition is an obstruction to embedding, stronger than merely saying that $A_{-}$ itself fails the property.

Let $U$ be a fixed finitely presented group with unsolvable word problem for a group. Form the finitely presented free product $P=U\ast A_{-}$. Given a word $w$ in the generators of $U$, apply part (a) to this $P$ and $w$, and output the finite presentation ofIf $w=1$ in $U$, it is also $1$ in $P$, so $P(w)$ is trivial and $B(w)\cong A_{+}$ has $\rho$. If $w\ne 1$ in $U$, its image stays nontrivial in the free product $P$, and $P$ embeds in $P(w)$. Therefore $A_{-}$ embeds in $B(w)$, which cannot have $\rho$. We have the effective equivalenceAn algorithm recognizing whether an arbitrary finite group presentation has $\rho$ would decide the unsolvable word problem for a group $U$. This contradiction proves the Adian–Rabin theorem: no Markov property of finitely presented groups is algorithmically decidable.

The factors ${\mathbb{Z}}^2$ and $\mathbb{Z}$ are torsion-free groups, and so is their free product $K$. Indeed every element of a free product is conjugate either into one factor or to an alternating word whose first and last syllables lie in different factors. A word of the latter kind has nonempty reduced powers of every positive length, so has infinite order. A nonidentity element of either factor also has infinite order.

By the finite-order result in part (b), every finite-order element of the multiple HNN extension $K_{\mathcal{M}}$ is conjugate into the torsion-free base $K$, and hence is the identity. Apply the same result once more to $G_{\mathcal{M}}$, whose base is $K_{\mathcal{M}}$. It follows thatThus the failure of a word problem for a group to be decidable does not require torsion.

Form the HNN extension which centralizes $L$:This is the extension associated to the identity isomorphism $L\to L$; relations on the displayed finite generating set imply $k^{-1}hk=h$ for all $h\in L$. Since $K_{\mathcal{M}}$ is finitely presented and $I,J$ are finite, this is a finite group presentation.

For any $g\in K_{\mathcal{M}}$,The forward implication follows from Britton's lemma: if $g\notin L$, the word $k^{-1}gk{g}^{-1}$ is reduced with two stable letters and cannot be the identity. The reverse implication is the defining centralization relation. Consequently the computable wordsatisfiesAn algorithm for the word problem for a group $G_{\mathcal{M}}$ would therefore decide the nonrecursive set $H_0(\mathcal{M})$, a contradiction. Hence $\boxed{G_{\mathcal{M}}\text{ has unsolvable word problem}}$.

Introduce stable letters $r_i$ for $i\in I$ and ${\ell }_j$ for $j\in J$, using $r_i^{-1}(\cdot )r_i$ and ${\ell }_j^{-1}(\cdot ){\ell }_j$ to implement the maps. Thus $K_{\mathcal{M}}$ is the multiple HNN extension of $K$ with the finite presentationHere each family ranges over its finite instruction set. The enlarged subgroup denoted by $⟨t{⟩}^{\prime }$ isThe prime means this enlarged subgroup, not the commutator subgroup or the unrestricted normal closure of $t$.

The key relationship isHere is a justification that also identifies the relevant intersection. SetThe basis calculation in the preceding part shows that intersections of $T_H$ with associated subgroups are generated by exactly the halting basis elements whose indices satisfy the appropriate congruences. Since the machine is deterministic and $(0,0)$ is terminal, halting at $(0,0)$ is equivalent for the two ends of every instruction edge. Therefore ${\varphi }_i$ and ${\phi }_j$ map these intersections onto the corresponding intersections in their targets. The same assertion holds on the integer lattices after declaring pairs with a negative coordinate nonhalting: the bounds on $a,b,c$ imply that each coordinate's sign is preserved by a transition and its inverse.

Apply Britton's lemma to a word in $B_H$ which represents an element of $K$. If it has stable letters, it must have a pinch. The base coefficient of that pinch lies in $T_H$ and an associated subgroup, and the intersection property just proved makes its transported image lie in $T_H$ again. Successive pinch removals therefore keep all base coefficients in $T_H$, and eventually remove every stable letter. It follows thatFinally, $t=t(0,0)$ belongs to $T_H$, so $L\subseteq B_H$. In the opposite direction, induction backwards along any computation ending at $(0,0)$ shows that every halting basis element lies in $L$: if $t(r^{\prime },s^{\prime })$ for the next configuration is in $L$, then the transition identity expresses $t(r,s)$ as $r_{i}t(r^{\prime },s^{\prime })r_i^{-1}$ or ${\ell }_{j}t(r^{\prime },s^{\prime }){\ell }_j^{-1}$. Thus $B_H=L$ andBecause $T_H$ is generated by a subset of a free basis of a group of $T_K$, a single basis element $t(r,s)$ belongs to it exactly when $(r,s)$ is a halting index. This proves the boxed relationship.

For $M>a\ge 0$ and $N>b\ge 0$, defineThe normal form theorem for a free product giveswhere $X,Y,T$ map to $x^M,y^N,t(a,b)$. To see injectivity, expand an alternating word in $⟨x^M,y^N⟩$ and powers of $t(a,b)$. The conjugating $x,y$ factors commute with the lattice syllables, so each intervening nonidentity lattice syllable stays nonidentity in the expanded free-product normal form.

Its intersection with $T_K$ is the free group with basisThis follows by moving all $x^M,y^N$ factors to the right; the zero-exponent lattice remainder characterizes membership in the kernel.

The required isomorphisms are specified on the three generators byandEach source and target has the same presentation $⟨X,Y,T\mid [X,Y]=1⟩$, and each displayed assignment identifies its three abstract generators. Hence these are genuine isomorphisms, not merely maps of generating sets.

On the kernel basis they give exactly the machine transitions:For example, rewrite the first input as $x^{-mu}{y}^{-mv}t(a_i,b_i)x^{mu}{y}^{mv}$ and apply ${\varphi }_i$ to each factor. These identities also hold for negative $u,v$, since they are identities in the groups.

The base free product for the group encoding of a modular machine isThe letters $x,y$ generate the first factor, and $t$ generates the second. Let $T_K$ be the kernel of the group homomorphism $K\to ⟨x,y⟩\cong {\mathbb{Z}}^2$ that kills $t$. Thenis a free group with this displayed free basis of a group. Indeed every word in $K$ can be rewritten as a product of such conjugates followed by an element of $⟨x,y⟩$, so they generate the kernel. A freely reduced product of these conjugates is nontrivial by the normal form theorem for a free product: after combining adjacent occurrences of the same conjugate, different successive indices give a nonzero intervening $x,y$-syllable. Thus there is no relation among the proposed basis elements.

For clarity, a modular machine of modulus $m>1$ has at most one instruction for each residue pair $(a,b)$, with $0\le a,b<m$ and $0\le c<m^2$. Its right and left transitions are respectivelyIts halting set at a designated terminal configuration $H_0(\mathcal{M})$ consists of the nonnegative pairs whose forward computation reaches $(0,0)$, including $(0,0)$ itself. These formulas explain the exponents in the associated-subgroup maps below.

Use a reduced sequence in an HNN extension for $\gamma$. By repeatedly conjugating a prefix to the other end and reducing any resulting pinch, one obtains a cyclically reduced sequence in an HNN extension: either an element of the base group, or a sequence of positive stable-letter length with no pinch even across its cyclic junction. For example, after conjugating away the initial base coefficient, write it as $t^{{ϵ}_1}{g}_1\cdots t^{{ϵ}_k}{g}_k$. A pinch across the junction can occur only if ${ϵ}_k=-{ϵ}_1$ and $g_k\in C_{{ϵ}_k}$. Moving the first stable letter to the end then exposes that pinch and reduces the stable-letter length by two. Iteration must terminate.

If the resulting cyclically reduced sequence has $k>0$, every positive power remains reduced and has stable-letter length equal to that power times $k$. By Britton's lemma, none is the identity. Thus a finite-order element must be conjugate into the base group $G$. Since $G$ embeds in the HNN extension, the order of a base-group element is unchanged, and conjugation also preserves order. ThereforeThe argument also applies to several stable letters: cyclic pinches must involve a stable letter and its own inverse.

In a direct product of groups, $(a,b{)}^r=(a^r,b^r)$. Thus a finite order for $(a,b)$ makes both coordinate orders finite. Conversely, if their orders are $p$ and $q$, the least positive exponent annihilating both is their least common multiple. Hencewhen both orders are finite; if either coordinate has infinite order, so does $(a,b)$.

If the Turing machine halts on $w$, follow its computation from $h{q}_{1}wh$. A transition at an already represented cell is one of the corresponding relations. At a boundary, first insert the required blank using a padding relation. Thus the computation gives a finite equality derivation to $hu{q}_{0}vh$. Replace $q_0$ by $q$, erase the symbols of $u,v$ using $s_{j}q=q=q{s}_j$, and erase both boundary markers. This proves $h{q}_{1}wh=q$ in the semigroup.

For the converse, equality in a presented semigroup means a finite sequence of contextual replacements using defining relations in either direction. In any derivation from $h{q}_{1}wh$ to $q$, consider the first occurrence of the special symbol $q$. Before it occurs, the erasure relations cannot be used in either direction. Each word therefore still has exactly two markers $h$, exactly one state letter, and the form $hu{q}_{i}vh$. Both directions of a transition relation join configurations linked by one actual machine step; both directions of a boundary-padding relation merely change how much blank tape is represented.

The first occurrence of $q$ must come from $q_0=q$ in the forward direction. Hence the initial configuration is connected, by transitions in either direction and harmless padding, to a configuration in state $q_0$. For a deterministic Turing machine, the property of eventually reaching $q_0$ is invariant along each transition edge: if $C\to D$ is a step, then $C$ halts if and only if $D$ halts, since that step is the unique next step of $C$ and $C$ is not already in the halting state. The same property is unchanged by padding. A finite path of these edges to $q_0$ therefore shows that the initial configuration halts.

ConsequentlyThe invariance argument is necessary because equality in a semigroup presentation allows reversed transitions as well as forward computation steps.

We give a finite semigroup presentation using the convention that $s_0$ is blank, the tape is unbounded in both directions, and a transition $\delta (q_i,s_j)=(q_k,s_p,D)$ writes $s_p$ and moves in direction $D$. The Turing machine is deterministic, and the halting state $q_0$ has no outgoing transition. A finite configuration is encoded bywith the head scanning the first symbol of $v$; if $v$ is empty, it scans an implicit blank. Unrepresented cells beyond the boundary markers $h$ are blank. An additional generator $q$ records completed halting and erasure.

The generators of the semigroup are $S\bigsqcup Q\bigsqcup \{h,q\}$. Its relations have the following finite families. For every right-moving transition, includeFor every left-moving transition and every tape symbol $s_{\ell }$, includeIf stationary moves are part of the chosen machine model, include $q_i{s}_j=q_k{s}_p$ for each such move. Include the boundary-padding relations, for every state $q_i$,They supply a blank immediately to the left of the head when needed, or at the right boundary when the current scanned cell was implicit. Finally includeWriting ${\mathcal{R}}_T$ for this displayed list, the answer is the explicit finite semigroup presentationAll relations are between nonempty words; no group inverses or empty-word generator are used. The transition families are finite because the transition table and alphabet are finite, and the padding and erasure families are visibly finite. The declared head convention determines which side of a tape symbol carries a state letter.