You are here

American Mathematical Monthly Contents—November 2012

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! —Scott Chapman

Vol. 119, No. 9, pp.715-811.

Journal subscribers and MAA members: Please login into the member portal by clicking on 'Login' in the upper right corner.

ARTICLES

The Fundamental Theorem of Algebra Made Effective: An Elementary Real-algebraic Proof via Sturm Chains

Michael 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.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.119.09.715

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.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.119.09.753

Magic Squares and Sudoku

John Lorch

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 $$p_{1}^{k_{1}}\cdots p_{t}^{k_{t}}$$ and $$q=\min\{p_{j}^{k_{j}}|1\leq j\leq t\}$$ , then there is a family of $$q(q-1)$$ mutually orthogonal magic sudoku solutions of order $$n^{2}$$ whenever $$q>3$$; such an orthogonal family is complete if $$n$$ is a prime power.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.119.09.759

Playing a Game to Bound the Chromatic Number

Panagiota 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.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.119.09.771

The Spiral of Theodorus and Sums of Zeta-values at the Half-integers

David 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 $$K\leq 0.75$$. 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.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.119.09.779

NOTES

A Few Riddles Behind Rolle’s Theorem

B. 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 $$n$$th derivative does not vanish on some interval $$I\subseteq\mathbb{R}$$ 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 $$n-1$$. We describe the corresponding system of inequalities in the simplest non-trivial case $$n=3$$.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.119.09.787

Note on a War-like Card Game

Boris 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.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.119.09.793

Newton Identities for Weierstrass Products

Florian 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.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.119.09.796

PROBLEMS AND SOLUTIONS

Problems 11670-11676
Solutions 11523, 11528, 11529, 11532, 11544

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.119.09.800

REVIEWS

In Pursuit of the Traveling Salesman. By William J. Cook. Princeton University Press, Princeton, NJ, 2012 xiii + 228 pp., ISBN 978-0-691-15270-7, $27.95. Reviewed by Stan Wagon

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.119.09.808