5
$\begingroup$

We consider only polynomial with integer coefficients. We know how to determine the first perfect square value but we don't know how to determine subsequent perfect square values except by testing every single value of the variable x.

As an example we have p(x) = 9 x^2 + 13x + 2. we have p(x)=64 for x=2. We can see that there are no other values of x < 2 for which p(x) takes a perfect square value by simply testing x=1 and x=0. We don't want to test every single value.

Given the value of the variable x that produced the perfect square value of the polynomial, is there a method or an algorithm or a test that can tell us that there is no other value smaller than x that will produce another perfect square value of the polynomial?

As an example where p(x) can take a perfect square value more than once, we have p(x) = 9x^2 + 13x + 1. p(x)=121 for x=3 and p(x)=1 for x=0.

$\endgroup$

4 Answers 4

3
$\begingroup$

I assume you're looking for integer values of $x$.

If, as in your examples, your polynomial $p$ is quadratic, it's quite easy to determine the integer solutions to $p(x) = y^2$. Look up "Pell's equation".

For polynomials of higher degree, the question is much more difficult. If the curve $p(x) - y^2$ has genus $> 1$, Faltings's theorem says there are only finitely many rational points, but I don't know if there are effective bounds.

$\endgroup$
4
  • $\begingroup$ thanks for the suggestion. and yes, I am only interested in integer values of x. In fact, if the polynomial represents a prime, then we already know that there can only be one value of the variable x that will make the polynomial take a perfect square value. But if we are using the method as a primality test, we are not supposed to know we are dealing with a prime unless we can show that there is only one value of x. $\endgroup$
    – user25406
    Feb 9, 2015 at 3:13
  • $\begingroup$ What do you mean by "the polynomial represents a prime"? $\endgroup$ Feb 9, 2015 at 5:10
  • $\begingroup$ @user25406: I also find your statement "the polynomial represents a prime" ambiguous. For example, $P(x) = 2x^2+2x+5$ represents a prime for $x = 0,2,3,6,\dots$. However, there is an infinite number of positive integer $x$ such that $P(x)$ is a square (by solving the Pell equation $p^2-2q^2=1$). $\endgroup$ Feb 9, 2015 at 6:40
  • $\begingroup$ @RobertIsrael, TitoPiezas. The first polynomial was derived for a prime but similar polynomial can also be derived for composite integers. And it's only in that sense that I used it and not in the sense of a "prime producing polynomial". $\endgroup$
    – user25406
    Feb 9, 2015 at 13:23
3
$\begingroup$

When in equation square:

$$y^2=a^2x^2+bx+c$$

This is equivalent to the representation of a number as the difference of squares. Means decisions not endless. To start with $s=1$ and finish when $x$ is less than 2.

And use the formula.

$$y=\frac{a}{s}\left(c-\left(\frac{b+s}{2a}\right)^2\right)+\frac{b+s}{2a}$$

$$x=\frac{1}{s}\left(c-\left(\frac{b+s}{2a}\right)^2\right)$$

$\endgroup$
4
  • $\begingroup$ individ, can you please post the derivation of your formula when you have a moment ( or a link ). I am curious to see if your formula involves factoring. If we can determine, without using factoring, that a polynomial of the kind above cannot take more than one perfect square value corresponding to N=1xp for a smaller value of the variable, then we would have a simple primality test. $\endgroup$
    – user25406
    Feb 19, 2015 at 16:56
  • $\begingroup$ I know the @ sign is missing so most probably individ will not get notified about my above comment. Can someone write a comment to notify individ so that I can get his answer while I am trying to figure out why I can't use @individ. thanks. $\endgroup$
    – user25406
    Feb 19, 2015 at 16:58
  • $\begingroup$ @user25406 I can only write the formula itself - without conclusion. The calculation method is original and has not been published yet. I can't do on the forum to tell. Although I think this formula is enough. It allows you to do a large bust. And during the search you can see how many decisions will be. You can do the search only to $x$ - that he was whole. $\endgroup$
    – individ
    Feb 19, 2015 at 17:24
  • $\begingroup$ thank you. please post a link to your paper when you publish your findings. $\endgroup$
    – user25406
    Feb 19, 2015 at 20:05
2
$\begingroup$

The problem is rather old and simple. Solved always standard. In Your case boils down to the need to solve equations of the form.

$$y^2=ax^2+bx+c$$

You can see the discussion here. https://mathoverflow.net/questions/31118/integer-polynomials-taking-square-values

Although they persistently looking for the sequence, but for the case when:

$$y^2=ax^2+bx+q^2$$

