[math-fun] Iterated averaging of triples
Suppose we have a set of 3 distinct numbers, {a,b,c}. Then averaging them in pairs preserves distinctness: {(a+b)/2,(b+c)/2,(c+a)/2}. Proof: assume not, e.g., (a+b)/2=(b+c)/2 => a=c. Contradiction. QED. So we can go backwards: {a,b,c} => {a+b-c,b+c-a,c+a-b} So, {(a+b)/2,(b+c)/2,(c+a)/2} => {(a+b+b+c-c-a)/2=b,(b+c+c+a-a-b)/2=c,(c+a+a+b-b-c)/2=a} Note also that 'averaging' preserves the sum of the triple (hence its average): (a+b)/2+(b+c)/2+(c+a)/2=a+b+c. Thus, 'going forward' and 'going backwards' preserves this sum. OK, so now let's iterate this averaging process N times. I contend that this process makes the numbers more and more 'average'; i.e., all three converge towards the same number: (a+b+c)/3. Yet, we can still recover our original 3 numbers by running the process backwards N times. Even better, we can go backwards *further* than our original 3 numbers. Curiously, if we start with {-1,0,1}, we get {-2^k,0,2^k}, for all k. Note now that a,b,c need not be 'numbers'; they could be vectors of numbers, so we can play this game in higher dimensions. E.g., we can choose triples of (x,y) pairs to represent triangles, so does iterating them converge towards equilateral triangles?
this is what happens to the x (or y) coordinates of a triangle when you bisect its edges, right? Cris
On Sep 17, 2020, at 11:00 PM, Henry Baker <hbaker1@pipeline.com> wrote:
Suppose we have a set of 3 distinct numbers, {a,b,c}.
Then averaging them in pairs preserves distinctness: {(a+b)/2,(b+c)/2,(c+a)/2}.
Proof: assume not, e.g., (a+b)/2=(b+c)/2 => a=c. Contradiction. QED.
So we can go backwards:
{a,b,c} => {a+b-c,b+c-a,c+a-b}
So, {(a+b)/2,(b+c)/2,(c+a)/2} => {(a+b+b+c-c-a)/2=b,(b+c+c+a-a-b)/2=c,(c+a+a+b-b-c)/2=a}
Note also that 'averaging' preserves the sum of the triple (hence its average): (a+b)/2+(b+c)/2+(c+a)/2=a+b+c. Thus, 'going forward' and 'going backwards' preserves this sum.
OK, so now let's iterate this averaging process N times.
I contend that this process makes the numbers more and more 'average'; i.e., all three converge towards the same number: (a+b+c)/3.
Yet, we can still recover our original 3 numbers by running the process backwards N times.
Even better, we can go backwards *further* than our original 3 numbers.
Curiously, if we start with {-1,0,1}, we get {-2^k,0,2^k}, for all k.
Note now that a,b,c need not be 'numbers'; they could be vectors of numbers, so we can play this game in higher dimensions. E.g., we can choose triples of (x,y) pairs to represent triangles, so does iterating them converge towards equilateral triangles?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://linkprotect.cudasvc.com/url?a=https%3a%2f%2fmailman.xmission.com%2fc...
If you think of the three points as the vertices of a triangle, then the next iteration replaces the points with the center points of the edges. The average is the centroid of the triangle, which is what the sequence converges to. The triangles remain similar to the original, so they do not approach equilateral triangles, but instead retain their original shape. They just keep getting smaller. Each iteration shrinks the triangle and rotates it 180 degrees about the centroid. Tom Henry Baker writes:
Suppose we have a set of 3 distinct numbers, {a,b,c}.
Then averaging them in pairs preserves distinctness: {(a+b)/2,(b+c)/2,(c+a)/2}.
Proof: assume not, e.g., (a+b)/2=(b+c)/2 => a=c. Contradiction. QED.
So we can go backwards:
{a,b,c} => {a+b-c,b+c-a,c+a-b}
So, {(a+b)/2,(b+c)/2,(c+a)/2} => {(a+b+b+c-c-a)/2=b,(b+c+c+a-a-b)/2=c,(c+a+a+b-b-c)/2=a}
Note also that 'averaging' preserves the sum of the triple (hence its average): (a+b)/2+(b+c)/2+(c+a)/2=a+b+c. Thus, 'going forward' and 'going backwards' preserves this sum.
OK, so now let's iterate this averaging process N times.
I contend that this process makes the numbers more and more 'average'; i.e., all three converge towards the same number: (a+b+c)/3.
Yet, we can still recover our original 3 numbers by running the process backwards N times.
Even better, we can go backwards *further* than our original 3 numbers.
Curiously, if we start with {-1,0,1}, we get {-2^k,0,2^k}, for all k.
Note now that a,b,c need not be 'numbers'; they could be vectors of numbers, so we can play this game in higher dimensions. E.g., we can choose triples of (x,y) pairs to represent triangles, so does iterating them converge towards equilateral triangles?
Thanks, Tom! Very interesting! Back to the drawing board, as I'd love a *rational* reversible sequence that converges to an equilateral triangle. At 11:12 PM 9/17/2020, Tom Karzes wrote:
If you think of the three points as the vertices of a triangle, then the next iteration replaces the points with the center points of the edges. The average is the centroid of the triangle, which is what the sequence converges to. The triangles remain similar to the original, so they do not approach equilateral triangles, but instead retain their original shape. They just keep getting smaller. Each iteration shrinks the triangle and rotates it 180 degrees about the centroid.
Tom
Henry Baker writes:
Suppose we have a set of 3 distinct numbers, {a,b,c}.
Then averaging them in pairs preserves distinctness: {(a+b)/2,(b+c)/2,(c+a)/2}.
Proof: assume not, e.g., (a+b)/2=(b+c)/2 => a=c. Contradiction. QED.
So we can go backwards:
{a,b,c} => {a+b-c,b+c-a,c+a-b}
So, {(a+b)/2,(b+c)/2,(c+a)/2} => {(a+b+b+c-c-a)/2=b,(b+c+c+a-a-b)/2=c,(c+a+a+b-b-c)/2=a}
Note also that 'averaging' preserves the sum of the triple (hence its average): (a+b)/2+(b+c)/2+(c+a)/2=a+b+c. Thus, 'going forward' and 'going backwards' preserves this sum.
OK, so now let's iterate this averaging process N times.
I contend that this process makes the numbers more and more 'average'; i.e., all three converge towards the same number: (a+b+c)/3.
Yet, we can still recover our original 3 numbers by running the process backwards N times.
Even better, we can go backwards *further* than our original 3 numbers.
Curiously, if we start with {-1,0,1}, we get {-2^k,0,2^k}, for all k.
Note now that a,b,c need not be 'numbers'; they could be vectors of numbers, so we can play this game in higher dimensions. E.g., we can choose triples of (x,y) pairs to represent triangles, so does iterating them converge towards equilateral triangles?
Here's an SVG image for a 3-4-5 right triangle: https://www.karzes.com/triangle-345.svg You can see from the image how the each step rotates the triangle by 180 degrees and scales it by 1/2, converging on the centroid without changing the shape. Tom Henry Baker writes:
Thanks, Tom!
Very interesting!
Back to the drawing board, as I'd love a *rational* reversible sequence that converges to an equilateral triangle.
At 11:12 PM 9/17/2020, Tom Karzes wrote:
If you think of the three points as the vertices of a triangle, then the next iteration replaces the points with the center points of the edges. The average is the centroid of the triangle, which is what the sequence converges to. The triangles remain similar to the original, so they do not approach equilateral triangles, but instead retain their original shape. They just keep getting smaller. Each iteration shrinks the triangle and rotates it 180 degrees about the centroid.
Tom
Henry Baker writes:
Suppose we have a set of 3 distinct numbers, {a,b,c}.
Then averaging them in pairs preserves distinctness: {(a+b)/2,(b+c)/2,(c+a)/2}.
Proof: assume not, e.g., (a+b)/2=(b+c)/2 => a=c. Contradiction. QED.
So we can go backwards:
{a,b,c} => {a+b-c,b+c-a,c+a-b}
So, {(a+b)/2,(b+c)/2,(c+a)/2} => {(a+b+b+c-c-a)/2=b,(b+c+c+a-a-b)/2=c,(c+a+a+b-b-c)/2=a}
Note also that 'averaging' preserves the sum of the triple (hence its average): (a+b)/2+(b+c)/2+(c+a)/2=a+b+c. Thus, 'going forward' and 'going backwards' preserves this sum.
OK, so now let's iterate this averaging process N times.
I contend that this process makes the numbers more and more 'average'; i.e., all three converge towards the same number: (a+b+c)/3.
Yet, we can still recover our original 3 numbers by running the process backwards N times.
Even better, we can go backwards *further* than our original 3 numbers.
Curiously, if we start with {-1,0,1}, we get {-2^k,0,2^k}, for all k.
Note now that a,b,c need not be 'numbers'; they could be vectors of numbers, so we can play this game in higher dimensions. E.g., we can choose triples of (x,y) pairs to represent triangles, so does iterating them converge towards equilateral triangles?
Maybe https://en.wikipedia.org/wiki/Rational_trigonometry would be useful. On Fri, Sep 18, 2020 at 9:03 AM Henry Baker <hbaker1@pipeline.com> wrote:
Thanks, Tom!
Very interesting!
Back to the drawing board, as I'd love a *rational* reversible sequence that converges to an equilateral triangle.
At 11:12 PM 9/17/2020, Tom Karzes wrote:
If you think of the three points as the vertices of a triangle, then the next iteration replaces the points with the center points of the edges. The average is the centroid of the triangle, which is what the sequence converges to. The triangles remain similar to the original, so they do not approach equilateral triangles, but instead retain their original shape. They just keep getting smaller. Each iteration shrinks the triangle and rotates it 180 degrees about the centroid.
Tom
Henry Baker writes:
Suppose we have a set of 3 distinct numbers, {a,b,c}.
Then averaging them in pairs preserves distinctness: {(a+b)/2,(b+c)/2,(c+a)/2}.
Proof: assume not, e.g., (a+b)/2=(b+c)/2 => a=c. Contradiction. QED.
So we can go backwards:
{a,b,c} => {a+b-c,b+c-a,c+a-b}
So, {(a+b)/2,(b+c)/2,(c+a)/2} => {(a+b+b+c-c-a)/2=b,(b+c+c+a-a-b)/2=c,(c+a+a+b-b-c)/2=a}
Note also that 'averaging' preserves the sum of the triple (hence its average): (a+b)/2+(b+c)/2+(c+a)/2=a+b+c. Thus, 'going forward' and 'going backwards' preserves this sum.
OK, so now let's iterate this averaging process N times.
I contend that this process makes the numbers more and more 'average'; i.e., all three converge towards the same number: (a+b+c)/3.
Yet, we can still recover our original 3 numbers by running the process backwards N times.
Even better, we can go backwards *further* than our original 3 numbers.
Curiously, if we start with {-1,0,1}, we get {-2^k,0,2^k}, for all k.
Note now that a,b,c need not be 'numbers'; they could be vectors of numbers, so we can play this game in higher dimensions. E.g., we can choose triples of (x,y) pairs to represent triangles, so does iterating them converge towards equilateral triangles?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
The triangle inequality a+b>c transforms to 2b>0, and similar for cyclic permutation. If (a,b,c) are positive lengths, even if they do not satisfy the triangle inequality, they will after one iteration. Thereafter the lengths can be folded into a triangle (or it’s mirror image). Similarly, if (a,b,c) are positive angles, choose angular units where a+b+c=pi. All subsequent iterations preserve the sum, so each triple determines a unique triangle (again, up to reflection). By the limiting property, both sequences converge to equilateral. Another possibility is: a = (a+b+c)/3 b = [(a*b)^(1/2)+(b*c)^(1/2)+(c*d)^(1/2)]/3 c = (a*b*c)^(1/3) Is this the best generalization of the agm to three (or more) variables? Does it even converge? —Brad
On Sep 18, 2020, at 12:03 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Suppose we have a set of 3 distinct numbers, {a,b,c}.
Then averaging them in pairs preserves distinctness: {(a+b)/2,(b+c)/2,(c+a)/2}.
Proof: assume not, e.g., (a+b)/2=(b+c)/2 => a=c. Contradiction. QED.
So we can go backwards:
{a,b,c} => {a+b-c,b+c-a,c+a-b}
So, {(a+b)/2,(b+c)/2,(c+a)/2} => {(a+b+b+c-c-a)/2=b,(b+c+c+a-a-b)/2=c,(c+a+a+b-b-c)/2=a}
Note also that 'averaging' preserves the sum of the triple (hence its average): (a+b)/2+(b+c)/2+(c+a)/2=a+b+c. Thus, 'going forward' and 'going backwards' preserves this sum.
OK, so now let's iterate this averaging process N times.
I contend that this process makes the numbers more and more 'average'; i.e., all three converge towards the same number: (a+b+c)/3.
Yet, we can still recover our original 3 numbers by running the process backwards N times.
Even better, we can go backwards *further* than our original 3 numbers.
Curiously, if we start with {-1,0,1}, we get {-2^k,0,2^k}, for all k.
Note now that a,b,c need not be 'numbers'; they could be vectors of numbers, so we can play this game in higher dimensions. E.g., we can choose triples of (x,y) pairs to represent triangles, so does iterating them converge towards equilateral triangles?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Oops, obvious typo where "d" should be "a", sorry. Call this iteration agm3, I checked that: agm3[1,2,3] = 1.8932121023002878019777... converges but it is not in the OEIS. Compare with https://oeis.org/A068521. On Fri, Sep 18, 2020 at 7:40 AM Brad Klee <bradklee@gmail.com> wrote:
Another possibility is:
a = (a+b+c)/3 b = [(a*b)^(1/2)+(b*c)^(1/2)+(c*d)^(1/2)]/3 <## Ed. Note: Typo Here c = (a*b*c)^(1/3)
Is this the best generalization of the agm to three (or more) variables? Does it even converge?
As I previously explained, the vertices converge to a point (the centroid, i.e. (a+b+c)/3), but they do *not* converge to an equilateral triangle. The shape of the triangle is preserved by each step (i.e., the triangles are all similar to each other). Each step scales the triangle by 1/2 and rotates it by 180 degrees about the centroid. It is *not* reflected. Reversing a step is identical, except it is scaled by 2 rather than 1/2. Performing two consecutive steps scales by 1/4 with no rotation. The mappings of old vertices to corresponding new vertices are: a -> (b+c)/2 b -> (a+c)/2 c -> (a+b)/2 Consider the difference between the new a and the new b: (b+c)/2 - (a+c)/2 = (b-a)/2 In other words, the new difference is -1/2 times the old difference (a-b). The length is halved, and the vector is negated (i.e., it is rotated by 180 degrees). This also shows that the ratios of the edge lengths are preserved. For example, consider the ratio of a pair of edge lengths: |a-b| / |a-c| After one iteration, the new ratio is: |(b-a)/2| / |(c-a)/2| = |a-b| / |a-c| Since the edge length ratios never change, clearly the triangles retain their exact shape, and do not converge to equilateral (unless they were equilateral to begin with). You can easily see this by drawing a right triangle, and inside that triangle drawing the triangle formed by the midpoints of each edge (i.e., one iteration). The new triangle is clearly a right triangle, with the exact same shape as the original (but scaled by 1/2 and rotated by 180 degrees). So all triangles will be right triangles, and hence will not converge to an equilateral triangle. Tom Brad Klee writes:
The triangle inequality a+b>c transforms to 2b>0, and similar for cyclic permutation. If (a,b,c) are positive lengths, even if they do not satisfy the triangle inequality, they will after one iteration. Thereafter the lengths can be folded into a triangle (or it’s mirror image). Similarly, if (a,b,c) are positive angles, choose angular units where a+b+c=pi. All subsequent iterations preserve the sum, so each triple determines a unique triangle (again, up to reflection). By the limiting property, both sequences converge to equilateral.
Another possibility is:
a = (a+b+c)/3 b = [(a*b)^(1/2)+(b*c)^(1/2)+(c*d)^(1/2)]/3 c = (a*b*c)^(1/3)
Is this the best generalization of the agm to three (or more) variables? Does it even converge?
—Brad
On Sep 18, 2020, at 12:03 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Suppose we have a set of 3 distinct numbers, {a,b,c}.
Then averaging them in pairs preserves distinctness: {(a+b)/2,(b+c)/2,(c+a)/2}.
Proof: assume not, e.g., (a+b)/2=(b+c)/2 => a=c. Contradiction. QED.
So we can go backwards:
{a,b,c} => {a+b-c,b+c-a,c+a-b}
So, {(a+b)/2,(b+c)/2,(c+a)/2} => {(a+b+b+c-c-a)/2=b,(b+c+c+a-a-b)/2=c,(c+a+a+b-b-c)/2=a}
Note also that 'averaging' preserves the sum of the triple (hence its average): (a+b)/2+(b+c)/2+(c+a)/2=a+b+c. Thus, 'going forward' and 'going backwards' preserves this sum.
OK, so now let's iterate this averaging process N times.
I contend that this process makes the numbers more and more 'average'; i.e., all three converge towards the same number: (a+b+c)/3.
Yet, we can still recover our original 3 numbers by running the process backwards N times.
Even better, we can go backwards *further* than our original 3 numbers.
Curiously, if we start with {-1,0,1}, we get {-2^k,0,2^k}, for all k.
Note now that a,b,c need not be 'numbers'; they could be vectors of numbers, so we can play this game in higher dimensions. E.g., we can choose triples of (x,y) pairs to represent triangles, so does iterating them converge towards equilateral triangles?
The triangle’s staying similar is interesting, and reminded me of something I had read years ago. Elmachtoub and Van Loan had a paper where you start with a random polygon (which is just n random points joined together in order) then did this same process of getting a new polygon as the midpoints of edges. They discovered that regardless of what you started with, you ended up with points that converged to the centroid, but were placed somewhat evenly around an ellipse with the same orientation. This untangling can be proven be rewriting the problem has multiplying a vector by a matrix and seeing convergence as for the power method for finding the dominant eigenvalue of a matrix. The fact that a triangle stays similar must be a special case of their analysis. For those who wish to see the fun that can happen, check out http://www.cs.cornell.edu/cv/ResearchPDF/PolygonSmoothingPaper.pdf Steve On Sep 18, 2020, at 9:47 AM, Tom Karzes <karzes@sonic.net<mailto:karzes@sonic.net>> wrote: As I previously explained, the vertices converge to a point (the centroid, i.e. (a+b+c)/3), but they do *not* converge to an equilateral triangle. The shape of the triangle is preserved by each step (i.e., the triangles are all similar to each other). Each step scales the triangle by 1/2 and rotates it by 180 degrees about the centroid. It is *not* reflected. Reversing a step is identical, except it is scaled by 2 rather than 1/2. Performing two consecutive steps scales by 1/4 with no rotation. The mappings of old vertices to corresponding new vertices are: a -> (b+c)/2 b -> (a+c)/2 c -> (a+b)/2 Consider the difference between the new a and the new b: (b+c)/2 - (a+c)/2 = (b-a)/2 In other words, the new difference is -1/2 times the old difference (a-b). The length is halved, and the vector is negated (i.e., it is rotated by 180 degrees). This also shows that the ratios of the edge lengths are preserved. For example, consider the ratio of a pair of edge lengths: |a-b| / |a-c| After one iteration, the new ratio is: |(b-a)/2| / |(c-a)/2| = |a-b| / |a-c| Since the edge length ratios never change, clearly the triangles retain their exact shape, and do not converge to equilateral (unless they were equilateral to begin with). You can easily see this by drawing a right triangle, and inside that triangle drawing the triangle formed by the midpoints of each edge (i.e., one iteration). The new triangle is clearly a right triangle, with the exact same shape as the original (but scaled by 1/2 and rotated by 180 degrees). So all triangles will be right triangles, and hence will not converge to an equilateral triangle. Tom Brad Klee writes: The triangle inequality a+b>c transforms to 2b>0, and similar for cyclic permutation. If (a,b,c) are positive lengths, even if they do not satisfy the triangle inequality, they will after one iteration. Thereafter the lengths can be folded into a triangle (or it’s mirror image). Similarly, if (a,b,c) are positive angles, choose angular units where a+b+c=pi. All subsequent iterations preserve the sum, so each triple determines a unique triangle (again, up to reflection). By the limiting property, both sequences converge to equilateral. Another possibility is: a = (a+b+c)/3 b = [(a*b)^(1/2)+(b*c)^(1/2)+(c*d)^(1/2)]/3 c = (a*b*c)^(1/3) Is this the best generalization of the agm to three (or more) variables? Does it even converge? —Brad On Sep 18, 2020, at 12:03 AM, Henry Baker <hbaker1@pipeline.com<mailto:hbaker1@pipeline.com>> wrote: Suppose we have a set of 3 distinct numbers, {a,b,c}. Then averaging them in pairs preserves distinctness: {(a+b)/2,(b+c)/2,(c+a)/2}. Proof: assume not, e.g., (a+b)/2=(b+c)/2 => a=c. Contradiction. QED. So we can go backwards: {a,b,c} => {a+b-c,b+c-a,c+a-b} So, {(a+b)/2,(b+c)/2,(c+a)/2} => {(a+b+b+c-c-a)/2=b,(b+c+c+a-a-b)/2=c,(c+a+a+b-b-c)/2=a} Note also that 'averaging' preserves the sum of the triple (hence its average): (a+b)/2+(b+c)/2+(c+a)/2=a+b+c. Thus, 'going forward' and 'going backwards' preserves this sum. OK, so now let's iterate this averaging process N times. I contend that this process makes the numbers more and more 'average'; i.e., all three converge towards the same number: (a+b+c)/3. Yet, we can still recover our original 3 numbers by running the process backwards N times. Even better, we can go backwards *further* than our original 3 numbers. Curiously, if we start with {-1,0,1}, we get {-2^k,0,2^k}, for all k. Note now that a,b,c need not be 'numbers'; they could be vectors of numbers, so we can play this game in higher dimensions. E.g., we can choose triples of (x,y) pairs to represent triangles, so does iterating them converge towards equilateral triangles? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com<mailto:math-fun@mailman.xmission.com> https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg...
Wow, yes this is fun! Here are two (messy) data sets: https://0x0.st/ils7.png https://0x0.st/ilsh.png Each point configuration is labeled with an initial and final score. The two scores seem to be uncorrelated. This is too bad because the ellipse score should go to 1 as the ellipse approaches a circle. Is there a way to score the initial data so that we can tell when it will turn out most like a circle in the end? (I didn't read the paper too closely but did ctrl-f "circle" and didn't find anything relevant.) --Brad On Fri, Sep 18, 2020 at 9:27 AM Lucas, Stephen K - lucassk <lucassk@jmu.edu> wrote:
For those who wish to see the fun that can happen, check out http://www.cs.cornell.edu/cv/ResearchPDF/PolygonSmoothingPaper.pdf
Steve
Very interesting paper! They didn't explicitly talk about reversing or inverses, but their matrices are invertible, so the sequences can be reversed. They also find cases where the iteration converges to a stable cycle. In the triangular case, each 2 'forward' steps produces the 'same' triangle, but 1/4 the size: (%o119) [[a1, a2], [b1, b2], [- (b1 + a1), - (b2 + a2)]] (%i120) forward(%),factor; a1 a2 b1 b2 b1 + a1 b2 + a2 (%o120) [[- --, - --], [- --, - --], [-------, -------]] 2 2 2 2 2 2 (%i121) forward(%),factor; b1 + a1 b2 + a2 b1 b2 a1 a2 (%o121) [[- -------, - -------], [--, --], [--, --]] 4 4 4 4 4 4 (This is a permuted list of the vertices, but scaled by 1/4.) Note that the intermediate step is the *rotation* of the original triangle by 180 degrees, as Tom points out, but scaled by 1/2, as demonstrated on this 3,4,5 right triangle: (%o113) [[- 4, - 3], [8, - 3], [- 4, 6]] (%i114) forward(%)*2; (%o114) [[- 8, 3], [4, - 6], [4, 3]] (%i115) forward(%)*2; (%o115) [[- 4, - 3], [- 4, 6], [8, - 3]] At 07:26 AM 9/18/2020, Lucas, Stephen K - lucassk wrote:
The triangle's staying similar is interesting, and reminded me of something I had read years ago. Elmachtoub and Van Loan had a paper where you start with a random polygon (which is just n random points joined together in order) then did this same process of getting a new polygon as the midpoints of edges. They discovered that regardless of what you started with, you ended up with points that converged to the centroid, but were placed somewhat evenly around an ellipse with the same orientation. This untangling can be proven be rewriting the problem has multiplying a vector by a matrix and seeing convergence as for the power method for finding the dominant eigenvalue of a matrix. The fact that a triangle stays similar must be a special case of their analysis.
For those who wish to see the fun that can happen, check out http://www.cs.cornell.edu/cv/ResearchPDF/PolygonSmoothingPaper.pdf
Steve
On Sep 18, 2020, at 9:47 AM, Tom Karzes <karzes@sonic.net<mailto:karzes@sonic.net>> wrote: As I previously explained, the vertices converge to a point (the centroid, i.e. (a+b+c)/3), but they do *not* converge to an equilateral triangle. The shape of the triangle is preserved by each step (i.e., the triangles are all similar to each other).
Each step scales the triangle by 1/2 and rotates it by 180 degrees about the centroid. It is *not* reflected.
Reversing a step is identical, except it is scaled by 2 rather than 1/2.
Performing two consecutive steps scales by 1/4 with no rotation.
The mappings of old vertices to corresponding new vertices are:
a -> (b+c)/2 b -> (a+c)/2 c -> (a+b)/2
Consider the difference between the new a and the new b:
(b+c)/2 - (a+c)/2 = (b-a)/2
In other words, the new difference is -1/2 times the old difference (a-b). The length is halved, and the vector is negated (i.e., it is rotated by 180 degrees).
This also shows that the ratios of the edge lengths are preserved. For example, consider the ratio of a pair of edge lengths:
|a-b| / |a-c|
After one iteration, the new ratio is:
|(b-a)/2| / |(c-a)/2| = |a-b| / |a-c|
Since the edge length ratios never change, clearly the triangles retain their exact shape, and do not converge to equilateral (unless they were equilateral to begin with).
You can easily see this by drawing a right triangle, and inside that triangle drawing the triangle formed by the midpoints of each edge (i.e., one iteration). The new triangle is clearly a right triangle, with the exact same shape as the original (but scaled by 1/2 and rotated by 180 degrees). So all triangles will be right triangles, and hence will not converge to an equilateral triangle.
Tom
Brad Klee writes: The triangle inequality a+b>c transforms to 2b>0, and similar for cyclic permutation. If (a,b,c) are positive lengths, even if they do not satisfy the triangle inequality, they will after one iteration. Thereafter the lengths can be folded into a triangle (or it's mirror image). Similarly, if (a,b,c) are positive angles, choose angular units where a+b+c=pi. All subsequent iterations preserve the sum, so each triple determines a unique triangle (again, up to reflection). By the limiting property, both sequences converge to equilateral.
Another possibility is:
a = (a+b+c)/3 b = [(a*b)^(1/2)+(b*c)^(1/2)+(c*d)^(1/2)]/3 c = (a*b*c)^(1/3)
Is this the best generalization of the agm to three (or more) variables? Does it even converge?
ÂBrad
On Seep 18, 2020, at 12:03 AM, Henry Baker <hbaker1@pipeline.com<mailto:hbaker1@pipeline.com>> wrote: Suppose we have a set of 3 distinct numbers, {a,b,c}.
Then averaging them in pairs preserves distinctness: {(a+b)/2,(b+c)/2,(c+a)/2}.
Proof: assume not, e.g., (a+b)/2=(b+c)/2 => a=c. Contradiction. QED.
So we can go backwards:
{a,b,c} => {a+b-c,b+c-a,c+a-b}
So, {(a+b)/2,(b+c)/2,(c+a)/2} => {(a+b+b+c-c-a)/2=b,(b+c+c+a-a-b)/2=c,(c+a+a+b-b-c)/2=a}
Note also that 'averaging' preserves the sum of the triple (hence its average): (a+b)/2+(b+c)/2+(c+a)/2=a+b+c. Thus, 'going forward' and 'going backwards' preserves this sum.
OK, so now let's iterate this averaging process N times.
I contend that this process makes the numbers more and more 'average'; i.e., all three converge towards the same number: (a+b+c)/3.
Yet, we can still recover our original 3 numbers by running the process backwards N times.
Even better, we can go backwards *further* than our original 3 numbers.
Curiously, if we start with {-1,0,1}, we get {-2^k,0,2^k}, for all k.
Note now that a,b,c need not be 'numbers'; they could be vectors of numbers, so we can play this game in higher dimensions. E.g., we can choose triples of (x,y) pairs to represent triangles, so does iterating them converge towards equilateral triangles?
This suggests the following question: For any three distinct, non-collinear points, does their exist an ellipse such that (1) the points all lie on the ellipse and (2) the distances between the points, along the ellipse, are equal? Tom Lucas, Stephen K - lucassk writes:
The triangle’s staying similar is interesting, and reminded me of something I had read years ago. Elmachtoub and Van Loan had a paper where you start with a random polygon (which is just n random points joined together in order) then did this same process of getting a new polygon as the midpoints of edges. They discovered that regardless of what you started with, you ended up with points that converged to the centroid, but were placed somewhat evenly around an ellipse with the same orientation. This untangling can be proven be rewriting the problem has multiplying a vector by a matrix and seeing convergence as for the power method for finding the dominant eigenvalue of a matrix. The fact that a triangle stays similar must be a special case of their analysis.
For those who wish to see the fun that can happen, check out http://www.cs.cornell.edu/cv/ResearchPDF/PolygonSmoothingPaper.pdf
Steve
On Sep 18, 2020, at 9:47 AM, Tom Karzes <karzes@sonic.net<mailto:karzes@sonic.net>> wrote:
As I previously explained, the vertices converge to a point (the centroid, i.e. (a+b+c)/3), but they do *not* converge to an equilateral triangle. The shape of the triangle is preserved by each step (i.e., the triangles are all similar to each other).
Each step scales the triangle by 1/2 and rotates it by 180 degrees about the centroid. It is *not* reflected.
Reversing a step is identical, except it is scaled by 2 rather than 1/2.
Performing two consecutive steps scales by 1/4 with no rotation.
The mappings of old vertices to corresponding new vertices are:
a -> (b+c)/2 b -> (a+c)/2 c -> (a+b)/2
Consider the difference between the new a and the new b:
(b+c)/2 - (a+c)/2 = (b-a)/2
In other words, the new difference is -1/2 times the old difference (a-b). The length is halved, and the vector is negated (i.e., it is rotated by 180 degrees).
This also shows that the ratios of the edge lengths are preserved. For example, consider the ratio of a pair of edge lengths:
|a-b| / |a-c|
After one iteration, the new ratio is:
|(b-a)/2| / |(c-a)/2| = |a-b| / |a-c|
Since the edge length ratios never change, clearly the triangles retain their exact shape, and do not converge to equilateral (unless they were equilateral to begin with).
You can easily see this by drawing a right triangle, and inside that triangle drawing the triangle formed by the midpoints of each edge (i.e., one iteration). The new triangle is clearly a right triangle, with the exact same shape as the original (but scaled by 1/2 and rotated by 180 degrees). So all triangles will be right triangles, and hence will not converge to an equilateral triangle.
Tom
Brad Klee writes: The triangle inequality a+b>c transforms to 2b>0, and similar for cyclic permutation. If (a,b,c) are positive lengths, even if they do not satisfy the triangle inequality, they will after one iteration. Thereafter the lengths can be folded into a triangle (or it’s mirror image). Similarly, if (a,b,c) are positive angles, choose angular units where a+b+c=pi. All subsequent iterations preserve the sum, so each triple determines a unique triangle (again, up to reflection). By the limiting property, both sequences converge to equilateral.
Another possibility is:
a = (a+b+c)/3 b = [(a*b)^(1/2)+(b*c)^(1/2)+(c*d)^(1/2)]/3 c = (a*b*c)^(1/3)
Is this the best generalization of the agm to three (or more) variables? Does it even converge?
—Brad
On Sep 18, 2020, at 12:03 AM, Henry Baker <hbaker1@pipeline.com<mailto:hbaker1@pipeline.com>> wrote:
Suppose we have a set of 3 distinct numbers, {a,b,c}.
Then averaging them in pairs preserves distinctness: {(a+b)/2,(b+c)/2,(c+a)/2}.
Proof: assume not, e.g., (a+b)/2=(b+c)/2 => a=c. Contradiction. QED.
So we can go backwards:
{a,b,c} => {a+b-c,b+c-a,c+a-b}
So, {(a+b)/2,(b+c)/2,(c+a)/2} => {(a+b+b+c-c-a)/2=b,(b+c+c+a-a-b)/2=c,(c+a+a+b-b-c)/2=a}
Note also that 'averaging' preserves the sum of the triple (hence its average): (a+b)/2+(b+c)/2+(c+a)/2=a+b+c. Thus, 'going forward' and 'going backwards' preserves this sum.
OK, so now let's iterate this averaging process N times.
I contend that this process makes the numbers more and more 'average'; i.e., all three converge towards the same number: (a+b+c)/3.
Yet, we can still recover our original 3 numbers by running the process backwards N times.
Even better, we can go backwards *further* than our original 3 numbers.
Curiously, if we start with {-1,0,1}, we get {-2^k,0,2^k}, for all k.
Note now that a,b,c need not be 'numbers'; they could be vectors of numbers, so we can play this game in higher dimensions. E.g., we can choose triples of (x,y) pairs to represent triangles, so does iterating them converge towards equilateral triangles?
On Fri 18 Sept. 2020, 08:41, Brad Klee <bradklee@gmail.com> wrote :
(...) Another possibility is: a = (a+b+c)/3 b = [(a*b)^(1/2)+(b*c)^(1/2)+(c*d)^(1/2)]/3 c = (a*b*c)^(1/3) Is this the best generalization of the agm to three (or more) variables? Does it even converge?
There was some recent discussion about generalization of AGM to more arguments, and I also found some older one on math-/stackexchange, where I recently answered a question asked more than 8 years ago: https://math.stackexchange.com/questions/442062/to-find-the-limit-of-three-t... . I think the most natural generalisation is to take as "update" for the k-th variable the k-th root of the k-th symmetric polynomial in the variables, normalized by the number of terms. For 3 that would mean a = (a+b+c)/3 b = [( a*b + b*c + c*d )/3 ]^(1/2) c = (a*b*c)^(1/3) i.e. slightly different than what you suggested for the 2nd one ("b"), In that stackexchange answer I showed that it converges. There are different proposals for other generalisations, <https://math.stackexchange.com/questions/1794795/arithmetic-geometric-mean-of-3-numbers> which do not give the same result but might be valid and maybe useful in particular situations. I find the above one the most appealing (natural / simple / straightforward) one, though. It gives AGM(1,2,3) = 1.9099262335408153... - Maximilian
The ultimate test is to see whichever definition leads to more interesting identities. The original Gauss AGM of course has many. For now I haven't seen any unexpected properties, so I don't know which is more "natural / simple / straightforward", maybe yours. Maybe neither, ha ha. It seems like your convergence proof also applies to the iteration I suggested, but I did not slow down to work out all the details. --Brad On Fri, Sep 18, 2020 at 11:19 AM M F Hasler <mhasler@dsi972.fr> wrote:
a = (a+b+c)/3 b = [( a*b + b*c + c*d )/3 ]^(1/2) c = (a*b*c)^(1/3)
I find the above one the most appealing (natural / simple / straightforward) one, though. It gives AGM(1,2,3) = 1.9099262335408153...
- Maximilian
participants (7)
-
Brad Klee -
Cris Moore -
Henry Baker -
Lucas, Stephen K - lucassk -
M F Hasler -
Mike Stay -
Tom Karzes