# Stability for hyperplane covers

Shagnik Das Department of Mathematics, National Taiwan University, Taiwan.
E-mail<EMAIL_ADDRESS>Valjakas Djaljapayan Department of Mathematics,
National Taiwan Normal University, Taiwan<EMAIL_ADDRESS>Yen-
Chi Roger Lin Department of Mathematics, National Taiwan Normal University,
Taiwan. E-mail<EMAIL_ADDRESS>Wei-Hsuan Yu Department of Mathematics,
National Central University, Taiwan. E-mail<EMAIL_ADDRESS>
###### Abstract

An almost $k$-cover of the hypercube $Q^{n}=\\{0,1\\}^{n}$ is a collection of
hyperplanes that avoids the origin and covers every other vertex at least $k$
times. When $k$ is large with respect to the dimension $n$, Clifton and Huang
asymptotically determined the minimum possible size of an almost $k$-cover.
Central to their proof was an extension of the LYM inequality, concerning a
weighted count of hyperplanes.

In this paper we completely characterise the hyperplanes of maximum weight,
showing that there are $\binom{2n-1}{n}$ such planes. We further provide
stability, bounding the weight of all hyperplanes that are not of maximum
weight. These results allow us to effectively shrink the search space when
using integer linear programming to construct small covers, and as a result we
are able to determine the exact minimum size of an almost $k$-cover of $Q^{6}$
for most values of $k$. We further use the stability result to improve the
Clifton–Huang lower bound for infinitely many choices of $k$ in every
sufficiently large dimension $n$.

##  1 Introduction

While it is clear that the hypercube $Q^{n}=\\{0,1\\}^{n}$ can be covered by
two hyperplanes, a classic and surprising result shows that if we have to
avoid the origin, then $n$ planes are needed to cover the remaining points.
Lying at the intersection of finite geometry and extremal combinatorics, this
problem and its variations have been studied by several researchers over the
decades. In the finite geometry setting, such a hyperplane cover is closely
related to the notion of blocking sets, and research in this direction was
pioneered in the late 1970s by Jamison [6]. Meanwhile in the extremal context,
this problem was first studied by Alon and Füredi [1], who resolved a problem
of Komjáth [7] from Ramsey Theory. The Alon–Füredi Theorem was a precursor to
the hugely influential Combinatorial Nullstellensatz, and indeed, this problem
has proven a valuable test case in the development of the algebraic method.
For a more thorough survey of the history of this problem, we refer the reader
to [2].

###  1.1 Covering with multiplicities

In recent years, renewed interest in this hyperplane covering problem was
sparked by the work of Clifton and Huang [5]. In this paper, they studied the
multiplicity version of the problem. Given $k\in\mathbb{N}$, we define an
_almost $k$-cover_ of $Q^{n}$ to be a set of hyperplanes that avoids the
origin while covering all other points of $Q^{n}$ at least $k$ times. We are
then interested in the minimum size of an almost $k$-cover, a quantity we
denote by $f(n,k)$. Note that the Alon–Füredi Theorem shows $f(n,1)=n$.

Clifton and Huang showed that the extremal function $f(n,k)$ exhibits
different behaviour, depending on the relative sizes of the two parameters.
When $n$ is large compared to $k$, they used algebraic methods to obtain lower
bounds on $f(n,k)$, showing that $f(n,2)=n+1$, $f(n,3)=n+3$ for all $n\geq 2$,
and $f(n,k)\geq n+k+1$ whenever $k\geq 4$ and $n\geq 3$. In a subsequent
paper, Sauermann and Wigderson [10] solved the algebraic version of this
problem, which in particular improves the lower bound to $f(n,k)\geq n+2k-3$
for any $k\geq 2$ and $n\geq 2k-3$. However, these lower bounds fall short of
Clifton and Huang’s upper bound of $f(n,k)\leq n+\binom{k}{2}$, which they
conjecture to be the truth for all $k\in\mathbb{N}$ and $n$ sufficiently large
with respect to $k$.

In this paper, however, we will be interested in the other regime, where $k$
is large with respect to $n$. In this range, Clifton and Huang [5] determined
asymptotically the size of the smallest almost $k$-covers, showing
$f(n,k)=\left(H_{n}+o(1)\right)k$, where
$H_{n}=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$ is the $n$th Harmonic
number. To prove this result, they solved the linear programming relaxation of
the integer linear program that represents the hyperplane covering problem. In
particular, to prove the lower bound, they first defined a weighting of the
points of $Q^{n}$.

######  Definition 1.1.

Let $x$ be a nonzero point in $Q^{n}$ with exactly $t$ coordinates equal to
$1$. The _weight_ of $x$ is defined as

$w(x)=\frac{1}{t{\binom{n}{t}}}.$

More generally, given any set $S\subseteq\mathbb{R}^{n}$, we define the
_weight_ of $S$ to be the sum of the weights of all points in $S\cap Q^{n}$;
that is,

$w(S)=\sum_{p\in S\cap Q^{n}}w(p).$ (1)

Given this definition, the crucial step was following theorem.

######  Theorem 1.2 ([5], Theorem 1.3).

If $h$ is a hyperplane avoiding the origin, then $w(h)\leq 1$.

To see how this implies the lower bound, observe that the total weight of the
hypercube is $H_{n}$. Since every point is covered at least $k$ times, it
follows that the total weight of the hyperplanes in an almost $k$-cover must
be at least $H_{n}k$. Since, by Theorem 1.2, each hyperplane can have weight
at most $1$, we must have

$f(n,k)\geq\left\lceil H_{n}k\right\rceil.$ (2)

There are a couple of key remarks to be made concerning this theorem. First,
Clifton and Huang observed that the bound is tight; any hyperplane
$h=\\{x:\sum_{i=1}^{n}c_{i}x_{i}=1\\}$ where all the coefficients $c_{i}$ are
all either $0$ or $1$ satisfies $w(h)=1$. In particular, this gives
exponentially many hyperplanes of maximum weight.

Next, Clifton and Huang observed that if the coefficients $c_{i}$ are all
positive, then the points covered by the hyperplane are the characteristic
vectors of the sets in an antichain. The bound then follows immediately from
the famous Lubell–Yamamoto–Meshalkin inequality [3, 8, 9, 11]. Thus, Theorem
1.2 can be viewed as a generalisation of the LYM inequality.

###  1.2 Our results

In this paper, we prove stability for Theorem 1.2, characterising all
hyperplanes of maximum weight, and improving the bound on the weight of all
other hyperplanes.

######  Theorem 1.3.

Let $h=\\{x:\sum_{i=1}^{n}c_{i}x_{i}=1\\}$ be an affine hyperplane in
$\mathbb{R}^{n}$ that does not pass through the origin. If the coefficients
satisfy

  1. (i)

$c_{i}\leq 1$ for all $i$,

  2. (ii)

$\sum_{i=1}^{n}c_{i}\geq 1$, and

  3. (iii)

$c_{i}\in\mathbb{Z}$ for all $i$,

then $w(h)=1$. Otherwise, $w(h)\leq 1-\frac{1}{n}$.

Note that the upper bound for the non-maximum-weight hyperplanes is best
possible. Indeed, the hyperplane $h_{\alpha}=\\{x:\alpha
x_{1}+\sum_{i=2}^{n}x_{i}=1\\}$ has $w(h_{\alpha})=1-\frac{1}{n}$ whenever
$\alpha\notin\\{-(n-2),-(n-3),\ldots,-1,0,1\\}$.

Our characterisation allows us to enumerate the hyperplanes of maximum weight.

######  Corollary 1.4.

The number of weight-$1$ hyperplanes in $\mathbb{R}^{n}$ is $\binom{2n-1}{n}$.

###### Proof.

We enumerate the weight-$1$ hyperplanes by establishing a bijection from the
set $B_{n}\subseteq\\{-1,+1\\}^{2n-1}$ of all sequences
$(b_{1},\dots,b_{2n-1})$ with exactly $n$ positive entries. For a sequence
$(b_{1},\dots,b_{2n-1})$ in $B_{n}$, let $i_{\ell}$ be the indices such that
$b_{i_{\ell}}=+1$ for $\ell=1,2,\dots,n$; we arrange these indices so that
$i_{1}<i_{2}<\cdots<i_{n}$, and we set $i_{0}=0$ for later usage. Now we
define a mapping $\varphi$ from $B_{n}$ to $\mathbb{Z}^{n}$ as follows: for
$b=(b_{1},\dots,b_{2n-1})\in B_{n}$, let $\varphi(b)=(c_{1},\ldots,c_{n})$,
where the coefficients $c_{\ell}$ are given by

$c_{\ell}=\sum_{j=i_{\ell-1}+1}^{i_{\ell}}b_{j},\qquad\ell=1,2,\dots,n.$

For instance, $\varphi(+1,+1,-1,-1,+1,-1,+1,+1,-1)=(1,1,-1,0,1)$.

It is clear that the image of $\varphi$ is exactly those vectors
$(c_{1},\ldots,c_{n})$ that satisfy the conditions (i), (ii), and (iii) in
Theorem 1.3, and the inverse mapping $\varphi^{-1}$ can be easily defined:
simply expand every coefficient $c_{\ell}$ into a sequence of $|c_{\ell}|+1$
terms of $-1$ followed by a $+1$. This shows that $\varphi$ is a bijection,
and the number of weight-1 hyperplanes in $\mathbb{R}^{n}$ is the cardinality
of $B_{n}$. ∎

The characterisation of maximum weight hyperplanes is also useful for
determining precise values of the extremal function $f(n,k)$. As an example of
an application of our result, we will prove the following, extending results
of Clifton and Huang (who determined $f(5,k)$ for all $k\geq 15$).

######  Theorem 1.5.

For $k\geq 65$, we have

$f(6,k)=\left\lceil\frac{49k}{20}\right\rceil$

whenever $k\not\equiv 2,11\pmod{20}$.

#### Organisation

In Section 2, we will review Clifton and Huang’s proof of Theorem 1.2,
introducing terminology that we will need in our own proofs. In Section 3, we
use this framework to prove Theorem 1.3, and prove some further stability. In
Section 4, we combine our stability result with the linear programming
approach to prove Theorem 1.5, and also show that the lower bound (2) is not
tight infinitely often. Finally, in Section 5, we provide some concluding
remarks and outline possible directions for further research.

##  2 The good, bad, and the redundant

In this section we will review the proof of Theorem 1.2, primarily with the
aim of establishing some terminology and notation that we shall use in our own
proofs in the next section.

Let $h$ be the affine hyperplane in $\mathbb{R}^{n}$ defined by the equation
$\sum_{i=1}^{n}c_{i}x_{i}=1$. We wish to show that $w(h)\leq 1$; that is, the
sum of the weights of the points of $Q^{n}$ contained in $h$ is at most $1$.
For this, it is useful to identify a point $x\in Q^{n}$ with the subset
$S\subseteq[n]$ whose characteristic vector it is; that is, $\\{i:x_{i}=1\\}$.
The idea behind the proof is to associate each set $S$ covered by the
hyperplane $h$ with a disjoint set of permutations in $S_{n}$, whose size is
proportional to the weight of $x$. Since the total number of permutations is
bounded by $n!$, this will in turn bound the weight of the hyperplane $h$.

######  Definition 2.1.

Given some set $S\subseteq[n]$ such that $\sum_{i\in S}c_{i}=1$, we say a
permutation $\pi\in S_{n}$ _yields_ $S$ provided that

  1. (i)

$\pi([|S|])=S;$ that is, $S$ is an initial segment of $\pi$, and

  2. (ii)

