feanor_math/
local.rs

1use crate::algorithms::int_bisect;
2use crate::divisibility::*;
3use crate::pid::{EuclideanRing, EuclideanRingStore};
4use crate::primitive_int::StaticRing;
5use crate::ring::*;
6
7/// Trait for principal ideal rings that additionally are local rings, i.e. have a unique
8/// maximal ideal.
9///
10/// Note that in this case, the unique maximal ideal is clearly generated by a single element.
11/// Such an element can be accessed via [`PrincipalLocalRing::max_ideal_gen()`]. Equivalently,
12/// a principal local ring can be characterized by the property that for any elements `x, y`,
13/// either `x | y` or `y | x`.
14///
15/// Principal local rings are also valuation rings, i.e. have a function `val: R -> ZZ_>0 u {∞}`
16/// that satisfies `val(xy) = val(x) + val(y)`, `val(x + y) >= min(val(x), val(y))` and if `val(x)
17/// >= val(y)` then `y | x`. This can be accessed using [`PrincipalLocalRing::valuation()`].
18#[stability::unstable(feature = "enable")]
19pub trait PrincipalLocalRing: EuclideanRing {
20    /// Returns a generator `p` or the unique maximal ideal `(p)` of this ring.
21    ///
22    /// In other words, for each element `x` we have either that `p | x` or `x | 1`.
23    fn max_ideal_gen(&self) -> &Self::Element;
24
25    /// Returns the smallest nonnegative integer `e` such that `p^e = 0` where `p` is
26    /// the generator of the maximal ideal.
27    fn nilpotent_power(&self) -> Option<usize>;
28
29    /// Returns the largest nonnegative integer `e` such that `p^e | x` where `p` is
30    /// the generator of the maximal ideal.
31    fn valuation(&self, x: &Self::Element) -> Option<usize> {
32        assert!(self.is_noetherian());
33        if self.is_zero(x) {
34            return None;
35        }
36        let ring = RingRef::new(self);
37        return Some(int_bisect::find_root_floor(&StaticRing::<i64>::RING, 0, |e| {
38            if *e < 0
39                || ring
40                    .checked_div(x, &ring.pow(ring.clone_el(ring.max_ideal_gen()), *e as usize))
41                    .is_some()
42            {
43                -1
44            } else {
45                1
46            }
47        }) as usize);
48    }
49}
50
51/// [`RingStore`] for [`PrincipalLocalRing`]
52#[stability::unstable(feature = "enable")]
53pub trait PrincipalLocalRingStore: EuclideanRingStore
54where
55    Self::Type: PrincipalLocalRing,
56{
57    delegate! { PrincipalLocalRing, fn max_ideal_gen(&self) -> &El<Self> }
58    delegate! { PrincipalLocalRing, fn valuation(&self, x: &El<Self>) -> Option<usize> }
59    delegate! { PrincipalLocalRing, fn nilpotent_power(&self) -> Option<usize> }
60}
61
62impl<R> PrincipalLocalRingStore for R
63where
64    R: RingStore,
65    R::Type: PrincipalLocalRing,
66{
67}
feanor_math/local.rs

feanor_math/
local.rs
