Positive-definite Polynomial Game

Given $n$ a positive even number. Alice and Bob are playing a game as follows. On the board initially there are $n+1$ unassigned numbers: $a_0, a_1, \dots, a_n$.

With Alice going first, each player alternatingly chooses an unassigned number and assigns a positive real value to it. Once all numbers have been assigned values, polynomial $P(x)$ is defined as:

$$P(x) = a_nx^n + \dots + a_1x +a_0$$

If $P(x) > 0$ for all $x \in R$ then Alice wins, otherwise Bob wins. Determine who has a winning strategy.

Variant 1: if the number $a_0$ is already fixed to 1, so there are only $n$ numbers on the board, who has a winning strategy?

Variant 2: if the winning condition is flipped: Alice wins if there exists an $x$ such that $P(x) < 0$.

Solution

The player who moves last has a winning strategy, regardless of winning condition. Variant 1 merely flips who moves last. If Variant 1 is in play and Alice moves first, then Bob moves last and Bob has a winning strategy. Note that $P(x)$ is positive definite iff $tP(x)$ for all $t$ positive numbers, so the magnitude of each number doesn't matter, only the relative magnitude of all coefficients. Therefore, the number "1" set by variant 1 is arbitrary and the variant merely ensures Bob's ability to win. For the rest of this solution, we assume that variant 1 is not in play and Alice goes first, and she should assign $a_0 = 1$. The rest of the proof can then be extensible to variant 1 while flipping the name Alice and Bob.

Lemma: polynomial $P(x)$ with positive coefficients are positive definite if and only if $P(1/x) > 0$ for all $x \neq 0$. This lemma is easy to see because $P(0) > 0$ anyways.

Part 1: proving that Alice can ensure positive definiteness.

Assume that $a_0 = 1$ has already been assigned. Now divide the remaining coefficients into pairs: $(a_1,a_2), (a_3,a_4), \dots, (a_{n-1},a_n)$. Whenever Bob makes a move and assigns a value to a coefficient, Alice assigns a value to its pair accordingly. We claim that Alice will be able to choose her value such that the resulting polynomial $Q_k(x) = a_{2k}.x^{2k} + a_{2k-1}.x^{2k-1} + 2/n$ is positive definite.

Proof: From the lemma, $Q_k$ is positive definite iff $R_k(x) = \frac{2}{n}x^{2k} + a_{2k-1}x + a_{2k}$ is positive definite.

If Bob chooses $a_{2k-1}$ then Alice can choose $a_{2k}$ large enough to make $R_k(x)$ positive definite. Whichever local minimum may exist due to Bob's choice, Alice can compensate it enough by adding a positive constant term to the whole polynomial.

If Bob chooses $a_{2k}$ then there exists an $a_{2k-1}$ small enough to make $R_k(x)$ positive definite. If $x \geq 0$ positive then $R_k(x) > 0$ because all coefficients are positive. But if $x < 0$ then by AM-GM:

$$ \frac{2}{n}x^{2k} + a_{2k} = \frac{2}{n}x^{2k} + \frac{a_{2k}}{2k-1} + \dots + \frac{a_{2k}}{2k-1} \geq 2k \sqrt[2k]{\frac{2}{n}.\left(\frac{a_{2k}}{2k-1}\right)^{2k-1}}.(-x) > -a_{2k-1}x$$

for small enough positive value of $a_{2k-1}$.

The final polynomial can be expressed as the sum:$P = Q_1 + \dots + Q_{n/2}$, and because at each step Alice can always ensure that the resulting $Q_k(x)$ is positive definite no matter what Bob chooses, then the final polynomial is also guaranteed to be positive definite.

Part 2: proving that Alice can ensure non-positive definiteness.

If $n=2$ then Alice can always ensure that the discriminant of the quadratic polynomial is positive, therefore the polynomial has two real roots. For $n > 2$, the general strategy is as follows: divide the coefficients into pairs as above, and Alice's assignment is always the pair of Bob's assignment as well. But this time the difference is that, after each of her move, Alice ensures that the TOTAL polynomial $P(x)$ is negative for some values of $x$ and maintains this invariant throughout the game.

First note that if Bob ever chooses an even coefficient $a_2,a_4,\dots$ then Alice's job is really easy. Take the current value of $P(-1)$ (after including Bob's addition), and by choosing her corresponding odd coefficient large enough, she can make $P(-1)$ negative because she's adding a multiple of $x^{2k-1}$ which is negative at $x=-1$.

