Let $R =\mathbb{Z}/N \mathbb{Z}$. Let $f:R\to \mathbb{R}$, $\rho:R\to \lbrack 0,1\rbrack$. We assume that it takes trivial time to compute any given value $f(m)$ or $\rho(m)$.

Define $$S(\delta,m) = \sum_{n\in R: \rho(n)\geq \delta} f(n+m).$$

Is it possible to compute $S(\delta,m)$ efficiently? To be precise: say we are given $\delta_i\in \lbrack 0,1\rbrack$, $m_i\in R$ for $1\leq i\leq N$. Is it possible to compute $S(\delta_i,m_i)$ for all $1\leq i\leq N$ in roughly linear time on $N$ (or some other time substantially smaller than $N^2$)?

To see why this might not be an unreasonable request, consider the two following extreme cases.

If all $m_i=0$ (or all $m_i$ are equal), we can compute the $N$ sums $S(\delta_i,m_i)$ easily in linear time.

If all $\delta_i=0$ (or all $\delta_i$ are equal), we can compute the $N$ sums $S(\delta_i,m_i)$ in roughly linear time (more precisely: $O(N \log N)$) using FFT. The reason is that $S(\delta,m_i)$ equals $F(m_i)$, where $F$ is the convolution of $f$ with the function $g(n) = \begin{cases} 1 &\text{if $\rho(-m)>\delta$,}\\ 0 &\text{otherwise.}\end{cases}$.

Is the general problem feasible? Can it be shown not to be feasible?


1 Answer 1


Define $$L := [(p(i),i) : i \in [1..N]]$$ and sort this list with respect to $p(i)$, this takes $O(N\log N)$.
Define $$R := [(\delta_i,i) : i \in [1..N]]$$ and reverse-sort it with respect to $\delta_i$ (biggest first), also takes $O(N\log N)$.
Now, having these lists sorted, you can run over them both and add stuff. You add the first few elements of $L$ together, until things get smaller than the first $\delta$ in $R$. Then you add to that everything until things get smaller than the second $\delta$ in $R$, etc. So all the adding takes about $O(N)$, because you don't start new for every new $i$ but only add to what you already have, giving us a total time of $O(N\log N)$.

  • $\begingroup$ I'm not sure of the meaning of some of your notation: what is $p(i)$? Where does $m_i$ come in? Are you sure you are not doing the case of $m_i$ constant? $\endgroup$ Aug 2, 2018 at 14:03
  • $\begingroup$ If $R = \mathbb{Z}/N\mathbb{Z}$, we can represent every element in $R$ by a number in $[1..N]$, that's why I wrote $p(i)$. Thinking about it again, I'm not entirely sure myself anymore where I put the $m_i$; should I remember it I will edit it in; but maybe I did do the case of constant $m_i$, sorry... $\endgroup$
    – Dirk
    Aug 6, 2018 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.