Lemma 7.1: extending subexponential coding sequences
ProvedQAlgorithms.Papers.Independent.Gap20.P07.subexponentialSequence_extensionLet be a finite nonnegative function on pairs of positive integers, decreasing in its first argument and increasing in its second. Suppose , , and . For any positive sequences with and
one has . Rate limits are interpreted in the extended nonnegative reals. No monotonicity of the sequence itself is assumed. This extends reliable subexponential code sequences using only resource wasting.
import Definitions.Def_QAlgorithms_Papers_Independent_Gap20_P07
noncomputable section
open Filter MeasureTheory
open scoped Topology ENNReal NNReal Matrix ComplexOrder ComplexConjugate
attribute [local instance] Classical.propDecidable
attribute [local instance] Classical.decEq
attribute [local instance] IsStarNormal.instContinuousFunctionalCalculus
namespace QAlgorithms.Papers.Independent.Gap20.P07
open QAlgorithms
open QAlgorithms.RealRegisters (Hilbert)
open QAlgorithms.Papers.Independent.Dependency50.P33
(State IsTraceClass IsTraceClassChannel traceSize rankOne tensorApply)
open QAlgorithms.Papers.Independent.Frontier30.P14
(Operation isometryCoeff conjugateKernel)
open QAlgorithms.Papers.Independent.Claimed50.P35
(stabilizedTraceClassNorm traceClassTensorMap traceClassChannelPower
transpose transposeBound TraceLinear tracePair MeasurePrepare)
open QAlgorithms.Papers.Independent.Gap48.P29 (fe FiniteCPMap)
/-- PDF pp.26--27, Lemma 7.1: subexponential means divergence AND successive
ratio tending to one; the rate comparison is strict limsup < liminf. Extended
rate limits retain unbounded rates; the error itself is finite nonnegative. -/
theorem subexponentialSequence_extension (delta : ℕ+ → ℕ+ → ℝ≥0)
(hmono : ErrorMonotone (fun n m => (delta n m : ℝ≥0∞)))
(N M : ℕ → ℕ+)
(hN : Tendsto (fun a => (N a : ℕ)) atTop atTop)
(hratio : Tendsto (fun a => (N (a + 1) : ℝ) / (N a : ℝ)) atTop (𝓝 1))
(herror : Tendsto (fun a => delta (N a) (M a)) atTop (𝓝 0))
(n m : ℕ → ℕ+) (hn : Tendsto (fun a => (n a : ℕ)) atTop atTop)
(hrate : Filter.limsup (rateRatio n m) atTop < Filter.liminf (rateRatio N M) atTop) :
Tendsto (fun a => delta (n a) (m a)) atTop (𝓝 0) := by sorry
end QAlgorithms.Papers.Independent.Gap20.P07
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be any function satisfying, for all positive integers ,
where these inequalities are formally taken after embedding the finite nonnegative values into . Let be four sequences of positive integers, indexed by all , such that , as real numbers, , and . Define the rate sequences and by division in . If
then in the nonnegative real numbers. The sequences themselves may oscillate; their stated limits and the strict comparison of extended-real rates are the imposed sequence conditions.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.