# Hybrid classical-quantum text search based on hashing

Farid Ablayev &Marat Ablayev &Nailya Salikhova

###### Abstract

The paper considers the problem of finding a given substring in a text. It is
known that the complexity of a classical search query in an unordered database
is linear in the length of the text and a given substring. At the same time,
Grover’s quantum search provides a quadratic speedup in the complexity of the
query and gives the correct result with a high probability.

We propose a hybrid classical-quantum algorithm (hybrid random-quantum
algorithm to be more precise), that implements Grover’s search to find a given
substring in a text. As expected, the algorithm works a) with a high
probability of obtaining the correct result and b) with a quadratic query
acceleration compared to the classical one.

What’s new is that our algorithm uses the uniform hash family functions
technique. As a result, our algorithm is much more memory efficient (in terms
of the number of qubits used) compared to previously known quantum algorithms.

##  1 Introduction.

Quantum search algorithms and its generalizations [1, 2, 3, 4, 5] are part of
a group of quantum algorithms that are of great interest in computer science.

The using of quantum computers can significantly reduce the computation time
for models with a large number of weights, or those requiring an exponentially
growing number of combinations. We presented a review of some results in the
field of quantum approaches to classification and information retrieval in the
papers [6, 7].

The task of finding occurrences of a given substring in a text is important
problem of information retrieval. It occurs in a wide range of applications,
namely, in text editors, in search robots, spam filters, bioinformatics, etc.
A large number of algorithms (deterministic and probabilistic) for solving the
search problem have been developed over the past few decades. Quantum
algorithms for solving the search problem have been developed in the last two
decades.

#####  Problem.

Given a binary $N$ length sequence

$string=b_{1}\dots b_{N}$

and a binary $m$ length sequence $w$, $m<N$. It is required to find the index
of the occurrence of the substring $w$ in the text $string$. Namely, it is
required to find an index $k$ such that $w=b_{k}\dots b_{k+m-1}$.

##### Related work.

The known Knuth-Morris-Pratt’s [8] classical algorithm (1977) solves the
problem in linear time $O(m+n)$.

In the early 2000s, a quantum algorithm [9] for searching for a given
substring in a text was presented. It allows to get quadratic search speed-up.
It returns one of the indexes of the occurrence of the searched substring. The
probability of getting the correct answer is strictly greater than 1/2. The
query complexity (this measure of complexity is sometimes associated with time
complexity) of an algorithm is
$O(\sqrt{n}\log{\sqrt{\frac{n}{m}}}\log{m}+\sqrt{m}\log^{2}{m})$. The authors
[9] do not estimate the memory complexity (number of used qubits) of their
algorithm. An analysis shows that the [9] algorithm requires $O(\log{n}+m)$
qubits.

#####  Our contribution.

We present a quantum algorithm for finding a pattern in a string. The
algorithm is based on Grover’s search algorithm and hashing technique. It is
known that the hashing method can significantly save space and, as a rule, the
time required for searching in databases. The results of the paper demonstrate
the potential of a universal hashing method for building quantum search
algorithms.

To simplify the presentation, not to clutter the idea with technical details,
consider the case when it is known in advance that the desired substring
occurs in the text exactly once.

More precisely, we propose a hybrid random-quantum search algorithm $\cal A$
that searches a text for a substring and has the following characteristics:

  * •

The $\cal A$ algorithm produces a result with a high probability of obtaining
the correct answer.

  * •

The $\cal A$ algorithm is based on Grover’s search. This search is presented
in the paper as an auxiliary algorithm ${\cal A}1$ and requires $O(\sqrt{n})$
query steps.

  * •

The $\cal A$ algorithm exponentially saves (compared to the [9] algorithm) the
number of qubits relative to the parameter $m$ – the length of the substring.
Namely, the algorithm requires $O(\log{n}+\log{m})$ qubits for his work.

The main idea of the paper is the use of hashing technique to save space
complexity in quantum search. The ${\cal A}$ algorithm is based on a certain
universal family of hash functions. The ${\cal A}2$ algorithm is a
generalization of the result to a general universal hash family of functions.

The result of the work is organized as follows. In the next section (Section
2), we present the basic model of the quantum search algorithm, basic notation
and definitions. In Section 3 we present the main result. We first present the
auxiliary quantum procedure ${\cal A}1$. Next, we present a quantum search
algorithm ${\cal A}$ based on the hashing technique. Theorem 1 is an analysis
of the ${\cal A}$ algorithm. In Section 5, we present the ${\cal A}2$
algorithm, a generalization of the ${\cal A}$ algorithm.

The preliminary version of the article was published in Russian [10].

##  2 Preliminaries for quantum query algorithm

We refer the reader to the [5, 11] for an introduction to the basics of
quantum query algorithms and the state of research in this area. Here we
define the query model of computations in a way that is convenient for us. We
use the notation defined in detail in [6, 7].

The operations applied to quantum $s$-qubit states
${\left|{\psi}\right\rangle}\in{({\cal{H}}^{2})}^{\otimes s}$ are
mathematically expressed using unitary operators:

${\left|{\psi^{\prime}}\right\rangle}=U{\left|{\psi}\right\rangle},$ (1)

where $U$ is a $2^{s}\times 2^{s}$ unitary matrix.

##### Query model.

For a finite sets $X$ and $Y$ let

$g:X\to Y$

be a discrete function. A quantum query algorithm $\cal A$ computing the
function $g$ begins in a quantum state $|\psi_{start}\rangle$ and applies a
sequence of operators

${\cal O}_{X},{\cal U},\dots,{\cal O}_{X},{\cal U},$

The operator ${\cal O}_{X}$ depends on the input $X$. The quantum community
calls the ${\cal O}_{X}$ operator an “oracle”. Application of the oracle is
called the query of the algorithm $\cal A$ to the initial data $X$. The
operator $\cal{U}$ does not depend on $X$.

The algorithm computes the value $g(\sigma)$ of the discrete function $g$ for
$\sigma\in X$ if the initial state $|\psi_{start}\rangle$ goes to the final
state

${\left|{\psi(g(\sigma))}\right\rangle}={\cal U}{\cal O}_{\sigma}\cdots{\cal
U}{\cal O}_{\sigma}{\left|{\psi_{start}}\right\rangle},$

in the process of computing on the input value $\sigma$. The final state
allows extracting the value of $g(\sigma)$ as a result of measuring the state
of ${\left|{\psi(g(\sigma))}\right\rangle}$.

##### Search in an unordered database.

Quantum search algorithm in an unordered database of $n$ elements, in which
there is exactly one element of interest to us (Grover’s algorithm) is a
special case of a group of query algorithms. The following algorithm scheme
underlies many generalizations.

  1. 1.

Initialize a quantum system of $O(\log n)$ qubits into a
${\left|{\psi_{start}}\right\rangle}$ state containing information about the
database. The ${\left|{\psi_{start}}\right\rangle}$ state is constructed so
that each of the $2^{O(\log n)}$ basis quantum states represents the required
information about $n$ database elements.

  2. 2.

The following $O(\sqrt{n})$ “macro” steps are performed on the
${\left|{\psi_{start}}\right\rangle}$ state

     * •

The oracle ${\cal O}_{X}$ is used. It recognizes the basis state of interest
to us and multiplies its amplitude by -1.

     * •

The operator $\cal U$ performs the inversion by the average value over all
amplitudes.

“Macro” Step 2 describes the key operation of quantum search. Each such step
increases the amplitude of the basis state that represents the desired
information. The number $O(\sqrt{n})$ of such steps maximizes the amplitude,
and the probability of extracting the required information from the resulting
state ${\left|{\psi_{final}}\right\rangle}$ becomes close to 1.

#####  Basic operations of qubits for quantum search.

The potential advantages of quantum algorithms, on which the results of this
work are based, lie in the possibility of implementing quantum operators of
dimension $2^{s}\times 2^{s}$ by basic operations based on a small number of
order $O(s)$ qubits and in a small number of quantum computing steps (not a
complex scheme implemented by basic elements).

Main operations are $I,X,Z,H$.

  * •

$I$ \- identity operator.

$I=\left(\begin{array}[]{cc}1&0\\\ 0&1\end{array}\right).$

  * •

$X$ \- is a NOT operator. It changes the state of the qubit from
${\left|{0}\right\rangle}$ to ${\left|{1}\right\rangle}$, and vice versa.

$\begin{array}[]{l}X=\left(\begin{array}[]{cc}0&1\\\
1&0\end{array}\right).\end{array}$ (2)

  * •

$Z$ \- amplitude sign reversal operator.

$\begin{array}[]{l}Z=\left(\begin{array}[]{cc}1&0\\\
0&-1\end{array}\right).\end{array}$ (3)

  * •

$H$ \- Hadamard operator.

$\begin{array}[]{l}H=\frac{1}{\sqrt{2}}\left(\begin{array}[]{cc}1&1\\\
1&-1\end{array}\right).\end{array}$ (4)

#####  Characteristics of the ${\cal A}$ algorithm.

The characteristics of a quantum query algorithm are the used memory, the
number of queries to the analyzed data, and the probability of an error.

> Size complexity (Memory complexity). The number $S({\cal A})$ of used qubits
> is a measure of the memory complexity of the quantum algorithm ${\cal A}$.
>
> We denote by $S^{\cal A}(string,w)$ the number of qubits used by the $\cal
> A$ algorithm to solve the problem of finding the substring $w$ in the
> $string$.
>
> Through $S^{\cal A}(n,m)$ we denote the maximum among the numbers $S^{\cal
> A}(string,w)$ over all $string$ and $w$ with parameters
> $N=|string|,m=|w|,n=N-m+1$.
>
> Query complexity. The number $Q({\cal A})$ of queries (number of the oracle
> applications) is a “query” measure of the complexity of the quantum
> algorithm ${\cal A}$. Note that in [11], one request to the oracle is
> testing one variable (one bit). Accordingly, in our work, one request to the
> oracle is implemented in the process of testing the entire string $w$ (hash
> values of $w$).
>
> We denote by $Q^{\cal A}(string,w)$ the number of applications by the
> algorithm $\cal A$ of the oracle operator.
>
> Through $Q^{\cal A}(n,m)$ we denote the maximum among the numbers $Q^{\cal
> A}(string,w)$ over all $string$ and $w$ with parameters
> $N=|string|,m=|w|,n=N-m+1$.
>
> Error probability.
>
> We denote by $Er^{\cal A}(string,w)$ the probability of the following event.
> The algorithm $\cal A$ as a result of solving the problem of finding the
> substring $w$ in the text $string$ gives the number $k$ of the position in
> the text $string$ such that $w_{k}\not=w$.
>
> Through $Er^{\cal A}(n,m)$ we denote the maximum among the numbers $Er^{\cal
> A}(string,w)$ over all $string$ and $w$ with parameters
> $N=|string|,m=|w|,n=N-m+1$.

##  3 Algorithms for finding the index of occurrence of a substring in the
text.

In this section, we present a hybrid classical-quantum algorithm (more
precisely, a hybrid random-quantum algorithm) ${\cal A}$ for finding a
substring $w$ of length $m$ in a binary text

$string=b_{1}\dots b_{N}.$

We consider the simplest version of the problem: we assume that the required
substring $w$ is guaranteed to occur exactly once in the text $string$.

The problem is reduced to a problem of finding word $w$ in a vocabulary as
follows. Let $n=N+1-m$. To simplify presentaion, we assume below that the
number $n$ (the number of substrings in the $string$) is a power of 2. Denote
by $V(string,m)$

a sequence composed of all substrings of length $m$ of the $string$

$V(string,m)=\\{w_{0},\dots,w_{n-1}\\},$

where $w_{k}=b_{k+1}\dots b_{k+m}$ for $0\leq k\leq n-1$. We will call
$V(string,m)$ a vocabulary.

Now the problem of finding the word $w$ in $string$ is represented as the
problem of finding an index $k$ such that $w=w_{k}$ for the vocabulary
$V(string,m)$.

###  3.1 Auxiliary quantum procedure ${\cal A}1$.

The quantum part of the algorithm is the following auxiliary quantum procedure
${\cal A}1$. Procedure ${\cal A}1$ starts with an initial quantum state
${\left|{string}\right\rangle}$ (quantum vocabulary) constructed from the
vocabulary $V$ using the preprocedure $\cal P$.

Pre-procedure $\cal P$ generates the initial state (quantum vocabulary)
${\left|{string}\right\rangle}$ from vocabulary $V=\\{v_{0},\dots,v_{n-1}\\}$
composed of binary words of length $l\geq 1$. The
${\left|{string}\right\rangle}$ state has the following structure

${\left|{string}\right\rangle}=\frac{1}{\sqrt{n}}\sum\limits_{k=0}^{n-1}{\left|{k}\right\rangle}\otimes{\left|{v_{k}}\right\rangle}\otimes{\left|{1}\right\rangle}.$

##### Description of the procedure ${\cal A}1$

> Input: Quantum state ${\left|{string}\right\rangle}$. Binary word $v$.
>
> Output: The index $k$, which is interpreted as an index such that $v=v_{k}$.

That is, ${\cal{A}}1({\left|{string}\right\rangle},v)$ implements the mapping

${\cal{A}}1:{\left|{string}\right\rangle},v\longmapsto k.$

The following two macro steps, described below in operator form, are applied
to the state ${\left|{string}\right\rangle}$ $\frac{\pi}{4}\sqrt{n}$ times. In
the literature, these two macro steps are often referred to as the “Grover
iteration” [1].

  * •

The oracle ${\cal O}_{f_{v}}$ operation of changing the phase of the state
representing information about $v_{k}$, for which $v_{k}=v$ is performed. For
a binary sequence $v\in\\{0,1\\}^{l}$ define the Boolean function
$f_{v}:\\{0,1\\}^{l}\rightarrow\\{0,1\\}$ by the condition: $f_{v}(x)=1$ if
and only if $x=v$.

Let ${\left|{x}\right\rangle}$ denotes the basic state corresponding to the
element $x$, which is one of $v_{k}$. In this case, ${\left|{x}\right\rangle}$
is the $l$ \- qubit basis state. Oracle ${\cal O}_{f_{v}}$ performs the
following three actions:

    1. 1.

Application of the $H$ operator on the auxiliary ($\log{n}+l+1$)-th qubit
${\left|{1}\right\rangle}$:

${\left|{x}\right\rangle}\otimes{\left|{1}\right\rangle}\quad\xrightarrow{I^{\otimes{\log{n}+l}}\otimes
H}\quad{\left|{x}\right\rangle}\otimes\frac{1}{\sqrt{2}}({\left|{0}\right\rangle}-{\left|{1}\right\rangle})$

    2. 2.

Application of the operator $U_{f_{v}}$ on the last $l+1$ qubits:

$\displaystyle{\left|{x}\right\rangle}\otimes\frac{1}{\sqrt{2}}({\left|{0}\right\rangle}-{\left|{1}\right\rangle})$
$\displaystyle\quad\xrightarrow{I^{\otimes{\log{n}}}\otimes
U_{f_{v}}}\quad\frac{1}{\sqrt{2}}{\left|{x}\right\rangle}\otimes({\left|{0\oplus
f_{v}(x)}\right\rangle}-{\left|{1\oplus f_{v}(x)}\right\rangle})=$
$\displaystyle=(-1)^{f_{v}(x)}{\left|{x}\right\rangle}\otimes\frac{1}{\sqrt{2}}({\left|{0}\right\rangle}-{\left|{1}\right\rangle})$

    3. 3.

Application of the $H$ operator on the auxiliary ($\log{n}+l+1$)-th qubit
${\left|{1}\right\rangle}$:

$\displaystyle(-1)^{f_{v}(x)}{\left|{x}\right\rangle}\otimes\frac{1}{\sqrt{2}}({\left|{0}\right\rangle}-{\left|{1}\right\rangle})$
$\displaystyle\quad\xrightarrow{I^{\otimes{\log{n}+l}}\otimes
H}\quad(-1)^{f_{v}(x)}{\left|{x}\right\rangle}\otimes{\left|{1}\right\rangle}$

Note that the auxiliary qubit at the end restores its value (by repeated
application of the Hadamard transformation) to the ${\left|{1}\right\rangle}$
state.

  * •

Inversion operation.  ${\cal D}$ = 2${\cal R}$ \- $I^{\otimes\log{n}}$ –
operator applied on the first $n$ qubits. The $\cal{R}$ operator is given in
matrix form:

${\cal R}=\frac{1}{\log{n}}\left(\begin{array}[]{cccc}1&1&\dots&1\\\
1&1&\dots&1\\\ \vdots&\dots&\ddots&\vdots\\\ 1&1&\dots&1\end{array}\right)$

Getting the result of computation (the output of the ${\cal A}1$). After
running the macro steps above $\frac{\pi}{4}\sqrt{n}$ times, we measure the
first $\log{n}$ qubits in the computational basis. The resulting $\log n$ bits
are interpreted as a binary representation of the required index $k$.

###  3.2  Algorithm ${\cal A}$.

The algorithm consists of two sequentially working parts:

  * •

First part: preparing the initial state based on the dictionary $V(string,m)$.

  * •

Second part: reading the search word $w$ and searching for its occurrence in
the vocabulary.

We emphasize that the algorithm ${\cal A}$ has two different input sets:
$V(string,m)$ and $w$. These sets are fed to the first and second parts of the
algorithm ${\cal A}$, respectively.

Notations.

  * •

For a binary string $w$ of length $m$, denote by $a(w)$ the number represented
by $w$, $0\leq a(w)\leq 2^{m}-1$.

Given a number $a\in\\{0,\dots,2^{m}-1\\}$, denote by $bin(a)$ its binary
representation of length $m$.

  * •

For the vocabulary $V(string,m)$, let $V_{p}$ denote the following vocabulary

$V_{p}=\\{v(w_{0}),\dots,v(w_{n-1})\\},$

where $v(w_{k})=bin(r(w_{k})_{p})$ and $r(w_{k})_{p}$ is the $p$-remainder of
$a(w_{k})$. That is, $a(w_{k})=cp+r(w_{k})_{p}$, where $c\geq 0$ and
$r(w_{k})_{p}\in\\{0,\dots,p-1\\}$.

  * •

Denote by $P_{d}=\\{p_{1},\dots,p_{d}\\}$ the set of first $d$ primes.

#### Description of the algorithm ${\cal{A}}$.

> Input:
>
> For the first part: Vocabulary $V(string,m)$.
>
> For the second part: Binary word $w$ of length $m$.
>
> Output: The index $k$, which is interpreted as an index such that $w=w_{k}$.

That is, ${\cal{A}}$ implements the mapping

${\cal{A}}:V(string,m),w\longmapsto k.$

The first part of the algorithm  is to prepare the initial state from the
vocabulary $V(string,m)$:

  * •

First, the algorithm makes a classical random choice: a prime number $p$ is
uniformly and randomly selected from the set $P_{d}$ and the vocabulary
$V_{p}$

$V_{p}=\\{v(w_{0}),\dots,v(w_{n-1})\\}$

prepared from the vocabulary $V(string,m)$.

  * •

Second step consists of preparation of quantum state
${\left|{string,p}\right\rangle}$ composed of $V_{p}$

${\left|{string,p}\right\rangle}=\frac{1}{\sqrt{n}}\sum\limits_{k=0}^{n-1}{\left|{k}\right\rangle}\otimes{\left|{v(w_{k})}\right\rangle}\otimes{\left|{1}\right\rangle}.$

The second part of the algorithm  is to read the input word $w$ and find $k$
such that $w=w_{k}$:

  * •

The algorithm reads the input word $w$ and prepares $v(w)=bin(r(w)_{p})$.

  * •

The quantum stage of the algorithm ${\cal{A}}$: quantum procedure ${\cal{A}}1$
is applied with the input ${\left|{string,p}\right\rangle}$ and word $v(w)$.
${\cal{A}}1$ implements the mapping

${\cal{A}}1:({\left|{string,p}\right\rangle},v(w))\longmapsto k.$

to the state ${\left|{string,p}\right\rangle}$ and the search word $v(w)$. The
number $k$ is the result of measuring the first $\log{n}$ qubits. The number
$k$ is declared as the required number of the word $w_{k}$ such that
$w=w_{k}$.

###  3.3 Characteristics of the algorithm $\cal A$

The following theorem describes the characteristics of the main part of the
$\cal A$ algorithm (searching for the $w$).

######  Theorem 1.

For a vocabulary $V=V(string,m)=\\{w_{0},\dots,w_{n-1}\\}$ of words of length
$m$, for a word $w$ of length $m$ algorithm $\cal A$ solves the problem of
finding index $k$ such that $w=w_{k}$ with the following characteristics.

For an arbitrary integer $c\geq 3$, for an integer $d=cnm$ it is true that

$\displaystyle S^{{\cal A}}(n,m)$ $\displaystyle=O(\log{n}+\log{m}),$
$\displaystyle Q^{{\cal A}}(n,m)$ $\displaystyle=O(\sqrt{n}),$ $\displaystyle
Er^{\mathcal{A}}(V,w)$ $\displaystyle\leq\frac{1}{c}+\frac{1}{n}.$

The proof of Theorem 1 is given in the next section.

##  4 Proof of Theorem1

###  4.1 Space complexity $S_{\epsilon}^{{\cal A}}(n,m)$.

We start with the technical Lemma we need below.

######  Lemma 1.

For arbitrary $p\in P_{d}$, for $d=cnm$, for vocabulary

$V_{p}=\\{v(w_{0}),\dots,v(w_{n-1})\\},$

generated from vocabulary $V$ and for a word $v(w)$ formed from the word $w$
of length $m$ it is true that

$|v(w)|=O(\log{n}+\log m),\qquad|v(w_{k})|=O(\log{n}+\log m).$

Proof. Due to the Theorem condition we select the set $P_{d}$ of the first $d$
primes, where $d=cnm$. Due to Chebyshev’s theorem there exist constants
$0<a<A$ such that for all $d=1,2,…,$ the $d$-th prime number $p_{d}$ satisfies
the inequalities

$ad\ln d<p_{d}<Ad\ln d.$

That is, for arbitrary $p\in P_{d}$ and $r\leq p$ it is true that

$bin(r)\leq\log(Ad\ln d)=O(\log n+\log m).$

$\Box$

To estimate the space complexity characteristic $S_{\epsilon}^{{\cal
A}}(n,m)$, consider the quantum state ${\left|{string,p}\right\rangle}$ formed
on the basis of $V_{p}$

${\left|{string,p}\right\rangle}=\frac{1}{\sqrt{n}}\sum\limits_{k=0}^{n-1}{\left|{k}\right\rangle}\otimes{\left|{v(w_{k})}\right\rangle}\otimes{\left|{1}\right\rangle}.$

First. $\log{n}$ qubits are needed to encode ${\left|{k}\right\rangle}$ basis
states. Second. According to the 1 Lemma, $O(\log n+\log m)$ qubits are needed
to encode ${\left|{v(w_{k})}\right\rangle}$ basis states. Thus, we have
$S_{\epsilon}^{{\cal A}}(n,m)=O(\log{n}+\log m)$.

###  4.2 The query complexity $Q^{\cal A}(n,m)$.

The query complexity $Q^{\cal A}(n,m)$ of algorithm ${\cal A}$ completely
determined by the query complexity $Q^{{\cal A}1}(n,m)$ of the auxiliary
procedure ${\cal A}1$ when ${\cal A}1$ takes as input the quantum state
${\left|{string,p}\right\rangle}$. Recall that
${\left|{string,p}\right\rangle}$ represents (quantumly) the vocabulary
$V_{p}$ for $p\in P_{d}$ with $d$ satisfying the condition of the theorem.

######  Property 1.

Let $p\in P_{d}$ with $d=cnm$. Let ${\left|{string,p}\right\rangle}$ be the
quantum state generated by $V_{p}$, where $V_{p}$ itself formed by the
vocabulary $V(string,m)$. Let a word $v(w)$ formed from $w$. Then for the
${\cal A}1({\left|{string,p}\right\rangle},v(w))$ the following is true

$\displaystyle Q^{{\cal A}1}(n,m)$ $\displaystyle=O(\sqrt{n})$ (5)

Proof. Let us consider the amplitude amplification procedure when the
procedure ${\cal A}1$ is applied to the initial state
${\left|{string,p}\right\rangle}$. Let’s put
${\left|{string_{0}}\right\rangle}={\left|{string,p}\right\rangle}$. Let us
denote the following numbers by $\alpha_{0}$ and $\beta_{0}$: $\alpha_{0}$ is
the initial amplitude for the required basic state
${\left|{k}\right\rangle}{\left|{v(w_{k})}\right\rangle}{\left|{1}\right\rangle}$
such that $v(w_{k})=v(w)$, and $\beta_{0}$ are the amplitudes of all other
basic states of the initial state ${\left|{string_{0}}\right\rangle}$.

$\alpha_{0}=1/\sqrt{n}=\beta_{0}=1/\sqrt{n}$ and
$\alpha_{0}^{2}+(n-1)\beta_{0}^{2}=1$.

By virtue of the introduced notation, the state
${\left|{string_{0}}\right\rangle}$ can be represented in the following form:

${\left|{string_{0}}\right\rangle}=\alpha_{0}\sum_{k:v(w_{k})=v(w)}{\left|{k}\right\rangle}\otimes{\left|{v(w_{k})}\right\rangle}\otimes{\left|{1}\right\rangle}+\beta_{0}\sum_{k:v(w_{k})\neq
v(w)}{\left|{k}\right\rangle}\otimes{\left|{v(w_{k})}\right\rangle}\otimes{\left|{1}\right\rangle}.$

After applying successively $j$ times two macrosteps to the initial state
${\left|{string_{0}}\right\rangle}$

1) The operation of changing the phase of the state representing information
about $w_{k}$, for which $v(w_{k})=v(w)$ is performed and

2) The inversion operations (called in the literature Grover’s iteration), the
amplitudes of the $(j+1)$-th state of the
${\left|{string_{j+1}}\right\rangle}$ will be expressed by formulas (see, for
example, [12] for a detailed technical justification for the effects of
operators 1), and 2) on ${\left|{string_{j}}\right\rangle}$ states):

$\alpha_{j+1}=\frac{n-2}{n}\alpha_{j}+\frac{2(n-1)}{n}\beta_{j}\quad\beta_{j+1}=\frac{n-2}{n}\beta_{j}-\frac{2}{n}\alpha_{j}.$

We have:

${\left|{string_{j+1}}\right\rangle}=\alpha_{j+1}\sum_{k:v(w_{k})=v(w)}{\left|{k}\right\rangle}\otimes{\left|{v(w_{k})}\right\rangle}\otimes{\left|{1}\right\rangle}+\beta_{j+1}\sum_{k:v(w_{k})\neq
v(w)}{\left|{k}\right\rangle}\otimes{\left|{v(w_{k})}\right\rangle}\otimes{\left|{1}\right\rangle},$

where (recall that we are considering the case when $k$ for which
$v(w_{k})=v(w)$ is the only number).

$\alpha_{j+1}^{2}+(n-1)\beta_{j+1}^{2}=1$

Therefore, $\alpha$ and $\beta$ can be given as

$\alpha_{j}=\sin{((2j+1)\theta)},\quad\beta_{j}=\frac{1}{\sqrt{n-1}}\cos{((2j+1)\theta)}$

Further, $\alpha_{r}=1$ if $(2r+1)\theta={\pi}/{2}$. Based on these
considerations, the optimal number $r$ of iterations of the search algorithm
$r={(\pi-2\theta)}/{4\theta}$ is determined.

[12] shows that the probability of getting an incorrect result does not exceed
${1}/{n}$ if you run $[{\pi}/{(4\theta)}]$ of Grover’s iterations in
succession. If $n$ is a sufficiently large number, then
$\theta\approx\sin{\theta}={1}/{\sqrt{n}}$, then

$r=\frac{\pi}{4}\sqrt{n}.$

Since one call to the oracle in the algorithm is testing an entire substring,
the final value is $Q^{{\cal A}1}(n,m)=O(\sqrt{n})$. $\Box$

###  4.3 The error $Er^{\cal A}(V,w)$

The proof of the upper bound for the error probability $Er^{{\cal A}}(V,w)$ is
based on the following considerations. For $V$ and the desired word $w$, we
split the set $P_{d}$ of primes into good $P_{good}$ and bad $P_{bad}$.

A prime number $p\in P$ will be considered as good for the $V$ and $w$ if
$r(w)_{p}\not=r(w_{j})_{p}$ for all $w_{j}\in V$ such that $w\not=w_{j}$. That
is, the vocabulary $V_{p}$ with $p\in P_{good}$ (the “good” vocabulary
$V_{p}$) represents the vocabulary $V$ “correctly”, and the vocabulary $V_{p}$
with $p\in P_{bad}$ (the “bad” vocabulary $V_{p}$) represents vocabulary $V$
“wrong”.

Then the error probability $Er^{{\cal A}}(V,w)$ of the algorithm ${\cal A}$
can be estimated from above as follows

$\displaystyle Er^{\cal A}(V,w)$ $\displaystyle\leq$ $\displaystyle
Pr_{bad}+(1-Pr_{bad})Er^{{\cal A}1}$ (6) $\displaystyle\leq$ $\displaystyle
Pr_{bad}+Er^{{\cal A}1},$

where $Pr_{bad}$ is the probability of choosing $p\in P_{bad}$ and $Er^{{\cal
A}1}$ is the error of ${\cal A}1$ when “good” dictionary $V_{p}$ is chosen for
procedure ${\cal A}1$.

Note that, if a bad $p$ occurs, it is possible to obtain the correct result
when applying the ${\cal A}1$ procedure. However, considering all
continuations of the procedure ${\cal A}1$ as erroneous for bad $p$, we only
increase the error probability.

In the remainder of the proof we estimate the $Pr_{bad}$ and $Er^{{\cal A}1}$
components of the sum (6).

######  Property 2.

For $d=cnm$ the following is true

$Pr_{bad}\leq\frac{1}{c}.$

Proof. Observe that $p$ is selected uniformly at random from $P_{d}$. So,
$Pr_{bad}=|P_{bad}|/|P_{d}|$. To estimate the $|P_{bad}|$ consider the
following. For a pair of distinct numbers $a_{1},a_{2}\in\\{0,\dots
2^{m}-1\\}$, we denote by $P_{a_{1},a_{2}}$, the set of primes $p\in P_{d}$
such that $a_{1}\equiv a_{2}\pmod{p}$. For the vocabulary $V$ and the desired
sequence $w$, we have that

$P_{bad}=\bigcup_{v\in V}P_{a(w),a(v)},$ (7)

Note that for an arbitrary pair of distinct numbers
$a_{1},a_{2}\in\\{0,\dots,2^{m}-1\\}$ the following is true

$|P_{a_{1},a_{2}}|\leq m.$ (8)

The idea of proving the inequality (8) is as follows. The number
$a=|a_{1}-a_{2}|$ does not exceed $2^{m}$. Therefore, less than $m$ different
primes can divide $a$. For details of the proof (8), see Lemma 7.4 [13].

Finally combining (7) and (8) we have that

$Pr_{bad}\leq\frac{nm}{cnm}=\frac{1}{c}.$

$\Box$

Now let’s estimate the second term of the sum (6). We estimate the $Er^{{\cal
A}1}$ in the condition when we apply the procedure ${\cal A}1$ for the state
${\left|{string,p}\right\rangle}$. The state ${\left|{string,p}\right\rangle}$
represents (quantumly) the vocabulary

$V_{p}=\\{v(w_{0}),\dots,v(w_{n-1})\\},$

for $p\in P_{good}$. That is, we are in the case where $V_{p}$ represents the
vocabulary $V$ “correctly”. This situation satisfies the condition of Grover’s
search algorithm. So, immediately we have that

$\displaystyle Er^{{\cal A}1}$ $\displaystyle\leq\frac{1}{n}.$ (9)

Now, finally, the probability $Er^{{\cal A}}(string,w)$ is estimated based on
(6) and Property 2 and (9) as follows:

$\displaystyle Er^{{\cal A}}(string,w)$
$\displaystyle\leq\frac{nm}{cnm}+\frac{1}{n}=\frac{1}{c}+\frac{1}{n}.$

Thus, we have that there are few “bad variants” of processing the pair
$string$ and $w$ by the ${\cal A}$ algorithm — their share does not exceed
$1/c$ of the total number of possible processings. In the “good case” of
processing the pair $string$ and $w$, the probability of erroneous processing
is bounded from above by the error probability of the procedure ${\cal A}1$,
which is bounded by $1/n$.

##  5 Generalization

In this section, we present the ${\cal A}2$ algorithm, which is a
generalization of the ${\cal A}$ algorithm in terms of universal family of
hash functions.

The concept of universal hashing is defined in [14] and has been discussed in
sufficient detail in a number of papers, see, for example, [15] and [16]. The
family ${\cal F}=\\{f_{1},\dots,f_{d}\\}$ of ($m,l$)-functions
$f:\\{0,1\\}^{m}\to\\{0,1\\}^{l}$ for $l<m$ is called a universal family of
hash functions if for some $\epsilon\in[0,1]$ and for an arbitrary pair
$v,w\in\\{0,1\\}^{m}$

$\frac{|F_{v,w}|}{|{\cal F}|}\leq\epsilon,$

where $F_{w,v}=\\{f\in{\cal F}:f(v)=f(w)\\}$.

For our purposes, we extend the definition of the universal family of hash
functions as follows.

######  Definition 1.

A family ${\cal F}=\\{f_{1},\dots,f_{d}\\}$ of ($m,l$)-functions

$f:\\{0,1\\}^{m}\to\\{0,1\\}^{l}$

for $n\geq 1$ and $\epsilon\in[0,1]$ will be called a strongly
$(n,\epsilon)$-universal family of hash ($m,l$)-functions if for each
$n$-subset $Set=\\{v_{1},\dots,v_{n}\\}$ of the set $\\{0,1\\}^{m}$ and an
arbitrary word $w\in\\{0,1\\}^{m}$

$\frac{|F_{Set,w}|}{|{\cal F}|}\leq\epsilon,$

where $F_{Set,w}=\bigcup_{v\in Set}F_{v,w}$.

Note that a strongly $(1,\epsilon)$-universal family of hash functions is an
$\epsilon$-universal family of hash functions in the standard sense.

##### Example of a Strongly $(n,\epsilon)$-universal family of hash functions.

An example of a strongly $(n,\epsilon)$-universal family of ($m,l$)-functions
is the set

${\cal F}=\\{f_{1},\dots,f_{d}\\}$

of following functions. For $j\in\\{1,\dots,d\\}$ ($m,l$)-function
$f_{j}:\\{0,1\\}^{m}\to\\{0,1\\}^{l}$ is determined by the $j$-th prime number
$p_{j}$ as follows:

$f_{j}(w)=bin(r(w)_{p_{j}}).$

Here $r(w)_{p_{j}}$ is the remainder $r$ when $a(w)$ is divided by a prime
$p_{j}$ and $bin(r(w)_{p_{j}})$ is the binary presentation of the number
$r(w)_{p_{j}}$. Clearly we have that $l\leq\log p_{d}$.

The family $\cal F$ satisfies the following property.

######  Property 3.

For $c\geq 3$ and $d=cnm$ the set ${\cal F}=\\{f_{1},\dots,f_{d}\\}$ of
($m,O(\log(nm))$)-functions forms a family that is strongly
$(n,1/c)$-universal family of hash ($m,O(\log(nm))$)-functions.

Proof. For the proof see the Property 2 above. $\Box$

We now present the ${\cal A}2$ algorithm – generalization of the ${\cal A}$
algorithm – in terms of a strongly $(n,\epsilon)$-universal family of hash
functions.

Algorithm ${\cal A}2$.

The algorithm consists of two sequentially working parts:

  * •

First part: preparing the initial state based on the dictionary $V(string,m)$.

  * •

Second part: reading the search word $w$ and searching for its occurrence in
the dictionary.

We emphasize that the algorithm ${\cal A}$ has two different input sets:
$V(string,m)$ and $w$. These sets are fed to the first and second parts of the
algorithm ${\cal A}$, respectively.

> Input:
>
> For the first part: Vocabulary $V(string,m)=\\{w_{0},\dots,w_{n-1}\\}$
> composed of binary words of length $m$ from the $string$.
>
> For the second part: Binary word $w$ of length $m$.
>
> Output: The index $k$, which is interpreted as an index such that $w=w_{k}$.

The first part of the algorithm (preparing the initial state):

  * •

The first stage of the algorithm – classical: The function $f$ is chosen
equiprobably from the set ${\cal F}$.

  * •

Second stage (preparation of the quantum state): For the function $f\in{\cal
F}$ and vocabulary $V(string,m)$ the algorithm forms vocabulary

$V_{f}=\\{f(w_{0})\dots,f(w_{n-1})\\}.$

Then, based on $V_{f}$, the following quantum state is generated:

${\left|{string,f}\right\rangle}=\frac{1}{\sqrt{n}}\sum\limits_{k=0}^{n-1}{\left|{k}\right\rangle}\otimes{\left|{f(w_{k})}\right\rangle}\otimes{\left|{1}\right\rangle}.$

The second part of the algorithm (searching for the $w$):

  * •

The third stage (quantum) of the algorithm ${\cal{A}}2$:

quantum procedure ${\cal{A}}1$ is applied with the input
${\left|{string,f}\right\rangle}$ and word $f(w)$. ${\cal{A}}1$ implements the
mapping

${\cal{A}}1:({\left|{string,f}\right\rangle},f(w))\longmapsto k.$

to the state ${\left|{string,f}\right\rangle}$ and the search word $f(w)$.

The number $k$ is the result of measuring the first $\log{n}$ qubits. The
number $k$ is declared as the required number of the word $w_{k}$ such that
$w=w_{k}$.

Now we have the following statement – a generalization of the Theorem 1 for
the ${\cal A}2$ algorithm based on ${\cal F}=\\{f_{1},\dots,f_{d}\\}$ strongly
$(n,\epsilon)$-universal family of ($m,l$)-functions.

######  Theorem 2.

For a vocabulary $V=V(string,m)=\\{w_{0},\dots,w_{n-1}\\}$ of $n$ words of
length $m$, for a word $w$ of length $m$ algorithm ${\cal A}2$ solves the
problem of finding an index $k$ such that $w=w_{k}$, with the following
characteristics

$\displaystyle S^{{\cal A}2}(n,m)$ $\displaystyle=O(\log{n}+l),$
$\displaystyle Q^{{\cal A}2}(n,m)$ $\displaystyle=O(\sqrt{n}),$ $\displaystyle
Er^{{\mathcal{A}}2}(string,w))$ $\displaystyle\leq\epsilon+\frac{1}{n}.$

Proof.  The proof of Theorem 2 repeats word for word the proof of Theorem 1
with only one amendment: it is based on the general family of ${\cal F}$
strongly $(n,\epsilon)$-universal ($m,l$)-functions instead of hash functions
functions of a specific family from the Property 3. $\Box$

##### Comment.

Note that such generalization (algorithm ${\cal A}2$) works effectively when
the length $l$ of hashes is small. As the algorithm $\cal A$ shows, such
algorithms exist – for the algorithm $\cal A$ the parameter $l=O(\log(nm))$,
see Property 3. This provides an upper bound

$S^{\cal A}=O(\log n+\log m).$

##  6 Conclusion.

The paper presents a hybrid classical-quantum algorithm ${\cal A}$ and its
generalization - the quantum algorithm ${\cal A}2$ for finding the occurrence
of the word $w$ in the text $string$. The problem naturally reduces to
searching for a word in the vocabulary $V(string)$ formed from $string$.

The quantum part of algorithms ${\cal A}$ and ${\cal A}2$ presented by the
auxiliary quantum procedure ${\cal A}1$. The quantum procedure ${\cal A}1$ is
essentially Grover’s quantum search algorithm. Here we use the original
conditions for applying Grover’s algorithm, namely, we consider that in the
text $string$ there is (necessarily) a unique occurrence of the word $w$. It
must be said that the calculation of query complexity depends on the direct
implementation of the algorithm. In this work, we consider the oracle as an
appeal to the whole substring, not to its individual bits.

The main declared result in saving the number of qubits used is achieved in
the ${\cal A}$ and ${\cal A}2$ algorithms. The ${\cal A}$ and ${\cal A}2$
algorithms use hash family techniques to save quantum space. The ${\cal A}$
algorithm is based on a specific family of hash functions. This specific
family of hash functions is known as Freivald fingerprints (see, for example,
the book [13], chapter 7 for more information). The ${\cal A}2$ algorithm is
the generalization of the ${\cal A}$ for an arbitrary strongly
$(n,\epsilon)$-universal family of hash functions.

It is important to note that in this paper, as well as in the cited paper [9],
the algorithms are applied to the quantum state (initial state), which is
prepared in advance based on the analyzed text $string$ (on the Vocabulary
$V(string)$ that is formed from the $string$). The preparation of the initial
state requires preliminary work, but this work is not taken into account in
the algorithms. Note that the problem of preparing the initial state, as a
special problem, is beginning to be discussed in the community dealing with
quantum information search. In particular, the authors of [17] drew attention
to the problem of the complexity of preparing the initial state.

Finally, once again, we note that in this paper we considered the case when it
is known in advance that the desired substring occurs in the text exactly
once. The problem can be expanded if the number of occurrences is greater than
1 and is known in advance, and also if the number of occurrences of the
substring is not known in advance. An estimate of the time and space
complexity of Grover’s search algorithm in these cases is described in [12].

## References

  * [1] Grover, Lov K.  A fast quantum mechanical algorithm for database search.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996.
  * [2] Gilliam, Austin and Pistoia, Marco and Gonciulea, Constantin.  Optimizing quantum search using a generalized version of grover’s algorithm.  arXiv preprint arXiv:2005.06468, 2020.
  * [3] Brassard, Gilles and Hoyer, Peter and Mosca, Michele and Tapp, Alain.  Quantum amplitude amplification and estimation.  Contemporary Mathematics, 305:53–74, 2002.
  * [4] Reitzner, Daniel and Nagaj, Daniel and Buzek, Vladimir.  Quantum walks.  arXiv preprint arXiv:1207.7283, 2012.
  * [5] Ronald De Wolf.  Quantum computing: Lecture notes.  arXiv preprint arXiv:1907.09415, 2019.
  * [6] Ablayev, Farid and Ablayev, Marat and Huang, Joshua Zhexue and Khadiev, Kamil and Salikhova, Nailya and Wu, Dingming.  On quantum methods for machine learning problems part i: Quantum tools.  Big Data Mining and Analytics, 3(1):41–55, 2019.
  * [7] Ablayev, Farid and Ablayev, Marat and Huang, Joshua Zhexue and Khadiev, Kamil and Salikhova, Nailya and Wu, Dingming.  On quantum methods for machine learning problems part ii: Quantum classification algorithms.  Big Data Mining and Analytics,3(1):56–67, 2019.
  * [8] Knuth, Donald E and Morris, Jr, James H and Pratt, Vaughan R.  Fast pattern matching in strings.  SIAM journal on computing, 6(2):323–350, 1977.
  * [9] Ramesh, Hariharan and Vinay, V.  String matching in $o(\sqrt{n}+\sqrt{m})$ quantum time.  Journal of Discrete Algorithms, 1(1):103–110, 2003.
  * [10] Marat Faridovich Ablayev and Nailya Maratovna Salikhova.  Quantum search for a given substring in the text using a hashing technique.  Proceedings of Kazan University. Physics & Mathematics Series/Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 162(3), 2020.
  * [11] Andris Ambainis.  Understanding quantum algorithms via query complexity.
  * [12] Boyer, Michel and Brassard, Gilles and Høyer, Peter and Tapp, Alain.  Tight bounds on quantum searching.  Fortschritte der Physik: Progress of Physics, 46(4-5):493–505, 1998\.
  * [13] Rajeev Motwani and Prabhakar Raghavan.  Randomized algorithms.  Cambridge university press, 1995.
  * [14] Carter, J Lawrence and Wegman, Mark N.  Universal classes of hash functions.  Journal of computer and system sciences, 18(2):143–154, 1979.
  * [15] Stinson, Douglas R.  Universal hashing and authentication codes.  In Annual International Cryptology Conference, pages 74–85. Springer, 1991.
  * [16] Stinson, Douglas R. Combinatorial techniques for universal hashing.  Journal of Computer and System Sciences, 48(2):337–346, 1994.
  * [17] Macaluso, Antonio and Clissa, Luca and Lodi, Stefano and Sartori, Claudio.  Quantum ensemble for classification.  arXiv preprint arXiv:2007.01028, 2020.


