aboutsummaryrefslogtreecommitdiff
path: root/src/algebra/mring.spad.pamphlet
blob: 46e50c7d81eb7de97271ba82c6f53591f60af931 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra mring.spad}
\author{Stephen M. Watt, Johannes Grabmeier, Mike Dewar}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{domain MRING MonoidRing}
<<domain MRING MonoidRing>>=
)abbrev domain MRING MonoidRing
++ Authors: Stephan M. Watt; revised by Johannes Grabmeier
++ Date Created: January 1986
++ Date Last Updated: 14 December 1995, Mike Dewar
++ Basic Operations: *, +, monomials, coefficients
++ Related Constructors: Polynomial
++ Also See:
++ AMS Classifications:
++ Keywords: monoid ring, group ring, polynomials in non-commuting
++  indeterminates
++ References:
++ Description:
++  \spadtype{MonoidRing}(R,M), implements the algebra
++  of all maps from the monoid M to the commutative ring R with
++  finite support.
++  Multiplication of two maps f and g is defined
++  to map an element c of M to the (convolution) sum over {\em f(a)g(b)}
++  such that {\em ab = c}. Thus M can be identified with a canonical
++  basis and the maps can also be considered as formal linear combinations
++  of the elements in M. Scalar multiples of a basis element are called
++  monomials. A prominent example is the class of polynomials
++  where the monoid is a direct product of the natural numbers
++  with pointwise addition. When M is
++  \spadtype{FreeMonoid Symbol}, one gets polynomials
++  in infinitely many non-commuting variables. Another application
++  area is representation theory of finite groups G, where modules
++  over \spadtype{MonoidRing}(R,G) are studied.

MonoidRing(R: Ring, M: Monoid): MRcategory == MRdefinition where
    Term ==> Record(coef: R, monom: M)

    MRcategory ==> Join(Ring, RetractableTo M, RetractableTo R) with
        monomial         : (R, M) -> %
          ++ monomial(r,m) creates a scalar multiple of the basis element m.
        coefficient : (%, M) -> R
          ++ coefficient(f,m) extracts the coefficient of m in f with respect
          ++ to the canonical basis M.
        coerce:   List Term -> %
          ++ coerce(lt) converts a list of terms and coefficients to a member of the domain.
        terms       : % -> List Term
          ++ terms(f) gives the list of non-zero coefficients combined
          ++ with their corresponding basis element as records.
          ++ This is the internal representation.
        map         : (R -> R, %) -> %
          ++ map(fn,u) maps function fn onto the coefficients
          ++ of the non-zero monomials of u.
        monomial?   : % -> Boolean
          ++ monomial?(f) tests if f is a single monomial.
        coefficients: % -> List R
          ++ coefficients(f) lists all non-zero coefficients.
        monomials: % -> List %
           ++ monomials(f) gives the list of all monomials whose
           ++ sum is f.
        numberOfMonomials: % -> NonNegativeInteger
           ++ numberOfMonomials(f) is the number of non-zero coefficients
           ++ with respect to the canonical basis.
        if R has CharacteristicZero then CharacteristicZero
        if R has CharacteristicNonZero then CharacteristicNonZero
        if R has CommutativeRing then Algebra(R)
        if (R has Finite and M has Finite) then Finite
        if M has OrderedSet then
          leadingMonomial   : % -> M
            ++ leadingMonomial(f) gives the monomial of f whose
            ++ corresponding monoid element is the greatest
            ++ among all those with non-zero coefficients.
          leadingCoefficient: % -> R
            ++ leadingCoefficient(f) gives the coefficient of f, whose
            ++ corresponding monoid element is the greatest
            ++ among all those with non-zero coefficients.
          reductum          : % -> %
            ++ reductum(f) is f minus its leading monomial.

    MRdefinition ==> add
        Ex ==> OutputForm
        Cf ==> coef
        Mn ==> monom

        Rep  := List Term

        coerce(x: List Term): % == x :: %

        monomial(r:R, m:M)  ==
          r = 0 => empty()
          [[r, m]]

        if (R has Finite and M has Finite) then
          size() == size()$R ** size()$M

          index k ==
            -- use p-adic decomposition of k
            -- coefficient of p**j determines coefficient of index(i+p)$M
            i:Integer := k rem size()
            p:Integer := size()$R
            n:Integer := size()$M
            ans:% := 0
            for j in 0.. while i > 0 repeat
              h := i rem p
              -- we use index(p) = 0$R
              if h ~= 0 then
                c : R := index(h :: PositiveInteger)$R
                m : M := index((j+n) :: PositiveInteger)$M
                --ans := ans + c *$% m
                ans := ans + monomial(c, m)$%
              i := i quo p
            ans

          lookup(z : %) : PositiveInteger ==
            -- could be improved, if M has OrderedSet
            -- z = index lookup z, n = lookup index n
            -- use p-adic decomposition of k
            -- coefficient of p**j determines coefficient of index(i+p)$M
            zero?(z) => size()$% pretend PositiveInteger
            liTe : List Term := terms z  -- all non-zero coefficients
            p  : Integer := size()$R
            n  : Integer := size()$M
            res : Integer := 0
            for te in liTe repeat
              -- assume that lookup(p)$R = 0
              l:NonNegativeInteger:=lookup(te.Mn)$M
              ex : NonNegativeInteger := (n=l => 0;l)
              co : Integer := lookup(te.Cf)$R
              res := res + co * p ** ex
            res pretend PositiveInteger

          random() == index( (1+(random()$Integer rem size()$%) )_
            pretend PositiveInteger)$%

        0                   == empty()
        1                   == [[1, 1]]
        terms a             == (copy a) pretend List(Term)
        monomials a         == [[t] for t in a]
        coefficients a      == [t.Cf for t in a]
        coerce(m:M):%       == [[1, m]]
        coerce(r:R): % ==
        -- coerce of ring
          r = 0 => 0
          [[r,    1]]
        coerce(n:Integer): % ==
        -- coerce of integers
          n = 0 => 0
          [[n::R, 1]]
        - a                 == [[ -t.Cf, t.Mn] for t in a]
        if R has noZeroDivisors
           then
            (r:R) * (a:%) ==
              r = 0 => 0
              [[r*t.Cf, t.Mn] for t in a]
           else
            (r:R) * (a:%) ==
              r = 0 => 0
              [[rt, t.Mn] for t in a | (rt:=r*t.Cf) ~= 0]
        if R has noZeroDivisors
           then
            (n:Integer) * (a:%) ==
              n = 0 => 0
              [[n*t.Cf, t.Mn] for t in a]
           else
            (n:Integer) * (a:%) ==
              n = 0 => 0
              [[nt, t.Mn] for t in a | (nt:=n*t.Cf) ~= 0]
        map(f, a)           == [[ft, t.Mn] for t in a | (ft:=f(t.Cf)) ~= 0]
        numberOfMonomials a == #a

        retractIfCan(a:%):Union(M, "failed") ==
          one?(#a) and one?(a.first.Cf) => a.first.Mn
          "failed"

        retractIfCan(a:%):Union(R, "failed") ==
          one?(#a) and one?(a.first.Mn) => a.first.Cf
          "failed"

        if R has noZeroDivisors then
          if M has Group then
            recip a ==
              lt := terms a
              #lt ~= 1 => "failed"
              (u := recip lt.first.Cf) case "failed" => "failed"
              --(u::R) * inv lt.first.Mn
              monomial((u::R), inv lt.first.Mn)$%
          else
            recip a ==
              #a ~= 1 or a.first.Mn ~= 1 => "failed"
              (u := recip a.first.Cf) case "failed" => "failed"
              u::R::%

        mkTerm(r:R, m:M):Ex ==
            r=1 => m::Ex
            r=0 or m=1 => r::Ex
            r::Ex * m::Ex

        coerce(a:%):Ex ==
            empty? a => (0$Integer)::Ex
            empty? rest a => mkTerm(a.first.Cf, a.first.Mn)
            reduce(_+, [mkTerm(t.Cf, t.Mn) for t in a])$List(Ex)

        if M has OrderedSet then -- we mean totally ordered
            -- Terms are stored in decending order.
            leadingCoefficient a == (empty? a => 0; a.first.Cf)
            leadingMonomial a    == (empty? a => 1; a.first.Mn)
            reductum a           == (empty? a => a; rest a)

            a = b ==
                #a ~= #b => false
                for ta in a for tb in b repeat
                    ta.Cf ~= tb.Cf or ta.Mn ~= tb.Mn => return false
                true

            a + b ==
                c:% := empty()
                while not empty? a and not empty? b repeat
                  ta := first a; tb := first b
                  ra := rest a;  rb := rest b
                  c :=
                    ta.Mn > tb.Mn => (a := ra; concat!(c, ta))
                    ta.Mn < tb.Mn => (b := rb; concat!(c, tb))
                    a := ra; b := rb
                    not zero?(r := ta.Cf+tb.Cf) =>
                                        concat!(c, [r, ta.Mn])
                    c
                concat!(c, concat(a, b))

            coefficient(a, m) ==
                for t in a repeat
                    if t.Mn = m then return t.Cf
                    if t.Mn < m then return 0
                0


            if M has OrderedMonoid then

            -- we use that multiplying an ordered list of monoid elements
            -- by a single element respects the ordering

              if R has noZeroDivisors then
                a:% * b:% ==
                  +/[[[ta.Cf*tb.Cf, ta.Mn*tb.Mn]$Term
                    for tb in b ] for ta in reverse a]
              else
                a:% * b:% ==
                  +/[[[r, ta.Mn*tb.Mn]$Term
                    for tb in b | not zero?(r := ta.Cf*tb.Cf)]
                      for ta in reverse a]
            else -- M hasn't OrderedMonoid

            -- we cannot assume that mutiplying an ordered list of
            -- monoid elements by a single element respects the ordering:
            -- we have to order and to collect equal terms
              ge : (Term,Term) -> Boolean
              ge(s,t) == t.Mn <= s.Mn

              sortAndAdd : List Term -> List Term
              sortAndAdd(liTe) ==  -- assume liTe not empty
                liTe := sort(ge,liTe)
                m : M :=  (first liTe).Mn
                cf : R := (first liTe).Cf
                res : List Term := []
                for te in rest liTe repeat
                  if m = te.Mn then
                    cf := cf + te.Cf
                  else
                    if not zero? cf then res := cons([cf,m]$Term, res)
                    m := te.Mn
                    cf := te.Cf
                if not zero? cf then res := cons([cf,m]$Term, res)
                reverse res


              if R has noZeroDivisors then
                a:% * b:% ==
                  zero? a => a
                  zero? b => b  -- avoid calling sortAndAdd with []
                  +/[sortAndAdd [[ta.Cf*tb.Cf, ta.Mn*tb.Mn]$Term
                    for tb in b ] for ta in reverse a]
              else
                a:% * b:% ==
                  zero? a => a
                  zero? b => b  -- avoid calling sortAndAdd with []
                  +/[sortAndAdd [[r, ta.Mn*tb.Mn]$Term
                    for tb in b | not zero?(r := ta.Cf*tb.Cf)]
                      for ta in reverse a]


        else -- M hasn't OrderedSet
            -- Terms are stored in random order.
          a = b ==
            #a ~= #b => false
            brace(a pretend List(Term)) =$Set(Term) brace(b pretend List(Term))

          coefficient(a, m) ==
            for t in a repeat
              t.Mn = m => return t.Cf
            0

          addterm(Tabl: AssociationList(M,R), r:R, m:M):R ==
              (u := search(m, Tabl)) case "failed" => Tabl.m := r
              zero?(r := r + u::R) => (remove!(m, Tabl); 0)
              Tabl.m := r

          a + b ==
              Tabl := table()$AssociationList(M,R)
              for t in a repeat
                  Tabl t.Mn := t.Cf
              for t in b repeat
                  addterm(Tabl, t.Cf, t.Mn)
              [[Tabl m, m]$Term for m in keys Tabl]

          a:% * b:% ==
              Tabl := table()$AssociationList(M,R)
              for ta in a repeat
                  for tb in (b pretend List(Term)) repeat
                      addterm(Tabl, ta.Cf*tb.Cf, ta.Mn*tb.Mn)
              [[Tabl.m, m]$Term for m in keys Tabl]

@
\section{package MRF2 MonoidRingFunctions2}
<<package MRF2 MonoidRingFunctions2>>=
)abbrev package MRF2 MonoidRingFunctions2
++ Author: Johannes Grabmeier
++ Date Created: 14 May 1991
++ Date Last Updated: 14 May 1991
++ Basic Operations: map
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords: monoid ring, group ring, change of coefficient domain
++ References:
++ Description:
++  MonoidRingFunctions2 implements functions between
++  two monoid rings defined with the same monoid over different rings.
MonoidRingFunctions2(R,S,M) : Exports == Implementation where
    R  : Ring
    S  : Ring
    M  : Monoid
    Exports ==> with
      map: (R -> S, MonoidRing(R,M)) -> MonoidRing(S,M)
        ++ map(f,u) maps f onto the coefficients f the element
        ++ u of the monoid ring to create an element of a monoid
        ++ ring with the same monoid b.
    Implementation ==> add
      map(fn, u) ==
        res : MonoidRing(S,M) := 0
        for te in terms u repeat
          res := res + monomial(fn(te.coef), te.monom)
        res

@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>

<<domain MRING MonoidRing>>
<<package MRF2 MonoidRingFunctions2>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}