Sunday, September 05, 2021

Guest Post on Solving (or trying to) Poly Diophantine Equations by Bogdan Grechuk

(Guest post by Bogdan Grechuk)


Motivated by Mathoverflow question here I have recently became interested in solving Polynomial Diophantine equations, that is, equations of the form

P(x1,...,xn)=0

for some polynomial P with integer coefficients. Because there are many such equations, I have decided to ask a computer to help me. Our conversation is presented here.


Highlights of the conversation: the height of a polynomial over Z in many variables is what you get when you make all of the coefficients positive and plug in x=2. For example, the height of

x3 - y4 + 5

is
23 + 24 + 5 = 8 + 16 + 5 = 29.

Note that, for all h, there are only a finite number of polynomials in many vars over Z with height h. With the help of my friend the computer we have looked at the equations with h=0,1,2,... and so on, and tried to  determine which ones have any integer solutions. As expected, the first equations were trivial, but at about h=22 we have started to meet quite interesting equations for which we needed help from  Mathoverflow to solve. The project is currently at h=29, with only one remaining open equation of this height.  Read the conversation with the computer, or my mathoverflow question

here
or my paper:

here
to find out more. I INVITE you to join me in this quest!

6 comments:

  1. The notion of height at diagonal case of all coordinates being 2 is very artificial.

    ReplyDelete
  2. I meant diagonal case. Why only study it?

    ReplyDelete
  3. Anonymous, in case you missed it, there was a blog post back in May discussing the meaning of the word "natural" (and by extension, the word "artificial").

    http://blog.computationalcomplexity.org/2021/05/what-is-natural-question-who-should.html

    Making all the coefficients positive and plugging in 2 may not be "natural" from the point of view of someone developing the theory of Diophantine equations, but there are people who are interested in the "simplest" Diophantine equations. Of course, one then has to define "simplest" precisely. We want small coefficients and small degree, but how much relative weight do we assign to coefficients versus degree? Substituting 2 for each variable is a simple way to achieve a reasonable balance.

    At least, that's my guess as to why they chose this measure.

    ReplyDelete
  4. For simplicity, consider monomial of degree d with coefficient a. If we do not use "^" notation, how many symbols we need to write it? For example, x^3y^2 is xxxyy, 5 symbols. In general, we need d symbols to write variables. For a coefficient a, it is common in computer science to write it in binary, not in decimal, and then we need about log_2(|a|) symbols. Hence, it is natural to define the length of this monomial M as l(M) = log_2(a)+d. This is nice but not an integer. However, ordering monomials by l(M) is absolutely equivalent to ordering them by 2^{l(M)} = 2^(log_2(|a|)+d) = |a|2^d.

    ReplyDelete
  5. A natural measure of length would be the length of an efficient binary encoding. That immediately gives an upper bound 2^n on the number of equations of length n bits. I just typed in a description of an elegant encoding which was all wiped out when I hit Preview:-(

    ReplyDelete
  6. Great text Bogdan!

    ReplyDelete