Opened 11 years ago

Closed 11 years ago

Last modified 11 years ago

#7595 closed enhancement (fixed)

Chinese Remainder Theorem for univariate polynomials over a field

Reported by: rlm Owned by: AlexGhitza
Priority: major Milestone: sage-4.3.1
Component: algebra Keywords:
Cc: Merged in: sage-4.3.1.alpha2
Authors: Robert Miller Reviewers: Robert Bradshaw, John Cremona
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

This wasn't hard to implement, since all the hard work was already done.

Attachments (2)

trac_7595.patch (4.4 KB) - added by rlm 11 years ago.
rebased on 4.3.rc0
trac_7595-failures.patch (1.1 KB) - added by rlm 11 years ago.
Should fix the issues in quadratic_formternary_Tornaria.py

Download all attachments as: .zip

Change History (21)

comment:1 Changed 11 years ago by rlm

  • Status changed from new to needs_review
  • Summary changed from Chinese Remainder Theorem for polynomials over a field to Chinese Remainder Theorem for univariate polynomials over a field

comment:2 follow-up: Changed 11 years ago by ncohen

  • Status changed from needs_review to needs_info

Hello !! This is clearly not my field but I dare intrude : I see you are using functions "crt" and "CRT_list", and I wondered if you would find it sensible to rename them to chinese_remainer_theorem and chinese_remainder_theorem_list ? If this is too long, it may be possible to drop the "theorem" from the name, but the fact remains that if I had to use this function sometime ( which is not excluded, as it is a very famous result ), there is no way on earth I would have thought of trying the "crt" function if I had not seen it related to this ticket :-)

I am under the impression the english speakers would end this message with :

"Well, just my two cents" :-)

Nathann

comment:3 in reply to: ↑ 2 Changed 11 years ago by rlm

  • Status changed from needs_info to needs_review

Replying to ncohen:

... I wondered if you would find it sensible to rename them to chinese_remainer_theorem ...

This is irrelevant to this ticket. You should bring it up on sage-devel instead.

comment:4 Changed 11 years ago by robertwb

  • Status changed from needs_review to positive_review

Nice.

comment:5 Changed 11 years ago by rlm

  • Reviewers set to Robert Bradshaw

This patch wasn't applying, so I've rebased it. No real changes though.

Changed 11 years ago by rlm

rebased on 4.3.rc0

comment:6 Changed 11 years ago by rlm

Just caught a doctest failure in sage/rings/arith.py. Oops!

comment:7 Changed 11 years ago by mhansen

  • Status changed from positive_review to needs_work
  • Work issues set to needs rebase

comment:8 Changed 11 years ago by rlm

Which ticket is the patch conflicting with?

comment:9 Changed 11 years ago by rlm

  • Status changed from needs_work to needs_review

I've checked, and this merges with the current rc1.

comment:10 Changed 11 years ago by cremona

  • Reviewers changed from Robert Bradshaw to Robert Bradshaw, John Cremona
  • Status changed from needs_review to positive_review
  • Work issues needs rebase deleted

The patch is fine, applies to 4.3.rc0 and all tests pass in sage/rings.

I have some problems with the CRT* functions though.

  1. CRT_list does not check that the two lists have the same length; if the moduli list is shorter you get an IndexError?, but it would be better to catch that and raise a more informative error.
  1. CRT_basis is rather silly. It calls CRT_list n times with the same moduli, which must be wasteful. It would be better to call plain CRT n times with suitable moduli (exercise for the reader).

Of course, I don't think that these issues should delay the current patch, but deserve a ticket of their own to make sure they are tided up.

comment:11 Changed 11 years ago by mhansen

  • Merged in set to sage-4.3.1.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

I've made #7836 for this.

comment:12 Changed 11 years ago by mhansen

  • Merged in sage-4.3.1.alpha0 deleted
  • Status changed from closed to needs_work

This causes failures in the following file sage/quadratic_forms/quadratic_form__ternary_Tornaria.py:

**********************************************************************
File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/devel/sage-main/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 476:
    sage: map(Q1.xi_rec, [-1,2,3,5])
