5
$\begingroup$

Let's define $k$-blocking set in affine space $AG(n,q)$ a set that meets every coset (translate of subspace) of dimension $k$.

I have seen a lot work related to minimal $(n-1)$-blockings set.

Covering finite fields with cosets of subspaces.

The Blocking Number of an Affine Space

In these articles it is proved that minimal $(n-1)$-blocking has $n(q-1)+1$ points.

I can't find any result about minimal $(n-2)$-blocking sets (even for $AG(n,2)$). I have managed to prove following bounds about $(n-2)$-blocking set in $AG(n,2)$. It has at least $2n-1$ and no more than $3n^{\log_{2} 3}+1$ points.

Here is a link to my paper. http://ysu.am/files/8.On%20The%20Minimal%20Coset%20Covering%20of%20Solutions%20of%20a%20Boolean%20Equation.pdf

I am very interested in the solution of the problem. Does anyone have any information about it?

I have also asked following questions related to problem: https://math.stackexchange.com/questions/869308/blocking-set-for-cosets-of-codimension-2 https://math.stackexchange.com/questions/863592/find-minimal-set-of-cosets-c-so-that-each-2-vectors-in-a-n-are-in-one-cos

$\endgroup$
  • $\begingroup$ This must be known. You may have a better luck if you contact the experts in finite geometries. $\endgroup$ – Seva Nov 6 '15 at 18:10
  • 1
    $\begingroup$ I'm interested in this problem as well. Did you try extending the Szeméredi approach by including both subspace equations in the polynomial? $\endgroup$ – Thomas Dybdahl Ahle Nov 15 '15 at 22:12
  • 1
    $\begingroup$ I have not tried it. Can you please share the paper? Here is my result dropbox.com/s/dvggj20u97xudh2/… $\endgroup$ – Ashot Nov 16 '15 at 6:23
  • $\begingroup$ You already have a link to the paper I was thinking about. Alon has a slightly shorter version on page 23 of tau.ac.il/~nogaa/PDFS/tools1.pdf . There are also some mentions on affine blocking sets in goo.gl/dUiqGU , but there doesn't appear to be a solution, at least at the time of release of the book. PG seems more well studied. Is it possible to generalize your results for $q>2$? $\endgroup$ – Thomas Dybdahl Ahle Nov 16 '15 at 8:53
  • $\begingroup$ Yes. Same idea gives $(n-2)$-blocking set of order ~ $n^{\log_{2} 3}$ $\endgroup$ – Ashot Nov 16 '15 at 16:00
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for the answer. The same method works for $q>2$ as well. Just the constant factor is changes: $q^2-1$ instead of $3$. $\endgroup$ – Ashot Jan 26 '16 at 18:01
  • $\begingroup$ You are welcome. But if we use the method that you have described for a general $q$, then shouldn't the bound be $(q^2 - 1)^{\log_2^n} = n^{\log_2^{q^2 - 1}}$, when $n$ is a power of $2$? This is because in your base step you will have $F(2) = q^2 - 1$. And then this upper bound will be worse than the quadratic upper bound we have. For example, for $q = 3$ it gives an upper bound of $O(n^3)$, while the bounds I have described are $O(n^2)$. $\endgroup$ – Anurag Jan 26 '16 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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