3
$\begingroup$

I was playing with the exterior algebra, and stumbled on this interesting function from $\Bbb N^2 \to \Bbb N$, which I'll call $f(x,y)$. This is plotted from $1 \leq x,y \leq 100$:

2D function

In this picture, yellow values are higher, blue values are lower. So you can see the function is at its lowest when $x:y$ is closest to a simple ratio.

For all $x$, we have $f(x,x) = 2$. However, for sufficiently large $x$, we also have $f(x,x+1) = 3$, $f(x,x+2)=4$, etc, so this function is also in some sense measuring the distance to the nearest low-slope line.

In comparison, here's the gcd(x,y) function:

gcd

So you can see that while both functions feature prominent rational slopes, that the first one seems to be "smoothed" relative to the GCD, and also reaches minima at rational slopes rather than maxima.

Is there some simple function that this resembles?

Here is a CSV, if anyone wants to play with it, but due to the way I calculated this function, there may be some sporadic errors (though should be good for $x,y < 50$ or so: https://pastebin.com/raw/vEWAdBVM


Just to say how I got this function:

So for each $x,y$ pair, I generated the vector $(x,y,1)$. Then, I wanted to find the "shortest" integer bivector that is the wedge product of $(x,y,1) \wedge v$ for some $v$ with integer coordinates. This is a plot of the norm of the resulting shortest bivector for each $(x,y)$.

I was using the $\ell_1$ norm to measure shortest for the thing I'm doing, but you get the same basic plot with the $\ell_2$ norm, as well as any $\ell_p$ norm.

For each $(x,y)$ pair above, I ran a Monte Carlo search testing 10000 randomly generated bivectors and took the best one; after a few tries everything converged to the plot above.

If you start with $(x,y,0)$ instead, you seem to get the basic GCD function instead, but $(x,y,1)$ gives the "smooth nega-GCD" pattern above.

I was surprised to find something so simple and beautiful from such a strange starting point!

$\endgroup$
  • $\begingroup$ It's also worth pointing out that $f(n,n^2-n)=n$ and $f(n,k)=n+1$ for all $k>n^2-n$. $\endgroup$ – Bartek May 18 at 2:59
  • 1
    $\begingroup$ Can you give an example of how to calculate a bivector/wedge product, for people like me for whom it's not clear? $\endgroup$ – Greg Martin May 18 at 4:46
  • $\begingroup$ @GregMartin the wedge product is basically an antisymmetric tensor product - there are all kinds of abstract characterizations of the exterior algebra, but probably the simplest is just to treat the wedge product of two vectors $a \wedge b$ as $a\otimes b - b \otimes a$. You can also treat it as the algebra given by the relation $a \wedge b = -b \wedge a$, which (if you use this identity on the basis elements and extend via linearity) is equivalent and also lets you get trivectors and general multivectors. More info here: en.wikipedia.org/wiki/Exterior_algebra $\endgroup$ – Mike Battaglia May 18 at 4:58
  • 2
    $\begingroup$ @GregMartin: It should be fine to replace "wedge product" by "cross product" here, as I'm fairly sure the OP is identifying $\wedge^2 V$ with $V$ via the Hodge star (or endowing $\wedge^2 V$ with a norm that would correspond to the usual norm on $V$ under this identification). So the OP is looking at the norm of the shortest nonzero vector in the $\mathbb{Z}$-lattice in $\mathbb{Z}^3$ generated by $\left(0,1,-y\right)$, $\left(-1,0,x\right)$ and $\left(y,-x,0\right)$. For comparison, the norm of the shortest nonzero vector in the $\mathbb{Z}$-lattice in $\mathbb{Z}^2$ generated ... $\endgroup$ – darij grinberg May 18 at 17:03
  • $\begingroup$ ... by $\left(0,y\right)$ and $\left(x,0\right)$ is $\gcd\left(x,y\right)$, by Bezout's theorem. $\endgroup$ – darij grinberg May 18 at 17:04
3
$\begingroup$

Hmm, it's not an exact match, but it reminds me a lot of this graph of the number of iterations required for Euclid's GCD algorithm.

$\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.