# Random restrictions of high-rank tensors and polynomial maps

Jop Briët  CWI & QuSoft, Science Park 123, 1098 XG Amsterdam, The Netherlands
<EMAIL_ADDRESS>and  Davi Castro-Silva  CWI & QuSoft, Science Park 123, 1098 XG
Amsterdam, The Netherlands<EMAIL_ADDRESS>
###### Abstract.

Motivated by a problem in computational complexity, we consider the behavior
of rank functions for tensors and polynomial maps under random coordinate
restrictions. We show that, for a broad class of rank functions called
_natural rank functions_ , random coordinate restriction to a dense set will
typically reduce the rank by at most a constant factor.

This work was supported by the Dutch Research Council (NWO) as part of the
NETWORKS programme (grant no. 024.002.003).

##  1\. Introduction

Different but equivalent definitions of matrix rank have been generalized to
truly different rank functions for tensors. Although they have proved useful
in a variety of applications, the basic theory of these rank functions,
describing for instance their interrelations and elementary properties, is
still far from complete.

Without going into the definitions (which are given in Section 2), we mention
a number of these rank functions to indicate some of the contexts in which
they have appeared. The _slice rank_ of a tensor was introduced by Tao [33,
34] to reformulate the breakthrough proof of the cap set conjecture due to
Croot, Lev and Pach [8] and Ellenberg and Gijswijt [11]. Slice rank is
generalized by the _partition rank_ , which was introduced by Naslund to prove
bounds on the size of subsets of $\mathbb{F}_{q}^{n}$ without $k$-right
corners [27], as well as provide exponential improvements on the
Erdős–Ginzburg–Ziv constant [26]. The _analytic rank_ is based on a measure of
equidistribution for multilinear forms associated to tensors over finite
fields, and was introduced by Gowers and Wolf to study solutions to linear
systems of equations in large subsets of finite vectors spaces [15].
_Geometric rank_ , defined and studied by Kopparty, Moshkovitz and Zuiddam in
the context of algebraic complexity theory [23], gives a natural analogue of
analytic rank for tensors over infinite fields.

Closely related to these rank functions for tensors are notions of rank for
multivariate polynomials. As quadratic forms on finite-dimensional vector
spaces are naturally represented by matrices after choosing a basis, matrix
rank gives a corresponding notion of rank for quadratic forms. This, in turn,
may be generalized to rank functions for arbitrary polynomials by considering
their associated homogeneous multilinear forms. Specific problems concerning
multivariate polynomials might also give rise to other notions of rank more
well-suited to the application at hand.

A notion of polynomial rank akin to the partition rank of tensors was used
already in the ’80s by Schmidt in work on algebraic geometry [31]. This notion
has been re-discovered and proven useful on several occasions (see Section 3),
and is referred to by several different names in the literature; here we will
refer to it as _Schmidt rank_. Work on the Inverse Theorem for the Gowers
uniformity norms led Green and Tao to define the notion of _degree rank_ [16],
which quantifies how hard it is to express the considered polynomial as a
function of lower-degree polynomials; this notion was shown to be closely
linked to equidistribution properties of multivariate polynomials over prime
fields $\mathbb{F}_{p}$. Tao and Ziegler [35] later studied the relationship
between the degree rank of a polynomial and its _analytic rank_ , defined as
the (tensor) analytic rank of its associated homogeneous multilinear form, and
exploited their close connection in order to prove the general case of the
Gowers Inverse Theorem over $\mathbb{F}_{p}^{n}$.

Recent work on constant-depth Boolean circuits by Buhrman, Neumann and the
present authors gave rise to a problem on equidistribution properties of
higher-dimensional polynomial maps under biased input distributions [5]. This
motivated a new notion of analytic rank for (high-dimensional) polynomial maps
and prompted the study of rank under random coordinate restrictions, which is
the topic of this paper.

Common to the tensors, polynomials and polynomial maps considered here is that
they can be viewed as maps on $\mathbb{F}^{X}$, where $\mathbb{F}$ is a given
field and $X$ is a finite set indexing the variables. The main question
addressed in this paper is whether, if a map $\phi$ on $\mathbb{F}^{X}$ has
high rank, most of its coordinate restrictions $\phi_{|I}$ on $\mathbb{F}^{I}$
also have high rank for dense subsets $I\subseteq X$ (where we also respect
the product structure of $X$ in the case of tensors). Our main results show
that this is the case for all “natural” rank functions, which include all
those mentioned above.

###  1.1. The matrix case

It is instructive to first consider the case of matrices, which is simpler and
illustrates the spirit of our main results. For a matrix
$A\in\mathbb{F}^{n\times n}$ and subsets $I,J\subseteq[n]$, denote by
$A_{|I\times J}$ the sub-matrix of $A$ induced by the rows in $I$ and columns
in $J$. Given $\sigma\in(0,1)$, consider a random set $I\subseteq[n]$
containing each element independently with probability $\sigma$; we write
$I\sim[n]_{\sigma}$ when $I$ is distributed as such. Note that, if
$I\sim[n]_{\rho}$ and $J\sim[n]_{\sigma}$ are independent, then $I\cup
J\sim[n]_{\eta}$ with $\eta=1-(1-\rho)(1-\sigma)$.

######  Proposition 1.1.

For every $\sigma\in(0,1]$ there exists $\kappa\in(0,1]$ such that for every
matrix $A\in\mathbb{F}^{n\times n}$ we have

$\mbox{\rm Pr}_{I\sim[n]_{\sigma}}\big{[}\operatorname{rk}(A_{|I\times
I})\geq\kappa\cdot\operatorname{rk}(A)\big{]}\geq
1-2e^{-\kappa\operatorname{rk}(A)}.$

  * Proof:

Write $\rho=1-\sqrt{1-\sigma}$ and let $J,J^{\prime}\sim[n]_{\rho}$ be
independent random sets; note that $J\cup J^{\prime}\sim[n]_{\sigma}$. Let
$r=\operatorname{rk}(A)$, and fix a set $S\subseteq[n]$ of $r$ linearly
independent rows of $A$. By the Chernoff bound [17], the probability that the
set $J$ satisfies $|J\cap S|<\rho r/2$ is at most $e^{-\rho r/8}$.

Now let $B:=A_{|(J\cap S)\times[n]}$ be the (random) sub-matrix of $A$ formed
by the rows in $J\cap S$. Since its rows are linearly independent, the rank of
$B$ is precisely $|J\cap S|$; let $T\subseteq[n]$ be a set of $|J\cap S|$
linearly independent columns of $B$. Then the probability that
$|J^{\prime}\cap T|<\rho|T|/2$ is at most $e^{-\rho|T|/8}$, and the rank of
$B_{|(J\cap S)\times(J^{\prime}\cap T)}=A_{|(J\cap S)\times(J^{\prime}\cap
T)}$ is equal to $|J^{\prime}\cap T|$. It follows from the union bound and
monotonicity of rank under restrictions that, with probability at least
$1-2e^{-\rho^{2}r/16}$, the principal sub-matrix of $A$ induced by $J\cup
J^{\prime}$ has rank at least $\rho^{2}r/4$. The result now follows since
$J\cup J^{\prime}\sim[n]_{\sigma}$. $\Box$

###  1.2. Main results and outline of the paper

Here we generalize Proposition 1.1 to tensors and polynomial maps for rank
functions that satisfy a few natural properties, namely “sub-additivity”,
“monotonicity”, a “Lipschitz condition” and, in the case of polynomial maps,
“symmetry” (see Section 2 and Section 3 for the precise definitions). Those
functions which satisfy these properties are called _natural rank functions_ ;
we note that all notions of rank mentioned above are natural rank functions.

Since our results are independent of the field considered (which can be finite
or infinite), we will always denote it by $\mathbb{F}$ and suppress statements
of the form “let $\mathbb{F}$ be a field” or “for every field $\mathbb{F}$”.
We begin by considering the case of tensors.

######  Definition 1.2 (Tensors).

For finite sets $X_{1},\dots,X_{d}\subset\mathbb{N}$, a $d$-tensor is a map
$T:X_{1}\times\cdots\times X_{d}\to\mathbb{F}$. We will associate with any
$d$-tensor $T$ a multilinear map
$\mathbb{F}^{X_{1}}\times\cdots\times\mathbb{F}^{X_{d}}\to\mathbb{F}$ and an
element of $\mathbb{F}^{X_{1}}\otimes\cdots\otimes\mathbb{F}^{X_{d}}$ in the
obvious way, and also denote these objects by $T$.

######  Definition 1.3 (Restriction of tensors).

For a tensor $T$ as in Definition 1.2 and subsets $I_{1}\subseteq
X_{1},\dots,I_{d}\subseteq X_{d}$, denote $I_{[d]}=I_{1}\times\cdots\times
I_{d}$ and write $T_{|I_{[d]}}$ for the restriction of $T$ to $I_{[d]}$. If
$T$ is viewed as an element of
$\mathbb{F}^{X_{1}}\otimes\cdots\otimes\mathbb{F}^{X_{d}}$, then
$T_{|I_{[d]}}$ is simply a sub-tensor.

We define $(\mathbb{F}^{\infty})^{\otimes d}$ to be the set of $d$-tensors
over $\mathbb{F}$ with finite support. Note that the tensors defined on finite
sets naturally embed into this set, and that the rank functions for tensors
discussed above are invariant under this embedding. Our main result regarding
tensors is then as follows:

######  Theorem 1.4.

For every $d\in\mathbb{N}$ and $\sigma\in(0,1]$, there exist constants
$C,\kappa>0$ such that the following holds. For every natural rank function
$\operatorname{rk}:(\mathbb{F}^{\infty})^{\otimes d}\to\mathbb{R}_{+}$ and
every $d$-tensor $T\in\bigotimes_{i=1}^{d}\mathbb{F}^{n_{i}}$ we have

$\mbox{\rm
Pr}_{I_{1}\sim[n_{1}]_{\sigma},\dots,I_{d}\sim[n_{d}]_{\sigma}}\big{[}\operatorname{rk}\big{(}T_{|I_{[d]}}\big{)}\geq\kappa\cdot\operatorname{rk}(T)\big{]}\geq
1-Ce^{-\kappa\operatorname{rk}(T)}.$

As noted before, the union of independent Bernoulli-random subsets of $[n]$ is
again a Bernoulli-random subset. As a consequence of this and monotonicity
under restrictions, in the standard case of “cubic” tensors where every row is
indexed by the same set, one also obtains the following symmetric version of
the last theorem:

######  Corollary 1.5.

For every $d\in\mathbb{N}$ and $\sigma\in(0,1]$, there exist constants
$C,\kappa>0$ such that the following holds. For every natural rank function
$\operatorname{rk}:(\mathbb{F}^{\infty})^{\otimes d}\to\mathbb{R}_{+}$ and
every $d$-tensor $T\in(\mathbb{F}^{n})^{\otimes d}$ we have

$\mbox{\rm
Pr}_{I\sim[n]_{\sigma}}\big{[}\operatorname{rk}\big{(}T_{|I^{d}}\big{)}\geq\kappa\cdot\operatorname{rk}(T)\big{]}\geq
1-Ce^{-\kappa\operatorname{rk}(T)}.$

Whereas the proof of the matrix case (Proposition 1.1) uses the fact that a
rank-$r$ matrix contains a full-rank $r\times r$ submatrix, the proof of the
general case of Theorem 1.4 proceeds differently and instead uses ideas from
probability theory, in particular concerning concentration inequalities on
product spaces. It will be presented in Section 2.

Recently, the topic of high-rank restrictions of tensors was explored in
detail by Karam [20], and Gowers provided an example of a 3-tensor of slice
rank $4$ which does not have a full-rank $4\times 4\times 4$ subtensor (see
[20, Proposition 3.1]). There are some interesting parallels between our
results and those of Karam, which will be discussed later on in Section 4; to
the best of our knowledge, his results do not suffice to establish our main
theorem above, or the other way around.

Next we consider the setting of polynomial maps, which are formally defined as
follows:

######  Definition 1.6 (Polynomial map).

A polynomial map is an ordered tuple
$\phi(x)=\big{(}f_{1}(x),\dots,f_{k}(x)\big{)}$ of polynomials
$f_{1},\dots,f_{k}\in\mathbb{F}[x_{1},\dots,x_{n}]$. We identify with $\phi$ a
map $\mathbb{F}^{n}\to\mathbb{F}^{k}$ in the natural way. The degree of $\phi$
is the maximum degree of the $f_{i}$.

######  Definition 1.7 (Restriction of polynomial maps).

For a polynomial map $\phi:\mathbb{F}^{n}\to\mathbb{F}^{k}$ and a set
$I\subseteq[n]$, define the restriction
$\phi_{|I}:\mathbb{F}^{I}\to\mathbb{F}^{k}$ to be the map given by
$\phi_{|I}(y)=\phi(\bar{y})$, where $\bar{y}\in\mathbb{F}^{n}$ agrees with $y$
on the coordinates in $I$ and is zero elsewhere.

We denote the space of all polynomial maps
$\phi:\mathbb{F}^{n}\to\mathbb{F}^{k}$ of degree at most $d$ by
$\operatorname{Pol}_{\leq d}(\mathbb{F}^{n},\mathbb{F}^{k})$, and write

$\operatorname{Pol}_{\leq
d}(\mathbb{F}^{\infty},\mathbb{F}^{k})=\bigcup_{n\in\mathbb{N}}\operatorname{Pol}_{\leq
d}(\mathbb{F}^{n},\mathbb{F}^{k}).$

Our main result in this setting is the following:

######  Theorem 1.8.

For every $d\in\mathbb{N}$ and $\sigma,\varepsilon\in(0,1]$, there exist
constants $\kappa=\kappa(d,\sigma)>0$ and
$R=R(d,\sigma,\varepsilon)\in\mathbb{N}$ such that the following holds. For
every natural rank function $\operatorname{rk}:\operatorname{Pol}_{\leq
d}(\mathbb{F}^{\infty},\mathbb{F}^{k})\to\mathbb{R}_{+}$ and every map
$\phi\in\operatorname{Pol}_{\leq d}(\mathbb{F}^{n},\mathbb{F}^{k})$ with
$\operatorname{rk}(\phi)\geq R$, we have

$\mbox{\rm
Pr}_{I\sim[n]_{\sigma}}\big{[}\operatorname{rk}(\phi_{|I})\geq\kappa\cdot\operatorname{rk}(\phi)\big{]}\geq
1-\varepsilon.$

The proof of this theorem will be given in Section 3. For reasons that will be
made clear in that section, this proof will be (at least superficially) quite
different from that of the tensor case, Theorem 1.4; it relies instead on
results from analysis of Boolean functions taken together with elementary
combinatorial arguments.

In Section 4 we discuss the relationship between our work and other works
present in the literature. In particular, we will explain the specific problem
which led to the study of rank under random coordinate restrictions. We will
also give a simple conditional proof of our main theorems mimicking the case
of matrices given in Proposition 1.1, as long as we assume the existence of a
so-called “linear core” which would generalize (in a somewhat weak sense) the
existence of a full-rank $r\times r$ submatrix inside matrices of rank $r$.
Finally, we propose some open problems to further our understanding of rank
functions.

###  1.3. Notation

Here we collect some notation that will be used throughout the paper. Given
sets $I_{1},\dots,I_{d}$, we write $I_{[d]}=I_{1}\times\cdots\times I_{d}$.
For a set $J$ and some $\sigma\in[0,1]$, we denote by $\pi_{\sigma}^{J}$ the
product distribution on $\\{0,1\\}^{J}$ where each coordinate is independently
set to $1$ with probability $\sigma$, or to $0$ with probability $1-\sigma$;
when $J=[n]$, we write simply $\pi_{\sigma}^{n}$. We write $J_{\sigma}$ for
the probability distribution over subsets of $J$ where each element is present
independently with probability $\sigma$. To denote that a random variable $X$
is distributed according to a distribution $\mu$, we write $X\sim\mu$.

##  2\. Tensors

Recall that, for a field $\mathbb{F}$ and integer $d\geq 2$, we denote by
$(\mathbb{F}^{\infty})^{\otimes d}$ the set of all $d$-tensors of finite
support over $\mathbb{F}$. All our results (including the values of the
implied constants) will hold independently of the field considered, so we will
always denote it by $\mathbb{F}$ without further comment.

The notions of tensor rank we will consider here are those called _natural
rank functions_ as defined below:

######  Definition 2.1 (Natural rank).

We say that $\operatorname{rk}:(\mathbb{F}^{\infty})^{\otimes
d}\to\mathbb{R}_{+}$ is a natural rank function if it satisfies the following
properties:

  1. (1)

Sub-additivity:
$\operatorname{rk}(T+S)\leq\operatorname{rk}(T)+\operatorname{rk}(S)$ for all
$T,S\in(\mathbb{F}^{\infty})^{\otimes d}$.

  2. (2)

Monotonicity under restrictions:
$\operatorname{rk}\big{(}T_{|I_{[d]}}\big{)}\leq\operatorname{rk}(T)$ for all
$T\in(\mathbb{F}^{\infty})^{\otimes d}$ and all sets
$I_{1},\dots,I_{d}\subset\mathbb{N}$.

  3. (3)

Restriction Lipschitz property:
$\operatorname{rk}\big{(}T_{|J_{[d]}}\big{)}\leq\operatorname{rk}\big{(}T_{|I_{[d]}}\big{)}+\sum_{i=1}^{d}|J_{i}\setminus
I_{i}|$ for all $T\in(\mathbb{F}^{\infty})^{\otimes d}$ and all sets
$I_{1}\subseteq J_{1},\dots,I_{d}\subseteq J_{d}$.

In order to motivate this definition, we now discuss several examples (and one
non-example) of natural rank functions that have been studied in the
literature. In what follows, given $i\in[d]$ and an element $u\in X_{i}$, the
restriction of $T:X_{1}\times\cdots\times X_{d}\to\mathbb{F}$ to the set
$X_{1}\times\cdots X_{i-1}\times\\{u\\}\times X_{i+1}\times\cdots\times X_{d}$
is referred to as a _slice_. Note that property (3) implies that a slice has
rank at most 1; conversely, under the assumption of property (1), property (3)
is satisfied provided that slices have rank at most 1.

#### Slice rank

The notion of slice rank was introduced by Tao [33] to give a more symmetric
version of Ellenberg and Gijswijt’s proof [11] of the cap set conjecture, and
was later further studied by Sawin and Tao [34]. It has been used in the study
of several extremal combinatorics problems, such as bounding the maximal sizes
of tri-colored sum-free sets [2] and sunflower-free sets [28], as well as
obtaining essentially tight bounds for Green’s arithmetic triangle removal
lemma [12].

A nonzero $d$-tensor $T$ (viewed as a multi-linear form) has slice rank 1 if
there exist $i\in[d]$, $R:\mathbb{F}^{X_{i}}\to\mathbb{F}$ and
$S:\prod_{j\in[d]\setminus\\{i\\}}\mathbb{F}^{X_{j}}\to\mathbb{F}$ such that
$T$ can be factored as $T=RS$. In general, the slice rank of $T$, denoted
$\operatorname{srank}(T)$, is then defined as the least $r\in\mathbb{N}$ such
that there is a decomposition $T=T_{1}+\cdots+T_{r}$ where each $T_{i}$ has
slice rank 1. Slice rank is sub-additive since the sum of decompositions of
two tensors $S,T$ gives a decomposition of $S+T$. It is monotone under
restrictions since a decomposition of $T$ induces a decomposition of its
restrictions. The restriction Lipschitz property can easily be verified
inductively slice-by-slice using sub-additivity.

#### Partition rank

The partition rank was introduced by Naslund [27] as a more general version of
the slice rank which allows one to handle problems that require variables to
be distinct. It was first used to provide bounds on the size of subsets of
$\mathbb{F}_{q}^{n}$ not containing $k$-right corners [27], as well as an
upper bound for the Erdős-Ginzburg-Ziv constant of $\mathbb{F}_{p}^{n}$ [26].

A nonzero $d$-tensor $T$ is defined to have partition rank 1 if there is a
nonempty strict subset $I\subset[d]$ and tensors $S:\prod_{i\in
I}\mathbb{F}^{X_{i}}\to\mathbb{F}$ and $R=\prod_{i\in[d]\setminus
I}\mathbb{F}^{X_{i}}\to\mathbb{F}$ such that $T$ can be factored as $T=SR$ .
In general, the partition rank of $T$, denoted $\operatorname{prank}(T)$, is
defined as the least $r\in\mathbb{N}$ such that there is a decomposition
$T=T_{1}+\cdots+T_{r}$ where each $T_{i}$ has partition rank 1. The properties
of Definition 2.1 for partition rank follow for the same reasons as for slice
rank.

#### Analytic rank

The notion of analytic rank was introduced by Gowers and Wolf [15] when
studying an arithmetic notion of complexity for linear systems of equations
over $\mathbb{F}_{p}^{n}$. It gives a quantitative measure of equidistribution
for the values taken by a tensor, and as such are well suited for arguments
relying on the dichotomy between structure and randomness. The analytic rank
was further studied by Lovett [25], and more recently it was used by the first
author in a problem concerning a random version of Szemerédi’s theorem over
finite fields [4].

The analytic rank is defined only if $\mathbb{F}$ is finite. For a non-trivial
additive character $\chi:\mathbb{F}\to\mathbb{C}^{*}$, the bias of a
$d$-tensor $T$ is defined by

$\operatorname{bias}(T)={\mathbb{E}}_{x_{1}\in\mathbb{F}^{X_{1}},\dots,x_{d}\in\mathbb{F}^{X_{d}}}\chi\big{(}T(x_{1},\dots,x_{d})\big{)};$

this definition is easily shown to be independent of the character $\chi$
chosen. The analytic rank of $T$ is then defined by

$\operatorname{arank}(T)=-\log_{|\mathbb{F}|}\operatorname{bias}(T).$

Lovett proved that the analytic rank is sub-additive [25, Theorem 1.5].
Monotonicity follows from [25, Lemma 2.1]. The restriction Lipschitz property
now follows from sub-additivity and the fact that a single slice has analytic
rank at most 1.

#### Geometric rank

Motivated by applications in algebraic complexity theory and extremal
combinatorics, as well as an open problem posed by Lovett, the geometric rank
was introduced by Kopparty, Moshkovitz and Zuiddam [23] as a natural extension
of analytic rank beyond finite fields. While its definition is algebraic
geometric in nature, it turns out to have deep connections with partition rank
and analytic rank, as shown by Cohen and Moshkovitz [7, 6].

For an algebraically closed field $\mathbb{F}$, the geometric rank of a
$d$-tensor $T$ is defined as

$\operatorname{GR}(T)=\operatorname{codim}\\{(x_{1},\dots,x_{d-1}):\,T(x_{1},\dots,x_{d-1},\cdot)=0\\},$

where $\operatorname{codim}$ denotes the codimension of an algebraic variety.
If the field $\mathbb{F}$ considered is not algebraically closed, then the
geometric rank is naturally defined via the embedding of $\mathbb{F}$ in its
algebraic closure. Sub-additivity and monotonicity of this rank function
follow directly from Lemma 4.2 and Lemma 4.4 of [23], respectively. The
restriction Lipschitz property follows from these properties and the fact that
a single slice has geometric rank at most 1.

#### Tensor rank

It is also instructive to remark on an important non-example, the notion
usually known simply as tensor rank, which is an important notion in the
context of computational complexity (see for instance [24, 29]). A nonzero
$d$-tensor $T$ has tensor rank 1 if it decomposes as
$T=\bigotimes_{i\in[d]}u_{i}$ for some functions
$u_{i}:\mathbb{F}^{X_{i}}\to\mathbb{F}$. The tensor rank of a general
$d$-tensor $T$ is then defined as the least $r\in\mathbb{N}$ such that
$T=T_{1}+\cdots+T_{r}$, where each $T_{i}$ has rank 1.

This rank function is not natural according to our Definition 2.1 because it
fails the restriction Lipschitz property. Consider for instance the 3-tensor
$T\in\mathbb{F}^{n\times n\times 2}$ consisting of the identity matrix stacked
on top of an all-ones matrix. The identity slice has tensor rank $n$ (which
implies that $T$ has tensor rank at least $n$), while the all-ones slice has
tensor rank 1. Thus, removing the identity slice reduces the tensor rank of
$T$ by at least $n-1$, instead of reducing it by at most 1 as required by the
restriction Lipschitz condition. This should not be taken as an indication
that our definition is too restrictive, however, as this example also shows
that Theorem 1.4 does _not_ hold for tensor rank: a $\sigma$-random
restriction of $T$ has tensor rank at most 1 with probability $1-\sigma$.
(This simple example can also be generalized in many ways.)

The main result of this section concerns how natural rank functions behave
under random coordinate restrictions. Intuitively, it shows that random
restrictions of high-rank tensors will also have high rank with high
probability. For convenience, we repeat below its formal statement as given in
the Introduction.

######  Theorem 2.2 (Theorem 1.4 restated).

For every $d\in\mathbb{N}$ and $\sigma\in(0,1]$, there exist constants
$C,\kappa>0$ such that the following holds. For every natural rank function
$\operatorname{rk}:(\mathbb{F}^{\infty})^{\otimes d}\to\mathbb{R}_{+}$ and
every $d$-tensor $T\in\bigotimes_{i=1}^{d}\mathbb{F}^{n_{i}}$ we have

$\mbox{\rm
Pr}_{I_{1}\sim[n_{1}]_{\sigma},\dots,I_{d}\sim[n_{d}]_{\sigma}}\big{[}\operatorname{rk}\big{(}T_{|I_{[d]}}\big{)}\geq\kappa\cdot\operatorname{rk}(T)\big{]}\geq
1-Ce^{-\kappa\operatorname{rk}(T)}.$

We note that our proof also obtains good quantitative bounds for the
parameters in the theorem, namely

$\displaystyle C=d\sqrt{\frac{3}{2\sigma}}\quad$
$\displaystyle\text{and}\quad\kappa=\frac{\ln
2}{3}\Big{(}\frac{\sigma}{4}\Big{)}^{d}\quad\text{if }\sigma\in(0,1/2),$
$\displaystyle C=d\sqrt{2}\quad$ $\displaystyle\text{and}\quad\kappa=\frac{\ln
2}{2}\Big{(}\frac{1}{6}\Big{)}^{d}\quad\text{if }\sigma\in[1/2,1].$

Note that one must always have $\kappa\leq\sigma^{d}$, as can be seen by
considering a diagonal tensor $T$ and the slice rank function
$\operatorname{srank}$, which for diagonal tensors equals the size of their
support [33, Lemma 1].

###  2.1. Concentration for monotone sub-additive functions

The main step in our proof of Theorem 1.4 is a type of concentration
inequality for monotone sub-additive functions on the hypercube.

In order to obtain such a result we will consider a notion of _two-point
distance_ from sets $A\subseteq\\{0,1\\}^{n}$, which intuitively measures how
many coordinates of some given point $x$ cannot be captured by any two
elements of $A$.

######  Definition 2.3.

Given a point $x\in\\{0,1\\}^{n}$ and a set $A\subseteq\\{0,1\\}^{n}$, the
two-point distance between $x$ and $A$ is

$h_{2}(x;A)=\min_{y,z\in A}\big{|}\big{\\{}i\in[n]:\,x_{i}\neq y_{i}\And
x_{i}\neq z_{i}\big{\\}}\big{|}.$

Note that this “distance” $h_{2}(x;A)$ can be zero even if $x\notin A$; for
instance, $h_{2}\big{(}00;\,\\{01,10\\}\big{)}=0$. The reason for considering
this notion is that one gets much better concentration for $h_{2}$ than one
does for the usual Hamming distance. This is shown by the following result,
which is a special case of an inequality of Talagrand [32, Theorem 3.1.1]:

######  Theorem 2.4.

Let $A\subseteq\\{0,1\\}^{n}$ be a set and $\mu=\bigotimes_{i=1}^{n}\mu_{i}$
be a product probability measure on $\\{0,1\\}^{n}$. Then

$\mbox{\rm Pr}_{x\sim\mu}\big{[}h_{2}(x;A)\geq k\big{]}\leq
2^{-k}\mu(A)^{-2}\quad\text{for all $k\geq 0$.}$

The next lemma is the key result needed for proving our main theorem for
tensors, and it deals more abstractly with monotone, sub-additive Lipschitz
functions on the hypercube. We endow $\\{0,1\\}^{n}$ with the usual partial
order, where $x\leq y$ if the support of $x$ is contained in the support of
$y$. A function $f:\\{0,1\\}^{n}\to\mathbb{R}$ is monotone if $f(x)\leq f(y)$
whenever $x\leq y$, and it is sub-additive if $f(x+y)\leq f(x)+f(y)$ for all
$x,y\in\\{0,1\\}^{n}$ with disjoint supports. Finally, $f$ is $1$-Lipschitz if

$\big{|}f(x)-f(y)\big{|}\leq\big{|}\big{\\{}i\in[n]:\,x_{i}\neq
y_{i}\big{\\}}\big{|}\quad\text{for all $x,y\in\\{0,1\\}^{n}$}.$

For a string $x\in\\{0,1\\}^{n}$ and set $I\subseteq[n]$, we let
$x_{I}\in\\{0,1\\}^{n}$ be the string that equals $x$ on the indices in $I$
and is zero elsewhere. The lemma that follows and its proof are inspired by an
argument of Schechtman [30, Corollary 12].

######  Lemma 2.5 (Concentration inequality).

Let $f:\\{0,1\\}^{n}\to\mathbb{R}_{+}$ be a monotone, sub-additive
$1$-Lipschitz function with maximum value $r$. Then

$\displaystyle\mbox{\rm Pr}_{x\sim\pi_{\sigma}^{n}}\big{[}f(x)\leq\sigma
r/4\big{]}$ $\displaystyle\leq\sqrt{\frac{3}{2\sigma}}\,2^{-\sigma r/12}\quad$
if $\,0<\sigma<1/2$, $\displaystyle\mbox{\rm
Pr}_{x\sim\pi_{\sigma}^{n}}\big{[}f(x)\leq r/6\big{]}$
$\displaystyle\leq\sqrt{2}\,2^{-r/12}$ if $\,1/2\leq\sigma\leq 1$.

  * Proof:

We first prove the first inequality above. Let $\sigma\in(0,1/2)$, and
consider the set

$A=\big{\\{}x\in\\{0,1\\}^{n}:\,f(x)\leq\sigma r/4\big{\\}}.$

