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.