# Some unfi nished ideas about dense subsets of a discrete set

(pdf copy)

We define the notion of ${\epsilon}$-dense subsets and enumerate the number ${\epsilon}$-dense subsets of the finite set ${[n]=\{1,2,\dots ,n\}}$.

1. Basic

Definition. A subset ${S}$ ${(\ne \emptyset)}$ of ${[n]}$ is said to be ${\epsilon}$-dense if ${\forall \, a\in [n]\, \exists s\in S}$ such that ${\mid s-a\mid \le \epsilon}$.

Lemma. The number of compositions of ${n}$ with not more than ${p}$ parts and no part exceeding ${\ell}$ is defined as ${f(n,p,l)}$. By Inclusion-Exclusion principle,

$\displaystyle f(n,p,l)={n+p-1\choose {p-1}}-\sum_{i=1}^{\lfloor \frac{n}{\ell +1}\rfloor} (-1)^{i+1} {p\choose i}{n-(\ell +1)i +p-1\choose {p-1}} \ \ \ \ \ (1)$

Definition. ${C(n,\epsilon)}$ is defined as the number of ${\epsilon}$-dense subsets of ${[n]}$ with least cardinality.

We observe that this least cardinality has to be ${k=\lceil \frac{n}{2\epsilon +1}\rceil}$.

$\displaystyle C(n,\epsilon)=\left \{ \begin{array}{ll} \sum_{x=0}^{2\epsilon}f(x,2,\epsilon)\cdot f(n-k-x,k-1,2\epsilon) & \text{ if }k\ge 2\\ \left. \begin{array}{ll} n & \text{ if } \epsilon \ge n-1\\ \left. \begin{array}{ll} 2\epsilon +2-n & \text{ if }2\epsilon +2-n\ge 1\\ 1 & \text{ if }2\epsilon +2-n\le 1 \end{array} \right \} \text{if }\epsilon

2. The open problem

The following matrix shows the ${C(n,\epsilon)}$ values with ${1\le n\le 15, 1\le \epsilon \le 15}$.

\bigskip

${\left( \begin{array}{ccccccccccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 1 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ 4 & 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 3 & 1 & 3 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ 1 & 9 & 2 & 4 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 \\ 8 & 8 & 1 & 3 & 5 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 \\ 4 & 6 & 16 & 2 & 4 & 6 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 \\ 1 & 3 & 15 & 1 & 3 & 5 & 7 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 \\ 13 & 1 & 13 & 25 & 2 & 4 & 6 & 8 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \\ 5 & 27 & 10 & 24 & 1 & 3 & 5 & 7 & 9 & 11 & 11 & 11 & 11 & 11 & 11 \\ 1 & 18 & 6 & 22 & 36 & 2 & 4 & 6 & 8 & 10 & 12 & 12 & 12 & 12 & 12 \\ 19 & 10 & 3 & 19 & 35 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 13 & 13 & 13 \\ 6 & 4 & 1 & 15 & 33 & 49 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 14 & 14 \\ 1 & 1 & 64 & 10 & 30 & 48 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 15 \end{array} \right)}$

Can we arrive at the values and the values of ${\epsilon}$‘s where the function maximizes?

(I will write more soon 🙂 )