Opened 4 years ago
Closed 3 years ago
#24170 closed enhancement (fixed)
Extend vector_space method to arbitrary subfields
Reported by:  klee  Owned by:  

Priority:  minor  Milestone:  sage8.2 
Component:  finite rings  Keywords:  
Cc:  Merged in:  
Authors:  Kwankyu Lee, Vincent Delecroix  Reviewers:  Vincent Delecroix, Kwankyu Lee 
Report Upstream:  N/A  Work issues:  
Branch:  d205018 (Commits, GitHub, GitLab)  Commit:  d20501819b3288ef4a8a57036ab884ab83cde69d 
Dependencies:  Stopgaps: 
Description (last modified by )
The current vector_space()
method of finite fields is only over prime subfield of the finite field. Newly implemented vector_space()
method returns a vector space isomorphic to the finite field viewed as a vector space over an arbitrary subfield of the finite field.
The essential functionality was already implemented in #20284, aka RelativeFiniteFieldExtension
. But it is presently not accessible easily. I took the implementation idea from the ticket and reimplemented it as a method to finite fields and made the interface straightforward.
sage: E = GF(16) sage: F = GF(4) sage: V, from_V, to_V = E.vector_space(F, map=True) sage: V sage: from_V Isomorphism: From: Vector space of dimension 2 over Finite Field in z2 of size 2^2 To: Finite Field in z4 of size 2^4 sage: to_V Isomorphism: From: Finite Field in z4 of size 2^4 To: Vector space of dimension 2 over Finite Field in z2 of size 2^2
Change History (40)
comment:1 Changed 4 years ago by
 Branch set to u/klee/24170
comment:2 Changed 4 years ago by
 Commit set to 99cab913489df949057e3dc19cddcee74f0f487c
comment:3 Changed 4 years ago by
 Status changed from new to needs_review
comment:4 Changed 4 years ago by
 Commit changed from 99cab913489df949057e3dc19cddcee74f0f487c to 2b195ee9aa175cb85052eba0857564fd947d075b
Branch pushed to git repo; I updated commit sha1. New commits:
2b195ee  Finite field and vector space isomorphisms

comment:5 Changed 4 years ago by
 Commit changed from 2b195ee9aa175cb85052eba0857564fd947d075b to d3719c7102bf2a23dcd69b07ec0e6ffb1876f578
Branch pushed to git repo; I updated commit sha1. New commits:
d3719c7  Minor fixes for documentation

comment:6 followup: ↓ 7 Changed 3 years ago by
Wouldn't be possible to exend the current vector_space
method with extra optional arguments subfield
(which would default to the prime field as it used to be) and basis
?
comment:7 in reply to: ↑ 6 Changed 3 years ago by
Replying to vdelecroix:
Wouldn't be possible to exend the current
vector_space
method with extra optional argumentssubfield
(which would default to the prime field as it used to be) andbasis
?
That was my first attempt. That was not so neat and I gave up that approach, mainly because my code relies on the vector_space
method, which is fundamental, and in this approach, the code would be recursive.
Now that you suggest that, I will try that approach again, as I don't have any hard reason to argue that the approach should be bad.
comment:8 Changed 3 years ago by
 Commit changed from d3719c7102bf2a23dcd69b07ec0e6ffb1876f578 to 5150b3d35aaea8a9c4b5e56a92bb5fc3122bdd90
comment:9 Changed 3 years ago by
 Description modified (diff)
comment:10 Changed 3 years ago by
 Summary changed from Add vector_space_over method to finite fields to Extend vector_space method to arbitrary subfields
comment:11 Changed 3 years ago by
 Description modified (diff)
 Reviewers set to Vincent Delecroix
comment:12 followups: ↓ 13 ↓ 16 Changed 3 years ago by
 Status changed from needs_review to needs_work
 The name
