Proof. Every symbol in a part is one level deeper than in the renormalised sub-source, so \(L=1+a\,L(B_L)+(1-a)\,L(B_R)\). The entropy grouping rule gives \(\mathrm H=\mathrm H_2(a)+a\,\mathrm H(B_L)+(1-a)\,\mathrm H(B_R)\). Subtract, and telescope down the tree (leaves contribute \(0\)). ◻

Proof. (i) \(\kappa\) is convex and even with \(\kappa(0)=0\) and \(\kappa(1)=1\). A convex function lies below the chord joining any two points of its graph, so on \([0,1]\) the graph of \(\kappa\) lies below the segment from \((0,0)\) to \((1,1)\); this gives \(\kappa(d)\le(1-d)\kappa(0)+d\kappa(1)=d\), and evenness extends it to \(\kappa(d)\le|d|\). We refer to this estimate as the chord bound. The quadratic bound follows from the Taylor expansion \[\begin{align} \mathrm H_2\Bigl(\tfrac{1+d}{2}\Bigr)\;&=\;1-\frac{1}{\ln2}\sum_{k\ge1}\frac{d^{2k}}{2k(2k-1)},\\ \text{i.e.}\quad \kappa(d)\;&=\;\frac{1}{\ln2}\sum_{k\ge1}\frac{d^{2k}}{2k(2k-1)}. \end{align}\] Since \(d^{2k}\le d^2\) for \(|d|\le1\) and \(\sum_{k\ge1}\tfrac1{2k(2k-1)}=\sum_{k\ge1}\bigl(\tfrac1{2k-1}-\tfrac1{2k}\bigr) =1-\tfrac12+\tfrac13-\cdots=\ln2\) (the alternating harmonic series), it follows that \(\kappa(d)\le\tfrac{d^2}{\ln2}\cdot\ln2=d^2\).

(ii) \(\mathrm H_2''(x)=-\tfrac1{x(1-x)\ln2}<0\) makes \(\mathrm H_2\) strictly concave, hence \(\kappa\) strictly convex (affine inner map). For \(0<s<t\le1\), writing \(s=\tfrac st\,t+(1-\tfrac st)\cdot0\), strict convexity and \(\kappa(0)=0\) give \(\kappa(s)<\tfrac st\,\kappa(t)\), i.e.\(\kappa(s)/s<\kappa(t)/t\): the ratio is strictly increasing, and since \(\kappa(t)>0\) for \(t>0\) the same display shows that \(\kappa\) is strictly increasing on \([0,1]\). The stated bound is the ratio at \(t=\tfrac15\), using \(\kappa(\tfrac15)=(\lambda-1)/5\), the definition 1 of \(\lambda\). ◻

Proof. Let the cut be after position \(k\) and \(x=m_L-m_R\). If \(x\ge0\) and the left part is a singleton, then \(x=2p_k-M\le p_k\) directly (\(M\), the block mass, is \(\ge p_k\)). Otherwise, for \(x\ge0\), moving the cut one step left transfers \(p_k\) to the right and yields imbalance \(|x-2p_k|\); optimality of the cut gives \(x\le|x-2p_k|\). If \(x>2p_k\) this reads \(x\le x-2p_k\), impossible; hence \(x\le2p_k\) and then \(x\le2p_k-x\), i.e. \(x\le p_k\). If \(x<0\): were the right part a single symbol, the left part would contain at least one symbol \(\ge\) that symbol, giving \(x\ge0\); so the cut can move one step right, transferring \(p_{k+1}\), and the same argument gives \(-x\le p_{k+1}\le p_k\). ◻

Proof. As the cut moves right the signed imbalance \(2(\text{prefix mass})-1\) strictly increases. The cut after position \(1\) is at least as good as the cut after position \(2\) iff \(|2p_1-1|\le|2(p_1+p_2)-1|\), which simplifies (in both sign cases) to \(2p_1+p_2\ge1\); and when this holds, the signed imbalance at position \(2\) is already \(2p_1+2p_2-1\ge p_2\ge0\), so all later cuts are worse. Conversely, if \(2p_1+p_2<1\) the cut after position \(2\) is strictly better than after position \(1\). With \(p_2\le p_1\), \(2p_1+p_2\ge1\) forces \(3p_1\ge1\). The identity is Lemma 1 with \(a=p_1\) and \(R(B_L)=0\). ◻

Proof. Lemma 5 and \(R(\rho)<1\) (Lemma 4) give \(R<(1-\mathrm H_2(p_1))+(1-p_1)\); the block form is the same computation after renormalisation. ◻

Proof of Proposition 1(a). The upper bound is Corollary 1. For the lower bound fix \(p_1\in[\tfrac12,1)\) and \(q\in[\tfrac12,1)\), and consider the three-symbol source \[p\;=\;\bigl(p_1,\;(1-p_1)q,\;(1-p_1)(1-q)\bigr),\] which is sorted since \((1-p_1)q\le p_1\) for \(p_1\ge\tfrac12\). Since \(2p_1\ge1\) the root splits the leader off on its own (Lemma 5), and the remaining binary block has redundancy \(1-\mathrm H_2(q)\). Hence \[\begin{align} R&=\bigl(1-\mathrm H_2(p_1)\bigr)+(1-p_1)\bigl(1-\mathrm H_2(q)\bigr)\\ &\;\xrightarrow[q\to1^-]{}\;2-p_1-\mathrm H_2(p_1). \end{align}\] The supremum is not attained because \(R<2-p_1-\mathrm H_2(p_1)\) always (Corollary 1). ◻

Proof of Proposition 1(b). \(R<1\) is Lemma 4. For the supremum, the binary source \((1-\varepsilon,\varepsilon)\) has \(R=1-\mathrm H_2(\varepsilon)\to1\) as \(\varepsilon\to0^+\). ◻

Proof of the corollary. For \(n\ge3\), Theorem 2 gives \(R\le p_1+C-\lambda p_n<p_1+C\) since \(\lambda,p_n>0\). For \(n=2\) (where necessarily \(p_1\ge\tfrac12\)), the chord bound (Lemma 2) gives \(R=\kappa(2p_1-1)\le2p_1-1<p_1<p_1+C\). ◻

Proof. The isolate/group dichotomy and \(p_1\ge\tfrac13\) are Lemma 5. For a group split, \(p_1\ge p_2\) gives \(\tfrac32a\le\tfrac32(p_1+p_2)\le2p_1+p_2<1\), so \(a<\tfrac23\). For shape \((2,\cdot)\): if \(a\ge\tfrac12\) then \(a\ge\tfrac25\) trivially; if \(a<\tfrac12\), Lemma 3 gives \(1-2a=|2a-1|\le p_2\), while \(p_2\le\tfrac a2\) (as \(p_1\ge p_2\), \(p_1+p_2=a\)), so \(1\le\tfrac52a\). It remains to exclude shapes with right part of size \(1\), and shape \((3,2)\).

Right part of size \(1\) (cut after \(n-1\)): the imbalance is \(1-2p_n\), and Lemma 3 gives \(1-2p_n\le p_{n-1}\le p_1<\tfrac12\), so \(p_n>\tfrac14\). For \(n\ge4\) all symbols then exceed \(\tfrac14\) and the total mass exceeds \(1\), a contradiction. For \(n=3\), cutting after position \(1\) (imbalance \(1-2p_1\)) is at least as good as after position \(2\) (imbalance \(1-2p_3\ge1-2p_1\)), with equality only if \(p_1=p_3\), i.e.the uniform ternary source.

Shape \((3,2)\) (cut after \(n-2\), \(n\ge5\)): let \(s=p_{n-1}+p_n\). If \(s\ge\tfrac12\) then \(p_{n-1}\ge\tfrac s2\ge\tfrac14\), so all symbols exceed \(\tfrac14\) and again the mass exceeds \(1\); hence \(s<\tfrac12\) and the imbalance is \(1-2s>0\). Moving the cut one step left transfers \(p_{n-2}\) and produces signed imbalance \(1-2s-2p_{n-2}\); optimality requires \(1-2s\le|1-2s-2p_{n-2}|\), which forces \(1-2s-2p_{n-2}<0\) and \[\label{eq:32a} p_{n-2}+2p_{n-1}+2p_n\;\ge\;1 .\tag{3}\] On the other hand the \(n-2\) largest symbols are each \(\ge p_{n-2}\), so \[\label{eq:32b} (n-2)\,p_{n-2}+p_{n-1}+p_n\;\le\;1 .\tag{4}\] Subtracting 3 from 4 : \((n-3)p_{n-2}\le p_{n-1}+p_n\le2p_{n-2}\), hence \(n\le5\). For \(n=5\) all the inequalities are forced into equalities, giving \(p_1=\cdots=p_5=\tfrac15\), the uniform quinary source. ◻

Proof. (S1) \(\psi'(x)=-\mathrm H_2'(x)-2(\lambda-1)=\log_2\tfrac{x}{1-x}-2(\lambda-1)<0\) for \(x\le\tfrac12\) (the logarithm is \(\le0\) there and \(\lambda>1\)), and \(\psi(\tfrac13)=c_3+\tfrac{\lambda-1}{3}\), which is the definition 1 of \(C\); by 2 the \(\log_23\)-terms cancel and \(C=4-\tfrac53\log_25\).

(S2) \(h\) is convex (\(-\mathrm H_2\) convex plus affine), so its maximum on \([\tfrac12,1]\) is at an endpoint: \(h(\tfrac12)=0+\tfrac{\lambda-1}{4}\) and \(h(1)=0\). And \(\tfrac{\lambda-1}4<\tfrac{\lambda-1}2<C\).

(S3) \(1-\mathrm H_2\) is convex, hence lies below its chord on \([\tfrac12,\tfrac23]\) through \(\bigl(\tfrac12,0\bigr)\) and \(\bigl(\tfrac23,1-\mathrm H_2(\tfrac23)\bigr)\); and \(\mathrm H_2(\tfrac23)=\mathrm H_2(\tfrac13)\), so the chord’s slope is \(c_3/\tfrac16=6c_3\). ◻

Proof. \(G\) is increasing in \(p_3\), so put \(p_3=\min(p_2,t)\); the junction is \(p_2=\tfrac{1-p_1}2\) (where \(p_2=t\)), which lies in \([1-2p_1,\,p_1]\) exactly for \(p_1\ge\tfrac13\). On each of the two \(p_2\)-segments, \(G\) is “affine \(-\) entropy of affine arguments”, hence convex in \(p_2\); so its maximum is at \(p_2\in\{1-2p_1,\;\tfrac{1-p_1}2,\;p_1\}\). This leaves three one-variable functions of \(p_1\), each again convex (same reason), so each is maximised at \(p_1\in\{\tfrac13,\tfrac12\}\):

• \(p_2=1-2p_1\) (then \(t=p_1\), \(p_3=1-2p_1\)): at \(p_1=\tfrac13\) the value is \(2-\tfrac23-\log_23+\tfrac13-\tfrac23C=\tfrac53-\log_23-\tfrac23C=\beta\); at \(p_1=\tfrac12\) it is \(1-\mathrm H(\tfrac12,0,\tfrac12)+0-\tfrac{C}2 =-\tfrac{C}2<0\).

• \(p_2=\tfrac{1-p_1}2\) (then \(p_3=t=p_2\)): at \(p_1=\tfrac13\) the value is again \(\beta\) (all three symbols \(\tfrac13\)); at \(p_1=\tfrac12\) it is \(1-\mathrm H(\tfrac12,\tfrac14,\tfrac14)+\tfrac14-\tfrac34C =-\tfrac14-\tfrac34C<0\).

• \(p_2=p_1\) (then \(p_3=1-2p_1\)): this function is pointwise \(\le\) the first one, since it has the same entropy term (by symmetry of \(\mathrm H\)) and the same \(p_3\), but the larger subtraction \(C\cdot2p_1\ge C\,(1-p_1)\) for \(p_1\ge\tfrac13\).

The two \(\tfrac12\)-endpoint values are \(\le\beta\): indeed \(-\tfrac14-\tfrac34C<-\tfrac{C}2\), and \[\beta+\frac{C}{2}\;=\;\frac{5}{3}-\log_23-\frac{C}{6}\;>\;0 .\] Hence \(G\le\beta\) on the whole region, and \(\beta<0\) by simple arithmetic. ◻

Proof. Step 1 (change of variables). Set \(x=p_1\), \(y=p_2\), \(u=A-p_2\), \(v=s-A\); then \(x+y+u+v=1\) and \(x,y,u\ge0\). From (P4), (P5): \(2A-s\le q\le u\) gives \(y+u-v\le u\), i.e.\(v\ge y\); and \(s-2A\le q\le u\) gives \(v\le y+2u\). In these variables, using \(r\le q\le u\) (P6), (P4) and that \(\Delta\) is nondecreasing in \(r\), \[\begin{align} \Delta\;\le\;F(x,y,u)\;&:=\;2-2x+y+3u-\mathrm H(x,y,u,v)\\ &\phantom{{}:={}}-C\,(x+y+u),\\ &\phantom{{}:={}}v=1-x-y-u . \end{align}\]

Step 2 (the polytope). Conditions (P1)–(P3), together with the two consequences \(v\ge y\) and \(v\le y+2u\) of (P5) from Step 1, translate to: \(\tfrac13\le x\le\tfrac12\); \(2x+y\ge1\); \(x+3y\ge1\); \(x+2y\le1\); \(x+2y+u\le1\) (\(v\ge y\)); \(x+2y+3u\ge1\) (\(v\le y+2u\)). Call this polytope \(\mathcal{P}\) (note \(u\ge0\) is implied by the last two with \(x+2y\le1\)).

Step 3 (convexity). \(F\) is affine minus \(\mathrm H(x,y,u,v)=\sum_k\mathrm I(a_k)\), a sum of the concave function \(\mathrm I\) evaluated at the affine arguments \(a_k\in\{x,y,u,v\}\); hence \(-\mathrm H\), and with it \(F\), is convex on \(\mathcal{P}\).

Step 4 (a hull of six points). We show that \(\mathcal{P}\) lies in the convex hull of the six points \(W_1,\dots,W_6\), where \[\begin{align} W_1&=\bigl(\tfrac13,\tfrac13,0\bigr),& W_2&=\bigl(\tfrac25,\tfrac15,\tfrac1{15}\bigr),& W_3&=\bigl(\tfrac25,\tfrac15,\tfrac15\bigr),\\ W_4&=\bigl(\tfrac12,\tfrac16,\tfrac1{18}\bigr),& W_5&=\bigl(\tfrac12,\tfrac16,\tfrac16\bigr),& W_6&=\bigl(\tfrac12,\tfrac14,0\bigr). \end{align}\] The idea is to project \(\mathcal{P}\) onto the \((x,y)\)-plane and then lift back. Eliminating \(u\), the pair \((x,y)\) ranges over the planar region \(\{\tfrac13\le x\le\tfrac12,\;y^-(x)\le y\le y^+(x)\}\) with \(y^+(x)=\tfrac{1-x}2\) and \(y^-(x)=\max\bigl(1-2x,\tfrac{1-x}3\bigr)\), the two bounds crossing at \(x=\tfrac25\). This region is the quadrilateral with corners \(Q_1=(\tfrac13,\tfrac13)\), \(Q_2=(\tfrac25,\tfrac15)\), \(Q_3=(\tfrac12,\tfrac16)\), \(Q_4=(\tfrac12,\tfrac14)\): its upper edge \(y=y^+(x)\) is the segment \(Q_1Q_4\), and its lower edge \(y=y^-(x)\) is the segment \(Q_1Q_2\) for \(x\le\tfrac25\) and \(Q_2Q_3\) for \(x\ge\tfrac25\), as the parametrisations \[\bigl(x,y^+(x)\bigr)=(1-\lambda)Q_1+\lambda Q_4,\qquad \lambda=6x-2,\] \[\bigl(x,y^-(x)\bigr)= \begin{cases} (1-\lambda)Q_1+\lambda Q_2,\quad \lambda=15x-5, & x\le\tfrac25,\\ (1-\lambda)Q_2+\lambda Q_3,\quad \lambda=10x-4, & x\ge\tfrac25, \end{cases}\] show; hence every \((x,y)\) in the region is a convex combination of \(Q_1,\dots,Q_4\). To lift back to \(\mathcal{P}\), fix such an \((x,y)\): the constraints \(x+2y+u\le1\) and \(x+2y+3u\ge1\) confine \(u\) to the interval \(\bigl[\tfrac{1-x-2y}3,\;1-x-2y\bigr]\), whose two endpoints are affine in \((x,y)\). Writing \(u\) as a convex combination of these two endpoints, and substituting for \((x,y)\) its expression as a convex combination of the \(Q_i\), exhibits \((x,y,u)\) as a convex combination of the six points \(\bigl(Q_i,\tfrac{1-x-2y}3\big|_{Q_i}\bigr)\) and \(\bigl(Q_i,(1-x-2y)\big|_{Q_i}\bigr)\). Since \(1-x-2y\) equals \(0,\tfrac15,\tfrac16,0\) at \(Q_1,\dots,Q_4\), these six points are exactly \(W_1,\dots,W_6\).

