bib

# Parallel Generation of Massive Scale-Free Graphs

Andy Yoo  Keith Henderson

(Lawrence Livermore National Laboratory
Livermore, CA 94551)

###### Abstract

One of the biggest huddles faced by researchers studying algorithms for
massive graphs is the lack of large input graphs that are essential for the
development and test of the graph algorithms. This paper proposes two
efficient and highly scalable parallel graph generation algorithms that can
produce massive realistic graphs to address this issue. The algorithms,
designed to achieve high degree of parallelism by minimizing inter-processor
communications, are two of the fastest graph generators which are capable of
generating scale-free graphs with billions of vertices and edges. The
synthetic graphs generated by the proposed methods possess the most common
properties of real complex networks such as power-law degree distribution,
small-worldness, and communities-within-communities. Scalability was tested on
a large cluster at Lawrence Livermore National Laboratory. In the experiment,
we were able to generate a graph with 1 billion vertices and 5 billion edges
in less than 13 seconds. To the best of our knowledge, this is the largest
synthetic scale-free graph reported in the literature.

##  1 Introduction

Recent studies have revealed that many real-world graphs belong to a special
class of graphs called complex networks (or graphs). Examples of the real-
world complex graphs include World-Wide Web [4], Internet [12, 13, 25, 30],
electric power grids [31], citation networks [16, 26, 28, 29], telephone call
graphs [1], and e-mail network [9]. These graphs typically carry a wealth of
valuable information for their respective domains. Therefore, a great deal of
research effort has been concentrated on developing algorithms to identify and
mine certain knowledge or data of interest from these graphs. For example,
algorithms that can find groups of vertices that have strong associations
between them (called communities) have been reported [5, 8, 22, 23, 24]. There
exist algorithms which, given a template pattern, can find subgraphs that
closely match to the input pattern [17]. Such algorithms can play a very
important role in detecting certain criminal activities or making critical
business decisions.

The real-world complex graphs are typically very large (with millions or more
vertices) and their sizes grow over time. Some researchers predict that the
size of these graphs will eventually reach $10^{15}$ vertices [15]. The high
complexity of the graph algorithms, combined with the large and increasing
size of the target graphs, however, makes these applications to be very
difficult to apply to large real graphs. Efforts are being made to parallelize
these applications [32, 2] and develop efficient out-of-core graph algorithms
[27] to cope with the technical challenges.

One of key issues in developing these graph applications is the availability
of large input graphs, as these graphs are essential for the developers to
develop and test the applications and to measure their scalability and
performance. Unfortunately, we do not have publicly available real graphs that
are large enough to test the functionality and true scalability of the graph
applications. A social network graph derived from the World Wide Web, for
example, contains 15 million vertices [11] and the largest citation network
available has two million vertices [21]. Although these real-world graphs tend
to grow in size, it is unlikely that the real graphs of sufficiently large
size will be available in the near future.

The lack of the large graphs has forced the researchers to use synthetically
generated random graphs, which are relatively cheap to construct, in their
experiments [32]. The random graphs (also known as Erdös-Rényi random graphs
[10]), however, is uninformative, since the structure of the random graphs
greatly differs from that of real-world graphs. In the absence of the large
real graphs, synthetic graphs may be used for the development of the graph
applications. There exist several good models to synthetically generate
complex networks [3, 18, 31]. A serious drawback of these models is that they
are all sequential models and hence, are inadequate to use to generate the
massive graphs with billions of vertices and edges.

In this paper, we propose two efficient and highly scalable graph generation
methods. Based on serial models [3, 18], these methods are designed to
generate massive scale-free graphs in parallel on distributed parallel
computers. These parallel generators require very little inter-processor
communications and thus achieve high degree of parallelism. The first method,
called parallel Barabasi-Albert (PBA) method, iteratively builds a graph using
a technique called two-phase preferential attachment. The second parallel
method, called parallel Kronecker (PK) method, applies the concept of
Kronecker product of matrices [14] and constructs a graph recursively in a
fractal fashion from a given seed graph. These are two of the fastest graph
generation algorithms with capability of generating scale-free graphs with
billions of vertices and edges. We have demonstrated their scalability by
constructing massive graphs on a large cluster at Lawrence Livermore National
Laboratory. In the experiment, we have generated a scale-free graph with 1
billion vertices and 5 billion edges in less than 13 seconds, and to the best
of our knowledge, this is the largest synthetic scale-free graph ever reported
in the literature. We also have analyzed the properties of the graphs
generated by the proposed methods and report the results in this paper. We
have found that these graphs possess commonly known properties of real-world
complex networks, including power-law degree distribution, small-worldness,
and communities-within-communities.

The remaining of the paper is organized as follows. Section 2 surveys the
related work in the literature. The proposed parallel models are described in
Section 3. Section 4 presents the results from performance and
characterization study, followed by concluding remarks and directions for
future work in Section 5.

##  2 Related Work

Erdös and Rényi have proposed a simple model that generates equilibrium random
graphs, called Erdös-Rényi random graphs [10]. In this model, given a fixed
number of vertices, a graph is constructed by connecting randomly chosen
vertices with an edge repeatedly until the predetermined number of edges are
obtained. This model is restrictive in that it produces only Poisson degree
distributions.

Dorogovtsev et al. proposed a model that can generate graphs with fat-tailed
degree distributions [7]. Given a random graph, this model restructures the
given graph by rewiring a randomly chosen end of a randomly chosen edge to a
preferentially chosen vertex and also moving a randomly chosen edge to a
position between two preferentially chosen vertices at each step of the
evolution.

The model proposed by Watts and Strogatz [31] generates random structures with
small diameter, which has been named as small-world graphs. This model
transforms a regular one-dimensional lattice (with vertex degree of four or
higher) by rewiring each edge, with certain probability, to a randomly chosen
vertex. It has been found that, even with the small rewiring probability, the
average shortest-path length of the resulting graphs is of the order of that
of random graphs, and generate graphs with fat-tailed degree distributions.

The majority of recent models uses a method called preferential attachment
[6]. In a representative model among these, proposed by Barabasi and Albert
[3], a new vertex joins the graph at each time step and gets connected to an
existing vertex with probability proportional to the vertex degree. With
preferential attachment, these models can emulate the dynamic growth of real
graphs.

Leskovec et al. [18] have proposed a graph generation model that addresses
some of recently discovered properties of time-evolving graphs: densification
and shrinking diameter. The main idea of their model is to recursively create
self-similar graphs with certain degree of randomness. The self-similarity of
the graphs is achieved by using the Kronecker product (also known as tensor
product) [14], which is a natural tool to construct self-similar structures.
Given a seed graph, at each step this model computes the Kronecker product of
two matrices that represent the seed graph and the graph generated in previous
step respectively. The graphs generated with this method have regular
structure. The model changes the entries in the target matrix with a certain
probability before each multiplication to add randomness to the graph.

##  3 Proposed Graph Generation Methods

### Parallel Barabasi-Albert (PBA) method

Scale-free graphs can be easily generated using a well-known technique called
preferential attachment [6]. In a simple serial model known as Barabasi-Albert
(BA) model [3], a scale-free graph is constructed, starting with a small
clique, by repeatedly creating a vertex and attach it to one of the existing
vertices with probability proportional to its current degree.

We have parallelized the BA model in this research and propose a graph
generation algorithm called parallel BA (PBA) method. In this method, vertices
are distributed to the processors, and all the edges adjacent to a given
vertex are stored on the same processor to which the vertex is assigned.

Sets of processors called factions are used in the PBA method. Each processor
belongs to one or more factions. The number of processors in each faction
varies. Such variation is essential for the correct implementation of the
preferential attachment operation in a distributed environment. Furthermore,
we can assign the processors to factions in a manner to enable us to generate
graphs with certain structures. The size of each faction is a degree of
freedom in this method. The number of factions is another degree of freedom.
To facilitate the implementation, we choose to assign all vertices on a single
processor to the same set of factions. In other words, if two vertices reside
on the same processor, then they are members of the same set of factions.

It is crucial to use an efficient implementation of the preferential
attachment to allow this method to scale. This can be done most efficiently by
selecting an existing edge from the graph with a uniform probability and then
randomly selecting one of its endpoints as the point to which a new vertex can
be attached. Therefore, an edge can be added in constant time in this
implementation.

A slight variation of this algorithm is used in the PBA method. The proposed
PBA algorithm is described below in detail. It is assumed that the algorithm
runs on a processor $p$. Other processors perform the same algorithm. We also
assume that $p$ is a member of factions $F_{0}$, $F_{1}$, …, $F_{n-1}$.

In the PBA method, an edge is attached in two phases. In the first phase of
our preferential attachment, $k$ edges are added per newly created local
vertex (a vertex that resides on $p$) as in the conventional BA model.
However, each edge, $e$, associates a local vertex with some processor $q$,
instead of connecting two vertices as in the serial model. The particular
vertex that is to be the eventual endpoint of $e$ is determined remotely by
the processor $q$.

The processor $q$ is selected using a variation of the preferential attachment
algorithm as follows. Let $A$ denote a local edge list maintained by the
processor $p$. First, we initialize $A$ by associating the first $s$ edges
with the processors in factions $F_{0}$, $F_{1}$, …, $F_{n-1}$, matching
sequentially one edge to one processor in the set of factions. Here, $s$ is
the total number of processors in factions $F_{0}$, $F_{1}$, …, $F_{n-1}$
(i.e., $s=\sum_{i=0}^{n-1}|F_{i}|$). For an edge $e_{j}$, where $j\geq s$, we
select an existing edge from $A$ with a uniform probability (thus realizing
preferential attachment) and then assign its associated processor to $e_{j}$.
This process is repeated until the predetermined number of local vertices and
edges are created on $p$. At the end of the first phase, $p$ sends a message
to each processor $q$ to notify the number of occurrences of $q$ in $A$.

In the second phase, $p$ determines the endpoints for the edges on remote
processors and connects the endpoints calculated by remote processors to its
local vertices. The processor $p$ first receives messages from other
processors, which contain the numbers of occurrences of $p$ in their
respective local edge list. That is, the message received from a processor $q$
represents the number of incomplete edges one of whose endpoints resides on
the processor $q$. These edges are to be connected to the local vertices on
$p$, selected by using the standard preferential attachment technique. Once
the list of the vertices for the attachment is determined, it is divided up
among the processors. Here, each processor is assigned as many vertices as it
requested. The selected vertices are then sent to the corresponding
processors.

Having sent the endpoints for the remote edges, then $p$ receives the lists of
endpoints from other processors for its own incomplete edges. Using the remote
vertices received, $p$ completes its local partition of the graph. This is
done by simply substituting each occurrence of processor $q$ in $A$ with the
next endpoint in the list sent by $q$. The resulting collection of edges
defines the portion of the graph stored on $p$.

| $u$ | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4
---|---|---|---|---|---|---|---|---|---|---
$v$ | $P_{1}$ | $P_{2}$ | $P_{0}$ | $P_{1}$ | $P_{1}$ | $P_{2}$ | $P_{0}$ | $P_{1}$ | $P_{0}$ | $P_{2}$
(a) Edge list on $P_{0}$ at the end of phase 1
| $u$ | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4
---|---|---|---|---|---|---|---|---|---|---
$v$ | 8 | $P_{2}$ | $P_{0}$ | 7 | 5 | $P_{2}$ | $P_{0}$ | 8 | $P_{0}$ | $P_{2}$
(b) A snapshot of edge list on $P_{0}$ during the phase 2
Figure 1: An example of PBA graph construction on processor $P_{0}$. A list of
edges, ($u$, $v$) is maintained on $P_{0}$, where $u$ denotes a local vertex
and $v$ is an endpoint determined by remote processors in phase 2. In this
example, three factions are used, where $F_{0}$ = {$P_{1}$, $P_{2}$}, $F_{1}$
= {$P_{1}$, $P_{3}$}, $F_{2}$ = {$P_{0}$, $P_{1}$}. Processor $P_{0}$ belongs
to fractions $F_{0}$ and $F_{2}$.

The two-phase preferential attachment is explained using an example in Figure
1. In this example, we generate a graph with 5 vertices per processor and 2
edges per vertex. It is assumed that there are three factions, $F_{0}$ =
{$P_{1}$, $P_{2}$}, $F_{1}$ = {$P_{1}$, $P_{3}$}, and $F_{2}$ = {$P_{0}$,
$P_{1}$} and processor $P_{0}$ belongs to fractions $F_{0}$ and $F_{2}$. The
vertices are assumed to be evenly distributed among the processors so that
vertices 0–4 are on $P_{0}$, vertices 5–8 on $P_{1}$, and so on.

In the first phase of the algorithm, $P_{0}$ selects processors and associates
them with the local vertices as shown in Figure 1.a, where the edge list on
$P_{0}$ is depicted. Note that the first four processors in the list are the
ones in the factions that $P_{0}$ belongs to, $F_{0}$ and $F_{2}$. The rest of
the processors in the list are selected using the standard preferential
attachment technique. At the end of phase 1, $P_{0}$ needs four endpoints from
$P_{1}$ (and three endpoints from each of $P_{0}$ and $P_{2}$). These
endpoints are determined by processor $P_{1}$ via preferential attachment and
sent to $P_{0}$ in the second phase. In this example, we assume that vertices
8, 7, 5, and 8 are sent to $P_{0}$. Once receiving the list, $P_{0}$ simply
replaces the entries marked with $P_{1}$ with the endpoints in the list. This
is shown in Figure 1.b.

We have found that it is useful to modify the algorithm slightly to
incorporate some inter-faction edges. In particular, during the first phase,
we occasionally select a processor that is not in any of the factions of $p$.
Such processors are chosen randomly. The probability of creating an inter-
faction edge is an another degree of freedom in this algorithm.

### Parallel Kronecker (PK) method

|
---
| $\left(\begin{array}[]{ccccc}1&1&1&1&0\\\ 1&1&0&0&0\\\ 1&0&1&0&0\\\
1&0&0&1&0\\\ 0&0&0&0&1\\\ \end{array}\right)$
---
(a) Seed graph $G_{1}$ with 5 vertices | (b) Adjacency matrix for $G_{1}$

| $\left(\begin{array}[]{ccccc}G_{1}&G_{1}&G_{1}&G_{1}&0\\\
G_{1}&G_{1}&0&0&0\\\ G_{1}&0&G_{1}&0&0\\\ G_{1}&0&0&G_{1}&0\\\
0&0&0&0&G_{1}\\\ \end{array}\right)$
---
|
---
(c) Adjacency matrix for $G_{2}=G_{1}\otimes G_{1}$ | (d) Plot for $G_{4}$

Figure 2: An example of the Kronecker multiplication for graph generation.
$G_{2}$ is constructed by multiplying the seed graph with itself (that is,
$G_{2}=G_{1}\otimes G_{1}$). The self-similarity in $G_{4}$ is clearly shown
in (d).

A model that uses well-known concept of Kronecker matrix multiplication to
generate scale-free graphs has been recently proposed [18]. If $A$ is an
$m\times n$ matrix and $B$ is a $p\times q$ matrix, then the Kronecker product
$A\otimes B$ is the $mp\times nq$ block matrix, defined as

$\displaystyle A\otimes B=\left(\begin{array}[]{ccc}a_{11}B&\cdots,&a_{1n}B\\\
\vdots&\ddots&\vdots\\\
a_{m1}B&\cdots,&a_{mn}B\end{array}\right)~{}\cite[cite]{[\@@bibref{}{horn1991}{}{}]}.$

The Kronecker product of two graphs is defined as the Kronecker product of
their adjacency matrices. Figure 2 shows an example where a Kronecker graph is
generated from given seed graph using the Kronecker graph multiplication.
Since the Kronecker method is an ideal tool to construct self-similar
structures, the graph generated by this method has also self-similar structure
as shown in Figure 2.d.

Implementing a serial algorithm for the above graph generation method is
straightforward. Starting with an $n_{0}\times n_{0}$ adjacency matrix with
$e_{0}$ edges representing a given seed graph, we recursively construct larger
adjacency matrices using Kronecker matrix multiplication in a top-down manner.
To generate the $i_{th}$ matrix from the $(i-1)_{th}$ matrix, we simply
replace every 1 in the $i_{th}$ matrix by an $n_{0}\times n_{0}$ block that is
a copy of the seed graph. We replace every 0 by an $n_{0}\times n_{0}$ block
of zeros. So if the $i_{th}$ graph has $n_{i}$ vertices, the $(i+1)_{th}$
graph has $n_{i}\times n_{i}$ vertices. Thus, $n_{i}$ = $n_{0}^{i+1}$ for all
iterations. We treat each edge in the graph at each iteration as a meta-edge.
A meta-edge is defined by its iteration and its position in the graph for that
particular iteration. Given the size of a target graph, we can calculate the
number of iterations required to generate the target graph.

A Kronecker graph can be generated efficiently by using a stack, initialized
with the edges in the seed graph. A graph is generated by expanding meta-edges
in the stack as follows. First, a meta-edge on the top of the stack is popped
up. If its iteration, $i$, is equal to the predetermined final iteration, then
the edge is added to the final graph. Otherwise, new meta-edges with iteration
$i+1$ are generated and pushed onto the stack. This operation is repeated
until the stack is depleted. We choose a stack because it guarantees that the
memory requirement is limited to $O(\sqrt[e_{0}]{|E|})$, where $|E|$ is the
number of edges in the final graph. An implementation using a queue is not
scalable, as it would require $O(|E|)$ memory space.

In the parallel implementation of the Kronecker method, the meta-edges are
divided among the groups of processors at each iteration. Each processor group
generates the same meta-edges at a given iteration. If there are more
processors in a processor group than there are edges in that group’s portion
of the graph, then each processor in the group is assigned to a single edge in
the stack. Here, each edge defines a new processor group that is a subset of
the original, and the process group ignores all other meta-edges at that
iteration. On the other hand, if there are more meta-edges than processors in
the processor group, the edges are divided as evenly as possible among those
processors. Each of those processors is then in a singleton processor group
for the remaining iterations. Each processor must be able to calculate on the
fly which meta-edges are in its processor group at a given iteration.

In general, it is difficult to achieve good load balance with the PK method,
as some processors may be assigned more work depending on processor group
sizes. A dynamic load balancing scheme may be used in conjunction with the PK
method to overcome this limitation. Furthermore, some randomization logics are
needed to irregulate the structure of the PK graphs. One approach for the
randomization is to add or delete meta-edges during the replacement phase at
each iteration by randomly modifying the seed graph temporarily. Another
approach is to perform exclusive-OR operation between the final adjacency
matrix with the adjacency matrix for a random graph.

##  4 Experimental Results

###  4.1 Experiment environment and metrics of interest

We have conducted a study to evaluate the proposed graph generators. The
experiments were conducted on MCR [20], a large Linux cluster located at
Lawrence Livermore National Laboratory. MCR has 1,152 nodes interconnected
with a Quadrics switch, and each of the compute nodes has two 2.4 GHz Intel
Pentium 4 Xeon processors and 4 GB of memory,

In this study, we are mainly interested in evaluating the performance of the
proposed graph generators and analyzing the graphs they generate. There are
well-known structural and temporal properties of the real complex networks
[19]. We use widely-accepted properties as indices to quantitatively evaluate
the synthetic graph generated by the proposed methods.

###  4.2 Results

Methods |  $|V|$ (Million) |  $|E|$ (Billion) | Time (Seconds)
---|---|---|---
PBA | 1,000 | 5 | 12.39
PK | 0.53 | 5.4 | 2.53
Table 1: Comparison of graph generation time by PBA and PK methods. The number
of vertices and edges in generated graphs are denoted by $|V|$ and $|E|$,
respectively.

Two graphs were generated by using the PBA and PK methods on 1,000 processors
on the MCR cluster, and we report the graph generation times in Table 1. The
generation time is an average of multiple runs. We have measured the maximum
time across all processes in each run. The disk I/O time is not included in
the time reported.

Both graphs have about 5 billion edges.111We measure the size of a graph by
the total space needed to store the graph in this paper. That is, given a
graph $G$ = ($V$, $E$), its size is $|V|+|E|$. Therefore, we consider the PBA
graph to be larger than the PK graph in this experiment. The number of
vertices in the PK graph is considerably smaller than that in the PBA graph
due to our use of a seed graph with large average degree. As shown in the
table, it takes less than 13 seconds to generate these massive graphs. The
high generation rate can be attributed to the high degree of parallelism of
the proposed algorithms.

---
Figure 3: Weak-scaling results

The performance of both methods is further detailed in Figure 3, where we show
the results from a weak-scaling study. In a weak-scaling test, the global
problem size increases as the total number of processors increases such that
the size of local problem remains constant. The local problem size of roughly
one million vertices and three million edges is used. The figure reveals that
the PK method is about four times faster than the PBA method. In particular,
the almost flat curve for the PK method highlights the embarrassingly-parallel
nature of the algorithm. The graph generation time for the PBA method, on the
other hand, increases as the number of processors increases. This is because
in the PBA method each processor processes endpoint vertices sent by remote
processors at the end of the execution, and the complexity of the processing
increases in proportion to the total number of processors used. Profiling of
the code confirms that each process spends most of its time in processing the
received endpoints.

|
---|---
(a) PBA graph ($\gamma=2.75$) | (b) PK graph ($\gamma=2.47$)

---
(c) Router graph ($\gamma=2.19$)

Figure 4: Degree distributions of the synthetic and router graphs. Here $k$
and $P(k)$ denote the degree and the number of vertices with degree $k$,
respectively. The $\gamma$ exponent of a power-law distribution, $P(k)\propto
k^{-\gamma}$, for each graph is obtained through curve fittings and shown here
as well.

In the remaining of this section, we analyze the graphs produced by the
proposed methods. A PBA graph studied in this experiments has 330,000 vertices
and 2 million edges. A PK graph with 160,000 vertices and 28 million edges,
constructed using a small seed graph with 20 vertices and 40 edges, is
analyzed. We also consider two real-world graphs, WWW and router graphs, for
comparison. The WWW graph has 325,000 vertices and 2.1 million edges, and the
smaller router graph has 285,000 vertices and 861,000 edges.

Figure 4 presents the degree distributions of the synthetic graphs and
compares them with that of the router graph. The graphs are shown in a log-log
scale. As shown in the figure, the curves for both PBA and PK graphs are
heavy-tailed. This is a signature of power-law degree distribution that is one
of the widely accepted property of real-world complex networks. It is shown in
Figure 4.c that the router graph also has fat-tailed degree distribution. To
verify that these graphs have power-law degree distributions, $P(k)\propto
k^{-\gamma}$, we have performed curve fittings for the measured degree
distributions and show the exponent of the power-law distribution ($\gamma$)
in Figure 4. As shown in the figure, $\gamma$ values for the three graphs are
greater than 2. This finding coincides with the fact that if the average
degree of a scale-free graph is finite, then its $\gamma$ value should be
$2<\gamma<\infty$ [6]. The PK graph has a large number of high degree
vertices. This is because the number of low-degree vertices is small in a
graph generated by the PK method, in which the degree of a vertex grows
exponentially. We can change the degree distribution by randomly adding low-
degree vertices to the final graph.

Graph | Avg. Path Length | Diameter (estimated)
---|---|---
WWW Graph | 7.54 | 46
Router Graph | 8.87 | 27
PK Graph | 3.20 | 5
PBA Graph | 6.26 | 12
Table 2: The comparison of path length and diameter of the synthetic graphs
with two real graphs. Both metrics are estimated by sampling to reduce the
computation overhead.

Table 2 presents the average path lengths and diameters of the two synthetic
graphs considered in the previous experiment as well as the WWW and router
graphs. Both metrics are estimates obtained through sampling to reduce the
computation time. Each of the graphs analyzed has short average path length,
which is the average value of the shorted path between two randomly chosen
vertices. Further, each synthetic graph has a small diameter that is the
maximum of all-pairs shortest path. These results indicate that the graphs
generated by the proposed methods have small world property, which is another
key characteristic of real-world complex networks. Obviously, such small-
worldness is more evident in the PK graph, as it contains a large number of
high-degree vertices (or hubs). Two real graphs, the WWW graph in particular,
appear to have the smaller number of hubs as indicated by the larger
diameters.

|
---
|
---
(a) PBA graph | (b) PK graph
Figure 5: Communities within PBA and PK graphs. The graphs are represented as
adjacency matrices.

In Figure 5, we show two adjacency matrices for PBA and PK graphs to visualize
the community structures within these synthetic graphs. As shown in the
figure, the PBA and PK graphs have clearly identifiable community structures.
A major difference between the two graphs is that the PK graph has more
regularly-structured communities compared to the PBA graph. The regular
community structure of the PK graph is the result of the systematic way of
graph construction by the PK method (using the Kronecker matrix
multiplication). In addition, the self-similar nature of the Kronecker product
is translated into the communities-within-communities structure in the PK
graph.

###  4.3 Comparison of the PBA and PK methods

An advantage of the PK method over the PBA method is its higher degree of
parallelism. The PK method is embarrassingly parallel, as once a seed graph is
given, processors generate the assigned portions of the target graph
independent of each other. A key limitation of the PK method is that the
structure of a resulting graph heavily depends on that of the initial seed
graph. In fact, even with randomized edge generation and removal, the
structure of final graph largely depends on the seed graph and thus relatively
regular. In consequence, this limitation makes it very difficult to configure
the PK method to generate a graph with desired property. For example, if the
seed graph is too small it is very difficult to control the degree of
vertices. To control the vertex degree, we need a relatively large seed graph,
but with such a large seed graph, it is hard to control the size of the final
graph.

Although slower than the PK method, the PBA method is still a very fast
algorithm. An obvious advantage of the PBA method is that using preferential
attachment as a key means to construct a graph, the method can be easily
configured to generate a graph of desired size and properties.

##  5 Conclusions and Future Work

Two efficient and scalable parallel graph generation methods that can generate
scale-free graphs with billions of vertices and edges are proposed in this
paper. The proposed parallel Barabasi-Albert (PBA) method iteratively builds
scale-free graphs using two-phase preferential attachment technique in a
bottom-up fashion. The parallel Kronecker (PK) method, on the other hand,
constructs a graph recursively in a top-down fashion from a given seed graph
using Kronecker matrix multiplication. These parallel graph generators operate
with high degree of parallelism. We have generated a graph with 1 billion
vertices and 5 billion edges in less than 13 seconds on a large cluster. This
is the highest rate of graph generation reported in the literature. We have
analyzed the graphs produced by our methods and shown that they have the most
common properties of the real complex networks such as power-law degree
distribution, small-worldness, and communities-within-communities.

There are other known and somewhat debatable properties of complex networks. A
rigorous study of the graphs generated by the proposed methods will reveal
whether these methods can produce synthetic graphs with these properties. This
study will also provide us with better understanding of how the logics used in
our algorithms affect the properties of the synthetic graphs they generate.
Based on this study, we will develop a set of pre- and post-generation
processing and randomization techniques that will enable us to construct a
synthetic graph with desired properties.

## References

  * [1] W. Aiello, F. Chung, and L. Lu.  A random graph model for massive graphs.  In Proceedings of the thirty-second annual ACM symposium on Theory of computing (STOC ’00), pages 171–180, New York, NY, USA, 2000.
  * [2] D. A. Bader and K. Madduri.  Designing multithreaded algorithms for breadth-first search and st-connectivity on the cray mta-2.  In Proceedings of International Conference on Parallel Processing (ICPP 2006), Aug. 2006.
  * [3] A.-L. Barabasi and R. Albert.  Emergence of scaling in random networks.  Science, 286:509, 1999.
  * [4] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, and A. Tomkins.  Graph structure in the web: Experiments and models.  In 9th World Wide Web Conference, 2000.
  * [5] A. Clauset, M. E. J. Newman, and C. Moore.  Finding community structure in very large networks.  Phys. Rev. E, 70(6):066111, Dec. 2004.
  * [6] S. N. Dorogovtsev and J. F. F. Mendes.  Evolution of Networks.  Oxford University Press, 2004.
  * [7] S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin.  Principles of statistical mechanics of random networks.  Nuclear Physics B, 666:396, 2003.
  * [8] J. Duch and A. Arenas.  Community detection in complex networks using extremal optimization.  Physical Review E, 72:027104, Jan. 2005.
  * [9] H. Ebel, L.-I. Mielsch, and S. Bornholdt.  Scale-free topology of e-mail networks.  Physical Review E, 66:035103, 2002.
  * [10] P. Erdös and A. Rényi.  On random graphs.  Publ. Math. Debrecen, 6:290–297, 1959.
  * [11] C. Faloutsos, K. McCurley, and A. Tomkins.  Fast discovery of connection subgraphs.  In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 118–127, Seattle, WA, USA, 2004\.
  * [12] M. Faloutsos, P. Faloutsos, and C. Faloutsos.  On power-law relationships of the internet topology.  In SIGCOMM, pages 251–262, 1999.
  * [13] R. Govindan and H. Tangmunarunkit.  Heuristics for internet map discovery.  In IEEE INFOCOM 2000, pages 1371–1380, Tel Aviv, Israel, March 2000.
  * [14] R. Horn and C. Johnson.  Topics in Matrix Analysis.  Cambridge University Press, 1991.
  * [15] T. Kolda, D. Brown, J. Corones, T. Critchlow, T. Eliassi-Rad, L. G. andBruce Hendrickson, V. Kumar, D. Lambert, C. Matarazzo, K. McCurley, M. Merrill, N. Samatova, D. Speck, R. Srikant, J. Thomas, M. Wertheimer, and P. C. Wong.  Data sciences technology for homeland security information management and knowledge discovery, 2004.  Report of the DHS Workshop on Data Sciences.
  * [16] P. L. Krapivsky, S. Redner, and F. Leyvraz.  Connectivity of growing random networks.  Physical Review Letters, 85:4629, 2000.
  * [17] M. Kuramochi and G. Karypis.  Frequent subgraph discovery.  In Proceedings of the 2001 IEEE International Conference on Data Mining (ICDM ’01), pages 313–320, Washington, DC, USA, 2001.
  * [18] J. Leskovec, D. Chakrabarti, J. Kleinberg, and C. Faloutsos.  Mathematically tractable graph generation and evolution, using kronecker multiplication.  In Proceedings of European Conference on Principles and Practice of Knowledge Discovery in Databases, 2005.
  * [19] J. Leskovec, J. Kleinberg, and C. Faloutsos.  Graphs over time: densification laws, shrinking diameters and possible explanations.  In Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining (KDD ’05), pages 177–187, 2005\.
  * [20] Multiprogrammatic Capability Cluster (MCR).  http://www.llnl.gov/linux/mcr.
  * [21] M. E. J. Newman.  From the cover: The structure of scientific collaboration networks.  Proceedings of the National Academy of Sciences, 98:404–409, 2001\.
  * [22] M. E. J. Newman.  Detecting community structure in networks.  European Physical Journal B, 38:321–330, May 2004.
  * [23] M. E. J. Newman.  Fast algorithm for detecting community structure in networks.  Phys. Rev. E, 69(6):066133, June 2004.
  * [24] M. E. J. Newman and M. Girvan.  Finding and evaluating community structure in networks.  Phys. Rev. E, 69(2):026113, Feb. 2004.
  * [25] R. Pastor-Satorras, A. Vazquez, and A. Vespignani.  Dynamical and correlation properties of the internet.  Physical Review Letters, 87:258701, 2001.
  * [26] S. Redner.  How popular is your paper? an empirical study of the citation distribution.  The European Physical Journal B, 4:131, 1998.
  * [27] J. F. Sibeyn, J. Abello, and U. Meyer.  Heuristics for semi_external depth first search on directed graphs.  In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, (SPAA’02), pages 282–292, 2002.
  * [28] C. Tsallis and M. P. de Albuquerque.  Are citations of scientific papers a case of nonextensivity?  The European Physical Journal B, 13:777, 2000.
  * [29] A. Vazquez.  Statistics of citation networks, 2001.  cond-mat/0105031.
  * [30] A. Vazquez, R. Pastor-Satorras, and A. Vespignani.  Large-scale topological and dynamical properties of internet.  Physical Review E, 65:066130, 2002.
  * [31] D. J. Watts and S. H. Strogatz.  Collective dynamics of small-world networks.  Nature, 393:440–442, 4 June 1998.
  * [32] A. Yoo, E. Chow, K. Henderson, W. McLendon, B. Hendrickson, and Ümit Çatalyürek.  A scalable distributed parallel breadth-first search algorithm on bluegene/l.  In Proceedings of Supercomputing’05, Nov. 2005.


Dedicated to the 85th birthday of Sergey Petrovich Novikov

# On the Novikov problem with a large number of quasiperiods and its
generalizations

A.Ya. Maltsev  L.D. Landau Institute for Theoretical Physics of Russian
Academy of Sciences
142432 Chernogolovka, pr. Ak. Semenova 1A

###### Abstract.

