# Approximating an integral representation of the Number Partition Problem

One can write out an integral whose solution gives the number of solutions to the NP-Complete Number Partition Problem and I'm wondering if anyone has an suggestions or ideas on who to solve or approximate this integral analytically or numerically.

Given $a_0, a_1, \dots, a_{n-1} \in \mathbb{Z}$, the Number Partition Problem asks for a partition of the $a_k$'s such that $\sum_{k=0}^{n-1} \sigma_k a_k = 0$, where $\sigma_k \in \{ -1,1 \}$.

Consider the following Integral:

$$I(a_0, a_1, \dots, a_{n-1}) = \frac{1}{2 \pi} \int_{-\pi}^{\pi} \prod_{k=0}^{n-1} (e^{ i a_k \theta } + e^{ -i a_k \theta } ) d\theta$$

$I(\dots)$ will count the number of solutions for a given instance of $(a_0, a_1, \dots, a_{n-1})$. Solving this integral is worse than NP-Hard (it's #P) so asking for a general solution is out of the question. But can one do any sort of approximation, either analytically or numerically? If you choose the $a_k$'s with some distribution, say uniform on some interval, can you exploit that randomness to help you approximate this integral?

Any ideas would be appreciated.

note: This has been studied by Borgs et all for the NPP Phase Transition and that's where I first saw this integral representation of the Number Partition Problem, but their analysis relies on approximating the family of instances given a uniform distribution on the $a_k$'s rather than trying to solve a particular instance, as I'm trying to do above.

-

1
I do not see the point of crossposting a question like this. Answers improve one another if everyone can see everyone else's answers; insights from different answers can be combined. Splitting up the answers like this seems counterproductive to me. – Qiaochu Yuan Dec 3 '10 at 17:12
There was one answer from the mathoverflow site, otherwise it is essentially unanswered. Should I add a comment on what has been suggested already? – user4143 Dec 3 '10 at 17:17

1
Depending on how big the $a_k$ are and how many terms that product has, the integrand can be violently oscillatory, and quite a lot of the usual numerical methods will have trouble with this. Turning this into a contour integral might make it slightly more tractable, though. – J. M. Dec 4 '10 at 13:17
– user4143 Dec 4 '10 at 16:11
Presumably if $\theta$ goes from $-\pi$ to $\pi$, you don't need the additional $2\pi$ in the exponents. – mjqxxxx Jan 20 '11 at 16:06
show 3 more comments

## 1 Answer

Using a discrete Fourier transformation seems more appropriate if the $a_i$ are integers. The number of solutions is the value of the convolution product $$\left(\delta_{a_0} + \delta_{-a_0}\right) * \left(\delta_{a_1} + \delta_{-a_1}\right) * ... * \left(\delta_{a_{n-1}} + \delta_{-a_{n-1}}\right)$$ evaluated at 0. This has the obvious dynamic programming solution, which takes something like $O(n A)$ time, where $A = \sum_i |a_i|$; i.e., it is a quasi-polynomial-time algorithm. If the $a_i$ are chosen at random from (bounded) distributions of integers instead, then the dynamic programming solution takes $O(n A^2)$ to calculate the expected number of solutions. The discrete Fourier transform translates that problem to a direct product of $n$ functions over $O(A)$ points, each of which can be computed in $O(A \log A)$ using the FFT, reducing the total time to $O(nA \log A)$. Moreover, the number of "approximate" partitions, i.e., choices of the $\sigma_i$ such that $|\sum_{i=0}^{n-1}\sigma_i a_i| \le k$ for some small $k$, falls out of this calculation essentially for free.

-

– user4143 Jan 21 '11 at 0:24
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 25, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9232707023620605, "perplexity_flag": "head"}