Step 5 (certified evaluation). By convexity, \(\max_\mathcal{P}F\le\max_jF(W_j)\). Write \(F=N-\mathrm H-CM\) with \(N=2-2x+y+3u\), \(M=x+y+u\), so that \(CM=4M-\tfrac53M\log_25\); with \(\log_26=1+\log_23\), \(\log_2{15}=\log_23+\log_25\), \(\log_2{18}=1+2\log_23\), \(\log_2\tfrac52=\log_25-1\), \(\log_2\tfrac{18}5=1+2\log_23-\log_25\), direct evaluation gives \[\begin{array}{l} F(W_1)=-1-\log_23+\tfrac{10}9\log_25=\beta,\\[3pt] F(W_2)=-\tfrac23-\tfrac25\log_23+\tfrac49\log_25,\\[3pt] F(W_3)=-\tfrac45+\tfrac13\log_25,\\[3pt] F(W_4)=-\tfrac{23}9-\tfrac56\log_23+\tfrac{40}{27}\log_25,\\[3pt] F(W_5)=-\tfrac83-\tfrac12\log_23+\tfrac{25}{18}\log_25,\\[3pt] F(W_6)=-\tfrac{13}4+\tfrac54\log_25 . \end{array}\] Each value is monotone in \(\log_23\) and in \(\log_25\) (sign of the coefficient); substituting \(\log_23>\tfrac{19}{12}\), \(\log_25<\tfrac73\) gives \[\begin{align} F(W_2)&\le\tfrac{-180-171+280}{270}=-\tfrac{71}{270},\\ F(W_3)&\le-\tfrac45+\tfrac13\cdot\tfrac73=-\tfrac1{45},\\ F(W_4)&\le\tfrac{-1656-855+2240}{648}=-\tfrac{271}{648},\\ F(W_5)&\le\tfrac{-576-171+700}{216}=-\tfrac{47}{216},\\ F(W_6)&\le-\tfrac{13}4+\tfrac{35}{12}=-\tfrac13, \end{align}\] so \(F(W_j)\le-\tfrac1{45}\) for \(j=2,\dots,6\); and \(F(W_1)=\beta<0\), critical at the same balanced configuration \(p_1=p_2=\tfrac13\) as in Case A. Hence \(\Delta\le F\le\max\bigl(\beta,-\tfrac1{45}\bigr)<0\) on \(\mathcal{P}\). ◻

Proof. The left part has at least two symbols: its leader is \(p_1\), and its remainder \(L'\) has mass \(x\), largest symbol \(p_2\) and least symbol \(p_k\) (\(k\) is the cut position), so \(p_k\le x\). Lemma 3 at the root reads \(|2a-1|=|2x-\delta|\le p_k\). Since \(|2x-\delta|\le x\) gives \(x\le\delta\), i.e.\(a\le1-p_1\le2p_1\) (as \(p_1\ge\tfrac13\)), the leader’s fraction of the left part is \(p_1/a\ge\tfrac12\), so the leader is again split off on its own within the left part (Lemma 5); this reduction applied inside the left part and the grouping identity \((1-\mathrm H_2(a))+a\bigl(1-\mathrm H_2(p_1/a)\bigr)=(1+a)-\mathrm H(p_1,x,1-a)\) give \[R=(1+a)-\mathrm H(p_1,x,1-a)+x\,R_{L'}+(1-a)\,R_{\mathrm{Rt}},\] where \(R_{L'}\) and \(R_{\mathrm{Rt}}\) are the redundancies of the renormalised left remainder \(L'\) (mass \(x\)) and right part \(\mathrm{Rt}\) (mass \(1-a\), largest symbol \(p_{k+1}\)). By Corollary 2 (every source), \((1-a)R_{\mathrm{Rt}}<p_{k+1}+(1-a)C\) (or \(=0\) for a singleton, when the same bound holds trivially).

Two left symbols. Then \(L'=\{p_2\}\), so \(x=p_2=p_k\) and \(xR_{L'}=0\); with \(p_{k+1}\le p_k=x\), \[R\;<\;(1+a)-\mathrm H(p_1,x,1-a)+x+(1-a)\,C\;=\;F(p_1,x),\] and \(|2x-\delta|\le p_k=x\) reads \(x\ge\tfrac\delta3\) (\(\delta-2x\le x\)) and \(x\le\delta\) (\(2x-\delta\le x\)).

