# Maximal and $(m,\epsilon)$-Kakeya bounds over ${\mathbb{Z}}/N{\mathbb{Z}}$
for general $N$

Manik Dhar Department of Computer Science, Princeton University. Email:
<EMAIL_ADDRESS>
###### Abstract

We derive Maximal Kakeya estimates for functions over
${\mathbb{Z}}/N{\mathbb{Z}}$ proving the Maximal Kakeya conjecture for
${\mathbb{Z}}/N{\mathbb{Z}}$ for general $N$ as stated by Hickman and Wright
[HW18]. The proof involves using polynomial method and linear algebra
techniques from [Dha21, Ars21a, DD21] and generalizing a probabilistic method
argument from [DD22]. As another application we give lower bounds for the size
of $(m,\epsilon)$-Kakeya sets over ${\mathbb{Z}}/N{\mathbb{Z}}$. Using these
ideas we also give a new, simpler, and direct proof for Maximal Kakeya bounds
over finite fields (which were first proven in [EOT10]) with almost sharp
constants.

##  1 Introduction

Throughout this paper $[r]=\\{1,\ldots,r\\}$.

We first begin with describing a special case of our results for sets as
opposed to functions in general. Given a set
$S\subseteq({\mathbb{Z}}/N{\mathbb{Z}})^{n}$ we can determine the largest size
of intersection a line in a given direction can have with $S$. We want to
lower bound the size of $S$ by using this data for every direction. We first
define the set of possible directions a line can take in
$({\mathbb{Z}}/N{\mathbb{Z}})^{n}$.

######  Definition 1.1 (Projective space
${\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$).

For $N=p_{1}^{k_{1}}\ldots p_{r}^{k_{r}}$ where $p_{1},\ldots,p_{r}$ are
distinct primes. The Projective space
${\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$ consists of vectors
$u\in({\mathbb{Z}}/N{\mathbb{Z}})^{n}$ upto unit
($({\mathbb{Z}}/N{\mathbb{Z}})^{\times}$) multiples of each other such that
$u$ $($mod $p_{i}^{k_{i}})$ has at least one unit co-ordinate for every
$i\in[r]$.

For each direction in ${\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$ we pick
a representative in $({\mathbb{Z}}/N{\mathbb{Z}})^{n}$. This allows us to
treat ${\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$ as a subset of
$({\mathbb{Z}}/N{\mathbb{Z}})^{n}$. We note then a line $L$ in direction
$u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$ is going to be a set of
the form $\\{a+tu|t\in{\mathbb{Z}}/N{\mathbb{Z}}\\}$ for some
$a\in{\mathbb{Z}}/N{\mathbb{Z}}$. We can now state our set size lower bound.

######  Theorem 1.2 (Set size lower bounds from maximal intersection sizes
over ${\mathbb{Z}}/N{\mathbb{Z}}$).

Say we are given $S\subseteq({\mathbb{Z}}/N{\mathbb{Z}})^{n}$ where
$N=p_{1}^{k_{1}}\ldots p_{r}^{k_{r}}$. We then have the following lower bound,

$\displaystyle|S|$ $\displaystyle\geq
C_{N,n}\underset{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}{{\mathbb{E}}}\left[\sup\limits_{a\in({\mathbb{Z}}/N{\mathbb{Z}})^{n}}|\\{a+tu|t\in{\mathbb{Z}}/N{\mathbb{Z}}\\}\cap
S|^{n}\right]$
$\displaystyle=C_{N,n}|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|^{-1}\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}\sup\limits_{a\in({\mathbb{Z}}/N{\mathbb{Z}})^{n}}|\\{a+tu|t\in{\mathbb{Z}}/N{\mathbb{Z}}\\}\cap
S|^{n},$

where

$C_{N,n}=\left(\prod_{j=1}^{r-1}\frac{1}{k_{j}\log(p_{j})+1}\prod\limits_{i=1}^{r}\frac{1}{2(k_{i}+\lceil\log_{p_{i}}(n)\rceil)}\right)^{n}.$

Note,
$\sup_{a\in({\mathbb{Z}}/N{\mathbb{Z}})^{n}}|\\{a+tu|t\in{\mathbb{Z}}/N{\mathbb{Z}}\\}\cap
S|$ is the maximal intersection a line in direction $u$ can have with $S$. The
above bound gives us new bounds for the Kakeya problem over
${\mathbb{Z}}/N{\mathbb{Z}}$ and generalizes them. To see that let us first
define Kakeya sets.

######  Definition 1.3 ($(m,\epsilon)$-Kakeya sets).

Let $N,n\in{\mathbb{N}}$. A subset
$S\subseteq({\mathbb{Z}}/N{\mathbb{Z}})^{n}$ is said to be
$(m,\epsilon)$-Kakeya when for at least an $\epsilon$ fraction of directions
$u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$ there exists a line
$L_{u}=\\{a+tu|t\in{\mathbb{Z}}/N{\mathbb{Z}}\\}$ in direction $u$ such that
$|L_{u}\cap S|\geq m$.

We note $(N,1)$-Kakeya sets are often just referred to as Kakeya sets. The
following is an immediate corollary of Theorem 1.2.

######  Corollary 1.4 ($(m,\epsilon)$-Kakeya bounds over
${\mathbb{Z}}/N{\mathbb{Z}}$ for general $N$).

Say we are given an $(m,\epsilon)$-Kakeya set
$S\subseteq({\mathbb{Z}}/N{\mathbb{Z}})^{n}$ where $N=p_{1}^{k_{1}}\ldots
p_{r}^{k_{r}}$ and $p_{1}>\ldots>p_{r}$. We then have the following lower
bound.

$|S|\geq C_{N,n}\epsilon m^{n},$

where

$C_{N,n}=\left(\prod_{j=1}^{r-1}\frac{1}{k_{j}\log(p_{j})+1}\prod\limits_{i=1}^{r}\frac{1}{2(k_{i}+\lceil\log_{p_{i}}(n)\rceil)}\right)^{n}.$

To our knowledge, Corollary 1.4 is the first $(m,\epsilon)$-Kakeya set bounds
over ${\mathbb{Z}}/N{\mathbb{Z}}$ for general $N$ (even the case of $N$
square-free was not known). Earlier, only bounds for $(N,1)$-Kakeya sets were
known for composite $N$ which were not prime powers.

Wolff in [Wol99] first asked the question of lower bounding the sizes of
Kakeya sets over finite fields whose resolution might help in proving the
Euclidean Kakeya conjecture. Wolff’s conjecture was proven by Dvir in [Dvi09]
by proving a lower bound of $q^{n}/n!$ for Kakeya sets in
${\mathbb{F}}_{q}^{n}$. Using the method of multiplicities and its extensions
[SS08, DKSS13, BC21] the constant was improved from $n!^{-1}$ to $2^{-n+1}$
which is known to be tight.

Ellenberg, Oberlin and Tao in [EOT10] proposed studying the size of Kakeya
sets over the rings ${\mathbb{Z}}/p^{k}{\mathbb{Z}}$ and
${\mathbb{F}}_{q}[x]/\langle x^{k}\rangle$. They were motivated by the fact
that these rings have “scales” and hence are closer to the Euclidean version
of the problem. Hickman and Wright posed the Kakeya set problem for
${\mathbb{Z}}/N{\mathbb{Z}}$ with arbitrary $N$ and considered connections
between the problem and the Kakeya conjecture over the $p$-adics in [HW18].
Indeed, proving strong enough lower bounds for the sizes of Kakeya sets over
the rings ${\mathbb{Z}}/p^{k}{\mathbb{Z}}$ and ${\mathbb{F}}_{q}[x]/\langle
x^{k}\rangle$ will resolve the Minkowski dimension Kakeya set conjecture for
the $p$-adic integers and and the power series ring ${\mathbb{F}}_{q}[[x]]$
respectively [EOT10, DH13, HW18]. The Kakeya problem over these rings is
interesting as similarly to the Euclidean case one can construct Kakeya sets
of Haar measure $0$ for the $p$-adic integers and the power series ring
${\mathbb{F}}_{q}[[x]]$. The constructions and generalizations to other
settings can be found in [DH13, Fra16, Car18, HW18, Dha21].

For $n=2$ and $N=p^{k}$, Dummit and Hablicsek in [DH13] proved that the sizes
of Kakeya sets are lower bounded by $p^{2k}/2k$. The author and Dvir [DD21]
gave almost tight Kakeya set lower bounds for ${\mathbb{Z}}/N{\mathbb{Z}}$
with square-free $N$. Arsovski in [Ars21b] gave the first
$(m,\epsilon)$-Kakeya set lower bounds for ${\mathbb{Z}}/p^{k}{\mathbb{Z}}$
resolving the $p$-adic Kakeya conjecture. A quantitatively stronger bound for
$(m,\epsilon)$-Kakeya sets over ${\mathbb{Z}}/p^{k}{\mathbb{Z}}$ were proven
in [Dha21] (by extending the proof in [Ars21a] which is an earlier version of
[Ars21b] with a different proof for only $(p^{k},1)$-Kakeya sets) and shown to
be almost sharp for $(p^{k},1)$-Kakeya sets. [Dha21] also proved Kakeya set
lower bounds over ${\mathbb{Z}}/N{\mathbb{Z}}$ for general $N$. [Sal22]
extended the techniques in [Ars21b] giving $(m,\epsilon)$-Kakeya bounds over
${\mathbb{F}}_{q}[x]/\langle x^{k}\rangle$ and resolving the Kakeya set
conjecture over ${\mathbb{F}}_{q}[[x]]$.

The general case of our results are Maximal Kakeya bounds over
${\mathbb{Z}}/N{\mathbb{Z}}$ for general $N$ which gives norm lower bounds for
functions $f:({\mathbb{Z}}/N{\mathbb{Z}})^{n}\rightarrow{\mathbb{Z}}_{\geq 0}$
using the data of the largest ‘intersection’ a line in a direction can have
with $f$. The size of ‘intersections’ of a line $L$ and $f$ is $\sum_{x\in
L}f(x)$. This information about ‘intersections’ is encapsulated using the
following definition.

######  Definition 1.5 (Maximal function).

Given $f:({\mathbb{Z}}/N{\mathbb{Z}})^{n}\rightarrow{\mathbb{Z}}_{\geq 0}$ we
define the maximal function
$f^{*}:{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}\rightarrow{\mathbb{Z}}_{\geq
0}$ as follows,

$f^{*}(u)=\sup\limits_{a\in({\mathbb{Z}}/N{\mathbb{Z}})^{n}}\left(\sum\limits_{t\in{\mathbb{Z}}/N{\mathbb{Z}}}f(a+tu)\right).$

The most general result we prove will lower bound the norm of $f$ by the norm
of $f^{*}$. Before describing the statement in its full generality we first
state it for $N=p^{k}$.

######  Theorem 1.6 (Maximal Kakeya bounds over
${\mathbb{Z}}/p^{k}{\mathbb{Z}}$).

Let $n>0$ be an integer, $p$ prime and $k\in{\mathbb{N}}$. For any function
$f:({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}\rightarrow{\mathbb{N}}$ we have the
following bound,

$\sum\limits_{x\in({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}}|f(x)|^{n}\geq
C_{p^{k},n}\underset{u\in{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}}{{\mathbb{E}}}[|f^{*}(u)|^{n}]=\frac{C_{p^{k},n}}{|{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}|}\left(\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}}|f^{*}(u)|^{n}\right),$

where

$C_{p^{k},n}=\frac{1}{(2(\lceil\log_{p}(\max_{u}f^{*}(u))+\log_{p}(n)\rceil))^{n}}.$

When $p>n$ we can improve $C_{p^{k},n}$ to,

$C_{p^{k},n}=(\lceil\log_{p}(\max_{u}f^{*}(u))\rceil+1)^{-n}(1+n/p)^{-n}.$

We note $\log_{p}(\max_{u}f^{*}(u))$ is bounded above by
$k+\log_{p}(\|f\|_{\ell^{\infty}})$ which means that as long as the terms are
not too big we can take the above inequality as a comparison between the
$\ell^{n}$ norms of $f$ and $f^{*}$.

Bounds of these types were first proven for finite fields in [EOT10]. Our
results will prove these bounds over ${\mathbb{Z}}/N{\mathbb{Z}}$ for general
$N$.

To state the general case of composite $N$ we first need some simple facts
which follow from the Chinese remainder theorem.

######  Fact 1.7 (Geometry of ${\mathbb{Z}}/p^{k}N_{0}{\mathbb{Z}}$).

Let
$p,N_{0},n,k\in{\mathbb{N}},R={\mathbb{Z}}/p^{k}N_{0}{\mathbb{Z}},R_{0}={\mathbb{Z}}/N_{0}{\mathbb{Z}}$
with $p$ prime and co-prime to $N_{0}$. Using the Chinese remainder theorem we
know that any co-ordinate in $R^{n}$ can be uniquely represented by a tuple in
$({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}\times R_{0}^{n}$. Also any direction in
the projective space ${\mathbb{P}}R^{n-1}$ can again be uniquely represented
by a tuple in
${\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}\times{\mathbb{P}}R_{0}^{n-1}$.
Finally, any line $L$ with direction
$b=(b_{p},b_{0})\in{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}\times{\mathbb{P}}R_{0}^{n-1}$
in $R^{n}$ is equivalent to the product of a line
$L_{p}\subset({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}$ in direction $b_{p}$ and a
line $L_{0}\subset R_{0}^{n}$ in direction $b_{0}$.

We will need to define a new quantity on which our bounds will depend.

######  Definition 1.8 ($p$-Maximal weight).

For $p$ and $N$ coprime and
$f:({\mathbb{Z}}/p^{k}N{\mathbb{Z}})^{n}\rightarrow{\mathbb{N}}$ we define the
$p$-maximal weight $\textsf{mweight}(f,p)$ as follows:

Let $L(u)=\\{a_{u}+tu|t\in{\mathbb{Z}}/p^{k}N{\mathbb{Z}}\\}$ be a line such
that $\sum_{x\in L(u)}f(x)=f^{*}(u)$. Using Fact 1.7 we note that the line
$L(u)$ can be written as a product of lines
$L_{p}(u)\subseteq({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}$ and
$L_{1}(u)\subseteq({\mathbb{Z}}/N{\mathbb{Z}})^{n}$. We define,

$\textsf{mweight}(f,p)=\sup_{u\in{\mathbb{P}}({\mathbb{Z}}/p^{k}N{\mathbb{Z}})^{n-1},z\in
L_{1}(u)}\sum\limits_{x\in L_{p}(u)}f((x,z)).$

Note, $\textsf{mweight}(f,p)$ for
$f:({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}\rightarrow{\mathbb{N}}$ is simply
$\max_{u}f^{*}(u)$.

We can finally state our main theorem.

######  Theorem 1.9 (Maximal Kakeya bounds over ${\mathbb{Z}}/N{\mathbb{Z}}$
for general $N$).

Let $n>0$ be an integer and $N=p_{1}^{k_{1}}\ldots p_{r}^{k_{r}}$ with $p_{i}$
primes and $k_{i}\in{\mathbb{N}}$. For any function
$f:({\mathbb{Z}}/N{\mathbb{Z}})^{n}\rightarrow{\mathbb{N}}$ we have the
following bound,

$\sum\limits_{x\in({\mathbb{Z}}/N{\mathbb{Z}})^{n}}|f(x)|^{n}\geq
C_{N,n}\underset{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}{{\mathbb{E}}}[|f^{*}(u)|^{n}]=\frac{C_{N,n}}{|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|}\left(\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}|f^{*}(u)|^{n}\right),$

where

$\displaystyle C_{N,n}=$
$\displaystyle\left(\frac{1}{2(\log(\textsf{mweight}(f,p_{1}))+1)\lceil\log_{p_{1}}(\textsf{mweight}(f,p_{1}))+\log_{p_{1}}(n)\rceil}\right)^{n}$
$\displaystyle\cdot\left(\frac{1}{2(k_{r}+\lceil\log_{p_{r}}(n)\rceil)}\prod\limits_{i=2}^{r-1}\frac{1}{2(k_{i}\log(p_{i})+1)(k_{i}+\lceil\log_{p_{i}}(n)\rceil)}\right)^{n}$

.

Similarly to the comment after Theorem 1.6 we note that
$\log(\textsf{mweight}(f,p_{1}))$ is bounded above by
$k_{1}\log(p_{1})+\log(\|f\|_{\ell^{\infty}})$. As before as long as the terms
are not too big we can take the above inequality as a comparison between the
$\ell^{n}$ norms of $f$ and $f^{*}$.

The overall argument will be via induction. The base case of Theorem 1.9 is
Theorem 1.6 (in fact the constants are slightly better for the $r=1$ case). We
also note if we apply Theorem 1.9 for $f$ equaling the indicator function
${\mathbf{1}}_{S}:({\mathbb{Z}}/N{\mathbb{Z}})^{n}\rightarrow{\mathbb{Z}}_{\geq
0}$ of a set $S$ we will get Theorem 1.2 (it is easy to see that
$\textsf{mweight}({\mathbf{1}}_{S},p_{1})\leq p_{1}$). Recall,
${\mathbf{1}}_{S}(x)=1$ if $x\in S$ and $0$ otherwise.

The main ideas in the proof involve using and extending the probabilistic and
the polynomial method tools from the papers [DD21, Ars21a, Dha21, DD22]. In
particular, generalizing the new probabilistic method arguments from [DD22] is
what allows us to overcome barriers to deal with the case of composite $N$
with multiple prime factors. As mentioned earlier, even $(m,\epsilon)$-Kakeya
bounds were not known for non prime power $N$ (even if $N$ was square-free).
Indeed, already known techniques (in particular, combining the arguments from
[Ars21b] and [EOT10]) would have sufficed to prove maximal bounds for the case
of prime powers.

In addition, we also show that a simple application of the arguments in [DD22]
leads to a direct and simpler proof for Maximal Kakeya bounds over finite
fields with almost sharp constants.

######  Theorem 1.10 (Maximal Kakeya bounds over finite fields).

Let $n>0$ be an integer, $q$ a prime power. For any function
$f:{\mathbb{F}}_{q}^{n}\rightarrow{\mathbb{C}}$ we have the following bound,

$\sum\limits_{x\in{\mathbb{F}}_{q}^{n}}|f(x)|^{n}\geq\frac{1}{2^{n}}\underset{u\in{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}}{{\mathbb{E}}}[|f^{*}(u)|^{n}]=\frac{1}{2^{n}}|{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}|^{-1}\left(\sum\limits_{u\in{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}}|f^{*}(u)|^{n}\right).$

The first bounds of this type were proven in [EOT10] where it was also proven
for the more general case of varities by reducing to the case of the case of
${\mathbb{F}}^{n}_{q}$. Our arguments can be combined with theirs to improve
the constants but we only focus on the case of ${\mathbb{F}}^{n}_{q}$ as that
is where our new argument is being used.

The sharpness of the above theorem is evident if we take the indicator
function of Kakeya sets which then gives us the lower bounds from [DKSS13]
which are tight up to a factor of $2$.***Indeed our arguments can be combined
with the arguments of [BC21] to get rid of this $2$ but we do not do that to
simplify the proof. Finally, we note that Theorem 1.9 can be used to resolve
the following statement of the Kakeya maximal conjecture in [HW18].

######  Conjecture 1.11 (Kakeya Maximal conjecture over
${\mathbb{Z}}/N{\mathbb{Z}}$).

For all $\epsilon>0$ and $n\in{\mathbb{N}}$ there exists a constant
$C_{n,\epsilon}$ such that the following holds: For a choice of a line $L(u)$
for each direction $u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$ we
have,

$\left\|\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}{\mathbf{1}}_{L(u)}\right\|_{\ell^{n/(n-1)}}\leq
C_{n,\epsilon}N^{\epsilon}\left(\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}|L(u)|\right)^{(n-1)/n}.$

The above inequality simply follows from taking the dual of Theorem 1.9. This
will be shown in Section 6.

###  1.1 Acknowledgements

The author would like to thank Zeev Dvir and Suryateja Gavva for helpful
comments and discussion. Research supported by NSF grant DMS-1953807.

###  1.2 Paper Organization:

In Section 2 we state preliminaries from [DKSS13, DD21, DD22] which we will
need. In Section 3 we prove Theorem 1.10 with our new techniques. In Section 4
we prove Theorem 1.6 which is the base case of our induction argument. In
Section 5 we finally prove Theorem 1.9. In Section 6 we prove Conjecture 6.

##  2 Preliminaries

###  2.1 Multiplicities and Hasse derivative

We first review the definitions of multiplicities and Hasse derivatives that
will be needed in the proof (see [DKSS13] for a more detailed discussion). We
will allow the definitions to be over an arbitrary field ${\mathbb{F}}$ since
we will need to apply them both for ${\mathbb{F}}={\mathbb{F}}_{q}$ (for
Theorem 1.10) and also for ${\mathbb{F}}={\mathbb{C}}$ (for Theorem 1.9 and
Theorem 1.6).

######  Definition 2.1 (Hasse Derivatives).

Let ${\mathbb{F}}$ be a field. Given a polynomial
$Q\in{\mathbb{F}}[x_{1},\ldots,x_{n}]$ and an $\mathbf{i}\in{\mathbb{Z}}_{\geq
0}^{n}$ the $\mathbf{i}$th Hasse derivative of $Q$ is the polynomial
$Q^{(\mathbf{i})}$ in the expansion

$Q(x+z)=\sum_{\mathbf{j}\in{\mathbb{Z}}_{\geq
0}^{n}}Q^{(\mathbf{j})}(x)z^{\mathbf{j}}$

where $x=(x_{1},...,x_{n})$, $z=(z_{1},...,z_{n})$ and
$z^{\mathbf{j}}=\prod_{k=1}^{n}z_{k}^{j_{k}}$.

Hasse derivatives satisfy the following useful property (see [DKSS13] for a
proof). We will only need this property to show that, if
$Q^{(\mathbf{i}+\mathbf{j})}$ vanishes at a point then so does
$(Q^{(\mathbf{i})})^{(\mathbf{j})}$.

######  Lemma 2.2.

Given a polynomial $Q\in{\mathbb{F}}[x_{1},\ldots,x_{n}]$ and
$\mathbf{i},\mathbf{j}\in{\mathbb{Z}}_{\geq 0}^{n}$, we have

$(Q^{(\mathbf{i})})^{(\mathbf{j})}=Q^{(\mathbf{i}+\mathbf{j})}\prod\limits_{k=1}^{n}\binom{i_{k}+j_{k}}{i_{k}}$

We make precise what it means for a polynomial to vanish on a point
$a\in{\mathbb{F}}^{n}$ with multiplicity. First we recall for a point
$\mathbf{j}$ in the non-negative lattice ${\mathbb{Z}}^{n}_{\geq 0}$, its
weight is defined as $\text{wt}(\mathbf{j})=\sum_{i=1}^{n}j_{i}$.

######  Definition 2.3 (Multiplicity).

For a polynomial $Q\in{\mathbb{F}}[x_{1},\ldots,x_{n}]$ and a point
$a\in{\mathbb{F}}^{n}$ we say $Q$ vanishes on $a$ with multiplicity
$m\in{\mathbb{Z}}_{\geq 0}$, if $m$ is the largest integer such that all Hasse
derivatives of $Q$ of weight strictly less than $m$ vanish on $a$. We use
$\textsf{mult}(Q,a)$ to refer to the multiplicity of $Q$ at $a$.

Note that the number of Hasse derivatives over
${\mathbb{F}}[x_{1},\ldots,x_{n}]$ with weight strictly less than $m$ is
$\binom{n+m-1}{n}$. Hence, requiring that a polynomial vanishes to order $m$
at a single point $a$ enforces the same number of homogeneous linear equations
on the coefficients of the polynomial. We will use the following simple
property concerning multiplicities of composition of polynomials (see [DKSS13]
for a proof).

######  Lemma 2.4.

Given a polynomial $Q\in{\mathbb{F}}[x_{1},\ldots,x_{n}]$ and a tuple
$G=(g_{1},\ldots,g_{n})$ of polynomials in ${\mathbb{F}}[y_{1},\ldots,y_{m}]$,
and $a\in{\mathbb{F}}^{m}$ we have,

$\textsf{mult}(Q\circ G,a)\geq\textsf{mult}(Q,G(a)).$

Finally, we need a lemma which given a $\epsilon$ fraction of directions
$B\subseteq{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}$ we can find a large set of
monomials of a fixed degree (not depending on $\epsilon$) such that any linear
combination of these monomials doesn’t vanish on the entirety of $B$ with high
multiplicity.

######  Lemma 2.5.

Let $r\in{\mathbb{N}}$ and $B\subseteq{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}$ with
$|S|\geq\epsilon|{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}|,\epsilon\in[0,1]$ then
for any $d<rq$ there exists a set
$P_{B}(d,r),|P_{B}(d,r)|=\epsilon\binom{d+n}{n}$ of monomials of degree
exactly $d$ such that no non-zero linear combination of monomials in
$P_{B}(d,r)$ vanishes with multiplicity at least $r$ over all points in $B$.

This is analogous to Corollary 6.12 in [DD22]. The proof is nearly identical
and uses a probabilistic method argument with the Schwartz-Zippel lemma
[Sch79, Zip79]. For completeness, we give a proof in the appendix.

###  2.2 Rank of matrices with polynomial entries

We will be needing a number of preliminaries from [Dha21] which we state
without proof.

######  Definition 2.6 (Rank of matrices with entries in
$\mathbb{F}[z]/\langle f(z)\rangle$).

Given a field ${\mathbb{F}}$ and a matrix $M$ with entries in
${\mathbb{F}}[z]/\langle f(z)\rangle$ where $f(z)$ is a non-constant
polynomial in ${\mathbb{F}}[z]$, we define the ${\mathbb{F}}$-rank of $M$
denoted $\textsf{rank}_{\mathbb{F}}M$ as the maximum number of
${\mathbb{F}}$-linearly independent columns of $M$.

Given a matrix $A$ with entries in ${\mathbb{F}}[z]/\langle f(z)\rangle$ we
want to construct a new matrix with entries only in ${\mathbb{F}}$ such that
their ${\mathbb{F}}$-ranks are the same. First we state a simple fact about
${\mathbb{F}}[z]/\langle f(z)\rangle$.

######  Fact 2.7 (Unique representation of elements in
${\mathbb{F}}[z\text{]}/\langle f(z)\rangle$).

Let ${\mathbb{F}}$ be a field and $f(z)$ a non-constant polynomial in
${\mathbb{F}}[z]$ of degree $d>0$. Every element in ${\mathbb{F}}[z]/\langle
f(z)\rangle$ is uniquely represented by a polynomial in ${\mathbb{F}}[z]$ with
degree strictly less than $d$ and conversely every degree strictly less than
$d$ polynomial in ${\mathbb{F}}[z]$ is a unique element in
${\mathbb{F}}[z]/\langle f(z)\rangle$. When we refer to an element
$h(z)\in{\mathbb{F}}[z]/\langle f(z)\rangle$ we also let it refer to the
unique degree strictly less than $d$ polynomial it equals.

######  Definition 2.8 (Coefficient matrix of $A$).

Let ${\mathbb{F}}$ be a field and $f(z)$ a non-constant polynomial in
${\mathbb{F}}[z]$ of degree $d>0$. Given any matrix $A$ of size $n_{1}\times
n_{2}$ with entries in ${\mathbb{F}}[z]/\langle f(z)\rangle$ we can construct
the coefficient matrix of $A$ denoted by $\textsf{Coeff}(A)$ with entries in
${\mathbb{F}}$ which will be of size $dn_{1}\times n_{2}$ whose rows are
labelled by elements in $\\{0,\ldots,d-1\\}\times[n_{1}]$ such that its
$(i,j)$’th row is formed by the coefficients of $z^{i}$ of the polynomial
entries of the $j$’th row of $A$.

The key property about the coefficient matrix immediately follows from its
definition.

######  Fact 2.9.

Let ${\mathbb{F}}$ be a field and $f(z)$ a non-constant polynomial in
${\mathbb{F}}[z]$ of degree $d>0$. Given any matrix $A$ with entries in
${\mathbb{F}}[z]/\langle f(z)\rangle$ and its coefficient matrix
$\textsf{Coeff}(A)$ it is the case that an ${\mathbb{F}}$-linear combination
of a subset of columns of $A$ is $0$ if and only if the corresponding
${\mathbb{F}}$-linear combination of the same subset of columns of
$\textsf{Coeff}(A)$ is also $0$.

In particular, the ${\mathbb{F}}$-rank of $A$ equals the ${\mathbb{F}}$-rank
of $\textsf{Coeff}(A)$.

We now need some simple properties related to the crank of tensor products. To
that end we first define the tensor/Kronecker product of matrices.

######  Definition 2.10 (Kronecker Product of two matrices).

Given a commutative ring $R$ and two matrices $M_{A}$ and $M_{B}$ of sizes
$n_{1}\times m_{1}$ and $n_{2}\times m_{2}$ corresponding to $R$-linear maps
$A:R^{n_{1}}\rightarrow R^{m_{1}}$ and $B:R^{n_{2}}\rightarrow R^{m_{2}}$
respectively, we define the Kronecker product $M_{A}\otimes M_{B}$ as a matrix
of size $n_{1}n_{2}\times m_{1}m_{2}$ with its rows indexed by elements in
$[n_{1}]\times[n_{2}]$ and its columns indexed by elements in
$[m_{1}]\times[m_{2}]$ such that

$M_{A}\otimes
M_{B}((r_{1},r_{2}),(c_{1},c_{2}))=M_{A}(r_{1},c_{1})M_{B}(r_{2},c_{2}),$

where $r_{1}\in[n_{1}],r_{2}\in[n_{2}],c_{1}\in[m_{1}]$ and $c_{2}\in[m_{2}]$.
$M_{A}\otimes M_{B}$ corresponds to the matrix of the $R$-linear map $A\otimes
B:R^{n_{1}}\otimes R^{n_{2}}\cong R^{n_{1}n_{2}}\rightarrow R^{m_{1}}\otimes
R^{m_{2}}\cong R^{m_{1}m_{2}}$.

We will need the following simple property of Kronecker products which follows
from the corresponding property of the tensor product of linear maps.

######  Fact 2.11 (Multiplication of Kronecker products).

Given matrices $A_{1},A_{2},B_{1}$ and $B_{2}$ of sizes $a_{1}\times n_{1}$,
$a_{2}\times n_{2}$, $n_{1}\times b_{1}$ and $n_{2}\times b_{2}$ we have the
following identity,

$(A_{1}\otimes A_{2})\cdot(B_{1}\otimes B_{2})=(A_{1}\cdot
B_{1})\otimes(A_{2}\cdot B_{2}).$

We also need a simple fact about tensor product of a set of linearly
independent rows with arbitrary vectors.

######  Fact 2.12 (Linear independence of Kronecker products).

Let $k,n,m\in{\mathbb{N}}$. Given linearly independent vectors
$r_{1},r_{2},\ldots,r_{k}\in{\mathbb{F}}^{n}$ then the set of vectors
$r_{i}\otimes{\mathbb{F}}^{m},i=[k]$ are mutually disjoint from each other
outside of $0$. In particular, the union of a set of linearly independent
vectors from each of $r_{i}\otimes{\mathbb{F}}^{m},i=[k]$ gives us a linearly
independent set of vectors.

###  2.3 Polynomial Method on the complex torus

This section also includes preliminaries from [Dha21] but written for a
slightly more general set of parameters. In most cases the proofs are near
identical as in Section 3 of [Dha21]. Where the proofs are more complicated we
give proofs in the appendix for completeness.

We first define the rings that we will work over.

######  Definition 2.13 (Rings $\overline{T}_{\ell}$ and $T_{\ell}^{k}$).

†††In [Dha21] $\overline{T}_{\ell}$ is defined as ${\mathbb{F}}_{p}[z]/\langle
z^{p^{\ell}}-1\rangle$. We will need this more general definition in this
paper.

We let

$\overline{T}_{\ell}={\mathbb{F}}_{p}[z]/\langle(z-1)^{\ell}\rangle$

and

$T_{\ell}^{k}={\mathbb{Z}}(\zeta_{p^{k}})[z]/\langle(z-1)^{\ell}\rangle$

where $\zeta_{p^{k}}$ is a primitive complex $p^{k}$’th root of unity.

In [Dha21] $\ell$ is a power of $p$ but that is not necessary for the proofs
to work. To prove maximal Kakeya bounds we need this extra control over the
parameters.

We suppress $p$ in the notation as it will be fixed to a single value
throughout our proofs. We also let $\zeta=\zeta_{p^{k}}$ throughout this
section for ease of notation.

Note that ${\mathbb{Z}}(\zeta)$ is the ring
${\mathbb{Z}}[\zeta]/\langle\phi_{p^{k}}(\zeta)\rangle$ where,

$\displaystyle\phi_{p^{k}}(x)=\frac{x^{p^{k}}-1}{x^{p^{k-1}}-1}=\sum\limits_{i=0}^{p-1}x^{ip^{k-1}},$
(1)

is the $p^{k}$ Cyclotomic polynomial. We will also work with the field
${\mathbb{Q}}(\zeta)={\mathbb{Q}}[\zeta]/\langle\phi_{p^{k}}(\zeta)\rangle$.

We need a simple lemma connecting ${\mathbb{Z}}(\zeta)$ to ${\mathbb{F}}_{p}$.

######  Lemma 2.14 (Quotient map $\psi_{p^{k}}$ from ${\mathbb{Z}}(\zeta)$ to
${\mathbb{F}}_{p}$).

The field ${\mathbb{F}}_{p}$ is isomorphic to ${\mathbb{Z}}(\zeta)/\langle
p,\zeta-1\rangle$. In particular, the map $\psi_{p^{k}}$ from
${\mathbb{Z}}(\zeta)$ to ${\mathbb{F}}_{p}$ which maps ${\mathbb{Z}}$ to
${\mathbb{F}}_{p}$ via the mod $p$ map and $\zeta$ to $1$ is a ring
homomorphism.

We note $\psi_{p^{k}}$ can be extended to the rings
${\mathbb{Z}}(\zeta)[z]/\langle h(z)\rangle$ for any
$h(x)\in{\mathbb{Z}}(\zeta)[x]$ by mapping $z$ to $z$. In particular, we also
have the following.

######  Corollary 2.15 (Extending $\psi_{p^{k}}$).

Let $h(x)\in{\mathbb{Z}}(\zeta)[x]$. $\psi_{p^{k}}$ is a ring homomorphism
from ${\mathbb{Z}}(\zeta)[z]/\langle h(z)\rangle$ to
${\mathbb{Z}}(\zeta)[z]/\langle
h(z),p,\zeta-1\rangle={\mathbb{F}}_{p}[z]/\langle\psi_{p^{k}}(h(z))\rangle$.

$T_{\ell}^{k}/\langle p,\zeta-1\rangle$ being isomorphic to
$\overline{T}_{\ell}$ is a special case of the corollary.

We also need the following lemma proving rank relations under the quotient map
$\psi_{p^{k}}$.

######  Lemma 2.16.

Let $A$ be a matrix with entries in $T_{\ell}^{k}$ then we have the following
bound,

$\textsf{rank}_{{\mathbb{Q}}(\zeta)}A\geq\textsf{rank}_{{\mathbb{F}}_{p}}\psi_{p^{k}}(A),$

where $\psi_{p^{k}}(A)$ is the matrix with entries in $\overline{T}_{\ell}$
obtained by applying $\psi_{p^{k}}$ to each entry of $A$.

We now define the Vandermonde matrices with entries in ${\mathbb{F}}_{p}[z]$
which was defined by Arsovski in [Ars21a] and whose ${\mathbb{F}}_{p}$-rank
will help us lower bound the size of Kakeya Sets.

######  Definition 2.17 (The matrix $M_{m,n}$).

The matrix $M_{m,n}$ is a matrix over ${\mathbb{F}}_{p}[z]$ with its rows and
columns indexed by points in $\\{0,\ldots,m-1\\}^{n}$. The
$(u,v)\in\\{0,\ldots,m-1\\}^{n}\times\\{0,\ldots,m-1\\}^{n}$ entry is

$M_{m,n}(u,v)=z^{\langle u,v\rangle}.$

For a matrix $M$ with entries in ${\mathbb{F}}[z]$ we let $M(\text{mod }G(z))$
is the matrix with same entries but over the ring ${\mathbb{F}}[z]/\langle
G(z)\rangle$. We let $M^{\ell}_{m,n}$ be the matrix $M_{m,n}(\text{mod
}(z-1)^{\ell})$. We will need the following bound on the
${\mathbb{F}}_{p}$-rank of these matrices.

######  Lemma 2.18 (Rank of $M^{\ell}_{m,n}$).

Let $m\geq\ell$ then the ${\mathbb{F}}_{p}$-rank of $M^{\ell}_{m,n}$ is at
least

$\text{rank}_{{\mathbb{F}}_{p}}M^{\ell}_{m,n}\geq\left\lceil\binom{\ell\lceil\log_{p}(\ell)\rceil^{-1}+n}{n}\right\rceil.$

For a given set of elements $V\subseteq\\{0,\ldots,m-1\\}^{n}$ let
$M_{m,n}(V)$ refer to the sub-matrix obtained by restricting to rows of
$M_{m,n}$ corresponding to elements in $V$ (similarly for $M^{\ell}_{m,n}$).
In particular, for any given $u\in\\{0,\ldots,m-1\\}^{n}$ we let
$M_{\ell,n}(u)$ refer to the $u$’th row of the matrix.

We first want to show the ${\mathbb{F}}_{p}$-rank of $M^{\ell}_{m,n}$ can be
explained by the rows indexed by elements $u\in\\{0,\ldots,m-1\\}^{n}$ such
that at least one coordinate is non-zero modulo $p$. To that end we let
$V_{m,p}$ represent the set of elements in $\\{0,\ldots,m-1\\}^{n}$ such that
at least one co-ordinate is non-zero modulo $p$.

######  Lemma 2.19.

The row-space of $\textsf{Coeff}(M^{\ell}_{m,n})$ equals the row-space of the
sub-matrix $\textsf{Coeff}(M^{\ell}_{m,n}(V_{m,p}))$.

###### Proof.

Consider the matrix $\textsf{Coeff}(M^{\ell}_{m,n})$. For any
$u\in\\{0,\ldots,m-1\\}^{n}$, the $u$’th row in $M^{\ell}_{m,n}$ will
correspond to a $p^{\ell}$ block of rows $B_{u}$ in
$\textsf{Coeff}(M^{\ell}_{m,n})$. Say $u$ doesn’t have a non-zero coordinate
modulo $p$. We can find an element $u^{\prime}\in V_{m,p}$ such that for some
$i$, $p^{i}u^{\prime}=u$. We claim that the block $B_{u}$ can be generated by
the block $B_{u^{\prime}}$ via a linear map. This follows because given the
coefficient vector of a polynomial $Q(z)$ in $\overline{T}_{\ell}$ the
coefficient vector of the polynomial $Q(z^{p})\in\overline{T}_{\ell}$ can be
obtained via a ${\mathbb{F}}_{p}$-linear map. ∎

