Convolución de Dirichlet

Tarea #6
Fundamentos de la Inform´tica I
a
Renata Mella
201273010-4
19 de Agosto de 2013
1. Sea A el conjunto de funciones aritm´ticas. Se define la convoluci´n de Dirichlet entre funciones
e
o
aritm´ticas:
e
(f ∗ g)(n) =
f (a)g(b)
ab=n

Podemos sumar funciones de la forma habitual:
(f + g)(n) = f (n) + g(n)
donde claramente la funci´n 0 es el elemento neutro, con lo que elconjunto de funciones
o
aritm´ticas con la suma es un grupo abeliano.
e
a) Demuestre que ∗ es cerrada en A, con lo que es una operaci´n.
o
Soluci´n: Sea f, g ∈ A. Como vimos anteriormente, se puede definir la convoluci´n de
o
o
Dirichlet sobre ´ste conjunto como:
e
(f ∗ g)(n) =

f (a)g(b)
ab=n

Como ab = n y n ∈ N, por propiedad notamos que a, b ∈ N. Si a, b ∈ N y f, g ∈ A,
entonces f(a), f (b) ∈ A y en consecuencia, f (a)f (b) ∈ A.
Como la convoluci´n es una suma de f (a)(b) es f´cil darse cuenta que la sumatoria de
o
a
´stas tambi´n pertenece a A, concluyendo as´ que la convoluci´n es una operaci´n cerrada.
e
e
ı
o
o
b) Demuestre que ∗ es conmutativa.
Soluci´n: Tenemos que ab = ba = n y que f (a)g(b) = g(b)f (a). En base a esto, podemos
o
escribir la convoluci´nde Dirichlet como:
o
(f ∗ g)(n) =

f (a)g(b)
ab=n

=

g(b)f (a)
ba=n

=g∗f
Por lo tanto, la convoluci´n es conmutativa.
o
c) Demuestre que ∗ es asociativa
Soluci´n: Teniendo en cuenta las demostraciones anteriores sobre conmutatividad y
o
agregando adem´s que h ∈ A y c, d, m ∈ N, escribiremos a continuaci´n la convoluci´n
a
o
o
como:

1

(f ∗ (g ∗ h))(n) =

f (a)
ad=ng(b)h(c)
bc=d

=

f (a)g(b)h(c)
abc=n

=

(

f (a)g(b))h(c)

mc=n ab=m

((f ∗ g)(m))h(c)

=
mc=n

= ((f ∗ g) ∗ h)(n)
d ) Determine el elemento neutro (n) para ∗ en A.
Soluci´n: EL elemento neutro debe cumplir que:
o
(f ∗ )(n) = ( ∗ f )(n) = f
Para que esto se cumpla, la funci´n (n) debe ser capaz de:
o
(f ∗ )(n) =

f (a) (b)
ab=n

= f (n) (1) +
1

f (a) (b)ab=n,b=1
0

= f (n) (1)
= f (n)
En el desarrollo vimos que cuando n = 1, (n) debe valer 1 para que solamente importe
el t´rmino al cual acompa˜a. Ahora, si n = 1, (n) debe valer 0 para ser capaz de anular
e
n
a cualquier t´rmino que lo acompa˜e. Viendo esto, podemos construir una funci´n (n)
e
n
o
que sea nuestro neutro:
1, si n = 1;
(n) =
0, si n = 1.
Esta funci´n se llamafunci´n identidad y en general, es el neutro de muchas otras funo
o
ciones aritm´ticas.
e
e) Dada una funci´n aritm´tica f , determine cu´ndo existe su inversa de Dirichlet, f −1 tal
o
e
a
que f ∗ f −1 = .
Soluci´n: Para encontrar cu´ndo una funci´n tiene inversa, como ´sto depende del valor
o
a
o
e
de (n), habr´ que analizarlo en ambos casos. Cuando n = 1, (1) = 1 y la convoluci´n
a
onos queda:
(f ∗ f −1 )(1) = 1
f (a)f −1 (b) = 1
ab=1

f (1)f −1 (1) = 1
ab=1

f (1)f −1 (1) = 1
f −1 (1) =

1
f (1)

(esto, considerando que la unica manera de que ab = 1 es que ambos, a y b sean 1). Esto
´
es posible s´lo si f (1) = 0.
o

2

Ahora consideremos el caso en que n = 1; cuando esto sucede, (n) = 0 y prodeceremos
nuestro analisis similar a lo hecho en el puntoanterior:
(f ∗ f −1 )(n) = 0
f (a)f −1 (b) = 0
ab=n

f (1)f −1 (n) +

f (a)f −1 (b) = 0
ab=n,b=0

f −1 = −

1
f (1)

f (a)f −1 (b)
ab=n

De ´sta forma, mantenemos la condici´n antes encontrada de que f (1) = 1 para que el
e
o
valor de f −1 exista.
f ) Demuestre que la convoluci´n de Dirichlet distribuye sobre la suma:
o
f ∗ (g + h) = f ∗ g + f ∗ h
Soluci´n: Considerandonuevamente que h ∈ A, escribimos la convoluci´n de la siguiente
o
o
forma:
(f ∗ (g + h))(n) =

f (a)(g + h)(b)
ab=n

=

f (a)(g(b) + h(b))
ab=n

=

(f (a)g(b) + f (a)h(b))
ab=n

= (f ∗ g)(n) + (f ∗ h)(n)
Comprobando as´ la distributividad de la convoluci´n.
ı
o
Concluya que A con estas operaciones es un anillo conmutativo.
Soluci´n: Consideremos la primera operaci´n como la...