Diophantine Equation

A Diophantine equation is a polynomial equation with integer coefficients for which only integer solutions are sought. Diophantine equations are known to be Turing complete.

Definitions

A Diophantine equation is defined by a multi-variate polynomial P(x,y,z,...). Solutions are values x,y,z,... such that P(x,y,z,...) = 0. The "magnitude" of a solution is max(|x|, |y|, |z|, ...) (the maximum absolute value of all it's variable assignments). The "score" for a Diophantine equation is the minimum magnitude across all solutions. In other words, it is the minimum N such that there exists a solution with -N ≤ x,y,z,... ≤ N.

The "size" or "height" of a Diophantine equation is the sum of |coefficient|*2^degree among all of its terms. For example $x^2+xy+6y+1=0$ has size $1\cdot 2^2+1\cdot 2^2+6\cdot 2^1+1\cdot 2^0=21$.

BBdio(H) is the maximum score among all solvable polynomial Diophantine equations of height H.

Champions

For 2 ≤ n ≤ 15: BBdio(n) = n-2 via the trivial equation $x-(n-2)=0$.[1]

n	BBdio(n)	Champion	Min Solution
2 ≤ n ≤ 20	≥ n-2	$x-(n-2)=0$	(n-2)
21	≥ 26	$x^2+xy+6y+1=0$	(-5, -26)
22	≥ 22	$x^3+y^2+4=3x$	(-8, ±22)
23	≥ 31	$x^2+xy+x+1=6y$	(5, -31)
24	≥ 66	$x^3+xy+5y=2$	(-4, -66)
25	≥ 470	$x^3+xy+y^2+y+7=0$
26	≥ 40	$x^2+xy+7y+4=0$
27	≥ 849	$x^3+x^2+y^2+9=x$
28	≥ 74	$x^3+xy+2x+5y=2$
29	≥ 221	$x^3+xy+x+7y+1=0$
30	≥ 849	$x^3+2x^2=y^2+10$