FiniteFieldIsomorphism
is very misleading. Furthermore, as a general comment "isomorphism" is not a precise term. What about "linear isomorphism" as in?sage: E = GF(16) sage: F = GF(4) sage: V = VectorSpace(F, 2) sage: Hom(V,E) Set of Morphisms (Linear Transformations) from Vector space of dimension 2 over Finite Field in z2 of size 2^2 to Finite Field in z4 of size 2^4
 What is the point of having empty classes
MorphismFiniteFieldToVectorSpace
andMorphismVectorSpaceToFiniteField
? I would prefer to simply remove them and haveAn other option is to move all the code in phi = MorphismVectorSpaceToFiniteField(V, self, from_V)  psi = MorphismFiniteFieldToVectorSpace(self, V, to_V) + from sage.categories.homset import Hom + from sage.categories.morphism import SetMorphism + phi = SetMorphism(Hom(V, self), from_V) + psi = SetMorphism(Hom(self, V), to_V)
vector_space
(computation ofC
, the functionsto_V
,from_V
, etc) within the classes.
 Did you notice the asymetry of categories
sage: E = GF(16) sage: F = GF(4) sage: V = VectorSpace(F, 4) Set of Morphisms (Linear Transformations) from Vector space of dimension 2 over Finite Field in z2 of size 2^2 to Finite Field in z4 of size 2^4 sage: Hom(E,V) Set of Morphisms from Finite Field in z4 of size 2^4 to Vector space of dimension 2 over Finite Field in z2 of size 2^2 in Category of finite enumerated additive commutative additive groups
 In the function
to_V
you should use directlyV
and notvector
 In your call to
matrix
it is much faster to also specify the base ring and the dimensions.
comment:13 in reply to: ↑ 12 Changed 3 years ago by
Replying to vdelecroix:
 The name
FiniteFieldIsomorphism
is very misleading. Furthermore, as a general comment "isomorphism" is not a precise term. What about "linear isomorphism" as in?sage: E = GF(16) sage: F = GF(4) sage: V = VectorSpace(F, 2) sage: Hom(V,E) Set of Morphisms (Linear Transformations) from Vector space of dimension 2 over Finite Field in z2 of size 2^2 to Finite Field in z4 of size 2^4
 What is the point of having empty classes
MorphismFiniteFieldToVectorSpace
andMorphismVectorSpaceToFiniteField
? I would prefer to simply remove them and haveAn other option is to move all the code in phi = MorphismVectorSpaceToFiniteField(V, self, from_V)  psi = MorphismFiniteFieldToVectorSpace(self, V, to_V) + from sage.categories.homset import Hom + from sage.categories.morphism import SetMorphism + phi = SetMorphism(Hom(V, self), from_V) + psi = SetMorphism(Hom(self, V), to_V)vector_space
(computation ofC
, the functionsto_V
,from_V
, etc) within the classes.
I modelled these classes after the corresponding classes in sage/rings/number_field/maps.py
. Look at the NumberFieldIsomorphism
, MapVectorSpaceToNumberField
, MapNumberFieldToVectorSpace
.
The point is to have a proper _repr_()
method (the morphisms are printed as Isomorphism
).
The classes MorphismVectorSpaceToFiniteField
and MorphismFiniteFieldToVectorSpace
are not empty. They are extended from FiniteFieldIsomorphism
. So including inherited methods, each of them has 4 updated methods compared with SetMorphism
.
I guess that you think "finite field isomorphism" is misleading. The intended meaning is "vector space isomorphism" for finite fields. I reject "linear isomorphism" (I never heard of this term). FiniteFieldLinearTransformation
or FiniteFieldLinearMap
is ok, but I don't prefer them over FiniteFieldIsomorphism
.
comment:14 Changed 3 years ago by
 Commit changed from 5150b3d35aaea8a9c4b5e56a92bb5fc3122bdd90 to f97f00394586818689027894e2aacd4d02568ca5
