Let $a_{i}$ and $b_{i}$ ($i=1,2, \cdots, n$) be rational numbers such that for any real number $x$ there is: \[x^{2}+x+4=\sum_{i=1}^{n}(a_{i}x+b)^{2}\] Find the least possible value of $n$.
Problem
Source: China TST 2006
Tags: algebra, polynomial, number theory, greatest common divisor, modular arithmetic, vector, linear algebra
18.06.2006 23:23
I think it is 5: For $n=5$ we have $(a_1,a_2,a_3,a_4,a_5)=(1/2,1/2,1/2,1/2,0)$ and $(b_1,b_2,b_3,b_4,b_5)=(1,-1,1,0,1)$, this works. Assume it were possble with 4 (or less), then I will prove this implies $a_1=a_2=a_3=a_4=0$ or $b_1=b_2=b_3=b_4=0$, which leads to a contradiction. Thus, assume there were rationals for which $(2a_1)^2+(2a_2)^2+(2a_3)^2+(2a_4)^2=4 =b_1^2+b_2^2+b_3^2 +b_4^2$, and $\sum_{cyc}(2a_1)(b_1)=1$. The existence of such rationals implies the existence of integer solutions (other than the trivial solution) to $\{\begin{array}{c} w^2+x^2+y^2+z^2=v^2 \\ a^2+b^2+c^2+d^2=e^2 \\ 4(ax+by+cz+wd) = ev\end{array}$. Now we have $(x^2+y^2+z^2+w^2)(a^2+b^2+c^2+d^2)=e^2v^2 =16(ax+by+cz+wd)^2$. For $n<4$: As we're dealing with integers, at least 1 factor in the LHS must be a multiple of 4, implying that either $(a,b,c)$ or $(x,y,z)$ are all even, wlog $(a,b,c)$. For $n=4$: assume both factors are not divisible by 8, then a,b,c,d,x,y,z,w are all odd, since each factor then is 4 mod 8. But from $(e/4)^2(v/4)^2 =(ax+by+cz+wd)^2$ it follows that at least one of $\frac e4,\frac v4$ is even, since $ax+by+cz+wd$ is even (the sum of 4 odd integers). Thus also here one of the factors has all its components even, wlog $(a,b,c,d)$ are 4 even integers. Now, if a solution existed, we would have that $(x^2+y^2+z^2+w^2)(a^2/4+b^2/4+c^2/4+d^2/4)= 16(ax/2+by/2+cz/2+dw/2)^2$, thus $(a/2,b/2,c/2,d/2,x,y,z,w)$ is a smaller solution. Thus, by descent, either $a=b=c=d=0$ or $x=y=z=w=0$, which is impossible. The minimum is thus $n=5$.
20.06.2006 21:13
yes, that is nice solution!
13.04.2012 06:24
By suitable transformation (letting $x=\frac{y-1}{2}$ and then multiplying through by noted square number 4), we are really looking for rational polynomials whose squares add up to $y^2+15$. Obviously $n=5$ works (one of many examples is in Peter's post). Lemma: 3 rational squares (one or two of which may be 0) cannot sum to $15$. Proof: Multiplying through by their GCD, we have relatively prime integer solutions to $x^2+y^2+z^2=15d^2$. If $d^2=1 \pmod 8$, then the RHS is $7 \pmod 8$ and can't be expressed as a sum of three squares. If $d^2=0,4 \pmod 8$, then $x,y,z,d$ must all be even, contradicting that they are relatively prime. Thus the lemma is proven. This obviously rules out $n=1,2,3$. Assume there exists a solution with $n = 4$. Then we have $a_1^2+a_2^2+a_3^2+a_4^2=1$, $a_1b_1+a_2b_2+a_3b_3+a_4b_4=0$ and $b_1^2+b_2^2+b_3^2+b_4^2=15$ Consider the vectors $a=(a_1,a_2,a_3,a_4)$ and $b=(b_1,b_2,b_3,b_4)$, with $a \cdot b=0$, $|a|=1$, $|b|=15$. There exists a matrix transformation which takes $a$ to $(1,0,0,0)$ that will have rational coefficients (EDIT: see below), and will necessarily preserve orthoganality and magnitude, so it will take $b$ to $(0,x,y,z)$, where $x^2+y^2+z^2=15$ and $x,y,z$ are rational, which we know to be impossible by our lemma. Thus, the minimal value is $n=5$. EDIT: mssmath has pointed out to me that my original argument for why this existed didn't work, but $\left[\begin{array}{cccc} a_1 & -a_2 & -a_3 & -a_4 \\ a_2 & a_1 & a_4 & a_3 \\ a_3 & -a_4 & a_1 & a_2 \\ a_4 & a_3 & -a_2 & a_1 \end{array}\right] ^{-1}$ does
23.03.2016 00:56
Can somebody kindly explain how one gets the explicit matrix transform described by Mewto55555?