The paper considers the Novikov problem of describing the geometry of level
lines of quasi-periodic functions on the plane. We consider here the most
general case, when the number of quasi-periods of a function is not limited.
The main subject of investigation is the arising of open level lines or closed
level lines of arbitrarily large sizes, which play an important role in many
dynamical systems related to the general Novikov problem. As can be shown
also, the results obtained for quasiperiodic functions on the plane can be
generalized to the multidimensional case. In this case, we are dealing with a
generalized Novikov problem, namely, the problem of describing level surfaces
of quasiperiodic functions in a space of arbitrary dimension. Like the Novikov
problem on the plane, the generalized Novikov problem plays an important role
in many systems containing quasiperiodic modulations.

##  1\. Introduction

We consider here the Novikov problem, namely, the problem of describing the
level lines of quasi-periodic functions on the plane with an arbitrary number
of quasi-periods. In this case, the description of the global geometry of open
(non-closed) level lines is of greatest interest, although the study of closed
level lines also plays an important role in describing the general picture. We
will here call a quasi-periodic function on the plane $\,f(x^{1},x^{2})\,$ the
restriction of an $N$-periodic function $\,F(z^{1},\dots,z^{N})\,$ for some
affine embedding $\,\mathbb{R}^{2}\subset\mathbb{R}^{N}\,$. The number $N$ is
called the number of quasi-periods of the function $\,f(x^{1},x^{2})\,$. Here
we will assume that the function $\,F(z^{1},\dots,z^{N})\,$ is sufficiently
smooth.

The first non-trivial and most deeply studied case of the Novikov problem is
the description of the level lines of quasi-periodic functions on the plane
with three quasi-periods. It is in this formulation that this problem was
first set in [1] and then intensively studied at Novikov’s topological school.
The Novikov problem with three quasiperiods plays a very important role in the
theory of magnetoconductivity of normal metals, since in this formulation it
is directly related to the description of the geometry of semiclassical
electron trajectories on Fermi surfaces in the presence of external magnetic
fields. The geometry of such trajectories, in turn, has the most significant
influence on the behavior of magnetotransport phenomena in metals in the limit
$\,B\rightarrow\infty\,$ ([2, 3, 4, 5]). The most significant results, which
form the basis for the description of level lines of functions with three
quasi-periods on the plane, were obtained in the papers [6, 7, 8, 9, 10, 11,
12]. The study of the Novikov problem in this case makes it possible to
determine important topological quantities, as well as to give a
classification of all non-trivial regimes observed in transport phenomena in
metals in strong magnetic fields (see, for example, [13, 14, 15, 16]).

At present, a number of deep topological results have also been obtained for
the Novikov problem with four quasi-periods (see [17, 18]). It can be noted,
however, that this problem has not been studied in as much detail as the
Novikov problem with three quasi-periods.

In general, the Novikov problem with an arbitrary number of quasi-periods has
many important applications, especially in the theory of complex two-
dimensional systems. The study of the Novikov problem, especially the
description of the geometry of non-compact level lines, is associated with
very diverse aspects of the dynamics in such systems. Very often arising
quasiperiodic functions play the role of potential energy in the problems
under consideration. We will therefore call here quasiperiodic functions also
quasiperiodic potentials. Most often, the occurrence of open level lines, or
closed level lines of arbitrarily large sizes, has a significant impact on the
behavior of transport phenomena that arise in the corresponding two-
dimensional systems. It can be noted that the study of the Novikov problem
with a large number of quasiperiods can also be considered as one of the
approaches to the study of random potentials on the plane. It must be said
that the study of the Novikov problem, in a wide variety of its aspects,
currently represents a whole direction in topology and the theory of dynamical
systems (see, for example, a review of recent results and literature in [19]).

In this paper we present a number of results related to the Novikov problem
with an arbitrary number of quasiperiods. More precisely, we prove here a
number of statements about the occurrence of open (non-compact) level lines,
as well as closed level lines of arbitrarily large diameter for embeddings
$\,\mathbb{R}^{2}\subset\mathbb{R}^{N}\,$ and functions
$\,F(z^{1},\dots,z^{N})\,$ in general position. The assertions formulated here
are, in fact, a further development of the results obtained in [19] and
related to the Novikov problem in its most general formulation. The results
presented here refer mainly to the case $\,N\geq 4\,$. The case $\,N=3\,$, as
shown in [6, 7, 8, 9, 10, 11, 12], actually admits a more detailed
description.

In fact, as we will also show here, similar statements can be proven for the
generalized Novikov problem, namely, the problem of describing the geometry of
level surfaces of quasiperiodic functions in spaces of arbitrary dimension.
Like the results for the Novikov problem on the plane, these statements can
play an important role in many phenomena associated with quasiperiodic
modulations in higher-dimensional systems.

##  2\. Sets of open and closed level lines of quasi-periodic functions on the
plane

In this work, we will consider the features of quasiperiodic potentials that
appear in cases of four or more quasiperiods. In this formulation, Novikov’s
problem does not, generally speaking, relate to the theory of galvanomagnetic
phenomena in metals with complex Fermi surfaces. Instead, however, it is
interesting in many different two-dimensional systems, where quasiperiodic
potentials are created using certain experimental techniques. The most common
technique in this case is, apparently, the method of superposition of several
one-dimensional (or, more generally, periodic) potentials (Fig. 1), the
periods of which are incommensurate and differently oriented in the plane
(see, for example, [20, 21, 22]). As is easy to show, the resulting potentials
can also be obtained as the restriction of an $N$-periodic function to the
plane for some embedding $\,\mathbb{R}^{2}\subset\mathbb{R}^{N}\,$ for a
suitable value of $N$. In addition, it can also be noted that quasiperiodic
(quasicrystalline) structures, for example, in systems of ultracold atoms, can
arise also in the absence of special external modulation (see, for example,
[23]). As in the case of three quasiperiods, Novikov’s problem here relates,
as a rule, primarily to transport phenomena in such systems.

Figure 1. Creation of quasiperiodic potentials on the plane by superposition
of one-dimensional periodic potentials (schematically)

Here it should immediately be noted that for functions with a large number of
quasiperiods, even very general questions, such as questions of the presence
of open level lines or closed level lines of arbitrarily large sizes, become
nontrivial. At the same time, it is questions of this type that are primarily
related to transport or, for example, percolation phenomena in the
corresponding systems. Here we will consider some questions of this type from
the most general point of view, using general constructions of the theory of
quasiperiodic functions. We will now move on to such consideration.

Consider an arbitrary affine embedding
$\,\mathbb{R}^{2}\rightarrow\mathbb{R}^{N}\,$. Since for our purposes the
affine transformations of the space $\,\mathbb{R}^{2}\,$ itself will not be of
interest, the essential parameters for us here, in fact, are the two-
dimensional direction $\,\xi\,$, and also the shift parameters of the space
$\,\mathbb{R}^{2}\,$ in directions orthogonal to it in the space
$\,\mathbb{R}^{N}\,$. The first part of these parameters is then the Grassmann
manifold $\,G_{N,2}\,$, while the second one can be considered as the
Euclidean space of dimension $\,N-2\,$. As in [19], it will be convenient here
to consider at once the entire collection of parallel subspaces
$\,\mathbb{R}^{2}\,$ in $\,\mathbb{R}^{N}\,$ for a fixed direction $\,\xi\,$.

We will everywhere assume here that the direction $\,\xi\,$ is not rational
and, moreover, is not contained in any integral hyperplane in
$\,\mathbb{R}^{N}\,$. In addition, we will divide all such directions
$\,\xi\,$ into partially irrational and completely irrational. Namely, we will
call a direction $\,\xi\,$ partially irrational if it contains exactly one (up
to a factor) integer vector from $\,\mathbb{R}^{N}\,$. We will call a
direction $\,\xi\,$ completely irrational if it does not contain integer
vectors from $\,\mathbb{R}^{N}\,$. For simplicity, we will here call non-
special directions $\,\xi\,$ completely irrational directions that do not lie
in any integer hyperplane in $\,\mathbb{R}^{N}\,$.

It is easy to see that the description of the level lines $\,F|_{\Pi}=c\,$ in
all planes $\,\Pi\,$ of direction $\,\xi\,$ is equivalent to the description
of all level lines of the foliation defined on the surface $\,F({\bf z})=c\,$
in $\,\mathbb{R}^{N}\,$ by the direction $\,\xi\,$.

It must be said that families of functions $\,F|_{\Pi}\,$ that arise in
different planes of a given direction $\,\xi\,$ often also correspond to
“related” potentials that arise in physical systems. In particular, in two-
dimensional electronic systems or systems of cold atoms, where such potentials
arise as a result of the superposition of periodic (or even one-dimensional)
potentials, such families represent potentials arising at the same parameters
and orientation of the initial potentials, except for their shifts in the
corresponding plane. Due to the peculiarities of this technique, various
potentials of the described family often arise during the experiment as a
result of a shift in the maxima and minima of the initial potentials with
other parameters fixed. For completely irrational directions $\,\xi\,$, it is
often assumed that the properties of such potentials are not fundamentally
different and there is no need to make much difference between them. In fact,
as it turns out, even the fact of the presence of open level lines at
important “critical” levels in such potentials may depend on the described
shifts of the initial potentials, which corresponds to different pictures in
different planes $\,\Pi\subset\mathbb{R}^{N}\,$ of the same direction. Here we
will discuss, in particular, these questions in the most general formulation.

Here we consider the function $\,F({\bf z})\,$ to be sufficiently smooth
generic $\,N$ \- periodic function taking values in the interval
$\,[F_{\min},F_{\max}]\,$.

In the case $\,N=3\,$ (see, for example, [12] and references therein), the
level line patterns arising in different planes of the same non-special
direction $\,\xi\,$ are qualitatively the same. In particular, if open level
lines appear at some level $\,c\,$ in one of these planes, they also appear in
all other planes of this direction. In the case $\,N\geq 4\,$, however, the
situation at the same level $\,c\,$ may be different in different planes of a
fixed (non-special) direction. Let us present here a number of results
formulated in [19] for the most general case.

1) For any two-dimensional direction $\,\xi\in G_{N,2}\,$ the levels $\,c\,$
corresponding to the presence of unbounded connected components of the set
$\,F|_{\Pi}=c\,$ in at least one plane $\,\Pi\,$ of direction $\,\xi\,$ form a
connected closed interval $\,[c_{1}(\xi),c_{2}(\xi)]\,$,

$F_{\min}\,<\,c_{1}(\xi)\,\leq\,c_{2}(\xi)\,<\,F_{\max}\,\,\,,$

which can contract to a single point $\,c_{0}(\xi)=c_{1}(\xi)=c_{2}(\xi)\,$.

2) For any non-special direction $\,\xi\,$ and any
$\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$ each plane $\,\Pi\,$ of direction $\,\xi\,$
contains either unbounded connected components of the set $\,F|_{\Pi}=c\,$, or
bounded connected components of this set of arbitrarily large size (or both).

3) For any $\,c\notin[c_{1}(\xi),c_{2}(\xi)]\,$ the sizes of all connected
components of the set $\,F|_{\Pi}=c\,$ in all planes $\,\Pi\,$ of direction
$\,\xi\,$ are limited by one constant $\,D(\xi,c)\,$ (which can grow
indefinitely as $\,c\,$ approaches the interval $\,[c_{1}(\xi),c_{2}(\xi)]$).