comment:15 followup: ↓ 18 Changed 3 years ago by
Replying to klee:
Replying to vdelecroix:
 The name
FiniteFieldIsomorphism
is very misleading. Furthermore, as a general comment "isomorphism" is not a precise term. What about "linear isomorphism" as in?sage: E = GF(16) sage: F = GF(4) sage: V = VectorSpace(F, 2) sage: Hom(V,E) Set of Morphisms (Linear Transformations) from Vector space of dimension 2 over Finite Field in z2 of size 2^2 to Finite Field in z4 of size 2^4
 What is the point of having empty classes
MorphismFiniteFieldToVectorSpace
andMorphismVectorSpaceToFiniteField
? I would prefer to simply remove them and haveAn other option is to move all the code in phi = MorphismVectorSpaceToFiniteField(V, self, from_V)  psi = MorphismFiniteFieldToVectorSpace(self, V, to_V) + from sage.categories.homset import Hom + from sage.categories.morphism import SetMorphism + phi = SetMorphism(Hom(V, self), from_V) + psi = SetMorphism(Hom(self, V), to_V)vector_space
(computation ofC
, the functionsto_V
,from_V
, etc) within the classes.I modelled these classes after the corresponding classes in
sage/rings/number_field/maps.py
. Look at theNumberFieldIsomorphism
,MapVectorSpaceToNumberField
,MapNumberFieldToVectorSpace
.The point is to have a proper
_repr_()
method (the morphisms are printed asIsomorphism
).The classes
MorphismVectorSpaceToFiniteField
andMorphismFiniteFieldToVectorSpace
are not empty. They are extended fromFiniteFieldIsomorphism
. So including inherited methods, each of them has 4 updated methods compared withSetMorphism
.
As you can see, sage/rings/number_field/maps.py
implements the conversion from the domain to the image in their _call_
method. This is what I proposed in the end of the point 2 in 12. So I would better go for this option.
Now, if you don't like moving the implementation of for_V
and to_V
as a _call_
method of the linear isomorphisms classes you should just make the _repr_
method more configurable. No need to make a new class.
I guess that you think "finite field isomorphism" is misleading. The intended meaning is "vector space isomorphism" for finite fields. I reject "linear isomorphism" (I never heard of this term).
FiniteFieldLinearTransformation
orFiniteFieldLinearMap
is ok, but I don't prefer them overFiniteFieldIsomorphism
.
I do. Let me say what I imagine when I read each class name
FiniteFieldIsomorphism
: an isomorphism between two finite fieldsFiniteFieldLinearTransformation
: a linear map between two finite fields
comment:16 in reply to: ↑ 12 Changed 3 years ago by
 Did you notice the asymetry of categories
sage: E = GF(16) sage: F = GF(4) sage: V = VectorSpace(F, 4) Set of Morphisms (Linear Transformations) from Vector space of dimension 2 over Finite Field in z2 of size 2^2 to Finite Field in z4 of size 2^4 sage: Hom(E,V) Set of Morphisms from Finite Field in z4 of size 2^4 to Vector space of dimension 2 over Finite Field in z2 of size 2^2 in Category of finite enumerated additive commutative additive groups
No. This looks ugly.
What do mean by "asymmetry of categories"? I get
sage: category(Hom(E,V)) Category of homsets of additive monoids sage: category(Hom(V,E)) Category of homsets of additive monoids
Do you mean the printing?
Anyway, is this related with this ticket?
comment:17 Changed 3 years ago by
 Branch changed from u/klee/24170 to public/24170
comment:18 in reply to: ↑ 15 ; followup: ↓ 19 Changed 3 years ago by
Replying to vdelecroix:
I do. Let me say what I imagine when I read each class name
FiniteFieldIsomorphism
: an isomorphism between two finite fieldsFiniteFieldLinearTransformation
: a linear map between two finite fields
I understand your concern. But just LinearTransformation
is also misleading because these maps are vector space *isomorphisms*. But I will not insist. This is not a big deal to me.
As you can see,
sage/rings/number_field/maps.py
implements the conversion from the domain to the image in their_call_
method. This is what I proposed in the end of the point 2 in 12. So I would better go for this option.Now, if you don't like moving the implementation of
for_V
andto_V
as a_call_
method of the linear isomorphisms classes you should just make the_repr_
method more configurable. No need to make a new class.
I doubt that I understand your suggestions well. It seems that you have a clear view of how to code the maps. So I invite you to modify the branch (now public) as you prefer. I am quite willing to accept your modifications as long as Sage gets a working E.vector_space(F)
method :)
comment:19 in reply to: ↑ 18 Changed 3 years ago by
Replying to klee:
Replying to vdelecroix:
I do. Let me say what I imagine when I read each class name
FiniteFieldIsomorphism
: an isomorphism between two finite fieldsFiniteFieldLinearTransformation
: a linear map between two finite fieldsI understand your concern. But just
LinearTransformation
is also misleading because these maps are vector space *isomorphisms*. But I will not insist. This is not a big deal to me.
Indeed, they are *vector space* isomorphisms ;)
As you can see,
sage/rings/number_field/maps.py
implements the conversion from the domain to the image in their_call_
method. This is what I proposed in the end of the point 2 in 12. So I would better go for this option.Now, if you don't like moving the implementation of
for_V
andto_V
as a_call_
method of the linear isomorphisms classes you should just make the_repr_
method more configurable. No need to make a new class.I doubt that I understand your suggestions well. It seems that you have a clear view of how to code the maps. So I invite you to modify the branch (now public) as you prefer. I am quite willing to accept your modifications as long as Sage gets a working
E.vector_space(F)
method :)
I am trying something.
comment:20 followups: ↓ 21 ↓ 25 Changed 3 years ago by
 Branch changed from public/24170 to public/24170v2
 Commit changed from f97f00394586818689027894e2aacd4d02568ca5 to 2d3ec2c935881d0c28e533a23b46338b928a8390
I implemented what I proposed (and also squashed your commits into one).
For the sake of this ticket there are several things to be fixed
 The code does not work with
sage: F = GF(9) sage: x = polygen(F) sage: E.<y> = F.extension(x^3  x + 1) sage: E.vector_space(F) Traceback (most recent call last): ... AttributeError: 'PolynomialQuotientRing_field_with_category' object has no attribute 'vector_space'
 There are no examples involving a custom field such as
F = GF(9, 't', modulus=(x^2+x1))
 It would be better to not impose the subfield to have a coercion implemented. I would propose to allow to pass a morphism as argument to vector space instead of a subfield. (as you wish that could be a double use of
subfield
or an extra argumentinclusion_map
).
 The example
E = GF(16)
andF = GF(4)
is by far too trivial. In this case you haveV = GF(p^n)^m
with the same n and m.
New commits:
0361682  24170: extend vector_space method of finite fields

2d3ec2c  24170: implement _call_ instead of local functions

comment:21 in reply to: ↑ 20 ; followup: ↓ 22 Changed 3 years ago by
Replying to vdelecroix:
I implemented what I proposed (and also squashed your commits into one).
For the sake of this ticket there are several things to be fixed
 The code does not work with
sage: F = GF(9) sage: x = polygen(F) sage: E.<y> = F.extension(x^3  x + 1) sage: E.vector_space(F) Traceback (most recent call last): ... AttributeError: 'PolynomialQuotientRing_field_with_category' object has no attribute 'vector_space'
 There are no examples involving a custom field such as
