algebraeon_rings/algebraic_number_field/generic/
order.rs

1use crate::{
2    algebraic_number_field::{
3        AlgebraicIntegerRingSignature, AlgebraicNumberFieldSignature, FullRankSublatticeWithBasis,
4        FullRankSublatticeWithBasisSignature, OrderIdeal,
5    },
6    matrix::{Matrix, SymmetricMatrix},
7    module::{
8        finitely_free_module::RingToFinitelyFreeModuleSignature,
9        finitely_free_submodule::FinitelyFreeSubmodule,
10    },
11    structure::{
12        AdditionSignature, AdditiveGroupSignature, AdditiveMonoidSignature,
13        CancellativeAdditionSignature, CancellativeMultiplicationSignature, CharZeroRingSignature,
14        CharacteristicSignature, CommutativeMultiplicationSignature, DedekindDomainSignature,
15        FinitelyFreeModuleSignature, IntegralDomainSignature,
16        LeftDistributiveMultiplicationOverAddition, MultiplicationSignature,
17        MultiplicativeAbsorptionMonoidSignature, MultiplicativeIntegralMonoidSignature,
18        MultiplicativeMonoidSignature, OneSignature, RightDistributiveMultiplicationOverAddition,
19        RingSignature, RingToIdealsSignature, RinglikeSpecializationSignature, SemiModuleSignature,
20        SemiRingSignature, TryNegateSignature, TryReciprocalSignature, ZeroEqSignature,
21        ZeroSignature,
22    },
23};
24use algebraeon_nzq::{Integer, Natural};
25use algebraeon_sets::structure::{
26    BorrowedStructure, EqSignature, Function, InjectiveFunction, MetaType, SetSignature, Signature,
27    ToStringSignature,
28};
29
30pub type RingOfIntegersWithIntegralBasis<K, KB> = OrderWithBasis<K, KB, true>;
31
32#[derive(Debug, Clone)]
33pub struct OrderWithBasis<
34    K: AlgebraicNumberFieldSignature,
35    KB: BorrowedStructure<K>,
36    const MAXIMAL: bool,
37> {
38    full_rank_z_sublattice: FullRankSublatticeWithBasis<K, KB>,
39    products: SymmetricMatrix<Vec<Integer>>,
40    one: Vec<Integer>,
41}
42
43impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
44    OrderWithBasis<K, KB, MAXIMAL>
45{
46    fn check_is_order(&self) -> Result<(), String> {
47        for b in self.full_rank_z_sublattice.basis() {
48            if !self.full_rank_z_sublattice.anf().is_algebraic_integer(b) {
49                return Err("Basis vectors must be algebraic integers for an order".to_string());
50            }
51        }
52        Ok(())
53    }
54
55    fn new_impl(anf: KB, basis: Vec<K::Set>) -> Result<Self, String> {
56        let n = anf.borrow().n();
57        let products = SymmetricMatrix::construct_bottom_left(n, |r, c| {
58            anf.borrow().mul(&basis[r], &basis[c])
59        });
60        let full_rank_z_sublattice = FullRankSublatticeWithBasis::new_unchecked(anf, basis);
61
62        let products = products.map(|p| {
63            full_rank_z_sublattice
64                .outbound_order_to_anf_inclusion()
65                .try_preimage(&p)
66        });
67        let products = products.unwrap_entries();
68        if products.is_none() {
69            return Err("An order must be closed under multiplication".to_string());
70        }
71        let products = products.unwrap();
72
73        let one = full_rank_z_sublattice
74            .outbound_order_to_anf_inclusion()
75            .try_preimage(&full_rank_z_sublattice.anf().one());
76        if one.is_none() {
77            return Err("An order must contain 1".to_string());
78        }
79        let one = one.unwrap();
80        let s = Self {
81            full_rank_z_sublattice,
82            products,
83            one,
84        };
85        Ok(s)
86    }
87
88    /// The conductor of an order is the ideal of the order consisting of all elements such that multiplying by any element of the ring of integers produces an element of the order.
89    pub fn conductor(&self) -> OrderIdeal {
90        self.anf()
91            .ring_of_integers()
92            .suborder_conductor_as_ideal_of_order(self)
93    }
94}
95
96impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>> OrderWithBasis<K, KB, false> {
97    pub fn new(anf: KB, basis: Vec<K::Set>) -> Result<Self, String> {
98        let s = Self::new_impl(anf, basis)?;
99        s.check_is_order()?;
100        Ok(s)
101    }
102
103    pub fn new_unchecked(anf: KB, basis: Vec<K::Set>) -> Self {
104        let s = Self::new_impl(anf, basis).unwrap();
105        #[cfg(debug_assertions)]
106        s.check_is_order().unwrap();
107        s
108    }
109}
110
111impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>> OrderWithBasis<K, KB, true> {
112    fn check_is_maximal(&self) -> Result<(), String> {
113        let self_disc = self.discriminant();
114        let anf_disc = FullRankSublatticeWithBasisSignature::<K>::anf(self).discriminant();
115        if self_disc != anf_disc {
116            debug_assert!(self_disc > anf_disc);
117            return Err("Not maximal".to_string());
118        }
119        Ok(())
120    }
121
122    pub fn new_maximal(anf: KB, basis: Vec<K::Set>) -> Result<Self, String> {
123        let s = Self::new_impl(anf, basis)?;
124        s.check_is_order()?;
125        s.check_is_maximal()?;
126        Ok(s)
127    }
128
129    pub fn new_maximal_unchecked(anf: KB, basis: Vec<K::Set>) -> Self {
130        let s = Self::new_impl(anf, basis).unwrap();
131        #[cfg(debug_assertions)]
132        s.check_is_order().unwrap();
133        s.check_is_maximal().unwrap();
134        s
135    }
136}
137
138impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool> PartialEq
139    for OrderWithBasis<K, KB, MAXIMAL>
140{
141    fn eq(&self, other: &Self) -> bool {
142        self.full_rank_z_sublattice == other.full_rank_z_sublattice
143    }
144}
145
146impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool> Eq
147    for OrderWithBasis<K, KB, MAXIMAL>
148{
149}
150
151impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool> Signature
152    for OrderWithBasis<K, KB, MAXIMAL>
153{
154}
155
156impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool> SetSignature
157    for OrderWithBasis<K, KB, MAXIMAL>
158{
159    type Set = Vec<Integer>;
160
161    fn is_element(&self, x: &Self::Set) -> Result<(), String> {
162        self.full_rank_z_sublattice.is_element(x)
163    }
164}
165
166impl<
167    K: AlgebraicNumberFieldSignature + ToStringSignature,
168    KB: BorrowedStructure<K>,
169    const MAXIMAL: bool,
170> ToStringSignature for OrderWithBasis<K, KB, MAXIMAL>
171{
172    fn to_string(&self, elem: &Self::Set) -> String {
173        self.full_rank_z_sublattice.to_string(elem)
174    }
175}
176
177impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool> EqSignature
178    for OrderWithBasis<K, KB, MAXIMAL>
179{
180    fn equal(&self, a: &Self::Set, b: &Self::Set) -> bool {
181        self.full_rank_z_sublattice.equal(a, b)
182    }
183}
184
185impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
186    RinglikeSpecializationSignature for OrderWithBasis<K, KB, MAXIMAL>
187{
188    fn try_ring_restructure(&self) -> Option<impl EqSignature<Set = Self::Set> + RingSignature> {
189        Some(self.clone())
190    }
191
192    fn try_char_zero_ring_restructure(
193        &self,
194    ) -> Option<impl EqSignature<Set = Self::Set> + CharZeroRingSignature> {
195        Some(self.clone())
196    }
197}
198
199impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool> ZeroSignature
200    for OrderWithBasis<K, KB, MAXIMAL>
201{
202    fn zero(&self) -> Self::Set {
203        self.full_rank_z_sublattice.zero()
204    }
205}
206
207impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
208    AdditionSignature for OrderWithBasis<K, KB, MAXIMAL>
209{
210    fn add(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
211        self.full_rank_z_sublattice.add(a, b)
212    }
213}
214
215impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
216    CancellativeAdditionSignature for OrderWithBasis<K, KB, MAXIMAL>
217{
218    fn try_sub(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
219        Some(self.sub(a, b))
220    }
221}
222
223impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
224    TryNegateSignature for OrderWithBasis<K, KB, MAXIMAL>
225{
226    fn try_neg(&self, a: &Self::Set) -> Option<Self::Set> {
227        Some(self.neg(a))
228    }
229}
230
231impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
232    AdditiveMonoidSignature for OrderWithBasis<K, KB, MAXIMAL>
233{
234}
235
236impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
237    AdditiveGroupSignature for OrderWithBasis<K, KB, MAXIMAL>
238{
239    fn neg(&self, a: &Self::Set) -> Self::Set {
240        self.full_rank_z_sublattice.neg(a)
241    }
242
243    fn sub(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
244        self.full_rank_z_sublattice.sub(a, b)
245    }
246}
247
248impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
249    FullRankSublatticeWithBasisSignature<K> for OrderWithBasis<K, KB, MAXIMAL>
250{
251    fn anf(&self) -> &K {
252        self.full_rank_z_sublattice.anf()
253    }
254
255    fn basis(&self) -> &Vec<<K>::Set> {
256        self.full_rank_z_sublattice.basis()
257    }
258}
259
260impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool> OneSignature
261    for OrderWithBasis<K, KB, MAXIMAL>
262{
263    fn one(&self) -> Self::Set {
264        self.one.clone()
265    }
266}
267
268impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
269    MultiplicationSignature for OrderWithBasis<K, KB, MAXIMAL>
270{
271    fn mul(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
272        let n = self.n();
273        debug_assert!(self.is_element(a).is_ok());
274        debug_assert!(self.is_element(b).is_ok());
275        let mut t = self.zero();
276        #[allow(clippy::needless_range_loop)]
277        for i in 0..n {
278            for j in 0..n {
279                self.add_mut(
280                    &mut t,
281                    &self
282                        .free_lattice_restructure()
283                        .scalar_mul(self.products.get(i, j).unwrap(), &(&a[i] * &b[j])),
284                );
285            }
286        }
287        debug_assert!(
288            self.equal(
289                &self
290                    .outbound_order_to_anf_inclusion()
291                    .try_preimage(&self.anf().mul(
292                        &self.outbound_order_to_anf_inclusion().image(a),
293                        &self.outbound_order_to_anf_inclusion().image(b)
294                    ))
295                    .unwrap(),
296                &t
297            )
298        );
299        t
300    }
301}
302
303impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
304    CommutativeMultiplicationSignature for OrderWithBasis<K, KB, MAXIMAL>
305{
306}
307
308impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
309    MultiplicativeMonoidSignature for OrderWithBasis<K, KB, MAXIMAL>
310{
311}
312
313impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
314    MultiplicativeAbsorptionMonoidSignature for OrderWithBasis<K, KB, MAXIMAL>
315{
316}
317
318impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
319    LeftDistributiveMultiplicationOverAddition for OrderWithBasis<K, KB, MAXIMAL>
320{
321}
322
323impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
324    RightDistributiveMultiplicationOverAddition for OrderWithBasis<K, KB, MAXIMAL>
325{
326}
327
328impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
329    SemiRingSignature for OrderWithBasis<K, KB, MAXIMAL>
330{
331}
332
333impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
334    OrderWithBasis<K, KB, MAXIMAL>
335{
336    pub fn quotient_sublattice(
337        &self,
338        a: &FinitelyFreeSubmodule<Integer>,
339        b: &FinitelyFreeSubmodule<Integer>,
340    ) -> FinitelyFreeSubmodule<Integer> {
341        #[cfg(debug_assertions)]
342        {
343            self.free_lattice_restructure()
344                .submodules()
345                .is_element(a)
346                .unwrap();
347            self.free_lattice_restructure()
348                .submodules()
349                .is_element(b)
350                .unwrap();
351        }
352
353        /*
354        We want the ideal of all points x in the ring R such that xj belongs to I for all j in J.
355        It's sufficient to check on a basis of points j in J.
356        For each j in a basis for J we find the space of points x such that xj belongs to I and take their intersection.
357         */
358
359        let n = self.n();
360        let module = self.free_lattice_restructure();
361        let sublattices = module.submodules();
362
363        sublattices.intersect_list(
364            b.basis()
365                .into_iter()
366                .map(|bv| {
367                    // column matrix for multiplication by jb wrt the integer basis for the ring
368                    let bv_mulmat = Matrix::join_cols(
369                        n,
370                        (0..n)
371                            .map(|c| {
372                                Matrix::<Integer>::from_col(self.mul(&bv, &module.basis_element(c)))
373                            })
374                            .collect(),
375                    );
376                    bv_mulmat.col_preimage(a)
377                })
378                .collect(),
379        )
380    }
381}
382
383impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool> RingSignature
384    for OrderWithBasis<K, KB, MAXIMAL>
385{
386    fn is_reduced(&self) -> Result<bool, String> {
387        Ok(true)
388    }
389}
390
391impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
392    CharacteristicSignature for OrderWithBasis<K, KB, MAXIMAL>
393{
394    fn characteristic(&self) -> Natural {
395        Natural::ZERO
396    }
397}
398
399impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
400    TryReciprocalSignature for OrderWithBasis<K, KB, MAXIMAL>
401{
402    fn try_reciprocal(&self, a: &Self::Set) -> Option<Self::Set> {
403        if self.is_zero(a) {
404            None
405        } else {
406            self.outbound_order_to_anf_inclusion().try_preimage(
407                &self
408                    .anf()
409                    .try_reciprocal(&self.outbound_order_to_anf_inclusion().image(a))
410                    .unwrap(),
411            )
412        }
413    }
414}
415
416impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
417    CancellativeMultiplicationSignature for OrderWithBasis<K, KB, MAXIMAL>
418{
419    fn try_divide(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
420        Some(self.mul(a, &self.try_reciprocal(b)?))
421    }
422}
423
424impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
425    MultiplicativeIntegralMonoidSignature for OrderWithBasis<K, KB, MAXIMAL>
426{
427}
428
429impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
430    IntegralDomainSignature for OrderWithBasis<K, KB, MAXIMAL>
431{
432}
433
434impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>, const MAXIMAL: bool>
435    CharZeroRingSignature for OrderWithBasis<K, KB, MAXIMAL>
436{
437    fn try_to_int(&self, x: &Self::Set) -> Option<Integer> {
438        self.anf()
439            .try_to_int(&self.outbound_order_to_anf_inclusion().image(x))
440    }
441}
442
443impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>> DedekindDomainSignature
444    for OrderWithBasis<K, KB, true>
445{
446}
447
448impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>> AlgebraicIntegerRingSignature<K>
449    for OrderWithBasis<K, KB, true>
450{
451    fn anf(&self) -> &K {
452        self.full_rank_z_sublattice.anf()
453    }
454
455    fn to_anf(&self, x: &Self::Set) -> K::Set {
456        self.outbound_order_to_anf_inclusion().image(x)
457    }
458
459    fn try_from_anf(&self, y: &K::Set) -> Option<Self::Set> {
460        self.outbound_order_to_anf_inclusion().try_preimage(y)
461    }
462
463    fn integral_basis(&self) -> Vec<Self::Set> {
464        self.free_lattice_restructure().basis_vecs()
465    }
466}
467
468impl<K: AlgebraicNumberFieldSignature, KB: BorrowedStructure<K>> OrderWithBasis<K, KB, true> {
469    pub fn suborder_conductor_as_ideal_of_order<KOB: BorrowedStructure<K>, const MAXIMAL: bool>(
470        &self,
471        order: &OrderWithBasis<K, KOB, MAXIMAL>,
472    ) -> OrderIdeal {
473        let anf = order.anf();
474        debug_assert_eq!(FullRankSublatticeWithBasisSignature::anf(self), anf);
475        debug_assert_eq!(AlgebraicIntegerRingSignature::anf(self), anf);
476
477        let order_to_maximal_order = self
478            .inbound_sublattice_inclusion_unchecked::<OrderWithBasis<K, KOB, MAXIMAL>, _>(order);
479
480        let ideal = order
481            .ideals()
482            .outbound_sublattices_inclusion()
483            .try_preimage(
484                &order_to_maximal_order
485                    .sublattices_inclusion()
486                    .try_preimage(
487                        &self.quotient_sublattice(
488                            &order_to_maximal_order.sublattices_inclusion().image(
489                                &Integer::structure()
490                                    .free_module(anf.n())
491                                    .submodules()
492                                    .full_submodule(),
493                            ),
494                            &Integer::structure()
495                                .free_module(anf.n())
496                                .submodules()
497                                .full_submodule(),
498                        ),
499                    )
500                    .unwrap(),
501            )
502            .unwrap();
503
504        #[cfg(debug_assertions)]
505        order.ideals().is_element(&ideal).unwrap();
506
507        ideal
508    }
509
510    pub fn suborder_conductor_as_ideal_of_self<KOB: BorrowedStructure<K>, const MAXIMAL: bool>(
511        &self,
512        order: &OrderWithBasis<K, KOB, MAXIMAL>,
513    ) -> OrderIdeal {
514        let anf = order.anf();
515        debug_assert_eq!(FullRankSublatticeWithBasisSignature::anf(self), anf);
516        debug_assert_eq!(AlgebraicIntegerRingSignature::anf(self), anf);
517
518        let order_to_maximal_order = self
519            .inbound_sublattice_inclusion_unchecked::<OrderWithBasis<K, KOB, MAXIMAL>, _>(order);
520
521        let ideal = self
522            .ideals()
523            .outbound_sublattices_inclusion()
524            .try_preimage(
525                &self.quotient_sublattice(
526                    &order_to_maximal_order.sublattices_inclusion().image(
527                        &Integer::structure()
528                            .free_module(anf.n())
529                            .submodules()
530                            .full_submodule(),
531                    ),
532                    &Integer::structure()
533                        .free_module(anf.n())
534                        .submodules()
535                        .full_submodule(),
536                ),
537            )
538            .unwrap();
539
540        #[cfg(debug_assertions)]
541        self.ideals().is_element(&ideal).unwrap();
542
543        ideal
544    }
545}
546
547// mod anf_inclusion {
548//     use super::*;
549//     use crate::structure::RingHomomorphism;
550
551//     #[derive(Debug, Clone)]
552//     pub struct AlgebraicNumberFieldOrderWithBasisInclusion<
553//         K: AlgebraicNumberFieldSignature,
554//         KB: BorrowedStructure<K>,
555//         const MAXIMAL: bool,
556//         OB: BorrowedStructure<OrderWithBasis<K, KB, MAXIMAL>>,
557//     > {
558//         _k: PhantomData<K>,
559//         _kb: PhantomData<KB>,
560//         order: OB,
561//     }
562
563//     impl<
564//         K: AlgebraicNumberFieldSignature,
565//         KB: BorrowedStructure<K>,
566//         const MAXIMAL: bool,
567//         OB: BorrowedStructure<OrderWithBasis<K, KB, MAXIMAL>>,
568//     > AlgebraicNumberFieldOrderWithBasisInclusion<K, KB, MAXIMAL, OB>
569//     {
570//         pub fn new(order: OB) -> Self {
571//             Self {
572//                 _k: PhantomData,
573//                 _kb: PhantomData,
574//                 order,
575//             }
576//         }
577
578//         pub fn order(&self) -> &OrderWithBasis<K, KB, MAXIMAL> {
579//             self.order.borrow()
580//         }
581//     }
582
583//     impl<
584//         K: AlgebraicNumberFieldSignature,
585//         KB: BorrowedStructure<K>,
586//         const MAXIMAL: bool,
587//         OB: BorrowedStructure<OrderWithBasis<K, KB, MAXIMAL>>,
588//     > Morphism<OrderWithBasis<K, KB, MAXIMAL>, K>
589//         for AlgebraicNumberFieldOrderWithBasisInclusion<K, KB, MAXIMAL, OB>
590//     {
591//         fn domain(&self) -> &OrderWithBasis<K, KB, MAXIMAL> {
592//             self.order()
593//         }
594
595//         fn range(&self) -> &K {
596//             self.order().anf()
597//         }
598//     }
599
600//     impl<
601//         K: AlgebraicNumberFieldSignature,
602//         KB: BorrowedStructure<K>,
603//         const MAXIMAL: bool,
604//         OB: BorrowedStructure<OrderWithBasis<K, KB, MAXIMAL>>,
605//     > Function<OrderWithBasis<K, KB, MAXIMAL>, K>
606//         for AlgebraicNumberFieldOrderWithBasisInclusion<K, KB, MAXIMAL, OB>
607//     {
608//         fn image(&self, x: &Vec<Integer>) -> <K as SetSignature>::Set {
609//             self.order()
610//                 .full_rank_z_sublattice
611//                 .outbound_order_to_anf_inclusion()
612//                 .image(x)
613//         }
614//     }
615
616//     impl<
617//         K: AlgebraicNumberFieldSignature,
618//         KB: BorrowedStructure<K>,
619//         const MAXIMAL: bool,
620//         OB: BorrowedStructure<OrderWithBasis<K, KB, MAXIMAL>>,
621//     > InjectiveFunction<OrderWithBasis<K, KB, MAXIMAL>, K>
622//         for AlgebraicNumberFieldOrderWithBasisInclusion<K, KB, MAXIMAL, OB>
623//     {
624//         fn try_preimage(&self, y: &<K as SetSignature>::Set) -> Option<Vec<Integer>> {
625//             self.order()
626//                 .full_rank_z_sublattice
627//                 .outbound_order_to_anf_inclusion()
628//                 .try_preimage(y)
629//         }
630//     }
631
632//     impl<
633//         K: AlgebraicNumberFieldSignature,
634//         KB: BorrowedStructure<K>,
635//         const MAXIMAL: bool,
636//         OB: BorrowedStructure<OrderWithBasis<K, KB, MAXIMAL>>,
637//     > RingHomomorphism<OrderWithBasis<K, KB, MAXIMAL>, K>
638//         for AlgebraicNumberFieldOrderWithBasisInclusion<K, KB, MAXIMAL, OB>
639//     {
640//     }
641// }
642
643#[cfg(test)]
644mod tests {
645    use super::*;
646    use crate::{
647        parsing::parse_rational_polynomial,
648        polynomial::Polynomial,
649        structure::{IdealsArithmeticSignature, IntoErgonomic, RingToIdealsSignature},
650    };
651    use algebraeon_nzq::Rational;
652
653    #[test]
654    fn ring_of_integer_arithmetic() {
655        let x = Polynomial::<Rational>::var().into_ergonomic();
656
657        // Take the integral basis (0 + x, 1/2 + 1/2x)
658        let a = Polynomial::<Rational>::from_coeffs(vec![Rational::ZERO, Rational::ONE]);
659        let b = Polynomial::<Rational>::from_coeffs(vec![Rational::ONE_HALF, Rational::ONE_HALF]);
660
661        let anf = (x.pow(2) + 7)
662            .into_verbose()
663            .algebraic_number_field()
664            .unwrap();
665        let roi =
666            RingOfIntegersWithIntegralBasis::new_maximal(anf, vec![a.clone(), b.clone()]).unwrap();
667
668        {
669            assert_eq!(
670                roi.outbound_order_to_anf_inclusion()
671                    .image(&vec![Integer::from(1), Integer::from(4)]),
672                (2 + 3 * &x).into_verbose()
673            );
674        }
675
676        {
677            assert!(
678                roi.outbound_order_to_anf_inclusion()
679                    .try_preimage(&Polynomial::<Rational>::from_coeffs(vec![
680                        Rational::ONE_HALF,
681                        Rational::ONE,
682                    ]))
683                    .is_none()
684            );
685
686            let c = roi
687                .outbound_order_to_anf_inclusion()
688                .try_preimage(&Polynomial::<Rational>::from_coeffs(vec![
689                    Rational::from(2),
690                    Rational::from(3),
691                ]))
692                .unwrap();
693            assert_eq!(c.len(), 2);
694            assert_eq!(c[0], Integer::from(1));
695            assert_eq!(c[1], Integer::from(4));
696        }
697
698        {
699            // 0 = 0 * (0+x) + 0 * (1/2 + 1/2x)
700            let zero = roi.zero();
701            assert_eq!(zero.len(), 2);
702            assert_eq!(zero[0], Integer::ZERO);
703            assert_eq!(zero[1], Integer::ZERO);
704        }
705
706        {
707            // 1 = -1 * (0+x) + 2 * (1/2 + 1/2x)
708            let one = roi.one();
709            assert_eq!(one.len(), 2);
710            assert_eq!(one[0], Integer::from(-1));
711            assert_eq!(one[1], Integer::from(2));
712        }
713
714        {
715            let alpha = roi
716                .outbound_order_to_anf_inclusion()
717                .try_preimage(&(2 + 3 * &x).into_verbose())
718                .unwrap();
719            let beta = roi
720                .outbound_order_to_anf_inclusion()
721                .try_preimage(&(-1 + 2 * &x).into_verbose())
722                .unwrap();
723
724            {
725                let gamma = roi
726                    .outbound_order_to_anf_inclusion()
727                    .try_preimage(&(1 + 5 * &x).into_verbose())
728                    .unwrap();
729                // (2 + 3x) + (-1 + 2x) = 1 + 5x
730                assert_eq!(roi.add(&alpha, &beta), gamma);
731            }
732
733            {
734                let gamma = roi
735                    .outbound_order_to_anf_inclusion()
736                    .try_preimage(&(-44 + &x).into_verbose())
737                    .unwrap();
738                // x^2 = -7 so
739                // (2 + 3x) * (-1 + 2x) = -44 + x
740                assert_eq!(roi.mul(&alpha, &beta), gamma);
741            }
742
743            {
744                let gamma = roi
745                    .outbound_order_to_anf_inclusion()
746                    .try_preimage(&(-2 - 3 * &x).into_verbose())
747                    .unwrap();
748                // -(2 + 3x) = -2 - 3x
749                assert_eq!(roi.neg(&alpha), gamma);
750            }
751
752            {
753                assert_eq!(
754                    roi.try_reciprocal(&roi.neg(&roi.one())).unwrap(),
755                    roi.neg(&roi.one())
756                );
757                assert_eq!(roi.try_reciprocal(&roi.one()).unwrap(), roi.one());
758                assert!(roi.try_reciprocal(&alpha).is_none());
759                assert!(roi.try_reciprocal(&beta).is_none());
760            }
761        }
762
763        println!("{:?}", roi);
764    }
765
766    #[test]
767    fn order_ideals() {
768        // Q[sqrt(-3)]
769        let anf = parse_rational_polynomial("x^2+3", "x")
770            .unwrap()
771            .algebraic_number_field()
772            .unwrap();
773
774        // Z[sqrt(-3)]
775        let order = anf
776            .order(vec![
777                parse_rational_polynomial("1", "x").unwrap(),
778                parse_rational_polynomial("x", "x").unwrap(),
779            ])
780            .unwrap();
781
782        let ideal6 = order
783            .ideals()
784            .principal_ideal(&order.from_int(Integer::from(6)));
785
786        let ideal15 = order
787            .ideals()
788            .principal_ideal(&order.from_int(Integer::from(15)));
789
790        assert!(
791            order.ideals().equal(
792                &order.ideals().add(&ideal6, &ideal15),
793                &order
794                    .ideals()
795                    .principal_ideal(&order.from_int(Integer::from(3)))
796            )
797        );
798
799        assert!(
800            order.ideals().equal(
801                &order.ideals().intersect(&ideal6, &ideal15),
802                &order
803                    .ideals()
804                    .principal_ideal(&order.from_int(Integer::from(30)))
805            )
806        );
807
808        assert!(
809            order.ideals().equal(
810                &order.ideals().quotient(&ideal15, &ideal6),
811                &order
812                    .ideals()
813                    .principal_ideal(&order.from_int(Integer::from(5)))
814            )
815        );
816    }
817
818    #[test]
819    fn order_conductor() {
820        // Q[sqrt(-3)]
821        let anf = parse_rational_polynomial("x^2+3", "x")
822            .unwrap()
823            .algebraic_number_field()
824            .unwrap();
825
826        // Z[1/2 + 1/2 sqrt(-3)]
827        let roi = anf.ring_of_integers();
828
829        // Z[sqrt(-3)]
830        let order = anf
831            .order(vec![
832                parse_rational_polynomial("1", "x").unwrap(),
833                parse_rational_polynomial("x", "x").unwrap(),
834            ])
835            .unwrap();
836
837        assert!(order.ideals().equal(
838            &order.conductor(),
839            &order.ideals().generated_ideal(vec![
840                vec![Integer::from(1), Integer::from(1)],
841                vec![Integer::from(0), Integer::from(2)]
842            ])
843        ));
844
845        assert!(
846            roi.ideals().equal(
847                &roi.suborder_conductor_as_ideal_of_self(&order),
848                &roi.ideals()
849                    .principal_ideal(&roi.from_int(Integer::from(2)))
850            )
851        );
852    }
853}
algebraeon_rings/algebraic_number_field/generic/order.rs

algebraeon_rings/algebraic_number_field/generic/
order.rs
