Thinking about permutations

Consider a set $S$ with $|S|=n$ elements (where all elements of $S$ are distinct). We can build ordered lists of $n$ elements by taking elements from set $S$ and using them (with no repetition) to build $n$ -tuples. With $n$ elements we can build $n!$ distinct $n$ -tuples.

Let us think in terms of vectors in $\mathbb{R}^n$ , where each vector represents a particular ordered list of the elements of some set with $n$ elements. If $x, y \in \mathbb{R}^n$ are permutations of one another, then they contain the same elements, but in a different order; consequently, for every $p \in \mathbb{N}$ we have

$\displaystyle\sum_{i=1}^n x_i^p = \displaystyle\sum_{i=1}^n y_i^p$ .

Let $I: \mathbb{R}^n \times \mathbb{R}^n \rightarrow \{0,1\}$ be an indicator function, such that $I(x,y) = 1$ if and only if $x,y$ are permutations of one another ( $I(x,y)=0$ otherwise). Let $g_p: \mathbb{R}^n \rightarrow \mathbb{R}$ be defined as

$g_p(z) = \displaystyle\sum_{i=1}^n z_i^p$ ,

for all $p \in \mathbb{N}$ . We can then conclude that

$I(x,y) = 1 \Rightarrow g_p(x) = g_p(y), \quad{} \forall p \in \mathbb{N}$ .

The condition $g_p(x) = g_p(y), \quad{} \forall p \in \mathbb{N}$ is necessary. Is it sufficient?! In other words, if $g_p(x) = g_p(y), \quad{} \forall p \in \mathbb{N}$ is true, can we conclude that vectors $x,y$ are permutations of one another?

This is an interesting problem. Think about it!

Update (Jan. 25, 2008): this post was featured on the 25th edition (Silver Jubilee) of the Carnival of Mathematics.

About these ads

Tags: Combinatorics, Mathematics

This entry was posted on January 18, 2008 at 13:23 and is filed under Combinatorics, Mathematics, Puzzles. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

12 Responses to “Thinking about permutations”

ulfarsson Says:
January 18, 2008 at 15:54 | Reply
This is a nice problem. I believe the condition is sufficient: To simplify let’s assume we are working with vectors with non-negative entries.

Let $y_n$ be the largest entry in $y$ and likewise let $x_n$ be the largest entry in $x$ . Assume $x_n < y_n$ and furthermore assume that $y_n \neq 0$ because $y_n = 0$ implies that $y$ is the zero vector)

Now define two new vectors $u = x/y_n$ and $v = y/y_n$ . It will still be true that $g_p(u) = g_p(v)$ for all $p$ . Now look at the limit of this equation as $p$ goes to infinity. The left side will be approaching zero while the right side will not – it will approach 1 if $y_n$ is the unique largest entry in $y$ – otherwise it will approach the number of elements in $y$ equal to $y_n$ .

Did you make this problem up or is it part of some bigger theory?
rod. Says:
January 20, 2008 at 10:59 | Reply
ulfarsson,

Thanks for your comment :-)

If we assume that the vectors’ entries are non-negative, then $g_p(z) = \|z\|_p^p$ and we are thus trying to prove that two vectors with equal $p$ -norms for all $p \in \mathbb{N}$ are, by necessity, permutations of one another.

If I understood it right, your proof shows via reductio ad absurdum that two vectors with equal $\infty$ -norms must have the same maximum entry, i.e., $x_n = y_n$ .

I like that proof, but does that prove that the condition is sufficient? What we want to know is that if $g_p(x)=g_p(y)$ for all $p \in \mathbb{N}$ , then $x,y$ are permutations of one another. This was not supposed to be so hard to prove; we need to think harder!

I formulated this problem while thinking about the smooth sorting problem. I make no claims whatsoever that no one has ever formulated this problem before, but with tens of thousands of theorems, it’s hard to keep track of every single result!
Vishal Says:
January 20, 2008 at 11:09 | Reply
Nice one. It seems like based on ulfarsson’s solution, we can argue that we don’t need $p$ to be all the positive integers. If we choose $p$ to be just the even integers, then the same proof as above carries for $x, y \in \mathbb{R}^n$ with non-negative entries as well. In fact, as long as $p$ belongs to some infinite sequence of positive even integers, we are okay.
Vishal Says:
January 20, 2008 at 11:19 | Reply
Rod,
Ulfarrson’s proof does indeed show that $x_n = y_n$ . But, then, once we have established that, can we not use the same argument for the rest of the entries in $x, y \in \mathbb{R}^n$ . Repeating the argument, thus, $n$ times, we end up showing that $x$ and $y$ indeed have the same entries! Am I wrong?

Any hint on how you did the problem? :)
rod. Says:
January 20, 2008 at 11:43 | Reply
Vishal,

Thanks for your comments. I should let you know that I haven’t yet been able to prove that the condition is sufficient. I have asked some mathematicians, and they say that it’s probably sufficient. Nevertheless, no formal proof has yet been presented.

