id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
8800,Doctest coverage of categories - numerous coercion fixes,SimonKing,Simon King,"According to William, the doctest coverage of categories is too low:
{{{
action.pyx: 0% (0 of 31)
functor.pyx: 17% (3 of 17)
map.pyx: 27% (10 of 37)
morphism.pyx: 20% (5 of 24)
pushout.py: 24% (19 of 77)
}}}
The original purpose of this ticket was to provide full doctest coverage for `functor.pyx` and `pushout.py`. '''The doctest coverage of both files is now 100%'''.
However, the attempt to create meaningful doctests uncovered many bugs in various parts of Sage, and also motivated the implementation of coercion for various algebraic structures for which this has not been done before.
This a-posteriori ticket description lists the bugs killed and the features added by the patch, which should apply (with a little fuzz) after the patch from #8807. For more details on the bugs, see the comments below.
1. Bug: Creating `ForgetfulFunctor` fails.
Was:
{{{
sage: abgrps = CommutativeAdditiveGroups()
sage: ForgetfulFunctor(abgrps, abgrps)
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
/home/king/SAGE/patches/doku/english/ in ()
/home/king/SAGE/sage-4.3.1/local/lib/python2.6/site-packages/sage/categories/functor.so in sage.categories.functor.ForgetfulFunctor (sage/categories/functor.c:2083)()
TypeError: IdentityFunctor() takes exactly one argument (2 given)
}}}
Now:
{{{
sage: abgrps = CommutativeAdditiveGroups()
sage: ForgetfulFunctor(abgrps, abgrps)
The identity functor on Category of commutative additive groups
}}}
2. Bug: Applying `ForgetfulFunctor` returns `None`.
Was:
{{{
sage: fields = Fields()
sage: rings = Rings()
sage: F = ForgetfulFunctor(fields,rings)
sage: F(QQ)
}}}
Now:
{{{
sage: fields = Fields()
sage: rings = Rings()
sage: F = ForgetfulFunctor(fields,rings)
sage: F(QQ)
Rational Field
}}}
3. Bug: Applying a functor does not complain if the argument is not contained in the domain.
Was:
{{{
sage: fields = Fields()
sage: rings = Rings()
sage: F = ForgetfulFunctor(fields,rings)
# Yields None, see previous bug
sage: F(ZZ['x','y'])
}}}
Now:
{{{
sage: fields = Fields()
sage: rings = Rings()
sage: F = ForgetfulFunctor(fields,rings)
sage: F(ZZ['x','y'])
Traceback (most recent call last):
...
TypeError: x (=Multivariate Polynomial Ring in x, y over Integer Ring) is not in Category of fields
}}}
4. Bug: Comparing identity functor with any functor only checks domain and codomain
Was:
{{{
sage: F = QQ['x'].construction()[0]
sage: F
Poly[x]
sage: F == IdentityFunctor(Rings())
False
sage: IdentityFunctor(Rings()) == F
True
}}}
Now:
{{{
sage: F = QQ['x'].construction()[0]
sage: F
Poly[x]
sage: F == IdentityFunctor(Rings())
False
sage: IdentityFunctor(Rings()) == F
False
}}}
5. Bug: Comparing identity functor with anything that is not a functor produces an error
Was:
{{{
sage: IdentityFunctor(Rings()) == QQ
Traceback (most recent call last):
...
AttributeError: 'RationalField_with_category' object has no attribute 'domain'
}}}
Now:
{{{
sage: IdentityFunctor(Rings()) == QQ
False
}}}
6. Bug: The matrix functor is ill defined; moreover, ill-definedness does not result in an error.
Was:
{{{
sage: F = MatrixSpace(ZZ,2,3).construction()[0]
sage: F(RR) in F.codomain()
False
# The codomain is wrong for non-square matrices!
sage: F.codomain()
Category of rings
}}}
Now:
{{{
sage: F = MatrixSpace(ZZ,2,3).construction()[0]
sage: F.codomain()
Category of commutative additive groups
sage: F(RR) in F.codomain()
True
sage: F = MatrixSpace(ZZ,2,2).construction()[0]
sage: F.codomain()
Category of rings
sage: F(RR) in F.codomain()
True
}}}
7. Bug: Wrong domain for `VectorFunctor`; and again, functors don't test if the domain is appropriate
Was:
{{{
sage: F = FreeModule(ZZ,3).construction()[0]
sage: F
VectorFunctor
sage: F.domain()
Category of objects
sage: F.codomain()
Category of objects
sage: Set([1,2,3]) in F.domain()
True
sage: F(Set([1,2,3]))
Traceback (most recent call last):
...
AttributeError: 'Set_object_enumerated' object has no attribute 'is_commutative'
}}}
Now:
{{{
sage: F = FreeModule(ZZ,3).construction()[0]
sage: F
VectorFunctor
sage: F.domain()
Category of commutative rings
sage: Set([1,2,3]) in F.domain()
False
sage: F(Set([1,2,3]))
Traceback (most recent call last):
...
TypeError: x (={1, 2, 3}) is not in Category of commutative rings
}}}
8. Bug: `BlackBoxConstructionFunctor` is completely unusable
`BlackBoxConstructionFunctor` should be a class, but is defined as a function. Moreover, the given init method is not using the init method of `ConstructionFunctor`. And the cmp method would raise an error if the second argument has no attribute `.box`.
The following did not work at all:
{{{
sage: from sage.categories.pushout import BlackBoxConstructionFunctor
sage: FG = BlackBoxConstructionFunctor(gap)
sage: FS = BlackBoxConstructionFunctor(singular)
sage: FG
BlackBoxConstructionFunctor
sage: FG(ZZ)
Integers
sage: FG(ZZ).parent()
Gap
sage: FS(QQ['t'])
// characteristic : 0
// number of vars : 1
// block 1 : ordering lp
// : names t
// block 2 : ordering C
sage: FG == FS
False
sage: FG == loads(dumps(FG))
True
}}}
9. Nitpicking: The `LocalizationFunctor` is nowhere used (yet)
Hence, I removed it.
10. Bug / New Feature: Make completion and and fraction field construction functors commute.
The result of them not commuting is the following coercion bug.
Was:
{{{
sage: R1. = Zp(5)[]
sage: R2 = Qp(5)
sage: R2(1)+x
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for '+': '5-adic Field with capped relative precision 20' and 'Univariate Polynomial Ring in x over 5-adic Ring with capped relative precision 20'
}}}
Now:
{{{
sage: R1. = Zp(5)[]
sage: R2 = Qp(5)
sage: R2(1)+x
(1 + O(5^20))*x + (1 + O(5^20))
}}}
11. New feature: Make the completion functor work on some objects that do not provide a completion method.
The idea is to use that the completion functor may commute with the construction of the given argument. That may safe the day.
Was:
{{{
sage: P. = ZZ[]
sage: C = P.completion(x).construction()[0]
sage: R = FractionField(P)
sage: hasattr(R,'completion')
False
sage: C(R)
Traceback (most recent call last):
...
AttributeError: 'FractionField_generic' object has no attribute 'completion'
}}}
Now:
{{{
sage: P. = ZZ[]
sage: C = P.completion(x).construction()[0]
sage: R = FractionField(P)
sage: hasattr(R,'completion')
False
sage: C(R)
Fraction Field of Power Series Ring in x over Integer Ring
}}}
12. Bug / new feature: Coercion for free modules, taking into account a user-defined inner product
Was:
{{{
sage: P. = ZZ[]
sage: M1 = FreeModule(P,3)
sage: M2 = QQ^3
sage: M2([1,1/2,1/3]) + M1([t,t^2+t,3]) # This is ok
(t + 1, t^2 + t + 1/2, 10/3)
sage: M3 = FreeModule(P,3, inner_product_matrix = Matrix(3,3,range(9)))
sage: M2([1,1/2,1/3]) + M3([t,t^2+t,3]) # This is ok
(t + 1, t^2 + t + 1/2, 10/3)
# The user defined inner product matrix is lost! Bug
sage: parent(M2([1,1/2,1/3]) + M3([t,t^2+t,3])).inner_product_matrix()
[1 0 0]
[0 1 0]
[0 0 1]
}}}
Now:
{{{
sage: parent(M2([1,1/2,1/3]) + M3([t,t^2+t,3])).inner_product_matrix()
[0 1 2]
[3 4 5]
[6 7 8]
}}}
However, the real problem is that modules are not part of the coercion model. I tried to implement it, but that turned out to be a can of worms. So, '''I suggest to deal with it on a different ticket'''. Here is one bug that isn't removed, yet:
{{{
sage: M4 = FreeModule(P,3, inner_product_matrix = Matrix(3,3,[1,1,1,0,1,1,0,0,1]))
sage: M3([t,1,t^2]) + M4([t,t^2+t,3]) # This should result in an error
(2*t, t^2 + t + 1, t^2 + 3)
}}}
Note that there should be no coercion between `M3` and `M4`, since they have different user-defined inner product matrices.
13. Bug / new feature: Quotient rings of univariate polynomial rings do not have a construction method.
Was:
{{{
sage: P. = QQ[]
sage: Q1 = P.quo([(x^2+1)^2*(x^2-3)])
sage: Q2 = P.quo([(x^2+1)^2*(x^5+3)])
sage: from sage.categories.pushout import pushout
sage: pushout(Q1,Q2)
Traceback (most recent call last):
...
CoercionException: No common base
}}}
Now:
{{{
sage: P. = QQ[]
sage: Q1 = P.quo([(x^2+1)^2*(x^2-3)])
sage: Q2 = P.quo([(x^2+1)^2*(x^5+3)])
sage: from sage.categories.pushout import pushout
sage: pushout(Q1,Q2)
Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^4 + 2*x^2 + 1
}}}
14. Insufficient coercion of quotient rings, if one modulus divides the other
Was:
{{{
sage: P5. = GF(5)[]
sage: Q = P5.quo([(x^2+1)^2])
sage: P. = ZZ[]
sage: Q1 = P.quo([(x^2+1)^2*(x^2-3)])
sage: Q2 = P.quo([(x^2+1)^2*(x^5+3)])
sage: Q.has_coerce_map_from(Q1)
False
}}}
Now: There is a coercion from `Q1` to `Q`.
15. Coercion of `GF(p)` versus `Integers(p)`
I am not sure if this is really a bug.
Was:
{{{
sage: from sage.categories.pushout import pushout
sage: pushout(GF(5), Integers(5))
Ring of integers modulo 5
}}}
Now
{{{
sage: from sage.categories.pushout import pushout
sage: pushout(GF(5), Integers(5))
Finite Field of size 5
}}}
16. Bug / new feature: Construction for QQbar was missing.
Now:
{{{
sage: QQbar.construction()
(AlgebraicClosureFunctor, Rational Field)
}}}
17. Bug / new feature: Construction for number fields is missing.
This became a rather complicated topic, including ""coercions for embedded versus non-embedded number fields and coercion for an order from a coercion from the ambient field"", ""pushout for number fields"", ""comparison of fractional ideals"", ""identity of residue fields"". See three discussions on sage-algebra and sage-nt
* [http://groups.google.com/group/sage-nt/browse_thread/thread/32b65a5173f43267 Bidirectional coercions]
* [http://groups.google.com/group/sage-nt/browse_thread/thread/5c376dbf7e99ea97 Coercions for number fields]
* [http://groups.google.com/group/sage-nt/browse_thread/thread/54c1e33872d14334 Comparison of fractional ideals]
__Coercion__
Important for the discussion is: What will we do with embeddings?
Currently, the embedding of two number fields is used to construct a coercion (compatible with the embedding). Of course, the given embedding is also used as a coerce map.
It was discussed to additionally have a ""forgetful"" coercion from an embedded to a non-embedded number field.
It turned out that with bidirectional and forgetful coercions together, one can construct examples in which the coercions do not form a commutative diagram. Hence, we do ''not'' introduce forgetful coercions here.
However, some improvement of the existing implementation was needed.
Was:
{{{
sage: K. = NumberField(x^4-2)
sage: L1. = NumberField(x^2-2, embedding = r4**2)
sage: L2. = NumberField(x^2-2, embedding = -r4**2)
sage: r2_1+r2_2 # indirect doctest
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (1109, 0))
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (1109, 0))
...
sage: K.has_coerce_map_from(L1.maximal_order())
False # that's the wrong direction.
sage: L1.has_coerce_map_from(K.maximal_order())
True
}}}
Now:
{{{
sage: K. = NumberField(x^4-2)
sage: L1. = NumberField(x^2-2, embedding = r4**2)
sage: L2. = NumberField(x^2-2, embedding = -r4**2)
sage: r2_1+r2_2 # indirect doctest
0
sage: (r2_1+r2_2).parent() is L1
True
sage: (r2_2+r2_1).parent() is L2
True
sage: K.has_coerce_map_from(L1.maximal_order())
True
sage: L1.has_coerce_map_from(K.maximal_order())
False
}}}
__Pushout__
Was:
{{{
sage: P. = QQ[]
sage: L.** = NumberField(x^8-x^4+1, embedding=CDF.0)
sage: M1. = NumberField(x^2+x+1, embedding=b^4-1)
sage: M2. = NumberField(x^2+1, embedding=-b^6)
sage: M1.coerce_map_from(M2)
sage: M2.coerce_map_from(M1)
sage: c1+c2; parent(c1+c2) #indirect doctest
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for '+': 'Number Field in c1 with defining polynomial x^2 + x + 1' and 'Number Field in c2 with defining polynomial x^2 + 1'
sage: from sage.categories.pushout import pushout
sage: pushout(M1['x'],M2['x'])
Traceback (most recent call last):
...
CoercionException: No common base
}}}
Now: Note that we will only have a pushout if the codomains of the embeddings are number fields. Hence, in the second example, we won't use `CDF` as a pushout.
{{{
sage: P. = QQ[]
sage: L.**** = NumberField(x^8-x^4+1, embedding=CDF.0)
sage: M1. = NumberField(x^2+x+1, embedding=b^4-1)
sage: M2. = NumberField(x^2+1, embedding=-b^6)
sage: M1.coerce_map_from(M2)
sage: M2.coerce_map_from(M1)
sage: c1+c2; parent(c1+c2) #indirect doctest
-b^6 + b^4 - 1
Number Field in b with defining polynomial x^8 - x^4 + 1
sage: from sage.categories.pushout import pushout
sage: pushout(M1['x'],M2['x'])
Univariate Polynomial Ring in x over Number Field in b with defining polynomial x^8 - x^4 + 1
sage: K. = NumberField(x^3-2, embedding=CDF(1/2*I*2^(1/3)*sqrt(3) - 1/2*2^(1/3)))
sage: L.**** = NumberField(x^6-2, embedding=1.1)
sage: L.coerce_map_from(K)
sage: K.coerce_map_from(L)
sage: pushout(K,L)
Traceback (most recent call last):
...
CoercionException: ('Ambiguous Base Extension', Number Field in a with defining polynomial x^3 - 2, Number Field in b with defining polynomial x^6 - 2)
}}}
__Comparison of fractional ideals / identity of Residue Fields__
Fractional ideals have a `__cmp__` method that only took into account the Hermite normal form. Originally, the comparison of fractional ideals by ""=="" and by ""cmp"" yields different results. Since ""=="" of fractional ideals is used for caching residue fields, but ""cmp"" was used for comparing residue fields, the residue fields did not provide unique parents.
Was:
{{{
sage: L.**** = NumberField(x^8-x^4+1)
sage: F_2 = L.fractional_ideal(b^2-1)
sage: F_4 = L.fractional_ideal(b^4-1)
sage: F_2==F_4
True
sage: K. = NumberField(x^4-2)
sage: L. = NumberField(x^4-2, embedding=CDF.0)
sage: FK = K.fractional_ideal(K.0)
sage: FL = L.fractional_ideal(L.0)
sage: FK != FL
True
sage: RL = ResidueField(FL)
sage: RK = ResidueField(FK)
sage: RK is RL
False
sage: RK == RL
True
}}}
Now:
{{{
sage: L.**** = NumberField(x^8-x^4+1)
sage: F_2 = L.fractional_ideal(b^2-1)
sage: F_4 = L.fractional_ideal(b^4-1)
sage: F_2==F_4
True
sage: K. = NumberField(x^4-2)
sage: L. = NumberField(x^4-2, embedding=CDF.0)
sage: FK = K.fractional_ideal(K.0)
sage: FL = L.fractional_ideal(L.0)
sage: FK != FL
True
sage: RL = ResidueField(FL)
sage: RK = ResidueField(FK)
sage: RK is RL
False
sage: RK == RL
False
}}}
Since `RL` is defined with the embedded field `L`, not with the unembedded `K`, there is no coercion from the order of `K` to `RL`. However, ''conversion'' works (this used to fail!):
{{{
sage: OK = K.maximal_order()
sage: RL.has_coerce_map_from(OK)
False
sage: RL(OK.1)
0
}}}
Note that I also had to change some arithmetic stuff in the `_tate` method of elliptic curves: The old implementation relied on the assumption that fractional ideals in an embedded field and in a non-embedded field can't be equal. This assumption should still hold (since we do not introduce forgetful coercion), but I think it is OK to keep the change in _tate.
'''Apply:'''
1. [attachment:8800_functor_pushout_doc_and_fixes.patch]
2. [attachment:referee.patch]
'''Dependencies:''' #10677, #2329.",defect,closed,major,sage-4.7,categories,fixed,categories doctests,,sage-4.7.alpha1,Simon King,Luis Felipe Tabera Alonso,N/A,,,,,
**