Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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 '10 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 '10 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 '10 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 '10 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 '10 at 22:59
show 4 more comments

3 Answers

up vote 5 down vote accepted

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

share|improve this answer
    
Thanks jc the link above is great. Looking into it in detail now. –  Mau Jul 8 '10 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 '10 at 22:57
add comment

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=

share|improve this answer
    
Thanks! Without getting into ECs, the 2nd degree case can be solved with Pell's method. –  Mau Jul 15 '10 at 21:01
add comment

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

share|improve this answer
    
Brilliant! Nice resource! –  Mau Jul 15 '10 at 21:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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