# Conservation laws for potential vorticity in a salty ocean or cloudy
atmosphere

###### Abstract

One of the most important conservation laws in atmospheric and oceanic science
is conservation of potential vorticity. The original derivation is
approximately a century old, in the work of Rossby and Ertel, and it is
related to the celebrated circulation theorems of Kelvin and Bjerknes.
However, the laws apply to idealized fluids, and extensions to more realistic
scenarios have been problematic. Here, these laws are extended to hold with
additional fundamental complexities, including salinity in the ocean, or
moisture and clouds in the atmosphere. In the absence of these additional
complexities, it is known that potential vorticity is conserved following each
fluid parcel; here, for a salty ocean or cloudy atmosphere, the general
conserved quantity is potential vorticity integrated over certain pancake-
shaped volumes. Furthermore, the conservation laws are also related to a
symmetry in the Lagrangian, which brings a connection to the symmetry-
conservation relationships seen in other areas of physics.

Geophysical Research Letters

Department of Mathematics, Department of Engineering Physics, Department of
Atmospheric and Oceanic Sciences,
University of Wisconsin–Madison, Madison, WI, 53706, USA

P<EMAIL_ADDRESS>
Important conservation laws of circulation and potential vorticity are known
only under idealized assumptions.

Here, conservation laws are described with additional realism, namely salinity
in the ocean or moisture and clouds in the atmosphere.

Potential vorticity is not conserved for each fluid parcel but for certain
pancake-shaped volumes.

## Plain Language Summary

A vortex can be seen in the atmosphere or ocean in a variety of settings,
including the intense vortices that are familiar from tornadoes and
hurricanes. A quantity called vorticity is a measure of the strength of a
vortex, or, more generally, of the amount of swirl in a fluid. Intimately
connected to vorticity is an important conserved quantity referred to as
potential vorticity. This quantity remains unchanged following the trajectory
of a fluid parcel. Owing to its conserved nature, potential vorticity is
widely used to study a wide range of weather events. However, this century-old
conservation result is only valid in an idealized setting: an atmosphere
devoid of clouds or an ocean without dissolved salt—i.e., without salinity.
Here, the conservation law is extended to hold in a cloudy atmosphere and
salty oceans. The generalized conservation statement presented here will aid
in the wider applicability of potential vorticity for analyzing and
understanding atmospheric and oceanic dynamics.

##  1 Introduction

In addition to conservation laws of mass, momentum, and energy, other
conservation laws arise for fluids, such as conservation of circulation and
potential vorticity. The circulation $\Gamma$ is defined as the integral of
the velocity $\vec{u}$ along a closed curve $C$,

$\Gamma=\oint_{C}\vec{u}\cdot d\vec{l},$ (1)

and the circulation theorems of Kelvin and Bjerknes [Thomson (1867), Bjerknes
(1898), Thorpe . (2003)] show that, under certain assumptions, the circulation
is conserved if the closed curve $C(t)$ moves with the fluid. See Figure 1 for
an illustration. The circulation is also related to the vorticity,
$\vec{\omega}=\nabla\times\vec{u}$, since Eqn. 1 can be rewritten, using
Stokes’ theorem, as

$\Gamma=\int_{A}\vec{\omega}\cdot d\vec{A},$ (2)

which is an area integral over any surface $A$ whose boundary is the closed
curve $C$, and where $d\vec{A}$ is a surface area element whose vector
direction is perpendicular to the surface. Helmholtz [Helmholtz (1858)] had
earlier formulated some related conservation statements in terms of vorticity.
An associated quantity is the potential vorticity (PV), which is the dot
product of the vorticity vector and the entropy gradient, $\nabla s$, weighted
by the fluid density $\rho$; that is,

$PV=\frac{\vec{\omega}\cdot\nabla s}{\rho}.$ (3)

Ertel [Ertel (1942)] showed that PV is conserved following the trajectory of a
fluid parcel, which builds on an earlier result of Rossby [Rossby (1940)] for
the shallow water equations.

Figure 1: Geometry of the circulation theorem for a dry atmosphere or
freshwater ocean. The curve $C(t)$ may be any curve on a surface of constant
entropy, $s(\vec{x},t)=c$.

PV is a fundamental quantity of interest in geophysical flows [Müller (1995),
Salmon (1998)]. It is extensively used in analysis of weather events [Davis
Emanuel (1991), Lackmann (2002)], the general ocean circulation [Rhines
(1986), Pollard Regier (1990), Holland . (1984), Müller (1995)],
magnetohydrodynamics (MHD) and astrophysical fluid dynamics [Webb Mace
(2015)]. The wide-ranging applications of PV stem from its conservation
properties and the notion of PV inversion [Hoskins . (1985), Smith Stechmann
(2017), Wetzel . (2020)].

Despite the importance of PV and the further knowledge gained over
approximately a century, the conservation laws of circulation and PV are
limited to fluids that are relatively idealized. In particular, these
conservation laws apply to an ocean or atmosphere that is composed of a single
fluid substance—water in the ocean, or dry air in the atmosphere. In nature,
the ocean and atmosphere include other substances which are of fundamental
significance. Moisture and clouds in the atmosphere are associated with
weather events such as hurricanes, tornadoes, and monsoons. Salinity in the
ocean affects the density and helps drive the thermohaline circulation and
meridional overturning circulation that move heat from low latitudes to high
latitudes [Marshall Schott (1999), Curry Mauritzen (2005), Peterson . (2006),
Vallis (2017)]. As one route to better understanding and predicting these
phenomena, it is desirable to have knowledge of the associated conserved
quantities.

The main goal of the present paper is to derive conservation principles for
circulation and potential vorticity, for the case of an ocean with salinity or
an atmosphere with moisture and clouds. The atmospheric case will be described
first, and then the oceanic case will follow in a similar way. Also,
circulation will be treated first, and then potential vorticity.

##  2 Circulation

The starting point is the evolution equation for the circulation $\Gamma$,
which was defined above in Eqn. 1. Its evolution equation follows from the
equations for conservation of mass and momentum [Thorpe . (2003), Bjerknes
(1898), Vallis (2017)] and it takes the form

$\frac{D\Gamma}{Dt}=\oint_{C(t)}\frac{1}{\rho}\nabla p\cdot d\vec{l},$ (4)

where $p$ is the pressure, $C(t)$ is a closed curve that moves along with the
fluid, and $D/Dt=\partial/\partial t+\vec{u}\cdot\nabla$ is a material
derivative—i.e., a derivative along the trajectory of a fluid parcel. See the
Supplementary Materials for a derivation. The fluid is assumed to be
compressible and inviscid.

Before considering the moist case, it is instructive to consider the dry case,
for which it is known that circulation is conserved, under certain assumptions
on the curve $C(t)$. To see this, one can rewrite (4) as

$\frac{D\Gamma}{Dt}=\oint_{C(t)}\theta\;d\pi,$ (5)

where the Exner function $\pi(p)$ is a function of pressure, and where the
potential temperature $\theta$ is a function of entropy, as
$s=c_{p}\log\theta+const.$, where $c_{p}$, commonly assumed constant for a dry
atmosphere, is the specific heat at constant pressure. The details of this
derivation are provided in the Supplementary Materials. From (5), one can
deduce the scenarios when the right-hand side is zero and circulation $\Gamma$
is conserved. In particular, if $\theta$ (and hence also entropy $s$) is a
constant on the closed curve $C(t)$, then the right-hand side of (5) is zero,
by the fundamental theorem of calculus for line integrals. Consequently,
circulation is conserved,

$\frac{D\Gamma}{Dt}=0,$ (6)

if the closed curve $C(t)$ lies on a surface of constant entropy. See Figure 1
for an illustration. In order for the material curve $C(t)$ to remain on a
surface of constant entropy for all times, the fluid is assumed to be
adiabatic, so that $Ds/Dt=0$. Finally, from (6), the circulation $\Gamma$ is
then said to be a _material invariant_ , since its material derivative is
zero.

In the moist case, one could try to repeat the derivation from the dry case to
arrive at a circulation theorem. However, this line of reasoning fails for a
moist system, since the integrand that would arise in (5) would no longer be a
material invariant, due to phase changes and cloud latent heating.

We now show that the challenges of the moist case can actually be overcome by
referring to fundamental principles of moist thermodynamics. Two derivations
will be shown: a derivation that directly refers to enthalpy, and a derivation
that does not. In terms of the enthalpy $h(s,p,q_{t})$, the fundamental
thermodynamic relation [Landau Lifshitz (1980), Landau Lifshitz (1987),
Pauluis (2008)] states that

$dh=T\,ds+\rho^{-1}\ dp+\mu\,dq_{t},$ (7)

which can be viewed as the differential of the function $h(s,p,q_{t})$ as

$dh=\left(\frac{\partial h}{\partial
s}\right)_{p,q_{t}}\,ds+\left(\frac{\partial h}{\partial p}\right)_{s,q_{t}}\
dp+\left(\frac{\partial h}{\partial q_{t}}\right)_{s,p}\,dq_{t},$ (8)

where $h$ is enthalpy, $T$ is temperature, $q_{t}$ is the total water specific
humidity, and $\mu=\mu_{v}-\mu_{d}$ is the difference of the chemical
potentials associated with water vapor and dry air, respectively. As a first
important observation, notice that (7) includes the term $\rho^{-1}\;dp$,
which is also the sole term that appears in the evolution equation for
circulation in (4). Therefore, inserting the fundamental relation (7) into the
evolution equation for circulation in (4), we have

$\frac{D\Gamma}{Dt}=-\oint_{C(t)}T\;ds-\oint_{C(t)}\mu\;dq_{t},$ (9)

where it was used that $\oint_{C(t)}dh=0$ for a closed curve. The aim now is
to identify scenarios when the right-hand side is zero. In this direction,
note that the line integrals are zero if the curve $C(t)$ lies on a surface of
constant entropy $s$ _and_ a surface of constant $q_{t}$. Furthermore, in
order for the material curve to have constant $s$ and $q_{t}$ for all times,
it is assumed that $Ds/Dt=0$ and $Dq_{t}/Dt=0$, so that $s$ and $q_{t}$ are
both material invariants, if reversible phase changes are assumed between
water vapor and liquid water, and precipitation is absent. Therefore, the
right hand side of (9) vanishes and we have

$\frac{D\Gamma}{Dt}=0,$ (10)

if $C(t)$ is a closed curve of constant $s$ and $q_{t}$. See Figure 2 for an
illustration. This is the moist, cloudy analog of the circulation theorems of
Kelvin and Bjerknes.

As an alternative derivation of (10) that does not directly refer to enthalpy,
return again to the starting point of (4), where the integrand is $\rho^{-1}$.
Now use a fundamental property of moist thermodynamics: any moist
thermodynamic variable can be written as a function of $s$, $q_{t}$ and $p$
[Pauluis (2008)]. Hence, $\rho^{-1}\;dp$ can be written as
$\rho^{-1}(s,q_{t},p)\;dp$, which, on a circuit $C(t)$ of constant entropy $s$
and total water mixing ratio $q_{t}$, is a function of pressure $p$ alone.
Consequently, (4) can furthermore be simplified to

$\frac{D\Gamma}{Dt}=\oint_{C(t)}df,$ (11)

where $f(p)$ is an antiderivative that satisfies
$df=(df/dp)\;dp=\rho^{-1}(s,q_{t},p)\;dp$. By (7) and (8), since
$(dh/dp)_{s,q_{t}}=\rho^{-1}$, the function $f$ can be identified as the
enthalpy $h$, which is insightful but not essential for this derivation.
Finally, since $C(t)$ is a closed curve, it follows from (11) that

$\frac{D\Gamma}{Dt}=0,$ (12)

if $C(t)$ is a closed curve of constant $s$ and $q_{t}$.

Figure 2: Geometry of the circulation theorem for an atmosphere with clouds or
an ocean with salinity. The curve $C(t)$ is a curve of constant entropy $s$
and total water specific humidity $q_{t}$.

As a comparison of the dry and moist cases, notice that both apply to material
curves $C(t)$ on surfaces of constant entropy $s$. However, while _any_ such
curve is valid for a dry atmosphere, the curve must also have constant $q_{t}$
for a moist, cloudy atmosphere.

##  3 Potential vorticity

Now consider the second quantity of interest here, defined above in (3):
potential vorticity. Its evolution equation follows from the equations for
conservation of mass, momentum, and entropy [Müller (1995), Schubert . (2001)]
and it takes the form

$\rho\frac{D}{Dt}\left(\frac{\vec{\omega}\cdot\nabla s}{\rho}\right)=\nabla
s\cdot\nabla\times\left(\frac{1}{\rho}\nabla p\right)$ (13)

See the Supplementary Materials for a derivation. On the right-hand side, the
term $\nabla\times(\rho^{-1}\nabla p)$ arises from the curl of the pressure
gradient in the statement of conservation of momentum.

For a dry atmosphere, PV is conserved for each fluid parcel, and it is helpful
to review this case as a prelude to the moist case. To see how dry PV is
conserved, note that the right-hand side of (13) can be written as

$\nabla s\cdot\nabla\times\left(\frac{1}{\rho}\nabla
p\right)=-\frac{1}{\rho^{2}}\nabla s\cdot\nabla p\times\nabla\rho,$ (14)

which is a scalar triple product. Then one can use a fundamental property of
thermodynamics for a dry atmosphere: the entropy can be expressed as a
function of pressure and density, so that $s=s(p,\rho)$. Consequently, we have

$\nabla s=\frac{\partial s}{\partial p}\nabla p+\frac{\partial
s}{\partial\rho}\nabla\rho$ (15)

and inserting this into (14) shows that the right-hand side of (13) is zero,
and the PV is conserved for each fluid parcel:

$\frac{D}{Dt}\left(\frac{\vec{\omega}\cdot\nabla s}{\rho}\right)=0.$ (16)

In essence, this proof works smoothly because the entropy $s$ is a function of
pressure $p$ and density $\rho$, for a dry atmosphere. However, for a moist
atmosphere, due to the effects of phase changes and cloud latent heating, it
is not true that $s=s(p,\rho)$, and it is therefore difficult to see how to
extend these proof ideas to apply to the moist case.

For a moist atmosphere with clouds, we now show that the difficulty of PV
conservation can be resolved by appealing to fundamentals of moist
thermodynamics. In particular, use the gradient form of the fundamental
thermodynamic relation in (7), and insert into (13) for the $\rho^{-1}\nabla
p$ term. Then, after using vector calculus identities, (13) becomes

$\rho\frac{D}{Dt}\left(\frac{\vec{\omega}\cdot\nabla s}{\rho}\right)=-\nabla
s\cdot\nabla\times\left(\mu\nabla q_{t}\right).$ (17)

The benefit of having replaced $\rho^{-1}\nabla p$ with $\mu\nabla q_{t}$ will
be seen below and arises from the fact that the right-hand side of (17) now
involves two quantities, $s$ and $q_{t}$, which are both conserved for each
fluid parcel, for the case of reversible phase changes between water vapor and
cloud liquid water, with no precipitation.

To proceed with finding the conservation law for moist PV, we abandon the idea
that moist PV can be conserved for each fluid parcel. In other words, we
abandon hope of showing that the right-hand side of (17) is zero. Instead,
consider the integral of moist PV over certain volumes. The evolution equation
of volume-integrated PV is

$\frac{D}{Dt}\int\int\int_{V(t)}\frac{\vec{\omega}\cdot\nabla
s}{\rho}\;\rho\,dV=\int\int\int_{V(t)}\rho\frac{D}{Dt}\left(\frac{\vec{\omega}\cdot\nabla
s}{\rho}\right)\;dV$ (18) $=-\int\int\int_{V(t)}\nabla\cdot\left(\mu\nabla
q_{t}\times\nabla s\right)\;dV$ (19) $=-\int\int_{A(t)}\mu\nabla
q_{t}\times\nabla s\cdot d\vec{A},$ (20)

where the volume integral in (18) is mass-weighted using density $\rho$, and
where the volume $V(t)$ is a material volume that moves with the fluid but
otherwise remains to be specified. See the Supplementary Materials for details
of the derivation. In brief, (18) uses the transport theorem, (19) uses (17)
and some vector calculus identities, and (20) follows from the divergence
theorem, where $A(t)$ is the surface that encloses the material volume $V(t)$.

Now it is time to identify the special volumes for which (20) is zero and
integrated moist PV is conserved. The intuition is similar to the case of the
moist circulation theorem in (9) where the appearance of the line elements
$ds$ and $dq_{t}$ suggested the choice of curves of constant $s$ and $q_{t}$.
Here, it is a surface integral that arises in (20), and in order for the
integral to vanish, the surface area element $d\vec{A}$ must be perpendicular
to $\nabla s$ or $\nabla q_{t}$. Hence, we have

$\frac{D}{Dt}\int\int\int_{V(t)}\frac{\vec{\omega}\cdot\nabla
s}{\rho}\;\rho\,dV=0,$ (21)

if the volume is defined to be enclosed by surfaces of constant $s$ and
surfaces of constant $q_{t}$. An alternative derivation, which does not
explicitly use the fundamental thermodynamic relation, is shown in the
Supplementary Materials. Either derivation leads to the same result, (21), the
conservation law for PV for a cloudy atmosphere, which applies to volume-
integrated PV.

Figure 3: Geometry of the PV conservation law for an atmosphere with clouds or
an ocean with salinity. The conserved quantity is not PV of individual
parcels, but PV integrated over certain cylinder-like volumes.

More generally, the surface could be composed piecewise, based on level
surfaces of general functions $F(s,q_{t})$, since any such level surface is
perpendicular to $\nabla s\times\nabla q_{t}$. Nevertheless, it is convenient
and simple to choose surfaces of constant $s$ or constant $q_{t}$, as
illustrated in Figure 3. The simplest such volume is shaped like a thin
cylinder, or pill box, or pancake.

As perhaps the most special case, notice that the volume $V(t)$ in Figure 3
will shrink to a point at a maximum or minimum value of $q_{t}$ on a constant-
entropy surface. As a result, at minima or maxima of $q_{t}$, the PV is
conserved for the individual parcel.

As another generalization, notice that the PV could be defined as
$\rho^{-1}\vec{\omega}\cdot\nabla q_{t}$ with $q_{t}$ in the role that is
normally played by entropy $s$. A similar conservation law also follows for
such a $q_{t}$-based PV. Moreover, the PV could be defined as
$\rho^{-1}\vec{\omega}\cdot\nabla F(s,q_{t})$ for any function $F$ of $s$ and
$q_{t}$. In that case, the proof proceeds in the same way by writing the
fundamental thermodynamic relation in a form that replaces $s$ and $q_{t}$ by
$F(s,q_{t})$ and $G(s,q_{t})$, where $G$ is arbitrary but functionally
independent of $F$.

For an ocean with salinity, the conservation laws for circulation and PV
follow in the same way. Simply replace specific humidity $q_{t}$ by salinity
$S$, and to avoid confusion, change the notation of the entropy $s$ to instead
be $\eta$, as is common in oceanography. Table 1 summarizes the conservation
laws for both the cloudy atmosphere and salty ocean.

| Cloudy Atmosphere | Salty Ocean
---|---|---
Circulation Theorem | $\frac{D}{Dt}\oint_{C(t)}\vec{u}\cdot d\vec{l}=0$ | $\frac{D}{Dt}\oint_{C(t)}\vec{u}\cdot d\vec{l}=0$
Curve $C(t)$ | Constant $s$ and $q_{t}$ | Constant $\eta$ and $S$
PV Conservation Law | $\frac{D}{Dt}\int\int\int_{V(t)}\frac{\vec{\omega}\cdot\nabla s}{\rho}\;\rho\,dV=0$ | $\frac{D}{Dt}\int\int\int_{V(t)}\frac{\vec{\omega}\cdot\nabla\eta}{\rho}\;\rho\,dV=0$
Surface of Volume $V(t)$ | Constant $s$ or $q_{t}$ | Constant $\eta$ or $S$
Table 1: Summary of conservation laws Conservation laws for an atmosphere with
clouds and an ocean with salinity. Commonly used notation for a cloudy
atmosphere is $s$ and $q_{t}$ for the entropy and total water specific
humidity, respectively, and for a salty ocean is $\eta$ and $S$ for the
entropy and salinity, respectively. Rotation and the Coriolis force could also
be incorporated with modifications described in (23) and (24).

##  4 Symmetry–conservation relationship

A symmetry–conservation relationship is also associated with these
conservation laws of circulation and PV. In particular, it is a particle-
relabeling symmetry, which, as the name suggests, involves particles whose
positions are $\vec{x}(\vec{a},t)$ or the relabeled positions
$\vec{x}(\vec{a}\,^{\prime},t)$, where the original label $\vec{a}$ was
replaced by the relabeling $\vec{a}\,^{\prime}=\vec{a}\,^{\prime}(\vec{a},t)$.
In a discrete setting, the relabeling of $\vec{x}_{n}(t)$ to
$\vec{x}_{n^{\prime}}(t)$ would simply involve a permutation of the labels,
$n=1,2,3,\cdots,N$, but there is no guarantee of an associated conservation
law for such a discrete symmetry. For the continuum setting of a cloudy
atmosphere, the symmetry applies to the Lagrangian

$\mathcal{L}(t)=\int\int\int\rho\left[\frac{1}{2}|\vec{u}|^{2}-E(\rho,s,q_{t})-\Phi(\vec{x})\right]\;dV_{a},$
(22)

where $E(\rho,s,q_{t})$ is the internal energy, $\Phi(\vec{x})$ is the
gravitational potential, and the integral is over the particle labels
$\vec{a}$, as the continuum version of a sum over the particles.

A key observation is that only some special particle relabelings will leave
the Lagrangian unchanged. For instance, for a dry atmosphere, the internal
energy $E(\rho,s)$ is a function of density and entropy, and it is well-known
that $E(\rho,s)$ and the Lagrangian remain unchanged for certain particle
relabelings on surfaces of constant entropy $s$ [Salmon (1998)]; and it
follows that the Kelvin–Bjerknes circulation theorem holds for curves $C(t)$
that lie on surfaces of constant entropy, as mentioned in (6) and Figure 1
above. Now, for a moist atmosphere, one can see the natural extension: the
particle relabeling should keep both $s$ and $q_{t}$ unchanged in order to
keep $E(\rho,s,q_{t})$ and the Lagrangian unchanged; consequently, the moist
circulation theorem in (10) and Figure 2 holds for curves $C(t)$ of constant
$s$ and $q_{t}$. These symmetry–conservation ideas have been derived in detail
for a moist Boussinesq setting [Kooloth . (2022)] and here provide motivation
and further understanding of the moist conservation laws of circulation and
PV. For instance, because the particle relabeling is constrained to curves
$C(t)$ of both constant $s$ and $q_{t}$, it follows that moist PV is not
conserved for individual parcels.

##  5 Concluding discussion

Rotation and the Coriolis term could also be incorporated here, in which case
the circulation theorem becomes

$\frac{D}{Dt}\oint_{C(t)}(\vec{u}+\vec{\Omega}\times\vec{x})\cdot d\vec{l}=0,$
(23)

where $\Omega$ is the angular rotation vector and $\vec{x}$ is the position
vector. The extension to include rotation follows standard procedures as in
cases without clouds or salinity [Salmon (1998), Vallis (2017), Cotter Holm
(2014)]. Furthermore, the PV conservation laws have the same form as in Table
1 except with $\omega=\nabla\times\vec{u}$ replaced by absolute vorticity,

$\vec{\omega}_{a}=\nabla\times\vec{u}+2\vec{\Omega},$ (24)

which is the sum of the relative vorticity and the angular rotation vector.

Many applications are possible for the conservation laws presented here. One
common use of PV conservation is to diagnose non-conservation, which is an
indication of additional physical processes [Haynes McIntyre (1987)]. The PV
conservation laws here could be used for similar purposes, with certain
modifications. For instance, cloud latent heating is considered one of the
sources of non-conservation for dry PV, but is incorporated into the
conservation law here for moist PV. Another application of PV conservation is
in numerical models of weather and climate. It is often desirable to design
such numerical methods to accurately satisfy the PV conservation law [Thuburn
(2008), Taylor Fournier (2010)]. The conservation laws here provide additional
targets for numerical conservation, now incorporating additional physical
processes of salinity and cloud latent heating.

##  6 Open Research

Data sharing not applicable to this article as no data sets were generated or
analysed during the current study.

###### Acknowledgements.

Leslie Smith and Sam Stechmann gratefully acknowledge grant support from the
Division of Mathematical Sciences of the National Science Foundation, in
conjunction with the award DMS-1907667.

## References

  * Bjerknes (1898) bjerknes1898hydrodynamischenBjerknes, V.  1898\.  Über einen hydrodynamischen Zirkulationssatz und seine Anwendung auf die Mechanik der Atmosphäre und des Weltmeeres Über einen hydrodynamischen zirkulationssatz und seine anwendung auf die mechanik der atmosphäre und des weltmeeres.  Kongl. Svenska Vetenskapsakad. Handl. Bd3197–106.
  * Cotter Holm (2014) cotter2014variationalCotter, C. Holm, D.  2014\.  Variational formulations of sound-proof models Variational formulations of sound-proof models.  Quart. J. Roy. Met. Soc.1406831966–1973.
  * Curry Mauritzen (2005) curry2005dilutionCurry, R. Mauritzen, C.  2005\.  Dilution of the northern North Atlantic Ocean in recent decades Dilution of the northern North Atlantic Ocean in recent decades.  Science30857291772–1774.
  * Davis Emanuel (1991) davis1991potentialDavis, CA. Emanuel, KA.  1991\.  Potential vorticity diagnostics of cyclogenesis Potential vorticity diagnostics of cyclogenesis.  Monthly Weather Review11981929–1953.
  * Ertel (1942) ertel1942neuerErtel, H.  1942\.  Ein neuer hydrodynamischer Wirbelsatz Ein neuer hydrodynamischer wirbelsatz.  Met. Zeitschr.59277–281.
  * Haynes McIntyre (1987) haynes1987evolutionHaynes, PH. McIntyre, ME.  1987\.  On the evolution of vorticity and potential vorticity in the presence of diabatic heating and frictional or other forces On the evolution of vorticity and potential vorticity in the presence of diabatic heating and frictional or other forces.  J. Atmos. Sci.445828–841.
  * Helmholtz (1858) helmholtz1858integralsHelmholtz, Hv.  1858\.  Über Integrale der hydrodynamischen Gleichungen, welche den Wirbelbewegungen entsprechen Über integrale der hydrodynamischen gleichungen, welche den wirbelbewegungen entsprechen.  J. Angew. Math.5525-55.
  * Holland . (1984) holland1984dynamicsHolland, W., Keffer, T. Rhines, P.  1984\.  Dynamics of the oceanic general circulation: the potential vorticity field Dynamics of the oceanic general circulation: the potential vorticity field.  Nature3085961698–705.
  * Hoskins . (1985) hoskins1985useHoskins, BJ., McIntyre, ME. Robertson, AW.  1985\.  On the use and significance of isentropic potential vorticity maps On the use and significance of isentropic potential vorticity maps.  Quart. J. Roy. Met. Soc.111470877–946.
  * Kooloth . (2022) kooloth2022hamiltonsKooloth, P., Smith, LM. Stechmann, SN.  2022\.  Hamilton’s principle with phase changes and conservation principles for moist potential vorticity Hamilton’s principle with phase changes and conservation principles for moist potential vorticity.  submitted.
  * Lackmann (2002) lackmann2002coldLackmann, GM.  2002\.  Cold-frontal potential vorticity maxima, the low-level jet, and moisture transport in extratropical cyclones Cold-frontal potential vorticity maxima, the low-level jet, and moisture transport in extratropical cyclones.  Monthly Weather Review130159–74.
  * Landau Lifshitz (1980) landau1980statisticalLandau, LD. Lifshitz, EM.  1980\.  Statistical Physics, Part 1 Statistical physics, part 1 (3 , 5).  Elsevier.
  * Landau Lifshitz (1987) landau1987fluidLandau, LD. Lifshitz, EM.  1987\.  Fluid Mechanics Fluid mechanics (2 , 6).  Elsevier.
  * Marshall Schott (1999) marshall1999openMarshall, J. Schott, F.  1999\.  Open-ocean convection: Observations, theory, and models Open-ocean convection: Observations, theory, and models.  Reviews of Geophysics3711–64.
  * Müller (1995) muller1995ertelMüller, P.  1995\.  Ertel’s potential vorticity theorem in physical oceanography Ertel’s potential vorticity theorem in physical oceanography.  Reviews of Geophysics33167–97.
  * Pauluis (2008) p08Pauluis, O.  2008\.  Thermodynamic consistency of the anelastic approximation for a moist atmosphere Thermodynamic consistency of the anelastic approximation for a moist atmosphere.  J. Atmos. Sci.6582719–2729.
  * Peterson . (2006) peterson2006trajectoryPeterson, BJ., McClelland, J., Curry, R., Holmes, RM., Walsh, JE. Aagaard, K.  2006\.  Trajectory shifts in the Arctic and subarctic freshwater cycle Trajectory shifts in the Arctic and subarctic freshwater cycle.  Science31357901061–1066.
  * Pollard Regier (1990) pollard1990largePollard, R. Regier, L.  1990\.  Large variations in potential vorticity at small spatial scales in the upper ocean Large variations in potential vorticity at small spatial scales in the upper ocean.  Nature3486298227–229.
  * Rhines (1986) rhines1986vorticityRhines, PB.  1986\.  Vorticity dynamics of the oceanic general circulation Vorticity dynamics of the oceanic general circulation.  Annual Review of Fluid Mechanics181433–497.
  * Rossby (1940) rossby1940planetaryRossby, CG.  1940\.  Planetary flow patterns in the atmosphere Planetary flow patterns in the atmosphere.  Quart. J. Roy. Met. Soc66 (Suppl.)68–87.
  * Salmon (1998) salmon1998lecturesSalmon, R.  1998\.  Lectures on Geophysical Fluid Dynamics Lectures on Geophysical Fluid Dynamics.  Oxford University Press.
  * Schubert . (2001) schubert2001potentialSchubert, WH., Hausman, SA., Garcia, M., Ooyama, KV. Kuo, HC.  2001\.  Potential vorticity in a moist atmosphere Potential vorticity in a moist atmosphere.  J. Atmos. Sci.58213148–3157.
  * Smith Stechmann (2017) smith2017precipitatingSmith, LM. Stechmann, SN.  2017\.  Precipitating quasigeostrophic equations and potential vorticity inversion with phase changes Precipitating quasigeostrophic equations and potential vorticity inversion with phase changes.  J. Atmos. Sci.74103285–3303.
  * Taylor Fournier (2010) taylor2010compatibleTaylor, MA. Fournier, A.  2010\.  A compatible and conservative spectral element method on unstructured grids A compatible and conservative spectral element method on unstructured grids.  Journal of Computational Physics229175879–5895.
  * Thomson (1867) thomson1867Thomson, W.  1867\.  4\. On vortex atoms 4. on vortex atoms.  Proceedings of the Royal Society of Edinburgh694-105.  10.1017/S0370164600045430
  * Thorpe . (2003) thorpe2003bjerknesThorpe, AJ., Volkert, H. Ziemiański, MJ.  2003\.  The Bjerknes’ Circulation Theorem: A Historical Perspective: A Historical Perspective The Bjerknes’ circulation theorem: A historical perspective: A historical perspective.  Bull. Am. Meteorol. Soc.844471–480.
  * Thuburn (2008) thuburn2008someThuburn, J.  2008\.  Some conservation issues for the dynamical cores of NWP and climate models Some conservation issues for the dynamical cores of NWP and climate models.  Journal of Computational Physics22773715–3730.
  * Vallis (2017) vallis2017atmosphericVallis, GK.  2017\.  Atmospheric and Oceanic Fluid Dynamics Atmospheric and Oceanic Fluid Dynamics.  Cambridge University Press.
  * Webb Mace (2015) webb2015potentialWebb, G. Mace, R.  2015\.  Potential vorticity in magnetohydrodynamics Potential vorticity in magnetohydrodynamics.  Journal of Plasma Physics811.
  * Wetzel . (2020) wetzel2020potentialWetzel, AN., Smith, LM., Stechmann, SN., Martin, JE. Zhang, Y.  2020\.  Potential Vorticity and Balanced and Unbalanced Moisture Potential vorticity and balanced and unbalanced moisture.  J. Atmos. Sci.7761913–1931.


# Refuting approaches to the log-rank conjecture for XOR functions

Hamed Hatami School of Computer Science, McGill University. Email:
<EMAIL_ADDRESS>Kaave Hosseini Department of Computer Science, University
of Rochester. Email<EMAIL_ADDRESS>Shachar Lovett Department of
Computer Science and Engineering, UC San Diego. Research supported by NSF
awards 1953928 and 2006443, and a Simons investigator award. Email:
<EMAIL_ADDRESS>Anthony Ostuni Department of Computer Science and
Engineering, UC San Diego. Research supported by NSF award 2006443. Email:
<EMAIL_ADDRESS>
###### Abstract

The log-rank conjecture, a longstanding problem in communication complexity,
has persistently eluded resolution for decades. Consequently, some recent
efforts have focused on potential approaches for establishing the conjecture
in the special case of XOR functions, where the communication matrix is lifted
from a boolean function, and the rank of the matrix equals the Fourier
sparsity of the function, which is the number of its nonzero Fourier
coefficients.

In this note, we refute two conjectures. The first has origins in Montanaro
and Osborne (arXiv’09) and is considered in Tsang et al. (FOCS’13), and the
second one is due to Mande and Sanyal (FSTTCS’20). These conjectures were
proposed in order to improve the best-known bound of Lovett (STOC’14)
regarding the log-rank conjecture in the special case of XOR functions. Both
conjectures speculate that the set of nonzero Fourier coefficients of the
boolean function has some strong additive structure. We refute these
conjectures by constructing two specific boolean functions tailored to each.

##  1 Introduction

The study of communication complexity seeks to determine the inherent amount
of communication between multiple parties required to complete a computational
task. Arguably, the most outstanding conjecture in the field is the log-rank
conjecture of Lovász and Saks [LS93]. They suggest that the (deterministic)
communication complexity of a two-party boolean function is upper bounded by
the matrix rank over $\mathbb{R}$. More precisely,

######  Conjecture 1.1 (Log-rank conjecture [LS93]).

Let $f:X\times Y\to\\{-1,1\\}$ be an arbitrary two-party boolean function.
Then,

$\operatorname{\mathrm{CC}}(f)\leq\operatorname{polylog}(\rank(f)),$

where $\operatorname{\mathrm{CC}}(f)$ is the communication complexity of $f$
and $\rank(f)$ is the rank over $\mathbb{R}$ of the corresponding boolean
matrix.

It is well-known that $\log(\rank(f))\leq\operatorname{\mathrm{CC}}(f)$
[MS82], so a positive resolution to 1.1 would imply that the communication
complexity of two-party boolean functions is determined by rank, up to
polynomial factors.

