# Improving the error term in the sieve of Eratosthenes

Madieyna Diouf  Department of Mathematics, Arizona State University, Tempe, AZ
85282<EMAIL_ADDRESS>
(Date: 09/20/2023)

###### Abstract.

We reduce the error term in the sieve of Eratosthenes taking care to ensure
that $n$ satisfies certain properties.

###### Key words and phrases:

Sieve theory, prime number theorem, prime counting function

###### 2010 Mathematics Subject Classification:

11N05, 11N36

##  1\. Introduction And Statement of Results

Sieve theory aims to improve upon the Sieve of Eratosthenes [2] by addressing
limitations related to the Mobius function and parity problem that hamper
accurate estimates. Despite the development of advanced techniques that lead
to more refined sieves like Brun’s sieve [3], Selberg’s sieve [5], and the
general number field sieve [7] among others that have assisted in overcoming
some of the obstacles posed by the original sieve, improving the error term in
the Sieve of Eratosthenes without straying too far from the core concept
remains a difficult task.
Our solution seeks to overcome this challenge and provides a valuable
perspective on a long-standing issue, with a small yet significant improvement
in the precision of the error term, currently at

$\displaystyle R=O\left(2^{w(P(z))}\right)=O\left(2^{\pi(n)}\right).$

We improve the expression to

(1.1) $\displaystyle R=O\left(2^{w\left(\frac{P(z)}{rad(n)}\right)}\right),$

given that $n$ has no prime divisor $\geq\sqrt{n}$, which guarantees that
$P(z)/rad(n)$ is an integer, where $rad(n)$ denotes the product of distinct
prime divisors of $n$;

$\displaystyle rad(n)=\prod_{p\mid n\atop p\text{ prime}}p.$

The best-known upper limit of $\pi(n)$ [11, 13] using Eratosthenes’s sieve is

(1.2) $\displaystyle\pi(n)$ $\displaystyle\ll\frac{n}{\log\log n}.$

The outcome given in $(1.2)$ is achieved by reducing the value of $z$ to $\log
n$. However, it is less robust than the Prime Number Theorem. Nevertheless, it
demonstrates the applicability and effectiveness of sieve theory. Our approach
is comparable, but we keep $z$ at $\sqrt{n}$ and improve the error term to
obtain the upper bound stated in $(1.1)$. Although we fall short of presenting
a retrieval of the upper bound in Chebyshev’s inequality using the sieve of
Eratosthenes, our findings open opportunities for further research with the
potential to deliver results that align more with the prime number theorem
which states that

$\displaystyle\pi(n)$ $\displaystyle\ll\frac{n}{\log n}.$

The essential concept behind achieving our result in expression $(1.1)$ is to
assign $d=d^{\prime}(n,d)$ for each divisor $d$ of $P(z)$, where $d^{\prime}$
is a positive integer, and execute a variable shift from $d$ to $d^{\prime}$
while summing;

$\displaystyle\sum_{d|P(z)}\mu(d)\left\\{\frac{n}{d}\right\\}.$

Significant results have been achieved in the field and beyond using
applications of sieve theory. Examples include Chen’s theorem [4], GYT theorem
[6], Green-Tao theorem [8] and Zhang-Maynard’s result [10, 12], to name a few.

##  2\. Background

Let us first introduce some well known concepts in sieve theory using sieve
notations. Consider a finite sequence of integers
$\mathscr{A}=\\{1,2,...,\>n\\}$ and a set of primes $\mathscr{P}$. For a given
$z\geq 2$, let $P(z)=\prod_{p<z,\>p\in\mathscr{P}}p$. Let $S(\mathscr{A,P},z)$
denote the number of primes in $\mathscr{A}$ that have no prime divisors
$p<z$. Say $\tau(n)$ is the number of positive divisors of $n$. Letting
$\mu(d)$ be the Möbius function, the exact formula of the Sieve of
Eratosthenes by Legendre is

$\displaystyle\pi(n)-\pi(z)+1=\sum_{d|P(z)}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor.\text{\>
\> \> \> \> \> \> }$

We obtain the Legendre identity

$\displaystyle S(\mathscr{A,P},z)$
$\displaystyle=\sum_{d|P(z)}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor.$ (2.1)
$\displaystyle S(\mathscr{A,P},z)$
$\displaystyle=n\sum_{d|P(z)}\frac{\mu(d)}{d}+\sum_{d|P(z)}\mu(d)\left\\{\frac{n}{d}\right\\}.$
$\displaystyle S(\mathscr{A,P},z)$
$\displaystyle=n\sum_{d|P(z)}\frac{\mu(d)}{d}+\sum_{d|P(z)}O(1).$
$\displaystyle=n\sum_{d|P(z)}\frac{\mu(d)}{d}+O\Big{(}\tau\big{(}P(z)\big{)}\Big{)}.$
$\displaystyle=n\prod_{p\leq
z}\left(1-\frac{1}{p}\right)+O\left(2^{\omega\left(P(z)\right)}\right).$ (2.2)
$\displaystyle S(\mathscr{A,P},z)$ $\displaystyle=n\prod_{p\leq
z}\left(1-\frac{1}{p}\right)+O\left(2^{\pi(z)}\right).$

But $(2.2)$ is of limited use (with current methods), unless $z$ is very small
such as $z=\log n$. This paper presents an alternative method.

##  3\. Results

For every divisor $d$ of $P(z)$, we let
$d=d^{\prime}\text{gcd}(d,n)$ for some integer $d^{\prime}$.
Going forward, the notation $(d,n)$ is used to denote the gcd$(d,n)$.
By replacing $d$ with $d^{\prime}(d,n)$, we obtain

$\displaystyle\sum_{d|P(z)}\mu(d)\left\\{\frac{n}{d}\right\\}$
$\displaystyle=\sum_{d^{\prime}(d,n)|P(z)}\mu(d^{\prime}(d,n))\left\\{\frac{n}{d^{\prime}(d,n)}\right\\}.$
(3.1) $\displaystyle=\sum_{d^{\prime}\big{|}\frac{P(z)}{(d,n)}}O(1).$

We observe the following:

$\displaystyle d^{\prime}$ $\displaystyle\big{|}\frac{P(z)}{(d,n)},$
$\displaystyle d^{\prime}$
$\displaystyle\big{|}\frac{P(z)rad(n)}{(d,n)rad(n)},$ (3.2) $\displaystyle
d^{\prime}$ $\displaystyle\big{|}\frac{P(z)}{rad(n)}k,$

where

(3.3) $\displaystyle k$ $\displaystyle=\frac{rad(n)}{(d,n)}.\text{\> \> \> \>
}$

The objective is to show that

(3.4) $\displaystyle d^{\prime}\big{|}\frac{P(z)}{rad(n)}.\text{\> \> \> \> }$

By using our configuration

(3.5) $\displaystyle d$ $\displaystyle=d^{\prime}(d,n),\text{\> \> \> }$

we consider the trivial case when $d=1$, then $d^{\prime}=1$ and $(3.4)$ is
justified.
If $d\mid n$, then $(d,n)=d$ and by $(3.5)$, $d^{\prime}=1$; But this is not
relevant since $\left\\{\frac{n}{d}\right\\}=0$.
If $d>n$, then $\lfloor\frac{n}{d}\rfloor=0$ at the start of the sieve. As a
result, $d$ does not contribute to the primary term or the error term, which
makes this scenario irrelevant.
Now suppose that $d\leq n$, $d\neq 1$ and $d\nmid n$, then $d^{\prime}\neq 1$.
By $(3.5)$,

$d^{\prime}\mid d$.

Thus,

$\displaystyle\text{$d^{\prime}\nmid(d,n)$};$

On the contrary, suppose that $d^{\prime}\mid(d,n)$, then $(d,n)=\alpha
d^{\prime}$ for some positive integer $\alpha$. By replacing $(d,n)$ with
$\alpha d^{\prime}$ in $(3.5)$, we have

(3.6) $\displaystyle d$ $\displaystyle=d^{\prime}\alpha d^{\prime}.$

Equation $(3.6)$ suggests that $d$ is not square free and this contradicts the
fact that $d\mid P(z)$; Therefore, $d^{\prime}\nmid(d,n)$. In addition, by
$(3.5)$ we have $d^{\prime}\mid d$; Hence,

$d^{\prime}$ does not divide $n$, $d^{\prime}$ does not divide $rad(n)$, (3.7)
$d^{\prime}$ does not divide $\frac{rad(n)}{(d,n)}$.

By $(3.3)$ and $(3.7)$,

(3.8) $\displaystyle d^{\prime}\nmid k.$

Upon including $(3.8)$ in $(3.2)$, we arrive at the following conclusion.

(3.9) $\displaystyle d^{\prime}$ $\displaystyle\big{|}\frac{P(z)}{rad(n)}.$

Applying $(3.9)$ to equation $(3.1)$, leads us to the following.

$\displaystyle\sum_{d|P(z)}\mu(d)\left\\{\frac{n}{d}\right\\}$
$\displaystyle=\sum_{d^{\prime}\big{|}\frac{P(z)}{rad(n)}}O(1).$ (3.10)
$\displaystyle=O\Big{(}2^{w\big{(}\frac{P(z)}{rad(n)}\big{)}}\Big{)}.$

Since $n$ has no prime divisor $\geq\sqrt{n}$, then $rad(n)\mid P(z)$. Thus,
$(3.10)$ is an improvement over the sieve’s current error term of
$O(2^{w(P(z))})$.

## References

  * [1] Nair, M. (February 1982). ”On Chebyshev-Type Inequalities for Primes”. American Mathematical Monthly. 89 (2): 126–129. doi:10.2307/2320934. JSTOR 2320934.
  * [2] Nicomachus and M. L. D’ooge (trans.). Introduction to Arithmetic. Macmillan, New York, 1926.
  * [3] V. Brun, Le crible d’Eratosthéne et le théorème de Goldbach, Skr. Norske Vid.-Akad. Kristiania I, No. 3, 1920.
  * [4] Ross, P. M. ”On Chen’s theorem that each large even number has the form P 1+ P 2 or P 1+ P 2 P 3.” Journal of the London Mathematical Society 2.4 (1975): 500-506.
  * [5] A. Selberg, Sieve methods, Proc. Sympos. Pure Math., vol. 20, Amer. Math. Soc, Providence,
  * [6] Goldston, Daniel A., János Pintz, and Cem Y. Yildirim. ”Primes in tuples I.” Annals of Mathematics (2009): 819-862.
  * [7] Lenstra, Arjen K., and W. Hendrik Jr. The development of the number field sieve. Vol. 1554. Springer Science & Business Media, 1993. R. I., 1971, pp. 311—351.
  * [8] Tarrence Tao. ”The parity problem in sieve theory”. https://terrytao.wordpress.com/2007/06/05/open-question-the-parity-problem-in-sieve-theory/
  * [9] Green, Ben, and Terence Tao. ”The primes contain arbitrarily long arithmetic progressions.” Annals of Mathematics (2008): 481-547.
  * [10] Zhang, Yitang. ”Bounded gaps between primes.” Annals of Mathematics (2014): 1121-1174.
  * [11] Ford, Kevin, and Heini Halberstam. ”The Brun-Hooley sieve.” Journal of Number Theory 81.2 (2000): 335-350.
  * [12] Maynard, James. ”Small gaps between primes.” Annals of mathematics (2015): 383-413.
  * [13] FORD, KEVIN. ”SIEVE METHODS LECTURE NOTES, PART I THE BRUN-HOOLEY SIEVE.”


# Coefficients of the inverse of functions for the subclass of the class
$\boldsymbol{\mathcal{U}(\lambda)}$

Milutin Obradović  Department of Mathematics, Faculty of Civil Engineering,
University of Belgrade, Bulevar Kralja Aleksandra 73, 11000, Belgrade, Serbia
<EMAIL_ADDRESS>and  Nikola Tuneski  Department of Mathematics and
Informatics, Faculty of Mechanical Engineering, Ss. Cyril and Methodius
University in Skopje, Karpoš II b.b., 1000 Skopje, Republic of North
Macedonia<EMAIL_ADDRESS>
###### Abstract.

Let ${\mathcal{A}}$ be the class of functions $f$ that are analytic in the
unit disk ${\mathbb{D}}$ and normalized such that
$f(z)=z+a_{2}z^{2}+a_{3}z^{3}+\cdots$. Let $0<\lambda\leq 1$ and

${\mathcal{U}}(\lambda)=\left\\{f\in{\mathcal{A}}:\left|\left(\frac{z}{f(z)}\right)^{2}f^{\prime}(z)-1\right|<\lambda,\,z\in{\mathbb{D}}\right\\}.$

In this paper sharp upper bounds of the first three coefficients of the
inverse function $f^{-1}$ are given in the case when

$\frac{f(z)}{z}\prec\frac{1}{(1-z)(1-\lambda z)}.$

###### Key words and phrases:

univalent, inverse functions, coefficients, sharp bound

###### 1991 Mathematics Subject Classification:

30C45

Let ${\mathcal{A}}$ denote the family of all analytic functions in the unit
disk ${\mathbb{D}}:=\\{z\in{\mathbb{C}}:\,|z|<1\\}$ satisfying the
normalization $f(0)=0=f^{\prime}(0)-1$. Let $\mathcal{S}$ denote the subclass
of $\mathcal{A}$ which consists of univalent functions in ${\mathbb{D}}$ and
let $\mathcal{U}(\lambda),$ $0<\lambda\leq 1,$ denote the set of all
$f\in{\mathcal{A}}$ satisfying the condition

(1)
$\left|\left(\frac{z}{f(z)}\right)^{2}f^{\prime}(z)-1\right|<\lambda\qquad(z\in{\mathbb{D}}).$

For $\lambda=1$ we put $\mathcal{U}(1)=\mathcal{U}$. More about these classes
can be found in [5, 6, 7, 8, 10].

In [7] it was claimed that all functions $f$ from $\mathcal{U}(\lambda)$
satisfy

(2) $\frac{f(z)}{z}\prec\frac{1}{(1+z)(1+\lambda z)}.$

Here ”$\prec$” denotes the usual subordination, i.e., $F(z)\prec G(z)$, for
$f$ and $G$ being analytic functions in ${\mathbb{D}}$, means that there
exists function $\omega(z)$, also analytic in $\|D$, such that $\omega(0)=0$
and $|\omega(z)|<1$ for all $z\in{\mathbb{D}}$. Recently, in [3], the author
gave a counterexample that subordination (2) is not necessarily satisfied by
all functions from $\mathcal{U}(\lambda)$.

For the functions $f$ from $\mathcal{U}(\lambda)$ satisfying subordination (2)
we have

(3) $\frac{f(z)}{z}=\frac{1}{(1-\omega(z))(1-\lambda\omega(z))},$

where $\omega$ is a Schwarz function, i.e., it is analytic in ${\mathbb{D}}$,
$\omega(0)=0$ and $|\omega(z)|<1,z\in{\mathbb{D}}$. Let’s put

$\omega(z)=c_{1}z+c_{2}z^{2}+\cdots.$

Later on we will use the fact due to Schur [9] that $|c_{2}|\leq
1-|c_{1}|^{2}$ (can be found also in Carlson’s work [1]).

Further, the inequality (1) for the function $f$ from ${\mathcal{U}}(\lambda)$
can be rewritten in the following, equivalent, form

$\left|\frac{z}{f(z)}-z\left(\frac{z}{f(z)}\right)^{\prime}-1\right|<\lambda\qquad(z\in{\mathbb{D}})$

and further

$\left|\frac{z}{f(z)}-z\left(\frac{z}{f(z)}\right)^{\prime}-1\right|\leq\lambda|z|^{2}\qquad(z\in{\mathbb{D}}).$

From here, after some calculations we obtain

$|(1+\lambda)c_{2}-\lambda c_{1}^{2}+(2(1+\lambda)c_{3}-4\lambda
c_{1}c_{2})z+\cdots|\leq\lambda$

for all $z\in{\mathbb{D}},$ and next,

(4) $|(1+\lambda)c_{2}-\lambda
c_{1}^{2}|\leq\lambda,\quad|2(1+\lambda)c_{3}-4\lambda
c_{1}c_{2}|\leq\lambda-\frac{1}{\lambda}|(1+\lambda)c_{2}-\lambda
c_{1}^{2}|^{2},$

for all $z\in{\mathbb{D}}.$ The last inequality follows from the result of
Carlson for the second coefficient of Schwarz functions cited above.

If $f\in\mathcal{S}$ and

(5) $f(z)=z+a_{2}z^{2}+a_{3}z^{3}+\cdots,$

then the inverse of $f$ has an expansion

(6) $f^{-1}(w)=w+A_{2}w^{2}+A_{3}w^{3}+\cdots$

near the origin (or precisely at least in $|w|<\frac{1}{4}$). By using the
identity $f(f^{-1})=w$ and the representations for the functions $f$ and
$f^{-1}$, we can obtain the next relations

(7) $\begin{array}[]{l}A_{2}=-a_{2},\\\ A_{3}=-a_{3}+2a_{2}^{2},\\\
A_{4}=-a_{4}+5a_{2}a_{3}-5a_{2}^{3}.\end{array}$

The main result of this paper are the sharp upper bounds for the modulus of
these three initial coefficients of $f^{-1}$.

######  Theorem 1.

Let $f\in\mathcal{U}(\lambda)$, $0<\lambda\leq 1$, satisfies subordination
(2), and let $f$ and $f^{-1}$ be given by (5) and (6), respectively. Then

$\begin{array}[]{l}|A_{2}|\leq 1+\lambda,\\\ |A_{3}|\leq
1+3\lambda+\lambda^{2},\\\
|A_{4}|\leq(1+\lambda)(1+5\lambda+\lambda^{2}).\end{array}$

All these results are best possible.

###### Proof.

For $f\in\mathcal{U}(\lambda)$, from the relation (3) we have (see [4], [7])

(8)
$\sum_{n=1}^{\infty}a_{n+1}z^{n}=\sum_{n=1}^{\infty}\frac{1-\lambda^{n+1}}{1-\lambda}\omega^{n}(z).$

If we put $\omega(z)=c_{1}z+c_{2}z^{2}+\cdots$, then from (8) by comparing the
coefficients we obtain

(9) $\left\\{\begin{array}[]{l}a_{2}=(1+\lambda)c_{1},\\\
a_{3}=(1+\lambda)c_{2}+(1+\lambda+\lambda^{2})c_{1}^{2},\\\
a_{4}=(1+\lambda)c_{3}+2(1+\lambda+\lambda^{2})c_{1}c_{2}+(1+\lambda+\lambda^{2}+\lambda^{3})c_{1}^{3}.\end{array}\right.$

Using (7) and (9) we also have

(10) $\left\\{\begin{array}[]{l}A_{2}=-(1+\lambda)c_{1},\\\
A_{3}=-(1+\lambda)c_{2}+(1+3\lambda+\lambda^{2})c_{1}^{2},\\\
A_{4}=-(1+\lambda)c_{3}+(3+8\lambda+3\lambda^{2})c_{1}c_{2}-(1+\lambda)(1+5\lambda+\lambda^{2})c_{1}^{3}.\end{array}\right.$

Since $|c_{1}|\leq 1$ and $|c_{2}|\leq 1-|c_{1}|^{2}$, from (10) we receive

$|A_{2}|\leq 1+\lambda$

and

$\begin{split}|A_{3}|&\leq(1+\lambda)|c_{2}|+(1+3\lambda+\lambda^{2})|c_{1}|^{2}\\\
&\leq(1+\lambda)(1-|c_{1}|^{2})+(1+3\lambda+\lambda^{2})|c_{1}|^{2}\\\
&\leq(1+\lambda)+(2\lambda+\lambda^{2})|c_{1}|^{2}\\\ &\leq
1+3\lambda+\lambda^{2}.\end{split}$

Also, from (10) we obtain

$A_{4}=-\frac{1}{2}\left[2(1+\lambda)c_{3}-4\lambda
c_{1}c_{2}-6(1+\lambda)c_{1}((1+\lambda)c_{2}-\lambda
c_{1}^{2})+2(1+\lambda)^{3}c_{1}^{3}\right],$

and from here, by applying (4),

$\begin{split}|A_{4}|&\leq\frac{1}{2}\left[|2(1+\lambda)c_{3}-4\lambda
c_{1}c_{2}|+6(1+\lambda)|c_{1}||(1+\lambda)c_{2}-\lambda
c_{1}^{2}|+2(1+\lambda)^{3}|c_{1}|^{3}\right]\\\
&\leq\frac{1}{2}\left[\lambda-\frac{1}{\lambda}|(1+\lambda)c_{2}-\lambda
c_{1}^{2}|^{2}+6(1+\lambda)|c_{1}||(1+\lambda)c_{2}-\lambda
c_{1}^{2}|+2(1+\lambda)^{3}|c_{1}|^{3}\right]\\\
&=\frac{1}{2}\left[\lambda-\frac{1}{\lambda}t^{2}+6(1+\lambda)|c_{1}|t+2(1+\lambda)^{3}|c_{1}|^{3}\right]\\\
&=:\frac{1}{2}h(t),\end{split}$

where $t=|(1+\lambda)c_{2}-\lambda c_{1}^{2}|$ and $0\leq t\leq\lambda,$ since

$|(1+\lambda)c_{2}-\lambda
c_{1}^{2}|\leq(1+\lambda)|c_{2}|+\lambda|c_{1}|^{2}\leq(1+\lambda)(1-|c_{1}|^{2})+\lambda|c_{1}|^{2}=\lambda.$

As for the maximal value of function $h$, we consider two cases:

Case 1: When $0\leq|c_{1}|\leq\frac{1}{3(1+\lambda)}$ the function $h$ attains
its maximum for $t_{0}=3(1+\lambda)\lambda|c_{1}|$ and we have

$h(t_{0})\leq\lambda+27\lambda(1+\lambda)^{2}|c_{1}|^{2}+2(1+\lambda)^{3}|c_{1}|^{3}\leq
4\lambda+\frac{2}{27},$

i.e.,

$|A_{4}|\leq 2\lambda+\frac{1}{27}.$

Case 2: For $\frac{1}{3(1+\lambda)}\leq|c_{1}|\leq 1$, the function $h$
attains its maximum for $t=\lambda$ and we have

$h(t)\leq 6(1+\lambda)\lambda|c_{1}|+2(1+\lambda)^{3}|c_{1}|^{3}\leq
2(1+\lambda)(1+5\lambda+\lambda^{2}),$

when $0\leq t\leq\lambda.$ So,

$|A_{4}|\leq(1+\lambda)(1+5\lambda+\lambda^{2}).$

From cases 1 and 2, since
$(1+\lambda)(1+5\lambda+\lambda^{2})>2\lambda+\frac{1}{27}$ when
$0<\lambda\leq 1$, we receive the estimate for $|A_{4}|$.

For the proof of sharpness of the theorem, let consider the function

$w=f_{\lambda}(z)=\frac{z}{(1-z)(1-\lambda z)}.$

Then

(11)
$z=f_{\lambda}^{-1}(w)=w-(1+\lambda)w^{2}+(1+3\lambda+\lambda^{2})w^{3}-(1+\lambda)(1+5\lambda+\lambda^{2})w^{4}-\cdots,$

which shows that our results are the best possible. ∎

Note that for $\lambda=1$ in Theorem 1 we have the estimates for class
$\mathcal{U}$ and in that case the inverse of the Koebe function is extremal,
as for the class $\mathcal{S}$ (see, for example Goodman’s book, Vol II,
p.205, [2]).

In the next theorem we study the Fekete-Szegő functional for the inverse
functions of the class $\mathcal{U}(\lambda)$. Namely, we have

######  Theorem 2.

For the inverse functions of functions from $\mathcal{U}(\lambda)$,
$0<\lambda\leq 1$, satisfying subordination (2), we have

$|A_{3}-\mu A_{2}^{2}|\leq\lambda+|1-\mu|(1+\lambda)^{2},$

where $\mu$ is complex number. The result is sharp for $0\leq\mu\leq 1$.

###### Proof.

From the relations (10) and (4) we obtain

$\begin{split}|A_{3}-\mu
A_{2}^{2}|&=|-(1+\lambda)c_{2}+(1+3\lambda+\lambda^{2})c_{1}^{2}-\mu(1+\lambda)^{2}c_{1}^{2}|\\\
&=|-((1+\lambda)c_{2}-\lambda c_{1}^{2})+(1-\mu)(1+\lambda)^{2}c_{1}^{2}|\\\
&\leq|(1+\lambda)c_{2}-\lambda c_{1}^{2}|+|1-\mu|(1+\lambda)^{2}|c_{1}|^{2}\\\
&\leq\lambda+|1-\mu|(1+\lambda)^{2}.\end{split}$

The sharpness of the estimate in the case when $0\leq\mu\leq 1$ follows from
the function $f_{\lambda}^{-1}$ defined by (11). ∎

## Funding

The authors did not receive any funding for the research published in this
article.

## Conflict of Interest

The authors declare that they have no conflict of interest.

## Ethical approval

This article does not contain any studies with human participants or animals
performed by any of the authors.

## References

  * [1] F. Carlson, Sur les coefficients d’une fonction bornée dans le cercle unité, Ark. Mat. Astr. Fys. 27A(1) (1940), 8 pp.
  * [2] A.W. Goodman: Univalent functions, Vol. 1-2, Mariner, Tampa, Florida, 1983.
  * [3] Li L., Ponnusamy S., Wirths K.J., Relations of the class ${\mathcal{U}}(\lambda)$ to other families of functions, arXiv:2104.05346.
  * [4] M. Obradović, Starlikeness and certain class of rational functions, Math. Nachr., 175:263–268, 1995.
  * [5] M. Obradović, S. Ponnusamy: New criteria and distortion theorems for univalent functions, Complex Variables Theory Appl. 44(2001), 173–191. (Also Reports of the Department of Mathematics, Preprint 190, June 1998, University of Helsinki, Finland).
  * [6] M. Obradović, S. Ponnusamy, On the class $\mathcal{U}$, Proc. 21st Annual Conference of the Jammu Math. Soc. and a National Seminar on Analysis and its Application, 11-26, 2011.
  * [7] M. Obradović, S. Ponnusamy, K. J. Wirths, Geometric studies on the class $\mathcal{U}(\lambda)$. Bull. Malays. Math. Sci. Soc. 39 (2016), no. 3, 1259–1284.
  * [8] M. Obradović and N. Tuneski, Some properties of the class $\mathcal{U}$, Ann. Univ. Mariae Curie-Skłodowska, Vol. 73, no 1, sectio A, (2019), 49-56.
  * [9] J. Schur, Über Potenzreihen, die im Innern des Einheitskreises beschränkt sind. (German), J. Reine Angew. Math. 147 (1917), 205–232.
  * [10] D.K. Thomas, N. Tuneski, A. Vasudevarao, Univalent functions. A primer. De Gruyter Studies in Mathematics, 69. De Gruyter, Berlin, 2018.


# Design Verification of the Quantum Control Stack

Seyed Amir Alavi  Riverlane Research Ltd, Cambridge, UK.  Samin Ishtiaq
Riverlane Research Ltd, Cambridge, UK.  Nick Johnson  Riverlane Research Ltd,
Cambridge, UK.  Rojalin Mishra  Riverlane Research Ltd, Cambridge, UK.
Dwaraka O N  Riverlane Research Ltd, Cambridge, UK.  Asher Pearl  Riverlane
Research Ltd, Cambridge, UK.  Jan Snoeijs 111Authors listed in alphabetical
order. Riverlane Research Ltd, Cambridge, UK.

###### Abstract

This paper describes the verification of the classical software and hardware
stack that is used to control cold atom- and superconducting-based quantum
computing hardware. The paper serves both as an introduction to quantum
computing and to how classical device verification techniques can be employed
there. Two main challenges in building a quantum control stack are generating
precise deterministic-timing operations at the edge and scaled-out processing
in the middle layer. Both challenges are to do with a certain kind of
functional performance correctness. And, as usual, the design lives under
tight power, memory and latency constraints. The quantum control stack is a
complex interaction of algorithms, software runtimes and digital hardware. We
take inspiration from modern software approaches to engineering, such as
continuous integration and hardware automation, to quickly ship experimental
features to customers in the field.

##  1 Introduction

The Church-Turing thesis states that all computers perform the same up to a
polynomial factor in execution speed. Quantum computers (QC) are the only
devices known to violate this thesis, promising a quantum speedup over
classical computers that may permit solutions to hitherto intractable problems
in science and mathematics. Quantum mechanics is a stranger place than the
everyday Newtonian world of state machines. In classical computing, the unit
of information, the bit, can be in one of the two states, 0 or 1. The quantum
equivalent to the bit is the qubit, representing superposition,
$\alpha\ket{0}+\beta\ket{1}$, where $\alpha$ and $\beta$ are complex numbers.
Consequently, information stored in a quantum computer grows exponentially
with every additional qubit. Moreover, the interconnected nature of the state
space for two or more qubits allows entangled states to be generated that are
impossible to produce with classical bits. These characteristics are expected
to enable quantum computers to tackle problems that are computationally hard
for classical algorithms, such as factoring large numbers or simulating
quantum interactions with high accuracy. Famous example applications are
breaking the RSA public-private key system security and cracking Bitcoin
encryption, or modelling chemical processes of industrial relevance such as
catalysis in the Haber process using the iron-molybdenum cofactor (FeMo-co)
[MH22].

Much research is underway on building the first quantum computers. A diverse
range of qubit technologies exist, and several approaches have demonstrated
high-fidelity quantum operations with the potential to scale up to large
numbers of qubits. Some examples are trapped ions confined within electric
fields, and superconducting circuits held at extremely low temperatures
(Section 3). However, qubits are extremely sensitive both to the environment
and to the signals used to control them. These control signals, consisting of
highly-tuned laser and radiofrequency (RF) electronic pulses, require high-
precision manipulation of the amplitude, frequency and phase of the waveforms
(Section 4). The more accurately we can manipulate these parameters, the
better we can control the quantum state. If we were only talking to digital
designers, we might conspiratorially admit that, while better qubits are the
foundation of quantum computing, better digital control of the qubits is a big
part of making quantum computing useful. (Just as a software (SW) person would
say that SW is what makes classical hardware (HW) useful!)

To overcome the fragility of individual qubits, quantum error correction (QEC)
is implemented by forming distributed ‘logical’ qubits. Each logical qubit is
constructed by encoding the quantum state over multiple physical ‘data’
qubits. In practice, these physical qubits are, for example, individual
trapped ions. Since direct measurements of the data qubits are forbidden due
to the destructive effect on the quantum state, additional so-called
‘auxiliary’ qubits are introduced which can interact with the data qubits to
yield information about their underlying states via parity checks. In this
way, errors such as bit flips can be detected (to within a certain
confidence). The surface code is one of the leading encoding schemes for fault
tolerant (FT) QC [Lit19]. The job of a quantum error correction algorithm is
to accurately infer the states of the data qubits from parity check
measurements made only on the auxiliaries, and then, once armed with this
information, to trigger operations on the data qubits that either preserve or
reset their states. Owing to short quantum coherence lifetimes (typically ms
for ion qubits, $\mu$s for superconducting qubits), this procedure places
challenging demands on the timing accuracy and feedback responsiveness of the
control system.

The control stack operates under tight power, memory, and latency constraints.
But, because of the requirement for accurate RF signals, there is also an
important functional performance correctness criteria in design verification
(Section 5). These would be challenging problems in any area but, as the
quantum computing industry moves from university labs to deep-tech scale-ups,
requirements change very frequently. Design verification now has the role to
quickly qualify the current design in a situation where there are many moving
parts of the full SW and HW stack. We take a more agile, SW-inspired approach
to full-stack device verification and shipping (Section 5).

##  2 Related Work

Google and ETH detail how the surface code is implemented on superconducting
systems [AI23, Kri+22]. Previous work at Delft is experimental [Kri+22] and
has filled-out some of the HW micro-architecture gaps to implement surface
code-based fault-tolerant computing [Fu+17]. The papers we cite here are
predominantly from large, well-organized research labs where the customer and
the design engineering are the same team. These organizations have single-
mission funding and a fixed set of internal-only requirements. The papers
describe gigantic feats of scientific achievement, but ones that cannot easily
be replicated outside that organization. The papers do not describe
replicable, automated design verification.

##  3 Quantum Hardware

A proliferation of emerging quantum computing hardware platforms exist,
including photonics, silicon spin qubits, and NV centres in diamond. In this
paper we focus our attention on trapped-ion and superconducting qubits. In a
trapped-ion architecture, the qubits are single atomic ions carrying an
overall positive electric charge. The ion is trapped by a time-varying
electric field that is generated by the ion-trap device itself – usually
microfabricated onto a chip by depositing metal electrode layers onto an
insulating substrate like silicon dioxide. Typically, the ion trap chip is the
size of a postage stamp and the ion is held above the surface at a height of
around 100 $\mu$m – approximately the width of a human hair. Laser cooling
techniques are used to bring the effective temperature of the ion to a few
$\mu$K. The qubit states $\ket{0}$ and $\ket{1}$ are chosen to be a ground
state and an excited state of the electronic energy levels within the ion.
Control over the quantum state is achieved using pulsed laser- and microwave-
fields with modulated amplitude, frequency and phase.

Superconducting qubits combine the operating principles of resonant LC
circuits with the quantum behaviour of a Josephson junction. Quantum circuits
containing many superconducting qubits can be fabricated onto microchips that
operate at mK temperatures within a 3He/4He dilution refrigerator. This ‘dil
fridge’ is a much-photographed device and looks like a gold-plated chandelier.
A mix of microwave frequency, RF and DC control signals are used to manipulate
the quantum states of superconducting qubits. IBM and Google have focused to
develop this technology as part of their quantum computing research efforts.

##  4 A Control System

Previously, we said that quantum states are controlled using pulsed laser or
electronic signals with modulated amplitude, frequency and phase. These
signals have to be transmitted with low-latency and high timing-accuracy. To
begin to do a basic operation like initialising a qubit into a particular
state, we need to sequence a set of pulses to run with at least ns timing
accuracy. The definition of this sequence can be written in a programming
language like OpenQASM’s OpenPulse [CA20]. The definition is then compiled
into instructions sent to a hardware execution unit that controls digital and
RF signal generators. At runtime, this execution unit calculates and transmits
the signals with clock accuracy. Timing-determinism is implemented by the
execution unit queuing instructions up for the signal generators and firing
them from the queue at the correct time. In practice, each execution unit
controls 10s of such signal generators, and there will be 10s, 100s, even
1000s (for FT QC) of these execution units. Early in the design cycle, a set
of FPGAs is the obvious choice of lego-bricks to build this system. The set of
FPGAs are coordinated and synchronised at configuration time via software, and
at run time via hardware signals. We know that cost pressures and increased
specialisation will cause a move to more dedicated custom hardware, at the
price of reduced flexibility of configuration/design re-spins. Our control
system is currently implemented on Xilinx RFSoC ZCU111 FPGAs.

These pulse sequences are the lowest level of control. A set of pulses can be
arranged into higher-level operations like qubit initialisation (init0, init1)
and physical qubit gates (X, H). A quantum hardware system often requires
early-morning calibration to discover the most accurate definitions of these
higher-level operations. For example, there may be drifts in parameters such
as frequency or amplitude over time, requiring compensation or re-calibration.
Typical calibration workflows in a QC lab will involve scans over a range of
control frequencies or power levels, to pinpoint the optimum qubit response.
One of the most common scanning procedures is used to drive the qubit between
the $\ket{0}$ state and the $\ket{1}$ state (and back again), to identify a
characteristic oscillation period for the qubit. These are known as Rabi
oscillations and the procedure is useful for calibrating the pulses which form
gates when applied to the qubit.

Once we have pulse-level definitions of physical gates, then these can be
abstracted again to define a physical circuit to implement error correction.
QEC is just a certain quantum circuit run over and over, which involves gates
and measurements. In practice, the control system for FT QC will also include
modules on logical state management, noise modelling, etc.

##  5 Control System Verification

We have built three flows to implement completeness and redundancy for full-
stack verification. These flows use all the classical verification techniques
we have in our armour to ensure full-system functional and performance (timing
determinate) correctness. The first flow (Section 5.1) is a very traditional
UVM-based verification. The second flow (Section 5.2) is a SystemC model of
the top-level combined with parts of the SW stack. The third flow (Section
5.3) is a pretty faithful lab mock-up of the actual in-field SW and HW.

We have a continuous integration (CI) system (Section 5.4) that kicks off
tests on both source and, transitively, on upstream/dependent repos. The flow
aims to ensure that a good version of the entire stack is always ready for
release. This system is designed to be automatic, discovering a “good
frontier” that is always ready for release across the set of source git repos.

###  5.1 Top/Block level UVM Verification

The first flow is a very traditional top- and block-level UVM-based
verification. This flow tests the custom HW using SystemVerilog simulation and
formal tools. The flow is cycle-accurate and allows full debugging of the
design but is slower than real hardware and can’t be used to do full-stack
verification. The architecture of the control system has both DSP and Digital
blocks. The critical blocks have been prototyped as functional SystemC or
Python implementations and are used as golden models.

To verify a single block of the quantum control stack using UVM, constrained
randomized data is driven from the top-level using multiple sequences in
parallel, which helps in making sure that data that flows throughout the stack
is always consistent. The integrity of data generated is checked in UVM using
scoreboards and reference models. Scoreboards in the test bench are used for
all the digital blocks of the architecture. The data generated by the
testbench and RTL are compared for correctness.

The DSP reference models define the shape and spectral purity of the generated
sinusoid. The models have reals as their native number representation. One of
the challenges has been keeping tabs on the number representation formats in
comparing the reference model to the RTL implementation. In our design flow
for one of the signal generation blocks, the Python reference model uses
floating point numbers, while the RTL implementation uses normalized fixed
point numbers. There are a variety of different formats in the data processing
chain, and we have convertors between them to verify the RTL. We have needed
to strongly specify the number of fractional digits, for instance; and to
check how different tools store and transmit fixed/floating point numbers. One
of the flows, illustrated in Figure 1 below, also includes several conversion
utilities: shown here are a fixed-to-floating converter, and a convertor to
represent the config to the DUT’s config RAMs.

Figure 1: Using a reference model to check a DSP implementation.

The expected and actual output digital samples are compared and checked to see
that they are within the allowed threshold. In Figure 1 the first two
Comparator graphs are the red/actual and the blue/expected pulses (they are
very close, and the blue expected completely overlaps the red actual), and the
error bars. The last two Comparator graphs are the blue/expected and
red/actual spectral graphs for the output. We applied Blackman windowing to
the expected and actual digital data. As the graphs show, the tones both
appear at driven frequency and with no unexpected harmonics within the
frequency band. Only checking the data integrity would not be sufficient for
any design. The UVM testbench makes sure that the design is cycle accurate.
Cycle accuracy in the testbench is checked by assertions to measure latency
between inputs and outputs of each block. In Figure 2 below, some validity
assertions are shown for one of the signal generation blocks.

Figure 2: SignalGen block valid timing assertions.

We use formal verification (FV) extensively to verify the interconnects of our
architecture.

The completeness of verification is measured by checking the functional and
code coverage. Functional coverage is checked with cover-points and coverage
bins programmed for each individual block. Code coverage is checked by running
multiple regressions and merging all data collected in each run. We use formal
verification to also speed up functional and code coverage, and for extracting
cover-points and eliminating dead code.

###  5.2 Top-level SystemC Model

In this section, we describe the second verification flow. This consists of a
SystemC [Ghe05] model of the top-level — with some non-critical blocks being
replaced by functional models — combined with a subset of the SW stack.
Including parts of the SW stack means that we are now running more of the
full-stack system in simulation and can run user-level programs. Even though
it is clock-level accurate, we get a factor improvement over the HW
simulators, enabling a faster turnaround for early bug discovery.

Figure 3: SystemC/C++ simulator SW stack.

The SW stack is shown in Figure 3. The bottom layer is the Verilated top-level
HW block in a SystemC wrapper. This layer is connected to a SystemC
transaction layer modelling (TLM) interface to execute Advanced eXtensible
Interface (AXI) bus transactions to communicate with the blocks. From this
layer, the same hardware abstraction layer (HAL) that is used in production
can be used to interface with the HW blocks. This level of abstraction brings
a lot of benefits such as testing production SW and easier maintenance of
verification, control and runtime code. At the highest level, the simulator
exposes both a SystemC and control API for execution of the simulation and
post-processing the log the simulation.

A Verilated model is very fast compared to running the design using the usual
SystemVerilog simulators due to the speed gain from native compiled C++. To
further improve the simulation speed, we have enabled multithreading in the
verilated model. This boosts the simulation speed by the number of available
processor cores on the machine. Although this feature is very useful, it has a
major limitation: the number of threads have to be fixed during Verilator
compilation (converting SystemVerilog to C++) time, which doesn’t support
optimizing the number of threads at runtime. The user API interface for the
simulator provides basic operational interface, such as starting, stopping,
signals to be recorded, initial configuration of the block, etc. The API
interacts with the runtime management system to synchronize operations between
different HW blocks and SW components of the HAL.

###  5.3 On-target automated tests in HW Lab

Verifying the functionality of the control system components on the target HW
is a crucial step to confirm actual expected behaviour of the simulation
results. In this step, all of the SW and HW components are deployed on the
target. We have custom tooling that runs integration tests automatically on
the target: it executes the test cases on the target, and captures the results
on the physical ports using the allocated data acquisition device, in this
case a network-controllable oscilloscope. This setup is shown in Figure 4

Figure 4: On-target HW automated tests setup.

There are limitations to be considered when designing the HW automated tests,
which are mainly the constraints on the data acquisition device such as the
number of available ports, and available memory/bandwidth for data retrieval.
This leads to a trade-off between resolution and length of sampling. Another
complexity worth mentioning here is the dynamic nature of the HW blocks
integrated into the FPGAs, which requires continuous change in the HW
connections and data capturing configuration. Although this step gets
complicated in practice, it provides valuable insight on performance of the
components leading to reduced risk of bugs or other issues after product
releases.

###  5.4 Full-stack CI

The source code for the control system is stored over nine git repos. Each
repo is logically contained in the sense that all the FPGA SystemVerilog
source is stored in one repo, all the low-level embedded software is stored in
one repo, etc. Each repo has it’s own set of testing and verification
artifacts and flows. When commits on a feature branch are ready to be merged
into the repo’s main branch, a full CI runs on the new branch.

Figure 5: CI Good Frontier.

This isolated set up ignores the fact that the repos are the source of
artifacts that build upon each other. This is true in both the source sense (a
C++ module dependent upon the source C++ module in another repo) and in the
binary sense (a source Python module dependent upon a C++ compiled binary)
too. In Figure 5 above, the history of each repo is shown going up; the red
arrows indicate a dependency (via git modules, package managers or manual
installs). In our experience, interesting bugs occur when several non-trivial
repos’ artifacts are run together. This makes sense intuitively: we think we
have completely understood and tested a module, but its interactions with
other modules in a larger sub-system bring out all the hidden assumptions we
have on the module’s interfaces. So, the earlier “full stack” integration can
be done, the sooner these critical late bugs can be found, and the quicker the
turnaround for new features.

The way we run full-stack integration testing is as follows. Every repo has a
CI-passing branch that points at the latest commit close to main (could be
main) at which all the repos work well together. The CI-passing pointers form
a “good frontier”, illustrated by the blue border in Figure 5 above, that is
always ready for release across all nine git repos. If CI passes on repo A’s
main, then A’s CI-passing branch is updated to main. All submodules
automatically track head of CI-passing which is the latest point that all
integration tests for all submodules passed.

The working model here is that an engineer checks out repo A’s main. All of
A’s submodules track CI-passing, and are automatically checked out at a
working commit that works with the head of main. The engineer makes a new
feat-br off main, does some work and makes a PR. On creation of the PR: (1) CI
on repo A tries to test A’s feat-br with submodule B’s CI-passing; (2) CI on
repo A tries to update submodule B’s ci-passing to head of main and tries to
run integration tests between A on new-branch and B. At least one of (1) or
(2) should pass. If both fail then there’s a problem, and the PR shouldn’t be
merged. If (2) fails but (1) passes, that serves as a good ongoing indication
that work is needed to fix integration between A and B without immediately
breaking A.

After the merge of the PR, full-stack CI checks out all submodules at head of
main, and runs integration tests performing any updates to CI-passing on
submodules if all integration tests pass. If any fail, CI-passing on all
submodules are kept at the older commits that worked. This ensures that if A
is itself a submodule of some other repo R, we don’t end up in a situation
where we’ve updated the ci-passing on B, but the head of main on A doesn’t
work with R, and so CI-passing on A doesn’t change, which would cause CI-
passing to no longer reflect a set of commits that all work together.

This model ensures that CI-passing is close to or at the head of main for all
the submodules (if it isn’t then that’s indicative of a larger problem that
needs to be fixed before release). By definition, CI-passing is “the latest
set of commits which work together correctly”, so should is always releasable.
We check out CI-passing for our release commits. Using this methodology, we
are able to release every two-week sprint.

##  6 Further Work

We have described the design verification flow for a quantum control system.
We see this as the 1st generation of control systems. There are two large
design trajectories in our current work. First, scaling out the system to 10s,
100s, 1000s of qubits in anticipation of fault tolerant quantum computing. We
are working to analyse and model functional, performance, protocol, memory,
etc requirements of scaled-out control system for different quantum hardware.
Second, portability over this different quantum hardware. How can we keep the
design configurable over different target systems and hardware, and how can we
verify over these configurations? It is quite likely that each generation
might be radically different from the previous one. So, we are working through
the implications for sub-system and full-system design verification. In
typical HW development, old source (not necessarily module) code is salvaged
and re-used. But modern agile ways of working provide good guides to more sure
ways of qualifying large-scale complex design.

## References

  * [Ghe05] F. Ghenassia  “Transaction Level Modeling with SystemC”, 2005
  * [Fu+17] X. Fu et al.  “An experimental microarchitecture for a superconducting quantum processor”  In _50th Annual IEEE/ACM International Symposium on Microarchitecture_ , 2017
  * [Lit19] D Litinski  “A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery”, 2019
  * [CA20] L. Capelluto and T. Alexander  “OpenPulse: Software for Experimental Physicists in Quantum Computing”  In _APS March_ , 2020
  * [Kri+22] S. Krinner et al.  “Realizing repeated quantum error correction in a distance-three surface code”, 2022, pp. 669–674
  * [MH22] S. M. and W.. Hensinger  “The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime”  In _AVS Quantum Science_ , 2022
  * [AI23] Google AI  “Suppressing quantum errors by scaling a surface code logical qubit”, 2023, pp. 676–681