Terrence Tao

Udruženi sadržaj What's new
Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao
Ažurirano: prije 6 dana 8 sati

Palomar – a registry of Lean verified mathematics

Sri, 2026-08-19 03:40

In recent months there has been a proliferation of AI-generated proofs of various old and new results, some of which have been formalized in the proof assistant language Lean. However, checking that a given Lean repository actually proves the claimed statement is somewhat non-trivial, especially for an audience which is not expert in the use of Lean: one has to first check that the claimed formal Lean statements have proofs that typecheck, that the proofs do not contain any “cheats” such as adding additional axioms, and that the formal statements also match (in a semantic sense) the informal description of the claimed results.

To help bring some clarity to this situation, I am happy to announce that Palomar registry of Lean verified mathematics, which is an initiative incubated by the Lean FRO and by ICARM, is now open for submissions. I am serving in several roles on this registry, including on the scientific advisory board, together with Jeremy Avigad, Matthew Ballard, Jaume de Dios, Nestor Guillen, Bryna Kra, Kim Morrison, Ravi Vakil, and Akshay Venkatesh.

A detailed motivation for Palomar can be found here, and further information about Palomar can be found here. A zeroth approximation of what Palomar intends to be is the analogue of a preprint server for Lean proofs. More precisely, Palomar (which is named after the astronomical observatory) is a registry of external Github repositories (or more precisely, “snapshots” of such repositories, as represented by a specific Github commit) containing Lean code adhering to the current best practices for such formalizations, in particular containing

  • A “challenge file” containing a short, human readable description in Lean of the results claimed.
  • A “solution module” containing an (arbitrarily long) proof of the results claimed in the challenge file.
  • A “formalization.yaml” file describing the results in informal language, and also containing a number of other relevant metadata and disclosures.

(There are also some additional technical requirements for the repository which I will omit here.) If a snapshot of a repository is submitted to Palomar, it will check both (a) that the solution module typechecks and proves exactly the results claimed in the challenge file, and that (b) the informal description of the result in the formalization.yaml file appears to match the result claimed in the challenge file, and that the repository meets various minimal standards required for a registry entry. The first check (a) is purely mechanical, using the Lean tool Comparator; the second check (b) is non-deterministic, being performed by a large language model. If a repository passes both checks, it can be registered on Palomar. It is worth stressing that the checks in (a) and (b) fall well short of what a proper human peer review of a submission for novelty, interest, and accuracy would give; in particular, Palomar is not a peer-reviewed journal.

The submission process is thorough, but achievable: as a test, I successfully managed to submit my own recent formalization of the proof of Sendov’s conjecture to Palomar, and also plan to submit some older formalizations to the registry soon.

In any event, the registry is now open for formalizations of both old and new results. Submissions (whether human-generated, AI-generated, or some mixture of both) are welcome; please read the (somewhat detailed) instructions here before starting a submission. (I will however note that modern AI agents are quite helpful in assisting with the mechanical details of the submission, though a human review is still strongly recommended.)

Discussion and feedback on Palomar will occur on this Zulip channel.

Kategorije: Matematički blogovi

A digestion of the proof of Sendov’s conjecture

Čet, 2026-08-13 00:10

This post concerns the following conjecture of Sendov, as well as its strengthening by Phelps–Rodriguez:

Conjecture 1 (Sendov’s conjecture) Let , and let be a degree polynomial with all zeroes in the unit disk. Then for every zero of , there exists a critical point of with .

Conjecture 2 (Phelps–Rodriguez conjecture) Let , and let be a degree polynomial with all zeroes in the unit disk. Then for every zero of , there exists a critical point of with , unless is on the unit circle and is a scalar multiple of .

By applying a rotation around the origin, we can normalize to be a real number with .

From the work of Rubinstein, both conjectures were already established in the case, so one can restrict to the case. Both of these conjectures then follow from

Conjecture 3 (Sendov’s conjecture in interior) Let . Let be a degree polynomial with all zeroes in the unit disk. Then if is a zero of , there exists a critical point of with .

All three of these conjectures were established for (in a sequence of papers culminating in this paper of Brown and Xiang) and for sufficiently large (in a paper of myself, which in turn built upon several partial results in this setting). This left the case of intermediate to be settled. My arguments used some qualitative ingredients (most notably analytic continuation) and as such did not easily lend themselves to quantifying the threshold of above which the argument was valid.

Recently, Lech Mazur was able to use an AI tool to resolve Sendov’s conjecture for all , with the proof verified in Lean. However, the AI-generated proof was not human-digested to be in the form of a publication-ready preprint; and it has taken me several days (with heavy AI assistance) to perform such a digestion, to place the proof in proper context with previous literature and to simplify and streamline the argument to highlight the main ideas. (Note: the above chat log only represents a portion of the digestion work: the rest was performed with pen and paper, or using some further AI agents.) The same arguments also give a new proof of Rubinstein’s theorem, which I also give below the fold.

One consequence of this digestion is that the argument in fact demonstrates Conjecture 3, and thus resolves both the Sendov conjecture and the Phelps–Rodriguez conjecture in full generality.

The proof ends up being remarkably elementary. No complex analysis is used other than the fundamental theorem of algebra (and very basic facts about Möbius transformations); and the deepest inequality used as input is the Maclaurin inequality (and we only need a special case of that inequality which can be derived from the arithmetic mean-harmonic mean inequality and an induction argument).

Using an AI agent, I have been able to formalize the entire argument in Lean, extended to by some minor modifications to the proof. This formalization is more streamlined than the original formalization (it has about 15,000 lines of code, compared with around 90,000 for the original proof).

We now prove Conjecture 3. The cases have long been known but need to be treated separately; a short proof using the machinery developed here is provided at the end of the post. Suppose now that we have a counterexample for some , thus one can find a degree polynomial with zeroes

for some and , in the closed unit disk, whose critical points all lie a distance at least from . We use notation here in the non-asymptotic sense, thus means that for some absolute constant (independent of ). We will also use the notation to denote a quantity that is bounded in magnitude by .

To capture the fact that the critical points lie at a distance at least from , we write these critical points as

for some (non-zero) in the closed unit disk.

Example 4 If and , then are the non-trivial roots of unity, while the are all equal to . Strictly speaking this is not actually a counterexample to Conjecture 3, because is not strictly less than one; nevertheless this is an important motivating near-counterexample for the arguments below.

Example 5 A generalization of the previous example was studied in Section 4 of my paper. Here one took

where was an asymptotic parameter going to infinity,

was a low-degree polynomial for some ,

and were constants. This polynomial has a zero at , critical points at , and additional critical points near . If all the critical points were at distance at least one from , one would have

and

while if all the zeroes were in the unit disk, the calculations in my paper showed that

Here denotes a quantity that goes to zero as . If one ignores the errors, one can show that these conditions are only simultaneously feasible if and all the vanish, but the argument was somewhat subtle (I had to proceed by inspecting the second Fourier coefficient of (1)). This illustrates the fact that the regime is particularly delicate.

We now have two sets of points in the closed unit disk: and . They “communicate” with each other through the polynomial and its first derivative , both of which can be expressed in terms of either set of points (as well as and ). Indeed, if we normalize to be monic, then we can factor in terms of the zeroes as

and thus upon differentiating

Here and in the sequel we adopt the convention of removing singularities when dealing with expressions that involve multiplication by both and , by cancelling such terms first in the event that .

In a similar vein, can be factored

and thus on integrating (and using )

It is convenient to rule out the easy case right away. In this case we see from (3), (4) that

which is absurd since the first product has magnitude at most one, and the second product has magnitude at least one. Thus we can assume henceforth that .

By inspecting or at various natural locations, we can thus obtain a number of identities relating the to the . We record the ones that we actually need here:

Lemma 6 (Communication identities) Let denote the function

  • (i) (Centroid identity) We have

    That is to say, the centroid of the zeroes equals the centroid of the critical values.
  • (ii) (Polar identity) We have

  • (iii) (First origin identity) We have

  • (iv) (Second origin identity) We have

    (Again, we are using the convention of removing singularities to deal with the case where some of the vanish.)

