# Testing and Learning Convex Sets in the Ternary Hypercube111This paper is an
updated and significantly expanded version of an earlier preprint [BBH23].

Hadley Black
University of California, Los Angeles
<EMAIL_ADDRESS>Supported by NSF award AF:Small 2007682, NSF Award:
Collaborative Research Encore 2217033 Eric Blais
University of Waterloo
<EMAIL_ADDRESS>Supported by an Ontario Early Researcher Award and an
NSERC Discovery grant. Nathaniel Harms
EPFL
<EMAIL_ADDRESS>Some of this work was done while the author was a
student at the University of Waterloo. Partly supported by an NSERC Graduate
Scholarship, an NSERC Postdoctoral Fellowship, and the Swiss State Secretariat
for Education, Research and Innovation (SERI) under contract number
MB22.00026.

###### Abstract

We study the problems of testing and learning high-dimensional discrete convex
sets. The simplest high-dimensional discrete domain where convexity is a non-
trivial property is the _ternary hypercube_ , $\\{-1,0,1\\}^{n}$. The goal of
this work is to understand structural combinatorial properties of convex sets
in this domain and to determine the complexity of the testing and learning
problems. We obtain the following results.

_Structural:_ We prove nearly tight bounds on the edge boundary of convex sets
in $\\{0,\pm 1\\}^{n}$, showing that the maximum edge boundary of a convex set
is $\widetilde{\Theta}(n^{3/4})\cdot 3^{n}$, or equivalently that every convex
set has influence $\widetilde{O}(n^{3/4})$ and a convex set exists with
influence $\Omega(n^{3/4})$.

_Learning and sample-based testing:_ We prove upper and lower bounds of
$3^{\widetilde{O}(n^{3/4})}$ and $3^{\Omega(\sqrt{n})}$ for the task of
learning convex sets under the uniform distribution from random examples. The
analysis of the learning algorithm relies on our upper bound on the influence.
Both the upper and lower bound also hold for the problem of _sample-based
testing_ with two-sided error. For sample-based testing with one-sided error
we show that the sample-complexity is $3^{\Theta(n)}$.

_Testing with queries:_ We prove nearly matching upper and lower bounds of
$3^{\widetilde{\Theta}(\sqrt{n})}$ for one-sided error testing of convex sets
with _non-adaptive queries_.

###### Contents

  1. 1 Introduction
    1. 1.1 Results
      1. 1.1.1 The Edge Boundary and Influence of Convex Sets
      2. 1.1.2 Sample-Based Learning and Testing
      3. 1.1.3 Non-Adaptive One-Sided Testing
    2. 1.2 Techniques
      1. 1.2.1 The Edge Boundary and Influence of Convex Sets
      2. 1.2.2 Sample-Based Learning and Testing
      3. 1.2.3 Non-Adaptive One-Sided Testing
    3. 1.3 Discussion and Open Problems
  2. 2 Convexity on the Ternary Hypercube
    1. 2.1 The Outward-Oriented Poset
    2. 2.2 Convexity and Witnesses of Non-Convexity
    3. 2.3 Concentration of Mass in the Ternary Hypercube
  3. 3 The Influence of Convex Sets
    1. 3.1 Upper Bound
      1. 3.1.1 One-Dimensional Random Walks and the Max-Walk
      2. 3.1.2 Upper Bound on the Number of Influential Edges of a Convex Set
      3. 3.1.3 Crossing Bound for the Max-Walk: Proof of Lemma 3.5
    2. 3.2 Lower Bound
      1. 3.2.1 A Convex Set with Large Influence
      2. 3.2.2 Bounding the Density Increment of Halfspaces: Proof of Lemma 3.16
  4. 4 Sample-Based Testing and Learning
    1. 4.1 Upper Bound
      1. 4.1.1 Fourier Analysis Setup over the Ternary Hypercube
      2. 4.1.2 Fourier Concentration for Convex Sets
      3. 4.1.3 Low-Degree Learning Algorithm and Proof of Theorem 1.5
    2. 4.2 Lower Bound
      1. 4.2.1 The Distributions $\mathcal{D}_{\mathsf{yes}}$ and $\mathcal{D}_{\mathsf{no}}$
      2. 4.2.2 Sets Drawn from $\mathcal{D}_{\mathsf{no}}$ are Far from Convex: Proof of Lemma 4.12
      3. 4.2.3 $\mathcal{D}_{\mathsf{yes}}$ and $\mathcal{D}_{\mathsf{no}}$ are Hard to Distinguish: Proof of Lemma 4.13
  5. 5 One-Sided Error Testing
    1. 5.1 Non-Adaptive Upper Bound
    2. 5.2 Non-Adaptive Lower Bound
      1. 5.2.1 Proof of the Lower Bound
      2. 5.2.2 Truncated Anti-slabs are Far from Convex
    3. 5.3 Sample-Based Lower Bound
  6. A Approximating Binomial Coefficients Near the Middle
    1. A.1 Proof of Theorem A.1
  7. B Testing by Learning

##  1 Introduction

A subset $S\subseteq[m]^{n}$ of the hypergrid is _discrete convex_ if it is
the intersection of a convex set $C\subseteq\mathbb{R}^{n}$ with the grid,
$S=C\cap[m]^{n}$, or equivalently if $S=[m]^{n}\cap\mathsf{Conv}(S)$ where
$\mathsf{Conv}(S)$ is the convex hull of $S$. Discrete convex sets may not
even be _connected_ (see Figure 1), which, along with some of their other
unpleasant features, makes them difficult to handle algorithmically and
analytically, the most famous example being the difference between linear
programming and integer linear programming.

We are interested in testing and learning discrete convex sets. A learning
algorithm should output an approximation of an unknown convex set $S$ by using
membership queries to $S$, while a testing algorithm should decide whether an
unknown set $S$ is either convex or $\epsilon$-_far_ from convex, meaning that
$\mathsf{dist}(S,T)>\epsilon$ for all convex sets $T$, where
$\mathsf{dist}(S,T)$ is the measure of the symmetric difference.

Convexity is particularly interesting for property testing because it can be
defined by a local condition: a set $S\subseteq\mathbb{R}^{n}$ is convex if
and only if for every 3 colinear points $x,y,z$, if $x,z\in S$ then $y\in S$.
This means that, to certify the non-convexity of a (continuous) set, it
suffices to provide 3 colinear points that violate this condition. Speaking
informally, property testing results, especially testing with _one-sided
error_ , are statements about the difficulty of finding such a certificate of
non-membership to the property, when the object $S$ is $\epsilon$-far from
satisfying the property. But, the fact that convexity is _defined_ by a local
condition does not make it easy to find violations of the condition when a set
is far from convex. This is particularly evident for _discrete_ convex sets
where, unlike continuous sets, there may not be _any_ lines which witness non-
convexity, and one must instead look for up to $n+1$ points that violate
Carathéodory’s theorem.

We are aware of no non-trivial algorithms for testing or learning discrete
convex sets in high dimensional grids $[m]^{d}$ when $m$ is small. Prior works
on testing and learning convex sets include:

  1. 1.

The analysis of convexity testers, such as the _line tester_ and more general
_convex hull testers_ , which are designed to simply “spot-check” for
violations of the local conditions that define convexity in $\mathbb{R}^{n}$
[RV04, BB20]. These works show that these spot-checkers are not very
efficient, requiring $2^{\Omega(n)}$ queries to detect sets that are
$\Omega(1)$-far from convex.

  2. 2.

Testing or learning convex sets in two dimensions, including the continuous
square $[0,1]^{2}$ [Sch92, BMR19a] or the discrete grid $[m]^{2}$ [Ras03,
BMR19b, BMR22].

  3. 3.

Testing convexity in high dimensions with _samples_ , either in the continuous
setting [CFSS17, HY22] or discrete setting [HY22], and learning convex sets
from random examples of the set [RG09] or from Gaussian samples [KOS08].

When $m\gg\operatorname{poly}(d)$, a “downsampling” or “gridding” approach can
reduce to the case $m=\operatorname{poly}(d)$ [CFSS17, HY22], but once $m$ is
small the only known algorithm for testing or learning is brute-force. So let
us see what happens when we make $m$ as small as possible. When $m=2$, testing
and learning convex sets in $[m]^{n}\equiv\\{0,1\\}^{n}$ is trivial, because
every subset of $\\{0,1\\}^{d}$ is convex and therefore testing is as easy as
possible (the tester may simply accept on every input) and learning is as hard
as possible (requiring $\Omega(2^{n})$ queries).

The story changes significantly when $m=3$, so that $[m]^{n}$ is equivalent to
the ternary hypercube $\\{0,\pm 1\\}^{n}$, where the difficulties of handling
high-dimensional discrete convex sets suddenly become evident. Although this
is the simplest domain where where high-dimensional discrete convex sets are
non-trivial, little is known about the structure of discrete convex sets on
the ternary hypercube that would help in designing testing and learning
algorithms. In this paper we will give the first results towards understanding
testing and learning discrete sets in high dimensions by focusing on the
ternary hypercube.

Figure 1: Example of a convex set in $\\{0,\pm 1\\}^{3}$. The black dots are
the set and the convex red ellipsoid contains them. Note that the set may not
be “connected” on the hypergrid.

###  1.1 Results

For two sets $S,T\subseteq\\{0,\pm 1\\}^{n}$, we define
$\mathsf{dist}(S,T)\vcentcolon=\frac{|S\Delta T|}{3^{n}}$, where $S\Delta T$
denotes the symmetric difference. A set $S\subseteq\\{0,\pm 1\\}^{n}$ is
$\varepsilon$-far from convex if for every (discrete) convex set
$T\subseteq\\{0,\pm 1\\}^{n}$, $\mathsf{dist}(S,T)\geq\varepsilon$. Given
$\varepsilon>0$, a _convexity tester_ is a randomized algorithm which is given
membership oracle access to an input $S\subseteq\\{0,\pm 1\\}^{n}$ and must
satisfy

  1. 1.

If $S$ is convex then the algorithm accepts with probability at least $2/3$.

  2. 2.

If $S$ is $\varepsilon$-far from convex then the algorithm rejects with
probability at least $2/3$.

The tester is _one-sided_ if it must accept convex sets $S$ with probability 1
instead of $2/3$. A tester is _non-adaptive_ if it chooses its set of queries
before receiving the answers to any of the queries and it is _sample-based_ if
its queries are independently and uniformly random.

A learning algorithm is given membership oracle access to a convex set
$S\subseteq\\{0,\pm 1\\}^{n}$ and must output (with probability at least
$2/3$) a set $T\subseteq\\{0,\pm 1\\}^{n}$ with
$\mathsf{dist}(S,T)<\varepsilon$; it is _proper_ if its output $T$ must be
convex.

####  1.1.1 The Edge Boundary and Influence of Convex Sets

One of the most important things to know about a set is its _edge boundary_.
The edge set of the ternary hypercube is defined as

$\displaystyle E=\left\\{(x,y)\in(\\{0,\pm
1\\}^{n})^{2}\colon\sum_{i=1}^{n}\left|x_{i}-y_{i}\right|=1\right\\}\text{.}$
(1)

Observe that $|E|=2n\cdot 3^{n-1}$. We will identify a set $S\subseteq\\{0,\pm
1\\}^{n}$ with its characteristic function and write $S(x)=1$ if $x\in S$ and
$S(x)=0$ otherwise. An edge $(x,y)$ is on the boundary of $S$ if $S(x)\neq
S(y)$. The influence of a set $S\subseteq\\{0,\pm 1\\}^{n}$ is its normalized
boundary size:

$\displaystyle\mathbb{I}(S):=\frac{1}{3^{n}}\cdot|\\{(u,v)\in E\colon S(u)\neq
S(v)\\}|=\frac{2n}{3}\cdot\mathbb{P}_{(u,v)\sim E}[S(u)\neq S(v)]\text{.}$ (2)

Before we state our results, consider some examples. Two important classes of
convex sets in $\\{0,\pm 1\\}^{n}$ are halfspaces and balls, which often have
minimal “boundary size” in various settings.

######  Example 1.1 (Halfspaces).

A halfspace is a set $H=\\{x\in\\{0,\pm 1\\}^{n}\;:\;\langle
v,x\rangle<\tau\\}$ where $v\in\mathbb{R}^{n}$ and $\tau\in\mathbb{R}$. To
maximize the influence, we want $\tau$ to be small, say $\tau=0$, and we want
$v\approx\vec{1}$. The probability that a random edge $(x,y)$ is on the
boundary is at most the probability that a uniformly random $x\sim\\{0,\pm
1\\}^{n}$ satisfies $|\langle\vec{1},x\rangle|\leq 1$, and it is not difficult
to show that this is at most $O\left(\frac{1}{\sqrt{n}}\right)$, giving an
estimate of $O(\sqrt{n})$ for the maximum influence of a halfspace.

######  Example 1.2 (Balls).

A ball is a set $B_{r}=\\{x\in\\{0,\pm 1\\}^{n}\;:\;\|x\|_{2}^{2}<r\\}$ where
$r\in\mathbb{R}$ is the radius. The average (squared) norm
$\mathbb{E}\left[\|x\|_{2}^{2}\right]$ for $x\sim\\{0,\pm 1\\}^{n}$ is the
same as the expected number of nonzero coordinates of $x$, which is
$\frac{2}{3}n$, so to maximize the edge boundary we think of
$r\approx\frac{2}{3}n$. Similar to above, the probability that $x\sim\\{0,\pm
1\\}^{n}$ is close enough to this threshold to find a boundary edge is
$O\left(\frac{1}{\sqrt{n}}\right)$, again giving an estimate of $O(\sqrt{n})$
for the maximum influence.

Our first result shows that there are convex sets with significantly larger
influence, which can be obtained by taking $S$ to be the intersection of
roughly $3^{\Theta(\sqrt{n})}$ random halfspaces with thresholds
$\tau=\Theta(n^{3/4})$; we think of these sets as interpolating between the
halfspaces and the ball. Our construction is inspired by [Kan14], who showed
bounds on the influence of intersections random halfspaces on the hypercube
$\\{0,1\\}^{n}$, and we note that similar constructions also achieve maximal
surface area under the Gaussian distribution on $\mathbb{R}^{n}$ [Naz03].

######  Theorem 1.3.

There exists a convex set $S\subseteq\\{0,\pm 1\\}^{n}$ with influence
$\mathbb{I}(S)=\Omega(n^{3/4})$.

Our main result on the influence of convex sets is that this construction is
essentially optimal: we show a matching upper bound (up to log factors) for
any convex set in $\\{0,\pm 1\\}^{n}$. Due to the discrete nature of the
domain, our proof of this theorem is significantly different from the previous
techniques that have been used to bound the surface area of convex sets in
continuous domains.

######  Theorem 1.4.

If $S\subseteq\\{0,\pm 1\\}^{n}$ is convex, then
$\mathbb{I}(S)=O(n^{3/4}\log^{1/4}n)$.

####  1.1.2 Sample-Based Learning and Testing

As an application of our bounds on the influence, we show using standard
Fourier analysis that any set $S\subseteq\\{0,\pm 1\\}^{n}$ can be
approximated with error $\varepsilon$ by a polynomial of degree
$\mathbb{I}(S)/\varepsilon$. Using Theorem 1.4 and the ?Low-Degree Algorithm?
of Linial, Mansour, and Nisan [LMN93] then gives us the following upper bound
for learning.

######  Theorem 1.5.

There is a uniform-distribution learning algorithm for convex sets in
$\\{0,\pm 1\\}^{n}$ which achieves error at most $\varepsilon$ with time and
sample complexity $3^{\widetilde{O}(n^{3/4}/\varepsilon)}$. The
$\widetilde{O}(\cdot)$ hides a factor of $\log^{1/4}n$.

A corollary of Theorem 1.5 is that the same upper bound on the sample
complexity holds for sample-based testing, due to the testing-by-learning
reduction (which is slightly non-standard because the learner is not _proper_
, see Appendix B).

######  Corollary 1.6.

There is a sample-based convexity tester for sets in $\\{0,\pm 1\\}^{n}$ with
sample complexity $3^{\widetilde{O}(n^{3/4}/\varepsilon)}$ where the
$\widetilde{O}(\cdot)$ hides a factor of $\log^{1/4}n$.

To complement our upper bounds, we prove also a lower bound for sample-based
testing. Here we remark that one of our motivations for studying convex sets
in $\\{0,\pm 1\\}^{n}$ is their similarity (in an informal sense) to
_monotone_ functions on $\\{0,1\\}^{n}$; an analogy between monotone functions
on $\\{0,1\\}^{n}$ and convex sets in Gaussian space was proposed in [DNS22]
and we are interested in this analogy for _discrete_ convex sets. Our lower
bound for sample-based testing discrete convex sets uses a version of
Talagrand’s random DNFs, which were used previously to prove lower bounds for
testing monotonicity on $\\{0,1\\}^{n}$ [BB16, CWX17].

######  Theorem 1.7.

For sufficiently small constant $\varepsilon>0$, every sample-based convexity
tester for sets in $\\{0,\pm 1\\}^{n}$ has sample complexity
$3^{\Omega(\sqrt{n})}$.

Again, the testing-by-learning reduction of Lemma B.1 implies that this lower
bound also holds for learning.

######  Corollary 1.8.

For sufficiently small constant $\varepsilon>0$, sample-based learning convex
sets in $\\{0,\pm 1\\}^{n}$ requires at least $3^{\Omega(\sqrt{n})}$ samples.

####  1.1.3 Non-Adaptive One-Sided Testing

A convexity tester with one-sided error is one that finds a _witness_ of non-
convexity with probability at least $2/3$ when the tested set is
$\varepsilon$-far from convex. A convexity tester is _non-adaptive_ if it must
choose its set of membership queries before receiving any of the query
results. Bounds on non-adaptive one-sided error testing therefore have a
natural combinatorial interpretation as bounds on the likelihood of blindly
finding a witness of non-convexity in a random substructure of the domain.

Our first result shows that there is a non-adaptive one-sided error tester
with sub-exponential query complexity $3^{o(n)}$. In contrast, a similar bound
for the Gaussian setting is not yet known to exist.

######  Theorem 1.9.

For every $\varepsilon>0$, there is a non-adaptive convexity tester with one-
sided error for sets in $\\{0,\pm 1\\}^{n}$ that has query complexity
$3^{\widetilde{O}\big{(}\sqrt{n\ln 1/\varepsilon}\big{)}}$ where the
$\widetilde{O}(\cdot)$ notation is hiding an extra $\ln n$ term.

Next, we show that Theorem 1.9 is essentially tight, in that the exponential
dependence on $\sqrt{n}$ in its bound is unavoidable.

######  Theorem 1.10.

For sufficiently small constant $\varepsilon>0$, every non-adaptive convexity
tester with one-sided error for sets in $\\{0,\pm 1\\}^{n}$ has query
complexity at least $3^{\Omega(\sqrt{n})}$.

Our Theorem 1.7 above showed that $3^{\Omega(\sqrt{n})}$ is required for
_sample-based_ testing. For one-sided error testers, we can improve this lower
bound to show that non-adaptive testers are significantly more powerful than
sample-based testers for one-sided testing.

######  Theorem 1.11.

For sufficiently small constant $\varepsilon>0$, sample-based convexity
testing in $\\{0,\pm 1\\}^{n}$ with one-sided error requires $3^{\Theta(n)}$
samples.

This theorem also includes a matching upper bound. The upper bound in Theorem
1.11 is trivial because a coupon-collector argument shows that one can learn
any set $S\subseteq\\{0,\pm 1\\}^{n}$ exactly using $O(n3^{n})$ samples. A
slightly improved bound of
$O\left(3^{n}\cdot\tfrac{1}{\varepsilon}\log(1/\varepsilon)\right)$ also holds
by a general upper bound on one-sided error testing via the VC dimension
[BFH21].

###  1.2 Techniques

The discrete nature of the ternary hypercube, in contrast to the continuity of
the domains $\mathbb{R}^{n}$ or $[0,1]^{n}$, provides a new angle in the study
of convexity which leads to the development of a new set of _combinatorial_
techniques and tools. In this section we give a brief overview of the
techniques we use to prove each of our theorems.

####  1.2.1 The Edge Boundary and Influence of Convex Sets

##### Influence Upper Bound:

Our proof of Theorem 1.4, which gives an upper bound on the edge boundary of a
convex set, is accomplished by relating the number of boundary edges to the
expected number of sign-changes of one-dimensional random processes. This is
done by constructing a distribution $\mathcal{D}$ over the edge-set $E$ of the
ternary hypercube, such that (a) $\mathcal{D}$ is “close” to the uniform
distribution over $E$ and (b) the probability that a random edge drawn from
$\mathcal{D}$ is influential for our convex set $S\subseteq\\{0,\pm 1\\}^{n}$
is equal to the expected number of sign-changes of a certain random process.
This process is defined by considering a random walk
$\bm{X}^{(0)},\ldots,\bm{X}^{(m)}$ of length $m\approx n^{1/2}$ where
$\bm{X}^{(0)}$ is a random point from the middle layers of $\\{0,\pm 1\\}^{n}$
and each $\bm{X}^{(s)}$ is obtained by flipping a random $0$-valued bit of
$\bm{X}^{(s-1)}$ to a uniform random $\\{\pm 1\\}$-value; the process finally
draws $\bm{s}\sim[m]$ uniformly at random and outputs the edge
$(\bm{X}^{(\bm{s}-1)},\bm{X}^{(\bm{s})})$.

The crux of the argument is to bound the expected number of times this random
walk enters and leaves the set $S$. Since $S$ is convex, it can be written as
an intersection of halfspaces $S=H_{1}\cap H_{2}\cap\cdots\cap H_{k}$ of the
form $H_{i}=\\{x\in\\{0,\pm 1\\}^{n}\colon\langle
x,v^{(i)}\rangle<\tau_{i}\\}$ where $v^{(i)}\in\mathbb{R}^{n}$ and
$\tau_{i}\in\mathbb{R}$. For each halfspace $H_{i}$, we define a corresponding
one-dimensional random walk
$\bm{W}_{i}(s)=\langle\bm{X}^{(s)},v^{(i)}\rangle-\tau_{i}$ and observe that
the original random walk crosses the boundary of $H_{i}$ at step $s$ if and
only if $\bm{W}_{i}$ _changes sign_ at step $s$. Then the number of times the
walk $\bm{X}^{(0)},\bm{X}^{(1)},\dotsc$ crosses the boundary of
$S=\bigcap_{i}H_{i}$ is the number of times the _maximum_ of the processes
$\bm{M}=\max_{i}\bm{W}_{i}$ changes sign. Therefore, our goal is to bound the
expected number of sign-changes for $\bm{M}$, which we accomplish by using
Sparre Andersen’s fluctuation theorem [Spa54] (as stated in [BB23]) to relate
this quantity to the number of sign-changes of a uniform random walk.

##### High-Influence Set Construction:

Our proof of Theorem 1.3 is inspired by the proof of [Kan14, Theorem 2] which
constructs a set in the Boolean hypercube $\\{\pm 1\\}^{n}$ with influence
$\Omega(\sqrt{n\log k})$ by considering an intersection of $k$ random
halfspaces each of which is at distance $\approx\sqrt{n\log k}$ from the
origin. In particular, when $k\approx 2^{\sqrt{n}}$ the construction has
influence $\approx n^{3/4}$ and when $k\approx 2^{n}$ the set has influence
$\approx n$. On the ternary hypercube $\\{0,\pm 1\\}^{n}$, the behaviour is
different: here, halfspaces exhibit a “density increment” behaviour as their
threshold moves away from the origin, which prevents the influence from
increasing as $k$ grows past $2^{\sqrt{n}}$, when $\Omega(\sqrt{n\log k})$
matches our upper bound of $\widetilde{O}(n^{3/4})$.

We can summarize this “density increment” phenomenon as follows. Most of the
edges of $\\{0,\pm 1\\}^{n}$ occur in the middle layer $\\{x\in\\{0,\pm
1\\}^{n}:\|x\|_{1}=\tfrac{2}{3}n\pm
O(\sqrt{n})\\}=\bigcup_{\ell=-O(\sqrt{n})}^{O(\sqrt{n})}\\{x\;:\;\|x\|_{1}=\tfrac{2}{3}n+\ell\\}$.
A convex set is an intersection of halfspaces, but for convenience we consider
its complement which is a union of halfspaces, and has the same influence.
Consider the “density” or measure of the halfspace with normal vector
$\vec{1}$ at distance $\tau$ from the origin on the points
$\\{x\;:\;\|x\|_{1}=\tfrac{2n}{3}+\ell\\}$:

$\rho(\ell,\tau):=\mathbb{P}_{x\in\\{0,\pm 1\\}^{n}\colon\left\lVert
x\right\rVert_{1}=\frac{2n}{3}+\ell}\left[\sum_{i}x_{i}>\tau\right]\,.$

Suppose that there is a fixed value $\rho$ such that
$\rho(\ell,\tau)\approx\rho$ up to constant factors for _all_ $\ell=\pm
O(\sqrt{n})$ simultaneously. Then we can take $k\approx\tfrac{1}{\rho}$ random
halfspaces with threshold $\tau$ and combine their boundary edges, since they
will be essentially disjoint on the whole middle layer, and it is not hard to
show that the influence of the resulting union is roughly $\tau$. It happens
that the condition of $\rho(\ell,\tau)$ being approximately equal for all
values $\ell=\pm O(\sqrt{n})$ holds for $\tau$ up to $\tau\approx n^{3/4}$ but
for $\tau\gg n^{3/4}$ the intersection of the halfspace with the set
$\\{x\;:\;\|x\|_{1}=\frac{2n}{3}+\ell\\}$ grows extremely fast with $\ell$
making $\rho(-\sqrt{n},\tau)\ll\rho(\sqrt{n},\tau)$, and the intersection of
halfspaces with threshold $\tau$ quickly approaches the ball with influence
$O(\sqrt{n})$ (see Example 1.2).

####  1.2.2 Sample-Based Learning and Testing

##### Learning Upper Bound:

Our proof of Theorem 1.5 follows by combining our upper bound on the influence
from Theorem 1.4 with the Low-Degree Algorithm of Linial, Mansour, and Nisan
[LMN93]. In particular, using Fourier analysis over $\\{0,\pm 1\\}^{n}$ in
combination with Theorem 1.4 we can show that for convex sets, a
$(1-\varepsilon)$-fraction of the Fourier mass is on the coefficients with
degree at most $\widetilde{O}(n^{3/4})/\varepsilon$. Then we may use the Low-
Degree Algorithm for learning the convex sets; see Section 4.1.3. Since the
ternary hypercube is a non-standard domain, we state the necessary Fourier
analysis for functions over $\\{0,\pm 1\\}^{n}$ in Section 4.1.1, which
follows [O’D14, Chapter 8]. One technical difference between Fourier analysis
over the Boolean and ternary hypercubes is that the standard Fourier basis
over $\\{\pm 1\\}^{n}$ is given by the parity functions which are bounded in
$[0,1]$, whereas any Fourier basis over $\\{0,\pm 1\\}^{n}$ will have
functions taking value $2^{O(n)}$ on some elements $x\in\\{0,\pm 1\\}^{n}$.
Nevertheless, with some care, we show that the Low-Degree Algorithm still
works.

##### Sample-Based Testing Lower Bound:

Our proof of Theorem 1.7 uses a family of functions known as _Talagrand’s
random DNFs_ adapted to the ternary hypercube. As we mentioned, this family of
functions has been used to prove lower bounds for monotonicity testing [BB16,
CWX17]. Our adapted version is described as follows. Each ?term? of the DNF is
chosen to be a random point $t\in\\{0,\pm 1\\}^{n}$ with $\left\lVert
t\right\rVert_{1}=\sqrt{n}$. We then say that a point $x\in\\{0,\pm 1\\}^{n}$
?satisfies? $t$ if $x_{i}=t_{i}$ for all $i\in[n]$ where $t_{i}\in\\{\pm
1\\}$. After choosing $N$ random terms $t^{(1)},\ldots,t^{(N)}$ we define the
disjoint regions of $\\{0,\pm 1\\}^{n}$ given by $U_{1},\ldots,U_{N}$ where
$U_{i}$ is the set of points $x\in\\{0,\pm 1\\}^{n}$ with $\left\lVert
x\right\rVert_{1}\in[2n/3\pm\sqrt{n}]$ which satisfy a unique term. Choosing
$N=3^{\sqrt{n}}$ results in $\bigcup_{i=1}^{N}U_{i}$ covering a constant
fraction of the domain. We then define two distributions
$\mathcal{D}_{\mathsf{yes}}$ and $\mathcal{D}_{\mathsf{no}}$ as follows.
Recall that $B_{r}$ is the radius-$r$ ball in the ternary cube (Example 1.2)
and let $D$ denote the set of points $x\in\\{0,\pm 1\\}^{n}$ with $\left\lVert
x\right\rVert_{1}\in[2n/3\pm\sqrt{n}]$ that don’t satisfy _any_ term.

  * •

$S\sim\mathcal{D}_{\mathsf{yes}}$ is drawn by setting
$S=B_{\frac{2n}{3}-\sqrt{n}}\cup D\cup\left(\bigcup_{i\in T}U_{i}\right)$
where $T$ includes each $i\in[N]$ independently with probability $1/2$. Such a
set is always convex.

  * •

$S\sim\mathcal{D}_{\mathsf{no}}$ is drawn by setting
$S=B_{\frac{2n}{3}-\sqrt{n}}\cup D\cup C$ where $C$ includes each
$x\in\bigcup_{i=1}^{N}U_{i}$ independently with probability $1/2$. Informally,
this set will be $\Omega(1)$-far from convex with constant probability since
its intersection with the middle layers is random.

For both distributions, each point $x\in\bigcup_{i=1}^{N}U_{i}$ satisfies
$\mathbb{P}_{S}[x\in S]=1/2$ and if $x\in U_{i}$ and $y\in U_{j}$ where $i\neq
j$, then the events $x\in S$ and $y\in S$ are independent. Thus, to
distinguish $\mathcal{D}_{\mathsf{yes}}$ and $\mathcal{D}_{\mathsf{no}}$ one
has to see at least two points from the same $U_{i}$ and this gives our sample
complexity lower bound.

####  1.2.3 Non-Adaptive One-Sided Testing

The proofs of Theorems 1.9, 1.10 and 1.11 all rely on a partial order
$\preceq$ defined on $\\{0,\pm 1\\}^{n}$, which we call the _outward-oriented
poset_ , that has the origin $0^{n}$ as the minimum element and the corners of
the cube $\\{\pm 1\\}^{n}$ as the maximum elements. (See Section 2.1 for the
formal definition of this poset and a discussion of its properties and
history.) For any $y\in\\{0,\pm 1\\}^{n}$, we define
$\mathsf{Up}(y)\vcentcolon=\\{x\in\\{0,\pm 1\\}^{n}:y\preceq x\\}$ to
represent the set of points above $y$ in this poset.

##### Non-Adaptive One-Sided Upper Bound:

An important property of the outward-oriented poset in the context of testing
convexity is that any point $y$ in the convex hull of a set of points
$X\subseteq\\{0,\pm 1\\}^{n}$ is also in the convex hull of
$X\cap\mathsf{Up}(y)$. Conversely, if a set $S\subseteq\\{0,\pm 1\\}^{n}$ is
_not_ convex, then there is a certificate of non-convexity of the form $(X,y)$
where $y\notin S$ is in the convex hull of $X\subseteq S$, and
$X\subseteq\mathsf{Up}(y)$. This property implies that a convexity tester can
search for certificates of non-convexity by repeatedly choosing a random point
$y$ and querying all points in $\mathsf{Up}(y)$. A naïve implementation of
this idea leads to a query complexity that is significantly larger than the
bound in the theorem. However, the ternary hypercube satisfies a strong
concentration of measure property: almost all of the points in the ternary
hypercube have $\tfrac{2}{3}n\pm O(\sqrt{n})$ non-zero coordinates. As a
result, we can refine the convexity tester to only query the points in
$\mathsf{Up}(y)$ whose number of non-zero coordinates is at most
$\tfrac{2}{3}n+O(\sqrt{n})$ to obtain the desired query complexity. The
details of the proof of Theorem 1.9 are presented in Section 5.

##### Non-Adaptive One-Sided Lower Bound:

The lower bound in Theorem 1.10 is obtained by considering the class of _anti-
slabs_ , which are defined by choosing a vector $v\in\\{0,\pm 1\\}^{n}$ with
$n/2$ non-zero coordinates and taking the set of points $\\{x\in\\{0,\pm
1\\}^{n}:|\langle v,x\rangle|>\tau\\}$. It is quite easy to find certificates
of non-convexity for anti-slabs—the three points $-x$, $0^{n}$, and $x$
obtained by choosing $x$ uniformly at random in the ternary hypercube forms
such a certificate with reasonably large probability whenever $\tau$ is small
enough. However, we can eliminate these certificates of non-convexity if we
“truncate” the anti-slabs by including the set of points whose number of non-
zero coordinates is below $\tfrac{2}{3}n-O(\sqrt{n})$, and excluding the
points whose number of non-zero coordinates is above
$\tfrac{2}{3}n+O(\sqrt{n})$. We show that any certificate of non-convexity for
these truncated anti-slabs must have two points $x,z$ with a large difference
between $\langle v,x\rangle$ and $\langle v,z\rangle$, but on the other hand,
any small set of queries has a low probability of including such a pair when
$v$ is chosen at random.

##### Sample-Based One-Sided Lower Bound:

Finally, the proof of the lower bound Theorem 1.11 again uses the outward-
oriented poset and the connection between convex hulls and the upwards sets
$\mathsf{Up}(y)$ to show that any set of $3^{o(n)}$ samples is unlikely to
draw any point $y$ that is contained in the convex hull of the other sampled
points and thus to have any possibility of identifying a certificate of non-
convexity of any set.

###  1.3 Discussion and Open Problems

As far as we know, we are the first to study convex sets and their associated
algorithmic problems on the ternary hypercube. Thus there are many possible
questions one could ask. In this section we discuss a few such questions which
we find most interesting.

##### Learning and sample-based testing.

The most obvious question which our work leaves open is that of determining
the true sample complexity of learning and sample-based testing of convex sets
in the ternary hypercube, where our results leave a gap of
$3^{\Omega(\sqrt{n})}$ vs. $3^{\widetilde{O}(n^{3/4})}$. By Theorem 1.3, our
upper bound of $\widetilde{O}(n^{3/4})$ on the influence of convex sets is
tight up to a factor of $\log^{1/4}n$, and therefore to improve our learning
upper bound would require another method.

######  Question 1.12.

Can we close the gap of $3^{\Omega(\sqrt{n})}$ vs.
$3^{\widetilde{O}(n^{3/4})}$ for learning convex sets and for sample-based
convexity testing in $\\{0,\pm 1\\}^{n}$?

##### Testing with two-sided error.

Our results for testing with queries apply only to case of one-sided error.
Earlier work on testing convex sets under the Gaussian distribution on
$\mathbb{R}^{n}$ with samples showed that, in that setting, two-sided error
was more efficient than one-sided [CFSS17].

######  Question 1.13.

Is there a two-sided error non-adaptive tester for domain $\\{0,\pm 1\\}^{n}$
with better query complexity than our one-sided error tester?

Our lower bound technique does not suffice for two-sided error. This is
because the class of anti-slabs, which we proved are hard to distinguish from
convex sets using a one-sided tester, can be distinguished from convex sets
with _two-sided_ error using only $O(n)$ samples. To do so, one may use the
standard testing-by-learning reduction of [GGR98], together with an $O(n)$
bound on the VC dimension of the anti-slabs (which are essentially the union
of two halfspaces).

##### Testing convexity in other domains.

Our results show that queries can be more effective than samples for testing
discrete convex sets in some high-dimensional domains. Is this true for all
discrete high-dimensional domains?

######  Question 1.14.

What are the sample and query complexities for testing discrete convexity over
general hypergrids $[m]^{n}$?

Note that our techniques do not immediately generalize to larger hypergrids,
so answering the last question even for the hypergrid $\\{0,\pm 1,\pm
2\\}^{n}$ requires some new ideas.

It would also be interesting to see if the gap between sample and query
complexity also holds for continuous sets.

######  Question 1.15.

Can queries improve upon the bounds of [CFSS17, HY22] for testing convex sets
with samples in $\mathbb{R}^{n}$ under the Gaussian distribution?

It is not clear if there is a formal connection between testing convex sets on
the domain $\\{0,\pm 1\\}^{n}$ and on the domain $\mathbb{R}^{n}$ under the
standard Gaussian distribution. One might expect a connection here because the
uniform distribution on $\\{0,\pm 1\\}^{n}$ acts similarly to the Gaussian in
certain ways when $n\to\infty$. But we do not see how to construct direct
reductions between these two settings for the problem of convexity testing.
Also, there is an intriguing analogy between monotone subsets of $\\{\pm
1\\}^{n}$ and convex subsets of $\mathbb{R}^{n}$ in the Gaussian space
[DNS22]. How do convex subsets of $\\{0,\pm 1\\}^{n}$ fit into this analogy?

##  2 Convexity on the Ternary Hypercube

The main object of study in this paper is the _ternary hypercube_ , an
analogue of the Boolean hypercube over the ternary set $\\{0,\pm 1\\}^{n}$.
This set can be viewed as a discrete subset of $\mathbb{R}^{n}$, as a
(hyper)grid graph in which two points $x,y\in\\{0,\pm 1\\}^{n}$ are connected
by an edge if and only if $\sum_{i=1}^{n}|x_{i}-y_{i}|=1$, and as a poset that
we will describe in more detail in the subsection below.

The study of the ternary hypercube and more general grid graphs goes back at
least to Bollobás and Leader [BL91]. As a poset, its study goes back at least
to Metropolis and Rota [MR78]. The ternary hypercube appears to have some
particularly elegant structure that is not necessarily shared by larger
hypergrids. We describe some of these fundamental properties in the following
subsections.

###  2.1 The Outward-Oriented Poset

We define a partial order over $\\{0,\pm 1\\}^{n}$, which puts the origin
$0^{n}$ as the minimum element and the corners $\\{\pm 1\\}^{n}$ as the
maximum elements.

######  Definition 2.1 (Outward-Oriented Poset).

We denote by $(\\{0,\pm 1\\}^{n},\preceq)$ the $n$-wise product of the partial
order defined by $0\prec 1$ and $0\prec-1$. Equivalently, we write $y\preceq
x$ when $\forall i\in[n]\colon(y_{i}\neq 0\leavevmode\nobreak\
\Longrightarrow\leavevmode\nobreak\ x_{i}=y_{i})$.

The outward-oriented poset can easily be extended to a lattice (by adding a
global maximum point), though since we do not need this extension we do not
pursue it here. The outward-oriented poset appears naturally in many different
contexts and, as a result, has received different names. For instance, it
arises in the study of the faces of the Boolean hypercube [MR78], where it is
sometimes called the “cubic lattice”, and in the study of partial Boolean
functions (see, e.g., [Eng97]). We use the name “outward-oriented poset” to
emphasize the fact that this poset is distinct from the partial order
inherited from $\mathbb{R}^{n}$.

######  Definition 2.2 (Upper Shadow).

For any point $y\in\\{0,\pm 1\\}^{n}$, the _upper shadow_ of $y$ is the set

$\mathsf{Up}(y)\vcentcolon=\left\\{x\in\\{0,\pm 1\\}^{n}:y\preceq
x\right\\}\,.$

###  2.2 Convexity and Witnesses of Non-Convexity

Given a set of points $X\subseteq\\{0,\pm 1\\}^{n}$, we denote the convex hull
of $X$ by

$\mathsf{Conv}(X):=\left\\{\sum_{x\in X}\lambda_{x}x\colon\sum_{x\in
X}\lambda_{x}=1\text{ and }\lambda_{x}\geq 0\text{, }\forall x\in
X\right\\}\text{.}$

######  Definition 2.3 (Discrete Convexity).

A set $S\subseteq\\{0,\pm 1\\}$ is _convex_ if $S=\mathsf{Conv}(S)\cap\\{0,\pm
1\\}^{n}$.

Let $\Delta(S,T)$ denote the cardinality of the symmetric difference between
$S$ and $T$. Given $S\subseteq\\{0,\pm 1\\}^{n}$, we define
$\mathsf{dist}(S,\mathbf{convex})$ as the minimum, over all convex sets
$T\subseteq\\{0,\pm 1\\}^{n}$, of $\Delta(S,T)\cdot 3^{-n}$. For brevity, we
also sometimes use the notation
$\varepsilon(S):=\mathsf{dist}(S,\mathbf{convex})$. If
$\varepsilon(S)\geq\varepsilon$ for some $\varepsilon\in(0,1)$, then we say
that $S$ is $\varepsilon$-far from convex.

######  Definition 2.4 (Violating Pairs).

Consider $S\subseteq\\{0,\pm 1\\}^{n}$. If $X\subseteq S$ and
$y\in\mathsf{Conv}(X)\cap\\{0,\pm 1\\}^{n}$, but $y\notin S$, then we call
$(X,y)$ a _violating pair_ for $S$. The pair is called _minimal_ if
$y\notin\mathsf{Conv}(X^{\prime})$ for any strict subset $X^{\prime}\subset
X$.

All of our results exploit the following key property of the outward-oriented
poset. This fact captures the structure of $\\{0,\pm 1\\}^{n}$ which we use
throughout the paper.

######  Fact 2.5.

If a violating pair $(X,y)$ is minimal, then $X\subseteq\mathsf{Up}(y)$.

###### Proof.

We have $y=\sum_{x\in X}\lambda_{x}x$ where $\sum_{x\in X}\lambda_{x}=1$.
Moreover, the minimality of $(X,y)$ implies that $\lambda_{x}>0$ for all $x\in
X$. Now, let $i\in[n]$ be some coordinate where $y_{i}\neq 0$. We need to show
that $x_{i}=y_{i}$ for all $x\in X$. Without loss of generality, suppose
$y_{i}=1$. Thus, we have $1=\sum_{x\in X}\lambda_{x}x_{i}$. If $x_{i}<1$ for
some $x\in X$, then we would have $\sum_{x\in X}\lambda_{x}x_{i}<1$, which is
a contradiction. ∎

Figure 2: An illustration of $\\{0,\pm 1\\}^{2}$. Arrows indicate the
direction of the partial order. The red triangle shows the convex hull of
$X:=\\{(-1,1),(1,0),(0,1)\\}$, which contains the origin. I.e. $(X,(0,0))$ is
a minimal violating pair for $X$.

######  Fact 2.6.

Let $S\subseteq\\{0,\pm 1\\}^{n}$. The following two statements are
equivalent.

  * •

$S$ is not convex.

  * •

There exists a minimal violating pair $(X,y)$ for $S$.

###### Proof.

Suppose there exists a minimal violating pair $(X,y)$ for $S$. Since
$X\subseteq S$, we have $\mathsf{Conv}(X)\subseteq\mathsf{Conv}(S)$ and so
$y\in\mathsf{Conv}(S)$. Thus, $y\notin S$ implies $S$ is not convex. Now
suppose $S$ is not convex. Then there exists
$y\in(\mathsf{Conv}(S)\cap\\{0,\pm 1\\}^{n})\setminus S$. Let $X\subseteq S$
be a minimal set of points such that $y\in\mathsf{Conv}(X)$. The pair $(X,y)$
is a minimal violating pair for $S$. ∎

