Quasiperiodic Patterns of the Complex Dimensions of Nonlattice Self-Similar Strings, via the LLL Algorithm

Abstract

The Lattice String Approximation algorithm (or LSA algorithm) of M. L. Lapidus and M. van Frankenhuijsen is a procedure that approximates the complex dimensions of a nonlattice self-similar fractal string by the complex dimensions of a lattice self-similar fractal string. The implication of this procedure is that the set of complex dimensions of a nonlattice string has a quasiperiodic pattern. Using the LSA algorithm, together with the multiprecision polynomial solver MPSolve which is due to D. A. Bini, G. Fiorentino and L. Robol, we give a new and significantly more powerful presentation of the quasiperiodic patterns of the sets of complex dimensions of nonlattice self-similar fractal strings. The implementation of this algorithm requires a practical method for generating simultaneous Diophantine approximations, which in some cases we can accomplish by the continued fraction process. Otherwise, as was suggested by Lapidus and van Frankenhuijsen, we use the LLL algorithm of A. K. Lenstra, H. W. Lenstra, and L. Lovász.

1. Introduction

From 1991 to 1993, Lapidus (in the more general and higher-dimensional case of fractal drums), as well as Lapidus and Pomerance established connections between complex dimensions and the theory of the Riemann zeta function by studying the connection between fractal strings and their spectra; see [1,2,3]. Then, in [4], Lapidus and Maier used the intuition coming from the notion of complex dimensions in order to rigorously reformulate the Riemann hypothesis as an inverse spectral problem for fractal strings. The notion of complex dimensions was precisely defined and the corresponding rigorous theory of complex dimensions was fully developed by Lapidus and van Frankenhuijsen, for example in [5,6,7,8], in the one-dimensional case of fractal strings. Recently, the higher-dimensional theory of complex dimensions was fully developed by Lapidus, Radunović and Žubrinić in the book [9] and a series of accompanying papers; see also the first author’s recent survey article [10].

The present paper focuses, in particular, on self-similar strings (and their natural generalizations), the boundary of which is a self-similar set (in $\mathbb{R}$), satisfying a mild non-overlapping condition, as introduced and studied in [5,6,7,8].

Given a closed, bounded and nonempty interval I of length L, and $M\ge 2$ contraction similitudes of $\mathbb{R}$,

$${\Phi }_1,\dots ,{\Phi }_M:I\to I,$$

a self-similar fractal string (or self-similar string, in short) is constructed through a procedure reminiscent of the construction of the Cantor set. In the first step, one subdivides the interval I into the images

$${\Phi }_1\left(I\right),\dots ,{\Phi }_M\left(I\right).$$

(1)

If one imposes a mild separation condition on the contraction similitudes, the images (1) now lie in the interval I, and they do not overlap, except possibly at the endpoints. Moreover, the complement in I of their union consists of one or more disjoint open intervals, called the first lengths. This process is then repeated with each of the images in (1), resulting in another finite collection of disjoint open intervals. The final result will be a countably infinite collection of pairwise disjoint and bounded open intervals, all contained in the original interval I. The union of these open intervals is the self-similar fractal string.

From the perspective of the current paper, there is an important dichotomy in the set of all self-similar fractal strings, according to which any self-similar fractal string is either lattice or nonlattice, depending on the scaling ratios with which a self-similar fractal string is constructed. (Note the two meanings of ‘lattice’. On the one hand, a lattice string is a certain kind of fractal string studied in fractal geometry. On the other hand, the LLL algorithm is a generalization of Euclid’s algorithm aimed at finding a reduced basis of a lattice as a discrete subgroup of ${\mathbb{R}}^N$ of rank N; see Section 3.1.) More specifically, the lattice (resp., nonlattice) case is when all (resp., two or more) of the logarithms of the N distinct scaling ratios are rationally dependent (resp., independent), with necessarily $1\le N\le M$. In other words, the multiplicative group $G\subseteq (0,+\infty )$ generated by the N distinct scaling ratios is of rank 1 in the lattice case (that is, $G=r^{\mathbb{Z}}$, for some $r\in (0,1)$, called the multiplicative generator) and is of rank $\ge 2$, in the nonlattice case. By definition, the generic nonlattice case is when $N\ge 2$ and the rank of G is equal to N.

In the lattice case, the complex dimensions (see Section 2 for a reminder of the definition of the complex dimensions as the poles of the ‘geometric zeta function’ associated with a fractal string.) can be numerically obtained via the roots of certain polynomials that are typically sparse with large degrees, and lie periodically on finitely many vertical lines counted according to multiplicity. Furthermore, on each vertical line, they are separated by a positive real number $\mathbf{p}$, called the oscillatory period of the string. (See [5] (Chapter 2), ref. [6] (Theorem 2.5), and [8] (Theorems 2.16 and 3.6)).

For nonlattice self-similar fractal strings, which are the main focus of the present paper, the complex dimensions cannot be numerically obtained in the same way as in the lattice case. Indeed, they correspond to the roots of a transcendental (rather than polynomial) equation. They can, however, be approximated by the complex dimensions of a sequence of lattice strings with larger and larger oscillatory periods. The Lattice String Approximation algorithm of Lapidus and van Frankenhuijsen, referred to in this paper as the LSA algorithm, allows one to replace the study of nonlattice self-similar fractal strings by the study of suitable approximating sequences of lattice self-similar fractal strings. Using this algorithm, M. L. Lapidus and M. van Frankenhuijsen have shown that the sets of complex dimensions of nonlattice self-similar fractal strings are quasiperiodically distributed, in a precise sense (see, e.g., [6] (Theorem 3.6, Remark 3.7) and [7,8] (Section 3.4.2)), and they have illustrated their results by means of a number of examples (see, e.g., the examples from Section 7 in [6] and their counterparts in Chapters 2 and 3 of [8]). Following the suggestion by those same authors in the introduction of [6], and in [7,8] (Remark 3.38), the current paper presents an implementation of the LSA algorithm incorporating the application of a powerful lattice basis reduction algorithm, which is due to A. K. Lenstra, H. W. Lenstra and L. Lovász and is known as the LLL algorithm, in order to generate simultaneous Diophantine approximations; see [11] (Proposition 1.39) and [12] (Proposition 9.4). It also uses the open source software MPSolve, due to D. A. Bini, G. Fiorentino and L. Robol in [13,14], in order to approximate the roots of large degree sparse polynomials. Indeed, the LLL algorithm along with MPSolve allow for a deeper numerical and visual exploration of the quasiperiodic patterns of the complex dimensions of self-similar strings via the LSA algorithm than what has already been done in [5,6,7,8].

In the latter part of [8] (Chapter 3), a number of mathematical results were obtained concerning either the nonlattice case with two distinct scaling ratios (amenable to the use of continued fractions) as well as the nonlattice case with three or more distinct scaling ratios (therefore, typically requiring more complicated simultaneous Diophantine approximation algorithms). In the present paper, it has become possible, in particular, to explore more deeply and accurately additional nonlattice strings with rank greater than or equal to three, i.e., those that cannot be solved using continued fractions.

The rest of this paper is organized as follows. Section 2 consists of some background on complex dimensions and self-similar fractal strings, leading up to the restatement of [8] (Theorem 3.18) (see also [6] (Theorem 3.6)), which provides the LSA algorithm. Then, in Section 3, a brief overview of lattice basis reduction is given, along with a restatement and proof of [12] (Proposition 9.4) to illustrate how the LLL algorithm is applied to simultaneous Diophantine approximations. In the latter part of Section 3 (see Section 3.2.1), we describe our implementation of the LLL algorithm for simultaneous Diophantine approximations which uses continued fractions. In Section 4, using our implementation of the LLL algorithm, together with MPSolve, a number of examples aimed at illustrating the quasiperiodic patterns of the complex dimensions of nonlattice self-similar fractal strings, and in the more general setting, of the roots (i.e., the zeros) of nonlattice Dirichlet polynomials, are shown and commented upon. These include examples previously studied in [5,6,7,8], which can now be viewed in a new light by using our refined numerical approach, and new handpicked examples which are computationally easier to explore and for which interesting new phenomena arise. The mathematical experiments performed in the current paper, along with earlier work in [6,7,8,15], have led to new questions and open problems which are briefly discussed in the concluding comments section, namely, Section 5.

2. Preliminary Materials

An (ordinary) fractal string $\mathcal{L}$ consists of a bounded open subset $\Omega \subset \mathbb{R}$; such a set $\Omega$ is a disjoint union of countably many disjoint open intervals. The lengths

$${\ell }_1,{\ell }_2,{\ell }_3,\dots$$

of the open intervals are called the lengths of $\mathcal{L}$, and since $\Omega$ is a bounded set, it is assumed without loss of generality that

$${\ell }_1\ge {\ell }_2\ge \cdots >0,$$

and that ${\ell }_j\to 0$ as $j\to \infty$ (We ignore here the trivial case when $\Omega$ is a finite union of open intervals).

Let ${\sigma }_{\mathcal{L}}$ denote the abscissa of convergence (Note that $\left|{\ell }_j^s\right|={\ell }_j^{\Re \left(s\right)}$, for every $s\in \mathbb{C}$ and all $j\in \mathbb{N}$).

$$\begin{array}{cc}\hfill {\sigma }_{\mathcal{L}}& =inf\left\{\sigma \in \mathbb{R}:\sum _{j=1}^{\infty }\left|{\ell }_j^s\right|<\infty ,\mathrm{for}\mathrm{every}s\in \mathbb{C}\mathrm{with}\Re \left(s\right)>\sigma \right\}\hfill \\ \hfill & =inf\left\{\alpha \in \mathbb{R}:\sum _{j=1}^{\infty }{\ell }_j^{\alpha }<\infty \right\},\hfill \end{array}$$

of the geometric zeta function

$${\zeta }_{\mathcal{L}}\left(s\right)=\sum _{j=1}^{\infty }{\ell }_j^s$$

of $\mathcal{L}$. Since there are infinitely many lengths, ${\zeta }_{\mathcal{L}}\left(s\right)$ diverges at $s=0$. Furthermore, since $\Omega$ has finite Lebesgue measure, ${\zeta }_{\mathcal{L}}\left(s\right)$ converges at $s=1$. Hence, it follows from standard results about general Dirichlet series (see, e.g., [16]) that the second equality in the above definition of ${\sigma }_{\mathcal{L}}$ holds, and, therefore, that $0\le {\sigma }_{\mathcal{L}}\le 1$.

Definition 1.

The dimension of a fractal string $\mathcal{L}$ with associated bounded open set Ω, denoted by $D_{\mathcal{L}}$, is defined as the (inner) Minkowski dimension of Ω:

$$D_{\mathcal{L}}=inf\{\alpha \ge 0:V\left(\epsilon \right)=O\left({\epsilon }^{1-\alpha }\right),\mathrm{as}\epsilon \to 0^{+}\},$$

where $V\left(\epsilon \right)$ denotes the volume (i.e., total length) of the inner tubular neighborhood of $\partial \Omega$ with radius ε given by

$$V\left(\epsilon \right)={vol}_1\left(\{x\in \Omega :d(x,\partial \Omega )<\epsilon \}\right).$$

According to [8] (Theorem 1.10) (see also [2]), the abscissa of convergence ${\sigma }_{\mathcal{L}}$ of a fractal string $\mathcal{L}$ coincides with the dimension $D_{\mathcal{L}}$ of $\mathcal{L}$: ${\sigma }_{\mathcal{L}}=D_{\mathcal{L}}$.

Definition 2.

Suppose ${\zeta }_{\mathcal{L}}\left(s\right)$ has a meromorphic continuation to the entire complex plane. Then the poles of ${\zeta }_{\mathcal{L}}\left(s\right)$ are called the complex dimensions of $\mathcal{L}$.

Remark 1.

While the theory of complex dimensions is developed in [5,6,7,8,9] for geometric zeta functions not necessarily having a meromorphic continuation to all of $\mathbb{C}$, the present paper only requires the simpler case considered in Definition 2 (which is the case, in particular, of all self-similar fractal strings). See also [10] for a recent survey of the theory of complex fractal dimensions.

The geometric importance of the set of complex dimensions of a fractal string $\mathcal{L}$ with boundary $\Omega$, which always includes its inner Minkowski dimension $D_{\mathcal{L}}$, is justified because, for example, the complex dimensions appear in an essential way in the explicit formula for the volume $V\left(\epsilon \right)$ of the inner tubular neighborhood of the boundary $\partial \Omega$; see the corresponding “fractal tube formulas” obtained in Chapter 8 of [8]. Accordingly, the complex dimensions give very detailed information about the intrinsic oscillations that are inherent to fractal geometries; see also Remark 2 below. The current paper, however, deals with the complex dimensions viewed only as a discrete subset of the complex plane, and the focus is on the special type of fractal strings that are constructed through an iterative process involving scaling, as is discussed in Section 2.1.

Remark 2.

In [5,6,7,8] (when $\nu =1$) and in [9,10] (when the integer $\nu \ge 1$ is arbitrary), a geometric object is said to be fractal if it has at least one nonreal complex dimension (It then has at least two nonreal complex dimensions since, clearly, nonreal complex dimensions come in complex conjugate pairs). This definition applies to fractal strings (including all self-similar strings, which are shown to be fractal in this sense) (In fact, self-similar strings have infinitely many nonreal complex dimensions; see, e.g., Equation (2.37) in [8] (Theorem 2.16).), that correspond to the $\nu =1$ case, and to bounded subsets of ${\mathbb{R}}^{\nu }$ (for any integer $\nu \ge 1$) as well as, more generally, to relative fractal drums, which are natural higher-dimensional counterparts of fractal strings.

2.1. Self-Similar Fractal Strings

Let I be a connected interval with length L. Let

$${\Phi }_1,{\Phi }_2,\dots ,{\Phi }_M:I\to I$$

(2)

be $M\ge 2$ contraction similitudes with distinct scaling ratios

$$1>r_1>r_2>\cdots >r_N>0.$$

What this means is that for all $j=1,\dots ,M$,

$$\left|{\Phi }_j\left(x\right)-{\Phi }_j\left(y\right)\right|=r_j|x-y|,\mathrm{for}\mathrm{all}x,y\in I.$$

Assume that after having applied to I each of the maps ${\Phi }_j$ in (2), for $j=1,\dots ,M$, the resulting images

$${\Phi }_1\left(I\right),\dots ,{\Phi }_M\left(I\right)$$

(3)

do not overlap, except possibly at the endpoints, and that ${\sum }_{j=1}^M{r}_j<1$.

These assumptions imply that the complement of the union, ${\bigcup }_{j=1}^M{\Phi }_j\left(I\right)$, in I consists of K pairwise disjoint open intervals with lengths

$$1>g_{1}L\ge g_{2}L\ge \cdots \ge g_{K}L>0,$$

called the first intervals. Note that the quantities $g_1,\cdots ,g_K$, called the gaps, along with the scaling ratios $r_1,\dots ,r_M$, satisfy the equation

$$\sum _{j=1}^M{r}_j+\sum _{k=1}^K{g}_k=1.$$

The process which was just described above is then repeated for each of the M images ${\Phi }_j\left(I\right)$, for $j=1,\dots ,M$, in (3) in order to produce $KM$ additional pairwise disjoint open intervals in I. Repeating this process ad infinitum yields countably many open intervals, which defines a fractal string $\mathcal{L}$ with bounded open set $\Omega$ given by the (necessarily disjoint) union of these open intervals. Any fractal string obtained in this manner is called a self-similar fractal string (or a self-similar string, in short).

Lapidus and van Frankenhuijsen have shown that the geometric zeta functions of self-similar fractal strings have meromorphic continuations to all of $\mathbb{C}$; see Theorem 2.3 in Chapter 2 of [8]. Specifically, the geometric zeta function ${\zeta }_{\mathcal{L}}\left(s\right)$ of any self-similar fractal string with scaling ratios ${\left\{r_j\right\}}_{j=1}^M$, gaps ${\left\{g_k\right\}}_{k=1}^K$, and total length L is given by

$${\zeta }_{\mathcal{L}}\left(s\right)=\frac{L^s{\sum }_{k=1}^K{g}_k^s}{1-{\sum }_{j=1}^M{r}_j^s},\mathrm{for}\mathrm{all}s\in \mathbb{C}.$$

(4)

Both the numerator and the denominator of the right-hand side of (4) are special kinds of exponential polynomials, known as Dirichlet polynomials. Hence, as was done in [6] and Chapter 3 of [8], the more general situation of the sets of complex dimensions of Dirichlet polynomials is considered, as is next explained.

Definition 3.

Given an integer $N\ge 1$, let $r_0>r_1>\cdots >r_N>0$, and let $m_0,m_1,\dots ,m_N\in \mathbb{C}$. The function $f:\mathbb{C}\to \mathbb{C}$ given by

$$f\left(s\right)=\sum _{j=0}^N{m}_j{r}_j^s$$

(5)

