4

In page 197, Equivalents of the Riemann Hypothesis Vol 1, the following statement caught my eye

There is an editorial comment in [102] that includes an observation by the GCHQ Problem Solving Group. They contest that one could replace the number 2 in inequality (7.94) by any constant $K > 1$ at the cost of having to check more cases by hand when $K$ is close to one. An example is cited: when $K = 1.2$ one needs to verify inequality (7.94) for $1 \leq n \leq 10^6$.

referring the inequality 7.94

$\sigma(n) \leq H_n +2\exp(H_n) \log(H_n)$, $n \geq 1$,

and the reference 102 being

[102] J. C. Lagarias and W. Janous, A generous bound for divisor sums: problem 10949, Amer. Math. Monthly 111 (2004), 264–265.

According to An Elementary Problem Equivalent to the Riemann Hypothesis by J. C. Lagarias, $K = 1$ is equivalent to RH. I understand the claim is not that RH can be proved by checking more cases by hand, but I want to understand what are the methods by which $K$ can be improved to any $1 + \epsilon$ by checking more cases? What are the barriers that prevent it from proving that $K \leq 1$ by checking for more cases?

Edit: Edited my question with more details after looking at the answer by @Charles

Prashanth Narasimha
  • 313

2 Answers2

7

1. By an inequality due to Robin (see (2.2) in Lagarias's paper), $$\sigma(n)\leq e^\gamma n\log\log n+\frac{n}{\log\log n},\qquad n\geq 3.$$ By Lemma 3.1 in Lagarias's paper, we also know that $$\exp(H_n)\log(H_n)\geq e^\gamma n\log\log n,\qquad n\geq 3.$$ Combining these two estimates, we infer that $$\sigma(n)\leq\left(1+\frac{1}{(\log\log n)^2}\right)\exp(H_n)\log(H_n),\qquad n\geq 3.$$ The fraction on the right hand side tends to zero (effectively), confirming the observation by the GCHQ Problem Solving Group. Explicitly, given any $\varepsilon>0$, we have $$\sigma(n)\leq(1+\varepsilon)\exp(H_n)\log(H_n),\qquad n\geq\exp\exp(\varepsilon^{-1/2}).$$

2. The barrier to prove Lagarias's inequality is the same as the barrier to prove the Riemann Hypothesis, since these two statements are equivalent. It is a difficult problem, and perhaps it is even undecidable from the ZFC axioms (of course most of us believe it is decidable).

GH from MO
  • 98,751
  • 3
    +1. Prashanth, this is the answer to accept. – Charles Aug 12 '21 at 18:56
  • Thanks for the explanation @GHfromMO . It's very clear for me now. Also, shouldn't there be $\exp(\gamma)$ in the denominator of the fraction on the RHS ? Your next statement that it tends to zero is still valid as $\exp(\gamma)$ is a constant, but I'm just making sure my understanding is correct as I don't really have a math background. – Prashanth Narasimha Aug 12 '21 at 19:20
  • Is there a way to check if the attempt of proof of some statement (not necessarily RH) is decidable from ZFC axioms? – Sylvain JULIEN Aug 12 '21 at 19:44
  • 3
    @PrashanthNCR: The third display can be strengthened by including a factor of $e^\gamma$ in the denominator. Note that $e^\gamma$ exceeds $1$. In fact this factor could be enlarged slightly, because in Robin's bound there is a constant $0.6482$ present in front of the fraction. I omitted these constants for elegance of presentation. – GH from MO Aug 12 '21 at 19:53
  • 1
    @SylvainJULIEN: If ZFC is consistent, then there is no algorithm that could tell about every statement in ZFC whether it is decidable or not from the ZFC axioms. – GH from MO Aug 12 '21 at 19:57
  • RH is a complex number problem. The theory of complex numbers is complete,, therefore there is either a proof of RH or a proof of its negation (analytic). On the other hand, it could be independent in Peano Arithmetic – EGME May 03 '22 at 15:11
  • @EGME I don't think it is known that RH is decidable within ZFC. Note also that the solvability of any diophantine equation can be formulated within the theory of complex numbers, and there are diophantine equations whose solvability is not decidable within ZFC (assuming ZFC is consistent). – GH from MO May 03 '22 at 19:46
  • As I understood from this discussion, if RH is false, it can be provably false because of Robin-Ramanujan inequalities – Prashanth Narasimha May 13 '22 at 02:21
6

The case $K=1$ is equivalent to the Riemann Hypothesis. [1] The GCHQ Problem Solving Group is not claiming that RH can be proved by checking a finite number of cases of this problem. I don't know what the barriers are that prevent it, though; I don't even know the method they used to extend $K$.

[1] Jeffrey C. Lagarias, An Elementary Problem Equivalent to the Riemann Hypothesis, American Mathematical Monthly 109 (2002), pp. 534–543.

Charles
  • 8,974
  • 1
  • 36
  • 74
  • Among those $n$ that I could reach, the largest value of $\frac{\sigma(n)-H_n}{\exp(H_n)\log(H_n)}$ is $\approx0.987238$, attained at $n=12$ – მამუკა ჯიბლაძე Aug 12 '21 at 14:03
  • Thanks @Charles , I understood that they are not claiming RH can be proved by checking a finite number of cases, I wanted to understand how can we reduce K to any 1+ϵ by checking more cases and why can't we go beyond $1$ ? Perhaps, I should edit my question. – Prashanth Narasimha Aug 12 '21 at 17:11
  • 1
    Well for $K<1$ it’s simply false: combining Thm. 2.2 and L. 3.2 in Lagarias’s paper, it follows immediately that $\limsup_{n\to\infty}\frac{\sigma(n)-H_n}{\exp(H_n)\log(H_n)}=\limsup_{n\to\infty}\frac{\sigma(n)}{\exp(H_n)\log(H_n)}\ge1$. – Emil Jeřábek Aug 12 '21 at 18:07
  • @EmilJeřábek Is any $n$ known with $\frac{\sigma(n)-H_n}{\exp(H_n)\log(H_n)}>\frac{\sigma(12)-H_{12}}{\exp(H_{12})\log(H_{12})}$? – მამუკა ჯიბლაძე Aug 12 '21 at 19:03
  • 2
    @მამუკა ჯიბლაძე sure, take the 100th number from this sequence: https://oeis.org/A004490 and you'll get $\approx 0.9929$ – Alexander Kalmynin Aug 13 '21 at 07:15
  • @AlexanderKalmynin Wow, thanks! But why 100th? Is this the smallest one? What is the next one? Can you give a reference for a study of the "record breakers" like that? Are they all colossally abundant? Do you think it makes sense to ask a separate question about it here on MO? – მამუკა ჯიბლაძე Aug 13 '21 at 07:21
  • @მამუკა ჯიბლაძე it is well known that if there exists an number that do not obey Lagarias inequality, then it must be a colossally abundant number. – Prashanth Narasimha Aug 13 '21 at 15:27
  • @PrashanthNCR I became curious about the sequence $a_k$ defined by requiring that for each $k$, $a_{k+1}$ is the smallest natural number with $L(a_{k+1})>L(a_k)$, where $L(n)=\frac{\sigma(n)-H_n}{\exp(H_n)\log(H_n)}$, starting with $a_1=1$, $a_2=2$. It seems that $a_3=6$, $a_4=12$ and $a_5$ is huge. By Alexander Kalmynin's example, $a_5$ does not exceed the 100th colossally abundant number. I wonder if $a_5$ is equal to it, and whether each $a_n$ is colossally abundant. How fast does this sequence grow? – მამუკა ჯიბლაძე Aug 13 '21 at 16:10
  • @მამუკა ჯიბლაძე Honestly, I don't remember the precise statement on colossal abundantness of these "record breakers", but Prashanth is probably right. I believe, some results of this type were also derived by Ramanujan. 100 here is pretty random, I chose it because 25th and 50th numbers from the list were not sufficient. – Alexander Kalmynin Aug 14 '21 at 07:05
  • @AlexanderKalmynin I did some calculations with that. If my numerical approximations for $H_n$ are correct, the first colossally abundant number whose ratio exceeds that of $12$ is the 58th one ($\approx5.95\times10^{76}$). And in fact it seems that starting from the 29th colossally abundant number these ratios grow monotonously. I think I will ask a separate question about it. – მამუკა ჯიბლაძე Aug 14 '21 at 09:54