Polynomial parametrization of the solutions to $yz=x^2+x\pm 1$

Question

If a Diophantine equation has infinitely many integer solutions, how to describe them all? One standard approach is polynomial parametrization. For example, all integer solutions to the equation $$ yz=x^2 $$ are given by $x=uvw$, $y=uv^2$, $z=uw^2$ for some integers $u,v,w$. More formally, a subset $S \subset {\mathbb Z}^n$ is a polynomial family if there exists polynomials $P_1,\dots,P_n$ in some variables $u_1,\dots,u_k$ and integer coefficients such that $(x_1,\dots,x_n) \in S$ if and only if there exists integers $u_1,\dots,u_k$ such that $x_i=P_i(u_1,\dots,u_k)$ for $i=1,\dots,n$.

For some equations the solution set is not a polynomial family but is a finite union of polynomial families. The simplest example is the equation $xy=0$ with solutions $(x,y)=(u,0)$ and $(0,u)$.

In 2010, Vaserstein https://annals.math.princeton.edu/wp-content/uploads/annals-v171-n2-p07-s.pdf answered a long-standing open question and showed that the solution set to the equation $$ xy - zt = 1 $$ is a polynomial family. As a corollary, he showed that the solutions to many equations, including $yz=x^2+a$ for any $a$ and $xy-zt=a$ for any $a$, are the finite unions of polynomial families. As noted by Fedor Pertov in the comment, this result also implies parametrization of the solution set of the equation $$ yz=x^2+x. $$

The simplest examples that seems to be not explicitly covered by this paper are equations $$ yz=x^2+x+1 $$ and $$ yz=x^2+x-1. $$

The question is, for each of these equations, whether its solution set is a finite union of polynomial families? Or, in simple words, can we write down all solutions using polynomial expressions with parameters?

Answer 1

For $x^2+x+1=yz$ we may factorize LHS in the unique factorization domain $\mathbb{Z}[\omega]$, where $\omega=e^{2\pi i/3}$: $$(x-\omega)(x-\omega^2)=yz.$$ Denote by $A$ the greatest common divisor of $x-\omega$ and $y$, say $x-\omega=AB$, $y=AC$. Then $B$ and $C$ are coprime, and $B(x-\omega^2)=Cz$. Thus $C$ divides $x-\omega^2$, that is, $x-\omega^2=CD$, $z=BD$. Since $AC$ is real, we get $A/\overline{C}\in \mathbb{R}$. Since both $A$ and $\overline{C}$ belong to $\mathbb{Z}[\omega]$, the line through 0 and $A$ intersects $\mathbb{Z}[\omega]$ by an infinite cyclic subgroup. So we get $A=pT$, $\overline{C}=qT$ (equivalently, $C=q\overline{T}$) for certain $p,q\in \mathbb{Z}$ and $T\in \mathbb{Z}[\omega]$. Thus $p$ divides $x-\omega$, but $(x-\omega)/p\in \mathbb{Z}[\omega]$ only if $p=\pm 1$, analogously $q=\pm 1$. So, $C=\pm \overline{A}$, analogously $D=\pm \overline{B}$. So, we should parametrize the solutions of $$x-\omega=AB,$$ the rest is automatic. If $A=u+v\omega$, $B=u_1+v_1\omega^2$, then $$AB=(u+v\omega)(u_1+v_1\omega^2)=uu_1+vv_1+(vu_1-uv_1)\omega-uv_1.$$ It equals $x-\omega$ if and only if $vu_1-uv_1=-1$ (and $x=uu_1+vv_1-uv_1$), which may be parametrized by the cited theorem of Vaserstein..

Answer 2

This is a partial solution. The equation

$$yz=x^2+x+1\tag{1}$$

has a parametric solution.

Since $x = 1/2 \pm 1/2\sqrt{-3+4yz}$, the expression $-3+4yz$ must be a perfect square. On the other hand, substitute $y=4k^2+k+1$ and $z=k+1$ to $-3+4yz$, then we get
$$-3+4yz = (4k+1)(1+2k)^2,$$ where $k$ is arbitrary integer. Hence $4k+1$ must be a perfect square.
Let $k = \Large{\frac{u^2-1}{4}}$ and $u=2n+1$ then we get a parametric solution $(x,y,z) = ( n(2n^2+3n+2), 4n^4+8n^3+5n^2+n+1, n^2+n+1 ).$
$n$ is arbitrary integer.

           n     x     y      z  
           
           1     7     19     3
           2    32    151     7
           3    87    589    13
           4   184   1621    21
           5   335   3631    31
           6   552   7099    43
           7   847  12601    57
           8  1232  20809    73
           9  1719  32491    91
          10  2320  48511   111
          11  3047  69829   133
          12  3912  97501   157
          13  4927 132679   183
          14  6104 176611   211
          15  7455 230641   241
          16  8992 296209   273
          17 10727 374851   307
          18 12672 468199   343
          19 14839 577981   381
          20 17240 706021   421
          
          

Another parametric solution is $(x,y,z)=(18n^3+27n^2+12n+1, 36n^4+72n^3+45n^2+9n+1, 9n^2+9n+3).$

The more general solution is $(x,y,z)=(ad+bc+bd, a^2+ab+b^2, c^2+cd+d^2)$ where $ac-bd=1.$

The equation

$$yz=x^2+x-1\tag{2}$$

has a parametric solution.

Since $x = 1/2 \pm 1/2\sqrt{5+4yz}$, the expression $5+4yz$ must be a perfect square. On the other hand, substitute $y=4k^2+5k+1$ and $z=5+5k$ to $5+4yz$, then we get
$$5+4yz = 5(5+4k)(2k+1)^2,$$ where $k$ is arbitrary integer. Hence $5(5+4k)$ must be a perfect square.
Let $k = \Large{\frac{5(u^2-1)}{4}}$ and $u=2n+1$ then we get a parametric solution $(x,y,z) = ( 50n^3+75n^2+30n+2, (20n^2+20n+1)(5n^2+5n+1), 25n^2+25n+5 ).$

           n     x        y     z  

           1    157      451    55
           2    762     3751   155 
           3   2117    14701   305 
           4   4522    40501   505 
           5   8277    90751   755 
           6  13682   177451  1055 
           7  21037   315001  1405 
           8  30642   520201  1805 
           9  42797   812251  2255 
          10  57802  1212751  2755 
          11  75957  1745701  3305 
          12  97562  2437501  3905 
          13 122917  3316951  4555 
          14 152322  4415251  5255 
          15 186077  5766001  6005 
          16 224482  7405201  6805 
          17 267837  9371251  7655 
          18 316442 11704951  8555 
          19 370597 14449501  9505 
          20 430602 17650501 10505 

Another parametric solution is $(x,y,z)=(2n^3+3n^2-8n-5, (n^2-n-1)(n^2+3n+1), 4n^2+4n-19).$

Answer 3

I will prove that, more generally, for any integer parameters $a,b,c,d$, the solution set to any equation in the form $$ ax^2 + bx + c = dyz $$ is a finite union of polynomial families.

Lemma: Let $S \subset Z^n$ be a finite union of polynomial families. Fix integers $a_1,\dots,a_n$, and positive integers $b_1,\dots,b_n$. Let $S' \subset S$ be the set of all $x=(x_1,\dots, x_n) \in S$ such that $x_i \equiv a_i (\text{mod }b_i)$ for all $i$. Then $S'$ is also a finite union of polynomial families.

Proof: We may assume that $S$ is a polynomial family. By definition, there exists polynomials $P_1,\dots,P_n$ in some variables $u=(u_1,\dots,u_k)$ such that, for every $x \in S$, we have $x_i=P_i(u), i=1,\dots,k$ for some $u \in {\mathbb Z}^k$. Let $m$ be the least common multiple of $b_1,\dots,b_n$. Let $Q$ be the set of vectors $q=(q_1,\dots q_k)$ such that all $q_i$ are integers such that $0 \leq q_i < m$. Let $Q' \subset Q$ be the set of $q \in Q$ such that $P_i(q_1,\dots,q_k)\equiv a_i (\text{mod } b_i)$ for every $i$. For each $q \in Q'$, do a substitution $u_i \to mv_i + q_i$ where $v_i$ is a new variable. Let $P^q_i(v_1,\dots,v_k)=P_i(mv_1 + q_1, \dots, mv_k+q_k)$. This way we have represented $S'$ as the union of $|Q'|$ polynomial families defined by $(P^q_1, \dots, P^q_n)$.

Corollary If the solution set $S$ to the equation $P(x_1,\dots,x_n)$ is a finite union of polynomial families, then so is the solution set $S'$ to the equation $P(b_1x_1-a_1,\dots,b_nx_n-a_n)=0$ for integers $a_1,\dots,a_n$ and non-zero integers $b_1,\dots,b_n$.

Now multiply the equation $ax^2+bx+c = dyz$ by $4a$ to get $4adyz = (2ax+b)^2 + 4ac-b^2$. This is the equation of the form $yz=x^2-D$ with $D=b^2-4ac$ with the restriction that $x \equiv -b (\text{mod } 2a)$ and $y \equiv 0 (\text{mod }4ad)$. As noted in the question, Vaserstein proved that the solution set to $yz=x^2-D$ is a finite union of polynomial families. It is left to apply the corollary.