is called a Dirichlet polynomial with scaling ratios $r_1,\dots ,r_N$ and respective multiplicities $m_0,\dots ,m_N$. (In the geometric situation of a self-similar string $\mathcal{L}$ discussed just above, $r_0≔-1$ and $m_0≔1$, while the $r_j$’s, with $j=1,\dots ,N$, correspond to the distinct scaling ratios, among the scaling ratios ${\left\{r_j\right\}}_{j=1}^M$ of $\mathcal{L}$. Hence, in particular, $1\le N\le M$ in this case, and, modulo a suitable abuse of notation, for each distinct scaling ratio $r_j$, for $j=1,\dots ,M$, $m_j≔\#\{1\le k\le M:r_k=r_j\}$ is indeed the multiplicity of $r_j$).

Therefore, the set of complex dimensions of any self-similar fractal string is a subset of the set of complex dimensions of an associated Dirichlet polynomial $f\left(s\right)$, as given in (5). While, in general, some of the zeros of the denominator of the right-hand side of (4) could be cancelled by the roots of its numerator (see [8] (Section 2.3.3)), in the important special case of a single gap length (i.e., when $g_1=\cdots =g_K$), the complex dimensions precisely coincide with the complex dimensions of $f\left(s\right)$. This can be seen directly (in light of (4)) or else by choosing the length L of the interval to be the reciprocal of the single gap length, which simplifies the geometric zeta function in such a way that the numerator, on the right-hand side of (4), is equal to 1; note that this rescaling has no effect on the complex dimensions. Hence, in that case, there are no cancellations, and all of the roots of $f\left(s\right)$ are complex dimensions.

The result in (4) establishes a deep connection between the study of complex dimensions of self-similar fractal strings and that of the roots of Dirichlet polynomials which was gaining interest as early as the start of the nineteenth century; see, e.g., [6,7,8,17,18], along with the relevant references therein.

In light of the discussion surrounding Equation (4), it suffices to study more generally the sets of complex dimensions of Dirichlet polynomials, which will be the focus for the remainder of this paper. For the purpose of investigating the sets of complex dimensions of Dirichlet polynomials, it is assumed without any loss of generality that $m_0≔-1$ and $r_0≔1$ in (5). That is, in the remainder of this paper, we will only consider Dirichlet polynomials of the form

$$f\left(s\right)=1-\sum _{j=1}^N{m}_j{r}_j^s,$$

(6)

with ${\left\{r_j\right\}}_{j=1}^N$ and ${\left\{m_j\right\}}_{j=1}^N$ as in Definition 3.

2.2. Lattice/Nonlattice Dichotomy and Lattice String Approximation

Let f be a Dirichlet polynomial, with distinct scaling ratios $r_1,\dots ,r_N$ and multiplicities $m_1,\dots ,m_N$, given by (6). Define the weights $w_1,\dots ,w_N$ of f by $w_j≔-log{r}_j$, for $1\le j\le N$.

Definition 4.

A Dirichlet polynomial f is called lattice if $w_j/w_1$ is rational for $1\le j\le N$, and it is called nonlattice otherwise. (Note that if $N=1$, then f must be lattice because $w_1/w_1=1$ is rational).

It is straightforward to check that a Dirichlet polynomial f is lattice if and only if there exists a (necessarily unique) real number r in $(0,1)$, called the multiplicative generator of f, and positive integers $k_1,\dots ,k_N$, without common divisors, such that $r_j=r^{k_j}$ for $j=1,\dots ,N$. Put another way, the lattice case is when the rank of the additive group

$$G≔\sum _{j=1}^N\mathbb{Z}{w}_j$$

equals 1, and the nonlattice case is when this rank is $\ge 2$.

Definition 5.

The rank of a Dirichlet polynomial is defined to be the rank of the group G defined above. Then, $f\left(s\right)$ is called generic nonlattice if the number N of distinct scaling ratios satisfies $N\ge 2$ and is equal to the rank of $f\left(s\right)$; furthermore, still of $N\ge 2$, $f\left(s\right)$ it is said to be nongeneric nonlattice, otherwise. In other words, $f\left(s\right)$ is generic nonlattice if and only if $N\ge 2$ and $w_1,\dots ,w_N$ are rationally independent.

Moreover, a self-similar fractal string is called (generic) nonlattice if its associated Dirichlet polynomial is (generic) nonlattice. A thorough description of the structure of the sets of complex dimensions of Dirichlet polynomials is provided by [8] (Theorem 3.6). Some of the most relevant features to the current paper are as follows:

The set of complex dimensions of any Dirichlet polynomial is a subset of the horizontally bounded vertical strip

$$R≔\{z\in \mathbb{C}:D_{\ell }\le \Re z\le D\},$$

where $D_{\ell }$ and D are the unique real numbers satisfying the equations (If $N=1$, then the second sum on the left-hand side of (7) is equal to zero, by convention).

$$1+\sum _{j=1}^{N-1}>|m_j|r_j^{D_{\ell }}=|m_N|r_N^{D_{\ell }}\mathrm{and}\sum _{j=1}^N\left|m_j\right|r_j^D=1,$$

(7)

respectively. These numbers satisfy the inequality $-\infty <D_{\ell }\le D$. If the multiplicities are positive integers, then the complex dimensions are symmetric about the real axis, the number D defined above is positive, and it is the only real root of f; furthermore, it is a simple root.

Remark 3.

In the case of a self-similar string $\mathcal{L}$, the nonnegative number D does not exceed 1 and coincides with $D_{\mathcal{L}}$, the inner Minkowski dimension of $\mathcal{L}$: $D=D_{\mathcal{L}}={\sigma }_{\mathcal{L}}$, in the notation introduced earlier for fractal strings.

2.2.1. Lattice Versus Nonlattice

If the Dirichlet polynomial (6), with distinct scaling ratios

$$1=r_0>r_1>\cdots >r_N>0,$$

is lattice, then according to Definition 4, the associated real numbers

$$1<\frac{w_2}{w_1}<\cdots <\frac{w_N}{w_1}<\infty ,$$

(8)

which are explicitly determined by the weights

$$0=w_0<w_1<\cdots <w_N<\infty ,$$

are all rational. Therefore, there exist positive integers

$$q<k_2<\cdots <k_N<\infty$$

such that

$$\frac{w_j}{w_1}=\frac{k_j}{q},\mathrm{for}j=2,\dots ,N.$$

According to [8] (Theorem 3.6), the complex dimensions of a lattice Dirichlet polynomial $f\left(s\right)$ lie periodically on finitely many vertical lines, and on each line they are separated by the positive number

$$\mathbf{p}=\frac{2\pi }{log{r}^{-1}},$$

called the oscillatory period of $f\left(s\right)$.

More precisely, following the discussion surrounding [8] (Equation (2.48), p. 58), the roots are computed by first rewriting $f\left(s\right)$ as a polynomial $g\left(z\right)$ of degree $k_N$ in the complex variable $z≔r^s$, where $r=r_1^{1/q}$ is the multiplicative generator of $f\left(s\right)$:

$$g\left(z\right)=1-m_1{z}^q-m_2{z}^{k_2}-m_3{z}^{k_3}-\cdots -m_N{z}^{k_N}.$$

(9)

There are $k_N$ roots of $g\left(z\right)$, counted with multiplicity. Each one is of the form

$$z=\left|z\right|e^{i\theta },$$

where $-\pi <\theta \le \pi$, and it corresponds to a unique root of $f\left(s\right)$, namely,

$$\omega =\frac{-log\left|z\right|}{log{r}^{-1}}-\frac{i\theta }{log{r}^{-1}}.$$

Therefore, given a lattice Dirichlet polynomial f with oscillatory period $\mathbf{p}$, there exist complex numbers ${\omega }_1,\dots ,{\omega }_u$ such that the set ${\mathcal{D}}_f$ of complex dimensions of f is given by

$${\mathcal{D}}_f=\bigcup _{1\le j\le u}{H}_j,$$

where for $1\le j\le u$,

$$H_j≔\{{\omega }_j+in\mathbf{p}:n\in \mathbb{Z}\}.$$

Now, let f be a nonlattice Dirichlet polynomial given by

$$f\left(s\right)=1-\sum _{j=1}^N{m}_j{r}_j^s$$

and with weights $w_1,\dots ,w_N$. Then, $N\ge 2$ and at least one of the associated real numbers

$$\frac{w_2}{w_1},\frac{w_3}{w_1},\dots ,\frac{w_N}{w_1}$$

(10)

is irrational; see Definition 4. Writing

$$f\left(s\right)=1-\sum _{j=1}^N{m}_j{\left(r_1^s\right)}^{w_j/w_1},$$

(11)

and noting that not all of the associated real numbers in (8) are rational, one sees that $f\left(s\right)$ cannot be expressed as a polynomial, which means that the approach which was just described above to compute the roots of a lattice Dirichlet polynomial is not applicable in the nonlattice case. Instead, the roots are approximated by a procedure developed by the two authors of [5,6,7,8]. The practicality of their procedure rests upon a long standing-problem in the theory of Diophantine approximations: namely, to efficiently generate infinitely many good rational approximations, with a common denominator, to a vector of real numbers with at least one irrational coordinate; see, e.g., [19].

Using this approximation procedure, referred to in the current paper as the Lattice String Approximation algorithm (LSA algorithm for short), the authors of [5,6,7,8] showed that the set of complex dimensions of nonlattice Dirichlet polynomial equations exhibit continuously evolving periodic patterns; they say that the complex dimensions of nonlattice Dirichlet polynomials have a quasiperiodic pattern; see, e.g., Remark 3.7 in [6] and Section 3.4 in [8].

2.2.2. Lattice String Approximation

The LSA algorithm is based on the theory of Diophantine approximations, which deals with the approximation of real numbers by rational numbers. The main step of the algorithm replaces the real numbers $w_2/w_1,\dots ,w_N/w_1$ in (8) with rational approximations having a common denominator. The resulting Dirichlet polynomial is lattice, and the roots of this resulting Dirichlet polynomial approximate the roots of (11) in a very special way. Therefore, before stating Theorem 1 below, which provides the algorithm, the following lemma on simultaneous Diophantine approximation is stated; see, e.g., [20] (Theorem 1A, p. 27). This well-known result is a generalization to several real numbers of Dirichlet us approximation theorem, itself a consequence of the pigeonhole principle.

Lemma 1.

Let $f\left(s\right)$ be a nonlattice Dirichlet polynomial with associated weights $w_1,\dots ,w_N$, where $N\ge 2$. Then, for every real number $Q>1$, there exist infinitely many vectors $(q,k_2,\dots ,k_N)\in {\mathbb{N}}^{N+1}$ such that

$$\left|\frac{w_j}{w_1}-\frac{k_j}{q}\right|<\frac{1}{qQ},$$

(12)

for all integers j such that $2\le j\le N$ and integers q such that $1\le q<Q^{N-1}$. Moreover, $q\to \infty$ as $Q\to \infty$.

Let f be a nonlattice Dirichlet polynomial with associated real numbers as in (8). If a real number $Q>1$ and positive integers $q,k_2,\dots ,k_N$ are computed such that Q and the vector $(q,k_2,\dots ,k_N)$ satisfy inequality (12), for each integer $j\in \{2,\dots ,N\}$, then the pair

$$Q,(q,k_2,k_3,\dots ,k_N)$$

(13)

is called a simultaneous Diophantine approximation to the associated real numbers in (8) (In the standard literature, the denominator q in a simultaneous Diophantine approximation also satisfies the inequality $q<Q^{N-1}$ in Lemma 1. However, since the proof of Theorem 1 does not use this estimate, we ignore this fact here and in the sequel). We are now ready to state the following key result ([8] (Theorem 3.18, p. 34)).

Theorem 1

(M. L. Lapidus and M. van Frankenhuijsen; [5,6,7,8]). Let $f\left(s\right)$ be a nonlattice Dirichlet polynomial of the form (6) with scaling ratios $1>r_1>\cdots >r_N>0$ and multiplicities $m_1,\dots ,m_N$, where $N\ge 2$ (Recall that one must then have $N\ge 2$; otherwise, one would be in the lattice case). Let $Q>1$, and let q and $k_j$ be as in Lemma 1 (except possibly without the condition $q<Q^{N-1}$). Then, the Dirichlet polynomial

$$f_q\left(s\right)=1-m_1{\left(r_1\right)}^s-\sum _{j=2}^N{m}_j{\left(r_1^{k_j/q}\right)}^s$$

is lattice with generator $r_1^{1/q}$ and oscillatory period

$$\mathbf{p}={\mathbf{p}}_q=:=\frac{2\pi q}{log{r}_1^{-1}}.$$

Moreover, for every approximation error $\epsilon >0$, if s belongs to the ε-region of stability (of radius εCQp)

$$B_{\epsilon }(q,Q)≔\left\{z\in \mathbb{C}:\left|z\right|<\epsilon CQ\mathbf{p}\right\},$$

then

$$|f_q\left(s\right)-f\left(s\right)|<\epsilon ,$$

where

$$C≔\frac{1}{2\pi }\sum _{j=1}^N\left|m_j\right|{\left(\frac{{\sum }_{j=0}^N\left|m_j\right|}{min\left\{1,\left|m_N\right|\right\}}\right)}^{\frac{-2w_N}{min\left\{w_1,w_N-w_{N-1}\right\}}}$$

(14)

is the LSA constant of $f\left(s\right)$(Note that since $m_0=-1$, we have that $\left|m_0\right|=1$ here).

Remark 4.

For a fixed order of accuracy $\epsilon >0$, we call a root of a lattice string approximation $f_q\left(s\right)$ lying inside its ε-region of stability a stable root, and we say that $f_{q_2}\left(s\right)$ is more stable than $f_{q_1}\left(s\right)$ if the ε-region of stability of $f_{q_2}\left(s\right)$ contains that of $f_{q_1}\left(s\right)$.

In summary, Theorem 1 says that a simultaneous Diophantine approximation

$$Q,(q,k_2,\dots ,k_N)$$

to the real numbers in (8) determines a lattice string approximation

$$f_q\left(s\right)=1-r_1^{-s}-r_1^{-s{k}_2/q}-\cdots -r_1^{-s{k}_N/q},$$

(15)

with the property that its values are close to the values of $f\left(s\right)$, with prescribed approximation error $\epsilon >0$, within a region of stability with radius that is proportional to $\epsilon$; the smaller the approximation error, the smaller the region of stability. The implication of Theorem 1 is that the roots of $f\left(s\right)$ are almost periodically distributed. That is, given a lattice string approximation $f_q\left(s\right)$ to a nonlattice Dirichlet polynomial $f\left(s\right)$, the roots of $f\left(s\right)$ are near the periodically distributed roots of $f_q\left(s\right)$, for a certain number of periods. Then, the roots of $f\left(s\right)$ start to deviate from this periodic pattern, and a new periodic pattern, associated with a more stable lattice string approximation, gradually emerges; see ibid.

Before illustrating this discussion by means of several examples in Section 4, we present our implementation of the LLL algorithm for simultaneous Diophantine approximations in the following section, which we will use in order to explore the roots of the more complicated Dirichlet polynomials with rank three or more.

3. Simultaneous Diophantine Approximations

In general, approximating the sets of complex dimensions of a nonlattice Dirichlet polynomial via the LSA algorithm requires a practical method for generating simultaneous Diophantine approximations. In 1982, A. K. Lenstra, H. W. Lenstra, and L. Lovász (or LLL, for brevity) presented in their paper [11] the first polynomial-time algorithm to factor a nonzero polynomial $f\in \mathbb{Q}\left[x\right]$ into irreducible factors in $\mathbb{Q}\left[x\right]$. Specifically, the number of arithmetic operations needed is bounded by a constant multiple of $n^4$, where n is the size of the input; see [11] (Proposition 1.26). The authors of that paper showed that their algorithm, which is now commonly referred to as the LLL algorithm, can generate simultaneous Diophantine approximations; see Theorem 2 below. As suggested by Lapidus and van Frankenhuijsen in [7] (p. 99), and then later in [8] (Remark 3.38, p. 101), the current paper utilizes the LLL algorithm in order to generate lattice string approximations.

The present section gives an overview of the LLL algorithm, and explains how it can be used to generate simultaneous Diophantine approximations. For more detail on the LLL algorithm and the corresponding method of lattice basis reduction, the interested reader can consult the original paper [11], together with Bremner’s book [12], providing an introductory exposition of the algorithm.

3.1. Lattice Basis Reduction

Definition 6.

Let n be a positive integer. A subset L of the n-dimensional real vector space ${\mathbb{R}}^n$ is called a (full-rank) lattice if there exists a basis $\beta =\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_n\}$ of ${\mathbb{R}}^n$ such that

