Changes between Initial Version and Version 10 of Ticket #12529


Ignore:
Timestamp:
10/08/20 23:20:00 (8 weeks ago)
Author:
slelievre
Comment:

Please review and add reviewer name.

Let's see if this can get in Sage 9.2.


New commits:

5b3253aAdd doctest for remainder in multivariate polynomial ring

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #12529

    • Property Status changed from new to needs_review
    • Property Authors changed from to Samuel Lelièvre
    • Property Milestone changed from sage-5.11 to sage-9.2
    • Property Priority changed from blocker to major
    • Property Branch changed from to public/12529
    • Property Stopgaps changed from to todo
    • Property Commit changed from to 5b3253a14e46a97e783d5800cc20898bd1bb6957
  • Ticket #12529 – Description

    initial v10  
    11On [http://groups.google.com/group/sage-support/browse_thread/thread/b90fbb622ddb55ab sage-support], Oleksandr Kazymyrov reported the following:
    22{{{
    3 sage: bits=3
    4 sage:
    5 sage: k=GF(2^bits,'a')
    6 sage: P=PolynomialRing(k,1+bits+bits+bits-1+(1<<bits),['y'] +
    7 ['a{0}'.format(g) for g in xrange(bits)] + ['b{0}'.format(g) for g in
    8 xrange(bits)] + ['c{0}'.format(g) for g in xrange(1,bits)] +
    9 ['p{0}'.format(g) for g in xrange(1<<bits)])
    10 sage:
    11 sage: A1=sum([P('(a{0})*y^{0}'.format(g)) for g in xrange(bits)])
    12 sage: A2=sum([P('(b{0})*y^{0}'.format(g)) for g in xrange(bits)])
    13 sage: A3=sum([P('(c{0})*y^{0}'.format(g)) for g in xrange(1,bits)])
    14 sage: pol = sum([P('(p{0})*y^{0}'.format(g)) for g in xrange(1<<bits)])
    15 sage: pol=pol.subs({P("y"):A2})
    16 sage: pol=A1.subs({P("y"):pol})
    17 sage: pol=pol+A3
    18 sage: pol.mod(P("y^{0}+y".format(1<<bits)))
    19 y^7*a2*b1^14*p7^2 + y^7*a2*b2^14*p7^2 + y^10*a2*b1^10*p5^2 + y^8*a2*b0^4*b1^8*p6^2 + y^8*a2*b0^8*b2^4*p6^2 + y^14*a1*b2^7*p7 + y^6*a2*b0^8*b1^6*p7^2 + y^6*a2*b1^8*b2^6*p7^2 + y^6*a2*b0^2*b1^4*b2^8*p7^2 + y^6*a2*b0^4*b2^10*p7^2 + y^9*a2*b0^2*b2^8*p5^2 + y^13*a1*b1*b2^6*p7 + y^5*a2*b0^2*b1^12*p7^2 + y^5*a2*b0^4*b1^8*b2^2*p7^2 + y^5*a2*b0^8*b2^6*p7^2 + y^5*a2*b1^2*b2^12*p7^2 + y^12*a2*b2^6*p3^2 + y^8*a2*b0^2*b1^8*p5^2 + y^6*a2*b1^4*b2^8*p6^2 + y^12*a1*b1^2*b2^5*p7 + y^12*a1*b0*b2^6*p7 + y^4*a2*b0^10*b1^4*p7^2 + y^4*a2*b0^12*b2^2*p7^2 + y^4*a2*b1^10*b2^4*p7^2 + y^4*a2*b0^4*b1^2*b2^8*p7^2 + y^9*a2*b2^8*p4^2 + y^12*a1*b2^6*p6 + y^5*a2*b1^12*p6^2 + y^11*a1*b1^3*b2^4*p7 + y^3*a2*b0^4*b1^10*p7^2 + y^3*a2*b0^8*b1^2*b2^4*p7^2 + y^3*a2*b1^4*b2^10*p7^2 + y^3*a2*b0^2*b2^12*p7^2 + y^10*a2*b1^2*b2^4*p3^2 + y^8*a2*b1^8*p4^2 + y^6*a2*b2^10*p5^2 + y^4*a2*b0^8*b1^4*p6^2 + y^10*a1*b1^4*b2^3*p7 + y^10*a1*b0*b1^2*b2^4*p7 + y^10*a1*b0^2*b2^5*p7 + y^2*a2*b0^12*b1^2*p7^2 + y^2*a2*b1^12*b2^2*p7^2 + y^2*a2*b0^2*b1^8*b2^4*p7^2 + y^2*a2*b0^6*b2^8*p7^2 + y^5*a2*b1^8*b2^2*p5^2 + y^10*a1*b1^2*b2^4*p6 + y^3*a2*b2^12*p6^2 + y^9*a1*b1^5*b2^2*p7 + y^9*a1*b0^2*b1*b2^4*p7 + y*a2*b0^6*b1^8*p7^2 + y*a2*b0^8*b1^4*b2^2*p7^2 + y*a2*b0^10*b2^4*p7^2 + y*a2*b1^6*b2^8*p7^2 + y^8*a2*b1^4*b2^2*p3^2 + y^8*a2*b0^2*b2^4*p3^2 + y^10*a1*b2^5*p5 + y^4*a2*b0^8*b2^2*p5^2 + y^4*a2*b1^2*b2^8*p5^2 + y^2*a2*b1^8*b2^4*p6^2 + y^2*a2*b0^4*b2^8*p6^2 + y^8*a1*b1^6*b2*p7 + y^8*a1*b0*b1^4*b2^2*p7 + y^8*a1*b0^3*b2^4*p7 + a2*b0^14*p7^2 + y^9*a1*b1*b2^4*p5 + y^8*a1*b1^4*b2^2*p6 + y^8*a1*b0^2*b2^4*p6 + y^7*a1*b1^7*p7 + y^8*a2*b2^4*p2^2 + y^6*a2*b1^6*p3^2 + y^8*a1*b0*b2^4*p5 + y^2*a2*b0^8*b1^2*p5^2 + a2*b0^12*p6^2 + y^6*a1*b0*b1^6*p7 + y^6*a1*b0^2*b1^4*b2*p7 + y^6*a1*b0^4*b2^3*p7 + y^8*a1*b2^4*p4 + y^6*a1*b1^6*p6 + y^5*a1*b0^2*b1^5*p7 + y^5*a1*b0^4*b1*b2^2*p7 + y^4*a2*b0^2*b1^4*p3^2 + y^4*a2*b0^4*b2^2*p3^2 + y^6*a1*b1^4*b2*p5 + a2*b0^10*p5^2 + y^4*a1*b0^3*b1^4*p7 + y^4*a1*b0^4*b1^2*b2*p7 + y^4*a1*b0^5*b2^2*p7 + y^5*a1*b1^5*p5 + y^4*a1*b0^2*b1^4*p6 + y^4*a1*b0^4*b2^2*p6 + y^3*a1*b0^4*b1^3*p7 + y^4*a2*b1^4*p2^2 + y^6*a1*b2^3*p3 + y^2*a2*b0^4*b1^2*p3^2 + a2*b0^8*p4^2 + y^4*a1*b0*b1^4*p5 + y^2*a1*b0^5*b1^2*p7 + y^2*a1*b0^6*b2*p7 + y^5*a1*b1*b2^2*p3 + y^4*a1*b1^4*p4 + y^2*a1*b0^4*b1^2*p6 + y*a1*b0^6*b1*p7 + y^4*a2*b2^2*p1^2 + y^4*a1*b1^2*b2*p3 + y^4*a1*b0*b2^2*p3 + a2*b0^6*p3^2 + y^2*a1*b0^4*b2*p5 + a1*b0^7*p7 + y^4*a1*b2^2*p2 + y^3*a1*b1^3*p3 + y*a1*b0^4*b1*p5 + a1*b0^6*p6 + y^2*a2*b1^2*p1^2 + a2*b0^4*p2^2 + y^2*a1*b0*b1^2*p3 + y^2*a1*b0^2*b2*p3 + a1*b0^5*p5 + y^2*a1*b1^2*p2 + y*a1*b0^2*b1*p3 + a1*b0^4*p4 + y^2*a1*b2*p1 + a2*b0^2*p1^2 + a1*b0^3*p3 + y*a1*b1*p1 + a1*b0^2*p2 + y^2*c2 + a2*p0^2 + a1*b0*p1 + y*c1 + a1*p0 + a0
     3sage: gens = 'y a0 a1 a2 b0 b1 b2 c1 c2 d0 d1 d2 d3 d4 d5 d6 d7'.split()
     4sage: R = PolynomialRing(GF(8), 17, gens)
     5sage: R.inject_variables(verbose=False)
     6sage: A, B, C = a0 + a1*y + a2*y^2, b0 + b1*y + b2*y^2, c1*y + c2*y^2
     7sage: D = d0 + d1*y + d2*y^2 + d3*y^3 + d4*y^4 + d5*y^5 + d6*y^6 + d7*y^7
     8sage: F = D.subs({y: B})
     9sage: G = A.subs({y: F}) + C
     10sage: g = G.mod(y^8 + y)
     11sage: g.degree(y)
     1214
    2013}}}
    2114
    22 The mod operation does not reduce all terms:
     15This is now fixed and we add a doctest:
    2316{{{
    24 sage: pol.mod(P("y^{0}+y".format(1<<bits))).monomials()[3]
    25 y^8*a2*b0^4*b1^8*p6^2
    26 sage: pol.mod(P("y^{0}+y".format(1<<bits))).monomials()[2]
    27 y^10*a2*b1^10*p5^2
    28 }}}
    29 However, a reduction of the single terms works:
    30 {{{
    31 sage: pol.mod(P("y^{0}+y".format(1<<bits))).monomials()[2].mod(P("y^{0}+y".format(1<<bits)))
    32 y^3*a2*b1^10*p5^2
     17sage: g.degree(y)
     187
    3319}}}
    3420
    35 Note that Singular does the reduction right:
    36 {{{
    37 sage: singular(pol).NF(singular(P.ideal(P("y^{0}+y".format(1<<bits)))).std())
    38 y^7*a2*b1^14*p7^2+y^7*a2*b2^14*p7^2+y^6*a2*b0^8*b1^6*p7^2+y^6*a2*b1^8*b2^6*p7^2+y^6*a2*b0^2*b1^4*b2^8*p7^2+y^6*a2*b0^4*b2^10*p7^2+y^5*a2*b0^2*b1^12*p7^2+y^5*a2*b0^4*b1^8*b2^2*p7^2+y^5*a2*b0^8*b2^6*p7^2+y^5*a2*b1^2*b2^12*p7^2+y^6*a2*b1^4*b2^8*p6^2+y^4*a2*b0^10*b1^4*p7^2+y^4*a2*b0^12*b2^2*p7^2+y^4*a2*b1^10*b2^4*p7^2+y^4*a2*b0^4*b1^2*b2^8*p7^2+y^5*a2*b1^12*p6^2+y^3*a2*b0^4*b1^10*p7^2+y^3*a2*b0^8*b1^2*b2^4*p7^2+y^3*a2*b1^4*b2^10*p7^2+y^3*a2*b0^2*b2^12*p7^2+y^6*a2*b2^10*p5^2+y^4*a2*b0^8*b1^4*p6^2+y^2*a2*b0^12*b1^2*p7^2+y^2*a2*b1^12*b2^2*p7^2+y^2*a2*b0^2*b1^8*b2^4*p7^2+y^2*a2*b0^6*b2^8*p7^2+y^5*a2*b1^8*b2^2*p5^2+y^3*a2*b2^12*p6^2+y*a2*b0^6*b1^8*p7^2+y*a2*b0^8*b1^4*b2^2*p7^2+y*a2*b0^10*b2^4*p7^2+y*a2*b1^6*b2^8*p7^2+y^4*a2*b0^8*b2^2*p5^2+y^4*a2*b1^2*b2^8*p5^2+y^2*a2*b1^8*b2^4*p6^2+y^2*a2*b0^4*b2^8*p6^2+a2*b0^14*p7^2+y^3*a2*b1^10*p5^2+y*a2*b0^4*b1^8*p6^2+y*a2*b0^8*b2^4*p6^2+y^7*a1*b1^7*p7+y^7*a1*b2^7*p7+y^6*a2*b1^6*p3^2+y^2*a2*b0^8*b1^2*p5^2+y^2*a2*b0^2*b2^8*p5^2+a2*b0^12*p6^2+y^6*a1*b0*b1^6*p7+y^6*a1*b0^2*b1^4*b2*p7+y^6*a1*b0^4*b2^3*p7+y^6*a1*b1*b2^6*p7+y^5*a2*b2^6*p3^2+y*a2*b0^2*b1^8*p5^2+y^6*a1*b1^6*p6+y^5*a1*b0^2*b1^5*p7+y^5*a1*b0^4*b1*b2^2*p7+y^5*a1*b1^2*b2^5*p7+y^5*a1*b0*b2^6*p7+y^4*a2*b0^2*b1^4*p3^2+y^4*a2*b0^4*b2^2*p3^2+y^2*a2*b2^8*p4^2+y^6*a1*b1^4*b2*p5+a2*b0^10*p5^2+y^5*a1*b2^6*p6+y^4*a1*b0^3*b1^4*p7+y^4*a1*b0^4*b1^2*b2*p7+y^4*a1*b0^5*b2^2*p7+y^4*a1*b1^3*b2^4*p7+y^3*a2*b1^2*b2^4*p3^2+y*a2*b1^8*p4^2+y^5*a1*b1^5*p5+y^4*a1*b0^2*b1^4*p6+y^4*a1*b0^4*b2^2*p6+y^3*a1*b0^4*b1^3*p7+y^3*a1*b1^4*b2^3*p7+y^3*a1*b0*b1^2*b2^4*p7+y^3*a1*b0^2*b2^5*p7+y^4*a2*b1^4*p2^2+y^6*a1*b2^3*p3+y^2*a2*b0^4*b1^2*p3^2+a2*b0^8*p4^2+y^4*a1*b0*b1^4*p5+y^3*a1*b1^2*b2^4*p6+y^2*a1*b0^5*b1^2*p7+y^2*a1*b0^6*b2*p7+y^2*a1*b1^5*b2^2*p7+y^2*a1*b0^2*b1*b2^4*p7+y^5*a1*b1*b2^2*p3+y*a2*b1^4*b2^2*p3^2+y*a2*b0^2*b2^4*p3^2+y^4*a1*b1^4*p4+y^3*a1*b2^5*p5+y^2*a1*b0^4*b1^2*p6+y*a1*b0^6*b1*p7+y*a1*b1^6*b2*p7+y*a1*b0*b1^4*b2^2*p7+y*a1*b0^3*b2^4*p7+y^4*a2*b2^2*p1^2+y^4*a1*b1^2*b2*p3+y^4*a1*b0*b2^2*p3+a2*b0^6*p3^2+y^2*a1*b0^4*b2*p5+y^2*a1*b1*b2^4*p5+y*a1*b1^4*b2^2*p6+y*a1*b0^2*b2^4*p6+a1*b0^7*p7+y^4*a1*b2^2*p2+y*a2*b2^4*p2^2+y^3*a1*b1^3*p3+y*a1*b0^4*b1*p5+y*a1*b0*b2^4*p5+a1*b0^6*p6+y^2*a2*b1^2*p1^2+a2*b0^4*p2^2+y^2*a1*b0*b1^2*p3+y^2*a1*b0^2*b2*p3+y*a1*b2^4*p4+a1*b0^5*p5+y^2*a1*b1^2*p2+y*a1*b0^2*b1*p3+a1*b0^4*p4+y^2*a1*b2*p1+a2*b0^2*p1^2+a1*b0^3*p3+y*a1*b1*p1+a1*b0^2*p2+y^2*c2+a2*p0^2+a1*b0*p1+y*c1+a1*p0+a0
    39 }}}
    40 So, it seems to me that the problem is in libsingular, not in Singular.
     21The problem may have been in libsingular,
     22rather than in Singular.
    4123
    42 I guess the reduction is supposed to reduce the tail as well - if tail reduction is not done by default, then the doc should mention it.
    43 
    44 I think those basic arithmetic failures generally are blockers.
     24It may have been tail reduction not being done.