{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T02:07:46Z","timestamp":1783908466434,"version":"3.55.0"},"reference-count":14,"publisher":"Walter de Gruyter GmbH","issue":"4","license":[{"start":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T00:00:00Z","timestamp":1638316800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,12,1]]},"abstract":"Summary<\/jats:title>\n 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.<\/jats:p>\n \n 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 (\n w<\/jats:italic>\n \u00b7\n z<\/jats:italic>\n +\n h<\/jats:italic>\n +\n j<\/jats:italic>\n \u2212\n q<\/jats:italic>\n )\n 2<\/jats:sup>\n +((\n g<\/jats:italic>\n \u00b7\n k<\/jats:italic>\n +\n g<\/jats:italic>\n +\n k<\/jats:italic>\n )\u00b7(\n h<\/jats:italic>\n +\n j<\/jats:italic>\n )+\n h<\/jats:italic>\n \u2212\n z<\/jats:italic>\n )\n 2<\/jats:sup>\n +(2 \u00b7\n k<\/jats:italic>\n 3<\/jats:sup>\n \u00b7(2\u00b7\n k<\/jats:italic>\n +2)\u00b7(\n n<\/jats:italic>\n + 1)\n 2<\/jats:sup>\n +1\u2212\n f<\/jats:italic>\n 2<\/jats:sup>\n )\n 2<\/jats:sup>\n + (\n p<\/jats:italic>\n +\n q<\/jats:italic>\n +\n z<\/jats:italic>\n + 2 \u00b7\n n<\/jats:italic>\n \u2212\n e<\/jats:italic>\n )\n 2<\/jats:sup>\n + (\n e<\/jats:italic>\n 3<\/jats:sup>\n \u00b7 (\n e<\/jats:italic>\n + 2) \u00b7 (\n a<\/jats:italic>\n + 1)\n 2<\/jats:sup>\n + 1 \u2212\n o<\/jats:italic>\n 2<\/jats:sup>\n )\n 2<\/jats:sup>\n + (\n x<\/jats:italic>\n 2<\/jats:sup>\n \u2212 (\n a<\/jats:italic>\n 2<\/jats:sup>\n \u2212\u2032 1) \u00b7\n y<\/jats:italic>\n 2<\/jats:sup>\n \u2212 1)\n 2<\/jats:sup>\n + (16 \u00b7 (\n a<\/jats:italic>\n 2<\/jats:sup>\n \u2212 1) \u00b7\n r<\/jats:italic>\n 2<\/jats:sup>\n \u00b7\n y<\/jats:italic>\n 2<\/jats:sup>\n \u00b7\n y<\/jats:italic>\n 2<\/jats:sup>\n + 1 \u2212\n u<\/jats:italic>\n 2<\/jats:sup>\n )\n 2<\/jats:sup>\n + (((\n a<\/jats:italic>\n +\n u<\/jats:italic>\n 2<\/jats:sup>\n \u00b7 (\n u<\/jats:italic>\n 2<\/jats:sup>\n \u2212\n a<\/jats:italic>\n ))\n 2<\/jats:sup>\n \u2212 1) \u00b7 (\n n<\/jats:italic>\n + 4 \u00b7\n d<\/jats:italic>\n \u00b7\n y<\/jats:italic>\n )\n 2<\/jats:sup>\n + 1 \u2212 (\n x<\/jats:italic>\n +\n c<\/jats:italic>\n \u00b7\n u<\/jats:italic>\n )\n 2<\/jats:sup>\n )\n 2<\/jats:sup>\n + (\n m<\/jats:italic>\n 2<\/jats:sup>\n \u2212 (\n a<\/jats:italic>\n 2<\/jats:sup>\n \u2212\u2032 1) \u00b7\n l<\/jats:italic>\n 2<\/jats:sup>\n \u2212 1)\n 2<\/jats:sup>\n + (\n k<\/jats:italic>\n +\n i<\/jats:italic>\n \u00b7 (\n a<\/jats:italic>\n \u2212 1) \u2212\n l<\/jats:italic>\n )\n 2<\/jats:sup>\n + (\n n<\/jats:italic>\n +\n l<\/jats:italic>\n +\n v<\/jats:italic>\n \u2212\n y<\/jats:italic>\n )\n 2<\/jats:sup>\n + (\n p<\/jats:italic>\n +\n l<\/jats:italic>\n \u00b7 (\n a<\/jats:italic>\n \u2212\n n<\/jats:italic>\n \u2212 1) +\n b<\/jats:italic>\n \u00b7 (2 \u00b7\n a<\/jats:italic>\n \u00b7 (\n n<\/jats:italic>\n + 1) \u2212 (\n n<\/jats:italic>\n + 1)\n 2<\/jats:sup>\n \u2212 1) \u2212\n m<\/jats:italic>\n )\n 2<\/jats:sup>\n + (\n q<\/jats:italic>\n +\n y<\/jats:italic>\n \u00b7 (\n a<\/jats:italic>\n \u2212\n p<\/jats:italic>\n \u2212 1) +\n s<\/jats:italic>\n \u00b7 (2 \u00b7\n a<\/jats:italic>\n \u00b7 (\n p<\/jats:italic>\n + 1) \u2212 (\n p<\/jats:italic>\n + 1)\n 2<\/jats:sup>\n \u2212 1) \u2212\n x<\/jats:italic>\n )\n 2<\/jats:sup>\n + (\n z<\/jats:italic>\n +\n p<\/jats:italic>\n \u00b7\n l<\/jats:italic>\n \u00b7 (\n a<\/jats:italic>\n \u2212\n p<\/jats:italic>\n ) +\n t<\/jats:italic>\n \u00b7 (2 \u00b7\n a<\/jats:italic>\n \u00b7\n p<\/jats:italic>\n \u2212\n p<\/jats:italic>\n 2<\/jats:sup>\n \u2212 1) \u2212\n p<\/jats:italic>\n \u00b7\n m<\/jats:italic>\n )\n 2<\/jats:sup>\n and we prove that that for any positive integer\n k<\/jats:italic>\n so that\n k<\/jats:italic>\n + 1 is prime it is necessary and sufficient that there exist other natural variables\n a<\/jats:italic>\n -\n z<\/jats:italic>\n 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 \u2115 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.\n <\/jats:p>","DOI":"10.2478\/forma-2021-0020","type":"journal-article","created":{"date-parts":[[2022,7,9]],"date-time":"2022-07-09T16:34:26Z","timestamp":1657384466000},"page":"221-228","source":"Crossref","is-referenced-by-count":4,"title":["Prime Representing Polynomial"],"prefix":"10.2478","volume":"29","author":[{"given":"Karol","family":"P\u0105k","sequence":"first","affiliation":[{"name":"Institute of Computer Science , University of Bia\u0142ystok , Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"374","published-online":{"date-parts":[[2022,7,9]]},"reference":[{"key":"2026071215074023036_j_forma-2021-0020_ref_001","doi-asserted-by":"crossref","unstructured":"[1] Grzegorz Bancerek, Czes\u0142aw Byli\u0144ski, Adam Grabowski, Artur Korni\u0142owicz, Roman Matuszewski, Adam Naumowicz, Karol P\u0105k, 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\u2013279. Springer International Publishing, 2015. ISBN 978-3-319-20614-1. doi:10.1007\/978-3-319-20615-8_17.","DOI":"10.1007\/978-3-319-20615-8_17"},{"key":"2026071215074023036_j_forma-2021-0020_ref_002","doi-asserted-by":"crossref","unstructured":"[2] Grzegorz Bancerek, Czes\u0142aw Byli\u0144ski, Adam Grabowski, Artur Korni\u0142owicz, Roman Matuszewski, Adam Naumowicz, and Karol P\u0105k. The role of the Mizar Mathematical Library for interactive proof development in Mizar. Journal of Automated Reasoning, 61(1):9\u201332, 2018. doi:10.1007\/s10817-017-9440-6.604425130069070","DOI":"10.1007\/s10817-017-9440-6"},{"key":"2026071215074023036_j_forma-2021-0020_ref_003","doi-asserted-by":"crossref","unstructured":"[3] Yuichi Futa, Hiroyuki Okazaki, Daichi Mizushima, and Yasunari Shidama. Gaussian integers. Formalized Mathematics, 21(2):115\u2013125, 2013. doi:10.2478\/forma-2013-0013.","DOI":"10.2478\/forma-2013-0013"},{"key":"2026071215074023036_j_forma-2021-0020_ref_004","doi-asserted-by":"crossref","unstructured":"[4] James P. Jones. Diophantine representation of Mersenne and Fermat primes. Acta Arithmetica, 35:209\u2013221, 1979. doi:10.4064\/AA-35-3-209-221.","DOI":"10.4064\/aa-35-3-209-221"},{"key":"2026071215074023036_j_forma-2021-0020_ref_005","doi-asserted-by":"crossref","unstructured":"[5] James P. Jones. Universal diophantine equation. Journal of Symbolic Logic, 47(4):549\u2013571, 1982.10.2307\/2273588","DOI":"10.2307\/2273588"},{"key":"2026071215074023036_j_forma-2021-0020_ref_006","doi-asserted-by":"crossref","unstructured":"[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\u2013464, 1976.10.1080\/00029890.1976.11994142","DOI":"10.1080\/00029890.1976.11994142"},{"key":"2026071215074023036_j_forma-2021-0020_ref_007","doi-asserted-by":"crossref","unstructured":"[7] Yuri Matiyasevich. Primes are nonnegative values of a polynomial in 10 variables. Journal of Soviet Mathematics, 15:33\u201344, 1981. doi:10.1007\/BF01404106.","DOI":"10.1007\/BF01404106"},{"key":"2026071215074023036_j_forma-2021-0020_ref_008","doi-asserted-by":"crossref","unstructured":"[8] Yuri Matiyasevich and Julia Robinson. Reduction of an arbitrary diophantine equation to one in 13 unknowns. Acta Arithmetica, 27:521\u2013553, 1975.10.4064\/aa-27-1-521-553","DOI":"10.4064\/aa-27-1-521-553"},{"key":"2026071215074023036_j_forma-2021-0020_ref_009","doi-asserted-by":"crossref","unstructured":"[9] Karol P\u0105k. The Matiyasevich theorem. Preliminaries. Formalized Mathematics, 25(4): 315\u2013322, 2017. doi:10.1515\/forma-2017-0029.","DOI":"10.1515\/forma-2017-0029"},{"key":"2026071215074023036_j_forma-2021-0020_ref_010","doi-asserted-by":"crossref","unstructured":"[10] Karol P\u0105k. Diophantine sets. Part II. Formalized Mathematics, 27(2):197\u2013208, 2019. doi:10.2478\/forma-2019-0019.","DOI":"10.2478\/forma-2019-0019"},{"key":"2026071215074023036_j_forma-2021-0020_ref_011","doi-asserted-by":"crossref","unstructured":"[11] Karol P\u0105k. Formalization of the MRDP theorem in the Mizar system. Formalized Mathematics, 27(2):209\u2013221, 2019. doi:10.2478\/forma-2019-0020.","DOI":"10.2478\/forma-2019-0020"},{"key":"2026071215074023036_j_forma-2021-0020_ref_012","doi-asserted-by":"crossref","unstructured":"[12] Christoph Schwarzweller. Proth numbers. Formalized Mathematics, 22(2):111\u2013118, 2014. doi:10.2478\/forma-2014-0013.","DOI":"10.2478\/forma-2014-0013"},{"key":"2026071215074023036_j_forma-2021-0020_ref_013","doi-asserted-by":"crossref","unstructured":"[13] Zhi-Wei Sun. Further results on Hilbert\u2019s Tenth Problem. Science China Mathematics, 64:281\u2013306, 2021. doi:10.1007\/s11425-020-1813-5.","DOI":"10.1007\/s11425-020-1813-5"},{"key":"2026071215074023036_j_forma-2021-0020_ref_014","doi-asserted-by":"crossref","unstructured":"[14] Rafa\u0142 Ziobro. Prime factorization of sums and differences of two like powers. Formalized Mathematics, 24(3):187\u2013198, 2016. doi:10.1515\/forma-2016-0015.","DOI":"10.1515\/forma-2016-0015"}],"container-title":["Formalized Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/reference-global.com\/pdf\/10.2478\/forma-2021-0020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T01:31:45Z","timestamp":1783906305000},"score":1,"resource":{"primary":{"URL":"https:\/\/reference-global.com\/article\/10.2478\/forma-2021-0020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,1]]},"references-count":14,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,7,9]]},"published-print":{"date-parts":[[2021,12,1]]}},"alternative-id":["10.2478\/forma-2021-0020"],"URL":"https:\/\/doi.org\/10.2478\/forma-2021-0020","relation":{},"ISSN":["1898-9934"],"issn-type":[{"value":"1898-9934","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,1]]}}}