F = GF(9, 't', modulus=(x^2+x1))
Right. These "finite fields" are actually PolynomialQuotientRing_field
. They are second citizen in terms of functionality as finite fields. My opinion is that finite fields defined with custom modulus should be reimplemented to be elevated to the first class citizen, and the current PolynomialQuotientRing_field
is just a patch work.
Anyway this ticket (or at least me) does not deal with PolynomialQuotientRing_field
.
comment:22 in reply to: ↑ 21 Changed 3 years ago by
Replying to klee:
Replying to vdelecroix:
I implemented what I proposed (and also squashed your commits into one).
For the sake of this ticket there are several things to be fixed
 The code does not work with
sage: F = GF(9) sage: x = polygen(F) sage: E.<y> = F.extension(x^3  x + 1) sage: E.vector_space(F) Traceback (most recent call last): ... AttributeError: 'PolynomialQuotientRing_field_with_category' object has no attribute 'vector_space'
 There are no examples involving a custom field such as
F = GF(9, 't', modulus=(x^2+x1))
Right. These "finite fields" are actually
PolynomialQuotientRing_field
. They are second citizen in terms of functionality as finite fields. My opinion is that finite fields defined with custom modulus should be reimplemented to be elevated to the first class citizen, and the currentPolynomialQuotientRing_field
is just a patch work.Anyway this ticket (or at least me) does not deal with
PolynomialQuotientRing_field
.
Second example is not
sage: F = GF(9, 't', modulus=(x^2+x1)) sage: type(F) <class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>
comment:23 Changed 3 years ago by
 Commit changed from 2d3ec2c935881d0c28e533a23b46338b928a8390 to 60242575333d2db9d0f2ae4c0f913bac12eb7a5b
Branch pushed to git repo; I updated commit sha1. New commits:
6024257  Allow morphism as subfield and add inclusion_map

