# Optimal Testing for Planted Satisfiability Problems

Quentin<EMAIL_ADDRESS>[ Department of Computing
and Mathematical Sciences
California Institute of Technology
Pasadena, CA 91125, USA

###### Abstract

We study the problem of detecting planted solutions in a random satisfiability
formula. Adopting the formalism of hypothesis testing in statistical analysis,
we describe the minimax optimal rates of detection. Our analysis relies on the
study of the number of satisfying assignments, for which we prove new results.
We also address algorithmic issues, and give a computationally efficient test
with optimal statistical performance. This result is compared to an average-
case hypothesis on the hardness of refuting satisfiability of random formulas.

62C20,

68R01, 60C05,

Satisfiability problem, High-dimensional detection, Polynomial-time
algorithms,

###### keywords:

[class=AMS]

###### keywords:

t1The author thanks Philippe Rigollet, Emmanuel Abbé, Dan Vilenchick and Amin
Coja-Oghlan for very helpful discussions. t2Partially supported by NSF grant
CAREER-DMS-1053987 when the author was at Princeton University, and by AFOSR
grant FA9550-14-1-0098.

###### Contents

  1. 1 Problem description
  2. 2 Optimal testing
    1. 2.1 Likelihood-ratio test
    2. 2.2 Information-theoretic lower bound
  3. 3 Polynomial-time testing
    1. 3.1 Variable coupling test
    2. 3.2 Hardness hypothesis on random instances
  4. 4 Alternative choices for planting distributions
  5. A Proofs of technical results

## Introduction

We study in this paper the problem of detecting a planted solution in a random
$k$-SAT formula of $m$ clauses on $n$ variables. This is formulated as a
hypothesis testing problem: Given a formula $\phi$, our goal is to decide
whether it is a typical instance, drawn uniformly among all formulas, or if it
has been drawn such that it is guaranteed to be satisfiable, by planting a
solution.

There is a resurgence in statistics of hypothesis testing problems, i.e.,
distinguishing null hypotheses with pure noise, against the presence of a
structured signal in a high-dimensional setting. The seminal work of [Ing82,
Ing98, DJ04], on the problem of detecting sparse or weakly sparse signals in
high dimension has inspired a wide literature of detection problems. Examples
include [ITV10] in the context of sparse linear regression, [ACCD11, BI13,
ACV13, MW13] for small cliques or communities in graphs and matrices,
[ABBDL10] for general combinatorial structured signals, and [ACBL12, BR12,
BR13] for sparse principal components of covariance matrices. These problems
are combinatorial in nature, and the complexity of the class of possible
signals (sparse vectors, cliques in a graph, small submatrices, or here the
$n$-dimensional hypercube) has a direct influence on the statistical and
algorithmic difficulties of the detection problem.

Minimax theory gives a formal definition of the statistical complexity of a
hypothesis testing problem, in terms of the sample size needed to identify
with high probability the underlying distribution of given instances. It
describes the interplay between the interesting parameters of a problem:
sample size, ambient dimension, signal-to-noise ratio, sparsity, underlying
dimension, etc.

This framework is particularly adapted to the study of random instances of
$k$-SAT formulas: a random formula $\phi$ can be interpreted as $m$
independent, identically distributed clauses, each on $k$ of the $n$
variables. The uniform distribution is equivalent to pure noise, the absence
of signal. Planting a solution is equivalent to changing the distribution of
the clauses, dependent on an assignment $x\in\\{0,1\\}^{n}$. This planted
satisfying assignment is the signal whose presence we seek to detect. The
optimal rate of detection will describe how large $m$ (the sample size) needs
to be for detection to be possible, as a function of $n$ (the ambient
dimension), and $k$, treated as a constant.

The properties of random instances of uniform $k$-SAT formulas have been
widely studied in the probability and statistical physics literature.
Particular attention has been paid to the notions of satisfiability thresholds
(sharp changes of behavior when the clause-to-variable density ratio
$\Delta=m/n$ varies) [AP04, AM06, CO09, COP13, CO13, DSS14], maximum
satisfiability [ANP03] geometry of the space of solutions [ANP03, ART06,
ACO08, KMRT+06, MRT09], and concentration of specific statistics [AM10, AM13].
The planted distribution has also been studied, often in order to create
random instances that are known to be satisfiable, such as in [BHL+01, HJKN06,
AGKS00, AJM04, ACO08, JMS05], and at high density in [AMZ06, CoKV07, FMV06].
Methods from statistical physics such as belief and survey propagation have
been applied to this problem and rigorously studied [BMZ02, MPZ02, MZ02,
CO10]. More recently, the algorithmic complexity (in a specific computational
model) of estimating the planted assignment has been studied in [FPV13].

Here, the use of tools from statistical analysis, such as the likelihood ratio
and the total variation distance, highlights the importance of a specific
statistic: the number of satisfying assignments. More specifically, we study
its deviations from its expected value. Optimal rates of detection are
obtained by proving new results concerning the concentration (or absence
thereof) of this statistic. We address algorithmic issues by showing that the
optimal rates of detection can be obtained by a newly introduced polynomial-
time test. We also show the effect of choosing a different planting
distribution on the detection problem, particularly on the optimal rates of
detection.

The following subsection introduces notations for $k$-SAT formulas. Our
hypothesis testing problem is formally described in Section 1. The optimal
rates of detection are derived in Section 2, and the problem of testing in
polynomial time is addressed in Section 3. The effect on the detection rates
of different choices for the planting distributions is studied in Section 4.

### Notations for $k$-SAT formulas

Let $n$ and $m$ be positive integers. For all fixed positive integers $k$, we
denote by $\mathcal{F}_{n,m}^{k}$ the set of boolean formulas on $n$ variables
that are the conjunction of $m$ disjunctions of $k$ distinct literals.
Formally, for all $\phi\in\mathcal{F}_{n,m}^{k}$, we have for all
$x\in\\{0,1\\}^{n}$

$\phi(x)=\bigwedge_{i=1}^{m}C_{i}(x)\,,$

where for all $i\in\\{1,\ldots,m\\}$, the clause $C_{i}$ is the disjunction of
$k$ literals on $k$ distinct variables, i.e., the value of a variable or its
negation

$C_{i}(x)=\ell_{i,1}\vee\ldots\vee\ell_{i,k}\,,\;\ell_{i,j}\in\\{x_{1},\bar{x}_{1},\ldots,x_{n},\bar{x}_{n}\\}\,,\text{and
}\ell_{i,j}\notin\\{\ell_{i,j^{\prime}},\bar{\ell}_{i,j^{\prime}}\\}.$

The $k$-SAT problem (short for satisfiability) is the decision problem of
determining whether a given formula $\phi$ is satisfiable, i.e., if there
exists $x\in\\{0,1\\}^{n}$ such that $\phi(x)$ evaluates to ’true’. For a
given $k$-SAT formula $\phi$, we denote by $\mathcal{S}(\phi)$ the set of
satisfying assignments

$\mathcal{S}(\phi)=\big{\\{}x\in\\{0,1\\}^{n}:\phi(x)=\,\text{{\sf'true'}}\big{\\}}\,,$

and by $Z(\phi)=|\mathcal{S}(\phi)|$ the number of satisfying assignments for
$\phi$. We often write $Z$ when it is not ambiguous. For a subset $S$ of
$\\{1,\ldots,m\\}$, we define the sub-formula

$\phi_{S}=\bigwedge_{i\in S}C_{i}\,.$

The definition of satisfying assignments extends to single clauses and sub-
formulas in general, with the notations $\mathcal{S}(C_{i})$ and
$\mathcal{S}(\phi_{S})$ for the set of assignments satisfying respectively,
the clause $C_{i}$ or the formula $\phi_{S}$. We denote by ${\sf SAT}$ the set
of satisfiable formulas: those with satisfying assignments.

##  1 Problem description

We are interested in distinguishing two distributions on
$\mathcal{F}^{k}_{m,n}$, the uniform, and planted distributions. The uniform
distribution, denoted by $\mathbf{P}_{\text{unif}}$, is generated by
independently selecting each clause uniformly from the $2^{k}{n\choose k}$
possible choices. The planted distribution, denoted by
$\mathbf{P}_{\text{planted}}$, is generated by randomly selecting an
assignment $x^{*}$ uniformly among the $2^{n}$ elements of $\\{0,1\\}^{n}$,
and then independently selecting all the clauses among the $(2^{k}-1){n\choose
k}$ clauses that are satisfied by $x^{*}$ (denoted by $\mathbf{P}_{x^{*}}$).
Each clause is given as $k$ literals, in a uniformly random order. We
represent this as a hypothesis testing problem, on the observation
$\phi\in\mathcal{F}^{k}_{m,n}$

$\displaystyle H_{0}$ $\displaystyle:$
$\displaystyle\phi\sim\mathbf{P}_{\text{unif}}$ $\displaystyle H_{1}$
$\displaystyle:$
$\displaystyle\phi\sim\mathbf{P}_{\text{planted}}=\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}\mathbf{P}_{x}\,.$

It is also possible to consider the detection problem with composite
alternative hypothesis over the $\mathbf{P}_{x}$. Our formulation is
equivalent to choosing a uniform prior over the planted assignments, and to
consider the distribution $\mathbf{P}_{\text{planted}}$, mixture of the
$\mathbf{P}_{x}$. We will mention two regimes: the linear regime, when
$m=\Delta n$, for some $\Delta>0$, usually the only one considered in the
probability theory literature; and the square-root regime, when $m=C\sqrt{n}$,
for some $C>0$, particularly relevant to the study of our statistical problem.
We will often consider $m,n$ large enough, but will mainly focus on non-
asymptotic results.

We define a test as a measurable function
$\Psi:\mathcal{F}^{k}_{m,n}\rightarrow\\{0,1\\}$, whose goal is to determine
the underlying distribution of the observation $\phi$. We define the
probability of error as the maximum of the probabilities of type I and type II
error, formally

$\mathbf{P}_{\text{unif}}(\Psi(\phi)=1)\vee\mathbf{P}_{\text{planted}}(\Psi(\phi)=0)\,.$

This quantity is used here to measure the success of any test $\Psi$. We will
consider that a test is successful when its probability of error is smaller
than $\delta\in(0,1)$, considered fixed for the whole problem, such as
$\delta=0.05$.

We can make the simple observation that under the planted distribution,
formulas are guaranteed to be satisfiable. This suggests to test
satisfiability of the formula in order to solve the hypothesis testing
problem. This test has a probability of error of type II equal to zero. Under
the uniform distribution, the behavior of
$\mathbf{P}_{\text{unif}}(\phi\in\text{\sf SAT})$ has been extensively
studied, and a phase transition has been shown to exist in the linear regime
of $m=\Delta n$, from satisfiability to unsatisfiability, around some
$\Delta_{k}$ close to $2^{k}\log(2)$. We refer to [COP13, CO13] and references
therein for more information, as well as [DSS14] for a proof of the sharpness
of the phase transition, for $k$ large enough. In this setting, when
$\Delta>\Delta_{k}$, the satisfiability test $\Psi_{\text{\sf
SAT}}=\mathbf{1}\\{\cdot\in\text{\sf SAT}\\}$ has a probability of error going
to 0, and when $\Delta<\Delta_{k}$, the error will converge to 1 (entirely
because of the probability of a type I error).

When thinking of the formula $\phi$ as a sequence of $m$ i.i.d. clauses, $m$
can be interpreted as the sample size, and the problem becomes easier when
$\Delta$ increases. When $\Delta$ is too small, the probability of error of
the test $\Psi_{\text{\sf SAT}}$ converges to 1. We see in the following
section that this simple rate can be significantly improved.

##  2 Optimal testing

In this section, we derive the optimal rate of detection for this problem,
i.e., how large $m$ should be for a test to be able to distinguish with high
probability the two hypotheses. We prove that the likelihood-ratio test is
successful in the square-root regime, and show that it is information-
theoretic optimal.

###  2.1 Likelihood-ratio test

A test based on the likelihood ratio between the two candidate distributions
can distinguish between them with high probability, in the square-root regime.
When $m\geq C\sqrt{n}$ for a specific constant $C$, the probability of error
of the likelihood-ratio test is smaller than $\delta\in(0,1)$.

######  Theorem 2.1.

For all $k\geq 2$, positive $m,n$, denote $\Psi_{\text{\sf LR}}$ the
likelihood-ratio test defined by

$\Psi_{\text{\sf
LR}}(\phi)=\mathbf{1}\\{Z(\phi)>\mathbf{E}_{\text{unif}}[Z]\\}\,.$ (1)

For any $\delta\in(0,1)$, there exists $\bar{C}_{k,\delta}>0$ such that for
$m\geq\bar{C}_{k,\delta}\sqrt{n}$, for $m,n$ large enough, it holds

$\mathbf{P}_{\text{unif}}(\Psi_{\text{\sf
LR}}(\phi)=1)\vee\mathbf{P}_{\text{planted}}(\Psi_{\text{\sf
LR}}(\phi)=0)\leq\delta\,.$

Proof  We first prove that the likelihood-ratio test has indeed form (1). For
discrete distributions, the likelihood ratio is simply equal to the ratio of
the two distributions. For all $\phi\in\mathcal{F}^{k}_{m,n}$, it holds

$\frac{\mathbf{P}_{\text{planted}}(\phi)}{\mathbf{P}_{\text{unif}}(\phi)}=\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}\frac{\mathbf{P}_{x}(\phi)}{\mathbf{P}_{\text{unif}}(\phi)}\,.$

To compute the probabilities in the above ratios, we can interpret the drawing
of $\phi$ by placing $m$ balls in $N=2^{k}{n\choose k}$ bins independently -
if it has distribution $\mathbf{P}_{\text{unif}}$ \- or otherwise in the
$N_{k}=(2^{k}-1){n\choose k}$ bins corresponding to clauses that are satisfied
by $x$. Therefore, it holds for all $\phi$

$\frac{\mathbf{P}_{x}(\phi)}{\mathbf{P}_{\text{unif}}(\phi)}=\left\\{\begin{array}[]{rl}0&\;\text{if
}x\notin\mathcal{S}(\phi)\\\
\Big{(}\frac{N}{N_{k}}\Big{)}^{m}&\;\text{otherwise }\end{array}\right.$

It can then be expressed in terms of $\mathbf{1}\\{x\in\mathcal{S}(\phi)\\}$,
and $N/N_{k}=1/(1-2^{-k})$

$\displaystyle\frac{\mathbf{P}_{\text{planted}}}{\mathbf{P}_{\text{unif}}}(\phi)$
$\displaystyle=$
$\displaystyle\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}\Big{(}\frac{N}{N_{k}}\Big{)}^{m}\mathbf{1}\\{x\in\mathcal{S}(\phi)\\}$
$\displaystyle=$
$\displaystyle\frac{1}{\mathbf{E}_{\text{unif}}[Z(\phi)]}\sum_{x\in\\{0,1\\}^{n}}\mathbf{1}\\{x\in\mathcal{S}(\phi)\\}=\frac{Z(\phi)}{\mathbf{E}_{\text{unif}}[Z(\phi)]}\,,$

by the known closed form of
$\mathbf{E}_{\text{unif}}[Z(\phi)]=2^{n}(1-2^{-k})^{m}$, which can be directly
derived by linearity. The likelihood-ratio test is therefore indeed
$\Psi_{\text{\sf
LR}}(\phi)=\mathbf{1}\\{Z(\phi)>\mathbf{E}_{\text{unif}}[Z(\phi)]\\}$. It is
now sufficient to prove
$\mathbf{P}_{\text{unif}}(\Psi(\phi)=1)+\mathbf{P}_{\text{planted}}(\Psi(\phi)=0)\leq\delta$,
as the maximum of two nonnegative numbers is smaller than their sum. By
definition of the likelihood-ratio test,

$\mathbf{P}_{\text{unif}}(\Psi_{\text{\sf
LR}}(\phi)=1)+\mathbf{P}_{\text{planted}}(\Psi_{\text{\sf
LR}}(\phi)=0)=1-d_{TV}(\mathbf{P}_{\text{unif}},\mathbf{P}_{\text{planted}})\,.$

Furthermore, by definition of the total variation distance

$\displaystyle d_{TV}(\mathbf{P}_{\text{unif}},\mathbf{P}_{\text{planted}})$
$\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}\phi\in\mathcal{F}^{k}_{m,n}\\\
\mathbf{P}_{\text{unif}}(\phi)>\mathbf{P}_{\text{planted}}(\phi)\end{subarray}}\\{\mathbf{P}_{\text{unif}}-\mathbf{P}_{\text{planted}}\\}(\phi)$
$\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}\phi\in\mathcal{F}^{k}_{m,n}\\\
Z(\phi)/\mathbf{E}[Z]<1\end{subarray}}\Big{(}1-\frac{Z(\phi)}{\mathbf{E}[Z]}\Big{)}\mathbf{P}_{\text{unif}}(\phi)$
$\displaystyle=$
$\displaystyle\mathbf{E}_{\text{unif}}\Big{[}\Big{(}1-\frac{Z(\phi)}{\mathbf{E}[Z]}\Big{)}_{+}\Big{]}\,.$

The total variation distance between distributions of i.i.d. elements being
non-decreasing in the sample size, we obtain by Lemma 2.2 that in the square-
root regime, for $C$ large enough and $m\geq C\sqrt{n}$,

$d_{TV}(\mathbf{P}_{\text{unif}},\mathbf{P}_{\text{planted}})\geq(1-e^{-\gamma_{k}C^{2}/C_{0}})(1-C_{0}/C^{2})\,.$

This bound yields the desired result for some large enough constant
$C_{k,\delta}>0$.

The proof of this theorem indicates that it is possible to distinguish the two
distributions whenever $Z$ is not concentrated around its expectation under
the uniform distribution. Our result is a consequence of the following lemma,
that states that in the square-root regime, for a constant $C$ large enough,
the ratio $Z/\mathbf{E}[Z]$ is much smaller than 1, with high probability.

######  Lemma 2.2.

For all $k\geq 2$, $C_{0}$ an absolute constant, $m=C\sqrt{n}$, and $C,n$
large enough, it holds with probability $1-C_{0}/C^{2}$,for some constant
$\gamma_{k}>0$ that

$Z<e^{-\gamma_{k}C^{2}/C_{0}}\,\mathbf{E}[Z]\,.$

A stronger result, concerning the linear regime, can be derived similarly in
order to answer a question regarding the behavior of $Z$ with respect to its
expectation. It is known [AM10] that for $\Delta$ small enough and
$n\rightarrow+\infty$, $n^{-1}\log(Z)$ and $n^{-1}\mathbf{E}[\log(Z)]$ have
the same limit, called the quenched average. In the following lemma, we prove
that this limit is actually different from the constant
$n^{-1}\log(\mathbf{E}[Z])$, called the annealed average, for all $\Delta>0$.

######  Lemma 2.3.

For all $k\geq 2$, $\Delta>0$, and $m=\Delta n$ large enough, if
$\phi\sim\mathbf{P}_{\text{unif}}$, it holds with probability $1-o(1)$, for
some constant $c_{k,\Delta}>0$ that

$Z<e^{-c_{k,\Delta}n}\,\mathbf{E}[Z]\,.$

This result is tangential to the problem at hand but of interest in and of
itself. We show here that the quenched and annealed averages are different for
all $\Delta$ and $k$, with a gap greater than $c_{k,\Delta}$, for which we
give no explicit formula. This phenomenon is hinted at in [ACO08, CO09], and
proven to hold for $\Delta$ large enough in [COP13], with an explicit lower
bound for the gap. We provide a proof for Lemma 2.2 and 2.3 in Appendix A.

###  2.2 Information-theoretic lower bound

The proof of Theorem 2.1 also hints at a lower bounds for the statistical
problem. The total variation distance $d_{TV}$ between the uniform and planted
distributions is close to 0 (and the statistical problem is impossible) when
$Z(\phi)$ is concentrated around its expectation.

The number of satisfying assignments is actually equal to its expectation
whenever no variable appears in two different clauses. Indeed, when this is
the case, the set of satisfying assignments can be described thus. There are
$m$ clauses on $m$ distinct groups of $k$ distinct variables. Each clause
allows a specific group of $k$ variables to take $2^{k}-1$ values, and the
$n-km$ remaining variables are free. There are therefore $(2^{k}-1)^{m}$
possible values for the constrained variables and $2^{n-km}$ possible values
for the $n-km$ remaining. Overall,
$Z=(2^{k}-1)^{m}2^{n-km}=2^{n}(1-2^{-k})^{m}=\mathbf{E}[Z]$. This observation
yields the following lower bound.

######  Theorem 2.4.

For $\nu\in(0,1/2)$, $m\leq 2\sqrt{\nu n}/k$, and $m,n$ large enough, it holds
that

$\inf_{\Psi}\big{\\{}\mathbf{P}_{\text{unif}}(\Psi(\phi)=1)\vee\mathbf{P}_{\text{planted}}(\Psi(\phi)=0)\big{\\}}\geq\frac{1}{2}-\nu\,.$

Proof  We use the total variation bound, for any test $\Psi$

$\displaystyle\mathbf{P}_{\text{unif}}(\Psi(\phi)=1)\vee\mathbf{P}_{\text{planted}}(\Psi(\phi)=0)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\big{(}\mathbf{P}_{\text{unif}}(\Psi(\phi)=1)+\mathbf{P}_{\text{planted}}(\Psi(\phi)=0)\big{)}$
$\displaystyle\geq$
$\displaystyle\frac{1-d_{TV}(\mathbf{P}_{\text{unif}},\mathbf{P}_{\text{planted}})}{2}\,.$

We denote by $F$ the set of formulas where no variable appears in two
different clauses.

$\displaystyle d_{TV}(\mathbf{P}_{\text{unif}},\mathbf{P}_{\text{planted}})$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{\phi\in\mathcal{F}^{k}_{m,n}}|\mathbf{P}_{\text{unif}}-\mathbf{P}_{\text{planted}}|(\phi)$
$\displaystyle=$ $\displaystyle\frac{1}{2}\sum_{\phi\in
F}|\mathbf{P}_{\text{unif}}-\mathbf{P}_{\text{planted}}|(\phi)+\frac{1}{2}\sum_{\phi\in
F^{c}}|\mathbf{P}_{\text{unif}}-\mathbf{P}_{\text{planted}}|(\phi)$
$\displaystyle=$ $\displaystyle\frac{1}{2}\sum_{\phi\in
F}\Big{|}\frac{Z(\phi)}{\mathbf{E}[Z]}-1\Big{|}\mathbf{P}_{\text{unif}}(\phi)+\frac{1}{2}\sum_{\phi\in
F^{c}}|\mathbf{P}_{\text{unif}}-\mathbf{P}_{\text{planted}}|(\phi)$

As noticed above, for all $\phi\in F$, $Z(\phi)=\mathbf{E}[Z]$; the likelihood
ratio is equal to 1. The first term of this equation is therefore equal to 0.
This also implies that
$\mathbf{P}_{\text{unif}}(\phi)=\mathbf{P}_{\text{planted}}(\phi)$ for all
$\phi\in F$, and $\mathbf{P}_{\text{unif}}(F)=\mathbf{P}_{\text{planted}}(F)$.
The second term is thus upper bounded by
$\mathbf{P}_{\text{unif}}(F^{c})=\mathbf{P}_{\text{planted}}(F^{c})$. It is
sufficient to prove that $\mathbf{P}_{\text{unif}}(F^{c})\leq 2\nu$, a variant
of the “birthday problem”: We place a group of $k$ balls in $n$ distinct bins
uniformly at random, $m$ times independently. The probability that none of
these $m$ groups intersect is equal to $\mathbf{P}_{\text{unif}}(F)$. When $i$
groups have already been drawn, occupying $ki$ bins, the probability that one
of the next $k$ balls falls in an occupied bin is smaller than $k^{2}i/n$ (the
expected number of such collisions). As $k^{2}(m-1)/n<1/2$ (for fixed $\nu$
and $n$ large enough) the following holds

$\mathbf{P}_{\text{unif}}(F)\geq\prod_{i=1}^{m-1}\Big{(}1-\frac{k^{2}i}{n}\Big{)}>\prod_{i=1}^{m-1}e^{-2k^{2}i/n}=e^{-k^{2}(m-1)(m-2)/n}>1-k^{2}m^{2}/n\,.$

This gives the desired result.

From the last two theorems, we can conclude that the optimal rate of detection
is $m^{*}=\sqrt{n}$. When $m=C\sqrt{n}$, detection is possible with
probability of error smaller than $\delta$, for $C$ greater than some constant
$\bar{C}_{k,\delta}$, by using the likelihood-ratio test. It is impossible to
distinguish the two hypotheses with error probability smaller than $1/2-\nu$
for $C<\underline{C}_{k,\nu}:=2\sqrt{\nu}/k$. No effort has been made to
optimize (or even quantify) the constant $\bar{C}_{k,\delta}$, as a function
of $k$ and $\delta$.

##  3 Polynomial-time testing

For $k\geq 2$, computing the outcome of the likelihood-ratio test involves
solving a $\\#$P-complete problem [Val79], and for $k\geq 3$, even computing
the outcome of the satisfiability test $\Psi_{\text{\sf SAT}}$ (which is
already suboptimal) is equivalent to solving a NP-hard problem. The testing
methods described in the previous section are not computationally efficient:
determining if a formula is satisfiable is the quintessential hard problem,
the first known to be NP-complete [Coo71, Lev73], at the root of the web of
problems known to be in the same class [Kar72]. None of the tests described
above can be computed in a computationally efficient manner. It is therefore
legitimate to examine the performance of tests that can be computed in
polynomial time.

Finding a satisfying assignment in formulas that are known to be satisfiable
has been the focus of substantial efforts [BMZ02, Fla02, KV06, CoKV07]. A
polynomial-time algorithm that does so in the linear regime (for a large
enough $\Delta$) is presented in [CoKV07], for the case $k=3$ (their results
extend to any fixed $k$). A similar problem is studied as well in [FPV13].
This method can be used as a tool for detection: in the unsatisfiable regime
(when $\Delta$ is large enough), the existence of a satisfying assignment is a
sufficient reason to reject the null. The main issue of this approach is that
the regime of detection is not optimal: $m$ needs to be of order $n$ (linear
regime), when only $\sqrt{n}$ (square-root regime) is required for the
likelihood-ratio test.

###  3.1 Variable coupling test

The proof that the likelihood-ratio test has a low probability of error in the
optimal regime is based on the fact that there is a large number of variables
that appear more than once, and on the fact that under the null distribution,
a couple of literals based on the same variable have equal probability to have
the same sign or opposite signs. We can use this fact to design a test that
runs in polynomial time and achieves the optimal rate of detection.

We recall that in each clause, the literals are given in a uniformly random
order. Let $T$ be the number of variables (among the $n$ possible) that appear
more than once as the first literal of a clause of $\phi$ (according to the
random ordering in the data) and $P$ (resp. $D$) the number of those for which
the first two occurrences (according to the natural order of the clauses) of
the same variable have the same sign (resp. different signs), so that $P+D=T$.
The following holds

######  Theorem 3.1.

For all $k\geq 2$, $m,n>0$ and $\delta\in(0,1)$, denote $\Psi_{\text{\sf
COU}}$ the test defined by

$\Psi_{\text{\sf COU}}(\phi)=\mathbf{1}\\{P/T>1/2+1/[2(2^{k}-1)]^{2}\\}\,,$

and

$\tilde{C}_{k,\delta}:=[2(2^{k}-1)]^{2}\sqrt{2\log(2/\delta)}\vee\sqrt{1024/\delta}\,.$

For $m\geq\tilde{C}_{k,\delta}\,\sqrt{n}$, it holds

$\mathbf{P}_{\text{unif}}(\Psi_{\text{\sf
COU}}(\phi)=1)\vee\mathbf{P}_{\text{planted}}(\Psi_{\text{\sf
COU}}(\phi)=0)\leq\delta\,.$

Proof

For each variable that appears at least twice as the first literal of a
clause, consider the probability that the two first occurrences (according to
the natural order of the clauses) of a variable as the first literal of a
clause (according to the random ordering in the data) have the same value. It
is equal to 1/2 under the uniform distribution, and conditionally on the value
of $T$, $P\sim\mathcal{B}(T,1/2)$. Under the planted distribution, each
literal has independently probability $(1+1/(2^{k}-1))/2$ to have the same
value as the corresponding variable in $x_{i}^{*}$, and probability
$(1-1/(2^{k}-1))/2$ to have a different value. Overall, the probability that
these two literals have the same sign under the planted distribution is

$\frac{1}{4}\big{(}1+\frac{1}{2^{k}-1}\big{)}^{2}+\frac{1}{4}\big{(}1-\frac{1}{2^{k}-1}\big{)}^{2}=\frac{1}{2}+\frac{1}{2(2^{k}-1)^{2}}\,.$

Therefore, conditionally on the value of $T$, $P$ has distribution
$\mathcal{B}(T,1/2+1/[2(2^{k}-1)^{2}])$. By Hoeffding’s inequality, the
following holds for all $\varepsilon>0$

$\displaystyle\mathbf{P}_{\text{unif}}\big{(}P/T>1/2+\varepsilon\,|\,T\big{)}\leq\exp(-2\varepsilon^{2}T)$
$\displaystyle\mathbf{P}_{\text{planted}}\big{(}P/T<1/2+1/[2(2^{k}-1)^{2}]-\varepsilon\,|\,T\big{)}\leq\exp(-2\varepsilon^{2}T)\,$

By Lemma A.1, and by definition of $\tilde{C}_{k,\delta}$,
$T\geq\tilde{C}_{k,\delta}^{2}/4$ with probability at least $1-\delta/2$. Let
$\varepsilon=1/[2(2^{k}-1)]^{2}$, and condition on the event
$T\geq\tilde{C}_{k,\delta}^{2}/4$. The previous yields, for
$C_{k,\delta}\geq\sqrt{2\log(2/\delta)}/\varepsilon$

$\displaystyle\mathbf{P}_{\text{unif}}\big{(}P/T>1/2+1/[2(2^{k}-1)]^{2}\,|\,T\big{)}\leq\delta/2$
$\displaystyle\mathbf{P}_{\text{planted}}\big{(}P/T<1/2+1/[2(2^{k}-1)]^{2}\,|\,T\big{)}\leq\delta/2\,.$

Which gives the desired result by a simple union bound.

###  3.2 Hardness hypothesis on random instances

The result of Theorem 3.1 can be contrasted with a hypothesis by Feige,
formulated in [Fei02], to prove hardness of approximation results in the worst
case. We recall the proposed assumption on the hardness of determining the
satisfiability of $3$-SAT formulas on average:

“Even when $\Delta$ is an arbitrarily large constant independent of $n$, there
is no polynomial time algorithm that refutes most 3CNF formulas with $n$
variables and $m=\Delta n$ clauses, and never wrongly refutes a satisfiable
formula.”

Formally, in a statistical language, it is conjectured in this hypothesis that
for all $\Delta>0$, in the linear regime, there is no test $\Psi$ that runs in
polynomial time such that $\mathbf{P}_{\text{unif}}(\Psi=1)\leq 1/2$, and
$\mathbf{P}_{1}(\Psi=0)=0$, for any distribution $\mathbf{P}_{1}$ supported on
SAT. In particular, in our testing problem, this hypothesis states that no
test that runs in polynomial time has a type I error smaller than 1/2 and a
type II error equal to 0. At first sight, this is in apparent contradiction
with theorem 3.1. Interestingly, this result shows that up to the optimal
square-root regime it is possible to design a test with small type I and type
II errors simultaneously, even though it is conjectured and widely believed
that it is impossible to distinguish those distributions with a completely
one-sided error.

There has been a recent interest in the notions of optimal rates for
polynomial-time algorithms. More specifically, there is a growing literature
on limitations, beyond those imposed by information theory, to the statistical
performance of computationally efficient procedures. Such phenomena have been
hinted at [DGR98, Ser00, CJ13, SSST12], and studied in specific computational
models, such as in [FGR+13, FPV13]. More recently, these barriers have been
proven to hold for various supervised tasks such as in [DLS13], based on a
primitive on random 3-SAT instances, and unsupervised problems in statistics
in [BR13] and the subsequent [MW13, Che13, WBS14], based on a hardness
hypothesis for the planted clique problem. The above discussion shows the
difficulty of using Feige’s hypothesis as a primitive to prove computational
lower bounds for statistical problems: it does not imply that it is impossible
to detect planted distributions in a computationally efficient manner in the
linear regime, and is extremely sensitive to the allowed probability of type I
and type II errors.

##  4 Alternative choices for planting distributions

The tests described in Theorems 2.1 and 3.1 exploit a fundamental difference
between the two considered distributions. Planting a satisfying assignment
$x^{*}\in\\{0,1\\}^{n}$ breaks the symmetry of the uniform distribution. The
likelihood ratio $Z/\mathbf{E}[Z]$ is affected by the imbalances in
interactions between variables. Similarly, the variable coupling test is based
on the bias in the signs of chosen literals, under the planted distribution.

This asymmetry is a characteristic of our choice of the planting distribution.
In this section, we observe that the rates of detection are different for
other natural choices of distribution on SAT, the set of satisfiable formulas.
Such an example is $\mathbf{P}_{\text{\sf SAT}}$, the uniform distribution on
SAT. In this new statistical problem, the alternative hypothesis becomes
$\tilde{H}_{1}:\phi\sim\mathbf{P}_{\text{\sf SAT}}$.

It is a fundamentally different statistical problem: its optimal rate of
detection is the linear regime $m^{*}=n$, achieved by the satisfiability test
$\Psi_{\text{\sf SAT}}$. Indeed, as shown in a simple remark in Section 1,
this test is successful in the satisfiable part of the linear regime.
Furthermore, as $\mathbf{P}_{\text{\sf SAT}}$ is the uniform distribution on
SAT, or $\mathbf{P}_{\text{unif}}(\,\cdot\,|\phi\in\text{\sf SAT})$, the total
variation distance $d_{TV}(\mathbf{P}_{\text{unif}},\mathbf{P}_{\text{\sf
SAT}})$ is equal to $\mathbf{P}_{\text{unif}}(\phi\notin\text{\sf SAT})$. As
explained before, this probability vanishes to 0 for $\Delta$ small enough,
which yields the matching lower bound. From a statistical point of view, this
modified hypothesis testing problem is a significantly harder task than the
detection of planted satisfiability.

Among all distributions on satisfiable formulas, the closest in total
variation distance to the uniform distribution (and therefore the choice of
alternative that yields the hardest statistical problem) is the uniform
distribution on SAT. Other distributions used to generate formulas that are
hard to solve, with hidden solutions (usually, with no immediate asymmetry) as
in [AJM04, BHL+01, JMS05, KMZ12] are candidates to create detection problems
with optimal rate of detection in the linear regime. Such an example is the
uniform distribution on formulas that are not-all-equal, or NAE satisfiable.

##  Appendix A Proofs of technical results

Lemma 2.2 and 2.3 are a consequence of the following result on the number of
variables that appear at least twice in the formula. For simplicity of the
proof, we only consider the first literal of each clause, which is sufficient
to our objective.

######  Lemma A.1.

Let $\phi$ be a random formula of $\mathcal{F}^{k}_{m,n}$ with distribution
$\mathbf{P}_{\text{unif}}$. Let $T$ be the number of variables (among the
possible $n$) that appear more than once as the first literal of a clause of
$\phi$.

  * •

Let $\Delta>0$, and $m=\Delta n$. There exists positive constants
$\varepsilon_{\Delta}$ and $r_{\Delta}$ such that

$\mathbf{P}(T<\varepsilon_{\Delta}n)\leq\frac{r_{\Delta}}{n}\,.$

  * •

Let $C>0$, and $m=C\sqrt{n}$. It holds that

$\mathbf{P}(T<C^{2}/4)\leq\frac{576}{C^{2}}\,.$

Proof  We prove this deviation bounds in the two regimes.

Linear regime

We first place ourselves in the linear regime $m=\Delta n$. The first literals
of the clauses of the random formula can be interpreted as being drawn by
independently placing $m$ balls uniformly in $n$ bins, and $T_{i}$ is the
indicator of the event “there are at least two balls in bin $i$”. This is the
complement of having either one or no ball in bin $i$, which yields

$\mathbf{E}[T_{i}]=1-\Big{[}\Big{(}1-\frac{1}{n}\Big{)}^{m}+m\Big{(}1-\frac{1}{n}\Big{)}^{m-1}\frac{1}{n}\Big{]}=1-\Big{[}\Big{(}1-\frac{\Delta}{m}\Big{)}^{m}+\Delta\Big{(}1-\frac{\Delta}{m}\Big{)}^{m-1}\Big{]}\,,$

which has limit $1-(1+\Delta)e^{-\Delta}=2\varepsilon_{\Delta}>0$. Therefore,
for $m$ large enough, $\mathbf{E}[T_{i}]>\varepsilon_{\Delta}$. By, definition
$T$ and $T_{i}$, we have

$T=T_{1}+\ldots+T_{n}\,.$

Therefore, it holds
$\mathbf{E}[T]=\mathbf{E}[T_{1}+\ldots+T_{n}]>n\varepsilon_{\Delta}$. These
variables are not independent and the variance is less simple

${\bf Var}[T]=n{\bf
Var}[T_{1}]+n(n-1)\big{[}\mathbf{E}[T_{1}T_{2}]-\mathbf{E}[T_{1}]\mathbf{E}[T_{2}]\big{]}\,.$

We control the last term

$\displaystyle\mathbf{E}[T_{1}T_{2}]$ $\displaystyle=$
$\displaystyle\mathbf{P}[T_{1}=1,T_{2}=1]=\mathbf{P}[T_{1}=1|T_{2}=1]\mathbf{P}[T_{2}=1]$
$\displaystyle=$ $\displaystyle\mathbf{P}[T_{1}=1|T_{2}=1]\mathbf{E}[T_{2}]$
$\displaystyle=$
$\displaystyle\Big{[}1-\Big{[}\Big{(}1-\frac{1}{n}\Big{)}^{m-2}+(m-2)\Big{(}1-\frac{1}{n}\Big{)}^{m-3}\frac{1}{n}\Big{]}\Big{]}\mathbf{E}[T_{2}]$

Therefore, we obtain the bound

$\mathbf{E}[T_{1}T_{2}]-\mathbf{E}[T_{1}]\mathbf{E}[T_{2}]\leq\Big{[}1-\Big{(}1-\frac{1}{n}\Big{)}^{2}+\Delta\Big{(}1-\Big{(}1-\frac{1}{n}\Big{)}^{2}\Big{)}\Big{]}\mathbf{E}[T_{2}]\leq\frac{3+3\Delta}{n}\,.$

Overall, this yields ${\bf Var}[T]\leq(4+3\Delta)n$. We now apply Chebyshev’s
inequality, with
$r_{\Delta}=(3+3\Delta)/(\mathbf{E}[T_{1}]-\varepsilon_{\Delta})^{2}$

$\mathbf{P}[T<\varepsilon_{\Delta}n]\leq\frac{{\bf
Var}[T]}{(\mathbf{E}[T_{1}]-\varepsilon_{\Delta})^{2}n^{2}}\leq\frac{r_{\Delta}}{n}\,.$

Square-root regime

This proof is a simple modification of the proof of the linear regime with the
same notations, for $m=C\sqrt{n}$. We derive the expectation and variance of
$T$

$\displaystyle\mathbf{E}[T_{i}]$ $\displaystyle=$ $\displaystyle
1-\Big{[}\Big{(}1-\frac{1}{n}\Big{)}^{m}+m\Big{(}1-\frac{1}{n}\Big{)}^{m-1}\frac{1}{n}\Big{]}$
$\displaystyle=$ $\displaystyle
1-\Big{[}\Big{(}1-\frac{1}{n}\Big{)}^{C\sqrt{n}}+\frac{C}{\sqrt{n}}\Big{(}1-\frac{1}{n}\Big{)}^{C\sqrt{n}-1}\Big{]}$
$\displaystyle=$ $\displaystyle
1-\Big{[}1-\frac{C}{\sqrt{n}}+\frac{C^{2}}{2n}+o\Big{(}\frac{1}{n}\Big{)}+\frac{C}{\sqrt{n}}-\frac{C^{2}}{n}+o\Big{(}\frac{1}{n}\Big{)}\Big{]}=\frac{C^{2}}{2n}+o\Big{(}\frac{1}{n}\Big{)}\,.$

Therefore, for $n$ large enough $\mathbf{E}[T_{i}]\in(C^{2}/3n,C^{2}/n)$ and
$\mathbf{E}[T_{i}]\in(C^{2}/3,C^{2}$). For the variance, as in the linear
regime it holds

${\bf Var}[T]=n{\bf
Var}[T_{1}]+n(n-1)\big{[}\mathbf{E}[T_{1}T_{2}]-\mathbf{E}[T_{1}]\mathbf{E}[T_{2}]\big{]}\,.$

We obtain in a similar way the following bound, for $n$ large enough

$\mathbf{E}[T_{1}T_{2}]-\mathbf{E}[T_{1}]\mathbf{E}[T_{2}]\leq\Big{[}1-\Big{(}1-\frac{1}{n}\Big{)}^{2}+\frac{C}{\sqrt{n}}\Big{(}1-\Big{(}1-\frac{1}{n}\Big{)}^{2}\Big{)}\Big{]}\mathbf{E}[T_{2}]\leq\frac{3}{n}\times
C^{2}/n\,.$

Therefore, ${\bf Var}[T]\leq 4C^{2}$, and we have, using Chebyshev’s
inequality

$\mathbf{P}[T\geq C^{2}/4]\leq\frac{{\bf
Var}[T]}{(C^{2}/3-C^{2}/4)^{2}}\leq\frac{576}{C^{2}}\,.$

Proof [Proof of Lemma 2.2 and 2.3]

For all $x\in\\{0,1\\}^{n}$, $x\in\mathcal{S}(\phi)$ if and only if $x$
satisfies all the clauses of $\phi$. We can therefore write

$\displaystyle
Z=\sum_{x\in\\{0,1\\}^{n}}\prod_{i=1}^{m}\mathbf{1}\\{x\in\mathcal{S}(C_{i})\\}\,.$

We recall that this yields, for $\phi$ drawn uniformly
$\mathbf{E}[Z]=2^{n}(1-2^{-k})^{m}$.

In the proof of Theorem 2.4, we use that $Z$ is equal to its expectation when
the $km$ variables in the formula are distinct. In the linear regime, or in
the square-root regime for a large enough constant, it is not the case, with
high probability. The interactions between the clauses that share the same
variable will create an imbalance between couples of clauses where the same
variables appears with the same sign, and those where it appears with a
different one.

We compute the conditional expectation of $Z$, given the first variable of
each clause, and whether the first two occurrences of every variable (when
there are two or more) are the same literal or not. Formally, we denote
$G=(G_{1},\ldots,G_{n})$ the partition of $\\{1,\ldots,m\\}$ in $n$ sets
(allowing some of them to be empty), where

$G_{i}=\big{\\{}j\in\\{1,\ldots,m\\}:C_{j}(x)\in\\{x_{i}\wedge\ldots,\bar{x}_{i}\wedge\ldots\\}\big{\\}}\,,$

and $\sigma=(\sigma_{1},\ldots,\sigma_{n})$, where $\sigma_{i}=0$ if there are
less than two elements in $G_{i}$, $\sigma_{i}=1$ if the first two elements of
$G_{i}$ have the same first literal (either both $x_{i}$ or both
$\bar{x}_{i}$), and $\sigma_{i}=-1$ otherwise. By linearity of expectation, it
holds

$\mathbf{E}[Z\,|\,(G,\sigma)]=\sum_{x\in\\{0,1\\}^{n}}\mathbf{E}\Big{[}\mathbf{1}\\{x\in\mathcal{S}(\phi)\\}\,|\,(G,\sigma)\Big{]}\,.$

We now observe that this conditional expectation is constant, for all
$x\in\\{0,1\\}^{n}$. Indeed, let $e_{0}$ be the assignment of all zeroes, and
$t_{x}$ be the literal-flipping transformation such that $t_{x}(e_{0})=x$, and
$T_{x}$ the corresponding literal-flipping transformation on formulas. For all
$x$, it holds

$\phi(x)=\phi(t_{x}(e_{0}))=(T_{x}\phi)(e_{0})\,.$

For all $x$, $T_{x}\phi$ also has distribution $\mathbf{P}_{\text{unif}}$, and
$(G,\sigma)$ is invariant by this transformation. Therefore, it holds

$\displaystyle\mathbf{E}[Z\,|\,(G,\sigma)]$ $\displaystyle=$
$\displaystyle\sum_{x\in\\{0,1\\}^{n}}\mathbf{E}\Big{[}\mathbf{1}\\{x\in\mathcal{S}(\phi)\\}\,|\,(G,\sigma)\Big{]}$
$\displaystyle=$
$\displaystyle\sum_{x\in\\{0,1\\}^{n}}\mathbf{E}\Big{[}\mathbf{1}\\{e_{0}\in\mathcal{S}(T_{x}\phi)\\}\,|\,(G,\sigma)\Big{]}$
$\displaystyle=$ $\displaystyle
2^{n}\mathbf{E}\Big{[}\mathbf{1}\\{e_{0}\in\mathcal{S}(\phi)\\}\,|\,(G,\sigma)\Big{]}\,.$

The assignment $e_{0}$ will satisfy the formula $\phi$ if and only if it
satisfies all the sub-formulas $\phi_{G_{1}},\ldots,\phi_{G_{n}}$ (the empty
formula is always satisfied). Given $(G,\sigma)$, the events
$\\{e_{0}\in\mathcal{S}(\phi_{G_{i}})\\}$ are independent: the sub-formulas
are satisfied by $e_{0}$ if and only if every clause contains at least one
negated literal, which occurs independently, conditioned on $(G,\sigma)$. We
can therefore compute the conditional expectation

$\displaystyle\mathbf{E}\Big{[}\mathbf{1}\\{e_{0}\in\mathcal{S}(\phi)\\}\,|\,(G,\sigma)\Big{]}$
$\displaystyle=$
$\displaystyle\mathbf{E}\Big{[}\prod_{i=1}^{n}\mathbf{1}\\{e_{0}\in\mathcal{S}(\phi_{G_{i}})\\}\,|\,(G,\sigma)\Big{]}$
$\displaystyle=$
$\displaystyle\prod_{i=1}^{n}\mathbf{E}\Big{[}\mathbf{1}\\{e_{0}\in\mathcal{S}(\phi_{G_{i}})\\}\,|\,(G,\sigma)\Big{]}$
$\displaystyle=$
$\displaystyle\prod_{i=1}^{n}\mathbf{E}\Big{[}\mathbf{1}\\{e_{0}\in\mathcal{S}(\phi_{G_{i}})\\}\,|\,(G_{i},\sigma_{i})\Big{]}$

The product terms can be expressed as a function of $g_{i}=|G_{i}|$. If
$\sigma_{i}=0$, in the case of $g_{i}<2$, treating separately the cases
$g_{i}=0$ or $1$, we have

$\mathbf{E}\Big{[}\mathbf{1}\\{e_{0}\in\mathcal{S}(\phi_{G_{i}})\\}\,|\,(G_{i},\sigma_{i}=0)\Big{]}=\Big{(}1-\frac{1}{2^{k}}\Big{)}^{g_{i}}\,.$

If there are at least two elements in $G_{i}$, we have

$\displaystyle\mathbf{E}\Big{[}\mathbf{1}\\{e_{0}\in\mathcal{S}(\phi_{G_{i}})\\}\,|\,(G_{i},\sigma_{i}=1)\Big{]}=\frac{1}{2}\Big{[}1+\Big{(}1-\frac{1}{2^{k-1}}\Big{)}^{2}\Big{]}\Big{(}1-\frac{1}{2^{k}}\Big{)}^{g_{i}-2}$
$\displaystyle\mathbf{E}\Big{[}\mathbf{1}\\{e_{0}\in\mathcal{S}(\phi_{G_{i}})\\}\,|\,(G_{i},\sigma_{i}=-1)\Big{]}=\Big{(}1-\frac{1}{2^{k-1}}\Big{)}\Big{(}1-\frac{1}{2^{k}}\Big{)}^{g_{i}-2}\,.$

Overall, this yields

$\mathbf{E}\Big{[}\mathbf{1}\\{e_{0}\in\mathcal{S}(\phi_{G_{i}})\\}\,|\,(G_{i},\sigma_{i})\Big{]}=\Big{[}1+\frac{\sigma_{i}}{2^{2k}(1-2^{-k})^{2}}\Big{]}\Big{(}1-\frac{1}{2^{k}}\Big{)}^{g_{i}}\,.$

Recall that we denote $P$ (resp. $D$) the number of groups for which
$\sigma_{i}=1$ (resp. $-1$). It holds that

$\mathbf{E}[Z\,|\,(G,\sigma)]=2^{n}\Big{(}1-\frac{1}{2^{k}}\Big{)}^{m}\Big{[}1+\frac{1}{2^{2k}(1-2^{-k})^{2}}\Big{]}^{P}\Big{[}1-\frac{1}{2^{2k}(1-2^{-k})^{2}}\Big{]}^{D}\,.$

