Lemmy: Bestiverse
  • Communities
  • Create Post
  • Create Community
  • heart
    Support Lemmy
  • search
    Search
  • Login
  • Sign Up
RSS BotMB to Hacker NewsEnglish · 11 hours ago

A Formal Proof of Complexity Bounds on Diophantine Equations

arxiv.org

external-link
message-square
0
fedilink
4
external-link

A Formal Proof of Complexity Bounds on Diophantine Equations

arxiv.org

RSS BotMB to Hacker NewsEnglish · 11 hours ago
message-square
0
fedilink
We present a universal construction of Diophantine equations with bounded complexity in Isabelle/HOL. This is a formalization of our own work in number theory. Hilbert's Tenth Problem was answered negatively by Yuri Matiyasevich, who showed that there is no general algorithm to decide whether an arbitrary Diophantine equation has a solution. However, the problem remains open when generalized to the field of rational numbers, or contrarily, when restricted to Diophantine equations with bounded complexity, characterized by the number of variables $ν$ and the degree $δ$. If every Diophantine set can be represented within the bounds $(ν, δ)$, we say that this pair is universal, and it follows that the corresponding class of equations is undecidable. In a separate mathematics article, we have determined the first non-trivial universal pair for the case of integer unknowns. In this paper, we contribute a formal verification of the main construction required to establish said universal pair. In doing so, we markedly extend the Isabelle AFP entry on multivariate polynomials, formalize parts of a number theory textbook, and develop classical theory on Diophantine equations in Isabelle. Additionally, our work includes metaprogramming infrastructure designed to efficiently handle complex definitions of multivariate polynomials. Our mathematical draft has been formalized while the mathematical research was ongoing, and benefitted largely from the help of the theorem prover. We reflect how the close collaboration between mathematician and computer is an uncommon but promising modus operandi.

Comments

alert-triangle
You must log in or register to comment.

Hacker News

hackernews

Subscribe from Remote Instance

You are not logged in. However you can subscribe from another Fediverse account, for example Lemmy or Mastodon. To do this, paste the following into the search field of your instance: !hackernews@lemmy.bestiver.se
lock
Community locked: only moderators can create posts. You can still comment on posts.

Posts from the RSS Feed of HackerNews.

The feed sometimes contains ads and posts that have been removed by the mod team at HN.

Visibility: Public
globe

This community can be federated to other instances and be posted/commented in by their users.

  • 182 users / day
  • 1.17K users / week
  • 3.29K users / month
  • 8.66K users / 6 months
  • 2 local subscribers
  • 1.4K subscribers
  • 21.8K Posts
  • 7.66K Comments
  • Modlog
  • mods:
  • patrick
  • RSS Bot
  • BE: 0.19.5
  • Modlog
  • Instances
  • Docs
  • Code
  • join-lemmy.org