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

I am looking for as general a class as possible of real functions defined on $\mathbb{R}^+$ that are guaranteed to have a finite number of zeroes - no, polynomials are not enough :).

Specifically, consider a class of functions defined like elementary functions, but without allowing for complex constants. It seems to me that such functions must have a finite number of zeros. Any ideas on how to prove this (or counterexmamples)?


Background: What I'm actually looking to do is prove that a real postive function $f:\mathbb{R}^+\to\mathbb{R}^+$ is eventually concave, i.e. there exist $x_0\geq 0$ such that $f(x)$ is concave for every $x\geq x_0$. I know that $f$ is real analytic, increasing and upper bounded, but its exact formula is intractable. It thus suffices to show that $f''$ has a finite number of zeroes and hence my question. The structure of $f''$ is more complicated than a "limited elementary function" described above, but a result on such functions will definitely be a step in the right direction.

share|improve this question
    
Isn't $\log(x+1)$ a counterexample? –  Igor Khavkine Oct 15 '12 at 10:53
    
Why so? It seems to me $log(1+x)$ equals 0 only once... –  Yair Carmon Oct 15 '12 at 11:04
    
You need something better than the vague definition of "elementary function" in Wikipedia. For example (on $\mathbb R$) is $\sqrt{x^2}-x = |x|-x$ supposed to be called "elementary"? I don't think so, but you can't see that from the Wikipedia definition. –  Gerald Edgar Oct 15 '12 at 13:01
    
Can you show us the explicit formula you have for $f$ ? Do you have a differential equation ? –  Lierre Oct 15 '12 at 13:50
    
I meant that $\log(x+1)$ is not eventually concave. Though perhaps I'm misunderstanding something about the motivation part of your question... ah, it seems that for you $f$ is some specific function that you didn't define, rather any function. –  Igor Khavkine Oct 15 '12 at 14:39
show 5 more comments

6 Answers

up vote 5 down vote accepted

Let $\mathcal R$ be any o-minimal expansion of the real ordered field $(\mathbb R,<,0,1,+,-,\cdot)$, and $\mathcal F$ be the class of functions (first-order) definable (with real parameters) in $\mathcal R$. On the one hand, $\mathcal F$ has various nice closure properties (in particular, it is closed under composition, taking inverse functions, and derivatives). On the other hand, o-minimality guarantees that for any $f\in\mathcal F$, $f\colon\mathbb R\to\mathbb R$, its positive set $\{x\in\mathbb R:f(x)>0\}$ is a finite union of points and intervals; in particular, $f$ is eventually positive, eventually negative, or eventually constant $0$.

Note that in practice, theories of structures known to be o-minimal are often also model complete, hence a function is definable iff its graph is a projection of a Boolean combination of positive sets of the basic functions included in its signature.

Wilkie proved that the exponential field $\mathbb R_{\exp}=(\mathbb R,\exp)$ is o-minimal. The class of functions definable in $\mathbb R_{\exp}$ includes the functions mentioned in your question, so the answer to your specific question is positive.

Even larger expansions of $\mathbb R$ are known to be o-minimal. First, by a result of van den Dries, $\mathbb R_\mathrm{an}$ is o-minimal, which is the expansion of $\mathbb R$ by all real-analytic functions $f\colon[0,1]^n\to\mathbb R$ (extended by the constant $0$ function outside $[0,1]^n$ to be defined on the whole of $\mathbb R^n$). Second, the pfaffian closure $\mathcal R_\mathrm{pfaff}$ of any o-minimal expansion $\mathcal R$ of $\mathbb R$ is again o-minimal, due to Speisseger. In particular, $\mathbb R_\mathrm{an,pfaff}$ is o-minimal. (The full definition of the pfaffian closure can be found e.g. in [1]. In particular, it includes all pfaffian functions such as $\exp$.)

[1] Patrick Speissegger, Pfaffian Sets and O-minimality, in: Lecture Notes on O-Minimal Structures and Real Analytic Geometry (C. Miller, J.-P. Rolin and P. Speissegger, eds.), Fields Institute Communications vol. 62, 2012, pp. 179–218, http://dx.doi.org/10.1007/978-1-4614-4042-0_5

share|improve this answer
1  
Thanks! It's also worth to mention Hardy's class $L$ “orders of infinity” that also answers my specific question in the affirmative, c.f. the first theorem in "An extension of hardy's classL of “orders of infinity” " by Michael Boshernitzan. Credit for this reference goes to Prof. Mikhail Sodin from TAU. –  Yair Carmon Oct 16 '12 at 15:10
add comment

I think that the theory of o-minimal structures could provide a good answer to your question. See the Pisa lecture notes of Michel Coste

http://perso.univ-rennes1.fr/michel.coste/polyens/OMIN.pdf

or the book of van den Dries (Tame Topology and o-minimal Structures, 1998).

share|improve this answer
add comment

Emil's answer is the definitive one, but I thought I would add some details. Wilkie's result about $\mathbb{R}_{\exp}$ that he mentions relies in part on Khovanskii's theory of fewnomials.

In a way, Wilkie's theorem is overkill for your purpose, especially if you're interested in elementary function, since Wilkie's result deals with the multitude of definable functions in the expansion that are definable but hard to describe succinctly.

On the other hand, Khovanskii's original result is much more hands on (though in no way constructive), relying on three purely elementary ingredients: perturbation, Rolle's theorem, and the Bezout inequality. So if you need at all to "look under the hood" and see why such a result may be true, you may want to take a look at Khovanskii's book. The beginning is rather accessible and contains a detailed proof of what you need.

share|improve this answer
    
Thanks! I couldn't find a copy of a book online but I did find a paper by Khovanskii titled "Fewnomials and Pfaff Manifolds" - does this also contain what I need? –  Yair Carmon Oct 25 '12 at 12:05
    
The paper should cover the same things. I would still advise you to try for the book though because I would assume it has more context and is more reader-friendly. From where I am, most of the book is available on Google books and Chapter I is probably the most useful for you. –  Thierry Zell Oct 25 '12 at 14:11
add comment

Regarding the statement of you background: The claim that a function $f: \mathbb{R}^+\to \mathbb{R}^+$ bounded and increasing will be concave for every $x \geq x_0$ is in general wrong.

Counterexample: Let us consider for a parameter $a>0$ the function $$ f_a(x) = 1 - e^{-x}(1+1/\sqrt a \sin x) .$$ Obviously, $f_a$ is bounded. Moreover, it is easy to check, that $$ f_a'(x) = 1/\sqrt a \ e^{-x}(\sqrt{a}-\cos x + \sin x) > 0 ,\quad\text{whenever}\quad a > 2 , $$ The second derivative is given by $$ f_a''(x) = 1/\sqrt a\ e^{-x}(2\cos x - \sqrt{a}) $$ and has no sign, whenever $a < 4$. Hence for $a\in (2,4)$ the statement is wrong.

share|improve this answer
    
I don't think that the OP meant the question for ANY function, but for some specific function which is too complicated to describe explicitly. –  Igor Rivin Oct 15 '12 at 14:15
    
I never made such a claim. Instead what I'm saying that if $f$ is increasing and bounded AND $f''$ has finitely many zeros (unlike your proposed counterexample) –  Yair Carmon Oct 15 '12 at 14:58
    
... then $f$ is eventually concave. The "finitely many zeros" issue is the motivation for my actual question. –  Yair Carmon Oct 15 '12 at 15:00
add comment

I'm still not totally clear on the precise question.

Consider classes of functions from (all or part of) $\mathbb{R}^+$ to $\mathbb{R}.$ We might demand that the domain be all of $\mathbb{R}^+$, all but finitely many points of $\mathbb{R}^+$, some union of finitely many sub-intervals or merely a "reasonable" subset. We might also require only finitely many zeros (on the domain) or no zeros. We might even require that the function be positive. If we desire closure under composition, addition, multiplication, subtraction and/or division then some of the domain/range options are compatible and others are not. This applies too if we want to include $\ln(x)$ or other specified functions. In any case, the constant zero function may be an exceptional member with certain restrictions which go unmentioned.

Here is a question, is something like it (related to) what you are asking?

Consider the class $G$ of all functions with domain a subset of $\mathbb{R}^+.$ Let $H$ be smallest subclass which is closed under composition, addition, multiplication, subtraction and division and contains the constant functions along with $x^r$ and $a^x,\log_a(x)$ for $a \gt 0. $ QUESTION: The initially specified functions all have only finitely many zeros. Is this true for all of $H?$ What if we also allow exponentiation $f(x)^{g(x)}?$

Qualifications: Here composition and division may contract the domain. Also, "finitely many zeros" should be understood to mean that the set of zeros is a finite union of intervals some or all of which may be singleton points.

share|improve this answer
    
Actually the initially specified functions have no zeros. One could say "polynomials" but that seems wasteful if one is about to allow addition and multiplication. –  Aaron Meyerowitz Oct 15 '12 at 19:55
add comment

Here is a general algebraic approach which may give you some help.
It may even solve your problem, although I am not promising that.

Clones in universal algebra are sets of functions which are closed under having projections of all arities and functional composition. Although I was not trained to do this, they can be viewed as a graded collection by arity, and one can look at the binary or ternary or (as in your case) unary members of the clone.

A simple result is that if one has a clone generated by a beginning set of functions B, then all the functions of each grade can be determined by B acting on a sufficiently large subset of members of just that grade, without using members of the other grades.

Something that you would like to have happen is to find a clone whose unary grade a) contains only functions with finitely many zeros b) is generated by operations in a small set B which are precisely those used in your target function (which I will call g instead of f''), and c) contains g.

Much as you might like it, that may not happen because B is "too rich" to be able to satisfy condition a). One approach to try is to "thin out" B: create some terms out of functions of B, make a new set B', and hope to make a subclone which will satisfy a). Hopefully you will be able to satisfy c), but thinning out the generating set may also toss out g .

Alternatively, you could look at the (unary grade of the) clone generated by g, or by g and a skilled choice of operations from B. If g's clone already contains functions with infinitely many zeros, then so will any clone that contains g, in which case you will know that a purely clone theoretic approach, even with a judicious choice from B, will not give you what you want.

Even so, don't give up yet. The difference of clones is not a clone but may be useful. You might show that a member of the unary grade either has finitely many zeros or has some property Q, where Q is preserved by the clone generating scheme. Now the hope is to find a helpful property Q which is something that you can demonstrate g does not have.

I realize the above is just an abstract nonsense version of what you already know, but it might be a useful shift in perspective for you.

Gerhard "Ask Me About System Design" Paseman, 2012.10.16

share|improve this answer
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.