# Optimization over symmetric polynomials

Consider the following constraint satisfaction problem: Let $\alpha_1 , \ldots, \alpha_k \in \mathbb{R}$ be given as well as an error parameter $\epsilon$. Find $p_1, \ldots, p_n$ such that

(i) $0 \le p_1, \ldots, p_n \le 1$

(ii) For $1\le j \le k$, $|(\sum_{i=1}^n p_i^j) - \alpha_j|\le \epsilon$.

Here $k \ll n$. I am interested in the time complexity of this problem: In particular, based on some symmetry considerations, one can show that it suffices to restrict one's search to the case where $p_1, \ldots, p_n$ all come from a set of size at most k. Based on this observation, one can consider all possible ways of partitioning $p_1, \ldots, p_n$ into k sets (which takes time $n^k$) and subsequently solve a problem which requires one to solve polynomial equations over the reals (in k variables and of degree bounded by k). This takes time $k^k$. The dependence of n^k is prohibitive for me and I was wondering if there is a way to solve this in time $O(n^{O(1)} \cdot k^{k})$ or at least better than $n^k$.

• cross-posted: cstheory.stackexchange.com/questions/30678/… – usul Mar 4 '15 at 3:47
• @Anindya De Can you give some context to this question? Like any paper that motivated you to ask this? – user6818 Mar 4 '15 at 20:32
• So you are looking for numbers whose norms are bound? Did you try simplest case $\alpha_j=\alpha$? – 1.. Mar 5 '15 at 4:20
• In a sense you are looking at intersection of $k$ varieties of polynomials $f_j(x_1,\dots,x_n)-\alpha_j-\eta=0$ where $\eta\in(-\epsilon,\epsilon)$ with cube $[0,1]^n$? – 1.. Mar 5 '15 at 4:27
• Obviously intersection of $f_j(x_1,…,x_n)−α_j−η=0$ will have a solution in $(x_1,\dots,x_k,0,\dots,0)$. However this may lie elsewhere outside $[0,1]^n$. – 1.. Mar 5 '15 at 5:54

The system has a very special structure, that prompts a different approach (classically known as Prony method): one can parametrise the $p_i$ as the roots of a polynomial $f(t)=\sum_{\ell=0}^n f_\ell t^\ell.$ Then for the case $\epsilon=0$ and $k\gg n$ one has that $(f_0,\dots,f_n)$ is in the kernel of the Hankel matrix $$\begin{pmatrix}a_1&a_2&\dots &a_n\\ a_2& a_3&\dots &a_{n+1}\\ \dots\\ a_n& a_{n+1}&\dots & a_{2n-1} \end{pmatrix}$$ as you can multiply the (truncated) Vandermonde matrix depending on $p_i$ by $(f_0,\dots,f_n)^\top$ (and by the corresponding vectors of coefficients of $tf(t)$, $t^2 f(t)$, etc.) on the left, obtaining zeros, which should equal to the scalar product of $(f_0,\dots,f_n)^\top$ (and by the corresponding vectors of coefficients of $tf(t)$, $t^2 f(t)$, etc.) and $(a_1,a_2,\dots)$.
• I forgot to add: In our case, $k \ll n$. – Anindya De Mar 4 '15 at 3:33