Proof. Choose \(n \in \mathbb{N}\) with \(nx \ge 1\), let \(\mathcal{Z}_i = \{0, 1\}\), and let \(Z_1, \ldots, Z_n\) be independent Bernoulli\((1/2)\) \(\{0,1\}\)-valued random variables. Define \[f_Z(t) := \frac{1}{\sqrt{nx}} \prod_{i=1}^n \mathbf{1}_{\{Z_i \le t\}}\,.\] Because \(nx \ge 1\), the function \(f_Z\) takes values in \([0,1]\) and is non-decreasing, so \(f_Z \in \mathcal{M}\). Flipping a single coordinate \(Z_i\) alters the product of indicators by at most \(1\), with equality attained, so \(c_i(f) = 1/\sqrt{nx}\). Summing the squares gives \(\eta_f = \bigl( n \cdot (1/\sqrt{nx})^2 \bigr)^{-1} = x\).

For every realisation \(z\), the function \(f_z\) is not equal to its expectation function, so the centred supremum is positive. Thus, \(u_{f_Z}>0\) by Lemma 4. ◻

Proof. We use the following elementary fact, whose proof is a standard exercise in monotonicity: if \(g, h \in \mathsf{M}\) and \(Q_g := \mathbb{Q} \cup D_g\), where \(D_g\) is the countable set of discontinuities of \(g\), then \[\sup_{t \in \mathbb{R}} \left| h(t) - g(t) \right| = \sup_{t \in Q_g} \left| h(t) - g(t) \right|\,.\] Let \(f_Z \in \mathcal{M}\), and write \(\mathbf{F}_Z(t) := \mathbb{E}\left[f_Z(t)\right]\) for the expectation of the randomised monotone function. Because \(f_z \in \mathsf{M}\) for each \(z\), the function \(\mathbf{F}_Z\) also belongs to \(\mathsf{M}\), as a pointwise expectation of members of \(\mathsf{M}\). Hence, for each \(z \in \mathcal{Z}\), \[\sup_{t \in \mathbb{R}} \left| f_z(t) - \mathbf{F}_Z(t) \right| = \sup_{t \in Q_{\mathbf{F}_Z}} \left| f_z(t) - \mathbf{F}_Z(t) \right|\,.\] The set \(Q_{\mathbf{F}_Z}\) is countable and does not depend on \(z\). For each \(t \in Q_{\mathbf{F}_Z}\), the map \[z \mapsto |f(z, t) - \mathbf{F}_Z(t)|\] is measurable, since \(z \mapsto f(z, t)\) is measurable and \(\mathbf{F}_Z(t)\) does not depend on \(z\). Therefore \[z \mapsto \sup_{t \in Q_{\mathbf{F}_Z}} \left| f(z, t) - \mathbf{F}_Z(t) \right|\] is measurable, being the supremum of a countable family of measurable functions, and the first displayed equality completes the proof. ◻

Proof. By Lemma 6 the centred supremum is measurable, so Lemma 4 applies. If \(u_{f_Z} = 0\), the centred supremum is almost surely zero, and every \(u > 0\) is admissible. If \(u_{f_Z} > 0\), then \(u_{f_Z}\) is admissible by Lemma 4 and so is \(u\). ◻

Proof of Proposition 1. Define \(U \colon \mathbb{R}_+ \to \mathbb{R}_+\) by \(U(0) = 0\) and, for \(x > 0\), \[U(x) := \sup\{u_{f_Z} : f_Z \in \mathcal{M},\;\eta_f = x\}\,.\] By Lemma 5 the set is non-empty, and by Lemma 4 it is bounded above by \(2x/\ln 2\), so \(U\) is defined.

Admissibility of \(U\). The value at zero is irrelevant for admissibility, because no \(f_Z\in\mathcal{M}\) has \(\eta_f=0\). For \(x>0\), \(U(x) \ge u_{f_Z}\) for every \(f_Z \in \mathcal{M}\) with \(\eta_f=x\). Because \(x>0\), there exists by Lemma 5 \(f_Z\in \mathcal{M}\) with \(\eta_f=x\) and \(u_{f_Z}>0\). Thus, \(U(x)>0\) and is admissible by Lemma 7.

Identification \(U_\mathcal{M} = U\). For any pointwise admissible \(V \colon \mathbb{R}_+ \to \mathbb{R}_+\) and any \(f_Z \in \mathcal{M}\) with \(\eta_f = x\), the bound at \(V(x)\) holds, so \(V(x) \ge u_{f_Z}\). Taking the supremum over \(f_Z\) gives \(V(x) \ge U(x)\), and taking the infimum over pointwise admissible \(V\) gives \(U_\mathcal{M}(x) \ge U(x)\). Conversely, \(U\) is itself pointwise admissible by the previous paragraph, so \(U_\mathcal{M}(x) \le U(x)\). Hence \(U_\mathcal{M} = U\), and the displayed inequality of the proposition is the admissibility of \(U_\mathcal{M}\) at \(\eta_f\).

Monotonicity. Let \(y \ge x > 0\) and let \(f_Z \in \mathcal{M}\) with \(\eta_f = x\). Define \(g_Z := \sqrt{x/y}\, f_Z\). Because \(0<\sqrt{x/y}\le 1\), the function \(g_Z\) still takes values in \([0,1]\) and is non-decreasing. Thus, \(g_Z \in \mathcal{M}\). By Lemma 2 with \(a = \sqrt{x/y}\), \(\eta_g = y\) and \(g_Z\) is equivalent to \(f_Z\), hence \(u_{g_Z} = u_{f_Z}\). Taking the supremum over \(f_Z\) with \(\eta_f = x\) gives \(U_\mathcal{M}(y) \ge U_\mathcal{M}(x)\).

Lower bound. Specialise the construction of Lemma 5 to \(n = 1\), so \(f_Z(t) = \mathbf{1}_{\{Z_1 \le t\}}\) with \(\eta_f = 1\), and let \(Z_1\) be uniform on \(\{0, 1\}\). For each \(t \in [0, 1)\), \(f_Z(t) = \mathbf{1}_{\{Z_1 = 0\}}\) takes the values \(0\) and \(1\) with equal probability, so \(|f_Z(t) - \mathbb{E}\left[f_Z(t)\right]| = \tfrac{1}{2}\). Hence \(\sqrt{\eta_f}\, \sup_t |f_Z(t) - \mathbb{E}\left[f_Z(t)\right]| = \tfrac{1}{2}\) surely.

Because \(\sqrt{\eta_f}\,\sup_{t \in \mathbb{R}}|f_Z(t) - \mathbb{E}\left[f_Z(t)\right]| = 1/2\) surely, Lemma 3 gives \(u_{f_Z} = \frac{2(1/2)^2}{\ln 2} = 1/(2\ln 2)\). Hence \[U_\mathcal{M}(1) \ge 1/(2 \ln 2)\,,\] and monotonicity extends this to every \(x \ge 1\). ◻

Proof. Let \(x \ge 4\) and define \(n_x := \lfloor \log_4 x \rfloor\). Set \(S = \mathcal{Q}_{n_x}\). We have \(\rho(S) = 0\). The hypercube \(\mathcal{Q}_{n_x}\) admits a Hamiltonian path with \(\mathcal{L}(S) = 2^{n_x} - 1\).

We have \[(2^{n_x} - 1 + n_x)^2 \le n_x 4^{n_x}\,.\] Indeed, \[2^{n_x}+n_x-1 \le \sqrt{n_x}\,2^{n_x}\,.\] For \(n_x=1\) this is equality. For \(n_x\ge2\), it follows because \[n_x-1=(\sqrt{n_x}-1)(\sqrt{n_x}+1) \le (\sqrt{n_x}-1)2^{n_x}\,.\] Thus, because \(\mathcal{L}(S)=2^{n_x}-1\) and \(4^{n_x}\le x\), \[\frac{(\mathcal{L}(S)+n_x)^2}{n_x} \le 4^{n_x} \le x \,.\]

Lemma 10 and the monotonicity of \(U_{\mathcal{M}}\) imply \[\sqrt{U_{\mathcal{M}}(x)} \ge \frac{n_x}{\sqrt{2n_x\ln 2}} = \frac{1}{\sqrt{2\ln 2}}\sqrt{n_x} \,.\] Because \(n_x \ge \log_4 x - 1\), the claim follows. ◻

Proof of Lemma 10. If \(n - 2\rho(S) \le 0\), the lower bound is non-positive and holds because \(U_{\mathcal{M}}\) is non-negative. Assume \(n - 2\rho(S) > 0\).

Identify \(\{0,1\}^n\) with the oriented cube \(\mathcal{Z} = \{-1,1\}^n\) via the standard bijection. Identify \(S\) with a subset \(\Theta \subseteq \mathcal{Z}\), preserving \(\rho(\Theta) = \rho(S)\) and \(\mathcal{L}(\Theta) = \mathcal{L}(S)\). Define \[\label{eq:f-extreme} f(z,\theta) = \langle z, \theta \rangle \,.\tag{3}\]

Because \(\langle z, \theta \rangle = n - 2d_H(z,\theta)\), we have \[\min_{z\in \mathcal{Z}} \max_{\theta\in \Theta} \langle z, \theta \rangle = n - 2\rho(\Theta) \,.\] This establishes \(\sup_{\theta\in \Theta} f(z,\theta) \ge n - 2\rho(\Theta)\) for all \(z\in \mathcal{Z}\).

We have \(c_i(f) = 2\) for all \(i\), because changing \(z_i\) to \(-z_i\) alters \(\langle z, \theta\rangle\) by \(\pm 2\theta_i\) with \(\theta_i \in \{-1, 1\}\). This gives \(\eta_f = 1/(4n)\). Thus, \[\sqrt{\eta_f} \sup_{\theta\in \Theta} f(z,\theta) \ge \frac{n - 2\rho(\Theta)}{2\sqrt{n}}, \qquad \text{for every } z \in \mathcal{Z} \,.\]

Let \(Z\) be uniformly distributed over \(\mathcal{Z}\). Because \(\mathbb{E}\left[f_Z(\theta)\right]=0\) and \(n - 2\rho(\Theta) > 0\), we have \[\sqrt{\eta_f} \sup_{\theta\in\Theta} |f(z,\theta) - \mathbb{E}\left[f_Z(\theta)\right]| \ge \sqrt{\eta_f} \max_{\theta\in\Theta} f(z,\theta) \ge \frac{n - 2\rho(\Theta)}{2\sqrt{n}}\] for every \(z\in\mathcal{Z}\). In particular, \[\mathbb{P}\left\{ \sqrt{\eta_f} \sup_{\theta\in \Theta} \left| f_Z(\theta) - \mathbb{E}\left[f_Z(\theta)\right] \right| \ge \frac{n - 2\rho(\Theta)}{2\sqrt{n}} \right\} = 1 \,.\] Therefore, \[\sqrt{u_{f_Z}} \ge \frac{n - 2\rho(\Theta)}{\sqrt{2n \ln 2}} \,.\] To see this note that for arbitrary \(0<u < (n - 2\rho(\Theta))^2/(2n\ln 2)\), taking \(\varepsilon = (n - 2\rho(\Theta))/(2\sqrt{n}\sqrt{u})\) gives \(\varepsilon\sqrt{u} = (n - 2\rho(\Theta))/(2\sqrt{n})\) and \(2\mathrm{e}^{-2\varepsilon^2} < 1\). Thus, \(u_{f_Z}\ge u\).

Let \(m = |\Theta|\) and order \(\Theta = \{\theta_1, \theta_2, \ldots, \theta_m\}\) to match the shortest path \(\mathcal{L}(\Theta)\). Define the surjective mapping \(\sigma \colon \mathbb{R} \to \Theta\) by \(\sigma(t) = \theta_{j(t)}\), where \[j(t) = \max\{1, \min\{m, \lfloor t \rfloor\}\} \,.\] Define \(g \colon \mathcal{Z} \times \mathbb{R} \to \mathbb{R}\) by \[g(z,t) = \frac{1}{2(\mathcal{L}(\Theta) + n)}\left( n + f(z, \sigma(t)) + 2\sum_{k=2}^{j(t)} d_H(\theta_k, \theta_{k-1}) \right) \,,\] where the sum evaluates to zero for \(j(t)=1\).

Because \(f(z, \theta) \in [-n, n]\) and the sum of successive distances is at most \(\mathcal{L}(\Theta)\), the mapping \(g_Z\) takes values in \([0,1]\). If \(j\ge2\), then \[f(z,\theta_j)-f(z,\theta_{j-1}) \ge -2d_H(\theta_j,\theta_{j-1})\,.\] The added term therefore compensates for any fall in the inner product, so \(g_Z(t)\) is non-decreasing in \(t\). Thus, \(g_Z \in \mathcal{M}\).

By Lemma 2, \(g_Z\) is equivalent to \(f_Z\) with \[\eta_{g} = 4(\mathcal{L}(\Theta) + n)^2 \eta_f = \frac{(\mathcal{L}(\Theta)+n)^2}{n} \,.\] Evaluating \(U_{\mathcal{M}}\) gives \[\sqrt{U_{\mathcal{M}}\left(\frac{(\mathcal{L}(\Theta)+n)^2}{n}\right)} = \sqrt{U_{\mathcal{M}}(\eta_g)} \ge \sqrt{u_{g_Z}} = \sqrt{u_{f_Z}} \ge \frac{n - 2\rho(\Theta)}{\sqrt{2n \ln 2}} \,,\] completing the proof. ◻

Proof. For \(1 < x \le 4^8\), the bound holds by the lower estimate in Proposition 1. Specifically, Proposition 1 establishes \(U_{\mathcal{M}}(x) \ge (2\ln 2)^{-1}\) for all \(x\ge 1\). Note that \[\sqrt{\log_4(4^8)} - (2\ln 2)^{-1/2} = \sqrt{8} - (2\ln 2)^{-1/2} < 2\,,\] and \[2 \min\left\{1, \frac{2\ln(\mathrm{e}+ \ln x)}{\sqrt{\ln x}}\right\} = 2, \qquad \text{for } 1< x\le 4^{55}\,.\] Together these establish the bound for \(1 < x \le 4^8\).

By Corollary 1, for \(x \ge 4^8\), the residual gap is bounded by \[\sqrt{\log_4 x} - \sqrt{U_{\mathcal{M}}(x)} \le \sqrt{\log_4 x} - \frac{1}{\sqrt{2\ln 2}}\sqrt{\log_4 x - 1} \,.\] Letting \(y = \log_4 x\) and \(a = 2\ln 2\), direct calculation shows that \[\sqrt{y} - \frac{\sqrt{y-1}}{\sqrt{a}} \le 2, \qquad 1 \le y \le 170\,,\] and \[\sqrt{a}y -\sqrt{y^2-y} \le 4\ln(\mathrm{e}+ay), \qquad 1 \le y \le 111\,.\] These together give \[\sqrt{y} - \frac{\sqrt{y-1}}{\sqrt{a}} \le 2\min\left\{1, \frac{2\ln(\mathrm{e}+ay)}{\sqrt{ay}}\right\} \,,\] for the remaining range \(8 \le y \le 111\). ◻

Proof. That \(n_k\) is an integer is immediate. The number \(r_k\) is an integer because \(t_k(t_k-1)\) is even. The remaining defining conditions are \(t_k\ge2\) and \(m_k\le2^{n_k}\). ◻

Proof. The maximal path length is bounded by \[\mathcal{L}(S) \le n_k(|S|-1) \,,\] which implies \((\mathcal{L}(S) + n_k)^2/n_k \le n_k|S|^2\). Thus, the monotonicity of \(U_{\mathcal{M}}\) and Lemma 10 imply \[\begin{align} \sqrt{U_{\mathcal{M}}(n_k m_k^2 )} & \ge \sqrt{U_{\mathcal{M}} (n_k |S|^2 )} \\ & \ge \sqrt{U_{\mathcal{M}} \left( \frac{(\mathcal{L}(S) + n_k)^2}{n_k} \right)} \\ & \ge \frac{1}{\sqrt{2\ln 2}} \frac{n_k - 2\rho(S)}{\sqrt{n_k}} \\ & \ge \frac{1}{\sqrt{2\ln 2}} \frac{n_k - 2r_k}{\sqrt{n_k}} \,. \end{align}\] Because any constellation satisfies \[\frac{n_k - 2r_k}{\sqrt{n_k}} = \sqrt{k} \,,\] the stated bound is established. ◻

Proof. Let \(s_1, \dots, s_{m_k}\) be independent random variables uniformly distributed over \(\mathcal{Q}_{n_k}\). Applying the union bound over all \(q \in \mathcal{Q}_{n_k}\) we obtain \[\begin{align} \mathbb{P}\left\{ \max_{q\in \mathcal{Q}_{n_k}} \min_{1 \le j \le m_k} d_H(q,s_j) > r_k \right\} & \le 2^{n_k}\left(1 - \frac{1}{2^{n_k}} \sum_{j=0}^{r_k}\binom{n_k}{j}\right)^{m_k} \\ & < 2^{n_k} \exp\left[- \frac{m_k}{2^{n_k}} \sum_{j=0}^{r_k}\binom{n_k}{j}\right] \,. \end{align}\] Under the stated hypothesis, this probability is strictly less than \(1\). This establishes the existence of a set \(S \subseteq \mathcal{Q}_{n_k}\) satisfying \(|S| \le m_k\) and \(\rho(S) \le r_k\). The conclusion follows directly from Lemma 13. ◻

Proof. By Lemma 14, the conclusion holds if \[\frac{1}{2^{n_k}} \sum_{j=0}^{r_k} \binom{n_k}{j} \ge \frac{1}{m_k} n_k \ln 2 \,.\] Lemma 32 in Appendix 7.1 provides a lower bound on the relevant binomial shell: \[\frac{1}{2^{n_k}}\binom{n_k}{r_k} \ge \frac{1}{\sqrt{2k}\,t_k} \exp\left(-\frac{k}{12(t_k^2-1)}\right) \mathrm{e}^{-k/2} \,.\] Bounding the summation from below by this single term, the required condition is satisfied if \[\frac{1}{\sqrt{2k}\,t_k} \exp\left(-\frac{k}{12(t_k^2-1)}\right) \mathrm{e}^{-k/2} \ge \frac{1}{m_k} n_k \ln 2 \,.\] Substituting \(n_k = k t_k^2\), taking logarithms, and isolating \(\ln m_k\) we obtain \[\begin{align} \ln m_k & \ge \ln(k t_k^2 \ln 2) + \frac{1}{2}\ln(2k) + \ln t_k + \frac{k}{12(t_k^2-1)} + \frac{k}{2} \\ & = \frac{k}{2} + \frac{3}{2}\ln k + 3\ln t_k + \frac{k}{12(t_k^2-1)} + \frac{1}{2}\ln 2 + \ln(\ln 2) \,. \end{align}\] Multiplying by \(2\) establishes the stated bound. ◻

Proof. Fix \(k \ge 26\). The formulas \[t_k=\left\lceil\tilde{t}_k\right\rceil, \qquad m_k=\left\lceil\tilde{m}_k\right\rceil\] uniquely determine \(n_k\) and \(r_k\). It remains to verify admissibility.

Because \(\tilde{t}_k=\sqrt{k}/5\) and \(k\ge26\), we have \[2\le t_k\le\sqrt{k}\,.\] Note also that \(\tilde{m}_k>1\). By its defining equation and \(t_k\ge2\) we have \[2\ln\tilde{m}_k \ge k+3\ln k+\ln2+2\ln(\ln2)>0\] for \(k\ge26\).

We have \[\begin{align} \ln m_k & = \ln \lceil \tilde{m}_k \rceil \le \ln(\tilde{m}_k + 1) \le \ln(2\tilde{m}_k) = \ln \tilde{m}_k + \ln 2 \\ & < \frac{k}{2} + \frac{3}{2}\ln k + 3\ln t_k + \frac{k}{12(t_k^2-1)} + \ln 2 \\ & \le \frac{k}{2} + \frac{3}{2}\ln k + 3\ln t_k + \frac{k}{36} + \ln 2 \\ & \le \frac{k}{2} + \frac{3}{2}\ln k + 3\ln \sqrt{k} + \frac{k}{36} + \ln 2 \\ & = \frac{19}{36}k + 3\ln k + \ln 2 \\ & \le \frac{19}{36}k + k \\ & = \frac{55}{36}k < 4k\ln 2 \le k t_k^2 \ln 2 = n_k\ln 2\,. \end{align}\] This establishes \(m_k \le 2^{n_k}\), and hence the tuned constellation is admissible.

Also, \(m_k=\lceil\tilde{m}_k\rceil\ge\tilde{m}_k\), so \(\ln(m_k^2)\ge\ln(\tilde{m}_k^2)\). By the definition of \(\tilde{m}_k\), the hypothesis of Lemma 15 is satisfied, and the final statement follows from that lemma. ◻

Proof. Fix \(x > 4^{111}\) and define the index set \[\mathcal{I}_x = \{k \ge 26 \colon n_k m_k^2 \le x \} \,.\] Because the sequence \((n_k m_k^2)\) diverges to infinity, the set \(\mathcal{I}_x\) has finite cardinality. We now show that it is not empty.

At the index \(k = 120\), we have \(t_{120} = 3\), \(n_{120} = 1080\), and expanding the logarithm gives \[\begin{align} \ln(n_{120} m_{120}^2) & \le \ln(n_{120}(\tilde{m}_{120}+1)^2) \\ & = \ln(n_{120}\tilde{m}_{120}^2) + 2\ln\left(1 + \frac{1}{\tilde{m}_{120}}\right) \\ & < 150.4 + 0.6 < 151 < 222\ln 2 < \ln x \,. \end{align}\] Thus, \(120 \in \mathcal{I}_x\), so the set is non-empty.

Define \(k_x = \max \mathcal{I}_x\). The maximality of \(k_x \ge 120\) ensures \(k_x+1 \notin \mathcal{I}_x\), establishing the bounds \[n_{k_x} m_{k_x}^2 \le x < n_{k_x+1} m_{k_x+1}^2 \,,\] and completing the proof. ◻

Proof. Let \(y = \ln x\). By Lemma 17, we have \[\begin{align} y & \ge \ln(n_{k_x} m_{k_x}^2) \ge \ln(n_{k_x} \tilde{m}_{k_x}^2) \\ & = k_x + 4 \ln k_x + 8 \ln t_{k_x} + \frac{k_x}{6(t_{k_x}^2-1)} + \ln 2 + 2\ln(\ln 2) \\ & > k_x + 4 \ln k_x + 8 \ln t_{k_x} + \ln 2 + 2\ln(\ln 2) \,. \end{align}\] Substituting the lower bounds \(k_x \ge 120\) and \(t_{k_x} \ge 3\) establishes \(y > k_x + 27\). This verifies the strict inequality \[\label{eq:1kx} y > k_x + 1 \,.\tag{4}\]

Define \(K_x = k_x + 1\). By Lemma 17, we have \[\begin{align} y & \le \ln(n_{K_x} m_{K_x}^2) \le \ln(n_{K_x} \tilde{m}_{K_x}^2) + \frac{2}{\tilde{m}_{K_x}} \\ & < K_x + 4 \ln K_x + 8 \ln t_{K_x} + \frac{K_x}{6(t_{K_x}^2-1)} + \frac{2}{\tilde{m}_{K_x}} \,. \end{align}\] We bound the two tuning penalties. By definition, \[t_{K_x} \le \frac{\sqrt{K_x}}{5} + 1 = \frac{\sqrt{K_x}}{5}\left(1 + \frac{5}{\sqrt{K_x}}\right) \,.\] Combining this with the elementary inequality \(\ln(1+z) \le z\) for \(z > -1\) gives \[8 \ln t_{K_x} \le 4 \ln K_x - 8 \ln 5 + \frac{40}{\sqrt{K_x}} \,.\] Furthermore, the lower bound \(t_{K_x} \ge \frac{\sqrt{K_x}}{5}\) ensures \[\frac{K_x}{6(t_{K_x}^2-1)} \le \frac{25 K_x}{6(K_x-25)} = \frac{25}{6}\left(1 + \frac{25}{K_x-25}\right) \,.\]

For \(K_x\ge121\), the first four terms in the bracket are bounded below by their values at \(K_x=121\). Also \(\tilde{m}_{K_x}>1\), so \(2/\tilde{m}_{K_x}<2\). Direct calculation gives \[8\ln5-1-\frac{40}{11} -\frac{25}{6}\left(1+\frac{25}{96}\right) -2 > 0 \,.\] Substituting \(K_x = k_x + 1\) and evaluating the constants for \(K_x \ge 121\) gives \[\begin{align} y - k_x & \le 1 + 8 \ln K_x + \frac{40}{\sqrt{K_x}} - 8\ln 5 + \frac{25}{6}\left(1 + \frac{25}{K_x-25}\right) + \frac{2}{\tilde{m}_{K_x}} \\ & \le 8 \ln(k_x+1) - \left[ 8\ln 5 - 1 - \frac{40}{\sqrt{K_x}} - \frac{25}{6}\left(1 + \frac{25}{K_x-25}\right) - \frac{2}{\tilde{m}_{K_x}} \right] \\ & < 8\ln(k_x+1) \,. \end{align}\] Applying the logarithmic substitution \(\ln(k_x+1) < \ln y = \ln(\ln x)\) derived from 4 establishes the stated result. ◻

Proof of Theorem 2. For \(1 < x \le 4^{111}\) the bound holds by Lemma 11. We show the bound for \(x > 4^{111}\).

Fix \(x > 4^{111}\) and let \(y = \ln x\). By Lemmas 16 and 17, \[\sqrt{\log_4 x} - \sqrt{U_{\mathcal{M}}(x)} \le \frac{1}{\sqrt{2\ln 2}} \left( \frac{y - k_x}{\sqrt{y} + \sqrt{y - (y - k_x)}} \right) \,.\] The map \(u \mapsto \frac{u}{\sqrt{y} + \sqrt{y - u}}\) is strictly increasing for \(0 \le u < y\). By Lemma 18 and the condition \(y \ge 222\ln 2\), \[y - k_x < 8\ln y < y \,,\] so applying the monotonicity above, \[\begin{align} \frac{1}{\sqrt{2\ln 2}} \frac{y - k_x}{\sqrt{y} + \sqrt{y - (y - k_x)}} & < \frac{1}{\sqrt{2\ln 2}} \frac{8\ln y}{\sqrt{y} + \sqrt{y - 8\ln y}} \\ & = \frac{8\ln y}{\sqrt{y}} \left[ \sqrt{2\ln 2} \left( 1 + \sqrt{1 - \frac{8\ln y}{y}} \right) \right]^{-1} \,. \end{align}\] The function \(y \mapsto \frac{\ln y}{y}\) is strictly decreasing for \(y \ge \mathrm{e}\). For \(y > 222\ln 2\), the bracketed factor in the inverted expression exceeds \(2\). Therefore, \[\frac{1}{\sqrt{2\ln 2}} \frac{y - k_x}{\sqrt{y} + \sqrt{y - (y - k_x)}} < \frac{4\ln y}{\sqrt{y}} \,.\] Because \(\ln y < \ln(\mathrm{e} + y) = \ln(\mathrm{e} + \ln x)\), this establishes the bound stated in Theorem 2 for \(x > 4^{111}\). ◻

