B Can multivariate non-negative polynomials always be written as a sum of squares?

[Danijel]

Does a proof by counterexample belong to direct or indirect type of proof?

 

[.Scott]

Direct
With an indirect proof, you show that there can be no counter examples.

 

[Danijel]

That is what I was thinking. So basically, if we say, for example, show that something doesn't hold universally, our task is to disprove an universal statement, that is to prove the negation of the statement by giving an example. However, this still has some connection to the original statement which says that something holds universally, so I was also thinking that in some way this was indirect. However, if our theorem is (that is, if we look at the negation as the starting statement) to disprove something universal, then we are giving a direct proof by posing an example. It's a little bit confusing. I am still inclining towards the direct whatsoever.

 

[mfb]

Keep in mind that these categories don't have a deeper meaning and the classification is somewhat arbitrary.
You can always say a proof of X (a direct proof) is showing "(not X) is wrong" and therefore proving X (which would make that an indirect proof) or vice versa.

 

[StoneTemplePython]

Something less abstract may help.

Suppose you're a great mathematician at the end of the 1800s and you show any polynomial with a single variable and real nonnegative coefficients can be written as a sum of squares. You conjecture, what about said polynomial except 2 variables or 3 or ... i.e. is it true that multivariate non-negative polynomial can always be written as a sum of squares?

Hilbert answered this as definitively "no" in 1888 using a lot of powerful analytical machinery but bit he didn't give an example.

About 80 years later Motzkin gave the first (very simple) example of a 2 variable non-negative polynomial that can't be written as a sum of squares. (The proof merely needs $GM \leq AM$.) People would generally say he directly showed the conjecture to be false by a single example, whereas Hilbert's approach was indirect.

Put differently:
Hilbert showed that these 'rule breaker' polynomials must exist. (Indirect.)

Motzkin directly proved they do exist with a simple example. (Direct.)

 

[Danijel]

Something less abstract may help.

Suppose you're a great mathematician at the end of the 1800s and you show any polynomial with a single variable and real nonnegative coefficients can be written as a sum of squares. You conjecture, what about said polynomial except 2 variables or 3 or ... i.e. is it true that multivariate non-negative polynomial can always be written as a sum of squares?

Hilbert answered this as definitively "no" in 1888 using a lot of powerful analytical machinery but bit he didn't give an example.

About 80 years later Motzkin gave the first (very simple) example of a 2 variable non-negative polynomial that can't be written as a sum of squares. (The proof merely needs $GM \leq AM$.) People would generally say he directly showed the conjecture to be false by a single example, whereas Hilbert's approach was indirect.

Put differently:
Hilbert showed that these 'rule breaker' polynomials must exist. (Indirect.)

Motzkin directly proved they do exist with a simple example. (Direct.)

Wow, an excellent answer! Thank you...