I can imagine that 3D is easier, since we only have to solve for *one* rotation. In 4D, there are 2 independent rotations. Perhaps the 4D answer is related to the fact that there are *two* gcd algorithms: a 'left' gcd and a 'right' gcd. So perhaps you have to find both gcd's for the final result? At 10:48 AM 10/22/2020, Fred Lunnon wrote:

Hurwitz quaternions work in 3-space --- see for example my write-up for when this algorithm last appeared on math-fun, https://arxiv.org/abs/1202.3198

I never needed to consider 4-space, since nobody has managed to discover a Heronian pentatope!

WFL

On 10/22/20, Henry Baker <hbaker1@pipeline.com> wrote:

...

Hurwitz quaternions might work for 4D.

At 09:32 AM 10/22/2020, Tom Karzes wrote:

...

Good job! That's the solution I found when I first came up with this problem:

First translate so that one of the points is at the origin. Then divide all the points by the GCD.

That's all there is to it. It doesn't matter which point ends up at the origin, as long as one of them does. The GCD will be the same no matter which one you choose. You can think of the translated set of points as displacement vectors (relative to the point at the origin).

Treating the points as Gaussian integers is a key insight. So is translating one of them to the origin, and of course dividing by their GCD. I went out of my way not to mention Gaussian integers in the problem description, just to make the solution a little less obvious. I also made sure my example didn't have any of the points at the origin, again to make it less obvious.

The minimal solution is unique up to multiplication by a unit (1, i, -1, -i).

Once you have a minimal solution, multiplication by any nonzero Gaussian integer will give you a new scaled/rotated set of integer points with the same shape. If you don't want to rotate, you can just multiply by a positive integer. And of course, you can reflect by taking the complex conjugate.

To compute the Gaussian GCD, the standard Euclidean Algorithm works perfectly well. It just needs to operate on Gaussian integers.

I actually used this for some raster graphics I was doing, where I had sets of points that I wanted to scale up or down without introducing any distortion. This solved the problem nicely.

Any idea how to scale this up to 3 (or more) dimensions? The Gaussian integer approach works great for 2D, but obviously not for higher dimensions. Is there a way to represent higher- dimensional points as, say, orthogonal matrices, or polynomials, or something along those lines, then obtain some sort of GCD and somehow factor it out? I guess part of the difficulty is that rotations don't commute in 3 or more dimensions.

Still, the basic problem is perfectly well-defined for higher dimensions, so some solution must be possible.

Tom

Allan Wechsler writes:

...

Yes. Then take the GCD of all the remaining points (considered as Gaussian integers), and divide out by the GCD to obtain the solution.

On Thu, Oct 22, 2020 at 1:19 AM Steve Witham <sw@tiac.net> wrote:

...

Not only does reflection not matter to the problem, but translate the problem so that one original point is (0, 0) and let the same point in the solution be (0, 0).

Without loss of generality, --Steve

...

From: Henry Baker <hbaker1@pipeline.com> Date: 10/21/20, 10:27 AM To:

I'm guessing factorization of Gaussian integers is involved...

At 12:51 AM 10/21/2020, Tom Karzes wrote: > Here's a puzzle some of you might like: