Putnam problem of the day

[Anonymous No.4558123]

Let <span class="math">p(x)[/spoiler] be a polynomial that is nonnegative for all real <span class="math">x[/spoiler]. Prove that for some <span class="math">k[/spoiler], there are polynomials <span class="math">f_1(x),\dots,f_k(x[/spoiler]) such that
<div class="math">p(x) = \sum_{j=1}^k (f_j(x))^2.</div>

[Anonymous No.4558148]

Niggers.

[Anonymous No.4558154]

I don't even understand what it's about. How can I prove that for some k......how is k related to anything?!?!?!? I mean?
Are fi(x) supposed to be polinomials of orders "i"or what?

This makes me feel stupid and I think it's discriminatory.

[Anonymous No.4558164]

to understand where k comes in you need to research Sigma notation.

[Anonymous No.4558206]

>>4558164
ha ha ha ha I need to what?!?!?!?!?!?
SRSLY, Where do you learn this type of math? Is this just going by the book, starting with calculus I...?

[Anonymous No.4558281]

>>4558206
http://en.wikipedia.org/wiki/Summation
You would generally learn this before taking calculus.

>>4558154
>Are fi(x) supposed to be polinomials of orders "i"or what?
No, the polynomials can be of any order. The subscripts are just a convenient notation for telling <span class="math">f_1[/spoiler] apart from <span class="math">f_2, f_3,[/spoiler] etc. without having to have an alphabet of arbitrarily long length.

To illustrate what the question is asking:

You can prove that <span class="math">11x^2 - 2x + 8 \geq 0[/spoiler] for all <span class="math">x[/spoiler] by rewriting it as a sum of squares of polynomials, for example:
<div class="math"> 11x^2 - 2x + 8 = (x^2 + 4x + 4) + (9x^2 - 6x + 1) + x^2 + 3 = (x + 2)^2 + (3x - 1)^2 + x^2 + \sqrt{3}^2 </div>The problem is asking for proof that you can do this for any polynomial thats <span class="math">\geq 0[/spoiler] for all <span class="math">x[/spoiler].

[Anonymous No.4558449]

Is this what we're trying to prove?
<div class="math">\forall p\exists k\ni p(x)=\sum_{j=1}^k (f(x))^2</div>

[Anonymous No.4558456]

>>4558449
<span class="math">f_j(x)[/spoiler]*

[Anonymous No.4558530]

>>4558449
The polynomials <span class="math">f_j[/spoiler] are allowed to depend on <span class="math">p[/spoiler]. If you wrote this out formally, you would need to include an existential quantifier ranging over finite sequences of polynomials.

[Anonymous No.4558657]

>>4558281
thx for your input I didn't understand first what op was trying to ask.
This is an interesting problem.

[Anonymous No.4558767]

>>4558281
Thank you for your explanation......
very interesting indeed.

[Anonymous No.4558939]

Consider for all x€R, p(x)>0.

If a is a simple 0, then p(a)=0 and p'(a) =/= 0 so if p(a-)>0 then p(a+)<0.
Absurd.

So if a is a 0 for p, then a is at least a double 0.
(i mean if p(a)=0 then p'(a)=0)

So p(x)=(x-a)²*q(x) with q(x)>0.
Conseider p is order 2n.
So p(x)=(x-a1)²*(x-a2)²*...*(x-an)² (win)
If we consider p is sorder 2n+1.
p(x)=(x-a1)²*...*(x-an)²*(x-an+1) : absurd.
So p is order 2n it is write as we wanted he was:
p(x)=f(x)²
with f(x)=(x-a1)..(x-an)
& k=1.

[Anonymous No.4558965]

>>4558939
No
I want to see how you write p(x)=x^2 + 1 as
p(x)=(x-a1)²*(x-a2)²*...*(x-an)²

[Anonymous No.4559025]

>>4558939
Problem asked for a sum, not a product.

[Anonymous No.4559047]

P(x) has degree n

Trivially, if n is odd, P(x) is not nonnegative.

By induction, we can complete the square three terms at a time.

The formal arguement is left as an exercise to the plebs.

[Anonymous No.4559071]

>>4559047
3 at a time? I think you're going too fast here. Intuitively, I'd say that if p's degree is n, in the worst case where you're not lucky with simplifications, you need up to k=n/2 roughly (well, maybe n/2-1), not n/3.

[Anonymous No.4559082]

Can't you just say that since p(x) is always positive then it is the square of some q(x), [p(x)=(q(x))^2] and then let f_j(x) = q(x)_j/[sqrt(k)]? The sum is then 1/k*{[q_1(x)]^2+[q_2(x)]^2+...+[q_k(x)]^2} = 1/k*{k*[q(x)]^2} = [q(x)]^2 = p(x)?

This can't be right but I'm so tired at this point I don't know why it's wrong.

[Anonymous No.4559088]

>>4559071

Nope, doing it (intelligently) three at a time means you end up in one of three situations:

1) no remainder
2) constant remainder
3) remainder of two terms which you can complete the square on

try it

[Anonymous No.4559137]

>>4559088
Say I take <span class="math">1+ax+bx^2+cx^3+dx^4+ex^5+fx^6[/spoiler] with <span class="math">a,b,c,d,e,f>0[/spoiler].

I guess you start by taking <span class="math">(1+\frac{a}{2}x)^2[/spoiler]. You're down to <span class="math">(b-a^2)x^2+c^3+d^4+ex^5+fx^6[/spoiler], or, well, <span class="math">b'x^2+c^3+d^4+ex^5+fx^6[/spoiler], where you can choose to have <span class="math">b'>0[/spoiler]. Now you can rewrite this as <span class="math">b'x^2(1+c'x+d'x^2+e'x^3+f'x^4)[/spoiler] with <span class="math">c'=c/b',\ d'=d/b',\ e'=e/b',\ f'=f/b'[/spoiler] all >0. So you can go on with the same process in the polynomial within brackets. With this technique, you only remove 2 terms each time if you're unlucky. You had something better in mind?

[Anonymous No.4559266]

I'm probably missing something critical, but isn't f(x) always a real number? in which case square(f(x)) will always be non negative, Making this a summation of non negative reals? which would either be 0 or a positive number. Meaning f(x)'s can be any polynomial at all as long as they're defined at x?

[Anonymous No.4559281]

>>4559266
The question says that for arbitrary (any) p(x), p(x) = the sum shown, not that for any f1(x), ..., fk(x) for any k, (f1(x))^2 + ... + (fk(x))^2 equals a nonnegative polynomial (which of course is trivial).

[Anonymous No.4559292]

So we are asked to prove that any polynomial p(x) that is nonnegative for all x can be represented as the sum of k polynonomials, each of which is the square of a polynomial f(x)?

Even degree polynomials ax^(2t) can be trivially accounted for by f_t(x) = sqrt(a)*x^t

If it is positive for all x, it means that p(x) is even.

So all we have to account for are the odd terms:

You just factor the coefficient of each odd term into a convenient 2ab form, and let a^2*x^(2s+2) + 2abx^(2s+1) + b^2*x^(2s) = (ax^(s+1) + bx^(s))^2

Then you subtract a^2 and b^2 from the two even terms around.

[Anonymous No.4559296]

So we are asked to prove that any polynomial p(x) that is nonnegative for all x can be represented as the sum of k polynonomials, each of which is the square of a polynomial f(x)?

Even degree terms ax^(2t) can be trivially accounted for by f_t(x) = sqrt(a)*x^t

If it is positive for all x, it means that p(x) is even.

So all we have to account for are the odd terms:

You just factor the coefficient of each odd term into a convenient 2ab form, and let a^2*x^(2s+2) + 2abx^(2s+1) + b^2*x^(2s) = (ax^(s+1) + bx^(s))^2

Then you subtract a^2 and b^2 from the two even terms around.

[Anonymous No.4559316]

>>4559296
>Even degree terms ax^(2t) can be trivially accounted for by f_t(x) = sqrt(a)*x^t
No, some coefficients of even terms can be negative.

[Anonymous No.4559324]

This is silly but, let k=1 (since it says for some k, so we can pick one) and f(x) be sqroot(P(x)), which just gives as P(x) = |f(x)|

what did I miss?

[Anonymous No.4559330]

>>4559324
f has to be a polynomial.

[Anonymous No.4559420]

>>4559316

Indeed.

The first term has to be positive, so once you accounted for the odd terms and are left with the even ones, you pair negative terms with the preceding positive term.