Consider the first round. If Bob chooses $a_{2k}$ then Alice chooses large enough $a_{2k-1}$ as described above. But if Bob chooses $a_{2k-1}$, Alice can choose small enough $a_{2k}$ to ensure non-positive definiteness. The current resulting polynomial is $a_{2k-1}x^{2k-1}+1 < 0$ as $x \to -\infty$, so pick any $y$ such that $a_{2k-1}y^{2k-1}+1 < 0$. Then Alice chooses $a_{2k}$ small enough such that $0 < a_{2k} < \frac{-a_{2k-1}y^{2k-1}-1}{y^{2k}}$ so that $a_{2k}y^{2k}+a_{2k-1}y^{2k-1}+1 < 0$

So once the invariant is established after the first round, then Bob has no choice but to keep choosing even coefficients. If Bob chooses an odd coefficient, then whichever value of $x$ caused $P(x)$ to be negative at the end of last round will continue to be (even more) negative, so Alice simply chooses a very small value of the corresponding even coefficient as described above. But even if Bob chooses an even coefficient, Alice can counter by choosing a large enough odd coefficient. Therefore she maintains the invariant of $P$ being non-positive definite until the end of the game.

AM-GM-HM

From OSP SMA 2018 For positive $a,b,c$ such that $1/a + 1/b + 1/c = 3$ prove that: $$a+b+c + \frac{4}{1+(abc)^\frac{2}{3}} \geq 5$$

Monic polynomial divisible by 2018

Let $P(x)$ a monic polynomial (polynomial having leading coefficient one) with integer coefficients such that $P(k)$ is divisible by 2018 for all integer $k$. Find the smallest possible degree of $P$

Solution

Note that $P(x) = x(x+1)(x+1) \dots (x+1008)$ is always divisible by 1009, because one of the factors is always divisible by 1009. It's also even. Therefore $P(x)$ is a polynomial that satisfies the problem requirement, having degree 1009. We shall show that this degree is minimal.

We call a polynomial (not necessarily monic) "good" if it has property that $P(k)$ is divisible by 2018 for all integer $k$.

Suppose $P_n(x)$ is a good monic polynomial having degree $n$, then we apply the following procedure: let $P_{n-1}(x) = P_n(x+1) - P_n(x)$. Then $P_{n-1}$ is a polynomial of degree $n-1$ (because the $x^n$ terms cancel out). Because $P_n$ is good, then $P_{n-1}$ is also good. Furthermore, the leading coefficient of $P_{n-1}$ is $n$, because the only source of $x^{n-1}$ terms is from the expansion of $(x+1)^n$. The other $x^{n-1}$ terms cancel out as well.

We continue this process to obtain $P_{n-2}, P_{n-3},$ and so on. At each step, define $P_m(x) = P_{m+1}(x+1) - P_{m+1}(x)$. We claim the following facts:

1. $P_m$ is good

2. The leading coefficient of $P_m$ is $n(n-1)(n-2) \dots (m+1) = \frac{n!}{m!}$

The two facts can be shown simultaneously using induction. It's obviously true for $m=n$, and as we demonstrated, it's also true for $m=n-1$. If it's true for $m+1$ then it's easy to see that it's true for $m$ as well, using the same argument we showed above.

Thus, at some point, we will arrive at $P_0$ having leading coefficient $n!$. That is, $P_0(x) = n!$ for all $x$, and this must be divisible by 2018 because $P_0$ is good. Therefore $n!$ is divisible by 2018.

What we showed was the necessary condition for a monic polynomial to be good. That is, if it has degree $n$ then $n!$ is divisible by 2018. The smallest possible such $n$ is 1009 because 1009 is prime. But we also showed a sufficient condition, that there exists a polynomial with degree 1009 that's both monic and good. Thus the answer is 1009.

Product of cosines

For $n$ natural number, and $a = \frac{2\pi}{2n+1}$ find the value of $$\cos a . \cos 2a . \cos 3a . \dots . \cos na$$

Solution

