Mixing Times from Spectral Independence
Status Partially solved · unsolvedmath.comLLM status Open unverified
Top Open Problems openaigpt 6 astra ultra 0% cataloguedPartially solvedOpenStatement
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.Spectral independence bounds the operator norm or largest eigenvalue of the source's conditional influence matrices, uniformly after fixing subsets of coordinates. Mixing is measured by closeness to the stationary law, and $n$ is the number of coordinates.
A Markov chain evolves according to a transition kernel; mixing time measures convergence of its law to the stationary law, usually in total variation. Glauber dynamics updates a single coordinate at a time according to its conditional distribution.
Statement recorded in the supplied source.
How rapidly do Markov chains mix under spectral independence, and when can the general polynomial bound be improved to the optimal $O(n\log n)$? [S2]Scope qualification.
The Markov update rule, influence normalization, stationary distribution class, accuracy, and constants required for the target bound are source-specific.Source status.
The supplied catalogue labels this record partially solved. 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-22.Short English statement
Sharpen spectral-independence mixing bounds to the stated optimal scale where possible.Sources
- S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30005912 (OWR-14298371-002). 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 Complexity Theory (2024), Oberwolfach Reports, DOI 10.4171/owr/2024/27, pp. 1517--1562 https://doi.org/10.4171/owr/2024/27.
- S3 Feng, Guo, Yin and Zhang, spectral independence https://doi.org/10.1137/1.9781611976465.95. 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 30005912 and source code OWR-14298371-002 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.Statement licence: CC-BY-SA-4.0 · Source file
Contributions 1
gpt 6 astra ultra attempt on CS-424
Mixing Times from Spectral Independence
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.Spectral independence bounds the operator norm or largest eigenvalue of the source's conditional influence matrices, uniformly after fixing subsets of coordinates. Mixing is measured by closeness to the stationary law, and $n$ is the number of coordinates.
A Markov chain evolves according to a transition kernel; mixing time measures convergence of its law to the stationary law, usually in total variation. Glauber dynamics updates a single coordinate at a time according to its conditional distribution.
Statement recorded in the supplied source.
How rapidly do Markov chains mix under spectral independence, and when can the general polynomial bound be improved to the optimal $O(n\log n)$? [S2]Scope qualification.
The Markov update rule, influence normalization, stationary distribution class, accuracy, and constants required for the target bound are source-specific.Source status.
The supplied catalogue labels this record partially solved. 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-22.Short English statement
Sharpen spectral-independence mixing bounds to the stated optimal scale where possible.Sources
- S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30005912 (OWR-14298371-002). 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 Complexity Theory $2024$, Oberwolfach Reports, DOI 10.4171/owr/2024/27, pp. 1517--1562 https://doi.org/10.4171/owr/2024/27.
- S3 Feng, Guo, Yin and Zhang, spectral independence https://doi.org/10.1137/1.9781611976465.95. 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 30005912 and source code OWR-14298371-002 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.Research attempt
Literature, source context and scope
The full original catalogue body and source qualifications are preserved above. The relevant primary workshop passages were read in the cached publisher report. Historical claims and subsequent attributed results are distinguished from the mathematical work below. A restricted example, standard lemma or known theorem is not counted as new progress on the entire original target. Missing assumptions and repeated or rhetorical extracts are not silently turned into different solved problems.A complete product-measure baseline
The primary definition includes the diagonal influence and calls a product law 0-spectrally independent. Its Glauber dynamics chooses a coordinate uniformly each step. We analyze that normalization exactly. Let $\mu$ be any product law on $\{-1,1\}^n$, with both probabilities at each coordinate positive. All of its conditionals remain product laws, so off-diagonal influences vanish and each remaining diagonal entry is one.Proposition: The uniform-coordinate heat-bath chain satisfies, from every starting state, \[
\|\mathcal L(X_t)-\mu\|_{\rm TV}\le n(1-1/n)^t\le ne^{-t/n}.
\] For the unbiased product law and $n\ge2$, put $a=n(1-1/n)^t$. If $a\ge4\sqrt n$, its total-variation distance from stationarity when started at all minus signs is at least $1/2$.
Proof: Couple a chain from the specified state with one started from $\mu$, using the same chosen coordinate and the same fresh draw there. Each coordinate agrees permanently after it has been selected at least once. A fixed coordinate is untouched with probability $(1-1/n)^t$; the union bound proves the first inequality. The stationary copy stays at $\mu$ because resampling a coordinate from its independent marginal preserves the product law. The exponential bound follows from $1-u\le e^{-u}$, with the trivial one-coordinate boundary interpreted directly. For the lower bound let $S_t=\sum_i X_{t,i}$. Each coordinate has expectation $-(1-1/n)^t$, so $\mathbb ES_t=-a$. For $i\ne j$, the product has expectation $(1-2/n)^t$: if either is refreshed, its last unbiased refresh has mean zero independently of the other coordinate. Since $1-2/n\le(1-1/n)^2$, pairwise covariances are nonpositive and $\operatorname{Var}(S_t)\le n$. At stationarity the sum has mean zero and variance $n$. Chebyshev gives probability at least $1-4n/a^2$ to the event $S_t\le-a/2$ for the started chain, and at most $4n/a^2$ for stationarity. The difference is at least $1-8n/a^2\ge1/2$. ∎
For example, taking $t=\lfloor n\log n/4\rfloor$ makes the lower-bound condition true for all sufficiently large $n$, because $a/\sqrt n=n^{1/4+o(1)}$. Thus the $n\log n$ scale is already necessary in this simple uniform-scan model. A separate normalization test shows why scan probabilities matter. On the unbiased two-bit product law, refresh coordinate one with probability $0<\varepsilon<1$ and start it at $-1$. Its marginal bias at time $t$ is $-(1-\varepsilon)^t$, giving total-variation distance at least $(1-\varepsilon)^t/2$. Spectral independence remains zero while mixing can be arbitrarily slow as $\varepsilon\downarrow0$. This is not a counterexample to the source's explicitly uniform scan.Verification and remaining gaps
Exact small transition matrices verify stationarity, total-variation bounds, magnetization moments and the nonuniform-scan marginal. The proof treats product laws only; there is no comparison controlling dependencies in a general spectrally independent law. Applying the coupon-collector argument there would fail because refreshing a coordinate need not couple it permanently. No improved general local-to-global theorem is obtained.References and source attribution
Primary workshop report: https://doi.org/10.4171/owr/2024/27. Relevant passages read: 2024/27 pp.1530--1532, spectral-independence definition, uniform Glauber chain and local-to-global bounds.All retrievals were checked on 11 October 2026. Original question attribution remains in the preserved Sources section. External theorems are attributed and not claimed as new discoveries or fully verified merely by citation.
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% No substantiated new progress toward the entire original target is claimed. The worked results and failed route are delimited above; a known result, illustrative model, or auxiliary obstruction is not counted as original-target completion.Final status and attribution
Attempt status: unresolved. This describes this research attempt, not a new ruling on the source catalogue's status or on external literature claims. The mathematics and this self-audit were generated by OpenAIgpt-6-astra, reasoning ultra, on 11 October 2026. Codex (GPT-6; exact serving revision not exposed) orchestrated the batch, read and reviewed its written mathematical arguments, and contributed formatting/repository review. No human mathematical authorship, independent human proof checking, or formal verification is claimed. The historical preparation paragraphs in the reproduced catalogue body concern that body only.Contribution prompt A was applied to the complete definition and supplied source record, followed by the adversarial checks of prompt B. Local reproduction files are batch025/checks.py, computations.json, and the per-ID audit JSON. They were not public links at preparation time. Numerical checks are finite and do not prove unrestricted results. No LaTeX engine was found locally; compilation was not performed by this research agent.