Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider the following extension of polynomials. The rational exponential expressions (REXes) are given by:

  1. The leaves 1 and $x$ for $x$ drawn from a class of variables; and
  2. Closed under the binary functions of addition, multiplication, exponentiation, and division.

This is a restriction to positive constants of a class of expressions studied in Brown, 1969, "Rational Exponential Expressions and a Conjecture Concerning π and e". Buchberger & Loos, 1982, "Algebraic Simplification", sect. 6, mention the existence of algorithms for finding canonical forms for these expressions, but say their correctness depends on number-theoretic conjectures that have not been settled.

I'm interested in a decision procedure for dominance, where for two REXes in one variable, $f$ and $g$, $f \leq g$ if $\exists N \in {\mathbb N}.\forall n \in {\mathbb N}. N \leq n \implies f(n) \leq g(n)$. Do we have either the existence of canonical forms, or decidability for this problem?

share|improve this question
    
Could you clarify the precise sense of "monomial" that you mean here? And you only have one variable for the decision problem? And you only require dominance for integer n in that question? (And you may want to add the logic tag.) –  Joel David Hamkins Jan 26 '10 at 19:13
    
It looks like it would make sense either with unary exponentiation exp(x) and with binary exponentiation y^x. Which do you mean? –  Douglas Zare Jan 26 '10 at 20:04
    
@Charles: Heh. The 'poly' in polynomial does not refer to the multiplicity of variables but of terms... You'd only improve your question by replacing 'monomial' by a more usual description. Also, please do not make corrections and clarifications to the question in the comments but in the actual question: you can edit it! –  Mariano Suárez-Alvarez Jan 26 '10 at 22:02
    
Joel: logic tag? My interest in the problem does stem from ordinal analysis, but the link is too obscure to justify it on those grounds. Why else might it count as logic? –  Charles Stewart Jan 27 '10 at 10:08
    
It seems logic related, since (i) you are considering terms in a formal language, and (ii) you are asking a decidability question. Also, the paper to which you link seems to engage with several logic issues, including the MRDP theorem. –  Joel David Hamkins Jan 27 '10 at 15:02
show 1 more comment

3 Answers

Yes, there are algorithms to decide asymptotic dominance - in fact for a much wider class of elementary functions. I discovered the first such algorithm circa 1980 while an undergrad member of the MIT Mathlab group researching effective algorithms for computing limits for the Macsyma symbolic computation system. Another different algorithm was discovered independently a handful of years later by John Shackell. You should be able to find references to the literature by googling the more recent buzzword "transseries". Many computer algebra systems have (partial) implementations of these algorithms. Here's an example of my algorithm on (my generalization of) an example Rich Schroeppel proposed to attempt to stump my algorithm (he was convinced no such algorithm existed). It shows that $\rm{\: lim_{x\to\infty}\ d40 = e^a}$ alt text
Don't dare try L'Hopital's rule on that monster!
For further discussion (and the text form of the above image)
see my post on sci.math, 1996/03/20, L'Hospital's rule question
http://groups.google.com/group/sci.math/msg/05298104ac44efd2
http://groups.google.com/groups?selm=WGD.96Mar20231913%40berne.ai.mit.edu

share|improve this answer
    
I've finally got around to get an idea of what is going on with transseries. So, as I understand it, by tuning the construction of a class of transmonomials (typically an inverted order), you can represent certain spaces of function as infinite power series over these. I haven't seen how transseries, which seem to be uncountable, are represented in computer algebra systems, and how, given heterogenous transmonomials P < P' and Q < Q', we can decide whether PQ' < P'Q. –  Charles Stewart Feb 8 '12 at 12:43
add comment

The integers are a red herring. All of the rational exponential expressions are logarithmico-exponential functions in the sense of Hardy. Therefore, for any such $f$ and $g$, either $f(t) > g(t)$ for all sufficiently large real $t$, $f(t) < g(t)$ for all sufficiently large real $t$ or $f(t)=g(t)$. There is no reason to restrict to the case that $t$ is an integer.

I highly suspect that this problem is decidable, but I don't actually know this. This is the sort of thing that people who study transseries think about.

share|improve this answer
    
I copied these links from the related question: mathoverflow.net/questions/3057/… –  David Speyer Jan 27 '10 at 17:17
    
In the case of multi-variable polynomials, the difference between the reals and the integers is the difference between decidability and undecidability. This is becasue Tarski's theorem shows that the decision problem for whether p(x1,...,xn) = 0 has a solution is decidable in the reals, but MRDP shows it is undecidable in the integers. But I agree that the question is likely decidable in the one-variable case. –  Joel David Hamkins Jan 27 '10 at 18:17
    
This "eventual trichotomy" property is something I had been thinking about: thank you for the reference (and cf. archive.org/details/ordersofinfinity00harduoft); I must clearly study the proof. I'll take a look at the transseries intro paper; this is a new field for me. –  Charles Stewart Jan 28 '10 at 11:02
2  
The crucial difficulty is that all proofs of the sign preservation at infinity for Hardy functions I know have the following logical step in some form: if the derivative preserves sign near infinity, then the function itself preserves sign near infinity. This is completely useless from the computational standpoint because it doesn't allow you to figure out which of the 2 possible signs the function preserves in finite number of steps. The transseries approach clearly has a similar problem. You have to decide if infinitely many terms are equal before you can proceed to the next order terms. –  fedja Jan 28 '10 at 12:53
add comment

I don't have an answer to the one-variable decision question that you asked.

But you did introduce multi-variable expressions, and there are some fascinating results on the multi-variable analogue of your domination problem. (Perhaps you know all this already...) That is, given two rational exponential expressions f(x1,...,xk) and f(x1,...,xk), the problem is to decide whether f(n1,...,nk) <= g(n1,...,nk), for all positive integers (n1,...,nk) except at most finitely often.

The answer is that this decision problem is undecidable, and it is undecidable even for polynomial expressions. There is no algorithm that will tell you when one multi-variable (positive) polynomial expression eventually dominates another.

The reason is that the decision problem of Diophantine equations is encodable into this domination problem. That work famously shows that the problem to decide if a given integer polynomial p(x1,...,xk) has a zero in the integers is undecidable. This is the famous MRDP solution to Hilbert's 10th problem.

It is easy to reduce the Diophantine problem to the domination problem, as follows. First, let us restrict to non-negative integers, for which the MRDP results still apply. Suppose we are given a polynomial p(x1,...,xk) expression over the integers, and want to decide if it has a solution in the natural numbers. This expression may involve some minus signs, which your expressions do not allow, but we will take care of that by moving all the minus signs to one side. Introduce a new variable x0 and consider the domination problem:

  • Does 1 <= (1+n0)p(n1,...,nk)2 for all natural numbers except finitely often?

We can expand the right hand side, and move the negative signs to the left, to arrive at an instance of your domination problem, using only positive polynomials. Now, if p(n1,...,nk) is never 0, then the answer to the stated domination problem is Yes, since the right hand side will always be at least 1 in this case. Conversely, if p(n1,...,nk) = 0 has a solution, then we arrive at infinitely many violations of domination by using any choice of n0. Thus, if we could decide the domination problem, then we could decide whether p(n1,...,nk) = 0 has solutions in the natural numbers, which we cannot do by the MRDP theorem. QED

I think the best situation with the Diophantine equations is that it remains undecidable with nine variables, and so the domination problem I described above is undecidable with ten variables. (Perhaps Bjorn Poonen will show up here and tell us a better answer?)

Of course, this doesn't answer the one-variable question that you asked, and probably you know all this already.

My final remark is that if one can somehow represent the inverse pairing function, then one will get undecidability even in the one variable case. That is, let f(n,m) = (n+m)(n+m+1)/2 + m be one of the usual pairing functions, which is bijective between ω2 and ω. Let p be the function such that p(f(n,m)) = n, the projection of the pairs onto the first coordinate. If the expressions are enriched to allow p, then one can in effect work with several variables by coding them all via pairing into one variable, and in this case, the domination problem in the one-variable case, for rational exponential expressions also allowing the function p, will be undecidable. It would seem speculative to suppose that p is itself equivalent to a rational exponential expression, but do you know this?

share|improve this answer
    
I think that, if we add inverse pairing functions to Diophantines, we can only code up undecidable problems if we have two variables: we can't existentially quantify over the variable that ranges over the problem set. –  Charles Stewart Jan 28 '10 at 10:40
    
No, one variable will suffice, once we have the inverse pairing function p. First, it is easy to solve the equation to express also the other projection function q. Now, for example, one can think of triples (a,b,c) as coded by iterated pairs n=((a,b),c), and then extract the coordinates from the single variable n using a=p(p(n)), b=q(p(n)) and c=q(n). Thus, any expression in integer variables (a,b,c) can be thought of as an expression just in one variable n. –  Joel David Hamkins Jan 28 '10 at 13:08
    
This doesn't deal with my worry. Consider the non-primeness Diophantine set characterised by (a+2)*(b+2)-n=0. The variable n plays a different role in determining the set of non-prime numbers: the a and b are existentially quantified, while the n is the argument to the predicate. I don't see how variables of different roles in this sense can be usefully simplified with pairing/projection functions. –  Charles Stewart Jan 29 '10 at 19:08
    
What I am claiming is that for every multivariable integer domination problem f(a,b,c) <= g(a,b,c), there is an equivalent single variable problem F(n) <= G(n), using rational expressions involving the inverse pairing function, such that the original inequality holds except finitely often iff the new inequality holds except finitely often. And the proof of this is to think of n as coding the triple (a,b,c) via the polynomial coding function, and then replace all occurences of a with p(p(n)), all occurences of b with q(p(n)) and c with q(n). Your non-primeness set is not a domination problem. –  Joel David Hamkins Jan 29 '10 at 20:05
    
Got it! Thanks. Given the space of possible pairing/projection functions, the issue isn't easy to dismiss. –  Charles Stewart Jan 29 '10 at 21:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.