Processing math: 18%

Tuesday, March 29, 2011

Dirichlet convolution is commutative

The Dirichlet convolutions was introduced here.  The following illustrates a proof technique that avoids writing nd over and over again.
Theorem
Proof:-
For any n we have
   (f*g)(n) 
= n=cdf(c)g(d)
= n=cdf(d)g(c)  [ as d runs through all divisors of  n, so does c=nd ]
= n=cdg(c)f(d)
= (g*f)(n) 
(proven) 

The proof technique can be extended to prove the associativity law.

No comments:

Post a Comment

Comment répondez vous?

over and ...', 'featuredImage': 'https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vIagmEouLVX6Sh8OdwaOV2kIyfQfrLBRrMx-J78qRgF6KdAegV6x14SntxqNHXI8Y7oJQdgRuqdqkHEXJ9zj8GDhTWnB6ntrLpEbv0Z5M', 'url': 'https://lefouque.blogspot.com/2011/03/dirichlet-convolution-is-commutative.html', 'type': 'item', 'isSingleItem': true, 'isMultipleItems': false, 'isError': false, 'isPage': false, 'isPost': true, 'isHomepage': false, 'isArchive': false, 'isLabelSearch': false, 'postId': 1147972456793829133}}]); _WidgetManager._RegisterWidget('_NavbarView', new _WidgetInfo('Navbar1', 'navbar', document.getElementById('Navbar1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_HeaderView', new _WidgetInfo('Header1', 'header', document.getElementById('Header1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_BlogView', new _WidgetInfo('Blog1', 'main', document.getElementById('Blog1'), {'cmtInteractionsEnabled': false, 'lightboxEnabled': true, 'lightboxModuleUrl': 'https://www.blogger.com/static/v1/jsbin/2721683219-lbx__en_gb.js', 'lightboxCssUrl': 'https://www.blogger.com/static/v1/v-css/1964470060-lightbox_bundle.css'}, 'displayModeFull')); _WidgetManager._RegisterWidget('_AdSenseView', new _WidgetInfo('AdSense1', 'sidebar-right-1', document.getElementById('AdSense1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_FollowersView', new _WidgetInfo('Followers1', 'sidebar-right-1', document.getElementById('Followers1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_BlogArchiveView', new _WidgetInfo('BlogArchive1', 'sidebar-right-1', document.getElementById('BlogArchive1'), {'languageDirection': 'ltr', 'loadingMessage': 'Loading\x26hellip;'}, 'displayModeFull')); _WidgetManager._RegisterWidget('_ProfileView', new _WidgetInfo('Profile1', 'sidebar-right-1', document.getElementById('Profile1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_HTMLView', new _WidgetInfo('HTML1', 'sidebar-right-1', document.getElementById('HTML1'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_HTMLView', new _WidgetInfo('HTML2', 'sidebar-right-1', document.getElementById('HTML2'), {}, 'displayModeFull')); _WidgetManager._RegisterWidget('_AttributionView', new _WidgetInfo('Attribution1', 'footer-3', document.getElementById('Attribution1'), {}, 'displayModeFull'));