Latin-strategy characterization conjecture for the symmetric group
Let be the symmetric group on elements. A Latin strategy is obtained by choosing an Latin square ; Alice's message identifies a row of 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
- Artur Czumaj, George Kontogeorgiou and Mike Paterson, “Haystack Hunting Hints and Locker Room Communication”, arXiv:2008.11448 (2021).
Progress summary
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 , a Latin maximum-agreement strategy is not optimal for the stated finite-field objective, with claimed values . 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 , 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 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.