Lehmer: source and evidence

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

1 \chapter{An exact computation workbook}
2 \label{app:computation-workbook}
3 
4 This appendix gives calculations that a reader can reproduce without trusting a status flag. The objects are the normalized coefficients of $\Delta$, the auxiliary shell polynomials, and one rational transfer certificate at $31$. Each calculation ends at its actual mathematical boundary. Agreement of finite outputs does not supply the missing all-prime nonvanishing argument.
5 
6 The complete integer inputs and outputs are in the companion evidence archive. Paths below are relative to its extracted project root. A JSON integer remains an integer even when it has many digits. An encoded rational pair $[a,b]$ means $a/b$, with a nonzero denominator. Converting these objects to floating point before checking an equality changes the contract.
7 
8 \section{Three engines and one coefficient shift}
9 \label{sec:workbook-engines}
10 
11 Write
12 \[
13  F(q)=\frac{\Delta(q)}q=\prod_{k\ge1}(1-q^k)^{24}
14       =\sum_{m\ge0}f_mq^m.
15 \]
16 Then $f_0=1$ and $\tau(n)=f_{n-1}$. This shift is essential. A program that stores $\tau(0)=0$ as a sentinel must not confuse that entry with the constant coefficient $f_0$.
17 
18 For direct product expansion, terms of degree at most $m$ depend only on factors with $k\le m$. The exact binomial expansion
19 \[
20  (1-q^k)^{24}=\sum_{j=0}^{24}(-1)^j\binom{24}{j}q^{kj}
21 \]
22 therefore supplies a finite algorithm for each desired coefficient. Three short calculations are
23 \begin{align*}
24  f_1&=-24,\\
25  f_2&=\binom{24}{2}-24=276-24=252,\\
26  f_3&=-\binom{24}{3}+(-24)(-24)-24\\
27     &=-2024+576-24=-1472.
28 \end{align*}
29 The last line comes respectively from the $q^3$ term in the first factor, the product of its $q$ term with the second factor's $q^2$ term, and the third factor's $q^3$ term. Thus it computes $\tau(4)$, not $\tau(3)$.
30 
31 The logarithmic derivative provides a different exact engine. With $\sigma_1(j)=\sum_{d\mid j}d$, comparison of coefficients in
32 \[
33  q\frac{F'(q)}{F(q)}=-24\sum_{j\ge1}\sigma_1(j)q^j
34 \]
35 gives
36 \begin{equation}
37  m f_m=-24\sum_{j=1}^{m}\sigma_1(j)f_{m-j}
38  \qquad(m\ge1).
39  \label{eq:workbook-divisor-recurrence}
40 \end{equation}
41 For $m=3$, the divisor sums are $1,3,4$. Hence
42 \[
43  f_3=-8\bigl(252+3(-24)+4\bigr)=-8\cdot184=-1472.
44 \]
45 An implementation should check that the numerator in \eqref{eq:workbook-divisor-recurrence} is divisible by $m$, rather than rounding the quotient.
46 
47 Jacobi gives a third engine. Put $T_j=j(j+1)/2$ and $a_j=(-1)^j(2j+1)$. The series
48 \[
49  A(q)=\prod_{k\ge1}(1-q^k)^3=1+\sum_{j\ge1}a_jq^{T_j}
50 \]
51 satisfies $F=A^8$. The identity $AqF'=8FqA'$ yields
52 \begin{equation}
53  m f_m=\sum_{\substack{j\ge1\\T_j\le m}}
54           a_j(9T_j-m)f_{m-T_j}.
55  \label{eq:workbook-triangular-recurrence}
56 \end{equation}
57 At $m=3$, only $T_1=1$, $T_2=3$ contribute. Its numerator is
58 \[
59  (-3)(9-3)(252)+5(27-3)(1)=-4536+120=-4416.
60 \]
61 Division by $3$ again gives $-1472$. The direct product, divisor recurrence and triangular recurrence reach the same integer through different algebraic operations.
62 
63 \Needspace{11\baselineskip}
64 \begin{center}
65 \begin{tabular}{r r r r}
66 \toprule
67 $m$ & $f_m=\tau(m+1)$ & $m$ & $f_m=\tau(m+1)$\\
68 \midrule
69 0 & $1$ & 5 & $-6048$\\
70 1 & $-24$ & 6 & $-16744$\\
71 2 & $252$ & 7 & $84480$\\
72 3 & $-1472$ & 8 & $-113643$\\
73 4 & $4830$ & 9 & $-115920$\\
74 \bottomrule
75 \end{tabular}
76 \end{center}
77 
78 The current independent comparison covers every $\tau(n)$ for $1\le n\le512$. The historical final-arithmetic run's direct-product comparison stopped at $128$, while the packet-tree run compared through $512$. These are different documented ranges. The new three-engine table supplies its own bound and does not infer one from an older summary.
79 
80 \section{Reconstructing the auxiliary polynomial}
81 \label{sec:workbook-polynomial}
82 
83 For a packet $v$, set $c_i=(v_i-i)/5$ and form
84 \[
85  P_v(T)=\prod_{0\le i<j\le4}\bigl((i-j)+T(c_i-c_j)\bigr).
86 \]
87 Its physical value is $P_v(5)=288W(v)$. Summing the full shell gives
88 \[
89  P_n(T)=\sum_{v\in\Vn}P_v(T)=\sum_{j=0}^{10}B_jT^j,
90  \qquad P_n(5)=288\tau(n).
91 \]
92 The polynomial has a different variable from the prime index. A root in $T$ or in a rescaled variable does not represent a nearby prime coefficient.
93 
94 For a nonzero $P_n$, use the convention $v_5(0)=+\infty$ and define
95 \[
96  \mu_n=\min_j\bigl(j+v_5(B_j)\bigr),\qquad
97  G_n(U)=5^{-\mu_n}P_n(5U)=\sum_{j=0}^{10}C_jU^j.
98 \]
99 Every $C_j=B_j5^{j-\mu_n}$ is an integer. The power of $5$ should be removed only after verifying divisibility for each coefficient. Since $288$ is a $5$-adic unit,
100 \begin{equation}
101  v_5(\tau(n))=\mu_n+v_5(G_n(1)).
102  \label{eq:workbook-normalized-valuation}
103 \end{equation}
104 All coefficients in the next two tables are exact integers from the freshly reproduced shell data. They allow a reader to check the normalization and every displayed residue without re-enumerating a large shell.
105 
106 \section{The simple branch at 499}
107 \label{sec:workbook-499}
108 
109 At $n=499$ the shell has $500$ packets. Of their weights, $262$ are positive and $238$ negative. Their sum is
110 \[
111  \tau(499)=-108877719272500.
112 \]
113 The minimum layer valuation is $\mu_{499}=3$.
114 
115 \Needspace{17\baselineskip}
116 \begin{center}
117 \begingroup\small
118 \setlength{\tabcolsep}{5pt}
119 \begin{tabular}{r r r r}
120 \toprule
121 $j$ & $B_j$ in $P_{499}$ & $C_j$ in $G_{499}$ & $j+v_5(B_j)$\\
122 \midrule
123 0 & $144000$ & $1152$ & 3\\
124 1 & $-360000$ & $-14400$ & 5\\
125 2 & $1063040$ & $212608$ & 3\\
126 3 & $28418240$ & $28418240$ & 4\\
127 4 & $-148872808$ & $-744364040$ & 4\\
128 5 & $209474504$ & $5236862600$ & 5\\
129 6 & $2422451240$ & $302806405000$ & 7\\
130 7 & $16445000$ & $10278125000$ & 11\\
131 8 & $8107402848$ & $25335633900000$ & 8\\
132 9 & $-11893316304$ & $-185833067250000$ & 9\\
133 10 & $-1160632800$ & $-90674437500000$ & 12\\
134 \bottomrule
135 \end{tabular}
136 \endgroup
137 \end{center}
138 
139 Summing the second coefficient column and using the normalization checks gives
140 \begin{align*}
141  P_{499}(5)&=-31356783150480000=288\tau(499),\\
142  G_{499}(1)&=-250854265203840.
143 \end{align*}
144 Reducing the normalized coefficients gives
145 \begin{align*}
146  G_{499}(U)&\equiv2+3U^2\pmod5,\\
147  G_{499}(U)&\equiv2+8U^2+15U^3+10U^4\pmod{25}.
148 \end{align*}
149 The first polynomial has the simple roots $1$ and $4$ modulo $5$. At $U=1$, the exact sum is $10$ modulo $25$ and its derivative is $1$ modulo $5$. Consequently
150 \[
151  G_{499}(1+5h)\equiv10+5h\pmod{25}.
152 \]
153 The five possibilities are $10,15,20,0,5$ as $h$ runs from $0$ to $4$. The root in the branch $U\equiv1\pmod5$ therefore lifts to $U=16\pmod{25}$.
154 
155 This lifted root is not the physical target. The target remains $U=1$, where $v_5(G_{499}(1))=1$. Formula \eqref{eq:workbook-normalized-valuation} gives $v_5(\tau(499))=3+1=4$.
156 
157 The following exact root history records both simple branches. Each entry lies between $0$ and $5^k-1$ and evaluates to zero modulo $5^k$. Consecutive entries agree modulo the preceding power. These conditions are stronger than displaying an approximate root.
158 
159 \Needspace{18\baselineskip}
160 \begin{center}
161 \begin{tabular}{r r r r}
162 \toprule
163 $k$ & $5^k$ & Root reducing to $1$ & Root reducing to $4$\\
164 \midrule
165 1 & 5 & 1 & 4\\
166 2 & 25 & 16 & 4\\
167 3 & 125 & 41 & 54\\
168 4 & 625 & 541 & 554\\
169 5 & 3125 & 3041 & 2429\\
170 6 & 15625 & 9291 & 14929\\
171 7 & 78125 & 9291 & 77429\\
172 8 & 390625 & 165541 & 233679\\
173 9 & 1953125 & 1337416 & 1014929\\
174 10 & 9765625 & 7196791 & 1014929\\
175 11 & 48828125 & 7196791 & 20546179\\
176 12 & 244140625 & 153681166 & 215858679\\
177 \bottomrule
178 \end{tabular}
179 \end{center}
180 
181 The fixed degree $10$ does not impose a universal ceiling on the valuation of polynomial values at varying inputs. A simple $5$-adic root supplies arbitrarily accurate integer approximations. That observation concerns the auxiliary variable. It neither changes the value at $1$ nor supplies interpolation of the prime-indexed family.
182 
183 \section{The double branch at 16249}
184 \label{sec:workbook-16249}
185 
186 At $16249$ the shell contains $16250$ packets, with $8284$ positive and $7966$ negative weights. The exact coefficient is
187 \[
188  \tau(16249)=133116215274958169206250.
189 \]
190 Here $\mu_{16249}=4$. The full coefficient table is as follows.
191 
192 \Needspace{17\baselineskip}
193 \begin{center}
194 \begingroup\small
195 \setlength{\tabcolsep}{4pt}
196 \begin{tabular}{r r r r}
197 \toprule
198 $j$ & $B_j$ in $P_{16249}$ & $C_j$ in $G_{16249}$ & $j+v_5(B_j)$\\
199 \midrule
200 0 & $4680000$ & $7488$ & 4\\
201 1 & $-13320000$ & $-106560$ & 5\\
202 2 & $-199541600$ & $-7981664$ & 4\\
203 3 & $-26375464320$ & $-5275092864$ & 4\\
204 4 & $737398074300$ & $737398074300$ & 6\\
205 5 & $-39838758304992$ & $-199193791524960$ & 5\\
206 6 & $-746041848478320$ & $-18651046211958000$ & 7\\
207 7 & $-6990990388478280$ & $-873873798559785000$ & 8\\
208 8 & $21389931029028020$ & $13368706893142512500$ & 9\\
209 9 & $-64003552771660728$ & $-200011102411439775000$ & 9\\
210 10 & $3937759175521630080$ & $61527487117525470000000$ & 11\\
211 \bottomrule
212 \end{tabular}
213 \endgroup
214 \end{center}
215 
216 The exact sums are
217 \begin{align*}
218  P_{16249}(5)&=38337469999187952731400000,\\
219  G_{16249}(1)&=61339951998700724370240.
220 \end{align*}
221 The first equals $288\tau(16249)$, and the second equals the first divided by $625$. Modulo $5$, the normalized polynomial is
222 \[
223  3+U^2+U^3=(U-1)^2(U-2).
224 \]
225 Modulo $25$, the table gives
226 \[
227  G_{16249}(U)\equiv13+15U+11U^2+11U^3+15U^5.
228 \]
229 Thus $G_{16249}(1)\equiv15\pmod{25}$ while $G'_{16249}(1)\equiv0\pmod5$. For every integer or $5$-adic integer $h$, polynomial Taylor expansion gives
230 \[
231  G_{16249}(1+5h)\equiv G_{16249}(1)+5hG'_{16249}(1)
232                     \equiv15\pmod{25}.
233 \]
234 Terms of order at least two have a factor $25$. This is a uniform obstruction throughout that residue branch, not merely the observation that five trial inputs fail. Every input congruent to $1$ modulo $5$ has normalized valuation exactly $1$.
235 
236 The other residual root should not be discarded. At $U=2$, the normalized value is $5$ modulo $25$ and its derivative is $1$ modulo $5$. That simple branch lifts to $22$ modulo $25$. The conclusion is that the double branch at $1$ does not lift, rather than that the polynomial has no $5$-adic roots anywhere.
237 
238 At the physical input $1$, the coefficient valuation is $4+1=5$. The two examples have different root geometry but both settle their actual target value by an exact modulo-$25$ calculation.
239 
240 \section{A first failure needs a domain}
241 \label{sec:workbook-valuation-domain}
242 
243 The tested auxiliary equality was
244 \[
245  v_\ell(\tau(p))=v_\ell(p+1),
246  \qquad p\ne\ell,\quad\ell\mid(p+1),\quad p\text{ prime}.
247 \]
248 The complete search through $150000$ contains $13848$ primes. The following counts refer to the indicated candidate sets, not to every prime without a residue condition.
249 
250 \Needspace{11\baselineskip}
251 \begin{center}
252 \begingroup\small
253 \begin{tabular}{r r r r r r}
254 \toprule
255 $\ell$ & First $p$ & $v_\ell(\tau(p))$ & $v_\ell(p+1)$ & Candidates & Discrepancies\\
256 \midrule
257 2 & 81919 & 20 & 14 & 13847 & 1\\
258 3 & 8747 & 8 & 7 & 6941 & 5\\
259 5 & 499 & 4 & 3 & 3451 & 50\\
260 \bottomrule
261 \end{tabular}
262 \endgroup
263 \end{center}
264 
265 The exact decisive values, including the discrepancy in the opposite $5$-adic direction, are
266 \begin{align*}
267  \tau(499)&=-108877719272500,\\
268  \tau(1249)&=27757672778617250,\\
269  \tau(8747)&=348766170858826454196,\\
270  \tau(81919)&=-904107824789465028682055680.
271 \end{align*}
272 For example, $1250=2\cdot5^4$, while the second integer has $5$-adic valuation $3$. Hence a proposed one-sided lift $v_5(\tau(p))\ge v_5(p+1)$ also fails at this actual prime.
273 
274 These four coefficients were checked independently by the Eisenstein convolution. If $\sigma_r(n)=\sum_{d\mid n}d^r$, the coefficient of $(E_4E_8-E_6^2)/1728$ is obtained from
275 \begin{align*}
276 1728\tau(n)={}&240\sigma_3(n)+480\sigma_7(n)+1008\sigma_5(n)\\
277  &+115200\sum_{k=1}^{n-1}\sigma_3(k)\sigma_7(n-k)\\
278  &-254016\sum_{k=1}^{n-1}\sigma_5(k)\sigma_5(n-k).
279 \end{align*}
280 This computes the selected integers without the triangular recurrence. The numerator is divided exactly by $1728$. The replay checks this independent formula for $1\le n\le128$ and at the four displayed primes, giving $132$ checks.
281 
282 The phrase ``first failure'' has two limits. It concerns the ordered search in its declared candidate set, and its exhaustive range ends at $150000$. A larger prime may supply another failure. The displayed nonzero integers refute an auxiliary valuation identity, not Lehmer's conjecture.
283 
284 \section{Reading the rational transfer at 31}
285 \label{sec:workbook-transfer}
286 
287 The degree-at-most-$22$ certificate has six coarse sectors and sixteen fine sectors. Both correction matrices have eighteen columns. Let
288 \[
289  A\in\Z^{6\times16},\quad
290  M_c\in\Z^{6\times18},\quad M_f\in\Z^{16\times18}.
291 \]
292 The fine-to-coarse parent map completely specifies $A$: its column $j$ has a $1$ in the parent row and zero elsewhere. The original fine masses are given below. Let $s_f$ denote their sixteen-entry column vector. Indices start at $0$.
293 
294 \Needspace{15\baselineskip}
295 \begin{center}
296 \begin{tabular}{r r r @{\qquad} r r r}
297 \toprule
298 $j$ & Parent & Fine mass & $j$ & Parent & Fine mass\\
299 \midrule
300 0 & 0 & $2354352$ & 8 & 0 & $-11844448$\\
301 1 & 2 & $-19467448$ & 9 & 1 & $-7162848$\\
302 2 & 4 & $-832048$ & 10 & 0 & $-31156048$\\
303 3 & 4 & $15074752$ & 11 & 2 & $4356352$\\
304 4 & 4 & $1881152$ & 12 & 2 & $32821152$\\
305 5 & 5 & $4248552$ & 13 & 2 & $1262352$\\
306 6 & 5 & $7759752$ & 14 & 0 & $-7455448$\\
307 7 & 4 & $-31808448$ & 15 & 3 & $-12874848$\\
308 \bottomrule
309 \end{tabular}
310 \end{center}
311 
312 For instance, row $0$ aggregates fine indices $0,8,10,14$:
313 \[
314  2354352-11844448-31156048-7455448=-48101592.
315 \]
316 The six coarse masses are therefore
317 \[
318  s_c=(-48101592,-7162848,18972408,
319       -12874848,-15684592,12008304)^t.
320 \]
321 Their sum, and the sum of the fine masses, is $-52843168$. These original masses differ in order from the lexicographic orbit bars because the certificate orders the residue-sector keys.
322 
323 The full machine certificate is
324 \begin{center}\small
325 \path{evidence/computation/replays/transport/p31_transport_certificate.json}.
326 \end{center}
327 It supplies an $18\times13$ rational matrix $N$ whose columns form a basis of $\ker M_c$, and the detail matrix $B=M_fN$ of size $16\times13$. The basic exact checks are
328 \[
329  AM_f=M_c,\quad As_f=s_c,\quad M_cN=0,
330  \quad B=M_fN,\quad AB=0.
331 \]
332 The last equation shows that a detail correction changes no coarse mass.
333 
334 The rational row-reduction results are
335 \[
336  \rank M_c=5,\qquad\rank M_f=15,\qquad\rank B=10.
337 \]
338 An independent check obtains the same lower bounds over both prime fields $\mathbb F_{65537}$ and $\mathbb F_{1000003}$. Every denominator used in a reduction is invertible there. A nonzero minor in either field proves a nonzero rational minor after clearing denominators.
339 
340 The corresponding upper bounds have direct structural explanations. Each correction matrix has column sum zero, giving bounds $5$ and $15$. Every row of $A$ has a nonempty, disjoint support, so $\rank A=6$ and $\dim\ker A=10$. Since $AB=0$, the detail rank is at most $10$. The upper and lower bounds establish the displayed ranks exactly.
341 
342 The coarse coefficient vector $a\in\Q^{18}$ makes
343 \[
344  x=s_f+M_fa,\qquad Ax=(0,0,0,0,0,-52843168)^t.
345 \]
346 The certificate then chooses a coefficient vector $d\in\ker M_c$. Its final fine vector $y=x+M_fd$ is zero except at index $6$, where it equals $-52843168$.
347 
348 One parent gives a concrete view of this second stage. Parent $5$ has fine children $5,6$. Just after the coarse stage their values are
349 \begin{align*}
350  x_5&=-\frac{161598180629860124657534386744}
351                  {23300823161076013875625},\\
352  x_6&=-\frac{1069691132209170737342448593256}
353                  {23300823161076013875625}.
354 \end{align*}
355 Their exact sum is $-52843168$. The detail stage adds $-x_5$ to child $5$ and $x_5$ to child $6$, giving $(0,-52843168)$ in that parent. All other parents retain their zero totals. This is a rational conservation calculation, not a numerical near-zero test.
356 
357 To verify the whole certificate, parse the rational pairs, check the matrix dimensions, verify all five identities, and compare both stored stages entry by entry. Then check $M_cd=0$ and the single surviving final entry. The script \path{code/check_transport_certificate.py} performs the independent equality and prime-field checks.
358 
359 This example does not assume a uniform rank theorem. Nor does full rank prove a uniformly nonzero survivor. At a shell whose original total were zero, complete zero-total transfer could still leave every final mass zero. At $31$ the separately computed exact total is nonzero, so the displayed survivor is authenticated for this one shell.
360 
361 \section{Reproducing a run and interpreting its record}
362 \label{sec:workbook-manifests}
363 
364 From the extracted source-set root, a new independent coefficient run is requested with
365 \begin{lstlisting}[basicstyle=\ttfamily\small,breaklines=true,frame=single,rulecolor=\color{Soft}]
366 python3 code/run_replays.py tau_independent \
367   --output-root evidence/computation/reader_coefficients
368 \end{lstlisting}
369 The destination must be fresh. The launcher refuses to replace an existing run directory. Omitting the suite name requests the complete declared sequence of suites. For that complete reproduction, use a fresh destination such as \path{evidence/computation/reproduced}. The large modular comparison consumes the newly generated dyadic result in that same destination, so these dependent suites belong in their declared order.
370 
371 A version $2$ manifest records the actual argument vector, exact arithmetic domain, semantic bounds, software versions and executed limits. Its \texttt{input\_artifacts} contain input checksums before and after execution. Its \texttt{declared\_results} name the scientific files the child must create. Output checksums cover those files and the execution logs.
372 
373 Three questions remain separate. Did execution finish within its limits with unchanged inputs and all required outputs? Does the code implement the intended finite assertion? Does a proof show that the finite assertion decides the universal claim? An exit code of zero answers only part of the first question.
374 
375 The count $704$ means $22$ selected modulus examples times $32$ exponents, not $704$ distinct primes. Of $24$ selected moduli, $11$ and $19$ had no observed matching prime through $10000$. That finite absence does not contradict positive density. The $24576$ synthetic cases mean $256$ moduli times three trace parameters times $32$ exponents. Their parameter $p=5M-1$ need not be prime, and their trace is not asserted to equal $\tau(p)$.
376 
377 A checksum pins bytes. Run provenance records execution. A timeout records an execution limit. A reproduced obstruction can refute its stated auxiliary implication while leaving Lehmer unchanged. Attach each exact calculation to a claim of the correct scope.

Back to source controls

Back to Lehmer: source and evidence