==== TABLE OF CONTENTS ====
Uniform-Matrix-Hitting-Points-in-Every-Positive-Characteristic//main.tex
Uniform-Matrix-Hitting-Points-in-Every-Positive-Characteristic//sections/construction.tex
Uniform-Matrix-Hitting-Points-in-Every-Positive-Characteristic//sections/introduction.tex
Uniform-Matrix-Hitting-Points-in-Every-Positive-Characteristic//sections/order.tex
Uniform-Matrix-Hitting-Points-in-Every-Positive-Characteristic//sections/systems.tex
Uniform-Matrix-Hitting-Points-in-Every-Positive-Characteristic//sections/words.tex
Uniform-Matrix-Hitting-Points-in-Every-Positive-Characteristic//references.bib
===========================

==== BEGIN Uniform-Matrix-Hitting-Points-in-Every-Positive-Characteristic//main.tex ====
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage{placeins}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\usepackage{xcolor}
\definecolor{linkblue}{RGB}{30,66,115}
\usepackage[colorlinks=true,linkcolor=linkblue,citecolor=linkblue,urlcolor=linkblue]{hyperref}
\hypersetup{pdftitle={Uniform Matrix Hitting Points in Every Positive Characteristic},pdfauthor={OpenAI},pdfsubject={Noncommutative polynomial identity testing}}
\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}
\DeclareMathOperator{\Mat}{Mat}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\ord}{ord}
\newcommand{\F}{\mathbb F}
\newcommand{\J}{\mathcal J}
\newcommand{\eps}{\epsilon}
\newcommand{\articleid}[1]{\begingroup\Urlmuskip=0mu plus 1mu\relax\nolinkurl{#1}\endgroup}
\setlist[enumerate]{itemsep=3pt,topsep=5pt}
\setlength{\emergencystretch}{2em}
\title{Uniform Matrix Hitting Points\\in Every Positive Characteristic}
\author{OpenAI}
\date{October 4, 2026}
\begin{document}
\maketitle
\begin{abstract}
We construct a single matrix substitution that detects every nonzero
size-$s$ division-free noncommutative formula in $n$ variables over every
field of a given positive characteristic. One deterministic machine,
given a promised prime $p$ in binary and $n,s$ in unary, outputs matrices
over $\mathbb F_p$ of dimension $O(n^3s^6)$ in polynomial bit time.
The same tuple works with arbitrary extension-field coefficients,
including in characteristic two. The construction also applies to the
stated acyclic algebraic path programs.
\end{abstract}
\input{sections/introduction}
\input{sections/words}
\input{sections/systems}
\input{sections/order}
\input{sections/construction}
\bibliographystyle{plain}
\bibliography{references}
\end{document}
==== END Uniform-Matrix-Hitting-Points-in-Every-Positive-Characteristic//main.tex ====

==== BEGIN Uniform-Matrix-Hitting-Points-in-Every-Positive-Characteristic//sections/construction.tex ====
\section{Truncation and construction over the prime field}
\label{sec:construction}

The order bound gives a finite amount of information in the variable $z$ that
detects every nonzero formula.  We first express the operators on this finite
space as matrices over $\F_p(t)$.  We then retain bounded Taylor expansions in
$t$ and represent multiplication by these truncated polynomials as matrices
over $\F_p$.  A common denominator bound ensures that the second truncation
preserves the nonvanishing established by the first.

\subsection{Truncating the word operators}

Fix a prime $p$ and integers $n,s\geq 1$, and set
\begin{equation}\label{eq:z-truncation-length}
  N=1+n\binom{2s}{2}.
\end{equation}
Let $F$ be any field of characteristic $p$ and put $K=F(t)$, with $t$ an
indeterminate over $F$.  Each operator $\mathcal J_i$ raises $z$-order by at
least one, so it induces an operator on $K[[z]]/(z^N)$.  In the ordered basis
$1,z,\ldots,z^{N-1}$, with vectors represented by coefficient columns, its
matrix is
\begin{equation}\label{eq:truncated-operators}
 (U_i)_{r,q}=
 \begin{cases}
 \displaystyle\frac{(1+t)^{i(r-q-1)}}{t^r-1},&0\leq qq$, and
inverting $\sigma-1$ divides that coefficient by $t^r-1$.  In particular,
$U_i\in\Mat_N(\F_p(t))$, independently of the choice of $F$.

Let $e_0$ be the coefficient column of the constant series $1$.  The recursion
$h_{iw}=\mathcal J_i(h_w)$ gives
\begin{equation}\label{eq:operator-evaluation}
 f(U_1,\ldots,U_n)e_0
   =\text{the coefficient column of }h_f\bmod z^N
\end{equation}
for every $f\in F\langle x_1,\ldots,x_n\rangle$.  The order of the operators
agrees with the order of matrix multiplication: the rightmost operator of a
word acts first.

Suppose that $f$ is nonzero and has a formula of size at most $s$.  Word-series
independence gives $h_f\ne0$.  Section~\ref{sec:systems} represents this series
as $uHv$ in a system of dimension $m\leq2s$ with numerator and denominator
degrees at most $n$.  Theorem~\ref{thm:order} therefore gives
\[
  \ord_z h_f\leq n\binom m2\leq n\binom{2s}{2}=N-1.
\]
Thus \eqref{eq:operator-evaluation} is nonzero, and in particular
\begin{equation}\label{eq:rational-hitting}
 f(U_1,\ldots,U_n)\ne0.
\end{equation}
The tuple $U$ already has the required simultaneous detection property, but its
entries are rational functions.  We next replace these functions by finite
matrices while preserving this property.

\subsection{Retaining finitely many coefficients of \texorpdfstring{$t$}{t}}

All denominators in \eqref{eq:truncated-operators} are nonzero at $t=0$.
Moreover, one denominator clears every polynomial evaluated at $U$.  Define
\begin{equation}\label{eq:t-truncation-length}
 D(t)=\prod_{r=1}^{N-1}(t^r-1),
 \qquad
 E=1+\binom N2+n(N-1).
\end{equation}
For every $f\in F\langle x_1,\ldots,x_n\rangle$, each entry of $Df(U)$ is a
polynomial in $F[t]$ of degree less than $E$.  To verify this, consider a
nonzero summand in the $(r,q)$ entry of a word product
$U_{i_1}\cdots U_{i_k}$.  Since the matrices are strictly lower triangular,
the summand follows a chain
\[
 q=j_0