5
$\begingroup$

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. The questions are at the end of the explanation.

  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 this previous question, 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 $3$D 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:

enter image description here

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

enter image description here

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$:

enter image description here

Well, 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.

I would like to ask the following questions:

  1. Are there some other known expected symmetries in four-dimensional representation of the extended Euclidean algorithm?

  2. I am using on of the two possible minimal pairs to make this visualization. Would it be better to use another type of tuples in order to see other type of symmetries? Thank you!

$\endgroup$
0
$\begingroup$

I will answer partially to my second point and keep open the question regarding the expected symmetries and the reasons of the symmetries, which still I do not understand.

The following combination of $4$-tuples provides a better insight of the symmetries regarding the gcd:

$$(a,b,gcd(a,b),sgn(gcd(a,b)) \cdot \lfloor \sqrt{\frac{a \cdot b}{|gcd(a,b)|} \rfloor})$$

where $gcd(a,b) \in \Bbb Z$ (instead of using the definition of the gcd as the absolute value, we are using the alternative definition that lets the gcd to be negative when the sign of the elements $(a,b)$ is not positive) and

$$sgn(gcd(a,b)) \cdot \lfloor \sqrt{\frac{a \cdot b}{|gcd(a,b)|} \rfloor}$$

is the floor of the square root of the least common multiple, letting it be negative (sgn is the sign function) if gcd is negative and positive if the sign of the gcd is positive. I am making the square root of the LCM because it is an approximation to the expected values of its biggest possible pair of multiples $x$ and $y$:

$$\{x,y\ /\ x \cdot y = LCM \} \land \{\not\exists\ x',y',\ x' \cdot y' = LCM , x'+y' \gt x+y \}$$

$x$ and $y$ will be located around the square root of the LCM, so it is a good approximation, and they are located inside the range of the tesseract, so they are very useful in terms of representing the relationship of $(a,b)$ and the gcd using $4$-tuples.

It leads to the following results, first an overview of the projection:

enter image description here

And zoomed:

enter image description here

So it seems better to use directly the gcd and a manipulation of the LCM to observe the symmetries of the tuples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.