[Number Theory] Using Brahmagupta Identity and FTA to show Non-Negative Univariate Polynomial is SOS

Let's use the Fundamental Theorem Algebra (FTA) and the Brahmagupta Fibonacci identity to prove that every non-negative polynnomial f(x)R[x]f(x) \in \mathbb{R}\left[ x \right] may be written as a sum of squares of polynomials.

Let pR[x] xRp \in \mathbb{R}[x] ~ \forall x \in \mathbb{R} and p(x)0p(x) \geq 0. By the Fundamental Theorem of Algebra, a degree nn polynomial pp has exactly nn complex roots, and our polynomial pp is of the form constant times a product of positive quadratics. The graph of the polynomial lies entirely above the x-axis, or touches it. So in the first case, the roots of p are all complex, whereas in the latter, pp has real roots with even multiplicity. Hence our polynomial is of the form

p=a f12f22fn2g1gm,p = a~f_1^2f_2^2 \cdots f_n^2g_1 \cdots g_m,

where aa is a real coefficient, the fif_i's have degree 1, and gjg_j's have degree 2 and no real roots. We also note that by the complex conjugate root theorem, the roots of pp come in complex conjugate pairs. Also, p(x)p(x) does not intersect the x-axis, so the degree of pp must be even.

A monic positive quadratic gjg_j, with no real roots, can be written as (x+a)2+b2(x+a)^2+b^2 by completing the square. From here, an expression of pp as a sum of squares follows from the Brahmagupta-Fibonacci identity; the product of gjg_j's, hence a product of the sums of squares, can be written as the sum of squares. For example, the product of two quadratics

((x+a)2+b2)((x+c)2+d2)((x+a)^2+b^2)((x+c)^2+d^2)

=((x+a)(x+c)+b2d2)+((x+a)2d2b2(x+c)).= ((x+a)(x+c) + b^2d^2) + ((x+a)^2d^2-b^2(x+c)).

If the degree of pp is 2, then

p=(x(a+ib))(x(aib))p = (x-(a+ib))(x-(a-ib))

=x22ax+a2+b2=(xa)2+b2= x^2-2ax+a^2+b^2 = (x-a)^2+b^2

where a,bR[x],a,b \in R[x], hence the sum of two squares.

If degree of pp is greater than or equal to 4, then we can write pp as the product of quadratics. By applying the Brahmagupta-Fibonacci identity as needed, the product of many sums of squares can be written as a sum of many squares.

Since the degree of pp is not odd, we have shown that a non-negative univariate polynomial is a sum of squares of polynomials. \blacksquare

Note that in the case that p=ap=a, where aRa\in \mathbb{R}, pp is itself a square.

Note by Tasha Kim
1 year, 4 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Some notes:

  1. In this proof, you don't really use the structure of the "real number field"; hence, you can actually generalise your proof to any polynomial ring.

  2. You can just consider a monic polynomial instead of a general one if you are working over a field.

  3. Algebraic closure is a very complicated manner, especially when you generalise to arbitrary rings; because of this, I tend to steer as far away as possible from invoking the FToA.

  4. I think in your last equation you want a,bR a,b \in \mathbb{R} , not R[x] R[x] .

If you are considering the algebraic closure of the "complex number field", then you know this result to be intuitively true, due to the fact that polynomial roots come in (complex) conjugate pairs. So if the degree of the polynomial is even, then you group each factor in twos and obtain a quadratic polynomial for which anyone can complete the square. However, I wonder if this will also work for arbitrary polynomial rings; the issue is that you won't be able to use FToA, and you would need to rely on ring theoretical methods.

Nice work though!

A Former Brilliant Member - 1 year, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...