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$
7
  • 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$ Commented Nov 15, 2015 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
    Commented Nov 16, 2015 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$ Commented Nov 16, 2015 at 8:53
  • $\begingroup$ Yes. Same idea gives $(n-2)$-blocking set of order ~ $n^{\log_{2} 3}$ $\endgroup$
    – Ashot
    Commented Nov 16, 2015 at 16:00
  • $\begingroup$ How did you get the lower bound of 2n - 1? I think it should be 2n. Take 2 disjoint hyperplanes that cover the space. Then every (n-2)-blocking set in AG(n,2) gives rise to an (n-1)-blocking set in these AG(n-1,2), which has size at least n by the Jamison/Brouwer-Schrijver bound. $\endgroup$
    – Anurag
    Commented Jan 22, 2016 at 23:52

1 Answer 1

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$
2
  • $\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
    Commented Jan 26, 2016 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
    Commented Jan 26, 2016 at 18:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .