# Simple proofs for lattice coverings and sparse tensors

Thomas Karam111Mathematical Institute, University of Oxford. Email:
<EMAIL_ADDRESS>
###### Abstract

We provide simple proofs of analogues for coverings numbers of lattices of
several recently studied basic statements on the ranks of tensors. We
highlight the differences and analogies between the proofs in both settings.

###### Contents

  1. 1 Introduction
  2. 2 Main results
  3. 3 Independent subsets arguments
    1. 3.1 Finding a subset of independent points
    2. 3.2 Deducing restrictions with linear bounds
  4. 4 Descending subspaces arguments
    1. 4.1 A bounded size statement
    2. 4.2 Deducing bounded numbers of decompositions
    3. 4.3 Deducing restrictions with the same covering number
  5. 5 Further directions

##  1 Introduction

Throughout, for any integer $d\geq 1$ we will take $n_{1},\dots,n_{d}$ to be
positive integers. All our statements will be uniform in $n_{1},\dots,n_{d}$
(but not in $d$) unless stated otherwise. We will denote a field by
$\mathbb{F}$, and all our statements will be uniform with respect to
$\mathbb{F}$. An order-$d$ _lattice subset_ will be taken to be a subset of
$[n_{1}]\times\dots\times[n_{d}]$, and an order-$d$ _tensor_ will be taken to
be a function $[n_{1}]\times\dots\times[n_{d}]\to\mathbb{F}$ (and more
generally a function $X_{1}\times\dots\times X_{d}\to\mathbb{F}$ where
$X_{1},\dots,X_{d}$ are finite subsets of $\mathbb{N}$). For any positive
integer $k$ we will denote by $[k]$ the set $\\{1,\dots,k\\}$ of positive
integers up to $k$.

The present paper will involve several notions of richness of lattice subsets
and of tensors. In the case of lattice subsets, perhaps the simplest such
notion is their size. Another is the smallest number of sets of a specified
type which together suffice to cover the lattice subset. That notion
specialises to the size if the specified sets for the covering are all the
singletons. In the case of tensors, arguably the simplest well-known notion is
the matrix rank, which in turn generalises to a wide class of notions of rank
for $d\geq 3$.

There is a simple connection between order-$d$ lattice subsets and tensors:
given an order-$d$ tensor $T$, the support

$\\{Z(T):=\\{(x_{1},\dots,x_{d})\in[n_{1}]\times\dots\times[n_{d}]:T(x_{1},\dots,x_{d})\neq
0\\}$

of $T$ is an order-$d$ lattice subset. Conversely an order-$d$ lattice subset
may be viewed as an order-$d$ tensor with entries in $\\{0,1\\}$. We now
formally define the class of covering numbers of lattice subsets which we will
be concerned with in this paper.

######  Definition 1.1.

Let $d\geq 1$ be an integer. We make the following definitions.

If $B$ is a subset of $[d]$, then we say that a _$B$ -subspace_ is a maximal
subset $S$ of $[n_{1}]\times\dots\times[n_{d}]$ such that $x_{i}=y_{i}$
whenever $x,y\in S$ and $i\in B^{c}$, and say that it has _order_ $|B|$.

If $M$ is a non-empty subset of $\mathcal{P}([d])$, then we say that an
$M$-subspace is a $B$-subspace for some $B\in M$.

If $A$ is furthermore a subset of $[n_{1}]\times\dots\times[n_{d}]$ then we
say that $A$ has $M$-covering number at most $1$ if $A$ is contained in an
$M$-subspace.

The $M$-covering number of $A$, denoted by $\operatorname{Mc}(A)$, is the
smallest nonnegative integer $k$ such that we can write $A$ as a union

$A\subset A_{1}\cup\dots\cup A_{k}$ (1)

of $k$ subsets $A_{1},\dots,A_{k}$ of $[n_{1}]\times\dots\times[n_{d}]$ which
each have $M$-covering number at most $1$.

We will refer to an inclusion such as (1) as an _$M$ -covering decomposition_,
and to the integer $k$ inside such an inclusion as the _length_ of that
decomposition.

For instance, for $d=2$, a $\\{1\\}$-subspace is a horizontal line, a
$\\{2\\}$-subspace is a vertical line, and any set contained in
$\\{x=1\\}\cup\\{y=1\\}$ has $\\{\\{1\\},\\{2\\}\\}$-covering number at most
$2$. For any $d\geq 1$, a $\emptyset$-subspace is a point, and the
$\\{\emptyset\\}$-covering number of $A$ is equal to the size of $A$. At the
other extreme, a $[d]$-subspace is the whole of
$[n_{1}]\times\dots\times[n_{d}]$, and any subset $A$ has $\\{[d]\\}$-covering
number at most $1$.

As for tensors, there is a somewhat analogous class of notions which also
arises from assigning different roles to different coordinates, although there
is extra flexibility which led us (and has led us in previous work [9], [11])
to consider a class which is indexed by families of partitions of $[d]$ rather
than families of subsets of $[d]$. This class had also arisen in the paper of
Naslund [12] which originally introduced the partition rank of tensors.

######  Definition 1.2.

Let $d\geq 1$ be an integer, and let $R$ be a non-empty family of partitions
of $[d]$. We say that an order-$d$ tensor $T$ has _$R$ -rank at most $1$_ if
there exists a decomposition

$T(x_{1},\dots,x_{d})=\prod_{J\in P}a_{J}(x(J))$

of $T$ that holds for every
$(x_{1},\dots,x_{d})\in[n_{1}]\times\dots\times[n_{d}]$, where $P\in R$ is a
partition of $[d]$, and $a_{J}:\prod_{j\in J}[n_{j}]\rightarrow\mathbb{F}$ is
a function for each $J\in P$. We say that the _$R$ -rank_ of $T$ is the
smallest nonnegative integer $k$ such that we can write $T$ as a sum of $k$
order-$d$ tensors each with $R$-rank at most $1$.

After the usual rank of matrices, the notion of $R$-rank which has received
the most attention is the tensor rank, which corresponds to the case where $R$
contains only the discrete partition $\\{\\{1\\},\dots,\\{d\\}\\}$, due to its
applications in computational complexity theory. The notion of rank which has
the strongest known connections to some covering number is the slice rank,
which corresponds to

$R=\\{\\{\\{1\\},\\{1\\}^{c}\\},\\{\\{2\\},\\{2\\}^{c}\\},\dots,\\{\\{d\\},\\{d\\}^{c}\\}\\}$

and was formulated by Tao in 2016 [16] when rewriting the proof of the
breakthrough by Croot-Lev-Pach [4] and then Ellenberg and Gijswijt [5] on the
cap-set problem in a more symmetric way. Meanwhile, an appealing analogue to
the slice rank on the side of covering numbers is the $M$-covering number
where $M=\\{\\{j\\}^{c}:j\in[d]\\}$. We shall refer to this quantity as the
_slice covering number_. After the slice rank was introduced, Sawin and Tao
were able to obtain lower bounds on the slice rank of a tensor in terms of
slice covering numbers. In one case, they discovered an exact identity between
the two, which follows immediately from their more general statement [14],
Proposition 4.

If $d\geq 1$ is an integer, and $A$ is an order-$d$ lattice subset, then we
say that $A$ is an _antichain_ if no two distinct elements $x,y\in A$ satisfy
$x_{j}\leq y_{j}$ for every $j\in[d]$.

######  Proposition 1.3.

Let $d\geq 2$ be an integer, and let $T$ be an order-$d$ tensor. If the
support $Z(T)$ of $T$ is contained in an antichain, then the slice rank of $T$
is equal to the slice covering number of $Z(T)$.

Proposition 1.3 cannot be extended to arbitrary tensors: for instance a tensor
with entries all equal to $1$ has slice rank equal to $1$, but may have
unbounded slice covering number. Nonetheless, the class of tensors covered by
Proposition 1.3 is already wide enough to have combinatorial applications. In
particular, as the remainder of the blog post of Sawin and Tao shows, it is
possible to use this characterisation to show the sharpness of the slice rank
bounds for both the capset problem ([14], Proposition 9) and the result [13]
of Naslund and Sawin on sunflower-free sets ([14], Proposition 10).

In this paper we give simple proofs of analogues of the main results of
previous works [6], [9], [10], [11], for slice coverings numbers of lattices
rather than ranks of tensors, and compare the difficulties and proofs of the
statements in both settings.

How close the analogy will be between the cases of the covering numbers of
lattice subsets and of the ranks of tensors will depend on the specific
notions involved and on the question at hand. Proposition 1.3 shows that there
are situations where this analogy is strong to the extent that we have an
exact correspondence between the two. As we will explain throughout the
remainder of the paper, in some other situations the proofs will be simpler
for covering numbers, but there will be still strong analogies in part of the
proof methods. And finally in yet some other cases the proofs for covering
numbers will be considerably simpler than and will have little resemblance
with the proofs for ranks.

## Acknowledgements

The author thanks Timothy Gowers for a discussion in 2021 where the suggestion
arose that proving statements on covering numbers of lattices could be used as
a warm-up for their more difficult tensor versions. The author also thanks the
organisers of the European Conference on Combinatorics, Graph Theory and
Applications 2023 (Eurocomb’23) for encouragement after the conference which
led to the present paper being put together.

##  2 Main results

We devote the present section to our main results regarding covering numbers.
We begin with a property for which the proofs contain major difficulties for
the ranks of tensors, but are immediate for covering numbers of lattice
subsets.

For any integer $d\geq 1$, we say that lattice subsets $A^{1}$, $A^{2}$ are in
diagonal sum if we can write

$A_{1}\subset X_{1}^{1}\times\dots\times X_{d}^{1}\text{ and }A^{2}\subset
X_{1}^{2}\times\dots\times X_{d}^{2}$

for some $X_{1}^{1},X_{1}^{2}\subset[n_{1}]$, …,
$X_{d}^{1},X_{d}^{2}\subset[n_{d}]$ such that the intersection $X_{j}^{1}\cap
X_{j}^{2}$ is empty for every $j\in[d]$. We likewise say that order-$d$
tensors are in diagonal sum if their supports are in diagonal sum.

Whether the $R$-rank of tensors is additive over diagonal sums for a given $R$
is still an open question in general. In particular that question is still
open for the partition rank. For the tensor rank, that question remained for a
long time a conjecture of Strassen until it was negatively settled by Shitov
[15] in 2019. It was then only in 2021 that Gowers [6] proved diagonal
additivity for the slice rank. On the other hand, diagonal additivity is
essentially always satisfied for covering numbers of lattice subsets.

######  Proposition 2.1.

Let $d\geq 1$ be an integer, and let $M\subset\mathcal{P}([d])$ be non-empty.
If $A_{1}$ and $A_{2}$ are order-$d$ lattice subsets in diagonal sum and $M$
does not contain $[d]$, then

$\operatorname{Mc}(A_{1}\cup
A_{2})=\operatorname{Mc}(A_{1})+\operatorname{Mc}(A_{2}).$

If on the other hand $M$ contains $[d]$, then this identity becomes false,
since the $M$-covering number is then always at most $1$. Proposition 2.1 is
immediate, because a given $B$-subspace for any $B\neq[d]$ cannot
simultaneously contain points of $A_{1}$ and of $A_{2}$, whereas a single
tensor with $R$-rank equal to $1$ (for any notion of $R$-rank) can have an
effect on both diagonal blocks at once.

Another topic where the proofs are much simpler for lattice covering numbers
than for ranks of tensors is that of the interplay between the different
notions. In [11] we addressed the following question: if the
$R_{1},\dots,R_{k}$-ranks of a tensor are all bounded, then for which $R$ is
the $R$-rank of that tensor necessarily bounded ? Proposition 2.2 answers the
analogous question for covering numbers.

If $d\geq 1$ is an integer, and $M_{1},M_{2}\subset\mathcal{P}([d])$ are non-
empty then we write

$M_{1}\wedge M_{2}=\\{B_{1}\cap B_{2}:B_{1}\in M_{1},B_{2}\in M_{2}\\}.$

######  Proposition 2.2.

Let $d\geq 1$ be an integer.

  1. 1.

Let $M\subset\mathcal{P}([d])$ be non-empty and let $B\in\mathcal{P}([d])$.
The $M$-covering number of any $B$-subspace is equal to

$\min_{B’\in M}\prod_{j\in B\setminus B’}n_{j}.$

In particular, if $n_{1}=\dots=n_{d}$ are all equal to some common integer
$n$, then this quantity is equal to

$n^{\min_{B’\in M}|B\setminus B’|},$

which is equal to $1$ if $B$ is contained in some $B^{\prime}\in M$ and is at
least $n$ otherwise.

  2. 2.

Let $M_{1},M_{2}\subset\mathcal{P}([d])$ be non-empty, and let $k_{1},k_{2}$
be nonnegative integers. If $A$ is an order-$d$ lattice subset such that
$\operatorname{M_{1}c}A\leq k_{1}$ and $\operatorname{M_{2}c}A\leq k_{2}$ then
$\operatorname{M_{1}\wedge M_{2}c}A\leq k_{1}k_{2}$.

###### Proof.

We first prove (i). If $S$ is a $B$-subspace and $S’$ is a $B’$-subspace for
some $B’\in M$, then we have

$|S|/|S\cap S’|=\prod_{j\in B\setminus B’}n_{j},$

which shows the lower bound. Choosing $B’$ which minimises this expression and
then considering the $M$-covering of $B$ consisting only of $B’$-subspaces
then provides the upper bound.

We now prove (ii). We begin by writing respective $M_{1}$\- and
$M_{2}$-covering decompositions

$A\subset S_{1}^{1}\cup\dots\cup S_{k_{1}}^{1}\text{ and }A\subset
S_{1}^{2}\cup\dots\cup S_{k_{2}}^{2}$

of $A$, where each set $S_{i}^{1}$ is an $M_{1}$-subspace and each set
$S_{i}^{2}$ is an $M_{2}$-subspace. It follows that $A$ is a subset of

$\bigcup_{1\leq i_{1}\leq k_{1}}\bigcup_{1\leq i_{2}\leq
k_{2}}S_{i_{1}}^{1}\cap S_{i_{2}}^{2}.$

For any $i_{1}\in[k_{1}]$ and every $i_{2}\in[k_{2}]$ the intersection
$S_{i_{1}}^{1}\cap S_{i_{2}}^{2}$ is a $B_{i_{1}}\cap B_{i_{2}}$-subspace for
some $B_{i_{1}}\in M_{1}$ and $B_{i_{2}}\in M_{2}$; in other words it is an
$M_{1}\wedge M_{2}$-subspace. ∎

Let $X_{1}\subset[n_{1}],\dots,X_{d}\subset[n_{d}]$ be coordinate subsets. If
$A$ is an order-$d$ lattice subset then we write

$A(X_{1}\times\dots\times X_{d})=A\cap(X_{1}\times\dots\times X_{d})$

for the restriction of $A$ to the product $X_{1}\times\dots\times X_{d}$.
Likewise, if $T$ is an order-$d$ tensor then we write
$T(X_{1}\times\dots\times X_{d})$ for the tensor $T’:X_{1}\times\dots\times
X_{d}\to\mathbb{F}$ defined by

$T’(x_{1},\dots,x_{d})=T(x_{1},\dots,x_{d})$

for every $(x_{1},\dots,x_{d})\in[n_{1}]\times\dots\times[n_{d}]$.

The main results which we will focus on throughout the remainder of this paper
are the following four. The first is an analogue for coverings of lattice
subsets of [9], Theorem 1.4, which informally states that a high-rank tensor
must necessarily have a high-rank subtensor with bounded size.

######  Theorem 2.3.

Let $d,l\geq 1$ be integers, and let $M\subset\mathcal{P}([d])$ be non-empty.
If $A$ is an order-$d$ lattice subset such that
$\operatorname{Mc}(A)\geq|M|l$, then there exist
$X_{1}\subset[n_{1}],\dots,X_{d}\subset[n_{d}]$ each with size at most $l$
such that

$\operatorname{Mc}A(X_{1}\times\dots\times X_{d})\geq l.$

In the case of tensors, linear bounds are not known. In [9] it was conjectured
(Conjecture 13.1) that we can take linear bounds for both the rank of the
original tensor and the sizes of the sets $X_{1},\dots,X_{d}$. Thereafter,
motivated by an application [2] to limitations on the decoding of corrupted
classical and quantum error-correcting codes with $\mathrm{NC}^{0}[\oplus]$
circuits, Briët and Castro-Silva also asked in [3], Section 4 for linear
bounds (referred to as the “linear core property” in that paper) for a class
of notions of rank called “natural rank functions” (which neither contains nor
is contained in the class of notions of $R$-ranks).

Motivated by an extension of a theorem of Green and Tao [8] on the
equidistribution of high-rank polynomials to subsets of finite prime fields,
ultimately realised in [7], another statement involving subtensors was proved
in [9], Theorem 1.8: if a tensor has high rank after any changes of its
entries that do not have their coordinates all pairwise distinct, then it has
a high-rank subtensor consisting entirely of entries with pairwise distinct
coordinates. There again, linear bounds were conjectured in [9], Conjecture
13.6. We show that an analogous result holds for lattice subsets and prove
linear bounds there.

If $d\geq 1$ is an integer then we write $E$ for the set of points of
$[n_{1}]\times\dots\times[n_{d}]$ which do _not_ have all their coordinates
pairwise distinct.

######  Theorem 2.4.

Let $d,l\geq 1$ be integers, and let $M\subset\mathcal{P}([d])$ be non-empty.
If $A$ is an order-$d$ lattice subset such that $\operatorname{Mc}(A\setminus
E)\geq d^{d}|M|l$ then there exist
$X_{1}\subset[n_{1}],\dots,X_{d}\subset[n_{d}]$ pairwise disjoint such that

$\operatorname{Mc}A(X_{1}\times\dots\times X_{d})\geq l.$

In a third direction, it was proved ([10], Theorem 3.5) that up to a simple
class of transformations, a tensor of a given order with bounded slice rank
over a finite field with bounded size necessarily has at most a bounded number
of minimal-length slice rank decompositions, up to a simple class of
transformations (which is indispensable in such a statement). We prove an
analogue of this statement for $M$-covering of lattice subsets for arbitrary
$M$, which is also simpler in that it is not necessary to appeal to any
analogue of the previously mentioned class of transformations.

######  Theorem 2.5.

Let $d,l\geq 1$ be integers, and let $M\subset\mathcal{P}([d])$ be non-empty.
If $A$ is an order-$d$ lattice subset such that $\operatorname{Mc}(A)=l$ then
there are at most $(|M|l^{d})^{l}$ $l$-tuples $(S_{1},\dots,S_{l})$ such that

$A\subset S_{1}\cup\dots\cup S_{l}$

and the set $S_{i}$ is an $M$-subspace for every $i\in[l]$.

The following example shows that the bound obtained in Theorem 2.5 is not too
far from the optimal bound. Indeed for fixed $d$ and $M$ both bounds are of
the type $\exp(C(d,M)l\log l)$, where the two constants $C(d,M)$ are away by a
factor which is at most linear in $d$.

######  Example 2.6.

Let $d,l\geq 1$ be integers. Assume that $\min(n_{1},\dots,n_{d})\geq l$. We
consider the order-$d$ lattice subset $A=\\{(i,\dots,i):i\in[l]\\}$. Let $M$
be a non-empty subset of $\mathcal{P}([d])$ which does not contain $[d]$. No
two points of $A$ can be contained in the same $M$-subspace, so the
$M$-covering number of $A$ is equal to $l$. For each point $x\in A$, there are
$|M|$ possible choices for an $M$-subspace containing $x$, so the number of
possible $l$-tuples $(S_{1},\dots,S_{l})$ is equal to $l!|M|^{l}$.

Coming full circle, we deduce from Theorem 2.5 another version of Theorem 2.3,
which is stronger than Theorem 2.3 in that the covering number of the
restricted lattice subset is the same as that of the original lattice subset,
but weaker in that the sizes of the coordinate sets are no longer linear in
(either) covering number.

In the following statement and in Corollary 2.8, the asymptotic notation $O$
is used with $d,M$ fixed and $l$ large.

######  Theorem 2.7.

Let $d,l\geq 1$ be integers, and let $M\subset\mathcal{P}([d])$ be non-empty.
If $A$ is an order-$d$ lattice subset such that $\operatorname{Mc}(A)\geq l$
then there exist $X_{1}\subset[n_{1}],\dots,X_{d}\subset[n_{d}]$ each with
size at most $O(\max(|M|,d)^{dl})$ such that

$\operatorname{Mc}A(X_{1}\times\dots\times X_{d})\geq l.$

In the case where the base field $\mathbb{F}$ is finite a qualitative analogue
of Theorem 2.7 for the ranks of tensors was proved by Blatter, Draisma, and
Rupniewski ([1], Corollary 1.3.3) through an analogue ([1], Theorem 1.2.1) of
the graph minor theorem to tensors, which informally states that any sequence
$(T_{i})$ of tensors over a fixed finite field is such that we can eventually
find $i<j$ such that $T_{i}$ is a restriction of $T_{j}$ up to linear
transformations.

It is also known that we cannot in general simultaneously require the covering
number of the restriction and the sizes of the coordinate sets to be equal to
the covering number of the original lattice subset. An order-$3$ lattice
subset with slice covering number equal to $4$, but such that all its $4\times
4\times 4$ restrictions have slice covering number equal to $3$ was
constructed by Gowers ([9], Proposition 3.1). Together with the Sawin-Tao
connection, Proposition 1.3, this construction immediately led to an analogous
counterexample for the slice rank of tensors as well.

Specialising Theorem 2.3, Theorem 2.4 and Theorem 2.7 to the slice covering
number and using Proposition 1.3 we obtain corresponding statements for the
slice rank of tensors which are sufficiently sparse in the sense that they are
supported inside an antichain. We write $\operatorname{sr}T$ for the slice
rank of a tensor $T$.

######  Corollary 2.8.

Let $d\geq 2,l\geq 1$ be integers, and let $T$ be an order-$d$ tensor
supported inside an antichain.

  1. (i)

If $\operatorname{sr}T\geq dl$ then we can find
$X_{1}\subset[n_{1}],\dots,X_{d}\subset[n_{d}]$ with size at most $l$ such
that

$\operatorname{sr}T(X_{1}\times\dots\times X_{d})\geq l.$

  2. (ii)

If for every order-$d$ tensor $V$ supported inside $E$ we have

$\operatorname{sr}(T-V)\geq d^{d+1}l$

then we can find $X_{1}\subset[n_{1}],\dots,X_{d}\subset[n_{d}]$ pairwise
disjoint such that

$\operatorname{sr}T(X_{1}\times\dots\times X_{d})\geq l.$

  3. (iii)

If $\operatorname{sr}T\geq l$ then then we can find
$X_{1}\subset[n_{1}],\dots,X_{d}\subset[n_{d}]$ with size at most
$O(\max(|M|,d)^{dl})$ such that

$\operatorname{sr}T(X_{1}\times\dots\times X_{d})\geq l.$

The remainder of the paper is organised as follows. In Section 3 we prove
Theorem 2.3 and Theorem 2.4. There, the main tool that we use, which does not
appear to have any simple analogue for tensors, is a lemma which states that
from any lattice subset $A$ with high $M$-covering number we are able to find
a large subset $A’\subset A$ of points that are independent in the sense that
any $M$-subspace can only contain at most one point of $A’$. After that, in
Section 4 we prove Theorem 2.5 and then Theorem 2.7 successively. Finally, in
Section 5 we discuss some remaining directions of progress.

##  3 Independent subsets arguments

###  3.1 Finding a subset of independent points

We begin by introducing the key ingredient of this section, which makes the
proofs of Theorem 2.3 and of Theorem 2.4 much simpler for covering numbers
than for ranks of tensors.

If $d\geq 1$ is an integer, $M\subset\mathcal{P}([d])$ is non-empty, and $A$
is an order-$d$ lattice subset, then we write $I_{M}(A)$ for the _$M$
-independence number of $A$_, defined as the largest size of a subset
$A’\subset A$ satisfying the property that whenever $x,y$ are two distinct
elements of $A’$ there is no $M$-subspace which contains both $x$ and $y$. If
$A’$ is a largest such subset (or in fact any such subset), then in particular
any further subset $A^{\prime\prime}$ of $A^{\prime}$ satisfies
$\operatorname{Mc}(A^{\prime\prime})=|A^{\prime\prime}|$.

######  Lemma 3.1.

Let $d\geq 1$, $l\geq 1$ be integers, let $M\subset\mathcal{P}([d])$ be non-
empty, and let $A$ be an order-$d$ lattice subset with $M$-covering number at
least $l$. Then $I_{M}(A)\geq|A|/|M|$.

###### Proof.

If $u$ is an element of $[n_{1}]\times\dots\times[n_{d}]$, then we let $M(u)$
be the union of all $M$-subspaces of $[n_{1}]\times\dots\times[n_{d}]$
containing $u$. We note that $M(u)$ necessarily has $M$-covering number at
most $|M|$. Given an order-$d$ lattice subset $A$, we construct $A’$ as
follows. We first choose arbitrarily an element $u^{1}\in A$. We then choose
arbitrarily another element $u^{2}\in A\setminus M(u_{1})$ if we can do so. We
continue inductively as long as we can: at the step $m$, we choose an element

$u^{m}\in A\setminus(M(u^{1})\cup\dots\cup M(u^{m-1}))$

provided that that set is not empty. Letting $t$ be the number of elements
$u^{i}$ which are chosen by this process before it stops, we take
$A’=\\{u^{1},\dots,u^{t}\\}$. By definition of $t$, the set $A$ is contained
in the union

$M(u^{1})\cup\dots\cup M(u^{t}),$

which has $M$-covering number at most $t|M|$, so
$t\geq\operatorname{Mc}(A)/|M|$. By construction no two points of $A’$ can be
contained in the same $M$-subspace: if that were the case for some points
$u^{i},u^{j}\in A’$ with $i<j$, then we would have $u^{j}\in M(u^{i})$,
contradicting the definition of $M(u^{i})$.∎

###  3.2 Deducing restrictions with linear bounds

We now separately deduce Theorem 2.3 and Theorem 2.4 from Lemma 3.1.

###### Proof of Theorem 2.3.

Let $A$ be an order-$d$ lattice subset such that
$\operatorname{Mc}(A)\geq|M|l$. By Lemma 3.1 we can find a subset $A^{\prime}$
of $A$ with size equal to $l$ and such that
$\operatorname{Mc}(A^{\prime})=|A^{\prime}|=l$. For each $j\in[d]$ let
$X_{j}=\\{x_{j}:x\in A^{\prime}\\}$ be the projection of $A^{\prime\prime}$ on
the $j$th coordinate axis. The sets $X_{j}$ all have size at most
$|A^{\prime}|=l$, and the set $A^{\prime}$ is contained in
$X_{1}\times\dots\times X_{d}$, so $A\cap(X_{1}\times\dots\times X_{d})$
contains $A^{\prime}$ and in particular

$\operatorname{Mc}(A\cap(X_{1}\times\dots\times
X_{d}))\geq\operatorname{Mc}(A^{\prime})=l.\qed$

In order to obtain Theorem 2.4, we will use the following well-known
statement, the proof of which is an instance of the probabilistic method which
we recall for completeness. We note that Theorem 2.4 specialises to Lemma 3.2
in the case $M=\\{\emptyset\\}$.

######  Lemma 3.2.

Let $d\geq 1$ be an integer, and let $A$ be a subset of
$[n_{1}]\times\dots\times[n_{d}]$. We can find pairwise disjoint
$X_{1}\subset[n_{1}],\dots,X_{d}\subset[n_{d}]$ such that

$|A(X_{1}\times\dots\times X_{d})|\geq|A\setminus E|/d^{d}.$

###### Proof.

We can assume without loss of generality that $n_{1}=\dots=n_{d}$ are all
equal to some common value $n$. Indeed, if $A$ is a subset of
$[n_{1}]\times\dots\times[n_{d}]$ then we can also view it as a subset of
$[n]^{d}$, where $n=\max(n_{1},\dots,n_{d})$. We then define independent
uniform random variables $U_{1},\dots,U_{n}$ taking values in $[d]$, and then
take

$X_{j}=\\{i\in[n]:U_{i}=j\\}$

for every $j\in[d]$. By construction the (random) sets $X_{1},\dots,X_{d}$ are
pairwise disjoint. For every $x\in A\setminus E$, the probability that $x$
belongs to $X_{1}\times\dots\times X_{d}$ is equal to $1/d^{d}$, so the
expected size of

$(A\setminus E)(X_{1}\times\dots\times X_{d})=A(X_{1}\times\dots\times X_{d})$

is $|A\setminus E|/d^{d}$. In particular, there is a desired choice of
$(X_{1},\dots,X_{d})$ for which the required inequality holds. ∎

Having shown that, we are now ready to deduce Theorem 2.4.

###### Proof of Theorem 2.4.

Let $A$ be an order-$d$ lattice subset such that

$\operatorname{Mc}(A\setminus E)\geq d^{d}|M|l.$

Without loss of generality we can assume that $A\cap E$ is empty. Again, by
Lemma 3.1 we can find a subset $A’$ of $A$ with $|A’|=d^{d}l$ and
$\operatorname{Mc}A’=d^{d}l$. Applying Lemma 3.2 we can find a subset
$A^{\prime\prime}$ of $A’$ with size $|A’|/d^{d}$ and pairwise disjoint
subsets $X_{1}\subset[n_{1}],\dots,X_{d}\subset[n_{d}]$ such that
$A^{\prime\prime}$ is contained in $X_{1}\times\dots\times X_{d}$. We then
have $\operatorname{Mc}(A^{\prime\prime})\geq|A^{\prime\prime}|$, as well as

$\operatorname{Mc}(A\cap(X_{1}\times\dots\times X_{d}))\geq l,$

as desired. ∎

##  4 Descending subspaces arguments

###  4.1 A bounded size statement

Our main auxiliary tool in this section is a result, Proposition 4.1, which
says in particular that if $A$ is an order-$d$ lattice subset such that every
subspace of $[n_{1}]\times\dots\times[n_{d}]$ with order between $1$ and $d-1$
has an intersection with $A$ that is covered by a bounded number of lower-
order subspaces, then $A$ has bounded size. Although its proof is technically
simpler, the iterative step in that proof result is similar in spirit to [9],
Proposition 11.4. Likewise, Proposition 4.1 itself is analogous to a
consequence of [9], Proposition 11.4 that we obtain by applying it at most
$2^{d}$ times: the fact that if an order-$d$ tensor $T$ has bounded $R$-rank,
and all the order-$d’$ subtensors with $2\leq d’\leq d$ that we can obtain
from $T$ by fixing some of the its $d$ coordinates have bounded partition
rank, then $T$ has bounded tensor rank.

If $d\geq 1$ is an integer and $C$ is a non-empty subset of $[d]$ then we
define a class $C^{*}$ of subsets of $[d]$ by

$C^{*}=\\{C\setminus\\{j\\}:j\in C\\}.$

######  Proposition 4.1.

Let $d\geq 1$, $l\geq 1$ be integers, let $M\subset\mathcal{P}([d])$ be non-
empty, and let $A$ be an order-$d$ lattice subset. Assume that for every $B\in
M$ and every non-empty $C\subset B$ the intersections of $A$ with every
$C$-subspace have $C^{*}$-covering number at most $l$. Then $|A|\leq
l^{\tau}\operatorname{Mc}(A)$, where $\tau$ is the largest size of any $B\in
M$.

###### Proof.

If $M=\\{\emptyset\\}$ then $\operatorname{Mc}(A)=|A|$, so we are done. Let us
now assume that $M\neq\\{\emptyset\\}$. Because $A$ has $M$-covering number at
most $l$, we can write

$A=\bigcup_{B\in M}\bigcup_{1\leq i\leq t_{B}}A\cap S_{B,i}$ (2)

for some $B$-subspaces $S_{B,i}$ and some nonnegative integers $t_{B}$
satisfying

$\sum_{B\in M}t_{B}=\operatorname{Mc}(A).$

Let $B_{\max}\in M$ with maximal size. By the assumption, for each
$i\in[t_{B_{\max}}]$ we can write

$A\cap S_{B_{\max},i}=\bigcup_{B^{1}\in B_{\max}^{*}}\bigcup_{1\leq i_{1}\leq
u_{B^{1}}}A\cap S_{B^{1},i_{1}}^{1}$

for some $B^{1}$-subspaces $S_{B^{1},i_{1}}^{1}$ and some nonnegative integers
$u_{B^{1}}$ satisfying

$\sum_{B^{1}\in B_{\max}^{*}}u_{B^{1}}\leq l.$

Letting $M^{1}=(M\setminus\\{B_{\max}\\})\cup B_{\max}^{*}$ we have obtained
an analogue of (2) in terms of the sets in $M^{1}$, which we can write as

$A=\bigcup_{B\in M^{1}}\bigcup_{1\leq i\leq t_{B}^{1}}A\cap S_{B,i}^{1}$ (3)

where the subspaces $S_{B,i}^{1}$ are $M^{1}$-subspaces.

If $M^{1}=\\{\emptyset\\}$ then every $A\cap S_{B,i}$ appearing in (3) has
size at most $1$. Otherwise we iterate by selecting a new set $B_{\max}^{2}$
with maximal size in $M^{1}$ which plays the same role as
$B_{\max}^{1}=B_{\max}$ previously did. More generally for any $m\geq 2$ the
step $m$ involves a set $B_{\max}^{m}$ with maximal size in $M^{m-1}$ and
leads to a decomposition

$A=\bigcup_{B\in M^{m}}\bigcup_{1\leq i\leq t_{B}^{m}}A\cap S_{B,i}^{m}$ (4)

where $M^{m}=(M\setminus B_{\max}^{m})\cup B_{\max}^{m}$ and the sets
$S_{B,i}^{m}$ are $M^{m}$-subspaces. At the end of step $m$ we stop if
$M^{m}=\\{\emptyset\\}$, and otherwise continue.

For any step $m$ the set $B_{\max}^{m}$ in that iteration can no longer appear
after the end of that step. Since the number of subsets of $[d]$ is bounded
above (by $2^{d}$), this process eventually terminates, after at most $2^{d}$
iterations. Whenever at some step $m$ of the process a set $B_{\max}^{m}$ is
selected, each subspace $S_{B_{\max}^{m-1},i}$ from the analogue at step $m-1$
of (4) is replaced by at most $l$ subspaces with strictly smaller order in
(4). Since the order of any subspace throughout the process can only take
values between $0$ and $\tau$, so can be decreased only at most $\tau$ times,
any subspace $S_{B,i}$ from (2) can have at most $l^{\tau}$ descendants with
order $0$ throughout the process. The result follows. ∎

###  4.2 Deducing bounded numbers of decompositions

The tool which we just obtained then allows us to prove Theorem 2.5 by
induction on the $M$-covering number of the lattice subset $A$, by
distinguishing into the cases where a subspace has a rich intersection with
$A$, which then forces one of a few subspaces to belong to a minimal-length
decomposition of $A$, and the case where there is no such subspace, in which
case $A$ has bounded size and it is then not too difficult to conclude. In the
case of tensors, there are likewise situations where we can guarantee that
some specific functions will be involved in a minimal-length decomposition up
to a change of basis (for instance [10], Proposition 3.4), but we cannot do so
in general. Furthermore, the analogue of the second case in the proof below is
a tensor with bounded tensor rank, and showing that the set of minimal-length
$R$-rank decompositions of a tensor cannot be too rich appears to be difficult
even under the assumption that that tensor has bounded tensor rank.

###### Proof of Theorem 2.5.

We write $Q(d,l,M)$ for our desired upper bound. Let $A$ be an order-$d$
lattice subset satisfying $\operatorname{Mc}(A)=l$. We proceed by induction on
$l$. The result is immediate if $l=0$. Assume now that $l\geq 1$. We
distinguish two cases.

Case 1: We can find a $C$-subspace $S$ with $C$ non-empty such that the
$C^{*}$-covering number of $A\cap S$ is at least $l+1$. Then necessarily any
$M$-covering decomposition of $A$ must necessarily involve a subspace
containing $S$: if it did not, then writing a length-$l$ decomposition of $A$
and taking the intersection with $S$ would show that $A\cap S$ has
$C^{*}$-covering number at most $l$. We may choose from at most $|M|$ possible
$M$-subspaces $S’$ containing $S$. Because $\operatorname{Mc}(A)=l$, for each
of these possibilities for $S^{\prime}$ we have $\operatorname{Mc}(A\setminus
S’)\geq l-1$. The inductive hypothesis shows that that for each of them, the
lattice subset $A\setminus S’$ only has at most $Q(d,l-1,M)$ length-$(l-1)$
$M$-covering decompositions, so there are at most $l|M|Q(d,l-1,M)$ length-$l$
$M$-covering decompositions. (The factor $l$ comes from the fact that there
are $l$ possibilities for how to place $S’$ in the $l$-tuple
$(S_{1},\dots,S_{l})$ which constitutes the decomposition.)

Case 2: If we are not in Case 1, then the assumption of Proposition 4.1 is
satisfied, and hence $|A|\leq l^{d}$: if $M$ does not contain $[d]$ then this
follows from $|A|\leq l^{d-1}\operatorname{Mc}(A)$, since
$\operatorname{Mc}(A)\leq l$ and if $M$ contains $[d]$ then this follows from
$|A|\leq l^{d}\operatorname{Mc}(A)$, since $\operatorname{Mc}(A)\leq 1$. There
are hence at most $l^{d}|M|$ possible $M$-subspaces that do not have empty
intersection with $A$. A length-$l$ decomposition is specified by an $l$-tuple
of the subspaces, so $A$ has at most $(l^{d}|M|)^{l}$ length-$l$ $M$-covering
decompositions. We have shown

$Q(d,l,M)\leq\max(l|M|Q(d-1,l,M),l^{dl}|M|^{l}).$

We have $Q(1,l,M)\leq l!\leq l^{l}$, so we may take $Q(d,l,M)\leq
l^{dl}|M|^{l}$. ∎

###  4.3 Deducing restrictions with the same covering number

Once Theorem 2.5 is proved, we deduce Theorem 2.7 by returning to the two
cases which we have previously considered. In the first case, we restrict the
subspace that had a rich intersection with $A$ so that the restriction still
has a rich intersection with $A$ but the coordinate sets have bounded size;
this then allows us to reduce to the case of an $M$-covering number one less
than the original one. The second case is straightforward, since if a set has
bounded size then all its coordinate projections have bounded size. As we do
not have a proof of the analogue of Theorem 2.5 to the $R$-ranks of tensors we
do not have such an analogue for Theorem 2.7 either.

###### Proof of Theorem 2.7.

We write $J(d,l,M)$ for our desired upper bound. We proceed by induction on
$d$. The result is immediate if $d=1$. We now assume that $d\geq 2$, and
assume that the result has been proved for all $1\leq d^{\prime}<d$. Let $A$
be an order-$d$ lattice subset satisfying $\operatorname{Mc}(A)\geq l$ for
some nonnegative integer $l$. By removing points of $A$ one by one, we can
without loss of generality assume that $\operatorname{Mc}A=l$.

We use the two cases from the proof of Theorem 2.5 to define a tree as
follows. First take the root to be $A$. If we are in Case 2, then the
construction stops. Otherwise, if we are in Case 1, then we fix a $C$-subspace
$S$ satisfying Case 1, and for each of the at most $|M|$ possible
$M$-subspaces $S’$ containing $S$ we take $A\setminus S’$ to be an immediate
descendant of $A$. For each of these we then separately iterate: given a new
set $A_{v}$, if it satisfies Case 2 then it becomes a leaf of the tree,
otherwise we fix a $C_{v}$-subspace $S_{v}$ analogous to $S$, and then define
its immediate descendants as we previously did. We continue the construction
until every set of the tree is either declared to be a leaf or attains a depth
equal to $l$.

For each non-leaf vertex $A_{v}$, the Case 1 assumption states that the
$C_{v}^{*}$-covering number of $A_{v}\cap S_{v}$ is at least $l+1$. Again,
without loss of generality we can assume that the $C_{v}^{*}$-covering number
of $A_{v}\cap S_{v}$ is exactly $l+1$. We know that $C_{v}$ is not the full of
[d]: if it were, then this would contradict $\operatorname{Mc}A_{v}\leq l$,
since the $[d]^{*}$-covering number of any order-$d$ lattice subset is always
at most its $M$-covering number. By the inductive hypothesis we may therefore
apply Theorem 2.7 for order-$|C_{v}|$-lattice subsets to $A_{v}\cap S_{v}$,
which shows that we can always find some sets $X_{1,v},\dots,X_{d,v}$ with
size at most $J(|C_{v}|,l+1,C_{v}^{*})$ such that the $C_{v}^{*}$-covering
number of

$(A_{v}\cap S_{v})(X_{1,v}\times\dots\times X_{d,v})$

is at least $l+1$.

For every leaf vertex $A_{v}$, Case 2 shows that $A_{v}$ has size at most
$l^{d}$, so we can enclose it into a product of sets $X_{1,v}\times\dots\times
X_{d,v}$ each with size at most $l^{d}$.

For every $j\in[d]$ we then take $X_{j}$ to be the union of the sets $X_{j,v}$
over all vertices $v$ of the tree. We next claim that

$\operatorname{Mc}A(X_{1}\times\dots\times X_{d})\geq l.$

Indeed, if we try to construct an $M$-covering of $A(X_{1}\times\dots\times
X_{d})$ with smaller length, then Case 1 from the proof of Theorem 2.5 shows
that necessarily we have to choose $M$-subspaces by going down the tree that
we have just constructed, and once we arrive at a leaf, either the leaf
already has depth $l$, or the remaining elements to incorporate are the same
as those that we had for the original set $A$, and that cannot be done with
fewer subspaces than for $A$ itself.

We may therefore take

$J(d,l,M)\leq(1+|M|+\dots+|M|^{l})\max_{C\in\mathcal{P}([d])\setminus\\{\emptyset,[d]\\}}J(d-1,l+1,C^{*})+|M|^{l}l^{d}.$

We may take $J(1,l,M’)=l$ for all non-empty $M’$ (the only such $M’$ is
$\\{1\\}$). As the $C^{*}$ contains at most $d$ sets, the bound follows. ∎

##  5 Further directions

Let us finish by mentioning a few questions motivated or inspired by the
discussion in this paper.

In one direction, we can aim to improve and if possible exactly determine the
optimal bounds in Theorem 2.3 and in Theorem 2.4. The current upper bounds
come from the lower bound on the $M$-independence number in terms of the
$M$-covering number in Lemma 3.1.

######  Question 5.1.

Let $d\geq 1$ be an integer, and let $M\subset\mathcal{P}([d])$ be non-empty.
For which values of $c$ do we have $I_{M}(A)\geq c\operatorname{Mc}(A)$ for
every order-$d$ lattice subset $A$ ?

Even for simple cases of $M$, such as when $M$ consists in all subsets of
$[d]$ with size $d-1$, this question does not appear to have an obvious
answer. It is also possible that the optimal upper bounds in Theorem 2.3 and
in Theorem 2.4 are better still than the optimal upper bounds coming from the
current argument, even if Lemma 3.1 on its own is optimised.

As we have seen many proofs are significantly or considerably easier for
lattice covering numbers than for ranks of tensors, and the connection of
Sawin and Tao (Proposition 1.3) provides a translation between the two for
sufficiently sparse tensors. The next question then naturally arises as a way
of obtaining more statements and proofs similar to those of Corollary 2.8,
which establish properties of sparse tensors purely by working with covering
numbers of lattice subsets.

######  Question 5.2.

Let $d\geq 1$ be an integer, and let $R$ be a non-empty family of partitions
of $[d]$. Are there any sparsity conditions on order-$d$ tensors which
guarantee that for some non-empty $M\subset\mathcal{P}([d])$ the $R$-rank of
$T$ is equal to the $M$-covering number of the support of $T$ ?

Proving such analogues of Proposition 1.3 does not appear obvious to achieve.
The statement and proof of the dual formulation of the slice rank ([14],
Proposition 1) underpinning the Sawin-Tao connection fails for the partition
rank. As for the tensor rank, the line covering number, corresponding to
$M=\\{\\{j\\}:j\in[d]\\}$, may appear natural to consider but it will
certainly not suffice for a tensor to be supported inside an antichain for its
tensor rank to be equal to its line covering number: if it did, then that
would answer a central open problem on tensor rank lower bounds by providing
explicit examples of order-$d$ tensors $[n]^{d}\to\mathbb{F}$ with tensor rank
$\Omega(n^{d-1})$.

## References

  * [1] A. Blatter, J. Draisma, F. Rupniewski, A tensor restriction theorem over finite fields, arXiv:2211.12319 (2022).
  * [2] Jop Briët, Harry Buhrman, Davi Castro-Silva, and Niels M.P. Neumann, Noisy decoding by shallow circuits with parities: classical and quantum, arXiv:2302.02870 (2023).
  * [3] Jop Briët and Davi Castro-Silva, Random restrictions of high-rank tensors and polynomial maps, arXiv:2212.13728 (2022).
  * [4] E. Croot, V. Lev and P. Pach, Progression-free sets in $\mathbb{Z}_{4}^{n}$ are exponentially small, Ann of Math. 185 (2017), 331-337.
  * [5] J. Ellenberg and D. Gijswijt, On large subsets of $\mathbb{F}_{q}^{n}$ with no three-term arithmetic progression Ann of Math. 185 (2017), 339-343.
  * [6] W. T. Gowers, The slice rank of a direct sum, arXiv:2105.08394v2 (2021).
  * [7] W. T. Gowers and T. Karam, Equidistribution of high rank polynomials with variables restricted to subsets of $\mathbb{F}_{p}$, arXiv:2209.04932 (2022).
  * [8] B. Green and T. Tao, The distribution of polynomials over finite fields, with applications to the Gowers norms. Contrib. Discrete Math. 4 (2009), no. 2, 1-36.
  * [9] T. Karam, High-rank subtensors of high-rank tensors, arXiv:2207.08030 (2022).
  * [10] T. Karam, Small sunflowers and the structure of slice rank decompositions, arXiv:2308.07101 (2023).
  * [11] T. Karam, The interplay between bounded ranks of tensors arising from partitions, arXiv:2310.11356 (2023).
  * [12] E. Naslund, The partition rank of a tensor and k-right corners in $\mathbb{F}_{q}^{n}$, Jour. Combin. Th, A 174 (2020), 105190.
  * [13] E. Naslund and W. Sawin, Upper bounds for sunflower-free sets, Forum Math. Sigma, 5 (2017), e15.
  * [14] W. Sawin and T. Tao, Notes on the “slice rank” of tensors, https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors.
  * [15] Y. Shitov, Counterexamples to Strassen’s direct sum conjecture, Acta Math. 222 (2019), 363-379.
  * [16] T. Tao, A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound, https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound.