Skip to content

Refactor O() and fix O() for lazy power series ring #39436

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 10 commits into from
Apr 29, 2025
Merged

Refactor O() and fix O() for lazy power series ring #39436

merged 10 commits into from
Apr 29, 2025

Conversation

user202729
Copy link
Contributor

@user202729 user202729 commented Feb 3, 2025 •
edited
Loading

Fixes O(x) for LazyPowerSeriesRing. (previously it doesn't work)

Also refactor it to check less special cases.

Use .perfect_power() instead of factor() to avoid wasting time if a large composite is passed.

Note: .O() and .add_bigoh() is the same for many rings, but not AsymptoticRing.
In particular

  • for most rings x.O(5) means x.add_bigoh(5) or x+O(x^5)
  • for AsymptoticRing x.O() means O(x)

Personally I think the latter makes more sense, but this is part of public API so we will have to live with this inconsistency. (The former does not make sense for AsymptoticRing even)

sage: A.<n> = AsymptoticRing(growth_group='QQ^n * n^QQ * log(n)^QQ', coefficient_ring=QQ); A
Asymptotic Ring <QQ^n * n^QQ * log(n)^QQ * Signs^n> over Rational Field
sage: n.O()
O(n)
sage: R.<x> = QQ[[]]
sage: x.O()
Traceback (most recent call last)
...
TypeError: O() takes exactly 1 positional argument (0 given)
sage: x.O(3)
x + O(x^3)

Thus the explicit check is needed. (add_bigoh is not implemented for AsymptoticRing)

I don't know why it's desirable to block O(2*x^2) for polynomial ring, but I'll leave the behavior unchanged just in case.

📝 Checklist

  • The title is concise and informative.
  • The description explains in detail what this PR is about.
  • I have created tests covering the changes.
  • I have updated the documentation and checked the documentation preview.

⌛ Dependencies

@user202729 user202729 changed the title Refactor O() Refactor O() and fix O() for lazy power series ring Feb 3, 2025
@github-actions GitHub Actions
Copy link

github-actions bot commented Feb 3, 2025 •
edited
Loading

Documentation preview for this PR (built with commit 61023a1; changes) is ready! 🎉
This preview will update shortly after each push to this PR.

@user202729
Copy link
Contributor Author

user202729 commented Feb 3, 2025 •
edited
Loading

Looks like genuine bug in doctest.

sage: R.<x> = ZZ[]
sage: W.<w> = ZpFM(5).extension(x^3 - 5)
sage: (1 + w)._polynomial_list()
[1, 1]
sage: (1 + w + O(w^11))._polynomial_list(pad=True)
[1, 1, 0]

The problem is the extension is ramified (Eisenstein), so O(…) is not yet implemented (sort of). (i.e. O(w^11) is identical to 0). It would actually be misleading to write the test like that.

But then, add_bigoh isn't implemented for fixed modulus in general either (even if the extension is unramified). So writing +O(w^…) is misleading in general in that it does nothing.

sage: W.<w> = ZpFM(5).extension(x^3 - 5)
sage: w^5
w^5
sage: O(w^4)  # before this change, gives error after this change
0
sage: w^5 + O(w^4)
w^5
sage: 1 + w + O(w^11)
1 + w

tscrim
tscrim approved these changes Feb 10, 2025
View reviewed changes
Copy link
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM except I don't know the math enough to verify the padic change. @xcaruso Can you comment on that doctest?

@tscrim
Copy link
Collaborator

tscrim commented Feb 23, 2025

@xcaruso @roed314 Could one of you comment on the changed doctest and/or analysis? I don't have the expertise to verify.

@user202729
Copy link
Contributor Author

A (more conservative) alternative is to implement a check in implementation of O to return zero for fixed modulus rings (so, another special case apart from Puiseux series).

But I really can't think of any case where O(something) in fixed modulus ring makes sense, since writing +O(…) does nothing, and even in generic code it seems not particularly useful. Might be better to raise an error to warn the user.

@roed314
Copy link
Contributor

roed314 commented Feb 23, 2025

I'll take a look, though probably won't have time for a couple days.

@user202729
Copy link
Contributor Author

I decide to just revert the change and special-case fixed modulus p-adic to always return 0. So the behavior of the doctest remains the same.

(I have no idea why pAdicZZpXFMElement does not inherit from pAdicFixedModElement, but it's not in scope.)

tscrim
tscrim approved these changes Apr 21, 2025
View reviewed changes
Copy link
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Sorry for the very long delay in finalizing this review. LGTM now. Thank you.

@user202729
Copy link
Contributor Author

Maybe worth noting that when x is in the lazy power series ring then O(x) is in the (normal, non-lazy) power series ring… but that behavior sounds completely reasonable to me anyway.

(I think someone (you?) pointed it out to me somewhere)

@vbraun vbraun merged commit d76572e into sagemath:develop Apr 29, 2025
21 of 23 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@tscrim tscrim tscrim approved these changes

Assignees
No one assigned
Labels
t: refactoring
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
4 participants
@user202729 @tscrim @roed314 @vbraun