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.41032871754\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. Independently replayed [T2026]: both certificates give the stated values exactly ($0.41032871754918741449\ldots$ and $0.410302117239\ldots$) in two implementations. |
| $0.4103333$* | [Kos2026] | Construction: a step function $f = \sum_i w_i 1_{[i/K,(i+1)/K)}$ with $K = 24576$ and $24592$ non-negative integer weights, the last 8 of them zero (support $[0, 3073/3072)$), scored by the same exact rule as [R2026]. Exact value: $134648548624804778248790016/328144294688458468928334649 = 0.41033335274\dots$, the minimum attained at $k = 21264$. Found by splitting each cell of the [R2026] certificate in four (in two steps) and re-optimizing the weights numerically; the result keeps the shape of [R2026], including about 22% of the mass in the interval $[1/6144, 2/6144)$, next to the left end. Certificate: in [Kos2026], commit a4ee94ef29ff, SHA-256 of K24576_0.4103333.json: 963cb7273062e7360fdfa460bb19c1cf37729364b8f708b09580b6655b783c9e. A standard-library verifier there computes every lag exactly; the value was also reproduced by an independent verifier written from the definition alone. |
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
- [Kos2026] Koshta, Dennis, with Claude (Anthropic, Claude Opus 5.5). An improved step-function lower bound for the Barnard–Steinerberger autocorrelation constant. Certificate and verifiers: https://github.com/DennisKoshta/c1c-autocorrelation-certificate (commit
a4ee94ef29ff, 23 Oct 2026). - [MR2020] Madrid, J.; Ramos, J. P. G. On optimal autocorrelation inequalities on the real line. arXiv:2003.06962
- [T2026] Toledo, Carlos. Independent replay of the step-function certificates for $C_{1c}$ [R2026] and $C_{1d}$ [CERT2026]: the weights as exact rationals, every lag of the autocorrelation ($C_{1c}$) and of the autoconvolution ($C_{1d}$) summed exactly, in two implementations that share no code with each other or with the certificates’ verifiers. Report (§7); code and record at commit
d9a3942(2026). - [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].
- The [T2026] replay was prepared with AI assistance (Claude); its numbers are read from the record at the commit cited.
- The [Kos2026] row was found and prepared with Claude (Anthropic, Claude Opus 5.5), directed by Dennis Koshta, who takes responsibility for the submission: the numerical re-optimization, the certificate, the verifiers and the text. The value was reproduced by a second Claude agent with its own verifier, written from the definition and the certificate format only; no human mathematician has checked the argument.