Extensions of autocorrelation inequalities with applications to additive combinatorics


  • S. Fish California Institute of Technology
  • D. King Wake Forest University
  • S. J. Miller Williams College


Autocorrelation, Integral Inequality


Barnard and Steinerberger show that for $f\in L^1(\mathbf{R})$, the following autocorrelation inequality holds: $$\min_{0 \leq t \leq 1} \int_\R f(x) f(x+t)\ \mathrm{d}x \ \leq\ 0.411 ||f||_{L^1}^2,$$ where the constant $0.411$ cannot be replaced by $0.37$. In addition to being interesting and important in their own right, inequalities such as these have applications in additive combinatorics where some problems, such as those of minimal difference basis, can be encapsulated by a convolution inequality similar to the above integral. Barnard and Steinerberger suggest that future research may focus on the existence of functions extremizing the above inequality (which is itself related to Brascamp-Lieb type inequalities). We show that for $f$ to be extremal under the above, we must have $$\max_{x_1 \in \R }\min_{0 \leq t \leq 1} \left[ f(x_1-t)+f(x_1+t) \right] \ \leq\ \min_{x_2 \in \R } \max_{0 \leq t \leq 1} \left[ f(x_2-t)+f(x_2+t) \right] .$$ Our central technique for deriving this result is local perturbation of $f$ to increase the value of the autocorrelation, while leaving $||f||_{L^1}$ unchanged. These perturbation methods can be extended to examine a more general notion of autocorrelation. Let $d,n \in \mathbb{Z}^+$, $f \in L^1$, $A$ be a $d \times n$ matrix with real entries and columns $a_i$ for $1 \leq i \leq n$, and $C$ be a constant. For a broad class of matrices $A$, we prove necessary conditions for $f$ to extremize autocorrelation inequalities of the form $$\min_{ \mathbf{t} \in [0,1]^d } \int_{\R} \prod_{i=1}^n\ f(x+ \mathbf{t} \cdot a_i)\ \mathrm{d}x\ \leq\ C ||f||_{L^1}^n.$$

Author Biographies

S. Fish, California Institute of Technology

Department of Mathematics

D. King, Wake Forest University

Department of Mathematics

S. J. Miller, Williams College

Professor of Mathematics, Williams College Fellow of the American Math Society Senator at Large, Phi Beta Kappa Faculty Fellow, Erdos Institute