A tractable streaming moment with square-root cancellation cost
in symmetric Lévy decompositions

Abstract

We construct a fixed computable nonnegative even function $f$ on the integers whose moment $F_{f}(x)=\sum_{i}f(x_{i})$ admits a small-space turnstile sketch, but whose approximation by differences of real symmetric Lévy–Khintchine exponents requires large cancellation. The function satisfies $f(0)=0$ and $f(k)\in\{1,3\}$ for $k\neq 0$ . Its sketch uses space polynomial in inverse relative accuracy and in the logarithms of dimension, final frequency bound, and inverse failure probability. On the integers $[-n,n]$ , the cancellation cost of a split $h=g_{+}-g_{-}$ is the least $\rho$ such that $g_{+}+g_{-}\leq\rho f$ . Among splits satisfying $|h-f|\leq\eta f$ , the minimum cost is $\Theta_{\eta}(\sqrt{n})$ for every fixed $0<\eta<1/6$ ; an exact finite Fourier split supplies the matching upper bound. This refutes the real-even integer specialization of the controlled-decomposition conjecture of Pettie and Wang (arXiv 2026). The witness uses Rudin–Shapiro signs: their order- $n$ pairing with the target’s second differences contrasts with the $O(\sqrt{n})$ uniform norm of their cosine polynomial. A positive-measure representation of second differences turns this contrast into a lower bound for the entire symmetric Lévy cone, including arbitrary jump measures and Gaussian parts.

Note. This paper was generated entirely by AI, including MiMo, using an automated research pipeline developed by Chenghua Liu and Hanyu Li.

1 Introduction

A turnstile stream maintains an integer vector $x$ under coordinate increments and decrements. For a fixed function $f$ , moment estimation asks for a relative approximation to $F_{f}(x)=\sum_{i}f(x_{i})$ using small space. When $f(0)=0$ and $1\leq f(k)\leq 3$ for $k\neq 0$ , a sample of the nonzero coordinates is enough, provided its weights can be evaluated in small space: every sampled weight is bounded, and the total weight is comparable to the support size. This argument places no restriction on how the values $f(1),f(2),\ldots$ are arranged. We show that their arrangement can nevertheless obstruct a proposed analytic characterization of tractability.

The Fourier–Hahn–Lévy construction of Pettie and Wang represents moments by differences of Lévy–Khintchine exponents [1, 2]. For an exact split $f=g_{+}-g_{-}$ , estimates of the two component moments with relative error $\alpha$ have combined absolute error at most $\alpha\sum_{i}(g_{+}(x_{i})+g_{-}(x_{i}))$ . Thus a bound $g_{+}+g_{-}\leq\rho f$ permits relative error $\varepsilon$ by estimating the components to accuracy $\varepsilon/\rho$ . The size of $\rho$ , not merely the existence of a signed representation, determines whether this reduction preserves a small-space guarantee. A Fourier expansion always provides such a representation on a finite integer interval, but need not control the cancellation uniformly as the interval grows.

We exhibit one fixed computable function with nonzero values in $\{1,3\}$ for which the smallest cancellation cost is $\Theta(\sqrt{n})$ on $[-n,n]$ , even after allowing a small fixed relative approximation error. The function is a constant plus the Rudin–Shapiro sequence. Its streaming algorithm only needs to evaluate a sampled sign; its analytic representation must reproduce the pattern of all the signs. The lower bound allows both exponents to depend on $n$ and the approximation error, so selecting a different decomposition at each scale does not remove the gap.

Proving that one Fourier split has large mass would not establish this claim: another set of frequencies, or a continuous jump measure, might give a cheaper split. We instead test every symmetric Lévy exponent through its centered second differences. These are cosine coefficients of a positive measure whose total mass is the exponent’s value at $1$ . A cosine polynomial therefore bounds the corresponding pairing with $D(g_{+}-g_{-})$ by its uniform norm times $g_{+}(1)+g_{-}(1)$ . Rudin–Shapiro signs supply both sides of the separation: linearly many sign changes give a pairing of order $n$ , whereas the polynomial has norm $O(\sqrt{n})$ . The pairing loses only $O(\eta n)$ under relative error $\eta$ , which is why approximation does not avoid the obstruction. Parseval’s identity gives an exact Fourier split of matching cost.

The pointwise controlled-decomposition question is Conjecture 1 of the expanded Pettie–Wang manuscript [2, Section 8.1]; we address its real-even integer specialization below. Wang’s harmonic sketch also uses a domination condition for signed combinations [3, Theorem 1 and Remark 3]. Our example shows why such an analytic condition cannot be inferred from streaming tractability alone. General turnstile characterizations, such as [4], impose no Lévy representation, and the bounded weights here require only the support-sampling methods of [5, 6].

1.1 Model and separation theorem

Let $\mathcal{L}_{\mathrm{sym}}$ be the cone of real symmetric Lévy–Khintchine exponents

g(x)=Ax^{2}+\int_{0}^{\infty}(1-\cos(xs))\,\nu(ds),\qquad A\geq 0,\qquad\int_{0}^{\infty}\min\{s^{2},1\}\,\nu(ds)<\infty,

(1.1)

where $\nu$ is a positive Borel measure on $(0,\infty)$ . Every $g\in\mathcal{L}_{\mathrm{sym}}$ is even and nonnegative, and $g(0)=0$ . For an even function $f:\mathbb{Z}\to[0,\infty)$ with $f(0)=0$ , an integer $n\geq 1$ , and $0\leq\eta<1$ , define

\rho_{\eta}^{f}(n):=\inf\left\{\rho\geq 0:\begin{array}[]{l}\text{there exist $g_{+},g_{-}\in\mathcal{L}_{\mathrm{sym}}$ such that, for every integer $|k|\leq n$,}\\ |g_{+}(k)-g_{-}(k)-f(k)|\leq\eta f(k),\\ g_{+}(k)+g_{-}(k)\leq\rho f(k)\end{array}\right\}.

(1.2)

The infimum of the empty set is $+\infty$ . We call $\rho$ the cancellation cost; $g_{+}+g_{-}$ is the corresponding cancellation envelope. The case $\eta=0$ requires exact agreement on the specified integers. No condition is imposed outside this range. Formulating the constraints as inequalities also covers targets that vanish at additional integers.

Write $\mathcal{T}_{\mathrm{even}}^{+}$ for the fixed nonnegative even functions $f$ with $f(0)=0$ for which the following holds. For every dimension $d\geq 1$ , integer frequency bound $U\geq 1$ , accuracy $0<\varepsilon\leq 1$ , and failure probability $0<\delta<1/3$ , the moment

F_{f}(x)=\sum_{i=1}^{d}f(x_{i}),\qquad x\in\mathbb{Z}^{d},\quad\|x\|_{\infty}\leq U,

admits a one-pass turnstile sketch using

\operatorname{poly}\bigl(\varepsilon^{-1},\log(2d),\log(2U),\log(1/\delta)\bigr)\quad\text{bits}

(1.3)

and returning a $(1\pm\varepsilon)$ -estimate with probability at least $1-\delta$ . The vector is initially zero, updates have the form $x_{i}\leftarrow x_{i}+\Delta$ with $\Delta\in\mathbb{Z}$ , and the stream is fixed independently of the sketch’s randomness. The promise on $U$ concerns the final vector; no bound on intermediate frequencies is needed for our construction. Space includes the random seed and decoding workspace, but not the read-only binary encoding of an incoming update. Unless a base is indicated, $\log$ denotes the natural logarithm.

The real-even integer formulation of the controlled-decomposition question asks whether

f\in\mathcal{T}_{\mathrm{even}}^{+}\quad\Longrightarrow\quad\rho_{\eta}^{f}(n)\leq q_{f}\bigl(\eta^{-1},\log(2n)\bigr)\quad(n\geq 1,\ 0<\eta<1)

(1.4)

for some polynomial $q_{f}$ depending only on $f$ . This is the real-symmetric specialization of Conjecture 1 in the expanded 2026 version of Pettie–Wang [2]. Their formulation uses a common size parameter for dimension and frequency range; keeping these parameters separate in (1.3) does not change the implication under consideration when both are polynomially bounded in that parameter.

Our counterexample uses the Rudin–Shapiro sequence

	$\displaystyle r_{k}$	$\displaystyle=(-1)^{a(k)}\quad(k\geq 0),$		(1.5)
	$\displaystyle a(k)$	$\displaystyle=\#\{\text{overlapping $11$ patterns in the binary expansion of $k$}\}.$		(1.5)

Define

f(0)=0,\qquad f(k)=2+r_{|k|}\in\{1,3\}\quad(k\neq 0).

(1.6)

This is a single computable function, not a family of tables indexed by the cutoff.

Theorem 1.1.

The function $f$ in (1.6) belongs to $\mathcal{T}_{\mathrm{even}}^{+}$ . For every integer $n\geq 15$ and every $0<\eta<1/6$ ,

\frac{(1-6\eta)\sqrt{n+1}}{8\sqrt{2}}<\rho_{\eta}^{f}(n)\leq\rho_{0}^{f}(n)\leq 6\sqrt{2n+1}.

(1.7)

The upper bound $\rho_{0}^{f}(n)\leq 6\sqrt{2n+1}$ holds for every $n\geq 1$ . Consequently, for each fixed $0<\eta<1/6$ , $\rho_{\eta}^{f}(n)=\Theta_{\eta}(\sqrt{n})$ , and (1.4) is false.

For example, at $\eta=1/100$ the theorem gives $\rho_{1/100}^{f}(n)>\sqrt{n+1}/24$ for every $n\geq 15$ . With dimension and final frequency bound at most $n$ , the streaming space at fixed accuracy is polynomial in $\log n$ , while the cancellation cost grows as $\sqrt{n}$ . The theorem concerns precisely the envelope in (1.2); it does not give a lower bound for estimators that use correlations between components or a different complex or asymmetric representation.

2 Second differences and the Rudin–Shapiro certificate

The jump measure in (1.1) can have infinite mass near the origin, so its total variation is not itself a suitable measure of cancellation. Second differencing inserts the integrable factor $1-\cos s$ . The resulting finite measure retains all the integer values needed for the lower bound, and its mass is already controlled by the cancellation constraint at the single integer $1$ .

For a function $u$ on $\mathbb{Z}$ , write

Du(k)=\frac{u(k+1)-2u(k)+u(k-1)}{2}.

(2.1)

The factor of $1/2$ makes $Dg(0)=g(1)$ for an even function vanishing at zero. The next identity extends this normalization to all cosine coefficients.

Lemma 2.1 (Positive second-difference measure).

For every $g\in\mathcal{L}_{\mathrm{sym}}$ , there is a finite positive measure $\lambda_{g}$ on $\mathbb{T}=\mathbb{R}/(2\pi\mathbb{Z})$ such that

Dg(k)=\int_{\mathbb{T}}\cos(kt)\,\lambda_{g}(dt)\quad(k\in\mathbb{Z}),\qquad\lambda_{g}(\mathbb{T})=g(1).

(2.2)

Proof.

Take the pushforward of $(1-\cos s)\nu(ds)$ under reduction modulo $2\pi$ , and add $A\delta_{0}$ , where $A$ and $\nu$ are from (1.1). This defines a positive finite measure because $1-\cos s\leq 2\min\{s^{2},1\}$ , and its mass is

\lambda_{g}(\mathbb{T})=A+\int_{0}^{\infty}(1-\cos s)\,\nu(ds)=g(1).

The identities

D(Ak^{2})=A,\qquad D(1-\cos(ks))=(1-\cos s)\cos(ks)

now give (2.2). Passing the finite difference through the integral is legitimate: each original integrand is integrable at the relevant integer, and the resulting integrand is bounded in absolute value by the integrable function $1-\cos s$ . The measure $\nu$ itself need not be finite. ∎

Corollary 2.2 (Dual inequality).

Let $h=g_{+}-g_{-}$ and $s=g_{+}+g_{-}$ , with $g_{+},g_{-}\in\mathcal{L}_{\mathrm{sym}}$ . For every finitely supported real sequence $(a_{k})_{k\in\mathbb{Z}}$ ,

\left|\sum_{k}a_{k}Dh(k)\right|\leq s(1)\left\|\sum_{k}a_{k}\cos(kt)\right\|_{L_{\infty}(\mathbb{T})}.

(2.3)

Proof.

The signed measure $\lambda_{g_{+}}-\lambda_{g_{-}}$ has total variation at most $g_{+}(1)+g_{-}(1)=s(1)$ . Integrating the cosine polynomial against this measure gives (2.3). ∎

Remark 2.3.

The inequality applies to Gaussian terms, finite or infinite jump measures, and both continuous and atomic measures. Its relation to the normalized Lévy cone can be made explicit. For integer $k$ , put

K_{t}(k)=\frac{1-\cos(kt)}{1-\cos t}\quad(t\neq 0\text{ in }\mathbb{T}),\qquad K_{0}(k)=k^{2}.

The value at $0$ is the continuous limit, and the measure in Lemma 2.1 satisfies

g(k)=\int_{\mathbb{T}}K_{t}(k)\,\lambda_{g}(dt).

Consequently, if $g(1)>0$ , then $g(k)/g(1)$ is a probability mixture of the normalized generators $K_{t}(k)$ . If $g(1)=0$ , then $A=0$ and $\nu$ is concentrated, up to a null set, on positive multiples of $2\pi$ ; hence $g(k)=0$ at every integer. In particular, atoms invisible on the integers cannot affect the certificate, and no restriction to a discrete frequency grid is involved.

To use (2.3), the test coefficients must correlate with the second differences of $f$ without adding coherently at any frequency. Alternating coefficients would fail: at $t=\pi$ , every term $(-1)^{k}\cos(kt)$ equals one, and the dual norm is as large as the number of terms. The Rudin–Shapiro construction instead has uniform norm of square-root order. It also has linearly many sign changes, each of which contributes with the same sign to the second-difference pairing. We record both properties, including the endpoint terms needed when $f(0)=0$ .

Set $P_{0}(z)=Q_{0}(z)=1$ and define

	$\displaystyle P_{m+1}(z)$	$\displaystyle=P_{m}(z)+z^{2^{m}}Q_{m}(z),$		(2.4)
	$\displaystyle Q_{m+1}(z)$	$\displaystyle=P_{m}(z)-z^{2^{m}}Q_{m}(z).$		(2.4)

The coefficients of $P_{m}$ are $r_{0},\ldots,r_{2^{m}-1}$ , as in the classical Rudin–Shapiro construction [7]. To verify the identification with (1.5), define

R_{m}(z)=\sum_{k=0}^{2^{m}-1}r_{k}z^{k},\qquad S_{m}(z)=\sum_{k=0}^{2^{m}-1}r_{2^{m}+k}z^{k}.

Prefixing binary words gives $R_{m+1}=R_{m}+z^{2^{m}}S_{m}$ and $S_{m+1}=R_{m}-z^{2^{m}}S_{m}$ . Indeed, the two halves of the word for $S_{m+1}$ are obtained by prefixing an $m$ -bit word by $10$ and $11$ , respectively; the first produces the signs in $R_{m}$ , and the second reverses those in $S_{m}$ . Since $R_{0}=S_{0}=1$ , induction gives $R_{m}=P_{m}$ and $S_{m}=Q_{m}$ .

Lemma 2.4 (Norm and transition counts).

Let $N=2^{m}$ . For every real $t$ ,

|P_{m}(e^{it})|^{2}+|Q_{m}(e^{it})|^{2}=2N,\qquad|P_{m}(e^{it})|\leq\sqrt{2N}.

(2.5)

If $T_{m}$ and $U_{m}$ count adjacent sign transitions in the coefficient words of $P_{m}$ and $Q_{m}$ , then $T_{m}+U_{m}=N-1$ , and for $m\geq 2$ ,

T_{m}=\begin{cases}N/2,&m\text{ odd},\\ N/2-1,&m\text{ even}.\end{cases}

(2.6)

Proof.

For $|z|=1$ , the parallelogram identity in (2.4) yields

|P_{m+1}(z)|^{2}+|Q_{m+1}(z)|^{2}=2\bigl(|P_{m}(z)|^{2}+|Q_{m}(z)|^{2}\bigr).

The initial sum is $2$ , proving (2.5).

At the word level, (2.4) concatenates $(P_{m},Q_{m})$ and $(P_{m},-Q_{m})$ . Exactly one of their two joins is a transition. Thus

T_{m+1}+U_{m+1}=2(T_{m}+U_{m})+1,

and the initial counts are zero, so $T_{m}+U_{m}=2^{m}-1$ . Both words begin with $1$ . In the concatenation forming $P_{m}$ , the left word ends with $r_{2^{m-1}-1}=(-1)^{m-2}$ , since $2^{m-1}-1$ has $m-1$ binary ones. For $m\geq 2$ , this join is therefore a transition exactly when $m$ is odd. Adding the internal transitions gives

T_{m}=T_{m-1}+U_{m-1}+\begin{cases}1,&m\text{ odd},\\ 0,&m\text{ even},\end{cases}

which is (2.6). ∎

The certificate must avoid second differences involving the exceptional value $f(0)=0$ . For $N=2^{m}\geq 4$ , retain only the interior terms:

A_{N}(t)=\sum_{k=2}^{N-2}r_{k}\cos(kt),\qquad\|A_{N}\|_{\infty}\leq\sqrt{2N}+3.

(2.7)

Indeed, it is the real part of $P_{m}(e^{it})$ after deleting the three terms at indices $0,1,N-1$ , each of modulus at most $1$ . On these indices, $Df=Dr$ . Moreover, $-r_{k}Dr(k)$ counts the sign changes on the two edges adjacent to $k$ : a neighboring equal sign contributes zero and a different sign contributes one. Thus the transition count gives a linear pairing, with the following exact boundary correction.

Lemma 2.5 (Exact second-difference pairing).

For $N=2^{m}\geq 16$ ,

\sum_{k=2}^{N-2}r_{k}Df(k)=\begin{cases}-N+1,&m\text{ odd},\\ -N+3,&m\text{ even}.\end{cases}

(2.8)

In particular, the absolute value is at least $N-3$ .

Proof.

Write $b_{k}=r_{k+1}-2r_{k}+r_{k-1}$ and $u_{j}=r_{j}r_{j+1}$ . A transition contributes $-1$ to $u_{j}$ , and a nontransition contributes $1$ , so

\sum_{j=0}^{N-2}u_{j}=N-1-2T_{m}.

The endpoint signs are

r_{0}=r_{1}=r_{2}=1,\qquad r_{N-2}=(-1)^{m-2},\qquad r_{N-1}=(-1)^{m-1}.

Thus $u_{0}=1$ , $u_{N-2}=-1$ , and $b_{1}=0$ . Summing the two neighboring products in $r_{k}b_{k}$ gives

	$\displaystyle\sum_{k=1}^{N-2}r_{k}b_{k}$	$\displaystyle=2\sum_{j=0}^{N-2}u_{j}-u_{0}-u_{N-2}-2(N-2)$
		$\displaystyle=2-4T_{m}.$		(2.9)

By (2.6), this equals $-2N+2$ for odd $m$ and $-2N+6$ for even $m$ . The $k=1$ term may be deleted because $b_{1}=0$ . For $2\leq k\leq N-2$ , all three arguments in the second difference are nonzero, and the constant $2$ in (1.6) cancels. Hence $Df(k)=b_{k}/2$ , and division by $2$ proves (2.8). Excluding $k=1$ is necessary for this last identity: the exceptional value $f(0)=0$ prevents the constant part from cancelling there. ∎

3 Proof of the separation theorem

The certificate now gives the lower bound for any admissible pair. Because the target is bounded by $3$ , relative error $\eta$ changes each second difference by at most $6\eta$ . Its total effect is therefore smaller than the linear pairing whenever $\eta<1/6$ . Only target values inside the prescribed interval are used; after applying the dual inequality, the envelope is needed only at $1$ .

Proposition 3.1 (Dyadic lower bound).

Let $N=2^{m}\geq 16$ , $n=N-1$ , and $0\leq\eta<1/6$ . If $g_{+},g_{-}\in\mathcal{L}_{\mathrm{sym}}$ satisfy

|g_{+}(k)-g_{-}(k)-f(k)|\leq\eta f(k),\qquad g_{+}(k)+g_{-}(k)\leq\rho f(k)\quad(|k|\leq n),

(3.1)

then

\rho\geq\frac{(1-6\eta)(N-3)}{3(\sqrt{2N}+3)}.

(3.2)

At $\eta=1/100$ , this implies

\rho\geq\frac{47(N-3)}{150(\sqrt{2N}+3)}\geq\frac{N}{6(\sqrt{2N}+3)}\geq\frac{\sqrt{N}}{12\sqrt{2}}.

(3.3)

Proof.

Put $h=g_{+}-g_{-}$ , $s=g_{+}+g_{-}$ , and $e=h-f$ . Since $f(j)\leq 3$ , the approximation condition gives $|e(j)|\leq 3\eta$ for $|j|\leq n$ . Therefore, for $2\leq k\leq N-2$ ,

|De(k)|\leq\frac{|e(k+1)|+2|e(k)|+|e(k-1)|}{2}\leq 6\eta.

All three indices lie in $[1,N-1]$ . There are $N-3$ terms in the pairing, so Lemma 2.5 yields

\left|\sum_{k=2}^{N-2}r_{k}Dh(k)\right|\geq(N-3)-6\eta(N-3)=(1-6\eta)(N-3).

(3.4)

Applying Corollary 2.2 with $a_{k}=r_{k}$ for $2\leq k\leq N-2$ and zero elsewhere, and then using (2.7), gives

s(1)\geq\frac{(1-6\eta)(N-3)}{\sqrt{2N}+3}.

On the other hand, $f(1)=3$ , so the cancellation constraint at $1$ gives $s(1)\leq 3\rho$ . This proves (3.2). For $\eta=1/100$ , the first simplification in (3.3) uses $22N\geq 141$ , and the second uses $3\leq\sqrt{2N}$ , both valid for $N\geq 16$ . ∎

Corollary 3.2 (All cutoffs).

For every $n\geq 15$ and $0\leq\eta<1/6$ ,

\rho_{\eta}^{f}(n)>\frac{(1-6\eta)\sqrt{n+1}}{8\sqrt{2}}.

(3.5)

Proof.

Take $N=2^{\lfloor\log_{2}(n+1)\rfloor}$ . Then $N\geq 16$ , $N-1\leq n$ , and $N>(n+1)/2$ . Restricting an admissible pair to $[-N+1,N-1]$ preserves both constraints. Thus Proposition 3.1 implies

\rho_{\eta}^{f}(n)\geq\frac{(1-6\eta)(N-3)}{3(\sqrt{2N}+3)}.

For $N\geq 16$ ,

N-3\geq\frac{13N}{16},\qquad\sqrt{2N}+3\leq\left(\sqrt{2}+\frac{3}{4}\right)\sqrt{N}<\frac{13}{6}\sqrt{N}.

Substitution gives

\rho_{\eta}^{f}(n)>\frac{(1-6\eta)\sqrt{N}}{8}>\frac{(1-6\eta)\sqrt{n+1}}{8\sqrt{2}},

as required. ∎

For the matching upper bound, it suffices to apply the periodic Fourier–Hahn construction [1, 2] on a group of size $2n+1$ . The bounded values of $f$ give a bounded mean-square Fourier norm. Cauchy–Schwarz then loses a factor $\sqrt{2n+1}$ when passing to the absolute Fourier mass, exactly the scale forced by the certificate.

Proposition 3.3.

For every $n\geq 1$ , there are $g_{+},g_{-}\in\mathcal{L}_{\mathrm{sym}}$ such that

g_{+}(k)-g_{-}(k)=f(k),\qquad g_{+}(k)+g_{-}(k)\leq 6\sqrt{2n+1}\,f(k)\quad(|k|\leq n).

Proof.

Put $p=2n+1$ and identify $[-n,n]\cap\mathbb{Z}$ with $\mathbb{Z}/p\mathbb{Z}$ . Let $F$ be the corresponding real even function, with normalized Fourier coefficients

c_{j}=\frac{1}{p}\sum_{x=0}^{p-1}F(x)e^{-2\pi ijx/p},\qquad 0\leq j<p.

Pairing $x$ with $-x$ shows that $c_{j}$ is real. Fourier inversion gives $F(k)=\sum_{j}c_{j}\cos(2\pi jk/p)$ , and $F(0)=0$ implies $\sum_{j}c_{j}=0$ . Hence

F(k)=\sum_{j=0}^{p-1}(-c_{j})\left(1-\cos\frac{2\pi jk}{p}\right).

(3.6)

Define $a_{j}^{+}=\max\{-c_{j},0\}$ , $a_{j}^{-}=\max\{c_{j},0\}$ , and

g_{\pm}(x)=\sum_{j=1}^{p-1}a_{j}^{\pm}\left(1-\cos\frac{2\pi jx}{p}\right),\qquad x\in\mathbb{R}.

Both functions belong to $\mathcal{L}_{\mathrm{sym}}$ , with finite positive atomic jump measures. The omitted $j=0$ term in (3.6) is identically zero, so $g_{+}-g_{-}=f$ on the required integers.

Cauchy–Schwarz and Parseval give

\sum_{j=0}^{p-1}|c_{j}|\leq\sqrt{p}\left(\sum_{j=0}^{p-1}|c_{j}|^{2}\right)^{1/2}=\left(\sum_{x=0}^{p-1}F(x)^{2}\right)^{1/2}\leq 3\sqrt{p}.

Since $0\leq 1-\cos\theta\leq 2$ , the cancellation envelope is at most $2\sum_{j}|c_{j}|\leq 6\sqrt{p}$ . At a nonzero integer in the prescribed range, $f(k)\geq 1$ ; at zero, the target and both exponents vanish. This proves the claimed pointwise bound. ∎

The exact split uses $O(n)$ atoms. It certifies the upper bound on cancellation, but is not the small-space algorithm for the moment. That algorithm recovers a sparse sample of the input coordinates and evaluates their weights directly. We finish by verifying that it works in the bit-space model of (1.3), including the promise on final rather than intermediate frequencies.

Proposition 3.4.

The function $f$ in (1.6) is a fixed computable member of $\mathcal{T}_{\mathrm{even}}^{+}$ .

Proof.

Let $S=\{i:x_{i}\neq 0\}$ , $s=|S|$ , and $F=F_{f}(x)$ . When $s>0$ , $s\leq F\leq 3s$ . If the coordinates are retained with probability $p$ using pairwise independent indicators $B_{i}$ , then

Z=\frac{1}{p}\sum_{i}B_{i}f(x_{i}),\qquad\mathbb{E}Z=F,\qquad\operatorname{Var}Z\leq\frac{9s}{p}.

Thus a sample with expected support size of order $\varepsilon^{-2}$ suffices for a relative estimate with constant success probability. Dyadic subsampling and sparse recovery implement this idea when $s$ is unknown, following the support-sampling framework [5, 6].

For the precise final-frequency model used here, Lemma A.2 supplies a self-contained finite-field implementation, including the selection of a sampling level, recovery errors, and amplification to failure probability $\delta$ . It uses space (1.3) for any weight function taking values in $\{1,2,3\}$ away from zero, provided those values can be evaluated in polylogarithmic space. The value $r_{|k|}$ is obtained by scanning the binary expansion of $|k|$ and recording the parity of the number of adjacent pairs of ones. This requires $O(\log(2U))$ workspace when $|k|\leq U$ . The lemma therefore applies to $f$ , including the zero vector, for which its output is exactly zero. ∎

Proof of Theorem 1.1.

Proposition 3.4 gives $f\in\mathcal{T}_{\mathrm{even}}^{+}$ . Corollaries 3.2 and 3.3, together with the inclusion of exact admissible pairs among approximate ones, give (1.7). For fixed $0<\eta<1/6$ , these bounds are of order $\sqrt{n}$ . If (1.4) held for this $f$ , then at $\eta=1/100$ it would imply $\rho_{1/100}^{f}(n)\leq q_{f}(100,\log(2n))$ , contradicting (3.5) as $n\to\infty$ . ∎

The separation depends on the sign pattern, not on large weights. For comparison, Appendix B constructs controlled splits of $k^{2}\log(1+|k|)$ , an example considered in [2], and more generally of fixed logarithmic powers multiplying $|k|^{p}$ , $0<p\leq 2$ . The first has cancellation cost $O(\varepsilon^{-1}\log n)$ at relative accuracy $\varepsilon$ , despite its slightly superquadratic growth. Together these examples distinguish growth restrictions on a target from the oscillatory obstruction detected by the second-difference certificate.

Appendix A A finite-field support-sampling sketch

This appendix supplies the bit-space guarantee used in Proposition 3.4, without a bound on intermediate frequencies. At each sampling level, a linear summary either recovers the retained frequencies or reports that the sample is too dense. The usual dyadic subsampling strategy [5, 6] then chooses a level with enough retained coordinates for concentration. Finite-field arithmetic removes any dependence on intermediate frequency magnitudes; an independent checksum prevents a dense vector from being mistaken for a sparse one. The decoder below uses polynomial time in the dimension, the sparsity threshold, and the field bit length.

Lemma A.1 (Sparse recovery with a checksum).

Let $d,U,K\geq 1$ be integers, and let $q>\max\{d,2U\}$ be prime. There is a linear turnstile summary over $\mathbb{F}_{q}$ , using $O(K\log q)$ bits, with the following guarantee for any fixed final vector $v\in[-U,U]^{d}\cap\mathbb{Z}^{d}$ . If $v$ has at most $K$ nonzero coordinates, the decoder returns $v$ exactly. Otherwise it returns $\mathsf{dense}$ , except with probability at most $d/q$ . Decoding uses $O(K^{2}\log q)$ workspace and time polynomial in $d,K,\log q$ .

Proof.

Store the $2K$ power sums and one random checksum

M_{t}=\sum_{i=1}^{d}v_{i}i^{t}\pmod{q}\quad(0\leq t<2K),\qquad C_{z}=\sum_{i=1}^{d}v_{i}z^{i}\pmod{q},

(A.1)

where $z$ is uniform in $\mathbb{F}_{q}$ . These quantities are linear in the updates. The seed $z$ , powers, and accumulators fit within $O(K\log q)$ bits.

There is at most one vector $y\in[-U,U]^{d}\cap\mathbb{Z}^{d}$ with at most $K$ nonzero coordinates that matches all the $M_{t}$ . Indeed, the difference of two candidates is supported on some $\ell\leq\min\{2K,d\}$ distinct indices. Its first $\ell$ power sums form a Vandermonde system over $\mathbb{F}_{q}$ , whose determinant is nonzero because the indices are distinct modulo $q$ . Every coordinate of the difference is therefore zero modulo $q$ . Its absolute value is at most $2U<q$ , so the two candidates are equal as integer vectors.

We next describe how to find this candidate, if it exists, without using $z$ or $C_{z}$ . If all power sums are zero, take the zero candidate. Otherwise try each $1\leq r\leq\min\{K,d\}$ . If the Hankel matrix $\mathsf{H}_{r}=(M_{t+j})_{0\leq t,j<r}$ is invertible, solve

\sum_{j=0}^{r-1}c_{j}M_{t+j}=-M_{t+r}\quad(0\leq t<r),\qquad P_{r}(X)=X^{r}+\sum_{j=0}^{r-1}c_{j}X^{j}.

(A.2)

Scan the indices $1,\ldots,d$ for roots of $P_{r}$ . If there are exactly $r$ roots, solve the Vandermonde system on these indices using $M_{0},\ldots,M_{r-1}$ to obtain their candidate values in $\mathbb{F}_{q}$ . Reject this trial if any value has no representative in $[-U,U]$ . Otherwise take those representatives and check all $2K$ power sums. Retain a trial only if every check passes. If no trial passes, there is no candidate found and the decoder returns $\mathsf{dense}$ .

To see that this procedure finds every valid sparse candidate, suppose $y$ has support $i_{1},\ldots,i_{r}$ and matches the power sums. Let $V_{t,a}=i_{a}^{t}$ for $0\leq t<r$ . Then

\mathsf{H}_{r}=V\operatorname{diag}(y_{i_{1}},\ldots,y_{i_{r}})V^{\mathsf{T}}

is invertible over $\mathbb{F}_{q}$ : the indices are distinct, and the nonzero values of $y$ remain nonzero modulo $q$ . The polynomial $\prod_{a=1}^{r}(X-i_{a})$ satisfies (A.2), so it is precisely the polynomial found at this trial. Its roots and values therefore recover $y$ . The zero candidate was handled separately, and uniqueness shows that two successful trials cannot produce different vectors.

Finally, return the candidate $y$ only if it also matches $C_{z}$ , and return $\mathsf{dense}$ otherwise. For a $K$ -sparse $v$ , the candidate is $v$ and always passes. If $v$ is not $K$ -sparse, any candidate $y$ differs from $v$ and is determined independently of $z$ . The polynomial

\sum_{i=1}^{d}(v_{i}-y_{i})Z^{i}\in\mathbb{F}_{q}[Z]

is nonzero and has degree at most $d$ . It has at most $d$ roots, so the probability of false acceptance is at most $d/q$ .

The linear systems have dimension at most $K$ , and a candidate uses at most $K$ index-value pairs. Gaussian elimination, the scans over indices, and the checks therefore use $O(K^{2}\log q)$ workspace and polynomial time in the stated parameters. All stored summaries are reduced modulo $q$ after each update. Since the final coordinates lie in $[-U,U]$ , arbitrary intermediate integer values do not affect the argument. ∎

We apply this recovery primitive at nested sampling levels. The level is selected from the sketch itself, so it is not enough to establish accuracy at one fixed level. The proof bounds the total probability of an inaccurate estimate over all levels that could be selected.

Lemma A.2 (Bounded-weight moments).

Let $w:\mathbb{Z}\to\{0,1,2,3\}$ satisfy $w(0)=0$ and $1\leq w(k)\leq 3$ for $k\neq 0$ . Suppose that $w(k)$ can be evaluated in space polynomial in $\log(2+|k|)$ . Then $\sum_{i}w(x_{i})$ has a one-pass turnstile sketch with the space and success guarantees in (1.3), under the promise $\|x\|_{\infty}\leq U$ on the final vector alone.

Proof.

We first construct one copy with success probability at least $3/4$ . Set

K=\left\lceil 2048\varepsilon^{-2}\right\rceil,\qquad J=\lceil\log_{2}d\rceil,\qquad\ell=\lceil\log_{2}(d+1)\rceil.

Choose a prime

B<q\leq 2B,\qquad B=\max\{2U,64d(J+1)\}.

(A.3)

Such a prime exists by Bertrand’s postulate, and may be found by trial division in $O(\log B)$ space. In particular, $\log q=O(\log(2d)+\log(2U))$ .

Let $\iota(i)\in\mathbb{F}_{2}^{\ell}$ be the length- $\ell$ binary representation of $i$ . Choose a uniform matrix $H\in\mathbb{F}_{2}^{J\times\ell}$ and a uniform vector $b\in\mathbb{F}_{2}^{J}$ , independently, and put $h(i)=H\iota(i)+b$ . For distinct indices the hash values are independent and uniform: the difference $H(\iota(i)-\iota(i^{\prime}))$ is uniform in $\mathbb{F}_{2}^{J}$ , while $b$ independently makes either hash value uniform. At level $0\leq j\leq J$ , retain $i$ when the first $j$ bits of $h(i)$ are zero. The indicators $B_{i}^{(j)}$ are pairwise independent at each level, with retention probability $p_{j}=2^{-j}$ . Level zero retains every coordinate.

At each level maintain the summary in Lemma A.1 for the sampled vector $v_{i}^{(j)}=B_{i}^{(j)}x_{i}$ , using independent checksums and the same prime $q$ . All checksum seeds are independent of the hashing. At the end, decode the summaries and select the smallest level whose decoder does not return $\mathsf{dense}$ . If this level is $j$ , let $\widehat{v}^{(j)}$ be its recovered candidate and output

\widehat{F}=2^{j}\sum_{i}w(\widehat{v}_{i}^{(j)}),

(A.4)

summing over its recovered support. If every decoder returns $\mathsf{dense}$ , output zero. Each update can be processed by testing its index at every level and adding its contribution modulo $q$ . Even an arbitrarily long binary encoding of $\Delta$ can be reduced modulo $q$ as it is read, using $O(\log q)$ workspace.

Fix the stream, let $s=|\{i:x_{i}\neq 0\}|$ , and put $F=\sum_{i}w(x_{i})$ . Conditioned on the hash function, the sampled vectors are fixed, and Lemma A.1 applies independently of that conditioning. A union bound gives probability at most

(J+1)d/q<1/64

(A.5)

that any nonsparse sampled vector is falsely accepted. If $s\leq K$ , level zero always recovers the full vector, so the estimate is exact, including when $s=0$ .

Suppose now that $s>K$ , and define

j_{*}=\left\lceil\log_{2}(2s/K)\right\rceil.

Then $1\leq j_{*}\leq J$ and $K/4<p_{j_{*}}s\leq K/2$ . Write $S_{j}=\sum_{i:x_{i}\neq 0}B_{i}^{(j)}$ for the sampled support size. Pairwise independence gives $\operatorname{Var}S_{j_{*}}\leq p_{j_{*}}s$ . Chebyshev’s inequality therefore yields

\Pr(S_{j_{*}}>K)\leq\frac{p_{j_{*}}s}{(K-p_{j_{*}}s)^{2}}\leq\frac{2}{K}.

(A.6)

For each $0\leq j\leq j_{*}$ , consider the estimator on the true sampled vector,

Z_{j}=p_{j}^{-1}\sum_{i}B_{i}^{(j)}w(x_{i}).

It satisfies $\mathbb{E}Z_{j}=F$ , $F\geq s$ , and $\operatorname{Var}Z_{j}\leq 9s/p_{j}$ . Hence

\Pr(|Z_{j}-F|>\varepsilon F)\leq\frac{9}{\varepsilon^{2}p_{j}s}.

No independence between levels is required. Summing these failure probabilities gives

\Pr\bigl(\exists j\leq j_{*}:\ |Z_{j}-F|>\varepsilon F\bigr)\leq\frac{9}{\varepsilon^{2}s}\sum_{j=0}^{j_{*}}2^{j}<\frac{18}{\varepsilon^{2}p_{j_{*}}s}<\frac{72}{\varepsilon^{2}K}.

(A.7)

If none of the bad events bounded in (A.5)–(A.7) occurs, then level $j_{*}$ is recoverable, the selected level is at most $j_{*}$ , and its recovered vector is correct. The output is therefore within $(1\pm\varepsilon)F$ . The total failure probability is less than

