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
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.
08.08.2014 10:25
The idea seems to be very similar to math154's solution to the Erdos Selfridge problem, except this solution works for complex numbers.
22.04.2015 02:38
The very first step is wrong, as the sets are much too large...
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$.
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.