5
$\begingroup$

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

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

5 Answers 5

5
$\begingroup$

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]))
$\endgroup$
2
  • $\begingroup$ Thanks jc the link above is great. Looking into it in detail now. $\endgroup$
    – Mau
    Jul 8, 2010 at 22:35
  • 3
    $\begingroup$ 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)$.) $\endgroup$
    – shreevatsa
    Jul 8, 2010 at 22:57
2
$\begingroup$

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=

$\endgroup$
1
  • $\begingroup$ Thanks! Without getting into ECs, the 2nd degree case can be solved with Pell's method. $\endgroup$
    – Mau
    Jul 15, 2010 at 21:01
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Brilliant! Nice resource! $\endgroup$
    – Mau
    Jul 15, 2010 at 21:03
0
$\begingroup$

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

$\endgroup$
-3
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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