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

Is there some existing notation for

\[f(n)\leq g(n)\] for sufficiently large n

Apart from just writing that itself? I'm thinking of something compact like the Landau notation $f\ll g$.

(Apologies if this is too specific for MathOverflow - just close it if so. I was also unsure what tags to add, so just edit it accordingly).

share|improve this question
    
Of course, you realize that the two condition you list are not equivalent? My general impression is that there is not a lot of standard notation for asymptotic relations. –  Harald Hanche-Olsen Jan 6 '10 at 13:30
    
Of course, sorry. I have edited out my dim moment. –  Thomas Bloom Jan 6 '10 at 13:46
14  
Whatever notation you end up picking, please oh please explain it before you use it! –  Mariano Suárez-Alvarez Jan 6 '10 at 15:55

4 Answers 4

up vote 12 down vote accepted

In logic, this relation is called almost less than or equal, and is denoted with an asterisks on the relation symbol, like this: $f \leq^* g$.

For example, the bounding number is the size of the smallest family of functions from N to N that is not bounded with respect to this relation. Under CH, the bounding number is the continuum, but it is consistent with the failure of CH that the bounding number is another intermediate value.

share|improve this answer
    
For example, in variations of this terminology set theorists often speak of the almost inclusion relation $A \subset^* B$, which means that A-B is finite. More generally, we have an ideal I and we use this notation to mean that A-B is in I. The structure P(omega)/Fin is extremely interesting, and uses this relation. –  Joel David Hamkins Jan 6 '10 at 16:07

Why not just overload $\leq$ when applied to sequences? I don't think there is any opportunity for confusion, and it fits with the notation you would use when extending $\leq$ to an ultraproduct.

This is what Jim Henle does in his "non-nonstandard analysis", which uses "eventually" as a replacement for an ultrafilter.

share|improve this answer
4  
The ultrafilter usage would be a mathematically different concept. For example, with an ultrafilter the order is a total (linear) order, but almost-less-than is not. The almost-less-than relation in the question uses a mere filter, the Frechet filter of all co-finite sets. –  Joel David Hamkins Jan 6 '10 at 16:10
6  
There certainly is opportunity for confusion in overloading $\leq$. It's not uncommon to use $\leq$ to mean an entrywise comparison of sequences (or more generally pointwise comparison of functions). And since it's common (sloppy) practice to obscure the distinction between a sequence and its entries, many readers are likely to assume that's what $\leq$ means (or find it distracting nevertheless even if the meaning is clearly defined). –  Mark Meckes Jan 6 '10 at 16:15
    
I still like the idea of using the same notation for a statement and the same statement extended to a product via a filter, but I also feel squeamish about almost-less-than not being a total order.. thanks for the food for thought! –  Matt Noonan Jan 6 '10 at 16:19
1  
@Mark: Point taken. Of course, that usage also fits with the filter usage, for the trivial filter. That said, if it needs this much justification then my suggestion is clearly not a good one. –  Matt Noonan Jan 6 '10 at 16:22

Good notation should be self-explaining and not require the reader to remember to much. I would write either: $$ f\le g\quad\text{eventually}$$ $$ f\le g\quad\text{ near }\infty$$ If you use it more than 100 times in a paper you could use something like $$ f \preccurlyeq g.$$

share|improve this answer

I agree with Joel Hamkins's answer, but I don't entirely agree with his comment on that answer. I generally use asterisks to mean "with finitely many exceptions" or "modulo finite sets", so I'd use $f\leq^*g$ and $A\subseteq^*B$ as Joel says. But when working modulo some ideal $I$ other than the ideal of finite sets, I'd ordinarily avoid asterisks and instead write $f\leq_Ig$ and $A\subseteq_IB$.

I'd like to protest vigorously against the use of $\ll$ in this situation. To me, $f\ll g$ means that $f$ is a lot smaller than $g$ (at least eventually), whereas here you might have $f(n)=g(n)-1$ for all $n$.

share|improve this answer
1  
But then $\ll$ in analytic number theory and related fields has a very different meaning (referred to by OP); essentially a synonym for big-Oh. –  quid Dec 17 '12 at 15:54

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.