#18595: Big Oh terms and equality
--------------------------------------------+------------------------
Reporter: behackl | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.8
Component: commutative algebra | Resolution:
Keywords: powerseries, asymptotics | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
--------------------------------------------+------------------------
Comment (by behackl):
Replying to [comment:4 nbruin]:
> Replying to [comment:3 behackl]:
> > I'll probably have to provide some more context. When I'm thinking of
O-notation, I have http://en.wikipedia.org/wiki/Big_O_notation#Equals_sign
in mind, that is I think of `O(f(x))` as the class of functions `g(x)`
such that `|g(x)| <= C |f(x)|` holds for `x -> oo`. By abuse of notation,
`g(x) = O(f(x))` then actually means `g(x) \in O(f(x))` -- and this leads
to the problem that I do not agree with
>
> Yes, I don't think that's a very useful way of thinking about the big-oh
used for power series approximations, and not the one that comes naturally
from their algebra. If anything, the big-oh is with respect to limits for
x->0 when applicable, although actual convergence is irrelevant for formal
power series arithmetic -- there's no problem taking power series with
coefficients over finite fields, for instance. What kind of limit would
you be taking?
>
> With that limit interpretation, we see that O(x^2^) would consist of all
those power series (ignoring convergence issues) for which lim_{x->0}
f(x)/x^2^ is finite. That would include 0.
>
Well -- mea culpa. I meant to write `x -> 0`; for `x -> oo` everything is
exactly the other way around (e.g. `x + O(x^2)` reduces to `O(x^2)`; there
the O term can absorb smaller terms).
So, the interpretation I have in mind and the limit interpretation
coincide. Sorry.
Of course, the limit definition only works when the point of approximation
is an inner point; and that also exactly how these O terms that I think of
are defined, for example, here:
http://algo.inria.fr/flajolet/Publications/AnaCombi/book.pdf (p. 722).
> > {{{
> > sage: RIF(0).is_zero()
> > True
> > sage: RIF((-0.1, 0.1)).is_zero()
> > False
> > }}}
> > This is more like the behavior I would expect from `O(x).is_zero()`.
What do you think?
>
> That's a very good parallel and it is exactly the behaviour we have. If
you want to do it using calculus-type limits, you should consider
lim_{x->0}, though.
>
{{{
sage: R.<x> = PowerSeriesRing(ZZ)
sage: R(0).is_zero()
True
sage: O(x).is_zero()
True
}}}
Following the behavior of RIF, I still would expect `O(x).is_zero()` to
return False, because I see `0 + O(x)` like `RIF((-0.1, 0.1))`: an
"approximate" zero.
> Algebraically, you get a much nicer definition. There `ZZ[[x]] =
limproj_{n->oo} Z[x]/(x^n)` and O(x^n^) can then be identified with the
kernel of the homomorphism `ZZ[[x]]-> Z[x]/(x^n)`. If you're not already
familiar with projective limits you might have to do some reading to get
familiar with them and if you're not interested in the underlying
algebraic theory you might not find it particularly enlightening to do so.
I have to admit that this definition of formal power series is new for me;
but I think I understand. I agree that within `ZZ[x]/(x)`,
`O(x).is_zero()` should yield `True`. But in `ZZ[[x]]` too?
And finally: what about the following:
{{{
sage: O(x) == O(x^2)
True
}}}
Does this equality make sense to you?
--
Ticket URL: <http://trac.sagemath.org/ticket/18595#comment:5>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
