# determining if a coincident point in a pair of rotated hexagonal lattices is closest to the origin?

A pair of hexagonal lattices with one scaled by the square root of a rational number $$r = \sqrt{\frac{m}{n}}$$ and then rotated will produce a variety of different hexagonal lattices of coincident points.

For the first lattice let

$$x, y = i+\frac{1}{2}j, \ \frac{\sqrt{3}}{2}j$$

and for the second

$$x, y = r\left(k+\frac{1}{2}l\right), \ r\left(\frac{\sqrt{3}}{2}l\right).$$

Per this and this helpful answer the squares of the distances to unit lattice points are given by Loeschian numbers (A003136) equal to $$i^2+ij+j^2$$ so in this case a point $$i, j$$ on the first lattice will coincide with a point $$k, l$$ on the second lattice once rotated by some amount if

$$n(i^2+ij+j^2) = m(k^2+kl+l^2).$$

For example if $$m, n = 13, 7$$ then both $$(i, j) = (5, 6)$$ and $$(6, 5)$$ will coincide with $$(k, l) = (5, 3)$$ at rotation angles of about 5.2 and 11.2 degrees as given by.

$$\theta = \arctan\left( \frac{\frac{\sqrt{3}}{2}l}{k+\frac{1}{2}l} \right) - \arctan\left( \frac{\frac{\sqrt{3}}{2}j}{i+\frac{1}{2}j} \right)$$

However, while the first solution is part of the hexagonal superlattice built on the much closer point $$(i, j), (k, l) = (1, 3), (1, 2)$$ the second point represents the shortest possible coincident distance and therefore a far lower density coincident lattice.

Question: Is there a simple test that can be applied to the pairs (5, 6), (3, 5) and (6, 5), (3, 5) (and knowing m, n) that will indicate immediately that one is based on a superlattice of much smaller period but the other represents the shortest distance in a much more sparse coincident lattice?

This answer and this comment below it provide some related tests and might adapted here, but ideally I'm looking for a yes/no test that does not involving testing all points closer.

plotting script: https://pastebin.com/pZFCGXbE

• I feel like there must be a more geometric answer to this question rather than just using an algorithm. – Tom Sep 19 '20 at 19:43
• @Tom the accepted answer provides exactly what I need. While I wouldn't say "just an algorithm" I do agree that it seems there should be something more "geometric" out there, and I think it will deserve a separate question. Please feel free to ping me if you need a new question asked. – uhoh Sep 20 '20 at 14:41
• No if that's what you were looking for then that's fine, it's just you mentioned another article with Clifford algebras on a very similar topic so I was wondering if there was something like that, but if this answer solves your problem then the problem is solved. – Tom Sep 20 '20 at 17:10
• @Tom per comments below the answer here I've now split this aspect off separately: Geometric way to check if a coincident point in a pair of rotated hexagonal lattices is closest to the origin? – uhoh Sep 24 '20 at 7:01

(I will use $$p,q$$ insteaf of your $$i,j$$, because I will use $$i$$ for the imaginary unit.)
Set $$u := \frac{1+\sqrt{3} i}{2}$$. Consider the set $$\{a+bu\mid a,b\in\mathbb{Z}\}$$. Since $$u^2=u-1$$, a product of two such numbers belongs to this set as well. I will denote this set $$\mathbb{Z}[u]$$.[1]

If your first lattice is put on the complex plane, its points will correspond exactly to elements of $$\mathbb{Z}[u]$$. And since scaling and rotating around the origin correspond to multiplication by a complex number, the points of your second lattice will correspond to numbers of the form $$Az_1$$, where $$A\in \mathbb{Z}[u]$$ and $$z_1\in\mathbb{C}$$ is the number where the point 1 ended up after the rotation and scaling.

In your case, $$z_1$$ is given by $$P=Kz_1$$, where $$P=p+qu$$ and $$K=k+lu$$ are elements of $$\mathbb{Z}[u]$$. The coincident points correspond to numbers $$P'\in \mathbb{Z}[u]$$ which can be represented as $$P' = K'z_1$$, where $$K'\in \mathbb{Z}[u]$$. You want to know whether there are such $$P'$$ with $$0<|P'|<|P|$$.

Assume that there are and that $$P_1 = K_1z_1$$ a coincident point with the minimal non-zero absolute value (i.e., closest to the origin). Since the coincident points form a hexagonal lattice, $$P$$ can be represented as $$P=AP_1$$, where $$A\in\mathbb{Z}[u]$$. Then $$Kz_1 = AK_1z_1$$, i.e., $$K = AK_1$$.

So if there is a coincident point closer to the origin than $$P$$, then there are elements $$A, P_1, K_1\in \mathbb{Z}[u]$$ such that $$AP_1 = P$$, $$AK_1 = K$$, and $$|A|>1$$. The converse is also true: if such $$A, P_1, K_1\in \mathbb{Z}[u]$$ exist, then $$P_1 = K_1z_1$$ is a coincident point, and since $$|P_1| = \frac{|P|}{|A|}<|P|$$, it is closer to the origin than $$P$$.

