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 via the MRDP theorem.

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	Source
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$	(-63, -470)
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	> 106	$x^3+x{y}^2+x+z^3-z+1=0$	(-4280795, 4360815, 5427173)*	Andrew R. Booker via https://arxiv.org/abs/2108.08705 v3 page 23
...
33	> 1011	$x^4+y^{2}z+z^2-z+3=0$	(708313, 1099536, -267298981516)*	https://arxiv.org/abs/2108.08705 v3 page 27
...
57	> 1015	$x^3+y^3+z^3=33$	(-2736111468807040, -8778405442862239, 8866128975287528)*	https://oeis.org/A060467
66	> 1016	$x^3+y^3+z^3=42$	(12602123297335631, 80435758145817515, −80538738812075974)*	https://oeis.org/A060467

Note: For large champions (marked with * in Min Solution column) these are not known to be strictly the smallest magnitude solutions, instead they appear to be solutions with the minimal smallest value. If that is the case, then this still bounds BBdio since the score of these equations must be ≥ the minimal smallest variable value.

Cryptids

There are several open problems in the sums of three cubes. Specifically, it is not currently known if there are any integer solutions to the equations $x^3+y^3+z^3=k$ for k = 114, 390, 627, 633, 732, 921, or 975. Therefore, $x^3+y^3+z^3=114$ is sort of like a BBdio(138) Cryptid in the sense that it requires solving an open math problem. However, this problem is expected to be solvable with perhaps 10x the compute used to solve the k=42, so it is not as futile as most Cryptids. Sheep suggests calling it an energy vampire.

See Also

• Discord BBdio thread