#24170 closed enhancement (fixed)

Extend vector_space method to arbitrary subfields

Reported by: klee Owned by:
Priority: minor Milestone: sage-8.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) Commit: d20501819b3288ef4a8a57036ab884ab83cde69d
Dependencies: Stopgaps:

Description (last modified by klee)

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 23 months ago by klee

  • Authors set to Kwankyu Lee
  • Branch set to u/klee/24170

comment:2 Changed 23 months ago by git

  • Commit set to 99cab913489df949057e3dc19cddcee74f0f487c

Branch pushed to git repo; I updated commit sha1. New commits:

99cab91Add vector_space_over method to finite fields

comment:3 Changed 23 months ago by klee

  • Status changed from new to needs_review

comment:4 Changed 23 months ago by git

  • Commit changed from 99cab913489df949057e3dc19cddcee74f0f487c to 2b195ee9aa175cb85052eba0857564fd947d075b

Branch pushed to git repo; I updated commit sha1. New commits:

2b195eeFinite field and vector space isomorphisms

comment:5 Changed 23 months ago by git

  • Commit changed from 2b195ee9aa175cb85052eba0857564fd947d075b to d3719c7102bf2a23dcd69b07ec0e6ffb1876f578

Branch pushed to git repo; I updated commit sha1. New commits:

d3719c7Minor fixes for documentation

comment:6 follow-up: Changed 22 months ago by vdelecroix

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 22 months ago by klee

Replying to vdelecroix:

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?

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 22 months ago by git

  • Commit changed from d3719c7102bf2a23dcd69b07ec0e6ffb1876f578 to 5150b3d35aaea8a9c4b5e56a92bb5fc3122bdd90

Branch pushed to git repo; I updated commit sha1. New commits:

e0d257aMerge to develop
5150b3dMerge with vector_space method

comment:9 Changed 22 months ago by klee

  • Description modified (diff)

comment:10 Changed 22 months ago by klee

  • Summary changed from Add vector_space_over method to finite fields to Extend vector_space method to arbitrary subfields

comment:11 Changed 22 months ago by klee

  • Description modified (diff)
  • Reviewers set to Vincent Delecroix

comment:12 follow-ups: Changed 22 months ago by vdelecroix

  • Status changed from needs_review to needs_work
  1. 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
    
  1. What is the point of having empty classes MorphismFiniteFieldToVectorSpace and MorphismVectorSpaceToFiniteField? I would prefer to simply remove them and have
    -        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)
    
    An other option is to move all the code in vector_space (computation of C, the functions to_V, from_V, etc) within the classes.
  1. 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
    
  1. In the function to_V you should use directly V and not vector
  1. 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 22 months ago by klee

Replying to vdelecroix:

  1. 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
    
  1. What is the point of having empty classes MorphismFiniteFieldToVectorSpace and MorphismVectorSpaceToFiniteField? I would prefer to simply remove them and have
    -        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)
    
    An other option is to move all the code in vector_space (computation of C, the functions to_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 22 months ago by git

  • Commit changed from 5150b3d35aaea8a9c4b5e56a92bb5fc3122bdd90 to f97f00394586818689027894e2aacd4d02568ca5

Branch pushed to git repo; I updated commit sha1. New commits:

5b8684fMerge develop
f97f003Speed up matrix construction

comment:15 follow-up: Changed 22 months ago by vdelecroix

Replying to klee:

Replying to vdelecroix:

  1. 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
    
  1. What is the point of having empty classes MorphismFiniteFieldToVectorSpace and MorphismVectorSpaceToFiniteField? I would prefer to simply remove them and have
    -        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)
    
    An other option is to move all the code in vector_space (computation of C, the functions to_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.

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 or FiniteFieldLinearMap is ok, but I don't prefer them over FiniteFieldIsomorphism.

I do. Let me say what I imagine when I read each class name

  • FiniteFieldIsomorphism : an isomorphism between two finite fields
  • FiniteFieldLinearTransformation: a linear map between two finite fields

comment:16 in reply to: ↑ 12 Changed 22 months ago by klee

  1. 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 22 months ago by klee

  • Branch changed from u/klee/24170 to public/24170

comment:18 in reply to: ↑ 15 ; follow-up: Changed 22 months ago by klee

Replying to vdelecroix:

I do. Let me say what I imagine when I read each class name

  • FiniteFieldIsomorphism : an isomorphism between two finite fields
  • FiniteFieldLinearTransformation: 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 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 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 22 months ago by vdelecroix

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 fields
  • FiniteFieldLinearTransformation: 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.

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 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 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 follow-ups: Changed 22 months ago by vdelecroix

  • Branch changed from public/24170 to public/24170-v2
  • 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

  1. 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'
    
  1. There are no examples involving a custom field such as F = GF(9, 't', modulus=(x^2+x-1))
  1. 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 argument inclusion_map).
  1. The example E = GF(16) and F = GF(4) is by far too trivial. In this case you have V = GF(p^n)^m with the same n and m.

