Need help solving a complicated algebraic equation

Other scientific, philosophical, mathematical etc. topics go here.

Need help solving a complicated algebraic equation

Postby quickfur » Wed Feb 03, 2016 6:42 pm

After two days of futile work on the following equation, I'm at a loss as to how to proceed any further:

√( (1 - B2) / (2*B2) ) = √(1 + 2*B2) + B

How do you simplify this equation to form a polynomial in B (without all those nasty radicals)?

Basically, this equation arises in the course of solving for the coordinates of the snub disphenoid. It seems to be of the correct form, because Wolfram Alpha is able to solve it and produce an algebraic expression that matches what's given in the Wikipedia article on the snub disphenoid. What I'm interested in, though, is how to get from this equation to the solution that Wolfram Alpha gives? According to the Wikipedia article, part of it involves solving a cubic equation; however, no matter how I try, I can't seem to get a cubic equation out of this. What are the common methods for attacking such complicated equations? Any tips?
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Need help solving a complicated algebraic equation

Postby Klitzing » Wed Feb 03, 2016 10:06 pm

First you take the roots onto one side and the remainder to the other
Code: Select all
sqrt((1-B²)/(2*B²))-sqrt(1+2*B²)=B

then you take the square of either side
Code: Select all
(1-B²)/(2*B²)-2*sqrt((1-B²)*(1+2*B²)/(2*B²))+1+2*B²=B²

then you take once again the remaining root onto one side and the rest onto the other
Code: Select all
(1-B²)/(2*B²)+1+B²=2*sqrt((1-B²)*(1+2*B²)/(2*B²))

now you have to square each side again, and the roots will have gone!

--- rk
Klitzing
Pentonian
 
Posts: 1637
Joined: Sun Aug 19, 2012 11:16 am
Location: Heidenheim, Germany

Re: Need help solving a complicated algebraic equation

Postby student91 » Wed Feb 03, 2016 10:10 pm

First, I would substitute; so I would try to solve an equation of the form
sqrt(a)=sqrt(b)+c. After squaring both sides, then getting b+c^2 to the other side, and finally squaring both sides again, this gives me a^2+b^2+c^4-2ab-2c^2(a+b)=0. But I guess you could use wolfram to get from sqrt(a)=sqrt(b)+c to something reliable.

Then it's just some routinework getting all back in again and working the fractions away
student91
Tetronian
 
Posts: 328
Joined: Tue Dec 10, 2013 3:41 pm

Re: Need help solving a complicated algebraic equation

Postby quickfur » Wed Feb 03, 2016 10:21 pm

Haha, didn't think anybody would answer so quickly. :P

I've actually figured out the trouble I was having. I had already tried the squaring method yesterday, but ended up with a quartic equation in B^2 (a degree 8 polynomial in B !!), so I thought I must have done something wrong, since both Wikipedia and Wolfram state the solution as the root of a cubic in B^2. Turns out, that the quartic I obtained was actually correct:

4*u4 + 20*u3 - 3*u2 - 6*u + 1 = 0

where u = B2.

What was missing, and probably can only be realized in retrospect, is that this quartic is divisible by (2*u - 1), yielding:

(2*u - 1)*(2*u3 + 11*u2 + 4*u - 1) = 0

The (2*u - 1) factor leads to the solution B^2 = 1/2, which turns out to be an inadmissible solution because when substituted into the other equations for the snub disphenoid, it causes the height to also be 1/√2, which is invalid because the original construction assumed that B should be strictly less than the total height.

So, throwing out the B^2=1/2 root, we are left finally with the desired cubic:

2*u3 + 11*u2 + 4*u - 1 = 0

which, checking with Wolfram again, yields the correct value for B^2.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Need help solving a complicated algebraic equation

Postby quickfur » Wed Feb 03, 2016 10:36 pm

This isn't the end of the story, though. This particular cubic has 3 irrational real roots, which means the roots cannot be expressed in terms of radicals over the reals. They are expressible as radicals over the complex numbers, though, even though their ultimate values are real.

Which is a bummer, because it means that in order to actually compute the value of B (on the computer, that is), I'll need to be able to compute the cube roots of complex numbers, which eventually will involve trigonometric functions. Which is OK, except that the expressions involved are very unwieldy, and probably I can get a more accurate value just by applying Newton's method to the cubic equation. (Or an implementation of inverse cubic interpolation, which my language of choice happens to provide in the standard library. :P)
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Need help solving a complicated algebraic equation

Postby quickfur » Wed Feb 17, 2016 12:23 pm

Just a quick update and further question:

So I finally worked out the cubic equation that yields the correct value of B, and, by suitable substitutions into some of the original equations, I was able to obtain polynomial expressions for all 3 unknowns in the coordinates of the snub disphenoid. This allowed me to write out the full coordinates (edge length 2, origin-centered) as follows:

Code: Select all
<0, A, ±1>
<±C, B, 0>
<0, -B, ±C>
<±1, -A, 0>

where the values of A, B, and C are expressed by:

Code: Select all
   -4 -  8u -   u² + 2u³ = 0, 2≤u≤3, A=√u
   -1 +  4v + 11v² + 2v³ = 0, 0≤v≤1, B=√v
  -64 + 64w - 17w² +  w³ = 0, 1≤w≤2, C=√w

The ranges given for u, v, and w are for selecting the correct roots of the cubics, since they have multiple values.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Need help solving a complicated algebraic equation

Postby quickfur » Wed Feb 17, 2016 12:41 pm

And now the further question. After the success with the snub disphenoid, I'm now trying to tackle the problem of algebraically expressing the coordinates of J86, the sphenocorona. This one is turning out to be quite a beast, since there are 5 unknowns in 5 non-linear equations, and thus far I have not been able to make much progress. I'm arbitrarily choosing y=0 to be the vertical coordinate of the far edges of the two squares (i.e., opposite the shared edge), which gives the coordinates as:

Code: Select all
<0, A, ±1>
<±P, 0, ±1>
<0, B, ±Q>
<±1, C, 0>

with the constraints:
Code: Select all
[0] C < B < 0 < A
[1] P² + A² = 3
[2] (B-A)² + (Q-1)² = 4
[3] P² + B² + (Q-1)² = 4
[4] (1-P)² + C² = 3
[5] (C-B)² + Q² = 3


Equations [1], [2], [3] combine nicely to give:
Code: Select all
P² = 3 - A²
B = A - 3/(2A)

but beyond that, things get ugly really quickly.

I did manage to derive an interestingly symmetric pair of equations for A and C:
Code: Select all
C² = A² - 1 + 2√(3-A²)
A² = C² - 1 ± 2√(3-C²)

