8
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jan 6, 2010 at 13:30
  • $\begingroup$ Of course, sorry. I have edited out my dim moment. $\endgroup$ Jan 6, 2010 at 13:46
  • 16
    $\begingroup$ Whatever notation you end up picking, please oh please explain it before you use it! $\endgroup$ Jan 6, 2010 at 15:55

4 Answers 4

13
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jan 6, 2010 at 16:07
6
$\begingroup$

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.

$\endgroup$
4
  • 4
    $\begingroup$ 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. $\endgroup$ Jan 6, 2010 at 16:10
  • 6
    $\begingroup$ 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). $\endgroup$ Jan 6, 2010 at 16:15
  • $\begingroup$ 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! $\endgroup$ Jan 6, 2010 at 16:19
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 6, 2010 at 16:22
5
$\begingroup$

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.$$

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – user9072
    Dec 17, 2012 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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