######  Fact 2.7.

Consider $S,Q\subseteq\\{0,\pm 1\\}^{n}$. If $Q$ does not contain any
$X\cup\\{y\\}$ such that $(X,y)$ is a violating pair for $S$, then there
exists a convex set $S^{\prime}$ such that $S^{\prime}\cap Q=S\cap Q$.

###### Proof.

Let $S^{\prime}=\mathsf{Conv}(S\cap Q)$ and consider an arbitrary $y\in Q$. We
need to show that $y\in S$ if and only if $y\in S^{\prime}$. Clearly, $y\in S$
implies $y\in S^{\prime}$. Now suppose $y\in S^{\prime}$ and note this implies
$y\in\mathsf{Conv}(S\cap Q)\subseteq\mathsf{Conv}(S)$. Thus, if $y\notin S$,
then $(S\cap Q,y)$ is a violating pair for $S$ and this contradicts our
assumption about $Q$. ∎

The following corollary is crucial for proving our lower bounds in Section 5.2
and Section 5.3.

######  Corollary 2.8.

Let $T$ be a convexity tester for sets $S\subseteq\\{0,\pm 1\\}^{n}$ with
$1$-sided error. Suppose $T$ rejects a set $S$ after querying a set $Q$. Then
$Q$ contains some $X\cup\\{y\\}$ such that $(X,y)$ is a minimal violating pair
for $S$.

###  2.3 Concentration of Mass in the Ternary Hypercube

For $x\in\\{0,\pm 1\\}^{n}$, observe that $\left\lVert
x\right\rVert_{1}=\left\lVert x\right\rVert_{2}^{2}$ is precisely the number
of non-zero coordinates of $x$. Moreover, each coordinate of a uniformly
random $x$ is non-zero with probability $2/3$, and so $\underset{x\in\\{0,\pm
1\\}^{n}}{\mathbb{E}}\left[\left\lVert x\right\rVert_{1}\right]=\frac{2n}{3}$.
Standard concentration inequalities yield the following bound on the number of
points $x\in\\{0,\pm 1\\}^{n}$ where $\left\lVert x\right\rVert_{1}$ is far
from this expectation.

######  Fact 2.9.

For every $\tau\geq 0$,

$\underset{x\in\\{0,\pm 1\\}^{n}}{\mathbb{P}}\left[\left|\left\lVert
x\right\rVert_{1}-\frac{2n}{3}\right|>\tau\right]\leq
2\exp(-\tau^{2}/2n)\text{.}$

###### Proof.

We have $\left\lVert x\right\rVert_{1}=\sum_{i=1}^{n}X_{i}$ where $X_{i}=1$
with probability $2/3$ and $X_{i}=0$ with probability $1/3$. Thus, the bound
follows immediately from Hoeffding’s inequality. ∎

Given $\tau\geq 0$, we use the following notation to denote the inner, middle,
and outer layers of $\\{0,\pm 1\\}^{n}$ with respect to distance $\tau$:

$\displaystyle\mathsf{Inn}(\tau):=\left\\{x\colon\left\lVert
x\right\rVert_{1}-\frac{2n}{3}<-\tau\right\\}\text{, }$
$\displaystyle\mathsf{Mid}(\tau):=\left\\{x\colon\left|\left\lVert
x\right\rVert_{1}-\frac{2n}{3}\right|\leq\tau\right\\}\text{, }$
$\displaystyle\mathsf{Out}(\tau):=\left\\{x\colon\left\lVert
x\right\rVert_{1}-\frac{2n}{3}>\tau\right\\}\text{.}$ (3)

Figure 3: This figure shows a pictorial representation of $\\{0,\pm 1\\}^{n}$
as a poset. Any vertical slice represents the set of all points with some
fixed number of non-zero coordinates, and this number is increasing from left
to right. The left-most point is the origin and the right-most points are the
vertices of the hypercube $\\{\pm 1\\}^{n}$. The outward-oriented poset goes
from left to right. The shaded blue region emanating from $y$ is the set
$\mathsf{Up}(y)$ of points above $y$ in the partial order. The set $X$
represents some minimal set of points for which $y\in\mathsf{Conv}(X)$ and
thus $y\prec x$ for all $x\in X$, by 2.5.

##  3 The Influence of Convex Sets

In this section we prove that the maximum edge boundary of convex sets in
$\\{0,\pm 1\\}^{n}$ is $\widetilde{\Theta}(n^{3/4})\cdot 3^{n}$, or
equivalently that the influence is $\widetilde{\Theta}(n^{3/4})$.

###  3.1 Upper Bound

We prove that convex sets in the ternary hypercube have influence
$\widetilde{O}(n^{3/4})$. The main idea in the proof is to relate the
influence of a convex set $S$ to the number of sign-changes in the maximum of
a set of one-dimensional random walks. The proof will consider a random walk
$\bm{X}^{(0)},\bm{X}^{(1)},\dotsc,\bm{X}^{(m)}$ starting from a random
position in the middle layer of the ternary hypercube and moving randomly
“outward” for $m=O\left(\sqrt{\frac{n}{\log n}}\right)$ steps, and count the
number of influential edges crossed near the “middle layers” by relating them
to one-dimensional random walks. We begin in Section 3.1.1 with definitions
regarding the one-dimensional random walks that we require and then in Section
3.1.2 show how they relate to the number of influential edges of $S$; finally,
in Section 3.1.3 we prove the necessary bound on the number of sign-changes of
the one-dimensional random walks.

_Notation._ In this section it will be convenient to use bold letters like
$\bm{X}$ for random variables, with the non-bold letter $X$ being reserved for
a fixed instantiation of $\bm{X}$.

####  3.1.1 One-Dimensional Random Walks and the Max-Walk

Let us define the types of one-dimensional random walks that will be necessary
for our proof.

######  Definition 3.1 (Random Walks).

Let $x=(x_{1},\dotsc,x_{m})\in\mathbb{R}^{m}$. Fix any permutation
$\sigma:[m]\to[m]$ and sign vector
$\varepsilon=(\varepsilon_{1},\dotsc,\varepsilon_{m})\in\\{\pm 1\\}^{m}$. For
any $a\in\mathbb{R}$, we define the function
$W_{x}^{+a}(t;\sigma,\varepsilon)$ for $t\in\\{0\\}\cup[m]$ as

$W_{x}^{+a}(t;\sigma,\varepsilon)\vcentcolon=\begin{cases}a&\text{ if }t=0\\\
a+\sum_{i=1}^{t}\varepsilon_{i}x_{\sigma(i)}&\text{ if }t>0\,.\end{cases}$

The random walk $\bm{W}_{x}^{+a}$ is defined by choosing a uniformly random
permutation $\bm{\sigma}$ and vector $\bm{\varepsilon}\sim\\{\pm 1\\}^{m}$ and
setting $\bm{W}_{x}^{+a}(t)=W_{x}^{+a}(t;\bm{\sigma},\bm{\varepsilon})$ for
every $t$. If $a=0$ we drop the superscript.

The main quantity of interest to us is the number of sign-changes of a random
walk, defined as follows.

######  Definition 3.2 (Crossing Number).

Let $W:\\{0\\}\cup[m]\to\mathbb{R}$ be any sequence. We define the _crossing
number_ $C(W)$ as the number of sign-changes of $W$, defined as the number of
times $t\in[m]$ such that either $W(t)\geq 0>W(t-1)$ or $W(t)<0\leq W(t-1)$.

An important feature of our random walks will be that they have the Distinct
Subset-Sum (DSS).

######  Definition 3.3 (DSS Random Walk).

We say a sequence $x\in\mathbb{R}^{m}$ has the Distinct Subset-Sum (DSS)
property if for every two disjoint subsets $A,B\subseteq[m]$, it holds that
$\sum_{a\in A}x_{a}\neq\sum_{b\in B}x_{b}$. In particular, the random walk
$\bm{W}_{x}$ satisfies

$\forall
t\in[m]\,,\;\underset{\bm{\sigma},\bm{\varepsilon}}{\mathbb{P}}\left[W_{x}(t;\bm{\sigma},\bm{\varepsilon})=0\right]=0\,.$

Note that, if $x$ has the DSS property, then so does any subsequence of $x$.

We will require an upper bound on the crossing number of _max-walks_ , which
are random walks defined as the maximum of a set of _constituent_ walks of the
type defined above.

######  Definition 3.4 (Max-Walk).

Let $X$ be a set of sequences $x\in\mathbb{R}^{m}$, and let
$a:X\to\mathbb{R}$. For a fixed permutation $\sigma$ and vector
$\varepsilon\in\\{\pm 1\\}^{m}$, define

$M_{X}^{+a}(t;\sigma,\varepsilon)\vcentcolon=\max_{x\in
X}W_{x}^{+a(x)}(t;\sigma,\varepsilon)\,,$

and let the random walk $\bm{M}_{X}^{+a}$ be defined as

$\bm{M}_{X}^{+a}(t)\vcentcolon=M_{X}^{+a}(t;\bm{\sigma},\bm{\varepsilon})$

where $\bm{\sigma},\bm{\varepsilon}$ are chosen uniformly at random.

The main fact about max-walks that we require is the following, which we prove
in Section 3.1.3.

######  Lemma 3.5 (Max-Walk Crossing Number).

Let $X$ be a set of sequences $x\in\mathbb{R}^{m}$, each having the DSS
property, and let $a:X\to\mathbb{R}$. Then

$\mathbb{E}\left[C(\bm{M}_{X}^{+a})\right]=O(\sqrt{m})\,.$

####  3.1.2 Upper Bound on the Number of Influential Edges of a Convex Set

We now prove the following upper bound on the influence of any convex set in
the ternary hypercube, restated below for convenience.

See 1.4

We require the following basic property of discrete convex sets.

######  Proposition 3.6.

Let $S\subseteq\\{0,\pm 1\\}^{n}$ be any discrete convex set. Then there is a
finite set of vectors $V\subseteq\mathbb{R}^{n}$ and thresholds
$\tau:V\to\mathbb{R}$, where each $v\in V$ defines a halfspace
$H_{v}\vcentcolon=\\{x\in\\{0,\pm 1\\}^{n}\;:\;\langle v,x\rangle<\tau(v)\\}$,
such that $S=\bigcap_{v\in V}H_{v}$. One may also assume that $V$ satisfies
the property that, for every $v\in V$ and every two disjoint subsets
$A,B\subseteq[n]$, $\sum_{i\in A}v_{i}\neq\sum_{j\in B}v_{j}$.

###### Proof.

Since $S$ is the intersection of its convex hull $\mathsf{Conv}(S)$ with
$\\{0,\pm 1\\}^{n}$, it may be written as the intersection of $\\{0,\pm
1\\}^{n}$ with a finite set of halfspaces with normal vectors $V$ and
thresholds $\tau:V\to\mathbb{R}$, and one may assume that none of the points
in $\\{0,\pm 1\\}^{n}$ lie on the hyperplane boundary of any of the
halfspaces. Then there is some $\delta>0$ such that the minimum distance
between a hyperplane and a point of $\\{0,\pm 1\\}^{n}$ is at least
$\delta\cdot n$. For each $v\in V$, apply independent random perturbations to
each coordinate to obtain $v^{\prime}_{i}=v_{i}+r_{i}$ where $r_{i}$ is drawn
from $[-\delta,\delta]$ uniformly at random. With probability 1, the resulting
set $V^{\prime}=\\{v^{\prime}\;:\;v\in V\\}$ satisfies the required
conditions. ∎

###### Proof of Theorem 1.4.

Recall the definition of the edge-set $E$ of the ternary cube from equation 1
and the set $\mathsf{Mid}(\ell)$ from Section 2.3. Given $\ell>0$, let

$E_{\ell}=\left\\{(u,v)\in E\colon u,v\in\mathsf{Mid}(\ell)\right\\}$

denote the set of edges lying in the middle $\ell$ layers of $\\{0,\pm
1\\}^{n}$. We consider the following process which samples a random edge in
$\\{0,\pm 1\\}^{n}$. Define $\ell:=\sqrt{2n\log n}$ and
$m:=\sqrt{\frac{n}{\log n}}$. Let $\mathcal{D}$ denote the distribution over
edges defined by the following procedure.

  1. 1.

Sample $\bm{X}^{(0)}\sim\mathsf{Mid}(\ell)$.

  2. 2.

Choose a random subset $\bm{T}\subseteq\\{i\colon\bm{X}^{(0)}_{i}=0\\}$ with
$|\bm{T}|=m$ of coordinates where $\bm{X}^{(0)}$ has a $0$.

  3. 3.

Let
$\bm{\varepsilon}=(\bm{\varepsilon}_{1},\ldots,\bm{\varepsilon}_{m})\in\\{\pm
1\\}^{m}$ be independent Rademacher random variables and let
$\bm{\sigma}\colon[m]\to\bm{T}$ be a random bijection.

  4. 4.

For each $s\in[m]$, let
$\bm{X}^{(s)}=\bm{X}^{(s-1)}+\bm{\varepsilon}_{s}e_{\bm{\sigma}(s)}=\bm{X}^{(0)}+\sum_{i=1}^{s}\bm{\varepsilon}_{i}e_{\bm{\sigma}(i)}$
where $e_{j}$ is the unit vector with a $1$ in coordinate $j$.

  5. 5.

Choose $\bm{s}\sim[m]$ and return the edge
$(\bm{X},\bm{Y})=(\bm{X}^{(s-1)},\bm{X}^{(s)})$.

Note that the above process can be equivalently defined as obtaining
$\bm{X}^{(s)}$ by selecting a uniform random coordinate $\bm{i}$ where
$\bm{X}^{(s-1)}_{\bm{i}}=0$ and flipping that bit to a random value in $\\{\pm
1\\}$, with equal probability. This results in a random walk
$\bm{X}^{(0)},\bm{X}^{(1)},\ldots,\bm{X}^{(m)}$ of length $m$ where each
$(\bm{X}^{(s-1)},\bm{X}^{(s)})$ is a random out-going edge from
$\bm{X}^{(s-1)}$. We use two main claims regarding this random walk to
complete the proof of the theorem. The first is that choosing an edge
$(\bm{X},\bm{Y})\sim\mathcal{D}$ is approximately the same as choosing a
uniformly random edge from the middle layers.

######  Claim 3.7.

Fix any $z\in\mathsf{Mid}(\ell)$ and $s\in[m]$. Then
$\mathbb{P}[\bm{X}^{(s)}=z]=\Theta(3^{-n})$. I.e., each step of the random
walk is approximately uniformly distributed over $\mathsf{Mid}(\ell)$. As a
corollary, for any fixed edge $(u,v)\in E_{\ell}$, we have

$\mathbb{P}_{(\bm{X},\bm{Y})\sim\mathcal{D}}[(\bm{X},\bm{Y})=(u,v)]=\Theta\left(\frac{1}{n\cdot
3^{n}}\right)\text{.}$

The second claim is that the probability of $(\bm{X},\bm{Y})\sim\mathcal{D}$
being an influential edge is small.

######  Claim 3.8.

$\mathbb{P}_{(\bm{X},\bm{Y})\sim\mathcal{D}}[S(\bm{X})\neq S(\bm{Y})]\leq
O\left(\frac{1}{\sqrt{m}}\right)$.

We defer the proof of both claims to the end of the section. We now prove
Theorem 1.4 using 3.7 and 3.8 as follows. Let $E$ denote the edges of the
ternary hypercube and let $E_{\ell}=\\{(u,v)\in E\colon
u,v\in\mathsf{Mid}(\ell)\\}$. By definition,

$\displaystyle\mathbb{I}(S)=\frac{1}{3^{n}}\cdot\Big{(}|\\{(u,v)\in E\setminus
E_{\ell}\colon S(u)\neq S(v)\\}|+|\\{(u,v)\in E_{\ell}\colon S(u)\neq
S(v)\\}|\Big{)}\text{.}$

The first term is bounded using 2.9 as

$\displaystyle\frac{|\\{(u,v)\in E\setminus E_{\ell}\colon S(u)\neq
S(v)\\}|}{3^{n}}\leq\frac{|E\setminus E_{\ell}|}{3^{n}}\leq
2n\cdot\frac{|\overline{\mathsf{Mid}(\ell)}|}{3^{n}}\leq 2n\cdot
2\exp(-\ell^{2}/2n)=O(1)$

since every vertex has degree at most $2n$. The second term is bounded as

$\displaystyle\frac{|\\{(u,v)\in E_{\ell}\colon S(u)\neq S(v)\\}|}{3^{n}}$
$\displaystyle=\frac{|E_{\ell}|}{3^{n}}\cdot\mathbb{P}_{(u,v)\sim
E_{\ell}}[S(u)\neq S(v)]\leq\frac{2n}{3}\cdot\mathbb{P}_{(u,v)\sim
E_{\ell}}[S(u)\neq S(v)]$ $\displaystyle\leq
Ln\cdot\mathbb{P}_{(\bm{X},\bm{Y})\sim\mathcal{D}}[S(\bm{X})\neq
S(\bm{Y})]\leq L^{\prime}n\cdot m^{-1/2}=L^{\prime}\cdot
n^{3/4}\log^{1/4}n\,,$

where $L,L^{\prime}$ are absolute constants. The first inequality follows
simply from $E_{\ell}\subset E$ and $|E|=2n\cdot 3^{n-1}$. The second
inequality follows from 3.7 and the third inequality follows from 3.8. This
completes the proof of Theorem 1.4. ∎

Let us now complete the deferred proofs of 3.7 and 3.8.

###### Proof of 3.7.

Let $\left\lVert z\right\rVert_{1}=\frac{2n}{3}+r$ where $|r|=O(\sqrt{n\log
n})$. In order for $X^{(s)}=z$ to occur we must have $\left\lVert
X^{(0)}\right\rVert_{1}=\frac{2n}{3}+r-s$. Thus, the probability is

$\displaystyle\mathbb{P}[X^{(s)}=z]$
$\displaystyle=\frac{1}{3^{n}}\left({n\choose\frac{2n}{3}+r-s}\cdot
2^{\frac{2n}{3}+r-s}\right)\cdot\left({n\choose\frac{2n}{3}+r}\cdot
2^{\frac{2n}{3}+r}\right)^{-1}$
$\displaystyle=\frac{1}{3^{n}}\cdot\frac{1}{2^{s}}\cdot{n\choose\frac{2n}{3}+r-s}{n\choose\frac{2n}{3}+r}^{-1}=\Theta(3^{-n})$

where the last step is due to the following fact:

_If $|r|\leq O(\sqrt{n\log n})$ and $s=O(\sqrt{\frac{n}{\log n}})$, then
${n\choose\frac{2n}{3}+r-s}{n\choose\frac{2n}{3}+r}^{-1}=\Theta(2^{s})$. As a
corollary, the number of points in the ternary cube with hamming weight
$\frac{2n}{3}+r-s$ and $\frac{2n}{3}+r$ differ by at most a constant factor._

This is proved as follows.

$\displaystyle\frac{{n\choose\frac{2n}{3}+r-s}}{{n\choose\frac{2n}{3}+r}}$
$\displaystyle=\frac{\left(\frac{2n}{3}+r\right)!\left(\frac{n}{3}-r\right)!}{\left(\frac{2n}{3}+r-s\right)!\left(\frac{n}{3}-r+s\right)!}=\prod_{p=0}^{s-1}\frac{\frac{2n}{3}+r-p}{\frac{n}{3}-r+s-p}=2^{s}\cdot\prod_{p=0}^{s-1}\frac{\frac{n}{3}+\frac{r}{2}-\frac{p}{2}}{\frac{n}{3}-r+s-p}$
$\displaystyle=2^{s}\cdot\prod_{p=0}^{s-1}\frac{\frac{n}{3}-r+s-p+(\frac{3r}{2}+\frac{p}{2}-s)}{\frac{n}{3}-r+s-p}=2^{s}\cdot\prod_{p=0}^{s-1}\left(1+\frac{\frac{3r}{2}+\frac{p}{2}-s}{\frac{n}{3}-r+s-p}\right)$

Observe that the numerator inside the product is $\pm O(\sqrt{n\log n})$ since
$r$ is the dominating term and the denominator is $\Omega(n)$ since $n/3$ is
the dominating term. Therefore, we have

$\displaystyle\frac{{n\choose\frac{2n}{3}+r-s}}{{n\choose\frac{2n}{3}+r}}=2^{s}\cdot\left(1\pm
O\left(\sqrt{\frac{\log n}{n}}\right)\right)^{s}=\Theta(1)\cdot 2^{s}$

since $s=O(\sqrt{\frac{n}{\log n}})$. ∎

###### Proof of 3.8..

Let $S$ be an intersection of halfspaces $S=\bigcap_{v\in V}H_{v}$, with
thresholds $\tau:V\to\mathbb{R}$, in the form promised by Proposition 3.6. In
particular, each vector $v\in V$ has the DSS property (Definition 3.3). Fix
any value of $\bm{X}^{(0)}=X^{(0)}$ and fix any permutation $\sigma$ and sign-
vector $\varepsilon=(\varepsilon_{1},\dotsc,\varepsilon_{m})\in\\{\pm
1\\}^{m}$ in the definition of $\mathcal{D}$, and consider the resulting fixed
values of $X^{(0)},X^{(1)},\dotsc,X^{(m)}$. Define $a:V\to\mathbb{R}$ as
$a(v)=\langle v,X^{(0)}\rangle-\tau(v)$.

