Extension and restriction principles for the HRT conjecture
Kasso A. Okoudjou







Kasso A. Okoudjou

Department of Mathematics & Norbert Wiener Center

University of Maryland

College Park, MD, 20742 USA

kasso@math.umd.edu
This work  was partially supported by a grant from the Simons Foundation # 319197, and ARO grant W911NF1610008. Part of this material is based upon work supported by the National Science Foundation under Grant No. DMS-1440140 while the author was in residence at the Mathematical Sciences Research Institute in Berkeley, California, during the Spring 2017 semester.

[2000]Primary 42C15; Secondary 42C40











The HRT (Heil-Ramanathan-Topiwala)  conjecture asks whether a finite collection of time-frequency shifts of a  non-zero square integrable function on   is linearly independent. This longstanding conjecture remains largely open even in the case when the function is assumed to be smooth. Nonetheless, the conjecture has been proved for some special families of functions and/or special sets of points. The main contribution of this paper is an inductive approach to investigate the HRT conjecture  based on the following. Suppose that the HRT is true for a given set of N points and a given function. We identify  the set of all  new points such that the conjecture remains true for the same function and the set of N+1 points obtained  by adding one of these new points to the original set. To achieve this we introduce a real-valued function whose global maximizers describe when the HRT is true. To motivate this new approach we re-derive a special case of the HRT for sets of 3 points. Subsequently, we establish   new results for points in (1,n) configurations, and for a family of symmetric (2,3) configurations. Furthermore, we use these results and the refinements of other known ones  to prove that the HRT holds for certain families of 4 points. 



Extension and restriction principles for the HRT conjecture
    Kasso A. Okoudjou
    December 30, 2023
===========================================================

myheadings plain
K. A. OKOUDJOUEXTENSION PRINCIPLE FOR THE HRT









§ INTRODUCTION


 For a, b ∈  and a function g defined on , let M_bf(x)=e^2π i bxf(x) and T_af(x)=f(x-a)  be  respectively  the modulation operator, and the translation operator.   Given a function g∈ L^2()
 and Λ={(a_k, b_k)}_k=1^N⊂^2, we define 
    𝒢(g, Λ)={e^2π i b_k ·g(· - a_k)}_k=1^N.
 𝒢(g, Λ) is called a (finite) Weyl-Heisenberg or Gabor system <cit.>. The HRT conjecture <cit.>, states that 


Given any 0≠ g ∈ L^2()  and Λ={(a_k, b_k)}_k=1^N⊂^2, 𝒢(g, Λ) is a linearly independent set in L^2().


To date a definitive answer to the Conjecture has not been given even  when one assumes that the function g is very smooth and decays fast, e.g., when g ∈ S(), the space of Schwartz functions on . In particular, the following (sub-conjecture) is also open



Given any g ∈ S(), g≠ 0  and Λ={(a_k, b_k)}_k=1^N⊂^2, 𝒢(g, Λ) is a linearly independent set in L^2().

 While the statement of the problem seems simple, a variety of sophisticated tools such as the ergodic theorems, von Neumann algebra methods, number theory arguments, random Schrödinger operators,  harmonic analysis, operator theory, has  been used to prove the few known results.  Perhaps the lack of unifying theme in the proofs of the known results attests to  the difficulty of this problem.
 
  The HRT conjecture contains two fundamental data: the function g ∈ L^2() and the set of points Λ={ (a_k, b_k)}_k=1^N ⊂^2. Most of the known results either assume g ∈ L^2 and Λ is restricted to some special family of points, or that Λ is very general and restrictions are imposed on g.  We outline all the known results about the HRT conjecture of which we are aware and we refer to the surveys  <cit.> for more details. 


 The following statements hold.


  (i) Conjecture <ref> holds for any Λ⊂^2, when g is compactly supported, or just supported within a half-interval (-∞, a], or [a, ∞) <cit.>.

  (ii) Conjecture <ref> holds for any Λ⊂^2, when g(x)=p(x)e^-π x^2 where p is a polynomial <cit.>.

  (iii) Conjecture <ref> holds for any g ∈ L^2(), when Λ is a finite set with  Λ⊂ A(^2) + z where A is a full rank 2× 2 matrix and z∈^2 <cit.>. In particular, Conjecture <ref> holds when #Λ≤ 3 for any g ∈ L^2 <cit.>.

  (iv) Conjecture <ref> holds for any g ∈ L^2, when #Λ =4 and two of the four points in Λ lie on a line and the remaining two points lie on a second parallel line <cit.>.

  (v) Conjecture <ref> holds for any g ∈ S(), when #Λ =4 and three  of the four points in Λ  lie on a line and the fourth point is off this line  <cit.>.

  (vi) Conjecture <ref> holds for any Λ⊂^2, when lim_x →∞|g(x)|e^cx^2=0 for all c>0 <cit.>. 

  (vii) Conjecture <ref> holds for any Λ⊂^2, when lim_x →∞|g(x)|e^cxlog x=0 for all c>0 <cit.>. 

  (viii) Conjecture <ref> holds when g is ultimately positive, and  Λ ={(a_k, b_k)}_k=1^N ⊂^2 is such that {b_k}_k=1^N are independent over the rationals  <cit.>. 

  (ix) Conjecture <ref> holds for any #Λ =4, when g is ultimately positive, and g(x) and g(-x) are ultimately decreasing <cit.>.  

  (x) Conjecture <ref> holds for any g ∈ L^2(), when Λ consists of collinear points <cit.>.

  (xi) Conjecture <ref> holds for any g ∈ L^2(), when Λ consists of N-1 collinear and equi-spaced  points, with the last point located off this line <cit.>.




We note that there is some redundancy in Proposition <ref> as part (vii) implies parts (i), (ii), and (vi). Nonetheless, we include all these results to give an historical perspective on the HRT conjecture.  In addition to these,  perturbation arguments <cit.> have  been used on either the function g or the set Λ to get related results. A spectral result related to the HRT  has been presented in <cit.>,  and estimates of frame bounds for Gabor systems related to the HRT conjecture have appeared in <cit.>. A connection between the HRT, the Bargmann-Fock space and the Segal-Bargmann transform was presented in <cit.>.  Other results concerning the HRT can be found in <cit.>, and  for an overview of the status of the conjecture we refer to <cit.>. When g ∈ L^2(^d), d≥ 2,  and Λ⊂^2d not much is known about the conjecture, see <cit.>. We refer  to <cit.> for a related problem for pure translation systems, and to <cit.> for some generalizations of the conjecture. 


A set Λ  of the form given in (iv) or (v) of Proposition <ref>, is referred to as a (2,2) configuration  and (1,3) configuration, respectively. More generally, 

An (n, m) configuration is a collection of n+m distinct points in the plane, such that there exist 2 distinct parallel lines such that one of them contains exactly n of the points and the other one contains exactly m of the points. 




One of the goals of this paper is to present two different approaches to investigate the HRT conjecture. On the one hand, we prove  an extension principle and use it to attack the HRT conjecture.  No such extension or other inductive methods related to the HRT have ever been proved. More specifically, knowing that the Conjecture holds for a given function g ∈ L^2() and a given set Λ={(a_k, b_k)}_k=1^N⊂^2, we identify the set of all (new) points (a, b) ∈^2 ∖Λ such that the conjecture remains true for the same function g and the new set Λ'=Λ∪{(a,b)}. On the other hand, we consider the related restriction principle which asks the following question; knowing that the HRT is true for a specific set of N+1 points and g, can one establish the conjecture for a family of N related points and the same function g? 
To answer these questions we introduce a real-valued function that is generated by the two data in the HRT conjecture, namely, the function g and the set Λ. As we shall show, this function is derived from the Gramian of 𝒢(g, Λ) and is based on a fundamental time-frequency analysis tool: the short-time Fourier transform. Using this function along with  refinements of some of the techniques introduced by Demeter in <cit.> allow us to recover some known results and  establish new ones. In particular, the main contributions of this paper are: ∙ a proof that  HRT conjecture holds for all (1,3) configurations when g is real-valued, ∙ a proof that HRT holds for a family of symmetric (2,3) configurations, ∙ a proof that HRT holds for  a large family of 4 points (not in (1,3) nor (2,2) configurations) and real-valued functions in L^2().

Furthermore, as a byproduct of our approach we obtain:∙  a new proof of HRT for collinear points, ∙ a new proof of HRT for sets of 3 unit-lattice points and real-valued functions.

The rest of the paper is organized as follows. In Section <ref>, we introduce some of the technical tools needed to state our results. We then use Bochner's theorem to provide a new proof of the HRT conjecture for collinear points (Theorem <ref>). We also motivate the extension principle by offering a new proof of the HRT conjecture for 3 points on the unit lattice and real-valued functions  (Proposition <ref>). 
In Section <ref> we  introduce and collect the main properties of the extension function which is the basis of the extension principle we propose. Subsequently, we prove in Section <ref> that there exists  at most one (equivalence class of) (1,n) configuration for which the HRT conjecture could fail whenever n≥ 3 (Theorem <ref>). Furthermore, when the generator is real-valued we show that   the HRT holds for all (1,3) configurations (Theorem <ref>). In Section <ref> we introduce the restriction principle. For this case, we refine Demeter's “conjugate trick” argument to establish both Conjecture <ref> (Theorem <ref>) and  Conjecture <ref> (Theorem <ref>) for a family of symmetric (2,3) configurations.  Subsequently, we apply the restriction principle to  prove Conjecture <ref> for real-valued functions and a related family of 4 points that are not  (1,3) nor (2,2) configurations (Corollary <ref>).















§ PRELIMINARIES AND MOTIVATION

In this section, we collect some properties of the Short-Time Fourier Transform
(STFT)  as  well as some results concerning positive definite matrices, see Section <ref>. Using the Gramian of 𝒢(g, Λ) and Bochner's theorem we then give a new proof of the HRT conjecture for collinear points, see Section <ref>. Finally, in Section <ref> we revisit the HRT for 3 points and provide a new proof of the validity of the conjecture in this case. This new proof serves as a motivation for the extension principle that we propose. The methodology we develop below is fundamentally based on the analysis of the Gramian of 𝒢(g, Λ). In particular, the notions of positive definiteness of functions and matrices constitute the overarching themes of this methodology.


 §.§ Preliminaries



Let f, g  ∈ L^2(). The Short-Time Fourier Transform
(STFT) of a function f with respect to a window g is

    V_g f(x, y)=∫_ f(t) g(t-x)  e^-2π i y  t  dt.

It is easy to prove that V_g f is 
a  bounded  uniformly continuous function on ^2, and that 
    lim_|x|, |y|→∞V_gf(x, y)=0;
see
 <cit.>. We will also need the following the orthogonality and covariance properties of the STFT:
given g_i, f_i, ∈ L^2(), i=1, 2, we have 

    V_g_1f_1V_g_2f_2=f_1f_2g_1g_2,
 and 

    V_g(T_aM_bf)(x, y)=e^-2π i ayV_gf(x-a, y-b),
 see <cit.>, and <cit.>.

We will also use the following formula whenever it is well defined: 

    ℱ_2(V_g_1f_1 V_g_2f_2)(ξ, η) = (V_f_2f_1 V_g_2g_1)(-η, ξ),
 where ℱ_2 denotes the two dimensional Fourier transform. We refer to <cit.> for a proof of this statement. 

We need some facts about positive definite matrices. We refer to <cit.> for details. In particular, given N × N Hermitian matrices A, and B, we write A ≻ B if A-B is positive definite. We will repeatedly use the following theorem.

<cit.> 
Let E be  an Hermitian N × N matrix such that 
    E=[   A   B; B^*   C ],
 where A, C are square matrices. Then, E is positive definite if and only if A is positive definite and C≻ B^*A^-1B. 


In our setting,  
    E=(f_kf_ℓ)_k, ℓ=1^N
will be the Gramian of a set of N functions {f_k}_k=1^N ⊂ L^2(). As a consequence, E is automatically positive semidefinite, i.e.,  E≽ 0. Furthermore, A and C will always be positive definite matrices. In particular, we will consider the case where A is an (N-1)× (N-1) positive definite matrix, C=1, and B=u will be a vector in ^N-1. In this case we will make repeated use of the following corollary of Theorem <ref>.

 With the above notations the following assertions hold:


  * E≽ 0 if and only if A^-1uu≤ 1. Furthermore, E≻ 0 if and only if A^-1uu< 1. Consequently, E is singular if and only if A^-1uu= 1.

  * E=(1-A^-1uu)A.




The proof is given in <cit.>. However, we outline it for the sake of completeness. 

We are given that A is positive definite. Now assume that E is positive semidefinite and let X=-A^-1u. Then 

    [   I   0; X^*   1 ][   A   u; u^*   1 ][ I X; 0 1 ]=[        A        0;        0 1-A^-1uu ]
 is positive semidefinite. Thus 1≥A^-1uu. And the converse is trivially seen. 

The last two parts easily follow as well. 





 §.§ Revisiting the HRT for collinear points

To the best of our knowledge no result on the HRT conjecture has been obtained through the  analysis of the Gramian of 𝒢(g, Λ)={e^2π i b_k ·g(· - a_k)}_k=1^N. Recall that the Gramian G_g of 𝒢(g, Λ)={e^2π i b_k ·g(· - a_k)}_k=1^N is the matrix given by 

    G_g   =(e^2π i b_k·g(· -a_k)e^2π i b_ℓ·g(· - a_ℓ))_k, ℓ = 1^N
       =(e^-2π i a_k(b_ℓ -b_k)V_gg(a_ℓ - a_k, b_ℓ-b_k))_k, ℓ=1^N.


It follows that G_g is positive semidefinite matrix and that the HRT conjecture holds if and only if G_g is strictly positive definite. In this section, we motivate our approach to analyze this Gramian by offering  a new proof of the  HRT conjecture for collinear points. While this result is well-known <cit.>, the new proof we provide illustrates the role of positive definiteness vis-a-vis the HRT conjecture. We will need the following version of Bochner's theorem, and refer to <cit.> for more on the classical  Bochner's theorem. We recall that a continuous complex-valued function f:^d → is positive definite if 

    ∑_j=1^N∑_k=1^Nc_jc_kf(x_j-x_k)≥ 0
 for any pairwise distinct points x_1,  x_2, , x_N∈^d, and (c_k)_k=1^N ∈^N. The function f is said to be strictly positive if equality holds in (<ref>) only when c_k=0 for all k=1, 2, , N. 

<cit.>
A continuous  complex-valued function f is positive definite if and only if f=μ̂ where μ is a non-negative finite Borel measure on . Furthermore, f is strictly positive definite if and only if there does not exist a non-zero trigonometric polynomial m vanishing on the support of μ, i.e., such that  ∫_ m dμ=0.







Let Λ={(a_k, b_k)}_k=1^N ⊂^2 be a set of collinear points. Then, by rotating and translating we can assume that Λ={(a_k, 0)}_k=1^N ⊂^2 with a_1=0, <cit.>. In this case, the Gramian of 𝒢(g, Λ) takes the form 


    G_g=(g(· -a_k)g(· - a_ℓ))_k, ℓ = 1^N= (ĝe^-2π i (a_k-a_ℓ) ·ĝ)_k, ℓ =1^N.


We can now give a new proof of the HRT conjecture when the points are collinear. 


Let 0≠ g ∈ L^2(), and Λ={(a_k, 0)}_k=1^N ⊂^2 with a_0=0. Then 
    𝒢(g, Λ)={g(· - a_k)}_k=1^N
 is linearly independent. 


 For g ∈ L^2() with g_2=1 let h(ξ)=|ĝ(ξ)|^2. We note that h is  non-negative, non-identically 0, and h ∈ L^1(). Let μ be the finite nonnegative Borel measure whose density with respect to the Lebesgue measure is the function h. The function Φ defined by 
    Φ(x)=ĥ(x)=μ̂(x)=∫_h(ξ) e^-2π i x ·ξdξ
 is continuous. Consequently, by Proposition <ref>, Φ  is positive definite. It remains to show that Φ is strictly positive definite. To do this, suppose that m is a non-zero trigonometric polynomial given by m(x)=∑_k=1^Kc_ke^2π i ξ_k x where c_k are complex numbers (not all zeros), and ξ_k are pairwise distinct real numbers.  It follows that 

    ∑_j=1^K ∑_k=1^K c_j c_k  Φ(ξ_j- ξ_k)    =∑_j=1^K ∑_k=1^K c_j c_k  ∫_ e^-2π i(ξ_j-ξ_k)x dμ(x)
        =∫_ ∑_j=1^Kc_j e^-2π i ξ_j x ∑_k=1^Kc_k e^2π i ξ_k x dμ(x)
       =∫_ |m(x)|^2 dμ(x)
       =∫_ |m(x)|^2 |ĝ(x)|^2 dx.
 This last integral vanishes only when m vanishes on the support of μ, which is the support of g. We can now conclude that Φ=ĥ=μ̂ is strictly positive definite. However, by (<ref>) we see that the Gramian of {g(· - a_k)}_k=1^N is exactly the matrix 

    G_g=(g(· -a_k)g(· - a_ℓ))_k, ℓ = 1^N=(Φ(a_k - a_ℓ))_k, ℓ =1^N.
 
Therefore,  G_g is strictly positive definite. 






 §.§ Motivation: The case of three points revisited

We now motivate our approach using the analysis of the Gramian of 𝒢(g, Λ)={g(· - a_k) e^2π i b_k·}_k=1^3 for 3 points {(a_k, b_k)}_k=1^3 ⊂^2. Furthermore, we suppose that the function g is real-valued. 
We note that following <cit.>, without loss of generality any set of three distinct  points can be transformed (through area preserving transformations)  into {(0,0), (0, 1), (a, b)} where (a, b) ∈^2∖{(0,0), (0,1)}. We also know that the HRT conjecture is always true for any set of two distinct points. Thus, {g, M_1g} is linearly independent and our task is to show that for any other point (a, b) ∈^2∖{(0,0), (0,1)}, {g, M_1g, M_bT_ag} remains  linearly independent. 

Observe that the Gramian G_g of {g, M_1g, M_bT_ag} can be written in the following block structure:


    G_g=[        A   u(a,b); u(a,b)^*        1 ]


 where 
    A=[ 1 α; α 1 ]    and     u(a,b)=[   V_gg(a, b); V_gg(a, b-1) ]
 with α=V_gg(0,1), and u(a,b)^* denoting the conjugate adjoint of u(a,b). Note that  |α| =|gM_1g|<g_2M_1g_2=g_2^2=1  since {g(·) , e^2π i ·g(·)} is linearly independent. We know that G_g is positive semidefinite and we wish to show that it is strictly positive definite. Appealing to Corolloary <ref>, we see that 
    0≤ F(a,b)=A^-1u(a,b)u(a,b)≤ 1
  and that  0≤ F(a,b)<1 if and only if {g, M_1g, M_bT_ag}  is linearly independent. Thus, the function F: ^2 → has range in [0,1] and 1 is its maximum value.

We can now prove the following result which serves both as a motivation to our approach and gives a new proof for the HRT conjecture for any 3 points on the integer lattice. 





Let 0≠ g ∈ L^2() be a real-valued function with g_2=1, and Λ={(0,0), (0, 1), (a,b)}, with (a, b)∈^2 ∖{(0,0), (0,1)}. Then the function F defined above  achieves its global maximum value 1 only for (a, b) ∈{(0,0), (0,1)}. Consequently,
Conjecture <ref> holds for  Λ and g. 
 




































































































































The proof of  Proposition <ref>  is based Demeter's result on (2,2) configurations, as well as on a   symmetry property of F. It also illustrates the restriction principle that will be introduced in Section <ref>.  First we prove the following symmetry of  F. 

 Suppose that g∈ L^2() is real-valued. With the setting above we have   

    F(a, b)=F(a, 1-b)
 for all (a, b)∈×, b≠ 1/2, and 
    F(-a, 1/2)=F(a,1/2)
 for all a ∈. 



Let 
    V=[ 0 1; 1 0 ].
  Then F(a, 1-b)=A^-1u(a, 1-b)u(a, 1-b), and 

    u(a, 1-b)=[ V_gg(a,1-b);  V_gg(a, b) ]=V [    V_gg(a,b); V_gg(a, b-1) ]=Vu(a,b).
 
Moreover, straightforward computations show that V^TA^-1V=VA^-1V=A̅^-1. 

Consequently,

    F(a, 1-b)   =A^-1u(a, 1-b)u(a, 1-b)=A^-1Vu(a,b)Vu(a,b)
       =V^TA^-1Vu(a,b)u(a,b)=A̅^-1u(a,b)u(a,b)
       =A̅^-1u(a,b)u(a,b)=A^-1u(a,b)u(a,b)
       =F(a, b)
 where we have used the fact that A^-1 is a positive definite matrix. 


When b=1/2 and a∈, we see that F(-a, 1/2)=A^-1u(-a, 1/2)u(-a, 1/2). but 
    u(-a, 1/2)=[  V_gg(-a, 1/2); V_gg(-a, -1/2) ]=[   e^π i aV_gg(a, 1/2); e^-π i aV_gg(a, -1/2) ]=Bu(a,b)
 where B=[  e^π i a        0;        0 e^-π i a ]. It follows that

    F(-a,1/2)   =A^-1u(-a, 1/2)u(-a, 1/2)=A^-1Bu(a, 1/2)Bu(a, 1/2)
       =B^*A^-1Bu(a,1/2)u(a,1/2)=A^-1u(a,1/2)u(a,1/2)
       =F(a,1/2)
 where we used the fact that  B^*A^-1B=A^-1. To see why this is the case we observe that a∈ and a series of computations shows that

    B^*A^-1B=11-|α|^2[            1 -α e^-2π i a;   -αe^2π i a            1 ]= 11-|α|^2[  1 -α; -α  1 ]=A^-1.







The following argument gives an alternate  proof of Proposition <ref>.



Because {g, M_1g, g} and {g, M_1g, M_1g} are both linearly dependent (repeated vectors) it follows that  F(0,0)=F(0,1)=1. Assume that there exists (a_0, b_0) ∈×∖{(0,0), (0,1)} such that F(a_0, b_0)=1 with b_0≠ 1/2.  In particular, by Corollary <ref> the system 𝒢(g, {(0,0), (0,1), (a_0, b_0)}) is linearly dependent, i.e., M_b_0T_a_0g belongs to the linear span of 𝒢(g, {(0,0), (0,1)}). Using Lemma <ref> we get that F(a_0, 1-b_0)=1 and therefore M_1-b_0T_a_0g belongs to the linear span of 𝒢(g, {(0,0), (0,1)}). Therefore,  𝒢(g, {(0,0), (0,1), (a_0, b_0), (a_0, 1-b_0)}) is also linearly dependent. But {(0,0), (0,1), (a_0, b_0), (a_0, 1-b_0)} is a (2,2) configuration and g ∈ L^2(), which contradicts <cit.>. 

The last case to consider is to assume that for some a_0≠ 0, b_0=1/2 and  F(a_0, 1/2)=1. But then using Lemma <ref> again we see that F(-a_0, 1/2)=F(a_0,1/2) and therefore 𝒢(g, {(0,0), (0,1), (a_0, 1/2), (-a_0, 1/2)}) is linearly dependent. But {(0,0), (0,1), (a_0, 1/2), (-a_0, 1/2)} is also a (2,2) configuration and g ∈ L^2(), which contradicts <cit.>. 










§ EXTENSION AND RESTRICTION  PRINCIPLES TO THE HRT CONJECTURE

In this section we describe in its full generality the aforementioned extension principle for the HRT conjecture. It could also be viewed as an inductive approach to attack the conjecture. More specifically, suppose that the Conjecture holds for a given function g ∈ L^2() and a given set Λ={(a_k, b_k)}_k=1^N⊂^2. We seek all the points (a, b) ∈^2 ∖Λ such that the conjecture remains true for the same function g and the new set Λ'=Λ∪{(a,b)}.  We investigate this question by using Theorem <ref> and Corollary <ref> to relate the Gramians of 𝒢(g, Λ') and 𝒢(g, Λ). In Section <ref> we introduce the main technical tool to extend the HRT in the sense given above. Subsequently, in  Section <ref> we apply this approach to  (1, n) configurations. Finally, in Section <ref> we introduce a related restriction principle that allows us to establish the HRT conjecture for a family of 4 points and real-valued functions from knowing that the conjecture can be proved for a related family of symmetric (2,3)  configurations. To establish the latter result  we refine  Demeter's “conjugate trick" arguments to handle this family of (2,3)  configurations. 




 §.§ The HRT extension principle
 
Let g ∈ L^2() with g_2=1. Assume that 
Conjecture <ref> holds for some  Λ={(a_k, b_k)}_k=1^N⊂^2 with (a_1, b_1)=(0,0). Let Λ'={(a_k, b_k)}_k=1^N∪{(a, b)} for   (a, b) ∈^2. 

