Constructions of Large m-Distance Sets on Triangular Lattice

Li-Ren Bao, Wei-Hsuan Yu · 2025

Read Constructions of Large m-Distance Sets on Triangular Lattice by Li-Ren Bao, Wei-Hsuan Yu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-00880.txt.

Introduction

Li-Ren Bao and one co-author, Wei-Hsuan Yu, construct large m-distance sets on triangular lattices. An m-distance set is a collection of points where distances between any two points take only m possible values. Finding large examples is a central problem in discrete geometry.

Bao and Yu use two different methods. One takes the first m smallest distances on the lattice and finds the largest cliques, fully connected groups, in the resulting graph. The other uses notions of hexagons, natural cells of the triangular lattice. They observe multiplicities of the distances, how often each distance occurs, to compare the two methods. The constructions add concrete large examples for testing bounds on distance sets.

Catalog record

CREATORLi-Ren Bao, Wei-Hsuan Yu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-00880

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Constructions of Large m-Distance Sets on Triangular Lattice Li-Ren Bao, Wei-Hsuan Yu Abstract An m m -distance set is a collection of points such that the distances between any two points have m m possible values. We use two different methods to construct large m m -distance sets on the triangular lattices. One is to use the first m smallest distances and find the largest cliques, and the other is using the notions of hexagons. Multiplicities of the distances were observed for comparison for the two methods. 1 Introduction An m -distance set is a point set where any two points have only m possible distances between them. If an m -distance set gains an m+1 -th distance when a new point is added, we will call it a maximal m -distance set. If an m -distance set has the largest number of points among all possible m -distance sets, it is called a maximum m -distance set. Note that a maximal m -distance is not always maximum, but a maximum m -distance set is always maximal. Determining the size of the maximum m -distance set in \mathbb{R}^{n} has been difficult, and we only know values for small m . Erdős and Fishburn 6 determined that the maximum sizes of planar 2,3,4 , and 5 distance sets are 5,7,9 , and 12 points, respectively. They also found all possible constructions for 2,3,4 distance sets in the paper. Then, Shinohara finished the classification of planar 3 -distance sets 9 , and then proved the maximum planar 5 -distance set is unique 10 . Finally, Wei proved that the maximum planar 6 -distance set has size 13 12 . For higher dimensions, to determine the maximum m -distance set is much more difficult. However, for 2 -distance sets, Lisoněk determined the maximum size in \mathbb{R}^{d} for d\leq 8 8 . Bannai, Sato, Shigezumi also gave a construction method for maximal m -distance sets in \mathbb{R}^{n} based on Johnson Graphs 4 . Other than Johnson Graphs, Adachi, Hayashi, Nozaki, and Yamamoto also classified some maximal m -distances set containing the Hamming Graph 1 . Here, we will discuss the construction of points located on the triangular lattices in a plane. These are points with coordinates a(1,0)+b(\frac{1}{2},\frac{\sqrt{3}}{2}) , where a,b\in\mathbb{Z} . We discuss the problem in triangular coordinates due to the following conjecture by Erdős and Fishburn 6 . Conjecture 1 . For any m\geq 3 , at least one of the maximum m -distance sets lies within triangular lattices. If m\geq 7 , then maximum m -distance sets can only be found in triangular lattices. For the cases of m\leq 6 , the above conjecture is true. There are some recent studies on the cases of triangular lattices. Most of them are based on special hexagonal figures. Balaji, Edwards, Loftin, Mcharo, Phillips, Rice, and Tsegaye gave a bound with regular polygons and especially regular hexagons in triangular lattices 3 . Ahmed and Wildstrom used some hexagons that are symmetrical with respect to vertical lines and bounded the number of distances inside them 2 . Here, we determine the maximum m - distance sets from m=7 to 34 under the assumption of using the m smallest distances in the triangular lattices. We also present an alternate method of construction by equiangular hexagons. If we use equiangular hexagons instead of regular hexagons, we can find constructions of larger size than the case found in 3 . The following values are the best lower bounds we found for sets that determine at most m distances by above two methods. The stars mean the construction method of hexagons is giving strictly larger constructions. m 7 8 9 10 11 12 13 14 15 16 17 18 19 20 size 16 19 21 24 27 27 31 34 37 37 42 45 48 * 49 m 21 22 23 24 25 26 27 28 29 30 31 32 33 34 size 55 58 61 * 63 63 69 72 75 * 75 * 79 79 85 88 91 * When designing the first method, we assume that the smallest m distances in triangular lattices will yield the maximum m -distance set. Therefore, we determine all points that have those distances with both (0,0) and (0,1) . Then we build a graph by using these distances to determine the edges, and find the maximum clique to construct the m -distance set. As these are in fact maximum when we are discussing distance sets based on the m smallest distances, we have the following conjecture Conjecture 2 . The maximum 7 -distance and 8 -distance sets have 16 and 19 points, respectively. The 7 -distance set can only be realized by taking all triangular lattices in a regular hexagon with side length 2 , and removing three all adjacent or all non-adjacent corners. The 8 -distance set can only be realized by taking all points in that regular hexagon. However, when we construct the 19 -distance set, we noticed that the smallest 19 distances cannot form a maximum size 19 -distance set. The 19 smallest distances would only yield a 19 -distance set of 45 points, while an equiangular hexagon with side length alternating 3 and 4 will form a 19 -distance set of 48 points. The main reason is that when we construct the 19 -distance set by the 19 smallest distances, the 19 th smallest distance only has multiplicity 2 . The hexagon eliminated this distance and added the 20 th smallest one which is 7 , resulting in a construction with 3 more points. This observation gives two other conjectures. Conjecture 3 . Taking all points in an equiangular hexagon with side length alternating k and k+1 , or a regular hexagon, will always give a maximum m-distance set. There are two confirmed examples for this conjecture: All triangular lattice points in a regular hexagon with side length 1 give a maximum 3 -distance set, and all triangular lattice points in an equiangular hexagon alternating side lengths 1 and 2 give the unique maximum 5 -distance set. Conjecture 4 . For any m\geq 3 , at least one construction of maximum m -distance set can be realized by repeatedly removing points from the aforementioned hexagons. This can be confirmed with a maximum 4 -distance set construction, which can be found by removing 3 corners from an equiangular hexagon with side length alternating 1 and 2 , and also with a maximum 6 -distance set, which can be obtained by deleting 6 corners from a regular hexagon with side length 2 . In the end, we found that for m=19,23,28,29,34 , the construction with equiangular hexagons has more points than the construction with the maximum clique method. The main reason is that some distances have low multiplicities if we use the m smallest distances in the maximum clique method. Substituting distances of small multiplicities out for a bigger integer yields a construction of larger size by the hexagon. This gives yet another conjecture about the multiplicities. Conjecture 5 . A maximum m -distance set will not have a distance with multiplicity less than or equal to 2 . 2 Preliminary In this paper, we use the following method

Read the complete text