For each $v\in V$, consider the sequences
$W_{v}^{+a(v)}\vcentcolon=W_{v}^{+a(v)}(\cdot\;;\sigma,\varepsilon)$. For each
$X^{(s)}$, observe that $X^{(s)}\in H_{v}$ if and only if $\langle
v,X^{(s)}\rangle<\tau(v)$, which is equivalent to the condition $W_{v}(s)<0$,
since

$\displaystyle W_{v}^{+a(v)}(s)$
$\displaystyle=a(v)+\sum_{j=1}^{s}\varepsilon_{j}\cdot
v_{\sigma(j)}=\left(\sum_{i:X^{(0)}_{i}\neq
0}v_{i}X^{(0)}_{i}\right)-t(v)+\sum_{j=1}^{s}X^{(s)}_{\sigma(j)}v_{\sigma(j)}$
$\displaystyle=\left(\sum_{j:X^{(s)}_{j}\neq
0}X^{(s)}_{j}v_{j}\right)-t(v)=\langle X^{(s)},v\rangle-t(v)\,.$

Therefore $X^{(s)}\in S$ if and only if $W_{v}^{+a(v)}(s)<0$ for all $v\in V$,
which is equivalent to $M_{V}^{+a}(s)<0$ where $M_{V}^{+a}$ is the max-walk
(recall Definition 3.4). Then for fixed sequence $X^{(0)},\dotsc,X^{(m)}$ and
uniformly random $\bm{s}\sim[m]$, the probability that
$(X^{(\bm{s}-1)},X^{(\bm{s})})$ is an influential edge is equal to
$\frac{C(M_{V}^{+a})}{m}$. Therefore, taking $\bm{\sigma}$ and
$\bm{\varepsilon}$ to be random, we have

$\underset{(\bm{X},\bm{Y})\sim\mathcal{D}}{\mathbb{P}}\left[S(\bm{X})\neq
S(\bm{Y})\right]=\frac{1}{m}\cdot\mathbb{E}\left[C(\bm{M}_{V}^{+{\bm{a}}})\right]=O(\sqrt{m})\,,$

where the final bound is due to Lemma 3.5, since each vector in $V$ was
assumed to have the DSS property. This concludes the proof of the claim. ∎

####  3.1.3 Crossing Bound for the Max-Walk: Proof of Lemma 3.5

We prove an upper bound on the number of times the maximum of a set of one-
dimensional random walks can change sign. Let us define certain special events
in a random walk.

Fix any walk time $m$ and let $W:\\{0\\}\cup[m]\to\mathbb{R}$. We define:

  * •

A _downcrossing_ of $W$ is a time $t\in[m]$ such that $W(t)<0\leq W(t-1)$.
$C_{\downarrow}(W)$ is the number of downcrossings of $W$.

  * •

An _upcrossing_ of $W$ is a time $t\in[m]$ such that $W(t)\geq 0>W(t)$.
$C_{\uparrow}(W)$ is the number of upcrossings of $W$.

  * •

A _downwards level return_ of $W$ is any time $t$ such that either:

    * –

If $W(0)\geq 0$ then the smallest time $t\in[m]$ such that $W(t)<W(0)$ is a
downwards level return.

    * –

For any upcrossing $s$ of $W$, the first time $t>s$ such that $W(t)<W(s)$ is a
downwards level return.

We write $L_{\downarrow}(W)$ for the number of downwards level returns of $W$.

  * •

The _downwards level decrease_ times of $W$ is the unique sequence
$s_{1}<s_{2}<\dotsm$ defined inductively as follows.

    * –

If $W(0)\geq 0$ then $s_{1}$ is the first time such that $W(s_{1})<W(0)$.
Otherwise let $t$ be the first upcrossing of $W$. Then $s_{1}$ is the first
time such that $W(s_{1})<W(t)$.

    * –

For $i>1$, if $W(s_{i-1})\geq 0$ then $s_{i}\in[m]$ is the smallest time such
that $W(s_{i})<W(s_{i-1})$. Otherwise, if $W(s_{i-1})<0$, then let $t$ be the
first upcrossing $t>s_{i-1}$ and define $s_{i}$ as the first time $s_{i}>t$
such that $W(s_{i})<W(t)$.

We write $S_{\downarrow}(W)$ for the number of downwards level decreases of
$W$.

  * •

The _upwards level increase_ times of $W$ is the unique sequence
$t_{1}<t_{2}<\dotsm$ defined inductively as follows.

    * –

If $W(0)<0$ then $t_{1}$ is the first time such that $W(t_{1})>W(0)$.
Otherwise let $s$ be the first downcrossing of $W$. Then $t_{1}$ is the first
time such that $W(t_{1})>W(t)$.

    * –

For $i>1$, if $W(t_{i-1})<0$ then $t_{i}$ is the first time such that
$W(t_{i})>W(t_{i-1})$. Otherwise if $W(t_{i-1})\geq 0$, then let $s$ be the
first downcrossing $s>t_{i-1}$ and define $t_{i}$ as the first time $t_{i}>s$
such that $W(t_{i})>W(s)$.

We write $S_{\uparrow}(W)$ for the number of upwards level increases of $W$.

The main technical tool in our analysis is the following version of Sparre
Andersen’s fluctuation theorem [Spa54], as found in [BB23, Prop. 4.1]. Recall
the definition of $\bm{W}_{x}$ from Definition 3.1 and the DSS property from
Definition 3.3.

######  Theorem 3.9 (Sparre Anderson; see [BB23], Proposition 4.1).

For every $m\in\mathbb{N}$, if $x\in\mathbb{R}^{m}$ has the DSS property, then
the random walk $\bm{W}_{x}$ satisfies

$\mathbb{P}\left[\forall
t\in[m]:\bm{W}_{x}(t)>0\right]=g(m)\vcentcolon=\frac{1}{4^{m}}{2m\choose
m}\,.$

We define a random variable $\bm{R}$ on the positive integers with

$\forall
t\in\mathbb{N}\,,\;\mathbb{P}\left[\bm{R}=t\right]\vcentcolon=g(t-1)-g(t)=\frac{1}{4^{t-1}}{2(t-1)\choose
t-1}-\frac{1}{4^{t}}{2t\choose t}\,,$

where we define $g(0)\vcentcolon=1$. For each $m\in\mathbb{N}$, we also define
a random variable $\bm{Q}^{(m)}$ by the following process. Set $q=0$ and
$X=0$; while $X<m$, increment $q$ and set $X\leftarrow X+\bm{R}$ where
$\bm{R}$ is a new independent copy of the random variable defined above. Then
set $\bm{Q}^{(m)}=q$ once this process terminates; note that $\bm{Q}^{(0)}=0$.
Observe that for every $k\in\mathbb{N}$,

$\mathbb{P}\left[\bm{Q}^{(m)}\geq
k\right]=\mathbb{P}\left[\bm{R}_{1}+\bm{R}_{2}+\dotsm+\bm{R}_{k}\leq m\right]$

where each $\bm{R}_{i}$ is an independent copy of $\bm{R}$, and

$\displaystyle\mathbb{E}\left[\bm{Q}^{(m)}\right]=\sum_{t=1}^{m}\mathbb{P}\left[\bm{R}=t\right]\cdot\left(1+\mathbb{E}\left[\bm{Q}^{(m-t)}\right]\right)\,.$

The following holds due to Theorem 3.9.

######  Proposition 3.10.

Let $x\in\mathbb{R}^{m}$ have the DSS property, let $a\in\mathbb{R}$, and let
$\bm{s}_{1}$, $\bm{t}_{1}$ denote the first downwards level decrease time and
upwards level increase times of $\bm{W}_{x}^{+a}$, respectively. Then for all
$z\in[m]$,

  1. 1.

If $a\geq 0$ then
$\mathbb{P}\left[\bm{s}_{1}=z\right]=\mathbb{P}\left[\bm{R}=z\right]$; and,

  2. 2.

If $a<0$ then
$\mathbb{P}\left[\bm{t}_{1}=z\right]=\mathbb{P}\left[\bm{R}=z\right]$.

######  Proposition 3.11.

Let $x\in\mathbb{R}^{m}$ have the DSS property and let $a\in\mathbb{R}$. Then

$\mathbb{E}\left[\bm{Q}^{(m)}\right]=\mathbb{E}\left[S_{\downarrow}(\bm{W}_{x}^{+a})+S_{\uparrow}(\bm{W}_{x}^{+a})\right]\,.$

###### Proof.

By induction on $m$. For $m=1$ we have
$\mathbb{E}\left[\bm{Q}^{(1)}\right]=\mathbb{P}\left[\bm{R}=1\right]=1/2$ and
$\mathbb{E}\left[S_{\downarrow}(\bm{W}_{x}^{+a})+S_{\uparrow}(\bm{W}_{x}^{+a})\right]=1/2$
since the random walk has probability $1/2$ of increasing or decreasing in the
first step; if $a\geq 0$ then the walk must decrease to create a downwards
level decrease, while if $a>0$ then the walk must increase to create an
upwards level increase.

Now let $m>1$. Suppose $a\geq 0$ without loss of generality. Then the first
level increase or decrease is a downwards level decrease. Let $\bm{s}_{1}$ be
the first downwards level decrease and let $\bm{y}$ denote the random
subsequence of $x$ that remains after removing the first $\bm{s}_{1}$ elements
according to the random permutation $\bm{\sigma}$. Then by induction and
Proposition 3.10,

$\displaystyle\mathbb{E}\left[S_{\downarrow}(\bm{W}_{x}^{+a})+S_{\uparrow}(\bm{W}_{x}^{+a})\right]$
$\displaystyle=\sum_{t=1}^{m}\mathbb{P}\left[\bm{s}_{1}=t\right]\cdot\left(1+\underset{}{\mathbb{E}}\left[\left.S_{\downarrow}\left(\bm{W}_{\bm{y}}^{+\bm{W}_{x}(\bm{s}_{1})}\right)+S_{\uparrow}\left(\bm{W}_{\bm{y}}^{+\bm{W}_{x}(\bm{s}_{1})}\right)\;\right|\;\bm{s}_{1}=t\right]\right)$
$\displaystyle=\sum_{t=1}^{m}\mathbb{P}\left[\bm{R}=t\right]\cdot\left(1+\mathbb{E}\left[\bm{Q}^{(m-t)}\right]\right)=\mathbb{E}\left[\bm{Q}^{(m)}\right]\,.\qed$

For a sequence $W:\\{0\\}\cup[m]\to\mathbb{R}$, write
$Z(W)=\sum_{t=1}^{m}\mathds{1}\left[W(t)\in\\{0,\pm 1\\}\right]$.

######  Lemma 3.12.

For any $m$, $\mathbb{E}\left[Z(\bm{W}_{\vec{1}})\right]=O(\sqrt{m})$.

###### Proof.

We first bound the number of times $t$ such that $\bm{W}_{\vec{1}}(t)=0$. If
$t$ is odd then $\mathbb{P}\left[\bm{W}_{\vec{1}}(t)=0\right]=0$. If $t$ is
even then there is a universal constant $C$ such that

$\mathbb{P}\left[\bm{W}_{\vec{1}}(t)=0\right]=\frac{1}{2^{t}}{t\choose
t/2}\leq C\cdot\frac{1}{\sqrt{t}}\,.$

Therefore the expected number of times $t$ with $\bm{W}_{\vec{1}}(t)=0$ is at
most

$\sum_{t\text{ even}}\mathbb{P}\left[\bm{W}_{\vec{1}}(t)=0\right]\leq
C\cdot\sum_{t=1}^{m}\frac{1}{\sqrt{t}}=O(\sqrt{m})\,.$

Now observe that the expected number of times $t$ where
$\bm{W}_{\vec{1}}(t)=1$ is the average of the expected number of times where
the shifted walks $\bm{W}_{\vec{1}}^{+a}$ is 0 on domain $[m-1]$, where $a=\pm
1$, and the same holds for the number of times $t$ where
$\bm{W}_{\vec{1}}(t)=-1$. ∎

######  Proposition 3.13.

There exists $x\in\mathbb{R}^{m}$ with the DSS property such that
$\mathbb{E}\left[S_{\downarrow}(\bm{W}_{x})+S_{\uparrow}(\bm{W}_{x})\right]\leq\mathbb{E}\left[Z(\bm{W}_{\vec{1}})\right]$.
As a consequence,

$\mathbb{E}\left[\bm{Q}^{(m)}\right]=O(\sqrt{m})\,.$

###### Proof.

Let $\delta\vcentcolon=\frac{1}{3m}$. Let $\bm{x}\vcentcolon=\vec{1}+\bm{z}$
where $\bm{z}\sim[-\delta,\delta]^{m}$ uniformly at random. Note that $\bm{x}$
has the DSS property with probability 1. For any fixed
$z\in[-\delta,\delta]^{m}$, any permutation $\sigma$, and any $r\in\\{\pm
1\\}^{n}$, write $W_{x}(t)\vcentcolon=W_{x}(t;\sigma,\varepsilon)$ for
$x=\vec{1}+z$. Then we have
$W_{x}(t;\sigma,\varepsilon)\in[W_{\vec{1}}(t;\sigma,\varepsilon)-1/3,W_{\vec{1}}(t;\sigma,\varepsilon)+1/3]$.
Now fix any $z\in[-\delta,\delta]^{m}$ such that $x=\vec{1}+z$ has the DSS
property; we show that it satisfies the required condition.

Let $s_{1}<s_{2}<\dotsm<s_{k}$ be the downwards level decreasing or upwards
level increasing points for $W_{x}$, let $s_{0}=0$, and observe that a point
cannot be both downwards level decreasing and upwards level increasing. We
show by induction on $i$ that $|W_{x}(s_{i})|\leq 1+1/3$ and therefore that
$W_{\vec{1}}(s_{i})\in\\{0,\pm 1\\}$. Since $W_{x}(0)=0$ it must be that
$s_{1}$ is downwards level decreasing and $W_{x}(s_{1})<0=W_{x}(0)\leq
W_{x}(s_{1}-1)$ and therefore $W_{x}(s_{1})\geq W_{x}(s_{1}-1)-1-1/3\geq-4/3$
so it must be that $W_{\vec{1}}(s_{1})\in\\{-1,0\\}$. For $i>1$, suppose that
$s_{i}$ is a downwards level decreasing point. If there exists an upcrossing
point $a>s_{i-1}$ such that $W_{x}(s_{i})<W_{x}(a)$, then we observe that
$W_{x}(a-1)<0\leq W_{x}(a)$ and therefore $W_{x}(a)<1+1/3$ so
$W_{\vec{1}}(a)\in\\{0,1\\}$. Now $W_{x}(s_{i})<W_{x}(a)\leq W_{x}(s_{i}-1)$
so it must be that $-1-1/3\leq W_{x}(s_{i})<1+1/3$ so
$W_{\vec{1}}(s_{i})\in\\{0,\pm 1\\}$. On the other hand, if
$W_{x}(s_{i-1})\geq 0$ and $W_{x}(s_{i})<W_{x}(s_{i-1})$ then by induction we
have $W_{\vec{1}}(s_{i-1})\in\\{0,1\\}$, and also
$W_{x}(s_{i}-1)>W_{x}(s_{i-1})$, so again we have $-1-1/3\leq
W_{x}(s_{i})<1+1/3$ and therefore $W_{\vec{1}}(s_{i})\in\\{0,\pm 1\\}$. A
similar argument holds for the upwards level increasing points.

The conclusion now follows from Proposition 3.11 and Lemma 3.12, since for the
$x\in\mathbb{R}^{m}$ defined in the current proof,

$\mathbb{E}\left[\bm{Q}^{(m)}\right]=\mathbb{E}\left[S_{\downarrow}(\bm{W}_{x})+S_{\uparrow}(\bm{W}_{x})\right]\leq\mathbb{E}\left[Z(\bm{W}_{\vec{1}})\right]=O(\sqrt{m})\,.\qed$

######  Proposition 3.14.

Let $X$ be a set of sequences $x\in\mathbb{R}^{m}$ each having the DSS
property, and let $a:X\to\mathbb{R}$ be arbitrary. Then

$\mathbb{E}\left[L_{\downarrow}(\bm{M}_{X}^{+a})\right]\leq\mathbb{E}\left[\bm{Q}^{(m)}\right]\,.$

###### Proof.

By induction on $m$. For $m=1$, the probability that $\bm{M}_{X}^{+a}$ has a
downwards level return is at most $1/2$, because if $M_{X}^{+a}(0)\geq 0$, all
of the maximizing constituent walks $x\in X$ satisfying
$W_{x}(0)^{+a(x)}=M_{X}^{+a}(0)$ must decrease. If $M_{X}^{+a}(0)<0$ then
there is no downwards level return for $m=1$.

Let $m>1$ and consider two cases. First assume that $M_{X}^{+a}(0)\geq 0$ and
let $x\in X$ be an arbitrary constituent walk satisfying
$W_{x}^{+a(x)}(0)=M_{X}^{+a}(0)$. For fixed permutation $\sigma$ and sign
vector $\varepsilon$, let $s_{1}$ be the first downwards level return point of
$M_{X}^{+a}(\cdot\;;\sigma,\varepsilon)$ and let $s^{\prime}_{1}$ be the first
downwards level return point of $W_{x}^{+a(x)}(\cdot\;;\sigma,\varepsilon)$.
Note that $s^{\prime}_{1}\leq s_{1}$ since $M_{X}^{+a}$ is the maximum of its
constituents.

Now we may write

$\mathbb{E}\left[L_{\downarrow}(\bm{M}_{X}^{+a})\right]=\sum_{s=1}^{m}\mathbb{P}\left[\bm{s}_{1}=s\right]\left(1+\underset{}{\mathbb{E}}\left[\left.L_{\downarrow}\left(\bm{M}_{\bm{Y}}^{+\bm{b}}\right)\;\right|\;\bm{s}_{1}=s\right]\right)\,,$

where $\bm{Y}$ denotes the set of vectors $X$ after removing the first $t$
coordinates according to the random permutation $\bm{\sigma}$ and
$\bm{b}:\bm{Y}\to\mathbb{R}$ is the starting point
$\bm{b}(\bm{y})=\bm{W}_{x}^{+a(x)}(t)$ of each walk $\bm{y}\in\bm{Y}$ obtained
from the original vector $x\in X$ by removing the first $t$ coordinates
according to $\bm{\sigma}$. By induction, this is

$\underset{}{\mathbb{E}}\left[\left.L_{\downarrow}\left(\bm{M}_{\bm{Y}}^{+\bm{b}}\right)\;\right|\;\bm{s}_{1}=s\right]\leq\mathbb{E}\left[\bm{Q}^{(m-s)}\right]\,.$

Now we write $\bm{s}_{1}=\bm{s}^{\prime}_{1}+(\bm{s}_{1}-\bm{s}^{\prime}_{1})$
where the second term is non-negative. Then

$\displaystyle\mathbb{E}\left[L_{\downarrow}(\bm{M}_{X}^{+a})\right]$
$\displaystyle\leq\sum_{s=1}^{m}\mathbb{P}\left[\bm{s}^{\prime}_{1}+(\bm{s}_{1}-\bm{s}^{\prime}_{1})=s\right]\cdot\left(1+\mathbb{E}\left[\bm{Q}^{(m-s)}\right]\right)$
$\displaystyle=\sum_{t=1}^{m}\mathbb{P}\left[\bm{s}^{\prime}_{1}=t\right]\sum_{s=0}^{m-t}\underset{}{\mathbb{P}}\left[\left.\bm{s}_{1}-\bm{s}^{\prime}_{1}=s\;\right|\;\bm{s}^{\prime}_{1}=t\right]\left(1+\mathbb{E}\left[\bm{Q}^{(m-(s+t))}\right]\right)\,.$

The inner sum is a convex sum of terms
$1+\mathbb{E}\left[\bm{Q}^{(m-(s+t))}\right]$ which are each bounded by
$1+\mathbb{E}\left[\bm{Q}^{(m-t)}\right]$ because
$\mathbb{E}\left[\bm{Q}^{(k)}\right]\geq\mathbb{E}\left[\bm{Q}^{(k^{\prime})}\right]$
when $k\geq k^{\prime}$. We also have
$\mathbb{P}\left[\bm{s}^{\prime}_{1}=t\right]=\mathbb{P}\left[\bm{R}=t\right]$
due to Proposition 3.10. Therefore,

$\mathbb{E}\left[L_{\downarrow}(\bm{M}_{X}^{+a})\right]\leq\sum_{t=1}^{m}\mathbb{P}\left[\bm{R}=t\right]\left(1+\mathbb{E}\left[\bm{Q}^{(m-t)}\right]\right)=\mathbb{E}\left[\bm{Q}^{(m)}\right]\,.$

We must now handle the case where $M_{X}^{+a}(0)<0$. Let $\bm{t}$ be the
smallest time where $\bm{M}_{X}^{+a}(\bm{t})\geq 0$. Then

$\mathbb{E}\left[L_{\downarrow}(\bm{M}_{X}^{+a})\right]=\sum_{t=1}^{m}\mathbb{P}\left[\bm{t}=t\right]\underset{}{\mathbb{E}}\left[\left.L_{\downarrow}\left(\bm{M}_{\bm{Y}}^{+\bm{b}}\right)\;\right|\;\bm{t}=t\right]\,,$

where $\bm{Y}$ and $\bm{b}$ are defined similarly as before, as the sequences
$X$ after removing the first $t$ coordinates according to the random
permutation $\bm{\sigma}$ and $\bm{b}(\bm{y})=\bm{W}_{x}^{+a(x)}(t)$ is where
the $x$ walk ended up at time $t$. This new walk starts above 0 so the above
argument applies and the conclusion holds. ∎

