mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory > PARI/GP

Reply
 
Thread Tools
Old 2020-03-19, 15:08   #1
Andrew99
 
Aug 2019

11 Posts
Default Solving Quartic Equation with a Coefficient of 1 MB Space

I have an equation of 4 degree (Quartic equation)and a coefficient of this equation takes 1 megabyte space in a text file. I want to solve this Quartic equation using computer. If the the equation has rational solution, I want to get rational solution with the exact numerator and the exact denominator (not the approximation). Is it possible?


There are are programming languages (e.g. MAGMA), computer algebra systems (e.g. PARI/GP, SageMath etc, here PARI is C library, can be called from a high-level language application ,for instance, written in C, C++, Pascal, Fortran, Perl, or Python).

If possible, then which programming language or computer algebra systems or library or softaware will be best to solve the Quartic equation as described above? What are the additional issues (configurations of RAM, Processor)?
Andrew99 is offline   Reply With Quote
Old 2020-03-19, 20:22   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Andrew99 View Post
I have an equation of 4 degree (Quartic equation)and a coefficient of this equation takes 1 megabyte space in a text file. I want to solve this Quartic equation using computer. If the the equation has rational solution, I want to get rational solution with the exact numerator and the exact denominator (not the approximation). Is it possible?
We need more information. Is the polynomial constant a prime number?
Is the lead coefficient a prime? [or monic]? If not, are these coefficients special in some way?

Please explain why you need/want to do this.

Also, please show us that you have some understanding of the problem by explaining
why I asked what I did. Why are these questions important?

Also, tell us what you want to do if there are no rational solutions. A full solution via Ferrari's
formula will be one total cluster f*ck.

Last fiddled with by R.D. Silverman on 2020-03-19 at 20:26
R.D. Silverman is offline   Reply With Quote
Old 2020-03-20, 06:09   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

863610 Posts
Default

Quote:
Originally Posted by Andrew99 View Post
I have an equation of 4 degree (Quartic equation)and a coefficient of this equation takes 1 megabyte space in a text file. I want to solve this Quartic equation using computer. If the the equation has rational solution, I want to get rational solution with the exact numerator and the exact denominator (not the approximation). Is it possible?
Yes.

Everything is possible if you have the know-how, the resources, and the patience.
Are all the coefficients integers? (if rationals, amplify to the LCM of denominators).
How many coefficients? (i.e. can you reduce to degree 2 or 3 by substitutions?)

Can you solve the equation in \(ℝ\) (to know approximations of solution?)
Can you apply Newton method (google-google) in the vicinity of the solutions to get to the rational solution? (or as better as needed rational approximation?) (you may keep those lines in the rational domain by some tricks, you can start rational, and store the numerator and denominator separate, like, in fact, pari does).

Edit: Ha!? It seems like AMS symbols don't work in matjax? I had to cheat that R by using UTF8 symbol

Last fiddled with by LaurV on 2020-03-20 at 06:34
LaurV is offline   Reply With Quote
Old 2020-03-20, 08:19   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by LaurV View Post
Yes.

Everything is possible if you have the know-how, the resources, and the patience.
False. Grossly false.
`
Quote:
Are all the coefficients integers? (if rationals, amplify to the LCM of denominators).
How many coefficients? (i.e. can you reduce to degree 2 or 3 by substitutions?)
(1) You should have waited until the O.P. answers my questions.
(2) You are wrong in your assertions. Reduction to lower degree requires
that the equation has rational solutions. The O.P. did not say that it does.
Indeed. Determining whether it does was part of the problem.
(3) You totally` missed the point of my questions!!!!!
(4) We don't even know if it has solutions in R. I would not want to compute a
Sturm sequence.
R.D. Silverman is offline   Reply With Quote
Old 2020-03-20, 10:26   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·17·127 Posts
Default

It depends how you look at it. I still assert that everything is possible, if you have enough resources, know how, and patience.

Sorry not to wait for the OP to reply to your questions, I know you had very good reasons to ask them (and I know a part of those reasons, indeed not all of them), but I just went a step ahead and I assumed the OP wants to make a factorization. I went that way long time ago (and banged my head on the wall, because, of course, I am not enough clever nor I know enough math. etc etc).

About your point 2, well, that is false. Reduction to lower degree does NOT require the solutions to be rational. Think about X^4-2=0, it has no rational solution, and still it can be written as Y^2-2=0, by substituting X^2=Y. Also think about how people few centuries ago used to solve (a subset of) cubic equations, making clever substitutions to reduce them to quadratics (I could point you to some Mathologer/Numberphile videos, hihi, but I am sure you know that already better than me, you just brainfarted or made a typo ).

Last fiddled with by LaurV on 2020-03-20 at 10:36
LaurV is offline   Reply With Quote
Old 2020-03-20, 12:06   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

334910 Posts
Default

