feanor_math/
local.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
use crate::algorithms::int_bisect;
use crate::pid::{EuclideanRing, EuclideanRingStore};
use crate::divisibility::*;
use crate::primitive_int::StaticRing;
use crate::ring::*;

///
/// Trait for principal ideal rings that additionally are local rings, i.e. have a unique
/// maximal ideal.
/// 
/// Note that in this case, the unique maximal ideal is clearly generated by a single element.
/// Such an element can be accessed via [`PrincipalLocalRing::max_ideal_gen()`]. Equivalently,
/// a principal local ring can be characterized by the property that for any elements `x, y`,
/// either `x | y` or `y | x`.
/// 
/// Principal local rings are also valuation rings, i.e. have a function `val: R -> ZZ_>0 u {∞}`
/// that satisfies `val(xy) = val(x) + val(y)`, `val(x + y) >= min(val(x), val(y))` and if `val(x) >= val(y)`
/// then `y | x`. This can be accessed using [`PrincipalLocalRing::valuation()`].
/// 
#[stability::unstable(feature = "enable")]
pub trait PrincipalLocalRing: EuclideanRing {

    ///
    /// Returns a generator `p` or the unique maximal ideal `(p)` of this ring.
    /// 
    /// In other words, for each element `x` we have either that `p | x` or `x | 1`. 
    /// 
    fn max_ideal_gen(&self) -> &Self::Element;

    ///
    /// Returns the smallest nonnegative integer `e` such that `p^e = 0` where `p` is 
    /// the generator of the maximal ideal.
    /// 
    fn nilpotent_power(&self) -> Option<usize>;

    ///
    /// Returns the largest nonnegative integer `e` such that `p^e | x` where `p` is 
    /// the generator of the maximal ideal.
    /// 
    fn valuation(&self, x: &Self::Element) -> Option<usize> {
        assert!(self.is_noetherian());
        if self.is_zero(x) {
            return None;
        }
        let ring = RingRef::new(self);
        return Some(int_bisect::find_root_floor(&StaticRing::<i64>::RING, 0, |e| {
            if *e < 0 || ring.checked_div(x, &ring.pow(ring.clone_el(ring.max_ideal_gen()), *e as usize)).is_some() {
                -1
            } else {
                1
            }
        }) as usize)
    }
}

///
/// [`RingStore`] for [`PrincipalLocalRing`]
/// 
#[stability::unstable(feature = "enable")]
pub trait PrincipalLocalRingStore: EuclideanRingStore
    where Self::Type: PrincipalLocalRing
{
    delegate!{ PrincipalLocalRing, fn max_ideal_gen(&self) -> &El<Self> }
    delegate!{ PrincipalLocalRing, fn valuation(&self, x: &El<Self>) -> Option<usize> }
    delegate!{ PrincipalLocalRing, fn nilpotent_power(&self) -> Option<usize> }
}

impl<R> PrincipalLocalRingStore for R
    where R: RingStore,
        R::Type: PrincipalLocalRing {}