Monday, February 6, 2017

Visualizing the possible symmetries of tuples $(a,b,x,y)$ of the extended Euclidean algorithm in a four-dimensional tesseract.

I am trying to visualize the possible symmetries in the Euclidean four-dimensional space of the $4$-tuples of points $(a,b,x,y)$ generated by the extended Euclidean algorithm, where $ax+by=gcd(a,b)$. There is more than one solution of $(x,y)$ pairs, so I am focusing on visualizing one of the two minimal pairs generated by the algorithm, as it is explained in the Wiki page of the Bézout's identity. This is a mirror of my question at MSE.

1. In the example below, basically what I am doing is generating a single $4$-tuple $(a,b,x,y)$, where $(x,y)$ is one of the two possible minimal pairs that the extended Euclidean algorithm generates for every possible combination of integer pairs $(a,b)$ where in this case $a,b \in [0,50]$.

2. For this reason, $50 \cdot 50=2500$ $4$-tuples are generated. Then the rest of combinations of positive and negative values of $a$ and $b$ were also included $(-a,b)$$(a,-b)$$(-a,-b)$ and the rest of $4$-tuples are calculated in the same way, obtaining the associated $(x,y)$ values as before.

3. Finally $4 \cdot 2500 = 10^4$ $4$-tuples have been generated. This set of $10^4$ four-dimensional tuples then is visualized inside a tesseract, following the methodology of my previous post, having the reference axes at $(0,0,0,0)$, the center of the tesseract, and representing them as points of the Euclidean four-dimensional space.

4. The result is shown as a $3D$ projection of the tesseract (a Schlegel diagram). So basically we are able to view the four-dimensional set of $4$-tuples $(a,b,x,y)$ representing each possible combination of $(a,b)$ as the first two dimensions, and their associated pair $(x,y)$, one of the minimal pairs generated by the Euclidean algorithm, as the last two dimensions. In other words, one single four-dimensional point $(a,b,x,y)$ represents a given pair $(a,b)$ and one of its minimal results of the extended Euclidean algorithm, $(x,y)$ .

5. So here are the results:



This is a zoom showing only the $4$-tuples associated with the **positive** combinations of $a$ and $b$:


And finally, this is the same zoom showing the whole set of results, for any combination of positive and negative values of $a$ and $b$:


Well, in this constellation of points, apart from being kind of "mesmerizing", it is possible to distinguish some basic already known symmetries, due to the inclusion of the tuples $(a,b,x_0,y_0)$ , $(-a,b,x_1,y_1)$ , $(a,-b,x_2,y_2)$ and $(-a,-b,x_3,y_3)$. But, in other hand, as we are visualizing a rotating set of four-dimensional points, it seems that other possible symmetries are there.

In general the methodology of projecting $4D$ into $3D$ is quite interesting: it is one of the closest ways to visualize the four-dimensional problem directly. Sometimes it is not easy to find symmetries when the problem is represented in lower dimensions, so seeing directly the $4$-dimensional system can provide new insights about the set of points being studied.

No comments:

Post a Comment