1)if false
2\documentclass{article}
3\usepackage{axiom, amsthm, amsmath, amsfonts, url}
4\newtheorem{ToDo}{ToDo}[section]
5
6\newcommand{\Axiom}{{\tt Axiom}}
7\begin{document}
8\title{dirichlet.spad}
9\author{Martin Rubey}
10\maketitle
11\begin{abstract}
12  The domain defined in this file models the Dirichlet ring,
13\end{abstract}
14\tableofcontents
15
16\section{The Dirichlet Ring}
17The Dirichlet Ring is the ring of arithmetical functions
18$$ f : \mathbb N_+ \rightarrow R$$
19(see \url{http://en.wikipedia.org/wiki/Arithmetic_function}) together
20with the Dirichlet convolution (see
21\url{http://en.wikipedia.org/wiki/Dirichlet_convolution}) as
22multiplication and component-wise addition.  Since we can consider
23the values an arithmetic functions assumes as the coefficients of a
24Dirichlet generating series, we call $R$ the coefficient ring of a
25function.
26
27In general we only assume that the coefficient ring $R$ is a ring.
28If $R$ happens to be commutative, then so is the Dirichlet ring, and
29in this case it is even an algebra.
30
31Apart from the operations inherited from those categories, we only
32provide some convenient coercion functions.
33)endif
34
35)abbrev domain DIRRING DirichletRing
36++ Author: Martin Rubey
37++ Description: DirichletRing is the ring of arithmetical functions
38++ with Dirichlet convolution as multiplication
39DirichletRing(Coef : Ring):
40            Exports == Implementation where
41
42    PI ==> PositiveInteger
43    FUN ==> PI -> Coef
44
45    Exports ==> Join(Ring, Eltable(PI, Coef)) with
46
47        if Coef has CommutativeRing then
48            IntegralDomain
49
50        if Coef has CommutativeRing then
51            Algebra Coef
52
53        coerce : FUN -> %
54        coerce : % -> FUN
55        coerce : Stream Coef -> %
56        coerce : % -> Stream Coef
57
58        zeta : constant -> %
59        ++ zeta() returns the function which is constantly one
60
61        multiplicative? : (%, PI) -> Boolean
62        ++ multiplicative?(a, n) returns true if the first
63        ++ n coefficients of a are multiplicative
64
65        additive? : (%, PI) -> Boolean
66        ++ additive?(a, n) returns true if the first
67        ++ n coefficients of a are additive
68
69    Implementation ==> add
70
71        Rep := Record(function : FUN)
72
73        per(f : Rep) : % == f pretend %
74        rep(a : %) : Rep == a pretend Rep
75
76        elt(a : %, n : PI) : Coef ==
77            f : FUN := (rep a).function
78            f n
79
80        coerce(a : %) : FUN == (rep a).function
81
82        coerce(f : FUN) : % == per [f]
83
84        indices : Stream Integer
85                := integers(1)$StreamTaylorSeriesOperations(Integer)
86
87        coerce(a : %) : Stream Coef ==
88            f : FUN := (rep a).function
89            map((n : Integer) : Coef +-> f(n::PI), indices)
90               $StreamFunctions2(Integer, Coef)
91
92        coerce(f : Stream Coef) : % ==
93            ((n : PI) : Coef +-> f.(n::Integer))::%
94
95        coerce(f : %) : OutputForm == f::Stream Coef::OutputForm
96
97        1 : % ==
98            ((n : PI) : Coef +-> (if one? n then 1$Coef else 0$Coef))::%
99
100        0 : % ==
101            ((n : PI) : Coef +-> 0$Coef)::%
102
103        zeta : % ==
104            ((n : PI) : Coef +-> 1$Coef)::%
105
106        (f : %) + (g : %) ==
107            ((n : PI) : Coef +-> f(n)+g(n))::%
108
109        - (f : %) ==
110            ((n : PI) : Coef +-> -f(n))::%
111
112        (a : Integer) * (f : %) ==
113            ((n : PI) : Coef +-> a*f(n))::%
114
115        (a : Coef) * (f : %) ==
116            ((n : PI) : Coef +-> a*f(n))::%
117
118        import from IntegerNumberTheoryFunctions
119
120        (f : %) * (g : %) ==
121            conv := (n : PI) : Coef +-> _
122                 reduce((a : Coef, b : Coef) : Coef +-> a + b, _
123                        [f(d::PI) * g((n quo d)::PI) for d in divisors(n::Integer)], 0)
124                        $ListFunctions2(Coef, Coef)
125            conv::%
126
127        unit?(a : %) : Boolean == not (recip(a(1$PI))$Coef case "failed")
128
129        qrecip : (%, Coef, PI) -> Coef
130        qrecip(f : %, f1inv : Coef, n : PI) : Coef ==
131            if one? n then f1inv
132            else
133                -f1inv * reduce(_+, [f(d::PI) * qrecip(f, f1inv, (n quo d)::PI) _
134                                     for d in rest divisors(n)], 0) _
135                               $ListFunctions2(Coef, Coef)
136
137        recip f ==
138            if (f1inv := recip(f(1$PI))$Coef) case "failed" then "failed"
139            else
140                mp := (n : PI) : Coef +-> qrecip(f, f1inv, n)
141
142                mp::%::Union(%, "failed")
143
144        multiplicative?(a, n) ==
145            for i in 2..n repeat
146                fl := factorList(factor i)$Factored(Integer)
147                rl := [a.(((f.factor)::PI)^((f.exponent)::PI)) for f in fl]
148                if a.(i::PI) ~= reduce((r : Coef, s : Coef) : Coef +-> r*s, rl)
149                then
150                    output(i::OutputForm)$OutputPackage
151                    output(rl::OutputForm)$OutputPackage
152                    return false
153            true
154
155        additive?(a, n) ==
156            for i in 2..n repeat
157                fl := factorList(factor i)$Factored(Integer)
158                rl := [a.(((f.factor)::PI)^((f.exponent)::PI)) for f in fl]
159                if a.(i::PI) ~= reduce((r : Coef, s : Coef) : Coef +-> r+s, rl)
160                then
161                    output(i::OutputForm)$OutputPackage
162                    output(rl::OutputForm)$OutputPackage
163                    return false
164            true
165
166
167--Copyright (c) 2010, Martin Rubey <Martin.Rubey@math.uni-hannover.de>
168--
169--Redistribution and use in source and binary forms, with or without
170--modification, are permitted provided that the following conditions are
171--met:
172--
173--    - Redistributions of source code must retain the above copyright
174--      notice, this list of conditions and the following disclaimer.
175--
176--    - Redistributions in binary form must reproduce the above copyright
177--      notice, this list of conditions and the following disclaimer in
178--      the documentation and/or other materials provided with the
179--      distribution.
180--
181--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
182--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
183--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
184--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
185--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
186--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
187--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
188--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
189--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
190--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
191--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
192