Opened 4 years ago
Closed 3 months ago
#26103 closed enhancement (invalid)
absolute_field() for towers of finite fields
Reported by: | saraedum | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | finite rings | Keywords: | finite fields, polynomial quotient ring, padicBordeaux |
Cc: | swewers, roed | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | u/saraedum/26103 (Commits, GitHub, GitLab) | Commit: | 0f7c2c959c577ef62edc7a2477dc7df6826d9f9a |
Dependencies: | #26105, #26161 | Stopgaps: |
Description (last modified by )
Towers of finite fields are hard to work with because they lose most of the nice functionality of simple extensions of prime finite fields and are also much slower.
Therefore it would be useful to have a method that turns a tower into a simple extension.
Note that there have been attempts to support relative extensions of finite fields in #21413 and that there is also sage.coding.relative_finite_field_extension
, the state of which is unclear to me. There is also _isomorphic_ring
on polynomial quotient rings which does something similar so this should probably be unified for finite fields.
Change History (18)
comment:1 Changed 4 years ago by
comment:2 Changed 4 years ago by
- Description modified (diff)
comment:3 Changed 4 years ago by
- Branch set to u/saraedum/26103
comment:4 Changed 4 years ago by
- Commit set to 2fc28c2d7324a2f15fc61582887c98ec5716b56c
- Dependencies set to #26105
New commits:
2fc28c2 | Add absolute_field() for finite fields
|
comment:5 Changed 4 years ago by
- Commit changed from 2fc28c2d7324a2f15fc61582887c98ec5716b56c to 14e6fdc6defb191b89e1eaf49ba6df681f6d1ba2
Branch pushed to git repo; I updated commit sha1. New commits:
14e6fdc | Comment on why this method should live in FiniteFields()
|
comment:6 Changed 4 years ago by
- Description modified (diff)
- Summary changed from simple_model() on quotients of polynomial rings to absolute_field() for towers of finite fields
comment:7 Changed 4 years ago by
- Commit changed from 14e6fdc6defb191b89e1eaf49ba6df681f6d1ba2 to 86857290813259c5a8f55655a62915f38b28c06f
Without proper support for morphisms with base_morphisms, the output is slightly ugly:
sage: k = GF(2) sage: R.<a> = k[] sage: l.<a> = k.extension(a^3 + a^2 + 1) sage: l.absolute_field() (Finite Field in z3 of size 2^3, Composite map: From: Finite Field in a of size 2^3 To: Finite Field in z3 of size 2^3 Defn: Ring morphism: From: Finite Field in a of size 2^3 To: Univariate Polynomial Ring in a over Finite Field of size 2 (using GF2X) Defn: a |--> a then Ring morphism: From: Univariate Polynomial Ring in a over Finite Field of size 2 (using GF2X) To: Univariate Polynomial Ring in a over Finite Field in z3 of size 2^3 Defn: Induced from base ring by Composite map: From: Finite Field of size 2 To: Finite Field in z3 of size 2^3 Defn: Identity endomorphism of Finite Field of size 2 then Ring morphism: From: Finite Field of size 2 To: Finite Field in z3 of size 2^3 Defn: 1 |--> 1 then Ring morphism: From: Univariate Polynomial Ring in a over Finite Field in z3 of size 2^3 To: Finite Field in z3 of size 2^3 Defn: a |--> z3^2 + 1, Ring morphism: From: Finite Field in z3 of size 2^3 To: Finite Field in a of size 2^3 Defn: z3 |--> a^2 + a)
Unfortunately, this does not work yet if we add another extension on top:
sage: R.<b> = l[] sage: m.<b> = l.extension(b^2 + b + a) sage: m.absolute_field() AttributeError: no attribute absolute_field
The problem is that even though m
is in the category of finite fields, it does not inherit the parent methods for some reason.
New commits:
cb8418a | Fix absolute_field() implementation
|
8685729 | Some temporary hacks to make absolute_field() work
|
comment:8 Changed 4 years ago by
- Commit changed from 86857290813259c5a8f55655a62915f38b28c06f to 8db7302fe39cfeb79f70a0f37986d8fc2001a85d
Branch pushed to git repo; I updated commit sha1. New commits:
8db7302 | Merge remote-tracking branch 'trac/develop' into 26103
|
comment:9 Changed 4 years ago by
It only gets worse for larger towers:
sage: R.<b> = l[] sage: m.<b> = l.extension(b^2 + b + a) sage: m.is_field() # refines category sage: m.absolute_field() (Finite Field in z6 of size 2^6, Composite map: From: Univariate Quotient Polynomial Ring in b over Finite Field in a of size 2^3 with modulus b^2 + b + a To: Finite Field in z6 of size 2^6 Defn: Ring morphism: From: Univariate Quotient Polynomial Ring in b over Finite Field in a of size 2^3 with modulus b^2 + b + a To: Univariate Polynomial Ring in b over Finite Field in a of size 2^3 Defn: b |--> b then Ring morphism: From: Univariate Polynomial Ring in b over Finite Field in a of size 2^3 To: Univariate Polynomial Ring in b over Finite Field in z6 of size 2^6 Defn: Induced from base ring by Composite map: From: Finite Field in a of size 2^3 To: Finite Field in z6 of size 2^6 Defn: Ring morphism: From: Finite Field in a of size 2^3 To: Univariate Polynomial Ring in a over Finite Field of size 2 (using GF2X) Defn: a |--> a then Ring morphism: From: Univariate Polynomial Ring in a over Finite Field of size 2 (using GF2X) To: Univariate Polynomial Ring in a over Finite Field in z3 of size 2^3 Defn: Induced from base ring by Composite map: From: Finite Field of size 2 To: Finite Field in z3 of size 2^3 Defn: Identity endomorphism of Finite Field of size 2 then Ring morphism: From: Finite Field of size 2 To: Finite Field in z3 of size 2^3 Defn: 1 |--> 1 then Ring morphism: From: Univariate Polynomial Ring in a over Finite Field in z3 of size 2^3 To: Finite Field in z3 of size 2^3 Defn: a |--> z3 + 1 then Ring morphism: From: Finite Field in z3 of size 2^3 To: Finite Field in z6 of size 2^6 Defn: z3 |--> z6^5 + z6^4 + z6^2 + 1 then Ring morphism: From: Univariate Polynomial Ring in b over Finite Field in z6 of size 2^6 To: Finite Field in z6 of size 2^6 Defn: b |--> z6^4 + z6^3, Ring morphism: From: Finite Field in z6 of size 2^6 To: Univariate Quotient Polynomial Ring in b over Finite Field in a of size 2^3 with modulus b^2 + b + a Defn: z6 |--> (a + 1)*b + a^2 + a)
comment:10 Changed 4 years ago by
- Commit changed from 8db7302fe39cfeb79f70a0f37986d8fc2001a85d to c68e16d40a05abf3a7729609358656d4e88935e7
Branch pushed to git repo; I updated commit sha1. New commits:
c68e16d | Hack around problems in morphisms of quotients and finite fields
|
comment:11 Changed 4 years ago by
- Dependencies changed from #26105 to #26105, #26161
comment:12 Changed 4 years ago by
- Commit changed from c68e16d40a05abf3a7729609358656d4e88935e7 to 0f7c2c959c577ef62edc7a2477dc7df6826d9f9a
comment:13 Changed 4 years ago by
- Description modified (diff)
comment:14 Changed 3 years ago by
- Keywords padicBordeaux added
comment:15 Changed 21 months ago by
https://gitlab.com/sagemath/sage/-/merge_requests/33 implements this in a more general way it seems.
So what's been done here is probably irrelevant.
comment:16 Changed 3 months ago by
- Milestone changed from sage-8.4 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
comment:17 Changed 3 months ago by
- Status changed from needs_review to positive_review
comment:18 Changed 3 months ago by
- Resolution set to invalid
- Status changed from positive_review to closed
See #25976 for a followup and https://github.com/MCLF/mclf/issues/103 for some context.