wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Curves Paradox?
        
(Message started by: Barukh on Jul 30^th, 2006, 4:44am)

Title: Curves Paradox?
Post by Barukh on Jul 30^th, 2006, 4:44am

Consider the following polynomial equation in 2 variables x, y:

a₁x³ + a₂y³ + a₃x²y + a₄xy² + a₅x² + a₆y² + a₇xy + a₈x + a₉y + a₁₀ = 0,

where a₁, …, a₁₀ are fixed real coefficients. The set of all the points satisfying this equation is called a cubic plane curve. This is because the highest sum of powers in any term of the polynomial equals to 3 (compare: a line is defined by a linear equation with three coefficients; the general conic – by a quadratic equation with six coefficients).

If we are given any ten coefficients a₁, …, a₁₀, do they determine the cubic curve uniquely? The answer is no, since we can always “normalize” the polynomial by dividing through one of the non-zero coefficients. This leaves 9 free coefficients. Therefore, if 9 arbitrary points (x₁, y₁), …, (x₉, y₉) are given in the plane, then plugging them into the polynomial, we get a linear system of 9 equations in 9 unknowns. Thus, we get the following proposition:

Proposition 1. There exists a unique cubic curve passing through 9 given points in the plane.

(Compare: there is a unique line passing through 2 points; a unique conic passing through 5 points).

On the other hand, the instance of the following theorem (http://mathworld.wolfram.com/BezoutsTheorem.html) gives the

Proposition 2. There exist two cubic curves intersecting in 9 (= 3x3) points.

Question: How to resolve this contradiction?

Title: Re: Curves Paradox?
Post by BNC on Jul 30^th, 2006, 5:12am

Just a quick observation:

Taking the 4th power, the polynomial will have 15 coefficients. Hence, according to the logic above, 14 points define it. The theorem quoted suggests up to 16 (4*4) intersection points.

[note: missing a "+" sign before the xy term].

Title: Re: Curves Paradox?
Post by Barukh on Jul 30^th, 2006, 11:28pm

on 07/30/06 at 05:12:43, BNC wrote:

;)

Quote:

[note: missing a "+" sign before the xy term].

Thanks, fixed.

Title: Re: Curves Paradox?
Post by SWF on Jul 31^st, 2006, 10:13pm

If all 9 of the arbitrary points have the same value of y, you are left with a cubic which can have only 3 possible values of x. So you can't fit it though 9 arbitrary points.

Title: Re: Curves Paradox?
Post by Barukh on Aug 1^st, 2006, 1:21am

SWF, in the case you mentioned the cubic is degenerated into a line, which means all the coefficients but a₁₀ will be equal to 0. Still, it is a unique (degenerate) cubic passing through these points.

It’s true that in this particular case another cubic won’t intersect it in 9 points. Therefore, the second proposition states the existence of such cubics – are you doubting this?

Title: Re: Curves Paradox?
Post by pex on Aug 1^st, 2006, 1:32am

on 08/01/06 at 01:21:34, Barukh wrote:

SWF, in the case you mentioned the cubic is degenerated into a line, which means all the coefficients but a₁₀ will be equal to 0.

Now that would be a cool curve! I would personally prefer to have a₈ nonzero as well. ;)

A propos the real problem, I do not yet have an idea...

Title: Re: Curves Paradox?
Post by Barukh on Aug 1^st, 2006, 1:52am

on 08/01/06 at 01:32:23, pex wrote:

Now that would be a cool curve! I would personally prefer to have a₈ nonzero as well. ;)

Oops... Of course! The a₉ will also be non-zero! ;D

Title: Re: Curves Paradox?
Post by Aravis on Aug 1^st, 2006, 6:30am

After looking at wikipedia's definition of Bezout's Theorem, I think we may have a starting point to work off this problem. I think our problem is that we have to seemingly violate Bezout's theorem, and find a way to reduce the number of intersection points predicted.

Wikipedia gives the example of two circles intersecting. As we can imagine, two circles intersect at just two points when we graph them. However, Bezout predicts four intersection points (2*2=4). This seemingly violates Bezout's Theorem as well.

Here is where I get lost and require assistance from somebody with more mathematical acumen. Supposedly, the circles intersect on the complex plane as well, in two points, and thus the circles actually intersect in four points, but only two points on the real plane.

We also know that we can specify a circle with three points. Therefore, if we just look at Bezout's and this fact, we have that three points exacly define a circle, but supposedly all circles intersect at four points. This is also a paradox.

As far as I can tell, the resolution comes from showing that some of the intersections predicted by Bezout's theorem lie in the complex plane.

Thus I believe (note: I cannot prove this whatsoever) that the resolution to our problem with our own paradox is that some number of the intersection points predicted by Bezout's for two cubic plane curves will lie in the imaginary plane.

If anybody can flesh this out (ie. use real math rather than handwaving), please do.

Title: Re: Curves Paradox?
Post by SMQ on Aug 1^st, 2006, 6:59am

I was first thinking along the same lines as Aravis, but... consider the two curves y = x^3 - 4x and its "opposite" x = y^3 - 4y. These are clearly both cubic plane curves, and plotting them shows they clearly intersect in nine distinct points. Therefore it must be proposition 1 which is in error: at least some sets of nine points do not uniquely determine a cubic plane curve.

--SMQ

Title: Re: Curves Paradox?
Post by Aravis on Aug 1^st, 2006, 7:38am

Hmm...
Well, lets look at this then...
Lets pretend we make the matrix to solve the system of linear equations.
Furthermore, use as points the intersection points of the two curves in question.

We need to prove that at least two of the lines of the matrix are degenerate, and give us no information.

In the example provided by SMQ, we can very easily see that the two curves intersect at (0,0).

Thus when we look at the line in the matrix specified by this point, we find that we have zeroes straight across. This eliminates some of the information we needed to specify the equation.

I posit (again, no proof) that given any set of nine intersection points between two plane curves, the system of linear equations generated by plugging those nine points into out equation for a plane curve will be degenerate.

If we can come up with a formula for the intersection points between two arbitrary plane curves, we might be able to prove this.

If it helps, the formula for the intersection points for the system SMQ described is (i believe)
x⁹-12x⁷+48x⁴-68x³-17x=0

Title: Re: Curves Paradox?
Post by towr on Aug 1^st, 2006, 7:52am

I don't see why a system of 9 linear equation in 9 variables would necessarily be uniquely solvable. They aren't necessarily linearly independent, are they?

Title: Re: Curves Paradox?
Post by Aravis on Aug 1^st, 2006, 10:01am

That's what I'm guessing too. However, if we really want to nail this 'paradox' down, we need to prove that for any nine points on a curve, they either do not uniquely specify that curve (the equations are not linearly independant) or they are not the intersection points between the curve and another curve.

Unfortunately, I can't figure out how to do that.

Title: Re: Curves Paradox?
Post by Barukh on Aug 1^st, 2006, 10:48am

Good points, Aravis and towr!

Aravis, of your two stated propositions, which one seems to you more plausible?

Title: Re: Curves Paradox?
Post by towr on Aug 1^st, 2006, 1:13pm

There's one straigthforward class of sets of points for which there are multiple solutions, based on SMQ's example. Namely where the set maps to itself if mirrored in the line x=y. In that case, for any curve that results, you can switch x and y, and get a curve of the same shape in a different orientation through the same points.
The exception is of course when the curve also mirrors in x=y.

There's more options from symmetry though. I'd hazard to guess there are at least 4 cubic curves through the points {-1,0,1} x {-1,0,1}, if any.

Title: Re: Curves Paradox?
Post by Aravis on Aug 1^st, 2006, 1:15pm

on 08/01/06 at 10:48:16, Barukh wrote:

Good points, Aravis and towr!

Aravis, of your two stated propositions, which one seems to you more plausible?

From SMQ's example of a case where there are nine intersections, it would seem to me that the second proposition (i.e. the nine equations are not linearly independant given the nine intersection points) would probably be right.

Title: Re: Curves Paradox?
Post by towr on Aug 1^st, 2006, 1:35pm

For my example of nine points, the linear dependence is also the case.
And the solution for the resulting curves is as follows:
x (1- x^2) = r y ( 1 - y^2)
(should be quite obvious that for any r the curve passes the points, both sides are always 0 in those points)

Title: Re: Curves Paradox?
Post by Deedlit on Aug 1^st, 2006, 3:14pm

on 08/01/06 at 10:01:25, Aravis wrote:

A proof hardly seems necessary; the two statements are obviously contradictory, right? Perhaps you are looking for some greater understanding of the situation that would make it less confusing; this is a less precise goal than finding a proof, however.

Title: Re: Curves Paradox?
Post by SWF on Aug 1^st, 2006, 9:05pm

I don't know what I was thinking (if at all) on my post last night. That's the last time I try a drive by post the night after 5 straight days of playing golf (and going to work on some of those days). Despite my blunder, I don't think this problem belongs in the Hard section, since it is fairly well known that a system of linear equations need not have a unique solution.

Title: Re: Curves Paradox?
Post by rmsgrey on Aug 2^nd, 2006, 5:08am

on 08/01/06 at 07:38:52, Aravis wrote:

In the example provided by SMQ, we can very easily see that the two curves intersect at (0,0).

Thus when we look at the line in the matrix specified by this point, we find that we have zeroes straight across. This eliminates some of the information we needed to specify the equation.

Just a quick nitpick - looking at (0,0) tells us that a₁₀=0 rather than telling us nothing...

Title: Re: Curves Paradox?
Post by Aravis on Aug 2^nd, 2006, 5:09am

on 08/01/06 at 15:14:50, Deedlit wrote:

Well, yes, they are contradictory, but so are the two original propositions. In my mind I just rephrased the two propositions. We already knew that the two could not exist simultaneously, and I gave a theory as to when which proposition holds true, i.e. whether the nine points describe a linearly independant set of nine equations.

I am not satisfied though, because I have given no reasoning. I don't really need proof, but more thought should be given. I feel that my statements are equivalent to saying 'things fall because they are heavier than air' Yes, this may be true, but it misses the real reasons behind why things fall.

Title: Re: Curves Paradox?
Post by towr on Aug 2^nd, 2006, 5:21am

I suppose it might be interesting to examine for what set of 9 points there actually is a unique curve through them. (Or equivalently what makes the system of equations linearly independent)

Title: Re: Curves Paradox?
Post by Grimbal on Aug 3^rd, 2006, 4:50am

on 08/01/06 at 13:13:04, towr wrote:

There's more options from symmetry though. I'd hazard to guess there are at least 4 cubic curves through the points {-1,0,1} x {-1,0,1}, if any.

a curve like a·(x³-x) + b·(y³-y)

In fact any set of points that is an intersection of 3 x values and 3 y values would match multiple curves.

[edit]Just realized that towr gave an equivalent formulation[/edit]

Title: Re: Curves Paradox?
Post by towr on Aug 3^rd, 2006, 5:15am

on 08/03/06 at 04:50:55, Grimbal wrote:

In fact any set of points that is an intersection of 3 x values and 3 y values would match multiple curves.

How about any affine transformation of such a set?
Scaling and translation is obvious, but how about shear and rotation?

Title: Re: Curves Paradox?
Post by Grimbal on Aug 3^rd, 2006, 7:45am

An affine substitution of x,y -> u,v wouldn't change the order of a polynomial on these variables. So it seems that all sets of 9 points that are generated by intersecting 2 sets of 3 parallel lines match an infinity of curves.

I think it is far from covering all cases, like all variations of intersecting two S-shaped curves as SMQ did.

Title: Re: Curves Paradox?
Post by SWF on Aug 3^rd, 2006, 6:54pm

If you have N parameters (a1, a2, ..., aN) that make the polynomial equal zero, and N-1 linear equations from plugging in different points (x1,y1), (x2,y2), ..., there are an infinite number of solutions if the rank of the matrix of linear equations is less than N-1. For this to be, the determinant of each (N-1) by (N-1) matrix left over after deleting a column must equal zero.

For a simple example, if the equation is a1*x + a2*y + a3 = 0, and you plug in (x1,y1) and (x2,y2) the linear equations are:
{0} . [ x1 y1 1]
{0} = [ x2 y2 1] * {a1,a2,a3}^T

(That is supposed to be a 2 by 3 matrix in the middle)

For an infinite number of solutions, the determinants after deleting each column in the matrix must all be zero: 0 = y1-y2 = x1-x2 = x1*y2-x2*y1. This can only happen if x1=x2 and y1=y2.

The algebra for the cubic with 10 parameters would be messy, but this approach should give conditions for multiple solutions.

Title: Re: Curves Paradox?
Post by towr on Aug 4^th, 2006, 1:34pm

Something that occured to me. If you have 9 points that are on the intersection of three parallel lines with three other parallel lines, can be described in 8 numbers.
You only need the direction of both sets of lines (2 numbers), and the distances of the line to a the origin (2 x 3 numbers).
So that's 8 degrees of freedom, one too few for uniquely defining a cubic curve.

Similarly any set of 9 points which takes less than 9 degrees of freedom would, I propose, not uniquely define a cubic curve.

Title: Re: Curves Paradox?
Post by Deedlit on Aug 4^th, 2006, 3:51pm

Keep in mind that whether a set of points defines a unique cubic curve is a property of that specific set of points, whereas degrees of freedom depend on which particular subspace we are saying that set of points belongs. For example, any set of nine points can be said to belong to a subspace in which 5 of the points are always present, and the other 4 can be arbitrary. This has 8 degrees of freedom.

Title: Re: Curves Paradox?
Post by Barukh on Sep 22^nd, 2006, 11:27pm

I forgot to mention that this problem is called Cramer's Paradox (http://www.mathpages.com/home/kmath207/kmath207.htm).