3

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 \}$.

flag
3 
 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 2010 at 21:11
1 
 This seems a bit localized/low-level for MO... at least, in my hasty and inexpert view – Yemon Choi Jul 8 2010 at 21:25
6 
 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 2010 at 21:43
2 
 @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 2010 at 22:48
4 
 @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 2010 at 22:59
show 4 more comments

3 Answers

5

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]))

link|flag
Thanks jc the link above is great. Looking into it in detail now. – Mau Jul 8 2010 at 22:35
3 
 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 2010 at 22:57
1

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

link|flag
Brilliant! Nice resource! – Mau Jul 15 2010 at 21:03
1

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

http://www.google.com/search?hl=en&source=hp&q=rational+points+on+elliptic+curves&aq=0&aqi=g5&aql=&oq=rational+points+on+&gs_rfai=

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

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.