The Saga of the High School Identities

Stanley Burris and Karen Yeats

Abstract. This paper surveys and updates results and open problems related to the variety defined by the High School Identities as well as the variety generated by the positive numbers with exponentiation.

The set of eleven basic identities of the positive integers N with the operations +, ×, ↑ which one learns in high school are as follows (the subset not involving exponentiation is called ĤSI):

HSI  \{ \frac{ĤSI  \{ \begin{matrix}(1) & x + y ≈ & y + x \\ (2) & x + (y + z) ≈ & (x + y) + z \\ (3) & x · 1 ≈ & x \\ (4) & x · y ≈ & y · x \\ (5) & x · (y · z) ≈ & (x · y) · z \\ (6) & x · (y + z) ≈ & (x · y) + (x · z) \end{matrix}}{\begin{matrix}(7) & 1^{x} ≈ & 1 \\ (8) & x^{1} ≈ & x \\ (9) & x^{y+z} ≈ & x^{y} · x^{z} \\ (10) & (x · y)^{z} ≈ & x^{z} · y^{z} \\ (11) & (x^{y})^{z} ≈ & x^{y·z}. \end{matrix}}

These can be found in Dedekind’s 1888 monograph [7] Was Sind Und Was Sollen Die Zahlen?—they are derived from the natural numbers with the successor operation. They are among the oldest and most familiar of the equational theories in mathematics.

Our first (and perhaps most important) models of these two sets of identities are

N = (N, +, ×, ↑, 1)  N̂ = (N, +, ×, 1)

Obvious questions to ask about the identities of these two well known algebras concern:

• Axioms for their equational theories, and the

• Decidability of their equational theories.

Date: July 31, 2002.

Research of the first author was supported by a grant from NSERC.

Research of the second author was supported by a NSERC Undergraduate Research Grant.

It has long been known that

(a) ĤSI is a finite set of axioms for the equational theory of N̂, and

(b) the equational consequences of ĤSI, that is, the equations true of N̂, are

decidable. One sees this by noting that every N̂ term t(x⃗), that is, a term in the language {+, ×, 1} of N̂, has a normal form, namely a polynomial p(x⃗). There is a straight forward effective procedure to find this normal form, namely by multiplying out and collecting terms. By classical algebra it is clear that an equation s(x⃗) ≈ t(x⃗) follows from ĤSI iff both sides have the same polynomial as their normal form. This is all one needs to prove that ĤSI is a basis for the equational theory of N̂ and that this equational theory is decidable.

However when we turn to study HSI and N we no longer have the benefit of such normal forms, the situation becomes immensely more complicated, and there are many open questions.

1. Models of HSI

When looking for natural models of ĤSI one not only has the algebra N̂ but also the familiar number systems yield models: the integers, the rationals, the reals, and the complex numbers; and one can take the nonegative [positive] integers, rationals, or reals.

However when we turn to find natural models of HSI many of these possibilities evaporate, e.g., the positive rationals are not closed under ↑. One of the most fascinating that survives (see §2) is the positive reals R^{+} = (R^{+}, +, ×, ↑, 1).

Another natural model was found by G. Birkhoff [2] (1942)—he showed that HSI holds for the algebra of posets^{1} where the operations are given by:

+ is disjoint union
× is cartesian product
↑ is order preserving maps

Consequently they also hold for the algebra of cardinal numbers. Aside from some examples in topos theory^{2} we know of few other natural models of HSI that have been studied.

1.1. The Smallest Submodels. This and the next subsection draw heavily on the papers [3] (1992) and [4] (1993) of Burris and Lee.

Every model of HSI has a smallest submodel, namely the subalgebra generated by the constant 1. The elements of this submodel are just 1,2,3, etc., where

2 := 1+1 3 := 2+1 etc.

1In a footnote Birkhoff says that Tukey pointed out that HSI holds more generally for preorders (= reflexive + transitive).

2D. Higgs examined several topoi in the hopes of finding a natural countermodel to Wilkie’s identity (see Section 5). So far no such countermodel has been found.

since these elements include 1 and are closed under addition, multiplication and exponentiation. We call these elements the integers of the model.

If the set of integers of a model of HSI is infinite then it is a copy of N, the free HSI algebra freely generated by Ø. On the other hand if the set of integers is finite then it must give a submodel that looks like Fig. 1, the quotient of N defined by

Figure 1. A finite quotient N_{a,k} of N

a ≈ a + k.

Not every positive a and k gives a quotient of N as pictured in Fig. 1—each picture does support addition and multiplication, but not necessarily exponentiation. It is routine to show that the congruences of N̂ are the relations ≡_{a,k} defined by (i, j) ∈≡_{a,k} iff i = j, or i, j ≥ a and i ≡ j mod k. We want to know the a, k for which ≡_{a,k} is a congruence of N, that is, when is ≡_{a,k} compatible with exponentiation. This is equivalent to the condition x^{a} ≡_{a,k} x^{a+k} holds for x ∈ N, which leads to the fascinating divisibility conditions in the following theorem (for a complete proof see [3]).

Theorem 1.1. The finite quotients of N are the N_{a,k} where a, k ∈ N satisfy (for all primes p):

p^{e}|k ⇒ e ≤ a
p|k ⇒ (p − 1)|k.

The next corollary gives a complete list of the five “circle” integer HSI-algebras, i.e., those with a = 1, and hence no “tail”. These give the examples of rings Z/(k) that support exponentiation (with 0^{0} = 0).

Corollary 1.2. N_{1,k} is a quotient of N iff k ∈ {1, 2, 6, 42, 1806}.

Already in the most elementary study of the quotients of N, the N_{a,k}, we run into an interesting question in the theory of numbers. Given a ∈ N define the sequence of primes Σ_{a} = (p_{1}, p_{2}, ⋯) by

• p_{1} = 2;

• given p_{1}, …, p_{i}, let p_{i+1} be the smallest prime p which is greater than p_{i} and such that (p − 1)|(p_{1} ⋯ p_{i})^{a}, assuming such a p exists. If no such p exists then Σ_{a} terminates with p_{i}.

Proposition 1.3. Given a positive integer a, there are infinitely many N_{a,k} iff the sequence of primes Σ_{a} is infinite.

Note that Σ_{1} = (2, 3, 7, 43), a finite sequence.

Problem 1. Is Σ_{a} finite for all (any) a > 1?

About 20% of the primes below 10,000,000 are in

Σ_{2} = (2, 3, 5, 7, 11, 13, 19, 23, …, 9999749, 9999973, …).

So even if Σ_{2} is finite, a computer enumeration does not look feasible.

Conjecture 1. Σ_{a} is infinite for a > 1, with asymptotic density zero in the set of primes.

To show the first part of the conjecture holds it suffices to show Σ_{2} is infinite as Σ_{a} ⊊ Σ_{a+1}.

1.2. The Five Two-Element Models of HSI. It is a routine exercise to verify that there are exactly five two-element models of HSI, and they are:

(1)  \begin{matrix}+ & 1 & a \\ 1 & 1 & 1 \\ a & 1 & a \end{matrix}  \begin{matrix}× & 1 & a \\ 1 & 1 & a \\ a & a & a \end{matrix}  \begin{matrix}↑ & 1 & a \\ 1 & 1 & 1 \\ a & a & 1 \end{matrix}

(2)  \begin{matrix}+ & 1 & a \\ 1 & 1 & 1 \\ a & 1 & a \end{matrix}  \begin{matrix}× & 1 & a \\ 1 & 1 & a \\ a & a & a \end{matrix}  \begin{matrix}↑ & 1 & a \\ 1 & 1 & 1 \\ a & a & a \end{matrix}

(3)  \begin{matrix}+ & 1 & a \\ 1 & 1 & a \\ a & a & a \end{matrix}  \begin{matrix}× & 1 & a \\ 1 & 1 & a \\ a & a & a \end{matrix}  \begin{matrix}↑ & 1 & a \\ 1 & 1 & 1 \\ a & a & a \end{matrix}

(4)  + 1 2 1 2 2 2 2 2  \begin{matrix}× & 1 & 2 \\ 1 & 1 & 2 \\ 2 & 2 & 2 \end{matrix}  \begin{matrix}↑ & 1 & 2 \\ 1 & 1 & 1 \\ 2 & 2 & 2 \end{matrix}  N_{2,1}

(5)  + 1 2 1 2 1 2 1 2  \begin{matrix}× & 1 & 2 \\ 1 & 1 & 2 \\ 2 & 2 & 2 \end{matrix}  \begin{matrix}↑ & 1 & 2 \\ 1 & 1 & 1 \\ 2 & 2 & 2 \end{matrix}  N_{1,2}

Clearly algebras (4) and (5) satisfy all the identities of N as they are quotients of N. But an astonishing fact is that we do not yet know if any of the three other two-element algebras satisfy all of the identities of N.

Problem 2. Are any of the algebras (1)–(3) in the variety generated by N?

By taking the variety generated by each of these two-element models of HSI we easily have many other recognizable models of HSI. In four of the cases below exponentiation is the first projection function π (defined by π(a, b) = a).

• Let H = ⟨H, ∨, ∧, →, 0, 1⟩ be a Heyting algebra.

Then H^{⋆} = ⟨H, ∨, ∧, ←, 1⟩ is an HSI-algebra, where a ← b is defined to be b → a.

• Let D = ⟨D, ∨, ∧, 1⟩ be a distributive lattice with 1. Then ⟨D, ∨, ∧, π, 1⟩ is an HSI-algebra.

• Let S = ⟨S, ∧, 1⟩ be a semilattice with 1. Then ⟨S, ∧, ∧, π, 1⟩ is an HSI-algebra.

• Let S = ⟨S, ∧, 0, 1⟩ be a semilattice with 0,1.

Then ⟨S, f, ∧, π, 1⟩ is an HSI-algebra, where f is the binary constant map whose value is always 0.

• Let R = ⟨R, +, ×, 0, 1⟩ be a Boolean ring. Then ⟨R, +, ×, π, 1⟩ is an HSI-algebra.

2. G.H. Hardy’s “Orders of Infinity”

One of the most important tools for studying the identities of N has been G.H. Hardy’s monograph [13] (1921) on the partial functions defined by the terms of the partial algebra on the reals R that we call R_{H}:

R_{H} = (R, +, −, ×, ÷, (^{^{n} √})_{n∈N}, exp, log, (r)_{r∈R}).

Let H be the set of partial functions defined by R_{H} terms t(x), and let H_{∞} be the set of f ∈ H such that f is eventually defined on the reals, that is, defined for sufficiently large values of x. (He called H_{∞} the set of logarithmico-exponential functions.) Hardy considered the following relation ≺ between functions that are eventually defined on the reals:

f ≺ g means f is eventually less than g, and proved the following fundamental result.

Theorem 2.1 (Hardy [13], Theorem 13). Given f, g ∈ H_{∞} either f ≺ g or g ≺ f or f is eventually equal to g.

Thus two distinct H_{∞}-functions cannot weave back and forth infinitely often, that is, we cannot have the situation suggested by Fig. 2. Note that this almost

Figure 2. Two functions repeatedly intersecting says ≺ defines a linear order on H. However two partial functions from H_{∞} that eventually agree need not agree everywhere they are defined.

To prove the ordering result Hardy introduced the following concepts:

(1) The order of an R_{H} term is the maximal number of nested exponentials and logs in it.

(2) An integral R_{H} term of order at most n is one of the form

∑_{i} α_{i}(x) · e^{β_{i}(x)} · ∏_{j} log γ_{ij}(x)

where the α_{i}(x), β_{i}(x) and γ_{ij}(x) are of order at most n − 1. Usual induction over formulas does not seem to yield Theorem 2.1. Instead

Hardy uses multi-stage induction to show:

an H_{∞}-function with arbitrarily large roots is eventually zero. He uses the fact:

every H_{∞}-function of order at most n is an algebraic expression in integral functions of order at most n.

One of his most important ways of reducing a case to the induction hypothesis is to differentiate, noting that Rolle’s Theorem guarantees:

f(x) has arbitrarily large roots implies f′(x) has arbitrarily large roots (see Fig. 3).

Figure 3. The derivative of f has a root between two roots of f

Corollary 2.2. If f, g ∈ H_{∞} are both defined on (a, ∞) but do not define the same function on (a, ∞) then either f ≺ g or g ≺ f.

Proof. This follows from the fact that f and g each have power series expansions in some neighborhood of any b ∈ (a, ∞), so if they are eventually equal then they are equal on (a, ∞). □

To connect Hardy’s work with R^{+} we first define a translation of terms: given any term t(x⃗) in the language of R^{+} let t^{∗}(x⃗) be the term obtained by replacing subterms of the form u^{v} in t by exp(v log u).

Then we observe that for t a term in the language of R^{+} each t^{∗} gives a partial function of R_{H} that is defined whenever all arguments are positive reals, and for such arguments it agrees with the term function of R^{+} defined by t.

As an immediate corollary we see that the term functions f, g of R^{+} as well as of N satisfy the hypothesis of Corollary 2.2, so ≺ defines a linear order on each of these sets. The set of term functions of N is called Sk (for the set of Skolem functions). We know more about the ordering on the term functions of N.

Theorem 2.3 (Ehrenfeucht [8] (1973)). The set Sk is well-ordered by ≺.

The exact order type of Sk under ≺ is not known.

Conjecture 2. (See [11], p. 8) ϵ_{0} is the order type of (Sk, ≺).

Using Corollary 2.2 we have the following result.

Theorem 2.4 (Macintyre [16] (1981)). V (N) = V (R^{+}).

Proof. As N is a subalgebra of R^{+} it suffices to show that each identity of N is also an identity of R^{+}.

First consider a one variable identity s(x) ≈ t(x). If this fails in R^{+} then the term functions that s(x) and t(x) define on R^{+} are eventually distinct. Hence they eventually disagree on the integers. So the identity also fails in N.

Now a simple induction on the number of variables shows that every identity of N is an identity of R^{+}. □

Thus in studying the identities of N it is natural to consider switching to the identities of R^{+} and make use of the tools of analysis.

3. Decidability

Hardy’s investigations of the asymptotic behaviour of H_{∞}-functions provided the starting point for investigations into the decidability of the equational theory of N. D. Richardson [21] (1969) built on Hardy’s work to show that the one variable equational theory of N is decidable, that is, one can decide which identities s(x) ≈ t(x) hold in the natural numbers. Richardson’s method was to study the validity of equations in R_{H}. However, before one can even talk about decidability of equations it is necessary to to have a countable language, to eliminate the continuum many real constants available in Hardy’s formulation. If we replace the constants (r)_{r∈R} in the model R_{H} by just the two constants 0, 1 then the language is countable, and furthermore any partial function in Hardy’s set H is defined by a term in the reduced language with the help of real parameters, i.e., it is defined by an expression t(x, r⃗) where t(x, y⃗) is a term using only the two constants 0 and 1, and r⃗ is a sequence of reals.

Richardson modified Hardy’s language a bit further, dropping the radicals and changing the log function to the log of the absolute value. So Richardson was working with the structure

R̃_{H} = (R, +, −, ×, ÷, exp, log | |, 0, 1).

Let H̃ be the set of partial functions defined by the R̃_{H} terms t(x, r⃗) with real parameters r, and let H̃_{∞} be the set of f ∈ H̃ for which f is eventually defined.

It is easy to see that H̃ ⊆ H, so Hardy’s Theorem holds for H̃_{∞}. Furthermore any partial function in H which can be defined without using radicals is also in H̃. In particular, all the term functions of R^{+} appear as restrictions (to the positive reals) of members of H̃_{∞}.

Now that we have a countable language it is possible to formulate a number of open questions concerning decision problems. In the following we write s ≺ t for terms s and t if the corresponding partial functions are in the relation ≺.

Problem 3 (Eventually Defined). Can one decide if a one variable R̃_{H} term t(x) is eventually defined?

Problem 4 (Root Size). Given that an R̃_{H} term t(x) is eventually defined and eventually nonzero, can one give an effective bound on (the size of) the roots of t(x)?

A special case of this is formulated for N.

Problem 5 (Intersection Size). Given that two N terms s(x) and t(x) do not define the same function on N (this is decidable—see Theorem 3.3), can one give an effective bound on the size of the n for which s and t agree?

Problem 6 (Dominance for H̃). Given t(x), an R̃_{H} term that is eventually defined, can one decide if 0 ≺ t(x)?

A special case of the Dominance problem is formulated for N.

Problem 7 (Dominance for Sk). Is there a decision procedure for s(x) ≺ t(x), where s(x), t(x) are terms in the language of N?

Richardson showed that if a decision procedure for Problem 7 exists then one can decide equality for the so-called exponential constants, that is, for the variable free terms in the language +, ×, ÷, ↑, 1.

Gurevic̆ [12] (1986) showed that if one considers only s(x), t(x) ≺ 2^{x^{2}} then Problem 7 is decidable.

3.1. Richardson’s Proof. Note that if t(x, y⃗) is an R̃_{H} term and b⃗ ∈ ℝ are such that t(x, b⃗) is defined on an interval I, then t(x, b⃗) defines a function in C^{∞}(I). Richardson’s main idea was to associate with each R̃_{H} term t a finite sequence of R̃_{H} terms

t_{0}, …, t_{k}

which give important information about the number of distinct zeros of t(x, b⃗) in any interval of definition.

Let us say that a term t(x, y⃗) has the property R(x, k) if there is a sequence of R̃_{H} terms

t_{0}(x, y⃗), …, t_{k}(x, y⃗)

such that

(1) t_{0}(x, y⃗) = t(x, y⃗) and \frac{∂}{∂x}t_{k}(x, y⃗) = 0

(2) For every interval I ⊆ ℝ and every tuple b⃗ ∈ ℝ^{n}, if t(x, b⃗) is defined on I then, for each a ∈ I and each i < k, t_{i+1}(a, b⃗) is defined and

t_{i+1}(a, b⃗) = 0  ⇔  \frac{∂}{∂x}t_{i}(a, b⃗) = 0.

The simplest example is when t(x) is a polynomial.

Example 3.1. Let t(x) be a polynomial of degree k. Then

t(x), t′(x), …, t^{(k)}

is a sequence that shows t(x) has R(x, k).

In this case the length of the sequence is just the degree of the polynomial. However the sequences quickly become more complicated:

Example 3.2. If p(x) is a polynomial of degree k and q(x) is a polynomial of degree ℓ, then for t(x) = exp(p(x)/q(x)) − 1 let r(x) = p(x)q′(x) − q(x)p′(x). The sequence

e^{p(x)/q(x)} − 1, r(x), r′(x), …, r^{(k+ℓ−1)}(x)

shows that t(x) has the property R(x, k + ℓ − 1).

Suppose that t(x, y⃗) is an R̃_{H} term that has property R(x, k). It is easy to show that for any interval I and any tuple b⃗, if t(x, b⃗) is defined in I then

either t(x, b⃗) = 0 on I, or t(x, b⃗) has at most k distinct roots in I. Richardson’s main result is that for each R̃_{H} term t(x⃗) and each variable x_{i} from x⃗

there is an effective procedure to find a nonnegative integer k such that t(x⃗) has property R(x_{i}, k).

It is amazing that one is able to effectively bound the number of roots of t(x, b⃗) on any interval I for which it is defined but not identically 0, but we do not know how to effectively bound the size of the roots in the interval I. (See Problems 4 and 5.)

From Richardson’s result one immediately has:

Theorem 3.3 (Richardson [21] (1969)). The one variable identities s(x) ≈ t(x) of N are decidable.

3.2. Macintyre’s Proof. Macintyre, initially unaware of Richardson’s work, tackled the decidability of the identities of N by refining Hardy’s work, but using the language of R̃_{H}. At each step of Hardy’s induction proof in which t(x, b⃗) is not identically 0 on an interval I, Macintyre effectively computed an upper bound on the number of roots of t(x, b⃗) in I. This allows him to prove the decidability of one variable equations, and then a simple inductive argument gives:

Theorem 3.4 (Macintrye, [16] (1981)). The identities s(x⃗) ≈ t(x⃗) of N are decidable.

We note that Macintyre’s proof of the one variable case requires an excursion into the complex plane, something that the other two published proofs do not.

3.3. Gurevic̆’s Proof. Another proof of the decidability of the equational theory of N was given by Gurevic̆ [9] (1985) using ideas of A. G. Khovanskii. This proof has a resemblance to that of Richardson, with the emphasis on building a chain of terms t_{0}, …, t_{k} linked in some fashion by differentiation. In Gurevic̆’s paper the t_{i} must satisfy

t_{0} = T, t_{k} ∈ Q, \frac{∂t_{j}}{∂x} = \frac{β_{j}t_{j} + t_{j+1}}{α_{j}}

By solving these linear differential equations one sees that the number of roots in I can drop by at most one when passing from t_{j} to t_{j+1}, in any given interval of definition I of t_{0} in which t_{j}(x, b⃗) is not identically 0,

In the same paper Gurevic̆ examines the equational consequences of any finite set Σ of identities true of N that contains the identities

1^{x} ≈ 1,  x^{1} ≈ 1 · x ≈ x · 1 ≈ x.  (3.1)

He gives a decision procedure that takes as input any such Σ and identity s ≈ t and determines if Σ ⊢ s ≈ t. The method is to describe a congruence of the term algebra generated by the finitely many variables of Σ, s and t, that yields a finite quotient whose size is effectively bounded and in which s ≈ t will fail if it is not a consequence of Σ. Thus

Theorem 3.5 (Gurevic̆ [9] (1985)). If Σ is a finite set of identities including (3.1) and true of N then the equational consequences of Σ form a decidable set of identities.

Corollary 3.6 (Gurevic̆ [9] (1985)). The equational consequences of HSI are decidable.

4. The Study of R_{exp}

Our understanding of the first-order theory of

R_{exp} = (R, +, −, ×, exp, 0, 1, <)

has made great strides in the last two decades. The interest in this structure was motivated by the famous result of Tarski that showed the ordered field

R = (R, +, ×, −, 0, 1, <)

has a decidable first-order theory, a result proved by the method of elimination of quantifiers. There are three results that we want to mention here:^{3}

• R_{exp} is O-minimal.

• R_{exp} has a model-complete theory.

• If Schanuel’s conjecture holds then R_{exp} has a decidable first-order theory.

3We are indebted to Charles Steinhorn for an enlightening conversation on the importance of these results.

To see that the study of the first-order theory of R_{exp} impacts our understanding of N we only need to note that y ≈ log x is first-order definable by x ≈ exp y. Thus one can define z ≈ x ↑ y for positive x, y by

(0 < x)&(0 < y)&∃u((x ≈ exp u)&z ≈ exp(yu)).

Then one can see that all term functions of R^{+} are first-order definable in R_{exp}.

4.1. O-minimal. An ordered structure A is said to be O-minimal if every set defined by a first-order formula ϕ(x, a⃗) with parameters a⃗ from A is just a union of finitely many open intervals and finitely many points. In particular this says that a definable subset is either bounded above or contains an interval (a, ∞).

Tarski’s elimination of quantifiers for R easily yields the result that R is Ominimal—after all, a quantifier free formula in a single variable with parameters a⃗ is (effectively equivalent to) a Boolean combination of atomic formulas of the form p(x, a⃗) ≈ 0, where p is a polynomial.

However we do not have elimination of quantifiers for R_{exp}. According to [26], Charbonnel presented an incomplete proof of the O-minimality of R_{exp} in 1991— the gaps were filled by Wilkie.

Hardy’s Theorem from Section 2 is an easy corollary of O-minimality of R_{exp} since any two R_{H} terms s(x) and t(x) can be expressed by first-order formulas of R_{exp} with real parameters, and thus the set of points where s(x) is less than t(x) is definable by a first-order formula of R_{exp} with real parameters.

By O-minimality one also sees that the set of points where a term of R_{H}, or a term of R̃_{H}, is undefined is a union of finitely many open sets and finitely many points.

4.2. Model Completeness. A first-order theory is model complete if every submodel of a model of the theory is an elementary submodel. Although not obvious, this is equivalent to requiring that every first-order formula be equivalent to an existential formula. Hence one can view model completeness as a step toward quantifier elimination. Wilkie [27] (1996) proved that the first-order theory of R_{exp} is model complete. This does not have an immediate bearing on our study of HSI, but it led to the next topic.

4.3. Decidability and Schanuel’s Conjecture. Schanuel’s conjecture says that if z_{1}, …, z_{n} are linearly independent complex numbers over the field Q of rationals then the field extension Q(z_{1}, …, z_{n}, e^{z_{1}}, …, e^{z_{n}}) has transcendence degree over Q at least n. (This conjecture is widely believed to be correct.) The Schanuel Conjecture for the Reals means his conjecture with z_{1}, …, z_{n} restricted to the reals.

Theorem 4.1 (Macintyre and Wilkie [17] (1996)). If Schanuel’s Conjecture for the Reals holds then the first-order theory of R_{exp} is decidable.

Since the term functions of R^{+} are definable by first-order formulas of R_{exp}, it follows that the problems posed at the beginning of Section 3 have positive answers if Schanuel’s conjecture holds.

Corollary 4.2. If Schanuel’s Conjecture [for the reals] holds then the Eventually Defined Problem and the Dominance Problem are decidable, and one effectively has a bound on the Root Size for t(x) for any interval I in which t(x) is defined but not identically zero.

5. Exotic identities of N

By the 1960s there was an interest in determining if HSI actually axiomatizes the equational theory of N. Although the identities were known to be decidable, this did not give a way to determine if there are any exotic identities of N, that is, identities not following from HSI.

5.1. The Wilkie Identity. In 1981 Wilkie circulated a manuscript^{4} [25] showing that the identity

\begin{matrix}((1 + x)^{y} + (1 + x + x^{2})^{y})^{x} · ((1 + x^{3})^{x} + (1 + x^{2} + x^{4})^{x})^{y} \\ ≈ ((1 + x)^{x} + (1 + x + x^{2})^{x})^{y} · ((1 + x^{3})^{y} + (1 + x^{2} + x^{4})^{y})^{x} , \end{matrix}

which we call W (x, y), is indeed an exotic identity of N.

Wilkie’s proof was purely syntactic, using an induction on the length of a supposed derivation of W (x, y) from HSI. This proof was soon augmented by a model theoretic proof of Gurevic̆ [9] (1985). Using the subterms of W (x, y), and a little tweaking, Gurevic̆ constructed a 59-element algebra satisfying HSI but not W (x, y). In Gurevic̆ [10] (1990) we find the following remark (p. 33):

C.W. Henson once asked if there are countermodels to Tarski’s question (whether all valid identities in signature (+, ·, ↑) were derivable) of a very small size, say, 5. Currently I don’t know; my own record was 33 elements and I heard a rumour that someone had pushed the record further to 28 elements.

Since then there has been considerable progress in the search for a smallest counterexample to W (x, y). The second column gives the size of a counterexample that has been found, the third column a lower bound on the size of any counterexample.

R. Gurevic̆  59 elements  [9] (1985)
⋮
R. Gurevic̆  33 elements  (≤ 1990)
S. Burris  28 elements  (1988)
⋮
S. Burris  16 elements  (1990)
S. Lee  15 elements  (1991)
\begin{matrix}S. Burris \\ S. Lee \end{matrix} \}  15 elements  ≥ 7 elements [3] (1992)

4This manuscript was not put in final form and published until 2002.

M. Jackson  14 elements  ≥ 8 elements [15] (1996)
\begin{matrix}S. Burris \\ K. Yeats \end{matrix} \}  13 elements  (2001)
\begin{matrix}S. Burris \\ K. Yeats \end{matrix} \}  12 elements  Fig. 4 (2001)

