mersenneforum.org Solving Quartic Equation with a Coefficient of 1 MB Space
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2020-03-19, 15:08 #1 Andrew99   Aug 2019 11 Posts 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)?
2020-03-19, 20:22   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Andrew99 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

2020-03-20, 06:09   #3
LaurV
Romulan Interpreter

Jun 2011
Thailand

863610 Posts

Quote:
 Originally Posted by Andrew99 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

2020-03-20, 08:19   #4
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by LaurV 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.

 2020-03-20, 12:06 #6 Dr Sardonicus     Feb 2017 Nowhere 334910 Posts 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.
2020-03-20, 13:23   #7
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by LaurV 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

 2020-03-20, 15:08 #8 CRGreathouse     Aug 2006 16EF16 Posts 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.
2020-03-20, 18:01   #9
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by CRGreathouse 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.

2020-03-20, 18:16   #10
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,381 Posts

Quote:
 Originally Posted by CRGreathouse 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

2020-03-20, 18:18   #11
xilman
Bamboozled!

May 2003
Down not across

2·5,101 Posts

Quote:
 Originally Posted by R.D. Silverman 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post aein Factoring 3 2017-02-25 16:42 fivemack Factoring 6 2011-12-12 05:08 Unregistered Homework Help 2 2009-03-03 19:56 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