z      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{| } ~  4  !"#$%&'()*+,-./01234  !"#$%&'()*+,-./012343210/.-,+*)('&%$#"!  4  !"#$%&'()*+,-./01234Definition of rings. 5 Addition 6Multiplication 7Compute additive inverse 8The additive identity 9The multiplicative identity :Addition is associative. ;Zero is the additive identity. <$Negation give the additive inverse. =Addition is commutative. >Multiplication is associative. ?4Multiplication is right-distributive over addition. @2Multiplication is left-ditributive over addition. A$One is the multiplicative identity. BISpecification of rings. Test that the arguments satisfy the ring axioms. C Subtraction D Summation EProduct FExponentiation 456789:;<=>?@ABCDEF456789:;<=>A?@BCFDE45678956789:;<=>?@ABCDEFG!Definition of commutative rings. HIASpecification of commutative rings. Test that multiplication is 4 commutative and that it satisfies the ring axioms. 456789:;<=>?@ABCDEFGHIGHIGHIJ Definition of integral domains. KLHSpecification of integral domains. Test that there are no zero-divisors 8 and that it satisfies the axioms of commutative rings. 456789:;<=>?@ABCDEFGHIJKLJKLJKLMDefinition of fields. NOPJSpecification of fields. Test that the multiplicative inverses behave as @ expected and that it satisfies the axioms of integral domains. Q Division 456789:;<=>?@ABCDEFGHIJKLMNOPQMNOPQMNNOPQR Matrices ST Row vectors UVWXConstruct a mxn matrix. YZ[\]#Compute the dimension of a matrix. ^_Transpose a matrix. `Matrix addition. aMatrix multiplication. b!Construct a nxn identity matrix. RSTUVWXYZ[\]^_`abTUVWRSX\[ZYba`_^]RSSTUUVWXYZ[\]^_`ab c2Ideals characterized by their list of generators. deThe zero ideal. fTest if an ideal is principal. gh'Evaluate the ideal at a certain point. iAddition of ideals. jMultiplication of ideals. k2Test if an operations compute the correct ideal. DThe operation should give a witness that the comuted ideal contains the same elements. If [ x_1, ..., x_n ] `op` [ y_1, ..., y_m ] = [ z_1, ..., z_l ] "Then the witness should give that $z_k = a_k1 * x_1 + ... + a_kn * x_n $ = b_k1 * y_1 + ... + b_km * y_m AThis is used to check that the intersection computed is correct. lGCompute witnesses for two lists for the zero ideal. This is used when + computing the intersection of two ideals. cdefghijkl cdefghijkl cddefghijklmEuclidean domains BGiven a and b compute (q,r) such that a = bq + r and r = 0 || d r < d b. $ Where d is the Euclidean function. nopCheck both that |a|  = |ab| and |a| = 0 for all a,b. qrstuv<The Euclidean algorithm for calculating the GCD of a and b. wFGeneralized Euclidean algorithm to compute GCD of a list of elements. xLowest common multiple, (a*b)/ gcd(a,b). yIGeneralized lowest common multiple to compute lcm of a list of elements. z#The extended Euclidean algorithm. (Computes x and y in ax + by = gcd(a,b). {*Generalized extended Euclidean algorithm. 3Solves a_1 x_1 + ... + a_n x_n = gcd (a_1,...,a_n) mnopqrstuvwxyz{mnopqrstuvwxyz{mnonopqrstuvwxyz{ |Strongly discrete rings EA ring is called strongly discrete if ideal membership is decidable. K Nothing correspond to that x is not in the ideal and Just is the witness. ; Examples include all Bezout domains and polynomial rings. }~HTest that the witness is actually a witness that the element is in the  ideal. |}~|}~|}}~ Definition of coherent rings. JWe say that R is coherent iff for any M, we can find L such that ML=0 and MX=0 <-> exists Y. X=LY Kthat is, iff we can generate the solutions of any linear homogeous system  of equations. GThe main point here is that ML=0, it is not clear how to represent the I equivalence in Haskell. This would probably be possible in type theory. Solves a system of equations. LTest that the solution of an MxN system is in fact a solution of the system &Intersection computable -> Coherence. MProof that if there is an algorithm to compute a f.g. set of generators for @ the intersection of two f.g. ideals then the ring is coherent. Takes the vector to solve, [ x1,...,xn]&, and a function (int) that computes " the intersection of two ideals. If [ x_1, ..., x_n ] `int` [ y_1, ..., y_m ] = [ z_1, ..., z_l ] 4then int should give witnesses us and vs such that: $z_k = n_k1 * x_1 + ... + u_kn * x_n  = u_k1 * y_1 + ... + n_km * y_m "Strongly discrete coherent rings. KIf the ring is strongly discrete and coherent then we can solve arbitrary  equations of the type AX=b. 2Solves general linear systems of the kind AX = B. LA is given as a matrix and B is given as a row vector (it should be column  vector).    Bezout domains ICompute a principal ideal from another ideal. Also give witness that the . principal ideal is equal to the first ideal.  toPrincipal <a_1,...,a_n> = (< a>,u_i,v_i)  where sum (u_i * a_i) = a a_i = v_i * a ,Test that the generated ideal is principal. GTest that the generated ideal generate the same elements as the given. %Intersection of ideals with witness. JIf one of the ideals is the zero ideal then the intersection is the zero  ideal. Intersection without witness. Coherence of Bezout domains. Chinese remainder theorem >Given a_1,...,a_n and m_1,...,m_n such that gcd(m_i,m_j) = 1. * Let m = m_1*...*m_n compute a such that:   a = a_i (mod m_i)  If b is such that b = a_i (mod m_i) then a = b (mod m) The function return (a,m). )Strongly discreteness for Bezout domains 2Given x, compute as such that x = sum (a_i * x_i)  Prufer domain Property specifying that:  au = bv and b(1-u) = aw MAlternative characterization of Prufer domains, given a and b compute u, v,  w, t such that: ua = vb && wa = tb && u+t = 1 $Go back to the original definition. Bezout domain -> Prfer domain 2Proof that all Bezout domains are Prufer domains. ICompute a principal localization matrix for an ideal in a Prufer domain. >Ideal inversion. Given I compute J such that IJ is principal. 7 Uses the principal localization matrix for the ideal. (Compute the intersection of I and J by: -(I  J)(I + J) = IJ => (I  J)(I + J)(I + J)' = IJ(I + J)' Coherence of Prufer domains.   GCD domains 6Compute gcd(a,b) = (g,x,y) such that g = gcd(a,b) and  a = gx  b = gy  and a, b /= 0 HSpecification of GCD domains. They are integral domains in which every : pair of nonzero elements have a greatest common divisor. Field of fractions )Embed a value in the field of fractions. JExtract a value from the field of fractions. This is only possible if the  divisor is one. Reduce an element. KA principal localization matrix for an ideal (x1,...,xn) is a matrix such that: ) The sum of the diagonal should equal 1. 4 For all i, j, l in {1..n}: a_lj * x_i = a_li * x_j MPrincipal localization matrices for ideals are computable in Bezout domains.  Type synonym for integers. 4567894567897The phantom type n represents which modulo to work in. "Q is the field of fractions of Z. Useful shorthand for Q[x]. GPolynomials over a commutative ring, indexed by a phantom type x that K denote the name of the variable that the polynomial is over. For example  UPoly Q X_ is Q[x] and UPoly Q T_ is Q[t]. The degree of the polynomial. The variable x in Q[x]. JTake a list and construct a polynomial by removing all zeroes in the end. ITake an element of the ring and the degree of the desired monomial, for  example: monomial 3 7 = 3x^7 *Compute the leading term of a polynomial. 'Formal derivative of polynomials in k[x]. Funny integration: ,Square free decomposition of a polynomial. <Distinct power factorization, aka square free decomposition  Pseudo-division of polynomials. 8Given s(x) and p(x) compute c, q(x) and r(x) such that: cs(x) = p(x)q(x)+r(x), deg r < deg p. The field of fraction of Q[x]. Field of rational functions.  'The elliptic curve y^2=1-x^4 over Q[x,y]. Abelian groups: *pow g n computes the n:th power of g, g^n "gen g constructs the cyclic group  g generated by g (Generalization for multiple generators,  S where S = {g_1,g_2,...}  FCompute the right and left cosets of a subset hs in the group G with ! respect to an element g in G   "The product of two subgroups of G  Quotient groups, G/H, assumes that H is normal 5 This version does not respect possible duplicates  Pairs of groups:  Z[sqrt(-5)], is a pair such that (a,b) = a + b*sqrt(-5)  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijk&lmnopqrstuvwxyz{|}~      -"0NQP      constructive-algebra-0.2.0Algebra.TypeChar.CharAlgebra.Structures.Ring"Algebra.Structures.CommutativeRing!Algebra.Structures.IntegralDomainAlgebra.Structures.FieldAlgebra.Matrix Algebra.Ideal"Algebra.Structures.EuclideanDomain#Algebra.Structures.StronglyDiscreteAlgebra.Structures.CoherentAlgebra.Structures.BezoutDomainAlgebra.Structures.PruferDomainAlgebra.Structures.GCDDomain#Algebra.Structures.FieldOfFractions Algebra.PLM Algebra.Z Algebra.Zn Algebra.Q Algebra.UPoly Algebra.FieldOfRationalFunctionsAlgebra.EllipticCurveAlgebra.Structures.GroupAlgebra.Structures.ModuleAlgebra.ZSqrt5ZYXWVUTSRQPONMLKJIHGFEDCBAZ_Y_X_W_V_U_T_S_R_Q_P_O_N_M_L_K_J_I_H_G_F_E_D_C_B_A_Ring<+><*>negzeroone propAddAssocpropAddIdentity propAddInv propAddComm propMulAssoc propRightDist propLeftDistpropMulIdentitypropRing<->sumRing productRing<^>CommutativeRing propMulCommpropCommutativeRingIntegralDomainpropZeroDivisorspropIntegralDomainFieldinv propMulInv propFieldMatrixVectorVecunVec lengthVecmatrixunMunMVecvectorToMatrixmatrixToVector dimensionisSquareMatrix transposeaddMmulMidentityIdealId zeroIdeal isPrincipalfromIdevaladdIdmulId isSameIdealzeroIdealWitnessesEuclideanDomaindquotientRemainderpropD propQuotRempropEuclideanDomainmoduloquotientdivides euclidAlg genEuclidAlglcmEgenLcmEextendedEuclidAlggenExtendedEuclidAlgStronglyDiscretememberpropStronglyDiscreteCoherentsolve propCoherentsolveMxN propSolveMxNsolveWithIntersectionsolveGeneralEquationpropSolveGeneralEquation solveGeneralpropSolveGeneral BezoutDomain toPrincipalpropToPrincipalpropIsSameIdealpropBezoutDomaindividesBgcdBintersectionBWitness intersectionBsolveBcrt PruferDomaincalcUVW propCalcUVWpropPruferDomaincalcUVWT propCalcUVWT fromUVWTtoUVW calcUVW_B computePLM_PD invertIdealintersectionPDWitnessintersectionPDsolvePD GCDDomaingcd'propGCD propGCDDomainFieldOfFractionstoFieldOfFractionsfromFieldOfFractionsreduce propReducepropPLM computePLM_BZ3ZntoQtoZQxUPolyUPdegxtoUPolymonomialltderivsqfrsqfrDecQXFieldOfRationalFunctionstoQXtoQx EllipticCurve AbelianGroupGroup propAssocpropIdpropInv propGrouppropCommpropAbelianGroupsumGroupModule*> propScalarMul propScalarAddpropScalarAssoc propModule<*ZSqrt5propLeftIdentitypropRightIdentitypropExtendedEuclidAlgpropGenExtEuclidAlg isSolution handleZero$fStronglyDiscreteapropIntegralDomainZpropEuclideanDomainZpropBezoutDomainZpropStronglyDiscreteZ propCoherentZ propSolveMxNZpropSolveGeneralEquationZpropSolveGeneralZpropPLMZpropPruferDomainZpropIsSameIdealPruferDomainIsZeroPrime'PrimeSqrt'SqrtZ17test1test2test3sqrtprime constUPoly integrateaddUPmulUP pseudoDividepropPD propFieldQX propIntDomEC+><+propPruferDomECpropIntersectionPECpowgenmultiGenorder rightCoset leftCosetproductquotientGroups// $fGroup(,)propIntDomZSqrt5propPruferDomZSqrt5