Say you're left with αx^4 - βx^2 + γ

You factor β into a convenient 2ab form and let a^2*x^4 - 2abx^2 + b^2 = (ax^2 - b)^2

I'm not sure what to do afterward, though

Generalizing for any even exponent gets trickier as you have to let a^2*x^(4s) - 2ab(2s-1)*x^(2s) + b(2s-1)^2 = (ax^(2s) - b(2s - 1))^2,

Which involves adding a term with twice a higher exponent, running in the risk of simply adding a bigger negative term to account for to the original polynomial...

[Anonymous No.4559429]

Here goes my first attempt at a proof on this site.


Trying to use the contra-positive. So:
for all k, for all polynomials f, any combination of these added by, (f(x))^2 for each f(x), not equal to P(x) implies that P(x) is negative. So I need to show that the assumption spans [0, infinity).
Can we just say that no matter what function, if it is non zero, f(x)^2 is positive or zero, so no matter how many functions added, it will be positive or zero. Simply take the function x^2, which is non-negative, with is among all non negative functions, and has co-domain [0,infinity), and since f(x) is squared, it will never be negative, no matter what f(x) is. So, all combinations for summations of all polynomials f(x) for all k >= 1, have the span of [0,infinity). So P(x) must be not non-negative, or, better said, negative. Since this was the contra-positive, its contra-positive must be true, which is the question.

Q.E.D?

[Anonymous No.4559778]

OK, here's kind of constructive proof by induction:

First remark: power of polynomial is even (for odd power far enough from 0 highest power would dominate and drive polynomial negative either for <span class="math">x>0[/spoiler] or for <span class="math">x<0[/spoiler]).
Second remark: if non-negative polynomial has any roots, their degeneracy is even. Indeed, let's assume that our polynomial has root in <span class="math">a[/spoiler] with degeneracy <span class="math">k[/spoiler], where k is odd. Then it can be represented as <span class="math">p(x)=g(x)\cdot(x-a)^k[/spoiler], where <span class="math">g(a)\neq0[/spoiler]. Since <span class="math">g(x)[/spoiler] is polynomial, it's continuous, so in some interval around <span class="math">a[/spoiler] it doesn't change sign. If it's positive, then for <span class="math">x<a[/spoiler] in that interval <span class="math">p(x)[/spoiler] would be negative; similar for negative <span class="math">g(x)[/spoiler]. Hence, we got a contradiction, which means that k should be even.

[Anonymous No.4559783]

>>4559778 cond't

