I read somewhere that you can compute the cardinality of sumsets by computing the convolutions of the characteristic vectors of the given sets, and that this can be done efficiently using Fast Fourier Transform. How would this work?


Here is a sketch of the main ideas. Let $S,T \subseteq \mathbb{N}$ be two multisets of non-negative integers, and define $S+T$ to be the multiset

$$S+T = \{s+t \mid s \in S, t \in T\}.$$

Let $\chi_S$ represent the characteristic vector of a set $S$. Then

$$\chi_{S+T} = \chi_S * \chi_T,$$

where $*$ is a convolution operator.

The Fourier transform $\mathcal{F}$ has the property that

$$\mathcal{F}(f*g) = \mathcal{F}(f) \times \mathcal{F}(g),$$

where $\times$ represents pointwise multiplication of functions. Therefore,

$$\mathcal{F}(\chi_{S+T}) = \mathcal{F}(\chi_S) \times \mathcal{F}(\chi_T),$$

and in particular,

$$\chi_{S+T} = \mathcal{F}^{-1}(\mathcal{F}(\chi_S) \times \mathcal{F}(\chi_T)).$$

This gives us a method to compute $S+T$. We can compute the characteristic vector $\chi_{S+T}$ for the multiset $S+T$ by computing $\mathcal{F}(\chi_S)$, the Fourier transform of the characteristic vector for $S$, and $\mathcal{F}(g)$; multiplying them; and then applying the inverse Fourier transform to the result. Each of these steps can be implemented efficiently using the Fast Fourier transform. The end result will be $\chi_{S+T}$, from which we can reconstruct $S+T$ or its cardinality.

The overall running time will be $O(n \log n)$, where $n$ is an upper bound on the largest element of $S,T$.


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.