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

Solution 1:

(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.