#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::collections::BTreeMap;
use crate::coeff::{Field, Plethystic, QAlgebra, Ring};
use crate::qt::QtPoly;
#[derive(Clone, Debug)]
pub struct Frac<C: Ring> {
num: QtPoly<C>,
den: BTreeMap<(u32, u32), u32>,
}
impl<C: Ring + 'static> crate::memo::HeapSize for Frac<C> {
fn heap_bytes(&self) -> usize {
crate::memo::HeapSize::heap_bytes(&self.num) + crate::memo::HeapSize::heap_bytes(&self.den)
}
}
impl<C: Ring> Frac<C> {
pub fn from_poly(num: QtPoly<C>) -> Self {
let mut f = Frac {
num,
den: BTreeMap::new(),
};
f.reduce();
f
}
pub fn inv_factor(a: u32, b: u32) -> Self {
assert!(a > 0 || b > 0, "1 - q^0 t^0 is zero");
let mut den = BTreeMap::new();
den.insert((a, b), 1);
Frac {
num: <QtPoly<C> as Ring>::one(),
den,
}
}
pub fn factor(a: u32, b: u32) -> Self {
Frac::from_poly(binomial(a, b))
}
pub fn from_factors(factors: &BTreeMap<(u32, u32), i32>) -> Self {
let mut num = <QtPoly<C> as Ring>::one();
let mut den = BTreeMap::new();
for (&(a, b), &m) in factors {
assert!(a > 0 || b > 0, "1 - q^0 t^0 is zero");
match m.cmp(&0) {
core::cmp::Ordering::Greater => {
for _ in 0..m {
num = num.mul_binomial(a, b);
}
}
core::cmp::Ordering::Less => {
den.insert((a, b), (-m) as u32);
}
core::cmp::Ordering::Equal => {}
}
}
Frac { num, den }
}
pub fn mul_factors(&self, factors: &BTreeMap<(u32, u32), i32>) -> Self {
let mut num = self.num.clone();
let mut den = self.den.clone();
for (&(a, b), &m) in factors {
assert!(a > 0 || b > 0, "1 - q^0 t^0 is zero");
match m.cmp(&0) {
core::cmp::Ordering::Greater => {
for _ in 0..m {
num = num.mul_binomial(a, b);
}
}
core::cmp::Ordering::Less => {
*den.entry((a, b)).or_insert(0) += (-m) as u32;
}
core::cmp::Ordering::Equal => {}
}
}
Frac { num, den }
}
pub fn parts(&self) -> (&QtPoly<C>, impl Iterator<Item = (&(u32, u32), &u32)>) {
(&self.num, self.den.iter())
}
pub fn denominator(&self) -> QtPoly<C> {
let mut d = <QtPoly<C> as Ring>::one();
for (&(a, b), &m) in &self.den {
for _ in 0..m {
d = d.mul_binomial(a, b);
}
}
d
}
pub fn into_poly(mut self) -> Option<QtPoly<C>> {
self.reduce();
self.den.is_empty().then_some(self.num)
}
pub fn reduce(&mut self) {
if self.num.is_zero() {
self.den.clear();
return;
}
self.den.retain(|&(a, b), m| {
while *m > 0 {
match divide_by_factor(&self.num, a, b) {
Some(q) => {
self.num = q;
*m -= 1;
}
None => break,
}
}
*m > 0
});
}
fn lift(&self, target: &BTreeMap<(u32, u32), u32>) -> QtPoly<C> {
let mut num = self.num.clone();
for (&(a, b), &m) in target {
let extra = m - self.den.get(&(a, b)).copied().unwrap_or(0);
for _ in 0..extra {
num = num.mul_binomial(a, b);
}
}
num
}
}
impl<C: Field> Frac<C> {
pub fn eval(&self, q: &C, t: &C) -> Option<C> {
let mut d = C::one();
for (&(a, b), &m) in &self.den {
let mut f = C::one();
f.add_assign(&pow(q, a).mul(&pow(t, b)).neg());
if f.is_zero() {
return None;
}
for _ in 0..m {
d = d.mul(&f);
}
}
Some(self.num.eval(q, t).div(&d))
}
}
fn pow<C: Ring>(x: &C, n: u32) -> C {
let mut acc = C::one();
for _ in 0..n {
acc = acc.mul(x);
}
acc
}
fn binomial<C: Ring>(a: u32, b: u32) -> QtPoly<C> {
let mut p = <QtPoly<C> as Ring>::one();
p.add_term(a, b, C::one().neg());
p
}
pub(crate) fn divide_by_factor<C: Ring>(n: &QtPoly<C>, a: u32, b: u32) -> Option<QtPoly<C>> {
let terms = n.raw();
let Some(bound) = terms.iter().map(|(k, _)| k.0 + k.1).max() else {
return Some(QtPoly::zero());
};
let mut consumed = vec![false; terms.len()];
let mut out: Vec<((u32, u32), C)> = Vec::with_capacity(terms.len());
for i in 0..terms.len() {
if consumed[i] {
continue;
}
let mut sum = C::zero();
let mut p = terms[i].0;
let mut lo = i;
loop {
match terms[lo..].binary_search_by_key(&p, |e| e.0) {
Ok(off) => {
let j = lo + off;
sum.add_assign(&terms[j].1);
consumed[j] = true;
lo = j + 1;
}
Err(off) => lo += off,
}
if sum.is_zero() {
if p.0 + p.1 > bound {
break;
}
} else {
if p.0 + p.1 + a + b > bound {
return None;
}
out.push((p, sum.clone()));
}
p = (p.0 + a, p.1 + b);
}
}
out.sort_unstable_by_key(|x| x.0);
Some(QtPoly::from_sorted(out))
}
impl<C: Ring> PartialEq for Frac<C> {
fn eq(&self, other: &Self) -> bool {
if self.den == other.den {
return self.num == other.num;
}
let mut lcm = self.den.clone();
for (k, &m) in &other.den {
let e = lcm.entry(*k).or_insert(0);
*e = (*e).max(m);
}
self.lift(&lcm) == other.lift(&lcm)
}
}
impl<C: Ring> Eq for Frac<C> {}
crate::coeff::impl_ring_ops!([C: Ring] Frac<C>);
impl<C: Ring> Ring for Frac<C> {
fn zero() -> Self {
Frac {
num: QtPoly::zero(),
den: BTreeMap::new(),
}
}
fn one() -> Self {
Frac {
num: <QtPoly<C> as Ring>::one(),
den: BTreeMap::new(),
}
}
fn is_zero(&self) -> bool {
self.num.is_zero()
}
fn add_assign(&mut self, other: &Self) {
if other.is_zero() {
return;
}
if self.is_zero() {
*self = other.clone();
return;
}
if other
.den
.iter()
.any(|(k, &m)| self.den.get(k).copied().unwrap_or(0) < m)
{
let mut lcm = self.den.clone();
for (k, &m) in &other.den {
let e = lcm.entry(*k).or_insert(0);
*e = (*e).max(m);
}
self.num = self.lift(&lcm);
self.den = lcm;
}
let lifted = other.lift(&self.den);
self.num.add_assign(&lifted);
}
fn mul(&self, other: &Self) -> Self {
if self.is_zero() || other.is_zero() {
return Self::zero();
}
let mut den = self.den.clone();
for (k, &m) in &other.den {
*den.entry(*k).or_insert(0) += m;
}
let mut f = Frac {
num: self.num.mul(&other.num),
den,
};
f.reduce();
f
}
fn neg(&self) -> Self {
Frac {
num: self.num.neg(),
den: self.den.clone(),
}
}
fn from_i64(n: i64) -> Self {
Frac::from_poly(<QtPoly<C> as Ring>::from_i64(n))
}
fn from_u128(n: u128) -> Self {
Frac::from_poly(<QtPoly<C> as Ring>::from_u128(n))
}
fn from_i128(n: i128) -> Self {
Frac::from_poly(<QtPoly<C> as Ring>::from_i128(n))
}
fn try_from_u128(n: u128) -> Option<Self> {
<QtPoly<C> as Ring>::try_from_u128(n).map(Frac::from_poly)
}
fn try_from_i128(n: i128) -> Option<Self> {
<QtPoly<C> as Ring>::try_from_i128(n).map(Frac::from_poly)
}
}
impl<C: QAlgebra> QAlgebra for Frac<C> {
fn div_u128(&self, n: u128) -> Self {
Frac {
num: self.num.div_u128(n),
den: self.den.clone(),
}
}
}
impl<C: Plethystic> Plethystic for Frac<C> {
fn frobenius(&self, n: u32) -> Self {
let mut f = Frac {
num: self.num.frobenius(n),
den: self
.den
.iter()
.map(|(&(a, b), &m)| ((a * n, b * n), m))
.collect(),
};
f.reduce();
f
}
}
impl<C: Ring> Frac<C> {
pub fn ratio(a1: u32, b1: u32, a2: u32, b2: u32) -> Self {
assert!(a2 > 0 || b2 > 0, "1 - q^0 t^0 is zero");
let num = if a1 == 0 && b1 == 0 {
<QtPoly<C> as Ring>::one()
} else {
binomial(a1, b1)
};
let mut den = BTreeMap::new();
den.insert((a2, b2), 1);
let mut f = Frac { num, den };
f.reduce();
f
}
}
impl<C: Ring> core::fmt::Display for Frac<C> {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
write!(f, "({})", self.num)?;
for (&(a, b), &m) in &self.den {
write!(f, "/(1-q^{a}t^{b})")?;
if m > 1 {
write!(f, "^{m}")?;
}
}
Ok(())
}
}
pub(crate) fn diff_may_divide<C: Ring>(n: &QtPoly<C>, a: u32, b: u32) -> bool {
let mut d = (a, b);
while d.1 != 0 {
d = (d.1, d.0 % d.1);
}
let (ap, bp) = (a / d.0, b / d.0);
let mut acc: Vec<C> = Vec::new();
for (&(x, y), c) in n.terms() {
let deg = (x * bp + y * ap) as usize;
if acc.len() <= deg {
acc.resize(deg + 1, C::zero());
}
acc[deg].add_assign(c);
}
acc.iter().all(C::is_zero)
}
pub(crate) fn divide_by_diff<C: Ring>(n: &QtPoly<C>, a: u32, b: u32) -> Option<QtPoly<C>> {
debug_assert!(a > 0 && b > 0, "divide_by_diff is for genuine Diff atoms");
let terms = n.raw();
if terms.is_empty() {
return Some(QtPoly::zero());
}
let max_t = terms
.iter()
.map(|(k, _)| k.1)
.max()
.expect("the empty case returned three lines above, so `terms` has a maximum");
let mut consumed = vec![false; terms.len()];
let mut out: Vec<((u32, u32), C)> = Vec::with_capacity(terms.len());
for i in (0..terms.len()).rev() {
if consumed[i] {
continue;
}
let mut running = C::zero();
let mut p = terms[i].0;
let mut hi = terms.len();
loop {
match terms[..hi].binary_search_by_key(&p, |e| e.0) {
Ok(j) => {
if !consumed[j] {
running.add_assign(&terms[j].1);
consumed[j] = true;
}
hi = j;
}
Err(j) => hi = j,
}
if !running.is_zero() {
if p.0 < a || p.1 > max_t {
return None;
}
out.push(((p.0 - a, p.1), running.clone()));
} else if p.1 > max_t || hi == 0 {
break;
}
if p.0 < a {
break;
}
p = (p.0 - a, p.1 + b);
}
}
out.sort_unstable_by_key(|x| x.0);
Some(QtPoly::from_sorted(out))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::Rational;
type F = Frac<Rational>;
fn r(n: i128) -> Rational {
Rational::from_int(n)
}
#[test]
fn frobenius_is_a_ring_homomorphism_on_fractions() {
let a = F::inv_factor(1, 1); let b = F::from_poly(binomial(2, 0)); for n in 1..4 {
assert_eq!(
a.mul(&b).frobenius(n),
a.frobenius(n).mul(&b.frobenius(n)),
"multiplicative at n = {n}"
);
let mut sum = a.clone();
sum.add_assign(&b);
let mut raised = a.frobenius(n);
raised.add_assign(&b.frobenius(n));
assert_eq!(sum.frobenius(n), raised, "additive at n = {n}");
}
assert_eq!(a.frobenius(1), a, "n = 1 is the identity");
assert_eq!(a.frobenius(2), F::inv_factor(2, 2));
}
#[test]
fn exact_division_by_a_binomial() {
let one_minus_q2: QtPoly<Rational> = binomial(2, 0);
let q = divide_by_factor(&one_minus_q2, 1, 0).expect("(1-q) divides (1-q^2)");
assert_eq!(q.coeff(0, 0), r(1));
assert_eq!(q.coeff(1, 0), r(1));
assert_eq!(q.len(), 2, "{q}");
assert!(divide_by_factor(&one_minus_q2, 0, 1).is_none());
assert_eq!(q.mul(&binomial(1, 0)), one_minus_q2);
}
#[test]
fn division_visits_keys_the_numerator_lacks() {
let n: QtPoly<Rational> = binomial(3, 0);
let q = divide_by_factor(&n, 1, 0).expect("(1-q) divides (1-q^3)");
for a in 0..3 {
assert_eq!(q.coeff(a, 0), r(1), "coefficient of q^{a}");
}
assert_eq!(q.len(), 3, "{q}");
}
#[test]
fn division_handles_interleaved_chains() {
let mut f: QtPoly<Rational> = <QtPoly<Rational> as Ring>::one();
f.add_term(1, 0, r(1));
f.add_term(0, 1, r(1));
let n = f.mul_binomial(1, 1);
let got = divide_by_factor(&n, 1, 1).expect("(1-qt) divides its own multiple");
assert_eq!(got, f, "got {got}, want {f}");
}
#[test]
fn non_divisibility_is_detected() {
let mut f: QtPoly<Rational> = <QtPoly<Rational> as Ring>::one();
f.add_term(2, 3, r(1)); for (a, b) in [(1, 0), (0, 1), (1, 1), (2, 3), (1, 2)] {
assert!(
divide_by_factor(&f, a, b).is_none(),
"(1 - q^{a} t^{b}) must not divide {f}"
);
}
}
#[test]
fn division_inverts_multiplication() {
let mut dense: QtPoly<Rational> = QtPoly::zero();
for a in 0..4 {
for b in 0..3 {
dense.add_term(a, b, r(i128::from(a) - i128::from(b) + 1));
}
}
let mut sparse: QtPoly<Rational> = QtPoly::zero();
sparse.add_term(0, 0, r(1));
sparse.add_term(4, 1, r(-3));
sparse.add_term(1, 6, r(5));
for f in [dense, sparse] {
for (a, b) in [(1, 0), (0, 1), (1, 1), (2, 1), (3, 3)] {
let prod = f.mul_binomial(a, b);
let back = divide_by_factor(&prod, a, b)
.unwrap_or_else(|| panic!("(1 - q^{a} t^{b}) must divide its own multiple"));
assert_eq!(back, f, "round trip through (1 - q^{a} t^{b})");
}
}
}
#[test]
fn the_two_exact_divisions_agree() {
let mut dense: QtPoly<Rational> = QtPoly::zero();
for a in 0..4 {
for b in 0..3 {
dense.add_term(a, b, r(i128::from(a) - i128::from(b) + 1));
}
}
let mut sparse: QtPoly<Rational> = QtPoly::zero();
sparse.add_term(0, 0, r(1));
sparse.add_term(4, 1, r(-3));
sparse.add_term(1, 6, r(5));
for f in [dense, sparse] {
for (a, b) in [(1, 0), (0, 1), (1, 1), (2, 1), (3, 3)] {
let d = binomial::<Rational>(a, b);
let prod = f.mul_binomial(a, b);
assert_eq!(
prod.divide_exact(&d),
divide_by_factor(&prod, a, b),
"(1 - q^{a} t^{b}) dividing its own multiple"
);
assert_eq!(
f.divide_exact(&d),
divide_by_factor(&f, a, b),
"(1 - q^{a} t^{b}) against a non-multiple"
);
}
}
}
#[test]
fn equality_is_not_structural() {
let mut one_plus_q: QtPoly<Rational> = <QtPoly<Rational> as Ring>::one();
one_plus_q.add_term(1, 0, r(1));
let a = F::from_poly(one_plus_q).mul(&F::inv_factor(2, 0));
let b = F::inv_factor(1, 0);
assert_eq!(a, b, "{a} must equal {b}");
assert_ne!(a.den, b.den, "the representations must differ");
}
#[test]
fn ring_axioms_hold() {
let a = F::inv_factor(1, 0); let b = F::inv_factor(0, 1); let one = <F as Ring>::one();
assert_eq!(a.mul(&one), a);
assert_eq!(a.mul(&b), b.mul(&a));
let mut z = a.clone();
z.add_assign(&a.neg());
assert!(z.is_zero());
assert_eq!(z, <F as Ring>::zero());
let mut sum = a.clone();
sum.add_assign(&b);
let mut want = a.mul(&b);
want.add_assign(&b.mul(&b));
assert_eq!(sum.mul(&b), want);
}
#[test]
fn addition_uses_the_lcm_not_the_product() {
let mut s = F::inv_factor(1, 0);
s.add_assign(&F::inv_factor(1, 0));
let (num, den) = s.parts();
assert_eq!(num.coeff(0, 0), r(2));
assert_eq!(num.len(), 1, "{num}");
let den: Vec<_> = den.collect();
assert_eq!(den, vec![(&(1, 0), &1)], "denominator must stay (1-q)^1");
}
#[test]
fn reduction_cancels_common_factors() {
let f = F::ratio(1, 0, 1, 0);
assert_eq!(f, <F as Ring>::one());
let (_, den) = f.parts();
assert_eq!(
den.count(),
0,
"the denominator must be gone, not merely equal"
);
let g = F::ratio(2, 0, 1, 0);
let (num, den) = g.parts();
assert_eq!(den.count(), 0);
assert_eq!(num.coeff(0, 0), r(1));
assert_eq!(num.coeff(1, 0), r(1));
}
#[test]
fn evaluation_and_its_poles() {
let f = F::inv_factor(1, 1); assert_eq!(f.eval(&r(2), &r(3)), Some(Rational::new(-1, 5)));
assert_eq!(f.eval(&r(1), &r(1)), None, "q t = 1 is a pole");
let g = F::ratio(1, 1, 1, 1); assert_eq!(g.eval(&r(1), &r(1)), Some(r(1)));
}
#[test]
fn division_by_integers_is_exact() {
let f = F::from_i64(6).mul(&F::inv_factor(1, 0));
let h = f.div_u128(4);
assert_eq!(h.eval(&r(0), &r(0)), Some(Rational::new(3, 2)));
}
}