← All problems

The maximal-index conjecture for sums of matrix entries from a probability vector

5 years old · documented by

Let p∈R≥0dp\in\mathbb{R}^d_{\geq 0} satisfy

∑i=1dpi=1.\sum_{i=1}^d p_i=1.

Define matrices a,g∈Rd×da,g\in\mathbb{R}^{d\times d} by

aij=pi+pj2,gij=pipj.a_{ij}=\frac{p_i+p_j}{2},\qquad g_{ij}=\sqrt{p_i p_j}.

Let ak↓a_k^\downarrow and gk↓g_k^\downarrow denote the kkth largest entries of aa and gg, respectively, and set

A=∑k=1h(d)ak↓,G=∑k=1h(d)gk↓.A=\sum_{k=1}^{h(d)}a_k^\downarrow,\qquad G=\sum_{k=1}^{h(d)}g_k^\downarrow.

Maximal-index conjecture. The maximal integer h(d)h(d) for which A+G≤dA+G\leq d holds for every probability vector pp is

h(d)=2d−5.h(d)=2d-5.

This conjecture concerns the sharp index in a bound arising from criteria for Markovian divisibility of linear maps. The supplied text gives no resolution or evidence establishing the claim, so its status remains open.

References
  1. Matthias C. Caro and Benedikt Graswald, “Necessary Criteria for Markovian Divisibility of Linear Maps”, arXiv:2009.06666 (2022).

Progress summary

Refreshed
Open · progress reported

A reader-submitted proof claims to settle the conjecture in dimensions five and higher, but no independent verification has been found.

The conjecture predicts that the sharp cutoff is h(d)=2d−5h(d)=2d-5. The previously catalogued 2020 source reported no resolution.

Community submission (unverified), October 28, 2026

A submitted proof argues that, for every d≥5d\ge 5, the inequality holds exactly when k≤2d−5k\le 2d-5, using incidence bounds, Cauchy--Schwarz, and a sharpness family. This is a claimed proof, not an independently verified result.

Current status (as of October 2026): The conjecture remains open in the verified literature; a reader-submitted proof claims the d≥5d\ge 5 classification, but it is unverified.

Sources

Solutions 1

For each probability vector in dimension d>=5, form and independently sort all d^2 ordered arithmetic means and all d^2 ordered geometric means. The sum of their respective largest k entries is at most d for every probability vector exactly when k<=2d-5. Incidence bounds, Cauchy–Schwarz and a sharpness family prove the classification. The complete separately sorted source statement is certified in Lean.See full solutionHide full solution

Scope: dimensions d>=5. The paper proves the exact maximal-index classification for every d>=5. This is not a claim that the unqualified formula holds in all smaller dimensions.

For each probability vector in dimension d>=5, form and independently sort all d^2 ordered arithmetic means and all d^2 ordered geometric means. The sum of their respective largest k entries is at most d for every probability vector exactly when k<=2d-5. Incidence bounds, Cauchy–Schwarz and a sharpness family prove the classification. The complete separately sorted source statement is certified in Lean.

AI-assisted preprint by Myeongjin Kang, with no affiliation. Internal AI review is not external journal peer review. The accompanying Lean certificate covers the precise scoped main statement; inspect the formal endpoint, assumptions and provenance in the supporting package. Prior-art investigations are documented bounded searches, not worldwide-priority certification. Original prose is offered under CC BY 4.0 and original code/Lean under MIT; third-party rights and existing notices are preserved. The public supporting ZIP contains original proof sources and verification evidence, with bibliographic links and hashes instead of redistributed third-party source manuscripts.

Recorded prior-art/source-access limits: No earlier resolution found in inspected primary and full-body citing sources. Citation indexes are incomplete; one published citing body and subscription indexes remain unread. Author listings are not full-body surveys. Parent addendum qualifies review scope; no absolute worldwide priority certified.

Full paper: Sharp maximal index for separately sorted arithmetic and geometric means in every dimension at least five.

Lean proof sources and pinned verification evidence: Zenodo supporting package. MathDB has not automatically verified the attached Lean certificate.