# Laplace and probability operators on graphs over ordered fields

Anna Muranova  Anna Muranova: Faculty of Mathematics and Computer Science,
University of Warmia and Mazury in Olsztyn, ul. Sloneczna 54, 10-710 Olsztyn,
Poland<EMAIL_ADDRESS>
###### Abstract.

We have investigated properties of eigenvalues of the normalized Laplacian
$\mathcal{L}$ for finite graphs over non-Archimedean ordered fields. We have
proved Cheeger’s inequality for first non-zero eigenvalue. Then we described
properties of the operator $\mathcal{P}=I-\mathcal{L}$, which is analogue of
transition probability matrix. We show that Cheeger estimate
$\alpha_{1}\preceq\sqrt{1-h^{2}}$ for the second largest eigenvalue of
$\mathcal{P}$ is crucial to be able to investigate the convergence for the
analogue of random walk to equilibrium over non-Archimedean ordered fields. We
provide the examples of convergence and non-convergence for graphs over the
Levi-Civita field.

Keywords: weighted graphs, Laplace operator, non-Archimedean field, ordered
field, probability operator, Cheeger constant.
Mathematics Subject Classification 2010:05C50, 05C22, 47A75, 12J15, 39A12

##  1\. Introduction

The eigenvalues of normalized Laplacian $\mathcal{L}$ on weighted graphs is a
classical widely investigated topic. For finite graphs the results are
presented in the classical books and papers on graph theory, like e.g. [1],
[7], [9]. The probability operator $\mathcal{P}$ is the difference of identity
operator and Laplacian. It uniquely describes a random walk on graph. The most
important results are that all eigenvalues of Laplacian lie in $[0,2]$, that
$0$ is always an eigenvalue and that the eigenvalues are symmetric with
respect to $1$ if and only if the graph is bipartite. The branch of results
for probability operator follows from the above mentioned facts. Further one
can consider the Hilbert space of functions from vertices of graph to
$\mathbb{R}$ and investigate properties of $\mathcal{P}$ and $\mathcal{L}$ as
operators on this space. It is known, that random walk converge to an
equilibrium for any given function on finite graph (see e.g. [7], [9]).

We investigate the Laplace and (analogue of) probability operators on graphs,
whose edge weights belong to a non-Archimedean real-closed ordered field
$\mathbb{K}$, following the previous works by author ([15], [16]). We show,
that the results, arising from linear algebra hold also in this settings. More
precisely, we present the prove, that eigenvalues of Laplacian belong to the
same orderedfield, and lie between $0$ and $2$ in the sence of the given
order. Further, they are symmetric with respect to $1$ if and only if the
graph is bipartite. Moreover, some inequalities in terms of number of vertices
also hold for them (see e.g. Proposition 1). We present the direct proofs of
all these facts.

Since there are some works (e.g. [3], [17]111Note, that we do not use any
definitions from there, nor the NAP-theory) on probability operator in non-
Archimedean ordered field, we will call the operator $\mathcal{P}$
_probability operator_ in this paper, keeping in mind, that its matrix has
values between $0$ and $1$ in $\mathbb{K}$. The details about operators are
described in Section 3.

In non-Archimedean fields the fact that eigenvalues of $\mathcal{P}$ are
between $-1$ and $1$ is not enough, to show the convergence of
$\mathcal{P}^{m}f,m\in\mathbb{N}$, $f$ is a function on vertices (or
$\mathcal{P}^{2m}f$ for bipartite graphs) to an equilibrium (i.e. some
function, depending on $f$). Moreover, the convergence it not always the case.
One of the possible ways to investigate the convergence is to use Cheeger
inequality (see Theorem 2):

$\lambda_{1}\succeq 1-\sqrt{1-h^{2}}$

for the smallest non-zero eigenvalue of Laplacian, which leads to
$\alpha_{1}\preceq\sqrt{1-h^{2}}$ for the second largest eigenvalue of
$\mathcal{P}$. Further we show, that in case of non-Archimidean ordered field
there is a crucial difference between two classical formulations of Cheeger’s
inequality:

$\lambda_{1}\succeq{\frac{h^{2}}{2}}\;\;\;\;\;\;\mbox{ and
}\;\;\;\;\;\;\lambda_{1}\succeq 1-\sqrt{1-h^{2}}$

since only the latest one can be used to prove the convergence for the
analogue of random walk.

In Section 5.1 we investigate the convergence for analogue of random walk
(i.e. the convergence of $\mathcal{P}^{m}f$ or $\mathcal{P}^{2m}f$) to
equilibrium, using inequalities, which in the classical (real) case are used
to calculate the rate of convergence. In Theorem 5 we show that, on the
contrary to real case, for any non-bipartite non-complete graph over non-
Archimedean field there is always a subspace of functions, for which random
walk does not converge. Complete graphs show different behavior due to Lemma 5
and we do not describe them in this note.

The largest non-Archimedean ordered field is the field of surreal numbers
([8], [2, Theorem 24.29]), and it is known (e.g. [18]) that the convergent
sequences in classical sense are exclusively constant sequences there.
Therefore, it makes sense to investigate convergence only in some particular
non-archimedean ordered fields. Following the previous work by the same author
([16]), which shows that the Levi-Civita field appears naturally in theory of
electrical networks, in the last section we investigate convergence of
(analogue of) random walk over the Levi-Civita field. Theorem 6 gives the
sufficient condition for convergence for any function on bipartite graph in
terms of Cheeger constant. For non-bipartite non-complete graphs the Theorem 7
describes sufficient conditions for existence of function, foe which the
random walk converges to an equilibrium.

##  2\. Preliminaries

Let $\mathbb{K}$ be an arbitrary real-closed non-Archimedean ordered field (in
fact, an order can be introduced in any real-closed field [12, Theorem 2.2]).
If the ordered field is not real closed, we should consider one if its real
closures, which are all isomorphic due to Artin-Schreier Theorem (see e.g.
[5]) with isomorphism, preserving the order. A field is called _ordered_ if
the property of positivness ($\succ 0$) is defined for its elements, and if it
satisfies the folowing postulates:

  1. (1)

For every element $a\in\mathbb{K}$, just one of the relations

$a\succ 0,a=0,-a\succ 0$

is valid.

  2. (2)

If $a\succ 0$ and $b\succ 0$, then $a+b\succ 0$ and $ab\succ 0$. We write
$a\succ b$ (“$a$ greater than $b$”) if $a-b\succ 0$. We write $a\prec b$ if
$b\succ a$ (“$a$ smaller than $b$”). This is a total order in $\mathbb{K}$.
The signs $\preceq$ and $\succeq$ correspond to “great or equal” and “smaller
or equal” (see [22]).

The set $\mathbb{K}^{+}=\\{a\in\mathbb{K}\mid a\succ 0\\}$ is called a _set of
positive elements_.

An ordered field is _non-Archimedean_ , if there exist an _infinitesimal_
$\epsilon\in\mathbb{K}$, i.e, $\epsilon$ such that $\epsilon\preceq 1/m$ for
any $m\in\mathbb{N}$, where $m=\underbrace{1+\cdots+1}_{m}\in\mathbb{K}$.

An ordered field $\mathbb{K}$ is _real-closed_ if it has no proper algebraic
extension to an ordered field, or, equivalently, if the complexification of
$\mathbb{K}$ is algebraically closed, or, again equivalently, if every
positive element in $\mathbb{K}$ has a square root and every polynomial over
$\mathbb{K}$ of odd degree has a root in $\mathbb{K}$ [5, p. 38].

Let $\mathbb{K}$ be a real-closed field. Further we need a complexification of
$\mathbb{K}$, i.e a field extension $\mathbb{K}(\sqrt{-1})$, which is
algebraically closed. Let us agree, that we pick up one square root of $-1$
and denote it by $\mathbf{i}$. Then we can consider the automorphism of this
field, which maps elements of $\mathbb{K}$ into themselves, and maps
$\mathbf{i}$ to $-\mathbf{i}$. We call this automorphism a _complex
conjugation_ and we denote it further in text by overlining the element (in
the same way as case of usual complex conjugation). We denote
$\mathbb{K}(\mathbf{i})$ by $\mathbb{K}_{C}$.

######  Definition 1.

[15] An _(OF-)graph_ 222in previous works by author it is called _weighted
graph with edge-weights from an ordered field_ , here OF comes from “ordered
field” for the sake of brevity is a couple $(V,b)$, where $V$ is a set of
vertices (i.e. arbitrary set) and $b:V\times V\rightarrow\mathbb{K}$ satisfies
the following properties:

  1. (1)

$b(x,y)\succeq 0$ for any $x,y\in V$,

  2. (2)

$b(x,y)=b(y,x)$ for any $x,y\in V$,

  3. (3)

$b(x,x)=0$ for any $x\in V$.

If $b(x,y)\neq 0$, we say that there is an _edge_ between $x,y$ and write
$x\sim y$.

The third condition means, that we consider graphs without loops. When the
filed $\mathbb{K}$ is relevant, we will say _graph over the field
$\mathbb{K}$_. Note that if instead of $\mathbb{K}$ we use $\mathbb{R}$, then
we obtain a classical definition of a _weighted graph_.

The _path_ in graph is any sequence of vertices $x_{1},x_{2},\dots,x_{n}$ such
that

$x_{1}\sim x_{2}\sim\dots\sim x_{n}.$

