Skip to main content
added 197 characters in body
Source Link
David E Speyer
  • 156.3k
  • 14
  • 421
  • 763

It is not possible to solve these equations/inequalities. EDIT: I am analyzing the version where the power sums start at $k=1$, not the original where they start al $k=\ell$. Thanks to Greg Kuperberg and Reid Barton for pointing this out.

Lemma: There is a constant $A>0$, and a sequence of polynomials $T_d(x)$ of degree $d$, such that $|T_d(x)| \leq 1$ on $[C_1, C_2]$, and $|T_d(0)| \geq e^{Ad}$.

Proof: The easiest proof is to take $T_d(x) = \lambda(x)^d$, where $\lambda$ is the linear function such that $\lambda(C_1) =1$ and $\lambda(C_2) = -1$. I think you'll get slightly tighter bounds if you take $T_d(x)$ to be an appropriately normalized Chebyshev polynomial. ❚

Now, suppose we had $2n+1$ numbers in $[C_1, C_2]$ such that $\sum x_i^k = \sum y_i^k$ for $1 \leq k \leq d$. Consider $$\sum_{i=1}^{n+1} T(x_i) - \sum_{i=1}^n T(y_i) \quad (*).$$

On the one hand, $(*)$ is a sum of $2n+1$ terms, each of which are $O(1)$, so it is $O(n)$.

On the other hand, if we write out $T_d$ as a polynomial and group terms of like degree, everything cancels but the constant term. So $(*)$ is $$(n+1) T(0) - n T(0) = T(0) \leq e^{Ad}$$.

So $e^{Ad} = O(n)$ and $d = O(\log n)$. Thus, we can only hope to get $\log n$ many power sums to match up.

It is not possible to solve these equations/inequalities.

Lemma: There is a constant $A>0$, and a sequence of polynomials $T_d(x)$ of degree $d$, such that $|T_d(x)| \leq 1$ on $[C_1, C_2]$, and $|T_d(0)| \geq e^{Ad}$.

Proof: The easiest proof is to take $T_d(x) = \lambda(x)^d$, where $\lambda$ is the linear function such that $\lambda(C_1) =1$ and $\lambda(C_2) = -1$. I think you'll get slightly tighter bounds if you take $T_d(x)$ to be an appropriately normalized Chebyshev polynomial. ❚

Now, suppose we had $2n+1$ numbers in $[C_1, C_2]$ such that $\sum x_i^k = \sum y_i^k$ for $1 \leq k \leq d$. Consider $$\sum_{i=1}^{n+1} T(x_i) - \sum_{i=1}^n T(y_i) \quad (*).$$

On the one hand, $(*)$ is a sum of $2n+1$ terms, each of which are $O(1)$, so it is $O(n)$.

On the other hand, if we write out $T_d$ as a polynomial and group terms of like degree, everything cancels but the constant term. So $(*)$ is $$(n+1) T(0) - n T(0) = T(0) \leq e^{Ad}$$.

So $e^{Ad} = O(n)$ and $d = O(\log n)$. Thus, we can only hope to get $\log n$ many power sums to match up.

It is not possible to solve these equations/inequalities. EDIT: I am analyzing the version where the power sums start at $k=1$, not the original where they start al $k=\ell$. Thanks to Greg Kuperberg and Reid Barton for pointing this out.

Lemma: There is a constant $A>0$, and a sequence of polynomials $T_d(x)$ of degree $d$, such that $|T_d(x)| \leq 1$ on $[C_1, C_2]$, and $|T_d(0)| \geq e^{Ad}$.

Proof: The easiest proof is to take $T_d(x) = \lambda(x)^d$, where $\lambda$ is the linear function such that $\lambda(C_1) =1$ and $\lambda(C_2) = -1$. I think you'll get slightly tighter bounds if you take $T_d(x)$ to be an appropriately normalized Chebyshev polynomial. ❚

Now, suppose we had $2n+1$ numbers in $[C_1, C_2]$ such that $\sum x_i^k = \sum y_i^k$ for $1 \leq k \leq d$. Consider $$\sum_{i=1}^{n+1} T(x_i) - \sum_{i=1}^n T(y_i) \quad (*).$$

On the one hand, $(*)$ is a sum of $2n+1$ terms, each of which are $O(1)$, so it is $O(n)$.

On the other hand, if we write out $T_d$ as a polynomial and group terms of like degree, everything cancels but the constant term. So $(*)$ is $$(n+1) T(0) - n T(0) = T(0) \leq e^{Ad}$$.

So $e^{Ad} = O(n)$ and $d = O(\log n)$. Thus, we can only hope to get $\log n$ many power sums to match up.

Source Link
David E Speyer
  • 156.3k
  • 14
  • 421
  • 763

It is not possible to solve these equations/inequalities.

Lemma: There is a constant $A>0$, and a sequence of polynomials $T_d(x)$ of degree $d$, such that $|T_d(x)| \leq 1$ on $[C_1, C_2]$, and $|T_d(0)| \geq e^{Ad}$.

Proof: The easiest proof is to take $T_d(x) = \lambda(x)^d$, where $\lambda$ is the linear function such that $\lambda(C_1) =1$ and $\lambda(C_2) = -1$. I think you'll get slightly tighter bounds if you take $T_d(x)$ to be an appropriately normalized Chebyshev polynomial. ❚

Now, suppose we had $2n+1$ numbers in $[C_1, C_2]$ such that $\sum x_i^k = \sum y_i^k$ for $1 \leq k \leq d$. Consider $$\sum_{i=1}^{n+1} T(x_i) - \sum_{i=1}^n T(y_i) \quad (*).$$

On the one hand, $(*)$ is a sum of $2n+1$ terms, each of which are $O(1)$, so it is $O(n)$.

On the other hand, if we write out $T_d$ as a polynomial and group terms of like degree, everything cancels but the constant term. So $(*)$ is $$(n+1) T(0) - n T(0) = T(0) \leq e^{Ad}$$.

So $e^{Ad} = O(n)$ and $d = O(\log n)$. Thus, we can only hope to get $\log n$ many power sums to match up.