Ulfarsson’s proof shows that if $\|x\|_{\infty}=\|y\|_{\infty}$ , then

$\displaystyle\max_{i \in \{1,2, \ldots, N\}}{x_i} = \displaystyle\max_{i \in \{1,2, \ldots, N\}}{y_i}$ ,

which follows from the definition of the $\infty$ -norm. Like you suggested, I also thought of repeating Ulfarsson’s argument $n$ times and thus show that $x,y$ have the same entries. However, I think that is “cheating”: if we remove the highest entries from vectors $x,y$ and then apply Ulfarsson’s argument, we are assuming that the 2nd, 3rd, 4th, etc entries of $x,y$ are the same. That is not what we want to prove, right? Am I thinking correctly?
rod. Says:
January 20, 2008 at 15:09 | Reply
There’s another way of looking at this problem. Let’s make $y= x + e$ , where $e \in \mathbb{R}^n$ is an error vector. The equation

$\displaystyle\sum_{i=1}^n x_i^p = \displaystyle\sum_{i=1}^n y_i^p$

can therefore be rewritten as

$\displaystyle\sum_{i=1}^n x_i^p = \displaystyle\sum_{i=1}^n (x_i + e_i)^p$ .

Invoking the binomial theorem we have

$\displaystyle (x_i + e_i)^p = \sum_{l=0}^p \binom{p}{l} x_i^l e_i^{p-l}$ ,

and therefore

$\displaystyle\sum_{i=1}^n x_i^p = \displaystyle\sum_{i=1}^n \sum_{l=0}^p \binom{p}{l} x_i^l e_i^{p-l}$ .

We can thus write

$\displaystyle\sum_{i=1}^n x_i^p = \displaystyle\sum_{i=1}^n x_i^p + \displaystyle\sum_{i=1}^n \sum_{l=0}^{p-1} \binom{p}{l} x_i^l e_i^{p-l}$ ,

and finally

$\displaystyle\sum_{i=1}^n \sum_{l=0}^{p-1} \binom{p}{l} x_i^l e_i^{p-l} = 0$ .

Not sure how this might help, but it’s a different way of looking at things, right?
ulfarsson Says:
January 20, 2008 at 15:42 | Reply
Let’s keep working with vectors with non-negative entries to simplify things. Then what we can do is this: Start with arbitrary vectors $x$ and $y$ such that $g_p(x) = g_p(y)$ for all $p$ (or for all $p$ in some infinite subset of the natural numbers, like pointed out above). Now reorder the entries in $x$ and $y$ so the entries are in an increasing order. What we want to prove is that the vectors are now exactly the same. The proof above shows that the reordered vectors have the same last element. Throw those elements away to get new vectors $x^\prime$ and $y^\prime$ that will still satisfy the $g_p$ equation. Now repeat.

If we allow negative entries then it should be easy to generalize the argument to work.
rod. Says:
January 20, 2008 at 16:10 | Reply
ulfarsson,

Like I said before, I like your thinking, but I don’t know if it’s doable. We could reorder the entries of vectors $x,y$ so the entries are in increasing order, and we could use your proof to conclude that the largest entries are equal ( $x_n = y_n$ ), throw them away and build $(n-1)$ -dimensional vectors $x',y'$ .

Now here’s the problem. You say “now repeat”. But how? Your proof applied to the $\infty$ -norm case only. Besides, just because $g_p(x)=g_p(y)$ for all $p \in \mathbb{N}$ , does that mean that $\|x'\|_{\infty} = \|y'\|_{\infty}$ ?
ulfarsson Says:
January 20, 2008 at 16:38 | Reply
Let’s do this by induction: What we want to proof is that for any natural number $n$ is the following: If two vectors of length $n$ satisfy the $g_p$ equation for all $p$ then they have the same entries.

Base case: $n=1$ is obvious.

Assume this is true for some fixed $n$ and let’s look at two vectors of length $n+1$ that satisfy the $g_p$ equation for all $p$ . By the proof above these vectors have the same largest elements. Throw the largest elements away and you have two vectors of length $n$ that still satisfy the $g_p$ equation for all $p$ . By induction these vectors have the same entries and we are done.

I think this works, unless I’m completely missing something.
D. Eppstein Says:
January 26, 2008 at 04:11 | Reply
See Newton’s identities in Wikipedia: http://en.wikipedia.org/wiki/Newton's_identities
(particularly the section on computing coefficients from power sums).

I used this power sum technique for identifying a set of elements recently in a research paper: http://arxiv.org/abs/0704.3313
rod. Says:
January 26, 2008 at 14:01 | Reply
Prof. Eppstein,

Thanks for the suggestion. I will be taking a look at Newton’s identities.
Playing with Permutations « Reasonable Deviations Says:
July 24, 2008 at 22:32 | Reply
[...] Thinking about permutations [...]

Rod Carvalho

Thinking about permutations

Like this:

12 Responses to “Thinking about permutations”

Leave a Reply Cancel reply

Follow “Rod Carvalho”