Formally, in the Hamming norm estimation problem there is an underlying vector \((x_1,\dots , x_N)\)  which starts from the all zero vector and processes up to \(m\)  updates each of the form \((i,v)\in [N]\times [\pm M]\) .
The update \((i,v)\)  means one should add \(v\)  to the \(i\) -th coordinate \(x_i\)  in the vector \(x\) .
After processing all \(m\)  updates, we have \({\left\Vert  {x} \right\Vert }_0 =|{\left\lbrace {ix_i\ne 0} \right\rbrace }|\)  and we want to output a number within \((1\pm \varepsilon )\Vert x\Vert _0\)  with probability \(\ge 2/3\) .
The strict turnstile model guarantees that \(x_i \ge 0\)  for all \(i \in [N]\)  at all positions in the stream,
in which case it suffices to prove the space lower bound in the simultaneous communication model following the reduction in Theorem 4.1 of [1]}.
Furthermore, it is also guaranteed that for every \(i \in [N]\) , \(x_i \le \mathsf {poly}(n)\)  at the end of the stream.
In this setting, the algorithm of [2]} approximates \(\Vert x\Vert _0\)  up to a \((1 \pm \varepsilon )\)  factor with \({{O} \left( {\varepsilon ^{-2}\log (N) \left(\log (1/\varepsilon ) + \log \log (mM) \right)} \right)}\)  bits of spaceIndeed, their algorithm stores \({{O} \left( {\varepsilon ^{-2}\log N} \right)}\)  counters modulo primes that are each \({{O} \left( {\log (1/\varepsilon ) + \log \log (mM)} \right)}\)  bits in magnitude, and it does not matter how large the values of \(x_i\)  are at intermediate positions in the stream., as long as \(\varepsilon > 0\) .