(the ± in the second equation hasn't been resolved yet, but my suspicion is that it should be a +).

But I can't get any further in terms of obtaining an equation in a single variable that would allow the derivation of an actual solution to the system of quadratic equations.

So the question is, what are some of the techniques and tricks one could use for tackling these sorts of equations? It took me many days (weeks, even) of trial and error just to get as far as the above, with lots of dead-ends, expressions that are far too big to manually work with, and many pages of scrap paper, and still the solution is nowhere in sight. I've even tried computing Gröbner bases for the equations, but that also turned out to be unworkable because the number of equations quickly exploded exponentially (or so it felt) and it became impractical to work with. So how does one work with these things in general??

And, on that note, how did people derive the coordinates for these polyhedra, if solving the equations algebraically proves so intractible? By numerical approximations? If so, how do we prove that these are actual Johnson solids (i.e., all faces are regular polygons), rather than very very near misses?
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Need help solving a complicated algebraic equation

Postby student91 » Thu Feb 25, 2016 11:14 pm

quickfur wrote:[..]So how does one work with these things in general??

And, on that note, how did people derive the coordinates for these polyhedra, if solving the equations algebraically proves so intractible? By numerical approximations? If so, how do we prove that these are actual Johnson solids (i.e., all faces are regular polygons), rather than very very near misses?

I haven't found any algebraic expressions for those coordinates on the internet, I suspect nobody ever tried to calculate these. However, the fact that you do get 5 unknowns in 5 equations does prove that this system is solvable, and thus the solid exist. Were you to have more equations than unknowns, you could get a near miss.
I wouldn't know how to solve these equations further though, but frankly I didn't look very deep into it yet. Maybe I'll give it a shot, but I'm not sure I'll get a result (like with the 600-cell diminishings, those turned out to be more complicated than I thought.)
student91
Tetronian
 
Posts: 328
Joined: Tue Dec 10, 2013 3:41 pm

Re: Need help solving a complicated algebraic equation

Postby quickfur » Fri Feb 26, 2016 8:04 pm

Actually, Wolfram Alpha does respond with algebraic coordinates to the query "sphenocorona coordinates". They appear to be generated by some kind of degree 4 or degree 6 polynomials. So somebody has obviously solved this before. Unfortunately, I couldn't coax the polynomials themselves from Wolfram Alpha.

Also, when it comes to non-linear equations, just because there are 5 equations and 5 unknowns does not guarantee the existence of a solution, or even a unique solution. I think you have to calculate either the Gröbner basis or something related to that, to know whether there is a solution, and whether there's a unique solution or multiple (countable/finite) solutions, or infinitely many solutions. The world of non-linear systems of equations is a lot less well-behaved than linear systems.

As for 600-cell diminishings, yeah, there's not only a lot of them out there, but there are also a lot of deep cuts that generate CRFs, with or without modifications after the initial cut(s). The 600-cell is a veritable gold mine of CRFs, and I think we've only barely scratched the surface of the possibilities so far. And this isn't even considering the analogues of these 600-cell truncates among the 600-cell family uniform polychora. Although obviously many of them will have no analogues, I believe a large subset do, and as far as I know, so far no one (none of us, at any rate) has managed to get a handle yet on exactly when and which 600-cell diminishings have analogues to a diminishing of a given uniform polychoron in this family.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Need help solving a complicated algebraic equation

Postby Keiji » Thu Mar 10, 2016 6:50 pm

quickfur wrote:Just a quick update and further question:

So I finally worked out the cubic equation that yields the correct value of B, and, by suitable substitutions into some of the original equations, I was able to obtain polynomial expressions for all 3 unknowns in the coordinates of the snub disphenoid. This allowed me to write out the full coordinates (edge length 2, origin-centered) as follows:

Code: Select all
<0, A, ±1>
<±C, B, 0>
<0, -B, ±C>
<±1, -A, 0>

where the values of A, B, and C are expressed by:

Code: Select all
   -4 -  8u -   u² + 2u³ = 0, 2≤u≤3, A=√u
   -1 +  4v + 11v² + 2v³ = 0, 0≤v≤1, B=√v
  -64 + 64w - 17w² +  w³ = 0, 1≤w≤2, C=√w

The ranges given for u, v, and w are for selecting the correct roots of the cubics, since they have multiple values.


Great to see you're still working on these! Is there any chance you could write up your derivation on the snub disphenoid article?

Incidentally, Wolfram|Alpha gets very confused when I paste in your equation for u - apparently there's a tiny imaginary component:

u =~ 2.45819+3.70074×10^-17 i

But when I click "More Digits", it decides otherwise:

u =~ 2.4581907758724858000+0.×10^-19 i

Even weirder, the above is "copyable plaintext", but the image says 20 instead of 19 at the end! Even though that doesn't make a difference - zero to the power of something is still zero of course.
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Need help solving a complicated algebraic equation

Postby quickfur » Fri Mar 11, 2016 1:35 am

The derivation is long and very ugly, involving lots of nasty-looking high-order polynomials that look like they're ready to jump off the page and eat your face. :P But perhaps it's worth summarizing the derivations (with a hand-wave of "omitted long algebraic derivation here") for posterity's sake. Fortunately I kept the entire derivation in a text file on my computer, so I don't have to repeat the ordeal of actually doing the derivation again. I much rather just post the resulting polynomials as I did in my earlier post, which should be enough information for anyone who's interested to run it through, say, Newton's algorithm or one of the fancy new cubic-interpolating algorithms to generate as many digits as they need for the roots.

(Having said that, though, the polynomials involved in the snub disphenoid's coordinates are pretty tame compared to the insanity that is the equations for the sphenocorona. Boy, that one really gives you a taste of just how nasty a seemingly-innocuous system of 2nd order equations can get. I have managed to get to the point where, in theory, I should be able to eliminate 4 variables and get an equation in a single variable that can be solved via polynomial root extraction. However, I say "in theory" because the substitutions involved would require squaring both sides 3-4 times, which means we're talking about a 8- to 16-fold increase in the degree of the polynomial, and the current equation is already degree 3 or 4. Each squaring multiplies the number of terms like rabbits, and the result is just so completely unwieldy that I'm not sure I have the stomach for it. How one is supposed to derive a supposedly order-4 equation from it (judging by asking Wolfram Alpha for the coordinates of the sphenocorona), eludes me. I suppose this is only tractable with a CAS like Mathematica. And mind you, this is just one of the 5 unknowns in the system; there's no telling what will happen once we obtain the value of the first unknown and substitute it into the rest of the equations!)

(Nevertheless, the sphenocorona's system of equations is evidently still within the reach of CAS algorithms... I asked Wolfram Alpha for the coordinates of the sphenomegacorona, and it doesn't even try to give me algebraic expressions for it, just decimal expansions. My guess is that Mathematica, or whatever it is Wolfram Alpha uses in the backend, is unable to cope with the most likely utterly insane complexity of an algebraic solution, and just resorts to one of the numerical algorithms to find the solution. I have been doing some research in algorithms for solving systems of polynomial equations, and so far we haven't managed to get very far beyond the Buchberger's algorithm for computing the Gröbner basis -- this algorithm is generally exponential in time complexity, and in the case of lexicographical ordering needed for solving individual variables, doubly-exponential (i.e., O(2^2^k)). Meaning to say, that past relatively small values of k, it is completely infeasible to compute an algebraic solution; you might as well just give up and use numerical algorithms instead. There has been various improvements to Buchberger's original algorithm, but still, they do not eliminate the double-exponential complexity, they just improve the coefficients. And a double-exponential grows so fast that even for small values of k (like, say, near 8-10 or more) it will quickly become infeasible.)

(And on that note, I used to think that since for CRFs we're really only dealing with polynomials of degree at most 2, so what's the big deal, right? Unfortunately, in the general case, degree 2 is equivalent to an arbitrarily large degree -- because you can always rewrite a system of higher-order polynomials as quadratics, by introducing new variables x and adding equations of the form x=y^2 to the system -- this way you can get as high as you want while the equations themselves only appear to be no higher than degree 2. So the fact that we're only dealing with quadratics in the starting equations doesn't really save us anything... if anything, it's probably only masking the true complexity of the system. To be able to solve these systems, you basically have to deal with polynomials of arbitrarily high degree -- and in multiple variables at that. It's an active area of research, from what I can tell, and thus far I have yet to find any research papers that have major breakthroughs in how to reduce the complexity of these things. It may well be the case that these systems are inherently complex, and are irreducible in the general case. Which, unfortunately, is bad news for us CRF hunters, because that means brute-force computer search will not be easy to implement without some major insight that gives us a feasible handle on the problem. Or, if you're an optimist, this might be construed to be good news, because the inherent complexity of these quadratic systems means that there should be plenty of places for unusual CRF crown jewels to hide in. :P We'd never run out of a job, so to speak, since a lot of ingenious insights will be required to find these crown jewels.)
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Need help solving a complicated algebraic equation

Postby quickfur » Fri Mar 11, 2016 1:41 am

P.S., about Wolfram Alpha's numerical approximations to the roots of cubic equations, this is actually not very surprising, because the formula for computing the roots of a cubic polynomial involves taking the square root of negative numbers. In the case where the polynomial has 3 real roots, the resulting complex numbers will have their imaginary terms cancel out, so the final answer will be real. However, it is actually not possible to express some of these roots algebraically without using complex numbers; it is inherent to the solution of cubics (historically, this is known as "casus irreducibilis").

My guess is that for a first approximation, Wolfram Alpha uses low-precision floats for the computation, and there is a slight roundoff error that causes the imaginary terms to not completely cancel out. But upon repeating the computation with higher precision, the roundoff error is lessened and the cancellation occurs, as it should.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Need help solving a complicated algebraic equation

Postby quickfur » Sun Mar 13, 2016 8:29 am

Keiji wrote:[...]
Great to see you're still working on these! Is there any chance you could write up your derivation on the snub disphenoid article?
[...]

The deed is done. :o Due to the length of the derivation, I decided to put it in its own page (Derivation of snub disphenoid coordinates), linked from the main snub disphenoid page.

(A lot of the tedious algebraic manipulations have been left out from the page, since it would cause it to double in length (possibly more!). Only the key points of the derivations are included. I also omitted some dead-end solution routes that I attempted. There was a lot of groping in the dark, misfired attempts at solving that ended up in a forest of polynomials of unmanageable length, etc.. The factorization of the quartic, in particular, was somewhat of a cheating move, since it was nigh impossible for anyone to guess at the linear factor. Or, for that matter, that factorization was possible at all. I only knew about it because Wolfram Alpha gave me that factorization. :oops: I did check my results via polynomial long division, though. That was fun. Systems of quadratic equations are evil!! :angry: )
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Need help solving a complicated algebraic equation

Postby Keiji » Sun Mar 13, 2016 11:09 am

Ooh, that's excellent. Thanks!

My equation solving techniques are rather rusty and were never good in the first place, so it's nice to be able to read through and understand this just from the (re)learning algebra point of view.

(Plus it's good to have the process documented in case anyone wants to use and check it, of course!)
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Need help solving a complicated algebraic equation

Postby quickfur » Sun Mar 13, 2016 10:44 pm

Well, I did skip a lot of intermediate steps in the derivation, so this may not be the best way to (re)learn algebraic solution methods... Plus, a lot of the steps require clairvoyance, i.e., why a particular step was taken and how one could have known to do that, is only clear in retrospect. This, of course, is a result of lots of trial-and-error and backtracking from dead ends, but to someone reading for the first time, it could give the baffling feeling that some seemingly arbitrary step was randomly chosen and somehow it magically leads to the solution. :P
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Need help solving a complicated algebraic equation

Postby ICN5D » Thu Mar 31, 2016 2:18 am

This is cool, I like this. I don't know if you've seen it in the toratopes thread, but I taught myself how to factor toratope x-section equations. It's all in notepad text, and not very presentable. But, the algorithm does work, and yields some interesting results. Lately, I tested it on lemniscate curves of T^n , and what the exact roots are, on the x-axis. I'm putting some images together that illustrate a bit better.
It is by will alone, I set my donuts in motion
ICN5D
Pentonian
 
Posts: 1135
Joined: Mon Jul 28, 2008 4:25 am
Location: the Land of Flowers


Return to General

Who is online

Users browsing this forum: No registered users and 1 guest

cron