Simultaneous Equations Involving Power Sums

Question

Let $\ell$ be a positive integer greater than 1. The problem is to find a set of $n$ real positive numbers $x_i$ and $n+1$ numbers $y_i$ such that $$\sum_{i=1}^n x_i^k= \sum_{i=1}^{n+1} y_i^k$$ for $k=\ell,\cdots,2\ell-1$. These $2n+1$ numbers need to be upper/lower bounded by a constant independent of $\ell$ [thus $x_i,y_i=\Theta(1)$] and also I suspect that it is possible to do so with just $n=\ell$ or $n=O(\ell)$. [$\ell$ equations with $2\ell$ unknowns, why not!] An existential proof suffices but a constructive proof or a recipe would be really nice.

For me it is useful to find a bounded from below solution that scales in polynomially in the following sense: There exist positive $c$, and $s$ such that $c\le x_i,y_i$ and $$\sum_i x_i+\sum_i y_i=O(\ell^s)$$.

The problem is related to a follow up on this paper of mine: arxiv:0908.1526 .

Answer 1

Actually Darsh gave an almost full solution. Let me fill in the minor technical details.

1) We need the following quantitative form of the inverse function theorem. Suppose that $F:\mathbb R^n\to \mathbb R^n$. Assume also that $\|DF(X)^{-1}\|\le C_1$, that $\max_{Y\in B(X, \delta)}\|D^2F(Y)\|\le C_2$, and that $C_1C_2\delta\le\frac 12$. Then $F(B(X,\delta))\supset B(F(X),\frac{\delta}{2C_1})$.

2) Take $n=2\ell-1$ and consider the mapping $F:\mathbb R^n\to \mathbb R^n$ given by $F(y_1,\dots,y_n)_k=\sum_{j=1}^n y_j^k$ where $k=1,2,\dots,n$. Take $X=(x_1,\dots,x_n)$ where $x_j=\frac{n+j}{n}$ for $j=1,\dots,n$.

3) Note that in $B(X,1)$, we have $\|D^2F\|\le A^n$ for some absolute $A>1$.

4) Note also that $DF(X)^*$ is the linear operator that maps the vector $(c_1,\dots,c_n)$ to the vector $p(x_1),\ldots,p(x_n)$ consisting of the values of the polynomial $p(x)=\sum_{k=1}^n c_k kx^{k-1}$. The inverse operator is given by the standard interpolation formula, which allows us to estimate its norm by $B^n$ with some absolute $B>1$.

5) Thus, taking $\delta=2^{-1}(AB)^{-n}$, we conclude that the image of the ball $B(X,\delta)$ contains a ball of radius $\frac\delta{2A^n}\ge C^{-n}$ with some absolute $C>2$.

6) In particular, it contains two points with the difference $(0,0,\dots,0,D^{-\ell},D^{-(\ell+1)},\dots,D^{-(2\ell-1)})$ with some absolute $D>1$, which is equivalent to what we need.

Answer 2

Maybe the following is useful: first pick arbitrary distinct positive numbers $y\_1,\ldots,y\_n$. Note that $(y\_1,\ldots,y\_n,y\_1,\ldots,y\_n,0)$ is a solution to your system for all $l$; however, the last component is zero, so it doesn't fit your constraints. To remedy this, fix $l=n$ and define $F:\mathbb{R}^{n+1}\to\mathbb{R}^n$ by $$F(a_1,\ldots,a\_n,b)\_k = \sum\_{i=1}^n(a\_i + y\_i)^{k+n-1} - b^{k+n-1} - \sum\_{i=1}^n y\_i^{k+n-1}.$$ Note that $F(0) = 0$ and $$\frac{\partial F\_k}{\partial a\_i} = (k+n-1)(a\_i+y\_i)^{k+n-2},$$ so $$ \begin{align*}\frac{\partial F\_k}{\partial a} &= \begin{bmatrix}n(a\_1 + y\_1)^{n-1} & \cdots & n(a\_n + y\_n)^{n-1} \\\\ \vdots & \ddots & \vdots \\\\ (2n-1)(a\_1 + y\_1)^{2n-2} & \cdots & (2n-1)(a\_n + y\_n)^{2n-2}\end{bmatrix} \\\\ &= \begin{bmatrix}n & & \\\\ & \ddots & \\\\ & & 2n-1\end{bmatrix} \begin{bmatrix}1 & \cdots & 1 \\\\ \vdots & \ddots & \vdots \\\\ (a\_1 + y\_1)^{n-1} & \cdots & (a\_n + y\_n)^{n-1}\end{bmatrix} \begin{bmatrix}(a\_1 + y\_1)^{n-1} & & \\\\ & \ddots & \\\\ & & (a\_n + y\_n)^{n-1}\end{bmatrix} \\\\ &= D\_1V(a\_1+y\_1,\ldots,a\_n+y\_n)D\_2, \end{align*}$$ where $D\_1$ and $D\_2$ are nonsingular diagonal matrices and $V(a\_1+y\_1,\ldots,a\_n+y\_n)$ is a Vandermonde matrix, which is nonsingular for all $(a\_1,\ldots,a\_n)$ sufficiently close to zero since $y\_1,\ldots,y\_n$ are distinct. Thus, by the implicit function theorem, for all $b$ sufficiently close to zero, there is a solution $(y\_1+a\_1,\ldots,y\_n+a\_n,y\_1,\ldots,y\_n,b)$ to your system. It should be easy to derive the bounds you require. Morally, though, taking $n=l$ gives you way too many degrees of freedom; you should be able to get away with much smaller $n$.

Afterthoughts: The problem with the above is that $b$ might need to be taken arbitrarily close to zero as $l$ increases. Since $n=l$ in this argument, if the points $x\_i$ and $y\_i$ also need to be bounded, then this means all the points can't be bounded away from one another as $l$ grows, and the Vandermonde matrix will become increasingly badly conditioned. (I didn't check that rigorously, but the heuristic argument seems pretty convincing.) I don't know how much any of that depends on how $y\_1,\ldots,y\_n$ are chosen. I've made this a community wiki post in case someone can fix the argument or prove that it doesn't work.

Answer 3

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.

Answer 4

I thought about this a bit and didn't get anywhere. I'm just posting to point out that the following problem appears to contain the fundamental difficulties of the original, while eliminating some of the irritating details:

Do there exist $0 <r < 1$ and $0 < c < 1$ such that, for every (or infinitely many) $n$, there are $n-1$ complex numbers $u\_1$, $u\_2$, ..., $u\_{n-1}$ and $n$ other complex numbers $v\_1$, $v\_2$, ..., $v\_n$, with $|u\_i|$, $|v\_i| < r$ and $$1+\sum_i u\_i^k = \sum\_i v\_i^k \quad (*)$$ for $0 \leq k \leq cn$?

This problem is easier in that we are allowed to use complex numbers rather than real ones. It is harder in that $(*)$ has to hold for all sufficiently small values of $k$, rather than $\ell \leq k \leq 2 \ell-1$. Therefore, there is no direct reduction either way.

There is also an aesthetic change (improvement, to my mind). I made the change of variables $u\_i = 1-x\_i$ and $v\_i = 1-y\_i$. This made the extra $1$ appear on the left hand side: conceptually, it is $(1-0)^k$. As a result, I now am asking for my solutions to be in a disc around $0$, and $(*)$ is valid for $k=0$.

My bet is that the answer is "no". But I'd like to see a proof.