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