Note that for $\,N=3\,$ assertion (3) is also true for bounded connected
components of the set $\,F|_{\Pi}=c\,$ for all values of
$\,c\in[F_{\min},F_{\max}]\,$. In the general case, however, this is not the
case.

Here we prove a number of statements that complement the general picture
considered in [19]. Note here that the assertions in [19] applied not only to
non-singular but also to singular level lines $\,F|_{\Pi}=c\,$ (see Fig. 2).
It was assumed in this case that the functions $\,F|_{\Pi}\,$ can only have
singularities of a certain form (multiple saddles, as well as isolated local
maxima and minima). Moreover, the general position conditions in [19] also
assumed that for completely irrational directions $\,\xi\,$ any connected
component of the set $\,F|_{\Pi}=c\,$ contains at most finitely many singular
points of the function $\,F|_{\Pi}\,$. Here we also assume that these generic
conditions hold.

Figure 2. Non-compact and compact singular connected components of the level
$\,F|_{\Pi}=c\,$ (schematically)

For simplicity, we will consider here the picture that arises in the planes
$\,\Pi\,$, in which the levels $\,F|_{\Pi}=c\,$ are non-singular. Here we will
call such planes non-singular planes. It is easy to see that for a generic
function $\,F\,$ and any value of $\,c\,$ the non-singular planes of direction
$\,\xi\,$ form a set of the full measure in any bounded domain in the set of
planes of direction $\,\xi\,$ (that is, in the space $\,\mathbb{R}^{N-2}$).

The level lines are here the connected components of the set $\,F|_{\Pi}=c\,$
in non-singular planes for the value $\,c\,$. All level lines, therefore, will
represent here non-singular curves, which we will divide into open (non-
closed) and closed ones (see Fig. 3).

Figure 3. Open and closed regular level lines $\,F|_{\Pi}=c\,$ (schematically)

When considering dynamics in physical systems, an important role can be played
by both the geometry of potential level lines $\,F|_{\Pi}\,$ and the geometry
of regions of higher or lower energies for a given energy level. We can see
that in reality the geometric properties of these objects are interconnected.
Here we will consider both the level lines of quasiperiodic potentials and the
areas of their higher or lower values, as well as the connection of these
objects with each other.

For each plane $\,\Pi\,$ of direction $\,\xi\,$ and a fixed value $\,c\,$
denote by $\,\Omega^{-}_{c}(\Pi)\,$ the set of points in $\,\Pi\,$, where
$\,F|_{\Pi}<c\,$. Similarly, denote by $\,\Omega^{+}_{c}(\Pi)\,$ the set of
points in $\,\Pi\,$, where $\,F|_{\Pi}>c\,$.

For each plane $\,\Pi\,$ we also introduce the notation $\,\sigma_{\bf
a}[\Pi]\,$ for the parallel shift of $\,\Pi\,$ in the space
$\,\mathbb{R}^{N}\,$ by a vector $\,{\bf a}\in\mathbb{R}^{N}\,$. It is easy to
see that integer shifts of any plane $\,\Pi\,$ of an irrational direction
$\,\xi\,$ form in this case an everywhere dense set among the planes of the
given direction. Similarly, for any set $\,M\subset\mathbb{R}^{N}\,$, we
denote by $\,\sigma_{\bf a}[M]\,$ its parallel shift by the vector $\,{\bf
a}\in\mathbb{R}^{N}\,$.

According to [19] (see detailed proof in arXiv:2306.11257) for any
$\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$ any plane $\,\Pi\,$ of a non-special
direction $\,\xi\,$ contains either unbounded connected components of the set
$\,F|_{\Pi}=c\,$, or bounded connected components of this set of arbitrarily
large sizes. This is true, in particular, for the planes of direction
$\,\xi\,$, that are non-singular for the value $\,c\,$. In this case, in such
plane $\,\Pi\,$ there are always either open lines of the level
$\,F|_{\Pi}=c\,$ or closed lines of this level of arbitrarily large sizes (or
both).

For non-singular planes $\,\Pi\,$ it is not difficult to prove the following
Lemma.

Lemma 2.1

Let $\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$ and $\,\Pi\,$ be a plane of the
direction $\,\xi\,$, non-singular for the value $\,c\,$. Then the presence of
open level lines $\,F|_{\Pi}=c\,$ is equivalent to the existence of unbounded
connected components of both sets $\,\Omega^{-}_{c}(\Pi)\,$ and
$\,\Omega^{+}_{c}(\Pi)\,$.

Proof.

Indeed, in the presence of an open level line $\,F|_{\Pi}=c\,$ we have two
unbounded connected components of the sets $\,\Omega^{-}_{c}(\Pi)\,$ and
$\,\Omega^{+}_{c}(\Pi)\,$ adjacent to it from different sides.

Conversely (see e.g. [12]), let a plane $\,\Pi\,$ have unbounded connected
components $\,M^{-}\,$ and $\,M^{+}\,$ of the sets $\,\Omega^{-}_{c}(\Pi)\,$
and $\,\Omega^{+}_{c}(\Pi)\,$ respectively. Let $\,{\bf x}\in M^{-}\,$ and
$\,{\bf y}\in M^{+}\,$. Then $\,{\bf x}\,$ and $\,{\bf y}\,$ do not lie inside
any of the closed level lines $\,F|_{\Pi}=c\,$. Let us join $\,{\bf x}\,$ and
$\,{\bf y}\,$ by a generic curve $\,\gamma\,$ in the plane $\,\Pi\,$. The
curve $\,\gamma\,$ can only intersect a finite number of closed level lines in
$\,\Pi\,$, while its intersection index with each of these lines is equal to
zero. Since $\,\gamma\,$ must cross the level $\,F|_{\Pi}=c\,$ an odd number
of times, it must intersect an open level line $\,F|_{\Pi}=c\,$.

Lemma 2.1 is proved.

Let us call here a closed level line $\,F|_{\Pi}=c\,$ an “electronic” level
line if the region $\,\Omega^{+}_{c}(\Pi)\,$ adjoins it from the outside.
Similarly, we call a closed level line $\,F|_{\Pi}=c\,$ a “hole” level line if
the region $\,\Omega^{-}_{c}(\Pi)\,$ adjoins it from the outside.

Lemma 2.2

Let $\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$, $\,\Pi\,$ is a plane of the
corresponding non-special direction $\,\xi\,$, non-singular for the value
$\,c\,$, and the size of the electronic level lines $\,F|_{\Pi}=c\,$ in the
plane $\,\Pi\,$ is bounded above by one constant. Then in $\,\Pi\,$ there are
unbounded connected components of the set $\,\Omega^{-}_{c}(\Pi)\,$.

Proof.

Indeed, if $\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$, then $\,\Pi\,$ contains either
open level lines $\,F|_{\Pi}=c\,$ (then everything is proved), or hole level
lines $\,F|_{\Pi}=c\,$ of arbitrarily large sizes. In the latter case,
$\,\Pi\,$ have connected components of the set $\,\Omega^{-}_{c}(\Pi)\,$ of
arbitrarily large sizes (adjacent to large hole level lines). Since the size
of the bounded connected components of the set $\,\Omega^{-}_{c}(\Pi)\,$ is
bounded by one constant, $\,\Pi\,$ must contain an unbounded (connected)
component of the set $\,\Omega^{-}_{c}(\Pi)\,$.

Lemma 2.2 is proved.

Similarly, there is

Lemma 2.2′

Let $\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$, $\,\Pi\,$ is a plane of the
corresponding non-special direction $\,\xi\,$, non-singular for the value
$\,c\,$, and the size of the hole level lines $\,F|_{\Pi}=c\,$ in the plane
$\,\Pi\,$ is bounded above by one constant. Then in $\,\Pi\,$ there are
unbounded connected components of the set $\,\Omega^{+}_{c}(\Pi)\,$.

On the whole, we can conclude that for a plane $\,\Pi\,$ of a non-special
direction $\,\xi\,$, which is non-singular for a value
$\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$ only one of the following four situations is
possible.

(A) The plane $\,\Pi\,$ contains open level lines $\,F|_{\Pi}=c\,$, as well as
unbounded connected components of both sets $\,\Omega^{-}_{c}(\Pi)\,$ and
$\,\Omega^{+}_{c}(\Pi)\,$.

B) In the plane $\,\Pi\,$, only the set $\,\Omega^{+}_{c}(\Pi)\,$ has
unbounded connected components and there are no open level lines
$\,F|_{\Pi}=c\,$. In this case $\,\Pi\,$ must contain arbitrarily large closed
level lines $\,F|_{\Pi}=c\,$ of the electronic type.

(C) In the plane $\,\Pi\,$, only the set $\,\Omega^{-}_{c}(\Pi)\,$ has
unbounded connected components and there are no open level lines
$\,F|_{\Pi}=c\,$. In this case $\,\Pi\,$ must contain arbitrarily large closed
level lines $\,F|_{\Pi}=c\,$ of the hole type.

(D) In the plane $\,\Pi\,$, there are no unbounded connected components of
both sets $\,\Omega^{-}_{c}(\Pi)\,$ and $\,\Omega^{+}_{c}(\Pi)\,$, as well as
open level lines $\,F|_{\Pi}=c\,$. In this case $\,\Pi\,$ must contain
arbitrarily large closed level lines $\,F|_{\Pi}=c\,$ of both electronic and
hole types.

It is also easy to see that in case (D), due to the absence of unbounded
connected components of the sets $\,\Omega^{-}_{c}(\Pi)\,$ and
$\,\Omega^{+}_{c}(\Pi)\,$, each electronic level line $\,F|_{\Pi}=c\,$ must be
contained in some larger hole level line. In turn, each hole level line
$\,F|_{\Pi}=c\,$ must also be contained in some larger electronic level line
$\,F|_{\Pi}=c\,$ (etc.) (Fig. 4).

Figure 4. Situation (D) in the plane $\,\Pi\,$ (schematically)

Theorem 2.1

Let $\,\xi\,$ be a non-special two-dimensional direction in
$\,\mathbb{R}^{N}\,$, $\,\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$, and $\,\Pi\,$ be a
plane of direction $\,\xi\,$, non-singular for the value $\,c\,$. Then in the
plane $\,\Pi\,$:

1) Situation (B) is possible only for $\,c=c_{1}(\xi)\,$.

2) Situation (C) is possible only for $\,c=c_{2}(\xi)\,$.

3) Situation (D) is possible only for
$\,c=c_{0}(\xi)=c_{1}(\xi)=c_{2}(\xi)\,$.

Proof.

Since the function $\,F({\bf z})\,$ can also be considered as a smooth
function on the torus $\,\mathbb{T}^{N}\,$, there is a constant $\,C\,$, such
that $\,|\nabla F({\bf z})|\leq C\,$ for all $\,{\bf z}\in\mathbb{R}^{N}\,$.

Let in some plane $\,\Pi\,$ of direction $\,\xi\,$, non-singular for the value
$\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$, there are no unbounded connected components
of the set $\,\Omega^{-}_{c}(\Pi)\,$. In this case, each connected component
of the set $\,\Omega^{-}_{c}(\Pi)\,$ is bounded by some closed level line
$\,F|_{\Pi}=c\,$ in the plane $\,\Pi\,$. Consider an arbitrary level
$\,c^{\prime}<c\,$ and all parallel shifts $\,\sigma_{\bf a}[\Pi]\,$ of the
plane $\,\Pi\,$ in $\,\mathbb{R}^{N}\,$ by vectors $\,{\bf a}\,$.

