Asymptotic notation, multiple variables

Last June I posted an announcement of my paper, "On Asymptotic
Notation with Multiple Variables." In this paper I showed that several
of the commonly-used properties of big-O notation are inconsistent
when applied to functions on more than one variable. I then proposed a
new definition that (I claimed) implies these properties when the
functions within the asymptotic notation are restricted to being
strictly nondecreasing. However, I've recently discovered a fatal flaw
in this definition, so that these properties don't all hold.

I have now revised the paper using a different definition. (I had
actually considered this definition last summer, but rejected it for
reasons I can no longer recall.) The new definition is actually
simpler and yields much simpler proofs than the original. The revised
paper can be found at http://people.cis.ksu.edu/~rhowell/asymptotic.pdf

For those of you who may have the original paper and are curious what
the error was, Theorems 3.8 and 3.9 are invalid. (I'm using the
theorem numbers from a revision dated August 29, 2007 - I don't have a
copy of the version originally posted, but I think the theorem numbers
are the same.) A counter-example for both theorems consists of the
functions f(m, n) = mn and g(m, n) defined to be:

- m^2 for m a power of 2 and n = 0;
- mn otherwise.

No proof is given for Theorem 3.8 - I instead claim that it is not
hard to show (oops). The error in the proof of Theorem 3.9 is that c'
depends on n_1, ..., n_{k-1}.

Rod Howell
Associate Professor
Dept. of Computing and Information Sciences
Kansas State University
http://people.cis.ksu.edu/~rhowell/
.