Large-Scale Bundle-Size Pricing: A Theoretical Analysis: With Identical Marginal Costs, Optimal Bundle-Size Pricing Asymptotically Achieves Perfect Price DiscriminationResearch Paper
Motivation
Firms that sell large catalogues of digital goods (streaming titles, cable channels, software features) rarely price every subset of products separately: with N products there are 2N bundles. A common simplification is bundle-size pricing (BSP), where the price depends only on how many items the customer takes and the customer picks which items go into the bundle. BSP sits between pure bundling (one price for everything) and full mixed bundling, and its menu has only N prices.
Bakos and Brynjolfsson (Management Science, 1999) showed that for many products a pure bundle extracts almost all surplus under suitable concentration. Armstrong (Review of Economic Studies, 1999) showed that a cost-based two-part tariff asymptotically achieves the perfect-price-discrimination profit. Chu, Leslie and Sorensen (American Economic Review, 2011) computed optimal BSP menus numerically for up to five goods. Abdallah, Asadpour and Reed (Operations Research, 2021) develop an asymptotic theory of BSP as N→∞. This mission formalizes their homogeneous-cost result: with identical marginal costs, optimal BSP asymptotically earns the perfect-price-discrimination profit.
Setting
A firm sells N products to one customer with valuationsX1,…,XN≥0, additive over bundles. Let X(1)≤⋯≤X(N) be the order statistics. A bundle of size n is worth VN(n)=∑k=0n−1X(N−k) to the customer, the sum of her n largest valuations, with VN(0)=0. The firm incurs a marginal cost cn≥0 for item n, so a bundle of size n costs cN(n)=∑k=0n−1cτ(N−k), where τ lists the items by valuation and ties go to the lowest index.
A BSP menu is p=(p(1),…,p(N)) with p(n)∈R+∪{+∞}, where +∞ means size n is not offered. The customer buys a size ζ(X,p)∈argmax0≤n≤N(VN(n)−p(n)), with n=0 the free no-purchase option. The firm's profit is π(p)=∑n=1N(p(n)−cN(n))1{ζ(X,p)=n}, and the BSP problem is E[π(pN⋆)]=suppE[π(p)]. The benchmark is perfect price discrimination, PPD=∑n=1NE[(Xn−cn)+], the most any selling mechanism can earn.
The large-offering regime describes the valuations as one random sequence X1,X2,…:
(Assumption 1) the empirical distribution functionFX,N(x)=N1∑n≤N1{Xn≤x} converges in probability to FX(x) for each x≥0, where FX is the distribution function of a nonnegative variable with finite mean μ;
(Assumption 2) {Xn} is uniformly integrable and N1∑n≤NXn→μ in probability;
(Assumption 3) the costs are bounded and their empirical distribution converges.
The normalized curves are VˉN(t)=N1VN(⌊Nt⌋) and cˉN(t)=N1cN(⌊Nt⌋) for t∈[0,1]. The quantile function is FX−1(s)=inf{x≥0:FX(x)≥s}.
Formalization targets
Goal: Theorem 2
With identical costs cn=c≥0, for every t∈[0,1],
VˉN(t)⇒Vˉ(t)=∫0tFX−1(1−s)ds,cˉN(t)⇒tc.
The size fraction t⋆=sup{s:FX−1(1−s)≥c} maximizes Vˉ(t)−tc over [0,1], and t⋆=1−FX(c) when c is a continuity point of FX. If FX(c)<1,
N→∞limPPDE[π(pN⋆)]=1.
Theorem 1 and the steps of the proofs
Theorem 1 is the general principle behind the goal. Suppose VˉN⇒Vˉ and cˉN⇒cˉ pointwise, with nondecreasing continuous limits, and t⋆∈argmaxVˉ−cˉ. Offer the single size ⌊Nt⋆⌋ at price NVˉ(t⋆)−g(N), where g(N) grows faster than E[(VN(⌊Nt⋆⌋)−NVˉ(t⋆))2] but is o(N). Then
The milestones follow the appendix proofs in order:
the pathwise bound π(p)/N≤suptVˉN(t)−cˉN(t);
the upper limit (A1);
the purchase probability (A4);
the lower limit (A5);
Theorem 1;
(A6), with μ=∫01FX−1(1−s)ds;
the identity between VˉN at grid points and integrals of the empirical quantile function;
convergence of empirical quantiles at continuity points;
(A7);
PPD/N→Vˉ(t⋆)−t⋆c;
∫01(FX−1(1−s)−c)+ds=Vˉ(t⋆)−t⋆c.
Significance
Theorem 2 says that, with identical marginal costs and enough statistical concentration across products, a menu of N size prices earns, to first order, everything a seller who knew each valuation could earn. Theorem 1 says more: one well-chosen bundle size, sold at a price slightly below its fluid value, is asymptotically as good as the optimal BSP menu. The paper's later results on heterogeneous costs (Theorems 3–4), clustered BSP and unknown budgets reuse this framework: Theorem 1 reduces each of them to computing the limit curves Vˉ and cˉ.
The results are proved in the paper and have no machine-checked version. This mission formalizes them under a weak-convergence hypothesis on the empirical distribution, with no independence assumption. The formal statements also fix points the page leaves implicit: the tie-breaking rules, the value of the BSP problem as a supremum, and the case FX(c)=1, where the goal's ratio degenerates.
Difficulty
The obvious route to Theorem 2 goes through Theorem 1, as the paper does. That needs a g(N) dominating the L2 fluctuation of VN(⌊Nt⋆⌋), and Assumptions 1–2 give no second moments. A proof of the goal must therefore avoid Theorem 1's g(N) condition or replace it with a weaker device.
The convergence VˉN(t)⇒Vˉ(t) is a statement about sums of top order statistics of a dependent sequence. Pointwise convergence of the empirical cdf does not by itself control the upper tail, which carries the mass of VN. The weak law and uniform integrability have to supply that control.
The upper bound (A1) requires exchanging a supremum over t with a limit in probability, which uses monotonicity of VˉN,cˉN in t and continuity of the limits. The step "VˉN(t)=∫0tFX,N−1(1−s)ds for 0≤t≤1" holds only at grid points t=n/N, so the off-grid error must be bounded separately.
Formalization scope
Everything lives in the namespace LargeBSP.Homog. Items are 0-indexed: coordinate n < N is the paper's item n+1. The valuations are one sequence X : ℕ → Ω → ℝ on a probability space, measurable and nonnegative; the N-product model uses its first N terms. FX is cdf ν for a probability measure ν on R with ν(−∞,0)=0 and finite mean. "⇒" toward a constant is convergence in probability (TendstoInMeasure); deterministic sequences use Tendsto.
Menus are ℕ → WithTop ℝ, with ⊤ meaning "not offered". Within a bundle size, items are ranked by valuation with ties to the lowest index, as on the page. Among sizes, the customer picks the smallest maximizer of surplus, a disclosed tie-break, so an indifferent customer does not buy. E[π(pN⋆)] is the real supremum of the expected profit over all menus with prices in R+∪{∞}. It is bounded by E∑n≤NXn, so it is never the junk value of an unbounded supremum.
The quantile is inf{y≥0:F(y)≥s}. Its set is empty only outside (0,1), where Lean returns 0; every use is at s∈(0,1) or inside an integral. The set defining t⋆ is taken over (0,1).
Disclosed readings:
the hypothesis FX(c)<1 on the goal's ratio claim (otherwise PPD/N→0 and the ratio is undetermined);
in Theorem 1, continuity of Vˉ,cˉ (stated where the theorem is introduced and used in its proof) and Vˉ(t⋆)>cˉ(t⋆) (the second ratio's denominator);
ω+ and o(⋅) encoded as E[⋅2]/g2→0 and g/N→0 with g eventually positive;
the grid-point form of the VˉN–quantile identity.
The tail condition (6) of the paper is not assumed: neither proof uses it.
The goal cannot be satisfied trivially. E[π(pN⋆)] is the value of the BSP problem over all menus, not a chosen menu. PPD is the sum of the per-item expectations. The instance Xn≡1, c=1/2 satisfies every hypothesis with PPD=N/2>0, Vˉ(t)=t and t⋆=1. So the ratio is neither 0/0 nor fixed by a degenerate menu.
Needed infrastructure: order statistics of a finite family through a rank function, empirical distribution and quantile functions, the identity "mean = integral of the quantile function", convergence of quantiles under weak convergence (van der Vaart, Lemma 21.2), and uniform integrability of averages. These parts are reusable well beyond pricing. Contributions are welcome on any milestone, and on proofs of the goal that bypass Theorem 1's second-moment condition.
Selected references
T. Abdallah, A. Asadpour, J. Reed, Large-Scale Bundle-Size Pricing: A Theoretical Analysis, Operations Research 69(4), 2021 (author's manuscript used). https://doi.org/10.1287/opre.2020.2097
Y. Bakos, E. Brynjolfsson, Bundling Information Goods: Pricing, Profits, and Efficiency, Management Science 45(12), 1999. https://doi.org/10.1287/mnsc.45.12.1613
C. S. Chu, P. Leslie, A. Sorensen, Bundle-Size Pricing as an Approximation to Mixed Bundling, American Economic Review 101(1), 2011. https://doi.org/10.1257/aer.101.1.263
Continuum Weatherall: Poincaré Lemma and Potentials vs. Field Strengths on a Vector SpaceResearch Paper
Motivation
Philosophers of physics use category theory to decide when a formulation of a theory carries excess structure. Weatherall (2016) represents each formulation of electromagnetism as a category of models and the passage from potentials to field strengths as the functor A↦F=dA. A functor that is not full forgets structure, one that is not essentially surjective forgets properties, and one that is not faithful forgets stuff. Weatherall's §4 argues on Minkowski space that the potential formulation with gauge transformations as arrows is related to the field-strength formulation by a functor that is full and essentially surjective. His footnote 9 sets topology aside, and the erratum to his Proposition 2 (arXiv v2, p. 15) records that the gauge-theoretic functor is not faithful, because constant gauge transformations act trivially on fields.
On a contractible spacetime these facts all rest on one theorem: the Poincaré lemma, which says closed differential forms are exact. A companion mission (Weatherall 2016: Potentials vs. Field Strengths on a Finite 2-Complex) proves the discrete version, in which fullness, faithfulness and essential surjectivity are equivalent to the vanishing of H1, H0 and H2 of a cell complex. This mission is the continuum version on a vector space, built on Mathlib's exterior derivative.
Timeline. The explicit radial homotopy operator proof of the Poincaré lemma is standard in textbooks; it is the proof of Theorem 4-11 in Spivak's Calculus on Manifolds (1965). Antiexact forms and the same operator are studied in Kycia (2020). Mathlib has the exterior derivative extDeriv with d2=0. In 2025 Kudryashov proved the degree-1 case for convex sets, stated for 1-forms written as E → E →L F with a symmetric derivative. Mathlib has no Poincaré lemma in higher degree, no de Rham cohomology and no Hodge star.
Setting
Let E be a real normed space, for example Rn, and F a real Banach space of field values. A differential k-form is a map ω:E→E[∧k]→LF that assigns to each point a continuous alternating k-linear map. Smooth means C∞ (ContDiff ℝ ∞). The exterior derivative is Mathlib's extDeriv:
A function χ:E→F is a 0-form, and dχ is its derivative viewed as a 1-form (grad). The radial homotopy operator sends a (k+1)-form ω to the k-form
(Kω)(x)(v1,…,vk)=∫01tkω(tx)(x,v1,…,vk)dt.
Field equations enter through an arbitrary predicate P on 2-forms. For example P(F)⟺⋆d⋆F=J once a metric is chosen, and P≡True in vacuum. The categories are:
Fld P (Weatherall's EM1): smooth closed 2-forms B with P(B), with only identity arrows.
Pot P (EM2 with gauge arrows, fn. 15): smooth 1-forms A with P(dA). An arrow A→A′ is a smooth χ:E→F with A+dχ=A′, and arrows compose by adding gauge functions.
fieldStrength P : Pot P ⥤ Fld P: the functor A↦dA, which sends every gauge arrow to an identity.
The cohomology conditions are elementary Props:
H0=0: smooth χ with dχ=0 implies χ=0.
H1=0: every smooth closed 1-form is dχ for a smooth χ.
H2=0 on the P-sector: every smooth closed 2-form B with P(B) is dA for a smooth A.
Formalization targets
Goal: the continuum classification
For every P that admits at least one potential:
fieldStrengthP is full and essentially surjective,faithful⟺F is trivial,H1=0,H2=0,H0=0⟺F is trivial.
So the potential description with gauge arrows forgets only stuff, namely the constant gauge transformations, and nothing else on a vector space.
Milestones
The radial homotopy operator preserves smoothness.
The homotopy formula d(Kω)+K(dω)=ω for smooth ω of degree k+1≥1.
The Poincaré lemma: a smooth closed form of degree ≥1 has a smooth primitive.
Degree 0: for differentiable χ, dχ=0 holds iff χ is constant.
H1=0 and H2=0 in the potentials language.
Constants act freely and transitively on gauge arrows AoA′ by χ↦χ+c, so Hom(A,A′) is empty or an F-torsor.
The structural equivalences, which mirror the discrete mission: full ⟺H1=0, faithful ⟺H0=0, essentially surjective ⟺H2=0.
Four supporting statements isolate the reusable ingredients of Milestone 2:
An alternating-sum identity for alternating maps.
An interior-product identity for Mathlib's alternatizeUncurryFin.
Differentiation of Kω under the integral sign.
The radial fundamental theorem of calculus.
Significance
The result. The goal makes precise, on Rn and with any field equation, the claim behind Weatherall's §4: up to the constants H0=F, potentials modulo gauge carry no more information than field strengths. With the discrete mission, it shows that the three ways of forgetting information correspond to H1, H0 and H2 in both settings. The continuum version is metric-free. Maxwell's equations, sources or any other field equation enter only through P, so the classification holds for all of them at once.
Formalizing it. The homotopy formula and the Poincaré lemma for Mathlib's extDeriv in arbitrary degree are not in Mathlib. They are prerequisites for de Rham cohomology of manifolds, for the homotopy invariance of de Rham cohomology, and for any formal treatment of gauge potentials, Chern–Simons terms or Hamiltonian mechanics that uses local primitives. The classical proof is a textbook argument; the remaining work is to formalize it against Mathlib's alternating-map API. Machine-checked versions exist elsewhere only in other representations: Mathlib proves degree 1 for 1-forms written as E → E →L F on convex sets, and this platform's Rudin chapter 10 mission has proved Poincaré's lemma (Rudin, Theorem 10.39) as Rudin.ch10_poincare_lemma and Rudin.ch10_primitive_of_closed, for its own coefficient-style KForm on convex open subsets of Rn. A bridge from those statements to Mathlib's extDeriv would be a welcome contribution.
Difficulty
The obstacle is the homotopy formula in general degree. Each side involves the alternatization alternatizeUncurryFin of a derivative, the insertion curryLeft of the position vector as the first argument, and Fin.removeNth reindexing. Matching the two sides requires the signs (−1)i from moving an argument to the front to cancel exactly against those of d. The degree-1 shortcut through Mathlib's existing curve-integral Poincaré lemma does not generalize, because it uses a different representation of 1-forms and has no analogue in degree 2, which the essential-surjectivity clause needs. A second, routine obstacle is smoothness of Kω: E need not be finite-dimensional, so differentiating under the integral needs bounds that are uniform in t∈[0,1] near each point.
Formalization scope
Forms. Forms are Mathlib's E → E [⋀^Fin k]→L[ℝ] F and the exterior derivative is extDeriv. "Smooth" is ContDiff ℝ ∞, where ∞ means C∞, not analytic. E is any real normed space, not necessarily finite-dimensional or complete, and F is a real Banach space (CompleteSpace F), so the integral defining K is the Bochner integral.
Domain. The domain is the whole space E, which is star-shaped about 0. Open subsets and manifolds are out of scope.
Categories.Fld P is a Mathlib Discrete category. Pot P has a hand-written Category instance whose arrows are the structure GaugeHom. Fullness, faithfulness and essential surjectivity are Mathlib's Functor.Full, Functor.Faithful and Functor.EssSurj.
Non-triviality. Statements that need an object assume [Nonempty (Pot P)], meaning the field equation has a solution. Without it Pot P is empty and faithfulness and fullness hold vacuously. The cohomology conditions are explicit statements about extDeriv and grad, not definitions that make a target hold by construction. The goal fixes nothing about P.
Symmetries. Spacetime symmetries are not included as arrows; as in the discrete mission, the categories compare potentials and fields over the fixed space E, and the only non-identity arrows are gauge transformations.
No metric. No Hodge star or metric appears. Duality and 1-form symmetries are out of scope.
Reusable infrastructure. The definitions file proves smoothness of extDeriv, d2=0 in the form used here, and the gauge invariance d(A+dχ)=dA. The homotopy operator, the homotopy formula and the Poincaré lemma are stated for arbitrary degree and are intended for reuse in de Rham and gauge-theory missions. Contributions toward a Mathlib-quality homotopy-operator API are welcome.
Selected references
J. O. Weatherall, "Understanding Gauge", Philosophy of Science 83 (2016) 1039–1049. arXiv:1505.02229, doi:10.1086/687936. §4: EM1/EM2, Proposition 1, footnotes 9 and 15; the erratum to Proposition 2 is on p. 15 of arXiv v2.
M. Spivak, Calculus on Manifolds, W. A. Benjamin, 1965. Theorem 4-11 (Poincaré lemma) and its proof via the operator I, which is K above.
A computable measure of entanglementResearch Paper
Motivation
A computable measure of entanglement establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.
Setting
Let dA,dB be positive integers, and fix an orthonormal product basis of CdA⊗CdB. For a matrix M on this space, let MTA denote its partial transpose on the first subsystem, so that (MTA)(a,b),(c,e)=M(c,b),(a,e). Write ∥X∥1=trX†X and N(M)=(∥MTA∥1−1)/2. Let ρ1,…,ρr be any finite family of Hermitian matrices on this space, and let p1,…,pr be nonnegative real numbers with ∑i=1rpi=1. Then
N(i=1∑rpiρi)≤i=1∑rpiN(ρi).
This expresses convexity of negativity under mixing, a property used in the paper's subsequent study of entanglement monotonicity. As in the printed proposition and its proof, the matrices need not be positive or have trace one; the displayed definition therefore gives N(0)=−1/2 outside the state domain.
Target
§II.A, Proposition 1, Eq. (7)
Let dA,dB be positive integers, and fix an orthonormal product basis of CdA⊗CdB. For a matrix M on this space, let MTA denote its partial transpose on the first subsystem, so that (MTA)(a,b),(c,e)=M(c,b),(a,e). Write ∥X∥1=trX†X and N(M)=(∥MTA∥1−1)/2. Let ρ1,…,ρr be any finite family of Hermitian matrices on this space, and let p1,…,pr be nonnegative real numbers with ∑i=1rpi=1. Then
N(i=1∑rpiρi)≤i=1∑rpiN(ρi).
This expresses convexity of negativity under mixing, a property used in the paper's subsequent study of entanglement monotonicity. As in the printed proposition and its proof, the matrices need not be positive or have trace one; the displayed definition therefore gives N(0)=−1/2 outside the state domain.
Significance
These are known results from the cited paper. The current contribution consists of source-reviewed, compiler-checked theorem statements and mathematical definitions. Formal proofs remain open. Only the listed selected results are in scope; no whole-paper completeness is claimed.
Difficulty
A complete solution must establish every quantified conclusion under the exact stated hypotheses, including error, probability and resource conditions wherever present. The source assumptions and conventions are recorded in the attached statements and independent readbacks.
Formalization scope
Definitions preserve the existing reviewed Lean interfaces. Every target proof is currently sorry, so each target is Open. Printed-source corrections, where necessary, are labeled with the printed claim, the change and its reason.
Their coefficient sum is no larger than that of any other such decomposition. Eigenvalues are counted with multiplicity. This is an attained variational characterization, valid also for A=0.
§II.A, Eq. (11)
Let ρ1 and ρ2 be bipartite density matrices. Regroup their product as (A1A2)∣(B1B2), and define EN(ρ)=log2∥ρTA∥1. Then
EN(ρ1⊗ρ2)=EN(ρ1)+EN(ρ2).
All four local spaces are finite and nonempty. This additivity concerns logarithmic negativity.
§II.A, unnumbered paragraph after Eq. (11)
There exist two density matrices ρ and σ on two qubits for which
EN(2ρ+σ)>2EN(ρ)+EN(σ).
Thus logarithmic negativity is not convex. This states only the nonconvexity clause; the source's subsequent inference about LOCC increase is deferred separately.
§II.B, Proposition 3, Eq. (17)
Fix a finite adaptive LOCC protocol before a bipartite density matrix ρ is supplied. Local instruments may change finite dimensions, add ancillas, discard systems, and choose later operations from prior outcomes. After any fixed classical coarse-graining, let Xi be its subnormalized outputs, pi=TrXi, and ρi′=Xi/pi for pi>0. Then
i:pi>0∑piN(ρi′)≤N(ρ).
Zero-probability outcomes contribute zero. This is the selective entanglement-monotone inequality.
§II.C, Eqs. (18)–(20)
Let S be a compact convex set of Hermitian trace-one matrices whose real span is the full Hermitian space. Define ∥A∥S and NS(A) as the infima of a++a− and a− over A=a+ρ+−a−ρ−, where a±≥0 and ρ±∈S. These sets are nonempty and bounded below. The first functional is a norm on Hermitian matrices; NS is convex and nonnegative. Moreover,
TrA=1⟹∥A∥S=1+2NS(A).
Members of S need not be positive. The statement includes definiteness, the triangle inequality, and absolute homogeneity of the norm.
§II.C, Eq. (21)
For a density matrix ρ on positive finite local spaces, let Nss and Nppts use the variational base construction with separable states and PPT states, respectively. Then
Nss(ρ)≥Nppts(ρ)≥N(ρ)≥0.
Furthermore, Nss(ρ)=0 exactly when ρ is separable; Nppts(ρ)=0 and N(ρ)=0 each hold exactly when ρTA≥0. These zero sets distinguish the measures. The phrase “in general” is not a universal strictness condition.
§II.C, unnumbered claim
Fix a finite adaptive LOCC protocol with arbitrary positive finite input and output dimensions, including a fixed final classical recording map. For input density matrix ρ, write pi and ρi′ for its probabilities and normalized positive-probability conditional outputs. Then both
The two robustness measures are defined by their actual separable and PPT bases. This retains selective, rather than only deterministic, monotonicity.
§I–II, sentence crossing PDF pp. 1–2
For any finite deterministic LOCC protocol P and any bipartite density matrix ρ,
EN(P(ρ))≤EN(ρ).
Here P(ρ) sums all subnormalized leaves after forgetting the transcript; input and output local dimensions may differ. This is the deterministic monotonicity asserted in the introduction and supported by §II.
§III.A, Proposition 4, Eq. (30)
Let m≥1 and let ρ be a state on Cm⊗Cm. Let P+ be its standard maximally entangled state, and let Δ(P+,ρ) be the infimum of ∥P+−P(ρ)∥1 over deterministic LOCC protocols P. Then
Δ(P+,ρ)≥2(1−m1+2N(ρ)).
The trace norm is unhalved. No optimal protocol is assumed to exist.
§III.B, Lemma 5 (adapted from [27]), Eq. (37)
Let m≥1 and let ρ be an m×m bipartite density matrix. For a deterministic LOCC teleportation protocol T, let ΛT,ρ map Alice's unknown input state to Bob's output. Define dmin by taking the infimum over T of the Haar average of ∥∣ϕ⟩⟨ϕ∣−ΛT,ρ(∣ϕ⟩⟨ϕ∣)∥1. Then
dmin(ρ)=m+1mΔ(P+,ρ).
The protocol is fixed before the unknown input. This optimized equality is the numbered result adapted from reference [27].
§IV, Proposition 7, Eq. (44)
Let ρ be a finite bipartite density matrix and 0≤ε<1. Define achievable nonnegative rates using the source's universal condition on diverging integer sequences: mα counts input copies, nα output Bell pairs, and limsupnα/mα≤c requires limsupΔ(Υ⊗nα,ρ⊗mα)≤ε. The supremum EDε is taken in the extended nonnegative reals. Then
EDε(ρ)≤EN(ρ).
The case ε=0 is included. The input/output letter interchange near Eq. (41) is resolved by Eq. (43) and the proof.
§V.A, Proposition 8, Eq. (48)
Let ∣ψ⟩=∑ici∣ui⟩⊗∣vi⟩ be a Schmidt expansion, where the two vector families are orthonormal, ci≥0, and ∑ici2=1. For ρ=∣ψ⟩⟨ψ∣,
N(ρ)=2(∑ici)2−1,Nss(ρ)=2N(ρ).
Coefficients are amplitudes, not squared eigenvalues; zero padding and rectangular local spaces are allowed. The robustness identification retains the source's attribution to [18].
§V.A, Eq. (50) and equality characterization
For normalized Schmidt data ∣ψ⟩=∑ici∣ui⟩∣vi⟩, with ci≥0, write ρ=∣ψ⟩⟨ψ∣ and ρA=TrBρ. Its entropy in bits satisfies
Zero coefficients contribute zero. Equality holds if and only if every pair of nonzero coefficients is equal. This includes rank-one product states and maximal entanglement on a proper Schmidt support.
§V.B, Eqs. (51)–(52)
Let d≥1, let F swap the two d-dimensional factors, and let P+ be the maximally entangled projector. Choose real a,b,c so that ρ=adP++bF+cI is a density matrix. Set f=dTr(ρP+) and g=Tr(ρF). Then
N(ρ)=4∣1−f∣+4∣1+f−2g/d∣+2∣g/d∣−21.
This computes the measure on the actual family (51), including d=1.
§V.B, Eq. (53)
For a density matrix ρ=adP++bF+cI as in Eq. (51), put f=dTr(ρP+) and g=Tr(ρF). Then
Nss(ρ)=Nppts(ρ)=21max{∣2f−1∣−1,∣2g−1∣−1,0}.
Both robustness quantities retain their variational definitions. The background coincidence of PPT and separability is specific to this family and is attributed by the source to [22].
§V.C, Eq. (64)
Let γ=(ACTCB) be a positive definite physical two-mode covariance matrix, so A,B are real symmetric 2×2 matrices and γ+iσ/2≥0. Use σ=diag(J,J) with J=(0−110), and let γTA reverse Alice's momentum. Then
det(ξI−σ−1γTA)=ξ4+(detA+detB−2detC)ξ2+detγ.
The polynomial's plus sign is retained; its roots occur as imaginary symplectic pairs.
Correction to the printed source.
Printed: PDF p.9 prints the standard block [[0,1],[1,0]] and describes the roots near Eq.(64) as real pairs.
Corrected: Use J=[[0,1],[-1,0]], explicitly in symplecticTwo and the covariance hypothesis; preserve every coefficient of Eq.(64).
Reason: Eq.(54) explicitly requires an antisymmetric symplectic form; the preceding normal-mode paragraph gives imaginary eigenvalue pairs. At the physical vacuum gamma=I/2 the characteristic polynomial is (X^2+1/4)^2. The symmetric printed block would give (X^2-1/4)^2. This is the minimal sign repair consistent with the source's commutation convention.
§VI.A and note [33], PDF pp. 10–11
For a tripartite density matrix, let M0=NAB∣C, M1=NAC∣B, and M2=NBC∣A. For every finite adaptive LOCC protocol acting on the three separated parties, with normalized positive-probability outputs ρi′ and probabilities pi, all three grouped negativities obey
∀k∈{0,1,2},i:pi>0∑piMk(ρi′)≤Mk(ρ).
All regroupings are computed from the same state. Local dimensions may change, and a fixed final coarse-graining is allowed. The other three functions in threePartyMeasures are reduced-state negativities defined by the source for a noncooperating discarded party; this theorem makes no monotonicity assertion about them under three-party LOCC.
§VI.B, Eq. (66)
For a four-party density matrix ρABCD, form ρABC=TrDρ and ρAB=TrCρABC. Then
NA∣BCD(ρ)≥NA∣BC(ρABC)≥NA∣B(ρAB),
and the same two inequalities hold for EN. These compare the measures and hence their distillation upper bounds. They do not compare actual optimal rates of different distillation tasks.
These additional statements have current no-edit source review. Their formal proofs remain open; deferred results are excluded.
NLTS Hamiltonians from good quantum codesResearch Paper
Motivation
NLTS Hamiltonians from good quantum codes establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.
Setting
Fix positive clustering constants c1,c2,δ0, a bound s on the number of nonzero entries in each row and column of the binary check matrices, and a positive constant B bounding the total number of checks by Bn. There exist a>0 and an integer n0≥2, uniform over the code, state, energy density and preparing circuit, with the following property.
For n≥n0, let Hx∈F2mx×n and Hz∈F2mz×n be check matrices with mx,mz>0, sparsity at most s, and mx+mz≤Bn. Put Cx=kerHx and Cz=kerHz, and assume the CSS condition Cx⊥⊆Cz. Write k for the encoded dimension, and assume k≥2. Assume Property 1: for every 0≤δ<δ0 and every y∈F2n, ∣Hzy∣≤δmz implies ∣y∣Cx⊥≤c1δn or ∣y∣Cx⊥≥c2n, and the same implication holds with x,z interchanged. Here ∣y∣S=minv∈S∣y+v∣, and ∣⋅∣ is Hamming weight. Define the unnormalized check Hamiltonian H=∑w row of Hx(I−Xw)/2+∑w row of Hz(I−Zw)/2, counting all supplied rows.
For every density matrix ρ and every 0≤ϵ<Eeff(C),
tr(Hρ)≤ϵn⟹depth(U)≥alogn
for every preparing circuit U. A preparing circuit consists of layers of disjoint arbitrary one- and two-qubit unitary gates on n+w qubits, for any w≥0, starts in ∣0⟩⊗(n+w), and has reduced output ρ on the first n qubits after discarding the other qubits. Depth is its number of layers; log is the natural logarithm.
Moreover, for every fixed r,q>0, there exist e∗>0 and n1≥2, uniform over all code instances, such that whenever n≥n1, k≥rn and min{mx,mz}≥qn, one has
k≥2,Eeff(C)≥e∗.
Consequently the allowed energy density can be chosen as a positive constant for the constant-rate, linear-distance qLDPC families satisfying Property 1 considered in the paper. The distance parameter does not enter the displayed cutoff; the paper's footnote 3 notes that Property 1 at δ=0 already implies linear distance.
This gives a depth obstruction for every low-energy density matrix, including mixed states, rather than only ground states.
Source correction. The paper prints only ϵ<E(C). Its proof uses Property 1 at 2ϵ1 with ϵ1=200nϵ/min(mx,mz), so we also require 400nϵ<δ0min(mx,mz). This is exactly the missing domain condition; it is automatic if c1≥1. No normalization c1≥1 is imposed, and the frozen printed cutoff is retained as the first entry of the minimum.
Correction to the printed source.
Printed: Theorem 5 permits eps < E(C), where E(C) is the printed energyCutoff, for arbitrary positive c1.
Corrected: Use eps < min(E(C), delta0min(mx,mz)/(400n)); give the eventual positive floor for this same minimum. No other hypothesis, constant, or conclusion is changed.
Reason: The source proof sets epsilon1=200neps/min(mx,mz) on p.3 and applies Property 1 at 2epsilon1 on p.4. Its domain is delta<delta0, but the printed cutoff only supplies 2c1epsilon1<delta0. The additional strict upper bound is exactly 2epsilon1<delta0. It is redundant for c1>=1 and retains every c1<1 instance satisfying the actual proof-domain condition.
Target
Theorem 5 (Formal statement of the NLTS theorem), §2
Fix positive clustering constants c1,c2,δ0, a bound s on the number of nonzero entries in each row and column of the binary check matrices, and a positive constant B bounding the total number of checks by Bn. There exist a>0 and an integer n0≥2, uniform over the code, state, energy density and preparing circuit, with the following property.
For n≥n0, let Hx∈F2mx×n and Hz∈F2mz×n be check matrices with mx,mz>0, sparsity at most s, and mx+mz≤Bn. Put Cx=kerHx and Cz=kerHz, and assume the CSS condition Cx⊥⊆Cz. Write k for the encoded dimension, and assume k≥2. Assume Property 1: for every 0≤δ<δ0 and every y∈F2n, ∣Hzy∣≤δmz implies ∣y∣Cx⊥≤c1δn or ∣y∣Cx⊥≥c2n, and the same implication holds with x,z interchanged. Here ∣y∣S=minv∈S∣y+v∣, and ∣⋅∣ is Hamming weight. Define the unnormalized check Hamiltonian H=∑w row of Hx(I−Xw)/2+∑w row of Hz(I−Zw)/2, counting all supplied rows.
For every density matrix ρ and every 0≤ϵ<Eeff(C),
tr(Hρ)≤ϵn⟹depth(U)≥alogn
for every preparing circuit U. A preparing circuit consists of layers of disjoint arbitrary one- and two-qubit unitary gates on n+w qubits, for any w≥0, starts in ∣0⟩⊗(n+w), and has reduced output ρ on the first n qubits after discarding the other qubits. Depth is its number of layers; log is the natural logarithm.
Moreover, for every fixed r,q>0, there exist e∗>0 and n1≥2, uniform over all code instances, such that whenever n≥n1, k≥rn and min{mx,mz}≥qn, one has
k≥2,Eeff(C)≥e∗.
Consequently the allowed energy density can be chosen as a positive constant for the constant-rate, linear-distance qLDPC families satisfying Property 1 considered in the paper. The distance parameter does not enter the displayed cutoff; the paper's footnote 3 notes that Property 1 at δ=0 already implies linear distance.
This gives a depth obstruction for every low-energy density matrix, including mixed states, rather than only ground states.
Source correction. The paper prints only ϵ<E(C). Its proof uses Property 1 at 2ϵ1 with ϵ1=200nϵ/min(mx,mz), so we also require 400nϵ<δ0min(mx,mz). This is exactly the missing domain condition; it is automatic if c1≥1. No normalization c1≥1 is imposed, and the frozen printed cutoff is retained as the first entry of the minimum.
Correction to the printed source.
Printed: Theorem 5 permits eps < E(C), where E(C) is the printed energyCutoff, for arbitrary positive c1.
Corrected: Use eps < min(E(C), delta0min(mx,mz)/(400n)); give the eventual positive floor for this same minimum. No other hypothesis, constant, or conclusion is changed.
Reason: The source proof sets epsilon1=200neps/min(mx,mz) on p.3 and applies Property 1 at 2epsilon1 on p.4. Its domain is delta<delta0, but the printed cutoff only supplies 2c1epsilon1<delta0. The additional strict upper bound is exactly 2epsilon1<delta0. It is redundant for c1>=1 and retains every c1<1 instance satisfying the actual proof-domain condition.
Significance
These are known results from the cited paper. The current contribution consists of source-reviewed, compiler-checked theorem statements and mathematical definitions. Formal proofs remain open. Only the listed selected results are in scope; no whole-paper completeness is claimed.
Difficulty
A complete solution must establish every quantified conclusion under the exact stated hypotheses, including error, probability and resource conditions wherever present. The source assumptions and conventions are recorded in the attached statements and independent readbacks.
Formalization scope
Definitions preserve the existing reviewed Lean interfaces. Every target proof is currently sorry, so each target is Open. Printed-source corrections, where necessary, are labeled with the printed claim, the change and its reason.
There is a deterministically explicit family of binary CSS check descriptions on n qubits, and constants ϵ,c,a,b>0, a locality bound s, and a threshold n0≥1, all independent of n. Explicit means that a deterministic polynomial-time function on unary n outputs the actual row counts and both binary check matrices. For every n≥1, both check matrices have row and column weights at most s, their total row count mn satisfies an≤mn≤bn, and their associated projector terms hi=(I−Xwi)/2 or (I−Zwi)/2 act on at most s qubits, commute, and annihilate a common unit vector. Let Hn=∑ihi be this unnormalized Hamiltonian. Every circuit P of parallel one- and two-qubit unitaries on disjoint wires, starting from zero qubits and allowing arbitrary clean ancillas and discarded qubits, has an output density operator ρP satisfying, for n≥n0,
Tr(HnρP)<ϵn⟹depth(P)≥clnn.
This is the existence of an NLTS Hamiltonian family. Quantifying over every preparation circuit gives the lower bound for mixed as well as pure low-energy states.
Formalization Note The deterministic interpretation of explicit and the CSS witness implementation are recorded for independent moderation; the theorem does not assume an NLTS guarantee on its family.
Section 2: support of both measurement distributions
Let HX,HZ be a binary CSS check presentation with n,mx,mz>0, and let ρ be any density operator with Tr(Hρ)≤ϵn, where ϵ≥0 and H is the sum of the actual check projectors. Write Dz,Dx for its standard- and product-Hadamard-basis distributions and Gbδ for the words violating at most a δ fraction of the actual checks on side b. For every ϵ1>0,
Dz(Gzϵ1)≥1−ϵ1mzϵn,Dx(Gxϵ1)≥1−ϵ1mxϵn.
If ϵ=0, both Gz0 and Gx0 have probability one. If ϵ>0, choosing ϵ1=200nϵ/min(mx,mz) gives both masses at least 199/200.
These bounds place low-energy measurement outcomes in the approximate classical codes. The energy identity and probability bounds are conclusions of the source argument, not hypotheses of the formal statement.
Section 2: equivalence classes and separated clusters
Let CX=kerHX and CZ=kerHZ be a binary CSS pair satisfying Property 1 with positive constants c1,c2,δ0. Assume ϵ1≥0, 2ϵ1<δ0, and 4c1ϵ1<c2. On Gzϵ1 define x∼zy when ∣x+y∣CX⊥≤2c1ϵ1n, with the corresponding definition on Gxϵ1 modulo CZ⊥. Here ∣v∣S=mins∈S∣v+s∣. For either basis this is an equivalence relation. Its distinct computed classes are nonempty, pairwise disjoint, and cover the corresponding approximate code. Distinct classes satisfy
x∈B,y∈B′,B=B′⟹∣x−y∣≥c2n.
This constructs the separated clusters needed for the depth argument.
Formalization Note The strict domain follows Property 1 on page 2; the page-4 prose writes a non-strict endpoint. The classes are computed from the relation rather than supplied with a separation guarantee.
Correction to the printed source.
Printed: Page 4 says 'assuming 2 epsilon1 <= delta0', but Property 1 on page 2 is stated only for delta < delta0.
Corrected: Use 0 <= epsilon1 and the strict inequality 2 epsilon1 < delta0 in the clustering regime.
Reason: The proof invokes Property 1 at delta = 2 epsilon1; the strict domain is necessary. This is a standing-domain clarification pending independent moderation.
Lemma 2: one basis has no highly concentrated cluster
Consider a binary CSS presentation with n,mx,mz>0 and logical dimension k≥1, satisfying Property 1 with c1,c2,δ0>0. Let ρ be any density operator. Assume ϵ1≥0, 2ϵ1<δ0, 4c1ϵ1<c2, and
2c1ϵ1≤(4nk−1)2.
For the computed clusters in the preceding result, either every standard-basis cluster has Dz-mass strictly less than 99/100, or every Hadamard-basis cluster has Dx-mass strictly less than 99/100.
This uncertainty consequence selects a basis in which no single cluster captures almost all probability. It requires no low-energy hypothesis once the clusters are defined.
Formalization Note The subtraction k−1 takes place in the reals. The positive-k reading comes from the section's positive-rate setting and is flagged for independent moderation.
Correction to the printed source.
Printed: The displayed finite lemma does not explicitly say k>=1, while Section 2 is introduced for constant-rate code families.
Corrected: State the finite lemma for k>=1 and n,mx,mz>0, keeping ((k-1)/(4n))^2 with real subtraction.
Reason: The proof uses a positive logical dimension; at k=0 the zero-radius clusters can concentrate in both bases. The finite positive-rate reading requires independent moderation.
Fact 3: uncertainty for subsets in conjugate bases
Let ρ be any n-qubit density operator, and let Dz,Dx be its standard- and product-Hadamard-basis measurement distributions. For all sets S,T⊆{0,1}n,
Dx(T)≤21−Dz(S)+2n∣S∣∣T∣.
This bounds concentration in conjugate bases and applies to mixed states. No positive-mass hypothesis on S is required; empty sets and n=0 are allowed.
Section 2: positive-mass separated unions
Let a binary CSS presentation on n>0 qubits satisfy Property 1 with c1,c2,δ0>0, and assume ϵ1≥0, 2ϵ1<δ0, and 4c1ϵ1<c2. Fix either basis and any density operator ρ. Suppose its measurement distribution D gives the approximate-code set mass at least 199/200, while each computed class has mass less than 99/100. Then there are disjoint subcollections M,M′ of the computed classes whose unions S,S′ are disjoint and satisfy
D(S)≥4001,D(S′)≥4001,∣x−y∣≥c2n(x∈S,y∈S′).
This extracts two positive-mass separated sets in whichever basis Lemma 2 selects. Both probability constants and the cross-union separation are retained.
Fact 4: depth lower bound for well-spread distributions
Let P be a circuit of depth t consisting of layers of disjoint one- and two-qubit unitaries, starting in the all-zero product state. Allow any number of clean ancillas and measure only its n>0 output qubits in the standard basis, giving distribution D. Let 0<μ<1, and suppose D(S),D(T)≥μ. For any u≥0 such that every x∈S,y∈T has Hamming distance at least u,
u2≤400nln(1/μ)23t.
For positive set distance this is equivalently t≥31log2(dist(S,T)2/(400nln(1/μ))).
This is the quantitative circuit-depth obstruction for well-spread output distributions. The exponential formulation also covers overlapping sets without taking the logarithm of zero; the original circuit's workspace is unrestricted.
Lemma 8: expansion implies clustering
Let A∈F2m×n and V⊆F2n. Let δ>0 and 0<μ<ν. Suppose every x∈V with ∣x∣≤νn satisfies ∣Ax∣≥(δ/μ)∣x∣. Then
x∈V,∣Ax∣≤δn⟹∣x∣≤μnor∣x∣≥νn.
This transfers small-set expansion to the clustering dichotomy. Both the size cutoff and syndrome cutoff use the number of columns n, even for rectangular matrices.
Formalization Note Positivity is taken from the proof and the paragraph immediately following Lemma 8; the unsupported zero-δ extension is excluded.
Correction to the printed source.
Printed: The displayed Lemma 8 omits its parameter domain; its proof uses delta>0 and mu>0 and the following paragraph takes mu<nu.
Corrected: State Lemma 8 on the meaningful positive regime delta>0 and 0<mu<nu, as pinned by the plan and proof.
Reason: For delta=0, an expansion hypothesis with beta=0 supplies no information and the claimed nontrivial dichotomy can fail. Independent moderation must confirm the intended domain.
Let F be a family of binary CSS check presentations. Fix positive αx,βx,αz,βz,δˉ,a,b and n0≥1. For all n≥n0, suppose an≤mx(n),mz(n)≤bn. For every 0≤δ<δˉ, define Vzδ as the words in Gzδ of minimum Hamming weight within their coset modulo CX⊥, and define Vxδ analogously modulo CZ⊥. Assume HX is (αx,βx)-expanding on Vxδ and HZ is (αz,βz)-expanding on Vzδ. Then there are constants c1,c2,δ0>0, independent of n, such that for all n≥n0 and 0≤δ<δ0,
y∈Gzδ⟹∣y∣CX⊥≤c1δnor∣y∣CX⊥≥c2n,
and the same dichotomy holds on the X side modulo CZ⊥.
This derives Property 1 from uniform expansion of minimal representatives, without assuming the desired dichotomy. The check-density factors converting δmside to a threshold relative to n are retained.
These additional statements have current no-edit source review. Their formal proofs remain open; deferred results are excluded.
Let ρ be an n-qubit density matrix and Q a Hermitian observable. Let O1,…,Ot be finite Kraus maps, with no trace-preservation requirement, applied in chronological order. Write ρf=Ot⋯O1(ρ), r(ρ)σ=Tr(σρ), q(Q)σ=2−nTr(σQ) and M(O)σ,τ=2−nTr(σO(τ)), in the order I,X,Y,Z on each wire. Then
Traces in these coordinates are real. The empty circuit has identity transfer matrix. These identities connect the physical experiments to real linear algebra.
§V (1)
Consider a fixed finite mitigation design on n qubits. Its slots comprise a product preparation, an ordered list of inverse or compensation stages, and an observable measurement; every slot is used exactly once. At slot j, let qj,i be real coefficients, let Cj=∑i∣qj,i∣, and set C=∏jCj. Assume the ideal density matrix, ideal Hermitian observable and each ideal stage map equal the corresponding signed sums of their physical realizations, on every input operator. In an inverse stage the native map precedes the correction; compensation chooses either the native map or a basis branch.
Sample each choice with weight ∣qj,i∣/Cj, run the resulting physical circuit, and multiply the readout by the sign of the product of selected coefficients. A rejected postselection returns zero and remains a trial. If Y is this effective outcome and m is the ideal circuit expectation, then
ω∑Pr(ω)=1,CE[Y]=m,E[RCs=1∑RYs]=m(R≥1).
Here Ys are independent complete trials. If a slot has zero coefficient mass, the defined trial is a zero-scoring dummy; the decomposition then has zero target expectation. This states conditional factorization, rather than existence of a complete calibrated design.
Correction to the printed source.
Printed: PDF p.4 prints the preparation and output sampling probabilities as q/C, without absolute values.
Corrected: Use |q|/C for preparations and readouts as well as gate choices; negative coefficients remain encoded in the estimator sign.
Reason: The same paper's §IV p.4 and Appendix I.3 p.19 explicitly prescribe absolute weights. Signed q/C can be negative and is not a probability. Independent moderation is required.
§VI
Let Y take values +1,−1 with probabilities p,1−p, where 0≤p≤1. Let C>0, m=C(2p−1) and ∣m∣≤1. For independent trials Y1,…,YR, with integers R,R0≥1, let m=CR−1∑iYi. Then
E[(m−m)2]=RC2−m2,E[(m−m)2]≤RC.
If ∣m∣<1, equality of this variance with the ideal binary-sampling variance (1−m2)/R0 holds exactly when
R0R=1−m2C2−m2.
The model has no postselection zeros. The formula distinguishes the exact overhead ratio from the usual C2 approximation; any desired positive standard deviation can be met using the displayed upper bound.
Table I; §VII
Use the sixteen matrices Ai in Table I, in their printed order, and the superoperators Bi(X)=AiXAi†. Let Wi be the corresponding printed word with Rx=HS3H, Rz=S3 and π=∣0⟩⟨0∣. Words are matrix products, so their rightmost factor acts first. For every i=1,…,16,
[Wi]=Bi,[A](X):=AXA†.
The phase convention for S is irrelevant at the superoperator level. The three primitive letters are H,S,π; postselection denotes the accepted branch, without renormalization. These equalities give physical words for the library. Linear independence is stated in the separate completeness item.
§VII; Appendix D
Let B1,…,B16 be the real 4×4 Pauli transfer matrices of Table I. Form the 16×16 matrix A whose columns are their column vectorizations. Then A is invertible. For every n≥0 and every real matrix E on the n-wire Pauli coordinate space, there is exactly one real coefficient array q such that
E=i1,…,in=1∑16qi1,…,inBi1⊗⋯⊗Bin.
For n=0 this is the scalar basis. The span concerns signed maps, including trace-decreasing branches, rather than only channels. It supplies the algebraic completeness needed for cancellation.
§VII, T example
Let T=diag(1,eiπ/4) and Rz=(I+iZ)/2 as in Table I. Write [A](X)=AXA†. Then, on every qubit operator,
Here Rz3 implements S up to global phase. This is an expectation-estimation decomposition, not deterministic synthesis with the corresponding time cost.
Appendix B (B2)
Let X,Z,Rx,Rz,πx=(I+X)/2,πz=(I+Z)/2 be the Table I matrices, let [A](ρ)=AρA†, and put the control in the first tensor factor. Then
The twelve coefficients have absolute sum 6/2+6=9. The identity holds on every operator; projective branches are unnormalized. It exhibits how local signed operations represent an entangling gate.
Appendix C (C1)–(C3); Appendix F (F10)
Let d≥1 and let A0,A be real d×d matrices. Define s=λmin(A0TA0), with eigenvalues counted with multiplicity. All norms below are Euclidean vector norms or their induced operator norms. If e=∥A−A0∥2<s, then
A is invertible,∥Ax∥2≥(s−e)∥x∥2for every x,∥A−1∥2≤(s−e)−1.
The strict inequality makes the denominator positive and the lower bound strictly positive for nonzero x. This is the symbolic robustness argument used for operation and SPAM completeness.
Appendix D (D1)–(D3)
For wire j=1,…,n, let Bj,i (i=1,…,16) be real 4×4 basis matrices and let Aj be the square matrix with columns vec(Bj,i). Assume each Aj invertible. For a real n-wire map E, vectorize by interleaving each wire's column and row indices, using the column-first convention of Eq. (2), correcting the reversed local pairs in (D3), and define
q=(A1⊗⋯⊗An)−1vecint(E).
The tensor synthesis matrix is invertible and
E=i∑qij⨂Bj,ij;
every coefficient array representing E equals this computed q. Empty tensors have scalar value one. This pins the construction rather than quantifying over unrelated coefficients.
Correction to the printed source.
Printed: Eq. (2), PDF p.5, stacks each basis matrix by columns. D3, PDF p.13, instead starts with E_{I...I,I...I}, E_{I...I,I...X}, varying the column index before the row index.
Corrected: Use column-then-row local index pairs, evaluating E(row,column), in both the tensor synthesis matrix and the interleaved target vector. This swaps the local row/column order printed in D3; all tensor factors and basis-operation labels retain their order.
Reason: D1 and the inverse-coordinate construction use the synthesis matrices defined by Eq. (2). Their target vector must use the same ordering. Correcting only D3 makes those formulas consistent; it changes neither the represented operation nor any coefficient-mass bound. Independent moderation must verify this source correction.
Appendix D, pp.13–14
Use reference preparations ∣0⟩,∣1⟩,∣+⟩,∣y+⟩ and reference observables I,X,Y,Z. Let Min0 have entries Tr(σaρi0), and let Mout0 have entries 21Tr(σaQi0), in Pauli order. For physical density preparations ρi and Hermitian observables Qi, form Min,Mout with the same formulas. The reference frames are invertible. With ∥⋅∥max denoting largest absolute entry,
∥Mα−Mα0∥max<41smin(Mα0)⟹Mα is invertible(α=in,out).
Whenever Min is invertible, every column v has unique coordinates q=Min−1v. Whenever Mout is invertible, every row w has unique coordinates q=wMout−1. Multiplication by the respective frame reconstructs the target exactly. These statements include all complete frames, not only nearby ones.
§VIII, pp.5–6
Let E0,E be ideal and native real Pauli transfer matrices on n wires. On each wire let Bj,1,…,Bj,16 be a complete real operation basis with invertible synthesis matrix Aj. Fix any real λ. Define q by applying the inverse tensor synthesis matrix to the interleaved coordinates of E0−λE. Then
E0=λE+i∑qij⨂Bj,ij,
and this coefficient array is unique for the chosen λ. No inverse of E is required. This is the algebraic compensation witness; physical sampling is conditional on the branch realizations.
Correction to the printed source.
Printed: Eq. (2), PDF p.5, stacks each basis matrix by columns. D3, PDF p.13, instead starts with E_{I...I,I...I}, E_{I...I,I...X}, varying the column index before the row index.
Corrected: Use column-then-row local index pairs, evaluating E(row,column), in both the tensor synthesis matrix and the interleaved target vector. This swaps the local row/column order printed in D3; all tensor factors and basis-operation labels retain their order.
Reason: D1 and the inverse-coordinate construction use the synthesis matrices defined by Eq. (2). Their target vector must use the same ordering. Correcting only D3 makes those formulas consistent; it changes neither the represented operation nor any coefficient-mass bound. Independent moderation must verify this source correction.
§VIII, pp.5–6
Let E0,E be invertible ideal and native real operation matrices. Let the local bases Bj,i have invertible synthesis matrices, and define N=EE0−1. Then NE0=E and N−1=E0E−1. The computed tensor coordinates q of E0E−1 are the unique representation of N−1, and
E0=(i∑qij⨂Bj,ij)E.
Thus the physical order is the native operation followed by its sampled correction. Both inverses have explicit hypotheses; the inverse noise need not itself be a channel.
Correction to the printed source.
Printed: Eq. (2), PDF p.5, stacks each basis matrix by columns. D3, PDF p.13, instead starts with E_{I...I,I...I}, E_{I...I,I...X}, varying the column index before the row index.
Corrected: Use column-then-row local index pairs, evaluating E(row,column), in both the tensor synthesis matrix and the interleaved target vector. This swaps the local row/column order printed in D3; all tensor factors and basis-operation labels retain their order.
Reason: D1 and the inverse-coordinate construction use the synthesis matrices defined by Eq. (2). Their target vector must use the same ordering. Correcting only D3 makes those formulas consistent; it changes neither the represented operation nor any coefficient-mass bound. Independent moderation must verify this source correction.
§VIII
Let E0,E be ideal and native real operation matrices, let r>1, and let the local operation bases be complete. For fixed real λ, set Eb=(1−r)E0+rE and compute the tensor coordinates q of Eb−λE. Then
Eb=λE+i∑qij⨂Bj,ij,
with a unique coefficient array for this λ. The statement asserts a signed linear decomposition. It does not assert nonnegative coefficients or complete positivity of Eb; the favorable Pauli boosting example is a separate model-specific observation.
Correction to the printed source.
Printed: Eq. (2), PDF p.5, stacks each basis matrix by columns. D3, PDF p.13, instead starts with E_{I...I,I...I}, E_{I...I,I...X}, varying the column index before the row index.
Corrected: Use column-then-row local index pairs, evaluating E(row,column), in both the tensor synthesis matrix and the interleaved target vector. This swaps the local row/column order printed in D3; all tensor factors and basis-operation labels retain their order.
Reason: D1 and the inverse-coordinate construction use the synthesis matrices defined by Eq. (2). Their target vector must use the same ordering. Correcting only D3 makes those formulas consistent; it changes neither the represented operation nor any coefficient-mass bound. Independent moderation must verify this source correction.
Appendix E (E1)–(E7); §IX
Fix an n-qubit physical tomographic frame of density preparations and observable measurements, with invertible input and output matrices Min,Mout. Let T be an invertible real gauge, fixed for all operations, and let Oj be finite Kraus maps in chronological order. Form the exact measured matrices Oj,ab=Tr(QaOj(ρb)) and g=MoutMin. Then g is invertible and
For every input and readout label b,a, including an empty operation sequence,
Tr(QaOt⋯O1(ρb))=(gT−1)a,∙Ot⋯O1T∙,b.
This establishes prediction invariance using computed exact calibration data; estimated coordinates need not be physical states.
Appendix F (F1)–(F6)
Let Min,j,Mout,j be invertible real local tomography frames on n wires. Use the reference matrices Min0,Mout0 computed from the Appendix D preparations and observables. Let ein=maxj∥Min,j−Min0∥2 and eout=maxj∥Mout,j−Mout0∥2. For the choice Tj=Min0, the estimated input frame is exactly Min0, so its error is zero. The estimated output frames are Mout,jMin,j(Min0)−1 and satisfy
The empty-wire maxima are zero. This keeps the valid symbolic bound separate from the printed numerical norm evaluations.
Appendix F (F7),(F8),(F13),(F14)
Let Mj be local real input-frame matrices, M0 the computed reference input matrix, M=⨂jMj, T=M0⊗n, and e=maxj∥Mj−M0∥2. Let O,O0 be real operation matrices and put eO=∥O−O0∥2, s=smin(M0) and en=(∥M0∥2+e)n−∥M0∥2n. Assume en<sn. Then M is invertible and
∥M−T∥2≤en,∥M−1∥2≤(sn−en)−1.
For the computed GST estimate O=TM−1OMT−1,
∥O−O0∥2≤sn−en2en(∥O0∥2+eO)+eO.
The empty tensor case has en=0 and identity gauge. This states the source proof's small-error domain, not a bound with a nonpositive denominator.
Correction to the printed source.
Printed: F14 and its use in F7 display an inverse norm bound without an explicit small-error inequality at that point.
Corrected: Require e_n<s_min(Min0)^n before applying the displayed reciprocal bound; keep all symbolic norms and the printed F7 formula.
Reason: The proof invokes F10 and C3, whose strict smallness condition makes the denominator positive. Invertibility alone is insufficient; this proof-domain clarification requires independent moderation.
§X (3); Appendix G (G1)–(G4)
Let Bj,i be real local library maps, let Aj be their 16×16 synthesis matrices, and let A0 be the synthesis matrix computed from Table I. Put emax=maxj∥Aj−A0∥max and s=smin(A0). Let O0,O be target and native n-wire real operation matrices, with eO=∥O0−O∥max. If emax<s/16, compute q by inverse tensor synthesis of O0−O. Then
The denominator is positive. This is a bound on the constructed λ=1 witness, without an assumed inverse-norm conclusion or any claim of optimality.
Correction to the printed source.
Printed: Eq. (2), PDF p.5, stacks each basis matrix by columns. D3, PDF p.13, instead starts with E_{I...I,I...I}, E_{I...I,I...X}, varying the column index before the row index.
Corrected: Use column-then-row local index pairs, evaluating E(row,column), in both the tensor synthesis matrix and the interleaved target vector. This swaps the local row/column order printed in D3; all tensor factors and basis-operation labels retain their order.
Reason: D1 and the inverse-coordinate construction use the synthesis matrices defined by Eq. (2). Their target vector must use the same ordering. Correcting only D3 makes those formulas consistent; it changes neither the represented operation nor any coefficient-mass bound. Independent moderation must verify this source correction.
§XI, pp.10–11
Assume the exact model z(e)=aexp(−κe) with a>0 and decay rate κ>0. Let e0>0 and r>1. Its two positive model values recover the zero-error value exactly:
z(e0)r/(r−1)z(re0)1/(1−r)=a=z(0).
The positivity assumptions specify real powers. This is conditional on exponential decay to zero and exact model points; it makes no unbiasedness assertion about ratios of noisy empirical measurements and no universal decay claim for Markovian errors.
Appendix H
Let U be an ideal n-qubit unitary and let G be any channel in finite normalized Kraus form. Set Nb=id and Na=G∘[U†], where [U](X)=UXU†. Then
Na,Nb are channels,G=Na∘[U]∘Nb.
This constructs the before/after noise model explicitly. The required inverse is the ideal unitary channel; invertibility of the noisy channel is unnecessary.
Appendix J
Let wx,wy,wz≥0 sum to one and let 0<ϵ≤1. Set pα=ϵwα and E′=∑α=x,y,zwα[σα]. Then
The component E′ is independent of ϵ because the ratios are fixed. The identities hold on all input operators and avoid division by zero.
Appendix J (J1); §XI p.9
Let π0=∣0⟩⟨0∣, π1=∣1⟩⟨1∣ and Lp=[π0+1−pπ1]. For 0<p≤1, define c(p)=(1−p−(1−p))/p and
Ep′(X)=π0Xπ0+c(p)(π0Xπ1+π1Xπ0).
For every qubit operator X,
Lp(X)=(1−p)X+pEp′(X).
Moreover c(p)→21 as p↓0 and c(p)−21=O(p) on the punctured positive neighborhood of zero, with uniform constants on that neighborhood. This describes slow variation of a trace-decreasing model's component, not exact exponential decay of all expectations.
Formalization scope
Only these reviewed original-paper statements are in scope. Definitions have reviewed bodies; target proofs remain open (sorry). Reviewed deferrals are excluded. No theorem proof or whole-paper formal proof is claimed.
Integer multiplication: κ = 1/2^182 (OpenAI manuscript construction)Open Problem
Motivation
Multiplying two binary integers is a basic task in computational complexity. The relevant resource here is the number of individual steps made by a machine whose tapes can only be accessed through moving heads. Harvey and van der Hoeven established an O(nlogn) bound in this model. The OpenAI manuscript proposes a positive saving in the exponent of the logarithm. Subsequent constructions explore larger savings. The formalization target is the complete computation and its time bound, including the analytic and implementation arguments needed to connect a finite construction to every input length.
Setting
A deterministic multitape Turing machine has a fixed finite alphabet, a fixed finite state set, and a fixed finite number of tapes. Each tape extends in one direction and has one head. A step reads the symbols under the heads, changes state, writes at those positions, and moves each head by at most one cell. The alphabet contains distinct blank, start-marker, zero, one, and separator symbols. Tape zero is the read-only input tape; tape one is the output tape; further tapes are available for work. The halting state freezes the configuration.
An input consists of two bit strings x,y of the same positive length n, separated by #. The strings are read most significant bit first, with leading zeros permitted. If val(x) denotes the represented natural number, the required output is exactly the 2n-bit binary representation of val(x)val(y), padded with leading zeros and followed by blanks. All tapes begin with a preserved start marker. Define L(n)=max(⌈log2n⌉,1).
Target
The full target is
IntMul.KappaBound(1/2182).
This asserts the existence of one machine that computes the exact product correctly for every positive input length, together with constants c>0 and n0 such that every pair of n-bit inputs, for n≥n0 and n≥1, halts within
cnL(n)1−1/2182
steps. Constants, alphabet, states, and tape count are independent of the input length. The number is an exact real value. Larger κ gives a stronger asymptotic saving because L(n)≥1.
Each entry supplies its own exact numerical value and identifies the construction that motivates it. Historical and new entries use the same machine definition. A proposed value may be recorded while its complete proof is still open; it becomes a proved record only when the goal has a verified proof. Numerical certificates are supporting results with their own scope, and do not establish a complete machine time bound.
Significance
A proof for any positive value would give a strict asymptotic improvement over nlogn. Such an improvement would contradict the proposed Ω(nlogn) lower bound, while remaining consistent with the known upper bound. The tracked value concerns asymptotic growth; it does not measure the runtime of a practical implementation. No claim about a currently fastest implementation follows from a larger saving.
Formalizing the full target connects exact finite calculations to a uniform algorithm. The community repository explicitly treats the original framework and remaining all-size interfaces as assumptions of its current evidence. In this mission those steps must be proved before the goal can be marked Proved. They are not added as hypotheses that would weaken the full target. Earlier published theorem statements and finite certificates may be reused with their original attribution and proof status.
Difficulty
A finite network certificate can establish a concrete role count or a rational margin, but does not itself supply a machine for every input length. A complete proof must establish correctness of the recursive construction, admissibility of its parameters, precision and error guarantees, and the cost of moving data on tapes. Counts of algebraic operations alone do not account for this last resource. The difficult connection is between these separate contracts and the single uniform machine quantified by the goal.
Formalization scope
The goal imports the existing public Definitions.Def_IntMul_MultitapeModel bundle and uses IntMul.KappaBound directly. No alternative machine or cost model is introduced. Natural numbers describe input lengths, head positions, and step counts; real numbers describe the asymptotic constant and exponent. The real power has base at least one. Correctness is required even below the asymptotic threshold. Inputs of length zero and malformed inputs are outside the specified task.
The input and output conventions exclude a machine that merely decides a predicate about the product. The entire output tape must contain the required product and then blanks. Neither failure to halt nor correctness on a finite collection of test inputs meets the target. The work tapes and final head positions are unconstrained. Reusable contributions include machine composition with explicit costs, exact encodings, analytic estimates, and proofs that the finite certificates imply the contracts required by the recursive algorithm. Every such contribution should state its own assumptions and conclusion explicitly.
Selected references
D. Harvey and J. van der Hoeven, Integer multiplication in time O(n log n), Annals of Mathematics 193(2), 563–617 (2021). Paper.
OpenAI, Integer multiplication below n log n, preprint (23 September 2026), pinned manuscript revision adc7f1241b42e322a6451854ab7e4b4c146bf78a. Source.
D. Colkitt and community contributors, A sharper exponent for integer multiplication, research repository (2026), revision 56b66d58297deca1d7dd130247d720e960f77a37. Checkpoint and attribution.
Status
A full Lean proof of this bound is already on the platform: NLogN.KFTop.kappa_bound (theorem f904f4ef), which also proved IntMul.Kappa.openai_theorem_1. It formalizes the OpenAI manuscript's construction (Prop 7/8 networks, τ = 1−2^-50, crude assembly) on top of a verified multitape-machine compiler and the Harvey–van der Hoeven O(n log n) machine. It uses only the standard axioms.
Penrose gravitational state reduction: the self-energy criterionResearch Paper
Motivation
Quantum mechanics prescribes two incompatible evolutions: the unitary Schrödinger evolution of an isolated system, and the discontinuous state reduction that a measurement appears to trigger. The measurement problem is to explain when and why reduction takes over. Penrose's answer, set out in the 1996 paper this mission formalizes, is that gravity drives the transition: a superposition of two distinct mass distributions carries two distinct space-time geometries; the time-translation needed to call such a superposition stationary is inherently ill-defined; and the resulting energy fuzziness destabilizes the superposition, with a characteristic lifetime of order ℏ/EΔ, where EΔ is the gravitational self-energy of the difference between the two mass distributions (Penrose 1996). The idea is an objective-collapse proposal in which observers play no special role; it descends from Károlyházy's 1966 considerations through Diósi's 1989 model (doi:10.1103/PhysRevA.40.1165) and its energy-conserving modification by Ghirardi, Grassi and Rimini (doi:10.1103/PhysRevA.42.1057), and it is testable in principle through the mirror-superposition experiment of Marshall, Simon, Penrose and Bouwmeester (doi:10.1103/PhysRevLett.91.130401). A survey of the physical picture is the Wikipedia article on the Penrose interpretation (https://en.wikipedia.org/wiki/Penrose_interpretation).
The physical criterion T≃ℏ/EΔ is a conjecture about nature, not a theorem, and this mission does not ask for its proof. What is a theorem is the mathematical backbone by which Penrose computes the quantity Δ — the measure of incompatibility of the two superposed space-time geometries in the Newtonian limit — and identifies it, up to an explicit constant, with the gravitational self-energy of the difference of the two mass distributions. Establishing that chain in Lean 4 is this mission's goal.
Setting
Fix a real gravitational constant G. A mass distribution is a smooth, rapidly decreasing (Schwartz) function ρ:R3→R: smooth enough that the potential below is twice differentiable and all integrals converge, and decaying so that boundary terms in the whole-space integration by parts vanish. In Lean these are elements of Mathlib's SchwartzMap over three-dimensional Euclidean space.
The Newtonian potential of ρ is
Φρ(x)=G∫R3∥x−y∥ρ(y)dy,
the gravitational field is f=−∇Φρ, and the Laplacian ∇2 is the trace of the second derivative: the sum of second directional derivatives along the standard orthonormal basis. Penrose's measure of incompatibility of two mass distributions ρ,ρ′ is
Δ(ρ,ρ′)=∫R3∥∇Φρ(x)−∇Φρ′(x)∥2dx,
the squared L2 norm of the difference of the two field gradients (Penrose 1996, Section 6). Two further quantities from the paper: the gravitational self-energy of a distribution σ,
E(σ)=−2G∬R3×R3∥x−y∥σ(x)σ(y)dxdy,
and the interaction energy between two distributions, I(ρ,ρ′)=−G∬ρ(x)ρ′(y)/∥x−y∥dxdy.
Sign conventions. The displayed formulas of Section 6 of the paper mix conventions: the paper's Poisson display ∇2Φ=−4πGρ is inconsistent with its displayed potential formula Φ(x)=−∫ρ(y)/∣x−y∣dy. This mission fixes the convention under which the paper's chain of identities holds as written: ∇2Φρ=−4πGρ, with the potential formula above. Under this convention the first three identities of the displayed chain hold verbatim; the final displayed formula of the paper carries a sign and constant slip and is corrected here to Δ=4πG2∬(ρ−ρ′)(x)(ρ−ρ′)(y)/∥x−y∥dxdy. The physical reading always takes G>0, but no item needs that hypothesis.
Formalization targets
The goal is the paper's central identification: the incompatibility measure is the gravitational self-energy of the difference of the two mass distributions, up to the explicit constant −8πG,
Δ(ρ,ρ′)=−8πG⋅E(ρ−ρ′).
The supporting chain, each step a milestone, from Section 6 of the paper:
∇2Φρ=−4πGρ(Poisson’s equation),Δ(ρ,ρ′)=−∫(Φρ−Φρ′)(∇2Φρ−∇2Φρ′)(x)dx(whole-space integration by parts),Δ(ρ,ρ′)=4πG∫(Φρ−Φρ′)(ρ−ρ′)(x)dx(substituting Poisson),Δ(ρ,ρ′)=4πG2∬(ρ−ρ′)(x)(ρ−ρ′)(y)/∥x−y∥dxdy(substituting the potential formula).
Two structural facts complete the mission: the self-energy is invariant under translation of the distribution (the two locations of Penrose's displaced lump have equal individual self-energies), and under that equal-self-energy hypothesis Δ is determined by the interaction energy and the common self-energy,
Δ=8πG⋅I(ρ,ρ′)−16πG⋅E(ρ),
which is the precise sense of the paper's remark that, apart from the factor 4π, it does not make any difference which expression is used.
Significance
The result itself. The chain turns a space-time consideration — the failure of a consistent time-translation for the superposed geometry — into a computable Newtonian quantity, and identifies that quantity with a classical binding-energy functional. It is the quantitative core of the Diósi–Penrose collapse criterion: every numerical prediction of the model (collapse rates for dust specks, electrons, mirrors) is extracted from the self-energy of the difference distribution.
Formalizing it. None of this chain is formalized anywhere to our knowledge, and Mathlib has no Newtonian-potential layer at all: no potential, no Poisson equation, no gravitational energy functionals. The mission therefore builds reusable infrastructure — Schwartz densities over Euclidean space, the Newtonian potential with its gradient and Laplacian, and the energy functionals — which serves any later Newtonian-gravity formalization (the Schrödinger–Newton equation, Diósi–Penrose dynamics). The proofs exist in the classical potential-theory literature (elliptic regularity for Poisson's equation; change of variables for translation invariance): the mission asks solvers to formalize known mathematics, not to prove new physics.
Difficulty
The naive attack on Poisson's equation — differentiate Φ(x)=G∫ρ(y)/∥x−y∥dy twice under the integral sign — fails at the singularity y=x, where the kernel 1/∥x−y∥ is not even once differentiable. That the potential is nonetheless twice differentiable with ∇2Φ=−4πGρ at every point is a genuine elliptic-regularity theorem; solvers will need either a distributional argument with cutoffs and a limiting step, or a direct construction of the second directional derivatives with explicit remainder estimates. The whole-space integration by parts needs decay control: the difference potential decays only like 1/∥x∥ when the difference distribution has nonzero total mass, so the boundary term over large balls must be estimated rather than assumed zero. The translation-invariance milestone is a change of variables in a double integral whose kernel is singular on the diagonal — routine, but integrability demands care.
Formalization scope
The Lean representation: mass densities are SchwartzMap (EuclideanSpace ℝ (Fin 3)) ℝ; integrals are Bochner integrals with respect to Mathlib's volume on Euclidean space; the Laplacian is the trace of the second Fréchet derivative, the sum of second directional derivatives along the standard basis vectors. The gravitational constant G is an unconstrained real parameter: every identity in the chain is algebraic in G, and the physical reading G>0 is recorded here only. Degenerate inputs: for Schwartz densities every integral appearing in the items converges; nevertheless, Lean's integral returns 0 for a non-integrable integrand, so establishing the relevant integrability is part of each proof — the identities are stated between the honest (convergent) quantities. No item carries an unsatisfiable hypothesis, and no statement is specialized to positive densities: the paper's derivation nowhere uses positivity, so the items quantify over all Schwartz ρ,ρ′. A trivializing formalization is ruled out: Δ is defined independently of the self-energy (an L2 norm of a field difference versus a double integral of densities), and the goal asserts their equality.
Selected references
R. Penrose, On Gravity's Role in Quantum State Reduction, General Relativity and Gravitation 28(5):581–600, 1996. https://doi.org/10.1007/BF02105068
R. Penrose, On the Gravitization of Quantum Mechanics 1: Quantum State Reduction, Foundations of Physics 44(5):557–575, 2014. https://doi.org/10.1007/s10701-013-9770-0
G. C. Ghirardi, R. Grassi, A. Rimini, Continuous-spontaneous-reduction models involving gravity, Physical Review A 42:1057, 1990. https://doi.org/10.1103/PhysRevA.42.1057
W. Marshall, C. Simon, R. Penrose, D. Bouwmeester, Towards Quantum Superpositions of a Mirror, Physical Review Letters 91:130401, 2003. https://doi.org/10.1103/PhysRevLett.91.130401
Wigner quasiprobability: nonnegativity and Hudson's theoremTextbook
Motivation
Classical statistical mechanics describes a particle by a probability density on phase space; quantum mechanics replaces this by a wavefunction, and the uncertainty principle forbids any honest probability interpretation of simultaneous position and momentum. In 1932, Eugene Wigner introduced the transform that has become the standard way of placing quantum states on classical phase space anyway: a quasiprobability distribution W(x,p), defined by an explicit integral formula, whose marginals reproduce the Born position and momentum distributions of the wavefunction (Wigner 1932). Unlike a probability density, W generally takes negative values, and this negativity is the standard marker of genuinely quantum behavior — of interference — in quantum optics, quantum information, and the study of the quantum-to-classical transition.
The central question about the probabilistic character of W is: which quantum states have an everywhere nonnegative Wigner function? Hudson's theorem (1974) gives the complete answer in one dimension: only Gaussian wave packets (Hudson 1974). This mission formalizes the definition, the basic properties, and the positivity characterization of the Wigner function, following the source text, the Wikipedia article Wigner quasiprobability distribution (oldid 1376057304).
Timeline of the key results:
1932 — E. Wigner introduces the distribution to study quantum corrections to thermodynamic equilibrium (Physical Review 40, 749).
1946 — H. J. Groenewold computes the Wigner function of the m-th Fock (number) state, this mission's key worked example (Physica 12, 405).
1949 — J. E. Moyal recognizes W as the moment-generating functional of quantum mechanics in phase space (Proc. Camb. Phil. Soc. 45, 99).
1974 — R. L. Hudson proves that Gaussian pure states are the only pure states with nonnegative Wigner function in one dimension (Rep. Math. Phys. 6, 249).
1983 — F. Soto and P. Claverie extend the characterization to arbitrary dimension via the Segal–Bargmann transform (J. Math. Phys. 24, 97).
Setting
A wavefunction is a function ψ:R→C, and ℏ>0 denotes the reduced Planck constant. The Wigner function of ψ at the phase-space point (x,p)∈R2 is
W(x,p)=πℏ1∫−∞∞ψ(x+y)ψ(x−y)e2ipy/ℏdy,
a Lebesgue (Bochner) integral over y. The Lean development factors this into three definitions mirroring the formula: the integrand (Wigner.wignerIntegrand), the integral (Wigner.wignerIntegral), and the Wigner function itself (Wigner.wigner), defined as the real part of the integral divided by πℏ; that the discarded imaginary part vanishes is itself milestone 1. The Fock states of the harmonic oscillator enter through the physicists' Hermite polynomials Hm and the ordinary Laguerre polynomials Lm, defined by their standard three-term recurrences, and the normalized m-th Hermite function
um(x)=(2mm!)−1/2π−1/4Hm(x)e−x2/2.
Formalization targets
Goal — Hudson's theorem
∫R∣ψ∣2=1 and Wψ≥0 on R2⟹∃a,b,c∈C,Rea>0,ψ=e−ax2+bx+ca.e.
This is exactly the source's statement of Hudson's theorem; nothing is left unfixed. The mission is complete when the goal is proved.
Milestones
The milestone list is the source's property list, ordered as the attack path: (1) reality of the defining integral; (2) the position marginal ∫Wdp=∣ψ(x)∣2; (3) the total integral ∬W=∫∣ψ∣2; (4) Groenewold's closed formula for the Fock states; (5) a concrete negativity witness, the first excited Fock state at the origin; (6) the pointwise bound ∣W∣≤2/h; (7) the converse of Hudson's theorem, that Gaussian pure states have nonnegative Wigner function.
Significance
The result itself. Hudson's theorem draws the exact boundary between the classical and the quantum in phase space: Gaussian states — coherent and squeezed states — are precisely the pure states that can be described by an honest phase-space probability density. This is used in quantum optics as a nonclassicality criterion, in tomography and state-reconstruction theory, and in the study of the quantum-to-classical transition: negativity of W is shielded by the uncertainty principle (negative regions cannot extend beyond a few ℏ) and disappears in the classical limit, as the source emphasizes.
What formalizing it adds. The Wigner transform and this circle of ideas are absent from current Mathlib, so the mission builds the foundations itself: the integral transform and its basic identities (reality, marginals, normalization, boundedness), the Hermite/Laguerre recurrences and Groenewold's Fock-state formula, and finally Hudson's theorem with its converse. All of these are reusable well beyond the mission — for quantum optics, for the Wigner–Ville time–frequency distribution used in signal analysis, and for the wider phase-space formulation of quantum mechanics (Moyal brackets, star products). These are known results: this is formalization of known mathematics, not new mathematics, and no machine-checked proof of Hudson's theorem exists in Mathlib today.
Difficulty
The naive approach to Hudson's theorem is doomed from the start, and solvers should know it: since the Husimi Q function (a Gaussian smoothing of W) is positive for every quantum state, no smoothing or positivity-of-convolution argument can extract any information from W≥0. The known route (Soto–Claverie) is: W≥0 everywhere forces the Husimi function strictly positive everywhere; the Husimi function is the squared modulus of the Segal–Bargmann transform F of ψ, so F is a zero-free entire function; hence F=eg for some entire g, and square-integrability of F against a Gaussian measure forces g to have at most quadratic growth, hence to be a quadratic polynomial; inverting the Segal–Bargmann transform then exhibits ψ as a Gaussian. The hard Lean steps are the growth-to-polynomial (Liouville-type) step, the inversion of the transform, and, for the milestone properties, the Fubini and Fourier-inversion machinery. Mathlib contains the raw harmonic analysis (Fourier inversion for Schwartz functions) but none of the assembled phase-space layer.
Formalization scope
Integrals are Bochner integrals with respect to Lebesgue measure on R; statements carry the integrability or regularity hypotheses under which the source's displayed integrals exist.
ℏ is an explicit real parameter, and every statement assumes 0<ℏ (the standing convention of the source). The Fock-state section uses the source's dimensionless units, i.e. ℏ=1.
The Wigner function is defined as the real part of the defining integral divided by πℏ; milestone 1 proves the imaginary part vanishes, so this is the same function as the source's.
Pure states are encoded by the normalization ∫∣ψ∣2=1.
The conclusion of Hudson's theorem holds only up to modification of ψ on a Lebesgue-null set (W is insensitive to null-set changes of ψ), so the goal states almost-everywhere equality; this is the faithful reading of "the wavefunction must have the form".
The Fock states are normalized: the source's displayed um=π−1/4Hme−x2/2 omits the factor (2mm!)−1/2 that its Fock-state formula requires; the definition includes it, since Groenewold's formula is stated for the normalized number states ∣m⟩=(a†)m/m!∣0⟩.
There is no trivializing encoding: Hudson's hypothesis ranges over all normalized wavefunctions, and the conclusion is not weakened beyond the almost-everywhere reading.
Infrastructure contributed and reusable beyond this mission: hermiteP, laguerreL, fockState, wignerIntegrand, wignerIntegral, wigner. Welcome additional contributions: the momentum marginal, the state-overlap formula (Property 6), Galilei covariance (Property 4), and harmonic-oscillator time evolution, as further theorems in the same namespace.
J. E. Moyal, Quantum mechanics as a statistical theory, Mathematical Proceedings of the Cambridge Philosophical Society 45(1), 99–124, 1949. https://doi.org/10.1017/S0305004100000487
Ensemble spaces: monodecomposability and separatenessResearch Paper
Motivation
A physical law is a claim about what happens whenever a preparation is repeated, not about a single run. The objects of the law are therefore ensembles: the statistical outputs of a preparation procedure. Classical probability distributions and quantum density operators are two realizations of that idea, and they share a convex structure coming from statistical mixing. Gabriele Carcassi and Christine A. Aidala isolate that structure in the draft chapter Ensemble spaces (12 October 2026), as part of the Assumptions of Physics project (assumptionsofphysics.org).
The convex fragment already separates a classical behaviour from a non-classical one. In a classical ensemble space, an ensemble that is separate from two ensembles is separate from every mixture of them. In a quantum ensemble space it need not be: the equal mixture of two orthogonal pure states is not separate from a pure state in their span. The draft turns this distinction into a theorem that uses only mixing. Monodecomposability — every decomposable ensemble has no two decompositions in which one summand is separate from both summands of the other — holds if and only if mixtures preserve separateness (Proposition 1.35).
This mission formalizes that equivalence and the lemmas of §§1.2–1.3 that it depends on. Entropy, affine embedding, and the open problems of the same draft are later developments and are not assumed here.
Setting
An ensemble space is a nonempty topological space E that is T0 and second countable, together with a continuous mixing operation
(p,a,b)↦pa+pˉb,p∈[0,1],pˉ=1−p.
Mixing is the identity 1a+0b=a, idempotent (pa+pˉa=a), commutative (pa+pˉb=pˉb+pa), and associative in the following sense. If p1,p3∈[0,1), p1+p3≤1 and p2=1−p1−p3, then
In the formalization the operation is mix p a b, equal to pa+pˉb. Binary mixing records only the first coefficient.
A finite mixture∑i=1npiei, for pi∈[0,1] with ∑ipi=1, is the nested mixture (1.11) of the pairs with pi=0, in the given order. Reordering the pairs does not change the ensemble (Corollary 1.12).
An ensemble c is a component of a when a=pc+pˉd for some ensemble d and some p∈(0,1]. Two ensembles are separate, written a⋔b, when they have no common component. An extreme point has no component other than itself. An internal point admits every ensemble as a component. A boundary point is a point that is not internal.
A set A is bounded arounde when every open neighbourhood U of e admits some p∈[0,1) with pe+pˉA⊆U.
An ensemble is decomposable when it is a mixture pa+pˉb with p∈(0,1) and a=b; separately decomposable when the two summands may be taken separate; and multidecomposable when it admits two such decompositions
e=pa1+pˉa2=qb1+qˉb2
with a1⋔b1 and a1⋔b2. It is monodecomposable when it is not multidecomposable. The space is monodecomposable when every decomposable ensemble is. Mixtures preserve separateness when e⋔a and e⋔b imply e⋔(pa+pˉb) for every p∈[0,1].
Formalization targets
Proposition 1.35 — goal
For an ensemble space E,
E is monodecomposable⟺mixtures preserve separateness in E.
The two sides are exactly Definitions 1.33 and 1.28. No entropy, orthogonality, or finite-dimensionality hypothesis is added, and none is removed.
Corollary 1.12
For pi∈[0,1] with ∑ipi=1 and any permutation τ,
i∑piei=i∑pτ(i)eτ(i),
and the common value exists as an ensemble.
Proposition 1.17
A set A is bounded around e if and only if pne+pˉnan→e whenever pn→1 in [0,1] and an∈A.
Proposition 1.21
The set of internal points is convex: it is closed under mixing.
Corollary 1.25
Components and separateness satisfy the six properties listed in the draft: every ensemble is a component of itself; a component yields a common component, so the two ensembles are not separate; separateness is irreflexive and symmetric; distinct extreme points are separate; an internal point is not separate from any ensemble; separate ensembles are boundary points.
Proposition 1.27
If e is separate from pe1+pˉe2 for some p∈(0,1), then e is separate from λe1+λˉe2 for every λ∈[0,1].
Corollary 1.32
An ensemble is extreme if and only if it is not decomposable.
Significance
Proposition 1.35 is the convex form of the draft's classicality test. One direction says that if mixing can create a common component where none existed, then some ensemble has two genuinely different separate decompositions. The other says that if mixing never does this, then no decomposable ensemble is multidecomposable. The quantum Bloch ball is the draft's witness that the property can fail; the classical simplex is the witness that it can hold. Those two model statements (Proposition 1.34 and Propositions 1.29–1.30) are not part of this mission, but the interface they would plug into is.
The same interface is what the later sections of the draft extend: entropy is defined on a space that already mixes, and affine combinations are built from that mixing. A machine-checked Proposition 1.35 is a base those extensions can import without taking the entropy axiom as a hypothesis they do not use.
The argument in the draft is a proof, not an open problem. It had not been formalized against this 12 October 2026 text. An earlier formalization on this platform records Axioms 4.4, 4.7 and 4.55 of the 31 December 2025 book, in which entropy is part of the same structure. That package is a different source. Importing it here would add the entropy axiom to theorems proved in the draft before entropy is introduced, and would weaken them.
Difficulty
The equivalence is not a rephrasing of the definitions. One direction needs Proposition 1.27, whose proof places an auxiliary ensemble on a segment and rewrites coefficients so that a common component of e and one mixture becomes a common component of e and another. The arithmetic is sensitive to which endpoint is which, and to the restriction p∈(0,1) rather than p∈[0,1].
Corollary 1.12 is an induction on a bracketed expression, not on an unordered convex combination. Definition 1.10 deletes zero coefficients before bracketing. An encoding that feeds a zero coefficient to binary mixing denotes the same point only after the mixture axioms are applied; the draft's definition does not do that. The statement below follows the draft and deletes zeros first.
Proposition 1.17 is a topological fact about a continuous binary operation on a space that need not be a topological vector space. There is no scalar multiplication to rescale a neighbourhood, so the argument has to manufacture the shrink from mixing alone. Boundedness around e is not the same as metric boundedness, and the draft does not assume a metric.
Formalization scope
The carrier is a type E with a topological-space instance. An EnsembleSpace packages nonemptiness, the T0 and second-countability axioms, and the mixing operation. Coefficients of the operation are elements of the unit interval. In the associativity axiom, each real expression is shown to lie in [0,1] and is then used as that element; it is not replaced by a projection.
Finite mixtures are partial. Zero coefficients are removed, order preserved, and the rest is folded by binary mixing as in (1.11). The fold returns no value if every coefficient was zero or a tail sum vanishes. On inputs with nonnegative coefficients at most 1 that sum to 1, Corollary 1.12 asserts that a value exists. Real coefficients that arise while rescaling a tail are passed through the projection onto [0,1], which is the identity for data obeying those hypotheses. The empty index set cannot occur under the sum hypothesis: the sum of no coefficients is 0=1.
Separateness, components, extreme and internal points, decomposability and monodecomposability are propositions on this structure. A component uses a coefficient in (0,1]. A decomposition uses a coefficient in (0,1) and two distinct ensembles. Multidecomposability asks for two such decompositions, with one summand of the first separate from both summands of the second.
Entropy, orthogonality, affine combinations, vector-space embeddings, metrics, and the classical and quantum models are out of scope. In particular the goal must not be restated as “every Choquet simplex is a simplex”, and separateness must not be replaced by disjointness of supports. Adding the entropy axiom, or cancellativity, is a different theorem. Contributions that build the missing model statements on top of these definitions, without changing them, are the natural continuation; changes to the definitions are not.
Selected references
G. Carcassi and C. A. Aidala, Ensemble spaces, draft chapter, 12 October 2026. Axiom 1.4 (p. 12), Axiom 1.7 (p. 13), Definition 1.10 (p. 15), Corollary 1.12 (p. 15), Definition 1.16 and Proposition 1.17 (pp. 17–19), Definitions 1.19, 1.20, 1.24 and Corollary 1.25 (pp. 19–22), Proposition 1.27 (p. 23), Definitions 1.28 and 1.31 (pp. 24–25), Corollary 1.32 (p. 25), Definition 1.33 and Proposition 1.35 (p. 26). The draft states that it is generated from the project sources.
T. Fritz, Convex spaces I: Definition and examples, arXiv:0903.5522, 2009. arXiv:0903.5522. Cited by the draft for the algebraic convex-space axioms matched by Axiom 1.7.
General Entanglement Breaking ChannelsResearch Paper
Motivation
General Entanglement Breaking Channels establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.
Setting
Let d≥1 and m≥0 be integers. Fix density matrices R1,…,Rm∈Md(C) and positive semidefinite matrices F1,…,Fm∈Md(C), and define the complex-linear Holevo map on all matrices by
Φ(X)=k=1∑mRkTr(FkX).
For every positive finite reference dimension a and every density matrix Γ on Ca⊗Cd,
(ida⊗Φ)(Γ)∈cone{A⊗B:A and B are density matrices}.
Here the cone consists of finite sums with nonnegative real coefficients and includes zero. If, in addition, {Fk}k=1m is a POVM, meaning ∑kFk=Id, then Φ is completely positive and trace-preserving, and every such joint output is a separable density matrix: it is a finite convex combination of product density matrices.
This is precisely the measure-and-prepare implication of Theorem 4 and its printed channel specialization. It applies to entangled inputs without purity, orthogonality, or independence restrictions on the prepared states.
Formalization Note The general part uses the frozen separable-positive-cone predicate because unrestricted positive effects need not preserve trace. The channel part uses normalized separability. The identity always acts on the reference factor.
Target
§2, Theorem 4(A) ⇒ (B); trace-preserving continuation and proof, PDF p.5; eq.(1), PDF p.2
Let d≥1 and m≥0 be integers. Fix density matrices R1,…,Rm∈Md(C) and positive semidefinite matrices F1,…,Fm∈Md(C), and define the complex-linear Holevo map on all matrices by
Φ(X)=k=1∑mRkTr(FkX).
For every positive finite reference dimension a and every density matrix Γ on Ca⊗Cd,
(ida⊗Φ)(Γ)∈cone{A⊗B:A and B are density matrices}.
Here the cone consists of finite sums with nonnegative real coefficients and includes zero. If, in addition, {Fk}k=1m is a POVM, meaning ∑kFk=Id, then Φ is completely positive and trace-preserving, and every such joint output is a separable density matrix: it is a finite convex combination of product density matrices.
This is precisely the measure-and-prepare implication of Theorem 4 and its printed channel specialization. It applies to entangled inputs without purity, orthogonality, or independence restrictions on the prepared states.
Formalization Note The general part uses the frozen separable-positive-cone predicate because unrestricted positive effects need not preserve trace. The channel part uses normalized separability. The identity always acts on the reference factor.
Significance
These are known results from the cited paper. The current contribution consists of source-reviewed, compiler-checked theorem statements and mathematical definitions. Formal proofs remain open. Only the listed selected results are in scope; no whole-paper completeness is claimed.
Difficulty
A complete solution must establish every quantified conclusion under the exact stated hypotheses, including error, probability and resource conditions wherever present. The source assumptions and conventions are recorded in the attached statements and independent readbacks.
Formalization scope
Definitions preserve the existing reviewed Lean interfaces. Every target proof is currently sorry, so each target is Open. Printed-source corrections, where necessary, are labeled with the printed claim, the change and its reason.
Theorem 2: Holevo form iff entanglement breaking; trace-preserving normalization
Let d≥1 and let Φ:Md(C)→Md(C) be complex-linear. A finite Holevo representation with density matrices Rk and positive semidefinite effects Fk exists if and only if Φ breaks entanglement in the separable-positive-cone sense.
Φ(X)=k∑Tr(FkX)Rk⟺Φ is entanglement breaking.
For every supplied such representation, trace preservation is equivalent to {Fk} being a POVM. For every supplied representation (2) with unit output vectors ψk, it is equivalent to ∑k∣ϕk⟩⟨ϕk∣=I; the input vectors ϕk need not be unit or nonzero.
This identifies measure-and-prepare maps without presupposing complete positivity or trace preservation.
Theorem 3: convexity of EBT
For d≥1, let EBTd be the set of complex-linear entanglement-breaking, trace-preserving maps on Md(C). Then
EBTd is convex over R.
Thus aΦ+(1−a)Ψ is EBT for any two EBT maps and any a∈[0,1]. Convexity refers to maps on all operators and supports the paper's study of extreme channels.
Introduction: unitary conjugation does not break entanglement
Let d≥2 and let U be a unitary matrix on Cd. Then
X⟼UXU†is not EBT.
This records that unitary dynamics preserves some entanglement. The dimension restriction corrects the printed sentence: at d=1 unitary conjugation is EBT. The correction requires independent source moderation.
Correction to the printed source.
Printed: Conjugation with a unitary matrix is not EBT, without any stated dimension exception.
Corrected: Restrict the unitary-channel assertion to d at least two.
Reason: At d=1 every joint state is separable across the one-dimensional acted-on system; the identity channel is EBT.
Introduction: extremality of a point channel
Let d≥1 and let R be a density matrix on Cd. Define the replacement map ΦR(X)=Tr(X)R on all operators. Then
ΦR is extreme in CPT⟺R is pure⟺ΦR is extreme in EBT.
Here pure means R=∣ψ⟩⟨ψ∣ for a unit vector ψ. Both ambient convex sets are recorded, as supported by the point-channel paragraph and Theorem 5(A),(B).
Eq.(3): explicit Kraus representation and CQ/QC reductions
Let d≥1, let {Rk}k=1m be density matrices, and let Fk be positive semidefinite. For arbitrary orthonormal bases {ea} and {fb}, set Akab=Rk∣ea⟩⟨fb∣Fk. Then, on every operator X,
k,a,b∑AkabXAkab†=k∑Tr(FkX)Rk.
If the effects form a POVM the Kraus family is normalized. In the CQ case Fk=∣fk⟩⟨fk∣, the reduced family is Rk∣ea⟩⟨fk∣, and is normalized. In the QC case Rk=∣ek⟩⟨ek∣, it is ∣ek⟩⟨fb∣Fk, normalized when F is a POVM. For pure-output CQ maps it further reduces to ∣ψk⟩⟨ek∣, with unit ψk.
These are explicit operator-sum witnesses; square roots are the positive matrix square roots.
Theorem 4(A)--(F), with trace-preserving specialization
Let d≥1 and let Φ:Md(C)→Md(C) be complex-linear. Write β=d−1/2∑j∣j,j⟩. The following six conditions are equivalent:
A finite Holevo form with density outputs and positive semidefinite effects exists.
Φ breaks entanglement in the separable positive cone.
Its normalized Choi operator (id⊗Φ)(∣β⟩⟨β∣) is in that cone.
It has a finite operator-sum representation with every Kraus operator of rank exactly one.
Υ∘Φ is completely positive for every positivity-preserving complex-linear endomap Υ of Md.
Φ∘Υ is completely positive for every such Υ.
A⟺B⟺C⟺D⟺E⟺F.
If Φ preserves trace, the corresponding six-way equivalence holds with a POVM in A, EBT in B, normalized separable density in C, ∑kAk†Ak=I in D, and trace-preserving positivity tests in E,F. Empty general representations are allowed for the zero map. This supplies all the theorem's characterizations, including its continuation on page 5.
Theorem 5(A): extreme CQ implies extreme EBT
Let d≥1 and let Φ be an extreme CQ map in the source's terminology: for an orthonormal basis ek and unit vectors ψk,
Φ(X)=k∑∣ψk⟩⟨ψk∣⟨ek∣X∣ek⟩.
Then Φ is an extreme point of the convex set of EBT maps. The vectors ψk may coincide or be dependent. The source-defined class is therefore distinguished from convex extremality itself.
Theorem 5(B): CPT extremality of an extreme CQ map
Let d≥1, let ek be an orthonormal basis of Cd, and let ψk be arbitrary unit vectors. For the supplied representation Φ(X)=∑k∣ψk⟩⟨ψk∣⟨ek∣X∣ek⟩,
Φ∈ext(CPTd)⟺⟨ψj∣ψk⟩=0for all j,k.
No orthogonality or independence assumption on outputs is imposed. This characterizes which pure-output CQ maps remain extreme in the larger channel set.
Theorem 5(C): EBT and CPT-extreme implies extreme CQ
Let d≥1. If Φ is EBT and is an extreme point of the set of CPT maps, then
Φ is a pure-output CQ map.
Explicitly, an orthonormal input basis and unit output vectors realizing Eq.(8) exist. Neither Choi rank d nor a d-term Kraus representation is assumed: those are proof conclusions. This identifies the overlap of EBT with the extreme points of CPT.
Theorem 5(D): qubit characterization and higher-dimensional counterexamples
The two dimension regimes for extreme EBT maps are:
ext(EBT2)={pure-output CQ maps on M2},
whereas, for every integer d≥3, there exists an extreme EBT endomap of Md that is not CQ.
The qubit proof is attributed by the paper on page 8 to Ruskai [18], quant-ph/0302032. The paper supplies the higher-dimensional counterexamples, including the qutrit example. The result separates EBT extremality from pure-output CQ structure in higher dimensions.
Section 3 Example: a four-dimensional extreme EBT QC map that is not CQ
Let g0,…,g3 and e0,…,e3 be orthonormal bases of C4. Put g±=(g0±3g1)/2 and set
These effects form a POVM, and the computed map Φ(X)=∑k=03Tr(FkX)∣ek⟩⟨ek∣ is an extreme EBT map which is QC and is not CQ.
The third displayed effect corrects the source's repeated g+ to g−, as forced by the word trine, normalization, and the proof. Independent source moderation is required. This is a concrete witness rather than a free existential channel.
Correction to the printed source.
Printed: The third effect is printed as (2/3)|g_+><g_+|, duplicating the second.
Corrected: Replace only that third effect by (2/3)|g_-><g_-|.
Reason: The narrative calls this a trine POVM and its proof uses that POVM. The changed effect cancels the off-diagonal entries; the printed effects do not sum to I.
Let d≥1 and let E1,…,Em be a von Neumann measurement: mutually orthogonal Hermitian projections summing to I. If some Ek has rank greater than one, then
Φ(X)=k∑EkXEkis not EBT.
The actual computed pinching map is used. A rank-two block can retain entanglement, distinguishing such block projections from rank-one dephasing.
Theorem 6: fewer than d Kraus operators precludes EBT
Let d≥1 and let A1,…,Am satisfy ∑kAk†Ak=I. If m<d, then the channel with this actual Kraus list satisfies
Φ(X)=k=1∑mAkXAk†is not EBT.
The empty normalized list is impossible for d>0. The result gives a lower bound on the size of every Kraus representation of an EBT map; its cited ingredients are [11], or [8] with [2].
Lemma 7: Choi rank d makes PPT equivalent to EBT
Let d≥1, let Φ be CPT, and let JΦ=(id⊗Φ)(∣β⟩⟨β∣) for the unit maximally entangled vector β=d−1/2∑j∣j,j⟩. If rankJΦ=d, then
Φ is EBT⟺T∘Φ is completely positive,
where T is matrix transpose, a complex-linear map. The exact rank and TP hypotheses are retained; the low-rank separability ingredient is attributed to [10].
Lemma 8: product decomposition length at most the common global/marginal rank
Let ρ be a separable density matrix on Ca⊗Cb, with a,b≥1. Suppose both ρ and its first marginal ρA=TrBρ have rank r. Then there exist m≤r, nonnegative weights pk summing to one, and unit vectors uk∈Ca, vk∈Cb such that
ρ=k=1∑mpk∣uk⟩⟨uk∣⊗∣vk⟩⟨vk∣.
The rank r is independent of the ambient dimensions. First proved in [10], the lemma receives a new proof here and bounds the length of separable decompositions under a matching marginal-rank assumption.
Section 3 Counterexample, Eq.(19): qutrit extreme EBT channel not CQ
Fix an orthonormal basis e0,e1,e2 of C3. Let v0=(e0+e1+e2)/3, v1=(e0−e1−e2)/3, v2=(−e0+e1−e2)/3, and v3=(−e0−e1+e2)/3. The computed channel
Φ(X)=43i=0∑3Tr(∣vi⟩⟨vi∣X)∣vi⟩⟨vi∣
is extreme in EBT, is not CQ, and is not extreme in CPT. Its distinct rays have overlap −1/3, and the only Hermitian projections commuting with all four pure densities are 0,I, ruling out an orthogonal block split.
Its positive rank-one Holevo form is essentially unique: in any finite representation with strictly positive weights ak, unit output vectors yk, and unit input vectors zk, each pair of pure densities equals (∣vi⟩⟨vi∣,∣vi⟩⟨vi∣) for some i. The sum of weights belonging to each ray is 3/4. This permits splitting and merging weights and arbitrary vector phases; it makes no assertion about arbitrary mixed-output or zero-effect presentations.
For each i, the plane reflection U_i=I-2|v_i⟩⟨v_i| is unitary, and on every operator X the final page-12 construction is explicitly realized by Phi(X)=(1/4)X+(3/16) sum_(i=0)^3 U_i X U_i†. The five nonnegative coefficients sum to one.
Section 4, Eq.(23): density coordinates and purity bounds
Let d≥1 and let G0,…,Gd2−1 be a real Hilbert–Schmidt orthonormal basis of Hermitian matrices, with G0=I/d and the remaining matrices traceless. For a density matrix ρ, put wj=Tr(ρGj), which is real. Then
The printed w0=d is corrected to its reciprocal, as forced by trace normalization. This coordinate description is used in the map factorization; independent source moderation of the correction remains required.
Correction to the printed source.
Printed: The source prints w_0=d^(1/2) with G_0=d^(-1/2)I and trace rho=1.
Corrected: State w_0=d^(-1/2); all other displayed coefficient formulas are retained.
Reason: Directly Tr(rho G_0)=Tr(rho)/sqrt(d)=1/sqrt(d); rho=I/2 is a concrete counterexample to the printed exponent.
Section 4: Holevo coordinate factorization and trace-preserving row
In the preceding Hermitian basis, let Rk be density matrices and Fk positive semidefinite effects, k=1,…,m. Define Wjk=Tr(RkGj), Unk=Tr(FkGn) and Tjn=Tr(GjΦ(Gn)) for the computed Holevo map. Then
Tjn=k∑WjkUnk,T=WUT.
Moreover, F is a POVM if and only if the first row of T is (1,0,…,0). Both factors have d2 rows and m columns. The product corrects the printed WTU according to those dimensions and the unchanged entrywise formula. Independent moderation of this correction is required.
Correction to the printed source.
Printed: The source prints T=W^T U although W and U are d^2 by N.
Corrected: Use T=W U^T and retain the source's unchanged entrywise sum t_jn=sum_k w_jk u_nk.
Reason: W^T U has shape N by N, while W U^T has the required d^2 by d^2 shape and exactly the printed entries.
Section 4: rank and affine image dimension of CQ/QC
Let d≥1, let G be the Hermitian coordinate basis above, and let Φ be CQ or QC. Let T be its full d2-by-d2 coordinate matrix and Dd the density matrices. Then
rankT≤d,dimRaff(Φ(Dd))≤d−1.
The second dimension is affine in the trace-one hyperplane, following the separation of the identity coordinate on page 12. A linear-dimension interpretation would fail at d=1. This bounds the geometry of the output-state set.
Correction to the printed source.
Printed: The source calls the density image a subspace of dimension at most d-1.
Corrected: Interpret this as an affine span over the real numbers within the trace-one hyperplane.
Reason: Equation (23) fixes the identity coordinate; the convex hull of d density outputs has affine dimension at most d-1. Linear dimension zero already fails for the d=1 state.
These additional statements have current no-edit source review. Their formal proofs remain open; deferred results are excluded.
Let Φ:M2(C)→M2(C) be complex-linear, completely positive and trace preserving. Let ∣β⟩=(∣00⟩+∣11⟩)/2 and ΓΦ=(id⊗Φ)(∣β⟩⟨β∣). Then
Φ is entanglement breaking⟺ΓΦ≤21I4.
The inequality is the positive-semidefinite operator order. This provides an operator test on the normalized Choi state.
Theorem 3
Let t,λ∈R3, and let Φt,λ be the trace-preserving canonical Bloch map v↦t+diag(λ)v. If it is entanglement breaking, then
j=1∑3∣λj∣≤1.
There is no unitality assumption. This is a necessary condition for the general translated channel.
Theorem 4
Let Φ be a completely positive trace-preserving qubit map with Φ(I)=I. Suppose independent unitary changes of input and output bases put it in canonical form with parameters t,λ∈R3. Then
Φ is entanglement breaking⟺j=1∑3∣λj∣≤1.
This makes the necessary condition sufficient in the unital case.
Amplitude damping counterexample
For 0≤α≤1, let Φα have translation (0,0,1−α2) and diagonal Bloch parameters (α,α,α2). These maps are completely positive and trace preserving, and
Φα is entanglement breaking⟺α=0.
Moreover, for every η>0 there is α∈(0,1] with 2α+α2<η and Φα not entanglement breaking. Thus small diagonal-parameter sum does not suffice for translated channels.
Linear channels and equation 9
For t∈R3 and a∈R, let Φ=Φt,(0,0,a). Then
Φ is CPT⟺t12+t22+(∣t3∣+∣a∣)2≤1.
Whenever this holds, Φ is CQ and equals X↦∑b=01Tr(∣b⟩⟨b∣X)Rb, where R0=(I+(t+ae3)⋅σ)/2 and R1=(I+(t−ae3)⋅σ)/2. This includes a=0, when the image is a point.
QC channels are unitarily equivalent to CQ channels
Let Φ be a QC qubit channel: it measures a POVM and prepares one of two orthogonal pure states. There are qubit unitaries U,V and a CQ map Ψ such that
Φ=AdV∘Ψ∘AdU,AdU(X)=UXU†.
A CQ map measures rank-one orthogonal input projectors and prepares density matrices. The assertion relates these two channel subclasses without identifying their definitions.
Extreme POVM need not give an extreme channel
Set w1=(1,0,0), w2=(−1/2,0,3/2), w3=(−1/2,0,−3/2), and Ek=(I+wk⋅σ)/3. Set Rk=(I+σk)/2, with σ1=X,σ2=Y,σ3=Z, and define
Φ(X)=k=1∑3Tr(EkX)Rk.
The effects form an extreme three-outcome POVM, each Rk is a density matrix, and Φ is EBT, neither CQ nor a point channel, and not extreme in the EBT set. Thus extreme measurement data need not produce an extreme channel.
Proposition 7
Let Φ=Φt,λ be a CPT qubit map in the fixed canonical basis, and let T(X)=XT. Then T∘Φ∘T is completely positive, and changing any individual translation coordinate tj to −tj preserves complete positivity. In addition,
CP(Φ∘T)⟺[∀j,CP(Φt,λ[j↦−λj])]⟺CP(T∘Φ).
Here CP denotes complete positivity. These are all three numbered assertions, together with the any-coordinate translation invariance explained immediately before the proposition.
Planar channels are entanglement breaking
Let Φt,λ be a CPT qubit map in canonical form. Then
(∃j∈{1,2,3}:λj=0)⟹Φt,λ is entanglement breaking.
The planar regime includes degenerate lines and points. This is a sufficient condition only.
Pure point channels are extreme
Let t∈R3 with ∥t∥2≤1, and set R=(I+t⋅σ)/2. The canonical point map is CPT and CQ, R is a density matrix, and on every operator X it satisfies
Φt,0(X)=Tr(X)R.
If ∥t∥2=1, there is a unit vector ψ with R=∣ψ⟩⟨ψ∣, and the map is extreme in both the CPT and EBT sets. This identifies the pure-output endpoint of the point-channel family.
Truly planar channels do not touch the Bloch sphere
Let Φt,λ be a CPT canonical qubit map. If exactly one coordinate of λ is zero, then
∥t+diag(λ)v∥2<1(∥v∥2≤1).
Also, when λ3=0, (∣λ1∣+∣λ2∣)2+∥t∥22≤1. If both λ1,λ2 are nonzero and equality holds, then t1=t2=0. Thus a truly planar image stays strictly inside the Bloch sphere.
Theorem 8
In a fixed diagonal basis, let U={λ∈R3:Φ0,λ is CPT and EBT}, and V={±e1,±e2,±e3}. Then
U=convR(V),Ext(U)=V.
The theorem determines both the entire parameter octahedron and exactly its six extreme points.
Unital EBT channels are the convex hull of unital CQ maps
In the real vector space of complex-linear qubit maps, let Eu be the unital trace-preserving entanglement-breaking maps, and Cu the unital CQ maps. Then
Eu=convR(Cu).
The channel sets allow arbitrary input and output bases. This is a statement in map space, not only in one diagonal parameter slice.
Theorem 9
Fix any translation t∈R3, and define Λt={λ:Φt,λ is completely positive}. Then
Λt∩(−Λt)={λ:Φt,λ is EBT}.
Inversion negates λ and leaves t fixed. Infeasible translations are permitted; both sides can be empty.
Theorem 10
Let E be the trace-preserving entanglement-breaking complex-linear qubit maps, and C the CQ maps. Then
Ext(E)⊆C,E=convR(C).
These are both conclusions of the main theorem. It does not assert that every CQ map is extreme. The proof gap concerning intersecting planes on p.15 is recorded separately, without becoming a theorem hypothesis.
Remark a planar same-basis convex decomposition
Suppose Φt,λ is EBT and λj=0 for a chosen coordinate j. It belongs to the real convex hull of canonical CQ maps Φt′,λ′ satisfying λj′=0 and having at most one nonzero coordinate of λ′. Moreover, if Ξt3,0 denotes the CPT parameter slice fixing only t3 and λ3=0, then
Ξt3,0=convR{(t,λ)∈Ξt3,0:Φt,λ is CQ}.
This preserves the canonical coordinate plane, including point-channel endpoints; the other translation coordinates may vary.
Equation 29 axial-translation EBT criterion
For a CPT canonical qubit map with t=(0,0,t3),
Φt,λ is EBT⟺(∣λ1∣+∣λ2∣)2≤(1−∣λ3∣)2−t32.
For fixed t3,l3 with ∣l3∣≤1 and q=(1−∣l3∣)2−t32≥0, its EBT slice is exactly {(v1,v2):∣v1∣+∣v2∣≤q}. This includes the filled square and its collapsed endpoints; a negative radicand is not totalized into an extra radius-zero slice.
Remark c parallelogram of same-basis decompositions
Fix t∈R3 and l3∈R. Let P consist of canonical EBT maps with these fixed parameters and either λ1=0 or λ2=0. Let Cdiag be all CQ maps canonical in the same basis. Then
convR(P)⊆convR(Cdiag).
This gives the same-basis decomposition on the illustrated parallelogram. It neither covers the entire slice nor requires CQ summands to retain l3.
Remark d equal singular magnitudes
Let Φ=Φt,λ be EBT, with ∣λj∣=a>0 for all three coordinates. There are input/output unitaries U,V and s∈{a,−a} such that, writing B(Ψ)=AdV∘Ψ∘AdU,
B(Φ)=Φ(∥t∥2,0,0),(s,s,s)∈convR(A).
Here A consists of canonical CQ maps for which tj=λj=0 for some j∈{2,3}. Also Φ∈convR(B−1(A)). Thus summands are canonical in the rotated basis and need not be canonical in the original one.
Formalization scope
Only these reviewed original-paper statements are in scope. Definitions have reviewed bodies; target proofs remain open (sorry). Reviewed deferrals are excluded. No theorem proof or whole-paper formal proof is claimed.
Separability Criterion for Density MatricesResearch Paper
Motivation
Separability Criterion for Density Matrices establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.
Setting
Let I and J index orthonormal bases of two nonempty finite-dimensional complex Hilbert spaces, with no requirement that their dimensions agree. Let ρ be a density matrix on their tensor product, so ρ is positive semidefinite and Trρ=1. Suppose it is separable: for some finite ensemble of density matrices Aa on the first subsystem and Ba on the second, and real weights wa≥0 summing to one, ρ=∑awaAa⊗Ba. Define its first-subsystem partial transpose by σ(i,j),(i′,j′)=ρ(i′,j),(i,j′). Then
σ=ρTI⪰0.
Equivalently, all eigenvalues of the Hermitian matrix σ are nonnegative. This is a necessary condition for separability, with no assertion of a converse.
Formalization Note The unspecified ensemble in Eq. (1) is represented by an arbitrary finite ensemble in the paper's finite-dimensional setting. Allowing zero weights is equivalent to the printed positive-weight convention after deleting zero-weight terms; normalization excludes an empty ensemble.
Target
Unnumbered conclusion following Eq. (6); definitions in Eqs. (1)–(3), PDF p. 2
Let I and J index orthonormal bases of two nonempty finite-dimensional complex Hilbert spaces, with no requirement that their dimensions agree. Let ρ be a density matrix on their tensor product, so ρ is positive semidefinite and Trρ=1. Suppose it is separable: for some finite ensemble of density matrices Aa on the first subsystem and Ba on the second, and real weights wa≥0 summing to one, ρ=∑awaAa⊗Ba. Define its first-subsystem partial transpose by σ(i,j),(i′,j′)=ρ(i′,j),(i,j′). Then
σ=ρTI⪰0.
Equivalently, all eigenvalues of the Hermitian matrix σ are nonnegative. This is a necessary condition for separability, with no assertion of a converse.
Formalization Note The unspecified ensemble in Eq. (1) is represented by an arbitrary finite ensemble in the paper's finite-dimensional setting. Allowing zero weights is equivalent to the printed positive-weight convention after deleting zero-weight terms; normalization excludes an empty ensemble.
Significance
These are known results from the cited paper. The current contribution consists of source-reviewed, compiler-checked theorem statements and mathematical definitions. Formal proofs remain open. Only the listed selected results are in scope; no whole-paper completeness is claimed.
Difficulty
A complete solution must establish every quantified conclusion under the exact stated hypotheses, including error, probability and resource conditions wherever present. The source assumptions and conventions are recorded in the attached statements and independent readbacks.
Formalization scope
Definitions preserve the existing reviewed Lean interfaces. Every target proof is currently sorry, so each target is Open. Printed-source corrections, where necessary, are labeled with the printed claim, the change and its reason.
Let ρ be a density matrix on two nonempty finite subsystem spaces with basis sets I and J. Define σmμ,nν=ρnμ,mν, transposing only the first subsystem. Then
σ†=σ.
The assertion holds for arbitrary subsystem dimensions and requires no separable decomposition. It makes the eigenvalue test a test on a Hermitian matrix.
Prose spanning pp.2–3 and Eq. (4)
Let ρ be a density matrix on CI⊗CJ, with I,J nonempty finite basis sets. Let U and V be arbitrary complex unitaries on the respective subsystem spaces, and set ρ=(U⊗V)ρ(U⊗V)†. Writing TI for transposition of the first subsystem only, one has
det(t1−ρTI)=det(t1−ρTI)
as polynomials in t. Hence the two partial transposes have the same eigenvalues with algebraic multiplicities. This expresses the criterion's independence of local basis choices.
Eqs. (7)–(8) and following calculation
For two qubits, let ∣s⟩=(∣01⟩−∣10⟩)/2, S=∣s⟩⟨s∣, and ρx=xS+(1−x)14/4, where 0≤x≤1. Let σx=ρxTI. Its characteristic polynomial is
det(t14−σx)=(t−41−3x)(t−41+x)3.
In particular, if x<1/3, then σx is positive definite and satisfies the necessary separability criterion. The calculation identifies the effect of white noise, whose random fraction includes all four Bell components equally.
Eqs. (9)–(13)
Let a,b∈C satisfy ∣a∣2+∣b∣2=1, and let 0≤x≤1. Set ∣ψ⟩=a∣01⟩+b∣10⟩ and ρ=x∣ψ⟩⟨ψ∣+(1−x)(∣00⟩⟨00∣+∣11⟩⟨11∣)/2. If x>(1+2∣ab∣)−1, then, for σ=ρTI,
detσ<0,λmin(σ)<0.
The negative eigenvalue obstructs separability. Both the determinant and spectral conclusions are retained.
Eq. (15) and following paragraph
Let S be the two-qubit singlet density matrix and let 0<x≤1. Define ρx=xS+(1−x)∣00⟩⟨00∣ and σx=ρxTI. Then
λmin(σx)<0,ρxis inseparable.
Thus even an arbitrarily small positive singlet fraction in this family produces entanglement. The zero-fraction endpoint is excluded by the source's positivity condition.
Final paragraph
Let ρ be a density matrix on two nonempty finite subsystem spaces I and J, and let k≥1. Group the k copies so that the first observer holds all I registers and the second holds all J registers. In these coordinates let ρ[k] denote the product with entries ∏t=1kρitjt,it′jt′, and put σ=ρTI. Then
The last implication holds independently of separability. This is the finite-copy stability that prevents strengthening this algebraic test by taking identical copies.
These additional statements have current no-edit source review. Their formal proofs remain open; deferred results are excluded.
Let {pj,ρ^j}j∈O be an ensemble of density matrices ρ^j on a finite-dimensional Hilbert space, indexed by a finite label set O, with probabilities pj≥0, ∑jpj=1. Write ρj:=pjρ^j and ρout:=∑jρj, and let ρout−1/2 be the generalized inverse square root (non-zero eigenvalues inverted, zero eigenvalues kept). The pretty good measurement (PGM) has effects Xj=ρout−1/2ρjρout−1/2. For density matrices σ1,σ2 let FBU(σ1,σ2):=trσ11/2σ2σ11/2 be the Bures–Uhlmann fidelity.
Then the success probability of the PGM, and therefore the optimal success probability Fcl over all measurements {Mj}j∈O (POVMs with one outcome per label), satisfy
the sums running over ordered pairs of distinct labels.
This bound expresses the error of state discrimination through pairwise overlaps only; it is the tool behind the polynomial query complexity of the hidden subgroup problem (Childs, Theorem 10.1).
Formalization Note The paper writes the left side of (39) as Fcl2 and opens (38) with Fcl2≥Fcl(ρ,RA,ρA), which is reversed relative to its own Corollary 4 and false in general (two equiprobable pure states with overlap 0.9). Its proof establishes the bound for the PGM success probability Fcl(ρ,RA,ρA) and then for the optimal Fcl≥Fcl(ρ,RA,ρA); that is what is stated. The reversal map of Eq. (35)–(36) is not formalized: for A of form (35), classical fidelities of reversal are exactly measurement success probabilities on the ensemble.
Target
Theorem 5
Let {pj,ρ^j}j∈O be an ensemble of density matrices ρ^j on a finite-dimensional Hilbert space, indexed by a finite label set O, with probabilities pj≥0, ∑jpj=1. Write ρj:=pjρ^j and ρout:=∑jρj, and let ρout−1/2 be the generalized inverse square root (non-zero eigenvalues inverted, zero eigenvalues kept). The pretty good measurement (PGM) has effects Xj=ρout−1/2ρjρout−1/2. For density matrices σ1,σ2 let FBU(σ1,σ2):=trσ11/2σ2σ11/2 be the Bures–Uhlmann fidelity.
Then the success probability of the PGM, and therefore the optimal success probability Fcl over all measurements {Mj}j∈O (POVMs with one outcome per label), satisfy
the sums running over ordered pairs of distinct labels.
This bound expresses the error of state discrimination through pairwise overlaps only; it is the tool behind the polynomial query complexity of the hidden subgroup problem (Childs, Theorem 10.1).
Formalization Note The paper writes the left side of (39) as Fcl2 and opens (38) with Fcl2≥Fcl(ρ,RA,ρA), which is reversed relative to its own Corollary 4 and false in general (two equiprobable pure states with overlap 0.9). Its proof establishes the bound for the PGM success probability Fcl(ρ,RA,ρA) and then for the optimal Fcl≥Fcl(ρ,RA,ρA); that is what is stated. The reversal map of Eq. (35)–(36) is not formalized: for A of form (35), classical fidelities of reversal are exactly measurement success probabilities on the ensemble.
Significance
These are known results from the cited paper. The current contribution consists of source-reviewed, compiler-checked theorem statements and mathematical definitions. Formal proofs remain open. Only the listed selected results are in scope; no whole-paper completeness is claimed.
Difficulty
A complete solution must establish every quantified conclusion under the exact stated hypotheses, including error, probability and resource conditions wherever present. The source assumptions and conventions are recorded in the attached statements and independent readbacks.
Formalization scope
Definitions preserve the existing reviewed Lean interfaces. Every target proof is currently sorry, so each target is Open. Printed-source corrections, where necessary, are labeled with the printed claim, the change and its reason.
This is the regret bound of online mirror descent with a constant step size.
Let E be a finite-dimensional real vector space with an arbitrary norm ∥⋅∥, and let ∥g∥∗=sup∥v∥=1g(v) be the dual norm of a linear functional g. Let K⊆E be a convex body (closed, convex, with nonempty interior). Let f1,…,fT:E→R be differentiable functions that are convex over K. Let h:E→R be differentiable and αh-strongly convex with respect to ∥⋅∥ for some αh>0, i.e. h(y)≥h(x)+⟨∇h(x),y−x⟩+2αh∥y−x∥2 for all x,y, and let Dh(y∥x)=h(y)−h(x)−⟨∇h(x),y−x⟩ be its Bregman divergence. Fix a step size η>0 and a starting point x0∈E. Mirror descent produces x1=ΠKh(x0) and, for 1≤t<T, xt+1=ΠKh(xt+1′) where ∇h(xt+1′)=∇h(xt)−η∇ft(xt); here ΠKh(x′)∈K minimizes Dh(⋅∥x′) over K. Then for every such run and every x∗∈K,
With the Euclidean norm and h=21∥x∥22 it recovers the regret bound of projected online gradient descent; with negative entropy on the simplex it gives the Hedge bound.
Formalization Note The source prints the second sum as ∑t=1n; n is a typo for T and is corrected. Gradients are Fréchet derivatives, whose operator norm is the dual norm. The first iterate is the Bregman projection of x0 (equal to x0 when x0∈K).
Target
Theorem 4.2
This is the regret bound of online mirror descent with a constant step size.
Let E be a finite-dimensional real vector space with an arbitrary norm ∥⋅∥, and let ∥g∥∗=sup∥v∥=1g(v) be the dual norm of a linear functional g. Let K⊆E be a convex body (closed, convex, with nonempty interior). Let f1,…,fT:E→R be differentiable functions that are convex over K. Let h:E→R be differentiable and αh-strongly convex with respect to ∥⋅∥ for some αh>0, i.e. h(y)≥h(x)+⟨∇h(x),y−x⟩+2αh∥y−x∥2 for all x,y, and let Dh(y∥x)=h(y)−h(x)−⟨∇h(x),y−x⟩ be its Bregman divergence. Fix a step size η>0 and a starting point x0∈E. Mirror descent produces x1=ΠKh(x0) and, for 1≤t<T, xt+1=ΠKh(xt+1′) where ∇h(xt+1′)=∇h(xt)−η∇ft(xt); here ΠKh(x′)∈K minimizes Dh(⋅∥x′) over K. Then for every such run and every x∗∈K,
With the Euclidean norm and h=21∥x∥22 it recovers the regret bound of projected online gradient descent; with negative entropy on the simplex it gives the Hedge bound.
Formalization Note The source prints the second sum as ∑t=1n; n is a typo for T and is corrected. Gradients are Fréchet derivatives, whose operator norm is the dual norm. The first iterate is the Bregman projection of x0 (equal to x0 when x0∈K).
Significance
These are known results from the cited paper. The current contribution consists of source-reviewed, compiler-checked theorem statements and mathematical definitions. Formal proofs remain open. Only the listed selected results are in scope; no whole-paper completeness is claimed.
Difficulty
A complete solution must establish every quantified conclusion under the exact stated hypotheses, including error, probability and resource conditions wherever present. The source assumptions and conventions are recorded in the attached statements and independent readbacks.
Formalization scope
Definitions preserve the existing reviewed Lean interfaces. Every target proof is currently sorry, so each target is Open. Printed-source corrections, where necessary, are labeled with the printed claim, the change and its reason.
This is the overlap identity for Fourier phase states (Brassard, Høyer, Mosca, Tapp, Lemma 10), which yields the outcome distribution of Fourier-transform phase estimation.
Let M>0 be an integer. For a real number 0≤ω<1, the phase state on the M-dimensional register with orthonormal basis ∣0⟩,…,∣M−1⟩ is
∣SM(ω)⟩=M1y=0∑M−1e2πiωy∣y⟩.
For reals ω0,ω1, let d(ω0,ω1)=minz∈Z∣z+ω1−ω0∣ be the distance on the circle R/Z. Let 0≤ω0<1, 0≤ω1<1, and Δ=d(ω0,ω1). Then:
if Δ=0, then ∣⟨SM(ω0)∣SM(ω1)⟩∣2=1;
if Δ=0, then
∣⟨SM(ω0)∣SM(ω1)⟩∣2=M2sin2(Δπ)sin2(MΔπ).
The inner product is conjugate-linear in its first argument. Taking ω0=x/M gives the probability of outcome x when FM−1∣SM(ω1)⟩ is measured, which is the paper's Theorem 11 and the lecture notes' Proposition 3.11.
Formalization Note The phase state is the shared definition bhmtPhaseState M ω on EuclideanSpace ℂ (Fin M), and d is circDist ω0 ω1 = |(ω0 − ω1) − round(ω0 − ω1)|, which equals the minimum in Definition 9.
Target
Lemma 10
This is the overlap identity for Fourier phase states (Brassard, Høyer, Mosca, Tapp, Lemma 10), which yields the outcome distribution of Fourier-transform phase estimation.
Let M>0 be an integer. For a real number 0≤ω<1, the phase state on the M-dimensional register with orthonormal basis ∣0⟩,…,∣M−1⟩ is
∣SM(ω)⟩=M1y=0∑M−1e2πiωy∣y⟩.
For reals ω0,ω1, let d(ω0,ω1)=minz∈Z∣z+ω1−ω0∣ be the distance on the circle R/Z. Let 0≤ω0<1, 0≤ω1<1, and Δ=d(ω0,ω1). Then:
if Δ=0, then ∣⟨SM(ω0)∣SM(ω1)⟩∣2=1;
if Δ=0, then
∣⟨SM(ω0)∣SM(ω1)⟩∣2=M2sin2(Δπ)sin2(MΔπ).
The inner product is conjugate-linear in its first argument. Taking ω0=x/M gives the probability of outcome x when FM−1∣SM(ω1)⟩ is measured, which is the paper's Theorem 11 and the lecture notes' Proposition 3.11.
Formalization Note The phase state is the shared definition bhmtPhaseState M ω on EuclideanSpace ℂ (Fin M), and d is circDist ω0 ω1 = |(ω0 − ω1) − round(ω0 − ω1)|, which equals the minimum in Definition 9.
Significance
These are known results from the cited paper. The current contribution consists of source-reviewed, compiler-checked theorem statements and mathematical definitions. Formal proofs remain open. Only the listed selected results are in scope; no whole-paper completeness is claimed.
Difficulty
A complete solution must establish every quantified conclusion under the exact stated hypotheses, including error, probability and resource conditions wherever present. The source assumptions and conventions are recorded in the attached statements and independent readbacks.
Formalization scope
Definitions preserve the existing reviewed Lean interfaces. Every target proof is currently sorry, so each target is Open. Printed-source corrections, where necessary, are labeled with the printed claim, the change and its reason.
Evolution of Shares in a Proof-of-Stake Cryptocurrency: Under Coin Rewards R_t = ρN_{t−1}^γ, Limiting Investor Shares Concentrate at the Initial Share as N → ∞ if and only if γ < 1Research Paper
Motivation
In a Proof-of-Stake (PoS) cryptocurrency, new coins are not mined with computing power: before each date the protocol picks one coin holder at random, with probability equal to the fraction of coins she holds, and pays her a reward of new coins. A common claim in the cryptocurrency press is that this makes the rich richer: larger holders are selected more often, so their holdings should grow faster. Roşu and Saleh (Management Science 67(2), 2021) test this claim in a model that is, for a buy-and-hold investor, a generalized Pólya urn whose number of added balls Rt varies with time.
Their first result (Proposition 1) is that an investor's share is a martingale with an almost-sure limit whose mean is the initial share, which the paper itself calls standard for Pólya urns. The sharper question is whether shares are stable in the strict sense: does the limiting share concentrate at the initial share when the economy starts with many coins? The answer depends on how fast the reward grows with the coin supply, and Proposition 4 locates the threshold exactly.
Setting
Time is discrete, t∈N. Fix a probability space with a filtration (Ft). Initially N0=N>0 coins are outstanding, and the tracked investor (investor 1) holds n0∈[0,N0] of them. At each date t≥1 the protocol pays a deterministic reward Rt≥0, so the coin supply is
Nt=N0+n=1∑tRn.
Let 1St∈{0,1}, Ft-measurable, indicate that investor 1 is selected at t. She never trades, so her coins follow nt=nt−1+Rt1St, and her share is πt=nt/Nt. The PoS selection rule is
E[1St+1∣Ft]=πta.s., for every t≥0.
The other investors enter only through Nt. The power reward is Rt=ρNt−1γ for t≥1, with constants ρ,γ>0.
The variance sequence is a0=0, at+1=at+(Rt+1/Nt+1)2(1−at), the paper's (A12). Proposition 1 gives an almost-sure limit π1,∞=limtπt. For the goal, the initial share π1 is fixed and the initial supply N varies: model N has N0=N and n0=π1N.
Formalization targets
Goal: Proposition 4 (p. 14)
For ρ,γ>0 and π1∈(0,1),
N→∞limP(∣π1,∞−π1∣≥ε)=0 for every ε>0⟺γ<1.
The statement fixes no constant and no rate. It is the full equivalence, as printed.
Milestones (in the order the proof uses them)
(A2), p. 17: πt+1−πt=Rt+1(1St+1−πt)/Nt+1.
Proposition 1, p. 8: (πt) is a martingale with an a.s. limit π∞∈[0,1] and Eπ∞=π0.
Lemma 1, p. 19: Vart(πt+1)=(Rt+1/Nt+1)2πt(1−πt).
Lemma 2, p. 20: Var(πt+1)=at+1π0(1−π0).
Lemma 3, pp. 20–21: the recursion stays in [0,1] and is nondecreasing.
Lemma 5, p. 22: for γ∈[0,1), at+1≤1−γρNγ−1.
Lemma 6, p. 23: limNVar(π1,∞)=0 implies concentration.
p. 24: Var(π∞)=limtatπ0(1−π0).
p. 24: for γ≥1 and each N>0, at→1.
(A31), p. 24: a [0,1]-valued X with mean π1 and variance π1(1−π1) has P(∣X−π1∣>ε)≥1−ε2π1(1−π1)−ε2>0.
Significance
The result. Proposition 4 separates two regimes of PoS reward schedules that grow with the supply. For sublinear growth (γ<1) a large economy keeps every holder's share near its starting value: the protocol does not redistribute wealth. For linear or faster growth (γ≥1) the limiting share has the maximal variance π1(1−π1) whatever the initial supply. The share then ends near 0 or 1 with probability bounded away from zero, even though its mean is unchanged. Proposition 3 of the same paper covers non-increasing rewards. Together they say which PoS implementations give stable shares.
Formalizing it. The paper's proofs are short and informal. This mission produces a machine-checked version of the model and of the equivalence, and a reusable Lean treatment of a time-inhomogeneous two-colour Pólya urn: the martingale property, the closed-form variance recursion, and the variance of the limit. None of these results has a machine-checked proof on Prove2Me or in Mathlib.
Difficulty
The "if" direction combines Lemma 5 with Chebyshev's inequality. Lemma 5 needs a Riemann-sum comparison: the sum ∑nRnRn+1/Nn2 is bounded by ρ∫N∞xγ−2dx. This uses that R is increasing and x↦xγ−2 is decreasing, and the details matter at the first index. The step from the variances of πt to the variance of the limit π∞ needs dominated convergence for squares.
The "only if" direction is where the printed argument is loose. The page lets N→∞ inside a statement about t→∞. What is true and needed is that for each fixed N the ratio Rt+1/Nt+1 stays bounded below in t, so at→1. The tail bound (A31) must then be derived from the exact variance alone, uniformly in N. Neither Doob's convergence theorem nor Chebyshev's inequality gives this lower bound directly.
Formalization scope
All objects are defined in the namespace PoSShares.Stability. A Model Ω carries the filtration, N0, n0, R and the indicators ξt=1St. coinSupply, coins, share, IsPoS and IsPowerReward are its supply, coins (5), share (1), selection rule and power reward. aSeq and alphaSeq are (A12) and (A16), both started at index 0 with value 0. Committed conventions:
Selection rule. The page assumes St is "independent of all other random variables", which cannot hold literally, because its probability πt−1 depends on past selections. The formalization uses the conditional probability E[1St+1∣Ft]=πt that the proofs use. It is not independence of ξ from F, which would force a constant selection probability.
One tracked investor. The others enter only through Nt, as in §3.3.1 of the paper.
Real endowments.n0 is real; the paper takes n0∈N, which with fixed π1 and N→∞ would force π1N∈N.
Added hypotheses. The goal adds 0<π1<1: for π1∈{0,1} the share never moves and the "only if" fails. Lemma 5 adds N>0, which Lemma 4 states and Lemma 5 omits.
Corrected reading. Milestone 9 states at→1 as t→∞ for each N>0; the page writes limN→∞at=1. Milestone 10 keeps the printed strict >ε.
One probability space. The family of models indexed by N∈N lives on one probability space. Model N≥1 has N0=N; model 0 is unconstrained beyond the shared hypotheses. π1,∞ is any measurable a.s. limit, and probabilities are μ.real.
Trivializing formalizations are ruled out:
IsPoS is satisfiable for every N0>0, n0∈[0,N0] and R≥0, and the power reward rule has a solution for all ρ,N0>0.
The limit π1,∞ is a hypothesis whose existence Proposition 1 asserts; it is not a limUnder default.
Every variance concerns a bounded random variable, so no L2 junk value enters.
The endowment is pinned to π1N0, so the share cannot move with N.
The goal is the full equivalence, not one implication.
A complete development needs Mathlib's conditional expectation and conditional variance, the martingale convergence theorem for bounded martingales, the law of total variance, Chebyshev's inequality, and integral comparison for monotone functions. The urn lemmas (milestones 1–5 and 8) apply to any deterministic reward schedule and are reusable beyond this mission. Proofs of any milestone are welcome, as are alternative arguments for Lemma 5.
Selected references
I. Roşu and F. Saleh, Evolution of Shares in a Proof-of-Stake Cryptocurrency, Management Science 67(2), 2021. https://doi.org/10.1287/mnsc.2020.3791 (formalized from the authors' manuscript of July 30, 2020).
R. Pemantle, A survey of random processes with reinforcement, Probability Surveys 4:1–79, 2007. https://doi.org/10.1214/07-PS094
Online Allocation and Pricing: Constant Regret via Bellman Inequalities: Regret Is at Most the Information Loss Plus the Bellman LossResearch Paper
Motivation
An online allocator must commit to an action after each arrival, although later arrivals can change which actions would have been best. Revenue management and online resource allocation use regret to measure the expected reward lost against a benchmark. If the benchmark sees too much future information, this gap can grow with the horizon even when the online controller behaves optimally. Vera, Banerjee, and Gurvich use a benchmark whose extra information can be chosen for the application, and relate regret to two quantities that can be studied separately: how often the online action disagrees with an informed action, and how accurately a proposed value function satisfies a Bellman equation (Vera–Banerjee–Gurvich, 2020, §§2–3).
The paper proves constant-regret application results for online probing, dynamic pricing, and learning by combining this framework with estimates particular to each model. This mission isolates the framework's Theorem 5 and the displayed statements leading to it. Its result is known on paper; the work here is to give the model, the conditional expectations, and the regret bound machine-checkable statements.
Setting
There are T decision periods, indexed by time to got=T,T−1,…,1. At the start of period t the controller is in state St∈S and observes an input ξt∈Ξ. It selects an action u from a nonempty feasible set U(St,ξt), collects real reward R(St,ξt,u), and moves to St−1=T(St,ξt,u). The initial state is the fixed state ST=s0.
The observed filtrationFt is generated by the arrivals ξt,…,ξT. A non-anticipative policy chooses an Ft-measurable action from the current state. Offline has the augmented filtration Gt=Ft∨H, where H is a fixed sigma-algebra carrying extra information. Offline's value V(t,s) is the feasible-action maximum in the conditional Bellman equation (2), with V(0,s)=0. Its expected initial value is the benchmark for the online policy's expected reward. Regret is their difference.
A relaxed valueϕ(t,s) and a Bellman lossLB(t,s) obey the Bellman inequalities if ϕ initially bounds the conditional Offline value, ends at zero, and at each state is at most one feasible action's immediate reward plus its expected relaxed continuation and LB. An action meeting this inequality is satisfying. A maximum-loss boundr controls the shortfall of every feasible action. For a policy with action Ut on its actual trajectory, Qt is the event that Ut is not satisfying under this same ϕ and LB.
Formalization targets
Satisfying actions under augmented information
Proposition 1 concerns a feasible Gt-adapted policy that always takes satisfying actions. It bounds its shortfall from Offline by the expected accumulated Bellman loss:
The proposal also states the one-step displayed inequality from its proof, where a conditional continuation at a fixed state and action becomes the conditional continuation of the policy's random trajectory.
Regret decomposition
Theorem 5 concerns a feasible non-anticipative policy. It states the pathwise-compensation expectation bound and, when LB is nonnegative, the paper's two-term bound:
The milestones include the paper's maximum-loss, compensated one-step, and iterated displays on the route to this target. The first inequality is also stated for signed LB; only the second requires LB≥0.
Significance
The theorem turns a regret analysis into two concrete estimates. An application can count or bound the periods when the online action fails the informed satisfying-action test, and can separately quantify the error in its chosen relaxed value. Neither quantity alone certifies small regret; the theorem supplies the inequality connecting both to the benchmark's actual reward gap. The paper's constant-regret claims use application-specific bounds on these terms (Vera–Banerjee–Gurvich, 2020, §§4–6).
A complete formalization would establish the conditional-expectation and measurability infrastructure needed to apply this template to other finite-horizon allocation models. The paper gives a proof of Theorem 5, but the theorem and its applications have no machine-checked proofs in this mission. The proposal records the open Lean statements and a statement-only non-vacuity check for the exact Bellman value with zero loss.
Difficulty
Definition 5 describes a satisfying action for a fixed state and action, while Theorem 5 evaluates it at a random state and a policy's random action. The conditional expectation in that definition cannot simply be substituted syntactically for the conditional expectation of the ensuing trajectory. Countable states and finite actions make the substitution meaningful, but measurability of the selected state and action still has to be established. The same issue appears in the maximum-loss display. Time runs backward, so the information at t−1 contains the information at t; a forward-indexed filtration would change the conditional expectation in the paper's formulas.
The second displayed inequality presents a separate statement issue: removing 1Qtc from LB is valid only for nonnegative LB. The paper allows signed Bellman losses elsewhere, so nonnegativity is attached to that inequality rather than to the definition of Bellman inequalities.
Formalization scope
The Lean model uses a countable state type, a finite nonempty action type, real rewards, and an explicit nonempty feasible-action set. The probability space carries a probability measure, measurable arrivals, and an auxiliary sub-sigma-algebra H. The observed and augmented information families are plain sigma-algebra families because their order decreases with time to go. The index t=0 is terminal; decision sums and hypotheses use exactly t∈{1,…,T}. Offline's value is defined by the feasible-action Bellman recursion and is never a free benchmark variable.
The source bounds the maximum reward above. This formalization additionally bounds feasible rewards, ϕ, and LB in absolute value over the finite horizon, and requires measurable reward, transition, and feasibility data. These assumptions ensure the real integrals and conditional expectations have their intended values. Definition 4 is an almost-sure real upper bound r rather than a supremum that could take a default value. The feasible-action maximum in the Bellman inequality is represented by a feasible witness. The source's family GΘ is represented by the single sigma-algebra it generates, H.
The goal covers every feasible Ft-adapted state-feedback policy; RABBI is in this class. Proposition 1 retains its distinct Gt-adapted policy class. The disagreement event uses the same LB as the Bellman inequalities. The maximum-loss display follows Definition 4's parentheses and sign, correcting a printed slip on p. 14. The nonnegative-loss condition corrects the second inequality of the printed Theorem 5. A complete development needs reusable lemmas on finite feasible maxima, measurable state-feedback trajectories, conditional expectations under decreasing information, and integration of finite sums. Contributions to those lemmas and to the five stated milestones are in scope.
Selected references
Alberto Vera, Siddhartha Banerjee, and Itai Gurvich, Online Allocation and Pricing: Constant Regret via Bellman Inequalities, arXiv preprint arXiv:1906.06361v2, 2020. arXiv.
Procurement Mechanisms for Assortments of Differentiated Products: In the Hotelling Model, Decentralized Linear Pricing Achieves the Optimal Centralized Consumer SurplusResearch Paper
Motivation
Public buyers of medicines, school meals, computers and similar goods often run a framework agreement. A central agency selects an assortment of products through an auction and fixes their unit prices. Public offices then buy from that menu as needed, each choosing what suits it. The European Union awarded €80 billion through framework agreements in 2010, 17% of all public procurement by value. Chile's ChileCompra bought US$3 billion this way in 2018, 22% of the country's public procurement (figures as cited in the paper's introduction). Two decisions are bundled in such a mechanism: which differentiated products to put in the assortment, and at what prices. A larger assortment serves heterogeneous users better; a smaller one lets the buyer extract lower prices from the suppliers, whose costs are private.
Saban and Weintraub (Operations Research, 2021; author version SSRN 3453144) model this trade-off as a mechanism-design problem and ask a structural question: how much does the buyer lose by being restricted to linear prices, where users pick quantities from the posted menu and every supplier is paid its unit price times the quantity sold, compared with a centralized planner who could dictate allocations and arbitrary transfers? Their answer for the Hotelling model of horizontal differentiation, Theorem 4.1, is the goal of this mission.
Setting
There are n≥2 suppliers i∈N={1,…,n}. Supplier i has a private unit cost θi in a finite set Θi of positive reals, drawn independently with probability mass function fi>0 and cdf Fi. A profile is θ=(θ1,…,θn)∈Θ=∏iΘi.
A unit mass of consumers sits uniformly on [0,1]; supplier i is located at ℓi, with 0≤ℓ1<⋯<ℓn≤1. A consumer at u buying from i at price pi has utility −(δ∣ℓi−u∣+pi), with transportation cost δ>0. Allocations x∈X={x≥0:∑ixi=1} (no outside option) give gross consumer surplusGCS(x), minus δ times the total transportation cost, and consumer surplusCS(x,p)=GCS(x)−∑ipixi. The demandd(Q,p) for an assortment Q⊆N and prices p is a maximizer of CS(⋅,p) over x∈X with xi=0 for i∈/Q.
where ρi(θi) is the predecessor of θi in Θi (itself for the lowest type). Virtual costs are assumed strictly increasing (Assumption 3.1).
In a direct mechanism with allocation x(θ) and transfers t(θ), supplier i of type θi reporting θi′ gets interim utility Ui(θi′∣θi)=∑θ−if−i(θ−i)(ti(θi′,θ−i)−θixi(θi′,θ−i)). The two problems are:
Cent: maximize Eθ[GCS(x(θ))−∑iti(θ)] subject to incentive compatibility (IC), individual rationality (IR) and x(θ)∈X;
DecLin: choose an assortment q(θ), unit prices p(θ) and an allocation x(θ) to maximize Eθ[CS(x(θ),p(θ))] subject to (IC), (IR) with transfers ti=pixi, x(θ)∈X, and (Demand) x(θ)=d(q(θ),p(θ)).
OPT(⋅) denotes the optimal value. Every DecLin mechanism is a Cent mechanism with the same value, so OPT(DecLin)≤OPT(Cent) always.
Formalization targets
Goal: Theorem 4.1
Let c∗=min1≤i≤n−1(ℓi+1−ℓi). If (1) some profile has ∣vi+1(θi+1)−vi(θi)∣≤δ(ℓi+1−ℓi)/4 for all i, and (2) every ∣Θi∣≥3 and consecutive virtual costs differ by at most δc∗/8, then
OPT(DecLin)=OPT(Cent).
Milestones
The proof runs through the following statements, in attack order:
Proposition 3.1: an allocation maximizing CS(⋅,v(θ)) with decreasing interim allocations and transfers given by the discrete envelope formula (7) is optimal for Cent.
The explicit Hotelling demand (active set Q(p), neighbours split the segment between them) maximizes consumer surplus.
Proposition 3.2 (parts 1–2) for the general Hotelling model: the Hotelling demand at virtual costs, with the transfers of Appendix B, is feasible, meets Proposition 3.1's conditions, and is ex-post individually rational.
Corollary 4.1: prices that reproduce the optimal allocation (10) and the optimal interim transfers (11) give OPT(DecLin)=OPT(Cent).
For the Hotelling model, (10) is the linear system A(θ)p(θ)=A(θ)v(θ) of (Mi(θ)) and (13).
Lemma F.1, the finite Fredholm alternative.
Lemma F.2: an all-active box of profiles, and paths of profiles that change one active cost at a time.
Lemma F.3: a dependency (14) among the rows forces ∑i∈Q(θ)gi(θi)xi(θ)=0.
Step 1 of the proof: (14) forces every transfer-row coefficient with a nonzero row to vanish.
Step 2 of the proof: with those coefficients zero, (15) holds.
Significance
The theorem identifies a regime where linear pricing, the format actually used in framework agreements, loses nothing relative to the best mechanism with arbitrary transfers. In general it does lose: the paper's Example 4.1 has OPT(Cent)>OPT(DecLin) (values −2.0638 and −2.0645). The conditions say that virtual costs are close relative to the transportation cost, so that every supplier is in the optimal assortment for some profile and costs can be moved one supplier at a time without leaving the assortment. This gives a design guideline: when products are differentiated enough relative to cost uncertainty, posting unit prices suffices. The companion result for two-part tariffs (Proposition 4.1) and the affine-demand analogue (Theorem 4.2) are outside this mission.
The theorem has a complete proof in the paper (Appendix F and the electronic companion), but no machine-checked version exists. A formal proof would check the discrete-type envelope argument (Proposition 3.1), the explicit Hotelling demand as an optimal-transport maximizer, and the linear-algebraic consistency argument, which has gaps at ties (see Formalization scope). Each of these is reusable: the discrete Myerson characterization applies to any procurement or auction model with finite type spaces, and the Hotelling demand result applies to any model of spatial competition on a segment.
Difficulty
The obvious argument is: solve Cent by Proposition 3.1, then pick prices equal to virtual costs, which induce the right demand. This fails because prices must do two jobs at once. They must reproduce the centralized allocation through consumer choice, which pins down price differences among active suppliers profile by profile, and they must reproduce the interim transfers (11), which pins down averages of pixi across profiles. Prices equal to virtual costs satisfy the first and generally violate the second. The question becomes whether one linear system in all prices of all profiles is consistent.
Lemma F.1 converts consistency into the statement that every dependency among the rows is also a dependency of the right-hand side. Proving that requires showing that the coefficients on transfer rows vanish (Step 1), and this is where Theorem 4.1's conditions enter: Lemma F.2's all-active box and connecting paths propagate gi=0 from one profile to its neighbours. Without such connectivity the profiles split into classes whose transfer constraints conflict, which is exactly what happens in Example 4.1.
Formalization scope
The Lean development lives in the namespace ProcureAssort.Hotelling, with one definition item (Setting) and eleven theorem items. Conventions:
Suppliers are Fin n, 0-indexed, ordered by location; n≥2 is assumed because c∗ needs two suppliers. Types are a Finset ℝ per supplier; "consecutive types" means no element strictly between. Profiles are dependent functions; all expectations are finite sums.
fi>0 on Θi and ∑fi=1; Θi positive; Assumption 3.1 is a hypothesis of every Hotelling statement. In the model-free Proposition 3.1, consumption vectors are assumed nonnegative, as the paper's proof uses.
GCS(x)=−δ∑i∫x1+⋯+xi−1x1+⋯+xi∣u−ℓi∣du: suppliers serve consecutive blocks of consumers in location order, which is the cost-minimizing assignment. For n=2, ℓ=(0,1) it equals Example 2.1's −2δ(x12+x22).
(Demand) is consumer optimality, the defining property (2) of d. OPT is a real supremum; both value sets are nonempty and bounded above by 0 in the Hotelling instance.
Q(p) is defined with ≤ as printed. At ties a supplier can be in Q(p) with zero demand. For this reason, Proposition 3.2's uniqueness clause and Corollary 4.1's "only if" are not stated. Step 1 is stated for the transfer rows with a nonzero coefficient, the only rows the paper's argument uses. Lemma F.2's second property is stated in the existential form its proof establishes.
The goal cannot be satisfied trivially. DecLin ranges only over mechanisms whose allocation is consumer-optimal for the posted assortment and prices, and whose payments are price times quantity. DecLin therefore cannot choose allocations freely or pay lump sums, and an equality with OPT(Cent) is a substantive claim. The hypotheses are satisfiable, for example with two suppliers at 0 and 1, δ=16 and Θi={1,2,3} uniform.
A complete development needs: finite-type mechanism-design bookkeeping (interim sums, the envelope formula), the Hotelling demand as a maximizer (a one-dimensional transport argument), finite-dimensional linear algebra for Lemma F.1, and the combinatorics of Lemma F.2. Contributions to any milestone are welcome, as are proofs of the Fredholm alternative and of the discrete Myerson lemma in general form.
When Is Society Susceptible to Manipulation?: Under Any Principal Interference, Beliefs in a Mixed DeGroot–Bayesian Network Converge Almost Surely to (I − W)⁻¹(BU∞ ⊙ θ)Research Paper
Motivation
Misinformation campaigns target specific people in a social network and rely on the network to spread what they plant. Whether such a campaign can succeed depends on how people combine what they see themselves with what their neighbours believe. Mostagir, Ozdaglar and Siderius (SSRN 3474643; Management Science, 2022, doi:10.1287/mnsc.2021.4265) model a network in which a strategic principal injects slanted news into chosen agents. Some agents are Bayesian and know the truth; the rest are DeGroot agents who average their own news-based opinion with their neighbours' beliefs.
The paper asks when society as a whole can be manipulated. Every later result in it — which agents the principal targets, which networks resist manipulation, how the answer depends on the network's density — is a statement about the agents' long-run beliefs. Its Theorem 2 supplies those beliefs in closed form, and that closed form is the subject of this mission.
There are n agents and a binary statey∈{S,R} with prior q=P(y=S)∈(0,1). Agent i has a signal qualitypi∈[1/2,1). At each time τ=1,2,… agent i receives a signal si,τ∈{S,R}:
Organic news equals the state with probability pi: P(si,τ=S∣y=S)=P(si,τ=R∣y=R)=pi.
The principal fixes an influence statey^ and an influence strategyx=(x1,…,xn)∈{0,1}n. A targeted agent (xi=1) receives the principal's message y^ with probability λ∗/(λ+λ∗) and organic news with probability λ/(λ+λ∗). Here λ>0 and λ∗>0 are the intensities of the organic and the principal's news. An untargeted agent receives only organic news.
Agent i's signals are independent over time. Its personal experience is the posterior it would compute taking every signal at face value. With zi,tS,zi,tR the numbers of S and R signals among si,1,…,si,t,
A set B of agents is Bayesian. A Bayesian agent knows y and always believes it. Each DeGroot agent i∈/B has weights θi≥0 and αij≥0 with θi+∑jαij=1. For a state y′, its belief πi,t(y′∣y) follows the DeGroot update
πi,t+1=θiBUi(y′∣hi,t+1)+j=1∑nαijπj,t.
The influence matrixW has zero rows for Bayesian agents and row (αij)j for DeGroot agents. The vector θ=(1B,θm+1,…,θn) has entry 1 on Bayesians. The unweighted graph G∗ has a link i→j when i listens to j; for a DeGroot agent this means αij>0.
Assumption 1 (pp. 10–11):
(i) pi<(λ∗+λ)/(2λ) for every agent;
(ii) G∗ is strongly connected;
(iii) a DeGroot agent has θi>0 exactly when pi>1/2;
(iv) some agent has pi>1/2.
Formalization targets
Goal: Theorem 2 (p. 11)
Under Assumption 1, for every principal action x∗, each DeGroot agent's personal experience converges almost surely to a constant BUi(hi,∞(x∗))(y′∣y), and
πt(y′∣y)a.s.(I−W)−1(BU(h∞(x∗))(y′∣y)⊙θ),
where the Bayesian entries of the vector BU(h∞(x∗)) are the correct belief. The goal does not fix the constants: the paper computes them only later (display (2), p. 12).
Milestones
Lemma 3 (p. 45): the spectral radius of W is strictly less than 1.
Proof of Theorem 2 (p. 47): I−W and its DeGroot block I−ADD are invertible.
§3.2 (p. 11): BUi(hi,t) converges almost surely to a constant.
Proof of Theorem 2 (p. 47): if ut→u∞ and πt+1=ut+1+Wπt, then πt→π∞=(I−W)−1u∞, the solution of π∞=u∞+Wπ∞.
Significance
Theorem 2 reduces the paper's manipulation question to linear algebra. A DeGroot agent ends up believing the wrong state exactly when the corresponding entry of (I−W)−1(BU∞⊙θ) crosses a threshold. The principal's targeting problem then becomes a combinatorial problem over x∗ in which the network enters only through (I−W)−1. The paper's DeGroot centrality (Proposition 2) and its results on dense and sparse networks all start from this formula.
On formalization: the paper proves Theorem 2, but no machine-checked version exists. The mission's statements also record two places where the written argument needs repair. The text attributes the almost-sure convergence of BUi to the martingale convergence theorem, but BUi is a face-value posterior and not a martingale under the corrupted signal law. The proof's step from small increments of πt to convergence of πt is also not valid as written. Both claims are true under Assumption 1, and a complete development supplies correct arguments. The supporting results — spectral radius below one for a substochastic matrix with leakage reachable from every row, and convergence of linear recursions with convergent input — are reusable beyond this paper.
Difficulty
Two steps resist the obvious arguments.
First, BUi(S∣hi,t) is a function of the drift zi,tS−zi,tR of a random walk. Its limit exists only if the walk is transient or pi=1/2. For a targeted agent the walk's step law mixes the principal's message with organic news. For one boundary value of pi the step has mean zero, the walk is recurrent and BUi oscillates forever. Assumption 1(i) excludes exactly that value. A proof must use it; a martingale argument does not apply.
Second, W is substochastic but not strictly so: a DeGroot row sums to 1−θi, which equals 1 whenever pi=1/2. A row-sum bound alone gives ρ(W)≤1, not <1. Strict inequality needs every DeGroot agent to reach, in the weighted graph, an agent that leaks weight — a Bayesian or a DeGroot agent with θi>0. This uses the interaction of Assumption 1 (ii), (iii) and (iv), with Bayesian agents' outgoing links playing no role in W.
Formalization scope
Agents are Fin n and the Bayesian set is a Finset. Time is discrete, and the history at time t is the signals at times 1,…,t. The state space is a two-element inductive type. The signals are random variables on a probability space (Ω,P). Each agent's sequence is independent over time with the law above; signals of different agents may be dependent. This is deliberate: in the paper all targeted agents receive the same principal stream, so cross-agent independence would exclude the paper's own model. The principal's action is pure (x∗∈{0,1}n), as §3.2 allows without loss of generality. The DeGroot initial belief can be any value in [0,1], and the conclusion holds for every such initial belief on one almost-sure event. "Spectral radius" is Mathlib's spectralRadius ℂ of the complexified matrix. (I−W)−1 is Mathlib's matrix inverse; no invertibility hypothesis is added, because Assumption 1 implies it. In the graph G∗, a DeGroot agent's links are exactly its positive weights; Bayesian agents' links are free.
The personal experience is the explicit face-value posterior of the given signal process, and the conclusion of the goal includes its almost-sure convergence to the constants used in the limit. The goal therefore cannot be met by an abstract learning rule or a free limit vector.
A complete development needs:
the strong law of large numbers (available in Mathlib) applied to the signal counts;
a Perron–Frobenius-type spectral bound for substochastic matrices on a strongly connected graph;
convergence of πt+1=ut+1+Wπt when ρ(W)<1.
Contributions of any of these, as standalone lemmas, are welcome.
A. Jadbabaie, P. Molavi, A. Sandroni, A. Tahbaz-Salehi, Non-Bayesian Social Learning, Games and Economic Behavior 76(1), 2012. https://doi.org/10.1016/j.geb.2012.06.001
D. Acemoglu, G. Como, F. Fagnani, A. Ozdaglar, Opinion Fluctuations and Disagreement in Social Networks, Mathematics of Operations Research 38(1), 2013. https://doi.org/10.1287/moor.1120.0570
Experimental Design in Two-Sided Platforms: An Analysis of Bias: In Demand-Constrained Markets the Naive Customer-Side Estimator Is Unbiased and the Listing-Side Estimator Is Generically BiasedResearch Paper
Motivation
Online marketplaces such as lodging, ride-hailing and freelancing platforms test changes to their product (a new ranking, a new fee display, a new photo layout) with randomized experiments. In a two-sided marketplace these experiments are subject to interference: treated and control units compete for the same scarce supply or demand, so the outcome of one unit depends on the treatment of others, and the stable-unit assumption behind the textbook difference-in-means estimator fails. The resulting bias can be as large as the effect being measured, and platforms routinely choose between randomizing customers (customer-side randomization, CR) and randomizing listings (listing-side randomization, LR) without a principled guide.
Johari, Li, Liskovich and Weintraub (arXiv:2002.05670, Management Science 2022) introduced a tractable model in which this question can be answered. Their analysis shows that which side to randomize depends on market balance, the ratio of the rate of demand to the rate at which supply is replenished. This mission formalizes the demand-constrained half of that answer.
Setting
There are finitely many listing typesθ∈Θ and customer typesγ∈Γ. Listings of type θ form a mass ρ(θ)>0, with ∑θρ(θ)=1. Customers arrive at total rate λ>0, a share ϕγ>0 of them of type γ (∑γϕγ=1). A state s=(s(θ))θ records the mass of available listings of each type, and lies in S={s:0≤s(θ)≤ρ(θ)}.
An arriving type-γ customer includes each available type-θ listing in its consideration set with probability αγ(θ)∈(0,1], has utility vγ(θ)>0 for it and an outside option of value ϵγ>0, and books by multinomial logit. In the mean-field limit the probability that it books a type-θ listing is
A booked type-θ listing stays occupied for an exponential time of rate τν(θ), with τ>0 and ν(θ)>0. A steady state is a state s∗∈S balancing the flows:
(ρ(θ)−s∗(θ))τν(θ)=λγ∑ϕγpγ(θ∣s∗)(θ∈Θ).
A two-sided randomization (TSR) design treats a fraction aC of customers and a fraction aL of listings. The intervention replaces (α,v) by (α~,v~), both positive, only when a treated customer meets a treated listing. The experimental system is the same mean-field model on the types (γ,i) and (θ,j), i,j∈{0,1} (0 = control, 1 = treatment), with ϕγ,1=aCϕγ, ϕγ,0=(1−aC)ϕγ, ρ(θ,1)=aLρ(θ) and ρ(θ,0)=(1−aL)ρ(θ). The mass vector is written ρ(aL). At its steady state s∗(aC,aL), the rate at which condition-i customers book condition-j listings is
Fix every parameter except λ and τ, and consider sequences with λ/τ→0 (a demand-constrained market). Then for every aC∈(0,1)
λGTECR(∞∣aC)−λGTE⟶0,
and for every aL∈(0,1) and Lebesgue-almost every treatment utility v~ in the positive orthant, there is L=0 such that along every such sequence
λGTELR(∞∣aL)−λGTE⟶L.
Milestones
Theorem 1 (p. 12): the steady state of the base system exists, is unique, and is interior, 0<s∗(θ)<ρ(θ). Its second part characterizes s∗ as the unique minimizer of the objective W of (10).
§5.1 (p. 16): every design (aC,aL)∈[0,1]2 has a unique steady state.
Proposition 2 (p. 19), with Step 1 of its proof: as λ/τ→0, s∗(θ,j)→ρ(θ,j) and Qij(∞∣aC,aL)/λ→∑θ∑γϕγ,ipγ,i(θ,j∣ρ).
From the proof of Theorem 3 (p. A7): the limit (46) of GTE/λ, the limits of the scaled CR and LR estimators, and the identity pγ,0(θ,1∣ρ(1))=pγ,0(θ,0∣ρ(0)).
Significance
Theorem 3, together with its supply-constrained mirror (Theorem 4 of the paper, not part of this mission), is the paper's main structural finding. Each naive design is unbiased in one extreme of market balance and biased in the other. When demand is scarce, customers do not compete for listings, so randomizing customers creates no interference, while randomizing listings makes treated and control listings compete for the same customers. This finding motivates the paper's TSR designs, which interpolate between CR and LR according to market balance.
The result is proved in the paper; nothing here is open. To the best of the curators' knowledge, no part of it has a machine-checked proof. The mission produces a formal account of the mean-field model and its steady state, which other models of matching markets with MNL choice and occupancy can reuse. It also makes the informal "generically biased" claim precise: the paper argues it only by saying that the limit "in general" differs from the GTE.
Difficulty
The central step is Theorem 1. The steady-state equation is a nonlinear fixed point, and the objective W whose minimizer it is fails to be convex in s. Existence and uniqueness therefore need a change of variables under which W becomes strictly convex and coercive, followed by a boundary argument. The limit statements then follow from a quantitative bound on ρ−s∗ and the continuity of the choice probability, but they must hold at boundary designs (aC or aL∈{0,1}), where some types have zero mass.
The LR half carries a second difficulty. Showing that the LR estimator is biased for one parameter value is easy; the claim is that the bias vanishes only on a Lebesgue-null set of treatment utilities. That requires the zero set of a nonzero rational function on an open orthant to be null, a fact Mathlib does not state in ready form.
Formalization scope
Everything lives in the namespace TwoSidedExp.DemandLimit. Types are Fintype; treatment conditions are Fin 2. A mean-field system MFSystem Γ Θ carries ρ,ϕ,α,v,ϵ (eps) and ν. A Model adds α~,v~, and Model.expt aC aL is the experimental system. λ and τ are arguments, and a sequence of systems is a pair of positive real sequences with λn/τn→0.
Conventions the formalization commits to:
Standing assumptions, all hypotheses of every theorem: ρ>0, ∑ρ=1, ϕ>0, ∑ϕ=1, α,α~∈(0,1], v,v~>0, ϵ>0. The positivity ν>0 and the bounds α,α~≤1 are implicit in the paper (an exponential rate and probabilities) and are made explicit.
Qij(∞) is the right side of (18) evaluated at a given state, and every theorem feeds it a steady state. The paper's definition as a long-run time average, and the ODE dynamics, Proposition 1, the stability part of Theorem 1 and the Markov-chain convergence of Theorem 2, are out of scope. The mission is stated on the mean-field steady state.
Steady states are quantified over, never chosen. The §5.1 milestone is what makes these hypotheses satisfiable.
Theorem 1's variational part is posed on 0<s≤ρ, since Lean's Real.log 0 = 0. In (10) the printed τ(θ) is read inside the sums, as in (30).
"Generically" (footnote 7) is read as: all other parameters fixed, for almost every v~ in (0,∞)Γ×Θ. The literal footnote is ill-posed, because ρ and ϕ range over Lebesgue-null simplices. The printed GTELR(∞∣aC) is read with aL.
Trivializing formalizations are ruled out explicitly. Qij is never evaluated at ρ instead of the steady state. GTE is built from the experimental system's Q11(∞∣1,1) and Q00(∞∣0,0), not from a separate formula. The LR half is an almost-everywhere statement with a sequence-independent L=0, not an existential.
Infrastructure that is reusable beyond this mission: strict convexity and coercivity of log-sum-exp-type objectives, and the Lebesgue-nullity of zero sets of nonzero polynomials on Rn. Proofs of any milestone are welcome. So are alternative routes to Theorem 1, for example via a monotone fixed-point argument.
Selected references
R. Johari, H. Li, I. Liskovich, G. Y. Weintraub, Experimental Design in Two-Sided Platforms: An Analysis of Bias, arXiv:2002.05670v5, 2021; Management Science 68(10), 2022. https://arxiv.org/abs/2002.05670
T. G. Kurtz, Solutions of ordinary differential equations as limits of pure jump Markov processes, Journal of Applied Probability 7(1), 1970. https://doi.org/10.2307/3212147
R. W. R. Darling, Fluid limits of pure jump Markov processes: a practical guide, arXiv:math/0210109, 2002. https://arxiv.org/abs/math/0210109
D. Holtz, S. Aral, Limiting bias from test-control interference in online marketplace experiments, arXiv:2004.12162, 2020. https://arxiv.org/abs/2004.12162
Product Decomposition of Periodic Functions in Quantum Signal Processing: Every SU(2)-Valued Laurent Polynomial of Degree n in E_n Is Uniquely a Product of n Primitive Matrices and a UnitaryResearch Paper
Motivation
Quantum signal processing transforms the eigenphases of a unitary operator by a sequence of controlled operations and single qubit rotations. To know which transformations such a sequence can realize, one must characterize the matrix functions produced by the sequence. Haah's product decomposition theorem gives such a characterization without the restriction on the projectors used in some earlier quantum signal processing constructions. The result concerns exact functions; the numerical synthesis algorithm and its precision analysis are separate parts of the paper.
Setting
Let t be a nonzero complex number. A rank one orthogonal projectorP on C2 is a Hermitian matrix with P2=P and trace one. Its complementary projector is I−P. The associated primitive matrix is
EP(t)=tP+t−1(I−P).
For ∣t∣=1, this matrix is unitary with determinant one. Given n such projectors, indexed in their multiplication order, and a constant matrix E0∈SU(2), the product of interest is
F(t)=E0EP1(t)EP2(t)⋯EPn(t).
The leftmost primitive factor is EP1, and the product has exactly n primitive factors. At n=0 the product of primitive factors is the identity and F is the constant matrix E0. Although the physical interpretation uses points on the unit circle, the formula defines F at every nonzero complex t. These conventions follow §2, equations (2) and (3).
A matrix Laurent polynomial of width n is written
F(t)=j=−n∑nCjtj,
where each Cj is a complex 2×2 matrix and all coefficients outside [−n,n] vanish. The set Pn consists of these polynomials for which F(η)∈SU(2) whenever ∣η∣=1. A member has degree n when Cn=0 or C−n=0. The subset En consists of members whose nonzero exponents have the parity of n, so C−n+k=0 for every odd integer k. The notation F†(t) conjugate transposes each coefficient while leaving its exponent unchanged: F†(t)=∑jCj†tj. These are the conventions of Definition 1 and equations (4) and (5).
Formalization targets
The goal is all of Theorem 2. First, every product of n primitive matrices belongs to En. Conversely, every F∈En of degree n has a unique ordered tuple (E0,P1,…,Pn) satisfying the product formula, with E0∈SU(2) and each Pj a rank one orthogonal projector. For n>0, the final projector is determined by the leading coefficient:
Pn=Tr(Cn†Cn)Cn†Cn.
The formula includes the assertion that its denominator is nonzero under the theorem's hypotheses; that is a consequence to establish, rather than an extra assumption. The n=0 case retains the product characterization and uniqueness, while having no final projector. The milestones state the source's primitive matrix observation, polynomial identities, leading coefficient conditions, degree reduction, and the relation between the two extreme coefficients.
Significance
The theorem identifies the Laurent polynomials that admit the specified quantum signal processing product and says that the factors are uniquely recoverable from the matrix function when the number of factors is fixed. This supports the exact synthesis question motivating the paper: whether a desired SU(2) valued function on the unit circle is achievable by the primitive operations. The formula for Pn also identifies the last factor directly from a coefficient of the target function. Haah's §4 algorithm uses the decomposition, but its numerical guarantees are outside this mission.
The paper proves Theorem 2. The formalization target is a machine checked version of that known theorem and its source stated intermediate claims. The definitions of matrix Laurent polynomial evaluation, parity restricted coefficient families, and primitive projector factors can also support later work on polynomial matrix functions. The mission does not claim that these statements have already been proved in Lean.
Difficulty
Membership in SU(2) is given only on the unit circle, while coefficient identities needed for the decomposition concern Laurent polynomials throughout C∖{0}. A pointwise unitary identity on the circle must therefore be promoted to an identity of Laurent polynomials before its extreme coefficients can be compared. The main structural difficulty is that a matrix product may lose its highest and lowest powers even when its factors are nonzero. Identifying a projector that lowers the degree must control both extremes at once and preserve the parity and SU(2) conditions. Uniqueness also depends on fixing exactly n factors: extra complementary factors can cancel.
Formalization scope
Lean represents a Laurent polynomial by a coefficient family C:Z→Mat2(C) with explicit width support, and evaluates it by a finite sum of integer powers. Equalities of Laurent polynomials are stated for every nonzero complex t. The positive integer n is represented as a natural number, with integer casts for exponents. The special unitary group is Mathlib's SU(2); the paper's rank one orthogonal projectors are represented by Hermitian idempotence together with trace one. This trace condition is equivalent to rank one for these 2×2 projectors. An ordered function on Fin(n) supplies precisely n factors. The last factor has index n−1 in Lean.
The set En retains both the width and SU(2) conditions of Pn and adds the parity condition. It is defined from coefficients, not from the existence of a product decomposition. Allowing rank zero or rank two projectors, dropping unitarity, or allowing a variable factor count would change the theorem. The source's remark that any orthogonal projector yields a member of E1 is read with the rank one condition of equation (2): the literal unrestricted remark fails for 0 and I. The singular leading coefficient milestones require n>0, and the last projector formula has the same domain.
The development needs facts about 2×2 determinants, conjugate transpose, projectors, finite matrix products, and uniqueness of finite Laurent expansions. The Laurent polynomial infrastructure and rank one matrix facts are reusable beyond this theorem. Contributions proving the source stated milestones, their faithful supporting algebraic lemmas, and the main product characterization are in scope. The parity refinement of §3.1, Lemma 4, and the §4 synthesis algorithm with its running time claim are outside this mission.
Selected references
J. Haah, Product Decomposition of Periodic Functions in Quantum Signal Processing, Quantum 3, 190 (2019); formalization source: arXiv:1806.10236v4, 2020, pp. 3–5.
Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics: Singular Value Transformation by Real Polynomials via Alternating Phase ModulationResearch Paper
Motivation
Many quantum algorithms act on a matrix A that is not itself unitary: a Hamiltonian to be simulated, a linear system to be inverted, a projector to be amplified. The standard way to hand such a matrix to a quantum computer is to embed it as a block of a unitary U, so that A=ΠUΠ for two orthogonal projectors Π,Π. The question is then which functions f(A) can be produced from a few uses of U and U†.
Gilyén, Su, Low and Wiebe (arXiv:1806.01838, STOC 2019) answered it for polynomials: interleaving U and U† with phase rotations about Π and Π applies a polynomial to every singular value of A. This quantum singular value transformation (QSVT) recovers Hamiltonian simulation, amplitude amplification, fixed-point search, quantum walks and matrix inversion as instances of one identity, and is now the common language of these algorithms (see the survey of Martyn, Rossi, Tan and Chuang, PRX Quantum 2021).
Timeline.
2016: Low, Yoder and Chuang characterize the single-qubit sequences eiφ0σz∏jW(x)eiφjσz, which they call quantum signal processing (QSP) (PRX 2016).
2016–2017: Low and Chuang lift QSP to Hermitian blocks by qubitization (Quantum 2019; PRL 2017).
2018: this paper replaces eigenvalues by singular values, so that arbitrary (even rectangular) blocks are allowed, and removes the earlier constraint Pℜ(0)=0 for even degree.
Setting
Let HU be a finite-dimensional complex Hilbert space, U a unitary on it, and Π,Π orthogonal projectors. The projected unitary is A=ΠUΠ. Put d=rankΠ, d~=rankΠ, dmin=min(d,d~). A singular value decomposition of A consists of orthonormal bases (ψi)i≤d of imgΠ and (ψ~i)i≤d~ of imgΠ and numbers ς1≥⋯≥ςdmin≥0 with
A=i=1∑dminςi∣ψ~i⟩⟨ψi∣.
For f:R→C, the singular value transformation is f(SV)(A)=∑i≤dminf(ςi)∣ψ~i⟩⟨ψi∣ when f is odd and f(SV)(A)=∑i≤df(ςi)∣ψi⟩⟨ψi∣ when f is even, with ςi:=0 for i>dmin.
The phase operator of a projector is eiφ(2Π−I)=eiφΠ+e−iφ(I−Π). For Φ=(φ1,…,φn)∈Rn, the alternating phase modulation sequenceUΦ is the product, from j=1 on the left to j=n on the right, of eiφj(2Π−I)U when n−j is even and of eiφj(2Π−I)U† when n−j is odd. On the single-qubit side, R(x)=(x1−x21−x2−x) for x∈[−1,1], and Φ is said to realize P∈C[x] if P(x) is the top-left entry of ∏j=1neiφjσzR(x) for every x∈[−1,1].
In Lean these are ProjUnitarySVD U Proj Projt (the decomposition data), svtOdd/svtEven, phaseRefl, altPhaseSeq, reflR and qspRefl, in the namespace QSVT19.Main.
Formalization targets
Goal: Corollary 18 (singular value transformation by real polynomials)
Let n≥1 and let Pℜ∈R[x] have degree n, parity nmod2, and ∣Pℜ(x)∣≤1 on [−1,1]. Then there is Φ∈Rn such that for every singular value decomposition of ΠUΠ
with Π′=Π for odd n and Π′=Π for even n. The only constraints on Pℜ are those that are necessary; no degree-dependent constant appears.
Milestones
Lemma 6, Theorem 5, Theorem 4 (first claim): sum-of-squares factorization and the characterization of which polynomials, and which real parts, arise from QSP.
Corollary 8: every P meeting four explicit conditions is realized by some Φ∈Rd in the reflection form; Corollary 10: every Pℜ as in the goal is ℜ[P] for such a P.
Definition 11 (existence of the decomposition), Table 2 (orthonormality of the spanning vectors of Definition 12), Lemma 14 (the block decomposition of U into one- and two-dimensional pieces).
Theorem 17: if Φ realizes P, then P(SV)(ΠUΠ)=ΠUΦΠ for odd n and ΠUΦΠ for even n.
Lemma 9 (optional): explicit phases realizing the Chebyshev polynomial Td.
Significance
The result. Corollary 18 says that every real polynomial of degree n, of definite parity and bounded by 1 on [−1,1], can be applied to the singular values of ΠUΠ with n uses of U and U† and one ancilla qubit. Every application in §3.4–§5 of the paper (fixed-point amplitude amplification, singular vector transformation, the pseudoinverse, Hamiltonian simulation, Gibbs sampling) is this corollary applied to a suitable approximating polynomial, so a formal proof makes all of them conditional only on polynomial approximation bounds.
Formalizing it. The result is proved in the paper; none of the statements of this mission has a machine-checked proof on the platform. A formal development would provide reusable infrastructure absent from Mathlib: singular value decompositions over sub-spaces, the two-dimensional invariant-subspace decomposition of a projected unitary (a quantitative form of Jordan's lemma), and the polynomial characterization of single-qubit QSP. Theorem 3 of the paper, the W(x) form of the QSP characterization, is already posed on the platform as QAlgorithms.Childs.qsp_characterization; Corollary 8 depends on it.
Difficulty
The obvious argument for Theorem 17 is "restrict UΦ to each two-dimensional subspace and read off the QSP product". Making that rigorous means proving that the subspaces of Definition 12 are pairwise orthogonal, invariant under every factor of UΦ, and that U acts on each pair of bases by exactly the reflection R(ςi), including the degenerate blocks with ςi∈{0,1}, the one-dimensional blocks HiR,HiL where UΦ contributes a phase e±iφ0, and the complement H⊥. The polynomial side is harder still: Lemma 6 factors a nonnegative even polynomial through its multiset of complex roots, grouping roots in (0,1), in [1,∞), on the imaginary axis and in the open quadrant, while tracking degree and parity. Neither step reduces to a library lemma, and an argument that works only for Hermitian A, or only when Π=Π, proves a different theorem.
Formalization scope
HU is ι → ℂ for a Fintype ι with the inner product star v ⬝ᵥ w; operators are Matrix ι ι ℂ; "unitary" is U ∈ Matrix.unitaryGroup ι ℂ; "orthogonal projector" is IsStarProjection. The projectors are named Proj, Projt because Π is Lean notation. Indices are 0-based.
A singular value decomposition is the structure ProjUnitarySVD U Proj Projt of data: orthonormal families with Π=∑i∣ψi⟩⟨ψi∣, Π=∑i∣ψ~i⟩⟨ψ~i∣, nonnegative non-increasing ς, and (17). The goal is posed for every such decomposition, with Φ chosen first; the Definition 11 milestone shows that one exists. ςi≤1 is a consequence and is not assumed.
f(SV) is the sum over the decomposition (Definition 16), never the right-hand side of (32) or (33); a formalization that defines it by an operator expression trivializes the goal.
eiφ(2Π−I) is written eiφΠ+e−iφ(I−Π), equal to the matrix exponential for an idempotent Π. The ancilla of (33) is the first tensor factor.
eiφσz and the parity predicate are the published definitions of QAlgorithms_Defs_Hamiltonian. "deg ≤ k − 1" is degree < k and "parity k−1" is parity k+1, avoiding natural-number subtraction.
Printed slips that affect statements:
Corollary 10 omits ℜ[P]=Pℜ; it is restored, as used in the proof of Corollary 18.
Corollary 8 and Corollary 18 are false for degree 0 (a constant eiα, respectively a constant c=1); both are posed with d≥1, n≥1.
Theorem 17's "P and Φ as in Corollary 8" is read as (14), the only property its proof uses.
Lemma 14's (25)–(28) index the HL blocks by [d]∖[r]; this is read as [d~]∖[r], as in (24).
Contributions welcome: proofs of any milestone, general lemmas on SVDs of compressions ΠUΠ, and a proof of the platform's open QSP characterization.
Selected references
A. Gilyén, Y. Su, G. H. Low, N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, arXiv:1806.01838v1, 2018; STOC 2019. https://arxiv.org/abs/1806.01838
G. H. Low, T. J. Yoder, I. L. Chuang, Methodology of resonant equiangular composite quantum gates, Physical Review X 6, 041067, 2016. https://doi.org/10.1103/PhysRevX.6.041067
Persuading Customers to Buy Early: The Value of Personalized Information Provisioning: The Personalized Buy/Wait/No Mechanism Is Optimal and Strictly Beats Public SignalingResearch Paper
Motivation
A seller who sells over two periods, at a full price now and a discount later, loses revenue to strategic customers who wait for the discount. Waiting is costly to the customer only through availability risk: if inventory is scarce, the product may be gone by the second period. Inventory is usually known to the firm and not to its customers, so the firm can try to shape how scarce the product looks. Drakopoulos, Jain and Randhawa (SSRN 3191629, version of April 17, 2020) study this as a problem of Bayesian persuasion (Kamenica and Gentzkow, AER 2011) with many receivers: the firm commits to prices and to a signaling policy before it learns its inventory, and then sends each customer a recommendation.
Their two main results separate public from private information. Theorem 1 (p. 15): with a public signal, seen by all customers, the firm earns no more than with prices alone. Theorem 2 (p. 17): with personalized signals, which may depend on each customer's valuation and be randomized independently across customers, a simple Buy/Wait/No mechanism is optimal and strictly beats every public mechanism when the low inventory level is small. Personalized recommendations are the kind of information online retailers and travel platforms send (low-stock alerts, buy-now prompts).
Setting
There is a unit mass of customers with valuations distributed on V=[0,b] with density f and complementary distribution Fˉ(v)=∫vbf; the hazard rate f/Fˉ is non-decreasing. The firm's inventory Q is high, qH=1 (enough for everyone), with probability P(H)∈(0,1), and low, qL∈(0,1], with probability P(L)=1−P(H). The monopoly price is pm=argmaxppFˉ(p), and Fˉ−1(q) is the valuation at which a mass q of customers lies above.
A straightforward mechanism fixes prices p1,p2≥0 and, after seeing Q, draws a latent index k from a finite set with a state-dependent law; given (Q,k), each v-customer is independently told Buy (in period 1), Wait (buy in period 2) or No. A customer who requests the product in a period with s units left and demand of mass D from the others gets it with probability avail(s,D): 0 if s≤0, 1 if D≤s, s/D otherwise (random rationing). The mechanism is obedient if every customer (for almost every v) weakly prefers to follow her recommendation, given the availabilities she can expect conditional on it: (Buy-1)–(No), p. 40. The firm's revenue is the expected value of rationed sales p1min{D1,Q}+p2min{D2,(Q−D1)+}. A mechanism is public when the recommendations depend only on (k,v) and obedience holds for each realized k.
The personalized mechanism (PS1)–(PS2), p. 17, sets p1=Fˉ−1(qL). In state L it tells customers with v≥p1 to buy and the rest No; in state H it tells v≥p1 to buy with probability
σH(v)=min{P(H)P(L)p1−p2v−p1,1}(13)
and to wait otherwise, tells p2≤v<p1 to wait, and v<p2No. The price p2 solves Fˉ(p2)−p2f(p2)=Fˉ(vˉ) (14) with vˉ=sup{v:σH(v)<1} (15).
Formalization targets
Goal: Theorem 2
If qL≤Fˉ(pm), then (14) has a root p2∈(0,p1), and for every such root the mechanism (PS2) is obedient, its revenue Rprivate is at least that of every obedient mechanism at any prices, and
Lemma 2 (p. 35): the L-state profit ϕ(t,p) of a public threshold t satisfies ϕ(t,p)≤max{(Fˉ−1(qL)−p)qL,0}, and for qL<Fˉ(p) its unique maximizer is Fˉ−1(qL).
Theorem 1 (c) (p. 15): Rϕ∗ is the largest revenue of a public mechanism.
Lemma 3 (p. 44): at fixed prices p1>p2, the (t∗,p1,p2)-mechanism built from an optimal threshold t∗ of the one-parameter program (A.16) is obedient, earns its value Dˉ(p1,p2), and is optimal among obedient mechanisms with those prices.
Lemma 4 (p. 44, corrected reading): if Fˉ(p2)>qL, then Dˉ(p1,p2)≤Dˉ(Fˉ−1(qL),p2).
The result says that the value of information in this market lies entirely in its personalization: public information is worthless (Theorem 1), and private recommendations strictly raise revenue whenever low inventory is scarce relative to the monopoly market. The optimal mechanism is explicit and has a simple form, with the low-type firm selling out exactly in period 1 and the high-type firm mimicking it as far as incentive compatibility allows; in the paper's uniform example (qL=P(H)=1/2) revenue rises from 1/4 to 13/48. The proof technique, a relaxation to a linear program over signal profiles followed by a dual reduction to a single threshold, is a template for many-receiver persuasion problems with congestion.
The theorems are proved in the paper; none of them has a machine-checked proof. The mission produces a formal model of strategic customers under rationing and personalized signaling, and the formal versions of the five steps. Two printed steps need correction to be true and are stated in corrected form (Lemma 4's tie case, the location of the root of (14)); formal proofs settle that the corrections suffice.
Difficulty
The obvious argument is a pointwise one: for each valuation, the Buy incentive constraint caps the high-state Buy probability given the low-state one, so set every cap tight. It fails because the availabilities in the constraints depend on the aggregate masses that the recommendations themselves create, so the constraints for different valuations are coupled; the paper resorts to an infinite-dimensional linear program and asserts strong duality without proof (p. 41). Lemma 4 is the algebraically heavy step (pp. 46–50): an envelope argument over the threshold combined with the hazard-rate monotonicity. Theorem 2 then needs a one-dimensional optimization in p2, the existence of a root of (14) (a fixed-point equation, since vˉ depends on p2), and the case p2>p1, which the paper never treats.
Formalization scope
The paper's game (Definitions 1–2: a continuum of customers, Bayesian Nash equilibrium, sender-preferred selection) is re-expressed as the class its proofs reduce to by the revelation principle (p. 39, footnote 5): obedient straightforward mechanisms with aggregate masses. Revenue optimality over this class is what Theorem 2 asserts after that reduction. The latent index is finite (Fin n, for every n); it carries the correlation between customers' signals that public signals need. Obedience is required for almost every valuation, as in Definition 1.
Committed conventions: V=[0,b], b>0, f continuous on [0,b] and positive on [0,b); 0<P(H)<1, 0<qL≤1; qH=1 and customer mass 1. Availability is avail above; at zero demand it is 1 with stock left and 0 without. (14) is written Fˉ(p2)−p2f(p2)=Fˉ(vˉ). In (PS2)(a) "v>p1" is taken as v≥p1 (a null set). (B) is read with min{⋅,1}. The program (A.16) keeps the no-Buy mechanism (Fˉ(t)=0), which the printed version drops. "The optimal mechanism" is stated as "an optimal mechanism" (ties exist). Lemmas 3–4 take p2<p1, implicit in the paper's divisions; the goal ranges over all prices p1,p2≥0, including p2>p1 (p. 8). Milestone (16) is stated at the prices of (PS1): p1=Fˉ−1(qL) and p2∈[0,p1) a root of (14).
Trivializing formalizations are ruled out: revenue counts rationed sales, not p1D1+p2D2; obedience is the printed conditional constraint multiplied by the probability of the recommendation, never divided by a possibly zero probability; availability never uses Lean's x/0=0; the goal carries the existence of a root of (14), so "for every root" is not vacuous; the mechanism class contains public and correlated mechanisms; and Rprivate is the revenue of the mechanism (PS2), tied to the formula (16) by a milestone.
A complete development needs: the density measure on [0,b] and its tail function Fˉ, monotonicity and continuity of Fˉ and its inverse, the quasi-concavity of pFˉ(p) under a non-decreasing hazard rate, and bounds for the rationing function. The hazard-rate and Fˉ−1 lemmas are reusable for other pricing models. Contributions of helper lemmas, of a primal proof of Lemma 3 avoiding the duality argument, and of the case p2>p1 are welcome.
Selected references
K. Drakopoulos, S. Jain, R. S. Randhawa, Persuading Customers to Buy Early: The Value of Personalized Information Provisioning, SSRN working paper 3191629, version of April 17, 2020. https://ssrn.com/abstract=3191629
D. Bergemann, S. Morris, Information Design: A Unified Perspective, Journal of Economic Literature 57(1):44–95, 2019. https://doi.org/10.1257/jel.20181489
Calibration of Distributionally Robust Empirical Optimization Models: The Worst-Case Sensitivity of the Expected Reward Equals Its Variance Divided by φ''(1)Research Paper
Motivation
Distributionally robust optimization (DRO) guards a data-driven decision against misspecification of the model that generated the data. In its penalized form, the decision maker replaces the sample-average problem maxxEPn[f(x,Y)], where Pn is the empirical distribution of the data Y1,…,Yn, by
xmaxQmin{EQ[f(x,Y)]+δ1Hϕ(Q∣Pn)},
where Hϕ is a ϕ-divergence and δ≥0 controls how far an adversary may move the distribution. Such models are used in operations research, statistics and machine learning (Ben-Tal et al. 2013; Lam 2016; Duchi and Namkoong 2019), and a practitioner must choose δ. Gotoh, Kim and Lim (arXiv:1711.06565, Operations Research 2021) study this calibration problem. Their first contribution, on which the rest of the paper builds, is an exact description of what the robust model penalizes for small δ: the worst-case loss of expected reward is, to first order, the variance of the reward divided by the curvature ϕ′′(1) of the divergence. This mission formalizes that theorem (Theorem 2.2) together with its proof chain in Appendix F.
Setting
A decision x is fixed throughout, so the data enter only through the reward vector f=(f1,…,fn) with fi=f(x,Yi). The nominal distribution is a probability vector Pn=(p1,…,pn) with every pi>0; the empirical distribution of distinct data points is pi=1/n. Write
The divergence generator is a function ϕ:R→R∪{+∞} satisfying Assumption 2.1: ϕ is closed (lower semicontinuous) and convex, ϕ(z)≥ϕ(1)=0 for z≥0, ϕ(z)=+∞ for z<0, and ϕ is twice continuously differentiable on a neighbourhood of z=1 with ϕ′′(1)>0. Kullback–Leibler (zlogz−z+1), modified χ2 ((z−1)2) and Burg (−logz+z−1) generators all qualify.
For δ>0, the worst-case measuresQ(δ) of (2.7) are the minimizers, over probability vectors q=(q1,…,qn), of
Jδ(q)=i=1∑nqifi+δ1i=1∑npiϕ(piqi),
and Q(0)=Pn. The worst-case sensitivity (2.8) of the expected reward is
SPn(f)=−δ↓0limδEQ(δ)[f]−EPn[f].
The proof uses the convex conjugateϕ∗(ζ)=supz{ζz−ϕ(z)} (F.5) and a Lagrange multiplier c⋆(δ) for the constraint ∑iqi=1.
Formalization targets
Goal: Theorem 2.2 (p. 8)
For every ϕ satisfying Assumption 2.1, every Pn with positive weights and every f, worst-case measures exist for each δ>0, and for every choice of them
SPn(f)=ϕ′′(1)1VPn[f].
Milestones (Appendix F, in proof order)
(F.4), p. 48.ϕ′ has a continuously differentiable local inverse near ζ=0, with [ϕ′]−1(0)=1 and [ϕ′]−1(ζ)=1+ζ/ϕ′′(1)+o(ζ).
p. 49.ϕ∗ is finite and twice continuously differentiable near 0, [ϕ∗]′=[ϕ′]−1 there, [ϕ∗]′(0)=1 and [ϕ∗]′′(0)=1/ϕ′′(1).
(F.7)–(F.8), p. 49. For small δ>0 the first-order condition ∑ipi[ϕ∗]′(δ(−fi−c))=1 has a unique solution c⋆(δ) near −EPn[f], and c⋆(δ)→−EPn[f] as δ↓0.
Proposition F.1, (F.1)–(F.2), p. 47. For small δ>0 the worst-case measure is unique, qi∗(δ)=pi[ϕ′]−1(δ(−fi−c⋆(δ))), and c⋆(δ) maximizes the dual function −δ1∑ipiϕ∗(δ(−fi−c))−c.
Proposition F.1, (F.3), p. 47.qi∗(δ)=pi{1−δ(fi−EPn[f])/ϕ′′(1)}+o(δ).
Significance
Theorem 2.2 identifies penalized DRO, for small δ, with a mean–variance trade-off: the robust objective is (by the expansion (2.6), which the paper cites) EPn[f]−2ϕ′′(1)δVPn[f]+o(δ), and the theorem gives the derivative of the worst-case mean that underlies that expansion. The paper's calibration method (§§4–6) rests on this: since in-sample robustness acts by penalizing variance, δ is chosen by trading an out-of-sample reduction in variance against a loss in mean.
The result is proved in the paper; to the best of current searches it has no machine-checked proof. The mission produces a complete formal proof of Theorem 2.2 under the paper's own assumption, a formal treatment of the conjugate duality for penalized ϕ-divergence problems on finite supports, and corrected versions of three steps of the printed argument (see Formalization scope).
Difficulty
The theorem is a first-order expansion of an argmin, and the obvious route is to differentiate the optimality conditions at δ=0 by the implicit function theorem. That step fails under Assumption 2.1: the system defining the multiplier c⋆(δ) involves [ϕ∗]′ evaluated at δ(−fi−c), and its partial derivative in δ at δ=0 requires a third derivative of ϕ, which is not assumed. For ϕ(z)=(z−1)2+∣z−1∣5/2 the multiplier satisfies c⋆(δ)+EPn[f]≈0.036δ, so it is not differentiable at 0, although Theorem 2.2 still holds. A proof therefore has to extract the first-order behaviour of Q(δ) from continuity of c⋆ at 0 alone. Further work lies in showing that the minimizer is interior and unique for small δ when ϕ is only locally smooth, and in handling extended-real values of ϕ and ϕ∗.
Formalization scope
ϕ is a function ℝ → EReal satisfying Assumption21: lower semicontinuity, pointwise convexity on R (with 0⋅(+∞)=0), 0≤ϕ(z) for z≥0, ϕ(1)=0, ϕ(z)=⊤ for z<0, finiteness and C2 smoothness of the real part on an open interval around 1, and ϕ′′(1)>0. Assumption 2.1 is the only hypothesis on ϕ: no third derivative, no finiteness on (0,∞), and no separate ϕ′(1)=0 (it follows from the assumption).
Derivatives of ϕ and ϕ∗ are those of their real parts (EReal.toReal); every statement that differentiates also asserts or implies finiteness where it differentiates.
The data are indexed by Fin n. The weights are general, pi>0 and ∑ipi=1; the paper's empirical distribution is pi=1/n, and its variance n1∑i(fi−EPn[f])2 is the special case. The paper's (2.4) also allows zero weights; these are excluded.
Q(δ) ranges over the minimizers of Jδ on Mathlib's stdSimplex. The goal asserts that minimizers exist for every δ>0 and that the limit holds for every selection of minimizers; it is not a statement about an arbitrary function constrained by hypotheses, and the existence clause rules out a vacuous reading.
The sensitivity (2.8) is stated as a one-sided limit along δ↓0, so the branch Q(0)=Pn is not needed.
Corrected readings: (F.4) prints ϕ−1 and ϕ′′(0) for [ϕ′]−1 and ϕ′′(1); p. 49 prints [ϕ∗]′′(0)=1/ϕ′′(0) for 1/ϕ′′(1); the claim that c⋆ is continuously differentiable at δ=0 is false under Assumption 2.1, and milestone 3 states continuity at 0 instead. The clause "Q(δ) is continuously differentiable near δ=0" of Proposition F.1 is not stated; (F.3) is.
Out of scope: the asymptotic out-of-sample analysis of §§3–5 (Proposition 3.2, Theorem 3.3, Propositions 4.1, 4.2, 5.2, Theorem 5.3), the bootstrap calibration algorithm of §6 and the experiments of §7. Those results either apply cited limit theorems, or expand moments of quantities known only in distribution without the integrability that would justify it.
Everything beyond the local definitions is in Mathlib: EReal, LowerSemicontinuous, stdSimplex, deriv, ContDiffOn, HasDerivAt, Filter.Tendsto. A reusable by-product is the local theory of the convex conjugate of a C2 convex function near a point of positive curvature. Contributions of proofs of any milestone are welcome.
Selected references
J. Gotoh, M. J. Kim, A. E. B. Lim, Calibration of Distributionally Robust Empirical Optimization Models, Operations Research, 2021; read as arXiv:1711.06565v2, 2020. https://arxiv.org/abs/1711.06565
A. Ben-Tal, D. den Hertog, A. De Waegenaere, B. Melenberg, G. Rennen, Robust Solutions of Optimization Problems Affected by Uncertain Probabilities, Management Science 59(2), 2013. https://doi.org/10.1287/mnsc.1120.1641
J. C. Duchi, H. Namkoong, Variance-based Regularization with Convex Objectives, Journal of Machine Learning Research 20, 2019. https://arxiv.org/abs/1610.02581
Initial Coin Offerings, Speculation, and Asset Tokenization: A Utility-Token ICO Fails When v ≤ 2c and Otherwise Has a Unique Equilibrium with Cap n* in (mc/v, m/2) and No Fund DiversionResearch Paper
Motivation
A firm can sell utility tokens before it has produced the good those tokens will buy. The sale supplies cash for production, but the firm can keep some or all of that cash instead. Speculators anticipate both the later value of a token and this diversion incentive when deciding whether to buy. Gan, Tsoukalas and Netessine study the resulting financing and production decisions in a three-period model of an initial coin offering (ICO). Their utility-token analysis identifies a value-to-cost threshold below which the ICO cannot raise cash and, above it, a unique equilibrium design under the paper's demand condition. Gan, Tsoukalas and Netessine, SSRN author version, §§2–3 and Appendix B.1.
The question matters to operations and finance because the funds obtained before production change the firm's later incentive to produce. Selling more tokens supplies a larger budget but leaves the firm with fewer tokens to sell after demand is realized. The model makes that tension quantitative through the ICO cap, production quantity and market token price. Gan, Tsoukalas and Netessine, pp. 7–14.
Setting
The firm initially has no wealth and owns m>0utility tokens, redeemable for its future product. It chooses an ICO price τ≥0 and a capn∈[0,m] on tokens sold to speculators. There are z≥m potential speculators. Each wants at most one token and arrives simultaneously. If s tokens sell, the firm may produce Q units at unit cost c>0, subject to 0≤Q≤τs/c. Customer demand D has probability law μ and cumulative distribution function F; customers value each unit at v>c. Token counts and quantities are represented by real numbers, as in the paper's continuous optimization. Gan, Tsoukalas and Netessine, §2, pp. 7–10.
The market-clearing price of a token after demand is realized is (v/m)min{Q,D}. Write S(Q)=Eμ[min{D,Q}] for expected sales. Conditional on s sales, the firm maximizes (m−s)(v/m)S(Q)−cQ over the production budget. A production ruleQ(τ,s) selects a maximizer at every feasible history; it is determined by this optimization problem rather than prescribed by a closed formula. At the ICO stage a speculator's expected utility is
uτ(s)=zs(mvS(Q(τ,s))−τ).
The participation rule sells all n offered tokens when uτ(n)≥0, and otherwise sells none. The firm's expected terminal wealth is ICO receipts less production cost plus the market value of its unsold tokens. An equilibrium consists of production optimality after every feasible history and a pair (τ,n) maximizing this wealth over all τ≥0 and 0≤n≤m. The market-clearing and participation rules are the model's interpretations of Lemma 1 and Lemma 2(i). Gan, Tsoukalas and Netessine, (1)–(3), (10), pp. 8–10, 12, 34.
Formalization targets
Proposition 1 identifies the optimal production quantity in two regimes. Proposition 2 identifies when a cap can support positive sales at a positive ICO price. Lemma 2 and Propositions 12–13 supply the participation and optimal-cap statements recorded as milestones. The main target is Proposition 3, including every part of its conclusion. Gan, Tsoukalas and Netessine, pp. 11–14, 34–35.
If v≤2c, no feasible ICO design raises cash. If v>2c, the equilibrium ICO price τ∗ and cap n∗ exist and are unique. With
Q∗=F−1(1−m−n∗mvc),
the cap is the unique point in (mc/v,m/2) satisfying
cmvn∗S(Q∗)=Q∗.
The remaining conclusions are τ∗=(v/m)S(Q∗), all n∗ tokens sell, market-period token price equals (v/m)min{Q∗,D} with expectation τ∗, and the full ICO proceeds are used for production: cQ∗=τ∗n∗. Gan, Tsoukalas and Netessine, Proposition 3, pp. 13–14.
Significance
The result gives a precise failure threshold for a utility-token ICO and ties the successful design to demand, production cost and the amount of tokens retained by the firm. In particular, its cap is below half of the total token supply, and at the optimum the production budget binds. These are statements about the model's incentive problem, with the demand condition required for its uniqueness result. Gan, Tsoukalas and Netessine, discussion after Proposition 3, p. 14.
The paper proves these results mathematically. This mission records their Lean statements as open goals; it does not yet supply machine-checked proofs. Completing the formalization would also develop reusable facts about expected truncated demand, inverse distribution functions, and optimization under a cash budget. The equity-token comparison, extensions and numerical experiments remain separate from this target. Gan, Tsoukalas and Netessine, §§4, 6 and Appendix C.
Difficulty
The firm controls the ICO price and cap before the production decision, while speculator participation responds to the production rule. Raising the cap increases possible receipts but can lower the firm's incentive to produce and therefore the resale value speculators expect. A production optimum for fixed sales does not by itself identify which sales level will occur. The firm's wealth also changes regime when the production budget ceases to bind, so a single smooth optimization statement does not cover the entire feasible set. The uniqueness claim depends on the demand-density condition stated before Proposition 12. Gan, Tsoukalas and Netessine, §§3.1–3.4 and Appendix B.1.
Formalization scope
Demand is one probability measure μ on R: F is its cumulative distribution function and S(Q) is the integral of min(D,Q) against that same measure. The inverse expression is the infimum of nonnegative x with F(x)≥y. The paper's F−1(0)=0 is represented by F(x)=0 for x≤0 and F(x)>0 for x>0. Because the proofs and the Appendix B.1 condition use a density and its derivative, the formal setting requires a positive differentiable density wherever x>0 and F(x)<1. The paper's informal z≫m is represented by m≤z. These choices are explicit added assumptions or readings of the source's conventions. Gan, Tsoukalas and Netessine, pp. 8–9, 34, 37–38, 46–48.
The Appendix B.1 condition on f′/f2 is applied at interior quantiles 0<y<1−2c/v, avoiding the support boundary where the paper does not define the derivative. Lemma 2(ii)–(iii) is stated at τ>0, because at zero price its printed conclusions fail. The positive boundary price in Proposition 12 is considered on the open viable-cap interval; its printed upper endpoint has no positive solution. Its “unique solution” is the unique positive solution, since zero also solves the first displayed equation. The participation equality there is evaluated at full sales s=n: evaluated after abstention at s=0, it would hold automatically. These boundary readings follow the paper's own adjacent analysis. Gan, Tsoukalas and Netessine, pp. 12–13, 34–35, 45–47.
The production rule is quantified over every rule that truly optimizes the budgeted production subgame. Expected sales is the integral against μ, never a free function unrelated to F. The equilibrium optimizes over all feasible prices and caps; the narrow interval for n∗ is a conclusion. The work needed includes measure-theoretic sales identities, quantile behavior, and the firm's regime-dependent optimization. Contributions establishing these facts or proving the named milestones fit this mission. The model here is the base utility-token, simultaneous-arrival model; equity tokens, sequential arrival, the §6 extensions and numerics are outside its scope.
Selected references
J. R. Gan, G. Tsoukalas and S. Netessine, Initial Coin Offerings, Speculation, and Asset Tokenization, SSRN author version 3361121, June 29, 2020; published in Management Science (2020). SSRN author version, DOI.