New commits:

036168224170: extend vector_space method of finite fields
2d3ec2c24170: implement _call_ instead of local functions
Last edited 22 months ago by vdelecroix (previous) (diff)

comment:21 in reply to: ↑ 20 ; follow-up: Changed 22 months ago by 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

  1. 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'
    
  1. There are no examples involving a custom field such as F = GF(9, 't', modulus=(x^2+x-1))

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 22 months ago by vdelecroix

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

  1. 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'
    
  1. There are no examples involving a custom field such as F = GF(9, 't', modulus=(x^2+x-1))

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.

Second example is not

sage: F = GF(9, 't', modulus=(x^2+x-1))
sage: type(F)
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>

comment:23 Changed 22 months ago by git

  • Commit changed from 2d3ec2c935881d0c28e533a23b46338b928a8390 to 60242575333d2db9d0f2ae4c0f913bac12eb7a5b

Branch pushed to git repo; I updated commit sha1. New commits:

6024257Allow morphism as subfield and add inclusion_map

comment:24 Changed 22 months ago by klee

  • Status changed from needs_work to needs_review

comment:25 in reply to: ↑ 20 ; follow-up: Changed 22 months ago by 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 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 ; follow-up: Changed 22 months ago by 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 of C. Why don't we just keep the original C?

+        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 ; follow-up: Changed 22 months ago by 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 of C. Why don't we just keep the original C?

+        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 ; follow-up: Changed 22 months ago by vdelecroix

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 of C. Why don't we just keep the original C?

+        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)?

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 22 months ago by 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 in vector_sapce to prevent the copying.

What other issues do you have for this ticket? Are you ok with FiniteFieldVectorSpaceIsomorphism?

comment:30 follow-up: Changed 22 months ago by klee

Currently inclusion_map argument is redundant. I may delete it if you agree.

comment:31 follow-up: Changed 22 months ago by vdelecroix

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 in vector_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 ; follow-up: Changed 22 months ago by vdelecroix

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 ; follow-up: Changed 22 months ago by 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.

comment:34 in reply to: ↑ 33 Changed 22 months ago by vdelecroix

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 22 months ago by git

  • Commit changed from 60242575333d2db9d0f2ae4c0f913bac12eb7a5b to d20501819b3288ef4a8a57036ab884ab83cde69d

Branch pushed to git repo; I updated commit sha1. New commits:

02b6c3eMerge develop
d205018Set C and Cinv immutable

comment:36 in reply to: ↑ 31 Changed 22 months ago by klee

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 22 months ago by klee

By the way, I am positive on Vincent's part of the code.

comment:38 follow-up: Changed 22 months ago by vdelecroix

  • Authors changed from Kwankyu Lee to Kwankyu Lee, Vincent Delecroix
  • Milestone changed from sage-8.1 to sage-8.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 22 months ago by klee

Replying to vdelecroix:

Let's go then.

Thank you. The branch is way better than it originally was :-)

comment:40 Changed 21 months ago by vbraun

  • Branch changed from public/24170-v2 to d20501819b3288ef4a8a57036ab884ab83cde69d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.