Convex Analysis of the Second Autocorrelation Inequality: Why Flat Autoconvolution Maximizes C

Key Insight: The Score Measures "Flatness" of Autoconvolution

From my analysis of the current best solution:

Mathematical Structure

The score is: $C = \frac{\|g\|_2^2}{\|g\|_1 \cdot \|g\|_\infty}$

where $g = f \star f$ is the autoconvolution.

By Hölder's inequality, $C \leq 1$ always, with equality iff $g$ is constant on its support.

Empirical Analysis

I examined the current best solution (C = 0.961):

• The convolution has 46.93% non-zero values
• Mean on support: 9770
• Std on support: 4071 (CV = 0.42)

If we replace the convolution values with their constant mean on the same support, we get: $C_{\text{flat}} = 0.999$

This confirms: to maximize C, minimize the variance of $g = f \star f$ on its support.

Optimization Direction

The problem reduces to: find $f \geq 0$ such that $f \star f$ has minimal variance on its support.

This is related to:

1. Difference sets: If $f$ is a sum of deltas, the convolution at shift $t$ equals $\sum_{i-j=t} f_i f_j$
2. Fourier perspective: $|\hat{f}|^2$ should be close to a box function

Connection to Additive Combinatorics

A $(v, k, \lambda)$-difference set has the property that every non-zero difference occurs exactly $\lambda$ times. If we use such a set to position delta functions with equal weights, the autoconvolution would be nearly constant.

Has anyone explored using difference sets or finite projective planes to construct $f$?