Return to Answer

Not much is known for the general case.

Let $m(k, n, q)$ denote the minimum size of an $k$-blocking set in $AG(n, q)$. Trivially we have $m(0, n, q) = q^n$ and $m(n, n, q) = 1$. By Jamison/Brouwer-Schrijver we get $m(n-1, n, q) = 1 + n(q-1)$ as you have mentioned. To at least give bounds on other values we can prove the following inequality $$qm(k, n-1, q) \leq m(k, n, q) \leq (q-1)m(k, n-1, q) + m(k-1, n - 1, q).$$

The lower bound follows from taking $q$ parallel hyperplanes that cover the space and then observing that the intersection of the blocking set with each of these hyperplanes is $k$-blocking set in $AG(n-1, q)$. For the upper bound, again take $q$ parallel hyperplanes, $H_1, \dots, H_q$. For $1 \leq i \leq q - 1$, let $B_i$ be a $k$-blocking set in $H_i$ and let $B_q$ be a $(k-1)$-blocking set in $H_q$. Then one can argue that $B = B_1 \cup \dots \cup B_q$ is a $k$-blocking set in $AG(n, q)$ as follows. If $S$ is a $k$-flat in $AG(n,q)$ which is contained in any $H_i$ for $i < q$, then it is blocked by $B_i$. If it is contained in $H_q$, then it is blocked by $B_q$ since $B_q$ blocks all $(k-1)$-flats, it must block all $k$-flats as well. If $S$ is not contained in any of the $H_i$'s then its intersection with $H_q$ is a $(k-1)$-flat, which is again blocked by $B_q$.

For your particular case of $(n-2)$-blocking sets, this tells us that $$q(1 + (n-1)(q-1) \leq m(n-2, n, q) \leq (q-1)^2\binom{n}{2} + (q-1)n + 1.$$

So, for a constant $q$ there is a linear lower bound and a quadratic upper bound. I don't know if there has been any improvement ``in general'' besides the one that you mention for $q = 2$. (Do your methods extends to $q > 2$? If yes, then do they improve these bounds?) I have asked a couple of colleagues who work in finite geometry and they don't know either.

For some particular values, note that in $AG(3,3)$ the complement of such a blocking set is a cap (see https://www.mathi.uni-heidelberg.de/~yves/Papers/CapSurvey.pdf). And we know that the maximum size of a cap in $AG(3,3)$ is $9$. Thus, $m(1, 3, 3) = 18$, which is one less than the upper bound we get above. I guess some other specific values can also be computed. Similarly, the problem of finding smallest 1-blocking sets in $AG(n,3)$ is equivalent to finding the largest caps in $AG(n,3)$, on which there is significant progress in general. See New bounds on cap sets.

Note that the problem is completely solved for projective spaces. We know that a $k$-blocking set in $PG(n,q)$ has size at least $\big[ {n-k + 1 \atop 1} \big]_q = 1 + q + \dots + q^{n-k}$ with equality if and only if the blocking set is an $(n-k)$-dimensional subspace. But if you want to talk about ``minimal'' blocking sets instead of the smallest ones, then the problem again becomes much harder.

For a recent survey on projective blocking sets see Chapter 3 in current research topics in galois geometry. There is also a small section on affine blocking sets where they mention the same recursive bound. They follow a different terminology though: what you have called an $(n-k)$-blocking set is called a $k$-blocking set.

Edit When $n = 3$ there are some nice improvements to the bounds. Peter Sziklai, and later Simeon Ball proved general results on $1$-blocking sets in affine spaces, which imply that the size of such a set in $AG(3,q)$ is at least $2q^2 - 1$. See Blocking sets in three dimensional finite affine spaces for the details. Also, the lower bound can be improved in general to $m(n-2, n, q) \geq (n-1)(q^2 - 1) + 1$. See Section 3 in http://www-ma4.upc.es/~simeon/polynomialmethod.pdf

Not much is known for the general case.

Let $m(k, n, q)$ denote the minimum size of an $k$-blocking set in $AG(n, q)$. Trivially we have $m(0, n, q) = q^n$ and $m(n, n, q) = 1$. By Jamison/Brouwer-Schrijver we get $m(n-1, n, q) = 1 + n(q-1)$ as you have mentioned. To at least give bounds on other values we can prove the following inequality $$qm(k, n-1, q) \leq m(k, n, q) \leq (q-1)m(k, n-1, q) + m(k-1, n - 1, q).$$

The lower bound follows from taking $q$ parallel hyperplanes that cover the space and then observing that the intersection of the blocking set with each of these hyperplanes is $k$-blocking set in $AG(n-1, q)$. For the upper bound, again take $q$ parallel hyperplanes, $H_1, \dots, H_q$. For $1 \leq i \leq q - 1$, let $B_i$ be a $k$-blocking set in $H_i$ and let $B_q$ be a $(k-1)$-blocking set in $H_q$. Then one can argue that $B = B_1 \cup \dots \cup B_q$ is a $k$-blocking set in $AG(n, q)$ as follows. If $S$ is a $k$-flat in $AG(n,q)$ which is contained in any $H_i$ for $i < q$, then it is blocked by $B_i$. If it is contained in $H_q$, then it is blocked by $B_q$ since $B_q$ blocks all $(k-1)$-flats, it must block all $k$-flats as well. If $S$ is not contained in any of the $H_i$'s then its intersection with $H_q$ is a $(k-1)$-flat, which is again blocked by $B_q$.

For your particular case of $(n-2)$-blocking sets, this tells us that $$q(1 + (n-1)(q-1) \leq m(n-2, n, q) \leq (q-1)^2\binom{n}{2} + (q-1)n + 1.$$

So, for a constant $q$ there is a linear lower bound and a quadratic upper bound. I don't know if there has been any improvement ``in general'' besides the one that you mention for $q = 2$. (Do your methods extends to $q > 2$? If yes, then do they improve these bounds?) I have asked a couple of colleagues who work in finite geometry and they don't know either.

For some particular values, note that in $AG(3,3)$ the complement of such a blocking set is a cap (see https://www.mathi.uni-heidelberg.de/~yves/Papers/CapSurvey.pdf). And we know that the maximum size of a cap in $AG(3,3)$ is $9$. Thus, $m(1, 3, 3) = 18$, which is one less than the upper bound we get above. I guess some other specific values can also be computed. Similarly, the problem of finding smallest 1-blocking sets in $AG(n,3)$ is equivalent to finding the largest caps in $AG(n,3)$, on which there is significant progress in general. See New bounds on cap sets.

Note that the problem is completely solved for projective spaces. We know that a $k$-blocking set in $PG(n,q)$ has size at least $\big[ {n-k + 1 \atop 1} \big]_q = 1 + q + \dots + q^{n-k}$ with equality if and only if the blocking set is an $(n-k)$-dimensional subspace. But if you want to talk about ``minimal'' blocking sets instead of the smallest ones, then the problem again becomes much harder.

For a recent survey on projective blocking sets see Chapter 3 in current research topics in galois geometry. There is also a small section on affine blocking sets where they mention the same recursive bound. They follow a different terminology though: what you have called an $(n-k)$-blocking set is called a $k$-blocking set.

Edit When $n = 3$ there are some nice improvements to the bounds. Peter Sziklai, and later Simeon Ball proved general results on $1$-blocking sets in affine spaces, which imply that the size of such a set in $AG(3,q)$ is at least $2q^2 - 1$. See Blocking sets in three dimensional finite affine spaces for the details. Also, the lower bound can be improved in general to $m(n-2, n, q) \geq (n-1)(q^2 - 1) + 1$. See Section 3 in http://www-ma4.upc.es/~simeon/polynomialmethod.pdf

Not much is known for the general case.

Let $m(k, n, q)$ denote the minimum size of an $k$-blocking set in $AG(n, q)$. Trivially we have $m(0, n, q) = q^n$ and $m(n, n, q) = 1$. By Jamison/Brouwer-Schrijver we get $m(n-1, n, q) = 1 + n(q-1)$ as you have mentioned. To at least give bounds on other values we can prove the following inequality $$qm(k, n-1, q) \leq m(k, n, q) \leq (q-1)m(k, n-1, q) + m(k-1, n - 1, q).$$

The lower bound follows from taking $q$ parallel hyperplanes that cover the space and then observing that the intersection of the blocking set with each of these hyperplanes is $k$-blocking set in $AG(n-1, q)$. For the upper bound, again take $q$ parallel hyperplanes, $H_1, \dots, H_q$. For $1 \leq i \leq q - 1$, let $B_i$ be a $k$-blocking set in $H_i$ and let $B_q$ be a $(k-1)$-blocking set in $H_q$. Then one can argue that $B = B_1 \cup \dots \cup B_q$ is a $k$-blocking set in $AG(n, q)$ as follows. If $S$ is a $k$-flat in $AG(n,q)$ which is contained in any $H_i$ for $i < q$, then it is blocked by $B_i$. If it is contained in $H_q$, then it is blocked by $B_q$ since $B_q$ blocks all $(k-1)$-flats, it must block all $k$-flats as well. If $S$ is not contained in any of the $H_i$'s then its intersection with $H_q$ is a $(k-1)$-flat, which is again blocked by $B_q$.

For your particular case of $(n-2)$-blocking sets, this tells us that $$q(1 + (n-1)(q-1) \leq m(n-2, n, q) \leq (q-1)^2\binom{n}{2} + (q-1)n + 1.$$

So, for a constant $q$ there is a linear lower bound and a quadratic upper bound. I don't know if there has been any improvement ``in general'' besides the one that you mention for $q = 2$. (Do your methods extends to $q > 2$? If yes, then do they improve these bounds?) I have asked a couple of colleagues who work in finite geometry and they don't know either.

For some particular values, note that in $AG(3,3)$ the complement of such a blocking set is a cap (see https://www.mathi.uni-heidelberg.de/~yves/Papers/CapSurvey.pdf). And we know that the maximum size of a cap in $AG(3,3)$ is $9$. Thus, $m(1, 3, 3) = 18$, which is one less than the upper bound we get above. I guess some other specific values can also be computed. Similarly, the problem of finding smallest 1-blocking sets in $AG(n,3)$ is equivalent to finding the largest caps in $AG(n,3)$, on which there is significant progress in general. See New bounds on cap sets.

Note that the problem is completely solved for projective spaces. We know that a $k$-blocking set in $PG(n,q)$ has size at least $\big[ {n-k + 1 \atop 1} \big]_q = 1 + q + \dots + q^{n-k}$ with equality if and only if the blocking set is an $(n-k)$-dimensional subspace. But if you want to talk about ``minimal'' blocking sets instead of the smallest ones, then the problem again becomes much harder.

For a recent survey on projective blocking sets see Chapter 3 in current research topics in galois geometry. There is also a small section on affine blocking sets where they mention the same recursive bound. They follow a different terminology though: what you have called an $(n-k)$-blocking set is called a $k$-blocking set.

Edit When $n = 3$ there are some nice improvements to the bounds. Peter Sziklai, and later Simeon Ball proved general results on $1$-blocking sets in affine spaces, which imply that the size of such a set in $AG(3,q)$ is at least $2q^2 - 1$. See Blocking sets in three dimensional finite affine spaces for the details.

Not much is known for the general case.

Let $m(k, n, q)$ denote the minimum size of an $k$-blocking set in $AG(n, q)$. Trivially we have $m(0, n, q) = q^n$ and $m(n, n, q) = 1$. By Jamison/Brouwer-Schrijver we get $m(n-1, n, q) = 1 + n(q-1)$ as you have mentioned. To at least give bounds on other values we can prove the following inequality $$qm(k, n-1, q) \leq m(k, n, q) \leq (q-1)m(k, n-1, q) + m(k-1, n - 1, q).$$

The lower bound follows from taking $q$ parallel hyperplanes that cover the space and then observing that the intersection of the blocking set with each of these hyperplanes is $k$-blocking set in $AG(n-1, q)$. For the upper bound, again take $q$ parallel hyperplanes, $H_1, \dots, H_q$. For $1 \leq i \leq q - 1$, let $B_i$ be a $k$-blocking set in $H_i$ and let $B_q$ be a $(k-1)$-blocking set in $H_q$. Then one can argue that $B = B_1 \cup \dots \cup B_q$ is a $k$-blocking set in $AG(n, q)$ as follows. If $S$ is a $k$-flat in $AG(n,q)$ which is contained in any $H_i$ for $i < q$, then it is blocked by $B_i$. If it is contained in $H_q$, then it is blocked by $B_q$ since $B_q$ blocks all $(k-1)$-flats, it must block all $k$-flats as well. If $S$ is not contained in any of the $H_i$'s then its intersection with $H_q$ is a $(k-1)$-flat, which is again blocked by $B_q$.

For your particular case of $(n-2)$-blocking sets, this tells us that $$q(1 + (n-1)(q-1) \leq m(n-2, n, q) \leq (q-1)^2\binom{n}{2} + (q-1)n + 1.$$

So, for a constant $q$ there is a linear lower bound and a quadratic upper bound. I don't know if there has been any improvement ``in general'' besides the one that you mention for $q = 2$. (Do your methods extends to $q > 2$? If yes, then do they improve these bounds?) I have asked a couple of colleagues who work in finite geometry and they don't know either.

For some particular values, note that in $AG(3,3)$ the complement of such a blocking set is a cap (see https://www.mathi.uni-heidelberg.de/~yves/Papers/CapSurvey.pdf). And we know that the maximum size of a cap in $AG(3,3)$ is $9$. Thus, $m(1, 3, 3) = 18$, which is one less than the upper bound we get above. I guess some other specific values can also be computed. Similarly, the problem of finding smallest 1-blocking sets in $AG(n,3)$ is equivalent to finding the largest caps in $AG(n,3)$, on which there is significant progress in general. See New bounds on cap sets.

Note that the problem is completely solved for projective spaces. We know that a $k$-blocking set in $PG(n,q)$ has size at least $\big[ {n-k + 1 \atop 1} \big]_q = 1 + q + \dots + q^{n-k}$ with equality if and only if the blocking set is an $(n-k)$-dimensional subspace. But if you want to talk about ``minimal'' blocking sets instead of the smallest ones, then the problem again becomes much harder.

For a recent survey on projective blocking sets see Chapter 3 in current research topics in galois geometry. There is also a small section on affine blocking sets where they mention the same recursive bound. They follow a different terminology though: what you have called an $(n-k)$-blocking set is called a $k$-blocking set.

Edit When $n = 3$ there are some nice improvements to the bounds. Peter Sziklai, and later Simeon Ball proved general results on $1$-blocking sets in affine spaces, which imply that the size of such a set in $AG(3,q)$ is at least $2q^2 - 1$. See Blocking sets in three dimensional finite affine spaces for the details. Also, the lower bound can be improved in general to $m(n-2, n, q) \geq (n-1)(q^2 - 1) + 1$. See Section 3 in http://www-ma4.upc.es/~simeon/polynomialmethod.pdf

Not much is known for the general case.

Let $m(k, n, q)$ denote the minimum size of an $k$-blocking set in $AG(n, q)$. Trivially we have $m(0, n, q) = q^n$ and $m(n, n, q) = 1$. By Jamison/Brouwer-Schrijver we get $m(n-1, n, q) = 1 + n(q-1)$ as you have mentioned. To at least give bounds on other values we can prove the following inequality $$qm(k, n-1, q) \leq m(k, n, q) \leq (q-1)m(k, n-1, q) + m(k-1, n - 1, q).$$

The lower bound follows from taking $q$ parallel hyperplanes that cover the space and then observing that the intersection of the blocking set with each of these hyperplanes is $k$-blocking set in $AG(n-1, q)$. For the upper bound, again take $q$ parallel hyperplanes, $H_1, \dots, H_q$. For $1 \leq i \leq q - 1$, let $B_i$ be a $k$-blocking set in $H_i$ and let $B_q$ be a $(k-1)$-blocking set in $H_q$. Then one can argue that $B = B_1 \cup \dots \cup B_q$ is a $k$-blocking set in $AG(n, q)$ as follows. If $S$ is a $k$-flat in $AG(n,q)$ which is contained in any $H_i$ for $i < q$, then it is blocked by $B_i$. If it is contained in $H_q$, then it is blocked by $B_q$ since $B_q$ blocks all $(k-1)$-flats, it must block all $k$-flats as well. If $S$ is not contained in any of the $H_i$'s then its intersection with $H_q$ is a $(k-1)$-flat, which is again blocked by $B_q$.

For your particular case of $(n-2)$-blocking sets, this tells us that $$q(1 + (n-1)(q-1) \leq m(n-2, n, q) \leq (q-1)^2\binom{n}{2} + (q-1)n + 1.$$

So, for a constant $q$ there is a linear lower bound and a quadratic upper bound. I don't know if there has been any improvement ``in general'' besides the one that you mention for $q = 2$. (Do your methods extends to $q > 2$? If yes, then do they improve these bounds?) I have asked a couple of colleagues who work in finite geometry and they don't know either.

For some particular values, note that in $AG(3,3)$ the complement of such a blocking set is a cap (see https://www.mathi.uni-heidelberg.de/~yves/Papers/CapSurvey.pdf). And we know that the maximum size of a cap in $AG(3,3)$ is $9$. Thus, $m(1, 3, 3) = 18$, which is one less than the upper bound we get above. I guess some other specific values can also be computed. Similarly, the problem of finding smallest 1-blocking sets in $AG(n,3)$ is equivalent to finding the largest caps in $AG(n,3)$, on which there is significant progress in general. See New bounds on cap sets.

Note that the problem is completely solved for projective spaces. We know that a $k$-blocking set in $PG(n,q)$ has size at least $\big[ {n-k + 1 \atop 1} \big]_q = 1 + q + \dots + q^{n-k}$ with equality if and only if the blocking set is an $(n-k)$-dimensional subspace. But if you want to talk about ``minimal'' blocking sets instead of the smallest ones, then the problem again becomes much harder.

For a recent survey on projective blocking sets see Chapter 3 in current research topics in galois geometry. There is also a small section on affine blocking sets where they mention the same recursive bound. They follow a different terminology though: what you have called an $(n-k)$-blocking set is called a $k$-blocking set.

Not much is known for the general case.

Let $m(k, n, q)$ denote the minimum size of an $k$-blocking set in $AG(n, q)$. Trivially we have $m(0, n, q) = q^n$ and $m(n, n, q) = 1$. By Jamison/Brouwer-Schrijver we get $m(n-1, n, q) = 1 + n(q-1)$ as you have mentioned. To at least give bounds on other values we can prove the following inequality $$qm(k, n-1, q) \leq m(k, n, q) \leq (q-1)m(k, n-1, q) + m(k-1, n - 1, q).$$

The lower bound follows from taking $q$ parallel hyperplanes that cover the space and then observing that the intersection of the blocking set with each of these hyperplanes is $k$-blocking set in $AG(n-1, q)$. For the upper bound, again take $q$ parallel hyperplanes, $H_1, \dots, H_q$. For $1 \leq i \leq q - 1$, let $B_i$ be a $k$-blocking set in $H_i$ and let $B_q$ be a $(k-1)$-blocking set in $H_q$. Then one can argue that $B = B_1 \cup \dots \cup B_q$ is a $k$-blocking set in $AG(n, q)$ as follows. If $S$ is a $k$-flat in $AG(n,q)$ which is contained in any $H_i$ for $i < q$, then it is blocked by $B_i$. If it is contained in $H_q$, then it is blocked by $B_q$ since $B_q$ blocks all $(k-1)$-flats, it must block all $k$-flats as well. If $S$ is not contained in any of the $H_i$'s then its intersection with $H_q$ is a $(k-1)$-flat, which is again blocked by $B_q$.

For your particular case of $(n-2)$-blocking sets, this tells us that $$q(1 + (n-1)(q-1) \leq m(n-2, n, q) \leq (q-1)^2\binom{n}{2} + (q-1)n + 1.$$

So, for a constant $q$ there is a linear lower bound and a quadratic upper bound. I don't know if there has been any improvement ``in general'' besides the one that you mention for $q = 2$. (Do your methods extends to $q > 2$? If yes, then do they improve these bounds?) I have asked a couple of colleagues who work in finite geometry and they don't know either.

For some particular values, note that in $AG(3,3)$ the complement of such a blocking set is a cap (see https://www.mathi.uni-heidelberg.de/~yves/Papers/CapSurvey.pdf). And we know that the maximum size of a cap in $AG(3,3)$ is $9$. Thus, $m(1, 3, 3) = 18$, which is one less than the upper bound we get above. I guess some other specific values can also be computed. Similarly, the problem of finding smallest 1-blocking sets in $AG(n,3)$ is equivalent to finding the largest caps in $AG(n,3)$, on which there is significant progress in general. See New bounds on cap sets.

Note that the problem is completely solved for projective spaces. We know that a $k$-blocking set in $PG(n,q)$ has size at least $\big[ {n-k + 1 \atop 1} \big]_q = 1 + q + \dots + q^{n-k}$ with equality if and only if the blocking set is an $(n-k)$-dimensional subspace. But if you want to talk about ``minimal'' blocking sets instead of the smallest ones, then the problem again becomes much harder.

For a recent survey on projective blocking sets see Chapter 3 in current research topics in galois geometry. There is also a small section on affine blocking sets where they mention the same recursive bound. They follow a different terminology though: what you have called an $(n-k)$-blocking set is called a $k$-blocking set.

Edit When $n = 3$ there are some nice improvements to the bounds. Peter Sziklai, and later Simeon Ball proved general results on $1$-blocking sets in affine spaces, which imply that the size of such a set in $AG(3,q)$ is at least $2q^2 - 1$. See Blocking sets in three dimensional finite affine spaces for the details.