Barnard–Steinerberger autocorrelation constant
Description of constant
$C_{1c}$ is the smallest constant for which one has \(\min_{0 \leq t \leq 1} \int_{\mathbb{R}} f(x) f(x+t)\ dx \leq C_{1c} \left(\int_{\mathbb{R}} f(x)\ dx\right)^2\) for all non-negative $f \in L^1(\mathbb{R})$.
Equivalently, in the notation of [K2021], $\tau = C_{1c}^{-1/2}$ is the infimum of $\int f$ over non-negative $f$ with $\int f(x) f(x+t)\ dx \geq 1$ for all $t \in [0,1]$.
The constant was introduced in [BS2020], alongside the constant $C_{1a}$. It is Problem 6 of [GGSWT2025].
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $1/2$ | Trivial | The autocorrelation is even, and its integral over $\mathbb{R}$ is $(\int f)^2$. |
| $\frac{1}{2(1+\theta_0)} = 0.4107675\dots$ | [BS2020] | Here $\theta_0 = -\min_x \frac{\sin x}{x} = 0.2172336\dots$. Stated as $0.411$ in [BS2020]; the exact form is [MR2020, (1.2)]. [MR2020] show it is not sharp within a restricted class of functions (non-quantitatively), and that dual test-function arguments of this type cannot go below it [MR2020, Thm 4.1]. |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $0.37$ | [BS2020] | Explicit example. |
| $0.4103287*$ | [R2026] | Construction: a step function $f = \sum_i w_i 1_{[i/K,(i+1)/K)}$ with $K = 6144$ and $6148$ non-negative integer weights (support $[0, 1.0005)$). Exact value: $21072342208353792/51354782902387969 = 0.41030287175\dots$, computed as $K \min_{0 \le k \le K} \sum_i w_i w_{i+k} / (\sum_i w_i)^2$. This is exact because the autocorrelation of an equal-step function is linear between consecutive multiples of $1/K$ (as in the proof of [K2021, Thm 3.1]). Certificate: in [R2026], commit 19f3971, SHA-256 of certificate.json: 62ac49ddbbfc9aa1053406363d9df9c912022ab85b72a447cf73c94bb9c1fd0e. An earlier certificate with $K = 3072$ giving $0.4103021$ is kept in the same repository. |
Additional comments and links
- Elementary examples. Difference bases already give step-function examples via [K2021, Thm 3.1]. For instance, the ruler $\{0,1,4,6\}$ (all differences $1,\dots,6$) gives exactly $3/8$, which beats $0.37$ by a hand computation.
- Relation to difference bases. [K2021] relates $\tau$ to the asymptotics of $g$-difference bases and states the bounds $1.560\ldots < \tau \le 1.643\ldots$.
- AlphaEvolve. [GGSWT2025] report that their attempt on this problem did not improve $0.37$: the search exploited the numerical integration in the scoring function. They suggest that a search over step functions with fixed step sizes would work better.
- Structure of near-extremizers. In the numerical near-extremizers of [R2026], about 21–22% of the mass sits in a single grid cell at one end, at both $K = 3072$ and $K = 6144$, and it re-concentrates there after being spread out. This suggests that extremizers are unbounded at one end (compare [K2021, Question 7.2]). Numerics cannot distinguish a point mass from a very sharp singularity.
- Averaged variant. [dDPM2021] study the variant in which the minimum over $t$ is replaced by an average.
References
- [BS2020] Barnard, R. C.; Steinerberger, S. Three convolution inequalities on the real line with connections to additive combinatorics. J. Number Theory 207 (2020), 42–55. arXiv:1903.08731
- [dDPM2021] de Dios Pont, J.; Madrid, J. On classical inequalities for autocorrelations and autoconvolutions. arXiv:2106.13873
- [GGSWT2025] Georgiev, B.; Gómez-Serrano, J.; Tao, T.; Wagner, A. Z. Mathematical exploration and discovery at scale. arXiv:2511.02864
- [K2021] Kravitz, N. Generalized difference sets and autocorrelation integrals. arXiv:2004.06611
- [MR2020] Madrid, J.; Ramos, J. P. G. On optimal autocorrelation inequalities on the real line. arXiv:2003.06962
- [R2026] rozetyp (GitHub). A lower bound for the Barnard–Steinerberger autocorrelation constant. Certificate and verifiers: https://github.com/rozetyp/barnard-steinerberger-lower-bound
Contribution notes
Prepared by rozetyp (GitHub), with assistance from Claude (Anthropic), which also helped find and verify the construction in [R2026]. The exact form of the [BS2020] upper bound was checked against [MR2020]. The linearity argument was checked against the proof of [K2021, Thm 3.1].