We first prove the following claim: for any $n$ positive odd number, $$\sin (nx) = \sin x P_n (\cos x)$$ $$\cos (nx) = \cos x Q_n (\cos x)$$ where $P_n(t)$ and $Q_n(t)$ are polynomials in the form of $2^{n-1} t^{n-1} + ...$ (In other words, they have degree $n-1$ and the leading coefficient $2^{n-1}$

Proof by induction, evident for $n=1$ and $n=3$. Inductive step: $$\sin (n+2)x = \sin nx \cos 2x + \cos nx \sin 2x = \sin x P_n (\cos x) (2 \cos^2 x - 1) + \cos x Q_n (\cos x) .2\sin x \cos x$$ $$ = \sin x ( P_n (\cos x) (2 \cos^2 x - 1) + 2\cos^2 x Q_n (\cos x) ) = \sin x P_{n+2} (\cos x)$$ where $P_{n+2}$ has degree $n+2$ and the leading coefficient $2. 2^{n-1} + 2.2^{n-1} = 2^{n+1}$

Likewise: $$\cos (n+2) x = \cos nx \cos 2x - \sin nx \sin 2x = \cos x Q_n(\cos x)(2 \cos^2 x - 1) - \sin x P_n (\cos x) . 2 \sin x \cos x$$ $$ = \cos x ( Q_n(\cos x)(2 \cos^2 x - 1) - 2 P_n (\cos x) (1 - \cos^2 x)) = \cos x Q_{n+2} (\cos x)$$ like before, the polynomial $Q_{n+2}$ has degree $n+2$ and leading coefficient $2^{n+1}$

So now, observe that $x = 0,a,2a, \dots, 2na$ are all solutions of the equation $$\cos (2n+1)x = 1 = \cos x Q_{2n+1}(\cos x)$$ Therefore $t = \cos 0, \cos a, \dots, \cos 2na$ are all roots of the polynomial $$ S(t) = tQ_{2n+1}(t) - 1$$ Because $S(t)$ has degree $2n+1$, then $\cos 0, \dots \cos 2na$ are ALL of the roots, and the product of all those roots is $\frac{1}{2^{2n}}$ (because $S(t)$ has leading coefficient $2^{2n}$

Now, $\cos a = \cos 2n a, \cos 2a = \cos (n-1) a$ and so on. So: $$\cos 0 . \cos a .\dots. \cos 2na = 1 . (\cos a. \dots . \cos na)^2 = \frac{1}{2^{2n}}$$ So: $$\cos a . \dots . \cos na = \frac{1}{2^n}$$

Polynomial and divisibility

Find an integer polynomial $P(x)$ with the lowest degree that satisfies the following:

$P(x)$ is divisible by $x^2+x+1$

$P(x)+3$ is divisible by $x^{2017} -1$

Solution

Let $Q(x) = x^2+x+1$ and $R(x) = x^{2016} + \dots + 1$. It's easy to show that $Q$ and $R$ are relatively prime.

The LCM for both divisors is thus $(x-1)Q(x)R(x)$ which has degree 2019.

Now if $P$ and $P'$ both satisfy the problem statement, then $P-P'$ must be divisible by $(x-1)Q(x)R(x)$.

On the other hand, if $P$ satisfies the problem statement, then $P + A(x).(x-1)Q(x)R(x)$ also satisfies the problem statement for any integer polynomial $A(x)$.

Therefore, we can find at most one $P(x)$ with degree less than 2019, because if there were two such polynomials, their difference must be divisible by $(x-1)Q(x)R(x)$ but that difference has degree less than 2019, so the difference must be zero. That one polynomial is our answer.

To find it: let $t$ be the root of $Q(x)$. We want to find $P(x)$ such that:

$$P(x)+3 = S(x).(x-1).R(x)$$ for some $S(x)$, with $S(x) = ax+b$. We know that it's possible for $S$ to be a linear function because we've established that there exists a $P$ with degree less than 2019, and $R$ has degree 2016.

$$P(t) + 3 = (at+b).(t-1).R(t)$$

$P(t) = 0$ because $P(x)$ is divisible by $Q(x)$ and $Q(t) = 0$.

$R(t) = t^{2016} + \dots + t + 1 = 1$ because every 3 consecutive terms in $t^{2016} + \dots + t$ sum to zero (because $Q(t) = 0$).

So: $$ 3 = (at+b)(t-1)$$ $$at^2 + (b-a)t - b-3 = 0$$ $$a(-t-1) + (b-a)t - b-3 = 0$$ $$ (b-2a)t=a+b+3$$

Solving for the system:$b-2a = 0, a+b+3 = 0$ gives us: $a = -1, b= -2$ so $S(x) = -(x+2)$

Plugging in to the equations, we find:

$$P(x) = -(x+2)(x^{2017}-1) - 3 = -x^{2018} - 2x^{2017} + x -1 = -x^2(x^{2016}-1) -2x(x^{2016}-1) -( x^2+x+1) $$

Each term in the right-most expression is divisible by $Q(x)$ because $(x^{2016}-1)$ is divisible by $x^3-1$ so $P(x)$ is also divisible by $Q(x)$

Sum of products of 3

Let $p>3$ be a prime number, and let $S={2,3,\dots,p-1}$ Let $X = \sum_{ i < j < k \in S} ijk$, prove that $X + 1$ is divisible by $p$.

Solution

Because $p$ is odd, let $p = 2m+1$. First we calculate $1^2 + \dots + (p-1)^2 \mod p$. We do this by realizing that $1^2 = (p-1)^2 \mod p, 2^2 = (p-2)^2 \mod p$ and so on. Every term will have a "pair", so the sum is: $$1^2 + \dots + m^2 + (m+1)^2 + \dots + (p-1)^2$$ $$ \equiv 2 (1 + \dots + m^2) \mod p$$ $$ \equiv m(m+1)(2m+1) \equiv 0 \mod p$$ because $2m+1 = p$. This means that $2^2 + \dots + (p-1)^2 \equiv -1 \mod p$

Next we calculate $1^3 + \dots + (p-1)^3 \mod p$. We do this by realizing that $p = 1 + (p-1) | 1^3 + (p-1)^3, p=2+(p-2) | 2^3+(p-2)^3$ and so on. Like above, each term will have a pair that it cancels out with. Thus $1^3 + \dots + (p-1)^3 \equiv 0 \mod p$, so $2^3 + \dots + (p-1)^3 \equiv -1 \mod p$.

Now we also have that $1+\dots + (p-1) \equiv 0 \mod p$, so $2 + \dots + (p-1) \equiv -1 \mod p$. From this, we have: $$ 2\sum_{i < j \in S} ij \equiv (-1)^2-(-1) \equiv 2 \mod p $$ $$\sum_{i < j \in S} ij \equiv 1 \mod p$$ because $p$ is odd.

Now, for any real numbers $a_1, \dots, a_n$, let us define the following variables: $$A = a_1 + \dots + a_n$$ $$B = \sum_{i < j} a_i a_j$$ $$C = \sum_{i \neq j } a_i^2 a_j$$ $$D = \sum_{i < j < k} a_i a_j a_k$$ $$E = a_1^2 + \dots + a_n^2$$ $$F = a_1^3 + \dots + a_n^3$$ Then we have: $$AB = (a_1+\dots+a_n)(a_1a_2 + a_1a_3 + \dots + a_{n-1}a_n) = C + 3D$$ The identity from middle to right is because for each $a_i$ in $A$, it's either paired with $a_ia_j$ or $a_j a_k$ in B. If it's paired with $a_i a_j$ then it would contribute towards $C$, otherwise it would contribute towards $3D$. Likewise, each term in $C$ and $3D$ can be traced back to $AB$. Each term $a_i^2 a_j$ in $C$ comes from $a_i$ in $A$ and $a_i a_j$ in $B$. Each term $3a_i a_j a_k$ in $3D$ comes from three sources: $a_i$ in $A$ and $a_j a_k$ in $B$ and its permutations. To further convince ourselves, $A$ has $n$ terms, and $B$ has $n(n-1)/2$ terms, so $AB$ has $n^2(n-1)/2$ terms. $3D$ has $n(n-1)(n-2)/2$ terms and $C$ has $n(n-1)$ terms, so altogether they have $n^2(n-1)/2$ terms.

Furthermore: $$C = a_1^2(A-a_1) + a_2^2(A-a_2) + \dots + a_n^2(A-a_n) = AE - F$$ So: $$3D = AB-C = F + AB-AE$$ This identity holds for any real numbers $a_i$, and it's based on pure algebraic manipulation. We can apply this identity to our set $S$. We already know that $F \equiv -1, A \equiv -1, B \equiv 1, E \equiv -1 \mod p$. From there, we have $3D \equiv -3 \mod p$, which means $(3D+3)$ is divisible by $p$. Because $p > 3$ then $D+1$ is divisible by $p$.

a,b,c,d odd powers

If $a,b,c,d$ are integers such that $a+b+c+d = 0$ then show that for any odd number $n$,

$$X_n = a^n + b^n + c^n + d^n$$

is divisible by $Y = \sqrt{-(a+b)(a+c)(a+d)(b+c)(b+d)(c+d)}$

And that if $n$ is prime, then $X_n$ is divisible by $n$ as well

First Solution

First, it is straightforward to show that $Y$ is indeed an integer.
$a+b = -(c+d)$
$a+c = -(b+d)$
$a+d = -(b+c)$
Multiplying all three, we have that $Y = |(a+b)(b+c)(c+a)|$
If $Y=0$, then $X_n = 0$ as well. So now we're going to assume that $Y > 0$. For proving divisibility purposes, we can also assume that $Y = (a+b)(b+c)(c+a)$.

Let $f(t) = (t-a)(t-b)(t-c) = t^3 - Pt^2 + Qt - R$ be a polynomial with roots $a,b,c$

We have that $Y=(a+b)(b+c)(c+a) = (P-a)(P-b)(P-c) = f(P) = PQ-R$.

Let's also define $S_n = a^n + b^n + c^n$. All we have to show is that $S_n - P^n$ is divisible by $Y$ for $n$ odd.

Now we assert the following, and prove by induction:
If $n$ is odd, then $S_n - P^n$ is divisible by $Y$
If $n=2m$ is even, then $S_n - P^n - 2(-Q)^m$ is divisible by $Y$.

We readily obtain that $S_1 = P$ and $S_2 = P^2 - 2Q$, so the assertions above are true for $n=1,2$.

Now for higher values of $n$, we have the following:
$a^{n-3}f(a) = a^n - Pa^{n-1} + Qa^{n-2} - Ra^{n-3} = 0$
similarly we can do the same for $b,c$ and add them, so that we have:
$S_n = PS_{n-1} - QS_{n-2} + RS_{n-3}$

If $n=2m$ is even, then $n-1$ is odd, $n-2 = 2(m-1)$ is even, and $n-3$ is odd. So from induction hypothesis, we can write:
$S_{n-1} = P^{n-1} + YZ_1$
$S_{n-2} = P^{n-2} + 2(-Q)^{m-1} + YZ_2$
$S_{n-3} = P^{n-3} + YZ_3$

where $Z_1, Z_2, Z_3$ are integers
So:
$$S_n = P^n + PYZ_1 - P^{n-2}Q + 2(-Q)^m -QYZ_2 + RP^{n-3} + RYZ_3$$
$$= P^n + 2(-Q)^m + P^{n-3}(PQ-R) + Y(PZ_1 - QZ_2 + RZ_3)$$
$$= P^n + 2(-Q)^m + Y(P^{n-3} + PZ_1 - QZ_2 + RZ_3)$$

which proves our induction assertion that $S_n - P^n - 2(-Q)^m$ is divisible by $Y$. For $n$ odd, we can do the same.

So $S_n - P^n = X_n$ is divisible by $Y$ for $n$ odd.

Second Solution

We have $d = -(a+b+c)$, then
$$X_n = a^n + b^n + c^n - (a+b+c)^n$$ if $n$ is odd.

For fixed values of $b,c$, let $f(a) = a^n + b^n + c^n - (a+b+c)^n$ by a polynomial of degree $n-1$ in $a$.
Note that $f(-b) = 0$ and $f(-c) = 0$. That means $X_n = f(a)$ is divisible by $(a+b)(a+c)$.

Write $f(a) = (a+b)(a+c)P(a)$ for $P$ some integer polynomial.
Now note that $f(a) = a^n - (a+b+c)^n + (b^n + c^n)$
$a^n - (a+b+c)^n$ is divisible by $(b+c)$ in a polynomic manner (not just integer divisibility), and so is $b^n + c^n$ (since $n$ is odd).

So $f(a)$ is divisible by $(b+c)$ in a polynomic manner, which means $P(a)$ is divisible by $(b+c)$.

Ternary Polynomial

A polynomial with integer coefficients is called "ternary" if its coefficients are all 1, -1, or zero.

First Question:
Find two polynomials $P(x)$ and $Q(x)$ with integer coefficients where at least one coefficient is larger than 2010, such that $P(x)Q(x)$ is ternary.

Second Question:
Does there exist a ternary multiple of $F(x) = x^2 - 3x + 1$ ?

Solution

First Question

Note that the polynomial $(x-1)(x^2-1)(x^4-1)(x^8-1) ... (x^{2^n}-1)$ is ternary. Indeed, because the coefficient of $x^k$ can only be formed in exactly one way. For digits in the binary representation of $k$ that is one, we take the $x^{2^i}$ term, and for the other digits, we take the $-1$ term.

Now, that polynomial can be factored. For example:
$$(x-1)(x^2-1)(x^4-1)(x^8-1)$$
$$=(x-1)^{4} (x+1) (x^3+x^2+x+1) (x^7+...+1)$$
$$=(x-1)^{4) (x+1) (x+1)(x^2+1) (x+1)(x^2+1)(x^4+1)$$
$$=(x-1)^4 (x+1)^3 (x^2+1)^2 (x^4+1)$$

So similarly,
$$(x-1)(x^2-1)(x^4-1)(x^8-1) ... (x^{2^n}-1)$$
$$ = (x-1)^{n+1} (x+1)^n (x^2+1)^{n-1} ... (x^{2^{n-1}}+1) $$

If we let $P(x) = (x-1)^{n+1}$ and $Q(x)$ to be the rest, we claim that we can make the largest coefficient in $P$ and $Q$ to be arbitrarily large by setting $n$ large enough. For $P$, it is clear due to binomial expansion. For $Q$, the factor $(x+1)^n$ will have a large enough coefficient, while the rest of the factors all consist of positive signs (no negative signs).

So by setting $n$ large enough, we could find $P$ and $Q$ that satisfy the desired conditions.

Second Question

We start by proving a lemma: if $s > 2$ then $s^n > s^{n-1} + ...+ s + 1$. This lemma can be proved by induction:
$s^{n+1} > 2s^n = s^n + s^n > s^n + ... + s + 1$

Now, we note that the larger root of $F$ is greater than 2, so let $r$ be this larger root. ( $r = (3 + \sqrt{13})/2 > 2$ ).

Suppose $P$ is a ternary polynomial such that $P(x) = F(x) G(x)$ for some integer polynomial $G$, then $P(r) = 0$.

But that is impossible if $r > 2$, due to the lemma above, since the largest term in $P$ cannot be offset by the rest of the terms. A contradiction.

Polynomial and divisibility

A sequence of polynomials $P_i(x)$ are defined as follows:
$P_1(x) = 1$
$P_2(x) = 1$
$P_{n+2}(x) = (x+2)P_{n+1}(x) - P_n(x), n=1,2,\dots$

Prove that for all $n > 1$, $P_n(x)^2 + x$ is divisible by $P_{n-1}(x)$

Polynomial Algorithm

Credit for this problem goes to Zeke Chin

Does there exist an algorithm for the decision problem:

Given a polynomial over $n$ variables $x_1,\cdots,x_n$ with positive integer coefficients, and a positive integer $c$, is it true that $cx_1\cdots x_n \leq P(x_1,\cdots,x_n)$ for all assignments of positive integers to $x_1,\cdots,x_n$?

For example, for $P = x_1^2 + x_2^2$ and $c=2$, the algorithm should return "Yes" since $2x_1x_2 \leq x_1^2 + x_2^2$

ABC String

How many strings of A's, B's, and C's are there that satisfy the following conditions:

1. There are $n$ A's and $2n$ total of B's and C's.

2. Every two adjacent letters are different.

2 Variable Recursion

This problem is written as an auxiliary lemma for the solution to this problem.

Suppose $f(m,n)$ is a function that is defined for non-negative integers $m,n$ where:

$f(m,n) = 0$ if $m < n$

$f(m,0) = 1 \forall m$

$\displaystyle f(m,n) = \sum_{k=1}^{n} f(k-1,k-1) f(m-k,n-k) + f(m-1,n) \forall m \geq n$

Prove that $f(m,n) = \frac{m-n+1}{m+1} \binom{m+n}{m}$

Polynomial not sum of squares

Let $P(x,y) = x^2y^4 + x^4y^2 + 1 - 3x^2y^2$

a.) Prove that $P(x,y)$ is non-negative

b.) Prove that $P(x,y)$ cannot be expressed as a sum of squares of polynomials.

Non-negative polynomials as sums of squares

Prove that any non-negative real polynomials can be expressed as a sum of squares.

More formally, if $P(x)$ is a polynomial with real coefficients such that $P(x) \geq 0 \forall x \in \mathbb{R}$, show that there exist $Q_1,Q_2,\cdots, Q_k$ polynomials with real coefficients such that $P(x) \equiv Q_1^2(x) + Q_2^2(x) + \cdots + Q_k^2(x)$.

KBB2 Problem 7

Prove that for any $n > 1$, the polynomial

$P(x) = 2008x^n + 7x + 56$

cannot be factored into two non-trivial integer polynomials.

(A polynomial is non-trivial if its highest degree is greater than one)