skip to main content

Title: Integral operators, bispectrality and growth of Fourier algebras
Abstract In the mid 1980s it was conjectured that every bispectral meromorphic function {\psi(x,y)} gives rise to an integral operator {K_{\psi}(x,y)} which possesses a commuting differential operator.This has been verified by a direct computation for several families of functions {\psi(x,y)} where the commuting differential operator is oforder {\leq 6} . We prove a general version of this conjecture for all self-adjoint bispectral functions of rank 1and all self-adjoint bispectral Darboux transformations of the rank 2 Bessel and Airy functions.The method is based on a theorem giving an exact estimate of the second- and first-order terms ofthe growth of the Fourier algebra of each such bispectral function. From it we obtaina sharp upper bound on the order of the commuting differential operator for theintegral kernel {K_{\psi}(x,y)} leading to a fast algorithmic procedurefor constructing the differential operator; unlike the previous examples its order is arbitrarily high.We prove that the above classes of bispectral functions are parametrized by infinite-dimensionalGrassmannians which are the Lagrangian loci of the Wilson adelic Grassmannian and its analogsin rank 2.  more » « less
Award ID(s):
Author(s) / Creator(s):
Date Published:
Journal Name:
Journal für die reine und angewandte Mathematik (Crelles Journal)
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Beginning with the work of Landau, Pollak and Slepian in the 1960s on time‐band limiting, commuting pairs of integral and differential operators have played a key role in signal processing, random matrix theory, and integrable systems. Previously, such pairs were constructed by ad hoc methods, which essentially worked because a commuting operator of low order could be found by a direct calculation. We describe a general approach to these problems that proves that every pointWof Wilson's infinite dimensional adelic Grassmannian gives rise to an integral operator , acting on for a contour , which reflects a differential operator with rational coefficients in the sense that on a dense subset of . By using analytic methods and methods from integrable systems, we show that the reflected differential operator can be constructed from the Fourier algebra of the associated bispectral function . The exact size of this algebra with respect to a bifiltration is in turn determined using algebro‐geometric methods. Intrinsic properties of four involutions of the adelic Grassmannian naturally lead us to consider the reflecting property above in place of plain commutativity. Furthermore, we prove that the time‐band limited operators of the generalized Laplace transforms with kernels given by the rank one bispectral functions always reflect a differential operator. A 90° rotation argument is used to prove that the time‐band limited operators of the generalized Fourier transforms with kernels admit a commuting differential operator. These methods produce vast collections of integral operators with prolate‐spheroidal properties, associated to the wave functions of all rational solutions of the KP hierarchy vanishing at infinity, introduced by Krichever in the late 1970s.

    more » « less
  2. Commuting integral and differential operators connect the topics of signal processing, random matrix theory, and integrable systems. Previously, the construction of such pairs was based on direct calculation and concerned concrete special cases, leaving behind important families such as the operators associated to the rational solutions of the Korteweg–de Vries (KdV) equation. We prove a general theorem that the integral operator associated to every wave function in the infinite-dimensional adelic Grassmannian G r a d of Wilson always reflects a differential operator (in the sense of Definition 1 below). This intrinsic property is shown to follow from the symmetries of Grassmannians of Kadomtsev–Petviashvili (KP) wave functions, where the direct commutativity property holds for operators associated to wave functions fixed by Wilson’s sign involution but is violated in general. Based on this result, we prove a second main theorem that the integral operators in the computation of the singular values of the truncated generalized Laplace transforms associated to all bispectral wave functions of rank 1 reflect a differential operator. A 9 0 ○ rotation argument is used to prove a third main theorem that the integral operators in the computation of the singular values of the truncated generalized Fourier transforms associated to all such KP wave functions commute with a differential operator. These methods produce vast collections of integral operators with prolate-spheroidal properties, including as special cases the integral operators associated to all rational solutions of the KdV and KP hierarchies considered by [Airault, McKean, and Moser, Commun. Pure Appl. Math. 30, 95–148 (1977)] and [Krichever, Funkcional. Anal. i Priložen. 12, 76–78 (1978)], respectively, in the late 1970s. Many examples are presented. 
    more » « less
  3. Lysyanskaya, Anna ; Handschuh, Helena (Ed.)
    We study the black-box function inversion problem, which is the problem of finding x[N] such that f(x)=y, given as input some challenge point y in the image of a function f:[N][N], using T oracle queries to f and preprocessed advice 01S depending on f. We prove a number of new results about this problem, as follows. 1. We show an algorithm that works for any T and S satisfying TS2maxST=(N3) . In the important setting when ST, this improves on the celebrated algorithm of Fiat and Naor [STOC, 1991], which requires TS3N3. E.g., Fiat and Naor's algorithm is only non-trivial for SN23 , while our algorithm gives a non-trivial tradeoff for any SN12 . (Our algorithm and analysis are quite simple. As a consequence of this, we also give a self-contained and simple proof of Fiat and Naor's original result, with certain optimizations left out for simplicity.) 2. We show a non-adaptive algorithm (i.e., an algorithm whose ith query xi is chosen based entirely on and y, and not on the f(x1)f(xi−1)) that works for any T and S satisfying S=(Nlog(NT)) giving the first non-trivial non-adaptive algorithm for this problem. E.g., setting T=Npolylog(N) gives S=(NloglogN). This answers a question due to Corrigan-Gibbs and Kogan [TCC, 2019], who asked whether it was possible for a non-adaptive algorithm to work with parameters T and S satisfying T+SlogNo(N) . We also observe that our non-adaptive algorithm is what we call a guess-and-check algorithm, that is, it is non-adaptive and its final output is always one of the oracle queries x1xT. For guess-and-check algorithms, we prove a matching lower bound, therefore completely characterizing the achievable parameters (ST) for this natural class of algorithms. (Corrigan-Gibbs and Kogan showed that any such lower bound for arbitrary non-adaptive algorithms would imply new circuit lower bounds.) 3. We show equivalence between function inversion and a natural decision version of the problem in both the worst case and the average case, and similarly for functions f:[N][M] with different ranges. All of the above results are most naturally described in a model with shared randomness (i.e., random coins shared between the preprocessing algorithm and the online algorithm). However, as an additional contribution, we show (using a technique from communication complexity due to Newman [IPL, 1991]) how to generically convert any algorithm that uses shared randomness into one that does not. 
    more » « less
  4. Abstract

    The generalized Wilson loop operator interpolating between the supersymmetric and the ordinary Wilson loop inN=4SYM theory provides an interesting example of renormalization group flow on a line defect: the scalar coupling parameterζhas a non-trivial beta function and may be viewed as a running coupling constant in a 1D defect QFT. In this paper we continue the study of this operator, generalizing previous results for the beta function and Wilson loop expectation value to the case of an arbitrary representation of the gauge group and beyond the planar limit. Focusing on the scalar ladder limit where the generalized Wilson loop reduces to a purely scalar line operator in a free adjoint theory, and specializing to the case of the rankksymmetric representation ofSU(N), we also consider a certain ‘semiclassical’ limit wherekis taken to infinity with the product2fixed. This limit can be conveniently studied using a 1D defect QFT representation in terms ofNcommuting bosons. Using this representation, we compute the beta function and the circular loop expectation value in the largeklimit, and use it to derive constraints on the structure of the beta function for general representation. We discuss the corresponding 1D RG flow and comment on the consistency of the results with the 1D defect version of the F-theorem.

    more » « less
  5. Let f: {0, 1}n → {0, 1} be a boolean function, and let f∧(x, y) = f(x ∧ y) denote the AND-function of f, where x ∧ y denotes bit-wise AND. We study the deterministic communication complexity of f∧ and show that, up to a logn factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of f∧. This comes within a logn factor of establishing the log-rank conjecture for AND-functions with no assumptions on f. Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions on f such as monotonicity or low F2-degree. Our techniques can also be used to prove (within a logn factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of f∧ is polynomially related to the AND-decision tree complexity of f. The results rely on a new structural result regarding boolean functions f: {0, 1}n → {0, 1} with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing f has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials f: {0, 1}n → with a larger range. 
    more » « less