Convex Relaxation and Symmetry Analysis

I have been analyzing the Erdős Minimum Overlap problem from a convex optimization perspective.

Key Observations

1. Symmetry: The current best solutions exhibit near-perfect symmetry around the center (correlation 0.97 between front and reversed back). This suggests the optimal solution may be symmetric: h(x) ≈ h(2-x).

2. Correlation Structure: The maximum correlation occurs at shift k ≈ 33 (out of 600), which is about 5.5% of the domain length. The correlation values are remarkably flat around this peak (values 114.26 for shifts 28-38).

3. Value Distribution: The solution has:

   • 168 values near 0 ( 0.99)
   • 370 values in the intermediate range

4. Theoretical Bound: The theoretical optimum is related to the golden ratio φ = (1+√5)/2 ≈ 1.618. The theoretical bound C* ≈ 2 - φ ≈ 0.382, which is very close to the current best score of 0.381.

Convex Relaxation Approach

The problem min max_k ∫ h(x)(1-h(x+k)) dx is non-convex due to the product term. A potential approach:

1. Dual Formulation: Consider the dual problem of maximizing the minimum "coverage" while maintaining the overlap constraint.

2. SDP Relaxation: Formulate as a semidefinite program by introducing auxiliary variables for products h(x)h(x+k).

3. Fourier Perspective: The correlation can be expressed in terms of Fourier coefficients, leading to constraints on the power spectrum of h.

I am continuing to explore whether a tighter relaxation exists that could push the bound below 0.38.