Conjecture 3. The 12 element algebra in Fig. 4 is a smallest counterexample to Wilkie’s identity.

5.2. How We Found the 12-Element Example. The method used first a lengthy search for possible cores of such an example. If W (x, y) fails in a model of HSI at (a, b) then we call the ĤSI-subalgebra generated by {a} a core of the model. Burris and Lee [3] (1992) state a number of conditions that cores must satisfy, for example, there must be at least three integers.

So first we searched for possible cores. Then we tried to expand the core candidates to models of HSI that failed W (x, y). Again we had some conditions that b must satisfy if W (a, b) is to fail, for example b cannot be in the core generated by a (Jackson [15] (1996)). C-programs were written and a few months of computing needed …

5.3. The Search for Natural Counterexamples to Wilkie’s Identity. The counterexamples to Wilkie that we know are quite intricate and certainly not easy to remember. One can hope for a natural counterexample along the lines of Birkhoff’s algebra of posets. The natural HSI-algebras that we have constructed from relational structures or topologies share features of Birkhoff’s algebra that lead to W (x, y) being satisfied, namely:

(a) elements of the algebra are structures that decompose into sums of components,

(b) exponentiation is given by certain maps, and such decompose into maps on the components, and

(c) product is given by Cartesian product.

Problem 8. Is there is natural counterexample to W (x, y)?