The Gramian G_g, N+1(a,b) of 𝒢(g, Λ')={e^2π i b_k ·g(· - a_k)}_k=1^N∪{e^2π i b ·g(· -a)} has  the following block structure:


    G_N+1:=G_g, N+1(a,b)=[      G_N u_N(a,b); u(a,b)^*        1 ]

 where G_N:=G_g, N is the Gramian of {e^2π i b_k ·g(· - a_k)}_k=1^N, u_N(a,b) is a vector in ^N given by 

    u_N(a,b)=[                e^2π i a_1b_1V_gg(a, b); e^-2π i  a_2 (b-b_2)V_gg(a-a_2, b-b_2);  e^-2π i a_3(b- b_3)V_gg(a-a_3, b-b_3);                                      ⋮;  e^-2π i  a_N(b-b_N)V_gg(a-a_N, b-b_N) ]=[                           V_gg(a, b); e^2π i  a_2b_2V_g(T_a_2M_b_2g)(a, b);  e^2π i a_3b_3V_g(T_a_3M_b_3g)(a, b);                                    ⋮; e^2π i  a_Nb_NV_g(T_a_NM_b_Ng)(a, b) ]
 and 
u_N(a,b)^* is the adjoint of  u_N(a,b).  

Because G_N is positive definite,  the function  F_N+1:^2 → [0, ∞] given by 

    F(a,b):=F_N+1(a, b)=G_N^-1u_N(a,b)u_N(a,b)

is well-defined.
For simplicity and when the context is clear, we write u(a,b) for u_N(a,b), and F(a, b) for F_N(a,b).  Note that when N=2 the function F is simply the one introduced in the proof of Theorem <ref>.
 The following result summarizes the main properties of F.


With the above notations assume that G_ N is a positive definite N× N matrix.   Then,  the following statements hold.


  (i) 0≤ F(a,b)≤ 1 for all (a, b) ∈^2, and moreover, F(a_k, b_k)=1 for each k=1, , N. 

  (ii) F is uniformly continuous and lim_|(a,b)|→∞F(a,b)=0.

  (iii) ∬_^2F(a,b)da db=N.

  (iv) The Fourier transform  F:^2 →  of F given by 
    F(ξ, η)=∬_^2F(a,b)e^-2π i (aξ+ bη)dadb,
 is strictly positive definite, and integrable. 

  (v) G_g(a,b)=(1-F(a,b))G_N.









(i) The Gramian of G_g(a,b) is positive semidefinite so by Corollary <ref> and the assumption that G_N is positive definite, we conclude that 
    0≤ F(a,b)≤ 1.
 Moreover, for (a,b)=(a_k, b_k) we know that the Gramian is positive semidefinite as the system is linearly dependent (one element is repeated twice). Thus, we get the moreover part of the result. 

(ii) This follows easily as each coordinate of u(a,b) is a uniformly continuous function that tends to 0 at infinity.

(iii) Suppose that G_g,N^-1=(B_i,j)_i, j=1^N.  We can now write 


    F(a,b)   =G_N^-1u(a,b)u(a,b)
    
       = ∑_k=1^N∑_ℓ=1^NB_k, ℓ(u(a,b))_ℓ (u(a,b))_k
       = ∑_k=1^N∑_ℓ=1^NB_k, ℓ  e^2π i (a_ℓ b_ℓ-a_k b_k)  V_g(T_a_ℓM_b_ℓg)(a,b)   V_g(T_a_kM_b_kg)(a,b)  .

Integrating this last formula over ^2 and using the orthogonality and covariance properties of the STFT, i.e., (<ref>) and (<ref>) we have 

    ∬_^2F(a,b) da  db = ∑_k, ℓ=1^N B_k, ℓ  e^2π i (a_ℓ b_ℓ-a_k b_k) ∬_^2 V_g(T_a_ℓM_b_ℓg)(a,b)  V_g(T_a_kM_b_kg)(a,b)    da  db

Evaluating the integral leads to

    ∬_^2 V_g(T_a_ℓM_b_ℓg)(a,b)  V_g(T_a_kM_b_kg)(a,b)    da  db    =  V_g(T_a_ℓM_b_ℓg)V_g(T_a_kM_b_kg)
       =T_a_ℓM_b_ℓgT_a_kM_b_kg gg
       = T_a_ℓM_b_ℓgT_a_kM_b_kg

Consequently,






    ∬_^2F(a,b) da  db    =   ∑_k, ℓ=1^N B_k, ℓ  e^2π i (a_ℓ b_ℓ-a_k b_k) T_a_ℓM_b_ℓgT_a_kM_b_kg
       =   ∑_k, ℓ=1^N B_k, ℓ M_b_ℓT_a_ℓgM_b_kT_a_kg
       =  ∑_k, ℓ=1^N B_k, ℓ  (G_N)_ℓ,k
       =1det G_N∑_ℓ=1^N ∑_k=1^N (-1)^k+ℓ  (G_N)_ℓ,k det G_N({ℓ}',{k}') 
        = 1G_N∑_ℓ=1^N G_N
       = N

where we use the fact that B_k,ℓ=(-1)^k+ℓdet G_Ndet G_N({k}',{ℓ}'). 

(iv) This part follows from the fact that F is nonnegative, not identically 0, continuous, and integrable.  

Using (<ref>), (<ref>), and the notations set in part (iii) we can compute F̂ explicitly

    F̂(ξ, η)    =  ∑_k=1^N∑_ℓ=1^NB_k, ℓ e^2π i (a_ℓ b_ℓ-a_k b_k)ℱ_2(V_g(T_a_ℓM_b_ℓg)  V_g(T_a_kM_b_kg) )(ξ, η)
       =∑_k=1^N∑_ℓ=1^NB_k, ℓ  e^2π i (a_ℓ b_ℓ-a_k b_k) 
      V_T_a_kM_b_kg(T_a_ℓM_b_ℓg)(-η, ξ)   V_gg (-η, ξ)
       =∑_k=1^N∑_ℓ=1^NB_k, ℓ  e^2π i (a_ℓ b_ℓ-a_k b_k- a_ℓ b_k)  e^-2π i(a_ℓξ +b_kη)   V_gg(-η -a_ℓ +a_k, ξ -b_ℓ +b_k)  V_gg (-η, ξ).


It is clear that 
    ∬_^2|F̂(ξ, η)|dξ dη≤∑_k=1^N∑_ℓ=1^N|B_k, ℓ| < ∞.


(v) Follows from Corollary <ref>. 













The following result is a consequence of Theorem <ref>.


  Let g ∈ L^2() with g_2=1 and Λ={(a_k, b_k)}_k=1^N⊂^2. Assume that 𝒢(g, Λ) is linearly independent. Let  Λ'={(a_k, b_k)}_k=1^N∪{(a, b)}. Then 𝒢(g, Λ') is linearly independent if and only if F(a,b)<1.  Furthermore,  there exists R:=R(Λ, g)>0 such that for all (a, b) ∈^2 with |(a, b)|> R, then 𝒢(g, Λ') is linearly independent where Λ'=Λ∪{(a, b)}



The first part follows from   part (1) of  Corollary <ref> and part (i) of Theorem <ref>. The existence of R is guaranteed by part (ii) of Theorem <ref>. 




(a) By the last part of Corollary <ref>, the extension function F makes the HRT conjecture a “local problem”. In other words, once the conjecture is known to be true for a function g and a set Λ={(a_k, b_k)}_k=1^N, it is also automatically true  for Λ'=Λ∪{(a, b)} whenever the new point lies outside a ball of radius R. So to establish the HRT everywhere for Λ' we must focus on the “local” properties of F, that is the restriction of F to the aforementioned ball.

(b)  Corollary <ref> makes it possible to explore the HRT from a numerical point of view. Indeed, Theorem <ref> and 
Corollary <ref>  assert that the HRT for Λ'={(a_k, b_k)}_k=1^N∪{(a, b)} holds if and only if (a, b) is not a global maximizer of F. So in theory, one only needs to prove that the set of global maximizers of F is  Λ. For  a smooth function g, differential calculus can be used to check this.  For example, for the  Gaussian  g(x)=2^1/4 e^-π x^2, using <cit.> we get that 
    V_gg(a,b)=e^-π i a be^-π a^2/2e^-π b^2/2.
 
In this case and using Λ={(0,0), (0,1)}∪{(a, b)},  F is simply

    F(a,b)= e^-π (a^2+b^2)1-e^-π[ 1 + e^π (2b-1) - 2 e^π(b-1)cos a ].
 One can then used multivariable calculus to show that the global maximizers of F  are exactly the two points (0,0) and (0,1), see Figure <ref>. 





More generally,  one can numerically analyze the function F to determine its global maximizers. For example, suppose Λ={(0,0), (1,0), (0,1)}. For the Gaussian g(x)=2^1/4e^-π x^2, Figure <ref> displays the graph of the function F on the square [-4, 4]× [-4,4]. This graph illustrates the validity of the HRT in this case, by showing that the global maximum value of F is only achieved on the set Λ.  Similarly, when g(x)=e^-|x|,  Figure <ref> displays the graph of the function F on the square [-4, 4]× [-4,4]. This graph illustrates the validity of the HRT in this case, by showing that the global maximum value of F is only achieved on the set Λ. Recall that the HRT is known to be true for this function and any set of 4 points <cit.>. Finally, Figure <ref> displays the graph of the function F on the square [-4, 4]× [-4,4] when g(x)=2^-1/21+|x|. To the best of our knowledge, the HRT has not been proved for this function and any set of 4 points. Therefore, Figure <ref> offers some numerical evidence to the validity of the conjecture in this case. We also refer to Corollary <ref> for some new results in this setting. 
















 §.§ The HRT conjecture  for (1, n) configurations

In this section, we consider the HRT conjecture for (1,n) configurations and prove that  the conjecture can only fail for at most one such configuration. The proof is elementary and based on some dimension arguments. We then focus on the case n=3 and show that when the generator is a real-valued function then  Conjecture <ref> holds for all (1,3).   Note that the strongest known results for these configurations assume either that the 3 collinear points are also equi-spaced, or that the generator is in S(). The motivation of the results presented in this section is <cit.> which states that the HRT conjecture holds for almost all (in the sense of Lebesgue measure) (1,3) configurations. A consequence of our result is that the HRT conjecture can only fail for at most one (1,3) configuration up to equivalence.  For more on the HRT for (1,3) we refer to Demeter's results <cit.> and a recent improvement due to Liu <cit.>.

Recall that by using the metaplectic transformations one can show that any (1,n) configuration has the form {(0,1)}∪{(a_k, 0)}_k=1^n where a_1=0 and the rest of the  a_ks are distinct and nonzero <cit.>. Note that the set of metaplectic transformations in ^2 can be identified with the set of 2× 2 symplectic matrices, which, in turn is SL(2, ) <cit.>. We say that two (1, n) configurations Λ_1 and Λ_2 are equivalent if and only if there exists a symplectic matrix A∈ SL(2, ) such that Λ_2=AΛ_1. Let the set of distinct equivalence classes under this relation be denoted by Λ_(1,n). Without any loss of generality we can assume that 

    Λ_(1,n)={(0,1)}∪{(a_k, 0)}_k=1^n
 with a_1=0 and a_k≠ 0 for all k=2, 3, , n. To prove that the HRT conjecture holds for all (1,n) configurations, it is enough to restrict to (1,n) configurations in Λ_(1,n). 





Let n≥ 3 and g∈ L^2() with g_2=1. Suppose that the HRT conjecture holds for g and any (1, n-1) configuration. Then there exists at most one (equivalence class of) (1, n) configuration Λ_0 ∈Λ_(1,n) such that 𝒢(g, Λ_0) is linearly dependent. Furthermore, suppose that Λ_0={(0,1)}∪{(a_k, 0)}_k=1^n ∈Λ_(1,n) is a (1,n) configuration such that 𝒢(g, Λ_0) is linearly dependent. Let a≠  a_k  for k=1, , n. Fix any k_0 ∈{1, , n} and consider 
    Λ ={(0,1)}∪{(a_1, 0), (a_2, 0), , (a_k_0-1, 0), (a, 0), (a_k_0+1, 0), , (a_n, 0)}.
 Then 𝒢(g, Λ) is linearly independent.


  Suppose by contradiction that there exist two distinct  (1, n) configurations (or equivalent classes) Λ_1 and Λ_2 such that 𝒢(g, Λ_i) is linearly dependent for i=1,2.  Further, suppose that 
    Λ_1={(0,1)}∪{(a_k, 0)}_k=1^n   and   Λ_2={(0,1)}∪{(b_k, 0)}_k=1^n
 where a_1=b_1=0 and a_i_0≠ b_i_0 for some i_0∈{2, , n}. Then, one can write 

    M_1g=∑_k=1^nc_kT_a_kg
 where c_k ≠ 0 for each k=1, , n. Indeed, if c_ℓ=0 for some ℓ∈{1, , n} then Λ'_1=Λ_1∖{(a_ℓ, 0)} will be a (1, n-1) configuration and (<ref>) will become 
    M_1g=∑_k=1,   k ≠ℓ^nc_kT_a_kg.
  That is 𝒢(g, Λ_1') will be linearly dependent contradicting one of the assumptions of the Theorem. Similarly,  

    M_1g=∑_k=1^nd_kT_b_kg
 where d_k ≠ 0 for each k=1, , n. Taking the difference between (<ref>) and (<ref>) and rearranging leads to 
    (c_1-d_1) g + c_i_0T_a_i_0g - d_i_0T_b_i_0g+∑_k=2,   k≠ i_0^n c_kT_a_kg - ∑_k=2,   k≠ i_0^n d_kT_b_kg =0
 where i_0 was chosen above. But since c_i_0d_i_0≠ 0 and  a_i_0≠ b_i_0, this last equation is equivalent to the fact that 
    {g, T_a_kg, T_b_kg: k=2 , n}
 is linearly dependent. But this contradicts the fact the HRT conjecture holds for any 0≠ g∈ L^2() and the collinear points {(0,0), (a_k, 0), (b_k, 0): k=2, , n}, <cit.>. Therefore, there can exist at most one (class of equivalence) (1, n) configuration Λ_0 for which 
𝒢(g, Λ_0) is linearly dependent.

For the last part,  suppose that Λ_0={(0,1)}∪{(a_k, 0)}_k=0^n ∈Λ_(1,n) is such that 𝒢(g, Λ_0) is linearly dependent.  Write   Λ_0= Λ_0'∪{(a_k_0, 0)} where 
    Λ_0'={(0,1), (0,0), (a_2, 0), , (a_k_0-1, 0), (a_k_0+1, 0), , (a_n, 0)}.
  By assumption, 𝒢(g, Λ_0') is linearly independent since Λ_0' is a (1, n-1) configuration. Then by  Corollary <ref>, F(a_k_0,0)=1 where F is the function obtained from the Gramian of 𝒢(g, Λ_0) according to Theorem <ref>.

Now, let  a∉{0, a_k: k=2, , n}. If F(a, 0)=1 then T_ag must belong to the linear span of {M_1g, T_a_kg: k=1, , n,  k≠ k_0} whose dimension is n. But, T_a_k_0g also belongs to this linear span. Therefore, the n+1 functions g, T_a_kg, T_ag, k=2, , n belong to an n dimensional space. However, these functions are linearly independent (because the points are collinear). This is a contradiction, from which we conclude that F(a, 0)<1, concluding the proof. 


 

In the special case where n=3 we have the following result.


Let g∈ L^2() with g_2=1. There exists at most one (equivalence class of) (1, 3) configuration Λ_0 such that 𝒢(g, Λ_0) is linearly dependent.



When n=3 it is known that the HRT conjecture holds for g and every (1, 2) configuration <cit.>. Thus the assumption of Theorem <ref> is satisfied and the corollary follows.


If we restrict to real-valued functions, then we can prove a stronger result by ruling out the existence of the single “bad” (equivalence class of ) (1,3) configuration given by Corollary <ref>.




Let g∈ L^2(),  g_2=1 be a real-valued function. Let  a≠ b≠ 0 and set Λ={(0,0), (0,1), (a,0), ( b,0)}  be a (1, 3) configuration. Then, Conjecture <ref> holds for  Λ and g.



Assume by way of contradiction that 𝒢(g, Λ) is linearly dependent. Then, there exists c_k ∈^*, k=1, 2, 3, such that 
    c_1g + c_2M_1g + c_3T_ag = T_bg.
 Because, g is real-valued, we see that 
    T_bg=T_bg= c̅_1g + c̅_2M_-1g + c̅_3T_ag.
 Hence, 
    (c_1-c̅_1)g+ c_2M_1g - c̅_2M_-1g +(c_3-c̅_3)T_ag=0.
 Note that c_2≠ 0. Hence, this last equation  is equivalent to the fact  that  𝒢(g, Λ')  where Λ'={(0,0), (a, 0), (0,1), (0, -1)} is linearly dependent. However, because the points (0,1), (0,0) and (0, -1) are equally spaced, Λ' is a (1, 3) configuration, for which Conjecture <ref> is known to hold <cit.>. Therefore, we arrive at a  contradiction.
 







 §.§ A restriction principle for the HRT conjecture


The goal of this section is to establish Conjecture <ref> for a large family of sets of cardinality 4 (that are not (1,3) nor (2,2) configurations) when g is a real-valued function. In addition, we establish similar results for Conjecture <ref>. 
In fact, we prove that the general case for (almost) any 4 points follows from a special family of (3,2) configurations. This is our restriction principle: proving that Conjecture <ref> or Conjecture <ref> hold for this special special family of (3,2) configurations implies its validity for a large family  4 points.  The proof of the next result is an extension of Demeter's “conjugate trick” arguments <cit.>. 




Let g∈ L^2() with g_2=1. Suppose Λ is a (3,2) configuration given by Λ={(0,0), (0,1), (0,-1), (a, b), (a, -b)} where b≠ 0. Then, Conjecture <ref> holds for  Λ and g whenever any of the following holds


  (i) a, b ∈.

  (ii) a∈ but b∉.

  (iii) a, b ∉ but ab ∈, and g is a real-valued function. 

 


We can  trivially assume that a≠ 0. Indeed, if a=0 then the points in Λ will all lie on the y-axis, that is the points will be collinear, and HRT is known to be true in this case <cit.>. 




(i) Suppose that a=pq, b=mn∈.  In this case, we see that Λ=AΛ', where A=[ 1q  0;  0 1n ] and Λ'={(0,0), (0, n), (0, -n), (p, m), (p, -m)}. In particular, Λ is a subset of a lattice and the result follows from <cit.>. 




(ii) Next assume that a ∈ and b∉.  By using a scaling matrix (a metaplectic transform)  we can assume that Λ has the following form:

    Λ={(0,0), (0,a), (0,-a), (1, b'), (1, -b')}
 with b'=ba ∉ <cit.>.  To simplify the notations we will assume that 
    Λ={(0,0), (0,a), (0,-a), (1, b), (1, -b)}
 with a ∈ and b ∉. 

Assume by  way of contradiction that 𝒢(g, Λ) is linearly dependent. Then, there exist c_k ∈, k=1, 2, 3, and d_k∈, for k=1, 2 such that 

    c_1g + c_2M_ag + c_3M_-ag= d_1M_-bT_1g + d_2M_bT_1g.

 Observe that c_k, d_k≠ 0 for each k, since the conjecture is true for all  (2,2) configurations, and (1,3) configurations where the points on the line are equiangular. We may also assume that c_1∈. 
 
 Consequently, we can write (<ref>) as 
 
 
    |P(x)g(x)|=|Q(x)g(x-1)|   a. e.

where P(x)=c_1+c_2e^2π i ax +c_3e^-2π i ax and Q(x)=e^2π i (-bx+θ)(r_1+r_2e^2π i (2bx+θ') with r_1, r_2∈ (0, ∞) and θ, θ'∈ [0, 1). (Here we write d_1=r_1e^2π i θ and d_2=r_2e^2π i θ'.) 
 
Furthermore, because 0≠ g ∈ L^2() we have that

    lim_|n|→∞   n∈g(x-n)=0    a. e.
 
and that  supp (g)∩ [0,1] has a positive measure. Let S⊂suppg∩ [0,1] be such that S has positive measure, and such that S+ contains no zeros of P and Q (this is possible since the set of such zeros is at most countable). From now on,  we assume that  (<ref>) and  (<ref>) hold for all x∈ S. 

Next, by the Birkhoff's pointwise ergodic theorem with 1_S, there exists x_0∈ S and n' ∈ such that x_1={-x_0-θ'b+ n'b}∈ S. Here and in what follows, we denote a fractional part of x∈ by {x}.  Let m=-x_0-θ'b+ n'b-x_1=y-x_1.
 
By iterating (<ref>),  it follows that for all N>m
 
    {[                                               |g(x_0+N)|             |g(x_0-1)|∏_n=0^N|Q(x_0+n)|∏_n=0^N|P(x_0+n)|;                                             |g(x_1-N+m)| |g(x_1-1)|∏_n=-N+m+1^-1|P(x_1+n)|∏_n=-N+m+1^-1|Q(x_1+n)| ].

 Next, observe that 
    ∏_n=-N+m^m|Q(x_1+n)|=∏_n=0^N|Q(x_0+n)|.
 
 Consequently,
 
    ∏_n=-N+m^-1|Q(x_1+n)|   =∏_n=-N+m^m|Q(x_1+n)| 1∏_n=0^m|Q(x_1+n)|    =K ∏_n=-N+m^m|Q(x_1+n)|
       =K∏_n=0^N|Q(x_0+n)|,
 where K=1∏_n=0^m|Q(x_1+n)| is a positive finite constant that depends only on m, x_0, n', b, and θ'.
 
 Now assume that a=t/s ∈, then P is s-periodic. Let T(x)=∏_n=0^s-1|P(x+n)|, and assume first that T(x_1)≥ T(x_0). Then,  
 
    ∏_n=-N+m+1^-1|P(x_1+n)|=K' ∏_n=0^N|P(x_1 -n)|≥∏_n=0^N|P(x_0+n)|
 for all N>m, where K'=1|P(x_1)|∏_n=-N^-N+m|P(x_1+n)| is a constant independent of N. 
 
 
  Consequently, for N>m, 
 
    |g(x_1-N+m)|   =|g(x_1 -1)|∏_n=-N+m^-1|P(x_1+n)|∏_n=-N+m^-1|Q(x_1+n)|
       ≥ C |g(x_1 -1)| ∏_n=0^N|P(x_0+n)|∏_n=0^N|Q(x_0+n)|
       ≥ C |g(x_1-1)||g(x_0-1)| |g(x_0+N)|^-1
 where C is a constant that depends only on x_0, m, r_1, r_2, c_1, c_2, and c_3. But this last inequality contradicts (<ref>). 
  
  Now if instead, T(x_0)≥ T(x_1). We will have 
  
    ∏_n=-N+m^-1|P(x_0+n)| ≥∏_n=0^N|P(x_1+n)|
 for all N>m, 
  
    ∏_n=-N+m^-1|Q(x_0+n)| ≃∏_n=0^N|Q(x_1+n)|,
 where we used the notation A≃ B to denote B/c≤ A≤ cB for some constant c that depends only on x_0, m, r_1, and r_2.
  
For N>m, 
    |g(x_0-N+m)|≥ C |g(x_0-1)| ∏_n=0^N|P(x_1+n)|∏_n=0^N|Q(x_1+n)|,
 and 
    |g(x_1+N)|=|g(x_1-1)|  ∏_n=0^N|Q(x_1+n)|∏_n=0^N|P(x_1+n)|.
 
Consequently, for N>m, 

    |g(x_0-N+m)|≥ C |g(x_0-1)| |g(x_1-1)||g(x_1+N)|^-1,
 where C is a constant that depends only on x_0, m, r_1, r_2, c_1, c_2, and c_3. But this last inequality contradicts (<ref>). 

We conclude that (<ref>) cannot hold unless, c_k=0 for k=1, 2,3 and d_k=0 for k=1,2. 
  





(iii) Similar to case (ii), and using a metaplectic transform we can assume that Λ is of the form Λ={(0,0), (0,a), (0,-a), (1, b), (1, b)} with a∉, b∈. 

We now proceed as in part (ii) and assume that (<ref>) holds. Since, g is assumed to be real-valued we see by taking the complex conjugate of (<ref>) that 
 
 
    c_1g+c_2M_-ag +c_3M_ag-d_1M_-bT_1g-d_2M_bT_1g=0.
 taking the difference between this last equation and (<ref>) , we obtain 
 
    (c_2-c_3)M_ag  + (c_3-c_2)M_-ag +(d_2-d_1)M_bT_1g +(d_1-d_2)M_-bT_1g=0.
 Now, the points {(0,a), (0,-a), (1, b), (1, -b)} form a (2,2) configuration and the HRT conjecture is true in this case. Therefore, 
 c_3=c̅_2, d_2=d̅_1. Consequently, we let c_1=c∈, c_2=re^2π i θ, and d_1=r'e^2π i θ', where r, r'∈ (0, ∞) and θ, θ' ∈ [0,1). 

Therefore, (<ref>) holds with P(x)=c+2rcos 2π (ax +θ) and Q(x)=2r'cos 2π (bx +θ'). In particular, Q is a s-periodic function if we let b=t/s∈. Reversing the role of the polynomials P and Q in the proof of (ii) establishes the result in this last case. 




 We note that the case a∉ and b∈ is equivalent (by a metaplectic transformation) to a, b, ab∉. This is the only case we have not been able to address. However, if we assume that g is smoother, then we can handle this case as well, see Theorem <ref> below. 



We can now prove the following result for a family of  4 points in ^2 and real-valued functions. This illustrates the restriction principle we announced in the introduction. Indeed, to establish the HRT conjecture for the family of sets of four points we use the fact the conjecture was proved for the above family of symmetric (2,3) configurations. More specifically, the following result holds. Note that any set of four distinct points can be transformed into {(0,0), (0, 1), (s, 0), (a, b)}. 






Let g∈ L^2(), g_2=1  be a real-valued function. Suppose  that Λ= {(0,0), (0, 1), (s, 0), (a, b)}⊂^2 be a subset of four distinct points.  Conjecture <ref> holds for  Λ and g, whenever any of the following holds


  (i) a, b∈.

  (ii) a∈ but b∉.

  (iii) a, b ∉ but ab ∈




 If ab=0 then, we are done by invoking Theorem <ref>. So we assume that ab≠ 0, and suppose by contradiction that there exist nonzero coefficients c_1, c_2, c_3 such that 
    T_sg=c_1g+c_2M_1g+c_3M_bT_ag.
 This implies that 
    T_sg=c̅_1g+c̅_2M_-1g+c̅_3M_-bT_ag.
 Hence, 
    (c_1-c_1)g + c_2M_1g -c_2M_-1g + c_3M_bT_ag   - c̅_3M_-bT_ag=0.
 Consequently,  𝒢(g, Λ) with Λ={(0,0), (0,1), (0,-1), (a, b), (a, -b)} is linearly dependent, which, contradicts Theorem <ref>. 






We recall the following conjecture. 
 <cit.>. Suppose Λ={(0,0), (0,1), (1, 0), (√(2), √(2))}, and if 0≠ g ∈ L^2() with g_2=1 then 𝒢(g, Λ) is linearly independent. 
 

An application of Corollary <ref> settles this conjecture in the special case where g is real-valued. Indeed, this follows from part (iii) of Corollary <ref>  by taking s=1, a=b=√(2)∉.
 

If we assume that the  function g is smoother, i.e., g∈() then we can extend <cit.> from (2,2) configurations to certain symmetric (3,2) configurations. It must be noted that the arguments given below were originally  introduced in <cit.>[The proof given in <cit.> contains a few inaccuracies that were fixed by C. Demeter and posted on Math Arxiv as arXiv:1006.0732.]. For the sake of completeness we give the details of the proof below. 



Let g∈(), g_2=1. Suppose Λ is a (3,2) configuration given by Λ={(0,0), (0,1), (0,-1), (a, b), (a, -b)} where b≠ 0. Then, Conjecture <ref> holds for  Λ and g  whenever any of the following holds


  (i) a, b ∈.

  (ii) a∈ but b∉.

  (iii) a, b, ab ∉.  

  (iv) a, b ∉ but ab ∈, and g is a real-valued function. 

 

 The proof is divided in a number of cases.

(i), (ii), (iv)  follow from Theorem <ref>.







(iii) Suppose that  a, b ∉. Furthermore, assume that ab∉. Using a metaplectic transformation, we may assume that Λ is of the form Λ={(0,0), (0,a), (0,-a), (1, b), (1, b)}, with a, b, b/a∉. The rest of the proof is an extension of <cit.>. 

We follow the proof of part  (ii) of Theorem <ref> and argue by contradiction. In particular, we assume that (<ref>), (<ref>), and (<ref>) hold for all x∈ I, where I⊂supp(g)∩ [0,1] is a set of positive measure. Recall that P(x)=c_1+c_2e^2π i ax+c_3e^-2π i ax and Q(x)=e^2π i (-bx+θ)(r_1+r_2e^2π i(2bx+θ')) where r_1, r_2∈ (0, ∞), θ, θ' ∈ [0,1), c_1∈, c_2, c_3∈ with c_k≠ 0 for k=1,2,3. 

We first prove that |-c_1±√(c_1^2-4c_2c_3)|2|c_2|≠ 1. Suppose by way of contradiction that |-c_1±√(c_1^2-4c_2c_3)|2|c_2|= 1. This implies that P(x)=0 has real solutions of the form 
    x_k=ω + ka
 for some ω∈ and k∈. 



Next we prove that  Q must also have some real roots. Indeed, assume that Q(x)≠ 0 for all x∈. Since a∉ we can choose k∈ with x_k>0 and {x_k}∈ I (recall that {u} is the fractional part of u). Note that g({x_k})≠ 0. We now use (<ref>) to get 
    0=|P(x_k)||g(x_k)|=|Q(x_k)||g(x_k-1)|
 Thus g(x_k-1)=0. We can continue this iteration to show that g(x_k-n)=0 for all n>0. Consequently, g({x_k})=0 which is a contradiction. Therefore, Q has real roots of the form 
    y_n=ω' +n2b
  for some ω'∈ and n∈. 

Furthermore, the zeros of P and Q must share a -orbit. Indeed, if this was not the case, we must have that x_k-y_n∉ for all n, k∈. However, a repeated use of (<ref>) will lead to the following contradiction. For any  k∈ Z we have 0=|P(x_k)||g(x_k)|=|Q(x_k)||g(x_k-1)|. Since x_k=x_k-0 is not a root of Q we see that g(x_k-1)=0. Continuing in this fashion we see that g(x_k-n)=0 for all n>0. Which is a contradiction. In fact, there must exist n≠ n' ∈ and m, m'∈ such that 
    x_n-y_m,   x_n'-y_m'∈.
 By taking the difference between these two numbers we see that 
    Na+M2b=k
 for some N, M, k∈. Using the fact that a, b∉ we arrive at the conclusion that all N, M satisfying this equation must be of the form N=ℓ N_0 and M=ℓ M_0 for some fixed N_0, M_0∈∖{0} and arbitrary ℓ∈. In addition, all n, m∈ such that x_n-y_m∈ must be of the form 


    {[          n  n_0+ℓ N_0;          m m_0+ℓ M_0, ].


for some fixed n_0, m_0, N_0, M_0∈, N_0, M_0 ≠ 0 and arbitrary ℓ∈. We also point out that for each x_n there is at most one y_m such that x_n-y_m∈.

Let x_ℓ= ω_0+ℓN_0a be a zero of P where ω_0=ω+n_0a, and y_ℓ be the zero of Q such that x_ℓ-y_ℓ∈. Note that y_ℓ=  ω_0'+ℓM_02b  where ω_0'=ω'+m_02b. Because N_0a≠M_02b, we can choose ℓ∈ such that one of the following three alternatives holds:∙ 0<x_ℓ<y_ℓ∙ x_ℓ<0<y_ℓ∙ x_ℓ<y_ℓ<0

If we assume that the first alternative holds, by ergodicity, we can choose ℓ∈ such that u_ℓ={x_ℓ}={y_ℓ}∈ I. Note that g(u_ℓ)≠ 0 and using the recursion (<ref>) and the fact that Q is nonzero on the orbit before y_ℓ, we see that g(u_ℓ +1)≠ 0, which implies that g(u_ℓ+2)≠ 0. We can continue all the way to g(u_ℓ+n)≠ 0 where n∈ is such that u_ℓ +n+1=x_ℓ. Applying (<ref>) one more time will give 
    0=|P(x_ℓ)||g(x_ℓ)|=|Q(x_ℓ)||g(u_ℓ+n)|≠ 0


It follows that inf_x∈|P(x)|>0. Similarly, we show that inf_x∈|Q(x)|>0. Consequently, ψ(x)=ln|c_1+c_2e^2π ix+c_3e^-2π i x| and ϕ(x)=ln|r_1+r_2e^2π i(2x+θ')| are well-defined and continuous on   

Using (<ref>) and (<ref>) we see that for each x, z∈ I


    lim_N→∞∑_n=1^Nϕ(bx+bn)-∑_n=1^Nψ(ax+an)=-∞

and 

    lim_N→∞∑_n=-N^-1ϕ(bz+bn)-∑_n=-N^-1ψ(az+an)=∞


We now use the approximation of a by rational and the fact |ψ'|≳ 1 to control parts of the above sums. 

Let p_k, q_k relatively prime integers, q →∞ such that 
    |a-p_kq_k|≤1q_k^2.
 Furthermore, 
    |na-np_kq_k|≤1q_k,   -q_k≤ n≤ q_k.
 By a Riemann sum approximation we see that 
    |∑_n=1^q_kψ(ax+an)-q_k∫_0^1ψ|=O(1)
 and 


    |∑_n=-q_k^-1ψ(ax+an)-q_k∫_0^1ψ|=O(1)
 for each x∈ [0,1]. Consequently, for each y, z∈ I we have


    |∑_n=1^q_kψ(ay+an)-∑_n=-q_k^-1ψ(az +an)|=O(1).


Now using Birkhoff's pointwise ergodic theorem for 1_I, we can choose x∈ I, n'∈ N such that z:={-x-θ'b+n'2b}∈ I. Let y:=-x-θ'b+n'2b and m=y-z. Then 
    ∑_n=-N+m^-1+mϕ(bz+bn)=∑_n=1^Nϕ(by-bn)=∑_n=1^Nϕ(bx+bn).
 Observe that for each N


    ∑_n=-N^-1ϕ(bz+bn)   =∑_n=-N^-N+m-1ϕ(bz+bn)+ ∑_n=-N+m^-1+mϕ(bz+bn)+∑_n=m^-1ϕ(bz+bn)
       =∑_n=1^Nϕ(bx+bn)+ ∑_n=-N^-N+m-1ϕ(bz+bn)+∑_n=m^-1ϕ(bz+bn)




Consequently, for each N 


    |∑_n=-N^-1ϕ(bz+bn)-∑_n=1^Nϕ(bx+bn)|   =|∑_n=-N^-N+m-1ϕ(bz+bn)+ ∑_n=m^-1ϕ(bz+bn)|
       =O(1)
 where we bound the last sum by a constant that depends only on m, z, and b. However, (<ref>)–(<ref>) cannot simultaneously hold. This completes the proof.


Next we suppose that a, b∉ but ab∈. 













 We note that as observed in <cit.>, rather than assuming that g∈() we could assume that g∈ L^2() is continuous and is such that lim_|n|→∞  n∈|g(x-n)|=0 for all x∈ [0,1]. 

 Suppose that g∈() is real-valued. In addition to the cases covered by Corollary <ref>, Theorem <ref> can be used to settle Conjecture <ref> when  a, b, ab∉.













We summarize what is known about the HRT for 4 points. In ^2, a set  Λ consisting of four distinct points in ^2 can be such that:


  (1) The four points are  collinear, in which case their convex hull is a line segment,

  (2) The four points form a (1,3) configuration,  in which case their convex hull is a triangle, 

  (3) The four points  form a (2,2) configuration,  in which case their convex hull is a trapezoid, or

  (4) The four points are in none of the previous three categories,  in which case their convex hull is a general quadrilateral. 


∙ In the first case Conjecture <ref> holds for any g ∈ L^2() <cit.>.∙ In the second case Conjecture <ref> holds for any g ∈() <cit.>. However, if g ∈ L^2,  Conjecture <ref> is true  when the three collinear points are also equispaced <cit.>. More generally, <cit.> has condition under which the conjecture remains true, and,  in fact, Conjecture <ref> holds for almost all (1,3) configurations. The results of this paper allow us to conclude that when g∈ L^2 is also real-valued then Conjecture <ref> for all (1,3) configurations.∙ For the third case, Conjecture <ref> holds for any g ∈ L^2() <cit.>.∙ In the last case,  to the best of our knowledge both Conjecture <ref> and Conjecture <ref> remain open. However,  when g(x)=e^-|x|^ϵ with ϵ>0 Conjecture <ref> holds for any set of 4 points <cit.>. In fact, when g decays faster than any exponential the HRT conjecture has been established not only in dimension one, but also in higher dimensions <cit.>. In this paper we showed that when g∈ L^2() is real-valued  Conjecture <ref> holds for a family of four distinct points.  


But is still unclear whether the HRT holds for any 4 points and every g∈ L^2().







§ ACKNOWLEDGMENT
 
The author thanks C. Heil for introducing him to this fascinating and addictive problem, and for invaluable comments and remarks on earlier versions of this paper. He also thanks R. Balan, J. J. Benedetto, and D. Speegle for helpful discussions over the years about various versions of the results presented here. He acknowledges C. Clark's help in generating the pictures included in the paper. Finally, he thanks W. Liu for helpful discussions, and the anonymous referees for their useful and insightful comments and remarks. 

amsplain


