% to be submitted to EJC
% revised by Qi on Aug. 103
\documentclass[12pt]{article}
\usepackage{e-jc}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}


% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

%% Use this to add footnotes 
\def\peter#1 {\fbox {\footnote {\ }}\ \footnotetext { From Peter: {\color{red}#1}}}

\def\gohar#1 {\fbox {\footnote {\ }}\ \footnotetext { From Gohar: {\color{blue}#1}}}

\def\qi#1 {\fbox {\footnote {\ }}\ \footnotetext { From Qi: {\color{orange}#1}}}

%% Use this to add new text or change the main text.
\newcommand{\mpeter}[1]{{{\color{red}#1}}}
\newcommand{\mgohar}[1]{{{\color{blue}#1}}}
\newcommand{\mqi}[1]{{{\color{orange}#1}}}



\newcommand{\bZ}{{\bf Z}}
\newcommand{\bbZ}{{\mathbb Z}}
\newcommand{\tr}{{\rm Tr}}
\newcommand{\gf}{{\mathbb F}}
\newcommand{\calC}{{\mathcal C}}
\newcommand{\calD}{{\mathcal D}}
\newcommand{\dy}{{\rm DY}}
\newcommand{\rt}{{\rm RT}}
\newcommand{\p}{{\rm P}}
\newcommand{\dm}{{\rm dim}}



% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf On the size of Kakeya sets in finite vector spaces}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Gohar Kyureghyan 
\thanks{The first and third authors thank Vsevolod Lev for bringing their attention to~\cite{mathoverflow}. The third author is supported by the Alexander von Humboldt (AvH) Stiftung/Foundation.}\\
\small Institute of Algebra and Geometry\\[-0.8ex] 
\small Otto-von-Guericke University Magdeburg\\[-0.8ex]
\small 39106 Magdeburg, Germany\\
\small\tt gohar.kyureghyan@ovgu.de\\
\and
Peter M\"uller \\
\small Institute for Mathematics\\[-0.8ex] 
\small University of W\"urzburg\\[-0.8ex] 
\small Campus Hubland Nord, 97074 W\"urzburg, Germany\\
\small\tt peter.mueller@mathematik.uni-wuerzburg.de\\
\and Qi Wang \\
\small Institute of Algebra and Geometry\\[-0.8ex]
\small Otto-von-Guericke University Magdeburg\\[-0.8ex]
\small 39106 Magdeburg, Germany\\
\small\tt qi.wang@ovgu.de\\
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

 \date{\dateline{submission date}{acceptance date}\\
\small Mathematics Subject Classifications: 11T30, 11T06}



\begin{document}


\maketitle




\begin{abstract}
For a finite field $\gf_q$, a Kakeya set $K$ is a subset of $\gf_q^n$ that contains a line in every direction. This paper derives new  upper bounds on the minimum size of Kakeya sets when $q$ is even. 

\bigskip\noindent \textbf{Keywords:} Kakeya set; finite vector space; Gold power function
\end{abstract}



\section{Introduction}

Let $\gf_q$ be a finite field with $q$ elements. A {\em Kakeya set} $K \subset \gf_q^n$ is a set containing a line in every direction. 
More formally, $K \subset \gf_q^n$ is a Kakeya set if and only if for every ${\bf x} \in \gf_q^n$, there exists ${\bf y} \in \gf_q^n$ such that $\{ {\bf y} + t {\bf x} : t \in \gf_q \} \subset K$. Wolff in~\cite{wolff99} asked whether a lower bound of the form $|K| \geq C_n \cdot q^n$ holds for all Kakeya sets $K$, where $C_n$ is a constant depending
only on $n$. Dvir~\cite{Dvir08} first gave such a lower bound with $|K| \geq (1/n!) q^n$. Later Dvir, Kopparty, Saraf and Sudan improved the lower bound to $|K| \geq (1/2^n) q^n$ in~\cite{DKSS09} (see also~\cite{SS08}). It was shown in~\cite{DKSS09} that for any $n \geq 1$ there exists a Kakeya set $K \subset \gf_q^n$ with
\begin{equation}\label{eqn-upperbound}
  |K| \leq 2^{-(n-1)} q^n + O(q^{n-1}).
\end{equation}
For more information on Kakeya sets, we refer to a recent survey~\cite{Dvir12}.
 
When $q$ is bounded and $n$ grows, bound (\ref{eqn-upperbound}) is weak, and some recent papers improved the $O$-term in it to give better upper bounds for this case. 
The best currently known bound was obtained by Kopparty, Lev, Saraf and Sudan in~\cite{KLSS11}, following the ideas from~\cite{SS08,DKSS09} (see also~\cite{MT04}):  

\begin{theorem}\cite[Theorem 6]{KLSS11}\label{thm-levbound}
Let $n \geq 1$ be an integer and $q$ a prime power. There exists a Kakeya set $K \subset \gf_q^n$ with
$$
|K| < 
\left\{ \begin{array}{ll}
  2\left( 1+ \frac{1}{q-1} \right) \left(\frac{q+1}{2}\right)^n & \textrm{if $q$ is odd,} \\
  \frac{3}{2} \left( 1 + \frac{1}{q-1} \right) \left(\frac{2q+1}{3}\right)^n & \textrm{if $q$ is an even power of $2$,} \\
  \frac{3}{2} \left( \frac{2(q+\sqrt{q}+1)}{3} \right)^n & \textrm{if $q$ is an odd power of $2$}.
\end{array}\right.
$$
\end{theorem}

Theorem~\ref{thm-levbound} was proved by constructing a Kakeya set $K \subset \gf_q^n$ from a suitable function $f: \gf_q \rightarrow \gf_q$ as follows: For a given $t \in \gf_q$, set $$I_f(t) := \{ f(x) + tx \,|\, x \in \gf_q\}.$$ 
Further, define 
$$
K := \{(x_1, \ldots, x_j, t, 0, \ldots, 0)\,|\, 0 \leq j \leq n-1, t \in \gf_q, x_1, \ldots, x_j \in I_f(t) \}.
$$
If $f$ is a non-linear function, then $K$ is  a Kakeya set~\cite{KLSS11} of size 
\begin{equation}\label{eqn-kssize}
  |K| = \sum_{j=0}^{n-1} \sum_{t \in \gf_q} |I_f(t)|^j = \sum_{t \in \gf_q} \frac{|I_f(t)|^n-1}{|I_f(t)| - 1} .
\end{equation}
Clearly, to construct a small Kakeya set, we need to find a function $f: \gf_q \rightarrow \gf_q$ for which the sets $I_f(t)$ are small. 
However,  for a  generic function $f:\gf_q \to \gf_q$, it is  difficult to have a good estimation  for the values $|I_f(t)|$, where $t \in \gf_q$.
Theorem~\ref{thm-levbound} was proved by taking
\begin{itemize}
  \item[-] $f(x) = x^2$ for $q$ odd, since then $|I_f(t)| \leq (q+1)/2$ holds for all $ t \in \gf_q$;
  \item[-] $f(x) = x^3$ for $q$ an even power of $2$, since then $|I_f(t)| \leq (2q + 1)/3$ holds for all $t \in \gf_q$;
  \item[-] $f(x) = x^{q-2} + x^2$ for $q$ an odd power of $2$, since then $|I_f(t)| \leq 2(q + \sqrt{q} + 1)/3$ holds for all $t \in \gf_q$.
\end{itemize}

Lemma 21 in~\cite{KLSS11} shows that for any $q$ and any function $f :\gf_q \to \gf_q$, there is an element $t \in \gf_q$ such that
$| I_f(t)| > q/2$. Hence for $q$ odd the function $f(x)=x^2$ yields the best upper bound  for the minimum size of Kakeya sets
produced by the construction presented above. For an even $q$, the authors of \cite{KLSS11} ask whether and to which extent the bounds of Theorem \ref{thm-levbound}
can be improved by choosing a better function $f$.
In this paper, we investigate this question further and derive indeed  better upper bounds on the size of Kakeya sets $K \subset \gf_q^n$, when $q$ is even.
 Our main result is
\begin{equation}\label{new-bound}
|K| < 
\left\{ \begin{array}{ll} \vspace*{0.3cm}
\frac{2q}{q + \sqrt{q} - 2} \left( \frac{q + \sqrt{q}}{2} \right)^n  & \textrm{if $q$ is an even power of $2$,} \\
  \frac{8q}{5q +2\sqrt{q}-3} \left( \frac{5q+ 2\sqrt{q}+5}{8} \right)^n & \textrm{if $q$ is an odd power of $2$}.
\end{array}\right.
\end{equation}
When  $q$ is an even power of $2$, say $q = 2^m$, we prove (\ref{new-bound}) by
determining explicitly the values $|I_f(t)|$ for $f(x) = x^{2^{m/2}+1}$ and $t \in \gf_q$. In the case  $q$ is an odd power of $2$,
the result follows with $f(x) = x^4 + x^3$. Presently, it is not clear to us, whether the bounds in (\ref{new-bound})
can be improved.


The following result by Bluher~\cite{Blu04} is used later in the paper:


\begin{theorem}\cite[Theorem 5.6]{Blu04}\label{thm-blu}
  Let $q = 2^m$ and $0 \leq i < m$ with $d = \gcd(i,m)$. Let $N_0$ denote the number of $b \in \gf_q^*$ such that $x^{2^i+1} + bx + b$ has no root in $\gf_q$.
\begin{itemize} \vspace*{0.1cm}
  \item[(i)] If $m/d$ is even, then $N_0 = \displaystyle{\frac{2^d(q-1)}{2(2^d+1)}}$. \vspace*{0.2cm}
  \item[(ii)] If $m/d$ is odd, then $N_0 = \displaystyle{\frac{2^d(q+1)}{2(2^d + 1)}}$.
\end{itemize}
\end{theorem}




\section{On Kakeya sets constructed using Gold power functions}

In this section, we use the Gold power functions $f(x)= x^{2^i+1}$ to derive  upper bounds on the minimum size of Kakeya sets $K \subset \gf_q^n$ with $q$ even. 
Theorem \ref{thm-blu} allows us to determine explicitly the size of the image set $I_f(t) := \{f(x) + tx: x \in \gf_q \}$ with $f(x) = x^{2^i + 1}$ and $t \in \gf_q$.

\begin{proposition}\label{pro-issize}
  Let $q = 2^m$, $f(x) = x^{2^i + 1} \in \gf_q[x]$ with $0 \leq i < m$, and $d = \gcd(i,m)$. Set $I_f(t) := \{f(x) + tx: x \in \gf_q \}$ for $t \in \gf_q$. We have: 
  \begin{itemize}
    \item[(i)] if $m/d$ is even, then $|I_f(0)| = \displaystyle{1 + \frac{q - 1}{2^d+1}}$, and $|I_f(t)| = \displaystyle{ \frac{q+1}{2} + \frac{q-1}{2(2^d+1)}} $ for all $t \in \gf_q^*$;
    \item[(ii)] if $m/d$ is odd, then $|I_f(0)| = \displaystyle{q}$, and $|I_f(t)| = \displaystyle{ \frac{q-1}{2} + \frac{q+1}{2(2^d + 1)}} $ for all $ t \in \gf_q^*$.
  \end{itemize}
\end{proposition}


\begin{proof}
  For $t = 0$, we have 
  $$
  |I_f(0)| = 1 +  \displaystyle{\frac{2^m - 1}{\gcd(2^m-1,2^i+1)}} .
  $$ 
  From the well-known fact (e.g.~\cite[Lemma 11.1]{McEliece87}) that
  \begin{equation*}
    \gcd(2^m-1, 2^i + 1) = \left\{ \begin{array}{ll}
      1 & \textrm{ if $m/d$ is odd,} \\
      2^d + 1 & \textrm{ if $m/d$ is even,}
    \end{array}\right.
  \end{equation*}
the assertion on $|I_f(0)|$ follows.


For $t \in \gf_q^*$, by definition, we have
  \begin{eqnarray*}
    |I_f(t)| & = & | \{f(x) + tx: x \in \gf_q\}| \\
    & = & |\gf_q| - | \{c \in \gf_q^*: f(x) + tx + c \textrm{ has no root in $\gf_q$} \} | \\
    & = & q - N_0' .
  \end{eqnarray*}
  To make use of Theorem~\ref{thm-blu}, we transform $f(x) + tx + c$ following the steps in \cite{Blu04}. Since $t \ne 0$ and $c \ne 0$, let $x = \displaystyle{\frac{c}{t} z}$, then
  \begin{eqnarray*}
    \lefteqn{f(x) + tx + c} \\
    & = & x^{2^i + 1} + tx + c \\
    & = & \frac{c^{2^i +1}}{t^{2^i+1}} \left( z^{2^i+1} + \frac{t^{2^i+1}}{c^{2^i}} z + \frac{t^{2^i+1}}{c^{2^i}} \right).
  \end{eqnarray*}
 
  Since
  $$
  \left\{ \frac{t^{2^i + 1}}{c^{2^i}} : c \in \gf_q^* \right\} = \gf_q^*,
  $$
  we have $N_0' = N_0$, where $N_0$ denotes the number of $b \in \gf_q^*$ such that $x^{2^i+1} + bx + b$ has no root in $\gf_q$. The conclusion then follows from Theorem~\ref{thm-blu}.
 \end{proof}

Proposition \ref{pro-issize} shows that the smallest Kakeya sets constructed using Gold power functions are achieved
with $i =m/2$ for an even $m$, and $i=0$ for an odd $m$. 
The discussion below shows that the choice $i=m/2$ implies a better upper bound on Kakeya sets compared with the one given in Theorem  \ref{thm-levbound}. 
The idea to use $f(x) = x^{2^{m/2}+1}$ to improve the bound in Theorem
\ref{thm-levbound} appears in \cite{kyureg-wang-wcc}, and was independently suggested by David Speyer in \cite{mathoverflow}.
Observe that $f(x) = x^3$ chosen in~\cite{KLSS11} to prove the bound for $m$ even is the Gold power function with $i = 1$ and $d =1$. 


 

When $m/d$ is odd, $|I_f(0)| = q$, and therefore the  bound obtained by the Gold power functions cannot be good for large $n$. However, for small values of $n$, it is better than the one of 
Theorem \ref{thm-levbound} \cite{kyureg-wang-wcc}.   


Next  consider the function $f(x) = x^{2^{m/2}+1}$. In particular, we show that this function yields a better upper bound on the minimum size of Kakeya sets in $\gf_q^n$ when $q$ is an even power
of $2$. First we present a direct proof for the size of the sets $\{ x^{2^{m/2}+1} +tx \,:\, x \in \gf_q \}, t \in \gf_q$. 

\begin{theorem}\label{meven}
Let $m$ be an even integer.  Then
$$
|I(0)| := |\{ x^{2^{m/2}+1}  \,:\, x \in \gf_q \}| = 2^{m/2},
$$
 and 
$$
|I(t)| := |\{ x^{2^{m/2}+1} +tx \,:\, x \in \gf_q \}| = \frac{2^m + 2^{m/2}}{2} 
$$ 
for all $t \in \gf_q^*$.

\end{theorem}

\begin{proof}
The identity on $I(0)$ is clear, since the  image set of the function $x \mapsto x^{2^{m/2}+1}$ is $\mathbb{F}_{2^{m/2}}$.  Let $t \in \gf_q^*$. Note  that $|I(t)| =|I(1)|$. Indeed, there is $s \in \gf_q$, such that $t = s^{2^{m/2}}$ and then
$$
x^{2^{m/2}+1} +tx = s^{2^{m/2}+1}\cdot \left( (x/s)^{2^{m/2}+1} + (x/s)\right).
$$ 
Hence it is enough to compute $I(1)$. Let $Tr(x) = x^{2^{m/2}}+x$ be the trace map from $\gf_q$ onto its subfield  $\mathbb{F}_{2^{m/2}}$. Recall that $Tr$
is a $\mathbb{F}_{2^{m/2}}$-linear surjective map. 

Set $g(x) = x^{2^{m/2}+1} +x$. If $y,z \in \gf_q$ are such that
$$
g(z) = z^{2^{m/2}+1} +z = y^{2^{m/2}+1} +y = g(y),
$$
then $z = y + u$ for some $u \in \mathbb{F}_{2^{m/2}}$, since the image set of the function $x \mapsto x^{2^{m/2}+1}$ is $\mathbb{F}_{2^{m/2}}$.
Further, for any $u \in \mathbb{F}_{2^{m/2}}$
$$
g(y+u) = (y + u)^{2^{m/2}+1} +y+u = y^{2^{m/2}+1} +y + u(y^{2^{m/2}}+y) + u^2 + u.
$$
Hence, $g(y) = g(y+u)$ if and only if
$$
 u(y^{2^{m/2}}+y) + u^2 + u = u(Tr(y)+ u+1)=0.
$$
Consequently, two distinct elements $y$ and $z$ share the same image under the function $g$ if and only $Tr(y) \ne 1$ and $z = y + Tr(y)+1$. 
This shows that $g$ is injective on  the set $\mathcal{O}$ of elements from $\gf_q$ having trace 1, and 2-to-1 on  $\gf_q \setminus \mathcal{O}$,
completing the proof.
\end{proof}

\begin{theorem}
Let $q=2^m$ with $m$ even and $n \geq 1$. There is a Kakeya set $K \subset \gf_q^n$ such that
$$
|K| < \frac{2q}{q + \sqrt{q} - 2} \left( \frac{q + \sqrt{q}}{2} \right)^n.
$$
\end{theorem}
\begin{proof}
The statement follows from (\ref{eqn-kssize}) and Theorem \ref{meven}.
\end{proof}




\section{On Kakeya sets constructed using the function $x \mapsto x^4+x^3$}

In this section we obtain an upper bound on the minimum size of Kakeya sets constructed using
the function $x \mapsto  x^4+x^3$ on $\gf_q$. For every $t \in \gf_q$, let $g_t : \gf_q \to \gf_q$ be defined by
$$
g_t(x) := x^4 +x^3 + tx.
$$
Next we study the image sets of functions $g_t(x)$. Given $y \in \gf_q$, let $g_t^{-1}(y)$ be the set of preimages of $y$,
that is
$$
g_t^{-1}(y) := \{ x \in \gf_q \,|\, g_t(x) =y \}.
$$
Further, for any integer $k \geq 0$ put $\omega_t(k)$ to denote the number of elements in $\gf_q$ having exactly $k$ preimages
under $g_t(x)$, that is
$$
\omega_t(k) := |\{ y \in \gf_q \,:\, |g_t^{-1}(y)| = k \}|.
$$
Note that  $\omega_t(k) =0$ for all $k \geq 5$, since the degree of $g_t(x)$ is 4. The next lemma establishes the value of
$\omega_t(1)$:

\begin{lemma}\label{omega-1}
Let $q = 2^m$ and $t \in \gf_q^*$. Then
\begin{itemize}
\item if $m$ is odd
$$
\omega_t(1) = \left\{ \begin{array}{ll} \vspace*{0.2cm}
  \frac{q+1}{3} & \mbox{ if } Tr(t) =0  \\
  \frac{q+4}{3}  & \mbox{ if } Tr(t) = 1
\end{array} \right .
$$
\item if $m$ is even
$$
\omega_t(1) = \left\{ \begin{array}{ll} \vspace*{0.2cm}
  \frac{q-1}{3} & \mbox{ if } Tr(t)=0 \\
  \frac{q+2}{3}  & \mbox{ if } Tr(t) =1.
\end{array} \right .
$$
\end{itemize}



\end{lemma}

\begin{proof}
Let $y \in \gf_q$ and $y \ne t^2$.
Then $t^{2^{m-1}}$ is not a solution of the following equation 
$$
h_{t,y}(x):= g_t(x) + y = x^4 +x^3 +tx +y =0.
$$
Observe that the number of the  solutions for the above equation 
is equal to the one of
$$
(t^2+y)x^4 +t^{2^{m-1}}x^2 + x +1 = x^4\cdot  h_{t,y}\left(\frac{1}{x} + t^{2^{m-1}} \right) =0.
$$
Hence  either $\omega_t(1)$ or $\omega_t(1)-1$ is equal to the number of elements $y \in \gf_q$ such that the affine polynomial
\begin{equation}\label{affine}
(t^2+y)x^4 +t^{2^{m-1}}x^2 + x +1
\end{equation}
has exactly one zero in $\gf_q$, depending on the number of preimages of $g_t(x)$ for $t^2$. Equation (\ref{affine}) has exactly 1 solution if and only if the linearized
polynomial 
$$
(t^2+y)x^4 +t^{2^{m-1}}x^2 + x
$$
has no non-trivial zeros, or equivalently
\begin{equation}\label{equat-bl}
u(x) := (t^2+y)x^3 +t^{2^{m-1}}x + 1
\end{equation}
has no zeroes. 

Since  $t^2+y \ne 0$, the number of zeroes of $u(x)$ is equal to the one of 
$$
\frac{1}{t^2+y} \cdot u\left(\frac{1}{t^{2^{m-1}}} z\right) = \frac{1}{t^{2^{m-1} + 1}} \left( z^3 + \frac{t^{2^{m-1} + 1}}{t^2 + y} z + \frac{t^{2^{m-1} + 1}}{t^2 + y} \right).
$$
Note that 
$$
\left\{ \frac{t^{2^{m-1} + 1}}{t^2 + y} : y \in \gf_q, y \ne t^2 \right\} = \gf_q^*.
$$
Hence by Theorem \ref{thm-blu} with $i=1$,  the number of elements $y \in \gf_q, y \ne t^2$, such that
(\ref{equat-bl}) has no zeros is
$$
\left\{ \begin{array}{ll} \vspace*{0.2cm}
  \frac{q+1}{3} & \mbox{ if $m$ is odd} \\ 
   \frac{q-1}{3} & \mbox{ if $m$ is even.}
\end{array} \right .
$$
To complete the proof, it remains to consider $y = t^2$. In this case
$$
g_t(x) + y = x^4 +x^3 +tx +t^2 = (x^2+t)(x^2+x+t),
$$
and therefore $g_t(x)+t^2$ has exactly one solution if $Tr(t) =1$ and exactly 3 solutions if $Tr(t)=0$.

\end{proof}

\begin{lemma}\label{omega-3}
Let $q = 2^m$ and $t \in \gf_q^*$. Then
$$
\omega_t(3) = \left\{ \begin{array}{ll} \vspace*{0.2cm}
  1  & \mbox{ if } Tr(t) =0  \\
  0  & \mbox{ if } Tr(t) = 1.
\end{array} \right .
$$
\end{lemma}
\begin{proof}
The proof of Lemma \ref{omega-1} shows that for any $y \ne t^2$, the number of solutions for $h_{t,y}(x) =0$ is a power of 2.
Hence only $t^2$ may have 3 preimages under $g_t(x)$, which is the case if and only if $Tr(t)=0$.
\end{proof}


The next lemma describes the behavior of the function $x^4+x^3$:
\begin{lemma}\label{omega0}
Let $q = 2^m$ and $k\geq 1$ an integer. Then
\begin{itemize}
\item if $m$ is odd
$$
\omega_0(k) = \left\{ \begin{array}{ll} \vspace*{0.2cm}
  q/2 & \mbox{ if } k=2  \\
   0  & \mbox{  otherwise,}
\end{array} \right .
$$
in particular, the cardinality of $I(0) := \{ x^4+x^3 : x \in \gf_q \}$ is $q/2$.
\item if $m$ is even
$$
\omega_0(k) = \left\{ \begin{array}{ll} \vspace*{0.2cm}
  1 & \mbox{ if } k=2  \\ \vspace*{0.2cm}
  \frac{2(q-1)}{3} & \mbox{ if } k=1 \\ \vspace*{0.2cm}
   \frac{(q-4)}{12} & \mbox{ if } k=4 \\ \vspace*{0.2cm}
  0  & \mbox{ otherwise.}
\end{array} \right .
$$
\end{itemize}
\end{lemma}
\begin{proof}
Note that $x^4+x^3 =0$ has 2 solutions.
Let $y \in \gf_q^*$. Then the steps of the proof for Lemma \ref{omega-1} show that the number of solutions of 
$$
x^4+x^3 +y =0
$$
is equal to the one of the affine polynomial
$$
a_y(x):= yx^4  + x +1.
$$
If the set of zeros of $a_y(x)$ is not empty, then the number of zeros of $a_y(x)$ is equal to the one of
the linearized polynomial 
$$l_y(x)  := yx^4 +x.
$$
If $m$ is odd, then $l_y(x)$ has exactly 2 zeroes for every $y \ne 0$, implying the statement for $m$ odd.
If $m$ is even, then $l_y(x)$ has only the trivial zero if $y$ is a non-cube in $\gf_q$, and otherwise
it has 4 zeroes. To complete the proof, it remains to recall that the number of non-cubes in $\gf_q$ is
$2(q-1)/3$.
\end{proof}


Lemmas \ref{omega-1}--\ref{omega0} yield the following upper bound for the size of the image sets of the considered
functions: 


\begin{theorem}\label{thm-new}
Let $q = 2^m$ with $m$ odd. For $t \in \gf_q$ set $I(t) := \{ x^4+x^3
+ tx : x \in \gf_q \}$. Let $v$ be the number of pairs $x,z\in\gf_q$
with $x^2+zx=z^3+z^2+t$. Then for $t\ne0$
\[
  \lvert I(t)\rvert=\frac{5}{8}q+\frac{q+1-v}{8}+\frac{\delta}{2}<
\frac{5}{8}q+\frac{2\sqrt{q}+5}{8},
\]
where $\delta=0$ or $1$ if $Tr(t)=0$ or $1$, respectively.
\end{theorem}
\begin{proof}
Note that
\[
\lvert I(t)\rvert = \omega_t(1) + \omega_t(2) + \omega_t(3) + \omega_t(4)
\]
and
\[
q = \omega_t(1) + 2 \cdot \omega_t(2) + 3\cdot \omega_t(3) + 4\cdot \omega_t(4).
\]
Let $v'$ be the number of distinct elements $x,y\in \gf_q$ with
$x^4+x^3+tx=y^4+y^3+ty$.
Clearly
\[
v' = 2\omega_t(2) + 6\omega_t(3) + 12\omega_t(4),
\]
hence
\[
\lvert I(t)\rvert=\frac{5q - v' + 3\omega_t(1) - \omega_t(3)}{8}.
\]
Setting $y=x+z$, we see that $x^4+x^3+tx=y^4+y^3+ty$ for $x\ne y$ is
equivalent to $x^2+zx=z^3+z^2+t$ for $z\ne0$. However, for $z=0$ this
latter equation has a unique solution, so $v=v'+1$.

Together with Lemmas \ref{omega-1}--\ref{omega0} we see that the size
of $I(t)$ is as claimed. The inequality follows from the Hasse bound for
points on elliptic curves, which in our case says that $\lvert
v-q\rvert\le 2\sqrt{q}$. (Note that the projective completion of the
curve $X^2+ZX=X^3+X^2+t$ has a unique point at infinity.)
\end{proof}


The bound obtained in Theorem \ref{thm-new} can be stated also as follows
\begin{equation}\label{int-part}
 \lvert I(t)\rvert \leq \left\lfloor \frac{5}{8}q+\frac{2\sqrt{q}+5}{8} \right\rfloor,
\end{equation}
since $\lvert I(t)\rvert$ is an integer. Our numerical calculations show that for odd $1 \leq m \leq 13$ bound (\ref{int-part}) is sharp, 
that is for these $m$  there are elements $t \in \mathbb{F}_{2^m}$ for which equality holds in (\ref{int-part}). 


\begin{theorem}
Let $q=2^m$ with $m$ odd and $n \geq 1$. There is a Kakeya set $K \subset \gf_q^n$ such that
$$
|K| < \frac{8q}{5q +2\sqrt{q}-3} \left( \frac{5q+ 2\sqrt{q}+5}{8} \right)^n.
$$
\end{theorem}

\begin{proof}
The statement follows from (\ref{eqn-kssize}) and Theorem \ref{thm-new}.
\end{proof}


%\section*{Acknowledgments}


\begin{thebibliography}{10}

\bibitem{Blu04}
A.~W. Bluher.
\newblock On {$x^{q+1}+ax+b$}.
\newblock {\em Finite Fields Appl.}, 10(3):285--305, 2004.

\bibitem{Dvir08}
Z.~Dvir.
\newblock On the size of {K}akeya sets in finite fields.
\newblock {\em J. Amer. Math. Soc.}, 22(4):1093--1097, 2009.

\bibitem{Dvir12}
Z.~Dvir.
\newblock Incidence theorems and their applications.
\newblock {\em arXiv preprint arXiv:1208.5073}, 2012.

\bibitem{DKSS09}
Z.~Dvir, S.~Kopparty, S.~Saraf, and M.~Sudan.
\newblock Extensions to the method of multiplicities, with applications to
  {K}akeya sets and mergers.
\newblock In {\em 2009 50th {A}nnual {IEEE} {S}ymposium on {F}oundations of
  {C}omputer {S}cience ({FOCS} 2009)}, pages 181--190. IEEE Computer Soc., Los
  Alamitos, CA, 2009.

\bibitem{KLSS11}
S.~Kopparty, V.~F. Lev, S.~Saraf, and M.~Sudan.
\newblock Kakeya-type sets in finite vector spaces.
\newblock {\em J. Algebraic Combin.}, 34(3):337--355, 2011.

\bibitem{kyureg-wang-wcc}
G.~Kyureghyan and Q.~Wang.
\newblock An upper bound on the size of kakeya sets in finite vector spaces.
\newblock {\em to appear in proceedings of WCC 2013}.

\bibitem{mathoverflow}
V.~F. Lev.
\newblock A mixing property for finite fields of characteristic 2.
\newblock http://mathoverflow.net/questions/102751/a-mixing-property-for-finite-fields-of-characteristic-2, 2012. 

\bibitem{McEliece87}
R.~J. McEliece.
\newblock {\em Finite fields for computer scientists and engineers}.
\newblock The Kluwer International Series in Engineering and Computer Science,
  23. Kluwer Academic Publishers, Boston, MA, 1987.

\bibitem{MT04}
G.~Mockenhaupt and T.~Tao.
\newblock Restriction and {K}akeya phenomena for finite fields.
\newblock {\em Duke Math. J.}, 121(1):35--74, 2004.

\bibitem{SS08}
S.~Saraf and M.~Sudan.
\newblock An improved lower bound on the size of {K}akeya sets over finite
  fields.
\newblock {\em Anal. PDE}, 1(3):375--379, 2008.

\bibitem{wolff99}
T.~Wolff.
\newblock Recent work connected with the {K}akeya problem.
\newblock In {\em Prospects in mathematics ({P}rinceton, {NJ}, 1996)}, pages
  129--162. Amer. Math. Soc., Providence, RI, 1999.

\end{thebibliography}




%\bibliographystyle{abbrv}


%\bibliography{kakeya-sets-ejc}



\end{document}