$\displaystyle\sum_{i=1}^{\ell}c_{\pi(i)}\begin{cases}<1&\text{ if
}\ell<|S|,\\\ =1&\text{ if }\ell=|S|,\\\ \end{cases}$ where
$1\leq\ell\leq|S|$.

From the definition, it is clear that each $\pi\in S_{n}$ can yield at most
one subset $S\subseteq[n]$. We call a permutation $\pi\in S_{n}$ _bad_ if it
does not yield any set $S\subseteq[n]$, and define $\mathcal{B}$ to be the
collection of all bad permutations in $S_{n}$.

Clifton and Huang [5] proved that, for every set $S\subseteq[n]$ such that
$\sum_{i\in S}c_{i}=1$, and for every cyclic permutation $\sigma$ of $S$,
there is at least one starting point in $S$ such that if we unfold $\sigma$ to
a linear permutation $\pi_{\sigma}$ of $S$, and extend it arbitrarily to any
$\pi\in S_{n}$ with $\pi|_{[|S|]}=\pi_{\sigma}$, then $\pi$ yields $S$. In the
case where $\sigma$ admits two or more such starting points, we call $\sigma$
_switchable_ , and from the available options, we choose $\pi_{\sigma}$ such
that the initial entry $\pi_{\sigma}(1)$ is the largest.

Now, consider a permutation $\pi\in S_{n}$. If $\pi$ is not bad, there is some
set $S$ that $\pi$ yields. Let $\sigma$ be the cyclic permutation of $S$
induced by $\pi|_{[|S|]}$. If $\pi|_{[|S|]}=\pi_{\sigma}$, we say that $\pi$
is _good_ , and otherwise we say that $\pi$ is _redundant_. We let
$\mathcal{G}\subseteq S_{n}$ be the set of good permutations, and
$\mathcal{R}\subseteq S_{n}$ the set of redundant permutations. Note that this
gives a partition $S_{n}=\mathcal{G}\cup\mathcal{B}\cup\mathcal{R}$ of the set
of the permutations of $[n]$ into the subsets of good, bad, and redundant
permutations, whence

$n!=|\mathcal{G}|+|\mathcal{B}|+|\mathcal{R}|.$ (3)

Given a set $S$ covered by $h$, note that there are $(|S|-1)!$ cyclic
permutations $\sigma$ of $S$, each of which gives $(n-|S|)!$ good permutations
(which must start with $\pi_{\sigma}$). Hence, abusing notation to write $S\in
h$ to indicate that $S$ is covered by $h$,

$|\mathcal{G}|=\sum_{S\in h}(|S|-1)!(n-|S|)!,$

or

$\frac{|\mathcal{G}|}{n!}=\sum_{S\in h}\frac{(|S|-1)!(n-|S|)!}{n!}=\sum_{S\in
h}\frac{1}{|S|\binom{n}{|S|}}=\sum_{x\in h}w(x)=w(h).$

Dividing (3) by $n!$ and rearranging then yields

$w(h)=\frac{|\mathcal{G}|}{n!}=1-\frac{|\mathcal{B}|}{n!}-\frac{|\mathcal{R}|}{n!}\leq
1.$ (4)

This proves Theorem 1.2. Moreover, it outlines how one can establish stability
— to prove that non-maximum-weight hyperplanes have weight bounded away from
$1$, we need to show that they admit many bad or redundant permutations.

##  3 Weights of hyperplanes

We will now use the framework set up in the previous section to prove our main
result, Theorem 1.3. Following that, we shall prove some further stability,
providing a partial characterisation of all hyperplanes of large weight.

###  3.1 The proof of Theorem 1.3

We first prove that if $h=\\{x:\sum_{i=1}^{n}c_{i}x_{i}=1\\}$, where the
coefficients $c_{i}$ satisfy the three conditions in Theorem 1.3, then
$w(h)=1$. Per the discussion in Section 2, this amounts to showing that every
permutation in $S_{n}$ is good, i.e., $\mathcal{G}=S_{n}$.

For any permutation $\pi\in S_{n}$, let $t$ be the smallest index such that

$\quad\sum_{j=1}^{t}c_{\pi(j)}=1.$

Note that the conditions (i), (ii) and (iii) guarantee that such an index
exists, and moreover that $\sum_{j=1}^{\ell}c_{\pi(j)}<1$ for all
$1\leq\ell\leq t-1$. Hence, $\pi$ yields the subset
$S=\\{\pi(1),\dots,\pi(t)\\}$.

Now consider the cyclic permutation $\sigma=\langle\pi(1),\dots,\pi(t)\rangle$
of $S$. We argue that $\pi(1)$ is the unique starting point for $\sigma$, that
is, $\pi|_{[t]}=\pi_{\sigma}$. There is nothing to prove if $t=1$, so we may
assume $t>1$ and $\pi(s)$ is another starting point of $\sigma$ with $1<s\leq
t$. Then $\sum_{i=s}^{t}c_{\pi(i)}<1$. Since all the coefficients $c_{j}$’s
are integers, this implies that $\sum_{i=s}^{t}c_{\pi(i)}\leq 0$. But this
leads to

$\sum_{i=1}^{s-1}c_{\pi(i)}=\sum_{i=1}^{t}c_{\pi(i)}-\sum_{i=s}^{t}c_{\pi(i)}\geq
1-0=1,$

which contradicts our choice of $t$. Hence we have $\pi|_{[t]}=\pi_{\sigma}$,
and so $\pi$ is good. As $\pi$ was an arbitrary permutation, it follows that
$\mathcal{G}=S_{n}$, as required.

To complete the proof of Theorem 1.3, we need to show that if $w(h)<1$, then
$w(h)\leq 1-\frac{1}{n}$. Note that by what we have just shown, we know at
least one of the following three cases must occur:

  1. (1)

$c_{i}>1$ for some $i\in[n]$,

  2. (2)

$\sum_{i=1}^{n}c_{i}<1$, or

  3. (3)

$c_{i}\notin\mathbb{Z}$ for some $i\in[n]$.

We treat each of these cases in turn.

#### Case (1)

$c_{i}>1$ for some $i\in[n]$.

Observe that any permutation $\pi$ with $\pi(1)=i$ is bad, since if a
permutation yields a set $S\in[n]$, its first $|S|$ partial sums are at most
$1$. Thus, $|\mathcal{B}|\geq(n-1)!$, and so by (4) we have $w(h)\leq
1-\frac{1}{n}$.

#### Case (2)

$\sum_{i=1}^{n}c_{i}<1$.

We will show that each cyclic permutation $\sigma$ of $[n]$ admits a starting
point for which the resulting permutation $\pi\in S_{n}$ is bad. Then
$|\mathcal{B}|\geq(n-1)!$, which once again implies $w(h)\leq 1-\frac{1}{n}$.

Now let $\pi^{\prime}$ be the permutation we obtain from $\sigma$ by starting
at $1$. For $1\leq t\leq n$, define $a_{t}=\sum_{i=1}^{t}c_{\pi^{\prime}(i)}$.
Let $t_{0}\in[n]$ be any index such that $a_{t_{0}}\geq a_{t}$ for all
$t\in[n]$. In particular,

$a_{t_{0}}\geq a_{n}=\sum_{i=1}^{n}c_{\pi^{\prime}(i)}=\sum_{i=1}^{n}c_{i}.$

If $t_{0}=n$, then $a_{t}\leq a_{t_{0}}=a_{n}<1$ for each $t\in[n]$, which
means that $\pi^{\prime}$ is already bad. Otherwise, take $\pi$ to be the
permutation obtained by starting $\sigma$ at $t_{0}+1$ . We shall show that
$\pi$ is bad. If not, then it yields some set $S\subseteq[n]$, and so there is
some $j$ with $\sum_{i=1}^{j}c_{\pi(i)}=1$. If $j\leq n-t_{0}$ then

$\sum_{i=1}^{j}c_{\pi(i)}=\sum_{i=t_{0}+1}^{t_{0}+j}c_{\pi^{\prime}(i)}=a_{t_{0}+j}-a_{t_{0}}\leq
0,$

by the choice of $t_{0}.$ Otherwise, if $n-t_{0}+1\leq j\leq n,$ then

$\sum_{i=1}^{j}c_{\pi(i)}=\sum_{i=t_{0}+1}^{n}c_{\pi^{\prime}(i)}+\sum_{i=1}^{j-n+t_{0}}c_{\pi^{\prime}(i)}=a_{n}-a_{t_{0}}+a_{j-n+t_{0}}\leq
a_{n}<1$

where the last inequality holds by $a_{t_{0}}\geq a_{j-n+t_{0}}$ and the
strict inequality follows by assumption. Hence, there is no such $j,$ and
$\pi$ must be bad, completing this case.

#### Case (3)

$c_{i}\notin\mathbb{Z}$ for some $i\in[n]$.

If $c_{i}$ is the unique non-integral coefficient, then any permutation with
$\pi(1)=i$ is bad, as all its partial sums will be non-integral. Thus, as in
Case (1), we will have $w(h)\leq 1-\frac{1}{n}$. Hence we may assume there are
$r\geq 2$ non-integral coefficients, which we may assume (without loss of
generality) to be $c_{1},c_{2},\dots,c_{r}$. In this case, we shall show that
for every cyclic permutation of $[n]$ there is a starting point for which the
corresponding permutation $\pi\in S_{n}$ is either bad or redundant. Then we
have $|\mathcal{B}|+|\mathcal{R}|\geq(n-1)!$, and so it again follows from
$(\ref{eq:wh})$ that $w(h)\leq 1-\frac{1}{n}.$

Let $\sigma$ be a cyclic permutation of $[n]$, and partition it into the
cyclic intervals $I_{1},I_{2},\dots,I_{r}$ starting $1,2,\dots,r$,
respectively. If one of these intervals has a partial sum at least 1, then
note that it is in fact strictly greater than 1; as $c_{i}$ is the only non-
integral coefficient in $I_{i}$, all partial sums are non-integral. Thus, if
we start $\pi$ at $i$, we obtain a bad permutation. Otherwise, for every
interval $I_{i}$, all the partial sums are strictly less than 1. In this case,
consider the permutation $\pi$ starting at $1$. If $\pi$ does not yield a set
$S\subseteq[n],$ then it is bad. So, we may assume $\pi$ yields a set
$S\subseteq[n]$. Note that $S$ must contain some $c_{j}$ for $2\leq j\leq r$,
since there must be another non-integral coefficient to make the sum integral.
Hence, $S$ intersects more than one of the intervals $I_{i}$ in $\sigma$.

Now, for $1\leq t\leq|S|$, define $a_{t}=\sum_{i=t}^{|S|}c_{\pi(i)}$, and let
$t_{0}$ be the smallest index that minimizes $a_{t}$. Note that we have $2\leq
t_{0}\leq|S|$, since $\sum_{i=1}^{|S|}c_{\pi(i)}=\sum_{i\in S}c_{i}=1$, while
if we choose $t$ be the index of the last non-integral coefficient in $S$ then
$a_{t}$ is a partial sum of that interval, and hence $a_{t}<1$. Let
$\pi^{\prime}$ be the permutation obtained by swapping the intervals
$\pi([1,t_{0}-1])$ and $\pi([t_{0},|S|])$. Note that we still have
$\pi^{\prime}([|S|])=S$, and that $\pi$ and $\pi^{\prime}$ induce the same
cyclic permutation of $S$.

######  Claim.

$\pi^{\prime}$ also yields $S$.

###### Proof of Claim..

