Wikipedia:Reference desk/Archives/Mathematics/2012 March 28

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 28

Determining whether a given polynomial is square.

Given a polynomial p(x), is it possible to tell for what integer values of x make p(x) prime? p(x) = x⁴ + x³ + x² + x + 1. The only solution I've found is x = 3, p(x) = 121, and I think it's the only one.

I've tried taking the square root, which gets me p(x) = (x^2 + 1/2 x + 3/8)² + 5/8 x + 55/64. However, this does not seem to be useful. I was attempting to get it in the form sqrt(p(x)) = sqrt(a(x)) + b(x), and then solve a(x) is a square and b(x) is an integer. But instead I got sqrt(p(x)) = sqrt(a(x) + b(x)).

Then I tried to use modular arithmetic to find restrictions on x. p(x) = x(x+1)(x² + 1) + 1, so I split n=sqrt(p(x)) into two cases, even and odd. If n is even, then p(x) is divisible by 4, which is impossible. So n must be odd. I tried other mods, but I couldn't get anything useful.

Is there another method of solving this, or should I stick with the modular arithmetic? Eaglenoise (talk) 18:11, 28 March 2012 (UTC)

Most of them look prime to me:

 x                  p(x)
--                 ----
-6                 1111
-5                  521
-4                  205
-3                   61
-2                   11
-1                    1
 0                    1
 1                    5
 2                   31
 3                  121
 4                  341
 5                  781
 6                 1555

Of that list, the only p(x)'s over 1 that aren't prime are 121 (11 squared), 205 (5×41) and 1555 (5×311). StuRat (talk) 19:54, 28 March 2012 (UTC)

Clarification needed: Do you mean to check for it being squared, as you said in the title, or prime, as you said in the first line ? If you meant squared, then I only find three values, where x is between -999 and 999:

 x                  p(x)
--                 ----
-1                    1
 0                    1
 3                  121

Somebody else will have to help you with a proof that there are no more beyond that. StuRat (talk) 21:43, 28 March 2012 (UTC)

Yes, I meant p(x) is a square. Sorry about that. And it says positive integers, so I think 3 is the only solution. Eaglenoise (talk) 23:47, 28 March 2012 (UTC)

OK, do you need a proof, or can we mark this resolved ? StuRat (talk) 01:28, 29 March 2012 (UTC)

I think it needs to be a proof. Not necessarily a formal one, but I need to show that no other solutions exist, using something better than proof by lots of samples. Eaglenoise (talk) 01:46, 29 March 2012 (UTC)

You can use calculus to do it. If you let y = √(x⁴+x³+x²+x+1), then you can write the Taylor series expansion for y in terms of 1/x. I just used Wolfram Alpha for this [1] to find y = x² + x/2 + 3/8 + 5/16x + O(1/x²) but it can be done by hand also. The x² + x/2 + 3/8 part differs from an integer by at least 1/8, so I think if you can find a bound on x over which the tail of the series is below 1/8 using Taylor's theorem you'll prove what you need. Then check all x below this bound explicitly as StuRat was doing. Rckrone (talk) 14:34, 29 March 2012 (UTC)

Okay, after several ninth degree polynomials, I've got it down to a simple inequality. Thanks! Eaglenoise (talk) 02:38, 30 March 2012 (UTC)

Resolved

An apparent counter-example against the completeness of Presburger Arithmetic:

Our Article claims that Presburger Arithmetic is complete. Isn't the following proposition a counter-example?

• ∀x ¬(x+x=1)

77.127.183.58 (talk) 19:06, 28 March 2012 (UTC)

What makes you think that proposition is unprovable in Presburger Arithmetic? If I remember correctly, Presburger Arithmetic is more or less Peano Arithmetic without multiplication, so you still have induction. It should be a simple matter to prove that by induction. --Trovatore (talk) 19:20, 28 March 2012 (UTC)

Hello Trovatore, I'm from the restrahnt (rather than the restrnt). Just think about the model of all rational non-negative numbers: This model satisfies Presburger axioms, yet not the proposition I've suggested. This proves that my proposition is not provable in Presburger Arithmetic. Similarly, the model of all non-negative integers, proves that the negation of my proposition is not provable (in Presburger Arithmetic) either. 77.127.183.58 (talk) 19:42, 28 March 2012 (UTC)

I may be speaking out of turn, but it would seem to me that in the model of non-negative rational numbers that the axiom schema 5 (induction) is not satisfied. If it was, one could prove all sorts of mathematical weirdnesses for rational numbers. — Quondum^☏✎ 20:04, 28 March 2012 (UTC)

Yes, I see. Thank you all. 77.127.183.58 (talk) 20:16, 28 March 2012 (UTC)

Implementing RK45 Correctly

Hey everyone, so I am trying to write my own RK45 and it will solve a 2x2 system of ODEs. The RHS will be F(x,y) returning (x',y'). For just a single ODE where our right-hand side is just a scalar x'=f(x), we compute k1,k2,k3,k4,k5,k6 and then we get $y_{k+1}$ (which is the 4th-order approximation) and $z_{k+1}$ (which is the 5th-order approximation). Then we get the scalar
$s=\left[{\frac {({\textrm {tolerance}})({\textrm {current\,time\,step}})}{2|z_{k+1}-y_{k+1}|}}\right]^{1/4}$
and the optimal time step is then the scalar times the current time step.

First question, after I get the scalar, I am supposed to repeat the RK step with this new time step, right? Because the first attempt was just "experimentation" to see what would be the optimal step size. So for every step, I have to do RK twice?

Second, if I have to repeat twice, then the second time should I do RK4 or RK5? RK4 would require a total of 10 function calls and RK5 will require a total of 12 function calls.

Third, if I don't have to repeat twice, then why not? Do I just use one of the approximations I already computed, $y_{k+1}$ or $z_{k+1}$? And should I just use $z_{k+1}$ because I have already computed it AND it is fifth order accurate.

Fourth, finally for my vector function (x',y')=F(x,y), which norm should I use in the denominator for the scalar? Just the Euclidean norm or the max or what? Thanks! - Looking for Wisdom and Insight! (talk) 23:07, 28 March 2012 (UTC)

Maybe a question for the computing ref desk? Or include some wikilinks to the relevant articles, so people know exactly what it's about... Ssscienccce (84.197.178.75) (talk) 12:19, 1 April 2012 (UTC)

Well, I thought it was more relevant here than at the computer science desk and I thought people here would know RK methods. Here is the Runge–Kutta–Fehlberg_method I was talking about. Either the questions are so obvious that no one thought they needed answering or the questions are so uncommon that no one has any answers or suggestions. I googled too and couldn't really come up with anything satisfactory for any of these questions. So any help would still be appreciated. - Looking for Wisdom and Insight! (talk) 10:22, 2 April 2012 (UTC)