I would think that for big enough N = a^2 + b^2, the moderately obvious "Pythagorean" solution would *not* be optimal, and that you could do better with big patches of points arranged in a triangular lattice. On Fri, Sep 11, 2020 at 3:54 PM Dan Asimov <dasimov@earthlink.net> wrote:

I think that for an approximate incremental algorithm, probably Steve's idea is optimal (in some precise sense).

(Years ago, I used something like that to get geodesic segments S(L) of length L on the n-torus T^n = R^n/Z^n that were intended to minimize the radius of the largest open ball B(r), r=r(L), in the complement T^n - S(L).)

For the exact question, I think that for N = a^2 + b^2 points in T^2, where gcd(a,b) = 1, you can tile T^2 by N squares (usually tilted). Then the vertices of the tiling (or equally the centers of the tiles) form an optimal arrangement. Giving the max-min distance as sqrt(1/N). (I think this is closely related to finite factor rings of the Gaussian integers.)

Checking N = 5, N = 10, N = 13, this looks an awful lot like exactly what Steve got for numbers of the form N = a^2 + b^2, gcd(a,b) = 1.

I'm not sure about exact solutions on T^3. But another method for approximating the exact answer is to consider the function

M : (T^3)^N —> R

on arrangements of N points on T^3 (or any-dimensional torus), that gives the max-min distance, and try to climb the gradient. One problem is that this function isn't always differentiable. Another is that, a priori, there might be local maxes that aren't global maxes, though I don't know if this can occur.

—Dan

Steve Witham wrote: ----- You can get a pretty nice packing on a square torus using the golden ratio. For the unit square, pick one of these spacings (Yes, they are > 1.) h = floor(N phi) / N or h = ceil(N phi) / N,

put the points at (k h (mod 1), k / N) for k = 1 to N,

and pick the better of the two packings. They are uniform, which makes it < O(N) to measure the closest spacing.

...

But what would seem to be the best arrangements for 1 <= N <= 10 on T^2 and T^3 ???

Here are my numbers. The sequence is not monotonic, which means you can sometimes do better by using the next spacing and leaving out a point!

Using the best of `floor()` or `ceil()` (on a unit square): N min distance 2 0.7071067811865476 3 0.4714045207910316 4 0.5 5 0.44721359549995765 6 0.3726779962499649 7 0.3194382824999699 8 0.3535533905932738 9 0.3333333333333333 10 0.3162277660168369 11 0.2874797872880344 12 0.25 13 0.27735009811261385 14 0.22587697572631218

I don't know an analogous method for the cube torus.

But you *could* "pack" points on a unit interval: k phi (mod 1) for k = 1 to N.

...Why would you want to do that!? you ask. Because you can keep adding points to the interval incrementally, and the neighbor distances (mod 1) are always within some constant factor of 1/N.

I have searched but not found a similarly simple way to add points incrementally to the square torus that gets remotely good packing. (I call this the peppering problem.)

--Steve

...

From: Dan Asimov <dasimov@earthlink.net> Date: 9/10/20, 6:26 PM

The Tammes problem is the well-known problem to find the arrangement of N points on the unit sphere S^2 that maximizes the minimum distance between any pair of them.

What about the same question for N points on the square torus

T^2 = R^2/Z^2

or the cubical torus

T^3 = R^3/Z^3

???

---

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun