6
$\begingroup$

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?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.