By Talagrand’s Inequality (Theorem 2.4) we have

$\mbox{\rm Pr}_{x\sim\pi_{\sigma}^{n}}\big{[}h_{2}(x;A)\geq\sigma
r/6\big{]}\leq 2^{-\sigma r/6}\,\mbox{\rm
Pr}_{x\sim\pi_{\sigma}^{n}}\big{[}f(x)\leq\sigma r/4\big{]}^{-2},$

so to finish the proof it suffices to show that

$\mbox{\rm Pr}_{x\sim\pi_{\sigma}^{n}}\big{[}h_{2}(x;A)\geq\sigma
r/6\big{]}\geq 2\sigma/3.$

We claim that

(1) $\big{\\{}x\in\\{0,1\\}^{n}:\,f(x)\geq 2\sigma
r/3\big{\\}}\subseteq\big{\\{}x\in\\{0,1\\}^{n}:\,h_{2}(x;A)\geq\sigma
r/6\big{\\}}.$

Indeed, if $h_{2}(x;A)<\sigma r/6$ then there are $y,z\in A$ such that

$\big{|}\big{\\{}i\in[n]:\,x_{i}\neq y_{i}\And x_{i}\neq
z_{i}\big{\\}}\big{|}<\sigma r/6.$

Denote $I=\big{\\{}i\in[n]:\,x_{i}\neq y_{i}\And x_{i}\neq z_{i}\big{\\}}$,
$J=\big{\\{}i\in[n]:\,x_{i}=y_{i}\big{\\}}$ and
$J^{\prime}=\big{\\{}i\in[n]:\,x_{i}\neq y_{i}\And x_{i}=z_{i}\big{\\}}$; note
that these sets partition $[n]$, and by assumption $|I|<\sigma r/6$. We then
have

$\displaystyle f(x)$ $\displaystyle\leq f(x_{I}+x_{J})+f(x_{J^{\prime}})$
$\displaystyle=f(x_{I}+y_{J})+f(z_{J^{\prime}})$
$\displaystyle\leq|I|+f(y_{J})+f(z_{J^{\prime}})$
$\displaystyle\leq|I|+f(y)+f(z)$ $\displaystyle<2\sigma r/3,$

so $\big{\\{}h_{2}(x;A)<\sigma r/6\big{\\}}\subseteq\big{\\{}f(x)<2\sigma
r/3\big{\\}}$ and inclusion (1) follows. It thus suffices to show that
$\mbox{\rm Pr}_{x\sim\pi_{\sigma}^{n}}\big{[}f(x)\geq 2\sigma r/3\big{]}\geq
2\sigma/3$.

We will next prove that, for any integer $k\geq 1$, we have

(2) $\mbox{\rm Pr}_{x\sim\pi_{1/k}^{n}}\big{[}f(x)\geq r/k\big{]}\geq 1/k.$

This is done by a simple _coupling argument_ , which will be important for us
again later on. Consider a uniformly random ordered $k$-partition
$(I_{1},\dots,I_{k})$ of $[n]$; thus the $k$ sets $I_{i}$ are pairwise
disjoint and have union $[n]$, with each of the $k^{n}$ possible such
$k$-tuples having the same probability. Denoting by $\mathbf{1}_{I}$ the
indicator function of set $I$, we have

$r=f(\mathbf{1}_{[n]})=f(\mathbf{1}_{I_{1}}+\dots+\mathbf{1}_{I_{k}})\leq\sum_{i=1}^{k}f(\mathbf{1}_{I_{i}}),$

so $f(\mathbf{1}_{I_{i}})\geq r/k$ holds for at least one $i\in[k]$ in _every_
ordered partition $(I_{1},\dots,I_{k})$. By symmetry, it follows that
$\mbox{\rm Pr}\big{[}f(\mathbf{1}_{I_{1}})\geq r/k\big{]}\geq 1/k$. Since the
marginal distribution of $\mathbf{1}_{I_{1}}$ (and every other
$\mathbf{1}_{I_{i}}$) is precisely $\pi_{1/k}^{n}$, we conclude that

$\mbox{\rm Pr}_{x\sim\pi_{1/k}^{n}}\big{[}f(x)\geq r/k\big{]}=\mbox{\rm
Pr}\big{[}f(\mathbf{1}_{I_{1}})\geq r/k\big{]}\geq 1/k,$

as wished.

Now let $k=\lceil 1/\sigma\rceil$. Since $0<\sigma<1/2$, we have
$2\sigma/3\leq 1/k\leq\sigma$, and so by monotonicity of $f$

$\displaystyle\mbox{\rm Pr}_{x\sim\pi_{\sigma}^{n}}\big{[}f(x)\geq 2\sigma
r/3\big{]}$ $\displaystyle\geq\mbox{\rm
Pr}_{x\sim\pi_{1/k}^{n}}\big{[}f(x)\geq 2\sigma r/3\big{]}$
$\displaystyle\geq\mbox{\rm Pr}_{x\sim\pi_{1/k}^{n}}\big{[}f(x)\geq
r/k\big{]}.$

From inequality (2) we then conclude that

$\mbox{\rm Pr}_{x\sim\pi_{\sigma}^{n}}\big{[}f(x)\geq 2\sigma r/3\big{]}\geq
1/k\geq 2\sigma/3,$

finishing the proof of the first inequality in the statement of the lemma.

The second inequality is proven using the same arguments, now applied to the
parameter $\sigma=1/2$ and the set $A=\big{\\{}x\in\\{0,1\\}^{n}:\,f(x)\leq
r/6\big{\\}}$. We obtain slightly better bounds since in this case
$1/\sigma=2$ is an integer, and so no rounding errors occur. By monotonicity
of $f$, the same bound continues to hold for all $\sigma>1/2$. $\Box$

###  2.2. The Random Restriction Theorem

It is now a simple matter to use Lemma 2.5 to prove the Random Restriction
Theorem for tensors.

  * Proof of Theorem 1.4:

Let $\operatorname{rk}:(\mathbb{F}^{\infty})^{\otimes d}\to\mathbb{R}$ be a
natural rank function, and $T\in\bigotimes_{i=1}^{d}\mathbb{F}^{n_{i}}$ be a
tensor. We wish to show that

$\mbox{\rm
Pr}_{I_{1}\sim[n_{1}]_{\sigma},\dots,I_{d}\sim[n_{d}]_{\sigma}}\big{[}\operatorname{rk}\big{(}T_{|I_{[d]}}\big{)}\geq\kappa(\sigma)\cdot\operatorname{rk}(T)\big{]}\geq
1-C(\sigma)e^{-\kappa(\sigma)\operatorname{rk}(T)}$

for some well-chosen constants $C(\sigma),\kappa(\sigma)>0$ depending only on
the value of $\sigma>0$ and the order $d$ of the tensor. We consider here the
case where $\sigma<1/2$, as the case where $\sigma\geq 1/2$ is
analogous.111This second case is also an immediate consequence of first case
together with monotonicity of $\operatorname{rk}$ under restrictions.

Define the function $f_{1}:\\{0,1\\}^{n_{1}}\to\mathbb{R}_{+}$ as follows: for
$x\in\\{0,1\\}^{n_{1}}$ with support $J$, $f_{1}(x)$ is the rank of the
subtensor of $T$ whose indices of the first row belong to $J$. In formula:

$f_{1}(\mathbf{1}_{J})=\operatorname{rk}\big{(}T_{|J\times\prod_{j=2}^{d}[n_{j}]}\big{)}\quad\text{for
all }J\subseteq[n_{1}].$

By the definition of natural rank, $f_{1}$ is a monotone, sub-additive
$1$-Lipschitz function with maximum value $\operatorname{rk}(T)$. Since
$\mathbf{1}_{J}\sim\pi_{\sigma}^{n_{1}}$ when $J\sim[n_{1}]_{\sigma}$, it
follows from Lemma 2.5 that

(3) $\mbox{\rm
Pr}_{I_{1}\sim[n_{1}]_{\sigma}}\bigg{[}\operatorname{rk}\big{(}T_{|I_{1}\times\prod_{j=2}^{d}[n_{j}]}\big{)}\geq\frac{\sigma\operatorname{rk}(T)}{4}\bigg{]}\geq
1-\sqrt{\frac{3}{2\sigma}}\,2^{-\frac{\sigma}{12}\operatorname{rk}(T)}.$

For any fixed $I_{1}\subseteq[n_{1}]$ satisfying
$f_{1}(\mathbf{1}_{I_{1}})\geq\sigma\operatorname{rk}(T)/4$, we define the
function $f_{2}:\\{0,1\\}^{n_{2}}\to\mathbb{R}_{+}$ by

$f_{2}(\mathbf{1}_{J})=\operatorname{rk}\big{(}T_{|I_{1}\times
J\times\prod_{j=3}^{d}[n_{j}]}\big{)}\quad\text{for all }J\subseteq[n_{2}].$

This function is again monotone, sub-additive and $1$-Lipschitz, and it has
maximum value at least $\sigma\operatorname{rk}(T)/4$. By Lemma 2.5 we have

$\mbox{\rm
Pr}_{I_{2}\sim[n_{2}]_{\sigma}}\bigg{[}\operatorname{rk}\big{(}T_{|I_{1}\times
I_{2}\times\prod_{j=3}^{d}[n_{j}]}\big{)}\geq\Big{(}\frac{\sigma}{4}\Big{)}^{2}\operatorname{rk}(T)\bigg{]}\geq
1-\sqrt{\frac{3}{2\sigma}}\,2^{-\frac{\sigma}{12}\frac{\sigma}{4}\operatorname{rk}(T)}.$

Since this holds whenever
$f_{1}(\mathbf{1}_{I_{1}})\geq\sigma\operatorname{rk}(T)/4$, taking the union
bound together with inequality (3) we obtain

$\mbox{\rm
Pr}_{I_{1}\sim[n_{1}]_{\sigma},I_{2}\sim[n_{2}]_{\sigma}}\bigg{[}\operatorname{rk}\big{(}T_{|I_{1}\times
I_{2}\times\prod_{j=3}^{d}[n_{j}]}\big{)}\geq\Big{(}\frac{\sigma}{4}\Big{)}^{2}\operatorname{rk}(T)\bigg{]}\geq
1-2\sqrt{\frac{3}{2\sigma}}\,2^{-\frac{\sigma}{12}\frac{\sigma}{4}\operatorname{rk}(T)}.$

Proceeding in this same way for each row of the tensor, and always taking the
union bound, we eventually conclude that

$\mbox{\rm
Pr}_{I_{1}\sim[n_{1}]_{\sigma},\dots,I_{d}\sim[n_{d}]_{\sigma}}\bigg{[}\operatorname{rk}\big{(}T_{|I_{[d]}}\big{)}\geq\Big{(}\frac{\sigma}{4}\Big{)}^{d}\operatorname{rk}(T)\bigg{]}\geq
1-d\sqrt{\frac{3}{2\sigma}}\,2^{-\frac{\sigma}{12}(\frac{\sigma}{4})^{d-1}\operatorname{rk}(T)},$

which finishes the proof. $\Box$

##  3\. Polynomial maps

Next we consider the setting of polynomials and higher-dimensional polynomial
maps. Recall that $\operatorname{Pol}_{\leq d}(\mathbb{F}^{n},\mathbb{F}^{k})$
is the space of all polynomial maps $\phi:\mathbb{F}^{n}\to\mathbb{F}^{k}$ of
degree at most $d$, and $\operatorname{Pol}_{\leq
d}(\mathbb{F}^{\infty},\mathbb{F}^{k})=\bigcup_{n\in\mathbb{N}}\operatorname{Pol}_{\leq
d}(\mathbb{F}^{n},\mathbb{F}^{k})$ is the space of all $k$-dimensional
polynomial maps over $\mathbb{F}$ of degree at most $d$.

######  Definition 3.1 (Natural rank).

We say that $\operatorname{rk}:\operatorname{Pol}_{\leq
d}(\mathbb{F}^{\infty},\mathbb{F}^{k})\to\mathbb{R}_{+}$ is a natural rank
function if it satisfies the following properties:

  1. (1)

Symmetry:
$\operatorname{rk}(\phi)=\operatorname{rk}(-\phi)$ for all
$\phi\in\operatorname{Pol}_{\leq d}(\mathbb{F}^{\infty},\mathbb{F}^{k})$.

  2. (2)

Sub-additivity:
$\operatorname{rk}(\phi+\gamma)\leq\operatorname{rk}(\phi)+\operatorname{rk}(\gamma)$
for all $\phi,\gamma\in\operatorname{Pol}_{\leq
d}(\mathbb{F}^{\infty},\mathbb{F}^{k})$.

  3. (3)

Monotonicity under restrictions:
$\operatorname{rk}(\phi_{|I})\leq\operatorname{rk}(\phi)$ for all
$\phi\in\operatorname{Pol}_{\leq d}(\mathbb{F}^{\infty},\mathbb{F}^{k})$ and
all sets $I\subset\mathbb{N}$.

  4. (4)

Restriction Lipschitz property:
$\operatorname{rk}(\phi_{|I\cup J})\leq\operatorname{rk}(\phi_{|I})+|J|$ for
all $\phi\in\operatorname{Pol}_{\leq d}(\mathbb{F}^{\infty},\mathbb{F}^{k})$
and all sets $I,J\subset\mathbb{N}$.

Below we discuss some natural rank functions for polynomial maps which have
appeared in the literature. Symmetry holds trivially for each of the ranks
discussed.

#### Degree rank

Motivated by proving a version of the Gowers Inverse Theorem for polynomial
phase functions, Green and Tao defined the notion of degree rank for functions
over $\mathbb{F}_{p}^{n}$ and showed that it is closely related to
equidistribution properties of polynomials [16]. For an integer $d\geq 1$, the
degree-$d$ rank of a function $f:\mathbb{F}^{n}\to\mathbb{F}$, denoted
$\operatorname{rk}_{d}(f)$, is the least $r\in\mathbb{N}$ such that there
exist polynomials $Q_{1},\dots,Q_{r}\in\mathbb{F}[x_{1},\dots,x_{n}]$ of
degree at most $d$ and a function $\Gamma:\mathbb{F}^{r}\to\mathbb{F}$ such
that $f$ can be decomposed as
$f(x)=\Gamma\big{(}Q_{1}(x),\dots,Q_{r}(x)\big{)}$. A slightly modified
version of this rank function, where one also allows “nonclassical
polynomials” to enter the decomposition, was instrumental in the proof of the
general Gowers Inverse Theorem over $\mathbb{F}_{p}^{n}$ by Tao and Ziegler
[35].

It turns out that, restricted to polynomials of degree at most $d$, the
function $\tfrac{1}{2}\operatorname{rk}_{d-1}$ is a natural rank function.
(The need to divide by $2$ is a normalization matter which has no important
impact.) Sub-additivity of this rank function follows directly since the sum
of decompositions of two polynomials $P,Q$ gives a decomposition of their sum
$P+Q$. Monotonicity follows since a decomposition of $P$ induces a
decomposition of any restriction $P_{|I}$. The restriction Lipschitz property
can be verified inductively using the fact that for a polynomial
$P\in\mathbb{F}[x_{1},\dots,x_{n}]$ of degree at most $d$, we have that
$P=P_{|[n-1]}+x_{n}P^{\prime}$ for some polynomial $P^{\prime}$ of degree at
most $d-1$. This shows that
$\operatorname{rk}_{d-1}(P)\leq\operatorname{rk}_{d-1}(P_{|[n-1]})+2$, where
the extra 2 comes from the polynomials $P^{\prime}$ and $x_{n}$.