Problem 9. Is there a natural HSI-algebra that is not in V (N)? In particular, is the algebra of [finite] posets in V (N)?

Problem 10. Is there an algebra with fewer than 12 elements that satisfies HSI but is not in the variety generated by N? (See Problem 2.)

5.4. The Smallest Exotic Identity. If s(x) ≈ t(x) is a one-variable equation that holds in N then both sides of the equation define the same Skolem function on N. Thus given two such identities s_{i}(x) ≈ t_{i}(x), i = 1, 2, we say that the first identity is smaller than the second identity if s_{1}(x) ≺ s_{2}(x) holds. Ehrenfeucht’s

14 STANLEY BURRIS AND KAREN YEATS

\begin{matrix}+ & 1 & 2 & 3 & 4 & a & b & c & d & e & f & g & h \\ 1 & 2 & 3 & 4 & 4 & 2 & 3 & d & 3 & 3 & 3 & 3 & 4 \\ 2 & 3 & 4 & 4 & 4 & 3 & 4 & 3 & 4 & 4 & 4 & 4 & 4 \\ 3 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ a & 2 & 3 & 4 & 4 & b & 4 & b & 3 & h & 3 & 3 & 4 \\ b & 3 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ c & d & 3 & 4 & 4 & b & 4 & b & 3 & 3 & 3 & 3 & 4 \\ d & 3 & 4 & 4 & 4 & 3 & 4 & 3 & 4 & 4 & 4 & 4 & 4 \\ e & 3 & 4 & 4 & 4 & h & 4 & 3 & 4 & 4 & 3 & h & 4 \\ f & 3 & 4 & 4 & 4 & 3 & 4 & 3 & 4 & 3 & 4 & 3 & 4 \\ g & 3 & 4 & 4 & 4 & 3 & 4 & 3 & 4 & h & 3 & 4 & 4 \\ h & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \end{matrix}

\begin{matrix}× & 1 & 2 & 3 & 4 & a & b & c & d & e & f & g & h \\ 1 & 1 & 2 & 3 & 4 & a & b & c & d & e & f & g & h \\ 2 & 2 & 4 & 4 & 4 & b & 4 & b & 4 & 4 & 4 & 4 & 4 \\ 3 & 3 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ a & a & b & 4 & 4 & c & b & c & b & h & 4 & 4 & 4 \\ b & b & 4 & 4 & 4 & b & 4 & b & 4 & 4 & 4 & 4 & 4 \\ c & c & b & 4 & 4 & c & b & c & b & 4 & 4 & 4 & 4 \\ d & d & 4 & 4 & 4 & b & 4 & b & 4 & 4 & 4 & 4 & 4 \\ e & e & 4 & 4 & 4 & h & 4 & 4 & 4 & 4 & 4 & h & 4 \\ f & f & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ g & g & 4 & 4 & 4 & 4 & 4 & 4 & 4 & h & 4 & 4 & 4 \\ h & h & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \end{matrix}

\begin{matrix}↑ & 1 & 2 & 3 & 4 & a & b & c & d & e & f & g & h \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & f & 4 & 4 & 4 \\ 3 & 3 & 4 & 4 & 4 & e & 4 & 4 & 4 & g & 4 & e & h \\ 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ a & a & c & c & c & c & c & c & c & c & c & c & c \\ b & b & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ c & c & c & c & c & c & c & c & c & c & c & c & c \\ d & d & 4 & 4 & 4 & f & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ e & e & 4 & 4 & 4 & 4 & 4 & 4 & 4 & h & 4 & 4 & 4 \\ f & f & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ g & g & 4 & 4 & 4 & h & 4 & 4 & 4 & 4 & 4 & h & 4 \\ h & h & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \end{matrix}

Figure 4. A Twelve-Element Counterexample to Wilkie’s Identity

Theorem says that the set of Skolem functions of N are well-ordered by ≺, so one can ask: Problem 11. What is the smallest one variable exotic identity? Conjecture 4 (Gurevic̆ [10] (1990), p. 29). The smallest exotic identity is

(P^{x} + Q^{x})^{2^{x}} · (R^{2^{x}} + S^{2^{x}})^{x} = (P^{2^{x}} + Q^{2^{x}})^{x} · (R^{x} + S^{x})^{2^{x}} where

P = 1 + x
Q = 2 + x
R = 2 + x + x^{3}
S = 4 + x^{2} + x^{3}.

5.5. The Search for Non-Exotic Identities. Considerable effort has been expended to find nice sets S of terms such that any equation true of N that has both sides from S will be a consequence of HSI. C.W. Henson and L.A. Rubel used Nevanlinna theory in [14] (1984) to show that S can be the set of terms that only use exponentiation of variables or constants. Gurevic̆ [11] (1993) extended this work by showing that one can allow exponentiation of polynomials.

6. The Equational Theory of N is not Finitely Axiomatizable

Gurevic̆ [10] (1990) showed that there is no finite set of identities that axiomatize the identities of N. Indeed the following collection of Wilkie style identities in one variable x are true of N but cannot all be derived from any finite subset of the identities true of N (n is odd in the following):

(P^{x} + Q_{n}^{x})^{2^{x}} · (R_{n}^{2^{x}} + S_{n}^{2^{x}})^{x} = (P^{2^{x}} + Q_{n}^{2^{x}})^{x} · (R_{n}^{x} + S_{n}^{x})^{2^{x}}

where

P = 1 + x
Q_{n} = 1 + x + ⋯ + x^{n−1}
R_{n} = 1 + x^{n}
S_{n} = 1 + x^{2} + ⋯ + x^{2n−2}.

Although much of his proof of the non-finitely axiomatizable result is an elementary study of the forms in which terms and equational proofs can be expressed, at one point he needs to go into the complex plane and examine analytic continuations of complex functions around singularities.

References

[1] Chris Arbuthnott, Master’s Thesis, University of Waterloo, 2002(?).

[2] Garrett Birkhoff, Generalized Arithmetic. Duke Math. J. 9 (1942), 283–302.

[3] S. Burris and S. Lee, Small models of the High School Identities. Internat. J. Algebra Comput. 2 (1992), 139–178.

[4] S. Burris and S. Lee, Tarski’s High School Identities. Amer. Math. Monthly 100 (1993), 231–236.

[5] S. Burris and H.P. Sankappanavar, A Course in Universal Algebra. Grad. Texts in Math. 78, Springer-Verlag, 1981. Springer. [Now available online from www.thoralf.uwaterloo.ca]