We need to consider row vectors which encode the evaluation of monomials and
their derivatives over points on a line in direction
$u\in({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}$.

######  Definition 2.20 (The evaluation vector $U_{d}^{({\bm{\alpha}})}(y)$).

Let ${\mathbb{F}}$ be a field, $n,d\in{\mathbb{Z}}$ and
${\bm{\alpha}}\in{\mathbb{Z}}_{\geq 0}^{n}$. For any given point
$y\in{\mathbb{F}}^{n}$ we define $U_{d}^{({\bm{\alpha}})}(y)$ to be a row
vector of size $d^{n}$ whose columns are indexed by monomials
$Q=x_{1}^{j_{1}}x_{2}^{j_{2}}\ldots
x_{n}^{j_{n}}\in{\mathbb{F}}[x_{1},\ldots,x_{n}]$ for
$j_{k}\in\\{0,\ldots,d-1\\},k\in[n]$ such that its $Q$’th column is
$Q^{({\bm{\alpha}})}(y)$.

Let $L\subseteq({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}$ be a line in direction
$u\in{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}$. A special case of
the next lemma proves that for any polynomial
$f\in{\mathbb{Z}}[x_{1},\ldots,x_{n}]$ we can evaluate
$f(z^{u})\in\overline{T}_{p^{k}}={\mathbb{F}}_{p}[z]/\langle(z-1)^{p^{k}}\rangle,z^{u}=(z^{u_{1}},\ldots,z^{u_{n}})$
from the evaluation of $f$ on the points $f(\zeta^{x}),x\in L$. Let
$\pi:L\rightarrow{\mathbb{Z}}_{\geq 0}$ be a function on the line such that
$\sum_{x\in L}\pi(x)\geq\ell$. The next lemma states that we can decode
$f(z^{u^{\prime}})\in\overline{T}_{\ell}={\mathbb{F}}_{p}[z]/\langle(z-1)^{\ell}\rangle$
from the evaluations of weight at most $\pi(\zeta^{x})$ Hasse derivatives of
$f$ at $\zeta^{x},x\in L$ for any $u^{\prime}$ in ${\mathbb{Z}}^{n}$ such that
$u^{\prime}\text{ (mod }p^{k}\text{)}=u$.

The lemma below can be thought of as analogous to how over finite fields the
evaluation of a polynomial and its Hasse derivatives with high enough weight
along a line in direction $u$ can be used to decode the evaluation of that
polynomial at the point at infinity along $u$ [DKSS13].

######  Lemma 2.21 (Decoding from evaluations on rich lines).

Let $L=\\{a+\lambda
u|\lambda\in{\mathbb{Z}}/p^{k}{\mathbb{Z}}\\}\subset({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}$
with
$a\in({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n},u\in{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}$,
$u^{\prime}\in{\mathbb{Z}}^{n}$ be such that $u^{\prime}\text{ (mod
}p^{k}\text{)}=u$ and $\pi:L\rightarrow{\mathbb{Z}}_{\geq 0}$ be a function
which satisfies $\sum_{x\in L}\pi(x)\geq\ell$.

Then, there exists elements
$c_{\lambda,{\bm{\alpha}}}\in{\mathbb{Q}}(\zeta)[z]$ (depending on $\pi,L$ and
$u^{\prime}$) for $\lambda\in{\mathbb{Z}}/p^{k}{\mathbb{Z}}$ and
${\bm{\alpha}}\in{\mathbb{Z}}_{\geq 0}^{n}$ with
$\text{wt}({\bm{\alpha}})<\pi(a+\lambda u)$ such that the following holds for
all polynomials $f\in{\mathbb{Z}}[x_{1},\ldots,x_{n}]$,

$\psi_{p^{k}}\left(\sum\limits_{\lambda=0}^{p^{k}-1}\sum\limits_{\text{wt}({\bm{\alpha}})<\pi(a+\lambda
u)}c_{\lambda,{\bm{\alpha}}}f^{({\bm{\alpha}})}(\zeta^{a+\lambda
u})\right)=f(z^{u^{\prime}})\in\overline{T}_{\ell}.$

For the application of $\psi_{p^{k}}$ in the statement of the lemma to make
sense we must have its input be an element in $T_{\ell}^{k}$. In other words,
we need the input of $\psi_{p^{k}}$ to be a polynomial in $z$ with
coefficients in ${\mathbb{Z}}(\zeta)$. This is indeed the case. This lemma is
basically Lemma 3.11 from [Dha21] and the proof is near identical. For
completeness we give the proof in the appendix.

We will need this Lemma in the form of the following Corollary.

######  Corollary 2.22 (Decoding $M^{\ell}_{m,n}$ from
$U^{({\bm{\alpha}})}_{m}$).

Let $L=\\{a+\lambda
u|\lambda\in{\mathbb{Z}}/p^{k}{\mathbb{Z}}\\}\subset({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}$
with
$a\in({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n},u\in{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}$,
$u^{\prime}\in{\mathbb{Z}}^{n}$ be such that $u^{\prime}\text{ (mod
}p^{k}\text{)}=u$ and $\pi:L\rightarrow{\mathbb{Z}}_{\geq 0}$ be a function
which satisfies $\sum_{x\in L}\pi(x)\geq\ell$ then there exists a
${\mathbb{Q}}(\zeta)[z]$-linear combination (with coefficients depending on
$\pi,L$ and $u^{\prime}$) of the vectors $U_{m}^{({\bm{\alpha}})}(\zeta^{x})$
for $x\in L$ and ${\bm{\alpha}}$ of weight strictly less than $\pi(x)$ which
under the map $\psi_{p^{k}}$ gives us the vector $M^{\ell}_{m,n}(u^{\prime})$.

This also implies that there exists for each $i=0,\ldots,\ell-1$ many
${\mathbb{Q}}(\zeta)$-linear combinations of
$U_{m}^{({\bm{\alpha}})}(\zeta^{x})$ for $x\in L$ and ${\bm{\alpha}}<\pi(x)$
such that under the map $\psi_{p^{k}}$ we get the $i$th row of
$\textsf{Coeff}(M^{\ell}_{m,n}(u^{\prime}))$.

To prove maximal bounds we will need to treat $M^{\ell}_{m,n}$ over
$\overline{T}_{\ell}$ as a sub-matrix of $M^{\ell+1}_{m,n}$ over
$\overline{T}_{\ell+1}$ in some sense. We make this precise now.

######  Lemma 2.23.

The row-space over ${\mathbb{F}}_{p}$ of $\textsf{Coeff}(M_{\ell,n})$ is a
sub-space of the row-space over ${\mathbb{F}}_{p}$ of
$\textsf{Coeff}(M_{\ell+1,n})$.

###### Proof.

This follows from the fact the coefficients of $Q$ modulo $(z-1)^{\ell}$ can
be computed as a linear combination of the coefficients of $Q$ modulo
$(z-1)^{\ell+1}$. This is because $(z-1)^{\ell}$ is a factor of
$(z-1)^{\ell+1}$. ∎

The previous lemma easily implies the next corollary using simple linear
algebra and Lemmas 2.18 and 2.19.

######  Corollary 2.24.

We have a set $A=A_{1}\cup\ldots\cup A_{\ell}$ of linearly independent row
vectors in the row space of $\textsf{Coeff}(M^{\ell}_{m,n})$ such that

  1. 1.

$|A|=\left\lceil\binom{\ell\lceil\log_{p}(\ell)\rceil^{-1}+n}{n}\right\rceil,$

  2. 2.

elements in $A_{i}$ are a subset of the rows of
$\textsf{Coeff}(M^{i}_{m,n}(V_{m,p}))$ and do note belong in the row space of
$\textsf{Coeff}(M^{i-1}_{m,n})$,

  3. 3.

and

$|A_{i}|=\left\lceil\binom{i\lceil\log_{p}(i)\rceil^{-1}+n}{n}\right\rceil-\left\lceil\binom{(i-1)\lceil\log_{p}(i)\rceil^{-1}+n}{n}\right\rceil$

for $i\in[\ell]$.

In the above corollary, for the purposes of our arguments, $A_{i}$ in some
sense encapsulates the linearly independent evaluations of degree $i$
monomials when we embed ${\mathbb{Z}}/p^{k}{\mathbb{Z}}$ over the complex
torus and use the $\psi_{p^{k}}$ operation. This kind of decomposition is
important for us to get Maximal Kakeya bounds.

##  3 Warm Up: Maximal Kakeya bounds over finite fields

In this section we prove Theorem 1.10. We restate it here.

######  Theorem 1.10 (Maximal Kakeya bounds over finite fields).

Let $n>0$ be an integer, $q$ a prime power. For any function
$f:{\mathbb{F}}_{q}^{n}\rightarrow{\mathbb{C}}$ we have the following bound,

$\sum\limits_{x\in{\mathbb{F}}_{q}^{n}}|f(x)|^{n}\geq\frac{1}{(2-1/q)^{n}}|{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}|^{-1}\left(\sum\limits_{u\in{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}}|f^{*}(u)|^{n}\right).$

By a limiting and scaling argument we note that it suffices to prove the
statement above only for natural number valued functions.

We first give a brief sketch for a weaker bound for the setting where $f$ is
the indicator function of a set to give intuition. The proof will be a
direction generalization of the proof of the Kakeya set problem via the
polynomial method. First let us describe the proof in [Dvi09] for the Kakeya
set problem. That paper corresponds to the setting where the function
$f:{\mathbb{F}}_{q}^{n}\rightarrow{\mathbb{N}}$ is the indicator function of a
set $S\subseteq{\mathbb{F}}_{q}^{n}$ such that $f^{*}$ is always $q$. That is
$S$ contains a line in every direction.

Dvir’s proof works by assuming the set has size smaller than
$\binom{q-1+n}{n}\geq q^{n}/n!$ which is the number of degree at most $q-1$
monomials in $n$ variables. This means we can find a non-zero linear
combination of these monomials to construct a polynomial $Q$ of degree at most
$q-1$ which vanishes on the entirety of $S$. As $S$ contains a line in each
direction $Q$ can be restricted on these lines and will vanish on $q$ points
while having degree at most $q-1$. By elementary algebra we can observe that
the highest degree part of $Q$ vanishes on every direction. This leads to a
contradiction as a homogenous polynomial of degree at most $q-1$ can not
vanish over every direction by the Schwartz-Zipple lemma [Sch79, Zip79].

We modify this proof using Lemma 2.5 to find a more suitable polynomial. We
now start out with an arbitrary set $S$ and let $f$ be its indicator function.
Clearly, $f^{*}\leq q$. Let

$B_{\geq k}=\\{u\in{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}|f^{*}(u)\geq k\\},$

in other words it is the set of directions for which there exists a line in
that direction with intersection at least $k$ with $S$. We also let
$\epsilon_{\geq k}=|B_{\geq k}|/|{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}|$.

We will prove that,

$|S|\geq\sum\limits_{k=0}^{q-1}\epsilon_{\geq k+1}\binom{k+n-1}{n-1}.$ (2)

Rearranging the RHS will show that the above inequality gives us the desired
bounds but with worse constants. For each $0\leq k\leq q-1$ we can find a set
of monomials $P(k)$ of degree $k$ such that any of their linear combinations
do not vanish over $B_{\geq k+1}$.

If we say (2) does not hold then we can find a non-zero polynomial $Q$ formed
by taking a linear combination of monomials from $\bigcup_{k=0}^{q-1}P(k)$
which vanishes on $S$. Say $Q$ is of degree $d$. Then consider the set of
directions $B_{\geq d+1}$. For each direction in $B_{\geq d+1}$ there exists a
line in that direction such that $Q$ vanishes on $d+1$ of its points. As $Q$
is of degree $d$ again by elementary algebra we can say that the degree $d$
part of $Q$ then must vanish on the direction vector. But the degree $d$ part
of $Q$ is a linear combination of monomials from $P(d)$ and hence can’t vanish
on the entirety of $B_{\geq d+1}$ leading to a contradiction.

The general statement is proven by letting derivatives also vanish and a more
careful analysis to get better constants.

###### Proof.

Let $f:{\mathbb{F}}_{q}^{n}\rightarrow{\mathbb{N}}$ and we define $B_{\geq
k}=\\{u||f^{*}(u)|\geq k,u\in{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}\\}$ and
$B_{k}=\\{u||f^{*}(u)|=k,u\in{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}\\}$. In other
words, $B_{\geq k}$ is the set of directions where the maximal function is at
least $k$ (similarly for $B_{k}$). We also let $w=\max_{u}f^{*}(u)$. For
$m\in{\mathbb{N}}$ and $0\leq k\leq w$, let

$\epsilon_{\geq k}=|B_{\geq k}|/|{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}|,$
$\epsilon_{k}=|B_{k}|/|{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}|$
$r_{k}=\left\lceil\frac{mk+1}{2q-1}-1\right\rceil,$

and

$d_{k}=r_{k}q-1.$

By definition, $\epsilon_{\geq k}=\sum\limits_{i=k}^{w}\epsilon_{k}$. We also
note that if $m\geq 2q$ then $0=r_{0}<r_{1}<r_{2}<\ldots<r_{w}$. The same also
holds for $-1=d_{0}<d_{1}<\ldots<d_{w}$.

We will prove the following inequality for all $m\geq 2q$,

$\sum\limits_{i=1}^{w}\epsilon_{\geq
i}\sum\limits_{j=d_{i-1}+1}^{d_{i}}\binom{j+n-1}{n-1}\leq\sum\limits_{x\in{\mathbb{F}}_{q}^{n}}\binom{mf(x)+n-1}{n}.$
(3)

We claim (3) proves the Theorem. Let us prove that first. The LHS of (3) can
be re-arranged to give,

$\displaystyle\sum\limits_{i=1}^{w}\epsilon_{\geq
i}\sum\limits_{j=d_{i-1}+1}^{d_{i}}\binom{j+n-1}{n-1}$
$\displaystyle=\sum\limits_{i=1}^{w}\sum_{k=i}^{w}\sum\limits_{j=d_{i-1}+1}^{d_{i}}\epsilon_{k}\binom{j+n-1}{n-1}$
$\displaystyle=\sum_{k=1}^{w}\sum\limits_{i=0}^{d_{k}}\epsilon_{k}\binom{i+n-1}{n-1}=\sum_{k=1}^{w}\epsilon_{k}\binom{d_{k}+n}{n}.$
(4)

We note as we let $m$ grow to $\infty$ we have,

$\lim\limits_{m\rightarrow\infty}\frac{1}{m^{n}}\binom{d_{k}+n}{n}=\frac{q^{n}k^{n}}{(2q-1)^{n}}\frac{1}{n!},$

and

$\lim\limits_{m\rightarrow\infty}\frac{1}{m^{n}}\binom{mf(x)-1+n}{n}=f(x)^{n}\frac{1}{n!}.$

These two limits with (3) and (3) imply,

$\sum\limits_{k=0}^{w}\epsilon_{k}q^{n}k^{n}\frac{1}{(2q-1)^{n}}\leq\sum\limits_{x\in{\mathbb{F}}_{q}^{n}}f(x)^{n}.$

As $q^{n}/(2q-1)^{n}=1/(2-1/q)^{n}$ and
$\epsilon_{k}=|B_{k}|/|{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}|$ where $B_{k}$ is
precisely the set of directions for which $f^{*}$ is $k$ we are done.

We now just have to prove (3) holds. For $j\in[d_{i-1}+1,d_{i}]$, using Lemma
2.5 we pick a set of monomials $P(j)$ of degree $j$ of size $\epsilon_{\geq
i}\binom{j+n-1}{n-1}$ such that any non-zero linear combination of those don’t
vanish on the entirety of $B_{\geq i}$ with multiplicity at least $r_{i}$.

Say (3) doesn’t hold, then we can find a non-zero polynomial $Q$ formed by
taking a non-zero linear combination of monomials in
$\bigcup\limits_{j=0}^{d_{w}}P(j)$ such that $Q$ vanishes on
$x\in{\mathbb{F}}_{q}^{n}$ with multiplicity at least $mf(x)$. This is because
vanishing with multiplicity at least $mf(x)$ gives us $\binom{mf(x)+n-1}{n}$
many linear constraints and we have $\sum\limits_{j=0}^{w}|P(j)|$ many
coefficients. $\sum\limits_{j=0}^{w}|P(j)|$ equals the LHS of (3).

Say $Q$ is of degree $d$ with $d_{i-1}<d\leq d_{i}$ for some $i\leq w$. Let
$Q^{H}$ be the highest degree part of $Q$. In other words, $Q^{H}$ is the
degree $d$ part of $Q$. By construction $Q^{H}$ is a non-zero linear
combination of monomials in $P(d)$.

######  Claim 3.1.

For all $u\in B_{\geq i}$,

$\textsf{mult}(Q^{H},u)\geq r_{i}.$

###### Proof.

Let ${\mathbf{j}}\in{\mathbb{Z}}_{\geq 0}^{n}$ with
$\text{wt}({\mathbf{j}})<r_{i}$. $Q^{({\mathbf{j}})}$ is a degree
$d-\text{wt}({\mathbf{j}})$ polynomial. If we consider a $u\in B_{\geq i}$
then there exists a line $L_{u}=\\{a+tu|t\in{\mathbb{F}}_{q}\\}$ such that
$\sum\limits_{x\in L_{u}}f(x)\geq i$. $Q^{({\mathbf{j}})}$ will vanish on each
point $x$ with multiplicity at least $mf(x)-\text{wt}({\mathbf{j}})$. By Lemma
2.4 we see that $Q^{({\mathbf{j}})}(a+tu)$ vanishes with multiplicity at least
$mf(a+tu)-\text{wt}({\mathbf{j}})$ for $t\in{\mathbb{F}}_{q}$. As
$Q^{({\mathbf{j}})}(a+tu)$ is a degree at most $d-\text{wt}({\mathbf{j}})$
polynomial we see that if $Q^{({\mathbf{j}})}(a+tu)$ is non-zero then,

$d-\text{wt}({\mathbf{j}})\geq\sum\limits_{t\in{\mathbb{F}}_{q}}(f(a+tu)-\text{wt}({\mathbf{j}}))\geq
mi-\text{wt}({\mathbf{j}})q.$

As $d\leq d_{i}=qr_{i}-1$ and $\text{wt}({\mathbf{j}})<r_{i}$ we have,

$qr_{i}-1+(q-1)r_{i}>mi.$

This means

$\left\lceil\frac{mk+1}{2q-1}-1\right\rceil=r_{i}>(mi+1)/(2q-1),$

leading to a contradiction. This implies that $Q^{({\mathbf{j}})}(a+tu)$ is
identically $0$. We note the coefficient of $t^{d-\text{wt}({\mathbf{j}})}$ in
$Q^{({\mathbf{j}})}(a+tu)$ is exactly $(Q^{H})^{({\mathbf{j}})}(u)$. As this
argument holds for all ${\mathbf{j}}\in{\mathbb{Z}}_{\geq 0}^{n}$ with
$\text{wt}({\mathbf{j}})<r_{i}$ we have that $Q^{H}$ vanishes on $u$ with
multiplicity $r_{i}$. ∎

The previous claim leads to a contradiction as by construction $Q^{H}$ is a
non-zero linear combination of monomials in $P(d)$ which by Lemma 2.5 cannot
vanish on the entirety of $B_{\geq i}$ with multiplicity at least $r_{i}$. ∎

##  4 Base case: Maximal Kakeya bounds over ${\mathbb{Z}}/p^{k}{\mathbb{Z}}$

The proof here involves replicating the arguments in the proof of Theorem 1.10
while applying polynomial method arguments over the complex torus.

######  Theorem 1.6 (Maximal Kakeya bounds over
${\mathbb{Z}}/p^{k}{\mathbb{Z}}$).

Let $n>0$ be an integer, $p$ prime and $k\in{\mathbb{N}}$. For any function
$f:({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}\rightarrow{\mathbb{N}}$ we have the
following bound,

$\sum\limits_{x\in({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}}|f(x)|^{n}\geq\frac{C_{p^{k},n}}{|{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}|}\left(\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}}|f^{*}(u)|^{n}\right),$

where

$C_{p^{k},n}=\frac{1}{(2(\lceil\log_{p}(\max_{u}f^{*}(u))+\log_{p}(n)\rceil))^{n}}.$

When $p>n$ we can improve $C_{p^{k},n}$ to,

$C_{p^{k},n}=(\lceil\log_{p}(\max_{u}f^{*}(u))\rceil+1)^{-n}(1+n/p)^{-n}.$

###### Proof.

Let $f:({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}\rightarrow{\mathbb{N}}$ and we
define $B_{\geq v}=\\{u||f^{*}(u)|\geq
v,u\in{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}\\}$ and
$B_{v}=\\{u||f^{*}(u)|=v,u\in{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}\\}$.
In other words, $B_{\geq v}$ is the set of directions where the maximal
function is at least $v$ (similarly for $B_{v}$). We also let
$w=\max_{u}f^{*}(u)$. For $m\in{\mathbb{N}}$ and $0\leq v\leq w$, let

$\epsilon_{\geq v}=|B_{\geq
v}|/|{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}|,$
$\epsilon_{v}=|B_{v}|/|{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}|$
$r_{v}=mv.$

By definition, $\epsilon_{\geq v}=\sum\limits_{i=v}^{w}\epsilon_{v}$.

We prove the following for all $m\in{\mathbb{N}}$.

$\displaystyle\sum\limits_{i=1}^{w}\epsilon_{\geq
i}\sum\limits_{j=r_{i-1}+1}^{r_{i}}\left(\left\lceil\binom{j\lceil\log_{p}(j)\rceil^{-1}+n}{n}\right\rceil-\left\lceil\binom{(j-1)\lceil\log_{p}(j-1)\rceil^{-1}+n}{n}\right\rceil\right)$
$\displaystyle\leq$
$\displaystyle\sum\limits_{x\in({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}}\binom{mf(x)+n-1}{n}.$
(5)

We claim (4) proves the Theorem. Let us prove that first. The LHS of (4) can
be re-arranged to give,

$\displaystyle\sum\limits_{i=1}^{w}\epsilon_{\geq
i}\sum\limits_{j=r_{i-1}+1}^{r_{i}}\left(\left\lceil\binom{j\lceil\log_{p}(j)\rceil^{-1}+n}{n}\right\rceil-\left\lceil\binom{(j-1)\lceil\log_{p}(j-1)\rceil^{-1}+n}{n}\right\rceil\right)$
$\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{w}\sum_{v=i}^{w}\sum\limits_{j=r_{i-1}+1}^{r_{i}}\epsilon_{v}\left(\left\lceil\binom{j\lceil\log_{p}(j)\rceil^{-1}+n}{n}\right\rceil-\left\lceil\binom{(j-1)\lceil\log_{p}(j-1)\rceil^{-1}+n}{n}\right\rceil\right)$
$\displaystyle=$
$\displaystyle\sum_{v=1}^{w}\sum\limits_{i=0}^{r_{v}}\epsilon_{v}\left(\left\lceil\binom{j\lceil\log_{p}(j)\rceil^{-1}+n}{n}\right\rceil-\left\lceil\binom{(j-1)\lceil\log_{p}(j-1)\rceil^{-1}+n}{n}\right\rceil\right)$
$\displaystyle=$
$\displaystyle\sum_{v=1}^{w}\epsilon_{v}\left\lceil\binom{r_{v}\lceil\log_{p}(r_{v})\rceil^{-1}+n}{n}\right\rceil.$
(6)

If we set $m=n$ then using (4) and (4) we have,

$\displaystyle\frac{1}{n!}\sum_{v=1}^{w}\epsilon_{v}\frac{v^{n}}{\lceil\log_{p}(v)+\log_{p}(n)\rceil^{n}}\leq
n^{-n}\sum_{v=1}^{w}\epsilon_{v}\left\lceil\binom{r_{v}\lceil\log_{p}(r_{v})\rceil^{-1}+n}{n}\right\rceil\leq\sum\limits_{x\in({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}}\frac{1}{n!}\prod\limits_{i=0}^{n-1}(f(x)+i/n)^{n}.$

As $(f(x)+i/n)\leq 2f(x)$ for integer $f(x)>0$ and $i<n$ we are done. If we
set $m=p$ a similar calculation and using the fact that $(f(x)+i/n)\leq
f(x)(1+(n-1)/p)$ for integer $f(x)>0$ and $i<n$ we will be done.

Now it remains to prove (4) for all $m\in{\mathbb{N}}$.

Fix some $m\in{\mathbb{N}}$. Consider a random matrix $G$ uniformly chosen
from $\textsf{GL}_{n}({\mathbb{Z}}/p^{k}{\mathbb{Z}})$ and let $G\cdot f$ be
the function which maps $x$ to $f(G^{-1}x)$. For a general set $S$ if we let
$G\cdot S$ be the set $\\{G\cdot x|x\in S\\}$ then the following identities
are immediate,

$G\cdot B_{\geq v}=\\{u|(G\cdot f)^{*}(u)|=|f^{*}(G^{-1}u)|\geq
v,u\in{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}\\}$

and

$G\cdot B_{v}=\\{u||(G\cdot
f)^{*}(u)|=v,u\in{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}\\}.$

Consider the matrix $U$ composed of the row vectors
$U_{mw}^{{\bm{\alpha}}}(\zeta^{x})$ for
$x\in({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}$ and
$\text{wt}({\bm{\alpha}})<m(G\cdot f)(x)$. This has rank at most,

$\displaystyle\sum\limits_{x\in({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}}\binom{mf(x)+n-1}{n}.$
(7)

Recall, $V_{mw,p}$ is the set of vectors in $\\{0,\ldots,mw-1\\}^{n}$ such
that it at least has one non-zero coordinate modulo $p$.

Consider the function $m(G\cdot f)$. For any $v=1,\ldots,w$ by construction we
have that for every $u\in G\cdot B_{\geq v}$ there exists a line $L_{u}$ such
that $(G\cdot f)(x)\geq v$. Now, Corollary 2.22 implies that for any $u\in
G\cdot B_{\geq v}$, $u^{\prime}\in V_{mw,p},u^{\prime}\text{ (mod
}p^{k}\text{)}=u$, $j=r_{v-1}+1,\ldots,r_{v}$ and $i=0,\ldots,j-1$ there
exists a ${\mathbb{Q}}(\zeta)$-linear combination of
$U_{mw}^{{\bm{\alpha}}}(\zeta^{x})$ where $x\in L_{u}$ and
$\text{wt}({\bm{\alpha}})\leq m(G\cdot f)(x)-1$ such that under $\psi_{p^{k}}$
we get the $i$th row of $\textsf{Coeff}(M^{j}_{mw,n}(u^{\prime}))$.

This means that there exists a matrix with ${\mathbb{Q}}(\zeta)$-entries such
that multiplying this matrix to $U$ from the left and applying $\psi_{p^{k}}$
gives us a matrix $M$ whose rows are composed of the rows in
$\textsf{Coeff}(M^{j}_{mw,n}(u^{\prime}))$ for $v=1,\ldots,w$, $u\in G\cdot
B_{\geq v}$, $u^{\prime}\in V_{mw,p},u^{\prime}\text{ (mod }p^{k}\text{)}=u$,
$j=r_{v-1}+1,\ldots,r_{v}$ and $i=0,\ldots,j-1$. By Lemma 2.16 we have that
(7) is lower bounded by the rank of $M$. As $G$ is chosen randomly we will
show the expected value of the rank of $M$ is at least

$\sum\limits_{i=1}^{w}\epsilon_{\geq
i}\sum\limits_{j=r_{i-1}+1}^{r_{i}}\left(\left\lceil\binom{j\lceil\log_{p}(j)\rceil^{-1}+n}{n}\right\rceil-\left\lceil\binom{(j-1)\lceil\log_{p}(j-1)\rceil^{-1}+n}{n}\right\rceil\right).$
(8)

This will complete the proof.

By Corollary 2.24 we have sets $A_{1},\ldots,A_{r_{w}}$ of linearly
independent row vectors in the row space of $\textsf{Coeff}(M^{mw}_{mw,n})$
such that elements in $A_{i}$ are a subset of the rows in
$\textsf{Coeff}(M^{i}_{mw,n}(V_{mw,p}))$ and do not belong in the row space of
$\textsf{Coeff}(M^{i-1}_{mw,n}(V_{mw,p}))$. We also have that,

$|A_{i}|=\left\lceil\binom{i\lceil\log_{p}(i)\rceil^{-1}+n}{n}\right\rceil-\left\lceil\binom{(i-1)\lceil\log_{p}(i)\rceil^{-1}+n}{n}\right\rceil$

for $i\in[r_{w}]$.

######  Claim 4.1.

For $j=r_{i-1}+1,\ldots,r_{i}$ any given row in $A_{j}$ will appear in $M$
with probability at least $\epsilon_{\geq i}$

###### Proof.

Let $j$ be some number from $r_{i-1}+1,\ldots,r_{i}$. We note that any given
row $y$ in $A_{j}$ will be from some
$\textsf{Coeff}(M^{j-1}_{mw,n}(u^{\prime}))$ where $u^{\prime}\in V_{mw,p}$.
Now, if $G\cdot B_{\geq i}$ contains $u^{\prime}\text{ (mod }p^{k}\text{)}$
then $y$ will appear in the matrix $M$. As
$\textsf{GL}_{n}({\mathbb{Z}}/p^{k}{\mathbb{Z}})$ acts transitively on
${\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}$ this will happen with
probability at least $\epsilon_{\geq i}$. ∎

Using the linearity of expectation, the above claim immediately implies that
the expected rank of $M$ is at least (8). ∎

##  5 Induction Step: Maximal Kakeya bounds over ${\mathbb{Z}}/N{\mathbb{Z}}$

We first give an outline of the proof in a special case with worse constants
to highlight the overall strategy. The goal is to extend the proof from [DD21]
using the probabilistic method and Corollary 2.24 to prove Theorem 1.9.

Let $N=p^{k_{0}}q^{k_{1}},N_{0}=p^{k_{0}},N_{1}=q^{k_{1}}$ where $p$ and $q$
are distinct primes. Given a set $S\subseteq({\mathbb{Z}}/N{\mathbb{Z}})^{n}$
let $f:({\mathbb{Z}}/N{\mathbb{Z}})^{n}\rightarrow{\mathbb{Z}}_{\geq 0}$ be
its indicator function. Let $L_{u}$ be the line in direction
$u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$ such that
$f^{*}(u)=\sum_{x\in L(u)}f(u)=|S\cap L(u)|$. In other words, $L(u)$ is the
line which has the maximal intersection with $S$ in direction $u$. $L_{u}$ can
decomposed as a product of lines
$L_{0}(u_{0},u_{1})\subseteq({\mathbb{Z}}/N_{0}{\mathbb{Z}})^{n}$ and
$L_{1}(u_{0},u_{1})\subseteq({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n}$ in
directions $u_{0}\in{\mathbb{P}}({\mathbb{Z}}/N_{0}{\mathbb{Z}})^{n-1}$ and
$u_{1}\in{\mathbb{P}}({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n-1}$ respectively.
Note, that $L_{0}(u_{0},u_{1})$ and $L_{0}(u_{0},u_{1})$ can and do depend on
$u=(u_{0},u_{1})$ and not just on $u_{0}$ or $u_{1}$ respectively.

Let $\zeta$ be a primitive $N_{0}$’th root of unity in ${\mathbb{C}}$ and
${\mathbf{1}}_{y}$ be the indicator vector of a point
$y\in({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n}$. We then examine the span of
vectors

$U_{N_{0}}^{{\bm{0}}}(\zeta^{x})\otimes{\mathbf{1}}_{y}$

for $x\in L_{0}(u),y\in
L_{1}(u),u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$ and
${\bm{0}}=(0,\ldots,0)\in{\mathbb{Z}}_{\geq 0}^{n}$. By counting the number of
vectors we see the dimension of the space spanned by these vectors is at most
$|S|$.

For
$(u_{0},u_{1})\in{\mathbb{P}}({\mathbb{Z}}/N_{0}{\mathbb{Z}})^{n-1}\times{\mathbb{P}}({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n-1}$,
we define the function
$g_{L(u_{0},u_{1})}:L_{1}(u_{0},u_{1})\rightarrow{\mathbb{Z}}_{\geq 0}$ as

$g_{L(u_{0},u_{1})}(y)=\sum_{x\in L_{0}(u_{0},u_{1})}f(x,y)=|S\cap
L_{0}(u_{0},u_{1})\times\\{y\\}|.$

We note that $g_{L(u_{0},u_{1})}\leq N_{0}$. In other words,
$g_{L(u_{0},u_{1})}$ is slicing the line $L(u_{0},u_{1})$ along the
${\mathbb{Z}}/N_{0}{\mathbb{Z}}$ part (that is along $u_{0}$) and measuring
its intersection with $S$. For each $L(u)$ we let $B_{\geq
i}(L(u))=\\{y|g_{L(u)}(y)\geq i,y\in L_{1}(u)\\}$ and $b_{\geq
i}(L(u))=|B_{\geq i}(L(u))|$.

Given $L(u_{0},u_{1})$ and $y\in L_{1}(u_{0},u_{1})$, we can use Corollary
2.22 to linearly generate the vector

$M^{g_{L(u_{0},u_{1})}(y)}_{N_{0},n}(u_{0})\otimes{\mathbf{1}}_{y}$

from the vectors $U_{m}^{{\bm{0}}}(\zeta^{x})\otimes{\mathbf{1}}_{y}$ for
$x\in L_{0}(u_{0},u_{1})$ after applying $\psi_{p^{k_{0}}}$. Now by Lemma 2.16
and Fact 2.9 the dimension of the space spanned by the rows in
$\textsf{Coeff}(M^{g_{L(u_{0},u_{1})}(y)}_{N_{0},n}(u_{0}))\otimes{\mathbf{1}}_{y}$
for
$(u_{0},u_{1})\in{\mathbb{P}}({\mathbb{Z}}/N_{0}{\mathbb{Z}})^{n-1}\times{\mathbb{P}}({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n-1}$,
$y\in L_{1}(u_{0},u_{1})$ is at most $|S|$. Let us call this set of rows $M$.

Corollary 2.24 will give us a number of linearly independent vectors
$A_{1},\ldots,A_{N_{0}}$ such that
$A_{i}\subseteq\textsf{Coeff}(M^{i}_{N_{0},n}),i\in[N_{0}]$ and the row-spaces
of $A_{i}$ form disjoint subspaces. Now, the goal is to use Fact 2.12 by
taking each element $z$ in the set $A_{i}$ and collect
$y\in({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n}$ such that
$\textsf{Coeff}(M^{g_{L(u_{0},u_{1})}(y)}_{N_{0},n}(u_{0}))$ contains $z$.
This will give us a set of linearly independent elements from $M$ and their
number will lower bound $|S|$. Note if we know for which $i\in[N_{0}]$ and
$u_{0}\in{\mathbb{P}}({\mathbb{Z}}/N_{0}{\mathbb{Z}})^{n-1}$ a given $z$ is in
$\textsf{Coeff}^{~{}i}_{N_{0},n}(u_{0}))$ then we just need to figure out for
what $y$ there exists a
$u_{1}\in{\mathbb{P}}({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n-1}$ such that
$g_{L(u_{0},u_{1})}(y)=i$.

With the above in mind, let $S(u_{0},i)$ for $u_{0}\in{\mathbb{P}}N_{0}^{n-1}$
and $i\in[N_{0}]$ be the set

$S(u_{0},i)=\bigcup\limits_{u_{1}\in{\mathbb{P}}({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n-1}}B_{\geq
i}(L(u_{0},u_{1})).$

Using Theorem 1.6 (in general here we use the induction hypothesis) we have,

$\textsf{rank}_{{\mathbb{F}}_{p_{0}}}\\{{\mathbf{1}}_{y}|y\in
S(u_{0},i)\\}=|S(u_{0},i)|\geq\sum\limits_{u_{1}\in{\mathbb{P}}({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n-1}}\frac{C_{N_{1},n}b_{\geq
i}(L(u_{0},u_{1}))^{n}}{|{\mathbb{P}}({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n-1}|},$

where $C_{N_{1},n}=2^{-1}(\lceil k_{1}+\log_{q}(n)\rceil)^{-n}$. Now we see
Fact 2.12 and Corollary 2.24 implies that,

$\sum\limits_{u_{0}\in{\mathbb{P}}({\mathbb{Z}}/N_{0}{\mathbb{Z}})^{n-1}}\sum_{j\in[N_{0}]}|S(u_{0},j)||\textsf{Coeff}(M^{j}_{N_{0},n}(u_{0}))\cap
A_{j}|\leq|S|.$

Ideally, the above would be enough to complete the proof but it is not easy to
directly argue the above is large. What we do is apply random rotations on the
${\mathbb{Z}}/N_{0}{\mathbb{Z}}$ component of our function which will lead to
a random permutation of the rows $M^{g_{L(u_{0},u_{1})}(y)}_{N_{0},n}(u_{0})$
along the $u_{0}$ co-ordinate. We then take expectation of the above along
with a very simple partition argument to get the desired bounds. For the
general case and better constants we use multiplicities as in the proof of
Theorem 1.6.

######  Theorem 1.9 (Maximal Kakeya bounds over ${\mathbb{Z}}/N{\mathbb{Z}}$).

Let $n>0$ be an integer and $N=p_{1}^{k_{1}}\ldots p_{r}^{k_{r}}$ with $p_{i}$
primes and $k_{i}\in{\mathbb{N}}$. For any function
$f:({\mathbb{Z}}/N{\mathbb{Z}})^{n}\rightarrow{\mathbb{N}}$ we have the
following bound,

$\sum\limits_{x\in({\mathbb{Z}}/N{\mathbb{Z}})^{n}}|f(x)|^{n}\geq\frac{C_{N,n}}{|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|}\left(\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}|f^{*}(u)|^{n}\right),$

where

$\displaystyle C_{N,n}=$
$\displaystyle\left(\frac{1}{2(\log(\textsf{mweight}(f,p_{1}))+1)\lceil\log_{p_{1}}(\textsf{mweight}(f,p_{1}))+\log_{p_{1}}(n)\rceil}\right)^{n}$
$\displaystyle\cdot\left(\frac{1}{2(k_{r}+\lceil\log_{p_{r}}(n)\rceil)}\prod\limits_{i=2}^{r-1}\frac{1}{2(k_{i}\log(p_{i})+1)(k_{i}+\lceil\log_{p_{i}}(n)\rceil)}\right)^{n}$

.

###### Proof.

The $r=1$ case is Theorem 1.6. Let the theorem be true for some $r$. We will
now prove it for $N=p_{0}^{k_{0}}p_{1}^{k_{1}}\ldots
p_{r}^{k_{r}}=p_{0}^{k_{0}}N_{1}$. Let
$f:({\mathbb{Z}}/N{\mathbb{Z}})^{n}\rightarrow{\mathbb{N}}$ and
$w=\textsf{mweight}(f,p_{0})$. We will use Fact 1.7 to decompose objects into
a ${\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}}$ component and
${\mathbb{Z}}/N_{1}{\mathbb{Z}}$ component.

Let $L(u)$ be the line in direction
$u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$ such that $\sum_{x\in
L(u)}f(x)=f^{*}(u)$. $L(u)=L(u_{0},u_{1})$ can be decomposed into a tensor
product of lines $L_{0}(u)$ in direction
$u_{0}\in{\mathbb{P}}({\mathbb{Z}}/p_{0}^{k_{0}})^{n-1}$ and $L_{1}(u)$ in
direction $u_{1}\in{\mathbb{P}}({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n-1}$. For
each $L(u)$ we define the function
$g_{L(u)}:L_{1}(u)\rightarrow{\mathbb{Z}}_{\geq 0}$ as follows

$g_{L(u)}(y)=\sum_{x\in L_{0}(u)}f(x,y).$

By definition of mweight we have $g_{L(u)}\leq w$. For each $L(u)$ we let
$B_{\geq i}(L(u))=\\{y|g_{L(u)}(y)\geq i,y\in L_{1}(u)\\}$ and $b_{\geq
i}(L(u))=|B_{\geq i}(L(u))|$. $B_{\geq i}(L(u))$ is the set of points $y$ on
$L_{1}(u)$ which have a weight greater than $i$ on the
${\mathbb{Z}}/N_{0}{\mathbb{Z}}$ line $L_{0}(u)\times\\{y\\}$. We similarly
define $B_{=i}(L(u))=\\{y|g_{L(u)}(y)=i,y\in L_{1}(u)\\}$ and
$b_{=i}(L(u))=|B_{=i}(L(u))|$.

Let $\zeta$ be a $p_{0}^{k_{0}}$’th root of unity. Consider a random matrix
$G$ uniformly chosen from
$\textsf{GL}_{n}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})$. Consider the
function $f_{G}(x,y)=f(G^{-1}\cdot x,y)$ where
$x\in({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})^{n}$ and
$y\in({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n}$. For any set $S$ we also define
$G\cdot S=\\{G\cdot x|x\in S\\}$ where $G$ acts on just the
${\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}}$ part of $x$ if
$x\in({\mathbb{Z}}/N{\mathbb{Z}})^{n}$ and is the usual action if
$x\in({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})^{n}$. We now consider the matrix
$U_{G}$ composed of the row vectors

$U^{{\bm{\alpha}}}_{mw}(\zeta^{G\cdot x})\otimes{\mathbf{1}}_{y}$

for all $x\in({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})^{n}$ and
$y\in({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n}$ and
${\bm{\alpha}}\in{\mathbb{Z}}_{\geq 0}^{n}$ with
$\text{wt}({\bm{\alpha}})<mf_{G}(x,y)$. The rank of $U_{G}$ is bounded above
by

$\sum\limits_{x\in({\mathbb{Z}}/N{\mathbb{Z}})^{n}}\binom{mf(x)+n-1}{n}.$ (9)

Recall, $V_{mw,p_{0}}$ is the set of vectors in $\\{0,\ldots,mw-1\\}^{n}$ such
that it at least has one non-zero coordinate modulo $p_{0}$.

Consider the function $mf_{G}$. We see that by construction the line

$G\cdot L(u_{0},u_{1})=(G\cdot L_{0}(u_{0},u_{1}),L_{1}(u_{0},u_{1}))$

will be a line in direction $(G\cdot u_{0},u_{1})$ such $\sum_{x\in G\cdot
L(u_{0},u_{1})}f_{G}(x)=f^{*}(u_{0},u_{1})=f_{G}^{*}(G\cdot u_{0},u_{1})$.
Now, Corollary 2.22 implies that for a $y\in L_{1}(u_{0},u_{1})$ and
$u_{0}^{\prime}\in V_{mw,p_{0}},u_{0}^{\prime}\text{(mod
}p_{0}^{k_{0}}\text{)}=G\cdot
u_{0},j=1,\ldots,mg_{L(u_{0},u_{1})}(y),i=0,\ldots,j-1$ we have a
${\mathbb{Q}}(\zeta)$-linear combination of
$U_{mw}^{{\bm{\alpha}}}(\zeta^{x})$ where $x\in G\cdot L_{0}(u_{0},u_{1})$ and
$\text{wt}({\bm{\alpha}})\leq mf_{G}(x,y)-1$ such that under
$\psi_{p_{0}^{k_{0}}}$ we get the $i$th row of
$\textsf{Coeff}(M^{j}_{mw,n}(u_{0}^{\prime}))$.

This means that there exists a matrix with ${\mathbb{Q}}(\zeta)$-entries such
that multiplying this matrix to $U$ from the left and applying
$\psi_{p_{0}^{k_{0}}}$ gives us a matrix $M_{G}$ whose rows are composed of
the rows in
$\textsf{Coeff}(M^{j}_{mw,n}(u_{0}^{\prime}))\otimes{\mathbf{1}}_{y}$ for
$(u_{0},u_{1})\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$, $y\in
L_{1}(u_{0},u_{1})$ and $u_{0}^{\prime}\in
V_{mw,p_{0}},u_{0}^{\prime}\text{(mod }p_{0}^{k_{0}}\text{)}=G\cdot u_{0},$
and $j=1,\ldots,mg_{L(u_{0},u_{1})}(y)$.

By construction and Lemma 2.16, the ${\mathbb{F}}_{p_{0}}$-rank of $M_{G}$
lower bounds the rank of $U_{G}$ and hence lower bounds (9). In general, it
suffices to lower bound the expected rank of $M_{G}$ over a random choice of
$G\in\textsf{GL}_{n}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})$. We do that in
the next claim.

######  Claim 5.1.

$\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1},i\in[w]}\frac{C_{N_{1},n}b_{\geq
i}(L(u))^{n}}{|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|}\cdot\left(\left\lceil\binom{\frac{mi}{\lceil\log_{p_{0}}(mi)\rceil}+n}{n}\right\rceil-\left\lceil\binom{\frac{m(i-1)}{\lceil\log_{p_{0}}(m(i-1))\rceil}+n}{n}\right\rceil\right)$

is a lower bound for
${\mathbb{E}}_{G\in\textsf{GL}_{n}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})}[\textsf{rank}_{{\mathbb{F}}_{p_{0}}}M_{G}]$
where

$C_{N_{1},n}=\left(\prod_{j=2}^{r-1}\frac{1}{k_{j}\log(p_{j})+1}\prod\limits_{i=2}^{r}\frac{1}{(2(k_{i}+\lceil\log_{p_{i}}(n)\rceil))}\right)^{n}.$

###### Proof.

Let $S(u_{0},i)$ for
$u_{0}\in{\mathbb{P}}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})^{n-1}$ and
$i\in[w]$ be the set

$S(u_{0},i)=\bigcup\limits_{u_{1}\in{\mathbb{P}}({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n-1}}B_{\geq
i}(L(u_{0},u_{1})).$

Using the induction hypothesis (in particular we use Theorem 1.2 for $r$ prime
factors) we have,

$\textsf{rank}_{{\mathbb{F}}_{p_{0}}}\\{{\mathbf{1}}_{y}|y\in
S(u_{0},i)\\}=|S(u_{0},i)|\geq\sum\limits_{u_{1}\in{\mathbb{P}}({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n-1}}\frac{C_{N_{1},n}b_{\geq
i}(L(u_{0},u_{1}))^{n}}{|{\mathbb{P}}({\mathbb{Z}}/N_{1}{\mathbb{Z}})^{n-1}|}.$
(10)

Recall for a fixed
$G\in\textsf{GL}_{n}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})$, $M_{G}$’s rows
are the rows in
$\textsf{Coeff}(M^{j}_{mw,n}(u_{0}^{\prime}))\otimes{\mathbf{1}}_{y}$ for
$(u_{0},u_{1})\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$ ,$y\in
L_{1}(u_{0},u_{1})$ and $u_{0}^{\prime}\in
V_{mw,p_{0}},u_{0}^{\prime}\text{(mod }p_{0}^{k_{0}}\text{)}=G\cdot u_{0},$
and $j\in[mg_{L(u_{0},u_{1})}(y)]$.

We can easily re-write this condition to note that $M_{G}$’s rows are the rows
in $\textsf{Coeff}(M^{j}_{mw,n}(u_{0}^{\prime}))\otimes{\mathbf{1}}_{y}$ for
$u_{0}\in{\mathbb{P}}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})^{n-1}$,
$u_{0}^{\prime}\in V_{mw,p_{0}},u_{0}^{\prime}\text{(mod
}p_{0}^{k_{0}}\text{)}=G\cdot u_{0},$ and $y\in S(u_{0},\lceil j/m\rceil)$ for
$j\in[mw]$.

By Corollary 2.24 we have a set $A=A_{1}\cup\ldots\cup A_{mw}$ of linearly
independent row vectors in the row space of $\textsf{Coeff}(M^{mw}_{mw,n})$
such that $A_{i}$ are a subset of rows in
$\textsf{Coeff}(M^{i}_{mw,n}(V_{m,p_{0}}))$ and do not belong in the row space
of $\textsf{Coeff}(M^{i-1}_{mw,n})$ for $i\in[mw]$. We also have

$|A_{i}|=\left\lceil\binom{i\lceil\log_{p_{0}}(i)\rceil^{-1}+n}{n}\right\rceil-\left\lceil\binom{(i-1)\lceil\log_{p_{0}}(i-1)\rceil^{-1}+n}{n}\right\rceil$

for $i\in[mw]$.

For a $u_{0}\in{\mathbb{P}}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})^{n-1}$,
let $V^{\prime}(u_{0})$ be the set of $u_{0}^{\prime}\in V_{mw,p_{0}}$ such
that $u_{0}^{\prime}\text{(mod }p_{0}^{k_{0}}\text{)}=u_{0}$.

Now Fact 2.12 implies that,

$\sum\limits_{u_{0}\in{\mathbb{P}}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})^{n-1}}\sum_{j\in[mw]}|S(u_{0},\lceil
j/m\rceil)|\left(\sum\limits_{u^{\prime}_{0}\in V^{\prime}(G\cdot
u_{0})}|\textsf{Coeff}(M^{j}_{mw,n}(u^{\prime}_{0})\cap
A_{j}|\right)\leq\textsf{rank}_{{\mathbb{F}}_{p_{0}}}M_{G}.$

By (10), to prove the claim it now suffices to show that

${\mathbb{E}}_{G\in\textsf{GL}_{n}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})}\left[\sum\limits_{u^{\prime}_{0}\in
V^{\prime}(G\cdot u_{0})}|\textsf{Coeff}(M^{j}_{mw,n}(u^{\prime}_{0})\cap
A_{j}|\right]\geq\frac{|A_{j}|}{|{\mathbb{P}}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})^{n-1}|}.$

