\documentclass[11pt,a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern,amsmath,amssymb,amsthm,mathtools}
\usepackage[a4paper,margin=25mm,headheight=15pt]{geometry}
\usepackage{microtype,booktabs,array,enumitem,xcolor,fancyhdr,needspace}
\usepackage[ruled,vlined]{algorithm2e}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,calc,fit,decorations.pathreplacing}
\usepackage[colorlinks=true,linkcolor=blue!40!black,citecolor=blue!40!black,urlcolor=blue!40!black]{hyperref}
\usepackage[nameinlink,noabbrev]{cleveref}
\definecolor{ink}{HTML}{183447}
\definecolor{accent}{HTML}{176B83}
\definecolor{pale}{HTML}{EDF4F6}
\usepackage[font=small,labelfont=bf]{caption}
\setlength{\parindent}{1.2em}
\setlength{\parskip}{2pt plus 1pt}
\setlength{\emergencystretch}{1.5em}
\setlist{nosep,leftmargin=1.7em,topsep=4pt}
\fancypagestyle{maintext}{%
  \fancyhf{}
  \fancyhead[L]{\small An Optimal Deterministic Adversary for Sorting}
  \fancyhead[R]{\small\color{ink}Nicholas Nash}
  \fancyfoot[C]{\thepage}
  \renewcommand{\headrulewidth}{0.3pt}
}
\newcommand{\appendixnotice}{%
  {\small\color{red!70!black}This page contains raw, but Lean verified, AI generated results}%
}
\fancypagestyle{appendixpages}{%
  \fancyhf{}
  \fancyhead[C]{\appendixnotice}
  \fancyfoot[C]{\appendixnotice\\[3pt]\thepage}
  \renewcommand{\headrulewidth}{0.3pt}
}
\pagestyle{maintext}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\vol}{\operatorname{vol}}
\newcommand{\Prb}{\mathbb P}
\newcommand{\E}{\mathbb E}
\newcommand{\R}{\mathbb R}
\newcommand{\ceil}[1]{\left\lceil #1\right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\half}{\tfrac12}
\DeclareMathOperator{\dist}{dist}
\hypersetup{pdftitle={An Optimal Deterministic Adversary for Sorting},pdfauthor={Nicholas Nash},pdfsubject={A deterministic sorting adversary with asymptotically optimal comparison lower bound}}
\title{An Optimal Deterministic Adversary for Sorting}
\author{Nicholas Nash\\[3pt]{\small\href{https://orcid.org/0009-0003-0475-7852}{ORCID: 0009-0003-0475-7852}}}
\date{8 November 2026}
\newcommand{\logtwo}{\log_2}
\begin{document}
\maketitle
\begin{abstract}
This paper describes an optimal \emph{deterministic}, polynomial-time adversary for
ordinary sorting. For any correct sorting algorithm, the adversary forces that
algorithm to make $(1-o(1))n\logtwo n$ comparisons. The best previously known
deterministic polynomial-time adversary forced $\frac{37}{64}n\logtwo n$ comparisons.
The adversary maintains a family of orders consistent with the answers so far,
using a hierarchy of directed acyclic graphs. Bounds on vertex degrees and directed
path lengths allow comparison answers to be chosen through deterministic
calculations on small graph neighborhoods.
\end{abstract}

\section*{Methodological disclosure}
The adversary and its analysis are due to AI (GPT 6 Astra).
The human author shaped the exposition and abstractions, and reviewed
the paper \emph{except for the appendices}.
A Lean formalization is available
\href{https://github.com/nicknash/sorting-adversary-proofs}{here}.
\input{sections/introduction}
\input{sections/related-work}
\input{sections/overview}
\input{sections/legality}
\input{sections/operation-properties}
\input{sections/lower-bound}
\input{sections/implementation}
\input{sections/consequences}
\clearpage
\pagestyle{appendixpages}
\begin{center}
\setlength{\fboxsep}{12pt}
\setlength{\fboxrule}{1pt}
\fcolorbox{red!65!black}{red!4}{%
\begin{minipage}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\raggedright
{\Large\bfseries\color{red!65!black}You are now entering AI-slop-land.\par}
\medskip
\large
The appendices of this paper have not been carefully reviewed by a human.
The main sorting result has been formalized in
\href{https://github.com/nicknash/sorting-adversary-proofs}{Lean}.
\end{minipage}}
\end{center}
\bigskip
\appendix
\input{sections/appendices}
\input{sections/positions}
\input{sections/coupling}
\input{sections/certificates}
\input{sections/execution}
\input{sections/arithmetic}
\input{sections/parameters}
\input{sections/consequences-proofs}
\clearpage
\pagestyle{maintext}
\input{sections/references}
\end{document}