[6] Bernd I. Dahn, Fine structure of the integral exponential functions below 2^{2^{x}}. Trans. Amer. Math. Soc. 297 (1986), 707–716.

[7] Richard Dedekind, Was sind und was sollen die Zahlen? 8te unveränderte Aufl. Friedr. Vieweg & Sohn, Braunschweig 1960. [English Translation: What are numbers and what should they be? Revised, edited, and translated from the German by H. Pogorzelski, W. Ryan and W. Snyder. RIM Monographs in Mathematics. Research Institute for Mathematics, Orono, ME, 1995.]

[8] A. Ehrenfeucht, Polynomial functions with exponentiation are well ordered. Alg. Universalis 3 (1973), 261-349.

[9] R. Gurevic̆, Equational theory of positive numbers with exponentiation.

Proc. Amer. Math. Soc. 94 (1985), 135–141.

[10] R. Gurevic̆, Equational theory of positive numbers with exponentiation is not finitely axiomatizable. Annal of Pure and Applied Logic 49 (1990), 1–30.

[11] R.H. Gurevic̆, Detecting algebraic (in)dependence of explicitly presented functions (some applications of Nevanlinna theory to mathematical logic). Trans. Amer. Math. Soc. 336 (1993), 1–67.

[12] R.H. Gurevic̆, Transcendental numbers and eventual dominance of exponential functions. Bull. London. Math. Soc. 18 (1986), 560–570.

