My Conjecture « Rod Carvalho's web notebook

My Conjecture

By Rod Carvalho

Let function $g_k: \mathbb{R}^n \rightarrow \mathbb{R}$ be defined as

$g_k(z) = \displaystyle\sum_{i=1}^n z_i^k$

for $k \in \mathbb{N}$ . Given a known vector $y \in \mathbb{R}^n$ , where $y_i \neq y_j, \forall i \neq j$ , we define constants $c_k = g_k(y)$ for $k \in \mathbb{N}$ . Finally, let polynomial function $p_k: \mathbb{R}^n \rightarrow \mathbb{R}$ be defined as

$p_k(x) = g_k(x) - c_k$ .

For the sake of clarity, note that

$p_k(x) = \displaystyle\sum_{i=1}^n x_i^k - \displaystyle\sum_{i=1}^n y_i^k$ .

For a given $k \geq 1$ , the set of solutions of equation $p_k(x) = 0$ define an algebraic variety. Note that $p_k(x) = 0 \Leftrightarrow g_k(x) = c_k$ , and therefore the algebraic variety defined by equation $p_k(x) = 0$ contains $y \in \mathbb{R}^n$ . Some particular cases:

$k = 1$ : $g_1(x) = c_1$ defines a hyperplane in $n$ -dimensional space.

$k = 2$ : $g_2(x) =c_2$ defines a hypersphere in $n$ -dimensional space.

I conjecture that the system of $n$ polynomial equations in $x \in \mathbb{R}^n$

$\left\{\begin{array}{rl}p_1(x) &= 0\\p_2(x) &= 0\\ \vdots & \\p_n(x) &= 0\\\end{array}\right.$

has exactly $n!$ solutions. From a geometric viewpoint, this is equivalent to conjecturing that the intersection of $n$ algebraic varieties is a finite set containing exactly $n!$ elements.

This conjecture seems to be true for $n = 2$ and $n=3$ , but I haven’t been able to prove anything for $n > 3$ . I dare you to take a shot at it!

I have been playing around with Buchberger’s algorithm, but I happened to get nowhere. Maybe Hilbert’s basis theorem would be helpful. Maybe not. It may happen that this conjecture is really easy to prove provided that one is acquainted with all that powerful algebraic machinery I know nothing about. Thanks.

-/-

Remark: Abstract Algebra is a field I am not familiar with. Not surprisingly, my knowledge of Algebraic Geometry is precisely null. I really have no idea whatsoever how easy / hard this problem is. I don’t even know if the problem is tractable. I hope the problem is well-posed, and I do hope someone will find it interesting. If you manage to prove anything, or at least to reach any conclusions, please post the solution on a preprint server such as arXiv.org.

Tags: Algebra, Algebraic Geometry, Mathematics

This entry was posted on May 19, 2008 at 2:58 am and is filed under Mathematics. 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.

9 Responses to “My Conjecture”

rod. Says:
May 19, 2008 at 4:34 am | Reply
As an example, let’s consider the case $k=3$ .

The system of polynomial equations is

$\left\{\begin{array}{rl}x_1 + x_2 + x_3 = y_1 + y_2 + y_3 \\x_1^2 + x_2^2 + x_3^2 = y_1^2 + y_2^2 + y_3^2\\x_1^3 + x_2^3 + x_3^3 = y_1^3 + y_2^3 + y_3^3\end{array}\right.$ .

According to my conjecture, this system of equations should have exactly $3! = 6$ solutions. According to MATLAB that seems to be the case. I have plotted each of the three $2$ -manifolds, and they intersect on $6$ points.

Another possibility is to use automated symbolic manipulation. I don’t have Maple, but I have MATLAB. For instance, the following script:
```
% declares symbolic variables
syms x1 x2 x3 y1 y2 y3;

% solves the equations
[x1,x2,x3] = solve(x1 + x2 + x3 - (y1 + y2 + y3),...
                   x1^2 + x2^2 + x3^2 - (y1^2 + y2^2 + y3^2),...
                   x1^3 + x2^3 + x3^3 - (y1^3 + y2^3 + y3^3))
```
produces exactly $6$ solutions:
```
x1 =

 y1
 y2
 y1
 y3
 y2
 y3

x2 =

 y3
 y3
 y2
 y2
 y1
 y1

x3 =

 y2
 y1
 y3
 y1
 y3
 y2
```
Of course, just because it works for $n = 2,3$ it does not mean it works for all $n \geq 2$ . Hence the term “conjecture” ;-)
Sune Kristian Jakobsen Says:
May 19, 2008 at 9:17 am | Reply
I couldn’t find out how to use Latex on this blog. I hope the following isn’t too hard to read.

If some of the coordinates in y are equal, there are not necessarily n! solutions: If y=(1,1), then y is the only solution. So the conjecture should be, that all the solutions are permutations of y’s coordinates.

Can anyone find counterexamples to this stronger conjecture?:
Let a_1, a_2, …, a_n be n integers, not all even. Now all the solutions to the system p_a_1(x)=0, p_a_2(x)=0,… , p_a_n(x)=0 are permutation of y.
Vishal Lama Says:
May 19, 2008 at 10:06 am | Reply
Sune,

I noticed that you had problems writing LaTeX on my blog too! This is what you need to do on WordPress blogs: “$ latex \\code_goes_here$”. Of course, you don’t write the double quotes. And also make sure there is no space between “latex” and “$” sign. Hope this helps.

And, there is no need to insert square brackets along with the LaTeX code!
Sune Kristian Jakobsen Says:
May 19, 2008 at 2:42 pm | Reply
Thanks Vishal

To prove that x is a permutation of y (in your conjecture), I want to prove that x and y both contains all the roots to a n-degree polynomial. The polynomial that has $x_1,x_2,...,x_n$ as roots is:
$x^n- (\sum_i x_i)x^{n-1} + (\sum_{i \not= j} x_i x_j)x^{n-2} -... + (-1)^n \prod_i x_i$
Therefore, if you can write $(\sum_i x_i)x^{n-1}, (\sum_{i \not= j} x_i x_j)x^{n-2}, ..., (-1)^n \prod_i x_i$ as a combination of $c_1, c_2, ..., c_n$ y must be a permutation of x.
The first term is $-c_1$ , the second is $\frac{c_1^2-c_2}{2}$ and the third is $\frac{c_1^3-3c_1 c_2+2c_3}{6}$ .

I think it is well-know that all the terms can can be written using only $c_1, c_2, ..., c_n$ , but here is a way to prove it:
In order to write the n’th term begin with $\frac{c_1^n}{n!}$ . This contains a lot of terms, and each contains at most n x-variables. We wants to isolate the terms with n x-variables. The terms with n-1 x-variables can be removed by subtracting a multiple of $c_1^{n-2}c_2$ . After that you can remove all the terms that contains n-2 x-variables by subtracting multiples of $c_1^{n-3}c_3$ and $c_1^{n-2}c_2^2$ and so on. This works because every “type” of term (by type I mean that the exponents are the same, so $x_1^2 x_2^2 x_3$ and $x_1^2 x_2 x_3^2$ are the same type) is the term with most x-variables in an expression of the form $c_1^{\alpha_1}c_2^{\alpha_2}...c_n^{\alpha_n}$ . E.g. if you want to remove terms of the form $x_1^2 x_2^2 x_3$ you can subtract a multiple of $c_1 c_2^2$ . This way you remove the terms of the type $x_1^2 x_2^2 x_3$ without introducing other terms with 3 or more x-variables.
rod. Says:
May 19, 2008 at 6:59 pm | Reply
@ Sune

Thank you very much for your insight! :-)

You are very right: the solutions of the system of polynomial equations

$\left\{\begin{array}{rl}p_1(x) &= 0\\p_2(x) &= 0\\ \vdots &\\p_n(x) & = 0\\\end{array}\right.$

are, in general, the $n!$ permutations of $n$ -tuple $y \in \mathbb{R}^n$ . Just like you said, if not all entries of $n$ -tuple $y$ are distinct, then the system of equations will have less than $n!$ distinct solutions. We can think of those solutions with multiplicity higher than $1$ as “degenerate” solutions.

I forgot to mention in my post that the entries of $y$ should be distinct. Thanks for reminding me. I have thus updated the original post.

I came to this conjecture while looking for an algebraic method of computing the permutations of a $n$ -tuple. I find it rather fascinating that an operation as “discrete” as computing permutations can be viewed as something as “continuous” as intersecting $2$ -manifolds in $n$ -dimensional space.

I will be thinking of the solution you proposed on your 2nd comment, and I will post my thoughts on it later on. Thanks a lot once again!
Playing with SymPy « Reasonable Deviations Says:
July 5, 2008 at 12:58 am | Reply
[...] is a known vector. According to my conjecture, this system of equations should have exactly solutions. The following Python script computes the [...]
Charles Says:
July 5, 2008 at 3:08 am | Reply
Here’s another argument, and I think it works. It’s algebro-geometic in nature.

First, expand to complex projective space $\mathbb{CP}^n$ with the same set of equations (we’re going to need a generically chosen vector $y$ , but I THINK not having any duplicate entries does it)

So we have $\mathbb{CP}^n$ with $n$ equations, of degrees $1,2,3,\ldots,n$ . So they define hypersurfaces in projective space of these degrees. Now, the intersection of them is determined by linear equivalence classes (more of that on my blog) but the gist is that any hypersurface is linearly equivalent to its degree times a hyperplane.

So then what we have is, if we denote the hyperplane by $H$ , the intersection is $n! H^n$ , where $H^n$ means the intersection of $n$ hyperplanes in $\mathbb{CP}^n$ . This is one. So the number of complex projective solutions is $n!$ . And if our vector was real to begin with, the permutations of the coordinates will all be solutions, and so there are $n!$ of them, so all are finite and real, as desired.

At least, I think that works out, I’m short on sleep, and certainly capable of being way off.
rod. Says:
July 10, 2008 at 4:14 am | Reply
@ Charles

Thank you very much for your input :-)

My training in in Electrical Engineering, not Math. I am not qualified to understand your comment. Unfortunately, I have only a very basic training in Algebra, and I know nothing of Algebraic Geometry.

I have asked a couple of friends who were trained as mathematicians to think about the conjecture and your comment. This is something that takes some time, but hopefully they’ll have something to say about it some time soon.

If you ever feel like writing a post on your blog on this topic, I would really appreciate it, since that would draw more attention to this conjecture and hopefully lead other mathematicians to think about it and give their input.

I don’t think I am qualified to prove the conjecture. Still, it would be great if someone did prove it, so I could develop some cool work based on it.

Thanks a lot once again!
Charles Says:
July 11, 2008 at 1:14 pm | Reply
I might do that. It seems to be a good illustration of some of the stuff I’ve discussed over the last couple of months. It’s an interesting problem, at the least!

Rod Carvalho's web notebook

My Conjecture

9 Responses to “My Conjecture”

Leave a Reply