Orbital library

orbital.math
Interface Quotient

All Superinterfaces:
Arithmetic, Normed

public interface Quotient
extends Arithmetic

Quotient represents an (algebraic) equivalence class ā=ã=[a]∈M/~. The quotient M/~ has the same algebraic structure as M.

Let π:M↠M/~; a↦ā be the canonical projection to the equivalence classes. When choosing one right-inverse (section) π-1, we have a canonical representative a=π-1(ā) of ā. However be aware that usually π-1 ∘ π ≠ id which means that the canonical representative of the equivalence class ā∈M/~ of a∈M usually is not a itself.

An implementation will reduce the values a∈M of the algebraic structure M modulo ~ to get the canonical representative of the equivalence class ā. Although an implementation is encouraged to reduce modulo ~ after each operation, this is not strictly required by some applications, as long as equality on the representatives is implemented to fit to the congruence of the equivalence classes. Of course, values of intermediate states need not be reduced at all. Nevertheless, an implementation that has a more lazy reduction policy should document this very carefully because it may affect precision considerations.

c.f. the universal mapping property of the quotient.

For R-modules M it is true that

∀I⊴R M/I⋅M ≅ M ⊗R R/I

Examples of Usage

For example in order to perform algebraic operations in the ring Z/nZ = Z/(n) ≅ {0,1,...,n-1} use a construct like the following:

 // create elements in Z/nZ
 final int n = 17;
 Quotient<Integer> a = Values.quotient(8, n);
 Quotient<Integer> b = Values.quotient(11, n);
 // perform calculations in Z/nZ
 Arithmetic c = a.add(b.multiply(a));
 
If you choose a prime n=p∈N then the above construct gives the finite field Fp of p elements. Note that you can simply leave out parametric type specifiers like <Integer> if you do not intend to use Java Generics (see ignoring templates).

In fact, you could also perform algebraic operations in the quotient ring Q[X]/(X2+X+1)

 // create elements in Q[X]/(X2+X+1)
 final Polynomial<Rational> m =
     Values.asPolynomial(Values.valueOf(new int[] {1,1,1}));
 Quotient<Polynomial<Rational>> a = Values.quotient(..., m);
 Quotient<Polynomial<Rational>> b = Values.quotient(..., m);
 // perform calculations in Q[X]/(X2+X+1)
 Arithmetic c = a.add(b.multiply(a));
 
Or get the complex field C as the quotient ring R[X]/(X2+1)
 // create elements in C alias R[X]/(X2+1)
 final Polynomial<Real> m =
     Values.asPolynomial(Values.valueOf(new double[] {1,0,1}));
 Quotient<Polynomial<Real>> a = Values.quotient(..., m);
 Quotient<Polynomial<Real>> b = Values.quotient(..., m);
 // iC corresponds to X∈R[X]/(X^2+1)
 Quotient<Polynomial<Real>> i = Values.quotient(
     Values.asPolynomial(Values.valueOf(new double[] {0,1})),
     m);
 // perform calculations in C alias R[X]/(X2+1)
 Arithmetic c = a.add(b.multiply(a)).multiply(i);
 

Author:
André Platzer
See Also:
Quotient Structures, ValueFactory.quotient(Arithmetic,Function), ValueFactory.quotient(Euclidean,Euclidean), ValueFactory.quotient(Polynomial,java.util.Set,java.util.Comparator)

Field Summary
 
Fields inherited from interface orbital.math.Arithmetic
numerical
 
Method Summary
 Quotient add(Quotient b)
           
 Quotient divide(Quotient b)
           
 Function getQuotientOperator()
          Get the quotient operator π-1∘π:M→M modulo whom we reduce the values to their canonical representative.
 Arithmetic inverse()
          Returns (modular) multiplicative inverse of this (mod ~).
 Quotient multiply(Quotient b)
           
 Quotient power(Quotient b)
           
 Arithmetic representative()
          Get the "canonical" representative of this equivalence class.
 Arithmetic scale(Arithmetic alpha)
          R/I is an R-algebra, if R is a ring.
 Quotient subtract(Quotient b)
           
 
Methods inherited from interface orbital.math.Arithmetic
add, divide, equals, isOne, isZero, minus, multiply, one, power, subtract, toString, valueFactory, zero
 
Methods inherited from interface orbital.math.Normed
norm
 

Method Detail

getQuotientOperator

Function getQuotientOperator()
Get the quotient operator π-1∘π:M→M modulo whom we reduce the values to their canonical representative.

This modulo operator maps an element a∈M to the canonical representative of its equivalence class modulo ~.

Note that this quotient operator should usually provide Object.equals(Object) to support checking for equal types of equivalence classes.

Returns:
the quotient operator π-1∘π:M→M of this quotient M/~.
Postconditions:
... RES == OLD(RES) ∧ RES is functional

representative

Arithmetic representative()
Get the "canonical" representative of this equivalence class.

Returns:
a "canonical" element π-1(ā)∈R such that π(a) = ā = this.
Postconditions:
RES == getQuotientOperator().apply(this) ∧ getQuotientOperator().apply(RES).equals(RES) ∧ new Modulus(RES, getQuotientOperator()).equals(this) ∧ ∀a,b∈M/~ (a.equals(b) ⇒ a.representative().equals(b.representative()))

inverse

Arithmetic inverse()
                   throws java.lang.ArithmeticException,
                          java.lang.UnsupportedOperationException
Returns (modular) multiplicative inverse of this (mod ~).

Specified by:
inverse in interface Arithmetic
Returns:
this-1.
Throws:
java.lang.ArithmeticException - if this quotient has no multiplicative inverse modulo ~. At least in quotients of Euclidean rings R an element a∈R/(m) does not have a multiplicative inverse, iff gcd(a, m)≠1.
java.lang.UnsupportedOperationException - if this class does not support this operation, principially, regardless of the argument.

add

Quotient add(Quotient b)
             throws java.lang.ArithmeticException
Throws:
java.lang.ArithmeticException

subtract

Quotient subtract(Quotient b)
                  throws java.lang.ArithmeticException
Throws:
java.lang.ArithmeticException

multiply

Quotient multiply(Quotient b)
                  throws java.lang.ArithmeticException,
                         java.lang.UnsupportedOperationException
Throws:
java.lang.ArithmeticException
java.lang.UnsupportedOperationException

divide

Quotient divide(Quotient b)
                throws java.lang.ArithmeticException,
                       java.lang.UnsupportedOperationException
Throws:
java.lang.ArithmeticException
java.lang.UnsupportedOperationException

power

Quotient power(Quotient b)
               throws java.lang.ArithmeticException,
                      java.lang.UnsupportedOperationException
Throws:
java.lang.ArithmeticException
java.lang.UnsupportedOperationException

scale

Arithmetic scale(Arithmetic alpha)
                 throws java.lang.ArithmeticException,
                        java.lang.UnsupportedOperationException
R/I is an R-algebra, if R is a ring. Multiplies a scalar with this arithmetic object returning the result.

Specified by:
scale in interface Arithmetic
Parameters:
alpha - the factor α to scale this arithmetic object with (per law of action of scalar multiplication).
Returns:
α·this
Throws:
java.lang.UnsupportedOperationException - if this class does not support this operation, principially, regardless of the argument. This would only be the case if M did not support it.
java.lang.ArithmeticException - if an exceptional arithmetic condition has occurred while performing the operation. This should not happen for R-modules (where R=alpha.getClass()).
See Also:
Arithmetic.multiply(Arithmetic)
Postconditions:
RES instanceof Quotient

Orbital library
1.3.0: 11 Apr 2009

Copyright © 1996-2009 André Platzer
All Rights Reserved.