{"id":11609,"date":"2024-09-27T08:28:39","date_gmt":"2024-09-27T12:28:39","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=11609"},"modified":"2024-09-28T10:48:32","modified_gmt":"2024-09-28T14:48:32","slug":"redheffer-and-mertens-continued","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/27\/redheffer-and-mertens-continued\/","title":{"rendered":"Redheffer and Mertens, Continued"},"content":{"rendered":"\r\n<div class=\"content\"><!--introduction-->\r\n<p>Shortly after I posted <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/23\/redheffer-mertens-and-one-million-dollars\/\">Redheffer, Mertens and One-Million Dollars<\/a> a few days ago, Mathworks' Pat Quillen made an important observation about computing the Mertens function.<\/p>\r\n<!--\/introduction-->\r\n<h3>Contents<\/h3>\r\n<div>\r\n<ul>\r\n<li>\r\n<a href=\"#73ae2fa0-4627-4547-a607-10ac24377ac2\"><tt>mertens<\/tt><\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#105a4af3-2ecd-4553-95b6-2771c2416e60\">Mertens function<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#35fad8fa-50a1-4b02-b629-5f287a32a9dd\">Mertens computation<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#f19f66cc-5f68-447b-83a8-43302e86ca3e\">Mertens conjecture<\/a>\r\n<\/li>\r\n<\/ul>\r\n<\/div>\r\n<h4>\r\n<tt>mertens<\/tt><a name=\"73ae2fa0-4627-4547-a607-10ac24377ac2\"><\/a>\r\n<\/h4>\r\n<p>The elements in the first column of the Redheffer matrix, <tt>A = redheffer(n)<\/tt>, are all equal to one. That dense column does not make MATLAB happy about computing <tt>det(A)<\/tt> . However, the last column of <tt>A<\/tt> has only a few nonzero elements and so Pat suggested interchanging the first and last columns before computing the determinant. This makes a world of difference. (Thanks, Pat.)<\/p>\r\n<pre class=\"codeinput\">type<span class=\"string\">mertens<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">\r\nfunction M = mertens(n)\r\n    A = redheffer(n);\r\n    M = A(1,1) - A(1,2:n)*(A(2:n,2:n)\\A(2:n,1));\r\nend\r\n<\/pre>\r\n<p>The time required to compute <tt>det(A)<\/tt> varies with the sparsity of the last column, but it is only a little more than the time to compute <tt>redheffer(n)<\/tt> in the first place.<\/p>\r\n<pre class=\"codeinput\">mertens2_time\r\n<\/pre>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/mertens3_blog_01.png\" alt=\"\"> <h4>Mertens function<a name=\"105a4af3-2ecd-4553-95b6-2771c2416e60\"><\/a>\r\n<\/h4>\r\n<p>Pat's change makes it possible to take <tt>n<\/tt> up to a quarter of a million, and beyond. Here is a new plot of the Mertens function <tt>M(n)<\/tt> and the <tt>sqrt(n)<\/tt> bounds of the Mertens conjecture.<\/p>\r\n<pre class=\"codeinput\">mertens_plot\r\n<\/pre>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/mertens3_blog_02.png\" alt=\"\"> <p>There are a quarter of a million points in the data for this plot. Fortunately, the .PNG file used for the blog only needs to sample the data.<\/p>\r\n<h4>Mertens computation<a name=\"35fad8fa-50a1-4b02-b629-5f287a32a9dd\"><\/a>\r\n<\/h4>\r\n<p>The job that I ran on my laptop to compute one-quarter of a million values of <tt>M(n)<\/tt> is still running. It currently is past 0.35 million and takes less than two seconds for each value. I may keep the job running over the weekend, just to see how far it gets.<\/p>\r\n<p>The task is embarrassingly parallel. If I had a pool with a million processors, I could have each processor compute one value. I would then just have to collect the results, but that doesn't involve any arithmetic.<\/p>\r\n<h4>Mertens conjecture<a name=\"f19f66cc-5f68-447b-83a8-43302e86ca3e\"><\/a>\r\n<\/h4>\r\n<p>You can see from the plot why late 19th- and early 20th-century mathematicians believed that the Mertens conjecture,<\/p>\r\n<pre>   |M(n)| &lt; sqrt(n) for all n,<\/pre>\r\n<p>might be true. It is hard to imagine that the plot of <tt>M(n)<\/tt> ever escapes <tt>sqrt(n)<\/tt>.<\/p>\r\n<p>We now know that <tt>M(n)<\/tt> eventually does escape, but only barely and only briefly. We also know that all the computation we can do with determinants of Redheffer's matrix will never prove or disprove the conjecture or win that million-dollar prize.<\/p>\r\n<script language=\"JavaScript\"> <!-- \r\n    function grabCode_6fdcc34df9a54e3fa70cce207febb4e0() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='6fdcc34df9a54e3fa70cce207febb4e0 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 6fdcc34df9a54e3fa70cce207febb4e0';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2024 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script>\r\n<p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\">\r\n<br>\r\n<a href=\"javascript:grabCode_6fdcc34df9a54e3fa70cce207febb4e0()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript>\r\n<\/span><\/a>\r\n<br>\r\n<br>\r\n      Published with MATLAB&reg; R2024a<br>\r\n<\/p>\r\n<\/div>\r\n<!--\r\n6fdcc34df9a54e3fa70cce207febb4e0 ##### SOURCE BEGIN #####\r\n%% Redheffer and Mertens, Continued\r\n% Shortly after I posted\r\n% <https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/23\/redheffer-mertens-and-one-million-dollars\/\r\n% Redheffer, Mertens and One-Million Dollars>\r\n% a few days ago, Mathworks' Pat Quillen made an important observation\r\n% about computing the Mertens function.\r\n\r\n%% |mertens|\r\n% The elements in the first column of the Redheffer matrix,\r\n% |A = redheffer(n)|, are all equal to one.  That dense column \r\n% does not make MATLAB happy about computing |det(A)| .\r\n% However, the last column of |A| has only a few nonzero elements and so\r\n% Pat suggested interchanging the first and last columns\r\n% before computing the determinant.  This makes a world of difference.\r\n% (Thanks, Pat.)\r\n\r\n   type mertens\r\n\r\n%% \r\n% The time required to compute |det(A)| varies with the sparsity of\r\n% the last column, but it is only a little more than the time\r\n% to compute |redheffer(n)| in the first place. \r\n\r\n   mertens2_time\r\n\r\n%% Mertens function\r\n% Pat's change makes it possible to take |n| up to a quarter of a million,\r\n% and beyond.  Here is a new plot of the Mertens function |M(n)| and the\r\n% |sqrt(n)| bounds of the Mertens conjecture.\r\n\r\n   mertens_plot\r\n\r\n%% \r\n% There are a quarter of a million points in the data for this plot.\r\n% Fortunately, the .PNG file used for the blog only needs to sample\r\n% the data.\r\n\r\n%% Mertens computation\r\n% The job that I ran on my laptop to compute one-quarter of\r\n% a million values of |M(n)| is still running.  It currently\r\n% is past 0.35 million and takes less than two seconds for each value.\r\n% I may keep the job running over the weekend, just to see how\r\n% far it gets.\r\n%\r\n% The task is embarrassingly parallel.  If I had a pool with \r\n% a million processors, I could have each processor compute one\r\n% value.  I would then just have to collect the results, but that\r\n% doesn't involve any arithmetic.\r\n\r\n%% Mertens conjecture\r\n% You can see from the plot why late 19th- and early 20th-century\r\n% mathematicians believed that the Mertens conjecture,\r\n%\r\n%     |M(n)| < sqrt(n) for all n,\r\n%\r\n% might be true.\r\n% It is hard to imagine that the plot of |M(n)| ever escapes\r\n% |sqrt(n)|.  \r\n%\r\n% We now know that |M(n)| eventually does escape,\r\n% but only barely and only briefly.  We also know that all the\r\n% computation we can do with determinants of Redheffer's matrix\r\n% will never prove or disprove the conjecture or win that\r\n% million-dollar prize.\r\n\r\n##### SOURCE END ##### 6fdcc34df9a54e3fa70cce207febb4e0\r\n-->\r\n","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/mertens2_plot_small-1.png\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><!--introduction-->\r\n<p>Shortly after I posted <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/23\/redheffer-mertens-and-one-million-dollars\/\">Redheffer, Mertens and One-Million Dollars<\/a> a few days ago, Mathworks' Pat Quillen made an important observation about computing the Mertens function.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/27\/redheffer-and-mertens-continued\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":11624,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[5,4,36],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/11609"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=11609"}],"version-history":[{"count":3,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/11609\/revisions"}],"predecessor-version":[{"id":11642,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/11609\/revisions\/11642"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media\/11624"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=11609"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=11609"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=11609"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}