To date, the best known bound is still exponentially far from that in 1.1.
Concretely, Lovett [Lov16] showed that $\operatorname{\mathrm{CC}}(f)\leq
O(\sqrt{\rank(f)}\log\rank(f))$. Very recently, Sudakov and Tomon posted a
preprint improving the bound to $O(\sqrt{\rank(f)})$ [ST23]. In hopes of
improving this result, many researchers have considered the special case of
XOR functions, where $f_{\oplus}(x,y)=f(x+y)$ for a boolean function
$f:\mathbb{F}_{2}^{n}\to\\{-1,1\\}$ [MO09, ZS10, TWXZ13, STV14, HHL18, MS20].
The XOR setting has several convenient properties. For example, the
eigenvalues of $f_{\oplus}$ correspond to the Fourier coefficients of $f$.
Thus, $\rank(f_{\oplus})=|\mathrm{supp}(\widehat{f})|$, the number of nonzero
coefficients in $f$’s Fourier expansion (also known as the Fourier sparsity).
Additionally, Hatami, Hosseini, and Lovett [HHL18] proved a polynomial
equivalence between $\operatorname{\mathrm{CC}}(f_{\oplus})$ and the parity
decision tree complexity of $f$, denoted $\operatorname{\mathrm{PDT}}(f)$.
Parity decision trees are defined similarly to standard decision trees, with
the extra power that each node can query an arbitrary parity of input bits.
These facts together imply that the log-rank conjecture for XOR functions can
be restated as follows:

######  Conjecture 1.2 (XOR log-rank conjecture).

Let $f:\mathbb{F}_{2}^{n}\to\\{-1,1\\}$. Then,

$\operatorname{\mathrm{PDT}}(f)\leq\operatorname{polylog}(|\mathrm{supp}(\widehat{f})|).$

The best known bound, due to [TWXZ13, STV14], is
$\operatorname{\mathrm{PDT}}(f)\leq O(\sqrt{|\mathrm{supp}(\widehat{f})}|)$, a
mere $\log$-factor improvement on the general case bound by Lovett [Lov16],
and matched by the recent bound of Sudakov and Tomon [ST23].

###  1.1 Folding

Folding is a fundamental concept in the analysis of the additive structure of
a function’s Fourier support. Let

$\mathcal{S}=\mathrm{supp}(\widehat{f})=\\{\gamma\in\mathbb{F}_{2}^{n}:\widehat{f}(\gamma)\neq
0\\}\quad\text{and}\quad\mathcal{S}+\gamma=\\{s+\gamma:s\in\mathcal{S}\\}.$

If $(s_{1},s_{2}),(s_{3},s_{4})\in\binom{\mathcal{S}}{2}$ satisfy
$s_{1}+s_{2}=s_{3}+s_{4}=\gamma$, we say the pairs $(s_{1},s_{2})$ and
$(s_{3},s_{4})$ fold in the direction $\gamma$.

Analyzing folding directions is useful in constructing efficient PDTs in the
context of 1.2. In particular, when a function $f$ is restricted according to
the result of some parity query $\gamma$, all pairs of elements in
$\mathcal{S}$ that fold in the direction $\gamma$ collapse to a single term in
the restricted function $f|_{\gamma}$’s Fourier support. Iterating this
process until the restricted function is constant yields a PDT whose depth
depends on the number of iterations performed and, thus, on the size of the
folding directions queried. Indeed, this is the general strategy used to prove
the aforementioned closest result to 1.2 [TWXZ13, STV14].

###  1.2 Refuting a greedy approach

An approach dating back to [MO09] seeks to prove 1.2 through the existence of
a single large folding direction. They conjectured that there always exists
$\gamma_{1},\gamma_{2}$ such that
$|(\mathcal{S}+\gamma_{1})\cap(\mathcal{S}+\gamma_{2})|\geq|\mathcal{S}|/K$
for some constant $K>1$. This yields the following
$O(\log|\mathcal{S}|)$-rounds greedy approach: query $\gamma_{1}+\gamma_{2}$
and consider the function restricted to the query response. This restriction
decreases the Fourier sparsity by a constant factor, so the function must
become constant in $O(\log|\mathcal{S}|)$ rounds. This implies the strong
upper bound of

$\operatorname{\mathrm{PDT}}(f)\leq O\left(\log|\mathcal{S}|\right).$

However, O’Donnell, Wright, Zhao, Sun, and Tan [OWZ+14] constructed a function
with communication complexity $\Omega(\log(|\mathcal{S}|)^{\log_{3}(6)})$;
hence one can not take $K$ to be a constant. However, to prove the log-rank
conjecture, taking $K=O(\operatorname{poly}\log(|\mathcal{S}|))$ suffices, and
this choice of $K$ remained plausible up to date. Such an approach is
mentioned in both [TWXZ13] and [MS20], and a similar approach was used to
verify the log-rank conjecture for many cases of functions lifted with AND
(rather than XOR) gadgets [KLMY21]. We strongly refute this conjecture.

######  Theorem 1.3.

For infinitely many $n$, there is a function
$f:\mathbb{F}_{2}^{n}\to\\{-1,1\\}$ such that for
$\mathcal{S}=\mathrm{supp}(\widehat{f})$, it holds

$|(\mathcal{S}+\gamma_{1})\cap(\mathcal{S}+\gamma_{2})|\leq
O\left(|\mathcal{S}|^{5/6}\right)$

for all distinct $\gamma_{1},\gamma_{2}\in\mathbb{F}_{2}^{n}$.

######  Remark 1.4.

Observe that this theorem implies the greedy method cannot obtain a bound
better than
$\operatorname{\mathrm{PDT}}(f)=\widetilde{O}(|\mathcal{S}|^{1/6})$. In fact,
a more careful analysis can rule out bounds better than
$\operatorname{\mathrm{PDT}}(f)=\widetilde{O}(|\mathcal{S}|^{1/5})$ (see
Remark 2.7).

The functions used in Theorem 1.3 are a variant of the addressing function
using disjoint (affine) subspaces. While we believe the specific construction
is novel, the concept of using functions defined with disjoint subspaces has
previously appeared in the literature in this context. Most notably,
Chattopadhyay, Garg, and Sherif used XOR functions based on this idea in the
pursuit of stronger counterexamples to a more general version of the log-rank
conjecture [CGS21].

###  1.3 Refuting a randomized approach

Rather than simply looking for a large folding direction, a recent work of
Mande and Sanyal [MS20] attempts to address 1.2 through a deeper understanding
of the additive structure of the spectrum of boolean functions. They showed
the following conjecture on the number of nontrivial folding directions yields
a polynomial improvement to the state-of-the-art upper bound for the XOR log-
rank conjecture via a randomized approach.

######  Conjecture 1.5 ([MS20]).

There are constants $\alpha,\beta\in(0,1)$ such that for every boolean
function $f:\mathbb{F}_{2}^{n}\to\\{-1,1\\}$, for
$\mathcal{S}=\mathrm{supp}(\widehat{f})$, it holds

$\Pr_{\gamma_{1},\gamma_{2}\in\mathcal{S}}\left[|(\mathcal{S}+\gamma_{1})\cap(\mathcal{S}+\gamma_{2})|>|\mathcal{S}|^{\beta}\right]\geq\alpha.$

In fact, Mande and Sanyal conjectured that one can take
$\beta=\frac{1}{2}-o(1)$. The conjecture might seem plausible given the
numerous results on the additive structure of the spectrum of boolean
functions. However, we strongly refute it, as well:

######  Theorem 1.6.

For any constant $c>0$ and infinitely many $n$, there is a function
$f:\mathbb{F}_{2}^{n}\to\\{-1,1\\}$ such that for
$\mathcal{S}=\mathrm{supp}(\widehat{f})$, it holds

$\Pr_{\gamma_{1},\gamma_{2}\in\mathcal{S}}\left[|(\mathcal{S}+\gamma_{1})\cap(\mathcal{S}+\gamma_{2})|>c\right]=o(1).$

#### Overview

We prove more precise versions of Theorem 1.3 in Section 2 and Theorem 1.6 in
Section 3.

##  2 One excellent folding direction

A large folding direction implies the existence of a parity query whose answer
substantially simplifies the resulting restricted function. This suggests the
following greedy approach to resolve the XOR log-rank conjecture: if we can
always find distinct $\gamma_{1},\gamma_{2}$ such that
$|(\mathcal{S}+\gamma_{1})\cap(S+\gamma_{2})|\geq\Omega(|\mathcal{S}|\>/\operatorname{polylog}(|\mathcal{S}|))$,
then querying $\gamma_{1}+\gamma_{2}$ and recursing on the appropriate
restriction of $f$ will force $f$ to be constant in
$\operatorname{polylog}(|\mathcal{S}|)$ rounds.

We refute this strategy by proving a precise version of Theorem 1.3.

######  Theorem 2.1.

For $n=2^{k}+7k$ with $k\in\mathbb{N}^{\geq 3}$, there is a function
$f:\mathbb{F}_{2}^{n}\to\\{-1,1\\}$ such that for
$\mathcal{S}=\mathrm{supp}(\widehat{f})$, it holds $|\mathcal{S}|\geq 2^{6k}$,
and yet $|(\mathcal{S}+\gamma_{1})\cap(\mathcal{S}+\gamma_{2})|\leq 2^{5k+4}$
for all distinct $\gamma_{1},\gamma_{2}\in\mathbb{F}_{2}^{n}$.

Our construction has the following form.

######  Example 2.2 (Subspace addressing).

Let $A_{1},\ldots,A_{2^{k}}\subset\mathbb{F}_{2}^{7k}$ be disjoint affine
subspaces of dimension $2k$. Define $f:\mathbb{F}_{2}^{7k+2^{k}}\to\\{-1,1\\}$
by

$f(x,y)=\begin{cases}(-1)^{y_{i}}&x\in A_{i}\\\ 1&x\not\in A_{1}\cup\cdots\cup
A_{2^{k}}\end{cases},$

where $x\in\mathbb{F}_{2}^{7k}$ and $y\in\mathbb{F}_{2}^{2^{k}}$.

We choose $A_{i}$’s randomly and show that the resulting function $f$ has the
suitable properties we need with high probability. Let $V^{\perp}=\\{w:\langle
w,v\rangle=0\text{ for all }v\in V\\}$ be the orthogonal complement of a
subspace $V$.

######  Lemma 2.3.

Suppose the random function $f$ is constructed by picking random affine
subspaces $A_{1},\cdots,A_{2^{k}}\subset\mathbb{F}_{2}^{7k}$ as follows: for
each $i\in[2^{k}]$, choose vectors
$a_{i},v_{i}^{1},\cdots,v_{i}^{2k}\in\mathbb{F}_{2}^{7k}$ uniformly and
independently, and let $V_{i}=\langle v_{i}^{1},\cdots,v_{i}^{2k}\rangle$ and
$A_{i}=V_{i}+a_{i}$. Then with probability $1-2^{-k+2}$, all of the following
hold:

  1. (a)

$\forall i$, $\dim(V_{i})=2k$.

  2. (b)

$\forall i\neq j$, $A_{i}\cap A_{j}=\emptyset$.

  3. (c)

$\forall i\neq j$, $V_{i}\cap V_{j}=\\{0\\}$.

  4. (d)

For all nonzero $v\in\mathbb{F}_{2}^{7k}$, $|\\{i:v\in V_{i}^{\perp}\\}|\leq
7$.

###### Proof.

For brevity, let $m=7k$.

  1. (a)

Fix $i\in[2^{k}]$. The probability that vectors $v_{i}^{1},\cdots,v_{i}^{2k}$
are linearly independent is at least

$\frac{2^{m}-1}{2^{m}}\cdot\frac{2^{m}-2}{2^{m}}\cdot\frac{2^{m}-2^{2}}{2^{m}}\cdot\cdots\cdot\frac{2^{m}-2^{2k-1}}{2^{m}}\geq(1-2^{2k-m})^{m}\geq
1-m2^{2k-m}.$

Hence the probability that there is $i\in[2^{k}]$ for which
$v_{i}^{1},\cdots,v_{i}^{2k}$ are not linearly independent is at most
$m2^{3k-m}=7k2^{-4k}\leq 2^{-k}$.

  2. (b)

Fix $i\neq j$. The probability that $A_{i}\cap A_{j}\neq\emptyset$ is at most
$2^{2k}2^{2k-m}=2^{4k-m}$. Hence, the probability that there are $i\neq j$
with $A_{i}\cap A_{j}\neq\emptyset$ is at most $2^{2k}2^{4k-m}=2^{-k}$.

  3. (c)

Fix $i\neq j$. The probability that $V_{i}\cap V_{j}\neq\\{0\\}$ is at most
$(2^{2k}-1)2^{2k-m}\leq 2^{4k-m}$. Hence, the probability that there are
$i\neq j$ with $V_{i}\cap V_{j}\neq\emptyset$ is at most
$2^{2k}2^{4k-m}=2^{-k}$.

  4. (d)

The probability that a fixed nonzero vector $v\in\mathbb{F}_{2}^{7k}$ is
orthogonal to at least $t$ subspaces among $V_{1},\cdots,V_{2^{k}}$ is at most
$\binom{2^{k}}{t}2^{-2tk}\leq 2^{-tk}$. Taking $t=8$ and union bounding over
all $2^{7k}-1$ options for $v$ shows that the probability that there is $v$
for which $|\\{i:v\in V_{i}^{\perp}\\}|\geq 8$ is at most $2^{-k}$.

By the union bound, the probability that any of items (a) to (d) are not
satisfied is at most $4\cdot 2^{-k}\leq 2^{-k+2}$. ∎

We will assume from now on that $f$ is chosen randomly so that Lemma 2.3
holds, and set $\mathcal{S}=\mathrm{supp}(\widehat{f})$. It remains to prove
there is no large folding direction. First, we give a lower bound on the size
of Fourier support of $f$.

######  Claim 2.4.

$|\mathcal{S}|\geq 2^{6k}$.

###### Proof.

We can express $f$ as

$\displaystyle f(x,y)$ $\displaystyle=\mathbbm{1}_{(A_{1}\cup\cdots\cup
A_{2^{k}})^{c}}(x)+\sum_{i=1}^{2^{k}}\mathbbm{1}_{A_{i}}(x)\cdot(-1)^{y_{i}}$
$\displaystyle=1-\sum_{i=1}^{2^{k}}\mathbbm{1}_{A_{i}}(x)+\sum_{i=1}^{2^{k}}\mathbbm{1}_{A_{i}}(x)\cdot(-1)^{y_{i}}$
$\displaystyle=1+\sum_{i=1}^{2^{k}}\mathbbm{1}_{A_{i}}(x)\cdot((-1)^{y_{i}}-1).$

Note that the Fourier support of the function $\mathbbm{1}_{A_{i}}(x)$ is
$V_{i}^{\perp}\subset\mathbb{F}_{2}^{7k}$, and of
$\mathbbm{1}_{A_{i}}(x)\cdot(-1)^{y_{i}}$ is $V_{i}^{\perp}+e_{i}$, where
$e_{i}$ is the $i$-th basis vector in the standard basis for
$\mathbb{F}_{2}^{2^{k}}$ embedded in the space
$\mathbb{F}_{2}^{7k}\times\mathbb{F}_{2}^{2^{k}}$. Since the affine subspaces
$V_{i}^{\perp}+e_{i}$ are disjoint and also
$\left(V_{i}^{\perp}+e_{i}\right)\cap\left(V_{i}^{\perp}\right)=\emptyset$ the
coefficients of characters in $V_{i}^{\perp}+e_{i}$ will not be canceled.
Hence, we get that

$\bigcup_{i=1}^{2^{k}}\left(V_{i}^{\perp}+e_{i}\right)\subset\mathcal{S}$

and hence $|\mathcal{S}|\geq 2^{k}\cdot 2^{7k-2k}=2^{6k}$. ∎

We also need the following claim.

######  Claim 2.5.

Suppose $W_{1},W_{2}\subset\mathbb{F}_{2}^{n}$ are two linear subspaces such
that $W_{1}\cap W_{2}=\\{0\\}$. Then for all $x\in\mathbb{F}_{2}^{n}$,

$|W_{1}^{\perp}\cap(W_{2}^{\perp}+x)|=2^{n-\dim{W_{1}}-\dim{W_{2}}}.$

###### Proof.

Suppose $\dim(W_{1})=d_{1}$ and $\dim(W_{2})=d_{2}$. Without loss of
generality, assume that $W_{1}=\mathbb{F}_{2}^{d_{1}}\times 0^{d_{2}}\times
0^{n-d_{1}-d_{2}}$ and $W_{2}=0^{d_{1}}\times\mathbb{F}_{2}^{d_{2}}\times
0^{n-d_{1}-d_{2}}$. Note that
$W_{1}^{\perp}=0^{d_{1}}\times\mathbb{F}_{2}^{d_{2}}\times\mathbb{F}_{2}^{n-d_{1}-d_{2}}$
and $W_{2}^{\perp}=\mathbb{F}_{2}^{d_{1}}\times
0^{d_{2}}\times\mathbb{F}_{2}^{n-d_{1}-d_{2}}$. Pick an arbitrary
$x=(x_{1},x_{2},x_{3})\in\mathbb{F}_{2}^{d_{1}}\times\mathbb{F}_{2}^{d_{2}}\times\mathbb{F}_{2}^{n-d_{1}-d_{2}}$.
Then
$W_{2}^{\perp}+(x_{1},x_{2},x_{3})=\mathbb{F}_{2}^{d_{1}}\times\\{x_{2}\\}\times\mathbb{F}_{2}^{n-d_{1}-d_{2}}$
and
$W_{1}^{\perp}\cap(W_{2}^{\perp}+x)=0^{d_{1}}\times\\{x_{2}\\}\times\mathbb{F}_{2}^{n-d_{1}-d_{2}}$
has the claimed size. ∎

Finally, Theorem 2.1 follows from claim below.

######  Claim 2.6.

For all distinct $\gamma_{1},\gamma_{2}\in\mathbb{F}_{2}^{7k+2^{k}}$, we have

$|(\mathcal{S}+\gamma_{1})\cap(\mathcal{S}+\gamma_{2})|\leq 2^{5k+4}.$