$$L=\left\{\sum _{j=1}^n{a}_j{\mathbf{x}}_j:a_1,a_2,\dots ,a_n\in \mathbb{Z}\right\}.$$

The subset β is called a basis of L, and n is called the rank of L. Moreover, for each $1\le j\le n$, let

$${\mathbf{x}}_j=(x_{j,1},\dots ,x_{j,n}),$$

where for each $1\le k\le n$, $x_{j,k}\in \mathbb{R}$. Then, the determinant $d\left(L\right)$ of L is defined by $d\left(L\right)=|det(X\left)\right|$, where X is the $n\times n$ matrix given by ${\left(X\right)}_{jk}=x_{j,k}$; the matrix X is called the basis matrix of L for β.

It readily follows from the following proposition that the positive number $d\left(L\right)$ does not depend on the choice of basis, as is stated in Corollary 1 below.

Proposition 1.

Let ${\beta }_1=\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_n\}$ and ${\beta }_2=\{{\mathbf{y}}_1,\dots ,{\mathbf{y}}_n\}$ be two bases of a lattice L of ${\mathbb{R}}^n$. Let X and Y be the basis matrices of L corresponding to the bases ${\beta }_1$ and ${\beta }_2$, respectively. Then,

$$Y=BX,$$

for some $n\times n$ matrix B with integer entries and determinant $\pm 1$; hence, either B or (if n is odd)$-B$ belongs to $SL(n,\mathbb{Z})$.

Proof. 

Since ${\beta }_1,{\beta }_2\subset L$, for each $j=1,\dots ,n$, there exist integers

$$a_{j,1},\dots ,a_{j,n},b_{j,1},\dots ,b_{j,n},$$

such that

$${\mathbf{x}}_j=a_{j,1}{y}_1+\cdots +a_{j,n}{y}_n\mathrm{and}{\mathbf{y}}_j=b_{j,1}{x}_1+\cdots +b_{j,n}{x}_n.$$

This means that there exist $n\times n$ matrices A and B with integer entries given by

$${\left(A\right)}_{jk}=a_{jk}\mathrm{and}{\left(B\right)}_{jk}=b_{jk},$$

respectively, such that $X=AY$ and $Y=BX$. By substitution, $Y=\left(BA\right)Y$. Since Y is invertible, it follows that $BA=I$, and so $det\left(A\right)det\left(B\right)=1$. Since A and B have integer entries, it follows that $det\left(B\right)=\pm 1$, as desired. □

Corollary 1.

Under the hypotheses and with the notation of Proposition 1,

$$det\left(L\right)=|det(X\left)\right|=|det(Y\left)\right|.$$

Therefore, the determinant of L, $det\left(L\right)=|det(X\left)\right|$, is independent of the choice of the basis of L used to evaluate it.

Suppose that we are given a lattice $L\subset {\mathbb{R}}^n$. In a shortest vector problem, one finds the shortest nonzero vector in L. That is, one tries to compute

$$\lambda =\lambda \left(L\right)≔\underset{\mathbf{x}\in L\backslash \left\{\mathbf{0}\right\}}{min}\left|\mathbf{x}\right|.$$

In the $\gamma$-approximation version of such a problem, one finds a nonzero lattice vector of length at most $\gamma ·\lambda \left(L\right)$, for a given real number $\gamma \ge 1$. These types of problems have many applications in number theory and cryptography; see, e.g., [12] (Chapters 7 and 9). No efficient algorithm is known to find the shortest vector in a lattice, or even just the length of the shortest vector. The LLL algorithm is the first polynomial-time algorithm to compute what is called an $\alpha$-reduced basis for a given lattice; see [11] (Proposition 1.26). Simply put, an $\alpha$-reduced basis for a lattice L is one with short vectors that are nearly orthogonal.

The α-Reduced Basis for a Lattice

Let $\beta =\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_n\}$ be a basis of ${\mathbb{R}}^n$, and let ${\mathbf{x}}_1^{*}={\mathbf{x}}_1$. For $1<j\le n$, define

$${\mathbf{x}}_j^{*}={\mathbf{x}}_j-\sum _{k=1}^{j-1}{\mu }_{j,k}{\mathbf{x}}_k^{*},$$

where, for $1\le k<j\le n$,

$${\mu }_{j,k}=\frac{{\mathbf{x}}_j·{\mathbf{x}}_k^{*}}{{\mathbf{x}}_k^{*}·{\mathbf{x}}_k^{*}}=\frac{{\mathbf{x}}_j·{\mathbf{x}}_k^{*}}{{\left|{\mathbf{x}}_k^{*}\right|}^2}.$$

The vectors ${\mathbf{x}}_1^{*},\dots ,{\mathbf{x}}_n^{*}$, called the Gram–Schmidt orthogonalization of $\beta$, form an orthogonal basis of ${\mathbb{R}}^n$, and the numbers ${\mu }_{j,k}$ are called the Gram–Schmidt coefficients of the orthogonalization.

Definition 7.

Let $\beta =\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_n\}$ be a basis for a lattice $L\subset {\mathbb{R}}^n$, and let ${\mathbf{x}}_1^{*},\dots ,{\mathbf{x}}_n^{*}$ be its Gram–Schmidt orthogonalization with Gram–Schmidt coefficients ${\mu }_{j,k}$, for $1\le k<j\le n$. Furthermore, let α be such that $1/4<\alpha <1$. The basis β is said to be α-reduced if the following two conditions are satisfied:

(i) 

$\left|{\mu }_{j,k}\right|\le 1/2,for1\le k<j\le n$;

(ii) 

${|x_j^{*}+{\mu }_{j,j-1}{x}_{j-1}^{*}|}^2\ge \alpha {\left|x_{j-1}^{*}\right|}^2,for1<j\le n$.

3.2. Simultaneous Diophantine Approximations via LLL

In this section, we discuss the key steps needed in order to generate lattice string approximations by using the LLL algorithm. Our implementation uses continued fractions, as opposed to using rational numbers with denominator equal to a power of 2, which was the approach used in [21] (Remark 4.1, p. 177).

After having recalled a technical result from [11] (Proposition 3.5 below), we state and prove the main result of [11], from our present perspective, namely, Theorem 2. This result establishes the LLL algorithm as a useful tool for computing simultaneous Diophantine approximations to two or more real numbers.

Proposition 2

([11] (Proposition 1.6); as described, e.g., in [12] (Proposition 4.6)). Let $\beta =\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_n\}$ be an α-reduced basis for a lattice $L\subset {\mathbb{R}}^n$, and let ${\mathbf{x}}_1^{*},\dots ,{\mathbf{x}}_n^{*}$ be its Gram–Schmidt orthogonalization. Then, the following three properties hold:

(i) 

${\left|{\mathbf{x}}_k\right|}^2\le {(4/(4\alpha -1))}^{j-1}·{\left|{\mathbf{x}}_j^{*}\right|}^2,\mathit{for}1\le k\le j\le n$;

(ii) 

$d\left(L\right)\le {\Pi }_{j=1}^n\left|{\mathbf{x}}_j\right|\le {(4/(4\alpha -1))}^{n(n-1)/4}·d\left(L\right)$;

(iii) 

$\left|{\mathbf{x}}_1\right|\le {(4/(4\alpha -1))}^{\frac{n-1}{4}}d{\left(L\right)}^{\frac{1}{n}}$.

Theorem 2

(A. K. Lenstra, H. W. Lenstra and L. Lovász, [11] (Proposition 1.39); as described, e.g., in [12] (Proposition 9.4) ). Given rational numbers $x_1,x_2,\dots ,x_n$ and δ satisfying $0<\delta <1$, there exists a polynomial-time algorithm (called the LLL algorithm) which finds integers $b\in \mathbb{N}$ and $a_1,\dots ,a_n\in \mathbb{Z}$ such that

$$\left|x_j-\frac{a_j}{b}\right|\le \frac{\delta }{b},and1\le b\le 2^{\frac{n(n+1)}{4}}{\delta }^{-n} for j=1,\dots ,n.$$

(16)

Proof. 

Let L be the lattice of rank $n+1$ with basis matrix

$$X=\left(\begin{array}{cccc}{2}^{\frac{-n(n+1)}{4}}{\delta }^{n+1}& x_1& \cdots & x_n\\ 0& -1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & -1\end{array}\right).$$

Using the LLL Algorithm, generate a reduced basis $\beta =\{{\mathbf{y}}_1,\dots ,{\mathbf{y}}_n\}$ for L, with reduction parameter $\alpha =3/4$. Then, if Y denotes the basis matrix of L for $\beta$, Proposition 1 says that there exists an $(n+1)\times (n+1)$ matrix C with integer entries such that $Y=CX$.

That is, there exist $c_{j,k}\in \mathbb{Z}$ for $0\le j,k\le n$ such that

$$Y=\left(\begin{array}{cccc}{c}_{0,0}& c_{0,1}& \cdots & c_{0,n}\\ c_{1,0}& c_{1,1}& \cdots & c_{1,n}\\ ⋮& ⋮& \ddots & ⋮\\ c_{n,0}& c_{n,1}& \cdots & c_{n,n}\end{array}\right)·\left(\begin{array}{cccc}{2}^{\frac{-n(n+1)}{4}}{\delta }^{n+1}& x_1& \cdots & x_n\\ 0& -1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & -1\end{array}\right).$$

In particular,

