 mersenneforum.org Solving Quartic Equation with a Coefficient of 1 MB Space
 Register FAQ Search Today's Posts Mark Forums Read  2020-03-19, 15:08 #1 Andrew99   Aug 2019 1110 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?
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

"name field"
Jun 2011
Thailand

24×613 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, 10:26 #5 LaurV Romulan Interpreter   "name field" Jun 2011 Thailand 100110010100002 Posts 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   2020-03-20, 12:06 #6 Dr Sardonicus   Feb 2017 Nowhere 2×3×853 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 3·1,993 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

2·3·11·23 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

24·13·53 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.   Thread Tools Show Printable Version Email this Page 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 22:56.

Mon Nov 29 22:56:07 UTC 2021 up 129 days, 17:25, 0 users, load averages: 2.00, 1.50, 1.36 