A partial digestion of the HRT counterexample

A function ${f(t) \in L^2({\bf R})}$ of one variable can be translated in space by a spatial shift ${x}$ to obtain a new function

$\displaystyle \pi(x,0) f(t) := f(t-x),$

and also modulated in frequency by a frequency shift ${\omega}$ to obtain a new function

$\displaystyle \pi(0,\omega) f(t) := e^{2\pi i \omega t} f(t).$

One can compose these two operations to obtain a time-frequency shift:

$\displaystyle \pi(x,\omega) f(t) := \pi(0, \omega) \pi(x,0) f(t) = e^{2\pi i \omega t} f(t-x).$

As per the time-frequency uncertainty principle, the two shifts do not quite commute with each other. For instance, we have

$\displaystyle \pi(x, 0) \pi(0, \omega) = e^{-2\pi i \omega x} \pi(0, \omega) \pi(x, 0). \ \ \ \ \ (1)$

As such, ${\pi}$ is not a representation of the abelian group ${{\bf R}^2}$ , but rather a portion of the Weyl representation of the Heisenberg group, but we will not adopt a representation-theoretic perspective here.

Some functions obey finite linear relations between their time-frequency shifts. For instance, a sinusoid ${f(t) = A \sin(k t + \phi)}$ obeys the relation

$\displaystyle \pi(\frac{\pi}{k},0) f + f = 0.$

However, the Heil-Ramanathan-Topiwala (HRT) conjecture states that once one imposes some reasonable decay condition on ${f}$ , no such relations exist:

Conjecture 1 (HRT conjecture) If ${f \in L^2({\bf R})}$ is non-zero, then there is no relation of the form
$\displaystyle c_1 \pi(z_1) f + \dots + c_n \pi(z_n) f = 0 \ \ \ \ \ (2)$
for some distinct time-frequency shifts ${z_1,\dots,z_n \in {\bf R}^2}$ and some coefficients ${c_1,\dots,c_n \in {\bf C}}$ , not all zero.

A special case of the HRT conjecture, which was also open, makes the additional assumption that ${f}$ was Schwartz.

Many positive results towards this conjecture were known. I will mention only a few here. A simple case is when we only have frequency shifts rather than spatial shifts:

$\displaystyle c_1 \pi(0, \omega_1) f + \dots + c_n \pi(0, \omega_n) f = 0.$

In this case, the operator ${(c_1 \pi(0, \omega_1) + \dots + c_n \pi(0, \omega_n))}$ is simply a physical space multiplier

$\displaystyle c_1 \pi(0, \omega_1) f(t) + \dots + c_n \pi(0, \omega_n) f(t) = B(t) f(t)$

with symbol

$\displaystyle B(t) = c_1 e^{2\pi i \omega_1 t} + \dots + c_n e^{2\pi i \omega_n t}$

so that the relation (2) now takes the simple pointwise form

$\displaystyle B(t) f(t) = 0. \ \ \ \ \ (3)$

If the coefficients ${c_1,\dots,c_n}$ are not all zero, then ${B}$ is a non-zero analytic function and thus has isolated zeroes. It is thus not possible to solve this equation for any ${f \in L^2({\bf R})}$ . Thus the HRT conjecture is true when all the time-frequency shifts ${z_1,\dots,z_n}$ lie on the vertical axis. Using the metaplectic representation, one can then handle the case when all the ${z_1,\dots,z_n}$ are collinear.

What about the non-collinear case? Suppose first that all the ${z_j}$ lie in the lattice ${{\bf Z}^2}$ , thus ${z_j = (k_j, l_j)}$ for some integers ${k_j, l_j}$ . Here, the phase shift in (1) disappears, and all the time-frequency shifts ${\pi(k_j, l_j) = \pi(k_j,0) \pi(0,l_j)}$ commute with each other. This suggests that it should be possible to diagonalize the situation with a suitable transform to convert (2) to a pointwise equation similar to (3). To find this diagonalization, observe that if one restricts the function ${f : {\bf R} \rightarrow {\bf C}}$ to a coset ${s + {\bf Z}}$ of the integers, then ${\pi(0,l_j)}$ just multiplies the function by the scalar ${2^{2\pi i l_j s}}$ , while ${\pi(k_j, 0)}$ shifts the function on this coset by ${k_j}$ . The latter translation operation can also be converted to pointwise multiplication by performing the Fourier transform on the integers. Thus, if one introduces the Zak transform

