1 Introduction

Consider the translation operator \(T_x f = f(t-x)\) and the modulation operator \(M_\omega f = e^{2 \pi i \omega \cdot t} f(t)\) acting on \(f \in L^2({{\,\mathrm{\mathbb {R}}\,}}^n).\) For \(\lambda = (x, \omega ) \in {{\,\mathrm{\mathbb {R}}\,}}^{2n}\) we define the time-frequency shift \(\pi (\lambda )f = M_\omega T_x f.\) The Heil–Ramanathan–Topiwala (HRT) Conjecture [8] states

Conjecture 1

Suppose \(f \in L^2({{\,\mathrm{\mathbb {R}}\,}})\) is nonzero and \(\Lambda \subset {{\,\mathrm{\mathbb {R}}\,}}^{2}\) is a finite set. Then the collection of functions \(\mathcal {G}(f, \Lambda ) = \{\pi (\lambda )f\}_{\lambda \in \Lambda }\) is linearly independent.

The HRT Conjecture is still open in its most general form, but it has been proven under various additional assumptions on the function f and the point set \(\Lambda \) [1,2,3,4,5, 8,9,10,11].

In this paper we will prove Conjecture 1 in cases where the distance between points in \(\Lambda \) is large relative to the decay of f.

Theorem 1

Let \(f \in C_0({{\,\mathrm{\mathbb {R}}\,}}^n),\) let \(\Lambda = \{(x_i,\omega _i)\}_{i=1}^N \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}\) be a finite set, and fix R so that \(|f(t)| < \frac{|f(0)|}{N-1}\) for all t outside of the ball of radius R around the origin. If \(||x_i - x_j|| > R\) whenever \( i \ne j\) then \(\mathcal {G}(f,\Lambda )\) is linearly independent.

The intuition for Theorem 1 is that if the points in \(\Lambda \) are spaced far apart then in any linear dependence the tails of translates of f must combine to cancel the peaks of f. This requires putting large coefficients on the translates of f. However by putting large coefficients on the translates of f,  we make the peaks of the translates more difficult to cancel, leading to a contradiction.

Theorem 1 is most effective when |f| drops off steeply near the origin. Given any \(f \in C_0({{\,\mathrm{\mathbb {R}}\,}}^n)\) we can engineer such a steep descent by applying a sufficiently large dilation, assuming \(f(0) \ne 0.\) We denote by \(D_r\) the unitary operator which dilates a function f uniformly along all the coordinate axes.

Corollary 1