Proof. Because \(h(t)\) is a partition of unity, \(g_Z(t)\) is a finite convex combination of the variables \(f_Z(\lambda, \theta) \in [0,1]\). For any coordinate \(i\), the triangle inequality ensures the variation of the sum is bounded by the convex combination of the maximal variations, giving \[c_i(g) \le c_i(f(\lambda^\ast, \cdot))\,.\] Similarly, centring the function and applying the triangle inequality gives \[\sup_{t \in T} \left|g_Z(t) - \mathbb{E}\left[g_Z(t)\right]\right| \le \sup_{\theta \in \Theta} \left|f_Z(\lambda^\ast, \theta) - \mathbb{E}\left[f_Z(\lambda^\ast, \theta)\right]\right|\,.\] Equality in both inequalities follows from the second property of the partition of unity. For any \(\theta \in \Theta\), evaluating at \(t = \theta\) gives \(h_{(\lambda^\ast, \theta)}(\theta) = 1\) and \(h_{(\lambda', \theta')}(\theta) = 0\) for all other pairs \((\lambda', \theta')\). Thus, \(g_Z(\theta) = f_Z(\lambda^\ast, \theta)\). Because the supremum over \(T\) is bounded below by the supremum over the subset \(\Theta \subseteq T\), exact equality holds. ◻

Proof. Restricting the domain. Fix \(f_Z \in \mathcal{M}\) and let \(a > 0\). Let \(\psi \colon (1/4,3/4) \to \mathbb{R}\) be a strictly increasing surjective function. Define \[f^{(1)}(z,t) := \begin{cases} 0, & t \le 1/4 \,, \\[4pt] f\left(z,\psi(t)\right), & t\in(1/4,3/4)\,, \\[4pt] 1, & t \ge 3/4 \,. \end{cases}\] By Lemma 2, and because outside \((1/4,3/4)\) the function is constant, the randomised function \(f^{(1)}_Z\colon [0,1]\to [0,1]\) is equivalent to \(f_Z\). Padding the domain ensures that subsequent steps do not require boundary conditions at the endpoints.

Strictly increasing expectations. Define the affine scaling, \[f^{(2)}(z,t) := \frac{1}{1+a} f^{(1)}(z,t) + \frac{a}{1+a} t \,,\qquad t\in[0,1] \,.\] By Lemma 2, the function \(f^{(2)}_Z\) is equivalent to \(f^{(1)}_Z\), and \[(1+a)^{-2} \eta_{f^{(2)}} = \eta_{f^{(1)}} \,.\] Hence, \(\eta_{f^{(2)}} = (1+a)^2 \eta_f\). Because \(a>0\), the added linear drift ensures the mapping \(t \mapsto f^{(2)}(z,t)\) is strictly increasing for every \(z\). Consequently, the expected function \(\mathbb{E}\left[f^{(2)}_Z(t)\right]\) is strictly increasing. Strict monotonicity ensures that the generalised inverse below is regular.

Generalised inverse. For every \(\vartheta\in [0,1]\), define the inverse mapping \[t_\vartheta = \inf \left\{ t \in [0,1] \colon \vartheta \le \mathbb{E}\left[f^{(2)}_Z(t)\right] \right\} = \sup \left\{ t \in [0,1] \colon \mathbb{E}\left[f^{(2)}_Z(t)\right] \le \vartheta \right\} \,.\] Let \(\Theta \subseteq [0,1]\) be the set of values \(\theta\) satisfying \(\theta = \mathbb{E}\left[f^{(2)}_Z(t_\theta)\right]\). Notice that \(\theta\mapsto t_\theta\) maps \(\Theta\) onto \([0,1]\), thus in particular \(f^{(3)}_Z(\theta) := f^{(2)}_Z(t_\theta)\) is equivalent to \(f^{(2)}_Z\) with the same coefficient. Further, \(\mathbb{E}\left[f^{(3)}_Z(\theta)\right] = \theta\) for all \(\theta\in \Theta\).

Interpolation. If the expected path is discontinuous, then \(\Theta\) has gaps. We use interpolation to fill these gaps and extend the domain from \(\Theta\) to \([0,1]\).

Define the left- and right-continuous limits \(f_Z^{(2)\mathrm{L}}\) and \(f_Z^{(2)\mathrm{R}}\), respectively, of \(f_Z^{(2)}\), given by \[f_Z^{(2)\mathrm{L}}(z,x) := \lim_{y\uparrow x} f^{(2)}(z,y) \quad \text{and}\quad f_Z^{(2)\mathrm{R}}(z,x) := \lim_{y\downarrow x} f^{(2)}(z,y), \qquad \forall z\in \mathcal{Z},\;x\in[0,1].\] Because \(f^{(2)}_Z\) is deterministic on \(\{0,1\}\), \(f_Z^{(2)\mathrm{L}}\) and \(f_Z^{(2)\mathrm{R}}\) are equivalent with \(c_i(f^{(2)\mathrm{L}}) = c_i(f^{(2)\mathrm{R}})\) for all \(i\). Furthermore, because pointwise limits preserve non-strict inequalities, we trivially have for all \(i\): \[\begin{align} c_i(f^{(2)\mathrm{R}}) & \le c_i(f^{(2)}), \quad \text{and} \\ \sup_{x\in [0,1]}\left| f_Z^{(2)\mathrm{R}}(z,x)- \mathbb{E}\left[f^{(2)\mathrm{R}}_Z(x)\right]\right| & \le \sup_{x\in [0,1]}\left| f_Z^{(2)}(z,x)-\mathbb{E}\left[f_Z^{(2)}(x)\right]\right|, \quad \forall z\in \mathcal{Z}. \end{align}\] Identical bounds hold for \(f_Z^{(2)\mathrm{L}}\).

Because the expected limits bound \(\vartheta\), exactly one of the following mutually exclusive cases must hold for any \(\vartheta \in [0,1]\): \[\begin{align} \mathbb{E}\left[f^{(2)}_Z(t_\vartheta)\right] & < \vartheta \le \mathbb{E}\left[f^{(2)\mathrm{R}}_Z(t_\vartheta)\right],\\ \mathbb{E}\left[f^{(2)\mathrm{L}}_Z(t_\vartheta)\right] & \le \vartheta < \mathbb{E}\left[f^{(2)}_Z(t_\vartheta)\right],\\ \mathbb{E}\left[f^{(2)}_Z(t_\vartheta)\right] & = \vartheta . \end{align}\] Thus, there exists a unique weight vector \((\alpha_{\vartheta}, \alpha_{\mathrm{R} \vartheta}, \alpha_{\mathrm{L} \vartheta}) \in \mathbb{R}^3_+\) satisfying the simplex conditions: \[\alpha_{\vartheta}+ \alpha_{\mathrm{R} \vartheta}+ \alpha_{\mathrm{L} \vartheta}=1, \qquad \alpha_{\mathrm{L} \vartheta} \alpha_{\mathrm{R} \vartheta}=0,\] that interpolates the target expectation: \[\vartheta = \alpha_{\vartheta} \mathbb{E}\left[f^{(2)}_Z(t_\vartheta)\right] + \alpha_{\mathrm{R} \vartheta} \mathbb{E}\left[f^{(2)\mathrm{R}}_Z(t_\vartheta)\right] + \alpha_{\mathrm{L} \vartheta} \mathbb{E}\left[f^{(2)\mathrm{L}}_Z(t_\vartheta)\right] .\] Clearly \(\alpha_\vartheta=1\) if and only if \(\vartheta = \mathbb{E}\left[f^{(2)}_Z(t_\vartheta)\right]\). Also, in case (R), \(\alpha_{\mathrm{L} \vartheta}=0\); in case (L) \(\alpha_{\mathrm{R} \vartheta}=0\).

