Degree-two-and-three Markov basis for the Birkhoff ranking model

A finite degree-p Markov basis for complete-ranking surveys

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

For an integer matrix $A$ and statistic vector $b$, the nonnegative integer fiber is $\mathcal F_b=\{x\in\mathbb N^d:Ax=b\}$. A Markov basis is a finite set of integer moves in $\ker A$ connecting every such fiber by moves that remain nonnegative. Its binomial generators form the toric ideal $I_A=\langle x^u-x^v:Au=Av\rangle$. In the ranking model, coordinates count permutations and $A$ has the vectorized permutation matrices as columns. The fixed summary counts how often each candidate appears at each rank.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. The source question is preserved as a solved historical record. No degree bound or minimality assertion is imported from the expanded catalogue title. The supplied catalogue marks this record solved; its present research status was not independently checked. The source text below is rendered literally where necessary; damaged formulas and composite extracts are not silently repaired into a new mathematical claim.

Statement recorded in the supplied source.

Problem 1. Explicitly describe a Markov basis for tables with fixed first-order summary. That is, describe a set of moves which will connect any two surveys that have the same first order summary. In a purely mathematical language: describe a generating set for the toric ideal given by the p2 × p! matrix whose columns are the p! p × p permutation matrices.

Contingency tables with quadratic statistics. [S2]

Source status.

The supplied catalogue labels this source record solved; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. This is documentation of a source-labelled solved record, not a newly proposed unsolved problem.

Short English statement

The historical question asks for moves connecting ranking surveys with the same first-order summary.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 20001178 (AIM-COMPUTATION-0016). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 AIM Workshop Problem Lists, source linked by catalogue record AIM-COMPUTATION-0016. https://aimath.org/WWN/compalgstat/compalgstat.pdf.

Verbatim supplied catalogue question

Problem 1. Explicitly describe a Markov basis for tables with fixed first-order summary. That is, describe a set of moves which will connect any two surveys that have the same first order summary. In a purely mathematical language: describe a generating set for the toric ideal given by the p2 × p! matrix whose columns are the p! p × p permutation matrices.

Contingency tables with quadratic statistics.

Exact target and construction

Fix any integer $p\ge1$. A survey is a vector of nonnegative integer permutation multiplicities; zero voters are allowed. No running-time or degree-three restriction occurs in original Problem 1. We construct a finite basis of degree at most $p$. Its enumeration is large and is not claimed efficient. This is a complete rederivation of an elementary known type of solution, not a claim of mathematical novelty. For every $q\in\{1,\ldots,p\}$, enumerate all pairs of multisets of $q$ permutations whose permutation-matrix sums agree, and include their nonzero multiplicity differences as moves (one sign suffices). This is explicit finite enumeration: there are only $p!$ available permutations and finitely many multisets of each bounded cardinality.

Integer regular bipartite decomposition.

Every $r$-regular bipartite multigraph with $p$ vertices on either side, where $r\ge1$, has a perfect matching. Here is the needed matching proof. Take a matching of largest size. If some left vertex is unmatched, form the vertices reachable from it by paths alternating between unmatched edges from left to right and matched edges from right to left. A reached unmatched right vertex would give an augmenting path, contradicting maximal size. Thus all reached right vertices are matched, and their matched partners are reached left vertices; there is one more reached left vertex than reached right vertices. Every edge from a reached left vertex reaches a right vertex, so, writing the two reached sets $S,T$, regularity implies $r|S|\le r|T|$, a contradiction. A perfect matching exists. Removing it leaves an $(r-1)$-regular multigraph. Induction decomposes the multigraph into $r$ perfect matchings. The case $r=0$ is the empty decomposition. Parallel edges are counted with multiplicity throughout, so this proof applies to sums of permutation matrices.

Connectivity theorem and proof.

Let $f,g$ be surveys with the same first-order summary. Their voter counts are equal, since a row sum of the summary is the voter count. Cancel common permutation occurrences. If nothing remains, the surveys agree. Otherwise choose one permutation $\pi$ occurring in the remaining target survey $g$. Every one of its $p$ edges occurs in the summary of the remaining current survey $f$. For each edge choose one permutation occurrence of $f$ containing that edge; take the union of the chosen occurrences, counting any one occurrence only once. This selects $q\le p$ occurrences, with $q\ge1$. Their sum $B$ is entrywise at least $P_\pi$. The matrix $B-P_\pi$ is nonnegative integral with every row and column sum $q-1$. By the preceding decomposition it is a sum of $q-1$ permutation matrices. Replacing the selected $q$ occurrences by $\pi$ and these $q-1$ permutations is one of our moves, or the zero change. It remains nonnegative because only actually present occurrences were removed. Cancel the newly obtained occurrence of $\pi$ against its target occurrence. Repetition decreases the remaining target voter count by at least one and terminates. Every fiber is therefore connected. The empty fiber requires nothing; the zero-voter fiber is a singleton. For $p=1,2$, distinct permutation matrices have independent multiplicities determined by the summary, so all fibers are singletons and the empty nonzero move set is correct.

Generation of the toric ideal.

Use one polynomial variable $X_\pi$ for each ranking and write $X^f$ for its survey monomial. For a permitted move $u=u^+-u^-$ with disjoint nonnegative parts, both $Au^+=Au^-$ and its binomial $X^{u^+}-X^{u^-}\in I_A$ hold by construction. If a nonnegative path step takes $f$ to $g=f-u$, feasibility gives $f-u^+\ge0$ and \[ X^f-X^g=X^{f-u^+}(X^{u^+}-X^{u^-}). \] The opposite move changes only the sign. Telescoping this identity along our connecting path expresses every generating binomial $X^f-X^g$ with $Af=Ag$ in the ideal generated by the displayed finite move set. The reverse containment follows because each move binomial lies in $I_A$. Thus the construction also answers the source's toric-ideal formulation.

Why quadratic moves alone cannot be assumed.

For $p=3$, the three even permutations and the three odd permutations each sum to the all-one $3$ by $3$ matrix. These are the only surveys with that summary: any two chosen disjoint permutations have union a single six-cycle, whose complement is the uniquely remaining permutation; the two one-factorizations are precisely the parity classes. More explicitly, after picking the image of candidate one, its two remaining image choices for candidate two determine the permutation, and pairwise disjointness forces either the three cyclic shifts or their three reversals. These two surveys have disjoint support, so their difference has degree three and no nontrivial degree-two step within this two-point fiber exists. This check prevents an unjustified reduction of our bounded degree-p construction to pairwise swaps.

Context, verification, and scope

The primary AIM question was inspected directly. Its trailing heading about quadratic statistics introduces the next problem and imposes no extra condition on this ranking model. The title's degree-two-and-three claim is not needed: our proved bound is $p$, and no general degree-three theorem is imported. The self-audit checked multiset multiplicities, nonnegative intermediate tables, cancellation, all $p$, and zero voters. No numerical computation, formal proof system, or independent human verification was used. The construction is explicit but deliberately makes no minimality, sparsity of the basis, or polynomial-time enumeration claim.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Full-solution scope declaration

The original target is to produce any explicit finite Markov basis for every complete-ranking first-order-summary model. The degree-$p$ construction and connectivity theorem above cover all sizes and all fibers, including zero voters. The matching lemma is proved completely, so no unverified external theorem is a proof dependency. Neither independent human checking nor formal verification occurred. The original source and supplied research summary were consulted for context; an exhaustive novelty search was not performed. All proofs remain without independent human or formal verification. The result is not claimed new, and the stronger degree-three statement in the catalogue title is outside the original requested specification.

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: 100% The explicit finite move set and nonnegative connectivity proof cover every quantifier of original Problem 1. This is full target coverage by a known-style rederivation, not a novelty assessment. The entire original fixed-first-order-summary Markov-basis question is covered by the explicit finite degree-p move set. No stronger degree-three, minimality, or efficiency claim is made.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• American Institute of Mathematics, Computational Algebraic Statistics, prepared by Seth Sullivant, version 27 March 2004; the original numbered source question and its adjacent scope were inspected on 11 October 2026. https://aimath.org/WWN/compalgstat/compalgstat.pdf.

Final status

Solved in this attempt, as a known-style rederivation. The entire original fixed-first-order-summary Markov-basis question is covered by the explicit finite degree-p move set. No stronger degree-three, minimality, or efficiency claim is made.