Lattice-cube minimal blocking sets

Question

Let $C_d(n)$ be the lattice cube consisting of the $n^d$ points with each of its $d$ coorindates in $\lbrace 1,2,\ldots,n \rbrace$. Define a blocking set for a lattice cube to be a set of points in the cube that meets every axis-parallel line through a lattice point of any facet of the cube. Let $b_d(n)$ be the minimum cardinality of a blocking set for $C_d(n)$.

Q1. What is the function $b_d(n)$?

For $d=2$, selecting the $n$ points on the diagonal through $(1,1)$ and $(n,n)$ suffices to block the $n$ lines through each facet/side of the cube/square; so $C_2(n)=n$. Because a facet consists of $n^{d-1}$ points, and a line orthogonal to the facet through each point must be blocked, $n^{d-1}$ is a lower bound on $b_d(n)$. A more specific version of Q1 is:

Q2. Can the lower bound be achieved? Is $b_d(n) = n^{d-1}$? If the lower bound cannot always be achieved, when can it be achieved?

For $C_3(3)$, the $\mathbb{Z}^3$-cube consisting of $27$ points, here is a blocking set $B$ with $|B|=10=n^2+1$:
        

Perhaps these questions have already been explored? If so, I would appreciate references. Thanks!

My interest in the above questions derive from the more geometrical question: What is the "minimal object'' that casts a (hyper)cube-shadow from parallel light rays in the $d$ coordinate directions? I defer this question until I understand the combinatorial version.

Addendum. As per Johan Wästlund and Eoin, indeed the lowerbound is achievable. Here is a 9-point blocking set for $C_3(3)$:
        

Answer 1

Hi Joseph, I think that the lower bound is always achievable. For example, you can take \begin{equation*} { B = \lbrace (v_1,\ldots ,v_d) \in C_d(n): \sum _{i=1}^d v_i \equiv 0 \mod n \rbrace } \end{equation*} since the modulo sum in this expression takes all $n$ distinct value on any axis parallel line. If we view $C_d(n)$ as the discrete torus, $B$ is just a hyperplane. It would be interesting to know whether all such blocking sets are of this form.

I don't know any references for this specific problem, but there has been interesting work on a similar problem of blocking non-trivial cycles in the discrete torus. Here, we again view $C_d(n)$ as the discrete torus and want to remove a set $B$ which intersects every non-contractible cycle. Maybe the following might be useful:

Béla Bollobás, Guy Kindler, Imre Leader, Ryan O'Donnell: Eliminating Cycles in the Discrete Torus. Algorithmica 50(4): 446-454 (2008)

Noga Alon: Economical Elimination of Cycles in the Torus. Combinatorics, Probability & Computing 18(5): 619-627 (2009)

Answer 2

This is somewhat of an expanded comment on Eoin's answer and his follow-up question of whether such sets correspond to hyperplanes in the discrete torus.

In the $C_2(n)$ case minimal blocking sets correspond to permutation of $\{1...n\}$ (consider a permutation matrix; then a minimal blocking set can be formed by choosing the points corresponding to the positions of the 1's in this matrix). Conversely, every minimal blocking set in the $d=2$ case arises this way, so for $n\geq 4$ not every blocking set corresponds to a hyperplane on a torus.

In the $d=3$ case this can be extended to see that every minimal blocking set corresponds to a set of $n$ permutations whose permutation matrix sums to the all 1's matrix (think of stacking the permutation matrices up to form our cube); again it is clear that not all such sets can correspond to hyperplanes if $n \geq 4$.

For $d \geq 4$, one can apply an analogous stacking approach using sets in $C_{d-1}$ to generate all minimal blocking sets although it is not immediately obvious to me how to relate these sets to permutations easily.

For $n = 2$, it is easy to see that there are exactly two minimal blocking sets in any dimension and both always correspond to toric hyperplanes, and it seems that all minimal blocking sets are also toric hyperplanes for $n=3$ in any dimension due to how little room there is in $S_3$ to form such sets (this should follow from induction on the dimension; once one lays down the first $d-1$-dimensional layer and one point in the next layer, this should determine where all the remaining points must go in the last two layers). If anyone can easily formalize this idea for the $n=3$ case (or provide a counterexample) I would love to see it.