Skip to main content
Notice removed Draw attention by CommunityBot
Bounty Ended with no winning answer by CommunityBot
added some references for the improvement in the lower bound
Source Link
Anurag
  • 1.2k
  • 1
  • 20
  • 29

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line?

Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = 0, y = 0$ and $z = 0$, forms such a set. If we denote by $s(q)$ the smallest possible size, then this gives us $$s(q) \leq 3q^2 - 3q + 1$$ for all $q$.

Since any two points of $\mathbb{F}_2^3$ form a line, we get $s(2) = 2^3 - 1 = 7 = 12 - 6 + 1$. For $q = 3$ we can do better. In $\mathbb{F}_3^3$ the complement of such a set is a cap, i.e., a set of points no three of which are collinear. We know that the largest size of a cap in $\mathbb{F}_3^3$ is $9$ (corresponding to a quadric), and hence $s(3) = 18 < 27 - 9 + 1$. (side note: the problem of finding such a blocking set in $\mathbb{F}_3^n$ is thus equivalent to the famous cap set problem. See the survey article by Bierbrauer and Edel, large caps in projective Galois spaces and the paper by Bateman and Katz, new bounds on cap sets)

Question 1: Can we improve the upper bound in general?

We can also give a lower bound on $s(q)$. Jamison/Brouwer-Schrijver proved using the polynomial method that the smallest possible size of a blocking set in $\mathbb{F}_q^2$ is $2q - 1$. See this, this, this and this for various proofs of their result. Now take any $q$ parallel affine planes in $\mathbb{F}_q^3$, then the intersection of a blocking set with these hyperplanes must have size at least $2q - 1$, and hence $$2q^2 - q \leq s(q).$$

Question 2: Can we improve this lower bound in general?

The Jamison/Brouwer-Schrijver result gives us another way of constructing a blocking set of size $3q^2 - 3q + 1$. Again take $q$ parallel hyperplanes $H_1, \dots, H_q$. Let $B_2, \dots, B_{q}$ be blocking sets of size $2q - 1$ in $H_2, \dots, H_{q}$. Then $B = H_1 \cup B_2 \cup \dots \cup B_{q}$ is a blocking set of size $(q-1)(2q-1) + q^2 = 3q^2 - 3q + 1$.

Note that the problem of determining $s(q)$ is trivial for projective spaces. It's a classical result that a line blocking set in $PG(3,q)$ has size at least $1 + q + q^2$ with equality if and only if it is a hyperplane. See Chapter 3 of current research topics in Galois geometry for a recent survey on projective blocking sets.

Edit 1: After Douglas Zare's improvementanswer below we have $s(q) \geq 2q^2 - 1$ for all $q$ and $s(q) \leq 3q^2 - 3q$ for $q \geq 3$. Can this be improved further?

I have also found two references that prove this lower bound of $2q^2 - 1$, Proposition 4.1 in Nuclei of pointsets in $PG(n,q)$ (1997) and Theorem 3.1 in On Nuclei and Blocking Sets in Desarguesian Spaces (1999). In fact, Sziklai has mentioned the same argument as Douglas Zare after his proof of Proposition 4.1. Their proofs are generalisations of the polynomial technique introduced by Blokhuis in On nuclei and affine blocking sets (1994).

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line?

Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = 0, y = 0$ and $z = 0$, forms such a set. If we denote by $s(q)$ the smallest possible size, then this gives us $$s(q) \leq 3q^2 - 3q + 1$$ for all $q$.

Since any two points of $\mathbb{F}_2^3$ form a line, we get $s(2) = 2^3 - 1 = 7 = 12 - 6 + 1$. For $q = 3$ we can do better. In $\mathbb{F}_3^3$ the complement of such a set is a cap, i.e., a set of points no three of which are collinear. We know that the largest size of a cap in $\mathbb{F}_3^3$ is $9$ (corresponding to a quadric), and hence $s(3) = 18 < 27 - 9 + 1$. (side note: the problem of finding such a blocking set in $\mathbb{F}_3^n$ is thus equivalent to the famous cap set problem. See the survey article by Bierbrauer and Edel, large caps in projective Galois spaces and the paper by Bateman and Katz, new bounds on cap sets)

Question 1: Can we improve the upper bound in general?

We can also give a lower bound on $s(q)$. Jamison/Brouwer-Schrijver proved using the polynomial method that the smallest possible size of a blocking set in $\mathbb{F}_q^2$ is $2q - 1$. See this, this, this and this for various proofs of their result. Now take any $q$ parallel affine planes in $\mathbb{F}_q^3$, then the intersection of a blocking set with these hyperplanes must have size at least $2q - 1$, and hence $$2q^2 - q \leq s(q).$$

Question 2: Can we improve this lower bound in general?

The Jamison/Brouwer-Schrijver result gives us another way of constructing a blocking set of size $3q^2 - 3q + 1$. Again take $q$ parallel hyperplanes $H_1, \dots, H_q$. Let $B_2, \dots, B_{q}$ be blocking sets of size $2q - 1$ in $H_2, \dots, H_{q}$. Then $B = H_1 \cup B_2 \cup \dots \cup B_{q}$ is a blocking set of size $(q-1)(2q-1) + q^2 = 3q^2 - 3q + 1$.

Note that the problem of determining $s(q)$ is trivial for projective spaces. It's a classical result that a line blocking set in $PG(3,q)$ has size at least $1 + q + q^2$ with equality if and only if it is a hyperplane. See Chapter 3 of current research topics in Galois geometry for a recent survey on projective blocking sets.

Edit 1: After Douglas Zare's improvement we have $s(q) \geq 2q^2 - 1$ for all $q$ and $s(q) \leq 3q^2 - 3q$ for $q \geq 3$. Can this be improved further?

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line?

Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = 0, y = 0$ and $z = 0$, forms such a set. If we denote by $s(q)$ the smallest possible size, then this gives us $$s(q) \leq 3q^2 - 3q + 1$$ for all $q$.

Since any two points of $\mathbb{F}_2^3$ form a line, we get $s(2) = 2^3 - 1 = 7 = 12 - 6 + 1$. For $q = 3$ we can do better. In $\mathbb{F}_3^3$ the complement of such a set is a cap, i.e., a set of points no three of which are collinear. We know that the largest size of a cap in $\mathbb{F}_3^3$ is $9$ (corresponding to a quadric), and hence $s(3) = 18 < 27 - 9 + 1$. (side note: the problem of finding such a blocking set in $\mathbb{F}_3^n$ is thus equivalent to the famous cap set problem. See the survey article by Bierbrauer and Edel, large caps in projective Galois spaces and the paper by Bateman and Katz, new bounds on cap sets)

Question 1: Can we improve the upper bound in general?

We can also give a lower bound on $s(q)$. Jamison/Brouwer-Schrijver proved using the polynomial method that the smallest possible size of a blocking set in $\mathbb{F}_q^2$ is $2q - 1$. See this, this, this and this for various proofs of their result. Now take any $q$ parallel affine planes in $\mathbb{F}_q^3$, then the intersection of a blocking set with these hyperplanes must have size at least $2q - 1$, and hence $$2q^2 - q \leq s(q).$$

Question 2: Can we improve this lower bound in general?

The Jamison/Brouwer-Schrijver result gives us another way of constructing a blocking set of size $3q^2 - 3q + 1$. Again take $q$ parallel hyperplanes $H_1, \dots, H_q$. Let $B_2, \dots, B_{q}$ be blocking sets of size $2q - 1$ in $H_2, \dots, H_{q}$. Then $B = H_1 \cup B_2 \cup \dots \cup B_{q}$ is a blocking set of size $(q-1)(2q-1) + q^2 = 3q^2 - 3q + 1$.

Note that the problem of determining $s(q)$ is trivial for projective spaces. It's a classical result that a line blocking set in $PG(3,q)$ has size at least $1 + q + q^2$ with equality if and only if it is a hyperplane. See Chapter 3 of current research topics in Galois geometry for a recent survey on projective blocking sets.

Edit 1: After Douglas Zare's answer below we have $s(q) \geq 2q^2 - 1$ for all $q$ and $s(q) \leq 3q^2 - 3q$ for $q \geq 3$. Can this be improved further?

I have also found two references that prove this lower bound of $2q^2 - 1$, Proposition 4.1 in Nuclei of pointsets in $PG(n,q)$ (1997) and Theorem 3.1 in On Nuclei and Blocking Sets in Desarguesian Spaces (1999). In fact, Sziklai has mentioned the same argument as Douglas Zare after his proof of Proposition 4.1. Their proofs are generalisations of the polynomial technique introduced by Blokhuis in On nuclei and affine blocking sets (1994).

Notice added Draw attention by Anurag
Bounty Started worth 50 reputation by Anurag
added some improvements
Source Link
Anurag
  • 1.2k
  • 1
  • 20
  • 29

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line?

Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = 0, y = 0$ and $z = 0$, forms such a set. If we denote by $s(q)$ the smallest possible size, then this gives us $$s(q) \leq 3q^2 - 3q + 1$$ for all $q$.

Since any two points of $\mathbb{F}_2^3$ form a line, we get $s(2) = 2^3 - 1 = 7 = 12 - 6 + 1$. For $q = 3$ we can do better. In $\mathbb{F}_3^3$ the complement of such a set is a cap, i.e., a set of points no three of which are collinear. We know that the largest size of a cap in $\mathbb{F}_3^3$ is $9$ (corresponding to a quadric), and hence $s(3) = 18 < 27 - 9 + 1$. (side note: the problem of finding such a blocking set in $\mathbb{F}_3^n$ is thus equivalent to the famous cap set problem. See the survey article by Bierbrauer and Edel, large caps in projective Galois spaces and the paper by Bateman and Katz, new bounds on cap sets)

Question 1: Can we improve the upper bound in general?

We can also give a lower bound on $s(q)$. Jamison/Brouwer-Schrijver proved using the polynomial method that the smallest possible size of a blocking set in $\mathbb{F}_q^2$ is $2q - 1$. See this, this, this and this for various proofs of their result. Now take any $q$ parallel affine planes in $\mathbb{F}_q^3$, then the intersection of a blocking set with these hyperplanes must have size at least $2q - 1$, and hence $$2q^2 - q \leq s(q).$$

Question 2: Can we improve this lower bound in general?

The Jamison/Brouwer-Schrijver result gives us another way of constructing a blocking set of size $3q^2 - 3q + 1$. Again take $q$ parallel hyperplanes $H_1, \dots, H_q$. Let $B_2, \dots, B_{q}$ be blocking sets of size $2q - 1$ in $H_2, \dots, H_{q}$. Then $B = H_1 \cup B_2 \cup \dots \cup B_{q}$ is a blocking set of size $(q-1)(2q-1) + q^2 = 3q^2 - 3q + 1$.

Note that the problem of determining $s(q)$ is trivial for projective spaces. It's a classical result that a line blocking set in $PG(3,q)$ has size at least $1 + q + q^2$ with equality if and only if it is a hyperplane. See Chapter 3 of current research topics in Galois geometry for a recent survey on projective blocking sets.

Edit 1: After Douglas Zare's improvement we have $s(q) \geq 2q^2 - 1$ for all $q$ and $s(q) \leq 3q^2 - 3q$ for $q \geq 3$. Can this be improved further?

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line?

Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = 0, y = 0$ and $z = 0$, forms such a set. If we denote by $s(q)$ the smallest possible size, then this gives us $$s(q) \leq 3q^2 - 3q + 1$$ for all $q$.

Since any two points of $\mathbb{F}_2^3$ form a line, we get $s(2) = 2^3 - 1 = 7 = 12 - 6 + 1$. For $q = 3$ we can do better. In $\mathbb{F}_3^3$ the complement of such a set is a cap, i.e., a set of points no three of which are collinear. We know that the largest size of a cap in $\mathbb{F}_3^3$ is $9$ (corresponding to a quadric), and hence $s(3) = 18 < 27 - 9 + 1$. (side note: the problem of finding such a blocking set in $\mathbb{F}_3^n$ is thus equivalent to the famous cap set problem. See the survey article by Bierbrauer and Edel, large caps in projective Galois spaces and the paper by Bateman and Katz, new bounds on cap sets)

Question 1: Can we improve the upper bound in general?

We can also give a lower bound on $s(q)$. Jamison/Brouwer-Schrijver proved using the polynomial method that the smallest possible size of a blocking set in $\mathbb{F}_q^2$ is $2q - 1$. See this, this, this and this for various proofs of their result. Now take any $q$ parallel affine planes in $\mathbb{F}_q^3$, then the intersection of a blocking set with these hyperplanes must have size at least $2q - 1$, and hence $$2q^2 - q \leq s(q).$$

Question 2: Can we improve this lower bound in general?

The Jamison/Brouwer-Schrijver result gives us another way of constructing a blocking set of size $3q^2 - 3q + 1$. Again take $q$ parallel hyperplanes $H_1, \dots, H_q$. Let $B_2, \dots, B_{q}$ be blocking sets of size $2q - 1$ in $H_2, \dots, H_{q}$. Then $B = H_1 \cup B_2 \cup \dots \cup B_{q}$ is a blocking set of size $(q-1)(2q-1) + q^2 = 3q^2 - 3q + 1$.

Note that the problem of determining $s(q)$ is trivial for projective spaces. It's a classical result that a line blocking set in $PG(3,q)$ has size at least $1 + q + q^2$ with equality if and only if it is a hyperplane. See Chapter 3 of current research topics in Galois geometry for a recent survey on projective blocking sets.

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line?

Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = 0, y = 0$ and $z = 0$, forms such a set. If we denote by $s(q)$ the smallest possible size, then this gives us $$s(q) \leq 3q^2 - 3q + 1$$ for all $q$.