#### Schmidt rank

A refinement of the notion of degree-$d$ rank was introduced by Schmidt in
[31], which was rediscovered independently on multiple occasions later on. The
same notion, specialized to cubic polynomials, was defined in [9] and referred
to as q-rank, while in [21] it was defined for homogeneous polynomials and
referred to simply as rank. It appeared under the name strength in [1], it was
studied in [18] without being explicitly defined and then again in [19], where
it was called strong rank.

A polynomial $P\in\mathbb{F}[x_{1},\dots,x_{n}]$ has Schmidt rank 1 if it is
reducible (i.e., it factors as $P=QR$ for two non-constant polynomials $Q,R$).
The Schmidt rank of a general polynomial, which we will denote
$\operatorname{prank}(P)$ to reflect its similarity with partition rank for
tensors, is the least $r\in\mathbb{N}$ such that $P$ can be decomposed as
$P=P_{1}+\cdots+P_{r}$, where each $P_{i}$ is reducible. Sub-additivity and
monotonicity follow for the same reasons as for slice and partition rank. The
argument used for degree-$d$ rank shows the restriction Lipschitz property.

#### Analytic rank

The next notion of rank is defined more generally for higher-dimensional
polynomial maps, and requires the field $\mathbb{F}$ to be finite. It was
introduced in the context of circuit complexity and error-correcting codes
[5]; see Section 4 for more details. For a finite field $\mathbb{F}$, the
analytic $d$-rank of a map $\phi\in\operatorname{Pol}_{\leq
d}(\mathbb{F}^{n};\mathbb{F}^{k})$ is defined by

$\operatorname{arank}_{d}(\phi)=-\log_{|\mathbb{F}|}\bigg{(}\max_{\psi:\mathbb{F}^{n}\to\mathbb{F}^{k},\,\deg(\psi)<d}\mbox{\rm
Pr}_{x\in\mathbb{F}^{n}}\big{[}\phi(x)=\psi(x)\big{]}\bigg{)}.$

Sub-additivity, monotonicity and the restriction Lipschitz property for this
rank function were proven in [5, Section 5].

Finally, we note that there is also another notion of analytic rank specific
to polynomials, which equals the tensor analytic rank of their associated
homogeneous multilinear form. It was introduced together with the notion of
tensor analytic rank by Gowers and Wolf [15], and can be equivalently defined
for polynomials $P$ of degree $d$ by

$-\log_{|\mathbb{F}|}\|\chi(P)\|_{U^{d}}^{2^{d}},$

where $\chi$ is a nontrivial additive character of $\mathbb{F}$ and
$\|\cdot\|_{U^{d}}$ is the Gowers uniformity norm of order $d$. Sub-additivity
and monotonicity under restrictions follow from the corresponding properties
for tensor analytic rank. Upon normalization by a factor $1/d$, the
restriction Lipschitz property follows from the same property for the analytic
rank of tensors. This notion of rank was also important in Tao and Ziegler’s
proof of the Gowers Inverse Theorem over $\mathbb{F}_{p}^{n}$ [35].

Our main result shows that random restrictions of a high-rank polynomial map
will also have high rank with high probability. We recall below its formal
statement as given in the Introduction.

######  Theorem 3.2 (Theorem 1.8 restated).

For every $d\in\mathbb{N}$ and $\sigma,\varepsilon\in(0,1]$, there exist
constants $\kappa=\kappa(d,\sigma)>0$ and
$R=R(d,\sigma,\varepsilon)\in\mathbb{N}$ such that the following holds. For
every natural rank function $\operatorname{rk}:\operatorname{Pol}_{\leq
d}(\mathbb{F}^{\infty},\mathbb{F}^{k})\to\mathbb{R}$ and every map
$\phi\in\operatorname{Pol}_{\leq d}(\mathbb{F}^{n},\mathbb{F}^{k})$ with
$\operatorname{rk}(\phi)\geq R$, we have

$\mbox{\rm
Pr}_{I\sim[n]_{\sigma}}\big{[}\operatorname{rk}(\phi_{|I})\geq\kappa\cdot\operatorname{rk}(\phi)\big{]}\geq
1-\varepsilon.$

The proof of this theorem proceeds differently from the proof of Theorem 1.4,
which gives the analogous result for tensors. The reason for this is that the
natural choice of function $f:\\{0,1\\}^{n}\to\mathbb{R}_{+}$ to which one
might apply the concentration inequality in Lemma 2.5, given by
$f(\mathbf{1}_{I})=\operatorname{rk}(\phi_{|I})$ (for some rank function
$\operatorname{rk}$), might fail to be 1-Lipschitz. For instance, consider (in
dimension $k=1$) a $2n$-variate polynomial
$p(x_{1},\dots,x_{n},y_{1},\dots,y_{n})$ such that each monomial contains both
an $x$ variable and a $y$ variable. Then the rank of $p$ restricted only to
its $x$ variables is zero, and similarly for the restriction to the $y$
variables, while $\operatorname{rk}(p)$ can be of order $\Theta(n)$. This
shows that $\operatorname{rk}(p_{|I\cup J})$ can be much larger than
$\operatorname{rk}(p_{|I})+\operatorname{rk}(p_{|J})$, and the argument used
in the tensor case breaks down.

###  3.1. The proof in expectation

The first step in our proof of Theorem 1.8 is to show that the desired result
is true _in expectation_ , rather than with high probability. More precisely,
our next lemma shows that the rank of random restrictions of a polynomial map
are, in expectation, comparable to the rank of the full map.

######  Lemma 3.3 (Linear expectation).

For every $\sigma\in(0,1]$ and every integer $d\geq 1$ there exists a constant
$c(\sigma,d)>0$ such that the following holds. For all $n,k\geq 1$ and all
maps $\phi\in\operatorname{Pol}_{\leq d}(\mathbb{F}^{n},\mathbb{F}^{k})$ we
have

${\mathbb{E}}_{J\sim[n]_{\sigma}}\operatorname{rk}(\phi_{|J})\geq
c(\sigma,d)\operatorname{rk}(\phi).$

This will be shown by an inductive argument which requires some further
restrictions on the variables of the polynomial map, as well as some further
notation. Given a polynomial map $\phi:\mathbb{F}^{n}\to\mathbb{F}^{k}$ and a
set $I\subseteq[n]$, we denote by $\deg_{I}(\phi)$ the total degree of the
variables indexed by $I$ in $\phi$, when all other variables are taken as
constants. For instance, if $n=4$, $k=1$ and

$\phi(x_{1},x_{2},x_{3},x_{4})=x_{1}^{2}x_{2}x_{4}+2x_{3}^{2}x_{4},$

then (as long as $\operatorname{char}(\mathbb{F})\neq 2$) we have
$\deg_{\\{1,2\\}}(\phi)=\deg_{\\{1,4\\}}(\phi)=3$, $\deg_{\\{2,3\\}}(\phi)=2$
and $\deg_{\\{4\\}}(\phi)=1$. Note that, in general,
$\deg_{I}(\phi)\neq\deg(\phi_{|I})$ due to the presence of monomials
containing both variables indexed by $I$ and variables indexed by
$[n]\setminus I$ (which are then regarded as constants).

We denote by $I^{c}:=[n]\setminus I$ the complement of the set $I$, and (as
usual) $J\sim I_{\sigma}$ denotes the random process of choosing a subset of
$I$ where each element $i\in I$ belongs to $J$ independently with probability
$\sigma$. Lemma 3.3 follows as a special case of the more technical lemma
bellow when we take $I=[n]$ and $\ell=d$.

######  Lemma 3.4.

For every $\sigma\in(0,1]$ and every integer $\ell\geq 1$ there exists a
constant $c(\sigma,\ell)>0$ such that the following holds. Let $d,n,k\geq 1$
be integers, $\phi\in\operatorname{Pol}_{\leq
d}(\mathbb{F}^{n},\mathbb{F}^{k})$ be a polynomial map and $I\subseteq[n]$ be
a set for which $\deg_{I}(\phi)\leq\ell$. Then

${\mathbb{E}}_{J\sim I_{\sigma}}\operatorname{rk}(\phi_{|J\cup I^{c}})\geq
c(\sigma,\ell)\operatorname{rk}(\phi).$

  * Proof:

Denote $m=\lceil 1/\sigma\rceil$. We will proceed by induction on $\ell\geq 1$
(note that the result is trivial if $\deg_{I}(\phi)=0$).

For the base case, suppose that $\deg_{I}(\phi)=1$. If
$\operatorname{rk}(\phi_{|I^{c}})>\operatorname{rk}(\phi)/2m$ we can conclude
by monotonicity, so suppose that
$\operatorname{rk}(\phi_{|I^{c}})\leq\operatorname{rk}(\phi)/2m$. Let
$I=J_{1}\cup\dots\cup J_{m}$ be any partition of $I$ into $m$ parts. We claim
that we can decompose $\phi$ as

$\phi=\phi_{|I^{c}}+\sum_{i=1}^{m}(\phi_{|J_{i}\cup I^{c}}-\phi_{|I^{c}}).$

Indeed, let $x^{\alpha}:=x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$ be a
monomial in the support of $\phi$, for some $\alpha\in\mathbb{Z}_{\geq
0}^{n}$. If $\operatorname{supp}(\alpha)\cap I=\emptyset$, then
$x^{\alpha}=(x^{\alpha})_{|I^{c}}=(x^{\alpha})_{|J_{i}\cup I^{c}}$ for all
$i\in[m]$. Otherwise, since $\deg_{I}(\phi)=1$, we have that
$\operatorname{supp}(\alpha)\cap J_{i}\neq\emptyset$ for exactly one
$i\in[m]$, and so $(x^{\alpha})_{|I^{c}}=0$ and
$x^{\alpha}=(x^{\alpha})_{|J_{i}\cup I^{c}}$ for exactly one $i\in[m]$.

By sub-additivity of $\operatorname{rk}$, and since
$\operatorname{rk}(-\phi)=\operatorname{rk}(\phi)$, it then follows that

$\operatorname{rk}(\phi)\leq(m-1)\operatorname{rk}(\phi_{|I^{c}})+\sum_{i=1}^{m}\operatorname{rk}(\phi_{|J_{i}\cup
I^{c}}).$

Since this holds for every $m$-partition of $I$, it follows from the same
coupling argument as in the proof of Lemma 2.5 that

${\mathbb{E}}_{J\sim I_{1/m}}\operatorname{rk}(\phi_{|J\cup
I^{c}})\geq\frac{\operatorname{rk}(\phi)-(m-1)\operatorname{rk}(\phi_{|I^{c}})}{m}\geq\frac{\operatorname{rk}(\phi)}{2m}.$

By monotonicity of rank under restrictions we conclude that

${\mathbb{E}}_{J\sim I_{\sigma}}\operatorname{rk}(\phi_{|J\cup
I^{c}})\geq{\mathbb{E}}_{J\sim I_{1/m}}\operatorname{rk}(\phi_{|J\cup
I^{c}})\geq\frac{\operatorname{rk}(\phi)}{2m},$

so in this case the lemma holds with $c(\sigma,1)=1/2m$.

Suppose now that $\ell\geq 2$ and we have already proven the lemma up to
degree $\ell-1$. Suppose $\deg_{I}(\phi)=\ell$ and recursively define
$\alpha_{0}=1$,

$\displaystyle\alpha_{r}=1+$
$\displaystyle\frac{1}{c(\sigma,\ell-1)^{2}}\sum_{j=0}^{r-1}\binom{r}{j}\alpha_{j}\quad\text{for
$1\leq r\leq\ell$, and}$
$\displaystyle\gamma=\bigg{(}\sum_{j=0}^{\ell}\binom{m}{j}\alpha_{j}\bigg{)}^{-1}.$

Note that $\gamma>0$ depends only on $\sigma$ and $\ell$.

We can assume that
$\operatorname{rk}(\phi_{|I^{c}})<\gamma\operatorname{rk}(\phi)$, as otherwise
we immediately conclude by monotonicity. If every $m$-partition
$I=A_{1}\cup\dots\cup A_{m}$ contains some part $A_{i}$ satisfying
$\operatorname{rk}(\phi_{|A_{i}\cup
I^{c}})\geq\gamma\alpha_{1}\operatorname{rk}(\phi)$, then the same coupling
argument as in the proof of Lemma 2.5 allows us to conclude (taking
$c(\sigma,\ell)=\gamma\alpha_{1}/m$, say). We may then assume there is some
(fixed) partition $I=A_{1}\cup\dots\cup A_{m}$ with

$\operatorname{rk}(\phi_{|A_{i}\cup
I^{c}})<\gamma\alpha_{1}\operatorname{rk}(\phi)\quad\text{for
all~{}$i\in[m]$.}$

Given a set $S\subseteq[m]$ define $A_{S}=\bigcup_{i\in S}A_{i}$. For a
polynomial map $\phi$, denote by $\phi[S]$ the polynomial map that remains by
keeping in $\phi$ only those monomials with variables in $A_{S}\cup I^{c}$ and
which have at least one variable in each $A_{i}$, $i\in S$. For instance,
$\phi[\emptyset]=\phi_{|I^{c}}$ and $\phi[\\{i\\}]=\phi_{|A_{i}\cup
I^{c}}-\phi_{|I^{c}}$ for each $i\in[m]$. Note that the set of monomials in
$\phi[R]$ is disjoint from the set of monomials in $\phi[S]$ if $R\neq S$;
moreover, every monomial of $\phi$ appears in some $\phi[S]$ with
$|S|\leq\ell$ (since $\deg_{I}(\phi)=\ell$ by assumption). It follows that

(4) $\phi=\sum_{S\subseteq[m]:\,|S|\leq\ell}\phi[S],$

and more generally

(5) $\phi_{|A_{S}\cup I^{c}}=\sum_{R\subseteq
S:\,|R|\leq\ell}\phi[R]\quad\text{for all~{}$S\subseteq[m]$.}$

From identity (4) we conclude there exists some $S\subseteq[m]$ with
$|S|\leq\ell$ for which
$\operatorname{rk}(\phi[S])\geq\gamma\alpha_{|S|}\operatorname{rk}(\phi)$, as
otherwise we would have

$\displaystyle\operatorname{rk}(\phi)$
$\displaystyle\leq\sum_{S\subseteq[m]:\,|S|\leq\ell}\operatorname{rk}(\phi[S])$
$\displaystyle<\sum_{S\subseteq[m]:\,|S|\leq\ell}\gamma\alpha_{|S|}\operatorname{rk}(\phi)$
$\displaystyle=\gamma\sum_{j=0}^{\ell}\binom{m}{j}\alpha_{j}\operatorname{rk}(\phi)$
$\displaystyle=\operatorname{rk}(\phi).$

Take some $S\subseteq[m]$ of minimal size such that
$\operatorname{rk}(\phi[S])\geq\gamma\alpha_{|S|}\operatorname{rk}(\phi)$; by
assumption we have that $2\leq|S|\leq\ell$.

Fix some arbitrary $i\in S$ and denote $S^{\prime}:=S\setminus\\{i\\}$; note
that $S^{\prime}\neq\emptyset$. Denote $\psi:=\phi[S]:\mathbb{F}^{A_{S}\cup
I^{c}}\to\mathbb{F}^{k}$, and note that $\deg_{A_{i}}(\psi)<\ell$ and
$\deg_{A_{S^{\prime}}}(\psi)<\ell$. Apply the induction hypothesis to obtain

${\mathbb{E}}_{J_{i}\sim(A_{i})_{\sigma}}\operatorname{rk}(\psi_{|J_{i}\cup
A_{S^{\prime}}\cup I^{c}})\geq c(\sigma,\ell-1)\operatorname{rk}(\phi[S]).$

For any fixed $J_{i}\subseteq A_{i}$, we can apply the induction hypothesis to
$\psi_{|J_{i}\cup A_{S^{\prime}}\cup I^{c}}$ and obtain

${\mathbb{E}}_{J_{S^{\prime}}\sim(A_{S^{\prime}})_{\sigma}}\operatorname{rk}(\psi_{|J_{i}\cup
J_{S^{\prime}}\cup I^{c}})\geq
c(\sigma,\ell-1)\operatorname{rk}(\psi_{|J_{i}\cup A_{S^{\prime}}\cup
I^{c}}),$

from which we conclude

$\displaystyle{\mathbb{E}}_{J_{S}\sim(A_{S})_{\sigma}}\operatorname{rk}(\psi_{|J_{S}\cup
I^{c}})$
$\displaystyle={\mathbb{E}}_{J_{i}\sim(A_{i})_{\sigma}}{\mathbb{E}}_{J_{S^{\prime}}\sim(A_{S^{\prime}})_{\sigma}}\operatorname{rk}(\psi_{|J_{i}\cup
J_{S^{\prime}}\cup I^{c}})$ $\displaystyle\geq
c(\sigma,\ell-1)^{2}\operatorname{rk}(\phi[S])$
$\displaystyle\geq\gamma\alpha_{|S|}c(\sigma,\ell-1)^{2}\operatorname{rk}(\phi).$

Using identity (5) restricted to the variables in $J_{S}\cup I^{c}$, by sub-
additivity and monotonicity of rank we have

$\displaystyle\operatorname{rk}(\phi_{|J_{S}\cup I^{c}})$
$\displaystyle\geq\operatorname{rk}(\phi[S]_{|J_{S}\cup
I^{c}})-\sum_{R\subsetneq S}\operatorname{rk}(\phi[R]_{|J_{S}\cup I^{c}})$
$\displaystyle\geq\operatorname{rk}(\phi[S]_{|J_{S}\cup
I^{c}})-\sum_{R\subsetneq S}\operatorname{rk}(\phi[R]),$

and so by taking expectation

$\displaystyle{\mathbb{E}}_{J_{S}\sim(A_{S})_{\sigma}}\operatorname{rk}(\phi_{|J_{S}\cup
I^{c}})$
$\displaystyle\geq\gamma\alpha_{|S|}c(\sigma,\ell-1)^{2}\operatorname{rk}(\phi)-\sum_{R\subsetneq
S}\operatorname{rk}(\phi[R])$
$\displaystyle\geq\gamma\bigg{(}\alpha_{|S|}c(\sigma,\ell-1)^{2}-\sum_{j=0}^{|S|-1}\binom{|S|}{j}\alpha_{j}\bigg{)}\operatorname{rk}(\phi)$
$\displaystyle=\gamma c(\sigma,\ell-1)^{2}\operatorname{rk}(\phi).$

Since ${\mathbb{E}}_{J\sim I_{\sigma}}\operatorname{rk}(\phi_{|J\cup
I^{c}})\geq{\mathbb{E}}_{J_{S}\sim(A_{S})_{\sigma}}\operatorname{rk}(\phi_{|J_{S}\cup
I^{c}})$ by monotonicity, the induction step is proven with
$c(\sigma,\ell)=\gamma c(\sigma,\ell-1)^{2}>0$. The lemma follows. $\Box$

###  3.2. Monotone functions on the hypercube and boosting

Our next result is a lemma which allows us to boost the probability of some
events (such as having high rank under random restrictions) from $\varepsilon$
to $1-\varepsilon$ by paying a relatively small price.

It will again be convenient to take a more abstract approach and deal with
Boolean functions rather than restrictions of polynomials. For a Boolean
function $g:\\{0,1\\}^{n}\to\\{0,1\\}$, the total influence of $g$ under
distribution $\pi_{\sigma}^{n}$ is given by

$\mathbf{I}^{(\sigma)}(g)=\sum_{i=1}^{n}{\mathbb{E}}_{x\sim\pi_{\sigma}^{n}}\big{|}g(x)-g(x^{i})\big{|},$

where $x^{i}$ differs from $x$ only in the $i$th coordinate. Denote by
$\mu_{\sigma}[g]:={\mathbb{E}}_{x\sim\pi_{\sigma}^{n}}\big{[}g(x)\big{]}$ its
expectation.

######  Lemma 3.5 (Boosting lemma).

For every $\sigma>0$ there is a constant $C_{\sigma}>0$ such that the
following holds. Let $n\in\mathbb{N}$, $f:\\{0,1\\}^{n}\to\mathbb{R}_{+}$ be a
monotone $1$-Lipschitz function and $\varepsilon\in(0,1/2]$. If $r\geq 1$
satisfies

$\mbox{\rm Pr}_{x\sim\pi_{\sigma}^{n}}\big{[}f(x)\geq r\big{]}>\varepsilon,$

then $\mbox{\rm Pr}_{x\sim\pi_{1.01\sigma}^{n}}\big{[}f(x)\geq
r-C_{\sigma}^{1/\varepsilon^{2}}\big{]}>1-\varepsilon$.

  * Proof:

Consider the Boolean function $g(x):=1\big{[}f(x)\geq r\big{]}$. Note that
there exists $q\in[\sigma,\,1.01\sigma]$ such that $\mathbf{I}^{(q)}(g)\leq
100/\sigma$, as otherwise by the Margulis-Russo formula we would have

$\mu_{1.01\sigma}[g]=\mu_{\sigma}[g]+\int_{\sigma}^{1.01\sigma}\frac{d\mu_{q}[g]}{dq}dq\geq\int_{\sigma}^{1.01\sigma}\mathbf{I}^{(q)}(g)dq>1.$

Let $\gamma\in(0,\varepsilon/2)$ be a constant to be chosen later. By
Friedgut’s junta theorem [13], there is a $C(q)^{100/\gamma\sigma}$-junta
$h:\\{0,1\\}^{n}\to\\{0,1\\}$ such that

$\mbox{\rm Pr}_{x\sim\pi_{q}^{n}}\big{[}g(x)\neq h(x)\big{]}<\gamma;$

let $J\subseteq[n]$, $|J|\leq C(q)^{100/\gamma\sigma}$, be the set of
variables on which $h$ depends. Then

$\displaystyle\mu_{q}[h]\geq\mu_{q}[g]-\gamma\geq\mu_{\sigma}[g]-\gamma>\varepsilon/2,$

which implies $\mbox{\rm
Pr}_{z\sim\pi_{q}^{J}}\big{[}h(z)=1\big{]}>\varepsilon/2$. Since

${\mathbb{E}}_{z\sim\pi_{q}^{J}}\mbox{\rm
Pr}_{y\sim\pi_{q}^{J^{c}}}\big{[}g(y,z)\neq h(z)\big{]}<\gamma,$

it follows that

$\mbox{\rm Pr}_{z\sim\pi_{q}^{J}}\big{[}\mbox{\rm
Pr}_{y\sim\pi_{q}^{J^{c}}}\big{[}g(y,z)\neq
h(z)\big{]}\geq\varepsilon\big{]}<\gamma/\varepsilon.$

Taking $\gamma=\varepsilon^{2}/2$, we conclude there exists
$z\in\\{0,1\\}^{J}$ such that $h(z)=1$ and

$\mbox{\rm Pr}_{y\sim\pi_{q}^{J^{c}}}\big{[}g(y,z)\neq 1\big{]}<\varepsilon.$

Since $f$ is $1$-Lipschitz by assumption, we have

$f(y,z)\geq r\implies f(y,z^{\prime})\geq r-|J|\quad\forall
z^{\prime}\in\\{0,1\\}^{J},$

and thus by monotonicity

$\displaystyle\mbox{\rm Pr}_{x\sim\pi_{1.01\sigma}^{n}}\big{[}f(x)\geq
r-|J|\big{]}$ $\displaystyle\geq\mbox{\rm
Pr}_{x\sim\pi_{q}^{n}}\big{[}f(x)\geq r-|J|\big{]}$
$\displaystyle={\mathbb{E}}_{z^{\prime}\sim\pi_{q}^{J}}\mbox{\rm
Pr}_{y\sim\pi_{q}^{J^{c}}}\big{[}f(y,z^{\prime})\geq r-|J|\big{]}$
$\displaystyle\geq\max_{z\in\\{0,1\\}^{J}}\mbox{\rm
Pr}_{y\sim\pi_{q}^{J^{c}}}\big{[}f(y,z)\geq r\big{]}$
$\displaystyle>1-\varepsilon.$

This is precisely what we wanted to prove, with constant

$C_{\sigma}=\sup_{q\in[\sigma,\,1.01\sigma]}C(q)^{200/\sigma}.$

$\Box$

###  3.3. The Random Restriction Theorem

Our main result, Theorem 1.8, follows easily from the lemmas given above.
Recall that we wish to show that

$\mbox{\rm
Pr}_{J\sim[n]_{\sigma}}\big{[}\operatorname{rk}(\phi_{|J})\geq\kappa(d,\sigma)\cdot\operatorname{rk}(\phi)\big{]}\geq
1-\varepsilon$

whenever $\operatorname{rk}(\phi)\geq R(d,\sigma,\varepsilon)$, for some well-
chosen constants $R(d,\sigma,\varepsilon)$ and $\kappa(d,\sigma)>0$.

  * Proof of Theorem 1.8:

Applying Lemma 3.3 with $\sigma$ substituted by $0.9\sigma$, we obtain

${\mathbb{E}}_{J\sim[n]_{0.9\sigma}}\operatorname{rk}(\phi_{|J})\geq
c(0.9\sigma,d)\operatorname{rk}(\phi).$

Since $\operatorname{rk}(\phi_{|J})\leq\operatorname{rk}(\phi)$ for all
subsets $J\subseteq[n]$, we conclude that

$\mbox{\rm
Pr}_{J\sim[n]_{0.9\sigma}}\bigg{[}\operatorname{rk}(\phi_{|J})\geq\frac{c(0.9\sigma,d)}{2}\operatorname{rk}(\phi)\bigg{]}\geq\frac{c(0.9\sigma,d)}{2}.$

By possibly decreasing $\varepsilon$ a little, we may assume that
$\varepsilon<c(0.9\sigma,d)/2$. Denote

$\kappa(d,\sigma)=\frac{c(0.9\sigma,d)}{4}\quad\text{and}\quad
R(d,\sigma,\varepsilon)=\frac{4C_{0.9\sigma}^{1/\varepsilon^{2}}}{c(0.9\sigma,d)},$

where $C_{0.9\sigma}>0$ is the constant guaranteed by the boosting lemma,
Lemma 3.5. Applying the boosting lemma to the function
$J\mapsto\operatorname{rk}(\phi_{|J})$ with
$r=c(0.9\sigma,d)\operatorname{rk}(\phi)/2$, we get

$\displaystyle\mbox{\rm
Pr}_{J\sim[n]_{0.9\sigma}}\big{[}\operatorname{rk}(\phi_{|J})\geq r\big{]}$
$\displaystyle\geq c(0.9\sigma,d)/2>\varepsilon$
$\displaystyle\implies\mbox{\rm
Pr}_{J\sim[n]_{\sigma}}\big{[}\operatorname{rk}(\phi_{|J})\geq
r-C_{0.9\sigma}^{1/\varepsilon^{2}}\big{]}>1-\varepsilon.$

Since
$c(0.9\sigma,d)\operatorname{rk}(\phi)/2-C_{0.9\sigma}^{1/\varepsilon^{2}}\geq\kappa(\sigma,d)\operatorname{rk}(\phi)$
whenever $\operatorname{rk}(\phi)\geq R(d,\sigma,\varepsilon)$, this concludes
the proof. $\Box$

##  4\. Discussion and open problems

The motivation for this work stems from a problem from theoretical computer
science which concerns decoding corrupted error-correcting codes (ECCs) with
NC${}^{0}[\oplus]$ circuits [5]. An ECC is a map
$E:\mathbb{F}_{2}^{k}\to\mathbb{F}_{2}^{n}$ with the property that the points
in its image (codewords) are well-separated in Hamming distance, enabling
retrieval of encoded messages provided codewords are not too badly corrupted
during transmission or storage. A standard noise model for corruption is the
_symmetric channel_ : for a parameter $\sigma\in[0,1]$ and given an element
$y\in\mathbb{F}_{2}^{n}$, this channel samples a set $I\sim[n]_{\sigma}$ and,
for each $i\in I$, replaces the coordinate $y_{i}$ with a uniformly
distributed element over $\mathbb{F}_{2}$. The problem is to determine whether
NC${}^{0}[\oplus]$ circuits are capable of correctly decoding corrupted
codewords with good probability over this noise distribution.

It turns out that the mappings such circuits can effect are precisely
constant-degree polynomial maps
$\phi:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{k}$. One of the main results in [5]
shows that the fraction of messages such maps can correctly decode with non-
negligible probability (over the symmetric channel noise model) tends to zero
as the size $k$ of the messages grows. The proof of this result uses a
structure-versus-randomness strategy to analyze the decoding capability of
$\phi$ based on the value $\operatorname{arank}_{d}(\phi)$ for $d=\deg(\phi)$
(the proof uses no assumptions on the specific ECC). The key to analyzing the
case when this rank is high – the pseudorandom setting – is to understand how
this rank behaves under random restrictions originating from the symmetric
channel noise; this is what motivated Theorem 1.8. While in this application
the degree of $\phi$ may exceed the field size, a similar result but with
quantitatively stronger bounds can be obtained in the high-characteristic
setting, where $\operatorname{char}(\mathbb{F})>\deg(\phi)$, by using Theorem
1.4.

As already remarked in the Introduction, our proof of Theorem 1.4 for higher-
order tensors proceeds quite differently from the matrix case (Proposition
1.1). The reason for this is that an analogous proof would require the
existence of a high-rank sub-tensor; to explain this more precisely, we
introduce the following definition.

######  Definition 4.1 (Core property).

Let $A,B:\mathbb{R}_{+}\to\mathbb{R}_{+}$ be unbounded increasing functions,
and let $\operatorname{rk}:(\mathbb{F}^{\infty})^{\otimes
d}\to\mathbb{R}_{+}$. We say that $\operatorname{rk}$ satisfies the _$(A,B)$
-core property_ if, for every $d$-tensor $T\in(\mathbb{F}^{\infty})^{\otimes
d}$ of high enough rank $\operatorname{rk}(T)$, there exist sets
$J_{1},\dots,J_{d}\subset\mathbb{N}$ of size at most $A(\operatorname{rk}(T))$
such that $\operatorname{rk}(T_{|J_{[d]}})\geq B(\operatorname{rk}(T))$. We
say that $\operatorname{rk}$ satisfies the _linear core property_ if it
satisfies the $(A,B)$-core property for linear functions $A(r)=Kr$ and
$B(r)=cr$, with $K,c>0$.

