\documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{lmodern,microtype} \usepackage[a4paper,margin=29mm]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{booktabs,longtable,array} \usepackage[dvipsnames]{xcolor} \usepackage[colorlinks=true,linkcolor=MidnightBlue,citecolor=MidnightBlue,urlcolor=MidnightBlue]{hyperref} \usepackage[nameinlink,noabbrev]{cleveref} % Explicit reference names and label types keep shared theorem counters portable. \crefname{theorem}{theorem}{theorems} \Crefname{theorem}{Theorem}{Theorems} \crefname{lemma}{lemma}{lemmas} \Crefname{lemma}{Lemma}{Lemmas} \crefname{proposition}{proposition}{propositions} \Crefname{proposition}{Proposition}{Propositions} \crefname{corollary}{corollary}{corollaries} \Crefname{corollary}{Corollary}{Corollaries} \hypersetup{pdftitle={A uniform 7/48 cubic upper bound for reset thresholds}, pdfauthor={Sungbin Hong},pdfsubject={Synchronizing automata and reset thresholds}} \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\rt}{\operatorname{rt}} \newcommand{\rk}{\operatorname{rk}} \newcommand{\corank}{\operatorname{corank}} \newcommand{\NN}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\pos}[1]{\left[#1\right]_+} \newcommand{\PF}{\operatorname{PF}} \newcommand{\de}{\mathrm d} \newcommand{\lean}[1]{{\small\texttt{\detokenize{#1}}}} \DeclareMathOperator{\im}{im} \title{A uniform $7/48$ cubic upper bound for reset thresholds} \author{Sungbin Hong\\[3pt] \small Department of Electrical and Electronic Engineering\\ \small Faculty of Engineering, The University of Tokyo\\ \small Tokyo, Japan\\ \small\href{mailto:hongsungbin2@g.ecc.u-tokyo.ac.jp}{\texttt{hongsungbin2@g.ecc.u-tokyo.ac.jp}}} \date{November 13, 2026} \begin{document} \maketitle \begin{abstract} We prove that every complete synchronizing deterministic finite automaton $A$ with $n$ states satisfies $\rt(A)\le\frac{7}{48}n^3+o(n^3)$, uniformly over the automaton and its finite alphabet. The coefficient is the milestone proposed in Trahtman's 2011 half-rank approach. The argument fixes a short word whose kernel is stable over a dyadic length interval. Degree transport in the graphs of pairs mergeable by short words, combined with a simultaneous selection of times of small degree growth, gives a compression bound for every sufficiently large subset of states. The bound remains available after replacing the current word. We combine it with the cheap-gap construction and the Pin--Frankl rank upgrade: the cost of reaching half rank is paid by a saving in the subsequent rank reductions. The required scalar comparison has an elementary analytic proof over its entire parameter domain. An explicit two-parameter estimate proves uniformity and extends the result from strongly connected automata to arbitrary complete synchronizing automata. The full theorem, including the word constructions used as classical inputs, has also been formalized in Lean~4. \end{abstract} \noindent\textbf{Keywords.} Synchronizing automaton; reset threshold; \v{C}ern\'y conjecture; degree transport; formal proof.\\ \textbf{2020 Mathematics Subject Classification.} 68Q70, 05C35. \section{Introduction} A reset word of a deterministic finite automaton sends all states to one state. The least length of such a word is its reset threshold. The \v{C}ern\'y conjecture predicts the bound $(n-1)^2$ for every synchronizing automaton with $n$ states. Our result concerns the cubic upper bound and does not establish the conjectured quadratic bound. The classical Pin--Frankl estimate is $(n^3-n)/6$ \cite{Frankl,Pin}. The specific milestone $7/48$ comes from Trahtman's 2011 proposal \cite{Trahtman2011}, whose contribution and subsequent withdrawal are discussed below. Szyku\l a developed the avoiding-word approach into a proved improvement of the general cubic coefficient \cite{Szykula}. Shitov's subsequent estimate has coefficient $8257/49923$, approximately $0.1654$ \cite{Shitov}. For classical background and recent open problems we refer to \cite{Volkov2008,Survey}. The quadratic benchmark is attained by \v{C}ern\'y's classical family \cite{Cerny1964}. An earlier preprint of the present author studies degree transport and a different improvement of the cubic coefficient \cite{Hong}. The proof below gives the required transport arguments directly and does not use the upper-bound theorem of that preprint. \begin{theorem}\label[theorem]{thm:main} Every complete synchronizing deterministic finite automaton $A$ with $n$ states over a finite input alphabet satisfies \[ \rt(A)\le \frac{7}{48}n^3+o(n^3). \] The remainder is uniform over all such automata and input alphabets. \end{theorem} Equivalently, for every $\zeta>0$ there is an integer $N(\zeta)$ such that, for every $n\ge N(\zeta)$ and every such $A$, $\rt(A)\le(7/48+\zeta)n^3$. In particular, if $R(n)$ is the maximum reset threshold among all such $n$-state automata, then $\limsup_{n\to\infty}R(n)/n^3\le7/48$. The order of quantifiers is part of the assertion: $N(\zeta)$ is independent of the alphabet and the transition function. All word lengths in this paper count letters of the original alphabet. \subsection{Trahtman's proposal and the origin of the milestone} \label{sec:trahtman} Trahtman's paper \emph{Modifying the upper bound on the length of minimal synchronizing word}, published at FCT~2011 \cite{Trahtman2011}, proposed the finite upper bound \begin{equation}\label{eq:trahtman-claim} \rt(\mathcal A)\le\frac{n(7n^2+6n-16)}{48} \qquad\text{(the 2011 claim, subsequently withdrawn).} \end{equation} Its structural idea was to reach an image of approximately half the states at quadratic cost and then apply the classical compression bound to the remaining image. In the published-version preprint, Lemma~4 claimed a word of length at most $k^2$ and corank at least $k$ up to the halfway range; Theorem~2 combined this with the completion sum. This is the starting point for the numerical target of the present work. The coefficient can be seen directly from the classical rank charges. At normalized corank $a$, their leading cost is $a^2n^2/2$ per rank. Therefore the completion after reaching half rank has leading cost \begin{equation}\label{eq:half-rank-origin} n^3\int_{1/2}^{1}\frac{a^2}{2}\,\de a =\frac7{48}n^3, \qquad n^3\int_0^{1/2}\frac{a^2}{2}\,\de a=\frac1{48}n^3. \end{equation} A uniform quadratic construction of the first half would remove the second contribution and leave $7/48$ as the cubic coefficient. This explains both the significance of the proposed value and why the cost before half rank is decisive. The claimed bound was not established by the 2011 proof. Its Lemma~3 asserted short avoidance of any prescribed state. Gonze, Jungers, and Trahtman \cite{Correction} gave a four-state counterexample in which avoiding one state requires six letters, contradicting the asserted bound of $n$ letters. The arXiv record \cite{TrahtmanWithdrawal} states that the paper was withdrawn because this key lemma was wrong and the paper's assertion had not been proved. We distinguish that unproved polynomial claim from the two-phase idea that continued to be useful. That idea is explicitly credited to Trahtman in Shitov's introduction \cite{Shitov}; Szyku\l a's avoiding-word method \cite{Szykula} provides the intervening linear-algebraic ingredient. The singleton-fiber mechanism also links these constructions: omitting a singleton input of a current word can lower its rank after a suitable splice. In the stable-rank upgrade used here, avoidance is obtained under an explicit rank-stability condition, through the valid avoid-or-compress lemma. No assertion of uniformly short avoidance of a prescribed state is used. Theorem~\ref{thm:main} establishes the uniform asymptotic $7/48$ coefficient; it does not assert the withdrawn finite polynomial \eqref{eq:trahtman-claim} or the old quadratic half-rank lemma. \subsection{Contribution and proof strategy} The constant $7/48$ is the leading cost of the usual Pin--Frankl completion after reaching half rank. The obstacle is the cost of reaching that rank. We pay this cost by making the completion cheaper, rather than requiring the entire first half to have subcubic cost. A short plateau word of corank $C$ supplies a uniform first-compression cost near $C^2$, valid down to approximately half the number of its kernel blocks. Consequently it continues to save rank-reduction cost after the current word has already reached half rank. For normalized parameters $c=C/n$ and $x=\rho/n$, where $\rho$ marks the first long gap in minimum corank lengths, the leading prefix cost is at most \begin{equation}\label{eq:intro-prefix} p(c,x)=\min\{c^2(1/2-x),\;2(x-c)_+W(x)\},\qquad W(x)=\begin{cases}1/16,&x\le1/4,\\x(1/2-x),&x\ge1/4.\end{cases} \end{equation} Here $y_+=\max\{y,0\}$. The saving in the completion is \begin{equation}\label{eq:intro-saving} S(c)=\int_{1/2}^{(1+c)/2}(a^2/2-c^2)_+\,\de a. \end{equation} The central scalar fact is $p(c,x)\le S(c)$ for $0\le c,x\le1/2$. Its proof in \cref{sec:scalar} uses polynomial identities and interval restriction; it requires no sampling or numerical optimization. The present argument uses short paths between two states, pays the rank loss of those paths, and applies avoid-or-compress with its explicit set and stability hypotheses. In particular, the positive leading prefix cost $p(c,x)$ is paid by the completion saving $S(c)$; it is not necessary to establish the quadratic half-rank claim discussed in \cref{sec:trahtman}. \section{Words, compression, and classical upgrades}\label{sec:words} Let $\mathcal A=(Q,\Sigma,\delta)$ be a complete deterministic finite automaton, with $|Q|=n\ge1$. Write $q\cdot w$ for the right action of a word $w\in\Sigma^*$, and $T\cdot w=\{q\cdot w:q\in T\}$ for a subset $T\subseteq Q$. Thus $q\cdot(uv)=(q\cdot u)\cdot v$. The rank of $w$ is $\rk(w)=|Q\cdot w|$, and its corank is $n-\rk(w)$. Synchronization means that some word has rank one. A word compresses $T$ if $|T\cdot w|<|T|$. For fixed $n$, there are only $n^n$ distinct transition maps of a letter. Removing duplicate letters preserves shortest word lengths, so the maximum $R(n)$ over arbitrary finite alphabets is well defined. For integers $t\ge0$, let $E_t$ be the simple graph on $Q$ in which distinct $p,q$ are adjacent if some word of length at most $t$ merges them. The graphs $E_t$ increase with $t$. Write $e_t=|E(E_t)|$, $\delta_t=\min_q\deg_{E_t}(q)$, and $\Delta_t=\max_q\deg_{E_t}(q)$. A subset is independent in $E_t$ exactly when no word of length at most $t$ compresses it. We use the following standard constructions. They are also proved in the accompanying formalization, as described in \cref{sec:formal}. \begin{lemma}[Pin--Frankl compression]\label[lemma]{lem:pf} If $\mathcal A$ is synchronizing and $T\subseteq Q$ has cardinality $s\ge2$, some word of length at most $\binom{n-s+2}{2}$ compresses $T$. In particular, a word of corank $r\le n-2$ can be extended to a word of larger corank at extra cost at most \[ \PF(r)=\binom{r+2}{2}. \] Starting from a word of corank at least $C$, the remaining reset cost is at most \begin{equation}\label{eq:pf-sum} \sum_{r=C}^{n-2}\PF(r) =\binom{n+1}{3}-\binom{C+2}{3} \le\frac{n^3-C^3}{6}. \end{equation} \end{lemma} The subset bound is the classical consequence of Frankl's set-pair theorem and Pin's shortest-word argument \cite{Frankl,Pin}. The last identity telescopes. If a rank reduction skips coranks, omitting their nonnegative charges can only decrease the total cost. \begin{lemma}[Avoid-or-compress and stable-rank upgrade]\label[lemma]{lem:stable} Suppose $\varnothing\ne P\subsetneq T\subseteq Q$ and some word $z$ satisfies $P\nsubseteq T\cdot z$. Then there is such an avoidance, or a compression of $T$, within $n-|P|$ letters. Consequently, if $u$ has corank $r\ge1$, $2(r+1)\le n$, and a word $v$ satisfies \begin{equation}\label{eq:stability} \rk(v)\le\rk(w)\quad\text{whenever }|w|\le|v|+2r, \end{equation} there is a word of corank at least $r+1$ and length at most $|u|+|v|+2r$. \end{lemma} The first assertion is Szyku\l a's avoiding-word lemma; the second is the stable-rank construction in Shitov's argument, within the Trahtman--Szyku\l a half-rank approach discussed in \cref{sec:trahtman}, \cite[Lemma~2]{Szykula}, \cite[Theorem~2]{Shitov}. We recall the second deduction to specify the actual word involved. Let $P$ be the inputs lying in singleton fibers of $u$. At most $2r$ inputs lie in nonsingleton fibers, so $|P|\ge n-2r\ge2$. Put $T=Q\cdot v$. If $P\nsubseteq T$, use the empty suffix. If $P\subsetneq T$, synchronization permits eventual avoidance of some element of $P$; avoid-or-compress and \eqref{eq:stability} give a word $z$, $|z|\le n-|P|\le2r$, with $P\nsubseteq Q\cdot vz$. The compression alternative contradicts \eqref{eq:stability}. If $P=T$, some letter must change $P$ as a set, since otherwise every word preserves a set of at least two states. Such a letter already omits an element of $P$. In every case the actual word $vzu$ misses the unique output associated with an omitted singleton input of $u$, and its image is contained in $Q\cdot u$. Its rank therefore decreases as required. \begin{lemma}[Accounting for replacement words]\label[lemma]{lem:descent} Suppose that for each actual word of corank $r0$ satisfying $C\le(1/2-\delta)n$, every subset $T\subseteq Q$ with \[ |T|\ge2,\qquad |T|\ge m/2+\epsilon n \] can be compressed by an original-alphabet word of length at most \begin{equation}\label{eq:finite-cap} C^2+\frac{\eta_0 n}{8\epsilon\delta} +\frac{\tau n}{2} +\frac{\eta_0 n}{4\epsilon}+\Omega. \end{equation} The word $v$ is chosen before $T$ and is common to all these subsets. \end{proposition} \begin{proof} Let $l$ be the shortest compression length of $T$, which exists by synchronization. If $l\le\Omega$, \eqref{eq:finite-cap} is immediate. Otherwise apply \cref{lem:calm} to $T_0=l-1$. We obtain $qm$, independence already contradicts the kernel clique property; thus the same reasoning covers every possible long-time case. The sum of the ordinary $E_q$ degrees of all singleton inputs is at most $nK_q$. Indeed, count incidences from each original vertex: its singleton neighbors are whole kernel blocks and number at most $K_q$. Since \eqref{eq:singleton-count} gives $s\ge2\delta n>0$, some singleton input has degree at most $nK_q/s$. By \eqref{eq:calm-spread}, \[ \Delta_q\le d+\tau+\frac{nK_q}{s}. \] At most $2C$ original states are nonsingletons. Summing their degrees by this maximum and singleton degrees by the incidence bound yields \begin{align*} e_q&\le\frac{nK_q}{2}+C(d+\tau)+\frac{CnK_q}{s}\\ &\le C^2+\frac{\eta_0n}{4\epsilon} +\frac{\tau n}{2} +\frac{\eta_0n}{8\epsilon\delta}. \end{align*} Here $d\le C\le n/2$ and $s\ge2\delta n$ were used. Finally \cref{lem:geodesic} gives $q\le e_q$, and $l\le q+\Omega$ proves the result. \end{proof} \subsection{Fixing the auxiliary parameter first} For an integer $k\ge1$, define \begin{align} J&=k^2,& M&=k,& \eta_k&=k^{-2}+3k^{-1},\nonumber\\ \delta_k&=\eta_k^{1/8},& \epsilon_k&=\eta_k^{1/4},& \theta_k&=\frac{\eta_k^{5/8}}8+\frac3{2k} +\frac{\eta_k^{3/4}}4,\label{eq:parameters}\\ A_k&=2^{k^2},& H_k&=(k+1)2^{k^2}+3k+1.\nonumber \end{align} For this fixed $k$, \cref{lem:plateau} supplies $|v|\le A_kn$. Moreover $\eta_0\le\eta_kn$, $\tau\le3n/k$, and $\Omega\le H_kn$. The last inequality follows by bounding $B\le A_kn$, $h\le n$, and $1\le n$. Substitution in \eqref{eq:finite-cap} gives the following form. \begin{corollary}\label[corollary]{cor:normalized-cap} For each $k\ge1$, every strongly connected synchronizing $n$-state automaton has an actual word $v$, $|v|\le A_kn$, such that, if its corank $C$ satisfies $C\le(1/2-\delta_k)n$, then every subset of at least two states and of size at least $(n-C)/2+\epsilon_kn$ can be compressed at cost at most \begin{equation}\label{eq:normalized-cap} C^2+\theta_kn^2+H_kn. \end{equation} \end{corollary} The error $\theta_k$ tends to zero as $k\to\infty$, whereas $H_k$ is fixed when $n\to\infty$. No parameter in this corollary depends on the alphabet or on the queried subset. \section{Reaching half rank with cheap gaps}\label{sec:prefix} Put $H=\lfloor n/2\rfloor$. For $0\le i\le n-1$, let $\lambda_i$ be the minimum length of a word of corank at least $i$. Set $\lambda_0=0$ and $g_i=\lambda_{i+1}-\lambda_i$ where defined. Choose the least $\rhon$ if it exists, and otherwise put $\rho=H$. Then \begin{equation}\label{eq:rho-short} \lambda_\rho\le n\rho\le n^2. \end{equation} For $n\ge4$, $\rho\ge1$: a synchronizing automaton with more than one state has a singular letter, so $\lambda_1=1$. If $\rho=H$, \eqref{eq:rho-short} and \cref{lem:pf} already give a reset word of length at most $(7/48)n^3+2n^2$. In the rest of this section assume $1\le\rhon$. \begin{lemma}[Gap upgrade]\label[lemma]{lem:gap-upgrade} For $\rho\le rn>2r$. A shortest word of length $\lambda_\tau$ has corank exactly $\tau$ and is rank-minimal among words of length at most $\lambda_\tau+2r$. Apply \cref{lem:stable}. All earlier gaps are at most $2r$, so \[ \lambda_\tau=\sum_{j<\tau}g_j \le\sum_{\substack{j<\rho\\i_j\le r}}2i_j. \] This is also the gap construction underlying \cite[Theorem~5]{Shitov}. \end{proof} \begin{proposition}[Cheap-gap prefix]\label[proposition]{prop:gap-prefix} If an actual word $v$ has corank $C$ and length at most $\ell$, there is an actual word of corank at least $H$ and length at most \begin{equation}\label{eq:gap-prefix} 2(\rho-C)_+n^2W(\rho/n)+n\ell+3n^2. \end{equation} Here $(\rho-C)_+=\max\{\rho-C,0\}$, with $C$ and $\rho$ integers. \end{proposition} \begin{proof} Start with a word of length $\lambda_\rho$ and corank at least $\rho$, and use \cref{lem:gap-upgrade,lem:descent}. In the full nominal sum over $r=\rho,\ldots,H-1$, the weight $2i$ of a gap in bucket $i$ occurs exactly \begin{equation}\label{eq:gap-participation} (H-\max\{\rho,i\})_+ \end{equation} times. The actual construction may skip ranks, reducing this sum. Let $C_0=\min\{C,\rho\}$. The first $C_0$ gaps have total $\lambda_{C_0}\le\lambda_C\le\ell$, and their rounded weights sum to at most $\ell+C_0$, because $2\lceil g/2\rceil\le g+1$. Their total exposure is at most $n(\ell+C_0)\le n\ell+n^2$. For each of the at most $\rho-C_0$ remaining gaps, put $y=i/n$ and $x=\rho/n$. Its exposure is at most \[ 2n^2y\pos{1/2-\max\{x,y\}}\le2n^2W(x). \] For $y\le x$ this follows from $y(1/2-x)\le x(1/2-x)$. For $y\ge x$, the parabola $y(1/2-y)$ is maximized at $1/4$ if $x\le1/4$, and at $x$ otherwise. Values $y\ge1/2$ contribute zero. Finally $\sum_{r=\rho}^{H-1}2r\le n^2$, and the initial word costs at most $n^2$. Adding these bounds proves \eqref{eq:gap-prefix}. The same argument handles $C\ge\rho$ through $C_0=\rho$. \end{proof} \begin{proposition}[Combined actual prefix]\label[proposition]{prop:combined-prefix} Suppose the same word $v$ has corank $C$, length at most $\ell$, and supplies a compression cap $C^2+U$, $U\ge0$, for every subset of size at least two and at least $(n-C)/2+\epsilon n$. Put $c=C/n$, $x=\rho/n$, and $E=\lceil\epsilon n\rceil$. Then an actual word $u$ of corank at least $H$ exists with \begin{equation}\label{eq:combined-prefix} |u|\le p(c,x)n^3+\frac{nU}{2}+\frac{En^2}{2} +n\ell+3n^2. \end{equation} \end{proposition} \begin{proof} There are two constructions. The gap construction is \eqref{eq:gap-prefix}, whose leading term is $2(x-c)_+W(x)n^3$. For the direct construction, start at corank $\rho$ and use the cap whenever \[ r+E\le R,\qquad R=\left\lfloor\frac{n+C}{2}\right\rfloor. \] This guarantees $n-r\ge(n-C)/2+\epsilon n$. At the remaining ranks below $H$, use the PF upgrade. Since $R\ge H$, at most $E$ such ranks occur. Each PF charge is at most $n^2/2$. Overpaying every nominal rank by $C^2+U$, and then adding the exceptional charges, bounds the direct word length by \[ n^2+(H-\rho)(C^2+U)+En^2/2 \le c^2(1/2-x)n^3+nU/2+En^2/2+n^2. \] Select the cheaper of these two actual words. Enlarging the errors to the common nonnegative remainder in \eqref{eq:combined-prefix} proves the proposition. The images of the two candidate words have not been identified with one another. \end{proof} \section{Paying the prefix from the completion saving}\label{sec:scalar} We first establish the scalar comparison from \cref{eq:intro-prefix,eq:intro-saving} independently of the automaton. \begin{lemma}[Scalar payment]\label[lemma]{lem:payment} For $0\le c,x\le1/2$, one has $p(c,x)\le S(c)$. \end{lemma} \begin{proof} If $x\le c$, then $p(c,x)=0$ and the assertion follows from nonnegativity of the integral. Suppose $x>c$ and put $d=1/2-c$. First let $0\le c\le1/3$. Since $W(x)\le1/16$, a convex combination of the two bounds defining $p$ gives \begin{equation}\label{eq:envelope} p(c,x)\le\min\{c^2(1/2-x),(x-c)/8\} \le\frac{c^2d}{1+8c^2}. \end{equation} Use weights $1/(1+8c^2)$ and $8c^2/(1+8c^2)$ in the last step. On the integration interval $a^2/2\ge1/8\ge c^2$, so \[ S(c)=\frac{c(3+3c-23c^2)}{48}. \] Subtracting the last expression in \eqref{eq:envelope} yields \[ S(c)-\frac{c^2d}{1+8c^2} =\frac{cF(c)}{48(1+8c^2)},\qquad F(c)=3-21c+49c^2+24c^3-184c^4. \] For $t=3c\in[0,1]$, the exact identity \begin{align*} F(t/3)={}&3(1-t)^4+5t(1-t)^3 +\frac{22}{9}t^2(1-t)^2\\ &+\frac{25}{9}t^3(1-t)+\frac5{81}t^4 \end{align*} shows that $F(c)\ge0$. Now let $1/3\le c\le1/2$. Since $x>c>1/4$ and $2x\le1$, \[ p(c,x)\le2x(x-c)(1/2-x) \le(x-c)(1/2-x)\le d^2/4. \] Restrict the integral defining $S(c)$ to $[3c/2,(1+c)/2]$, an interval of length $d$ contained in its original interval. On writing $a=3c/2+t$ we obtain \[ S(c)\ge\int_0^d\left(\frac{c^2}{8}+\frac{3c}{2}t +\frac{t^2}{2}\right)\de t =\frac{c^2d}{8}+\frac{3cd^2}{4}+\frac{d^3}{6} \ge d^2/4. \] The last inequality uses $3c\ge1$. These arguments include $c=0$ and $c=1/2$, where no strictly positive common margin is needed. \end{proof} The formal scalar proof establishes the stronger inequality $p(c,x)+c/2000\le S(c)$. We use only its weaker consequence above; the shorter two-case proof is included to make the payment transparent. \begin{proposition}[Mixed completion]\label[proposition]{prop:suffix} Under the cap assumptions of \cref{prop:combined-prefix}, assume $0\le c=C/n\le1/2$. From any actual word $u$ of corank at least $H$ one can reach rank one with a word $w$ satisfying \begin{equation}\label{eq:suffix} |w|\le |u|+\left(\frac7{48}-S(c)\right)n^3 +nU+\frac{En^2}{2}+3n^2. \end{equation} \end{proposition} \begin{proof} At nominal corank $r\le n-2$, use the cap or the PF upgrade, whichever is cheaper, when $r+E\le R=\lfloor(n+C)/2\rfloor$; otherwise use PF. All options produce actual words. The cap applies to the actual image of each current word, including a word obtained by replacement. The PF charge obeys \[ \PF(r)\le r^2/2+2n,\qquad \PF(r)\le n^2/2. \] For bulk ranks, the selected cost is at most $\min\{r^2/2,C^2\}+U+2n$. Of the ranks with $r\le R$, at most $E$ fail the bulk condition; charge an extra $n^2/2$ for each. This count follows by injecting such an $r$ into $\{0,\ldots,E-1\}$ via $r\mapsto R-r$. Set $A=(1+c)/2$ and define the nondecreasing function \[ f_c(a)=\begin{cases}\min\{a^2/2,c^2\},&a\le A,\\ a^2/2,&a>A.\end{cases} \] It can have an upward jump at $A$. Its left Riemann sum is still bounded above by its integral. Since $H/n\ge1/2-1/(2n)$ and $f_c\le1/2$ on $[0,1]$, \[ n^2\sum_{r=H}^{n-2}f_c(r/n) \le n^3\int_{1/2}^1 f_c(a)\,\de a+n^2/4. \] The integral equals $7/48-S(c)$. The summed $U$ terms cost at most $nU$, the PF rounding costs at most $2n^2$, and the exceptional ranks cost at most $En^2/2$. The remaining Riemann endpoint allowance fits in $3n^2$ together with PF rounding. Apply \cref{lem:descent} to obtain \eqref{eq:suffix}. \end{proof} \begin{corollary}[Interior finite estimate]\label[corollary]{cor:interior} Under the same assumptions, $\mathcal A$ has a reset word of length at most \begin{equation}\label{eq:interior} \frac7{48}n^3+\frac32nU+En^2+n\ell+6n^2. \end{equation} \end{corollary} \begin{proof} Use \cref{prop:combined-prefix} and then \cref{prop:suffix} from its selected actual word. The leading remainder is $(p(c,x)-S(c))n^3\le0$ by \cref{lem:payment}. \end{proof} \section{Uniform finite bounds and the general case}\label{sec:uniform} With the parameters in \eqref{eq:parameters}, define \begin{equation}\label{eq:EkBk} \mathcal E_k=\frac{\delta_k}{8}+2\theta_k+2\epsilon_k, \qquad B_k=4(k+1)2^{k^2}+20k+100. \end{equation} Then $\mathcal E_k\to0$ as $k\to\infty$, since $\eta_k\to0$ and all powers in \eqref{eq:parameters} are positive. The constants are chosen for bookkeeping and are not optimized. \begin{theorem}[Finite strongly connected bound]\label[theorem]{thm:finite-sc} Let $k\ge1$ satisfy $\delta_k<1/2$. Every strongly connected complete synchronizing automaton with $n\ge4$ states has a reset word of length at most \begin{equation}\label{eq:finite-sc} \left(\frac7{48}+\mathcal E_k\right)n^3+B_kn^2. \end{equation} \end{theorem} \begin{proof} Choose $v$ from \cref{cor:normalized-cap} and let $C$ be its corank. If $C\ge(1/2-\delta_k)n$, use $v$ and complete by PF. Since $0<\delta_k<1/2$, \[ \frac{n^3-C^3}{6} \le\left(\frac7{48}+\frac{\delta_k}{8}\right)n^3. \] For example, integrate the derivative $a^2/2\le1/8$ over $[1/2-\delta_k,1/2]$; larger $C$ only improves the bound. The initial word costs at most $A_kn\le B_kn^2$, so \eqref{eq:finite-sc} follows in this case. Otherwise $C\le(1/2-\delta_k)n$ and the uniform cap applies. If $\rho=H$, the shortcut following \eqref{eq:rho-short} suffices. If $\rho0$, first choose $k\ge1$ such that $\delta_k<1/2$ and $\mathcal E_k<\zeta/2$. Then choose an integer \[ N\ge6,\qquad N>\frac{2(B_k+2)}{\zeta}. \] For all $n\ge N$, \cref{thm:finite-all} implies the required estimate. Both choices depend only on $\zeta$. In particular they precede the alphabet and transition function, which proves uniformity. \end{proof} For an explicit common remainder, one can set \[ e(n)=\inf_{\substack{k\ge1\\\delta_k<1/2}} \left(\mathcal E_k+\frac{B_k+2}{n}\right). \] The indexing set is nonempty, $e(n)\ge0$, and $e(n)\to0$ by the same two-stage choice. For $n\ge6$, \eqref{eq:finite-all} for every admissible $k$ gives $\rt(\mathcal A)\le(7/48+e(n))n^3$. Thus $e(n)n^3$ is one common $o(n^3)$ remainder. \section{Formal verification}\label{sec:formal} The accompanying Lean~4 development establishes \cref{thm:main} under the declaration \begin{center} \lean{CernyComplete.uniform_seven_forty_eight}. \end{center} The threshold $N$ is chosen before the state count, alphabet size, and transition function. Transitions are total functions, synchronization means that an actual word sends the whole state set to one point, and word length is \lean{List.length} over the original alphabet. Thus the formal statement has the same uniform scope and cost convention as the theorem in this paper. The PF and stable-rank constructions are proved within the development; their intermediate interface propositions are discharged before the final theorem. Its recorded axiom dependencies are the standard \lean{propext}, \lean{Classical.choice}, and \lean{Quot.sound}, with no additional axiom or unfinished proof. The accompanying artifact records clean compilation of 32 mathematical modules and one audit module, module-by-module kernel replay, and a successful fresh replay of the final import closure, using Lean~4.35.0 and pinned dependencies. Finite diagnostics supplement these checks; the scalar inequality and final theorem are proved over their full domains. Source correspondence and reproduction instructions are given in Appendices~\ref{app:formal-correspondence} and~\ref{app:formal-reproduction}. The complete formalization, certificate, execution history, and file hashes are preserved in a separate artifact. That artifact is not included in this Hexagon deposit; the deposited source contains the paper and its AI-use disclosure. \section*{Acknowledgments and use of AI tools} OpenAI Codex and Anthropic Claude were used extensively in exploratory reasoning, proof development, programming, formalization, auditing, and manuscript preparation. The artifact distinguishes separate AI review contexts, finite computations, and actual Lean executions. Those review contexts are not external human peer review. At the time of this deposit, the human contributor claims no personal checking or understanding of any part of the proof. We acknowledge the authors of the classical results and the upstream formalization contributors identified in Appendix~\ref{app:formal-correspondence}. No AI system is listed as an author, and no claim of an external academic review or a priority adjudication is made by the verification certificate. \appendix \section{Formal statement and source correspondence} \label{app:formal-correspondence} The proposition of \lean{CernyComplete.uniform_seven_forty_eight} can be written schematically as follows: \begin{quote}\small \begin{verbatim} forall epsilon : Real, 0 < epsilon -> exists N : Nat, forall n a : Nat, N <= n -> forall step : Fin n -> Fin a -> Fin n, Synchronizing step -> ResetWithin step ((coefficient + epsilon) * (n : Real)^3) \end{verbatim} \end{quote} Here \lean{coefficient} is $7/48$ in $\RR$; \lean{Synchronizing} asserts an actual rank-one word, and \lean{ResetWithin} asserts such a word with \lean{List.length} at most the bound. Finite labelings identify this statement with \cref{thm:main}. \begin{center}\small \begin{tabular}{@{}>{\raggedright\arraybackslash}p{.43\linewidth}% >{\raggedright\arraybackslash}p{.51\linewidth}@{}} \toprule Mathematical component & Principal Lean modules \\ \midrule Actual words, graphs, quotient capacity & \lean{CernyWordKernel}, \lean{CernyKernel} \\ Whole-block and ordinary transport & \lean{CernyWholeBlocks}, \lean{CernyDegreeTransport} \\ Connectors, plateau, simultaneous times & \lean{CernyExistence}, \lean{CernyExistenceCalm} \\ All-subsets compression cap & \lean{CernyCompression}, \lean{CernyCompressionCount}, \lean{CernyCompressionGlobal} \\ Classical constructions proved internally & \lean{CernyPFVendor}, \lean{CernyPF}, \lean{CernyStableLinear}, \lean{CernyStableVectors}, \lean{CernyStableAvoid}, \lean{CernyStableUpgrade} \\ Actual prefix and mixed completion & \lean{CernyPrefixGaps}, \lean{CernyGapAssembly}, \lean{CernyFiniteMixed}, \lean{CernyFiniteAssembly} \\ Scalar payment, errors, general inputs & \lean{CernyScalar}, \lean{CernyError}, \lean{CernyReduction}, \lean{CernyUniform}, \lean{CernyComplete} \\ \bottomrule \end{tabular} \end{center} The interface propositions \lean{PFUpgrade} and \lean{StableRankUpgrade} are discharged by \begin{center} \lean{CernyPF.pfUpgrade_of_sync}\\ \lean{CernyStable.stableRankUpgrade_of_sync}. \end{center} The PF component incorporates Baobing Zhang's (\texttt{baobingzhang}) Apache-2.0 Lean formalization \cite{Zhang}, with source, attribution, and license preserved in the artifact. Its bridge identifies the vendor and original-word evaluators. The stable-rank component proves avoid-or-compress by the linear-space argument and constructs the splice $vzu$ explicitly. \section{Reproducing the formal verification} \label{app:formal-reproduction} The complete formalization is preserved separately as \texttt{completed-audit.zip}, with its certificate and reproduction guide. It is not part of the files deposited on Hexagon. The artifact records compilation of all 33 project modules with \texttt{lean --trust=0}, module-by-module replay by \texttt{leanchecker}, and a final \texttt{leanchecker --verbose --fresh CernyComplete} replay. The fresh replay checks imported logical declarations in a new environment; it does not recompile every mathlib source. The certificate in \texttt{project/verification.json} records the pinned tool and dependency revisions, exact commands, and successful exit statuses. Detailed dependency audits and execution logs are preserved in the artifact. For readers with a copy of that artifact, extract it and, on Linux x86\_64, run \begin{quote}\small \begin{verbatim} cd cerny-7-48-completed-audit-2026-11-13/project bash bootstrap_and_verify.sh --fresh-target \end{verbatim} \end{quote} The bootstrap requires Python~3, \texttt{curl}, \texttt{git}, GNU \texttt{tar} with zstd support, and network access to download fixed tool and dependency versions. If that environment is already prepared, run \texttt{python3 verify.py --fresh-target} instead. The large Lean and mathlib installations are not embedded in the source distribution. These records belong to the supplied completed-audit artifact; manuscript preparation did not repeat the full kernel replay. \begin{thebibliography}{99} \small \raggedright \bibitem{Cerny1964} J.~\v{C}ern\'y, \emph{Pozn\'amka k homog\'ennym experimentom s kone\v{c}n\'ymi automatmi}, Matematicko-fyzik\'alny \v{c}asopis \textbf{14}(3) (1964), 208--216. In Slovak. \url{https://dml.cz/dmlcz/126647}. \bibitem{Frankl} P.~Frankl, \emph{An extremal problem for two families of sets}, 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, \emph{On two combinatorial problems arising from automata theory}, in 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{Szykula} M.~Szyku\l a, \emph{Improving the upper bound on the length of the shortest reset words}, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), LIPIcs \textbf{96}, 56:1--56:13. \href{https://doi.org/10.4230/LIPIcs.STACS.2018.56}{doi:10.4230/LIPIcs.STACS.2018.56}. \href{https://arxiv.org/abs/1702.05455}{arXiv:1702.05455}. \bibitem{Shitov} Y.~Shitov, \emph{An improvement to a recent upper bound for synchronizing words of finite automata}, Journal of Automata, Languages and Combinatorics \textbf{24} (2019), 367--373. \href{https://doi.org/10.25596/jalc-2019-367}{doi:10.25596/jalc-2019-367}. \href{https://arxiv.org/abs/1901.06542}{arXiv:1901.06542}. \bibitem{Correction} F.~Gonze, R.~M.~Jungers, and A.~N.~Trahtman, \emph{A note on a recent attempt to improve the Pin--Frankl bound}, Discrete Mathematics \& Theoretical Computer Science \textbf{17}(1) (2015), 307--308. \href{https://doi.org/10.46298/dmtcs.2101}{doi:10.46298/dmtcs.2101}. \href{https://arxiv.org/abs/1412.0975}{arXiv:1412.0975}. \bibitem{Trahtman2011} A.~N.~Trahtman, \emph{Modifying the upper bound on the length of minimal synchronizing word}, in Fundamentals of Computation Theory (FCT~2011), Lecture Notes in Computer Science \textbf{6914} (2011), 173--180. \href{https://doi.org/10.1007/978-3-642-22953-4_15}{doi:10.1007/978-3-642-22953-4\_15}. Published-version preprint: \href{https://arxiv.org/abs/1104.2409v4}{arXiv:1104.2409v4}. The claimed upper bound was not established; see \cite{Correction,TrahtmanWithdrawal}. \bibitem{TrahtmanWithdrawal} A.~N.~Trahtman, \emph{Withdrawal notice for arXiv:1104.2409}, version~7, March~21, 2014; the first withdrawn version is version~5, December~10, 2012. \url{https://arxiv.org/abs/1104.2409v7}. \bibitem{Volkov2008} M.~V.~Volkov, \emph{Synchronizing automata and the \v{C}ern\'y conjecture}, in Language and Automata Theory and Applications (LATA~2008), Lecture Notes in Computer Science \textbf{5196} (2008), 11--27. \href{https://doi.org/10.1007/978-3-540-88282-4_4}{doi:10.1007/978-3-540-88282-4\_4}. \bibitem{Survey} M.~Szyku\l a, \emph{Synchronizing automata: Open problems}, Electronic Proceedings in Theoretical Computer Science \textbf{451} (2026), 33--47. \href{https://doi.org/10.4204/EPTCS.451.3}{doi:10.4204/EPTCS.451.3}. \href{https://arxiv.org/abs/2608.24245}{arXiv:2608.24245}. \bibitem{Hong} S.~Hong, \emph{Degree transport and a smaller cubic coefficient for reset thresholds}, preprint, Hexagon 2611.00172v1, November 2026. \url{https://hexagonmath.org/2611.00172v1}. \bibitem{Zhang} B.~Zhang, \emph{Lean formalization of the Pin--Frankl bound and Kari's theorem}, software contribution, 2026. Source submission and preserved provenance: \url{https://github.com/TheJustinSunPrize/awards/pull/605}. \end{thebibliography} \end{document}