###### Proof.

First, note that it suffices to prove the claim for all distinct
$\gamma_{1},\gamma_{2}\in\mathcal{S}$, since if
$s_{1}+\gamma_{1}=s_{2}+\gamma_{2}$ for $s_{1},s_{2}\in\mathcal{S}$, it must
be that $\gamma_{1}+\gamma_{2}=s_{1}+s_{2}\in\mathcal{S}+\mathcal{S}$. Pick an
arbitrary non-zero $\gamma=\gamma_{1}+\gamma_{2}$ for
$\gamma_{1},\gamma_{2}\in\mathcal{S}$. Remember that

$|(\mathcal{S}+\gamma_{1})\cap(\mathcal{S}+\gamma_{2})|=|\mathcal{S}\cap(\mathcal{S}+\gamma)|\quad\text{and}\quad\mathcal{S}\subseteq\left(\bigcup_{i=1}^{2^{k}}V_{i}^{\perp}\right)\cup\left(\bigcup_{i=1}^{2^{k}}(V_{i}^{\perp}+e_{i})\right).$

Hence $\mathcal{S}\cap(\mathcal{S}+\gamma)\subseteq A\cup B\cup C$, where

$\displaystyle A$
$\displaystyle=\bigcup_{i,j}\left(V_{i}^{\perp}\cap(V_{j}^{\perp}+\gamma)\right)$
$\displaystyle B$
$\displaystyle=\bigcup_{i,j}\left(V_{i}^{\perp}\cap(V_{j}^{\perp}+e_{j}+\gamma)\right)$
$\displaystyle C$
$\displaystyle=\bigcup_{i,j}\left((V_{i}^{\perp}+e_{i})\cap(V_{j}^{\perp}+e_{j}+\gamma)\right).$

Let $|\cdot|$ denote the Hamming weight of a vector. Decompose
$\gamma=(\gamma_{x},\gamma_{y})$ where $\gamma_{x}\in\mathbb{F}_{2}^{7k}$ and
$\gamma_{y}\in\mathbb{F}_{2}^{2^{k}}$. Observe that $|\gamma_{y}|\leq 2$,
since (as noted above) we may assume $\gamma\in\mathcal{S}+\mathcal{S}$
without loss of generality.

  * Case 1:

$|\gamma_{y}|=0$.

Note that in this case $B=\emptyset$ and
$C=\bigcup_{i}\left((V_{i}^{\perp}+e_{i})\cap(V_{i}^{\perp}+e_{i}+\gamma_{x})\right)$.
Overall, we get

$\displaystyle|\mathcal{S}\cap(\mathcal{S}+\gamma_{x})|$
$\displaystyle\leq\left|\bigcup_{i,j}\left(V_{i}^{\perp}\cap(V_{j}^{\perp}+\gamma_{x})\right)\right|+\left|\bigcup_{i}\left((V_{i}^{\perp}+e_{i})\cap(V_{i}^{\perp}+e_{i}+\gamma_{x})\right)\right|$
$\displaystyle=\left|\bigcup_{i,j}\left(V_{i}^{\perp}\cap(V_{j}^{\perp}+\gamma_{x})\right)\right|+\left|\bigcup_{i}\left(V_{i}^{\perp}\cap(V_{i}^{\perp}+\gamma_{x})\right)\right|$
$\displaystyle\leq\sum_{i\neq
j}|V_{i}^{\perp}\cap(V_{j}^{\perp}+\gamma_{x})|+2\sum_{i}|V_{i}^{\perp}\cap(V_{i}^{\perp}+\gamma_{x})|$
$\displaystyle\leq\sum_{i\neq
j}|V_{i}^{\perp}\cap(V_{j}^{\perp}+\gamma_{x})|+2\cdot
2^{5k}\cdot|\\{i:\gamma_{x}\in V_{i}^{\perp}\\}|$

To bound the first term, note that $V_{i}\cap V_{j}=\\{0\\}$ for all $i\neq j$
(by item (c) of Lemma 2.3). Using 2.5 we have that
$|V_{i}^{\perp}\cap(V_{j}^{\perp}+\gamma_{x})|=2^{7k-\dim(V_{i})-\dim(V_{j})}=2^{7k-2k-2k}=2^{3k}$.

To bound the second term, by item (d) of Lemma 2.3, we have that
$|\\{i:\gamma_{x}\in V_{i}^{\perp}\\}|\leq 7$. Overall, we get that

$|\mathcal{S}\cap(\mathcal{S}+\gamma)|\leq 2^{2k}\cdot 2^{3k}+7\cdot
2^{5k+1}\leq 2^{5k+4}.$

  * Case 2:

$|\gamma_{y}|=1$. Suppose $\gamma_{y}=e_{i}$ for some $i$.

In this case, $A=C=\emptyset$ and
$B=V_{i}^{\perp}\cap(V_{i}^{\perp}+e_{i}+\gamma_{y})$. Hence,

$|\mathcal{S}\cap(\mathcal{S}+\gamma)|\leq|V_{i}^{\perp}\cap(V_{i}^{\perp}+e_{i}+\gamma_{y})|\leq|V_{i}^{\perp}|=2^{5k},$

  * Case 3:

$|\gamma_{y}|=2$. This is similar to Case 2. ∎

######  Remark 2.7.

We have chosen parameters for simplicity of exhibition; however, by choosing
the original disjoint affine subspaces from
$\mathbb{F}_{2}^{(6+\varepsilon)k}$ rather than $\mathbb{F}_{2}^{7k}$, a
similar analysis rules out any bounds stronger than
$\operatorname{\mathrm{PDT}}(f)=\widetilde{O}(|\mathcal{S}|^{1/5})$ resulting
from this greedy method.

##  3 Many good folding directions

Rather than hoping for one large folding direction, [MS20] sought many
nontrivial ones. In this section, we refute their conjecture (1.5) with the
following quantified version of Theorem 1.6.

######  Theorem 3.1.

For $n=2^{d}-1$ with $d\in\mathbb{N}$, there is a function
$f:\mathbb{F}_{2}^{n}\to\\{-1,1\\}$ such that for
$\mathcal{S}=\mathrm{supp}(\widehat{f})$, it holds

$\Pr_{\gamma_{1},\gamma_{2}\in\mathcal{S}}\left[\left|(\mathcal{S}+\gamma_{1})\cap(\mathcal{S}+\gamma_{2})\right|\geq
2^{k+2}\right]\leq 2^{-k}+2^{1-d}\qquad\forall k\geq 1.$

Let $T$ be a full binary decision tree of depth $d$. There are $n=2^{d}-1$
internal nodes indexed by $[2^{d}-1]$, where we query (distinct) $x_{i}$ at
node $i$. Each of the largest depth internal nodes $v$ is adjacent to two
leaves: -1 and 1, corresponding to $v=0$ and $v=1$, respectively. Let
$f:\mathbb{F}_{2}^{n}\to\\{-1,1\\}$ be the resulting function. For example,
the following decision tree corresponds to $f$ for $n=7$.

for tree= grow=south, circle, draw, minimum size=3ex, inner sep=1pt, s sep=7mm
[$x_{1}$ [$x_{2}$, edge label=node[midway,above,font=]0 [$x_{4}$ [-1] [1] ]
[$x_{5}$ [-1] [1] ] ] [$x_{3}$, edge label=node[midway,above,font=]1  [$x_{6}$
[-1] [1] ] [$x_{7}$ [-1] [1] ] ] ]

Suppose the leaves are indexed by $[2^{d}]$. Then $f$ can be written as

$\sum_{i\in[2^{d}]}\mathrm{sign}(L_{i})\cdot\mathbbm{1}_{L_{i}},$ (1)

where $\mathbbm{1}_{L_{i}}$ denotes the indicator function of the inputs that
result in leaf $i$, and $\mathrm{sign}(L_{i})\in\\{-1,1\\}$ is the output at
leaf $i$. Let $P_{i}$ be the ordered set of coordinates that are queried to
reach the leaf $i$. Then for input
$x=(x_{1},\ldots,x_{n})\in\mathbb{F}_{2}^{n}$, we can write

$\mathbbm{1}_{L_{i}}(x)=\prod_{t\in
P_{i}}\left(\frac{1+(-1)^{a_{t}+x_{t}}}{2}\right)=\frac{1}{2^{d}}\left(\sum_{P\subseteq
P_{i}}(-1)^{\sum_{j\in P}a_{j}}\cdot(-1)^{\sum_{j\in P}x_{j}}\right),$

where $a_{t}\in\mathbb{F}_{2}$ is the output of node $t$ on the path $P_{i}$.

To find the Fourier support $\mathcal{S}=\mathrm{supp}(\widehat{f})$, it
remains to determine which terms “survive” cancellation in Equation (1). Let
$\mathcal{N}(i)$ be the index of the internal node adjacent to leaf $i$.
Observe that when $\mathcal{N}(i)=\mathcal{N}(j)$ for $i\neq j$ (so
$\mathrm{sign}(L_{i})=-\mathrm{sign}(L_{j})$),

