EDITORIAL POLICY MATHEMATICS MAGAZINE (ISSN 0025-570X) is pub- lished by the Mathematical Association of America at 1529 Eighteenth Street, N.W., Washington, D.C. 20036 Mathematics Magazine aims to provide and Hanover, PA, bimonthly except July/August. lively and appealing mathematical exposi- The annual subscription price for MATHEMATICS tion. The Magazine is not a research jour- MAGAZINE to an individual member of the Associ- ation is $131. Student and unemployed members re- nal, so the terse style appropriate for such a ceive a 66% dues discount; emeritus members receive journal (lemma-theorem-proof-corollary) is a 50% discount; and new members receive a 20% dues not appropriate for the Magazine. Articles discount for the first two years of membership.) should include examples, applications, his- Subscription correspondence and notice of change torical background, and illustrations, where of address should be sent to the Membership/ appropriate. They should be attractive and Subscriptions Department, Mathematical Association accessible to undergraduates and would, of America, 1529 Eighteenth Street, N.W., Washington, ideally, be helpful in supplementing un- D.C. 20036. Microfilmed issues may be obtained from University Microfilms International, Serials Bid Coordi- dergraduate courses or in stimulating stu- nator, 300 North Zeeb Road, Ann Arbor, MI 48106. dent investigations. Manuscripts on history are especially welcome, as are those show- Advertising correspondence should be addressed to ing relationships among various branches of MAA Advertising mathematics and between mathematics and 1529 Eighteenth St. NW other disciplines. Washington DC 20036 A more detailed statement of author Phone: (866) 821-1221 guidelines appears in this Magazine, Vol. Fax: (202) 387-1208 E-mail: CONTENTS ARTICLES 243 Structured Population Dynamics: An Introduction to Integral Modeling, by Joseph Briggs, Kathryn Dabbs, Michael Holm, Joan Lubben, Richard Rebarber, Brigitte Tenhumberg, and Daniel Riser-Espinoza 258 What Do We Know at 7 PM on Election Night? by Andrew Gelman and Nate Silver At 267 Putzer’s Algorithm for e via the Laplace Transform, by William A. Adkins and Mark G. Davidson NOTES 276 The Geometry of the Snail Ball, by Stan Wagon 279 Another Morsel of Honsberger, by Mowaffaq Hajja 283 Cantor’s Other Proofs that R Is Uncountable, by John Franks 289 Nothing Lucky about 13, by B. Sury 294 Proof Without Words: The Alternating Harmonic Series Sums to ln 2, by Matt Hudelson 295 Period Three Begins, by Cheng Zhang 297 Stacking Blocks and Counting Permutations, by Lara K. Pudwell 302 Counting Ordered Pairs, by David M. Bradley PROBLEMS 303 Proposals 1851–1855 304 Quickies 1003–1004 304 Solutions 1826–1830 310 Answers 1003–1004 REVIEWS 311 P vs. NP, God masters Rubik’s Cube, and sports does math NEWS AND LETTERS 313 39th USA Mathematical Olympiad and 1st USA Junior Mathematical Olympiad 320 51st International Mathematical Olympiad 324 2010 Carl B. Allendoerfer Award 327 Pronouncing “Oresme” The Mathematical Association of America 1529 Eighteenth Street, NW ® Washington, DC 20036 Vol. 83, No. 4, October 2010 ® MATHEMATICS MAGAZINE EDITOR Walter Stromquist ASSOCIATE EDITORS Bernardo M. A´ brego California State University, Northridge Paul J. Campbell Beloit College Annalisa Crannell Franklin & Marshall College Deanna B. Haunsperger Carleton College Warren P. Johnson Connecticut College Victor J. Katz University of District of Columbia, retired Keith M. Kendig Cleveland State University Roger B. Nelsen Lewis & Clark College Kenneth A. Ross University of Oregon, retired David R. Scott University of Puget Sound Paul K. Stockmeyer College of William & Mary, retired Harry Waldman MAA, Washington, DC LETTER FROM THE EDITOR We begin with two articles about applications—to polls and to populations. Andrew Gelman and Nate Silver tell us how to predict the result of a presidential election during the first hours of the vote count. Their model uses the final polling results for each state, and takes into account the correlations among the separate polling “errors” (which might include last-minute swings). Thus, learning that one state has moved in a particular direction can increase the probability that other states have moved in the same direction. From the earliest reported results, they construct ever-tighter probability distributions for the final electoral vote. Is there a reader who can apply the same methods to the 2010 congressional elections? Your goal would be to say which party controls each house by, say, 9 or 10 PM on November 2. Post your results ahead of the networks and win fame and fortune! Population dynamics is the subject of an article by a team from Richard Rebarber’s REU group at the University of Nebraska. They describe population models for plant and animal species. Many of us have seen transition matrices used for this purpose, when populations can be partitioned naturally into age or size classes. But what if the distribution is naturally continuous? This team shows how integral models can be used in these cases, and how they compare to their discrete analogs. The third article, by William Adkins and Mark Davidson, gives us a computational method that might be useful in many applications. How many of us, seeing the linear system y′ = Ay, have wanted to write the answer y = exp(At) and be done with it? Alas, computing exp(At) requires serious attention! Nicole Oresme reappears on page 327. His work in the 14th century helped us to understand balls rolling down inclined planes, but he might have been alarmed by the device that Stan Wagon describes in the Notes section. Elsewhere in the Notes section you can find the name of an effective middle-school teacher, quotations from Euclid and Gauss, and the first proof that the real numbers are uncountable (not diagonalization!). If you are looking for the answer to the puzzle in our last issue about a Tower-of-Hanoi graph, start on page 257. The Olympiads This issue contains the problems and solutions for both the US- AMO and the IMO. We also have the problems and solutions for the USAJMO—the USA Junior Mathematical Olympiad, for students in 10th grade and below—which was given for the first time this year. The USAMO, USAJMO, and US participation in the IMO are programs of the MAA, carried out by the staff of the MAA’s Lincoln, Nebraska office and volunteers led by the MAA’s Committee on the American Math- ematical Competitions. These features have appeared in the MAGAZINE every year, but this year we are bringing them to you more quickly. Thanks to the authors, who met tight deadlines. The Allendoerfer Awards We are also pleased to honor the winners of the 2010 Carl B. Allendoerfer Awards, for articles published in this MAGAZINE during 2009. The winners are Ezra Brown, Keith Mellinger, David Speyer, and Bernd Sturmfels. Walter Stromquist, Editor 242 ARTICLES Structured Population Dynamics: An Introduction to Integral Modeling JOSEPH BRIGGS North Carolina State University Raleigh, NC KATHRYN DABBS University of Tennessee Knoxville, TN MICHAEL HOLM JOAN LUBBEN RICHARD REBARBER BRIGITTE TENHUMBERG University of Nebraska Lincoln, NE DANIEL R ISER-ESP INOZA Swarthmore College Swarthmore, PA Will an exotic species thrive in a new territory? What are the best management options to eradicate a population (pest species) or to facilitate population recovery (endangered species)? Population modeling helps answer these questions by integrating mathemat- ics and biology. Often, a single species cannot be properly modeled as one population, but instead is best treated as a structured population, where the individuals in the population are partitioned into classes, or stages. As an example of a stage structured population, it is natural to partition an insect population into egg, larva, pupa, and adult stages. The choice of the stages and the breakdown of the population into stages depend heavily on the type of population, and are informed by biological intuition. For instance, fecundity (number of offspring per capita) in animals often varies with age, while in plants, fecundity typically depends on size. This implies that for mammals, the stages might be best determined by age, so that age is a good stage variable for mammals, while size might be a good stage variable for plants. Furthermore, for many animals there are natural classes of ages—the egg/larva/pupa/adult partition of an insect population— while for many plants, the stages can be better described as a continuous function of stem diameter, or another indicator of size. When the stages are discrete, a matrix model is used, and when the stages are continuous, an integral model is used. Both integral and matrix models are commonly used in population viability analysis and are both important tools in guiding population management [4, 19]. These models are used to predict long-term and transient behavior of a population, and they inform wildlife managers about which populations are in danger of going extinct or of growing unacceptably large. Another basic modeling choice is whether time is modeled as a discrete variable or a continuous variable. Field data is often collected at regular time intervals, for Math. Mag. 83 (2010) 243–257. doi:10.4169/002557010X521778. ⃝c Mathematical Association of America 243 244 MATHEMATICS MAGAZINE instance on a yearly or seasonal basis, so it is often easier and more practical to model time discretely. There is some controversy about the relative merits of discrete-time versus continuous-time modeling [7]. Nonetheless, in most of the ecological literature on single-species structured populations, time is modeled as a discrete variable, so in this article we also model time as a discrete variable. For a population that is partitioned into finitely many stages and modeled at discrete times, the evolution of the population can often be described using a Population Pro- jection Matrix (PPM). The entries in a PPM are determined by the life history param- eters of the population, and the properties of the matrix—for instance, its spectrum— determine the behavior of the solutions of the model. In the next section we describe PPMs in detail. When stages are described by a continuous variable, one can either maintain the continuous stage structure, or partition the continuous range of stages into a finite number of stages. The latter is called a discretization of the population. To do it effec- tively one must ensure that each stage consists of individuals with comparable growth, survival, and fecundity, because the accuracy of the approximation depends on the sim- ilarity of individuals within each stage class. In general, a large number of life history stages increases model accuracy, but at the cost of increasing parameter uncertainty, since each nonzero matrix entry needs to be estimated from data, and the more stages there are, the less data is available per stage. This tradeoff can often be avoided by maintaining the continuous structure, and using an Integral Projection Model (IPM) that uses continuous life history functions that are functions of a continuous range of stages. We discuss IPMs in detail below. In this article we illuminate the differences and similarities between matrix popu- lation models and integral population models for single-species stage structured pop- ulations. We illustrate the use of integral models with an application to Platte thistle, following Rose et al. [22], showing how the model is determined by basic life history functions. PPMs are ubiquitous in ecology, but for many purposes an IPM might be easier and/or more accurate to use. In TABLE 1 we summarize the similarities between PPMs and IPMs. In order to compare the predictions for PPMs and IPMs, enough data must be available to find the parameters in both models. This is done for models for the plant monkshood in Easterling et al. [9]. We should mention that if time is treated as a continuous variable, the analogue of a PPM model is an ordinary differential equation, and the analogue of a IPM is an integro-differential equation. Matrix models Matrix models were introduced in the mid 1940s, but did not become the dominant paradigm in ecological population modeling until the 1970s. The modern theory is described in great detail in Caswell [4], which also contains a good short history of population projection matrices in its Section 2.6. We summarize some of this history here. The basic theory of describing, predicting, and analyzing population growth by analyzing life history parameters such as survival and fecundity can be traced back to Cannan [3] in 1895. Matrix models in particular were developed independently by Bernardelli [2], Lewis [16], and Leslie [15]. The latter is most relevant to the mod- ern theory. P. H. Leslie was a physiologist and self-taught mathematician, who, while working at the Bureau of Animal Population at Oxford between 1935 and 1968, syn- thesized mortality and fertility data into single models using matrices. We briefly de- scribe his basic models, which are still used for population description, analysis, and prediction. Although he was highly regarded and well connected in the ecology community, Leslie’s work in matrix modeling initially received little attention. One of the few VOL. 83, NO. 4, OCTOBER 2010 245 TABLE 1: Comparison of matrix and integral models Population Projection Matrix Integral Projection Model number of ∫ y1 number of continuous vector entry n(i, t) individuals in stage n(y, t) dy individuals expected function class i at time t y0 between sizes y0 and y1 stage distribution continuous stage distribution T m 1 state vector n(t) = [n(1, t), · · · , n(m, t)] ∈ R of population state n(·, t) ∈ L (ms, Ms) of population at time t function at time t probability of an probability an probability ∫ y 1 individual individual of size x probability pi j density p(y, x) dy transitioning function y0 will grow and survive from class j to i to a size between y0 and y1 number of ∫ y1 number of newborns scalar fi j newborns size i function f (y, x) dy between sizes y0 and y1 from parents size j y0 from parents of size x the i j th entry matrix entry ki j = pi j + fi j of the function k(y, x) = p(y, x) + f (y, x) kernel transition matrix ∫ [ ] Ms integral matrix A = ki j (Av)(y) = k(y, x)v(x) dx operator m s discrete matrix indices continuous variables stage j ∼ t and i ∼ t + 1 associated with stage x ∼ t and y ∼ t + 1 associated with variables time t and time t + 1 variables time t and time t + 1 ∑m ∫ Ms difference integral n( j, t + 1) = k ji n(i, t) n(y, t + 1) = k(y, x)n(x, t) dx equation i=1 equation ms vector matrix operator n(t + 1) = An(t) n(t + 1) = An(t) integration form multiplication form 246 MATHEMATICS MAGAZINE contemporaries who did use the matrix model was Leonard Lefkovitch. He also imple- mented a matrix model [14], but with an innovation: The populations were partitioned into classes based on developmental stage rather than age. This made the method more applicable to plant ecologists, who began defining stage classes by size rather than age—a change that usually resulted in better predictions. As Caswell points out [4], it took some 25 years for the ecology community to adopt matrix projection models after Leslie’s influential work. There were two major reasons for this delay. The ecology community at that time thought of matrix algebra as an advanced and esoteric mathematical subject. More importantly, there was a more accessible method, also contributed by Leslie, called life table analysis [4, Section 2.3]. Before the widespread use of computers, there was no information that a matrix model could provide that a life table could not. This would change as more sophisti- cated matrix algebra and computation methods emerged to convince ecologists of the worth of matrix models. For instance, using elementary linear algebra, one can predict asymptotic population growth rates and stable stage distributions from the spectral properties of the matrix. Also, the use of eigenvectors facilitated the development of sensitivity and elasticity analyses, giving an easy way to determine how small changes in life history parameters effect the asymptotic population growth rate. This is an es- pecially important question for ecological models, which are typically very uncertain. Sensitivity and elasticity analyses are sometimes used to make recommendations about which stage class conservation managers should focus on in order to increase the pop- ulation growth rate of an endangered species. Transition matrices To set up a matrix model we start with a population partitioned into m stage classes. Let t ∈ N = {0, 1, 2, . . . } be time, measured discretely, and let n(t) be the population column vector T n(t) = [n(1, t), n(2, t), . . . , n(m, t)] , where each entry n(i, t) is the number of individuals belonging to class i at time t. A discrete-time matrix model takes the form n(t + 1) = An(t), (1) where A = (ki j ) is the m × m PPM containing the life-history parameters. It is also called a transition matrix, since it dictates the demographic changes occurring over one time step. We can write (1) as m ∑ n(i, t + 1) = ki jn( j, t), i = 1, . . . n. (2) j=1 The entry ki j determines how the number of stage j individuals at time t affects the number of stage i individuals at time t + 1. This is the form we will generalize when we discuss integral equations. In their simplest form, the entries of A are survivorship probabilities and fecundi- ties. What we call a Leslie matrix has the form ⎛ ⎞ f1 f2 · · · fm−1 fm ⎜p1 0 · · · 0 0 ⎟ ⎜ ⎟ A = ⎜ 0 p2 · · · 0 0 ⎟ , ⎜ ⎟ . . ⎝ . . ⎠ . 0 . 0 0 0 · · · · · · pm−1 0 VOL. 83, NO. 4, OCTOBER 2010 247 where pi is the probability that an individual survives from age class i to age class i + 1, and fi is the fecundity, which is the per capita average number of offspring reaching stage 1 born from mothers of stage class i . The transition matrix has this particular structure when age is the stage class variable and individuals either move into the next class or die. In general, entries for the life-history parameters may appear in any entry of the m x m matrix A. t For any matrix A and t ∈ N, let A denote the tth power of A for any natural number t . It follows from (1) that t n(t) = A n(0). (3) The long-term behavior of n(t) is determined by the eigenvalues and eigenvectors of A. We say that A is nonnegative if all of its entries are nonnegative, and that A is primitive t if for some t ∈ N, all entries of A are positive. This second condition is equivalent to every stage class having a descendent in every other stage class at some time step in the future. PPMs are generally nonnegative and primitive, thus the following theorem is extremely useful [23, Section 1.1]: PERRON-FROBENIUS THEOREM. Let A be a square, nonnegative, primitive ma- trix. Then A has an eigenvalue, λ, known as the dominant eigenvalue, that satisfies: 1. λ is real and λ > 0, 2. λ has right and left eigenvectors whose components are strictly positive, ˜ ˜ ˜ 3. λ > |λ| for any eigenvalue λ such that λ ̸= λ, 4. λ has algebraic and geometric multiplicity 1. This theorem is important in the analysis of population models because the domi- nant eigenvalue is the asymptotic growth rate of the modeled population, and its asso- ciated eigenvector is the asymptotic population structure. To see this, assume that A is primitive. Let n = [n1, n2, . . . , nm], and ‖n‖ denote the ℓ1 norm: ‖n‖ = |n1| + |n2| + . . . |nm|. (4) Denote the unit eigenvector associated with λ by v , so ‖n(t + 1)‖ n(t) lim = λ and lim = v. (5) t→∞ ‖n(t)‖ t→∞ ‖n(t)‖ Thus as time goes on, the growth rate approaches λ and the stage structure approaches v. In particular, the dynamics of a long-established population is described by λ and v. Problems with stage discretization To use a population projection matrix model, the population needs to be decomposed into a finite number of discrete stage classes that are not necessarily reflective of the true population structure. As mentioned pre- viously, if stage classes are defined in such a way that there is at least one class in which the life history parameters vary considerably, then it might not be possible to accurately describe individuals in that stage class, which might result in erroneous predictions. Easterling [8] and Easterling et al. [9] give an example of such a “bad” partition of the population. Fortunately it is often possible to decompose a particular population in a biolog- ically sensible fashion. Vandermeer [24] and Moloney [18] have crafted algorithms to minimize errors associated with choosing class boundaries. Such algorithms help to derive more reasonable matrices, but for many populations they cannot altogether eliminate the sampling and distribution errors associated with discretization. For in- stance, for many plants size is the natural stage variable, and no decomposition of 248 MATHEMATICS MAGAZINE size into discrete stage classes will adequately capture the life history variations. Fur- thermore, sensitivity and elasticity analyses have both been shown to be affected by changes in stage class division, Easterling, et al. [9]. Regardless of how well the population is decomposed into stages, there is also the problem that in a matrix model individuals of a given stage class are treated as though they are identical through every time step. That is, two individuals starting in the same class will always have the same probability of transitioning into a different stage class at every time step in the future, which is not necessarily the case for real populations. For many populations, these difficulties can be overcome by analyzing a continuum of stages, which is discussed in the next section. Integral projection models An alternate approach to discretizing continuous variables such as size is to use In- tegral Projection Models. These models retain much of the analytical machinery that makes the matrix model appealing, while allowing for a continuous range of stages. Easterling [8] and Easterling et al. [9] show how to construct such an integral projec- tion model, using continuous stage classes and discrete time, and they provide sensi- tivity and elasticity formulas analogous to those for matrix models. In Ellner and Rees [10] an IPM analogue of the Perron-Frobenius Theorem is given. In particular, there are readily checked conditions under which such a model has an asymptotic growth rate that is the dominant eigenvalue of an operator whose associated eigenvector is the asymptotic stable population distribution. Just as ecologists were slow to adopt matrix models, they have, so far, not used inte- gral models widely. Stage structured IPMs of the type considered in this paper have ap- peared in the scientific literature since around ten years ago [5, 6, 8, 9, 10, 11, 21, 22]. There is a large literature on integral models for spatial spread of a population [12, 13]. The structure of the integral operators describing spatial spread can be very different from those for IPMs. For instance, the integral operators discussed in this paper are compact, while the operators describing spatial spread might not be compact. Com- pact operators have many properties that are similar to those of matrices [1, Chapter 17], and these properties make the spectral analysis, and hence the asymptotic analysis, more analogous to matrix models. Continuous stage structure and integral operators Let n(x, t) be the population distribution as a function of the stage x at time t. For example, if ms is the minimum size, and Ms is the maximum size, as determined by field measurements, then x ∈ [ms, Ms] would be the size of an individual. The analogue of the matrix entries ki, j for i, j ∈ {0, 1, . . . m} is a projection ker- nel k(y, x) for y, x ∈ [ms, Ms], and the role of the matrix multiplication operation is analogous to an integral operator. The kernel is time-independent, which is analogous to the time-independent matrix entries. The time unit t = 1 represents a time interval in which data is naturally measured; in the example in this paper the unit of time is a year. The analogue of (2) is ∫ Ms n(y, t + 1) = k(y, x)n(x, t) dx, y ∈ [ms, Ms]. (6) ms In particular, the kernel determines how the distribution of stage x individuals at time t contributes to the distribution of stage y individuals at time t + 1, in much the same way that in (2) the (i, j)th entry of a projection matrix determines how an individual in stage j at time t contributes to stage i at time t + 1.