7480

# On a generalization of the three spectral inverse problem

O. P. Boyko  O. M. Martynyuk  V. M. Pivovarchik  South Ukrainian National
Pedagogical University, 26 Staroportofrankivs’ka, Odesa, 65020, Ukraine
<EMAIL_ADDRESS>On occasion of Yu. M. Berezansky anniversary

(Date: 22/01/2015)

###### Abstract.

We consider a generalization of the three spectral inverse problem, that is,
for given spectrum of the Dirichlet-Dirichlet problem (the Sturm-Liouville
problem with Dirichlet conditions at both ends) on the whole interval $[0,a]$,
parts of spectra of the Dirichlet-Neumann and Dirichlet-Dirichlet problems on
$[0,a/2]$ and parts of spectra of the Dirichlet-Newman and Dirichlet-Dirichlet
problems on $[a/2,a]$, we find the potential of the Sturm-Liouville equation.

###### Key words and phrases:

Sturm-Liouville equation, Dirichlet boundary condition, Neumann boundary
condition, Marchenko equation, Lagrange interpolation series, sine-type
function, Nevanlinna function.

###### 2000 Mathematics Subject Classification:

Primary 34A55; Secondary 34B24

##  1\. Introduction

The theory of direct and inverse spectral problems is based on the base of
classical results of Yu. M. Berezansky, V. A. Marchenko, M. G. Krein, B. M.
Levitan (see [1], [15], [12], [14]). The so-called half-inverse problem and
three spectral problem are branches of this theory.

In the present paper we show the relations between the three spectral problem
and the Hochstadt-Lieberman problem. We use the same equation (see equation
(2.9)) and similar methods for recovering the potential in these problems.

Uniqueness of solution for the three spectral problem was considered in many
publications (see [8], [2], [3], [4], [7], [23], [5], [6]), the problem of
existence of its solution has been treated in [21], [18] and [11]. Let us
describe the three spectral problem.

Let $\\{\lambda_{k}\\}_{-\infty,k\not=0}^{\infty}$,
$\\{\nu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}$ and
$\\{\nu_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}$ be the spectra of the
problems

$\left\\{\begin{array}[]{c}-y^{\prime\prime}+q(x)y=\lambda^{2}y,\\\
y(0)=y(a)=0,\end{array}\right.$ (1.1)
$\left\\{\begin{array}[]{c}-y^{\prime\prime}+q(x)y=\lambda^{2}y,\\\
y(0)=y\left(\frac{a}{2}\right)=0,\end{array}\right.$ (1.2)
$\left\\{\begin{array}[]{c}-y^{\prime\prime}+q(x)y=\lambda^{2}y,\\\
y\left(\frac{a}{2}\right)=y(a)=0,\end{array}\right.$ (1.3)

respectively, where $q\in L_{2}(0,a)$ is a real valued function.

It is known [18] that
$\\{\nu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}\cap\\{\nu_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}=\emptyset$
if and only if
$\\{\lambda_{k}\\}_{-\infty,k\not=0}^{\infty}\cap\\{\nu_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}=\emptyset$
if and only if
$\\{\lambda_{k}\\}_{-\infty,k\not=0}^{\infty}\cap\\{\nu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}=\emptyset$.
In this case this three spectra uniquely determine the potential $q$.

Let us consider also the problems

$\left\\{\begin{array}[]{c}-y^{\prime\prime}+q(x)y=\lambda^{2}y,\\\
y(0)=y^{\prime}\left(\frac{a}{2}\right)=0,\end{array}\right.$ (1.4)
$\left\\{\begin{array}[]{c}-y^{\prime\prime}+q(x)y=\lambda^{2}y,\\\
y^{\prime}\left(\frac{a}{2}\right)=y(a)=0\end{array}\right.$ (1.5)

with the spectra denoted by $\\{\mu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}$
and $\\{\mu_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}$, respectively.

It is clear and it will be shown below that
$\\{\mu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}\cap\\{\mu_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}=\emptyset$
if and only if
$\\{\lambda_{k}\\}_{-\infty,k\not=0}^{\infty}\cap\\{\mu_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}=\emptyset$
if and only if
$\\{\lambda_{k}\\}_{-\infty,k\not=0}^{\infty}\cap\\{\mu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}=\emptyset$.
In this case these three spectra
$\\{\lambda_{k}\\}_{-\infty,k\not=0}^{\infty}$,
$\\{\nu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}$ and
$\\{\nu_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}$ uniquely determine the
potential $q(x)$ on $[0,a]$.

Let us consider another three spectral problem: given
$\\{\lambda_{k}\\}_{-\infty,k\not=0}^{\infty}$,
$\\{\nu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}$ and
$\\{\mu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}$, find $q$. Since knowledge of
$\\{\mu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}$ and
$\\{\nu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}$ is equivalent to the
knowledge of the projection of $q$ onto $(0,\frac{a}{2})$, this problem is
nothing but the Hochstadt-Lieberman problem [10] (see also [9], [22], [8],
[16], [17]). It is known that these data uniquely determine $q$ on the whole
interval $(0,a)$.

The aim of the present paper is to show that one may use
$\\{\lambda_{k}\\}_{-\infty,k\not=0}^{\infty}$ and certain parts of the
spectra $\\{\mu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}$,
$\\{\mu_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}$
$\\{\nu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}$ and
$\\{\nu_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}$ to determine $q$. Namely,
under certain conditions, if the spectrum
$\\{\lambda_{k}\\}_{-\infty,k\not=0}^{\infty}$ is given, the eigenvalues
$\\{\nu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}$ and
$\\{\nu_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}$ are given not all but
excluding a finite number $2n_{1}$ of $\nu_{k}^{(1)}$s and a finite number
$2n_{2}$ of $\nu_{k}^{(2)}$s then it is possible to use $2n_{1}$ eigenvalues
$\mu_{k}^{(2)}$ and $2n_{2}$ eigenvalues $\mu_{k}^{(1)}$ instead to determine
$q$ on $(0,a)$.

##  2\. Main result

Let us rewrite problem (1.1) as follows

$\displaystyle-y_{j}^{\prime\prime}+q_{j}(x)y_{j}=\lambda^{2}y_{j},\quad
x\in\left[0,a/2\right],\quad j=1,2,$ (2.1) $\displaystyle y_{1}(0)=0,$ (2.2)
$\displaystyle y_{2}(0)=0,$ (2.3) $\displaystyle
y_{1}\left(a/2\right)=y_{2}\left(a/2\right),$ (2.4) $\displaystyle
y_{1}^{\prime}(a/2)+y_{2}^{\prime}(a/2)=0.$ (2.5)

We rewrite problems (1.2) and (1.3) as

$\left\\{\begin{array}[]{c}-y_{j}^{\prime\prime}+q_{j}(x)y_{j}=\lambda^{2}y_{j},\
\ x\in\left(0,a/2\right),\\\
y_{j}(0)=y_{j}\left(a/2\right)=0,\end{array}\right.\quad j=1,2.$ (2.6)

Also we rewrite (1.4) and (1.5) as

$\left\\{\begin{array}[]{c}-y_{j}^{\prime\prime}+q_{j}(x)y_{j}=\lambda^{2}y_{j},\
\ x\in\left(0,a/2\right),\\\
y_{j}(0)=y_{j}^{\prime}\left(a/2\right)=0,\end{array}\right.\quad j=1,2.$
(2.7)

Definition 2.1. ([24]). ${\mathcal{L}}^{a}$ is the Paley-Wiener class of
entire functions of exponential type $\leq a$ which belong to
$L_{2}(-\infty,\infty)$ for real $\lambda$.

By the Paley-Wiener theorem ${\mathcal{L}}^{a}$-functions are the Fourier
images of all square summable functions supported on $[-a,a]$.

Let us denote by $s_{j}(\lambda,x)$ the solution of the Sturm-Liouville
equation (2.1) which satisfies the conditions $s_{j}(\lambda,0)=0$,
$s_{j}^{\prime}(\lambda,0)=1$. The spectra
$\\{\nu_{k}^{(j)}\\}_{-\infty,k\not=0}^{\infty}$
($\nu_{-k}^{(j)}=-\nu_{k}^{(j)}$) of problems (2.6) coincide with the sets of
zeros of the characteristic functions

$s_{j}(\lambda,\frac{a}{2})=\frac{\sin\lambda\frac{a}{2}}{\lambda}-A_{j}\frac{\cos\lambda\frac{a}{2}}{\lambda^{2}}+\frac{\psi_{1,j}(\lambda)}{\lambda^{2}},$

where
$A_{j}\mathop{=}\limits^{{\operatorname{def}}}\frac{1}{2}\int_{0}^{\frac{a}{2}}q_{j}(x)\,dx$,
$\psi_{1,j}\in{\mathcal{L}}^{\frac{a}{2}}$. Moreover, $\psi_{1,j}(0)=A_{j}$,
$\psi_{1,j}(-\lambda)=\psi_{1,j}(\lambda)$, otherwise
$s_{j}(\lambda,\frac{a}{2})$ would have a pole at $\lambda=0$.

The spectra $\\{\mu_{k}^{(j)}\\}_{-\infty,k\not=0}^{\infty}$
($\mu_{-k}^{(j)}=-\mu_{k}^{(j)}$) of problems (2.7) coincide with the set of
zeros of

$s_{j}^{\prime}(\lambda,\frac{a}{2})=\cos\lambda\frac{a}{2}+A_{j}\frac{\sin\lambda\frac{a}{2}}{\lambda}+\frac{\psi_{2,j}(\lambda)}{\lambda},$
(2.8)

where $\psi_{2,j}\in{\mathcal{L}}^{\frac{a}{2}}$ and $\psi_{2,j}(0)=0$.

Let us look for the solution of problem (2.1)–(2.5) in the form
$y_{1}=C_{1}s_{1}(\lambda,x)$, $y_{2}=C_{2}s_{2}(\lambda,x)$, where $C_{j}$
are constants. Then (2.4) and (2.5) imply

$C_{1}s_{1}\left(\lambda,a/2\right)=C_{2}s_{2}(\lambda,a/2),$
$C_{1}s_{1}^{\prime}\left(\lambda,a/2\right)+C_{2}s_{2}^{\prime}(\lambda,a/2)=0.$

This system of equations possesses nontrivial solution at the zeros of the
characteristic function

$\omega(\lambda)=s_{1}(\lambda,a/2)s_{2}^{\prime}(\lambda,a/2)+s_{2}(\lambda,a/2)s_{1}^{\prime}(\lambda,a/2).$
(2.9)

The set of zeros $\\{\lambda_{k}\\}_{-\infty,k\not=0}^{\infty}$ of this
function is the spectrum of problem (2.1)–(2.5). Let us notice that problem
(2.1)–(2.5) is the Dirichlet-Dirichlet problem on the whole interval and
therefore

$\omega(\lambda)=\frac{\sin\lambda a}{\lambda}-A_{0}\frac{\cos\lambda
a}{\lambda^{2}}+\frac{\psi_{0}(\lambda)}{\lambda^{2}},$

where $A_{0}=A_{1}+A_{2}$, $\psi_{0}\in{\mathcal{L}}^{a}$. We introduce the
following notation: let
$\\{\theta_{k}^{2}\\}_{k=1}^{\infty}=:\\{(\nu_{k}^{(1)})^{2}\\}_{k=1}^{\infty}\cup\\{(\nu_{k}^{(2)})^{2}\\}_{k=1}^{\infty}$
and $\theta_{-k}=:-\theta_{k}$, $\nu_{-k}^{(j)}=-\nu_{k}^{(j)}$ ($j=1,2$).

The corresponding direct theorem is as follows.

Theorem 2.2. Let a real-valued $q\in L_{2}(0,a)$ then the spectra
$\\{\lambda_{k}\\}_{-\infty,k\not=0}^{\infty}$,
$\\{\nu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}$ and
$\\{\nu_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}$ of problems (1.1), (1.2) and
(1.3) satisfy the conditions:

1\. (see[15])

$\displaystyle\lambda_{k}$ $\displaystyle=\frac{\pi k}{a}+\frac{A_{0}}{\pi
k}+\frac{\beta_{k}^{(0)}}{k},$ (2.10) $\displaystyle\nu_{k}^{(j)}$
$\displaystyle=\frac{2\pi k}{a}+\frac{A_{j}}{\pi
k}+\frac{\beta_{k}^{(j)}}{k},\quad j=1,2,$ $\displaystyle\mu_{k}^{(j)}$
$\displaystyle=\frac{\pi(2k-1)}{a}+\frac{A_{j}}{\pi
k}+\frac{\beta_{k}^{(j)}}{k},\quad j=1,2,$

where $A_{1}=\frac{1}{2}\int_{0}^{\frac{a}{2}}q(x)\,dx$,
$A_{2}=\frac{1}{2}\int_{\frac{a}{2}}^{a}q(x)\,dx$ and $A_{0}=A_{1}+A_{2}$,
$\\{\beta_{k}^{(j)}\\}_{k=1}^{\infty}\in l_{2}$ ($j=0,1,2$).

2\. All the nonzero eigenvalues $\lambda_{k}$, $\nu_{k}^{(1)}$ and
$\nu_{k}^{(2)}$ are simple. If any of them is $0$ then it is of algebraic
multiplicity 2 ([15]).

3\. (see[18])

$-\infty<\lambda_{1}^{2}<\theta_{1}^{2}\leq\lambda_{2}^{2}\leq\theta_{2}^{2}\leq\cdots$

4\. (see[18])

$\lambda_{k}^{2}=\theta_{k}^{2}\quad{\text{if and only
if}}\quad\lambda_{k}^{2}=\theta_{k-1}^{2}.$

We will use the following known result.

Proposition 2.3. (see [15]).

$-\infty<(\mu_{1}^{(j)})^{2}<(\nu_{1}^{(j)})^{2}<(\mu_{2}^{(j)})^{2}<(\nu_{2}^{(j)})^{2}<\cdots$

Definition 2.4. (see e.g. [20]). A meromorphic function $f(z)$ is said to be
an essentially positive Nevanlinna function if

(i) ${\rm Im}z{\rm Im}f(z)>0$ for all nonreal $z$,

(ii) there exists $\beta\in\mathbb{R}$ such that $f(z)>0$ for all $z<\beta$.

Proposition 2.5. The eigenvalues $\\{\lambda_{k}\\}_{-\infty,\
k\not=0}^{\infty}$ of problem (2.1)–(2.5)

(i) are interlaced with the union $\\{\tau_{k}\\}_{-\infty,\
k\not=0}^{\infty}\mathop{=}\limits^{{\operatorname{def}}}\\{\mu^{(1)}_{k}\\}_{-\infty,\
k\not=0}^{\infty}\cup\\{\mu^{(2)}_{k}\\}_{-\infty,\ k\not=0}^{\infty}$

$-\infty<\tau_{1}^{2}\leq\lambda_{1}^{2}\leq\tau_{2}^{2}\leq\lambda_{2}^{2}\leq\cdots,$

(ii) all $\lambda_{k}$ are simple and for $k>0$ $\lambda_{k}=\tau_{k}$ if and
only if $\lambda_{k}=\tau_{k+1}$.

###### Proof.

It is known that
$\frac{s_{1}(\sqrt{z},\frac{a}{2})}{s_{1}^{\prime}(\sqrt{z},\frac{a}{2})}$ and
$\frac{s_{2}(\sqrt{z},\frac{a}{2})}{s_{2}^{\prime}(\sqrt{z},\frac{a}{2})}$ are
essentially positive Nevanlinna functions. It is known (see e.g. [19], Sec.
4.1) that if $f$ and $g$ are essentially positive Nevanlinna function then
such is also $(f+g)$. Therefore,

$\frac{\phi(\sqrt{z})}{s_{1}^{\prime}(\sqrt{z},\frac{a}{2})s_{2}^{\prime}(\sqrt{z},\frac{a}{2})}=\frac{s_{1}(\sqrt{z},\frac{a}{2})}{s_{1}^{\prime}(\sqrt{z},\frac{a}{2})}+\frac{s_{2}(\sqrt{z},\frac{a}{2})}{s_{2}^{\prime}(\sqrt{z},\frac{a}{2})}.$

is an essentially positive Nevanlinna function and (i) and (ii) follow by
Proposition 4.3 of [20]. ∎

##  3\. Inverse three spectral problem

In this section we will use known results on sine-type functions.

Definition 3.1. A function $f$ is said to be of sine-type $a$ (see [13]), if
its zeros are all distinct and there exist positive numbers $m$, $M$ and $p$
such that

$me^{|{\rm Im}\lambda|a}\leq|f(\lambda)|\leq Me^{|{\rm Im}\lambda|a}$

for $|{\rm Im}\lambda|>p$.

According to the statements 3 and of Theorem 2.2 each interval
$(\lambda_{k}^{2},\lambda_{k+1}^{2})$ contains exactly one element of
$\\{\theta_{k}^{2}\\}_{k=1}^{\infty}$ and according to Proposition 2.4 exactly
one element of $\\{\tau_{k}^{2}\\}_{k=1}^{\infty}$.

Definition 3.2. An interval $(\lambda_{k},\lambda_{k+1})$ is said to be
regular if it contains either exactly one element of $\\{\mu_{k}^{(1)}\\}$ and
exactly one element of $\\{\nu_{k}^{(2)}\\}$ or it contains either exactly one
element of $\\{\mu_{k}^{(2)}\\}$ and exactly one element of
$\\{\nu_{k}^{(1)}\\}$.

Remark. It can happen that regular intervals do not exist.

We will use the following notation:

$\pm\mathbb{N}=\pm 1,\pm 2,\ldots,\qquad N_{j}=\pm k_{1,j},\pm
k_{2,j},\ldots,\pm k_{n_{j},j}.$

The main result of this paper is given by the following theorem.

Theorem 3.3. Let $\\{\lambda_{k}\\}_{-\infty,\ k\not=0}^{\infty}$ be the
spectrum of problem (2.1)–(2.5),
$\\{\nu_{k}^{(j)}\\}_{-\infty,k\not=0}^{\infty}$ be the spectra of problems
(2.6) and let
$\\{\nu_{k}^{(1)}\\}_{-\infty,k\not=0}^{\infty}\cap\\{\nu_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}=\emptyset$.
Let $\\{\mu^{(2)}_{k}\\}_{k\in N_{1}}$ ($\mu^{(2)}_{-k}=-\mu^{(2)}_{k}$) be
eigenvalues of problem (2.7) with $j=2$ such that $(\mu_{k}^{(2)})^{2}$ belong
to the regular intervals and and $\\{\mu^{(1)}_{k}\\}_{k\in N_{2}}$
($\mu^{(1)}_{-k}=-\mu^{(1)}_{k}$) be eigenvalues of problem (2.7) with $j=1$
such that $(\mu_{k}^{(1)})^{2}$ belong to the regular intervals.

Then $\\{\nu^{(1)}_{k}\\}_{k\in(\pm\mathbb{N}\backslash N_{1})}$,
$\\{\mu^{(2)}_{k}\\}_{k\in\pm N_{1}}$,
$\\{\nu^{(2)}_{k}\\}_{k\in(\pm\mathbb{N}\backslash N_{2})}$ and
$\\{\mu^{(1)}_{k}\\}_{k\in\pm N_{2}}$ uniquely determine the pair ($q_{1}$,
$q_{2}$).

###### Proof.

Using (2.10) we find $A_{j}$ ($j=1,2$)

$A_{j}=\lim\limits_{k\to\infty}\pi k\left(\nu_{k}^{(j)}-\frac{2\pi
k}{a}\right).$

Let us consider the functions

$\omega(\lambda)=a\mathop{\prod}\limits_{k=1}^{\infty}\left(\frac{a}{\pi
k}\right)^{2}(\lambda_{k}^{2}-\lambda^{2}),$
$\phi_{1}(\lambda)=\frac{a}{2}\mathop{\prod}\limits_{k\in\pm\mathbb{N}\backslash
N_{1}}\left(\frac{a}{2\pi
k}\right)^{2}((\nu_{k}^{(1)})^{2}-\lambda^{2})\mathop{\prod}\limits_{k\in
N_{1}}\left(\frac{a}{2\pi
k}\right)^{2}\left((\mu_{k}^{(2)})^{2}-\lambda^{2}\right),$ (3.1)
$\phi_{2}(\lambda)=\frac{a}{2}\mathop{\prod}\limits_{k\in\pm\mathbb{N}\backslash
N_{2}}\left(\frac{a}{2\pi
k}\right)^{2}((\nu_{k}^{(2)})^{2}-\lambda^{2})\mathop{\prod}\limits_{k\in
N_{2}}\left(\frac{a}{2\pi
k}\right)^{2}\left((\mu_{k}^{(1)})^{2}-\lambda^{2}\right).$ (3.2)

Since

$s^{\prime}_{j}(\lambda)=\mathop{\prod}\limits_{k=1}^{\infty}\left(\frac{a}{2\pi(k-\frac{1}{2})}\right)^{2}((\mu_{k}^{(j)})^{2}-\lambda^{2}),$
$s_{j}(\lambda)=\frac{a}{2}\mathop{\prod}\limits_{k=1}^{\infty}\left(\frac{a}{2\pi
k}\right)^{2}((\nu_{k}^{(j)})^{2}-\lambda^{2}),$ (3.3)

we conclude keeping in mind (2.9), (3.1) and (3.2) that the functional
equation

$X(\lambda)\phi_{1}(\lambda)+Y(\lambda)\phi_{2}(\lambda)=\omega(\lambda)$
(3.4)

possesses a solution

$\tilde{X}(\lambda)=\mathop{\prod}\limits_{k\in\pm\mathbb{N}\backslash
N_{1}}\left(\frac{a}{\pi(2k-1)}\right)^{2}((\mu_{k}^{(2)})^{2}-\lambda^{2})\mathop{\prod}\limits_{k\in
N_{1}}\left(\frac{a}{\pi(2k-1)}\right)^{2}\left((\nu_{k}^{(1)})^{2}-\lambda^{2}\right),$
$\tilde{Y}(\lambda)=\mathop{\prod}\limits_{k\in\pm\mathbb{N}\backslash
N_{2}}\left(\frac{a}{\pi(2k-1)}\right)^{2}((\mu_{k}^{(1)})^{2}-\lambda^{2})\mathop{\prod}\limits_{k\in
N_{2}}\left(\frac{a}{\pi(2k-1)}\right)^{2}\left((\nu_{k}^{(2)})^{2}-\lambda^{2}\right).$

Let us prove that equation (3.4) possesses unique solution in the class of
sine-type functions of the form

$X(\lambda)=\cos\lambda\frac{a}{2}+A_{2}\frac{\sin\lambda\frac{a}{2}}{\lambda}+\frac{\tau_{2}(\lambda)}{\lambda},$
(3.5)
$Y(\lambda)=\cos\lambda\frac{a}{2}+A_{1}\frac{\sin\lambda\frac{a}{2}}{\lambda}+\frac{\tau_{1}(\lambda)}{\lambda},$
(3.6)

where $\tau_{j}\in{\mathcal{L}}^{\frac{a}{2}}$.

To this end, using (2.9) and (2.8) we obtain

$s_{2}^{\prime}(\nu_{k}^{(2)},\frac{a}{2})=\frac{\omega(\nu_{k}^{(2)})}{s_{1}(\nu_{k}^{(2)},\frac{a}{2})}=\cos\nu_{k}^{(2)}\frac{a}{2}+A_{2}\frac{\sin\nu_{k}^{(2)}\frac{a}{2}}{\nu_{k}^{(2)}}+\frac{\psi_{2,j}(\nu_{k}^{(2)})}{\nu_{k}^{(2)}},$

where due to (2.13)
$\\{\psi_{2,j}(\nu_{k}^{(2)})\\}_{-\infty,k\not=0}^{\infty}\in l_{2}$ by Lemma
1.4.3 of [15] .

We look for the solution of (3.4) in the form (3.5), (3.6). Let us consider
(3.4) at the zeros of $\phi_{2}$ which we will use as the nodes of
interpolation. Comparing (3.1) and (3.3) we obtain

$\phi_{1}(\lambda)=s_{1}(\lambda,\frac{a}{2})\mathop{\prod}\limits_{k\in
N_{1}}\left((\mu_{k}^{(2)})^{2}-\lambda^{2}\right)((\nu_{k}^{(1)})^{2}-\lambda^{2})^{-1}.$
(3.7)

Thus, we conclude that for $k\in\pm{\mathbb{N}}\backslash N_{2}$

$X(\nu_{k}^{(2)})=\frac{\omega(\nu_{k}^{(2)})}{\phi_{1}(\nu_{k}^{(2)})}=\frac{\omega(\nu_{k}^{(2)})}{s_{1}(\nu_{k}^{(2)},\frac{a}{2})}\mathop{\prod}\limits_{p\in
N_{1}}\left((\mu_{p}^{(2)})^{2}-(\nu_{k}^{(2)})^{2}\right)^{-1}((\nu_{p}^{(1)})^{2}-(\nu_{k}^{(2)})^{2})$

and for $k\in N_{2}$

$X(\mu_{k}^{(1)})=\frac{\omega(\mu_{k}^{(1)})}{\phi_{1}(\mu_{k}^{(1)})}=\frac{\omega(\mu_{k}^{(1)})}{s_{1}(\mu_{k}^{(1)},\frac{a}{2})}\mathop{\prod}\limits_{p\in
N_{1}}\left((\mu_{p}^{(2)})^{2}-(\mu_{k}^{(1)})^{2}\right)^{-1}((\nu_{p}^{(1)})^{2}-(\mu_{k}^{(1)})^{2}).$

Hence, for $k$ large

$\displaystyle X(\nu_{k}^{(2)})$
$\displaystyle=\left(\cos\nu_{k}^{(2)}\frac{a}{2}+A_{2}\frac{\sin\nu_{k}^{(2)}\frac{a}{2}}{\nu_{k}^{(2)}}+\frac{\psi_{2,j}(\nu_{k}^{(2)})}{\nu_{k}^{(2)}}\right)(1+O(k^{-2})$
$\displaystyle=\cos\nu_{k}^{(2)}\frac{a}{2}+A_{2}\frac{\sin\nu_{k}^{(2)}\frac{a}{2}}{\nu_{k}^{(2)}}+\left(\cos\nu_{k}^{(2)}\frac{a}{2}+A_{2}\frac{\sin\nu_{k}^{(2)}\frac{a}{2}}{\nu_{k}^{(2)}}\right)O(k^{-2})$
$\displaystyle+\frac{\psi_{2,j}(\nu_{k}^{(2)})}{\nu_{k}^{(2)}}(1+O(k^{-2})).$

Than the sequence $\\{\tau_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}$ where

$\tau_{k}^{(2)}=:\nu_{k}^{(2)}\left(X(\nu_{k}^{(2)})-\cos\nu_{k}^{(2)}\frac{a}{2}-A_{2}\frac{\sin\nu_{k}^{(2)}\frac{a}{2}}{\nu_{k}^{(2)}}\right),\
\ k\in\pm\mathbb{N}\backslash N_{2}$

and

$\tau_{k}^{(2)}=:\mu_{k}^{(1)}\left(X(\mu_{k}^{(1)})-\cos\mu_{k}^{(1)}\frac{a}{2}-A_{2}\frac{\sin\mu_{k}^{(1)}\frac{a}{2}}{\mu_{k}^{(1)}}\right),\
\ k\in N_{2}$

belongs to $l_{2}$.

Let us assume that $\phi_{2}(0)\neq 0$, otherwise we can shift the spectral
parameter $\lambda^{2}\rightarrow\lambda^{2}+c$. Since
$\tilde{\phi_{2}}(\lambda)=\lambda\phi_{2}(\lambda)$ is a sine type function
with all zeros including $\tilde{\phi}_{2}(0)=0$ simple we can use the set
$\\{\nu_{k}^{(2)}\\}_{k\in\pm{\mathcal{N}}\backslash
N_{2}}\cup\\{\mu_{k}^{(1)}\\}_{k\in N_{2}}\cup\\{0\\}$ of zeros of
$\tilde{\phi}_{2}$ as the nodes of interpolation. The values of the function
$\tau_{2}(\lambda)$ we interpolate are $\tau^{(2)}_{k}$ and $\tau^{(2)}(0)=0$.
Since $\\{\tau_{k}^{(2)}\\}_{-\infty,k\not=0}^{\infty}\in l_{2}$, according to
[13], [24] the series

$\tau_{2}(\lambda)\\!=:\\!\tilde{\phi}_{2}(\lambda)\mathop{\sum}\limits_{k\in\pm{\mathcal{N}}\backslash
N_{2}}\frac{\tau_{k}^{(2)}}{\frac{d\tilde{\phi}_{2}(\lambda)}{d\lambda}|_{\lambda=\nu_{k}^{(2)}}(\lambda-\nu_{k}^{(2)})}\\!+\\!\tilde{\phi}_{2}(\lambda)\mathop{\sum}\limits_{k\in
N_{2}}\frac{\tau_{k}^{(2)}}{\frac{d\tilde{\phi}_{2}(\lambda)}{d\lambda}|_{\lambda=\mu_{k}^{(1)}}(\lambda-\mu_{k}^{(1)})}$
(3.8)

converges uniformly on any compact of $\mathbb{C}$ and in the norm of
$L_{2}(-\infty,\infty)$ to a function in ${\mathcal{L}}^{a/2}$ . Since (3.8)
establishes one-to-one correspondence between $l_{2}$ and
${\mathcal{L}}^{\frac{a}{2}}$ we conclude that

$X(\lambda)=:\cos\lambda\frac{a}{2}+A_{2}\frac{\sin\lambda\frac{a}{2}}{\lambda}+\frac{\tau_{2}(\lambda)}{\lambda}=\tilde{X}(\lambda).$

It is easy to prove in the same way that $\tilde{Y}(\lambda)$ is also uniquely
determined by (3.4) . We identify with $\nu_{k}^{(1)}$ the zero of $\tilde{X}$
which lies in the regular interval containing $\mu_{k}^{(2)}$ ($k\in N_{1}$)
and with $\nu_{k}^{(2)}$ the zero of $\tilde{Y}$ which lies in the regular
interval containing $\mu_{k}^{(1)}$ ($k\in N_{2}$). It is clear that
$\\{\nu_{k}^{(j)}\\}_{-\infty,k\not=0}^{\infty}$ and
$\\{\mu_{k}^{(j)}\\}_{-\infty,k\not=0}^{\infty}$ uniquely determine
$q_{j}(x)$. The method of recovering $q_{j}(x)$ by the two spectra
$\\{\nu_{k}^{(j)}\\}_{-\infty,k\not=0}^{\infty}$ and
$\\{\mu_{k}^{(j)}\\}_{-\infty,k\not=0}^{\infty}$ can be found in [15]. The
theorem is proved. ∎

## References

  * [1] Ju. M. Berezanskii, Expansions in Eigenfunctions of Selfadjoint Operators, Amer. Math. Soc., Providence, RI, 1968. (Russian edition: Naukova Dumka, Kiev, 1965)
  * [2] M. Drignei, Uniqueness of solutions to inverse Sturm-Liouville problems with $L^{2}(0,a)$ potentials using three spectra, Adv. Appl. Math. 42 (2009), no. 4, 471–482.
  * [3] M. Drignei, Constructability of an $L_{R}^{2}(0,a)$ solution of an inverse Sturm-Liouville problem using three spectra, Inverse Problems 26 (2010), no. 2, 025003, 29 pp.
  * [4] M. Drignei, Numerical reconstruction in a three-spectra inverse Sturm-Liouville problem with mixed boundary conditions, Inverse Problems in Science and Engineering 21 (2013), no. 8, 1368–1391.
  * [5] J. Eckhardt, Two inverse spectral problems for a class of singular Krein strings, Int. Math. Res. Not. IMRN 3 (2014), 3692–3713.
  * [6] J. Eckhardt, F. Gesztesy, R. Nichols and G. Teschl, Inverse spectral theory for Sturm-Liouville operators with distributed potentials, J. London Math. Soc. (2) 88 (2013), no. 3, 801–828.
  * [7] S. Fu, Z. Xu, and G. Wei, Inverse indefinite Sturm-Liouville problems with three spectra, J. Math. Anal. Appl. 381 (2011), 506–512.
  * [8] F. Gesztesy and B. Simon, On the determination of a potential from three spectra, Differential Operators and Spectral Theory, Amer. Math. Soc. Transl. Ser. 2, vol. 189, Amer. Math. Soc., Providence, RI, 1999, 85–92.
  * [9] O. H. Hald, Inverse eigenvalue problem for the mantle, Geophysical Journal of the Royal Astronomical Society 62 (1980), 41–48.
  * [10] H. Hochstadt and B. Lieberman, An inverse Sturm-Liouville problems with mixed given data, SIAM J. Appl. Math. 34 (1978), 676–680.
  * [11] R. O. Hryniv and Ya. V. Mykytyuk, Inverse spectral problems for Sturm–Liouville operators with singular potentials. Part III: Reconstruction by three spectra, J. Math. Anal. Appl. 284 (2003), 626–646.
  * [12] M. G. Krein, Selected works, Vol. 3: Spectral Theory of a String and Questions of Stability, Institute of Mathematics of the National Academy of Sciences of Ukraine, Kiev, 1997. (Russian)
  * [13] B. Ja. Levin and Yu. I. Lyubarskii, Interpolation by entire functions of special classes and related expansions in series of exponents, Izv. Acad. Nauk USSR 39 (1975), no. 3, 657–702. (Russian)
  * [14] B. M. Levitan, Inverse Sturm-Liouville Problems, VNU Science Press, Utrecht, 1987. (Russian edition: Nauka, Moscow, 1984)
  * [15] V. A. Marchenko, Sturm-Liouville Operators and their Applications, Operator Theory, vol. 22, Birkhäuser, Basel, 1986. (Russian edition: Naukova Dumka, Kiev, 1977)
  * [16] O. Martynyuk and V. Pivovarchik, On Hochstadt-Lieberman theorem, Inverse Problems 26 (2010), no. 3, 035011, 6 pp.
  * [17] V. Pivovarchik, On the Hald-Gesztesy-Simon theorem, Integral Equations and Operator Theory 73 (2012), 383–393.
  * [18] V. Pivovarchik, An inverse Sturm-Liouville problem by three spectra, Integral Equations and Operator Theory 34 (1999), 234–243.
  * [19] V. Pivovarchik and H. Woracek, Shifted Hermite-Biehler functions and their applications, Integral Equations and Operator Theory 57 (2007), 101–126.
  * [20] V. Pivovarchik and H. Woracek, Sums of Nevanlinna functions and differential equations on star-shaped graphs, Operators and Matrices 3 (2009), no. 4, 451–501.
  * [21] L. A. Sakhnovich, Half-inverse problem on the finite interval, Inverse Problems 17 (2001), no. 3, 527–532.
  * [22] T. Suzuki, Inverse problems for heat equations on compact intervals and on circles, I, J. Math. Soc. Japan 38 (1986), no. 1, 39–65.
  * [23] G. Wei and X. Wei, A generalization of three spectra theorem for inverse Sturm-Liouville, Appl. Math. Lett. 35 (2014), 41–45.
  * [24] R. M. Young, An Introduction to Nonharmonic Fourier Series, Academic Press, New York, 1980.


# iEDA: An Open-Source Intelligent Physical Implementation Toolkit and Library

Xingquan Li1,111, Simin Tao1, Zengrong Huang1, Shijian Chen1,2,13, Zhisheng
Zeng1,2,13, Liwei Ni1,2,13,
Zhipeng Huang1, Chunan Zhuang1, Hongxi Wu4,3, Weiguo Li11,3, Xueyan
Zhao2,13,1, He Liu5,1, Shuaiying Long1,
Wei He1, Bojun Liu1, Sifeng Gan1, Zihao Yu2,3, Tong Liu12,3, Yuchi Miao1,
Zhiyuan Yan2,13, Hao Wang6,3,
Jie Zhao1, Yifan Li7,13,3, Ruizhi Liu2,13,1, Xiaoze Lin1,2,13, Bo Yang1,9,
Zhen Xue1,2,13, Fuxing Huang4, Zonglin Yang8,3,
Zhenggang Wu1, Jiangkao Li11,3, Yuezuo Liu6,3, Ming Peng6,3, Yihang Qiu10,3,
Wenrui Wu8,3, Zheqing Shao6,3,
Kai Mo8,3, Jikang Liu8,3, Yuyao Liang8,3, Mingzhe Zhang6,3, Zhuang Ma6,3,
Xiang Cong6, Daxiang Huang1,
Guojie Luo5,1, Huawei Li2,13,1, Haihua Shen13,1, Mingyu Chen2,13,1, Dongbo
Bu14,13,1, Wenxing Zhu4,1,
Ye Cai8,1, Xiaoming Xiong10, Ying Jiang9,1, Yi Heng9,1, Peng Zhang1, Biwei
Xie${}^{2,1,\text{\Letter}}$, and Yungang Bao${}^{2,13,3,1,\text{\Letter}}$
Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>1Peng Cheng Laboratory, Shenzhen, China
2State Key Lab of Processors, Institute of Computing Technology, Chinese
Academy of Sciences, Beijing, China  3Beijing Institute of Open Source Chip,
Beijing, China  4Fuzhou University, Fuzhou, China  5Peking University,
Beijing, China  6University of Science and Technology of China, Hefei, China
7Institute of Microelectronics, Chinese Academy of Sciences, Beijing, China
8Shenzhen University, Shenzhen, China  9Sun Yat-sen University, Guangzhou,
China  10Guangdong University of Technology, Guangzhou, China  11Minnan Normal
University, Zhangzhou, China  12The Hong Kong University of Science and
Technology (Guangzhou), Guangzhou, China  13University of Chinese Academy of
Sciences, Beijing, China  14Institute of Computing Technology, Chinese Academy
of Sciences, Beijing, China

###### Abstract

Open-source EDA shows promising potential in unleashing EDA innovation and
lowering the cost of chip design. This paper presents an open-source EDA
project, iEDA, aiming for building a basic infrastructure for EDA technology
evolution and closing the industrial-academic gap in the EDA area. iEDA now
covers the whole flow of physical design (including Floorplan, Placement, CTS,
Routing, Timing Optimization etc.), and part of the analysis tools (Static
Timing Analysis and Power Analysis). To demonstrate the effectiveness of iEDA,
we implement and tape out three chips of different scales (from 700k to 1.5M
gates) on different process nodes (110nm and 28nm) with iEDA. iEDA is publicly
available from the project home page http://ieda.oscc.cc.

###### Index Terms:

Netlist-to-GDS, infrastructure, tool, flow, chip.

##  I Introduction

The rapid advancement of digital technology has led to a substantial increase
in demand for the growth of the integrated circuit (IC) industry. However,
Moore’s law has reached its limits [1]. To meet the growing needs for
computing and storage, we may explore alternative integration technologies,
such as 3D chip design or package and chiplets. Moreover, we should strive to
improve the quality of chip design, especially in the area of electronic
design automation (EDA). Chip design, EDA tools, and methodologies have been
the subject of research for many years. Fortunately, new techniques such as
artificial intelligence, hardware acceleration, and collaborative design of
chips and EDA have demonstrated their capacity and practical value in EDA.
These advancements open up the potential for further optimizing EDA tools and
methodologies.

To maximize the benefits of new techniques in EDA, we need an open-source
platform accessible to all EDA enthusiasts. There are already several open
source physical design platform OpenROAD [2] and tools (e.g., DREAMPlace [3],
CUGR [4], Dr.CU 2.0 [5], OpenTimer [6]) that work well to promote open
collaboration and innovation. The platform should be automated, well-designed,
and compatible while supporting tapeout while offering high performance and
scalability, providing comprehensive documentation, and easy-to-learn. The
iEDA project aims to create an open-source EDA platform and build an EDA
community. It supports chip implementation from netlist to GDSII for block-
level chips and system-on-chips (SoCs) at 28nm process node. The main goal of
iEDA is to provide a research platform for enthusiasts to explore chip design,
EDA methodologies, algorithms, software development, and more.

Figure 1: The iEDA framework and infrastructure.

##  II iEDA Status

###  II-A Framework

The iEDA platform consists of four key components: basic infrastructure, a
functional module-level data model, a solver (algorithms and AI models), and
function operations as shown in Fig. 1. The infrastructure includes the basic
data and a series of EDA software kits and frameworks. The data model provides
pre-design data services for upper-level EDA functions. The AI models and
algorithms are the core solvers that determine the quality and performance of
the platform. The operations component is responsible for chip design
functions, which include data models and solvers. The iEDA platform, along
with a process design kit (PDK), enables the flow of chip design from RTL
design to GDS layout.

###  II-B Infrastructure

The iEDA software infrastructure, as shown in Fig. 1, includes a file system
with parsers and file managers, a database with builders, writers, and data
managers, a platform with evaluators, optimizers, and managers, and an
interface with apps, evaluations, and tests, as well as a GUI. This unified
infrastructure ensures the robustness and extensibility of iEDA.

###  II-C Tools

The chip design step and the iEDA tools are shown in Fig. 2, each iEDA tool is
composed of several low-coupling functional operations, which works by calling
a series of different algorithms on designated data models.

####  II-C1 Floorplan and Power Delivery Network

Floorplanning is the initial stage of physical design. iFP mainly includes the
following parts: layout initialization, pre-placement of certain cells,
automatic generation of IO locations, automatic placement of macros based on
the netlist structure and IO, and generation of the power delivery network.

####  II-C2 Placement

Placement mainly ensures the proper coordinate of each cell mapped in the
netlist within a designated region, which must comply with design rules and be
conducive to routing, timing convergence, and power consumption. iPL is mainly
composed of a global placer, post-global placer, legalizer, detailed placer,
filler, and checker. The objective of iPL is to minimize wire-length, timing
and congestion.

Figure 2: Chip design step and iEDA tools.

####  II-C3 Timing Optimization

Timing optimization is aimed at ensuring that the chip design is both
functionally correct and meets the design requirements for performance. iTO
offers distinct and user-friendly interfaces to fix timing design rule
violations, hold time violations, and setup time violations. Our goal is to
resolve any timing violations on the chip to enhance its overall performance.

####  II-C4 Clock Tree Synthesis

The goal of iCTS is to balance skew among flip-flops while optimizing design
resource usage, under timing constraints. It has an integrated timing model
that offers accurate and efficient computation of timing information, such as
delay, capacitance, and slew. The algorithms implemented in iCTS allow for the
generation of topologies with various objectives and support the creation of
hierarchical clock trees using multiple merging criteria.

####  II-C5 Routing

Routing entails physical wires of the interconnections among components
embedded in a chip. The objective of routing is to meet performance and
functional requirements while considering factors such as design rule check
(DRC) and signal integrity. iRT consists of components such as a resource
allocator, topology generator, planar router, layer assigner, guide processor,
track assigner, space router, and region manager.

####  II-C6 Static Timing Analysis

iSTA is a timing analysis tool that provides easy-to-use interfaces for
accessing required timing data. Besides of basic timing path analysis, iSTA
offers incremental timing propagation, detailed timing reports, advanced delay
calculation based on composite current source (CCS) liberty, basic cross-talk
delay analysis, and on-chip variation analysis. iSTA also supports parallel
processing of load liberty data for faster performance.

####  II-C7 Power Analysis

iPA is a power analysis tool that supports both basic vectorless analysis
without waveform data and vector analysis with VCD/SAIF data. It features fast
toggle and static probability propagation, and glitch analysis that considers
timing delay.

###  II-D Flow

To verify the functionality and effectiveness of iEDA, we develop iFlow, which
is implemented in Python by calling TCL-based or Python-based tool commands.
It is worth noting that, since iEDA supports only netlist-to-GDSII, iFlow
integrates Yosys/ABC [7][8] for synthesis and some commercial tools for
signoff analysis and verification. We implement and tape out three chips with
iEDA: one 5-stage RISC-V chip supporting RT-Thread on 110nm; two 11-stage
RISC-V chips supporting Linux on 110nm and 28nm in respective. The first
5-stage RISC-V chip on 110nm has already successfully booted up (Fig. 3), and
the other two chips will return before May.2023.

Figure 3: From GDS to computer device.

##  III iEDA Future

###  III-A Infrastructure

To better serve the research and development of EDA technology, we will
further support more file formats and process nodes, and provide more
evaluators and optimizers. In addition, we will try to decompose the tools of
iEDA into micro-services and build a cloud-native EDA system.

###  III-B Tools

The performance of physical design tools will be further improved through
carefully designed software architecture and key algorithms, combined with
hardware acceleration and AI models, to support larger and more diverse chip
designs and scenarios. We will launch electromigration (EM) and interconnect
resistance drop (IR) analysis to complete the analysis toolchain. All analysis
tools will share the common database with physical design tools. Physical
verification is the final step in IC design closure and typically involves
design rule check (DRC), layout versus schematic (LVS), and electrical rule
check (ERC). In the upcoming version of iEDA, the development of these tools
is being planned.

###  III-C Flow

Chip design flow encompasses multiple steps and involves numerous parameters.
Furthermore, the requirements for chip design and process node are highly
diverse, making it challenging to adapt to various design objectives and
constraints within a specific chip design script. To overcome this challenge
and achieve an efficient flow with the right parameter configuration, our plan
is to extract the majority of parameters from the EDA tools used in the design
flow. Additionally, we aim to optimize the chip design objective by conducting
a thorough study of the design space exploration

###  III-D AiEDA

In the era of intelligence, it has gradually become a trend to use artificial
intelligence (AI) technology to liberate engineers from heavy repetitive work.
This can also further improve the chip performance and production efficiency.
With the powerful application of AI in many engineering fields, we have reason
to believe that AI can bring significant value for EDA. However, due to the
deficiency of AI infrastructure in EDA, such as open-source EDA toolkit and
package, accessible labeled data set and system, and valuable AI model for
EDA, the existing AI works in EDA lack practical implementation possibilities.
To maximize the value of AI for EDA, we will build some AI infrastructures in
the next iEDA version. Futhermore, AI researcher and developer can focus on
valuable AI model for EDA, and then we will obtain a better chip design
solution which is composed of EDA tool and AI model as shown in Fig. 4.

Figure 4: iEDA tools with AI models.

## Acknowledgment

This work is supported in part by the Major Key Project of PCL (No.
PCL2021A08), the Strategic Priority Research Program of Chinese Academy of
Sciences (No. XDC05030400), the Strategic Priority Research Program of Chinese
Academy of Sciences (No. XDA0320300), the National Key R&D Program of China
(No. 2022YFB4500403), National Natural Science Foundation of China (No.
62090024), the National Natural Science Foundation of China (No. 62090021),
the National Natural Science Foundation of China (No. 62174033), the National
Natural Science Foundation of China (No. 61907024).

## References

  * [1] M. S. Lundstrom and M. A. Alam. Moore’s law: The journey ahead. _Science_ , 378(6621):722–723, 2022.
  * [2] T. Ajayi and D. Blaauw. OpenROAD: Toward a self-driving, open-source digital layout implementation tool chain. _In Proceedings of Government Microcircuit Applications and Critical Technology Conference_ , 2019.
  * [3] Y. Lin, S. Dhar, W. Li, H. Ren, B. Khailany, and D. Z. Pan. DREAMPlace: Deep learning toolkit-enabled GPU acceleration for modern VLSI placement. _In Proceedings of DAC_ , pages 1–6, 2019.
  * [4] J. Liu, C.-W. Pui, F. Wang, and E. F. Young. CUGR: Detailed- routability-driven 3D global routing with probabilistic resource model. _In Proceedings of DAC_ , pages 1–6. IEEE, 2020.
  * [5] H. Li, G. Chen, B. Jiang, J. Chen, and E. F. Young. Dr. CU 2.0: A scalable detailed routing framework with correct-by-construction design rule satisfaction. _In Proceedings of ICCAD_ , pages 1–7. IEEE, 2019.
  * [6] T.-W. Huang and M. D. Wong. OpenTimer: A high-performance timing analysis tool. _In Proceedings of ICCAD_ , pages 895–902. IEEE, 2015.
  * [7] C. Wolf, J. Glaser, and J. Kepler. Yosys - A free verilog synthesis suite. _In Proceedings of the 21st Austrian Workshop on Microelectronics_ , 2013.
  * [8] R. Brayton and A. Mishchenko. ABC: An academic industrial strength verification tool. _In Proceedings of Computer Aided Verification_ , Edinburgh, UK, pages 24–40. Springer, 2010.


# Using the Swing Lemma and Czédli diagrams for congruences of planar
semimodular lattices

George Grätzer<EMAIL_ADDRESS>http://server.maths.umanitoba.ca/homepages/gratzer/ University of Manitoba

(Date: April 12, Version 0.4)

###### Abstract.

A planar semimodular lattice $K$ is _slim_ if $\mathsf{M}_{3}$ is not a
sublattice of $K$. In a recent paper, G. Czédli found four new properties of
congruence lattices of slim, planar, semimodular lattices, including the _No
Child Property_ : _Let $P$ be the ordered set of join-irreducible congruences
of $K$. Let $x,y,z\in P$ and let $z$ be a maximal element of $P$. If $x\neq
y$, $x,y\prec z$ in $P$, then there is no element $u$ of $P$ such that $u\prec
x,y$ in $P$._

We are applying my Swing Lemma, 2015, and a type of standardized diagrams of
Czédli’s, to verify Czédli’s four properties.

###### Key words and phrases:

Rectangular lattice, patch lattice, slim planar semimodular lattice,
congruence lattice

###### 2000 Mathematics Subject Classification:

06C10

##  1\. Introduction

Let $K$ be a planar semimodular lattice. We call the lattice $K$ _slim_ if
$\mathsf{M}_{3}$ is not a sublattice of $K$. In the paper [4], I found a
property of congruences of slim, planar, semimodular lattices. In the same
paper (see also Problem 24.1 in G. Grätzer [6]), I proposed the following:

Problem 1. Characterize the congruence lattices of slim planar semimodular
lattices.

G. Czédli [2, Corollaries 3.4, 3.5, Theorem 4.3] found four new properties of
congruence lattices of slim, planar, semimodular lattices.

######  Czédli’s Theorem [2].

Let $K$ be a slim, planar, semimodular lattice with at least three elements
and let $\mathcal{P}$ be the ordered set of join-irreducible congruences of
$K$.

  1. (i)

_Partition Property:_ The set of maximal elements of $\mathcal{P}$ can be
represented as the disjoint union of two nonempty subsets such that no two
distinct elements in the same subset have a common lower cover.

  2. (ii)

_Maximal Cover Property:_ If $x\in\mathcal{P}$ is covered by a maximal element
$y$ of $\mathcal{P}$, then $y$ is not the only cover.

  3. (iii)

_Four-Crown Two-pendant Property:_ There is no cover-preserving embedding of
the ordered set $\mathcal{R}$ in Figure 1 into $\mathcal{P}$ satisfying the
property: any maximal element of $\mathcal{R}$ is a maximal element of
$\mathcal{P}$.

  4. (iv)

_No Child Property:_ Let $x\neq y\in\mathcal{P}$ and let $z$ be a maximal
element of $\mathcal{P}$. Let us assume that both $x$ and $y$ are covered by
$z$ in $\mathcal{P}$. Then there is no element $u\in\mathcal{P}$ such that $u$
is covered by $x$ and $y$.

In this paper, we will prove this theorem using the Swing Lemma and Czédli
diagrams, see Sections 2.1 and 2.2. By G. Grätzer and E. Knapp [11], every
slim, planar, semimodular lattice $K$ has a congruence-preserving extension
$\overline{K}$ to a slim rectangular lattice. Any of the properties (i)–(iv)
holds for $K$ iff it holds for $\overline{K}$. Therefore, in the rest of this
paper, we can assume that $K$ is a slim rectangular lattice, simplifying the
discussion.

Figure 1. The Four-crown Two-pendant ordered set $\mathcal{R}$ with notation;
the covering $\mathsf{N}_{7}$ sublattice with notation

### Outline

Section 2 provides the results we need: the Swing Lemma, Czédli’s
$\mathcal{C}_{1}$-diagrams (we call them Czédli diagrams), and forks. Section
3 proves the Partition Property, Section 4 does the Maximal Cover Property,
while Section 5 verifies the No Child Property. Finally, The Four-Crown Two-
pendant Property is proved in Section 6.

##  2\. Background

Most basic concepts and notation not defined in this paper are available in
Part I of the book [6], see

`https://www.researchgate.net/publication/299594715`
`arXiv:2104.06539`

It is available to the reader. We will reference it, for instance, as [CFL2,
page 52].

###  2.1. Swing Lemma

An _SPS lattice_ $K$ is a slim, planar, and semimodular lattice, see [CFL2,
Chapter 4]. For an edge (prime interval) $E$ of $K$, let $E=[0_{E},1_{E}]$ and
define $\textup{col}(E)$, the _color of_ $E$, as $\textup{con}(E)$, the (join-
irreducible) congruence generated by collapsing $E$ (see [CFL2, Section 3.2]).
We write $\mathcal{P}$ for $J(\operatorname{Con}K)$, the ordered set of join-
irreducible congruences of $K$.

As in my paper [5], for the edges $U,V$ of an SPS lattice $K$, we define a
binary relation: $U$  _swings_ to $V$, in formula,
$U\mathbin{\raisebox{2.0pt}{\rotatebox{160.0}{$\curvearrowleft$}}}V$, if
$1_{U}=1_{V}$, the element $1_{U}=1_{V}$ covers at least three elements, and
$0_{V}$ is neither the left-most nor the right-most element covered by
$1_{U}=1_{V}$; if also $0_{U}$ is such, then the swing is _interior_.

######  Swing Lemma [G. Grätzer [5]].

Let $K$ be an SPS lattice and let $U$ and $V$ be edges in $K$. Then
$\textup{col}(V)\leq\textup{col}(U)$ iff there exists an edge $R$ such that
$U$ is up-perspective to $R$ and there exists a sequence of edges and a
sequence of binary relations

(1)
$R=R_{0}\mathbin{\varrho}_{1}R_{1}\mathbin{\varrho}_{2}\dots\mathbin{\varrho}_{n}R_{n}=V,$

where each relation $\mathbin{\varrho}_{i}$ is
$\stackrel{{\scriptstyle\textup{dn}}}{{\thicksim}}$ (down-perspective) or
$\mathbin{\raisebox{2.0pt}{\rotatebox{160.0}{$\curvearrowleft$}}}$ (swing).

In addition, the sequence (1) also satisfies

(2) $1_{R_{0}}\geq 1_{R_{1}}\geq\dots\geq 1_{R_{n}}.$

The following statements are immediate consequences of the Swing Lemma, see my
papers [5] and [7].

######  Corollary 1.

We use the assumptions of the Swing Lemma.

  1. (i)

If $\textup{col}(U)=\textup{col}(V)$, then either $U$ and $V$ are perspective
or there exist edges $S$ and $T$ so that
$U\stackrel{{\scriptstyle\textup{up}}}{{\thicksim}}S\mathbin{\raisebox{2.0pt}{\rotatebox{160.0}{$\curvearrowleft$}}}T\stackrel{{\scriptstyle\textup{dn}}}{{\thicksim}}V$,
where the swing is interior.

  2. (ii)

If $v\prec u$ in $\mathcal{P}$, then there exist edges $U,L$ of color $u$ and
$R,V$ of color $v$ such that
$U\stackrel{{\scriptstyle\textup{up}}}{{\thicksim}}L\mathbin{\raisebox{2.0pt}{\rotatebox{160.0}{$\curvearrowleft$}}}R\stackrel{{\scriptstyle\textup{dn}}}{{\thicksim}}V$,
as in see the first diagram of Figure 2.

Note that the covering relation in $\mathcal{P}$ can always be represented in
a covering $\mathsf{N}_{7}$.

Figure 2. Illustrating Corollaries 2 and 3

######  Corollary 2.

Let the edge $U$ be on the upper edge of $K$. Then $\textup{col}(U)$ is a
maximal element of $\mathcal{P}$. Conversely, if $u$ is a maximal element of
$\mathcal{P}$, then there is an edge $U$ on the upper edge of $K$ so that
$\textup{col}(U)=u$.

######  Corollary 3.

Let $v\prec u$ in $\mathcal{P}$ and $u$ be a maximal element of $\mathcal{P}$.
If $U$ is an edge on the upper edge of $K$ with $\textup{col}(U)=u$, then
there exist an edge $L$ such that
$U\stackrel{{\scriptstyle\textup{dn}}}{{\thicksim}}L\mathbin{\raisebox{2.0pt}{\rotatebox{160.0}{$\curvearrowleft$}}}V$,
as in the second diagram of Figure 2.

###  2.2. Czédli diagrams

In the diagram of a planar lattice $K$, a _normal edge_ (_line_) has a slope
of $45\degree$ or $135\degree$. If it is the first, we call it a _normal-up
edge_ (_line_), otherwise, a _normal-down edge_ (_line_). Any edge of slope
strictly between $45\degree$ and $135\degree$ is _steep_. We use the symbols ,
, , and , for normal, normal-up, normal-down, and steep, respectively.

######  Definition 4 (G. Czédli [1]).

A diagram of an SPS lattice $L$ is a _Czédli-diagram_ if the middle edge of
any covering $\mathsf{N}_{7}$ is steep and all other edges are normal.

######  Theorem 5 (G. Czédli [1]).

Every slim, planar, semimodular lattice $K$ has a Czédli diagram.

See the illustrations in this paper for examples of Czédli diagrams. G. Czédli
[1] calls these $\mathcal{C}_{1}$-diagrams. He also defines
$\mathcal{C}_{0}$\- and $\mathcal{C}_{2}$-diagrams. For an alternative proof
for the existence of Czédli diagrams, see G. Grätzer [10].

_In this paper, $K$ denotes a slim rectangular lattice with a fixed Czédli
diagram_.

Let $C$ and $D$ be maximal chains in an interval $[a,b]$ of $K$ such that
$C\cap D=\\{a,b\\}$. If there is no element of $K$ between $C$ and $D$, then
we call $C\cup D$ a  _cell_. A four-element cell is a _$4$ -cell_. Opposite
edges of a $4$-cell are called _adjacent_. Planar semimodular lattices are
$4$-cell lattices, that is, all of its cells are $4$-cells, see G. Grätzer and
E. Knapp [9, Lemmas 4, 5] and [CFL2, Section 4.1] for more detail.

The following statement illustrates the use of Czédli diagrams.

######  Lemma 6.

Let $K$ be a slim rectangular lattice $K$ with a fixed Czédli diagram and let
$X$ be a -edge of $K$. Then $X$ is up-perspective either to an edge in the
upper-left boundary of $K$ or to a -edge.

###### Proof.

If $X$ is not in the upper-left boundary of $K$, then there is a $4$-cell $C$
whose lower-right edge is $X$. If the upper-left edge is  or it is in the
upper-left boundary, then we are done. Otherwise, we proceed the same way
until we reach the upper-left boundary. ∎

###  2.3. Trajectories

G. Czédli and E. T. Schmidt [3] introduced a _trajectory_ in $K$ as a maximal
sequence of consecutive edges, see also [CFL2, Section 4.1]. The _top edge_
$T$ of a trajectory is either in the upper boundary of $K$ or it is . For such
an edge $T$, we denote by $\textup{traj}{(T})$ the trajectory with top edge
$T$. Since an element $a$ in a slim semimodular lattice has at most three
covers (G. Grätzer and E. Knapp [9, Lemma 8]), a trajectory has at most one
top edge and at most one –edge. So we conclude:

######  Lemma 7.

Let $K$ be a slim rectangular lattice $K$ with a fixed Czédli diagram. Let $X$
and $Y$ be –edges of $K$. Then $\textup{traj}{(X})$ and $\textup{traj}{(Y})$
are disjoint.

##  3\. The Partition Property

We start with a lemma.

######  Lemma 8.

Let $X$ and $Y$ be distinct edges on the upper-left boundary of $K$ of color
$x$ and $y$, respectively. Then there is no edge $Z$ of $K$ of color $z$ such
that $z\prec x,y$.

###### Proof.

By way of contradiction, let $Z$ be an edge of color $z$ such that $z\prec
x,y$. $\ell_{Y}$ the $\includegraphics[scale={.2}]{normaldn}-$line through
$0_{Y}$. By Corollary 3, there exist edges $L_{X},L_{Y},Z_{X},Z_{Y}$ such that
$X\stackrel{{\scriptstyle\textup{dn}}}{{\thicksim}}L_{X}\mathbin{\raisebox{2.0pt}{\rotatebox{160.0}{$\curvearrowleft$}}}Z_{X}$,
$Y\stackrel{{\scriptstyle\textup{dn}}}{{\thicksim}}L_{Y}\mathbin{\raisebox{2.0pt}{\rotatebox{160.0}{$\curvearrowleft$}}}Z_{Y}$
and $Z\in\textup{traj}{(Z_{X}})\cap\textup{traj}{(Z_{Y}})$. This implies that
$Z_{X}\stackrel{{\scriptstyle\textup{up}}}{{\thicksim}}Z_{Y}$, contradicting
that $0_{Z_{X}}$ is meet-irreducible or that
$Z_{X}\stackrel{{\scriptstyle\textup{dn}}}{{\thicksim}}Z_{Y}$, contradicting
that $0_{Z_{Y}}$ is meet-irreducible. ∎

By Corollary 2, the set of maximal elements of $\mathcal{P}$ is the same as
the set of colors of edges in the upper boundaries, which set we can partition
into the set of colors of edges in the upper-left and upper-right boundaries.
No two distinct elements in the same subset have a common lower cover by Lemma
8. This verifies the Partition Property.

##  4\. The Maximal Cover Property

Let $x\in\mathcal{P}$ be covered by a maximal element $y$ of $\mathcal{P}$. By
Corollary 3, there is a covering $\mathsf{N}_{7}$ such that
$\textup{col}(M)=x$ and $\textup{col}(L)=y$, using the notation of Figure 1.
Moreover, $\textup{col}(L)$ and $\textup{col}(R)$ are the only covers of $x$
in $\mathcal{P}$. By Corollary 2, there is an edge $U$ in the upper-left
boundary, so that $U\stackrel{{\scriptstyle\textup{dn}}}{{\thicksim}}L$.
Similarly, there is an edge $V$ in the upper-right boundary, so that
$V\stackrel{{\scriptstyle\textup{dn}}}{{\thicksim}}R$. So if the Maximal Cover
Property fails, then $\textup{col}(L)=\textup{col}(R)$. This contradicts
Corollary 1(i).

##  5\. The No Child Property

By way of contradiction, let us assume that there are elements
$a,b,c,d\in\mathcal{P}$ with $b\neq c\prec a$, $d\prec b,c$ in $\mathcal{P}$,
where $a$ is maximal in $\mathcal{P}$. By Corollary 2, the element $a$ colors
an edge $A$ in the upper boundary of $K$, say, in the upper-left boundary.

By Corollary 3, we get a covering $\mathsf{N}_{7}$, with middle edge $B$,
upper-left edge $L$ satisfying that $\textup{col}(B)=b$ and
$A\stackrel{{\scriptstyle\textup{dn}}}{{\thicksim}}L$. Similarly, we get
another covering $\mathsf{N}_{7}$, with middle edge $C$ and upper-left edge
$L^{\prime}$ satisfying that $\textup{col}(B)=b$ and
$A\stackrel{{\scriptstyle\textup{dn}}}{{\thicksim}}L^{\prime}$. By Lemma 7,
$\textup{traj}{(B})$ and $\textup{traj}{(C})$ are disjoint, contradicting the
existence of the element $d\prec b,c\in\mathcal{P}$, see Corollary 1(ii).

##  6\. The Four-Crown Two-pendant Property

By way of contradiction, assume that the ordered set $\mathcal{R}$ of Figure 1
is a cover preserving ordered subset of $\mathcal{P}$, where $a,b,c,d$ are
maximal elements of $\mathcal{P}$. By Corollary 2, there are edges $A,B,C,D$
on the upper boundary of $K$, so that $\textup{col}(A)=a$,
$\textup{col}(B)=b$, $\textup{col}(C)=c$, $\textup{col}(D)=d$. By left-right
symmetry, we can assume that the edge $A$ is on the upper-left boundary of
$K$. Since $p\prec a,b$ in $\mathcal{P}$, it follows from Lemma 8 that the
edge $B$ cannot be on the upper-left boundary of $K$. So $B$ is on the upper-
right boundary of $K$, and so is $D$. Similarly, $C$ is on the upper-left
boundary of $K$. So there are four cases, (i) $C$ is below $A$ and $B$ is
below $D$; (ii) $C$ is below $A$ and $D$ is below $B$; and so on. The first
two are illustrated in Figure 3.

Figure 3. Illustrating the proof of The Four-Crown Two-pendant Property

We consider the first case. By Corollary 3 (see Figure 2), there is a covering
$\mathsf{N}_{7}$ with middle edge $P$ (as in the first diagram of Figure 3) so
that $A$ and $B$ are down-perspective to the left-upper edge and the right-
upper edge of the covering $\mathsf{N}_{7}$, respectively. We define,
similarly, the edge $Q$ for $C$ and $B$, the edge $S$ for $A$ and $D$, the
edge $R$ for $C$ and $D$, and the edge $U$ for $R$ and $P$.

The ordered set $\mathcal{R}$ is a cover preserving subset of $\mathcal{P}$,
so we get the covering $\mathsf{N}_{7}$ with middle edge $U$, upper-left edge
$U_{l}$ and upper-right edge $U_{r}$; the edge $U$ is collapsed by
$\textup{con}(P)\wedge\textup{con}(R)$. Then
$R\stackrel{{\scriptstyle\textup{dn}}}{{\thicksim}}U_{l}$ and
$P\stackrel{{\scriptstyle\textup{dn}}}{{\thicksim}}U_{r}$, contradicting that
$\textup{traj}{(P})$ and $\textup{traj}{(R})$ do not meet in a $4$-cell since
$\ell(P)$ and $\ell(R)$ are both  and so parallel. This conludes the proof of
the Four-Crown Two-pendant Property and of Czédli’s Theorem.

Of course, the diagrams in Figure 3 are only illustrations. The grid could be
much larger, the edges $A,C$ and $B,D$ may not be adjacent, and there maybe
lots of other elements in $K$. However, our argument only utilized what is
true (for instance, that some edges are ) whatever the configuration.

The second case is similar, except that we get the edge $V$ and cannot get the
edge $U$. The third and fourth cases follow the same way.

## References

  * [1] Czédli, G.: Diagrams and rectangular extensions of planar semimodular lattices. Algebra Universalis 77, 443–498 (2017)
  * [2] Czédli, G.: Lamps in slim rectangular planar semimodular lattices.
`http://arxiv.org/abs/2101.0292`

  * [3] Czédli, G., Schmidt, E. T.: Slim semimodular lattices. I. A visual approach. ORDER 29, 481-497 (2012)
  * [4] G. Grätzer, Congruences of fork extensions of lattices. Algebra Universalis 76 (2016), 139-154.
  * [5] Grätzer, G.: Congruences in slim, planar, semimodular lattices: The Swing Lemma. Acta Sci. Math. (Szeged) 81, 381–397 (2015)
  * [6] Grätzer, G.: The Congruences of a Finite Lattice, A Proof-by-Picture Approach, second edition. Birkhäuser, 2016. xxxii+347.
  * [7] G. Grätzer, Congruences and trajectories in planar semimodular lattices. Discussiones Mathematicae 38 (2018), 131–142.
  * [8] G. Grätzer, Notes on planar semimodular lattices. IX. On Czédli diagrams. http://arxiv.org/abs/2104.02534
  * [9] G. Grätzer and E. Knapp, Notes on planar semimodular lattices. I. Construction. Acta Sci. Math. (Szeged) 73 (2007), 445–462.
  * [10] G. Grätzer, Notes on planar semimodular lattices. IX. On Czédli diagrams.
http://arxiv.org/abs/2104.02534

  * [11] G. Grätzer and E. Knapp, Notes on planar semimodular lattices. III. Rectangular lattices. Acta Sci. Math. (Szeged) 75 (2009), 29–48.