We can now prove Lemma 3.5.

###### Proof of Lemma 3.5.

First observe that $C(\bm{M}_{X}^{+a})\leq
2\,C_{\downarrow}(\bm{M}_{X}^{+a})+1$ so it suffices to bound
$C_{\downarrow}(\bm{M}_{X}^{+a})$. By definition it holds that
$C_{\downarrow}(\bm{M}_{X}^{+a})\leq L_{\downarrow}(\bm{M}_{X}^{+a})$, so by
Proposition 3.14 and Proposition 3.13, we have

$\mathbb{E}\left[C_{\downarrow}(\bm{M}_{X}^{+a})\right]\leq\mathbb{E}\left[\bm{Q}^{(m)}\right]=O(\sqrt{m})\,.\qed$

###  3.2 Lower Bound

Recall the definition of the _influence_ of a set in the ternary hypercube
given in equation 2. In this section, we show that there exists a convex set
whose influence is $\Omega(n^{3/4})$, nearly matching the upper bound given in
Theorem 1.4.

The construction of the high-influence set is obtained by considering the
intersection of $2^{\sqrt{n}}$ random halfspaces whose distance from the
origin is $\Theta(n^{3/4})$. This approach is inspired by [Kan14, Theorem 2],
who showed that in the Boolean hypercube, an intersection of $k$ random
halfspaces with an appropriately chosen distance from the origin will have
expected influence $\Omega(\sqrt{n\log k})$. In the ternary hypercube, this
type of argument still works as long as $k\leq 2^{O(\sqrt{n})}$. This type of
construction was also used by Nazarov [Naz03] to show the existence of convex
sets in $\mathbb{R}^{n}$ whose Gaussian surface area is $\Omega(n^{1/4})$,
which matches the $O(n^{1/4})$ upper bound proven by Ball [Bal93].

####  3.2.1 A Convex Set with Large Influence

We prove the following theorem.

See 1.3

###### Proof.

Recall that the edges of $\\{0,\pm 1\\}^{n}$ are the directed pairs of points
$(x,y)$ such that there exists $i\in[n]$ for which $x_{i}=0$, $y_{i}\in\\{\pm
1\\}$ and $x_{j}=y_{j}$ for all $j\neq i$. We will use the following claim
which is also used by Kane (see [Kan14, Lemma 7] and its proof).

######  Claim 3.15.

For any $n$ and $\varepsilon\in[2^{-n},1/2]$, there exists
$\tau=\Theta(\sqrt{n\log 1/\varepsilon})$ such that

$\mathbb{P}_{x\sim\\{\pm
1\\}^{n}}\left[\sum_{i=1}^{n}x_{i}>\tau\right]\geq\varepsilon\text{.}$

Let $\varepsilon=2^{-\sqrt{n}}$ and choose $\tau=\Theta(\sqrt{n\log
1/\varepsilon})=\Theta(n^{3/4})$ so that

$\displaystyle\rho:=\mathbb{P}_{z\sim\\{\pm
1\\}^{2n/3}}\left[\sum_{i}z_{i}>\tau\right]\geq\varepsilon$ (4)

as guaranteed by 3.15. The main technical lemma that allows our construction
to work is the following, which we prove in Section 3.2.2. Note that this
lemma crucially uses the assumption that $\tau=O(n^{3/4})$ and this is where
the structure of the ternary hypercube prevents this construction from
obtaining sets with influence $\gg n^{3/4}$.

######  Lemma 3.16.

For all $n$, all $\Omega(\sqrt{n})\leq\tau\leq O(n^{3/4})$, and all
$\ell=O(\sqrt{n})$,

$\underset{x\sim\\{\pm
1\\}^{n+\ell}}{\mathbb{P}}\left[\sum_{i=1}^{n+\ell}x_{i}>\tau\right]\leq
O\left(\underset{x\sim\\{\pm
1\\}^{n}}{\mathbb{P}}\left[\sum_{i=1}^{n}x_{i}>\tau\right]\right)\text{.}$

By Lemma 3.16 there are constants $C_{0}<1<C_{1}$ such that for all
$\ell\in[-\sqrt{n},\sqrt{n}]$, we have

$\displaystyle C_{0}\rho\leq\underset{z\sim\\{\pm
1\\}^{2n/3+\ell}}{\mathbb{P}}\left[\sum_{i}z_{i}>\tau\right]\leq
C_{1}\rho\text{.}$ (5)

Define $H:=\\{x\in\\{0,\pm 1\\}^{n}\colon\sum_{i=1}^{n}x_{i}>\tau\\}$. Let
$L_{m}=\\{x\in\\{0,\pm 1\\}^{n}\colon\left\lVert x\right\rVert_{1}=m\\}$ and
note that

$\underset{z\sim\\{\pm
1\\}^{2n/3+\ell}}{\mathbb{P}}\left[\sum_{i}z_{i}>\tau\right]=\underset{z\sim
L_{2n/3+\ell}}{\mathbb{P}}\left[\sum_{i}z_{i}>\tau\right]$

and so equation 5 tells us that the density of $H$ in $L_{2n/3+\ell}$ only
differs by a constant multiplicative factor for any
$\ell\in[-\sqrt{n},\sqrt{n}]$. We abuse notation and write
$H(x)=\mathbf{1}(x\in H)$. Now, let $E_{\sqrt{n}}$ denote the set of edges in
$\\{0,\pm 1\\}^{n}$ which have both endpoints in $\mathsf{Mid}(\sqrt{n})$ and
let

$\displaystyle\mathbb{I}_{\mathsf{mid}}(H)$
$\displaystyle:=\frac{1}{3^{n}}\cdot|\\{(x,y)\in E_{\sqrt{n}}\colon H(x)\neq
H(y)\\}|$ (6)

denote the influence of $H$ restricted to $\mathsf{Mid}(\sqrt{n})$. We prove
the following lower bound on this quantity.

######  Claim 3.17.

$\mathbb{I}_{\mathsf{mid}}(H)=\Omega(\rho\cdot\tau)$.

###### Proof.

Let $\mathcal{I}=[2n/3-\sqrt{n},2n/3+\sqrt{n}-1]$ and observe that we can
write

$\displaystyle\mathbb{I}_{\mathsf{mid}}(H)$
$\displaystyle=\frac{1}{3}\sum_{i=1}^{n}\underset{x\sim\\{0,\pm
1\\}^{n}}{\mathbb{E}}\left[\mathbf{1}(\left\lVert
x\right\rVert_{1}\in\mathcal{I})\cdot\left(|H(x^{i\leftarrow
1})-H(x^{i\leftarrow 0})|+|H(x^{i\leftarrow
0})-H(x^{i\leftarrow-1})|\right)\right]$
$\displaystyle=\frac{1}{3}\sum_{i=1}^{n}\underset{x\sim\\{0,\pm
1\\}^{n}}{\mathbb{E}}\left[\mathbf{1}(\left\lVert
x\right\rVert_{1}\in\mathcal{I})\cdot(H(x^{i\leftarrow
1})-H(x^{i\leftarrow-1}))\right]$ (7)
$\displaystyle=\frac{1}{3}\underset{x\sim\\{0,\pm
1\\}^{n}}{\mathbb{E}}\left[\sum_{i=1}^{n}\mathbf{1}(\left\lVert
x\right\rVert_{1}\in\mathcal{I})\left(H(x^{i\leftarrow
1})-H(x^{i\leftarrow-1})\right)\right]$
$\displaystyle=\frac{1}{3}\underset{z\sim\\{0,\pm
1\\}^{n}}{\mathbb{E}}\left[\sum_{i:z_{i}=1}\mathbf{1}(\left\lVert
z^{i\leftarrow 0}\right\rVert_{1})H(z)-\sum_{i:z_{i}=-1}\mathbf{1}(\left\lVert
z^{i\leftarrow 0}\right\rVert_{1})H(z)\right]$ (8)

where equation 7 holds because $H$ is a monotone function with respect to the
standard partial order, i.e., if $x_{i}\leq y_{i}$ for all $i\in[n]$, then
$x\in H$ implies $y\in H$, and equation 8 follows by the observation that for
each $i$, $z\in\\{0,\pm 1\\}^{n}$ appears in the sum as $H(z)$ whenever
$x=z^{i\leftarrow 0}$ and $z_{i}=1$, and appears in the sum as $-H(z)$
whenever $x=z^{i\leftarrow 0}$ and $z_{i}=-1$. Let
$\mathcal{I}^{\prime}=[2n/3-\sqrt{n}+1,2n/3+\sqrt{n}-1]$. Thus, the above
expression can be rewritten as

$\displaystyle\mathbb{I}_{\mathsf{mid}}(H)$
$\displaystyle=\frac{1}{3}\underset{z\sim\\{0,\pm
1\\}^{n}}{\mathbb{E}}\left[H(z)\sum_{i=1}^{n}z_{i}\cdot\mathbf{1}(\left\lVert
z^{i\leftarrow 0}\right\rVert_{1}\in\mathcal{I})\right]$
$\displaystyle\geq\frac{1}{3}\underset{z\sim\\{0,\pm
1\\}^{n}}{\mathbb{E}}\left[H(z)\mathbf{1}(\left\lVert
z\right\rVert_{1}\in\mathcal{I}^{\prime})\sum_{i=1}^{n}z_{i}\right]>\frac{\tau}{3}\underset{z\sim\\{0,\pm
1\\}^{n}}{\mathbb{E}}\left[H(z)\mathbf{1}(\left\lVert
z\right\rVert_{1}\in\mathcal{I}^{\prime})\right]$ (9)

where the first inequality holds since
$\mathcal{I}^{\prime}\subset\mathcal{I}$ and $\left\lVert
z\right\rVert_{1}\in\mathcal{I}^{\prime}$ implies $\left\lVert z^{i\leftarrow
0}\right\rVert_{1}\in\mathcal{I}$ for all $i\in[n]$. The second inequality
holds since $H(z)=1$ if and only if $\sum_{i}z_{i}>\tau$. Finally,

$\displaystyle\underset{z\sim\\{0,\pm
1\\}^{n}}{\mathbb{E}}\left[H(z)\mathbf{1}(\left\lVert
z\right\rVert_{1}\in\mathcal{I}^{\prime})\right]$
$\displaystyle=\frac{1}{3^{n}}\cdot\sum_{\ell=-\sqrt{n}+1}^{\sqrt{n}-1}\sum_{z\in
L_{2n/3+\ell}}H(z)$
$\displaystyle=\sum_{\ell=-\sqrt{n}+1}^{\sqrt{n}-1}\frac{{n\choose
2n/3+\ell}\cdot 2^{2n/3+\ell}}{3^{n}}\cdot\underset{z\sim\\{\pm
1\\}^{2n/3+\ell}}{\mathbb{P}}\left[\sum_{i}z_{i}>\tau\right]$ (10)

and the quantity in the RHS is $\Omega(\rho)$ by the lower bound in equation 5
and since ${n\choose 2n/3+\ell}\cdot 2^{2n/3+\ell}=\Omega(3^{n}/\sqrt{n})$ for
all $\ell\in[-\sqrt{n},\sqrt{n}]$ by an application of Stirling’s
approximation. Combining this with Section 3.2.1, we conclude that
$\mathbb{I}_{\mathsf{mid}}(H)=\Omega(\rho\cdot\tau)$ as claimed. ∎

Let $k:=\max\\{\lfloor(4C_{1}\rho)^{-1}\rfloor,1\\}\leq\varepsilon^{-1}$.
Choose $v^{(1)},\ldots,v^{(k)}\in\\{\pm 1\\}^{n}$ i.i.d. uniformly at random
and for each $i\in[k]$ define $H_{i}=\\{x\in\\{0,\pm 1\\}^{n}\colon\langle
x,v^{(i)}\rangle>\tau\\}$. Let $S=\cap_{i=1}^{k}\overline{H_{i}}$ be the
convex set formed by the intersection of the complements of the $H_{i}$’s.
Note that $\overline{S}=\cup_{i=1}^{k}H_{i}$ and
$\mathbb{I}(S)=\mathbb{I}(\overline{S})$ and thus it suffices to give a lower
bound on $\mathbb{I}(\overline{S})$. Observe that every edge $(x,y)$ that is
influential for $H_{i}$ is guaranteed to be influential for $\overline{S}$ if
$x,y\notin H_{j}$ for all $j\neq i\in[k]$. Moreover, if $\left\lVert
x\right\rVert_{1}=\frac{2n}{3}+\ell$ where $\ell\in[-\sqrt{n},\sqrt{n}]$, then

$\underset{v^{(j)}\sim\\{\pm 1\\}^{n}}{\mathbb{P}}\left[x\in
H_{j}\right]=\underset{v^{(j)}\sim\\{\pm 1\\}^{n}}{\mathbb{P}}\left[\langle
v^{(j)},x\rangle>\tau\right]=\underset{z\sim\\{\pm
1\\}^{2n/3+\ell}}{\mathbb{P}}\left[\sum_{i}z_{i}>\tau\right]\leq
C_{1}\cdot\rho\text{.}$

Thus, by a union bound, the probability that a $H_{i}$-influential edge
$(x,y)$ with $x,y\in\mathsf{Mid}(\sqrt{n})$ remains influential for
$\overline{S}$ is at least $1-2(k-1)\cdot C_{1}\rho\geq
1-2\cdot(4C_{1}\rho)^{-1}\cdot C_{1}\rho\geq 1/2$. Therefore,

$\displaystyle\underset{v^{(1)},\ldots,v^{(m)}}{\mathbb{E}}\left[\mathbb{I}(\overline{S})\right]\geq\frac{1}{2}\sum_{i=1}^{k}\mathbb{I}_{\mathsf{mid}}(H_{i})=\Omega(k\cdot\rho\cdot\tau)=\Omega(\tau)=\Omega\left(n^{3/4}\right)$
(11)

and this completes the proof. ∎

####  3.2.2 Bounding the Density Increment of Halfspaces: Proof of Lemma 3.16

Our proof makes crucial use of the following tight bound on the binomial
coefficient ${n\choose\frac{n-\tau}{2}}$ for any $\tau=O(n^{3/4})$.
Importantly, the bound is tight up to constant multiplicative factors, as
opposed to constant factors in the exponent.

######  Fact 3.18.

If $\tau=O(n^{3/4})$, then
${n\choose\frac{n-\tau}{2}}=\Theta\left(\frac{2^{n}}{\sqrt{n}}\cdot\exp(-\frac{\tau^{2}}{2n})\right)$.

3.18 is a special case of a much more general approximation, Corollary A.2,
specifically the case of $s=2$. The proof is relatively tedious and so we
relegate it to Appendix A. Using 3.18 we are able to prove the following claim
which is important for the proof of Lemma 3.16.

######  Claim 3.19.

For all $n$, all $\Omega(\sqrt{n})\leq\tau\leq O(n^{3/4})$, and all
$\ell=O((n/\tau)^{2})$,

$2^{-(n+\ell)}{n+\ell\choose\frac{n+\ell-\tau}{2}}\leq
O\left(2^{-n}{n\choose\frac{n-\tau}{2}}\right)\text{.}$

###### Proof.

Since $\tau=O(n^{3/4})$, by 3.18

$\displaystyle
2^{-(n+\ell)}{n+\ell\choose\frac{n+\ell-\tau}{2}}\leq\frac{1}{\Theta(\sqrt{n+\ell})}\exp\left(-\frac{\tau^{2}}{2(n+\ell)}\right)=\frac{1}{\Theta(\sqrt{n})}\exp\left(-\frac{\tau^{2}}{2n(1+\ell/n)}\right).$

Observe that

$\displaystyle-\frac{\tau^{2}}{2n(1+\ell/n)}=-\frac{\tau^{2}}{2n}\left(1-\frac{\ell}{n+\ell}\right)=-\frac{\tau^{2}}{2n}+\frac{\tau^{2}\ell}{2n(n+\ell)}=-\frac{\tau^{2}}{2n}+O(1)$

since $\ell=O((n/\tau)^{2})$. Therefore,

$2^{-(n+\ell)}{n+\ell\choose\frac{n+\ell-\tau}{2}}\leq\frac{1}{\Theta(\sqrt{n})}\exp\left(-\frac{\tau^{2}}{2n}\right)\leq
O\left(2^{-n}{n\choose\frac{n-\tau}{2}}\right)$

where the second inequality is by 3.18 since $\tau=O(n^{3/4})$. ∎

We are now set up to prove Lemma 3.16.

###### Proof of Lemma 3.16..

First, write

$\displaystyle\underset{x\sim\\{\pm
1\\}^{n+\ell}}{\mathbb{P}}\left[\sum_{i=1}^{n+\ell}x_{i}>\tau\right]=\underset{x\sim\\{\pm
1\\}^{n+\ell}}{\mathbb{P}}\left[\tau<\sum_{i=1}^{n+\ell}x_{i}\leq
2\tau\right]+\underset{x\sim\\{\pm
1\\}^{n+\ell}}{\mathbb{P}}\left[\sum_{i=1}^{n+\ell}x_{i}>2\tau\right]\text{.}$
(12)

By Hoeffding’s inequality, the second term is

$\displaystyle\underset{x\sim\\{\pm
1\\}^{n+\ell}}{\mathbb{P}}\left[\sum_{i=1}^{n+\ell}x_{i}>2\tau\right]$
$\displaystyle\leq\exp\left(-\frac{2\cdot(2\tau)^{2}}{4(n+\ell)}\right)$
$\displaystyle=\exp\left(-\frac{2\tau^{2}}{n}\left(1-\frac{1}{(n/\ell)+1}\right)\right)=O\left(\exp\left(-\frac{2\tau^{2}}{n}\right)\right)$
(13)

since $\frac{\tau^{2}\ell}{n^{2}}=O(1)$. Using 3.19, the first term is

$\displaystyle\underset{x\sim\\{\pm
1\\}^{n+\ell}}{\mathbb{P}}\left[\tau<\sum_{i=1}^{n+\ell}x_{i}\leq
2\tau\right]$
$\displaystyle=\frac{1}{2^{n+\ell}}\sum_{\tau^{\prime}\in(\tau,2\tau]\text{
even}}{n+\ell\choose\frac{n+\ell-\tau^{\prime}}{2}}$ $\displaystyle\leq
O\left(\frac{1}{2^{n}}\sum_{\tau^{\prime}\in(\tau,2\tau]\text{
even}}{n\choose\frac{n-\tau^{\prime}}{2}}\right)=O\left(\underset{x\sim\\{\pm
1\\}^{n}}{\mathbb{P}}\left[\tau<\sum_{i=1}^{n}x_{i}\leq
2\tau\right]\right)\text{.}$ (14)

We now just need to show that the first term dominates the second term. By
3.18

$\displaystyle\underset{x\sim\\{\pm
1\\}^{n}}{\mathbb{P}}\left[\tau<\sum_{i=1}^{n}x_{i}\leq 2\tau\right]$
$\displaystyle=\frac{1}{2^{n}}\sum_{\tau^{\prime}\in(\tau,2\tau]\text{
even}}{n\choose\frac{n-\tau^{\prime}}{2}}$
$\displaystyle\geq\Omega\left(\frac{\tau}{\sqrt{n}}\exp\left(-\frac{2\tau^{2}}{n}\right)\right)=\Omega\left(\exp\left(-\frac{2\tau^{2}}{n}\right)\right)\text{.}$
(15)

Plugging the bounds from Section 3.2.2, Section 3.2.2, and Section 3.2.2 back
into equation 12 yields

$\underset{x\sim\\{\pm
1\\}^{n+\ell}}{\mathbb{P}}\left[\sum_{i=1}^{n+\ell}x_{i}>\tau\right]\leq
O\left(\underset{x\sim\\{\pm
1\\}^{n}}{\mathbb{P}}\left[\tau<\sum_{i=1}^{n}x_{i}\leq
n^{3/4}\right]\right).\qed$

##  4 Sample-Based Testing and Learning

In this section we prove upper and lower bounds for testing and learning
convex sets on $\\{0,\pm 1\\}^{n}$ with samples.

###  4.1 Upper Bound

See 1.5

Our proof of Theorem 1.5 uses the standard approach of showing that when $S$
is convex, its low-degree Fourier coefficients contain most of the information
about $S$. We can then learn $S$ by estimating its low-degree Fourier
coefficients. This learning approach was established by Linial, Mansour, and
Nisan, and is referred to as the ?Low-Degree Algorithm? [LMN93]. The section
is organized as follows:

  1. 1.

Section 4.1.1: Setup of the Fourier analysis over the ternary hypercube that
will be necessary for the learning result.

  2. 2.

Section 4.1.2: Bounds on the Fourier concentration of convex sets, using the
influence bounds from Section 3.

  3. 3.

Section 4.1.3: The low-degree learning algorithm and the proof of Theorem 1.5
and Corollary 1.6.

####  4.1.1 Fourier Analysis Setup over the Ternary Hypercube

This subsection uses mostly standard techniques, following Chapter 8 of
[O’D14] which outlines how to generalize Fourier analysis of Boolean functions
to arbitary product spaces.

Let $\pi_{1/3}$ and $\pi_{1/3}^{\otimes n}$ denote the uniform distribution
over $\\{0,\pm 1\\}$ and $\\{0,\pm 1\\}^{n}$, respectively. Let
$L^{2}(\\{0,\pm 1\\}^{n},\pi_{1/3}^{\otimes n})$ denote the real inner product
space of functions $f\colon\\{0,\pm 1\\}^{n}\to\mathbb{R}$ with inner product
$\langle f,g\rangle=\mathbb{E}_{x}[f(x)g(x)]$.

######  Definition 4.1.

