# On the geometry of the multiplier space of $\ell_{A}^{p}$

Raymond Cheng  Department of Mathematics and Statistics, Old Dominion
University, Norfolk, VA 23529, USA<EMAIL_ADDRESS>and  Christopher Felder
Department of Mathematics and Statistics, Washington University in St. Louis,
St. Louis, MO 63130, USA<EMAIL_ADDRESS>
###### Abstract.

For $p\in(1,\infty)\setminus\\{2\\}$, some properties of the space
$\mathscr{M}_{p}$ of multipliers on $\ell^{p}_{A}$ are derived. In particular,
the failure of the weak parallelogram laws and the Pythagorean inequalities is
demonstrated for $\mathscr{M}_{p}$. It is also shown that the extremal
multipliers on the $\ell^{p}_{A}$ spaces are exactly the monomials, in stark
contrast to the $p=2$ case.

###### 2020 Mathematics Subject Classification:

Primary 46E15; Secondary 30J99, 30H99.

##  1\. Introduction

Sequence spaces play an important role in functional analysis, providing a
rich source of examples, a fertile ground for generating conjectures, and a
supply of applicable tools. Indeed the theory of Banach spaces arose from
early studies of the sequence space $\ell^{p}$. The case $\ell^{1}$ is
connected to the Wiener Algebra, and its additional structure has made deeper
inroads possible. The case of $\ell^{2}$ is particularly well understood,
being isometrically isomorphic to the Hardy space $H^{2}$ on the open unit
disk $\mathbb{D}$. In this situation, the interplay between the analytical
properties of the functions and the behavior of the space has given rise to a
deep and extensive body of results, one of the great triumphs of the past
century of mathematical analysis.

By contrast, when $p\neq 1$ and $p\neq 2$, relatively little is known about
the space $\ell^{p}_{A}$, the space of analytic functions on $\mathbb{D}$ for
which the corresponding Maclaurin coefficients are $p$-summable. For
$1<p<\infty$, there is a notion of a $p$-inner function, in terms of which the
zero sets of $\ell^{p}_{A}$ can be described [14]. Unlike $H^{2}$, however,
the analogous inner-outer factorization can fail when $p\neq 2$ [10]. Whereas
the multiplier algebra of $H^{2}$ is the familiar space $H^{\infty}$, the
multipliers on $\ell^{p}_{A}$ have not been completely characterized.

In this paper we obtain some geometric properties of the multiplier space of
$\ell^{p}_{A}$. These include the failure of the weak parallelogram laws and
the Pythagorean inequalities. In addition, we show that when $1<p<\infty$ and
$p\neq 2$, the extremal multipliers on $\ell^{p}_{A}$ are exactly the
monomials. That is, the operator norm of a multiplier $\varphi$ on
$\ell^{p}_{A}$ coincides with its norm in $\ell^{p}_{A}$ precisely if it is of
the form

$\varphi(z)=\gamma z^{k}$

for some $\gamma\in\mathbb{C}$ and nonnegative integer $k$. Again, this is
quite distinct from the $p=2$ case, in which the extremal multipliers consist
of the constant multiples of inner functions.

##  2\. The space $\ell^{p}_{A}$

For $1\leqslant p\leqslant\infty$, the space $\ell^{p}_{A}$ is defined to be
collection of analytic functions on the open unit disk $\mathbb{D}$ of the
complex plane for which the Maclaurin coefficients are $p$-summable. (The
definition makes sense when $0<p<1$, but our attention will be limited to the
range $1\leqslant p\leqslant\infty$.) This function space is endowed with the
norm that it inherits from the sequence space $\ell^{p}$. Thus let us write

$\|f\|_{p}=\|(a_{k})_{k=0}^{\infty}\|_{\ell^{p}}$

for

$f(z)=\sum_{k=0}^{\infty}a_{k}z^{k}$

belonging to $\ell^{p}_{A}$. We stress that $\|\cdot\|_{p}$ refers to the norm
on $\ell^{p}_{A}$, and not the norm on $H^{p}$, or some other function space.

The following property is elementary, and will be essential for identifying
the extremal multipliers on $\ell^{p}_{A}$ (for a proof, see [16, Proposition
1.5.2]).

######  Proposition 2.1.

If $1\leqslant p_{1}<p_{2}\leqslant\infty$, then
$\ell^{p_{1}}_{A}\subseteq\ell^{p_{2}}_{A}$, and
$\|f\|_{p_{2}}\leqslant\|f\|_{p_{1}}$ for all $f\in\ell^{p_{1}}_{A}$.
Furthermore, $\|f\|_{p_{2}}=\|f\|_{p_{1}}$ holds if and only if

$f(z)=\gamma z^{k}$

for some $\gamma\in\mathbb{C}$ and nonnegative integer $k$.

Throughout this paper, if $1\leqslant p\leqslant\infty$, then $p^{\prime}$
will be the Hölder conjugate to $p$, that is, $1/p+1/p^{\prime}=1$ holds. We
recall that for $1\leqslant p<\infty$, the dual space of $\ell^{p}_{A}$ can be
identified with $\ell^{p^{\prime}}_{A}$, under the pairing

$\langle f,g\rangle=\sum_{k=0}^{\infty}f_{k}g_{k},$

where $f(z)=\sum_{k=0}^{\infty}f_{k}z^{k}$ and
$g(z)=\sum_{k=0}^{\infty}g_{k}z^{k}$ (except that complex conjugates are taken
of the coefficients $g_{k}$ when $p=2$).

For further exploration of $\ell^{p}_{A}$, we refer to the paper [12] or the
book [16].

##  3\. Orthogonality

There is a natural way to define “inner function” in the context of
$\ell^{p}_{A}$, that makes use of a notion of orthogonality in general normed
linear spaces.

Let $\mathbf{x}$ and $\mathbf{y}$ be vectors belonging to a normed linear
space $\mathcal{X}$. We say that $\mathbf{x}$ is orthogonal to $\mathbf{y}$ in
the Birkhoff-James sense [2, 24] if

(3.1)
$\|\mathbf{x}+\beta\mathbf{y}\|_{\mathcal{X}}\geqslant\|\mathbf{x}\|_{\mathcal{X}}$

for all scalars $\beta$, and in this case we write
$\mathbf{x}\perp_{\mathcal{X}}\mathbf{y}$.

Birkhoff-James orthogonality extends the concept of orthogonality from an
inner product space to normed spaces. There are other ways to generalize
orthogonality, but this approach is particularly fruitful since it is
connected to an extremal condition via (3.1).

It is straightforward to check that if $\mathcal{X}$ is a Hilbert space, then
the usual orthogonality relation $\mathbf{x}\perp\mathbf{y}$ is equivalent to
$\mathbf{x}\perp_{\mathcal{X}}\mathbf{y}$. More typically, however, the
relation $\perp_{\mathcal{X}}$ is neither symmetric nor linear. When
$\mathcal{X}=\ell^{p}_{A}$, let us write $\perp_{p}$ instead of
$\perp_{\ell^{p}_{A}}$.

There is an analytical criterion for the relation $\perp_{p}$ when
$p\in(1,\infty)$.

######  Theorem 3.2 (James [24]).

Suppose that $1<p<\infty$. Then for $f(z)=\sum_{k=0}^{\infty}f_{k}z^{k}$ and
$g(z)=\sum_{k=0}^{\infty}g_{k}z^{k}$ belonging to $\ell^{p}_{A}$ we have

(3.3)
${f}\perp_{p}{g}\iff\sum_{k=0}^{\infty}|f_{k}|^{p-2}\overline{f}_{k}g_{k}=0,$

where any incidence of “$|0|^{p-2}0$” in the above sum is interpreted as zero.

In light of (3.3) we define, for a complex number $\alpha=re^{i\theta}$, and
any $s>0$, the quantity

(3.4) $\alpha^{\langle s\rangle}=(re^{i\theta})^{\langle
s\rangle}:=r^{s}e^{-i\theta}.$

It is readily seen that for any complex numbers $\alpha$ and $\beta$, exponent
$s>0$, and integer $n\geqslant 0$, we have

$\displaystyle(\alpha\beta)^{\langle s\rangle}$ $\displaystyle=\alpha^{\langle
s\rangle}\beta^{\langle s\rangle}$ $\displaystyle|\alpha^{\langle s\rangle}|$
$\displaystyle=|\alpha|^{s}$ $\displaystyle\alpha^{\langle s\rangle}\alpha$
$\displaystyle=|\alpha|^{s+1}$ $\displaystyle(\alpha^{\langle s\rangle})^{n}$
$\displaystyle=(\alpha^{n})^{\langle s\rangle}$ $\displaystyle(\alpha^{\langle
p-1\rangle})^{\langle p^{\prime}-1\rangle}$ $\displaystyle=\alpha.$

Further to the notation (3.4), for $f(z)=\sum_{k=0}^{\infty}f_{k}z^{k}$, let
us write

(3.5) $f^{\langle s\rangle}(z):=\sum_{k=0}^{\infty}f_{k}^{\langle
s\rangle}z^{k}$

for any $s>0$. By comparing with the case $p=2$, we can think of taking the
${\langle s\rangle}$ power as generalizing complex conjugation.

If $f\in\ell^{p}_{A}$, it is easy to verify that $f^{\langle
p-1\rangle}\in\ell^{p^{\prime}}$. Thus from (3.3) we get

(3.6) $f\perp_{p}g\iff\langle g,f^{\langle p-1\rangle}\rangle=0.$

Consequently the relation $\perp_{p}$ is linear in its second argument, when
$p\in(1,\infty)$, and it then makes sense to speak of a vector being
orthogonal to a subspace of $\ell^{p}_{A}$. In particular, if $f\perp_{p}g$
for all $g$ belonging to a subspace $\mathscr{X}$ of $\ell^{p}_{A}$, then

$\|f+g\|_{p}\geqslant\|f\|_{p}$

for all $g\in\mathscr{X}$. That is, $f$ solves an extremal problem in relation
to the subspace $\mathscr{M}$.

Direct calculation will also confirm that

$\langle f,f^{\langle p-1\rangle}\rangle=\|f\|^{p}_{p}.$

With this concept of orthogonality established, we may now define what it
means for a function in $\ell^{p}_{A}$ to be inner in a related sense.

######  Definition 3.7.

Let $1<p<\infty$. A function $f\in\ell^{p}_{A}$ is said to be $p$-inner if it
is not identically zero and it satisfies

$f(z)\ \,\perp_{p}\ \,z^{k}f(z)$

for all positive integers $k$.

That is, $f$ is nontrivially orthogonal to all of its forward shifts. Apart
from a harmless multiplicative constant, this definition is equivalent to the
traditional meaning of “inner” when $p=2$. Furthermore, this approach to
defining an inner property is consistent with that taken in other function
spaces [1, 3, 15, 17, 20, 21, 22, 31, 32].

Birkhoff-James Orthogonality also plays a role when we examine a version of
the Pythagorean theorem for normed spaces in Section 5.

##  4\. Multipliers on $\ell^{p}_{A}$

An analytic function $\varphi$ on $\mathbb{D}$ is said to be a multiplier of
$\ell_{A}^{p}$ if

$f\in\ell^{p}_{A}\implies\varphi f\in\ell^{p}_{A}.$

The set of multipliers of $\ell^{p}_{A}$ will be denoted by $\mathscr{M}_{p}$.

For $\varphi\in\mathscr{M}_{p}$, an application of the closed graph theorem
shows that the linear mapping

$M_{\varphi}:\ell^{p}_{A}\to\ell^{p}_{A},\quad M_{\varphi}f=\varphi f$

is continuous. Thus we can define the multiplier norm of $\varphi$ by

$\|\varphi\|_{\mathscr{M}_{p}}:=\sup\\{\|\varphi
f\|_{p}:f\in\ell^{p}_{A},\|f\|_{p}\leqslant 1\\}.$

In other words, the multiplier norm of $\varphi$ coincides with the operator
norm of $M_{\varphi}$ on $\ell^{p}_{A}$. Henceforth we identify the
multiplication operator $M_{\varphi}$ with its symbol $\varphi$.

Relatively little is known about the multipliers on $\ell^{p}_{A}$, except
when $p=1$ or $p=2$. In the former case, we know that
$\mathscr{M}_{1}=\ell^{1}_{A}$, and in the latter,
$\mathscr{M}_{2}=H^{\infty}$. We will accordingly concentrate our efforts on
the range $1<p<\infty$, with $p\neq 2$.

The following basic results have been established in the literature.

######  Proposition 4.1.

Let $1<p<\infty$. If $\varphi\in\mathscr{M}_{p}$, then $\varphi\in
H^{\infty}\cap\ell^{p}_{A}\cap\ell^{p^{\prime}}_{A}$, and
$\mathscr{M}_{p}=\mathscr{M}_{p^{\prime}}$, with
$\|\varphi\|_{\mathscr{M}_{p}}=\|\varphi\|_{\mathscr{M}_{p^{\prime}}}$.

######  Proposition 4.2.

Let $1<p<\infty$. If
$\varphi(z)=\sum_{k=0}^{\infty}\varphi_{k}z^{k}\in\mathscr{M}_{p}$, then
$\|\varphi\|_{p}\leqslant\|\varphi\|_{\mathscr{M}_{p}}\leqslant\|\varphi\|_{1}$
(with $\|\varphi\|_{1}=\infty$ being possible), and

$|\varphi_{0}|+|\varphi_{1}|+\cdots+|\varphi_{n}|\leqslant\|\varphi\|_{\mathscr{M}_{p}}(n+1)^{1/p^{\prime}}.$

If all of the coefficients of $\varphi$ are nonnegative, then
$\varphi\in\ell^{1}_{A}$, and $\|\varphi\|_{1}=\|\varphi\|_{\mathscr{M}_{p}}$.

Define the difference quotient mapping $Q_{w}$ by

$Q_{w}f(z):=\frac{f(z)-f(w)}{z-w}$

for any $w\in\mathbb{D}$ and analytic function $f$ on $\mathbb{D}$.

Difference quotients are (bounded) operators on $\mathscr{M}_{p}$. In fact,
for any multiplier $\varphi$ on $\ell^{p}_{A}$, and $w\in\mathbb{D}$,

$\|Q_{w}\varphi\|_{\mathscr{M}_{p}}\leqslant\frac{1}{1-|w|}(\|\varphi\|_{\mathscr{M}_{p}}+\varphi(w)).$

For proofs of these multiplier properties, see [16, Chapter 12], which has
references to original sources.

To extract some geometric information about $\mathscr{M}_{p}$, we will rely on
the following observation.

######  Corollary 4.3.

For any complex numbers $\alpha$ and $\beta$, the multiplier
$\varphi(z)=\alpha+\beta z$ satisfies

$\|\varphi\|_{\mathscr{M}_{p}}=\|\varphi\|_{1}=|\alpha|+|\beta|.$

###### Proof.

The claim is trivial if $\alpha=0$ or $\beta=0$. Otherwise, the mapping

$f(z)\longmapsto
f\Big{(}\frac{\alpha\bar{\beta}}{|\alpha\bar{\beta}|}z\Big{)}$

determines a linear isometry on $\ell^{p}_{A}$ (in fact it is unitary).

Consequently, the multiplier $\varphi$ has the same norm as the multiplier

$\varphi\Big{(}\frac{\alpha\bar{\beta}}{|\alpha\bar{\beta}|}z\Big{)}=\frac{1}{\bar{\alpha}}\Bigg{(}|\alpha|^{2}+\beta\bar{\alpha}\Big{(}\frac{\alpha\bar{\beta}}{|\alpha\bar{\beta}|}z\Big{)}\Bigg{)}=\frac{1}{\bar{\alpha}}\big{(}|\alpha|^{2}+|\beta\bar{\alpha}|z\big{)},$

which is $|\alpha|+|\beta|$, according to the last part of Proposition 4.2. ∎

Already this delivers some information about the geometry of
$\mathscr{M}_{p}$.

######  Corollary 4.4.

If $1<p<\infty$, then $\mathscr{M}_{p}$ fails to be strictly convex.

###### Proof.

The unit ball in $\mathscr{M}_{p}$ contains the segment $t+(1-t)z$ for
$0\leqslant t\leqslant 1$. ∎

It is known that certain Blaschke products are multipliers of $\ell^{p}_{A}$
(e.g., if the zeros converge to the boundary rapidly enough), and that certain
other classes of functions are multipliers. However, there does not yet exist
a complete characterization of $\mathscr{M}_{p}$ in terms of the coefficients,
or of the boundary function. Our sources on the subject include [19, 23, 25,
26, 27, 28, 29, 30, 33, 34, 35], along with the survey paper [12].

##  5\. The geometry of $\mathscr{M}_{p}$

It is well known that when $1<p<\infty$, the spaces $\ell^{p}$ (and hence also
$\ell^{p}_{A}$) are uniformly convex and uniformly smooth. In fact, more can
be said. A normed space $\mathscr{X}$ is said to satisfy the Lower Weak
Parallelogram property (LWP) with constant $C>0$ and exponent $r>1$, if

$\|x+y\|^{r}_{\mathscr{X}}+C\|x-y\|^{r}_{\mathscr{X}}\leqslant
2^{r-1}(\|x\|_{\mathscr{X}}^{r}+\|y\|_{\mathscr{X}}^{r})$

for all $x$ and $y$ in $\mathscr{X}$; it satisfies the Upper Weak
Parallelogram property (UWP) if for some (possibly different) constant and
exponent the reverse inequality holds for all $x$ and $y$ in $\mathscr{X}$. If
$\mathscr{X}$ is a Hilbert space, then the parallelogram law holds,
corresponding to $r=2$ and $C=1$. Otherwise, these inequalities generalize
Clarkson’s inequalities [18], and the parameters $r$ and $C$ give a sense of
how far the space $\mathscr{X}$ departs from behaving like a Hilbert space.

It was shown in [9] that the $L^{p}$ spaces satisfy LWP and UWP when
$1<p<\infty$, and the full ranges of parameters $C$ and $r$ were identified
(see also [4, 5, 7, 8, 13]). More generally, a space satisfying LWP is
uniformly convex, and a space satisfying UWP is uniformly smooth [9,
Proposition 3.1]. From this it could be further surmised that the dual of a
LWP space is an UWP space, and vice-versa; this is made precise in [7, Theorem
3.1].

Another useful consequence of the weak parallelogram laws is a version of the
Pythagorean Theorem for normed spaces, where orthogonality is in the Birkhoff-
James sense. It takes the form of a family of inequalities relating the
lengths of orthogonal vectors with that of their sum [9, Theorem 3.3].

######  Theorem 5.1 ([9]).

If a smooth Banach space $\mathscr{X}$ satisfies LWP with constant $C>0$ and
exponent $r>1$, then there exists $K>0$ such that

(5.2)
$\|x\|^{r}_{\mathscr{X}}+K\|y\|^{r}_{\mathscr{X}}\leqslant\|x+y\|^{r}_{\mathscr{X}}$

whenever $x\perp_{\mathscr{X}}y$; if $\mathscr{X}$ satisfies UWP with constant
$C>0$ and exponent $r>1$, then there exists a positive constant $K$ such that

(5.3)
$\|x\|^{r}_{\mathscr{X}}+K\|y\|^{r}_{\mathscr{X}}\geqslant\|x+y\|^{r}_{\mathscr{X}}$

whenever $x\perp_{\mathscr{X}}y$. In either case, the constant $K$ can be
chosen to be ${C}/{(2^{r-1}-1)}$

When $\mathscr{X}$ is any Hilbert space, the parameters are $K=1$ and $r=2$,
and the Pythagorean inequalities reduce to the familiar Pythagorean theorem.
More generally, these Pythagorean inequalities enable the application of some
Hilbert space methods and techniques to smooth Banach spaces satisfying LWP or
UWP; see, for example, [16, Proposition 4.8.1 and Proposition 4.8.3; Theorem
8.8.1].

The weak parallelogram laws and the Pythagorean inequalities fail on $L^{1}$
and $L^{\infty}$. We previously saw in Corollary 4.3 that $\mathscr{M}_{p}$
contains a subspace, consisting of the linear functions, that behaves
geometrically like $\ell^{1}_{A}$. Consequently we would expect the weak
parallelogram laws and the Pythagorean inequalities to fail on
$\mathscr{M}_{p}$, and indeed that is the case.

######  Theorem 5.4.

Let $1<p<\infty$. The space $\mathscr{M}_{p}$ fails to satisfy LWP or UWP for
any constant $C>0$ or exponent $r>1$.

###### Proof.

If

$\|1+z\|^{r}_{\mathscr{M}_{p}}+C\|1-z\|^{r}_{\mathscr{M}_{p}}\leqslant
2^{r-1}(\|1\|_{\mathscr{M}_{p}}^{r}+\|z\|^{r}_{\mathscr{M}_{p}})$

holds, then

$(1+C)2^{r}\leqslant 2^{r-1}(2),$

which forces $C=0$. Thus LWP fails.

Similarly, for $C>0$ we have

$\|1\|^{r}_{\mathscr{M}_{p}}+C^{r}\|z/C\|^{r}_{\mathscr{M}_{p}}\geqslant
2^{r-1}(\|1+z/C\|^{r}_{\mathscr{M}_{p}}+\|1-z/C\|^{r}_{\mathscr{M}_{p}})$

implies

$2\geqslant 2^{r-1}\cdot 2\cdot(1+1/C)^{r},$

which is absurd when $1<r<\infty$. Therefore UWP also fails. ∎

######  Theorem 5.5.

Let $1<p<\infty$. The space $\mathscr{M}_{p}$ fails to satisfy either of the
Pythagorean inequalities for any parameters $r>1$ and $K>0$.

###### Proof.

Fix $c\neq 0$. Let $\varphi(z)=1+cz$, and consider $f(z)\in\ell^{p}_{A}$ of
the form $f(z)=f_{0}+f_{2}z^{2}+f_{4}z^{4}+\cdots$. Then

$\displaystyle\|\varphi(z)f(z)\|_{p}^{p}$
$\displaystyle=\|(1+cz)(f_{0}+f_{2}z^{2}+f_{4}z^{4}+\cdots)\|^{p}_{p}$
$\displaystyle=\|(f_{0}+f_{2}z^{2}+f_{4}z^{4}+\cdots)+cz(f_{0}+f_{2}z^{2}+f_{4}z^{4}+\cdots)\|_{p}^{p}$
$\displaystyle=|f_{0}|^{p}+|c|^{p}|f_{0}|^{p}+|f_{1}|^{p}+|c|^{p}|f_{1}|^{p}+|f_{2}|^{p}+|c|^{p}|f_{2}|^{p}$
$\displaystyle=\|f\|_{p}^{p}+|c|^{p}\|f\|_{p}^{p}$
$\displaystyle\geqslant\|f\|_{p}^{p}.$

This shows that $\|1+cz\|_{\mathscr{M}_{p}}\geqslant\|1\|_{\mathscr{M}_{p}}$
for all constants $c$, or $1\perp_{\mathscr{M}_{p}}z$. By considering the
limit

$\lim_{c\rightarrow
0}\frac{\|1+cz\|_{\mathscr{M}_{p}}^{r}-\|1\|_{\mathscr{M}_{p}}^{r}}{\|cz\|_{\mathscr{M}_{p}}^{r}}=\lim_{c\rightarrow
0}\frac{(1+|c|)^{r}-1^{r}}{|c|^{r}},$

we see that $\mathscr{M}_{p}$ fails to satisfy (5.3), as $K=\infty$ would be
forced.

Next, note that for $c\neq 0$, we have

$\displaystyle\|(1+z)+c(1-z)\|_{\mathscr{M}_{p}}$
$\displaystyle=\|(1+c)+(1-c)z\|_{\mathscr{M}_{p}}$ $\displaystyle=|1+c|+|1-c|$
$\displaystyle\geqslant 2$ $\displaystyle=\|1+z\|_{1}$
$\displaystyle=\|1+z\|_{\mathscr{M}_{p}}.$

This shows that $1+z\perp_{\mathscr{M}_{p}}1-z$. Next, consider

$\frac{\|(1+z)+c(1-z)\|_{\mathscr{M}_{p}}^{r}-\|1+z\|_{\mathscr{M}_{p}}^{r}}{\|c(1-z)\|_{\mathscr{M}_{p}}^{r}}=\frac{(|1+c|+|1-c|)^{r}-2^{r}}{2|c|^{r}},$

where $1<r<\infty$.

This tends toward zero as $c\rightarrow 0^{+}$, which would require $K=0$.
Thus, (5.2) fails to hold. ∎

##  6\. Functionals on $\mathscr{M}_{p}$

Let $1<p<\infty$. Suppose that
$\lambda=(\lambda_{0},\lambda_{1},\lambda_{2},\ldots)$ is a sequence of
complex numbers such that for some $C>0$ we have

$|\lambda_{0}\varphi_{0}+\lambda_{1}\varphi_{1}+\lambda_{2}\varphi_{2}+\cdots|\leqslant
C\|\varphi\|_{\mathscr{M}_{p}}$

for all $\varphi(z)=\sum_{k=0}^{\infty}\varphi_{k}z^{k}\in\mathscr{M}_{p}$.
Then $\lambda$ determines a bounded linear functional on $\mathscr{M}_{p}$
with norm at most $C$. Let us give the name $\mathscr{S}=\mathscr{S}_{p}$ to
the collection of functionals arising in this manner. It is a nonempty
collection, since it contains all of $\ell^{p^{\prime}}_{A}$. Thus
$\mathscr{S}$ is a linear manifold within $\mathscr{M}_{p}^{*}$, the
continuous dual space of $\mathscr{M}_{p}$.

If $\lambda=(\lambda_{0},\lambda_{1},\lambda_{2},\ldots)\in\mathscr{S}$, then
$\lambda_{k}=\lambda(z^{k})$ and the pairing

$\lambda(\varphi)=\sum_{k=0}^{\infty}\lambda_{k}\varphi_{k}.$

applies for all $\varphi\in\mathscr{M}_{p}$.

Trivially, we can bound the norm of $\lambda$ as follows:

(6.1) $\|\lambda\|_{p^{\prime}}=\sup_{\varphi\neq
0}\frac{|\lambda(\varphi)|}{\|\varphi\|_{p}}\geqslant\sup_{\varphi\neq
0}\frac{|\lambda(\varphi)|}{\|\varphi\|_{\mathscr{M}_{p}}}=\|\lambda\|_{\mathscr{M}_{p}^{*}}\geqslant\sup_{\varphi\neq
0}\frac{|\lambda(\varphi)|}{\|\varphi\|_{1}}=\|\lambda\|_{\infty},$

possibly with $\infty$ on the left side.

Of course since
$\mathscr{M}_{p}\subseteq\ell^{p}_{A}\cap\ell^{p^{\prime}}_{A}$ we also have

$\|\lambda\|_{p}\geqslant\|\lambda\|_{\mathscr{M}_{p}^{*}},$

again, with the left side possibly being infinite.

Taking the $\langle p-1\rangle$ power does something natural in this context.

######  Proposition 6.2.

Let $1<p<\infty$. If $\varphi\in\mathscr{M}_{p}$, then $\varphi^{\langle
p-1\rangle}\in\mathscr{S}$.

###### Proof.

In this situation, $\varphi^{\langle p-1\rangle}\in\ell^{p^{\prime}}_{A}$, and
hence $\varphi^{\langle p-1\rangle}\in\mathscr{S}$, by (6.1). ∎

Members of $\mathscr{S}$ might not have radial boundary limits, but they do
satisfy the following growth condition, which can also be interpreted as
boundedness of point evaluation.

######  Proposition 6.3.

Let $1<p<\infty$. If $\lambda\in\mathscr{S}$, then

$|\lambda(w)|\leqslant\frac{\|\lambda\|_{\mathscr{M}^{*}_{p}}}{(1-|w|^{p})^{1/p}},\
\,w\in\mathbb{D}.$

###### Proof.

The point evaluation functional at any point $w$ of the disk is a multiplier
on $\ell^{p}_{A}$, since its coefficients are absolutely summable. Apply
$\lambda\in\mathscr{S}$ to point evaluation at $w$ to see that $\lambda$
satisfies the growth condition shown above. ∎

It turns out that difference quotients are bounded on $\mathscr{S}$.

######  Proposition 6.4.

Let $1<p<\infty$. If $\lambda\in\mathscr{S}$, and $w\in\mathbb{D}$, then
$Q_{w}\lambda\in\mathscr{S}$, and

$\|Q_{w}\lambda\|_{\mathscr{M}_{p}^{*}}\leqslant\frac{\|\lambda\|_{\mathscr{M}_{p}^{*}}}{1-|w|}.$

###### Proof.

It is easy to see that if $\varphi\in\mathscr{M}_{p}$, then $S^{k}\varphi$
belongs to $\mathscr{M}_{p}$ for all $k\geqslant 0$, with equal norms. We now
calculate

$\displaystyle(Q_{w}\lambda)(\varphi)$
$\displaystyle=\Bigg{(}\frac{\sum\lambda_{k}z^{k}-\sum\lambda_{k}w^{k}}{z-w}\Bigg{)}(\varphi)$
$\displaystyle=\Big{(}\sum_{k=1}^{\infty}\lambda_{k}(z^{k-1}+z^{k-2}w+\cdots+w^{k-1})\Big{)}(\varphi)$
$\displaystyle=\Big{(}\sum_{k=1}^{\infty}\sum_{j=0}^{k-1}\lambda_{k}z^{j}w^{k-j-1}\Big{)}(\varphi)$
$\displaystyle=\sum_{k=1}^{\infty}\sum_{j=0}^{k-1}\lambda_{k}\varphi_{j}w^{k-j-1}$
$\displaystyle=\lambda_{1}(\varphi_{0})$
$\displaystyle\quad\,+\lambda_{2}(\varphi_{0}w+\varphi_{1})$
$\displaystyle\quad\,+\lambda_{3}(\varphi_{0}w^{2}+\varphi_{1}w+\varphi_{2})$
$\displaystyle\quad\,+\cdots$
$\displaystyle=\lambda(S\varphi)+w\lambda(S^{2}\varphi)+w^{2}\lambda(S^{3}\varphi)+\cdots.$

