Central-Trajectory Integral Bounds

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

The primal-dual central trajectory satisfies primal and dual feasibility with positive primal variables $x$ and dual slacks $s$, and $x_i s_i=\nu$. A dot denotes differentiation with respect to $\nu$, $\circ$ is componentwise multiplication, and $\lVert z\rVert_1=\sum_i|z_i|$.

A linear program optimizes $c^Tx$ over a polyhedron $\{x:Ax\leq b\}$. In the simplex method a pivot moves between adjacent basic feasible solutions; a pivot rule chooses the next such move.

Statement recorded in the supplied source.

For the primal-dual central trajectory $(x(\nu),s(\nu),y(\nu))$ of a linear program with constraint matrix $A$, define $\kappa(\nu)=\lVert\nu\dot x(\nu)\circ\dot s(\nu)\rVert_1^{1/2}$ and $$F(\nu_0,\nu_1)=\int_{\nu_1}^{\nu_0}\frac{\kappa(\nu)}{\nu}\,d\nu.$$ Is $F(\infty,0)$ bounded by a quantity depending only on $A$? More specifically, is $F(\infty,0)=O\!\left(n^{3.5}\log(\bar\chi_A^*+n)\right)$? [S2]

Scope qualification.

The condition measure $\bar\chi_A^*$ and required rank/feasibility assumptions are those of the report. $F(\infty,0)$ denotes the corresponding improper integral when defined.

Source status.

The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Bound the total stated central-path integral using only the constraint matrix and obtain the conjectured quantitative estimate.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30000172 (OWR-783-004). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Optimization and Applications $2005$, Oberwolfach Reports, DOI 10.4171/owr/2005/02, pp. 69--133 https://doi.org/10.4171/owr/2005/02.
• S3 primary OWR paper text https://ems.press/content/serial-article-files/45976. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30000172 and source code OWR-783-004 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

The primary report, printed pages 123--124, states a superlevel-covering theorem for each constant curvature threshold and then conjectures the full improper-integral bound. This attempt proves the full integral estimate for $A=(1,1)$ and an elementary sufficient condition for the general conjecture. Applying that condition to the reported theorem requires a threshold-uniform bound on its implicit constants. The short report does not supply the proof needed to audit that uniformity, so the conditional reduction is not presented as a proof of the conjecture or as a contradiction in the report.

Research attempt: A two-variable integral and a conditional superlevel reduction

A direct bound on curvature

Use standard-form feasibility $Ax=b$, $A^Ty+s=c$, positivity, and $x_is_i=\nu$. Assume the central trajectory is differentiable on the interval in question. Differentiating gives $A\dot x=0$, $\dot s=-A^T\dot y$, and $s_i\dot x_i+x_i\dot s_i=1$. Set \[ u_i=\sqrt{s_i/x_i}\,\dot x_i,\qquad v_i=\sqrt{x_i/s_i}\,\dot s_i. \] Then $u+v=\nu^{-1/2}{\bf1}$ and $u\cdot v=\dot x\cdot\dot s=0$. Consequently $\lVert u\rVert_2^2+\lVert v\rVert_2^2=n/\nu$, and Cauchy's inequality followed by $2ab\leq a^2+b^2$ gives \[ \kappa(\nu)^2=\nu\sum_i|u_iv_i| \leq\nu\lVert u\rVert_2\lVert v\rVert_2\leq n/2. \] This is a finite-interval pointwise estimate; integrating a constant against $d\nu/\nu$ over all positive $\nu$ would diverge.

The entire improper integral for one fixed matrix

Take $A=(1,1)$, right side $b>0$, and any two real costs. Subtracting a constant from both costs changes only the dual variable, and swapping coordinates does not change the integral. For unequal costs it therefore suffices to use costs $(0,c)$ with $c>0$. Write the slacks as $(s,s+c)$ and set $t=s/c>0$. Solving feasibility and complementarity gives \[ x_1=\frac{b(t+1)}{2t+1},\quad x_2=\frac{bt}{2t+1},\quad \nu=\frac{bc\,t(t+1)}{2t+1}. \] The derivative $d\nu/dt=bc(2t^2+2t+1)/(2t+1)^2$ is positive; $t$ parametrizes all $0<\nu<\infty$. Differentiating $x_i$ and $s_i$ and using $d/d\nu=(d\nu/dt)^{-1}d/dt$ yields \[ \kappa^2=\frac{2t(t+1)(2t+1)}{(2t^2+2t+1)^2},\qquad F(\infty,0)=\sqrt2\int_0^\infty\frac{dt}{\sqrt{t(t+1)(2t+1)}}. \] On $(0,1]$ the integrand is at most $\sqrt2/\sqrt t$; on $[1,\infty)$ it is at most $t^{-3/2}$. Hence \[ F(\infty,0)\leq2\sqrt2+2, \] independently of $b$ and of the nonzero cost difference. With equal costs the two primal coordinates are constantly $b/2$, so $\dot x=0$ and $F=0$. This proves a matrix-only bound for this one-row two-variable family, including the cost-degeneracy case, without claiming continuity of the total integral in that degeneracy.

Exactly what a uniform superlevel bound would imply

For general $A$, put $H=\log(\bar\chi_A^*+n)$ and suppose, as an additional hypothesis, that one absolute constant $C$ gives \[ \mu\{\nu>0:\kappa(\nu)>t\} \leq Cn^3\left(H+\log^+(1/t)\right),\quad 0<t\leq\sqrt n, \qquad d\mu=d\nu/\nu. \tag{1} \] Here $\log^+(z)=\max(0,\log z)$, and the same $C$ must work for every threshold, dimension and instance covered by the theorem. Pointwise $\kappa(\nu)=\int_0^{\sqrt n}{\bf1}_{\{t<\kappa(\nu)\}}dt$. Integrating this nonnegative identity first on finite rectangles, then taking increasing limits, gives the layer-cake identity \[ F(\infty,0)=\int_0^{\sqrt n}\mu\{\kappa>t\}\,dt. \] Under $1$ this is at most \[ Cn^3\left(\sqrt n H+\int_0^1\log(1/t)\,dt\right) =Cn^3(\sqrt n H+1). \] For $n\geq2$ this has the conjectured order. The elementary integral equals one by evaluating $t-t\log t$ at the endpoints; the limit $t\log t\to0$ follows, for example, by writing $t=e^{-u}$.

The report covers each superlevel set by at most $n(n-1)/2$ intervals of logarithmic length of the stated order $nH+n\log(1/t)$. If their hidden constant were uniform as in $1$, summing their lengths and applying the displayed argument would finish this route. A theorem only for each fixed threshold, with an uncontrolled threshold-dependent constant, is insufficient: integrability of that dependence must be proved. We have not checked the underlying full proof or obtained a uniform replacement. The report's explicit logarithmic term makes this route worth checking, but is not a substitute for that missing audit. No assertion is made that its constant actually fails to be uniform.

Verification and adversarial audit

The two-variable parameterization covers both ends of the improper integral and cancels the data-dependent scales $b,c$ exactly. Equal costs are handled separately because the substitution $t=s/c$ is then invalid. The curvature bound uses orthogonality from exact primal-dual feasibility. The layer-cake argument is nonnegative, so it does not assume finiteness of the desired integral in advance. Its hypothesis $1$, rather than a silently imported uniformity assertion, is displayed explicitly.

Audit corrections.

Kept the source conjecture separate from a conditional consequence of a stronger audited superlevel estimate; checked zero cost difference and both improper-integral endpoints.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The general matrix-only bound and its quantitative dependence remain unresolved here. A complete special family and a conditional implication are established. Proving or extracting a threshold-uniform estimate from the source literature is the first unfinished step of the general route, and its mathematical validity is not claimed merely because the source has a fixed-threshold theorem.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/45976 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.