Counting Arcs in $${\mathbb {F}}_q^2$$

Abstract

Abstract An arc in $$\mathbb F_q^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> </mml:math> is a set $$P \subset \mathbb F_q^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>P</mml:mi> <mml:mo>⊂</mml:mo> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> </mml:mrow> </mml:math> such that no three points of P are collinear. We use the method of hypergraph containers to prove several counting results for arcs. Let $${\mathcal {A}}(q)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>(</mml:mo> <mml:mi>q</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> denote the family of all arcs in $$\mathbb F_q^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> </mml:math> . Our main result is the bound $$\begin{aligned} |{\mathcal {A}}(q)| \le 2^{(1+o(1))q}. \end{aligned}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtable> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>A</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>q</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>|</mml:mo> </mml:mrow> <mml:mo>≤</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> <mml:mi>q</mml:mi> </mml:mrow> </mml:msup> <mml:mo>.</mml:mo> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:math> This matches, up to the factor hidden in the o (1) notation, the trivial lower bound that comes from considering all subsets of an arc of size q . We also give upper bounds for the number of arcs of a fixed (large) size. Let $$k \ge q^{2/3}(\log q)^3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≥</mml:mo> <mml:msup> <mml:mi>q</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>q</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mn>3</mml:mn> </mml:msup> </mml:mrow> </mml:math> , and let $${\mathcal {A}}(q,k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>(</mml:mo> <mml:mi>q</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> denote the family of all arcs in $$\mathbb F_q^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> </mml:math> with cardinality k . We prove that $$\begin{aligned} |{\mathcal {A}}(q,k)| \le \left( {\begin{array}{c}(1+o(1))q\\ k\end{array}}\right) . \end{aligned}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtable> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>A</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>q</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>|</mml:mo> </mml:mrow> <mml:mo>≤</mml:mo> <mml:mfenced> <mml:mrow> <mml:mtable> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> <mml:mi>q</mml:mi> </mml:mrow> </mml:mtd> </mml:mtr> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mrow/> <mml:mi>k</mml:mi> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:mfenced> <mml:mo>.</mml:mo> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:math> This result improves a bound of Roche-Newton and Warren [12]. A nearly matching lower bound $$\begin{aligned} |{\mathcal {A}}(q,k)| \ge \left( {\begin{array}{c}q\\ k\end{array}}\right) \end{aligned}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtable> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>A</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>q</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>|</mml:mo> </mml:mrow> <mml:mo>≥</mml:mo> <mml:mfenced> <mml:mrow> <mml:mtable> <mml:mtr> <mml:mtd> <mml:mi>q</mml:mi> </mml:mtd> </mml:mtr> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mrow/> <mml:mi>k</mml:mi> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:mfenced> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:math> follows by considering all subsets of size k of an arc of size q .

Locations

• Discrete & Computational Geometry - View - PDF
• PubMed - View