Exception raised:
    Traceback (most recent call last):
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_18[8]>", line 1, in <module>
        map(Q1.xi_rec, [-Integer(1),Integer(2),Integer(3),Integer(5)])###line 476:
    sage: map(Q1.xi_rec, [-1,2,3,5])
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 481, in xi_rec
        return self.reciprocal().xi(p)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 456, in xi
        return kronecker_symbol(p, self.basiclemma(2))
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 385, in basiclemma
        a=self(self.basiclemmavec(M))
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 416, in basiclemmavec
        return CRT_list(vec,mod)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/rings/arith.py", line 2522, in CRT_list
        return moduli[0].parent()(v[0])
      File "parent.pyx", line 538, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:4956)
      File "coerce_maps.pyx", line 82, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3142)
      File "coerce_maps.pyx", line 77, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3040)
      File "integer.pyx", line 653, in sage.rings.integer.Integer.__init__ (sage/rings/integer.c:6803)
    TypeError: unable to coerce <type 'sage.modules.vector_integer_dense.Vector_integer_dense'> to an integer
**********************************************************************
File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/devel/sage-main/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 478:
    sage: map(Q2.xi_rec, [-1,2,3,5])
Exception raised:
    Traceback (most recent call last):
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_18[9]>", line 1, in <module>
        map(Q2.xi_rec, [-Integer(1),Integer(2),Integer(3),Integer(5)])###line 478:
    sage: map(Q2.xi_rec, [-1,2,3,5])
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 481, in xi_rec
        return self.reciprocal().xi(p)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 456, in xi
        return kronecker_symbol(p, self.basiclemma(2))
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 385, in basiclemma
        a=self(self.basiclemmavec(M))
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 416, in basiclemmavec
        return CRT_list(vec,mod)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/rings/arith.py", line 2522, in CRT_list
        return moduli[0].parent()(v[0])
      File "parent.pyx", line 538, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:4956)
      File "coerce_maps.pyx", line 82, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3142)
      File "coerce_maps.pyx", line 77, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3040)
      File "integer.pyx", line 653, in sage.rings.integer.Integer.__init__ (sage/rings/integer.c:6803)
    TypeError: unable to coerce <type 'sage.modules.vector_integer_dense.Vector_integer_dense'> to an integer

Changed 11 years ago by rlm

Should fix the issues in quadratic_formternary_Tornaria.py

comment:13 Changed 11 years ago by rlm

This patch should fix the issues mentioned above. I wasn't sure whether to make a new ticket, or just post it here (never seen a "needs_work" closed ticket...)

comment:14 Changed 11 years ago by cremona

  • Status changed from needs_work to needs_review

comment:15 Changed 11 years ago by cremona

  • Status changed from needs_review to positive_review

I changed the ticket to "needs review" and then gave it a positive review -- it works for me.

comment:16 follow-up: Changed 11 years ago by mvngu

This ticket is rather messy. The patch trac_7595.patch is merged in Sage 4.3.1.alpha0 and it was then closed as being fixed in that version. Later on, the value in the field "Merged in:" was deleted. Now there is another patch `trac_7595-failures.patch` which hasn't been merged yet as of Sage 4.3.1.alpha1. And yet the ticket is declared as "fixed", but without a value for the field "Merged in:". I think the ticket's status should now be "open" not "fixed", until trac_7595-failures.patch is merged.

comment:17 in reply to: ↑ 16 Changed 11 years ago by rlm

Replying to mvngu:

The patch trac_7595.patch is merged in Sage 4.3.1.alpha0 ... Now there is another patch trac_7595-failures.patch which hasn't been merged yet as of Sage 4.3.1.alpha1.

The patch was rolled back-- neither is in Sage-4.3.1.alpha1

And yet the ticket is declared as "fixed"...

Apparently when the ticket was reopened, this did not revert. I don't know how to fix this, but the ticket is definitely open.

... until trac_7595-failures.patch is merged.

Repeat: as of sage-4.3.1.alpha1, *both* patches need to be merged.

comment:18 Changed 11 years ago by rlm

  • Merged in set to 4.3.1.alpha2
  • Status changed from positive_review to closed

comment:19 Changed 11 years ago by mvngu

  • Merged in changed from 4.3.1.alpha2 to sage-4.3.1.alpha2
Note: See TracTickets for help on using tickets.