$\displaystyle Zf(s,\nu) := \sum_{k \in {\bf Z}} f(s+k) e^{2\pi i k \nu}$

of ${f}$ then the equation

$\displaystyle c_1 \pi(k_1, l_1) f + \dots + c_n \pi(k_n, l_n) f = 0$

can be transformed after a brief calculation to the equation

$\displaystyle B(s,\nu) Zf(s,\nu) = 0$

where the symbol ${B(s,\nu)}$ is now given by the formula

$\displaystyle B(s,\nu) = c_1 e^{2\pi i (k_1 \nu + l_1 s)} + \dots + c_n e^{2\pi i (k_n \nu + l_n s)}.$

As before, if the coefficients ${c_1,\dots,c_n}$ are not all zero, then ${B}$ is a non-zero analytic function and thus non-zero almost everywhere. Thus ${Zf}$ has to vanish almost everywhere, which for ${f \in L^2({\bf R})}$ can be used to show that ${f}$ also vanishes.

More generally, there is a result of Linnell that the conjecture is true if ${z_1,\dots,z_n}$ lie in a translate of a discrete subgroup of ${{\bf R}^2}$ ; this (together with the argument handling the collinear case) establishes all cases where ${n \leq 3}$ , and several partial results involving the ${n=4}$ cases are also known. The conjecture is also known if ${f}$ is decays at a suitably super-exponential rate, by work of Bownik and Speegle.

I was aware of this conjecture through various talks and conversations with colleagues, and even briefly tried my hand at it for a while, though not with particularly serious effort (or progress). It was thus a nice surprise to see that it has just been resolved by Faulhuber, Petersen, van Velthoven, and Voigtlaender, even in the Schwartz case:

Theorem 2 There exist complex numbers ${c_1,\dots,c_{12}\in {\bf C}}$ , not all zero, distinct points ${z_1,\dots,z_{12} \in {\bf R}^2}$ , and a non-zero Schwartz function ${f_* \in \mathcal{S}({\bf R})}$ such that
$\displaystyle c_1 \pi(z_1) f_* + \dots + c_{12} \pi(z_{12}) f_* = 0.$

It is perhaps unsurprising that this result is AI-assisted. However, I think the authors have disclosed their AI use responsibly, with the final arguments written by hand with a readable overview of the argument, as well as proper discussion of methods, relation to past literature, and other independent numerical checks on the result.

The negative result lies only a little beyond the positive results: ${n}$ is now increased to ${12}$ , and all but one of the points ${z_1,\dots,z_{12}}$ lie in (a translate of) a discrete subgroup of ${{\bf R}^2}$ (in fact the explicit subgroup ${{\bf Z} \times \frac{1}{2}{\bf Z}}$ is used). The functions constructed are smooth and rapidly decaying, but not analytic or super-exponentially decaying, which would start being in conflict with the known positive results.

In addition to AI being used to come up with the initial proof strategy, a more traditional numerical computation was used to verify one step of the argument.

I have not had the time to do a full digestion of the result, but (after reading the introduction, and using a little AI assistance of my own) I was able to understand the main ideas at a high level. The first few reductions are relatively standard. Setting ${z_{12} = 0}$ and ${c_{12} = -c_*}$ , one can view the problem as one of solving an eigenvalue problem

$\displaystyle (c_1 \pi(z_1) + \dots + c_{11} \pi(z_{11})) f_* = c_* f_*.$

