# The exceptional set for integers of the form $[p_{1}^{c}]+[p_{2}^{c}]$

Roger Baker  Department of Mathematics
Brigham Young University
Provo, UT 84602, U.S.A<EMAIL_ADDRESS>
###### Abstract.

Let $1<c<24/19$. We show that the number of integers $n\leq N$ that cannot be
written as $[p_{1}^{c}]+[p_{2}^{c}]$ ($p_{1}$, $p_{2}$ primes) is
$O(N^{1-\sigma+\varepsilon})$. Here $\sigma$ is a positive function of $c$
(given explicitly) and $\varepsilon$ is an arbitrary positive number.

###### Key words and phrases:

Exponential sums, the Hardy-Littlewood method.

###### 2020 Mathematics Subject Classification:

Primary 11N36; Secondary 11L20.

##  1\. Introduction

Let $\mathcal{E}_{c}(N)$ denote the set of integers $n\leq N$ which cannot be
represented in the form $n=[p_{1}^{c}]+[p_{2}^{c}]$. Here $c$ is a constant,
$c>1$ and $p_{1}$, $p_{2}$ are primes. We seek to show for as large a range of
$c$ as possible that the cardinality $|\mathcal{E}_{c}(N)|$ is of smaller
order than $N$ as $N\to\infty$. There is a result of this kind due to Laporta
[7]: let $c\in\left(1,\frac{17}{16}\right)$. Then for any $\varepsilon>0$ and
$B>0$,

(1.1) $|\mathcal{E}_{c}(N)|\ll N\,\exp(-B(\log N)^{\frac{1}{3}-\varepsilon}).$

The implied constant in (1.1) depends on $B$ and $\varepsilon$.

For the shorter range $c\in\left(1,\frac{24}{23}\right)$, Zhu [8] established
a bound that saves a power of $N$; for $\varepsilon>0$,

(1.2) $|\mathcal{E}_{c}(N)|\ll N^{41/18-4\gamma/3+\varepsilon}.$

Here and below $\gamma=1/c$. The implied constant depends on $c$ and
$\varepsilon$ in (1.2).

In the present paper we make a power saving for a longer range of $c$.

######  Theorem 1.

Let $1<c<24/19$ and write

$\sigma=\min\left(\frac{48-38c}{29}\,,\,\frac{16-10c}{75}\right).$

We have

(1.3) $|\mathcal{E}_{c}(N)|\ll N^{1-\sigma+\varepsilon}.$

The implied constant in (1.3) depends on $c$ and $\varepsilon$.

Our argument is an application of the Hardy-Littlewood method, with a single
‘major arc’

$\mathcal{M}:=[-\omega,\omega]\,,\,\omega=N^{-\frac{1}{3}-\varepsilon}.$

The discussion of the major arc follows Zhu [8]. On the minor arc

$m:=[\omega,1-\omega],$

we need to give a good fourth power moment bound for the exponential sum

(1.4) $T(x)=\sum_{p\leq M^{\gamma}}\log p\,e(x[p^{c}]).$