$${\mathbf{y}}_1=\left(c_{0,0}{2}^{\frac{-n(n+1)}{4}}{\delta }^{n+1},c_{0,0}{x}_2-c_{0,1},\dots ,c_{0,0}{x}_n-c_{0,n}\right).$$

Put $b=c_{0,0}$, and for $j=1,\dots ,n$, put $a_j=c_{0,j}$. Then, It follows from the third inequality (i.e., from part (iii) in Proposition 2) that

$$\left|{\mathbf{y}}_1\right|\le 2^{\frac{n}{4}}d{\left(L\right)}^{\frac{1}{n+1}}=\delta <1.$$

(17)

Note that if $b=0$, then $\left|{\mathbf{y}}_1\right|\ge 1$, where

$${\mathbf{y}}_1=\left(0,-a_1,-a_2,\dots ,-a_n\right);$$

but that contradicts (17). Upon replacing ${\mathbf{y}}_1$ by $-{\mathbf{y}}_1$, it can be assumed without loss of generality that $b\ge 1$. Therefore, since the length of ${\mathbf{y}}_1$ is greater than or equal to any of the components of ${\mathbf{y}}_1$,

$$2^{\frac{-n(n+1)}{4}}{\delta }^{n+1}b\le \left|{\mathbf{y}}_1\right|\le \delta ;$$

so that

$$b\le 2^{\frac{n(n+1)}{4}}{\delta }^{-n}$$

and hence,

$$\left|x_j-\frac{a_j}{b}\right|<\frac{\delta }{b},\mathrm{for}1\le j\le n.$$

This completes the main part of the proof of the theorem. Moreover, since the number of arithmetic operations needed by LLL is $O(n^{4}logB)$, where B is a constant that is explicitly determined from the rows of X (see [11] (Proposition 1.26)), we now have the desired polynomial-time algorithm. □

3.2.1. Description of Our Current Implementation

There have been a number of implementations of the LLL algorithm for generating simultaneous Diophantine approximations to a set of real numbers

$$x_1,x_2,\dots ,x_N,$$

(18)

aimed at generating approximations with bounded Dirichlet coefficient (see, e.g., [21] (Definition 1.2, p. 168)) and prescribed quality; see, e.g., [21,22]. The first known practical algorithm for generating simultaneous Diophantine approximations was given by Jacobi in [23]. See [24] for a general review of the problem of simultaneous Diophantine approximation, including some of the algorithms proposed after Jacobi’s algorithm. Our implementation is focused on computing sequences of increasingly accurate simultaneous Diophantine approximations.

Any practical implementation of the LLL algorithm uses rational numbers. For example, in an iterative version of the LLL algorithm from [21], which finds higher-dimensional simultaneous Diophantine approximations (see [20] (Chapter 2, Theorem 1E)), all of the irrational numbers in their implementation are approximated by rational numbers with denominator $2^M$, for some $M\in \mathbb{Z}$ (i.e., by dyadic numbers). Our implementation follows the one in [12] (Section 9.2) and uses the continued fraction process (see, e.g., [20] (Chapter 1)), which generates, for any real number $\alpha$, an infinite sequence of “reduced fractions”

$$\frac{a_1}{b_1},\frac{a_2}{b_2},\frac{a_3}{b_3},\dots$$

that approximate $\alpha$. Each rational number $a_j/b_j$ is called the $j^{th}$ convergent to $\alpha$, and it is a well-known fact that every convergent $a_j/b_j$ to $\alpha$ satisfies the inequality

$$\left|\alpha -\frac{a_j}{b_j}\right|<\frac{1}{b_j^2};$$

see, e.g., [20] (Chapter 1). Therefore, since $b_j\to \infty$ (see the proof of [20] (Chapter 1, Lemma 4D)), for any real number $Q>1$, there exists $j\ge 1$ such that the ordered pair Q, $(b_j,a_j)$ satisfies inequality (12) from Lemma 1, and thus forms a simultaneous Diophantine approximation to $\alpha$; see the paragraph preceding the statement of Theorem 1.

Denote the $n_j^{th}$ convergent to the real number $x_j$ by

$$\frac{a_{j,n_j}}{b_{j,n_j}},\mathrm{for}j=1,\dots ,N.$$

We start by initializing $0<\delta <1$ (close to 1) and a positive integer $n_{\mathrm{steps}}$, which together determine the step-size $\Delta \delta =\delta /n_{\mathrm{steps}}$, and then proceed to generate the first convergents

$$\frac{a_{1,1}}{b_{1,1}},\frac{a_{2,1}}{b_{2,1}},\dots ,\frac{a_{N,1}}{b_{N,1}}$$

(19)

to the real numbers in (18) via the continued fraction process. Then, as in the proof of Theorem 2, we take the convergents in (19) along with the current value of $\delta$, and use them both to generate integers $b,a_1,\dots ,a_n$ that satisfy each of the inequalities in (16).

For each $1\le j\le N$, define the errors

$$E_1\left(j\right):=\left|x_j-\frac{a_{j,n_j}}{b_{j,n_j}}\right|\mathrm{and}{E}_2\left(j\right):=\left|\frac{a_j}{b}-\frac{a_{j,n_j}}{b_{j,n_j}}\right|.$$

We distinguish two cases.

Case 1.

If

$$E_2\left(j\right)\ge 2E_1\left(j\right),\mathrm{for}j=1,\dots ,N,$$

(20)

then the simultaneous Diophantine approximation

$$Q=\underset{1\le j\le N}{min}\frac{1}{|x_{j}b-a_j|},(b,a_1,\dots ,a_N)$$

to the real numbers in (18) is obtained, and the entire process is repeated after replacing $\delta$ with $\delta -\Delta \delta$. Note that since $\delta <1$ and $b\ge 1$, we have that

$$\left|x_j-\frac{a_j}{b}\right|<1,\mathrm{for}j=1,\dots ,N;$$

so that $Q>1$. In this case, we say that none of the rational approximations $a_j/b$ can distinguish between the convergent $a_{j,n_j}/b_{j,n_j}$, and the real number $x_j$.

Case 2.

For each $1\le j\le N$ with $E_2\left(j\right)<2E_1\left(j\right)$, the convergent $a_{j,n_j}/b_{j,n_j}$ is updated to the next convergent $a_{j,n_j+1}/b_{j,n_j+1}$, which is closer to $x_j$. With the current value of $\delta$ and the updated convergents, a new set of integers $b,a_1,\dots ,a_n$ satisfying the inequalities in (16) is achieved, and we check whether we are still in Case 2. Since $\delta$ is fixed, this process of updating convergents and checking will eventually terminate because the denominators of the continued fractions tend to infinity, putting us back in Case 1, and therefore yielding another simultaneous Diophantine approximation; see

Table 1. A table showing how the convergents are updated for a fixed $\delta$ to generate two simultaneous Diophantine approximations to the real numbers ${log}_2\left(3\right)$, ${log}_2\left(5\right)$, ${log}_2\left(7\right)$, using the procedure outlined in Section 3.2.1.

$\frac{{\mathit{a}}_{\mathit{j},{\mathit{n}}_{\mathit{j}}}}{{\mathit{b}}_{\mathit{j},{\mathit{n}}_{\mathit{j}}}}$∘	$\frac{{\mathit{a}}_{\mathit{j}}}{\mathit{b}}$•	${\mathit{x}}_1={log}_2\left(3\right),{\mathit{x}}_2={log}_2\left(5\right),{\mathit{x}}_3={log}_2\left(7\right)$♢
		$\delta =0.10$
$\frac{1054}{665}$	$\frac{4953}{3125}$
$\frac{1493}{643}$	$\frac{7256}{3125}$
$\frac{6718}{2393}$	$\frac{8773}{3125}$
		$\delta =0.01$
$\frac{1054}{665}$	$\frac{\mathrm{4,476,254}}{\mathrm{2,824,202}}$
$\frac{1493}{643}$	$\frac{\mathrm{6,557,595}}{\mathrm{2,824,202}}$
$\frac{6718}{2393}$	$\frac{\mathrm{7,928,537}}{\mathrm{2,824,202}}$
		$\delta =0.01$
$\frac{\mathrm{50,508}}{\mathrm{31,867}}$	$\frac{\mathrm{163,519}}{\mathrm{103,169}}$
$\frac{\mathrm{177,797}}{\mathrm{76,573}}$	$\frac{\mathrm{239,551}}{\mathrm{103,169}}$
$\frac{\mathrm{248,027}}{\mathrm{88,349}}$	$\frac{\mathrm{289,632}}{\mathrm{103,169}}$

.

Remark 5.

We choose to use the continued fraction process in our implementation because it is very efficient. Specifically, each convergent is best possible (a rational number $a/b$ is a best possible approximation of a real number α if $|\alpha -a/b|$ does not decrease if $a/b$ is replaced by another rational number written in reduced form and with a smaller denominator), and in principle, the continued fraction process is identical to the Euclidean algorithm. We also note that our implementation extends the one from [12] because it finds a sequence of meaningful simultaneous Diophantine approximations, in the sense described in Case 1 and Case 2 above. While it is true that the rational implementation in [21] also finds meaningful approximations, it does not use the continued fraction process.

4. The Quasiperiodic Patterns in the Nonlattice Case

Using the LSA algorithm, together with our implementation of the LLL algorithm for simultaneous Diophantine approximation (see Section 3.2.1), and the multiprecision polynomial solver MPSolve, which is due to D. A. Bini, G. Fiorentino and L. Robol [13,14], we study examples of nonlattice Dirichlet polynomials previously studied in, e.g., [6,8], as well as several new examples, all aimed at illustrating the discussion in the first paragraph, following the statement of Theorem 1, which describes how the quasiperiodic patterns from the complex dimensions of nonlattice Dirichlet polynomials begin to emerge.

The visual exploration of the quasiperiodic patterns in this section extend those from the previous works by the two authors of [5,6,7,8]; see, especially [8] (Figure 3.6, p.87), ref. [6] (Figure 9, p.62), and also [8] (Figure 3.2, p. 71), along with the associated examples, which show the roots of several lattice string approximations to nonlattice Dirichlet polynomials in sequence, and illustrate the emergence of a quasiperiodic pattern. Our approach starts by taking the best lattice string approximation $f_q\left(s\right)$ that we can compute to a nonlattice Dirichlet polynomial $f\left(s\right)$, where, by “best”, we mean having the largest $\epsilon$-region of stability. We then compute the roots of $f\left(s\right)$, using the complex version of Newton’s method with the stable roots of $f_q\left(s\right)$ as initial guesses, up to a region large enough to include several periods of stable roots from a few increasingly good lattice string approximations (All of the applications of the LSA algorithm to the examples given in Section 4 use $\epsilon =1/10$. While this approximation error is small enough to separate the roots of $f\left(s\right)$ vertically, it does not separate them horizontally. Therefore, it is possible that we miss some roots when applying Newton’s method. In any case, the roots which we obtain suffice to show the emergence of a quasiperiodic pattern, which is the central aim of this section). By plotting the roots of these lattice string approximations against the roots of $f\left(s\right)$, we show how the roots of $f\left(s\right)$ are near the roots of each approximation for a certain number of periods of that approximation (sometimes, only for a fraction of a period), and how they eventually start to move away from those roots. We also show plots of the best lattice string approximations that we computed, giving an impression of the quasiperiodic pattern on a larger scale; compare with [8] (Figure 3.7, p. 88). We also present an especially crafted nonlattice Dirichlet polynomial whose roots exhibit a global structure which has not been observed before.

