# A maximal cardinality subset of n lattice points so that all points in the subset have distance at least 4

If we have some random set of $$n$$ lattice points what is the maximum cardinality of a subset in which all points have distance at least $$4$$ (or some other number). I really hope the best bound is not the trivial $$n/16$$. I'm not asking for a proof that this bound is the best possible, just provide the best bound you can.

I’ll try to provide a framework for the question. Let $$d$$ be a fixed distance $$d$$ (equal to $$4$$ in our case). A set $$A’$$ of lattice points we shall call $$d$$-separated, if any two distinct points of $$B$$ are placed at distance at least $$d$$. We are interested in a smallest $$r=r(d)$$ such that any finite set $$A$$ of lattice points has a $$d$$-separated subset $$B$$ of size at least $$|A|/r$$. I guess Empy2 obtained a bound $$r\le 15$$ by constructing a coloring of $$\Bbb Z^2$$ into $$15$$ colors such that each monochromatic subset is $$d$$-separated. Indeed, in this case as $$B$$ we can chose a largest monochromatic subset of $$A$$, which imply $$|B|\ge |A|/15$$ . Unfortunately, it can be easily shown that there is no such coloring in $$14$$ colors. (I’m going to write a proof later.) But this not imply that $$r>14$$, because a $$d$$-separated subset $$B$$ of $$A$$ may be chosen by different method. So there is sense to look for subsets $$A$$ of lattice points with the biggest ratio $$|A|/|B|$$, where $$B$$ is a maximal $$d$$-separated subset of $$A$$.

The following set has ratio $$14$$.

...
....
....
...


Are there subsets of lattice points with the bigger ratio?

From the $$n\times n$$ array, the following gives about $$n^2/15$$, or one point in every fifteen.

$$x(3,3)+y(-1,4)$$

• Do you think it's possible to achieve $n^2/14$? That was actually a bound I was hoping for to solve a problem which led me to this question. The problem says that it's always possible to choose a subset of a set of unit circles having area $S$ so that the area of a chosen subset is at least $2S/9$. If you use a well-known result saying that for a figure of area $S$ it's always possible to set a coordinate system so that the figure contains at least $S$ lattice points it quickly becomes clear that a bound of $n^2/14$ would solve the problem. – mr. clock Dec 4 '18 at 8:48