Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Alon's matching lower bound: Ω(n2/3)\Omega(n^{2/3})Ω(n2/3) is attained

Proved
KonyaginUnitVectors.exists_sum_norm_ge_of_triangle_free_forall_n

by aarontcao · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsdiscrete-geometrygraph-theory

There is a positive constant ccc such that for every nnn there is a system of nnn unit vectors, of which among any three some two are orthogonal, whose sum has norm at least cn2/3cn^{2/3}cn2/3.

Together with the upper bound this makes the exponent sharp at 2/32/32/3, so the answer to Lovasz's problem is Θ(n2/3)\Theta(n^{2/3})Θ(n2/3) and not merely O(n2/3)O(n^{2/3})O(n2/3).

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.

Preamble
import Mathlib
open scoped RealInnerProductSpace
Formal statement
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
Source
Noga Alon, "Explicit Ramsey graphs and orthonormal labelings", Electron. J. Combin. 1 (1994) R12, doi:10.37236/1192, https://doi.org/10.37236/1192
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.

Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

  • Endorsed by aarontcao · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me