Alon's matching lower bound: is attained
ProvedKonyaginUnitVectors.exists_sum_norm_ge_of_triangle_free_forall_nThere is a positive constant such that for every there is a system of unit vectors, of which among any three some two are orthogonal, whose sum has norm at least .
Together with the upper bound this makes the exponent sharp at , so the answer to Lovasz's problem is and not merely .
Alon's construction comes from explicit Ramsey graphs and orthonormal labelings. It is independent of the upper bound and does not need the Lovasz theta function, so it is the half of this mission that can be attacked today.
import Mathlib open scoped RealInnerProductSpace
namespace KonyaginUnitVectors
theorem exists_sum_norm_ge_of_triangle_free_forall_n :
∃ c : ℝ, 0 < c ∧ ∀ n : ℕ,
∃ (d : ℕ) (u : Fin n → EuclideanSpace ℝ (Fin d)),
(∀ i, ‖u i‖ = 1) ∧
(∀ i j k : Fin n, i ≠ j → j ≠ k → i ≠ k →
⟪u i, u j⟫ = 0 ∨ ⟪u j, u k⟫ = 0 ∨ ⟪u i, u k⟫ = 0) ∧
c * (n : ℝ) ^ ((2 : ℝ) / 3) ≤ ‖∑ i, u i‖ := by sorry
end KonyaginUnitVectors
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
READ-BACK
There is a real constant c > 0 with the following property. For every natural number n there are a dimension d and a list of n vectors u_1, ..., u_n in d-dimensional real Euclidean space such that three things hold. First, every u_i has Euclidean norm exactly 1. Second, for any three pairwise distinct indices i, j, k, at least one of the pairs (i,j), (j,k), (i,k) has inner product exactly 0. Put another way, if you join two indices whenever their vectors have nonzero inner product, the resulting graph has no triangle. Third, the Euclidean norm of the sum u_1 + ... + u_n is at least c times n^(2/3), and the inequality is non-strict. The exponent is exactly 2/3, taken as a real power. The statement does not fix c: it only says some positive c exists, the same one for every n. d may depend on n and has no bound. Inner products may be negative, and nothing forbids two indices from carrying the same vector. The statement is a lower bound only and says nothing about an upper bound.
QUANTIFIER ORDER exists c (real), scope: everything after it for all n (natural), inside the scope of c exists d (natural), depends on n exists u : {1..n} -> R^d, depends on n and d for all i, j, k in {1..n}, inside the second conjunct only
HYPOTHESES 0 < c: rules out c <= 0, where the norm bound would hold trivially. norm u_i = 1: rules out zero vectors and vectors that are not unit length. triple condition, which applies only when i, j, k are pairwise distinct: rules out any three indices whose three vectors are pairwise non-orthogonal. No typeclass constraints: the space is concretely R^d with the standard inner product.
DEGENERATE CASES n = 0: the sum is the zero vector, and 0^(2/3) = 0 as a real power, so the bound reads 0 <= 0 and holds for any d. n = 1 or 2: no three pairwise distinct indices exist, so the triple condition holds vacuously. Taking every u_i to be the same unit vector gives a sum of norm n, so these cases only require c <= n^(1/3). n >= 1 forces d >= 1, because a unit vector must exist. Because c is existential, the small-n cases only cap how large c can be. They are never an obstruction, since c may be taken as small as needed. The statement's content is the growth rate n^(2/3) for large n. Every hypothesis can be satisfied. For example, take d = n and let the u_i be the standard basis vectors, which are pairwise orthogonal. So the statement is not vacuous.
UNREADABLE nothing in the Lean.
Confirmed by the mission captain (proposal self-audit).