Abstract Recursion & Complexity Analysis
Abstract Recursion & Complexity Analysis
Yiannis N. Moschovakis
Department of Mathematics
University of California, Los Angeles
ynm@[Link]
October 2018
iv
This final prepublication draft of ARIC was compiled on November 30, 2018, 22:50
CONTENTS
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chapter 1. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1A. Standard notations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Partial functions, 9. Monotone and continuous functionals, 10. Trees, 12.
Problems, 14.
1B. Continuous, call-by-value recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
The where -notation for mutual recursion, 17. Recursion rules, 17. Problems, 19.
1C. Some basic algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
The merge-sort algorithm, 21. The Euclidean algorithm, 23. The binary (Stein)
algorithm, 24. Horner’s rule, 25. Problems, 25.
1D. Partial structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Φ-structures, 30. Substructures, 32. Diagrams, 32. Homomorphisms and em-
beddings, 33. Substructure generation, 33. Certificates, 34. Problems, 35.
1E. Partial equational logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Syntax, 36. Semantics, 38. Explicit definability, 39. Problems, 42.
v
vi CONTENTS
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
Symbol index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
General index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
INTRODUCTION
where cε (x, y) is the number of divisions (calls to the rem-oracle) required for
the computation of gcd(x, y) by the Euclidean and logarithms are to the base
2. Much more is known about cε (x, y), but this upper bound suggests one
plausible formulation of the Euclidean’s (worst-case) weak optimality:
Main Conjecture. For every algorithm α from rem and eq0 which computes
gcd(x, y) when x, y ≥ 1, there is a number r > 0, such that for infinitely many
pairs (x, y) with x > y ≥ 1,
cα (x, y) > r log x,
where cα (x, y) is the number of calls to the rem-oracle that α makes in the
computation of gcd(x, y).
This is a classical fact about the Euclidean algorithm, taking for example
the pairs (Fn+3 , Fn+2 ) of successive Fibonacci numbers, cf. Problems x1C.8,
x1C.9. The general case is open, probably not easy and certainly not precise
as it stands, without specifying what algorithms it is about and what it means
for an algorithm to call an oracle in the course of a computation.
Now, there are Turing machines which compute gcd(x, y) making no oracle
calls at all, simply because gcd(x, y) is Turing computable—so that’s not it.
In fact, there is no generally accepted, rigorous definition of what algorithms
are. This is not a problem when we study particular algorithms, which are
typically specified precisely in some form or other without any need to investi-
gate whether all relevant algorithms can be similarly specified. In Complexity
Theory—and especially when we want to establish lower bounds for some mea-
sure of computational complexity—the standard methodology is to ground
proofs on rigorously defined models of computation, such as Turing machines,
register or random access machines, decision trees, straight line programs,
etc., and sometimes also on specific representations of the input, e.g., unary
or binary notation for natural numbers, adjacency matrices for graphs, etc.
There is a problem with this practice, when we try to compare lower bound
results obtained for different models, typically attacked by establishing simu-
lations of one model by another, cf. van Emde Boas [1990]; and this problem
becomes acute when we want to prove absolute (or at least widely applicable)
lower bounds which are small, polynomial or even linear (in the length of the
Introduction 3
input) as in the Main Conjecture, generally less complex than the standard
simulations.
So there are two equally important aims of research in this area:
One is to derive lower bounds for mathematical problems; the other is to
develop a foundational framework in which one may be able to prove (or at
least argue convincingly) that these bounds are absolute, that they restrict all
relevant algorithms. The first of these naturally requires mathematical tools
from the area in which the problems arise; and the second inevitably involves
logic.
Recursion gets in the picture because there are both foundational arguments
and mathematical results which support the view that all elementary1 algo-
rithms can be faithfully expressed by recursive programs, so that lower bounds
established for them should be absolute, cf. Moschovakis [1984], [1989a],
[1998], [2001]. This connection has motivated much of the work reported
here, but it is not our topic.
Here I will take a different approach to the derivation and justification of
robust lower bounds, which is more widely applicable and does not tie us to
any specific foundational view of what algorithms are.
In Chapter 4, which is the heart of this book, we formulate three simple
axioms about algorithms in the style of abstract model theory. These are
bundled into the notion of a uniform process of an arbitrary (first order) struc-
ture: all concrete algorithms specified by computation models induce uniform
processes, as do their usual nondeterministic versions. Uniform processes can
“compute” functions that are not computable, they are not about that; but
they carry a rich complexity theory which, when applied to concrete algo-
rithms yields non-trivial lower bounds, in some cases optimal, absolutely or
up to a multiplicative constant.
For a sample result, suppose
A = (A, R1A , . . . , RkA , φ1A , . . . , φlA ) = (A, Υ)
is a first order structure on the vocabulary Φ = {R1 , . . . , Rk , φ1 , . . . , φl },
suppose P ⊆ An is an n-ary relation on A and let Φ0 ⊆ Φ. From these data,
we will define a function
c = calls(Φ0 )(A, P) : An → N ∪ {∞} = {0, 1, . . . , ∞},
1 There are algorithms whose implementations print output (or drop bombs), ask “the user” if
she prefers business or coach class and may never terminate. In this book we confine ourselves to
pure, finitary algorithms which compute partial functions or decide relations from given partial
functions and relations, for which complexity theory is most fully developed. The extension of
most of what we say to algorithms with side effects or interaction requires combining the methods
we will use with classical domain theory, introduced by Scott and Strachey [1971] and richly
developed by Scott and many others since then, especially the early Plotkin [1977], [1983]. It is
not as different from what we will be doing as one might think, but we will not go into it here.
4 Introduction
throw some light on the central problem of deriving and justifying absolute
lower complexity bounds.
The exposition is elementary, aimed at advanced undergraduates, graduate
students and researchers in mathematics and computer science with some
knowledge of logic, a good understanding of the basic facts about algorithms
and computability and an interest in foundational questions. Many of the
(roughly) 250 problems are very easy, to test understanding, but there are also
more challenging ones, sometimes marked with an asterisk ∗ and a few that I
cannot do, marked “Open Problem”.
I have tried hard to assign results to those who proved them and to give
correct and useful references to the literature, but this is not the place to look
for a history of recursion and its interaction with computability—another vast
and complex topic which is way out of my expertise and certainly not of the
moment.
Yiannis N. Moschovakis
Santa Monica, CA and Paleo Faliro, Greece
Acknowledgments.
My greatest debt is to Lou van den Dries, whose insights in van den Dries
[2003] led to a fruitful (and very pleasant) collaboration that produced van
den Dries and Moschovakis [2004], [2009] and ultimately led to Part II of this
book.
I am grateful to Vaughan Pratt and Anush Tserunyan for letting me include
in this book unpublished results of theirs; to Vasilis Paschalis and Tyler Arant
for chasing errors and typos in Parts I and II respectively—and I know they
must have missed some, it’s OK; and to my wife, always, and for many things
other than her help with this book.
To go farther than this, I would need to put down the many logicians,
philosophers and computer scientists who have informed my understanding of
logic, recursion, algorithms and the connections among these subjects, includ-
ing Stephen Kleene, John McCarthy, Dana Scott and many, many others—too
long a list to put down here and certainly not unique to me.
Finally, I want to thank the hundreds of students who have taken courses or
wrote [Link]. or Ph.D. Theses with me on these topics, mostly at UCLA and the
University of Athens, including the Graduate Program in Logic, Algorithms
and Computation (MPLA). It is sometimes said that we learn more from our
students than they learn from us and perhaps this is true of me; in any case,
there is no doubt that I have enjoyed the process, very much.
CHAPTER 1
PRELIMINARIES
We collect here some basic facts we need from set theory, recursion theory,
logic and arithmetic, primarily to fix terminology and notation, and we also
describe some simple examples of algorithms to which we can refer later.
Most readers of this book will know most of these facts and should peruse
this chapter quickly, coming back to it later, as needed. One exception is the
“where” notation in Section 1B for definitions by mutual recursion which we
will use extensively, and another might be the treatment of equational logic of
partial terms in Section 1E: there are several ways to approach this topic, but
only one works well with recursive equations and it is important to get it right
early on.
7
8 1. Preliminaries
2 This definition gives gcd(x, 0) = 0 (even when x = 0), silly values that we do not care about;
but it is useful to have gcd(x, y) defined for all x, y, and these values simplify some equations.
1A. Standard notations 9
3 A partial function f : X * W comes “tagged” with its input and output sets, which means
that “given f” implies that we are also given X and W —and we will often use this, especially in
definitions. On the other hand, if Df ⊆ X 0 and W ⊂ W 0 , then there is exactly one f 0 : X 0 * W 0
which agrees with f on their common domain of convergence, and it is natural to use the same
name for it—which we will often do.
10 1. Preliminaries
f(x, p1 , . . . , pk )↓
=⇒ (∃ finite p10 v p1 , . . . , pk0 v pk )[f(x, p10 , . . . , pk0 ) = f(x, p1 , . . . , pk )],
where a partial function is finite if it has finite domain of convergence.
Partial functions are (degenerate) continuous functionals, with the conven-
tional understanding of (1A-10) and these notions when k = 0.
Typical (and most basic) continuous functionals are the applications,
(1A-11) apn (x1 , . . . , xn , p) = p(x1 , . . . , xn ) (n ≥ 1),
usually with x1 , . . . , xn ranging over some set A and p : An * W .
4 This is Kleene’s strong equality between “partial values” often denoted by “'”.
1A. Standard notations 11
between “function” and “function value” is surely important, but if he could not handle it he was
probably in the wrong field.
6 It is assumed that the input and output sets of the given functionals and the ranges of the
A more dignified name for mangling might be adding, permuting and identi-
fying variables, but that is way too long; whatever you call it, it is a very useful
operation, it provides for definitions of the form
f(x, y, p, r) = h(x, x, r, p, p),
and combined with the three operations preceding it justifies complex explicit
definitions, e.g.,
f(x, y, p, r) = h(x, g1 (x, y, p), (ë~
u )g2 (u, x, u), p, r).
1A.1. Proposition. If a class of functionals F is closed under mangling (1A-15),
then F is closed under substitution (1A-12) if and only if it is closed under com-
position
(1A-16) f(~
x, y ~ , ~r) = g(h(~
~, p ~ ), y
x, p ~ , ~r).
Strings. For any set L, L∗ = L<ù is the set of strings (words, finite se-
quences) from L and we will use mostly standard notations for them:
(1A-17) nil = ( ) (the empty string),
|(u0 , . . . , um−1 )| = m, (u0 , . . . , um−1 )i = ui (i < m),
head((u0 , . . . , um−1 )) = (u0 ) (with head(nil) = nil),
tail((u0 , . . . , um−1 )) = (u1 , . . . , um−1 ) (= nil if m ≤ 1),
cons(u, (v0 , . . . , vm−1 )) = ((u)0 , v0 , . . . , vm−1 )
(u0 , . . . , um−1 ) ∗ (v0 , . . . , vn−1 ) = (u0 , . . . , um−1 , v0 , . . . , vn−1 ),
u v v ⇐⇒ (∃w)[u ∗ w = v], (the initial segment relation),
/ v ⇐⇒ u v v & u 6= v.
uv
These definitions of head(u) and cons(u, v) in effect identify a member t of L
with the string (t) ∈ L∗ , which simplifies in some ways dealing with strings.
Sometimes we denote strings by simply listing their elements
u0 u1 · · · vm−1 ≡ (u0 , u1 , . . . , um−1 ),
especially when we think of them as words from some alphabet L of symbols;
and in such cases, we typically use “≡” to denote the equality relation on
words, since “=” is often one of the symbols in the alphabet.
Trees. For our purposes, a (finite, non-empty, rooted, N-labelled) tree on a
<ù
set X is any finite set T ⊂ (N × X ) of non-empty finite sequences (nodes)
from N × X which has a unique node of length 1, its root and is closed under
initial segments,
∅=
6 u v v ∈ T =⇒ u ∈ T .
1A. Standard notations 13
x1 R x2
and assume it has this structure (with a root which has two children) even if
it happens that x1 = x2 ; so formally, we need to set
T = {((0, x)), ((0, x), (0, x1 )), ((0, x), (1, x2 ))},
14 1. Preliminaries
From recursion theory, we will need the following, fundamental result which
justifies recursive definitions:
1B.1. Theorem (The Fixed Point Lemma). (1) For every continuous func-
tional f : X × (X * W ) * W , the recursive equation
(1B-1) p(x) = f(x, p)
has a v-least solution p : X * W , characterized by the conditions
(FP) p(x) = f(x, p) (x ∈ X ),
(MIN) if (∀x)[f(x, q)↓ ⇒ f(x, q) = q(x)], then p v q (q : X * W ).
We say that p is the canonical solution of (1B-1) and we write
(1B-2) p(x) = f(x, p) >> p.
(2) Similarly, every system of mutual continuous recursive equations
(1B-3) p1 (x1 ) = f1 (x1 , p1 , . . . , pK ), . . . , pK (xK ) = fK (xK , p1 , . . . , pK )
(with input and output sets for f1 , . . . , fK matching so that the equations
make sense) has a v-least (canonical) solution tuple p1 , . . . , pK characterized
by the conditions
(FP) pi (xi ) = f(xi , p1 , . . . p K ) (i = 1, . . . , K, xi ∈ Xi ),
(MIN) if for (i = 1, . . . , K, and all xi ∈ Xi )
f(xi , q1 , . . . , qK )↓ =⇒ fi (xi , q1 , . . . , qK ) = qi (xi ) ,
then p1 v q1 , . . . , pK v qK ,
and we write
p1 (x1 ) = f1 (x1 , p1 , . . . , pK )
p1
(1B-4) .. ..
. >> .
pK (xK ) = fK (xK , p1 , . . . , pK ) pK .
(3) Moreover, if the given functionals have additional partial function argu-
ments ~r = (r1 , . . . , rm ) and p1 (~r), . . . , pK (~r) are defined for each ~r by (2) so
that
p1 (x1 ) = f1 (x1 , p1 , . . . , pK , ~r)
p1 (~r)
(1B-5) .
.. ..
>> .
pK (xK ) = fK (xK , p1 , . . . , pK , ~r) p K (~r),
then the functionals
gi (xi , ~r) = pi (~r)(xi ) (i = 1, . . . , K )
are continuous.
16 1. Preliminaries
p0 v p1 v p2 v · · · ;
S
and set p = {pk : k ∈ N}, i.e.,
f(x, p) = p(x).
is defined as in the proof of (1) for each fixed ~r, then g k is continuous.
(2) and the full statement (for systems) of (3) are proved by the same
argument with some added (messy) notation. a
We refer to (FP) and (MIN) in Part (1) of the Fixed Point Lemma as
the fixed point and the minimality properties of the recursive definition—and
similarly with the corresponding conditions in Part (2).
1B. Continuous, call-by-value recursion 17
The where -notation for mutual recursion. To express and prove properties
of recursive definitions, we now introduce the following two notations for
mutual recursion: given a continuous system of recursive equations and their
solutions
p1 (x1 ) = f1 (x1 , p
~ , ~r) p1 (~r)
.. ..
. >> .
pk (xk ) = fk (xk , p
~ , ~r) pk (~r)
as in (1B-5) (with p ~ = p1 , . . . , pk , ~r = r1 , . . . , rm ) and a continuous functional
f0 (y, p
~ , ~r) (with y varying over some set Y ), we set
n o
(1B-6) f0 (y, p ~ , ~r) where p1 (x1 ) = f1 (x1 , p ~ , ~r), . . . , pk (xk ) = fk (xk , p
~ , ~r)
n o
= f0 (y, p ~ , ~r) where pi (xi ) = fi (xi , p ~ , ~r) : 1 ≤ i ≤ k
=df f0 (y, p1 (~r), . . . , pk (~r), ~r).
A functional f(y, ~r) is defined by recursion from given continuous functionals
f0 , f1 , . . . , fk (with suitable input and output sets) if
The first of the two notations in (1B-6) is useful for giving succinct recursive
definitions of specific functionals while the second simplifies the statement of
general rules for mutual recursion, as in the next result:
1B.2. Theorem (Recursion rules). If f, f0 , . . . , g, g0 , . . . are all continuous
~ = p1 , . . . , pk , q~ = q1 , . . . , qt , ~r = r1 , . . . , rm , then:
and p
n o
(subst) f(g(x, ~r), y, ~r) = f(q(x), y, ~r) where q(x) = g(x, ~r)
n o
~ , q~, ~r) where pi (xi ) = fi (xi , p
(head) f0 (x, p ~ , q~, ~r) : 1 ≤ i ≤ k
n o
where qj (yj ) = gj (yj , q~, ~r) : 1 ≤ j ≤ t
n
= f0 (x, p ~ , q~, ~r) where pi (xi ) = fi (xi , p ~ , q~, ~r) : 1 ≤ i ≤ k,
o
qj (yj ) = gj (yj , q~, ~r) : 1 ≤ j ≤ t
18 1. Preliminaries
n
(Bekič-Scott) f0 (x, q, p ~ , ~r) where pi (xi ) = fi (xi , q, p ~ , ~r) : 1 ≤ i ≤ k,
n oo
q(y) = g0 (y, q, q~, p~ , ~r) where qj (yj ) = gj (yj , q, q~, p ~ , ~r) : 1 ≤ j ≤ t
n
= f0 (x, q, p
~ , ~r) where pi (xi ) = fi (xi , q, p ~ , ~r) : 1 ≤ i ≤ k,
o
q(y) = g0 (y, q, q~, p ~ , ~r), qj (yj ) = gj (yj , q, q~, p~ , ~r) : 1 ≤ j ≤ t
Proof. The (head) and (Bekič-Scott) rules are stated for the record in very
general forms which are hard to understand, and it helps to read the proof for
a special case of (head) below and to work out a special case for (Bekič-Scott)
in Problem x1B.9. Basically, these rules allow us to “flatten” nested recursions,
simply remove all the “ where s” and all the braces except the outermost ones.
(ë-subst). There is only one recursive definition in this identity, which is in
fact trivial,
u , y) = g(~
q(~ u , y, ~r) >> q(~r).
The FP property for it gives
q(~r)(~
u , y) = g(~
u , y, ~r),
so that the right-hand side of (ë-subst) has the value
u )q(~r)(~
f(x, (ë~ u , y), ~r) = f(x, (ë~
u )g(u, y, ~r), ~r);
which is the same as the value of its left-hand side.
(head). For the simple case with k = t = 1 and suppressing the dependence
on ~r which does not enter in the argument, we need to show
n o n o
(1B-8) f0 (x, p, q) where p(u) = f1 (u, p, q) where q(v) = g1 (v, q)
n o
= f0 (x, p, q) where p(u) = f1 (u, p, q), q(v) = g1 (v, q) .
There are three recursive definitions involved in this equation:
(A) q(v) = g1 (v, q) >> q
(1) By the FP property on the second equation of (C), we have (for every
v), qe(v) = g1 (v, qe), and then the MIN property on (A) gives q v qe .
(2) The FP property on the first equation of (C) gives p(u)
e = f1 (u, p,
e qe),
and then the MIN property on (B) gives p(e q ) v pe .
(3) Consider now the two partial functions p(q) and q which by the FP
properties on (B) and (A) satisfy both equations of (C); the MIN property on
(C) then implies that pe v p(q), qe v q .
The boxed inequalities imply first that q = qe, and then
pe v p(q) = p(e
q ) v p,
e
so that all these partial functions are equal and we have p(q) = p.
e
Proof of the general case of (head) is only a notational variant of this and
the Substitution (subst) and Bekič-Scott rules (Bekič-Scott) in the theorem
are proved similarly and we leave them for the problems. a
Monotone recursion. It is well known that Theorems 1B.1 and 1B.2 hold
for monotone functionals which need not be continuous, cf. Theorem 7.36
and the problems for Chapter 7 in Moschovakis [2006]. These are classical
results of elementary set theory whose proofs require definition by transfinite
recursion and we will not need them here.
The next problem is another very special (but important) case of the Bekič-
Scott rule; a version of this is known in classical recursion theory as the First
Recursion Theorem:
x1B.10. Problem. Let f : X × (X * W ) * W be a functional defined by
a recursion
n o
f(x, p) = f0 (x, p, q) where q(y) = f1 (y, p, q)
1C. Some basic algorithms 21
Proof. That (1C-2) determines a function and that (1C-3) holds are both
trivial, by induction on |w| + |v|. For the comparison counting, notice first
that (1C-2) computes merge(w, v) using no comparisons at all, if one of w or
v is nil; if both |w| > 0 and |v| > 0, we make one initial comparison to decide
whether w0 ≤ v0 , and no more than |w| + |v| − 2 additional comparisons after
that (by the induction hypothesis, in either case), for a total of |w| + |v| − 1.a
In the next Chapter 2, we will make precise what it means to compute
merge(w, v) by repeated applications of (1C-2), but it is really quite obvious:
for example, when L = N with the natural ordering:
merge((3, 1), (2, 4)) = (2) ∗ merge((3, 1), (4))
= (2, 3) ∗ merge((1), (4))
= (2, 3, 1) ∗ merge(( ), (4))
= (2, 3, 1, 4).
For each sequence u with |u| = m > 1 and k = b m2 c the integer part of 21 |u|,
let:
(1C-4) half1 (u) = (u0 , . . . , uk−1 ), half2 (u) = (uk , . . . , um−1 ),
and for |u| ≤ 1, set
(1C-5) half1 (nil) = half2 (nil) = nil, half1 ((x)) = nil, half2 ((x)) = (x),
so that in any case
u = half1 (u) ∗ half2 (u)
and each of the two halves of u has length within 1 of 12 |u|.
1C.2. Proposition. The sort function satisfies the equation
(1C-6) sort(u) = if |u| ≤ 1 then u
else merge(sort(half1 (u)), sort(half2 (u)))
and it can be computed from (1C-2) and (1C-6) using no more than |u| log |u|
comparisons.
Proof. The validity of (1C-6) is immediate, by induction on |u|. To prove
the bound on comparisons, also by induction, note that it is trivial when
|u| ≤ 1, and suppose that dlog |u|e = k + 1, so that (easily) both halves of u
have length ≤ 2k . Thus, by the induction hypothesis and Proposition 1C.1,
we can compute sort(u) using no more than
k2k + k2k + 2k + 2k − 1 < (k + 1)2k+1
comparisons. a
By a basic, classical result, the merge-sort is optimal (in a very strong sense)
for the number of comparisons required to sort a string, cf. Theorem 4G.1.
1C. Some basic algorithms 23
The lower bounds for the complexity measure c{rem} (ε, x, y) are best ex-
pressed in terms of the classical Fibonacci sequence, defined by the recursion
Anticipating again terminology from the next chapter, the Stein is a recur-
sive algorithm of the structure
·
(1C-11) Nst = (N, parity, em2 , iq2 , − , =, <)
whose primitives are Presburger functions, cf. page 44.
Horner’s rule. For any field F , Horner’s rule computes the value
VF (a0 , . . . , an , x) = ÷(x) = a0 + a1 x + · · · + an x n (n ≥ 1)
of a polynomial ÷(x) of degree n using no more than n multiplications and n
additions in F as follows:
÷0 (x) = an ,
÷1 (x) = an−1 + x÷0 (x) = an−1 + an x
..
.
÷j (x) = an−j + x÷j−1 (x) = an−j + an−j+1 x + · · · + an x j
..
.
÷(x) = ÷n (x) = a0 + x÷n−1 (x) = a0 + a1 x + · · · + an x n .
This is an example of a simple but important straight line algorithm from the
field primitives of F . It can also be used to decide the (plausibly simpler)
nullity relation of degree n on F ,
(1C-12) NF (a0 , . . . , an , x) ⇐⇒ a0 + a1 x + · · · + an x n = 0,
from the primitives of (the expansion of F by the identity relation on) F,
F = (F, 0, 1, +, −, ·, ÷, =)
by adding a last line7
NF (x) = eqF (÷n (x), 0) = eqF (a0 + a1 x + · · · + an x n , 0).
It is known that Horner’s rule is optimal for many fields and inputs, both
for the number of multiplications and the number of additions that are needed
to compute VF (~ a , x) or to decide NF (~
a , x), in fact the earliest results on this
(from the 1960s) were the first significant lower bounds for natural problems
in algebra. We will establish some of them in Chapter 9.
x1C.1. Problem. Prove that if x > v0 > v1 > · · · > vn−1 , then the compu-
tation of merge((x), v) by (1C-2) will require n comparisons.
In the next two problems we define and analyze a simple algorithm for
sorting, which is much less efficient than the merge-sort.
7 We sometimes use eq (x, y) rather than x = y, especially when the infix notation x = y
A
might cause confusion.
26 1. Preliminaries
and can be computed from (1C-16) and the equation in Problem x1C.4∗ using
no more than s(|u|) comparisons, where for m > 0,
x1C.6∗ . Problem. For the function s(m) defined in (1C-17), prove that
s(m)
limm→∞ log(m!)
= 1.
ϕ k−2 ≤ Fk ≤ ϕ k .
√ √
x1C.8. Problem. Prove that if ϕ = 1+2 5 and ϕ̂ = 1−2 5 are the two roots
of the quadratic equation x 2 = x + 1, then 1 < ϕ < 2, |ϕ̂| < 1. and for all k,
ϕ k − ϕ̂ k ϕk
Fk = √ ≥ √ − 1.
5 5
Hint: Use induction on k for the equation, and infer the inequality from the
ϕ̂ k
fact that √ < 1.
5
x1C.9. Problem. Prove that successive Fibonacci numbers Fk , Fk+1 with
k ≥ 2 are relatively prime, and c{rem} (ε, Fk+1 , Fk ) = k − 1.
Lamé’s Lemma predicts the following upper bounds for c(ε, x, y) for small
values of y (and any x ≥ y):
Values of y c(ε, x, y)
1 1
2 2
3 3
4-5 4
6-8 5
9 - 13 6
These are a bit better than the simple 2 log y bound. The next two problems
clarify the situation, but require some arithmetic (of the sort that we will often
“leave for an exercise”):
x1C.11. Problem. Prove that if x ≥ y ≥ 2, then
√
log( 5y)
c(ε, x, y) ≤ ,
log ϕ
where ϕ is the positive root of x + 1 = x 2 .
x1C.12∗ . Problem. Prove that for all real numbers y ≥ 16,
√
log( 5y)
< 2 log y.
log ϕ
Hint: Check the inequality by hand for y = 16, and then check (using the
Mean value Theorem) that the function
√
log( 5y)
f(y) = 2 log y −
log ϕ
on R is increasing for y > 0.
x1C.13. Problem (Bezout’s Lemma). Prove that for all natural numbers
x, y ≥ 1, there exist integers α, â ∈ Z such that
gcd(x, y) = αx + ây.
In fact, we can set α = α(x, y), â = â(x, y) where the functions
α, â : N × N → Z = {. . . , −2, −1, 0, 1, 2, . . . }
are the least solutions of the following system of recursive equations, for
x ≥ y ≥ 1:
α(x, y) = if (y | x) then 0 else â(y, rem(x, y)),
â(x, y) = if (y | x) then 1
else α(y, rem(x, y)) − iq(x, y)â(y, rem(x, y)).
Use this recursion to express gcd(231, 165) as an integer, linear combination
of 231 and 165.
1D. Partial structures 29
x1C.14. Problem. Prove that two numbers x, y ≥ 1 are coprime if and only
if there exist integers α, â ∈ Z such that 1 = αx + ây.
x1C.15. Problem. For positive numbers, show: if x⊥
⊥ a and x | ab, then
x | b.
x1C.16. Problem. Prove that for all x ≥ y ≥ 1, there are infinitely many
choices of integers α and â such that
gcd(x, y) = αx + ây,
y
but only one choice such that 0 ≤ α < .
gcd(x, y)
x1C.17∗ . Problem. Define an algorithm from the primitives of a field F
which decides the nullity relation (1C-12) of degree n using no more than
n − 1 additions, along with multiplications and equality tests, and count how
many multiplications and equality tests it uses. Hint: Consider separately the
cases where the characteristic of F is 2 or 6= 2 and show first that you can test
whether a + bx = 0 using no additions or subtractions, just multiplications
and equality tests.
To use the basic notions of equational logic in the study of recursion and
computation, we must introduce two small wrinkles: allow the interpretations
of function symbols by partial functions, since computations often diverge,
and add branching (conditionals) to the term-formation rules. We deal with
the first of these here and will move to the second in the next section.
(Many-sorted, partial) structures. A pair (S, Φ) is a vocabulary if the set of
sorts S is not empty, containing in particular the boolean sort boole and at
least one other sort, and Φ is a finite set of function symbols, each with an
assigned type of the form
type(φ) = (s1 , . . . , sn , sort(φ))
where s1 , . . . , sn ∈ S \ {boole} and sort(φ) ∈ S.
A (partial) (S, Φ)-structure is a pair
(1D-1) A = ({As }s∈S , Υ) = ({As }s∈S , {φ A }φ∈Φ ),
where each As is a set; and for each φ ∈ Φ,
if type(φ) = (s1 , . . . , sn , s), then φ A : As1 × · · · × Asn * As .
For s 6= boole, the convergent objects φ A with type(φ) = (s) are the distin-
guished elements of sort s of A.
30 1. Preliminaries
Φ-structures. Most often there is just one sort ind (other than boole): we
describe these structures as in model theory, by identifying the universe (of
individuals) A = Aind , listing Υ, and letting the notation suggest
type(φ) = (ind, . . . , ind, s)
| {z }
nφ
for every φ ∈ Φ—now called the vocabulary. The number nφ is the arity of
φ, and we allow arity(φ) = 0, in which case φ is a (boolean or individual,
perhaps diverging) constant.
A structure is relational if all its primitives are of boolean sort, e.g., if
A = (A, ≤) is an ordering.
Typical are the basic structures of unary and binary arithmetic
(1D-2) Nu = (N, 0, S, Pd, eq0 ), Nb = (N, 0, parity, iq2 , em2 , om2 , eq0 ),
where
em2 (x) = 2x, om2 (x) = 2x + 1
are the operations of even and odd multiplication by 2. More generally, for any
k ≥ 3, the structure of k-ary arithmetic is
(1D-3) Nk-ary = (N, 0, mk,0 , . . . , mk,k−1 , iqk , remk , eq0 ),
where mk,i (x) = kx + i, iqk (x) = iq(x, k) and remk (x) = rem(x, k). These
are total structures, as is the standard structure of Peano arithmetic
(1D-4) N = (N, 0, 1, +, ·, =),
as is the Lisp structure of strings (or lists) from a set L,
(1D-5) L∗ = (L∗ , nil, eqnil , head, tail, cons),
defined on page 12 (with each x ∈ L identified with the string (x)).
The Euclidean structure
(1D-6) Nε = (N, rem, eq0 , eq1 )
is partial, because rem(x, y) converges only when y 6= 0, and so is any field
F = (F, 0, 1, +, −, ·, ÷, =)
(including the reals R and the complexes C) because the quotient x ÷ y
converges only when y 6= 0.
There are many interesting examples of many-sorted structures, e.g., a vector
space V over a field F
V = (V, F, 0F , 1F , +F , −F , ·F , ÷F , 0V , +V , −V , ·)
where the last primitive · : F × V → V is scalar-vector multiplication and
the other symbols have their natural meanings. On the other hand, dealing
1D. Partial structures 31
directly with many sorts is tedious, and we will work with one-sorted Φ-
structures. The more general versions follow by “identifying” a many-sorted
A as in (1D-1) with the single-sorted
(1D-7) (]s∈S 0 As , {A0s : s ∈ S 0 }, Υ) (S 0 = S \ {boole}),
S
where ]s∈S 0 As = {(s, x) : s ∈ S 0 & x ∈ As } is the disjoint union of the
basic universes of A, A0s (t, x) ⇔ [t = s & x ∈ As ] for s 6= boole, and the
primitives in Υ are defined in the obvious way and diverge on arguments not of
the appropriate kind. We will often assume this representation of many-sorted
structures without explicit mention.
Caution! Contrary to the usual assumption in logic, we have allowed the
empty Φ-structure A = (∅, {φ A }φ∈Φ ), in which every φ A is an “empty func-
tion”. The empty structure is of no interest, of course, but it comes up in
constructions of families of structures, where At = {s ∈ B : P(s, t)} with
some P(s, t) for which it is difficult (perhaps effectively impossible) to check
whetherAt is empty. The convention is unusual but does not cause any prob-
lems.
Unified notation for functions and relations. There are still two sorts in Φ-
structures, ind and boole, and we will need to deal with both partial functions
and relations of all arities on their universe. Typically we will just call all these
objects (partial) functions and write
(1D-8) f : An * As (s ∈ {ind, boole}, Aind = A, Aboole = B),
most often skipping the tiresome side notation which explains what this “s”
stands for.
Restrictions. If A = (A, Υ) is a Φ-structure and U ⊆ A = Aind , we set
A U = (U, {φ A U }φ∈Φ ),
where, for any f : An * As ,
f U (x1 , . . . , xn ) = w ⇐⇒ x1 , . . . , xn ∈ U, w ∈ Us & f(x1 , . . . , xn ) = w.
Expansions and reducts. An expansion of a Φ-structure A is obtained by
adding new primitives to A,
(A, Φ) = (A, Υ ∪ Φ).
Conversely, the reduct A Φ0 of a structure8 A = (A, Υ) to a subset Φ0 ⊆ Φ
of its vocabulary is defined by removing all the operations in Υ \ Υ0 . For
example, the reduct of the field of real numbers to {0, +, −} is the additive
group on R,
R {0, +, −} = (R, 0, +, −).
8 It will be convenient to allow on occasion an infinite vocabulary Φ; and in these (clearly
identified) cases, claims about Φ-structures can be interpreted, as usual, as claims about their
reducts A Φ0 to finite subsets of Φ.
32 1. Preliminaries
Notice that we use the same symbol for restriction to a subset and to
a sub-vocabulary, but there is no danger of confusion, even though we will
sometimes combine these two operations:
(1D-9) A Φ0 U = (A Φ0 ) U,
so that, for example, R {0, 1, +, −, ·} Z = (Z, 0, 1, +, −, ·), the ring of
integers.
Substructures. A (partial) substructure U ⊆p A of a Φ-structure A is a
structure of the same vocabulary Φ, such that U ⊆ A and for every φ ∈ Φ,
φ U v φ A , i.e.,
~ ∈ U n & w ∈ Us & φ U (~
x x ) = w =⇒ φ A (~
x ) = w.
A substructure U is strong (or induced) if in addition, for all φ ∈ Φ,
x~ ∈ U n & w ∈ Us & φ A (~x ) = w =⇒ φ U (~ x ) = w,
in which case U = A U .
Notice that we do not require of a substructure U ⊆p A that it be closed under
the primitives of A—in particular, it need not contain all the distinguished
elements of A. This is contrary to the usual terminology in mathematics and
logic, where, for example, a subfield of a field F must (by definition) contain
0, 1 and be closed under +.−, · and ÷.
Diagrams. The (equational) diagram of a Φ-structure A is the set
eqdiag(A) = {(φ, x ~ ∈ An , w ∈ Asort(φ) and φ A (~
~ , w) : φ ∈ Φ, x x ) = w},
where for nullary φ, the entry in eqdiag(A) is (φ, φ A ).
For example, we might have
(1D-10) eqdiag(U) = {2 + 1 = 3, 2 + 3 = 5, 2 ≤ 5, 5 6≤ 1},
where U ⊆p (N, 0, 1, +, ·, ≤) with 2, 1, 3 ∈ U ; and we have used here the
obvious conventions, to write
x ) = w, R(~
φ(~ x ), ¬R(~
x)
rather than the more pedantic
(φ, x
~ , w), (R, x
~ , tt), (R, x
~ , ff)
and to use “infix notation”, i.e., write x + y rather than +(x, y).
Structures are most easily specified by giving their universe and their equa-
tional diagram—especially if they are finite; and clearly,
U ⊆p A ⇐⇒ U ⊆ A & eqdiag(U) ⊆ eqdiag(A).
Sometimes we will specify a structure A by just giving its diagram, the impli-
cation being that its universe A comprises those members of A which occur in
eqdiag(A).
1D. Partial structures 33
eqdiag(Gm [X ]))
= {(φ, u1 , . . . , uni , w) ∈ eqdiag(A) : u1 , . . . , uni , w ∈ Gm [X ] ∪ B}.
34 1. Preliminaries
~ = (x1 , . . . , xn ) ∈ An , we write
For a tuple x
S
Gm (~
x ) = Gm [{x1 , . . . , xn }], G∞ (~
x) = m Gm (~
x ),
Gm (~
x ) = A Gm [{x1 , . . . , xn }], G∞ (~
x ) = A G∞ [X ],
and if the structure in which these sets and substructures are computed is not
obvious from the context, we write Gm (A, x ~ ), Gm (A, x ~ ), etc.
A structure A is generated by x ~ if A = G∞ (A, x ~ ), so that if it is also finite,
then A = Gm (A, x ~ ) for some m.
Certificates. A (Φ-)certificate is a pair (U, x~ ), such that
(1D-14) ~ ∈ U n , and U = G∞ (U, x
U is a finite Φ-structure, x ~ );
and it is a certificate of or in a Φ-structure A if, in addition, U ⊆p A.
Notice that if (U, x ~ ) is a certificate, then U = Gm (U, x
~ ) for some finite m.
We will motivate the terminology in Section 4D but, basically, we will use
certificates (U, x~ ) to model computations on the input x ~.
Certificates carry some natural measures of “size” or complexity, e.g.,
depth(U, x
~ ) = min{m : U = Gm (U, x
~ )},
values(U, x
~ ) = |{w ∈ U : (φ, u~ , w) ∈ eqdiag(U) for some φ, u~ }|,
calls(U, x
~ ) = |eqdiag(U)|.
Notice that depth(U, x ~ ) depends on both U and x ~ , while values(U, x
~ ) and
calls(U, x
~ ) depend only on U.
The meanings of the first and last of these measures are obvious, and the
intermediate values(U, x ~ ) counts the number of distinct values of entries in
eqdiag(U); it may be smaller than the universe U or the number of entries in
eqdiag(U), for example if (U, (2, 3)) is the certificate of the Peano structure N
with
U = {2, 3, 5, 6}, eqdiag(U) = {2 + 3 = 5, 3 + 2 = 5, 3 + 3 = 6},
cf. Problem x1D.6.
We also need the depth of an element below a tuple,
(1D-15) depth(w; A, x
~ ) = min{m : w ∈ Gm (A, x
~ )}, (w ∈ G∞ (A, x
~ )),
and by convention,
depth(tt; A, x
~ ) = depth(ff; A, x
~ ) = 0.
~ ) = 0, and if φ A (u1 , . . . , unφ )↓ , then
Clearly, depth(xi ; A, x
depth(φ A (u1 , . . . , unφ ); A, x
~ ) ≤ max{depth(ui ; A, x
~ ) : i = 1, . . . , nφ } + 1.
The inequality is strict if sort(φ) = boole or
m = max{depth(ui ; A, x
~ ) : i = 1, . . . , nφ } =⇒ φ(~
u ) ∈ Gm (A, x
~ ).
1D. Partial structures 35
(1D-16) depth(w; A, x
~ ) ≤ depth(w; U, x
~)
≤ depth(U, x
~ ) ≤ values(U, x
~ ) ≤ calls(U, x
~ ).
Proof is easy and we leave it for Problem x1D.7. a
U = Gm (A, x
~ ) ⇐⇒ U = Gm (A, x
~)
u ∈ U k , φ ∈ Φ) φ A (~
& (∀~ u )↓ =⇒ φ A (~
u) ∈ U ∪ B .
so that each t in u~0 is xj for some j, and for each s < m, each t in the tuple
u~s+1 occurs in the sequence x ~ , u~0 , w0 , u~1 , w1 , . . . , u~s , ws ; in particular, each
structure Us with
eqdiag(Us ) = (φ0 , u~, w0 ), . . . , (φs , u~s , ws )
~ and so (Us , x
is generated by x ~ ) is a certificate.
x1D.9. Problem. Prove that for every (finite) vocabulary Φ, there is a num-
~ ∈ An and every m,
ber a such that for every Φ-structure A, every x
am
x )| ≤ C 2
|Gm (~ (C = n + |Φ|).
Give an example of a structure A where |Gm (x)| cannot be bounded by a
single exponential in m.
(A-terms) E :≡ tt | ff | x (x ∈ A)
| vi | φ(E1 , . . . , Enφ ) | if E0 then E1 else E2 ,
1E. Partial equational logic 37
Notice that these include terms of sort boole, e.g., tt, ff and R(E1 , . . . , En ) if
R ∈ Φ is of boolean sort, so they are more general than the usual terms of
logic which are all of sort ind.
The depth of an algebraic term is defined by the recursion
E + M :≡ +(E, M )
for binary function symbols, etc. We also define the propositional connectives
on terms of boolean sort using the conditional:
9 We do not allow variables of boolean sort, a convenient choice which does not affect in any
have nice properties when A is not sufficiently rich, e.g., it need not be closed
under composition, cf. Problem x1E.9.
1E.1. Proposition. For every Φ-structure A, Expl(A) is the smallest class E of
functionals on A (as in (1E-6)) which contains all n-ary functions x
~ 7→ tt, x
~ 7→ ff
and all projections Pin and is closed under the following operations:
(1), Mangling, as in (1A-15),
f(x1 , . . . , xn , r1 , . . . rm ) = h(xð(1) , . . . , xð(k) , ró(1) , . . . , ró(l ) ).
(2), Substitution into the primitives, f(~ x , ~r) = φ A (h1 (~ x , ~r), . . . , hm (~
x , ~r)).
(3), Substitution into applications, f(~ x , p, ~r) = p(h1 (~ x , ~r), . . . , hm (~x , ~r)).
(4), Branching, f(~ x , ~r) = if h1 (~
x , ~r) then h2 (~ x , ~r) else h3 (~ x , ~r).
Proof. To prove that Expl(A) is closed under (1) – (4), we need to verify
some simple, natural closure properties of the set of terms; and the proof that
if E has these properties, then it contains every explicit f is by induction on the
term E which defines f. Both arguments are simple exercises in using the de-
finition and properties of the denotation function (especially Problem x1E.4)
and we skip them, except for one small part which we put in Problem x1E.8.a
1E.2. Proposition. Every A-explicit functional is continuous.
Proof. It is enough to check that the collection of continuous functionals
on A is closed under definitions (1) – (4) in Proposition 1E.1. To take just one
case which explains the (obvious) idea, suppose
f(x, r) = φ A (h1 (x, r), h2 (x, r))
with continuous h1 (x, r), h2 (x, r).
To verify first that f(x, r) is monotone, assume that r v r 0 and compute:
φ A (h1 (x, r), h2 (x, r)) = w
=⇒ h1 (x, r)↓ & h2 (x, r)↓ & φ A (h1 (x, r), h2 (x, r)) = w,
but, by the hypothesis, h1 (x, r 0 ) = h1 (x, r) & h2 (x, r 0 ) = h2 (x, r),
and so φ A (h1 (x, r 0 ), h2 (x.r 0 )) = φ A (h1 (x, r), h2 (x.r)) = w.
For the compactness of f(x, r), similarly,
φ A (h1 (x, r), h2 (x, r)) = w
=⇒ h1 (x, r)↓ & h2 (x, r)↓ & φ A (h1 (x, r), h2 (x, r)) = w;
by the assumed compactness and monotonicity of h1 , h2 , there are finite r1 v r
and r2 v r such that
h1 (x, r) = h1 (x, r1 ) = h(x, r1 ∪ r2 ), h2 (x, r) = h2 (x, r2 ) = h2 (x, r1 ∪ r2 ),
where r1 ∪ r2 is the finite “union” of r1 and r2 and
φ A (h1 (x, r), h2 (x, r)) = φ A (h1 (x, r1 ∪ r2 ), h2 (x, r1 ∪ r2 )). a
1E. Partial equational logic 41
Proof is by checking that the class of functionals h for which the Propo-
sition holds satisfies the hypothesis of Proposition 1E.1, and it is trivial in all
cases except (3) when the variable q is involved: i.e., with k = 2 and skipping
~r1 , ~r2 which do not enter the argument,
y , q) = q(h1 (~
h(~ y , q), h2 (~
y , q)).
We compute:
f(~
x, y
~ , p)
= (ëu, v)p(~
x , u, v) h1 (~ y , (ëu, v)p(~x , u, v)), h2 (~
y , (ëu, v)p(~x , u, v)
=p x ~ , h1 (~
y , (ëu, v)p(~x , u, v)), h2 (~
y , (ëu, v)p(~x , u, v))
= p(~
x , f1 (~ ~ , p), f2 (~
x, y x, y
~ , p))
with explicit f1 , f2 by the induction hypothesis, so f(~ ~ , p) is explicit.
x, y a
Such appeals to Proposition 1E.1 are most often the simplest way to verify
properties of all A-explicit functionals, but sometimes it is just simpler to use
directly their definition. A case in point is the following easy and useful result:
1E.4. Proposition. If the vocabulary Φ has a relation symbol R of arity k > 0
and A is a Φ-structure such that RA : Ak → B is total, then Expl(A) is closed
under the substitution operation (1A-12) and ë-substitution (1A-13):
x , ~r) = g(h1 (~
f(~ x , ~r), . . . , hk (~
x , ~r), ~r), f(~
x, y ~ , ~r) = h(~
~, p y , (ë~
u )g(~
u, x ~ ), ~r).
~, p
Proof. For substitution, with k = 2 and suppressing ~r which does not enter
the argument, we need to prove that if
x ) = g(h(~
f(~ x ))
and h(~
x ), g(u) are A-explicit, then so is f(~
x ).
Fix pure, extended terms M (~x) and E(u) such that
x ) = den(M (~
h(~ x )), g(u) = den(E(u)).
Supposing that R is unary, let
F (x) :≡ if R(M (x)) then E(M (x)) else E(M (x))
42 1. Preliminaries
x1E.1. Problem (Parsing for terms). Prove that for any Φ-structure A, every
A-term E satisfies exactly one of the following conditions.
1. E ≡ tt, or E ≡ ff, or E ≡ x for some x ∈ A, or E ≡ v for a variable v.
2. E ≡ φ(E1 , . . . , En ) for a uniquely determined φ ∈ Φ and uniquely
determined terms E1 , . . . , En .
3. E ≡ if E0 then E1 else E2 for uniquely determined E0 , E1 , E2 .
x1E.2. Problem. Prove that if ð : A → B is an isomorphism between two
Φ-structures, then for every extended Φ-term E(~x),
x ) = w ⇐⇒ B |= E(ð(~
A |= E(~ x )) = ð(w), (x1 , . . . , xn , w ∈ A).
x1E.3. Problem. Give an example of two (extended) terms E1 (x) and E2 (x)
such that for every x ∈ A, den(E1 (x)) = den(E2 (x)), but if M is closed and
den(M ) ↑, then den(E1 (M )) 6= den(E2 (M )).
x1E.4. Problem. Prove that for every term E(x) and closed term M ,
den(M ) = w =⇒ den(E(M )) = den(E(w)).
x1E.5. Problem. Prove that for any two terms E1 (x), E2 (x), if M is closed,
den(M )↓ and den(E1 (x)) = den(E2 (x)) for every x ∈ A, then
den(E1 (M )) = den(E2 (M )).
These results extend trivially to simultaneous substitutions.
x1E.6. Problem (Homomorphism property). Prove that if ð : A → B is a
homomorphism of one Φ-structure into another, then for every Φ-term M (~x)
~ ∈ An ,
and all x
if den(A, M (~
x ))↓ , then ð(den(A, M (~
x )) = den(B, M (ð(~
x )))
where, naturally, ð(x1 , . . . , xn ) = (ð(x1 ), . . . , ð(xn )).
x1E.7. Problem. For each of the following (and with the definitions in (1E-1),
(1E-4)) determine whether it is true or false for all terms of boolean sort:
(1) |= if φ then ø1 else ø2 = if ¬φ then ø2 else ø1 .
1E. Partial equational logic 43
Gm (A, x
~ ) = {den(A, E(~
x )) : E(~x) is pure, algebraic,
sort(E) = ind and depth(E) ≤ m},
by the definition of “depth” for algebraic terms on page 37.
x1E.14. Problem. Prove that a partial function f : An * As is A-explicit if
and only if there are pure, algebraic terms Ci (~x) of boolean sort and algebraic
terms Vi (~x) such that
den(V0 (~ x )) if den(C0 (~ x )) = tt,
den(V 1 (~
x )) ow., if den(C 0 (~
x ))↓ & den(C1 (~
x )) = tt,
f(~x) = .
..
den(Vk (~ x )) ow., if den(Ck−1 (~ x ))↓ & den(Ck (~
x )) = tt,
den(Vk+1 (~ x )) ow., if den(Ck (~x ))↓ .
Infer that for a total structure A, a relation R ⊆ An is A-explicit if and only if
it is definable by a quantifier-free formula, as these are defined in (1E-1).
This representation of explicit functions and relations is especially interest-
ing (and has been much studied) for the Presburger structure11
·
(1E-10) NPres = (N, 0, 1, +, − , <, eqN , {remm , iqm }m≥2 ),
where remm (x) = rem(x, m), iqm (x) = iq(x, m). This is because a total
function f : Nn → N is explicit in NPres —a Presburger function—exactly when
its graph is definable in additive arithmetic
N+ = (N, 0, 1, +, eqN ),
a corollary of the classical quantifier elimination result for Presburger arith-
metic, cf. Enderton [2001]. The Presburger functions are piecewise linear in
the following, precise sense:
x1E.15∗ . Problem. Prove that if f : Nn → N is a Presburger function,
then there is a partition of Nn into disjoint sets D1 , . . . , Dk ⊆ Nn which are
11 The Presburger structure has an infinite vocabulary, see Footnote 8 on page 31.
1E. Partial equational logic 45
12 This work of McCarthy is not as well known or appreciated as it should be: there are al-
most no citations of it in early textbooks and articles on the theory of computation by computer
scientists, with the notable exception of Manna [1974] whose last chapter on the Fixpoint Theory
of Programs explains (and extends considerably) McCarthy’s ideas; and the logicians who devel-
oped abstract (and higher type) recursion theory starting in the late 1950s worked in complete
ignorance of McCarthy’s work—including the author of Moschovakis [1989a] who will forever
be embarrassed by this.
49
50 2. Recursive (McCarthy) programs
(1) p1 , . . . , pK are distinct function symbols not in Φ, the recursive variables
of E.
(2) Each Ei (0 ≤ i ≤ K ) is a pure term in the program vocabulary
voc(E) = Φ ∪ {p1 , . . . , pK }.
(3) Each ~xi (1 ≤ i ≤ K ) is a list of distinct individual variables which
includes all the individual variables that occur in Ei .
(4) The arities and sorts of the recursive variables p1 , . . . , pK and the sorts
of the parts Ei of E are such that the equations within the braces make
sense.
The term E0 is the head of E, the system of equations
(2A-2) p1 (~x1 ) = E1 , . . . , pK (~xK ) = EK
within the braces is its body, and we allow K = 0 in this definition, so that
every pure Φ-term is identified with a program with empty body,
E ≡ E where { }.
A program with non-empty body will be interpreted as a mutual recursive
definition, a formal version of the where -notation introduced in Section 1B.
We allow arity(pi ) = 0, in which case the equation for pi in (2A-1) has
the form “pi = Ei ,” the list of variable ~xi is empty and Ei is a pure, closed
voc(E)-term, i.e., a nullary constant φ or function variable pj of either sort.
Free and bound occurrences of variables. All occurrences of the recursive
variables p1 , . . . , pK and all occurrences of individual variables in the body of
a program E are bound in E; the free variables of E (if any) are the individual
variables which occur in the head term E0 .
In general, we think of recursive programs as generalized pure Φ-terms
and we define extended Φ-programs as we did for terms: if the list of distinct
variables ~x ≡ x1 , . . . , xn includes all the free individual variables of E (those
which occur in the head E0 ), then
n o
(2A-3) E(~x) ≡df (E,~x) ≡ E0 (~x) where p1 (~x1 ) = E1 , . . . , pK (~xK ) = EK .
structure (Z, 0, 1, +, −, ·, rem, iq, eq0 ), one for each of the needed coefficients
in Bezout’s Lemma: the first is
n
α(x, y) where α(x, y) = if (rem(x, y) = 0) then 0 else â(y, rem(x, y)),
â(x, y) = if (rem(x, y) = 0) then 1
o
else α(y, rem(x, y)) − iq(x, y) · â(y, rem(x, y))
and the second is obtained from this by changing the head to â(x, y). Both
programs have the binary recursive variables α and â.
In some cases we express algorithms by a single recursive equation, e.g.,
gcd(x, y) = if (y = 0) then x else gcd(y, rem(x, y))
for the Euclidean, and then we need to add a trivial head term to accord with
the “official” definition: so the formal recursive program which expresses the
Euclidean is
We will assume that this addition of a head term is done when needed.13
Semantics. Fix an extended recursive program E(~x) on the vocabulary Φ
as in (2A-3) and a Φ-structure A, let p
~ = (p1 , . . . , pK ) and set
f0 (~ ~ ) = den((A, p
x, p ~ ), E0 (~
x )),
(2A-5)
fi (~ ~ ) = den((A, p
xi , p ~ ), Ei (~
xi )) (i = 1, . . . , K ).
These functionals are continuous by Proposition 1E.2, so we can set
13 Notice that the variables x, y occur both free (in the head) and bound (in the bodies) of these
examples, a practice that is sometimes not allowed in formal languages but is very convenient in
the formal study of recursive equations.
52 2. Recursive (McCarthy) programs
More generally, if~r = r1 , . . . , rm is a list of distinct function symbols (other
than the pj ) and every Ei is a pure term in
voc(E) = Φ ∪ {p1 , . . . , pK , r1 , . . . , rm },
then (2A-3) is an extended recursive program on Φ with parameters (or free
function variables) ~r which is naturally interpreted in expansions
(A, ~r) = (A, Υ, r1 , . . . , rk )
of a Φ-structure A. The parts of E(~x) define now functionals
f0 (~ ~ , ~r) = den((A, p
x, p ~ , ~r), E0 (~
x )),
(2A-8)
fi (~ ~ , ~r) = den((A, p
xi , p ~ , ~r), Ei (~
xi )) (i = 1, . . . , K )
(2A-9) denA
E(~x) (~
x , ~r)
n o
=df f0 (~ ~ , ~r) where p1 (~
x, p x1 ) = f1 (~ ~ , ~r), . . . , pK (~
x1 , p xK ) = fK (~ ~ , ~r) .
xK , p
(2A-10) x , ~r) = f0 (~
f(~ ~ , ~r)
x, p
n o
where p1 (~ x1 ) = f1 (~ ~ , ~r), . . . , pK (~
x1 , p xK ) = fK (~ ~ , ~r)
xK , p
The classical example is the (total) structure Nu = (N, 0, S, Pd, eq0 ) of unary
arithmetic whose recursive partial functions and functionals are exactly the
Turing computable ones, an elegant characterization of Turing computability
due to McCarthy [1963], cf. Proposition 2C.3.14
2A.1. Theorem (The First Recursion Theorem). The class Rec(A) is closed
under recursive definitions: i.e., if (2A-10) holds with A-recursive functionals
f0 , . . . fk , then f is also A-recursive.
14 More precisely, these are the classical deterministic recursive functionals on N; we will intro-
the last step by the (head) rule of Theorem 1B.2, and this recursive definition
of f involves one fewer functional which is not explicit.
If f0 (~ ~ , ~r) is explicit, we can simplify the definition of f by applying
x, p
in the same way the (Bekič-Scott) rule of Theorem 1B.2 to some fi , cf.
Problem x2A.4. a
In effect, the (head) and (Bekič-Scott) rules allow us to remove from n any
expression with nested occurrences of the where-construct all the braces and
o
other than the first and last without changing the value—messy to write up
in full generality but basically trivial and easy to apply in specific recursive
definitions.
The name of the theorem comes from the special case
n o
(2A-13) x ) = p(~
f(~ x ) where p(~x ) = f1 (~
x , p)
by which the least fixed point of every recursive functional is recursive and which
is often dubbed the First Recursion Theorem, at least for Nu .
The First Recursion Theorem combines easily with the recursive rules in
Theorem 1B.2 to yield the elementary closure properties of Rec(A):
2A.2. Corollary. Every A-explicit functional is recursive in A, and Rec(A) is
closed under the elementary operations on functionals in (1A-12) – (1A-15):
(Substitution) f(~ x , ~r) = g(h1 (~ x , ~r), . . . , hk (~
x , ~r), ~r)
(ë-substitution) f(~
x, y ~, p ~ , ~r) = h(~ x , (ë~ u )g(~u, y~, p~ ), ~r)
(Branching) f(~ x , ~r) = if h(~ x , ~r) then g1 (~ x , ~r) else g2 (~
x , ~r)
(Mangling) f(x1 , . . . , xn , r1 , . . . , rm )
= h(xð(1) , . . . , xð(k) , ró(1) , . . . , ró(l ) ).
54 2. Recursive (McCarthy) programs
Proof. For a simple case of mangling which illustrates the trivial argument
that works in general, suppose
f(x, r1 , r2 ) = h(x, x, r1 ),
n o
with h(u1 , u2 , q) = h0 (u1 , u2 , p, q) where p(w) = h1 (w, p, q)
x ) = g(h1 (~
f(~ x ), . . . , hk (~
x )) = p(q1 (~
x ), . . . , qk (~
x ))
n o
where q1 (~ x ) = h1 (~
x ), . . . , qk (~
x ) = hk (~
x ), p(~
y ) = g(~
y)
To simplify the notation further, suppose that the given recursive definition
of h(~
x , q) has only one equation in its body and rewrite it to insert a dummy
dependence of the recursive variable r on x ~ ,15
~, y
n o
h(~x , q) = h0 (~x , r, q) where r(~z ) = h1 (~z , r, q)
n o
= h0 (~x , (ë~
z )r(~z, x ~ ), q) where r(~z , x
~, y ~ ) = h1 (~z , (ë~z )r(~z , x
~, y ~ ), q) ;
~, y
x , (ë~
h(~ u )p(~
u, x ~ )) = h0 (~
~, y x , (ë~z )r(~z , x ~ ), (ë~
~, y u )p(~ u, x
~, y~ ))
n o
where r(~ z, x
~, y~ ) = h1 (~z , (ë~z )r(~z , x ~ ), ë(u)p(~
~, y u, x ~) ;
~, y
15 This maneuver of adding dummy variables is needed because we did not allow the functionals
fi (xi , p
~ , ~r) in the body of a recursive definition (1B-7) with head f0 (y, p
~ , ~r) to depend on the
variable y—which complicates this proof, but simplifies considerably the formulation of the
recursion rules in Theorem 1B.2.
2A. Syntax and semantics 55
Recall that the class of primitive recursive functions on N is the smallest class
of (total) functions on N which contains the successor S, the n-ary constant
functions C0n (~x ) = 0 and the projection functions Pin (~ x ) = xi , and which is
closed under composition and primitive recursion. By the last two problems,
every primitive recursive function f : Nn → Ns is Nu -recursive.
Primitive recursive functions have been studied extensively, especially be-
cause of their applications to proof theory—the most basic of these stemming
from the fact that they are all provably recursive in Peano arithmetic.
(2A-17) x ) = ìy[g(y, x
f(~ ~ ) = 0]
=df the least y such that (∀i < y)(∃w)[g(i, x
~ ) = w + 1 & g(y, x
~ ) = 0].
Combined with classical results (for example in Kleene [1952]), these last
two problems imply easily that a partial function f : Nn * N is Nu -recursive
exactly when it is Turing-computable. We will formulate a version of this for
functionals in Proposition 2C.3.
One would expect that various restrictions on the general form (2A-10) of
recursive definitions yield A-recursive functions and functionals with spe-
cial properties, and there are many results of this kind in what is called
schematology, cf. Greibach [1975] (and references given there) and the ear-
lier Péter [1951] for recursion on N. This is not our topic, but it is worth
discussing here two notions of restricted recursion which are important for
the theory of recursive programs.
Simple fixed points. A partial function f : An * A is a simple fixed point
of A if it is the canonical (least) solution of a single equation
x ) = g(~
p(~ x , p)
with an A-explicit g(~
x , p), so
n o
(2B-1) x ) = p(~
f(~ x ) where p(~
x ) = g(~
x , p) .
2B. Simple fixed points and tail recursion 59
r(s, t, x
~1 , x ~ ) = if (s = t = a)
~2 , x
then f0 (~
x , (ë~
x1 )r(a, a, x
~1 , x ~ ), (ë~
~2 , x x2 )r(a, b, x
~1 , x ~ ))
~2 , x
else if (s = a & t = b)
then f1 (~
x1 , (ë~
x1 )r(a, a, x
~1 , x ~ ), (ë~
~2 , x x2 )r(a, b, x
~1 , x ~ ))
~2 , x
else f2 (~
x2 , (ë~
x1 )r(a, a, x
~1 , x ~ ), (ë~
~2 , x x2 )r(b, a, x
~1 , x ~ ))
~2 , x
and check by an easy fixed-point-argument that for all x ~1 and x
~, x ~2 ,
f1 (~
x1 ) = r(a, b, x
~1 , x ~1 ),
~2 , x f2 (~
x2 ) = r(b, a, x
~1 , x ~ ),
~2 , x
and so f(~
x ) = r(a, a, x
~1 , x ~ ).
~2 , x
60 2. Recursive (McCarthy) programs
It follows that if a~1 , a~2 are sequences of respective lengths those of x
~1 and x
~2 ,
then
x ) = r(a, a, a
f(~ ~1 , a ~ ).
~2 , x
Taken together, these two Propositions say that every A-recursive partial
function is a section of a fixed point, except that to realize this, we may need to
add two strongly explicit points to A. This is an important fact about abstract
recursion, but we will not need it, and so we leave its (technically messy) proof
and a variation of it for Problems x2B.1∗ , x2B.2.
McColm [1989] has also shown that multiplication is not a simple fixed
point of Nu , along with several other results in this classical case. The general
problem of characterizing in a natural way the simple fixed points of a structure
A is largely open and it is not clear what (if any) their algebraic or foundational
significance might be, cf. Problem x2B.6.
Tail recursion. A partial function p : Ak * As is defined by tail recursion
from test : Ak * B, output : Ak * As and ó : Ak * Ak if it is the (canonical,
least) solution of the recursive equation
(2B-6) u ) = if test(~
p(~ u ) then output(~
u ) else p(ó(~
u )).
test(x, y) = eq0 (rem(x, y)), output(x, y) = y, ó(x, y), = (y, rem(x, y)).
Tail recursion captures the notion of explicit iteration, perhaps best ex-
pressed by this
2B. Simple fixed points and tail recursion 61
2B.4. Proposition. The canonical, least solution of the tail recursive equa-
tion (2B-6) is given by
(2B-7) x ) = output(ó m (~
p(~ x )) where m = ìk test(ó k (~
x ))
=df output(ó m (~
x )) where m is least such that
(∀i < m)[test(ó i (~
x )↓ ] & test(ó m (~
x )).
Proof. We use the construction of p(~ x ) in the proof of the Fixed Point
Lemma 1B.1, which starts with the totally undefined p0 (~
x ) and sets
pk+1 (~
x ) = if test(~ x )) else pm (ó k (~
x ) then output(~ x )).
By induction on k, we get
(
k+1 output(ó m (~
x )) where m ≤ k is least such that test(ó m (~
x )),
p (~ x) =
↑ if no such m ≤ k exists,
and then p = limk pk easily satisfies (2B-7). a
Tail recursive programs and functions. An extended Φ-program is tail recur-
sive if it is of the form
(2B-8) E(~x) ≡ p(input(~x))
n o
where p(~u) = if test(~u) then output(~u) else p(ó(~u))
with Φ-explicit terms input, test, output, ó of suitable sorts, arities and co-
arities; and a partial function f : An * As is tail recursive in a Φ-structure A
if it is computed in A by a tail recursive program, i.e., if
(2B-9) x ) = p(input(~
f(~ x ))
n o
where p(~ u ) = if test(~
u ) then output(~
u ) else p(ó(~
u )) ,
with A-explicit input, test, output, ó.We set
Tailrec0 (A) = {f : An * As : n ≥ 0 and f is tail recursive in A}.
In general, this is not a well-behaved class, cf. Problem x2B.7. If A is pointed,
however, it is a very natural, well-structured class of partial functions, espe-
cially because it is then closed under definitions by
Mutual tail recursion. A system of mutual tail recursion in a structure A is
a set of equations
n o
(2B-10) E : p1 (~ x1 ) = f1 (~ ~ ), . . . , pK (~
x1 , p xK ) = fK (~ ~)
xK , p
where each fi (~ ~ ) is in one of the following two forms, with A-explicit
xi , p
testi (~
xi ), outputi , óij (~
xi ) and ôik (~
xi ):
(tail call) fi (~
xi ) = if testi (~
xi ) then outputi (~ xi ) else pj (óij (~
xi ))
(branching call) fi (~xi ) = if testi (~
xi ) then pj (óij (~
xi )) else pk (ôik (~
xi )).
62 2. Recursive (McCarthy) programs
2B.5. Theorem. If A is pointed and p1 , . . . , pn are the solutions of a system
of mutual tail recursion (2B-10), then each p i is tail recursive in A.
Proof. If all the equations in (2B-10) are branching calls, then their solu-
tions are the partial functions with empty domains of convergence; and if they
are all tail calls, then the proof is simple and we leave it for Problem x2B.10.
So we may assume that there is an L such that 1 ≤ L < K , every fi (~ xi ) is
a tail call for i ≤ L and every fi (~ xi ) is a branching call when L < i ≤ K . We
will also simplify notation by
writing x for x
~1 , . . . , x
~n
and pretending for the moment that A has K strongly explicit constants,
1, . . . , K . With these conventions, we put
W
W
test(i, x) ⇐⇒df 1≤j≤L [i = j & testi (~
xi )]
⇐⇒ [i = 1 & test1 (~
xi ] ∨ · · · ∨ [i = L & testL (~
xL ],
output1 (~
x1 ) if i = 1,
..
output(i, x) =df .
output (~
L xL ) otherwise, if i ≥ L.
This is certainly true at t = 0, when all these partial functions have empty
domain of convergence.
In the induction step, first for i ≤ L,
with an A-explicit functional g(~ x , p, ~r), i.e., if f satisfies the relativized version
of (2B-1) in which we allow the given g to depend on the arbitrary parameters
~r. In the same way, f(~ x , ~r) is tail recursive in A if for suitable A-explicit
64 2. Recursive (McCarthy) programs
h1 , . . . , hk , test, output,
x2B.1∗ . Problem (Adding points, 1). Prove Proposition 2B.3: that for every
A and every f : An * As ,
f ∈ Rec(A) ⇐⇒ f a,b ∈ Rec(A[a, b]),
with A[a, b] and f a,b defined by (2B-4) and (2B-5). Hint: For the non-
trivial direction (⇐=), we need to code an arbitrary A[a, b]-explicit recursive
equation by a (long) system of A-explicit equations; it is clear that this can be
done in some way, and the trick is to formulate a precise lemma which gives it
and which can be proved “by induction”, i.e., by appealing to Proposition 1E.1.
x2B.2. Problem (Adding points, 2). Define A[a, b]∗ like A[a, b], except that
each φ ∈ Φ is now interpreted by
φ ∗ (x1 , . . . , xn ) = if x1 , . . . , xn ∈ A then φ(x1 , . . . , xn ) else a,
so that if A is a total structure, then so is A[a, b]∗ . Prove that for any partial
function f : An * As , f ∈ Rec(A) ⇐⇒ f a,b ∈ Rec(A[a, b]∗ . Hint: Use
Problem x2B.1∗ , do not repeat its proof.
The next three problems lead to a proof of Proposition 2B.1.
x2B.3. Problem. Suppose F (x, p) is a continuous functional whose fixed
point p : N → N is a total, unary function, and let
(2B-16) stage(x) = stageF (x) = the least k such that p k (x)↓ −1
in the notation of Lemma 1B.1. Prove that for infinitely many x,
stage(x) ≤ x.
2B. Simple fixed points and tail recursion 65
fi (~
x ) = pi (inputi (~
x ))
n o
where pi (ui ) = if testi (ui ) then outputi (ui ) else pi (ói (ui )
for i = 1, 2, 3, where ui varies over some product Aki and all the twelve partial
functions in them are explicit in A.
2B. Simple fixed points and tail recursion 67
q1 (~
x ) = q11 (~
x , input1 (~
x ))
q11 (~
x , u) = if test1 (u) then r(~
x , u) else q11 (~
x , ó1 (u))
x , u) = if output1 (u) then q2 (~
r(~ x ) else q3 (~
x)
q2 (~
x ) = q21 (~
x , input2 (~
x ))
q21 (~
x , v) = if test2 (v) then output2 (v) else q21 (~
x , ó2 (~
x ))
q3 (~
x ) = q31 (~
x , input3 (~
x ))
q31 (~
x , w) = if test3 (w) then output3 (w) else q31 (~
x , ó3 (w)).
By Proposition 2B.4,
x , v) = output2 (ó2m (v)) with m least such that test2 (ó2m (v))
q 21 (~
and so
and similarly q 3 (~
x ) = f3 (~
x ). It takes just a bit more work to show that
q 1 (~
x ) = if f1 (~
x ) then f2 (~
x ) else f3 (~
x ) = f(~
x ).
S ó T
ó s
input - s ó
z output W
- f(x)
···
X x 0
?
inputð (~
x ) = ð(input(~
x )), óð (ð(s)) = ð(ó(s)),
Tð (ð(s)) = T (s), outputð (ð(s)) = output(s).
2C.2. Theorem. For any structure A, a partial function f : An * As is tail
recursive in A if and only if it is computed by an iterator i which is explicitly
representable in A.
This, too is an easy consequence of Proposition 2B.4 and we leave it for
Problem x2C.3, but it is the main tool for relating computability and com-
plexity theory developed (as is usual) using computation models to abstract
recursion. For example:
2C.3. Proposition (Turing computability and recursion). Every deterministic
Turing machine which operates on natural numbers using their binary expansions
is explicitly representable in the structure Nb = (N, 0, parity, iq2 , em2 , om2 , eq0 )
of binary arithmetic.
As a consequence, a functional f(~ x , ~r) on N is computable by a deterministic
Turing machine if and only if it is tail recursive in Nb —which is equivalent to f
being recursive in Nb or Nu .
Outline of proof. The second claim follows from the general theory of tail
recursion we developed in Section 2B and some unavoidable Turing machine
programming.
For a detailed proof of the main claim, we would need to settle on one of
a myriad of precise specifications of Turing machines and do a lot of coding,
which is not of the moment. We explain, instead, the simple idea which is
72 2. Recursive (McCarthy) programs
needed using a toy example and leave for Problem x2C.4 the argument for a
more general, reasonably realistic case.
Suppose a Turing machine M has only one two-way infinite tape, only
one symbol in its alphabet, 1, (internal) states Q0 , . . . , Qk (with Q0 declared
initial), and computes a unary partial function f : N * N by operating on
the unary (tally) representation of numbers
n = |1 ·{z
· · 1},
n+1
so that 0 = 1, 1 = 11, etc. If we use 0 to denote the blank square, then the
“complete configuration” of M at a stage in a computation is a triple (Qj , ô, i),
where ô : Z → {0, 1}, ô(l ) = 0 for all but finitely many l ’s, and i ∈ Z is the
location of the scanned cell; and if we then write ô as a pair of sequences
emanating from the scanned cell y0
· · · x3 x2 x1 x0 y 0 y 1 y 2 y 3 · · ·
↑
one “growing” to the left and the other to the right, we can code (ô, i) by the
pair of numbers
P P
(x, y) = ( k xk 2k , k yk 2k )
and code the complete configuration of M by the triple of numbers (j, x, y).
So we can identify the set S of states of the iterator defined by M with N3 ,
and then output(j, x, y) = y and the set T of terminal states is defined by
cases on j, keeping in mind that the numbers 0, . . . , k are all strongly explicit
in Nb —as are all numbers.
To check that the transition function ó : N3 → N3 is also explicit in Nb ,
notice first that y0 = parity(y) so that the scanned symbol can be computed
from x and y by Nb -operations. The input configuration for the number n
is coded by the triple (Q0 , 0, y) where n is the binary expansion of y, i.e.,
y = 1 + 2 + · · · + 2n = 2n+1 − 1; and all machine operations correspond to
simple Nb -explicit functions on these codes. For example:
move to the right : x 7→ 2x + parity(y), y 7→ iq2 (y),
move to the left : x 7→ iq2 (x), y 7→ 2y + parity(x),
print 1 on the scanned square : x 7→ x, y 7→ 1 + em(iq2 (y)) = om(iq2 (y)),
where, with the notation of (1D-2),
2x + parity(y) = if (parity(y) = 0) then em2 (x) else om2 (x).
Using these functions, it is quite simple to construct an explicit definition of
ó (setting ó(j, x, y) = (j, x, y) if j > k).
If M has two symbols 1 and a and we want it to receive the input in binary
notation, which is typical, then the scanned symbol can be any one of blank,
2C. Iterators 73
0, 1 or a, we code these by the four pairs 00, 10, 01 and 11 respectively, and
we “pad” the tapes so that they have even length and they can be read as
sequences of these symbols. If, for example, the input is 4, which is 001 in
binary, then the initial configuration is (0, 0, y) where the binary expansion of
y is 101001 so y = 1 + 22 + 25 = 1 + 4 + 32 = 37. It is again easy to check that
the elementary operations of M are explicit in Nb —and the same well-known
technique of using binary sequences of fixed length to code any finite number
of symbols and padding the tapes works in general. a
About implementations (I). An implementation of a “program” or “algo-
rithm” which computes a partial function f : X * W is—at a minimum—an
iterator i : X W which also computes f, it is correct. They come in
many varieties and are classified in many ways, especially by whether they are
sequential or parallel and by what resources (e.g., space) they use.
None of this is precise, of course, as there is no general agreement on what
“programs” (in general) or “algorithms” are, and it is certainly not enough:
no one would argue that the merge-sort and the insert-sort have the same
implementations, even though they both compute the sorting function from
the same primitives. On the other hand, these terms are intuitively understood
quite well, they are widely used and there are few arguments about whether a
particular iterator is an implementation of a specific algorithm, whether it is
parallel or sequential, etc.
We will define a (classical) sequential implementation of recursive programs
in the next section and we will also discuss briefly the (difficult) problem of
making these notions and claims about them precise in Section 2H; other than
that, we will use these terms loosely, with their customary, intuitive meaning
when they help explain or motivate what we want to do or have done. For
example, we can read Theorem 2C.1 as claiming (in part) that an iterator i
implements the tail recursive program
n o
Ei : p(input(~x)) where p(~u) = if test(~u) then output(~u) else p(ó(~u))
which expresses it in Ai , but it is clear from the proof that much more than
that is established about the connection between i and Ei , cf. Problem x3A.3.
x2C.2. Problem (Theorem 2C.1). Prove that the partial function computed
by an iterator i : X W is tail recursive in Ai .
74 2. Recursive (McCarthy) programs
x2C.3. Problem (Theorem 2C.2). Prove that f : An * As is tail recursive
in a structure A exactly when it is computed by an iterator i which is explicitly
representable in A.
x2C.4. Problem. Outline a proof of Proposition 2C.3 for a Turing machine
M which computes a functional f(x, y, p) on N with p ranging over unary
partial functions, has K symbols in its alphabet and uses two two-way tapes—
one of them to call the “oracle” for p.
(pass) a~ x : ~b → a~ : x ~b (x ∈ A)
(e-call) ~ ~b → a~ : φiA (~
a~ φi : x x ) ~b
(i-call) ~ ~b → a~ Ei (~
~ pi : x
a x , ~p) : ~b
(comp) a~ h(F1 , . . . , Fn ) : ~b → a~ h F1 · · · Fn : ~b
~ if F then G else H : ~b → a~ G H ? F : ~b
(br) a
(br0) a~ G H ? : tt ~b → a~ G : ~b
(br1) a~ G H ? : ff ~b → a~ H : ~b
• The underlined words are those which trigger a transition and are
changed by it.
• In (pass), x ∈ A ∪ B.
• In the external call (e-call), x~ = x1 , . . . , xn , φi ∈ Φ, and arity(φi ) = n.
• In the internal call (i-call), pi is an n-ary recursive variable of E defined
by the equation pi (~x) = Ei (~x, ~p).
• In the composition transition (comp), h is a (constant or variable) func-
tion symbol in voc(E) with arity(h) = n.
and the input function uses the head term E0 (~x) of E(~x),
input(~
x ) ≡ E0 (~
x) :
and it is a partial function, because for a given s (clearly) at most one transition
s → s 0 is activated by s. Notice that only the external calls depend on the
structure A and only the internal calls depend on the program E—and so, in
particular, all programs with the same body share the same transition function.
76 2. Recursive (McCarthy) programs
An illustration of how these machines compute is given in Figure 2 on
page 77.
The next result is a trivial but very useful observation:
2D.1. Lemma (Transition locality). If s0 , s1 , . . . , sn is a partial computation
of i(A, E) and a~ ∗ , ~b ∗ are such that the sequence a~ ∗ s0 ~b ∗ is a state, then the
sequence
a~ ∗ s0 ~b ∗ , a
~ ∗ s1 ~b ∗ , . . . , a
~ ∗ sn ~b ∗
is also a partial computation of i(A, E).
2D.2. Theorem (Implementation correctness). (1) Suppose A is a Φ-struct-
ure, E(~x) is an extended Φ-program with recursive variables p1 , . . . , pK , the
partial functions p1 , . . . , pK are the mutual fixed points in A of the system in
the body of E(~x)
(2D-2) pi (~
xi ) = den((A, p1 , . . . , pK ), Ei (~
xi )) (i = 1, . . . , K )
and M is an (A, E)-term. Then for every w ∈ A ∪ B,
(2D-3) den((A, p1 , . . . , pK ), M ) = w ⇐⇒ M : →∗i(A,E(~x)) : w.
In particular, with M ≡ E0 (~
x ),
den(A, E(~ x ) →∗i(A,E(~x)) : w,
x )) = w ⇐⇒ E0 (~
and so the extended program E(~x) and the recursive machine i(A, E(~x)) compute
the same partial function in A.
(2) Similarly for functionals: if E(~x) is an extended Φ program with para-
x , ~r) on A, then, for every
meters ~r ≡ r1 , . . . , rk which computes a functional f(~
~r, the recursive machine i((A, ~r), E(~x)) associated with E(~x) and ~r computes
f(~x , ~r).
Outline of proof. With A and E(~x) fixed, we write i = i(A, E(~x)).
(1) First we define the partial functions computed by i,
pei (~ xi ) : →∗i : w
xi ) = w ⇐⇒ pi (~ (i = 1, . . . , K )
and show by an easy induction on the closed term F that
(2D-4) den((A, pe1 , . . . , peK ), F ) = w ⇐⇒ F : →∗i : w.
When we apply this to the terms Ei (~
xi ), we get
den((A, pe1 , . . . , peK ), Ei (~ xi ) →∗i w ⇐⇒ pei (~
xi )) = w ⇐⇒ Ei (~ xi ) = w;
which then means that the partial functions p
e1, . . . , peK satisfy the system (2D-2).
Next we show that for any closed term F as above and any system p1, . . . , pK of
solutions of (2D-2),
F : →∗i w =⇒ den((A, p1 , . . . , pK ), F ) = w.
2D. The recursive machine 77
f(2, 3) : (comp)
f23 : (pass, pass)
f : 2 3 (i-call)
if (2 = 0) then 3 else S(f(Pd(2), 3)) : (br)
3 S(f(Pd(2), 3)) ? eq0 (2) : (comp, pass, e-call)
3 S(f(Pd(2), 3)) ? : ff (br2)
S(f(Pd(2), 3)) : (comp)
S f(Pd(2), 3) : (comp)
S f Pd(2) 3 : (pass)
S f Pd(2) : 3 (comp)
S f Pd 2 : 3 (pass)
S f Pd : 2 3 (e-call)
Sf : 1 3 (i-call)
S if (1 = 0) then 3 else S(f(Pd(1), 3)) : (br), (comp many times)
S S f Pd(1) 3 : (pass)
S S f Pd(1) : 3 (comp)
S S f Pd 1 : 3 (pass)
S S f Pd : 1 3 (e-call)
SSf : 0 3 (i-call)
S S if (0 = 0) then 3 else S(f(Pd(0), 3)) : (br), (comp many times), (pass)
S S 3 S f(Pd(0), 3) ? eq0 (0) :
S S 3 S f(Pd(0), 3) ? : tt (br0)
SS3 : (pass)
SS : 3 (e-call)
S : 4 (e-call)
: 5
(e-call) a~ φi : ~x ~b → a~ : φi (~x) ~b
(br0) a~ G H ? : b0 ~b → a~ G : ~b (if b0 = tt)
(br1) a~ G H ? : b0 ~b → a~ H : ~b (if b0 = ff)
and consider the symbolic computation starting with the head p(u, u) :
If the environment does not decide the term eq0 (u), then the computation
cannot go any further, it stalls. If the environment has the condition eq0 (u) =
ff, then (br1) is activated and we continue:
The next time that ? will show up, we will need to have one of the two conditions
: S n (u)
(I think) are the minimal, known hypotheses on A which guarantee that R(A) = Tailrec(A)—
they are satisfied, for example, when A is a proper, elementary extension of A. They also imply
reasonable versions of the Enumeration and Snm theorems, so that a decent part of classical
recursion theory can be developed for these structures. (And as far as I know, it was Jon Barwise
who first noticed this, for the corresponding problem in the theory of inductive definability on an
arbitrary A.)
82 2. Recursive (McCarthy) programs
2E. Finite nondeterminism
(2E-1) s →∗i s 0
⇐⇒ there is a convergent computation (s0 , . . . , sn ) with s0 = s, sn = s 0
and we say that i computes f : X * W if
(2E-2) f(x) = w ⇐⇒ (∃s ∈ T )[input(x) →∗i s & output(s) = w],
but they must be read more carefully now: i : X W computes f if whenever
f(x)↓ , then at least one convergent computation starting with input(x) produces
the value f(x) and no convergent computation from input(x) produces a different
value. Divergent computations are disregarded.
Nondeterministic recursive programs are defined exactly as before, except
that we allow multiple definitions for each recursive variable. For example, in
iterator” we mean some i which may be deterministic, and the same for programs; in other words,
“deterministic” is the default, even if sometimes, for emphasis, we refer to a “deterministic”
iterator or program.
2E. Finite nondeterminism 83
so each t in u~0 is xj for some j, and for each s < m, each t in the tuple u~s+1
occurs in the sequence x ~ , u~0 , w0 , u~1 , w1 , . . . , u~s , ws . Define the program
n
E ≡ p0 (~x, φ0 (~u0 )) where p0 (~x, y) = p1 (~x, φ1 (~u1 )),
o
p1 (x, y) = p2 (~x, φ2 (~u2 )), . . . , pm (~x, y) = φm (~um )
with suitably chosen tuples of variables ~ui so that if we set~x := x ~ , then ~u0 = u~0 ,
~u1 = u~1 , . . . , ~um = u~m ; and finally check that if c is the computation of the
recursive machine for E on the input E0 (~ x ) = p0 (~
x , φ0 (~
u )), then U = Uc . a
Fixed point semantics for nondeterministic programs. It is also useful to
characterize the denotations of nondeterministic programs using a natural
least-fixed-point operation, if for no other reason than to verify that the
definitions we gave do not depend on the specific choice of the recursive
machine as a “preferred” implementation—as there are many others. We
define here the notions we need and leave for Problems x2E.14∗ and x2E.15∗
the precise formulation and (easy) proofs of the relevant correctness results.
A partial multiple valued (pmv) function f : X *mv W assigns to each
x ∈ X a (possibly empty) subset of W . We write
f(x) →mv w ⇐⇒ w ∈ f(x),
f(x)↓ ⇐⇒ f(x) 6= ∅,
Gf (x, w) ⇐⇒ f(x) →mv w (the graph of f),
and we put on the space (X →mv W ) of all pmv functions on X to W the
partial ordering induced by their graphs,
f ⊆ g ⇐⇒ Gf ⊆ Gg ⇐⇒ (∀x, w)[f(x) →mv w =⇒ g(x) →mv w].
Every partial function f : X * W can be viewed as a pmv function whose
values are empty or singletons, f(x) = {f(x)} = {w : f(x) = w}, and the
basic operations on partial functions we introduced in Section 1A (easily and
2E. Finite nondeterminism 85
naturally) extend to pmv functions. For example: the composition and the
conditional operations on pmv functions are defined by
19 This theorem and Problems x2E.16 – x2E.19 are in Pratt [2008] which has not been published.
x2E.1. Problem. Prove that the following are equivalent for a Φ-structure
A and a nondeterministic extended Φ-program E(~x):
(a) E(~x) computes a partial function in A.
(b) E(~x) computes a partial function in every substructure U ⊆p A.
(c) E(~x) computes a partial function in every finite substructure U ⊆p A.
2E. Finite nondeterminism 87
x2E.19. Problem. Fix t ≥ 2. Prove that for every s ≥ 1 and every u such
that u ≤ 2s and t − u ≥ 2, there is a computation of Pratt’s algorithm which
starts from (Ft+1 , Ft , Ft+1 , Ft ) and reaches a state (Ft+1 , Ft , ?, Ft−u ) doing no
more than 2s divisions.
Infer that for all t ≥ 3,
(2E-14) c s (rem)(Nε , EP (Ft+1 , Ft )) ≤ 2dlog(t − 2)e + 1 = O(log log(Ft )).
Hint: The measure c s (Φ0 )(A, E(~x )) for nondeterministic recursive programs
is defined in (2E-5). For (2E-14), you also need Problem x1C.7.
90 2. Recursive (McCarthy) programs
2F. Some standard models of computation
We discuss here some of the many important results on the relation between
full and tail recursion. It is an interesting and difficult subject, but not central
21 This does not affect the Cook-Reckhow RAMs over the structure A
CR in (2F-4), in which
eqN is obviously explicit.
2G. Full vs. tail recursion (I) 95
to our concerns, and so we will focus on just a few, characteristic facts and
mostly skip proofs.22
Examples where Tailrec0 (A) ( Rec0 (A). Perhaps the first example of a
structure where some recursive function is not tail recursive is the following
2G.1. Theorem (Patterson and Hewitt [1970], Lynch and Blum [1979]).
There is a total, pointed, countable structure
T = (T, 0, 1, s, d, leaf, red, eq0 , eq1 )
with s, d : T → T and leaf, red, eq0 , eq1 : T → B, such that
Tailrec0 (T) ( Rec0 (T),
in fact some total relation on T is recursive but not tail recursive.
Proof. For each n ≥ 0, let
Tn = {(n, t0 , . . . , ti−1 ) : i ≤ n & (∀j ≤ (i − 1))[tj ≤ 1]},
viewed as the complete binary tree of sequences of length ≤ (n + 1), with the
root labelled n and all the other nodes labelled 0 or 1. It carries the obvious
son, daughter and leaf functions
s(u) = u ∗ {0}, d (u) = u ∗ {1} (|u| < n + 1),
leaf(u) ⇐⇒ |u| = n + 1,
where |(n, t0 , . . . , ti−1 )| = i + 1 as in (1A-17) and s(u) = d (u) = u if leaf(u).
It has 2n leaves and 2n+1 − 1 nodes.
A (restricted) coloring of Tn assigns to each node white or red, so that all the
nodes which are not leaves are white and all but at most one leaf are painted
red; so there are 2n + 1 colored trees of depth n, say
Tn,1 , . . . , Tn,2n +1 with Tn,1 the tree where all leaves red.
The (disjoint) union
S
T = n,1≤j≤2n +1 Tn,j
is the universe of T, and the functions and relations on it are those inherited
from the individual trees, with the constants 0 and 1 respectively naming the
leaves (1, 0), (1, 1) of the tree T1,1 .
The unary (total) relation
(2G-1) Red(u) ⇐⇒ all the leaves below u are red
is recursive in T—in fact a simple fixed point—since it is (easily) the unique
solution of the recursive equation
p(u) = if leaf(u) then red(u) else p(u ∗ {0}) & p(u ∗ {1}) .
22 I am indebted to Siddharth Bhaskar for advising me on what to include from this area in
which I am anything but expert—but, of course, the blame for what is left out is entirely mine.
96 2. Recursive (McCarthy) programs
To complete the proof, it suffices to prove that Red(u) is not tail recursive, or
equivalently by Proposition 2F.1 and the discussion on page 91, that Red(u) is
not decided by a primitive register program; so assume towards a contradiction
that some primitive register program P of T with k registers and L+1 commands
decides Red(u), so that by (2F-2)
Red(u) ⇐⇒ P starting on (0, u, a~ ) returns tt
with suitable constants a
~ = a2 , . . . , ak . We consider the computations of P
on inputs of the form
(2G-2) u = (n) ∈ Tn,j , where n ≥ 2 & 1 ≤ j ≤ 2n + 1,
and we leave for Problem x2G.1 the proofs of three simple lemmas about them:
Lemma 1. If a state (l, x1 , . . . , xk ) occurs in the computation of P starting
with (2G-2), then every xi is either a constant or a node in Tn .
Call two states
s = (l, x1 , . . . , xk ) and s 0 = (l 0 , x10 , . . . , xk0 )
in a computation by P equivalent if the following conditions hold:
(i) l = l 0 .
(ii) For i = 1, . . . , k,
xi = 0 ⇐⇒ xi0 = 0, xi = 1 ⇐⇒ xi0 = 1, red(xi ) ⇐⇒ red(xi0 ).
(iii) For i = 1, . . . , k, |xi | = the length of the node xi = |xi0 |.
Notice that by (i),
if s is equivalent with s 0 , then [s is halting ⇐⇒ s 0 is halting].
Lemma 2. If s and s 0 are equivalent and the transition function of P takes s
to s and s 0 to s 0 , then s and s 0 are also equivalent.
Lemma 3. The number of equivalence classes of states in a computation of P
starting with (2G-2) is bounded by (L + 1)23k (n + 1)k .
Granting these lemmas, consider now the computation
(0, (n), a
~ ), (l1 , x
~1 ), . . . , (lm , x
~m )
of P with shape (sequence of addresses) (0, . . . , lm ) where
2n > k(L + 1)23k (n + 1)k
and (n) is the root of Tn,1 , the copy of Tn in which all leaves are red. The state
(lm , x
~m ) is halting and returns tt, and no previous state is halting; this means,
by Lemma 2, that
m < (L + 1)23k (n + 1)k < 2n ,
since otherwise some (li , x
~i ) would be equivalent with some (li+k , x
~i+k ), and
then
li = li+k = li+2k , . . . ,
2G. Full vs. tail recursion (I) 97
and the computation would diverge. It follows that at least one leaf of Tn,1 does
not occur in any of the registers during the computation, since the number of
nodes which are “seen” is ≤ k(L + 1)23k (n + 1)k < 2n ; and this means that
“the same” computation is executed by P if we start with (n) the root of the
tree Tn,i in which this leaf is white, which then returns the wrong value. a
Patterson and Hewitt [1970] was written at a time when a central problem
was the logic of programs, the search for natural conditions which insure that
two program schemas compute the same partial function on all structures of
a fixed vocabulary, cf. Walker and Strong [1973]. This influenced the formu-
lation of results, including Theorem 2 of Patterson and Hewitt [1970] which
claims only that a specific recursive program is not logically equivalent to any
finite register program. Lynch and Blum [1979] define a specific structure in
which some recursive function is not tail recursive as in Theorem 2G.1, which
we proved here by a slight modification of the Patterson-Hewitt construction.
Many better examples were given later, including Stolboushkin and Tait-
slin [1983] which starts with a Burnside group, not quite trivial to construct
and especially Tiuryn [1989], which also gives many references to the extensive
literature on the problem and related results on the difference between the ex-
pressive power between deterministic and nondeterministic register programs.
The Tiuryn example is simple to describe and it includes the identity relation
among the primitives—which makes the proof of the version of Lemma 3 that
is needed much more difficult. We will discuss some of this work in Problems
x2G.2 – x2G.4, but we will not reproduce Tiuryn’s proof.
Examples where Tailrec0 (A) should be ( Rec0 (A). Jones [1999] proves that
Tailrec0 (L–b ) ( Rec0 (L–b ) ⇐⇒ LOGSPACE 6= PTIME,
where L–b = ({0, 1}∗ , nil, eqnil , head, tail) is the cons-free reduct of the Lisp
structure L∗ on binary strings. He proves many other things in this seminal
paper, and in the subsequent Jones [2001] he obtains similar characteriza-
tions of the distinction between full and tail recursion for some higher type
structures.23
Bhaskar [2018] uses one of Jones’ methods to show that
Tailrec0 (NPd ) ( Rec0 (NPd ) ⇐⇒ EXPTIME 6= LINSPACE,
where predecessor arithmetic NPd = (N, 0, 1, Pd, eq0 ) is the successor-free
reduct of unary arithmetic Nu . A more interesting (and substantially more
difficult) result in this paper is the equivalence
Tailrec0 (Fp ) ( Rec0 (Fp ) ⇐⇒ EXPTIME 6= LINSPACE (p prime),
23 Some results of this type were also cited in Tiuryn [1989] about the related distinction between
x2G.1. Problem. Prove the three lemmas in the proof of Theorem 2G.1.
Hint: The commands in the primitive register program P are all in one of the
forms
xi := xj ; goto l 0 , xi := s(xj ); goto l 0 , xi := d (xj ); goto l 0
if test(xi ) goto l 0 else goto l 00 , halt, return output(xi ),
where test and output are leaf, red, eq0 , or eq1 . Taking cases on this list verifies
easily Lemmas 1 and 2, and Lemma 3 is also easily proved by a counting
argument.
x2G.2. Problem. Let for each n ≥ 0
Tn = {(n, t0 , . . . , ti−1 ) : i ≤ n & (∀j ≤ (i − 1))[tj ≤ 1]},
as in the proof of Theorem 2G.1, and consider the forest
S
Ts = ( n Tn , 0, 1, s, d, =)
as before but without the colors and with the addition of =. Prove that the
relation
(2G-3) B(u, v) ⇐⇒ u v v (v is equal to or below u)
is recursive in Ts .
Tiuryn [1989] proves that B(u, v) is not tail recursive in Ts .
x2G.3. Problem. Prove that in the structure T of Theorem 2G.1, the (par-
tial) function
White(u) = if there exists a white leaf below u then tt else ↑
is computed by a nondeterministic register program but not by any determi-
nistic one. Hint: Use a variation of the proof of Theorem 2G.1.
The corresponding problem for total functions is (as far as I know) open:
x2G.4. Open problem. Define a total, pointed structure A and a total func-
tion f : An → B which is computed by a nondeterministic register program
but not by any deterministic one.
2H. What is an algorithm? 99
24 Using imprecise formulations of the Church-Turing Thesis and vague references to Church
[1935], [1936] and Turing [1936], it is sometimes claimed naively that algorithms are Turing
machines. This does not accord with the original formulations of the Church-Turing Thesis, cf. the
discussion in Section 1.1 of Moschovakis [2014] (which repeats points well known and understood
by those who have thought about this matter); and as we mentioned in the Introduction, it is not
a useful assumption.
100 2. Recursive (McCarthy) programs
There is also the restriction to first-order primitives, partial functions and
relations. This is necessary for the development of a conventional theory of
complexity, but recursion and computability from higher type primitives have
been extensively studied: see Kleene [1959], Kechris and Moschovakis [1977]
and Sacks [1990] for the higher-type recursion which extends directly the
first-order notion we have adopted, and Longley and Normann [2015] for a
near-complete exposition of the many and different approaches to the topic.25
Once we focus on algorithms which compute partial functions (2H-1) from
the primitives of a Φ-structure, then the problem of defining them rigorously
comes down basically to choosing between iterative algorithms specified by
computation models as in Section 2C and elementary recursive algorithms
expressed directly by recursive programs; at least this is my view, which I have
explained and defended as best I can in Section 3 of Moschovakis [1998].
The first of these choices—that algorithms are iterative processes—is the
standard view, explicitly or implicitly adopted (sometimes with additional re-
strictions) by most mathematicians and computer scientists, including Knuth
in Section 1.1 of his classic Knuth [1973]. More recently (and substantially
more abstractly, on arbitrary structures), this standard view has been devel-
oped, advocated and defended by Gurevich and his collaborators, cf. Gure-
vich [1995], [2000] and Dershowitz and Gurevich [2008]; see also Tucker and
Zucker [2000] and Dužı́ [2014].
I have made the second choice, that algorithms (which compute partial
functions from the primitives of a Φ-structure A) are directly expressed by
recursive programs, and I have developed and defended this view in several
papers, most carefully in Moschovakis [1998].
With the notation in Section 2A, my understanding of the algorithm ex-
pressed by an extended recursive Φ-program
n o
E(~x) ≡ E0 (~x) where p1 (~x1 ) = E1 , . . . , pK (~xK ) = EK
in a Φ-structure A is that it calls for solving in A the system of recursive
equations in the body of E(~x) and then plugging the solutions in its head to
compute for each x ~ ∈ An the value den(A, E(~ x )); how we find the canoni-
cal solutions of this system is not part of the elementary recursive algorithm
expressed by E(~x) in this view, and this raises some obvious questions:
About implementations (II). To compute den(A, E(~ x )) in specific cases, we
might use the method outlined in the proof of the Fixed Point Lemma 1B.1, or
the recursive machine defined in Section 2C or any one of several well known
and much studied implementations of recursion. These are iterative algorithms
which (generally) use fresh primitives and should satisfy additional properties,
25 See also Moschovakis [1989a]—which is about recursion on structures with arbitrary
monotone functionals for primitives—and the subsequent Moschovakis [1989b] where the rele-
vant notion of algorithm from higher-type primitives is modeled rigorously.
2H. What is an algorithm? 101
103
104 3. Complexity theory for recursive programs
where pk1 , . . . , pkK are the iterates of the system that defines M as in the proof
of the Fixed Point Lemma, Theorem 1B.1. We define D(M ) by recursion on
k
(3A-5) stage(M ) = the least k such that M ↓ ,
and recursion on the length of terms within this. We consider cases on the
form of M .
(D1) If M is tt, ff, x ∈ A or a convergent, nullary constant, set D(M ) = 0.
(D2) If M ≡ φ(M1 , . . . , Mm ) for some φ ∈ Φ and M ↓ , then
stage(M ) = max{stage(M1 ), . . . , stage(Mm )},
and these subterms are all smaller than M , so we may assume that D(Mi ) is
defined for i = 1, . . . , m; we set
D(M ) = max{D(M1 ), . . . , D(Mm )} + 1.
(D3) If M ≡ if M0 then M1 else M2 and M ↓ , then either M 0 = tt, M 1 ↓
and stage(M ) = max{stage(M0 ), stage(M1 )} or the corresponding conditions
hold with M0 and M2 . In either case, the terms M0 , Mi are proper subterms
of M , and we can assume that D is defined for them and define D(M )
appropriately as in case (D2).
(D4) If M ≡ p(M1 , . . . , Mm ) with a recursive variable p of E, M ↓ and
k = stage(M ), then
k k k
M = pk (M 1 , . . . , M m )↓ ,
and so stage(Mi ) ≤ k and we can assume that D(Mi ) is defined for i =
1, . . . , n, since these terms are smaller than M . Moreover, if M 1 = w1 , . . . ,
M m = wm , then
pk (w1 , . . . , wm ) = den((A, pk−1
1 , . . . , pk−1
K ), Ep (w1 , . . . , wm ))↓
tt ff x φ φ(M1 , . . . , Mn )
^ q
M1 M2 ... Mn
= ^ R
M0 M1 M0 M2
p(M1 , . . . , Mn )
) = s z
?
M1 M2 ... Mn Ep (M 1 , . . . , M n )
(T 4) If M ≡ p(M1 , . . . , Mm ), set
T (M ) = Top(M, T (M1 ), . . . , T (Mm ), T (Ep (M 1 , . . . , M m ))).
(4) is somewhat stronger than (3) and simpler, which makes it (perhaps)
worth proving, although this involves some seemingly unavoidable computa-
tions.
By Problem x3A.11 a stronger inequality holds when ` = 1, so we assume
that ` ≥ 2 and proceed again by induction on D(M ).
Case 1. D(M ) ≤ 1. In this case M is tt, ff, a parameter x ∈ A or a nullary
p
constant φ, so that Lp (M ) = Ls (M ) ≤ 1 ≤ (` + 1)L (M ) .
Case 2, M ≡ φ(M1 , . . . , Mn ). The induction hypothesis gives us the result
for M1 , . . . , Mn , and we compute:
Ls (M ) = Ls (M1 ) + · · · + Ls (Mn ) + 1
p p
(M1 ) (Mn )
≤ (` + 1)L + · · · + (` + 1)L +1
≤ `(` + 1)A + 1 (A = max{Lp (M1 ), . . . , Lp (Mn )})
p
(M )
≤ `(` + 1)A + (` + 1)A = (` + 1)A+1 = (` + 1)L .
Case 3, M ≡ if M0 then M1 else M2 . The argument is very similar to Case
2 and we skip it.
Case 4, M ≡ p(M1 , . . . , Mn ). Now
Ls (M ) = Ls (M1 ) + · · · + Ls (Mn ) + Ls (Ep (M 1 , . . . , M n )) + 1.
If Lp (M1 ) = · · · = Lp (Mn ) = 0, then each Mi is a truth value or a parameter
x, so their sequential logical complexities are also = 0, and then, using the
induction hypothesis:
Ls (M ) = Ls (Ep (M 1 , . . . , M n )) + 1
p
(Ep (M 1 ,... ,M n ))
≤ (` + 1)L +1
Lp (Ep (M 1 ,... ,M n ))+1 p
(M )
≤ (` + 1) = (` + 1)L .
In the opposite case, setting
A = max{Lp (M1 ), . . . , Lp (Mn )} ≥ 1, B = Lp (Ep (M 1 , . . . , M n )),
we can compute as above:
Ls (M ) = Ls (M1 ) + · · · + Ls (Mn ) + Ls (Ei (M 1 , . . . , M n )) + 1
p p
≤ (` + 1)L (M1 ) + · · · + (` + 1)L (Mn )
+ (` + 1)B + 1
≤ `(` + 1)A + (` + 1)B+1 ,
and it suffices to prove that for all A ≥ 1 and all B ∈ N,
`(` + 1)A + (` + 1)B+1 ≤ (` + 1)A+B+1 ;
but this inequality is equivalent to
` 1
+ ≤ 1,
(` + 1)B+1 (` + 1)A
110 3. Complexity theory for recursive programs
a somewhat smaller measure which counts only the number of distinct calls
to the primitives in Φ0 .
C s (M ) can be easily read off the computation tree T (M ) and also off the
computation of the recursive machine starting with M : , Problems x3A.13
and x3A.14.
The depth-of-calls complexity C p (Φ0 )(M ). Fix again a Φ-structure A, a
subset Φ0 ⊆ Φ of the vocabulary and an extended Φ-program E(~x). The
depth of calls to Φ0
C p (Φ0 )(M ) = C p (Φ0 )(A, E, M )
of any M ∈ Conv(A, E) is defined by the following recursion on D(M ):
(C p 1) C p (Φ0 )(tt) = C p (Φ0 )(ff) = C p (Φ0 )(x) = 0 (x ∈ A); and for
nullary constants, C p (Φ0 )(φ) = 0 if φ ∈ / Φ0 , and C p (Φ0 )(φ) = 1
if φ ∈ Φ0 .
(C p 2) If M ≡ φ(M1 , . . . , Mn ), then
(
max{C p (Φ0 )(M1 ), . . . , C p (Φ0 )(Mn )} + 1, if φ ∈ Φ0 ,
C p (Φ0 )(M ) =
max{C p (Φ0 )(M1 ), . . . , C p (Φ0 )(Mn )}, otherwise.
(C p 3) If M ≡ if M0 then M1 else M2 , then
(
max{C p (Φ0 )(M0 ), C p (Φ0 )(M1 )}, if M 0 = tt,
C p (Φ0 )(M ) =
max{C p (Φ0 )(M0 ), C p (Φ0 )(M2 )}, if M 0 = ff.
(C p 4) If M ≡ p(M1 , . . . , Mn ) of E with p a recursive variable of E, then
C p (Φ0 )(M ) = max{C p (Φ0 )(M1 ), . . . , C p (Φ0 )(Mn )}
+ C p (Φ0 )(Ep (M 1 , . . . , M n )
The depth of calls to Φ0 of E in A is that of its head term,
(3A-13) c p (Φ0 )(~
x ) = c p (Φ0 )(A, E(~
x )) =df C p (Φ0 )(A, E0 (~
x )),
and again, we skip the subscript when it is Φ,
(C p , c p ) C p (M ) = C p (Φ))(M ), c p (~
x ) = c p (Φ)(~
x ).
Intuitively, the number C p (Φ0 )(M ) counts the maximal number of calls
to the primitives in Φ0 that must be executed in sequence in any computation
of M by (any implementation of) E. It is more directly relevant to parallel
implementations—which is why we will sometimes call it the parallel calls
complexity. It is not as easy to read it from T (M ), however, which assumes
not only parallelism but (potentially infinite) nondeterminism. In the key
recursive calls p(M1 , . . . , Mn ), for example, we put the children on the same
level,
M1 , . . . , Mn , Ep (M 1 , . . . , M n )
112 3. Complexity theory for recursive programs
so that the depth of the tree is one more than the maximum of the depths
of the trees for these terms; but M 1 , . . . , M n must be computed before the
computation of the rightmost child can be (realistically) started,27 which is
why we set
C p (Φ0 )(p(M1 , . . . , Mn ))
= max{C p (Φ0 )(M1 ), . . . , C p (Φ0 )(Mn )} + C p (Φ0 )(Ep (M 1 , . . . , M n )).
C p (Φ0 )(M ) is also not easy to read off the computation of the recursive
machine starting with M : , for a different reason: it is a measure of parallel
complexity and the recursive machine is decidedly sequential.
The complexity measure c p (~ x ) is majorized by all natural complexity mea-
sures of all reasonable implementations of recursive programs, and so lower
bound results about it have wide applicability. Most of the lower bounds for
problems in arithmetic we will derive in Part II are for a related “intrinsic”
complexity measure, somewhat smaller than c p (~ x ).
x3A.1. Problem. Make precise and prove that all five of the complexity
functions we introduced for recursive programs are preserved under isomor-
phisms.
For example, if ð : A → B is an isomorphism of one Φ-structure onto
another, N (~y) is a pure voc(E)-term and y ~ ∈ An , then
A |= N (~
y ) = w =⇒ B |= N (ð(~ y )) = ð(w)
& C s (Φ0 )(A, E, N (~
y )) = C s (Φ0 )(B, E, N (ð(~
y ))) .
Hint: Prove this first for the tree-depth complexity D(M ).
x3A.2∗ . Problem. Prove (3A-9), that for each program E, there is a number
C = CE such that for every M ∈ Conv(A, E),
Ls (M ) ≤ TimeA,E (M ) ≤ Ls (M ) + C.
Hint: For the second, non-trivial inequality, prove that for every pure,
~ ∈ Am ,
extended voc(E)-term N (~y), there is a number CN such that for all y
y )↓ =⇒ Ls (M ) ≤ Time(M ) + CN .
M = N (~
The next problem is a more detailed version of Theorem 2C.1, which re-
lates the time complexity of an iterator in (2C-4) with the sequential calls-
complexity of the associated tail recursive program.
27 This leaves out so-called call-by-need implementations, a variety of call-by-name implemen-
x3A.3. Problem. Prove that for each iterator i and the associated recursive
program E ≡ Ei on A = Ai and for all x ∈ X ,
i(x) = den(Ai , Ei (x)),
s
c (Ai , Ei (x)) = 2 Timei (x) − 1.
Hint: Prove that if
n o
p(input(~x)) where p(~u) = if test(~u) then output(~u) else p(ó(~u))
is the tail recursive program which computes i(x) in Ai , then for every state s
of i and n ≥ 1,
p(s) : ↓ & C s (p(s)) = 2n
⇐⇒ there is a convergent computation (s1 , . . . , sn ) of i with s = s1 .
This exact relation between the time complexity of i and the number-of-
calls complexity of the associated recursive program Ei reflects some specific
choices we made in how we count Timei and it is not of any particular interest;
on the other hand, we would expect that any “natural” complexity measure
Ti (x) of an iterator i is “coded” in Ei , in the sense that
Ti (x) = Θ(C (Ai , Ei (x)))
for some “natural” complexity measure on recursive programs. This is one
version of the claim that algorithms can be faithfully expressed by recursive
programs on which we have been harping.
x3A.4. Problem. Prove that for each extended Φ-program with empty body
E(~x) ≡ E(~x) where { } (a Φ-term), there is a number CE such that for every
Φ-structure A and x~ ∈ An ,
x )↓ =⇒ lEs (~
A |= E(~ x ) ≤ CE .
Hint: Take CE to be any reasonable definition of the length of E.
x3A.5. Problem. Prove that the following are equivalent for any structure
A and M ∈ Conv(A, E):
(i) C p (M ) = 0.
(ii) Ls (M ) = 0.
(iii) The value M is independent of the primitives of A, i.e., for any Φ-
structure A0 = (A, Υ0 ) with the same universe
den(A, E, M ) = den(A0 , E, M ).
(iv) There are no Φ-nodes in the computation tree T (M ).
We will sometimes appeal silently to this simple observation to simplify
formulas, for example by dividing by c p (A, E(~ x )) or using it in the form
x )) ≥ 1 when the value denA
c p (A, E(~ E (~
x ) obviously depends on the primitives
of A.
114 3. Complexity theory for recursive programs
(D2) M ≡ φ(M1 , . . . , Mm ) ≡ N (~
x ) with N (~x) ≡ φ(N1 (~x), . . . , Nm (~x)).
Now D(Mi ) < k = D(M ), so we can set
x ) = φ A (fN1 ,k−1 (~
fN,k (~ x ), . . . , fN2 ,k−1 (~
x )).
(D3) where M is defined by branching is handled similarly.
(D4) Taking m = 2 again,
M ≡ p(M1 , M2 ) ≡ p(N1 (~
x ), N2 (~
x ))
for a recursive variable p of E and
M = den(A, Ep (M 1 , M 2 ));
now D(M1 ), D(M2 ), D(Ep (M 1 , M 2 )) < D(M ), so we can use the induction
hypothesis and set
fN,k (~
x ) = fEp ,k−1 (fN1 ,k−1 (~
x ), fN2 ,k−1 (~
x )). a (Lemma 2)
To prove (1) with f(~ x ) = den(A, E(~
x )), we note that a uniform bound on
d (~
x ) gives a uniform bound k for stage(~x ) for x
~ ∈ S by Lemma 1; and then
Lemma 2 gives an explicit definition for f(~ x ) on S. a
Tserunyan’s inequalities. The constants in Proposition 3B.1 depend only on
Φ and the total arity of a program which computes some f : An * As in any
Φ-structure A, and their proofs were quite simple. Less obvious is that for any
program E, there are constants Ks , Kp such that for every Φ-structure A, if
den(A, x ~ )↓ , then
(3B-2) (a) lEs (~
x ) ≤ Ks + Ks cEs (~
x ), (b) lEp (~
x ) ≤ Kp + Kp cEp (~
x ),
i.e., in both the sequential and the parallel measures, counting the logical steps
in addition to the calls to the primitives produces at most a linear increase in
complexity. From the point of view of deriving lower bounds, the significance
of these inequalities becomes evident if we reverse them:
1 s 1 p
(3B-3) (a) cEs (~
x) ≥ (l (~
x ) − Ks ), (b) cEp (~
x) ≥ (l (~
x ) − Kp ).
Ks E Kp E
Here (a) means that the high sequential complexity of a f : An * As from
specified primitives is not caused by the large number of logical operations
that we must execute to compute f(~ x )—i.e., (literally) by the “computational
complexity” of f—but is due to the large number of calls to the primitives
that are necessary to compute f(~ x ), at least up to a linear factor. Ditto for
the parallel complexity lEp (~
x ) and its “calls-counting” counterpart cEp (~x ). It
is another manifestation of the fact that lower bound results are most often
proved by counting calls to the primitives, which is well known and little
understood; and, incidentally, it emphasizes the importance of identifying all
the (non-logical) primitives that are used by an algorithm which computes a
particular function.
118 3. Complexity theory for recursive programs
The proofs of these inequalities require some new ideas and are due to
Anush Tserunyan.28
We fix a Φ-structure A and a recursive program E with recursive variables
p1 , . . . , pK and total arity ` = `(E) ≥ 1. We can insure that
then H is an overall upper bound to the number of terms that can be con-
structed by a single assignment of parameters to the variables in all the sub-
terms of E.
We start with some preliminary estimates which are needed for the proofs
of both inequalities in (3B-2).
3B.3. Lemma. If M ∈ Conv(A, E) and C p (M ) = 0, then either M ∈ B or
M occurs in M .
28 The results in the remainder of this section are due to Anush Tserunyan, Part (3) of her
P
F s (M ) = F s (M1 ) + · · · + F s (Mm+1 ) = 1≤i≤m+1,j<ki F s (Nji )
as required, again because M is not splitting. a
3B. Complexity inequalities 121
induction hypothesis applies to it since it is not M and hence D(N ) < D(M ),
and we have
Lp (M ) ≤ Lp (N ) + |v(M )| ≤ (2V + 1)F p (N ) + V
by (3B-4) again, as required. a
3B.13. Corollary. (1) For every Φ-program E, there is are constants K1 , K2
such that for every Φ-structure A, if (denA
E (~
x )↓ ), then
p p
(~
x) (~
x)
(3B-10) x ) ≤ K1c
c s (~ x ) ≤ K2c
and l s (~ .
(2) If an extended Φ-program E(x) ~ computes f : An * As in a structure
A and one of the complexities d (~ x ), c p (~
x ), c s (~
x ), l p (~
x ), l s (~
x ) is bounded on
the domain of convergence of f, then they are all bounded—and Theorem 3B.2
applies, so f(~ x ) is explicit if A is reasonably well behaved.
Proof. (1) Notice that these inequalities hold with any K > 0 if c p (~ x ) = 0,
because in that case l s (~ x ) = 0 by Problem x3A.5, and then c s (~ x ) = 0 because
c s (~ x ). So we fix a structure A and we compute, assuming denA
x ) ≤ l s (~ E (~
x )↓
p
and c (~ x ) > 0:
For the second inequality,
p
(~
x)
l s (~
x ) ≤ (` + 1)l (Theorem 3A.3)
Kp +Kp c p (~
x)
≤ (` + 1) (Theorem 3B.12)
c p (~x )
≤ (` + 1)2Kp ;
and for the first, we start with c s (~
x ) ≤ l s (~
x ) and use the second one.
(2) If d (~
x ) is bounded, then all five complexities are bounded by Propo-
sition 3B.1; and if c p (~
x ) is bounded, then l s (~ x ) is bounded by (1) and then
d (~
x ) is bounded by Proposition 3B.1 again. This covers all possibilities. a
Full vs. tail recursion (II). In Section 2G we described several examples of
(pointed) structures in which not every recursive function is tail recursive. A
related—perhaps more interesting—question is about the relative complexities
of full and tail recursive definitions of the same function, and the best result I
know about this is the following:
3B.14. Theorem (Bhaskar [2017]). For every function g : N → N, there is
an increasing function ã : N → N with the following properties, where
n
A = (NPd , ã) = (N, 0, 1, Pd, eq0 , ã) and f(n, x) = ã 2 (x).
(1) Tailrec0 (A) = Rec0 (A).
(2) There is an extended recursive program E which computes f in A with
sequential logical complexity (time)
l s (A, E(n, x)) = O(2n ).
(3) The function f is tail recursive in A.
3B. Complexity inequalities 125
(4) For every extended tail recursive program F of A which computes f, there
are increasing sequences {ni }, {xi } such that for all i,
l s (A, F (ni , xi )) ≥ g(ni ).
Questions about intensional—especially complexity—differences between
programs which compute the same function from the same primitives were an
important part of schematology from the very beginning. My own interest in
these problems was stimulated by the remarkable theorem in Colson [1991],
whose call-by-value version (due to Fredholm [1995]) and with the natural
understanding of the terminology has the following, dramatic consequence:
3B.15. Colson’s Corollary. If a primitive recursive definition of the minimum
function on N is expressed faithfully in a programming language, then one of
the two computations of min(1, 1000) and min(1000, 1) will take at least 1000
steps.
The point is that the simple (tail) recursive program which computes
min(x, y) in Nu in time O(min(x, y)) cannot be matched in efficiency by a
primitive recursive one, even though min(x, y) is a primitive recursive func-
tion; and so, as a practical and (especially) a foundational matter, we need to
consider “recursive schemes” more general than primitive recursion, even if,
ultimately, we are only interested in primitive recursive functions.
Moschovakis [2003] extends the results of Colson and Fredholm to primi-
tive recursive programs from arbitrary Presburger primitives using gcd(x, y)
rather than min(x, y) and then asks if the same gap in efficiency occurs between
tail and full recursion in the Presburger structure (1E-10), cf. Open Prob-
lem x3B.2.29 The corresponding question about Nu in Open Problem x3B.3 is
(I think) the most important problem in this area.
x3B.1. Open problem. Can a complexity gap like that in Theorem 3B.14 be
realized by a relation R rather than a function f : N2 → N? For a precise
version: is there a total, pointed structure A and an n-ary relation R on A
such that the following hold:
(1) Tailrec0 (A) = Rec0 (A).
(2) R is tail recursive in A.
(3) Some extended program E decides R in A so that for every tail recursive
F which also decides R, there is a sequence {~
x }n of inputs such that
limn→∞ l s (A, F (~
xn )) = ∞ & (∀n)[l s (A, F (~ xn )))2 ].
xn )) ≥ (l s (A, E(~
29 van den Dries [2003] answered another question in this paper, and this started the collabo-
ration which led to van den Dries and Moschovakis [2004], [2009] and eventually to many of the
results in Chapters 5 – 8 of this book.
126 3. Complexity theory for recursive programs
x3B.2. Open problem. Can a complexity gap between tail and full recursion
like that in Theorem 3B.14 or Open Problem x3B.1 be realized in the Presburger
structure?
x3B.3. Open problem. Can a complexity gap between tail and full recursion
like that in Theorem 3B.14 or Open Problem x3B.2 be realized in unary
arithmetic Nu or in the List structure L∗ ?
Part II. Intrinsic complexity
CHAPTER 4
Most of the known lower bound results in the literature are established for
specific computation models and the natural complexity measures associated
with them, and so any claim that they are absolute—or even that they hold
for a great variety of models—must be inferred from the proofs. The results
about recursive programs in van den Dries and Moschovakis [2004], [2009]
are somewhat more robust: they are proved directly from the abstract def-
initions of complexities in Chapter 3 using basically nothing more than the
homomorphism and finiteness properties in Problems x2E.2, x2E.4, without
reference to the recursive machine or any other implementations of recursive
programs. They imply lower bounds for most computation models, because
of the representation of iterators by tail recursive programs in Theorem 2C.1,
the complexity refinement of it in Problem x3A.3 (and the discussion after it)
and what comes next.
Our main aim in this chapter is to extract from the homomorphism and
finiteness properties of nondeterministic recursive programs in Problems x2E.2
and x2E.4 a general, algebraic method for deriving robust lower bounds for
algorithms from specified primitives assuming very little about what these
objects are.30
The key notions are those of a uniform process and certification in Sec-
tions 4B and 4D and the main result is the Homomorphism Test, Lemma 4E.3.
We will start, however, with a brief discussion of “algorithms from primitives”
which motivates our choice of notions without assuming any specific, rigorous
definition of “what algorithms are”.
The basic intuition is that an n-ary algorithm of sort s from the primitives of
a structure A = (A, Υ) computes (in some one or in many different ways) an
30 Itis sometimes doubted whether it makes sense to talk of nondeterministic algorithms from
specified primitives, and with good reason. Here, it is useful to assume that it does: the precise
results will be stated about nondeterministic recursive programs and are not affected by surrounding
loose talk.
129
130 4. The homomorphism method
definition of substructures on page 32: it is possible that w ∈ U, φ(w) ∈ U but still φ U (w) ↑.
4A. Uniformity of algorithms 131
The second axiom tries to capture the uniformity of algorithms, that they
follow “the same” procedure on any two inputs x ~ ∈ An . We would expect—
~, y
at the least—that an isomorphism ð : U → V between two substructures
of A induces an isomorphism between the computations of α U and those
of α V ; we postulate something which is weaker, in that it does not refer
to “computations” but stronger in that it requires uniformity for arbitrary
homomorphisms, which need not be injective or surjective:
II. Homomorphism Axiom. If α is the process induced by an algorithm of A
and ð : U → V is a homomorphism of one substructure of A into another, then
(4A-1) x ) = w =⇒ V |= α(ð(~
U |= α(~ x )) = ð(w) x ∈ U n ).
(~
U ⊆p A =⇒ α U v α A = α.
The idea here is that the oracle for each φ A may consistently respond to each
request for φ U (~
u ) by delivering φ V (ð(~
u )). This transforms any computation
U
of α (~x ) into one of α V (ð(~x )), which in the end delivers the value ð(w) =
ð(α U (~
x )).
This argument is convincing for the identity embedding idU : U V
and works for nondeterministic recursive programs, Problem x2E.2. It is not
quite that simple in full generality, because algorithms may employ in their
computations complex data structures and rich primitives, e.g., stacks, queues,
trees, the introduction of higher type objects by ë-abstraction and subsequent
application of these objects to suitable arguments, etc. The claim is that any
homomorphism ð : U → V lifts naturally to these data structures, and so the
image of a convergent computation of α U (~ x ) is a convergent computation of
α V (ð(~
x )). Put another way: if some ð : U → V does not lift naturally to a
mapping of the relevant computations, then the algorithm is using essentially
some hidden primitives not included in A and so it is not an algorithm from
{φ A }φ∈Φ . It is clear, however, that the Homomorphism Axiom demands
something more of algorithms (and how they use oracles) than the Locality
Axiom, and we will discuss it again in Section 4G.
The Homomorphism Axiom is at the heart of this approach to the derivation
of lower bounds.
III. Finiteness Axiom. If α is the process induced by an algorithm of A, then
(4A-2) x ) = w =⇒ U |= α(~
A |= α(~ x) = w
for some finite U ⊆p A which is generated by x
~ ;
132 4. The homomorphism method
This combines two ingredients of the basic intuition: first, that in the course
of a computation the algorithm may only request of the oracles values φ A (~ u)
for arguments in the input x ~ or that it has already computed from x ~ , and
second, that computations are finite. A suitable U is then determined by
putting in eqdiag(U) all the calls made by the algorithm in the computations of
α(~x ).
The Finiteness Axiom implies, in particular, that partial functions com-
puted by an A-algorithm take values in the substructure generated by the
input, since for any process of A which satisfies Axiom III,
α A (~
x ) = w =⇒ w ∈ G∞ (A, x
~ ) ∪ B.
By Problems x2E.2 and x2E.4, axioms I – III are satisfied by nondetermin-
istic recursive algorithms. They also hold for all concrete algorithms expressed
by computation models, e.g., Turing machines, finite register programs, Random
Access machines, decision trees . . . , and their nondeterministic versions; this
can be proved by applying Theorem 2C.1, Proposition 2C.3 and their natural
extensions to the nondeterministic versions of these models, cf. Problem x4B.2.
We can express succinctly the claim that all algorithms satisfy these axioms in
terms of the following basic notion:
A process α of A is uniform if it has the homomorphism and finiteness
properties (4A-1), (4A-2); a partial function f : An * As is uniform in A if it
is defined by a uniform process of A; and we set
n o
Unif(A) = f : An * As : f is uniform in A .
(4C-1) U = Gm (U, x
~ ) ⊆p A & ð : U
→ V ⊆p A
~ ) = ì(V, ð(~
=⇒ ì(U, x x )).
Typical examples are32
depth(U, x
~ ) = min{m : U = Gm (U, x
~ )},
values(U, x
~ ) = |{w ∈ U : (φ, u~ , w) ∈ eqdiag(U) for some φ, u~ }|,
calls(Φ0 )(U, x
~ ) = |eqdiag(U Φ0 )| (Φ0 ⊆ Φ)
which we introduced on page 34 (with Φ0 = Φ for the last one). By Proposi-
tion 1D.1,
(4C-2) depth(U, x
~ ) ≤ values(U, x
~ ) ≤ calls(U, x
~ ).
If ì is a substructure norm on A and α is a uniform process of A, then the
ì-complexity measure of α is the partial function
(4C-3) ~ ) =df min{ì(U, x
ì(α, x ~ ) : U |=c α(~
x )↓ },
defined on the domain of convergence of α A . By using the norms above, we
get three natural complexity measures on uniform processes,
(4C-4) depth(α, x
~ ), values(α, x
~ ), calls(Φ0 )(α, x
~ ).
32 The depth and values norms can also be relativized to arbitrary Φ ⊆ Φ, but it is te-
0
dious, we have no interesting results about them, and we leave the relativization for depth for
Problem x4C.8∗ .
4C. Complexity measures on uniform processes 137
The first and last of these three correspond to familiar complexity measures
with roughly similar names for concrete algorithms but not exactly:33
– The “sequential” measure calls(Φ0 )(α, x ~ ) intuitively counts the least num-
ber of distinct calls to primitives in Φ0 required to define α(~ x ) by the process α,
where (φ, u~ , w) and (φ 0 , u~ 0 , w 0 ) are distinct if either φ 6≡ φ 0 or u~ 6= u~ 0 ;
– the “parallel” measure depth(α, x ~ ) counts the least number of distinct calls
to the primitives of A which must be executed in sequence to define α(~ x ); and
– the less familiar middle measure values(α, x ~ ) counts the least number of
points in A that α must compute from x ~ to define α(~ x ).
These measures are typically lower than their versions for concrete algorithms,
because they count distinct calls and points, while an algorithm may (stupidly
or by design, e.g., to simplify the code) make the same call many times, cf.
Problem x4C.6.
4C.1. Lemma. For every uniform process α of a Φ-structure A and all x ~, w
such that α(~ x ) = w,
(4C-5) depth(α(~
x ); A, x
~ ) ≤ depth(α, x
~ ) ≤ values(α, x
~ ) ≤ calls(α, x
~ ),
where, by our convention, depth(tt, A) = depth(ff, A) = 0.
Proof. The first inequality is trivial if w ∈ B and immediate for w ∈ A,
because if U |=c α(~
x ) = w, then w ∈ U and so
depth(w; A, x
~ ) ≤ depth(w; U, x
~ ) ≤ depth(U, x
~ ).
For the third claimed inequality, suppose α(~ x ) = w and choose a certifi-
cate (U, x~ ) of A with least |eqdiag(U)| such that U |=c α(~ x ) = w, so that
calls(α, x
~ ) = |eqdiag(U)|. Now values(U, x ~ ) ≤ |eqdiag(U)| by (1D-16) in
Proposition 1D.1, and since (U, x ~ ) is among the certificates in A considered
in the definition of values(α, x
~ ), we have
values(α, x
~ ) ≤ |eqdiag(U)| = calls(α, x
~ ).
The second inequality is proved by a similar argument. a
We record for easy reference the relation between these complexity measures
and the complexity measures for programs we studied in Chapter 3, in the two
cases that are most important for the applications:
4C.2. Proposition. Let αE be the uniform process induced on a Φ-structure
A by a nondeterministic extended program E(~x).
(1) If Φ0 ⊆ Φ and den(A, E(~ x ))↓ , then
(4C-6) ~ ) ≤ c s (Φ0 )(A, E(~
calls(Φ0 )(αE , x x )),
33 There are, of course, many other substructure norms which induce useful complexity mea-
sures, including those which come by combining the three basic ones: for example
~ ) · 6depth(U,~x )
~ ) = values(U, x
ì(U, x
comes up naturally in the proof of Theorem 8B.2!
138 4. The homomorphism method
Proof is easy and we leave it for Problems x4C.4, x4C.6 and x4C.7. a
(U, x
~ ) ≈ (V, y
~ ) ⇐⇒ |eqdiag(U)| = |eqdiag(V)|
& (∃ an isomorphism ð : U x) = y
→ V)[ð(~ ~ ],
and prove that ≈ is an equivalence relation with finitely many equivalence
classes.
A A
4D. Forcing and certification c 141
U f(x) ð
ð(f(x))
f f
ð
x ð(x)
Figure 4. ð : U → A respects f : A * A at x.
A A
4D. Forcing and certification c
Next come forcing and certification, the two basic notions of this chapter:
A
U x ) = w ⇐⇒ f(~
f(~ x) = w
& every homomorphism ð : U → A respects f at x
~,
A A
U c x ) = w ⇐⇒ U is finite, generated by x
f(~ ~ &U x ) = w,
f(~
A A
U c x )↓ ⇐⇒ (∃w)[U
f(~ c x ) = w].
f(~
A
If U c x )↓ , we call (U, x
f(~ ~ ) a certificate for f at x
~ in A,
A
U certifies f at x
~ in A ⇐⇒ U c x )↓ .
f(~
A A
We will sometimes write and c for and c when the relevant Φ-
structure is clear from the context and also
U x ) for U
R(~ x ) = tt,
R(~ U x ) for U
¬R(~ x ) = ff
R(~
so that we must have ð(rn+2 ) = 0; and then all the equations in (4D-3) hold
and we have the required ð(x)⊥ ⊥ ð(y).
This is typical: although computations by concrete algorithms define cer-
tificates, they generally do not give minimal certificates.
The connection with Pratt certificates for primality. To the best of my knowl-
edge, certificates were first introduced in Pratt [1975] in his proof that primality
is NP and they have been used extensively since then, primarily to design non-
deterministic algorithms for primality. We are using the term in a related but
different way.
With our terminology, a Pratt certificate for primality in a structure A =
(N, Υ) with universe N is a nondeterministic program E(p) such that
~ ) ≤ c p (A, E(~
depth(A, f, x x )) (f(~
x )↓ ),
~ ) ≥ m.
then ì(A, f, x
Other than the definitions, this is the main—in fact the only—tool we will
use in the sequel to derive intrinsic lower bounds from specified primitives.
The results will be (primarily) about the most important intrinsic complexity
measures, when ì(U, x ~ ) is depth(U, x
~ ), values(U) or calls(Φ0 )(U, x
~ ). We will
use two notations for them:
depthf (A, x~ ) = depth(A, f, x~) = min{depth(U, x~) : U A c f(~ x )↓ },
valuesf (A, x~ ) = values(A, f, x~) = min{values(U) : U A c f(~x )↓ },
callsf (Φ0 )(A, x ~ ) = min{calls(U Φ0 ) : U A
~ ) = calls(Φ0 )(A, f, x c f(~ x )↓ }.
(4E-7) calls(w; A, x
~ ) = min{|eqdiag(U, x
~ )| : U ⊆p A, w ∈ U }
≤ calls(A, f, x
~ ),
cf. Problem x4E.11.
These output complexities provide lower bounds for any reasonable notion
of algorithmic complexity measure which counts (among other things) the
applications of primitives that must be executed (in sequence or altogether),
simply because an algorithm must (at least) construct from the input the value
f(~ x ). This is well understood and used extensively to derive lower bounds
in arithmetic and algebra which are clearly absolute.34 We will consider
some results of this type in Section 5A and also in Chapter 9. The more
sophisticated complexity measure depthf (A, x ~ ) is especially useful when f
takes simple values, e.g., when f is a relation: in this case calls(f(~
x ); A, x
~) = 0
and (4E-6), (4E-7) do not give any information.
Explicit (term) reduction and equivalence. Intrinsic complexities are very
fine measures of information. Sometimes, especially in algebra, we want to
know the exact value ì(A, f, x ~ ), which might be the degree of a polynomial
or the dimension of a space. In other cases, especially in arithmetic, we
may try to computes ì(A, f, x ~ ) up to a factor (a multiplicative constant),
either because the exact value is too difficult to compute or because we only
care for asymptotic estimates of computational complexity. The next, simple
proposition gives a trivial way to relate the standard complexity measures of
two structures when the primitives of one are explicitly definable in the other.
A structure A = (A, Υ) is explicitly reducible to a structure A0 = (A, Φ)
on the same universe if Υ ⊆ Expl(A0 ), and explicitly equivalent to A0 if in
addition Φ ⊆ Expl(A).
34 The
most interesting result of thistype that I know is Theorem 4.1 in van den Dries and
√
Moschovakis [2009], an O log log a -lower bound on depth(gcd(a + 1, b), A, a, b) with A =
(N, 0, 1, +, −, ·, ÷) and (a, b) a Pell pair, cf. page 177. This is due to van den Dries, and it is
the largest lower bound known for the gcd on infinitely many inputs from primitives that include
multiplication. It is not known whether it holds for coprimeness, for which the best known result
is a log log log-lower bound for algebraic decision trees in Mansour, Schieber, and Tiwari [1991a].
4E. Intrinsic complexities of functions and relations 147
The first problem says, in effect, that for any substructure norm, ì(A, f, x
~)
is determined by the value f(~ x ) and the isomorphism type of the substructure
G∞ (A, x~ ) of A generated by x~.
x4E.1∗ . Problem. Suppose that A is a Φ-structure, x ~ ∈ An , and there is
~, y
an isomorphism
ð : G∞ (A, x
~)
→ G∞ (A, y
~)
such that ð(~
x) = y
~ . Prove that for every substructure norm ì on A and every
f : An * As ,
~ ) = ì(A, f, y
ì(A, f, x ~ ).
Hint: Use the fact that substructure norms are respected by isomorphisms
and that the hypothesis is symmetric in x
~ and y
~.
x4E.2. Problem. Prove that every Φ-structure A and f : An * As ,
depth(A, f, x
~ ) ≤ calls(A, f, x
~ ) (f(~
x )↓ ).
x4E.3. Problem (Obstruction to calls(A, R, x ~ ) = 0). Suppose R(~x ) is a (to-
tal) n-ary relation on the universe of a Φ-structure A and for some tuple x~ ∈ An
of distinct elements of A, calls(A, R, x~ ) = 0. Prove that R is constant, i.e.,
either (∀~
y )R(~
y ) or (∀~
y )¬R(~
y ).
This allows us in most cases to see immediately that callsf (A, x ~ ) > 0:
for example, calls(A, Prime, x) > 0 for every A with A = N and for every
x, simply because there are primes and composites. There is no equally
simple, general test for depth(A, f, x
~ ) > 0, but it is worth putting down some
sufficient conditions which are easy to verify in special cases—we will need
them in Chapters 5 – 8 when we want to divide by depth(A, f, x ~ ).
148 4. The homomorphism method
Hint: For the counterexamples in (2) use a structure where Graphf is among
the primitives; and for (4), you need a specific such example which keeps
~ ) finite.
ì(A, f, x
x4E.8. Problem. Prove that for the coprimeness relation, some K and all
t ≥ 3,
depth(Nε , ⊥
⊥ , Ft+1 , Ft ) ≤ K (log t) = O(log log Ft ),
where F0 , F1 , . . . is the Fibonacci sequence. Hint: Use Pratt’s algorithm.
x4E.9∗ . Problem. Prove that if f : An * As is explicit in a Φ-structure A
and ì is any substructure norm on A, then there is a number K such that
~) ≤ K
ì(A, f, x (f(~
x )↓ ).
Hint: Use Proposition x1E.14 to prove that for explicit f, there is an m
such that
x ) = w =⇒ (∃U)[U |=c f(~
f(~ x ) = w & |eqdiag(U)| ≤ m],
and then appeal to Problem x4C.12∗ .
x4E.10∗ . Problem. Prove Proposition 4E.4. Hint: Start by appealing to
Problem x4E.9∗ to set
Kφ = max{ì(A0 , φ A , x
~ ) : φ ∈ Φ}.
x4E.11. Problem. Prove (4E-7).
x4E.12. Open problem (vague). For a (total) structure A and a function
f : An → As , do any of the complexity functions ì(A, f, x
~ ) encode interesting
model theoretic properties of A? Perhaps when ì is one of depth, values or
calls and f(~
x ) codes an invariant of some substructure of A determined by
~ —a degree, dimension, etc.
x
For some of these results, the set D is not of any particular interest and we
abstract it away:
(3) A uniform process α on A is weakly ì-optimal for f if it is weakly-ì-
optimal on some D ⊆ An such that
(4F-4) sup{ì(A, f, x
~) : x
~ ∈ D} = ∞.
One precise version of the Main Conjecture on page 2 claims something
stronger than the weak calls(rem)-optimality of (the process) ε (induced by)
the Euclidean in Nε : it asks for a set D ⊆ N2 and a K > 0 such that
(4F-5) (x, y) ∈ D =⇒
calls(rem)(ε, x, y) ≤ L(x, y) ≤ K calls(rem)(A, gcd, x, y)
where L(x, y) = 2 log(max(x, y)); which then satisfies (4F-3) and (4F-4)
by (∗) on page 2. Most of the results in Chapters 5 – 8 establish the weak depth-
optimality of some recursive algorithms which compute various arithmetical
functions and relations from various primitives in this enhanced form, proving
that
~ ∈ den =⇒ ì(α, x
x ~ ) ≤ KL(~
x ) ≤ ì(A, f, x
~) (K > 0)
p
with some interesting L(~ x )— log(x), log log(x), log log(x), etc.
Other than that, weak optimality looks like a very weak condition on
processes, but it is not, cf. Problem x4F.3∗ .
x4F.2. Problem. Prove that if α is (the process induced by) the Euclidean
algorithm in Nε , then
(for infinitely many x, y)[x > y & calls(rem)(x, y) ≤ 1].
(This trivial fact is why the definition of weak optimality demands (4F-4) of
D.)
x4F.3∗ . Problem. Suppose α is a uniform process of A which defines a total
function f : An * As . Prove that if α is not weakly ì-optimal for f, then for
every rational r > 0, there exists a set E ( An and a number m such that
(4F-6) sup{ì(α, x
~) : x
~ ∈ E} ≤ m & (∀~
x∈ ~ ) ≤ rì(α, x
/ E)[ì(A, f, x ~ )].
the connection with the logical notions in Tarski [1986] was pointed out in a footnote. The
definition and (a version of) Lemma 4G.2 below are due to Itay Neeman and they were used to
simplify considerably both the statements and the proofs of the lower bound results about RAMs
in that paper, but the notion deserves the fancier name—it has legs.
4G. Logical extensions 153
version of this fact: we will show (in part) that if =A is among the primitives
of A, then lower bounds for intrinsic complexities which hold in A persist in all
its logical extensions—in a precise and very general way.
First, however, we prove a very simple application of logical extensions
which uses nothing but their definition:
The lower bound for comparison sorting. One of the few lower bound
results that is regularly taught in undergraduate courses on algorithms is
that “Ω(n log n) comparisons are [on some input] necessary for sorting n ele-
ments” in the eloquent formulation of Dasgupta, Papadimitriou, and Vazi-
rani [2011, 2.3], which also notes that [their] “neat argument applies only to
algorithms that use comparisons”. We give here a version of the usual proof
which is based on a precise definition of the “comparison algorithms” for
which it works in terms of logical extensions.
4G.1. Theorem (Lower bound for sorting). Suppose
• ≤ is a linear ordering of a set L which has at least n ≥ 2 elements;
• B = (B, ≤, {ø B }ø∈Ψ ) is a logical extension of (L, ≤) which contains the
set of strings from L, L∗ ⊆ B;
• E(u) is an extended (deterministic) recursive program in the vocabulary
of B which computes sort≤ (u) for every u ∈ L∗ ; and
• c s (≤)(u) = c s (≤)(B, E(u)) is the number of ≤-calls complexity of E(u)
in B;
then there is some u ∈ L∗ of length n such that c s (≤)(u) ≥ log(n!).
Proof is by way of two Lemmas:
Lemma 1. For every ordering ≤0 of L, E(v) computes
sort≤0 : Ln → Ln
in every structure B0 = (B, ≤0 , {ø B }ø∈Ψ ) derived from B by replacing ≤ by ≤0 .
Proof. Fix a set X ⊆ L with exactly n members and let ð : L
→ L be the
unique permutation of L such that
s, t ∈ X =⇒ s ≤ t ⇐⇒ ð(s) ≤0 ð(t) and s ∈
/ X =⇒ ð(s) = s.
Since B is a logical extension of (L, ≤), ð can be extended to a permutation of
B which respects the fresh primitives, and so it is an isomorphism
→ (B, ≤0 X, {ø B }ø∈Ψ ) = B0 .
ð : B = (B, ≤ X, {ø B }ø∈Ψ )
The hypothesis on the extended program E(u) is that
B |= E(u) = sort≤ (u);
so Problem x3A.1 implies that if u ∈ X n , then
B0 |= E(ð(u)) = ð(sort≤ (u)) = sort≤0 (ð(u));
154 4. The homomorphism method
and if we set in this u = ð−1 (v) for any v ∈ X n , we get the required
(4G-2) B0 |= E(v) = ð(sort≤ (ð−1 (v)) = sort≤0 (v). a (Lemma 1)
Problem x3A.1 also gives the following equation on the complexity mea-
sures,
(4G-3) c s (≤0 )(B0 , E(v)) = c s (≤)(B, E(ð−1 (v))),
which we now use:
Lemma 2. Fix a tuple v = (v1 , . . . , vn ) ∈ X n of distinct members of X and
consider the computations of the recursive machine for E(v) with respect to all
orderings ≤ of X ; there is at least one such ≤ for which
c s (≤)(B, E(v)) ≥ log(n!).
The log(n!) lower bound does not hold for non-deterministic programs, cf.
Problem x4G.6.
Embedding Test. The most important applications of logical extensions to
complexity theory derive from the following basic fact:
4G.2. Lemma (Neeman, cf. Footnote 35). If B is logical over an infinite
structure A, V ⊆p B, and
(4G-4) U = V Φ A ⊆p A,
then for every finite X ⊆ U and every k,
(1) Gk (V, X ) ∩ A = Gk (U, X ), and
(2) if ðA : A → A and ðB → B are as in (LE3) above and ðA fixes every
B
s ∈ Gk (U, X ), then ð fixes every t ∈ Gk (V, X ).
~ ∈ An ,
It follows that for all x
(4G-5) (V, x
~ ) is a certificate in B =⇒ (U, x
~ ) is a certificate in A.
4G. Logical extensions 155
Proof. We prove (1) and (2) together by induction on k, the basis being
trivial since
G0 (U, X ) = G0 (V, X ) = X.
At the induction step, we assume (1) and (2) for k.
To prove (2) first at k + 1, suppose ðA fixes every s ∈ Gk+1 (U, X ) and
t ∈ Gk+1 (V, X ). If
t = φ V (z1 , . . . , zn ) = φ B (~z ) with φ ∈ Φ and z1 , . . . , zn ∈ Gk (V, X ),
then z1 , . . . , zn ∈ A, since φ B (~z ) = φ A (~z ) ↓ ; so z1 , . . . , zn ∈ Gk (U, X ) by
(1) of the induction hypothesis; so t ∈ Gk+1 (U, X ) and ðB fixes it by the
hypothesis. If
t = ø V (~
z ) = ø B (~z ) with z1 , . . . , zn ∈ Gk (V, X ),
then using the properties of ðB and (2) for k,
ðB (t) = ðB (ø B (~z )) = ø B (ðB (~z )) = ø B (~z ) = t.
To prove (1) at k + 1, suppose there is some t ∈ Gk+1 (V, X ) ∩ A such that
t∈/ Gk+1 (U, X ), so it must be that t = ø V (z1 , . . . , zn ) with a fresh primitive
and z1 , . . . , zn ∈ Gk (V, X ). Choose a permutation ðA : A → A which fixes
every member of Gk (A, X ) but moves t—which exists since Gk (A, X ) is finite
while A is infinite; now ðB (t) = ðA (t) 6= t, which contradicts (2) at k + 1.
Proof of (4G-5). If V = Gk (V, x ~ ) and X = {x1 , . . . , xn }, then
V = Gk (V, x
~ ) = Gk (V, X ), U = Gk (U, x
~ ) = Gk (U, X ),
and the two structures U = Gk (V, x ~ ) Φ A and Gk (U, x
~ ) have the same
universe Gk (V, x
~ ) ∩ A = Gk (U, x
~ ) by (1). They are both Φ-structures; and
for every φ ∈ Φ,
V Φ A |= φ(~z ) = w ⇐⇒ U |= φ(~z ) = w,
because φ = φ A , and so the restrictions of these two partial functions to the
B
·
Nd = (N, Lind ) with Lind = {0, 1, . . . , d, +, − , iqd , =, <}.
(2x1 + r) · y = 2(x1 · y) + r · y,
159
160 5. Lower bounds from Presburger primitives
The members of Bm (~
a ) are natural numbers. In full detail:
x ∈ Bm (~
a ) ⇐⇒ x ∈ N and there exist x0 , . . . , xn ∈ Z
x0 + x1 a 1 + · · · + xn a n
such that x = ,
dm
and for i = 0, . . . , n, |xi | ≤ d 2m .
5A.2. Lemma (Lind -inclusion). For all a~ ∈ Nn and all m:
(1) a1 , . . . , an ∈ Bm (~
a ) ⊆ Bm+1 (~
a ).
5A. Representing the numbers in Gm (Nd , a~ ) 161
(2) For every primitive φ : Nk → N in Lind ,
x1 , . . . , xk ∈ Bm (~
a ) =⇒ φ(x1 , . . . , xk ) ∈ Bm+1 (~
a ).
(3) Gm (~
a ) = Gm (Nd , a~ ) ⊆ Bm (~
a ).
Proof. We take n = 2 to simplify the formulas, the general argument being
only a notational variant.
d m ai
(1) The first inclusion holds because ai = m and the second because
d
x0 + x1 a 1 + x2 a 2 dx0 + dx1 a1 + dx2 a2
=
dm d m+1
and |dxi | ≤ d · d 2m < d 2(m+1) .
(2) Clearly 0, . . . , d ∈ Bm (~
a ) for every m ≥ 1, and so the constants stay in
Bm (~
a ) once they get in.
For addition, let x, y ∈ Bm (~ a ), so
x0 + x1 a 1 + x2 a 2 y0 + y1 a 1 + y2 a 2
x+y = +
dm dm
d (x0 + y0 ) + d (x1 + y1 )a1 +1 +d (x2 + y2 )an
=
d m+1
and the coefficients in the numerator satisfy
|d (xi + yi )| ≤ d (d 2m + d 2m ) ≤ dd 2m+1 = d 2m+2 .
The same works for arithmetic subtraction. Finally, for integer division by d ,
if i = remd (x) < d , then
1 (x0 − id m ) + x1 a1 + x2 a2
iqd (x) = (x − i) = for some 1 ≤ i < d
d d m+1
and this number is in Bm+1 (~a ) as above.
(3) follows immediately from (2), by induction on m. a
5A.3. Proposition (Multiplication from Lind ). For every number a ≥ 2,
1 a2
depth(a 2 ; Nd , a) ≥ log .
log d a+1
Proof. It is enough to show that for a ≥ 2,
1 a2
a 2 ∈ Gm (Nd , a) =⇒ m ≥ log ,
log d a+1
so assume that a 2 ∈ Gm (a). By Lemma 5A.2, there exist x0 , x1 ∈ Z such that
|x0 |, |x1 | ≤ d 2m and
x0 + x1 a
a2 = ,
dm
162 5. Lower bounds from Presburger primitives
x5A.6∗ . Problem. Prove that for every d ≥ 2, there is an r > 0 and infinitely
pairs of numbers (a, b) such that for every d ≥ 2,
depth(rem(a, b); Lind , a, b) > r log(max(a, b)).
Infer that the recursive program for rem(x, y) in Problem x5A.4 is weakly
depth-optimal for rem(x, y) in every Nd . Hint: Use the pairs (a 3 + a, a 2 ).
(Note: It is possible to give an easier proof of an O(log max(a, b)) lower bound
for depthrem (Nd , a, b) using the Homomorphism Test, see Problem x5B.1.
The proof suggested here uses output-depth complexity and requires a simple
divisibility argument. It is due to Tim Hu.)
x5A.7. Problem. Define a weakly depth-optimal program from Lind which
computes the exponential function f(x, y) = x y (with 00 = x 0 = 1).
Using non-trivial number theory. The proof of Theorem 5B.3 used nothing
but the definition of prime numbers, and none of the results about intrinsic
lower bound of number-theoretic relations in the sequel will require much
more. One might expect that truly significant results about primality depend
on deep properties of primes, and it is worth stating here one example of this.
5B.4. Theorem. There are infinitely many primes p, such that every number
whose binary expansion differs from that of p in any one digit is composite.
This was proved by Cohen and Selfridge [1975] and Sun [2000], Tao [2011]
extended it to expansions of numbers relative to any k > 1, and all three
of these papers established much stronger results about the form of primes
with this property, various transformations (other than flipping a digit) which
spoils their primeness, their density relative to the density of primes, etc. Sun
and Tao also observed the obvious complexity implications of the theorem:
to decide correctly whether x is prime, an algorithm which is given its input
x in binary form (and basically nothing else) must read all the digits of x, on
infinitely many inputs. This is usually made precise in terms of boolean circuit
complexity which we have not defined, but a strong version of it is a fact about
the intrinsic calls-complexity of primality in the appropriate structure.
P
If x = j xj 2j (with xi < 2) is the binary expansion of x > 0, let
biti (x) = xi , length(x) = max{i : biti (x) > 0} + 1,
bitboundi (x) ⇐⇒ i ≥ length(x) − 1,
166 5. Lower bounds from Presburger primitives
The method in the preceding section can be easily adapted to derive lower
bound results for many unary relations on N. Some of these are covered by
the next, fairly general notion.
A unary relation R(x) is a good example if for some polynomial
(5C-1) ë(ì) = 1 + l1 ì + l2 ì2 + · · · + ls ìs
with coefficients in N, constant term 1, and degree > 0 and for all ì ≥ 1,
(5C-2) R(x) =⇒ ¬R(ë(ì)x).
For example, primality is good, taking ë(ì) = 1 + ì, and being a power of
2 is good with ë(ì) = 1 + 2ì. We leave for the problems several interesting
results of this type.
x5C.2. Problem (van den Dries and Moschovakis [2004]). Prove that if R(x)
is a good example, then for all a ≥ 2,
1
R(a) =⇒ depthR (Nd , a) ≥ log a.
4 log d
x5C.3. Problem. Prove that if m > 0, then (1+m 2 )n 2 is not a perfect square.
Hint: Prove first that 1 + m 2 is not a perfect square, and then reduce the result
to the case where m⊥ ⊥ n.
x5C.4. Problem. Prove that the following two relations are good examples:
R1 (a) ⇐⇒ a is a perfect square
R2 (a) ⇐⇒ a is square-free.
x5C.5. Problem. Prove that if ë(ì) is as in (5C-1), then there is a constant
C such that
(5C-3) log ë(ì) ≤ C log ì (ì ≥ 2).
The next problem gives a logarithmic lower bound for depthR (Nd , a) with
good R at many points where R(a) fails to hold.
x5C.6. Problem. Suppose R(x) is a good example with associated polyno-
mial ë(ì). Prove that there is a rational constant r > 0, such that for all a ≥ 2
and m ≥ 1,
R(a) =⇒ depthR (Nd , ë(d m+1 )a) ≥ r log(ë(d m+1 )a).
We extend here (mildly) the methods in the preceding section so they apply
to binary functions, and we show the result in the heading.
For the remainder of this section, a, b, c range over N and x, y, z, xi , yi , zi
range over Z.
5D.1. Lemma. Suppose a > 2 and set b = a 2 − 1.
a
(1) a⊥⊥ b, and if |xi |, |yi | < for i = 0, 1, 2 and ë ≥ 1, then
4
x0 + x1 ëa + x2 ëb = y0 + y1 ëa + y2 ëb ⇐⇒ x0 = y0 & x1 = y1 & x2 = y2 ,
x0 + x1 ëa + x2 ëb > y0 + y1 ëa + y2 ëb
⇐⇒ [x0 > y0 & x1 = y1 & x2 = y2 ]
∨ [x1 > y1 & x2 = y2 ] ∨ [x2 > y2 ].
(2) If d 2m+3 < a and ë = 1 + d m+1 , then there is an embedding
ð : Nd Gm (a, b) Nd
such that ða = ëa, ðb = ëb.
5D. Stein’s algorithm is weakly depth-optimal from Lind 169
We now add to the basic primitives of the Presburger structures division with
remainder, i.e., the integer quotient and remainder operations. Set:
·
Lin0 = {0, 1, =, <, +, − }, N0 = (N, Lin0 ),
·
Lin0 [÷] = Lin0 ∪ {iq, rem} = {0, 1, =, <, +, − , iq, rem},
·
N0 [÷] = (N, Lin0 [÷]) = (N, 0, 1, =, <, +, − , iq, rem).
Every expansion of a Presburger structure by division with remainder is obvi-
ously explicitly equivalent to N0 [÷], and so all the results of this chapter apply
to these richer structures with only inessential changes in the constants.
The derivations of absolute lower bounds for unary relations from Lin0 [÷]
is similar to those from Lind in Sections 5B and 5C and we will consider it
first. For binary relations, however, like coprimeness, we need some new ideas
as well as some elementary results from number theory.
The numbers in C (~ a ; h) are said to have height (no more than) h with respect
to a~ , and, trivially,
x ≤ h =⇒ x ∈ C (a; h), h ≤ h 0 =⇒ C (~ a ; h 0 ).
a ; h) ⊆ C (~
We need to estimate how much the height is increased when we perform various
operations on numbers. The results are very simple for the primitives in Lin0 :
171
172 6. Lower bounds from division with remainder
There is no simple, general result of this type for division with remainder,
and in this section we will consider only the simplest case n = 1, when C (a; h)
comprises the numbers of height h with respect to a single a. We start with
the appropriate version of Lemma 5B.1.
6A.2. Lemma (Lin0 [÷]-Uniqueness). If |xi |, |yi | ≤ h for i ≤ 2, ë ≥ 1 and
2h 2 < a, then:
x0 + x1 ëa y0 + y1 ëa
= ⇐⇒ y2 x0 = x2 y0 & y2 x1 = x2 y1 ,
x2 y2
x0 + x1 ëa y0 + y1 ëa
> ⇐⇒ [y2 x1 > x2 y1 ] ∨ [y2 x1 = x2 y1 & y2 x0 > x2 y0 ].
x2 y2
In particular, if x ∈ C (a; h) and 2h 2 < a, then there are unique x0 , x1 , x2
with no common factor other than 1 such that
x0 + x1 a
(6A-2) x= (|x0 |, |x1 |, |x2 | ≤ h).
x2
Proof of the two equivalences is immediate from Lemma 5B.1, since
x0 + x1 a y0 + y1 a
> ⇐⇒ y2 x0 + y2 x1 a > x2 y0 + x2 y1 a.
x2 y2
The uniqueness of relatively prime x0 , x1 , x2 which satisfy (6A-2) and these
equivalences requires a simple divisibility argument, Problem x6A.1. a
and (6A-3) is the correct division equation for ñ(x), ñ(y). Thus
1
R(a) =⇒ depthR (N0 [÷], a) > log log a.
12
Proof. Suppose R(a), let m = depthR (N0 [÷], a), and assume that
m+3
26 < a.
ë = ë(a!),
with ða = ëa; and since ¬R(ëa), the Homomorphism Test 4E.3 yields a
contradiction, so that
m+3
(6A-4) 26 ≥ a.
The crucial, last inequality (6B-4) holds for any pair of positive numbers
which satisfies Pell’s equation. To see this, suppose x 2 − 2y 2 = 1, and notice
first that since
x2 1
2
= 2 + 2 > 2,
y y
x √
we have > 2, and hence
y
x √ √
+ 2 > 2 2 > 2;
y
now
x √ x √ 1
( − 2)( + 2) = 2
y y y
yields the required
x √ 1 1
0< − 2= x √ < .
y ( y + 2)y 2 2y 2 a
In fact, the pairs (xn , yn ) defined in (6B-1) comprise all positive solutions
of Pell’s equation, cf. Problem x6B.1.
Good approximations of irrationals. A pair of numbers (a, b) (or the proper
a
fraction ) is a good approximation of an irrational number î, if a⊥ ⊥ b and
b
a 1
(6B-5) −î < 2.
b b
Theorem√ 6B.1 asserts in part that there are infinitely many good approxi-
mations of 2. This is true of all irrational numbers, and it is worth under-
standing it in the context of what we are doing, although we will never need it
in its full generality.
6B.2. Theorem (Hardy and Wright [1938] Thm. 188). For every irrational
number î > 0, there are infinitely many pairs (x, y) of relatively prime natural
numbers such that
x 1
î− < 2.
y y
Of the many proofs of this result, we outline one which (according to Hardy
and Wright) is due to Dirichlet.
Proof. For any real number î, let
bîc = the largest natural number ≤ î
be the house of î and î − bîc its fractional part, so that
0 ≤ î − bîc < 1.
6B. Three results from number theory 179
If we divide the half-open (real) unit interval into n disjoint, equal parts,
1 1 2 n−1
[0, 1) = [0, ) ∪ [ , ) ∪ · · · ∪ [ , 1),
n n n n
then for every î, the fractional part î − bîc will belong to exactly one of these
subintervals. Now fix a number
n ≥ 1,
and apply this observation to each of the n + 1 numbers
0, î, 2î, . . . , nî;
at least two of their fractional parts will be in the same subinterval of [0, 1),
so that, no matter what the n ≥ 1, we get
0≤j<k≤n
such that
1
jî − bjîc − (kî − bkîc) < ;
n
and setting y = k − j, x = bkîc − bjîc, we get
1
x − yî < .
n
We may assume that x and y are relatively prime in this inequality, since if we
divide both by gcd(x, y) the inequality persists. Moreover, since 0 < y < n,
we can divide the inequality by y to get
x 1 1
−î < < 2.
y ny y
Notice that if n = 1, then this construction gives y = 1, x = bîc, and the
rather trivial good approximation
bîc 1
− î < 2.
1 1
However, we have not yet used the fact that î is irrational, which implies that
x
0< −î ,
y
so that there is a number
1
m> .
| xy − î|
We now repeat the construction with m instead of n, to get x1 , y1 such that
x1 1 x1 1 1 x
− î < 2 and −î < ≤ < −î ,
y1 y1 y1 my1 m y
180 6. Lower bounds from division with remainder
x1
so that is a better, good approximation of î; and repeating the construction
y1
indefinitely, we get infinitely many, distinct good approximations. a
Next comes the most important result we need, which says, in effect, that
algebraic irrational numbers cannot have “too good” approximations.
6B.3. Theorem (Liouville’s Theorem). Suppose î is an irrational root of an
irreducible (over Q) polynomial f(x) with integer coefficients and of degree
n ≥ 2, and let
x6B.1. Problem. Prove that the pairs of numbers (xn , yn ) defined in the
proof of Theorem 6B.1 comprise all the positive solutions of the Pell equation
a 2 = 2b 2 + 1.
Recall from Problem x1C.8 that if
√ √
1+ 5 1− 5
ϕ= , ϕ̂ =
2 2
182 6. Lower bounds from division with remainder
Prove that:
(1) a < (M + 2)b.
(2) For all z, y ∈ Z,
b a y 1 b
0 < |z| < √ =⇒ − > 2
=⇒ |za − yb| > .
2C b z 2Cz 2C |z|
Prove also that for every quadratic irrational î > 1, (∗) holds for infinitely
many coprime pairs a, b.
Beyond this, it is not clear whether the notion (or suitable adaptations of it
to arbitrary algebraic real numbers) has any number-theoretic uses. But it is
exactly what we need for the next, basic result.
We can now combine the methods from Sections 5D and 6A, to derive
a double-log lower bound for coprimeness from Lin0 [÷]. The key is the
following Uniqueness Lemma for linear combinations of a difficult pair.
6C.1. Lemma. Suppose (a, b) is a difficult pair, 1 ≤ ë ∈ N, and
√
b
|x3 yi |, |y3 xi | < √
2 10
for i = 0, 1, 2, 3 with x3 , y3 > 0. Then
x0 + x1 ëa + x2 ëb y0 + y1 ëa + y2 ëb
=
x3 y3
⇐⇒ [y3 x0 = x3 y0 & y3 x1 = x3 y1 & y3 x2 = x3 y2 ],
x0 + x1 ëa + x2 ëb y0 + y1 ëa + y2 ëb
>
x3 y3
⇐⇒ [y3 (x1 a + x2 b) > x3 (y1 a + y2 b)]
or [y3 (x1 a + x2 b) = x3 (y1 a + y2 b)]
& y 3 x0 > x 3 y 0 .
Proof. The claimed equivalences follow from the following two facts, ap-
plied to (y3 x0 − x3 y0 ) + (y3 x1 − x3 y1 )ëa + (y3 x2 − x3 y2 )ëb.
√
b
(1) If x + zëa + yëb = 0 and |x|, |y|, |z| < √ , then x = y = z = 0.
10
184 6. Lower bounds from division with remainder
if we square this and simplify (using that 40 < 26 ), we see that it follows from
the assumed h 28 ≤ b. a
6C.3. Lemma (Inclusion). Suppose (a, b) is a difficult pair, and for any m,
let Gm (a, b) = Gm (N0 [÷], a, b); it follows that
4m+5 4m
if 22 ≤ a, then Gm (a, b) ⊆ C (a, b; 22 ).
Proof is by induction on m, the case m = 0 being trivial. To apply
Lemmas 6A.1 and 6C.2 at the induction step, we need to verify (under the
hypothesis on a and m) the following two inequalities.
4m 12 4(m+1)
(1) 22 ≤ 22 . This holds because
4m 12 4m 4 4m 4(m+1)
22 = 212·2 < 22 ·2 = 22 .
4m 28
(2) 22 ≤ b. So compute:
4m 28 4m 5 4m 4m+5
22 = 228·2 < 22 ·2 = 22 ≤ a. a
4m+6
6C.4. Lemma. Suppose (a, b) is a difficult pair, 22 ≤ a, and set ë = 1+a!.
Then there is an embedding
4m
ð : N0 [÷] C (a, b; 22 ) N0 [÷]
such that ð(a) = ëa, ð(b) = ëb.
Proof. To simplify notation, let
4m
h = 22 .
As in the proof of Lemma 6A.5, we will actually need to define the embedding
on the larger substructure N0 [÷] C (a, b; h 12 ), so let’s first verify that the
assumed bound on h is good enough to insure unique canonical forms in
C (a, b; h 12 ). By Lemma 6C.1, we need to check that
2 √
12 b
h < √ ,
2 10
which is equivalent to
(6C-8) 4 · 10h 48 < b;
and this is true, because
4m 55 6 4m 4m+6
4 · 10h 49 < 22 · 24 h 49 ≤ h 55 = 22 < 22 ·2 = 22 < a,
This corollary implies that Theorem 6C.5 is best possible (except, of course,
for the specific constant 10), because the absolute lower bound it gives for
all difficult pairs is matched by the Pratt algorithm on pairs of successive
Fibonacci numbers. Note, however, that it does not rule out the possibility
that the Main Conjecture in the Introduction holds for all uniform processes
of Nε , even if we formulate it for coprimeness rather than the gcd—because
it might hold with another, more restrictive or different notion of “difficult
pair” which excludes pairs of successive Fibonacci umbers; in other words, we
may have the wrong proof.
The most exciting possibility would be that the conjecture holds for de-
terministic uniform processes—or just deterministic programs—which would
exhibit the distinction between determinism and nondeterminism in a novel
context. I have no idea whether this holds or how to go about proving it.
6C. Coprimeness from Lin0 [÷] 189
x6C.1∗ . Problem (van den Dries and Moschovakis [2004], [2009]). For
every quadratic irrational î > 1, there is a rational number r > 0 such
that for all but finitely many good approximations (a, b) of î,
(6C-11) depth(N[÷], ⊥
⊥ , a, b) ≥ r log log a.
Hint: Use Problem x6B.5 to adjust the argument for difficult pairs in this
section.
The O(log log) bound in this problem is best possible, because of Pratt’s
algorithm.
CHAPTER 7
37 The usual convention is to set deg(0) = −∞, which saves some considerations of cases in
stating results.
191
192 7. Lower bounds from division and multiplication
The sum, difference and product of two polynomials are defined by the
performing the obvious operations on the coefficients and collecting terms:
P
X + Y = i (xi + yi )T i , deg(X + Y ) ≤ max(deg(X ), deg(Y ))
P i
−X = i (−xi )T , deg(−X ) = deg(X )
P Pi=k
k
XY = k i=0 xi yk−i T deg(XY ) = deg(X ) + deg(Y ).
The last formula illustrates the occasional usefulness of thinking of a polyno-
mial as an infinite sum with just finitely many non-zero terms.
With these operations, the set K [T ] of polynomials over a ring K is a
(commutative) ring over K . For the more interesting division operation, we
need to assume that K is a field.
7A.1. Theorem (The Division Theorem for polynomials). If K is a field,
and X, Y ∈ K [T ] such that deg(X ) ≥ deg(Y ) and Y 6= 0, then there exist
unique polynomials Q, R ∈ K [T ] such that
(7A-1) X = YQ + R and R = 0 or deg(R) < deg(Y ).
Proof is by induction on the difference d = n − m of the degrees of the
given polynomials, n = deg(X ), m = deg(Y ).
At the basis, if m = n, then
xn
X =Y +R
yn
with R defined by this equation, so that either it is 0 or its degree is less than
xn
n, since X and Y have the same highest term xn T n .
yn
In the induction step, with d = n − m > 0, first we divide X by YT d , the
two having the same degree:
X = YT d Q1 + R1 (R1 = 0 or deg(R1 ) < n).
If R1 = 0 or deg(R1 ) < m, we are done; otherwise deg(R1 ) ≥ deg(Y ) and we
can apply the induction hypothesis to get
R1 = YQ2 + R2 (R2 = 0 or deg(R2 ) < deg(Y )).
We now have
X = Y (T d Q1 + Q2 ) + R2 (R2 = 0 or deg(R2 ) < deg(Y )),
which is what we needed.
We skip the proof of uniqueness, which basically follows from the construc-
tion. a
We call (7A-1) the correct division equation (cde) for X, Y .
This basic fact does not hold for polynomials in Z[T ]: for example, if X = 3
and Y = 2, then there are no Q, R which satisfy (7A-1), simply because 2
does not divide 3 in Z. To get at the results we need, it is most convenient to
7A. Polynomials and their heights 193
work with the larger ring Q[T ], but study a particular “presentation” of it, in
which the concept if height is made explicit.
The height of a non-zero integer polynomial is the maximum of the absolute
values of its coefficients,
height(x0 + x1 T + · · · + xn T n ) = max{|xi | | i = 0, . . . , n} (xi ∈ Z).
To extend the definition to Q[T ], we let for each n, h ∈ N,
nx + x T + x T2 + · · · + x Tn
0 1 2 n
(7A-2) Qn (T ; h) = |
x∗ o
x0 , . . . , xn , x ∗ ∈ Z, x ∗ > 0 and |x0 |, . . . , |xn |, |x ∗ | ≤ h .
This is the set of polynomials in the indeterminate T over Q, with degree n and
height no more than h. When the degree is not relevant, we skip the subscript,
S
Q(T ; h) = n Qn (T ; h);
and in computing heights, it is sometimes convenient to use the abbreviation
X : h ⇐⇒ X ∈ Q(T ; h).
The canonical form (7A-2) gives a unique height(X ) if the coefficients xi
have no common factor with x ∗ , but this is not too important: most of the
time we only care for an upper bound for height(X ) which can be computed
without necessarily bringing X to canonical form. Notice however, that (as a
polynomial over Q),
3 + 2T 1 1
X = = + T,
6 2 3
1
but the height of X is neither 3 nor ; it is 6.
2
It is very easy to make “height estimates” for sums and products of polyno-
mials:
7A.2. Lemma. If X, Y are in Q[T ] with respective degrees n and m and
X : H, Y : h, then
X + Y : 2Hh, XY : (n + m)Hh.
Proof. For addition,
(y ∗ x0 + x ∗ y0 ) + (y ∗ x1 + x ∗ y1 )T + · · ·
X +Y = ,
x∗y ∗
and every term in the numerator clearly has absolute value ≤ 2Hh. For
multiplication,
Pn+m Pi=k
k=0 i=0 x i y k−i Tk
XY = .
x∗y∗
194 7. Lower bounds from division and multiplication
and if k = n + m, then
Pi=n+m
i=0 xi yk−i = |xn ym | ≤ Hh < (n + m)Hh
since xi = 0 when i > n and yj = 0 when j > m. a
The next result is a version of the Division Theorem 7A.1 for Q[T ] which
supplies additional information about the heights.
7A.3. Lemma (Lemma 2.3 of Mansour, Schieber, and Tiwari [1991b]). Sup-
pose X and Y are polynomials with integer coefficients,
deg(X ) = n ≥ m = deg(Y ), X : H, Y : h,
and X = YQ + R with R = 0 or deg(R) < deg(Y ).
Then
Q1 R1
Q= , R= ,
ymd +1 ymd +1
where d = n − m and Q1 , R1 are in Z[T ] with height ≤ H (2h)d +1 . It follows
that
Q, R : H (2h)d +1 .
Proof is by induction on d .
Basis, deg(X ) = deg(Y ) = n. In this case
xn
X =Y +R
yn
with R defined by this equation, so that either it is 0 or it is of degree < n.
xn
Now Q1 = has height ≤ H , and
yn
R 1 = y n X − xn Y
so that the typical coefficient of R1 is of the form yn xi − xn yi , and the absolute
value of this is bounded by 2Hh = H (2h)0+1 .
Induction Step, d = deg(X ) − deg(Y ) = n − m > 0. Consider the
polynomial
(7A-3) Z = ym X − xn YT d
whose degree is < n = m + d since the coefficient of T n in it is ym xn − xn ym .
If Z = 0 or deg(Z) < m, then
xn T d Z xn ymd T d yd Z
X =Y + =Y d +1
+ md +1
ym ym ym ym
7A. Polynomials and their heights 195
We establish here suitable versions of Lemma 6A.5 and Theorem 6A.6 for
the structure
·
N0 [÷, ·] = (N0 , Lin0 [÷, ·]) = (N, 0, 1, =, <, +, − , iq, rem, ·)
√
with a log log bound.
Set, for any a, n, h ∈ N,
n x + x a + x a2 + · · · + x an
0 1 2 n
(7B-1) Qn (a; h) = ∈N
x∗ o
| x0 , . . . , xn , x ∗ ∈ Z, x ∗ > 0 and |x0 |, . . . , |xn |, |x ∗ | ≤ h .
These are the values for T := a of polynomials in Qn (T ; h), but only those
which are natural numbers; and they are the sort of numbers which occur
(with various values of h) in Gm (a) = Gm [(N0 [÷, ·], a). To simplify dealing
with them, we will be using the standard notations
x0 + x1 a + x2 a 2 + · · · + xn a n
(7B-2) x = f(a) = ,
x∗
y0 + y1 a + y2 a 2 + · · · + ym a m
y = g(a) = ,
y∗
where it is assumed that xn , ym 6= 0 (unless, of course, x = 0, in which case,
by convention, n = 0 and x0 = 0). It is also convenient to set xi = 0 for i > n,
and similarly for yj , and to use the same abbreviations we set up for Qn (T ; h),
especially
S
Q(a; h) = n Qn (a; h), x : h ⇐⇒ x ∈ Q(a; h).
7B.1. Lemma. With x and y as in (7B-2), if h ≥ 2 and x, y ∈ Qn (a; h), then
x + y, x −·
y ∈ Qn (a; h 3 ), and xy ∈ Q2n (a; nh 3 ).
Proof. These are all immediate, using Lemma 7A.2. a
The analogous estimates for iq(x, y) and rem(x, y) are substantially more
complex, and we need to establish first the uniqueness of the representa-
tions (7B-2) when h is small relative to a.
7B.2. Lemma. (1) With all xi ∈ Z and a > 2, if |xi | < a for i ≤ n, then
x0 + x1 a + · · · + xn a n = 0 ⇐⇒ x0 = x1 = · · · = xn = 0;
7B. Unary relations from Lin0 [÷, ·] 197
where the condition on R(a) is trivial if R(a) ≤ 0, and follows from the
corresponding condition about degrees in (7B-3) by Lemma 7B.2, provided
that the height of R(a) is sufficiently small, specifically
2
2 h 4n+10 < a;
so here we assume
2
(H2) c ≥ 21, so that 2 h 4n+10 ≤ hh 8n+20 = h 8n+21 < h 21(n+1) < a.
However, (7B-5) need not be the correct division equation for the numbers
f(a), g(a), because Q(a) might not be integral or R(a) might be negative.
For an example where both of these occur, suppose
f(a) = a 2 − 1, g(a) = 2a with a odd,
in which case (7B-3) and (7B-5) take the form
T a
T 2 − 1 = 2T ( ) − 1, a 2 − 1 = 2a( ) − 1.
2 2
To correct for this problem, we consider four cases.
Case 1, Q(a) ∈ N and R(a) ≥ 0. In this case (7B-5) is the cde for f(a) and
g(a), and from (7B-4),
Q(a), R(a) : h 4n+10 ;
thus we assume at this point
(H3) d ≥ 10, so that h 4n+10 ≤ h d (n+1) .
Q1 (a)
Case 3, Q(a) = / N, and Q1 (a) ≥ z > 1. We note that
∈
z
Q1 (a) : h 4n+10 , z ≤ h 4n+10 ,
and both Q1 (a) and z are positive, and so we can put down the cde for them
in N:
Q1 (a) = zQ2 + R2 (0 < R2 < z),
where we know that R2 > 0 by the case hypothesis. From this it follows that
Q1 (a) − R2 4n+10 3
R2 < z ≤ h 4n+10 , and Q2 = : h = h 12n+30
z
by Lemma 7B.1 again. Replacing these values in (7B-5), we get
R2
(7B-6) f(a) = g(a)Q2 + g(a) + R(a)
| z {z }
and the number above the underbrace is in Z, as the difference between two
numbers in N. This number is the value for T := a of the polynomial
R2
g(T ) + R(T )
z
whose leading coefficient is that of g(T )—since deg(R(T )) < deg(g(T ))—
and hence positive. We would like to infer from this that
R2
g(a) + R(a) > 0,
z
using Lemma 7B.2, and so we make sure that its height is suitably small.
From the two summands, the second has the larger height, h 4n+10 , and so by
Lemma 7B.1, the height of the sum is bounded by
h 4n+10 )3 = h 12n+30 ;
in these papers are very different from the direct applications of the Embed-
ding Test that we have been using, which makes it very difficult to compare
their results with ours.
As we mentioned in Footnote 34 on page 146, Mansour, Schieber, and
Tiwari [1991b] also derive (for their models) a triple-log lower bound for
coprimeness from Lin0 [÷, ·] on infinitely√many inputs, and van den Dries has
proved (using output complexity) an O( log log)-lower bound for computing
gcd(x, y) on infinitely many inputs. We list as an open problem what would
be the best (intrinsic) relevant result.
x7B.1. Open problem. Prove that for some infinite set of pairs A ⊂ N × N
and some r > 0,
q
(a, b) ∈ A =⇒ depth⊥
⊥ (N 0 [÷, ·], a, b) > r log log max(a, b).
CHAPTER 8
NON-UNIFORM COMPLEXITY IN N
A computer has finite memory, and so it can only store and operate on a finite
set of numbers. Because of this, complexity studies which aim to be closer to
the applications are often restricted to the analysis of algorithms on structures
with universe the finite set
[0, 2N ) = {x ∈ N : x < 2N }
of N -bit numbers for some fixed (large) N , typically restrictions to [0, 2N ) of
expansions of Nd or N0 , e.g., N0 [÷], N0 [÷, ·], etc. The aim now is to derive
lower bounds for the worst case behavior of such algorithms as functions of
N ; and the field is sometimes called non-uniform complexity theory, since, in
effect, we allow for each N the use of a different algorithm which solves a
given problem in A [0, 2N ).
For each structure A = (N, Υ) with universe N, each relation R ⊆ Nn and
each N , let
n o
(8-7) depthR (A, 2N ) = max depthR (A [0, 2N ), x ~ ) : x1 , . . . , xn < 2N
and similarly for valuesR (A, 2N ), callsR (A, 2N ). These are the intrinsic (worst
case) non-uniform bit complexities of R from the primitives of A, at least those
of them for which we can derive lower bounds. As it turns out, the results
and the proofs are essentially the same for Nd , except for the specific con-
stants which are now functions of N (and somewhat smaller). For N0 [÷]
and N0 [÷, ·], however, we need a finer analysis and we can only derive lower
bounds for the larger complexity valuesR (A, 2N ), primarily because there is
“less room” in [0, 2N ) for embeddings which exploit the uniformity assump-
tion in the definition of intrinsic complexities. It is this new wrinkle in the
proofs that is most interesting in this brief chapter.
We will show here that the intrinsic lower bounds from Lind of Chap-
ter 5 hold also in the non-uniform case, with somewhat smaller constants.
203
204 8. Non-uniform complexity in N
This means (roughly) that for these problems, the lookup algorithm in Prob-
lem x8A.1 is weakly optimal for depth intrinsic bit complexity in Nd .
8A.1. Theorem (van den Dries and Moschovakis [2009]). If N ≥ 3, then
N
depthPrime (Nd , 2N ) > .
5 log d
Proof. Suppose p < 2N is prime and let
m = depthPrime (Nd [0, 2N ), p), ë = 1 + d m+1 .
If
x0 + x1 ëp
(a) d 2m+2 < p and (b) < 2N for all |x0 |, |x1 | ≤ d 2m ,
dm
then the proof of Lemma 5B.2 would produce an embedding
ð : Gm (Nd [0, 2n ), p) Nd [0, 2N )
which does not respect the primality of p, yielding a contradiction. So for
every prime p < 2N , one of (a) or (b) must fail. To exploit this alternative,
we need to apply it to primes not much smaller than 2N , but small enough so
that (b) holds, and to find them we appeal to Bertrand’s Postulate, Hardy and
Wright [1938, Theorem 418]; this guarantees primes between l and 2l when
l ≥ 3. So choose p such that
2N −1 < p < 2N ,
which exists because 2N −1 > 3 when N ≥ 3.
Case 1, d 2m+2 ≥ p, and so d 2m+2 > 2N −1 . Using as always the fact that
N
m ≥ 1, this gives easily m > 5 log d.
N
and so the case hypothesis implies that m > 5 log d again, as required. a
Similar mild elucidations of the proofs we have given extend all the lower
bound results about Nd in Chapter 5 to intrinsic bit complexity, and they are
simple enough to leave for the problems.
8B. Non-uniform lower bounds from Lin0 [÷] 205
where the two products are equal because denom(a) = 1 and values(U, a) =
|U | − 1. To prove this we follow very closely the proof of Lemma 6A.5: we set
x + x a x + x ëa
0 1 0 1
ñ(x) = ñ = ;
x2 x2
check that this is a well defined injection on U which takes values in N, because
x ∈ U =⇒ denom(x) | (ë − 1);
and finally verify that it is an embedding from U to N0 [÷] exactly as in the
proof of Lemma 6A.5. a
8B.2. Theorem (van den Dries and Moschovakis [2009]). If N ≥ 8, then
1
(8B-3) valuesPrime (N0 [÷], 2N ) > log N.
10
Proof. Let k = b N2 c − 1 so that
N N
k+1≤ < k + 2 and so k > − 2.
2 2
The hypothesis on N yields 2k > 4, so Bertrand’s Postulate insures that there
exists some prime p such that 2k < p < 2k+1 . This is the prime we want. Let
A = N0 [÷] [0, 2N ) (to simplify notation) and choose U ⊆p A so that
A
U c Prime(p), valuesPrime (A, p) = values(U, p),
and set m = depth(U, p). (It could be that m > depthPrime (A, p).) Let
Q Q
ë = 1 + x∈U denom(x) = 1 + x∈U,x6=p denom(x)
as above. If
m+3 x0 + x1 ëp m+1
26 < p and < 2N whenever |xi | ≤ 26 ,
x2
8B. Non-uniform lower bounds from Lin0 [÷] 207
m+2
then ë < 2í6 and the argument in the proof of Lemma 8B.1 produces an
embedding ð : U A which does not respect the primality of p, contrary to
the choice of U; so one of the two following cases must hold.
m+3
Case 1: 26 ≥ p > 2k . This gives 6m+3 > k > N2 − 2, and this easily
implies (with m ≥ 1) that í ≥ m > log10N in this case, cf. Problem x8B.1.
m+1
Case 2: For some x0 , x1 , x2 with |xi | ≤ 26 ,
x0 + x1 ëp
≥ 2N .
x2
Compute:
x0 + x1 ëp m+1 m+1 m+2 N m+1 m+2 N
≤ 26 + 26 · 2í6 · 2 2 ≤ 2 · 26 +í6 · 2 2
x2
m+2 N m+2 N
≤ 22í6 +1
· 2 2 ≤ 23í6 ·22.
m+2 N
So the case hypothesis gives 23í6 · 2 2 ≥ 2N which gives 3í6m+2 ≥ N2 and
then í6m+3 ≥ N . This is the basic fact about the non-uniform, intrinsic bit
·
complexity of primality from {=, <, +, − , iq, rem} and it can be used to derive
a lower bound for the measure induced by the substructure norm
ì(U, a) = values(U, a) · 6depth(U,a)+3 .
To derive an easier to understand lower bound for the values complexity,
we compute: 6í 6í+3 ≥ í6m+3 ≥ N ; so 62í+3 ≥ N ; so (2í + 3) log 6 ≥ log N ,
and since í > 0, as usual, 5í ≥ 2í + 3 and so
1 1
í≥ log N > log N. a
5 log 6 10
It should be clear that the numerology in this proof was given in detail
mostly for its amusement value, since from the first couple of lines in each
of the cases one sees easily that í > r log N for some r. Moreover, one
1
can certainly bring that 10 up quite a bit, with cleverer numerology, a more
judicious choice of p, or by weakening the result to show that (8B-3) holds
only for very large N . The problems ask only for these more natural (if slightly
weaker) results and leave it up to the solver whether they should indulge in
manipulating numerical inequalities.
x8B.2. Problem. Suppose R is a good example with the property that for
some k and every m ≥ 1, there is some x such that R(x) and
m km
26 < x < 26 .
Prove that for some r > 0 and sufficiently large N ,
valuesR (N[÷], 2N ) > r log N.
Verify also that the good examples in Problem x5C.4 satisfy the hypothesis.
x8B.3. Problem (van den Dries and Moschovakis [2009]). Prove that for some
r > 0 and all sufficiently large N ,
N
values⊥
⊥ (N[÷], 2 ) > r log N.
√ N
Hint: Use the largest good approximation (a, b) of 2 with a < 2 2 .
x8B.4. Open problem. Prove that for some r > 0 and all sufficiently large N ,
N
depth⊥
⊥ (N[÷], 2 ) > r log N.
x8B.5. Problem. Derive a lower bound for valuesR (Lin0 [÷, ·], 2N ) when R
is a good example or ⊥
⊥.
CHAPTER 9
38 I am grateful to Tyler Arant for checking and correcting many errors in the first draft of this
chapter; and, of course, I am fully responsible for the inevitable remaining errors.
209
210 9. Polynomial nullity (0-testing)
and in that case, the extensions F [~ a ], F (~
a ) ⊆ K are naturally isomorphic
with F [~
u ] and F (~
u ) respectively by the relabelling isomorphism determined by
ai 7→ ui , for i = 1, . . . , k. Similarly, if K1 , K2 ⊃ F and a~ ∈ K1n , ~b ∈ K2n
are algebraically independent over F , then the relabelling ai 7→ bi induces an
isomorphism
ë : F (~ → F (~b)
a) (ë(ai ) = bi , i = 1, . . . n)
a ] and F [~b]. We will
which fixes F , and similarly for the polynomial rings F [~
often establish some facts about one of these rings or fields and then quote
them for the other, often without explicit mention, and we will also use the
same terminology for these isomorphic structures: if, for example, a, b are
complex numbers which are algebraically independent (over the prime field
Q), then the members of Q(a, b) are “the rational functions of a, b”.
A partial ring homomorphism
ð : F1 * F2
on one field to another is a partial function whose domain of convergence
Domain(ð) is a subring R1 of F1 (with 1) and which respects as usual the ring
operations, including ð(1) = 1. Notice that for every U ⊆p F1 ,
(9A-1) if ð is total on U and 0 6= x ∈ U =⇒ ð(x) 6= 0 ,
then ð U : U → F2 is a homomorphism,
i.e., ð U preserves not only the ring operations, but also all divisions in
eqdiag(U). This is because if (÷, u, v, w) ∈ eqdiag(U), then ð(u), ð(v), ð(w)
are all defined and v 6= 0, so ð(v) 6= 0 by the hypothesis of (9A-1); and since
vw = u, we have ð(v)ð(w) = ð(u), which then gives ð(w) = ð(u) ð(v)
.
If F (v, u~ ) ⊆ K for some field K and α ∈ K , then the substitution v 7→ α
induces a partial ring homomorphism
÷ (v, u~ ) ÷ (α, u~ ) ÷ (v, u~ )
n n n
(9A-2) ñα = ∈ F (v, u~ )
÷d (v, u~ ) ÷d (α, u~ ) ÷d (v, u~ )
with
n ÷ (v, u~ ) o
n
Domain(ñα ) = : ÷d (α, u~ ) 6= 0 ⊆ F (v, u~ ).
÷d (v, u~ )
Notice that F [v, u~ ] ⊂ Domain(ñα ) and ñα (ui ) = ui . We will sometimes call
ñα “the substitution” (v 7→ α), and the only homomorphisms we will need
are compositions of such substitutions.
9A.1. The Substitution Lemma. Suppose F, K are fields, v, u~ are indetermi-
nates, U is a finite subset of F (v, u~ ), K ⊇ F (v, u~ ) and {αt }t∈I is an infinite
set of distinct elements of K . It follows that for all but finitely many t ∈ I , the
9B. Generic {·, ÷}-optimality of Horner’s rule 211
so that
P P
(f0 − f00 ) xi øi + 1≤i≤n (fi − fi0 )xi + (φ(y) − φ 0 (y))
1≤i≤n
P
= 1≤i≤n (f0 − f00 )øi + (fi − fi0 ) xi + (φ(y) − φ 0 (y)) = 0.
This yields φ(y) = φ 0 (y) and for each i, (f0 − f00 )øi + (fi − fi0 ) = 0; and
since no øi is in F by (2) of the hypothesis, this implies that f0 = f00 , and
finally that fi − fi0 for each i.
The identity (9B-2) is trivial because ð(z) = x1 ø1 + · · · + xn øn and ð(xi ) =
xi .
Basis, n = 1. This is covered by the preliminary case.
Induction Step, n > 1. If the preliminary case does not apply, then there
is at least one non-trivial {·, ÷} in eqdiag(U); so there is a least m > 0 such
that some ÷ ∈ Gm (U, z, x ~ , y) is a non-trivial product or quotient of elements
of Gm−1 (U, z, x~ , y) in which all {·, ÷} are trivial; and so there is at least one
non-trivial {·, ÷} in eqdiag(U) of the form
P P
(9B-4) (f00 z + 1≤i≤n fi0 xi + φ 0 (y)) ◦ (f0 z + 1≤i≤n fi xi + φ(y)) = ÷
where ◦ is · or ÷. We consider cases on how this can arise.
Case 1: There is some i ≥ 1 such that fi 6= 0, and the first factor in (9B-4) is
not in F . We assume without loss of generality that f1 6= 0, and then dividing
the equation by f1 we put the second factor in the form
P
(9B-5) f0 z + x1 + 2≤i≤n fi xi + φ(y).
By the Substitution Lemma 9A.1, there is some f ∈ F such that the substitu-
tion
P
ñ1 (x1 ) = f − f0 z − 2≤i≤n fi xi − φ(y)
214 9. Polynomial nullity (0-testing)
induces an isomorphism
ñ1 U : U
→ ñ1 [U] = U1 ⊆p F(z, x2 , . . . , xn , y).
Notice that ñ1 does not introduce any new non-trivial multiplication or divi-
sion (because it is the identity on F (y)), and it turns the chosen operation in
U into a trivial one since
P
ñ1 (f0 z + x1 + 2≤i≤n fi xi + φ(y)) = f.
So there are fewer than n − 1 {·, ÷} in eqdiag(U1 ), and U1 is generated by
z, x2 , . . . , xn , y and {f} ∪ (F ∩ U ).
Applying Lemma 9A.1 again, fix some g ∈ F such that the substitution
1
ñ2 (z) = (f − φ(y))ø1 + gz
1 + f0 ø1
induces an isomorphism
ñ2 U1 : U1
→ ñ2 [U1 ] = U2 ⊆p F(z, x2 , . . . , xn , y).
This too does not introduce any non-trivial multiplications or divisions, and
U2 is generated by z, x2 , . . . , xn , y and F ∩ U2 . The required partial ring
homomorphism is the composition
ð = ó ◦ ñ2 ◦ ñ1 : F (z, x
~ , y) * F (~
x , y)
of the three substitutions, where ó is guaranteed by the induction hypothesis
so that ó U2 : U2 F(x2 , . . . , xn , y) and
P
gó(z) = 2≤i≤n (øi − fi ø1 )ó(xi ).
This exists because the functions
1
(øi − fi ø1 ) (i = 2, . . . , n)
g
satisfy (2) in the theorem.
To see that ð has the required property, notice first that
ð(z) = ó(ñ2 (z))
because ñ1 (z) = z. Using the corresponding properties of ñ2 and ó, we get:
P
ð(x1 )ø1 + 2≤i≤n ð(xi )øi
P P
= ó ñ2 (f − φ(y) − 2≤i≤n fi xi − f0 z) ø1 + 2≤i≤n ó(xi )øi
P P
= ó f − φ(y) − 2≤i≤n fi xi − f0 ñ2 (z) ø1 + 2≤i≤n ó(xi )øi
P
= (f − φ(y))ø1 − f0 ø1 ó(ñ2 (z)) + 2≤i≤n (øi − fi ø1 )ó(xi )
= (f − φ(y))ø1 − f0 ø1 ó(ñ2 (z)) + gó(z).
9B. Generic {·, ÷}-optimality of Horner’s rule 215
and the last is immediate from the definition of ñ2 (z). (Note that we use
repeatedly the fact that ó is injective on U2 and the identity on F (y).)
Case 2: f1 = · · · = fn = 0, f0 6= 0, and the first factor in (9B-4) is not in
F . We may assume without loss of generality that f0 = 1, and so the second
factor has the form
z + φ(y).
ñ1 (z) := f − φ(y)
induces an isomorphism
ñ1 : U
→ ñ1 [U] = U1 ⊆p F(~
x , y).
ñ2 : U1
→ ñ2 [U1 ] = U2 ⊆p F(z, x2 , . . . , xn , y).
ó : U2 F(z, x2 , . . . , xn , y)
such that
P
gó(z) = 2≤i≤n ó(xi )øi .
Counting identity tests along with {·, ÷}. The generic {·, ÷, =}-optimality
of Horner’s rule for nullity is an easy Corollary of Theorem 9B.1.
9B.4. Theorem.40 Suppose F is a field of characteristic 0, n ≥ 1 and
z, x1 , . . . , xn , y ∈ F are algebraically independent over Q; then
(9B-6) calls(·, ÷, =)(F, NF , z, x1 , . . . , xn , y) = n + 1.
In particular, (9B-6) holds for the reals R and the complexes C with alge-
braically independent z1 , x1 , . . . , xn , y.
Proof. Horner’s rule gives
calls(·, ÷, =)(F, NF , z, x1 , . . . , xn , y) ≤ n + 1,
for all z, x
~ , y.
40 This result is also implicit in Bürgisser and Lickteig [1992], for algebraic decision trees.
9B. Generic {·, ÷}-optimality of Horner’s rule 217
h c h
b0
hence x2b2 · · · xnbn = x2 2 · · · xnbn , hence bi = bi0 for i = 2, . . . , n; and since
bi bi0 = 0, all these numbers are 0. If we repeat this argument41 using xn rather
than x1 , we get that b1 = b10 = 0 also, so that the original assumption takes
the simpler form
1 1 n
c 1 1 n
c 0
x 1 y + · · · + x n y p(y) = x 1 y + · · · + x n y p0 (y);
hc hc0
and if we expand again in powers of x1 and equate the leading terms we get
1 c 1 0 0
c
y p(y)x1c = c 0 y c p0 (y)x1c ,
h h
which yields c = c 0 and finally p(y) = p0 (y) as required. a (Sublemma 1)
Proof . Let
−b10 −b20 −bn0 −c 0
W = x1 x2 · · · xn z pd (y)pd0 (y)
where pd (y), pd0 (y) are the denominators of p(y), p0 (y) and replace (9C-5)
in eqdiag(U) by the operations
w1
u1 = Wu, v1 = Wv, w1 = u1 + v1 , w =
W
along with all the multiplications, divisions and trivial additions and subtrac-
tions required to compute W . If U0 is the resulting structure, then U ⊆ U 0 and
the fixed, non-trivial addition in U has been replaced by one of the form (9C-6).
It is not quite true that U ⊆p U0 , because the equation w = u + v is in
eqdiag(U) but not in eqdiag(U0 ). On the other hand, if ð : Q(z, x ~ , y) * K is a
partial ring homomorphism which is total and injective on U 0 , then its restric-
tion ð U : U K is an embedding, because it respects all the other entries
1 )+ð(v1 ) ð(w1 )
in eqdiag(U) and ð(u + v) = ð(uð(W )
= ð(W )
= ð(w). a (Sublemma 2)
We need this to be equal to hð(z) = hñt (ót (z)) = hñt (z b1 ) = hαtb1 , i.e., we
must choose αt so that
f
b2
αt−c + t b1 (x b21 y 2 + · · · + x bn1 y n ) = hαtb1 ,
t (x 2 · · · x bnn )
d
For any positive t, the polynomial on the left has a negative value when
X = 0 and it goes to ∞ as X → ∞, so it has a root on the positive axis, and
we fix αt to be its least positive root. Moreover, for each α ∈ R+ , there are at
9C. Generic {+, −}-optimality of Horner’s rule 223
There are infinitely many distinct αg ’s, since g 7→ αg is injective, and so the
homomorphism induced by x1 7→ αg is injective on U1 for all but finitely
many g’s, we choose one such g to define ñ2 (x1 ) and trace the computation
backward to complete the proof. a
ó : Q(−z, x1 , . . . , xn , y)
→ Q(z, x 1 , . . . , x n , y)
−z 7→ z, x1 7→ x 1 , . . . , xn 7→ x n , y 7→ y,
Now Lemma 9C.3 applies and guarantees a partial ring homomorphism ð00 :
Q(z, x~ , y) * K which is the identity on Q(y), total and injective on U 00 and
satisfies
and then ð is also total and injective on U , since U ⊆ U 0 and it satisfies the
required ð(z) + ð(x1 )y 1 + · · · + ð(xn )y n = 0. a
9C. Generic {+, −}-optimality of Horner’s rule 225
Counting identity tests along with {+, −}. The (small) variation of Horner’s
rule we described on page 218 shows that for every field F of characteristic
6= 2 and all z, x
~ = (x1 , . . . , xn ), y,
calls(+, −, =)(F, NF , z, x
~ , y) ≤ n + 1,
cf. Problem x9C.2. We show that this is best possible for “rich” fields in the
generic case.
9C.4. Theorem.42 If n ≥ 1, F is a field, K ⊆ F and z, x1 , . . . , xn , y are in F
and algebraically independent over Q, then
(9C-10) calls(+, −, =)(F, NF , z, x1 , . . . , xn , y) = n + 1.
In particular, this holds when F is the real or the complex field, R or C.
Proof. We assume n ≥ 2, leaving the (easy) n = 1 case for Problem x9C.1,
so what we need to prove to infer (9C-10) for n ≥ 2 by the Homomorphism
Test 4E.3 is the following: for every finite U ⊆p F generated by (U ∩ Q) ∪
~ , y} and such that
{z, x
calls(+, −, =)(U, z, x
~ , y) ≤ n,
there is a homomorphism ð : U → F such that
(9C-11) ð(z) + ð(x1 )y 1 + · · · + ð(xn )y n = 0.
We define trivial {+, −, =} as in the proof of Lemma 9C.3 and we enumerate
eqdiag(U) as in Problem x1D.8,
eqdiag(U) = φ0 ◦0 ø0 = ù0 , . . . , φm ◦m øm = ùm
where each ◦i is one of the field operations +, −, ·, ÷ or a trivial inequation
and for each s ≤ m, the structure Us with
U s = {0, z, x
~ , y} ∪ {ùi : i < s & ùi ∈ U }
eqdiag(Us ) = {φ0 ◦0 ø0 = ù0 , . . . , φs−1 ◦s−1 øs−1 = ùs−1 }
is generated by (U ∩ F ) ∪ {0, z, x ~ , y}. Suppose αk and αl (in this order) are
the last two non-trivial entries in this enumeration of eqdiag(U) and consider
first the structure Uk . Its diagram has fewer than n − 1 non-trivial {+, −} and
it satisfies all the other hypotheses of Lemma 9C.2, so there is a partial ring
homomorphism
ð : Q(z, x
~ , y) * K ⊆ F
which is total, injective on U k and the identity on F (y) and satisfies (9C-11).
If αk is an inequation, then ð respects it because it is injective; and then it also
respects αl and all the trivial entries after αk because it is a ring homomorphism
which is the identity on F (y), and we are done. In the opposite case αk is
42 A differently formulated but equivalent result is proved for algebraic decision trees in Bürg-
x9C.2. Problem. Prove that if F has characteristic 6= 2, then for all tuples
~ , y = z, x1 , . . . , xn , y ∈ F ,
z, x
calls(+, −, =)(F, NF , z, x
~ , y) ≤ n + 1.
Hint: Use the subroutine in Problem x9C.1 and Corollary 4E.2.
x9C.3. Problem. Prove that if A, B ⊂ R are any two countable sets of alge-
braically independent (over Q) real numbers, then the fields KA , KB defined
from A and B by (9C-1) are isomorphic.
x9C.4∗ . Problem. Prove Theorem 9C.5.
REFERENCES
Siddharth Bhaskar
[2017] A difference in complexity between recursion and tail recursion,
Theory of Computing Systems, vol. 60, pp. 299–313. 124.
[2018] Recursion versus tail recursion over Fp, Journal of Logical and Alge-
braic Methods in Programming, pp. 68–90. 97.
Joseph Busch
[2007] On the optimality of the binary algorithm for the Jacobi symbol,
Fundamenta Informaticae, vol. 76, pp. 1–11. 170.
[2009] Lower bounds for decision problems in imaginary, norm-Euclidean
quadratic integer rings, Journal of Symbolic Computation, vol. 44, pp. 683–
689. 170.
Alonzo Church
[1935] An unsolvable problem in elementary number theory, Bulletin of the
American Mathematical Society, vol. 41, pp. 332–333, This is an abstract of
Church [1936]. 99, 229.
[1936] An unsolvable problem in elementary number theory, American Jour-
nal of Mathematics, pp. 345–363, An abstract of this paper was published in
Church [1935]. 99, 229.
229
230 References
L. Colson
[1991] About primitive recursive algorithms, Theoretical Computer Science,
vol. 83, pp. 57–69. 125.
Martin Davis
[1958] Computability and unsolvability, Originally published by McGraw-
Hill, available from Dover. 4.
M. Dužı́
[2014] A procedural interpretation of the Church-Turing thesis, Church’s
Thesis: Logic, Mind and Nature (Adam Olszewski, Bartosz Brozek, and Piotr
Urbanczyk, editors), Copernicus Center Press, Krakow 2013. 100.
Herbert Enderton
[2001] A mathematical introduction to logic, Academic Press, Second edi-
tion. 44.
References 231
Daniel Fredholm
[1995] Intensional aspects of function definitions, Theoretical Computer
Science, vol. 163, pp. 1–66. 125.
Robin Gandy
[1980] Church’s Thesis and principles for mechanisms, The Kleene Sym-
posium (J. Barwise, H. J. Keisler, and K. Kunen, editors), North Holland
Publishing Co, pp. 123–148. 99.
Sheila A. Greibach
[1975] Theory of program structures: Schemes, Semantics, Verification,
Lecture Notes in Computer Science, vol. 36, Springer-Verlag. 58.
Yuri Gurevich
[1995] Evolving algebras 1993: Lipari guide, Specification and validation
methods (E. Börger, editor), Oxford University Press, pp. 9–36. 100.
[2000] Sequential abstract state machines capture sequential algorithms,
ACM Transactions on Computational Logic, vol. 1, pp. 77–111. 100.
Neil D. Jones
[1999] LOGSPACE and PTIME characterized by programming languages,
Theoretical Computer Science, pp. 151–174. 97.
[2001] The expressive power of higher-order types or, life without CONS,
Journal of Functional Programming, vol. 11, pp. 55–94. 97.
Stephen C. Kleene
[1952] Introduction to metamathematics, D. Van Nostrand Co, North
Holland Co. 4, 57, 63.
[1959] Recursive functionals and quantifiers of finite types I, Transactions of
the American Mathematical Society, vol. 91, pp. 1–52. 100.
D. E. Knuth
[1973] The Art of Computer Programming, Volume 1. Fundamental Algo-
rithms, second ed., Addison-Wesley. 100.
[1981] The Art of Computer Programming, Volume 2. Seminumerical algo-
rithms, second ed., Addison-Wesley. 24.
232 References
Saul A. Kripke
[2000] From the Church-Turing Thesis to the First-Order Algorithm Theo-
rem, Proceedings of the 15th Annual IEEE Symposium on Logic in Computer
Science (Washington, DC, USA), LICS ’00, IEEE Computer Society, The
reference is to an abstract. A video of a talk by Saul Kripke at The 21st Inter-
national Workshop on the History and Philosophy of Science with the same title
is posted at [Link] and this is
my only knowledge of this article. 99.
J. van Leeuwen
[1990] Handbook of theoretical computer science, vol. A, Algorithms and
Complexity, Elsevier and the MIT Press. 230.
Zohar Manna
[1974] Mathematical theory of computation, Originally published by
McGraw-Hill, available from Dover. 20, 49.
John McCarthy
[1960] Recursive functions of symbolic expressions and their computation
by machine, Part I, Communications Of the ACM, vol. 3, pp. 184–195. 49.
[1963] A basis for a mathematical theory of computation, Computer pro-
gramming and formal systems (P. Braffort and D Herschberg, editors), North-
Holland, pp. 33–70. 49, 52.
Gregory L. McColm
[1989] Some restrictions on simple fixed points of the integers, The Journal
of Symbolic Logic, vol. 54, pp. 1324–1345. 60.
João Meidânis
[1991] Lower bounds for arithmetic problems, Information Processing Let-
ters, vol. 38, pp. 83–87. 201.
References 233
Yiannis N. Moschovakis
[1984] Abstract recursion as a foundation of the theory of algorithms, Com-
putation and proof theory (M. M. Richter et al., editors), vol. 1104, Springer-
Verlag, Berlin, Lecture Notes in Mathematics, pp. 289–364. 3, 59.
[1989a] The formal language of recursion, The Journal of Symbolic Logic,
vol. 54, pp. 1216–1252 3, 49, 99, 100. Posted in ynm’s homepage.
[1989b] A mathematical modeling of pure, recursive algorithms, Logic at
Botik ’89 (A. R. Meyer and M. A. Taitslin, editors), vol. 363, Springer-Verlag,
Berlin, Lecture Notes in Computer Science, pp. 208–229 100. Posted in ynm’s
homepage.
[1998] On founding the theory of algorithms, Truth in mathematics (H. G.
Dales and G. Oliveri, editors), Clarendon Press, Oxford, pp. 71–104 3, 100,
101. Posted in ynm’s homepage.
[2001] What is an algorithm?, Mathematics unlimited – 2001 and beyond
(B. Engquist and W. Schmid, editors), Springer, pp. 929–936 3. Posted in
ynm’s homepage.
[2003] On primitive recursive algorithms and the greatest common divisor
function, Theoretical Computer Science, vol. 301, pp. 1–30. 125.
[2006] Notes on set theory, second edition, Undergraduate texts in mathe-
matics, Springer. 19.
[2014] On the Church-Turing Thesis and relative recursion, Logic and Science
Facing the New Technologies (Peter Schroeder-Heister, Gerhard Heinzmann,
Wilfrid Hodges, and Pierre Edouard Bour, editors), College Publications,
Logic, Methodology and Philosophy of Science, Proceedings of the 14th In-
ternational Congress (Nancy), pp. 179–200 99. Posted in ynm’s homepage.
A. M. Ostrowski
[1954] On two problems in abstract algebra connected with Horner’s rule,
Studies presented to R. von Mises, Academic Press, New York, pp. 40– 48. 209.
V. Ya. Pan
[1966] Methods for computing values of polynomials, Russian Mathematical
Surveys, vol. 21, pp. 105–136. 211.
Christos H. Papadimitriou
[1994] Computational complexity, Addison-Wesley. 4.
234 References
Rózsa Péter
[1951] Rekursive funktionen, Akadémia Kiadó, Budapest. 58.
Gordon Plotkin
[1977] LCF considered as a programming language, Theoretical Computer
Science, vol. 5, pp. 223–255. 3.
[1983] Domains, Posted on Plotkin’s homepage. 3.
Vaughan Pratt
[1975] Every prime has a succint certificate, SIAM Journal of computing,
vol. 4, pp. 214–220. 143.
[2008] Euclidean gcd is exponentially suboptimal: why gcd is hard to analyse,
unpublished manuscript. 85.
Hartley Rogers
[1967] Theory of recursive functions and effective computability, McGraw-
Hill. 4.
Gerald E. Sacks
[1990] Higher recursion theory, Perspectives in Mathematical Logic,
Springer. 100.
J. Stein
[1967] Computational problems associated with Racah Algebra, Journal of
Computational Physics, vol. 1, pp. 397Ű– 405. 24.
Z. W. Sun
[2000] On integers not of the form ±pa ± q b , Proceedings of the American
Mathematical Society, vol. 208, pp. 997–1002. 165.
References 235
Terence Tao
[2011] A remark on primality testing and decimal expansions, Journal of
the Australian Mathematical Society, vol. 91, pp. 405– 413. 165.
Alfred Tarski
[1986] What are logical notions?, History and Philosophy of Logic, vol. 7,
pp. 143–154, edited by John Corcoran. 152.
Jerzy Tiuryn
[1989] A simplified proof of DDL < DL, Information and Computation,
vol. 82, pp. 1–12. 97, 98.
Anush Tserunyan
[2013] (1) Finite generators for countable group actions; (2) Finite index
pairs of equivalence relations; (3) Complexity measures for recursive programs,
Ph.D. Thesis, University of California, Los Angeles, Kechris, A. and Neeman,
I., supervisors. 118, 121, 123.
Alan M. Turing
[1936] On computable numbers with an application to the Entscheidung-
sproblem, Proceedings of the London Mathematical Society, vol. 42, pp. 230–
265, A correction, ibid. volume 43 (1937), pp. 544–546. 99.
Shmuel Winograd
[1967] On the number of multiplications required to compute certain func-
tions, Proceedings of the National Academy of Sciences, USA, vol. 58, pp. 1840–
1842. 212.
[1970] On the number of multiplications required to compute certain func-
tions, Communications on pure and applied mathematics, vol. 23, pp. 165–179.
212.
Symbol index
Fk , 24 L<ù , 12
L∗ , 12 ∼∞ , 8
Ai , 70 Nst , 25
C, 30 where , 17
F, 30 where , 49
L∗ , 30
N, 30 (U, x~ ), 34
N0 , 171 Bm (~a ), 160
Nk-ary , 30 D(M ), 104
Nε , 24, 30 E(~v), 38
Nb , 30 F [~
u ], F (~u ), 209
Nd , 159 F p (M ), 121
Nu , 30 Gm [X ], 33
NPres , 44 K [T ], 191
NPd , 97 S(n), 7
R, 30 X : h, 193
B, 9 [0, 2N ), 203
|X |, 9 em2 (x), 30
cde, 8, 192 Expl(A), 39
dxe, 7 Gm (~x ), G∞ (~ x ), 34
C, 7 Lp (M ), 108
T , 12, 13 Ls (M ), 107
T 0 , 13 om2 (x), 30
Tu , 13 Rec(A), 52
I, 9 Rec0 (A), 52
≡, 12 Recnd (A), 83
bxc, 7 Rec0nd (A), 83
A Tailrec(A), 64
, 141
A
c , 141 Tailrec0 (A), 61
ϕ, ϕ̂, 27 arity(φ), 30
Z, 7 ÷R (~x ), 9
|=c , 133 Timei (x), 70
N, 7 eqdiag(A), 32
nil, 12 first(z), 80
M , 103 head(u), 12
Lind , 159 Compi (x), 70
K, 218 Z[T ], 191
Q, 7 iqm (x), 8
R, 7 ìy, 57
>> , 15 Pd(n), 7
238 Symbol index
implementations, 73, 100 open problem, 65, 98, 99, 114, 125,
input, output sets, 9 126, 202, 208
intrinsic complexities, 144 operations on functionals, see func-
iterator, 69–70 tional
explicit representation, 71 optimality and weak optimality, 150–
nondeterministic, 82 151
output complexity, 146
Kleene strong equality, ', 10
pairing scheme, 80
ë-abstraction, 11 parallel calls complexity,
Lamé’s Lemma, 27 see depth-of-calls complex-
Liouville’s Theorem, 180 ity 111
logic of programs, 97 parallel logical complexity, 108
logical extension, 152 partial function, f : X * W , 9,
lookup algorithm, 205 see also functional
finite, 9
Main Conjecture, 2, 151 RAM computable, 91
mangling, see functional register computable, 90
many-sorted structure, see struc- strict composition, 10
ture partial multiple valued (pmv) func-
minimalization, ìy, 57 tion, 84, see also func-
monotone, see functional tional
Morris example, 20 partial ring homomorphism, 210
mutual tail recursion, 61 partial structure, see structure
Pell pairs, 177, 181
N -bit numbers, 203 Pell’s equation, 177
natural numbers, N, 7 Φ-structure, same as structure, 30
nd, same as nondeterministic Φ-terms, 36
nested recursion, 57 pointed structure, 59
non-uniform (bit) complexity, 203 minimal pointed extension, 60
nondeterministic iterator, see iter- polynomial evaluation, 25, 209
ator Pratt certificate, see certificate
nondeterministic programs, see re- Pratt’s nuclid algorithm, 85, 188
cursive programs predecessor arithmetic, 97
nondeterministic recursive machine, predecessor, Pd(x), 7
see recursive machine Presburger structure NPres , 44
Normal Form Theorem, 63 primitive recursion, 56, 68, 125
nullity, 0-testing, 25, 209 process, 130, see also uniform process
number-of-calls complexity, induced by a program, 130
c s (Φ0 )(~
x ), 110 example of non-uniform, 133
products, 9
obstruction to calls(A, R, x
~ ) = 0, programs, see recursive programs
147 pure term, 37
obstruction to depth(A, R, x~ ) = 0,
148 random access machines, 91
242 General index
extended, 61
terms, 36
the binary (Stein) algorithm, 24
the binary-insert-sort algorithm, 27
the Euclidean algorithm, 23
coprimeness by the Euclidean,
24
the insert-sort algorithm, 26
the merge-sort algorithm, 21
tree-depth complexity, D(M ), 104
trees, 12
v below u, u v v, 13
children, 13
degree, 13
depth, 13
splitting depth, 13
leaf, 13
nodes, 12
root, 12
size, 13
splitting, 13
subtree, 13
Tserunyan’s first theorem, 121
Tserunyan’s second theorem, 123
vocabulary, 29
infinite, 31