\frac{1}{64}+\frac{2}{K}+\frac{72}{\varepsilon^{2}K}<\frac{1}{4}.

Choose $R$ to be the smallest odd integer at least $8\log(1/\delta)$ . Run $R$ independent copies and return their median. The probability that at least half the copies fail is at most $e^{-R/8}\leq\delta$ , by Hoeffding’s inequality applied to their failure indicators. The hash seed uses $O(J\ell)$ bits, and the summaries of one copy use $O((J+1)K\log q)$ bits. Sequential decoding uses an additional $O(K^{2}\log q)$ workspace, and evaluating $w$ requires the polynomial in $\log(2U)$ from the hypothesis. Storing the $R$ outputs for their median also fits within (1.3). This proves the stated space bound and success probability. ∎

Appendix B Controlled decompositions for logarithmic moments

The logarithm can be approximated by a small difference of powers: for small $\alpha$ , $\alpha^{-1}(1-e^{-\alpha y})$ approximates $y$ . Multiplying this identity by $x^{2}$ suggests a split of $x^{2}\log(1+|x|)$ into a Gaussian exponent and a damped quadratic. The point requiring verification is that the damped term is itself a Lévy exponent. Bernstein-function calculus establishes this and also permits higher finite differences for fixed powers of the logarithm.

Recall that a Bernstein function $\phi$ is a nonnegative smooth function on $(0,\infty)$ with completely monotone derivative, meaning $(-1)^{j}\phi^{(j+1)}(t)\geq 0$ for all integers $j\geq 0$ . When $\phi(0)=0$ , its representation has the form

\phi(t)=bt+\int_{0}^{\infty}(1-e^{-ut})\,\mu(du),\qquad b\geq 0,\qquad\int_{0}^{\infty}\min\{u,1\}\,\mu(du)<\infty.

(B.1)

Here $\mu$ is a positive measure on $(0,\infty)$ . A complete Bernstein function is a Bernstein function whose measure $\mu$ has a completely monotone density. We use the equivalent analytic characterization: a nonnegative function on $(0,\infty)$ with a finite nonnegative limit at zero is a complete Bernstein function if it extends holomorphically to $\mathbb{C}\setminus(-\infty,0]$ and has nonnegative imaginary part in the upper half-plane [8, Chapters 3 and 6].

For completeness, (B.1) explains why $x\mapsto\phi(x^{2})$ belongs to $\mathcal{L}_{\mathrm{sym}}$ . For $u>0$ , the Gaussian characteristic-function identity gives

1-e^{-ux^{2}}=\int_{0}^{\infty}(1-\cos(xs))\frac{e^{-s^{2}/(4u)}}{\sqrt{\pi u}}\,ds.

The density in this integral has mass $1$ and second moment $2u$ , so its integral against $\min\{s^{2},1\}$ is at most $\min\{2u,1\}\leq 2\min\{u,1\}$ . Integrating against $\mu$ and applying Tonelli’s theorem gives the integrability condition in (1.1), with Gaussian coefficient $b$ . Thus

\phi(0)=0,\quad\phi\text{ Bernstein}\quad\Longrightarrow\quad\phi(x^{2})\in\mathcal{L}_{\mathrm{sym}}.

(B.2)

Lemma B.1 (A complete Bernstein kernel).

Let $0<a,b\leq 1$ and $c\geq 0$ satisfy $bc\leq a$ . Then

\phi_{a,b,c}(t)=\frac{t^{a}}{(1+t^{b})^{c}},\qquad t\geq 0,

is a complete Bernstein function vanishing at zero.

Proof.

Use principal branches on $\mathbb{C}\setminus(-\infty,0]$ . If $z=re^{i\theta}$ , with $0<\theta<\pi$ , then

0<\arg(1+z^{b})<b\theta.

Indeed, $1+z^{b}$ lies strictly inside the sector between the positive real axis and $z^{b}$ . It neither vanishes nor meets the negative real axis. Conjugation gives the corresponding statement in the lower half-plane, and the denominator is positive on the positive real axis. The quotient is therefore holomorphic on the slit plane.

The argument of the quotient is $a\theta-c\arg(1+z^{b})$ . If $c>0$ , it is strictly greater than $(a-bc)\theta\geq 0$ and at most $a\theta<\pi$ . If $c=0$ , it equals $a\theta\in(0,\pi)$ . Thus the quotient maps the upper half-plane into itself. It is nonnegative on $(0,\infty)$ and tends to zero as $t\downarrow 0$ . The preceding characterization proves the claim. ∎

Proposition B.2 (A single logarithm).

Let $F(k)=k^{2}\log(1+|k|)$ , $n\geq 2$ , and $0<\varepsilon<1/2$ . Set $\alpha=2\varepsilon/\log(1+n)$ . Then

G_{+}(x)=\alpha^{-1}x^{2},\qquad G_{-}(x)=\alpha^{-1}\frac{x^{2}}{(1+|x|)^{\alpha}}

belong to $\mathcal{L}_{\mathrm{sym}}$ , and for every integer $|k|\leq n$ ,

	$\displaystyle(1-\varepsilon)F(k)$	$\displaystyle\leq G_{+}(k)-G_{-}(k)\leq F(k),$		(B.3)
	$\displaystyle G_{+}(k)+G_{-}(k)$	$\displaystyle\leq\frac{\log(1+n)}{\varepsilon\log 2}\,F(k).$		(B.4)

Proof.

The parameter satisfies $0<\alpha<2$ . Applying Lemma B.1 with $(a,b,c)=(1,1/2,\alpha)$ shows that $t(1+\sqrt{t})^{-\alpha}$ is a Bernstein function vanishing at zero. Equation (B.2) therefore proves $G_{-}\in\mathcal{L}_{\mathrm{sym}}$ , and $G_{+}\in\mathcal{L}_{\mathrm{sym}}$ is a Gaussian exponent.

For $k\neq 0$ , put $y=\alpha\log(1+|k|)$ . Then $0<y\leq 2\varepsilon$ and

\frac{G_{+}(k)-G_{-}(k)}{F(k)}=\frac{1-e^{-y}}{y}.

The identity $(1-e^{-y})/y=\int_{0}^{1}e^{-ty}\,dt$ , together with $1-ty\leq e^{-ty}\leq 1$ , gives

1-y/2\leq\frac{1-e^{-y}}{y}\leq 1.

(B.5)

This proves (B.3). Also,

G_{+}(k)+G_{-}(k)\leq 2\alpha^{-1}k^{2}\leq\frac{2}{\alpha\log 2}\,F(k),

which is (B.4). At zero, all the functions vanish. ∎

Proposition B.3 (Fixed logarithmic powers).

Fix $0<p,\beta\leq 2$ and an integer $m\geq 1$ . For every $n\geq 2$ and $0<\varepsilon<1/2$ , the function

F_{p,\beta,m}(k)=|k|^{p}\bigl[\log(1+|k|^{\beta})\bigr]^{m}

admits a relative $(1-\varepsilon,1)$ approximation on $[-n,n]\cap\mathbb{Z}$ by a difference of two elements of $\mathcal{L}_{\mathrm{sym}}$ , with cancellation cost

O_{p,\beta,m}\bigl((\varepsilon^{-1}\log n)^{m}\bigr).

Proof.

Set

a=p/2,\qquad b=\beta/2,\qquad\alpha=\min\left\{\frac{2\varepsilon}{m\log(1+n^{\beta})},\frac{p}{m\beta}\right\}.

For every $0\leq j\leq m$ , we have $bj\alpha\leq a$ . By Lemma B.1 and (B.2),

H_{j}(x)=|x|^{p}(1+|x|^{\beta})^{-j\alpha}

belongs to $\mathcal{L}_{\mathrm{sym}}$ . Define the positive and negative parts of the finite difference explicitly by

G_{+}(x)=\alpha^{-m}\sum_{\begin{subarray}{c}0\leq j\leq m\\ j\ \mathrm{even}\end{subarray}}\binom{m}{j}H_{j}(x),\qquad G_{-}(x)=\alpha^{-m}\sum_{\begin{subarray}{c}0\leq j\leq m\\ j\ \mathrm{odd}\end{subarray}}\binom{m}{j}H_{j}(x).

(B.6)

Both functions belong to $\mathcal{L}_{\mathrm{sym}}$ .

For $k\neq 0$ , put $y=\alpha\log(1+|k|^{\beta})$ . The binomial theorem gives

G_{+}(k)-G_{-}(k)=|k|^{p}\alpha^{-m}(1-e^{-y})^{m},

so the ratio to $F_{p,\beta,m}(k)$ equals $\bigl((1-e^{-y})/y\bigr)^{m}$ . Since $0<y\leq 2\varepsilon/m$ , (B.5) and Bernoulli’s inequality imply

1-\varepsilon\leq 1-\frac{my}{2}\leq(1-y/2)^{m}\leq\left(\frac{1-e^{-y}}{y}\right)^{m}\leq 1.

For the cancellation envelope, $H_{j}(k)\leq|k|^{p}$ yields

G_{+}(k)+G_{-}(k)\leq 2^{m}\alpha^{-m}|k|^{p}.

At nonzero integers, $\log(1+|k|^{\beta})\geq\log 2$ , and hence

\frac{G_{+}(k)+G_{-}(k)}{F_{p,\beta,m}(k)}\leq\left(\frac{2}{\log 2}\right)^{m}\alpha^{-m}.

Finally,

\alpha^{-1}=\max\left\{\frac{m\log(1+n^{\beta})}{2\varepsilon},\frac{m\beta}{p}\right\}=O_{p,\beta,m}(\varepsilon^{-1}\log n).

At zero, the target and both functions in (B.6) vanish. This proves both assertions. ∎

References

[1] S. Pettie and D. Wang, Sketching, moment estimation, and the Lévy–Khintchine representation theorem, in 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), LIPIcs 325, 77:1–77:23, 2025. doi:10.4230/LIPIcs.ITCS.2025.77.
[2] S. Pettie and D. Wang, A unified construction of streaming sketches via the Lévy–Khintchine representation theorem, arXiv:2410.17426v4, 5 April 2026. Expanded manuscript incorporating the ITCS 2025 paper [1] and Universal Perfect Samplers for Incremental Streams (SODA 2025).
[3] D. Wang, Harmonic decomposition in data sketches, in Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), 383–394, 2025. doi:10.1145/3717823.3718321. Author version: arXiv:2403.15366v3, 2024.
[4] V. Braverman, S. R. Chestnut, D. P. Woodruff, and L. F. Yang, Streaming space complexity of nearly all functions of one variable on frequency vectors, in Proceedings of the 35th ACM SIGMOD–SIGACT–SIGAI Symposium on Principles of Database Systems (PODS 2016), 261–276, 2016. doi:10.1145/2902251.2902282.
[5] H. Jowhari, M. Sağlam, and G. Tardos, Tight bounds for $L_{p}$ samplers, finding duplicates in streams, and related problems, in Proceedings of the 30th ACM SIGMOD–SIGACT–SIGART Symposium on Principles of Database Systems (PODS 2011), 49–58, 2011. doi:10.1145/1989284.1989289.
[6] G. Cormode and D. Firmani, A unifying framework for $L_{0}$ -sampling algorithms, Distributed and Parallel Databases 32(3) (2014), 315–335. doi:10.1007/s10619-013-7131-9.
[7] J. Brillhart, On the Rudin–Shapiro polynomials, Duke Mathematical Journal 40(2) (1973), 335–353.
[8] R. L. Schilling, R. Song, and Z. Vondraček, Bernstein Functions: Theory and Applications, second revised and extended edition, De Gruyter Studies in Mathematics 37, De Gruyter, 2012. doi:10.1515/9783110269338.

A tractable streaming moment with square-root cancellation cost in symmetric Lévy decompositions

Abstract

1 Introduction

1.1 Model and separation theorem

Theorem 1.1.

2 Second differences and the Rudin–Shapiro certificate

Lemma 2.1 (Positive second-difference measure).

Proof.

Corollary 2.2 (Dual inequality).

Proof.

Remark 2.3.

Lemma 2.4 (Norm and transition counts).

Proof.

Lemma 2.5 (Exact second-difference pairing).

Proof.

3 Proof of the separation theorem

Proposition 3.1 (Dyadic lower bound).

Proof.

Corollary 3.2 (All cutoffs).

Proof.

Proposition 3.3.

Proof.

Proposition 3.4.

Proof.

Proof of Theorem 1.1.

Appendix A A finite-field support-sampling sketch

Lemma A.1 (Sparse recovery with a checksum).

Proof.

Lemma A.2 (Bounded-weight moments).

Proof.

Appendix B Controlled decompositions for logarithmic moments

Lemma B.1 (A complete Bernstein kernel).

Proof.

Proposition B.2 (A single logarithm).

Proof.

Proposition B.3 (Fixed logarithmic powers).

Proof.

References

A tractable streaming moment with square-root cancellation cost
in symmetric Lévy decompositions