Since $\pi^{\prime}([|S|])=S$, the only way that $\pi^{\prime}$ could fail to
yield $S$ is if there is some index $j\in[|S|-1]$ such that
$\sum_{i=1}^{j}c_{\pi^{\prime}(i)}\geq 1$. If $j\leq|S|-t_{0}+1$ then
$\pi^{\prime}([j])=\pi([t_{0},t_{0}+j-1]).$ If this partial sum is positive,
let alone greater than or equal to $1$, then

$\displaystyle
a_{t_{0}+j}=\sum_{i=t_{0}+j}^{|S|}c_{\pi(i)}=\sum_{i=t_{0}}^{|S|}c_{\pi(i)}-\sum_{i=t_{0}}^{t_{0}+j-1}c_{\pi(i)}=a_{t_{0}}-\sum_{i=1}^{j}c_{\pi^{\prime}(i)}<a_{t_{0}},$

which contradicts the choice of $t_{0}$ ($a_{t_{0}}$ is the minimum sum).
Thus, $j\geq|S|-t_{0}+2$, in which case
$\pi^{\prime}([j])=\pi([t_{0},|S|])\cup\pi([1,j-|S|+t_{0}-1])$ and

$\sum_{i=1}^{j}c_{\pi^{\prime}(i)}=\sum_{i=1}^{j-|S|+t_{0}-1}c_{\pi(i)}+\sum_{i=t_{0}}^{|S|}c_{\pi(i)}\geq
1.$

Recall that $\pi$ yields $S$, and so we have $\sum_{i=1}^{|S|}c_{\pi(i)}=1$.
We can therefore deduce that $\sum_{i=t_{0}+j-|S|}^{t_{0}-1}c_{\pi(i)}\leq 0$,
and so

$a_{t_{0}+j-|S|}=\sum_{i=t_{0}+j-|S|}^{|S|}c_{\pi(i)}=\sum_{i=t_{0}+j-|S|}^{t_{0}-1}c_{\pi(i)}+\sum_{i=t_{0}}^{|S|}c_{\pi(i)}=\sum_{i=t_{0}+j-|S|}^{t_{0}-1}c_{\pi(i)}+a_{t_{0}}\leq
a_{t_{0}},$

which again contradicts our choice of $t_{0}$ (recall that $j\leq|S|-1$ which
implies $t_{0}+j-|S|<t_{0}$). Hence, there is no such index $j$, and
$\pi^{\prime}$ yields $S$ as well. ∎

Thus, we see that each of these cyclic permutations $\sigma$ of $S$ are
switchable, admitting at least two starting points that result in permutations
yielding $S$. We defined $\pi_{\sigma}$ to be the permutation with the largest
starting entry, and hence the permutation $\pi$ obtained from starting
$\sigma$ at $1$ is redundant. Hence, we have shown that for each permutation
of $[n]$, there is a starting point giving a bad or redundant permutation,
which resolves Case (3).

This completes the proof of Theorem 1.3.

###  3.2 Further stability

Theorem 1.3 characterises the hyperplanes of maximum possible weight. It is
then natural to ask what we can say about hyperplanes of large weight, and
indeed, our methods allow us to at least partially describe their
coefficients.

######  Theorem 3.1.

Let $h=\\{x:\sum_{i=1}^{n}c_{i}x_{i}=1\\}$ be a hyperplane in $\mathbb{R}^{n}$
of weight $w(h)>1-\frac{r}{n}$. Then the following hold:

  * (a)

$|\\{i:c_{i}>1\\}|\leq r-1$, and

  * (b)

$|\\{i:c_{i}\notin\mathbb{Z}\\}|\leq 2r^{2}-1$.

Before we embark on the proof, we first note that the bound in part (a) is
best possible. Indeed, if $c_{1}=\ldots=c_{r-1}=2,c_{r}=\ldots=c_{n}=1$, then
it is easy to see that a permutation $\pi$ is bad if $\pi(1)\in[r-1]$, and
good otherwise. This implies $w(h)=1-\frac{r-1}{n}>1-\frac{r}{n}$, and we have
$r-1$ coefficients larger than $1$.

On the other hand, we do not expect the bound in part (b) to be tight, and
rather expect that there can be at most $O(r)$ non-integral coefficients.
However, note that a bound of $r$ is not true in general. For instance, if
$n=2r-1$, then we can take $c_{i}=\frac{1}{2}$ for all $i$; this has weight
$\frac{1}{2}$ but $n=2r-1$ fractional coefficients. Perhaps, though, if one
imposes some lower bound on $n$, then it could be true that one must have
fewer than $r$ fractional coefficients.

Finally, we note that Theorem 3.1 only has two parts in its characterisation,
as compared to the three parts in Theorem 1.3. One might also expect that, if
the hyperplane has weight close to one, then the sum of the coefficients
should not be too small. However, this is not true — one could have
$c_{1}=c_{2}=\ldots=c_{n-1}=1$, with $c_{n}$ tending to $-\infty$. Then the
sum of the coefficients is very small, but all permutations except those
starting with $n$ are good, meaning $w(h)=1-\frac{1}{n}$. Hence, it appears to
be somewhat complicated to formulate an appropriate condition on the sums of
the coordinates.

###### Proof.

For (a), note that any permutation starting with a coefficient larger than $1$
is bad. Thus, if there are at least $r$ coefficients larger than $1$, we have
$|\mathcal{B}|\geq r(n-1)!$, and then (4) implies $w(h)\leq 1-\frac{r}{n}$.

For (b), we make the following claim.

######  Claim.

If $h$ has $s$ fractional coefficients, then for any circular permutation of
$[n]$ and $b\in\mathbb{N}$, there are either $b$ starting points that give bad
permutations, or $\frac{s}{b}$ that give bad or switchable permutations.

Let us first see how the claim gives the result. Suppose for contradiction
that $h$ has $s=2r^{2}$ fractional coefficients, and set $b=r$. Then we know
that the $(n-1)!$ circular permutations of $[n]$ are of two types — the first
give rise to at least $r$ bad permutations, and the second give rise to $2r$
permutations that are either bad or switchable. Suppose there are
$\alpha(n-1)!$ circular permutations of the first kind, and thus
$(1-\alpha)(n-1)!$ circular permutations of the second kind. If we let
$\mathcal{S}$ denote the set of switchable permutations, we have
$|\mathcal{B}|+|\mathcal{S}|\geq r\alpha(n-1)!+2r(1-\alpha)(n-1)!$, with
$|\mathcal{B}|\geq r\alpha(n-1)!$.

Now notice that at least half of all switchable permutations are redundant,
and so it follows from the above inequalities that
$|\mathcal{B}|+|\mathcal{R}|\geq r(n-1)!$, and so the weight of the hyperplane
is at most $1-\frac{r}{n}$. ∎

To finish, we prove the claim.

###### Proof of Claim.

Fix a circular permutation $\sigma$ of $[n]$, and let
$I_{1},I_{2},\ldots,I_{s}$ be the (cyclic) intervals that start with
fractional coefficients, labelled in cyclic order. For $1\leq i\leq s$, let
$\pi_{i}$ be the linear permutation of $[n]$ obtained from $\sigma$ by
starting at the $i$th fractional coefficient (so $I_{i}$ is an initial segment
of $\pi_{i}$).

Now since each $I_{i}$ starts with a fractional coefficient, and has no other,
all of its initial sums are fractional. Thus, if $I_{i}$ has any initial sum
that is at least $1$, it is strictly larger than $1$, and so $\pi_{i}$ will be
a bad permutation. Thus, if there are at least $b$ such intervals, then we
obtain $b$ bad permutations, and we are done.

Suppose instead that $I_{i}$ has an initial sum in the interval $(0,1)$. If
the permutation $\pi_{i}$ is good, then it yields a set $S$. Thus, if we
consider the tail interval of $S$ with the smallest sum, this will be a proper
subinterval of $S$ (since all of $S$ has sum $1$, but we can drop the initial
sum in $I_{i}$ with positive sum to obtain a tail interval with smaller sum).
Then, as in the proof of Theorem 1.3, we can rotate $S$ to obtain another
permutation that yields $S$ with the same cyclic permutation of $S$. Hence,
$\pi_{i}$ is switchable in this case.

In the remaining case, then, all initial sums of $I_{i}$, including $I_{i}$
itself, must be strictly negative. Suppose we have $b$ such intervals
appearing consecutively in $\sigma$, and assume without loss of generality
that these are $I_{1},I_{2},\ldots,I_{b}$. If all of these intervals are good,
let $S_{i}$ be the set yielded by $\pi_{i}$.

First observe that $S_{i}$ and $S_{i+1}$ cannot end in the same interval.
Indeed, if this were the case, then $S_{i}\triangle S_{i+1}$ would be
$I_{i}\cup J$, where $J$ is the difference of two initial sums of the interval
in which $S_{i}$ and $S_{i+1}$ end. However, the sum of $I_{i}$ is fractional,
while the sum of $J$ must be an integer, and thus we cannot have both $S_{i}$
and $S_{i+1}$ having sum equal to $1$.

Next, observe that $S_{i}$ must end after $S_{i+1}$. If not, then $S_{i+1}$
contains $S_{i}\setminus I_{i}$ as an initial sum. However, the sum of $S_{i}$
is $1$, while the sum of $I_{i}$ is negative, so this means that $S_{i+1}$ has
an initial sum that is strictly larger than $1$, which is a contradiction.

Hence, it follows that the sets $S_{i}$, $1\leq i\leq b$, all end in distinct
intervals. If $S_{i}$ ends in the interval $I_{j}$, then notice that
$I_{j}\cap S_{i}$ is a tail sum of $S_{i}$, and it must be positive. If this
sum is in $(0,1)$, then as before, we will be able to rotate $S_{i}$, which
means that $\pi_{i}$ is switchable. Otherwise, $I_{j}$ contains an initial sum
that is larger than $1$, but we only have at most $b-1$ such intervals. Thus,
one of $\pi_{1},\ldots,\pi_{b}$ must be switchable.

Hence, we have shown that every set of $b$ consecutive intervals has at least
one bad or switchable permutation. By averaging over the $s$ intervals, it
follows that there are at least $\frac{s}{b}$ bad or switchable permutations,
as required. ∎

##  4 Almost $k$-covers

In this section, we show how our stability result can be used in the
determination of $f(n,k)$, the minimum number of hyperplanes needed for an
almost $k$-cover of the $n$-dimensional hypercube $Q^{n}$.

###  4.1 Constructing small covers

Recall that $f(n,k)$ is the solution to the integer linear program where we
have a variable for every hyperplane, representing the multiplicity with which
it appears in the cover, and a constraint for every nonzero point in
$\\{0,1\\}^{n}$, ensuring the point is covered at least $k$ times.

Unfortunately, integer linear programming is notoriously difficult to solve,
and this is especially true in this setting, as the number of variables
involved grows incredibly quickly. Indeed, there are infinitely many
hyperplanes in $\mathbb{R}^{n}$ that could, in principle, be included in our
cover. However, we can finitise our problem by observing that we need only
consider hyperplanes that intersect the hypercube _maximally_ — that is, if
$H_{1}$ and $H_{2}$ are hyperplanes, both avoiding the origin, and
$H_{1}\cap\\{0,1\\}^{n}\subseteq H_{2}\cap\\{0,1\\}^{n}$, then we can replace
any occurrence of $H_{1}$ in a cover with a copy of $H_{2}$.

Since any $n$ points in $\mathbb{R}^{n}$ determine a unique hyperplane, it
follows that any maximally intersecting hyperplane must contain at least $n$
points of the hypercube. In particular, this implies that there are at most
$\binom{2^{n}-1}{n}$ hyperplanes we need to consider, making the integer
linear program finite.