comment:24 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:25 in reply to: ↑ 20 ; followup: ↓ 26 Changed 3 years ago by
Replying to vdelecroix:
I implemented what I proposed
Would you explain why this is necessary? As far as I understand, C
is just constructed and mutable, and this code will make a duplicate copy of C
. Why don't we just keep the original C
?
+ if C.is_mutable(): + C = C.__copy__() + C.set_immutable()
comment:26 in reply to: ↑ 25 ; followup: ↓ 27 Changed 3 years ago by
Replying to klee:
Replying to vdelecroix:
I implemented what I proposed
Would you explain why this is necessary? As far as I understand,
C
is just constructed and mutable, and this code will make a duplicate copy ofC
. Why don't we just keep the originalC
?+ if C.is_mutable(): + C = C.__copy__() + C.set_immutable()
The original C
is kept if it is immutable which is the way to go from the point of view of the constructor. If you want to avoid the copy in your function, make the matrix argument immutable first...
comment:27 in reply to: ↑ 26 ; followup: ↓ 28 Changed 3 years ago by
Replying to vdelecroix:
Replying to klee:
Replying to vdelecroix:
I implemented what I proposed
Would you explain why this is necessary? As far as I understand,
C
is just constructed and mutable, and this code will make a duplicate copy ofC
. Why don't we just keep the originalC
?+ if C.is_mutable(): + C = C.__copy__() + C.set_immutable()The original
C
is kept if it is immutable which is the way to go from the point of view of the constructor. If you want to avoid the copy in your function, make the matrix argument immutable first...
I know that by reading your code. From my point of view, the classes are only for vector_space()
method or at least used only internally. Then I wonder why we worry that C
could be mutable and that C
could be changed after the object was constructed (which seems the situation that you worry about). In other words, I doubt that your code above could be useful really, unless you convince me...
Is your code just a common idiom in Sage when an argument for a constructor is a matrix, which could be mutable (so that the code is required as a convention)?
comment:28 in reply to: ↑ 27 ; followup: ↓ 29 Changed 3 years ago by
Replying to klee:
Replying to vdelecroix:
Replying to klee:
Replying to vdelecroix:
I implemented what I proposed
Would you explain why this is necessary? As far as I understand,
C
is just constructed and mutable, and this code will make a duplicate copy ofC
. Why don't we just keep the originalC
?+ if C.is_mutable(): + C = C.__copy__() + C.set_immutable()The original
C
is kept if it is immutable which is the way to go from the point of view of the constructor. If you want to avoid the copy in your function, make the matrix argument immutable first...I know that by reading your code. From my point of view, the classes are only for
vector_space()
method or at least used only internally. Then I wonder why we worry thatC
could be mutable and thatC
could be changed after the object was constructed (which seems the situation that you worry about). In other words, I doubt that your code above could be useful really, unless you convince me...Is your code just a common idiom in Sage when an argument for a constructor is a matrix, which could be mutable (so that the code is required as a convention)?
For now, the class is only built with vector_space
but nobody knows the future. If you feel better with
assert C.is_immutable()
It is also fine for me.
comment:29 in reply to: ↑ 28 Changed 3 years ago by
Replying to vdelecroix:
For now, the class is only built with
vector_space
but nobody knows the future.
Ok. I see your motivation now. Then I would set the matrix C
immutable in vector_sapce
to prevent the copying.
What other issues do you have for this ticket? Are you ok with FiniteFieldVectorSpaceIsomorphism
?
comment:30 followup: ↓ 32 Changed 3 years ago by
Currently inclusion_map
argument is redundant. I may delete it if you agree.
comment:31 followup: ↓ 36 Changed 3 years ago by
Replying to klee:
Replying to vdelecroix:
For now, the class is only built with
vector_space
but nobody knows the future.Ok. I see your motivation now. Then I would set the matrix
C
immutable invector_sapce
to prevent the copying.What other issues do you have for this ticket?
I left a stupid comment
# from_V # needs C
in maps_finite_field.py
If this ticket is duplicating some features of what used to be implemented in linear code, then some appropriate deprecation has to be done (possibly in later ticket but please do create them)
Are you ok with
FiniteFieldVectorSpaceIsomorphism
?
I am.
comment:32 in reply to: ↑ 30 ; followup: ↓ 33 Changed 3 years ago by
Replying to klee:
Currently
inclusion_map
argument is redundant. I may delete it if you agree.
Redundant with what?
comment:33 in reply to: ↑ 32 ; followup: ↓ 34 Changed 3 years ago by
Replying to vdelecroix:
Replying to klee:
Currently
inclusion_map
argument is redundant. I may delete it if you agree.Redundant with what?
subfield
argument can take a morphism.
comment:34 in reply to: ↑ 33 Changed 3 years ago by
Replying to klee:
Replying to vdelecroix:
Replying to klee:
Currently
inclusion_map
argument is redundant. I may delete it if you agree.Redundant with what?
subfield
argument can take a morphism.
Ha ok. Very good.
comment:35 Changed 3 years ago by
 Commit changed from 60242575333d2db9d0f2ae4c0f913bac12eb7a5b to d20501819b3288ef4a8a57036ab884ab83cde69d
comment:36 in reply to: ↑ 31 Changed 3 years ago by
Replying to vdelecroix:
If this ticket is duplicating some features of what used to be implemented in linear code, then some appropriate deprecation has to be done (possibly in later ticket but please do create them)
Right. First we need some discussion. See #24279.
comment:37 Changed 3 years ago by
By the way, I am positive on Vincent's part of the code.
comment:38 followup: ↓ 39 Changed 3 years ago by
 Milestone changed from sage8.1 to sage8.2
 Reviewers changed from Vincent Delecroix to Vincent Delecroix, Kwankyu Lee
 Status changed from needs_review to positive_review
Let's go then.
comment:39 in reply to: ↑ 38 Changed 3 years ago by
Replying to vdelecroix:
Let's go then.
Thank you. The branch is way better than it originally was :)
comment:40 Changed 3 years ago by
 Branch changed from public/24170v2 to d20501819b3288ef4a8a57036ab884ab83cde69d
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Add vector_space_over method to finite fields