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 F_p 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]/(X²+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]/(X²+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);
 // i∈C 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