A _Fourier basis_ for $L^{2}(\\{0,\pm 1\\},\pi_{1/3})$ is an orthonormal basis
$\phi_{-1},\phi_{0},\phi_{+1}\colon\\{0,\pm 1\\}^{n}\to\mathbb{R}$ with
$\phi_{0}\equiv 1$.

An important message in Chapter 8 of [O’D14] is that the specific choice of
Fourier basis does not matter. For concreteness, we can use the following
basis given in Example 8.10 of [O’D14].

######  Definition 4.2.

Define the following Fourier basis for $L^{2}(\\{0,\pm 1\\},\pi_{1/3})$:
$\phi_{0}\equiv 1$,

$(\phi_{-1}(-1),\phi_{-1}(0),\phi_{-1}(1))=(-\sqrt{6}/2,0,\sqrt{6}/2)\text{,
and
}(\phi_{1}(-1),\phi_{1}(0),\phi_{1}(1))=(-\sqrt{2}/2,\sqrt{2},-\sqrt{2}/2)\text{.}$

It can be easily confirmed that the basis in Definition 4.2 is orthonormal and
so is indeed a Fourier basis. Now, given $\alpha\in\\{0,\pm 1\\}^{n}$, we
define $\phi_{\alpha}\in L^{2}(\\{0,\pm 1\\}^{n},\pi_{1/3}^{\otimes n})$ as

$\displaystyle\phi_{\alpha}(x):=\prod_{i=1}^{n}\phi_{\alpha_{i}}(x_{i})$ (16)

An immediate corollary of Proposition 8.13 from [O’D14] is that
$(\phi_{\alpha})_{\alpha\in\\{0,\pm 1\\}^{n}}$ is a Fourier basis for
$L^{2}(\\{0,\pm 1\\}^{n},\pi_{1/3}^{\otimes n})$. I.e.,
$\phi_{(0,0,\ldots,0)}\equiv 1$ and this basis is orthonormal. Definition 8.14
of [O’D14] now asserts that every function $f\colon\\{0,\pm
1\\}^{n}\to\mathbb{R}$ can be written as

$\displaystyle f(x)=\sum_{\alpha\in\\{0,\pm
1\\}^{n}}\widehat{f}(\alpha)\phi_{\alpha}(x)\text{ where }\widehat{f}=\langle
f,\phi_{\alpha}\rangle=\mathbb{E}_{x}[f(x)\phi_{\alpha}(x)]$ (17)

is the Fourier coefficient of $f$ on $\alpha$.

####  4.1.2 Fourier Concentration for Convex Sets

We use the notation $\\#\alpha:=|\\{i\colon\alpha_{i}\neq 0\\}|$. Our goal is
now to prove the following fact about the Fourier coefficients of convex sets.
Here we abuse notation and use $S\colon\\{0,\pm 1\\}^{n}\to\\{\pm 1\\}$
defined as $S(x)=(-1)^{\mathbf{1}(x\notin S)}$ to denote membership in the set
$S$.

######  Lemma 4.3 (Fourier Concentration for Convex Sets).

There exists a constant $C>0$ such that for any convex set $S\subseteq\\{0,\pm
1\\}^{n}$ and $\varepsilon>0$,

