\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern,amsmath,amssymb,amsthm,mathtools}
\usepackage[margin=27mm]{geometry}
\usepackage{hyperref,microtype}
\hypersetup{colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue,
pdftitle={Degree Transport and a Smaller Cubic Coefficient for Reset Thresholds},
pdfauthor={HONG SUNGBIN}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{remark}\newtheorem{remark}[theorem]{Remark}
\newcommand{\rt}{\operatorname{rt}}
\newcommand{\corank}{\operatorname{corank}}
\newcommand{\al}{\frac{8257}{49923}}
\title{Degree Transport and a Smaller Cubic Coefficient\\for Reset Thresholds}
\author{HONG SUNGBIN\thanks{Human submitting contributor. The research and text were primarily generated by AI; no human verification or understanding of the proof is claimed. See Section~\ref{sec:provenance}.}\\[3pt]
\small Department of Electrical and Electronic Engineering\\
\small Faculty of Engineering, The University of Tokyo\\
\small\href{mailto:hongsungbin2@g.ecc.u-tokyo.ac.jp}{\texttt{hongsungbin2@g.ecc.u-tokyo.ac.jp}}\\
\small ORCID: \href{https://orcid.org/0009-0005-6165-714X}{0009-0005-6165-714X}}
\date{5 November 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove that every synchronizing complete deterministic finite automaton
on $n\ge2$ states has reset threshold at most
\[
 \frac{8242}{49923}n^3+O(n^2).
\]
The cubic coefficient improves on Shitov's $8257/49923$ by $5/16641$.
The main ingredient is a degree-transport inequality for graphs of state
pairs mergeable by short words. It relates a long gap between consecutive
minimum-rank word lengths to a large corank achievable in at most $n-1$
letters. Combining this relation with a discrete dual of Shitov's counting
argument gives the improvement. An appendix makes the quadratic remainder
explicit for every $n\ge2$. The argument applies to arbitrary finite
alphabets and does not prove the quadratic \v{C}ern\'y conjecture.
\end{abstract}
\medskip
\noindent\textit{2020 Mathematics Subject Classification.} 68Q70.
\quad\textit{Keywords.} Synchronizing automaton, reset threshold,
\v{C}ern\'y conjecture, merge graph, avoiding word.


\section{Introduction and main result}
Let $\mathcal A=(Q,\Sigma,\delta)$ be a complete deterministic finite
automaton, $|Q|=n$. Words act on the right. The rank of a word $w$ is
$|Qw|$ and its corank is $n-|Qw|$. The reset threshold $\rt(\mathcal A)$
is the minimum length of a rank-one word. All constants in $O(\cdot)$
below are absolute and uniform over automata and alphabet sizes.

\begin{theorem}\label{thm:main}
Every synchronizing complete deterministic finite automaton with
$n\ge2$ states satisfies
\[
 \rt(\mathcal A)\le \frac{8242}{49923}n^3+O(n^2).
\]
\end{theorem}

The comparison coefficient is Shitov's
\[
 \alpha=\frac7{48}+\frac{15625}{798768}=\frac{8257}{49923}.
\]
The August 2026 survey \cite[Section 2.1]{survey} records this as the
best known general cubic coefficient. The coefficient difference is
\[
 \alpha-\frac{8242}{49923}=\frac5{16641}
       =0.000300462712577\ldots .
\]
The contribution is the transport inequality in Lemma~\ref{lem:transport}
and its use in the two-case argument of Section~4.
Appendix~\ref{explicit:appendix} gives an explicit uniform bound for the
quadratic remainder, valid for every $n\ge2$. A smaller leading coefficient is an
asymptotic improvement and does not imply a better numerical bound for
every small $n$. No optimality or exhaustive priority claim is made.

For $0\le j\le n-1$, let $\lambda_j$ be the minimum length of a word
of corank at least $j$. Set $\lambda_n=+\infty$ and
$\delta_j=\lambda_{j+1}-\lambda_j$. Thus $\lambda_0=0$ and
$\lambda_{n-1}=\rt(\mathcal A)$. If $\delta_j>0$, every minimum
$\lambda_j$ word has corank exactly $j$.
In Sections~2--4, assume that $\mathcal A$ is strongly connected.
Write
\[
 h=n-1,\qquad D=\max\{\corank(w):|w|\le h\}.
\]
In particular $\lambda_D\le n-1$.

\section{Transport in the merge graph}
For an integer $t\ge0$, let $E_t$ be the simple graph on $Q$ with an edge
$xy$, $x\ne y$, precisely when a word of length at most $t$ merges $x,y$.
Let $\Delta_t$ and $m_t$ be its maximum and minimum degrees.

\begin{lemma}[Degree transport]\label{lem:transport}
For every $t\ge0$,
\[
 D\ge \Delta_t-m_{t+h}.
\]
\end{lemma}
\begin{proof}
Choose $c$ with degree $\Delta_t$ in $E_t$, and $q$ with degree
$m_{t+h}$ in $E_{t+h}$. There is a word $u$ of length at most $h$
taking $q$ to $c$. If $y\in Qu\cap N_{E_t}(c)$, select a preimage
$z$ with $zu=y$. A word of length at most $t$ merges $c,y$, so its
concatenation after $u$ merges $q,z$ in length at most $t+h$.
Here $z\ne q$, and distinct $y$ require distinct $z$.
Consequently $|Qu\cap N_{E_t}(c)|\le m_{t+h}$. The image $Qu$ therefore
omits at least $\Delta_t-m_{t+h}$ states. Its corank is at most $D$.
\end{proof}

\begin{lemma}\label{lem:plateaugraphs}
Fix $1\le r<n/2$ and $L=\delta_r>0$. For every integer $0\le t<L$,
$E_t$ has a vertex cover of size $r$, and
\[
 (n-r)m_t\le r\Delta_t,\qquad |E_t|\ge t,\qquad
 \Delta_t\ge \frac tr.
\]
\end{lemma}
\begin{proof}
The image $S$ of a minimum $\lambda_r$ word has size $n-r$ and is
independent in $E_t$: otherwise a suffix of length at most $t<L$
would give corank at least $r+1$ before $\lambda_{r+1}$.
Thus $Q\setminus S$ is a cover of size $r$. Summing degrees over $S$
shows $(n-r)m_t\le r\Delta_t$.

Let $v$ be a shortest word compressing $S$, with length $\ell$.
Then $\ell\ge L$. Some pair in $S$ merged by $v$ has pair distance
exactly $\ell$, for a shorter merging word would compress $S$.
Along $v$ its successive pair distances are exactly
$\ell,\ell-1,\ldots,1$: a smaller distance at any point would shorten
the original merging word. Thus for every distance $1,\ldots,t$
there is a distinct edge of $E_t$. This proves $|E_t|\ge t$.
Every edge meets the cover, so $|E_t|\le r\Delta_t$.
\end{proof}

\begin{lemma}[An exact plateau inequality]\label{lem:exact}
For every positive integer $M$ and $1\le r<n/2$,
\[
 \delta_r\le
 \frac{r(n-r)}{n-2r}D+
 \frac{r^2}{n-2r}\frac{n-1}{M}+M(n-1)+1.
 \tag{1}\label{eq:exact}
\]
\end{lemma}
\begin{proof}
The assertion is immediate if $\delta_r\le M(n-1)+1$.
Otherwise put $L=\delta_r$, $k=n-r$, $q=r/k$, and
$t_j=L-1-(M-j)h$, $0\le j\le M$.
All these horizons are nonnegative and less than $L$. Lemmas
\ref{lem:transport} and \ref{lem:plateaugraphs} give
\[
 D\ge \Delta_{t_j}-m_{t_{j+1}}
   \ge \Delta_{t_j}-q\Delta_{t_{j+1}}\quad(0\le j<M).
\]
The degrees are nondecreasing with the horizon. Summing and using
$\Delta_{t_M}\le n-1$ gives
\[
 MD\ge (1-q)\sum_{j=0}^{M-1}\Delta_{t_j}
           +q\Delta_{t_0}-q\Delta_{t_M}
 \ge M(1-q)\Delta_{t_0}-q(n-1).
\]
As $\Delta_{t_0}\ge t_0/r$, this becomes
\[
 D\ge\frac{n-2r}{r(n-r)}(L-1-Mh)
       -\frac{r(n-1)}{(n-r)M}.
\]
Rearranging proves \eqref{eq:exact}.
\end{proof}

\begin{corollary}\label{cor:band}
If $D<n/50$, then uniformly for $n/3\le r\le9n/20$,
\[
 \delta_r\le \frac{(r+1)(r+2)}2
                   -\frac1{10}(3r-n)n+400n+1.
 \tag{2}\label{eq:band}
\]
\end{corollary}
\begin{proof}
The two coefficient functions in \eqref{eq:exact} are increasing with
$r/n$ on this interval and attain $99n/40$ and $81n/40$,
respectively, at its right endpoint. With $M=400$ this gives
\[
 \delta_r\le\frac{99}{40}nD+\frac{81}{16000}n(n-1)
                +400(n-1)+1
 \le\frac{873}{16000}n^2+400n+1.
\]
For $x\in[1/3,9/20]$, the function
$x^2/2-(3x-1)/10$ is increasing, since its derivative is $x-3/10>0$.
Its minimum is $1/18$, and
\[
 \frac1{18}-\frac{873}{16000}=\frac{143}{144000}>0.
\]
Since $(r+1)(r+2)/2\ge r^2/2$, this proves \eqref{eq:band}.
\end{proof}

\section{The compression framework and its discrete dual}
We use two established bounds. Pin--Frankl \cite{frankl,pin} gives
\[
 \delta_r\le P_r:=\frac{(r+1)(r+2)}2\quad(0\le r\le n-2).
 \tag{3}\label{eq:pf}
\]
Let
\[
 \rho=\min\{j:\delta_j>n\},\qquad m=\lfloor n/2\rfloor .
\]
Then $\lambda_\rho\le\rho n<n^2$. For $j<\rho$ the gaps are in $[0,n]$.
Let $s_i$ count those $j<\rho$ with
$\delta_j\in\{2i-1,2i\}$, and put $G_r=\sum_{i\le r}i s_i$.
Zero gaps are not counted, so $\sum_i s_i\le\rho$.
Shitov's avoiding-word construction \cite[Theorems 2 and 5]{shitov},
building on Szyku\l a's avoiding-word method \cite{szykula2018},
implies
\[
 \delta_r\le 2G_r+2r\quad(\rho\le r<m).
 \tag{4}\label{eq:shitov}
\]
Indeed choose the first $\tau$ with $\delta_\tau>2r$.
Then $\tau\le\rho$, $\lambda_\tau\le2G_r$, and the singleton-fiber
avoidance argument prepends a word of length at most
$\lambda_\tau+2r$ to a minimum corank-$r$ target. If $\delta_r=0$
the bound is automatic. This step needs no strong connectivity.

For $\rho\le r<m$, define
\[
 z_r=\frac{\delta_r}{2}-r-1,\qquad A_r=\frac{r^2}{4}.
\]
Equations \eqref{eq:pf}--\eqref{eq:shitov} imply
$z_r\le A_r$ and $z_r\le G_r$. The $z_r$ may be negative.
Summing gaps and using \eqref{eq:pf} after $m$ gives
\[
 \rt(\mathcal A)\le \frac7{48}n^3+
                 2\sum_{r=\rho}^{m-1}z_r+O(n^2)
 \quad(\rho<m).
 \tag{5}\label{eq:reset}
\]

Set
\[
 \beta=\frac{25}{129},\quad
 \gamma=\frac{125}{258},\quad
 \mu=\frac{\beta^2}{5}=\gamma(1/2-\gamma)=\frac{125}{16641},\quad
 \mathcal M=\frac{15625}{1597536}.
\]
Suppose $\beta n/2\le\rho\le\gamma n$ and put
$g=\lfloor\gamma n\rfloor$, $\mu_n=g(m-g)$.
For sufficiently large $n$, $\rho\le g<m$. Define
\[
 b_r=\begin{cases}\mu_n/[r(r+1)],&r<g,\\1,&r\ge g,\end{cases}
 \qquad a_r=1-b_r .
\]
These are in $[0,1]$ uniformly in this range, since
$\mu/(\beta/2)^2=4/5<1$.
For every bin index $i$,
\[
 B_i=i\sum_{r=\max(\rho,i)}^{m-1}b_r
 \le\mu_n\min(1,i/\rho).
 \tag{6}\label{eq:bins}
\]
For $\rho\le i\le g$, telescoping gives $B_i=\mu_n$;
for $i<\rho$, it gives $B_i=i\mu_n/\rho$.
For $g<i<m$, $B_i=i(m-i)\le g(m-g)$, as $g>m/2$.
For $i\ge m$, $B_i=0$.

Define the nonnegative mass defect
\[
 P=\rho-\sum_i\min(1,i/\rho)s_i .
\]
Multiplying the two bounds on $z_r$ by $a_r,b_r$ gives the exact dual
estimate
\[
 \sum_{r=\rho}^{m-1}z_r
 \le D_n(\rho)-\mu_nP
              -\sum_{r=\rho}^{m-1}a_r(A_r-z_r),
 \tag{7}\label{eq:dual}
\]
where
\[
 D_n(\rho)=\mu_n\rho+
 \sum_{r=\rho}^{g-1}
       \left(1-\frac{\mu_n}{r(r+1)}\right)\frac{r^2}{4}.
\]
Here \eqref{eq:bins} bounds $\sum b_rG_r$ by $\mu_n(\rho-P)$.

Uniformly for $\beta/2\le x=\rho/n\le\gamma$,
\[
 D_n(\rho)=n^3F(x)+O(n^2),\qquad
 F(x)=\frac{5\mu x}{4}-\frac{x^3}{12}
                 +\frac{\gamma^3}{12}-\frac{\mu\gamma}{4}.
 \tag{8}\label{eq:F}
\]
To see the uniform error, use $\mu_n=\mu n^2+O(n)$ and
\[
 D_n(\rho)=\frac{\mu_n(5\rho-g)}4+
                 \frac14\sum_{r=\rho}^{g-1}r^2+
                 \frac{\mu_n}4\sum_{r=\rho}^{g-1}\frac1{r+1}.
\]
The last harmonic sum is uniformly bounded, since $\rho\ge\beta n/2$.
Furthermore $F'(x)=(5\mu-x^2)/4$ and $5\mu=\beta^2$.
Thus $F$ is maximized at $\beta$, with $F(\beta)=\mathcal M$.
In particular \eqref{eq:dual} yields
\[
 \sum z_r\le\mathcal M n^3-\mu_nP
                   -\sum a_r(A_r-z_r)+O(n^2).
 \tag{9}\label{eq:central}
\]

\section{The two cases and all outer ranges}
First consider the central range
\[
 \beta n/2\le\rho\le n/3.
\]
The maximum short-word corank satisfies $D\le\rho$:
if $D>\rho$ then
$\lambda_D\ge\lambda_{\rho+1}>\lambda_\rho+n\ge n$,
contrary to $\lambda_D\le n-1$.
The first $D$ gaps therefore occur among the pre-$\rho$ gaps.
A positive gap $\delta_j$ has bin index
$\lceil\delta_j/2\rceil\le(\delta_j+1)/2$.
In the expression defining $P$, its defect contribution is at least
$1-(\delta_j+1)/(2\rho)$; a zero gap contributes one.
All remaining contributions are nonnegative. Consequently
\[
 P\ge D-\frac{\lambda_D+D}{2\rho}
       \ge D-\frac{n-1+D}{2\rho}=D-O(1),
 \tag{10}\label{eq:cheapmass}
\]
uniformly in the central range.

If $D\ge n/50$, equations \eqref{eq:reset}, \eqref{eq:central}
and \eqref{eq:cheapmass} give
\[
 \rt(\mathcal A)\le
 \left(\alpha-\frac{\mu}{25}\right)n^3+O(n^2)
 =\frac{8242}{49923}n^3+O(n^2).
 \tag{11}\label{eq:highD}
\]
Here $\mu_n=\mu n^2+O(n)$ and $\mu/25=5/16641$.

If $D<n/50$, apply Corollary \ref{cor:band} on
$I_n=\{r:n/3\le r\le9n/20\}$, which lies between $\rho$ and $g$
for sufficiently large $n$. It implies
\[
 A_r-z_r\ge\frac1{20}(3r-n)n-O(n)
          \quad(r\in I_n).
\]
The error is uniform. On this band,
$a_r\ge1-9\mu+O(1/n)$. The other cap deficits are nonnegative, so
\[
 2\sum a_r(A_r-z_r)
 \ge\frac1{10}(1-9\mu)n^3
         \int_{1/3}^{9/20}(3x-1)\,dx+O(n^2)
 =\frac{21119}{11094000}n^3+O(n^2).
 \tag{12}\label{eq:lowD}
\]
An $O(n^2)$ term in a lower bound denotes a quantity bounded in
absolute value by a uniform constant times $n^2$.
The coefficient in \eqref{eq:lowD} is strictly greater than $\mu/25$.
Equations \eqref{eq:reset} and \eqref{eq:central} again give
\eqref{eq:highD}.

For completeness, every remaining $\rho$ range already has a larger
cubic deficit, so no central-case assumption is left unproved.
If $\rho<\beta n/2$, use $z_r\le G_r$ to get
\[
 \sum_{r=\rho}^{m-1}z_r
 \le\sum_i i(m-\max(\rho,i))_+s_i
 \le\frac{m^2}{4}\rho\le\frac{\rho n^2}{16}.
\]
Thus the deficit from $\alpha$ in \eqref{eq:reset} is at least
\[
 2\mathcal M-\frac{\beta}{16}
        =\frac{2975}{399384}>\frac{\mu}{25}.
\]
If $n/3<\rho\le\gamma n$, use \eqref{eq:F} and the fact that $F$
decreases after $\beta$. The deficit is at least
\[
 2(F(\beta)-F(1/3))=\frac{186}{79507}>\frac{\mu}{25}.
\]
Integer roundings change these estimates by $O(n^2)$ only.
Finally if $\rho\ge\gamma n$, use Pin--Frankl directly after
$\lambda_\rho<n^2$. It gives
\[
 \rt(\mathcal A)\le \frac{1-(\rho/n)^3}{6}n^3+O(n^2)
 \le \frac{1-\gamma^3}{6}n^3+O(n^2).
\]
The resulting deficit is
\[
 \alpha-\frac{1-\gamma^3}{6}
       =\frac{1822061}{103041072}>\frac{\mu}{25}.
\]
This includes $\rho\ge m$. Appendix~\ref{explicit:appendix} replaces
these uniform error terms by numerical bounds and covers all small $n$.

\section{Removing strong connectivity}
A synchronizing automaton has exactly one closed strongly connected
component $C$: two disjoint closed components could never be merged.
Let $s=|C|$. Every state outside $C$ reaches $C$ along a path of length
at most $n-s$. Starting from the current image, choose an outside state
and append such a path. States already in $C$ remain there, and the
number of outside image states decreases by at least one.
After at most $n-s$ repetitions, a word of length at most $(n-s)^2$
maps $Q$ into $C$.

The automaton restricted to $C$ is strongly connected and synchronizing.
The proved bound there, followed after this entering word, gives
\[
 \rt(\mathcal A)\le(n-s)^2+\frac{8242}{49923}s^3+O(s^2)
 \le\frac{8242}{49923}n^3+O(n^2).
\]
For $s=1$ the reset suffix is empty. This completes the proof of
Theorem~\ref{thm:main} for arbitrary synchronizing complete automata.
Appendix~\ref{explicit:appendix} supplies an explicit quadratic remainder.

\section{Reproducibility and AI provenance}\label{sec:provenance}
\paragraph{Mathematical and computational evidence.}
The universal argument is the written proof above, using the cited
Pin--Frankl and Shitov bounds. The ancillary files contain standard-library
Python scripts and their outputs. The script \texttt{verify.py} checks
exact rational identities and 216 finite dual and cheap-prefix profiles.
The script \texttt{verify\_degree\_transport.py} enumerates all labelled
binary transition tables on $2$, $3$, and $4$ states, filters for strong
connectivity and synchronization, computes pair distances by breadth-first
search, and computes $D$ by subset breadth-first search. The resulting
18,894 automata and 76,476 integer-horizon checks have no violations of
Lemma~\ref{lem:transport}. The script
\texttt{verify\_explicit\_constant.py} checks 16 exact rational guards
used in Appendix~\ref{explicit:appendix}. All three scripts were rerun
with Python 3.14.7 for this version. These finite diagnostics are not
formal proofs of the universal statements.

\paragraph{Generation and revision.}
OpenAI Codex, using the model label \texttt{6.1 sol}, performed the
literature searches, exploratory calculations, proof development,
programming, and primary drafting in October 2026. This November 2026
revision used OpenAI Codex with the model label \texttt{6 astra} to revise
the manuscript, derive an explicit quadratic remainder, and repeat the
checks. A review generated by Google Gemini with the model label
\texttt{Gemini 3.1 Pro}, and supplied by the human contributor, was used
as editorial input; its settings were not supplied. These model labels
were reported by the human submitting contributor and have not been
independently verified as provider snapshot identifiers. The review
comments were not treated as a proof certificate. Separate AI review
passes examined the graph argument, the scalar dual, boundary cases,
the explicit remainder, and the bibliography. Such passes can share
systematic errors and do not constitute human peer review or independent
formal verification.

\paragraph{Human contribution and understanding.}
HONG SUNGBIN directed the research request, supplied the Gemini comments,
and requested preparation of this submission. The text and mathematical
development are primarily AI-generated. The submitting contributor makes
no claim of having personally checked and understood any part of the
proof; the corresponding human-understanding declaration is \emph{none}.
AI systems are disclosed as tools, not named as contributors.

\paragraph{Verification limits.}
No proof-assistant verification or external human peer review has been
performed. The cited survey supports the comparison with Shitov's bound;
the literature search is not an exhaustive priority certification.
This version contains neither a proof of the quadratic \v{C}ern\'y
conjecture nor a claim that repository acceptance certifies correctness.
The ancillary JSON file \texttt{ai\_usage.json} records the tool roles,
declared human understanding, reproduction commands, and check scope.

\appendix
\numberwithin{equation}{section}
\section{An explicit quadratic remainder}\label{explicit:appendix}
This appendix gives an explicit uniform choice for the quadratic remainder
in Theorem~\ref{thm:main} by replacing the asymptotic errors with numerical
bounds. The constant is deliberately conservative, chosen for simplicity,
and not optimized. Put $c=8242/49923$, $d_0=\mu/25=5/16641$, and retain the
notation of the proof above.

\begin{lemma}[Explicit remainder]\label{explicit:remainder}
Every synchronizing complete DFA with $n\ge2$ states satisfies
\[
 \rt(\mathcal A)\le c n^3+500n^2.
\]
\end{lemma}
\begin{proof}
We first treat strongly connected automata with $n\ge10000$.
The following bounds hold uniformly whenever
$\beta n/2\le\rho\le\gamma n$:
\begin{equation}\label{explicit:floor}
 |\mu_n-\mu n^2|\le n+1,\qquad
 0\le b_r\le1,\qquad
 D_n(\rho)\le n^3F(\rho/n)+2n^2.
\end{equation}
Here is explicit justification of the rounding and admissibility claims.
Write $g=\gamma n-\theta$ and $m=n/2-\eta$, with
$0\le\theta,\eta<1$. Then
\[
 \mu_n-\mu n^2
 =\bigl((2\gamma-1/2)\theta-\gamma\eta\bigr)n
       +\theta\eta-\theta^2.
\]
The absolute value is at most $n+1$. Also $g<m$, $g>m/2$, and
$\mu n^2-n-1>0$ for $n\ge10000$. For $r\ge\rho$ and $r<g$,
\[
 b_r\le \frac{\mu n^2+n+1}{\beta^2n^2/4}
 =\frac45+\frac{4(n+1)}{\beta^2n^2}<\frac9{10}.
\]
The last rational inequality holds at $n=10000$ and its extra term
decreases thereafter. The other $b_r$ equal one.

To bound $D_n$, use its exact expansion in the main proof. Since
$0\le5\rho-g\le2n$,
\[
 \frac{\mu_n(5\rho-g)}4
 \le\frac{\mu n^2(5\rho-\gamma n)}4
       +\frac{n(n+1)}2+\frac{\mu n^2}4.
\]
The square sum is at most
$((\gamma n)^3-\rho^3)/3$, by comparison with the integral of $x^2$.
The harmonic sum is at most
$\log(g/\rho)\le\log5<2$.
The error in $D_n$ is consequently at most
\[
 \left(\frac12+\frac{3\mu}{4}\right)n^2+n+\frac12<2n^2,
\]
proving \eqref{explicit:floor}.

The reset-length bookkeeping also has the uniform explicit form
\begin{equation}\label{explicit:reset}
 \rt(\mathcal A)\le\frac7{48}n^3
       +2\sum_{r=\rho}^{m-1}z_r+3n^2\qquad(\rho<m).
\end{equation}
Indeed $\lambda_\rho<n^2$, the normalizing sum
$\sum_{r=\rho}^{m-1}(2r+2)$ is at most $m(m+1)\le n^2$,
and the Pin--Frankl tail is
\[
 \sum_{r=m}^{n-2}P_r
 =\frac{n^3-n-m(m+1)(m+2)}6\le\frac7{48}n^3.
\]
For the last inequality, $m(m+1)(m+2)\ge n^3/8$ for both parities
of $n\ge2$. Thus even $2n^2$ would suffice in
\eqref{explicit:reset}; we retain the looser allowance.

In the central range $\beta n/2\le\rho\le n/3$, the exact mass bound
and $D\le\rho$ give
\[
 P\ge D-\frac{n-1+D}{2\rho}
   \ge D-\frac1\beta-\frac12>D-6.
\]
If $D\ge n/50$, both $n/50-6$ and $\mu n^2-n-1$ are positive.
Therefore
\begin{align*}
 2\mu_nP
 &\ge2(\mu n^2-n-1)(n/50-6)\\
 &\ge d_0n^3-\left(12\mu+\frac1{25}\right)n^2
 \ge d_0n^3-n^2.
\end{align*}
The dual estimate, \eqref{explicit:floor}, and
\eqref{explicit:reset} now give
\begin{equation}\label{explicit:largeD}
 \rt(\mathcal A)\le c n^3+8n^2.
\end{equation}

Suppose instead that $D<n/50$. Write
$I_n=\{\lceil n/3\rceil,\ldots,\lfloor9n/20\rfloor\}$ and
$a_0=1-9\mu$. For $n\ge10000$ this band is contained in
$\{\rho,\ldots,g-1\}$. On it,
\[
 a_r\ge a_0-\frac{10}{n},\qquad
 2(A_r-z_r)\ge H_r-400n,
 \quad H_r=\frac1{10}(3r-n)n\ge0.
\]
The first inequality follows from
$\mu_n/[r(r+1)]\le9\mu+9(n+1)/n^2$.
The second follows directly from \eqref{eq:band} and the definition
of $z_r$; the discarded extra term is $r/2\ge0$.

For explicit control of the sum, the increasing function
$H(t)=(3t-n)n/10$ satisfies
\[
 \sum_{r\in I_n}H_r
 \ge\int_{n/3}^{9n/20}H(t)\,dt-H(9n/20)
 \ge\frac{n^3}{10}\int_{1/3}^{9/20}(3x-1)\,dx-n^2.
\]
To justify the first inequality, integrate up to
$\lfloor9n/20\rfloor$ and compare each interval with its right-endpoint
summand; the omitted terminal interval has length less than one.
We also have $|I_n|\le n$ and
$\sum_{r\in I_n}H_r\le(7/200)n^3$.
Using $0\le a_r\le1$ and nonnegative cap deficits outside the band,
\begin{align*}
 2\sum_{r=\rho}^{m-1}a_r(A_r-z_r)
 &\ge a_0\sum_{r\in I_n}H_r
       -\frac{10}{n}\sum_{r\in I_n}H_r-400n|I_n|\\
 &\ge K n^3-402n^2,
 \qquad K=\frac{21119}{11094000}>d_0.
\end{align*}
Here $0<a_0<1$ and $10(7/200)=7/20$, so the total quadratic loss
is smaller than $402n^2$. It follows that
\begin{equation}\label{explicit:smallD}
 \rt(\mathcal A)\le(\alpha-K)n^3+409n^2
                  \le c n^3+409n^2.
\end{equation}

The outer ranges require smaller allowances. When $\rho<\beta n/2$,
the direct count estimate and \eqref{explicit:reset} give
\[
 \rt(\mathcal A)\le
  \left(\alpha-\frac{2975}{399384}\right)n^3+3n^2.
\]
When $n/3<\rho\le\gamma n$, use \eqref{explicit:floor} and
the nonnegative dual penalties to obtain
\[
 \rt(\mathcal A)\le
  \left(\alpha-\frac{186}{79507}\right)n^3+7n^2.
\]
Finally, for $\rho\ge\gamma n$, the exact Pin--Frankl tail after
$\lambda_\rho<n^2$ gives
\[
 \rt(\mathcal A)\le\frac{1-\gamma^3}{6}n^3+n^2
 =\left(\alpha-\frac{1822061}{103041072}\right)n^3+n^2.
\]
Each of these three subtractions is greater than $d_0$.
Thus all strongly connected cases with $n\ge10000$ are bounded by
$c n^3+500n^2$.

For $2\le n<10000$, the ordinary Pin--Frankl bound gives
\[
 \rt(\mathcal A)\le\frac{n^3-n}{6}
 \le c n^3+16n^2,
 \qquad
 10000\left(\frac16-c\right)
 =\frac{1570000}{99846}<16.
\]
This argument does not require strong connectivity.

For a general automaton whose unique closed strongly connected component
has $s$ states, use the entering word of length at most $(n-s)^2$
from the main proof. If $s\ge2$, the established bound on that component
gives
\[
 \rt(\mathcal A)\le(n-s)^2+c s^3+500s^2
                    \le c n^3+500n^2,
\]
because $(n-s)^2\le n^2-s^2\le500(n^2-s^2)$ and $c>0$.
If $s=1$, the entering word itself resets the automaton and has length
at most $(n-1)^2$. This completes the explicit all-$n$ proof.
\end{proof}

\clearpage
\begin{thebibliography}{9}
\bibitem{frankl}
P.~Frankl, An extremal problem for two families of sets,
\emph{European Journal of Combinatorics} \textbf{3} (1982), 125--127.
\href{https://doi.org/10.1016/S0195-6698(82)80025-5}{doi:10.1016/S0195-6698(82)80025-5}.
\bibitem{pin}
J.-E.~Pin, On two combinatorial problems arising from automata theory,
in \emph{Combinatorial Mathematics}, North-Holland Mathematics Studies
\textbf{75} (1983), 535--548.
\href{https://doi.org/10.1016/S0304-0208(08)73432-7}{doi:10.1016/S0304-0208(08)73432-7}.
\bibitem{shitov}
Y.~Shitov, An improvement to a recent upper bound for synchronizing words
of finite automata, \emph{Journal of Automata, Languages and Combinatorics}
\textbf{24} (2019), 367--373.
\href{https://arxiv.org/abs/1901.06542}{arXiv:1901.06542};
\href{https://doi.org/10.25596/jalc-2019-367}{doi:10.25596/jalc-2019-367}.
\bibitem{szykula2018}
M.~Szyku\l a, Improving the upper bound on the length of the shortest reset
word, in \emph{STACS 2018}, LIPIcs \textbf{96}, 56:1--56:13 (2018).
\href{https://doi.org/10.4230/LIPIcs.STACS.2018.56}{doi:10.4230/LIPIcs.STACS.2018.56}.
\bibitem{survey}
M.~Szyku\l a, Synchronizing automata: Open problems,
\emph{EPTCS} \textbf{451} (2026), 33--47.
\href{https://arxiv.org/abs/2608.24245}{arXiv:2608.24245};
\href{https://doi.org/10.4204/EPTCS.451.3}{doi:10.4204/EPTCS.451.3}.
\end{thebibliography}
\end{document}