Now, induction:
If polynomial is of power 0, the problem is trivial.
Now, suppose that for some even n we know how to represent polynomial of the power of <span class="math">n[/spoiler] as a sum of squares. Let's now consider polynomial of the power <span class="math">n+2[/spoiler] (it can't be <span class="math">n+1[/spoiler], since <span class="math">n+1[/spoiler] would be odd).
If it has any roots, their degenracy is even (as shown above). Then, represent <span class="math">p(x)=g(x)\cdot(x-a)^{2m}[/spoiler]. The power of <span class="math">g(x)[/spoiler] is at most n, so according to the induction step we know how to represent it as a sum of squares: <span class="math">g(x)=\sum_{j=1}^{k}(f_j(x))^2[/spoiler]. But then <span class="math">f(x)=g(x)\cdot(x-a)^{2m}=\sum_{j=1}^{k}(f_j(x))^2\cdot(x-a)^{2m}=\sum_{j=1}^{k}(f_j(x)\cdot(x-a)^m)^
2[/spoiler] - also sum of squares.
Now, if <span class="math">g(x)[/spoiler] doesn't have any roots, it's strictly positive, so it has a positive lower boundary <span class="math">b[/spoiler]. Then <span class="math">g'(x)=g(x)-b[/spoiler] is non-negative (by definition of lower boundary) and has at least one zero. Therefore we know how to deal with it, so he have <span class="math">g'(x)=\sum_{j=1}^k(f'_j(x))^2[/spoiler]. Then <span class="math">g(x)=g'(x)+b=\sum_{j=1}^k(f'_j(x))^2+b=\sum_{j=1}^{k+1}(f'_j(x))^2[/spoiler], where <span class="math">f_{k+1}(x)=\sqrt(b)[/spoiler] and <span class="math">f_j(x)=f'_j(x)[/spoiler] for <span class="math">1\leq j \leq k[/spoiler].

[Anonymous No.4559819]

>>4558449
What does the big E mean?

[Anonymous No.4559827]

>>4559819
see
http://en.wikipedia.org/wiki/Summation
also read
>>4558281

[Anonymous No.4559844]

>>4559783
> g'(x)=g(x)-b ... has at least one zero
This depends on g attaining its minimum. There are many non-negative (non-polynomial) functions that don't, for example <span class="math">\displaystyle{\frac{1}{1+x^2}}[/spoiler].

[Anonymous No.4559853]

>>4559819
backwards E means "there exists"

[Anonymous No.4559858]

>>4559853
no, that's a 3.

[Anonymous No.4559876]

>>4559844
Yes, I forgot to add this part. It should be quite obvious that if p(x) is non-negative non-constant polynomial, for large enough x it will be greater than some positive constant A. That means, that p(x) reaches its minimum inside some finite interval, and since it's continuos everywhere on real axis, there exist a point x0 such that f(x0)=b (b is lower bound).

[Anonymous No.4559894]

>>4559858
>In predicate logic, an existential quantification is the predication[1] of a property or relation to at least one member of the domain. It is denoted by the logical operator symbol ∃ (pronounced "there exists" or "for some"), which is called the existential quantifier.

http://en.wikipedia.org/wiki/Existential_quantification

oh, okay bro

[Anonymous No.4560383]

>>4559894
thats so 1337

[Anonymous No.4560384]

>>4558939
that makes no sense whatsoever..

[Anonymous No.4560414]

Isn't that what a sum is?

[Anonymous No.4560430]

>any value squared is positive (for all real x)
>the summation of those values (those f(x)'s) will always be positive
>left hand side is always positive
>right hand side is always positive

[Anonymous No.4560437]

>>4560430
are you retarded? That's trivial and not what they ask to prove..

[Anonymous No.4560448]

>>4560437
Okay, how would you solve it then?

[Anonymous No.4560464]

>>4560448
I don't know, but atleast I'm not just spewing out some bullshit without understanding the question

[Anonymous No.4560537]

>>4558154
>it's discriminatory
It's discriminatory against 'tards.

[Anonymous No.4560798]

<span class="math">
\mathrm{Maybe\ easiest,\ if\ least\ impressive,\ way...\ If\ you\ keep\ squaring\ something\ it\ should\ go\ positive\ eventually!\ If\ }
\\
p(x)p(x) = p(x)^2 \mathrm{\ and\ } p(x)^2p(x)^2 = p(x)^4
\\
\mathrm{\ then\ } p(x)p(x) +p(x)^2p(x)^2 = p(x)^2 + p(x)^4 = p(x)^2(1+p(x)^2) = h(x)
\\
\mathrm{and\ since\ you\ can\ build\ other\ polynomes\ out\ of\ the\ first,\ then\ the\ polynome\ p(x)\ must\ itelf\ be\ composed\ of\ other\ polynomes\ f_n(x)\ to\ be\ a\ polynome,\ or\ made\ from\ basic\ elements.\ }
[/spoiler]

[Anonymous No.4560803]

<span class="math"> \mathrm{Maybe\ easiest,\ if\ least\ impressive,\ way.\ If\ you\ keep\ squaring\ something\ it\ should\ go\ positive\ eventually!\ If\ }
p(x)p(x) = p(x)^2 \mathrm{\ and\ } p(x)^2p(x)^2 = p(x)^4
\mathrm{ }
\mathrm{\ then\ } p(x)p(x) +p(x)^2p(x)^2 = p(x)^2 + p(x)^4 = p(x)^2(1+p(x)^2) = h(x)
\mathrm{ }
\mathrm{and\ since\ you\ can\ build\ other\ polynomes\ out\ of\ the\ first,\ then\ the\ polynome\ p(x)\ must\ itelf\ be\ composed\ of\ other\ polynomes\ f_n(x)\ to\ be\ a\ polynome,\ or\ made\ from\ basic\ elements.\ }
[/spoiler]

[Anonymous No.4561082]

>>4559894
that's a symbol, not a backwards letter

don't bro me before you know me, chump.

[Anonymous No.4561381]

whats with all the retards today? we had these threads every day for months and now the primary school shows up?