If the rank of the additive group G corresponding to a nonlattice Dirichlet polynomial $f\left(s\right)$ is equal to two, we can use the continued fraction process alone in order to generate lattice string approximations to $f\left(s\right)$. Otherwise, the rank is more than two, and we turn to our implementation of the LLL algorithm for simultaneous Diophantine approximation. In any case, we plot the roots of a lattice string approximation $f_q\left(s\right)$ corresponding to the simultaneous Diophantine approximation given by the pair Q, $(q,k_2,\dots ,k_N)$ by computing the roots of an associated polynomial in $\mathbb{C}\left[x\right]$ with degree $k_N$, and which is typically sparse; see the discussion surrounding the equation in (9) from Section 2.2.1. In Section 4.2, we show both generic and nongeneric nonlattice examples with rank two, and in Section 4.3, we show generic and nongeneric nonlattice examples with rank three or more. In practice, lattice string approximations with at least one period of stable roots correspond to polynomials with very large degree. Consequently, it takes a significant amount of computing power to implement the approach described above. In [8], (Section 3.8), the first two authors of the present paper state: “The maximal degree 5000 is the limit of computation: It took several hours with our software on a Sun workstation to compute the golden diagram, which involved solving a polynomial equation of degree 4181. However, finding the roots of the polynomial is the most time-consuming part of the computation. Since these polynomials contain only a few monomials, there may exist ways to speed up this part of the computation.” In the current paper, using MPSolve and the high performance computer ELSA at the third author’s institution, the maximal degree 300,000 k is now our limit.

In the present paper, we are careful about the combination of scaling ratios and multiplicities from a nonlattice Dirichlet polynomial $f\left(s\right)$. Indeed, if they are not balanced properly, even the best lattice string approximations that we would be able to compute will have very few stable roots. Specifically, there is still the issue of the size of the LSA constant C in the radius $\epsilon CQ{\mathbf{p}}_q$ of the $\epsilon$-region of stability, and which in some cases can be smaller than the reciprocal of Q. Therefore, we pay special attention to the LSA constant C and show how to reverse engineer examples with C being not too small. Hence, not only do we provide a new implementation of the LLL algorithm that enables us to deal with more complicated examples, but we also give a “starter-kit” for the interested reader to explore the quasiperiodic patterns of nonlattice Dirichlet polynomials.

4.1. A Special Class of Nonlattice Dirichlet Polynomials

Let

$$f\left(s\right)=1-\sum _{j=1}^N{m}_j{r}_j^s$$

be a nonlattice Dirichlet polynomial, which is associated to the real numbers

$$\frac{w_2}{w_1},\frac{w_3}{w_1},\dots ,\frac{w_N}{w_1},$$

(21)

explicitly determined from the scaling ratios of $f\left(s\right)$. Setting ${\alpha }_1=1$ and ${\alpha }_j=w_j/w_1$, for all $2\le j\le N$, we write

$$f\left(s\right)=1-\sum _{j=1}^N{m}_j{r}_1^{{\alpha }_{j}s}.$$

Recall that each simultaneous Diophantine approximation given by the ordered pair Q, $(q,k_2,\dots ,k_N)$ to the real numbers ${\alpha }_2,\dots ,{\alpha }_N$, such that $k_j/q$ approximates ${\alpha }_j$, for all integers j such that $2\le j\le N$, determines the lattice string approximation

$$f_q\left(s\right)=1-m_1{r}_1^s-\sum _{j=2}^N{m}_j{\left(r_j^{k_j/q}\right)}^s$$

to $f\left(s\right)$, and that for any approximation error $\epsilon >0$, the radius of the $\epsilon$-region of stability $B_{\epsilon }(q,Q)$ of $f_q\left(s\right)$ is $\epsilon CQ{\mathbf{p}}_q$, where

$$C:=\frac{1}{2\pi }\sum _{j=1}^N\left|m_j\right|{\left(\frac{{\sum }_{j=0}^N\left|m_j\right|}{min\left\{1,\left|m_N\right|\right\}}\right)}^{\frac{-2w_N}{min\left\{w_1,w_N-w_{N-1}\right\}}}$$

is the LSA constant of $f\left(s\right)$ from Theorem 1, and ${\mathbf{p}}_q$ is the oscillatory period of $f_q\left(s\right)$.

Consider the class of nonlattice Dirichlet polynomials of the form

$$f\left(s\right)=1-m_1{r}^s-m_2{r}^{{\alpha }_{2}s}-m_3{r}^{{\alpha }_{3}s}-\cdots -m_{N-1}{r}^{{\alpha }_{N-1}s}-r^{{\alpha }_{N}s},$$

(22)

where $1>r>0$ and $m_1,m_2,\dots ,m_{N-1}>0$. Note that

$$1<{\alpha }_2<{\alpha }_3<\cdots <{\alpha }_{N-1}<{\alpha }_N,$$

and that since $f\left(s\right)$ is nonlattice, ${\alpha }_j$ is irrational, for some integer j such that $2\le j\le N$. All of the examples of nonlattice Dirichlet polynomials shown in [5,6,7,8] are of the form (22), except for both the scaled and unscaled versions of the example in [8] (Example 3.55, p. 113). The following new theorem provides infinitely many nonlattice Dirichlet polynomials of the form (22), with LSA constant arbitrarily close to ${\left(32\pi \right)}^{-1}$.

Theorem 3.

Let $f\left(s\right)$ be a rank two nonlattice Dirichlet polynomial of the form (22). Then, the LSA constant of $f\left(s\right)$ is given by

$$C=C\left(\xi \left(N\right),{\alpha }_{N-1},{\alpha }_N\right)=\frac{\xi \left(N\right)+1}{2\pi }{\left(\frac{1}{{\left(\xi \left(N\right)+2\right)}^2}\right)}^{\frac{{\alpha }_N}{min\left\{1,{\alpha }_N-{\alpha }_{N-1}\right\}}},$$

(23)

where $\xi \left(N\right):={\sum }_{j=1}^{N-1}\left|m_j\right|$.

Moreover, For any $\epsilon >0$, there exists a nonlattice Dirichlet polynomial of the form (22) with LSA constant C satisfying the inequality $0<{\left(32\pi \right)}^{-1}-C<\epsilon$.

Proof. 

The formula for C is found by a direct substitution; see Equation (14) in Theorem 1 above. By requiring that ${\alpha }_N-{\alpha }_{N-1}>1$, we have

$$\frac{{\alpha }_N}{min\left\{1,{\alpha }_N-{\alpha }_{N-1}\right\}}={\alpha }_N.$$

Since we can always manufacture a nonlattice Dirichlet polynomial of the form (22), with $\xi \left(N\right)$ arbitrarily close to zero and ${\alpha }_N$ arbitrarily close to 2 from the right, the theorem follows. □

4.2. Rank Two Examples

Recall from Definition 5 that the rank of a nonlattice Dirichlet polynomial

$$f\left(s\right)=1-m_1{r}_1^s-m_2{r}_2^s-\cdots -m_N{r}_N^s$$

is equal to the number of rationally independent numbers in the set

$$\left\{-log\left(r_1\right),-log\left(r_2\right),\dots ,-log\left(r_N\right)\right\}.$$

If the rank is equal to two, then exactly one of the associated real numbers in (21) is irrational, and we can use the continued fraction process to generate lattice string approximations to $f\left(s\right)$:

Suppose that only $\alpha =w_2/w_1$ is irrational. We start by computing a convergent $a/b$ to $\alpha$, and then we modify the remaining real numbers (which are all rational) so that they have denominator b. Then, we obtain the simultaneous Diophantine approximation given by the pair Q, $(q,k_2,k_3,\dots k_N)$ to the real numbers in (21), where $q=b$, $k_2=a$,

$$\frac{k_j}{q}=\frac{w_j}{w_1},\mathrm{for}j=3,\dots ,N,$$

and

$$Q=\underset{2\le j\le N}{min}\frac{w_1}{\left|w_{j}q-w_1{k}_j\right|}=\frac{w_1}{\left|w_{2}b-w_{1}a\right|}.$$

Finally, we obtain the lattice sting approximation

$$f_q\left(s\right)=1-m_1{\left(r_1\right)}^s-\sum _{j=2}^N{m}_j{\left(r_1^{k_j/q}\right)}^s,$$

with generator $r_1^{1/q}$ and oscillatory period ${\mathbf{p}}_q=\frac{2\pi q}{log{r}_1^{-1}}$.

Otherwise, the rank is greater than two (since $f\left(s\right)$ is nonlattice), and in that case we use the LLL algorithm in order to generate lattice string approximations; examples with rank greater than two are discussed in Section 4.3.

For any lattice string approximation $f_q\left(s\right)$ to a nonlattice Dirichlet polynomial $f\left(s\right)$, we define

$$a=min\{\Re \left(s\right):f_q\left(s\right)=0\}\mathrm{and}b=max\{\Re \left(s\right):f_q\left(s\right)=0\}.$$

This notation will be used in Section 4.2.1 just below.

4.2.1. The 2-3 and the Golden Polynomial

Example 1.

The 2-3 polynomial

$$f\left(s\right)=1-2^{-s}-3^{-s}$$

from, e.g., [8] (Section 2.3.5, pp. 49–50 and Section 3.8, pp. 115, 117), has scaling ratios $r_1=2^{-1}$, $r_2=3^{-1}$ and multiplicities $m_1=m_2=1$. It is also of the form (22), with $N=2$ and ${\alpha }_2={log}_2\left(3\right)$.

Table 2. Simultaneous Diophantine approximations to the real number ${log}_2\left(3\right)$ associated to the 2-3 polynomial, and specifications for the corresponding lattice string approximations.

