The Spectrum of $\mathbb{Q}$-Isotropic Binary Quadratic Forms
Giorgos Kotsovolis


V^2A-Mark: Versatile Deep Visual-Audio Watermarking for Manipulation Localization and Copyright Protection
    
Xuanyu Zhang1,2, Youmin Xu1, Runyi Li1, Jiwen Yu1, Weiqi Li1, Zhipei Xu1, Jian Zhang1,2 

1 School of Electronic and Computer Engineering, Peking University

2 Peking University Shenzhen Graduate School-Rabbitpre AIGC Joint Research Laboratory

    April 29, 2024
=========================================================================================================================================================================================================================================================


    We give a complete list of the points in the spectrum 
    𝒵={inf_(x,y)∈Λ,xy≠0| xy|, Λ is a unimodular rational lattice of ^2}
 above 1/3. We further show that the set of limit points of 𝒵 with values larger than 1/3, is equal to the set {2m/√(9m^2-4)+3m, where m is a Markoff number}. 



§ INTRODUCTION

For a lattice Λ⊂^2 of covolume 1, we define 
    λ_1(Λ)=inf_(x,y)∈Λ\0| xy|.
 The set of values that λ_1 assumes as Λ varies through the unimodular lattices of ^2 is the well studied Markoff spectrum ℳ and could be interpreted (after some renormalization) as the set of first eigenvalues, when the operator D=xy acts on the orthogonal complement of the constant functions inside L(^2/Λ) (See <cit.> for details). The points inside ℳ⋂ (1/3,∞), were classified by Markoff (<cit.>,<cit.>), who parametrized them by the Markoff numbers; natural numbers that are solutions of the cubic equation 
    x^2+y^2+z^2=3xyz.
 When all the vectors of the lattice Λ lie in √(d_Λ)·^2, for some positive rational constant d_Λ, we trivially have that λ_1(Λ)=0. We shall refer to these lattices as rational. In this paper, we study the distribution of the first non-zero eigenvalue of such tori; we define 
    λ^*_1(Λ)=inf_(x,y)∈Λ, xy≠0| xy|
 and we wish to understand the set 
    𝒵={λ_1^*(Λ), Λ is a unimodular rational lattice of ^2}.
 This spectral problem first appears, in a different form as we discuss in Section <ref>, in the work of Zaremba (<cit.>,<cit.>), who was interested in numerical approximation of double integrals and, following Hlawka <cit.>, understood that determining the higher values of these numbers could have applications in bounding the error term of such numerical approximations. Zaremba essentially showed that  
    𝒵={min_q∈ℕ,0<q<bq||qa/b||, a/b∈}
 and hence we denote by 𝒵, both the spectrum and the function 
    𝒵:a/b→min_q∈ℕ,0<q<bq||qa/b||,
 for some rational a/b∈ with (a,b)=1. There is a clear connection between the 𝒵 spectrum and the notorious Zaremba conjecture, which can be interpreted as follows, in terms of the function 𝒵: 

    There exists some absolute positive constant C, such that for every b∈ℕ, there exists a∈ℕ such that 𝒵(a/b)>C.
 Zaremba considered the largest values that the function 𝒵 attains and proved that the largest points of the spectrum are the points F_n-2/F_n, where F_n is the Fibonacci sequence. The rational numbers that attain the value F_n-2/F_n are F_n-1/F_n and F_n-2/F_n . He proceeded to show that the first point that lies outside this sequence is equal to 10/29, but to our knowledge his investigation of the spectrum ended there. We give a complete description of all points of 𝒵∩ (1/3,∞). The classification of these points will be achieved in Section <ref>. For now we state the following result regarding the limit points of 𝒵 larger than 1/3: 


    Let m denote a Markoff number. Then 
    2m/√(9m^2-4)+3m
 is a limit point of 𝒵∩ (1/3,∞). Furthermore, these are all the limit points in 𝒵 larger than 1/3.

We further prove the following regarding the distribution of the limit points of 𝒵 below 1/3:

    For every ϵ>0, there exist uncountably many limit points of 𝒵 in (1/3-ϵ,1/3).



§ EQUIVALENT DEFINITIONS OF THE 𝒵 SPECTRUM


