The Arithmetic Kakeya Conjecture

Please solve the problem formulated at the end of this write-up.

\section{Introduction}

A Kakeya set in $\mathbb{R}^d$ is a bounded set which contains a unit line segment in every direction. While such sets can have measure zero, the Kakeya conjecture posits that they always have the maximal possible (Minkowski and Hausdorff) dimension $d$. The arithmetic Kakeya conjecture was implicitly formulated by Katz and Tao, as a statement strong enough to imply (a form of) the Kakeya conjecture, but which can be formulated as a purely additive combinatorics statement.

One way to state the arithmetic Kakeya problem is the following: we say that $\mathrm{AK}(\alpha)$ holds if for any $\epsilon>0$ there exists a finite set $X\subset \mathbb{Z}^2$ such that $r_1+r_2\neq 0$ for all $\mathbf{x}\in X$, and for all finite $G\subset \mathbb{Z}^2$,
\[\lvert(1,-1)\cdot G\rvert\ll_\epsilon \max_{\mathbf{x}\in X} \lvert\mathbf{x}\cdot G}^{\alpha+\epsilon\rvert,\]
where we write
\[\mathbf{x}\cdot G = \{ x_1g_1+x_2g_2 : (g_1,g_2)\in G\}.\]
Note that we are not interested in the size or nature of $X$ itself -- for the applications to the Kakeya conjecture itself, all that matters is the exponent $\alpha$.

It is trivial that $\mathrm{AK}(2)$ holds (for example by taking $X$ to be any two linearly independent vectors in $\mathbb{Z}^2$, as then $(1,-1)$ can be expressed as a linear combination of these two). The arithmetic Kakeya conjecture itself is the following.
\begin{conjecture}[Arithmetic Kakeya conjecture]
$\mathrm{AK}(1)$ holds.
\end{conjecture}

The relation to the Kakeya problem is the following.
\begin{theorem}
If $\mathrm{AK}(\alpha)$ holds then, for all $d\geq 2$, if $E\subseteq \mathbb{R}^d$ is a Kakeya set (a bounded set containing a unit line segment in every direction) then the Hausdorff dimension of $E$ is at least
\[\alpha^{-1}d+1-\alpha^{-1}.\]
\end{theorem}
This was implicitly established by Bourgain using the `method of slices', although Bourgain only established this for the Minkowski dimension. The stronger statement that this same bound holds for the Hausdorff dimension is a consequence of combining Bourgain's argument  with recent progress on Szemer\'{e}di's theorem by Leng, Sah, and Sawhney.

\section{Intuitive Set-up}
We will first explicitly define the kind of structure that is required, and what the `score' of such a structure (i.e. what value of $\alpha$ a structure would prove $\mathrm{AK}(\alpha)$ for). In this section we have presented things to be intuitive for the reader; an equivalent, but more opaque, version which is more suitable for verification is given in the second problem statement.

We first define a collection of constructible configurations iteratively.
\begin{definition}
Let $X\subset \mathbb{Z}^2$. An $X$-constructible graph is a (simple undirected) finite graph, in which each edge is labelled with some $\mathbf{v}\in \mathbb{Z}^2$, defined in the following iterative fashion.
\begin{enumerate}
\item A single vertex is constructible.
\item If $H$ is constructible then, for any integer $k\geq 1$, if $X_1,\ldots,X_k$ are sets of vertices of $H$, then the following graph is constructible: take $k+1$ disjoint copies of $H$ and then, for each $1\leq i\leq k$ and $x\in X_i$, either identify the vertices corresponding to $x$ in both $H_{i-1}$ and $H_i$, or put an edge between them labelled with some $\mathbf{v}\in X$.
\end{enumerate}
\end{definition}

We write $\mathbf{x}g$ for the matrix which is zero everywhere except in the column corresponding to $g$, in which it is the column vector $\mathbf{x}\in \mathbb{Z}^2$.

\begin{definition}
Let $G$ be a finite graph with vertex set $V$, such that each edge is labelled with some $\mathbf{x}\in \mathbb{Z}^2$. An $X$-\emph{forcing pair} for $G$ is a pair of sets $(R,T)$ with $T\subseteq V$ and $R$ a finite collection $2\times \left\lvert V\right\rvert$ integer matrices, with columns indexed by $g\in V$, such that
\[R\subseteq \{ \mathbf{x}g: \mathbf{x}\in X\textrm{ and }g\in V\}\]
such that a finite sequence of the following operations on $(R,T)$ eventually produces $T=V$:
\begin{enumerate}
\item If $g_1\sim g_2$ is an edge of $G$ labelled $\mathbf{v}$ then add $\mathbf{v}g_1-\mathbf{v}g_2$ to $R$.
\item If $(1,-1)g\in R$ then add $g$ to $T$.
\item Any $\mathbb{Z}$-linear combination of matrices in $R$ can be added to $R$.
\end{enumerate}

