diff 56bc728..f6bf760 uniform_trace_reconstruction_v2.txt
diff --git a/uniform_trace_reconstruction_v2.txt b/uniform_trace_reconstruction_v2.txt
index 2a2318d..dc059c5 100644
--- a/uniform_trace_reconstruction_v2.txt
+++ b/uniform_trace_reconstruction_v2.txt
@@ -61,19 +61,19 @@ Write q=1-p. All logarithms are natural unless a base is shown.
Define the budget proxy
- mathsf X(n,p)sfX(n,p) &=
+ X(n,p)sfX(n,p) &=
1+(log n)/(1+log(1/q)), & q>0,[6pt]
1, & q=0,
[4pt]
- B(n,p) &= p^{-1},(log n),mathsf X(n,p)^2sfX(n,p)^2,
- (1+log mathsf X(n,p))^6sfX(n,p))^6 .
+ B(n,p) &= p^{-1},(log n),X(n,p)^2sfX(n,p)^2,
+ (1+log X(n,p))^6sfX(n,p))^6 .
[Uniform trace reconstruction]
There are absolute constants C,cge 1 and one randomized multitape
-Turing machine mathcal AcalA with the following property. Take any
+Turing machine A with the following property. Take any
nge 2, any rational pin(0,1], and any xin{0,1}^n. Given
n and p in binary and access to independent deletion traces of x
with retention probability p, the machine
@@ -96,7 +96,7 @@ generation of the traces.
For a fixed p, plugging q>0 constant into (eq:budget) gives
-mathsf X(n,p)=O(sfX(n,p)=O(log n) and hence
+X(n,p)=O(sfX(n,p)=O(log n) and hence
B(n,p)=O_p((log n)^3 (1+loglog n)^6). Since
M_C=exp(CB), the number of traces is
exp(O_p((log n)^3(1+loglog n)^6)), which is
@@ -104,7 +104,7 @@ quasipolynomial in n. The running time bound
(n+L+M_C)^c is then also quasipolynomial. So both resources are
quasipolynomial for fixed p. When instead qle n^{-kappa} for a
fixed kappa>0, one has 1+log(1/q)ge kappalog n, so
-mathsf X(n,p)sfX(n,p)le 1+1/kappa is bounded and p^{-1} is bounded by a
+X(n,p)sfX(n,p)le 1+1/kappa is bounded and p^{-1} is bounded by a
constant depending only on kappa; then B(n,p)=O_kappa(log n)
and everything is polynomial in n.
@@ -251,7 +251,7 @@ array assigns real numbers m_J to subsets J⊆ U with
|J|le 2D, with m_∅=1, subject to the single
positive-semidefiniteness condition
- mathcal M_D(m)=(m_calM_D(m)=(m_{I△ J})_{substack{I,J⊆ U
+ M_D(m)=(m_{I△ J})_{substack{I,J⊆ U
|I|,|J|le D}}succeq 0,
where △ is symmetric difference. Only subsets that actually
@@ -262,7 +262,7 @@ The array defines a functional EE on polynomials of degree at most
2D as follows: substitute X_i=u_i for ile d; expand each remaining
bit as (1+Y_i)/2; reduce Y_i^2=1; then set
EE[prod_{iin J}Y_i]=m_J and extend complex-linearly. Call
-umapstoEE a positive moment functional of order 2D fixing
+u|->EE a positive moment functional of order 2D fixing
u. The word ``positive'' asserts (eq:moment-matrix), not the
existence of an actual probability law realising all these moments; any
feasible array, even a fictitious one, is allowed in the test.
@@ -322,10 +322,10 @@ For p<1 introduce the bookkeeping quantities
Q=1+log(1/q_*),
Y=1+(log n)/(Q).
-When qge 1/n these give Y=mathsf X(n,p)sfX(n,p) exactly. When q<1/n
-they give 1le mathsf X(n,p)sfX(n,p)le Y<2. In all cases
+When qge 1/n these give Y=X(n,p)sfX(n,p) exactly. When q<1/n
+they give 1le X(n,p)sfX(n,p)le Y<2. In all cases
- mathsf X(n,p)sfX(n,p)le Yle 2,mathsf X(n,p),sfX(n,p),
+ X(n,p)sfX(n,p)le Yle 2,X(n,p),sfX(n,p),
QY=Q+log nle Clog n
for an absolute constant C, since nge 2.
@@ -378,17 +378,17 @@ absolute coefficients of every f_j.
For s>0 and omegainRR, the signal of the feature is the
exponentially damped Fourier sum
- mathcal S_f(s,calS_f(s,omega)
+ S_f(s,omega)
=sum_{j=1}^n Delta[f_j],e^{(-s+iiomega)(j-d)}.
Every monomial in f_j uses positions at most j, so
Delta[f_j]=0 for j<d; hence, despite the exponent being centred at
d, only jge d contribute. For the base case k=1, where f_j=X_j,
-this reads mathcal S_f(s,0)=calS_f(s,0)=sum_{jge d}Delta[X_j],e^{-s(j-d)}, whose
+this reads S_f(s,0)=calS_f(s,0)=sum_{jge d}Delta[X_j],e^{-s(j-d)}, whose
first term is Delta[X_d]=pm1; that single term is what makes the
starting signal about 1/2 at decay s=4, as made precise in
(eq:initial-signal). The whole multiscale argument has one goal: to preserve a detectable signal
-mathcal S_f(s,calS_f(s,omega) while shrinking both s and |omega| to
+S_f(s,omega) while shrinking both s and |omega| to
O(1/n), at the cost of raising the order k by at most a factor of
four per step.
@@ -415,13 +415,13 @@ Suppose
]
and, for some (beta Sle sle S) and (abs{omega}le2.002s),
- abs{mathcal S_f(s,calS_f(s,omega)}ge e^{-E},
+ abs{S_f(s,omega)}ge e^{-E},
Ege C_0(1+klog(2k)+log H_f+logfrac1{S'}).
Then there is an order-(k') feature (f'), with (1le k'le4k),
satisfying
- abs{mathcal S_calS_{f'}(s',omega')}ge e^{-7.98E},
+ abs{S_{f'}(s',omega')}ge e^{-7.98E},
beta S'le s'le S', abs{omega'}le2.002s',
and
@@ -490,7 +490,7 @@ First, P is shown to keep a signal at almost the original decay:
Let V be a centred real normal variable with variance sigma^{-2}.
Since W(l),mathbf EbfE,e^{Vl}=1,
[
- mathcal S_f(s,calS_f(s,omega)=mathbf EbfE,P(e^{-s+V+iiomega}).
+ S_f(s,omega)=mathbf EbfE,P(e^{-s+V+iiomega}).
]
Write delta=10^{-4}. Exponential tilting gives
[
@@ -570,7 +570,7 @@ for r=0 its total mass is 1/2. In particular
Proof.
For r=0 put half of w(v),dv on the diagonal. Suppose r>0 and
-partition the line into chains v+jr, jinmathbb Z,bbZ, with
+partition the line into chains v+jr, jinZ, with
-r/2le v<r/2. Write w_j=w(v+jr). On the edge from j to j-1, for
jge1, put weight
[
@@ -582,7 +582,7 @@ positive vertex. Build the negative-side edges the same way, from the
negative tail toward zero. The only possibly unused weight sits at the
central vertex, with value
[
- R(v)=sum_{jinmathbb Z}bbZ(-1)^j w(v+jr).
+ R(v)=sum_{jinZ}-1)^j w(v+jr).
]
To check no weight is overused, periodize w at period 2r and
subtract its translate by r. By (eq:cauchy-transform), with
@@ -868,13 +868,13 @@ against the Gaussian bound. So the iterated deformation is a jointly
absolutely convergent integral, and finite tuple sums may be exchanged
with it.
-Write mathcal U=calU={u:max_r|u_r|le S'/16}. Integrating the last bound
+Write U={u:max_r|u_r|le S'/16}. Integrating the last bound
and splitting the negative quadratic term into two equal halves on
-mathcal U^ccalU^c gives absolute constants C,C' with
+U^c gives absolute constants C,C' with
|nu|_{abs}
&le Cexp(C_4K^2beta^2E/2),
- int_{mathcal U^c}calU^c|dnu|
+ int_{U^c}|dnu|
&le C'expBigl[((C_4K^2beta^2)/(2)
-(c_1K^2)/(1024))EBigr].
@@ -884,7 +884,7 @@ then betale1/4 with C_4K^2beta^2/2le0.001. Enlarging C_0 to
absorb fixed prefactors gives
|nu|_{abs}le e^{0.005E},
- int_{mathcal U^c}calU^c|dnu|le e^{-20E}.
+ int_{U^c}|dnu|le e^{-20E}.
This respects the constant order fixed earlier: K first, beta
second, then eta_0 small to meet the window estimate, and only
@@ -906,7 +906,7 @@ The link from j_r to j_{r+1} receives the parameter
exp(-rb-iisum_{l=1}^r(u_l+t_l)), 1le r<m.
Thus every added damping is at least b, uniformly in u. On
-mathcal U,calU,
+U,
[
|Ω|le(beta+1/4)S',
beta S'le s'le[beta+rho(beta+1/4)]S'le S',
@@ -947,7 +947,7 @@ interleaving is fixed, choosing arbitrary strictly increasing values for
its v distinct positions specifies exactly one assignment to its
labeled tuples, so no further restriction remains on the new tuple. Its
largest position is i_v=j_m. Summing all these assignments gives an
-order-v feature f^{mathcal I,u}calI,u with outer weight
+order-v feature f^{I,u}calI,u with outer weight
exp((-s'+iiΩ)(i_v-d)).
The needed combinatorial fact controls its height.
@@ -976,7 +976,7 @@ one edge may contribute to several new parameters, but it need pay for
only one of their upper bounds. Concretely, take two old tuples
(i_1,i_3,i_5) and (i_2,i_4,i_6) joined by one dashed endpoint
link-edge, with gaps g_a=(i_a,i_{a+1}) for 1le ale5. The assignment
-g_amapsto e_a, 1le ale5, gives every gap a distinct crossing edge:
+g_a|-> e_a, 1le ale5, gives every gap a distinct crossing edge:
e_1 crosses both g_1 and g_2 but is charged only to g_1, and e_2
supplies the bound for g_2.
@@ -1002,7 +1002,7 @@ centering
caption{A schematic interleaving of the two old tuples (i_1,i_3,i_5)
and (i_2,i_4,i_6), joined by the dashed endpoint link e_5. Here
-g_a is the gap (i_a,i_{a+1}). The assignment g_amapsto e_a for
+g_a is the gap (i_a,i_{a+1}). The assignment g_a|-> e_a for
1le ale5 uses a distinct crossing edge for every gap: e_1 crosses
both g_1 and g_2 but is charged only to g_1, while e_2 supplies
the bound for g_2.}
@@ -1014,7 +1014,7 @@ is the sum of a_e over edges crossing it, hence at least that of its
assigned edge. Since 1+1/a decreases with a,
Lemma~lem:edge-gap-assignment gives
- H_{f^{mathcal I,u}calI,u}
+ H_{f^{I,u}calI,u}
&leprod_{e assigned}(1+1/a_e)
leprod_{e present}(1+1/a_e) notag
&le H_f^m(1+1/b)^{m-1}le H_f^4(1+1/b)^3.
@@ -1027,20 +1027,20 @@ is the empty product one.
{itshape Completing the multiscale estimate.}
Apply Delta to the expanded product and use the integral
-representation for each interleaving. With nu_{mathcal I}calI the
+representation for each interleaving. With nu_{I} the
corresponding measure,
Delta[product]
- =sum_{mathcal I}calIint_{RR^m}
- mathcal S_calS_{f^{mathcal I,u}calI,u}(s',Ω),dnu_{mathcal I}calI(u).
+ =sum_{I}{RR^m}
+ S_{f^{I,u}calI,u}(s',Ω),dnu_{I}
All estimates are uniform over interleavings, and the integrands are
-uniformly bounded even outside mathcal U.calU. Indeed, for each fixed
-endpoint j the coefficients of f_j^{mathcal I,u}calI,u have absolute sum at
+uniformly bounded even outside U. Indeed, for each fixed
+endpoint j the coefficients of f_j^{I,u}calI,u have absolute sum at
most the height in (eq:interleaving-height), terms with j<d
vanish under Delta by prefix agreement, and s'ge b gives
- |mathcal S_calS_{f^{mathcal I,u}calI,u}(s',Ω)|
+ |S_{f^{I,u}calI,u}(s',Ω)|
le 2H_f^4(1+1/b)^3sum_{lge0}e^{-bl}
le 2H_f^4(1+1/b)^4.
@@ -1054,7 +1054,7 @@ enough absolute C_0 gives
]
Here log(1+1/b) is at most an absolute constant plus log(1/S'),
because b=beta S', S'le1, and beta is already fixed. If every
-signal in (eq:product-feature-integral) with uinmathcal UcalU had
+signal in (eq:product-feature-integral) with uinU had
magnitude below e^{-7.98E}, then (eq:contour-mass) and
(eq:contour-uniform-signal) would give
[
@@ -1063,9 +1063,9 @@ magnitude below e^{-7.98E}, then (eq:contour-mass) and
le e^{-7.965E}+e^{-19.98E}<e^{-7.94E}.
]
This contradicts Lemma~lem:balanced-product. Some interleaving and
-some uinmathcal UcalU therefore give a feature with signal at least
+some uinU therefore give a feature with signal at least
e^{-7.98E}. Its order is at most mkle4k; (eq:new-outer-decay)
-and the bounds on mathcal UcalU give the outer parameters;
+and the bounds on U give the outer parameters;
(eq:interleaving-height) gives (eq:multiscale-height); and
the crossing description gives the parameter factors and
(eq:added-parameters). This completes the proof of
@@ -1079,7 +1079,7 @@ control the signal, so a single one-variable continuation bridges the gap.
Throughout, 0<p<1 and q_*,Q,Y are as in
(eq:aux-parameters). Recall from (eq:aux-comparisons) that
- 1lemathsf X(n,p)sfX(n,p)le Yle2mathsf X(n,p),sfX(n,p),
+ 1leX(n,p)sfX(n,p)le Yle2X(n,p),sfX(n,p),
QY=Q+log nle Clog n.
@@ -1132,7 +1132,7 @@ ell_j=max{0,log(1/S_j)} the recurrence gives
]
hence
- log(1/S_j)le C2^jA_0qquad(0le jle h).
+ log(1/S_j)le C2^jA_0 (0le jle h).
Now iterate Proposition~prop:multiscale. Start with the order-one
@@ -1140,13 +1140,13 @@ feature f_i^{(0)}=X_i at decay s_0=4 and frequency zero. Prefix
agreement gives Delta[X_i]=0 for i<d while abs{Delta[X_d]}=1;
since abs{Delta[X_i]}le2 for all i,
- abs{mathcal S_calS_{f^{(0)}}(4,0)}
+ abs{S_{f^{(0)}}(4,0)}
ge1-2sum_{rge1}e^{-4r}
=1-(2)/(e^4-1)>frac12 .
Use error exponents
- E_j=C_5A_0mu^jqquad(0le jle h),
+ E_j=C_5A_0mu^j (0le jle h),
with absolute C_5 chosen after H and eta.
@@ -1156,7 +1156,7 @@ f^{(j)} of order k_jle4^j with
beta S_jle s_jle S_j,
abs{omega_j}le2.002s_j,
- abs{mathcal S_calS_{f^{(j)}}(s_j,omega_j)}ge e^{-E_j},
+ abs{S_{f^{(j)}}(s_j,omega_j)}ge e^{-E_j},
log H_{f^{(j)}}le C4^jA_0.
@@ -1194,7 +1194,7 @@ small absolute c_2>0 so that every elementary parameter obeys
agegammamin{abs{theta},D_*theta^2},
gamma=c_2q_*Y^{-alpha}le1.
-Indeed, the increasing map umapsto umin{1,D_*u} changes by at most
+Indeed, the increasing map u|-> umin{1,D_*u} changes by at most
a factor max{C_1,C_1^2} when u becomes C_1u, so
c_2lebetaeta/max{C_1,C_1^2} suffices; shrinking c_2 further
covers z_0 since absomegale2.002s. Conjugating an elementary
@@ -1212,7 +1212,7 @@ In particular an inner gap of f, even after multiplying by z_0,
contains at most (4^h+2)/3le D_* elementary factors.
The next lemma explains why this count matters. The Cayley map
-zmapsto(1+z)/(1-z) sends the unit disk to the right half-plane, and a
+z|->(1+z)/(1-z) sends the unit disk to the right half-plane, and a
quantitative distance from its boundary is needed.
[Products with controlled damping]
@@ -1263,14 +1263,14 @@ f. Define the polynomial in k complex variables
At the point Z_0^*=z_0, Z_r^*=z_rz_0 (1le r<k), the powers of
z_0 telescope to i_k, so
- F(Z^*)=z_0^d,mathcal S_f(s,calS_f(s,omega),
+ F(Z^*)=z_0^d,S_f(s,omega),
abs{F(Z^*)}ge e^{-E_h-1},
where sdle nS_hle1. Each coordinate of Z^* is a nonempty product of
at most D_* elementary parameters, so Lemma~lem:product-cayley
gives
- re(1+Z_r^*)/(1-Z_r^*)ge c_3gammaqquad(0le r<k).
+ re(1+Z_r^*)/(1-Z_r^*)ge c_3gamma (0le r<k).
A bound on the coordinates' collective closeness to the unit circle is also needed. If
z_r=e^{-a_r+iitheta_r}, then
@@ -1325,7 +1325,7 @@ abs{G(u)}le n^kε when all abs{u_r}le1; on that polydisk
abs{Z_r}le q+p=1. Thus (eq:trace-generating-identity) gives
abs{F(Z)}le(n/p)^kε
- qquadwhenever abs{Z_r-q}le p (0le r<k).
+ whenever abs{Z_r-q}le p (0le r<k).
This uses only ordinary trace ranks and the convention that a rank
product is zero when the trace is too short.
@@ -1335,7 +1335,7 @@ The lower bound (eq:input-polynomial-signal) and the upper bound
coordinates the disk abs{Z-q}le p becomes a half-plane:
abs{Z-q}le p
- iff re(1+Z)/(1-Z)gefrac qpqquad(abs Z<1).
+ iff re(1+Z)/(1-Z)gefrac qp (abs Z<1).
Indeed, writing w=(1+Z)/(1-Z) and expanding
abs{pw-(1+q)}^2le p^2abs{w+1}^2 reduces it to 4qle4pre w. All
@@ -1504,8 +1504,8 @@ Using (eq:aux-comparisons-2), the right-hand side of
(eq:separation-exponent) is at most
frac Cp(log n)Y^2(1+log Y)
- le C_6,p^{-1}(log n)mathsf X(n,p)^2sfX(n,p)^2
- (1+logmathsf X(n,p))^6sfX(n,p))^6
+ le C_6,p^{-1}(log n)X(n,p)^2sfX(n,p)^2
+ (1+logX(n,p))^6sfX(n,p))^6
=C_6,B(n,p).
Taking ε=e^{-C_{sep}B(n,p)} with
@@ -1542,34 +1542,34 @@ zeta=2^{-b_zeta} so that
with C_{sep} from Theorem~thm:separation. Integer
formulas for these choices come later. Let
[
- mathcal I_D=calI_D={I⊆{1,...,n}:1le|I|le D},
- N=|mathcal I_D|,calI_D|,
+ I_D={I⊆{1,...,n}:1le|I|le D},
+ N=|I_D|,calI_D|,
T=512(1+N)zeta^{-2},
]
which is an integer. From T independent traces form the empirical mean
widehatwidehat t_It_I of the rank observable defining T_I, for every
-Iinmathcal I_D.calI_D. These are ordinary trace observables: a requested
+IinI_D. These are ordinary trace observables: a requested
rank that is absent contributes zero.
-For each fixed input x let mathcal GcalG be the event
+For each fixed input x let G be the event
- |widehatwidehat t_I-T_I(x)|t_I-T_I(x)|lezeta/8quadfor every Iinmathcal I_D.calI_D.
+ |widehatwidehat t_I-T_I(x)|t_I-T_I(x)|lezeta/8quadfor every IinI_D.
Each observable takes values in {0,1}, so its empirical mean has
variance at most 1/(4T). Chebyshev and a union bound give
- mathbb P_x(bbP_x(mathcal G^c)calG^c)le(16N)/(Tzeta^2)lefrac1{32}.
+ P_x( G^c)calG^c)le(16N)/(Tzeta^2)lefrac1{32}.
The same event controls all the prefix tests, even though the prefixes are
chosen using the data.
For a proposed prefix, use the remaining sign variables and their moment
-matrix M(m)=mathcal M_D(m)calM_D(m) from (eq:moment-matrix); its nonempty
+matrix M(m)=M_D(m) from (eq:moment-matrix); its nonempty
moment coordinates form a real vector m. Consider the rational
constraints
min[-1,1]^l, M(m)succeq0,
- |EE_m[T_I]-widehatwidehat t_I|t_I|lezetaquad(Iinmathcal I_D),calI_D),
+ |EE_m[T_I]-widehatwidehat t_I|t_I|lezetaquad(IinI_D),
where l is the number of moment coordinates. Substituting the prefix and
writing each remaining bit as one half of one plus its sign makes
@@ -1577,20 +1577,20 @@ EE_m[T_I] an affine function of m; its nonconstant coefficients have
absolute sum at most one by (eq:coeff-bounds).
-On mathcal G,calG, a prefix whose first incorrect bit is at its last
+On G, a prefix whose first incorrect bit is at its last
position has no solution to (eq:prefix-feasibility). Every correct
prefix has a moment vector m^*in[-1,1]^l such that, with G the
dimension of its moment matrix,
M(m^*)succeq(zeta/8)Id_G,
- |EE_{m^*}[T_I]-widehatwidehat t_I|t_I|lezeta/2quad(Iinmathcal I_D).calI_D).
+ |EE_{m^*}[T_I]-widehatwidehat t_I|t_I|lezeta/2quad(IinI_D).
Proof.
If a wrong prefix had a feasible moment vector, then
(eq:empirical-good) and (eq:prefix-feasibility) would give
-|EE_m[T_I]-T_I(x)|le9zeta/8 for all Iinmathcal I_D,calI_D, contradicting
+|EE_m[T_I]-T_I(x)|le9zeta/8 for all IinI_D, contradicting
Theorem~thm:separation and (eq:decoder-parameters).
For a correct prefix, mix the moments of the true completion with weight
@@ -1654,7 +1654,7 @@ norm a_2le1 and, under the slack assumption,
If instead the matrix condition fails, find a nonzero rational vector v
with v^top M(m^{cur})v<0 (constructed just below). Write the
-associated affine form as v^top M(m)v=c+hcdot m and set
+associated affine form as v^top M(m)v=c+h· m and set
a=h/(G,v^top v). Each matrix entry is the constant 1 or one moment
coordinate, so norm h_1lenorm v_1^2le Gnorm v_2^2 and
norm a_2le1. The slack matrix bound gives
@@ -1750,7 +1750,7 @@ binary input. Continue to assume p<1 and use q_*,Q,Y from
(eq:aux-parameters). Define the positive integers
u&=1+lceillog_2 nrceil, &
- v&=1+lfloorlog_2(1/q_*)rfloor,
+ v&=1+floor(log_2(1/q_*)),
y&=1+lceil u/vrceil, &
w&=1+lceillog_2 yrceil, &
a_p&=lceil1/prceil.
@@ -1766,7 +1766,7 @@ The elementary comparisons
wasymp1+log Y, p^{-1}le a_ple2p^{-1}
]
have absolute constants. For the bound on y use uge(log n)/log2
-and vle Q/log2. With Yasympmathsf X(n,p)sfX(n,p) these give
+and vle Q/log2. With YasympX(n,p)sfX(n,p) these give
B(n,p)le a_p,u,y^2,w^6le C,B(n,p).
@@ -1805,7 +1805,7 @@ substituting the prefix constructs them directly; no list of complete
trace masks is needed.
These enumerations fit the resource scale. From D=O(Y^2),
-Yasympmathsf X(n,p),sfX(n,p), and (eq:budget),
+YasympX(n,p),sfX(n,p), and (eq:budget),
Dlog n=O(B(n,p)).
@@ -1840,10 +1840,10 @@ For p<1, use (eq:integer-decoder-parameters), request the T
traces, and compute the empirical statistics. Run the prefix rule. This
defines the machine on every stream of well-formed traces.
-On mathcal G,calG, induction on prefix length shows precisely the correct
+On G, induction on prefix length shows precisely the correct
extension accepts: the incorrect extension is infeasible by
Lemma~lem:prefix-slack, and the correct one has the slack that
-guarantees acceptance. Thus the output is x on mathcal G,calG, whose
+guarantees acceptance. Thus the output is x on G, whose
probability is at least 31/32>2/3 for each fixed x.
Each trace has at most n bits and one delimiter. Reading the traces and