Having read Omphaloskeptic’s post half a dozen times, I think I’m starting to understand the proof. One step I don’t understand:
…is how you got the equation into the form to the right of the last equal sign. I guess basic algebra, but I can’t replicate the step.
More importantly, is there a way one can then determine the values of the integral* solutions for (x,y) if one starts out with fixed integral values for a & b (and x != b)? Or would one simply be stuck with the problem of factorizing c to arrive at the solutions?
It sucks not being a math person. The word “integral” threw me at first, but I take it that you’re simply using it as the adjective form of “integer.”
I’m pretty sure you’d have to factor. In general, determining integral points of varieties (umm… i’ll explain in a bit[1]) is a very sensitive and case-by-case process, and only estimates can be worked out in general.
Here’s a similar example: Consider again an elliptic curve, but now consider the coefficients and variables to take values which are integers modulo p for some prime p. That is, they’re not integers, but remainders of integers after division by p[2]. Hasse’s theorem states that the number of points N on the curve satisfies
|N - (p+1)| <= 2sqrt(p)
and further that for any N satisfying that inequality, there exists an elliptic curve with N points. That is, without considering specific parameter values this is the best you can say.
[1] What we’re really considering here are not just sets of points, but solution sets of collections of polynomial equations, called “varieties”. The field of algebraic geometry was created to investigate just these sorts of questions.
[2] Using remainders after division by 12 is essentially how clock time works.
Yes, you can get this by long division of polynomials. Dividing a+x[sup]2[/sup] by b-x gives a quotient of -(x+b) and remainder of a+b[sup]2[/sup]. To do long division, you just do the following steps:
Let P be the dividend and D the divisor. Initially the quotient Q is 0.
If the degree (the maximum power of x) of the dividend is less than that of the divisor, stop. The remainder in the dividend is now the long-division remainder.
Remove the highest-order term from the dividend by subtracting out a multiple kx[sup]n[/sup]D of the divisor. (Here k will be the ratio of the coefficients of the highest-order terms in P and D, and n will be the difference in their degrees.) Add a term kx[sup]n[/sup] to the quotient Q, and subtract kx[sup]n[/sup]D from the dividend P.
Go to step 1.
It’s easy to see why this works; at each iteration, step 2 preserves the value of Q+(P/D), but it moves the highest-order terms out of P and into Q until the value left in P has smaller degree than that of D. It is exactly the same as the long-division algorithm used in grade school, except that in grade school you used “powers of 10” explicitly instead of powers of x.
For this example, start with P=a+x[sup]2[/sup], D=b-x, Q=0.
deg(P)=2, deg(D)=1; so we’re not done.
k=1/(-1)=-1; n=deg(P)/deg(D)=1. So add a term -x to Q (now Q=-x), and subtract -x(b-x) from P (now P=a+bx).
deg(P)=1, deg(D)=1; so we’re not done.
k=b/(-1)=-b; n=deg(P)/deg(D)=0. So add a term -b to Q (now Q=-x-b), and subtract -b(b-x) from P (now P=a+b[sup]2[/sup]).
deg(P)=0, deg(D)=1; so we’re done. Now the quotient is Q=-x-b and the remainder is P=a+b[sup]2[/sup].
It’s easy to check: just put all the values over the same denominator b-x:
-(x+b) + (a+b[sup]2[/sup])/(b-x) = -(x+b)(b-x)/(b-x) + (a+b[sup]2[/sup])/(b-x) = (x[sup]2[/sup] - b[sup]2[/sup] + a + b[sup]2[/sup])/(b-x) = (x[sup]2[/sup]+a)/(b-x), the original form.
If there were an easier way than just factoring c, then you could use this as a clever trick to factor integers quickly. (Given c, it’s easy to find a and b such that c=a+b[sup]2[/sup], so given the number c to factor, we’d just compute such a and b, break RSA, and, depending on our inclinations, either steal a fortune or make a mathematical name for ourselves.) Since factoring large integers is believed to be hard, it seems unlikely that such a thing exists.
Sorry about the use of “integral.” Using “integer” as an adjective still grates on me sometimes, but “integral” has its own problems too.
Hey Mathochist, since you brought up elliptic curves: I’m reading Silverman and Tate’s undergrad intro to elliptic curves (Rational Points on Elliptic Curves), which (never having run into elliptic curves except as related to integration and doubly-periodic functions) I like quite a bit — actually I find the idea of thinking of elliptic curves as groups utterly beautiful. But sometimes I’d like more details; do you have a recommendation for a readable but more advanced book on the same stuff (elliptic curves, with an emphasis on Diophantine analysis)?
Wow. Thanks, guys! This helps a bunch. So would it be fair to conclude the following:
Finding an integral solution for (x,y) in the hyperbola described by y = (a+x^2) / (b-x) where a & b are positive integers and b != x is essentially the same problem as factoring (b^2 + a)?
Why is factoring so hard, anyway? I understand trial division becomes impractical past numbers of a certain size. I understand we have some pretty complicated sieve-like algorithms that are a significant improvement over trial divison. I’ve read that, given a quantum computer, the problem would be a snap. But could it be that there is, out there, somewhere, a simple algorithm for factorising a non-prime integer into its component primes? Since it’s pretty easy to multiply those primes together, doesn’t it stand to reason that there’s a fairly simple way to undo the same operation? Or have mathematicians pretty much proven that such a simple route is not possible?
And what’s the term for this: factoring or factorizing?
No one even knows at this point whether it is hard. If you could answer why it’s hard, you’d probably be at least 20-30 years ahead of the best and brightest mathematicians and computer scientists of today.
Yep. Find it, publish it, and if you’re not proven wrong after two years, you get a million bucks.
No. A very large part of modern cryptography is based on the fact that this doesn’t hold.
Nope. Complexity theory is a very young discipline, and it appears to be a lot harder than what we’ve enountered so far.
…based on the fact that we haven’t found such simple solutions or based on the fact that we’ve demonstrated that no simple solutions exist for analogous problems? In other words, have we proven that there are a number of relatively simple operations which have no simple “reversals,” and, due to that, it actually stands to reason that something as simple as multiplication does not have a simple solution for reversing it?
Basically, is it just a fluke that no one’s found a way to factor large numbers and we’re assuming it’s hard because none of the great math minds have yet found a way, or do we have sound mathematical reason to believe there is no way?
Sorry, I was unclear. No one has proof that factorization is hard or easy, but there are functions which are easy to calculate that seem to be very hard to invert. Again, proving that a problem is hard is a major breakthrough.
OK. First, it seems like we’ve got more than two parameters with the hyperbola (distance between the asymptotes, for one), but perhaps that’s intruding into the “rigid motions.” But forgetting this, given just the hyperbola, we don’t know anything about the cone of which the hyperbola is a section other than the fact the cone contains all the points in the hyperbola?
Let’s call our two hyperbola parameters, which we know: HP
Let’s call our three cone-plane parameters, which we don’t know: CP
Is there only one valid set of values for CP? In other words, even if we can’t determine CP, can we still be sure that there’s exactly one cone instance out there that our hyperbola is a section of?
Could we approximate CP by guessing values, drawing the cone for those values, comparing the hyperbola revealed by the intersecting plane with the original hyperbola on the same plane, and repeating the process to minimize the difference in HP? Realizing we could never by such means be certain of CP, but we could come up with a pretty good guess.
I’m not sure what you mean by “distance between the asymptotes”–the asymptotes intersect. Do you mean the distance between the two arcs? That is a function of the two given parameters.
More generally, it’s well known (and easy to see) that by rigid rotation and translation you can convert any hyperbola to standard form, (x/a)[sup]2[/sup]-(y/b)[sup]2[/sup]=1. There are clearly only two parameters in this equation, a and b. You can make different choices of parameters, but in any case you will have only two independent real parameters relevant to the equation.
The answer is No. Parameter counting indicates that there’s a one-parameter family of solutions for CP, for a given hyperbola HP. That is, there’s one “knob” you can turn, to simultaneously adjust the three cone-plane parameters in such a way that the intersection of the cone and plane remains the same. (It’s not actually too hard to work this out. You can find a function for the angle H between the hyperbola’s asymptotes as a function of the cone’s opening angle C and the angle between the cone’s axis and the plane P. The distance between the hyperbola’s vertices V is proportional to the distance from the cone’s vertex to the plane D, and also depends on some function of C and P. So we can adjust C and P to keep H constant, and then vary D to keep V constant.)