Since any two points of $\mathbb{F}_2^3$ form a line, we get $s(2) = 2^3 - 1 = 7 = 12 - 6 + 1$. For $q = 3$ we can do better. In $\mathbb{F}_3^3$ the complement of such a set is a cap, i.e., a set of points no three of which are collinear. We know that the largest size of a cap in $\mathbb{F}_3^3$ is $9$ (corresponding to a quadric), and hence $s(3) = 18 < 27 - 9 + 1$. (side note: the problem of finding such a blocking set in $\mathbb{F}_3^n$ is thus equivalent to the famous cap set problem. See the survey article by Bierbrauer and Edel, large caps in projective Galois spaces and the paper by Bateman and Katz, new bounds on cap sets)

Question 1: Can we improve the upper bound in general?

We can also give a lower bound on $s(q)$. Jamison/Brouwer-Schrijver proved using the polynomial method that the smallest possible size of a blocking set in $\mathbb{F}_q^2$ is $2q - 1$. See this, this, this and this for various proofs of their result. Now take any $q$ parallel affine planes in $\mathbb{F}_q^3$, then the intersection of a blocking set with these hyperplanes must have size at least $2q - 1$, and hence $$2q^2 - q \leq s(q).$$

Question 2: Can we improve this lower bound in general?

The Jamison/Brouwer-Schrijver result gives us another way of constructing a blocking set of size $3q^2 - 3q + 1$. Again take $q$ parallel hyperplanes $H_1, \dots, H_q$. Let $B_2, \dots, B_{q}$ be blocking sets of size $2q - 1$ in $H_2, \dots, H_{q}$. Then $B = H_1 \cup B_2 \cup \dots \cup B_{q}$ is a blocking set of size $(q-1)(2q-1) + q^2 = 3q^2 - 3q + 1$.

Note that the problem of determining $s(q)$ is trivial for projective spaces. It's a classical result that a line blocking set in $PG(3,q)$ has size at least $1 + q + q^2$ with equality if and only if it is a hyperplane. See Chapter 3 of current research topics in Galois geometry for a recent survey on projective blocking sets.

Edit 1: After Douglas Zare's improvement we have $s(q) \geq 2q^2 - 1$ for all $q$ and $s(q) \leq 3q^2 - 3q$ for $q \geq 3$. Can this be improved further?

Source Link
Anurag
  • 1.2k
  • 1
  • 20
  • 29

Blocking sets in three dimensional finite affine spaces

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line?

Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = 0, y = 0$ and $z = 0$, forms such a set. If we denote by $s(q)$ the smallest possible size, then this gives us $$s(q) \leq 3q^2 - 3q + 1$$ for all $q$.

Since any two points of $\mathbb{F}_2^3$ form a line, we get $s(2) = 2^3 - 1 = 7 = 12 - 6 + 1$. For $q = 3$ we can do better. In $\mathbb{F}_3^3$ the complement of such a set is a cap, i.e., a set of points no three of which are collinear. We know that the largest size of a cap in $\mathbb{F}_3^3$ is $9$ (corresponding to a quadric), and hence $s(3) = 18 < 27 - 9 + 1$. (side note: the problem of finding such a blocking set in $\mathbb{F}_3^n$ is thus equivalent to the famous cap set problem. See the survey article by Bierbrauer and Edel, large caps in projective Galois spaces and the paper by Bateman and Katz, new bounds on cap sets)

Question 1: Can we improve the upper bound in general?

We can also give a lower bound on $s(q)$. Jamison/Brouwer-Schrijver proved using the polynomial method that the smallest possible size of a blocking set in $\mathbb{F}_q^2$ is $2q - 1$. See this, this, this and this for various proofs of their result. Now take any $q$ parallel affine planes in $\mathbb{F}_q^3$, then the intersection of a blocking set with these hyperplanes must have size at least $2q - 1$, and hence $$2q^2 - q \leq s(q).$$

Question 2: Can we improve this lower bound in general?

The Jamison/Brouwer-Schrijver result gives us another way of constructing a blocking set of size $3q^2 - 3q + 1$. Again take $q$ parallel hyperplanes $H_1, \dots, H_q$. Let $B_2, \dots, B_{q}$ be blocking sets of size $2q - 1$ in $H_2, \dots, H_{q}$. Then $B = H_1 \cup B_2 \cup \dots \cup B_{q}$ is a blocking set of size $(q-1)(2q-1) + q^2 = 3q^2 - 3q + 1$.

Note that the problem of determining $s(q)$ is trivial for projective spaces. It's a classical result that a line blocking set in $PG(3,q)$ has size at least $1 + q + q^2$ with equality if and only if it is a hyperplane. See Chapter 3 of current research topics in Galois geometry for a recent survey on projective blocking sets.