In today's blog, I will focus on a very interesting result from Augustin-Louis Cauchy. He discovered that there are limits to the number of values a function of multiple parameters can take when you change the order of the parameters. The content in today's blog is taken from Peter Pesic's Abel's Proof
.Joseph-Louis Lagrange had shown that the number of values a function of n parameters can take from permuting parameters will necessarily divide n!. I went over this result in a previous entry.
Cauchy found additional limits on the number of values a function can take. For a function with n parameters, if p is the highest prime that divides n, then the function can take 1, 2, or at least p possible values from permuting the order of its parameters.
That a function with n parameteres can take 1 value is easy to show. Consider the following function:
f(x1, x2, ..., xn) = x1 + x2 + ... + xn
Clearly, swapping any two parameters doesn't change the value so it is clear that no permutation will change its value. In this case, the function of n parameters can only take on 1 value.
It is also easy to show a function of n parameters can take on 2 values. Consider the following function:
f(x1, x2, ..., xn) = (x1 - x2) *(x1 - x3)*... *(x1 - xn)*...*(xn-1 - xn)
Now, any swap of two parameters will keep the absolute value but change the sign of the function. So, the absolute value stays the same.
So, this is where Cauchy's Theorem comes in. Cauchy proves that if a function of n parameters takes on more than 2 values, then it necessarily takes on at least p values where p is the highest prime dividing n.
Here's an example where this occurs. Consider the following function:
f(x1, x2, x3, x4, x5) = (x1 + x2 + x3 + x4) - x5
How many values can this function take on if we permute the parameters? Since swapping x5 changes the value of the function, we can see that there are at least 5 possible values (1 + 4) that the function can take.
Let's start out with some definitions:
Definition 1: f(P)u
Let P be a permutation and let f(P)u represent the value of the function after the permutation P is applied to the function f, u times. I will use f(P)0 to mean that the permutation has been applied 0 times.
Definition 2: Order of a Permutation
A permutation P is said to be of order k if Pk(f(x1, ..., xn)) = f(x1, ..., xn). Using the above notation, this means that f(P)k = f(P)0.
In other words, the permutation after being applied k times return the function to its original ordering of the parameters.
Definition 3: f(P)-u
By -u, I mean the inverse of the permutation. Since each permutation is one-to-one and onto, (see here for review if needed), it follows that it has an inverse which is also a permutation. f(P)-u means that we apply the inverse of the permutation u times.
This gives us the result that if we apply the permutation P u times to f(P)-u, we are left with f(P)-u+u = f(P)0
Now, I will use these definitions in the following lemmas from Cauchy:
Lemma 1:
Let f be a function that takes n parameters.
Let p be the largest prime that divides n
Let m be the number of values that f takes on when we permute the order of f's parameters.
If m is less than p, then any permutation of order p will leave the value of f unchanged.
Proof:
(1) Let P be a permutation of order p such as (x1 → x2 → x3 → ... → xp → x1)
(2) So, we have f(P)p = f(P)0
(3) Now, let's consider the set of p-1 orderings that f takes as we apply P to f:
f(P)0, f(P)1, f(P)2, ..., f(P)p-1
(4) Since we are assuming that m is at most p-1, it follows that two of these values must be the same.
(5) Let's label them r and r' where 0 ≤ r' ≤ p-2 and 1 ≤ r ≤ p-1 and further r' is less than r so that:
f(P)r = f(P)r'
(6) Now since both r, r' are less than p, we know that p-r ≥ 1.
(7) Now, if we apply the permutation P to both values (p-r) times, we get:
f(P)r+p-r = f(P)r'+p-r
(8) Since r+p-r = p and f(P)p = f(P)0, we are left with:
f(P)0 = f(P)r'+p-r
(9) Let j = r'+p-r so that we have:
f(P)0 = f(P)j
(10) We can see that f(P)0 = f(P)bj where b is any integer that we choose since:
(a) For b=1, this is clearly the case from step #9.
(b) We assume it is true up to b-1 so that:
f(P)0 = f(P)(b-1)j = f(P)bj-j
(c) Now, we apply P to each side j times so that we have:
f(P)0+j = f(P)bj-j+j
(d) This gives us that:
f(P)j = f(P)bj
(e) Applying step #9 gives us:
f(P)0 = f(P)bj
(f) We can make the same argument for the case when b is negative.
(g) Let P-1 be the inverse permutation of P.
(h) Apply P-1 j times to each value in step #9 gives us:
f(P)-j = f(P)0
(h) Now, we assume that it is true up to b-1 so that we have:
f(P)-j(b-1) = f(P)-bj+jf(P)0
(i) Now, we apply P-1 j times to each side to get:
f(P)-bj = f(P)-j
(j) Applying step #10i gives us:
f(P)-bj = f(P)0
(11) Now, we know that j is a number less than p since j = r' + p - r and r is greater than r'.
(12) Since p is prime, it follows that gcd(p,j)=1 and using Bezout's Identity, we know that there exists integers a',b such that:
a'p + bj = 1
(13) Let a = -a', then we have:
-ap + bj = 1
which is the same as:
bj = ap + 1
(14) Appyling this equation to f gives us:
f(P)bj = f(P)ap+1
(15) From step #10 this gives us that:
f(P)0 = f(P)ap+1
(16) But from step #2, this gives us that:
f(P)0 = f(P)ap
(17) This means that:
f(P)ap = f(P)ap+1
(18) But this is only possible if P doesn't change the value of the function.
QED
Let's explore Lemma 1 in more detail. Consider our function with 2 values where:
f(x1, x2, x3) = (x1 - x2)*(x1 - x3)*(x2 - x3)
Since n=3, the highest prime is 3. Let's see how many permutations there are with the order of 3.
P = (x1 → x2 → x3 → x1)
So, applying P once gives us:
f(P)1 = (x2 - x3)*(x2 - x1)*(x3 - x1) = (x2 - x3)*(-1)*(x1 - x2)*(-1)*(x1 - x3) = (x1 - x2)*(x1 - x3)*(x2 - x3)
So, we see that Lemma 1 holds.
Now, it turns out that this lemma has a surprising corollary.
Corollary 1.1:
Let f be a function that takes n parameters.
Let p be the largest prime that divides n
Let m be the number of values that f takes on when we permute the order of f's parameters.
If m is less than p, then any permutation of order 3 will leave the value of f unchanged.
Proof:
(1) Let P1 be a permutation of order 3 which we can define as xi1 → xi2 → xi3 → xi1
(2) I will show that it is equivalent to application of two permutations of order p.
(3) Let P2 be the permutation of order p such that:
xi1 → xi2 → ... → xip
We can view this as (1234...p)
(4) Let P3 be another permutation of order p such that:
xi2 → xi3, xi3 → xi1, xi4 → xi2, xi5 → xi4, xi6 → xi5, ..., xi1 → xip
We can view this as (1p...5423)
(5) Now, if we perform the first permutation (P2) and then the second (P3), we get:
xi1 → xi2 → xi3, xi2 → xi3 → xi1, xi3 → xi4 → xi2, xi4 → xi5 → xi4, xi5 → xi6 → xi5, ..., xip → xi1 → xip
(6) In other words, we have the three-order permutation:
xi1 → xi2 → xi3 → xi1
(7) Since both order-p permutations of step #3 and step #4 do not change the value of the function and since P1 = P3(P2), it follows P1 does not change the value of the function.
QED
Let's see this result in action. Let's revise our example above to now have 5 parameters so that we have n=5, p=5 and the number of different values are 2:
f(x1, x2, x3, x4, x5) = (x1 - x2)*(x1 - x3)*...*(x2 - x3)...*(x4 - x5)
Now, let's see what happens when we apply the following permutation of order 3:
P = (x1 → x2 → x3 → x1)
We get:
f(P)1 = (x2 - x3)*(x2 - x4)*...*(x4 - x5)
Now, we only need to consider the cases where the the first element is greater than the second element. This occurred twice so that we now have:
(x2 - x1)*(x3 - x1)
But if it occurs only twice, then we have:
(-1)*(x1 - x2)*(-1)*(x1 - x3) = (x1-x2)*(x1 - x3)
So, we see that the corrollary holds.
Cauchy was able to take this result one step farther:
Corollary 1.2:
Let f be a function that takes n parameters.
Let p be the largest prime that divides n
Let m be the number of values that f takes on when we permute the order of f's parameters.
If m is less than p, then application of any two permutation of order 2 will leave the value of f unchanged.
Proof:
(1) Let P1 be an order-2 permutation such that:
xj1 → xj2
(2) Let P2 be an order-2 permutation with overlap with P1
xj2 → xj3
(3) So, we can define an order-3 permutation that is equivalent to the application of these two permutations of order 2:
xj1 → xj2 → xj3
(4) Again, we know that application of the two overlapping order-2 permutations cannot change the value. If they did, this would imply that the above order-3 permutation would also change the value which goes against Corollary 1.1 above.
(5) Let's redefine P2 so that it does not overlap with P1 so that:
xj3 → xj4
(6) But in this case, it is equivalent to application of two order-3 permutations.
(7) Let us define P3 as:
xj1 → xj2→ xj3
(8) And define P4 as:
xj3 → xj1 → xj4
(9) We can see that they are equivalent since we now have:
xj1 → xj2 → xj2
xj2 → xj3 → xj1
xj3 → xj1 → xj4
xj4 → xj4 → xj3
(10) Again, the application of two order-2 permutations cannot change the value since the application of two order-3 permutations cannot change the value.
QED
Now, we are ready for Cauchy's main theorem.
Theorem 2: For a function with n parameters, if p is the highest prime that divides n, then the function can take 1, 2, or at least p possible values from permuting the order of its parameters.
Proof:
(1) To prove this theorem, we only need to prove that if the number of values is less than p, then it is 1 or 2.
(2) Assume that the number of values that the function takes is less than p.
(3) Assume further that the number of values is at least 3.
(4) Let's label them V1, V2, V3
(5) Let's define a permutation P1 as the reordering of V1 so that it becomes V2 so that:
Let V1 = f(xi1, xi2, ..., xin)
Let V2 = f(xj1, xj2, ..., xjn)
Then P1 = (xi1 → xj1, ..., xin → xjn)
(6) Now, we know that P1 is an order 2 permutation since:
(a) We can view P1 as sequence of order 2 permutations (see step 5 above)
(b) Each of the permutations is either changing the value or keeping the value. By Corollary 1.2 above, if one of the permutations changes the value, then any order-2 permutation applied to it must undo the change.
(c) So, clearly if the value changes, only of the sequence of order-2 permutations changes the value.
(7) Using the same logic as step #5, we can define a permutation that changes V2 to V3 and we can assume that this permutation consists of a sequence of order-2 permutations.
(8) But by the same logic as step #6, P2 must also be an order-2 permutation.
(9) But now we have a contradiction since if we can apply P1 to V1 to change the value to V2 and we can apply P2 to V2 to change the value to V3, then we have a situation where application of two 2-order permutations results in a change of value which contradicts Corollary 1.2.
(10) Therefore, we must reject our assumption in step #3 and assume that the number of values is at most 2.
QED
References
- Peter Pesic, Abel's Proof: An Essay on the Sources and Meaning of Mathematical Unsolvability, The MIT Press, 2004.