5

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

Mau
  • 51
  • 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 08 '10 at 21:11
  • Thanks! I updated the question: I'm interested in quadratic polynomials. – Mau Jul 08 '10 at 21:18
  • 2
    This seems a bit localized/low-level for MO... at least, in my hasty and inexpert view – Yemon Choi Jul 08 '10 at 21:25
  • 1
    @jc: thanks, I had misstated the problem. Using the quadratic formula gives all real values, but I just want the integer ones. – Mau Jul 08 '10 at 21:30
  • 7
    When P is quadratic one can use the theory of Pell equations (http://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 08 '10 at 21:43
  • 3
    @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 08 '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 08 '10 at 22:59
  • @KB: thanks. Interesting to see you have a different valid series from the valid one presented by shreevatsa in the comments to the answer below. Is there a way to go from one representation to the other? – Mau Jul 08 '10 at 23:49
  • @Mau: yes. You just eliminate one of the variables in shreevatsa's solution and get mine. – Kevin Buzzard Jul 09 '10 at 06:41
  • @Kevin, if $n^2=37x^2+3$, then $|(n/x)-\sqrt{37}|<1/(4x^2)$, so $n/x$ is a convergent of the continued fraction for $\sqrt{37}$. That continued fraction is simply $[6;12,12,12,\dots]$ and alternate convergents give $n^2-37x^2=\pm1$. So, no solutions to $n^2=37x^2+3$, and no need to bring in primes in the quadratic field. – Gerry Myerson Sep 22 '22 at 06:02
  • That's true, but it's also true that this trick will not work in general to answer the general question asked by the OP. It's also true that whilst your solution avoids using the theory of factoring in quadratic fields (something we teach to undergraduates at my university), it does use a big chunk of the theory of continued fractions (something we don't). – Kevin Buzzard Sep 25 '22 at 16:03

5 Answers5

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]))
Glorfindel
  • 2,743
j.c.
  • 13,490
  • Thanks jc the link above is great. Looking into it in detail now. – Mau Jul 08 '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 08 '10 at 22:57
2

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=

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

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

Max Alekseyev
  • 30,425
0

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.

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

Community
  • 1
Mbel
  • 11
-3

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.

individ
  • 448