5
$\begingroup$

Let $G_n$ be a $n\times n\times n$ lattice, so $G_n=$Join@@Join@@Array[{##}&,{10,10,10}].

Given a set of lattice points $U$, we say it 'covers' another set $V$ if for each $v\in V$, some $u\in U$ shares two of its coordinates with $v$, i.e. $\frac{u-v}{\lVert u-v\rVert}\in\{(0,0,1),(0,1,0),(1,0,0)\}$, i.e. they are on a common gridline.

So, for instance, $G_n$ is covered by one of it's slices, as depicted below. You can cover $G_4$ with a set of fewer points: consider $S=${{2,3,0},{1,0,3},{2,1,1},{3,2,3},{3,0,2},{1,2,2},{0,3,1},{0,1,0}}. There are 8 points, and they cover $G_4$ like so:

The goal is to compute $\Xi(n)=\min_{S\subseteq G_n\text{ and }S\text{ covers }G_n}|S|$, or the smallest number of points needed to cover $G_n$.

This code randomly chooses new points until $G_n$ is covered

NestWhile[{Append[#, #3], 
DeleteCases[#2,Alternatives @@ Table[ReplacePart[#3, i -> _], {i, 3}]]} & @@ 
Append[#, RandomChoice@#[[2]]] &, {{}, 
Flatten[Outer[List, #, #, #] &@Range[0, n-1], 2]},Length@#[[2]] > 0 &][[1]]

My above slice comment yields a trivial upper bound $\Xi(n)\leq n^2$. A lower bound is obtained by noting that each point in a set covering $G_n$ covers at most $3n-2$ points, hence $\lceil n^3/(3n-2)\rceil\leq\Xi(n)$.

In the case of 4, $7\leq\Xi(n)\leq8$ by my exhibited upper bound. I want to compute or improve bounds for $\Xi(10)$, as well as every value $\Xi(n<10)$. I also want to get better asymptotic bounds, and perhaps even conjecture a closed form if FindSequenceFunction has enough to work with.

This is the same as How can I quickly find the coordinates of key points?, except that I specifically want asymptotic bounds and closed forms. Therefore I'm expecting three kinds of answers

(1) ways of searching covering sets for finding small upper bounds

(2) ways of reducing search space for finding larger lower bounds

(3) particular covering sets for arbitrary $G_n$, like the trivial Join@@Array[{##,0}&,{n,n}].

Using other languages like Ben Izd's previous answer is valid, but I'm going to verify and visualize everything in Mathematica.

Improve this question
$\endgroup$
2
  • $\begingroup$ So, for instance, how can we easily prove that $\Xi(4)=8$? $\endgroup$
    – Adam
    Commented Sep 11, 2022 at 7:43
  • 1
    $\begingroup$ To prove $\Xi(4) \geq 8$ distinguish two cases. Case 1: Every $x$-slice (here $x$ is the first coordinate) contains at least two points of $S$. Case 2: There exists an $x$-slice containing less than $2$ points of $S$. Case 1 implies $|S| \geq 4\cdot 2 = 8$ because there are four $x$-slices. Case 2 implies that in the $x$-slice with less than $2$ points of $S$, at least $9$ points in that slice are not covered by points in that slice, and must be covered by $\geq 9$ points of $S$ that are not in the slice, therefore $|S| \geq 9$. $\endgroup$
    – user293787
    Commented Sep 11, 2022 at 9:25

2 Answers 2

Reset to default
3
$\begingroup$

Regarding visualization you can do something like this:

n = 4;
p = {{2, 3, 0}, {1, 0, 3}, {2, 1, 1}, {3, 2, 3}, {3, 0, 2}, {1, 2, 
     2}, {0, 3, 1}, {0, 1, 0}} + 1;
grid = Tuples[Range[n], {3}];
fp = Pick[
   grid, (d |-> (MemberQ[Count[d - #, 0] & /@ p, 2 | 3])) /@ grid, 
   False];
Graphics3D[{{Black, Sphere[#, 1/10] & /@ grid}, {Opacity[0.5], Green, 
   Sphere[#, 1/5] & /@ p}, {Opacity[0.5], Red, 
   Sphere[#, 1/5] & /@ fp}, 
  Line /@ ({{{#1, #2, 1}, {#1, #2, n}}, {{#1, 1, #3}, {#1, 
         n, #3}}, {{1, #2, #3}, {n, #2, #3}}} & @@@ p)}, 
 BoxStyle -> Dashed, SphericalRegion -> True]
Clear[n, grid, p, fp]

Green dots are covering set and red dots are points that were not covered. In the first image we have 8 green dots and all points were covered, in the second one we have 7 green dots and 7 red dots that were not covered. Also take care that I use range of point's coordinates 1;;n instead of OP's 0;;n-1.

enter image description here enter image description here

Improve this answer
$\endgroup$
1
2
$\begingroup$

An upper bound is $\Xi(n) \leq \lceil n^2/2 \rceil$ and one can construct examples of this size using

aux[k_]:=Select[Tuples[Range[0,k-1],3],(Mod[Total[#],k]==0)&];
S[n_]:=With[{k=Floor[n/2]},Join[aux[k],k+aux[n-k]]];

As @MichaelE2 pointed out here, this was discussed on Math SE and the accepted answer refers to two blog posts 1, 2. This code implements the proposal in the second blog post.

Examples.

  • This is S[4]:
{{0,0,0},{0,1,1},{1,0,1},{1,1,0},
 {2,2,2},{2,3,3},{3,2,3},{3,3,2}}
  • This is S[5]:
{{0,0,0},{0,1,1},{1,0,1},{1,1,0},
 {2,2,2},{2,3,4},{2,4,3},{3,2,4},{3,3,3},{3,4,2},{4,2,3},{4,3,2},{4,4,4}}

Note. In set-builder notation, $S = A \cup B$ where $k = \lfloor n/2 \rfloor$ and \begin{align} A &= \{(x,y,z) \in \mathbb{Z}^3 \;\mid\; 0 \leq x,y,z < k,\;\; x+y+z = r_A \bmod k \}\\ B &= \{(x,y,z) \in \mathbb{Z}^3 \;\mid\; k \leq x,y,z < n,\;\; x+y+z = r_B \bmod n-k \} \end{align} The $r_A,r_B$ are arbitrary fixed integers.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.