The graph is called _connected_ if there exist a path between any two of its
vertices. The graph is called _finite_ if its set of vertices is finite
($\\#V<\infty$). In this note we consider exclusively finite connected graphs.

The graph is called _complete_ if $x\sim y$ for any $x,y\in V$. Otherwise it
is called _non-complete_.

A graph is called _bipartite_ , if there exist a partition of its vertices
$V=~{}V_{1}\cup~{}V_{2}$ such that if $x\sim y$ for $x,y\in V$ then either
$x\in V_{1},y\in V_{2}$ or $x\in V_{2},y\in V_{1}$. Otherwise, the graph is
called _non-bipartite_.

Let us consider the _normalized_ weights

(1) $p(x,y)=\dfrac{b(x,y)}{b(x)},$

where $b(x)=\sum_{y}b(x,y)$. Note, that $p(x,y)\neq p(y,x)$ in general.

It is known that weighted graph can be considered as Hilbert space (e. g. [9],
[11]). We would like to introduce an analogue of scalar product on OF-graphs.

Let us consider a set of functions on vertices of OF-graph

$\mathfrak{F}=\\{f\mid f:V\rightarrow\mathbb{K}\\}$

As an analogue of _scalar_ product for any $f,g\in\mathfrak{F}$ we consider

$\langle f,g\rangle=\sum_{x\in V}f(x)g(x)b(x).$

We list below the properties of this scalar product, which are crucial for us.
These properties coincide with the properties of usual scalar product for
order $>$ on $\mathbb{R}$.

  1. (1)

for any $f,g\in\mathfrak{F}$ holds

$\langle f,g\rangle=\langle g,f\rangle;$

  2. (2)

for any $a,b\in\mathbb{K}$ and for any $f,g\in\mathfrak{F}$ holds

$\langle af+bf,g\rangle=a\langle f,g\rangle+b\langle f,g\rangle;$

  3. (3)

for any $f\in\mathfrak{F}$

$\langle f,f\rangle\succeq 0$

and $\langle f,f\rangle=0$ if and only if $f\equiv 0$ on $V$.

Moreover, the analogue of complex-valued scalar product can be considered for
the functions, taking values in $\mathbb{K}_{C}$. We denote the set of
functions on vertices with values from $\mathbb{K}_{C}$ by

$\mathfrak{F}_{C}=\\{f\mid f:V\rightarrow\mathbb{K}_{C}\\}.$

Then the ‘complex’ scalar product for $f,g\in\mathfrak{F}_{C}$ is defined by

$\langle f,g\rangle_{C}=\sum_{x\in V}f(x)\overline{g(x)}b(x).$

It posses properties (1) – (2) and is anti-symmetric, i.e.

  1. (3enumi)

for any $f,g\in\mathfrak{F}_{C}$

$\langle f,g\rangle_{C}=\overline{\langle g,f\rangle}_{C}.$

Obviously, $\langle f,g\rangle_{C}=\langle f,g\rangle$ for any
$f,g\in\mathfrak{F}$.

These things are usually described in frameworks of symmetric and Hermitian
quadratic forms (see e.g. [12]), but we would like to bring here together
several things and introduce an analogue of a pre-Hilbert space on finite OF-
graphs.

We define

$\|f\|=\sqrt{\langle f,f\rangle}\in\mathbb{K}^{+}$

for any $f\in\mathfrak{F}_{c}$.

##  3\. Laplace and probability operators, their eigenvalues

Our main point of investigation will be a normalized Laplace operator
(Laplacian) and (analogue of) probability operator on $\mathfrak{F}$.
_Laplacian_ is defined by

(2) $\mathcal{L}f(x)=\sum_{y\in V}(f(x)-f(y))\dfrac{b(x,y)}{b(x)}=\sum_{y\in
V}(f(x)-f(y))p(x,y)$

for any $f\in\mathfrak{F}$. We call the operator $\mathcal{P}=I-\mathcal{L}$
on $f\in\mathfrak{F}$ _probability operator_ , since for classical weighted
graphs $\mathcal{P}$ is a stochastic matrix of the corresponding Markov chain
(see e.g. [14], [23] just to mention some among many). The entries of the
corresponding matrix over $\mathbb{K}$ lie between $0$ and $1$, moreover,
elements of each row/column sum up to $1\in\mathbb{K}$.

The Laplacian is a symmetric operator with respect to the introduced scalar
product (i.e. $\langle\mathcal{L}f,g\rangle=\langle f,\mathcal{L}g\rangle$ for
$f,g\in\mathfrak{F}$), due to the _Green formula_ [15, Thm. 22]:

$\sum_{x\in V}\mathcal{L}f(x)g(x)b(x)=\dfrac{1}{2}\sum_{x,y\in
V}(\nabla_{xy}f)(\nabla_{xy}g)b(x,y),$

where $\nabla_{xy}f=f(y)-f(x)$ for any $f,g\in\mathfrak{F}$.

Moreover, it is symmetric for the scalar product
$\langle\cdot,\cdot\rangle_{C}$ and all the functions from $\mathfrak{F}_{C}$,
since the analogue of Green formula for function from $\mathfrak{F}_{c}$ can
be proven in the classical way (see e.g proof in [9] or proof in [15, Thm.
22]). Therefore,

$\displaystyle\sum_{x\in V}\mathcal{L}f(x)\overline{g(x)}b(x)=\sum_{x\in
V}\mathcal{L}f(x)\overline{g(x)}b(x).$

Now we present here several lemmas, which are reformulations of known
algebraic facts for the Laplacian as a linear operator on $\mathfrak{F}$.
Moreover, we present proofs for some of them, since not all linear algebra
techniques can be used over an arbitrary (non-Archimedean) ordered field.

######  Lemma 1.

All eigenvalues of the Laplacian belong to $\mathbb{K}$. Moreover, all its
eigenfunctions belong to $\mathfrak{F}$.

###### Proof.

Let $\lambda\in\mathbb{K}_{C}$ be an eigenvalue of $\mathcal{L}$ with an
eigenfunction $f$, i.e. there exists $f\in\mathfrak{F}_{c}$, $f\not\equiv 0$
such that $\mathcal{L}f(x)=\lambda f(x)$ for any $x\in V$. Then

$\displaystyle\lambda\langle f,f\rangle_{C}=\langle\lambda
f,f\rangle_{C}=\langle\mathcal{L}f,f\rangle_{C}=\langle
f,\mathcal{L}f\rangle_{C}=\langle f,\lambda
f\rangle_{C}=\overline{\lambda}\langle f,f\rangle_{C}$

due to anti-symmetry. Therefore, dividing by $\langle f,f\rangle_{C}$ we
obtain $\overline{\lambda}=\lambda$ from where follows, that
$\lambda\in\mathbb{K}$.

Let $\lambda$ has an eigenfunction $f\in\mathfrak{F}_{C}$. Then, there exists
$f_{1},f_{2}\in\mathfrak{F}$ such that $f=f_{1}+\mathbf{i}f_{2}$, and due to
the linearity of $\mathcal{L}$,

$\mathcal{L}f=\mathcal{L}f_{1}+\mathbf{i}\mathcal{L}f_{2}=\lambda
f_{1}+\mathbf{i}\lambda f_{2}$

from where follows

$\displaystyle\mathcal{L}f_{1}$ $\displaystyle=\lambda f_{1}$
$\displaystyle\mathcal{L}f_{2}$ $\displaystyle=\lambda f_{2}.$

Moreover, since $f\not\equiv 0$, at least one of the functions $f_{1},f_{2}$
is not constantly zero and, therefore, it is an eigenfunction of
$\mathcal{L}$.

∎

######  Lemma 2.

All the eigenvalues of the Laplacian are precisely the roots of characteristic
polynomial of its matrix.

###### Proof.

Follows from more general theorem, see e.g. [12, Theorem 3.2 on p.562] ∎

######  Lemma 3.

There exists an orthonormal basis ($\langle v_{i},v_{j}\rangle=0$ and
$\|v_{i}\|=1$ for any $i,j=\overline{1,n},i\neq j$) of eigenfunctions of the
Laplacian, i.e. the matrix of Laplacian is diagonilazable over $\mathbb{K}$.

###### Proof.

Follows from the proof of Lemma 6.3 in [12, p. 582], and proof of the Spectral
Theorem 6.4 there. ∎

Therefore, the Laplacian has exactly $n=\\#V$ eigenvalues

$\lambda_{0}\preceq\lambda_{1}\preceq\dots\preceq\lambda_{n-1}$

and there are $n$ orthonormal eigenfunctions $v_{0},v_{1}\dots,v_{n-1}$,
forming a basis of $\mathfrak{F}$. These notations for eigenvalues and
eigenfunctions of the Laplacian will be used through the entire paper.

######  Lemma 4.

Set

$\mathcal{R}(f)=\dfrac{\langle\mathcal{L}f,f\rangle}{\langle f,f\rangle}$

for $f\in\mathfrak{F}\setminus\\{0\\}$ (the function $\mathcal{R}$ is called
the _Rayleigh quotient_ of $\mathcal{L}$). The following is true for all
$k=0,\dots,n-1$:

(3) $\lambda_{k}\preceq\mathcal{R}(f)\mbox{ for any }f\in\mathfrak{F}\mbox{
with }\langle f,v_{i}\rangle=0\;\mbox{ for all }\;i=\overline{0,k-1},$ (4)
$\lambda_{k}\succeq\mathcal{R}(f)\mbox{ for any }{f\in\mathfrak{F}\mbox{ with
}\langle f,v_{i}\rangle=0\;\mbox{ for all }\;i=\overline{k+1,n-1}}.$

Moreover,

(5) $\lambda_{k}=\min_{\begin{subarray}{c}f:\langle f,v_{i}\rangle=0\\\
\forall\;i=0,\dots,k-1\end{subarray}}\mathcal{R}(f)=\max_{\begin{subarray}{c}f:\langle
f,v_{i}\rangle=0\\\ \forall\;i=k+1,\dots,n-1\end{subarray}}\mathcal{R}(f),$

where maximum and minimum are attained on the corresponding eigenfunction
$v_{k}$.

###### Proof.

The fact that $\lambda_{k}=\mathcal{R}(v_{k})$ follows from the definitions of
Rayleigh quotient and an eigenvalue.

The inequalities (3) and (4) follow from considering Rayleigh quotient for the
basis decomposition $f=f_{k}v_{k}+\dots+f_{n-1}v_{n-1}$ and
$f=f_{0}v_{0}+\dots+f_{k}v_{k}$ for any function from the given subspaces.

∎

Further we present some facts, which are known for classical weighted graphs
(see e.g. [7], [9]) and have their analogues fo OF-graphs. We also comment on
their proofs for OF-graphs.

######  Theorem 1.

For any finite OF-graph with $\\#V>1$ the following is true:

  1. (1)

$\lambda_{0}=0$ is a simple eigenvalue of $\mathcal{L}$ with constant
eigenfunction.

  2. (2)

An eigenfunction $v_{1}$, corresponding to the first non-zero eigenvalue
satisfies $\langle v_{1},1\rangle=0$

  3. (3)

All the eigenvalues of $\mathcal{L}$ are contained in $[0,2]$.

  4. (4)

If the graph is not bipartite then all the eigenvalues of $\mathcal{L}$ are in
$[0,2)$.

  5. (5)

If the graph is bipartite and $\lambda$ is an eigenvalue of $\mathcal{L}$,
then $2-\lambda$ is an eigenvalue of $\mathcal{L}$ with the same multiplicity.

###### Proof.

Follows exactly the same outline as the proof of Theorem 2.3 and Theorem 2.6
in [9]. ∎

######  Corollary 1 (see e.g. [7], [9]).

$\lambda_{n-1}=2$ is a simple eigenvalue of any bipartite graph with
eigenfunction $c=const$ on $V_{1}$ and $-c$ on $V_{2}$ (where $V=V_{1}\cup
V_{2}$ is the partition).

######  Proposition 1.

For any finite OF-graph with $\\#V=n$ the following is true:

(6) $\sum_{i=1}^{n-1}\lambda_{i}=n.$

Consequently,

(7) $\lambda_{1}\preceq\dfrac{n}{n-1}$

and

(8) $\lambda_{n-1}\succeq\dfrac{n}{n-1}$

###### Proof.

Equality (6) follows from the fact, that the trace of a matrix is independent
of the basis. The latest can be proven over arbitrary ordered field by
considering free coefficient of the trace of the characteristic polynomial of
the matrix. The equations (7) and (8) follows from (6) using $\lambda_{0}=0$.
∎

Now let us consider the operator $\mathcal{P}=I-\mathcal{L}$, where $I$ is an
identity matrix $n\times n$. In the classical case $\mathcal{P}$ corresponds
to the stochastic matrix of Markov chain. Therefore, further we call
$\mathcal{P}$ a _probability operator_ for the sake of brevity. Due to the
Theorem 1 its eigenvalues are

$\boxed{1=\alpha_{0}\succ\alpha_{1}\succeq\alpha_{2}\dots\succeq\alpha_{n-1}\succeq-1}$

where $\alpha_{i}=1-\lambda_{i}$) and belong to $\mathbb{K}$. Moreover, we
have

######  Proposition 2.

For any finite OF-graph with $\\#V>1$ the following is true:

  1. (1)

The eigenfunction of $\mathcal{P}$, corresponding to the eigenvalue $1$, is
constant.

  2. (2)

If the graph is not bipartite then all the eigenvalues of $\mathcal{P}$ are in
$(-1,1]$.

Again, we will use these notations for eigenvalues of $\mathcal{P}$ through
the entire note. Note, that its eigenfunctions are the same as for the
corresponding Laplacian.

##  4\. Estimates on eigenvalues

In the classical case of weighted graphs the absolute values of eigenvalues
$\alpha_{1}$ and $\alpha_{n-1}$ (the latest plays role in the case of non-
bipartite graphs) determine the rate of convergence of random walk, i.e. the
speed of convergence of $\mathcal{P}^{m}f,m\in\mathbb{N}$ (or
$\mathcal{P}^{2m}f$ for bipartite graphs) for $f\in\mathfrak{F}$ to a
function, depending on $f$(see e.g. [9]). In this Section, we present
estimates on these eigenvalues for OF-graphs. The main result here is the
Cheeger’s inequality in its stronger formulation for OF-graphs (Theorem 2).

By _absolute value of $k\in\mathbb{K}$_ we mean the value
$|k|\in\mathbb{K}^{+}\cup\\{0\\}$ defined as follows

$|k|=\begin{cases}k,\mbox{ if }k\succeq 0\\\ -k,\mbox{otherwise.}\end{cases}$

###  4.1. Cheeger’s inequality

######  Lemma 5.

For any non-complete graph $\alpha_{1}\succeq 0$.

###### Proof.

The proof follows the classical outline for the proof of fact, that
$\lambda_{1}\leq 1$, see e.g. [9, p.44]. We present the proof here in a
shorter form.

Let us take two vertices $z_{1},z_{2}$ such that $z_{1}\not\sim z_{2}$ (it is
possible, since the graph is non-complete) and consider function

$f(x)=\begin{cases}c_{1},\mbox{ for }x=z_{1}\\\ c_{2},\mbox{ for }x=z_{2}\\\
0,\mbox{ otherwise},\end{cases}$

where $c_{1},c_{2}\in\mathbb{K}$, such that $\langle f,1\rangle=0$. Let us
denote $V_{12}=V\setminus\\{z_{1},z_{2}\\}$. Then $f(x)=0$ for $x\in V_{12}$.

We have $\langle f,f\rangle=c_{1}^{2}b(z_{1})+c_{2}^{2}b(z_{2})$ and, due to
the Green formula,

$\displaystyle\langle\mathcal{L}f,f\rangle$
$\displaystyle=\dfrac{1}{2}\sum_{x,y\in V}(f(y)-f(x))^{2}b(x,y)$
$\displaystyle=\dfrac{1}{2}\left(\sum_{\begin{subarray}{c}x=z_{1},\\\ y\in
V_{12}\end{subarray}}(f(y)-f(x))^{2}b(x,y)+\sum_{\begin{subarray}{c}x\in
V_{12},\\\ y=z_{1}\end{subarray}}(f(y)-f(x))^{2}b(x,y)\right)$
$\displaystyle+\dfrac{1}{2}\left(\sum_{\begin{subarray}{c}x=z_{2},\\\ y\in
V_{12}\end{subarray}}(f(y)-f(x))^{2}b(x,y)+\sum_{\begin{subarray}{c}x\in
V_{12},\\\ y=z_{2}\end{subarray}}(f(y)-f(x))^{2}b(x,y)\right)$
$\displaystyle+\underbrace{\dfrac{1}{2}\left(\sum_{\begin{subarray}{c}x=z_{1},\\\
y=z_{2}\end{subarray}}(f(y)-f(x))^{2}b(x,y)+\sum_{\begin{subarray}{c}x=z_{2},\\\
y=z_{1}\end{subarray}}(f(y)-f(x))^{2}b(x,y)\right)}_{=0\mbox{ since
}z_{1}\not\sim z_{2}}$ $\displaystyle=\sum_{\begin{subarray}{c}x=z_{1},\\\
y\in
V_{12}\end{subarray}}(f(y)-f(x))^{2}b(x,y)+\sum_{\begin{subarray}{c}x=z_{2},\\\
y\in V_{12}\end{subarray}}(f(y)-f(x))^{2}b(x,y)+0$
$\displaystyle=c_{1}^{2}b(z_{1})+c_{2}^{2}b(z_{2}).$

Therefore, $\mathcal{R}(f)=1$. Then from Lemma 4 follows, that
$\lambda_{1}\preceq 1$ and $\alpha_{1}\succeq~{}0$. ∎

Further in this subsection we discuss Cheeger constant for OF-graphs. Cheeger
isoperimetric constant was firstly introduced by Jeff Cheeger for manifolds in
[6] and then generalized to graphs (see e.g. [1], [7]).

Firstly, we introduce the following notations for $\emptyset\neq S\subset V$:

$b(S)=\sum_{x\in S}b(x)$

and

$b(\partial S)=\sum_{x\in S,y\in V\setminus S}b(x,y),$

i.e. $\partial S$ is a subset of edges of $V$, which have their ends in both
$S$ and $V\setminus S$.

######  Definition 2.

Let $V$ be a finite connected OF-graph with at least two vertices. The
_Cheeger constant_ is defined by

(9) $h=\min_{\emptyset\neq S\subset
V,b(S)\preceq\frac{1}{2}b(V)}\dfrac{b(\partial S)}{b(S)}=\min_{\emptyset\neq
S\subset V}\dfrac{b(\partial S)}{\min\\{b(S),b(V\setminus S)\\}}$

It holds $h\preceq 1$ (consider $S$, consisting of the one vertex with the
smallest weight).

The most known estimates of the first non-zero eigenvalue of Laplacian for
classical weighted graphs in terms of Cheeger constants are

$\lambda_{1}\geq 1-\sqrt{1-h^{2}}$

and

$\lambda_{1}\geq\dfrac{h^{2}}{2},$

where the second follows from the first, but the second is easier to prove
([1], [7]). These estimates obviously lead to the following estimates for the
eigenvalue $\alpha_{1}$ of probability operator for non-complete graphs:
$\alpha_{1}\leq\sqrt{1-h^{2}}$ and $\alpha_{1}\leq 1-\frac{h^{2}}{2}$. In a
non-Archimedean ordered field for the r.h.s. of the latest inequality holds