The solution can be written quite simply. To do this, use the following equation Pell.

$$p^2-as^2=1$$

Using the solutions of the Pell equation solution can be written as :

$$x=(2qp+bs)s$$

$$y=qp^2+bps+aqs^2$$

In order to find all solutions of this equation Pell often use the exponentiation of the sum with the root of the coefficient. It is difficult and does not make sense. It is better to make the sequence knowing the first solution of the Pell equation $(p_0 ; s_0 )$. Then using any solution $(p_1 ; s_1 )$ can be found the following. To do this, use the formula.

$$p_2=p_0p_1+ay_0y_1$$

$$y_2=y_0p_1+p_0y_1$$

To find the first solution of the Pell equation easily. This is a standard procedure. Need to decompose the root factor in the continued fraction. The difficulty will be when $c$ is not a square.

There are several formulas you can use. http://www.artofproblemsolving.com/blog/103509

http://www.artofproblemsolving.com/blog/101140

The problem still boils down to any of the Pell equation. For this purpose it is necessary to make the replacement of the $x\longrightarrow(x+r)$ or such $y\longrightarrow(y+r)$ . Further standard to seek solutions to the Pell equation.

$\endgroup$
5
  • $\begingroup$ This is all for the quadratic case, right? $\endgroup$ Feb 9, 2015 at 7:10
  • $\begingroup$ @RobertIsrael Enough to do the replacement $x=y-x$ And then check whether the resulting equation to have a solution. Or the number of solutions of course. $\endgroup$
    – individ
    Feb 9, 2015 at 7:31
  • $\begingroup$ @individ, a from your Pell equation must not be a square but in the polynomial p(x)=9x^2 + 13x +2, a=9=3^2. and c=2 not being a square introduces another difficulty (as you pointed out yourself). And I just don't know of a way around these difficulties. So my next question to you is: do you know of a way to handle this kind of difficulties? $\endgroup$
    – user25406
    Feb 9, 2015 at 15:00
  • $\begingroup$ @individ: I am asking if it is possible to prove that the expressions $$x=(2qp+bs)s$$ $$y=qp^2+bps+aqs^2$$ are the only solution of that equation. $\endgroup$
    – Safwane
    Jul 15, 2021 at 15:39
  • $\begingroup$ @Safwane No. The peculiarity of the equations of the Pell type is that there can be written infinitely many different formulas that will describe its solutions. There are just some formulas that most fully describe all the solutions. The form of the equation can also change. By various substitutions and transformations, and this will lead to a different formula. $\endgroup$
    – individ
    Jul 15, 2021 at 15:50
1
$\begingroup$

To explore the equation $$y^2=9x^2+13x+2$$ first multiply by $36=4\times 9$ to obtain $$(6y)^2=4\cdot(9x)^2+4\cdot 13\cdot9x+72=(18x+13)^2-97$$ so that $$(18x+13)^2-(6y)^2=(18x+6y+13)(18x-6y+13)=97$$

For integer solutions you have that $97$ is prime, so the factors are $1$ and $97$ or $-1$ and $-97$. Either way the difference between the factors is $12y=\pm96$ so that $y=\pm8$ and $x$ must be a solution of $9x^2+13x+2=64$. From there you have:

$$(9x+31)(x-2)=9x^2+13x-62$$

For $y^2=a^2x^2+bx+c$ multiply by $4a^2$ and complete the square to get $$(2ay)^2=(2a^2x+b)^2+4a^2c-b^2$$and proceed similarly. You have to test all factorisations at the end.

$\endgroup$
4
  • $\begingroup$ Note for the second example, the same product comes out at $133=1\times 133=7\times 19$ and you have to test $y=\pm 11$ and $y=\pm 1$, which replicates the solutions you have found. $\endgroup$ Feb 9, 2015 at 16:14
  • $\begingroup$ Note that this works smoothly because the coefficient of $x$ is a square and there is no need to revert to the Pell Equation machinery in this case. For a general quadratic, you need the general theory. $\endgroup$ Feb 9, 2015 at 16:18
  • $\begingroup$ Thanks Mark. I was hoping for two things. That there is a general method to find a smaller value than the value that corresponds to N=1xN or at least to be be able to say such a value does not exist without having to test every single value that is smaller. And second, that the method does not involve factoring. $\endgroup$
    – user25406
    Feb 16, 2015 at 22:54
  • $\begingroup$ Sorry it took so long to accept the answer. I lost track of this post. $\endgroup$
    – user25406
    Sep 19, 2022 at 21:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .