The Riemann hypothesis as the parity of special binomial coefficients

Yu. V. Matiyasevich

Čebyševskij sbornik, Tome 19 (2018) no. 3, pp. 46-60.

Résumé

The Riemann Hypothesis has many equivalent reformulations. Some of them are arithmetical, that is, thewy are statements about properties of integers or natural numbers. Among them the reformulations with the simplest logical structure are those from the class $\Pi_1^0$ from the arithmetical hierachy, that is, having the form "for every $x_1,\dots,x_m$ relation $A(x_1,\dots,x_m)$ holds", where $A$ is decidable. As an example one can take the reformulation of the Riemann Hypothsis as the assertion that certain Diophantine equation has no solution (such particular equation can be given explicitly). While the logical structure of this reformulation is indeed very simple, all known methods for constructing such Diophantine equation produce equations occupying several pages. On the other hand, there are known other reformulation also belonging to class $\Pi_1^0$ but having rather short wording. As examples one can mention the criteria of the validity of the Riemann Hypothesis proposed by J.-L. Nicolas, by G. Robin, and by J. Lagarias. The shortcoming of these reformulations (as compared to Diophantine equations) consists in the usage of constants and funtions which are “more complicated” than integers and addition and multiplication sufficient for constructing Diophantine equations. The paper presents a system of $9$ conditions imposed on $9$ variables. In order to state these conditions one needs only addition, multiplication, exponentiation (unary, with fixed base $2$), congruences and remainders, inequalities, and binomial coefficient. The whole system can be written explicitly on a single sheet of paper. It is proved that the system is inconsistent if and only if the Riemann Hypothesis is true.

Détail

Keywords: the Riemann Hypothesis, binomial coefficients.

Bibliographie

[1] Broughan K., Equivalents of the Riemann hypothesis, v. 1, Arithmetic equivalents, Cambridge University Press, Cambridge, 2017 | MR

[2] Broughan K., Equivalents of the Riemann hypothesis, v. 2, Analytic equivalents, Cambridge University Press, Cambridge, 2017, xx+491 pp. | DOI | MR

[3] Gödel K., “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I”, Monatsh. Math. Phys., 1931 | DOI | MR

[4] Booker A.R., “Turing and the Riemann hypothesis”, Notices Am. Math. Soc., 53:10 (2006), 1208–1211 | MR | Zbl

[5] Booker A. R. Artin's conjecture, Turing's method, and the Riemann hypothesis, Exp. Math., 15:4 (2006), 385–407 | DOI | MR | Zbl

[6] S. B. Cooper, J. van Leeuwen (eds.), Alan Turing – His Work and Impact, Elsevier Science, 2013 | DOI | MR | Zbl

[7] Matiyasevich Yu. V., “Alan Turing and number theory”, Matematika v vysshem obrazovanii, 10 (2012), 111–134 (in Russian)

[8] Turing A. M., “On computable numbers, with an application to the Entscheidungsproblem”, Proc. London Math. Soc., 42:2 (1936), 230–265 | MR

[9] Kreisel G., “Mathematical significance of consistency proofs”, Journal of Symbolic Logic, 23:2 (1958), 155–182 | MR

[10] Yedidia A., Aaronson S., “A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory”, Complex Systems, 25 (2016) | DOI | MR

[11] Aaronson S., The blog, https://www.scottaaronson.com/blog/?p=2741 | MR

[12] Calude C. S., Calude E., Dinneen M. J., “A new measure of the difficulty of problems”, J. Mult.-Val. Log. Soft Comput., 12:3/4 (2006), 285–307 | MR | Zbl

[13] Calude E., “The complexity of Riemann's hypothesis”, J. Mult.-Val. Log. Soft Comput., 18:3/4 (2012), 257–265 | MR | Zbl

[14] Yu. V. Matiyasevich, The Riemann Hypothesis in Computer Science, Preprints of St. Petersburg Department of Steklov Mathematical Institute, No 7, 2018 | DOI

[15] Manin Yu. I., Panchishkin A. A., Introduction to modern number theory. Fundamental problems, ideas and theories, Transl. from the Russian, 2nd revised ed., Springer, Berlin, 2005 | MR | Zbl

[16] Matiyasevich Yu., Hilbert's Tenth Problem, Transl. from the Russian, MIT Press, Cambridge (Massachusetts)–London, 1993 | MR | MR | Zbl

[17] Davis M., Matijasevič Yu., Robinson J., “Hilbert's tenth problem: Diophantine equations: Positive aspects of a negative solution”, Proc. Symp. Pure Math., 28 (1976), 323–378 | MR | Zbl

[18] Hernandez Caceres J. M., The Riemann Hypothesis and Diophantine equations, Master's Thesis in Mathematics, Mathematical Institute, University of Bonn

[19] Moroz B. Z., The Riemann Hypothesis and Diophantine equatons, St. Petersburg Mathematical Society Preprints, No 3, 2018 (in Russian)

[20] Nayebi A., On the Riemann Hypothesis and Hilbert's Tenth Problem, Unpublished Manuscript, , 2012 http://web.stanford.edu/ãnayebi/projects/RH_Diophantine.pdf

[21] Matijasevič Yu. V., “On recursive unsolvability of Hilbert's tenth problem”, Studies in Logic and the Foundations of Mathematics, 74, 89–110 | MR

[22] Jones J. P., “Universal Diophantine equation”, J. Symb. Log., 47 (1982), 549–571 | DOI | MR | Zbl

[23] Schoenfeld L., “Sharper bounds for the Chebyshev functions $\theta(x)$ and $\psi(x)$. II”, Math. Comput., 30 (1976), 337–360 | DOI | MR | Zbl

[24] Nicolas J.-L., “Petites valeurs de la fonction d'Euler”, J. Number Theory, 17 (1983), 375–388 | DOI | MR | Zbl

[25] Robin G., “Grandes valeurs de la fonction somme des diviseurs et hypothèse de Riemann”, J. Math. Pures Appl. (9), 63 (1984), 187–213 | MR | Zbl

[26] Lagarias J. C., “An elementary problem equivalent to the Riemann hypothesis”, Am. Math. Mon., 109:6 (2002), 534–543 | DOI | MR | Zbl

[27] Mann H. B., Shanks D., “A necessary and sufficient condition for primality, and its source”, J. Comb. Theory, Ser. A, 13 (1972), 131–134 | DOI | MR | Zbl

[28] Hsu L., Shiue P. J.-S., “On a combinatorial expression concerning Fermat's Last Theorem”, Adv. Appl. Math., 18:2 (1997), 216–219 | DOI | MR | Zbl

[29] Matiyasevich Yu.V., “A class of primality criteria formulated in terms of the divisibility of binomial coefficients”, Journal of Soviet Mathematics, 16:1 (1981), 874–885 | DOI | Zbl | Zbl

[30] Matiyasevich Yu., “Some arithmetical restatements of the four color conjecture”, Theor. Comput. Sci., 257:1/2 (2001), 167–183 | DOI | MR | Zbl

[31] Margenstern M., Matiyasevich Yu., “A binomial representation of the $3x + 1$ problem”, Acta Arith., 91:4 (1999), 367–378 | DOI | MR | Zbl

[32] Kummer E. E., “Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen”, Journal für die Reine und Angewandte Mathematik, 44 (1852), 93–146 | MR | Zbl

[33] Singmaster D., “Notes on binomial coefficients. I: A generalization of Lucas' congruence”, J. Lond. Math. Soc., II. Ser., 8 (1974), 545–548 | DOI | MR | Zbl

[34] Lucas E., “Théorie des Fonctions Numériques Simplement Périodiques”, American Journal of Mathematics, 1 (1878), 184–240 http://www.jstor.org/stable/2369311 | MR | Zbl

[35] Schmidt E., “Über die Anzahl der Primzahlen unter gegebener Grenze”, Math Annalen, 57 (1903 (1932)), 195–203 | MR

[36] Ingham A. E., The distribution of prime numbers, reprinted in 1990, Cambridge Tracts in Mathematics and Mathematical Physics, 30, Cambridge University Press, London, 1932 | MR