Unfortunately, there is a considerable difference between _finite_ and
_computationally feasible_ , and this upper bound of $\binom{2^{n}-1}{n}$
grows far too fast to leave us with any hope of computing exact answers even
when $n$ is as small as $6$. While it should be pointed out that this is
indeed just an upper bound, and some hyperplanes are significantly
overcounted, brute-force enumeration of the maximally intersecting hyperplanes
(which we could only carry out for $n\leq 5$) shows that the true number also
exhibits rapid growth.

$n$ | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---
Upper bound | 1 | 3 | 35 | 1365 | 169911 | 67945521
Actual count | 1 | 3 | 11 | 95 | 2629 | ??
Weight-$1$ planes | 1 | 3 | 10 | 35 | 126 | 462
Table 1: The number of maximally intersecting and weight-$1$ hyperplanes in
$\mathbb{R}^{n}$.

In order to be able to proceed computationally, then, it is necessary to
restrict the search space. A natural place to start is by only considering
hyperplanes of maximum weight. Indeed, the Clifton–Huang lower bound (2) shows
that in any almost $k$-cover, the total weight of the hyperplanes must be at
least $H_{n}k$, where $H_{n}$ is the $n$th Harmonic number. To minimise the
size of the cover, then, we would want each hyperplane to have as much weight
as possible.

As we saw in Corollary 1.4, there are far fewer hyperplanes of weight $1$; the
number of these is the much more modest $\binom{2n-1}{n}$. Moreover, Theorem
1.3 characterises these maximum-weight planes, so we are able to set up the
corresponding integer linear program and efficiently search for small covers
when $n=6$. In many cases we are able to find covers matching the
Clifton–Huang lower bound, as shown in Theorem 1.5, which we first restate.

See 1.5

###### Proof.

The Clifton–Huang lower bound (2) gives $f(n,k)\geq\left\lceil
H_{6}k\right\rceil=\frac{49k}{20}$, and so we need only prove the upper bound.
To this end, we solved the integer linear program corresponding to $f(n,k)$
for various values of $k$, restricting ourselves to using the $462$
hyperplanes of weight $1$.

We noted that $f(6,60)=147$, which comes from the general construction given
by Clifton and Huang [5]. We next considered the case $k=20$. The lower bound
implies $f(6,20)\geq 49$, with equality only possible if all hyperplanes
involved have weight $1$. Our integer linear program solver found such an
almost-$k$ cover, which we have provided in Appendix A. Note that this cover
includes hyperplanes with coefficients other than $0$ or $1$; that is, it uses
some of the new weight-$1$ hyperplanes described in Theorem 1.3.

Having thus established that $f(6,20)=49$, we turn to other values of $k$.
Now, since $f(n,k+\ell)\leq f(n,k)+f(n,\ell)$, these together imply that
$f(6,k+20m)\leq f(6,k)+49m$ for all integers $m\geq 1$. We then solved the
integer linear program for all $23\leq k\leq 42$, finding that
$f(n,k)=\left\lceil\frac{49k}{20}\right\rceil$ in all cases except
$k\in\\{31,33,42\\}$. While the first and last of these values are excluded
from our result, we were able to resolve the case $k\equiv 13\pmod{20}$ by
finding $f(6,k)=\left\lceil\frac{49k}{20}\right\rceil$ for $k=53$.

Using this finite set of computational results, together with the recursive
upper bound, it follows that $f(6,k)\leq\left\lceil\frac{49k}{20}\right\rceil$
for all $k\geq 65$ with $k\not\equiv 2,11\pmod{20}$. ∎

It is natural to ask what happens when $k\equiv 2,11\pmod{20}$. Our
computational results were restricted to hyperplanes of weight $1$. However,
by Theorem 1.3, we know that all other hyperplanes have weight at most
$\frac{5}{6}$. Thus, if we have a cover of $m$ planes containing at least one
plane that is not of weight $1$, the total weight of the planes in the cover
is at most $m-\frac{1}{6}$.

For $k\equiv 2,11\pmod{20}$, we have
$\frac{49k}{20}\geq\left\lceil\frac{49k}{20}\right\rceil-\frac{1}{10}$. Hence,
in light of the previous remark, if there is a cover of size
$\left\lceil\frac{49k}{20}\right\rceil$, it must consist entirely of
weight-$1$ hyperplanes. Our solutions to the integer linear program show that
for $k\in\\{11,22,31,42,51,62\\}$, no such cover exists; in all these cases,
we have $f(6,k)=\left\lceil\frac{49k}{20}\right\rceil+1$.

However, it is not inconceivable that further along these sequences, the
Clifton–Huang lower bound is realised; that is, $f(6,2+20m_{0})=5+49m_{0}$ or
$f(6,11+20m_{0})=27+49m_{0}$ for some suitably large $m_{0}$. If this does
happen, then using $f(6,20)=49$, it again follows that we would have equality
for all $m\geq m_{0}$.

Indeed, we also have
$\frac{49k}{20}>\left\lceil\frac{49k}{20}\right\rceil-\frac{1}{6}$ when
$k\equiv 13\pmod{20}$, which means that any cover of size
$\left\lceil\frac{49k}{20}\right\rceil$ can only contain weight-$1$
hyperplanes. Our solutions to the integer linear program show that there are
no such covers for $k=13$ or $k=33$, but it does exist for $k=53$ (and,
therefore, for all further terms in this sequence).

###  4.2 Improving the lower bound

In some cases, though, one can show that the lower bound
$f(n,k)\geq\left\lceil H_{n}k\right\rceil$ is not tight for arbitrarily large
$k$. Using numerical data about the hyperplanes in $\mathbb{R}^{5}$, Clifton
and Huang were able to show that
$f(5,67+60m)=\left\lceil\frac{137k}{60}\right\rceil+1$ for all $m\geq 1$.
Using our stability result, we can extend this to all sufficiently large $n$,
showing that the lower bound is not tight infinitely often.

######  Theorem 4.1.

Let $k\geq 2$ and $n\in\mathbb{N}$ be such that $0<\left\lceil
kH_{n}\right\rceil-kH_{n}<\frac{1}{n\binom{n-1}{\lfloor n/2\rfloor}}$. Then
$f(n,k)\geq\left\lceil kH_{n}\right\rceil+1$.

In particular, if $n$ is sufficiently large, there are infinitely many choices
of $k$ for which $f(n,k)\geq\left\lceil kH_{n}\right\rceil+1$.

###### Proof.

Consider a smallest almost $k$-cover $\mathcal{H}$ of $Q^{n}$, and for each
hyperplane $h$, let $x_{h}$ denote the number of copies of $h$ in
$\mathcal{H}$. We then have

$\left|\mathcal{H}\right|=\sum_{h}x_{h}=\sum_{h}\left(\sum_{S:S\in
h}w(S)+1-\sum_{S:S\in h}w(S)\right)x_{h}.$

We obtain

$\left|\mathcal{H}\right|=\sum_{S}\left(\sum_{h:h\ni
S}x_{h}\right)w(S)+\sum_{h}\left(1-\sum_{S:S\in h}w(S)\right)x_{h}.$

Now, since $\mathcal{H}$ is an almost $k$-cover, we have $\sum_{h:h\ni
S}x_{h}\geq k$ for all $S$. Since

$\sum_{S}w(S)=\sum_{s=1}^{n}\sum_{S:|S|=s}w(S)=\sum_{s=1}^{n}\frac{\binom{n}{s}}{s\binom{n}{s}}=\sum_{s=1}^{n}\frac{1}{s}=H_{n},$

we can further rearrange this equation to obtain

$\left|\mathcal{H}\right|-kH_{n}=\sum_{S}\left(\sum_{h:h\ni
S}x_{h}-k\right)w(S)+\sum_{h}\left(1-\sum_{S:S\in h}w(S)\right)x_{h}.$ (5)

Consider the terms on the right-hand side of (5). Since $\mathcal{H}$ is an
almost $k$-cover, every set is covered at least $k$ times, so $\sum_{h:h\ni
S}x_{h}-k$ is always non-negative integer. Furthermore, by Theorem 1.3, each
hyperplane has weight either exactly $1$ or at most $1-\frac{1}{n}$, which
means $1-\sum_{S:S\in h}w(S)$ is non-negative, and is at least $\frac{1}{n}$
when it is positive. Thus, each individual summand on the right-hand side is
non-negative, and the positive summands are at least
$\min\left(\min_{S}w(S),\frac{1}{n}\right)=\frac{1}{n\binom{n-1}{\lfloor
n/2\rfloor}}$.

Now we look at the left-hand side. Since it must be non-negative, we have
$\left|\mathcal{H}\right|\geq\left\lceil H_{n}k\right\rceil$. Suppose we had
equality. By our assumption on $k$ and $n$, $0<\left\lceil kH_{n}\right\rceil-
kH_{n}<\frac{1}{n\binom{n-1}{\lfloor n/2\rfloor}}$, but we previously
established that the right-hand side, if positive, must be at least
$\frac{1}{n\binom{n-1}{\lfloor n/2\rfloor}}$. Hence, we must have
$f(n,k)=\left|\mathcal{H}\right|\geq\left\lceil kH_{n}\right\rceil+1$.

For the second assertion, let $H_{n}=\frac{c_{n}}{d_{n}}$, where $c_{n}$ and
$d_{n}$ are coprime. We can then find some $1\leq k_{0}\leq d_{n}$ such that
$kc_{n}\equiv-1\pmod{d_{n}}$. It then follows that for any $k\equiv
k_{0}\pmod{d_{n}}$, we have $\left\lceil kH_{n}\right\rceil-
kH_{n}=\frac{1}{d_{n}}$.

As shown by Boyd [4], $d_{n}=e^{(1+o(1))n}$. On the other hand,
$n\binom{n-1}{\lfloor n/2\rfloor}\leq n2^{n-1}$. Hence, for $n$ sufficiently
large, we have $\left\lceil H_{n}k\right\rceil-
H_{n}k<\frac{1}{n\binom{n-1}{\lfloor n/2\rfloor}}$. Thus, for this infinite
sequence of values of $k$, $f(n,k)\geq\left\lceil H_{n}k\right\rceil+1$. ∎

######  Remark.

Note that in the proof of the second statement, it suffices to have $k\equiv
k_{0}\pmod{d_{n}}$ where $k_{0}$ is such that $ck_{0}\equiv-r\pmod{d_{n}}$ for
some $1\leq r<\frac{d_{n}}{n\binom{n-1}{\lfloor n/2\rfloor}}$. This shows that
the linear programming lower bound is not tight for approximately
$(e/2)^{(1+o(1))n}$ of the $e^{(1+o(1))n}$ residue classes.

##  5 Concluding remarks

In this paper, we have studied the Clifton–Huang weighting of hyperplanes,
characterising the hyperplanes of maximum weight, and proving some stability,
showing that all other hyperplanes have weight bounded away from $1$. We have
then shown how this result can be used to determine further values of the
extremal function $f(n,k)$, which is the minimum number of hyperplanes needed
to cover all nonzero points of $Q^{n}$ at least $k$ times, while avoiding the
origin completely. Several open problems remain, and we shall highlight some
possible directions for further research below.

#### Maximal hyperplanes

