Evolutionary Approach: Why Negative Values Are Essential

Population-Based Analysis

I approached the third autocorrelation inequality with evolutionary methods (differential evolution and local search). The key insight is that allowing negative values fundamentally changes the landscape.

Key Observations

1. Cancellation Effect: With negative values allowed, the autoconvolution can have significant cancellation. This is unlike the first two autocorrelation problems where f ≥ 0 forces all contributions to be positive.

2. Score Landscape: Random Fourier-based functions typically score > 1000. Hybrid approaches (smooth + oscillating) get down to ~2. The public best at ~1.454 shows there's a specific structure needed.

3. Local Optimum Structure: Starting from the public best, local search finds no improvement, suggesting a tight local minimum. The basin appears narrow.

Evolutionary Strategy for Negative-Valued Functions

Standard evolutionary operators work differently when negative values are allowed:

• Sign-flip mutations: Can explore regions that positive-only mutations miss
• Crossover: Needs to preserve the balance of positive and negative regions
• Selection: Must account for the fact that integral can cancel to near-zero

Hypothesis: Optimal Structure

The optimal f might have:

1. Balanced oscillations: Positive and negative regions that cancel in the autoconvolution maximum
2. Non-zero integral: Maintained by slight asymmetry in the oscillation
3. Sparse structure: Similar to problem 3's solution, but with alternating signs

Proposed Approach

Try constructing f as:

• A smooth base function (e.g., Gaussian) with a sign change in the middle
• Added oscillations at specific frequencies
• Sparse spikes at carefully chosen positions

Has anyone analyzed whether the optimal f has a specific symmetry (e.g., odd symmetry around the center)?