It is not clear to me that the question is even being posed seriously. I will assume, for the sake of discussion, that it is.

I wonder where the coefficients came from. Are they integers? Exact fractions? What?

The clause "a coefficient of this equation takes 1 megabyte space in a text file" is ambiguous. Does it only apply to one of the coefficients, or do theyall require that much space? Or is, perhaps, the polynomial monic?

Assuming the coefficients are integers, one could also ask what is actually known about them. Are they of some special form?

In addition to LaurV's suggestion of approximate solution, there is also (assuming integer coefficients) the possibility of reducing the polynomial (mod p) for small prime numbers p. Assuming the coefficients are integers, and the reduction is not the zero polynomial in Fp[x], it can easily be factored in Fp[x]. If any of these mod p factorizations have no linear factors, you have the answer to your rational zeroes question -- there aren't any.
Dr Sardonicus is offline   Reply With Quote
Old 2020-03-20, 13:23   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by LaurV View Post

About your point 2, well, that is false. Reduction to lower degree does NOT require the solutions to be rational. Think about X^4-2=0, it has no rational solution, and still it can be written as Y^2-2=0, by substituting X^2=Y.
The roots are still degree 4. And the substitution does not help find any rational roots. And determining if the quartic is
reducible runs into the same questions that I asked, as well as making any linear transforms.

Last fiddled with by R.D. Silverman on 2020-03-20 at 13:31
R.D. Silverman is offline   Reply With Quote
Old 2020-03-20, 15:08   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

16EF16 Posts
Default

There's a closed algebraic form for the solutions of a quartic, so you can just substitute away and be done. The solutions mightl be, say, 20 MB each before simplification, but that shouldn't be a problem. You can then simplify and check if they're rational as desired.
CRGreathouse is offline   Reply With Quote
Old 2020-03-20, 18:01   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
There's a closed algebraic form for the solutions of a quartic, so you can just substitute away and be done. The solutions mightl be, say, 20 MB each before simplification, but that shouldn't be a problem. You can then simplify and check if they're rational as desired.
I am pretty sure that the solution will be a lot bigger. The discriminant alone
contains 6th degree terms. The solution contains many terms expressed in terms
of the resolvent cubic which itself has many terms in its solution.

I am also unsure whether it CAN be "simplified". Casus irreducibilis says that Cardano's
formula for the resolvent cubic can not be simplified.

I may, of course, be missing something.
R.D. Silverman is offline   Reply With Quote
Old 2020-03-20, 18:16   #10
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,381 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
There's a closed algebraic form for the solutions of a quartic, so you can just substitute away and be done. The solutions mightl be, say, 20 MB each before simplification, but that shouldn't be a problem. You can then simplify and check if they're rational as desired.
No, the rational roots will be shorter, due to https://en.wikipedia.org/wiki/Rational_root_theorem

To find "only" the rational roots, you could (fully) factorize the polynom, an easier/faster way (could be well known, found yesterday) :
Let the polynom in Z[x]: a(n)*x^n+...+a(1)*x+a(0)=0
approximate the (real) roots with better than 1/(2*abs(a(n))) absolute difference.
and for each x0 approximated root test the r=g/a(n) rational number as a root, where g=round(x0*a(n)).
You'll get all rational solutions, and this works for every n.
(you can simplify r by computing gcd(g,a(n)) ,

Ok, small (trivial) example:
Code:
f(x)=10*x^2 - 17*x - 63
let x0=-1.801 approx. solution, then a(2)=10, g=round(-1.801*10)=-18, and
r=-18/10=-9/5 is indeed a rational root.
(and the other root of f(x) is also rational

Last fiddled with by R. Gerbicz on 2020-03-20 at 18:36 Reason: typos
R. Gerbicz is offline   Reply With Quote
Old 2020-03-20, 18:18   #11
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

2·5,101 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I am pretty sure that the solution will be a lot bigger. The discriminant alone
contains 6th degree terms. The solution contains many terms expressed in terms
of the resolvent cubic which itself has many terms in its solution.

I am also unsure whether it CAN be "simplified". Casus irreducibilis says that Cardano's
formula for the resolvent cubic can not be simplified.

I may, of course, be missing something.
We've already established that Bob is an engineer, not a mathematician

Bob doubtless remembers the last time I cracked this gag. Something to do with running the LL test backwards.
xilman is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
reduce number of coefficient for polynomial selection with msieve on GPU aein Factoring 3 2017-02-25 16:42
Don't fear the quartic fivemack Factoring 6 2011-12-12 05:08
Spearman's rank correlation coefficient Unregistered Homework Help 2 2009-03-03 19:56
Quartic: Parameters R.D. Silverman Factoring 9 2009-02-18 23:24

All times are UTC. The time now is 08:26.

Sat Aug 15 08:26:50 UTC 2020 up 2 days, 5:02, 0 users, load averages: 2.22, 2.13, 2.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.