# Solve $V_1+V_2+\cdots+V_k=A, V_1^2+V_2^2+\cdots+V_k^2=B$ in positive integers

There have been changes made to the second equation in the pair that will be worth looking at. All values for the solutions must be non-zero positive integers (natural numbers). Please note, all values must be distinct!

According to this equation,

$$V_1^2+V_2^2+\cdots+V_k^2 = \left(\frac{2\left(V_{1}+V_{2}+\cdots+V_{k}\right)}{k}-V_{1}\right)^{2}+\left(\frac{2\left(V_{1}+V_{2}+\cdots+V_{k}\right)}{k}-V_{2}\right)^2+\cdots+\left(\frac{2\left(V_{1}+V_{2}\cdots+V_{k}\right)}{k}-V_{k}\right)^{2}$$

(Source: Personal observation)

There can be at most only two common solutions to the two equations $V_{1}+V_{2}\cdots+V_{k}=A$ and $V_{1}^{2}+V_{2}^{2}+\cdots +V_{k}^{2}=B$, where $V_{1},V_{2},\cdots V_{k}$ denote different variables whose values I wish to find for a fixed value $A$ and $B$ for each of the two equations.

Is it possible to solve this problem with the least of guesswork application? What if $k$ were to extend into really large numbers, creating about $10^{10}$ variables and above? If not possible (for very large numbers), never mind. Thanks all!

PS Sorry if the tags don't match up with the topic.

-
The way this is written, I am uncertain of what you are trying to solve. $V_1 + V_2 + \cdots + V_k = A$ is fine, but what is $V_1^2 + V_2^2 + \cdots + V_k^2$ equal to in this question? – Nicholas Stull May 8 '12 at 11:50
Have you seen the Newton-Girard identities by any chance? – J. M. May 8 '12 at 11:50
@JM: Nope, I haven't. – Mach9 May 8 '12 at 11:55
@Nicholas Stull: I mean to say, if you find one common solution for the variables of the two given equations $V_{1}+V_{2}\cdots+V_{k}=A$ and $V_{1}^{2}+V_{2}^{2}\cdots +V_{k}^{2}$, you will get another solution if it exists using the equation $V_{1}^{2}+V_{2}^{2}\cdots+V_{k}^{2}=(\frac{2(V_{1}+V_{2}\cdots+V_{k})}{k}-V_{1}‌​)^{2}+(\frac{2(V_{1}+V_{2}\cdots+V_{k})}{k}-V_{2})^{2}\cdots+(\frac{2(V_{1}+V_{2}‌​\cdots+V_{k})}{k}-V_{k})^{2}$. Hope that clears it up. – Mach9 May 8 '12 at 11:58
No, I haven't taken that into account. How could I? You only added that condition an hour ago :-) – Jyrki Lahtonen May 8 '12 at 18:04

There are infinitely many solutions to these equations (unless $k = 2$, in which case there are 2 solutions, but where the other one can be obtained by interchanging $X_1$ and $X_2$. The set of zeros of any polynomial of the form

$$x^k - A x^{k - 1} + \frac{A^2 - B}{2} x^{k - 2} + a_{k - 2} x^{k - 2} + \dots + a_1 x + a_0$$

with $a_0,\dots,a_{k - 2}$ arbitrary will satisfy.

To see this, note for any polynomial, the coefficients are $$x^k + (- s_1) x^{k - 1} + s_2 x^{k - 2} + \dots + (-1)^k s_k$$

where the $s_i$ are the elementary symmetric polynomials in the zeros of this polynomial. Clearly, $A$ equals the first symmetric polynomial in the $X_i$, and it's easy to check that $(A^2 - B)/2$ equals the second symmetric polynomial in the $X_i$. We can then pick the other coefficients arbitrarily, and will still have the sum of the roots equal to $A$, and the sum of their squares equal to $B$.

-
And what if the values for each variable must be an integer greater than zero (aka natural numbers)? Are the number of solutions still infinite? I assumed a problem that looks this simple must have an equally simple answer. As it turns out, I think I'm wrong. – Mach9 May 8 '12 at 12:44
@Mach9: In the integers $V_1^2+\cdots+V_k^2=B$ alone can only have finitely many solutions. On top of that, if we restrict to positive integers, $V_1+\cdots+V_k=A$ must have finitely many solutions (again, all by itself). – anon May 8 '12 at 12:47
@anon: Hmm... I'm still skeptical. Can I have an example? – Mach9 May 8 '12 at 12:49
@Mach: what Lieven has been describing is precisely the Newton-Girard identity that I was (unsuccessfully, it seems) trying to get you to read about. – J. M. May 8 '12 at 12:57

The point of this answer is to describe a way of proving that there will be several solutions for some combinations of $(A,B,k)$.

Let us (temporarily) fix an upper bound $n$ for the variables $V_i$. Without loss of generality we can then assume that $n\ge V_1>V_2>\cdots>V_k>0$. There are ${n\choose k}$ such vectors $(V_1,V_2,\ldots,V_k)$, and let us denote the set of such vectors by $V(n,k)$. For all such vectors we have $0<V_1+V_2+\cdots+V_k<nk$ and $0<V_1^2+V_2^2+\cdots+V_k^2<n^2k$. Consider the function $f:V(n,k)\rightarrow \{1,2,\ldots,nk\}\times \{1,2,\ldots,n^2k\}$ defined by $(V_1,V_2,\ldots,V_k)\mapsto(\sum_i V_i, \sum_i V_i^2)$.

The are at most $n^3k^2$ possible values for $f$. Therefore there exists at least one vector $(A,B)$ that occurs as a value of at least $$N(n,k)=\left\lceil\frac{{n\choose k}}{n^3k^2}\right\rceil$$ distinct vectors $V=(V_1,V_2,\ldots,V_k)$.

It follows immediately that $N(n,k)$ takes arbitrarily large values. For example, if $k=4$, then $$N(n,4)=\left\lceil \frac{n(n-1)(n-2)(n-3)}{n^34! 4^2}\right\rceil>\frac{(n-1)(n-2)(n-3)}{384n^2}.$$ Here in the numerator we have a cubic polynomial of $n$, so it "wins" over the quadratic denominator for large enough $n$ by any factor you wish.

Marginally sharper bounds can be derived by using tighter upper and lower bounds for the two components of the values of $f$.

For a numerical example let us pick $n=1000$, $k=4$. There are $${1000\choose 4}=41417124750$$ vectors $(V_1,V_2,V_3,V_4)$ with $1000\ge V_1>V_2>V_3>V_4>0.$ Their sum has at most $4\cdot1000=4000$ possible values. The sum of their squares has at most $4\cdot1000^2=4000000$ possibilities. Therefore some combination of $(\text{sum},\text{sum of squares})$ occurs at least $$\frac{41417124750}{4000\cdot4000000 }\approx 2.6$$ times, i.e. for some pair $(A,B)$ of integers there are at least 3 different solutions such that $1000\ge V_1>V_2>V_3>V_4>0$, all integers.

Surprisingly often a counting argument and the principle "the most frequent case occurs at least as often as the average" works.

-
To address one further question raised in a comment. If $k=5$, then $N(n,k)$ grows as a quadratic polynomial in $n$. When we insist on distinct values for the variables, it is impossible to keep $n$ fixed and let $k$ grow, so my earlier comment to that effect became meaningless, when the distinctness assumption was added. – Jyrki Lahtonen May 8 '12 at 19:43

Chapter 8, Mehrgradige Ketten, of Gloden's book, Mehrgradige Gleichungen, is devoted to this sort of thing and generalizations. Here's a small numerical example: $$\displaylines{1+17+18=2+13+21=3+11+22=6+7+23=36,\cr1^2+17^2+18^2=2^2+13^2+21^2=3^2+11^2+22^2=6^2+7^2+23^2=614\cr}$$ Gloden writes, "Wir geben zuerst eine Methode an, um zweigradige Ketten mit 3 Gliedern in jedem Element und einer beliebigen Anzahl Elemente zu bilden." My German's little weak, but I think he's saying he gives a method for finding as many triples of integers as you want with the same sum and the same sum of squares. The idea seems to be, find a number that has many representations as $a^2+ab+b^2$. If $$a^2+ab+b^2=c^2+cd+d^2$$ then the triples $(a,b,-a-b)$ and $(c,d,-c-d)$ have the same sum and the same sum of squares.

Now, the number of representations of $n$ as $a^2+ab+b^2$ has to do with the number of primes $p\equiv1\pmod3$ dividing $n$. So for example \eqalign{91&=7\times13=6^2+5*6+5^2=9^2+1*9+1^2\cr&=10^2+(-1)*10+(-1)^2=11^2+(-5)*11+(-5)^2\cr} which gives you the triples $$(6,5,-11),(9,1,-10),(10,-1,-9),(11,-5,-6)$$ and then add 12 to everything to get positive integers: $$(18,17,1),(21,13,2),(22,11,3),(23,7,6)$$ which is the example given earlier. If you start with $n=7\times13\times19$, you'll get 8 triples with the same sum and same sum of squares; start with $n=7\times13\times19\times31$, 16 triples; etc.

There are asymptotically $x/\log x$ primes up to $x$, and the product of the primes up to $x$ is asymptotically $e^x$. Restricting to the primes 1 more than a multiple of 3 should cut those asymptotic estimates to $x/(2\log x)$ and $e^{x/2}$, respectively. Then that product will have about $2^{x/(2\log x)}$ representations as $a^2+ab+b^2$, so you'll get that many triples, using numbers on the order of $e^{x/4}$ if I've thought this out correctly.

-