Suppose \(f \in C_0({{\,\mathrm{\mathbb {R}}\,}}^n)\) and \(f(0) \ne 0.\) Given \(\Lambda = \{(x_i,\omega _i)\}_{i=1}^N \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}\) there exists \(r > 0\) such that \(\mathcal {G}(D_{r'}f, \Lambda )\) is linearly independent for all \(0< r' < r.\)

Similarly, if f has a singularity away from which it is bounded then we can find translates of f which have an arbitrarily steep drop off. Thus we can prove Conjecture 1 for such functions.

Theorem 2

Let f be continuous except at a point p where \(\lim _{t \rightarrow p} |f(t)| = \infty .\) Assume that f is bounded away from any neighborhood of p. Then \(\mathcal {G}(f, \Lambda )\) is linearly independent for any finite \(\Lambda \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}.\)

2 Proofs, Examples, and Extensions

The following lemma captures the intuition for Theorem 1 described above.

Lemma 1

Let \(S = \{x_i\}_{i=1}^N \subset {{\,\mathrm{\mathbb {R}}\,}}^n, f \in C({{\,\mathrm{\mathbb {R}}\,}}^n),\) and \(E = \{e_i\}_{i=1}^N \subset C({{\,\mathrm{\mathbb {R}}\,}}^n)\) such that \(|e_i(t)| = 1\) for all \(t \in {{\,\mathrm{\mathbb {R}}\,}}^n.\) Furthermore, suppose that \(|f(x_i - x_j)| < \frac{|f(0)|}{N-1}\) whenever \(x_i, x_j\) are distinct points in S. Then the collection of functions \(\{e_i(t)f(t-x_i)\}_{i=1}^N\) is linearly independent.

Proof

Assume that the functions \(\{e_i(t)f(t-x_i)\}_{i=1}^N\) are linearly dependent, so that for some coefficients \(\{c_i\}_{i=1}^N\) we have

$$\begin{aligned} \sum _{i=1}^N c_ie_if(t-x_i)= 0. \end{aligned}$$

Since f is continuous this equality holds for all \(t \in {{\,\mathrm{\mathbb {R}}\,}}^n.\) If we evaluate the left hand side at the point \(x_j\) we can rearrange to get the following inequality

$$\begin{aligned} |c_j||f(0)|&= \left| \sum _{i=1, i \ne j}^Nc_ie_i(x_j)f(x_j-x_i) \right| \\&\le \sum _{i=1, i \ne j}^N|c_i||f(x_j-x_i)|\\&<\frac{|f(0)|}{N-1}\sum _{i=1, i \ne j}^N|c_i|. \end{aligned}$$

After summing all these inequalities and canceling |f(0)| from each side, we see that

$$\begin{aligned} \sum _{j=1}^N |c_j| < \frac{1}{N-1}\sum _{j=1}^N\sum _{i=1, i \ne j}^N|c_i| = \sum _{j=1}^N |c_j| \end{aligned}$$

which is a contradiction. The last equality follows since each term \(|c_i|\) appears in exactly \(N-1\) of the inner sums in the second expression. \(\square \)

Now we can prove our first theorem.

Proof of Theorem 1

We can apply Lemma 1 with \(S=\{x_i\}_{i=1}^N\) and \(E = \{e^{2\pi i \omega _i \cdot t}\}_{i=1}^N.\) Since the points \(x_i-x_j\) all lie outside the ball of radius R around the origin, \(|f(x_i - x_j)| < \frac{|f(0)|}{N-1}\) as required. \(\square \)

Note that we only need to assume that the time coordinates of the points in \(\Lambda \) are spaced far apart for Theorem 1 to hold. Although the specific value f(0) suspiciously appears in our hypothesis, \(\mathcal {G}(f, \Lambda )\) is linearly independent if and only if \(\mathcal {G}(T_xf, \Lambda )\) is linearly independent for all \(x \in {{\,\mathrm{\mathbb {R}}\,}}^n,\) so we can always translate f to put the most advantageous value at the origin.

Given Theorem 1, it is straightforward to deduce Corollary 1.

Proof of Corollary 1

Since \(f \in C_0({{\,\mathrm{\mathbb {R}}\,}}^n)\) and \(f(0) \ne 0,\) we can find a value \(R>0\) such that \(|f(t)| < \frac{|f(0)|}{N-1}\) for all t outside of a ball of radius R around 0. Applying a dilation \(D_r,\) we see that \(|D_rf(t)| < \frac{|D_rf(0)|}{N-1}\) whenever t lies outside a ball of radius rR. Let \(M = \min _{i,j}||x_i-x_j||\) be the minimum distance between any two points in \(\Lambda .\) Then whenever \(0< r < \frac{M}{R}\) we can apply Theorem 1 to show that \(\mathcal {G}(D_rf, \Lambda )\) is linearly independent. \(\square \)

Since translations and modulations are exchanged under the Fourier transform, we get an analogous result in the frequency domain.

Corollary 2

Let \(f \in L^1({{\,\mathrm{\mathbb {R}}\,}}^n)\) so that \({\hat{f}} \in C_0({{\,\mathrm{\mathbb {R}}\,}}^n)\) and let \(\Lambda = \{(x_i,\omega _i)\}_{i=1}^N \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}.\) Then there exists a value \(r > 0\) such that \(\mathcal {G}(D_{r'}f, \Lambda )\) is linearly independent whenever \(r' > r.\)

Example 1

Consider the family of functions

$$\begin{aligned} f_{C, \omega } = {\left\{ \begin{array}{ll} \frac{\cos (\omega t)}{|t|} &{}\quad |t| \ge \frac{1}{C}\\ C \cos (\omega t)&{}\quad |t| < \frac{1}{C}. \end{array}\right. } \end{aligned}$$

The functions \(f_{C, \omega }\) are in \(L^2({{\,\mathrm{\mathbb {R}}\,}}) \cap C_0({{\,\mathrm{\mathbb {R}}\,}}).\) Nonetheless they decay slowly at infinity and oscillate in the tail. To the author’s knowledge, such functions are not covered by the results of [1, 2], or [11] which assume fast decay at infinity or ultimate positivity. Given \(\Lambda = \{(x_i,\omega _i)\}_{i=1}^N\) let \(M = \min _{i,j}|x_i-x_j|.\) Then by applying Theorem 1, we can see that \(\mathcal {G}(f_{C, \omega }, \Lambda )\) is linearly independent whenever \(C > \frac{N-1}{M}.\) For the four point set \(\Lambda ' = \{(0,0), (1,0), (0,1), (\sqrt{2}, \sqrt{2})\}\) we have \(\mathcal {G}(f_{\omega , C}, \Lambda ')\) linearly independent whenever \(C > \frac{3}{\sqrt{2} - 1}.\)

Example 1 suggests that the function \(f(t) = \frac{\cos (\omega t)}{|t|}\) should satisfy Conjecture 1 in full, as it is the pointwise limit of \(f_{C,\omega }\) as \(C \rightarrow \infty .\) This is true, and is implied by Theorem 2 which we are now ready to prove.

Proof of Theorem 2

Without loss of generality we may assume that \(p=0.\) If we fix \(\Lambda \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}\) of size N such that the minimum distance between the x-coordinates in \(\Lambda \) is R,  we would like to find a translate of f which satisfies \(|f(t+x)| < \frac{|f(x)|}{N-1}\) outside the ball of radius R around x. If we can find such an x then the argument in the proof of Lemma 1 applies to show \(\mathcal {G}(f, \Lambda )\) is linearly independent. To find such an x,  we first note that since f is bounded away from 0 we can find A such that \(|f(t)| < A\) outside a ball of radius \(\frac{R}{2}\) around 0. Since \(\lim _{t \rightarrow 0} |f(t)| = \infty ,\) we can find an x less than \(\frac{R}{2}\) such that \(|f(x)| > A(N-1),\) and this x satisfies the criteria described above. \(\square \)

Example 2

We can adapt the examples above to find functions in \(L^2({{\,\mathrm{\mathbb {R}}\,}})\) satisfying Conjecture 1. Consider the family of functions

$$\begin{aligned} g_\omega (t) = {\left\{ \begin{array}{ll} \frac{\cos (\omega t)}{|t|^{\frac{1}{4}}} &{}\quad |t| < 1 \\ \frac{\cos (\omega t)}{|t|} &{}\quad otherwise. \end{array}\right. } \end{aligned}$$

The functions \(g_\omega (t)\) are in \(L^2({{\,\mathrm{\mathbb {R}}\,}}) \cap C_0({{\,\mathrm{\mathbb {R}}\,}}).\) By Theorem 2, they satisfy Conjecture 1.

By applying the Short Time Fourier Transform (STFT) we can demonstrate linear independence when the points in \(\Lambda \) are sufficiently far apart in the time-frequency plane. For \(f,g \in L^2({{\,\mathrm{\mathbb {R}}\,}}^n)\) the STFT of f with respect to g is given by

$$\begin{aligned} V_gf(\lambda ) = \langle f, \pi (\lambda )g \rangle . \end{aligned}$$

It is easy to see [7] that \(V_gf \in C_0({{\,\mathrm{\mathbb {R}}\,}}^{2n})\) and satisfies the identity

$$\begin{aligned} V_g T_{u}M_{\eta }f(x, \omega ) = e^{-2 \pi i u \cdot \omega }V_gf(x-u, \omega - \eta ). \end{aligned}$$

Theorem 3

Suppose \(f,g \in L^2({{\,\mathrm{\mathbb {R}}\,}}^n)\) so that \(V_gf \in C_0({{\,\mathrm{\mathbb {R}}\,}}^{2n}).\) Let \(\Lambda = \{\lambda _i\}_{i=1}^N \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}\) and fix R so that \(|V_gf(\lambda )| < \frac{|V_gf(0)|}{N-1} = \frac{|\langle f, g \rangle |}{N-1}\) for all \(\lambda \) outside of the ball of radius R around the origin. If \(||\lambda _i - \lambda _j|| > R\) whenever \( i \ne j\) then \(\mathcal {G}(f,\Lambda )\) is linearly independent.

Proof

Suppose \(\mathcal {G}(f, \Lambda )\) is linearly dependent so that for some coefficients \(c_i\) we have

$$\begin{aligned} \sum _{i=1}^N c_i\pi (\lambda _i)f = 0. \end{aligned}$$

Then by applying the STFT with respect to g we have

$$\begin{aligned} \sum _{i=1}^N c_i'e^{-2 \pi i u_i \cdot \omega }V_gf(\lambda - \lambda _i) = \sum _{i=1}^N c_i'V_g\pi (\lambda _i)f = 0 \end{aligned}$$

where \(u_i\) denotes the time coordinate of \(\lambda _i\) and \(c_i' = e^{-2\pi i x_i \omega _i}c_i.\) However we can apply Lemma 1 to \(V_gf\) with \(S = \{\lambda _i\}_{i=1}^N\) and \(E = \{e^{-2 \pi i u_i \cdot \omega }\}_{i=1}^N\) to show that the functions \(\{e^{-2 \pi i u_i \cdot \omega }V_gf(\lambda - \lambda _i)\}_{i=1}^N\) must be linearly independent, which is a contradiction. \(\square \)

3 Discussion

Our Lemma 1 and Theorem 1 demonstrate that \(\mathcal {G}(f, \Lambda )\) is linearly independent when the points of \(\Lambda \) are far apart relative to the decay in f. However our proofs use no properties specific to the modulations \(e^{2 \pi i \omega t},\) and apply just as well to functions in \(L^p({{\,\mathrm{\mathbb {R}}\,}}^n)\) when \(n>1\) and \(p>2.\) Given the generality of Theorem 1 and in light of the following example, we can see that Theorem 1 alone provides only loose evidence for Conjecture 1.

Example 3

In [6] the authors demonstrate that the function

$$\begin{aligned} f(a,b) = \int _{\frac{1}{3}}^{\frac{2}{3}} exp(i(a\cos ^{-1}(t) + b\cos ^{-1}(1-t)))dt \end{aligned}$$

is in \(C_0({{\,\mathrm{\mathbb {R}}\,}}^2) \cap L^p({{\,\mathrm{\mathbb {R}}\,}}^2)\) for \(p > 4\) and satisfies the dependence

$$\begin{aligned} 2f(a,b) = f(a+1, b) + f(a-1, b) + f(a, b+1) + f(a, b-1). \end{aligned}$$

Nonetheless, our Theorem 1 and Corollary 1 can be applied to f,  though Theorem 1 clearly does not rule out the dependence above.

One could try to expand the utility of Theorem 3 by leveraging the choice of window function as a free variable. One could leave f and \(\Lambda \) fixed but vary the window function g in an attempt to satisfy the hypotheses. This leads naturally to the following question.

Question 1

Given \(f \in L^2({{\,\mathrm{\mathbb {R}}\,}}^n), R> 0, N > 0\) can we design a window \(g \in L^2({{\,\mathrm{\mathbb {R}}\,}}^n)\) so that \(|V_gf| < \frac{|\langle f, g \rangle |}{N}\) outside the ball of radius R around the origin?

A positive answer to Question 1 would prove the HRT conjecture. We would want to design g so that \(V_gf\) decreases sharply near the origin and then has a fat tail, since we know that the probability mass of \(V_gf\) cannot be too heavily concentrated near the origin due to various uncertainty principles for the STFT. Alternatively, it may be possible to develop a kind of uncertainty principle which answers Question 1 negatively.