We have shown that the weight of any hyperplane is either $1$ or at most
$1-\frac{1}{n}$. This latter bound is best possible, as evidenced, for
example, by the plane $\Pi_{c}$ defined by
$x_{1}+x_{2}+\ldots+x_{n-1}+cx_{n}=1$, where
$c\notin\\{-(n-1),-(n-2),\ldots,1\\}$. However, as explained in Section 4,
when we are setting up the integer linear program for the covering problem, we
need only consider hyperplanes that intersect $\\{0,1\\}^{n}$ maximally. Since
$\Pi_{1}$ covers all the points that $\Pi_{c}$ does, and more, the above
hyperplane is not maximal.

We could hope for stronger applications, then, if we could show that the
weight of a _maximal_ hyperplane is either $1$ or much smaller. Unfortunately,
there is not much we can gain here — we can find maximal hyperplanes of weight
$1-\frac{1}{n-1}$. For example, it is known that the following hyperplanes,
together with permutations of coefficients, are maximal hyperplanes of weight
$1-\frac{1}{n-1}$:

  * •

$x_{1}+\cdots+x_{n-2}-kx_{n-1}-(n-2-k)x_{n}=1$,
$k=1,\dots,\lfloor\frac{n-2}{2}\rfloor$.

  * •

$x_{1}+\cdots+x_{n-2}+2x_{n-1}-kx_{n}=1$, $k=1,\dots,n-3$.

  * •

$x_{1}+\cdots+x_{n-3}+2x_{n-2}-kx_{n-1}-(n-2-k)x_{n}=1$,
$k=1,\dots,\lfloor\frac{n-2}{2}\rfloor$.

Still, it would be interesting to prove this larger separation for maximal
hyperplanes, which could be significant for smaller values of $n$.

######  Question 5.1.

Let $h$ be a hyperplane that intersects $Q^{n}$ maximally. Is it true that
either $w(h)=1$ or $w(h)\leq 1-\frac{1}{n-1}$?

In our proof, with somewhat more involved arguments, we are able to establish
the improved bound in some of our cases, including when we have a coefficient
larger than $1$, or when we have a positive fractional coefficient. However,
it remains to resolve the problem in the other cases.

Another direction that could help with reducing the search space for a wider
range of parameters would be to characterise those hyperplanes whose weight is
close to $1$. Initial steps in that direction were taken in Theorem 3.1, and
it would be great to complete the picture.

######  Question 5.2.

Can we characterise all hyperplanes $h$ with
$w(h)=1-O\left(\frac{1}{n}\right)$?

#### Improved lower bounds

In this setting, our lower bounds come from the fractional relaxation of the
integer linear program, whose value was proven to be $H_{n}k$, where $H_{n}$
is the $n$th Harmonic number, by Clifton and Huang [5]. This immediately gives
$f(n,k)\geq\left\lceil H_{n}k\right\rceil$, and Clifton and Huang further
proved that this lower bound is asymptotically tight.

However, it is not always sharp. As we have shown in Theorem 4.1, for every
sufficiently large $n$ there are infinitely many choices of $k$ for which we
have $f(n,k)\geq\left\lceil H_{n}k\right\rceil+1$. However, our methods do not
allow us to prove any larger separation between the fractional and integer
solutions, since an almost $k$-cover of size $\left\lceil
H_{n}k\right\rceil+2$ could contain a hyperplane of very small weight. That
said, in all the computational results we have obtained, we always have
$f(n,k)\leq\left\lceil H_{n}k\right\rceil+1$. It would be interesting to see
how large $f(n,k)-\left\lceil H_{n}k\right\rceil$ can be, and to develop
methods for proving stronger lower bounds.

######  Question 5.3.

Given $n$ and sufficiently large $k$, can we have $f(n,k)\geq\lceil
H_{n}k\rceil+2$?

It is worth reiterating a question of Clifton and Huang, who asked if the
difference between the integer and fractional problems was bounded by an
absolute constant.

######  Question 5.4 (Clifton–Huang [5]).

Is there an absolute constant $C>0$, such that for every $n$ there are only
finitely many $k$ with $f(n,k)\geq\left\lceil H_{n}k\right\rceil+C$?

#### Large dimensions

Finally, we note that while this linear programming approach is very fruitful
in the cases we have considered, where $n$ is fixed and $k$ is large, Clifton
and Huang showed the problem behaves very differently when $k$ is fixed and
$n$ is large. The polynomial method has been fruitful in establishing lower
bounds in this range, but Sauermann and Wigderson [10] showed that the
solution to the algebraic problem is smaller than Clifton and Huang’s
conjectured value of $f(n,k)$.

######  Conjecture 5.5 (Clifton–Huang [5]).

For $k\geq 2$ and $n$ sufficiently large, we have $f(n,k)=n+\binom{k}{2}$.

## Acknowledgement

Shagnik Das is supported by Taiwan NSTC grant 111-2115-M-002-009-MY2. Wei-
Hsuan Yu is supported by MOST under Grant No. 109-2628-M-008-002-MY4. Valjakas
Djaljapayan and Yen-chi Roger Lin are partially supported by MOST under Grant
No. 111-2115-M-003-009.

## References

  * [1] Noga Alon and Zoltán Füredi.  Covering the cube by affine hyperplanes.  European journal of combinatorics, 14(2):79–83, 1993.
  * [2] Anurag Bishnoi, Simona Boyadzhiyska, Shagnik Das, and Tamás Mészáros.  Subspace coverings with multiplicities.  Combinatorics, Probability and Computing, page 1–14, 2023.
  * [3] Béla Bollobás.  On generalized graphs.  Acta Mathematica Academiae Scientiarum Hungarica, 16(3):447–452, 1965.
  * [4] David W. Boyd.  A $p$-adic study of the partial sums of the harmonic series.  Experimental Mathematics, 3(4):287–302, 1994.
  * [5] Alexander Clifton and Hao Huang.  On almost $k$-covers of hypercubes.  Combinatorica, 40(4):511–526, 2020.
  * [6] R. E. Jamison.  Covering finite fields with cosets of subspaces.  Journal of Combinatorial Theory, Series A, 22(3):253–266, 1977\.
  * [7] Péter Komjáth.  Partitions of vector spaces.  Periodica Mathematica Hungarica, 28(3):187–193, 1994.
  * [8] D Lubell.  A short proof of sperner’s lemma.  Classic Papers in Combinatorics, page 402, 1987.
  * [9] Lev D Meshalkin.  Generalization of sperner’s theorem on the number of subsets of a finite set.  Theory of Probability & Its Applications, 8(2):203–204, 1963.
  * [10] Lisa Sauermann and Yuval Wigderson.  Polynomials that vanish to high order on most of the hypercube.  Journal of the London Mathematical Society, 106(3):2379–2402, 2022\.
  * [11] Koichi Yamamoto.  Logarithmic order of free distributive lattice.  Journal of the Mathematical Society of Japan, 6(3-4):343–353, 1954\.

##  Appendix A An almost $20$-cover of $Q^{6}$

We used an integer linear program solver to find an almost $20$-cover of
$Q^{6}$ that consists of 49 hyperplanes. Each row of Table 2 lists the
coefficients $c_{i}$ that give the hyperplane of the form
$\sum_{i=1}^{6}c_{i}x_{i}=1$.

Table 2: The coefficients for hyperplanes $\vec{c}\cdot\vec{x}=1$ in an almost
20-cover in $Q_{*}^{6}$, where $\vec{c}=(c_{1},c_{2},c_{3},c_{4},c_{5},c_{6})$

$c_{1}$ | $c_{2}$ | $c_{3}$ | $c_{4}$ | $c_{5}$ | $c_{6}$
---|---|---|---|---|---
1 | 1 | 1 | 0 | $-1$ | $-1$
1 | 1 | 1 | 0 | $-2$ | 0
1 | 1 | 1 | $-1$ | $-1$ | 0
1 | 1 | 0 | 1 | $-1$ | 0
1 | 1 | 0 | $-2$ | 1 | 1
1 | 1 | $-1$ | 1 | 1 | $-1$
1 | 1 | $-1$ | 1 | 0 | $-1$
1 | 1 | $-1$ | 0 | 0 | 1
1 | 1 | $-2$ | 1 | 0 | 0
1 | 0 | 1 | 0 | 1 | $-1$
1 | 0 | 1 | 0 | 0 | 0
1 | 0 | 1 | 0 | 0 | $-1$
1 | 0 | 1 | $-1$ | $-1$ | 1
1 | 0 | 0 | 1 | 1 | 1
1 | 0 | 0 | 1 | $-1$ | 0
1 | 0 | 0 | 0 | 1 | 0
1 | 0 | 0 | 0 | 0 | 1
1 | 0 | $-1$ | 1 | 1 | 0
1 | 0 | $-1$ | 1 | 0 | 1
1 | $-2$ | 0 | 0 | 1 | 1
0 | 1 | 1 | 1 | 1 | 0
0 | 1 | 1 | 1 | 0 | $-1$
0 | 1 | 1 | 0 | 0 | 1
0 | 1 | 1 | 0 | 0 | 0
0 | 1 | 0 | 1 | $-2$ | 1

$c_{1}$ | $c_{2}$ | $c_{3}$ | $c_{4}$ | $c_{5}$ | $c_{6}$
---|---|---|---|---|---
0 | 1 | 0 | 0 | 1 | 0
0 | 1 | 0 | 0 | 1 | 0
0 | 1 | 0 | 0 | 0 | 1
0 | 1 | 0 | 0 | 0 | 0
0 | 1 | $-1$ | 1 | 1 | 1
0 | 0 | 1 | 1 | 1 | $-1$
0 | 0 | 1 | 1 | 0 | 0
0 | 0 | 1 | 1 | 0 | 0
0 | 0 | 1 | 0 | 1 | 0
0 | 0 | 1 | 0 | 0 | 1
0 | 0 | 1 | 0 | 0 | 1
0 | 0 | 1 | 0 | 0 | 0
0 | 0 | 1 | $-1$ | 1 | 0
0 | 0 | 0 | 1 | 1 | 0
0 | 0 | 0 | 1 | 0 | 1
0 | 0 | 0 | 1 | 0 | 0
0 | 0 | 0 | 0 | 1 | 1
0 | 0 | 0 | 0 | 1 | 0
0 | 0 | 0 | 0 | 1 | 0
0 | 0 | 0 | 0 | 0 | 1
0 | 0 | $-1$ | 1 | 0 | 1
0 | 0 | $-1$ | 0 | 1 | 1
0 | $-1$ | 1 | 0 | 1 | 1
$-1$ | 1 | 0 | 1 | $-1$ | 1


# Uniform continuity bound for sandwiched Rényi conditional entropy

Ashutosh Marwah and Frédéric Dupuis  Département d’informatique et de
recherche opérationnelle,
Université de Montréal,
Montréal QC, Canada

###### Abstract

We prove a simple uniform continuity bound for the sandwiched Rényi
conditional entropy for $\alpha\in[1/2,1)\cup(1,\infty]$, which is independent
of the dimension of the conditioning system.

##  1 Introduction

Conditional entropies quantify the amount of uncertainty of a system when one
has access to side information. Rényi conditional entropies have been
instrumental in understanding both classical and quantum information theoretic
processes in the one-shot domain [1, 2, 3, 4, 5, 6]. There are multiple
generalizations and definitions of Rényi conditional entropies for quantum
states. One of the most important of these is the sandwiched Rényi conditional
entropy [7, 8] (which we denote as $\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}$
following the notation in Tomamichel’s book, Quantum Information Processing
with Finite Resources [9]), which is defined for a quantum state $\rho_{AB}$,
$\alpha\in[1/2,1)\cup(1,\infty]$ and $\alpha^{\prime}=(\alpha-1)/\alpha$ as

