License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITP.2022.26
URN: urn:nbn:de:0030-drops-167350
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16735/
Go to the corresponding LIPIcs Volume Portal

Pąk, Karol ; Kaliszyk, Cezary

Formalizing a Diophantine Representation of the Set of Prime Numbers

pdf-format:
LIPIcs-ITP-2022-26.pdf (0.7 MB)

Abstract

The DPRM (Davis-Putnam-Robinson-Matiyasevich) theorem is the main step in the negative resolution of Hilbert’s 10th problem. Almost three decades of work on the problem have resulted in several equally surprising results. These include the existence of diophantine equations with a reduced number of variables, as well as the explicit construction of polynomials that represent specific sets, in particular the set of primes. In this work, we formalize these constructions in the Mizar system. We focus on the set of prime numbers and its explicit representation using 10 variables. It is the smallest representation known today. For this, we show that the exponential function is diophantine, together with the same properties for the binomial coefficient and factorial. This formalization is the next step in the research on formal approaches to diophantine sets following the DPRM theorem.

BibTeX - Entry

@InProceedings{pak_et_al:LIPIcs.ITP.2022.26,
  author =	{P\k{a}k, Karol and Kaliszyk, Cezary},
  title =	{{Formalizing a Diophantine Representation of the Set of Prime Numbers}},
  booktitle =	{13th International Conference on Interactive Theorem Proving (ITP 2022)},
  pages =	{26:1--26:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-252-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{237},
  editor =	{Andronick, June and de Moura, Leonardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16735},
  URN =		{urn:nbn:de:0030-drops-167350},
  doi =		{10.4230/LIPIcs.ITP.2022.26},
  annote =	{Keywords: DPRM theorem, Polynomial reduction, prime numbers}
}

Keywords: DPRM theorem, Polynomial reduction, prime numbers
Collection: 13th International Conference on Interactive Theorem Proving (ITP 2022)
Issue Date: 2022
Date of publication: 03.08.2022
Supplementary Material: Formalization can be found at:
Software (Formalization): http://cl-informatik.uibk.ac.at/cek/itp2022/

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI