Let $A=\{a_1,a_2,\cdots,a_{2010}\}$ and $B=\{b_1,b_2,\cdots,b_{2010}\}$ be two sets of complex numbers. Suppose \[\sum_{1\leq i<j\leq 2010} (a_i+a_j)^k=\sum_{1\leq i<j\leq 2010}(b_i+b_j)^k\] holds for every $k=1,2,\cdots, 2010$. Prove that $A=B$.
Problem
Source:
Tags: algebra, polynomial, function, complex numbers, algebra unsolved
orl
28.08.2010 23:55
Approach by wood: 2010 is not of much importance here; we substitute it by $n$. Let $\sigma_1=a_1+\cdots+a_n$, $\sigma_2=\sum_{i<j}a_ia_j$, ..., $\sigma_n=a_1\cdots a_n$ be the elementary symmetric polynomials of the $a_i$. Set $S_k=a_1^k+\cdots +a_n^k$. By Newton, if $k\le n$, then $S_k-\sigma_1 S_{k-1}+\cdots+(-1)^{k-1}S_1+(-1)^k ka_k=0$. If we know the values of $S_1,\cdots, S_n$, then we can find the values of $\sigma_1,\cdots,\sigma_n$. Hence the set $\{a_1,\cdots,a_n\}$ is uniquely determined by $S_1,\cdots, S_n$, because the $a_i$ are the roots of $x^n-\sigma_1 x^{n-1}+\cdots+(-1)^n \sigma_n$. Now let $T_k=\sum_{i<j}(a_i+a_j)^k$. Then $T_k=\sum_{i<j}\bigg( a_i^k+\binom k1 a_i^{k-1}a_j+\cdots+a_j^k\bigg)$. Note \[S_{k-l}S_l=\bigg(\sum a_i^{k-l}\bigg)\bigg(\sum a_j^{l}\bigg)=\sum_{i,j} a_i^{k-l}a_j^l\\ =\sum_{i<j} a_i^{k-l}a_j^l+\sum_{i>j} a_i^{k-l}a_j^l+S_k.\] Hence \[2T_k=\binom k1 S_{k-1}S_1+\binom k2 S_{k-2}S_2+\cdots+\binom{k}{k-1}S_{1}S_{k-1}+ \\ \bigg((n-1)-\binom k1-\cdots-\binom{k}{k-1}\bigg)S_k.\] So if $n$ is not of the form $2^k-1$, then $S_1,\cdots,S_n$, consequently $\{a_1,\cdots,a_n\}$, is uniquely determined by $T_1,\cdots,T_n$. Finally, it's easy to see $2010$ is not of the form $2^k-1$. So draws the conclusion.
Naysh
08.08.2014 10:25
We will show that the hypothesis holds true for any complex numbers $a_1,a_2,...,a_n$ and $b_1,b_2,...,b_n$ when $n$ is not a power of $2$.
Define $A'=\{a_i+a_j|i\neq j\}$ and $B'=\{b_i+b_j|i\neq j\}$. By Newton Sums, $A'=B'$.
Now, we claim that when $n$ is not a power of $2$, $A'=B'\Longrightarrow A=B$.
Suppose to the contrary that $A\neq B$. Then consider the functions $f(z)=\displaystyle\sum_{k=1}^ne^{za_k}$ and $ g(z)=\displaystyle \sum_{k=1}^ne^{zb_k}$.
Then $A'=B'$ is equivalent to the algebraic statement that \[f(z)^2-f(2z)=g(z)^2-g(2z)\Longrightarrow f(z)+g(z) = \dfrac{f(2z)-g(2z)}{f(z)-g(z)}.\]
Take the limit as $z$ approaches $0$ on both sides. On the LHS, the value is clearly just $f(0)+g(0)=2n$.
On the RHS, the value is indeterminate, so apply L'hopital's Rule and differentiate the numerator and denominator repeatedly until the denominator is not zero.
Clearly this is possible, since if the denominator were to always be zero, then $\displaystyle\sum_{k=1}^na_k^m=\sum_{k=1}^nb_k^m$ for all nonnegative integers $m$, which by Newton's Sums would mean that $A=B$, which would contradict out assumption.
So, after $\ell$ applications of L'hopital's rule, the RHS reduces to $2^{\ell}$.
Equating the LHS and RHS produces $2n=2^{\ell}\Longrightarrow n=2^{\ell - 1}$, which contradicts the assumption that $n$ is not a power of $2$.
Thus, $A'=B'$ implies that $A=B$, and the conclusion follows.
The idea seems to be very similar to math154's solution to the Erdos Selfridge problem, except this solution works for complex numbers.
va2010
22.04.2015 02:38
The very first step is wrong, as the sets are much too large...
iceillusion
05.06.2020 12:44
orl wrote: \[2T_k=\binom{k}{1}S_{k-1}S_1+\binom{k}{2}S_{k-2}S_2+\cdots+\binom{k}{k-1}S_{1}S_{k-1}+\bigg((n-1)-\binom{k}{1}-\cdots-\binom{k}{k-1}\bigg)S_k.\] This step contains a mistake. The correct equality should be \[2T_k=\sum_{i=1}^{k-1}\binom{k}{i}(S_{k-i}S_i-S_k)+2(n-1)S_k=\sum_{i=1}^{k-1}\binom{k}{i}S_{k-i}S_i+(2n-2^k)S_k\]and thus the problematic $n$ are powers of $2$. A way to see this without computation is from Selfridge and Strauss' work, which shows by example that when $n$ is a power of $2$ the multiset $\{a_i+a_j|1\leq i<j\leq n\}$ doesn't necessarily determines a set $A=\{a_1,...,a_n\}\subset\mathbb{Z}$. On the other hand this problem is exactly the approach of that paper to prove the positive statement when $n$ is not a power of $2$.
IAmTheHazard
20.07.2023 03:52
definitely not the finish I expected We reformulate the problem as follows: given that there exist complex $x_1,\ldots,x_{2020}$, given $\sum_{1 \leq i<j \leq 2010} (x_i+x_j)^k$ for $1 \leq k \leq 2010$, we can uniquely determine the multiset $\{x_1,\ldots,x_{2010}\}$. For a sequence of $2010$ nonnegative integers, let $[e_1,\ldots,e_{2010}]$ denote the symmetric polynomial $$\sum_{\mathrm{sym}}\prod_{i=1}^{2010} x_i^{e_i}.$$Observe that $$[p_1,\ldots,p_{2010}][q_1,\ldots,q_{2010}]=\sum_{\sigma} [p_1+q_{\sigma(1)},\ldots,p_{2010}+q_{\sigma(2010)}]\qquad (\heartsuit),$$where the sum is over all permutations of $\{1,\ldots,2010\}$. We have the following lemma: Lemma: Let $1 \leq k \leq 2010$ be fixed. For every decreasing tuple of $2010$ nonnegative integers $(e_1,\ldots,e_{2010})$ with sum $k$, except when $e_1=k$ and $e_2=\cdots=e_{2010}=0$, there exist two decreasing tuples of $2010$ nonnegative integers $(p_1,\ldots,p_{2010})$ and $(q_1,\ldots,q_{2010})$ whose sums are positive add up to $k$, such that when they are multiplied, among the expansion of $[p_1,\ldots,p_{2010}][q_1,\ldots,q_{2010}]$, according to $(\heartsuit)$, the polynomial $[e_1,\ldots,e_{2010}]$ appears, and every other polynomial $[e_1',\ldots,e_{2010}']$ where $e_1' \geq \cdots \geq e_{2010}'$ satisfies the fact that the tuple $(e_{2010}',\ldots,e_1')$ is lexicographically smaller than $(e_{2010},\ldots,e_1)$. Proof: Take the maximal $i \geq 2$ such that $e_i>0$. Then consider $(p_1,\ldots,p_{2010})=(e_i,0,\ldots,0)$ and $(q_1,\ldots,q_{2010})=(e_1,\ldots,e_{i-1},0,\ldots,0)$. It is clear that this works. $\blacksquare$ We now have the following key claim, which is the pith of the problem. Claim: We can determine the value of every polynomial $[i_1,\ldots,i_{2010}]$ where $i_1+\cdots+i_{2010}=k$, for every $1 \leq k \leq 2010$. Proof: This is by strong induction on $k$, with the base case of $k=1$ being obvious, since we are given a nonzero multiple of $[1,0,\ldots,0]$ in the problem statement for $k=1$. For the inductive step, construct the set $S$ of all products $[p_1,\ldots,p_{2010}][q_1,\ldots,q_{2010}]$ generated by the lemma as $(e_1,\ldots,e_{2010})$ varies. Note that we know the value of every polynomial in $S$, since it is the product of lower-degree polynomials whose values we know by hypothesis. It is clear that the polynomials in $S$, as well as $[k,0,\ldots,0]$, form a basis of the vector space of symmetric homogeneous degree-$k$ polynomials in $x_1,\ldots,x_{2010}$, since we can construct any such polynomial uniquely by starting from the tuple $(e_1,\ldots,e_{2010})$ whose reverse is lexicographically largest and move downwards. I claim that in the representation of $\sum_{1 \leq i<j \leq 2010} (x_i+x_j)^k$ with this basis, the coefficient of $[k,0,\ldots,0]$ is nonzero. First, note that the only polynomials in $S$ whose reverse-lexicographically smallest "term" contains exactly two nonzero values (exactly one is impossible) are those formed from multiplying $[a,0,\ldots,0]$ with $[k-a,0,\ldots,0]$ for some $a$. Therefore, these polynomials, as well as $[k,0,\ldots,0]$ are the only ones which can have a nonzero coefficient in the representation of $\sum_{1 \leq i<j \leq 2010} (x_i+x_j)^k$: otherwise, take the polynomial with nonzero coefficient whose reverse-lexicographically smallest "term" is the smallest, which contains at least three zeroes, and get a contradiction, since by the construction of $S$ and the extremal condition, we find that this term must appear in $\sum_{1 \leq i<j \leq 2010} (x_i+x_j)^k$, which is not possible since at most two variables get multiplied together in any monomial of its expansion. Therefore, by scaling, we may reformulate the problem somewhat: prove that if $\sum_{1 \leq i<j \leq 2010} (x_i+x_j)^k$ is expressed (uniquely) as a linear combination of the polynomials $x_1^k+\cdots+x_{2010}^k$ and $(x_1^a+\cdots+x_{2010}^a)(x_1^{k-a}+\cdots+x_{2010}^{k-a})$ for $1 \leq a \leq k-1$ (really these are the same, but it helps to treat them differently), then the coefficient of $x_1^k+\cdots+x_{2010}^k$ is nonzero. To that end, we write \begin{align*} \sum_{1 \leq i<j \leq 2010} (x_i+x_j)^k&=2009\sum_{i=1}^{2010} x_i^k+\color{blue}{\sum_{1 \leq i<j \leq 2010}\sum_{a=1}^{k-1}\binom{k}{a}x_i^ax_j^{k-a}}\\ \frac{1}{2}\sum_{a=1}^{k-1} \binom{k}{a} (x_1^a+\cdots+x_{2010}^a)(x_1^{k-a}+\cdots+x_{2010}^{k-a})&=\frac{1}{2}\sum_{a=1}^{k-1}\binom{k}{a}\left(\sum_{i=1}^{2010} x_i^k+\sum_{1 \leq i<j \leq 2010} (x_i^ax_j^{k-a}+x_i^{k-a}x_j^a)\right)\\ &=\frac{1}{2}\sum_{a=1}^{k-1}\binom{k}{a}\sum_{i=1}^{2010} x_i^k+\color{blue}{\sum_{1\leq i<j\leq 2010}\sum_{a=1}^{k-1} \binom{k}{a}x_i^ax_j^{k-a}}. \end{align*}Since the blue parts are the same, it follows that if $\sum_{1 \leq i<j \leq 2010} (x_i+x_j)^k$ can be expressed as a linear combination of the above polynomials with the $x_1^k+\cdots+x_{2010}^k$ coefficient zero, then we must have $$2009=\frac{1}{2}\sum_{a=1}^{k-1}\binom{k}{a}=\frac{1}{2}(2^k-2)=2^{k-1}-1,$$but this is obviously never true. Therefore, since we know the values of $\sum_{1 \leq i<j \leq 2010} (x_i+x_j)^k$ and all the polynomials in $S$, we can find the value of $[k,0,\ldots,0]$. Then, since $S$ and $[k,0,\ldots,0]$ form a basis for symmetric homogeneous degree-$k$ polynomials in $x_1,\ldots,x_{2010}$, we can find the value of every $[i_1,\ldots,i_{2010}]$ where $i_1+\cdots+i_{2010}=k$, completing the inductive hypothesis. $\blacksquare$ To finish the problem, observe that by our key claim, we can find the $k$-th elementary symmetric sum of the $x_i$ for $1 \leq k \leq 2010$, which we can use to write down a unique monic degree-$2010$ polynomial whose roots are precisely $x_1,\ldots,x_{2010}$, so the multiset $\{x_1,\ldots,x_{2010}\}$ is uniquely determined. $\blacksquare$ Remark: Neither $2010$ nor the choice of $\sum_{1 \leq i<j \leq 2010} (x_i+x_j)^k$ are particularly important in the problem, although neither can be replaced by any arbitrary value. In general, most of the time we should expect any linear polynomial instead of $x_i+x_j$ to work, although with more variables the computations should quickly become intractable. Nevertheless, if we fix the linear polynomial, I believe it is the case that the density of the non-working choices for the number of variables (replacing $2010$) is $0$ in the natural numbers.