op826_envelope_at_two
For value ratio R = 2, the discrete envelope min (1 / floor(sqrt 2)) (ceil(sqrt 2) / 2) equals 1.
Statement
theorem op826_envelope_at_two :
min (1 / (⌊Real.sqrt (2 : ℝ)⌋ : ℝ)) ((⌈Real.sqrt (2 : ℝ)⌉ : ℝ) / (2 : ℝ)) = 1- Source
- arXiv:2610.34625
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op826_online_single_high_efx_upper_bound_twoFor three agents and value ratio R = 2, the online single-high EFX competitive ratio is at most the conjectured envelope min (1 /…
Read back from the Lean
The minimum of 1 / ⌊√2⌋ and ⌈√2⌉ / 2 (evaluated in the real numbers, with floor and ceiling cast from integers to reals) is equal to 1.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem computes the discrete EFX envelope at $R = 2$ by calculating the floor and ceiling of $\sqrt{2}$. Using standard characterizations of floor and ceiling, it proves $\lfloor \sqrt{2} \rfloor = 1$ and $\lceil \sqrt{2} \rceil = 2$ by bounding $\sqrt{2}$ between $1$ and $2$. Substituting these values reduces the formula to $\min(1 / 1, 2 / 2) = 1$, which is verified by elementary arithmetic.
The floor $\lfloor \sqrt{2} \rfloor$ equals $1$.
Using the characterization of the floor function (`Int.floor_eq_iff`), showing $\lfloor \sqrt{2} \rfloor = 1$ reduces to checking $1 \le \sqrt{2}$ and $\sqrt{2} < 1 + 1$. Both inequalities are verified by numerical evaluation (`norm_num`), allowing the floor term in the main goal to be rewritten as $1$.
uses
Int.floor_eq_iffrw [show ⌊Real.sqrt (2 : ℝ)⌋ = (1 : ℤ) by rw [Int.floor_eq_iff] constructor <;> norm_num]
The ceiling $\lceil \sqrt{2} \rceil$ equals $2$.
Using the characterization of the ceiling function (`Int.ceil_eq_iff`), showing $\lceil \sqrt{2} \rceil = 2$ reduces to showing $2 - 1 < \sqrt{2}$ and $\sqrt{2} \le 2$. The upper bound $\sqrt{2} \le 2$ is verified directly by `norm_num`. For the lower bound $1 < \sqrt{2}$, `Real.lt_sqrt` squares both sides to obtain $1^2 < 2$ (using $0 \le 1$), which is then closed by numerical computation (`norm_num`). Rewriting replaces $\lceil \sqrt{2} \rceil$ with $2$ in the main goal.
uses
Int.ceil_eq_iff,Real.lt_sqrtrw [show ⌈Real.sqrt (2 : ℝ)⌉ = (2 : ℤ) by rw [Int.ceil_eq_iff] constructor · norm_num rw [Real.lt_sqrt (by norm_num : (0 : ℝ) ≤ 1)] norm_num · norm_num]
The minimum $\min(1 / 1, 2 / 2)$ simplifies to $1$.
With the floor and ceiling replaced by $1$ and $2$, the expression becomes $\min(1 / 1, 2 / 2) = 1$. Elementary real arithmetic and taking the minimum closes the goal via `norm_num`.
norm_num
Int.floor_eq_iff- An integer $z$ equals $\lfloor a \rfloor$ if and only if $z \le a < z + 1$.
Int.ceil_eq_iff- An integer $z$ equals $\lceil a \rceil$ if and only if $z - 1 < a \le z$.
Real.lt_sqrt- For $0 \le x$, $x < \sqrt{y}$ is equivalent to $x^2 < y$.
- While Mathlib's `norm_num` can directly decide non-strict inequalities like $1 \le \sqrt{2}$ and $\sqrt{2} \le 2$, it does not automatically reduce strict inequalities with a square root on the right ($1 < \sqrt{2}$). The proof therefore explicitly invokes `Real.lt_sqrt` on line 11 to square both sides before calling `norm_num`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Evaluation of the discrete EFX envelope at R = 2 yields 1. -/theorem op826_envelope_at_two : min (1 / (⌊Real.sqrt (2 : ℝ)⌋ : ℝ)) ((⌈Real.sqrt (2 : ℝ)⌉ : ℝ) / (2 : ℝ)) = 1 := by rw [show ⌊Real.sqrt (2 : ℝ)⌋ = (1 : ℤ) by rw [Int.floor_eq_iff] constructor <;> norm_num] rw [show ⌈Real.sqrt (2 : ℝ)⌉ = (2 : ℤ) by rw [Int.ceil_eq_iff] constructor · norm_num rw [Real.lt_sqrt (by norm_num : (0 : ℝ) ≤ 1)] norm_num · norm_num] norm_num