From this we obtain

$\displaystyle|(Q_{w}\lambda)(\varphi)|$
$\displaystyle\leqslant\|\lambda\|_{\mathscr{M}_{p}^{*}}\|S\varphi\|_{\mathscr{M}_{p}}+|w|\|\lambda\|_{\mathscr{M}_{p}^{*}}\|S^{2}\varphi\|_{\mathscr{M}_{p}}+|w|^{2}\|\lambda\|_{\mathscr{M}_{p}^{*}}\|S^{3}\varphi\|_{\mathscr{M}_{p}}+\cdots$
$\displaystyle=\frac{\|\lambda\|_{\mathscr{M}_{p}^{*}}\|\varphi\|_{\mathscr{M}_{p}}}{1-|w|},$

which proves the claim. ∎

Let us add that the weak parallelogram laws and the Pythagorean inequalities
must fail on $\mathscr{M}_{p}^{*}$ as well. This is because it contains a
subspace that is isomorphic to $\ell^{\infty}_{A}(\\{0,1\\})$. Furthermore we
see that $\mathscr{M}_{p}$ fails to be smooth. For example, the multiplier $1$
is normed by both $1$ and $1+z$ in $\mathscr{M}_{p}^{*}$.

##  7\. The extremal multipliers on $\ell^{p}_{A}$

Recall that if $\varphi\in\mathscr{M}_{p}$, then
$\|\varphi\|_{\mathscr{M}_{p}}\geqslant\|\varphi\|_{p}$. We say that the
multiplier $\varphi$ is $\it extremal$ if equality holds, that is,

$\|\varphi\|_{\mathscr{M}_{p}}=\|\varphi\|_{p}.$

For $\ell^{2}_{A}=H^{2}$, the multipliers are the bounded analytic functions
on $\mathbb{D}$, and the extremal multipliers are exactly the constant
multiples of inner functions. Indeed, if

$\sup_{z\in\mathbb{D}}|\varphi(z)|=\sup_{0<r<1}\int_{\mathbb{T}}|\varphi(re^{i\theta})|^{2}\,\frac{d\theta}{2\pi},$

then $|\varphi(e^{i\theta})|=\|\varphi\|_{H^{\infty}}$ a.e. is forced. The
reverse implication is similarly trivial.

For $\ell^{p}_{A}$, $p\neq 2$, it would therefore be plausible to guess that
the extremal multipliers are the $p$-inner functions. However, this is
incorrect. It was shown in [14] that for $2<p<\infty$, there are $p$-inner
functions whose zero sets fail to be Blaschke sequences. Such a $p$-inner
function cannot be a multiplier of $\ell^{p}_{A}$, since it would also have to
belong to $\ell^{p^{\prime}}_{A}$. In the paper [6] $p$-inner functions are
constructed whose zero sets accumulate at every point of the boundary circle
$\mathbb{T}$. However, by [16, Corollary 12.6.3], a multiplier on
$\ell^{p}_{A}$ for $p\in[1,2)$ has unrestricted limits almost everywhere on
$\mathbb{T}$. A $p$-inner function thus described cannot therefore be a
multiplier on $\ell^{p}_{A}$.

More can be said when $p\neq 2$. First, the extremality of a multiplier is
inherited by its conjugate in the following sense.

######  Proposition 7.1.

Let $\varphi\in\mathscr{M}_{p}$. If
$\|\varphi\|_{\mathscr{M}_{p}}=\|\varphi\|_{p}$, then
$\|\lambda\|_{\mathscr{M}_{p}^{*}}=\|\lambda\|_{p^{\prime}}$, where
$\lambda=\varphi^{\langle p-1\rangle}$.

###### Proof.

By hypothesis,

$\|\varphi\|_{\mathscr{M}_{p}}=\sup\frac{|\langle\varphi
f,g\rangle|}{\|f\|_{p}\|g\|_{p^{\prime}}}=\sup\frac{|\langle\varphi
1,g\rangle|}{\|1\|_{p}\|g\|_{p^{\prime}}}=\|\varphi\|_{p}.$

This forces $g=\varphi^{\langle p-1\rangle}$, apart from a harmless
multiplicative constant.

Since $g\in\ell^{p^{\prime}}$, we also have $g\in\mathscr{S}$ by (6.1).
Relabeling $g$ as the functional $\lambda$, we have

$\|\varphi\|_{p}=\frac{|\langle\varphi,g\rangle|}{\|g\|_{p^{\prime}}}\leqslant\frac{|\langle\varphi,\lambda\rangle|}{\|\lambda\|_{\mathscr{M}_{p}^{*}}}\leqslant\|\varphi\|_{\mathscr{M}_{p}}.$

Equality is forced throughout, and we conclude that

$\|\lambda\|_{p^{\prime}}=\|\lambda\|_{\mathscr{M}_{p}^{*}}.$

∎

This comes into play in the main result, to which we presently turn.

######  Theorem 7.2.

Let $p\in(1,\infty)\setminus\\{2\\}$. A multiplier $\varphi\in\mathscr{M}_{p}$
satisfies $\|\varphi\|_{\mathscr{M}_{p}}=\|\varphi\|_{p}$ if and only if
$\varphi$ is a monomial.

###### Proof.

First, the claim is trivial if $\varphi$ is identically zero, so let us
suppose otherwise. Also, since $\mathscr{M}_{p}=\mathscr{M}_{p^{\prime}}$ as
point sets and with equal norms, it follows
$\mathscr{M}_{p}^{*}=\mathscr{M}_{p^{\prime}}^{*}$ with equal norms as well.

Now suppose that $2<p<\infty$. Then $1<p^{\prime}<2$, and we have

$\|\varphi\|_{p^{\prime}}\geqslant\|\varphi\|_{p}=\|\varphi\|_{\mathscr{M}_{p}}=\|\varphi\|_{\mathscr{M}_{p^{\prime}}}\geqslant\|\varphi\|_{p^{\prime}}.$

Equality is forced throughout. In particular,
$\|\varphi\|_{p}=\|\varphi\|_{p^{\prime}}$, which implies that $\varphi$ is a
monomial, according to Proposition 2.1. (This step fails if $p=p^{\prime}=2$).

Finally, let $1<p<2$, and suppose that $\varphi\in\mathscr{M}_{p}$ is
extremal; that is, $\|\varphi\|_{\mathscr{M}_{p}}=\|\varphi\|_{p}$. Then

$\displaystyle\|\varphi\|_{\mathscr{M}_{p}}$ $\displaystyle=\|\varphi\|_{p}$
$\displaystyle\geqslant\|\varphi\|_{p^{\prime}}$
$\displaystyle\geqslant\|\varphi\|_{\mathscr{M}_{p^{\prime}}^{*}}$
$\displaystyle\geqslant\frac{|\langle\varphi^{\langle
p-1\rangle},\varphi\rangle|}{\|\varphi^{\langle
p-1\rangle}\|_{\mathscr{M}_{p^{\prime}}}}$
$\displaystyle=\frac{\|\varphi\|^{p}_{p}}{\|\varphi^{\langle
p-1\rangle}\|_{\mathscr{M}_{p^{\prime}}}}\ \ \ (\star)$
$\displaystyle=\frac{\|\varphi\|^{p}_{p}}{\|\varphi^{\langle
p-1\rangle}\|_{p^{\prime}}}$ $\displaystyle=\|\varphi\|_{p}.$

This forces $\varphi$ to be a monomial.

From the line ($\star$) to the next, we used $\|\varphi^{\langle
p-1\rangle}\|_{\mathscr{M}_{p^{\prime}}}=\|\varphi^{\langle
p-1\rangle}\|_{p^{\prime}}$, which we derive as follows:

$\displaystyle\|\varphi\|_{p}^{p-1}$
$\displaystyle=\frac{|\langle\varphi^{\langle
p-1\rangle},\varphi\rangle|}{\|\varphi\|_{p}}$
$\displaystyle=\frac{|\langle\varphi^{\langle
p-1\rangle},\varphi\rangle|}{\|\varphi\|_{\mathscr{M}_{p}}}$
$\displaystyle\leqslant\|\varphi^{\langle p-1\rangle}\|_{\mathscr{M}_{p}^{*}}$
$\displaystyle=\|\varphi^{\langle
p-1\rangle}\|_{\mathscr{M}_{p^{\prime}}^{*}}$
$\displaystyle\leqslant\|\varphi^{\langle p-1\rangle}\|_{p^{\prime}}$
$\displaystyle=\|\varphi\|_{p}^{p-1}$

and equality must hold throughout.

Conversely, if any monomial multiplier, and it can be checked by inspection
that it is extremal. ∎

######  Example 7.3.

If $1<p<\infty$ and $0<|w|<1$, then the function

$B(z):=\frac{1-z/w}{1-w^{\langle p^{\prime}-1\rangle}z},$

turns out to be $p$-inner [11, Lemma 3.2], and

$\|B\|_{p}^{p}=1+\frac{(1-|w|^{p^{\prime}})^{p-1}}{|w|^{p}}.$

Note, in particular, that when $p=2$ the function $B$ is the Blaschke factor,
possibly apart from a multiplicative constant, with its root at $w$.

Since $B$ is analytic in a neighborhood of the closed disk
$\overline{\mathbb{D}}$, it is a multiplier. Let us show directly that for
$p=4$ it fails to be extremal, as must be the case according to Theorem 7.2.

We will take as a test function

$f(z):=1-w^{\langle{p^{\prime}}-1\rangle}z,$

so that $f\in\ell^{p}_{A}$ and

$\|f\|_{p}^{p}=1+1/|w|^{p}.$

Now fix $p=4$, so that $p^{\prime}=4/3$. For $0<a<1$ we have the elementary
inequalities

$\displaystyle a-a^{2}$ $\displaystyle>0$ $\displaystyle 3(a^{2}-a)$
$\displaystyle<a^{2}-a$ $\displaystyle a^{3}+1-3a+3a^{2}-a^{3}$
$\displaystyle<a^{2}-a+1$ $\displaystyle a^{3}+(1-a)^{3}$
$\displaystyle<\frac{a^{3}+1}{1+a}$ $\displaystyle 1+\frac{(1-a)^{3}}{a^{3}}$
$\displaystyle<\frac{1+1/a^{3}}{1+a}.$

Substitute $a=|w|^{4/3}$ to obtain

$1+\frac{(1-|w|^{4/3})^{4-1}}{|w|^{4}}<\frac{1+1/|w|^{4}}{1+|w|^{4/3}}.$

This yields the bound

$\displaystyle\|B\|_{p}^{p}$
$\displaystyle=1+\frac{(1-|w|^{4/3})^{p-1}}{|w|^{4}}$
$\displaystyle<\frac{1+1/|w|^{4}}{1+|w|^{4/3}}$
$\displaystyle=\frac{\|Bf\|_{p}^{p}}{\|f\|_{p}^{p}}$
$\displaystyle\leqslant\|B\|_{\mathscr{M}_{p}}^{p}.$

This verifies that $B$ fails to be an extremal multiplier.

## References

  * [1] A. Aleman, S. Richter, and C. Sundberg.  Beurling’s theorem for the Bergman space.  Acta Math., 177(2):275–310, 1996.
  * [2] J. Alonso, H. Martini, and S. Wu.  On Birkhoff orthogonality and isosceles orthogonality in normed linear spaces.  Aequationes Math., 83(1-2):153–189, 2012.
  * [3] Catherine Bénéteau, Matthew C. Fleeman, Dmitry S. Khavinson, Daniel Seco, and Alan A. Sola.  Remarks on inner functions and optimal approximants.  Canad. Math. Bull., 61(4):704–716, 2018.
  * [4] W. L. Bynum.  Weak parallelogram law for Banach spaces.  Canad. Math. Bull., 19(3):269–275, 1976.
  * [5] W. L. Bynum and J. H. Drew.  A weak parallelogram law for $\ell_{p}$.  Amer. Math. Monthly, 79:1012–1015, 1972.
  * [6] R. Cheng.  The zero sets of $\ell^{p}_{A}$ are nested.  Illinois J. Math., 63:601–618, 2019.
  * [7] R. Cheng and C. Harris.  Duality of the weak parallelogram laws on Banach spaces.  J. Math. Anal. Appl., 404(1):64–70, 2013.
  * [8] R. Cheng, A. G. Miamee, and M. Pourahmadi.  On the geometry of $L^{p}(\mu)$ with applications to infinite variance processes.  J. Aust. Math. Soc., 74(1):35–42, 2003.
  * [9] R. Cheng and W. T. Ross.  Weak parallelogram laws on Banach spaces and applications to prediction.  Period. Math. Hungar., 71(1):45–58, 2015.
  * [10] Raymond Cheng and James G. Dragas.  On the failure of canonical factorization in $\ell^{p}_{A}$.  J. Math. Anal. Appl., 479:1939–1955, 2019.
  * [11] Raymond Cheng, Javad Mashreghi, and William T. Ross.  Birkhoff–James Orthogonality and the Zeros of an Analytic Function.  Comput. Methods Funct. Theory, 17(3):499–523, 2017.
  * [12] Raymond Cheng, Javad Mashreghi, and William T. Ross.  Multipliers of sequence spaces.  Concr. Oper., 4:76–108, 2017.
  * [13] Raymond Cheng, Javad Mashreghi, and William T. Ross.  Optimal weak parallelogram constants for $L^{p}$ spaces.  Math. Inequal. Appl., 21(4):1047–1058, 2018.
  * [14] Raymond Cheng, Javad Mashreghi, and William T. Ross.  Inner functions and zero sets for $\ell^{p}_{A}$.  Trans. Amer. Math. Soc., 372(3):2045–2072, 2019.
  * [15] Raymond Cheng, Javad Mashreghi, and William T. Ross.  Inner functions in reproducing kernel spaces.  In Analysis of operators on function spaces, Trends Math., pages 167–211. Birkhäuser/Springer, Cham, 2019.
  * [16] Raymond Cheng, Javad Mashreghi, and William T. Ross.  Function theory and $\ell^{p}$ spaces, volume 75 of University Lecture Series.  American Mathematical Society, Providence, R.I., 2020.
  * [17] Raymond Cheng, Javad Mashreghi, and William T. Ross.  Inner vectors for Toeplitz operators.  Complex Analysis and Spectral Theory, Special Volume in Celebration of Thomas Ransford’s 60th Birthday(Khavinson and Mashreghi, Eds.), (in press).
  * [18] J. A. Clarkson.  Uniformly convex spaces.  Trans. Amer. Math. Soc., 40(3):396–414, 1936.
  * [19] Karel de Leeuw.  On $L_{p}$ multipliers.  Ann. of Math. (2), 81:364–379, 1965.
  * [20] P. Duren, D. Khavinson, H. S. Shapiro, and C. Sundberg.  Invariant subspaces in Bergman spaces and the biharmonic equation.  Michigan Math. J., 41(2):247–259, 1994.
  * [21] Peter Duren, Dmitry Khavinson, and Harold S. Shapiro.  Extremal functions in invariant subspaces of Bergman spaces.  Illinois J. Math., 40(2):202–210, 1996.
  * [22] Peter Duren, Dmitry Khavinson, Harold S. Shapiro, and Carl Sundberg.  Contractive zero-divisors in Bergman spaces.  Pacific J. Math., 157(1):37–56, 1993.
  * [23] Lars Hörmander.  Estimates for translation invariant operators in $L^{p}$ spaces.  Acta Math., 104:93–140, 1960.
  * [24] R. C. James.  Orthogonality and linear functionals in normed linear spaces.  Trans. Amer. Math. Soc., 61:265–292, 1947.
  * [25] V. Lebedev and A. Olevskiĭ.  Idempotents of Fourier multiplier algebra.  Geom. Funct. Anal., 4(5):539–544, 1994.
  * [26] V. V. Lebedev.  Inner functions and $l^{p}$-multipliers.  Funktsional. Anal. i Prilozhen., 32(4):10–21, 95, 1998.
  * [27] V. V. Lebedev.  Spectra of inner functions and $l^{p}$-multipliers.  In Complex analysis, operators, and related topics, volume 113 of Oper. Theory Adv. Appl., pages 205–212. Birkhäuser, Basel, 2000.
  * [28] V. V. Lebedev and A. M. Olevskiĭ.  Fourier $L^{p}$-multipliers with bounded powers.  Izv. Ross. Akad. Nauk Ser. Mat., 70(3):129–166, 2006.
  * [29] Vladimir Lebedev and Alexander Olevskiĭ.  Bounded groups of translation invariant operators.  C. R. Acad. Sci. Paris Sér. I Math., 322(2):143–147, 1996.
  * [30] N. K. Nikol′skiĭ.  On spaces and algebras of Toeplitz matrices operating in $l^{p}$.  Sibirsk. Mat. Ž., 7:146–158, 1966.
  * [31] Stefan Richter.  Invariant subspaces of the Dirichlet shift.  J. Reine Angew. Math., 386:205–220, 1988.
  * [32] D. Seco.  A characterization of Dirichlet-inner functions.  Complex Anal. Oper. Theory, 13(4):1653–1659, 2019.
  * [33] I. È. Verbickiĭ.  Multipliers of spaces $l^{p}_{A}$.  Funktsional. Anal. i Prilozhen., 14(3):67–68, 1980.
  * [34] S. A. Vinogradov.  Multipliers of power series with sequence of coefficients from $l^{p}$.  Zap. Naučn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 39:30–39, 1974.  Investigations on linear operators and the theory of functions, IV.
  * [35] S. A. Vinogradov.  Multiplicative properties of power series with a sequence of coefficients from $l^{p}$.  Dokl. Akad. Nauk SSSR, 254(6):1301–1306, 1980.