$\displaystyle\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}$
$\displaystyle=\sup_{\eta_{B}}\frac{1}{1-\alpha}\log\operatorname{Tr}\left(\eta_{B}^{-\alpha^{\prime}/2}\rho_{AB}\eta_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}.$

where the supremum is taken over all quantum states $\eta_{B}$. For
$\alpha=1/2$, this definition results in $H_{\max}$, which characterizes the
rate of compression for a probabilistic source [10] and for $\alpha=\infty$,
it results in $H_{\min}$, which has been used to characterize the amount of
randomness which one can extract from a system independent of the conditioning
system [2]. Recently, the sandwiched conditional entropies with
$\alpha\in(1,2]$ have also been used to derive bounds for randomness
extraction [6].

Many applications require that we are able to bound the conditional entropy of
one state in terms of another state, which is close to the original state. For
von Neumann conditional entropy, the Alicki-Fannes-Winter (AFW) uniform
continuity bound [11, 12] enables us to do this. It states that for two
quantum states $\rho_{AB}$ and $\sigma_{AB}$ such that
$\frac{1}{2}\left\|\rho_{AB}-\sigma_{AB}\right\|_{1}\leq\epsilon$, we have

$\displaystyle|H(A|B)_{\rho}-H(A|B)_{\sigma}|\leq
2\epsilon\log(d_{A})+(1+\epsilon)h\left(\frac{\epsilon}{1+\epsilon}\right)$
(1)

where the function $h(x)=-x\log(x)-(1-x)\log(1-x)$ is the binary entropy and
$d_{A}$ is the dimension of the vector space $A$. A key feature of this bound
is that it is independent of the size $d_{B}$ of the conditioning system. This
is crucial in many applications, particularly in cryptography, where the
conditioning system often represents an adversary’s system whose size cannot
be bounded. The AFW bound has been used widely in quantum information theory
(see, for example, the converse bounds for channel capacities [13]).

In this paper, we will prove a uniform continuity bound, like the AFW bound,
for sandwiched Rényi conditional entropies. Specifically, in Theorem 1 and
Corollary 1, we prove that for two quantum states $\rho_{AB}$ and
$\sigma_{AB}$ such that
$\frac{1}{2}\left\|\rho_{AB}-\sigma_{AB}\right\|_{1}\leq\epsilon$, and for
$\alpha<1$ we have

$\displaystyle|\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\sigma}-\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}|\leq\log(1+\epsilon)+\frac{1}{1-\alpha}\log\left(1+\epsilon^{\alpha}d_{A}^{2(1-\alpha)}-\frac{\epsilon}{(1+\epsilon)^{1-\alpha}}\right)$

and for $\alpha>1$, we have

$\displaystyle|\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\sigma}$
$\displaystyle-\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}|$
$\displaystyle\leq\log(1+\sqrt{2\epsilon})+\frac{1}{1-\beta}\log\left(1+(\sqrt{2\epsilon})^{\beta}d_{A}^{2(1-\beta)}-\frac{\sqrt{2\epsilon}}{(1+\sqrt{2\epsilon})^{1-\beta}}\right)$

where $\beta$ is such that $\alpha^{-1}+\beta^{-1}=2$.

To prove these, we make use of a simple lemma about the subadditivity of the
function $X\mapsto\operatorname{Tr}(X^{\alpha})$ for $\alpha<1$ and use the
duality relation for sandwiched Rényi conditional entropy, which states that
for a pure tripartite state $\rho_{ABC}$ and an
$\alpha\in[\frac{1}{2},1)\cup(1,\infty]$,
$\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}=-\tilde{H}_{\beta}^{\uparrow}(A|C)_{\rho}$
for $\beta$ such that $\alpha^{-1}+\beta^{-1}=2$.

Jabbour and Datta [14] proved the following tight uniform continuity bound for
classical and quantum-classical states when $\alpha<1$:(1)(1)(1)Jabbour and
Datta [14] use the optimized Petz Rényi conditional entropy definition as the
definition for the quantum Rényi conditional entropy. For classical states and
quantum-classical states, though, their definition of conditional entropy is
equal to the one considered in this paper.

$\displaystyle|\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\sigma}-\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}|\leq\frac{1}{1-\alpha}\log\left((1-\epsilon)^{\alpha}+\epsilon^{\alpha}(d_{A}-1)^{1-\alpha}\right).$
(2)

The proof for Eq. (2) uses conditional majorization [15] and a series of
transforms to tightly convert the probability distributions in question into
distributions it is easier to argue about. The continuity bound proven in this
paper for the Rényi conditional entropy of classical probability distributions
(see Eq. (4) in Theorem 1) is almost the same as Eq. (2). In addition, the
proof of our main theorem (Theorem 1 below) is much simpler than the proof of
Eq. (2). Also Leditzky et al. [16] proved using Hölder’s inequality that for
$\alpha\in[\frac{1}{2},1)$

$\displaystyle\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}-\tilde{H}_{\beta}^{\uparrow}(A|B)_{\sigma}\geq\frac{2\alpha}{1-\alpha}\log
F(\rho_{AB},\sigma_{AB})$

where $\beta$ is such that $\alpha^{-1}+\beta^{-1}=2$ and $F$ is the fidelity
function. Although this inequality is not a continuity bound (since the Rényi
parameter is different in the two terms), it can often be used as a continuity
bound in applications where one of the states is particularly simple (e.g.
maximally entangled, or maximally mixed). (Also see [17, 18] for related
inequalities.)

##  2 Uniform continuity bound for quantum Rényi entropies

In the following, the dimension of a vector space $\mathcal{V}$ will be
succinctly referred to as $d_{\mathcal{V}}$. Also, for Hermitian matrices $P$
and $Q$, we will use the notation $P\geq Q$ to denote that the matrix $P-Q$ is
positive semidefinite.

We will use the sandwiched Rényi relative entropy [7, 8] for our proof. For
$\alpha\in[\frac{1}{2},1)\cup(1,\infty]$ and positive operators $P$ and $Q$
such that $\operatorname{Tr}(P)\neq 0$, the sandwiched Rényi relative entropy
of $P$ relative to $Q$ is defined as

$\displaystyle\tilde{D}_{\alpha}(P||Q):=\begin{cases}\frac{1}{\alpha-1}\log\frac{\operatorname{Tr}\left(Q^{-\alpha^{\prime}/2}PQ^{-\alpha^{\prime}/2}\right)^{\alpha}}{\operatorname{Tr}(P)}&\text{
if }(\alpha<1\text{ and }P\nperp Q)\text{ or }\ker(Q)\subseteq\ker(P)\\\
\infty&\text{else.}\end{cases}$

For $\alpha\in[\frac{1}{2},1)\cup(1,\infty]$, the sandwiched Rényi relative
entropy satisfies the data processing inequality, that is, for any completely
positive and trace-preserving map $\Phi$ and positive operators $P$ and $Q$,
we have

$\displaystyle\tilde{D}_{\alpha}(P||Q)\geq\tilde{D}_{\alpha}(\Phi(P)||\Phi(Q)).$

We begin by stating a lemma about the subadditivity of the trace of matrices
raised to the power of $\alpha\in[0,1]$. This was proven by McCarthy [19]. We
provide a proof here for completeness.

######  Lemma 2.1 (McCarthy’s Inequality [19]).

For positive semidefinite matrices $P$ and $Q$ and $\alpha\in[0,1]$, we have

$\displaystyle\operatorname{Tr}((P+Q)^{\alpha})\leq\operatorname{Tr}(P^{\alpha})+\operatorname{Tr}(Q^{\alpha})$

###### Proof.

First, note that the statement is trivial for $\alpha=0$ and $\alpha=1$. For
the other values of $\alpha$, we will use the following integral
representation of $t^{\alpha}$ where $t\in[0,\infty)$ and $\alpha\in(0,1)$
(see for example Example V.1.10 in Bhatia’s Matrix Analysis [20])

$\displaystyle t^{\alpha}=\int_{0}^{\infty}\frac{t}{\lambda+t}d\mu(\lambda)$

where $\mu$ is a positive measure on $(0,\infty)$. For a positive semidefinite
matrix $X$, and $\alpha\in(0,1)$ we can use this representation to write

$\displaystyle
X^{\alpha}=\int_{0}^{\infty}{X}{(\lambda+X)^{-1}}d\mu(\lambda).$

Thus, we have

$\displaystyle\operatorname{Tr}((P+Q)^{\alpha})$
$\displaystyle=\int_{0}^{\infty}\operatorname{Tr}\left({(P+Q)}{(\lambda+P+Q)^{-1}}\right)d\mu(\lambda)$
$\displaystyle=\int_{0}^{\infty}\operatorname{Tr}\left({P}{(\lambda+P+Q)^{-1}}\right)d\mu(\lambda)+\int_{0}^{\infty}\operatorname{Tr}\left({Q}{(\lambda+P+Q)^{-1}}\right)d\mu(\lambda)$
$\displaystyle\leq\int_{0}^{\infty}\operatorname{Tr}\left({P}{(\lambda+P)^{-1}}\right)d\mu(\lambda)+\int_{0}^{\infty}\operatorname{Tr}\left({Q}{(\lambda+Q)^{-1}}\right)d\mu(\lambda)$
$\displaystyle=\operatorname{Tr}(P^{\alpha}+Q^{\alpha})$

where for the inequality we use the fact that the function $X\mapsto X^{-1}$
is operator anti-monotone (see for example Proposition V.1.6 in Bhatia’s
Matrix Analysis [20]). ∎

We will now use the lemma above to prove the following uniform continuity
bound for sandwiched Rényi entropies with $\alpha<1$.

######  Theorem 1.

For $\alpha<1$, $\epsilon\in[0,1]$ and bipartite normalized quantum states
$\rho_{AB}$ and $\sigma_{AB}$ such that
$\frac{1}{2}\left\|\rho_{AB}-\sigma_{AB}\right\|_{1}\leq\epsilon$, the
difference in sandwiched Rényi conditional entropy for the two states can be
bounded as

$\displaystyle|\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\sigma}-\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}|\leq\log(1+\epsilon)+\frac{1}{1-\alpha}\log\left(1+\epsilon^{\alpha}d_{A}^{2(1-\alpha)}-\frac{\epsilon}{(1+\epsilon)^{1-\alpha}}\right).$
(3)

If, in addition, system $A$ is classical for both $\rho_{AB}$ and
$\sigma_{AB}$ or system $B$ is classical for both states, then we can
strengthen the bound to

$\displaystyle|\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\sigma}-\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}|\leq\log(1+\epsilon)+\frac{1}{1-\alpha}\log\left(1+\epsilon^{\alpha}d_{A}^{1-\alpha}-\frac{\epsilon}{\left(d_{A}(1+\epsilon)\right)^{1-\alpha}}\right).$
(4)

###### Proof.

For $\alpha<1$, we can write the sandwiched Rényi conditional entropy as

$\displaystyle
2^{(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}}=\sup_{\eta_{B}}\operatorname{Tr}\left(\eta_{B}^{-\alpha^{\prime}/2}\rho_{AB}\eta_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}.$
(5)

This form will turn out to be useful later.

We can assume that $\epsilon>0$ as otherwise the bound is trivial. Since the
upper bound in the theorem is increasing in the trace distance, it is
sufficient to prove the bound for
$\left\|\rho_{AB}-\sigma_{AB}\right\|_{1}=2\epsilon$. Let
$\rho_{AB}-\sigma_{AB}=P^{\prime}_{AB}-Q^{\prime}_{AB}$ be the decomposition
of $\rho_{AB}-\sigma_{AB}$ into its positive and negative parts, so that
$P^{\prime}_{AB}\geq 0$ and $Q^{\prime}_{AB}\geq 0$. Note that
$\operatorname{Tr}(P^{\prime}_{AB})=\operatorname{Tr}(Q^{\prime}_{AB})=\epsilon$.
Thus, we can further define the density operators
$P_{AB}:=P^{\prime}_{AB}/\epsilon$ and $Q_{AB}:=Q^{\prime}_{AB}/\epsilon$.

