1
$\begingroup$

Let denote $\mathbf{x} = \{x_1,x_2,...,x_N \}$ with $x_i \in \Bbb R$ for $i=1,...,N$ and $f(\mathbf{x},n)$ be the $n$-th symmetric sum of the set $\mathbf{x}$

$$ f(\mathbf{x},n) = \sum_{\sigma_1,...,\sigma_n} \left(\prod_{i=1}^n x_{\sigma_i}\right) $$ with $\sigma_1,...\sigma_n \in \{1,2,...,N \}$ and $\sigma_i \ne \sigma_j$ for $i\ne j$

(the definition of the $n$-th symmetric sum can also be found here)

Let define $g(\mathbf{x},a)$ be the sum of symmetric sum $$ g(\mathbf{x},a)= \sum_{n=0}^N a^{\mathbb{mod}(n,2)} f(\mathbf{x},n) $$ with $a \in \Bbb R$ and $\mathbb{mod}(n,2) = \begin{cases} 1 \quad \text{ if } n \text{ odd} \\ 0 \quad \text{ if } n \text{ even} \end{cases}$

Example 1: N = 2: $$ g(\mathbf{x},a)= 1 - a(x_1 +x_2) + (x_1 x_2) $$

Example 2: N = 3: $$ g(\mathbf{x},a)= 1 - a(x_1 +x_2+x_3) + (x_1 x_2+x_2 x_3+x_3 x_1) - a x_1 x_2 x_3 $$

The complexity of $g(\mathbf{x},a)$ is $\mathcal{O}(2^n)$ with a naive algorithm. Indeed, the sum $g(\mathbf{x},a)$ has exactly $2^N$ terms and we sum up the terms sequentially

$$ g(\mathbf{x},a)= \sum_{n=1}^N\left( a^{\mathbb{mod}(N,2)} \sum_{\sigma_1,...,\sigma_n} \left(\prod_{i=1}^n x_{\sigma_i}\right)\right) $$

My question: does there exist a better algorithm for computing $g(\mathbf{x},a)$ which is less complex than $\mathcal{O}(2^N)$?

My attempt: There exists special cases where $a=\pm 1$ that can factorize the sum $g(\mathbf{x},a)$ as follows $$ g(\mathbf{x},a)= \prod_{n=1}^N(x_i+a) $$ and then the sum can be computed in $\mathcal{O}(N)$. I try to find a mathematical method like this for $a \ne \pm 1$ without success. In fact, all difficulties lie on the modulo function $\mathbb{mod}(n,2)$.

$\endgroup$
3
$\begingroup$

But $g(x,a)$ is linear in $a$ so if you can compute it efficiently for two different values of $a$ then you can compute it efficiently for all $a$?

$\endgroup$
3
  • 1
    $\begingroup$ But $x_1,x_2,...x_n$ are also variables. $\endgroup$
    – NN2
    May 19 at 17:47
  • 1
    $\begingroup$ But as a function of $a$ it is linear for each $x$, so simply compute $g(x,-1)$ and $g(x,+1)$ and fit a line through these points to get $g(x,\cdot)$ for this particular $x$. $\endgroup$
    – prim
    May 19 at 17:51
  • 1
    $\begingroup$ Yes, you are right. The problem becomes simple from this angle. Thank you for your answer! $\endgroup$
    – NN2
    May 19 at 17:56

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.