converging 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 +
4 · 2!
8 · 3!
3 · 5 ·
16 · 4!
3 · 5 · 7 ·
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.
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
)-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
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 . But we do not
venture into this exciting, but dangerous, territory.
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
give an interesting comment from Chris Hobbs on the formula
b2 − 4ac
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”.
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.