20 NOTES
converging all sufficiently small z. For example, the square root func-
tion y =
√for
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.
3DISCRETE
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.
4O(
)-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.
5KOBLITZ’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.
6CHOICELESS
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.
7We
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”.
8TROPICAL
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