algebraeon_rings/structure/
rings.rs

1use super::*;
2use crate::polynomial::*;
3use algebraeon_macros::{signature_meta_trait, skip_meta};
4use algebraeon_nzq::{Integer, Natural, NaturalCanonicalStructure, Rational, traits::*};
5use algebraeon_sets::structure::*;
6use std::{borrow::Borrow, fmt::Debug};
7
8mod unconstructable_universal_structure {
9    use algebraeon_sets::structure::{EqSignature, SetSignature, Signature};
10    use std::fmt::Debug;
11    use std::marker::PhantomData;
12
13    use crate::structure::{
14        AdditionSignature, AdditiveGroupSignature, AdditiveMonoidSignature,
15        CancellativeAdditionSignature, CharZeroRingSignature, CharacteristicSignature,
16        CommutativeMultiplicationSignature, LeftDistributiveMultiplicationOverAddition,
17        MultiplicationSignature, MultiplicativeAbsorptionMonoidSignature,
18        MultiplicativeMonoidSignature, OneSignature, RightDistributiveMultiplicationOverAddition,
19        RingSignature, RinglikeSpecializationSignature, SemiRingSignature, TryNegateSignature,
20        TryReciprocalSignature, ZeroSignature,
21    };
22
23    pub struct UnconstructableStructure<Set> {
24        _set: PhantomData<Set>,
25    }
26
27    unsafe impl<Set> Send for UnconstructableStructure<Set> {}
28
29    unsafe impl<Set> Sync for UnconstructableStructure<Set> {}
30
31    impl<Set> Debug for UnconstructableStructure<Set> {
32        fn fmt(&self, _f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
33            unreachable!()
34        }
35    }
36
37    impl<Set> Clone for UnconstructableStructure<Set> {
38        fn clone(&self) -> Self {
39            unreachable!()
40        }
41    }
42
43    impl<Set> PartialEq for UnconstructableStructure<Set> {
44        fn eq(&self, _other: &Self) -> bool {
45            unreachable!()
46        }
47    }
48
49    impl<Set> Eq for UnconstructableStructure<Set> {}
50
51    impl<Set> Signature for UnconstructableStructure<Set> {}
52
53    impl<Set: Debug + Clone + Send + Sync> SetSignature for UnconstructableStructure<Set> {
54        type Set = Set;
55
56        fn is_element(&self, _x: &Self::Set) -> Result<(), String> {
57            unreachable!()
58        }
59    }
60
61    impl<Set: Debug + Clone + Send + Sync> EqSignature for UnconstructableStructure<Set> {
62        fn equal(&self, _a: &Self::Set, _b: &Self::Set) -> bool {
63            unreachable!()
64        }
65    }
66
67    impl<Set: Debug + Clone + Send + Sync> RinglikeSpecializationSignature
68        for UnconstructableStructure<Set>
69    {
70    }
71
72    impl<Set: Debug + Clone + Send + Sync> ZeroSignature for UnconstructableStructure<Set> {
73        fn zero(&self) -> Self::Set {
74            unreachable!()
75        }
76    }
77
78    impl<Set: Debug + Clone + Send + Sync> AdditionSignature for UnconstructableStructure<Set> {
79        fn add(&self, _a: &Self::Set, _b: &Self::Set) -> Self::Set {
80            unreachable!()
81        }
82    }
83
84    impl<Set: Debug + Clone + Send + Sync> CancellativeAdditionSignature
85        for UnconstructableStructure<Set>
86    {
87        fn try_sub(&self, _a: &Self::Set, _b: &Self::Set) -> Option<Self::Set> {
88            unreachable!()
89        }
90    }
91
92    impl<Set: Debug + Clone + Send + Sync> TryNegateSignature for UnconstructableStructure<Set> {
93        fn try_neg(&self, _a: &Self::Set) -> Option<Self::Set> {
94            unreachable!()
95        }
96    }
97
98    impl<Set: Debug + Clone + Send + Sync> AdditiveMonoidSignature for UnconstructableStructure<Set> {}
99
100    impl<Set: Debug + Clone + Send + Sync> AdditiveGroupSignature for UnconstructableStructure<Set> {
101        fn neg(&self, _a: &Self::Set) -> Self::Set {
102            unreachable!()
103        }
104    }
105
106    impl<Set: Debug + Clone + Send + Sync> OneSignature for UnconstructableStructure<Set> {
107        fn one(&self) -> Self::Set {
108            unreachable!()
109        }
110    }
111
112    impl<Set: Debug + Clone + Send + Sync> MultiplicationSignature for UnconstructableStructure<Set> {
113        fn mul(&self, _a: &Self::Set, _b: &Self::Set) -> Self::Set {
114            unreachable!()
115        }
116    }
117
118    impl<Set: Debug + Clone + Send + Sync> CommutativeMultiplicationSignature
119        for UnconstructableStructure<Set>
120    {
121    }
122
123    impl<Set: Debug + Clone + Send + Sync> TryReciprocalSignature for UnconstructableStructure<Set> {
124        fn try_reciprocal(&self, _a: &Self::Set) -> Option<Self::Set> {
125            unreachable!()
126        }
127    }
128
129    impl<Set: Debug + Clone + Send + Sync> MultiplicativeMonoidSignature
130        for UnconstructableStructure<Set>
131    {
132    }
133
134    impl<Set: Debug + Clone + Send + Sync> MultiplicativeAbsorptionMonoidSignature
135        for UnconstructableStructure<Set>
136    {
137    }
138
139    impl<Set: Debug + Clone + Send + Sync> LeftDistributiveMultiplicationOverAddition
140        for UnconstructableStructure<Set>
141    {
142    }
143
144    impl<Set: Debug + Clone + Send + Sync> RightDistributiveMultiplicationOverAddition
145        for UnconstructableStructure<Set>
146    {
147    }
148
149    impl<Set: Debug + Clone + Send + Sync> SemiRingSignature for UnconstructableStructure<Set> {}
150
151    impl<Set: Debug + Clone + Send + Sync> CharacteristicSignature for UnconstructableStructure<Set> {
152        fn characteristic(&self) -> algebraeon_nzq::Natural {
153            unreachable!()
154        }
155    }
156
157    impl<Set: Debug + Clone + Send + Sync> RingSignature for UnconstructableStructure<Set> {}
158
159    impl<Set: Debug + Clone + Send + Sync> CharZeroRingSignature for UnconstructableStructure<Set> {
160        fn try_to_int(&self, _x: &Self::Set) -> Option<algebraeon_nzq::Integer> {
161            unreachable!()
162        }
163    }
164}
165
166/*
167All methods are allowed to return None, and if they do it should only affect speed of algorithms, not correctness.
168Where methods do not return None, the resulting structure may be used for optimizations only.
169
170The methods currently require cloning some structures when sucessful.
171That's because it's currently prohibitively messy to allow returning by value or by reference depending on context.
172Stabilisation of Rust features such as impl aliases may make this more feasible in future.
173*/
174pub trait RinglikeSpecializationSignature: SetSignature + ToOwned<Owned = Self> {
175    /*
176    Used by:
177     - Polynomial rings to determine whether the karatsuba is usable.
178     */
179    fn try_ring_restructure(&self) -> Option<impl EqSignature<Set = Self::Set> + RingSignature> {
180        Option::<unconstructable_universal_structure::UnconstructableStructure<Self::Set>>::None
181    }
182
183    /*
184    Used by:
185     - Formatting polynomials as strings: If the set of coefficients has this structure then it's possible to call .try_to_int(..) which can allow for nicer formatting at integer coefficients.
186     */
187    fn try_char_zero_ring_restructure(
188        &self,
189    ) -> Option<impl EqSignature<Set = Self::Set> + CharZeroRingSignature> {
190        Option::<unconstructable_universal_structure::UnconstructableStructure<Self::Set>>::None
191    }
192}
193
194/// A set with a special element `0`.
195#[signature_meta_trait]
196pub trait ZeroSignature: RinglikeSpecializationSignature {
197    fn zero(&self) -> Self::Set;
198}
199
200/// A set with an associative commutative binary operation of addition.
201#[signature_meta_trait]
202pub trait AdditionSignature: RinglikeSpecializationSignature {
203    fn add(&self, a: &Self::Set, b: &Self::Set) -> Self::Set;
204
205    fn add_mut(&self, a: &mut Self::Set, b: &Self::Set) {
206        *a = self.add(a, b);
207    }
208}
209
210/// When `a + x` = `a + y` implies `x` = `y` for all `a`, `x`, `y`.
211#[signature_meta_trait]
212pub trait CancellativeAdditionSignature: AdditionSignature {
213    /// Return the unique `x` such that `a` = `b + x`, or `None` if no such `x` exists.
214    fn try_sub(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set>;
215}
216
217#[signature_meta_trait]
218pub trait TryNegateSignature: ZeroSignature + AdditionSignature {
219    fn try_neg(&self, a: &Self::Set) -> Option<Self::Set>;
220}
221
222#[signature_meta_trait]
223pub trait AdditiveMonoidSignature: ZeroSignature + AdditionSignature + TryNegateSignature {
224    fn sum(&self, vals: Vec<impl Borrow<Self::Set>>) -> Self::Set {
225        let mut sum = self.zero();
226        for val in vals {
227            self.add_mut(&mut sum, val.borrow());
228        }
229        sum
230    }
231}
232
233#[signature_meta_trait]
234pub trait AdditiveGroupSignature: CancellativeAdditionSignature {
235    fn neg(&self, a: &Self::Set) -> Self::Set;
236
237    fn sub(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
238        self.add(a, &self.neg(b))
239    }
240}
241
242#[signature_meta_trait]
243pub trait ZeroEqSignature: ZeroSignature + EqSignature {
244    fn is_zero(&self, a: &Self::Set) -> bool {
245        self.equal(a, &self.zero())
246    }
247}
248impl<R: ZeroSignature + EqSignature> ZeroEqSignature for R {}
249
250/// A set with a special element `1`.
251#[signature_meta_trait]
252pub trait OneSignature: RinglikeSpecializationSignature {
253    fn one(&self) -> Self::Set;
254}
255
256/// A set with an associative binary opperation `*`.
257#[signature_meta_trait]
258pub trait MultiplicationSignature: RinglikeSpecializationSignature {
259    fn mul(&self, a: &Self::Set, b: &Self::Set) -> Self::Set;
260
261    fn mul_mut(&self, a: &mut Self::Set, b: &Self::Set) {
262        *a = self.mul(a, b);
263    }
264}
265
266/// When `*` is commutative.
267#[signature_meta_trait]
268pub trait CommutativeMultiplicationSignature: MultiplicationSignature {}
269
270/// When `1 * a` = `a * 1` = `a` for all `a`.
271#[signature_meta_trait]
272pub trait MultiplicativeMonoidSignature: OneSignature + MultiplicationSignature {
273    fn product(&self, vals: Vec<impl Borrow<Self::Set>>) -> Self::Set {
274        let mut prod = self.one();
275        for val in vals {
276            self.mul_mut(&mut prod, val.borrow());
277        }
278        prod
279    }
280
281    fn nat_pow(&self, a: &Self::Set, n: &Natural) -> Self::Set {
282        if *n == Natural::ZERO {
283            self.one()
284        } else if *n == Natural::ONE {
285            a.clone()
286        } else {
287            debug_assert!(*n >= Natural::TWO);
288            let bits: Vec<_> = n.bits().collect();
289            let mut pows = vec![a.clone()];
290            while pows.len() < bits.len() {
291                pows.push(self.mul(pows.last().unwrap(), pows.last().unwrap()));
292            }
293            let count = bits.len();
294            debug_assert_eq!(count, pows.len());
295            let mut ans = self.one();
296            for i in 0..count {
297                if bits[i] {
298                    self.mul_mut(&mut ans, &pows[i]);
299                }
300            }
301            ans
302        }
303    }
304}
305
306#[signature_meta_trait]
307pub trait TryLeftReciprocalSignature: OneSignature + MultiplicationSignature {
308    /// `x` such that `x*a`=`1` or `None` if no such `x` exists.
309    fn try_left_reciprocal(&self, a: &Self::Set) -> Option<Self::Set>;
310}
311
312#[signature_meta_trait]
313pub trait TryRightReciprocalSignature: OneSignature + MultiplicationSignature {
314    /// `x` such that `a*x`=`1` or `None` if no such `x` exists.
315    fn try_right_reciprocal(&self, a: &Self::Set) -> Option<Self::Set>;
316}
317
318#[signature_meta_trait]
319pub trait TryReciprocalSignature: OneSignature + MultiplicationSignature {
320    /// `b` such that `a*b`=`1` and `b*a`=`1` or `None` if no such `b` exists.
321    fn try_reciprocal(&self, a: &Self::Set) -> Option<Self::Set>;
322
323    fn is_unit(&self, a: &Self::Set) -> bool {
324        self.try_reciprocal(a).is_some()
325    }
326
327    #[skip_meta]
328    fn units(&self) -> MultiplicativeMonoidUnitsStructure<Self, &Self> {
329        MultiplicativeMonoidUnitsStructure::new(self)
330    }
331
332    #[skip_meta]
333    fn into_units(self) -> MultiplicativeMonoidUnitsStructure<Self, Self> {
334        MultiplicativeMonoidUnitsStructure::new(self)
335    }
336}
337
338impl<S: TryReciprocalSignature + CommutativeMultiplicationSignature> TryLeftReciprocalSignature
339    for S
340{
341    fn try_left_reciprocal(&self, a: &Self::Set) -> Option<Self::Set> {
342        self.try_reciprocal(a)
343    }
344}
345
346impl<S: TryReciprocalSignature + CommutativeMultiplicationSignature> TryRightReciprocalSignature
347    for S
348{
349    fn try_right_reciprocal(&self, a: &Self::Set) -> Option<Self::Set> {
350        self.try_reciprocal(a)
351    }
352}
353
354#[signature_meta_trait]
355pub trait MultiplicativeMonoidTryInverseSignature:
356    MultiplicativeMonoidSignature + TryReciprocalSignature
357{
358    fn try_int_pow(&self, a: &Self::Set, n: &Integer) -> Option<Self::Set> {
359        if *n == Integer::ZERO {
360            Some(self.one())
361        } else if *n > Integer::ZERO {
362            Some(self.nat_pow(a, &Abs::abs(n)))
363        } else {
364            Some(self.nat_pow(&self.try_reciprocal(a)?, &Abs::abs(n)))
365        }
366    }
367}
368impl<S: MultiplicativeMonoidSignature + TryReciprocalSignature>
369    MultiplicativeMonoidTryInverseSignature for S
370{
371}
372
373#[signature_meta_trait]
374pub trait MultiplicativeMonoidSquareOpsSignature: MultiplicativeMonoidSignature {
375    fn is_square(&self, a: &Self::Set) -> bool {
376        self.sqrt_if_square(a).is_some()
377    }
378
379    fn sqrt_if_square(&self, a: &Self::Set) -> Option<Self::Set>;
380}
381
382/// 0 is such that `a*0` = `0*a` = `0` for all a in the monoid.
383/// such an element is unqiue if it exists.
384#[signature_meta_trait]
385pub trait MultiplicativeAbsorptionMonoidSignature:
386    MultiplicativeMonoidSignature + ZeroSignature
387{
388}
389
390/// When `a*(b + c) = a*b + a*c`.
391#[signature_meta_trait]
392pub trait LeftDistributiveMultiplicationOverAddition:
393    AdditionSignature + MultiplicationSignature
394{
395}
396
397/// When `(a + b)*c = a*c + b*c`.
398#[signature_meta_trait]
399pub trait RightDistributiveMultiplicationOverAddition:
400    AdditionSignature + MultiplicationSignature
401{
402}
403
404/// When `a * x` = `a * y` implies `x` = `y` for all `a`, `x`, `y`.
405#[signature_meta_trait]
406pub trait LeftCancellativeMultiplicationSignature: MultiplicationSignature {
407    /// Try to find `x` such that `a` = `b * x`.
408    fn try_left_divide(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set>;
409}
410
411/// When `x * a` = `y * a` implies `x` = `y` for all `a`, `x`, `y`.
412#[signature_meta_trait]
413pub trait RightCancellativeMultiplicationSignature: MultiplicationSignature {
414    /// Try to find `x` such that `a` = `x * b`.
415    fn try_right_divide(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set>;
416}
417
418#[signature_meta_trait]
419pub trait CancellativeMultiplicationSignature:
420    CommutativeMultiplicationSignature
421    + LeftCancellativeMultiplicationSignature
422    + RightCancellativeMultiplicationSignature
423{
424    fn try_divide(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set>;
425
426    /// return true iff a is divisible by b
427    fn divisible(&self, a: &Self::Set, b: &Self::Set) -> bool {
428        self.try_divide(a, b).is_some()
429    }
430}
431
432impl<S: CancellativeMultiplicationSignature> LeftCancellativeMultiplicationSignature for S {
433    fn try_left_divide(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
434        self.try_divide(a, b)
435    }
436}
437
438impl<S: CancellativeMultiplicationSignature> RightCancellativeMultiplicationSignature for S {
439    fn try_right_divide(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
440        self.try_divide(a, b)
441    }
442}
443
444#[signature_meta_trait]
445pub trait AreAssociateMultiplicationSignature:
446    CancellativeMultiplicationSignature + ZeroEqSignature
447{
448    fn are_associate(&self, a: &Self::Set, b: &Self::Set) -> bool {
449        if self.equal(a, &self.zero()) && self.equal(b, &self.zero()) {
450            true
451        } else {
452            self.try_divide(a, b).is_some() && self.try_divide(b, a).is_some()
453        }
454    }
455}
456impl<S: CancellativeMultiplicationSignature + ZeroEqSignature> AreAssociateMultiplicationSignature
457    for S
458{
459}
460
461#[signature_meta_trait]
462pub trait MultiplicativeIntegralMonoidSignature:
463    MultiplicativeAbsorptionMonoidSignature
464    + TryLeftReciprocalSignature
465    + TryRightReciprocalSignature
466    + LeftCancellativeMultiplicationSignature
467    + RightCancellativeMultiplicationSignature
468{
469}
470
471// semi-rings need not have cancellative addition
472// but reciprocals are unique when they exist because all reciprocals are two-sided due to commutativity
473#[signature_meta_trait]
474pub trait SemiRingSignature:
475    AdditiveMonoidSignature
476    + TryNegateSignature
477    + MultiplicativeAbsorptionMonoidSignature
478    + CommutativeMultiplicationSignature
479    + LeftDistributiveMultiplicationOverAddition
480    + RightDistributiveMultiplicationOverAddition
481{
482    fn from_nat(&self, x: impl Into<Natural>) -> Self::Set {
483        let x = x.into();
484        if x == Natural::ZERO {
485            self.zero()
486        } else if x == Natural::ONE {
487            self.one()
488        } else {
489            let two = self.add(&self.one(), &self.one());
490            debug_assert!(x >= Natural::TWO);
491            let bits: Vec<bool> = x.bits().collect();
492            let mut ans = self.zero();
493            let mut v = self.one();
494            for b in bits {
495                if b {
496                    self.add_mut(&mut ans, &v);
497                }
498                self.mul_mut(&mut v, &two);
499            }
500            ans
501        }
502    }
503}
504
505#[signature_meta_trait]
506pub trait SemiRingEqSignature: SemiRingSignature + EqSignature {}
507impl<R: SemiRingSignature + EqSignature> SemiRingEqSignature for R {}
508
509#[signature_meta_trait]
510pub trait RingUnitsSignature: RingSignature + TryReciprocalSignature {}
511impl<Ring: RingSignature + TryReciprocalSignature> RingUnitsSignature for Ring {}
512
513#[signature_meta_trait]
514pub trait RingSignature: SemiRingSignature + AdditiveGroupSignature {
515    /// Determine whether the ring is reduced.
516    ///
517    /// Returns `Ok(true)` if the ring is reduced, `Ok(false)` if it is not,
518    /// and `Err` when the implementation cannot decide.
519    fn is_reduced(&self) -> Result<bool, String> {
520        Err("unable to decide whether the ring is reduced".to_string())
521    }
522
523    fn bracket(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
524        self.sub(&self.mul(a, b), &self.mul(b, a))
525    }
526
527    fn from_int(&self, x: impl Into<Integer>) -> Self::Set {
528        let x = x.into();
529        if x < Integer::ZERO {
530            self.neg(&self.from_int(-x))
531        } else {
532            self.from_nat(x.abs())
533        }
534    }
535
536    #[skip_meta]
537    fn inbound_principal_integer_map(&self) -> PrincipalIntegerMap<Self, &Self> {
538        PrincipalIntegerMap::new(self)
539    }
540
541    #[skip_meta]
542    fn into_inbound_principal_integer_map(self) -> PrincipalIntegerMap<Self, Self> {
543        PrincipalIntegerMap::new(self)
544    }
545}
546
547#[signature_meta_trait]
548pub trait RingEqSignature: RingSignature + EqSignature {}
549impl<R: RingSignature + EqSignature> RingEqSignature for R {}
550
551#[signature_meta_trait]
552pub trait IntegralDomainSignature:
553    RingSignature
554    + TryReciprocalSignature
555    + MultiplicativeIntegralMonoidSignature
556    + CancellativeMultiplicationSignature
557    + EqSignature
558{
559    fn try_from_rat(&self, x: &Rational) -> Option<Self::Set> {
560        let n = Fraction::numerator(x);
561        let d = Fraction::denominator(x);
562        debug_assert!(!d.is_zero());
563        self.try_divide(&self.from_int(n), &self.from_nat(d))
564    }
565}
566
567#[signature_meta_trait]
568pub trait FavoriteAssociateSignature: TryReciprocalSignature + EqSignature {
569    //For associate class of elements, choose a unique representative
570    //write self=unit*assoc and return (unit, assoc)
571    //0 is required to return (1, 0)
572    //every unit u is required to return (u, 1) i.e. 1 is the favorite associate of every unit
573    //it seems to happen that the product of favorite associates is another favorite associate. Should this be a requirement?
574
575    fn factor_fav_assoc(&self, a: &Self::Set) -> (Self::Set, Self::Set);
576    fn fav_assoc(&self, a: &Self::Set) -> Self::Set {
577        self.factor_fav_assoc(a).1
578    }
579    fn is_fav_assoc(&self, a: &Self::Set) -> bool {
580        let (_u, b) = self.factor_fav_assoc(a);
581        self.equal(a, &b)
582    }
583}
584
585#[signature_meta_trait]
586pub trait CharacteristicSignature: SemiRingSignature {
587    fn characteristic(&self) -> Natural;
588}
589
590#[signature_meta_trait]
591pub trait OrderedRingSignature: IntegralDomainSignature {
592    // <= satisfying translation invariance and multiplication by positive scalar
593    fn ring_cmp(&self, a: &Self::Set, b: &Self::Set) -> std::cmp::Ordering;
594    fn abs(&self, a: &Self::Set) -> Self::Set {
595        match self.ring_cmp(a, &self.zero()) {
596            std::cmp::Ordering::Less => self.neg(a),
597            std::cmp::Ordering::Equal => self.zero(),
598            std::cmp::Ordering::Greater => a.clone(),
599        }
600    }
601}
602
603#[signature_meta_trait]
604pub trait FiniteUnitsSignature: RingSignature {
605    fn all_units(&self) -> Vec<Self::Set>;
606
607    fn all_units_and_zero(&self) -> Vec<Self::Set> {
608        let mut elems = vec![self.zero()];
609        elems.append(&mut self.all_units());
610        elems
611    }
612}
613
614impl<R: RingSignature + TryReciprocalSignature> FiniteUnitsSignature for R
615where
616    for<'a> MultiplicativeMonoidUnitsStructure<R, &'a R>: FiniteSetSignature<Set = R::Set>,
617{
618    fn all_units(&self) -> Vec<Self::Set> {
619        self.units().list_all_elements()
620    }
621}
622
623#[signature_meta_trait]
624pub trait GreatestCommonDivisorSignature:
625    FavoriteAssociateSignature + IntegralDomainSignature
626{
627    //any gcds should be the standard associate representative
628    //euclidean_gcd can be used to implement this
629    fn gcd(&self, x: &Self::Set, y: &Self::Set) -> Self::Set;
630    fn gcd_list(&self, elems: Vec<impl Borrow<Self::Set>>) -> Self::Set {
631        let mut gcd = self.zero();
632        for x in elems {
633            gcd = self.gcd(&gcd, x.borrow());
634        }
635        gcd
636    }
637    fn lcm(&self, x: &Self::Set, y: &Self::Set) -> Self::Set {
638        if self.is_zero(x) && self.is_zero(y) {
639            self.zero()
640        } else {
641            self.try_divide(&self.mul(x, y), &self.gcd(x, y)).unwrap()
642        }
643    }
644    fn lcm_list(&self, elems: Vec<impl Borrow<Self::Set>>) -> Self::Set {
645        let mut lcm = self.one();
646        for x in elems {
647            lcm = self.lcm(&lcm, x.borrow());
648        }
649        lcm
650    }
651}
652
653#[signature_meta_trait]
654pub trait BezoutDomainSignature: GreatestCommonDivisorSignature {
655    //any gcds should be the standard associate representative
656    fn xgcd(&self, a: &Self::Set, b: &Self::Set) -> (Self::Set, Self::Set, Self::Set); //(g, x, y) s.t. g = ax + by
657    fn xgcd_list(&self, elems: Vec<&Self::Set>) -> (Self::Set, Vec<Self::Set>) {
658        // println!("{:?}", elems);
659        match elems.len() {
660            0 => (self.zero(), vec![]),
661            1 => {
662                let (unit, assoc) = self.factor_fav_assoc(elems[0]);
663                (assoc, vec![self.try_reciprocal(&unit).unwrap()])
664            }
665            2 => {
666                let (g, x, y) = self.xgcd(elems[0], elems[1]);
667                (g, vec![x, y])
668            }
669            n => {
670                let k = n / 2;
671                let (g1, coeffs1) = self.xgcd_list((0..k).map(|i| elems[i]).collect());
672                let (g2, coeffs2) = self.xgcd_list((k..n).map(|i| elems[i]).collect());
673                let (g, x, y) = self.xgcd(&g1, &g2);
674                let mut coeffs = vec![];
675                for c in coeffs1 {
676                    coeffs.push(self.mul(&x, &c));
677                }
678                for c in coeffs2 {
679                    coeffs.push(self.mul(&y, &c));
680                }
681                (g, coeffs)
682            }
683        }
684    }
685}
686
687#[signature_meta_trait]
688pub trait EuclideanDivisionSignature: SemiRingEqSignature {
689    /// None for 0 and Some(norm) for everything else
690    fn norm(&self, elem: &Self::Set) -> Option<Natural>;
691
692    /// None if b is 0 and Some((q, r)) such that a=bq+r and r=0 or norm(r) < norm(b)
693    fn quorem(&self, a: &Self::Set, b: &Self::Set) -> Option<(Self::Set, Self::Set)>;
694
695    fn quo(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
696        self.quorem(a, b).map(|(q, _r)| q)
697    }
698
699    fn rem(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
700        if self.is_zero(b) {
701            a.clone()
702        } else {
703            let (_q, r) = self.quorem(a, b).unwrap();
704            r
705        }
706    }
707
708    fn euclidean_gcd(&self, mut x: Self::Set, mut y: Self::Set) -> Self::Set
709    where
710        Self: FavoriteAssociateSignature,
711    {
712        //Euclidean algorithm
713        while !self.is_zero(&y) {
714            let r = self.rem(&x, &y);
715            (x, y) = (y, r);
716        }
717        let (_unit, assoc) = self.factor_fav_assoc(&x);
718        assoc
719    }
720
721    fn euclidean_xgcd(
722        &self,
723        mut x: Self::Set,
724        mut y: Self::Set,
725    ) -> (Self::Set, Self::Set, Self::Set)
726    where
727        Self: FavoriteAssociateSignature + IntegralDomainSignature,
728    {
729        let orig_x = x.clone();
730        let orig_y = y.clone();
731
732        let mut pa = self.one();
733        let mut a = self.zero();
734        let mut pb = self.zero();
735        let mut b = self.one();
736
737        while !self.is_zero(&y) {
738            let (q, r) = self.quorem(&x, &y).unwrap();
739            let new_a = self.add(&pa, &self.neg(&self.mul(&q, &a)));
740            (a, pa) = (new_a, a);
741            let new_b = self.add(&pb, &self.neg(&self.mul(&q, &b)));
742            (b, pb) = (new_b, b);
743            (x, y) = (y, r);
744        }
745        let (unit, ass_x) = self.factor_fav_assoc(&x);
746        // g = u*g_ass
747        // g = xa+by
748        // xa+by=u*g_ass
749        debug_assert!(self.is_unit(&unit));
750        let (g, a, b) = (
751            ass_x,
752            self.try_divide(&pa, &unit).unwrap(),
753            self.try_divide(&pb, &unit).unwrap(),
754        );
755        // println!("{:?} = {:?} * {:?} + {:?} * {:?}", g, a, orig_x, b, orig_y);
756        debug_assert!(self.equal(
757            &self.add(&self.mul(&a, &orig_x), &self.mul(&b, &orig_y)),
758            &g
759        ));
760        debug_assert!(self.equal(&g, &self.euclidean_gcd(orig_x, orig_y)));
761        (g, a, b)
762    }
763}
764
765#[signature_meta_trait]
766pub trait EuclideanDomainSignature: EuclideanDivisionSignature + IntegralDomainSignature {}
767impl<Ring: EuclideanDivisionSignature + IntegralDomainSignature> EuclideanDomainSignature for Ring {}
768
769#[signature_meta_trait]
770pub trait InfiniteSignature: RinglikeSpecializationSignature {
771    fn generate_distinct_elements(&self) -> Box<dyn Iterator<Item = Self::Set>>;
772}
773
774#[signature_meta_trait]
775pub trait FieldSignature: IntegralDomainSignature {
776    fn from_rat(&self, x: &Rational) -> Self::Set {
777        self.try_from_rat(x).unwrap()
778    }
779}
780
781impl<FS: FieldSignature> FavoriteAssociateSignature for FS {
782    fn factor_fav_assoc(&self, a: &Self::Set) -> (Self::Set, Self::Set) {
783        if self.is_zero(a) {
784            (self.one(), self.zero())
785        } else {
786            (a.clone(), self.one())
787        }
788    }
789}
790
791impl<FS: FieldSignature> EuclideanDivisionSignature for FS {
792    fn norm(&self, elem: &Self::Set) -> Option<Natural> {
793        if self.is_zero(elem) {
794            None
795        } else {
796            Some(Natural::from(1u8))
797        }
798    }
799
800    fn quorem(&self, a: &Self::Set, b: &Self::Set) -> Option<(Self::Set, Self::Set)> {
801        if self.is_zero(b) {
802            None
803        } else {
804            Some((self.try_divide(a, b).unwrap(), self.zero()))
805        }
806    }
807}
808
809impl<FS: FieldSignature> GreatestCommonDivisorSignature for FS {
810    fn gcd(&self, x: &Self::Set, y: &Self::Set) -> Self::Set {
811        self.euclidean_gcd(x.clone(), y.clone())
812    }
813}
814
815impl<FS: FieldSignature> BezoutDomainSignature for FS {
816    fn xgcd(&self, x: &Self::Set, y: &Self::Set) -> (Self::Set, Self::Set, Self::Set) {
817        self.euclidean_xgcd(x.clone(), y.clone())
818    }
819}
820
821/// When `.characteristic()` always returns 0
822#[signature_meta_trait]
823pub trait CharZeroRingSignature: RingSignature + CharacteristicSignature {
824    fn try_to_int(&self, x: &Self::Set) -> Option<Integer>;
825}
826
827impl<RS: CharZeroRingSignature + 'static> InfiniteSignature for RS {
828    fn generate_distinct_elements(&self) -> Box<dyn Iterator<Item = <Self as SetSignature>::Set>> {
829        struct IntegerIterator<RS: CharZeroRingSignature> {
830            ring: RS,
831            next: Integer,
832        }
833
834        impl<RS: CharZeroRingSignature> Iterator for IntegerIterator<RS> {
835            type Item = RS::Set;
836
837            fn next(&mut self) -> Option<Self::Item> {
838                let next = self.next.clone();
839                if Integer::ZERO < next {
840                    self.next = -self.next.clone();
841                } else {
842                    self.next = Integer::from(1) - self.next.clone();
843                }
844                Some(self.ring.from_int(next))
845            }
846        }
847
848        Box::new(IntegerIterator {
849            ring: self.clone(),
850            next: Integer::from(0),
851        })
852    }
853}
854
855#[signature_meta_trait]
856pub trait CharZeroFieldSignature: FieldSignature + CharZeroRingSignature {
857    fn try_to_rat(&self, x: &Self::Set) -> Option<Rational>;
858
859    #[skip_meta]
860    fn inbound_principal_rational_map(&self) -> PrincipalRationalMap<Self, &Self> {
861        PrincipalRationalMap::new(self)
862    }
863    #[skip_meta]
864    fn into_inbound_principal_rational_map(self) -> PrincipalRationalMap<Self, Self> {
865        PrincipalRationalMap::new(self)
866    }
867}
868
869#[signature_meta_trait]
870pub trait FiniteFieldSignature: FieldSignature + FiniteUnitsSignature + FiniteSetSignature {
871    // Return (p, k) where p is a prime and |F| = p^k
872    fn characteristic_and_power(&self) -> (Natural, Natural);
873}
874
875//is a subset of the complex numbers
876#[signature_meta_trait]
877pub trait ComplexSubsetSignature: RinglikeSpecializationSignature {
878    fn as_f32_real_and_imaginary_parts(&self, z: &Self::Set) -> (f32, f32);
879    fn as_f64_real_and_imaginary_parts(&self, z: &Self::Set) -> (f64, f64);
880}
881
882//is a subset of the real numbers
883#[signature_meta_trait]
884pub trait RealSubsetSignature: ComplexSubsetSignature {
885    fn as_f64(&self, x: &Self::Set) -> f64 {
886        let (r, i) = self.as_f64_real_and_imaginary_parts(x);
887        debug_assert_eq!(i, 0.0);
888        r
889    }
890    fn as_f32(&self, x: &Self::Set) -> f32 {
891        let (r, i) = self.as_f32_real_and_imaginary_parts(x);
892        debug_assert_eq!(i, 0.0);
893        r
894    }
895}
896
897#[signature_meta_trait]
898pub trait RealRoundingSignature: RealSubsetSignature {
899    fn floor(&self, x: &Self::Set) -> Integer; //round down
900    fn ceil(&self, x: &Self::Set) -> Integer; //round up
901    fn round(&self, x: &Self::Set) -> Integer; //round closets, either direction is fine if mid way
902}
903
904#[signature_meta_trait]
905pub trait RealFromFloatSignature: RealSubsetSignature {
906    fn from_f64_approx(&self, x: f64) -> Self::Set;
907    fn from_f32_approx(&self, x: f32) -> Self::Set {
908        self.from_f64_approx(f64::from(x))
909    }
910}
911
912#[signature_meta_trait]
913pub trait ComplexConjugateSignature: RinglikeSpecializationSignature {
914    fn conjugate(&self, x: &Self::Set) -> Self::Set;
915}
916
917impl<RS: RealSubsetSignature> ComplexConjugateSignature for RS {
918    fn conjugate(&self, x: &Self::Set) -> Self::Set {
919        x.clone()
920    }
921}
922
923#[signature_meta_trait]
924pub trait PositiveRealNthRootSignature: ComplexSubsetSignature {
925    //if x is a non-negative real number, return the nth root of x
926    //may also return Ok for other well-defined values such as for 1st root of any x and 0th root of any non-zero x, but is not required to
927    fn nth_root(&self, x: &Self::Set, n: usize) -> Result<Self::Set, ()>;
928    fn square_root(&self, x: &Self::Set) -> Result<Self::Set, ()> {
929        self.nth_root(x, 2)
930    }
931    fn cube_root(&self, x: &Self::Set) -> Result<Self::Set, ()> {
932        self.nth_root(x, 3)
933    }
934}
935
936// TODO: Move this sort of struture to the field inclusion homomorphism
937#[signature_meta_trait]
938pub trait AlgebraicClosureSignature: FieldSignature
939where
940    //TODO: can this allow polynomial structures taking a reference to the base field rather than an instance?
941    PolynomialStructure<Self::BFS, Self::BFS>: FactoringMonoidSignature<FactoredExponent = NaturalCanonicalStructure>
942        + SetSignature<Set = Polynomial<<Self::BFS as SetSignature>::Set>>,
943{
944    type BFS: FieldSignature; //base field structure
945
946    fn base_field(&self) -> Self::BFS;
947
948    fn base_field_inclusion(&self, x: &<Self::BFS as SetSignature>::Set) -> Self::Set;
949
950    //return None for the zero polynomial
951    fn all_roots_list(
952        &self,
953        poly: &Polynomial<<Self::BFS as SetSignature>::Set>,
954    ) -> Option<Vec<Self::Set>>;
955
956    fn all_roots_unique(
957        &self,
958        poly: &Polynomial<<Self::BFS as SetSignature>::Set>,
959    ) -> Option<Vec<Self::Set>> {
960        let base_field_poly = self.base_field().into_polynomials();
961        self.all_roots_list(
962            &base_field_poly
963                .factorizations()
964                .expand_squarefree(&base_field_poly.factor(poly)),
965        )
966    }
967
968    fn all_roots_powers(
969        &self,
970        poly: &Polynomial<<Self::BFS as SetSignature>::Set>,
971    ) -> Option<Vec<(Self::Set, usize)>> {
972        let mut root_powers = vec![];
973        let base_field_poly = self.base_field().into_polynomials();
974        for (factor, k) in base_field_poly.factor(poly).into_powers()? {
975            for root in self.all_roots_list(&factor).unwrap() {
976                root_powers.push((root, (&k).try_into().unwrap()));
977            }
978        }
979        Some(root_powers)
980    }
981}
982
983/// The free ring of rank 0 is the integers
984/// The free ring of rank 1 is the polynomial ring over the integers
985/// The free ring of rank n is the multipolynomial ring over the integers
986#[signature_meta_trait]
987pub trait FreeRingSignature: RingSignature {
988    type Generator: Clone + Debug + PartialEq + Eq + std::hash::Hash + Send + Sync;
989
990    fn free_generators(&self) -> std::collections::HashSet<Self::Generator>;
991    fn free_rank(&self) -> usize {
992        self.free_generators().len()
993    }
994}
algebraeon_rings/structure/rings.rs

algebraeon_rings/structure/
rings.rs
