use crate::field::{Fp, PrimeField};
use crate::hom::{Morphism, express_in_row_basis, hom, identity};
use crate::linalg::DenseMat;
use crate::module::Module;
fn flat_row(f: &Morphism, cols: usize) -> Vec<Fp> {
let mut row = Vec::with_capacity(cols);
for v in 0..f.source().algebra().quiver().num_vertices() {
let map = f.map_at(v);
for r in 0..map.rows() {
row.extend_from_slice(map.row(r));
}
}
row
}
fn express(flat: &DenseMat, f: &Morphism, field: &PrimeField) -> Vec<Fp> {
let mut vectors = DenseMat::zero(1, flat.cols());
for (c, &v) in flat_row(f, flat.cols()).iter().enumerate() {
vectors.set(0, c, v);
}
express_in_row_basis(flat, &vectors, field).row(0).to_vec()
}
pub struct EndoAlgebra {
module: Module,
field: PrimeField,
basis: Vec<Morphism>,
flat: DenseMat,
table: Vec<Vec<Fp>>,
one: Vec<Fp>,
radical: DenseMat,
complement: DenseMat,
full: DenseMat,
qtable: Vec<Vec<Fp>>,
qone: Vec<Fp>,
quotient_commutative: bool,
center: DenseMat,
fixed: DenseMat,
}
impl EndoAlgebra {
pub fn new(m: &Module) -> EndoAlgebra {
let field = m.field();
let basis = hom(m, m).expect("a module shares its own algebra");
let flat_cols: usize = m.dim_vector().iter().map(|&d| d * d).sum();
let mut flat = DenseMat::zero(basis.len(), flat_cols);
for (r, f) in basis.iter().enumerate() {
for (c, &v) in flat_row(f, flat_cols).iter().enumerate() {
flat.set(r, c, v);
}
}
let dim = basis.len();
let mut table = Vec::with_capacity(dim * dim);
for i in 0..dim {
for j in 0..dim {
let product = basis[i].then(&basis[j]).expect("endomorphisms compose");
table.push(express(&flat, &product, &field));
}
}
let one = express(&flat, &identity(m), &field);
let mut endo = EndoAlgebra {
module: m.clone(),
field,
basis,
flat,
table,
one,
radical: DenseMat::zero(0, dim),
complement: DenseMat::zero(0, dim),
full: DenseMat::zero(0, dim),
qtable: Vec::new(),
qone: Vec::new(),
quotient_commutative: true,
center: DenseMat::zero(0, 0),
fixed: DenseMat::zero(0, 0),
};
endo.radical = ronyai_radical(&endo);
endo.analyze_quotient();
endo
}
fn analyze_quotient(&mut self) {
let field = self.field;
let dim = self.dim();
let mut rows: Vec<Vec<Fp>> = (0..self.radical.rows())
.map(|r| self.radical.row(r).to_vec())
.collect();
let mut complement_rows: Vec<Vec<Fp>> = Vec::new();
for i in 0..dim {
let mut unit = vec![Fp::ZERO; dim];
unit[i] = Fp::ONE;
rows.push(unit.clone());
if DenseMat::from_rows(&rows).rank(&field) == rows.len() {
complement_rows.push(unit);
} else {
rows.pop();
}
}
self.complement = DenseMat::from_rows(&complement_rows);
let full_rows: Vec<Vec<Fp>> = (0..self.radical.rows())
.map(|r| self.radical.row(r).to_vec())
.chain(complement_rows.iter().cloned())
.collect();
self.full = if dim == 0 {
DenseMat::zero(0, 0)
} else {
DenseMat::from_rows(&full_rows)
};
let q = self.complement.rows();
let mut qtable = Vec::with_capacity(q * q);
for i in 0..q {
for j in 0..q {
let product = self.multiply(self.complement.row(i), self.complement.row(j));
qtable.push(self.reduce(&product));
}
}
self.qtable = qtable;
self.qone = self.reduce(&self.one);
self.quotient_commutative =
(0..q).all(|i| (0..i).all(|j| self.qtable[i * q + j] == self.qtable[j * q + i]));
let mut cond_rows = Vec::new();
for j in 0..q {
for comp in 0..q {
let mut row = vec![Fp::ZERO; q];
for (i, entry) in row.iter_mut().enumerate() {
*entry = field.sub(self.qtable[i * q + j][comp], self.qtable[j * q + i][comp]);
}
cond_rows.push(row);
}
}
self.center = if q == 0 {
DenseMat::zero(0, 0)
} else {
DenseMat::from_rows(&cond_rows).kernel_basis(&field)
};
let c = self.center.rows();
let mut frobenius = DenseMat::zero(c, c);
for r in 0..c {
let zp = self.qpow(self.center.row(r), field.modulus());
let mut as_matrix = DenseMat::zero(1, q);
for (col, &v) in zp.iter().enumerate() {
as_matrix.set(0, col, v);
}
let in_center = express_in_row_basis(&self.center, &as_matrix, &field);
for col in 0..c {
frobenius.set(r, col, in_center.get(0, col));
}
}
let mut shifted = frobenius;
for i in 0..c {
shifted.set(i, i, field.sub(shifted.get(i, i), Fp::ONE));
}
self.fixed = shifted
.transpose()
.kernel_basis(&field)
.mul(&self.center, &field);
}
fn reduce(&self, coords: &[Fp]) -> Vec<Fp> {
let mut as_matrix = DenseMat::zero(1, self.dim());
for (c, &v) in coords.iter().enumerate() {
as_matrix.set(0, c, v);
}
let expressed = express_in_row_basis(&self.full, &as_matrix, &self.field);
(self.radical.rows()..self.dim())
.map(|c| expressed.get(0, c))
.collect()
}
fn qmul(&self, a: &[Fp], b: &[Fp]) -> Vec<Fp> {
let q = self.complement.rows();
let mut out = vec![Fp::ZERO; q];
for (i, &ai) in a.iter().enumerate() {
if ai.is_zero() {
continue;
}
for (j, &bj) in b.iter().enumerate() {
if bj.is_zero() {
continue;
}
let c = self.field.mul(ai, bj);
for (k, out_k) in out.iter_mut().enumerate() {
let t = self.field.mul(c, self.qtable[i * q + j][k]);
*out_k = self.field.add(*out_k, t);
}
}
}
out
}
fn qpow(&self, a: &[Fp], mut exp: u64) -> Vec<Fp> {
let mut base = a.to_vec();
let mut acc = self.qone.clone();
while exp > 0 {
if exp & 1 == 1 {
acc = self.qmul(&acc, &base);
}
base = self.qmul(&base, &base);
exp >>= 1;
}
acc
}
#[inline]
pub fn module(&self) -> &Module {
&self.module
}
#[inline]
pub fn field(&self) -> PrimeField {
self.field
}
#[inline]
pub fn dim(&self) -> usize {
self.basis.len()
}
#[inline]
pub fn basis(&self) -> &[Morphism] {
&self.basis
}
#[inline]
pub fn one(&self) -> &[Fp] {
&self.one
}
pub fn coords(&self, f: &Morphism) -> Vec<Fp> {
assert!(
f.source().ptr_eq(&self.module) && f.target().ptr_eq(&self.module),
"coords: not an endomorphism of this algebra's module"
);
express(&self.flat, f, &self.field)
}
pub fn morphism(&self, coords: &[Fp]) -> Morphism {
assert_eq!(coords.len(), self.dim(), "morphism: coordinate count");
let mut maps: Vec<DenseMat> = self
.module
.dim_vector()
.iter()
.map(|&d| DenseMat::zero(d, d))
.collect();
for (k, &c) in coords.iter().enumerate() {
if c.is_zero() {
continue;
}
for (v, map) in maps.iter_mut().enumerate() {
let block = self.basis[k].map_at(v as u32);
for r in 0..map.rows() {
for j in 0..map.cols() {
let t = self.field.mul(c, block.get(r, j));
map.set(r, j, self.field.add(map.get(r, j), t));
}
}
}
}
Morphism::new(&self.module, &self.module, maps)
.expect("linear combinations of endomorphisms are endomorphisms")
}
pub fn multiply(&self, a: &[Fp], b: &[Fp]) -> Vec<Fp> {
let dim = self.dim();
assert!(
a.len() == dim && b.len() == dim,
"multiply: coordinate count"
);
let mut out = vec![Fp::ZERO; dim];
for (i, &ai) in a.iter().enumerate() {
if ai.is_zero() {
continue;
}
for (j, &bj) in b.iter().enumerate() {
if bj.is_zero() {
continue;
}
let c = self.field.mul(ai, bj);
for (k, out_k) in out.iter_mut().enumerate() {
let t = self.field.mul(c, self.table[i * dim + j][k]);
*out_k = self.field.add(*out_k, t);
}
}
}
out
}
#[inline]
pub fn radical_basis(&self) -> &DenseMat {
&self.radical
}
#[inline]
pub fn radical_dim(&self) -> usize {
self.radical.rows()
}
pub fn in_radical(&self, coords: &[Fp]) -> bool {
assert_eq!(coords.len(), self.dim(), "in_radical: coordinate count");
let mut stacked = DenseMat::zero(self.radical.rows() + 1, self.dim());
for r in 0..self.radical.rows() {
for c in 0..self.dim() {
stacked.set(r, c, self.radical.get(r, c));
}
}
for (c, &v) in coords.iter().enumerate() {
stacked.set(self.radical.rows(), c, v);
}
stacked.rank(&self.field) == self.radical.rows()
}
#[inline]
pub fn quotient_is_commutative(&self) -> bool {
self.quotient_commutative
}
#[inline]
pub fn semisimple_factor_count(&self) -> usize {
self.fixed.rows()
}
pub fn is_local(&self) -> bool {
self.dim() > 0 && self.quotient_commutative && self.semisimple_factor_count() == 1
}
pub(crate) fn split_idempotent(&self, rng: &mut SplitMix64) -> Option<Vec<Fp>> {
if self.semisimple_factor_count() < 2 {
return None;
}
let field = self.field;
let q = self.complement.rows();
let f = (0..self.fixed.rows())
.map(|r| self.fixed.row(r))
.find(|f| {
let mut stacked = DenseMat::zero(2, q);
for c in 0..q {
stacked.set(0, c, self.qone[c]);
stacked.set(1, c, f[c]);
}
stacked.rank(&field) == 2
})?;
let minpoly = self.quotient_min_poly(f);
let roots = split_squarefree_roots(&minpoly, &field, rng)?;
let mut projector = vec![
field.inv(
roots[1..]
.iter()
.fold(Fp::ONE, |acc, &b| field.mul(acc, field.sub(roots[0], b))),
),
];
for &b in &roots[1..] {
let mut next = vec![Fp::ZERO; projector.len() + 1];
for (k, &c) in projector.iter().enumerate() {
next[k + 1] = field.add(next[k + 1], c);
next[k] = field.sub(next[k], field.mul(b, c));
}
projector = next;
}
let mut ebar = vec![Fp::ZERO; q];
for &c in projector.iter().rev() {
ebar = self.qmul(&ebar, f);
for (k, e_k) in ebar.iter_mut().enumerate() {
*e_k = field.add(*e_k, field.mul(c, self.qone[k]));
}
}
if self.qmul(&ebar, &ebar) != ebar || ebar.iter().all(|c| c.is_zero()) || ebar == self.qone
{
return None;
}
let mut e = vec![Fp::ZERO; self.dim()];
for (i, &c) in ebar.iter().enumerate() {
for (k, e_k) in e.iter_mut().enumerate() {
*e_k = field.add(*e_k, field.mul(c, self.complement.get(i, k)));
}
}
for _ in 0..64 {
let square = self.multiply(&e, &e);
if square == e {
if e.iter().all(|c| c.is_zero()) || e == self.one {
return None;
}
return Some(e);
}
let cube = self.multiply(&square, &e);
for (k, e_k) in e.iter_mut().enumerate() {
let three = field.add(field.add(square[k], square[k]), square[k]);
let two = field.add(cube[k], cube[k]);
*e_k = field.sub(three, two);
}
}
None
}
pub(crate) fn singular_element(&self, rng: &mut SplitMix64, attempts: u32) -> Option<Vec<Fp>> {
let field = self.field;
let p = field.modulus();
let q = self.complement.rows();
if q == 0 {
return None;
}
for _ in 0..attempts {
let abar: Vec<Fp> = (0..q).map(|_| field.elem(rng.below(p) as i64)).collect();
let minpoly = self.quotient_min_poly(&abar);
if minpoly.len() < 3 {
continue;
}
let Some((g, _)) = coprime_split(&minpoly, &field, rng) else {
continue;
};
let value = self.qpoly_eval(&g, &abar);
let mut lifted = vec![Fp::ZERO; self.dim()];
for (i, &c) in value.iter().enumerate() {
for (k, out) in lifted.iter_mut().enumerate() {
*out = field.add(*out, field.mul(c, self.complement.get(i, k)));
}
}
return Some(lifted);
}
None
}
fn qpoly_eval(&self, poly: &[Fp], f: &[Fp]) -> Vec<Fp> {
let field = self.field;
let mut acc = vec![Fp::ZERO; self.complement.rows()];
for &c in poly.iter().rev() {
acc = self.qmul(&acc, f);
for (k, out) in acc.iter_mut().enumerate() {
*out = field.add(*out, field.mul(c, self.qone[k]));
}
}
acc
}
fn quotient_min_poly(&self, f: &[Fp]) -> Vec<Fp> {
let mut powers = vec![self.qone.clone()];
loop {
let next = self.qmul(powers.last().expect("powers start at f⁰"), f);
let stack = DenseMat::from_rows(&powers);
if let Some(x) = stack.transpose().solve(&next, &self.field) {
let mut minpoly: Vec<Fp> = x.iter().map(|&c| self.field.neg(c)).collect();
minpoly.push(Fp::ONE);
return minpoly;
}
powers.push(next);
}
}
}
pub(crate) struct SplitMix64(pub(crate) u64);
impl SplitMix64 {
pub(crate) fn next_u64(&mut self) -> u64 {
self.0 = self.0.wrapping_add(0x9e37_79b9_7f4a_7c15);
let mut z = self.0;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
z ^ (z >> 31)
}
pub(crate) fn below(&mut self, n: u64) -> u64 {
self.next_u64() % n
}
}
fn poly_trim(mut a: Vec<Fp>) -> Vec<Fp> {
while a.last().is_some_and(|c| c.is_zero()) {
a.pop();
}
a
}
fn poly_eval(a: &[Fp], x: Fp, field: &PrimeField) -> Fp {
let mut acc = Fp::ZERO;
for &c in a.iter().rev() {
acc = field.add(field.mul(acc, x), c);
}
acc
}
fn poly_rem(a: &[Fp], b: &[Fp], field: &PrimeField) -> Vec<Fp> {
let mut r = a.to_vec();
let db = b.len() - 1;
while r.len() > db {
let lead = *r.last().expect("r is longer than b");
let shift = r.len() - 1 - db;
if !lead.is_zero() {
for (i, &c) in b.iter().enumerate() {
let t = field.mul(lead, c);
r[shift + i] = field.sub(r[shift + i], t);
}
}
r.pop();
}
poly_trim(r)
}
fn poly_quotient(a: &[Fp], b: &[Fp], field: &PrimeField) -> Vec<Fp> {
let db = b.len() - 1;
let mut r = a.to_vec();
let mut quot = vec![Fp::ZERO; a.len() - db];
while r.len() > db {
let lead = *r.last().expect("r is longer than b");
let shift = r.len() - 1 - db;
quot[shift] = lead;
if !lead.is_zero() {
for (i, &c) in b.iter().enumerate() {
let t = field.mul(lead, c);
r[shift + i] = field.sub(r[shift + i], t);
}
}
r.pop();
}
quot
}
fn poly_gcd(a: &[Fp], b: &[Fp], field: &PrimeField) -> Vec<Fp> {
let (mut x, mut y) = (poly_trim(a.to_vec()), poly_trim(b.to_vec()));
while !y.is_empty() {
let lead_inv = field.inv(*y.last().expect("y is nonzero"));
let monic: Vec<Fp> = y.iter().map(|&c| field.mul(c, lead_inv)).collect();
y = poly_rem(&x, &monic, field);
x = monic;
}
let lead_inv = field.inv(*x.last().expect("gcd of nonzero inputs is nonzero"));
x.iter().map(|&c| field.mul(c, lead_inv)).collect()
}
fn poly_powmod(base: &[Fp], mut exp: u64, modulus: &[Fp], field: &PrimeField) -> Vec<Fp> {
let mut b = poly_rem(base, modulus, field);
let mut acc = vec![Fp::ONE];
while exp > 0 {
if exp & 1 == 1 {
acc = poly_rem(&poly_mul(&acc, &b, field), modulus, field);
}
b = poly_rem(&poly_mul(&b, &b, field), modulus, field);
exp >>= 1;
}
acc
}
fn poly_derivative(a: &[Fp], field: &PrimeField) -> Vec<Fp> {
let mut out = Vec::with_capacity(a.len().saturating_sub(1));
for (k, &c) in a.iter().enumerate().skip(1) {
out.push(field.mul(c, field.elem(k as i64)));
}
poly_trim(out)
}
fn poly_mulmod(a: &[Fp], b: &[Fp], modulus: &[Fp], field: &PrimeField) -> Vec<Fp> {
poly_rem(&poly_mul(a, b, field), modulus, field)
}
fn coprime_split(
poly: &[Fp],
field: &PrimeField,
rng: &mut SplitMix64,
) -> Option<(Vec<Fp>, Vec<Fp>)> {
let n = poly.len() - 1;
if n < 2 {
return None;
}
let derivative = poly_derivative(poly, field);
if derivative.is_empty() || poly_gcd(poly, &derivative, field).len() > 1 {
return None;
}
let p = field.modulus();
let mut frobenius = DenseMat::zero(n, n);
let step = poly_powmod(&[Fp::ZERO, Fp::ONE], p, poly, field);
let mut current = vec![Fp::ONE];
for i in 0..n {
for (j, &c) in current.iter().enumerate() {
frobenius.set(i, j, c);
}
current = poly_mulmod(¤t, &step, poly, field);
}
for i in 0..n {
frobenius.set(i, i, field.sub(frobenius.get(i, i), Fp::ONE));
}
let fixed = frobenius.transpose().kernel_basis(field);
let candidate = (0..fixed.rows())
.map(|r| poly_trim(fixed.row(r).to_vec()))
.find(|v| v.len() > 1)?;
let proper = |g: &Vec<Fp>| g.len() > 1 && g.len() <= n;
if p <= 4096 {
for s in 0..p as i64 {
let mut shifted = candidate.clone();
shifted[0] = field.sub(shifted[0], field.elem(s));
let g = poly_gcd(poly, &poly_trim(shifted), field);
if proper(&g) {
return Some((g.clone(), poly_quotient(poly, &g, field)));
}
}
return None;
}
for _ in 0..64 {
let mut shifted = candidate.clone();
shifted[0] = field.sub(shifted[0], field.elem(rng.below(p) as i64));
let shifted = poly_trim(shifted);
let g = poly_gcd(poly, &shifted, field);
if proper(&g) {
return Some((g.clone(), poly_quotient(poly, &g, field)));
}
let mut powered = poly_powmod(&shifted, (p - 1) / 2, poly, field);
if powered.is_empty() {
powered.push(Fp::ZERO);
}
powered[0] = field.sub(powered[0], Fp::ONE);
let g = poly_gcd(poly, &poly_trim(powered), field);
if proper(&g) {
return Some((g.clone(), poly_quotient(poly, &g, field)));
}
}
None
}
fn split_squarefree_roots(
poly: &[Fp],
field: &PrimeField,
rng: &mut SplitMix64,
) -> Option<Vec<Fp>> {
let degree = poly.len() - 1;
let p = field.modulus();
if p <= 4096 {
let roots: Vec<Fp> = (0..p as i64)
.map(|a| field.elem(a))
.filter(|&a| poly_eval(poly, a, field).is_zero())
.collect();
return (roots.len() == degree).then_some(roots);
}
if degree == 0 {
return Some(Vec::new());
}
if degree == 1 {
return Some(vec![field.neg(poly[0])]);
}
for _ in 0..64 {
let delta = field.elem(rng.below(p) as i64);
let base = vec![delta, Fp::ONE];
let mut shifted = poly_powmod(&base, (p - 1) / 2, poly, field);
if shifted.is_empty() {
shifted.push(Fp::ZERO);
}
shifted[0] = field.sub(shifted[0], Fp::ONE);
let shifted = poly_trim(shifted);
if shifted.is_empty() {
continue;
}
let g = poly_gcd(poly, &shifted, field);
if g.len() - 1 == 0 || g.len() - 1 == degree {
continue;
}
let h = poly_quotient(poly, &g, field);
let mut roots = split_squarefree_roots(&g, field, rng)?;
roots.extend(split_squarefree_roots(&h, field, rng)?);
return Some(roots);
}
None
}
fn char_poly(a: &DenseMat, field: &PrimeField) -> Vec<Fp> {
let n = a.rows();
assert_eq!(a.cols(), n, "char_poly: matrix is not square");
let mut h = a.clone();
for col in 0..n.saturating_sub(2) {
let Some(t) = ((col + 1)..n).find(|&r| !h.get(r, col).is_zero()) else {
continue;
};
if t != col + 1 {
for c in 0..n {
let (x, y) = (h.get(t, c), h.get(col + 1, c));
h.set(t, c, y);
h.set(col + 1, c, x);
}
for r in 0..n {
let (x, y) = (h.get(r, t), h.get(r, col + 1));
h.set(r, t, y);
h.set(r, col + 1, x);
}
}
let pivinv = field.inv(h.get(col + 1, col));
for i in (col + 2)..n {
let u = field.mul(h.get(i, col), pivinv);
if u.is_zero() {
continue;
}
for c in 0..n {
let t = field.mul(u, h.get(col + 1, c));
h.set(i, c, field.sub(h.get(i, c), t));
}
for r in 0..n {
let t = field.mul(u, h.get(r, i));
h.set(r, col + 1, field.add(h.get(r, col + 1), t));
}
}
}
let mut polys: Vec<Vec<Fp>> = Vec::with_capacity(n + 1);
polys.push(vec![Fp::ONE]);
for m in 1..=n {
let mut pm = vec![Fp::ZERO; m + 1];
for (k, &c) in polys[m - 1].iter().enumerate() {
pm[k + 1] = field.add(pm[k + 1], c);
let t = field.mul(h.get(m - 1, m - 1), c);
pm[k] = field.sub(pm[k], t);
}
let mut sub = Fp::ONE;
for i in (1..m).rev() {
sub = field.mul(sub, h.get(i, i - 1));
if sub.is_zero() {
break;
}
let coeff = field.mul(h.get(i - 1, m - 1), sub);
if coeff.is_zero() {
continue;
}
for (k, &c) in polys[i - 1].iter().enumerate() {
pm[k] = field.sub(pm[k], field.mul(coeff, c));
}
}
polys.push(pm);
}
polys.pop().expect("polys holds p_0..p_n")
}
fn poly_mul(a: &[Fp], b: &[Fp], field: &PrimeField) -> Vec<Fp> {
let mut out = vec![Fp::ZERO; a.len() + b.len() - 1];
for (i, &x) in a.iter().enumerate() {
if x.is_zero() {
continue;
}
for (j, &y) in b.iter().enumerate() {
let t = field.mul(x, y);
out[i + j] = field.add(out[i + j], t);
}
}
out
}
fn morphism_char_poly(f: &Morphism, field: &PrimeField) -> Vec<Fp> {
let mut acc = vec![Fp::ONE];
for v in 0..f.source().algebra().quiver().num_vertices() {
acc = poly_mul(&acc, &char_poly(f.map_at(v), field), field);
}
acc
}
fn ronyai_radical(e: &EndoAlgebra) -> DenseMat {
let field = e.field;
let n = e.module.total_dim();
if e.dim() == 0 {
return DenseMat::zero(0, 0);
}
let mut cur = DenseMat::identity(e.dim());
let p = field.modulus();
let mut power = 1u64;
loop {
if cur.rows() == 0 {
break;
}
let gens: Vec<Morphism> = (0..cur.rows()).map(|r| e.morphism(cur.row(r))).collect();
let mut cond = DenseMat::zero(gens.len(), gens.len());
for (j, gj) in gens.iter().enumerate() {
for (k, gk) in gens.iter().enumerate() {
let product = gj.then(gk).expect("endomorphisms compose");
let cp = morphism_char_poly(&product, &field);
cond.set(k, j, cp[n - power as usize]);
}
}
cur = cond.kernel_basis(&field).mul(&cur, &field);
if power * p > n as u64 {
break;
}
power *= p;
}
cur.row_space_basis(&field)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{
an_with_relations, cyclic_nakayama, dual_numbers, kronecker, linear_an,
radical_square_zero_cycle, truncated_poly,
};
use crate::module::direct_sum;
fn f5() -> PrimeField {
PrimeField::new(5).unwrap()
}
fn unit(dim: usize, k: usize, field: &PrimeField) -> Vec<Fp> {
let mut v = vec![field.zero(); dim];
v[k] = field.one();
v
}
#[test]
fn end_of_a_simple_is_one_dimensional() {
let a = linear_an(3, f5());
let e = EndoAlgebra::new(&Module::simple(&a, 0));
assert_eq!(e.dim(), 1);
assert_eq!(e.multiply(e.one(), e.one()), e.one().to_vec());
}
#[test]
fn field_is_the_field_of_the_module() {
let a = linear_an(3, f5());
let e = EndoAlgebra::new(&Module::simple(&a, 0));
assert_eq!(e.field(), f5());
}
#[test]
fn end_of_the_zero_module_is_zero_dimensional() {
let a = linear_an(3, f5());
let e = EndoAlgebra::new(&Module::zero(&a));
assert_eq!(e.dim(), 0);
assert!(e.one().is_empty());
}
#[test]
fn end_of_the_dual_numbers_regular_module_has_dimension_2() {
let a = dual_numbers(f5());
let e = EndoAlgebra::new(&Module::projective(&a, 0));
assert_eq!(e.dim(), 2);
}
#[test]
fn structure_constants_reproduce_composition() {
let field = f5();
let a = linear_an(2, field);
let p0 = Module::projective(&a, 0);
let p1 = Module::projective(&a, 1);
let (sum, _, _) = direct_sum(&[&p0, &p1]);
let e = EndoAlgebra::new(&sum);
assert_eq!(e.dim(), 3);
for i in 0..e.dim() {
for j in 0..e.dim() {
let product = e.basis()[i].then(&e.basis()[j]).unwrap();
assert_eq!(
e.multiply(&unit(e.dim(), i, &field), &unit(e.dim(), j, &field)),
e.coords(&product),
"b_{i} · b_{j}"
);
}
}
}
#[test]
fn one_is_neutral_and_multiplication_is_associative_on_basis_triples() {
let field = f5();
let a = dual_numbers(field);
let p = Module::projective(&a, 0);
let (sum, _, _) = direct_sum(&[&p, &p]);
let e = EndoAlgebra::new(&sum);
let units: Vec<Vec<Fp>> = (0..e.dim()).map(|k| unit(e.dim(), k, &field)).collect();
for x in &units {
assert_eq!(e.multiply(e.one(), x), *x);
assert_eq!(e.multiply(x, e.one()), *x);
for y in &units {
for z in &units {
assert_eq!(
e.multiply(&e.multiply(x, y), z),
e.multiply(x, &e.multiply(y, z))
);
}
}
}
}
struct XorShift64(u64);
impl XorShift64 {
fn next_u64(&mut self) -> u64 {
let mut x = self.0;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
self.0 = x;
x
}
fn below(&mut self, n: u64) -> u64 {
self.next_u64() % n
}
}
fn fields() -> [PrimeField; 3] {
[
PrimeField::new(2).unwrap(),
PrimeField::new(3).unwrap(),
PrimeField::new(5).unwrap(),
]
}
#[test]
fn char_poly_of_a_companion_matrix_recovers_its_polynomial() {
let field = f5();
let rows = vec![
vec![field.elem(0), field.elem(1), field.elem(0)],
vec![field.elem(0), field.elem(0), field.elem(1)],
vec![field.elem(-4), field.elem(-3), field.elem(-2)],
];
assert_eq!(
char_poly(&DenseMat::from_rows(&rows), &field),
vec![field.elem(4), field.elem(3), field.elem(2), field.elem(1)]
);
assert_eq!(char_poly(&DenseMat::zero(0, 0), &field), vec![field.one()]);
}
#[test]
fn char_poly_satisfies_cayley_hamilton_on_random_matrices() {
let mut rng = XorShift64(0x0005_eed0_c4a1_e401);
for field in fields() {
let p = field.modulus();
for _ in 0..25 {
let n = 1 + rng.below(6) as usize;
let mut a = DenseMat::zero(n, n);
for r in 0..n {
for c in 0..n {
a.set(r, c, field.elem(rng.below(p) as i64));
}
}
let cp = char_poly(&a, &field);
let mut acc = DenseMat::zero(n, n);
for &coeff in cp.iter().rev() {
acc = acc.mul(&a, &field);
for i in 0..n {
acc.set(i, i, field.add(acc.get(i, i), coeff));
}
}
assert_eq!(acc, DenseMat::zero(n, n), "p = {p}, n = {n}");
}
}
}
#[test]
fn radical_of_end_of_a_simple_is_zero() {
for field in fields() {
let a = linear_an(3, field);
let e = EndoAlgebra::new(&Module::simple(&a, 1));
assert_eq!(e.radical_dim(), 0, "p = {}", field.modulus());
}
}
#[test]
fn radical_of_end_of_indecomposable_projectives_matches_path_counts() {
for field in fields() {
for algebra in [
linear_an(3, field),
kronecker(2, field),
cyclic_nakayama(&[3, 3, 3], field).unwrap(),
radical_square_zero_cycle(3, field),
] {
for v in 0..algebra.quiver().num_vertices() {
let e = EndoAlgebra::new(&Module::projective(&algebra, v));
assert_eq!(e.dim(), 1, "End P_{v} over F_{}", field.modulus());
assert_eq!(e.radical_dim(), 0, "rad End P_{v}");
}
}
}
}
#[test]
fn radical_of_end_of_truncated_polynomial_regular_modules_has_codimension_1() {
for field in fields() {
for n in 2..=4 {
let a = truncated_poly(n, field).unwrap();
let e = EndoAlgebra::new(&Module::projective(&a, 0));
assert_eq!(e.dim(), n, "p = {}", field.modulus());
assert_eq!(e.radical_dim(), n - 1, "p = {}", field.modulus());
}
}
}
#[test]
fn radical_of_end_of_a_truncated_polynomial_quotient_module_is_known() {
for field in fields() {
let a = truncated_poly(3, field).unwrap();
let x = DenseMat::from_rows(&[
vec![field.zero(), field.one()],
vec![field.zero(), field.zero()],
]);
let m = Module::new(a, vec![2], vec![x]).unwrap();
let e = EndoAlgebra::new(&m);
assert_eq!(e.dim(), 2);
assert_eq!(e.radical_dim(), 1);
}
}
#[test]
fn radical_of_end_of_a_sum_of_distinct_simples_is_zero() {
for field in fields() {
let a = linear_an(3, field);
let s0 = Module::simple(&a, 0);
let s1 = Module::simple(&a, 1);
let (sum, _, _) = direct_sum(&[&s0, &s1]);
let e = EndoAlgebra::new(&sum);
assert_eq!(e.dim(), 2);
assert_eq!(e.radical_dim(), 0);
}
}
#[test]
fn radical_of_a_2x2_matrix_algebra_is_zero() {
for field in fields() {
let a = linear_an(3, field);
let s = Module::simple(&a, 0);
let (sum, _, _) = direct_sum(&[&s, &s]);
let e = EndoAlgebra::new(&sum);
assert_eq!(e.dim(), 4);
assert_eq!(e.radical_dim(), 0, "p = {}", field.modulus());
}
}
#[test]
fn radical_of_end_of_a_doubled_dual_numbers_module_has_dimension_4() {
for field in fields() {
let a = dual_numbers(field);
let p = Module::projective(&a, 0);
let (sum, _, _) = direct_sum(&[&p, &p]);
let e = EndoAlgebra::new(&sum);
assert_eq!(e.dim(), 8);
assert_eq!(e.radical_dim(), 4, "p = {}", field.modulus());
}
}
#[test]
fn radical_elements_are_nilpotent_and_the_radical_is_an_ideal() {
for field in fields() {
let a = an_with_relations(3, &[(0, 2)], field).unwrap();
let p0 = Module::projective(&a, 0);
let s0 = Module::simple(&a, 0);
let (sum, _, _) = direct_sum(&[&p0, &s0]);
let e = EndoAlgebra::new(&sum);
assert!(e.radical_dim() > 0);
for r in 0..e.radical_dim() {
let x = e.morphism(e.radical_basis().row(r));
let mut power = x.clone();
for _ in 1..sum.total_dim() {
power = power.then(&x).unwrap();
}
assert!(power.is_zero(), "radical element is nilpotent");
for k in 0..e.dim() {
let b = &e.basis()[k];
assert!(e.in_radical(&e.coords(&b.then(&x).unwrap())));
assert!(e.in_radical(&e.coords(&x.then(b).unwrap())));
}
}
assert!(!e.in_radical(e.one()));
}
}
#[test]
fn end_of_a_simple_and_of_uniserial_projectives_is_local() {
for field in fields() {
let a3 = linear_an(3, field);
assert!(EndoAlgebra::new(&Module::simple(&a3, 0)).is_local());
assert!(EndoAlgebra::new(&Module::projective(&a3, 0)).is_local());
for n in 2..=4 {
let a = truncated_poly(n, field).unwrap();
let e = EndoAlgebra::new(&Module::projective(&a, 0));
assert!(e.is_local(), "k[x]/(x^{n}) over F_{}", field.modulus());
assert!(e.quotient_is_commutative());
assert_eq!(e.semisimple_factor_count(), 1);
}
}
}
#[test]
fn end_of_a_sum_of_distinct_simples_has_two_commutative_factors() {
for field in fields() {
let a = linear_an(3, field);
let s0 = Module::simple(&a, 0);
let s1 = Module::simple(&a, 1);
let (sum, _, _) = direct_sum(&[&s0, &s1]);
let e = EndoAlgebra::new(&sum);
assert!(e.quotient_is_commutative());
assert_eq!(e.semisimple_factor_count(), 2);
assert!(!e.is_local());
}
}
#[test]
fn a_2x2_matrix_algebra_is_semisimple_but_neither_commutative_nor_local() {
for field in fields() {
let a = linear_an(3, field);
let s = Module::simple(&a, 0);
let (sum, _, _) = direct_sum(&[&s, &s]);
let e = EndoAlgebra::new(&sum);
assert_eq!(e.radical_dim(), 0);
assert!(!e.quotient_is_commutative());
assert_eq!(e.semisimple_factor_count(), 1);
assert!(!e.is_local());
}
}
#[test]
fn end_of_p0_plus_s0_has_a_radical_and_two_factors() {
for field in fields() {
let a = linear_an(3, field);
let p0 = Module::projective(&a, 0);
let s0 = Module::simple(&a, 0);
let (sum, _, _) = direct_sum(&[&p0, &s0]);
let e = EndoAlgebra::new(&sum);
assert_eq!(e.dim(), 3);
assert_eq!(e.radical_dim(), 1);
assert!(e.quotient_is_commutative());
assert_eq!(e.semisimple_factor_count(), 2);
assert!(!e.is_local());
}
}
#[test]
fn the_zero_endomorphism_algebra_is_not_local() {
let a = linear_an(3, f5());
let e = EndoAlgebra::new(&Module::zero(&a));
assert!(!e.is_local());
assert_eq!(e.semisimple_factor_count(), 0);
}
#[test]
fn split_idempotent_is_exact_nontrivial_and_deterministic() {
for field in fields() {
let a = linear_an(3, field);
let p0 = Module::projective(&a, 0);
let s0 = Module::simple(&a, 0);
let (sum, _, _) = direct_sum(&[&p0, &s0]);
let e = EndoAlgebra::new(&sum);
let first = e.split_idempotent(&mut SplitMix64(7)).unwrap();
let again = e.split_idempotent(&mut SplitMix64(7)).unwrap();
assert_eq!(first, again, "seeded run is reproducible");
assert_eq!(e.multiply(&first, &first), first);
assert!(first.iter().any(|c| !c.is_zero()));
assert_ne!(first, e.one().to_vec());
}
}
#[test]
fn singular_element_is_a_non_unit_that_is_not_nilpotent() {
for field in [f5(), PrimeField::new(32003).unwrap()] {
let a = dual_numbers(field);
let p = Module::projective(&a, 0);
let (sum, _, _) = direct_sum(&[&p, &p]);
let e = EndoAlgebra::new(&sum);
assert_eq!(e.semisimple_factor_count(), 1);
assert!(e.split_idempotent(&mut SplitMix64(7)).is_none());
let coords = e
.singular_element(&mut SplitMix64(7), 64)
.expect("M_2(k) contains non-units that are not nilpotent");
let phi = e.morphism(&coords);
assert!(
!phi.is_isomorphism(),
"a unit gives the trivial Fitting split"
);
let mut power = phi.clone();
for _ in 0..sum.total_dim() {
power = power.then(&phi).expect("endomorphisms compose");
}
assert!(
!power.is_zero(),
"a nilpotent gives the trivial Fitting split"
);
let again = e.singular_element(&mut SplitMix64(7), 64).unwrap();
assert_eq!(coords, again, "seeded run is reproducible");
}
}
#[test]
fn singular_element_is_none_for_a_local_algebra() {
for field in fields() {
let a = dual_numbers(field);
let p = Module::projective(&a, 0);
let e = EndoAlgebra::new(&p);
assert!(e.is_local());
assert!(e.singular_element(&mut SplitMix64(11), 64).is_none());
}
}
#[test]
fn split_idempotent_is_none_for_local_and_single_factor_algebras() {
let field = f5();
let a = linear_an(3, field);
let p0 = Module::projective(&a, 0);
assert!(
EndoAlgebra::new(&p0)
.split_idempotent(&mut SplitMix64(7))
.is_none()
);
let s = Module::simple(&a, 0);
let (sum, _, _) = direct_sum(&[&s, &s]);
assert!(
EndoAlgebra::new(&sum)
.split_idempotent(&mut SplitMix64(7))
.is_none()
);
}
#[test]
fn split_idempotent_works_over_a_large_prime_via_cantor_zassenhaus() {
let field = PrimeField::new(1_000_003).unwrap();
let a = linear_an(2, field);
let s0 = Module::simple(&a, 0);
let s1 = Module::simple(&a, 1);
let (sum, _, _) = direct_sum(&[&s0, &s1]);
let e = EndoAlgebra::new(&sum);
assert_eq!(e.semisimple_factor_count(), 2);
let idem = e.split_idempotent(&mut SplitMix64(7)).unwrap();
assert_eq!(e.multiply(&idem, &idem), idem);
assert!(idem.iter().any(|c| !c.is_zero()));
assert_ne!(idem, e.one().to_vec());
}
#[test]
fn split_squarefree_roots_recovers_all_roots() {
let field = f5();
let poly = vec![field.elem(3), field.elem(-4), field.one()];
let mut roots = split_squarefree_roots(&poly, &field, &mut SplitMix64(1)).unwrap();
roots.sort_by_key(|r| r.raw());
assert_eq!(roots, vec![field.elem(1), field.elem(3)]);
let big = PrimeField::new(1_000_003).unwrap();
let c0 = big.mul(big.elem(2), big.elem(123_456));
let c1 = big.neg(big.add(big.elem(2), big.elem(123_456)));
let mut roots =
split_squarefree_roots(&[c0, c1, big.one()], &big, &mut SplitMix64(1)).unwrap();
roots.sort_by_key(|r| r.raw());
assert_eq!(roots, vec![big.elem(2), big.elem(123_456)]);
}
#[test]
fn coords_and_morphism_round_trip() {
let field = f5();
let a = linear_an(2, field);
let p0 = Module::projective(&a, 0);
let p1 = Module::projective(&a, 1);
let (sum, _, _) = direct_sum(&[&p0, &p1]);
let e = EndoAlgebra::new(&sum);
let coords: Vec<Fp> = (0..e.dim() as i64).map(|i| field.elem(i + 1)).collect();
assert_eq!(e.coords(&e.morphism(&coords)), coords);
assert_eq!(e.coords(&identity(&sum)), e.one().to_vec());
}
fn kronecker_f4_module() -> Module {
let field = PrimeField::new(2).unwrap();
let a = kronecker(2, field);
let id = DenseMat::from_rows(&[
vec![field.one(), field.zero()],
vec![field.zero(), field.one()],
]);
let c = DenseMat::from_rows(&[
vec![field.zero(), field.one()],
vec![field.one(), field.one()],
]);
Module::new(a, vec![2, 2], vec![id, c]).unwrap()
}
#[test]
fn end_of_the_f4_kronecker_module_is_the_field_with_four_elements() {
let e = EndoAlgebra::new(&kronecker_f4_module());
assert_eq!(e.dim(), 2);
assert_eq!(e.radical_dim(), 0);
assert_eq!(e.semisimple_factor_count(), 1);
assert!(e.quotient_is_commutative());
assert!(e.is_local());
}
#[test]
fn m2_of_f4_has_one_factor_but_is_not_local_and_yields_no_idempotent() {
let m = kronecker_f4_module();
let (sum, _, _) = direct_sum(&[&m, &m]);
let e = EndoAlgebra::new(&sum);
assert_eq!(e.dim(), 8);
assert_eq!(e.radical_dim(), 0);
assert_eq!(e.semisimple_factor_count(), 1);
assert!(!e.quotient_is_commutative());
assert!(!e.is_local());
assert_eq!(e.split_idempotent(&mut SplitMix64(7)), None);
}
}