{"id":11534,"date":"2024-09-23T13:12:35","date_gmt":"2024-09-23T17:12:35","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=11534"},"modified":"2024-09-24T15:59:03","modified_gmt":"2024-09-24T19:59:03","slug":"redheffer-mertens-and-one-million-dollars","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/23\/redheffer-mertens-and-one-million-dollars\/","title":{"rendered":"Redheffer, Mertens and One-Million Dollars"},"content":{"rendered":"\r\n<div class=\"content\"><!--introduction-->\r\n<p>I didn't know anything about these topics until a couple of weeks ago. Now I can't stop thinking about them.<\/p>\r\n<div>\r\n<ul>\r\n<li>Redheffer's matrix has been in the <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2019\/06\/24\/bohemian-matrices-in-the-matlab-gallery\/\">MATLAB Gallery<\/a> for a long time, but I have ignored it .<\/li>\r\n<li>Redheffer's matrix can be used to compute Mertens function and investigate the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Mertens_conjecture\">Mertens conjecture<\/a>.<\/li>\r\n<li>A proof of the Mertens conjecture would also provide a proof of the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Riemann_hypothesis\">Riemann hypothesis<\/a>.<\/li>\r\n<li>For nearly a century, all the available computational evidence indicated that the Mertens conjecture was likely to be true.<\/li>\r\n<li>The Riemann hypothesis is the most important unsolved problem in mathematics and wins a Clay prize worth <a href=\"https:\/\/www.claymath.org\/millennium\/riemann-hypothesis\">one-million dollars<\/a>.<\/li>\r\n<li>MATLAB's sparse matrix functions turn out to be useful in an investigation of Redheffer's matrix and the Mertens conjecture.<\/li>\r\n<li>However, it has been known since 1985 that the Mertens conjecture is false.<\/li>\r\n<\/ul>\r\n<\/div>\r\n<!--\/introduction-->\r\n<h3>Contents<\/h3>\r\n<div>\r\n<ul>\r\n<li>\r\n<a href=\"#2d146fb3-e642-4534-8abc-f6bd4172cb22\">Redheffer's Matrix<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#c96693b1-3919-4e67-a170-6cce4441d01f\">M&ouml;bius Function<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#836b6d3d-e1b4-4745-ad03-b981f45f27f1\">Mertens Function<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#0f0d8bde-8d42-4c35-8772-b1ffcff4f493\">Mertens Conjecture<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#9868ed40-d800-45dd-86e2-689947ebfa96\">Mertens Meets Redheffer<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#4d6ae617-5d39-451e-8830-05d5c5b708ca\">Redheffer Sparsity<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#97777758-987d-412a-818b-1699b3e29e48\"><tt>redheffer<\/tt><\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#dbc5bd95-bd9c-416a-ac57-cfecef904a51\">Sparse LU<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#9a68266e-576b-4c95-9da1-cace89537c2a\"><tt>mertens<\/tt><\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#8ec87641-a59d-493a-ab13-07ab2c281490\">Mertens Conjecture Is False<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#21e01bb7-5064-4d67-8944-ff6723e7cd3f\">Postscripts<\/a>\r\n<\/li>\r\n<li>\r\n<a href=\"#70930006-7dce-4504-9b07-915062743cee\">References<\/a>\r\n<\/li>\r\n<\/ul>\r\n<\/div>\r\n<h4>Redheffer's Matrix<a name=\"2d146fb3-e642-4534-8abc-f6bd4172cb22\"><\/a>\r\n<\/h4>\r\n<p>\r\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Raymond_Redheffer\">Raymond Redheffer<\/a> (1921-2005) was an American mathematician, a professor at UCLA for 55 years, the author of several popular textbooks, the inventor of the electronic game <a href=\"https:\/\/en.wikipedia.org\/wiki\/Nim\">Nim<\/a> and, with Ray and Charles Eames, the creator of a four-meter long poster <a href=\"https:\/\/www.worthpoint.com\/worthopedia\/1966-ray-charles-eames-office-men-1724813663\">Men of Modern Mathematics<\/a>.<\/p>\r\n<p>Redheffer's matrix is a matrix of zeros and ones. <tt>A(k,j)<\/tt> equals one if <tt>j<\/tt> is a divisor of <tt>k<\/tt>. In addition, the first column is all ones.<\/p>\r\n<pre>  function A = redheffer(n)\r\n      k = 1:n;\r\n      j = k';\r\n      A = (mod(k,j) == 0);\r\n      A(:,1) = 1;\r\n  end<\/pre>\r\n<p>Or<\/p>\r\n<pre>  A = gallery('redheff',n)<\/pre>\r\n<p>Here is the 10-by-10.<\/p>\r\n<pre class=\"codeinput\">A=redheffer(10);disp(full(A))\r\n<\/pre>\r\n<pre class=\"codeoutput\">     1     1     1     1     1     1     1     1     1     1\r\n     1     1     0     1     0     1     0     1     0     1\r\n     1     0     1     0     0     1     0     0     1     0\r\n     1     0     0     1     0     0     0     1     0     0\r\n     1     0     0     0     1     0     0     0     0     1\r\n     1     0     0     0     0     1     0     0     0     0\r\n     1     0     0     0     0     0     1     0     0     0\r\n     1     0     0     0     0     0     0     1     0     0\r\n     1     0     0     0     0     0     0     0     1     0\r\n     1     0     0     0     0     0     0     0     0     1\r\n<\/pre>\r\n<p>And here is a spy plot of the 200-by-200.<\/p>\r\n<pre class=\"codeinput\">A=redheffer(200);spy(A)title(<span class=\"string\">'redheffer(200)'<\/span>)\r\n<\/pre>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/mertens_blog3_01.png\" alt=\"\"> <h4>M&ouml;bius Function<a name=\"c96693b1-3919-4e67-a170-6cce4441d01f\"><\/a>\r\n<\/h4>\r\n<p>The M&ouml;bius function was introduced in 1832 by German mathematician August M&ouml;bius and is ubiquitous in the study of prime numbers. For positive integers <tt>n<\/tt>, <tt>\u03bc(n)<\/tt> is<\/p>\r\n<div>\r\n<ul>\r\n<li>\r\n<tt>0<\/tt> if <tt>n<\/tt> has a squared prime factor,<\/li>\r\n<li>\r\n<tt>+1<\/tt> if <tt>n<\/tt> is square-free and has an even number of prime factors,<\/li>\r\n<li>\r\n<tt>-1<\/tt> if <tt>n<\/tt> is square-free and has an odd number of prime factors.<\/li>\r\n<\/ul>\r\n<\/div>\r\n<h4>Mertens Function<a name=\"836b6d3d-e1b4-4745-ad03-b981f45f27f1\"><\/a>\r\n<\/h4>\r\n<p>\r\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Franz_Mertens\">Franz Mertens<\/a> (1840-1927) was a Polish mathematician who spent most of his career in Austria at the University of Vienna. Here is a <a href=\"https:\/\/mathshistory.st-andrews.ac.uk\/Biographies\/Mertens\/\">link<\/a> to a biography of Mertens at the University of St. Andrews MacTutor project.<\/p>\r\n<p>The Mertens function is sum of values of the M&ouml;bius function. For a positive integer <tt>n<\/tt>, the Mertens function is<\/p>\r\n<pre>   M(n) = sum(\u03bc(1:n))<\/pre>\r\n<p>So <tt>M(n)<\/tt> is the difference between the number of square-free integers with an even number of prime factors and those with an odd number.<\/p>\r\n<p>This graphic shows <tt>M(n)<\/tt> for <tt>n = 1:100000<\/tt>.<\/p>\r\n<pre class=\"codeinput\">mertens_plot_2\r\n<\/pre>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/mertens_blog3_02.png\" alt=\"\"> <h4>Mertens Conjecture<a name=\"0f0d8bde-8d42-4c35-8772-b1ffcff4f493\"><\/a>\r\n<\/h4>\r\n<p>The Mertens function <tt>M(n)<\/tt> fluctuates wildly and grows slowly with increasing <tt>n<\/tt>. The graphic shows that M(n) is easily bounded by of <tt>sqrt(n)<\/tt> and <tt>-sqrt(n)<\/tt>, at least for <tt>n<\/tt> less than <tt>100k<\/tt>. The Mertens conjecture is that this continues for larger <tt>n<\/tt>.<\/p>\r\n<pre>  -sqrt(n) &lt; M(n) &lt; sqrt(n) for all n<\/pre>\r\n<p>The conjecture was included in a letter from Stieltjes to Hermite in 1895 and in a paper by Mertens in 1897. The result is important since a proof of the Mertens conjecture would imply the truth of the Riemann hypothesis.<\/p>\r\n<h4>Mertens Meets Redheffer<a name=\"9868ed40-d800-45dd-86e2-689947ebfa96\"><\/a>\r\n<\/h4>\r\n<p>I became interested in all this when I learned that the determinant of the MATLAB Gallery matrix which I have ignored for years is related to the Riemann hypothesis and the million-dollar prize.<\/p>\r\n<pre>  M(n) = det(gallery('redheff',n))<\/pre>\r\n<p>I know very little about the distribution of prime numbers and computing values of the M&ouml;bius function. On the other hand, I know a lot about numerical linear algebra and computing determinants.<\/p>\r\n<p>In general, I am dead set against computing determinants. They are often used to check for singularity or to somehow compute eigenvalues. But here the determinant is an integer counter of modest size.<\/p>\r\n<h4>Redheffer Sparsity<a name=\"4d6ae617-5d39-451e-8830-05d5c5b708ca\"><\/a>\r\n<\/h4>\r\n<p>Computing <tt>M(n)<\/tt> directly with <tt>det(redheffer(n))<\/tt> requires <tt>O(n^2)<\/tt> space and <tt>O(n^3)<\/tt> time and is not practical for large <tt>n<\/tt>.<\/p>\r\n<p>However, <tt>A = redheffer(n)<\/tt> is modestly sparse. Here is the fraction of nonzeros.<\/p>\r\n<pre>  s = nnz(A)\/n^2<\/pre>\r\n<pre class=\"codeinput\">disp(sparsity)\r\n<\/pre>\r\n<pre class=\"codeoutput\">      n         s    \r\n    _____    ________\r\n    10000    0.001037\r\n    20000    0.000553\r\n    30000    0.000382\r\n    40000    0.000294\r\n    50000    0.000239\r\n    60000    0.000203\r\n    70000    0.000176\r\n    80000    0.000156\r\n    90000    0.000139\r\n    1e+05    0.000127\r\n<\/pre>\r\n<p>Taking advantage of this sparsity and the MATLAB tools for sparse matrix computation provide linear space complexity and perhaps <tt>O(n^2)<\/tt> time complexity.<\/p>\r\n<h4>\r\n<tt>redheffer<\/tt><a name=\"97777758-987d-412a-818b-1699b3e29e48\"><\/a>\r\n<\/h4>\r\n<p>Here is MATLAB code to generate a sparse <tt>redheffer(n)<\/tt> without creating any full intermediate matrices.<\/p>\r\n<pre class=\"codeinput\">type<span class=\"string\">redheffer<\/span>\r\n<\/pre>\r\n<pre class=\"codeoutput\">\r\nfunction A = redheffer(n)\r\n    j(1:n) = (1:n)';\r\n    k(1:n) = 1;\r\n    m = n;\r\n    for i = 2:n\r\n        t = [1 i:i:n]';\r\n        p = length(t);\r\n        j(m+(1:p)) = t;\r\n        k(m+(1:p)) = i;\r\n        m = m+p;\r\n    end\r\n    A = sparse(k,j,1,n,n);\r\nend\r\n<\/pre>\r\n<p>As expected, we see that the execution time for <tt>redheffer(n)<\/tt> is a linear function of <tt>n<\/tt>. (The space required also grows linearly.)<\/p>\r\n<pre class=\"codeinput\">redheffer_time\r\n<\/pre>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/mertens_blog3_03.png\" alt=\"\"> <h4>Sparse LU<a name=\"dbc5bd95-bd9c-416a-ac57-cfecef904a51\"><\/a>\r\n<\/h4>\r\n<p>The MATLAB Gaussian elimination function <tt>lu<\/tt> with one sparse input and four sparse outputs is designed for solving sparse linear systems.<\/p>\r\n<pre>  [L,U,P,Q] = lu(A)<\/pre>\r\n<p>Written primarily by Tim Davis and included in his UMFPACK package, the function uses an unsymmetric pattern multifrontal pivoting strategy to find permutations <tt>P<\/tt> and <tt>Q<\/tt> so that <tt>L<\/tt> is lower triangular, <tt>U<\/tt> is upper triangular and<\/p>\r\n<pre>  P*A*Q = L*U<\/pre>\r\n<p>Consequently, the determinant of <tt>A<\/tt> is the product of four easily computed determinants.<\/p>\r\n<pre>  det(A) = det(L)*det(U)*det(P)*det(Q)<\/pre>\r\n<p>The pivoting strategy aims to reduce fill-in while maintaining numerical stability.<\/p>\r\n<p>For example, here are <tt>L<\/tt> and <tt>U<\/tt> for the Redheffer matrix in the spy plot near the top of this blog post.<\/p>\r\n<pre class=\"codeinput\">closeA=redheffer(200);[L,U,P,Q]=lu(A);spy(L|U)title(<span class=\"string\">'L|U'<\/span>)\r\n<\/pre>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/mertens_blog3_04.png\" alt=\"\"> <p>And here are the four determinants.<\/p>\r\n<pre class=\"codeinput\">dets=[det(L),det(U),det(P),det(Q)];disp(dets)\r\n<\/pre>\r\n<pre class=\"codeoutput\">     1    -8    -1    -1\r\n<\/pre>\r\n<p>Finally, <tt>M(200)<\/tt> is<\/p>\r\n<pre class=\"codeinput\">M_200=det(L)*det(U)*det(P)*det(Q)\r\n<\/pre>\r\n<pre class=\"codeoutput\">M_200 =\r\n    -8\r\n<\/pre>\r\n<h4>\r\n<tt>mertens<\/tt><a name=\"9a68266e-576b-4c95-9da1-cace89537c2a\"><\/a>\r\n<\/h4>\r\n<p>Mertens function can be computed with four lines of code.<\/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    der = @(x) full(round(prod(diag(x))));\r\n    A = redheffer(n);\r\n    [L,U,P,Q] = lu(A);\r\n    M = der(L)*der(U)*det(P)*det(Q);\r\nend\r\n<\/pre>\r\n<p>Execution time for <tt>mertens<\/tt> is dominated by the time in sparse <tt>lu<\/tt>. The time required to compute the four determinants is an order of magnitude smaller than the other two.<\/p>\r\n<p>Experimentally, we see that the time complexity of sparse <tt>lu<\/tt> is <tt>O(n^2)<\/tt>, but we have no proof.<\/p>\r\n<pre class=\"codeinput\">mertens_time2\r\n<\/pre>\r\n<img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/mertens_blog3_05.png\" alt=\"\"> <h4>Mertens Conjecture Is False<a name=\"8ec87641-a59d-493a-ab13-07ab2c281490\"><\/a>\r\n<\/h4>\r\n<p>The Mertens conjecture stood for nearly 100 years before it was proved false in 1985 by Andrew Odlyzko and Herman te Riele. The authors present indirect proofs that<\/p>\r\n<pre>  lim sup (n -&gt; inf) M(n)\/sqrt(n) &gt; 1.06<\/pre>\r\n<pre>  lim inf (n -&gt; inf) M(n)\/sqrt(n) &lt; -1.009<\/pre>\r\n<p>Odlyzko and te Riele do not actually produce any value of <tt>n<\/tt> for which <tt>M(n) &gt; sqrt(x)<\/tt>. They suspect that any Mertens conjecture counterexample requires <tt>n<\/tt> &gt; $10^{30}$, which is far beyond any computation possible today.<\/p>\r\n<p>Odlyzko and te Riele also describe several complete tabulations of <tt>M(n)<\/tt> for <tt>n<\/tt> as large as $7.8 \\cdot 10^{9}$ . These computations do not use Redheffer determinants.<\/p>\r\n<h4>Postscripts<a name=\"21e01bb7-5064-4d67-8944-ff6723e7cd3f\"><\/a>\r\n<\/h4>\r\n<p>To tell the truth, I did not really expect to find any Mertens or Riemann counterexamples. I did, however, enjoy computing determinants for the first time and discovering an unexpected use for sparse LU.<\/p>\r\n<p>Thanks a lot to Tim Davis for his help with this post.<\/p>\r\n<h4>References<a name=\"70930006-7dce-4504-9b07-915062743cee\"><\/a>\r\n<\/h4>\r\n<p>A. M. Odlyzko and H. J. J. te Riele, \"Disproof of the Mertens conjecture\", <i>Journal f&uuml;r die reine und angewandte Mathematik<\/i>, Vol. 357 (1985), Pages138-160. <a href=\"https:\/\/eudml.org\/doc\/152712\">https:\/\/eudml.org\/doc\/152712<\/a>.<\/p>\r\n<p>Timothy A. Davis, \"A Column Pre-Ordering Strategy for the Unsymmetric-Pattern Multifrontal Method\", <i>ACM Transactions on Mathematical Software<\/i>, Vol. 30, No. 2, June 2004, Pages 165&ndash;195. <a href=\"https:\/\/dl.acm.org\/doi\/abs\/10.1145\/992200.992205\">https:\/\/dl.acm.org\/doi\/abs\/10.1145\/992200.992205<\/a>.<\/p>\r\n<script language=\"JavaScript\"> <!-- \r\n    function grabCode_482a8da5c0f748dc9f2af6f28abde6ac() {\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='482a8da5c0f748dc9f2af6f28abde6ac ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 482a8da5c0f748dc9f2af6f28abde6ac';\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_482a8da5c0f748dc9f2af6f28abde6ac()\"><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\n482a8da5c0f748dc9f2af6f28abde6ac ##### SOURCE BEGIN #####\r\n%% Redheffer, Mertens, Riemann and $1M\r\n% I didn't know anything about these topics until a couple of\r\n% weeks ago. Now I can't stop thinking about them.\r\n%\r\n% * Redheffer's matrix has been in the \r\n% <https:\/\/blogs.mathworks.com\/cleve\/2019\/06\/24\/bohemian-matrices-in-the-matlab-gallery\/\r\n% MATLAB Gallery> for a long time, but I have ignored it        .\r\n% * Redheffer's matrix can be used to compute Mertens function and\r\n% investigate the\r\n% <https:\/\/en.wikipedia.org\/wiki\/Mertens_conjecture\r\n% Mertens conjecture>.\r\n% * A proof of the Mertens conjecture would also provide a proof of the\r\n% <https:\/\/en.wikipedia.org\/wiki\/Riemann_hypothesis Riemann hypothesis>.\r\n% * For nearly a century, all the available computational evidence\r\n% indicated that the Mertens conjecture was likely to be true.\r\n% * The Riemann hypothesis is the most important unsolved problem in\r\n% mathematics and wins a Clay prize worth \r\n% <https:\/\/www.claymath.org\/millennium\/riemann-hypothesis\r\n% one-million dollars>.\r\n% * MATLAB's sparse matrix functions turn out to be useful\r\n% in an investigation of Redheffer's matrix and the Mertens conjecture.\r\n% * However, it has been known since 1985 that the Mertens\r\n% conjecture is false.\r\n\r\n%% Redheffer's Matrix\r\n% <https:\/\/en.wikipedia.org\/wiki\/Raymond_Redheffer Raymond Redheffer>\r\n% (1921-2005) was an American mathematician, a professor at UCLA for\r\n% 55 years, the author of several popular textbooks, the inventor\r\n% of the electronic game <https:\/\/en.wikipedia.org\/wiki\/Nim Nim>   \r\n% and, with Ray and Charles Eames, the creator of a four-meter long poster\r\n% <https:\/\/www.worthpoint.com\/worthopedia\/1966-ray-charles-eames-office-men-1724813663\r\n% Men of Modern Mathematics>.\r\n%\r\n% Redheffer's matrix is a matrix of zeros and ones.\r\n% |A(k,j)| equals one if |j| is a divisor of |k|.\r\n% In addition, the first column is all ones.\r\n%\r\n%    function A = redheffer(n)\r\n%        k = 1:n;\r\n%        j = k';\r\n%        A = (mod(k,j) == 0);\r\n%        A(:,1) = 1;\r\n%    end\r\n%\r\n% Or\r\n%\r\n%    A = gallery('redheff',n)\r\n%\r\n% Here  is the 10-by-10.\r\n\r\n    A = redheffer(10);\r\n    disp(full(A))\r\n\r\n%%\r\n% And here is a spy plot of the 200-by-200.\r\n\r\n    A = redheffer(200);\r\n    spy(A)\r\n    title('redheffer(200)')\r\n\r\n%% M\u00f6bius Function\r\n% The M\u00f6bius function was introduced in 1832 by German mathematician\r\n% August M\u00f6bius and is ubiquitous in the study of prime numbers.\r\n% For positive integers |n|, |\u03bc(n)| is\r\n%\r\n% * |0| if |n| has a squared prime factor,\r\n% * |+1| if |n| is square-free and has an even number of prime factors,\r\n% * |-1| if |n| is square-free and has an odd number of prime factors.\r\n%\r\n%% Mertens Function\r\n% <https:\/\/en.wikipedia.org\/wiki\/Franz_Mertens Franz Mertens>\r\n% (1840-1927) was a Polish mathematician who spent most of his\r\n% career in Austria at the University of Vienna.\r\n% Here is a\r\n% <https:\/\/mathshistory.st-andrews.ac.uk\/Biographies\/Mertens\/\r\n% link> to a biography of Mertens at the University of St. Andrews\r\n% MacTutor project.\r\n%\r\n% The Mertens function is sum of values of the M\u00f6bius function.\r\n% For a positive integer |n|, the Mertens function is\r\n%\r\n%     M(n) = sum(\u03bc(1:n))\r\n%\r\n% So |M(n)| is the difference between the number of square-free\r\n% integers with an even number of prime factors and those with an\r\n% odd number.\r\n%\r\n% This graphic shows |M(n)| for |n = 1:100000|.\r\n\r\n    mertens_plot_2\r\n\r\n%% Mertens Conjecture\r\n% The Mertens function |M(n)| fluctuates wildly and grows slowly with\r\n% increasing |n|.  The graphic shows that M(n) is easily bounded\r\n% by of |sqrt(n)| and |-sqrt(n)|, at least for |n| less than |100k|.\r\n% The Mertens conjecture is that this continues for larger |n|.\r\n% \r\n%    -sqrt(n) < M(n) < sqrt(n) for all n\r\n%\r\n% The conjecture was included in a letter from Stieltjes to\r\n% Hermite in 1895 and in a paper by Mertens in 1897.\r\n% The result is important since a proof of the Mertens conjecture\r\n% would imply the truth of the Riemann hypothesis.\r\n\r\n%% Mertens Meets Redheffer\r\n% I became interested in all this when I learned that\r\n% the determinant of the MATLAB Gallery matrix which I have\r\n% ignored for years is related to the Riemann hypothesis and\r\n% the million-dollar prize.\r\n%\r\n%    M(n) = det(gallery('redheff',n))\r\n%\r\n% I know very little about the distribution of prime numbers and\r\n% computing values of the M\u00f6bius function.  On the other hand,\r\n% I know a lot about numerical linear algebra and computing determinants.\r\n%\r\n% In general, I am dead set against computing determinants.\r\n% They are often used to check for singularity or to somehow\r\n% compute eigenvalues.  But here the determinant is an\r\n% integer counter of modest size.\r\n\r\n%% Redheffer Sparsity\r\n% Computing |M(n)| directly with |det(redheffer(n))| requires\r\n% |O(n^2)| space and |O(n^3)| time and is not practical for\r\n% large |n|.\r\n%\r\n% However, |A = redheffer(n)| is modestly sparse.\r\n% Here is the fraction of nonzeros.\r\n% \r\n%    s = nnz(A)\/n^2\r\n     \r\n     disp(sparsity)\r\n\r\n%% \r\n% Taking advantage of this sparsity and the MATLAB tools for\r\n% sparse matrix computation provide\r\n% linear space complexity and perhaps |O(n^2)| time complexity.\r\n\r\n%% |redheffer|\r\n% Here is MATLAB code to generate a sparse |redheffer(n)| without\r\n% creating any full intermediate matrices.\r\n\r\n\r\n    type redheffer\r\n\r\n%%\r\n% As expected, we see that the execution time for |redheffer(n)|\r\n% is a linear function of |n|.  (The space required also grows linearly.)\r\n\r\n    redheffer_time\r\n\r\n%% Sparse LU\r\n% The MATLAB Gaussian elimination function |lu| with one sparse\r\n% input and four sparse outputs\r\n% is designed for solving sparse linear systems.\r\n% \r\n%    [L,U,P,Q] = lu(A)\r\n%\r\n% Written primarily\r\n% by Tim Davis and included in his UMFPACK package, the function\r\n% uses an unsymmetric pattern multifrontal pivoting strategy to\r\n% find permutations |P| and |Q| so that |L| is lower triangular,\r\n% |U| is upper triangular and\r\n%\r\n%    P*A*Q = L*U\r\n%\r\n% Consequently, the determinant of |A| is the product of four easily\r\n% computed determinants.\r\n%\r\n%    det(A) = det(L)*det(U)*det(P)*det(Q)\r\n%\r\n% The pivoting strategy aims to reduce fill-in while maintaining\r\n% numerical stability.\r\n\r\n%%\r\n% For example, here are |L| and |U| for the Redheffer matrix\r\n% in the spy plot near the top of this blog post.\r\n\r\n    close\r\n    A = redheffer(200);\r\n    [L,U,P,Q] = lu(A);\r\n    spy(L|U)\r\n    title('L|U')\r\n    \r\n%%\r\n% And here are the four determinants.\r\n\r\n    dets = [det(L), det(U), det(P), det(Q)];\r\n    disp(dets)\r\n\r\n%%\r\n% Finally, |M(200)| is\r\n\r\n    M_200 = det(L)*det(U)*det(P)*det(Q)\r\n\r\n%% |mertens|\r\n% Mertens function can be computed with four lines of code.\r\n\r\n    type mertens\r\n\r\n%%\r\n% Execution time for |mertens| is dominated by the time in sparse |lu|.\r\n% The time required to compute the four determinants is an order of\r\n% magnitude smaller than the other two.  \r\n%\r\n% Experimentally, we see that the time complexity of sparse |lu| is\r\n% |O(n^2)|, but we have no proof.   \r\n\r\n    mertens_time2\r\n\r\n%% Mertens Conjecture Is False\r\n% The Mertens conjecture stood for nearly 100 years before it was \r\n% proved false in 1985 by Andrew Odlyzko and Herman te Riele.\r\n% The authors present indirect proofs that\r\n%\r\n%    lim sup (n -> inf) M(n)\/sqrt(n) > 1.06\r\n%\r\n%    lim inf (n -> inf) M(n)\/sqrt(n) < -1.009\r\n%\r\n% Odlyzko and te Riele do not actually produce any value of |n| for \r\n% which |M(n) > sqrt(x)|. They suspect that any Mertens conjecture\r\n% counterexample requires |n| > $10^{30}$, which is far beyond any\r\n% computation possible today.\r\n%\r\n% Odlyzko and te Riele also describe several complete tabulations of \r\n% |M(n)| for |n| as large as $7.8 \\cdot 10^{9}$ .  These computations\r\n% do not use Redheffer determinants.\r\n\r\n%% Postscripts\r\n% To tell the truth, I did not really expect to find any Mertens or\r\n% Riemann counterexamples.  I did, however, enjoy computing determinants\r\n% for the first time and discovering an unexpected use for sparse LU. \r\n%\r\n% Thanks a lot to Tim Davis for his help with this post.\r\n\r\n%% References\r\n% A. M. Odlyzko and H. J. J. te Riele,\r\n% \"Disproof of the Mertens conjecture\",\r\n% _Journal f\u00fcr die reine und angewandte Mathematik_,\r\n% Vol. 357 (1985), Pages138-160. <https:\/\/eudml.org\/doc\/152712>.\r\n%\r\n% Timothy A. Davis,\r\n% \"A Column Pre-Ordering Strategy for the Unsymmetric-Pattern Multifrontal\r\n% Method\",\r\n% _ACM Transactions on Mathematical Software_,\r\n% Vol. 30, No. 2, June 2004, Pages 165\u2013195.\r\n% <https:\/\/dl.acm.org\/doi\/abs\/10.1145\/992200.992205>.\r\n% \r\n\r\n\r\n##### SOURCE END ##### 482a8da5c0f748dc9f2af6f28abde6ac\r\n-->\r\n","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/mertens_plot_small2.png\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><!--introduction-->\r\n<p>I didn't know anything about these topics until a couple of weeks ago. Now I can't stop thinking about them.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2024\/09\/23\/redheffer-mertens-and-one-million-dollars\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":11582,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[5,4,8,36],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/11534"}],"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=11534"}],"version-history":[{"count":7,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/11534\/revisions"}],"predecessor-version":[{"id":11606,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/11534\/revisions\/11606"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media\/11582"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=11534"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=11534"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=11534"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}