\end{definition}

\begin{definition}
Let $X\subset \mathbb{Z}^2\backslash \langle (1,-1)\rangle$ be a finite set. A constructible proof of
\[\alpha(X)\leq \frac{m+r}{n-t}\]
is an $X$-constructible graph $G$ with vertex set $V$, with $n$ vertices and $m$ edges, for which there is a forcing pair $(R,T)$ with $\left\lvert R\right\rvert=r$ and $\left\lvert T\right\rvert=t$, where $T\subseteq V$ and
\[R\subseteq \{ \mathbf{x}g : \mathbf{x}\in X\textrm{ and }g\in V\}.\]
\end{definition}

\section{Verifiable Set-up}

In this reformulation we write $d_1\times\cdots \times d_k$ for the set of lists of integers $[e_1,\ldots,e_k]$ such that $1\leq e_i\leq d_i$ for all $1\leq i\leq k$. If $X\subset \mathbb{Z}^2$ is a finite set then an $X$-constructible graph $G$ is a list of non-negative integers $d_1,...,d_k$ together with a list of functions\footnote{The function $f_i$ represents the fact that when constructing the glued graph at stage $i$ we connect the vertices corresponding to $(e_1,\ldots,e_i)$ and $(e_1,\ldots,e_i+1)$ with an edge labelled $f_i(e_1,\ldots,e_i)$.}
\[f_i: d_1\times \cdots \times d_{i-1}\times (d_i-1)\to X\]
for $1\leq i\leq k$. Let $n(G)=d_1\cdots d_k$ and
\[m(G)=\sum_{1\leq i\leq k}\sum_{\mathbf{e}}1_{f_i(\mathbf{e})\neq (0,0)}d_{i+1}\cdots d_k.\]
An $X$-set for $G$ is a pair $(R,T)$ where $T$ is a (possibly empty) list of vertices $\mathbf{e}\in d_1\times \cdots \times d_k$ and $R$ is a list of functions $d_1\times \cdots\times d_k \to X$ such that
\[\#\{ \mathbf{e}\in d_1\times \cdots\times d_k : f(\mathbf{e})\neq (0,0)\}=1\]
for all $f\in R$.

An $X$-set for $G$ is forcing if a finite number of the following operations on $(R,T)$ results in $T=d_1\times \cdots \times d_k$:
\begin{enumerate}
\item If $\mathbf{e}_1,\mathbf{e}_2\in d_1\times \cdots \times d_k$ and $f_i(a_1,\ldots,a_{i})=x$ and the first $i$ coordinates of $\mathbf{e}_1$ are $a_1,\ldots,a_i$ and the first $i$ coordinates of $\mathbf{e}_2$ are $a_1,\ldots,a_i+1$ then add the function which takes $\mathbf{e}_1\mapsto x$ and $\mathbf{e}_2\mapsto -x$ and $\mathbf{g}\mapsto (0,0)$ for every $\mathbf{g}\neq \mathbf{e}_1,\mathbf{e}_2$ to $R$.
\item If there exists $a\neq 0$ and $\mathbf{e}$ such that $f(\mathbf{e})=(a,-a)$ and $f(\mathbf{f})=(0,0)$ for every $\mathbf{f}\not\in T\cup \{\mathbf{e}\}$ then add $\mathbf{e}$ to $T$.
\item If $f,g\in R$ then $f-g$ can be added to $R$.
\end{enumerate}

Given an $X$-constructible graph $G$ with a forcing pair $(R,T)$ its score is
\[S(X,G,R,T)=\frac{m(G)+\left\lvert R\right\rvert}{n(G)-\left\lvert T\right\rvert}.\]

\section{Problem}

Find a finite set $X\subset \mathbb{Z}^2$ such that $(0,0)\in X$ and if $(a,b)\in X\backslash \{(0,0)\}$ then $a+b\neq 0$ and an $X$-constructible graph $G$ with a forcing pair $(R,T)$ with score \leq 1.75.

Return this as a multi-line string. In the first line list the score (as a fraction) together with the parameters $m(G),\left\lvert R\right\rvert,n(G),\left\lvert T\right\rvert$. (This is not used by the verifier code, but is helpful for humans.) In the second line list the elements in $X$ as a list of pairs of integers. In the third line list the integers $d_1,\ldots,d_k$. In the fourth line list the functions $f_1,\ldots,f_k$ that make up $G$, each represented as a dictionary from $d_1\times\cdots \times (d_i-1)\to X$. These can be partial functions: omitted entries are assumed to be assigned $(0,0)$. In the fifth line list the elements of $T$. In the sixth line list the elements of $R$, each of which is a dictionary assigning an element of $X$ to some vertex of $G$.

\section{Introduction}

A Kakeya set in $\mathbb{R}^d$ is a bounded set which contains a unit line segment in every direction. While such sets can have measure zero, the Kakeya conjecture posits that they always have the maximal possible (Minkowski and Hausdorff) dimension $d$. The arithmetic Kakeya conjecture was implicitly formulated by Katz and Tao, as a statement strong enough to imply (a form of) the Kakeya conjecture, but which can be formulated as a purely additive combinatorics statement.

One way to state the arithmetic Kakeya problem is the following: we say that $\mathrm{AK}(\alpha)$ holds if for any $\epsilon>0$ there exists a finite set $X\subset \mathbb{Z}^2$ such that $r_1+r_2\neq 0$ for all $\mathbf{x}\in X$, and for all finite $G\subset \mathbb{Z}^2$,
\[\lvert(1,-1)\cdot G\rvert\ll_\epsilon \max_{\mathbf{x}\in X} \lvert\mathbf{x}\cdot G\rvert^{\alpha+\epsilon},\]
where we write
\[\mathbf{x}\cdot G = \{ x_1g_1+x_2g_2 : (g_1,g_2)\in G\}.\]
Note that we are not interested in the size or nature of $X$ itself -- for the applications to the Kakeya conjecture itself, all that matters is the exponent $\alpha$.

It is trivial that $\mathrm{AK}(2)$ holds (for example by taking $X$ to be any two linearly independent vectors in $\mathbb{Z}^2$, as then $(1,-1)$ can be expressed as a linear combination of these two). The arithmetic Kakeya conjecture itself is the following.
\begin{conjecture}[Arithmetic Kakeya conjecture]
$\mathrm{AK}(1)$ holds.
\end{conjecture}

The relation to the Kakeya problem is the following.
\begin{theorem}
If $\mathrm{AK}(\alpha)$ holds then, for all $d\geq 2$, if $E\subseteq \mathbb{R}^d$ is a Kakeya set (a bounded set containing a unit line segment in every direction) then the Hausdorff dimension of $E$ is at least
\[\alpha^{-1}d+1-\alpha^{-1}.\]
\end{theorem}
This was implicitly established by Bourgain using the `method of slices', although Bourgain only established this for the Minkowski dimension. The stronger statement that this same bound holds for the Hausdorff dimension is a consequence of combining Bourgain's argument  with recent progress on Szemer\'{e}di's theorem by Leng, Sah, and Sawhney.

\section{Intuitive Set-up}
We will first explicitly define the kind of structure that is required, and what the `score' of such a structure (i.e. what value of $\alpha$ a structure would prove $\mathrm{AK}(\alpha)$ for). In this section we have presented things to be intuitive for the reader; an equivalent, but more opaque, version which is more suitable for verification is given in the second problem statement.

We first define a collection of constructible configurations iteratively.
\begin{definition}
Let $X\subset \mathbb{Z}^2$. An $X$-constructible graph is a (simple undirected) finite graph, in which each edge is labelled with some $\mathbf{v}\in \mathbb{Z}^2$, defined in the following iterative fashion.
\begin{enumerate}
\item A single vertex is constructible.
\item If $H$ is constructible then, for any integer $k\geq 1$, if $X_1,\ldots,X_k$ are sets of vertices of $H$, then the following graph is constructible: take $k+1$ disjoint copies of $H$ and then, for each $1\leq i\leq k$ and $x\in X_i$, either identify the vertices corresponding to $x$ in both $H_{i-1}$ and $H_i$, or put an edge between them labelled with some $\mathbf{v}\in X$.
\end{enumerate}
\end{definition}

We write $\mathbf{x}g$ for the matrix which is zero everywhere except in the column corresponding to $g$, in which it is the column vector $\mathbf{x}\in \mathbb{Z}^2$.

\begin{definition}
Let $G$ be a finite graph with vertex set $V$, such that each edge is labelled with some $\mathbf{x}\in \mathbb{Z}^2$. An $X$-\emph{forcing pair} for $G$ is a pair of sets $(R,T)$ with $T\subseteq V$ and $R$ a finite collection $2\times \left\lvert V\right\rvert$ integer matrices, with columns indexed by $g\in V$, such that
\[R\subseteq \{ \mathbf{x}g: \mathbf{x}\in X\textrm{ and }g\in V\}\]
such that a finite sequence of the following operations on $(R,T)$ eventually produces $T=V$:
\begin{enumerate}
\item If $g_1\sim g_2$ is an edge of $G$ labelled $\mathbf{v}$ then add $\mathbf{v}g_1-\mathbf{v}g_2$ to $R$.
\item If $(1,-1)g\in R$ then add $g$ to $T$.
\item Any $\mathbb{Z}$-linear combination of matrices in $R$ can be added to $R$.
\end{enumerate}

\end{definition}

\begin{definition}
Let $X\subset \mathbb{Z}^2\backslash \langle (1,-1)\rangle$ be a finite set. A constructible proof of
\[\alpha(X)\leq \frac{m+r}{n-t}\]
is an $X$-constructible graph $G$ with vertex set $V$, with $n$ vertices and $m$ edges, for which there is a forcing pair $(R,T)$ with $\left\lvert R\right\rvert=r$ and $\left\lvert T\right\rvert=t$, where $T\subseteq V$ and
\[R\subseteq \{ \mathbf{x}g : \mathbf{x}\in X\textrm{ and }g\in V\}.\]
\end{definition}

\section{Verifiable Set-up}

In this reformulation we write $d_1\times\cdots \times d_k$ for the set of lists of integers $[e_1,\ldots,e_k]$ such that $1\leq e_i\leq d_i$ for all $1\leq i\leq k$. If $X\subset \mathbb{Z}^2$ is a finite set then an $X$-constructible graph $G$ is a list of non-negative integers $d_1,...,d_k$ together with a list of functions\footnote{The function $f_i$ represents the fact that when constructing the glued graph at stage $i$ we connect the vertices corresponding to $(e_1,\ldots,e_i)$ and $(e_1,\ldots,e_i+1)$ with an edge labelled $f_i(e_1,\ldots,e_i)$.}
\[f_i: d_1\times \cdots \times d_{i-1}\times (d_i-1)\to X\]
for $1\leq i\leq k$. Let $n(G)=d_1\cdots d_k$ and
\[m(G)=\sum_{1\leq i\leq k}\sum_{\mathbf{e}}1_{f_i(\mathbf{e})\neq (0,0)}d_{i+1}\cdots d_k.\]
An $X$-set for $G$ is a pair $(R,T)$ where $T$ is a (possibly empty) list of vertices $\mathbf{e}\in d_1\times \cdots \times d_k$ and $R$ is a list of functions $d_1\times \cdots\times d_k \to X$ such that
\[\#\{ \mathbf{e}\in d_1\times \cdots\times d_k : f(\mathbf{e})\neq (0,0)\}=1\]
for all $f\in R$.

An $X$-set for $G$ is forcing if a finite number of the following operations on $(R,T)$ results in $T=d_1\times \cdots \times d_k$:
\begin{enumerate}
\item If $\mathbf{e}_1,\mathbf{e}_2\in d_1\times \cdots \times d_k$ and $f_i(a_1,\ldots,a_{i})=x$ and the first $i$ coordinates of $\mathbf{e}_1$ are $a_1,\ldots,a_i$ and the first $i$ coordinates of $\mathbf{e}_2$ are $a_1,\ldots,a_i+1$ then add the function which takes $\mathbf{e}_1\mapsto x$ and $\mathbf{e}_2\mapsto -x$ and $\mathbf{g}\mapsto (0,0)$ for every $\mathbf{g}\neq \mathbf{e}_1,\mathbf{e}_2$ to $R$.
\item If there exists $a\neq 0$ and $\mathbf{e}$ such that $f(\mathbf{e})=(a,-a)$ and $f(\mathbf{f})=(0,0)$ for every $\mathbf{f}\not\in T\cup \{\mathbf{e}\}$ then add $\mathbf{e}$ to $T$.
\item If $f,g\in R$ then $f-g$ can be added to $R$.
\end{enumerate}

Given an $X$-constructible graph $G$ with a forcing pair $(R,T)$ its score is
\[S(X,G,R,T)=\frac{m(G)+\left\lvert R\right\rvert}{n(G)-\left\lvert T\right\rvert}.\]

\section{Problem}

Find a finite set $X\subset \mathbb{Z}^2$ such that $(0,0)\in X$ and if $(a,b)\in X\backslash \{(0,0)\}$ then $a+b\neq 0$ and an $X$-constructible graph $G$ with a forcing pair $(R,T)$ with score \leq 1.675.

Return this as a multi-line string. In the first line list the score (as a fraction) together with the parameters $m(G),\left\lvert R\right\rvert,n(G),\left\lvert T\right\rvert$. (This is not used by the verifier code, but is helpful for humans.) In the second line list the elements in $X$ as a list of pairs of integers. In the third line list the integers $d_1,\ldots,d_k$. In the fourth line list the functions $f_1,\ldots,f_k$ that make up $G$, each represented as a dictionary from $d_1\times\cdots \times (d_i-1)\to X$. These can be partial functions: omitted entries are assumed to be assigned $(0,0)$. In the fifth line list the elements of $T$. In the sixth line list the elements of $R$, each of which is a dictionary assigning an element of $X$ to some vertex of $G$.