1. bookVolume 29 (2021): Issue 4 (December 2021)
Journal Details
License
Format
Journal
eISSN
1898-9934
First Published
09 Jun 2008
Publication timeframe
4 times per year
Languages
English
access type Open Access

Prime Representing Polynomial

Published Online: 09 Jul 2022
Volume & Issue: Volume 29 (2021) - Issue 4 (December 2021)
Page range: 221 - 228
Accepted: 30 Nov 2021
Journal Details
License
Format
Journal
eISSN
1898-9934
First Published
09 Jun 2008
Publication timeframe
4 times per year
Languages
English
Summary

The main purpose of formalization is to prove that the set of prime numbers is diophantine, i.e., is representable by a polynomial formula. We formalize this problem, using the Mizar system [1], [2], in two independent ways, proving the existence of a polynomial without formulating it explicitly as well as with its indication.

First, we reuse nearly all the techniques invented to prove the MRDP-theorem [11]. Applying a trick with Mizar schemes that go beyond first-order logic we give a short sophisticated proof for the existence of such a polynomial but without formulating it explicitly. Then we formulate the polynomial proposed in [6] that has 26 variables in the Mizar language as follows (w·z+h+jq)2+((g·k+g+k)·(h+j)+hz)2+(2 · k3·(2·k+2)·(n + 1)2+1−f2)2+ (p + q + z + 2 · ne)2 + (e3 · (e + 2) · (a + 1)2 + 1 − o2)2 + (x2 − (a2 −′ 1) · y2 − 1)2 + (16 · (a2 − 1) · r2 · y2 · y2 + 1 − u2)2 + (((a + u2 · (u2a))2 − 1) · (n + 4 · d · y)2 + 1 − (x + c · u)2)2 + (m2 − (a2 −′ 1) · l2 − 1)2 + (k + i · (a − 1) − l)2 + (n + l + vy)2 + (p + l · (an − 1) + b · (2 · a · (n + 1) − (n + 1)2 − 1) − m)2 + (q + y · (ap − 1) + s · (2 · a · (p + 1) − (p + 1)2 − 1) − x)2 + (z + p · l · (ap) + t · (2 · a · pp2 − 1) − p · m)2 and we prove that that for any positive integer k so that k + 1 is prime it is necessary and sufficient that there exist other natural variables a-z for which the polynomial equals zero. 26 variables is not the best known result in relation to the set of prime numbers, since any diophantine equation over ℕ can be reduced to one in 13 unknowns [8] or even less [5], [13]. The best currently known result for all prime numbers, where the polynomial is explicitly constructed is 10 [7] or even 7 in the case of Fermat as well as Mersenne prime number [4]. We are currently focusing our formalization efforts in this direction.

Keywords

MSC

[1] Grzegorz Bancerek, Czesław Byliński, Adam Grabowski, Artur Korniłowicz, Roman Matuszewski, Adam Naumowicz, Karol Pąk, and Josef Urban. Mizar: State-of-the-art and beyond. In Manfred Kerber, Jacques Carette, Cezary Kaliszyk, Florian Rabe, and Volker Sorge, editors, Intelligent Computer Mathematics, volume 9150 of Lecture Notes in Computer Science, pages 261–279. Springer International Publishing, 2015. ISBN 978-3-319-20614-1. doi:10.1007/978-3-319-20615-8_17. Open DOISearch in Google Scholar

[2] Grzegorz Bancerek, Czesław Byliński, Adam Grabowski, Artur Korniłowicz, Roman Matuszewski, Adam Naumowicz, and Karol Pąk. The role of the Mizar Mathematical Library for interactive proof development in Mizar. Journal of Automated Reasoning, 61(1):9–32, 2018. doi:10.1007/s10817-017-9440-6.604425130069070 Open DOISearch in Google Scholar

[3] Yuichi Futa, Hiroyuki Okazaki, Daichi Mizushima, and Yasunari Shidama. Gaussian integers. Formalized Mathematics, 21(2):115–125, 2013. doi:10.2478/forma-2013-0013. Open DOISearch in Google Scholar

[4] James P. Jones. Diophantine representation of Mersenne and Fermat primes. Acta Arithmetica, 35:209–221, 1979. doi:10.4064/AA-35-3-209-221. Open DOISearch in Google Scholar

[5] James P. Jones. Universal diophantine equation. Journal of Symbolic Logic, 47(4):549–571, 1982.10.2307/2273588 Search in Google Scholar

[6] James P. Jones, Sato Daihachiro, Hideo Wada, and Douglas Wiens. Diophantine representation of the set of prime numbers. The American Mathematical Monthly, 83(6):449–464, 1976.10.1080/00029890.1976.11994142 Search in Google Scholar

[7] Yuri Matiyasevich. Primes are nonnegative values of a polynomial in 10 variables. Journal of Soviet Mathematics, 15:33–44, 1981. doi:10.1007/BF01404106. Open DOISearch in Google Scholar

[8] Yuri Matiyasevich and Julia Robinson. Reduction of an arbitrary diophantine equation to one in 13 unknowns. Acta Arithmetica, 27:521–553, 1975.10.4064/aa-27-1-521-553 Search in Google Scholar

[9] Karol Pąk. The Matiyasevich theorem. Preliminaries. Formalized Mathematics, 25(4): 315–322, 2017. doi:10.1515/forma-2017-0029. Open DOISearch in Google Scholar

[10] Karol Pąk. Diophantine sets. Part II. Formalized Mathematics, 27(2):197–208, 2019. doi:10.2478/forma-2019-0019. Open DOISearch in Google Scholar

[11] Karol Pąk. Formalization of the MRDP theorem in the Mizar system. Formalized Mathematics, 27(2):209–221, 2019. doi:10.2478/forma-2019-0020. Open DOISearch in Google Scholar

[12] Christoph Schwarzweller. Proth numbers. Formalized Mathematics, 22(2):111–118, 2014. doi:10.2478/forma-2014-0013. Open DOISearch in Google Scholar

[13] Zhi-Wei Sun. Further results on Hilbert’s Tenth Problem. Science China Mathematics, 64:281–306, 2021. doi:10.1007/s11425-020-1813-5. Open DOISearch in Google Scholar

[14] Rafał Ziobro. Prime factorization of sums and differences of two like powers. Formalized Mathematics, 24(3):187–198, 2016. doi:10.1515/forma-2016-0015. Open DOISearch in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo