Is there way to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$ faster than $O(n^3)$

Question

Given array $A$ of size $n$, we want to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$. Is there way to speed this up rather than the standard $O(n^3) $ calculation with 3 for loops. I haven't worked with sums so I don't know their properties, but I was thinking if there is some way to rewrite the formula to get faster calculations.

Answer 1

Let $A = \sum_{i=1}^n A_i$. We have $$ \begin{align*} A^3 &= \sum_{i=1}^n A_i^3 + 3\sum_{i=1}^n \sum_{j \neq i} A_i^2 A_j + 6 \sum_{i < j < k} A_i A_j A_k \\ &= \sum_{i=1}^n A_i^3 + 3 \sum_{i=1}^n A_i^2 (A - A_i) + 6 \sum_{i < j < k} A_i A_j A_k. \end{align*} $$ This gives a linear time algorithm.

More generally, the theory of symmetric polynomials ensures that every symmetric polynomial can be computed in linear time, since it is a polynomial in the quantities $B_d := \sum_{i=1}^n A_i^d$. For example, $$ \sum_{i<j<k} A_i A_j A_k = \frac{B_1^3+2B_3-3B_1B_2}{6}. $$