November 2012 Contents
November’s American Mathematical Monthly opens with two articles on the Fundamental Theorem of Algebra. The first offers a real-algebraic proof via Sturm Chains. The second offers a proof via the four basic operations. Our articles round out with a look at the relationship between magic squares and sudoku, a game which allows one to bound chromatic numbers, and sums of zeta-values and their connection to the spiral of Theodorus. Our notes consider riddles associated with Rolle’s Theorem, strategies in a war-like card game, and Newton identities for Weierstrass products. Stan Wagon reviews William J. Cook’s In Pursuit of the Traveling Salesman. Don’t forget our world-famous Problem Section!
Not a member? Join the MAA today!
The Fundamental Theorem of Algebra Made Effective: An Elementary Real-algebraic Proof via Sturm ChainsMichael Eisermann
Sturm’s theorem (1829/35) provides an elegant algorithm to count and locate the real roots of any real polynomial. In his residue calculus (1831/37), Cauchy extended Sturm’s method to count and locate the complex roots of any complex polynomial. For holomorphic functions Cauchy’s index is based on contour integration, but in the special case of polynomials it can effectively be calculated via Sturm chains using Euclidean division as in the real case. In this way we provide an algebraic proof of Cauchy’s theorem for polynomials over any real closed field. As our main tool, we formalize Gauss’ geometric notion of winding number (1799) in the real-algebraic setting, from which we derive a real-algebraic proof of the Fundamental Theorem of Algebra. The proof is elementary inasmuch as it uses only the intermediate value theorem and arithmetic of real polynomials. It can thus be formulated in the first-order language of real closed fields. Moreover, the proof is constructive and immediately translates to an algebraic root-finding algorithm.
The Fundamental Theorem of Algebra: From the Four Basic Operations
Oswaldo Rio Branco de Oliveira
This paper presents an elementary and direct proof of the Fundamental Theorem of Algebra, via Weierstrass’ Theorem on Minima, that avoids the following: all root extractions, angles, non-algebraic functions, differentiation, integration, series, and arguments by induction.
Magic Squares and Sudoku
We introduce a family of magic squares, called linear magic squares, and show that any parallel linear sudoku solution of sufficiently large order can be relabeled so that all of its subsquares are linear magic. As a consequence, we show that if n has prime factorization and q = min , then there is a family of mutually orthogonal magic sudoku solutions of order n2 whenever q > 3; such an orthogonal family is complete if n is a prime power.
Playing a Game to Bound the Chromatic NumberPanagiota N. Panagopoulou and Paul G. Spirakis
We provide here a new method for proving several known bounds on the chromatic number of a graph in a unified manner. To do so, we view vertices of a graph as players in a strategic game. Each player has the same set of actions, which is a set of colors. In a certain profile, where each vertex has chosen a color, a vertex gets a payoff equal to zero if its color is the same as one of its neighbors. Otherwise, the vertex gets as a payoff the number of vertices that chose the same color as its own color. In a pure Nash equilibrium of such a game, no vertex can improve its payoff by deviating unilaterally. We prove that, if we start with the trivial proper coloring, where each vertex chooses its unique name as a color, then any selfish improvement sequence (i.e., a sequence of steps, where at each step a single vertex changes its color in order to improve its payoff) reaches a pure Nash equilibrium in polynomial time, and that the number of colors used by any pure Nash equilibrium satisfies four known upper bounds on the chromatic number. This implies that there is a polynomial time algorithm for computing a proper coloring of any given graph G where the number of colors used satisfies all these bounds.
The Spiral of Theodorus and Sums of Zeta-values at the Half-integersDavid Brink
The total angular distance traversed by the spiral of Theodorus is governed by the Schneckenkonstante K introduced by Hlawka. The only published estimate of K is the bound . We express K as a sum of Riemann zeta-values at the half-integers and compute it to 100 decimal places. We find similar formulas involving the Hurwitz zeta-function for the analytic Theodorus spiral and the Theodorus constant introduced by Davis.
A Few Riddles Behind Rolle’s TheoremB. Shapiro and M. Shapiro
First year undergraduates usually learn about classical Rolle’s theorem which says that between two consecutive zeros of a smooth univariate function f , one can always find at least one zero of its derivative. In this paper, we study a generalization of Rolle’s theorem dealing with zeros of higher derivatives of smooth univariate functions enjoying a natural additional property. Namely, we call a smooth function whose nth derivative does not vanish on some interval a polynomial-like function of degree n on I. We conjecture that for polynomial-like functions of degree n with n real distinct roots, there exists a non-trivial system of inequalities completely describing the set of possible locations of their zeros together with their derivatives of order up to . We describe the corresponding system of inequalities in the simplest non-trivial case n = 3.
Note on a War-like Card GameBoris Alexeev and Jacob Tsimerman
We prove that the probability that one of the players has a winning strategy in the War-like card game “Peer Pressure” approaches zero as the number of cards dealt approaches infinity, even if the cards are dealt in a slightly-biased manner.
Newton Identities for Weierstrass ProductsFlorian Breuer
We prove a generalization of the Newton Identities for entire functions, which give a relation between the Taylor coefficients and sums of powers of reciprocals of the zeros of an entire function. We apply these identities to a number of special functions, yielding some interesting recursion relations.