Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
2  
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
show 10 more comments

3 Answers 3

up vote 5 down vote accepted

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$.

share|improve this answer
    
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
1  
@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
1  
@Mach9: This answer solves the case when you allow real-number solutions (and indeed, this answer was posted prior to your edit IIRC). If we restrict to positive integers we need much more than this, so you might consider either (a) deleting the part about integers from this question, and instead post another one which is fully clarified, or (b) unaccepting this answer and awaiting one that addresses this version. I don't think the comments are sufficient for me to explain NG here; even though it doesn't answer your question on the integers, would you like me to explain them in another answer? –  anon May 8 '12 at 16:56
show 2 more comments

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.