$1-\frac{h^{2}}{2}\succeq\frac{1}{2}\succ\epsilon$

for any infinitesimal $\epsilon$. The latest means, that one can not use
weaker version of Cheeger’s inequality to investigate convergence of the
analogue of random walk in non-Archimedean case (for the details see Section
5). Therefore, our next step is to prove the stronger Cheeger’s inequality for
OF-graphs. Our proof is similar to the classical proof by Chung [7] for
unweighted graphs and to proof in [1], but the latest proof use integrals,
which we can not use over ordered fields. We also do not use integral
notations as, for example, in [9]. Moreover, we write our proof very
accurately, to be sure that we use exclusively properties of an ordered field.

######  Theorem 2 (Cheeger’s inequality).

$\lambda_{1}\succeq 1-\sqrt{1-h^{2}}$

Firstly, we prove several Lemmas for $\lambda_{1}$.

######  Lemma 6.

(10)
$\lambda_{1}\succeq\dfrac{\frac{1}{2}\sum_{x,y}b(x,y)(g(x)-g(y))^{2}}{\sum_{x}b(x)g(x)^{2}},$

where

$g(x)=\begin{cases}v_{1}(x),\mbox{ for }v_{1}(x)\succ 0\;(\Leftrightarrow x\in
V^{+}),\\\ 0,\mbox{ otherwise }(\Leftrightarrow x\in V^{-}).\end{cases}$

Note that $V^{-}$ is non-empty, since $\langle v_{1},1\rangle=0$.

###### Proof.

From the one hand we have

$\langle\mathcal{L}v_{1},g\rangle=\sum_{x}b(x)\mathcal{L}v_{1}(x)g(x)=\lambda_{1}\sum_{x}b(x)v_{1}(x)g(x)=\lambda_{1}\sum_{x}g^{2}(x)b(x).$

From the other hand, due to the Green’s formula

$\displaystyle\langle\mathcal{L}v_{1},g\rangle$
$\displaystyle=\dfrac{1}{2}\sum_{x,y}b(x,y)(v_{1}(y)-v_{1}(x))(g(y)-g(x))$
$\displaystyle=\dfrac{1}{2}\sum_{x,y\in V^{+}}b(x,y)(g(y)-g(x))^{2}$
$\displaystyle+\underbrace{\dfrac{1}{2}\sum_{x,y\in
V^{-}}b(x,y)(v_{1}(y)-v_{1}(x))\underbrace{(g(y)-g(x))}_{=0\mbox{ on
}V^{-}}}_{=0=\frac{1}{2}\sum_{x,y\in V^{-}}b(x,y)(g(y)-g(x))^{2}}$
$\displaystyle+\underbrace{\dfrac{1}{2}\sum_{\begin{subarray}{c}x\in V^{-},\\\
y\in V^{+}\end{subarray}}b(x,y)\underbrace{(v_{1}(y)-v_{1}(x))}_{\succeq
g(y)-g(x)}\underbrace{(g(y)-g(x))}_{=g(y)\succeq 0}}_{\succeq(g(y)-g(x))^{2}}$
$\displaystyle+\underbrace{\dfrac{1}{2}\sum_{\begin{subarray}{c}x\in V^{-},\\\
y\in V^{+}\end{subarray}}b(x,y)\underbrace{(v_{1}(y)-v_{1}(x))}_{\preceq
g(y)-g(x)}\underbrace{(g(y)-g(x))}_{=g(y)\preceq 0}}_{\succeq(g(y)-g(x))^{2}}$
$\displaystyle\succeq\dfrac{1}{2}\sum_{x,y}b(x,y)(g(y)-g(x))^{2}$

Therefore, (10) follows. ∎

###### Proof of Theorem 2.

Within the proof $V^{+},V^{-}$ and $g$ are as in the proof of Lemma 6.

Without loss of generality, we can assume that $b(V^{+})\preceq b(V^{-})$
(otherwise, consider eigenfunction $-v_{1}$). Moreover, we can enumerate all
$n=\\#V$ vertices of the graph so, that

$\underbrace{v_{1}(x_{1})\preceq\dots\preceq v_{1}(x_{n_{0}})\preceq
0}_{V^{-}}\prec\underbrace{v_{1}(x_{n_{0}+1})\preceq\dots\preceq
v_{1}(x_{n})}_{V^{+}}.$

We introduce some further notations. Let

$S_{i}=\\{x_{j}\;:\;1\leq j\leq i\\},\;i={1,\dots,n}$

and

$\beta=\min_{i={1,\dots,n}}\dfrac{b(\partial
S_{i})}{\min\\{b(S_{i}),b(V\setminus S_{i})\\}}.$

Then

$b(\partial S_{i})=\sum_{\begin{subarray}{c}j:1\leq j\leq i\\\ k:i<k\leq
n\end{subarray}}b(x_{j},x_{k})$ $b(S_{i})=\sum_{j:1\leq j\leq i}b(x_{j})\mbox{
and }b(V\setminus S_{i})=\sum_{j:i<j\leq n}b(x_{j})$

and we note that $h\preceq\beta$.

Denoting the r.h.s of (10) by $W$ and multiplying numerator and denominator by
$\sum_{x,y}b(x,y)(g(x)+g(y))^{2}$ we obtain

$W=\dfrac{\frac{1}{2}\sum_{x,y}b(x,y)(g(x)-g(y))^{2}\sum_{x,y}b(x,y)(g(x)+g(y))^{2}}{\sum_{x}b(x)g(x)^{2}\sum_{x,y}b(x,y)(g(x)+g(y))^{2}}$

and by Cauchy-Schwarz inequality 333The Cauchy-Schwarz inequality in an
ordered field can be proven by induction or through Pythagorean theorem

(11)
$W\succeq\dfrac{\frac{1}{2}\left(\sum_{x,y}b(x,y)\left|g^{2}(x)-g^{2}(y)\right|\right)^{2}}{\sum_{x}b(x)g(x)^{2}\sum_{x,y}b(x,y)(g(x)+g(y))^{2}}$

Apart from this from (10) we have

$\displaystyle W\sum_{x}b(x)g(x)^{2}$
$\displaystyle=\dfrac{1}{2}\sum_{x,y}b(x,y)(g(x)-g(y))^{2}=[\mbox{ Green
formula}]$
$\displaystyle=\sum_{x}\mathcal{L}g(x)g(x)b(x)=\sum_{x}b(x)g^{2}(x)-\sum_{x,y}b(x,y)g(y)g(x)$
$\displaystyle=[\pm\mbox{the first sum}]$
$\displaystyle=2\sum_{x}b(x)g^{2}(x)-\sum_{x}b(x)g^{2}(x)-\sum_{x,y}b(x,y)g(y)g(x)$
$\displaystyle=2\sum_{x}b(x)g^{2}(x)-\sum_{x,y}b(x,y)g^{2}(x)-\sum_{x,y}b(x,y)g(y)g(x)$
$\displaystyle=2\sum_{x}b(x)g^{2}(x)-\left(\sum_{x,y}b(x,y)g(x)(g(x)+g(y))\right)$
$\displaystyle=2\sum_{x}b(x)g^{2}(x)-\left(\sum_{x,y}b(x,y)g(y)(g(x)+g(y))\right)$
$\displaystyle=2\sum_{x}b(x)g^{2}(x)-\dfrac{1}{2}\left(\sum_{x,y}b(x,y)(g(x)+g(y))^{2}\right),$

where in the last two lines we exchanged notations $x$ and $y$, sum the two
lines up and divided by $2$ (usually this trick is used in a proofs of Green’s
formula).

Therefore, from (11) follows

$\displaystyle W$
$\displaystyle\succeq\dfrac{\frac{1}{2}\left(\sum_{x,y}b(x,y)|g^{2}(x)-g^{2}(y)|\right)^{2}}{\sum_{x}b(x)g(x)^{2}(4\sum_{x}b(x)g^{2}(x)-2W\sum_{x}b(x)g(x)^{2})}$
$\displaystyle\succeq\dfrac{\frac{1}{2}\left(\sum_{x,y}b(x,y)|g^{2}(x)-g^{2}(y)|\right)^{2}}{\left(\sum_{x}b(x)g(x)^{2}\right)^{2}(4-2W)}$

Now let us estimate the numerator
$A:=\frac{1}{2}\left(\sum_{x,y}b(x,y)|g^{2}(x)-g^{2}(y)|\right)^{2}$.

$\displaystyle A$
$\displaystyle=\dfrac{1}{2}\left(2\sum_{i<j}b(x_{i},x_{j})(g^{2}(x_{j})-g^{2}(x_{i}))\right)^{2}=2\left(\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}b(x_{i},x_{j})(g^{2}(x_{j})-g^{2}(x_{i}))\right)^{2}$
$\displaystyle=2\left(\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}b(x_{i},x_{j})(g^{2}(x_{j})-g^{2}(x_{j-1})+g^{2}(x_{j-1})\dots-g^{2}(x_{i+1})+g^{2}(x_{i+1})-g^{2}(x_{i}))\right)^{2}$
$\displaystyle=2\left(\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}b(x_{i},x_{j})\sum_{k=i}^{j-1}(g^{2}(x_{k+1})-g^{2}(x_{k}))\right)^{2}$
$\displaystyle=2\left(\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\sum_{k=i}^{j-1}b(x_{i},x_{j})(g^{2}(x_{k+1})-g^{2}(x_{k}))\right)^{2}$
$\displaystyle=[\mbox{change limits of summation for $k$ and $j$}]$
$\displaystyle=2\left(\sum_{i=1}^{n-1}\sum_{k=i}^{n-1}\sum_{j=k+1}^{n}b(x_{i},x_{j})(g^{2}(x_{k+1})-g^{2}(x_{k}))\right)^{2}$
$\displaystyle=2\left(\sum_{i=1}^{n-1}\sum_{k=i}^{n-1}(b(x_{i},x_{k+1})+\dots+b(x_{i},x_{n}))(g^{2}(x_{k+1})-g^{2}(x_{k}))\right)^{2}$
$\displaystyle=[\mbox{change limits of summation for $k$ and $i$}]$
$\displaystyle=2\left(\sum_{k=1}^{n-1}\sum_{i=1}^{k}(b(x_{i},x_{k+1})+\dots+b(x_{i},x_{n}))(g^{2}(x_{k+1})-g^{2}(x_{k}))\right)^{2}$
$\displaystyle=2\left(\sum_{k=1}^{n-1}\underbrace{\sum_{i=1}^{k}\sum_{j=k+1}^{n}b(x_{i},x_{j})}_{=b(\partial
S_{k})}(g^{2}(x_{k+1})-g^{2}(x_{k}))\right)^{2}$
$\displaystyle=2\left(\sum_{k=1}^{n-1}b(\partial
S_{k})(g^{2}(x_{k+1})-g^{2}(x_{k}))\right)^{2}=2\left(\sum_{k=n_{0}}^{n-1}b(\partial
S_{k})(g^{2}(x_{k+1})-g^{2}(x_{k}))\right)^{2}.$

Note that for $k\geq n_{0}$ we have $b(V\setminus S_{k})\preceq b(S_{k})$ due
to $V^{-}\subset S_{k}$. Therefore

$\dfrac{b(\partial S_{k})}{b(V\setminus S_{k})}\succeq\beta$

for such $k$ and we obtain

$\displaystyle A$ $\displaystyle\succeq 2\left(\sum_{k=n_{0}}^{n-1}\beta
b(V\setminus S_{k})(g^{2}(x_{k+1})-g^{2}(x_{k}))\right)^{2}$
$\displaystyle=2\left(\beta\sum_{k=n_{0}}^{n-1}\sum_{j=k+1}^{n}b(x_{j})(g^{2}(x_{k+1})-g^{2}(x_{k}))\right)^{2}$
$\displaystyle=2\left(\beta\sum_{j=n_{0}+1}^{n}\sum_{k=n_{0}}^{j-1}b(x_{j})(g^{2}(x_{k+1})-g^{2}(x_{k}))\right)^{2}$
$\displaystyle=2\left(\beta\sum_{j=n_{0}+1}^{n}b(x_{j})(g^{2}(x_{j})-g^{2}(x_{n_{0}}))\right)^{2}=2\left(\beta\sum_{j=n_{0}+1}^{n}b(x_{j})g^{2}(x_{j})\right)^{2},$
$\displaystyle=2\left(\beta\sum_{j=1}^{n}b(x_{j})g^{2}(x_{j})\right)^{2},$

where the last two equalities are true, since $g(x_{i})=0$ for $i\leq n_{0}$
and $V^{-}\neq\emptyset$.

Therefore,

$\displaystyle W$
$\displaystyle\succeq\dfrac{A}{\left(\sum_{x}b(x)g(x)^{2}\right)^{2}(4-2W)}\succeq\dfrac{2\beta^{2}}{4-2W}$

From where follows ($W\preceq 2$ as Rayleigh quotient of $g$), that

$W^{2}-2W+\beta^{2}\preceq 0$

and $W\succeq 1-\sqrt{1-\beta^{2}}$ since discriminant is positive due to
$\beta\preceq 1=\dfrac{b(\partial S_{1})}{b(S_{1})}$.

∎

Using Lemma 5 we immediately get the estimate of $\alpha_{1}$ in terms of
Cheeger constant:

######  Corollary 2.

For any non-complete graph the following holds:

$\alpha_{1}=|\alpha_{1}|\preceq\sqrt{1-h^{2}}.$

###  4.2. An estimation of $\alpha_{n-1}$

######  Lemma 7.

For any graph with at least two vertices the following holds:
$\alpha_{n-1}\prec 0$ and
$|\alpha_{n-1}|\succeq\frac{1}{n-1}=c_{n}\in\mathbb{Q}^{+}\subset\mathbb{K}$.

###### Proof.

It follows from (8) since $\alpha_{n-1}=1-\lambda_{n-1}$. ∎

##  5\. Properties of $\mathcal{P}^{m}f$ and its subsequences

###  5.1. Estimations of $\mathcal{P}^{m}f$

Through this Section let $\mathcal{P}$ be a probability operator as above and
$f\in\mathfrak{F}$. We investigate a behaviour of the sequence
$\\{\mathcal{P}^{m}f\\}_{m\in\mathbb{N}}$ as $m\to\infty$. Firstly we present
estimates on $\\{\mathcal{P}^{m}f\\},m\in\mathbb{N}$ in terms of $f$. The
results are similar to the case of classical weighted graphs.

######  Theorem 3.

For any non-complete graph with $\\#V=n>2$ and for any
$f\in\operatorname{span}(\\{v_{i}\mid\alpha_{i}\succ 0,i=\overline{0,n-1}\\})$
the following holds

$\|\mathcal{P}^{m}f-\widetilde{f}\|\preceq\alpha_{1}^{m}\|f\|,$

where

$\widetilde{f}(x)=\dfrac{1}{b(V)}\sum_{y\in V}f(y)b(y),\;x\in V.$

###### Proof.

Let $f=\sum\limits_{i=0}^{k}f_{i}v_{i}$, where $\displaystyle
k=\max_{\begin{subarray}{c}i=\overline{0,n-1};\\\ \alpha_{i}\succ
0\end{subarray}}i$. Then

$\mathcal{P}^{m}f-\widetilde{f}=\sum\limits_{i=0}^{k}f_{i}\alpha_{i}^{m}v_{i}-\widetilde{f}=f_{0}v_{0}+\sum\limits_{i=1}^{k}f_{i}\alpha_{i}^{m}v_{i}-\widetilde{f},$

since $\alpha_{0}=1$. Further, using that $v_{0}$ is a constant normalized
eigenfunction, i.e. $v_{0}\equiv\frac{1}{\sqrt{b(V)}}$, we get

$\displaystyle f_{0}$ $\displaystyle=\langle f,v_{0}\rangle=\langle
f,\dfrac{1}{\sqrt{b(V)}}\rangle=\dfrac{1}{\sqrt{b(V)}}\sum_{y\in V}f(y)b(y).$

Therefore,

$\displaystyle f_{0}v_{0}$ $\displaystyle=\dfrac{1}{{b(V)}}\sum_{y\in
V}f(y)b(y)=\widetilde{f}$

and

$\displaystyle\mathcal{P}^{m}f-\widetilde{f}$
$\displaystyle=\sum\limits_{i=1}^{k}f_{i}\alpha_{i}^{k}v_{i}.$

Then

$\displaystyle\|\mathcal{P}^{m}f-\widetilde{f}\|^{2}$
$\displaystyle=\langle\mathcal{P}^{m}f-\widetilde{f},\mathcal{P}^{2m}f-\widetilde{f}\rangle=\sum\limits_{i=1}^{k}f_{i}^{2}\alpha_{i}^{2m}$
$\displaystyle\preceq\max_{1\leq i\leq
k}\alpha_{i}^{2m}\sum\limits_{i=1}^{k}f_{i}^{2}\preceq\max_{1\leq i\leq
k}\alpha_{i}^{2m}\sum\limits_{i=0}^{k}f_{i}^{2}=\max_{1\leq i\leq
k}\alpha_{i}^{2m}\|f\|^{2}.$

and we obtain

$\displaystyle\|{\mathcal{P}^{m}}f-\widetilde{f}\|$
$\displaystyle\preceq\alpha_{1}^{m}\|f\|,$

since eigenvalues are ordered by their values. The condition of non-
completeness is needed to ensure $\alpha_{1}\succ 0$. ∎

Applying now Corollary 2 we obtain:

######  Corollary 3.

Under the conditions of Theorem 3 the following holds

$\|\mathcal{P}^{m}f-\widetilde{f}\|\preceq\left(\sqrt{1-h^{2}}\right)^{m}\|f\|.$

######  Theorem 4.

For bipartite graphs with the partition $V=V_{1}\cup V_{2}$ the following
holds for any $f\in\mathcal{F}$:

$\|\mathcal{P}^{2m}f-\overline{f}\|\preceq\alpha_{1}^{2m}\|f\|,$

where

$\overline{f}(x)=\dfrac{2}{b(V)}\begin{cases}\sum_{y\in V_{1}}f(y)b(y),\;x\in
V_{1},\\\ \sum_{y\in V_{2}}f(y)b(y),\;x\in V_{2}.\end{cases}$

The proof follows from explanations to Theorem 2.7 in [9] and follows the same
outline as the proof of Theorem 3.

###### Proof.

Let $f=\sum_{i=0}^{n-1}f_{i}v_{i}$. Then

$\displaystyle\mathcal{P}^{2m}f-\overline{f}$
$\displaystyle=\sum\limits_{i=0}^{n-1}f_{i}\alpha_{i}^{2m}v_{i}-\overline{f}$
$\displaystyle=f_{0}v_{0}+f_{n-1}v_{n-1}+\sum\limits_{i=1}^{n-2}f_{i}\alpha_{i}^{2m}v_{i}-\overline{f},$

since $\alpha_{0}=1$ and for bipartite graphs $\alpha_{n-1}=-1$. Let us notice
that

$\displaystyle f_{0}$ $\displaystyle=\langle f,v_{0}\rangle=\langle
f,\dfrac{1}{\sqrt{b(V)}}\rangle=\dfrac{1}{\sqrt{b(V)}}\sum_{y\in V}f(y)b(y)$
$\displaystyle=\dfrac{1}{\sqrt{b(V)}}\sum_{y\in
V_{1}}f(y)b(y)+\dfrac{1}{\sqrt{b(V)}}\sum_{y\in V_{2}}f(y)b(y)$

and

$\displaystyle f_{n-1}$ $\displaystyle=\langle
f,v_{n-1}\rangle=\dfrac{1}{\sqrt{b(V)}}\sum_{y\in
V_{1}}f(y)b(y)-\dfrac{1}{\sqrt{b(V)}}\sum_{y\in V_{2}}f(y)b(y)$

Therefore,

$\displaystyle f_{0}v_{0}$ $\displaystyle=\dfrac{1}{{b(V)}}\sum_{y\in
V_{1}}f(y)b(y)+\dfrac{1}{{b(V)}}\sum_{y\in V_{2}}f(y)b(y)$

and

$f_{n-1}v_{n-1}=\begin{cases*}\dfrac{1}{{b(V)}}\sum_{y\in
V_{1}}f(y)b(y)-\dfrac{1}{{b(V)}}\sum_{y\in V_{2}}f(y)b(y),\;x\in V_{1}\\\
-\dfrac{1}{{b(V)}}\sum_{y\in V_{1}}f(y)b(y)+\dfrac{1}{{b(V)}}\sum_{y\in
V_{2}}f(y)b(y),\;x\in V_{2}\end{cases*}$

from where follows $f_{0}v_{0}+f_{n-1}v_{n-1}-\overline{f}=0$ and

$\displaystyle\mathcal{P}^{2m}f-\overline{f}$
$\displaystyle=\sum\limits_{i=1}^{n-2}f_{i}\alpha_{i}^{2m}v_{i}.$

Then

$\displaystyle\|\mathcal{P}^{2m}f-\overline{f}\|^{2}$
$\displaystyle=\langle\mathcal{P}^{2m}f-\overline{f},\mathcal{P}^{2m}f-\overline{f}\rangle=\sum\limits_{i=1}^{n-2}f_{i}^{2}\alpha_{i}^{4m}$
$\displaystyle\preceq\max_{1\leq i\leq
n-2}\alpha_{i}^{4m}\sum\limits_{i=1}^{n-2}f_{i}^{2}\preceq\max_{1\leq i\leq
n-2}\alpha_{i}^{4m}\sum\limits_{i=0}^{n-1}f_{i}^{2}=\max_{1\leq i\leq
n-2}\alpha_{i}^{4m}\|f\|^{2}.$

and we obtain

$\displaystyle\|\mathcal{P}^{2m}f-\overline{f}\|^{2}$
$\displaystyle\preceq\alpha_{1}^{2m}\|f\|^{2},$

since $\alpha_{1}=-\alpha_{n-2}$ and the values of other eigenvalues are
between them. ∎

######  Corollary 4.

Let $\\#V>2$. Under the conditions of Theorem 4 the following holds

$\|\mathcal{P}^{2m}f-\overline{f}\|\preceq\left({1-h^{2}}\right)^{m}\|f\|$

###### Proof.

$\\#V>2$ provides non-completness of bipartite graph and we can use Corollary
2. ∎

###  5.2. Propierty of non-convergence for non-bipartite graphs

The convergence of sequence $\\{k_{n}\\}_{n\in\mathbb{N}}$ to $k$ in ordered
field means by definition, that for any element $a\in\mathbb{K}$ there exists
$N_{0}\in\mathbb{N}$ such that for any $n\geq N_{0}$ we have

$|k_{n}-k|\preceq a.$

To state any result on convergence for an arbitrary ordered field is
impossible, since in surreal numbers (which is the largest possible ordered
field, containing all the others, see e.g. [8], [2, Theorem 24.29]) only
constant sequences converge, if one consider the above mentioned classical
notion of convergence ([18, Theorem 16]). Therefore, we will present the
theorem on convergence for the important case of the Levi-Civita field in the
next section.

However, for non-bipartite graphs we have the following surprisingly
interesting property of $\mathcal{P}^{m}$ over arbitrary non-Archimedean
ordered field $\mathbb{K}$.

######  Theorem 5.

Let $V$ be a non-bipartite graph over a non-Archimedean field $\mathbb{K}$.
Then there is no limit $\mathcal{\alpha}_{n-1}^{m}v_{n-1}(x)$ for $m\to\infty$
for any vertex $x\in V$ with $v_{n-1}(x)\neq 0$ over any non-Archimedean
ordered field. There are no partial limits.

In other words, there always exists a function $f$ and a vertex $x\in V$ such
that $\mathcal{P}^{2m}f(x)$ has no (partial) limit in $\mathbb{K}$.

###### Proof.

For any two elements of the sequence $\alpha_{n-1}^{m}v_{n-1}(x)$ and
$\alpha_{n-1}^{m+l}v_{n-1}(x)$, where $l\in\mathbb{N}$ we have

$|\alpha_{n-1}^{m}v_{n-1}(x)-\alpha_{n-1}^{m+l}v_{n-1}(x)|=|\alpha_{n-1}^{m}||1-\alpha_{n-1}^{l}||v_{n-1}(x)|\\\
\succ{\epsilon}|1+\alpha_{n-1}|{|v_{n-1}(x)|},$

where $\epsilon\in\mathbb{K}$ is any infinitesimal, since
$|\alpha_{n-1}^{m}|\succeq 1/(n-1)^{m}\succ\epsilon$ due to Lemma 7 and for
$|1-\alpha_{n-1}^{l}|$ we have two possibilities:

  * •

if $l$ is odd, then $|1-\alpha_{n-1}^{l}|\succ 1\succ|1+\alpha_{n-1}|$, since
$-1\prec\alpha_{n-1}\prec 0$ for non-bipartite graphs.

  * •

If $l$ is even, then
$\alpha_{n-1}^{l}=|\alpha_{n-1}|^{l}\prec|\alpha_{n-1}|\prec 1$, since graph
is non-bipartite, and
$|1-\alpha_{n-1}^{l}|\succ|1-|\alpha_{n-1}||=|1+\alpha_{n-1}|$.

Since $-1\prec\alpha_{n-1}$ for non-bipartite graph we have
$|1+\alpha_{n-1}|\neq 0$ and non-convergence follows from the fact that any
subsequence is not a Cauchy sequence.

∎

##  6\. Mixing over Levi-Civita field

###  6.1. Preliminaries on the Levi-Civita field

The Levi-Civita field was introduced by Tullio Levi-Civita in 1862 [13]. The
Levi-Civita field is the smallest non-Archimedean real-closed ordered field,
which is Cauchy complete in the order topology. Moreover, it has a subfield,
isomorphic to the field of rational functions, whose elements naturally appear
as edge weights in the theory of electrical networks (see e.g. [15, 16]).

Firstly, we recall the definition and main notations for the Levi-Civita field
$\mathcal{R}$ (see e.g. [4], [10], [19], [20], [21]).

######  Definition 3.

A subset $Q$ of the rational numbers $\mathbb{Q}$ is called _left-finite_ if
for every number $r\in\mathbb{Q}$ there are only finitely many elements of $Q$
that are smaller than $r$.

######  Definition 4.

[13] We define the Levi-Civita field $\mathcal{R}$ as a field of formal power
series on $\epsilon$, where any element $a\in\mathcal{R}$ can be written as

(12) $a=\sum_{i=0}^{\infty}a_{i}\epsilon^{q_{i}},$

with $a_{i}\in\mathbb{R}$ and $Q=\\{q_{i}\\}_{i=0}^{\infty}\subset\mathbb{Q}$
being left-finite.

Addition and multiplication are defined naturally as for formal power series.
The order is defined as follows: $a\succ 0$ if $a_{0}>0$.

For

(13) $a=\sum_{i=0}^{\infty}a_{i}\epsilon^{q_{i}}\mbox{ and
}d=\sum_{i=0}^{\infty}d_{i}\epsilon^{p_{i}}\ $

we write $a\approx d$ (“$a$ is comparable to $d$”) if $q_{0}=p_{0}$ and
$a_{0}=d_{0}$. For the element $a=0$ we put $q_{0}=\infty$. Therefore, two
non-zero elements are comparable, if the first terms of their series coincide.
Zero is comparable only to itself.

For the convenience, we state the following lemma, which follows immediately
from the notion of comparabless.

######  Lemma 8.

The following two statements hold:

  1. (1)

Let $a\approx d$ for $a,d\in\mathcal{R}\setminus\\{0\\}$, then
$|a|\succ\epsilon|d|$. Moreover, from $a\approx d$ follows $|a|\approx|d|$ and
$a^{m}\approx d^{m}$ for any $m\in\mathbb{N}$.

  2. (2)

Let $a\approx r$ for $a\in\mathcal{R},r\in\mathbb{R}\setminus\\{0\\}$. Then
$|a|\succ\epsilon$ and there exists $q>0$ such that $|a-r|\prec\epsilon^{q}$.

  3. (3)

If $a_{1}\approx d_{1}$ and $a_{2}\approx d_{2}$, where
$a_{1},a_{2},d_{1},d_{2}\in\mathcal{R}$, then $a_{1}a_{2}\approx d_{1}d_{2}$.

###  6.2. Properties of $\mathcal{P}^{m}f$ in the Levi-Civita field

Let us consider finite graphs over the Levi-Civita field. Two following
Propositions describe completely the behaviour of eigenfunctions of
$\mathcal{P}$ under the action of $\mathcal{P}^{m},m\in\mathbb{N}$ depending
on eigenvalues.

######  Proposition 3.

If $\alpha_{i}$ is an eigenvalue of probability operator such that
$\alpha_{i}\approx r$ for some $r\in\mathbb{R}\setminus\\{0\\}$ and
$\alpha_{i}\neq 1$ then there is no limit $\mathcal{\alpha}_{i}^{m}v_{i}(x)$
for $m\to~{}\infty,m\in\mathbb{N}$ whenever $v_{i}(x)\neq 0$. Moreover, if in
addition $\alpha_{i}\neq-1$, then there are no partial limits.

###### Proof.

Firstly the case $\alpha_{i}=~{}-1$ is obvious, since the partial limits for
$\alpha_{i}=-1$ exist for the subsequences $\mathcal{\alpha}_{i}^{2m}v_{i}(x)$
and $\mathcal{\alpha}_{i}^{2m+1}v_{i}(x)$ and limit does not exists whenever
$v_{i}(x)\neq 0$. Therefore, let further in the proof $a_{i}\neq\pm 1$.

Let us point out that $|r|\leq 1$ follows from $|\alpha_{i}|\preceq 1$ .

For any two elements of sequence $\alpha_{i}^{m}v_{i}(x)$ and
$\alpha_{i}^{m+l}v_{i}(x)$, where $l\in\mathbb{N}$ we have

$|\alpha_{i}^{m}v_{i}(x)-\alpha_{i}^{m+l}v_{i}(x)|=|\alpha_{i}^{m}||1-\alpha_{i}^{l}||v_{i}(x)|.$

For the first multiplayer $|\alpha_{i}^{m}|\approx|r^{m}|$ holds and
$|\alpha_{i}^{m}|\succ\epsilon$ due to Lemma 8. Further we have several cases:

  1. (1)

for $r^{l}\neq 1$, we have
$|1-\alpha_{i}^{l}|\approx|1-r^{l}|\in\mathbb{R}\setminus\\{0\\}$ and we
obtain

(14)
$|\alpha_{i}^{m}v_{i}(x)-\alpha_{i}^{m+l}v_{i}(x)|\succ{\epsilon}^{2}|v_{i}(x)|.$

due to Lemma 8 (2).

  2. (2)

for $r^{l}=1$ (i. e. $r=1$ or $r=-1$ with $l$ being even) we have

$|1-~{}\alpha_{i}^{l}|\approx~{}|\alpha_{i,1}lr^{l-1}\epsilon^{q_{1}}|\mbox{
for }\alpha_{i}=r+\sum_{j=1}^{\infty}\alpha_{i,j}\epsilon^{q_{j}},$

and $|1-~{}\alpha_{i}^{l}|\succ\epsilon^{q_{1}+1}|\alpha_{i,1}lr^{l-1}|$ due
to Lemma 8 (1), since $\alpha_{i,1}\neq 0$ whenever $\alpha\neq\pm 1$.
Therefore,

$|\alpha_{i}^{m}v_{i}(x)-\alpha_{i}^{m+l}v_{i}(x)|\succ{\epsilon}^{2+q_{1}}|\alpha_{i,1}lr^{l-1}||v_{i}(x)|$

and again since $\alpha_{i,1}\neq 0$ we obtain

(15)
$|\alpha_{i}^{m}v_{i}(x)-\alpha_{i}^{m+l}v_{i}(x)|\succ{\epsilon}^{3+q_{1}}|v_{i}(x)|.$

From (14) and (15) we obtain that for any $m,l\in\mathbb{N}$ holds

$|\alpha_{i}^{m}v_{i}(x)-\alpha_{i}^{m+l}v_{i}(x)|\succ{\epsilon}^{3+q_{1}}|v_{i}(x)|,$

i.e. the sequence $\alpha_{i}^{m}v_{i}(x)$ has no Cauchy subsequences. ∎

######  Proposition 4.

If $\alpha_{i}$ is an eigenvalue of probability operator such that
$\alpha_{i}\approx r\epsilon^{q}$, for some
$r\in\mathbb{R},q>0,q\in\mathbb{Q}\cup\\{\infty\\}$ then there is a limit
$\mathcal{\alpha}_{i}^{m}v_{i}(x)$ for $m\to\infty,m\in\mathbb{N}$ for any
vertex $x\in V$.

###### Proof.

Note that we also include here the case $\alpha_{i}=0$
($\Leftrightarrow\alpha_{i}\approx 0$), since in this case
$\alpha_{i}^{m}v_{i}(x)=0\to 0$ for $m\in\mathbb{N}$.

Therefore, further in the proof we assume that $r\neq 0$. We have

$|\alpha_{i}^{m}v_{i}(x)|\approx|r^{m}\epsilon^{qm}v_{i}(x)|.$

Let $\displaystyle v_{i}(x)=\sum_{j=0}^{\infty}v_{i,j}\epsilon^{t_{j}}$. Then

$|\alpha_{i}^{m}v_{i}(x)|=|r^{m}||v_{i,0}(x)|\epsilon^{qm+t_{0}}+o(\epsilon^{qm+t_{0}}),$

where $o(\epsilon^{p})$ stays for terms with powers of $\epsilon$, higher then
$p$. Therefore, for any $a\succ
0,a=\sum_{i=0}^{\infty}a_{i}\epsilon^{q_{i}}\in\mathcal{R}$ we obtain
${|\alpha_{i}^{m}v_{i}(x)|\prec a}$ taking $m$ large enough (such that
$qm+t_{0}>q_{0}$). ∎

Now we present convergence results in terms of Cheeger constant $h$ defined by
(9).

######  Theorem 6.

Let $V$ be a bipartite graph with $\\#V>2$ over the Levi-Civita field. Let
$h\approx 1$. Then for any $f\in\mathfrak{F}$ we have
$\mathcal{P}^{2m}f\to\overline{f}$, where

$\overline{f}=\dfrac{2}{b(V)}\begin{cases}\sum_{y\in V_{1}}f(y)b(y),\;x\in
V_{1},\\\ \sum_{y\in V_{2}}f(y)b(y),\;x\in V_{2}.\end{cases}$

###### Proof.

Since $\\#V>2$, the bipartite graph is non-complete and $\alpha_{1}\succeq 0$.
Since $h\preceq 1$, from $h^{2}\approx 1$ we get
$1-h^{2}=|1-h^{2}|\prec\epsilon^{q}$ for some $q>0$ due to Lemma 8 (2) and the
convergence follows from Corollary 4, since

$\|\mathcal{P}^{2m}-\overline{f}\|\prec\epsilon^{qm}\|f\|\prec\epsilon^{qm+t_{0}}\varphi_{0}\mbox{
for }\|f\|=\sum_{i=0}^{\infty}\varphi_{i}\epsilon^{t_{i}}.$

Therefore, for any $a\succ
0,a=\sum_{i=0}^{\infty}a_{i}\epsilon^{q_{i}}\in\mathcal{R}$ we obtain
${\|\mathcal{P}^{2m}-\overline{f}\|\prec a}$ taking $m$ large enough (such
that $qm+t_{0}>q_{0}$). ∎

######  Theorem 7.

Let $V$ be a non-complete non-bipartite graph with $\\#V=n>1$ over the Levi-
Civita field. Let $h\approx 1$. Then for any
$f\in\operatorname{span}(\\{v_{i}\mid\alpha_{i}\succ 0,i=\overline{0,n-1}\\})$
we have $\mathcal{P}^{m}f\to\widetilde{f}$, where

$\widetilde{f}(x)=\dfrac{1}{b(V)}\sum_{y\in V}f(y)b(y),\;x\in V.$

###### Proof.

Follows from Theorem 3 by Corollary 2, similarly to the proof of Theorem 6. ∎

###  6.3. Examples

######  Example 1.

Let us consider a graph over the Levi-Civita field with $4$ vertices,
presented at Figure 1 with $R,D>0$ (notations $R$ and $D$ come from electrical
networks and make sense there, see e.g. [15], [16]).

$1$$2$$3$$4$$R^{-1}$$R^{-1}$$D^{-1}\epsilon$ Figure 1.

The matrix of the operator $\mathcal{P}$ is the following:

$\left(\begin{array}[]{cccc}0&1&0&0\\\ \frac{1}{2}&0&\frac{1}{2}&0\\\
0&\frac{D}{D+R\epsilon}&0&\frac{R\epsilon}{D+R\epsilon}\\\ 0&0&1&0\\\
\end{array}\right)$

The corresponding eigenvalues are $\alpha_{0,3}=\pm 1$ and
$\alpha_{1,2}=\pm\sqrt{\frac{R\epsilon}{2D+2R\epsilon}}$ (note, that the graph
is bipartite). The latest eigenvalues can be written as generalized binomial
series (which gives as a homomorphism from rational functions on $\epsilon$ to
$\mathcal{R}$) as

$\displaystyle\alpha_{1,2}$
$\displaystyle=\pm\sum_{i=0}^{\infty}{{-\frac{1}{2}}\choose{}_{i}}\frac{1}{\sqrt{2}}\left(\frac{R}{D}\right)^{i+\frac{1}{2}}\epsilon^{i+\frac{1}{2}}$
$\displaystyle=\pm\frac{1}{\sqrt{2}}\left(\frac{R}{D}\right)^{\frac{1}{2}}\epsilon^{\frac{1}{2}}\mp\frac{1}{2\sqrt{2}}\left(\frac{R}{D}\right)^{\frac{3}{2}}\epsilon^{\frac{3}{2}}+o(\epsilon^{\frac{3}{2}}),$

where ${{-\frac{1}{2}}\choose{}_{k}}$ is a generalized binomial coefficient.

Therefore,
$|\alpha_{1,2}|\prec\left(\frac{R\epsilon}{2D}\right)^{\frac{1}{2}}$ and

$\|\mathcal{P}^{2m}f-\overline{f}\|\prec\left(\frac{R\epsilon}{2D}\right)^{m}\|f\|,$

from where follows, that $\mathcal{P}^{2m}f\to\overline{f}$ as $m$ goes to
$\infty$.

We can also easily calculate Cheeger constant for a given graph (considering
all possible partitions) and get

$h=\frac{D}{D+2R\epsilon}$

that holds on the partition $\\{1,2\\}\cup\\{3,4\\}$.

Further,

$h=\sum_{i=0}^{\infty}(-1)^{i}\left(\frac{2R}{D}\right)^{i}\epsilon^{i}\approx
1$

and we can use Theorem 6 to state the convergence of $\mathcal{P}^{2m}f$.

######  Example 2.

Let us investigate the eigenvalues of the graph over the Levi-Civita field,
presented at Figure 2 with $R,D>0$.

$1$$2$$3$$4$$R^{-1}$$D^{-1}\epsilon$$R^{-1}$ Figure 2.

The corresponding eigenvalues are $\alpha_{0,3}=\pm 1$ and
$\alpha_{1,2}=\pm{\frac{D}{D+R\epsilon}}$. The latest eigenvalues can be
written in form generalized binomial series as

$\alpha_{1,2}=\pm\sum_{i=0}^{\infty}{{-1}\choose{}_{i}}\left(\dfrac{R}{D}\right)^{i}\epsilon^{i}=\pm
1\mp\frac{R\epsilon}{D}+o(\epsilon).$

Therefore, $|\alpha_{1,2}|\approx 1$.

The Cheeger constant for a given graph is

$h=\frac{R\epsilon}{2D+R\epsilon}=\frac{R\epsilon}{2D}-\left(\frac{R\epsilon}{2D}\right)^{2}+o(\epsilon^{2}).$

This example has shown us, that a small (smaller than any natural number)
Cheeger constant is possible over $\mathcal{R}$, as well as eigenvalues of
$\mathcal{P}$ comparable to $1$, and the convergence of $\mathcal{P}^{m}f$
fails for general $f$.

## References

  * [1] Frank Bauer, Jürgen Jost. Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator. _Communications in analysis and geometry_. V. 21, n. 4, 787–845 (2013).
  * [2] Béla Bajnok. _An Invitation to Abstract Mathematics_ , Springer, 2013.
  * [3] V. Benci, L. Horsten, S. Wenmackers. Non-Archimedean Probability. _Milan J. Math_. 81, 121–151 (2013).
  * [4] Martin Berz, Christian Bischof, George Corliss, Andreas Griewank, Andreas. Computational Differentiation: Techniques, Applications, and Tools. Chapter 2: Calculus and Numerics on Levi-Civita Fields. eds., SIAM, 1996.
  * [5] H. G. Dales and W. Hugh Woodin. Super-Real Fields. Oxford Univ. Press, 1996.
  * [6] Jeff Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. In Gunning, Robert C. (ed.). _Problems in analysis_(Papers dedicated to Salomon Bochner, 1969). Princeton, N. J.: Princeton Univ. Press. pp. 195–199 (1970)
  * [7] F. R. K. Chung. Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, No. 92, AMS, Providence, Rhone Island, 1997.
  * [8] John Horton Conway. _On numbers and games_. Academic Press, L.M.S. monographs 6, 1976.
  * [9] A. Grigor’yan.  Introduction to Analysis on Graphs, volume 71 of AMS University Lecture Series.  Providence, Rhode Island, 2018.
  * [10] J. F. Hall, T. D. Todorov, T. D. Ordered Fields, the Purge of Infinitesimals from Mathematics and the Rigorousness of Infinitesimal Calculus. _Bulgarian Journal of Physics_ 42(2): 99–127 (2015).
  * [11] Matthias Keller, Daniel Lenz, Radoslaw Wojciechowski.  Graphs and Discrete Dirichlet Spaces. Grundlehren der mathematischen Wissenschaften, 358, Springer, 2021.
  * [12] Serge Lang. Algebra. Graduate Texts in Mathematics, 211. Springer, 2002.
  * [13] Tullio Levi-Civita.  Sugli infiniti ed infinitesimi attuali quali elementi analitici.  Atti Ist. Veneto di Sc., Lett. ed Art., 7a, 4:1765 (1892).
  * [14] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer.  Markov Chains and Mixing Times.  Providence, Rhode Island, 2009.
  * [15] Anna. Muranova. On the notion of effective impedance. _Operators and Matrices_. Volume 14, Number 3 (2020), 723-741.
  * [16] Anna. Muranova. Effective impedance over ordered fields. _J. Math. Phys. 62_ , 033502 (2021).
  * [17] A.R. Pruss, Underdetermination of infinitesimal probabilities. _Synthese_ 198, 777–799 (2021).
  * [18] Simon Rubinstein-Salzedo, Ashvin Swaminatham. Analysis on Surreal Numbers. _Journal of Logic & Analysis_. 6:5 (2014) 1–39
  * [19] Khodr Shamseddine. A brief survey of the study of power series and analytic functions on the Levi-Civita fields, _Contemporary Mathematics_ 596: 269–279(2013).
  * [20] Khodr Shamseddine. em New Elements of Analysis on the Levi-Civita Field. Thesis (Sc. D.) Michigan State University, East Lansing, Michigan, USA (1999).
  * [21] Khodr Shamseddine, Martin Berz. Analysis on the Levi-Civita field, a brief overview. _Contemporary Mathematics_ 508: 215–237 (2010).
  * [22] B.L. van der Waerden. Algebra. Volume 1. Springer, 2003.
  * [23] Wolfgang Woess.  Denumerable Markov Chains.  EMS, 2009.