As a key application of our lower bound techniques, we provide a space
lower bound for \((1\pm \varepsilon )\) -approximating the Hamming norm in the strict turnstile model.
This problem, which is also known as the \(L_0\)  norm estimation and denoted by \( \textsc {T} _\varepsilon \) , requires estimating \({\left\Vert  {\mathbf {x}} \right\Vert }_0 :=|{\left\lbrace {i x_i \ne 0} \right\rbrace }|\)  of a vector \(\mathbf {x} = (x_1, \ldots , x_N)\)  and outputting an estimate \(\widetilde{F}\)  for which \((1-\varepsilon ){\left\Vert  {\mathbf {x}} \right\Vert }_0\le \widetilde{F} \le (1+\varepsilon ){\left\Vert  {\mathbf {x}} \right\Vert }_0 \)  with constant probability.
The vector \(\mathbf {x}\)  is initialized to all zeros and undergoes a sequence of \(m\)  updates each of the form
\((i,v)\in [N]\times [\pm M]\) ,
where \([\pm M]:={\left\lbrace {0,\pm 1,\dots ,\pm M} \right\rbrace }\)  and each update \((i,v)\)  causes \(x_i\leftarrow x_i+v\) .
In the strict turnstile model \(x_i \ge 0\)  holds for all \(i\)  and at all points in the stream.
We obtain an \({\Omega \left( {\varepsilon ^{-2}\log (N)\log \log (mM)} \right)}\)  bits of space lower bound for \((1\pm \varepsilon )\) -approximating the Hamming norm.
This lower bound matches the best known upper bound \({{O} \left( {\varepsilon ^{-2}\log (N)\left(\log (1/\varepsilon )+\log \log (mM)\right)} \right)}\)  [1]} for any \(\varepsilon \ge 1/\mathsf {polylog}(mM)\) .
Note that \(\varepsilon \ge 1/\mathsf {polylog}(mM)\)  is required in order to obtain polylogarithmic space, and so is the most common setting of parameters.
Perhaps surprisingly,
there is an upper bound of \({{O} \left( {\varepsilon ^{-2}\log (mM)} \right)}\)  bits of space for \((1\pm \varepsilon )\) -approximating
\(L_p\)  for \(p>0\)  [2]} (improving an earlier \({{O} \left( {\log ^2 N} \right)}\)  bound of [3]}; see also a time-efficient version in [4]}),
and thus we provide
a strict separation in the complexities for \(p = 0\)  and \(p > 0\) .
The Hamming norm has many applications, as it corresponds to estimating the number of distinct values, and can be used to estimate set union and intersection sizes (see [5]} where it was introduced).
