Collectively describe and combine $N$ elements so that the result is invariant under permutation.

Question

I apologize that I am not a mathematician, but I got into this nice problem. :)

I have $N$ scalars defining $N$ properties $x_i$ for each integer $i = 1, 2, \dots, N$ associated with a corresponding set of $N$ elements that can undergo any kind of permutation. In other words, any vector obtained by a permutation of elements $x_i$ is an equally valid set for such properties.

1. What if now I want to describe "uniquely" (and without losing information) this set of properties, keeping in mind their permutation symmetry? Is there a way (e.g., a function, a linear combination) in which such $N$ objects $x_i$ could be combined to better describe their permutable ensemble?

Example. Suppose I want to describe a collection of five apples and their weights. Obviously, any vector obtained by the permutation of their five weights would describe it, but what if I want to find a unique representation? The sum or the product of all five weights are probably the most trivial way to globally represent it, but they are "reductive" and there must be a more general way to condense the whole information.

2. What happen instead if I have a set of properties that describe a property of two of such permutable objects? I guess a similar approach as above can be used.

Example. Suppose I want to collectively describe the spatial extension of a company that is occupying five identical buildings distributed on a geographical area. Suppose I can measure only the distance between each pair of buildings by $x_{ij}$. Now, to collectively describe such property, I would need to find a way to describe the $\frac12 N(N-1)$ distances according to the permutation symmetries (as all the buildings are identical).

Please note that sum or product would correspond to a reduction of the dimension and then alone their are not enough. Hence "describe" means to keep the maximum of information: so the function should ideally remain in $\mathbb{R}^N$.

I have also found some replies here, but this is not the most general case. I guess group theory would do that, but I am not sure how to implement it. Thank you.

Answer 1

You might want to use symmetric polynomials : in addition to the sum and the product, you consider the sums of products of $k$ distinct elements, for $k = 0 , ..., n$

These numbers code the information you want. To prove this, you can use polynomials. For $k= 0, ..., n$, define $\sigma_k := \sum_{I\subseteq \lbrace 1,..., n\rbrace, |I| = k} \prod_{i\in I} x_i$. Note that $\sigma_0 = 1$. Define the polynomial $P := \sum_{k=0}^n (-1)^k \sigma_k X^{n-k}$. You can check that $P = \prod_{i} (X-x_i)$. So the scalars $\sigma_k$ code the whole information, including possible doubles.

Example : $(X-x_1)(X-x_2)(X-x_3) = X^3 -(x_1+x_2+x_3)X^2 + (x_1x_2+x_2x_3+x_1x_3)X - x_1x_2x_3$. Since the information you want is coded by the polynomial $(X-x_1)(X-x_2)(X-x_3)$, you can code it using its coefficients.

Remarks :

1. These identities are used in model theory to code finite sets in fields, which is not so different from the OP's request.
2. If I gave you the vector of the $\sigma_k$, you would know the polynomial. So, in a sense, you would know the $x_i$, since they are its roots. Yet, you wouldn't have an explicit formula expressing the $x_i$ in terms of the $\sigma_k$. Now, there are algorithms to find approximate values for the roots of a polynomial. In our case, we know how to bound the values of the roots in terms of the coefficients of the polynomial, so we would know "where to search".