The calculations here are somewhat similar to material in [2]. A device of Cai
[3] (see Lemma 6 (i) below and an exponential sum bound of Heath-Brown [6]
(Lemma 4 below) play a key role.

##  2\. Preparatory Lemmas

We assume throughout that $1<c<24/19$ and that the positive number
$\varepsilon$ is sufficiently small. Constants implied by ‘$\ll$’ and ‘$O$’
depend at most on $c$ and $\varepsilon$, unless otherwise stated. We write
$A\asymp B$ when $A\ll B\ll A$.

######  Lemma 1.

Let $0<x<1$. For real numbers $a_{n}$, $|a_{n}|\leq 1$, let

$W(X,x)=\sum_{1\leq n\leq X}a_{n}e(x[n^{c}]).$

Given $H$, $2\leq H\leq X$, we have

$\displaystyle W(X,x)$ $\displaystyle\ll\frac{X\mathcal{L}}{H}+\sum_{0\leq
h\leq H}\min\left(1,\frac{1}{h}\right)\Bigg{|}\sum_{1\leq n\leq
X}a_{n}e((h+\gamma)n^{c})\Bigg{|}$
$\displaystyle\quad+\sum_{h=1}^{\infty}\min\left(\frac{1}{h}\,,\,\frac{H}{h^{2}}\right)\Bigg{|}\sum_{1\leq
n\leq X}e(hn^{c})\Bigg{|}.$

Here $\gamma\in\\{x,-x\\}$, while (here and below), $\mathcal{L}=\log X$.

###### Proof.

This is a variant of [2], Lemma 1, where the summation over $n$ runs over
$\left(\frac{X}{8},X\right]$. The proof is unchanged. ∎

######  Lemma 2.

Let $\ell\geq 0$ be a given integer, $L=2^{\ell}$. Suppose that $f$ has
$\ell+2$ continuous derivatives on $\left[\frac{X}{2},X\right]$ and

(2.1) $|f^{(r)}(x)|\asymp
FX^{-r}\quad\left(r=1,\ldots,\ell+2,\,x\in\left[\frac{X}{2},X\right]\right).$

Then for $[a,b]\subset\left[\frac{X}{2},X\right]$, we have

(2.2) $\sum_{a\leq n\leq b}e(f(n))\ll
F^{1/(4L-2)}X^{1-(\ell+2)/(4L-2)}+F^{-1}X.$

The implied constant in (2.2) depends only on the implied constant in (2.1).

###### Proof.

Graham and Kolesnik [4], Theorem 2.9. ∎

######  Lemma 3 (B process).

Suppose that $f^{\prime\prime}<0$ and, for $x\in\left[\frac{X}{2},X\right]$,

$|f^{\prime\prime}(x)|\asymp FX^{-2},\ f^{(j)}(x)\ll FX^{-j}\quad(j=3,4).$

Define $x_{\nu}$ by $f^{\prime}(x_{\nu})=\nu$ and let
$\phi(\nu)=-f(x_{\nu})+\nu x_{\nu}$. Then for
$[a,b]\subset\left[\frac{X}{2},X\right]$, we have

$\displaystyle\sum_{a\leq n\leq b}e(f(n))$
$\displaystyle=\sum_{f^{\prime}(b)\leq\nu\leq
f^{\prime}(a)}\frac{e(\phi(\nu)-1/8)}{|f^{\prime\prime}(x_{\nu})|^{1/2}}$
$\displaystyle\hskip 36.135pt+O(\log(FX^{-1}+2)+F^{-1/2}X).$

###### Proof.

[4], Lemma 3.6. ∎

######  Lemma 4.

Let $k$ be an integer, $k\geq 3$. Let $f$ have continuous derivatives
$f^{(j)}$ $(1\leq j\leq k)$ on $[0,N]$,

$|f^{(k)}(x)|\asymp\lambda_{k}\quad\text{ on }(0,N].$

Then for $(a,b]\subset(0,N]$,

$\sum_{a\leq n\leq b}e(f(n))\ll
N^{1+\varepsilon}\left(\lambda_{k}^{\frac{1}{k(k-1)}}+N^{-\frac{1}{k(k-1)}}+N^{-\frac{2}{k(k-1)}}\lambda_{k}^{-\frac{2}{k^{2}(k-1)}}\right).$

###### Proof.

Heath-Brown [6], Theorem 1. ∎

######  Lemma 5.

Let $0<B<1$ and $|c_{n}|\leq 1$. Let

$V(x)=\sum_{1\leq n\leq X}c_{n}e([n^{c}]x).$

Then

$\int_{B}^{2B}|V(y)|^{2}dy\ll XB+X^{2-c}\mathcal{L}.$

###### Proof.

[2], Lemma 12. ∎

Let $\|\theta\|$ denote distance of $\theta$ from the nearest integer.

######  Lemma 6.

(i) Suppose that $a_{n}$ $(1\leq n\leq X)$ are complex numbers with
$a_{n}\ll\mathcal{L}$. Let

$V(n)=\sum_{1\leq n\leq X}a_{n}e(x[n^{c}]).$

Suppose that $U>0$ satisfies

$\sum_{1\leq n\leq X}e(x[n^{c}])\ll
U+\mathcal{L}X^{1-c}\|x\|^{-1}\quad(0<|x|\leq 2).$

Then for any Borel measurable bounded function $G$ on $[\omega,1-\omega]$, we
have

(2.3) $\displaystyle\left|\int_{\omega}^{1-\omega}V(x)G(x)dx\right|^{2}$
$\displaystyle\qquad\ll\mathcal{L}^{4}X^{2-c}\int_{\omega}^{1-\omega}|G(x)|^{2}dx+\mathcal{L}^{2}UX\left(\int_{\omega}^{1-\omega}|G(x)|dx\right)^{2}.$

(ii) Suppose further that

$V(x)\ll V\quad(x\in[\omega,1-\omega]).$

Then

$\int_{\omega}^{1-\omega}|V(x)|^{4}dx\ll\mathcal{L}^{4}(V^{2}X^{2-c}+UX^{2}).$

###### Proof.

Arguing as in [2], proof of Lemma 13, the left-hand side of (2.3) is

$\displaystyle\ll
X\mathcal{L}^{2}\int_{\omega}^{1-\omega}|G(y)|\int_{\omega}^{1-\omega}|G(x)|U\,dx$
$\displaystyle+X\mathcal{L}^{3}\int_{\omega}^{1-\omega}|G(y)|\int_{\omega}^{1-\omega}|G(x)|\min\left(X,\frac{X^{1-c}}{\|x-y\|}\right)dxdy.$

It now suffices to show that

(2.4) $\displaystyle\int_{\omega}^{1-\omega}$
$\displaystyle|G(y)|\int_{\omega}^{1-\omega}|G(x)|\min\left(X,\frac{X^{1-c}}{\|x-y\|}\right)dxdy$
$\displaystyle\ll X^{1-c}\mathcal{L}\int_{\omega}^{1-\omega}|G(x)|^{2}dx.$

The left-hand side of (2.4) is

$\displaystyle\leq\frac{1}{2}\int_{\omega}^{1-\omega}\int_{\omega}^{1-\omega}(|G(x)|^{2}+|G(y)|^{2})\min\left(X,\frac{X^{1-c}}{\|x-y\|}\right)dxdy$
$\displaystyle=\int_{\omega}^{1-\omega}|G(x)|^{2}\int_{\omega}^{1-\omega}\min\left(X,\frac{X^{1-c}}{\|x-y\|}\right)dxdy.$

It is a straightforward matter to show that the last inner integral is $\ll
X^{1-c}\mathcal{L}$, and (2.4) follows.

For part (ii) we take $G(x)=\overline{V}(x)|V(x)|^{2}$. Now

$\int_{\omega}^{1-\omega}|G(x)|^{2}dx\ll
V^{2}\int_{\omega}^{1-\omega}|V(x)|^{4}dx$

while Cauchy’s inequality together with Lemma 5 yields

$\displaystyle\int_{\omega}^{1-\omega}|G(x)|dx$
$\displaystyle\leq\int_{\omega}^{1-\omega}|V(x)|^{2}dx\int_{\omega}^{1-\omega}|V(x)|^{4}dx$
$\displaystyle\ll X\mathcal{L}^{2}\int_{\omega}^{1-\omega}|V(x)|^{4}dx.$

Now part (i) yields

$\left(\int_{\omega}^{1-\omega}|V(x)|^{4}dx\right)^{2}\ll\int_{\omega}^{1-\omega}|V(x)|^{4}dx\
\mathcal{L}^{4}(X^{2-c}V^{2}+UX^{2}),$

and (ii) follows. ∎

######  Lemma 7.

Let $G$ be a complex function on $[1,X]$. Let $u\geq 1$, $v$, $z$ be numbers
satisfying $u^{2}\leq z$, $128uz^{2}\leq X$, and $2^{20}X\leq v^{3}$. Then

$\sum_{1\leq n\leq X}\Lambda(n)G(n)$

is a linear combination (with bounded coefficients) of $O(\mathcal{L})$ sums
of the form

$\sum_{m}a_{m}\sum_{n\geq z}(\log n)^{4}G(mn)$

with $h=0$ or 1, $|a_{m}|\leq d(m)^{5}$, together with $O(\mathcal{L}^{3})$
sums of the form

$\underset{1\leq mn\leq X}{\sum_{m}a_{n}\sum_{u\leq n\leq v}}b_{n}G(mn)$

in which $|a_{m}|\leq d(m)^{5}$, $|b_{n}|\leq d(n)^{5}$. Here $d(\cdots)$ is
the divisor function.

###### Proof.

Heath-Brown [5], pp. 1367–1368. ∎

Throughout the rest of the paper, let $2\leq M\leq N$. We write $X=M^{\gamma}$
and recall the definition of $T(x)$ in (1.4).

######  Lemma 8.

We have, for $n\in[M/2,M]$,

$\int_{-\omega}^{\omega}T(x)^{2}e(-xn)dx=\frac{\Gamma^{2}(1+\gamma)}{\Gamma(2\gamma)}\,n^{2\gamma-1}+0\left(M^{2\gamma-1}\exp\left(-a\left(\frac{\log
M}{\log\log M}\right)^{1/3}\right)\right),$

where $a$ is a positive constant. The implied constant depends on $c$ and $a$.

###### Proof.

This is Lemma 3.6 of Zhu [8], with minor corrections provided on p. 197 of the
erratum. ∎

##  3\. Proof of Theorem 1

Let $R(n)$ be the number of representations $n=[p_{1}^{c}]+[p_{2}^{c}]$,
$p_{1}$ and $p_{2}$ prime. We proceed initially as on p. 198 of Zhu [8]. For
our theorem, it suffices by a dyadic argument to show that when $M\leq N$, the
quantity

$Z(M):=\left|\left\\{n\in\left(\frac{M}{2},M\right]:\ R(n)=0\right\\}\right|.$

satisfies

$Z(M)\ll M^{1-\sigma+\varepsilon}.$

Let $n\in\left(\frac{M}{2},M\right]$. If $R(n)=0$, then

$\int_{-\omega}^{1-\omega}T(x)^{2}e(-xn)dx=0,$

and Lemma 8 yields

$\left|\int_{m}T(x)e(-xn)dx\right|=\left|\int_{\mathcal{M}}T(x)^{2}e(-xn)dx\right|\gg
M^{2\gamma-1}.$

Thus

$\displaystyle Z(M)M^{4\gamma-2}$ $\displaystyle\ll\sum_{n\in
Z(M)}\left|\int_{m}T(x)^{2}e(-xn)dx\right|^{2}$
$\displaystyle\ll\int_{m}|T(x)|^{4}dx,$

where Bessel’s inequality is used in the last step. It remains to show that

$M^{2-4\gamma}\int_{m}|T(x)^{4}dx\ \ll\ M^{1-\sigma+\varepsilon},$

so that it suffices to show that, with $X=M^{\gamma}$,

(3.1) $\int_{m}|T(x)|^{4}dx\ll X^{4-c-c\sigma+\varepsilon}.$

Let us assume for a moment that

(3.2) $\sum_{1\leq n\leq X}e(x[n^{c}])\ll
X^{2-c-c\sigma+\varepsilon/2}+X^{1-c}\|x\|^{-1}\quad(0<x\leq 2)$

and that

(3.3) $T(x)\ll X^{1-c\sigma/2+\varepsilon/4}\quad(\omega\leq x\leq 1-\omega).$

Lemma 6 (ii) yields

$\int_{m}|T(x)|^{4}dx\ll\mathcal{L}^{4}(X^{2-c\sigma+\varepsilon/2+2-c}+X^{2-c-c\sigma+\varepsilon/2+2}),$

so that (3.1) holds. It remains to prove (3.2), (3.3). Using a dyadic
argument, we need only show (with general $X\geq 2$) that

(3.4) $\sum_{\frac{X}{2}<n\leq X}e(x[n^{c}])\ll
X^{2-c-c\sigma+\varepsilon/2}+X^{1-c}\|x\|^{-1}\quad(0<x<2)$

and that

(3.5) $\sum_{\frac{X}{2}<n\leq X}(\log p)e(x[p^{\sigma}])\ll
X^{1-c\sigma/2+\varepsilon/4}\quad(\omega\leq x\leq 1-\omega).$

Since $c\sigma<1$, we may show in place of (3.5) that

(3.6) $\sum_{\frac{X}{2}<n\leq X}\Lambda(n)e(x[n^{\sigma}])\ll
X^{1-c\sigma/2+\varepsilon/4}.$

For (3.4), we apply Lemma 1, taking $H=X^{c-1+c\sigma}$. Let

$S_{h}=\sum_{\frac{X}{2}<n\leq X}e((h+\gamma)n^{c})\ ,\ h\geq 0,$

where $\gamma=\\{x\\}$ if $h=0$ and $\gamma\in\\{0,\\{x\\},-\\{x\\}\\}$ for
$h\geq 1$. It suffices to show that

(3.7)
$\displaystyle\sum_{h=0}^{\infty}\min\left(\frac{1}{h+1}\,,\,\frac{H}{h^{2}}\right)|S_{h}|$
$\displaystyle\ll X^{2-c-c\sigma+\varepsilon/2}+X^{1-c}\|x\|^{-1}$
$\displaystyle\hskip 36.135pt(0<x<2).$

The term $X^{1-c}\|x\|^{-1}$ on the right-hand side of (3.7) is needed only
when $h=0$ or 1 and $X^{c-1}(h+\gamma)<\varepsilon$. In this case, the Kusmin-
Landau theorem ([4, Theorem 2.1]) gives

$S_{h}\ll X^{1-c}(h+\gamma)^{-1}\ll X^{1-c}\|x\|^{-1}.$

Let

$F_{h}=(h+\gamma)X^{c}\ ,\ N_{h}=F_{h}X^{-1}.$

To bound $S_{h}$ we apply the B-process followed by Lemma 4 with $k=5$. (It is
crucial here that $\frac{c}{c-1}>4$ for the fifth derivative to have
appropriate order of magnitude.) The error term arising from the B-process is
$\ll X^{1/2}$ since $F_{h}X^{-1}\gg 1$. This gives rise to an acceptable
contribution to (3.7) since $2-c-c\sigma>1/2$. In order to obtain (3.7) it
remains to show that

$\displaystyle\sum_{h=0}^{\infty}\min\left(\frac{1}{h+1}\,,\,\frac{H}{h^{2}}\right)X^{1+\varepsilon/2}F_{h}^{-1/2}$
$\displaystyle
N_{h}((F_{h}N_{h}^{-5})^{\frac{1}{20}}+N_{h}^{-1/20}+(F_{h}N_{h}^{-5})^{-1/50}N_{h}^{-1/10})$
$\displaystyle\qquad\ll X^{2-c-c\sigma+\varepsilon/2}.$

Now

$\displaystyle X^{1+\varepsilon/2}F_{h}^{-1/2}N_{h}(F_{h}N_{h}^{-5})^{1/20}$
$\displaystyle\ll X^{1/4+\varepsilon/2}F_{h}^{3/10}$ $\displaystyle\ll
X^{1/4+3c/10+\varepsilon/2}(h+1)^{3/10},$
$\displaystyle\sum_{h=0}^{\infty}\min\left(\frac{1}{h+1}\,,\,\frac{H}{h^{2}}\right)$
$\displaystyle X^{1/4+3c/10+\varepsilon/2}(h+1)^{3/10}$ $\displaystyle\ll
H^{3/10}X^{1/4+3c/10+\varepsilon/2}$ $\displaystyle\ll
X^{\frac{3}{10}\,(c-1+c\sigma)+1/4+3c/10+\varepsilon/2}$ $\displaystyle\ll
X^{2-c-c\sigma+\varepsilon/2}$

since $\sigma\leq(41-32c)/26c$ is easily deduced from the definition of
$\sigma$.

Next,

$\displaystyle X^{1+\varepsilon/2}F_{h}^{-1/2}N_{h}^{19/20}$ $\displaystyle\ll
F_{h}^{9/20}X^{1/20+\varepsilon/2}$
$\displaystyle\ll(h+1)^{9/20}X^{(9c+1)/20+\varepsilon/2},$
$\displaystyle\sum_{h=0}^{\infty}\min\left(\frac{1}{h+1}\,,\,\frac{H}{h^{2}}\right)$
$\displaystyle(h+1)^{9/20}X^{(9c+1)/20+\varepsilon/2}$ $\displaystyle\ll
X^{\frac{9}{20}\,(c-1+c\sigma)+(9c+1)/20+\varepsilon/2}$ $\displaystyle\ll
X^{2-c-c\sigma+\varepsilon/2}$

since

$\sigma\leq\frac{48-38c}{29c}\,.$

Finally,

$\displaystyle X^{\varepsilon/2}F_{h}^{-1/2}(F_{h}N_{h}^{-5})^{-1/50}$
$\displaystyle N_{h}^{9/10}=X^{\varepsilon/2}F_{h}^{24/50}$
$\displaystyle\ll(h+1)^{12/25}X^{12c/25+\varepsilon/2},$
$\displaystyle\sum_{h=0}^{\infty}\min\left(\frac{1}{h+1}\,,\,\frac{H}{h^{2}}\right)$
$\displaystyle(h+1)^{12/25}X^{12c/25+\varepsilon/2}$ $\displaystyle\ll
X^{(c-1+c\sigma)12/25}X^{12c/25+\varepsilon/2}.$

This is

$\ll X^{2-c-c\sigma+\varepsilon/2}$

since $\sigma\leq(62-49c)/37c$ follows from the definition of $\sigma$. Thus
(3.7) holds.

In order to prove (3.6), we apply Lemma 7, taking $u=\frac{X^{1/5}}{128}$,
$z=X^{2/5}$, $v=128X^{1/3}$. Recall that $\omega\leq x\leq 1-\omega$. It
suffices to show that, for $|a_{m}|\leq 1$,

$\underset{mn\leq X}{\sum_{m}a_{m}\,\sum_{n\geq X^{2/5}}}(\log
n)^{h}e(x[(mn)^{c}])\ll X^{1-\frac{c\sigma}{2}+\frac{\varepsilon}{5}}$

and that, for $|a_{m}|\leq 1$, $|b_{n}|\leq 1$ we have

$\underset{mn\leq X}{\sum_{m}a_{m}\sum_{X^{1/5}\leq n\leq
2^{7}x^{1/3}}}b_{n}e(x([(mn)^{c}]))\ll X^{1-c\sigma/2+\varepsilon/5}.$

After applying Lemma 1 with $H=X^{c\sigma/2}$, a partial summation if needed,
and dyadic dissections we see that it suffices to show

(3.8)
$\sum_{h=0}^{\infty}\min\left(\frac{1}{h+1}\,,\,\frac{H}{h^{2}}\right)|S_{j}(h)|\ll
X^{1-\frac{c\sigma}{2}+\varepsilon/6}\quad(j=1,2).$

Here

$S_{1}(h)=\sum_{m\leq XY^{-1}}\Bigg{|}\sum_{\begin{subarray}{c}Y\leq
n<Y^{\prime}\\\ mn\leq X\end{subarray}}e((h+\gamma)(mn)^{c}\Bigg{|}$

where $Y\geq X^{2/5}$, $Y<Y^{\prime}\leq 2Y$ and

(3.9) $\gamma=x\,\text{ if }\,h=0\ ,\ \gamma\in\\{x,-x\\}\,\text{ if }\,h\geq
1.$

As for $S_{2}(h)$,

$S_{2}(h)=\sum_{Z\leq m\leq 2Z}\Bigg{|}\sum_{\begin{subarray}{c}Y<n\leq 2Y\\\
mn\leq X\end{subarray}}b_{n}e((h+\gamma)(mn)^{c})\Bigg{|}$

with $Z\leq X$ and $X^{1/5}\ll Y\ll X^{1/3}$, $ZY\ll X$.

To bound $S_{1}(h)$ we apply Lemma 2 with $\ell=2$ to the inner sum. Let
$F=(h+\gamma)X^{c}$, then

$\displaystyle F\gg xX^{c}$ $\displaystyle\gg X^{c-1/3-\varepsilon},$
$\displaystyle XY^{-1}(YF^{-1})$ $\displaystyle=XF^{-1}\ll
X^{4/3-c+\varepsilon}\ll X^{1-c\sigma}$

since $c\sigma<6/75$ from the definition of $\sigma$. This term produces a
satisfactory contribution in (3.8). Also

$\displaystyle F\ll(h+1)$ $\displaystyle X^{c},$ $\displaystyle
XY^{-1}F^{1/14}Y^{5/7}$
$\displaystyle\ll(h+1)^{1/14}X^{1+c/14-\frac{2}{7}\cdot\frac{2}{5}},$
$\displaystyle\sum_{h=0}^{\infty}\min\Bigg{(}\frac{1}{h+1}\,$
$\displaystyle,\,\frac{H}{h^{2}}\Bigg{)}|S_{1}(h)|$ $\displaystyle\ll
H^{1/14}X^{31/35+c/14}$ $\displaystyle\ll
X^{\frac{31}{35}+\frac{c}{14}+\frac{c\sigma}{28}}\ll X^{1-c\sigma/2}$

since

$\sigma\leq\frac{16-10c}{75c}\,.$

For $S_{2}(h)$, we proceed as in the proof of Theorem 5 of [1]. We have, for
$Q\leq N$,

(3.10) $|S_{2}(h)|^{2}\ll\frac{X^{2}}{Q}+\frac{X}{Q}\ \sum_{q\leq Q}\
\sum_{n\asymp Y}\Bigg{|}\sum_{m\in
I(n)}e((h+\gamma)m^{c}((n+q)^{c}-n^{c}))\Bigg{|}$

where $I(n)$ is a subinterval of $[Z,2Z]$. Take $Q=X^{c\sigma}\leq X^{6/75}$.

We estimate the inner sum in (3.10) using Lemma 2 with $\ell=1$. We have

$\displaystyle\sum_{m\in I(n)}$ $\displaystyle
e((h+\gamma)m^{c}((n+q)^{c}-n^{c}))$
$\displaystyle\quad\ll((h+1)X^{c\sigma+c}Y^{-1})^{1/6}Z^{1/2}+ZF_{h,q}^{-1}$
where $\displaystyle F_{h,q}$ $\displaystyle=(h+\gamma)X^{c}\,q\,Y^{-1}\geq
X^{c-2/3-\varepsilon}\geq X^{c\sigma}$

leading to an acceptable term arising from $ZF_{h,q}^{-1}$ in (3.8). (Of
course, $Q$ was chosen so that $X^{2}/Q$ is likewise acceptable.)

Now a short computation yields

$\displaystyle\frac{X}{Q}\ \sum_{q\leq Q}\ \sum_{n\leq Y}((h+1)$
$\displaystyle X^{c\sigma+c}Y^{-1})^{1/6}Z^{1/2}$
$\displaystyle\ll(h+1)^{1/6}X^{29/18+(c\sigma+c)/6}$

(since $Y\ll X^{1/3}$). The contribution to (3.8) is

$\displaystyle\ll\sum_{h=0}^{\infty}$
$\displaystyle\min\left(\frac{1}{h+1}\,,\,\frac{H}{h^{2}}\right)(h+1)^{1/12}X^{29/36+(c\sigma+c)/12}$
$\displaystyle\hskip 36.135pt\ll X^{29/36+(3c\sigma+2c)/24}\ll
X^{1-c\sigma/2}$

since $\sigma\leq\frac{14-6c}{45c}$ from the definition of $\sigma$. This
shows that (3.8) holds, and the proof of Theorem 1 is complete. $\hfill\Box$

## References

  * [1] R. C. Baker, Sums of two relatively prime cubes, Acta Arith. 129 (2007), 103–149.
  * [2] R. C. Baker, Some Diophantine equations and inequalities with primes. Funct. Approx. Comment. Math. 64 (2021), 203–250.
  * [3] Y. C. Cai, A ternary Diophantine inequality involving primes, Int. J. Number Theory 14 (2018), 2257–2268.
  * [4] S. W. Graham and G. Kolesnik, Van der Corput’s Method of Exponential Sums, Cambridge University Press, Cambridge 1991.
  * [5] D. R. Heath-Brown, Prime numbers in short intervals and a generalized Vaughan identity, Can. J. Math. 34 (1982), 1365–1377.
  * [6] D. R. Heath-Brown, A new $k$-th derivative estimate for a trigonometric sum via Vinogradov’s integral, Proc. Steklov Inst. Math. 296 (2017), 88–103.
  * [7] M. B. S. Laporta, On a binary problem with prime numbers, Math. Balkanica (N.S.) 13 (1999), 119–123.
  * [8] W. B. Zhu, Representation of integers as sums of fractional powers of primes and powers of 2, Acta Arith. 181 (2017), 185–196, erratum, ibid., 197–199.


# Enhanced sensitivity of an all-dielectric refractive index sensor with
optical bound state in the continuum

Dmitrii N. Maksimov1,2, Valery S. Gerasimov1,3, Andrey A. Bogdanov4, Sergey P.
Polyutov1 1International Research Center of Spectroscopy and Quantum
Chemistry, Siberian Federal University, 660041, Krasnoyarsk, Russia  2Kirensky
Institute of Physics, Federal Research Center KSC SB RAS, 660036, Krasnoyarsk,
Russia  3Institute of Computational Modeling SB RAS, Krasnoyarsk, 660036,
Russia  4Department of Physics and Engineering, ITMO University, 191002, St.
Petersburg, Russia

###### Abstract

The sensitivity of a refractive index sensor based on an optical bound state
in the continuum is considered. Applying Zel’dovich perturbation theory we
derived an analytic expression for bulk sensitivity of an all-dielectic sensor
utilizing symmetry protected in-$\Gamma$ optical bound states in a dielectric
grating. The upper sensitivity limit is obtained. A recipe is proposed for
obtaining the upper sensitivity limit by optimizing the design of the grating.
The results are confirmed through direct numerical simulations.

## Introduction

Recently, we have witnessed a surge of interest to bound states in the
continuum (BICs) Hsu  _et al._ (2016); Koshelev  _et al._ (2019a); Sadreev
(2021) that have revolutionized nanophotonics by paving a way to high
throughput optical sensing devices with enhanced light-matter interaction at
the nanoscale Molina  _et al._ (2012); Romano  _et al._ (2018a); Bulgakov and
Sadreev (2008); Penzo  _et al._ (2017); Zhen  _et al._ (2014); Mocella and
Romano (2015); Koshelev  _et al._ (2019b); Zito  _et al._ (2019). The most
remarkable feature of BICs is the occurrence of high-quality Fano resonances
in the transmittance spectrum Shipman and Venakides (2005); Sadreev  _et al._
(2006); Blanchard  _et al._ (2016); Bulgakov and Maksimov (2018a). The Fano
resonances emerge when the system’s symmetry is broken, so the otherwise
localized BIC mode can couple with impinging light Koshelev  _et al._ (2018);
Maksimov  _et al._ (2020). The spectral position of these extremely narrow
Fano resonances is affected by the refractive index of the surrounding medium
allowing to design optical sensors with an excellent figure of merit (FOM) Liu
_et al._ (2017); Romano  _et al._ (2018b, c); Yesilkoy  _et al._ (2019);
Mukherjee  _et al._ (2019); Vyas and Hegde (2020) as the narrow Fano feature
can be easily resolved in the spectral measurements. Despite the unsurpassed
FOM, the major drawback of the dielectric sensors in comparison against the
plasmonic ones is a noticeably (approximately five times) less sensitivity
Bosio  _et al._ (2019). Nowadays, comparative analysis of dielectric sensors
performance is already available in the existing literature Pitruzzello and
Krauss (2018); Wang  _et al._ (2021). Yet, to the best of our knowledge, there
is no exhaustive theory providing a clear optimization procedure that would
lead to the maximal sensitivity of a BIC sensor. In our previous paper
Maksimov  _et al._ (2020) we argued that the maximal sensitivity of a BIC
sensor is given by $S_{\mathrm{max}}=\lambda_{\mathrm{BIC}}/n_{c}$, where
$\lambda_{\mathrm{BIC}}$ is the vacuum wavelength of the BIC, and $n_{c}$ is
the the cladding fluid refractive index, i.e. the physical quantity whose
variation is measured by the sensor. In this paper we provide a rout for
achieving the above limit by considering an optical BICs whose spectral
position approach the frequency cut-offs of the first order diffraction
channels. An analytic expression for a BIC vacuum wavelength shift is derived
by applying the Zel’dovich perturbation theory Zel’dovich (1961). The primary
advantage of the Zel’dovich approach is that it can be applied to optical
delocalized eigenmodesLai  _et al._ (1990) to have already been proved useful
in theory of plasmonic sensors Zalyubovskiy  _et al._ (2012). The onset of
diffraction usually has a negative impact on high-Q resonances, particularly
on BICs which are typically destroyed by the radiation losses Sadrieva  _et
al._ (2017). However, in the situation when the first order diffraction cut-
off frequency is not yet exceeded the evanescent field are demonstrated to
provide the largest overlap with the cladding fluid leading to enhanced
sensitivity Romano  _et al._ (2019).

## The system

One of the most important platforms for implementing optical BICs is
subwavelength dielectric gratings Marinica  _et al._ (2008); Sadrieva  _et
al._ (2017); Monticone and Alù (2017); Bulgakov  _et al._ (2018); Bulgakov and
Maksimov (2018b); Lee and Magnusson (2019); Bykov  _et al._ (2019); Gao  _et
al._ (2019); Hemmati and Magnusson (2019) which have been extensively studied
for sensing applications with both dielectric Maksimov  _et al._ (2020); Zhang
_et al._ (2021); Finco  _et al._ (2021); Park and Park (2021); Mesli  _et al._
(2021) and plasmonic structures Jia  _et al._ (2021). The system under
consideration is a subwavelength dielectric grating of period $h=300{\rm nm}$
made of ${\rm TiO}_{2}$. In our numerical simulations we use $n_{g}=2.485$ as
the refractive index of the grating while the material losses are ignored so
the absorption coefficient is set to zero. The ${\rm TiO}_{2}$ grating is
placed on top of a glass substrate with refractive index $n_{s}=1.5$ as shown
in Fig. 1 (a). The geometric parameters of the grating are specified in the
caption to Fig. 1.

Figure 1: BIC in dielectric grating. (a) ${\rm TiO}_{2}$ dielectric grating on
a glass substrate, $h=300nm$, $b=0.5h$, $w=0.5h$, $n_{g}=2.485$, and
$n_{s}=1.5$. The magenta arrow is the electric vector of an incident $s$-wave;
(b) Number of scattering channels allowed for diffraction. The red star
indicates the position of a symmetry protected BIC with $k_{{\rm BIC}}=3.262$,
$n_{c}=1.7$. The BIC mode profile is depicted below its spectral position in
procedure defined units with red areas corresponding to positive $E_{x}$
whereas in the blue areas $E_{x}$ is negative.

Propagation of TE modes is controlled by the Helmholtz equation

$\nabla^{2}E_{x}(y,z)+k^{2}\epsilon(y,z)E_{x}(y,z)=0,$ (1)

where $E_{x}$ is the $x$-component of the electric field, $\epsilon=f(y,z)$ —
the coordinate dependant dielectric function, $\nabla^{2}$ — the 2D Laplacian
operator, and $k=\omega/c$ is the vacuum wave-number. The spectrum of far-
field diffraction channels available for scattering is given by

$n_{c}k^{2}=\left(\beta+\frac{2\pi m}{h}\right)^{2}+k_{z}^{2},\
m=-\infty,\ldots,-1,0,1,\ldots,\infty,$ (2)

where $k_{z}$ is the $z$ component of the outgoing wave vector, $\beta$ is the
propagation constant with respect to the $y$-axis, and $n_{c}$ is the
refractive index of the cladding fluid. All simulation results referenced
throughout the paper have been obtained with application of FDTD Lumerical
photonics simulation software solution.

Following our previous work Maksimov  _et al._ (2020) we consider a symmetry
protected in-$\Gamma$ BIC which does not radiate to the far field because it
is symmetrically mismatched with the zeroth-order diffraction channel at
strict normal incidence. In engineering a symmetry protected BIC it is of key
importance to ensure that the higher diffraction orders are not allowed at the
BIC wavelength. Once diffraction is allowed either in the substrate or in the
superstrate (cladding fluid) the BIC is destroyed being transformed into a
leaky mode radiating into the diffraction channels Sadrieva  _et al._ (2017).
The onset of diffraction is typically detected by occurrence of Wood-Rayleigh
anomaly in the scattering spectra Wood (1902); Rayleigh (1907). The positions
of Wood’s anomalies are given by the following equations

$\displaystyle n_{c}k=|\beta|,$ $\displaystyle n_{c}k=\beta+\frac{2\pi m}{h}\
\mathrm{if}\ m>0,$ $\displaystyle n_{c}k=-\beta-\frac{2\pi m}{h}\ \mathrm{if}\
m<0.$ (3)

In Fig. 1 (b) we demonstrate the number of diffraction channels $N$ allowed in
the cladding depending on the spectral parameters of the incident wave, namely
its vacuum wavelength, $k$ and the propagation constant in the $y$-direction,
$\beta$. Each colored domain in Fig. 1 (b) corresponds to the specified value
of $N$. Wood’s anomalies occur when the boundaries between the domains with
$N>1$ are crossed under variation of the spectral parameters of the incident
wave. The symmetry protected BICs can be found in the domain of specular
reflection $N=1$. The spectral position of such a BIC with $n_{c}=1.7$ is
shown in 1 (b) by a red plus sign. The BIC mode profile is set in the middle.
It is important for our future purpose to point out that the BIC mode profile
has the following asymptotic far-field expression

$E_{x}\propto e^{-\varkappa z}\sin\left(\frac{2\pi y}{h}\right),$ (4)

where

$\varkappa=\sqrt{\left(\frac{2\pi}{h}\right)^{2}-\epsilon^{\scriptscriptstyle{(0)}}_{\infty}k^{2}}$
(5)

with $\epsilon^{\scriptscriptstyle{(0)}}_{\infty}=n_{c}^{2}$ and $y=0$
corresponding to the geometric center of the unit cell. Notice that in
Equation (4) we only retained the contribution of the first order evanescent
diffraction channels, since the higher order channels decay much faster with
the increase of $z$.

## Perturbation theory

The Zel’dovich Zel’dovich (1961) perturbation approach is introduced by
writing a series expansion in the increment of the dielectric function
$\Delta\epsilon$

$\displaystyle\epsilon=\epsilon^{\scriptscriptstyle{(0)}}+\Delta\epsilon,$
$\displaystyle k=k^{\scriptscriptstyle{(0)}}+\Delta k,$ $\displaystyle
E_{x}=E_{x}^{\scriptscriptstyle{(0)}}+E_{x}^{\scriptscriptstyle{(1)}}.$ (6)

By definition the function $\epsilon^{\scriptscriptstyle{(0)}}$ is the total
coordinate dependent dielectric function with the reference value of the
cladding fluid refractive index, whereas $\Delta\epsilon$ is the increment of
the dielectric constant of the cladding fluid. Substituting the above into
Equation (1) we have up to the first perturbation order

$\displaystyle\nabla^{2}E_{x}^{\scriptscriptstyle{(0)}}+\epsilon^{\scriptscriptstyle{(0)}}(k^{\scriptscriptstyle{(0)}})^{2}E_{x}^{\scriptscriptstyle{(0)}}=0,$
(7)
$\displaystyle\nabla^{2}E_{x}^{\scriptscriptstyle{(1)}}+\epsilon^{\scriptscriptstyle{(0)}}(k^{\scriptscriptstyle{(0)}})^{2}E_{x}^{\scriptscriptstyle{(1)}}=-\Delta\epsilon(k^{\scriptscriptstyle{(0)}})^{2}E_{x}^{\scriptscriptstyle{(0)}}-2\epsilon^{\scriptscriptstyle{(0)}}\Delta
kk^{\scriptscriptstyle{(0)}}E_{x}^{\scriptscriptstyle{(0)}}.$ (8)

Following Zel’dovich we multiply Equation (8) by
$E_{x}^{\scriptscriptstyle{(0)}}$ and integrate within the limits specified
below

$\int\limits_{-{h}/{2}}^{{h}/{2}}dy\int\limits_{-d}^{d}dzE_{x}^{\scriptscriptstyle{(0)}}[\nabla^{2}E_{x}^{\scriptscriptstyle{(1)}}+\epsilon^{\scriptscriptstyle{(0)}}(k^{\scriptscriptstyle{(0)}})^{2}E_{x}^{\scriptscriptstyle{(1)}}]=-\int\limits_{-{h}/{2}}^{{h}/{2}}dy\int\limits_{-d}^{d}dz[\Delta\epsilon(k^{\scriptscriptstyle{(0)}})^{2}+2\epsilon^{\scriptscriptstyle{(0)}}\Delta
kk^{\scriptscriptstyle{(0)}}](E_{x}^{\scriptscriptstyle{(0)}})^{2},$ (9)

where $d>b$ is an arbitrary distance from the grating. By applying Green’s
theorem together with Equation (7) one rewrites the L.H.P. of Equation (9) in
the following manner

$\int\limits_{-{h}/{2}}^{{h}/{2}}dy\int\limits_{-d}^{d}dzE_{x}^{\scriptscriptstyle{(0)}}[\nabla^{2}E_{x}^{\scriptscriptstyle{(1)}}+\epsilon^{\scriptscriptstyle{(0)}}(k^{\scriptscriptstyle{(0)}})^{2}E_{x}^{\scriptscriptstyle{(1)}}]=\int\limits_{\ell}d\ell\left(E_{x}^{\scriptscriptstyle{(0)}}\frac{\partial
E_{x}^{\scriptscriptstyle{(1)}}}{\partial
n}-E_{x}^{\scriptscriptstyle{(1)}}\frac{\partial
E_{x}^{\scriptscriptstyle{(0)}}}{\partial n}\right),$ (10)

where $\ell$ is a path encircling the integration domain of the L.H.P. in the
clockwise direction. The integrals along the lines $y=-h/2$ and $y=h/2$ cancel
each other due to periodicity while the integral along $z=-d$ can be neglected
as we assume that the BIC field decays faster in the substrate because of a
lesser refractive index. This leads us to

$\int\limits_{-{h}/{2}}^{{h}/{2}}dy\int\limits_{-d}^{d}dzE_{x}^{\scriptscriptstyle{(0)}}[\nabla^{2}E_{x}^{\scriptscriptstyle{(1)}}+\epsilon^{\scriptscriptstyle{(0)}}(k^{\scriptscriptstyle{(0)}})^{2}E_{x}^{\scriptscriptstyle{(1)}}]=\int\limits_{-h/2}^{h/2}dy\left(E_{x}^{\scriptscriptstyle{(0)}}(y,d)\frac{\partial
E_{x}^{\scriptscriptstyle{(1)}}(y,d)}{\partial
z}-E_{x}^{\scriptscriptstyle{(1)}}(y,d)\frac{\partial
E_{x}^{\scriptscriptstyle{(0)}}(y,d)}{\partial z}\right).$ (11)

Equating the R.H.P. of Equation (11) to that of Equation (9) and inserting the
following asymptotic expressions

$\displaystyle\frac{\partial E_{x}^{\scriptscriptstyle{(0)}}}{\partial
z}=-\varkappa^{\scriptscriptstyle{(0)}}E_{x}^{\scriptscriptstyle{(0)}},$
$\displaystyle\frac{\partial E_{x}^{\scriptscriptstyle{(1)}}}{\partial
z}=\frac{1}{2\varkappa^{\scriptscriptstyle{(0)}}}[\Delta\epsilon(k^{\scriptscriptstyle{(0)}})^{2}+2\epsilon^{\scriptscriptstyle{(0)}}_{\infty}k^{\scriptscriptstyle{(0)}}\Delta
k]E_{x}^{\scriptscriptstyle{(0)}}-\varkappa^{\scriptscriptstyle{(0)}}E_{x}^{\scriptscriptstyle{(1)}},$
(12)

one has

$\frac{\Delta k}{\Delta\epsilon}=-\frac{k^{\scriptscriptstyle{(0)}}}{2}I,$
(13)

where

$I=\frac{\displaystyle\int\limits_{S_{\rm
c}}dS\left(E_{x}^{\scriptscriptstyle{(0)}}\right)^{2}+\frac{1}{2\varkappa^{\scriptscriptstyle{(0)}}}\displaystyle\int\limits_{-h/2}^{h/2}dy\left[E_{x}^{\scriptscriptstyle{(0)}}(y,d)\right]^{2}}{\displaystyle\int\limits_{S_{\rm
tot}}dS\epsilon^{\scriptscriptstyle{(0)}}\left(E_{x}^{\scriptscriptstyle{(0)}}\right)^{2}+\frac{\epsilon^{\scriptscriptstyle{(0)}}_{\infty}}{2\varkappa^{\scriptscriptstyle{(0)}}}\int\limits_{-h/2}^{h/2}dy\left[E_{x}^{\scriptscriptstyle{(0)}}(y,d)\right]^{2}}.$
(14)

Thus, for the differential sensitivity
$S=\Delta\lambda_{\scriptscriptstyle{\mathrm{BIC}}}/\Delta n_{c}$ we have

$S=\lambda n_{c}I.$ (15)

On approach to the cut-off of the first order diffraction channels
$\varkappa\rightarrow 0$ we have

$S=\frac{\lambda_{\scriptscriptstyle{\mathrm{BIC}}}}{n_{c}}$ (16)

which coincides with the upper sensitivity limit predicted in Maksimov  _et
al._ (2020). Before proceeding to numerical validation of the newfound results
some comments are due on the choice of $d$. It is obvious that $d$ should be
taken large enough to guarantee that the far-field asymptotic behaviour be
given by Equation (4). In the domain of specular reflection at the normal
incidence the evanescent fields of the second order diffraction channels decay
faster than $e^{-2\pi z/h}$. Therefore, for a practical choice it is
sufficient to take $d>\lambda_{\scriptscriptstyle{\rm BIC}}$. At the save
time, from the computation viewpoint the choice of $d$ determines the size of
the computational domain. Technically, $d$ is the distance at which the PML
absorbers are placed to set-up reflectionless boundary conditions. Thus,
application of Equations (14, 15) allows us to predict the sensitivity of BICs
with the evanescent fields extended beyond the computational domain.

## Numerical validation

Figure 2: Fano resonance shift and differential sensitivity. (a) The vacuum
wavelength of the symmetry protected BIC as a function of the cladding fluid
refractive index. (b) Differential sensitivity obtained from Equation (15) —
green circles, and through the shift of the Fano resonance — blue dots at
$\theta=2(\mathrm{deg})$. (c) Shift of the Fano resonance obtained at
$\theta=2(\mathrm{deg})$, $n_{c}=2.0$ with $\Delta n=0.01$.

In Fig. 2 (a) we plotted the vacuum wavelength of the symmetry protected BIC
at different values of $n_{c}$. One can see from Fig. 2 (a) that
$\lambda_{\mathrm{\scriptscriptstyle{BIC}}}$ decreases with the increase of
$n_{c}$ especially at larger values of $n_{c}$. In Fig. 2 (b) we plotted the
values of differential sensitivity obtained by two different methods. The
"theoretical" result is obtained by directly applying Equation (15) meanwhile
the "numerical" values are obtained finding the shift of a BIC-induced Fano
resonance under illumination by a plane wave at the incidence angle
$\theta=2(\mathrm{deg})$. To keep the approach consistent while changing
$n_{c}$, the incidence angle $\theta$ is defined in reference to the wave
vectors in the outer space (air), so the incident angle within the cladding
fluid $\theta_{c}$ is found through the formula

$n_{c}\sin(\theta_{c})=\sin(\theta).$ (17)

The typical picture of the shift in the resonance position is shown in Fig. 2
(c). In Fig. 2 (b) we also plotted the maximal value of the sensitivity
according to Equation (16). One can see from Fig. 2 (b) that with the increase
of $n_{c}$ the sensitivity approach the upper limit given by Equation (16).
Notice that at larger $n_{c}$ the numerically observed sensitivity deviates
from the theoretical expressions (14, 15). This is because the first order
frequency cut-offs are lower at $\theta\neq 0$ according to Equation (The
system), see also Fig. 2 (b). In our case the onset of diffraction at
$n_{c}=2.21$ destroys the high-Q resonance with the chosen angle of incidence
$\theta=2\mathrm{(deg)}$ although the BIC proper is not yet destroyed.
Finally, notice that the observed sensitivity enhancement can be easily
understood from Fig. 2 (a) which is complemented with subplots of two BIC mode
profiles. One can see that at larger $n_{c}$ the BIC fields are further
extended into the upper half-space providing a better overlap with the
cladding fluid.

## Conclusion

In this paper we have demonstrated an approach allowing to achieve the upper
sensitivity limit for an all-dielectric sensor based on an optical bound state
in the continuum (BIC). The analytic expressions for computing the bulk
sensitivity from the BIC vacuum wavelength and mode profile have been derived
as Equations (14, 15). The most remarkable feature of the obtained expressions
is that the maximal sensitivity is independent of the material and geometric
parameters of the grating allowing for freedom in choosing of the constituent
dielectric. All that is necessary for achieving the maximal sensitivity is to
vary the geometric parameters for the BIC eigenfrequency approaching the cut-
offs of the first order diffraction channels. The BICs are topologically
protected objects Zhen  _et al._ (2014); Bulgakov and Maksimov (2017a, b) and
therefore are bit destroyed under variation of geometric parameters complying
with the structure point group symmetry as far as the BIC eigenfrequency
remains in the spectral domain of the specular reflection Bulgakov  _et al._
(2018). In the regime of maximal sensitivity the vacuum wavelength of the
in-$\Gamma$ BIC is always given by

$\lambda_{\scriptscriptstyle{\mathrm{BIC}}}=n_{c}h,$ (18)

while the maximal sensitivity is simply
$S_{\scriptscriptstyle{\mathrm{max}}}=\lambda_{\scriptscriptstyle{\mathrm{BIC}}}/n_{c}$.
Notice that due to the scaling invariance of Maxwell’s equations,
$\lambda_{\scriptscriptstyle{\mathrm{BIC}}}$ can be tuned to any desired
wavelength by isometric transformation of the grating.

In the numerical example proposed the maximal sensitivity has been achieved
with a relatively large value of the cladding fluid refractive index
$n_{c}=2.21$. This, of course, out of the range required in practical
applications which are stuck around the refractive index of water.
Importantly, achieving the maximal sensitivity requires the refractive index
of the cladding larger than that of substrate. If the situation is the
opposite, the first order diffraction channels will first open in the
substrate Sadrieva  _et al._ (2017) destroying the BIC before the maximal
overlap with the cladding has been achieved. There are two possible solutions
to this problem. The first is, obviously, applying a low index substrate
Schubert  _et al._ (2007). The second is using a substrate of a properly
chosen Bragg reflector Bikbaev  _et al._ (2021) which would isolate the lower
half-space by a photonic band gap for the outgoing waves of the first order of
diffraction. This problem will be addressed in the future studies.

## References

  * Hsu  _et al._ (2016) Chia Wei Hsu, Bo Zhen, A. Douglas Stone, John D. Joannopoulos, and Marin Soljačić, “Bound states in the continuum,” Nature Reviews Materials 1, 16048 (2016).
  * Koshelev  _et al._ (2019a) Kirill Koshelev, Gael Favraud, Andrey Bogdanov, Yuri Kivshar, and Andrea Fratalocchi, “Nonradiating photonics with resonant dielectric nanostructures,” Nanophotonics 8, 725–745 (2019a).
  * Sadreev (2021) Almas F Sadreev, “Interference traps waves in open system: Bound states in the continuum,” Reports on Progress in Physics (2021).
  * Molina  _et al._ (2012) Mario I Molina, Andrey E Miroshnichenko, and Yuri S Kivshar, “Surface bound states in the continuum,” Physical review letters 108, 070401 (2012).
  * Romano  _et al._ (2018a) Silvia Romano, Gianluigi Zito, Stefano Managò, Giuseppe Calafiore, Erika Penzo, Stefano Cabrini, Anna Chiara De Luca, and Vito Mocella, “Surface-enhanced raman and fluorescence spectroscopy with an all-dielectric metasurface,” The Journal of Physical Chemistry C 122, 19738–19745 (2018a).
  * Bulgakov and Sadreev (2008) Evgeny N Bulgakov and Almas F Sadreev, “Bound states in the continuum in photonic waveguides inspired by defects,” Physical Review B 78, 075105 (2008).
  * Penzo  _et al._ (2017) Erika Penzo, Silvia Romano, Yu Wang, Scott Dhuey, Luca Dal Negro, Vito Mocella, and Stefano Cabrini, “Patterning of electrically tunable light-emitting photonic structures demonstrating bound states in the continuum,” J. Vac. Sc.& Tech. B 35, 06G401 (2017).
  * Zhen  _et al._ (2014) Bo Zhen, Chia Wei Hsu, Ling Lu, A. Douglas Stone, and Marin Soljačić, “Topological nature of optical bound states in the continuum,” Physical Review Letters 113, 257401 (2014).
  * Mocella and Romano (2015) V. Mocella and S. Romano, “Giant field enhancement in photonic resonant lattices,” Physical Review B 92, 155117 (2015).
  * Koshelev  _et al._ (2019b) Kirill Koshelev, Andrey Bogdanov, and Yuri Kivshar, “Meta-optics and bound states in the continuum,” Science Bulletin 64, 836–842 (2019b).
  * Zito  _et al._ (2019) Gianluigi Zito, Silvia Romano, Stefano Cabrini, Giuseppe Calafiore, Anna Chiara De Luca, Erika Penzo, and Vito Mocella, “Observation of spin-polarized directive coupling of light at bound states in the continuum,” Optica 6, 1305–1312 (2019).
  * Shipman and Venakides (2005) Stephen P Shipman and Stephanos Venakides, “Resonant transmission near nonrobust periodic slab modes,” Physical Review E 71, 026611 (2005).
  * Sadreev  _et al._ (2006) Almas F Sadreev, Evgeny N Bulgakov, and Ingrid Rotter, “Bound states in the continuum in open quantum billiards with a variable shape,” Physical Review B 73, 235342 (2006).
  * Blanchard  _et al._ (2016) Cédric Blanchard, Jean-Paul Hugonin, and Christophe Sauvan, “Fano resonances in photonic crystal slabs near optical bound states in the continuum,” Physical Review B 94, 155303 (2016).
  * Bulgakov and Maksimov (2018a) E. N. Bulgakov and D. N. Maksimov, “Optical response induced by bound states in the continuum in arrays of dielectric spheres,” Journal of the Optical Society of America B 35, 2443 (2018a).
  * Koshelev  _et al._ (2018) Kirill Koshelev, Sergey Lepeshov, Mingkai Liu, Andrey Bogdanov, and Yuri Kivshar, “Asymmetric metasurfaces with high-q resonances governed by bound states in the continuum,” Physical review letters 121, 193903 (2018).
  * Maksimov  _et al._ (2020) Dmitrii N. Maksimov, Valeriy S. Gerasimov, Silvia Romano, and Sergey P. Polyutov, “Refractive index sensing with optical bound states in the continuum,” Optics Express 28, 38907 (2020).
  * Liu  _et al._ (2017) Yonghao Liu, Weidong Zhou, and Yuze Sun, “Optical refractive index sensing based on high-Q bound states in the continuum in free-space coupled photonic crystal slabs,” Sensors 17, 1861 (2017).
  * Romano  _et al._ (2018b) Silvia Romano, Gianluigi Zito, Stefania Torino, Giuseppe Calafiore, Erika Penzo, Giuseppe Coppola, Stefano Cabrini, Ivo Rendina, and Vito Mocella, “Label-free sensing of ultralow-weight molecules with all-dielectric metasurfaces supporting bound states in the continuum,” Photonics Research 6, 726 (2018b).
  * Romano  _et al._ (2018c) Silvia Romano, Annalisa Lamberti, Mariorosario Masullo, Erika Penzo, Stefano Cabrini, Ivo Rendina, and Vito Mocella, “Optical biosensors based on photonic crystals supporting bound states in the continuum,” Materials 11, 526 (2018c).
  * Yesilkoy  _et al._ (2019) Filiz Yesilkoy, Eduardo R. Arvelo, Yasaman Jahani, Mingkai Liu, Andreas Tittl, Volkan Cevher, Yuri Kivshar, and Hatice Altug, “Ultrasensitive hyperspectral imaging and biodetection enabled by dielectric metasurfaces,” Nature Photonics 13, 390–396 (2019).
  * Mukherjee  _et al._ (2019) Samyobrata Mukherjee, Jordi Gomis-Bresco, Pilar Pujol-Closa, David Artigas, and Lluis Torner, “Angular control of anisotropy-induced bound states in the continuum,” Optics Letters 44, 5362 (2019).
  * Vyas and Hegde (2020) Hardik Vyas and Ravi S. Hegde, “Improved refractive-index sensing performance in medium contrast gratings by asymmetry engineering,” Optical Materials Express 10, 1616 (2020).
  * Bosio  _et al._ (2019) Noemi Bosio, Hana Šípová-Jungová, Nils Odebo Länk, Tomasz J. Antosiewicz, Ruggero Verre, and Mikael Käll, “Plasmonic versus all-dielectric nanoantennas for refractometric sensing: A direct comparison,” ACS Photonics 6, 1556–1564 (2019).
  * Pitruzzello and Krauss (2018) Giampaolo Pitruzzello and Thomas F Krauss, “Photonic crystal resonances for sensing and imaging,” Journal of Optics 20, 073004 (2018).
  * Wang  _et al._ (2021) Jie Wang, Jinzhe Yang, Hongwei Zhao, and Min Chen, “Quasi-BIC-governed light absorption of monolayer transition-metal dichalcogenide-based absorber and its sensing performance,” Journal of Physics D: Applied Physics 54, 485106 (2021).
  * Zel’dovich (1961) Ya B Zel’dovich, “On the theory of unstable states,” Sov. Phys. JETP 12, 542–548 (1961).
  * Lai  _et al._ (1990) H. M. Lai, P. T. Leung, K. Young, P. W. Barber, and S. C. Hill, “Time-independent perturbation for leaking electromagnetic modes in open systems with application to resonances in microdroplets,” Physical Review A 41, 5187–5198 (1990).
  * Zalyubovskiy  _et al._ (2012) Sergiy J. Zalyubovskiy, Maria Bogdanova, Alexei Deinega, Yurii Lozovik, Andrew D. Pris, Kwang Hyup An, W. Paige Hall, and Radislav A. Potyrailo, “Theoretical limit of localized surface plasmon resonance sensitivity to local refractive index change and its comparison to conventional surface plasmon resonance sensor,” Journal of the Optical Society of America A 29, 994 (2012).
  * Sadrieva  _et al._ (2017) Zarina F. Sadrieva, Ivan S. Sinev, Kirill L. Koshelev, Anton Samusev, Ivan V. Iorsh, Osamu Takayama, Radu Malureanu, Andrey A. Bogdanov, and Andrei V. Lavrinenko, “Transition from optical bound states in the continuum to leaky resonances: Role of substrate and roughness,” ACS Photonics 4, 723–727 (2017).
  * Romano  _et al._ (2019) Silvia Romano, Gianluigi Zito, Sofía N. Lara Yépez, Stefano Cabrini, Erika Penzo, Giuseppe Coppola, Ivo Rendina, and Vito Mocellaa, “Tuning the exponential sensitivity of a bound-state-in-continuum optical sensor,” Optics Express 27, 18776 (2019).
  * Marinica  _et al._ (2008) D. C. Marinica, A. G. Borisov, and S. V. Shabanov, “Bound states in the continuum in photonics,” Physical Review Letters 100, 183902 (2008).
  * Monticone and Alù (2017) Francesco Monticone and Andrea Alù, “Bound states within the radiation continuum in diffraction gratings and the role of leaky modes,” New Journal of Physics 19, 093011 (2017).
  * Bulgakov  _et al._ (2018) E. N. Bulgakov, D. N. Maksimov, P. N. Semina, and S. A. Skorobogatov, “Propagating bound states in the continuum in dielectric gratings,” Journal of the Optical Society of America B 35, 1218–1222 (2018).
  * Bulgakov and Maksimov (2018b) Evgeny N. Bulgakov and Dmitrii N. Maksimov, “Avoided crossings and bound states in the continuum in low-contrast dielectric gratings,” Physical Review A 98, 053840 (2018b).
  * Lee and Magnusson (2019) Sun-Goo Lee and Robert Magnusson, “Band dynamics of leaky-mode photonic lattices,” Optics Express 27, 18180 (2019).
  * Bykov  _et al._ (2019) Dmitry A. Bykov, Evgeni A. Bezus, and Leonid L. Doskolovich, “Coupled-wave formalism for bound states in the continuum in guided-mode resonant gratings,” Physical Review A 99, 063805 (2019).
  * Gao  _et al._ (2019) Xingwei Gao, Bo Zhen, Marin Soljačić, Hongsheng Chen, and Chia Wei Hsu, “Bound states in the continuum in fiber bragg gratings,” ACS Photonics 6, 2996–3002 (2019).
  * Hemmati and Magnusson (2019) Hafez Hemmati and Robert Magnusson, “Resonant dual-grating metamembranes supporting spectrally narrow bound states in the continuum,” Advanced Optical Materials 7, 1900754 (2019).
  * Zhang  _et al._ (2021) Haoran Zhang, Tao Wang, Jiacheng Sun, Shaoxian Li, Israel De Leon, Remo Proietti Zaccaria, Liang Peng, Fei Gao, Xiao Lin, Hongsheng Chen, _et al._ , “High-contrast grating resonator supported quasi-bic lasing and gas sensing,” arXiv preprint arXiv:2105.08885 (2021).
  * Finco  _et al._ (2021) Giovanni Finco, Mehri Ziaee Bideskan, Larissa Vertchenko, Leonid Y. Beliaev, Radu Malureanu, Lars René Lindvold, Osamu Takayama, Peter E. Andersen, and Andrei V. Lavrinenko, “Guided-mode resonance on pedestal and half-buried high-contrast gratings for biosensing applications,” Nanophotonics 0 (2021), 10.1515/nanoph-2021-0347.
  * Park and Park (2021) Gyeong Cheol Park and Kwangwook Park, “Critically coupled Fabry-Perot cavity with high signal contrast for refractive index sensing,” Scientific reports 11 (2021), 10.1038/s41598-021-98654-w.
  * Mesli  _et al._ (2021) Sabrina Mesli, Hakim Yala, Mahdi Hamidi, Abderrahmane BelKhir, and Fadi Issam Baida, “High performance for refractive index sensors via symmetry-protected guided mode resonance,” Optics Express 29, 21199 (2021).
  * Jia  _et al._ (2021) Shangtong Jia, Zhi Li, and Jianjun Chen, “High-sensitivity plasmonic sensor by narrowing fano resonances in a tilted metallic nano-groove array,” Optics Express 29, 21358 (2021).
  * Wood (1902) R W Wood, “On a Remarkable Case of Uneven Distribution of Light in a Diffraction Grating Spectrum,” Proceedings of the Physical Society of London 18, 269–275 (1902).
  * Rayleigh (1907) L. Rayleigh, “On the Dynamical Theory of Gratings,” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 79, 399–416 (1907).
  * Bulgakov and Maksimov (2017a) Evgeny N. Bulgakov and Dmitrii N. Maksimov, “Topological bound states in the continuum in arrays of dielectric spheres,” Physical Review Letters 118, 267401 (2017a).
  * Bulgakov and Maksimov (2017b) Evgeny N. Bulgakov and Dmitrii N. Maksimov, “Bound states in the continuum and polarization singularities in periodic arrays of dielectric rods,” Physical Review A 96, 063833 (2017b).
  * Schubert  _et al._ (2007) E. F. Schubert, J. K. Kim, and J.-Q. Xi, “Low-refractive-index materials: A new class of optical thin-film materials,” Physica Status Solidi (b) 244, 3002–3008 (2007).
  * Bikbaev  _et al._ (2021) Rashid G. Bikbaev, Dmitrii N. Maksimov, Pavel S. Pankin, Kuo-Ping Chen, and Ivan V. Timofeev, “Critical coupling vortex with grating-induced high q-factor optical tamm states,” Optics Express 29, 4672 (2021).

## Author contributions statement

D.N.M. and A.A.B conceived the idea presented. D.N.M. derived the analytic
results. V.S.G. ran numerical simulations. S.P.P. supervised the project. All
authors have equally contributed to writing the paper.

## Additional information

Competing interests: The authors declare no competing interests.

Data availability: The data that support the findings of this study are
available from the corresponding author, D.N.M., upon reasonable request.


Given a partition of a graph into connected components, the membership oracle asserts whether any two vertices of the graph lie in the same component or not.
We prove that for $n\ge k\ge 2$, learning the components of an $n$-vertex hidden graph with $k$ components requires at least $(k-1)n-\binom k2$ membership queries.
Our result improves on the best known information-theoretic bound of $\Omega(n\log k)$ queries, and exactly matches the query complexity of the algorithm introduced by Reyzin and Srivastava <cit.> for this problem.
Additionally, we introduce an oracle, with access to which one can learn the number of components of $G$ in asymptotically fewer queries than learning the full partition, thus answering another question posed by the same authors.
Lastly, we introduce a more applicable version of this oracle, and prove asymptotically tight bounds of $\widetilde\Theta(m)$ queries for both learning and verifying an $m$-edge hidden graph $G$ using it.

[3]Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, USA.
[3]Mathematics Institute and DIMAP, University of Warwick, Coventry, CV4 7AL, UK<EMAIL_ADDRESS>[2]Blueqat Research, Shibuya 2-24-12, Tokyo, Japan<EMAIL_ADDRESS>[1]Equal contribution

Keywords: 	graph learning, graph reconstruction, query complexity

Accepted for presentation at the Conference on Learning Theory (COLT) 2022.

§ INTRODUCTION

§.§ Background and Applications

A graph $G=(V,E)$ consists of a vertex set $V$ and an edge set $E\subseteq \binom V2$.
The field of graph learning deals with learning a hidden graph using queries to black-box oracles that reveal partial information about the graph.
In several real world scenarios, learning a full graph by checking only pairwise adjacency is inefficient, and several oracles can speed up the process of learning by encoding more information per query.
Different oracles could be useful or easier to implement in different scenarios.
For example, in the context of trying to learn a hidden network graph, a traceroute query between a pair of vertices can give information about a shortest path between the vertices and their distance in the graph.
In the context of bioinformatics, one can model a graph with vertices corresponding to chemicals, and two vertices are joined by an edge if they react when mixed together.
In such a situation, oracles such as edge-detection and edge-counting can be implemented by mixing different sets of chemicals and measuring the intensity of reaction.
As calling an oracle incurs cost, researchers try to estimate the query complexity: the least number of queries to the oracle required to learn a specific graph or graph property.

A separate type of problem that is also widely studied is the problem of graph verification.
In this setting, we have a hidden graph $G=(V,E)$ and a known graph $\widehat G=(V,\widehat E)$, and an oracle that reveals information about $G$.
The main task in this area is to verify whether $G=\widehat G$ using as few oracle queries as possible.
In the context of our paper, we assume $|\widehat E| = |E|$, as $G$ and $\widehat G$ are trivially unequal if they do not have the same number of edges.
Verification tasks are prevalent in real networks where it is important to make sure a recent snapshot of a network is accurate.

Due to their practical and theoretical importance, both graph learning and verification have garnered a lot of interest in recent years.
Perhaps the first problem considered in the literature was the problem of learning a degree-bounded tree using the shortest path oracle <cit.>.
The shortest path oracle and the distance oracle were extensively studied in <cit.>.
The current best upper bound on learning a connected bounded-degree graph on $n$ vertices is due to  Mathieu and Zhou <cit.>, where they provide a randomized $\widetilde O(n^{3/2})$-query algorithm to learn such a graph.
Abrahamsen et. al. <cit.> prove the exact bound on the query complexity using a weaker oracle called the betweenness oracle, thus suggesting that the bound of $\widetilde O(n^{3/2})$ might be not tight.
Parallel results in graph verification have also been obtained for the distance oracle <cit.> and betweenness oracle <cit.>.
Although there is still a gap between the lower bound of $\Omega(n)$ and upper bound of $\widetilde O(n^{3/2})$ for learning degree-bounded graphs using distance oracle, the gap was closed recently for random degree-bounded regular graphs by Mathieu and Zhou <cit.>.

Another well-studied oracle is the edge-detection oracle, which, given a set of vertices of the hidden graph $G$, tells if it is an independent set or not.
Results on learning restricted classes of graphs using this oracle such as matchings <cit.>, stars and cliques <cit.>, Hamiltonian cycles <cit.> were succeeded by a very general treatment by  Angluin and Chen <cit.>.
Using a recursive coloring argument, they show that $O(m\log n)$ edge-detection queries are sufficient to learn an arbitrary hidden graph.
Reyzin and Srivastava <cit.> consider and compare the shortest path, edge-detection and edge-counting queries and prove a variety of lower and upper bounds for learning partitions, trees and arbitrary graphs.
In other related work, Beerliova et. al. <cit.> consider an oracle called the layered-graph oracle.

§.§ Our Results

§.§.§ Membership queries

Every graph $G$ admits a partition of its vertex set into connected components.
We say that a learner learns the components of $G$ if it learns this partition.
For an $n$-vertex hidden graph $G$ with $k$ components, one of the problems studied in <cit.> entails learning the components of $G$.
More precisely, if $\alpha$ denotes the membership query given by

\[
\alpha(u,v)=\left\{
\begin{array}{rl}
1, &\mbox{if }u\mbox{ and }v\mbox{ belong to the same component},\\
0, &\mbox{otherwise};
\end{array}
\right.
\]

then they demonstrate an algorithm to learn the components of $G$.

[Reyzin and Srivastava <cit.>]

* Start with a set $S$ of already classified vertices and a set $C$ of component representatives which are both initialized to $\{v_0\}$ for some arbitrary $v_0\in V(G)$.

* For every unclassified vertex $v\in V(G)\setminus S$, sequentially query $\{\alpha(x,v):x\in C\}$.

* If some query $\alpha(x,v)$ is true, add $v$ to $S$. Otherwise, the component of $v$ has not been discovered till now, so add $v$ to both $S$ and $C$.

* Repeat the procedure until $S=V(G)$.

It can be seen that when $k$ is small compared to $n$, Algorithm <ref> uses $O(nk)$ many $\alpha$-queries.
In particular, if we consider a graph $G$ which is the union of isolated vertices $\{1,\ldots, k-1\}$ and a clique $K_{\{k,\ldots, n\}}$, Proposition <ref> demonstrates that Algorithm <ref> uses $(k-1)n -\binom{k}{2}$ queries in the worst case.

However, the best known lower bound for this fundamental problem of learning components with $\alpha$ was an information-theoretic bound of $\Omega(n\log k)$ queries.
To the knowledge of the authors, no proof of an $\Omega(nk)$ lower bound has been published till date since it was first posed by Reyzin and Srivastava <cit.>.
Our main theorem is the first exact lower bound of $(k-1)n -\binom{k}{2}$ queries to this problem, when $k$ is known to the algorithm.

Given any algorithm $\mathcal A$ that makes membership queries on a hidden graph $G$ with $n$ vertices and $k$ components, there is an adversary that can force $\mathcal A$ to make at least $(k-1)n -\binom{k}{2}$ queries to learn the partition of $G$.

We also prove an exact bound if the number of connected components in $G$ is unknown.

Given any algorithm $\mathcal A$ that makes membership queries on a hidden graph $G$ with $n$ vertices,
there is an adversary that can force $\mathcal A$ to make at least $kn-\binom{k+1}{2}$ queries to learn the partition of $G$,
where $k$ is the number of connected components in $G$.

When the number of components $k$ of a hidden graph $G$ is known to an algorithm, intuitively it should require fewer queries to learn all components of $G$.
This is also reflected in the fact that our lower bound in Theorem <ref> is $(n-k)$ lower than the lower bound in Theorem <ref>.
According to Proposition <ref>, the bounds from both Theorems <ref> and <ref> are tight.

We make a note here that Theorems <ref> and <ref>, as well as the membership oracle is applicable to a much more general discrete setting: learning partitions of any finite $n$-element set into $k$ parts.
However, the problem of learning partitions is not well-represented in the literature and hence we use the more familiar and equivalent language of graph learning for presenting Theorems <ref> and <ref>.

§.§.§ Multiple-membership queries

Reyzin and Srivastava <cit.> also posed a question on whether there is an oracle that has to be queried fewer times to learn the number of components in an $n$-vertex hidden graph than learning the components.
For a vertex $u$ and a set $S$ of vertices not containing $u$, we define the multiple-membership query

\[
\alpha_m(u,S)=\left\{\begin{array}{rl}
1, & \mbox{if }u\mbox{ and }v\mbox{ belong to the same component for some }v\in S,\\
0, & \mbox{otherwise}.
\end{array}
\right.
\]

Our second result gives a positive answer to their question:

For an $n$-vertex hidden graph $G$, learning the number of components of $G$ can be done using $O(n)$ $\alpha_m$-queries. However, learning all the components requires $\Theta(n\log k)$ $\alpha_m$-queries.

§.§.§ Vertex-neighborhood detection queries

We modify $\alpha_m$ into a query that is more applicable in practical scenarios, which we call the vertex-neighborhood detection query $\beta$ given by:

\[
\beta(u,S)=\left\{\begin{array}{rl}
1, & \mbox{if }u\mbox{ and }v\mbox{ are adjacent for some }v\in S,\\
0, & \mbox{otherwise}.
\end{array}
\right.
\]

$\beta$ is useful in the setting of biochemistry where it is easy to detect a reaction between a fixed reagent and a set of other chemicals, and could be applicable to genome sequencing using polymerase chain reaction (PCR) tests <cit.>.

We analyze the problems of graph learning and graph verification using $\beta$-queries, and prove tight bounds for these problems (up to logarithmic factors):

Learning or verifying an $n$-vertex hidden graph on $m$ edges requires $\Omega(m)$ $\beta$-queries. Conversely, learning such a graph can be done in $O(m\log n)$ queries, whereas verifying can be done in $O(m+n)$ queries.

As an immediate consequence to Theorem <ref>, note that all sparse families of graph which satisfy $m=O(n)$, such as trees, planar graphs and minor-free graphs, can be both learned and verified using $\widetilde\Theta(n)$ queries to $\beta$.

This paper is organized as follows. In Section <ref>, we prove Theorems <ref>, <ref> and <ref>. Section <ref> presents our results on the $\beta$ oracle, and proves Theorem <ref>.
Finally, we make some concluding remarks in Section <ref>.

§ GRAPH PARTITIONS AND THE MEMBERSHIP QUERY

In this section, we consider the membership query given by $\alpha(u,v)=1$ iff $u$ and $v$ belong to the same connected component. Our goal in this section is to prove Theorem <ref>.

§.§ Preliminaries

We briefly state some preliminary results before diving into the proof.

§.§.§ Upper bound on query complexity of Algorithm <ref>

First, we give a quick demonstration of the upper bound of $(k-1)n-\binom k2$ of the query complexity of Algorithm <ref>.

Algorithm <ref> uses at most $(k-1)n-\binom k2$ queries to learn the graph $G$ consisting of isolated vertices $\{1,\ldots, k-1\}$ and a clique $K_{\{k,\ldots, n\}}$. If $k$ is not known to the algorithm, it requires $(n-k)$ additional queries.

Suppose $k$ is known. Without loss of generality assume that the algorithm determines the components of the $k-1$ isolated vertices using $1+\cdots+(k-2)=\frac 12(k-2)(k-1)$ many membership queries first.
Otherwise, if the large component is discovered earlier, our algorithm can learn $G$ using fewer queries.
To classify the remaining $(n-k+1)$ vertices into the $k$'th component, we only need to make sure that each of them does not share a component with $\{1,\ldots, k-1\}$.
This requires $(k-1)(n-k+1)$ membership queries.
Hence, the total number of $\alpha$-queries required in this case equals

\[\frac12(k-1)(k-2) + (k-1)(n-k+1) = (k-1)\left(n-\frac k2\right) = (k-1)n -\binom{k}{2},\]

as desired.

When $k$ is not known, the last $(n-k+1)$ vertices each require not only $(k-1)$ queries each, but the vertices $\{k+1,\ldots, n\}$ each need one additional query.
The total number of queries made therefore, is $(n-k)$ more, proving the second part of our claim.

§.§.§ Uniquely $k$-colorable graphs

Our proof will be closely related to the following definition in graph theory.

Given a graph $G$, we say that it is $k$-colorable if there is a labelling $\chi:V(G)\to \{1,\ldots, k\}$ such that the two endpoints of any edge receives distinct labels.
Such a $\chi$ is also called a proper $k$-coloring.
$G$ is said to be uniquely $k$-colorable if it has a unique proper $k$-coloring $\chi$ (up to permutations of $\{1,\ldots, k\}$).

The following theorem gives a lower bound for the number of edges in a uniquely $k$-colorable graph on $n$ vertices.

A uniquely $k$-colorable graph on $n$ vertices must have at least $(k-1)n - \binom k2$ edges.

For the sake of completeness, we give an outline of the proof. We urge the reader to refer to the cited sources for further information on uniquely $k$-colorable graphs.

Suppose $G$ is a uniquely $k$-colorable graph on $n$ vertices, and its color classes are $I_1,\ldots,I_k$.
Each $I_i$ is an independent set, and the edges of $G$ go across these color classes.
Let us fix any pair $i\neq j$, and consider the bipartite graph $G[I_i\cup I_j]$.
If $G[I_i\cup I_j]$ was disconnected, we could switch around the colors of these connected components to obtain a new proper $k$-coloring of $G$, a contradiction.
Thus, $G[I_i\cup I_j]$ is a connected bipartite graph, implying there are at least $|I_i|+|I_j|-1$ edges between components $I_i$ and $I_j$.
It can then be seen that

\[
\begin{aligned}
|E(G)|&\ge \sum_{i<j} |I_i|+|I_j|-1 \\&= (k-1)(|I_1|+\cdots+|I_k|) - \binom k2 \\&= (k-1)n - \binom k2.
\end{aligned}
\]

We are ready to present the proofs of Theorems <ref> and <ref> in the following two sections.

§.§ Membership query

First we present our proof of Theorem <ref>.
Recall that $\alpha(u,v)=1$ iff $u$ and $v$ belong to the same component in an $n$-vertex hidden graph with $k$ components, and we are aiming to prove a lower bound of $(k-1)n - \binom k2$ queries on learning all its components.

§.§.§ Proof of Theorem <ref>.

We will use the following definition in our proofs.

Suppose that $G$ is a $k$-colorable graph and $i,j \in V(G)$ are distinct vertices that are not adjacent in $G$.
Then $\{i,j\}$ is called a $k$-separable pair if there exists a
proper $k$-coloring $\chi\colon V(G)\to [k]$ of $G$ such that $\chi(i)\neq \chi(j)$,
and we call such a coloring $\chi$ an $\{i,j\}$-separating coloring.
Otherwise, we call $\{i,j\}$ a $k$-inseparable pair.

For example, the nonadjacent pair in $K_{k+1}^{-}$ (the graph obtained from a $(k+1)$-clique by removing one edge) is $k$-inseparable.
The following fact is easy to observe from the definition.

Suppose that $G$ is a $k$-colorable graph and $i,j \in V(G)$ are distinct vertices that are not adjacent in $G$.
Then $\{i,j\}$ is a $k$-inseparable pair if and only if the graph $G'$ obtained from $G$ by adding the edge $\{i,j\}$ has chromatic number $k+1$.

Now we present our proof of Theorem <ref>.
As mentioned earlier, our proof is adversarial.
We (the adversary) start with initializing an empty auxiliary (simple) graph $H$ with $|V(H)|=n$, and pick an arbitrary $k$-coloring $\chi:V(H) \to \{1,\ldots, k\}$ of $H$.
Let $G$ be the hidden graph corresponding to $H$, where each color class corresponds to a partition.

Suppose now that $\mathcal A$ makes a query $\alpha(x,y)$. We respond to $\mathcal A$ and update the graph $H$ and its $k$-coloring $\chi$ according to the following rules:

* If $\chi(x)\neq \chi(y)$, we add $xy$ to $E(H)$ and reply “no" to the algorithm.

* If $\chi(x)=\chi(y)$ and $\{x,y\}$ is $k$-separable in $H$,
we add $xy$ to $E(H)$ and modify the coloring of $G$ to a $\{x,y\}$-separating $k$-coloring, and reply “no".

* If $\chi(x)=\chi(y)$ and $\{x,y\}$ is $k$-inseparable,
then we do not add $xy$ to $E(H)$, and answer “yes".

We illustrate some intermediate steps in the evolution of $H$ and $\chi$ against a sample algorithm $\mathcal A$ in Figure <ref>.

redvertex=[align=center, inner sep=0pt, text centered, circle,black,fill=red!10,draw=red,text width=1.3em,very thick]
greenvertex=[align=center, inner sep=0pt, text centered, circle,black,fill=green!10,draw=green,text width=1.3em,very thick]
bluevertex=[align=center, inner sep=0pt, text centered, circle,black,fill=blue!10,draw=blue,text width=1.3em,very thick]

[bluevertex] (x4) at (0:2)$4$;
[redvertex] (x3) at (60:2)$3$;
[redvertex] (x2) at (120:2)$2$;
[redvertex] (x1) at (180:2)$1$;
[greenvertex] (x6) at (240:2)$6$;
[bluevertex] (x5) at (300:2)$5$;
(270:3) node $G:\ \{1,2,3\}, \{4,5\}, \{6\}$;

(3.5,0) node [above] $ \alpha(1,5)$;
[->] (2.7,0)–(4.3,0);

[bluevertex] (x4) at (0:2)$4$;
[redvertex] (x3) at (60:2)$3$;
[redvertex] (x2) at (120:2)$2$;
[redvertex] (x1) at (180:2)$1$;
[greenvertex] (x6) at (240:2)$6$;
[bluevertex] (x5) at (300:2)$5$;
(270:3) node $G:\ \{1,2,3\}, \{4,5\}, \{6\}$;

(10.5,0) node [above] $ \alpha(2,3)$;
[->] (9.7,0)–(11.3,0);

[bluevertex] (x4) at (0:2)$4$;
[redvertex] (x3) at (60:2)$3$;
[redvertex] (x2) at (120:2)$2$;
[redvertex] (x1) at (180:2)$1$;
[greenvertex] (x6) at (240:2)$6$;
[bluevertex] (x5) at (300:2)$5$;
[dashed] (x2)–(x3) node [above, midway] separable;
(270:3) node $G:\ \{1,2,3\}, \{4,5\}, \{6\}$;

[->] (14,-3.8)–(14,-4.3);

[greenvertex] (x4) at (0:2)$4$;
[bluevertex] (x3) at (60:2)$3$;
[redvertex] (x2) at (120:2)$2$;
[redvertex] (x1) at (180:2)$1$;
[greenvertex] (x6) at (240:2)$6$;
[bluevertex] (x5) at (300:2)$5$;
(270:3) node $G:\ \{1,2\}, \{3,5\}, \{4,6\}$;

(10.5,-7) node [above] $ \alpha(1,3)$;
[->] (11.3,-7)–(9.7,-7);

[greenvertex] (x4) at (0:2)$4$;
[bluevertex] (x3) at (60:2)$3$;
[redvertex] (x2) at (120:2)$2$;
[redvertex] (x1) at (180:2)$1$;
[greenvertex] (x6) at (240:2)$6$;
[bluevertex] (x5) at (300:2)$5$;
(270:3) node $G:\ \{1,2\}, \{3,5\}, \{4,6\}$;

(3.5,-7) node [above] $\alpha(1,2)$;
[->] (4.3,-7)–(2.7,-7);

[greenvertex] (x4) at (0:2)$4$;
[bluevertex] (x3) at (60:2)$3$;
[redvertex] (x2) at (120:2)$2$;
[redvertex] (x1) at (180:2)$1$;
[greenvertex] (x6) at (240:2)$6$;
[bluevertex] (x5) at (300:2)$5$;
[dashed] (x1)–(x2) node [midway, above, rotate=60] inseparable;
(270:3) node $G:\ \{1,2,3\}, \{4,5\}, \{6\}$;

A sample set of queries and the corresponding evolution of $H$ and the partition of $G$. Here $n=6$ and $k=3$. Our adversary responds “yes" only to $\alpha(1,2)$, and “no" to all other $\alpha$-queries made by $\mathcal A$ in this example.

Observe that adding new edges into $H$ does not change the inseparability of a pair $\{x,y\}$.
Therefore, all $k$-inseparable pairs $\{x,y\}$ of $H$ remain $k$-inseparable in the evolution of the algorithm.
Further, by construction, every edge of $H$ corresponds to a non-coincidence in $G$'s components.
Vertex pairs $\{x,y\}$ of $H$ that have $\alpha(x,y)=1$ are $k$-inseparable, and hence belong to the same color class for any proper $k$-coloring of $H$.
Further, $\chi$ is always a proper $k$-coloring of $H$, and hence induces a partition of $G$ into $k$ components.

Now, suppose that $\mathcal A$ learns a unique partition of $G$ into $k$ components.
This would mean that the coloring $\chi$ of the graph $H$ must be a unique $k$-coloring.
By Theorem <ref>, $H$ has at least $(k-1)n - \binom k2$ edges, as desired.

We note that our adversary checks over all possible $k$-colorings of $H$, and hence does not have a $\poly(n,k)$ runtime.
However, a slight modification to the argument above (given in Appendix <ref>) is able to prove the existence of a $\poly(n,k)$-time adversary that forces at least $\frac12(n-k)(k-1)$ queries.
It might be interesting to analyze the effect of limiting resources available to the adversary to prove different versions of this theorem.

§.§.§ Proof of Theorem <ref>

Now we prove Theorem <ref>.
Our proof is basically a modification of the proof of Theorem <ref>: instead of a single auxiliary graph $H$ with $|V(H)|=n$, now we will maintain two graphs $H_1$ and $H_2$ on the same vertex set $V$ of size $n$.
We start with the coloring $\chi\colon V\to \{1\}$, i.e. all vertices of $V$ receive the color $1$.

Suppose an algorithm $\mathcal A$ makes a query $\alpha(x,y)$. We then respond according to the rules below:

* If $\chi(x)\neq \chi(y)$, add $xy$ to $E(H_1)$ and reply “no" to the algorithm.

* If $\chi(x)=\chi(y)$ and $\{x,y\}$ is $k$-separable in $H_1$,
add $xy$ to $E(H_1)$ and modify the coloring of $H_1$ to a $\{x,y\}$-separating coloring, and reply “no".

* If $\chi(x)=\chi(y)$ and $\{x,y\}$ is $k$-inseparable in $H_1$,
add $xy$ to $E(H_2)$ and answer “yes".

Note that similar to before, adding new edges into $H_1$ does not change the inseparability of a pair $\{x,y\}$. Hence, if $\mathcal A$ learns the hidden graph $G$ when the algorithm stops, the graph $H_1$ must be a uniquely $k$-colorable graph.
This implies

\[
|E(H_1)|\ge (k-1)n-\binom k2.
\]

Additionally, we claim the following about $H_2$.

When $\mathcal A$ stops, the graph $H_2$ must have at most $k$ connected components.

Let us assume that the unique $k$-partition corresponding to $H_1$ is $\mathcal{P}_k = \{V_1,\ldots, V_k\}$.

Suppose on the contrary that $H_2$ has $m$ connected components and $m\ge k+1$, say with vertex sets $C_1, \ldots, C_m$.
As every edge of $H_2$ corresponds to an inseparable pair, for every $i\in [m]$, there exists $j\in [k]$ such that $C_i \subset V_j$.
In other words, the $m$-partition $\mathcal{P}_m = \{C_1,\ldots, C_m\}$ is a refinement of $P_{k}$.
The contradiction is that $\mathcal A$ cannot distinguish
the $m$-partition $\mathcal{P}_m$ from the $k$-partition $\mathcal{P}_k$.
Therefore, $H_2$ has at most $k$ connected components.

As an immediate corollary, we obtain $|E(H_2)| \ge n-k$.
Therefore, the algorithm requires at least

\[|E(H_1)|+|E(H_2)| \ge (k-1)n-\binom{k}{2}+n-k = kn-\binom{k+1}2\]

many queries, completing the proof of Theorem <ref>.

§.§ Multiple-membership query

Now we turn our attention to the problem of learning both $k$ and individual components using multiple-membership queries.

§.§.§ Proof of Theorem <ref>

Recall that $\alpha_m(u,S)=1$ if and only if there is a $v\in S$ such that $u$ and $v$ belong to the same component. There are three assertions in Theorem <ref>, and we prove each of them below.

* Part 1. Learning $k$: First, we demonstrate an algorithm that learns the number of components of an $n$-vertex hidden graph $G$ using $O(n)$ queries to $\alpha_m$.
Start with $S=V(G)$.
While there is a vertex $v\in S$ such that $\alpha_m(v,S\setminus\{v\})=1$, we delete $v$ from $S$.
When this algorithm terminates, we end up with an independent set $S$ whose each vertex lies in a different component.
Conversely, as every other vertex $v\in V(G)$ lies in the same component as some vertex in $G$, $|S|$ will equal the number of components of $G$.
Therefore, the above algorithm learns $k$ using $O(n)$ many $\alpha_m$-queries. $\blacksquare$

* Part 2. Lower bound on learning components: Next, we claim that learning all components of $G$ requires at least $\Omega(n\log k)$ queries.
This proof is information-theoretic.
The total number of partitions of $n$ vertices into $k$ parts is $\Omega(k^n)$, and hence any algorithm making $\alpha_m$-queries must have depth $\Omega(n\log k)$. $\blacksquare$

* Part 3. Upper bound on learning components: Note that the function <ref> learns the components of the hidden graph $G$ using multiple-membership queries.
Vertex set $V(G)=\{v_1,\ldots,v_n\}$, Oracle $\alpha_m$.
Partition $V(G)=C_1\sqcup\cdots\sqcup C_k$ such that each $C_i$ is a connected component.
Initialize $C_1=\{v_1\}$, $k=1$
$i=2$ to $n$
$\alpha_m(v_i, C_1\cup\cdots \cup C_k)=0$
k += 1
Add $v_i$ to $C_k$

Find $j$ such that $\alpha_m(v_i, C_j)=1$ via binary search among $\{C_1,\ldots, C_k\}$
Add $v_i$ to its corresponding $C_j$

$\{C_1,\ldots, C_k\}$

The binary search in the else statement works because $\alpha_m$ can query $v_i$ with a union of several $C_j$'s at once. This step requires $O(\log k)$ queries, and therefore our algorithm has query complexity of $O(n\log k)$.$\blacksquare$

This completes the proof of Theorem <ref>, and hence $\alpha_m$ is an oracle that can learn the number of components $k$ in a hidden graph with fewer queries than learning the components. $\Box$

§ THE VERTEX-NEIGHBORHOOD DETECTION QUERY

For the remainder of the paper, we consider the vertex-neighborhood detection query given by $\beta(v,S)=1$ iff there is some edge from $v$ to some vertex in $S$.
We now prove tight bounds of $\widetilde \Theta(m)$ for both learning and verifying graphs (with $m$ edges) using $\beta$-queries.

§.§ Proof of Theorem <ref>

Now we move onto analyzing the problems of graph learning and verification using the oracle $\beta$.
Let us take a hidden graph $G$ on $n$ vertices and $m$ edges. It is clear that $\beta$ can only detect one edge at a time, and hence both learning and verifying a hidden graph using $\beta$ would trivially require at least $\Omega(m)$ queries.
Hence, it suffices to prove upper bounds of $O(m+n)$ for verification and $O(m\log n)$ for learning $G$.

§.§.§ Verification using $\beta$

For the verification problem, we have a graph $\widehat G$ with $V(\widehat G) = V(G) = V$ that is known to us. We verify each edge $uv\in E(\widehat G)$ individually by checking $\beta(u,\{v\})=1$, and this requires $m$ queries.

Next, we verify the non-edges of $\widehat G$. Fix a vertex $v$ and compute its neighborhood $N_{\widehat G}(v)=\{u\in V: uv\in E(\widehat G)\}$.
Note that if $\widehat G$ was the same as $G$, we would have

\[
\beta\Bigl(v, V\setminus ( N_{\widehat G}(v)\cup\{v\} )\Bigr)=0.
\]

Since checking all non-edges through a vertex takes a single $\beta$-query, we can verify all non-edges of $\widehat G$ using $n$ queries.
Hence, verifying all edges and non-edges of $G$ using can be done using $O(m+n)$ $\beta$-queries.$\blacksquare$

§.§.§ Learning using $\beta$

Although slightly more involved, our algorithm for learning a hidden graph $G$ is also based on divide-and-conquer.
The main step consists of devising a recursive method (which we call <ref>) that, for a fixed vertex $v\in V$, learns all neighbors (and non-neighbors) of $v$.

Vertex $v$, Set $S$, Hidden graph $G$, Oracle $\beta$.
Mark all neighbors of $v$ in $S$ blue, and non-neighbors red.
findNeighbors($v, S$).
Mark the vertex of $S$ blue and terminate

Mark the vertex of $S$ red and terminate

Divide $S$ into two (approximately) equal parts $S_1\sqcup S_2$
$\beta(v, S_1)=1$
findNeighbors($v, S_1$)

Mark all vertices of $S_1$ red and terminate

$\beta(v, S_2)=1$
findNeighbors($v, S_2$)

Mark all vertices of $S_2$ red and terminate

Let us first analyze the query complexity of <ref>.

Suppose $\ell$ is the number of neighbors of $v$ in $S$.
Then, <ref>($v,S$) takes at most $O(\ell\log |S|)$ queries to mark all neighbors of $v$ in $S$ red and non-neighbors blue.

(Claim <ref>):
We take a look at the recursion tree $T$ for <ref>($v,S$), and color its nodes red or blue as follows.
The root node corresponds to the computation of <ref>($v,S$), and so we keep the set $S$ in it.
If $\beta(v,S)=1$, we color the root node blue, otherwise we color it red.
In the next level, the node containing $S$ has two children: $S_1$ and $S_2$ corresponding to the equipartition of $S$.
Let us color $S_1$ blue if $\beta(v,S_1)=1$, and red otherwise. Similarly, we color $S_2$, and continue this coloring scheme down the entire recursion tree.
A sample $T$ and its coloring is depicted in Figure <ref>.

A sample recursion tree $T$ corresponding to <ref>($v,S$)

Let $T_b$ be the subtree with blue vertices. It is clear that each leaf of $T_b$ corresponds to a vertex marked blue by <ref>, implying that $T_b$ is a tree with $\ell$ leaves and depth at most $\log|S|$. Therefore,

\[
|V(T_b)|\le O(\ell\log |S|).
\]

Now we take a closer look at the red vertices of $T$.
By construction, each red vertex is a leaf, i.e. the computation stops at these vertices.
This means that the parents of red vertices are always blue.
Further, two red nodes cannot be siblings, as if $\beta(v,A)=\beta(v,B)=0$, then $\beta(v, A\cup B)=0$, implying that the computation would have stopped at the parent of $A$ and $B$.
Thus, every red vertex has a unique blue parent.
This implies that the number of red vertices in $T$ is bounded above by $|V(T_b)|$, leading to

\[
|V(T)|\le 2|V(T_b)| \le O(\ell \log |S|),
\]

completing the proof of Claim <ref>.

Therefore, to learn $G$, we can run <ref>($v, V\setminus \{v\}$) over all vertices $v$. Observe that the total number of queries made is at most

\[
\sum_{v\in V(G)} O(\deg(v)\log n) = O(m\log n),
\]

thus proving the required upper bound. $\blacksquare$

§ CONCLUSION AND FUTURE WORK

In this paper, we demonstrated a fundamental and exact lower bound on the problem of learning partitions using membership queries (which we called $\alpha$), filling a long lasting gap in the literature.
We generalized the membership oracle to take subsets of vertices as one of its inputs (which we called $\alpha_m$), and demonstrated how learning the number of components can be done using fewer $\alpha_m$-queries than the components themselves.
In the second section, we also demonstrated a powerful oracle (which we called $\beta$) that can be used to efficiently learn and verify sparse graphs.

It would be very interesting to see other oracles which can exploit structural properties of sparse graphs, such as the existence of small separators.
Graph families that admit the existence of small separators include a vast array of graphs such as planar graphs <cit.>, bounded genus graphs <cit.>, minor-free graphs <cit.>, etc.
Further, it should be possible to extend these results to learning and verification of graphs with polynomially bounded expansion <cit.>, and we leave this as a future avenue of investigation.

§ ACKNOWLEDGMENTS

The authors are immensely thankful to Mano Vikash Janardhanan for bringing the membership oracle to their attention, and for several fruitful discussions on graph learning theory.
Research of the first author was supported by ERC Advanced Grant 101020255.

§ APPENDIX: POLYNOMIAL-TIME ADVERSARY AGAINST ALGORITHM <REF>

Our goal in this section is to prove a slight modification of Theorem <ref>. We prove that by sacrificing a constant factor of $\frac 12$, it is possible to demonstrate an adversary that runs in $\poly(n,k)$ time:

Given any algorithm $\mathcal A$ that makes membership queries on a hidden graph $G$ with $n$ vertices and $k$ components, there is a $\poly(n,k)$-time adversary that can force $\mathcal A$ to make at least $\frac12(n-k)(k-1)$ $\alpha$-queries to learn the partition of $G$.

As in the original proof, we initialize an empty graph $H$ with $|V(H)|=n$, and pick any $k$-coloring $\chi:V(H) \to \{1,\ldots, k\}$ of $H$.
Let $G$ be the hidden graph corresponding to $H$, where each color class corresponds to a partition.
For the sake of simplicity, we shall call vertices of $H$ with degree at least $k-1$ big, and those with degree less than $k-1$ small.

redvertex=[align=center, inner sep=0pt, text centered, circle,black,fill=red!10,draw=red,text width=1.3em,very thick]
bigredvertex=[align=center, inner sep=2pt, circle,black,fill=red!10,draw=red,text width=1.2em,very thick]
greenvertex=[align=center, inner sep=0pt, text centered, circle,black,fill=green!10,draw=green,text width=1.3em,very thick]
bluevertex=[align=center, inner sep=0pt, text centered, circle,black,fill=blue!10,draw=blue,text width=1.3em,very thick]

[bluevertex] (x4) at (0:2)$4$;
[redvertex] (x3) at (60:2)$3$;
[redvertex] (x2) at (120:2)$2$;
[redvertex] (x1) at (180:2)$1$;
[greenvertex] (x6) at (240:2)$6$;
[bluevertex] (x5) at (300:2)$5$;
(270:3) node $G:\ \{1,2,3\}, \{4,5\}, \{6\}$;

(3.5,0) node [above] $ \alpha(3,4)$;
[->] (2.7,0)–(4.3,0);

[bluevertex] (x4) at (0:2)$4$;
[redvertex] (x3) at (60:2)$3$;
[redvertex] (x2) at (120:2)$2$;
[redvertex] (x1) at (180:2)$1$;
[greenvertex] (x6) at (240:2)$6$;
[bluevertex] (x5) at (300:2)$5$;
(270:3) node $G:\ \{1,2,3\}, \{4,5\}, \{6\}$;

(10.5,0) node [above] $ \alpha(2,3)$;
[->] (9.7,0)–(11.3,0);

[bluevertex] (x4) at (0:2)$4$;
[redvertex] (x3) at (60:2)$3$;
[redvertex] (x2) at (120:2)$2$;
[redvertex] (x1) at (180:2)$1$;
[greenvertex] (x6) at (240:2)$6$;
[bluevertex] (x5) at (300:2)$5$;
[dashed] (x2)–(x3);
(x2) node [above=.5em] big;
(x3) node [above=.5em] small;
(270:3) node $G:\ \{1,2,3\}, \{4,5\}, \{6\}$;

[->] (14,-3.8)–(14,-4.3);

[bluevertex] (x4) at (0:2)$4$;
[greenvertex] (x3) at (60:2)$3$;
[redvertex] (x2) at (120:2)$2$;
[redvertex] (x1) at (180:2)$1$;
[greenvertex] (x6) at (240:2)$6$;
[bluevertex] (x5) at (300:2)$5$;
(270:3) node $G:\ \{1,2\}, \{4,5\}, \{3,6\}$;

(10.5,-7) node [above] $ \alpha(1,2)$;
[->] (11.3,-7)–(9.7,-7);

[bluevertex] (x4) at (0:2)$4$;
[greenvertex] (x3) at (60:2)$3$;
[redvertex] (x2) at (120:2)$2$;
[redvertex] (x1) at (180:2)$1$;
[greenvertex] (x6) at (240:2)$6$;
[bluevertex] (x5) at (300:2)$5$;
[dashed] (x1)–(x2);
(x1) node [above=.5em] big;
(x2) node [above=.5em] big;
(270:3) node $G:\ \{1,2\}, \{4,5\}, \{3,6\}$;

(3.5,-7) node [above] $\alpha(1,2)$;
[->] (4.3,-7)–(2.7,-7);

[shift=(0,-7), rotate=18]
[greenvertex] (x4) at (0:2)$4$;
[bluevertex] (x3) at (72:2)$3$;
[bigredvertex] (x12) at (144:2)$1$,$2$;

[greenvertex] (x6) at (216:2)$6$;
[bluevertex] (x5) at (288:2)$5$;
(270:3) node $G:\ \{1,2\}, \{3,5\}, \{4,6\}$;

A sample set of queries and the corresponding evolution of $H$ and the partition of $G$. Here $n=6$ and $k=3$, and vertices of degree at least $2$ are “big". Our adversary responds “yes" to $\alpha(1,2)$ and “no" to every other query made by $\mathcal A$.

Suppose now that $\mathcal A$ makes a query $\alpha(x,y)$. We respond to $\mathcal A$ as follows:

* If $\chi(x)\neq \chi(y)$, we add $xy$ to $E(H)$ and reply “no" to the algorithm.

* If $\chi(x)=\chi(y)$ and either $x$ or $y$ is small, say $x$, then we note that $x$ has at most $k-2$ neighbors and hence two admissible colors.
We then modify $\chi(x)$ to its other admissible color different from $\chi(y)$, add the edge $xy$ to $E(H)$, and reply “no".

* Finally, if $\chi(x)=\chi(y)$ and both $x$ and $y$ are big, we identify (i.e., contract) vertices $x$ and $y$.
In terms of $G$, this would mean $x$ and $y$ belong to the same component.

We illustrate some intermediate steps in the evolution of $H$ and $\chi$ in Figure <ref>.

Note that $\chi$ is always a proper $k$-coloring of $H$, and hence induces a partition of $G$ into $k$ components. Suppose that $\mathcal A$ learns a unique partition of $G$ into $k$ components.
Then, there are two cases to consider:

* Case 1. The adversary contracts at least $\frac n2$ vertices:
In this case, as each contracted vertex has degree at least $k-1$, $\mathcal A$ must have made at least $\frac n2(k-1)$ queries.

* Case 2. The adversary contracts less than $\frac n2$ vertices:
In this case, $\mathcal A$ can learn a unique partition of $G$ iff $\chi$ is a unique $k$-coloring of $H$. Since $H$ started with $n$ vertices, $H$ is a graph on at least $\frac n2$ vertices which is uniquely $k$-colorable. By Theorem <ref>, $H$ has at least $\frac n2(k-1) - \binom k2$ edges.

In either case, $\mathcal A$ makes at least $\frac n2(k-1)-\binom k2=\frac12(n-k)(k-1)$ queries, as desired.