Proof: For (i), we inspect the behavior of as . From (2) we have

and thus on differentiating term by term

Meanwhile, from (4) we have

Comparing coefficients, we obtain the claim.

For (ii), we consider the expression . On the one hand, from (2), (3) one has

(Note from hypothesis that cannot be a critical point, so the denominator is non-zero.) On the other hand, from (4), (5) one has

Equating the two identities, we obtain (ii) after some algebra.

For (iii), we evaluate . From (2) we have

while from (5) we have

Equating the two identities, we obtain (iii) after some algebra using (6).

For (iv), we similarly evaluate . From (3) we have

while from (4) one has

Equating the two identities, we obtain (iv) after some algebra using (6).

Remarkably, the polynomial will play no further role in the argument: the identities in (i)-(iv), together with the hypotheses that and lie in the closed unit disk, will be sufficient by themselves to obtain a contradiction.

Example 7 Continuing the example in Example 4, in (i) both sides vanish. In (ii), both sides are equal to one. For (iii) and (iv), we have , with both sides of (iii) equal to one, and both sides of (iv) equal to zero.

Remark 8 The centroid identity is extremely classical, going back to this 1948 paper of Popoviciu. The comparison of the polynomial at a location and at the polar inversion of that location across the closed unit disk is a familiar trick in the literature; see, e.g., Lemma 5 and Theorem 8 of Dégot. The specific form of the polar identity is implicit in the first part of Section 5 of Mazur’s AI-generated proof, while the origin identities are extracted from equation (6.3) of that proof. The first origin identity is also very close to Theorem 6 of Dégot, while the second origin identity is similar to some identities appearing in the proof of Lemma 6 of Dégot, as well as the work of Mir–Nazir–Wani and (in the case) Rubinstein. The work of Meir–Sharma and Mir–Nazir–Wani also contain several further identities relating the to the ; see in particular Lemma 15 below. Variants of (5) also appear in Proposition 10 of Miller.

Remark 9 The first origin identity (9) is already strong enough to handle asymptotically all examples of the form in Example 5, except in the endpoint case where vanish and the are all . Indeed, as the are in the closed unit disk, (9) implies that

On the other hand, routine calculations (omitted here) show that

leading asymptotically to the constraint

But all terms here are non-negative (since ), so this forces a contradiction unless (and hence also ) and the all vanish.

As mentioned in Example 5, the most delicate regime occurs when . It is convenient to introduce the normalized version

of , thus , and the case corresponds to . Informally, measures how close is to (at the scale of ).

A key role in the argument will be played by the mean

of the , particularly the real part . As the all lie in the unit disk, the mean does also, so that

and

On the other hand, in the example in Example 4, is equal to the extremal value of , and . In Example 5, we have (and ).

It will be convenient to work with the quadratic polynomial

with a particular emphasis on the value at :

One should primarily think of as a measure of how close is to . Clearly we have

for all (note that is strictly less than ).

The arguments will revolve around the relationship between and . Specifically, we will establish the following two inequalities below the fold. The first inequality, which we call the “polar inequality”, comes in three forms:

Proposition 10 (Polar inequality)
  • (i) (Raw polar inequality) We have

  • (ii) (Polar inequality in , form) We have

  • (iii) (Simplified polar inequality) We have

    In particular, since , one has

It will be the inequality (18) that we use in practice, but it will be derived from (17), which in turn is a consequence of (16), which will follow from the polar identity (8) together with the fact that the and lie in the unit disk. The bound (18) is only slightly weaker than (17); see the (Gemini-generated) image below.

I was not able to find an exact duplicate of the above polar inequalities in past literature, but the paper of Dégot contains several similar inequalities. The inequality (16) was extracted from (5.1) of Mazur’s AI-generated proof; the subsequent bounds (17), (18) arose from my attempts to simplify the arguments after that point.

The second inequality, which is more difficult, also will come in several forms:

Proposition 11 (Origin inequality) Let .
  • (i) (Raw origin inequality) We have

  • (ii) ( bound) We have

  • (iii) (Origin inequality in , form) We have

Part (i) (which was extracted with some effort from Section 6 of the original AI-generated argument) will be deduced from the first and second origin identities (9), (10), as well as the centroid identity (7). Part (ii) will follow from (i) and the polar inequality (18), while part (iii) is an elementary consequence of (i).

As it turns out, the last three terms in (21) are asymptotically negligible as . Dropping those terms gives a competing feasibility region for and which is disjoint from the one coming from the polar inequality (17) (or (18)):

This already suggests that one can use this approach to recover my previous result on Sendov’s conjecture holding for all sufficiently large . In fact, even with the three error terms in (21) added, there is enough room between the two inequalities (18), (21) to obtain a contradiction for all (using the additional bound to control these errors), although showing this for medium-sized (such as ) requires a certain amount of computer assistance.

For fixed , the right-hand side of (21) is monotone increasing in (or equivalently, monotone decreasing in ). In view of (18), we can thus replace by in this inequality, so that is replaced by

and replaced by . The inequality (21) then becomes an inequality involving only and :

We also note that the bounds force the constraint

This prevents from getting too close to the upper limit (or getting too close to zero).

We can now eliminate all large degrees, e.g., , as follows. The quadratic attains its minimum at . For we have

while for (if this region is non-vacuous) we can bound the quadratic by its value at . Thus

Evaluating these expressions, we arrive at

Since , we have . Next, we claim that . As is monotone increasing in , it suffices to do this when . Here one can directly compute that

since the discriminant of the numerator is negative, we conclude that

as desired.

Dropping some and terms, we conclude that

Every term on the right-hand side can be seen to be decreasing in for . Thus the right-hand side can be bounded by

giving the desired contradiction.

The remaining range to handle is when

It turns out that (22) remains infeasible in this range. This can be illustrated numerically without much difficulty: see this applet. For instance, in the most delicate case , the right-hand side of (22) only gets as large as (and in particular stays below ) throughout the range :

I have also verified this bound in Lean.

— 1. The polar inequality —

We begin with a proof of Proposition 10.

As is well known, the Möbius transform maps the closed unit disk to itself. In particular, we have

for all of the zeroes . Inserting this into the polar identity (8) and using the triangle inequality, we conclude the lower bound

We now convert this bound to a bound involving the quantity in (12). From the arithmetic mean-geometric mean inequality we have

and from (12) we have

Since , we thus have

giving the raw polar inequality (16).

Bounding by and using the quantities from (11), (15), we observe that

Using the basic inequality , we thus have

with strict inequality for . From (16) we conclude (17). This also implies , since otherwise the integrand is always bounded by , which is absurd.

On evaluating the integral in (17), we obtain

and thus

so on taking logarithms we obtain

It remains to establish the bound

Here we use an AI-generated argument. One can directly calculate

where and . If we can show that

for all , then taking logarithms in (17) yields

from which (26) will follow by routine algebra.

Both sides of (27) vanish at . Taking derivatives, it suffices to show that

which rearranges to

To expand the left-hand side, we use the double angle formulae and

to rewrite it as

Collecting the coefficient of for and extracting a common factor of , one is left with

where . (The remaining coefficients, which also receive contributions from the polynomial terms, all vanish.) Thus the left-hand side has the Taylor expansion

in which every coefficient is non-negative, giving the claim.

Remark 12 As the image in the introduction suggests, the bound (18) is only slightly weaker than (17). For small , one can perform Taylor approximation on the latter bound to obtain

while the former bound is

Note that is slightly smaller than .

Relating to this, the constant in (27) cannot be improved.

— 2. The origin inequality —

Now we turn to the proof of Proposition 11, which is more difficult and revolves around an analysis of the function defined in (6). We begin with a heuristic analysis. Inserting the approximation for small into (6) and using (12), we are led to the approximation

at least when is small (which turns out to be the dominant regime in applications). This suggests a relation

between the two expressions involving in the origin identities in Lemma 6. Substituting in this approximation, we obtain some (slightly complicated) approximation for the sum in terms of , , , , and the product .

