# How should I restrict the points considered in each hexagonal lattice to correctly count all unique near-coincident lattices?

## Background:

If a hexagonal lattice is defined by integers $$i, j$$ where $$x = a_1 \left(i + \frac{1}{2} j\right)$$ and $$y = a_1 \frac{\sqrt{3}}{2} j$$, the distance to the origin for each point $$r(a_1, i, j)$$ will be $$a_1 \sqrt{i^2 + j^2 + ij}$$. See this answer to my earlier question.

If I have a second hexagonal lattice with constant $$a_2$$ it will form a coincident if there's some supercell of one that matches a supercell of the other, and since both are periodic it's sufficient to show that these lengths are equal:

$$a_1^2 (i^2 + j^2 + ij) = a_2^2(k^2 + l^2 + kl)$$

The example in the plot below is for $$(i, j), (k, l) = (5, 4), (2, 3)$$ and $$a_1=1$$, which makes $$a_2 = \sqrt{\frac{61}{19}}$$

To visualize the coincidence it's necessary to rotate the second lattice by

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

We can know by symmetry that the negative of this angle or +10.26° will generate a second coincident lattice, and in fact every $$\theta$$ such that $$\mod(\theta, \ 30°) \ne 0$$ will have a complementary lattice at $$-\theta$$. At integer multiples of 30 degrees the pair will be degenerate and we'll count it as only a single coincident lattice.

## Question:

I am writing an algorithm to find near-coincident lattices, where the lengths differ by some small fraction $$\delta$$, perhaps 1 percent:

$$\left|\frac{a_1^2 (i^2 + j^2 + ij) }{ a_2^2(k^2 + l^2 + kl)} - 1\right| <= \delta$$

I want to count the number of unique near-coincident configurations. The algorithm will be used in a python script.

My problem is that I don't want to miss any near-coincidences and at the same time don't want to double-count.

Question: How should I restrict the points considered in each hexagonal lattice to correctly count all unique near-coincident lattices?

I know I should restrict my search to a pie-shaped segment of all points in each of the two lattices, perhaps a 30° slice of one against a 60° slice of the other, but I haven't been able to convince myself that this guess is mathematically sound.

Example of a proper coincident lattice: $$(i, j), (k, l) = (5, 4), (2, 3)$$ with $$\frac{a_2}{a_1} = \sqrt{\frac{61}{19}}$$

• Help with proper tagging is appreciated! – uhoh May 11 '20 at 12:36
• I suspect I have unfortunate and ironic news for you. – Dan Uznanski May 11 '20 at 13:12
• Yep. Writing it up now. – Dan Uznanski May 11 '20 at 15:03
• @DanUznanski I'm holding my breath, I hope it's not too unfortunate or ironic... – uhoh May 11 '20 at 15:21

As long as the $$a_1/a_2$$ ratio is the square root of of a ratio of Loeschian numbers (A003136), then I have bad news: every single pair is coincident! We can do this by simply selecting $$i,j$$ to give $$i^2+ij+j^2 = a_2^2$$ and $$k,\ell$$ to give $$k^2+k\ell+\ell^2 = a_1^2$$.

Even worse: since the Loeschian numbers include all the squares, and thus the square root of ratios includes all rational numbers, which are dense among the reals, every single positive real number provides a near-coincident pair of lattices!

Here's a series of increasingly good lattices for $$a_1/a_2 = \pi$$.

1 (1, 0), 7 (2, 1) 0.40994348586990825
1 (1, 0), 9 (3, 0) 0.09662271123215094
3 (1, 1), 28 (4, 2) 0.057457614402431245
3 (1, 1), 31 (5, 1) 0.04487699344296536
4 (2, 0), 39 (5, 2) 0.012267118060447002
13 (3, 1), 127 (7, 6) 0.010274466253241465
13 (3, 1), 129 (8, 5) 0.005388703766188607
21 (4, 1), 208 (12, 4) 0.0035495556592474165
25 (5, 0), 247 (11, 7) 0.0010521861245589292
49 (5, 3), 484 (22, 0) 0.0008045131128543437
52 (6, 2), 513 (21, 3) 0.0004277365626641494
67 (7, 2), 661 (20, 9) 0.00039863067017686937
84 (8, 2), 829 (20, 13) 5.641699819802781e-05


Here I illustrate $$\pi \approx \sqrt{\frac{247}{25}}$$. The error is just over one part in 1000, which means that if I'd actually drawn the magenta point as two separate points, you wouldn't be able to tell at this scale.