# Probabilistic Counting in Generalized Turnstile Models††thanks: This work
was supported by NSF grant CCF-2221980.

Dingyu Wang
University of Michigan
<EMAIL_ADDRESS>
###### Abstract

Traditionally in the turnstile model of data streams, there is a state vector
$x=(x_{1},x_{2},\ldots,x_{n})$ which is updated through a stream of pairs
$(i,k)$ where $i\in[n]$ and $k\in\mathbb{Z}$. Upon receiving $(i,k)$,
$x_{i}\leftarrow x_{i}+k$. A distinct count algorithm in the turnstile model
takes one pass of the stream and then estimates $\|x\|_{0}=|\\{i\in[n]\mid
x_{i}\neq 0\\}|$ (aka $L_{0}$, the Hamming norm).

In this paper, we define a finite-field version of the turnstile model. Let
$F$ be any finite field. Then in the $F$-turnstile model, for each $i\in[n]$,
$x_{i}\in F$; for each update $(i,k)$, $k\in F$. The update $x_{i}\leftarrow
x_{i}+k$ is then computed in the field $F$. A distinct count algorithm in the
$F$-turnstile model takes one pass of the stream and estimates
$\|x\|_{0;F}=|\\{i\in[n]\mid x_{i}\neq 0_{F}\\}|$.

We present a simple distinct count algorithm, called $F$-PCSA, in the
$F$-turnstile model for any finite field $F$. The new $F$-PCSA algorithm takes
$m\log(n)\log(|F|)$ bits of memory and estimates $\|x\|_{0;F}$ with
$O(\frac{1}{\sqrt{m}})$ relative error where the hidden constant depends on
the order of the field.

$F$-PCSA is straightforward to implement and has several applications in the
real world with different choices of $F$. Most notably,

  * •

$\mathbb{F}_{2}$-PCSA can be used to estimate the number of non-zero elements
in a boolean system where every element has a boolean state which can be
toggled during a stream of updates;

  * •

$\mathbb{F}_{2^{k}}$-PCSA can be used to estimate the number of non-zero
elements in a $k$-boolean system where every element has a vector of $k$
boolean attributes which can be individually toggled during a stream of
updates;

  * •

$\mathbb{F}_{p}$-PCSA can be used to implement simple and efficient
$L_{0}$-estimation algorithms in the (original) turnstile model, making the
probabilistic counting with deletions conceptually no harder than the
probabilistic counting without deletions. With different schemes to select
$p$, one gets different upper bounds. To get a $(1\pm\epsilon)$-estimation of
$L_{0}$ with 1/3 error probability, one needs

    * –

$O(\epsilon^{-2}\log n\cdot(\log\epsilon^{-1}+\log\log\|x\|_{\infty}))$ bits,
matching the state of the art $L_{0}$-estimation algorithm by Kane, Nelson and
Woodruff [9];

    * –

$O(\epsilon^{-2}\log n\cdot\log\|x\|_{\infty})$ bits, which is useful when the
maximum frequency is small;

    * –

$O(\epsilon^{-2}\log
n\cdot\max(\log\frac{\|x\|_{1}}{\|x\|_{0}},\log\epsilon^{-1}))$ bits, which is
useful when the average non-zero frequency is low.

The upper bounds above can be further sharpened by ignoring the top
$O(\epsilon)$-fraction of elements with non-zero frequencies.

##  1 Introduction

_Distinct-Count_ is the problem of approximately counting the number of
distinct elements in a stream. In 1983, Flajolet and Martin [8] proposed the
first streaming Distinct-Count algorithm, Probabilistic Counting with
Stochastic Averaging (PCSA). Although being the first streaming Distinct-Count
algorithm in history, the PCSA sketch already possesses two fundamental
characteristics that are desirable when counting distinct elements.

  * •

“Zero knowledge”. The distribution of PCSA’s memory state depends only on the
cardinality of the stream.

  * •

“Scale invariance”. The behavior of the sketch is multiplicatively periodic in
the cardinality.

However, PCSA only works in the _incremental_ setting, in which only
insertions are allowed.

######  Definition 1 (incremental setting).

Let $U=\\{1,2,\ldots,n\\}$ be the universe (e.g. the set of IPv4 addresses).
The state vector $x=(x_{1},x_{2},\ldots,x_{n})\in\mathbb{N}^{n}$ is
initialized as all zeros and gets updated by a stream of pairs in the form of
$(v,k)$, where $v\in U$ and $k\in\mathbb{N}$.

  * •

Upon receiving $(v,k)$, $x_{v}\leftarrow x_{v}+k$.

A streaming Distinct-Count algorithm in the incremental setting takes one pass
of the stream and estimates $\|x\|_{0}=|\\{v\in U:x_{v}\neq 0\\}|$ (aka
cardinality, $F_{0}$), i.e., the number of elements that have non-zero
frequency.

######  Remark 1.

By convention (e.g. [1]), we refer to $x_{v}$ as the _frequency_ of $v$ when
$x_{v}$ encodes the number of occurrences of $v$. However, for a general-
purpose $x_{v}$, we will call it the _state_ of $v$.

In 2003, Cormode, Datar, Indyk, and Muthukrishnan [5] gave the first Distinct-
Count algorithm in the _turnstile model_ , allowing both insertions and
deletions.

######  Definition 2 (turnstile model, [5], [10]).

Let $U=\\{1,2,\ldots,n\\}$ be the universe. The state vector
$x=(x_{1},x_{2},\ldots,x_{n})\in\mathbb{Z}^{n}$ is initialized as all zeros
and gets updated by a stream of pairs in the form of $(v,k)$, where $v\in U$
and $k\in\mathbb{Z}$.

  * •

Upon receiving $(v,k)$, $x_{v}\leftarrow x_{v}+k$.

A streaming Distinct-Count algorithm in the turnstile model takes one pass of
the stream and estimates $\|x\|_{0}=|\\{v\in U:x_{v}\neq 0\\}|$ (aka $L_{0}$
or the Hamming norm).

######  Remark 2.

One may also define the updates as $\mathsf{Insert}(v)$ and
$\mathsf{Delete}(v)$ in the turnstile model, which is equivalent to receiving
$(v,+1)$ and $(v,-1)$ respectively.

######  Remark 3.

Algorithms in the turnstile model natively support unions and symmetric
differences of streams, since they are often _linear_ [10].

##### The key insight.

The application of a streaming model is intimately related to the _algebraic
structure_ of the update ($k$) and the state ($x_{v}$). The only difference in
the definitions of the incremental setting and the turnstile model is that the
former assumes $k,x_{v}\in\mathbb{N}$, while the latter assumes
$k,x_{v}\in\mathbb{Z}$. The fact that $\mathbb{Z}$ has an additive inverse
allows the turnstile model to incorporate deletions natively. With this
observation, it is natural to define the following general model as a
framework.

######  Definition 3 ($M$-turnstile model).

Let $(M,+)$ be a commutative monoid. The _$M$ -turnstile model_ is defined as
follows. Let $U=\\{1,2,\ldots,n\\}$ be the universe. The state vector
$x=(x_{1},x_{2},\ldots,x_{n})\in M^{n}$ is initialized as all zeros (i.e. the
identity of the monoid $M$) and gets updated by a stream of pairs in the form
of $(v,k)$, where $v\in U$ and $k\in M$.

  * •

Upon receiving $(v,k)$, $x_{v}\leftarrow x_{v}+k$.

A streaming Distinct-Count algorithm in the $M$-turnstile model takes one pass
of the stream and estimates $\|x\|_{0}=|\\{v\in U:x_{v}\neq 0\\}|$.

######  Remark 4.

With this definition, the incremental setting is just the
$\mathbb{N}$-turnstile model and the original turnstile model is the
$\mathbb{Z}$-turnstile model. In general, $M$ is the structure of the state of
the elements. For example, if every element has a boolean state (on/off), then
$M$ is the $\\{0,1\\}$-field. See Table 1 for a list of models defined in the
$M$-turnstile framework.

######  Remark 5.

In order for the state vector $x\in M^{n}$ to be updated in parallel, the
algebraic structure of $M$ must at least be a commutative monoid.
Specifically, associativity and commutativity are needed to merge streams
unorderedly, and the existence of identity is needed to initialize the values
of all elements. There are similar notions in recent work in the field of
automata theory [2] and commutative algebra [4].

model name |  $M$-turnstile framework | note
---|---|---
incremental setting |  $\mathbb{N}$-turnstile model |
(original) turnstile model |  $\mathbb{Z}$-turnstile model |
$k$-boolean model $\dagger\star$ |  $\mathbb{F}_{2^{k}}$-turnstile model |  $k$ is a positive integer
$p$-cyclic model $\dagger\star$ |  $\mathbb{F}_{p}$-turnstile model |  $p$ is a prime
finite field model $\dagger\star$ |  $F$-turnstile model |  $F$ is a finite field
invertible model $\dagger$ |  $G$-turnstile model |  $G$ is an abelian group
base model $\dagger$ |  $M$-turnstile model |  $M$ is a commutative monoid
Table 1: Examples of models in the $M$-turnstile framework. $\dagger$: The
model is newly defined in this work. $\star$: The Distinct-Count problem in
the model is solved in this work by $F$-PCSA.

In general, it is not yet clear how to generally solve Distinct-Count in the
$M$-turnstile model for an arbitrary commutative monoid $M$. However, we show
that when $M$ is a _finite field_ $F$, it is straightforward to solve
Distinct-Count in the $F$-turnstile model, conceptually no harder than solving
Distinct-Count in the incremental setting.

##### Contribution.

Concretely, we present a simple streaming Distinct-Count algorithm in the
$F$-turnstile model (Definition 3) for any finite field $F$, called $F$-PCSA.
We prove that $F$-PCSA gives an unbiased estimate of $\|x\|_{0;F}$ with
$O(1/\sqrt{m})$ relative error (the hidden constant depends on $|F|$, see
Table 2 on page 2) using $(m\log n\cdot\log|F|)$ bits of memory. Let
$\widehat{\|x\|_{0}}$ be the estimator of $\|x\|_{0}$. We say it is _unbiased_
if for any $x\in F^{n}$,

$\displaystyle\mathbb{E}\widehat{\|x\|_{0}}=\|x\|_{0}.$

We say $\widehat{\|x\|_{0}}$ has a _relative error_ $\epsilon$ if for any
$x\in F^{n}$,

$\displaystyle\frac{\sqrt{\mathbb{V}\widehat{\|x\|_{0}}}}{\|x\|_{0}}=\epsilon.$

In 2023, Bæk, Pagh and Walzer [3] analyzed a set sparse recovery algorithm
over $\mathbb{F}_{2}$. They commented in the introduction that “Linear
sketches over finite fields are less well-studied [in comparison to sketches
over $\mathbb{Z}$ and $\mathbb{R}$], but are natural in some applications.”
[3]. We have a similar motivation here for $\mathbb{F}_{2}$-PCSA.
$\mathbb{F}_{2}$-PCSA can be used to count the number of elements that appear
an odd number of times, or the number of 1s in a boolean system. In general,
for a prime $p$, $\mathbb{F}_{p}$-PCSA can be used to count the number of
elements whose frequencies are _not_ divisible by $p$.

Now consider another series of finite fields. For any positive integer $k$,
$\mathbb{F}_{2^{k}}$-PCSA can be used to estimate the number of non-zero
$x_{v}$s where each $x_{v}$ is $\mathbb{F}_{2^{k}}$-valued (thus can be stored
as a $k$-bit string). The state $x_{v}$ can be used to identify a vector of
$k$ boolean attributes of the element $v$. Then given a stream of attribute
toggles (in the form of “toggle the $j$th attribute of the element $v$”),
$\mathbb{F}_{2^{k}}$-PCSA estimates the number of elements who have at least
one nonzero attribute.

When the prime $p$ is large, the $\mathbb{F}_{p}$-turnstile model approximates
the original $\mathbb{Z}$-turnstile model. Thus as an application of the
generic $F$-PCSA algorithm, $\mathbb{F}_{p}$-PCSA can be used to estimate
$L_{0}$ when $p$ is propertly selected. By different strategies of selecting
the prime $p$, it provides the following space complexity upper bounds
(assuming a random oracle). To get a $(1\pm\epsilon)$-estimation of $L_{0}$
with 1/3 error probability, one needs

  * •

$O(\epsilon^{-2}\log n\cdot(\log\epsilon^{-1}+\log\log\|x\|_{\infty}))$ bits,
matching the state of the art $L_{0}$-estimation algorithm by Kane, Nelson and
Woodruff [9];

  * •

$O(\epsilon^{-2}\log n\cdot\log\|x\|_{\infty})$ bits, which is useful when the
maximum frequency is small;

  * •

$O(\epsilon^{-2}\log
n\cdot\max(\log\frac{\|x\|_{1}}{\|x\|_{0}},\log\epsilon^{-1}))$ bits, which is
useful when the average non-zero frequency is low.

Note that the upper bounds above can be made sharper by an _$O(\epsilon)$
-mass discount_, i.e. ignoring the top $O(\epsilon)$-fraction of elements with
non-zero frequencies. The key observation is: The worst thing that can happen
in $\mathbb{F}_{p}$-PCSA when $x_{v}$ is unusually large for some element
$v\in U$ is that $v$ gets missed in the final estimator (as if $v$ has never
appeared in the stream). It is fine to miss an $O(\epsilon)$-fraction of
elements to get a $(1\pm\epsilon)$-estimation of $\|x\|_{0}$, which is why in
$\mathbb{F}_{p}$-PCSA one may simply ignore the top $O(\epsilon)$-fraction of
elements with high (even unbounded) frequencies.

Not all sketches enjoy this $O(\epsilon)$-mass discount feature. For example,
the first $L_{0}$-estimation algorithm [5] uses a linear combination of
$p$-stable random variables with a small $p$ (e.g. $p<0.01$) to approximate
$L_{0}$, which is sensitive to sparse high frequencies. To see this, let
$x_{1}$ be the only non-zero entry in the vector $x$. For a fixed $p$, no
matter how small $p$ is, the estimator
$\widehat{\|x\|_{0}}_{\text{$p$-stable}}$ becomes arbitrarily large as $x_{1}$
increases to infinity, while $\|x\|_{0}$ is just $1$ by construction.

###  1.1 Notations

Let $\mathbbm{1}\left[\cdot\right]$ be the indicator function.

Let $U=\\{1,2,\ldots,n\\}$ and
$x=(x_{1},x_{2},\ldots,x_{n})\in\mathbb{Z}^{n}$.

notation | definition | name
---|---|---
$\|x\|_{0}$ | $|\\{v\in U\mid x_{v}\neq 0\\}|$ |  $L_{0}$, Hamming norm
$\|x\|_{1}$ | $\sum_{v\in U}|x_{v}|$ | $L_{1}$
$\|x\|_{\infty}$ | $\max_{v\in U}|x_{v}|$ | maximum, $L_{\infty}$

Let $F$ be any finite field. Let $|F|$ be the order of $F$. By default, 0
denotes the additive identity of $F$ and 1 denotes the multiplicative identity
of $F$. The definition of $L_{0}$ can be extended to fields, i.e.
$\|x\|_{0}=|\\{v\in U\mid x_{v}\neq 0\\}|$ where $x_{v}$s are $F$-valued and
$0$ is the additive identity of $F$. When we want to emphasize that $x$ is
$F$-valued, we write $L_{0}$ as $\|x\|_{0;F}$. For any prime $p$ and positive
integer $k$, we denote the field of order $p^{k}$ as $\mathbb{F}_{p^{k}}$.

Let $X$ be a real random variable. Let $\mathbb{E}X$ be its expectation and
$\mathbb{V}X$ be its variance. Let $Y,Z$ be two generic111For example, random
variables over a finite field. random variables. We write $Y\sim Z$ if $Y$ and
$Z$ are identically distributed.

Let $m$ be a positive integer. $[m]$ is a shorthand for the set
$\\{1,2,\ldots,m\\}$.

###  1.2 Preliminaries

Commutative monoids are the most general algebraic structures to be updated in
parallel.

######  Definition 4 (commutative monoids).

Let $M$ be a set and $+:M\times M\to M$ be a binary operator over $M$. Then
$M$ is a _commutative monoid_ if

  * •

$\forall a,b,c\in M$, $(a+b)+c=a+(b+c)$; (associativity)

  * •

$\forall a,b\in M$, $a+b=b+a$; (commutativity)

  * •

$\exists 0\in M\,\forall a\in M,a+0=0+a=a$. (existence of identity)

Finite fields are the central objects in this work. Finite fields can be
unambiguously identified by their orders up to isomorphism. Thus we write the
finite field of order $q$ as $\mathbb{F}_{q}$, where $q$ is necessarily
$p^{k}$ for some prime $p$ and some positive integer $k$.

###  1.3 Overview of $F$-PCSA

Since $F$-PCSA is similar to PCSA [8], we will first recap the definition of
PCSA.

####  1.3.1 PCSA Sketch

######  Definition 5 (PCSA [8]).

Let $U=\\{1,2,\ldots,n\\}$ be the universe. The PCSA sketch stores a table of
bits, BITMAP$[i,j]$ where $i\in[m]$ and $j\in\mathbb{N}$. For every $(i,j)$,
BITMAP$[i,j]$ is initialized to zero. There is a hash function
$h:U\to[m]\times\mathbb{N}$ such that for any element $v\in U$,
$\mathbb{P}(h(v)=(i,j))=\frac{1}{m}2^{-j}$ for each $(i,j)$. Upon an insertion
of $v\in U$ (or receiving $(v,1)$ in the $\mathbb{N}$-turnstile model),

$\displaystyle\textrm{BITMAP}[h(v)]\leftarrow\textrm{BITMAP}[h(v)]\lor 1.$

See Figure 1(a) for an example of PCSA’s memory snapshot.

(a) PCSA’s memory

(b) $F$-PCSA’s memory

(c) $\mathbb{F}_{2}$-PCSA’s memory

Figure 1: All three sketches are coupled using the same $h$ hash function. The
way that “1”s appear in PCSA is statistically the same with the way “R”s
appear in $F$-PCSA. One does observe concrete “1”s in PCSA’s memory. On the
other hand, “R”s in $F$-PCSA are observed in the memory as independent
instances of uniform random varaibles over $F$. As an example, every bit that
should have been a “1” in PCSA now has a half chance to be a “0” in
$\mathbb{F}_{2}$-PCSA.

Let $Q_{i}$ be the position of the leftmost zero in the $i$th row. It is
observed in [8] that whenever the cardinality doubles, $Q_{i}$ increases by 1
on average. The PCSA’s estimator is thus

$\displaystyle\widehat{\|x\|_{0}}_{\text{{PCSA}{}}}=\alpha_{m}2^{\frac{1}{m}\sum_{i=1}^{m}Q_{i}},$

where $\alpha_{m}$ is some normalization factor.

##### Middle Range Assumption.

We assume the cardinality is in the middle range in this work, i.e.
$\|x\|_{0}\gg 1$ and $\|x\|_{0}\ll|U|$. In this case, all bits $(i,j)$ with
$j\geq\log|U|$ are zeros with high probability. Thus we only need to store
bits $(i,j)$ with $j\in[0,\log|U|]$, which requires $(m\log|U|)$ bits of
memory. For the case where $\|x\|_{0}=\Theta(1)$ or $\|x\|_{0}=\Theta(|U|)$,
separate estimation methods are needed, which are out of the scope of this
paper.

####  1.3.2 $F$-PCSA Sketch

The algebraic structure of finite fields brings us the following properties.

######  Lemma 1.

Let $F$ be a finite field. Then the uniform distribution over $F$ is well-
defined.

Let $R_{1},R_{2},\ldots,R_{k}$ be i.i.d. uniform random variables over $F$.
Then for any non-zero $a\in F$ and $k\in\mathbb{Z}_{+}$,

$\displaystyle aR_{1}\sim R_{1}$ (1) $\displaystyle\sum_{i=1}^{k}R_{i}\sim
R_{1}.$ (2)

###### Proof.

The uniform distribution over a finite field $F$ is just the normalized
counting measure, which is a well-defined probability measure since $F$ is
finite.

Since $F$ is a field and $a$ is non-zero, there is a multiplicative inverse
$a^{-1}$ of $a$. Then we have, for any $b\in F$,

$\displaystyle\mathbb{P}(aR_{1}=b)=\mathbb{P}(R_{1}=ba^{-1})=\frac{1}{|F|}.$

Thus (1) is proved. For (2), it suffices to prove $R_{1}+R_{2}\sim R_{1}$ and
then use induction. For any $b\in F$,

$\displaystyle\mathbb{P}(R_{1}+R_{2}=b)$ $\displaystyle=\sum_{c\in
F}\frac{1}{|F|}\mathbb{P}(R_{1}+c=b)$ since every element $c$ has an additive
inverse $-c$ in $F$, $\displaystyle=\sum_{c\in
F}\frac{1}{|F|}\mathbb{P}(R_{1}=b-c)=\sum_{c\in
F}\frac{1}{|F|^{2}}=\frac{1}{|F|},$

∎

The lemma above enables us to count over $F$ in an almost identical way as
PCSA counts over $\mathbb{N}$.

######  Definition 6 ($F$-PCSA).

Let $U=\\{1,2,\ldots,n\\}$ be the universe. The $F$-PCSA sketch stores a table
of $F$-values, FIELDMAP[$i$,$j$] where $i\in[m]$ and $j\in\mathbb{N}$. For
every $(i,j)$, FIELDMAP$[i,j]$ is initialized to zero (the additive identity
of $F$). There is a hash function $h:U\to[m]\times\mathbb{N}$ such that for
any $v\in U$, $\mathbb{P}(h(v)=(i,j))=\frac{1}{m}2^{-j}$ for each $(i,j)$.
There is another hash function $g:U\to F$ such that for any $v\in U$, $g(v)$
is uniformly random over $F$. Upon receiving $(v,k)$ where $v\in U,k\in F$,

$\displaystyle\textrm{FIELDMAP}[h(v)]\leftarrow\textrm{FIELDMAP}[h(v)]+k\cdot
g(v).$

Together with Lemma 1, it is immediate that, conditioning on the hash function
$h$, the entry $\textrm{FIELDMAP}[i,j]$ behaves as follows.

$\displaystyle\textrm{FIELDMAP}[i,j]$ $\displaystyle=0,\quad\text{if $x_{v}=0$
for all $v\in U$ that $h(v)=(i,j)$}$ $\displaystyle\textrm{FIELDMAP}[i,j]$
$\displaystyle\sim R,\quad\text{if $x_{v}\neq 0$ for some $v\in U$ that
$h(v)=(i,j)$},$

where $R$ is a uniform random variable over $F$. See Figure 1(b) for a diagram
of $F$-PCSA’s memory. $F$-PCSA behaves statistically the same with the
original PCSA with the twist that “1”s becomes “R”s. This is the intuition why
it is no harder to count in the $F$-turnstile model than in the
$\mathbb{N}$-turnstile model. One needs $\log|F|$ bits per register to store
$F$-values and thus $F$-PCSA needs $(m\log|U|\cdot\log|F|)$ bits of memory.

We use the _highest index_ (the index of the rightmost non-zero value)
estimator for $F$-PCSA. Let $W_{i}$ be the highest index of non-zero entries
in the $i$th row. Then the estimator is defined as

$\displaystyle\widehat{\|x\|_{0;F}}_{\text{$F$-{PCSA}{}}}=\beta_{m}2^{\frac{1}{m}\sum_{i=1}^{m}W_{i}},$

where $\beta_{m}$ is some normalization factor. We prove, under some
simplification assumptions listed in Section 2.1, in Theorem 2 that
$\widehat{\|x\|_{0;F}}_{\text{$F$-{PCSA}{}}}$ is unbiased with $O(1/\sqrt{m})$
relative error (the leading constant depends on $|F|$). See Table 2 for
computed normalization factors and relative errors for a list of finite
fields.

$|F|$ | $\psi_{\mathbb{E}}(|F|)$ | $\psi_{\mathbb{V}}(|F|)$ | normalization factor ($\beta_{m}$) | relative error
---|---|---|---|---
2 | -0.1100 | 5.588 | 1.079$m$ | 1.638$/\sqrt{m}$
3 | 0.5487 | 4.321 | 0.6836$m$ | 1.441$/\sqrt{m}$
4 | 0.7903 | 4.002 | 0.5782$m$ | 1.387$/\sqrt{m}$
5 | 0.9173 | 3.861 | 0.5295$m$ | 1.362$/\sqrt{m}$
6 | not a field | not a field | not a field | not a field
7 | 1.049 | 3.732 | 0.4833$m$ | 1.339$/\sqrt{m}$
8 | 1.088 | 3.697 | 0.4704$m$ | 1.333$/\sqrt{m}$
9 | 1.118 | 3.671 | 0.4607$m$ | 1.328$/\sqrt{m}$
10 | not a field | not a field | not a field | not a field
$2^{8}$ | 1.326 | 3.512 | 0.3989$m$ | 1.299$/\sqrt{m}$
$2^{32}$ | 1.333 | 3.507 | 0.3969$m$ | 1.298$/\sqrt{m}$
$\infty$ | 1.333 | 3.507 | 0.3969$m$ | 1.298$/\sqrt{m}$
Table 2: Asymptotic constants as $m\to\infty$. By Theorem 2, the normalization
factor is $2^{-\psi_{\mathbb{E}}(|F|)}m$ and the relative error is
$\sqrt{m^{-1}(\log^{2}2)\psi_{\mathbb{V}}(|F|)}$, where
$\psi_{\mathbb{E}}(|F|)$ and $\psi_{\mathbb{V}}(|F|)$ are defined in Theorem 6
(Appendix A). The values of $\psi_{\mathbb{E}}(|F|)$ and
$\psi_{\mathbb{V}}(|F|)$ in the table are obtained through numerical
integration. Interestingly, as $|F|$ goes to infinity, $F$-PCSA estimator
statistically converges to the LogLog estimator [6] and the relative error
computed here (1.298$/\sqrt{m}$) matches Durand and Flajolet’s computation for
the LogLog’s relative error, which is
$m^{-1/2}\sqrt{\frac{1}{12}\log^{2}2+\frac{1}{6}\pi^{2}}\approx
1.29806/\sqrt{m}$.

###  1.4 Related Work

To the best of our knowledge, the problem of Distinct-Count in the
$F$-turnstile model where $F$ is a generic finite field is new. Thus
$\mathbb{F}_{2^{k}}$-PCSA are interesting new counting algorithms in
$k$-boolean systems. $\mathbb{F}_{p}$-PCSA where $p$ is a small prime is also
new to count the number of elements whose frequency is not divisible by $p$.

When $p$ is large, $\mathbb{F}_{p}$-turnstile goes to $\mathbb{Z}$-turnstile
and the Distinct-Count problem in the $\mathbb{F}_{p}$-turnstile model is
intimately related to the $L_{0}$-estimation in the $\mathbb{Z}$-turnstile
model. Indeed, finite fields $\mathbb{F}_{p}$ when $p$ is large are used in
the construction of the $L_{0}$-estimation algorithm proposed by Kane, Nelson
and Woodruff [9] (KNW-$L_{0}$). They randomly project the vector hashed to
each cell to an element in $\mathbb{F}_{p}$, with some random large prime $p$.
When $p$ is large, $\mathbb{F}_{p}$-PCSA and KNW-$L_{0}$ store statistically
very similar information (a multi-resolution table of random projections over
$\mathbb{F}_{p}$). However, the estimation methods are different. KNW-$L_{0}$
first uses a subroutine RoughEstimator to roughly estimates $\|x\|_{0}$. From
this rough estimate, KNW-$L_{0}$ chooses one column (see Figure 1(b)) with a
constant fraction of “R”s. Then they prove that by choosing a large $p$
randomly, no “R” will be a zero _in that column_. Conditioning on this event,
the $L_{0}$-estimation can be solved by their $F_{0}$-estimation algorithm (in
the incremental setting), through balls-and-bins statistics in that column. On
the other hand, the estimator of $\mathbb{F}_{p}$-PCSA inherently takes
account of the events “$\texttt{R}=\texttt{0}$” and uses the highest index to
give an estimator with exact and sharper error constants. The difference
between the two estimation methods becomes more significant when $p$ is small,
e.g. $p=2$, where half of the “1”s will be “0”s in the table (see Figure 1(c))
and there is no way to condition with high probability on the event that
“$\texttt{R}\neq\texttt{0}$” for a whole column.

###  1.5 Organization

$F$-PCSA is formally analyzed in Section 2. Applications of $F$-PCSA on
$L_{0}$-estimation are discussed in Section 3.

##  2 Analysis of $F$-PCSA

###  2.1 Simplification Assumptions

######  Assumption 1 (random oracle).

There is a random oracle that provides ideal hash functions $h$ and $g$.

######  Assumption 2 (poissonization).

Since we only care about the cases where $\|x\|_{0}$ is in the middle range
(see the Middle Range Assumption in Section 1.3), we may assume the following.

  * •

Since every element is hashed to only one table entry (through the hash
function $h(\cdot)$), there are negligible negative correlations between table
entries. For example, if there is only one non-zero element, then a non-zero
entry necessarily implies that all other entries are zeros. However, this
correlation vanishes when $\|x\|_{0}\gg 1$ and thus we will assume all the
entries in FIELDMAP are _strictly_ independent. I.e. when a new element comes
in, instead of being hashed to only one entry, now every entry $(i,j)$ has an
independent chance of $\frac{1}{m}2^{-j}$ to be hashed to.

  * •

The probability that one hits the $(i,j)$ entry is $\frac{1}{m}2^{-j}$ which
goes to $1-e^{-\frac{1}{m}2^{-j}}$ as $j$ becomes large. Since $\|x\|_{0}\gg
1$ and the highest index is likely to be large, we will assume the probability
of hitting the $(i,j)$ entry is _exactly_ $1-e^{-\frac{1}{m}2^{-j}}$.

  * •

Since $\|x\|_{0}$ is assumed to be in the middle range, we assume that the
columns are indexed by _integers_ , extending infinitely to both ends. E.g.
the probability of hitting the $(i,-3)$ entry is now assumed to be
$1-e^{-\frac{2^{3}}{m}}$.

######  Remark 6.

This assumption is called “poissonization” since it essentially assumes that
elements are inserted _continuously_ into the sketch with rate 1, which is why
the entries are independent and the $(i,j)$ entry has a hitting probability
$1-e^{-\frac{1}{m}2^{-j}}$. Poissonization doesn’t affect the statistics of
high-positioned entries when $\|x\|_{0}$ becomes mildly large, which can be
shown by a standard coupling method.

There is another difficulty during the analysis of such estimators: The
behavior of the estimator has constant fluctuations which do _not_ vanish even
when $m$ goes to infinity. See, for example, the analysis of PCSA [8] and
HyperLogLog [7] where every statement has a periodic error term. See Figure 1
of [11] for a visualization of the fluctuation. As proposed in [11], these
fluctuations can be eliminated elegantly by _randomly offsetting_ the
subsketches.

######  Assumption 3 (random offsetting).

We assume that for each $i\in[m]$, there is a random offset $\Theta_{i}$
uniformly drawn from $[0,1)$ for the $i$th subsketch. Then the $i$th subsketch
randomly ignores a $2^{-\Theta_{i}}$-fraction of the elements in the universe.
Thus now the probability of hitting the $(i,j)$ entry is
$1-e^{-m^{-1}2^{-j-\Theta_{i}}}$.

######  Remark 7.

A PCSA-style sketch is inherently multiplicatively periodic in $2$ and
therefore one will get the same relative behaviour for $\|x\|_{0}=2^{k}$ with
different $k\in\mathbb{N}$. However, the sketch will have different behaviours
for e.g. $\|x\|_{0}=2^{k}$ and $\|x\|_{0}=2^{k+0.5}$. The random offsetting
assumption adds noise to this process, thus making the sketch now has an
“averaged” behaviour for any $\|x\|_{0}\in\mathbb{R}^{+}$. Note that this
random offsetting trick is _necessary to be actually implemented_ if the
required error is comparable to the fluctuation magnitudes (usually small,
e.g. $<10^{-6}$ for PCSA [8]).

With all the assumptions above, we reconstruct the $F$-PCSA sketch (Definition
6) in the following subsection.

###  2.2 Construction of $F$-PCSA

With the poissonization assumptions, now $F$-PCSA consists of $m$ i.i.d.
subsketches (rows in FIELDMAP). We will construct one subsketch now.

Let $F$ be any finite field. Let the _memory state_
$s=(s_{i})_{-\infty}^{\infty}$ be a bilaterally infinite vector over $F$
(corresponding to one row in FIELDMAP). We will refer the state vector $x$ in
the $F$-turnstile model (Definition 3) as the _stream state_. Recall that the
stream state is an $n$-vector over $F$ where $n$ is the size of the universe
$U$.

We first draw a random offset $\Theta\in[0,1)$. Then with the (poissonized)
hash functions $h$ and $g$ provided by the random oracle, we generate two
tables of random variables $H=(H_{v,i})_{v\in U,i\in\mathbb{Z}}$ and
$G=(G_{v,i})_{v\in U,i\in\mathbb{Z}}$, where for each $v\in U$ and
$i\in\mathbb{Z}$,

  * •

$H_{v,i}$ is a $\\{0,1\\}$-random variable222 0 is the additive identity in
$F$; 1 is the multiplicative identity in $F$. with
$\mathbb{P}(H_{v,i}=0)=e^{-m^{-1}2^{-i-\Theta}}$,

  * •

$G_{v,i}$ is a uniform random variable over $F$.

The entries in $H$ and $G$ are all independent. The two tables $H$ and $G$ are
independent.

The sketching process can be described as follows.

  * •

Initially, both the memory state $s$ and the stream state $x$ are all zeros.

  * •

Upon receiving $(v,k)$ for $v\in U$ and $k\in F$,

    * –

$x_{v}\leftarrow x_{v}+k$ and

    * –

for each $i\in\mathbb{Z}$

      * *

$s_{i}\leftarrow s_{i}+k\cdot H_{v,i}G_{v,i}$.

Note that the process described above faithfully simulates the $F$-PCSA in
Definition 6 with the assumptions listed in Section 2.1.

We then formalize the intuition in Section 1.3.2.

###  2.3 Characterization of $F$-PCSA’s States

######  Theorem 1 (characterization of $F$-PCSA’s state).

Fix a stream state $x$ and an offset $\theta\in[0,1)$. Let the memory state be
$S=(S_{i})_{i\in\mathbb{Z}}$.333We capitalize the memory state $s$ when we
emphasize it as a _random vector_ for a fixed stream state $x$. Then

  * •

$S_{i}$s are mutually independent.

  * •

$\mathbb{P}(S_{i}\neq 0)=(1-e^{-\|x\|_{0}m^{-1}e^{-i-\theta}})(1-|F|^{-1})$,
for $i\in\mathbb{Z}$.

###### Proof.

By construction, the memory state $S$ and the stream state $x$ are linearly
related:

$\displaystyle S_{i}=\sum_{v\in U}x_{v}H_{v,i}G_{v,i}.$ (3)

Consequently, $S_{i}$s are independent due to the independence of entries of
$H$ and $G$.

Recall that $G_{v,i}$s are i.i.d. uniform random variables over $F$. By Lemma
1, we have

$\displaystyle S_{i}$ $\displaystyle=\sum_{v\in
U}x_{v}H_{v,i}G_{v,i}=\sum_{v\in U:x_{v}H_{v,i}\neq 0}x_{v}H_{v,i}G_{v,i}$
$\displaystyle\sim\mathbbm{1}\left[\exists v,x_{v}H_{v,i}\neq 0\right]R_{i},$

where $R_{i}$ is uniformly random over $F$. Thus we know

$\displaystyle\mathbb{P}(S_{i}\neq 0)$ $\displaystyle=\mathbb{P}(\exists
v,x_{v}H_{v,i}\neq 0)\mathbb{P}(R_{i}\neq 0)$
$\displaystyle=(1-\mathbb{P}(\forall v,x_{v}H_{v,i}=0))(1-|F|^{-1})$
$\displaystyle=(1-\prod_{v\in U}\mathbb{P}(x_{v}H_{v,i}=0))(1-|F|^{-1})$ (4)

Recall that $H_{v,i}$ is a binary random variable with probability
$e^{-2^{-i/m-\theta}}$ of being 0. Since $F$ is a field, $x_{v}H_{v,i}=0$ if
and only if $(H_{v,i}=0\lor x_{v}=0)$. Thus

$\displaystyle\mathbb{P}(x_{v}H_{v,i}=0)=\begin{cases}1,&x_{v}=0\\\
e^{-m^{-1}2^{-i-\theta}},&x_{v}\neq 0\end{cases},$

and then by (4),

$\displaystyle\mathbb{P}(S_{i}\neq 0)$
$\displaystyle=(1-e^{-\|x\|_{0}m^{-1}2^{-i-\theta}})(1-|F|^{-1}).$

∎

With the characterization theorem, we now analyze the estimator of $F$-PCSA.

###  2.4 Estimation of $F$-PCSA

The estimation is based on the highest non-zero position. The analysis is
overall straightforward except for a technical asymptotic analysis included in
the appendix.

######  Definition 7 (highest index/position).

Let $S$ be the memory state and $\Theta$ be the random offset. Then the
_highest index_ $B$ is defined as

$\displaystyle B=\sup\\{i\in\mathbb{Z}\mid S_{i}\neq 0\\}$

and the _highest position_ 444The highest position is just the smoothed
version of the highest index. is defined as

$\displaystyle W=B+\Theta.$

######  Definition 8.

Let $\nu:\mathbb{R}\times[0,1]\to\mathbb{R}$ be a function. For
$z\in\mathbb{R}$ and $r\in[0,1]$,

$\displaystyle\nu(z,r)$
$\displaystyle=(1-e^{-2^{-z}})r\prod_{j=1}^{\infty}\left(1-(1-e^{-2^{-z-j}})r\right)$

######  Lemma 2 (p.d.f. of $W$).

Let $f_{W}$ be the probability density function of $W$. Then

$\displaystyle f_{W}(z)$
$\displaystyle=\nu(z-\log_{2}(\|x\|_{0}m^{-1}),1-|F|^{-1}).$ (5)

###### Proof.

For $i\in\mathbb{Z}$, by the characterization theorem (Theorem 1),

$\displaystyle\mathbb{P}(B\leq
i|\Theta=\theta)=\prod_{j=i+1}^{\infty}\mathbb{P}(S_{j}=0)=\prod_{j=i+1}^{\infty}\left(1-(1-e^{-\|x\|_{0}m^{-1}2^{-j-\theta}})(1-|F|^{-1})\right)$

Thus

$\displaystyle\mathbb{P}(B=i|\Theta=\theta)$ $\displaystyle=\mathbb{P}(B\leq
i+1|\Theta=\theta)-\mathbb{P}(B\leq i|\Theta=\theta)$
$\displaystyle=(1-e^{-\|x\|_{0}m^{-1}2^{-i-\theta}})(1-|F|^{-1})\prod_{j=i+1}^{\infty}\left(1-(1-e^{-\|x\|_{0}m^{-1}2^{-j-\theta}})(1-|F|^{-1})\right)$
$\displaystyle=\nu(i+\theta-\log_{2}(\|x\|_{0}m^{-1}),1-|F|^{-1}).$ (6)

Then we have

$\displaystyle\int_{-\infty}^{z_{0}}f_{W}(z)dz$
$\displaystyle=\mathbb{P}(W\leq z_{0})=\mathbb{P}(B+\Theta\leq
z_{0})=\int_{0}^{1}\mathbb{P}(B+\theta\leq z_{0}|\Theta=\theta)\,d\theta$
$\displaystyle=\int_{0}^{1}\sum_{i=-\infty}^{\infty}\mathbbm{1}\left[i+\theta\leq
z_{0}\right]\mathbb{P}(B=i|\Theta=\theta)\,d\theta$ by (6),
$\displaystyle=\int_{0}^{1}\sum_{i=-\infty}^{\infty}\mathbbm{1}\left[i+\theta\leq
z_{0}\right]\nu(i+\theta-\log(\|x\|_{0}m^{-1}),1-|F|^{-1})\,d\theta$
$\displaystyle=\int_{-\infty}^{\infty}\mathbbm{1}\left[z\leq
z_{0}\right]\nu(z-\log_{2}(\|x\|_{0}m^{-1}),1-|F|^{-1})\,dz$
$\displaystyle=\int_{-\infty}^{z_{0}}\nu(z-\log_{2}(\|x\|_{0}m^{-1}),1-|F|^{-1})\,dz.$

Differentiate both sides by $z_{0}$ and we get (5). ∎

######  Definition 9.

Let $\phi:(0,1)\times[0,1]\to\mathbb{R}$ be a function. For $t\in(0,1)$ and
$r\in[0,1]$,

$\displaystyle\phi(t,r)=\int_{-\infty}^{\infty}2^{tz}\nu(z,r)\,dz.$

######  Lemma 3 (base-2 moment generating function of $W$).

For $t\in(0,1)$ and $|F|\geq 2$,