Now, we have that $\sigma_{AB}+\epsilon P_{AB}=\rho_{AB}+\epsilon Q_{AB}$. For
any positive semidefinite operator $\eta_{B}$, we have the following chain of
implications

$\displaystyle\sigma_{AB}+\epsilon P_{AB}=\rho_{AB}+\epsilon Q_{AB}$
$\displaystyle\Rightarrow$ $\displaystyle\
\eta_{B}^{-\alpha^{\prime}/2}\left(\sigma_{AB}+\epsilon
P_{AB}\right)\eta_{B}^{-\alpha^{\prime}/2}=\eta_{B}^{-\alpha^{\prime}/2}\rho_{AB}\
\eta_{B}^{-\alpha^{\prime}/2}+\epsilon\eta_{B}^{-\alpha^{\prime}/2}Q_{AB}\
\eta_{B}^{-\alpha^{\prime}/2}$ $\displaystyle\Rightarrow$
$\displaystyle\operatorname{Tr}\left(\eta_{B}^{-\alpha^{\prime}/2}\left(\sigma_{AB}+\epsilon
P_{AB}\right)\eta_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}=\operatorname{Tr}\left(\eta_{B}^{-\alpha^{\prime}/2}\rho_{AB}\
\eta_{B}^{-\alpha^{\prime}/2}+\epsilon\eta_{B}^{-\alpha^{\prime}/2}Q_{AB}\
\eta_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}$ $\displaystyle\Rightarrow$
$\displaystyle\operatorname{Tr}\left(\eta_{B}^{-\alpha^{\prime}/2}\left(\sigma_{AB}+\epsilon
P_{AB}\right)\eta_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}\leq\operatorname{Tr}\left(\eta_{B}^{-\alpha^{\prime}/2}\rho_{AB}\eta_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}+\epsilon^{\alpha}\operatorname{Tr}\left(\eta_{B}^{-\alpha^{\prime}/2}Q_{AB}\eta_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}$

where we use Lemma 2.1 in the third step. Taking the supremum on the right-
hand side, we get

$\displaystyle\operatorname{Tr}\left(\eta_{B}^{-\alpha^{\prime}/2}\left(\sigma_{AB}+\epsilon
P_{AB}\right)\eta_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}$
$\displaystyle\leq\sup_{\omega_{B}}\left\\{\operatorname{Tr}\left(\omega_{B}^{-\alpha^{\prime}/2}\rho_{AB}\omega_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}+\epsilon^{\alpha}\operatorname{Tr}\left(\omega_{B}^{-\alpha^{\prime}/2}Q_{AB}\omega_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}\right\\}$
$\displaystyle\leq\sup_{\omega_{B}}\left\\{\operatorname{Tr}\left(\omega_{B}^{-\alpha^{\prime}/2}\rho_{AB}\omega_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}\right\\}+\epsilon^{\alpha}\sup_{\omega_{B}}\left\\{\operatorname{Tr}\left(\omega_{B}^{-\alpha^{\prime}/2}Q_{AB}\omega_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}\right\\}.$

Using Eq. (5), we derive that for every state $\eta_{B}$

$\displaystyle\operatorname{Tr}\left(\eta_{B}^{-\alpha^{\prime}/2}\left(\sigma_{AB}+\epsilon
P_{AB}\right)\eta_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}$ $\displaystyle\leq
2^{(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}}+\epsilon^{\alpha}2^{(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{Q}}$
$\displaystyle\leq
2^{(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}}+\epsilon^{\alpha}d_{A}^{1-\alpha}$
(6)

where we have used $\tilde{H}_{\alpha}^{\uparrow}(A|B)_{Q}\leq\log(d_{A})$ to
derive the last line. Now, we will try to lower bound the term on the left-
hand side. For an arbitrary $\delta>0$, there exist states $\mu_{B}$ and
$\nu_{B}$ such that

$\displaystyle 2^{(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\sigma}}$
$\displaystyle\leq\operatorname{Tr}\left(\mu_{B}^{-\alpha^{\prime}/2}\sigma_{AB}\mu_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}+\delta$
(7) $\displaystyle 2^{(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{P}}$
$\displaystyle\leq\operatorname{Tr}\left(\nu_{B}^{-\alpha^{\prime}/2}P_{AB}\nu_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}+\delta.$
(8)

We use these states to define the state $\theta_{BC}$ as

$\displaystyle\theta_{BC}:=\frac{1}{1+\epsilon}\mu_{B}\otimes\ket{0}\bra{0}_{C}+\frac{\epsilon}{1+\epsilon}\nu_{B}\otimes\ket{1}\bra{1}_{C}.$

Also, define

$\displaystyle\bar{\sigma}_{ABC}:=\frac{1}{1+\epsilon}\sigma_{AB}\otimes\ket{0}\bra{0}_{C}+\frac{\epsilon}{1+\epsilon}P_{AB}\otimes\ket{1}\bra{1}_{C}.$

With these definitions, we have the following chain of inequalities

$\displaystyle\operatorname{Tr}\left(\theta_{B}^{\frac{-\alpha^{\prime}}{2}}(\sigma_{AB}+\epsilon
P_{AB})\theta_{B}^{\frac{-\alpha^{\prime}}{2}}\right)^{\alpha}$
$\displaystyle=(1+\epsilon)^{\alpha}\operatorname{Tr}\left(\theta_{B}^{\frac{-\alpha^{\prime}}{2}}\bar{\sigma}_{AB}\theta_{B}^{\frac{-\alpha^{\prime}}{2}}\right)^{\alpha}$
$\displaystyle=(1+\epsilon)^{\alpha}2^{-(1-\alpha)\tilde{D}_{\alpha}(\bar{\sigma}_{AB}||\operatorname{\mathds{1}}_{A}\otimes\theta_{B})}$
$\displaystyle\geq(1+\epsilon)^{\alpha}2^{-(1-\alpha)\tilde{D}_{\alpha}(\bar{\sigma}_{ABC}||\operatorname{\mathds{1}}_{A}\otimes\theta_{BC})}$
$\displaystyle=(1+\epsilon)^{\alpha-1}\operatorname{Tr}\left(\mu_{B}^{-\alpha^{\prime}/2}\sigma_{AB}\mu_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}+$
$\displaystyle\hskip
71.13188pt\epsilon(1+\epsilon)^{\alpha-1}\operatorname{Tr}\left(\nu_{B}^{-\alpha^{\prime}/2}P_{AB}\nu_{B}^{-\alpha^{\prime}/2}\right)^{\alpha}$
$\displaystyle\geq(1+\epsilon)^{\alpha-1}\left[2^{(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\sigma}}+\epsilon
2^{(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{P}}\right]$
$\displaystyle\hskip 71.13188pt-(1+\epsilon)^{\alpha}\delta$
$\displaystyle\geq(1+\epsilon)^{\alpha-1}\left[2^{(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\sigma}}+\epsilon
d_{A}^{\alpha-1}\right]$ $\displaystyle\hskip
71.13188pt-(1+\epsilon)^{\alpha}\delta$

where we use the data processing inequality for $\tilde{D}_{\alpha}$ for the
first inequality, the definitions of the states $\mu_{B}$ and $\nu_{B}$ (Eq.
(7), (8)) in the second last step and the fact that
$\tilde{H}_{\alpha}^{\uparrow}(A|B)_{P}\geq-\log(d_{A})$ in the last step.
Combining this inequality with the upper bound in Eq. (6) yields

$\displaystyle 2^{(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\sigma}}$
$\displaystyle\leq(1+\epsilon)^{1-\alpha}2^{(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}}+(1+\epsilon)^{1-\alpha}\epsilon^{\alpha}d_{A}^{1-\alpha}-\epsilon
d_{A}^{\alpha-1}+(1+\epsilon)\delta.$

Since $\delta$ is arbitrary we can let $\delta\rightarrow 0$. Further, taking
the logarithm on both sides and dividing by $1-\alpha>0$, we get

$\displaystyle\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\sigma}$
$\displaystyle\leq\frac{1}{1-\alpha}\log\left((1+\epsilon)^{1-\alpha}2^{(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}}+(1+\epsilon)^{1-\alpha}\epsilon^{\alpha}d_{A}^{1-\alpha}-\epsilon
d_{A}^{\alpha-1}\right)$

We can now bound the difference of the conditional entropies as

$\displaystyle\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\sigma}-\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}$
$\displaystyle\leq\frac{1}{1-\alpha}\log\left((1+\epsilon)^{1-\alpha}2^{(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}}+(1+\epsilon)^{1-\alpha}\epsilon^{\alpha}d_{A}^{1-\alpha}-\epsilon
d_{A}^{\alpha-1}\right)$ $\displaystyle\hskip
71.13188pt-\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}$
$\displaystyle=\frac{1}{1-\alpha}\log\left((1+\epsilon)^{1-\alpha}+\left((1+\epsilon)^{1-\alpha}\epsilon^{\alpha}d_{A}^{1-\alpha}-\epsilon
d_{A}^{\alpha-1}\right)2^{-(1-\alpha)\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}}\right)$
$\displaystyle\leq\frac{1}{1-\alpha}\log\left((1+\epsilon)^{1-\alpha}+\left((1+\epsilon)^{1-\alpha}\epsilon^{\alpha}d_{A}^{1-\alpha}-\epsilon
d_{A}^{\alpha-1}\right)d_{A}^{1-\alpha}\right)$
$\displaystyle=\log(1+\epsilon)+\frac{1}{1-\alpha}\log\left(1+\epsilon^{\alpha}d_{A}^{2(1-\alpha)}-\frac{\epsilon}{(1+\epsilon)^{1-\alpha}}\right)$

where we used the fact that
$(1+\epsilon)^{1-\alpha}\epsilon^{\alpha}d_{A}^{1-\alpha}\geq\epsilon
d_{A}^{\alpha-1}$ since $d_{A}\geq 1$, which implies that the right-hand side
in the second line is a decreasing function in
$\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}$, which we again lower bound by
$-\log(d_{A})$ (when $A$ or $B$ is classical, we can use
$\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}\geq 0$ and derive the stronger
bound in Eq. (4)). Since we did not use any specific property of $\rho_{AB}$
or $\sigma_{AB}$, one can derive the same upper bound by switching $\rho_{AB}$
and $\sigma_{AB}$. ∎

It is worth noting that in the limit $\alpha\rightarrow 1$, the bound in Eq.
(3) yields the bound

$\displaystyle|H(A|B)_{\rho}-H(A|B)_{\sigma}|\leq
2\epsilon\log(d_{A})+(1+\epsilon)\log(1+\epsilon)-\epsilon\log(\epsilon)$

which is equal to the tight continuity bound for conditional von Neumann
entropy (Eq. 1) proven by Winter [12]. This indicates that our bound is close
to being tight in the regime where $\alpha$ is close to $1$ and $\alpha<1$.

We will now prove a uniform continuity bound for sandwiched Rényi conditional
entropies with $\alpha>1$ as a corollary to the above theorem by making use of
the duality relation for these entropies. Recall that according to the duality
relation [7, 21] for $\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}$, we have that
for a pure state $\rho_{ABC}$

$\displaystyle\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}=-\tilde{H}_{\beta}^{\uparrow}(A|C)_{\rho}$

for $\alpha,\beta\in[1/2,1)\cup(1,\infty]$ satisfying
$\alpha^{-1}+\beta^{-1}=2$. Note that for $\alpha\in(1,\infty]$, the $\beta$
satisfying the duality condition lies in $[1/2,1)$.

######  Corollary 1.

For $\alpha>1$, $\epsilon\in[0,1]$ and bipartite normalized quantum states
$\rho_{AB}$ and $\sigma_{AB}$ such that
$\frac{1}{2}\left\|\rho_{AB}-\sigma_{AB}\right\|_{1}\leq\epsilon$, the
difference in sandwiched Rényi conditional entropy for the two states can be
bounded as

$\displaystyle|\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\sigma}$
$\displaystyle-\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}|$
$\displaystyle\leq\log(1+\sqrt{2\epsilon})+\frac{1}{1-\beta}\log\left(1+(\sqrt{2\epsilon})^{\beta}d_{A}^{2(1-\beta)}-\frac{\sqrt{2\epsilon}}{(1+\sqrt{2\epsilon})^{1-\beta}}\right)$
(9)

for $\beta=\frac{\alpha}{2\alpha-1}$ defined such that
$\alpha^{-1}+\beta^{-1}=2$.

###### Proof.

If $\frac{1}{2}\left\|\rho_{AB}-\sigma_{AB}\right\|_{1}\leq\epsilon$, then
using the Fuchs-van de Graaf inequality along with Uhlmann’s theorem, we can
find purifications $\rho_{ABC}$ and $\sigma_{ABC}$ such that

$\displaystyle\frac{1}{2}\left\|\rho_{ABC}-\sigma_{ABC}\right\|_{1}\leq\sqrt{2\epsilon}.$

For $\alpha>1$, choose $\beta<1$ such that $\alpha^{-1}+\beta^{-1}=2$, then
using the duality relation and Theorem 1 we have that

$\displaystyle|\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\sigma}-\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}|$
$\displaystyle=|\tilde{H}_{\beta}^{\uparrow}(A|C)_{\sigma}-\tilde{H}_{\beta}^{\uparrow}(A|C)_{\rho}|$
$\displaystyle\leq\log(1+\sqrt{2\epsilon})+\frac{1}{1-\beta}\log\left(1+(\sqrt{2\epsilon})^{\beta}d_{A}^{2(1-\beta)}-\frac{\sqrt{2\epsilon}}{(1+\sqrt{2\epsilon})^{1-\beta}}\right)$

∎

We expect that the bound in Eq. (9) is not tight in the constants and the
exponents. For $H_{\min}=\tilde{H}_{\infty}^{\uparrow}$, the corollary above
gives us the bound

$\displaystyle|{H}_{\min}(A|B)_{\sigma}-{H}_{\min}(A|B)_{\rho}|\leq\log(1+\sqrt{2\epsilon})+2\log\left(1+(2\epsilon)^{1/4}d_{A}-\frac{\sqrt{2\epsilon}}{(1+\sqrt{2\epsilon})^{1/2}}\right)$

It is easy to prove a tighter uniform continuity bound with an upper bound of
$\log(1+\epsilon d_{A}^{2})$ for $H_{\min}$. We prove it in the Appendix as
Theorem 2. Nevertheless, the bound above is independent of the conditioning
system, and it should be sufficient for most applications.

##  3 Conclusion

We proved a simple uniform continuity bound for the sandwiched Rényi
conditional entropy. Further work should look at improving these bounds,
especially for $\alpha>1$. Deriving continuity bounds for other Rényi
conditional entropies also remains an open problem.

## Acknowledgements

We would like to thank Mark Wilde for his comments and for pointing us to work
related to this paper. AM is supported by bourse d’excellence Google and would
like to thank Google for their financial support. This research was also
supported by Canada’s NSERC.

##  Appendix A Uniform continuity bound for $H_{\min}$

In the following theorem, we prove a simple and tighter uniform continuity
bound for $H_{\min}=\tilde{H}_{\infty}^{\uparrow}$. Recall that $H_{\min}$ can
be equivalently defined as

$\displaystyle
H_{\min}(A|B)_{\rho}:=\max\left\\{\lambda\in\mathbb{R}:\text{there exists
$\eta_{B}$ such that }\rho_{AB}\leq
2^{-\lambda}\operatorname{\mathds{1}}_{A}\otimes\eta_{B}\right\\}.$

######  Theorem 2.

For $\epsilon\in[0,1]$ and bipartite normalized quantum states $\rho_{AB}$ and
$\sigma_{AB}$ such that
$\frac{1}{2}\left\|\rho_{AB}-\sigma_{AB}\right\|_{1}\leq\epsilon$, the
difference in the min-entropy for the two states can be bounded as

$\displaystyle|H_{\min}(A|B)_{\sigma}-H_{\min}(A|B)_{\rho}|\leq\log(1+\epsilon
d_{A}^{2}).$ (10)

###### Proof.

Once again, since the upper bound in the theorem is increasing in $\epsilon$,
we can simply prove the bound for states $\rho_{AB}$ and $\sigma_{AB}$ such
that $\frac{1}{2}\left\|\rho_{AB}-\sigma_{AB}\right\|_{1}=\epsilon$. We also
assume that $\epsilon>0$. Then, following the argument in Theorem 1, we can
write $\rho_{AB}-\sigma_{AB}=\epsilon P_{AB}-\epsilon Q_{AB}$ for density
operators $P_{AB}$ and $Q_{AB}$. We will now use the fact that
$\sigma_{AB}\leq\rho_{AB}+\epsilon Q_{AB}$. Using the definition of
$H_{\min}(A|B)_{\rho}$, we know that there exists a state $\eta_{B}$ such that

$\displaystyle\rho_{AB}\leq
2^{-H_{\min}(A|B)_{\rho}}\operatorname{\mathds{1}}_{A}\otimes\eta_{B}.$

Also, since $H_{\min}(A|B)_{Q}\geq-\log(d_{A})$, we have

$\displaystyle Q_{AB}$ $\displaystyle\leq
2^{-H_{\min}(A|B)_{Q}}\operatorname{\mathds{1}}_{A}\otimes\eta^{\prime}_{B}$
$\displaystyle\leq d_{A}\operatorname{\mathds{1}}_{A}\otimes\eta^{\prime}_{B}$

for some state $\eta^{\prime}_{B}$. Thus, we have

$\displaystyle\sigma_{AB}$ $\displaystyle\leq\rho_{AB}+\epsilon Q_{AB}$
$\displaystyle\leq
2^{-H_{\min}(A|B)_{\rho}}\operatorname{\mathds{1}}_{A}\otimes\eta_{B}+\epsilon
d_{A}\operatorname{\mathds{1}}_{A}\otimes\eta^{\prime}_{B}$
$\displaystyle\leq(2^{-H_{\min}(A|B)_{\rho}}+\epsilon
d_{A})\operatorname{\mathds{1}}_{A}\otimes\left(\frac{2^{-H_{\min}(A|B)_{\rho}}\eta_{B}+\epsilon
d_{A}\eta^{\prime}_{B}}{2^{-H_{\min}(A|B)_{\rho}}+\epsilon d_{A}}\right)$

which implies that

$\displaystyle 2^{-H_{\min}(A|B)_{\sigma}}\leq
2^{-H_{\min}(A|B)_{\rho}}+\epsilon d_{A}$ $\displaystyle\Rightarrow
2^{H_{\min}(A|B)_{\rho}-H_{\min}(A|B)_{\sigma}}\leq 1+\epsilon
d_{A}2^{H_{\min}(A|B)_{\rho}}$ $\displaystyle\Rightarrow
H_{\min}(A|B)_{\rho}-H_{\min}(A|B)_{\sigma}\leq\log\left(1+\epsilon
d_{A}^{2}\right).$

A similar bound can be proven in the opposite direction if we follow the above
procedure with $\rho_{AB}$ and $\sigma_{AB}$ interchanged. ∎

## References

  * [1] E. Arikan.  An inequality on guessing and its application to sequential decoding.  IEEE Transactions on Information Theory, 42(1):99–105, 1996.
  * [2] Renato Renner and Robert König.  Universally composable privacy amplification against quantum adversaries.  In Joe Kilian, editor, Theory of Cryptography, pages 407–425, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
  * [3] Masahito Hayashi.  Large deviation analysis for quantum security via smoothing of Rényi entropy of order 2, 2013.
  * [4] Frédéric Dupuis, Omar Fawzi, and Renato Renner.  Entropy accumulation.  Communications in Mathematical Physics, 379(3):867–913, 2020.
  * [5] Rotem Arnon-Friedman, Frédéric Dupuis, Omar Fawzi, Renato Renner, and Thomas Vidick.  Practical device-independent quantum cryptography via entropy accumulation.  Nature Communications, 9(1):459, 2018.
  * [6] Frédéric Dupuis.  Privacy amplification and decoupling without smoothing, 2021.
  * [7] Martin Müller-Lennert, Frédéric Dupuis, Oleg Szehr, Serge Fehr, and Marco Tomamichel.  On quantum Rényi entropies: A new generalization and some properties.  Journal of Mathematical Physics, 54(12):122203, 2013.
  * [8] Mark M. Wilde, Andreas Winter, and Dong Yang.  Strong converse for the classical capacity of entanglement-breaking and hadamard channels via a sandwiched Rényi relative entropy.  Communications in Mathematical Physics, 331(2):593–622, 2014.
  * [9] Marco Tomamichel.  Quantum Information Processing with Finite Resources.  Springer International Publishing, 2016.
  * [10] Robert König, Renato Renner, and Christian Schaffner.  The operational meaning of min- and max-entropy.  IEEE Transactions on Information Theory, 55(9):4337–4347, Sep 2009\.
  * [11] R Alicki and M Fannes.  Continuity of quantum conditional information.  Journal of Physics A: Mathematical and General, 37(5):L55–L57, Jan 2004.
  * [12] Andreas Winter.  Tight uniform continuity bounds for quantum entropies: Conditional entropy, relative entropy distance and energy constraints.  Communications in Mathematical Physics, 347(1):291–313, 2016.
  * [13] Mark M. Wilde.  Quantum Information Theory.  Cambridge University Press, 2013.
  * [14] Michael G. Jabbour and Nilanjana Datta.  A tight uniform continuity bound for the Arimoto-Rényi conditional entropy and its extension to classical-quantum states, 2020.
  * [15] Gilad Gour, Andrzej Grudka, Michał Horodecki, Waldemar Kłobus, Justyna Łodyga, and Varun Narasimhachar.  Conditional uncertainty principle.  Physical Review A, 97(4), Apr 2018.
  * [16] Felix Leditzky, Mark M. Wilde, and Nilanjana Datta.  Strong converse theorems using rényi entropies.  Journal of Mathematical Physics, 57(8):082202, Aug 2016.
  * [17] Xin Wang and Mark M. Wilde.  Resource theory of asymmetric distinguishability.  Physical Review Research, 1(3), Dec 2019.
  * [18] J. Eisert and M. M. Wilde.  A smallest computable entanglement monotone, 2022.
  * [19] Charles A. McCarthy.  Cp.  Israel Journal of Mathematics, 5(4):249–271, 1967.
  * [20] Rajendra Bhatia.  Matrix Analysis, volume 169.  Springer, 1997.
  * [21] Salman Beigi.  Sandwiched Rényi divergence satisfies data processing inequality.  Journal of Mathematical Physics, 54(12):122202, 2013.