A given row vector in $A_{j}$ corresponds to a row vector in
$M^{j}_{mw,n}(V^{\prime}(u^{\prime}))$ for some
$u^{\prime}\in{\mathbb{P}}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})^{n-1}$.
This means that $A_{j}$ appears in
$\textsf{Coeff}(M^{j}_{mw,n}(u^{\prime}_{0}))$ for some $u^{\prime}_{0}\in
V^{\prime}(G\cdot u_{0})$ if and only if $G\cdot u_{0}=u^{\prime}$. As the
action of $\textsf{GL}_{n}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})$ is
transitive on ${\mathbb{P}}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})^{n-1}$ we
see that the probability of this happening is
$|{\mathbb{P}}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})^{n-1}|^{-1}$. Linearity
of expectation then completes the proof. ∎

We will also need another simple claim.

######  Claim 5.2.

For all $u$,

$\sum\limits_{i\in[w]}b_{\geq
i}(L(u))^{n}(i^{n}-(i-1)^{n})\geq\left(\frac{|f^{*}(u)|}{\log(w)+1}\right)^{n}.$

###### Proof.

By definition we have

$\displaystyle b_{\geq 1}(L(u))\geq b_{\geq 2}(L(u))\geq\ldots\geq b_{\geq
w}(L(u)).$ (11)

We will show that there exists some $j\in[w]$ such that $b_{\geq j}(L(u))\geq
f^{*}(u)/(j(\log(w)+1))$. Then using (11) we will be done.

Say for all $j\in[w]$ we have $b_{\geq j}(L(u))<f^{*}(u)/(j(\log(w)+1))$. By
the choice of $L(u)$ we have

$\sum\limits_{i\in[w]}b_{=i}(L(u))i=\sum\limits_{i\in[w]}b_{\geq
i}(L(u))=f^{*}(u).$

But the above leads to a contradiction if we sum $b_{\geq
i}(L(u))<f^{*}(u)/(i(\log(w)+1))$ for $i\in[w]$. ∎

We can re-arrange the summation in the lower bound of Claim 5.1 to get,

$\displaystyle\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1},i\in[w]}\frac{C_{N_{1},n}b_{\geq
i}(L(u))^{n}}{|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|}\cdot\left(\left\lceil\binom{\frac{mi}{\lceil\log_{p_{0}}(mi)\rceil}+n}{n}\right\rceil-\left\lceil\binom{\frac{m(i-1)}{\lceil\log_{p_{0}}(m(i-1))\rceil}+n}{n}\right\rceil\right)$
$\displaystyle\geq$
$\displaystyle\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1},i\in[w]}\frac{C_{N_{1},n}}{|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|}\cdot\left\lceil\binom{\frac{mi}{\lceil\log_{p_{0}}(mi)\rceil}+n}{n}\right\rceil(b_{\geq
i}(L(u))^{n}-b_{\geq i+1}(L(u))^{n})$ $\displaystyle\geq$
$\displaystyle\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1},i\in[w]}\frac{C_{N_{1},n}}{|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|}\cdot\frac{(mi)^{n}}{\lceil\log_{p_{0}}(w)+\log_{p_{0}}(m)\rceil^{n}}(b_{\geq
i}(L(u))^{n}-b_{\geq i+1}(L(u))^{n})$ $\displaystyle\geq$
$\displaystyle\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1},i\in[w]}\frac{C_{N_{1},n}}{|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|}\cdot\frac{b_{\geq
i}(L(u))^{n}}{\lceil\log_{p_{0}}(w)+\log_{p_{0}}(m)\rceil^{n}}((mi)^{n}-(m(i-1))^{n}).$

Setting $m=n$ in the above inequality combined with Claim 5.1 and the fact
that
${\mathbb{E}}_{G\in\textsf{GL}_{n}({\mathbb{Z}}/p_{0}^{k_{0}}{\mathbb{Z}})}[\textsf{rank}_{{\mathbb{F}}_{p_{0}}}M_{G}]$
lower bounds (9) gives us

$\frac{1}{n!}\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1},i\in[w]}\frac{C_{N_{1},n}}{|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|}\cdot\frac{b_{\geq
i}(L(u))(i^{n}-(i-1)^{n})}{\lceil\log_{p_{0}}(w)+\log_{p_{0}}(n)\rceil^{n}}\leq\sum\limits_{x\in({\mathbb{Z}}/N{\mathbb{Z}})^{n}}\frac{1}{n!}\prod\limits_{i=0}^{n-1}(f(x)+i/n).$

Using the fact that $f(x)+i/n\leq 2f(x)$ for $f(x)\geq 1$ and Claim 5.2 we are
done. ∎

##  6 Proof of Conjecture 1.11

######  Conjecture 1.11 (Kakeya Maximal conjecture over
${\mathbb{Z}}/N{\mathbb{Z}}$).

For all $\epsilon>0$ and $n\in{\mathbb{N}}$ there exists a constant
$C_{n,\epsilon}$ such that the following holds: For a choice of a line $L(u)$
for each direction $u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$ we
have,

$\left\|\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}{\mathbf{1}}_{L(u)}\right\|_{\ell^{n/(n-1)}}\leq
C_{n,\epsilon}N^{\epsilon}\left(\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}|L(u)|\right)^{(n-1)/n}.$

We note
$2N^{n-1}\geq\left(\sum_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}|L(u)|\right)^{(n-1)/n}\geq
N^{n-1}$ so it suffices to replace the right hand side by $N^{n-1}$.

We will also need the following known number theoretic estimate which follows
from Theorem 315 in [HW75].

######  Fact 6.1.

For a natural number $N$ with prime factorization $p_{1}^{k_{1}}\ldots
p_{r}^{k_{r}}$ we have,

$\prod\limits_{i=1}^{r}k_{i}\log(p_{i})=N^{o(1)},$

where $o(1)$ tends to $0$ as $N\rightarrow\infty$.

###### Proof of Conjecture 1.11.

Throughout this proof we treat $n$ as fixed. In particular we hide any
functions only depending on $n$ in the $O$ and $\Omega$ notation.

Let $N=p_{1}^{k_{1}}\ldots p_{r}^{k_{r}}$ for primes $k_{1}>\ldots>k_{r}$.

Let
$h(x)=\sum_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}{\mathbf{1}}_{L(u)}(x)$
and $g(x)=h(x)^{1/(n-1)}$. We note $\|g\|_{\infty}\leq 2N$.

We immediately have the following identity,

$\left\|\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}{\mathbf{1}}_{L(u)}\right\|_{\ell^{n/(n-1)}}=\|h\|_{\ell^{n/(n-1)}}=\frac{\langle
g,h\rangle}{\|g\|_{\ell^{n}}}.$ (12)

Let $f(x)=\lceil g(x)\rceil$. We note $g(x)\leq f(x)\leq 2g(x)$ and
$\|f\|_{\infty}\leq 2\|g\|_{\infty}\leq 4N$. This also means that
$\textsf{mweight}(f,p_{1})\leq 4Np_{1}^{k}$. By the definition of the maximal
function we note $f^{*}(u)\geq\sum_{x\in L(u)}f(x)$. We let
$f^{\prime}(u)=\sum_{x\in L(u)}f(x)$ and $g^{\prime}(u)=\sum_{x\in L(u)}g(u)$
for $u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}$.

Now, using $f^{*}\geq f^{\prime}$ and Theorem 1.9 we have,

$\|f\|_{\ell^{n}}\geq|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|^{-1/n}C^{1/n}\|f^{*}\|_{\ell^{n}}\geq|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|^{-1/n}C^{1/n}\|f^{\prime}\|_{\ell^{n}}$
(13)

where

$C^{1/n}=\Omega\left(\frac{1}{\log_{p_{1}}(Np_{1}^{k}n)+1}\prod\limits_{i=2}^{r}\frac{1}{(k_{i}\log(p_{i})+1)(2(k_{i}+\lceil\log_{p_{i}}(n)\rceil))}\right)\geq\Omega(N^{-o(1)})$
(14)

using Fact 6.1 ($o(1)$ is a function which goes to $0$ as $N\rightarrow\infty$
and $n$ is fixed). Putting (12), (13), and (14) together with the fact that
$g(x)\leq f(x)\leq 2g(x)$ we get,

$\displaystyle\left\|\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}{\mathbf{1}}_{L(u)}\right\|_{\ell^{n/(n-1)}}$
$\displaystyle\leq 2\frac{\langle h,f\rangle}{\|f\|_{\ell^{n}}}\leq
2C^{-1/n}|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|^{1/n}\frac{\langle
h,f\rangle}{\|f^{\prime}\|_{\ell^{n}}}$ $\displaystyle\leq
O(N^{o(1)})|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|^{1/n}\frac{\langle
h,f\rangle}{\|f^{\prime}\|_{\ell^{n}}}$
$\displaystyle=O(N^{o(1)})|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|^{1/n}\frac{\sum\limits_{x\in({\mathbb{Z}}/N{\mathbb{Z}})^{n}}\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}{\mathbf{1}}_{L(u)}(x)f(x)}{\|f^{\prime}\|_{\ell^{n}}}$
$\displaystyle=O(N^{o(1)})|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|^{1/n}\frac{\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}\sum\limits_{x\in
L(u)}f(x)}{\|f^{\prime}\|_{\ell^{n}}}$
$\displaystyle=O(N^{o(1)})|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|^{1/n}\frac{\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}f^{\prime}(u)}{\|f^{\prime}\|_{\ell^{n}}}.$

Finally, applying Hölder’s inequality gives us,

$\displaystyle\left\|\sum\limits_{u\in{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}}{\mathbf{1}}_{L(u)}\right\|_{\ell^{n/(n-1)}}$
$\displaystyle\leq
O(N^{o(1)})|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|^{1/n}\|1\|_{\ell^{n/(n-1)}({\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1})}$
$\displaystyle\leq
O(N^{o(1)})|{\mathbb{P}}({\mathbb{Z}}/N{\mathbb{Z}})^{n-1}|\leq
O(N^{n-1+o(1)}).$

As $N$ grows this completes the proof. ∎

## References

  * [Ars21a] Bodan Arsovski.  The p-adic Kakeya conjecture.  arXiv preprint 2108.03750v1, 08-08-2021.
  * [Ars21b] Bodan Arsovski.  The p-adic Kakeya conjecture.  arXiv preprint 2108.03750v3, 11-01-2021.
  * [BC21] Boris Bukh and Ting-Wei Chao.  Sharp density bounds on the finite field Kakeya.  arXiv preprint 2108.00074, 2021.
  * [Car18] Xavier Caruso.  Almost all non-archimedean Kakeya sets have measure zero.  Confluentes Mathematici, 10(1):3–40, 2018.
  * [DD21] Manik Dhar and Zeev Dvir.  Proof of the Kakeya set conjecture over rings of integers modulo square-free N.  Combinatorial Theory, to appear, 2021.
  * [DD22] Manik Dhar and Zeev Dvir.  Linear hashing with $\ell_{\infty}$ guarantees and two-sided kakeya bounds, 2022.
  * [DH13] Evan P. Dummit and Márton Hablicsek.  Kakeya sets over non-archimedean local rings.  Mathematika, 59(2):257–266, 2013.
  * [Dha21] Manik Dhar.  The kakeya set conjecture for $\mathbb{Z}/\text{{N}}\mathbb{Z}$ for general N.  arXiv preprint 2110.14889, 2021.
  * [DKSS13] Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan.  Extensions to the method of multiplicities, with applications to Kakeya sets and mergers.  SIAM Journal on Computing, 42(6):2305–2328, 2013.
  * [Dvi09] Zeev Dvir.  On the size of Kakeya sets in finite fields.  Journal of the American Mathematical Society, 22(4):1093–1097, 2009\.
  * [EOT10] Jordan S Ellenberg, Richard Oberlin, and Terence Tao.  The Kakeya set and maximal conjectures for algebraic varieties over finite fields.  Mathematika, 56(1):1–25, 2010.
  * [Fra16] Robert Fraser.  Kakeya-type sets in local fields with finite residue field.  Mathematika, 62(2):614–629, Jan 2016.
  * [HW75] G.H. Hardy and E.M. Wright.  An Introduction to the Theory of Numbers.  4th edition, 1975.
  * [HW18] Jonathan Hickman and James Wright.  The Fourier restriction and Kakeya problems over rings of integers modulo N.  Discrete Analysis, (11), 2018.
  * [Luc78] Edouard Lucas.  Théorie des fonctions numériques simplement périodiques.  American Journal of Mathematics, 1(4):289–321, 1878.
  * [Sal22] Alejo Salvatore.  The kakeya conjecture on local fields of positive characteristic.  arXiv preprint arXiv:2202.11344, 2022.
  * [Sch79] Jacob T Schwartz.  Probabilistic algorithms for verification of polynomial identities.  In International Symposium on Symbolic and Algebraic Manipulation, pages 200–215. Springer, 1979.
  * [SS08] Shubhangi Saraf and Madhu Sudan.  An improved lower bound on the size of Kakeya sets over finite fields.  Anal. PDE, 1(3):375–379, 2008.
  * [Wol99] Thomas Wolff.  Recent work connected with the Kakeya problem.  Prospects in mathematics (Princeton,NJ, 1996), pages 29–162, 1999\.
  * [Zip79] Richard Zippel.  Probabilistic algorithms for sparse polynomials.  In Edward W. Ng, editor, Symbolic and Algebraic Computation, pages 216–226, Berlin, Heidelberg, 1979. Springer Berlin Heidelberg.

##  Appendix A Proof of Lemma 2.5

The proof here only involves a minor adaptation of the ideas in [DD22].

First, we state the multiplicity version of the Schwartz-Zippel bound [Sch79,
Zip79] (see [DKSS13] for a proof). We denote by
${\mathbb{F}}[x_{1},..,x_{n}]_{\leq d}$ the space of polynomials of total
degree at most $d$ with coefficients in ${\mathbb{F}}$.

######  Lemma A.1 (Schwartz-Zippel with multiplicities).

Let ${\mathbb{F}}$ be a field, $d\in{\mathbb{Z}}_{\geq 0}$ and let
$f\in{\mathbb{F}}[x_{1},..,x_{n}]_{\leq d}$ be a non-zero polynomial. Then,
for any finite subset $U\subseteq{\mathbb{F}}$ ,

$\sum\limits_{a\in U^{n}}\textsf{mult}(f,a)\leq d|U|^{n-1}.$

###  A.1 The EVAL matrix, its submatrices and their ranks

Our main object of interest is the matrix encoding the evaluation of a subset
of monomials (with their derivatives) on a subset of points.

######  Definition A.2 ($\textsf{EVAL}^{m}(S,W)$ matrix).

Let ${\mathbb{F}}$ be a field, and let $n,m\in\mathbb{N}$. Given a set
$S\subset{\mathbb{F}}^{n}$ and a set of monomials
$W\subset{\mathbb{F}}[x_{1},\ldots,x_{n}]$, we let $\textsf{EVAL}^{m}(S,W)$
denote an $|S|\binom{m-1+n}{n}\times|W|$ matrix whose columns are indexed by
$W$ and rows are indexed by tuples $(x,\mathbf{j})\in
S\times{\mathbb{Z}}_{\geq 0}^{n}$ s.t. $\text{wt}(\mathbf{j})<m$. The
$((x,\mathbf{j}),f)$th entry of this matrix is,

$f^{(\mathbf{j})}(x).$

In other words, the $(x,\mathbf{j})$th row of the matrix consists of the
evaluation of the $\mathbf{j}$’th Hasse derivative of all $f\in W$ at $x$.
Equivalently, the $f$’th column of the matrix consists of the evaluations of
weight strictly less than $m$ Hasse derivatives of $f$ at all points in $S$.

Let $W_{d,n}$ denote the set of monomials in $n$-variables
$x_{1},\ldots,x_{n}$ of degree at exactly $d$. Our first lemma shows that the
${\mathbb{F}}_{q}$-rank of
$\textsf{EVAL}^{m}({\mathbb{P}}{\mathbb{F}}_{q}^{n-1},W_{d,n})$ is maximal
whenever $d$ is not too large. This is essentially the Schwartz-Zippel lemma
since it means that a polynomial of bounded degree could be recovered from its
evaluations (up to high enough order) on a product set and evaluations of
homogenous polynomials over ${\mathbb{P}}{\mathbb{F}}_{q}^{n-1}$ gives us
evaluations over the entirety of ${\mathbb{F}}_{q}^{n}$.

######  Lemma A.3 (Rank of
$\textsf{EVAL}^{m}({\mathbb{P}}{\mathbb{F}}_{q}^{n-1},W_{d,n})$).

Let $m\in{\mathbb{N}}$ then for all $d<mq$ we have,

$\text{rank}_{{\mathbb{F}}_{q}}\textsf{EVAL}^{m}({\mathbb{P}}{\mathbb{F}}_{q}^{n-1},W_{d,n})=|W_{d,n}|=\binom{d+n-1}{n-1}.$

###### Proof.

Let $v_{m}$ be the column of
$\textsf{EVAL}^{m}({\mathbb{P}}{\mathbb{F}}_{q}^{n-1},W_{d,n})$ corresponding
to the monomial $m\in W_{d,n}$. The linear combination $\alpha_{m}v_{m}$ is
precisely the evaluation of Hasse derivative of weight strictly less than $m$
of the homogenous polynomial $\alpha_{m}m$ over
${\mathbb{P}}{\mathbb{F}}_{q}^{n-1}$. If such a linear combination is zero
then we get a homogenous linear polynomial of degree $d<mq$ which vanishes on
the entirety of ${\mathbb{P}}{\mathbb{F}}_{q}^{n-1}$ with multiplicity at
least $m$. As the polynomial is homogenous the same holds over the entirety of
${\mathbb{F}}_{q}^{n}$. This immediately contradicts Lemma A.1. ∎

Our final lemma, which is the heart of this section, shows that if we have a
set $S$ of a $\delta$ fraction of points from
${\mathbb{P}}{\mathbb{F}}_{q}^{n-1}$ then
$\text{rank}_{{\mathbb{F}}_{q}}\textsf{EVAL}^{m}(S,W_{d,n})$ is at least a
$\delta$ fraction of
$\text{rank}_{{\mathbb{F}}_{q}}\textsf{EVAL}^{m}({\mathbb{P}}{\mathbb{F}}_{q}^{n-1},W_{d,n})$

######  Lemma A.4 (Rank of $\textsf{EVAL}^{m}(S,W_{d,n})$).

Let $m\in{\mathbb{N}}$ and $S\subseteq{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}$ with
$|S|\geq\delta|{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}|,\delta\in[0,1]$ then for
all $d<mq$ we have,

$\text{rank}_{{\mathbb{F}}_{q}}\textsf{EVAL}^{m}(S,W_{d,n})\geq\delta\cdot|W_{d,n}|=\delta\binom{d+n}{n-1}.$

We note that Lemma 2.5 is a simple corollary of the above.

###### Proof.

Consider $S\subseteq{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}$ such that
$|S|=\delta|{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}|$. For any
$M\in\text{GL}_{n}({\mathbb{F}}_{q})$ let $M\cdot S=\\{M\cdot y|y\in S\\}$.

######  Claim A.5.

$\textsf{rank}_{{\mathbb{F}}_{q}}\textsf{EVAL}^{m}(S,W_{d,n})=\textsf{rank}_{{\mathbb{F}}_{q}}\textsf{EVAL}^{m}(M\cdot
S,W_{d,n}).$

###### Proof.

We will prove this statement by constructing an isomorphism between the
column-space of the two matrices. An element in the column space of
$\textsf{EVAL}^{m}(S,W_{d,n})$ is the evaluation of the weight strictly less
than $m$ Hasse derivatives on $S$ of a degree $d$ homogenous polynomial
$f(x)\in{\mathbb{F}}_{q}[x_{1},\ldots,x_{n}]$. We map such a vector to the
evaluation of the weight strictly less than $m$ Hasse derivatives on $M\cdot
S$ of the polynomial $f(M^{-1}x)$ which will also be homogenous of degree $d$.
The choice of $f$ in the beginning can be ambiguous but if there are two
polynomials $f(x)$ and $g(x)$ having the same evaluation of weight strictly
less than $m$ Hasse derivatives over $S$ then $f(x)-g(x)$ vanishes on $S$ with
multiplicity at least $m$. By Lemma 2.2, $f(M^{-1}x)-g(M^{-1}x)$ vanishes on
$M\cdot S$ with multiplicity $m$ which implies $f(M^{-1}x)$ and $g(M^{-1}x)$
evaluate to the same weight strictly less than $m$ Hasse derivatives over
$M\cdot S$. The inverse map can be similarly constructed. ∎

The above claim shows it suffices to show the rank bound for any $M\cdot S$
where $M\in\text{GL}_{n}({\mathbb{F}}_{q})$. We do this by a probabilistic
method argument.

The previous Lemma implies that
$\textsf{EVAL}^{m}({\mathbb{P}}{\mathbb{F}}_{q}^{n-1},W_{d,n})$ has
${\mathbb{F}}_{q}$-rank $|W_{d,n}|$. As this is a matrix with
${\mathbb{F}}_{q}$ entries this means that there exists a
$|W_{d,n}|=\binom{d+n-1}{n-1}$ subset of rows $R$ of
$\textsf{EVAL}^{m}({\mathbb{P}}{\mathbb{F}}_{q}^{n-1},W_{d,n})$ which are
linearly independent.

These rows are indexed by tuples

$(x,{\mathbf{i}})\in{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}\times{\mathbb{Z}}_{\geq
0}^{n}$

with $\text{wt}({\mathbf{i}})<m$. The $(x,{\mathbf{i}})$th row is the
evaluation of the ${\mathbf{i}}$th Hasse Derivative at $x$ of the monomials in
$W_{d,n}$.

We pick an $M\in\text{GL}_{n}({\mathbb{F}}_{q})$ uniformly at random. We now
calculate the expected fraction of the rows from $R$ which appear in
$\textsf{EVAL}^{m}(M\cdot S,W_{d,n})$.

A row in $R$ indexed by
$(x,{\mathbf{i}})\in{\mathbb{P}}{\mathbb{F}}_{q}^{n-1}\times{\mathbb{Z}}_{\geq
0}^{n}$ will appear in $\textsf{EVAL}^{m}(M\cdot S,W_{d,n})$ if and only if
$x\in M\cdot S$. As the action of $\text{GL}_{n}({\mathbb{F}}_{q})$ on
${\mathbb{P}}{\mathbb{F}}_{q}^{n-1}$ is transitive we see that this happens
with probability at least $\delta$. This means the expected fraction of rows
in $R$ appearing in $\textsf{EVAL}^{m}(M\cdot S,W_{d,n})$ is at least
$\delta$. This ensures that there is some matrix $M$ such that
$\textsf{EVAL}^{m}(M\cdot S,W_{d,n})$ and hence $\textsf{EVAL}^{m}(M\cdot
S,W_{d,n})$ has ${\mathbb{F}}_{q}$-rank at least $\delta|W_{d,n}|$. ∎

##  Appendix B Proof of Lemma 2.18

As we need a small modification, we reproduce the analysis of [Dha21, Ars21a]
here. We first show $M_{\ell,1}$ has an explicit decomposition as a product of
lower and upper triangular matrices.

######  Lemma B.1 (Lemma 5 in [Ars21a]).

Let $V_{m}$ for $m\in{\mathbb{N}}$ be an $m\times m$ matrix whose row and
columns are labelled by elements in $\\{0,\ldots,m-1\\}$ such that its $i,j$th
entry is $z^{ij}\in{\mathbb{Z}}[z]$.

In this setting, there exists a lower triangular matrix $L_{m}$ over
${\mathbb{Z}}[z]$ with ones on the diagonal such that its inverse is also
lower triangular with entries in ${\mathbb{Z}}[z]$ with ones on the diagonal,
and an upper triangular matrix $D_{m}$ over ${\mathbb{Z}}[z]$ whose rows and
columns are indexed by points in $\\{0,\ldots,m-1\\}$ such that the $j$th
diagonal entry for $j\in\\{0,\ldots,m-1\\}$ equals

$\displaystyle D_{m}(j,j)=\prod_{i=0}^{j-1}(z^{j}-z^{i})$

such that $V_{m}=L_{m}D_{m}$.

This statement is precisely Lemma 5 in [Ars21a]. It is easy to prove by doing
elementary row operations on the Vandermonde matrix $V_{m}$.

We will also need Lucas’s theorem from [Luc78].

######  Theorem B.2 (Lucas’s Theorem [Luc78]).

Let $p$ be a prime and Given two natural numbers $a$ and $b$ with expansion
$a_{k}p^{k}+\ldots+a_{1}p+a_{0}$ and $b_{k}p^{k}+\ldots+b_{0}$ in base $p$ we
have,

$\binom{a}{b}\text{(mod
}p\text{)}=\prod\limits_{i=0}^{k}\binom{a_{i}}{b_{i}}\text{(mod }p\text{)}.$

A particular consequence is that $\binom{a}{b}$ is non-zero if and only if
every digit in base-$p$ of $b$ is at most as large as every digit in base-$p$
of $a$.

######  Lemma 2.18.

$m\geq\ell$ then the ${\mathbb{F}}_{p}$-rank of $M^{\ell}_{\ell,n}$ is at
least

$\text{rank}_{{\mathbb{F}}_{p}}M_{\ell,n}\geq\left\lceil\binom{\ell\lceil\log_{p}(\ell)\rceil^{-1}+n}{n}\right\rceil.$

###### Proof.

Using the previous lemma we note that $V_{m}=L_{m}D_{m}$. Under the ring map
$f$ from ${\mathbb{Z}}[z]$ to ${\mathbb{Z}}[z]/\langle(z-1)^{\ell}\rangle$,
$V_{m}=L_{m}D_{m}$ becomes $M^{\ell}_{m,1}=\overline{L}_{m}\overline{D}_{m}$
where $\overline{L}_{m}$ and $\overline{D}_{m}$ are the matrices $f(L_{\ell})$
and $f(D_{\ell})$ respectively.

We next notice that $M^{\ell}_{m,n}$ is $M_{\ell,1}$ tensored with itself $n$
times which we denote as $M^{\ell}_{m,n}=(M^{\ell}_{m,1})^{\otimes n}$. Using
$M^{\ell}_{m,1}=\overline{L}_{m}\overline{D}_{m}$ and Fact 2.11 we have
$M^{\ell}_{m,n}=(M^{\ell}_{m,1})^{\otimes n}=\overline{L}_{m}^{\otimes
n}\overline{D}_{m}^{\otimes n}$. As $L_{m}$ was invertible with its inverse
also having entries in ${\mathbb{Z}}[z]$ we see that $\overline{L}_{m}$ is
also invertible and $\left(\overline{L}_{m}^{\otimes
n}\right)^{-1}M^{\ell}_{m,n}=\overline{D}_{m}^{\otimes n}$. By standard
properties of the tensor product have that,

$\textsf{rank}_{{\mathbb{F}}_{p}}M^{\ell}_{m,n}\geq\textsf{rank}_{{\mathbb{F}}_{p}}\overline{D}_{m}^{\otimes
n}.$

As $\overline{D}_{m}$ is upper triangular so will $\overline{D}_{m}^{\otimes
n}$ be. Therefore, to lower bound the rank of $\overline{D}_{m}^{\otimes n}$
we can lower bound the number of non-zero diagonal elements.

The diagonal elements in $\overline{D}_{m}^{\otimes n}$ correspond to the
product of diagonal elements chosen from $n$ copies of $\overline{D}_{m}$.
Recall, the rows and columns of $\overline{D}_{m}$ are labelled by
$j\in\\{0,\ldots,m-1\\}$ with

$\displaystyle D_{m}(j,j)=\prod_{i=0}^{j-1}(z^{j}-z^{i})$

Setting $z-1=w$ we note that ${\mathbb{F}}_{p}[z]/\langle(z-1)^{\ell}\rangle$
is isomorphic to ${\mathbb{F}}_{p}[w]/\langle w^{\ell}\rangle$. $D_{m}(j,j)$
can now be written as

$\displaystyle D_{m}(j,j)=(1+w)^{j(j-1)/2}\prod_{i=1}^{j}((1+w)^{i}-1)$

Using Lucas’s Theorem (Theorem B.2) we see that the largest power of $t$ which
divides $(1+w)^{l}-1$ is the same as the largest power of $p$ which divides
$l$. For any $j\leq\ell-1$ , therefore the largest power of $w$ which divides
$\overline{D}_{m}(j,j)$ is at most

$\displaystyle\sum\limits_{t=0}^{\lfloor\log_{p}(j)\rfloor}\left(\left\lfloor\frac{j}{p^{t}}\right\rfloor-\left\lfloor\frac{j}{p^{t+1}}\right\rfloor\right)p^{t}$
$\displaystyle=j+\sum\limits_{t=1}^{\lfloor\log_{p}(j)\rfloor}\left\lfloor\frac{j}{p^{t}}\right\rfloor
p^{t-1}(p-1)$ $\displaystyle\leq j(1+\lfloor\log_{p}(j)\rfloor(1-1/p))$
$\displaystyle\leq
j(\lfloor\log_{p}(\ell-1)\rfloor+1-\lfloor\log_{p}(\ell-1)\rfloor/p).$ (15)

Consider the set of tuples $(j_{1},\ldots,j_{n})\in{\mathbb{N}}$ such that
$j_{1}+\ldots+j_{n}\leq\lceil\ell/(\lfloor\log_{p}(\ell-1)\rfloor+1)\rceil$.
Using (15) we see that the diagonal entry in $\overline{D}_{m}^{\otimes n}$
corresponding to the tuple will be divisible by at most
$w^{\lceil\ell/(\lfloor\log_{p}(\ell-1)\rfloor+1)\rceil(\lfloor\log_{p}(\ell-1)\rfloor+1-\lfloor\log_{p}(\ell-1)\rfloor/p)}$.
It is easy to check that the exponent is at most $\ell-1$ which will guarantee
that the $(j_{1},\ldots,j_{n})$’th diagonal entry of
$\overline{D}_{m}^{\otimes n}$ is non-zero.

We note as $\lfloor\log_{p}(\ell-1)\rfloor+1=\lceil\log_{p}(\ell)\rceil$ we
get at least $\lceil\binom{\ell/\lceil\log_{p}(\ell)\rceil^{-1}+n}{n}\rceil$
non-zero diagonal entries proving the desired rank bound. ∎

##  Appendix C Proof of Lemma 2.21

We need two simple facts for the proof.

######  Fact C.1 (Hasse Derivatives of composition of two functions).

Let ${\mathbb{F}}$ be a field, $n\in{\mathbb{N}}$. Given a tuple of
polynomials
$C(y)=(C_{1}(y),C_{2}(y),\ldots,C_{n}(y))\in({\mathbb{F}}[y])^{n}$,
$w\in{\mathbb{N}}$ and $\gamma\in{\mathbb{F}}$ there exists a set of
coefficients $b_{w,{\bm{\alpha}}}\in{\mathbb{F}}$ (which depend on $C$ and
$\gamma$) where ${\bm{\alpha}}\in{\mathbb{Z}}^{n}_{\geq 0}$ such that for any
$f\in{\mathbb{F}}[x_{1},\ldots,x_{n}]$ we have,

$h^{(w)}(\gamma)=\sum\limits_{\text{wt}({\bm{\alpha}})\leq
w}b_{w,{\bm{\alpha}}}f^{({\bm{\alpha}})}(C_{1}(\gamma),\ldots,C_{n}(\gamma)),$

where $h(y)=f(C_{1}(y),\ldots,C_{n}(y))$.

This fact follows easily from the definition of the Hasse derivative. A proof
can also be found in Proposition 6 of [DKSS13]. We also need another fact
about the isomorphism between polynomials and the evaluations of their
derivatives at a sufficiently large set of points.

######  Fact C.2 (Computing polynomial coefficients from polynomial
evaluations).

Let ${\mathbb{F}}$ be a field and $n\in{\mathbb{N}}$. Given distinct
$a_{i}\in{\mathbb{F}}$ and $\beta_{i}\in{\mathbb{Z}}_{\geq 0},i=1,\ldots,n$,
let $h(y)=\prod_{i=1}^{n}(y-a_{i})^{\beta_{i}}\in{\mathbb{F}}[y]$. We have an
isomorphism between

$\frac{{\mathbb{F}}[z]}{\left\langle
h(z)\right\rangle}\longleftrightarrow{\mathbb{F}}^{\sum\limits_{i=1}^{n}\beta_{i}},$

which maps every polynomial $f\in{\mathbb{F}}[z]/\langle h(z)\rangle$ to the
evaluations $(f^{(j_{i})}(a_{i}))_{i,j_{i}}$ where $i\in\\{1,\ldots,n\\}$ and
$j_{i}\in\\{0,\ldots,\beta_{i}-1\\}$.

This is a simple generalization of the fact that for a univariate polynomial
having its first $\beta$ Hasse derivatives at $a$ be $0$ is equivalent to it
being divisible by $(z-a)^{\beta}$. It can be proven in several ways, one way
of proving it would be using the previous statement with the Chinese remainder
theorem for the ring ${\mathbb{F}}[y]$. To prove Lemma 2.21 we will need the
following corollary of the fact above.

######  Corollary C.3 (Computing a polynomial from its evaluations).

Let ${\mathbb{F}}$ be a field and $n\in{\mathbb{N}}$. Given distinct
$a_{i}\in{\mathbb{F}}$ and $\beta_{i}\in{\mathbb{Z}}_{\geq 0}$, let
$h(y)=\prod_{i=1}^{n}(y-a_{i})^{\beta_{i}}\in{\mathbb{F}}[y]$. Then there
exists coefficients $t_{i,j}\in{\mathbb{F}}[z]$ (depending on $h$) for
$i\in\\{1,\ldots,n\\},j\in\\{0,\ldots,\beta_{i}-1\\}$ such that for any
$f(y)\in{\mathbb{F}}[y]$ we have,

$\sum\limits_{i=1}^{n}\sum\limits_{j=0}^{\beta_{i}-1}t_{i,j}f^{(j)}(a_{i})=f(z)\in{\mathbb{F}}[z]/\langle
h(z)\rangle.$

###### Proof.

Fact C.2 implies that there exists a ${\mathbb{F}}$-linear map which can
compute the coefficients of $1,z,z^{2},\ldots,z^{\sum_{i=1}^{n}\beta_{i}-1}$
of $f(z)\in{\mathbb{F}}[z]/\langle h(z)\rangle$ from the evaluations
$f^{(j_{i})}(a_{i})$ for $i\in\\{1,\ldots,n\\}$ and
$j_{i}\in~{}\\{0,\ldots,\beta_{i}-1\\}$. Multiplying these coefficients with
$1,\ldots,z^{\sum_{i=1}^{n}\beta_{i}-1}$ computes $f(z)$ in
${\mathbb{F}}[z]/\langle h(z)\rangle$. ∎

We are now ready to prove Lemma 2.21.

###### Proof of Lemma 2.21.

As the statement we are trying to prove is linear over ${\mathbb{Z}}$ we see
that it suffices to prove the lemma in the case of when $f$ equals a monomial.
Given $v\in{\mathbb{Z}}_{\geq 0}^{n}$ we let
$Q_{v}(x)=Q_{v}(x_{1},\ldots,x_{n})=x_{1}^{v_{1}}\ldots x_{n}^{v_{n}}$ be a
monomial in ${\mathbb{F}}[x_{1},\ldots,x_{n}]$ where ${\mathbb{F}}$ is an
arbitrary field (we will be working with ${\mathbb{F}}={\mathbb{Q}}(\zeta)$
and ${\mathbb{F}}={\mathbb{F}}_{p}$). Let
$C(y)=y^{u^{\prime}}=(y^{u^{\prime}_{1}},y^{u^{\prime}_{2}},\ldots,y^{u^{\prime}_{n}})\in({\mathbb{F}}[y])^{n}$
where
$u^{\prime}=(u^{\prime}_{1},\ldots,u^{\prime}_{n})\in{\mathbb{Z}}^{n},u=(u_{1},\ldots,u_{n})\in{\mathbb{P}}({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n-1}$
and $u^{\prime}\text{ (mod }p^{k}\text{)}=u$. For this proof we use the
elements in $\\{0,\ldots,p^{k}-1\\}$ to represent the set
${\mathbb{Z}}/p^{k}{\mathbb{Z}}$.

We first prove the following claim.

######  Claim C.4.

Let $w\in{\mathbb{N}},\lambda\in{\mathbb{Z}}/p^{k}{\mathbb{Z}}$. There exists
coefficients $b^{\prime}_{w,{\bm{\alpha}}}(\lambda)\in{\mathbb{Q}}(\zeta)$
(depending on $w,\lambda$ and $C$) for ${\bm{\alpha}}\in{\mathbb{Z}}_{\geq
0}^{n}$ with $\text{wt}({\bm{\alpha}})\leq~{}w$ such that for all monomials
$Q_{v}(x)\in{\mathbb{Z}}[x_{1},\ldots,x_{n}],v\in{\mathbb{Z}}_{\geq 0}^{n}$ we
have,

$\sum\limits_{\text{wt}({\bm{\alpha}})\leq
w}b^{\prime}_{w,{\bm{\alpha}}}(\lambda)Q_{v}^{({\bm{\alpha}})}(\zeta^{a+\lambda
u})=\zeta^{\langle a,v\rangle}(Q_{v}\circ C)^{(w)}(\zeta^{\lambda}).$

###### Proof.

For every $\lambda\in{\mathbb{Z}}/p^{k}{\mathbb{Z}}$ and $w\in{\mathbb{N}}$,
using Fact C.1 we can find coefficients
$b_{w,{\bm{\alpha}}}(\lambda)\in{\mathbb{Q}}(\zeta)$ such that,

$\displaystyle(G\circ
C)^{(w)}(\zeta^{\lambda})=\sum\limits_{\text{wt}({\bm{\alpha}})\leq
w}b_{w,{\bm{\alpha}}}(\lambda)G^{({\bm{\alpha}})}(C(\zeta^{\lambda}))=\sum\limits_{\text{wt}({\bm{\alpha}})\leq
w}b_{w,{\bm{\alpha}}}(\lambda)G^{({\bm{\alpha}})}(\zeta^{\lambda
u^{\prime}}),$ (16)

for every polynomial $G\in{\mathbb{Q}}(\zeta)[x_{1},\ldots,x_{n}]$ where
$(G\circ C)(y)=f(y^{u^{\prime}})\in{\mathbb{Q}}(\zeta)[y]$. As
$u^{\prime}\text{ (mod }p^{k}\text{)}=u$ and $\zeta$ is a primitive $p^{k}$’th
root of unity in ${\mathbb{C}}$ we note that

$\zeta^{a+\lambda u}=\zeta^{a+\lambda u^{\prime}}.$

We now make the simple observation that for any
${\bm{\alpha}}\in{\mathbb{Z}}_{\geq 0}^{n}$ and $v\in{\mathbb{Z}}_{\geq
0}^{n}$ we have

$Q^{({\bm{\alpha}})}_{v}(x)=\prod\limits_{i=1}^{n}\binom{v_{i}}{\alpha_{i}}x_{i}^{v_{i}-\alpha_{i}},$

which implies

$Q^{({\bm{\alpha}})}_{v}(\zeta^{a+\lambda u})=\zeta^{\langle
a,v\rangle}\zeta^{-\langle{\bm{\alpha}},a\rangle}Q^{({\bm{\alpha}})}_{v}(\zeta^{\lambda
u})=\zeta^{\langle
a,v\rangle}\zeta^{-\langle{\bm{\alpha}},a\rangle}Q^{({\bm{\alpha}})}_{v}(\zeta^{\lambda
u^{\prime}}).$

The above equation combined with (16) for $G=Q_{v}$ implies,

$\displaystyle\zeta^{\langle a,v\rangle}(Q_{v}\circ
C)^{(w)}(\zeta^{\lambda})=\sum\limits_{\text{wt}({\bm{\alpha}})\leq
w}\zeta^{\langle{\bm{\alpha}},a\rangle}b_{w,{\bm{\alpha}}}(\lambda)Q_{v}^{({\bm{\alpha}})}(\zeta^{a+\lambda
u}),$

for all $w\in{\mathbb{N}}$ and $v\in{\mathbb{Z}}_{\geq 0}^{n}$. Setting
$b^{\prime}_{w,{\bm{\alpha}}}(\lambda)=\zeta^{\langle{\bm{\alpha}},a\rangle}b_{w,{\bm{\alpha}}}(\lambda)$
we are done . ∎

Without loss of generality let us assume $\sum_{x\in L}\pi(x)=\ell$ (if it is
greater we can reduce each of the $\pi(x)$ until we reach equality - this
would just mean that our computation was done by ignoring some higher order
derivatives at some of the points).

Let $h(y)\in{\mathbb{Z}}(\zeta)[y]\subseteq{\mathbb{Q}}(\zeta)[y]$ be the
polynomial,

$h(y)=\prod\limits_{\lambda\in{\mathbb{Z}}/p^{k}{\mathbb{Z}}}(y-\zeta^{\lambda})^{\pi(a+\lambda
u)}.$

Using Corollary C.3 there is a ${\mathbb{Q}}(\zeta)[z]$-linear combination of
the evaluations $(Q_{v}\circ C)^{(w)}(\zeta^{\lambda})$ for
$\lambda\in{\mathbb{Z}}/p^{k}{\mathbb{Z}}$ and $w<\pi(a+\lambda u)$ which can
compute the element

$(Q_{v}\circ C)(z)=z^{\langle
v,u^{\prime}\rangle}\in{\mathbb{Q}}(\zeta)[z]/\langle h(z)\rangle.$

This statement along with Claim C.4 leads to the following: there exists
elements $c_{\lambda,{\bm{\alpha}}}\in{\mathbb{Q}}(\zeta)[z]$ (depending on
$\pi,L$ and $u^{\prime}$) for $\lambda\in{\mathbb{Z}}/p^{k}{\mathbb{Z}}$ and
${\bm{\alpha}}\in{\mathbb{Z}}_{\geq 0}^{n}$ with
$\text{wt}({\bm{\alpha}})<\pi(a+\lambda u)$ such that the following holds for
all monomials $m_{v}\in{\mathbb{Z}}[x_{1},\ldots,x_{n}],v\in{\mathbb{Z}}_{\geq
0}$ we have,

$\sum\limits_{\lambda=0}^{p^{k}-1}\sum\limits_{\text{wt}({\bm{\alpha}})<\pi(a+\lambda
u)}c_{\lambda,{\bm{\alpha}}}Q_{v}^{({\bm{\alpha}})}(\zeta^{a+\lambda
u})=\zeta^{\langle a,v\rangle}(m_{v}\circ C)(z)=\zeta^{\langle
a,v\rangle}z^{\langle v,u^{\prime}\rangle}\in{\mathbb{Q}}(\zeta)/\langle
h(z)\rangle.$

We claim that these are coefficients we wanted to construct in the statement
of this lemma.

All we need to show now is that $\psi_{p^{k}}$ is a ring homomorphism from the
ring ${\mathbb{Z}}(\zeta)/\langle h(z)\rangle$ to the ring
$\overline{T}_{\ell}={\mathbb{F}}_{p}(\zeta)/\langle(z-1)^{\ell}\rangle$ and
maps $\zeta^{\langle a,v\rangle}z^{\langle v,u^{\prime}\rangle}$ to
$z^{\langle v,u^{\prime}\rangle}$. This follows from Corollary 2.15 and noting

$\psi_{p^{k}}(h(z))=(z-1)^{\sum\limits_{\lambda\in{\mathbb{Z}}_{p^{k}}}\pi(a+\lambda
u)}=(z-1)^{\ell}\in{\mathbb{F}}_{p}[z].$

∎