# Algorithm for computing the sum of symmetric sums (better than $\mathcal{O}(2^N)$ )

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)$$.

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$$?
• But $x_1,x_2,...x_n$ are also variables.
• 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$.