$\mathit{f}\left(\mathit{s}\right)=1-2^{-\mathit{s}}-3^{-\mathit{s}}$		$\mathit{C}\approx 0.0008$
$\mathbf{Q},(\mathit{q},{\mathit{k}}_{\mathbf{2}})$	${\mathbf{p}}_{\mathit{q}}$	$\mathbf{\epsilon }\mathit{CQ}\mathbf{p}$
$\mathrm{192,530},(\mathrm{111,202};\mathrm{176,251})$	$1.00\times {10}^6$	$1.60\times {10}^7$
$\mathrm{189,140},(\mathrm{79,335};\mathrm{125,743})$	719,150	$1.12\times {10}^7$
$\mathrm{95,410},(\mathrm{31,867};\mathrm{50,508})$	288,865	$2.27\times {10}^6$
$\mathrm{38,096.3},(\mathrm{15,601};\mathrm{24,727})$	141,419	$\mathrm{445,358}$
$\mathrm{15,878.2},(665;1054)$	6028.04	$7912.17$
$678.06,(306;485)$	2773.8	$155.478<{\mathbf{p}}_{306}$
$331.94,(53;84)$	480.43	$13.18<{\mathbf{p}}_{53}$

shows data for several lattice string approximations to the 2-3 polynomial. For example, the lattice string approximation

$$\begin{array}{cc}\hfill f_{\mathrm{15,601}}\left(s\right)& =1-2^{-s}-2^{-s\frac{\mathrm{24,727}}{\mathrm{15,601}}}\hfill \\ \hfill & =1-{\left(2^{-s/\mathrm{15,601}}\right)}^{\mathrm{15,601}}-{\left(2^{-s/\mathrm{15,601}}\right)}^{\mathrm{24,727}}\hfill \end{array}$$

has about three periods of stable roots, and it is determined from the simultaneous Diophantine approximation given by the pair $Q=\mathrm{38,096.3}$, $(\mathrm{15,601};\mathrm{24,727})$ to the real number ${log}_2\left(3\right)$. Note that the best lattice string approximation to the 2-3 polynomial obtained in [6,8] comes from the convergent $485/306$, and does not even have one full period of stable roots. Figure 1 shows how the roots of the 2-3 polynomial (marked with dots) are near the roots of $f_{306}\left(s\right)$ (marked with circles), and how they eventually start to move away from them. Notice that the point at which the roots of the 2-3 polynomial start to move away from the roots of the lattice string approximation agrees with the theoretical prediction from [8]; see Theorem 1.

We also observe that the roots seem to stay close to the roots of $f_{306}$ for much longer near the extreme vertical lines $\Re \left(z\right)=a$ and $\Re \left(z\right)=b$. We do not have an explanation for this phenomenon, which occurs in all of the examples discussed in the current paper. In fact, Example 3 below shows the roots of a lattice string approximation staying close to a third line. Figure 2 displays stable roots of the lattice string approximation $f_{\mathrm{111,202}}\left(s\right)$, giving an impression of the quasiperiodic pattern on a larger scale. We note that large scale plots like the ones in Figure 2 were provided for only three out of the ten rank two examples from [6,8]. In the sequel, we will exhibit additional plots of this kind, and arising from far better lattice string approximations. Furthermore, these plots suggest that the patterns from the roots of very good lattice string approximations lie in a wide spectrum, all the way from highly disordered to regular; compare, especially, Figure 2 with Figure 9.

Example 2.

The golden polynomial

$$f\left(s\right)=1-2^{-s}-2^{-\varphi s}$$

from, e.g., [8] (Section 2.3.5, pp. 49, 51–52, 53, and Section 3.6, pp. 104–106), has scaling ratios $r_1=2^{-1}$, $r_2=2^{-\varphi }$ and multiplicities $m_1=m_2=1$, where $\varphi =\frac{1+\sqrt{5}}{2}$ denotes the golden ratio.

It is also of the form (22), with $N=2$ and ${\alpha }_2=\varphi$; see also the golden+ polynomial in, e.g., [8] (Section 3.2.2, pp. 73–74). We compute lattice string approximations to the golden polynomial by generating convergents to the golden ratio. One way to do this, aside from using the continued fraction process, is to take the Fibonacci numbers

$$1,1,2,3,5,8,13,34,55,\dots$$

and divide each one, starting with the second, by the preceding number.

Table 3. Simultaneous Diophantine approximations to the golden ratio ϕ associated to the golden polynomial, and specifications for the corresponding lattice string approximations.

$\mathit{f}\left(\mathit{s}\right)=1-2^{-\mathit{s}}-2^{-\mathit{\varphi }\mathit{s}}$		$\mathit{C}\approx 0.001$
$\mathbf{Q},(\mathit{q},{\mathit{k}}_{\mathbf{2}})$	${\mathbf{p}}_{\mathit{q}}$	$\mathbf{\epsilon }\mathit{CQ}\mathbf{p}$
$\mathrm{271,444},(\mathrm{121,393};\mathrm{196,418})$	$1.10\times {10}^6$	$3.01\times {10}^7$
$\mathrm{39,603},(\mathrm{17,711};\mathrm{28,657})$	160,545	$\mathrm{642,594}$
$5778,(2584;4181)$	23,423.2	$\mathrm{13,678.4}<{\mathbf{p}}_{2584}$
$3571,(1597;2584)$	14,476.4	$5224.68<{\mathbf{p}}_{1597}$
$2207,(987;1597)$	8946.88	$1995.65<{\mathbf{p}}_{987}$
$1364,(610;987)$	5529.48	$762.27<{\mathbf{p}}_{610}$

shows data for several lattice string approximations to the golden polynomial. Notice that we obtain fewer lattice string approximations to the golden polynomial with at least one period of stable roots than we did for the 2-3 polynomial in Example 1. On the other hand, our best lattice string approximation to the golden polynomial has roots that are stable for about twenty seven periods, whereas for the 2-3 polynomial studied in Example 1, our best one has roots that are stable for about sixteen periods. Figure 3 shows how the roots of the golden polynomial (marked with dots) are near the roots of the lattice string approximations $f_{610}\left(s\right)$ (marked with circles) and $f_{987}\left(s\right)$ (marked with diamonds), and how they eventually start to move away from them. We see again that the point at which the roots of the golden polynomial start to move away from the roots of $f_{610}\left(s\right)$ and $f_{987}\left(s\right)$ is consistent with the theoretical prediction. Figure 4 shows stable roots of the lattice string approximation $f_{\mathrm{121,393}}\left(s\right)$, giving an impression of the quasiperiodic pattern on a larger scale. Observe how the roots constitute a slightly less regular pattern than the one in Figure 2. Furthermore, we note that the best lattice string approximation to the golden polynomial in [6,8] was determined from the convergent $4181/2584$ to the golden ratio ϕ.

Example 3.

Consider the nongeneric nonlattice Dirichlet polynomial

$$f\left(s\right)=1-(2^{-s}+3^{-s}+4^{-s})·{10}^{-1}-6^{-s}.$$

This example was inspired by the 2-3-4-6 polynomial

$$g\left(s\right)=1-2^{-s}-3^{-s}-4^{-s}-6^{-s}$$

from [8] (Section 3.7.1, pp. 113, 115–116), which is of the form (22), with $N=4$, $r=2^{-1}$, $m_1=m_2=m_3=1$, and ${\alpha }_2={log}_2\left(3\right)$, ${\alpha }_3=2$, ${\alpha }_4={\alpha }_2+1$. The LSA constant of $g\left(s\right)$ is of the order of ${10}^{-7}$, rendering the quasiperiodic pattern of its roots difficult to explore via the LSA algorithm.

By scaling the multiplicities $m_1$, $m_2$, $m_3$ by a factor of ${10}^{-1}$, we obtain the nongeneric nonlattice Dirichlet polynomial $f\left(s\right)$, with LSA constant $C=0.0001$, calculated by using the formula (23) in Theorem 3. As a result, we obtain a more tractable version of the 2-3-4-6 polynomial.

Table 4. This table shows simultaneous Diophantine approximations to the real number ${log}_2\left(3\right)$ associated to the nonlattice Dirichlet polynomial from Example 3, along with some specifications for the corresponding lattice string approximations.

$\mathit{f}\left(\mathit{s}\right)=1-(2^{-\mathit{s}}-3^{-\mathit{s}}-4^{-\mathit{s}})·{10}^{-1}-6^{-\mathit{s}}$		$\mathit{C}\approx 0.0001$
$\mathbf{Q},(\mathit{q},{\mathit{k}}_{\mathbf{2}})$	${\mathbf{p}}_{\mathit{q}}$	$\mathbf{\epsilon }\mathit{CQ}\mathbf{p}$
$\mathrm{192,530},(\mathrm{111,202};\mathrm{176,251})$	$1.00\times {10}^6$	$2.55\times {10}^6$
$\mathrm{189,140},(\mathrm{79,335};\mathrm{125,743})$	719,150	$1.78\times {10}^6$
$\mathrm{95,410},(\mathrm{31,867};\mathrm{50,508})$	288,865	$\mathrm{362,315}$
$\mathrm{38,096.3},(\mathrm{15,601};\mathrm{24,727})$	141,419	$\mathrm{70,825}<{\mathbf{p}}_{15601}$
$\mathrm{15,878.2},(665;1054)$	6028.04	$1258.27<{\mathbf{p}}_{665}$
$678.06,(306;485)$	2773.8	$24.72<{\mathbf{p}}_{306}$
$331.94,(53;84)$	480.43	$2.09<{\mathbf{p}}_{53}$

shows data for several lattice string approximations to $f\left(s\right)$, and just like for the 2-3 polynomial in Example 1, we generate lattice string approximations by approximating ${log}_2\left(3\right)$. We note, however, that they are not as good as the ones from Table 2 because the LSA constant is smaller. Figure 5 displays the roots of $f\left(s\right)$ moving away from the roots of $f_{306}\left(s\right)$. We again observe that the roots remain close to the roots of $f_{306}\left(s\right)$ near the two extreme vertical lines $\Re \left(z\right)=a$ and $\Re \left(z\right)=b$, as shown in parts (a) and (c) of Figure 5, respectively. However, we see in part (b) of Figure 5 some of the roots staying close to a third line, $\Re \left(z\right)=-0.0543$. Figure 6 shows one period of stable roots of the lattice string approximation $f_{\mathrm{111,202}}$, giving an impression of two distinct quasiperiodic patterns on each side of the vertical line $\Re \left(z\right)=-0.0543$. Note that while the part to the left is smaller than the part on the right, both parts consist of roughly the same number of roots, which may be inferred by observing that the roots in the left part seem to be more densely distributed than the ones in the right part.

4.3. Rank Three or More Examples

In this section, we discuss examples with rank greater than two, which make use of our implementation of the LLL algorithm. While the authors of [6,8] did show two examples with rank greater than two, specifically, the 2-3-5 polynomial of rank three from, e.g., [8] (Section 3.6, pp. 108–109) and the 2-3-5-7 polynomial of rank four from [8] (Section 3.7.1, pp. 113–114), the visual presentation of the roots was severely limited, due to the absence of tools like the LLL algorithm and MPSolve. Here, we plot the roots of the 2-3-5-7 polynomial, and also the roots of two new examples, all of which are of the form (22).

