20 NOTES converging for all sufficiently small z. For example, the square root func- tion y = √ x is analytic at the point x = 1 since by Newton’s binomial formula we have √ 1 + z = 1 + z 2 − z2 4 · 2! + 3 · z3 8 · 3! − 3 · 5 · z4 16 · 4! + 3 · 5 · 7 · z5 32 · 5! + · · · for all z such that |z| 1. But a power series expansion for y = √ x at x = 0 does not exist: the function y = √ x is not analytic at x = 0. 3 DISCRETE VS. CONTINUOUS: the two other great divides in mathe- matics are between “finite” and “infinite” and between “geometric” and “formula-based” we shall discuss them later in the book. It is quite com- mon to associate the “geometric” or visual, and “formula-based” or verbal modes of thinking with the activities of the two hemispheres of the brain. For lack of space, I cannot go into detail in any case, I am more interested in the mechanisms of the synthesis of the two modes than reasons for their separation. 4 O( )-NOTATION. We give a few words about O( )-notation for orders of magnitude of functions of natural argument n: we say that f(n) = O(g(n)) if there is a constant C such that f(n) Cg(n) for all sufficiently large n. Hence f(n) is O(nd) if f(n) Cnd. 5 KOBLITZ’S THESIS. Like all general proclamations about mathemat- ics, Koblitz’s thesis has its natural limits of applicability. As usual, we have all possible complications caused by the non-constructive nature of many mathematical proofs: sometimes it is possible to prove that a certain al- gorithm has polynomial complexity O(nd), without having any way to find the actual degree d one example can be found in [330]. But we do not venture into this exciting, but dangerous, territory. 6 CHOICELESS ALGORITHMS. A few words of warning are due. Any algo- rithm on a clearly described finite set of inputs can be made into a choice- less algorithm by running it on all possible reorderings of the input struc- tures. Therefore the concept of choiceless computing is meaningful only if we assume resource limitations and focus on choiceless polynomial time algorithms. 7 We give an interesting comment from Chris Hobbs on the formula x1,2 = −b ± √ b2 − 4ac 2a for the roots of the quadratic equation: I know that this formula is always written with the plus/minus but, as you’ve argued in the text, it’s not only unnecessary, it’s also wrong. It has worried me since I first met it as a child that, accord- ing to that formula, there are four roots to a quadratic equation: the square root function delivers two and the plus/minus turns them into four (two positive, ++ and −−, and two negative, −+ and +−). Just a quibble but it’s a shame that we don’t have a no- tation for “the negative square root of x” and “the positive square root of x”. 8 TROPICAL MATHEMATICS. The works [396, 408] use min, not max, as a basic operation ⊕, but this makes no difference since in both cases the re- sults are similar. Traditionally, max is used in works originating in control theory and min in papers motivated by applications to algebraic geometry.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2010 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.