The time-frequency shifts ${z_1,\dots,z_{11}}$ are chosen to lie in a translate of the discrete subgroup ${{\bf Z} \times \frac{1}{2}{\bf Z}}$ by a certain irrational shift ${(\alpha, \beta/2)}$ . As mentioned previously, if in the shifts of a standard lattice ${{\bf Z} \times {\bf Z}}$ , it would be natural to work with the Zak transform of ${f_*}$ , but it turns out that the approach does not quite work when doing this for topological reasons (relating to the fact that scalar quasiperiodic functions of mean zero are forced to have zeroes), and so the authors used the slightly denser lattice instead ${{\bf Z} \times \frac{1}{2}{\bf Z}}$ , which relates to a vector-valued version of the Zak transform taking values in ${{\bf C}^2}$ rather than ${{\bf C}}$ . Here, the phase shift in (1) does not completely disappear, but becomes a sign change. This slight loss of abelianness means that we cannot hope to diagonalize the problem all the way to a scalar problem, but we can still hope to reduce it to a two-dimensional vector-valued problem. Indeed, by applying a suitable vector-valued version of the Zak transform, the eigenvalue problem can be transformed to a a “vector cocycle problem”

$\displaystyle B_*(z) F_*(z - \tau) = c_* F_*(z), \ \ \ \ \ (4)$

where ${F_* : {\bf R}^2 \rightarrow {\bf C}^2}$ is a non-zero smooth quasiperiodic vector-valued function, ${\tau}$ is an irrational shift ${\tau= (\alpha,\beta)}$ , and ${B_*(z)}$ is a certain explicit ${2 \times 2}$ matrix-valued function depending on the choices of ${c_1,\dots,c_{11}}$ , ${z_1,\dots,z_{11}}$ , and ${\tau}$ .

How to solve this equation? The motivating scenario here is if the matrix function ${B_*(z)}$ was replaced by a rank one function

$\displaystyle B_0(z) = \chi(z) \chi(z-\tau)^*$

for some smooth vector-valued function ${\chi : {\bf R}^2 \rightarrow {\bf C}}$ of unit magnitude. Then one could solve the equation by taking ${F_*(z) = \chi(z)}$ and ${c_* = 1}$ . It is not possible to make the function ${B_*}$ exactly of this form, but through some numerical computation and clever AI-assisted guesswork, the authors were able to find a choice of ${c_1,\dots,c_{11}}$ and ${z_1,\dots,z_{11}}$ , and ${\tau}$ that made ${B_*}$ approximately equal to a rank one function ${B_0}$ of this form, in fact getting a uniform estimate

$\displaystyle \sup_{z \in {\bf R}^2} \| B_*(z) - B_0(z) \|_{op} < \frac{1}{3}.$

As it turns out, such an approximation is sufficient to run a contraction mapping argument to find a solution to a variant of (4), namely

$\displaystyle B_*(z) v_*(z - \tau) = q_*(z) v_*(z)$

for some smooth ${v_* : {\bf R}^2 \rightarrow {\bf C}^2}$ and ${q_* : {\bf R}^2 \rightarrow {\bf C}}$ . (Here it was important to get the operator norm bound below ${\frac{1}{3}}$ ; they are barely able to do this, with a numerically obtained bound of ${0.333032}$ , though this bound might not be optimal.)

The main remaining obstacle is that the “eigenvalue function” ${q_*(z)}$ is varying in the parameter ${z}$ rather than constant. (This issue was, by the way, anticipated to some extent in previous work of Demeter, who observed that eigenfunctions of the almost Matthieu discrete Schrödinger operator gave a near-miss counterexample to the HRT conjecture, but with an eigenvalue that depended on an auxiliary phase shift parameter rather than constant.) However, if one was able to solve the scalar cocycle equation

$\displaystyle q_*(z) h(z-\tau) = c_* h(z) \ \ \ \ \ (5)$

for some smooth ${h : {\bf R}^2 \rightarrow {\bf C}}$ , then one could solve the equation (4) by setting ${F_*(z) = h(z) v_*(z)}$ . The approach to solve (5) is standard: take logarithms, apply a Fourier transform, and then divide out by the multiplier associated to the ${\tau}$ shift. This can cause a well-known “small divisor” problem (which arises in various dynamical contexts, such as in the KAM theorem) if ${\tau}$ behaves too much like a rational vector, but the standard resolution to this is to select a shift ${\tau}$ that obeys good Diophantine approximation properties. For the purposes of numerics the authors selected an extremely concrete shift, namely

$\displaystyle \tau = (2^{1/3} - 1, 2^{2/3} - 1)$

but I get the impression that the exact choice here was not crucial for the argument, and that many other irrational algebraic numbers could have worked here.