Recall that generating lattice string approximations to nonlattice Dirichlet polynomials with rank greater than two means generating simultaneous Diophantine approximations to two or more real numbers. The naive approach is to build off the process described in the second to last paragraph before Section 4.2.1, and simply generate a convergent to each irrational number and then find a common denominator. However, this process is extremely inefficient.

Example 4.

The 2-3-5-7 polynomial

$$f\left(s\right)=1-2^{-s}-3^{-s}-5^{-s}-7^{-s}$$

from [8] (Section 3.7.1, pp. 113–114) is a generic nonlattice example with rank four. It is of the form (22), with LSA constant $C=5.2\times {10}^{-9}$.

Table 5. This table shows simultaneous Diophantine approximations Q, $(q,k_2,k_3)$ to the real numbers ${log}_2\left(3\right)$, ${log}_2\left(5\right)$ associated to the nonlattice Dirichlet polynomial in Example 4, along with some specifications for their corresponding lattice string approximations.

$\mathit{f}\left(\mathit{s}\right)=1-2^{-\mathit{s}}-3^{-\mathit{s}}-5^{-\mathit{s}}-7^{-\mathit{s}}$		$\mathit{C}\approx 5.2\times {10}^{-9}$
$\mathbf{Q},(\mathit{q},{\mathit{k}}_{\mathbf{2}},{\mathit{k}}_{\mathbf{3}},{\mathit{k}}_{\mathbf{4}})$	${\mathbf{p}}_q$	$\mathbf{\epsilon }\mathit{CQ}\mathbf{p}$
$265.73,(\mathrm{103,169};\mathrm{163,519};\mathrm{239,551};\mathrm{289,632})$	$\mathrm{935,198}$	$0.13<{\mathbf{p}}_{103169}$
$75.19,(\mathrm{18,355};\mathrm{29,092};\mathrm{42,619};\mathrm{51,529})$	166,383	$0.006<{\mathbf{p}}_{18355}$
$39.53,(3125;4953;7256;8773)$	28,327.3	$0.0005<{\mathbf{p}}_{3125}$
$22.97,(441;699;1024;1238)$	3997.54	$4.8\times {10}^{-5}<{\mathbf{p}}_{441}$
$17.33,(171;271;397;480)$	1550.07	$1.40\times {10}^{-5}<{\mathbf{p}}_{171}$

shows the data for the lattice string approximations we computed, and we note that with such a small LSA constant, and because the LLL algorithm is not as efficient as the continued fraction process, we cannot even get a single lattice string approximation with roots that are stable for at least one period. Figure 7 and Figure 8 show the roots of each lattice string approximation from Table 5.

Example 5.

The 3-4-13 polynomial

$$f\left(s\right)=1-3^{-s}-4^{-s}-{13}^{-s}$$

is a generic nonlattice example with rank three. It is of the form (22), with LSA constant $C=0.0007$; see

Table 6. This table shows simultaneous Diophantine approximations Q, $(q,k_2,k_3)$ to the real numbers ${log}_3\left(4\right)$, ${log}_3\left(13\right)$ associated to the nonlattice Dirichlet polynomial in Example 5, along with some specifications for their corresponding lattice string approximations.

$\mathit{f}\left(\mathit{s}\right)=1-3^{-\mathit{s}}-4^{-\mathit{s}}-{13}^{-\mathit{s}}$		$\mathit{C}\approx 0.0007$
$\mathbf{Q},(\mathit{q},{\mathit{k}}_{\mathbf{2}},{\mathit{k}}_{\mathbf{3}})$	${\mathbf{p}}_q$	$\mathbf{\epsilon }\mathit{CQ}\mathbf{p}$
$1111.13,(\mathrm{85,248};\mathrm{107,571};\mathrm{199,030})$	$\mathrm{487,551}$	$\mathrm{39,943.5}<{\mathbf{p}}_{\mathrm{85,248}}$
$400.52,(7947;\mathrm{10,028};\mathrm{18,554})$	45,450.5	$1342.23<{\mathbf{p}}_{7947}$
$185.72,(4090;5161;9549)$	23,391.5	$320.33<{\mathbf{p}}_{4090}$
$75.38,(233;294;544)$	1332.57	$7.4<{\mathbf{p}}_{233}$

for the data on the lattice string approximations we computed. Figure 9 displays the roots of the lattice string approximation $f_{\mathrm{85,248}}\left(s\right)$. Observe how irregular the roots are, when compared to the other examples shown in the rest of Section 4. Furthermore, note the dense pocket of roots near the imaginary axis.

Example 6.

Let $a>0$ be an irrational number, and consider the nonlattice Dirichlet polynomial

$$f\left(s\right)=1-m_1{2}^{-s}-m_2{2}^{-{\alpha }_{2}s}-m_3{2}^{-{\alpha }_{3}s}-2^{-{\alpha }_{4}s},$$

where ${\alpha }_2>1$ is irrational, ${\alpha }_3={\alpha }_2+a$, and ${\alpha }_4={\alpha }_3+1$.

Choosing $m_1=m_2=m_3=0.10$, $a=1/\sqrt{100003}$, and ${\alpha }_2={log}_2\left(3\right)$, we obtain a nongeneric nonlattice Dirichlet polynomial of the form (22), with rank three and with LSA constant $C=0.002$; see

Table 7. This table shows simultaneous Diophantine approximations Q, $(q,k_2,k_3)$ to the real numbers ${log}_2\left(3\right)$ and ${log}_2\left(3\right)+a$ associated to the nonlattice Dirichlet polynomial in Example 6, along with some specifications for their corresponding lattice string approximations.

$\mathit{f}\left(\mathit{s}\right)=1-{\mathit{m}}_1{2}^{-\mathit{s}}-{\mathit{m}}_2{2}^{-{\mathit{\alpha }}_2\mathit{s}}-{\mathit{m}}_3{2}^{-{\mathit{\alpha }}_3\mathit{s}}-2^{-{\mathit{\alpha }}_4\mathit{s}}$		$\mathit{C}\approx 0.002$
$\mathbf{Q},(\mathit{q},{\mathit{k}}_{\mathbf{2}},{\mathit{k}}_{\mathbf{3}})$	${\mathbf{p}}_{\mathit{q}}$	$\mathbf{\epsilon }\mathit{CQ}\mathbf{p}$
$997.5,(\mathrm{100,562};\mathrm{159,387};318)$	$\mathrm{911,566}$	$\mathrm{252,396}<{\mathbf{p}}_{100562}$
$537.25,(\mathrm{46,803};\mathrm{74,181};148)$	424,256	$\mathrm{63,267}<{\mathbf{p}}_{46803}$
$283.56,(6956;\mathrm{11,025};22)$	63,054.2	$4962.89<{\mathbf{p}}_{6956}$
$172.10,(1583;2509;5)$	14,349	$685.48<{\mathbf{p}}_{1583}$
$55.32,(318;504;1)$	2882.58	$44.26<{\mathbf{p}}_{318}$

for data on the lattice string approximations we computed. Figure 10 shows plots of the roots of two lattice string approximations, giving a totally new large scale impression of the quasiperiodic pattern. Figure 11 shows the roots of lattice string approximations moving away from the roots of $f\left(s\right)$.

5. Concluding Remarks

We close this paper by a few comments concerning future research directions motivated, in part, by the present work and by earlier work in [8] (Chapter 3) (about the quasiperiodic patterns of the complex dimensions of nonlattice self-similar fractal strings), as well as by [15]. We limit ourselves here to a few questions concerning those matters.

While this is not a topic discussed in the present paper, it is worthwhile to mention that the LSA algorithm from [5,6,7,8] also establishes a deep connection to the theory of mathematical quasicrystals; for such quasicrystals, see, e.g., [15,25,26,27,28], and the relevant references therein. See also, especially, the open problem formulated in [8] (Problem 3.22, restated in Problem 1 below) asking to view the quasiperiodic set of complex dimensions of a nonlattice self-similar string (or, more generally, the set of zeros of a nonlattice Dirichlet polynomial) as a generalized mathematical quasicrystal; this problem was recently addressed by the third author in their Ph. D. thesis (see Chapter 4 of [29]), and it will be the topic of a future joint paper [30].

Problem 1.

([7] (p. 86), ref. [8] (Problem 3.22, p. 89)). Is there a natural way in which the quasiperiodic pattern of the sets of complex dimensions of nonlattice Dirichlet polynomials can be understood in terms of a notion of a suitable (generalized) quasicrystal or of an associated quasiperiodic tiling?

Generalized quasicrystals of complex dimensions also play an important role in a related, but significantly more general context, in the book by the first author, [15].

Aspects of Theorem 1 ([8] (Theorem 3.18, p. 84)) need to be refined. While this theorem is very helpful, in particular, for explaining when the roots of $f\left(s\right)$ start to move away from the roots of a lattice string approximation, it does not explain why they stay close near certain lines for much longer. This would suggest, among other things, that the density results and plots concerning the roots of nonlattice Dirichlet polynomials obtained in [8] (Section 3.6) can be improved, at least in certain cases.

Along similar lines, can we explain the observations made in Example 3 regarding the concentration of the roots near the extreme vertical lines $\Re \left(z\right)=a$ and $\Re \left(z\right)=b$, as well as near a third vertical line (here, the line $\Re \left(z\right)=-0.0543$); see, especially, Figure 5. How general is this phenomenon?

Another, rather puzzling, phenomenon is the appearance in both parts of Figure 10 (about Example 6) of very regular patterns and shapes. Can we find a good mathematical explanation for this new phenomenon? Furthermore, can we predict when related phenomena will arise and what types of shapes or patterns can be expected?

Based on the quasiperiodic patterns described in Section 4 of the present paper, it seems reasonable to expect that the patterns for the roots of a nonlattice Dirichlet polynomial exhibit the property of repetitivity often used to qualify one of the features of mathematical quasicrystals; see, e.g., [25,26,27,28], Appendix F of [15] and the relevant references therein. It would be interesting to precisely formulate and then prove the corresponding statement in our present situation, at least for a suitable class of nonlattice Dirichlet polynomials (and, in particular, of nonlattice self-similar fractal strings). One may also ask a similar question regarding the property of finite local complexity; for the latter geometric property, see, e.g., ibid, including [27] (Definition 1.2).

Understanding the diffraction measures and patterns of sets of roots of lattice and, eventually, of nonlattice, Dirichlet polynomials is the object of two papers in preparation by the authors ([30], along with its sequel). For now, our main result in this context, to be discussed in [30], concerns the lattice case. However, a conjecture of the first author, along with the LSA algorithm from [8] (described in Theorem 1 above), may likely provide a clue as to what the general nonlattice case should entail. The numerical and graphical results obtained in the present work should also be helpful in this endeavor.