As lie in the closed unit disk, the product does also. However, past experience with the Sendov conjecture has taught us that the worst cases tend to be when lie very close to the boundary of the disk, so that is close to one. For instance, in Example 4 all the and lie on the unit circle, and . See Remark 3 of Dégot or Theorem 1.10(ii) of my own paper for other places where this heuristic is noted. To simplify the discussion, let us assume for now that is exactly one, so that all lie on the unit circle. This leads in particular to the inversion identities

The centroid identity in Lemma 6(i) relates the sum of the with the sum of the . Using (31), this gives a similar identity relating the sum of the with the sum of the . The latter sum is of course just . This combines well with the previous approximation, thus giving an approximate identity relating , to , , and . As it turns out, the roles of and are minor and can be quickly eliminated for the purposes of obtaining useful bounds, leading eventually to the relation in Proposition 11.

We turn to the details. To make the approximation (30) more precise, we note that , and hence by the fundamental theorem of calculus

The heuristic (29) predicts that , which would give (30). If we actually differentiate (6) carefully, we obtain the exact identity

Bounding , we write this

When faced with a similar expression in (24), we used the arithmetic mean-geometric mean inequality. Here, the analogous tool is Maclaurin’s inequality, which gives

and hence by Cauchy–Schwarz

Repeating the calculations used to show (25), we have

and so we obtain the bound

Integrating this, we obtain a rigorous analogue of (30),

and thus by the triangle inequality

From the first and second origin identities (9), (10) we have

The next step is thus to estimate . When , then all the were on the unit circle and we could use (31) (and the centroid identity) to proceed. Now, we are no longer assuming to equal , but we can still adapt the previous arguments with a loss proportional to . The key lemma is

Lemma 13 (Defect lemma) Let be some points in the closed unit disk. Then

Proof: By a limiting argument we may assume that none of the vanish. If we write for some , then we can calculate that

and

Thus the desired inequality reduces to the superadditivity property

But from the sinh addition formula we have

for all non-negative (this also follows from the convex nature of together with ), and the claim follows by induction.

We remark that the lemma can also be proven by direct induction, without an appeal to hyperbolic trigonometry.

From taking complex conjugates of the centroid identity (7) and performing some algebra, we have

Using the defect lemma (applied to the points ) and the triangle inequality we conclude that

where as before we are removing singularities when some of the vanish. Applying (12) and some algebraic manipulation, we arrive at

Substituting this back into (33), we conclude that

and hence after some algebra and the triangle inequality

Inserting this into (32), we obtain

We can simplify (34) by reducing to the case. Indeed, we shall show that

which implies that the right-hand side of (34) is non-decreasing in in the range . Thus we may replace by in (34) to conclude that

Let us now verify (35). Using and the triangle inequality, we can lower bound

Inserting this into (35) and clearing denominators, we reduce after some algebra to

But as a quadratic polynomial in , the left-hand side has discriminant , which one can check to be negative for sufficiently large (in fact suffices), giving the claim (35).

Next we eliminate the role of the imaginary term . Observe for any complex number with positive real part that

as can be seen by squaring both sides. The expression has real part

which lies between and (in particular, it is positive), and imaginary part of magnitude at most

by (13). We conclude that

The right-hand side can be rearranged using the quantity from (11) as

so the bound (36) gives (19).

— 2.1. Upper bound on —

Now we can prove (20). Suppose for contradiction that ; since , this implies that . Crudely discarding the term in (19) and bounding by , we have

The quadratic polynomial equals at and attains its minimum at with value . By convexity, we thus have

for and

for (this latter statement is vacuous if ). Since , we can therefore crudely bound

and hence

From (15) we have , thus by (18) one has

From another application of (18) one has

We conclude that

It is now convenient to introduce the quantity , thus with

and

Inserting these bounds and dividing by , we conclude

Since , we obtain

Since and , we conclude that

Routine calculus shows that has a maximum of at most , and that the right-hand side here is at most , giving the required contradiction. This proves (20).

— 2.2. A simplified estimate —

Now we show (21). Note from (11) that

