Prove2Me

OAI.CommonBasesFPRAS.MachineCode.Effect.safe_witness: intermediate lemma from OpenAI, Approximate counting of common bases of two matroids

Proved
OAI.CommonBasesFPRAS.MachineCode.Effect.safe_witness

by dbenbenn · Oct 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

openai-math

An intermediate lemma of the split of OpenAI's proof of OAI.common_bases_fpras, carved from OpenAI's openai/math development for this platform. The statement and its proof are OpenAI's (OpenAI, Approximate counting of common bases of two matroids, OpenAI Math Release, September 23, 2026, result family 114, github.com/openai/math, Apache License 2.0); in Lean it is the declaration OAI.CommonBasesFPRAS.MachineCode.Effect.safe_witness of lean/OAI/Combinatorics/MatroidCounting/MatroidCounting/CommonBases.lean at commit adc7f12, ported to Lean 4.33.1 and Mathlib 0df444a.

The statement, as published (namespace OAI.CommonBasesFPRAS.MachineCode.Effect, with open Expression, open scoped Classical, open Expression, open Expression, open scoped Classical, open Expression, open scoped Classical, open Expression, open Expression, open scoped Classical):

lemma safe_witness : OracleSafe witnessCode (bankScope phaseScope)

Definitions. The statement is written with OAI.CommonBasesFPRAS.MachineCode.BankData, OAI.CommonBasesFPRAS.MachineCode.Optional, OAI.CommonBasesFPRAS.MachineCode.OracleSafe, OAI.CommonBasesFPRAS.MachineCode.PhaseInput, OAI.CommonBasesFPRAS.MachineCode.StateData, OAI.CommonBasesFPRAS.MachineCode.DataType, OAI.CommonBasesFPRAS.MachineCode.Effect.bankScope, OAI.CommonBasesFPRAS.MachineCode.Effect.phaseScope and OAI.CommonBasesFPRAS.MachineCode.Effect.witnessCode (definitions bundle OAIQ2Mt000 of this split).

Used by. The proof of OAI.CommonBasesFPRAS.MachineCode.safe_single of this split imports it.

Preamble
import Mathlib
import Definitions.Def_OAIQ2Mt000
Formal statement
section

set_option linter.all false
set_option linter.unusedVariables false
set_option linter.unusedTactic false
set_option linter.unreachableTactic false

namespace OAI

namespace CommonBasesFPRAS

namespace MachineCode


open Expression

open Expression

open Expression

open Expression

open Expression

open Expression
end MachineCode

namespace MachineCode

open Expression
open scoped Classical

open Expression

open Expression
open scoped Classical

open Expression
open scoped Classical

open Expression

open Expression
open scoped Classical
namespace Effect
lemma safe_witness : OracleSafe witnessCode (bankScope phaseScope) := by
  sorry
end Effect

open Expression
open scoped Classical

open Expression

open Expression Effect

open Expression
open scoped Classical

open Expression

open Expression Effect

open Expression
open Expression Effect

open Expression

open Expression

open Expression Effect

open Expression

open Expression

open Expression Effect
open scoped Classical

open Expression

open Expression
open scoped Classical

open Expression

open scoped Classical

end MachineCode
end CommonBasesFPRAS

open CommonBasesFPRAS CommonBasesFPRAS.MachineCode

end OAI
end
Source
OpenAI, Approximate counting of common bases of two matroids, OpenAI Math Release, September 23, 2026, https://github.com/openai/math (result family 114; paper: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Approximate-counting-of-common-bases-of-two-matroids-September-23-2026/main.pdf; Apache License 2.0); Lean: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/lean/OAI/Combinatorics/MatroidCounting/MatroidCounting/CommonBases.lean (declaration OAI.CommonBasesFPRAS.MachineCode.Effect.safe_witness)

View graph