It is possible to design a set of $(G,\sigma)$, event of probability close to
1, for which this expectation has the desired value. To do so, we study the
behavior of $P$ and $D$, the number of variables that appear at least twice
among the first variables of the clauses, for which respectively
$\sigma_{i}=1$ or $-1$.

Indeed, for a large $T=P+D$, with $P$ and $D$ close to $(P+D)/2$, this
expectation is significantly smaller than $\mathbf{E}[Z]$. Indeed, for all
$t\in(0,1)$, the function
$f_{t}:\alpha\mapsto(1+t)^{1+\alpha}(1-t)^{1-\alpha}$ is continuous and
$f_{t}(0)=1-t^{2}$, so there exists $\alpha_{t}\in(0,1)$ such that
$f_{t}(\alpha)<1-t^{2}/2$ for all $|\alpha|<\alpha_{t}$. Therefore, there
exists $\alpha_{k}\in(0,1)$ such that

$\Big{[}1+\frac{1}{2^{2k}(1-2^{-k})^{2}}\Big{]}^{1+\alpha}\Big{[}1-\frac{1}{2^{2k}(1-2^{-k})^{2}}\Big{]}^{1-\alpha}<1-\frac{1}{2^{4k+1}(1-2^{-k})^{4}}:=e^{-\gamma_{k}}\,,$

for all $|\alpha|<\alpha_{k}$, for some $\gamma_{k}>0$.

For every variable, we denote $T_{i}=|\sigma_{i}|\in\\{0,1\\}$, and
$T=T_{1}+\ldots+T_{n}$. We now prove independently the two lemmas.

Linear regime, Lemma 2.3

We control $P$ and $D$ in the regime $m=\Delta n$. By lemma A.1, it holds that

$\mathbf{P}[T<\varepsilon_{\Delta}n]\leq\frac{r_{\Delta}}{n}\,.$

Of these $T$ variables, between $T/2(1+\alpha_{k})$ and $T/2(1-\alpha_{k})$
will have their first two occurrences with the same literal, with probability
greater than $1-e^{-\alpha_{k}^{2}\varepsilon_{\Delta}n/2}$, by Hoeffding’s
inequality. We call $B$ the event $T\geq n\varepsilon_{\Delta}$ and
$P\in(T/2(1-\alpha_{k}),T/2(1+\alpha_{k}))$. By the above,
$\mathbf{P}(B)=1-o(1)$. For $(G,\sigma)$ in the event $B$, it holds

$\displaystyle\mathbf{E}[Z\,|\,(G,\sigma)]$ $\displaystyle=$ $\displaystyle
2^{n}\Big{(}1-\frac{1}{2^{k}}\Big{)}^{m}\Big{[}1+\frac{1}{2^{2k}(1-2^{-k})^{2}}\Big{]}^{P}\Big{[}1-\frac{1}{2^{2k}(1-2^{-k})^{2}}\Big{]}^{D}$
$\displaystyle<$ $\displaystyle
2^{n}\Big{(}1-\frac{1}{2^{k}}\Big{)}^{m}(e^{-\gamma_{k}})^{T/2}<e^{-\gamma_{k}\varepsilon_{\Delta}n/2}\mathbf{E}[Z]:=e^{-2c_{k,\Delta}n}\,\mathbf{E}[Z]\,.$

Therefore $\mathbf{E}[Z\,|\,B]<e^{-2c_{k,\Delta}n}\,\mathbf{E}[Z]$. We can now
conclude by conditioning on $B$ and using Markov’s inequality

$\displaystyle\mathbf{P}(Z>e^{-c_{k,\Delta}n}\,\mathbf{E}[Z])$
$\displaystyle=$
$\displaystyle\mathbf{P}(Z>e^{-c_{k,\Delta}n}\,\mathbf{E}[Z]\,|\,B)\mathbf{P}(B)+$
$\displaystyle\mathbf{P}(Z>e^{-c_{k,\Delta}n}\,\mathbf{E}[Z]\,|\,B^{c})\mathbf{P}(B^{c})$
$\displaystyle\leq$
$\displaystyle\mathbf{P}(Z>e^{-c_{k,\Delta}n}\,\mathbf{E}[Z]\,|\,B)+\mathbf{P}(B^{c})$
$\displaystyle\leq$
$\displaystyle\frac{\mathbf{E}[Z\,|\,B]}{e^{-c_{k,\Delta}n}\,\mathbf{E}[Z]}+\mathbf{P}(B^{c})$
$\displaystyle\leq$ $\displaystyle e^{-c_{k,\Delta}n}+\mathbf{P}(B^{c})\,.$

Which yields the desired result.

Square-root regime, Lemma 2.2

As in the linear regime, we control $P$ and $D$ when $m=C\sqrt{n}$. Lemma A.1
yields

$\mathbf{P}[T\geq C^{2}/4]\leq\frac{576}{C^{2}}\,.$

Again, of these $T$ variables, between $T/2(1+\alpha_{k})$ and
$T/2(1-\alpha_{k})$ will have their first two occurrences with the same
literal, with probability greater than $1-e^{-\alpha_{k}^{2}C^{2}/8}$, by
Hoeffding’s inequality. We call $B$ the event $T\geq C^{2}/4$ and
$P\in(T/2(1-\alpha_{k}),T/2(1+\alpha_{k}))$. By the above,
$\mathbf{P}(B)=1-O(1/C^{2})$. For $(G,\sigma)$ in the event $B$, it holds

$\displaystyle\mathbf{E}[Z\,|\,(G,\sigma)]$ $\displaystyle=$ $\displaystyle
2^{n}\Big{(}1-\frac{1}{2^{k}}\Big{)}^{m}\Big{[}1+\frac{1}{2^{2k}(1-2^{-k})^{2}}\Big{]}^{P}\Big{[}1-\frac{1}{2^{2k}(1-2^{-k})^{2}}\Big{]}^{D}$
$\displaystyle<$ $\displaystyle
2^{n}\Big{(}1-\frac{1}{2^{k}}\Big{)}^{m}(e^{-\gamma_{k}})^{T/2}<e^{-\gamma_{k}C^{2}/8}\mathbf{E}[Z]\,.$

Therefore $\mathbf{E}[Z\,|\,B]<e^{-\gamma_{k}C^{2}/8}\,\mathbf{E}[Z]$. We can
now conclude by conditioning on $B$ and using Markov’s inequality

$\displaystyle\mathbf{P}(Z>e^{-\gamma_{k}C^{2}/16}\,\mathbf{E}[Z])$
$\displaystyle=$
$\displaystyle\mathbf{P}(Z>e^{-\gamma_{k}C^{2}/16}\,\mathbf{E}[Z]\,|\,B)\mathbf{P}(B)+$
$\displaystyle\mathbf{P}(Z>e^{-c_{k,\Delta}n}\,\mathbf{E}[Z]\,|\,B^{c})\mathbf{P}(B^{c})$
$\displaystyle\leq$
$\displaystyle\mathbf{P}(Z>e^{-\gamma_{k}C^{2}/16}\,\mathbf{E}[Z]\,|\,B)+\mathbf{P}(B^{c})$
$\displaystyle\leq$
$\displaystyle\frac{\mathbf{E}[Z\,|\,B]}{e^{-\gamma_{k}C^{2}/16}\,\mathbf{E}[Z]}+\mathbf{P}(B^{c})$
$\displaystyle\leq$ $\displaystyle
e^{-\gamma_{k}C^{2}/8}+\mathbf{P}(B^{c})\,.$

This yields the second result, for $C$ large enough, and some absolute
constant $C_{0}$.

## References

  * [ABBDL10] Louigi Addario-Berry, Nicolas Broutin, Luc Devroye, and Gábor Lugosi, _On combinatorial testing problems_ , Ann. Statist. 38 (2010), no. 5, 3063–3092. MR 2722464 (2011k:62035)
  * [ACBL12] Ery Arias-Castro, Sébastien Bubeck, and Gábor Lugosi, _Detection of correlations_ , Ann. Statist. 40 (2012), no. 1, 412–435. MR 3014312
  * [ACCD11] Ery Arias-Castro, Emmanuel J. Candès, and Arnaud Durand, _Detection of an anomalous cluster in a network_ , Ann. Statist. 39 (2011), no. 1, 278–304.
  * [ACO08] Dimitris Achlioptas and Amin Coja-Oghlan, _Algorithmic barriers from phase transitions_ , Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (2008), 793–802.
  * [ACV13] Ery Arias-Castro and Nicolas Verzelen, _Community detection in random networks_ , Arxiv Preprint (2013).
  * [AGKS00] Dimitris Achlioptas, Carla Gomes, Henry Kautz, and Bart Selman, _Generating satisfiable problem instances_ , AAAI/IAAI (2000), 256–261.
  * [AJM04] Dimitris Achlioptas, Haixia Jia, and Cristopher Moore, _Hiding satisfying assignments: two are better than one_ , IN PROCEEDINGS OF AAAI’04 24 (2004), 131–136.
  * [AM06] Dimitris Achlioptas and Cristopher Moore, _Random $k$-sat: Two moments suffice to cross a sharp threshold_, SIAM Journal on Computing 36 (2006), no. 3, 740–762.
  * [AM10] Emmanuel Abbe and Andrea Montanari, _On the concentration of the number of solutions of random satisfiability formulas_ , Random Structures $\&$ Algorithms (2010).
  * [AM13] , _Conditional random fields, planted constraint satisfaction, and entropy concentration_ , Arxiv Preprint (2013).
  * [AMZ06] Fabrizio Altarelli, Rémi Monasson, and Francesco Zamponi, _Can rare sat formulas be easily recognized? on the efficiency of message passing algorithms for k-sat at large clause-to-variable ratios_ , CoRR abs/cs/0609101 (2006).
  * [ANP03] Dimitris Achlioptas, Assaf Naor, and Yuval Peres, _On the fraction of satisfiable clauses in typical formulas_ , EXTENDED ABSTRACT IN FOCS’03 (2003), 362–370.
  * [AP04] Dimitris Achlioptas and Yuval Peres, _The threshold for random $k$-sat is $2^{k}\ln 2-o(k)$_, J. Amer. Math. Soc. 17 (2004), 947–973.
  * [ART06] Dimitris Achlioptas and Federico Ricci-Tersenghi, _On the solution-space geometry of random constraint satisfaction problems_ , STOC ’06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (2006), 130–139.
  * [BHL+01] Wolfgang Barthel, Alexander K. Hartmann, Michele Leone, Federico Ricci-Tersenghi, Martin Weigt, and Riccardo Zecchina, _Hiding solutions in random satisfiability problems: A statistical mechanics approach_ , CoRR cond-mat/0111153 (2001).
  * [BI13] Cristina Butucea and Yuri I. Ingster, _Detection of a sparse submatrix of a high-dimensional noisy matrix_ , Bernoulli (to appear) (2013).
  * [BMZ02] A. Braunstein, M. Mézard, and R. Zecchina, _Survey propagation: an algorithm for satisfiability_.
  * [BR12] Quentin Berthet and Philippe Rigollet, _Optimal detection of sparse principal components in high dimension_ , Ann. Statist. 41 (2012), no. 4, 1780–1815.
  * [BR13] , _Complexity theoretic lower bounds for sparse principal component detection_ , J. Mach. Learn. Res. (COLT) 30 (2013), 1046–1066.
  * [Che13] Yudong Chen, _Incoherence-optimal matrix completion_.
  * [CJ13] Venkat Chandrasekaran and Michael I. Jordan, _Computational and statistical tradeoffs via convex relaxation_ , Proceedings of the National Academy of Sciences (2013).
  * [CO09] Amin Coja-Oghlan, _Random constraint satisfaction problems_ , Electronic Proceedings in Theoretical Computer Science 9 (2009), 32–37.
  * [CO10] , _On belief propagation guided decimation for random k-sat_.
  * [CO13] , _The asymptotic k-sat threshold_.
  * [CoKV07] Amin Coja-oghlan, Michael Krivelevich, and Dan Vilenchik, _Why almost all k-cnf formulas are easy_ , PROCEEDINGS OF THE 13TH INTERNATIONAL CONFERENCE ON ANALYSIS OF ALGORITHMS (2007).
  * [Coo71] S. A. Cook, _The complexity of theorem proving procedures_ , Proceedings of the Third Annual ACM Symposium (New York), ACM, 1971, pp. 151–158.
  * [COP13] Amin Coja-Oghlan and Konstantinos Panagiotou, _Going after the k-sat threshold_ , STOC ’13 Proceedings of the 45th annual ACM symposium on Symposium on theory of computing (2013), 705–714.
  * [DGR98] Scott E. Decatur, Oded Goldreich, and Dana Ron, _Computational sample complexity_ , SIAM JOURNAL ON COMPUTING 29 (1998).
  * [DJ04] David Donoho and Jiashun Jin, _Higher criticism for detecting sparse heterogeneous mixtures_ , Ann. Statist. 32 (2004), no. 3, 962–994. MR 2065195 (2005e:62066)
  * [DLS13] Amit Daniely, Nati Linial, and Shai Shalev Shwartz, _More data speeds up training time in learning halfspaces over sparse vectors_ , Arxiv Preprint (2013).
  * [DSS14] Jian Ding, Allan Sly, and Nike Sun, _Proof of the satisfiability conjecture for large k_.
  * [Fei02] Uriel Feige, _Relations between average case complexity and approximation complexity_ , Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (New York), ACM, 2002, pp. 534–543 (electronic). MR 2121179
  * [FGR+13] Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao, _Statistical algorithms and a lower bound for planted clique_ , Proceedings of the Fourty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2013, 2013.
  * [Fla02] Abraham Flaxman, _A spectral technique for random satisfiable 3cnf formulas_ , SODA ’03 Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms (2002), 357–363.
  * [FMV06] Uriel Feige, Elchanan Mossel, and Dan Vilenchik, _Complete convergence of message passing algorithms for some satisfiability problems_ , IN RANDOM (2006), 339–350.
  * [FPV13] Vitaly Feldman, Will Perkins, and Santosh Vempala, _On the complexity of random satisfiability problems with planted solutions_ , Arxiv Preprint (2013).
  * [HJKN06] Harri Haanpää, Matti Järvisalo, Petteri Kaski, and Ilkka Niemelä, _Hard satisfiable clause sets for benchmarking equivalence reasoning techniques_ , Journal on Satisfiability, Boolean Modeling and Computation 2 (2006), no. 1, 27–46.
  * [Ing82] Yu. I. Ingster, _The asymptotic efficiency of tests for a simple hypothesis against a composite alternative_ , Teor. Veroyatnost. i Primenen. 27 (1982), no. 3, 587–592. MR 673934 (84m:62040)
  * [Ing98] Yuri I. Ingster, _Minimax detection of a signal for $l^{n}$-balls_, Math. Methods Statist. 7 (1998), no. 4, 401–428 (1999). MR 1680087 (2000f:62012)
  * [ITV10] Yuri I. Ingster, Alexandre B. Tsybakov, and Nicolas Verzelen, _Detection boundary in sparse regression_ , Electron. J. Stat. 4 (2010), 1476–1526.
  * [JMS05] Haixia Jia, Cristopher Moore, and Doug Strain, _Generating hard satisfiable formulas by hiding solutions deceptively_ , IN AAAI (2005), 384–389.
  * [Kar72] Richard M. Karp, _Reducibility among combinatorial problems_ , Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), Plenum, New York, 1972, pp. 85–103. MR 0378476 (51 #14644)
  * [KMRT+06] Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborova, _Gibbs states and the set of solutions of random constraint satisfaction problems_.
  * [KMZ12] Florent Krzakala, Marc Mézard, and Lenka Zdeborová, _Reweighted belief propagation and quiet planting for random k-sat_.
  * [KV06] Michael Krivelevich and Dan Vilenchik, _Solving random satisfiable 3cnf formulas in expected polynomial time_ , IN PROC. 17TH ACM-SIAM SYMP. ON DISCRETE ALGORITHMS (2006), 454–463.
  * [Lev73] Leonid Levin, _Universal search problems_ , Problemy Peredachi Informatsii 9 (1973), no. 3, 115–116.
  * [MPZ02] M. Mézard, G. Parisi, and R. Zecchina, _Analytic and algorithmic solution of random satisfiability problems_.
  * [MRT09] Andrea Montanari, Ricardo Restrepo, and Prasad Tetali, _Reconstruction and clustering in random constraint satisfaction problems_.
  * [MW13] Zongming Ma and Yihong Wu, _Computational barriers in minimax submatrix detection_ , Arxiv Preprint (2013).
  * [MZ02] Marc Mezard and Riccardo Zecchina, _The random k-satisfiability problem: from an analytic solution to an efficient algorithm_.
  * [Ser00] Rocco A. Servedio, _Computational sample complexity and attribute-efficient learning_ , Journal of Computer and System Sciences 60 (2000), no. 1, 161–178.
  * [SSST12] Shai Shalev-Shwartz, Ohad Shamir, and Eran Tomer, _Using more data to speed-up training time_ , Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics April 21-23, 2012 La Palma, Canary Islands., JMLR W&CP, vol. 22, 2012, pp. 1019–1027.
  * [Val79] Leslie G. Valiant, _The complexity of enumeration and reliability problems_ , SIAM J. Comput. 8 (1979), no. 3, 410–421.
  * [WBS14] Tengyao Wang, Quentin Berthet, and Richard J. Samworth, _Statistical and computational trade-offs in estimation of sparse principal components_ , Arxiv Preprint (2014).


Below we include a simple supervised learning example in which we compare the
standard variance reduction algorithm SVRG (Johnson and Zhang,, 2013) to the
$SSO$ algorithm in the supervised learning setting. Like the examples above,
we test the optimization algorithms using the Chang and Lin, (2011) rcv1
dataset, under an MSE loss. This plot shows that SSO can outperform SVRG for
even small batch-size settings. For additional details on the implementation
and hyper-parameters used, see https://github.com/WilderLavington/Target-
Based-Surrogates-For-Stochastic-Optimization. We note that it is likely, that
for small enough batch sizes SVRG may become competitive with SSO, however we
leave such a comparison for future work.

Figure 15: Comparison of the average mean-squared error between SGD, SVRG, and
SSO-SGD. This plot displays that even in settings where the batch-size is
small, SSO can even improve over variance reduction techniques like SVRG.

###  E.6 Imitation Learning

(a) Walker2d-v2 Environment

(b) Hopper-v2 Environment

Figure 16: Comparison of policy return, and log policy loss incurred by SGD,
SLS, Adam, Adagrad, and SSO as a function of the total interactions. Unlike
Section 5, the mean of the policy is parameterized by a neural network model.
In both environments, for both behavioral policies, SSO outperforms all other
online-optimization algorithms. Additionally, as m in increases, so to does
the performance of SSO in terms of both the return as well as the loss.

(a) Walker2d-v2 Environment

(b) Hopper-v2 Environment

Figure 17: Comparison of policy return, and log policy loss incurred by SGD,
SLS, Adam, Adagrad, and SSO as a function of the total interactions. Unlike
Section 5, the mean of the policy is parameterized by a linear model. In both
environments, for both behavioral policies, SSO outperforms all other online-
optimization algorithms. Additionally, as m in increases, so to does the
performance of SSO in terms of both the return as well as the loss.

Figure 18: Comparison of log policy loss incurred by SGD, SLS, Adam, Adagrad,
and SSO as a function of the total interactions for the Walker2d gym
environment. Unlike Section 5, the mean of the policy is parameterized by a
linear model. Unlike Fig. 17 and Fig. 16,this plot displays 500 thousand
iterations instead of only 50. We again see that SSO outperforms all other
online-optimization algorithms, even for a very large number of iterations.
Additionally, as m in increases, we again see the performance of SSO log loss
improves as well.

Comparisons of Adagrad, SLS, Adam, and SSO evaluated on two Mujoco (Todorov et
al.,, 2012) imitation learning benchmarks (Lavington et al.,, 2022),
Hopper-v2, and Walker-v2. In this setting training and evaluation proceed in
rounds. At every round, a behavioral policy samples data from the environment,
and an expert labels that data. The goal is guess at the next stage
(conditioned on the sampled states) what the expert will label the examples
which are gathered. Here, unlike the supervised learning setting, we receive a
stream of new data points which can be correlated and drawn from following
different distributions through time. Theoretically this makes the
optimization problem significantly more difficult, and because we must
interact with a simulator, querying the stochastic gradient can be expensive.
Like the example in Appendix E, in this setting we will interact under both
the experts policy distribution (behavioral cloning), as well as the policy
distribution induced by the agent (online imitation). We parameterize a
standard normal distribution whose mean is learned through a mean squared
error loss between the expert labels and the mean of the agent policy. Again,
the expert is trained following soft-actor-critic. All experiments were run
using an NVIDIA GeForce RTX 2070 graphics card. with a AMD Ryzen 9 3900
12-Core Processor.

In this this setting we evaluate two measures: the per-round log-policy loss,
and the policy return. The log policy loss is as described above, while the
return is a measure of how well the imitation learning policy actually solves
the task. In the Mujoco benchmarks, this reward is defined as a function of
how quickly the agent can move in space, as well as the power exerted to move.
Imitation learning generally functions by taking a policy which has a high
reward (e.g. can move through space with very little effort in terms of
torque), and directly imitating it instead of attempting to learn a cost to go
function as is done in RL (Sutton et al.,, 2000).

Each algorithm is evaluated over three random seeds following the same
initialization scheme. As before, in all settings, algorithms use either their
theoretical step-size when available, or the default as defined by (Paszke et
al.,, 2019). The inner-optimization loop is set according to line-search
parameters and heuristics following Vaswani et al., 2019b . All algorithms and
batch sizes are evaluated for 50 rounds of interaction (accept in the case of
Fig. 18, which is evaluated for 500) and performance is represented as a
function of total interactions with the environment. Below we learn a policy
which is parameterized by a two layer perception with 256 hidden units and
relu activations (as was done in the main paper). For further details, please
see the attached code repository.


# An equichordal characterization of the ellipsoid and the sphere

V. A. Aguilar-Arteaga1, R. I. Ayala-Figueroa2, J. Jerónimo-Castro3,
and E. Morales-Amaya4
1,3Facultad de Ingeniería
Universidad Autónoma de Querétaro, México
2Instituto Tecnológico de Mexicali
Tecnológico Nacional de México, México
4Facultad de Matemáticas-Acapulco,
Universidad Autónoma de Guerrero, México
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Let $K$ and $L$ be two convex bodies in $\mathbb{R}^{n}$, $n\geq 3$, with
$L\subset\text{int}\,K$. In this paper we prove the following result: if every
two parallel chords of $K$, supporting $L$ have the same length, then $K$ and
$L$ are homothetic and concentric ellipsoids. We also prove a similar theorem
when instead of parallel chords we consider concurrent chords. We may also
replace, in both theorems, supporting chords of $L$ by supporting sections of
constant width. In the last section we also prove similar theorems where we
consider projections instead of sections.

##  1 Introduction

Let $K$ be a convex body, i.e., a compact and convex set with non-empty
interior. We say that a point $x$ in the interior of $K$ is an _equichordal
point_ if all the chords of $K$ through $x$ have the same length. The famous
Equichordal Problem, due to W. Blaschke, W. Rothe, and R. Weitzenböck [2], and
Fujiwara [4], asks about the existence of a convex planar body with two
equichordal points. M. Rychlik in [10], finally gave a complete proof about
the non existence of a body with two equichordal points. In [7] was introduced
an extension of the notion of an equichordal point: Let $K$ and $L$ be two
convex bodies in $\mathbb{R}^{n}$, $n\geq 2$, with $L\subset\text{int}\,K$; it
is said that $L$ is an _equichordal body_ for $K$ if every chord of $K$
tangent to $L$ have length equal to a given number $\lambda$. In [1], J.
Barker and D. Larman proved that if $K$ is a convex body that possesses an
equichordal ball then it is also a ball. This result was extended in [7] and
is proved there that only Euclidean balls possess an equichordal convex body.

Another interesting and classical result is due to W. Süss [11]: if all
$2$-dimensional sections of a convex body $K\subset\mathbb{R}^{3}$ through a
point $p\in\text{int}K$ are sets of constant width, then $K$ is a ball. This
result was latter generalized by L. Montejano in [8]. As in the case of the
equichordal point, we can also consider a pair of convex bodies, one in the
interior of the other, such that the sections tangent to the inner body are of
constant width.

In this paper we continue the study of characterizations of the Euclidean ball
and the ellipsoid by mean of equality of the length of chords and by sections
of constant width supporting a convex body in the interior of another convex
body.

##  2 A characterization of the ellipsoid

Let $\mathcal{E}\subset\mathbb{R}^{n}$, $n\geq 2$, be an ellipsoid and let
$\mathcal{E}^{\prime}$ be an ellipsoid in its iterior, homothetic and
concentric with $\mathcal{E}$. It is not difficult to see that every pair of
chords of $\mathcal{E}$, parallel and tangent to $\mathcal{E}^{\prime}$, have
the same length (see Fig. 1). However, is very unexpected that this condition
characterizes the ellipsoid if the dimension of the space is $n\geq 3$. In the
plane, every pair of centrally symmetric and concentric convex bodies share
the same property.

Figure 1: Parallel chords tangent to $\mathcal{E}^{\prime}$ have the same
length

######  Theorem 1.

Let $K,L\subset\mathbb{R}^{n}$, $n\geq 3$, be convex bodies with
$L\subset\emph{int}K$. Suppose for every $u\in\mathbb{S}^{n-1}$ all the chords
of $K$ supporting $L$ and parallel to $u$, have the same length $\lambda(u)$.
Then $K$ and $L$ are homothetic and concentric ellipsoids.

_Proof._ Let $u\in\mathbb{S}^{n-1}$ be any unit vector. Let $[a,b]$ be any
chord of $K$ parallel to $u$ touching $L$ at $x$. Consider a $2$-dimensional
plane $H$ supporting $L$ at $x$ and such that $[a,b]\subset H$. We will show
that $[a,b]$ is a affine diameter of $H\cap K$. Suppose this is not the case
and let $[a^{\prime},b^{\prime}]$ be the affine diameter of $H\cap K$ parallel
to $[a,b]$. We have that $|a^{\prime}b^{\prime}|>|ab|$. Let $\Pi$ be a
$2$-dimensional plane containing $[a^{\prime}b^{\prime}]$ such that $\Pi$
intersect the interior of $L$. Let see $[c,d]$ and $[c^{\prime},d^{\prime}]$
be the two chords of $K$, parallel to $[a^{\prime},b^{\prime}]$, supporting
$\Pi\cap L$. By hypothesis
$|cd|=|c^{\prime}d^{\prime}|<|a^{\prime}b^{\prime}|$, and by the convexity of
$\Pi\cap K$, this is not possible. Hence $|ab|=|a^{\prime}b^{\prime}|$ and
then $[a,b]$ is an affine diameter of $H\cap K$. In the same way we can prove
that any other chord of $H\cap K$ through $x$ is an affine diameter of $H\cap
K$. By a well known result of Hammer [5] we have that $H\cap K$ has center of
symmetry at the point $x$. This is true for every $2$-dimensional plane
supporting $L$ at $x$, it follows that the hypersection supporting $L$ at $x$
has center of symmetry at $x$. Now, by a theorem due to Olovjanishnikov [9] we
have that $K$ and $L$ are homothetic and concentric ellipsoids. $\Box$

We believe the following conjectures are true.

######  Conjecture 1.

Let $K,L\subset\mathbb{R}^{2}$ be convex bodies with $L\subset\emph{int}K$ and
$L$ centrally symmetric. Suppose every pair of parallel chords of $K$
supporting $L$ have the same length. Then $K$ is also centrally symmetric.

######  Conjecture 2.

Let $K,L\subset\mathbb{R}^{3}$ be convex bodies with $L\subset\emph{int}K$ a
strictly convex body. Suppose every section of $K$ supporting $L$ has the
contact point as an equichordal point. Then $K$ and $L$ are concentric balls.

##  3 Characterization of the sphere by concurrent chords

The following lemma is interesting by itself and will be useful for the
subsequent results.

######  Lemma 1.

Let $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ be two concentric and homothetic
ellipses with $\mathcal{E}_{1}\subset\emph{int}\mathcal{E}_{2}$. Let
$[a,a^{\prime}]$ be the chord of $\mathcal{E}_{2}$, tangent to
$\mathcal{E}_{1}$, and orthogonal to the mayor axis of $\mathcal{E}_{2}$.
Then, any other chord $[b,b^{\prime}]$ tangent to $\mathcal{E}_{1}$, not
orthogonal to the mayor axis of $\mathcal{E}_{2}$, has length bigger than the
length of $[a,a^{\prime}]$.

Figure 2: $[a,a^{\prime}]$ is the tangent chord with minimum length

_Proof._ Let $y$ be the point of intersection between the lines $aa^{\prime}$
and $bb^{\prime}$, and let $m$ and $x$ be the points where the chords
$[a,a^{\prime}]$ and $[b,b^{\prime}]$ touch $\mathcal{E}_{1}$, respectively.
We know that $[a,b]\parallel[m,x]\parallel[a^{\prime},b^{\prime}]$ (see Fig.
2), this can be seen easily if we apply an affine transformation which send
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ to concentric circles. To see that
$|aa^{\prime}|<|bb^{\prime}|$ it is enough, by Thale’s theorem, to prove that
$|ym|<|yx|$.

Consider the circle $\Gamma$ with diameter $[p,q]$, the minor axis of
$\mathcal{E}_{1}$. Let $z$ be the projection of $x$ into the minor axis of
$\mathcal{E}_{1}$ and let $x^{\prime}$ be the point where the segment $[z,x]$
intersects the circle $\Gamma$. By a well known property of the ellipse, we
have that $\frac{|zx|}{|zx^{\prime}|}=\lambda>1$, for a fixed number
$\lambda$. The linear transformation that send $\mathcal{E}_{1}$ to $\Gamma$,
also send the tangent segments $[y,m]$ and $[y,x]$ to the segments
$[y^{\prime},m^{\prime}]$ and $[y^{\prime},x^{\prime}]$, tangent to $\Gamma$.
Clearly, we have that $|ym|=|y^{\prime}m^{\prime}|$ and
$|y^{\prime}x^{\prime}|<|yx|$ and since
$|y^{\prime}m^{\prime}|=|y^{\prime}x^{\prime}|$ we have that $|ym|<|yx|$.
$\Box$

Figure 3: The length of $[y,x]$ is bigger than the length of
$[y^{\prime},x^{\prime}]$

######  Theorem 2.

Let $K,L,M\subset\mathbb{R}^{n}$, $n\geq 3$, be convex bodies with
$L\subset\emph{int}K\subset\emph{int}M$. Suppose for every $x\in\partial M$
all the lines supporting $L$ and passing through $x$, intersects in $K$ chords
of the same length $\lambda(x)$. Then $K$ and $L$ are concentric balls.

_Proof._ First we prove the theorem in dimension $n=3$. Let $x\in\partial M$
be any point and $C(x,L)$ be the support cone of $L$ with apex at $x$. Define
as $\gamma(x)=\\{C(x,L)\cap\partial M\\}\setminus\\{x\\}$, which is clearly a
simple and closed curve in the boundary of $M$. Notice that $\gamma(x)$
divides the boundary of $M$ into two open regions, the region $R^{-}$ that
contains $x$ and the region $R^{+}$ that does not contain $x$. Now, consider a
chord $[x,y]$ so that $y\in\gamma(x)$ and any chord $[x^{\prime},y^{\prime}]$
of $M$ parallel to $[x,y]$, supporting $L$, and such that $x^{\prime}\in
R^{-}$ and $y^{\prime}\in R^{+}$. Since the cone $C(x^{\prime},L)$ intersects
$R^{-}$ we have that $\gamma(x)\cap\gamma(x^{\prime})\neq\emptyset$. Choose a
point $z\in\gamma(x)\cap\gamma(x^{\prime})$. Since $zx$ and $zx^{\prime}$ are
support lines of $L$ that pass through $z\in\partial M$, then
$\lambda(z)=|[z,x^{\prime}]\cap K|=|[z,x]\cap
K|=\lambda(x)=\lambda(x^{\prime})$. We have proved that the intersection of
$[x,y]$ with $K$ and the intersection of $[x^{\prime},y^{\prime}]$ with $K$
have the same length. That is, parallel chords of $K$ supporting $L$ have the
same length. From theorem 1 we can say that $K$ and $L$ are homothetic and
concentric ellipsoids. But from Lemma 1 we can see that $K$ and $L$ must be,
indeed, concentric balls.

For dimension $n>3$ we just use the fact that if every $3$-dimensional section
of a convex body is a $3$-dimensional ball, then it is an $n$-dimensional
ball. $\Box$

######  Remark 1.

We may replace the set $M$ in Theorem 2 by a pair of parallel hyperplanes
$H_{1}$ and $H_{2}$ such that $K$ and $L$ are contained in the open region
between those planes. The proof follows the same ideas.

##  4 Characterization of the sphere by sections of constant width

######  Theorem 3.

Let $K,L\subset\mathbb{R}^{3}$ be convex bodies with $L\subset\emph{int}K$.
Suppose for every $u\in\mathbb{S}^{n-1}$ all sections of $K$ supporting $L$
and parallel to $u$, have the same constant width $h(u)$. Then $K$ and $L$ are
concentric balls.

_Proof._ We will prove first that $K$ is strictly convex. Suppose this is not
the case and let $[p,q]$ be a segment in the boundary if $K$. Let $S_{1}$ be a
supporting $2$-dimensional plane of $L$ containing $[p,q]$. Since $S_{1}\cap
K$ is of constant width, it must be strictly convex, then $[p,q]$ must be a
point. Now, let $u\in\mathbb{S}^{2}$ be any unit vector. Let $H$ be any
support plane of $L$ parallel to $u$. By hypothesis, the section $H\cap K$ is
of constant width $h(u)$. Let $[a,b]\subset H$ be a chord of $K$, parallel to
$u$, supporting $L$. We will show that $[a,b]$ is a diameter of $H\cap K$.
Suppose this is not the case, and let $[a^{\prime},b^{\prime}]$ be a diameter
of $H\cap K$ parallel to $[a,b]$. Then we have $|a^{\prime}b^{\prime}|>|ab|$.
Let $\Pi$ be a plane supporting $L$ and parallel to $u$ such that the
$2$-dimensional plane $\Gamma$, containing $[a^{\prime},b^{\prime}]$ and the
diameter $[x,y]$ of $\Pi\cap K$ parallel to $u$. Let $[c,d]$ and
$[c^{\prime},d^{\prime}]$, the chords of $K$ in $\Gamma$, parallel to $u$ and
supporting $L$. Since $[c,d]$ and $[c^{\prime},d^{\prime}]$ belong each one to
supporting sections of $L$ parallel to $u$, we have that
$|a^{\prime}b^{\prime}|=|xy|\geq|cd|,|c^{\prime}d^{\prime}|$. This cannot
happen since $K$ is strictly convex and so every section of $K$ is strictly
convex as well. Hence $[a^{\prime},b^{\prime}]=[a,b]$, i.e., $[a,b]$ is a
diameter of $H\cap K$. With this, we have proved that all the chords of $K$,
parallel to $u$ and supporting $L$, have the same length $h(u)$. This is true
for every $u\in\mathbb{S}^{2}$ then we apply Theorem 1 and get that $K$ and
$L$ are homothetic and concentric ellipsoids. However, only Euclidean balls
have sections of constant width. Therefore, $K$ and $L$ are concentric balls.
$\Box$

In a very similar way we can prove the following.

######  Theorem 4.

Let $K,L,M\subset\mathbb{R}^{3}$ be convex bodies with
$L\subset\emph{int}K\subset\emph{int}M$. Suppose for every $x\in\partial M$
all sections of $K$ supporting $L$ and passing through $x$, are of constant
width $h(x)$. Then $K$ and $L$ are concentric balls.

_Proof._ Following the same ideas as in 2, we show that any two parallel
sections are of the same constant width. Hence using Theorem 3 and Lemma 1 the
result follows directly. $\Box$

##  5 A particular case of Süss theorem

We start this section with a proof for a particular case of Süss theorem,
i.e., we will prove that a convex body with concurrent sections of constant
width 1 is a ball. Before giving the proof we introduce the following
notation: for every $\upsilon\in\mathbb{S}^{2}$ denote by $S(\upsilon)$ the
circle $\mathbb{S}^{2}\cap\upsilon^{\bot},$ by $H(\upsilon)$ and
$H(-\upsilon)$ the two supporting planes of $K$ orthogonal to $\upsilon,$ and
by $\text{Sb}(K,\upsilon)$ the shadow boundary of $K$ in direction $\upsilon$,
i.e.,

$\text{Sb}(K,\upsilon)\equiv\\{x\in\partial K:\text{there is a line parallel
to }\upsilon\text{ and touching }K\text{ at }x.\\}$

It is a well known result of W. Blaschke [3] that a convex body $K$ is an
ellipsoid if for every $\upsilon\in\mathbb{S}^{2}$ the shadow boundary
$Sb(K,\upsilon)$ is a planar curve. Moreover, if we know that
$\text{Sb}(K,\upsilon)$ is orthogonal to $\upsilon$, for every
$\upsilon\in\mathbb{S}^{2}$, then the conclusion is even stronger: $K$ is a
Euclidean ball. However, if we restrict the directions for the shadow
boundaries we have the following interesting conclusion.

######  Lemma 2.

Let $K\subset\mathbb{R}^{3}$ be a convex body and $\upsilon\in\mathbb{S}^{2}$
such that for every $w\in S(\upsilon)$ we have that $\emph{Sb}(K,w)$ is a
closed planar curve orthogonal to $w$. Then $K$ has an axis of revolution
parallel to $\upsilon$.

_Proof._ Let $H(\upsilon)$ and $H(-\upsilon)$ be the planes supporting $K$,
orthogonal to $\upsilon,$ and consider the points $a\equiv H(\upsilon)\cap K$
and $b\equiv H(-\upsilon)\cap K.$ Clearly, $a$ and $b$ belong to
$\text{Sb}(K,w)$ for every $w\in S(\upsilon)$, and since $w\bot\
\text{Sb}(K,w)$ then we get that $[a,b]$ is parallel to $\upsilon.$ Now, let
$\Omega$ be a plane parallel to $H(\upsilon)$ which intersects the interior of
$K$. Consider an arbitrary vector $w\in S(\upsilon),$ let $\Pi$ be the plane
orthogonal to $w$ through $[a,b]$, and let $\\{x,y\\}\equiv\Omega\cap\partial
K\cap\Pi$. We have that $\text{Sb}(K,w)=\Pi\cap\partial K$, then the tangent
vectors to $\Omega\cap\partial K$ through the points $x$ and $y$ are parallel
to $w$. We have that $[x,y]$ is orthogonal to $w$ and intersects the segment
$[a,b]$ in a point $m$. It is known that a planar curve is a circle if all its
normal lines are concurrent, it follows that $\Omega\cap\partial K$ is a
circle with center at $m$. Since the above is true for every plane $\Omega$
orthogonal to $\upsilon$ and intersecting $K$, we conclude that the line $ab$
is an axis of revolution for $K$. $\Box$

Figure 4: The shadow boundaries orthogonal to $\upsilon$ are planar curves

######  Theorem 5.

Let $K\subset\mathbb{R}^{3}$ be a convex body and let $p$ be a point in its
interior. If every $2$-dimensional section of $K$ through $p$ has constant
width 1, then $K$ is a ball with center at $p$ and diameter 1.

_Proof._ Let $[a,b]$ be any affine diameter of $K$. The section containing
$p$, $a$, and $b$, has constant width and has diameter equal to $|ab|=1.$ It
follows that all the affine diameters of $K$ are indeed diameters and hence
$K$ is a body of constant width 1. Let $H$ be any $2$-dimensional plane
containing $p$ with orthogonal unit vector $u$. The orthogonal projection of
$K$ onto $H$, $\pi_{u}(K)$, is a $2$-dimensional body of constant width 1
which contains $H\cap K$, then we have that $\pi_{u}(K)=H\cap K$. It follows
that $\text{Sb}(K,u)=\partial(H\cap K)$. We have proved that all the shadow
boundaries of $K$ are planar curves, by Blaschke’s theorem we have that $K$
must be an ellipsoid. However, since $K$ is a body of constant width it must
be a ball. $\Box$

######  Remark 2.

This theorem can also be proved using Lemma 2: it is not difficult to prove
that there are two diameters of $K$ passing through $p$. By Lemma 2 we have
that each one of these diameters is an axis of revolution of $K$ and is well
known that the only convex body with two axes of revolution is the Euclidean
ball.

##  6 Equichordal projections

We give a result where instead of sections tangent to the inner body we
consider orthogonal projections.

######  Theorem 6.

Let $K,L\subset\mathbb{R}^{3}$ be convex bodies with $L\subset\emph{int}K$ and
$L$ strictly convex. Suppose for every $u\in\mathbb{S}^{2}$ all the chords of
$\pi_{u}(K)$ that are tangent to $\pi_{u}(L)$ have length equal to 1. Then $K$
and $L$ are concentric balls.

_Proof._ Let $u\in\mathbb{S}^{2}$ be any direction and let $[a,b]$ be any
chord of $\pi_{u}(K)$ supporting $\pi_{u}(L)$. Let $\Pi(a,b)$ be the plane
parallel to $u$ and containing $[a,b]$. Clearly, $\Pi(a,b)$ is a supporting
plane of $L$. Let $a^{\prime},b^{\prime}\in\partial K$ be the points such that
$\pi_{u}(a^{\prime})=a$ and $\pi_{u}(b^{\prime})=b.$ We have that the lines
$a^{\prime}a$ and $b^{\prime}b$ are supporting lines of the section
$S(a,b)=\Pi(a,b)\cap K$ (see Fig. 5). If $[a^{\prime},b^{\prime}]$ is not
parallel to $[a,b]$ then we can find a direction $w\in\mathbb{S}^{2}$ where a
chord of $\pi_{w}(K)$ tangent to $\pi_{w}(L)$ has length bigger than $1$. To
see this, consider $w$, orthogonal to $[a^{\prime},b^{\prime}]$ and parallel
to $\Pi(a,b)$. We have that the segment $\Pi(a,b)\cap\pi_{w}(K)$ has length
bigger than or equal to $|a^{\prime}b^{\prime}|>|ab|=1$, which is a
contradiction to the hypothesis of the theorem. Hence we have that
$[a^{\prime},b^{\prime}]$ is parallel to $[a,b]$, i.e., the width of $S(a,b)$
in the direction of $[a,b]$ is equal to $1$. In the same way we prove that the
width of $S(a,b)$ in every direction parallel to $\Pi(a,b)$ is equal to $1$.
In other words, $S(a,b)$ is a set of constant width $1$. We have proved that
all the sections of $K$ supporting $L$ are sets of constant width $1$, we
apply Theorem 3 and conclude that $K$ and $L$ are concentric balls. $\Box$

Figure 5: The section $S(a,b)$ is a set of constant width $1$

######  Remark 3.

Following similar ideas, we can prove the case in Theorem 6 when $L$ is a
point. However, we suspect the following is also true.

######  Conjecture 3.

Let $K,L\subset\mathbb{R}^{3}$ be convex bodies with $L\subset\emph{int}K$ and
$L$ strictly convex. Suppose for every $w\in\mathbb{S}^{2}$ the chords of
$\pi_{u}(K)$ that are tangent to $\pi_{u}(L)$ and are parallel to $w$, with
$u\bot w$, have length equal to $\lambda(w)$. Then $K$ and $L$ are homothetic
and concentric ellipsoids.

Finally, we have the following conjecture for which we provide in the last
theorem an advance in direction to find a proof.

######  Conjecture 4.

Let $K\subset\mathbb{R}^{3}$ be a convex body and let $p$ be a point in its
interior. Suppose for every $u\in\mathbb{S}^{2}$ the point $\pi_{u}(p)$ is an
equichordal point of $\pi_{u}(K)$. Then $K$ is ball.

######  Theorem 7.

Let $K\subset\mathbb{R}^{3}$ be a strictly convex body and let $p$ be an
equichordal point of $K$. Suppose that for all $u\in\mathbb{S}^{2}$,
$\pi_{u}(p)$ is an equichordal point of $\pi_{u}(K)$. Then $K$ is body of
revolution.

_Proof._ Let $[a,b]$ be an affine diameter of $K$ through $p$. We will prove
now that $[a,b]$ is a binormal of $K$, i.e., there exist support planes of $K$
through $a$ and $b$, respectively, which are orthogonal to the chord $[a,b]$.
Let $\Pi_{a}$ and $\Pi_{b}$ be parallel support planes of $K$ through $a$ and
$b$, respectively, and let $v\in\mathbb{S}^{2}$ be the unit vector orthogonal
to them. If $v$ is parallel to $[a,b]$, then $[a,b]$ is indeed a binormal of
$K$ and we are done. Let us assume that $v$ is not parallel to $[a,b]$. Let
$w\in\mathbb{S}^{2}$ be parallel to $[a,b]$ and let $u$ be a unit vector
orthogonal to $v$ and parallel to the subspace generated by $v$ and $w$. Let
$a^{\prime}=\pi_{u}(a)$ and $b^{\prime}=\pi_{u}(b)$ be the orthogonal
projections of $a$ and $b$ onto the plane $u^{\bot}$. Let $[x,y]$ be the chord
of $K$ through $p$ which is parallel to $u^{\bot}$ and consider the segment
$[x^{\prime},y^{\prime}]\subset\pi_{u}(K)$, with $x^{\prime}=\pi_{u}(x)$ and
$y^{\prime}=\pi_{u}(y)$. Since $[x^{\prime},y^{\prime}]$ passes through
$p^{\prime}=\pi_{u}(p),$ which is an equichordal point of $\pi_{u}(K)$, we
have that

$|a^{\prime}b^{\prime}|\geq|x^{\prime}y^{\prime}|=|xy|=|ab|,$

however, this is only possible if $|a^{\prime}b^{\prime}|=|ab|$, which implies
that $[a,b]$ is parallel to $[a^{\prime},b^{\prime}]$. We have proved that
$[a,b]$ is orthogonal to $\Pi_{a}$ and $\Pi_{b}$, i.e., $[a,b]$ is a binormal
of $K$.

Now, let $u\in\mathbb{S}^{2}$ be any vector orthogonal to $[a,b]$ and denote
by $K_{u}$ the $2$-dimensional section of $K$ orthogonal to $u$ and passing
through $p$. We have that all chords of $\pi_{u}(K)$ through $\pi_{u}(p)$ have
length equal to $|\pi_{u}(a)\pi_{u}(b)|=|ab|$, and since
$\pi_{u}(K_{u})\subset\pi_{u}(K)$ we have that $\pi_{u}(K_{u})=\pi_{u}(K)$.
Since $K$ is a strictly convex body, we obtain that the shadow boundary of $K$
in direction $u$, $\text{Sb}(K,u)$, coincides with $\partial K_{u}$, in other
words, $\text{Sb}(K,u)$ is a planar closed curve orthogonal to $u$. Now we
apply Lemma 2 and conclude that the line $ab$ is an axis of revolution for
$K$. $\Box$

## References

  * [1] J. A. Barker, and D. G. Larman, _Determination of convex bodies by certain sets of sectional volumes._ Discrete Math. 241 (2001), $79-96$.
  * [2] W. Blaschke, W. Rothe, and R. Weitzenböck, _Aufgabe 552,_ Arch. Math. Phys. 27 (1917), $82$.
  * [3] W. Blaschke. _Kreis und Kugel,_ Göschen, Leipzig, (1916).
  * [4] M. Fujiwara. _Uber die Mittelkurve zweier geschlossenen konvexen Kurven in Bezug auf einen Punkt_ , Tohoku Math. J. 10 (1916), $99-103$.
  * [5] P. C. Hammer. _Diameters of convex bodies,_ Proc. Amer. Math. Soc. 5 (1954), $304-306.$
  * [6] P. C. Hammer. _Convex bodies associated with a convex body,_ Proc. Amer. Math. Soc. 2 (1951), $781-793$.
  * [7] J. Jerónimo-Castro, F. G. Jimenez-Lopez, and E. Morales-Amaya. _Some results about equichordal convex bodies,_ Discrete Comput. Geom., in print.
  * [8] L. Montejano. _A characterization of the Euclidean ball in terms of concurrent sections of constant width,_ Geometriae Dedicata 37 (1991), $307-316$.
  * [9] S.P. Olovjanishnikov. _On a characterization of the ellipsoid,_ Ucen. Zap. Leningrad. State Univ. Ser. Mat. 83 (1941), $114-128$.
  * [10] M. R. Rychlik. _A complete solution to the equichordal point problem of Fujiwara, Blaschke, Rothe and Weitzenböck,_ Invent. Math. 129 (1997), no. 1, $141-212$.
  * [11] W. Süss. _Eine charakteristische Eigenschaft der Kugel ,_ Jahresber Deutsch Math.-Verein. 34 (1926), $245-247$.