while from (15) we have

and hence also

From (15) we have

By the mean value theorem (noting that is non-negative) we thus have

From the standard beta function identity

(and the fact that ) we can thus replace (19) by

From (15) we have

Thus by (37), (38), (39)

Dividing by the positive quantity gives the claim.

— 3. Rubinstein’s theorem —

We now adapt the arguments to give a proof of Rubinstein’s theorem that the Phelps–Rodriguez conjecture holds in the case, i.e.,

Theorem 14 (Rubinstein’s theorem) Let , and let be a degree polynomial with all zeroes in the unit disk. If , then there exists a critical point of with , unless is a scalar multiple of .

The argument here is essentially in Remark 5.1 of this paper of Tang and Zhang.

Taking contrapositives, we may assume that the critical points are of the form for some in the closed unit disk, and normalize to be monic; our task is to show that .

The polar identity (8), based on calculating degenerates to a triviality when , but we have the following usable substitute, valid for any choice of , first observed in equation (3.2) of Meir–Sharma:

Lemma 15 (Meir–Sharma identity) If and the critical points are of the form then all the zeroes are not equal to , and

Proof: By hypothesis, is not a critical point of , so and for all . Instead of computing , we instead consider the expression . On the one hand, from (4) we have

while from differentiating (4) we have

Meanwhile, from (3) we have

and from differentiating (3) we have

Using these identities to compute in two different ways gives the claim.

Now take . Since lie in the closed unit disk, has real part at least , while is at most . Thus, the only way that the above identity can hold is if for all , hence for all . Thus all critical points are at the origin, which forces for some . Since , we conclude that , giving the claim.

— 4. The cases —

We now prove the cases of Conjecture 3. The starting point is (23). Using the triangle inequality and , this implies that

(This also follows from (16) and .) From Hölder’s inequality and we conclude that

The right-hand side can be computed to equal

which is obviously less than for , giving the contradiction.

Remark 16 The same argument also works for , but breaks down for higher .

— 5. Further directions —

The Sendov and Phelps–Rodriguez conjectures are now resolved, but several related conjectures remain open. The following strengthening of Sendov’s conjecture, by Borcea, is open for any :

Conjecture 17 (Borcea conjecture) Let and , and let be a degree polynomial with zeroes satisfying . Then for every zero of , there exists a critical point of with .

Sendov’s conjecture is the limiting case of this conjecture. There has been relatively little progress on this conjecture: the cases were established by Khavinson, Pereira, Putinar, Saff, and Shimorin, and in this previous paper we reported the negative result that AlphaEvolve failed to find a counterexample to the conjecture. The proof methods here do not seem to extend easily; all the identities relating zeroes and critical points continue to hold, but now that the are only constrained to the unit disk in an averaged moment sense, all of the inequalities developed above now fail.

Another strengthening of Sendov’s conjecture that remains open is Schmeisser’s conjecture:

Conjecture 18 (Schmeisser’s conjecture) Let , and let be a degree polynomial with all zeroes in the closed unit disk. Then for any in the convex hull of the zeroes of , there exists a critical point of with .

Schmeisser proved several special cases of this conjecture, and AlphaEvolve again failed to find a counterexample, but there has not been much further progress. Here, the are now back in the closed unit disk, but we no longer have , again rendering most of the previous identities invalid. But perhaps some modification of the arguments here can make some progress on this conjecture.

A common generalization of the Borcea and Schmeisser conjectures was proposed in Conjecture 2.4 of this paper of Zhang. A slightly different strengthening was also proposed in Conjecture 1.10 of Tang and Zhang:

Conjecture 19 (Tang–Zhang conjecture) Let , and let be a degree polynomial with all zeroes in the closed unit disk and critical points . Then for any , one has .

Sendov’s conjecture is the limiting case . By Hölder’s inequality, the case is the strongest form of the conjecture.

Another well known variant of Sendov’s conjecture is Smale’s problem:

Conjecture 20 (Smale’s problem) Let , and let be a degree polynomial. Then for any zero of , there exists a critical point of with .

The constant is best possible, as can be seen by the example and . Using the Koebe one-quarter theorem, Smale proved this conjecture with replaced by . Some slight improvements of this bound have been obtained over the years; for instance for , the improved bound of was obtained by Crane. Again, AlphaEvolve failed to find a counterexample to this conjecture. This problem does not seem to have a direct relationship with Sendov’s conjecture, and there is no useful normalization of the zeroes and critical points that is confined to the unit disk. Nevertheless there may be some hope of making progress on this conjecture, perhaps working first in the asymptotic regime .

Needless to say, I did try some desultory attempts to use AI tools to attack these questions, but without much notable success.

One potential way forward is to find further proofs of Sendov’s conjecture that utilize other techniques that might be more broadly applicable to this larger family of problems. The proof here is remarkable in that the zeroes and critical points are treated almost as independent mathematical objects, communicating with each other only very narrowly through four identities in which one only inspects the underlying polynomial (and its derivative) at a small number of points. It could be that an approach focusing on more global features of the polynomial may lead to new proofs of Sendov’s conjecture, and perhaps also of its generalizations.

Kategorije: Matematički blogovi

A partial digestion of the HRT counterexample

Čet, 2026-08-06 19:26

A function of one variable can be translated in space by a spatial shift to obtain a new function

and also modulated in frequency by a frequency shift to obtain a new function

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

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

As such, is not a representation of the abelian group , 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 obeys the relation

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

Conjecture 1 (HRT conjecture) If is non-zero, then there is no relation of the form

for some distinct time-frequency shifts and some coefficients , not all zero.

A special case of the HRT conjecture, which was also open, makes the additional assumption that 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:

In this case, the operator is simply a physical space multiplier

with symbol

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

If the coefficients are not all zero, then is a non-zero analytic function and thus has isolated zeroes. It is thus not possible to solve this equation for any . Thus the HRT conjecture is true when all the time-frequency shifts lie on the vertical axis. Using the metaplectic representation, one can then handle the case when all the are collinear.

What about the non-collinear case? Suppose first that all the lie in the lattice , thus for some integers . Here, the phase shift in (1) disappears, and all the time-frequency shifts 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 to a coset of the integers, then just multiplies the function by the scalar , while shifts the function on this coset by . 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

of then the equation

can be transformed after a brief calculation to the equation

where the symbol is now given by the formula

As before, if the coefficients are not all zero, then is a non-zero analytic function and thus non-zero almost everywhere. Thus has to vanish almost everywhere, which for can be used to show that also vanishes.

More generally, there is a result of Linnell that the conjecture is true if lie in a translate of a discrete subgroup of ; this (together with the argument handling the collinear case) establishes all cases where , and several partial results involving the cases are also known. The conjecture is also known if 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 , not all zero, distinct points , and a non-zero Schwartz function such that

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: is now increased to , and all but one of the points lie in (a translate of) a discrete subgroup of (in fact the explicit subgroup 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 and , one can view the problem as one of solving an eigenvalue problem

The time-frequency shifts are chosen to lie in a translate of the discrete subgroup by a certain irrational shift . As mentioned previously, if in the shifts of a standard lattice , it would be natural to work with the Zak transform of , 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 , which relates to a vector-valued version of the Zak transform taking values in rather than . 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”

where is a non-zero smooth quasiperiodic vector-valued function, is an irrational shift , and is a certain explicit matrix-valued function depending on the choices of , , and .

How to solve this equation? The motivating scenario here is if the matrix function was replaced by a rank one function

for some smooth vector-valued function of unit magnitude. Then one could solve the equation by taking and . It is not possible to make the function exactly of this form, but through some numerical computation and clever AI-assisted guesswork, the authors were able to find a choice of and , and that made approximately equal to a rank one function of this form, in fact getting a uniform estimate

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

for some smooth and . (Here it was important to get the operator norm bound below ; they are barely able to do this, with a numerically obtained bound of , though this bound might not be optimal.)

The main remaining obstacle is that the “eigenvalue function” is varying in the parameter 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

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

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.

Kategorije: Matematički blogovi