$\sum_{\alpha\colon\\#\alpha>\frac{C}{\varepsilon}n^{3/4}\log^{1/4}n}\widehat{S}(\alpha)^{2}\leq\varepsilon\text{.}$

###### Proof.

The idea is to make use of our upper bound on the influence of convex sets
from Theorem 1.4. We will need the following slightly different definition of
the influence given by [O’D14]. We will refer to this slightly different
notion as _Fourier influence_ and will denote it by
$\mathbb{I}^{\mathsf{Fourier}}(f)$ for clarity. We will show that these
definitions are equivalent up to a constant factor. Below, for $x\in\\{0,\pm
1\\}^{n}$, $i\in[n]$, and $b\in\\{0,\pm 1\\}$, we write $x^{i\leftarrow b}$
for the vector obtained from $x$ by setting $x_{i}$ to $b$.

######  Definition 4.4 (Def. 8.17 and 8.22, [O’D14]).

For $f\in L^{2}(\\{0,\pm 1\\}^{n},\pi_{1/3}^{\otimes n})$ and $i\in[n]$, the
_projection of $f$ onto $i$_ is

$\text{E}_{i}f(x)=\mathbb{E}_{b\in\\{0,\pm 1\\}}[f(x^{i\leftarrow
b})]\text{.}$

The _$i$ ’th coordinate Laplacian operator_ $\text{L}_{i}$ is defined as
$\text{L}_{i}f:=f-\text{E}_{i}f$. The _Fourier influence of coordinate $i$ on
$f$ is _ $\mathbb{I}_{i}^{\mathsf{Fourier}}(f)=\langle
f,\text{L}_{i}f\rangle$. The _total Fourier influence of $f$_ is
$\mathbb{I}^{\mathsf{Fourier}}(f)=\sum_{i=1}^{n}\mathbb{I}_{i}^{\mathsf{Fourier}}(f)$.

We will need the two following identities.

######  Proposition 4.5 (Prop. 8.16 and Prop. 8.23, [O’D14]).

Every $f\in L^{2}(\\{0,\pm 1\\}^{n},\pi_{1/3}^{\otimes n})$ satisfies the
following two identities:

  1. 1.

$\sum_{\alpha\in\\{0,\pm 1\\}^{n}}\widehat{f}(\alpha)^{2}=\mathbb{E}[f^{2}]$

  2. 2.

$\mathbb{I}^{\mathsf{Fourier}}(f)=\sum_{\alpha\in\\{0,\pm
1\\}^{n}}\\#\alpha\cdot\widehat{f}(\alpha)^{2}$

######  Lemma 4.6 (Fourier Concentration from Influence).

Let $\mathcal{F}\colon\\{0,\pm 1\\}^{n}\to\\{\pm 1\\}$ be a class of functions
with Fourier influence upper bounded by $\mathbb{I}^{\mathsf{Fourier}}(f)\leq
B$ for all $f\in\mathcal{F}$. Then, for any $\varepsilon>0$, we have

$\sum_{\alpha\in\\{0,\pm
1\\}^{n}\colon\\#\alpha>B/\varepsilon}\widehat{f}(\alpha)^{2}\leq\varepsilon\text{.}$

###### Proof.

By item (1) of Proposition 4.5, we have $\sum_{\alpha}f(\alpha)^{2}=1$. Thus,
$\sum_{\alpha}\\#\alpha\cdot\widehat{f}(\alpha)^{2}$ is the expectation of
$\\#\alpha$ when $\alpha$ is sampled with probability
$\widehat{f}(\alpha)^{2}$. By item (2) of Proposition 4.5 we have

$\sum_{\alpha\in\\{0,\pm
1\\}^{n}}\\#\alpha\cdot\widehat{f}(\alpha)^{2}=\mathbb{I}^{\mathsf{Fourier}}(f)\leq
B$

and now applying Markov’s inequality yields the desired inequality. ∎

######  Fact 4.7 (Equivalence of Influence Definitions).

For every $f\colon\\{0,\pm 1\\}^{n}\to\\{\pm 1\\}$, we have

$\frac{3}{8}\cdot\mathbb{I}^{\mathsf{Fourier}}(f)\leq\mathbb{I}(f)\leq\frac{3}{4}\cdot\mathbb{I}^{\mathsf{Fourier}}(f)\text{.}$

###### Proof.

Let $\Delta_{i}(f)$ denote the number of lines in the ternary hypercube of the
form $(x^{i\leftarrow-1},x^{i\leftarrow 0},x^{i\leftarrow 1})$ such that
$f_{\\{x^{i\leftarrow-1},x^{i\leftarrow 0},x^{i\leftarrow 1}\\}}$ is not
constant, and let $\Delta(f)=\sum_{i}\Delta_{i}$ be the total number of such
lines. Recall the definition of $\mathbb{I}(f)$ from equation 2 and observe
that since every such line contains either $1$ or $2$ influential edges, we
have $\Delta(f)\cdot 3^{-n}\leq\mathbb{I}(f)\leq 2\Delta(f)\cdot 3^{-n}$. We
will show that $\mathbb{I}^{\mathsf{Fourier}}(f)=\frac{8}{3}\Delta(f)\cdot
3^{-n}$ and combining these observations completes the proof. We have

$\displaystyle\mathbb{I}_{i}^{\mathsf{Fourier}}(f)=\langle
f,\text{L}_{i}f\rangle=\mathbb{E}_{x}\left[f(x)(f(x)-\text{E}_{i}f(x))\right]=\mathbb{E}_{x}\left[1-f(x)\mathbb{E}_{b\in\\{0,\pm
1\\}}[f(x^{i\leftarrow b})]\right]\text{.}$ (18)

Now, for a fixed $x$, consider the line in dimension $i$, containing $x$:
$\ell_{i}(x):=(x^{i\leftarrow-1},x^{i\leftarrow 0},x^{i\leftarrow 1})$.
Observe that if $f$ is constant on $\ell_{i}(x)$, then
$1-f(x)\mathbb{E}_{b\in\\{0,\pm 1\\}}[f(x^{i\leftarrow b})]=0$. If $f$ is non-
constant on $\ell_{i}(x)$, then either it contains two $+1$’s and one $-1$ or
vice versa. In both cases we have

$\displaystyle\mathbb{E}_{a\in\\{0,\pm 1\\}}\left[1-f(x^{i\leftarrow
a})\mathbb{E}_{b\in\\{0,\pm 1\\}}[f(x^{i\leftarrow
b})]\right]=1-\mathbb{E}_{b\in\\{0,\pm 1\\}}[f(x^{i\leftarrow
b})]^{2}=8/9\text{.}$ (19)

Therefore,

$\displaystyle\mathbb{I}_{i}^{\mathsf{Fourier}}(f)$
$\displaystyle=\mathbb{E}_{x}\left[1-f(x)\mathbb{E}_{b\in\\{0,\pm
1\\}}[f(x^{i\leftarrow b})]\right]=\mathbb{E}_{x}\mathbb{E}_{a\in\\{0,\pm
1\\}}\left[1-f(x^{i\leftarrow a})\mathbb{E}_{b\in\\{0,\pm
1\\}}[f(x^{i\leftarrow b})]\right]$
$\displaystyle=\frac{8}{9}\mathbb{E}_{x}\left[\mathbf{1}(f|_{\ell_{i}(x)}\text{
is not constant})\right]=\frac{8}{3}\Delta_{i}(f)\cdot 3^{-n}$

and summing over all $i$ completes the proof. ∎

Combining Theorem 1.4, Lemma 4.6, and 4.7 completes the proof of Lemma 4.3. ∎

####  4.1.3 Low-Degree Learning Algorithm and Proof of Theorem 1.5

Recall that we are using the basis for the space of functions $f\colon\\{0,\pm
1\\}^{n}\to\mathbb{R}$ given by

$\displaystyle\phi_{\alpha}(x):=\prod_{i=1}^{n}\phi_{\alpha_{i}}(x_{i})\text{
\leavevmode\nobreak\ for every\leavevmode\nobreak\ }\alpha\in\\{0,\pm
1\\}^{n}$ (20)

where $\alpha_{-1},\alpha_{0},\alpha_{1}$ are a basis for the space of
functions $f\colon\\{0,\pm 1\\}\to\mathbb{R}$ defined as: $\phi_{0}\equiv 1$,

$(\phi_{-1}(-1),\phi_{-1}(0),\phi_{-1}(1))=(-\sqrt{6}/2,0,\sqrt{6}/2)\text{,
and
}(\phi_{1}(-1),\phi_{1}(0),\phi_{1}(1))=(-\sqrt{2}/2,\sqrt{2},-\sqrt{2}/2)\text{.}$

Recall that $\widehat{f}(\alpha)=\mathbb{E}_{x}[f(x)\phi_{\alpha}(x)]$. Our
learning upper bound Theorem 1.5 follows immediately by combining Lemma 4.3
with the following theorem.

######  Theorem 4.8 (Low-Degree Algorithm over $\\{0,\pm 1\\}^{n}$).

Let $\mathcal{F}\colon\\{0,\pm 1\\}^{n}\to\\{\pm 1\\}$ be a class of functions
such that for $\varepsilon>0$ and $\tau=\tau(\varepsilon,n)$,

$\sum_{\alpha\in\\{0,\pm
1\\}^{n}\colon\\#\alpha>\tau}\widehat{f}(\alpha)\leq\varepsilon\text{.}$

Then $\mathcal{F}$ can be learned with time and sample complexity
$\text{poly}(n^{\tau},1/\varepsilon)$.

###### Proof.

Let $A:=\\{\alpha\in\\{0,\pm 1\\}^{n}\colon\\#\alpha\leq\tau\\}$. Note that
$|A|=\sum_{\Delta=0}^{\tau}{n\choose\Delta}\cdot
2^{\Delta}=\text{poly}(n^{\tau})$. We take $s$ samples
$x_{1},\ldots,x_{s}\in\\{0,\pm 1\\}^{n}$ where $s$ will be chosen later. For
each $\alpha$, we use the empirical estimate
$Z_{\alpha}:=\frac{1}{s}\sum_{i=1}^{s}f(x_{i})\phi_{\alpha}(x_{i})$ and return
the hypothesis

$\displaystyle h(x)=\mathrm{sgn}\left(\sum_{\alpha\in
A}Z_{\alpha}\phi_{\alpha}(x)\right)\text{.}$ (21)

Consider the event that
$|Z_{\alpha}-\widehat{f}(\alpha)|\leq\sqrt{\varepsilon/|A|}$ for all $\alpha$.
We first show that this event occurs with high probability, and then show that
if it occurs, then $h$ is a good hypothesis.

######  Claim 4.9.

Set $s:=\frac{3|A|^{2}}{\varepsilon}=\text{poly}(n^{\tau},1/\varepsilon)$.
Then

$\mathbb{P}_{x_{1},\ldots,x_{s}}\left[|Z_{\alpha}-\widehat{f}(\alpha)|\leq\sqrt{\varepsilon/|A|}\text{
for all }\alpha\in A\right]\text{.}$

###### Proof.

Fix any $\alpha\in A$ and observe that
$Z_{\alpha}=\frac{1}{s}\sum_{i=1}^{s}X_{i}$ where $X_{1},\ldots,X_{s}$ are
independent copies of $X=f(x)\phi_{\alpha}(x)$ for $x\sim\\{0,\pm 1\\}^{n}$
drawn uniformly at random. Note that in the setting of the Boolean hypercube
when one uses the standard basis of parity functions, the random variable $X$
always lies in $\\{\pm 1\\}$. In the ternary hypercube this is not the case
and in fact $|\phi_{\alpha}(x)|$ can be exponentially large. For instance
$\phi_{\vec{1}}(\vec{0})=(\sqrt{2})^{n}$. However, since
$\langle\phi_{\alpha},\phi_{\alpha}\rangle=1$ for all $\alpha$, we’re able to
show that $\mathbf{Var}(X)\leq 1$ and this allows us to obtain good estimates
for $\widehat{f}(\alpha)$. We have

$\sigma^{2}:=\mathbf{Var}(X)=\mathbb{E}_{x}[(f(x)\phi_{\alpha}(x))^{2}]-\mathbb{E}_{x}[f(x)\phi_{\alpha}(x)]^{2}=1-\widehat{f}(\alpha)^{2}$

by definition of the Fourier coefficient $\widehat{f}(\alpha)$ and the fact
that our basis is orthonormal and so in particular
$\mathbb{E}_{x}[\phi_{\alpha}(x)^{2}]=\langle\phi_{\alpha},\phi_{\alpha}\rangle=1$.
Therefore,
$\mathbf{Var}(Z_{\alpha})=\frac{\sigma^{2}}{s}=\frac{1-\widehat{f}(\alpha)^{2}}{s}\leq\frac{1}{s}$.
Note also that $\mathbb{E}[Z_{\alpha}]=\widehat{f}(\alpha)$. Now, by
Chebyshev’s inequality, we have

$\mathbb{P}\left[|Z_{\alpha}-\widehat{f}(\alpha)|\geq\frac{k}{\sqrt{s}}\right]\leq\mathbb{P}\left[|Z_{\alpha}-\widehat{f}(\alpha)|\geq
k\sqrt{\mathbf{Var}(Z_{\alpha})}\right]\leq\frac{1}{k^{2}}.$

Setting $k=\sqrt{3|A|}$ and recalling $s=\frac{3|A|^{2}}{\varepsilon}$ yields

$\mathbb{P}\left[|Z_{\alpha}-\widehat{f}(\alpha)|\geq\sqrt{\varepsilon/|A|}\right]=\mathbb{P}\left[|Z_{\alpha}-\widehat{f}(\alpha)|\geq\frac{k}{\sqrt{s}}\right]\leq\frac{1}{3|A|}$

and taking a union bound over all $\alpha\in A$ completes the proof of the
claim. ∎

######  Claim 4.10.

Using the definition of $h$ in equation 21, if
$|Z_{\alpha}-\widehat{f}(\alpha)|\leq\sqrt{\varepsilon/|A|}$ for all
$\alpha\in A$, then $\mathbb{P}_{x\sim\\{0,\pm 1\\}^{n}}[h(x)\neq
f(x)]\leq\varepsilon$.

###### Proof.

First, observe that

$\displaystyle\mathbb{P}_{x}\left[f(x)\neq
h(x)\right]=\frac{1}{4}\mathbb{E}_{x}\left[(f(x)-h(x))^{2}\right]\text{.}$
(22)

Now, if $f(x)\neq h(x)$, then $\left(f(x)-\sum_{\alpha\in
A}Z_{\alpha}\phi_{\alpha}(x)\right)^{2}\geq 1=\frac{1}{4}(f(x)-h(x))^{2}$.
Clearly if $f(x)=h(x)$, then this inequality also holds. Thus, for any
$x\in\\{0,\pm 1\\}^{n}$, this inequality holds. Combining this observation
with equation 22 yields

$\displaystyle\mathbb{P}_{x}\left[f(x)\neq h(x)\right]$
$\displaystyle\leq\mathbb{E}_{x}\left[\left(f(x)-\sum_{\alpha\in
A}Z_{\alpha}\phi_{\alpha}(x)\right)^{2}\right]\text{.}$ (23)

In the next calculation, for $\alpha\notin A$, let $Z_{\alpha}:=0$. Now,
writing $f(x)=\sum_{\alpha}\widehat{f}(\alpha)\phi_{\alpha}(x)$, expanding the
squared sum, applying linearity of expectation, and using the fact that
$\mathbb{E}_{x}[\phi_{\alpha}(x)\phi_{\alpha^{\prime}}(x)]=\langle\phi_{\alpha},\phi_{\alpha^{\prime}}\rangle=0$
for any $\alpha\neq\alpha^{\prime}$, we get

$\displaystyle\mathbb{E}_{x}\left[\left(\sum_{\alpha}\phi_{\alpha}(x)\left(\widehat{f}(\alpha)-Z_{\alpha}\right)\right)^{2}\right]$
$\displaystyle=\mathbb{E}_{x}\left[\sum_{\alpha,\alpha^{\prime}}\phi_{\alpha}(x)\phi_{\alpha^{\prime}}(x)\left(\widehat{f}(\alpha)-Z_{\alpha}\right)\left(\widehat{f}(\alpha^{\prime})-Z_{\alpha^{\prime}}\right)\right]$
$\displaystyle=\sum_{\alpha,\alpha^{\prime}}\langle\phi_{\alpha},\phi_{\alpha^{\prime}}\rangle\left(\widehat{f}(\alpha)-Z_{\alpha}\right)\left(\widehat{f}(\alpha^{\prime})-Z_{\alpha^{\prime}}\right)$
$\displaystyle=\sum_{\alpha}\left(\widehat{f}(\alpha)-Z_{\alpha}\right)^{2}\text{.}$
(24)

Finally, using equation 23, Section 4.1.3, and the fact that
$|\widehat{f}(\alpha)-Z_{\alpha}|\leq\sqrt{\varepsilon/|A|}$ for $\alpha\in A$
and $\sum_{\alpha\notin A}\widehat{f}(\alpha)^{2}\leq\varepsilon$, yields

$\displaystyle\mathbb{P}_{x}\left[f(x)\neq h(x)\right]$
$\displaystyle\leq\sum_{\alpha}\left(\widehat{f}(\alpha)-Z_{\alpha}\right)^{2}=\sum_{\alpha\in
A}\left(\widehat{f}(\alpha)-Z_{\alpha}\right)^{2}+\sum_{\alpha\notin
A}\widehat{f}(\alpha)^{2}\leq|A|\cdot\frac{\varepsilon}{|A|}+\varepsilon=2\varepsilon$

and this completes the proof of the claim. ∎

Combining 4.9 and 4.10 completes the proof of Theorem 4.8. ∎

###  4.2 Lower Bound

In this section we prove the following lower bound on the _sample complexity_
of convexity testing in the ternary hypercube.

See 1.7

Our proof of Theorem 1.7 follows the standard approach of defining a pair of
distributions $\mathcal{D}_{\mathsf{yes}},\mathcal{D}_{\mathsf{no}}$ over
subsets of $\\{0,\pm 1\\}^{n}$ such that the following hold:

  * •

$\mathcal{D}_{\mathsf{yes}}$ is supported over convex sets.

  * •

Sets drawn from $\mathcal{D}_{\mathsf{no}}$ are typically far from convex:
$\mathbb{P}_{S\sim\mathcal{D}_{\mathsf{no}}}[\varepsilon(S)=\Omega(1)]=\Omega(1)$.

  * •

The distributions over labeled examples from $\mathcal{D}_{\mathsf{yes}}$ and
$\mathcal{D}_{\mathsf{no}}$ are close in TV-distance.

####  4.2.1 The Distributions $\mathcal{D}_{\mathsf{yes}}$ and
$\mathcal{D}_{\mathsf{no}}$

Our construction uses a variant of random Talagrand DNFs adapted to the case
of testing convexity in the ternary hypercube, $\\{0,\pm 1\\}^{n}$. In
particular, our construction is inspired by the approach of [BB16] and [CWX17]
to prove lower bounds for testing monotonicity of functions on the Boolean
hypercube, $\\{0,1\\}^{n}$.

Let $N=3^{\sqrt{n}}$ and choose $N$ _terms_ $t^{(1)},\ldots,t^{(N)}\in\\{0,\pm
1\\}^{n}$ i.i.d. according the following distribution. For each $i\in[N]$:

  1. 1.

Form a (multi)-set $T_{i}$ by taking $\sqrt{n}$ independent uniform samples
from $[n]$.

  2. 2.

For each $a\in T_{i}$, set $t^{(i)}_{a}\in\\{\pm 1\\}$ uniformly at random.
For each $a\notin T_{i}$, set $t^{(i)}_{a}=0$.

Let $\boldsymbol{t}=(t^{(1)},\ldots,t^{(N)})$ denote the random sequence of
terms. Recall the _outward-oriented poset_ (Definition 2.1) over $\\{0,\pm
1\\}^{n}$. For each $i\in[N]$, let

$\displaystyle U_{i}:=\left\\{x\in\mathsf{Mid}(\sqrt{n})\colon x\succeq
t^{(i)}\text{ and }x\not\succeq t^{(j)}\text{ for all
}j\in[N]\setminus\\{i\\}\right\\}$ (25)

denote the set of points in the middle layers of the ternary hypercube which
satisfy the $i$’th term, uniquely. Let $U=\cup_{i=1}^{N}U_{i}$ denote the set
of points which satisfy a unique term.

Sets drawn from $\mathcal{D}_{\mathsf{yes}}$ are generated as follows. Choose
a uniform random assignment $\boldsymbol{\phi}\colon[N]\to\\{0,1\\}$. For
every $x\in\mathsf{Mid}(\sqrt{n})$ define

$S_{\boldsymbol{t},\boldsymbol{\phi}}(x)=\begin{cases}1,&\text{if }\forall
i\in[N]\text{, }x\not\succeq t^{(i)}\\\ 0,&\text{if }\exists i\neq
j\in[N]\text{, }x\succeq t^{(i)}\text{ and }x\succeq t^{(j)}\\\
\boldsymbol{\phi}(i),&\text{if }x\in U_{i}\text{.}\end{cases}$

Sets drawn from $\mathcal{D}_{\mathsf{no}}$ are generated as follows. Choose a
uniform random function $\boldsymbol{r}\colon U\to\\{0,1\\}$. For each
$x\in\mathsf{Mid}(\sqrt{n})$ define

$S_{\boldsymbol{t},\boldsymbol{r}}(x)=\begin{cases}1,&\text{if }\forall
i\in[N]\text{, }x\not\succeq t^{(i)}\\\ 0,&\text{if }\exists i\neq
j\in[N]\text{, }x\succeq t^{(i)}\text{ and }x\succeq t^{(j)}\\\
\boldsymbol{r}(x),&\text{if }x\in U\text{.}\end{cases}$

For $x\notin\mathsf{Mid}(\sqrt{n})$: if $x\in\mathsf{Inn}(\sqrt{n})$, then
both the yes and no distributions assign value $1$ and if
$x\in\mathsf{Out}(\sqrt{n})$, then both the yes and no distributions assign
value $0$.

Theorem 1.7 follows immediately by combining the following three lemmas.

######  Lemma 4.11.

Every set in the support of $\mathcal{D}_{\mathsf{yes}}$ is convex.

###### Proof.

Let $S_{\boldsymbol{t},\boldsymbol{\phi}}\subseteq\\{0,\pm 1\\}^{n}$ be any
set drawn from $\mathcal{D}_{\mathsf{yes}}$. We observe that
$S_{\boldsymbol{t},\boldsymbol{\phi}}$ is non-increasing with respect to the
_outward-oriented poset_ (recall Definition 2.1). Suppose $y\notin
S_{\boldsymbol{t},\boldsymbol{\phi}}$ and let $x\in\mathsf{Up}(y)$ (recall
Definition 2.2). We have three cases depending on where $y$ lies.

  * •

$y\in\mathsf{Out}(\sqrt{n})$: in this case $x\in\mathsf{Out}(\sqrt{n})$ as
well and so $x\notin S_{\boldsymbol{t},\boldsymbol{\phi}}$.

  * •

$y\succeq t^{(i)},t^{(j)}$ for two terms $i\neq j\in[N]$: in this case we have
$x\succeq y\succeq t^{(i)},t^{(j)}$ and so $x\notin
S_{\boldsymbol{t},\boldsymbol{\phi}}$.

  * •

$y\in U_{i}$ for some $i\in[N]$ and $\boldsymbol{\phi}(i)=0$: in this case we
have $x\succeq y\succeq t^{(i)}$ and so either (i) $x\in U_{i}$, (ii) there
exists $j\neq i\in[N]$ for which $x\succeq t^{(j)}$, or (iii)
$x\in\mathsf{Out}(\sqrt{n})$. In all cases $x\notin
S_{\boldsymbol{t},\boldsymbol{\phi}}$.

Since $S_{\boldsymbol{t},\boldsymbol{\phi}}$ is non-increasing we have
$\mathsf{Up}(y)\subset\overline{S_{\boldsymbol{t},\boldsymbol{\phi}}}$ and so
by 2.5 any minimal set of points $X$ such that $y\in\mathsf{Conv}(X)$
satisfies $X\subset\overline{S_{\boldsymbol{t},\boldsymbol{\phi}}}$. Thus
$S_{\boldsymbol{t},\boldsymbol{\phi}}$ is convex by 2.6. ∎

######  Lemma 4.12.

For $S_{\boldsymbol{t},\boldsymbol{r}}\sim\mathcal{D}_{\mathsf{no}}$, we have
$\mathbb{P}_{\boldsymbol{t},\boldsymbol{r}}[\varepsilon(S_{\boldsymbol{t},\boldsymbol{r}})\geq\Omega(1)]\geq\Omega(1)$.

We prove Lemma 4.12 in Section 4.2.2.

######  Lemma 4.13.

Given a collection of points $\boldsymbol{x}=(x_{1},\ldots,x_{s})\in(\\{0,\pm
1\\}^{n})^{s}$ and a set $S\subseteq\\{0,\pm 1\\}^{n}$, let
$(\boldsymbol{x},S(\boldsymbol{x})):=((x_{1},S(x_{1})),\ldots,(x_{s},S(x_{s})))$
denote the corresponding collection of labelled examples. Let
$\mathcal{E}_{\mathsf{yes}}$ and $\mathcal{E}_{\mathsf{no}}$ denote the
distributions over $(\boldsymbol{x},S(\boldsymbol{x}))$ when $\boldsymbol{x}$
consists of $s$ i.i.d. uniform samples and $S\sim\mathcal{D}_{\mathsf{yes}}$
and $S\sim\mathcal{D}_{\mathsf{no}}$, respectively. If $s\leq 3^{\sqrt{n}/3}$,
then the total variation distance between $\mathcal{E}_{\texttt{yes}}$ and
$\mathcal{E}_{\texttt{no}}$ is $o(1)$.

We prove Lemma 4.13 in Section 4.2.3.

####  4.2.2 Sets Drawn from $\mathcal{D}_{\mathsf{no}}$ are Far from Convex:
Proof of Lemma 4.12

###### Proof.

Recall the definition of the set $U$ in equation 25. We prove Lemma 4.12 by
showing that with constant probability over the terms $\boldsymbol{t}$ and the
random function $\boldsymbol{r}\colon U\to\\{0,1\\}$, there exists a
collection $L$ of $\Omega(3^{n})$ disjoint co-linear triples $(x,y,z)$ such
that $x,z\in S_{\boldsymbol{t},\boldsymbol{r}}$, $y\notin
S_{\boldsymbol{t},\boldsymbol{r}}$, and $y=\frac{1}{2}(x+z)$. The existence of
such a set implies that
$\varepsilon(S_{\boldsymbol{t},\boldsymbol{r}})\geq\frac{1}{3}|L|\cdot
3^{-n}=\Omega(1)$ since the membership of at least one point from each of
these triples would need to changed in order to make the set convex.

We first show that there is a large collection $T$ of disjoint co-linear
triples lying in $\mathsf{Mid}(\sqrt{n})$. Then, by 4.16 and fact that each
point in $U$ is included in the set $S_{\boldsymbol{t},\boldsymbol{r}}$ with
probability $1/2$, we can argue that with constant probability, a constant
fraction of the triples in $T$ will be violations of convexity.

######  Claim 4.14.

There exists a set $T$ of $\Omega(3^{n})$ disjoint co-linear triples $(x,y,z)$
such that (a) $x,y,z\in\mathsf{Mid}(\sqrt{n})$, and (b) $y=\frac{1}{2}(x+z)$.

###### Proof.

Given $z\in\\{0,\pm 1\\}^{n-1}$ and $b\in\\{0,\pm 1\\}$, let $(b,z)\in\\{0,\pm
1\\}^{n}$ denote the point whose first coordinate is $b$ and the rest of the
coordinates are given by $z$. Consider the set of disjoint triples

$\displaystyle T:=\left\\{((-1,z),(0,z),(+1,z))\colon z\in\\{0,\pm
1\\}^{n-1}\text{ such that }\left\lVert
z\right\rVert_{1}\in\left[\frac{2n}{3}-\sqrt{n},\frac{2n}{3}+\sqrt{n}-1\right]\right\\}\text{.}$

Observe that every triple $(x,y,z)$ is contained in $\mathsf{Mid}(\sqrt{n})$
and clearly $y=\frac{1}{2}(x+z)$. We use the following fact to lower bound
$|T|$. This fact follows from an application of Stirling’s approximation.

######  Fact 4.15.

For any $N$ and $\ell\in[-O(\sqrt{N}),O(\sqrt{N})]$, we have
${N\choose\frac{2N}{3}+\ell}=\Theta\left(\frac{1}{\sqrt{N}}\cdot\frac{3^{N}}{2^{2N/3}+\ell}\right)$.

By the above fact,

$|T|=\sum_{\ell=-\sqrt{n}}^{\sqrt{n}-1}{n-1\choose\frac{2n}{3}+\ell}2^{2n/3+\ell}=\sum_{\ell=-\sqrt{n}}^{\sqrt{n}-1}\Omega\left(\frac{1}{\sqrt{n-1}}\cdot\frac{3^{n-1}}{2^{2(n-1)/3+\ell}}\right)2^{2n/3+\ell}=\Omega(3^{n})$

and this completes the proof of the claim. ∎

Let $T$ denote the set of $\Omega(3^{n})$ disjoint co-linear triples in
$\mathsf{Mid}(\sqrt{n})$ given by 4.14. We will need the following claim which
shows that triples in $T$ are contained in $U$ with constant probability.

######  Claim 4.16.

For any $(x,y,z)\in T$, we have $\mathbb{P}_{\boldsymbol{t}}[x,y,z\in
U]\geq\frac{1}{1,000,000}$.

###### Proof.

By definition of $T$ we have $x,y,z\in\mathsf{Mid}(\sqrt{n})$ and $x_{1}=+1$,
$y_{1}=0$, $z_{1}=-1$ and $x_{j}=y_{j}=z_{j}$ for all $j\in[2,n]$. Recall the
distribution over the terms $t=(t^{(1)},\ldots,t^{(N)})$ defined in Section
4.2.1. Note that $\mathbb{P}_{t^{(i)}}[t^{(i)}\preceq y]=(\frac{\left\lVert
y\right\rVert_{1}}{2n})^{\sqrt{n}}$ since $t^{(i)}\preceq y$ if and only if
each of the $\sqrt{n}$ non-zero coordinates $a$ of $t^{(i)}$ (a) is chosen as
one of the non-zero coordinates of $y$ which happens with probability
$\left\lVert y\right\rVert/n$ and (b) $t^{(i)}_{a}$ is set to $y_{a}$ which
happens with probability $1/2$. Also note that for a term $t^{(i)}$, we have
$t^{(i)}\prec y$ implies $t^{(i)}\prec x,z$. Therefore,

$\displaystyle\mathbb{P}_{\boldsymbol{t}}[x,y,z\in U_{i}]$
$\displaystyle=\mathbb{P}_{t^{(i)}}[t^{(i)}\preceq x,y,z]\cdot\prod_{j\neq
i}\mathbb{P}_{t^{(j)}}[t^{(j)}\not\preceq x,y,z]$
$\displaystyle=\mathbb{P}_{t^{(i)}}[t^{(i)}\preceq y]\cdot\prod_{j\neq
i}\mathbb{P}_{t^{(j)}}[t^{(j)}\not\preceq x,z]$
$\displaystyle=\mathbb{P}_{t^{(i)}}[t^{(i)}\preceq y]\cdot\prod_{j\neq
i}\left(1-\mathbb{P}_{t^{(j)}}[(t^{(i)}\preceq x)\vee(t^{(i)}\preceq
z)]\right)\text{.}$ (26)

The first term is lower bounded by

$\displaystyle\mathbb{P}_{t^{(i)}}[t^{(i)}\preceq y]=\left(\frac{\left\lVert
y\right\rVert_{1}}{2n}\right)^{\sqrt{n}}\geq\left(\frac{\frac{2n}{3}-\sqrt{n}}{2n}\right)^{\sqrt{n}}=\frac{1}{3^{\sqrt{n}}}\left(1-\frac{3}{2\sqrt{n}}\right)^{\sqrt{n}}\geq\frac{e^{-3/2-o(1)}}{N}\geq\frac{1}{5N}\text{.}$
(27)

To lower bound the second term, observe that

$\displaystyle\mathbb{P}_{t^{(i)}}[t^{(i)}\preceq x]=\left(\frac{\left\lVert
x\right\rVert_{1}}{2n}\right)^{\sqrt{n}}\leq\left(\frac{\frac{2n}{3}+\sqrt{n}}{2n}\right)^{\sqrt{n}}=\frac{1}{3^{\sqrt{n}}}\left(1+\frac{3}{2\sqrt{n}}\right)^{\sqrt{n}}\leq\frac{e^{3/2}}{N}\leq\frac{5}{N}$
(28)

and the same bound holds for the point $z$. Therefore, by a union bound
$\mathbb{P}_{t^{(i)}}[(t^{(i)}\preceq x)\vee(t^{(i)}\preceq z)]\leq 10/N$.
Plugging this bound along with equation 27 into Section 4.2.2 and summing over
all $i\in[N]$ yields

$\displaystyle\mathbb{P}_{\boldsymbol{t}}[x,y,z\in U]$
$\displaystyle=\sum_{i=1}^{N}\mathbb{P}_{t^{(i)}}[t^{(i)}\preceq
y]\cdot\prod_{j\neq i}\left(1-\mathbb{P}_{t^{(j)}}[(t^{(i)}\preceq
x)\vee(t^{(i)}\preceq z)]\right)\geq
N\cdot\frac{1}{5N}\cdot\left(1-\frac{10}{N}\right)^{N}$

which is at least $\frac{1}{1,000,000}$ and this completes the proof. ∎

Now, for a set
$S_{\boldsymbol{t},\boldsymbol{r}}\sim\mathcal{D}_{\mathsf{no}}$, let

$T_{\mathsf{viol}}=\\{(x,y,z)\colon x,z\in
S_{\boldsymbol{t},\boldsymbol{r}}\text{ and }y\notin
S_{\boldsymbol{t},\boldsymbol{r}}\\}$

denote the set of triples in $T$ that are violations of convexity for
$S_{\boldsymbol{t},\boldsymbol{r}}$. By definition of
$\mathcal{D}_{\mathsf{no}}$ and using 4.16, for any fixed $(x,y,z)\in T$, we
have

$\displaystyle\mathbb{P}[(x,y,z)\in
T_{\mathsf{viol}}]=\mathbb{P}_{\boldsymbol{t}}[x,y,z\in
U]\cdot\mathbb{P}_{\boldsymbol{r}}[\boldsymbol{r}(x)=\boldsymbol{r}(z)=1,\boldsymbol{r}(y)=0\leavevmode\nobreak\
|\leavevmode\nobreak\ x,y,z\in U]\geq\frac{1}{8,000,000}.$

Therefore, $\mathbb{E}_{\boldsymbol{t},\boldsymbol{r}}[|T\setminus
T_{\mathsf{viol}}|]\leq|T|(1-\frac{1}{8,000,000})$ and so by Markov’s
inequality

$\displaystyle\mathbb{P}_{\boldsymbol{t},\boldsymbol{r}}\left[|T_{\mathsf{viol}}|\leq\frac{|T|}{8,000,000^{2}}\right]$
$\displaystyle\leq\mathbb{P}_{\boldsymbol{t},\boldsymbol{r}}\left[|T\setminus
T_{\mathsf{viol}}|\geq|T|\left(1-\frac{1}{8,000,000^{2}}\right)\right]$
$\displaystyle=\mathbb{P}_{\boldsymbol{t},\boldsymbol{r}}\left[|T\setminus
T_{\mathsf{viol}}|\geq|T|\left(1-\frac{1}{8,000,000}\right)\left(1+\frac{1}{8,000,000}\right)\right]$
$\displaystyle\leq\mathbb{P}_{\boldsymbol{t},\boldsymbol{r}}\left[|T\setminus
T_{\mathsf{viol}}|\geq\mathbb{E}_{\boldsymbol{t},\boldsymbol{r}}[|T\setminus
T_{\mathsf{viol}}|]\left(1+\frac{1}{8,000,000}\right)\right]$
$\displaystyle\leq\frac{1}{1+\frac{1}{8,000,000}}=1-\frac{1}{8,000,001}\text{.}$

Finally, since $|T|=\Omega(3^{n})$, this gives us

$\displaystyle\mathbb{P}_{\boldsymbol{t},\boldsymbol{r}}\left[\varepsilon(S_{\boldsymbol{t},\boldsymbol{r}})\geq\Omega(1)\right]\geq\mathbb{P}_{\boldsymbol{t},\boldsymbol{r}}\left[|T_{\mathsf{viol}}|\geq\frac{|T|}{8,000,000^{2}}\right]\geq\frac{1}{8,000,001}$

and this completes the proof of Lemma 4.12. ∎

####  4.2.3 $\mathcal{D}_{\mathsf{yes}}$ and $\mathcal{D}_{\mathsf{no}}$ are
Hard to Distinguish: Proof of Lemma 4.13

###### Proof.

Recall the definition of the set $U_{i}$ in equation 25. For $a\neq b\in[s]$,
let $E_{ab}$ denote the event that $x_{a}$ and $x_{b}$ belong to the same
$U_{i}$ for some $i\in[N]$. Observe that conditioned on
$\overline{\vee_{a,b}E_{ab}}$, the distributions $\mathcal{E}_{\mathsf{yes}}$
and $\mathcal{E}_{\mathsf{no}}$ are identical.

Let $x,y\in\\{0,\pm 1\\}^{n}$ denote two independent uniform samples. We have

$\displaystyle\mathbb{P}[E_{ab}]=\mathbb{P}_{x,y,\boldsymbol{t}}\left[\bigvee_{i=1}^{n}(x\in
U_{i}\wedge y\in
U_{i})\right]=\sum_{i=1}^{n}\mathbb{P}_{x,y,\boldsymbol{t}}\left[x\in
U_{i}\wedge y\in U_{i}\right]=\sum_{i=1}^{N}\mathbb{P}_{y,\boldsymbol{t}}[y\in
U_{i}]^{2}$ (29)

where the second equality holds since the $U_{i}$’s are disjoint and the third
equality holds by independence of $x$ and $y$. Now, for a fixed $i\in[N]$, if
$y\notin\mathsf{Mid}(\sqrt{n})$ observe that $\mathbb{P}_{\boldsymbol{t}}[y\in
U_{i}]=0$ and if $y\in\mathsf{Mid}(\sqrt{n})$, we have
$\mathbb{P}_{\boldsymbol{t}}[y\in U_{i}]\leq 5/N$ by equation 28. Thus,
$\mathbb{P}_{y,\boldsymbol{t}}[y\in U_{i}]\leq 5/N$ and combining this with
equation 29 yields $\mathbb{P}[E_{ab}]\leq 25/N$. Finally, by a union bound,
we have

$d_{\text{TV}}(\mathcal{E}_{\mathsf{yes}},\mathcal{E}_{\mathsf{no}})\leq\mathbb{P}_{\boldsymbol{x},\boldsymbol{t}}\left[\bigvee_{a\neq
b\in[s]}E_{ab}\right]\leq s^{2}\cdot\frac{25}{N}=o(1)$

since $N=3^{\sqrt{n}}=\omega(s^{2})$. ∎

##  5 One-Sided Error Testing

###  5.1 Non-Adaptive Upper Bound

We complete the proof of Theorem 1.9 in this section. The upper bound on the
query complexity for testing convexity non-adaptively with one-sided error is
achieved by Algorithm 1. (As a reminder, the notions of upward shadow
$\mathsf{Up}(y)$ and middle layers $\mathsf{Mid}(\ell)$ in the algorithm are
introduced in Definition 2.2 and Section 2.3, respectively.)

Algorithm 1 Convexity tester for sets in $\\{0,\pm 1\\}^{n}$.

Input: A set $S\subseteq\\{0,\pm 1\\}^{n}$ and a parameter
$\varepsilon\in(0,1)$.

Set $\ell:=\sqrt{2n\ln 8/\varepsilon}$ and repeat $\frac{4}{\varepsilon}$
times:

  1. 1.

Query $y\in\\{0,\pm 1\\}^{n}$ uniformly at random.

  2. 2.

If $y\in\overline{S}\cap\mathsf{Mid}(\ell)$, then query all points in
$\mathsf{Up}(y)\cap\mathsf{Mid}(\ell)$.

  3. 3.

If there exists $X\subseteq S\cap\mathsf{Up}(y)\cap\mathsf{Mid}(\ell)$ such
that $y\in\mathsf{Conv}(X)$, then reject.

Accept.

The analysis of Algorithm 1 relies on the following lemma regarding sets that
are far from convex.

######  Lemma 5.1.

Let $S\subseteq\\{0,\pm 1\\}^{n}$ and $\varepsilon\leq\varepsilon(S)$. If
$\ell=\sqrt{2n\ln 8/\varepsilon}$, then

$|\mathsf{Conv}\big{(}S\cap\mathsf{Mid}(\ell)\big{)}\cap\big{(}\overline{S}\cap\mathsf{Mid}(\ell)\big{)}|\geq\frac{\varepsilon}{2}\cdot
3^{n}\text{.}$

In words, there are at least $\frac{\varepsilon}{2}\cdot 3^{n}$ points in the
middle layers $\mathsf{Mid}(\ell)$ that are not in $S$ but that lie in the
convex hull of the portion of $S$ in the middle layers.

###### Proof.

Let $T:=\mathsf{Conv}(S\cap\mathsf{Mid}(\ell))\cap\\{0,\pm 1\\}^{n}$. Clearly,
$T$ is convex and so

$\displaystyle\varepsilon(S)\cdot
3^{n}\leq\Delta(S,T)=|T\cap\overline{S}|+|\overline{T}\cap S|\text{.}$

Now observe that $S\cap\mathsf{Mid}(\ell)\subseteq T$ and so $\overline{T}\cap
S\subseteq\overline{\mathsf{Mid}(\ell)}$. Thus, $|\overline{T}\cap
S|\leq|\overline{\mathsf{Mid}(\ell)}|$. Next, we have

$|T\cap\overline{S}|=|T\cap(\overline{S}\cap\mathsf{Mid}(\ell))|+|T\cap(\overline{S}\cap\overline{\mathsf{Mid}(\ell)})|\leq|T\cap(\overline{S}\cap\mathsf{Mid}(\ell))|+|\overline{\mathsf{Mid}(\ell)}|\text{.}$

By 2.9, $|\overline{\mathsf{Mid}(\ell)}|\leq 2\exp(-\ln(8/\varepsilon))\cdot
3^{n}=\frac{\varepsilon}{4}\cdot 3^{n}$. Therefore, combining the above yields

$\displaystyle|T\cap(\overline{S}\cap\mathsf{Mid}(\ell))|\geq\varepsilon(S)\cdot
3^{n}-2|\overline{\mathsf{Mid}(\ell)}|\geq\left(\varepsilon(S)-\frac{\varepsilon}{2}\right)\cdot
3^{n}\geq\frac{\varepsilon(S)}{2}\cdot 3^{n}$

where the last step holds since $\varepsilon\leq\varepsilon(S)$. ∎

We now prove the correctness of Algorithm 1. The tester always accepts when
$S$ is convex, since in this case
$\mathsf{Conv}(S\cap\mathsf{Mid}(\ell))\subseteq S$. Now suppose
$\varepsilon(S)\geq\varepsilon$. If
$y\in\mathsf{Conv}(S\cap\mathsf{Mid}(\ell))\cap(\overline{S}\cap\mathsf{Mid}(\ell))$,
then there exists some $X\subseteq S\cap\mathsf{Mid}(\ell)$ such that $(X,y)$
is a minimal violating pair. Crucially, 2.5 guarantees that
$X\subseteq\mathsf{Up}(y)$. Thus, if the tester picks such a $y$ in step (1),
then it is guaranteed to reject $S$ since step (2) queries all points in
$\mathsf{Up}(y)\cap\mathsf{Mid}(\ell)$. Therefore, using Lemma 5.1, the
probability that the tester rejects $S$ after one iteration of steps 1-3 is at
least

$\underset{y\in\\{0,\pm
1\\}^{n}}{\mathbb{P}}\left[y\in\mathsf{Conv}(S\cap\mathsf{Mid}(\ell))\cap(\overline{S}\cap\mathsf{Mid}(\ell))\right]\geq\varepsilon/2\text{.}$

Thus, the tester rejects $S$ with probability at least
$1-(1-\varepsilon/2)^{4/\varepsilon}\geq 2/3$.

We now bound the number of queries. I.e., we need to bound the size of
$\mathsf{Up}(y)\cap\mathsf{Mid}(\ell)$ when $y\in\mathsf{Mid}(\ell)$. Note
that each point in this set can be obtained by choosing a set of $2\ell$
coordinates where $y$ has a zero, and then flipping each of these coordinates
to a value in $\\{0,\pm 1\\}$. Therefore, when $y\in\mathsf{Mid}(\ell)$, we
have

$\displaystyle|\mathsf{Up}(y)\cap\mathsf{Mid}(\ell)|\leq\binom{n}{2\ell}\cdot
3^{2\ell}\leq n^{4\ell}=n^{\sqrt{32n\ln 8/\varepsilon}}$

and so the total number of queries made by the tester is at most
$\frac{4}{\varepsilon}\cdot n^{\sqrt{32n\ln 8/\varepsilon}}$. This completes
the proof of Theorem 1.9.

###  5.2 Non-Adaptive Lower Bound

We complete the proof of Theorem 1.10 establishing the lower bound on the
query complexity of non-adaptive convexity testers with one-sided error in
this section. The starting point for the lower bound is the notion of an
_anti-slab_ in $\\{0,\pm 1\\}^{n}$.

######  Definition 5.2 (Slab).

Fix $\tau\geq 1$ and $v\in\\{0,\pm 1\\}^{n}$. The $(\tau,v)$-_slab_ is defined
as

$\mathsf{Slab}_{\tau,v}=\left\\{x\in\\{0,\pm 1\\}^{n}\colon\left|\langle
v,x\rangle\right|\leq\tau\right\\}\text{.}$

We refer to $\overline{\mathsf{Slab}_{\tau,v}}$ as the $(\tau,v)$-_anti-slab_.

Note that a slab is an intersection of two parallel halfspaces and so an anti-
slab is a union of two parallel and disjoint halfspaces. Anti-slabs are
clearly non-convex, and the following claim establishes an important property
of any certificate of non-convexity for the anti-slab. In particular, it shows
that if a set of queries contains a witness of non-convexity for the
$(\tau,v)$-anti-slab, then it must contain two points
$x\in\overline{\mathsf{Slab}_{\tau,v}}$ and $y\in\mathsf{Slab}_{\tau,v}$ whose
projections onto $v$ are separated by at least distance $\tau$.

######  Claim 5.3 (The Structure of Violating Pairs for Anti-slabs).

Suppose $(X,y)$ is a violating pair for the $(\tau,v)$-anti-slab,
$\overline{\mathsf{Slab}_{\tau,v}}$. Then there exists a point $x\in X$ for
which $|\langle v,x-y\rangle|>\tau$.

###### Proof.

We have $y\in\mathsf{Conv}(X)$ and so $\sum_{x\in X}\lambda_{x}x=y$ where
$\sum_{x\in X}\lambda_{x}=1$. Moreover, we have $y\in\mathsf{Slab}_{\tau,v}$
and so

$\displaystyle\sum_{x\in X}\lambda_{x}\langle v,x\rangle=\left\langle
v,\sum_{x\in X}\lambda_{x}x\right\rangle=\langle
v,y\rangle\in[-\tau,\tau]\text{.}$ (30)

We also have $X\subseteq\overline{\mathsf{Slab}_{\tau,v}}$, which implies
$\left|\langle v,x\rangle\right|>\tau$ for all $x\in X$. Therefore, by
equation 30 there clearly has to be some $x\in X$ where $\langle v,x\rangle$
is positive and some $x^{\prime}\in X$ where $\langle v,x^{\prime}\rangle$ is
negative, for otherwise the LHS would be outside the interval $[-\tau,\tau]$.
In particular, this implies $\langle v,x\rangle>\tau$ and $\langle
v,x^{\prime}\rangle<-\tau$ and so

$\langle v,x^{\prime}\rangle<-\tau\leq\langle v,y\rangle\leq\tau<\langle
v,x\rangle\text{.}$

Thus, if $\langle v,y\rangle\leq 0$, then $|\langle v,x-y\rangle|>\tau$, and
if $\langle v,y\rangle\geq 0$, then $|\langle v,x^{\prime}-y\rangle|>\tau$. ∎

We now introduce our hard family of sets: truncated anti-slabs. (As a
reminder, the sets $\mathsf{Inn}(t)$ and $\mathsf{Out}(t)$ are defined in
Section 2.3.)

######  Definition 5.4 (Truncated Anti-slab).

Fix $\tau\geq 1$, $v\in\\{0,\pm 1\\}^{n}$, and $t\geq 1$. The $t$-truncated
$(\tau,v)$-anti-slab is defined as follows:

$\mathsf{TAS}_{\tau,v,t}=\left(\overline{\mathsf{Slab}_{\tau,v}}\cup\mathsf{Inn}(t)\right)\setminus\mathsf{Out}(t)\text{.}$

Figure 4: An illustration of the $t$-truncated $(\tau,v)$-anti-slab. The
dotted circle represents $\\{\pm 1\\}^{n}$ and everything within it is
$\\{0,\pm 1\\}^{n}$. The dark shaded regions are $\mathsf{TAS}_{v}$. The pair
$(\\{x_{1},x_{2},x_{3}\\},y)$ is a violation for the set.

In particular, we fix $\tau=\sqrt{n}$, $t=0.7\sqrt{n}$, and consider vectors
$v\in\\{0,\pm 1\\}^{n}$ for which $\left\lVert v\right\rVert_{1}=n/2$. Thus,
henceforth we will drop the subscripts $\tau,t$ and abbreviate
$\mathsf{TAS}_{v}:=\mathsf{TAS}_{\sqrt{n},v,0.7\sqrt{n}}$.

In other words, $\mathsf{TAS}_{v}$ is the set obtained by taking the
$(\sqrt{n},v)$-anti-slab, adding in all points with fewer than
$\frac{2}{3}n-0.7\sqrt{n}$ non-zero entries, and removing all points with more
than $\frac{2}{3}n+0.7\sqrt{n}$ non-zero entries. The intuition for why these
sets are hard to test (for non-adaptive testers with one-sided error) is as
follows. Suppose a one-sided error tester $T$ has queried a set
$Q\subset\\{0,\pm 1\\}^{n}$ and rejects $\mathsf{TAS}_{v}$. By Corollary 2.8,
$Q$ must contain a minimal violating pair $(X,y)$ for $\mathsf{TAS}_{v}$. Note
that $X\subset\mathsf{TAS}_{v}$, $y\notin\mathsf{TAS}_{v}$, and $y\prec x$ for
all $x\in X$ by 2.5. By 5.3, there is some $x\in X$ such that $|\langle
v,x-y\rangle|>\sqrt{n}$. Additionally, by the truncation, we have
$x\notin\mathsf{Out}(0.7\sqrt{n})$ and $y\notin\mathsf{Inn}(0.7\sqrt{n})$.
Since $y\prec x$, this implies $\left\lVert x-y\right\rVert_{1}\leq
1.4\sqrt{n}$. In summary, for $T$ to reject $\mathsf{TAS}_{v}$ after querying
$Q$, there must be some $y\prec x\in Q$ for which $|\langle
v,x-y\rangle|>\sqrt{n}$, but also $\left\lVert x-y\right\rVert_{1}\leq
1.4\sqrt{n}$.

We consider the family of sets $F=\\{\mathsf{TAS}_{v}\colon\left\lVert
v\right\rVert_{1}=n/2\\}$. By the above argument the lower bound boils down to
the following question: given $y\prec x$ such that $\left\lVert
x-y\right\rVert_{1}\leq 1.4\sqrt{n}$, how many vectors $v\in\\{0,\pm 1\\}^{n}$
(with $\left\lVert v\right\rVert_{1}=n/2$) exist for which $|\langle
v,x-y\rangle|>\sqrt{n}$? We show that this number is upper bounded by
$|F|\cdot\exp(-\Omega(\sqrt{n}))$ and so, by a union bound, the number of sets
in $F$ that $T$ can reject after querying $Q$ is bounded by
$|Q|^{2}\cdot|F|\cdot\exp(-\Omega(\sqrt{n}))$. Therefore, for $T$ to be a
valid non-adaptive tester with one-sided error, we must have
$|Q|^{2}=\exp(\Omega(\sqrt{n}))$ and this gives the result. This argument is
formalized in Section 5.2.1.

Of course, for the above argument to prove Theorem 1.10, we need to show that
truncated anti-slabs are $\Omega(1)$-far from convex.

######  Lemma 5.5.

Consider $v\in\\{0,\pm 1\\}^{n}$ where $\left\lVert
v\right\rVert_{2}^{2}=n/2$. We have
$\mathsf{dist}(\mathsf{TAS}_{v},\mathbf{convex})=\Omega(1)$.

The above Lemma 5.5 is a corollary of the following Lemma 5.6.

######  Lemma 5.6.

Consider $v\in\\{0,\pm 1\\}^{n}$ where $\left\lVert v\right\rVert_{1}=n/2$.
There exists a set $L\subset(\\{0,\pm 1\\}^{n})^{3}$ of $\Omega(3^{n})$
disjoint colinear triples such that for every $(x,y,z)\in L$ the following
hold.

  1. 1.

$y=\frac{x+z}{2}$ and $y\in\mathsf{Slab}_{\sqrt{n},v}$,
$x,z\in\overline{\mathsf{Slab}_{\sqrt{n},v}}$.

  2. 2.

$x,y,z\in\mathsf{Mid}(0.7\sqrt{n})$.

In Section 5.2.1 we prove Theorem 1.10 using 5.3 and Lemma 5.5. In Section
5.2.2 we prove Lemma 5.6, which immediately implies Lemma 5.5.

####  5.2.1 Proof of the Lower Bound

Recall the definition of $\mathsf{Inn}(t)$, $\mathsf{Mid}(t)$, and
$\mathsf{Out}(t)$ in Section 2.3. Given $v\in\\{0,\pm 1\\}^{n}$, recall that

$\displaystyle\mathsf{TAS}_{v}$
$\displaystyle=\left(\overline{\mathsf{Slab}_{\sqrt{n},v}}\cup\mathsf{Inn}(0.7\sqrt{n})\right)\setminus\mathsf{Out}(0.7\sqrt{n})$

is the $0.7\sqrt{n}$-truncated $(\sqrt{n},v)$-anti-slab (Definition 5.4). Let
$V$ denote the set of all vectors $v\in\\{0,\pm 1\\}^{n}$ where $\left\lVert
v\right\rVert_{2}^{2}=n/2$. By Lemma 5.5, we have
$\mathsf{dist}(\mathsf{TAS}_{v},\textbf{convex})=\Omega(1)$ for all $v\in V$.
Also note that $|V|=\binom{n}{n/2}\cdot 2^{n/2}=2^{3n/2}/\Theta(\sqrt{n})$.

Given $x,y\in\\{0,\pm 1\\}^{n}$, let $\Delta(x,y)=\\{i\in[n]\colon x_{i}\neq
y_{i}\\}$. For $v\in\\{0,\pm 1\\}^{n}$, let $\mathsf{NZ}_{v}=\\{i\colon
v_{i}\neq 0\\}$. Let $T$ be a one-sided error, non-adaptive tester for convex
sets in $\\{0,\pm 1\\}^{n}$.

######  Claim 5.7.

Fix $v\in V$ and suppose that $T$ rejects $\mathsf{TAS}_{v}$ after querying a
set $Q\subseteq\\{0,\pm 1\\}^{n}$. Then there exists $x\neq y\in Q$ such that
(a) $|\Delta(x,y)|\leq 1.4\sqrt{n}$ and (b)
$|\Delta(x,y)\cap\mathsf{NZ}_{v}|>\sqrt{n}$.

###### Proof.

By Corollary 2.8, $Q$ must contain a minimal violating pair $(X,y)$ for
$\mathsf{TAS}_{v}$. By 5.3, there exists $x\in X$ for which $|\langle
y-x,v\rangle|>\sqrt{n}$. Observe that
$|\Delta(x,y)\cap\mathsf{NZ}_{v}|\geq|\langle y-x,v\rangle|$ and so (b) holds.

Now, since $(X,y)$ is a violating pair we have $x\in\mathsf{TAS}_{v}$ and
$y\notin\mathsf{TAS}_{v}$ and since $(X,y)$ is minimal, 2.5 implies that
$y\prec x$. By construction, we have
$\mathsf{Inn}(0.7\sqrt{n})\subseteq\mathsf{TAS}_{v}$ and
$\mathsf{Out}(0.7\sqrt{n})\subseteq\overline{\mathsf{TAS}_{v}}$ and so it must
be the case that $x,y\in\mathsf{Mid}(0.7\sqrt{n})$. In summary, $x$ can be
obtained by changing at most $1.4\sqrt{n}$ zero values in $y$ to non-zero
values. Thus, (a) holds. ∎

Now, given $x,y\in\\{0,\pm 1\\}^{n}$, let

$\displaystyle V(x,y)=\Big{\\{}v\in
V\colon|\Delta(x,y)\cap\mathsf{NZ}_{v}|>\sqrt{n}\Big{\\}}\subseteq V\text{.}$
(31)

######  Claim 5.8.

If $|\Delta(x,y)|\leq 1.4\sqrt{n}$, then $|V(x,y)|\leq O(|V|)\cdot
2^{-0.08\sqrt{n}}$.

###### Proof.

Note that $|\mathsf{NZ}_{v}|=n/2$ for all $v\in V$ and so $|V(x,y)|$ can be
bounded as follows. In the following calculation, a vector $v\in V(x,y)$ is
chosen by picking $\ell>\sqrt{n}$ coordinates from $\Delta(x,y)$ and
$n/2-\ell$ coordinates from $[n]\setminus\Delta(x,y)$ to be non-zero. Then
each of these coordinates is fixed to a value in $\\{\pm 1\\}$.

$\displaystyle|V(x,y)|$
$\displaystyle=\sum_{\ell>\sqrt{n}}\binom{|\Delta(x,y)|}{\ell}\binom{n-|\Delta(x,y)|}{n/2-\ell}2^{n/2}$
$\displaystyle\leq
2^{n/2}\binom{n-|\Delta(x,y)|}{n/2-\sqrt{n}}\sum_{\ell>\sqrt{n}}\binom{|\Delta(x,y)|}{\ell}$
$\displaystyle=\frac{2^{3n/2}}{\Theta(\sqrt{n})}\cdot
2^{-|\Delta(x,y)|}\sum_{\ell>\sqrt{n}}\binom{|\Delta(x,y)|}{\ell}=O(|V|)\cdot
2^{-|\Delta(x,y)|}\sum_{\ell>\sqrt{n}}\binom{|\Delta(x,y)|}{\ell}$ (32)

To bound the RHS, observe that
$2^{-k}\cdot\sum_{\ell>\sqrt{n}}\binom{k}{\ell}$ is precisely the probability
that a random subset $S\subseteq[k]$ has size $|S|>\sqrt{n}$, which is a
monotone increasing function of $k$. Thus, the RHS of Section 5.2.1 is a
monotone increasing function of $|\Delta(x,y)|$ and so is maximized by setting
$\Delta(x,y)=1.4\sqrt{n}$. Thus,

$\displaystyle|V(x,y)|$ $\displaystyle\leq O(|V|)\cdot
2^{-1.4\sqrt{n}}\sum_{\ell>\sqrt{n}}\binom{1.4\sqrt{n}}{\ell}$
$\displaystyle\leq O(|V|)\cdot
2^{-1.4\sqrt{n}}\cdot\sqrt{n}\cdot\binom{1.4\sqrt{n}}{\sqrt{n}}\leq
O(|V|)\cdot 2^{-0.08\sqrt{n}}\text{.}$

The last inequality holds by the well known bound ${m\choose
k}\leq\left(\frac{em}{k}\right)^{k}$ as follows. We have
${1.4\sqrt{n}\choose\sqrt{n}}={1.4\sqrt{n}\choose
0.4\sqrt{n}}\leq(\frac{e\cdot
1.4}{0.4})^{0.4\sqrt{n}}=2^{0.4\log_{2}(1.4e/0.4)\sqrt{n}}<2^{1.31\sqrt{n}}$.
∎

Now, given a set of queries $Q\subseteq\\{0,\pm 1\\}^{n}$, let

$\displaystyle V(Q)=\Big{\\{}v\in V\colon\exists x\neq y\in Q\text{ such that
}|\Delta(x,y)\cap\mathsf{NZ}_{v}|>\sqrt{n}\text{ and }|\Delta(x,y)|\leq
1.4\sqrt{n}\Big{\\}}\subseteq V\text{.}$ (33)

By 5.7, if $T$ rejects $\mathsf{TAS}_{v}$ after querying the set $Q$, then
$v\in V(Q)$. Informally, $V(Q)$ contains all $v$ for which $Q$ can contain a
witness of non-convexity for the set $\mathsf{TAS}_{v}$. Moreover, by 5.8 and
the union bound, we have

$\displaystyle\left|V(Q)\right|\leq\sum_{x,y\in
Q}\left|V(x,y)\right|\leq|Q|^{2}\cdot O(|V|)\cdot 2^{-0.08\sqrt{n}}\text{.}$
(34)

Now, let $Q$ be the set of $q$ queries sampled according to the distribution