Let p>1 denote some natural number and g=(g_1,g_2) some non-zero integer vector in ^2 coprime to p. Zaremba's considerations regarding good bounds for the numerical computation of double integrals led him to consider integer lattices of the form 
    Λ_p,g={(u,v)∈^2: ug_1+vg_2≡ 0 p},
 calling a vector g “good" if the quantity p^-1inf_(u,v)∈Λ_p,g,uv≠ 0| uv| is large. It is clear that Λ_p,g has volume p and thus Λ'_p,g=1/√(p)Λ_p,g is a unimodular rational lattice with 
    λ_1^*(Λ'_p,g)=p^-1inf_(u,v)∈Λ_p,g,uv≠ 0| uv|.
 Our definition of the 𝒵-spectrum should now be clear. However, we give another equivalent definition in the language of continued fractions, which shall be fruitful for our considerations: For every unimodular rational lattice Λ, there exists by definition some rational number d such that (c,a),(0,b) is a basis of the integral lattice 1/√(d)Λ. Since Λ is unimodular, we must have bc=d. Then 
    λ_1^*(Λ)=inf_q,l,qc(qa+lb)≠0| d^-1qc(qa+lb) |=inf_q,l,qc(qa+lb)≠0| q(qa/b+l) |=min_q∈ℕ:0<q<bq||qa/b||,
 and hence 
    𝒵={min_q∈ℕ,0<q<bq||qa/b||, a/b∈}.
 Now, by a theorem of Perron (<cit.>), we have that 
    min_q∈ℕ:0<q<bq||qa/b||=1/max_1≤ i≤ n([a_i,a_i+1,...,a_n]+[0;a_i-1,a_i-2,...,a_1]),
 where a/b=[a_0;a_1,a_2,...,a_n] is its continued fraction expansion.


§ EARLY CONSIDERATIONS OF ADMISSIBLE CONFIGURATIONS

Let ρ denote some rational number with continued fraction expansion [a_0;a_1,a_2,...,a_n]. The chain T=[a_1a_2...a_n] will be the chain associated to ρ and conversely we associate to a chain [a_1a_2,...a_n] the rational number equal to ρ_T=[0;a_1,...,a_n]. We shall be using T and ρ interchangably. Since 
    𝒵^-1(ρ)=max_i∈{1,...,n}([a_i;a_i+1,...,a_n]+[0;a_i-1,...,a_1]),
 if T contains some number larger than 2, we clearly have 𝒵^-1(ρ)≥3. We call the rational numbers ρ satisfying 𝒵(ρ)>1/3 and their corresponding chains admissible. Hence, from now on we assume that the continued fraction sequence of ρ is composed only of 1's and 2's. Markoff proved his celebrated theorem by first analyzing the properties of admissible chains. The main difference from our point of view is that one has to consider finite chains as opposed to the Markoff spectrum. However, more or less the following lemmata or variants of theirs can be found in textbooks with a standard treatment of the Markoff spectrum above 1/3. See for example <cit.>, <cit.>, <cit.>. We include their proofs for the convenience of the reader.

 
    If T contains the chain [121], then 𝒵(T)≤1/3.


    If T contains the chain [121], then we have be definition 
    𝒵^-1(T)≥ [2;1,1]+[0;1,1]=3.


Notice that a chain of the form [a_1a_2...a_n2] corresponds to the same rational number as the chain [a_1a_2,...,a_n11] and hence we identify these chains. Furthermore, because of the identity 𝒵(a/b)=𝒵(1-a/b), we also identify the chains [11a_1a_2,...a_n] and [2a_1a_2...a_n]. We make the following convention: 
 

Convention: By the identifications above, we will assume from now on that every chain starts and ends with an even number of 2's. This number is allowed to be zero.
 
    If T contains the chain [212] and is not equal to [11111], then 𝒵(T)≤1/3.


    If T is not equal to [11111], then T contains the chain [212], which can be extended inside T. If it is extended by a 1, this contradicts Lemma <ref>. If it is extended by a 2, we have that T contains the chain [2212] or the chain [2122]. In either case, 
    𝒵^-1(T)≥ [2;1,2]+[0;2,1]=3.


For some finite chain T, define T^* to be its reverse chain. A section of T is by definition an ordered pair of finite chains R,S such that [T]=[RS]. We define 𝒵(R| S)=1/ρ_R^*+1/ρ_S.

    𝒵(S^*11|22S)=1/3.


    This is simply a restatement of the identity 
    [0;2,x]+[0;1,1,x]=1.


 By definition, 𝒵(T) is equal to the minimum 𝒵(R| S) as (R,S) ranges over all of its sections. It is clear now that we have the following identity 
    𝒵(T)=𝒵(T^*).
 
 
 We define the following ordering between chains: 
    [T_1]<[T_2]ρ_T_1>ρ_T_2.

 

    If T has the section (R^*1122S) and 𝒵(T)>1/3 then [S]<[R].


    This is a direct corollary of Lemma <ref> combined with monotonicity properties of continued fractions.



    If T=[1^e^1_12^e^2_11^e^1_22^e^2_2...1^e^1_n2^e^2_n], where e^j_i are positive integers, except possibly e^1_1 and e^2_n which are allowed to be 0, then all e^j_i are even or T consists only of 1's or only of 2's.


    Assume that T contains an odd power of 1. We then have a section of either T or T^* of the form [R^*1^l| 2^m 1^n S], where l is odd, m≥ 1 and n is allowed to be zero. If l=1, then either R=∅, which forces T to consist only of 1's, or R≠∅ and we have a contradiction by Lemma <ref>. By the convention and the fact that we cannot have a subchain of the form [121], m≥ 2. Hence by Lemma <ref>, we have 
    [2^m-21^nS]<[1^l-2R].
 This forces m to be equal to 2 and n≤ l-2 to be odd. Considering the section [S^*1^n| 2^m1^lR] of T^*, we have that l≤ n-2 in a similar manner- a contradiction. Therefore, 1 appears only in even clusters. Similar considerations regarding the clusters of 2 conclude the proof of the lemma.


From now on we assume that our chain does not consist only of 1's or only of 2's. These chains are already trivially known to be admissible. Since 1's and 2's appear in even clusters, we will from now own be denoting a=[22] and b=[11], following Bombieri (<cit.>). 

    With the notation of Lemma <ref>, for either j=1 or j=2, 
    e^j_i≤ 2
 for all i.


Suppose that this is not the case. Then there exists at least one subchain of the form [b^e(ab)^ka^f] with e,f≥ 2. Consider k minimal such that a subchain of that form exists. Then for some chains R,S T has a section of the form [R^*b^e(ab)^k-1ab| aa^f-1S]. By Lemma <ref>, 
    [a^f-1S]<[a(ba)^k-1b^eR].
 Hence, f=2 and S must start with (ba)^k'b^s_1, where k'≤ k-1 and s_1≥ 2, which is absurd by minimality of k.




§ NIELSEN MOVES ON FINITE WORDS

Regarding the start and ending of admissible chains we have the following:

    If 𝒵(T)>1/3, then T starts and ends with b.


    Assume that T ends with a. Then T has a section of the form [R^*b^sa^kb^m-1b| aa^l-1], where m≥ 1 and l≥ 2, since if l=1, the chain ends in [122], which by our identification is the same as [1211], which is absurd by Lemma <ref>. By Lemma <ref> 
    [a^l-1]<[b^m-1a^kb^sR]
 and therefore we must have m=1, k≤ l-1, s=0, R=∅ and thus T=[a^kba^l] with k<l. Symmetrically, we obtain l<k, which is a contradiction.

By Lemma <ref> and Lemma <ref>, an admissible T can have one of the following two forms: 
    
  * Type I: b^e_1ab^e_2a...ab^e_n or
    
  * Type II: ba^e_1ba^e_2...a^e_nb.


In either case, we call (e_1,e_2,...,e_n) the characteristic sequence of T. Let A denote the set of admissible words. For a word on the letters a and b, the Nielsen moves U and V are classically defined as: 
    U:a→ ab, b→ b
 and 
    V:a→ a, b→ ab.
 The Nielsen moves are automorphisms of the free group F_2=⟨ a,b⟩ and every automorphism of the free group can be constructed as a word on the autoprhisms U,V and their inverses. When dealing with finite words, it will become apparent that we have to “correct" the definition of Nielsen moves, so that we respect the admissibility property of our chains. We define the variants of U and V on A, which we shall call U and V as follows. For T∈ A, 
    U(T)=bU(T) and V(T)=a^-1V(T).
 Notice that V is well defined since V(T) always starts with an isolated copy of a. In the next proposition we shall show that U and V fix A and furthermore, U is invertible on words of Type II and V is invertible on words of Type I. We will be referring to these adjusted Nielsen moves as A-Nielsen moves. We prove:


    
    𝒵(T)>1/3𝒵(U(T))>1/3
 and similarly 
    𝒵(T)>1/3𝒵(V(T))>1/3.



    T is either of Type I or II. Suppose that T is Type II, since the proof is identical in both cases. We can hence write T=[ba^e_1...a^e_nb]. By Lemma <ref> and standard monotonicity properties of continued fractions, T is admissible if and only if 
    (e_i-1,e_i+1,...,e_n,∞)<(e_i-1,e_i-2,...,e_1,∞)
 for i=2,3,4,...,n in the lexicographic ordering and the same holds for T^*. Notice that the move V simply increases all the e_i's by 1 and hence the equivalance is clear. As for the move U, U(T) will be Type I and by Lemma <ref>, U(T) is admissible if and only if 
    (e'_i-1,e'_i+1,...,e'_k,1,1,1,...)<(e'_i-1,e'_i-2,...,e'_1,1,1,1,...),
 where {e'_i}_i=1^k is the characteristic sequence of U(T) and the same holds for U(T)^*. However, notice that the characteristic sequence of  U(T) is equal to 
    (2,1,1,...,1_e_1-1,2,1,1,...,1_e_2-1,...,1,1,...,1_e_n-1,2),
 from which the equivalence follows. Working similarly with U(T)^* concludes the proof of the lemma.

The following theorem classifies all admissible chains.

Let T some chain that does not consist only of 1's or only of 2's. Then, T is admissible if and only if there exists a finite word Ψ in the A-Nielsen moves U and V and some k∈ℕ such that 
    T=Ψ(b(ab)^k).



    The reverse dirertion is clear by Proposition <ref>  since T=b(ab)^k is admissible, as one can deduce by Lemma <ref>. For the other direction, we induct on the length  N(T) of the word T in the letters a and b. If N(T)=3, then we must have T=bab. Notice now that N(U(T))>N(T) and  N(V(T))>N(T). Hence, according to whether T is Type I or II, we can apply U^-1 or  V^-1 accordingly and decrease the length of the word. Say T is of Type I. By induction, V^-1(T)=Ψ((b(ab)^k)) for some word Ψ on U and V. Defining Ψ'=U·Ψ concludes the proof of the theorem.

After classifying all possible admissible chains, we wish to understand their corresponding 𝒵 function, or equivalently their minimal splitting.
 
For a word of Nielsen moves Ψ, we have that 
    Ψ([ab])=awb,
 where w is symmetric. 


    Fix k. We induct on the length of Ψ. If N(Ψ)=0, the result clearly holds. Assume, it holds for Ψ. Then U(Ψ([ab]))=U(awb)=abU(w)b. However, 
    bU(w)=bU(w^*)=bb^-1(U(w))^*b=(bU(w))^*,
 and hence bU(w) is symmetric. With similar cosiderations for VΨ, we conclude the result.


The following proposition will essentially give us our minimal splitting for Ψ(b(ab)^k).


    Let Ψ a word on the Nielsen moves U,V and let Ψ denote the corresponding word on the A-Nielsen moves. Then, there is a unique section Π_1Π_2 of Ψ(ab) such that Π_1,Π_2  are symmetric. We then have 
    Ψ(b(ab)^k)=[Π_2Π_1Π_2...Π_1Π_2_k]
 


    Fix k. We use induction on the length of the word Ψ, or equivalently the length of the word Ψ. If N(Ψ)=0, then Π_1=a and Π_2=b. Now suppose the theorem holds for all Ψ with N(Ψ)<t. Let Ψ have length t. Suppose the first letter of Ψ is U without loss of generality. Then U^-1Ψ has length t-1, and therefore we can uniquely write U^-1Ψ(ab)=Π_1Π_2 and U^-1Ψ(b(ab)^k)=[Π_2Π_1Π_2...Π_1Π_2_k]. Define Π'_1=U(Π_1)b^-1 and Π'_2=bU(Π_2) and notice that the section Π'_1Π'_2 satisfies the wanted properties. As for uniqueness, assume that we can write Ψ(ab)=Π”_1Π”_2, where 
        
  * Π”_1 is symmetric and starts and ends with a
        
  * Π”_2 is symmetric and starts and ends with b.
      Then 
    U^-1Ψ(ab)=U^-1(Π”_1b)U^-1(b^-1Π”_2).
  By induction, 
    U^-1(Π”_1b)=U^-1(Π'_1b) and U^-1(b^-1Π”_2)=U^-1(b^-1Π'_2),
 from which uniqueness follows.


We shall refer to this unique section of Ψ(ab) as the symmetric section. We have proved that every admissible word has the form [Π_2Π_1Π_2...Π_1Π_2_k], where Π_1Π_2 is the symmetric section of Ψ(ab). The next lemma will be our main ingredient for finding the minimal section of Ψ(b(ab)^k).

 
    Let Ψ some finite Nielsen word. Write 
    Ψ(ab)=a^e_1ba^e_2...a^e_nb,
 if α is of Type I and 
    Ψ(ab)=ab^e_1ab^e_2...ab^e_n,
 if α is of Type II. 
 
 We then have 
    (e_1,e_2,e_3,...,e_n,∞)>(e_i,e_i+1,...,e_n,∞)
 and 
    (e_n,e_n-1,e_n-2,...,e_1,∞)<(e_n-i+1,e_n-i,...,e_1,∞),
 for all i∈{2,...,n}, if α is of Type I and 
    (e_1,e_2,e_3,...,e_n,1,1,...)<(e_i,e_i+1,...,e_n,1,1,..),
 and 
    (e_n,e_n-1,e_n-2,...,e_1,1,1,..)>(e_n-i+1,e_n-i,...,e_1,1,1,..),
 for all i∈{2,...,n}, if α is of Type II. The ordering here is lexicographic.
    



The assertion is clear for the empty Nielsen word. Assume it is true for all Nielsen words up to length N. Then for some word of length N, say of Type I, of the form a^e_1ba^e_2...a^e_nb, we have that 
    V(a^e_1ba^e_2...a^e_nb)=a^e_1+1ba^e_2+1...a^e_n+1b,
 and the conclusion follows. On the other hand, the word U(a^e_1ba^e_2...a^e_nb) is now of Type II with sequence of exponents equal to 
    (1,1,...,1_e_1-1,2,1,1,...,1_e_2-1,...,1,1,...,1_e_n-1,2).
 



   Let Ψ some Nielsen word in a=(2,2) and b=(1,1). For some positive integer k, let r^Ψ_k the rational number with corresponding chain [Π_2Π_1Π_2...Π_1Π_2_k], where Π=Π_1Π_2 is the unique symmetric section of Ψ(ab). Then 
   
    𝒵(r^Ψ_k)=([Π]+1/[Π_2ΠΠ···Π_k-1 times])^-1.
 
    
    
    

     Let Q| P denote a section of r^Ψ_k such that 𝒵(r^Ψ_k)=𝒵(Q| P). By Lemma <ref>, we know that Q=Π_2ΠΠ···Π_s times and  P=ΠΠ···Π_k-s times. However, since Π has even length in 1 and 2 we get by standard continued fraction theory that since P and Q are even, ρ_P+1/ρ_Q is maximized for s=k-1 and therefore 
    𝒵(r^Ψ_k)=([Π]+1/[Π_2ΠΠ···Π_k-1 times])^-1.



By putting together the points constructed in Theorem <ref>, the chains that consist only of 1's and the chains that consist only of 2's, we have  found all the points inside 𝒵∩ (1/3,∞):



   𝒵⋂ (1/3,∞] is equal to 
    {𝒵(r^Ψ_k),Ψ is a Nielsen word and k∈ℕ}∪{F_n-2/F_n,n≥ 2}∪{(1/2+[2;2,2,...,2_n])^-1,n≥ 0}.
 




§ LIMIT POINTS OF 𝒵∩ (1/3,∞) AND LIMIT POINTS OF 𝒵∩ (1/3-Ε,1/3).


Notice that if k_i is some sequence of positive integers and Ψ_i is a sequence of Nielsen words on U and V satisfying N(Ψ_i)→∞, then by Lemma <ref> 
    𝒵(r_k_i^Ψ_i)→1/3.
 Hence, in order to study the limit points of 𝒵 larger than 1/3, we have to understand for a fixed Ψ the limits lim_n→∞𝒵(r_n^Ψ).  
 
 
To a continued fraction of a rational number ρ of the form [0;a_1,a_2,...,a_n] with n even, we associate the matrix 
    M_ρ=[ a_1   1;   1   0 ]·[ a_2   1;   1   0 ]···[ a_n   1;   1   0 ].

Markoff showed that the triple
    (Tr(Ψ(a))/3,Tr(Ψ(b))/3,Tr(Ψ(ab))/3)
 is a solution (x,y,z) of the Markoff equation, with no two entries sharing a common prime factor. He further showed, that M_Ψ(ab) has the following form: 

    M_Ψ(ab)=[ 3z-z'     *;     z    z' ],
 where z' is the unique integer solution of the equation 
    x+yz'≡ 0 z and 0<z'<z.



By Theorem <ref> and the argument in the beginning of the section, all the limit points of 𝒵 larger than 1/3 are of the form: 

    
  * 1/(1+√(5)/2)^2,
    
  * 2/(1+√(2))^2,
    
  * 1/[Π_2Π]^-1+[Π], where here Π denotes the periodization of Π and Π=Π_1Π_2 denotes the symmetric splitting of Ψ(ab) for some Nielsen word Ψ. 


We know by definition of the matrix M_Ψ(ab) that [Π]=3z-z'/z and that [Π_2Π]^-1 is equal to  
    (3z-z')-z'-√(9z^2-4)/2z.
 Therefore, 
    1/[Π_2Π]^-1+[Π]=1/-(3z-2z')-√(9z^2-4)/2z+3z-z'/z=1/√(9z^2-4)/2z+3/2.



We now prove Theorem <ref>, showing that below the point 1/3, we can find uncountably many limit points as close as we desire:

:
    For any finite sequence of positive integers n_1,n_2,...,n_k define 
    R(n_1,n_2,...,n_k)=[0;1,1,...,1_n_1,2,2,1,1,...,1_n_2,2,2,...,2,2,1,1,...,1_n_k]

    Clearly by Lemma <ref>, there exists some N_0, such that for any n_1,n_2,...,n_k≥ N_0: 
    𝒵(R(n_1,n_2,...,n_k))>1/3-ϵ.
 Choose now n_1 to be odd. By the description of all the points in the spectrum above 1/3, we know that 𝒵(R(n_1,n_2,...,n_k))≤1/3 and by picking n_1< n_i for all i∈{2,3,...,k} we can make the inequality strict. We conclude that 
    𝒵(R(n_1,n_2,...,n_k))∈(1/3-ϵ,1/3).


    Choose n_2 even such that n_i<n_2 for all i∈{1,3,...,k}. Then, we can see the maximal section is  
    [1,1,...,1_n_1|2,2,1,1,...,1_n_2,2,2,...,2,2,1,1,...,1_n_k],
 and 
    𝒵(R(n_1,n_2,...,n_k))=1/[2;2,1,1,...,1_n_2,2,2,...,2,2,1,1,...,1_n_k]+[0;1,1,...,1_n_1].
 It is clear now that by choosing (n_3,n_4,...,n_k)  in the range (n_1,n_2) and taking k→∞, we can construct uncountably many limit points of the form 
    lim_k→∞1/[2;2,1,1,...,1_n_2,2,2,...,2,2,1,1,...,1_n_k,...]+[0;1,1,...,1_n_1].







§ ACKNOWLEDGEMENTS

I wish to thank my advisor Peter Sarnak for suggesting this problem to me and for many useful remarks on earlier drafts of this paper. 



abbrv



