SIMO Retiree Blog

(Guest author Andrew here!) A good exercise for Olympiad students is to prove the following: A real polynomial $f(x)\in \R[x]$ which is everywhere non-negative ( psd , short for positive semi-definite) must be a sum of squares ( sos ).  This is in some sense an algebraic witness to the analytic property of being non-negative, and is an example of what is known as a Positivstellensatz . One might reasonably ask whether this extends to the case of multiple variables, and it turns out the answer is no .  Consider the two variable polynomial $g(x,y)=x^4y^2+x^2y^4-3x^2y^2+1$ (the Motzkin polynomial ). Non-negativity follows from the AM-GM inequality. But how can we show that it isn't a sum of squares? We now introduce an object known as the Newton polytope. Given a polynomial $f$,  To every monomial with non-zero coefficient, assign a point whose $i^{th}$ coordinate is the degree of the $i^{th}$ variable in that monomial, e.g. assign to $x_1^n$ the point $(n, 0)$. The Newton p...

(This is David.) I'm back with a short post about a beautiful proof for a beautiful problem I saw recently. Three dimensions? Let me explain the title. I think it was during a decent IMO where Grant Sanderson (of 3blue1brown fame) gave a talk about problems that are super easy once we move to a higher dimension. If you weren't there at the talk, he also made it into a youtube video - I highly recommend watching it if you haven't already! Here at the SIMO X-Men blog, we aren't unfamilliar with this idea - one of the most popular blogposts to date is Glen's Spacetime, Special Relativity, and a Lot of Circles where we saw that interpreting circles as points in 3-dimensional space was a really powerful tool for lots of geometry problems involving tangent circles. And the nice thing is, this trick doesn't stop at puzzles and Olympiad problems - it also shows up in real research. Arguably, the recent breakthrough for the sofa problem used this idea, and I've...

(Andrew here.)  In research, it often happens that people rediscover results lost to the sands of time, which always makes me wonder what gemstones have been lost and are waiting to be rediscovered. It also means that a lot of surprising things can be learned from reading old papers.

(Jeck here.) Consider an arrangement of $n$ lines on the plane, which do not necessarily need to be in general position. There are many combinatorial problems one can explore with such configurations: If no three lines are concurrent, the number of regions into which these lines divide the plane is given by $1+\binom{n+1}{2}$. If not all lines are concurrent, there is always at least one intersection point that is shared by exactly two lines.