$\displaystyle\mathbb{E}2^{tW}=\|x\|_{0}^{t}m^{-t}\phi(t,1-|F|^{-1}).$

###### Proof.

By Lemma 2,

$\displaystyle\mathbb{E}2^{tW}=\int_{-\infty}^{\infty}f_{W}(z)2^{tz}\,dz$
$\displaystyle=\int_{-\infty}^{\infty}\nu(z-\log_{2}(\|x\|_{0}m^{-1}),1-|F|^{-1})2^{tz}\,dz$
set $s=z-\log_{2}(\|x\|_{0}m^{-1})$
$\displaystyle=\|x\|_{0}^{t}m^{-t}\int_{-\infty}^{\infty}\nu(s,1-|F|^{-1})2^{ts}\,ds$
by the definition of $\phi(\cdot,\cdot)$ (Definition 9)
$\displaystyle=\|x\|_{0}^{t}m^{-t}\phi(t,1-|F|^{-1}).$

∎

######  Theorem 2 ($F$-PCSA).

Let $F$ be any finite field and $m\geq 3$ be the number of i.i.d. subsketches.
Let $W_{1},W_{2},\ldots,W_{m}$ be the highest positions of the subsketches.
Then the $F$-PCSA estimator is defined as

$\displaystyle\widehat{\|x\|_{0}}=\phi(1/m,1-|F|^{-1})^{-m}m2^{\frac{1}{m}\sum_{i=1}^{m}W_{i}}.$

The estimator is unbiased,

$\displaystyle\mathbb{E}\widehat{\|x\|_{0}}=\|x\|_{0},$

and has variance

$\displaystyle\mathbb{V}\widehat{\|x\|_{0}}$
$\displaystyle=(\phi(1/m,1-|F|^{-1})^{-2m}\phi(2/m,1-|F|^{-1})^{m}-1)\|x\|_{0}^{2}.$

When $m$ is large,

$\displaystyle\widehat{\|x\|_{0}}$
$\displaystyle=(2^{-\psi_{\mathbb{E}}(|F|)}+O(m^{-1}))m2^{\frac{1}{m}\sum_{i=1}^{m}W_{i}}$
$\displaystyle\mathbb{V}\widehat{\|x\|_{0}}$
$\displaystyle=\|x\|_{0}^{2}m^{-1}\left((\log^{2}2)\psi_{\mathbb{V}}(|F|)+O(m^{-1})\right),$

where $\psi_{\mathbb{E}}$ and $\psi_{\mathbb{V}}$ are defined in Theorem 6 in
Appendix A. The relative error is bounded

$\displaystyle\sqrt{(\log^{2}2)\psi_{\mathbb{V}}(|F|)}<\sqrt{79},$ (7)

for all finite fields $F$.

######  Remark 8.

The rough bound (7) is only to show the relative error is $O(1)$ regardless of
$F$. The actual relative errors are much smaller. See Table 2 on page 2 for
some computed values of relative errors.

###### Proof.

Since $W_{i}$s are independent, we have

$\displaystyle\mathbb{E}\widehat{\|x\|_{0}}$
$\displaystyle=\phi(1/m,1-|F|^{-1})^{-m}m\mathbb{E}2^{\frac{1}{m}\sum_{i=1}^{m}W_{i}}$
$\displaystyle=\phi(1/m,1-|F|^{-1})^{-m}m\left(\mathbb{E}2^{\frac{1}{m}W_{1}}\right)^{m}$
by Lemma 3,
$\displaystyle=\phi(1/m,1-|F|^{-1})^{-m}m\left(\|x\|_{0}^{1/m}m^{-1/m}\phi(1/m,1-|F|^{-1})\right)^{m}$
$\displaystyle=\|x\|_{0}.$

Thus $\widehat{\|x\|_{0}}$ is unbiased. Similarly,

$\displaystyle\mathbb{E}\widehat{\|x\|_{0}}^{2}$
$\displaystyle=\phi(1/m,1-|F|^{-1})^{-2m}m^{2}\left(\mathbb{E}2^{\frac{2}{m}W_{1}}\right)^{m}$
$\displaystyle=\phi(1/m,1-|F|^{-1})^{-2m}m^{2}\left(\|x\|_{0}^{2/m}m^{-2/m}\phi(2/m,1-|F|^{-1})\right)^{m}$
$\displaystyle=\|x\|_{0}^{2}\phi(1/m,1-|F|^{-1})^{-2m}\phi(2/m,1-|F|^{-1})^{m}.$

The variance is obtained by the formula
$\mathbb{V}\widehat{\|x\|_{0}}=\mathbb{E}\widehat{\|x\|_{0}}^{2}-(\mathbb{E}\widehat{\|x\|_{0}})^{2}$.

The asymptotic case when $m$ is large is proved in Theorem 6 in Appendix A.

∎

##  3 Applications to $L_{0}$-Estimation

First note that an unbiased algorithm with relative error $O(\epsilon)$
implies a $(1\pm\epsilon)$-estimation algorithm with constant error
probability by Chebyshev’s inequality. Thus $F$-PCSA gives an
$(1\pm\epsilon)$-estimation of $\|x\|_{0;F}$ with a constant error probability
in the $F$-turnstile model using $O(\epsilon^{-2}\log n\cdot\log|F|)$ bits of
memory.

###  3.1 A Matching Upper Bound with Kane, Nelson and Woodruff’s
$L_{0}$-Estimation Algorithm

We will prove that it is possible to achieve the same space complexity of
KNW-$L_{0}$ ([9]) with $\mathbb{F}_{p}$-PCSA using a similar $p$-selection
trick. Instead of bounding the probabilities of all the “bad events” as in
[9], for $\mathbb{F}_{p}$-PCSA we only need to estimate the difference between
$\|x\|_{0}$ and $\|x\|_{0;\mathbb{F}_{p}}$, where $\|x\|_{0}$ is the quantity
we _want_ to estimate and $\|x\|_{0;\mathbb{F}_{p}}$ is the quantity we _can_
estimate accurately by $\mathbb{F}_{p}$-PCSA.

######  Theorem 3.

Let $\epsilon>0$ be the desired error. Let $P$ be a random prime uniformly
drawn from the set $S$ of the smallest $\frac{10\log\|x\|_{\infty}}{\epsilon}$
primes. Then for any $x\in\mathbb{Z}^{n}$

$\displaystyle\|x\|_{0}\geq\|x\|_{0;\mathbb{F}_{P}},\quad\text{and}\quad\mathbb{P}(\|x\|_{0}-\|x\|_{0;\mathbb{F}_{P}}>\epsilon\|x\|_{0})\leq\frac{1}{10}.$

###### Proof.

Since for any $a\in\mathbb{Z}$, $a=0$ implies $a=0\mod P$, we have
$\|x\|_{0}\geq\|x\|_{0;\mathbb{F}_{P}}$.

Imagine every element is placing balls in a set of bins indexed by $S$. Each
element $v\in U$ will place a ball in the bin indexed by $p\in S$ if $p\mid
x_{v}$. By randomly picking a prime $P$ from the set $S$,
$\|x\|_{0}-\|x\|_{0;\mathbb{F}_{P}}$ is equal to the number of element $v$
with $P\mid x_{v}$, which is equal to the number of balls in the bin indexed
by $P$. Note that for every element $v\in U$, $x_{v}$ has at most
$\log\|x\|_{\infty}$ distinct prime factors. Thus the number of balls is at
most $\|x\|_{0}\log\|x\|_{\infty}$. As a result, the number of bins with at
least $\epsilon\|x_{0}\|$ balls is at most $\log\|x\|_{\infty}/\epsilon$
(otherwise we run out of balls). We conclude that

$\displaystyle\mathbb{P}(\|x\|_{0}-\|x\|_{0;\mathbb{F}_{P}}>\epsilon\|x\|_{0})$
$\displaystyle\leq\frac{\text{number of bins with at least $\epsilon\|x\|_{0}$
balls}}{\text{number of bins}}$
$\displaystyle\leq\frac{\log\|x\|_{\infty}/\epsilon}{{10\log\|x\|_{\infty}}/{\epsilon}}=1/10.$

∎

######  Remark 9.

In KNW-$L_{0}$, a random prime is picked in the range
$[O(\frac{\log\|x\|_{\infty}}{\epsilon}),O((\frac{\log\|x\|_{\infty}}{\epsilon})^{3})]$.
In contrast, we only need to pick a random prime in the range
$[2,\tilde{O}(\frac{\log\|x\|_{\infty}}{\epsilon})]$ for
$\mathbb{F}_{p}$-PCSA.

To store a prime in Theorem 3, one needs
$(\log\epsilon^{-1}+\log\log\|x\|_{\infty}+O(1))$ bits of memory. Therefore,
by choosing a random $p$ with the scheme in Theorem 3, $\mathbb{F}_{p}$-PCSA
gets the same space complexity $O(\epsilon^{-2}\log
n(\log\epsilon^{-1}+\log\log\|x\|_{\infty}))$ with KNW-$L_{0}$, to give a
$(1\pm\epsilon)$-estimation of $L_{0}$ with a constant error probability, but
with a much smaller hidden constant.

###  3.2 New Space Complexity Upper Bounds for $L_{0}$-Estimation

####  3.2.1 $O(\epsilon^{-2}\log n\cdot\log\|x\|_{\infty})$

Let $p$ be a prime number. Trivially, if $\|x\|_{\infty}<p$ then
$\|x\|_{0}=\|x\|_{0;\mathbb{F}_{p}}$. Therefore by choosing $p$ of size
$\tilde{O}(\|x\|_{\infty})$, $\|x\|_{0}$ is perfectly estimated by
$\mathbb{F}_{p}$-PCSA, which uses $O(\epsilon^{-2}\log n\log\|x\|_{\infty})$
space. Most notably, if the system is boolean ($x_{v}$s toggle between 0 and
1) or the system’s insertions and deletions are interleaved, then
$\|x\|_{\infty}<2$. In such case, $\mathbb{F}_{2}$-PCSA estimates $\|x\|_{0}$
perfectly with only $O(\epsilon^{-2}\log n)$ bits of memory.

####  3.2.2 $O(\epsilon^{-2}\log
n\cdot\max(\log(\frac{\|x\|_{1}}{\|x\|_{0}}),\log(\epsilon^{-1})))$

Observe the following.

######  Theorem 4.

Let $\epsilon>0$ be the desired error. Let $S=\\{p_{1},p_{2},\ldots,p_{K}\\}$
be a set of $K$ distinct primes such that $\min S\geq\|x\|_{1}/\|x\|_{0}$ and
$K\geq 10/\epsilon$. Let $P$ be a random prime uniformly drawn from S. Then
for any $x\in\mathbb{Z}^{n}$,

$\displaystyle\|x\|_{0}\geq\|x\|_{0;\mathbb{F}_{P}},\quad\text{and}\quad\mathbb{P}(\|x\|_{0}-\|x\|_{0;\mathbb{F}_{P}}>\epsilon\|x\|_{0})\leq\frac{1}{10}.$

###### Proof.

We only need to prove the second inequality. Let
$y_{k}=|\\{v:p_{k}|x_{v},x_{v}\neq 0\\}|$, i.e. the number of non-zero
$x_{v}$s that have prime factor $p_{k}$. Without loss of generality, assume
$x_{1},x_{2},\ldots,x_{\tau}$ are positive and $x_{\tau+1},\ldots,x_{n}$ are
zeros. Then by the AM-GM inequality,

$\displaystyle\frac{\sum_{i=1}^{\tau}x_{i}}{\tau}\geq\left(\prod_{i=1}^{\tau}x_{i}\right)^{\tau^{-1}}\geq\left(\prod_{i=1}^{K}p_{i}^{y_{i}}\right)^{\tau^{-1}}\geq
p_{*}^{\tau^{-1}\sum_{i=1}^{K}y_{i}},$

where $p_{*}=\min S$. Thus we have
$\sum_{i=1}^{K}y_{i}\leq\tau\frac{\log(\|x\|_{1}/\tau)}{\log p_{*}}$. Note
that

$\displaystyle\mathbb{P}(\|x\|_{0}-\|x\|_{0;\mathbb{F}_{P}}\geq\epsilon\|x\|_{0})$
$\displaystyle=\sum_{i=1}^{K}\frac{1}{K}\mathbbm{1}\left[y_{k}\geq\epsilon\|x\|_{0}\right]$
where we use
$\mathbbm{1}\left[y_{k}\geq\epsilon\|x\|_{0}\right]\leq\frac{y_{k}}{\epsilon\|x\|_{0}}$,
$\displaystyle\leq\sum_{i=1}^{K}\frac{1}{K\epsilon\|x\|_{0}}y_{k}=\frac{1}{K\epsilon\|x\|_{0}}\sum_{i=1}^{K}y_{k}.$
since $\sum_{i=1}^{K}y_{i}\leq\tau\frac{\log(\|x\|_{1}/\tau)}{\log p_{*}}$
$\displaystyle\leq\tau\frac{\log(\|x\|_{1}/\tau)}{\log
p_{*}}\frac{1}{K\epsilon\|x\|_{0}}$ by definition, $\tau=\|x\|_{0}$
$\displaystyle=\frac{\log(\|x\|_{1}/\|x\|_{0})}{\log
p_{*}}\frac{1}{K\epsilon}$

By assumption, $p_{*}=\min S\geq\|x\|_{1}/\|x\|_{0}$ and $K\geq 10/\epsilon$.
We conclude that
$\mathbb{P}(\|x\|_{0}-\|x\|_{0;\mathbb{F}_{P}}\geq\epsilon\|x\|_{0})\leq
1/10$. ∎

To store a prime in Theorem 4, one needs
$\log(\tilde{O}(\max(\|x\|_{1}/\|x\|_{0},\epsilon^{-1})))$ bits of space.
Therefore, by choosing a random $p$ with the scheme in Theorem 4,
$\mathbb{F}_{p}$-PCSA gets a new space complexity $O(\epsilon^{-2}\log
n\cdot\max(\log(\frac{\|x\|_{1}}{\|x\|_{0}}),\log(\epsilon^{-1})))$ to give a
$(1\pm\epsilon)$-estimation of $L_{0}$ with a constant error probability.

Note that $\|x\|_{1}/\|x\|_{0}$ is precisely the _average non-zero frequency_.
Thus this scheme is particularly space-saving in a system where the maximum
frequency is unbounded but the average frequency is small.

######  Remark 10.

Similar upper bounds can be proved in the same way with
$\frac{\|x\|_{1}}{\|x\|_{0}}$ replaced by
$(\frac{\sum_{i=1}^{\tau}x_{i}^{\gamma}}{\|x\|_{0}})^{\gamma^{-1}}$ for any
$\gamma\in(0,1)$ by realizing that
$\frac{\sum_{i=1}^{\tau}x_{i}^{\gamma}}{\tau}\geq\left(\prod_{i=1}^{\tau}x_{i}\right)^{\gamma\tau^{-1}}$.

###  3.3 $O(\epsilon)$-Mass Discount

######  Theorem 5.

Given a state vector $x\in\mathbb{Z}^{n}$, without loss of generality, we
assume

$|x_{1}|\geq|x_{2}|\geq\ldots\geq|x_{\tau}|>0=|x_{\tau+1}|=\ldots=|x_{n}|,$

where $\tau=\|x\|_{0}$. We define the $(\epsilon/2)$-mass discounted vector
$x^{(\epsilon/2)}$ as follows.

$\displaystyle x^{(\epsilon/2)}_{i}$ $\displaystyle=0,\quad
i\leq\epsilon\tau/2$ $\displaystyle x^{(\epsilon/2)}_{i}$
$\displaystyle=x_{i},\quad i>\epsilon\tau/2.$

Suppose $P$ is a random prime chosen by some scheme such that

$\displaystyle\mathbb{P}(\|x^{(\epsilon/2)}\|_{0}-\|x^{(\epsilon/2)}\|_{0;\mathbb{F}_{P}}>\frac{\epsilon}{2}\|x^{(\epsilon/2)}\|_{0})$
$\displaystyle\leq\frac{1}{10},$ then
$\displaystyle\mathbb{P}(\|x\|_{0}-\|x\|_{0;\mathbb{F}_{P}}>\epsilon\|x\|_{0})$
$\displaystyle\leq\frac{1}{10}.$

###### Proof.

By construction we have
$\|x\|_{0}-\|x^{(\epsilon/2)}\|_{0}=\frac{\epsilon}{2}\|x\|_{0}$. Thus we have

$\displaystyle\mathbb{P}(\|x\|_{0}-\|x\|_{0;\mathbb{F}_{P}}>\epsilon\|x\|_{0})$
$\displaystyle=\mathbb{P}(\|x^{(\epsilon/2)}\|-\|x\|_{0;\mathbb{F}_{P}}>\frac{\epsilon}{2}\|x\|_{0})$
where we always have
$\|x\|_{0;\mathbb{F}_{P}}\geq\|x^{(\epsilon/2)}\|_{0;\mathbb{F}_{P}}$ and
$\|x\|_{0}\geq\|x^{(\epsilon/2)}\|_{0}$, so
$\displaystyle\leq\mathbb{P}(\|x^{(\epsilon/2)}\|-\|x^{(\epsilon/2)}\|_{0;\mathbb{F}_{P}}>\frac{\epsilon}{2}\|x^{(\epsilon/2)}\|_{0})\leq
1/10.$

∎

This theorem formally proves that we may replace $x$ by $x^{(\epsilon/2)}$ in
the upper bounds we derived earlier in this section.

## Acknowledgement

The author would like to thank Hung Ngo for raising the question of finding a
counter part of PCSA/HyperLogLog that allows deletions and is simple to
implement in practice. The author would like to thank Yaowei Long to be a
supportive sanity-checker.

## References

  * [1] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 20–29, 1996.
  * [2] Rajeev Alur, Konstantinos Mamouras, and Caleb Stanford.  Automata-based stream processing.  In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017\.
  * [3] Jakob Bæk Tejs Houen, Rasmus Pagh, and Stefan Walzer.  Simple set sketching.  In Symposium on Simplicity in Algorithms (SOSA), pages 228–241. SIAM, 2023.
  * [4] John C Baez, John Foley, and Joe Moeller.  Network models from petri nets with catalysts.  arXiv preprint arXiv:1904.03550, 2019.
  * [5] Graham Cormode, Mayur Datar, Piotr Indyk, and Shanmugavelayutham Muthukrishnan.  Comparing data streams using hamming norms (how to zero in).  IEEE Transactions on Knowledge and Data Engineering, 15(3):529–540, 2003.
  * [6] Marianne Durand and Philippe Flajolet.  Loglog counting of large cardinalities.  In Algorithms-ESA 2003: 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings 11, pages 605–617. Springer, 2003.
  * [7] Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier.  Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm.  Discrete mathematics & theoretical computer science, (Proceedings), 2007.
  * [8] Philippe Flajolet and G Nigel Martin.  Probabilistic counting algorithms for data base applications.  Journal of computer and system sciences, 31(2):182–209, 1985.
  * [9] Daniel M Kane, Jelani Nelson, and David P Woodruff.  An optimal algorithm for the distinct elements problem.  In Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 41–52, 2010.
  * [10] Yi Li, Huy L Nguyen, and David P Woodruff.  Turnstile streaming algorithms might as well be linear sketches.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 174–183, 2014.
  * [11] Seth Pettie and Dingyu Wang.  Information theoretic limits of cardinality estimation: Fisher meets shannon.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 556–569, 2021.

##  Appendix A Asymptotic Analysis

######  Lemma 4.

Let $X_{r}$ be a random variable with density $\nu(z,r)$ and $r\in[1/2,1]$.
Then $X_{r}$ is sub-exponential. Specifically,

$\displaystyle\mathbb{E}2^{|X_{r}|/6}<4.$

###### Proof.

Note that

$\displaystyle\mathbb{E}2^{|X_{r}|/6}=\int_{-\infty}^{0}2^{-z/6}\nu(z,r)\,dz+\int_{0}^{\infty}2^{z/6}\nu(z,r)\,dz.$

We estimate the two parts separately. Note that $\nu(z,r)\leq(1-e^{-2^{-z}})$
since $r\leq 1$. We first estimate

$\displaystyle\int_{0}^{\infty}2^{z/6}\nu(z,r)\,dz$
$\displaystyle\leq\int_{0}^{\infty}2^{z/6}(1-e^{-2^{-z}})\,dz<2$

Note that since $r\in[1/2,1]$,
$\nu(z,r)\leq\prod_{j=1}^{\infty}(1-(1-e^{-2^{-z-j}})/2)$. Then we estimate

$\displaystyle\int_{-\infty}^{0}2^{-z/6}\nu(z,r)\,dz\leq\int_{-\infty}^{0}2^{-z/6}\prod_{j=1}^{\infty}(1-(1-e^{-2^{-z-j}})/2)\,dz<2$

We conclude that

$\displaystyle\mathbb{E}2^{|X_{r}|/6}<2+2=4,$ (8)

from which we know $X_{r}$ is sub-exponential. ∎

######  Lemma 5.

Let $X_{r}$ be a random variable with density $\nu(z,r)$ and $r\in[1/2,1]$.
Then

$\displaystyle\log\mathbb{E}e^{tX_{r}}$
$\displaystyle=t\mathbb{E}X_{r}+\frac{t^{2}}{2}\mathbb{V}X_{r}+O(t^{3}),\quad
t\to 0$

###### Proof.

Note that by the definition of the exponential function,

$\displaystyle\mathbb{E}e^{tX_{r}}=\sum_{k=0}^{\infty}\frac{t^{k}}{k!}\mathbb{E}X_{r}^{k}=1+t\mathbb{E}X_{r}+\frac{t^{2}}{2}\mathbb{E}X_{r}^{2}+\sum_{k=3}^{\infty}\frac{t^{k}}{k!}\mathbb{E}X_{r}^{k}.$

We want to prove
$\mathbb{E}e^{tX_{r}}=1+t\mathbb{E}X_{r}+\frac{t^{2}}{2}\mathbb{E}X_{r}^{2}+O(t^{3})$
as $t\to 0$. Then we need to bound the moments $\mathbb{E}|X_{r}|^{k}$. Since
$X_{r}$ is sub-exponential (Lemma 4), we can bound the moments in a standard
way. For $k\geq 1$,

$\displaystyle\mathbb{E}|X_{r}|^{k}$
$\displaystyle=\mathbb{E}(2^{|X_{r}|/6}\cdot 2^{-|X_{r}|/6}|X_{r}|^{k})=\int
2^{z/6}\cdot(2^{-z/6}z^{k})\,d\mu_{|X_{k}|}$ (9) $\displaystyle\leq\int
2^{z/6}\cdot\sup_{s\geq
0}(2^{-s/6}s^{k})\,d\mu_{|X_{k}|}=\mathbb{E}2^{|X_{r}|/6}\sup_{s\geq
0}(2^{-s/6}s^{k}),$ (10)

where $\sup_{s\geq 0}(2^{-s/6}s^{k})=e^{-k}(6k/\log 2)^{k}$. Thus by Lemma 4
and (10)

$\displaystyle\mathbb{E}|X_{r}|^{k}\leq 4e^{-k}(6k/\log 2)^{k}<4\cdot
3.2^{k}\cdot k^{k},$ (11)

Thus we have

$\displaystyle|\mathbb{E}e^{tX_{r}}-(1+t\mathbb{E}X_{r}+\frac{t^{2}}{2}\mathbb{E}X_{r}^{2})|$
$\displaystyle=\left|\sum_{k=3}^{\infty}\frac{t^{k}}{k!}\mathbb{E}X_{r}^{k}\right|\leq\sum_{k=3}^{\infty}\frac{t^{k}}{k!}\mathbb{E}|X_{r}|^{k}$
$\displaystyle\leq\sum_{k=3}^{\infty}\frac{t^{k}}{k!}4\cdot 3.2^{k}\cdot
k^{k}$

By Stirling’s formula, we know for $k\in\mathbb{N}$,

$\displaystyle k!>\sqrt{2\pi k}(k/e)^{k}>e^{-k}k^{k}.$

Thus

$\displaystyle|\mathbb{E}e^{tX_{r}}-(1+t\mathbb{E}X_{r}+\frac{t^{2}}{2}\mathbb{E}X_{r}^{2})|$
$\displaystyle\leq 4\sum_{k=3}^{\infty}t^{k}(3.2e)^{k}\leq 8t^{3}(3.2e)^{3},$

as soon as $3.2et<1/2$. Thus we have

$\displaystyle\mathbb{E}e^{tX_{r}}$
$\displaystyle=1+t\mathbb{E}X_{r}+\frac{t^{2}}{2}\mathbb{E}X_{r}^{2}+O(t^{3}),\quad
t\to 0.$ Note that $\log(1+x)=x-\frac{1}{2}x^{2}+O(x^{3})$ as $x\to 0$. Since
$X_{r}$ is sub-exponential (Lemma 4), both $|\mathbb{E}X_{r}|$ and
$\mathbb{E}X^{2}_{r}$ are finite. Thus $\displaystyle\log\mathbb{E}e^{tX_{r}}$
$\displaystyle=t\mathbb{E}X_{r}+\frac{t^{2}}{2}\mathbb{E}X_{r}^{2}-\frac{1}{2}t^{2}(\mathbb{E}X_{r})^{2}+O(t^{3})$
$\displaystyle=t\mathbb{E}X_{r}+\frac{t^{2}}{2}\mathbb{V}X_{r}+O(t^{3}),\quad
t\to 0,$

since $\mathbb{V}X_{r}=\mathbb{E}X_{r}^{2}-(\mathbb{E}X_{r})^{2}$. ∎

######  Theorem 6.

Define $X_{r}$ to be a random variable with density $\nu(z,r)$ (see Definition
8). Then for $r\in[1/2,1]$,

$\displaystyle\phi(1/m,r)^{-m}$ $\displaystyle=2^{-\mathbb{E}X_{r}}+O(m^{-1})$
$\displaystyle\frac{\phi(2/m,r)^{m}}{\phi(1/m,r)^{2m}}$
$\displaystyle=1+(\log^{2}2)m^{-1}\mathbb{V}X_{r}+O(m^{-2}),\quad m\to\infty.$

Furthermore, for any $r\in[1/2,1]$, $(\log^{2}2)\mathbb{V}X_{r}<79$. We define
$\psi_{\mathbb{E}}(|F|)=\mathbb{E}X_{1-|F|^{-1}}$ and
$\psi_{\mathbb{V}}(|F|)=\mathbb{V}X_{1-|F|^{-1}}$.

###### Proof.

By construction, we have
$\phi(t,r)=\int_{-\infty}^{\infty}2^{tz}\nu(z,r)\,dz=\mathbb{E}2^{tX_{r}}$.
Then we have

$\displaystyle\log(\phi(1/m,r))$
$\displaystyle=\log\mathbb{E}2^{X_{r}/m}=\log\mathbb{E}e^{(\log 2)X_{r}/m}$ by
Lemma 5, as $m\to\infty$, $\displaystyle=((\log
2)/m)\mathbb{E}X_{r}+\frac{((\log 2)/m)^{2}}{2}\mathbb{V}X_{r}+O(m^{-3}).$

Thus we have

$\displaystyle\log(\phi(1/m,r)^{-m})$ $\displaystyle=(-m)\log(\phi(1/m,r))$
$\displaystyle=(-m)\left(((\log
2)/m)\mathbb{E}X_{r}+\frac{(\log(2)/m)^{2}}{2}\mathbb{V}X_{r}+O(m^{-3})\right)$
$\displaystyle=-(\log 2)\mathbb{E}X_{r}+O(m^{-1}).$
$\displaystyle\log\left(\frac{\phi(2/m,r)^{m}}{\phi(1/m,r)^{2m}}\right)$
$\displaystyle=m\log(\phi(2/m,r))-2m\log(\phi(1/m,r))$
$\displaystyle=m\left((2(\log
2)/m)\mathbb{E}X_{r}+\frac{(2\log(2)/m)^{2}}{2}\mathbb{V}X_{r}+O(m^{-3})\right)$
$\displaystyle-2m\left(((\log
2)/m)\mathbb{E}X_{r}+\frac{(\log(2)/m)^{2}}{2}\mathbb{V}X_{r}+O(m^{-3})\right)$
$\displaystyle=(\log^{2}2)m^{-1}\mathbb{V}X_{r}+O(m^{-2}).$

Note that $e^{x}=1+x+O(x^{2})$ as $x\to 0$. Thus

$\displaystyle\phi(1/m,r)^{-m}$ $\displaystyle=e^{-(\log
2)\mathbb{E}X_{r}+O(m^{-1})}=e^{-(\log
2)\mathbb{E}X_{r}}(1+O(m^{-1}))=2^{-\mathbb{E}X_{r}}+O(m^{-1}).$
$\displaystyle\frac{\phi(2/m,r)^{m}}{\phi(1/m,r)^{2m}}$
$\displaystyle=e^{(\log^{2}2)m^{-1}\mathbb{V}X_{r}+O(m^{-2})}=1+(\log^{2}2)m^{-1}\mathbb{V}X_{r}+O(m^{-2}).$

Finally, to bound $\mathbb{V}X_{r}$, note that

$\displaystyle\mathbb{V}X_{r}$
$\displaystyle=\mathbb{E}X_{r}^{2}-(\mathbb{E}X_{r})^{2}\leq\mathbb{E}X_{r}^{2}$
by the moment bound (11) $\displaystyle\mathbb{E}X_{r}^{2}$ $\displaystyle\leq
4\cdot 3.2^{2}\cdot 2^{2}<164.$

We conclude that $(\log^{2}2)\mathbb{V}X_{r}<79$. ∎