Characterizing (up to permutations) finite sequences of real numbers

Question

Let $S=\{x_1,\cdots, x_N\}$ be a finite sequence of real numbers. I am interested in characterizing the family of functions $F$ such that for any $f\in F$ the function $$ c(\lambda) =\sum_{i=1}^{N}f(x_i-\lambda),\;\lambda \in \mathbb{R} $$ uniquely identifies the sequence $S$ up to element permutations. My intuition is that, for example, any monotonic (not constant) $f$ will work (true?). Any suggestion how to characterize $F$ even partially?

Answer 1

This requirement may be rephrased as follows: $f$ does not satisfy no non-trivial relation of the form $\sum f(t+x_i)=\sum f(t+y_i)$. At first, the set of functions satisfying such a relation is a linear space. This may be seen from rewriting relation symbolically as $(\sum T^{x_i}-\sum T^{y_i}) f=0$, where $T$ is a shift operator: $(Tf)(t)=f(t+1)$. Multiplying two non-trivial quasipolynomials in $T$ we again get a non-trivial quasi-polynomial.

In particular, this linear space contains polynomial function (of any degree), functions $c^t p(t)$ for polynomials $p$ and complex numbers $c$ (like $f(t)=t^2 \cos (e t)$ or $\pi^t$.) On the other hand, $f$ may be a function like $[t]$.

Of course, 'most' functions do not belong to this linear space.

Answer 2

It is easy to show that if $f(x)$ is continuous and increasing in one interval, and continuous and decreasing in another interval, then sets of $\{c_\lambda \}$ leave an ambiguity in the $x_i$. So consider the restriction $F^+$ of $F$ to only non-decreasing functions (and in the end, take the union of this with its negative).

The information provided by $\{c_\lambda \}$ consists of the gaps of reals not in $\{c_\lambda \}$. If $f \in F^+$ is continuous, then $\{c_\lambda \}$ may have upper and/or lower bounds, but will have no gaps in between, so the information is inadequate to specify the $x_i$ uniquely.

Suppose $f(x)$ is discontinuous at one point $u$ and let $f(x)$ be unbounded (either below or above). Then we can always choose the $x_i$ so as to "mask" the gap exopsed by the discontinuity for any specific $x_i$. So if $f \in F^+$ it is non-decreasing and bounded.

Suppose $f(x)$ is discontinuous at one point $u$ and let $$ \inf(f(x)) = A > -\infty\\ \lim_{x\to u^-} f(x) = B \geq A \\ \lim_{x\to u^+} f(x) = C > B \\ \sup(f(x)) = D \geq C $$ (with $D < \infty$).

Then (by the same reasoning that requires $f(x)$ to be bounded) unless $$ C - B > (B-A) + (D-C) $$ the gap will not appear.

Any non-decreasing function $F(x)$ that is continuous everywhere except at a single point $x=u$ and has finite but different limits at $u$ from the left and the right will produce a set $\{c_\lambda \}$ that allows full determination of the $x_i$, as being at the gaps in the set $\{u- c_\lambda : \lambda \in \Bbb{R}\}$.

Finally, can there be additional discontinuities? There can! Let the sizes of additional discontinuities by $k_m$ and let $\sum_m k_m = K$. $K$ must be finite since $f(x)$ is non-decreasing and bounded. The gaps in the set $\{u- c_\lambda : \lambda \in \Bbb{R}\}$ can be separated into two distinct groups, one of which dictates the positions of the $x_i$ as before, provided $$ C-B > (B-A) + (D-C) + K $$

And this fully characterizes the $f(x) \in F^+$. Thake the union of this set of functions with their negatives to get $F$.

Answer 3

No polynomial will suffice for $f$ since sets with the same moments up to order equal to the degree of $f$ are indistinguishable. To determine the set, moments of order up to the size of the set are needed.

If $f(x) = e^x$, then $\sum f(x_i-\lambda) = e^{-\lambda}\sum e^{x_i}$ so no information can be obtained other than $\sum e^{x_i}$. So faster than polynomial growth is also insufficient in general.

However, if $f(x)$ is monotonic and increases faster than $e^x$, the set can be reconstructed. For example, if $f(x)=e^{x^\alpha}$ for $\alpha\gt 1$ then $\sum f(x_i-\lambda)$ is dominated by the largest $x_i$s as $\lambda\to -\infty$. Specifically, the sum is asymptotic to $me^{(x_{max}-\lambda)^\alpha}$ where $m$ is the number of times the largest value $x_{max}$ is in the set. From this $m$ and $x_{max}$ can be determined. Then remove $me^{(x_{max}-\lambda)^\alpha}$ from the sum and repeat.