Therefore, the thing you want to know is equivalent to the following: given the elements $$P=p+qu$$ and $$K=k+lu$$ of $$\mathbb{Z}[u]$$, do they have a common divisor in $$\mathbb{Z}[u]$$ whose absolute value is greater than 1? This can be decided using Euclid's algorithm:

• Set variables $$A:= p+qu$$ and $$B:=k+lu$$; if $$|A|<|B|$$, switch $$A$$ and $$B$$ in places.
• While $$B\neq 0$$, repeat: Calculate $$\frac AB$$ [2] and "round" it to the nearest element of $$\mathbb{Z}[u]$$,[3] let's denote it $$D$$. Set $$B$$ to $$A-DB$$ and $$A$$ to the old value of $$B$$.(end of loop)
• If $$|A|=1$$ (i.e., if $$A$$ is one of the numbers $$\pm 1, \pm u, \pm(u-1)$$), then the numbers $$p+qu$$ and $$k+lu$$ have no common divisors in $$\mathbb{Z}[u]$$ other than $$\pm 1, \pm u, \pm(u-1)$$; in the terms of your problem, it means that the corresponding coincident point is closest to the origin. Otherwise, there are closer points.

For example, if we start with values $$A = 6+5u$$ and $$B = 5+3u$$, then $$\frac{A}{B} = \frac{9+u}{7}$$; the closest element of $$\mathbb{Z}[u]$$ is $$1$$, so the values of $$A$$ and $$B$$ change to $$5+3u$$ and $$6+5u - 1(5+3u) = 1+2u$$. Now, $$\frac{5+3u}{1+2u} = 3-u$$, which lies in $$\mathbb{Z}[u]$$, so the values of $$A$$ and $$B$$ change to $$1+2u$$ and $$0$$. Since $$|1+2u|>1$$, we see that there must be a coincident point closer to the origin. And if you apply the algorithm to the starting values $$5+6u$$ and $$5+3u$$, you will find that there are no closer coincident points in that case. (I think that the inscriptions on your pictures are wrong: the first one corresponds to $$(6,5)\leftrightarrow (5,3)$$, and the second one to $$(5,6)\leftrightarrow (5,3)$$.)

[1] Actually, $$\mathbb{Z}[u]$$ means the set of all numbers of the form $$a_0+a_1u+\dots+a_ku^k$$, where $$k\in\mathbb{Z}_{\geq 0}$$ and $$a_0,\dots,a_k\in \mathbb{Z}$$; but since $$u^2=u-1$$, this is the set I described.

[2] Note that for $$x,y,z,t\in\mathbb{R}$$, $$\frac{x+yu}{z+tu} = \frac{(x+yu)(z+t-tu)}{z^2+zt+t^2} = \frac{x(z+t)+ (y(z+t)-xt)u - ytu^2}{z^2+zt+t^2}= \frac{(x(z+t)+yt) + (yz-xt)u}{z^2+zt+t^2}$$.

[3] Nearest in the sense that the absolute value of their difference is smallest. If $$x,y\in\mathbb{R}$$, then the element of $$\mathbb{Z}[u]$$ nearest to $$x+yu$$ is one of $$\lfloor x\rfloor + \lfloor y\rfloor u$$, $$\lfloor x\rfloor + \lceil y\rceil u$$, $$\lceil x\rceil + \lfloor y\rfloor u$$, $$\lceil x\rceil + \lceil y\rceil u$$, so you need to check only these four numbers.

• @uhoh It's a property of absolute value of complex numbers: for $a,b\in \mathbb{C}$, $|ab| = |a||b|$. Since $AP_1 = P$, $|A||P_1| = |P|$. – Litho Sep 17 '20 at 18:47
• for your "rounding" inside Euclid; is that an instance of something that's done often in this kind of analysis, or is it somewhat special and/or unusual? – uhoh Sep 17 '20 at 19:21
• @uhoh The thing which allows Euclid's algorithm to work is that $\mathbb{Z}[u]$ is a Euclidean domain. I.e., for any $A,B\in \mathbb{Z}[u]$, if $B\neq 0$, then there are $D,R\in\mathbb{Z}[u]$ such that $A=BD+R$ and $|R|^2<|B|^2$. Since $\mathbb{Z}[u]$ is embedded into $\mathbb{C}$, where you can divide by non-zero elements, $|R|=|A-BD|=|B||A/B-D|$, so it follows from the fact that for any $z:=A/B\in\mathbb{C}$, there is $D\in\mathbb{Z}[u]$ such that $|z-D|<1$. I don't know how common these things are, I'm not really familiar with this area. – Litho Sep 18 '20 at 8:01
• @uhoh By the way, $D$ doesn't really have to be the closest to $A/B$, it's good as long as $|A/B-D|<1$. – Litho Sep 18 '20 at 8:05
• This is lovely, thank you very much! Every line you've written is helpful. I apply the tests on $|B|$ and $|A|$ to their integers so there's no floating point problems. Now I can go in step by step and watch in detail what happens. – uhoh Sep 20 '20 at 14:37