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.
Previous Page Next Page