algebraeon_rings/quaternion_algebra/
mod.rs

1use crate::structure::*;
2use algebraeon_nzq::Natural;
3use algebraeon_sets::structure::*;
4use std::{borrow::Cow, fmt};
5
6pub mod quaternion_orders;
7
8// When char != 2
9//  has a basis of 1, i, j, ij
10//  and is such that i^2=a and j^2=b and ij = -ji
11//  for some non-zero a and b
12//
13// When char == 2
14//  has basis 1, i, j, k
15//  and is such that i^2+i=a and j^2=b and k=ij=j(i+1)
16//  for some a and some non-zero b
17#[derive(Debug, Clone)]
18pub struct QuaternionAlgebraStructure<Field: FieldSignature> {
19    base: Field,
20    is_char_2: bool,
21    a: Field::Set,
22    b: Field::Set,
23}
24
25impl<Field: FieldSignature + CharacteristicSignature> QuaternionAlgebraStructure<Field> {
26    pub fn base_field(&self) -> &Field {
27        &self.base
28    }
29
30    pub fn new(base: Field, a: Field::Set, b: Field::Set) -> Self {
31        let is_char_2 = base.characteristic() == Natural::TWO;
32        Self {
33            base,
34            is_char_2,
35            a,
36            b,
37        }
38    }
39}
40
41impl<Field: FieldSignature + ToStringSignature + fmt::Display> fmt::Display
42    for QuaternionAlgebraStructure<Field>
43{
44    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
45        write!(
46            f,
47            "Quaternion Algebra ({}, {}) over base field {}",
48            self.base.to_string(&self.a),
49            self.base.to_string(&self.b),
50            self.base
51        )
52    }
53}
54
55#[derive(Debug, Clone, Copy, PartialEq, Eq, CanonicalStructure)]
56#[canonical_structure(eq)]
57pub enum QuaternionAlgebraBasis {
58    R,
59    I,
60    J,
61    K,
62}
63
64impl CountableSetSignature for QuaternionAlgebraBasisCanonicalStructure {
65    fn generate_all_elements(&self) -> impl Iterator<Item = Self::Set> + Clone {
66        vec![
67            QuaternionAlgebraBasis::R,
68            QuaternionAlgebraBasis::I,
69            QuaternionAlgebraBasis::J,
70            QuaternionAlgebraBasis::K,
71        ]
72        .into_iter()
73    }
74}
75
76impl FiniteSetSignature for QuaternionAlgebraBasisCanonicalStructure {
77    fn size(&self) -> usize {
78        4
79    }
80}
81
82#[derive(Debug, Clone)]
83pub struct QuaternionAlgebraElement<Set> {
84    // represent x + yi + zj + wk
85    x: Set,
86    y: Set,
87    z: Set,
88    w: Set,
89}
90
91impl<Field: FieldSignature> PartialEq for QuaternionAlgebraStructure<Field> {
92    fn eq(&self, other: &Self) -> bool {
93        self.base == other.base
94            && self.base.equal(&self.a, &other.a)
95            && self.base.equal(&self.b, &other.b)
96    }
97}
98
99impl<Field: FieldSignature> Eq for QuaternionAlgebraStructure<Field> {}
100
101impl<Field: FieldSignature> EqSignature for QuaternionAlgebraStructure<Field> {
102    fn equal(&self, a: &Self::Set, b: &Self::Set) -> bool {
103        self.base.equal(&a.x, &b.x)
104            && self.base.equal(&a.y, &b.y)
105            && self.base.equal(&a.z, &b.z)
106            && self.base.equal(&a.w, &b.w)
107    }
108}
109
110impl<Field: FieldSignature> Signature for QuaternionAlgebraStructure<Field> {}
111
112impl<Field: FieldSignature> SetSignature for QuaternionAlgebraStructure<Field> {
113    type Set = QuaternionAlgebraElement<Field::Set>;
114
115    fn is_element(&self, _x: &Self::Set) -> Result<(), String> {
116        Ok(())
117    }
118}
119
120impl<Field: FieldSignature> RinglikeSpecializationSignature for QuaternionAlgebraStructure<Field> {
121    fn try_ring_restructure(&self) -> Option<impl EqSignature<Set = Self::Set> + RingSignature> {
122        Some(self.clone())
123    }
124}
125
126impl<Field: FieldSignature> ZeroSignature for QuaternionAlgebraStructure<Field> {
127    fn zero(&self) -> Self::Set {
128        QuaternionAlgebraElement {
129            x: self.base.zero(),
130            y: self.base.zero(),
131            z: self.base.zero(),
132            w: self.base.zero(),
133        }
134    }
135}
136
137impl<Field: FieldSignature> AdditionSignature for QuaternionAlgebraStructure<Field> {
138    fn add(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
139        QuaternionAlgebraElement {
140            x: self.base.add(&a.x, &b.x),
141            y: self.base.add(&a.y, &b.y),
142            z: self.base.add(&a.z, &b.z),
143            w: self.base.add(&a.w, &b.w),
144        }
145    }
146}
147
148impl<Field: FieldSignature> CancellativeAdditionSignature for QuaternionAlgebraStructure<Field> {
149    fn try_sub(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
150        Some(self.sub(a, b))
151    }
152}
153
154impl<Field: FieldSignature> TryNegateSignature for QuaternionAlgebraStructure<Field> {
155    fn try_neg(&self, a: &Self::Set) -> Option<Self::Set> {
156        Some(self.neg(a))
157    }
158}
159
160impl<Field: FieldSignature> AdditiveMonoidSignature for QuaternionAlgebraStructure<Field> {}
161
162impl<Field: FieldSignature> AdditiveGroupSignature for QuaternionAlgebraStructure<Field> {
163    fn neg(&self, a: &Self::Set) -> Self::Set {
164        QuaternionAlgebraElement {
165            x: self.base.neg(&a.x),
166            y: self.base.neg(&a.y),
167            z: self.base.neg(&a.z),
168            w: self.base.neg(&a.w),
169        }
170    }
171
172    fn sub(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
173        QuaternionAlgebraElement {
174            x: self.base.sub(&a.x, &b.x),
175            y: self.base.sub(&a.y, &b.y),
176            z: self.base.sub(&a.z, &b.z),
177            w: self.base.sub(&a.w, &b.w),
178        }
179    }
180}
181
182impl<Field: FieldSignature> OneSignature for QuaternionAlgebraStructure<Field> {
183    fn one(&self) -> Self::Set {
184        QuaternionAlgebraElement {
185            x: self.base.one(),
186            y: self.base.zero(),
187            z: self.base.zero(),
188            w: self.base.zero(),
189        }
190    }
191}
192
193impl<Field: FieldSignature> MultiplicationSignature for QuaternionAlgebraStructure<Field> {
194    fn mul(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
195        let a_param = &self.a;
196        let b_param = &self.b;
197        let base = &self.base;
198        let ab = base.mul(a_param, b_param);
199
200        if self.is_char_2 {
201            // Quaternion multiplication in characteristic 2.
202            //
203            //   i^2 + i = a
204            //   j^2 = b
205            //   k = ij = j(i + 1)
206            unimplemented!("Quaternion multiplication for char=2 is not implemented yet");
207        } else {
208            // Quaternion multiplication in characteristic ≠ 2.
209            //
210            //   i^2 = a
211            //   j^2 = b
212            //   ij = k = -ji
213
214            let z0 = base.sub(
215                &base.add(
216                    &base.add(
217                        &base.mul(&a.x, &b.x),
218                        &base.mul(&base.mul(&a.y, &b.y), a_param),
219                    ),
220                    &base.mul(&base.mul(&a.z, &b.z), b_param),
221                ),
222                &base.mul(&base.mul(&a.w, &b.w), &ab),
223            );
224            let z1 = base.sub(
225                &base.add(
226                    &base.add(&base.mul(&a.x, &b.y), &base.mul(&a.y, &b.x)),
227                    &base.mul(&base.mul(&a.z, &b.w), b_param),
228                ),
229                &base.mul(&base.mul(&a.w, &b.z), b_param),
230            );
231            let z2 = base.add(
232                &base.sub(
233                    &base.add(&base.mul(&a.x, &b.z), &base.mul(&a.z, &b.x)),
234                    &base.mul(&base.mul(&a.y, &b.w), a_param),
235                ),
236                &base.mul(&base.mul(&a.w, &b.y), a_param),
237            );
238            let z3 = base.add(
239                &base.sub(
240                    &base.add(&base.mul(&a.x, &b.w), &base.mul(&a.w, &b.x)),
241                    &base.mul(&a.z, &b.y),
242                ),
243                &base.mul(&a.y, &b.z),
244            );
245
246            QuaternionAlgebraElement {
247                x: z0,
248                y: z1,
249                z: z2,
250                w: z3,
251            }
252        }
253    }
254}
255
256impl<Field: FieldSignature> CommutativeMultiplicationSignature
257    for QuaternionAlgebraStructure<Field>
258{
259}
260
261impl<Field: FieldSignature> MultiplicativeMonoidSignature for QuaternionAlgebraStructure<Field> {}
262
263impl<Field: FieldSignature> MultiplicativeAbsorptionMonoidSignature
264    for QuaternionAlgebraStructure<Field>
265{
266}
267
268impl<Field: FieldSignature> LeftDistributiveMultiplicationOverAddition
269    for QuaternionAlgebraStructure<Field>
270{
271}
272
273impl<Field: FieldSignature> RightDistributiveMultiplicationOverAddition
274    for QuaternionAlgebraStructure<Field>
275{
276}
277
278impl<Field: FieldSignature> SemiRingSignature for QuaternionAlgebraStructure<Field> {}
279
280impl<Field: FieldSignature> TryReciprocalSignature for QuaternionAlgebraStructure<Field> {
281    fn try_reciprocal(&self, a: &Self::Set) -> Option<Self::Set> {
282        let n_inv = self.base.try_reciprocal(&self.reduced_norm(a))?;
283        Some(self.scalar_mul(&self.conjugate(a), &n_inv))
284    }
285
286    fn is_unit(&self, a: &Self::Set) -> bool {
287        self.base.is_unit(&self.reduced_norm(a))
288    }
289}
290
291impl<Field: FieldSignature> RingSignature for QuaternionAlgebraStructure<Field> {}
292
293impl<Field: FieldSignature> SemiModuleSignature<Field> for QuaternionAlgebraStructure<Field> {
294    fn ring(&self) -> &Field {
295        &self.base
296    }
297
298    fn scalar_mul(&self, a: &Self::Set, x: &Field::Set) -> Self::Set {
299        let base = &self.base;
300        QuaternionAlgebraElement {
301            x: base.mul(x, &a.x),
302            y: base.mul(x, &a.y),
303            z: base.mul(x, &a.z),
304            w: base.mul(x, &a.w),
305        }
306    }
307}
308
309impl<Field: FieldSignature> AlgebraSignature<Field> for QuaternionAlgebraStructure<Field> {}
310
311impl<Field: FieldSignature> FreeModuleSignature<Field> for QuaternionAlgebraStructure<Field> {
312    type Basis = QuaternionAlgebraBasisCanonicalStructure;
313
314    fn basis_set(&self) -> impl std::borrow::Borrow<Self::Basis> {
315        Self::Basis {}
316    }
317
318    fn to_component<'a>(
319        &self,
320        b: &QuaternionAlgebraBasis,
321        v: &'a Self::Set,
322    ) -> Cow<'a, Field::Set> {
323        Cow::Borrowed(match b {
324            QuaternionAlgebraBasis::R => &v.x,
325            QuaternionAlgebraBasis::I => &v.y,
326            QuaternionAlgebraBasis::J => &v.z,
327            QuaternionAlgebraBasis::K => &v.w,
328        })
329    }
330
331    fn from_component(&self, b: &QuaternionAlgebraBasis, r: &Field::Set) -> Self::Set {
332        let mut v = self.zero();
333        match b {
334            QuaternionAlgebraBasis::R => v.x = r.clone(),
335            QuaternionAlgebraBasis::I => v.y = r.clone(),
336            QuaternionAlgebraBasis::J => v.z = r.clone(),
337            QuaternionAlgebraBasis::K => v.w = r.clone(),
338        }
339        v
340    }
341}
342
343impl<Field: FieldSignature + CharacteristicSignature> CharacteristicSignature
344    for QuaternionAlgebraStructure<Field>
345{
346    fn characteristic(&self) -> Natural {
347        self.base.characteristic()
348    }
349}
350
351impl<Field: CharZeroFieldSignature> CharZeroRingSignature for QuaternionAlgebraStructure<Field> {
352    fn try_to_int(&self, a: &Self::Set) -> Option<algebraeon_nzq::Integer> {
353        // The element must be of the form [a.x, 0, 0, 0]
354        if self.base.is_zero(&a.y) && self.base.is_zero(&a.z) && self.base.is_zero(&a.w) {
355            self.base.try_to_int(&a.x)
356        } else {
357            None
358        }
359    }
360}
361
362impl<Field: FieldSignature> QuaternionAlgebraStructure<Field> {
363    pub fn i(&self) -> QuaternionAlgebraElement<Field::Set> {
364        QuaternionAlgebraElement {
365            x: self.base.zero(),
366            y: self.base.one(),
367            z: self.base.zero(),
368            w: self.base.zero(),
369        }
370    }
371
372    pub fn j(&self) -> QuaternionAlgebraElement<Field::Set> {
373        QuaternionAlgebraElement {
374            x: self.base.zero(),
375            y: self.base.zero(),
376            z: self.base.one(),
377            w: self.base.zero(),
378        }
379    }
380
381    pub fn k(&self) -> QuaternionAlgebraElement<Field::Set> {
382        QuaternionAlgebraElement {
383            x: self.base.zero(),
384            y: self.base.zero(),
385            z: self.base.zero(),
386            w: self.base.one(),
387        }
388    }
389
390    pub fn conjugate(
391        &self,
392        a: &QuaternionAlgebraElement<Field::Set>,
393    ) -> QuaternionAlgebraElement<Field::Set> {
394        let base = &self.base;
395        if self.is_char_2 {
396            // https://jvoight.github.io/quat-book.pdf paragraph 6.2.6.
397            QuaternionAlgebraElement {
398                x: base.add(&a.x, &a.y),
399                y: a.y.clone(),
400                z: a.z.clone(),
401                w: a.w.clone(),
402            }
403        } else {
404            QuaternionAlgebraElement {
405                x: a.x.clone(),
406                y: base.neg(&a.y),
407                z: base.neg(&a.z),
408                w: base.neg(&a.w),
409            }
410        }
411    }
412
413    pub fn reduced_trace(&self, a: &QuaternionAlgebraElement<Field::Set>) -> Field::Set {
414        if self.is_char_2 {
415            // https://jvoight.github.io/quat-book.pdf paragraph 6.2.6.
416            a.y.clone()
417        } else {
418            self.base.add(&a.x, &a.x) // 2 * &a.x
419        }
420    }
421
422    pub fn reduced_norm(&self, a: &QuaternionAlgebraElement<Field::Set>) -> Field::Set {
423        let base = &self.base;
424        let a_param = &self.a;
425        let b_param = &self.b;
426        let ab = base.mul(a_param, b_param);
427
428        if self.is_char_2 {
429            // https://jvoight.github.io/quat-book.pdf equation 6.2.7.
430            // t^2 + t·x + a·x^2 + b·y^2 + b·y·z + ab·z^2
431            let t2 = base.mul(&a.x, &a.x);
432            let tx = base.mul(&a.x, &a.y);
433            let ax2 = base.mul(a_param, &base.mul(&a.y, &a.y));
434            let by2 = base.mul(b_param, &base.mul(&a.z, &a.z));
435            let byz = base.mul(b_param, &base.mul(&a.z, &a.w));
436            let abz2 = base.mul(&ab, &base.mul(&a.w, &a.w));
437            base.add(
438                &base.add(&base.add(&base.add(&base.add(&t2, &tx), &ax2), &by2), &byz),
439                &abz2,
440            )
441        } else {
442            let term0 = base.mul(&a.x, &a.x);
443            let term1 = base.mul(a_param, &base.mul(&a.y, &a.y));
444            let term2 = base.mul(b_param, &base.mul(&a.z, &a.z));
445            let term3 = base.mul(&ab, &base.mul(&a.w, &a.w));
446
447            base.sub(&base.sub(&base.add(&term0, &term3), &term1), &term2)
448        }
449    }
450}
451
452#[cfg(test)]
453mod tests {
454    use super::*;
455    use algebraeon_nzq::Rational;
456
457    #[test]
458    fn test_add_and_mul() {
459        // Hamilton quaternion algebra: H = (-1, -1 / QQ)
460        let h =
461            QuaternionAlgebraStructure::new(Rational::structure(), -Rational::ONE, -Rational::ONE);
462
463        let i = h.i();
464        let j = h.j();
465        let i_plus_j = h.add(&i, &j);
466        let j_plus_i = h.add(&j, &i);
467        let i_times_j = h.mul(&i, &j);
468        let j_times_i = h.mul(&j, &i);
469
470        assert!(h.equal(&i_plus_j, &j_plus_i));
471        assert!(h.equal(&i_times_j, &h.neg(&j_times_i)));
472    }
473
474    #[test]
475    fn test_reduced_norm_from_sage_example() {
476        let h = QuaternionAlgebraStructure::new(
477            Rational::structure(),
478            Rational::from(-5i32),
479            Rational::from(-2i32),
480        );
481
482        assert_eq!(h.reduced_norm(&h.i()), Rational::from(5i32));
483        assert_eq!(h.reduced_norm(&h.j()), Rational::from(2i32));
484
485        let a = QuaternionAlgebraElement {
486            x: Rational::from_integers(1, 3),
487            y: Rational::from_integers(1, 5),
488            z: Rational::from_integers(1, 7),
489            w: Rational::ONE,
490        };
491
492        let expected = Rational::from_integers(22826, 2205);
493        assert_eq!(h.reduced_norm(&a), expected);
494    }
495}
algebraeon_rings/quaternion_algebra/mod.rs

algebraeon_rings/quaternion_algebra/
mod.rs
