noether/numthy/
fractional_ideal.rs

1// SPDX-License-Identifier: MIT
2// Copyright (c) 2026 Benjamin Antieau and Deven Manam
3//! Exact nonzero fractional ideals of number-field orders.
4
5use core::fmt;
6use core::ops::{Add, Mul};
7use std::collections::{BTreeMap, BTreeSet};
8
9use serde::{Deserialize, Deserializer, Serialize, Serializer};
10
11use super::integer::{factor as factor_integer, remove_factor, FactorError};
12use super::number_field_order::{integer_lcm, ExactLattice};
13use super::{NumberFieldElement, NumberFieldOrder, NumberFieldOrderError, PrimeDecompositionError};
14use crate::commalg::{Ideal, PrimeIdeal};
15use crate::{
16    ContextMismatchError, Integer, NoetherError, Rational, Ring, SemanticType, TypeDescription,
17};
18
19static FRACTIONAL_IDEAL_DESCRIPTION: TypeDescription = TypeDescription {
20    semantic_id: "noether/numthy/FractionalIdeal@1",
21    rust_path: "noether::numthy::FractionalIdeal",
22    python_path: Some("noether.numthy.FractionalIdeal"),
23};
24
25/// Failure to construct or operate on a fractional ideal.
26#[derive(Debug, Clone, PartialEq, Eq)]
27pub enum FractionalIdealError {
28    /// Fractional ideals in this API are nonzero and need a nonzero generator.
29    ZeroIdeal,
30    /// An exact lattice failed a full-rank invariant.
31    InvalidLattice,
32    /// An integral ideal was required, but the lattice was not contained in its order.
33    NotIntegral,
34    /// Values from different number-field orders were combined.
35    ContextMismatch(ContextMismatchError),
36    /// Canonical serialized content was malformed.
37    InvalidEncoding(String),
38}
39
40impl fmt::Display for FractionalIdealError {
41    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
42        match self {
43            Self::ZeroIdeal => {
44                f.write_str("a fractional ideal needs at least one nonzero number-field generator")
45            }
46            Self::InvalidLattice => {
47                f.write_str("fractional-ideal generators did not span a full-rank exact lattice")
48            }
49            Self::NotIntegral => {
50                f.write_str("fractional ideal is not contained in its coefficient order")
51            }
52            Self::ContextMismatch(error) => error.fmt(f),
53            Self::InvalidEncoding(message) => {
54                write!(f, "invalid fractional-ideal encoding: {message}")
55            }
56        }
57    }
58}
59
60impl std::error::Error for FractionalIdealError {
61    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
62        match self {
63            Self::ContextMismatch(error) => Some(error),
64            _ => None,
65        }
66    }
67}
68
69impl From<ContextMismatchError> for FractionalIdealError {
70    fn from(value: ContextMismatchError) -> Self {
71        Self::ContextMismatch(value)
72    }
73}
74
75/// Failure to value or factor a number-field fractional ideal.
76#[derive(Debug, Clone, PartialEq, Eq)]
77pub enum IdealFactorizationError {
78    /// Unique prime-ideal factorization requires the maximal order.
79    NonMaximalOrder,
80    /// Values from different number-field orders were combined.
81    ContextMismatch(ContextMismatchError),
82    /// Exact order arithmetic failed.
83    Order(NumberFieldOrderError),
84    /// Exact ideal arithmetic failed.
85    Ideal(FractionalIdealError),
86    /// Rational-prime decomposition failed.
87    PrimeDecomposition(PrimeDecompositionError),
88    /// Complete integer factorization failed.
89    IntegerFactorization(FactorError),
90    /// A signed public exponent did not fit in `i64`.
91    ExponentOverflow,
92    /// An exact reconstruction invariant failed.
93    Invariant(&'static str),
94}
95
96impl fmt::Display for IdealFactorizationError {
97    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
98        match self {
99            Self::NonMaximalOrder => f.write_str(
100                "ideal valuation and factorization require a maximal number-field order",
101            ),
102            Self::ContextMismatch(error) => error.fmt(f),
103            Self::Order(error) => error.fmt(f),
104            Self::Ideal(error) => error.fmt(f),
105            Self::PrimeDecomposition(error) => error.fmt(f),
106            Self::IntegerFactorization(error) => error.fmt(f),
107            Self::ExponentOverflow => {
108                f.write_str("ideal-factorization exponent does not fit in signed 64 bits")
109            }
110            Self::Invariant(claim) => write!(f, "ideal-factorization invariant failed: {claim}"),
111        }
112    }
113}
114
115impl std::error::Error for IdealFactorizationError {
116    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
117        match self {
118            Self::ContextMismatch(error) => Some(error),
119            Self::Order(error) => Some(error),
120            Self::Ideal(error) => Some(error),
121            Self::PrimeDecomposition(error) => Some(error),
122            Self::IntegerFactorization(error) => Some(error),
123            Self::NonMaximalOrder | Self::ExponentOverflow | Self::Invariant(_) => None,
124        }
125    }
126}
127
128impl From<NumberFieldOrderError> for IdealFactorizationError {
129    fn from(value: NumberFieldOrderError) -> Self {
130        Self::Order(value)
131    }
132}
133
134impl From<FractionalIdealError> for IdealFactorizationError {
135    fn from(value: FractionalIdealError) -> Self {
136        Self::Ideal(value)
137    }
138}
139
140impl From<PrimeDecompositionError> for IdealFactorizationError {
141    fn from(value: PrimeDecompositionError) -> Self {
142        Self::PrimeDecomposition(value)
143    }
144}
145
146impl From<FactorError> for IdealFactorizationError {
147    fn from(value: FactorError) -> Self {
148        Self::IntegerFactorization(value)
149    }
150}
151
152/// A nonzero fractional ideal of an exact number-field order.
153///
154/// The ideal is stored as a canonical row-Hermite rational lattice in the
155/// ambient field's distinguished power basis. Construction from generators
156/// forms their `NumberFieldOrder`-span; equality therefore compares ideals,
157/// not the supplied generator list.
158#[derive(Clone)]
159pub struct FractionalIdeal {
160    order: NumberFieldOrder,
161    lattice: ExactLattice,
162}
163
164impl FractionalIdeal {
165    /// Construct the fractional ideal generated over `order` by exact field elements.
166    pub fn new(
167        order: NumberFieldOrder,
168        generators: &[NumberFieldElement],
169    ) -> Result<Self, FractionalIdealError> {
170        if generators.is_empty() || generators.iter().all(NumberFieldElement::is_zero) {
171            return Err(FractionalIdealError::ZeroIdeal);
172        }
173        if generators
174            .iter()
175            .any(|element| !order.field().contains(element))
176        {
177            return Err(FractionalIdealError::ContextMismatch(
178                ContextMismatchError {
179                    expected: format!("NumberFieldOrder(discriminant={})", order.discriminant()),
180                    actual: "number-field element from another field".to_owned(),
181                },
182            ));
183        }
184
185        let order_basis = order.basis();
186        let mut spanning = Vec::with_capacity(generators.len() * order_basis.len());
187        for generator in generators {
188            if generator.is_zero() {
189                continue;
190            }
191            for basis_element in &order_basis {
192                spanning.push(generator.mul(basis_element)?);
193            }
194        }
195        Self::from_spanning_elements(order, &spanning)
196    }
197
198    fn from_spanning_elements(
199        order: NumberFieldOrder,
200        elements: &[NumberFieldElement],
201    ) -> Result<Self, FractionalIdealError> {
202        let lattice = ExactLattice::from_spanning_elements(order.field(), elements)
203            .ok_or(FractionalIdealError::InvalidLattice)?;
204        Ok(Self { order, lattice })
205    }
206
207    fn mismatch(&self, other: &Self) -> ContextMismatchError {
208        ContextMismatchError {
209            expected: format!(
210                "NumberFieldOrder(discriminant={})",
211                self.order.discriminant()
212            ),
213            actual: format!(
214                "NumberFieldOrder(discriminant={})",
215                other.order.discriminant()
216            ),
217        }
218    }
219
220    /// The coefficient order of this ideal.
221    pub fn order(&self) -> &NumberFieldOrder {
222        &self.order
223    }
224
225    /// Canonical `Z`-basis of this fractional ideal.
226    pub fn basis(&self) -> Vec<NumberFieldElement> {
227        self.lattice.basis(self.order.field())
228    }
229
230    /// Whether an exact field element lies in this fractional ideal.
231    pub fn contains(&self, element: &NumberFieldElement) -> bool {
232        self.order.field().contains(element) && self.lattice.contains(element)
233    }
234
235    /// Whether this fractional ideal is contained in its coefficient order.
236    pub fn is_integral(&self) -> bool {
237        self.basis()
238            .iter()
239            .all(|element| self.order.contains(element))
240    }
241
242    /// View this value as a generic integral ideal when it lies in its order.
243    pub fn as_ideal(&self) -> Result<Ideal<NumberFieldOrder>, FractionalIdealError> {
244        if !self.is_integral() {
245            return Err(FractionalIdealError::NotIntegral);
246        }
247        Ideal::from_canonical_generators(self.order.clone(), self.basis())
248            .map_err(|_| FractionalIdealError::InvalidLattice)
249    }
250
251    /// Sum of two fractional ideals of the same order.
252    pub fn add(&self, other: &Self) -> Result<Self, FractionalIdealError> {
253        if self.order != other.order {
254            return Err(self.mismatch(other).into());
255        }
256        let mut spanning = self.basis();
257        spanning.extend(other.basis());
258        Self::from_spanning_elements(self.order.clone(), &spanning)
259    }
260
261    /// Product of two fractional ideals of the same order.
262    pub fn mul(&self, other: &Self) -> Result<Self, FractionalIdealError> {
263        if self.order != other.order {
264            return Err(self.mismatch(other).into());
265        }
266        let left_basis = self.basis();
267        let right_basis = other.basis();
268        let mut spanning = Vec::with_capacity(left_basis.len() * right_basis.len());
269        for left in &left_basis {
270            for right in &right_basis {
271                spanning.push(left.mul(right)?);
272            }
273        }
274        Self::from_spanning_elements(self.order.clone(), &spanning)
275    }
276
277    /// Exact absolute ideal norm, extended multiplicatively to fractional ideals.
278    pub fn norm(&self) -> Rational {
279        let degree = self.order.field().degree();
280        let (ideal_numerator, ideal_denominator) = self.lattice.covolume_parts(degree);
281        let (order_numerator, order_denominator) = self.order.covolume_parts();
282        Rational::new(
283            &ideal_numerator * &order_denominator,
284            &ideal_denominator * &order_numerator,
285        )
286        .expect("an exact full-rank lattice has positive nonzero covolume")
287    }
288
289    fn subset_of(&self, other: &Self) -> bool {
290        self.order == other.order && self.basis().iter().all(|element| other.contains(element))
291    }
292
293    fn scaled_by_integer(&self, scalar: &Integer) -> Result<Self, FractionalIdealError> {
294        let scalar = self.order.field().scalar(Rational::from(scalar.clone()));
295        let basis = self
296            .basis()
297            .iter()
298            .map(|element| element.mul(&scalar))
299            .collect::<Result<Vec<_>, _>>()?;
300        Self::from_spanning_elements(self.order.clone(), &basis)
301    }
302
303    fn integral_multiple(&self) -> Result<(Integer, Self), IdealFactorizationError> {
304        let mut denominator = Integer::one();
305        for element in self.basis() {
306            let coordinates = self.order.rational_coordinates(&element).ok_or(
307                IdealFactorizationError::Invariant(
308                    "fractional-ideal basis left its ambient order lattice",
309                ),
310            )?;
311            for coordinate in coordinates {
312                denominator = integer_lcm(&denominator, &coordinate.denominator());
313            }
314        }
315        let integral = self.scaled_by_integer(&denominator)?;
316        if !integral.is_integral() {
317            return Err(IdealFactorizationError::Invariant(
318                "clearing order-coordinate denominators did not make the ideal integral",
319            ));
320        }
321        Ok((denominator, integral))
322    }
323
324    fn unit_ideal(&self) -> Result<Self, FractionalIdealError> {
325        self.order.fractional_ideal(&[self.order.one()])
326    }
327
328    fn power(ideal: &Self, mut exponent: u64) -> Result<Self, IdealFactorizationError> {
329        let mut output = ideal.unit_ideal()?;
330        let mut base = ideal.clone();
331        while exponent != 0 {
332            if exponent & 1 == 1 {
333                output = output.mul(&base)?;
334            }
335            exponent >>= 1;
336            if exponent != 0 {
337                base = base.mul(&base)?;
338            }
339        }
340        Ok(output)
341    }
342
343    fn integral_valuation(
344        &self,
345        prime: &PrimeIdeal<NumberFieldOrder>,
346    ) -> Result<u64, IdealFactorizationError> {
347        if !self.is_integral() {
348            return Err(IdealFactorizationError::Invariant(
349                "integral valuation received a nonintegral ideal",
350            ));
351        }
352        let norm = self.norm();
353        if !norm.denominator().is_one() {
354            return Err(IdealFactorizationError::Invariant(
355                "integral ideal had a nonintegral norm",
356            ));
357        }
358        let (_, norm_exponent) = remove_factor(&norm.numerator(), &prime.rational_prime());
359        let residue_degree = u64::try_from(prime.residue_degree())
360            .map_err(|_| IdealFactorizationError::ExponentOverflow)?;
361        let upper_bound = norm_exponent / residue_degree;
362        if upper_bound == 0 {
363            return Ok(0);
364        }
365
366        let prime_ideal = prime.as_fractional_ideal();
367        let mut powers = vec![(1_u64, prime_ideal.clone())];
368        while powers.last().expect("one prime power exists").0 <= upper_bound / 2 {
369            let (exponent, power) = powers.last().expect("one prime power exists");
370            powers.push((exponent * 2, power.mul(power)?));
371        }
372
373        let mut valuation = 0_u64;
374        let mut contained_power = self.unit_ideal()?;
375        for (step, power) in powers.iter().rev() {
376            if *step > upper_bound - valuation {
377                continue;
378            }
379            let candidate = contained_power.mul(power)?;
380            if self.subset_of(&candidate) {
381                valuation += *step;
382                contained_power = candidate;
383            }
384        }
385        if valuation < upper_bound && self.subset_of(&contained_power.mul(&prime_ideal)?) {
386            return Err(IdealFactorizationError::Invariant(
387                "binary ideal containment did not find the maximal valuation",
388            ));
389        }
390        Ok(valuation)
391    }
392
393    /// The signed `P`-adic valuation of this fractional ideal.
394    pub fn valuation(
395        &self,
396        prime: &PrimeIdeal<NumberFieldOrder>,
397    ) -> Result<i64, IdealFactorizationError> {
398        if self.order != *prime.order() {
399            return Err(IdealFactorizationError::ContextMismatch(
400                ContextMismatchError {
401                    expected: format!(
402                        "NumberFieldOrder(discriminant={})",
403                        self.order.discriminant()
404                    ),
405                    actual: format!(
406                        "NumberFieldOrder(discriminant={})",
407                        prime.order().discriminant()
408                    ),
409                },
410            ));
411        }
412        if !self.order.is_maximal()? {
413            return Err(IdealFactorizationError::NonMaximalOrder);
414        }
415        let (denominator, integral) = self.integral_multiple()?;
416        let integral_valuation = integral.integral_valuation(prime)?;
417        let (_, denominator_exponent) = remove_factor(&denominator, &prime.rational_prime());
418        let ramification = u64::try_from(prime.ramification_index())
419            .map_err(|_| IdealFactorizationError::ExponentOverflow)?;
420        let denominator_valuation = denominator_exponent
421            .checked_mul(ramification)
422            .ok_or(IdealFactorizationError::ExponentOverflow)?;
423        let signed = i128::from(integral_valuation) - i128::from(denominator_valuation);
424        i64::try_from(signed).map_err(|_| IdealFactorizationError::ExponentOverflow)
425    }
426
427    /// Complete signed prime-ideal factorization in this maximal order.
428    ///
429    /// The result is reconstructed exactly after moving negative powers to
430    /// the left side, so no unchecked factor list can escape this method.
431    pub fn factor(
432        &self,
433    ) -> Result<Vec<(PrimeIdeal<NumberFieldOrder>, i64)>, IdealFactorizationError> {
434        if !self.order.is_maximal()? {
435            return Err(IdealFactorizationError::NonMaximalOrder);
436        }
437        let (denominator, integral) = self.integral_multiple()?;
438        let norm = integral.norm();
439        if !norm.denominator().is_one() {
440            return Err(IdealFactorizationError::Invariant(
441                "integral ideal had a nonintegral norm",
442            ));
443        }
444
445        let denominator_factorization = factor_integer(&denominator)?;
446        let denominator_exponents = denominator_factorization
447            .factors()
448            .iter()
449            .cloned()
450            .collect::<BTreeMap<_, _>>();
451        let mut rational_primes = denominator_exponents
452            .keys()
453            .cloned()
454            .collect::<BTreeSet<_>>();
455        rational_primes.extend(
456            factor_integer(&norm.numerator())?
457                .factors()
458                .iter()
459                .map(|(prime, _)| prime.clone()),
460        );
461
462        let mut factors = Vec::new();
463        for rational_prime in rational_primes {
464            let denominator_exponent = denominator_exponents
465                .get(&rational_prime)
466                .copied()
467                .unwrap_or(0);
468            for prime in self.order.prime_ideals_above(&rational_prime)? {
469                let integral_valuation = integral.integral_valuation(&prime)?;
470                let ramification = u64::try_from(prime.ramification_index())
471                    .map_err(|_| IdealFactorizationError::ExponentOverflow)?;
472                let cleared_valuation = denominator_exponent
473                    .checked_mul(ramification)
474                    .ok_or(IdealFactorizationError::ExponentOverflow)?;
475                let exponent = i128::from(integral_valuation) - i128::from(cleared_valuation);
476                let exponent = i64::try_from(exponent)
477                    .map_err(|_| IdealFactorizationError::ExponentOverflow)?;
478                if exponent != 0 {
479                    factors.push((prime, exponent));
480                }
481            }
482        }
483
484        let mut left = self.clone();
485        let mut right = self.unit_ideal()?;
486        for (prime, exponent) in &factors {
487            let power = Self::power(&prime.as_fractional_ideal(), exponent.unsigned_abs())?;
488            if *exponent < 0 {
489                left = left.mul(&power)?;
490            } else {
491                right = right.mul(&power)?;
492            }
493        }
494        if left != right {
495            return Err(IdealFactorizationError::Invariant(
496                "prime powers did not reconstruct the fractional ideal",
497            ));
498        }
499        Ok(factors)
500    }
501
502    /// Serialize this exact ideal to canonical JSON.
503    pub fn to_json(&self) -> Result<String, NoetherError> {
504        serde_json::to_string(self).map_err(|error| NoetherError::Serialization(error.to_string()))
505    }
506
507    /// Restore and validate an exact fractional ideal from canonical JSON.
508    pub fn from_json(value: &str) -> Result<Self, NoetherError> {
509        serde_json::from_str(value).map_err(|error| NoetherError::Serialization(error.to_string()))
510    }
511}
512
513impl PartialEq for FractionalIdeal {
514    fn eq(&self, other: &Self) -> bool {
515        self.order == other.order && self.lattice == other.lattice
516    }
517}
518
519impl Eq for FractionalIdeal {}
520
521impl fmt::Display for FractionalIdeal {
522    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
523        write!(
524            f,
525            "FractionalIdeal(degree={}, norm={})",
526            self.order.field().degree(),
527            self.norm()
528        )
529    }
530}
531
532impl fmt::Debug for FractionalIdeal {
533    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
534        fmt::Display::fmt(self, f)
535    }
536}
537
538impl SemanticType for FractionalIdeal {
539    const TYPE_ID: &'static str = "noether/numthy/FractionalIdeal@1";
540
541    fn canonical_bytes(&self) -> Result<Vec<u8>, NoetherError> {
542        let mut output = Vec::new();
543        append_component(&mut output, &self.order.canonical_bytes()?)?;
544        for element in self.basis() {
545            append_component(&mut output, &element.canonical_bytes()?)?;
546        }
547        Ok(output)
548    }
549
550    fn describe() -> &'static TypeDescription {
551        &FRACTIONAL_IDEAL_DESCRIPTION
552    }
553}
554
555fn append_component(output: &mut Vec<u8>, component: &[u8]) -> Result<(), NoetherError> {
556    let length = u64::try_from(component.len()).map_err(|_| {
557        NoetherError::Serialization(
558            "fractional-ideal component does not fit canonical framing".to_owned(),
559        )
560    })?;
561    output.extend_from_slice(&length.to_be_bytes());
562    output.extend_from_slice(component);
563    Ok(())
564}
565
566impl Add<&FractionalIdeal> for &FractionalIdeal {
567    type Output = Result<FractionalIdeal, FractionalIdealError>;
568
569    fn add(self, rhs: &FractionalIdeal) -> Self::Output {
570        self.add(rhs)
571    }
572}
573
574impl Mul<&FractionalIdeal> for &FractionalIdeal {
575    type Output = Result<FractionalIdeal, FractionalIdealError>;
576
577    fn mul(self, rhs: &FractionalIdeal) -> Self::Output {
578        self.mul(rhs)
579    }
580}
581
582#[derive(Serialize, Deserialize)]
583#[serde(deny_unknown_fields)]
584struct FractionalIdealRepr {
585    order: NumberFieldOrder,
586    basis: Vec<Vec<String>>,
587}
588
589impl Serialize for FractionalIdeal {
590    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
591    where
592        S: Serializer,
593    {
594        FractionalIdealRepr {
595            order: self.order.clone(),
596            basis: self
597                .basis()
598                .into_iter()
599                .map(|element| {
600                    element
601                        .coefficients()
602                        .into_iter()
603                        .map(|coefficient| coefficient.to_string())
604                        .collect()
605                })
606                .collect(),
607        }
608        .serialize(serializer)
609    }
610}
611
612impl<'de> Deserialize<'de> for FractionalIdeal {
613    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
614    where
615        D: Deserializer<'de>,
616    {
617        let repr = FractionalIdealRepr::deserialize(deserializer)?;
618        let basis = repr
619            .basis
620            .iter()
621            .map(|coefficients| {
622                let coefficients = coefficients
623                    .iter()
624                    .map(|coefficient| {
625                        coefficient
626                            .parse::<Rational>()
627                            .map_err(serde::de::Error::custom)
628                    })
629                    .collect::<Result<Vec<_>, D::Error>>()?;
630                repr.order
631                    .field()
632                    .element(&coefficients)
633                    .map_err(serde::de::Error::custom)
634            })
635            .collect::<Result<Vec<_>, D::Error>>()?;
636        Self::new(repr.order, &basis).map_err(serde::de::Error::custom)
637    }
638}
639
640impl NumberFieldOrder {
641    /// Construct the nonzero fractional ideal generated by `generators`.
642    pub fn fractional_ideal(
643        &self,
644        generators: &[NumberFieldElement],
645    ) -> Result<FractionalIdeal, FractionalIdealError> {
646        FractionalIdeal::new(self.clone(), generators)
647    }
648}
noether/numthy/fractional_ideal.rs

noether/numthy/
fractional_ideal.rs
