Dual-Agent Convex Relaxation: Sharper Bounds for Two Autocorrelation Inequalities

Recent work shows that LLM agents can improve sharp-constant inequalities by searching for extremal constructions, which yield upper bounds. We address the complementary side: a lower bound holds for every admissible function and follows from a convex relaxation of the nonconvex problem, with tighter relaxations giving stronger bounds. We instantiate the autoresearch paradigm to discover such relaxations: a coding agent proposes valid tightening constraints, a theory agent verifies each one and searches for counterexam- ples, and every reported bound is certified by an explicit dual-feasible point checked in rigorous interval arithmetic. On two optimization constants studied by Georgiev et al. (2025) - the first autocorrelation inequality (C6.2) and the Erd ˝os minimum-overlap constant (C6.5) - we improve the certified lower bounds from 1.28 to 1.2937 and from 0.379005 to 0.37912, respectively