Draisma [10] proved that slice rank has a core-like property, up to local
linear transformation and provided $\mathbb{F}$ is infinite. In particular his
result shows that, for every $d,r\in\mathbb{N}$ and every $d$-tensor
$T\in\bigotimes_{i=1}^{d}\mathbb{F}^{X_{i}}$ of slice rank at least $r$, there
are linear maps $\varphi_{i}:\mathbb{F}^{X_{i}}\to\mathbb{F}^{n}$ such that
the tensor $(\varphi_{1}\otimes\cdots\otimes\varphi_{d})T$ also has slice rank
at least $r$, where $n=n(d,r)$ is a constant depending only on $d$ and $r$.

More in line with Definition 4.1, Karam [20] recently proved that several rank
functions for tensors defined in terms of decompositions, including the slice
rank, partition rank and tensor rank, satisfy the $(A,B)$-core property for
some functions $A$ and $B$. For partition rank over finite fields, for
instance, he obtains explicit functions $A(r)=\exp(O_{d,\mathbb{F}}(r))$ and
$B(r)=\Omega_{d}(r/(\log r)^{d})$; for the slice rank of 3-tensors he shows
that one can take $A(r)=O(r)$ and $B(r)=\Omega(r^{1/3})$; and for tensor rank,
he shows the “perfect” linear core property $A(r)=B(r)=r$. Karam conjectures,
moreover, that all these rank functions in fact satisfy the linear core
property [20, Conjecture 13.1]. In this case, a similar argument to the one we
used for matrices in the introduction allows us to easily deduce a Random
Restriction Theorem:

######  Theorem 4.2.

Suppose $\operatorname{rk}:(\mathbb{F}^{\infty})^{\otimes d}\to\mathbb{R}_{+}$
satisfies the linear core property, monotonicity under restrictions and the
restriction Lipschitz property. Then for every $\sigma\in(0,1]$ there exist
constants $C,\kappa>0$ such that, for every $d$-tensor
$T\in\bigotimes_{i=1}^{d}\mathbb{F}^{n_{i}}$, we have

$\mbox{\rm
Pr}_{I_{1}\sim[n_{1}]_{\sigma},\dots,I_{d}\sim[n_{d}]_{\sigma}}\big{[}\operatorname{rk}\big{(}T_{|I_{[d]}}\big{)}\geq\kappa\cdot\operatorname{rk}(T)\big{]}\geq
1-Ce^{-\kappa\operatorname{rk}(T)}.$

  * Proof:

Let $K,c>0$ be the constants in the linear core property of
$\operatorname{rk}$, and denote $\lambda=c/(3dK)$. For a given $d$-tensor
$T\in\bigotimes_{i=1}^{d}\mathbb{F}^{n_{i}}$, fix sets
$J_{1}\subseteq[n_{1}],\dots,J_{d}\subseteq[n_{d}]$ of size
$K\operatorname{rk}(T)$ such that $\operatorname{rk}(T_{|J_{[d]}})\geq
c\operatorname{rk}(T)$.

Let $I_{1}\sim(J_{1})_{1-\lambda},\dots,I_{d}\sim(J_{d})_{1-\lambda}$ be
random sets and consider the random event

$E=\big{\\{}|I_{i}|\geq(1-2\lambda)|J_{i}|\,\text{ for all }1\leq i\leq
d\big{\\}}.$

Whenever $E$ holds, by the restriction Lipschitz property we have

$\displaystyle\operatorname{rk}(T_{|I_{[d]}})$
$\displaystyle\geq\operatorname{rk}(T_{|J_{[d]}})-\sum_{i=1}^{d}|J_{i}\setminus
I_{i}|$ $\displaystyle\geq c\operatorname{rk}(T)-d\cdot 2\lambda
K\operatorname{rk}(T)$ $\displaystyle=c\operatorname{rk}(T)/3.$

By the Chernoff bound and union bound, the probability of $E$ is at least
$1-d\,e^{-(c/12d)\operatorname{rk}(T)}$; it then follows from monotonicity
that

$\mbox{\rm
Pr}_{I_{1}\sim[n_{1}]_{1-\lambda},\dots,I_{d}\sim[n_{d}]_{1-\lambda}}\bigg{[}\operatorname{rk}(T_{|I_{[d]}})\geq\frac{c}{3}\operatorname{rk}(T)\bigg{]}\geq
1-d\,e^{-\frac{c}{12d}\operatorname{rk}(T)}.$

Now we apply the same argument to the (random) tensor
$\tilde{T}=T_{|I_{[d]}}$, and union-bound with the event
$\big{\\{}\operatorname{rk}(T_{|I_{[d]}})\geq
c\operatorname{rk}(T)/3\big{\\}}$. Since $(I_{i})_{1-\lambda}$ is distributed
as $[n_{i}]_{(1-\lambda)^{2}}$ when $I_{i}\sim[n_{i}]_{1-\lambda}$, we
conclude that

$\mbox{\rm
Pr}_{I_{1}\sim[n_{1}]_{(1-\lambda)^{2}},\dots,I_{d}\sim[n_{d}]_{(1-\lambda)^{2}}}\bigg{[}\operatorname{rk}(T_{|I_{[d]}})\geq\Big{(}\frac{c}{3}\Big{)}^{2}\operatorname{rk}(T)\bigg{]}\geq
1-2d\,e^{-\frac{c}{12d}\frac{c}{3}\operatorname{rk}(T)}.$

In general, applying this same argument recursively $t$ times in total, we get

$\mbox{\rm
Pr}_{I_{1}\sim[n_{1}]_{(1-\lambda)^{t}},\dots,I_{d}\sim[n_{d}]_{(1-\lambda)^{t}}}\Big{[}\operatorname{rk}(T_{|I_{[d]}})\geq\Big{(}\frac{c}{3}\Big{)}^{t}\operatorname{rk}(T)\Big{]}\geq
1-td\,e^{-\frac{c}{12d}(\frac{c}{3})^{t-1}\operatorname{rk}(T)}.$

The theorem now follows by taking $t$ to be the smallest integer for which
$(1-\lambda)^{t}\leq\sigma$, and using monotonicity under restrictions. $\Box$

We quickly remark on another interesting connection between our results and
recent work on high-rank maps by Gowers and Karam [14]. These authors studied
equidistribution properties of polynomials and multilinear forms on
$\mathbb{F}_{p}^{n}$ when the variables are restricted to subsets of their
domain; this setting is quite similar to what motivated our studies, as
explained in the beginning of this section. A crucial step in their arguments
was a result (Proposition 3.5 in [14]) showing that the values taken by
multilinear forms of high partition rank must be close to uniformly
distributed under a wide range of non-uniform input distributions. Under the
well-known conjecture (within additive combinatorics) that the partition rank
and analytic rank of tensors are equivalent up to a multiplicative constant,
their result would straightforwardly imply the conclusion of our Random
Restriction Theorem (Theorem 1.4) when restricted to either the partition rank
or the analytic rank of tensors, although making use of very different
arguments.

Analogous to Definition 4.1, it also makes sense to define a core property for
polynomial maps (which include single polynomials by setting $k=1$).

######  Definition 4.3.

Let $A,B:\mathbb{R}_{+}\to\mathbb{R}_{+}$ be unbounded increasing functions,
and let $\operatorname{rk}:\operatorname{Pol}_{\leq
d}(\mathbb{F}^{n};\mathbb{F}^{k})\to\mathbb{R}_{+}$. We say that
$\operatorname{rk}$ satisfies the _$(A,B)$ -core property_ if, for every
polynomial map $\phi\in\operatorname{Pol}_{\leq
d}(\mathbb{F}^{n};\mathbb{F}^{k})$ of high enough rank
$\operatorname{rk}(\phi)$, there exists a sets $I\subseteq[n]$ of size at most
$A(\operatorname{rk}(\phi))$ such that $\operatorname{rk}(\phi_{|I})\geq
B(\operatorname{rk}(\phi))$. We say that $\operatorname{rk}$ satisfies the
_linear core property_ if it satisfies the $(A,B)$-core property for linear
functions $A(r)=Kr$ and $B(r)=cr$, with $K,c>0$.

A property comparable to a core property for polynomial maps was proved by
Kazhdan and Ziegler [22]. For simplicity, we state it here only for
polynomials. They showed that a polynomial $P\in\mathbb{F}[x_{1},\dots,x_{n}]$
with high Schmidt rank and $\deg(P)<\operatorname{char}(\mathbb{F})$ is
universal in the following sense: If $\operatorname{prank}(P)\geq r$, then for
any $Q\in\mathbb{F}[x_{1},\dots,x_{m}]$ of degree $\deg(P)$ there is an affine
map $\phi:\mathbb{F}^{m}\to\mathbb{F}^{n}$ such that $Q=P\circ\phi$, provided
$r$ is large enough in terms of $m$. Taking $Q$ to be a polynomial of maximal
Schmidt rank $m$ shows that, up to an affine transformation, $P$ restricts to
an $m$-variate polynomial of maximal Schmidt rank.

It would be of interest to know which notions of rank for polynomial maps have
a core property, and especially if any of the rank functions discussed here
have the linear core property (see [3] for recent progress on this). The same
proof as given for Theorem 4.2 shows that a linear core property implies a
Random Restriction Theorem for polynomial maps that is quantitatively stronger
than Theorem 1.8. Finally, it would also be interesting to know if there
exists an example analogous to that of Gowers for slice rank mentioned in
Section 1, that would rule out the possibility of a perfect linear core
property (i.e. with $A(r)=B(r)=r$, for functions $A$ and $B$ as in Definition
4.3).

## Acknowledgements

The authors would like to thank Victor Souza for bringing Karam’s paper [20]
to their attention, and Jan Draisma and Tamar Ziegler for a number of helpful
pointers to the literature. We also thank Thomas Karam for helpful comments on
a preliminary version of this manuscript.

## References

  * [1] Tigran Ananyan and Melvin Hochster, _Small subalgebras of polynomial rings and Stillman’s conjecture_ , J. Amer. Math. Soc. 33 (2020), 291–309.
  * [2] Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans, _On cap sets and the group-theoretic approach to matrix multiplication_ , Discrete Anal. (2017), Paper No. 3, 27.
  * [3] Andreas Blatter, Jan Draisma, and Filip Rupniewski, _A tensor restriction theorem over finite fields_ , 2022, arXiv:2211.12319.
  * [4] Jop Briët, _Subspaces of tensors with high analytic rank_ , Online J. Anal. Comb. (2021), no. 16, Paper No. 6, 9.
  * [5] Jop Briët, Harry Buhrman, Davi Castro-Silva, and Niels M.P. Neumann, _Noisy decoding by shallow circuits with parities: classical and quantum_ , 2022, to appear.
  * [6] Alex Cohen and Guy Moshkovitz, _Partition and analytic rank are equivalent over large fields_ , 2021, arXiv:2102.10509.
  * [7] by same author, _Structure vs. randomness for bilinear maps_ , STOC ’21—Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2021, pp. 800–808.
  * [8] Ernie Croot, Vsevolod F. Lev, and Péter Pál Pach, _Progression-free sets in $\mathbb{Z}^{n}_{4}$ are exponentially small_, Ann. of Math. (2) 185 (2017), no. 1, 331–337.
  * [9] Harm Derksen, Rob H. Eggermont, and Andrew Snowden, _Topological noetherianity for cubic polynomials_ , Algebra Number Theory 11 (2017), no. 9, 2197–2212.
  * [10] Jan Draisma, _Topological Noetherianity of polynomial functors_ , J. Amer. Math. Soc. 32 (2019), no. 3, 691–707.
  * [11] Jordan S. Ellenberg and Dion Gijswijt, _On large subsets of $\mathbb{F}^{n}_{q}$ with no three-term arithmetic progression_, Ann. of Math. (2) 185 (2017), no. 1, 339–343.
  * [12] Jacob Fox and László Miklós Lovász, _A tight bound for Green’s arithmetic triangle removal lemma in vector spaces_ , Adv. Math. 321 (2017), 287–297.
  * [13] Ehud Friedgut, _Boolean functions with low average sensitivity depend on few coordinates_ , Combinatorica 18 (1998), no. 1, 27–35.
  * [14] W. T. Gowers and Thomas Karam, _Equidistribution of high-rank polynomials with variables restricted to subsets of $\mathbb{F}_{p}$_, 2022, arXiv:2209.04932.
  * [15] W. T. Gowers and J. Wolf, _Linear forms and higher-degree uniformity for functions on $\mathbb{F}^{n}_{p}$_, Geom. Funct. Anal. 21 (2011), no. 1, 36–69.
  * [16] Ben Green and Terence Tao, _The distribution of polynomials over finite fields, with applications to the Gowers norms_ , Contrib. Discrete Math. 4 (2009), no. 2, 1–36.
  * [17] Torben Hagerup and Christine Rüb, _A guided tour of Chernoff bounds_ , Information Processing Letters 33 (1990), no. 6, 305–308.
  * [18] Elad Haramaty and Amir Shpilka, _On the structure of cubic and quartic polynomials_ , STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, 2010, pp. 331–340.
  * [19] Pooya Hatami, _On the structure of quintic polynomials_ , Approximation, randomization, and combinatorial optimization. Algorithms and techniques, LIPIcs. Leibniz Int. Proc. Inform., vol. 60, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, pp. Art. No. 33, 18.
  * [20] Thomas Karam, _High-rank subtensors of high-rank tensors_ , 2022, arXiv:2207.08030.
  * [21] David Kazhdan and Tamar Ziegler, _Approximate cohomology_ , Selecta Math. (N.S.) 24 (2018), no. 1, 499–509.
  * [22] by same author, _Properties of high rank subvarieties of affine spaces_ , Geom. Funct. Anal. 30 (2020), no. 4, 1063–1096.
  * [23] Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam, _Geometric rank of tensors and subrank of matrix multiplication_ , 35th Computational Complexity Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 169, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020, pp. Art. No. 35, 21.
  * [24] J. M. Landsberg, _Geometry and the complexity of matrix multiplication_ , Bull. Amer. Math. Soc. (N.S.) 45 (2008), no. 2, 247–284.
  * [25] Shachar Lovett, _The analytic rank of tensors and its applications_ , Discrete Anal. (2019), Paper No. 7, 10.
  * [26] Eric Naslund, _Exponential bounds for the Erdős-Ginzburg-Ziv constant_ , J. Combin. Theory Ser. A 174 (2020), 105185, 19.
  * [27] by same author, _The partition rank of a tensor and $k$-right corners in $\mathbb{F}_{q}^{n}$_, J. Combin. Theory Ser. A 174 (2020), 105190, 25.
  * [28] Eric Naslund and Will Sawin, _Upper bounds for sunflower-free sets_ , Forum Math. Sigma 5 (2017), Paper No. e15, 10.
  * [29] Ran Raz, _Tensor-rank and lower bounds for arithmetic formulas_ , J. ACM 60 (2013), no. 6, Art. 40, 15.
  * [30] Gideon Schechtman, _Concentration results and applications_ , Handbook of the geometry of Banach spaces, Vol. 2, North-Holland, Amsterdam, 2003, pp. 1603–1634.
  * [31] Wolfgang M. Schmidt, _The density of integer points on homogeneous varieties_ , Acta Math. 154 (1985), no. 3-4, 243–296.
  * [32] Michel Talagrand, _Concentration of measure and isoperimetric inequalities in product spaces_ , Inst. Hautes Études Sci. Publ. Math. (1995), no. 81, 73–205.
  * [33] Terence Tao, https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/, 2016\.
  * [34] Terence Tao and Will Sawin, https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors/, 2016\.
  * [35] Terence Tao and Tamar Ziegler, _The inverse conjecture for the Gowers norm over finite fields in low characteristic_ , Ann. Comb. 16 (2012), no. 1, 121–188.


# Noncommutative Quantum Cosmology for the FLRW model in Unimodular Gravity

J. A. Astorga-Moreno1<EMAIL_ADDRESS>Miguel A. García-Aspeitia2
<EMAIL_ADDRESS>E. A. Mena-Barboza3<EMAIL_ADDRESS>1Departamento de Física, Centro de Investigación y Estudios Avanzados del IPN,
Apartado Postal 14-740, 07000, CDMX, México.  2Depto. de Física y Matemáticas,
Universidad Iberoamericana Ciudad de México, Prolongación Paseo
de la Reforma 880, México D. F. 01219, México  3Centro Universitario de la
Ciénega, Universidad de Guadalajara
Ave. Universidad 1115, Ed. de Investigación y Tutorías, C.P. 47820 Ocotlán,
Jalisco, México.

###### Abstract

It is well known that classical Unimodular Gravity (UG) is equivalent to
General Relativity, but is not clear the equivalence at the quantum level.
Here we exhibit, in the UG framework, the Quantum Cosmology (QC) for a
Friedmann-Lemaitre-Robertson-Walker (FLRW) universe, considering an
inflationary scenario and also introducing a deformation on the commutation
relations for the minisuperspace variables (NCC).

Unimodular Gravity, Quantum Cosmology, Inflation.

###### pacs:

04.20.Fy, 04.50.-h, 98.80.Qc.

##  I Introduction

The Universe acceleration is one of the most profound mysteries of the
Universe evolution, being observed first by Supernovaes 1  and confirmed by
the acoustic peaks of Cosmic Microwave Background Radiation (CMB) 2 . The
straightforward explanation of the Universe acceleration can be through the
presence of an effective cosmological constant (CC), whose role fit
extraordinarily well with diverse cosmological observations 3 . However,
despite its benefits, the CC is afflicted with several problems. Among the
most vicious, is the problem when we try to quantify the quantum vacuum
oscillations, to explain the number obtained by observations 4 ; 5 . The
theoretical prediction is 120 orders of magnitude of difference with respect
to the value given by the observations. Another problem that afflicts the CC
is the coincidence problem due that the domination epoch of CC is around
$z\sim 0.7$, i.e. in late time of the Universe evolution. These are some
reason of why the community dedicates time to explore other paths to tackle
the problem. The most studied are for example the dynamical dark energy (DDE),
like the Chaplygin gases 6 , the emergent DE that comes from the presence of
scalar fields 7 . Other alternatives to affront the problem of Universe
acceleration are, for example, brane theories 8 ; 9 ; 10 , $f(R)$ models 11 ,
unimodular gravity (UG) 12 ; 13 , which implies modifications to General
Relativity (GR) in order to obtain a natural late acceleration without the
addition of an exotic fluid (see 14  for a compilation of models).

On the other hand, one of the best candidates to tackle the cosmic
acceleration, is the previously mentioned UG 15 , whose main characteristic is
that scalar density is considered a constant in contrast with GR. The
imposition of this, generates a gravitational field equation with the
characteristic that it is trace-free and the energy momentum tensor is not
conserved at least if this is imposed as an extra hypothesis. If we add the
energy-momentum conservation, the traditional Einstein field equations are
recovered with the apparition of a CC with non gravitating characteristics due
that it is an integration constant, having the capability to add the expected
value, obtained from observations 12 ; 13 .

Recently, at the quantum level, the UG is also studied in order to generate a
coherent quantum theory of gravity. We know that classically the UG theory is
equivalent to GR when it is imposed the condition $\nabla^{\nu}T_{\mu\nu}=0$,
however differs when it comes to quantum theory 16 . Is in this vein that we
study the quantum cosmology scenario through the canonical quantization. We
start this performance using the FLRW metric with a scalar field with an
exponential potential, it is derived and exhibit relations in a UG framework
through the Wheeler-DeWitt (WDW) and the Einstein-Hamilton-Jacobi (EHJ)
equations. The results are presented via a semiclassical limit, in order to
see the evolution through the temporal variable. This task is reached through
the introduction of noncommutativity between minisuperspace coordinates.

The paper outline is as follows: In Sec. II, we present the mathematical
formalism of unimodular gravity and the WDW equation. In Sec. III it is
deduced the semiclassical approximation for the WDW equation in UG context.
Finally, Sec. IV is dedicated to conclusions and discussions. From here, we
will use natural units in which $c=\hbar=k_{B}=1$.

##  II WDW equation in Unimodular gravity

Unimodular gravity can be followed from the action

$S=\int dx^{4}\sqrt{-g}\left(\frac{1}{2\kappa}R-\mathcal{L}_{matt}\right),$
(1)

where $\kappa\equiv 8\pi G$, $\mathcal{L}_{matt}$, corresponds to the matter
Lagrangian and $R$ is the usual Ricci scalar111For a discussion of the
equivalence between metrics in unimodular coordinates and other systems for a
FRLW Universe, see 20 ; 21 .. In Unimodular gravity context, the scalar
density is usually constrained in the form $\sqrt{-g}=\epsilon_{0}$, hence,
the action can be manipulated in order to found the following field equations

$R_{\mu\nu}-\frac{1}{4}g_{\mu\nu}R=8\pi
G\left(T_{\mu\nu}-\frac{1}{4}g_{\mu\nu}T\right),$ (2)

where the energy momentum tensor is defined as usual, this happens because the
combination of $T_{\mu\nu}-g_{\mu\nu}T/4$ is independent of what energy-
momentum tensor we are using17 .
Now, the line element for a homogeneous an isotropic universe is

$ds^{2}=-N^{2}(t)dt^{2}+a^{2}(t)\Big{[}\frac{dr^{2}}{1-kr^{2}}+r^{2}(d\theta^{2}+\sin^{2}\theta
d\varphi^{2})\Big{]},$ (3)

where $a$ is the scale factor, $N$ the lapse function and $k$ the curvature
constant that takes the values $0,1,-1$ that correspond to a flat, open and
closed universe, respectively. In references 18 ; 19  appears a relevant
analysis for the flat case in the early Universe, considering

$S=S_{g}+S_{\phi}=\int
dx^{4}\sqrt{-g}\Big{[}R-2\Lambda-\frac{(\dot{\phi})^{2}}{2N^{2}}-V(\phi)\Big{]},$
(4)

taking in mind that $\phi$ is a scalar field endowed with a scalar potential
$V$, $\Lambda$ is the cosmological constant. Now, the metric determinant is
restricted to satisfy the unimodular condition $\sqrt{-g}=\epsilon_{0}$, where
$\epsilon_{0}$ is a fixed scalar density, then the unimodular action $S_{UN}$
can be written as

$\displaystyle
S_{UN}=\int^{t_{1}}_{t_{0}}dt\frac{\epsilon_{0}}{N}\Big{[}-\frac{12(\dot{a})^{2}}{a^{2}N}-\frac{6\dot{a}\dot{N}}{aN^{2}}-\frac{(\dot{\phi})^{2}}{2N}-$
$\displaystyle N(V+2\Lambda+6ka^{-2})\Big{]},$ (5)

making the ansatz $\dot{a}/a=\dot{\alpha}$ the Lagrangian becomes

$\displaystyle\mathcal{L}=\frac{\epsilon_{0}}{N^{2}}\Bigg{[}-\dot{\alpha}\Big{(}12\dot{\alpha}+\frac{6\dot{N}}{N}\Big{)}-\frac{(\dot{\phi})^{2}}{2}-N^{2}\Big{(}V(\phi)+$
$\displaystyle 2\Lambda+6ke^{-2\alpha}\Big{)}\Bigg{]},$ (6)

obtaining the canonical momenta and fixing $N=e^{-3\alpha}$, we are in a
position to write the corresponding Hamiltonian

$\mathcal{H}=\frac{e^{-6\alpha}}{\epsilon_{0}}\Bigg{[}\frac{\Pi^{2}_{\alpha}}{24}-\frac{\Pi^{2}_{\phi}}{2}+\epsilon_{0}e^{6\alpha}\Big{(}V(\phi)+2\Lambda+6ke^{-2\alpha}\Big{)}\Bigg{]}.$
(7)

Replacing $\Pi_{q^{\mu}}=-i\partial_{q^{\mu}}$, here $q^{\mu}=(\alpha,\phi)$,
and $\mathcal{H}=0$ implies the WDW equation in the unimodular framework
(UGWDW)

$\Box\psi+\epsilon_{0}e^{6\alpha}\Big{(}V(\phi)+2\Lambda+6ke^{-2\alpha}\Big{)}\psi=0,$
(8)

where

$\Box\equiv-\frac{1}{24}\partial^{2}_{\alpha}+\frac{1}{2}\partial^{2}_{\phi},$
(9)

is the two dimensional modified D’Alambertian. Applying the following
transformation between coordinates

$u=-6\alpha+\lambda\phi,\quad v=2\alpha,$ (10)

if $\lambda$ is a parameter, then using $V=V_{0}e^{-\lambda\phi}$, we
get222This potential represents a chaotic inflation model. in (8)

$\displaystyle\partial^{2}_{u}\psi-\frac{1}{3(\lambda^{2}-3)}\partial^{2}_{v}\psi+$
$\displaystyle\frac{2\epsilon_{0}V_{0}e^{-u}}{\lambda^{2}-3}\psi+\frac{2\epsilon_{0}}{\lambda^{2}-3}\Big{(}2\Lambda
e^{3v}+6ke^{2v}\Big{)}\psi=0.$ (11)

Considering $\psi=X(u)Y(v)$, we have the following two equations

$\displaystyle\frac{d^{2}X}{du^{2}}+(\beta e^{-u}-\eta^{2})X=0,$ (12a)
$\displaystyle\frac{d^{2}Y}{dv^{2}}-\Big{(}12\epsilon_{0}\Lambda
e^{3v}+36k\epsilon_{0}e^{2v}+3(\lambda^{2}-3)\eta^{2}\Big{)}Y$
$\displaystyle=0,$ (12b)

with $\eta^{2}$ the separation constant and
$\beta=\frac{2\epsilon_{0}V_{0}}{\lambda^{2}-3}$. The equation (12a) can be
treated as a Bessel one, resulting

$X=\left\\{\begin{array}[]{ll}c_{0}J_{2\eta}\Big{(}2\sqrt{\beta}e^{-\frac{u}{2}}\Big{)}+c_{1}Y_{2\eta}\Big{(}2\sqrt{\beta}e^{-\frac{u}{2}}\Big{)},\quad\lambda>\sqrt{3}\\\
\\\
c_{0}J_{2\eta}\Big{(}2i\sqrt{\beta}e^{-\frac{u}{2}}\Big{)}+c_{1}Y_{2\eta}\Big{(}2i\sqrt{\beta}e^{-\frac{u}{2}}\Big{)},\quad\lambda<\sqrt{3}.\end{array}\right.$
(13)

In the flat case (12b) can be transformed as a modified Bessel equation then,
taking $\kappa=\frac{2\sqrt{(\lambda^{2}-3)}\eta}{\sqrt{3}}$, we have

$Y=\left\\{\begin{array}[]{ll}c_{0}I_{\kappa}\Big{(}\frac{4\sqrt{\epsilon_{0}\Lambda}}{\sqrt{3}}e^{\frac{3v}{2}}\Big{)}+c_{1}K_{\kappa}\Big{(}\frac{4\sqrt{\epsilon_{0}\Lambda}}{\sqrt{3}}e^{\frac{3v}{2}}\Big{)},\quad\lambda>\sqrt{3}\\\
\\\
c_{0}I_{i\kappa}\Big{(}\frac{4\sqrt{\epsilon_{0}\Lambda}}{\sqrt{3}}e^{\frac{3v}{2}}\Big{)}+c_{1}K_{i\kappa}\Big{(}\frac{4\sqrt{\epsilon_{0}\Lambda}}{\sqrt{3}}e^{\frac{3v}{2}}\Big{)},\quad\lambda<\sqrt{3}.\end{array}\right.$
(14)

The product $XY=\psi_{\eta}$ forms a family of solutions because have a
dependence on the parameter $\eta$, thus the general solution, using a
weighting function $F(\eta)$, can be put as

$\psi=\int{F(\eta)\psi_{\eta}d\eta}.$ (15)

Now we propose a deformation in the variables that obey kind of commutation
relation as in noncommutative quantum mechanicsgamboa , in our work, this
noncommutativity can be applied to a quantum cosmological model, where
$q_{nc}^{\mu}=q^{\mu}\pm\frac{\theta\Pi_{q^{\mu}}}{2}$ the noncommutative in
coordinates unimodular gravity Wheeler-DeWitt equation (NCC-UGWDW), the theta
parameter is an uncertainty between the variables, analogous to the Heisenberg
uncertainty principle but on the spatial or mini-superspace variables

$\Box\psi_{nc}+\epsilon_{0}e^{6\alpha_{nc}}\Big{(}V(\phi_{nc})+2\Lambda+6ke^{-2\alpha_{nc}}\Big{)}\psi_{nc}=0,$
(16)

where we have proposed a particular ansatz in the configuration coordiantes

$\alpha_{nc}=\alpha+\frac{\Pi_{\phi}\theta}{2},\qquad\phi_{nc}=\phi-\frac{\Pi_{\alpha}\theta}{2},$
(17)

which satisfy the deformed algebra

$\\{\phi_{nc},\alpha_{nc}\\}=\theta,\qquad\\{\alpha_{nc},\Pi_{\alpha}\\}=\\{\phi_{nc},\Pi_{\phi}\\}=1,$
$\\{\Pi_{\phi},\Pi_{\alpha}\\}=0,$ (18)

we choose the momenta in both spaces are the same
$\Pi^{nc}_{\alpha}=\Pi_{\alpha}$ and via the above transformations we have in
(16)

$\displaystyle\Box\psi_{nc}+\epsilon_{0}(V_{0}e^{6\alpha-\lambda\phi}e^{-i\theta(3\partial_{\phi}+\lambda\partial_{\alpha})}+$
$\displaystyle 2\Lambda
e^{6\alpha}e^{-3i\theta\partial_{\phi}}+6ke^{4\alpha}e^{-2i\theta\partial_{\phi}})\psi_{nc}=0.$
(19)

and using the properties

$\displaystyle e^{\eta(A+B)}$ $\displaystyle=e^{-\eta^{2}[A,B]}e^{\eta
A}e^{\eta B},$ $\displaystyle e^{i\theta\partial_{x}}e^{\eta x}$
$\displaystyle=e^{i\eta\theta}e^{\eta x},$ (20)

together with (10) and the anzats $\psi_{nc}=e^{\pm ip_{1}u}Y_{nc}(v)$, gives

$\displaystyle\frac{d^{2}Y_{nc}}{dv^{2}}-\Big{(}12\epsilon_{0}\Lambda
e^{3v}e^{\pm 3p_{1}\lambda\theta}+36k\epsilon_{0}e^{2v}e^{\pm
2p_{1}\lambda\theta}+$ $\displaystyle
3(\lambda^{2}-3)p_{1}^{2}\Big{)}Y_{nc}=0.$ (21)

then when $k=0$ and making
$w=\frac{4\sqrt{\epsilon_{0}\Lambda}e^{\frac{3v}{2}}e^{\frac{\pm
3ip_{1}\lambda\theta}{2}}}{\sqrt{3}}$ results a modified Bessel equation with
$\kappa=\frac{2\sqrt{\lambda^{2}-3}p_{1}}{\sqrt{3}}$, getting for $Y_{nc}$
when $\lambda>\sqrt{3}$ and $\lambda<\sqrt{3}$, respectively

$\left\\{\begin{array}[]{ll}c_{0}I_{\kappa}\Big{(}\frac{4\sqrt{\epsilon_{0}\Lambda}e^{\frac{-3\bar{v}}{2}}e^{\frac{\pm
3p_{1}\lambda\theta}{2}}}{\sqrt{3}}\Big{)}+c_{1}K_{\kappa}\Big{(}\frac{4\sqrt{\epsilon_{0}\Lambda}e^{\frac{-3\bar{v}}{2}}e^{\frac{\pm
3p_{1}\lambda\theta}{2}}}{\sqrt{3}}\Big{)},\\\ \\\
c_{0}I_{i\kappa}\Big{(}\frac{4\sqrt{\epsilon_{0}\Lambda}e^{\frac{-3\bar{v}}{2}}e^{\frac{\pm
3p_{1}\lambda\theta}{2}}}{\sqrt{3}}\Big{)}+c_{1}K_{i\kappa}\Big{(}\frac{4\sqrt{\epsilon_{0}\Lambda}e^{\frac{-3\bar{v}}{2}}e^{\frac{\pm
3p_{1}\lambda\theta}{2}}}{\sqrt{3}}\Big{)}.\end{array}\right.$ (22)

under the diffeomorphism $v\leftrightarrow-\bar{v}$ and also recovering (14)
when $\theta\to 0$. Proceeding similarly, the commutative and NCC cases when
$\Lambda=0$, $k\neq 0$ and $\Lambda=0$, $k=0$ also can be studied.

Now, looking for the effects of noncommutativity, let us consider the
following wave packet weighted by a Gaussian

$\psi=\int^{\infty}_{-\infty}e^{-a(p_{1}-b)}\psi_{nc}dp_{1}$ (23)

given the dependence of $\psi_{nc}$ on the parameter $p_{1}$. Since the
scenario where the influence of the parameter $\theta$ could play a prominent
role is in the quantum behavior of the early universe 22 , for the UG context
FIG. 1 shows the changes that the universe could have if noncommutativity is
considered,

Figure 1: Plot of $|\psi|^{2}$ varying the variables $u,\bar{v}$ and
$\theta=4$.

and FIG. 2 the possibility of tunneling among states where the peaks appears.
The integral (23) is solved numerically for the variables $u,\bar{v}$ in the
case $p_{1}>0$, $\lambda<\sqrt{3}$ with the parameters $a=1.5$, $b=1.3$,
$c_{0}=0,c_{1}=1$ and $\epsilon_{0}=\lambda=1$.

Figure 2: Variation of $|\psi|^{2}$ along the main peaks with $\theta=4$. The
inner plot shows $|\psi|^{2}$ with $\theta=0$.

##  III Semiclassical Approximation

We shall make use of the semiclassical approximation to extract the dynamics
of the UGWDW equation, taking in mind that such approximation hides the
problem of time and hence the dynamical evolution of the minisuperspace can be
obtained. The semiclassical limit is achieved considering in (8) the WKB
procedure with $\psi(x,\phi)\approx e^{i(S_{1}(x)+S_{2}(\phi))}$ and the
conditions

$(\partial_{q^{\mu}}S_{\mu})^{2}\gg\partial^{2}_{q^{\mu}}S_{\mu},$ (24)

resulting the aforementioned EHJ equation

$\displaystyle\frac{1}{24}\Big{(}\frac{dS_{1}}{dx}\Big{)}^{2}-\frac{1}{2}\Big{(}\frac{dS_{2}}{d\phi}\Big{)}^{2}+\epsilon_{0}V_{0}e^{6x}e^{-\lambda\phi}+$
$\displaystyle 2\epsilon_{0}\Lambda e^{6x}+6\epsilon_{0}ke^{4x}=0.$ (25)

Using the definition for the momenta

$\displaystyle\partial_{x}{S_{1}}$
$\displaystyle=\partial_{\dot{x}}{\mathcal{L}}=12\epsilon_{0}e^{6x}\dot{x}$
$\displaystyle\partial_{\phi}{S_{2}}$
$\displaystyle=\partial_{\dot{\phi}}{\mathcal{L}}=-\epsilon_{0}e^{6x}\dot{\phi},$
(26)

equation (25) transforms in

$\displaystyle
6\epsilon_{0}(\dot{x})^{2}-\frac{\epsilon_{0}}{2}(\dot{\phi})^{2}+V_{0}G_{1}(x,\phi)+2\Lambda
e^{-6x}+$ $\displaystyle 6ke^{-8x}=0,$ (27)

where333The next allow us to avoid cross terms.

$\displaystyle G_{1}(x,\phi)$ $\displaystyle=e^{-6x}e^{-\lambda\phi}$
$\displaystyle=\sum_{n\in\mathbb{N}\cup\\{0\\}}\frac{(-1)^{n}(6x+\lambda\phi)^{n}}{n!}$
$\displaystyle\approx 1-6x-\lambda\phi,$ (28)

we get the relations

$\displaystyle\frac{dt}{\sqrt{6\epsilon_{0}}}$
$\displaystyle=\frac{dx}{\sqrt{|C+6V_{0}x-2\Lambda e^{-6x}-6ke^{-8x}|}}$
$\displaystyle\frac{\sqrt{2}dt}{\sqrt{\epsilon_{0}}}$
$\displaystyle=\frac{d\phi}{\sqrt{C+V_{0}(\lambda\phi-1)}}.$ (29)

The first equation in (29), under the transformation
$\alpha\leftrightarrow-x$, we find an implicit expression for $\alpha$ given
by

$-t=\sqrt{12\epsilon_{0}}\int{\frac{d\alpha}{\sqrt{|C-12V_{0}\alpha-4\Lambda
e^{6\alpha}-12ke^{8\alpha}|}}},$ (30)

and the second one is straightforward to solve for the variable $\phi$

$\phi=\frac{\lambda
V_{0}}{4}\Big{(}\frac{\sqrt{2}t}{\sqrt{\epsilon_{0}}}+C_{1}\Big{)}^{2}-\frac{C}{\lambda
V_{0}}+\frac{1}{\lambda}.$ (31)

In the same manner, (19) with (10), (20) and $\psi_{nc}(u,v)\approx e^{i[\pm
p_{1}u+f(\theta)]}e^{iS_{1}(v)}$, where $f(\theta)$ shows the contribution of
the parameter of no commutation, gives for large $u$

$\displaystyle\Big{(}\frac{dS_{1}}{dv}\Big{)}^{2}-3(\lambda^{2}-3)p_{1}^{2}+\epsilon_{0}\Big{(}12\Lambda
e^{3v}e^{\pm 3p_{1}\lambda\theta}+$ $\displaystyle 36ke^{2v}e^{\pm
2p_{1}\lambda\theta}\Big{)}=0.$ (32)

As a final step, in (32) applying (26), we are in position to derive a NCC
relation (implicit for $\alpha$)444Considering a first order approximation for
$e^{-12x}$ and the transformation $\alpha\leftrightarrow-x$.

$\displaystyle-t=\sqrt{12\epsilon_{0}}\int{\frac{d\alpha}{\sqrt{|\mathcal{M}|}}},$
(33)

with $\mathcal{M}=C+12\kappa^{2}\alpha-4\Lambda e^{6\alpha}e^{\pm
3p_{1}\lambda\theta}-12ke^{8\alpha}e^{\pm 2p_{1}\lambda\theta}$ and
$\kappa=\sqrt{\lambda^{2}-3}p_{1}$. It is interesting to note in the last term
that when $\lambda=2$, $p_{1}=\sqrt{V_{0}}$ and $\theta\to 0$ we get (30). In
this vein, when $\kappa\to 0$ and $k=0$, in the UG NCC semiclassical
relation555If $\theta$ tends to zero we get the respective commutative
relation. for $\alpha$ we deduce, with $\Lambda_{nc}=4\Lambda e^{\pm
3\lambda\theta}$

$a^{3}_{nc}(t)\approx(\Lambda_{nc})^{-\frac{1}{2}}\Big{[}\rm
sech\Big{(}\frac{\sqrt{3}t}{2}\Big{)}\Big{]},$ (34)

being a similar expression in a flat space for the scale factor derived for
the respective NCC solution in GR 23 . Also, if CC does not contribute and
$V_{0}$ is small enough, there are no modifications.

##  IV Conclusions and Outlooks

Here we investigated Noncommutative Quantum Cosmology for the FLRW model in
the Unimodular context, although QC presents a limited model to describe the
quantum theory of the universe. Exists in literature a proposal for a
noncommutative theory of gravity 24 ; 25 , our work has provided a picture, as
seen in previous references 22 ; 26  for GR, that shows the drastically change
at the time of considering noncommutativity in the early Universe using
Unimodular Gravity. We find that the construction and computation of the NCC-
WDW equation is a complicated task, due at each $\theta$ order, higher
derivates will appear. We compare the states with those obtained in the
noncommutative minisuperspace and the parameter of noncommutativity proposed,
together with the case $p_{1}>0,\lambda<\sqrt{3}$, are selected for a better
approach, observing that making $c_{0}=0$ gives a similar expression already
reported 22 . In the same manner that in GR, the deformation of the
minisuperspace variables creates new possible states of the Universe evolving
not only from the state in the commutative case, but from any other
represented in FIG. 1 where the peaks compete to be the most probable state of
the Universe. On the other hand, the semiclassical case in the UG framework
shows a commutative and NCC expression for the variable $\alpha$ is quite
similar to the respective one in GR but we must note that the evolution in
time for the variable $\phi$ is different, since the UG expression differs
with the solution found in GR, without affecting the desire to study some
cosmological parameters. In general, the wave functions $\psi_{nc}$ and the
equation (33), under some considerations in the parameters, show equivalences
in the QC formalism between UG and GR for the model.

###### Acknowledgements.

J.A. A.-M. acknowledges CONACyT for the support by a postdoctoral fellowship
at CINVESTAV, México. M.A.G.-A. acknowledges support from cátedra Marcos
Moshinsky and Universidad Iberoamericana for support with the SNI grant. E.A.
M.-B. is grateful to M. Sabido for discussions and very useful comments and
Adler, also the authors recognize the useful comments of the reviewers.

## References

  * (1) A.G. Riess, V. Filippennko, P. Chalis, A. Clocchiatti, A. Diercks, et al, The Astronomical Journal.  116, 1009, (1998).
  * (2) N. Aghanim, et al (Planck), arXiv:1087.06209 [astro-ph.CO].
  * (3) M. Carroll, Living Rev. Rel. 4, 1, (2001), arXiv:astro-ph/004075 [astro-ph.CO].
  * (4) S. Weinberg, Reviews of Modern Physics 61, (1989).
  * (5) Y. B. Zeldovich, Soviet Physics Uspekhi 11, (1968).
  * (6) A. Hernández-Almada, J. Magana, M.A. García-Aspeitia and V. Motta, Eur. Phys. J.C. 79 12, (2019), arXiv:1805.07895 [astro-ph.CO].
  * (7) A. Hernández-Almada, G. Leon, J. Magana, M.A. García-Aspeitia and V. Motta, Mon. Not. Roy. Astron. Soc. 497 1590, (2020), arXiv:2002.12881 [astro-ph.CO].
  * (8) R. Maartens, Living Rev. Rel. 7, 7, (2004), arXiv:gr-qc/03120 [gr-qc].
  * (9) M.A. García-Aspeitia, A. Hernández-Almada, J. Magana, M.H. Amante, V. Motta and C. Martínes-Robles, Phys. Rev. D 97 101301, (2018), arXiv:1804.05085 [gr-qc].
  * (10) M.A. García-Aspeitia, J. Magana, A. Hernández-Almada and V. Motta, Phys. Rev. D 27 1850006, (2017), arXiv:1619.08220 [astro-ph.CO].
  * (11) C. Escamila-Rivera, A. Hernández-Almada, M.A. García-Aspeitia and V. Motta, (2020), 10.1142/S0218271821500772, arXiv:2005.13957 [gr-qc].
  * (12) M.A. García-Aspeitia, C. Martínes-Robles, A. Hernández-Almada, J. Magana and V. Motta, Phys. Rev. D 99 123525, (2019), arXiv:1903.06344 [gr-qc].
  * (13) M.A. García-Aspeitia, A. Hernández-Almada, J. Magana and V. Motta, Phys. Dark Univ. 32 100840, (2021), arXiv:1912.07500 [astro-ph.CO].
  * (14) V. Motta, M.A. García-Aspeitia, A. Hernández-Almada, J. Magana and T. Verdugo, Universe 7 163, (2021), arXiv:2104.04642 [astro-ph.CO].
  * (15) G. F. Ellis, H. van Elst, J. Murugan and J.P. Uzan, 28 225007, (2011).
  * (16) A. Eichhorn, Class. Quant. Grav. 30 115016, (2013), arXiv:1301.0879 [gr-qc].
  * (17) A. H. Chamseddine, Phys. Lett. B 504, 33 (2001).
  * (18) O. Obregon, M. Sabido, E. Mena, Mod. Phys. Lett. A24, 1907-1914 (2009).
  * (19) L. Smolin, Phys. Rev. D. 80 084003, (2009), arXiv:0904.4841 [hep-th].
  * (20) W. Guzmán, M. Sabido, J. Socorro and L. Urena-López, Int. J. Mod.Phys. D 16, 641, (2007), arXiv:gr-qc/0506041.
  * (21) arXiv:hep-th/0410213.
  * (22) J. Gamboa, M. Loewe and J. C. Rojas, Phys. Rev D 64, 067901 (2001); M. Chaichian, M. M. Sheikh-Jabbari and A. Tureanu, Phys. Rev. Lett. 86 2716 (2001).
  * (23) E. Alvarez, S. Gonzalez-Martín, M. Herrero-Valea and C.-Martín, JHEP 78, 220151, (2015), 10.1007/JHEP08(2015)078, arXiv:1505.01995.
  * (24) J.A. Astorga-Moreno, J. Chagoya, J. Flores-Urbina and M. A. García-Aspeitia, JCAP 09, (2019), 10.1088/JCAP09(2019)005, arXiv:1905.11253.
  * (25) H. García-Compeán, O. Obregón and C. Ramírez, Phys. Rev. Lett. 88, (2002).
  * (26) E. A. Mena-Barboza, O. Obregón and M. Sabido, Int. J. Mod. Phys. D 18, (2015).
  * (27) N. Seiberg and E. Witten, JHEP 09, 032, (1999).
  * (28) N. Nekrasov and A. Schwarz, Commun. Math. Phys. 198, 689, (1999).
  * (29) A. Crespo-Hernandez, E. A. Mena-Barboza, Int. J. Mod. Phys. D 29, (2020).