Let’s play a game:
You build an ordered list of real numbers, and you conceal it from me. You then compute for each , and you give me the -tuple . Finally, I build a list of real numbers such that for all . Can I conclude that my list is a permutation of yours (or equal to it)?
Each ordered list of elements is an -tuple. We can also think of an ordered list of reals as a vector in , where the list’s -th element is the vector’s -th entry.
The following 3-stage diagram hopefully clarifies the essence of this -player game:
where I am player #1, and you’re player #2. The game’s three stages are:
- player #2 builds an ordered list , but player #1 doesn’t have access to it.
- player #2 gives player #1 the “measurements” , where .
- player #1 builds ordered list from such that for all .
We know that it’s always possible to build list , because if is equal to or a permutation of , then all equality conditions
will be satisfied. What we don’t know is whether any list that satisfies the equality conditions will be a permutation of . In more rigorous terms: if are permutations of one another, then it is necessary that the equalities hold. What we would like to know is whether the fact that the equalities hold is sufficient for us to conclude that are permutation of one another.
But how can player #1 build the desired ordered list? A possibility would be for player #1 to solve the following system on polynomial equations in variables
where is a contant, and is a variable.
The game I propose on this post stems from two closely related problems I have been thinking of since January 2008. I have written a few posts on these problems already: