# Number of distinct $f(x_1,x_2,x_3,\ldots,x_n)$ under permutation of the input

$\alpha _n ^n-1=0$

$\alpha _n=e^{2 \pi i/n}$

$$f(x_1,x_2,x_3,\ldots,x_n)=(x_1+\alpha _n x_2+ \alpha _n ^2 x_3+\cdots+\alpha _n ^{n-1} x_n)^n$$

I have read in Jim Brown's paper on page 5 that Lagrange showed

If n=3 then $f(x_1,x_2,x_3)$ Maximum can have 2 different results with all permutations of $(x_1,x_2,x_3)$

If n=4 then $f(x_1,x_2,x_3,x_4)$ Maximum can have 3 different results with all permutations of $(x_1,x_2,x_3,x_4)$

If n=5 then $f(x_1,x_2,x_3,x_4,x_5)$ Maximum can have 6 different results with all permutations of $(x_1,x_2,x_3,x_4,x_5)$

but no proof how he did that result.

According to the Paper, It was an important result for insolvability of quintic via radicals. Thus I searched the paper of Lagrange (Lagrange's 1771 paper reflections on the Algebraic theory of Equations ) in the internet but I could not find it.

Jım Brown's paper does not mention the general solution for n.

What is the general formula of how many different values can have $f(x_1,x_2,x_3,\ldots,x_n)$ with all permutations of $(x_1,x_2,x_3,\ldots,x_n)?$ Any idea to find the general formula for n?

or if it is not possible for all n , at least to show a way how easily to proof for n=3,n=4 and n=5 (I tried to do that n=3 is relatively easy but need a lot calculation in classic approach as binomial expansion). Could you please help me how to approach the problem without using group theory? I need a proof in algebraic way. And also welcome all links that shows how Lagrange proved for n=3,n=4 and n=5.

Note:I try to understand deeply how Abel and Ruffini showed the insolubility of quintic via radicals. The problem is also related to my other question that shown that f is not symmetric function n>2. and $f(x_1,x_2,x_3,\ldots,x_n)=f(x_n,x_1,x_2,\ldots,x_{n-1})=f(x_{n-1},x_n,x_1,\ldots,x_{n-2})=.....=f(x_2,x_3,x_4,\ldots,x_n,x_1)$
(totally $n$ permutation of f is equal each other) it means at least n values are the same in total $n!$ all permutations of $(x_1,x_2,x_3,\ldots,x_n)$ .

$UPDATE:$ I completed the Proof for $n=3$ I would like to share my way for $n=3$

All permutations for $n=3$ are:

$1)$-->$f(x_1,x_2,x_3)=(x_1+\alpha _3 x_2+ \alpha _3 ^2 x_3)^3$

$2)$-->$f(x_3,x_1,x_2)=(x_3+\alpha _3 x_1+ \alpha _3 ^2 x_2)^3=\alpha _3 ^3(x_3+\alpha _3 x_1+ \alpha _3 ^2 x_2)^3=(\alpha _3 x_3+\alpha _3 ^2 x_1+ x_2)^3$

$3)$-->$f(x_2,x_3,x_1)=(x_2+\alpha _3 x_3+ \alpha _3 ^2 x_1)^3=\alpha _3 ^3(x_2+\alpha _3 x_3+ \alpha _3 ^2 x_1)^3=(\alpha _3 x_2+ \alpha _3 ^2 x_3+x_1)^3$

$4)$-->$f(x_1,x_3,x_2)=(x_1+\alpha _3 x_3+ \alpha _3 ^2 x_2)^3$

$5)$-->$f(x_2,x_1,x_3)=(x_2+\alpha _3 x_1+ \alpha _3 ^2 x_3)^3=\alpha _3 ^3(x_2+\alpha _3 x_1+ \alpha _3 ^2 x_3)^3=(\alpha _3x_2+\alpha _3 ^2 x_1+ x_3)^3$

$6)$-->$f(x_3,x_2,x_1)=(x_3+\alpha _3 x_2+ \alpha _3 ^2 x_1)^3=\alpha _3 ^3 (x_3+\alpha _3 x_2+ \alpha _3 ^2 x_1)^3=(x_3\alpha _3+\alpha _3 ^2 x_2+ x_1)^3$

It can be easily seen that

(Permutation 1 = Permutation 3) and (Permutation 2 = Permutation 3)

Thus (Permutation 1 = Permutation 2 =Permutation 3)

(Permutation 4 = Permutation 6) and (Permutation 5 = Permutation 6)

Thus (Permutation 4 = Permutation 5 =Permutation 6)

If so for n=3, the function can have 2 different result {Permutation 1= $f(x_1,x_2,x_3)$ , Permutation 4 = $f(x_1,x_3,x_2)$)

To test with inputs: $x_1=1, x_2=2 ,x_3=0$

we know very well that $1+\alpha _3+\alpha _3 ^2=0$

$\alpha _3=e^{2 \pi i/3}=-\frac{1}{2}+ i\frac{\sqrt{3}}{2}$

Permutation 1: $f(x_1,x_2,x_3)=f(1,2,0)=(1+2\alpha _3)^3=1+6\alpha _3+12\alpha _3 ^2+8=-3-6\alpha _3=-3i\sqrt{3}$

Permutation 4: $f(x_1,x_3,x_2)=f(1,0,2)=(1+2\alpha _3 ^2)^3=1+6\alpha _3^2+12\alpha _3 +8=3+6\alpha _3=3i\sqrt{3}$

As you see in the example above .Permutation 1 and Permutation 4 cannot be the same always.

• Note that shew is an archaic form of the verb "show" that is conjugated just like "show", differing only in the vowel. Thus, in case you intended to use this archaic form, its past tense would be "shewed", not "shew", just as the past tense of "show" is "showed". – joriki Mar 15 '12 at 23:14
• The $n=3$ case is nicely done in the section on Lagrange at en.wikipedia.org/wiki/Cubic_function#Lagrange.27s_method. – Gerry Myerson Jun 28 '12 at 5:48

The $f$ you defined does not have this property when $n\ge 4$.

We can show that, if $(x_1,\dots,x_n)$ are arbitrary, when $$t_\sigma=f(x_{\sigma(1)},\dots,x_{\sigma(n)})$$ then the set of images $T=\{t_\sigma:\sigma\text{ is a permutation}\}$ has maximum cardinality exactly $(n-1)!$.

Proof:

• Write $f(x_1,\dots,x_n) = g(x_1,\dots,x_n)^n$. Note that a cyclic permutation of $(x_1,\dots,x_n)$ multiplies $g$ by $\alpha_n^k$ and therefore $f$ is multiplied by $\alpha_n^{kn} = 1$. So since $t_{\pi\circ\sigma}=t_\sigma$ when $\pi$ is one of the $n$ cyclic permutations, the maximum cardinality of $T$ is at most $n!/n=(n-1)!$.

• Now, since $g$ is a linear function with distinct coefficients before each $x_i$, if you are working in a characteristic zero field, the set of all $g(x_{\sigma(1)},\dots,x_{\sigma(n)})$ has maximum cardinality $n!$. But since the equation $t_\sigma=X^n$ has at most $n$ solutions in $X$, the maximum cardinality of $T$ is at least $(n-1)!$, finishing the proof.

Now, why doesn't it work? In fact I don't know if the resolvent can be defined by a systematic formula that extends for all $n$: we just find ad-hoc polynomials that happen to let us reduce the equation to a degree as low as possible. As a result, proving that such a polynomial exists is much easier than proving that no polynomial exists, and I don't know if there are proofs of Abel-Ruffini that don't use group theory.

So, how could we define a resolvent for $n=4$? Since $n$ is even there are $\tbinom{n}{n/2}/2=3$ ways to partition the roots into a set of two equal-sized subsets, so that: $$f(x)=x_1x_2+x_3x_4$$ has at most 3 images under permutation of $x$ (and it is easy to check that this bound is reached). There are 8 symmetries that can be derived from the two generator equations: $$f(a,b,c,d)=f(b,a,c,d)\\ f(a,b,c,d)=f(c,d,a,b)$$ Note that in general $f(a,b,c,d)\ne f(b,c,d,a)$, so unlike when $n=3$ cylic permutations are not always symmetries. Also note that this construction is only really useful for $n=4$, since for $n=6$ we get $\tbinom{n}{n/2}/2=10>6$.

