algebraeon_rings/structure/
homomorphisms.rs

1use super::*;
2use crate::matrix::{Matrix, MatrixStructure};
3use crate::polynomial::Polynomial;
4use algebraeon_sets::structure::*;
5use std::borrow::Borrow;
6use std::collections::{HashMap, HashSet};
7use std::fmt::Debug;
8use std::marker::PhantomData;
9
10mod range_module {
11    use std::borrow::Cow;
12
13    use itertools::Itertools;
14
15    use super::*;
16    #[derive(Debug, Clone)]
17    pub struct RingHomomorphismRangeModuleStructure<
18        'h,
19        Domain: RingSignature,
20        Range: RingSignature,
21        Hom: RingHomomorphism<Domain, Range>,
22    > {
23        _domain: PhantomData<Domain>,
24        _range: PhantomData<Range>,
25        hom: Cow<'h, Hom>,
26    }
27
28    impl<'h, Domain: RingSignature, Range: RingSignature, Hom: RingHomomorphism<Domain, Range>>
29        RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
30    {
31        fn new(hom: Cow<'h, Hom>) -> Self {
32            Self {
33                _domain: PhantomData,
34                _range: PhantomData,
35                hom,
36            }
37        }
38
39        pub fn module(&self) -> &Range {
40            self.hom.range()
41        }
42
43        pub fn homomorphism(&'h self) -> &'h Hom {
44            self.hom.as_ref()
45        }
46    }
47
48    impl<'h, Domain: RingSignature, Range: RingSignature, Hom: RingHomomorphism<Domain, Range>>
49        PartialEq for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
50    {
51        fn eq(&self, other: &Self) -> bool {
52            std::ptr::eq(self.hom.as_ref(), other.hom.as_ref())
53        }
54    }
55
56    impl<'h, Domain: RingSignature, Range: RingSignature, Hom: RingHomomorphism<Domain, Range>> Eq
57        for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
58    {
59    }
60
61    impl<'h, Domain: RingSignature, Range: RingSignature, Hom: RingHomomorphism<Domain, Range>>
62        Signature for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
63    {
64    }
65
66    impl<'h, Domain: RingSignature, Range: RingSignature, Hom: RingHomomorphism<Domain, Range>>
67        RinglikeSpecializationSignature
68        for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
69    {
70    }
71
72    impl<'h, Domain: RingSignature, Range: RingSignature, Hom: RingHomomorphism<Domain, Range>>
73        SetSignature for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
74    {
75        type Set = Range::Set;
76
77        fn is_element(&self, x: &Self::Set) -> Result<(), String> {
78            self.hom.range().is_element(x)
79        }
80    }
81
82    impl<'h, Domain: RingSignature, Range: RingEqSignature, Hom: RingHomomorphism<Domain, Range>>
83        EqSignature for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
84    {
85        fn equal(&self, a: &Self::Set, b: &Self::Set) -> bool {
86            self.hom.range().equal(a, b)
87        }
88    }
89
90    impl<'h, Domain: RingSignature, Range: RingSignature, Hom: RingHomomorphism<Domain, Range>>
91        ZeroSignature for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
92    {
93        fn zero(&self) -> Self::Set {
94            self.hom.range().zero()
95        }
96    }
97
98    impl<'h, Domain: RingSignature, Range: RingSignature, Hom: RingHomomorphism<Domain, Range>>
99        AdditionSignature for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
100    {
101        fn add(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
102            self.hom.range().add(a, b)
103        }
104    }
105
106    impl<'h, Domain: RingSignature, Range: RingSignature, Hom: RingHomomorphism<Domain, Range>>
107        CancellativeAdditionSignature
108        for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
109    {
110        fn try_sub(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
111            Some(self.sub(a, b))
112        }
113    }
114
115    impl<'h, Domain: RingSignature, Range: RingSignature, Hom: RingHomomorphism<Domain, Range>>
116        TryNegateSignature for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
117    {
118        fn try_neg(&self, a: &Self::Set) -> Option<Self::Set> {
119            Some(self.neg(a))
120        }
121    }
122
123    impl<'h, Domain: RingSignature, Range: RingSignature, Hom: RingHomomorphism<Domain, Range>>
124        AdditiveMonoidSignature for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
125    {
126    }
127
128    impl<'h, Domain: RingSignature, Range: RingSignature, Hom: RingHomomorphism<Domain, Range>>
129        AdditiveGroupSignature for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
130    {
131        fn neg(&self, a: &Self::Set) -> Self::Set {
132            self.hom.range().neg(a)
133        }
134    }
135
136    impl<'h, Domain: RingSignature, Range: RingSignature, Hom: RingHomomorphism<Domain, Range>>
137        SemiModuleSignature<Domain>
138        for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
139    {
140        fn ring(&self) -> &Domain {
141            self.hom.domain()
142        }
143
144        fn scalar_mul(&self, a: &Self::Set, x: &Domain::Set) -> Self::Set {
145            self.hom.range().mul(&self.hom.image(x), a)
146        }
147    }
148
149    impl<
150        'h,
151        Domain: RingSignature + FiniteSetSignature,
152        Range: RingSignature,
153        Hom: FiniteRankFreeRingExtension<Domain, Range>,
154    > CountableSetSignature for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
155    {
156        fn generate_all_elements(&self) -> impl Iterator<Item = Self::Set> + Clone {
157            let n = self.homomorphism().degree();
158            (0..n)
159                .map(|_| self.ring().list_all_elements())
160                .multi_cartesian_product()
161                .map(|v| self.homomorphism().from_vec(v))
162        }
163    }
164
165    impl<
166        'h,
167        Domain: RingSignature + FiniteSetSignature,
168        Range: RingSignature,
169        Hom: FiniteRankFreeRingExtension<Domain, Range>,
170    > FiniteSetSignature for RingHomomorphismRangeModuleStructure<'h, Domain, Range, Hom>
171    {
172    }
173
174    pub trait RingHomomorphism<Domain: RingSignature, Range: RingSignature>:
175        Function<Domain, Range>
176    {
177        fn range_module_structure<'h>(
178            &'h self,
179        ) -> RingHomomorphismRangeModuleStructure<'h, Domain, Range, Self> {
180            RingHomomorphismRangeModuleStructure::new(Cow::Borrowed(self))
181        }
182
183        fn into_range_module_structure(
184            self,
185        ) -> RingHomomorphismRangeModuleStructure<'static, Domain, Range, Self> {
186            RingHomomorphismRangeModuleStructure::new(Cow::Owned(self))
187        }
188    }
189
190    impl<
191        A: RingSignature,
192        B: RingSignature,
193        C: RingSignature,
194        AB: RingHomomorphism<A, B>,
195        BC: RingHomomorphism<B, C>,
196    > RingHomomorphism<A, C> for CompositionMorphism<A, B, C, AB, BC>
197    {
198    }
199}
200pub use range_module::*;
201
202mod principal_subring_inclusion {
203    use super::*;
204    use algebraeon_nzq::*;
205
206    /// The unique ring homomorphism Z -> R of the integers into any ring R
207    #[derive(Debug, Clone, PartialEq, Eq)]
208    pub struct PrincipalIntegerMap<Ring: RingSignature, RingB: BorrowedStructure<Ring>> {
209        _ring: PhantomData<Ring>,
210        ring: RingB,
211    }
212
213    impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>> PrincipalIntegerMap<Ring, RingB> {
214        pub fn new(ring: RingB) -> Self {
215            Self {
216                _ring: PhantomData,
217                ring,
218            }
219        }
220    }
221
222    impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>>
223        Morphism<IntegerCanonicalStructure, Ring> for PrincipalIntegerMap<Ring, RingB>
224    {
225        fn domain(&self) -> &IntegerCanonicalStructure {
226            Integer::structure_ref()
227        }
228
229        fn range(&self) -> &Ring {
230            self.ring.borrow()
231        }
232    }
233
234    impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>>
235        Function<IntegerCanonicalStructure, Ring> for PrincipalIntegerMap<Ring, RingB>
236    {
237        fn image(&self, x: &Integer) -> <Ring as SetSignature>::Set {
238            self.range().from_int(x)
239        }
240    }
241
242    impl<Ring: CharZeroRingSignature, RingB: BorrowedStructure<Ring>>
243        InjectiveFunction<IntegerCanonicalStructure, Ring> for PrincipalIntegerMap<Ring, RingB>
244    {
245        fn try_preimage(&self, x: &<Ring as SetSignature>::Set) -> Option<Integer> {
246            self.range().try_to_int(x)
247        }
248    }
249
250    impl<Ring: RingSignature, RingB: BorrowedStructure<Ring>>
251        RingHomomorphism<IntegerCanonicalStructure, Ring> for PrincipalIntegerMap<Ring, RingB>
252    {
253    }
254
255    /// The unique field embedding Q -> K of the rationals into any field of characteristic zero
256    #[derive(Debug, Clone, PartialEq, Eq)]
257    pub struct PrincipalRationalMap<Field: CharZeroFieldSignature, FieldB: BorrowedStructure<Field>> {
258        _field: PhantomData<Field>,
259        field: FieldB,
260    }
261
262    impl<Field: CharZeroFieldSignature, FieldB: BorrowedStructure<Field>>
263        PrincipalRationalMap<Field, FieldB>
264    {
265        pub fn new(field: FieldB) -> Self {
266            Self {
267                _field: PhantomData,
268                field,
269            }
270        }
271    }
272
273    impl<Field: CharZeroFieldSignature, FieldB: BorrowedStructure<Field>>
274        Morphism<RationalCanonicalStructure, Field> for PrincipalRationalMap<Field, FieldB>
275    {
276        fn domain(&self) -> &RationalCanonicalStructure {
277            Rational::structure_ref()
278        }
279
280        fn range(&self) -> &Field {
281            self.field.borrow()
282        }
283    }
284
285    impl<Field: CharZeroFieldSignature, FieldB: BorrowedStructure<Field>>
286        Function<RationalCanonicalStructure, Field> for PrincipalRationalMap<Field, FieldB>
287    {
288        fn image(&self, x: &Rational) -> <Field as SetSignature>::Set {
289            self.range().try_from_rat(x).unwrap()
290        }
291    }
292
293    impl<Field: CharZeroFieldSignature, FieldB: BorrowedStructure<Field>>
294        InjectiveFunction<RationalCanonicalStructure, Field>
295        for PrincipalRationalMap<Field, FieldB>
296    {
297        fn try_preimage(&self, x: &<Field as SetSignature>::Set) -> Option<Rational> {
298            self.range().try_to_rat(x)
299        }
300    }
301
302    impl<Field: CharZeroFieldSignature, FieldB: BorrowedStructure<Field>>
303        RingHomomorphism<RationalCanonicalStructure, Field>
304        for PrincipalRationalMap<Field, FieldB>
305    {
306    }
307}
308pub use principal_subring_inclusion::*;
309
310/// The inclusion of an integral domain into its field of fractions
311pub trait FieldOfFractionsInclusion<Ring: RingSignature, Field: FieldSignature>:
312    RingHomomorphism<Ring, Field> + InjectiveFunction<Ring, Field>
313{
314    fn numerator_and_denominator(&self, a: &Field::Set) -> (Ring::Set, Ring::Set);
315    fn numerator(&self, a: &Field::Set) -> Ring::Set {
316        self.numerator_and_denominator(a).0
317    }
318    fn denominator(&self, a: &Field::Set) -> Ring::Set {
319        self.numerator_and_denominator(a).1
320    }
321}
322
323/// An injective homomorphism A -> B of integral domains where there is a way to get all roots in B of a polynomial over A
324pub trait IntegralDomainExtensionAllPolynomialRoots<
325    A: IntegralDomainSignature,
326    B: IntegralDomainSignature,
327>: RingHomomorphism<A, B> + InjectiveFunction<A, B>
328{
329    /// Return all roots of the polynomial in B with duplicate elements according to multiplicity
330    fn all_roots(&self, polynomial: &Polynomial<A::Set>) -> Vec<B::Set>;
331}
332
333/// A ring extension Z -> R such that R is a finitely free Z-module
334pub trait FiniteRankFreeRingExtension<Z: RingSignature, R: RingSignature>:
335    RingHomomorphism<Z, R> + InjectiveFunction<Z, R>
336{
337    // things inherited from the finitely free domain-module structure on the range
338    fn degree(&self) -> usize;
339    fn to_vec(&self, a: &R::Set) -> Vec<Z::Set>;
340    fn from_vec(&self, v: Vec<impl Borrow<Z::Set>>) -> R::Set;
341    fn to_col(&self, a: &R::Set) -> Matrix<Z::Set>;
342    fn from_col(&self, v: Matrix<Z::Set>) -> R::Set;
343    fn to_row(&self, a: &R::Set) -> Matrix<Z::Set>;
344    fn from_row(&self, v: Matrix<Z::Set>) -> R::Set;
345
346    /// matrix representing column vector multiplication by `a` on the left
347    fn col_multiplication_matrix(&self, a: &R::Set) -> Matrix<Z::Set>;
348
349    /// matrix representing row vector multiplication by `a` on the right
350    fn row_multiplication_matrix(&self, a: &R::Set) -> Matrix<Z::Set>;
351}
352
353impl<Z: RingSignature, R: RingSignature, Hom: RingHomomorphism<Z, R> + InjectiveFunction<Z, R>>
354    FiniteRankFreeRingExtension<Z, R> for Hom
355where
356    for<'h> RingHomomorphismRangeModuleStructure<'h, Z, R, Self>:
357        FinitelyFreeModuleSignature<Z, Set = R::Set>,
358    for<'h> <RingHomomorphismRangeModuleStructure<'h, Z, R, Self> as FreeModuleSignature<Z>>::Basis:
359        FiniteSetSignature,
360{
361    fn degree(&self) -> usize {
362        self.range_module_structure().rank()
363    }
364    fn to_vec(&self, a: &R::Set) -> Vec<Z::Set> {
365        self.range_module_structure().to_vec(a)
366    }
367    fn from_vec(&self, v: Vec<impl Borrow<Z::Set>>) -> R::Set {
368        self.range_module_structure().from_vec(v)
369    }
370    fn to_col(&self, a: &R::Set) -> Matrix<Z::Set> {
371        self.range_module_structure().to_col(a)
372    }
373    fn from_col(&self, v: Matrix<Z::Set>) -> R::Set {
374        self.range_module_structure().from_col(v)
375    }
376    fn to_row(&self, a: &R::Set) -> Matrix<Z::Set> {
377        self.range_module_structure().to_row(a)
378    }
379    fn from_row(&self, v: Matrix<Z::Set>) -> R::Set {
380        self.range_module_structure().from_row(v)
381    }
382
383    fn col_multiplication_matrix(&self, a: &R::Set) -> Matrix<Z::Set> {
384        let basis = self.range_module_structure().basis_vecs();
385        Matrix::from_cols(
386            (0..self.degree())
387                .map(|i| {
388                    self.range_module_structure()
389                        .to_vec(&self.range().mul(a, &basis[i]))
390                })
391                .collect(),
392        )
393    }
394
395    fn row_multiplication_matrix(&self, a: &R::Set) -> Matrix<Z::Set> {
396        self.col_multiplication_matrix(a).transpose()
397    }
398}
399
400/// A finite dimensional field extension F -> K
401pub trait FiniteDimensionalFieldExtension<F: FieldSignature, K: FieldSignature>:
402    RingHomomorphism<F, K> + InjectiveFunction<F, K> + FiniteRankFreeRingExtension<F, K>
403{
404    fn norm(&self, a: &K::Set) -> F::Set;
405
406    fn trace(&self, a: &K::Set) -> F::Set;
407
408    /// The monic minimal polynomial of a
409    fn min_poly(&self, a: &K::Set) -> Polynomial<F::Set>;
410
411    fn trace_form_matrix(&self, elems: &[K::Set]) -> Matrix<F::Set> {
412        let n = self.degree();
413        assert_eq!(n, elems.len());
414        Matrix::construct(n, n, |r, c| {
415            self.trace(&self.range().mul(&elems[r], &elems[c]))
416        })
417    }
418
419    fn discriminant(&self, elems: &[K::Set]) -> F::Set {
420        MatrixStructure::new(self.domain().clone())
421            .det(self.trace_form_matrix(elems))
422            .unwrap()
423    }
424}
425
426impl<F: FieldSignature, K: FieldSignature, Hom: RingHomomorphism<F, K> + InjectiveFunction<F, K>>
427    FiniteDimensionalFieldExtension<F, K> for Hom
428where
429    for<'h> RingHomomorphismRangeModuleStructure<'h, F, K, Self>:
430        FinitelyFreeModuleSignature<F, Set = K::Set>,
431    for<'h> <RingHomomorphismRangeModuleStructure<'h, F, K, Self> as FreeModuleSignature<F>>::Basis:
432        FiniteSetSignature,
433{
434    fn norm(&self, a: &K::Set) -> F::Set {
435        MatrixStructure::new(self.domain().clone())
436            .det(self.col_multiplication_matrix(a))
437            .unwrap()
438    }
439
440    fn trace(&self, a: &K::Set) -> F::Set {
441        MatrixStructure::new(self.domain().clone())
442            .trace(&self.col_multiplication_matrix(a))
443            .unwrap()
444    }
445
446    fn min_poly(&self, a: &K::Set) -> Polynomial<F::Set> {
447        MatrixStructure::new(self.domain().clone())
448            .minimal_polynomial(self.col_multiplication_matrix(a))
449            .unwrap()
450    }
451}
452
453/// Represent all ring homomorphisms from `domain` to `range`
454#[derive(Debug, Clone, PartialEq, Eq)]
455pub struct RingHomomorphisms<Domain: RingSignature, Range: RingSignature> {
456    domain: Domain,
457    range: Range,
458}
459
460impl<Domain: RingSignature, Range: RingSignature> RingHomomorphisms<Domain, Range> {
461    pub fn new(domain: Domain, range: Range) -> Self {
462        Self { domain, range }
463    }
464}
465
466impl<Domain: RingSignature, Range: RingSignature> Signature for RingHomomorphisms<Domain, Range> {}
467
468impl<Domain: FreeRingSignature, Range: RingSignature> SetSignature
469    for RingHomomorphisms<Domain, Range>
470{
471    type Set = HashMap<Domain::Generator, Range::Set>;
472
473    fn is_element(&self, x: &Self::Set) -> Result<(), String> {
474        if self.domain.free_generators() != x.keys().cloned().collect::<HashSet<_>>() {
475            return Err("missing key".to_string());
476        }
477
478        for v in x.values() {
479            self.range.is_element(v)?;
480        }
481
482        Ok(())
483    }
484}
algebraeon_rings/structure/homomorphisms.rs

algebraeon_rings/structure/
homomorphisms.rs
