==== TABLE OF CONTENTS ==== A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction//main.tex A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction//part-1.tex A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction//summary.tex =========================== ==== BEGIN A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction//main.tex ==== \documentclass{article} \usepackage{pdfpages} \usepackage[unicode,hidelinks]{hyperref} \hypersetup{pdftitle={A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction},pdfauthor={OpenAI},pdfsubject={Stated improvement; optimal complexity open}} \pagestyle{empty} \begin{document} \includepdf[pages=-,pagecommand={},addtotoc={1,section,1,{Summary},s-summary}]{summary.pdf} \includepdf[pages=-,pagecommand={},addtotoc={1,section,1,{Report},s-part-1}]{part-1.pdf} \end{document} ==== END A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction//main.tex ==== ==== BEGIN A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction//part-1.tex ==== \documentclass[11pt]{article} \usepackage{amsmath,amssymb,amsthm} \usepackage[margin=1in]{geometry} \usepackage[hidelinks]{hyperref} \newtheorem{thm}{Theorem} \title{A latest-anchor induction with spectrally compact masks\\for worst-case trace reconstruction} \author{OpenAI} \date{} \emergencystretch=3em \allowdisplaybreaks \begin{document} \maketitle \begin{abstract} We give an improved worst-case sample bound for reconstructing a string from independent deletion traces, with its length and retention probability known. For each fixed retention probability, the number of traces is quasipolynomial: the logarithm of the sample budget is $O((\log n)^3(1+\log\log(2n))^6)$. If the deletion probability is at most $n^{-\varepsilon}$ for fixed $\varepsilon>0$, polynomially many traces suffice. These bounds apply to binary strings and to strings of general symbols observed exactly. They concern sample complexity and do not assert an efficient reconstruction algorithm or matching optimality. \end{abstract} \section*{Bound and comparison} Consider the i.i.d.\ deletion channel on an unknown string $x$ of length $n$: a trace consists of the symbols retained, in order with no labels on their original positions, when each position is retained independently with probability $p$. Different traces are independent. The length and retention probability (and the channel model) are known to the reconstructor. All logarithms without specified base are natural. The standard worst-case reconstruction task is to recover the entire string with success probability at least $2/3$ for each possible $x$. \begin{thm} For integer $n\ge 2$ and $00$, setting $\mathcal X=1+\log n/(1+\log(1/q))$, the logarithm of the required sample budget is at most \[ O\big(p^{-1}(\log n)\mathcal X^2 (1+\log\mathcal X)^6\big) \] with an absolute constant. In particular for fixed $\varepsilon>0$ and $0\le q\le n^{-\varepsilon}$ the number of traces can be polynomial in $n$ (with parameters of the polynomial allowed to depend on $\varepsilon$). The same asymptotic bounds also suffice for strings with general symbols (assuming exact observation of retained symbols). This concerns sample complexity, not computational efficiency. \end{thm} This improves the order of the upper estimate with the parameter prescriptions of the quasipolynomial-bound proof of Burudgunte, Valiant and Wang \cite{BVW} (BVW). For clarity, their Theorem 43 statement uses an unspecified log-power $c$ and dependence $p^{-7/3}$ in the exponent. The proof in Section 8 uses $b_{\rm old}=\lceil\log_{1.1}\log_2 n\rceil$ as its depth bound, $p_{\rm base}=3^{-b_{\rm old}}\min(p,1/4)$, and a pair-test bound $4\tau_{\rm base}^{-2C^{b_{\rm old}}}$ (some $C\ge 1$), with $\log(1/\tau_{\rm base})$ given by a constant times $d_{\rm base}^{1/3}p_{\rm base}^{-1/3}$ for $d_{\rm base}=\max(p_{\rm base}^{-6},O(1))$. Thus even ignoring the $C^{b_{\rm old}}$ multiplier, the order from the inverse retention term of that estimate uses a log-power at least $(7/3)\log_{1.1}(3)>26$ for fixed $p$. Our improvement is relative to the proved quantitative estimate with those prescriptions, not a claim about all possible optimizations of BVW's approach. In particular our bound does not go below quasipolynomial order for fixed $00$, see \cite{CDLS}. \section*{Gap probes with level masks} We first work with binary strings. Throughout assume the original length sufficiently large by an absolute constant. Smaller $n\ge2$ can be handled by collecting $\lceil p^{-n}\log 3\rceil$ traces to see one of full length with probability at least $2/3$; for bounded $n\ge2$ use $\log(1/p)\le1/p$ to absorb this budget. For $n=1$ separately $O(p^{-1})$ suffice. If $n\ge2$ and $p<1/n$ the full-length-trace strategy costs at most $\exp(O(p^{-1}\log n))$, since with $s=np\le1$, $n\log(1/p)=p^{-1}s(\log n+\log(1/s))$. Also if $n\ge2$ and $q=1-p<1/n$, then $p^n\ge(1-1/n)^n\ge1/4$, so a constant number of traces suffices via the same strategy. Hence for the rest write $q=1-p$ and suppose $p,q\ge1/n$. Prepend a known block of zeros of length equal to the original length to both candidates when comparing. Traces of the extended inputs can be simulated by prepending independently sampled deletion traces of the zero block. In the binary-case proof from here, \(n\) will now denote this doubled length so still \(p,q\ge1/n\). Fix any two distinct extended binary candidate strings \(x,y\) (sharing the known all-zero prefix), use \(0\)-based source indices, and write \(d\ge n/2\) for their first mismatch. Put \[ \begin{split} \ell_*&=1+\log(1/q),\qquad b=\lceil\log_2(1+\log n/\ell_*)\rceil,\\ M_h&=4^{b-h},\qquad L_h=2^{b-h}\ (0\le h\le b),\\ D&=10^{14},\qquad \epsilon=10^{-5},\qquad a_0=\exp(-10^{16})/(D L_0),\\ t_h&=a_{h+1}=D q L_h a_h^2\ (0\le h1\). A probe at stage \(j\) also has finitely many admissible masks of levels \(h0\) then let \(\delta\downarrow0\)). Since \((v/a_0)\log(1/a_0)=O(b^2)=o(B_0)\), this gives the desired pivot. \section*{Weighted phase step} For the induction step (not yet at stopping) abbreviate \(a=a_j,\ t=a_{j+1},\ B=B_j,\ E=B/f(\theta/a_j)\); thus \(t/a\le.01\), \(a\le a_0\ll .001\), and during a step \(a>.001/n\). Use a polynomial-Gaussian mask \[ \sigma^2=2.4 B/t^2,\quad \ell=\lfloor10^{-10}E\rfloor,\quad v(m)=e^{-y^2/2}\sum_{k=0}^{\ell}(y^2/2)^k/k!,\qquad y=m/\sigma . \] We have \(0\le v\le1\), and for \(0\le m\le3E/a\), \(1-v(m)\le e^{-2E}\): putting \(w=y^2/2\le2 E(t/a)^2\le2 E\exp(-2\cdot10^{16})\), the exponential Taylor remainder times \(e^{-w}\) is at most \((e w/(\ell+1))^{\ell+1}\) by the Taylor remainder formula and the factorial bound. Choose either \(c(s)=\operatorname{Re}s\) or \(c(s)=\operatorname{Im}s\), so that replacing \(s_x,s_y\) by \(c(s_x),c(s_y)\) retains pivot magnitude at least \(\frac12 e^{-E}\) (the original complex pivot is a sum of the two pivots, the latter times \(i\)). For every \(m\) with \(0\le d+m\Lambda. \] Use grid weights \(k_l=h/(\pi(1+(lh-v_0^*)^2))\) for \(|l|\le\gamma\), zero elsewhere. With \(m_l=\max(|F(l)|,|G(l)|)\le1\), define \[ g_l=\min(50,E^{-1}\log(1/m_l)),\quad q_l=\min(50,E^{-1}\log(2 m_l/|F(l)-G(l)|)). \] Set \(g_l=50\) when \(m_l=0\), and \(q_l=50\) when the denominator vanishes. Thus \(g_l,q_l\) are nonnegative and symmetric by reality, with \[ \mathcal G:=\sum_l k_l g_l,\qquad Q:=\sum_l k_l q_l,\qquad \mathcal G+Q\le1.003. \] Indeed \(g_l+q_l\le\min(100,\log(2/|J(e^{ialh})|)/E)\le\min(100,\log(3/|J_\diamond(e^{ialh})|)/E)\) for all large \(n\): when the latter capped upper bound from \(J_\diamond\) does not give 100 use \(|J_\diamond(e^{ialh})|\ge 3 e^{-100E}\) and \(\sup_{|z|=1}|J_\diamond-J|\le 2e^{-200E}\). The Poisson inequality applied at the truncated pivot bounds the continuous integral of this last capped upper bound on \([-10^4,10^4]\) against \(dx/(\pi(1+(x-v_0^*)^2))\) by \(1.0025\) since the Poisson density on the unit circle at angle \(ax\), times \(a\), is at least \((1-2a)/(\pi(1+(x-v_0^*)^2))\), the truncated circle supremum is \(\le2\), and the full-circle deficit is nonnegative; also \(10^4 a<\pi\). Indeed the Poisson density in the rescaled variable \(x\) is \[ \frac{a(1-e^{-2a})} {2\pi((1-e^{-a})^2+2e^{-a}(1-\cos(a x-\theta)))} \ge \frac{1-2a}{\pi(1+(x-v_0^*)^2)}. \] Logarithmic zeros cause no issue by regularization as in the base. For discretization, uniformly for thresholds in \([0,100)\) the strict upper level set of the cap on this interval is a union of \(O(H_*)\) intervals by counting zeros of squared modulus of the truncated polynomial minus a constant (the constant-modulus case is immediate). The smooth-kernel integral and grid sum differ by \(O(H_* h)=o(1)\), uniformly by bounded variation and bounded supremum. Apply layer cake. For the rest of the phase proof, \(h\) denotes the grid mesh above and \(j\) when indexing edge separations or references denotes a nonnegative shift, not the induction stage. Take parameters from the following table by rounding \(|v_0^*|\) up to the next positive integer \(w\) (allow equality, with \(0\mapsto1\)). Here \(S\) is a real interval radius parameter and \(M,J_*\) are conservative lower bounds: \[ \begin{array}{c|ccc} w&S&M&J_*\\\hline 1&1.5&.419&.524\\ 2&2.1&.357&.453\\ 3&2.8&.297&.380\\ 4&3.6&.246&.335\\ 5&4.4&.208&.292 \end{array} \] The simple estimates used below are \[ \begin{gathered} M< \tfrac12-\tfrac2\pi \arctan(\exp(-\pi/S))-.0002,\\ J_* < \tfrac1\pi(\arctan(S+w)+\arctan(S-w))-.0002,\\ T_{\rm lim}(v):=6 f(v)-.1,\\ T_{\rm lim}(w-1)> \max\left\{2.006/M,\,1.005/(J_*-(1+2J_*/M)^2 M/16)\right\} \end{gathered} \] with positive denominator. For example, these rational bounds may be checked without sensitive numerical evaluations as follows. Use \(3.14159<\pi<3.14160\); replace \(\exp(-\pi/S)\) by the upper bound \(1/\sum_{i=0}^{12}(3.14159/S)^i/i!\). Write \(\arctan(S+w)=\pi/2-\arctan(1/(S+w))\). The remaining arctangent arguments have modulus at most \(.6\) and evaluating \(\sum_{i=0}^6(-1)^i x^{2i+1}/(2i+1)\) incurs error at most \(.6^{15}/15\). Lower bound \(\exp(u)\) in \(f(w-1)\) by \(1+u+u^2/2\). More explicitly these substitutions (taking the worst endpoints when dividing by a $\pi$ interval) yield respectively lower bounds on the first two right sides and upper bounds on the maximum on the last right side as follows: \[ \begin{array}{c|ccc} w &\text{first lower}&\text{second lower}&\text{last upper}\\\hline 1&.4217&.5262&4.96\\ 2&.3594&.4553&5.79\\ 3&.2993&.3825&6.94\\ 4&.2478&.3370&8.26\\ 5&.2098&.2940&9.71 \end{array} \] Here the last column just uses the rational $M,J_*$ in the parameter table and rounds up. We record why these capture the two relevant masses. First, for every integer \(1\le j\le S/h\), every (binary or fractional) vertex cover on \([-\gamma,\gamma]\cap\mathbb Z\) of all edges \((l,l+j)\) in this interval has total \(k_l\) weight at least \(M\), uniformly for large \(n\). To see this extend the weights to the untruncated Cauchy kernel \(h K_{\rm Cau}(lh-v_0^*)\), \(K_{\rm Cau}(x)=1/[\pi(1+x^2)]\), and extend the cover by weight 1 at all vertices outside the interval (cost \(<.0001\) for large \(n\), by e.g. the tail bound and \(O(h)\) Riemann error). A fractional cover means vertex numbers in \([0,1]\) with endpoint sums \(\ge1\); on each residue chain mod \(j\) these can be rounded to a random binary cover preserving expected weight (select where the vertex number is at least its threshold), by a uniform threshold \(U_0\in[0,1]\) at even vertices (center counted as even in each chain) and threshold \(1-U_0\) at odd vertices (use non-strict comparison). In each chain take a central vertex \(l\) nearest to \(v_0^*/h\). All weights are nonincreasing outward on each of its two arms. For binary covers the minimum weight is the lesser of the two alternating parity cover weights: if center is omitted, both first neighbors are forced, then pair disjoint edges at offsets \((2,3),(4,5),\ldots\) on each arm require at least the odd weights there; if center is included, edges \((1,2),(3,4),\ldots\) on each arm require the even weights. This reasoning works for the infinite chain by summability. Put \(d'=jh\), \(x=lh-v_0^*\) for the central vertex chosen with \(-d'/2\le x0$ by a semicircle contour closed above with residue at $i$, similarly by symmetry and continuity otherwise). Odd parity similarly has weight \(h\Xi(x+d')\). The latter is no larger since summing the geometric Fourier series gives \(\Xi(x)=(1-r_0^2)/(2d'(1+r_0^2-2r_0\cos(\pi x/d')))\) with \(r_0=e^{-\pi/d'}\). Summing odd parity masses over the \(j\) central representatives gives up to \(O(h)\) error the integral \[ \int_{-d'/2}^{d'/2}\Xi(x+d')\,dx =\tfrac12-\tfrac2\pi\arctan(e^{-\pi/d'}), \] where the identity follows by integrating the series. The error is uniform: the variation of \(x\mapsto\Xi(x+d')\) on this interval is at most \(\int_{\mathbb R}|K_{\rm Cau}'|\); the representatives are one per subinterval in the equal partition of mesh \(h\). This parity mass is minimized at the largest possible \(d'\), yielding the cover bound after the tail subtraction. Second, \(\sum_{|l|\le S/h}k_l>J_*\) directly by Riemann-summing the integral on \([-S,S]\), centered at \(v_0^*\), whose translated Cauchy mass there is minimized at the furthest center \(\pm w\). Write now \(R=\mathcal G/M\), \(T_0=T_{\rm lim}(v_0^*)\ge T_{\rm lim}(w-1)\), so \(2R1.004 \] (a contradiction). Here and below \(T_0<50\) since \(|v_0^*|\le5\). By symmetry choose this witness \(s\ge0\). For each integer \(0\le j\le s\) choose a reference pair \((e_j,e_j+j)\) in the large arc grid with sum of \(g\)-deficits at its endpoints at most \(R\). Indeed if the minimum sum on such edges at \(j\ge1\) is \(R'>R\), the clipped deficits \(\min(1,g_l/R')\) give a fractional cover costing at most \(\mathcal G/R'.999\) together with \(M<.499\). Suppose the claim fails for contradiction. The failed pairs \((l,-l)\) bound the modulus difference at every endpoint or witness \(l\) by \(\Lambda/m_l\), since they bound the difference of squares by \(\Lambda\). At all these indices \(2g_l0$ is at most $\pi\Lambda/v$ by normalization and the chord bound). Hence \(|d_s|\le 100N\Lambda e^{2R E}\) modulo \(2\pi\). Similarly the triple with frequencies \((e_s+s,-e_s,-s)\) gives \(|U(s)-d_s|\le100\Lambda e^{(R+g_s)E}\) modulo \(2\pi\). But \(R+g_s+q_s\le\max(2R+q_s,2g_s+q_s)\Lambda\). Expand the products. Each array copy is a combination of a constant latest valid probe (one wildcard, value 1), the stage-\(j\) probe, and its complex conjugate (including any mask factors), all with scalar coefficients of modulus \(\le1\) from the floor, \(Y,Z_j\) and projection. Each copy also carries the Gaussian-polynomial mask \(v(m_s)\) and phase \(e^{i\theta_s m_s}\). Group the expansion both by factor types per tuple and by the total weak ordering of all selected source positions in all copies, including all equality ties (same source index) as part of the ordering. The number \(P\) of nonempty order categories (also counting component types) satisfies \(\log P=o(B)\) uniformly. To see this, take only assignments already satisfying all exact adjacencies within copies. They consist of at most \(4^{j+1}\) ordered-within-copy contiguous blocks. Specify the weak order of all block starting positions with equality ties included, costing at most \(m!\,2^m\) for \(m\le4^{j+1}\) blocks. After sorting starts and breaking start ties by a fixed label order for counting, process blocks in that order; a new start is either beyond the maximum end index of all prior blocks, or specify its offset from that maximum. The latter offset has magnitude at most \(k-1\) since the new start never precedes the start of the prior block attaining that maximum (of length at most \(k\)). This determines the full total weak position order (lengths known); whenever a start lies beyond the maximum end, its cluster lies strictly after all prior blocks. We only use this encoding to count, not to impose extra distance constraints on a class. There are at most \(81(4k+1)^{4^{j+1}}\) additional specifications including factor types. Thus \(\log P=O(4^j\log(4k+4^{j+1}+2))=O(4^j b)=o(B)\), including the case \(k=1\). Fix any resulting category. All its exact adjacency constraints act across adjacent distinct slots of the merged sorted order, since an old exact edge spanning an intervening distinct slot would make the category empty. Collect them as exact edges of the merged tuple and designate its remaining edges loose. All assignments of remaining distinct slots satisfying the merged exact constraints and strict increase give precisely the assignments in the category (ordering and equalities incorporate every constraint from distinct copies). The merged order \(k'\le4k\); its block count is at most the sum of old block counts because each old block stays within a single merged block, and each resulting block contains at least one old block. Tie bit-predicates are multiplied. Retain all old mask factors, unchanged including their interval endpoints (and conjugations under prior projection; conjugate measures just negate frequencies and conjugate the scalars). They preserve their level bounds and each creates at most 4 copies here. The wildcard component has no old masks. Choose a component whose latest selected index is last in the fixed category (break ties deterministically); relabel as \(s=r\). Denote the overall latest offset by \(Y_0=m_r\), set \(g_r=0,\ g_s=Y_0-m_s\ge0\) for \(s5t\) then contributes at most \[ \exp(1.2031B)\cdot 2\exp[-(4.99)^2(1-\zeta)2.4 B/8] = o(e^{-6 B}) \] still true after multiplication by \(P\). We will replace \(K(g,\omega)\) for retained \(\omega\) by an admissible \(K^{\rm c}(g,\omega)\) satisfying on \(g_s\ge0\) \[ |K-K^{\rm c}|\le e^{-20 B} e^{-\epsilon t \sum_s g_s}. \tag{4} \] The constants here and in admissibility are absolute, uniform on \(|\omega|\le5.01t\), for all stages if \(n\) sufficiently large. The replacement below can be taken measurably in \(\omega\). The resulting replacement error is at most \(\exp(1.2031B-20 B+o(B))\) over all categories by the same coverage and discrepancy-cancellation bound. Given these estimates, suppose for contradiction every merged category with a retained \(\omega\), using \(K^{\rm c}\), fails the next target. Let \(u=(\omega+\theta_{\rm sum})/t\) and \(v=\omega/t\), so \(|u-v|<.01,\ |u|\le5\). The retained discrepancy integrated for any category is then bounded by \(e^{1.203 B}\) times the integral on this interval of \(\exp(-8 B / f(u))\) under \(\nu\). The density in \(v\) is at most \(C\sqrt{B}\exp[-.3(1-\zeta)v^2 B]\). For these \(u,v\), \[ 8/f(u)+.3(1-\zeta)v^2 \ge 7.8\exp(-.05 u^2)+.3u^2-.04 > 7.4 , \] since the minimum of \(7.8e^{-x}+6x\) over \(x\ge0\) is \(6(1+\log(1.3))>7.5\). Hence even after integration and multiplication by \(P\) and adding tails and (4) errors we would get full product discrepancy \(o(e^{-6B})\), contradiction. This proves existence of the required next pivot using the admissible masks if (4) holds. \section*{Radial compactification proving (4)} Fix \(|\omega|\le 5.01t\) and suppress it in \(K(g,\omega)\). Put \(R=R_j\), so \(R/t=(j+1)^2\,M_j/L_j\ge1\). Take \(H_0\) a sufficiently large fixed absolute constant (unrelated to the polynomial \(H\)), \(W=H_0 B/t,\ \tau^2=W/R\), and \[ U(x)=\frac1{\tau\sqrt{2\pi}}\int_{-W}^W e^{-(x-v)^2/(2\tau^2)}\,dv . \] For sufficiently large fixed \(H_0\), \[ \left|K(g)-K(g)\prod_{sW/2\); then \(\mathcal{Q}(g)\ge W^2/(4r)\) by \(g_r=0\) and Cauchy (in fact \(\mathcal{Q}(g)\ge |g|_2^2/r\) on these \(r-1\) free coordinates). In (3) expend half the negative quadratic on \(t\bar g+\epsilon t\sum g_s\) by completing the square as above (cost \(O(B)\)), leaving decay \(\exp(-c W^2/\sigma^2)\); use \(0\le U\le1\). This yields (5) since \(R W\ge H_0 B\) and \(W^2/\sigma^2=(H_0^2/2.4) B\). Consider the entire function of \(d'=r-1\) variables \[ \mathcal J(g)=e^{R\sum_s g_s} K(g)\prod_{sC_3 R}|\widehat{\mathcal J}(\lambda)|d\lambda \le \tfrac14 e^{-20 B}. \tag{6} \] Here and in the following estimates \(s\) index sums may include the coordinate \(g_r=0\). To check this explicitly, from the entire formula (2) valid for \(g=x-i y\) (here \(x,y\in\mathbb R^{d'}\) are real vectors unrelated to the source strings, with zero appended as last coordinate in \(s\) sums), using \(|\omega|\le5.01t\), one obtains \[ |K(x-i y)|\le \exp(C_4 B+C_4 t\textstyle\sum_{s0 \tag{8} \] for an absolute constant \(c_0\le1\). In fact for each such edge let the sums over its covering differences be taken with multiplicity. Then \(\eta=\sum R_h>0\) by coverage. The frequency perturbations sum to at most \(C\eta\) in absolute value. The sum of the \(\beta_s\)'s has square bounded by \[ \eta\sum_{\rm coverings}\frac{(10^4 a_h)^2}{R_h} \le C_6(\eta/q)\sum_{h\ge0}\frac{1}{(h+1)^2} = O(\eta/q), \] using at most \(3\cdot4^{j-h-1}\le M_h\) coverings per level \(h\). Hence when \(\eta\le1\), \(1-|z^*|^2=1-e^{-2\eta}\ge(1-e^{-2})\eta\) and \(|1-z^*|^2\le C_7\eta/q\) by \(|\varphi|=O(\sqrt{\eta/q})+O(\eta)\). When \(\eta>1\), (8) follows from \(|1-z^*|\le2,\ 1-|z^*|^2\ge1-e^{-2}\). For the root \(z_0\) itself one has \(\kappa(z_0)\ge 4/p\): use \(p\ge1/n,\ 04/p\). We move all loose-edge arguments further into the retention disk and also interpolate the exact constraints by the same analytic parameter. Let \(S=4/(p c_0)\) and \(\varsigma\) now denote a complex variable on the strip \(1/2\le\Re\varsigma\le S\). For each loose edge \(e\), let \(\alpha_e+i\delta_e=(1+z_e^*)/(1-z_e^*)\); for each exact edge set its target \(z_e^*=0\), so \(\alpha_e=1,\delta_e=0\). Define \[ z_e(\varsigma)=\frac{\alpha_e\varsigma+i\delta_e-1}{\alpha_e\varsigma+i\delta_e+1} \] so \(z_e(1)=z_e^*\), \(\kappa(z_e(\varsigma))=\alpha_e\Re\varsigma\). Use \(K_{\rm ex}=k-A\) for the number of exact edges in the selected tuple of order \(k\), with \(A\) blocks. Let \(G(\varsigma)\) be its difference sum at \(z_0\) with all exact-edge selectors on gap distance \(\Delta\) replaced by \(z_e(\varsigma)^{\Delta-1}\) (including \(0^0=1\)), loose edges using \(z_e(\varsigma)^\Delta\), and normalize the entire sum by \(n^{-A}(1+\varsigma)^{-2K_{\rm ex}}\). All negative latest-offset terms cancel. On this strip the analytic function \(G\) is bounded by 2: for every exact edge sum over \(\Delta\ge1\) with geometric bound \(1/(1-|z_e|)\), where \(1-|z_e|^2=4\Re\varsigma/|1+\varsigma|^2\) (since \(\alpha=1,\delta=0\)); this costs at most 1 per exact edge against the normalization \(|1+\varsigma|^{-2}\). For other edges use at most \(n\) choices per gap and similarly \(n\) choices for the latest (cancellation if latest before \(d\)); their factors have modulus at most 1. At \(\varsigma=1\) we have \[ \log |G(1)|\ge -A\log n-2K_{\rm ex}\log 2-O(\ell_*8^b(b+1)^6) = -O(\ell_*8^b(b+1)^6). \] Here \(k\le2P_0\,4^b=O(8^b)\), \(A\le4^b\), \(\log n\le\ell_*2^b\). Hadamard's three-lines theorem on \(\Re\varsigma\in[1/2,S]\) gives some \(\varsigma\) on \(\Re\varsigma=S\) with \[ |G(\varsigma)|\ge \exp(-O(p^{-1}\ell_*8^b(b+1)^6)). \tag{9} \] Indeed the right-line weight at 1 is \((1/2)/(S-1/2)\). All constructions up to now may depend on the given pair but the implied constants are absolute (if needed take a point within a factor 2 of the right-line supremum). To recall the strip argument: take positive numbers bounding the suprema on both lines strictly from above, divide the analytic function by the exponential of the complex affine interpolant of the logs of these two numbers, and apply the maximum principle to the quotient times \(\exp(\delta\varsigma^2)\), for \(\delta>0\), on increasingly tall rectangles in the strip. The horizontal-side bound tends to 0 by boundedness and the damping, and on the vertical sides the extra factor has modulus at most \(\exp(\delta S^2)\). Letting \(\delta\downarrow0\) and then taking limits of the two bounds proves log-convex interpolation of the suprema. For this line \(\kappa(z_e(\varsigma))\ge 4q/p\) by (8) and \(\kappa(0)=1\), so \(z_0 z_e(\varsigma)\) and \(z_0\) lie in the closed disk of center \(q=1-p\), radius \(p\). To see the product, for any two inputs \(u,v\) strictly in the unit disk, with \(\kappa(u),\kappa(v)>0\), \[ \frac{|1-u v|^2}{1-|u v|^2} \le \frac{|1-u|^2}{1-|u|^2}+\frac{|1-v|^2}{1-|v|^2} \] by \(1-uv=(1-u)+u(1-v)\) and Cauchy--Schwarz. Hence for the product \(y_e=z_0 z_e(\varsigma)\) this ratio is at most \(p/(2q)\). Also \[ p^2-|y_e-q|^2=p(1-|y_e|^2)-q|1-y_e|^2 \ge \frac p2(1-|z_e|^2). \] The root disk inclusion follows similarly. Put \(\lambda_e=(y_e-q)/p,\lambda_0=(z_0-q)/p\) indexing edges here by \(e=1,\ldots,k-1\). They have modulus \(\le1\), and \(1-|\lambda_e|\ge (1-|z_e|^2)/(4p)\). On a trace \(U\) of the extended input consider \[ T(U)=n^{-A}(1+\varsigma)^{-2K_{\rm ex}} \sum_{0\le s_1<\cdots