Define the target randomised function \(g_Z\) in \(\mathcal{M}_{\mathsf{id}}([0,1])\) via \[g(z,\vartheta) := \alpha_{\vartheta} f^{(2)}(z,t_\vartheta) + \alpha_{\mathrm{R} \vartheta} f^{(2)\mathrm{R}}(z,t_\vartheta) + \alpha_{\mathrm{L} \vartheta} f^{(2)\mathrm{L}}(z,t_\vartheta).\] By Lemma 33 of the Appendix, the map \(\vartheta \mapsto g(z, \vartheta)\) is non-decreasing for each \(z \in \mathcal{Z}\). Linearity of expectation implies \(\mathbb{E}\left[g_Z(\vartheta)\right] = \vartheta\) for all \(\vartheta \in [0,1]\), establishing \(g_Z \in \mathcal{M}_{\mathsf{id}}([0,1])\).

Applying Lemma 21, \(g_Z\) is equivalent to \(f^{(3)}_Z\). Because \(f^{(3)}_Z\) is equivalent to \(f^{(2)}_Z\), \[\eta_g = \eta_{f^{(2)}} = (1+a)^2 \eta_f\,.\] Equivalence is transitive; \(g_Z\) is equivalent to \(f_Z\). ◻

Proof of Theorem 3. By Lemma 22, \(U_{\mathcal{M}_{\mathsf{id}}}\) is well defined on the whole of \(\mathbb{R}_+\), because \(U_\mathcal{M}\) is well defined. Further, \[U_{\mathcal{M}_{\mathsf{id}}}(x) \le U_{\mathcal{M}}(x) \le U_{\mathcal{M}_{\mathsf{id}}}\big((1+a)^2 x\big)\,,\] for any \(x\ge 0\) and any \(a>0\). Because \(a\) is arbitrary, \(U_{\mathcal{M}_{\mathsf{id}}}\) is monotone and its right-continuous version equals the right-continuous version of \(U_{\mathcal{M}}\). ◻

Proof. Assume \(m := r \sup_{t\in[0,1]} |f(t)-t| > 0\); the case \(m=0\) is trivial. By definition either \(\sup_t (f(t)-t)^+ = m/r\) or \(\sup_t (f(t)-t)^- = m/r\); consider the former, the latter being symmetric. By Lemma 23 there is \(t^\ast\) with \(t^\ast+\alpha\in[0,1]\) for \(0\le\alpha\le m/r\) and \[r\bigl(f(t)-t\bigr)\;\ge\; m-r\,(t-t^\ast), \qquad t\in[t^\ast,\,t^\ast+m/r] \,.\] Fix \(H\in\mathcal{H}\) with gauge \(h=H'\ge 0\) strictly increasing. Restricting the integral to this interval and using monotonicity of \(h\), \[\begin{align} r\int_0^1 h\!\left(r|f(t)-t|\right)\mathrm{d}t & \ge r\int_{t^\ast}^{t^\ast+m/r} h\!\bigl(m-r(t-t^\ast)\bigr)\mathrm{d}t \\ & = \int_0^m h(s)\,\mathrm{d}s = H(m) \,, \end{align}\] by the substitution \(s=m-r(t-t^\ast)\). Because \(H^{-1}\) is increasing, \[H^{-1}\!\left(r\int_0^1 h\!\left(r|f(t)-t|\right)\mathrm{d}t\right)\ge m \,.\] As \(H\in\mathcal{H}\) was arbitrary, the infimum is \(\ge m\). ◻

Proof. Fix a realisation \(z\). We have \(f_z\colon[0,1]\to[0,1]\) is deterministic and non-decreasing, so Corollary 2 applies with \(r=\sqrt{\eta_f}\) and \(f=f_z\). ◻

Proof. Set \(r := \sqrt{\eta_f}\) and define the random variable \(X_t := r|f_Z(t)-t|\) for \(t\in[0,1]\), with realisation \(X_t(z) = r|f_z(t)-t|\). By McDiarmid’s inequality, \(\mathbb{P}\{X_t \ge \varepsilon\} \le 2\mathrm{e}^{-2\varepsilon^2}\) for all \(\varepsilon>0\). By Corollary 3, for each realisation \(z\) and any \(H \in \mathcal{H}_0\), \[\sup_{t\in[0,1]}X_t(z) \le H^{-1}\left( r\int_0^1 h(X_t(z))\,\mathrm{d}t \right) \,.\] Taking expectations (the left side being independent of \(H\)), then applying Jensen’s inequality to the strictly concave \(H^{-1}\) and Tonelli’s theorem to the inner integral, we have \[\begin{align} \mathbb{E}\left[\sup_{t\in[0,1]}X_t\right] & \le \inf_{H\in\mathcal{H}_0} \mathbb{E}\left[ H^{-1}\left( r\int_0^1 h(X_t)\,\mathrm{d}t \right)\right] \\ & \le \inf_{H\in\mathcal{H}_0} H^{-1}\left( r\int_0^1 \mathbb{E}\left[h(X_t)\right]\,\mathrm{d}t \right) \,. \end{align}\] For fixed \(t\), the layer-cake representation with respect to the Lebesgue–Stieltjes measure \(\mathrm{d}h\) provides \[\mathbb{E}\left[h(X_t)\right] = h(0)+\int_0^\infty \mathbb{P}\{X_t\ge \varepsilon\}\,\mathrm{d} h(\varepsilon) \le h(0)+\int_0^\infty 2\mathrm{e}^{-2\varepsilon^2}\,\mathrm{d} h(\varepsilon) \,.\] By integration by parts, \[\begin{align} \int_0^\infty 2\mathrm{e}^{-2\varepsilon^2}\,\mathrm{d}h(\varepsilon) & = \left[2h(\varepsilon)\mathrm{e}^{-2\varepsilon^2}\right]_{0}^{\infty} - \int_0^\infty h(\varepsilon)\,\mathrm{d}\left(2\mathrm{e}^{-2\varepsilon^2}\right) \\ & = -2h(0) + \int_0^\infty 8\varepsilon\,h(\varepsilon)\mathrm{e}^{-2\varepsilon^2}\,\mathrm{d}\varepsilon \,. \end{align}\] Because \(H \in \mathcal{H}_0\), the upper boundary term is zero. Combining the residual terms, \(h(0) - 2h(0) = -h(0) \le 0\). Upper-bounding this non-positive term by zero, we have \[\mathbb{E}\left[h(X_t)\right] \le \int_0^\infty 8\varepsilon\,h(\varepsilon)\mathrm{e}^{-2\varepsilon^2}\,\mathrm{d}\varepsilon \,,\] uniformly in \(t\). Substituting this bound back into the integral inside \(H^{-1}\) completes the proof. ◻

Proof. Fix \(f_Z\in\mathcal{M}_{\mathsf{id}}\) and set \(x=\eta_f\). We establish that for all \(\varepsilon>0\), \[\mathbb{P}\left\{ \sqrt{\eta_f}\sup_{t\in[0,1]}|f_Z(t)-t| \ge \varepsilon\mathcal{E}(\eta_f) \right\} \le 2\mathrm{e}^{-2\varepsilon^2}.\] If \(\varepsilon\le \sqrt{(\ln 2)/2}\), then \(2\mathrm{e}^{-2\varepsilon^2}\ge 1\), and the inequality holds trivially. Assume \(\varepsilon>\sqrt{(\ln 2)/2}\) and set \(a := \sqrt{(\ln 2)/2}\). The \(\ell_2\)-norm identities are \[\mathcal{E}(\eta_f) = \left\| \left(1, \frac{\beta(\eta_f)}{a}\right) \right\|_2 \,, \qquad \varepsilon = \left\| \left(\sqrt{\varepsilon^2-a^2}, a\right) \right\|_2 \,.\] By the Cauchy–Schwarz inequality, \[\begin{align} \varepsilon\mathcal{E}(\eta_f) & \ge \left\langle \left(\sqrt{\varepsilon^2-a^2}, a\right), \left(1, \frac{\beta(\eta_f)}{a}\right) \right\rangle \\ & = \sqrt{\varepsilon^2-a^2} + \beta(\eta_f) \,. \end{align}\] Define the maximal deviation \[S(Z) := \sup_{t\in[0,1]}|f_Z(t)-t| \,.\] Applying Corollary 6 with the deterministic shift \(g(t) = t\) provides the centred upper tail concentration \[\mathbb{P}\left\{ \sqrt{\eta_f}\left( S(Z) - \mathbb{E}\left[S(Z)\right] \right) \ge v \right\} \le \mathrm{e}^{-2v^2}, \qquad v>0.\] Substituting the expectation bound \(\sqrt{\eta_f}\mathbb{E}\left[S(Z)\right] \le \beta(\eta_f)\) of Lemma 24, we have \[\mathbb{P}\left\{ \sqrt{\eta_f}S(Z) \ge \beta(\eta_f)+v \right\} \le \mathrm{e}^{-2v^2}, \qquad v>0.\] Evaluating at \(v = \sqrt{\varepsilon^2-a^2}\), \[\begin{align} \mathbb{P}\left\{ \sqrt{\eta_f}S(Z) \ge \varepsilon\mathcal{E}(\eta_f) \right\} & \le \mathbb{P}\left\{ \sqrt{\eta_f}S(Z) \ge \beta(\eta_f)+\sqrt{\varepsilon^2-a^2} \right\} \\ & \le \mathrm{e}^{-2(\varepsilon^2-a^2)} = \mathrm{e}^{-2\varepsilon^2} \mathrm{e}^{2a^2} = 2\mathrm{e}^{-2\varepsilon^2}, \end{align}\] where \(\mathrm{e}^{2a^2}=\mathrm{e}^{\ln2}=2\). Hence \(\mathcal{E}(x)^2\) is admissible, in the sense defined in Section 2, for every \(f_Z\in\mathcal{M}_{\mathsf{id}}\) with \(\eta_f=x\), so \(\mathcal{E}(x)^2\ge u_{f_Z}\); taking the supremum, \(\sqrt{U_{\mathcal{M}_{\mathsf{id}}}(x)}\le\mathcal{E}(x)\). ◻

Proof. We upper-bound the infimum in the definition of \(\beta(x)\) by evaluating the exact integral for the specific gauge \(h_p(\varepsilon) = p \mathrm{e}^{p\varepsilon}\): \[I_p := \int_0^\infty 8\varepsilon\, h_p(\varepsilon) \mathrm{e}^{-2\varepsilon^2} \,\mathrm{d}\varepsilon = \int_0^\infty 8\varepsilon p \mathrm{e}^{p\varepsilon - 2\varepsilon^2} \,\mathrm{d}\varepsilon \,.\] To evaluate this, we apply integration by parts. Let \(u = 2p \mathrm{e}^{p\varepsilon}\) and \(\mathrm{d} v = 4\varepsilon \mathrm{e}^{-2\varepsilon^2}\,\mathrm{d}\varepsilon\), which integrates to \(v = -\mathrm{e}^{-2\varepsilon^2}\). This implies: \[\begin{align} I_p & = \left[ -2p \mathrm{e}^{p\varepsilon - 2\varepsilon^2} \right]_0^\infty - \int_0^\infty \left(2p^2 \mathrm{e}^{p\varepsilon}\right) \left(-\mathrm{e}^{-2\varepsilon^2}\right) \,\mathrm{d}\varepsilon \\ & = 2p + 2p^2 \int_0^\infty \mathrm{e}^{p\varepsilon - 2\varepsilon^2} \,\mathrm{d}\varepsilon \,. \end{align}\] We isolate the Gaussian core by completing the square in the exponent: \(-2\varepsilon^2 + p\varepsilon = -2\left(\varepsilon - \frac{p}{4}\right)^2 + \frac{p^2}{8}\). Substituting this back into the integral and factoring out the exponential, we have \[I_p = 2p + 2p^2 \mathrm{e}^{p^2/8} \int_0^\infty \mathrm{e}^{-2(\varepsilon - p/4)^2} \,\mathrm{d}\varepsilon \,.\] We upper-bound the remaining shifted Gaussian integral by extending its lower limit to \(-\infty\), which evaluates exactly to \(\sqrt{\pi/2}\). Substituting this, we have \[I_p \le 2p + 2p^2 \sqrt{\frac{\pi}{2}} \mathrm{e}^{p^2/8} = 2p + p^2\sqrt{2\pi} \, \mathrm{e}^{p^2/8} \,.\] Because \(\beta(x)\) is defined as an infimum, it is bounded by the evaluation at \(H_p\), so that \(\beta(x) \le H_p^{-1}(\sqrt{x} I_p) = \frac{1}{p} \ln(1 + \sqrt{x} I_p)\).

The “in particular” claim follows because \(\sqrt{U_{\mathcal{M}_{\mathsf{id}}}(x)}\le\mathcal{E}(x)\le\mathcal{E}(x,p)\) by Lemma 25, and the uniformisation Theorem 3 transports the bound to \(U_{\mathcal{M}}\), the envelope \(\mathcal{E}(\cdot,p)\) being continuous. ◻

Proof. Write \(y=\ln x\), so \(\sqrt{\log_4 x}=\sqrt{y/(2\ln2)}\). Subtracting this leading term from 5 , we have \[\sqrt{U_{\mathcal{M}}(e^y)}-\sqrt{\tfrac{y}{2\ln2}} \le \sqrt{\tfrac{y}{2\ln2}} \left[\sqrt{(1+\Lambda(y))^2+\tfrac{2\ln2}{y}}-1\right],\] which by Lemma 27 is at most \(2\ln(\mathrm{e}+y)/\sqrt{y}\) for \(y\ge y_0\). ◻

Proof. By 6 , \[\sqrt{U_{\mathcal{M}}(x)}-\sqrt{\log_4 x} \le \mathcal{E}(x,5)-\sqrt{\log_4 x}=:S(x) \,.\] Because \(\mathcal{E}(x,5)\ge\sqrt{\tfrac{2}{\ln2}}\,\psi(x,5)\), on \(2.5\le x<\mathrm{e}^{y_0}\) \[\frac{\mathrm d}{\mathrm dx}\,\mathcal{E}(x,5) = \frac{(2/\ln2)\,\psi(x,5)\,\psi'(x)}{\mathcal{E}(x,5)} \le \sqrt{\tfrac{2}{\ln2}}\,\psi'(x) < \frac{\mathrm d}{\mathrm dx}\sqrt{\log_4 x}\,,\] so \(S\) is decreasing and attains its maximum at \(x=2.5\): \[S(2.5)=\mathcal{E}(2.5,5)-\sqrt{\log_4 2.5}=1.9966\ldots<2 \,.\] This establishes the result. ◻

Proof. By the trivial bound of Lemma 4, \(\sqrt{U_{\mathcal{M}}(x)}-\sqrt{\log_4 x}\le T(x):= \sqrt{\tfrac{2}{\ln2}\,x}-\sqrt{\log_4 x}\). A direct verification provides \(T(x)\le T(2.5)=1.8728\ldots<2\) on \([1,2.5]\). ◻

Proof of Theorem 4. Put \(y=\ln x\), so that \(\sqrt{\log_4 x}=\sqrt{y/(2\ln2)}\), and let \(x_0=\mathrm e^{y_0}\). Because the right-hand side of the asserted bound is nonnegative, it suffices to show \[\sqrt{U_{\mathcal{M}}(x)}-\sqrt{\log_4 x} \le 2\min\!\left\{1,\frac{\ln(\mathrm{e}+y)}{\sqrt{y}}\right\}\] for all \(x>1\); the positive part then follows at once. The function \(g(y):=\ln(\mathrm{e}+y)/\sqrt{y}\) is strictly decreasing on \((0,\infty)\), because \(g'(y)<0\) is equivalent to the elementary inequality \(2y/(\mathrm{e}+y)<\ln(\mathrm{e}+y)\); and \(g(y_0)=1\), so \(g\le1\) for \(y\ge y_0\) and \(g\ge1\) for \(0<y\le y_0\). Hence \[2\min\!\left\{1,\frac{\ln(\mathrm{e}+y)}{\sqrt{y}}\right\} =\begin{cases} \dfrac{2\ln(\mathrm{e}+y)}{\sqrt{y}}, & y\ge y_0 \quad(x\ge x_0), \\[8pt] 2, & 0<y< y_0 \quad(1<x<x_0). \end{cases}\] Case \(x\ge x_0\). By Corollary 4, \[\sqrt{U_{\mathcal{M}}(x)}-\sqrt{\log_4 x} \le \frac{2\ln(\mathrm{e}+\ln x)}{\sqrt{\ln x}} = 2\min\!\left\{1,\frac{\ln(\mathrm{e}+y)}{\sqrt{y}}\right\}.\] Case \(1<x<x_0\). Here the right-hand side is \(2\). The ranges \([1,2.5)\) and \([2.5,x_0)\) partition \((1,x_0)\): on \([1,2.5)\), Lemma 29 provides \(\sqrt{U_{\mathcal{M}}(x)}-\sqrt{\log_4 x}<2\), and on \([2.5,x_0)\), Lemma 28 provides the same bound. Thus \(\sqrt{U_{\mathcal{M}}(x)}-\sqrt{\log_4 x}<2\) throughout \((1,x_0)\). Combining the two cases proves the bound for every \(x>1\). ◻

Proof. The bound \(|X_Z(t)| \le 1\) holds by the normalisation \(\sum_{j=1}^m |\psi_j(t)| = 1\), and the local-derivative bound \(\kappa(t) := \sum_{j=1}^m |\psi'_j(t)|\) satisfies \(|X'_Z(t)| \le \kappa(t)\) for every realisation. The drifted process \[Y_Z(t) := X_Z(t) + \mathrm{Arc}_{\ell_1}(t) + 1\] has derivative \(Y'_Z(t) = X'_Z(t) + \kappa(t) \ge 0\), so for every realisation \(Z = z\) the path \(Y_z\) is non-decreasing in \(t\), and \(Y_Z(t) \in [0,\, 2 + \mathrm{Arc}_{\ell_1}]\). Normalise to define \[f_Z(t) := \frac{Y_Z(t)}{2 + \mathrm{Arc}_{\ell_1}} \,,\] giving \(f_Z \in \mathcal{M}\). Applying Lemma 2 twice — first with \(a = 1\) and deterministic shift \(h(t) = \mathrm{Arc}_{\ell_1}(t) + 1\), then with \(a = (2 + \mathrm{Arc}_{\ell_1})^{-1}\) and \(h \equiv 0\) — shows that \(f_Z\) is equivalent to \(X_Z\) with \(\eta_{f_Z} = (2 + \mathrm{Arc}_{\ell_1})^2 \eta_X>1\), so Theorem 4 applied to \(f_Z\) gives the result. ◻

Proof. For a constellation, by definition, we have \(k,t_k\in\mathbb{N}\) with \(t_k\ge2\), and \[n_k := k\,t_k^2, \qquad r_k := \frac{k\,t_k(t_k-1)}{2}\,.\] Because \(t_k\) and \(t_k-1\) are consecutive integers, their product \(t_k(t_k-1)\) is an even integer, ensuring that \(r_k\ge 1\) is an integer. We also clearly have that \(n_k\ge 4\) is an integer. Set \[\lambda_k := \frac{r_k}{n_k} = \frac{k\,t_k(t_k-1)}{2k\,t_k^2}= \frac{t_k-1}{2t_k} = \frac{1}{2} - \frac{1}{2t_k}\,.\] Note that \(1/4\le\lambda_k <1/2\), because \(t_k\ge 2\). Thus, we apply the lower bound of 9 : \[\binom{n_k}{r_k}= \binom{n_k}{\lambda_k n_k} \ge \frac{1}{\sqrt{8n_k\lambda_k(1-\lambda_k)}}\, 2^{n_k \mathcal{H}_2(\lambda_k)} \,.\]

Dividing by \(2^{n_k}\) gives \[\label{eq:brackterm} \frac{1}{2^{n_k}}\binom{n_k}{r_k} \ge \frac{1}{\sqrt{8n_k\lambda_k(1-\lambda_k)}} \, \left[2^{-n_k(1-\mathcal{H}_2(\lambda_k))}\right] \,.\tag{11}\]

Now \[\lambda_k(1-\lambda_k) = \left(\frac{1}{2}-\frac{1}{2t_k}\right) \left(\frac{1}{2}+\frac{1}{2t_k}\right) = \frac{1}{4}-\frac{1}{4t_k^2} \le \frac{1}{4} \,,\] and therefore \[\label{eq:firstest} \frac{1}{\sqrt{8n_k\lambda_k(1-\lambda_k)}} \ge \frac{1}{\sqrt{2n_k}} = \frac{1}{\sqrt{2k}\,t_k} \,.\tag{12}\]

It remains to bound the bracketed term in 11 . Writing \(\delta:=\frac{1}{2t_k}\) and noting that \(0<\delta \le 1/4\), we have \[\lambda_k = \frac{1}{2} - \delta\,.\] By the exact Taylor expansion in 10 , we have \[1-\mathcal{H}_2\left(\frac{1}{2}-\delta\right) = \frac{1}{\ln 2} \sum_{j=1}^{\infty} \frac{(2\delta)^{2j}}{2j(2j-1)}\,.\] Because \(2\delta=1/t_k\), this becomes \[1-\mathcal{H}_2(\lambda_k) = \frac{1}{\ln 2} \sum_{j=1}^{\infty} \frac{t_k^{-2j}}{2j(2j-1)} \,.\] Separating the first term and bounding the remainder by a geometric series, \[\begin{align} 1-\mathcal{H}_2(\lambda_k) & \le \frac{1}{\ln 2} \left[ \frac{1}{2t_k^2} + \frac{1}{12}\sum_{j=2}^{\infty}t_k^{-2j} \right] \\ & = \frac{1}{\ln 2} \left[ \frac{1}{2t_k^2} + \frac{1}{12t_k^4}\sum_{m=0}^{\infty}t_k^{-2m} \right] \,. \end{align}\] Hence \[1-\mathcal{H}_2(\lambda_k) \le \frac{1}{\ln 2} \left[ \frac{1}{2t_k^2} + \frac{1}{12t_k^2(t_k^2-1)} \right] \,,\] and multiplying by \(n_k\ln 2=k\,t_k^2\ln 2\) gives \[n_k(1-\mathcal{H}_2(\lambda_k))\ln 2 \le k\,t_k^2\left(\frac{1}{2t_k^2} + \frac{1}{12t_k^2(t_k^2-1)}\right) = \frac{k}{2} + \frac{k}{12(t_k^2-1)} \,.\] Thus \[\begin{align} 2^{-n_k(1-\mathcal{H}_2(\lambda_k))} & = \exp\left(-n_k(1-\mathcal{H}_2(\lambda_k))\ln 2\right) \\ & \ge \exp\left(-\frac{k}{2}-\frac{k}{12(t_k^2-1)}\right) = \exp\left(-\frac{k}{12(t_k^2-1)}\right)\mathrm{e}^{-k/2} \,. \end{align}\]

Substituting this and 12 into 11 , we obtain \[\frac{1}{2^{n_k}}\binom{n_k}{r_k} \ge \frac{1}{\sqrt{2k}\,t_k} \exp\left(-\frac{k}{12(t_k^2-1)}\right) \mathrm{e}^{-k/2} \,.\] This proves the claim. ◻

Proof. Let \(\vartheta_1 < \vartheta_2\). Because the expectation \(\mathbb{E}\left[f^{(2)}_Z(t)\right]\) is strictly increasing, the generalised inverse gives \(t_{\vartheta_1} \le t_{\vartheta_2}\). Two cases arise:

• If \(t_{\vartheta_1} < t_{\vartheta_2}\), the monotonicity of \(t \mapsto f^{(2)}(z,t)\) bounds the maximum possible interpolated value at \(t_{\vartheta_1}\) by the minimum possible interpolated value at \(t_{\vartheta_2}\). Thus, \[g(z, \vartheta_1) \le f^{(2)\mathrm{R}}(z, t_{\vartheta_1}) \le f^{(2)\mathrm{L}}(z, t_{\vartheta_2}) \le g(z, \vartheta_2) \,.\]

• If \(t_{\vartheta_1} = t_{\vartheta_2} = t^\ast\), the interpolation occurs across a single vertical jump. Because \(\vartheta_1 < \vartheta_2\), the unique interpolation weights for \(\vartheta_2\) shift mass from the left limit \(f^{(2)\mathrm{L}}(z, t^\ast)\) towards the evaluation \(f^{(2)}(z, t^\ast)\) and the right limit \(f^{(2)\mathrm{R}}(z, t^\ast)\). The pointwise ordering \(f^{(2)\mathrm{L}}(z, t^\ast) \le f^{(2)}(z, t^\ast) \le f^{(2)\mathrm{R}}(z, t^\ast)\) ensures this rightward weight shift gives \(g(z, \vartheta_1) \le g(z, \vartheta_2)\).

Thus, \(g_Z\) is non-decreasing. ◻

Proof. For each coordinate \(i\), \[c_i(\overline{f^+}) \le c_i(f), \qquad c_i(\overline{f^-}) \le c_i(f), \qquad c_i(\overline{|f|}) \le c_i(f)\,,\] and the result follows. ◻

Proof. Write \(g(z,\theta) = f(z,\theta) - h(\theta)\). Because \(h\) is deterministic, \(c_i(g) = c_i(f)\) for all \(i\), so \(\eta_g = \eta_f\); and \(S = \overline{|g|}\), so Lemma 34 gives \(\eta_S \ge \eta_g = \eta_f\). If \(\eta_S = \infty\), then \(S(Z) = \mathbb{E}\left[S(Z)\right]\) surely and the bound holds. Otherwise \(\infty > \eta_S \ge \eta_f > 0\), and for all \(\varepsilon > 0\) McDiarmid’s inequality gives \[\mathbb{P}\left\{ S(Z) - \mathbb{E}\left[S(Z)\right] \ge \varepsilon \right\} \le \mathrm{e}^{-2\varepsilon^2\eta_S} \le \mathrm{e}^{-2\varepsilon^2\eta_f}\,.\] With \(\varepsilon/\sqrt{\eta_f}\) in place of \(\varepsilon\), the bound follows. ◻

Proof of Lemma 23. Positive deviation. Let \(S := \sup_{t\in[0,1]} (f(t)-t)^+ \ge \varepsilon\). Choose a sequence \((t_n) \subset [0,1]\) such that \(f(t_n)-t_n \to S\). By compactness, passing to a subsequence if necessary, assume \(t_n \to t^\ast \in [0,1]\). Because \(f \le 1\), \(t_n \le 1 - (f(t_n) - t_n)\). Taking limits gives \(t^\ast \le 1 - S \le 1 - \varepsilon\). Thus, \(t^\ast + \alpha \in [0,1]\) for all \(\alpha \in [0, \varepsilon]\).

Fix \(\alpha \in [0, \varepsilon]\). For sufficiently large \(n\), \(t_n \le t^\ast + \alpha\). Monotonicity of \(f\) implies \(f(t^\ast + \alpha) \ge f(t_n)\). Thus, \[\begin{align} f(t^\ast + \alpha) - (t^\ast + \alpha) & \ge f(t_n) - t^\ast - \alpha \\ & = (f(t_n) - t_n) + t_n - t^\ast - \alpha \,. \end{align}\] Letting \(n \to \infty\) gives us \(f(t^\ast + \alpha) - (t^\ast + \alpha) \ge S - \alpha \ge \varepsilon - \alpha \ge 0\).

Negative deviation. Let \(S := \sup_{t\in[0,1]} (t-f(t))^+ \ge \varepsilon\). Choose \((t_n) \subset [0,1]\) such that \(t_n - f(t_n) \to S\), and assume \(t_n \to t^\ast \in [0,1]\). Because \(f \ge 0\), \(t_n \ge t_n - f(t_n)\), giving \(t^\ast \ge S \ge \varepsilon\). Thus, \(t^\ast - \alpha \in [0,1]\) for all \(\alpha \in [0, \varepsilon]\).

Fix \(\alpha \in [0, \varepsilon]\). For large \(n\), \(t_n \ge t^\ast - \alpha\). Monotonicity of \(f\) gives \(f(t^\ast - \alpha) \le f(t_n)\), and therefore \[\begin{align} (t^\ast - \alpha) - f(t^\ast - \alpha) & \ge t^\ast - \alpha - f(t_n) \\ & = (t_n - f(t_n)) + t^\ast - t_n - \alpha \,. \end{align}\] Letting \(n \to \infty\) gives us \((t^\ast - \alpha) - f(t^\ast - \alpha) \ge S - \alpha \ge \varepsilon - \alpha \ge 0\). ◻

Proof of Lemma 27. Write \(c:=2\ln2\), and set \[\Phi(y):=\ln\left( 4\sqrt{2\pi}\,y+4\sqrt{y}\,\mathrm{e}^{-y/2} +\mathrm{e}^{-y} \right), \qquad \Lambda(y)=\frac{\Phi(y)}{y} \,.\] Recall that \(y_0\) solves \[\ln(\mathrm{e}+y)=\sqrt{y} \,.\] Numerically, \(y_0=3.102884\ldots\), so \(y_0>3\).

Reduction by squaring. Multiplying the claimed bound by \(\sqrt{c/y}>0\) and isolating the square root, it is equivalent to \[\sqrt{\left(1+\frac{\Phi(y)}{y}\right)^2+\frac{c}{y}} \le 1+\frac{2\sqrt{c}\,\ln(\mathrm{e}+y)}{y} \,.\] Both sides are positive. Squaring and multiplying by \(y^2\), the equivalent inequality is \[2y\Phi(y)+\Phi(y)^2+cy \le 4\sqrt{c}\,y\ln(\mathrm{e}+y) +4c\,\ln(\mathrm{e}+y)^2 \,.\]

Majorising \(\Phi\). The function \[y\mapsto 4\sqrt{y}\,\mathrm{e}^{-y/2}+\mathrm{e}^{-y}\] is decreasing for \(y\ge1\). Hence, for \(y\ge3\), \[4\sqrt{y}\,\mathrm{e}^{-y/2}+\mathrm{e}^{-y} \le 4\sqrt{3}\,\mathrm{e}^{-3/2}+\mathrm{e}^{-3} \le (11-4\sqrt{2\pi})\,3 \,.\] Because \(y\ge y_0>3\), we have \[4\sqrt{2\pi}\,y +4\sqrt{y}\,\mathrm{e}^{-y/2} +\mathrm{e}^{-y} \le 11y \,.\] Therefore \[0<\Phi(y)\le \ln(11y), \qquad y\ge y_0 \,.\] Because the map \(\xi\mapsto2y\xi+\xi^2\) is increasing on \(\xi\ge0\), it is enough to prove \[2y\ln(11y)+\ln(11y)^2+cy \le 4\sqrt c\,y\ln(\mathrm{e}+y) +4c\,\ln(\mathrm{e}+y)^2 \,.\] Define \[\Psi(y) := 4\sqrt c\,y\ln(\mathrm{e}+y) +4c\,\ln(\mathrm{e}+y)^2 -2y\ln(11y)-\ln(11y)^2-cy \,.\] We prove that \(\Psi(y)\ge0\) for \(y\ge y_0\).

Convexity of \(\Psi\). Differentiating, \[\Psi'(y) = 4\sqrt c\left(\ln(\mathrm{e}+y)+\frac{y}{\mathrm{e}+y}\right) +\frac{8c\ln(\mathrm{e}+y)}{\mathrm{e}+y} -2\ln(11y)-2-\frac{2\ln(11y)}{y}-c\] and \[\Psi''(y) = \frac{4\sqrt{c}}{\mathrm{e}+y} +\frac{4\sqrt c\,\mathrm{e}}{(\mathrm{e}+y)^2} +\frac{8c(1-\ln(\mathrm{e}+y))}{(\mathrm{e}+y)^2} -\frac{2}{y} +\frac{2(\ln(11y)-1)}{y^2} \,.\] We show that \(\Psi''(y)\ge0\) for \(y\ge y_0\).

The only negative terms in \(\Psi''\) are \(-2/y\) and the negative part of the term containing \(1-\ln(\mathrm{e}+y)\). We use \[\frac{8c(\ln(\mathrm{e}+y)-1)}{(\mathrm{e}+y)^2} \le \frac{4c}{\mathrm{e}^3} \,,\] because \[\max_{u>0}\frac{\ln(u)-1}{u^2}=\frac{1}{2\mathrm{e}^3} \,.\]

The tail (\(y\ge6\)). For \(y\ge 6\), discard the nonnegative terms \[\frac{4\sqrt c\,\mathrm{e}}{(\mathrm{e}+y)^2}, \qquad \frac{2(\ln(11y)-1)}{y^2}\] from \(\Psi''\). After multiplying by \((\mathrm{e}+y)^2\), it is enough to prove \[\left( \frac{4\sqrt c}{\mathrm{e}+y}-\frac{2}{y} \right)(\mathrm{e}+y)^2 -8c(\ln(\mathrm{e}+y)-1) \ge0 \,.\] The first term equals \[(4\sqrt c-2)y +(4\sqrt c-4)\mathrm{e} -\frac{2\mathrm{e}^2}{y} \,.\] For \(y\ge6\), \[\frac{2\mathrm{e}^2}{y}\le\frac{\mathrm{e}^2}{3} \,.\] Thus, it is enough to prove \(\Xi(y)\ge0\), where \[\Xi(y) := (4\sqrt c-2)y +(4\sqrt c-4)\mathrm{e} -\frac{\mathrm{e}^2}{3} -8c(\ln(\mathrm{e}+y)-1) \,.\] But \[\Xi'(y) = (4\sqrt c-2)-\frac{8c}{\mathrm{e}+y}>0, \qquad y\ge6 \,,\] and \[\Xi(6)>2.79 \,.\] Hence \(\Psi''(y)\ge0\) for \(y\ge6\).

The bounded range (\(y_0\le y\le6\)). Using the global bound above in the formula for \(\Psi''\), we have \[\Psi''(y) \ge \frac{4\sqrt c}{\mathrm{e}+y} +\frac{4\sqrt c\,\mathrm{e}}{(\mathrm{e}+y)^2} +\frac{2(\ln(11y)-1)}{y^2} -\frac{2}{y}-\frac{4c}{\mathrm{e}^3} \,.\] The function \[y\mapsto\frac{\ln(11y)-1}{y^2}\] is decreasing on \([y_0,\infty)\), because \[\frac{\mathrm d}{\mathrm dy} \left(\frac{\ln(11y)-1}{y^2}\right) = \frac{3-2\ln(11y)}{y^3}<0 \,.\] Hence, on \([y_0,4]\), \[\Psi''(y) \ge \frac{4\sqrt c}{4+\mathrm{e}} +\frac{4\sqrt c\,\mathrm{e}}{(4+\mathrm{e})^2} +\frac{2(\ln44-1)}{16} -\frac{2}{y_0} -\frac{4c}{\mathrm{e}^3} >0 \,.\] Similarly, on \([4,6]\), \[\Psi''(y) \ge \frac{4\sqrt c}{6+\mathrm{e}} +\frac{4\sqrt c\,\mathrm{e}}{(6+\mathrm{e})^2} +\frac{2(\ln44-1)}{36} -\frac{1}{2} -\frac{4c}{\mathrm{e}^3} >0 \,.\] Therefore \(\Psi''(y)\ge0\) for all \(y\ge y_0\).

Because \[\Psi'(y_0)=1.440209\ldots>0\] and \[\Psi(y_0)=4.275887\ldots>0 \,,\] the function \(\Psi\) is increasing and positive on \([y_0,\infty)\). This proves the majorised inequality, hence the squared inequality, and therefore the scalar envelope bound. ◻