**Nearest neighbours**

What does this sequence represent? `(2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 16, 16, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 20, 20, 20, 20, 20, 20, 21, 21, 21, 22, 22, 22, 22, 22, 22, 23, ...)`

We discussed the problem of *nearest neighbours* in **problem 114** on this website. Another version with Mathematica programs can be studied in → GitHub. A discussion dealing with the first steps of this problem appeared in → reddit.

The **integer sequence** resulting from the problem of *nearest neighbours* was published in **OEIS** on 1^{st} November 2021 as **A347941**. The "inverse" sequence was identified as **A261953**.

The problem is not comprehensively solved. It deserves attention because it can be stated quite simply and seems to offer several promising ways for further investigation. We shall here present a short summary of the problem and its (as yet incomplete) solution:

Consider a set `G` of `n` points in the real plane with pairwise different distances. A point `A` `∈` `G` is called a nearest neighbour if there exists a point `B` `∈` `G` with smaller distance to `A` than to any other point in `G`.

**For any given **`n` we want to find the lowest possible number `b(n)` of nearest neighbours. What is already known as a (partial) solution?

- For
`n` `≤` `9` the problem is solved: `b(n)` `=` `2` .

- For
`n` `=` `10,` `11,` `12` we have `b(n)` `≤` `3` .

- For
`n` `≥` `13` we have `b(n)` `≤` `2j` for `n` `=` `9j-5` `...` `9j` and `b(n)` `≤` `2j+1` for `n` `=` `9j+1` `...` `9j+3, j` `≥` `1` .

Thereby we get a sequence `a(n)` as the best known upper bound for `b(n)` :
`a(2)` `=` `a(3)` `=` `2` .

`a(n)` `=` `2j` for `n` `=` `9j-5` `...` `9j, j` `≥` `1` .

`a(n)` `=` `2j+1` for `n` `=` `9j+1` `...` `9j+3, j` `≥` `1` .

This is the sequence A347941 in OEIS. A list of the entries can be seen at the top of this article. We illustrate `a(n)` in figures 1 and 2.

**Figure 1** Green: *Nearest neighbours*.

Left: For `n` `=` `9` (or less) points we can find an arrangement with `2` nearest neighbours (which of course is optimal).

Right: For `n` `=` `12` (or `n` `=` `10,` `11`) points we can find an arrangement with `3` nearest neighbours. Does an arrangement exist for these `n` with `2` nearest neighbours? We suppose: No.

**Figure 2** Green: *Nearest neighbours*. – For `n` `=` `57` points we can find an arrangement with `13` nearest neighbours. Does an arrangement exist for this `n` with less than `13` nearest neighbours? We suppose: No. This is supported by the (much tested) conjecture that combinations of several "islands" of points with `2` nearest neighbours and at most one "island" with `3` nearest neighbours give an optimal result – the islands being built as in figure 1 and arranged as in figure 2.

Figures 1 and 2 show `a(9)` `=` `2, a(12)` `=` `3` and `a(57)` `=` `13` . The formula for the complete sequence was given above.

We can invert the problem and get a sequence `c(m)` in the following way:

For `m` nearest neighbours `d(m)` is defined as the largest possible number of points in `G` . For `m` `≥` `2` we obtain from `a(n)` the sequence `c(m)` `=` `(9,` `12,` `18,` `21,` `27,` `30,` `...)` as best known lower bounds for `d(m); c(m)` is listed in OEIS as A261953 für `m` `≥` `2` . – `c(5)` `=` `21` asserts that a `G` with `21` points and `5` nearest neighbours exists but no `G` with more than `21` points and `5` nearest neighbours is as yet known (we suppose that such a `G` does not exist).

Which **progress** with the problem of *nearest neighbours* seems feasible? Any comments are welcome.
- One gives a positive partial solution:
`b(n)` `=` `a(n)` for some `n` `>` `9`.

- One gives a negative partial solution: One or several conjectures made above are wrong – e.g. a
`G` is presented with `19` points and `4` nearest neighbours. In this case a revision of `a(n)` would be necessary.

What would be a **complete solution** of the problem of nearest neighbours? Any comments are welcome.
- One gives a proof for
`a(9)` `=` `2` and `a(12)` `=` `3` being optimal; and for all bigger `n` the "islands-method" from figure 2 is proved to be optimal. Then `b(n)` `=` `a(n)` is proved.

- One establishes
`b(n)` ( `≠` `a(n)`) with a comprehensive and proven formula.

Last update 2021-11-02

blog overview | previous article | next article

Manfred Börgens | main page