$\displaystyle
2^{d}(\mathrm{sign}(L_{i})\cdot\mathbbm{1}_{L_{i}}(x)+\mathrm{sign}(L_{j})\cdot\mathbbm{1}_{L_{j}}(x))$
$\displaystyle=\mathrm{sign}(L_{i})\sum_{P\subseteq P_{i}}(-1)^{\sum_{t\in
P}a_{t}}\cdot(-1)^{\sum_{t\in P}x_{t}}$
$\displaystyle\qquad-\mathrm{sign}(L_{i})\sum_{P\subseteq
P_{j}}(-1)^{\sum_{t\in P}a_{t}}\cdot(-1)^{\sum_{t\in P}x_{t}}$
$\displaystyle=2\cdot\mathrm{sign}(L_{i})\cdot\sum_{P\subseteq
P_{i},\>\mathcal{N}(i)\in P}(-1)^{\sum_{t\in P}a_{t}}\cdot(-1)^{\sum_{t\in
P}x_{t}},$

since $x_{\mathcal{N}(i)}$ is the only $x$ value that $P_{i}$ and $P_{j}$
disagree on. That is, each term in $f$’s expansion must contain
$\mathcal{N}(i)$ for some $i$. Moreover, once these cancellations are made,
$\mathbbm{1}_{L_{i}}$ does not interact with $\mathbbm{1}_{L_{j}}$ for
$\mathcal{N}(i)\neq\mathcal{N}(j)$, since no term can contain both
$\mathcal{N}(i)$ and $\mathcal{N}(j)$. In summary,

$\mathcal{S}=\bigcup_{i\in[2^{d}]}\\{s:s\subseteq P_{i}\text{ and
}\mathcal{N}(i)\in s\\}.$

Let $\gamma_{1},\gamma_{2}\in\mathcal{S}$. By our observation on the structure
of $\mathcal{S}$, they have the form
$\gamma_{1}=\alpha_{1}\dot{\cup}\\{\mathcal{N}(i)\\},\gamma_{2}=\alpha_{2}\dot{\cup}\\{\mathcal{N}(j)\\}$
for some $i,j\in[2^{d}]$. We are interested in the number of pairs
$(\beta_{1},\beta_{2})\in\mathcal{S}\times\mathcal{S}$ such that
$\gamma_{1}+\gamma_{2}=\beta_{1}+\beta_{2}$. It will suffice to focus on the
setting $\mathcal{N}(i)\neq\mathcal{N}(j)$ since this occurs with overwhelming
probability. In this case, the quantity
$|(\mathcal{S}+\gamma_{1})\cap(\mathcal{S}+\gamma_{2})|$ depends only on the
depth of the lowest common ancestor of $P_{i}$ and $P_{j}$.

######  Claim 3.2.

If $|(\mathcal{S}+\gamma_{1})\cap(\mathcal{S}+\gamma_{2})|\geq 2^{k+2}$, then
the lowest common ancestor of $P_{i}$ and $P_{j}$ is at depth at least $k$.

###### Proof.

We will show the contra-positive. Suppose the lowest common ancestor $a$ of
$P_{i}$ and $P_{j}$ is at depth $\ell<k$, and suppose
$\beta_{1},\beta_{2}\in\mathcal{S}$ satisfy
$\beta_{1}+\gamma_{1}=\beta_{2}+\gamma_{2}$. Without loss of generality,
assume $\mathcal{N}(i)\in\beta_{1}$ and $\mathcal{N}(j)\in\beta_{2}$. Then
$\beta_{1}$ and $\beta_{2}$ must be a subset of the elements in the paths
$P_{i}$ and $P_{j}$, respectively.

First, consider each element $E\in P_{i}\cap P_{j}$, which is all those above
(and including) $a$. If $E\in\gamma_{1}+\gamma_{2}$, then
$E\in\beta_{1}+\beta_{2}$ only if $E$ is in precisely one of
$\beta_{1},\beta_{2}$. Likewise, if $E\not\in\gamma_{1}+\gamma_{2}$, then
$E\not\in\beta_{1}+\beta_{2}$ only if $E$ is in neither or both of
$\beta_{1},\beta_{2}$. In either case, we have two options for each $E$.

Now consider each element $E\in P_{i}$ below $a$. By assumption, $E\not\in
P_{j}$. Thus, if $E\in\gamma_{1}+\gamma_{2}$, it must be that $E\in\gamma_{1}$
and $E\not\in\gamma_{2}$. For $\beta_{1}+\beta_{2}$ to contain $E$, we must
likewise have $E\in\beta_{1}$ and $E\not\in\beta_{2}$. Similarly, if
$E\not\in\gamma_{1}+\gamma_{2}$, it cannot be in $\gamma_{1}$ or $\gamma_{2}$.
Thus, it is not in $\beta_{1}$ or $\beta_{2}$ either. An identical argument
for $E\in P_{j}$ shows that we only have one way to account for elements in
the paths $P_{i}$ or $P_{j}$ below $a$.

Doubling to compensate for the cases where $\mathcal{N}(j)\in\beta_{1}$ and
$\mathcal{N}(i)\in\beta_{2}$, we find the number of options for
$(\beta_{1},\beta_{2})\in\mathcal{S}\times\mathcal{S}$ such that
$\beta_{1}+\gamma_{1}=\beta_{2}+\gamma_{2}$ is at most $2^{\ell+2}<2^{k+2}$. ∎

Theorem 3.1 follows quickly from the claim. The probability that $P_{i}$ and
$P_{j}$ have a common ancestor at depth at least $k$ is at most $2^{-k}$, so

$\displaystyle\quad\,\Pr_{\gamma_{1},\gamma_{2}\in\mathcal{S}}\left[\left|(\mathcal{S}+\gamma_{1})\cap(\mathcal{S}+\gamma_{2})\right|\geq
2^{k+2}\right]$
$\displaystyle\leq\Pr_{\gamma_{1},\gamma_{2}\in\mathcal{S}}\left[\left|(\mathcal{S}+\gamma_{1})\cap(\mathcal{S}+\gamma_{2})\right|\geq
2^{k+2}\>\middle|\>\mathcal{N}(\gamma_{1})\neq\mathcal{N}(\gamma_{2})\right]+2^{1-d}$
$\displaystyle\leq 2^{-k}+2^{1-d},$

where we overload notation by letting
$\mathcal{N}(\gamma)=\mathcal{N}(i)\in\gamma$.

##  4 Acknowledgements

This work was done in part while the authors were visiting the Simons
Institute for the Theory of Computing. A.O. thanks Daniel M. Kane for a number
of helpful discussions. We also thank anonymous reviewers for useful comments
on an earlier version of this manuscript.

## References

  * [CGS21] Arkadev Chattopadhyay, Ankit Garg, and Suhail Sherif, _Towards stronger counterexamples to the log-approximate-rank conjecture_ , Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2021, pp. 175–190.
  * [HHL18] Hamed Hatami, Kaave Hosseini, and Shachar Lovett, _Structure of protocols for XOR functions_ , SIAM Journal on Computing 47 (2018), no. 1, 208–217.
  * [KLMY21] Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan, _Log-rank and lifting for AND-functions_ , Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), 2021, pp. 197–208.
  * [Lov16] Shachar Lovett, _Communication is bounded by root of rank_ , Journal of the ACM (JACM) 63 (2016), no. 1, 1–9.
  * [LS93] László Lovász and Michael Saks, _Communication complexity and combinatorial lattice theory_ , Journal of Computer and System Sciences 47 (1993), no. 2, 322–349.
  * [MO09] Ashley Montanaro and Tobias Osborne, _On the communication complexity of XOR functions_ , arXiv preprint arXiv:0909.3392 (2009).
  * [MS82] Kurt Mehlhorn and Erik M Schmidt, _Las Vegas is better than determinism in VLSI and distributed computing_ , Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing (STOC), 1982, pp. 330–337.
  * [MS20] Nikhil S Mande and Swagato Sanyal, _On parity decision trees for Fourier-sparse boolean functions_ , 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [OWZ+14] Ryan O’Donnell, John Wright, Yu Zhao, Xiaorui Sun, and Li-Yang Tan, _A composition theorem for parity kill number_ , 2014 IEEE 29th Conference on Computational Complexity (CCC), IEEE, 2014, pp. 144–154.
  * [ST23] Benny Sudakov and István Tomon, _Matrix discrepancy and the log-rank conjecture_ , 2023.
  * [STV14] Amir Shpilka, Avishay Tal, and Ben Lee Volk, _On the structure of boolean functions with small spectral norm_ , Proceedings of the 5th Conference on Innovations in Theoretical Computer Science (ITCS), 2014, pp. 37–48.
  * [TWXZ13] Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang, _Fourier sparsity, spectral norm, and the log-rank conjecture_ , 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2013, pp. 658–667.
  * [ZS10] Zhiqiang Zhang and Yaoyun Shi, _On the parity complexity measures of boolean functions_ , Theoretical Computer Science 411 (2010), no. 26-28, 2612–2618.