Integer polynomials taking square values

Is there a way to determine a formula giving all integer values of $x$ for which the value of a polynomial $P(x)$ with integer coefficients is a square?

That is, is there a closed formula for:

$X = \{ x \in \mathbb{N} : \exists \ n \in \mathbb{N} : P(x) = n^2 \}$ ?

I'm interested in particular in $P'(x) = 8x^2-8x+1$, but am wondering about the general case as well.

For $P'(x)$ a sample of $X$ is $\{ 1, 3, 15, 85, 493, 2871, 16731, 97513, \ldots \}$.

-
For $P$ of degree at least $5$, at least for some $n$ the roots of $P(x) - n^2 = 0$ will in general not be solvable by radicals. So in this sense there need not be a closed formula. If you intend something else, please clarify. – Pete L. Clark Jul 8 '10 at 21:11
This seems a bit localized/low-level for MO... at least, in my hasty and inexpert view – Yemon Choi Jul 8 '10 at 21:25
When P is quadratic one can use the theory of Pell equations (en.wikipedia.org/wiki/Pell's_equation). In general the problem is hard; for generic P of degree greater than 2, X is finite by Siegel's theorem, and even the case where P is cubic is a difficult problem about elliptic curves for which one generally needs computer calculations. – Qiaochu Yuan Jul 8 '10 at 21:43
@Qiaochu: even when $P$ is quadratic the question is a little harder than Pell; it is Pell (which is "what are the units in this real quadratic field?") plus a problem about principal ideals: "list all the principal ideals in the integers of this quadratic field with that given norm". For example to solve $n^2=37x^2+3$ you need to figure out whether the factorization of $(3)$ into primes in the integers of $\mathbf{Q}(\sqrt{37})$ is into two principal primes or two non-principal ones. I'll leave it as an exercise ;-) which you can do if you want to convince yourself that Pell alone isnt enough – Kevin Buzzard Jul 8 '10 at 22:48
@OP: for the $8x^2-8x+1$ question you can get the next number in the sequence like this: if $a_n$ is the $n$th term then $a_n=6a_{n-1}-a_{n-2}-2$. Proof by completing the square and then general Pell equation theory. – Kevin Buzzard Jul 8 '10 at 22:59

There's a fairly detailed explanation of the solution to a similar equation here. See also this page, which can give you an automated step-by-step solution to such quadratic diophantine equations.

I'll also add that the command Reduce[8 x^2 - 8 x + 1 - y^2 == 0 && Element[x | y, Integers], {x, y}] will produce the answer to your particular problem in Mathematica fairly quickly. I'm making this an answer because the output is too huge to fit into the comments.

(C[1] [Element] Integers && C[1] >= 0 &&
x == 1/32 (16 +
4 (-2 (17 - 12 Sqrt[2])^C[1] +
Sqrt[2] (17 - 12 Sqrt[2])^C[1] - 2 (17 + 12 Sqrt[2])^C[1] -
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) &&
y == 1/2 ((17 - 12 Sqrt[2])^C[1] -
Sqrt[2] (17 - 12 Sqrt[2])^C[1] + (17 + 12 Sqrt[2])^C[1] +
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) || (C[1] [Element] Integers &&
C[1] >= 0 &&
x == 1/32 (16 +
4 (-2 (17 - 12 Sqrt[2])^C[1] +
Sqrt[2] (17 - 12 Sqrt[2])^C[1] - 2 (17 + 12 Sqrt[2])^C[1] -
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) &&
y == 1/2 (-(17 - 12 Sqrt[2])^C[1] +
Sqrt[2] (17 - 12 Sqrt[2])^C[1] - (17 + 12 Sqrt[2])^C[1] -
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) || (C[1] [Element] Integers &&
C[1] >= 0 &&
x == 1/32 (16 -
4 (-2 (17 - 12 Sqrt[2])^C[1] +
Sqrt[2] (17 - 12 Sqrt[2])^C[1] - 2 (17 + 12 Sqrt[2])^C[1] -
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) &&
y == 1/2 ((17 - 12 Sqrt[2])^C[1] -
Sqrt[2] (17 - 12 Sqrt[2])^C[1] + (17 + 12 Sqrt[2])^C[1] +
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) || (C[1] [Element] Integers &&
C[1] >= 0 &&
x == 1/32 (16 -
4 (-2 (17 - 12 Sqrt[2])^C[1] +
Sqrt[2] (17 - 12 Sqrt[2])^C[1] - 2 (17 + 12 Sqrt[2])^C[1] -
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) &&
y == 1/2 (-(17 - 12 Sqrt[2])^C[1] +
Sqrt[2] (17 - 12 Sqrt[2])^C[1] - (17 + 12 Sqrt[2])^C[1] -
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) || (C[1] [Element] Integers &&
C[1] >= 0 &&
x == 1/32 (16 +
4 (2 (17 - 12 Sqrt[2])^C[1] + Sqrt[2] (17 - 12 Sqrt[2])^C[1] +
2 (17 + 12 Sqrt[2])^C[1] -
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) &&
y == 1/2 (-(17 - 12 Sqrt[2])^C[1] -
Sqrt[2] (17 - 12 Sqrt[2])^C[1] - (17 + 12 Sqrt[2])^C[1] +
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) || (C[1] [Element] Integers &&
C[1] >= 0 &&
x == 1/32 (16 +
4 (2 (17 - 12 Sqrt[2])^C[1] + Sqrt[2] (17 - 12 Sqrt[2])^C[1] +
2 (17 + 12 Sqrt[2])^C[1] -
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) &&
y == 1/2 ((17 - 12 Sqrt[2])^C[1] +
Sqrt[2] (17 - 12 Sqrt[2])^C[1] + (17 + 12 Sqrt[2])^C[1] -
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) || (C[1] [Element] Integers &&
C[1] >= 0 &&
x == 1/32 (16 -
4 (2 (17 - 12 Sqrt[2])^C[1] + Sqrt[2] (17 - 12 Sqrt[2])^C[1] +
2 (17 + 12 Sqrt[2])^C[1] -
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) &&
y == 1/2 (-(17 - 12 Sqrt[2])^C[1] -
Sqrt[2] (17 - 12 Sqrt[2])^C[1] - (17 + 12 Sqrt[2])^C[1] +
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) || (C[1] [Element] Integers &&
C[1] >= 0 &&
x == 1/32 (16 -
4 (2 (17 - 12 Sqrt[2])^C[1] + Sqrt[2] (17 - 12 Sqrt[2])^C[1] +
2 (17 + 12 Sqrt[2])^C[1] -
Sqrt[2] (17 + 12 Sqrt[2])^C[1])) &&
y == 1/2 ((17 - 12 Sqrt[2])^C[1] +
Sqrt[2] (17 - 12 Sqrt[2])^C[1] + (17 + 12 Sqrt[2])^C[1] -
Sqrt[2] (17 + 12 Sqrt[2])^C[1]))

-
Thanks jc the link above is great. Looking into it in detail now. – Mau Jul 8 '10 at 22:35
Just to summarize here the solution given by the second link "Dario Alpern's generic two-integer variable equation solver": all integer solutions to $8x^2 - 8x + 1 = y^2$ are given by \begin{align*}X_{n+1} &= 3X_n + Y_n - 1 \\ Y_{n+1} &= 8X_n + 3Y_n - 4,\end{align*} starting with $(X_0, Y_0)$ as either $(0,1)$ or $(1,-1)$. (The other two (0,-1) and (1,1) are redundant, being generated in one step from these two. It's easy to see that if the $n$th solution given by $(1,-1)$ is $(x,y)$, then $(x,y)$ is positive and the $n$th solution given by $(0,-1)$ is just $(-x+1,-y)$.) – shreevatsa Jul 8 '10 at 22:57

Your sequence is http://oeis.org/classic/A011900

-
Brilliant! Nice resource! – Mau Jul 15 '10 at 21:03

This looks like counting points on hyper-elliptic curves to me...

You are basically finding the integer solutions to

$Y^2 = 8X^2 - 8X + 1$

in you example. But this case is not too difficult, because it's of genus $0$.

It will be more interesting if $P(x)$ is of degree $3$ or higher.

To begin with this very interesting subject of point-counting, probably you can try

-
Thanks! Without getting into ECs, the 2nd degree case can be solved with Pell's method. – Mau Jul 15 '10 at 21:01

In fact, as shown here ( see link ), solving this problem is equivalent to factoring integers. In the link below, it is shown how factoring can be reduced to finding a polynomial with integer coefficients which takes a perfect square value for a given value of the variable.

So finding an efficient method to zoom in on the value of the variable that makes a polynomial take a perfect square value is equivalent to a solution of the factoring problem.

http://math.stackexchange.com/questions/1112015/is-reducing-factoring-of-integers-to-finding-a-polynomial-which-takes-a-perfect

-

For these equations we use the standard approach. For a private quadratic form: $$Y^2=aX^2+bX+1$$

Using solutions of Pell's equation: $$p^2-as^2=1$$

Solutions can be expressed through them is quite simple.

$$Y=p^2+bps+as^2$$

$$X=2ps+bs^2$$

$p,s$ - these numbers can have any sign.

Finding solutions of equations Pell - standard procedure.

-