It is easy to see that for $\,|{\bf a}|<(c-c^{\prime})/C\,$ the set
$\,\Omega^{-}_{c^{\prime}}(\sigma_{\bf a}[\Pi])\,$ belongs to the set
$\,\sigma_{\bf a}[\Omega^{-}_{c}(\Pi)]\,$, and thus each of its connected
components lies inside some non-singular closed curve in the plane
$\,\sigma_{\bf a}[\Pi]\,$. As a consequence, each connected component of the
boundary of this set, i.e. the set $\,F|_{\sigma_{\bf a}[\Pi]}=c^{\prime}\,$,
is also bounded by some non-singular closed curve that does not intersect
other such curves in the plane $\,\sigma_{\bf a}[\Pi]\,$.

Thus, in all planes $\,\sigma_{\bf a}[\Pi]\,$ for $\,|{\bf
a}|<(c-c^{\prime})/C\,$ there are no unbounded connected components
(nonsingular or singular) of the set $\,F|_{\sigma_{\bf
a}[\Pi]}=c^{\prime}\,$. Since $\,\xi\,$ is a non-special direction in
$\,\mathbb{R}^{N}\,$, any plane of direction $\,\xi\,$ coincides with one of
these planes $\,\sigma_{\bf a}[\Pi]\,$ after a parallel shift by some integer
vector from $\,\mathbb{R}^{N}\,$. We thus obtain that
$\,c^{\prime}\notin[c_{1}(\xi),c_{2}(\xi)]\,$.

Similarly, one can prove that if in some plane $\,\Pi\,$ of a non-special
direction $\,\xi\,$, non-singular for a value
$\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$, there are no unbounded connected components
of the set $\,\Omega^{+}_{c}(\Pi)\,$, then any value $\,c^{\prime}>c\,$ does
not belong to the interval $\,[c_{1}(\xi),c_{2}(\xi)]\,$. All statements of
the theorem follow directly from these statements.

Theorem 2.1 is proved.

One substantial remark can be made here. Namely, quasiperiodic potentials with
a large number of quasiperiods can be considered, among other things, as a
model of random potentials on the plane (possessing, however, some long-range
order). It can be noted here that the use of quasiperiodic potentials for
modeling random potentials plays an important role not only in the
multidimensional, but also in the one-dimensional case (see, for example, [24]
and the references given there). Here we would also like to discuss aspects of
this approach in the case of two dimensions.

As a rule (see, for example, [25, 26]), in the theory of random potentials on
the plane it is assumed that open level lines of such potentials have a rather
complex geometry and arise only at one energy level $\,V({\bf x})=E_{0}\,$.
Based on this, we can see that it is natural to consider a quasiperiodic
potential as an approximation for a random potential if the corresponding
interval $\,[c_{1},c_{2}]\,$ for it contracts to a point
$\,c_{1}=c_{2}=c_{0}\,$.

It can also be noted that in the case of three quasiperiods the situation
$\,c_{2}>c_{1}\,$ also entails the presence of regular topological (and
geometric) properties of open potential level lines (in the case $\,N\geq
4\,$, however, a similar connection has not yet been established), which also
distinguishes such potentials from random ones. On the other hand, in the
situation $\,c_{1}=c_{2}=c_{0}\,$ potentials with three quasiperiods can have
very complex open level lines, which brings them very close to random ones
(see, for example [10, 11, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
40, 41, 42, 43, 44, 45]). Note, however, that situations (B), (C) and (D) in
the case of three quasi-periods are impossible and any potential with three
quasi-periods has at least one open level line.

In the case $\,N\geq 4\,$, a situation is possible when the potential does not
have open level lines at any energy level (situation (D)), and closed level
lines of arbitrarily large sizes arise only at a single level. This property,
however, is unstable with respect to parallel shifts of the plane $\,\Pi\,$ in
the space $\,\mathbb{R}^{N}\,$. From the point of view of the experimental
methods for creating quasiperiodic potentials mentioned above, this means that
the presence or absence of open level lines $\,F|_{\Pi}=c_{0}\,$ can depend on
the positions of the maxima and minima of periodic potentials superimposed on
each other. These properties, in our opinion, are not an obstacle to
considering such potentials as a model of random potentials on the plane.

A similar situation (the absence of open level lines, as well as of unbounded
connected components of the region of higher or lower energies) can be
observed in the case of $\,N\geq 4\,$ also on the boundaries of the interval
$\,[c_{1},c_{2}]\,$ for $\,c_{2}>c_{1}\,$ (situations (B) and (C)). As in the
previous case, this situation is unstable with respect to parallel shifts of
the plane $\,\Pi\,$ in the space $\,\mathbb{R}^{N}\,$ and depends on the
positions of the maxima and minima of periodic potentials in the experimental
techniques we mentioned. It can also be noted that situations of this type are
also of interest from the point of view of the theory of percolation in
quasiperiodic potentials.

Returning to the general consideration, we can note here that the intervals
$\,[c_{1},c_{2}]\,$ (or level $\,c_{0}$) represent transition regimes between
two, in a sense, opposite situations in the planes $\,\Pi\,$. Namely, for
$\,c<c_{1}(\xi)\,$ each plane $\,\Pi\,$ of the direction $\,\xi\,$ can be
considered as a unique unbounded component of the set $\,F|_{\Pi}>c\,$, in
which there are “inclusions” of regions $\,F|_{\Pi}<c\,$, the sizes of which
do not exceed some fixed constant (for a given $\,c$). (Inside such inclusions
there may be smaller inclusions of regions $\,F|_{\Pi}>c\,$, etc.). Similarly,
for $\,c>c_{2}(\xi)\,$, each plane $\,\Pi\,$ of the direction $\,\xi\,$
represents an unbounded connected component of the set $\,F|_{\Pi}<c\,$ with
similar inclusions of regions $\,F|_{\Pi}>c\,$, etc. For certain two-
dimensional systems, in particular, these two situations correspond to
different signs of the Hall conductivity in the presence of a magnetic field
orthogonal to the plane of the system.

The transition between the two situations described above in the case of
quasiperiodic functions can be quite nontrivial and, in particular, may or may
not be accompanied by the arising of open level lines. As we can see, the last
property may be especially important for potentials that are most suitable for
the role of random ones from our point of view
($c_{1}(\xi)=c_{2}(\xi)=c_{0}(\xi)$). A complex geometry of the resulting
level lines can play a very important role both in the semiclassical
consideration of transport phenomena in such systems, and, in fact, also in a
more general situation (see, for example, [46, 47, 48, 49]).

The values $\,c_{1}$, $\,c_{2}$, as well as $\,c_{0}\,$ can be called
“critical” values of the corresponding potentials, since at these values
qualitative changes in the picture of the potential level lines occur. As can
be seen from the results formulated above, it is at these values that the
behavior of the potential level lines can be most interesting.

Theorem 2.1 directly implies

Theorem 2.2

Let $\,\xi\,$ be a non-special direction in $\,\mathbb{R}^{N}\,$ such that
$\,c_{1}(\xi)<c_{2}(\xi)\,$. Then for any $\,c\in(c_{1}(\xi),c_{2}(\xi))\,$
each plane $\,\Pi\,$ of the direction $\,\xi\,$, which is non-singular for the
value $\,c\,$, contains open level lines $\,F|_{\Pi}=c\,$.

Comment.

In fact, it is not difficult to see that all the statements formulated above
are also true for planes containing singular levels $\,F|_{\Pi}=c\,$ for non-
special directions $\,\xi\,$ in $\,\mathbb{R}^{N}\,$. In this case, along with
open level lines, we must consider all non-compact connected level components
$\,F|_{\Pi}=c\,$ in the plane $\,\Pi\,$, and, along with closed ones, compact
connected components. It can be seen that the above statements, as well as
their proofs, do not, in fact, undergo essential changes. We just recall that
we mean here the fulfillment of the general position conditions; in
particular, we assume that each singular connected component $\,F|_{\Pi}=c\,$
for non-special directions $\,\xi\,$ contains at most a finite number of
multiple saddles of the function $\,F|_{\Pi}\,$.

It can also be noted that any completely irrational direction $\,\xi\,$ is
non-special either in $\,\mathbb{R}^{N}\,$, or in a space of lower dimension.
In the latter case, it is natural to consider the corresponding functions
$\,F|_{\Pi}\,$ as functions with a smaller number of quasi-periods.

The statements formulated above refer to the most general case and describe
the situation for completely irrational directions $\,\xi$. As we have already
said, the case $\,N=3\,$ admits a more detailed description of the level lines
of the functions $\,F|_{\Pi}=c\,$. Moreover, a more detailed description also
exists in the case of $\,N\geq 4\,$ for the partially irrational directions
$\,\xi\,$ that we defined at the beginning of the section (see [19]).

##  3\. Multidimensional generalizations of the Novikov problem

A natural generalization of the Novikov problem is the problem of describing
level surfaces of quasiperiodic functions in the space $\,\mathbb{R}^{n}\,$
with $\,N\,$ quasiperiods. Here we naturally call a quasiperiodic function in
$\,\mathbb{R}^{n}\,$ with $\,N\,$ quasiperiods the restriction of an
$N$-periodic function $\,F(z^{1},\dots,z^{N})\,$ onto the space
$\,\mathbb{R}^{n}\,$ for some embedding
$\,\mathbb{R}^{n}\subset\mathbb{R}^{N}\,$ ($n<N$). As before, we assume here
that the function $\,F(z^{1},\dots,z^{N})\,$ is periodic with respect to the
standard integer lattice $\,\mathbb{Z}^{N}\subset\mathbb{R}^{N}\,$. As a
general position condition, we can, for example, require that the subspace
$\,\mathbb{R}^{n}\,$ intersects transversally with any integer subspace
$\,\mathbb{R}^{m}\subset\mathbb{R}^{N}\,$. The essential parameters for us
will be the direction of embedding $\,\mathbb{R}^{n}\subset\mathbb{R}^{N}\,$
(i.e. a point of the Grassmann manifold $\,G_{N,n}$), as well as the
parameters of parallel shifts of $\,\mathbb{R}^{n}\,$ in $\,\mathbb{R}^{N}\,$
in directions orthogonal to it (i.e. a point in the space
$\,\mathbb{R}^{N-n}$).

Certainly, physical applications of the generalized Novikov problem relate
primarily to the case $\,n=3\,$. As in the two-dimensional case, here we can
especially highlight the case $\,N=2n\,$, which is most often encountered in
the quasicrystals. At the same time, the construction of quasiperiodic
modulations and potentials of the most general form in three-dimensional
systems is also an important direction in modern experimental physics (see,
for example, [50]). It can be noted that here, as in the two-dimensional case,
the study of the Novikov problem seems to be the most important in describing
transport phenomena in such systems.

As was noted in [19] (see arXiv:2306.11257), a number of results of this work
can, in fact, be generalized to the case of quasiperiodic functions in a space
of arbitrary dimension. Here we will consider in more detail these
generalizations, as well as similar generalizations of the results presented
in the previous section.