You can check Lagrange's original 1770 paper (in French) to see that it is indeed the way he defined cubic resolvents and quartic resolvents.

He also gives a much more complicated polynomial for quintics, which he derives by generalizing to any root of unity $\alpha$ ($\alpha^5=1$), expanding the $f$ you just defined as a linear combination of $\alpha^0,\dots,\alpha^{n-1}$ and taking only the coefficient of $\alpha^0$. It turns out the resulting expression is highly symmetric, and the 20 symmetries can be derived from the three generators: \begin{align} f(a,b,c,d,e)&=f(b,c,d,e,a)&&\text{cyclic permutation}\\ f(a,b,c,d,e)&=f(e,d,c,b,a)&&\text{reversal}\\ f(a,b,c,d,e)&=f(a,c,e,b,d)&&\text{doubling modulo 5} \end{align} so that there are $5!/20=6$ distinct values. Cyclic permutation is for the same reason as when $n=3$; reversal and doubling modulo 5 come from the fact when replacing $\alpha$ by another root of unity $\alpha'=\alpha^k$ (where $k$ is relative prime with $n$), the coefficient of $\alpha'^0$ is the same as that of $\alpha^0$ so that $f$ is unchanged. In fact reversal is even implied by doubling modulo 5.

This construction of course generalize to all prime $n$, and in fact we have the closed form $$f(x_1,\dots,x_n)=\sum_{i_1+\dots+i_n=0\pmod n} x_{i_1}\dots x_{i_n}$$ which has $n(n-1)$ symmetries corresponding to the invertible affine maps $z\mapsto az+b$ of $\mathbb Z/n\mathbb Z$ (such maps preserve the condition $i_1+\dots+i_n=0 \pmod n$), so that the maximum cardinality of the images of $f$ is at most $(n-2)!$ (so for $n=3$, this degenerates to a completely symmetric function that is of no use to actually solving the equation because it doesn't give us any relation between the roots).

• Thanks a lot for your answer. Could you please give more detail how you got the general formula $\tbinom{n}{n/2}/2$ for n is even? I wonder why a general formula cannot be found for all n. It is strange that odd zeta function values do not have closed form expression of $\pi$ too such as $\zeta(3),\zeta(5) etc$. I started to suspect a relation between them?????*. And Also there should be proofs of Abel-Ruffini that don't use group theory because Historically Abel-Ruffini offered their ideas before grup theory of Galois . Thanks a lot for your valuable response. – Mathlover Jul 2 '12 at 7:00
• There are $\tbinom{n}{n/2}$ ways to choose a particular $n/2$-sized subset $A$ of $E=[1,n]$. $\{A,E\setminus A\}$ forms a partition of $E$, but since we don't care about the order ($\{A,E\setminus A\}=\{B,E\setminus B\}$ where $B=E\setminus A$) each partition corresponds to exactly 2 subsets, so there are $\tbinom{n}{n/2}/2$ partitions. Note that there is no reason to think this is the best polynomial for all even $n$: this is just a general formula for that particular family of polynomials! – Generic Human Jul 2 '12 at 15:01
• For $\zeta(5),\zeta(7),\dots$: we don't know much about them today, but there is a conjecture that they are algebraically independent over $\mathbb Q$. We don't even know that $\zeta(5)$ is irrational! You're right about the proofs of Abel-Ruffini. – Generic Human Jul 2 '12 at 15:03
• @GenericHuman: excellent answer which I am not smart enough to completely understand. I hope you will look at my new update to this question and respond further. – Marty Green Dec 20 '13 at 19:11
• I added an update to this question but I don't know what happened to it...its not there anymore. – Marty Green Dec 21 '13 at 0:49

There is a followup to this question with a more explicit answer for the case of n=5 posted here:

Resolvent of the Quintic...Functions of the roots