← All problems

Latin-strategy characterization conjecture for the symmetric group

6 years old · traced to

Let Sn\mathbb{S}_n be the symmetric group on nn elements. A Latin strategy is obtained by choosing an n×nn\times n Latin square SS; Alice's message identifies a row of SS that agrees with the input permutation at the maximum possible number of positions. An optimal strategy is one attaining the maximum success probability.

Latin-strategy characterization conjecture. Optimal strategies are exactly Latin strategies.

This conjecture proposes a complete characterization of optimal strategies, extending the explicitly described shift strategies. The paper states it as an open question and does not prove the characterization.

References
  1. Artur Czumaj, George Kontogeorgiou and Mike Paterson, “Haystack Hunting Hints and Locker Room Communication”, arXiv:2008.11448 (2021).

Progress summary

Refreshed
Open · progress reported

No independently verified resolution has appeared; an unverified submission claims a five-element counterexample to the conjecture.

The conjecture says that the optimal strategies for the symmetric group are exactly those arising from Latin squares. The catalogued paper treated this characterization as open in August 2020.

Community submission (unverified), November 7, 2026

A submitted argument claims that, at n=5n=5, a Latin maximum-agreement strategy is not optimal for the stated finite-field objective, with claimed values 290<302290<302. If its scope and proof are correct, this would refute the Latin-implies-optimal direction; the submission is not independently verified here.

Current status (as of November 2026): The characterization remains unsettled; an unverified submission claims a counterexample at n=5n=5, but no independently assessed resolution or refutation is recorded.

Sources

Solutions 1

A Latin maximum-agreement strategy that is not optimal for the finite field objectiveSee full solutionHide full solution

Result and scope. Refutes the universal Latin-implies-optimal direction of the source Definition3 finite field characterization: two nonempty Latin maximum-agreement partitions at n=5 have actual fields290<302. MathDB347712 is interpreted through its explicit source Definition3.

Complete proof: A Latin maximum-agreement strategy that is not optimal for the finite field objective · PDF.

The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.

This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.