As in the case of $\,n=2\,$, we will be interested here, first of all, in the
arising of unbounded connected components of level surfaces of quasiperiodic
functions, as well as their bounded components of arbitrarily large size. Here
we will call a connected component of a level surface (regular or singular)
unbounded if it cannot be contained in any ball of finite radius in the space
$\,\mathbb{R}^{n}\,$.

Below we will assume that level surfaces of quasiperiodic functions can be
both regular and singular. At the same time, we will assume that the
corresponding functions $\,F|_{\mathbb{R}^{n}}\,$ can only have singularities
of a certain type, namely, multiple saddles or isolated maxima and minima. As
before, we will assume that for generic directions of the embedding
$\,\mathbb{R}^{n}\subset\mathbb{R}^{N}\,$ each connected component of the
function $\,F|_{\mathbb{R}^{n}}\,$ can contain only a finite number of its
singular points.

As in the case of $\,n=2\,$, we will consider here the generalized Novikov
problem for all subspaces $\,\mathbb{R}^{n}\subset\mathbb{R}^{N}\,$ of a fixed
direction $\,\xi\in G_{N,n}\,$. Similar to the case $\,n=2\,$ ([19]), we can
formulate here the following lemma.

Lemma 3.1

Let $\,F(z^{1},\dots,z^{N})\,$ be an $N$-periodic function in
$\,\mathbb{R}^{N}\,$ and let $\,\xi\in G_{N,n}\,$ and $\,c\in\mathbb{R}\,$ be
such that for any $n$-dimensional affine subspace $\,V\,$ of direction
$\,\xi\,$ all level surfaces $\,F|_{V}=c\,$ (singlar or nonsingular) are
compact. Then the diameters of all these level surfaces are bounded from above
by one constant common to all the subspaces of direction $\,\xi\,$.

Proof.

Like in the case $\,n=2\,$, we can claim that each compact level surface
$\,F|_{V}=c\,$ (both singular and non-singular) has a neighborhood of finite
diameter such that all other level surfaces $\,F|_{V}=c\,$ in parallel
subspaces that intersect this neighborhood lie entirely in it. Since the
hypersurface $\,F(z^{1},\dots,z^{N})=c\,$ is compact in the torus
$\,\mathbb{T}^{N}\,$, we can choose a finite family of such neighborhoods so
that their images cover this hypersurface in $\,\mathbb{T}^{N}\,$.

Lemma 3.1 is proved.

Lemma 3.2

Let $\,F(z^{1},\dots,z^{N})\,$ be an $N$-periodic function, and let $\,\xi\in
G_{N,n}\,$ be a fixed $n$-dimensional direction in $\,\mathbb{R}^{N}\,$. Then
the set of values $\,c\in\mathbb{R}\,$ such that for at least one subspace
$\,V\,$ of direction $\,\xi\,$ the level surface $F|_{V}=c\,$ has unbounded
connected components forms a closed interval $\,[c_{1},c_{2}]\,$ or consists
of a single point $\,c_{0}\,$.

The proof of Lemma 3.2 follows the pattern of the proof of Theorem 1 in [12],
which only needs to be slightly modified using Lemma 3.1 and applied to the
multidimensional case.

By analogy with the case $\,n=2\,$, let us also formulate here the following
lemma.

Lemma 3.3

For any generic direction $\,\xi\in G_{N,n}\,$ and any
$\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$ each affine subspace $\,V\,$ of direction
$\,\xi\,$ contains either unbounded connected components (singular or non-
singular) of the set $\,F|_{V}=c\,$, or bounded non-singular connected
components of this set of arbitrarily large size (or both).

Proof.

The proof of Lemma 3.3 is similar to the proof of the analogous statement for
the case $\,n=2\,$ ([19], arXiv:2306.11257). Let us have an affine subspace
$\,V\,$ of direction $\,\xi\,$ where the cize of all non-singular connected
components of the surface $\,F|_{V}=c\,$ is limited by one constant. (By the
size of a component we mean the minimum diameter $\,D\,$ of the sphere
$\,S^{n-1}\,$ in which it can be placed.

Let us take a subspace $\,V^{\prime}\,$ of direction $\,\xi\,$, containing an
unbounded component (singular or non-singular) of the surface
$\,F|_{V^{\prime}}=c\,$. According to our general assumptions, we can take a
connected part of this component such that it does not contain singular points
and cannot be enclosed in a sphere of diameter $D$. There is a small $\delta$
such that this part is preserved for all parallel shifts of $\,V^{\prime}\,$
in all transversal directions by a distance less than $\delta$.

Consider the corresponding $\delta$-neighborhood $O$ of $\,V^{\prime}\,$.
Integer shifts of the original subspace $\,V\,$ are everywhere dense in
$\,\mathbb{R}^{N}\,$ for our $\,\xi\,$ and must fall in the neighborhood $O$.
We get a contradiction.

Lemma 3.3 is proved.

We will now present analogues of the statements made in the previous section
for the multidimensional generalization of the Novikov problem. We will not
now assume that the subspaces $\,V\,$ are non-singular, since the proofs of
our assertions do not change significantly for subspaces containing singular
points of the functions $\,F|_{V}\,$ under our general assumptions.

As in the case $\,n=2\,$, for each affine subspace $\,V\,$ and a fixed value
$\,c\,$ denote by $\,\Omega^{-}_{c}(V)\,$ the set of points in $\,V\,$, where
$\,F|_{V}<c\,$. Similarly, denote by $\,\Omega^{+}_{c}(V)\,$ the set of points
in $\,V\,$, where $\,F|_{V}>c\,$. Under our general assumptions, we can again
formulate here the following simple lemma.

Lemma 3.4

Let $\,\xi\,$ be a generic $n$-dimensional direction in $\,\mathbb{R}^{N}\,$
and $\,V\,$ be an affine subspace of direction $\,\xi\,$. Then the presence of
unbounded connected components of the level surface $\,F|_{V}=c\,$ (singular
or non-singular) is equivalent to the existence of unbounded connected
components of both sets $\,\Omega^{-}_{c}(V)\,$ and $\,\Omega^{+}_{c}(V)\,$ in
$\,V\,$.

By analogy with the two-dimensional case let us call here a non-singular
bounded component of the surface $\,F|_{V}=c\,$ an “electronic” component if
the region $\,\Omega^{+}_{c}(V)\,$ adjoins it from the outside. Similarly, we
call a non-singular bounded component of the surface $\,F|_{V}=c\,$ a “hole”
component if the region $\,\Omega^{-}_{c}(V)\,$ adjoins it from the outside.

Similar to the two-dimensional case, we can formulate the following lemmas
here.

Lemma 3.5

Let $\,\xi\,$ be a generic $n$-dimensional direction in $\,\mathbb{R}^{N}\,$
and $\,V\,$ be an affine subspace of direction $\,\xi\,$. Let
$\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$ and the size of the electronic components of
$\,F|_{V}=c\,$ in $\,V\,$ is bounded above by one constant. Then in $\,V\,$
there are unbounded connected components of the set $\,\Omega^{-}_{c}(V)\,$.

Lemma 3.5′

Let $\,\xi\,$ be a generic $n$-dimensional direction in $\,\mathbb{R}^{N}\,$
and $\,V\,$ be an affine subspace of direction $\,\xi\,$. Let
$\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$ and the size of the hole components of
$\,F|_{V}=c\,$ in $\,V\,$ is bounded above by one constant. Then in $\,V\,$
there are unbounded connected components of the set $\,\Omega^{+}_{c}(V)\,$.

The proof of Lemmas 3.5 and 3.5′ is completely similar to the case $\,n=2\,$
taking into account Lemma 3.3. Using the lemmas formulated above, we can state
here that in a subspace $\,V\,$ of a generic direction $\,\xi\,$ and
$\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$, under our general assumptions, only one of
the following four situations is possible.

(A′) The subspace $\,V\,$ contains unbounded connected components of the
surface $\,F|_{V}=c\,$ (singular or non-singular), as well as unbounded
connected components of both sets $\,\Omega^{-}_{c}(V)\,$ and
$\,\Omega^{+}_{c}(V)\,$.

(B′) In the subspace $\,V\,$, only the set $\,\Omega^{+}_{c}(V)\,$ has
unbounded connected components and there are no unbounded connected components
of the surface $\,F|_{V}=c\,$. In this case $\,V\,$ must contain arbitrarily
large non-singular bounded connected components of $\,F|_{V}=c\,$ of the
electronic type.

(C′) In the subspace $\,V\,$, only the set $\,\Omega^{-}_{c}(V)\,$ has
unbounded connected components and there are no unbounded connected components
of the surface $\,F|_{V}=c\,$. In this case $\,V\,$ must contain arbitrarily
large non-singular bounded connected components of $\,F|_{V}=c\,$ of the hole
type.

(D′) The subspace $\,V\,$ contains neither unbounded connected components of
the set $\,\Omega^{-}_{c}(V)\,$, nor unbounded connected components of the set
$\,\Omega^{+}_{c}(V)\,$, nor unbounded connected components of the level
surface $\,F|_{V}=c\,$. In this case $\,V\,$ must contain arbitrarily large
non-singular bounded connected components of $\,F|_{V}=c\,$ of both electronic
and hole types.

It is also easy to see that in case (D′), due to the absence of unbounded
connected components of the sets $\,\Omega^{-}_{c}(V)\,$ and
$\,\Omega^{+}_{c}(V)\,$, each electronic component $\,F|_{V}=c\,$ must be
contained in some larger hole component. In turn, each hole component
$\,F|_{V}=c\,$ must also be contained in some larger electronic component
$\,F|_{V}=c\,$.

Finally, as in the case $\,n=2\,$, we can formulate here the following
theorems.

Theorem 3.1

Let $\,\xi\,$ be a generic $n$-dimensional direction in $\,\mathbb{R}^{N}\,$,
$\,\,c\in[c_{1}(\xi),c_{2}(\xi)]\,$, and $\,V\,$ be a subspace of direction
$\,\xi\,$. Then in the subspace $\,V\,$:

1) Situation (B′) is possible only for $\,c=c_{1}(\xi)\,$.

2) Situation (C′) is possible only for $\,c=c_{2}(\xi)\,$.

3) Situation (D′) is possible only for
$\,c=c_{0}(\xi)=c_{1}(\xi)=c_{2}(\xi)\,$.

Theorem 3.2

Let $\,\xi\in G_{N,n}\,$ be a generic direction in $\,\mathbb{R}^{N}\,$ such
that $\,c_{1}(\xi)<c_{2}(\xi)\,$. Then for any
$\,c\in(c_{1}(\xi),c_{2}(\xi))\,$ each subspace $\,V\,$ of direction $\,\xi\,$
contains unbounded connected components (singular or non-singular) of the
suraface $\,F|_{V}=c\,$.

The proof of Theorems 3.1 and 3.2 is carried out similarly to the case
$\,n=2\,$, taking into account the above lemmas.

##  4\. Conclusion

The paper considers questions related to the general Novikov problem, i.e. the
description of the level lines of quasi-periodic functions on the plane with
an arbitrary number of quasi-periods. More precisely, the cases of arising of
open level lines of such functions, as well as their closed level lines,
having arbitrarily large sizes, are investigated. The arising of such level
lines is closely related to certain values of the function under
consideration, lying within the full range of its values. The latter
circumstance actually plays an important role in the study of dynamical
systems related to the Novikov problem, where the considered function $\,F\,$
often plays the role of the Hamiltonian function. In fact, the presented
results can also be formulated for the generalized Novikov problem, namely,
the problem of describing level surfaces of quasiperiodic functions in
$n$-dimensional spaces. As a rule, the geometric features of such level
surfaces appear primarily in describing transport phenomena in systems with
quasi-periodic modulations.

## References

  * [1] S.P. Novikov, The Hamiltonian formalism and a many-valued analogue of Morse theory., // Russian Math. Surveys 37 (5), 1-56 (1982).
  * [2] I.M. Lifshitz, M.Ya. Azbel, M.I. Kaganov., The Theory of Galvanomagnetic Effects in Metals., // Sov. Phys. JETP 4:1, 41-53 (1957).
  * [3] I.M. Lifshitz, V.G. Peschansky., Galvanomagnetic characteristics of metals with open Fermi surfaces., // Sov. Phys. JETP 8:5, 875-883 (1959).
  * [4] I.M. Lifshitz, V.G. Peschansky., Galvanomagnetic characteristics of metals with open Fermi surfaces. II., // Sov. Phys. JETP 11:1, 131-141 (1960).
  * [5] I.M. Lifshitz, M.Ya. Azbel, M.I. Kaganov., Electron Theory of Metals. New York: Consultants Bureau, 1973.
  * [6] A.V. Zorich., A problem of Novikov on the semiclassical motion of an electron in a uniform almost rational magnetic field., // Russian Math. Surveys 39 (5), 287-288 (1984).
  * [7] I.A. Dynnikov., Proof of S.P. Novikov’s conjecture for the case of small perturbations of rational magnetic fields., // Russian Math. Surveys 47:3, 172-173 (1992).
  * [8] S.P. Tsarev, private communication, 1992-1993
  * [9] I.A. Dynnikov., Proof of S.P. Novikov’s conjecture on the semiclassical motion of an electron., // Math. Notes 53:5, 495-501 (1993).
  * [10] I.A. Dynnikov., Surfaces in 3-torus: geometry of plane sections., // Proc. of ECM2, BuDA, 1996.
  * [11] I.A. Dynnikov., Semiclassical motion of the electron. A proof of the Novikov conjecture in general position and counterexamples., Solitons, geometry, and topology: on the crossroad, Amer. Math. Soc. Transl. Ser. 2, 179, Amer. Math. Soc., Providence, RI, 1997, 45-73.
  * [12] I.A. Dynnikov., The geometry of stability regions in Novikov’s problem on the semiclassical motion of an electron., // Russian Math. Surveys 54:1, 21-59 (1999).
  * [13] S.P. Novikov, A.Y. Maltsev., Topological quantum characteristics observed in the investigation of the conductivity in normal metals., // JETP Letters 63 (10), 855-860 (1996).
  * [14] S.P. Novikov, A.Y. Maltsev., Topological phenomena in normal metals., // Physics-Uspekhi 41:3, 231-239 (1998).
  * [15] A.Ya. Maltsev, S.P. Novikov., Quasiperiodic functions and Dynamical Systems in Quantum Solid State Physics., // Bulletin of Braz. Math. Society, New Series 34:1 (2003), 171-210.
  * [16] A.Ya. Maltsev, S.P. Novikov., Dynamical Systems, Topology and Conductivity in Normal Metals in strong magnetic fields., // Journal of Statistical Physics 115:(1-2) (2004), 31-46.
  * [17] S.P. Novikov, Levels of quasiperiodic functions on a plane, and Hamiltonian systems, // Russian Math. Surveys, 54 (5) (1999), 1031-1032
  * [18] I.A. Dynnikov, S.P. Novikov, Topology of quasi-periodic functions on the plane, // Russian Math. Surveys, 60 (1) (2005), 1-26
  * [19] I.A. Dynnikov, A.Ya. Maltsev, S.P. Novikov, Geometry of quasi-periodic functions on the plane, // Russian Math. Surveys, Volume 77, Issue 6, 1061–1085 (2022), arXiv:2306.11257
  * [20] L. Guidoni, B. Depret, A. di Stefano, and P. Verkerk, Atomic diffusion in an optical quasicrystal with five-fold symmetry, // Phys. Rev. A 60, R4233 (1999).
  * [21] L. Sanchez-Palencia and L. Santos, Bose-Einstein Condensates in Optical Quasicrystal Lattices, // Phys. Rev. A 72, 053607 (2005).
  * [22] L. Guidoni and P. Verkerk, Optical lattices: cold atoms ordered by light, // Journal of Optics B: Quantum and Semiclassical Optics, 1, R23 (1999).
  * [23] Sarang Gopalakrishnan, Ivar Martin, and Eugene A. Demler, Quantum quasicrystals of spin-orbit coupled dipolar bosons, // Phys. Rev. Lett. 111, 185304 (2013).
  * [24] Yunfei Wang, Jia-Hui Zhang, Yuqing Li, Jizhou Wu, Wenliang Liu, Feng Mei, Ying Hu, Liantuan Xiao, Jie Ma, Cheng Chin, and Suotang Jia, Observation of Interaction-Induced Mobility Edge in an Atomic Aubry-Andre Wire, // Phys. Rev. Lett. 129, 103401 (2022).
  * [25] D. Stauffer, Scaling theory of percolation clusters, // Physics Reports 54, 1-74 (1979).
  * [26] J.W. Essam, Percolation theory, // Rep. Prog. Phys. 43, 833 (1980).
  * [27] A.V. Zorich., Asymptotic Flag of an Orientable Measured Foliation on a Surface., Proc. “Geometric Study of Foliations”., (Tokyo, November 1993), ed. T.Mizutani et al. Singapore: World Scientific Pb. Co., 479-498 (1994).
  * [28] A.V. Zorich., Finite Gauss measure on the space of interval exchange transformations. Lyapunov exponents., // Annales de l’Institut Fourier 46:2, (1996), 325-370.
  * [29] Anton Zorich., On hyperplane sections of periodic surfaces., Solitons, Geometry, and Topology: On the Crossroad, V. M. Buchstaber and S. P. Novikov (eds.), Translations of the AMS, Ser. 2, vol. 179, AMS, Providence, RI (1997), 173-189.
  * [30] Anton Zorich., How do the leaves of closed 1-form wind around a surface., “Pseudoperiodic Topology”, V.I.Arnold, M.Kontsevich, A.Zorich (eds.), Translations of the AMS, Ser. 2, vol. 197, AMS, Providence, RI, 1999, 135-178.
  * [31] R. De Leo., Existence and measure of ergodic leaves in Novikov’s problem on the semiclassical motion of an electron., // Russian Math. Surveys 55:1 (2000), 166-168.
  * [32] R. De Leo., Characterization of the set of “ergodic directions” in Novikov’s problem of quasi-electron orbits in normal metals., // Russian Math. Surveys 58:5 (2003), 1042-1043.
  * [33] R. De Leo., Topology of plane sections of periodic polyhedra with an application to the Truncated Octahedron., // Experimental Mathematics 15:1 (2006), 109-124.
  * [34] Anton Zorich., Flat surfaces., in collect. “Frontiers in Number Theory, Physics and Geometry. Vol. 1: On random matrices, zeta functions and dynamical systems”; Ecole de physique des Houches, France, March 9-21 2003, P. Cartier; B. Julia; P. Moussa; P. Vanhove (Editors), Springer-Verlag, Berlin, 2006, 439-586.
  * [35] R. De Leo, I.A. Dynnikov., An example of a fractal set of plane directions having chaotic intersections with a fixed 3-periodic surface., // Russian Math. Surveys 62:5 (2007), 990-992.
  * [36] I.A. Dynnikov., Interval identification systems and plane sections of 3-periodic surfaces., // Proceedings of the Steklov Institute of Mathematics 263:1 (2008), 65-77.
  * [37] R. De Leo, I.A. Dynnikov., Geometry of plane sections of the infinite regular skew polyhedron $\\{4,\,6\,|\,4\\}$., // Geom. Dedicata 138:1 (2009), 51-67.
  * [38] A. Skripchenko., Symmetric interval identification systems of order three., // Discrete Contin. Dyn. Sys. 32:2 (2012), 643-656.
  * [39] A. Skripchenko., On connectedness of chaotic sections of some 3-periodic surfaces., // Ann. Glob. Anal. Geom. 43 (2013), 253-271.
  * [40] I. Dynnikov, A. Skripchenko., On typical leaves of a measured foliated 2-complex of thin type., Topology, Geometry, Integrable Systems, and Mathematical Physics: Novikov’s Seminar 2012-2014, Advances in the Mathematical Sciences., Amer. Math. Soc. Transl. Ser. 2, 234, eds. V.M. Buchstaber, B.A. Dubrovin, I.M. Krichever, Amer. Math. Soc., Providence, RI, 2014, 173-200, arXiv: 1309.4884
  * [41] I. Dynnikov, A. Skripchenko., Symmetric band complexes of thin type and chaotic sections which are not actually chaotic., // Trans. Moscow Math. Soc., Vol. 76, no. 2, 2015, 287-308.
  * [42] A. Avila, P. Hubert, A. Skripchenko., Diffusion for chaotic plane sections of 3-periodic surfaces., // Inventiones mathematicae, October 2016, Volume 206, Issue 1, pp 109–146.
  * [43] A. Avila, P. Hubert, A. Skripchenko., On the Hausdorff dimension of the Rauzy gasket., // Bulletin de la societe mathematique de France, 2016, 144 (3), pp. 539 - 568.
  * [44] A.Ya. Maltsev, S.P. Novikov., The Theory of Closed 1-Forms, Levels of Quasiperiodic Functions and Transport Phenomena in Electron Systems., // Proceedings of the Steklov Institute of Mathematics 302, 279-297 (2018).
  * [45] Ivan Dynnikov, Pascal Hubert, Alexandra Skripchenko, Dynamical Systems Around the Rauzy Gasket and Their Ergodic Properties, // International Mathematics Research Notices IMRN 2022, 1-30 (Published online), arXiv 2011.15043
  * [46] A.Ya. Maltsev, Quasiperiodic functions theory and the superlattice potentials for a two-dimensional electron gas, // Journal of Mathematical Physics 45:3, 1128 (2004).
  * [47] M. Titov and M.I. Katsnelson, Metal-Insulator Transition in Graphene on Boron Nitride, // Phys. Rev. Lett. 113, 096801 (2014).
  * [48] I.A. Dynnikov, A.Ya. Maltsev, Features of the motion of ultracold atoms in quasiperiodic potentials, // JETP 133 (6), 711-736 (2021)
  * [49] A.Ya. Maltsev, S.P. Novikov, Open level lines of a superposition of periodic potentials on a plane, // Annals of Physics 447 (Pt.2), 169039 (2022).
  * [50] L. Guidoni, C. Triche, P. Verkerk, and G. Grynberg, Quasiperiodic Optical Lattices, // Phys. Rev. Lett. 79, 3363 (1997).