% Hexagon source adaptation of the published Zenodo edition. % Changes are limited to packaging, bibliography rendering, navigation and archive links. % Mathematical formulas and their order are preserved; see the local integrity record. \PassOptionsToPackage{expansion=false,nopatch=footnote}{microtype} \documentclass[11pt,a4paper]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{lmodern,microtype} \usepackage[margin=26mm,headheight=14pt]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{booktabs,longtable,array,enumitem} \usepackage[unicode,hidelinks]{hyperref} \usepackage{fancyhdr} \pagestyle{fancy}\fancyhf{}\fancyhead[L]{\small Local freedom and capacity barriers}\fancyhead[R]{\small Brice Pouly}\fancyfoot[C]{\thepage} \setlength{\parskip}{3pt}\setlength{\parindent}{1.2em} \setlength{\emergencystretch}{2em} \setcounter{tocdepth}{1} \makeatletter \renewcommand{\l@section}[2]{\addpenalty{\@secpenalty}\addvspace{2pt}\@dottedtocline{1}{0pt}{2em}{\bfseries #1}{\bfseries #2}} \makeatother \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition}\newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \theoremstyle{remark}\newtheorem{remark}[theorem]{Remark} \newcommand{\N}{\mathbb N}\newcommand{\Z}{\mathbb Z}\newcommand{\Q}{\mathbb Q}\newcommand{\R}{\mathbb R}\newcommand{\F}{\mathbb F} \newcommand{\D}{\mathcal D}\newcommand{\M}{\mathcal M_{\pm}} \newcommand{\1}{\mathbf 1} \DeclareMathOperator{\core}{core}\DeclareMathOperator{\sq}{sq}\let\Cap\relax\DeclareMathOperator{\Cap}{Cap}\DeclareMathOperator{\Pack}{Pack}\DeclareMathOperator{\rank}{rank}\DeclareMathOperator{\wt}{wt}\DeclareMathOperator{\Res}{Res}\DeclareMathOperator{\disc}{disc}\DeclareMathOperator{\diag}{diag}\DeclareMathOperator{\MaxCut}{MaxCut} \newcommand{\cl}[1]{[#1]} \newcommand{\eps}{\varepsilon} \newcommand{\leg}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\dd}{\,\mathrm d} \newcommand{\sourcefile}[1]{\texttt{\detokenize{#1}}} \hypersetup{bookmarksdepth=2,bookmarksopen=true,bookmarksopenlevel=1,pdftitle={Local freedom and capacity barriers in quadratic trace reconstruction},pdfauthor={Brice Pouly},pdfsubject={Local compatibility, arithmetic certificates, and forced errors in multiplicative traces}} \usepackage{bookmark} \begin{document} \title{Local freedom and capacity barriers\\in quadratic trace reconstruction} \author{Brice Pouly\\[4pt]\small With AI assistance from GPT-6 Astra} \date{} \maketitle \begin{abstract} A completely multiplicative sign function is determined by its values on $n^2+1$, $n^2+2$, and $n^2-2$, but exact determination does not quantify how many readings detect a negative prime sign. We distinguish three losses of information: partial compatibility tests, geometric restrictions on certificates, and fractional relaxation of signed constraints. After fixing a prime head, we describe the exact fibre of a window and the parity constraints joining two windows. For any fixed head and any sequence $H_N=N^{o(1)}$, one table with $o(N)$ negative entries passes every $H_N$-window test and every two-reading test. A separate finite table passes these tests without any global source. We bound certificate capacity---fractional packing under unit reading loads---for narrow and binary certificates and for low-degree transport libraries whose links cancel odd prime valuations in pairs. A fixed algebraic curve of certificates for a target prime $p$ has at most logarithmic capacity, or capacity at most one when a reading is constant; in the infinite unanchored case its common poles have field $\Q(\sqrt p)$. Conversely, selected values of $n^2+1$ can force linearly many errors while the capacity of all certificates stays bounded. Two internally disjoint pair families compose without loss on their existing readings, whereas sixteen actual values exhibit $\Pack=3<\Cap=4<\mu=5$. The selected-sample constructions do not give an upper bound for the minimum on a complete prefix. \end{abstract} \begingroup\setlength{\parskip}{0pt}\tableofcontents\endgroup \clearpage % Original source: sections/01_introduction.tex \section{What exact observations fail to quantify}\label{sec:intro} The identity \[ (3^2+2)(9^2+2)(1752^2+2)=2\cdot37433^2 \] forces the product of three observed signs to equal the sign at the prime two. Indeed, the readings are $11$, $83$, and $2\cdot11\cdot83\cdot41^2$. Writing $x,y$ for the first two signs and $\sigma$ for the prescribed sign at two, their sign triple is $(x,y,\sigma xy)$. Each pair can take all four values while the signs at two, three, five, and seven are held fixed, but for $\sigma=-1$ the triple cannot be all positive. A multiplicative relation is information about a joint assignment, not about its separate projections. The same distinction persists at a much larger scale. There are tables on all three traces up to $N$ with only $o(N)$ negative entries that pass every short-window test and every pair test, each test admitting a genuine multiplicative explanation. These explanations need not agree on the unobserved primes. A different loss of information occurs when an exact product relation is replaced by the inequality ``at least one of these readings is negative''. All such inequalities together can have a fractional packing value much smaller than the number of errors imposed on an actual source. A third, separate restriction appears when certificates must obey a prescribed geometry: exact identities can be plentiful while reusing too few readings to carry much weight. The paper distinguishes partial compatibility, geometrically restricted capacity, and fractional relaxation. Its contribution is to quantify these losses in the same arithmetic observation system, rather than to introduce new general principles of parity or optimisation. \subsection{Sources, labels, and the target minimum} Let $\M$ be the completely multiplicative functions $h:\N_{\ge1}\to\{-1,1\}$. Set \begin{equation}\label{eq:basic} \D=\{-1,-2,2\},\qquad Q_d(n)=n^2-d,\qquad I_N=\{(n,d):1\le n\le N,\ d\in\D,\ Q_d(n)>0\}. \end{equation} A label $i=(n,d)$ denotes the reading $Q_i=Q_d(n)$. Equal integer values at different labels remain different readings; $|I_N|=3N-1$. For a prime $p$, define \begin{equation}\label{eq:minimum} E_N(h)=\sum_{i\in I_N}\1_{h(Q_i)=-1},\qquad m_p(N)=\min_{h\in\M,\ h(p)=-1}E_N(h). \end{equation} Only finitely many prime signs affect this minimum. All signs other than the prescribed sign at $p$ are free, and a minimising source may change with $N$. A \emph{certificate for $p$} on a labelled sample $A=(A_i)_{i\in I}$ is a nonempty subset $C\subseteq I$ such that \begin{equation}\label{eq:certificate} \prod_{i\in C}A_i=pz_C^2,\qquad z_C\in\N_{\ge1}. \end{equation} Its signs have product $-1$ whenever $h(p)=-1$. To add the resulting error inequalities without charging a reading more than once, impose \begin{equation}\label{eq:loads} \alpha_C\ge0,\qquad \sum_{C\ni i}\alpha_C\le1\quad(i\in I). \end{equation} The maximum of $\sum_C\alpha_C$ is the \emph{capacity} $\Cap_p(A)$: a fractional packing value under unit reading loads. The maximum number of disjoint certificates is $\Pack_p(A)$, and the actual minimum is \[ \mu_p(A)=\min_{h(p)=-1}\sum_{i\in I}\1_{h(A_i)=-1}. \] The elementary inequalities \begin{equation}\label{eq:invariants} \Pack_p(A)\le\Cap_p(A)\le\mu_p(A) \end{equation} are the starting point, not equalities to be assumed. Restrictions on the allowed certificates will always be indicated. On the full sample, $\mu_p((Q_i)_{i\in I_N})=m_p(N)$. The minimum number of labels meeting every certificate is exactly $\mu_p(A)$, by Proposition~\ref{prop:hitting}. Thus an integral cover of all certificates retains the true error minimum; it is the fractional relaxation that can lower its value. The fifteen-reading example in Section~\ref{subsec:fifteen} has capacity five but error minimum seven. For a positive integer $a$, $\core(a)$ is its squarefree kernel: $a=\core(a)\sq(a)^2$. Thus $\core(a)$ records \emph{odd} valuations, not every prime divisor. Write $\cl a$ for its class in $\Q_{>0}^{\times}/\Q_{>0}^{\times2}$, viewed additively as a vector space over $\F_2$. A source is precisely a linear character of this space. All unspecified logarithms are natural, and constants in $O$ or $\ll$ depend only on displayed subscripts. We use $N^{o(1)}$ for a positive quantity whose logarithm is $o(\log N)$, or, in an upper-bound statement, one bounded by $O_\delta(N^\delta)$ for every fixed $\delta>0$. The exact injectivity of the three infinite traces has a short explanation. For the quotient of two sources with identical traces, the values $2$, $3$, and $6$ first fix the signs at two and three. For every prime $q\ge5$, at least one $d\in\D$ is a quadratic residue modulo $q$. A centred root $1\le r\le(q-1)/2$ gives $Q_d(r)=qm$ with $0M/16,\qquad 1\le\Cap_2(A)<16. \] The indices may be required to exceed any prescribed bound, and any finite compatible prime head may be preserved. A separate sample of sixteen explicit values satisfies \[ \Pack_2(A)=3,\qquad\Cap_2(A)=4,\qquad\mu_2(A)=5. \] For two square classes $a+b=\cl p$, two internally disjoint families of pairs with respective classes $a$ and $b$, of sizes $M_a,M_b$, yield at least $\min(M_a,M_b)$ disjoint certificates for $p$ on their existing labels. The sixteen-value sample shows that the analogous lossless principle fails for five families. \end{theorem} Here $M$ counts selected observations, not their largest index. The arithmetic realisation does not preserve density or give a useful height bound in terms of $M$. \paragraph{A positive baseline on the complete prefix.} The obstructions below do not mean that a negative prime sign is detected only finitely often. The following elementary consequence of injectivity and Pell multiplication gives a useful reference scale, not an optimal lower bound or a new Pell result. \begin{proposition}[Logarithmic disjoint packing]\label{prop:baseline} For every fixed prime $p$, there is $c_p>0$ such that, for all sufficiently large $N$, \[ \Pack_p((Q_i)_{i\in I_N})\ge c_p\log N, \qquad m_p(N)\ge c_p\log N. \] \end{proposition} \begin{proof} The class $[p]$ lies in the span of the classes of the three traces. Otherwise a linear functional vanishing on that span but taking value one at $[p]$ would define a nontrivial source with all three traces positive, contradicting the injectivity proved above. Choose an inclusion-minimal finite certificate $C_0$ for $p$. Its classes $a_i=\core(Q_i)>1$ are distinct: two equal classes could be removed without changing the target. The inequality $a_i>1$ follows because none of the positive readings is a square. Write $n_i^2-a_i u_i^2=d_i$. By Pell's theorem, choose an integral unit $\epsilon_i=x_i+y_i\sqrt{a_i}>1$ of norm one with $x_i,y_i>0$ \cite[Theorem~2.3 and multiplication of solutions]{Conrad}. Define \[ n_{i,k}+u_{i,k}\sqrt{a_i}=(n_i+u_i\sqrt{a_i})\epsilon_i^k \quad(k\ge0). \] These are positive integer solutions with strictly increasing $n_{i,k}$, and $n_{i,k}=\tfrac12(n_i+u_i\sqrt{a_i})\epsilon_i^k+O_i(\epsilon_i^{-k})$. Thus the number of terms with $n_{i,k}\le N$ is $\log N/\log\epsilon_i+O_i(1)$. Take the same initial number of terms in every orbit, namely the minimum of these counts. At each rank, one reading from each orbit gives a certificate for $p$. The certificates are disjoint: an orbit has no repeated index, and different orbits have different square classes and hence cannot share a label. The fixed certificate and units give $\gg_p\log N$ disjoint certificates, proving both claims. \end{proof} For $p=2$, the singletons generated by $n_k+u_k\sqrt2=(1+\sqrt2)(3+2\sqrt2)^k$ already give \[ m_2(N)\ge\frac{\log N}{\log(3+2\sqrt2)}-O(1). \] A stronger lower bound for the same unrestricted minimum is proved in \cite[Theorem~1.3]{PoulyReconstruction}: \[ m_p(N)\ge\Phi_c(K),\qquad \Phi_c(K)=\exp\!\left(\exp\!\left(c\frac{\log K}{\log\log K}\right)\right), \qquad K=\frac{\log N}{\log\max(3,p)}, \] for each fixed $0{\raggedright\arraybackslash}p{.30\textwidth}>{\raggedright\arraybackslash}p{.36\textwidth}>{\raggedright\arraybackslash}p{.27\textwidth}@{}} \toprule Prior result or mechanism & Scope retained or added here & Use in the paper\\ \midrule One fixed quadratic, square target: $O_P(\sqrt N)$ \cite[Proposition~5.1]{BWX} & Mixed trace types and arbitrary target class, with the weaker exponent $2/3+\varepsilon$ & Pair constraints in a common table\\[4pt] Exact-ratio counts \cite{BWX,CS} & Mixed types; a realised link bounds its reduced coefficients & Necessity of library diversity under unit loads\\[4pt] Binary ports, joins, and positive graph forms \cite{Cornuejols,EJ,GW} & Actual prime assignments and quadratic values, with square factors removed exactly & Arithmetic gaps and repair without hidden sign variables\\[4pt] Siegel and coefficient-uniform curve counts \cite{ABP,CCDN} & Target-imposed common poles; loads on fixed curves or on paired transport links & Distinct geometric capacity barriers\\ \bottomrule \end{tabular} \end{center} \paragraph{What the arithmetic realisations establish.} The same low-weight table works for all the specified tests, rather than selecting a different table for each test. The fixed-curve theorem forces the field $\Q(\sqrt p)$ at the common poles before converting integrality into a load bound. The selected-sample realisation preserves every allowed prime assignment and the entire certificate family. Finally, composing two matchings keeps the existing labels and their height. These are the assertions to distinguish from the classical mechanisms above; they do not claim a general improvement in those mechanisms. \paragraph{Reading route.} Section~\ref{sec:arithmetic} supplies the two counting estimates used repeatedly. Sections~\ref{sec:local}--\ref{sec:partial} explain local freedom and simultaneous partial compatibility. Sections~\ref{sec:geometry}--\ref{sec:transport} quantify geometric restrictions on certificates. Sections~\ref{sec:gap}--\ref{sec:composition} show what capacity misses and where composition succeeds or fails. The graph examples and rational centres are supporting illustrations, not additional main themes. The appendices retain two complementary distinctions: full rank in logarithmic windows, and a single source with every finite word at positive frequency but zero measured entropy. % Original source: sections/02_arithmetic.tex \section{Two counting estimates with moving square classes}\label{sec:arithmetic} A private prime gives an exact local degree of freedom. Before using that observation, we need to count the readings for which no such prime is available. We also need to count pairs that remain dependent after a prime head is fixed. The two estimates below answer these different questions; neither assumes anything about the signs of a source. \subsection{A square class has only logarithmically many representatives} The logarithmic dependence comes from classical norm equations; compare also \cite[remark after Lemma~3.2 and equation~(13)]{BWX}. The proof below isolates an absolute spacing bound sufficient for all our moving square classes. Put $\lambda_0=(3+\sqrt5)/2$, and let $\tau(k)$ denote the number of positive divisors of $k$. \begin{lemma}[Uniform norm count]\label{lem:norm} If $a\ge2$ is squarefree, $K\ne0$ is an integer, and $M>1$, the number of pairs $X\ge0$, $Y\ge1$ satisfying \[ X^2-aY^2=K,\qquad 1\alpha_1$ of the same ideal and the same signed norm have quotient a unit $u>1$ of norm one. Its conjugate is $u^{-1}>0$, so its integral trace is at least three. Hence $u\ge\lambda_0$. The generators of each ideal are multiplicatively separated in $(1,M]$, which proves the count. For $a=1$, factor $(X-Y)(X+Y)=K$. \end{proof} For a squarefree $a\ge1$, write \[ R_a(N)=\#\{i\in I_N:\core(Q_i)=a\}. \] No positive $Q_d(n)$ is a square: each lies strictly between the adjacent squares on the relevant side of $n^2$. Thus $R_1(N)=0$. Applying Lemma~\ref{lem:norm} to $n^2-au^2=d$ gives the explicit uniform estimate \begin{equation}\label{eq:R} R_a(N)\le5\left(1+\frac{\log(2N+1)}{\log\lambda_0}\right). \end{equation} The factor five is $\sum_{d\in\D}\tau(|d|)$. No regulator or class number is being bounded uniformly in $a$. \subsection{All pairs in a prescribed square class} \begin{theorem}[Uniform pair count]\label{thm:pairs} For every fixed $\eps>0$, uniformly in $N\ge2$ and squarefree $a\ge1$, \[ T_a(N):=\#\{\{i,j\}\subset I_N:i\ne j,\ \core(Q_iQ_j)=a\} \ll_\eps N^{2/3+\eps}. \] The diagonal in labels is excluded, but distinct labels of equal integer value are retained. \end{theorem} \begin{proof} We first control large square parts. If $1\le U\le N^{2/3}$, then \begin{equation}\label{eq:squaretail} B_N(U):=\#\{i:\sq(Q_i)>U\} \ll\left(\frac NU+N^{2/3}\right)\log(2N). \end{equation} To see this, put $V=\lceil N^{2/3}\rceil$. For $UV$, then $\core(Q_i)\ll N^{2/3}$, and \eqref{eq:R} pays for all these classes. This proves \eqref{eq:squaretail}. Now choose $U=\lfloor N^{1/3}\rfloor$. Once the square class of one member of a pair is fixed, the other's class is fixed as well: it is $\core(a\core(Q_i))$. By \eqref{eq:R}, a reading has $O(\log(2N))$ partners in this target class. Pairs meeting the large-square-part set therefore contribute \[ O(B_N(U)\log(2N))\ll N^{2/3}\log^2(2N). \] For the remaining pairs write \[ n^2-d=rbu^2,\qquad m^2-e=rcv^2, \qquad bc=a, \] where $rb,rc$ are squarefree, $(b,c)=1$, and $u,v\le U$. Eliminating $r$ gives \begin{equation}\label{eq:pairnorm} X^2-aY^2=K,\quad X=bum,\quad Y=vn, \quad K=b^2eu^2-adv^2. \end{equation} There are at most $\tau(a)$ choices of $(b,c)$. If $a>1$, $K=0$ admits no positive solution. If $a=1$ and $K=0$, then $eu^2=dv^2$. The distinct same-sign elements of $\D$ have a nonsquare ratio, so $d=e$, $u=v$, and then $n=m$. This is the excluded diagonal. A represented class satisfies $a\le(N^2+2)^2$. Crude bounds $X+Y\sqrt a\le6N^6$ and $|K|\le40N^{10}$ now suffice. For every fixed $\eta>0$, $\tau(k)\ll_\eta k^\eta$: for large primes $q$, $e+1\le2^e\le q^{\eta e}$, and the remaining finite set of primes contributes a constant. Lemma~\ref{lem:norm}, including its factorised case, consequently gives $O_\eps(N^\eps)$ solutions per choice after reducing the auxiliary exponent. Summing over nine choices of $d,e$, $U^2$ choices of $u,v$, and $\tau(a)$ choices of $b$ proves the result. \end{proof} The threshold $N^{1/3}$ balances the square-part tail against the two free square factors. It is not an optimality claim for pair counting. \subsection{A sieve for the absence of an odd prime factor} For $Y\ge2$ and a prime $p$, let \[ A_d(T;Y,p)=\{1\le n\le T:Q_d(n)>0,\ v_q(Q_d(n))\text{ is even for every }q>Y,\ q\ne p\}. \] Let $\mathcal P_d^{\rm ex}$ be the odd primes congruent to $5,3,7$ modulo eight when $d=-1,-2,2$, respectively. Define $A_d^{\rm ex}(T;Y,p)$ by imposing the same parity condition only for $q\in\mathcal P_d^{\rm ex}$. \begin{theorem}[Uniform odd-factor sieve]\label{thm:sieve} Uniformly in $T\ge3$, $Y\ge2$, $p$, and $d\in\D$, \begin{align} |A_d(T;Y,p)|&\ll T\min\left(1,\frac{\log(2Y)}{\log(2T)}\right),\label{eq:sieveone}\\ |A_d^{\rm ex}(T;Y,p)|&\ll T\min\left(1,\sqrt{\frac{\log(2Y)}{\log(2T)}}\right).\label{eq:sievehalf} \end{align} For every positive integer $M$, the number of readings $i\in I_N$ with $\core(Q_i)\mid\operatorname{rad}(pM)$ is at most \begin{equation}\label{eq:alphabet} C N\min\left(1,\frac{\log(2+\log(2M))}{\log(2N)}\right). \end{equation} For a fixed $M$, the sharper bound $O(2^{\omega(M)}\log(2N))$ also holds, uniformly in $p$. \end{theorem} \begin{proof} We give the finite sieve and its error term, since its uniformity is consumed later by moving widths and moving rule libraries. Sieve over odd splitting primes for $Q_d$, or over $\mathcal P_d^{\rm ex}$, in $Y0}}\prod_{q\mid m}\1_{v_q(Q_d(n))=1} =Tg(m)+r_m,\qquad |r_m|\le\rho(m). \] For $m=1$ the possible missing value $Q_2(1)<0$ costs at most one. For $m>1$ it is not in a forbidden class. Put $t(q)=g(q)/(1-g(q))$, extend multiplicatively on squarefree integers in this prime set, and define \[ G(z)=\sum_{m\le z}t(m),\qquad \lambda_m=\frac{\mu(m)t(m)}{g(m)G(z)} \sum_{\substack{r\le z/m\\(r,m)=1}}t(r)\quad(m\le z). \] Set $\lambda_m=0$ otherwise. The classical Selberg diagonalisation \cite[Section~13.2]{Kedlaya} here reads \begin{equation}\label{eq:selberg} \lambda_1=1,\quad |\lambda_m|\le2^{\omega(m)},\qquad \sum_{a,b\le z}\lambda_a\lambda_b g([a,b])=G(z)^{-1}. \end{equation} For completeness, if $y_r=\sum_{r\mid m}\lambda_mg(m)$, Möbius inversion gives $y_r=\mu(r)t(r)/G(z)$. The identity $g([a,b])=g(a)g(b)\sum_{r\mid(a,b)}1/t(r)$ transforms the quadratic form into $\sum_r y_r^2/t(r)=1/G(z)$. Also $t(m)/g(m)=\prod_{q\mid m}(1-g(q))^{-1}\le2^{\omega(m)}$, which proves the weight bound. A sifted integer makes the weighted sum exactly one. Squaring and using \eqref{eq:selberg} therefore bounds its count by \begin{equation}\label{eq:sieveerror} \frac{T}{G(z)}+\sum_{a,b\le z}|\lambda_a\lambda_b|\rho([a,b]) \le\frac{T}{G(z)}+z^4(1+\log z)^6. \end{equation} Indeed, $\rho([a,b])\le[a,b]2^{\omega([a,b])}$, $[a,b]\le z^2$, and $\sum_{m\le z}4^{\omega(m)}\le z(1+\log z)^3$ on squarefree integers. Sifting only valuation one enlarges the exceptional set; higher odd valuations do not invalidate this upper bound. Let $\theta=1$ for all splitting primes and $\theta=1/2$ for the exclusive class. Fixed-modulus Mertens estimates \cite[Theorem~3.3]{BF} and $g(q)=2/q+O(q^{-2})$ give, uniformly for $x\ge Y\ge2$, \begin{equation}\label{eq:euler} \prod_{\substack{Y0$. Choose each available prime up to $x$ independently with probability $g(q)$ and let $R$ be their product. Then $\mathbb E\log R\le\tfrac14\log z$, so $\mathbb P(R\le z)\ge3/4$. The probability of a squarefree product $m$ is $t(m)/\prod(1+t(q))$. Consequently \[ G(z)\gg(\log z/\log(2Y))^\theta\quad(Y\le x). \] If $Y>x$, use $G(z)\ge1$ and the trivial count. With $z=T^{1/8}$, the error in \eqref{eq:sieveerror} is $O(T^{1/2}\log^6(2T))$, absorbed by both claimed bounds for large $T$. The bounded range is absorbed in the absolute constant. For \eqref{eq:alphabet}, take $Y=\max(3,\log(2M))$ and omit also the primes dividing $M$. The omission beyond $Y$ changes the Euler product by only a bounded factor, since \[ \sum_{\substack{q\mid M\\q>Y}}\frac1q \le\frac{\log M}{Y\log Y}\ll1. \] Repeat the dimension-one argument; if $Y$ is too large, the trivial bound applies. Finally, for fixed $M$ there are at most $2^{\omega(M)+1}$ square classes supported on $pM$, and \eqref{eq:R} proves the last assertion. \end{proof} The probability space in this proof is only a device for lower-bounding a finite Euler sum. No source signs have been randomised. % Original source: sections/03_local.tex \section{The exact freedom of one window, and the cost of joining two}\label{sec:local} An unusually large prime factor is useful only if its valuation is odd and it is not shared by another reading in the experiment. A resultant makes the second condition automatic inside a sufficiently short window. The first condition cannot be discarded. \subsection{Private odd factors and an exact fibre} For an interval of $H$ consecutive indices starting at $u$, let $W(u,H)$ consist of its positive labelled readings. Set \[ \Delta_H=(H^2+4)^2,\qquad B_Y(W)=\{i\in W:P^+(\core(Q_i))\le Y\}, \] where $P^+(1)=1$. The complement $G_Y(W)=W\setminus B_Y(W)$ will supply the free coordinates. \begin{lemma}[A common divisor pays for the separation]\label{lem:resultant} For distinct typed shifts $(t,d)$ and $(s,e)$, a common prime divisor of $(u+t)^2-d$ and $(u+s)^2-e$ divides the nonzero integer \[ R_{d,e}(t-s)=(t-s)^4-2(d+e)(t-s)^2+(d-e)^2. \] Moreover $|R_{d,e}(v)|\le(v^2+4)^2$. \end{lemma} \begin{proof} The displayed integer is the resultant of the two monic quadratics. They are irreducible over $\Q$, and equality of the monic polynomials would force equality of their typed shifts. They are therefore coprime. The resultant vanishes modulo any common prime divisor. The bound follows from $|d|,|e|\le2$. \end{proof} \begin{theorem}[Exact window fibre]\label{thm:fibre} Fix all prime signs $\kappa(q)$ for $q\le Y$, where $Y\ge\Delta_H$. The possible words $w\in\{-1,1\}^{W(u,H)}$ are exactly those satisfying \begin{equation}\label{eq:fibre} w_i=\kappa(\core(Q_i))\quad(i\in B_Y(W)). \end{equation} All other coordinates are jointly free. In particular, the fibre has cardinality $2^{|W|-|B_Y(W)|}$, equal to $2^{3H-|B_Y(W)|}$ when $u\ge2$. \end{theorem} \begin{proof} A reading in $B_Y(W)$ depends only on the prescribed head, so \eqref{eq:fibre} is necessary. Every other reading has an odd prime factor $q>Y$. By Lemma~\ref{lem:resultant}, this prime divides no other reading in the window, even to an even valuation. Choose one such prime for each free reading. These primes are distinct and can be flipped independently to realise any requested assignment. This also proves the statement for a window containing $n=1$, with the nonpositive reading omitted. \end{proof} The theorem fixes the whole prime head before the word is requested. It is not a statement that a typical source happens to give independent signs. With independent fair signs on the remaining primes, however, its free coordinates do indeed have the uniform joint law, conditionally on the head. \begin{proposition}[Optimal repair inside one window]\label{prop:repair-window} Let $h_0$ agree with the fixed head, and let $w$ satisfy \eqref{eq:fibre}. Let $J=\{i\in G_Y(W):w_i\ne h_0(Q_i)\}$. For $i\in J$ let $q_i^*$ be the largest prime of odd valuation in $Q_i$. For every $\sigma>0$, \[ \min_{\substack{h|_{q\le Y}=h_0|_{q\le Y}\\h(Q_i)=w_i\ (i\in W)}} \sum_{q:h(q)\ne h_0(q)}q^{-\sigma} =\sum_{i\in J}(q_i^*)^{-\sigma}. \] The smallest number of flipped primes is $|J|$. For an arbitrary requested word, the smallest residual Hamming error is its number of mismatches on $B_Y(W)$. \end{proposition} \begin{proof} The sets of odd prime factors above $Y$ belonging to different readings are disjoint. A changed free coordinate requires an odd, hence nonempty, set of flips in its own set. Its cheapest choice is the largest such prime. These choices affect no other reading, so all the individual lower bounds are attained together. Head-determined coordinates cannot be repaired, and every other coordinate can. \end{proof} The cost is at most $3H/Y^\sigma$, but a bound on the number of ordinary prime divisors would not prove this statement. For example, \[ 1393^2+1=2\cdot985^2=2\cdot5^2\cdot197^2. \] At $H=1$ and $Y=25$, the large prime $197$ supplies no freedom: the reading is determined by the sign at two. \subsection{How much of a window is forced?} \begin{corollary}[Average exceptional fraction]\label{cor:average-window} For $X\ge3$, $1\le H\le X$, and $Y\ge\Delta_H$, \[ \frac1X\sum_{X\le u<2X}\frac{|B_Y(W(u,H))|}{H} \ll \min\left(1,\frac{\log(2Y)}{\log(2X)}\right). \] Thus if $H=X^{o(1)}$ and $\log Y=o(\log X)$, all but $o(X)$ origins have $o(H)$ forced coordinates, in the usual quantitative sense obtained from Markov's inequality. \end{corollary} \begin{proof} Each positive labelled reading with index below $3X$ belongs to at most $H$ of the windows. The count of such readings with no odd prime factor above $Y$ is bounded by \eqref{eq:sieveone}; exempting an extra prime can only enlarge it. Divide the resulting bound by $XH$. \end{proof} For example, $H=\lfloor\exp(\sqrt{\log X})\rfloor$ and $Y=\Delta_H$ give $|B_Y(W)|\ll H(\log X)^{-1/4}$ outside $O(X(\log X)^{-1/4})$ origins. Every compatible repair on such a window has harmonic cost below $3/H^3$. The source may depend on the origin and the requested word. No simultaneous global assignment follows from this estimate. \subsection{Joining windows introduces parity, even without a cycle} Consider two disjoint $H$-windows, and fix all prime signs through $Y\ge\Delta_H$. A prime above $Y$ can have odd valuation at most once in each window. Construct a multigraph with the readings as vertices and one additional vertex $*$. A prime of odd valuation in exactly two readings gives an edge between them; a prime occurring oddly in exactly one reading gives an edge from it to $*$. Primes with no odd occurrence are irrelevant. A \emph{closed component} is a connected component not containing $*$; isolated reading vertices count as closed components. For a closed component $C$, define $k_C=\core(\prod_{i\in C}Q_i)$. Every prime factor of $k_C$ is at most $Y$. \begin{theorem}[Exact gluing criterion]\label{thm:gluing} A word on the union $W$ of the two windows extends to a source with the fixed head if and only if \begin{equation}\label{eq:closed} \prod_{i\in C}w_i=\kappa(k_C) \quad\text{for every closed component }C. \end{equation} If there are $c$ closed components, the fibre has size $2^{|W|-c}$. Its Hamming distance from an arbitrary word is exactly the number of violated equations in \eqref{eq:closed}. In particular, deleting one reading from each closed component is necessary and sufficient to leave all remaining coordinates jointly free. \end{theorem} \begin{proof} Relative to a reference assignment of tail signs, flipping a prime toggles the endpoints of its edge, with the coordinate at $*$ discarded. The incidence vectors of a connected graph over $\F_2$ span the even-weight vectors on its vertices. A spanning tree proves this directly by removing leaves. For a component containing $*$, discarding that coordinate leaves the full space on its reading vertices. For a closed component, the only restriction is its total parity. These restrictions are disjoint and yield exactly \eqref{eq:closed}. A violated component needs at least one changed coordinate, and changing one coordinate in each violated component suffices. If no coordinate is deleted from a closed component, its parity restriction persists; deleting one makes its projection unrestricted. \end{proof} A component can be a tree and still be closed. Consequently, counting cycles alone does not describe the obstruction to gluing. \begin{example}[Two free triples that do not glue freely]\label{ex:two-windows} Take the windows $n=9$ and $n=175$, each of width one, and $Y=25$. Their readings are \[ (82,83,79),\qquad(30626,30627,30623), \] with $30626=2\cdot15313$, $30627=3^2\cdot41\cdot83$, and $30623=113\cdot271$. Each triple is free after the head is fixed. In the union, however, the vertices $82,30627,83$ form a closed path with edge primes $41,83$. Its relation is \[ 82\cdot30627\cdot83=2\cdot10209^2. \] When $\kappa(2)=-1$, at least one of these three readings is negative. The full six-reading fibre has size $32$, although every pair projection is free. Flipping the signs at $82$ and $30627$ relative to a compatible word costs exactly $1/41$ in harmonic distance; flipping only the first is incompatible with the same head. \end{example} The numerical assertions in this example are checked by the accompanying verifier. Their explanation is the closed-path parity, not the computation. \subsection{The exact weighted repair problem} The optimisation mechanism is the classical minimum $T$-join and its reduction to matching in the shortest-path metric \cite{EJ}; see also \cite[Chapter~2]{Cornuejols}. The arithmetic assertion is that this minimum equals the cost of changing the actual tail-prime signs. Give the edge belonging to a prime $q$ the cost $q^{-\sigma}$, for fixed $\sigma>0$. Relative to a reference source, let $J$ be the reading coordinates to be toggled. Put $T=J$ if $|J|$ is even, and $T=J\cup\{*\}$ otherwise. \begin{proposition}[Repair as a minimum join]\label{prop:tjoin} A repair exists if and only if $J$ has even cardinality in every closed component. Its least prime cost is the minimum total edge cost of a subgraph whose odd-degree vertices are exactly $T$. \end{proposition} \begin{proof} Flipping primes is exactly selecting edges modulo two, so the incidence equation gives both necessity and sufficiency. Positive costs make any extraneous cycle removable. Pairing the odd vertices along paths in a feasible subgraph bounds its cost below by a minimum pairing in the shortest-path metric, separately in each component. Conversely, the symmetric difference of shortest paths for a pairing has the required odd vertices and costs no more than the sum of their lengths. This proves the equality with the minimum join formulation. \end{proof} This is a finite weighted optimisation identity, not a claim about exact numerical comparison of arbitrary irrational weights. For $\sigma=1$ all costs are rational. With three or more windows, a tail prime may meet three readings; the columns are then hyperedges, and the graph formula no longer applies. For instance, $41$ divides $9^2+1$, $11^2+2$, and $17^2-2$. % Original source: sections/04_partial.tex \section{One low-weight table passing all the partial tests}\label{sec:partial} Local freedom by itself allows a different word at every origin. We now keep \emph{one table} and satisfy all the window and pair tests at once. The construction uses square classes to make the pair conditions consistent, then makes a large prime head trivial to make the window conditions consistent. It does not impose all higher-order multiplicative relations. \subsection{Pair compatibility has an exact description} Fix a finite prime set $S$ and its signs $\kappa$. For $i\in I_N$, set \[ r_i=\prod_{\substack{q\notin S\\v_q(Q_i)\text{ odd}}}q, \qquad a_i=\prod_{q\in S}\kappa(q)^{v_q(Q_i)}. \] Two nonzero vectors over $\F_2$ are independent exactly when they are distinct. It follows that a table passes every one- and two-reading test if and only if \begin{equation}\label{eq:pairtable} w_i=a_i z_{r_i},\qquad z_1=1, \end{equation} where one arbitrary sign $z_r$ is chosen for each nontrivial exterior class. This is a common assignment to classes, not necessarily a character on their span. A relation among three different classes can still fail. The same observation gives a useful deletion statement. Write $R_r^{(S)}=\#\{i:r_i=r\}$. The smallest number of deletions that leaves every one- and two-reading projection free outside $S$ is \begin{equation}\label{eq:pairdeletion} b_S(N)=R_1^{(S)}+\sum_{r>1}(R_r^{(S)}-1)_+ \ll_\eps 2^{|S|}N^{2/3+\eps}. \end{equation} Indeed, delete every trivial exterior class and all but one representative of every other class. Necessity is immediate. For the bound, a trivial class has full square class supported on $S$, while a pair of equal exterior classes has product class supported on $S$. There are at most $2^{|S|}$ such full classes, and $r-1\le\binom r2$. Apply \eqref{eq:R} and Theorem~\ref{thm:pairs}. This bound is independent of the heights of the primes in $S$. \subsection{Choosing the orientations of the classes} \begin{theorem}[Quantitative common-table construction]\label{thm:partial} Let $N\ge2$, $1\le H\le N$, and let $S$ have $s$ elements. Prescribe $\kappa$ on $S$. If \[ Y\ge\max(2,\max S,\Delta_H), \] with $\max\varnothing=1$, a finite algorithm produces a table $w$ passing every $H$-window test and every pair test, with \begin{equation}\label{eq:partialweight} \#\{i:w_i=-1\}\ll N\min\left(1,\frac{\log(2Y)}{\log(2N)}\right) +C_\eps2^sN^{2/3+\eps} \end{equation} for every fixed $\eps>0$. Each test uses sources agreeing with the \emph{same} prescribed head on $S$. \end{theorem} \begin{proof} Extend the head to all primes through $Y$ by assigning $+1$ to primes not in $S$. The set \[ B_Y=\{i\in I_N:P^+(\core(Q_i))\le Y\} \] is a union of exterior classes, because every prime of $S$ is at most $Y$. Use \eqref{eq:pairtable}. For classes in $B_Y$ set $z_r=1$, including $r=1$. On every other class choose $z_r$ so that the number of negative values $a_i z_r$ is as small as possible, breaking ties by either fixed convention. The pair tests hold by construction. In each window the only coordinates forced by the enlarged head are those in $B_Y$, and they have exactly the required sign $a_i$. Theorem~\ref{thm:fibre} supplies a source for that window. The negative entries in $B_Y$ number at most $|B_Y|$, bounded by \eqref{eq:sieveone}. On a remaining exterior class, if the two head phases occur $R_+$ and $R_-$ times, the contribution is $\min(R_+,R_-)\le R_+R_-$. Each oppositely phased pair in the same exterior class has its full product class supported on $S$, with character value $-1$. There are at most $2^s$ possible full classes. Summing Theorem~\ref{thm:pairs} over them bounds all these minority contributions by the second term in \eqref{eq:partialweight}. All steps are finite: factor the readings, group their exterior classes, and choose their orientations. No efficient asymptotic factorisation algorithm is needed for the existence statement. \end{proof} For fixed $S$, $H=N^{o(1)}$, and $Y=\max(2,\max S,\Delta_H)$, choose a fixed $\eps<1/3$ to get weight $o(N)$. This proves the asymptotic part of Theorem~\ref{thm:intro-partial}. More generally, a moving head still works if $s\le(1/3-\eta)\log_2N$ for fixed $\eta>0$, $\log Y=o(\log N)$, and $0<\eps<\eta$. There is a direct limitation on proof systems using only these tests. Any inequality that is a valid consequence of precisely their feasible-set constraints must hold at the table in Theorem~\ref{thm:partial}. It cannot force a linear Hamming weight on all such tables. Allowing higher-degree algebraic consequences of the \emph{same} constraints does not remove an actual feasible point. This observation does not concern a system with additional prime variables and global relations that the table fails. In particular, the complete relations of \cite[Theorem~1.1]{PoulyReconstruction} may have logarithmic support cardinality without lying in any of the short windows tested here. \subsection{An explicit failure of global realisability} For $N=4096$, $H=2$, $S=\{2,3,5,7\}$, $\kappa(2)=-1$ and the other head signs positive, take $Y=64=\Delta_2$. The construction above, with positive orientation in ties, gives \begin{center} \begin{tabular}{lr}\toprule Quantity & Value\\\midrule Readings & $12287$\\ Exterior classes & $11930$\\ Head-determined readings & $177$\\ Negative head-determined readings & $103$\\ Other negative readings & $149$\\ Total negative readings & $252$\\\bottomrule \end{tabular} \end{center} There are $140$ nonfixed classes with both head phases. The negative counts on $n^2+1,n^2+2,n^2-2$ are respectively $90,94,68$. The verifier tests all $4095$ windows by binary linear algebra and all pair constraints by the exact exterior-class criterion. The entries at $3^2+2=11$, $9^2+2=83$, and $1752^2+2=2\cdot11\cdot83\cdot41^2$ are all positive. Their product is $2\cdot37433^2$, so any global source producing those entries would be positive at two. But the table's reading $1^2+1=2$ is negative. Thus the table has no global multiplicative source, even without an externally imposed head. This is a finite witness of incompatible global explanations. The asymptotic construction gives a possibly different table for each $N$ and does not claim that every resulting table is globally impossible. Neither assertion supplies a source attaining $m_2(N)=o(N)$. \subsection{Two complete traces still leave most individual readings ambiguous}\label{subsec:two-traces} Locality is not the only way to discard information. Even when two traces are known at \emph{every} index, the third retains many undetermined coordinates. The following fibre description is the trace part of \cite[Lemma~2.1]{PoulySelective}, applied to the quotient of two sources. We retain its short proof; the subsequent counting and rank bounds quantify what remains undetermined after a prime head is also fixed. \begin{proposition}[Exact fibre after two full traces]\label{prop:two-traces} Fix $d\in\D$. Two sources agree on all positive values of $Q_e$, $e\ne d$, if and only if they agree at every prime outside $\mathcal P_d^{\rm ex}$. The prime signs in $\mathcal P_d^{\rm ex}$ are arbitrary. \end{proposition} \begin{proof} An exclusive prime divides no value of the two retained quadratics, so changing its sign has no effect. Conversely, apply the quotient argument from Section~\ref{sec:intro}. The retained readings fix two, and also three whenever three is visible. If $q\ge5$ is the least visible prime with negative quotient sign, a centred root on a retained trace gives $Q_e(r)=qm$, $0Y$ divides at most one reading in a certificate, by Lemma~\ref{lem:resultant}. If $q\ne p$, its valuation there must therefore be even. Every reading of every certificate lies in the common set \[ \{(n,d)\in I_N:n\in A_d(N;Y,p)\}. \] Sum the unit-load inequalities over this set and apply \eqref{eq:sieveone}. Since $\log(2\Delta_H)\ll\log(2H)$, the result follows. \end{proof} For a probability law $\Pi_N$ on certificates with $\Pi_N\{C:i\in C\}\le K/N$ for every label, scaling by $N/K$ shows that \[ \Pi_N\{\text{width}(C)\le H\}\ll K\frac{\log(2H)}{\log(2N)}. \] Thus any such diffuse law places asymptotically negligible mass on subpolynomial widths. This is a necessary condition on a law, not a construction of one. Binary certificates have a stronger obstruction that does not restrict width: \begin{equation}\label{eq:binarycap} \Cap_p(\text{size}\le2)\le R_p(N)+T_p(N)\ll_\eps N^{2/3+\eps}. \end{equation} There is also an exact finite formula. The involution $\tau_p(a)=\core(pa)$ has no fixed point. Apart from the orbit $\{1,p\}$, the certificates between the classes $a$ and $\tau_p(a)$ form complete bipartite graphs. Since $R_1=0$, \begin{equation}\label{eq:binaryexact} \Cap_p(\text{size}\le2) =R_p(N)+\sum_{\{a,\tau_p(a)\}\ne\{1,p\}} \min(R_a(N),R_{\tau_p(a)}(N)), \end{equation} with one summand per orbit. The smaller side bounds the edge mass and can be fully matched. Deleting that side, and all class-$p$ singletons, is also the least deletion that destroys every binary certificate. This integer optimum remains only a lower bound for $m_p(N)$. \subsection{A trace used only once must meet a sieve exception} The supplementary laws of quadratic reciprocity give the visibility table \begin{center} \begin{tabular}{c c c c}\toprule $q\bmod8$ & $q\mid n^2+1$ possible & $q\mid n^2+2$ possible & $q\mid n^2-2$ possible\\\midrule $1$ & yes & yes & yes\\ $3$ & no & yes & no\\ $5$ & yes & no & no\\ $7$ & no & no & yes\\\bottomrule \end{tabular} \end{center} An exclusive prime is exclusive to a \emph{trace}, not necessarily to a single reading on it. \begin{theorem}[A singly represented trace]\label{thm:exclusive} Under unit loads, the total weight of certificates in which at least one trace is represented exactly once satisfies \[ \sum_{C:\exists d,\ |C\cap Q_d|=1}\alpha_C\ll\frac N{\sqrt{\log(2N)}}, \] uniformly in $p$, with no bound on the total size or width of a certificate. \end{theorem} \begin{proof} If $(n,d)$ is the only label of its trace in a certificate, each exclusive prime $q\ne p$ must have even valuation in $Q_d(n)$. Thus $n\in A_d^{\rm ex}(N;2,p)$. Every certificate under consideration meets the union of these three exceptional sets. Summing the loads on that union bounds the total mass by its size, and \eqref{eq:sievehalf} applies. \end{proof} In particular, all mixed triplets and all certificates of size at most five using all three traces have sublinear total capacity. The theorem does not exclude triplets contained in one trace, nor does it prove that six readings suffice for a positive density. A six-reading example explains the boundary of the argument: \begin{center} \begin{tabular}{c r l}\toprule Trace & Index & Reading\\\midrule $n^2+1$ & $2$ & $5$\\ $n^2+1$ & $13$ & $170=2\cdot5\cdot17$\\ $n^2+2$ & $1$ & $3$\\ $n^2+2$ & $11$ & $123=3\cdot41$\\ $n^2-2$ & $11$ & $119=7\cdot17$\\ $n^2-2$ & $17$ & $287=7\cdot41$\\\bottomrule \end{tabular} \end{center} Their product is $2\cdot73185^2$. The exclusive primes $5,3,7$ cancel within their respective traces, and $17,41$ join the pairs. Outside two the six square classes have rank five: the coordinates $5,3,7$ force equal coefficients within each pair, and $17,41$ force equality between pairs. Hence the full set is the only nonempty relation, and its target is two. There is no proper square or target-two subrelation. \subsection{A separate fixed-size improvement}\label{subsec:fixed-size} The width bound is uniform over all sizes. When the size is fixed, integral-point bounds give a different estimate that can be stronger at polynomial widths. \begin{theorem}[Bounded size and width]\label{thm:fixed-size} For every fixed $k\ge2$ and $\eps>0$, uniformly in $p$, $N\ge2$, and $1\le H\le N$, \[ \Cap_p(\text{size}\le k,\ \text{width}\le H) \ll_{k,\eps}\log(2N)+(H+1)^{k-1+\eps}. \] Thus widths $H\le N^\theta$ have capacity $o(N)$ whenever $\theta<1/(k-1)$. For each fixed width $H$, the capacity of \emph{all} certificates in that width is $O_H(\log(2N))$, uniformly in $p$. \end{theorem} \begin{proof} An anchored shape with $r\ge2$ readings gives \[ F(T)=\prod_{j=1}^r((T+t_j)^2-d_j),\qquad 0\le t_j0$, uniformly in $p,d$. The same upper bound holds for their capacity. If all these denominators use a common set of $o(\log N)$ primes, their number and capacity are $N^{o(1)}$. \end{theorem} \begin{proof} For a fixed denominator $b\le2N$, \eqref{eq:centre-norm} has norm $db^2$ and \[ 1\log N$, we have $N^{1/d}0$, uniformly in $a,b,d,e$. A library of $K$ exact-ratio rules supporting certificates under the preceding parity-pairing definition satisfies \[ \sum_C|C|\alpha_C\ll_\eta KN^\eta+\log(2N). \] A linear mass therefore requires $K\ge N^{1-o(1)}$ in the precise sense that $K\gg_\eta N^{1-\eta}$ for each fixed $\eta>0$ along such a family. \end{proposition} \begin{proof} If any link exists, reduction of the ratio implies $a,b\le N^2+2$. Eliminating the cofactor gives \[ (bn)^2-abm^2=b(bd-ae)=K_0. \] If $K_0=0$, positivity of the indices gives $bn^2=am^2$ and $bd=ae$. The only square ratio between elements of $\D$ is the identical one, forcing the identical label; there is no admissible link. Otherwise $|K_0|\ll N^4$, and $bn+m\sqrt{ab}\ll N^3$. Remove the square part of $ab$ and use Lemma~\ref{lem:norm}, including its factorised case, followed by the divisor bound. This proves the link count. Every reading of a supported certificate either belongs to one of these links or has no odd prime factor except possibly $p$. The latter readings have square class $p$ and number $O(\log(2N))$; square class one does not occur. Count the endpoints of the $K$ link sets and sum their unit loads. \end{proof} The exponent $\eta$ is fixed before $N$ tends to infinity. The final necessary condition does not result from substituting a varying $\eta(N)$ into an untracked constant. % Original source: sections/08_gap.tex \section{Capacity can miss most of the forced errors}\label{sec:gap} Every certificate gives an odd-parity constraint on actual signs. Replacing it by a positive covering inequality forgets part of that constraint. We first identify the resulting optimisation problem exactly, then realise large gaps using quadratic readings rather than an abstract binary matrix alone. \subsection{The integral obstruction and its fractional relaxation} Represent the square classes of a finite sample by rows $v_i\in\F_2^d$, and the target by a nonzero vector $t$. Then \begin{equation}\label{eq:binarymodel} \mu_t=\min_{x:\,t\cdot x=1}\wt((v_i\cdot x)_i), \qquad C\text{ is a certificate}\Longleftrightarrow\sum_{i\in C}v_i=t. \end{equation} Add a distinguished element $e$, represented by $t$, to the binary matroid represented by the vectors $v_i$ (viewed as columns). An inclusion-minimal certificate $C$ is exactly a set for which $C\cup\{e\}$ is a circuit containing $e$. Indeed, a zero-sum proper subset of $C$ could be removed, and a target-sum proper subset would contradict minimality. The converse is the same argument in reverse. Thus the minimal certificates form the \emph{port at $e$} of this binary matroid, in the terminology of Cornu\'ejols \cite[author's July 2000 notes, Section~8.3.1, p.~120]{Cornuejols}. Every certificate contains a minimal one. Replacing it by that subset preserves its weight and cannot increase any load; it also preserves disjointness in an integral packing. Hitting all minimal certificates is equivalent to hitting all certificates. Writing $\nu,\nu^*$ for integral and fractional packing and $\tau,\tau^*$ for integral and fractional covering of this port, the dictionary is \[ \Pack=\nu,\qquad \Cap=\nu^*=\tau^*,\qquad \mu=\tau. \] The middle equality is finite linear programming duality. The following standard separation argument proves the last equality directly in our sign notation. \begin{proposition}[Integral-cover interpretation]\label{prop:hitting} The minimum $\mu_t$ equals the smallest cardinality of a subset $B$ of readings that meets every certificate for $t$. \end{proposition} \begin{proof} The negative readings of an assignment with $t\cdot x=1$ meet every certificate. Conversely, if $B$ meets every certificate, $t$ is not in the span of the rows outside $B$. A linear functional can therefore vanish on that span and equal one on $t$. Its negative readings are contained in $B$. \end{proof} Thus all certificate inequalities with an integral cover retain the true minimum. Passing to the fractional cover, equivalently to the capacity by finite linear programming duality, is the relaxation at issue. The arithmetic constructions below exhibit its gap with the full family of certificates; Section~\ref{subsec:fifteen} makes the distinction explicit through an identity of signed products. \subsection{Realising odd binary rows on \texorpdfstring{$n^2+1$}{n squared plus one}} The criterion used here is classical. Lemmermeyer's nonresidue-graph formulation \cite[Section~5, Proposition~5.3]{Lemmermeyer} gives a norm-minus-one unit when every nontrivial bipartition of the prime-discriminant graph has an odd cross-degree. Our nonresidue conditions give a complete graph on an odd number of vertices, which has that property. When $2$ occurs, its prime-discriminant vertex is $8$, not $2$; for each odd $q\equiv5\pmod8$, the relevant symbols $(8/q)$ and $(q/2)$ are both $-1$. We keep the elementary proof below to obtain the integral equation in precisely our conventions, rather than infer integrality from a statement about units in a maximal order. \begin{lemma}[Classical odd nonresidue criterion, specialised]\label{lem:odd-pell} Let $q_0=2$, and choose distinct primes $q_1,\ldots,q_{d-1}\equiv5\pmod8$ with $\leg{q_i}{q_j}=-1$ for $i\ne j$, $i,j\ge1$. Every product $a$ of an odd number of distinct primes from this list admits positive integers $n,u$ with \[ n^2-au^2=-1. \] Such solutions give arbitrarily large, distinct $n$. \end{lemma} \begin{proof} The quadratic reciprocity law makes the pairwise nonresidue requirements symmetric, since all odd primes are $1$ modulo four; also $\leg2{q_j}=\leg{-2}{q_j}=-1$ and $\leg{-1}{q_j}=1$. The number $a$ is congruent to five modulo eight if it is odd, and to two modulo eight otherwise. Take the solution $X,Y>0$ of $X^2-aY^2=1$ with least $X$, whose existence is Lagrange's theorem \cite[Theorem~2.3]{Conrad}. Reduction modulo eight gives $X$ odd and $Y$ even. The consecutive coprime integers $(X-1)/2$ and $(X+1)/2$, of product $a(Y/2)^2$, have the form $br^2$ and $cs^2$ with $bc=a$. Thus \[ cs^2-br^2=1. \] If $b,c>1$, one contains an even number of the selected prime factors and the other an odd number. The even part contains an odd prime $\ell$. Every prime in the other part is a nonresidue modulo $\ell$, including two when present. Reducing the displayed equation modulo $\ell$, and using $\leg{-1}{\ell}=1$, would make the odd part a residue, a contradiction. Thus $b=1$ or $c=1$. If $c=1$, then $s^2-ar^2=1$ is a positive Pell solution with $sM/16,\qquad 1\le\Cap_2(A)<16. \] These values of the invariants are unchanged by restricting sources to the prescribed head. \end{theorem} \begin{proof} Put $d=\lfloor M/2\rfloor$, $t=\lfloor M/16\rfloor$, and choose the rows independently and uniformly from the odd-weight affine hyperplane of $\F_2^d$. For $x_0=1$, the all-ones vector $x$ produces $M$ negative readings. Every other such $x$ gives independent fair row evaluations. Writing $B(M,t)=\sum_{j=0}^t\binom Mj$, the probability that some such assignment has weight at most $t$ is bounded by \[ 2^{d-1-M}B(M,t). \] A sum of an even number of odd rows cannot equal $e_0$. A nonempty odd subset of rows sums uniformly over the odd affine hyperplane, so the probability that some certificate has size at most $t$ is at most \[ 2^{1-d}B(M,t). \] The binary entropy bound gives $B(M,t)\le2^{MH_2(1/16)}<2^{3M/8}$. The sum of the two failure probabilities is at most $(9/2)2^{-M/8}<1$ for $M\ge32$. There is therefore a matrix with minimum greater than $t$ and no certificate of size at most $t$. It has a certificate: otherwise separation of $e_0$ from the row span would give an assignment of weight zero. Thus its capacity is at least one. Summing the unit loads gives \[ (t+1)\sum_C\alpha_C\le\sum_C|C|\alpha_C\le M, \] so the capacity is at most $M/(t+1)<16$, while the minimum is at least $t+1>M/16$. Corollary~\ref{cor:realisation} transfers this entire finite model to the required readings and head. \end{proof} The probability argument selects a finite matrix, not a random multiplicative source in the conclusion. Large integrality gaps are a familiar combinatorial phenomenon; the point here is their realisation on a single quadratic trace with all actual source assignments preserved. \subsection{A fifteen-reading model in which signed multiplication does more}\label{subsec:fifteen} The classical binary character model on a four-dimensional vector space makes the lost information visible without an optimisation solver. Its role here is its exact realisation by the subsequent quadratic values, not a new abstract coding construction. In $\F_2^5$, let $W$ be the even-weight subspace, of dimension four, and take the fifteen rows \[ v_t=e_0+t,\qquad 0\ne t\in W. \] No row is the target, and every certificate has odd size, hence at least three. For distinct nonzero $t,u$, the triple $\{t,u,t+u\}$ is a certificate. There are $35$ such triples, each vertex lies in seven, and giving each weight $1/7$ gives capacity five. The size lower bound gives the reverse inequality $\Cap\le15/3=5$. For an actual source with target sign $-1$, write its reading signs as $Z_t=-\chi(t)$, where $\chi$ is a character of $W$. A nontrivial character is positive on seven of the fifteen nonzero vectors and negative on eight. Thus the error minimum is seven, attained by any nontrivial character; the trivial character gives fifteen errors. Equivalently, with $S=\sum_{t\ne0}Z_t$, \begin{equation}\label{eq:fifteen-square} Z_tZ_u=-Z_{t+u}\quad(t\ne u),\qquad S^2=15-14S. \end{equation} Hence $S=1$ or $-15$, and the number of errors is seven or fifteen. Corollary~\ref{cor:realisation} makes this model arithmetic. An explicit realisation with basis primes $2,5,13,37,557$ is included in \sourcefile{data/fifteen_readings.csv}; each identity $n_i^2+1=a_i u_i^2$ is checked exactly. Equation~\eqref{eq:fifteen-square} uses the signs of the products, not only the inequalities saying that each target triple contains an error. It explains how seven errors can be forced while the capacity of \emph{all} certificates is five. % Original source: sections/09_graphs.tex \section{Quadratic positivity can retain information that capacity loses}\label{sec:graphs} The previous example used a signed quadratic identity. Graphs give a reusable form of that mechanism, and show that it can coexist with the absence of information in many small observation sets. \subsection{Graph cuts realised by quadratic readings} Let $G=(V,E)$ be a finite simple graph. Choose the prime $2$ and one prime $q_v$ for each vertex as in Lemma~\ref{lem:odd-pell}. Realise each edge $uv$ by a distinct reading \[ A_{uv}=n_{uv}^2+1=2q_uq_v b_{uv}^2. \] For $h(2)=-1$, put $s_v=h(q_v)$. The edge reading is $Z_{uv}=-s_us_v$, and therefore \begin{equation}\label{eq:graphminimum} \mu_2(A)=|E|-\MaxCut(G) =\min_{s\in\{-1,1\}^V}\frac14\sum_{uv\in E}(s_u+s_v)^2. \end{equation} An edge subset is a target-two certificate exactly when it is Eulerian and has odd cardinality: every vertex prime cancels, while two remains odd. Every such subgraph contains an odd cycle. Replacing a certificate by an odd cycle contained in it cannot increase a load. Consequently \begin{equation}\label{eq:oddcycle-cap} \Cap_2(A)=\text{fractional packing value of the odd cycles of }G. \end{equation} These equalities use all source assignments and all certificates on the sample. The matrix inequality behind graph cuts is classical: see Delorme--Poljak \cite{DP} and the semidefinite primal--dual formulations in Goemans--Williamson \cite[Section~4]{GW}. We use its equivalent form for monochromatic edges, with an additional budget on the multiplicative readings. In particular, the following weighted inequality does not require independent vertex signs. Suppose positive integers $a_v$ and labelled readings $Q_{i(e)}$ satisfy \[ Q_{i(e)}t_e^2=p\,a_ua_v r_e^2\quad(e=uv). \] Give edges weights $w_e\ge0$ with $\sum_{e:i(e)=i}w_e\le1$ for every reading. Let $Q_w=D_w+A_w$ be the weighted signless Laplacian. If $Q_w-\diag(b_v)$ is positive semidefinite, then for every $h(p)=-1$, \begin{equation}\label{eq:weighted-positive} E_N(h)\ge\frac14\sum_v b_v, \end{equation} provided the readings lie in $I_N$. Indeed, with $s_v=h(a_v)$, the weighted error sum is $\frac14s^TQ_ws$, while $s_v^2=1$. Shared prime factors between the $a_v$ do not affect this argument. Formula~\eqref{eq:weighted-positive} is a sufficient input for a proof on a prefix; no family of that strength on the full prefix is constructed here. \subsection{Bounded-degree samples with a growing gap} For a $d$-regular graph whose least adjacency eigenvalue is at least $-\rho$, \eqref{eq:graphminimum} gives \[ \mu_2(A)\ge\frac{|V|(d-\rho)}4 =\frac{|E|}{2}\left(1-\frac\rho d\right). \] If the girth is $g$, then every certificate has at least $g$ edges, so $\Cap_2(A)\le |E|/g$. The classical nonbipartite six-regular Ramanujan graphs provide an infinite family with \[ g>\frac23\log_5|V|,\qquad\lambda_{\min}\ge-2\sqrt5. \] We use the \emph{starting graph} of Alon--Ganguly--Srivastava \cite[beginning of Section~3]{AGS}, where this input is explicitly attributed to the Lubotzky--Phillips--Sarnak construction \cite{LPS}. Their subsequently modified graph is not the input here. With $M=3|V|$ edges, arithmetic realisation gives \begin{equation}\label{eq:graphgap} \mu_2(A)\ge\frac{3-\sqrt5}{6}M>\frac M{12}, \qquad 1\le\Cap_2(A)<\frac{3M}{2\log_5(M/3)}. \end{equation} Each free prime occurs in exactly six reading classes. The numerical inequality can also be witnessed rationally: if $A_G$ is the adjacency matrix, then $A_G+5I$ is positive definite, and \[ \frac14s^T(6I+A_G)s =\frac M{12}+\frac14s^T(A_G+5I)s. \] A rational $LDL^T$ decomposition of the positive definite rational matrix gives a finite sum-of-squares certificate. This is degree two in the \emph{prime sign variables}, not a degree-two consequence in unconstrained reading signs. \subsection{Why forest observations do not see the target sign} Take the vertex signs independently and fairly, and consider either target sign $\sigma=h(2)$. The readings on edges are $\sigma s_us_v$. On every forest these readings are independent and fair under either value of $\sigma$: choose a root sign in each component, and the edge signs then determine all other vertex signs bijectively. It follows that fewer than $g$ distinct edge readings cannot distinguish the two target signs, even when each queried edge is chosen from the preceding answers. At every step the queried set is a forest, and the next new edge is conditionally fair under both hypotheses. Re-reading an edge gives the same sign, not fresh randomness. This local indistinguishability is compatible with \eqref{eq:graphgap}; the latter uses the entire graph's prime-sign structure. \subsection{A finite graph with exact capacity and exact error minimum} The Hoffman--Singleton graph supplies a compact exact example. Use vertices $P_{i,j}$ and $Q_{i,j}$ for $i,j\in\F_5$. Join $P_{i,j}$ to $P_{i,j+1}$, $Q_{i,j}$ to $Q_{i,j+2}$, and $P_{i,j}$ to $Q_{k,ik+j}$ for all $k$. Edges are undirected. This is the usual pentagon--pentagram construction \cite{Brouwer}. It has $50$ vertices and $175$ edges. If $A$ is its adjacency matrix and $J$ the all-ones matrix, direct counting gives \[ A^2=6I-A+J. \] Set $C=5A+15I-J$. Then $C^2=25C$ and $C\mathbf1=0$. For every sign vector $s$, \begin{equation}\label{eq:HS} \frac14s^T(7I+A)s =50+\frac{\norm{Cs}^2}{500}+\frac{(\sum_v s_v)^2}{20}. \end{equation} Assigning $+1$ to every $P$-vertex and $-1$ to every $Q$-vertex attains fifty monochromatic edges, so the graph's actual error minimum is fifty. The matrix identity says that adjacent vertices have no common neighbour and distinct nonadjacent vertices have exactly one. Thus there are no triangles or quadrilaterals. For an edge $uv$, each of the $6\cdot6$ choices $a\in N(u)\setminus\{v\}$ and $b\in N(v)\setminus\{u\}$ has a unique common neighbour $c$, giving a pentagon $u,a,c,b,v$. Conversely every pentagon through $uv$ arises this way. Each edge therefore belongs to $36$ pentagons, and the total number is $175\cdot36/5=1260$. Weight $1/36$ on every pentagon gives an odd-cycle packing of mass $35$. Every odd cycle has length at least five, so the total load gives the reverse bound $175/5=35$. Thus its arithmetic realisations satisfy \[ \Cap_2(A)=35<\mu_2(A)=50. \] The accompanying finite verifier constructs the graph, enumerates its pentagons, and checks both matrix identities in integer arithmetic. The transfer to $175$ distinct integer readings is the existence result of Corollary~\ref{cor:realisation}; a list of those $175$ potentially enormous indices is not supplied or claimed to have been generated. % Original source: sections/10_composition.tex \section{Two families compose without loss; five need not}\label{sec:composition} One can force errors by first writing the target prime class as a sum of several pivot classes. If the target sign is negative, at least one pivot is negative, and a disjoint family for that pivot already forces its full error count. Converting \emph{all} the pivot families into direct certificates for the target is a stronger requirement. We now separate these two operations. \subsection{A lossless theorem for two families} \begin{theorem}[Two-family composition]\label{thm:twofamilies} Let $a,b$ be square classes with $a+b=t\ne0$. On a common labelled sample, let $\mathcal A$ be a family of $M_a$ internally disjoint pairs of class $a$, and $\mathcal B$ a family of $M_b$ internally disjoint pairs of class $b$. The families may overlap each other. Their existing labels contain at least $\min(M_a,M_b)$ disjoint certificates of class $t$, each of size two or four. The construction uses only a traversal of the two listed matchings. It introduces no new reading and does not increase the largest index when the sample is arithmetic. \end{theorem} \begin{proof} Truncate both families to the same size $M=\min(M_a,M_b)$. Their union is an edge-coloured graph of maximum degree two. The colours alternate along every component. There is no edge in both families, because $a\ne b$. Two endpoints at distance two along a component have class $a+b=t$. An alternating cycle has length divisible by four: summing all its edge classes gives $(\text{length}/2)t=0$. Partition each consecutive block of four vertices into its two distance-two pairs. A cycle with $4k$ edges thus gives $2k$ disjoint target pairs. For a path with $L$ edges, partition successive blocks of four vertices in the same way. The four residue classes give the following outputs: \begin{center} \begin{tabular}{c c c}\toprule $L$ & Target pairs already obtained & Unused data\\\midrule $4k$ & $2k$ & one vertex\\ $4k+1$ & $2k$ & one edge of the majority colour\\ $4k+2$ & $2k+1$ & one vertex\\ $4k+3$ & $2k+2$ & none\\\bottomrule \end{tabular} \end{center} For $L=4k+2$, the last three vertices contribute their distance-two pair. Let $b_a,b_b$ count the paths of length $1$ modulo four whose majority colours are $a,b$, and let $g_a,g_b$ count those of length $3$ modulo four. Equality of the two total colour counts gives \[ b_a+g_a=b_b+g_b. \] The target pairs already obtained number \[ M+\frac{g_a+g_b-b_a-b_b}{2}. \] Pair a reserved $a$-edge with a reserved $b$-edge. Their four vertices form a target certificate; reserved edges lie in distinct components and are disjoint from all previous outputs. This adds $\min(b_a,b_b)$ certificates. The new total is \[ M+\min(g_a,g_b)\ge M. \] All steps inspect each listed edge a bounded number of times. \end{proof} The size-four output cannot simply be suppressed. The four readings at indices $5,57,4,13$ of $n^2+1$ are $26,3250,17,170$. The first pair has class five, the second class ten, and their product has class two. No proper subset has class two; the direct output must use all four readings. The theorem consequently cannot be iterated by treating its output as another family of pairs. \subsection{Sixteen readings with three different invariants}\label{subsec:sixteen} Start with independent classes $a,e_1,\ldots,e_5$ and target $t=e_1+\cdots+e_5$. Use the sixteen readings indexed by subsets $S\subseteq\{1,\ldots,5\}$ of size at most two, with class \begin{equation}\label{eq:sixteen-classes} v_S=a+\sum_{j\in S}e_j. \end{equation} For each $i$, there are five disjoint pairs of class $e_i$: \[ \{\varnothing,\{i\}\},\qquad \{\{j\},\{i,j\}\}\quad(j\ne i). \] If $h(t)=-1$, at least one $h(e_i)$ is negative, so its five pairs force at least five errors. The assignment $h(a)=+1$ and $h(e_i)=-1$ for every $i$ attains exactly five, namely the singleton vertices. Thus $\mu_t=5$. Every target certificate has even cardinality, because its $a$-coordinate must cancel. It has no size-two instance, since the symmetric difference of two sets of size at most two cannot be all five indices. Hence its size is at least four, giving $\Cap_t\le16/4=4$. The reverse bound has a symmetric fractional witness. The target quartets fall into three types according to their subset sizes: \begin{center} \begin{tabular}{c r c}\toprule Sizes & Number & Weight per quartet\\\midrule $(0,1,2,2)$ & $15$ & $1/15$\\ $(1,1,1,2)$ & $10$ & $1/20$\\ $(1,2,2,2)$ & $50$ & $1/20$\\\bottomrule \end{tabular} \end{center} The first type partitions the five indices into a singleton and two pairs; the second chooses three singletons and their complementary pair. For the third, fix its singleton $i$. Its three pair-edges must have odd degree at the other four indices and even degree at $i$. They are either a three-edge star on the other four vertices (four choices), or a two-edge path centred at $i$ and a disjoint edge (six choices). This gives ten quartets per singleton. The empty vertex has load $15/15=1$. A singleton has loads $3/15$, $6/20$, and $10/20$, again summing to one. A pair vertex has loads $3/15$, $1/20$, and $15/20$; the last count follows either directly or by symmetry from $50\cdot3/10=15$. All loads are one, and the total weight is four. Therefore $\Cap_t=4$. Three disjoint certificates are \begin{align*} &\{\varnothing,1,23,45\},\\ &\{2,3,4,15\},\\ &\{5,12,13,14\}, \end{align*} where strings denote subsets. Four disjoint certificates would each have size four and partition all sixteen readings. But the sum of all sixteen classes is $t$: each $e_i$ occurs five times and $a$ occurs sixteen times. The sum of four target certificates would instead be $4t=0$. Thus $\Pack_t=3$. \begin{theorem}[Five-family obstruction on actual readings]\label{thm:fivefamilies} There are sixteen distinct values $n_S^2+1$, all with $n_S<10^{35}$, and five internally disjoint families of five pairs each, whose target classes sum to $\cl2$, such that \[ \Pack_2=3<\Cap_2=4<\mu_2=5. \] All three invariants use the full family of certificates on the sixteen labels. \end{theorem} \begin{proof} Use the independent prime basis $2,5,13,17,29,37$ and set \[ a=\cl{58},\quad (e_1,e_2,e_3,e_4,e_5) =(\cl{754},\cl{1073},\cl{3770},\cl{18241},\cl{170}). \] Their sum is $\cl2$. Independence follows, for example, from the reverse expressions \[ \cl2=\sum_i e_i,\quad \cl5=e_1+e_3,\quad \cl{13}=a+e_1, \quad\cl{17}=e_2+e_4,\quad\cl{29}=a+\cl2,\quad\cl{37}=e_2+\cl{29}. \] Appendix~\ref{app:witness} gives explicit positive integers $n_S,u_S$ and squarefree $c_S$ with $n_S^2+1=c_Su_S^2$ and $\cl{c_S}=v_S$. The indices are distinct and below the stated bound. This realises exactly the model \eqref{eq:sixteen-classes}, so all three values just proved carry over. The source negative precisely at $2,13,29$ among these six basis primes attains the five-error minimum. \end{proof} The numerical witness can be checked entirely by integer multiplication, binary elimination, and rational load sums. No numerical linear-programming tolerance is required. One may replicate every square class $R$ times at distinct indices by odd powers of its negative-Pell solution. Every source then has exactly $R$ copies of its old errors, giving $\mu_2=5R$. Lifting the quartet weights uniformly over all choices of copies gives capacity $4R$, and the size-four lower bound gives the reverse inequality. There are five pair families of size $5R$, and at least $3R$ disjoint direct certificates. We do not assert that the integral packing is exactly $3R$ after replication. The obstruction does not classify three or four pair families, nor special families with additional arithmetic structure. It also leaves the five-error conclusion intact: one negative pivot supplies its own five disjoint pairs. For the same reason it is compatible with \cite[Theorem~1.3 and Section~5]{PoulyReconstruction}. That amplification selects a negative pivot and uses its family; it does not require simultaneous conversion of all pivot families into direct certificates for the target prime. % Original source: sections/11_conclusion.tex \section{What a quantitative reconstruction argument must still supply}\label{sec:conclusion} The obstructions proved here refer to three different operations. Restricting a table to windows or pairs can lose global multiplicative coherence. Restricting certificates to a narrow geometry or a small transport library can lose capacity. Replacing an integral cover by its fractional relaxation can lose part of the true error minimum even when \emph{every} certificate is available. The first operation is measured by the common-table construction, not by separate examples at different windows. The second is measured by unit loads on actual labels, not by the number of formal identities. The third is witnessed by real quadratic values, but on selected samples whose heights are not controlled by their cardinality. These distinctions explain why none of the negative results is a construction with $m_p(N)=o(N)$. They also leave several precise possibilities open. A proof of a polynomial or linear lower bound for $m_p(N)$ could use genuinely global relations that the partially compatible tables fail. It could construct a sufficiently diverse nonlocal family with its loads paid at the original height. Or it could exploit positivity on actual prime signs, as in \eqref{eq:weighted-positive}, rather than insist that certificate capacity equal the minimum. The selected graph samples show that the last mechanism can be stronger; they do not supply its missing full-prefix arithmetic input. For composition, the two-family theorem gives a height-preserving positive result. The five-family example shows why that result is not a general associativity principle. Determining what additional structure permits further lossless composition is a separate question from improving the growth rate of $m_p(N)$. \paragraph{Finite data and reproducibility.}\label{sec:repro} The reproducibility bundle is supplied inside the published source archive on Zenodo, \url{https://doi.org/10.5281/zenodo.23319030}. It contains the manuscript sources, frozen bibliography, standard-library Python checks, and reference CSV/JSON files. After extracting the ZIP, run \begin{quote}\small\ttfamily python3 checks/reproduce.py \end{quote} This command rebuilds the finite data in an isolated temporary directory, compares all generated files byte for byte with the reference data, and runs the additional finite checks of the logarithmic baseline. It does not overwrite the supplied reference files. The expected principal outputs are: \begin{center}\small \begin{tabular}{@{}p{.36\textwidth}p{.59\textwidth}@{}} \toprule Instance & Expected exact checks\\ \midrule Table with $N=4096$, $H=2$ & $12\,287$ readings, $252$ negatives, $4\,095$ feasible windows; every pair covered by the exterior-class criterion\\[3pt] Fifteen quadratic readings & $1\,024$ target subsets; $\Cap=5$, $\mu=7$\\[3pt] Sixteen quadratic readings & $1\,024$ target subsets, $75$ quartets; $\Pack=3$, $\Cap=4$, $\mu=5$\\[3pt] Hoffman--Singleton graph & $50$ vertices, $175$ edges, $1\,260$ pentagons; $\Cap=35$, $\mu=50$\\ \bottomrule \end{tabular} \end{center} The small gluing and centre examples are checked as well. For the graph, only the graph and matrix witnesses are generated, not its $175$ Pell indices. Neither these tests nor the baseline checks prove asymptotic estimates. The archive manifest identifies this data revision and its files; SHA-256 hashes and reproduction commands are included in the published bundle. \paragraph{AI assistance and responsibility.} GPT-6 Astra assisted the research development, calculations, proof drafting, source consultation, and preparation of the original manuscript and checker. GPT-6 Astra Pro assisted the reviews and revisions, including bibliographic cross-checks, proof exposition, and reproducibility packaging. The revision history is recorded in the source archive. The supplied reviews are AI reports, not human mathematical endorsements. The finite checker has been rerun for this edition; no Lean formalisation or independent human verification is claimed. The author is responsible for the submitted manuscript. Computational agreement concerns only the explicit finite objects and does not certify originality or the external theorems used in the proofs. \appendix % Original source: sections/appendix_rank.tex \section{Full freedom in logarithmic windows}\label{app:rank} The mesoscopic fibre theorem identifies exactly which coordinates remain forced after a large head is fixed. With a smaller head and a logarithmic number of readings, a different argument can show that \emph{all} coordinates are free at almost every origin. This is not a consequence of the average exceptional-fraction bound, which permits a small nonzero number of forced coordinates. Let $\mathcal T$ be a set of $m$ distinct typed shifts $(t,d)$, with $0\le t\le N$ and $d\in\D$. Let $S$ contain $s$ primes of arbitrary heights, and let \[ v^S_{t,d}(n)=\bigl(v_q((n+t)^2-d)\bmod2\bigr)_{q\notin S}. \] \begin{theorem}[A growing full-rank window]\label{thm:log-rank} For all sufficiently large $N$, uniformly when $m+s\le\log_2N$, \[ \#\{2\le n\le N:\rank_{\F_2}(v^S_{t,d}(n))_{(t,d)\in\mathcal T}0$ and $B_0\ge2$, there is a set of primes $\Gamma\subset(B_0,\infty)$ and a single source \[ h(n)=\beta_2(n)(-1)^{\sum_{q\in\Gamma}v_q(n)} \] such that \[ \sum_{q\in\Gamma}q^{-1/2}<\eps,\qquad \sum_{q\in\Gamma}q^{-t}<\infty\quad\text{for every }t>0. \] Every finite word over $\mathcal A$ has a positive natural frequency in $a_h$, and its logarithmic frequency is the same. The empirical stationary measure is ergodic, has rational discrete spectrum, and has entropy zero. Its support is nevertheless the full shift, whose topological entropy is $\log8$. Each individual trace has mean zero; in particular $E_N(h)=(3/2+o(1))N$. \end{theorem} \begin{proof} We first record a uniform continuity bound. For any two sources $f,g$, the fraction of origins $2\le n\le X+1$ where their words of width $L$ differ is at most \begin{equation}\label{eq:word-continuity} C_L\sum_{q:f(q)\ne g(q)}q^{-1/2},\qquad C_L=3L(2L+6). \end{equation} A disagreement requires a changed prime dividing one of the $3L$ readings. An odd prime has at most two roots modulo $q$, so meets at most $2X/q+2$ origins per reading. If it meets any, then $q\le(X+L)^2+2\le(L+2)^2X^2$, and $2/q+2/X\le(2L+6)/\sqrt q$. The prime two satisfies the same upper bound. Union over the primes and readings proves \eqref{eq:word-continuity}. A source with finitely many negative primes gives a rationally almost periodic sequence: truncate the valuations of those primes at a large exponent to obtain a periodic approximation, with disagreement density tending to zero. Simple roots modulo odd prime powers have density at most $2/q^k$; the valuation at two in these traces is already zero or one. Every finite word then has a frequency. If a word of width $L$ occurs at $r$, it persists on the progression modulo \[ W=\prod_{q\text{ negative}}q^{1+\max_{0\le j0$, eventually $\sigma_j\le t$, so the same summable stage bounds prove $\sum_\Gamma q^{-t}<\infty$. The total half-power cost is at most $b_0<\eps$. By \eqref{eq:word-continuity}, $a_h$ is a limit in disagreement density of finite-support, hence periodically approximable, sequences. Periodic approximation makes the frequency of every fixed word a Cauchy limit. Its logarithmic frequency agrees by summation by parts. For the word $w_j$, the tail can remove a density at most $C_{L_j}b_j$, leaving \[ \nu_h(w_j)\ge1/W_j-C_{L_j}b_j\ge1/(2W_j)>0. \] The word frequencies are not uniform in $j$ and are not equal to $8^{-L_j}$. Each finite-support $h_j$ is negative at two and at finitely many odd primes. In a periodic valuation truncation, the odd-prime conditions are independent of the parity of the index by the Chinese remainder theorem. The sign supplied by two alternates on each trace, so each trace mean is zero. Remove the truncation and then use \eqref{eq:word-continuity} to pass to $h$. The structural conclusion is the classical theorem on rationally almost periodic sequences \cite[Theorem~1.7]{BKLR}: their empirical measure is ergodic with rational discrete spectrum. In this example the reason can also be seen directly. On the profinite integers with Haar measure, translation by one is ergodic with rational discrete spectrum. For each fixed shift, $\sum_{q\in\Gamma}2/q<\infty$ makes the odd-prime correction a well-defined measurable product almost everywhere. It codes a factor of this rotation. Finite-support Chinese-remainder calculations and \eqref{eq:word-continuity} identify its cylinder laws with the empirical frequencies just constructed. Here is a direct entropy bound. If a periodic sequence of period $T$ approximates $a_h$ in disagreement density at most $\delta<1/2$, take a stationary limiting coupling with its phase. A block of length $m$ is specified by the phase, its error positions, and at most seven alternative symbols at each error. With base-two entropy, \[ H_\mu(a(0),\ldots,a(m-1)) \le\log_2T+m\bigl(H_2(\delta)+\delta\log_2 7\bigr). \] Divide by $m$, let $m$ tend to infinity, and then let $\delta$ decrease to zero. This proves zero measured entropy. Every one of the $8^m$ words has positive frequency, so the language is the full shift and its topological entropy is $\log8$. \end{proof} The distinction between topological and measured entropy in rationally almost periodic systems is classical; see also \cite[Section~3.1]{BKLR}. The construction above realises it simultaneously on these three traces with a protected head and a support summable in every positive power. The dependence can be visible already at distance one. The density $\Delta_d$ where $h(Q_d(n))$ differs from $\beta_2(Q_d(n))$ satisfies \[ \Delta_d\le\sum_{q\in\Gamma}\frac{\rho_d(q)}{q+1} \le2\sum_{q\in\Gamma}\frac1q<2\eps, \] where $\rho_d(q)$ is the number of roots of $Q_d$ modulo $q$. The local factor $\rho_d(q)/(q+1)$ is obtained by summing the odd valuation probabilities of the simple roots. The finite-support formula passes to $\Gamma$ using \eqref{eq:word-continuity}, not an uncontrolled infinite sum of congruence errors. Since each $\beta_2$ trace alternates, \[ \lim_{X\to\infty}\frac1X\sum_{n=2}^{X+1}h(Q_d(n))h(Q_d(n+1)) \le-1+4\Delta_d<-1+8\eps. \] Thus positive frequencies for every word, even with balanced one-coordinate marginals, do not imply independent or Bernoulli statistics. % Original source: sections/appendix_witness.tex \section{The sixteen-reading arithmetic witness}\label{app:witness} The row labels refer to the subsets used in Section~\ref{subsec:sixteen}. The two tables give $n_S^2+1=c_Su_S^2$ exactly. Splitting the indices and square factors into separate tables keeps the integers legible. \begin{center}\small \begin{tabular}{r r r}\toprule $S$ & $c_S$ & $n_S$\\\midrule $\varnothing$ & 58 & 99\\ 1 & 13 & 18\\ 2 & 74 & 43\\ 3 & 65 & 8\\ 4 & 1258 & 114669\\ 5 & 2465 & 34208\\ 12 & 13949 & 505872859718\\ 13 & 290 & 17\\ 14 & 237133 & 37467803169731567258356998326647518\\ 15 & 2210 & 47\\ 23 & 69745 & 8539575550866247307711088\\ 24 & 986 & 157\\ 25 & 3145 & 1344783432\\ 34 & 1185665 & 918139433921728\\ 35 & 442 & 21\\ 45 & 185 & 68\\\bottomrule \end{tabular} \end{center} \begin{center}\small \begin{tabular}{r r}\toprule $S$ & $u_S$\\\midrule $\varnothing$ & 13\\ 1 & 5\\ 2 & 5\\ 3 & 1\\ 4 & 3233\\ 5 & 689\\ 12 & 4283214685\\ 13 & 1\\ 14 & 76941780537374507308269877334405\\ 15 & 1\\ 23 & 32335512290115324082601\\ 24 & 5\\ 25 & 23979605\\ 34 & 843194258497\\ 35 & 1\\ 45 & 5\\\bottomrule \end{tabular} \end{center} The exact verifier finds $1024$ target-two subsets, of sizes $4,6,8,10,12,16$, in numbers $75,216,435,232,65,1$ respectively. These counts are an additional finite check; the proofs of $\Pack=3$, $\Cap=4$, and $\mu=5$ in Section~\ref{subsec:sixteen} do not require exhaustive enumeration. The CSV file includes the same square factors and classes, and the fractional packing file lists all $75$ quartets with their rational weights. % Original source: references.bbl % Frozen, locally typeset bibliography. No BibTeX executable is required. \begin{thebibliography}{23} \pdfbookmark[1]{References}{bibliography} \bibitem{AGS} N. Alon, S. Ganguly, and N. Srivastava. \emph{High-girth near-Ramanujan graphs with localized eigenvectors}. \href{https://arxiv.org/abs/1908.03694v1}{arXiv:1908.03694v1}, 2019. Input: the unmodified starting graph at the beginning of Section 3, attributed there to Lubotzky--Phillips--Sarnak. \bibitem{ABP} P. Alvanos, Y. Bilu, and D. Poulakis. Characterizing algebraic curves with infinitely many integral points. \emph{International Journal of Number Theory} \textbf{5}(4) (2009), 585--590. \href{https://doi.org/10.1142/S1793042109002274}{doi:10.1142/S1793042109002274}. Locators: \href{https://arxiv.org/abs/0907.2097v1}{arXiv:0907.2097v1}, introduction and Theorem 1.2. \bibitem{BF} M. Bardestani and T. Freiberg. \emph{Mertens's theorem for splitting primes and more (A concise and adaptable proof of Hardy)}. \href{https://arxiv.org/abs/1309.7482v1}{arXiv:1309.7482v1}, 2013. Theorem 3.3; only fixed-modulus progressions are used. \bibitem{BKLR} V. Bergelson, J. Ku{\l}aga-Przymus, M. Lema{\'n}czyk, and F. K. Richter. Rationally almost periodic sequences, polynomial multiple recurrence and symbolic dynamics. \emph{Ergodic Theory and Dynamical Systems} \textbf{39}(9) (2019), 2332--2383. \href{https://doi.org/10.1017/etds.2017.130}{doi:10.1017/etds.2017.130}. Locators: \href{https://arxiv.org/abs/1611.08392v2}{arXiv:1611.08392v2}, Theorem 1.7 and Section 3.1. \bibitem{BWX} R. de la Bret\`eche, V. Y. Wang, and M. W. Xu. \emph{Random Multiplicative Functions and Making Squares from Polynomial Values}. \href{https://arxiv.org/abs/2607.06398v1}{arXiv:2607.06398v1}, 2026. Lemmas 3.1--3.4, equation (13), and Proposition 5.1. \bibitem{Brouwer} A. E. Brouwer. \href{https://aeb.win.tue.nl/graphs/Hoffman-Singleton.html}{\emph{Hoffman--Singleton graph}}. Author's graph notes, pentagon--pentagram construction; accessed 27 September 2026. \bibitem{CCDN} W. Castryck, R. Cluckers, P. Dittmann, and K. H. Nguyen. The dimension growth conjecture, polynomial in the degree and without logarithmic factors. \emph{Algebra \& Number Theory} \textbf{14}(8) (2020), 2261--2294. \href{https://doi.org/10.2140/ant.2020.14.2261}{doi:10.2140/ant.2020.14.2261}. Locator: Theorem 3 of \href{https://arxiv.org/abs/1904.13109v1}{arXiv:1904.13109v1}. \bibitem{CS} J. Chinis and B. Shala. Random Chowla's conjecture for Rademacher multiplicative functions. \emph{Transactions of the American Mathematical Society} \textbf{378} (2025), 8025--8053. \href{https://doi.org/10.1090/tran/9457}{doi:10.1090/tran/9457}. Locators: \href{https://arxiv.org/abs/2409.05952v2}{arXiv:2409.05952v2}, Lemmas 2.4--2.5 and proof. \bibitem{Conrad} K. Conrad. \href{https://kconrad.math.uconn.edu/blurbs/ugradnumthy/pelleqn1.pdf}{\emph{Pell's Equation, I}}. Author's notes, Theorem 2.3 and multiplication of solutions; accessed 27 September 2026. \bibitem{Cornuejols} G. Cornu\'ejols. \emph{Combinatorial Optimization: Packing and Covering}. CBMS-NSF Regional Conference Series in Applied Mathematics 74, SIAM, 2001. \href{https://doi.org/10.1137/1.9780898717105}{doi:10.1137/1.9780898717105}. The port definition is in the \href{https://www.researchgate.net/publication/245695625_Combinatorial_Optimization_Packing_and_Covering}{author's July 2000 notes}, Section 8.3.1, p.~120; this locator refers to those notes, not the SIAM pagination. \bibitem{DP} C. Delorme and S. Poljak. Laplacian eigenvalues and the maximum cut problem. \emph{Mathematical Programming} \textbf{62} (1993), 557--574. \href{https://doi.org/10.1007/BF01585184}{doi:10.1007/BF01585184}. \bibitem{EJ} J. Edmonds and E. L. Johnson. Matching, Euler tours and the Chinese postman. \emph{Mathematical Programming} \textbf{5} (1973), 88--124. \href{https://doi.org/10.1007/BF01580113}{doi:10.1007/BF01580113}. \href{https://research.ibm.com/publications/matching-euler-tours-and-the-chinese-postman}{Author-institution record}. \bibitem{ES} J.-H. Evertse and J. H. Silverman. Uniform bounds for the number of solutions to $Y^n=f(X)$. \emph{Mathematical Proceedings of the Cambridge Philosophical Society} \textbf{100}(2) (1986), 237--248. \href{https://doi.org/10.1017/S0305004100066068}{doi:10.1017/S0305004100066068}. Theorem 1(b); \href{https://ir.cwi.nl/pub/1788/1788D.pdf}{original text in the CWI repository}. \bibitem{GW} M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. \emph{Journal of the ACM} \textbf{42}(6) (1995), 1115--1145. \href{https://doi.org/10.1145/227683.227684}{doi:10.1145/227683.227684}. \href{https://math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf}{Author's copy}, Section 4, especially Sections 4.2--4.3. \bibitem{HB} D. R. Heath-Brown. The square sieve and consecutive square-free numbers. \emph{Mathematische Annalen} \textbf{266}(3) (1984), 251--259. \href{https://doi.org/10.1007/BF01475576}{doi:10.1007/BF01475576}. \bibitem{Kedlaya} K. S. Kedlaya. \emph{Notes on analytic number theory}. \href{https://kskedlaya.org/ant/chap-selberg.html}{Chapter 13: The Selberg sieve}, especially Theorem 13.1 and (13.2.3). Author's online notes; accessed 27 September 2026. \bibitem{Lemmermeyer} F. Lemmermeyer. \emph{Higher Descent on Pell Conics. I. From Legendre to Selmer}. \href{https://arxiv.org/abs/math/0311309}{arXiv:math/0311309}, 2003. Section 5, Proposition 5.3. \bibitem{LPS} A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. \emph{Combinatorica} \textbf{8} (1988), 261--277. \href{https://doi.org/10.1007/BF02126799}{doi:10.1007/BF02126799}. The specialised starting-graph statement is located in \cite[Section~3]{AGS}. \bibitem{MSW} L. M\'erai, I. E. Shparlinski, and A. Winterhof. Character sums over sparse elements of finite fields. \emph{Bulletin of the London Mathematical Society} \textbf{56}(4) (2024), 1488--1510. \href{https://doi.org/10.1112/blms.13008}{doi:10.1112/blms.13008}. Input: Lemma 3.1 of \href{https://arxiv.org/abs/2211.08452v1}{arXiv:2211.08452v1}. \bibitem{Milne} J. S. Milne. \href{https://www.jmilne.org/math/CourseNotes/ANT.pdf}{\emph{Algebraic Number Theory}}. Version 3.08, 19 July 2020. Chapters 3--5, especially Propositions 4.1--4.2. \bibitem{DLMF} National Institute of Standards and Technology. \emph{Digital Library of Mathematical Functions}. \href{https://dlmf.nist.gov/27.12}{Section 27.12: Asymptotic formulas---primes}, equations (27.12.5) and (27.12.8), and the preceding statement of Dirichlet's theorem. Accessed 27 September 2026. \bibitem{PoulyReconstruction} B. Pouly. \emph{Arithmetic reconstruction and error recovery from three quadratic traces}. Zenodo, 2026. \href{https://doi.org/10.5281/zenodo.23317860}{doi:10.5281/zenodo.23317860}. Theorems 1.1 and 1.3, and Section 5. \bibitem{PoulySelective} B. Pouly. \emph{Selective normality and algebraic rigidity of multiplicative traces}. Zenodo, 2026. \href{https://doi.org/10.5281/zenodo.23318326}{doi:10.5281/zenodo.23318326}. Lemma 2.1. \end{thebibliography} \end{document}