At least three left symbols. Then \(|L'|\ge2\) and \(xR_{L'}<p_2+xC\) (Corollary 2 again); since \(p_2\) and \(p_k\) are distinct symbols of \(L'\), \(p_2+p_{k+1}\le p_2+p_k\le x\), whence \(R<F(p_1,x)+xC=G(p_1,x)\). Moreover \(p_k\le\min(p_2,\,x-p_2)\le\tfrac x2\), so \(|2x-\delta|\le\tfrac x2\): \(x\ge\tfrac{2\delta}5\) and \(x\le\tfrac{2\delta}3\).

For the endpoints, in \(x\), with \(t:=1-p_1-x\) and \(\mathrm I'(t)=-\log_2t-\log_2e\), \[\frac{\partial F}{\partial x}\;=\;2-C+\log_2\frac{x}{t}, \qquad \frac{\partial G}{\partial x}\;=\;2+\log_2\frac{x}{t},\] both strictly increasing in \(x\) (\(x\) increases, \(t\) decreases); so \(F(p_1,\cdot)\) and \(G(p_1,\cdot)\) are decreasing-then-increasing and each is maximised over its \(x\)-interval at an endpoint. ◻

Proof. In each of (ii)–(vi) the difference of the two curves is concave (a sum of \(\pm\mathrm I\) of affine arguments), so nonnegativity on \([\tfrac13,\tfrac12]\) follows from its two endpoint values; (o) and (i) are direct algebra. Concavity in (ii)–(vi). Each difference is affine plus terms \(\pm \mathrm I(u(p_1))\) with \(u\) affine of slope \(s\), contributing \(\pm s^2I''(u)=\mp\tfrac{s^2}{u\ln2}\) to the second derivative; collecting them, the second derivatives times \(\ln2\) are \[\mathrm{(ii),(iii)}:\;-\tfrac1{p_1}-\tfrac4\delta+\tfrac1{1-p_1};\qquad \mathrm{(iv)}:\;-\tfrac4{3\delta}-\tfrac1{3(2-p_1)}+\tfrac1{1-p_1};\] \[\mathrm{(v)}:\;-\tfrac8{5\delta}-\tfrac1{5(3-p_1)}+\tfrac1{1-p_1};\qquad \mathrm{(vi)}:\;-\tfrac8{3\delta}-\tfrac1{3(1+p_1)}+\tfrac1{1-p_1},\] each negative: on \([\tfrac13,\tfrac12)\) one has \(\tfrac1{1-p_1}\le2\), while \(\delta\le\tfrac13\) gives \(\tfrac4\delta\ge12\), \(\tfrac4{3\delta}\ge4\), \(\tfrac8{5\delta}\ge\tfrac{24}5\), \(\tfrac8{3\delta}\ge8\), all \(>2\).

Endpoints at \(\tfrac12\). There \(\delta=0\) and all four constrained curves degenerate to \(F(\tfrac12,0)=G(\tfrac12,0)=\tfrac32+\tfrac{C}2-\mathrm H_2(\tfrac12)=K =\tilde{B}(\tfrac12)\), while \(T_0(\tfrac12)=\tfrac12=\tilde{B}(\tfrac12) -\tfrac{C}2\): the values claimed.

Endpoints at \(\tfrac13\), where \(\delta=\tfrac13\) and \(\tilde{B}(\tfrac13)=\tfrac{10}3-\log_23-\tfrac59\log_25\) (substitute \(C=4-\tfrac53\log_25\)). For (ii): \(T_0(\tfrac13)=2-3\mathrm I(\tfrac13)=2-\log_23\), so \(\tilde{B}(\tfrac13)-T_0(\tfrac13)=\tfrac{C}3\). For (iii): using \(\mathrm I(\tfrac13)=\tfrac{\log_23}3\) and \(\mathrm I(\tfrac23)=\tfrac23(\log_23-1)\), \[\begin{align} &-2+\tfrac43+\mathrm I\bigl(\tfrac13\bigr)-\mathrm I\bigl(\tfrac23\bigr) +\mathrm I\bigl(\tfrac13\bigr)\\ &\quad=\;-\tfrac23+\tfrac{\log_23}3-\tfrac23(\log_23-1)+\tfrac{\log_23}3\;=\;0 . \end{align}\] For (iv)–(vi), evaluating \(\mathrm H\) at the argument triples \(\bigl(\tfrac13,\tfrac19,\tfrac59\bigr)\), \(\bigl(\tfrac13,\tfrac2{15},\tfrac8{15}\bigr)\), \(\bigl(\tfrac13,\tfrac29,\tfrac49\bigr)\) and subtracting from \(\tilde{B}(\tfrac13)\) yields the closed forms in (iv)–(vi), each positive. ◻

Proof. The single difference \(W_{\mathrm{iso}}-F(\cdot,\tfrac\delta3)\) is strictly decreasing by (a), so its unique sign change and its signs at the interior points \(\tfrac25,\tfrac7{16}\) follow from the closed-form values below. (a) \(p_1\le1-p_1\) gives the first claim. Differentiating \(F(p_1,\tfrac\delta3)\) in \(p_1\) (the \(\log_2e\)-terms cancel, since the argument slopes \(1,-\tfrac23,-\tfrac13\) sum to zero): \[\begin{align} \tfrac{d}{dp_1}F\bigl(p_1,\tfrac\delta3\bigr) \;&=\;-\tfrac{1+C}{3}+\log_23+\log_2p_1\\ &\quad-\tfrac23\log_2\delta-\tfrac13\log_2(2-p_1)\\ \;&\ge\;-\tfrac{1+C}{3}+\log_23-\tfrac{\log_25}3 \\ \;&=\;\tfrac{9\log_23+2\log_25-15}{9}, \end{align}\] using \(\log_2p_1\ge-\log_23\), \(\log_2\delta\le-\log_23\), \(\log_2(2-p_1)\le\log_25-\log_23\) and \(C=4-\tfrac53\log_25\); and \(9\log_23+2\log_25>15\).

(b) The value at \(\tfrac13\) is the endpoint value of Lemma 11(iv), since \(W_{\mathrm{iso}}(\tfrac13) =\tilde{B}(\tfrac13)\) by item (i) there; at \(\tfrac12\), \(W_{\mathrm{iso}}(\tfrac12)=\tfrac K2\) while \(F(\tfrac12,0)=K\). The difference is strictly decreasing by (a), whence the unique zero and the sign pattern.

(c) At \(\tfrac25\) (\(\delta=\tfrac15\)): \(\mathrm H_2(\tfrac25) =\log_25-\tfrac25-\tfrac35\log_23\) gives \(W_{\mathrm{iso}}(\tfrac25) =\tfrac{29}{10}+\tfrac35\log_23-\tfrac32\log_25\), and \(\mathrm I(\tfrac1{15})=\tfrac1{15}(\log_23+\log_25)\), \(\mathrm I(\tfrac8{15})=\tfrac8{15}(\log_23+\log_25-3)\) give \(F(\tfrac25,\tfrac1{15})=\tfrac{17}3-\tfrac35\log_23-\tfrac{17}9\log_25\). At \(\tfrac7{16}\) (\(\delta=\tfrac18\)): the terms \(\mathrm I(\tfrac7{16})\) cancel in the difference, which needs only \(\mathrm I(\tfrac1{24})=\tfrac1{24}(3+\log_23)\), \(\mathrm I(\tfrac{25}{48})=\tfrac{25}{48}(4+\log_23-2\log_25)\) and \(\mathrm I(\tfrac9{16})=\tfrac9{16}(4-2\log_23)\). ◻

Proof. Every comparison below is between two curves whose difference is concave, so its sign on the relevant subinterval is fixed by the closed-form values at the endpoints \(\tfrac13,\tfrac25,\tfrac7{16},\tfrac12\) computed here. For concavity, as in Lemma 11, each difference is affine plus terms \(\pm \mathrm I(u(p_1))\) with \(u\) affine of slope \(s\), contributing \(\mp\tfrac{s^2}{u\ln2}\) to the second derivative. Since \(W_{\mathrm{iso}}\) and \(\tilde{B}\) differ by an affine function (Lemma 11(i)), the differences in (i) and (iv) have the same second derivatives as in Lemma 11(iii),(v),(vi), and are therefore concave. For the differences against \(F(\cdot,\tfrac\delta3)\), the second derivatives times \(\ln2\) are \[\begin{align} &\text{(ii), }e_{T_0}:\;-\tfrac1{p_1}-\tfrac8{3\delta}+\tfrac1{3(2-p_1)};\\ &e_{G(\cdot,2\delta/5)}:\; -\tfrac4{15\delta}+\tfrac{9-2p_1}{15(2-p_1)(3-p_1)};\\ &e_{G(\cdot,2\delta/3)}:\; -\tfrac4{3\delta}-\tfrac{\delta}{3(2-p_1)(1+p_1)}, \end{align}\] all negative on \([\tfrac13,\tfrac12)\): \(\tfrac1{3(2-p_1)}\le\tfrac29< \tfrac8{3\delta}\), and \(\tfrac{9-2p_1}{15(2-p_1)(3-p_1)} \le\tfrac{25/3}{15\cdot\frac{3}{2}\cdot\frac{5}{2}}=\tfrac4{27} <\tfrac45\le\tfrac4{15\delta}\) (as \(\delta\le\tfrac13\)).

Exact values. \(h(\tfrac13)=0\): both \(W_{\mathrm{iso}}\) and \(F(\cdot,\delta)\) equal \(\tilde{B}\) at \(\tfrac13\) (Lemma 11(i),(iii)). At \(\tfrac12\): \(\delta=0\) and \(F(\tfrac12,0)=G(\tfrac12,0)=K\), \(T_0(\tfrac12)=K-\tfrac{C}2\) (proof of Lemma 11), giving the values in (ii),(iii). For \(h(\tfrac7{16})\): with \(\mathrm I(\tfrac7{16})=\tfrac7{16}(4-\log_27)\), \(\mathrm I(\tfrac9{16})=\tfrac9{16}(4-2\log_23)\), \(\mathrm I(\tfrac18)=\tfrac38\), one gets \(W_{\mathrm{iso}}(\tfrac7{16})=-\tfrac{51}{32}+\tfrac98\log_23 -\tfrac{15}{32}\log_25+\tfrac7{16}\log_27\) and \(F(\tfrac7{16},\tfrac18)=-\tfrac7{16}-\tfrac{35}{48}\log_25 +\tfrac78\log_27\).

At \(\tfrac25\) (\(\delta=\tfrac15\)), with \(F(\tfrac25,\tfrac1{15})=\tfrac{17}3-\tfrac35\log_23-\tfrac{17}9\log_25\) (Lemma 12): \[\begin{align} G\bigl(\tfrac25,\tfrac2{25}\bigr) &=\tfrac{111}{25}-\tfrac{13}5\log_25+\tfrac{13}{25}\log_213,\\ G\bigl(\tfrac25,\tfrac2{15}\bigr) &=\tfrac{23}5-\tfrac35\log_23-2\log_25+\tfrac7{15}\log_27, \end{align}\] \[T_0\bigl(\tfrac25\bigr)=\tfrac{13}5-\log_25,\] and subtracting each from \(F(\tfrac25,\tfrac1{15})\) gives the three stated closed forms. For the chord bound, substitute \(\mathrm I(\tfrac{13}{25})=\tfrac{13}{25}\cdot2\log_25-\tfrac{13}{25}\log_213\) and then \(\mathrm I(\tfrac{64}{125})=\tfrac{64}{125}(3\log_25-6)\), \(\mathrm I(\tfrac{27}{50})=\tfrac{27}{50}(1+2\log_25-3\log_23)\). ◻

Proof. Write \(E(p_1)\) for the right-hand side (well defined: the two curves agree at \(p^*\)). Strong induction on \(n\); a source with \(p_1<\tfrac12\) has \(n\ge3\), and a block with maximal fraction in \([\tfrac13,\tfrac12)\) has at least three symbols, so the induction is well founded. A sub-block with maximal fraction \(q\) is bounded by: \(q+C\) if \(q<\tfrac13\) (Corollary 2); \(E(q)<K\) if \(q\in[\tfrac13,\tfrac12)\) (induction hypothesis, then the monotonicity of the pieces, Lemma 12(a): on the left piece \(E(q)\le W_{\mathrm{iso}}(\tfrac13)=2-\log_23+\tfrac{C}3<K\), since \(K-W_{\mathrm{iso}}(\tfrac13)=\log_23-\tfrac56-\tfrac5{18}\log_25\ge\tfrac{11}{108}>0\) (by \(\log_23>\tfrac{19}{12}\), \(\log_25<\tfrac73\)), and on the right piece \(E(q)<F(\tfrac12,0)=K\)); \(V(q)\) if \(q\ge\tfrac12\) (Corollary 1). So, exactly as before, every sub-block with maximal fraction \(q<\tfrac12\) has redundancy \(<K\).

Isolate root (\(2p_1+p_2\ge1\)): here \(R=(1-\mathrm H_2(p_1))+(1-p_1)R(\rho)\) with leader fraction \(q=p_2/(1-p_1)\le y:=p_1/(1-p_1)\), and \(y\in[\tfrac12,1)\). If \(q<\tfrac13\), then \(R(\rho)<\tfrac13+C<K\) by Lemma 11(o); if \(q\in[\tfrac13,\tfrac12)\), then \(R(\rho)<K\). In both cases \(R<(1-\mathrm H_2(p_1))+(1-p_1)K=W_{\mathrm{iso}}(p_1)\). If \(q\ge\tfrac12\), then \(R(\rho)<V(q)\le\max\bigl(V(\tfrac12),V(y)\bigr)=\max\bigl(\tfrac12,V(y)\bigr)\), since \(V\) is convex on \([\tfrac12,y]\ni q\). If the maximum is \(\tfrac12\), then \(R<(1-\mathrm H_2(p_1))+\tfrac{1-p_1}2<W_{\mathrm{iso}}\) (as \(\tfrac12<K\)); otherwise \(R<(1-\mathrm H_2(p_1))+(1-p_1)V(y)=T_0(p_1)\) by the grouping identity of Lemma 11. So the isolate root yields \(R<W_{\mathrm{iso}}(p_1)\) or \(R<T_0(p_1)\).

Group root (\(2p_1+p_2<1\)): Lemma 10 bounds \(R\) strictly by one of the four endpoint curves \(F(p_1,\tfrac\delta3)\), \(F(p_1,\delta)\), \(G(p_1,\tfrac{2\delta}5)\), \(G(p_1,\tfrac{2\delta}3)\).

In every case \(R\) is strictly below one of the six curves of Lemma 13, and that lemma bounds each of them by \(W_{\mathrm{iso}}(p_1)\) on \([\tfrac13,p^*]\) and by \(F(p_1,\tfrac\delta3)\) on \([p^*,\tfrac12)\), i.e.by \(E(p_1)\). ◻

Proof. \(W_{\mathrm{iso}}\le\tilde{B}\) is Lemma 11(i), with equality only at \(\tfrac13\); \(F(\cdot,\tfrac\delta3)\le\tilde{B}\) is Lemma 11(iv), with equality only at \(\tfrac12\) (the difference is concave, positive at \(\tfrac13\), zero at \(\tfrac12\)). ◻

Proof. For \(p_1<\tfrac13\): \(R<p_1+C<\tfrac13+C<K\) by Lemma 11(o). For \(p_1\in[\tfrac13,p^*]\): \(R<W_{\mathrm{iso}}(p_1)\le W_{\mathrm{iso}}(\tfrac13) =2-\log_23+\tfrac{C}3<K\), by the monotonicity of Lemma 12(a) and the \(\tfrac{11}{108}\)-certificate in the proof of Theorem 3. For \(p_1\in[p^*,\tfrac12)\): \(R<F(p_1,\tfrac\delta3)<F(\tfrac12,0)=K\), again by Lemma 12(a). ◻

Proof. Left piece. \(p_1+C-W_{\mathrm{iso}}(p_1)\) has derivative \(1-W_{\mathrm{iso}}'=1+\log_2\tfrac{1-p_1}{p_1}+K>0\), so on \([\tfrac13,p^*]\) it is minimised at \(\tfrac13\), where (since \(W_{\mathrm{iso}}(\tfrac13)=\tilde{B}(\tfrac13)\)) it equals \(\tfrac23C-c_3=-\beta\), the critical margin of Lemma 8 resurfacing.

Right piece. \(p_1+C-F(p_1,\tfrac\delta3)\) is concave (its second derivative times \(\ln2\) is \(-\tfrac1{p_1}-\tfrac4{3\delta} -\tfrac1{3(2-p_1)}<0\)), so on \([\tfrac25,\tfrac12]\supseteq[p^*,\tfrac12)\) it is minimised at an endpoint. At \(\tfrac12\) it equals \(\tfrac{C}2\), and at \(\tfrac25\) it equals \(-\tfrac{19}{15}+\tfrac35\log_23+\tfrac29\log_25\), which exceeds \(\tfrac{C}2\); so the margin is at least \(\tfrac{C}2\) throughout. ◻

Proof. Every entropy term is of the form \(\mathrm I(a/b)=\tfrac ab\bigl(\log_2b-\log_2a\bigr)\), so each value is a rational combination of logarithms of small integers. For example, at \(p_1=\tfrac13\), \(\Theta(\tfrac13)=\tfrac{4+2/3}{3}+\tfrac{4}{9}K-\mathrm H\bigl(\tfrac13,\tfrac29,\tfrac49\bigr)\) with \(\mathrm H\bigl(\tfrac13,\tfrac29,\tfrac49\bigr) =\tfrac{\log_23}3+\tfrac29\bigl(\log_29-\log_22\bigr)+\tfrac49\bigl(\log_29-\log_24\bigr) =\tfrac53\log_23-\tfrac{10}9\); substituting \(K=\tfrac52-\tfrac56\log_25\) gives \(\Theta(\tfrac13)=\tfrac{34}9-\tfrac53\log_23-\tfrac{10}{27}\log_25\). The remaining values are identical routine evaluations. ◻

Proof. As in Lemma 14, each item is the evaluation of the stated curves at a rational point, hence a rational combination of \(\log_23,\log_25,\log_27,\log_2{11},\log_2{13},\log_2{19},\log_2{23}\); the displayed closed forms follow by collecting coefficients. For example, (A1) is \((\Pi-\Theta)(\tfrac13)\) with both values taken from Lemma 14: \(1+\tfrac{C-\log_23}2-\tfrac{34}9+\tfrac53\log_23+\tfrac{10}{27}\log_25 =-\tfrac79+\tfrac76\log_23-\tfrac{25}{54}\log_25\). Each sign then follows from Lemma 20(i): replacing each \(\log_2m\) by a rational bound from its continued-fraction expansion reduces the sign to a comparison of integer powers. Coarse bounds such as \(\tfrac{19}{12}<\log_23<\tfrac{27}{17}\) suffice for the items with a comfortable margin; the near-degenerate ones, (A1), (A2), (C2), and (S), use correspondingly higher convergents (for instance \(\log_23<\tfrac{485}{306}\), i.e.\(3^{306}<2^{485}\)). ◻

Proof. On \((0,\tfrac13)\) the bound \(q+C\) increases to the limit \(\tfrac13+C\). On \([\tfrac13,\tfrac12)\), \(E=\max(W_{\mathrm{iso}},F_\ell)\) with \(W_{\mathrm{iso}}\) decreasing and \(F_\ell\) increasing (Lemma 12(a)), so \(E(q)\le\max\bigl(W_{\mathrm{iso}}(\tfrac13),F_\ell(Q)\bigr)\) for \(q\le Q\); and \(W_{\mathrm{iso}}(\tfrac13)\le\tfrac13+C\) is \(\tfrac32c_3\le C\). On \([\tfrac12,1)\), \(V\) is convex, so \(V(q)\le\max\bigl(V(\tfrac12),V(Q)\bigr)=\max\bigl(\tfrac12,V(Q)\bigr)\), while the \([\tfrac13,\tfrac12)\) part contributes at most \(\max(\tfrac13+C,K)=K\) (Lemma 11(o)), and \(\tfrac12<K\). For the last claim it remains to check \(F_\ell(Q)\le Q+C\) on \([\tfrac13,\tfrac12)\): the difference \(Q+C-F_\ell(Q)\) is concave (\(F_\ell\) is affine plus \(-\mathrm I\) of affine arguments, hence convex), so it is bounded below by the smaller of its endpoint values \(\tfrac13+C-F_\ell(\tfrac13)>0\) (certificate (B1)) and \(\tfrac12+C-K=\tfrac{C}2>0\). ◻

Proof. (i) \(2p_1+p_2\le3p_1<1\), so the root does not isolate the leader (Lemma 5); thus \(k\ge2\), and the leader lies in \(L\) since blocks are prefixes.

(ii) Suppose \(2p_1+p_2<a\), i.e.\(p_2<a-2p_1\). By Lemma 3, \(s\le p_k\le p_2<a-2p_1\). If \(a\le\tfrac12\) then \(1-2a<a-2p_1\) gives \(a>\tfrac{1+2p_1}3\ge\tfrac12\) (using \(p_1\ge\tfrac14\)), a contradiction; if \(a>\tfrac12\) then \(2a-1<a-2p_1\) gives \(a<1-2p_1\le\tfrac12\), again a contradiction. Hence \(2p_1+p_2\ge a\) and, by Lemma 5 applied inside \(L\), \(L\) splits as \(\{p_1\}\,|\,L'\): the leader is a leaf at depth \(2\). Identity 11 is the recursion (Lemma 1) at the root, the isolate reduction inside \(L\), and the grouping identity \((1-\mathrm H_2(a))+a\bigl(1-\mathrm H_2(p_1/a)\bigr)=(1+a)-\mathrm H(p_1,x,1-a)\), exactly as in Lemma 10.

(iii) If \(B=\{p_n\}\) then \(1-a=p_n\le p_k\le p_1\), so \(a\ge1-p_1>\tfrac12\); the bound \(s\le p_k\) forces \(p_k\ge2a-1\ge1-2p_1\), and \(p_k\le p_1\) then gives \(p_1\ge\tfrac13\), a contradiction. ◻

Proof. Here \(x=p_2=p_k\le p_1\) and \(R_{L'}=0\), so by 11 and Lemma 16, \(R<h(a):=J(a)+(1-a)\,M(Q(a))\). The constraint \(s\le x\) reads \(a\in[\tfrac{1+p_1}3,\,1-p_1]\), and \(x\le p_1\) caps \(a\le2p_1\); since \(p_1\ge\tfrac14>\tfrac15\) the window is \([\tfrac{1+p_1}3,\,2p_1]\). Along it \(Q\) increases from \(\delta/(2-p_1)<\tfrac13\) (as \(p_1>\tfrac15\)) through \(Q=\tfrac13\) at \(a_{13}:=\tfrac{1+3p_1}4\) and \(Q=\tfrac12\) at \(a_{12}:=\tfrac{1+2p_1}3\), to \(Q(2p_1)=p_1/\delta\ge\tfrac12\) (as \(p_1\ge\tfrac14\); also \(a_{13}\le a_{12}\le 2p_1\) there).

On \([\tfrac{1+p_1}3,a_{13}]\) (\(Q\le\tfrac13\)): \(h(a)=J(a)+x+(1-a)C=F(p_1,x)\) with \(x\in[\tfrac\delta3,\tfrac{1-p_1}4]\). Since \(\partial_xF=2-C+\log_2\tfrac{x}{1-p_1-x}\) is strictly increasing in \(x\) (Lemma 10), \(F\) is decreasing-then-increasing, so \(h\le\max\bigl(F(p_1,\tfrac\delta3),F(p_1,\tfrac{1-p_1}4)\bigr)\).

On \([a_{13},a_{12}]\) (\(\tfrac13\le Q\le\tfrac12\)): \(h\le\max\bigl(\mathrm{fl}(a),\mathrm{co}(a)\bigr)\) pointwise, where \(\mathrm{fl}(a):=J(a)+(1-a)(\tfrac13+C)\) and \(\mathrm{co}(a):=J(a)+(1-a)F_\ell(Q(a))\). Since \(J'=1+\log_2Q\le1+\log_2\tfrac12=0\) here, \(\mathrm{fl}\) is decreasing, and \(\mathrm{fl}(a_{13})=F(p_1,\tfrac{1-p_1}4)\) (at \(Q=\tfrac13\) the two bounds agree). Expanding \((1-a)F_\ell(Q)\) by the scaled grouping identity \((1-a)\sum_i \mathrm I(u_i)=\sum_i \mathrm I\bigl(u_i(1-a)\bigr) -\mathrm I(1-a)\) (\(\sum_i u_i=1\)), \[\begin{align} \mathrm{co}(a)=&(1+a)+\frac{5(1-a)-x}{3} +\frac{2(1-a)-x}{3}\,C\\ &-\mathrm I(p_1)-2\mathrm I(x)\\ &-\mathrm I\Bigl(\frac{1+2p_1-3a}{3}\Bigr) -\mathrm I\Bigl(\frac{2+p_1-3a}{3}\Bigr), \end{align}\] an affine function of \(a\) plus terms \(-\mathrm I(\text{affine})\), which is convex. Hence \(\mathrm{co}\le\max\bigl(\mathrm{co}(a_{13}),\mathrm{co}(a_{12})\bigr)\); \(\mathrm{co}(a_{13})\le\mathrm{fl}(a_{13})\) because \(F_\ell(\tfrac13)\le\tfrac13+C\) (certificate (B1)), and \(\mathrm{co}(a_{12})=J(a_{12})+(1-a_{12})K=\Theta(p_1)\) by \(F_\ell(\tfrac12)=K\) (Lemma 14).

On \([a_{12},2p_1]\) (\(Q\ge\tfrac12\)): \(h\le\max\bigl(\mathrm{fl}_K(a),f(a)\bigr)\) pointwise, where \(\mathrm{fl}_K:=J+(1-a)K\) and \(f:=J+(1-a)V(Q)\). \(\mathrm{fl}_K\) is convex (\(J''>0\)), so \(\mathrm{fl}_K\le\max\bigl(\mathrm{fl}_K(a_{12}),\mathrm{fl}_K(2p_1)\bigr) =\max\bigl(\Theta(p_1),N_K(p_1)\bigr)\). Expanding \((1-a)\mathrm H_2(Q)=\mathrm I(x)+\mathrm I(1+p_1-2a)-\mathrm I(1-a)\), \[f(a)=3-2a+p_1-\mathrm I(p_1)-2\mathrm I(a-p_1)-\mathrm I(1+p_1-2a),\] again convex, so \(f\le\max\bigl(f(a_{12}),f(2p_1)\bigr)\); here \(f(a_{12})=J(a_{12})+(1-a_{12})V(\tfrac12)\le\Theta(p_1)\) (as \(V(\tfrac12)=\tfrac12<K\)) and \(f(2p_1)=N(p_1)\). ◻

Proof. Here \(L'=\{p_2,p_3\}\), \(p_3=x-p_2=p_k\), and \(x\,R_{L'}=x\bigl(1-\mathrm H_2(p_2/x)\bigr)\) exactly. Using \(x\,\mathrm H_2(p_2/x)=\mathrm I(p_2)+\mathrm I(p_3)-\mathrm I(x)\), 11 and Lemma 16 give \[\begin{align} R\;<\;v(a,p_3):=&(1+a)+x-\mathrm I(p_1)-\mathrm I(1-a)\\ &-\mathrm I(x-p_3)-\mathrm I(p_3) +(1-a)\,M\Bigl(\frac{p_3}{1-a}\Bigr). \end{align}\] The constraints are \(s\le p_3\le x/2\) (Lemma 3; \(p_3\) is the smaller of the pair), which force \(a\in[\tfrac{2+p_1}5,\tfrac{2-p_1}3]\); the sorting constraint \(p_2\le p_1\) is automatic: for \(a\ge\tfrac12\), \(p_2\le x-s=1-p_1-a\le\tfrac12-p_1\le p_1\), and for \(a<\tfrac12\), \(p_2\le x-s=3a-1-p_1<\tfrac12-p_1\le p_1\) (using \(p_1\ge\tfrac14\)). Since \(a\le\tfrac{2-p_1}3<\tfrac{1+p_1}2\) (as \(p_1>\tfrac15\)) we have \(x<1-a\), so \(p_3/(1-a)\le x/(2(1-a))<\tfrac12\), and Lemma 16 gives \(M\bigl(p_3/(1-a)\bigr)\le p_3/(1-a)+C\). Hence \[\begin{align} v\;\le\;w(a,p_3):=&(1+a)+x+p_3+(1-a)\,C\\ &-\mathrm I(p_1)-\mathrm I(1-a)-\mathrm I(x-p_3)-\mathrm I(p_3). \end{align}\] For fixed \(a\), \(w\) is convex in \(p_3\), so \(w\le\max\bigl(w(a,s),\,w(a,x/2)\bigr)\).

Balanced corner \(w(a,x/2)\). This is convex in \(a\) (affine plus \(-\mathrm I(1-a)-2\mathrm I(x/2)\)) on \([\tfrac{2+p_1}5,\tfrac{2-p_1}3]\), hence at most \(\max(E_1,E_2)\), its values at the two endpoints (at \(a=\tfrac{2+p_1}5\): \(x/2=\tfrac{1-2p_1}5=s\); at \(a=\tfrac{2-p_1}3\): \(x/2=\tfrac{1-2p_1}3=s\)).

Key-tight corner \(w(a,s)\). On \(a\le\tfrac12\), \(s=1-2a\) and \(x-s=3a-1-p_1\), so \(w(a,s)\) is affine plus \(-\mathrm I(1-a)-\mathrm I(3a-1-p_1)-\mathrm I(1-2a)\), hence convex; on \(a\ge\tfrac12\), \(s=2a-1\) and \(x-s=1-p_1-a\), so it is likewise convex. Hence it is bounded by its values at \(a\in\{\tfrac{2+p_1}5,\tfrac12,\tfrac{2-p_1}3\}\). The extreme endpoints coincide with those of the balanced corner (there \(s=x/2\)), and at \(a=\tfrac12\), \(s=0\): \(w(\tfrac12,0)=\tfrac32+x+\tfrac{C}2-\mathrm I(p_1)-\mathrm I(\tfrac12)-\mathrm I(x) =\Pi(p_1)\) with \(x=\tfrac12-p_1\). ◻

Proof. Now \(p_k\le\min\bigl(p_2,\tfrac{x-p_2}2\bigr)\le\tfrac x3\) (the rest \(L'\setminus\{p_2\}\) has \(\ge2\) symbols, each \(\ge p_k\)), so the constraint \(s\le p_k\le x/3\) confines \(a\in[\tfrac{3+p_1}7,\tfrac{3-p_1}5]\), whence \(1-a\ge\tfrac{2+p_1}5\) and \(p_k/(1-a)\le\tfrac{x/3}{1-a}\le\tfrac{1-2p_1}{2+p_1}<\tfrac13\) (as \(p_1>\tfrac17\)): the right part is always bounded affinely, \((1-a)R_B<p_k+(1-a)\,C\). The redundancy of \(L'\) is bounded by \(x\,\mathrm{ch}(q')\), \(q':=p_2/x\). Since the total is increasing in \(p_k\), put \(p_k=\min\bigl(p_2,\tfrac{x-p_2}2\bigr)\) and write \(D(a):=J(a)+(1-a)\,C\).

Branch \(p_2\le x/3\) (\(p_k=p_2\), \(q'\le\tfrac13\); Lemma 16 gives \(\mathrm{ch}(q')\le q'+C\) there): the total is at most \(D+2p_2+xC\), increasing in \(p_2\), hence at most \(\Lambda(a):=D(a)+\tfrac{2x}3+xC\), which is convex in \(a\) (\(J''>0\)), so \(\Lambda\le\max(\Lambda_1,\Lambda_2)\), its endpoint values at \(x=\tfrac{3\delta}7\) and \(x=\tfrac{3\delta}5\).

Branch \(p_2\ge x/3\) (\(p_k=\tfrac{x-p_2}2\)): the total is \(g(p_2):=D(a)+x\,\mathrm{ch}(q')+\tfrac{x-p_2}2\) with \(p_2\in[\tfrac x3,\,x-2s]\) (the ceiling from \(p_k\ge s\)); note \(q'\le q'_{\max}:=1-2s/x\), and \(q'\ge\tfrac12\) occurs (iff \(p_2\ge x/2\)) only when \(s\le x/4\). Bound \(\mathrm{ch}\) by its three regime forms; each resulting expression is convex (or monotone) in \(p_2\): the form \(D+x(\tfrac13+C)+\tfrac{x-p_2}2\) (valid for \(q'\in[\tfrac13,\tfrac12)\) via \(W_{\mathrm{iso}}\le\tfrac13+C\), as in Lemma 16) is decreasing in \(p_2\), hence at most its value \(\Lambda(a)\) at \(p_2=\tfrac x3\); the form \(D+xF_\ell(p_2/x)+\tfrac{x-p_2}2\) is convex in \(p_2\) (the scaled \(xF_\ell(p_2/x)\) has \(\mathrm I\)-arguments \(p_2,\tfrac{x-2p_2}3,\tfrac{2x-p_2}3\), affine in \(p_2\)), with maximum at \(p_2=\tfrac x3\) (where (B1) gives \(\le\Lambda(a)\)) or at \(p_2=\min(\tfrac x2,x-2s)\); the form with \(V(q')\) (\(q'\ge\tfrac12\), so \(s\le x/4\)) is convex in \(p_2\) via \(xV(p_2/x)=2x-p_2-\mathrm I(p_2)-\mathrm I(x-p_2)+\mathrm I(x)\), with maximum at \(p_2=\tfrac x2\) (value \(\le D+xK+\tfrac x4\), as \(V(\tfrac12)=\tfrac12<K\)) or at \(p_2=x-2s\). Three corner curves in \(a\) remain.

(a) The half corner \(\kappa_0(a):=D(a)+xK+\tfrac x4\) (from \(p_2=\tfrac x2\); by \(F_\ell(\tfrac12)=K\) it also dominates the \(F_\ell\)-bound there), defined for \(s\le\tfrac x4\), i.e. \(a\in[\tfrac{4+p_1}9,\tfrac{4-p_1}7]\). It is convex, so \(\kappa_0\le\max(\Theta'',\Theta')\), its endpoint values.

(b) The Key-tight corner with \(q'_{\max}<\tfrac12\) (\(p_2=x-2s\), \(\tfrac x4\le s\le\tfrac x3\)): the expression \(D+xF_\ell(1-2s/x)+s\) has \(\mathrm I\)-arguments \(x-2s,\;\tfrac{4s-x}3,\;\tfrac{x+2s}3\), all affine in \(a\) on either side of \(a=\tfrac12\), hence convex there; and its window endpoints are \(s=\tfrac x3\) (\(q'_{\max}=\tfrac13\), value \(\le\Lambda(a)\) by (B1)) and \(s=\tfrac x4\) (\(q'_{\max}=\tfrac12\), value \(=\kappa_0\) at the corresponding endpoint). Sorting is inactive here: \(p_2=x-2s\le\tfrac x2\le\tfrac{3\delta}{10}<\tfrac14\le p_1\).

(c) The Key-tight corner with \(q'_{\max}\ge\tfrac12\) (\(p_2=x-2s\), \(s\le\tfrac x4\), \(V\)-bound): \[\begin{align} m(a)\;=\;&(1+a)-\mathrm I(p_1)-\mathrm I(1-a)\\ &+(1-a)\,C+x+3s-\mathrm I(x-2s)-\mathrm I(2s), \end{align}\] convex on either side of \(a=\tfrac12\); its corners are \(a=\tfrac12\), where \(s=0\) and \(m=\Pi(p_1)\) exactly, and \(s=\tfrac x4\), where \(2\mathrm I(\tfrac x2)=x+\mathrm I(x)\) gives \(m=\kappa_0-x\bigl(K-\tfrac12\bigr)\le\kappa_0\). Sorting is again inactive: over this branch \(p_2=x-2s\) is maximised at \(a=\tfrac12\), where it equals \(\tfrac12-p_1\le p_1\). ◻

Proof. Every difference is affine in \(p_1\) plus terms \(\pm \mathrm I(u(p_1))\) with \(u\) affine; second derivatives are computed as in Lemma 11, and endpoint signs are Lemmas 14 and 15.

(a) \(\Theta-F(\cdot,\tfrac\delta3)\): second derivative \(\bigl[\tfrac1{1-p_1}-\tfrac4{3\delta}-\tfrac1{3(2-p_1)}\bigr]/\ln2<0\) (\(\delta\le\tfrac12\) gives \(\tfrac4{3\delta}\ge\tfrac83\) while \(\tfrac1{1-p_1}\le\tfrac32\)), so concave, and \(\ge0\) at both ends ((C1) at \(\tfrac14\); \(0\) exactly at \(\tfrac13\), the contact of Lemma 14), hence \(\ge0\) between. \(\Theta-F(\cdot,\tfrac{1-\cdot}4)\) is affine (Lemma 14) and positive at both ends ((C2)). \(\Theta-N_K\): second derivative \(\bigl[\tfrac1{1-p_1}-\tfrac1{p_1}-\tfrac4\delta\bigr]/\ln2<0\), so concave; it vanishes exactly at \(\tfrac14\) (both values \(\tfrac{1+C}4\)) and is positive at \(\tfrac13\) ((C3)).

(b) \(\Pi'=-1+\log_2\tfrac{p_1}{1/2-p_1}\le0\) iff \(p_1\le2\bigl(\tfrac12-p_1\bigr)\), i.e.\(p_1\le\tfrac13\). Each of \(E_1,E_2,\Lambda_1,\Theta''\) is convex, so bounded by the larger of its values at \(p_1\in\{\tfrac14,\tfrac13\}\), and all eight values are below \(\Pi(\tfrac13)\): (D1)–(D4).

(c) \(\Pi-\Lambda_2\): the terms \(-\mathrm I(p_1)\) cancel; the second derivative is \(\bigl[\tfrac2\delta-\tfrac{12}{5\delta}-\tfrac1{5(2+p_1)}\bigr]/\ln2 =\bigl[-\tfrac2{5\delta}-\tfrac1{5(2+p_1)}\bigr]/\ln2<0\), so concave and positive at both ends ((D5)). \(\Pi-\Theta'\): second derivative \(\bigl[\tfrac2\delta-\tfrac{16}{7\delta}-\tfrac1{7(3+p_1)}\bigr]/\ln2<0\), so concave and positive at both ends ((D6)). ◻

Proof. \((\Pi-\Theta)''\ln2=\tfrac1{1/2-p_1}-\tfrac1{1-p_1}>0\) (the \(-\mathrm I(p_1)\) terms cancel; the \(\Theta\)-terms contribute \(-\tfrac1{3(1-p_1)}-\tfrac2{3(1-p_1)}\)), and \((\Theta-N)''\ln2=\tfrac1{1-p_1}-\tfrac2{p_1}-\tfrac9{1-3p_1}<0\). The values at \(\tfrac14\) are Lemma 14. A convex function positive at \(\tfrac14\) and negative at \(\tfrac13\) has exactly one zero there with the stated sign pattern (its derivative changes sign at most once); likewise the concave difference in (ii). For (iii), the two certified signs at \(\rho\) place \(\rho\) strictly between the zeros. ◻

Proof. By Lemma 17 every source in the regime satisfies 11 , and by Propositions 3–5 (the three possible sizes of \(L'\)), \[\begin{align} R\;<\;\max\Bigl\{&F\bigl(\cdot,\tfrac\delta3\bigr), F\bigl(\cdot,\tfrac{1-\cdot}4\bigr),\Theta,N_K,N,\\ &\;\Pi,E_1,E_2,\Lambda_1,\Lambda_2,\Theta',\Theta''\Bigr\}(p_1). \end{align}\] By Lemma 18 every listed curve except \(\Pi,\Theta,N\) is dominated by \(\Theta\) or by \(\Pi\) on all of \([\tfrac14,\tfrac13]\), so \(R<\max(\Pi,\Theta,N)\); Lemma 19 identifies the maximum piecewise. ◻

Proof. On \([\tfrac14,b_1]\): \(p_1+C-\Pi\) has derivative \(2-\log_2\tfrac{p_1}{1/2-p_1}\ge2-\log_22>0\), so the margin is minimised at \(\tfrac14\), value \(\tfrac{C}2\). On \([b_1,b_2]\): \(p_1+C-\Theta\) is concave (\(\Theta\) is convex), positive at \(\tfrac14\) (\(\tfrac34C\)) and at \(\tfrac13\) (since \(\Theta(\tfrac13)<N(\tfrac13^-)=2-\log_23\) by (A2), it exceeds \(\tfrac13+C-(2-\log_23)>0\)). On \([b_2,\tfrac13)\): \(p_1+C-N\) has derivative \(1-N'=4+3\log_2\tfrac{1-3p_1}{p_1}\), and on \([b_2,\tfrac13)\subset[\rho,\tfrac13)\) one has \(\tfrac{1-3p_1}{p_1}\le\tfrac{1-3\rho}{\rho}=\tfrac3{23}<2^{-4/3}\), so the margin decreases to the limit \(\tfrac13+C-(2-\log_23)>0\) at \(\tfrac13^-\) ((A3)). Finally \(W_3\) increases to \(N(\tfrac13^-)=2-\log_23\) along the third piece (there \(N'=-3+3\log_2\tfrac{p_1}{1-3p_1}>0\), since \(p_1>2(1-3p_1)\) for \(p_1>\tfrac27\)), while on the first two pieces \(W_3\le\Pi(\tfrac14)<2-\log_23\) (\(\Pi\) decreasing; on \([b_1,b_2]\), \(\Theta\le\max\bigl(\Theta(b_1),\Theta(b_2)\bigr) =\max\bigl(\Pi(b_1),N(b_2)\bigr)\); and (A3)). ◻

Proof. Fix \(p_1\in[\tfrac14,\tfrac13)\) and \(0<\varepsilon<\tfrac12\), and consider \[p^{(\varepsilon)} =\bigl(p_1,p_1,p_1,(1-3p_1)(1-\varepsilon),(1-3p_1)\varepsilon\bigr).\] It is sorted because \(1-3p_1\le p_1\). The root prefix imbalances at the first three cuts are \[1-2p_1,\qquad |4p_1-1|,\qquad 6p_1-1,\] and the second is minimal for \(\tfrac14\le p_1<\tfrac13\); the fourth cut has imbalance \(1-2(1-3p_1)\varepsilon\ge\tfrac12\), while \(|4p_1-1|\le\tfrac13\). Thus the root split is \((p_1,p_1)\,|\,(p_1,(1-3p_1)(1-\varepsilon),(1-3p_1)\varepsilon)\). The left child has zero redundancy. In the right child the leader fraction is \(p_1/(1-2p_1)\ge\tfrac12\), so it isolates; the remaining pair has redundancy \(1-\mathrm H_2(\varepsilon)\). Applying Lemma 1 twice gives \[\begin{align} R(p^{(\varepsilon)}) =\;&1-\mathrm H_2(2p_1)\\ &+(1-2p_1)\Bigl(1-\mathrm H_2\Bigl(\frac{p_1}{1-2p_1}\Bigr)\Bigr)\\ &+(1-3p_1)\bigl(1-\mathrm H_2(\varepsilon)\bigr). \end{align}\] Letting \(\varepsilon\downarrow0\) and grouping entropy terms, \[R(p^{(\varepsilon)})\longrightarrow 3-3p_1-\mathrm H(p_1,p_1,p_1,1-3p_1)=N(p_1).\] For \(p_1\in[b_2,\tfrac13)\), Theorem 4 gives the matching strict upper bound \(R<N(p_1)\) for every finite source, so the supremum is exactly \(N(p_1)\) and is not attained. ◻

Proof. (i) is the two displayed identities. (ii): \(\mathrm I(u)=-u\log_2u\) has \(\mathrm I''(u)=-1/(u\ln2)\), so \(g''=\sum_j c_j s_j^{\,2}\,\mathrm I''(u_j)\) equals the stated sum; a concave function on an interval attains its minimum, and a convex function its maximum, at an endpoint. ◻