# Skolem's problem

About 1956, Skolem proposed a very simple problem which has not yet been solved (as far as I know).

Consider the smallest class `Sk` of one place functions over the naturals which contains

• The identity function
• The function with constant value `1`
and whenever it contains `f` and `g` contains also the pointwise sum, product and power:
• f+g
• f.g
• f^g
Define `f < g ` to mean that `g` majorises `f`; ie. that there is some `n` such that `f(m) < g(m)` for all ```m > n ```. For example, the majorisation order between polynomials (in the form `x^n1 + x^n2 + .. x^nk` with `n1 >= n2 >= .. >= nk`) is the same as the lexicographic (dictionary) order of their exponent sequences `(n1,n2,...,nk)`. Given `f : Sk`, define `Sk(f)` to be the class of `g : Sk` such that ```g < f```.

By a result of Hardy (1924) [or was it Richardson?], this order is linear. By a result of Ehrenfeucht (1973, using Kruskal's theorem), `Sk` is wellordered. Skolem's problem/conjecture is that the order-type of `Sk` is `epsilon_0`. (He showed that it is at least `epsilon_0`.)

One might think that there should be a simple solution to this problem. However, all we know so far is that:

• The order type is less that the first critical ```epsilon number``` (`phi_2(0)` in the Veblen hierarchy over `a |-> w^a`). [Levitz]
• The o.t. of `Sk(2^x)` is `w^w`.
• The o.t. of `Sk(2^(2^x))` is `w^(w^w)`.
These partial results are proved in various papers by Hilbert Levitz, Lou van den Dries, and Bernd I. Dahn. I will write down some references when/if I find them again.
• Lou van den Dries and Hilbert Levitz, Transactions of the American Mathematical Society, 286 (1984) pp 339-349. (There is another relevant article by Dahn shortly after in the same journal).
One wonders what happens when we consider expressions in more than one variable.
Peter Hancock