[13] G.H. Hardy, Orders of Infinity, the ’Infinitar’ Calcul of Paul Du Bois-Reymond. Cambridge University Press. [first ed. 1921] 2nd ed. 1954.

[14] C.W. Henson and L.A. Rubel, Some applications of Nevanlinna theory to mathematical logic: identities of exponential functions. Trans. Amer. Math. Soc. 282 (1984), 1–32.

[15] M.G. Jackson, A note on HSI-identities and counterexamples to Wilkie’s identity. Algebra Universalis 36 (1996), 528–535.

[16] A. Macintyre, The laws of exponentiation. Model theory and arithmetic. (Paris, 1979-1980) Lecture Notes in Math. 890, 185–197. Springer, 1981.

[17] Angus Macintrye and A.J. Wilkie, On the decidability of the real exponential field. Kreiseliana: about and around Georg Kreisel, ed. by P. Olfreddi, 441–467, A.K. Peters, 1996.

[18] David Marker, Khovanskii’s theorem. Algebraic Model Theory, eds. Bradd T. Hart, Alistair H. Lachlan and Matthew A. Valeriote, 181–193, Kluwer Academic Publ., 1997.

[19] Anand Pillay and Charles Steinhorn, Definable sets in ordered structures. I Trans. Amer. Math. Soc. 295 (1986), 565–592.

[20] Julia F. Knight, Anand Pillay and Charles Steinhorn, Definable sets in ordered structures. II Trans. Amer. Math. Soc. 295 (1986), 593–605.

[21] D. Richardson, Solution of the identity problem for integral exponential functions. Zeitschr. f. math. Logik und Grundlagen d. Math. 15 (1969), 333–340.

[22] John Shackell, Growth estimates for exp-log functions. J. Symbolic Computation 10 (1990), 611–632.

[23] Lou van den Dries, A completeness theorem for trigonometric identities and various results on exponential functions. Proc. Amer. Math. Soc. 96 (1986), 345–352.

[24] Lou van den Dries, Hilbert Levitz, On Skolem’s exponential functions below 2^{2^{x}}. Trans. Amer. Math. Soc. 286 (1984), 339–349.

[25] A.J. Wilkie, On exponentiation — a solution to Tarski’s high school algebra problem. Quaderni di Matematica (to appear).

[26] A.J. Wilkie, O-Minimality. Documenta Mathematica, Extra Volume ICM 1998, 1 633–636.

[27] A.J. Wilkie, Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function. J. Amer. Math. Soc. 4 (1996), 1051–1094.

[28] A.J. Wilkie, Schanuel’s conjecture and the decidability of the real exponential field. Algebraic Model Theory, eds. Bradd T. Hart, Alistair H. Lachlan and Matthew A. Valeriote, 223–230, Kluwer Academic Publ., 1997.

Dept. of Pure Mathematics, University of Waterloo, Waterloo, Ont., Canada N2L 3G1

E-mail address: snburris@thoralf.uwaterloo.ca

Dept. of Pure Mathematics, University of Waterloo, Waterloo, Ont., Canada N2L 3G1

E-mail address: kayeats@uwaterloo.ca