Machine-level form of the community construction at (PR #6453)
OpenIntMul.Kappa.pr6453_machineThere are one deterministic multitape Turing machine , in the model of Def_IntMul_MultitapeModel, a real exponent saving , and constants , , such that
- for every and every pair of -bit strings , the machine halts on input with the output , in some finite number of steps; and
- the number of steps is at most
for every , where .
This is the machine-level form of the community construction whose exponent saving is — PR #6453 of CrocSwap/integer-mult-bounds, a third group-1091 anchor stacked on the clean mixed-root composition of PR #6417. In the source, that construction is a finite certificate stated conditionally on five inherited framework assumptions: the all-width native claims, the owned-erasure discipline, the compiler, the precision tape, and analytic recovery. None of these is a statement about a Turing machine, while the campaign's formal goal is the full bound with no assumed framework. This node is the transcription of those five assumptions, together with the construction's own cost invoices, into the machine and cost model of Def_IntMul_MultitapeModel.
The statement allows a polylogarithmic overhead and a saving strictly above the advertised , which is the form in which any recursive multiplication algorithm's cost analysis terminates: the block bookkeeping produces the logarithmic factor, and the exponent margin is what absorbs it. Applied through the platform lemma IntMul.Kappa.kappaBound_of_polylog_slack, this node yields IntMul.Kappa.KappaBound (0.003287014).
Certificate data. The construction is pinned at the head of PR #6453, b1a3e525793eca35c56324aa7ffd0b714cf606d4 of ChaloupeMusic/integer-mult-bounds (a fork of CrocSwap/integer-mult-bounds; the branch is third-anchor-clean-mixed-root, a direct child of PR #6417's head df683ace130c83ca8caaa301b027a247a46e4ea8). Its certificate research/p104-third-anchor-clean-mixed-root/RESULT.json records the saving exactly as , the tested value , the parent value , and the exact crossing interval . The pricing step is a rank-moment inequality: for the productive-target and paid-call rank histograms of the word, whose surplus is in rank mass.Progress: the arithmetic of the certificate is formalised. Four nodes now carry it. Pr6453.moment_kappa_gt (https://prove2.me/theorems/36f216ad-14c6-4d36-afda-aaf01c1951d7) proves the price inequality at with certified margin . Pr6453.invoice (https://prove2.me/theorems/6243e969-8639-4d7a-8c57-4f61bc066f05) shows that the word's invoice — the closed form and the event fold — produces exactly those histograms, so the inequality is attached to the invoice rather than to two given lists. Pr6453.outer_ledger (https://prove2.me/theorems/b55a79fc-facd-45b8-9f1e-523b0f691859) checks the nine cost margins of the outer ledger against the saving, each with its exact slack. Pr6453.recursion (https://prove2.me/theorems/bcf0475e-6277-4e75-8b59-6c5de4245316) composes them: the price inequality is exactly the contraction ratio being below one, and then the whole call tree costs at most times its root, with the exponent unchanged and the bound uniform in the depth. What remains for this node is the construction which makes the costs actually contract at that ratio: the recursive call tree of the word, its scheduling and precision analysis, and the assembly of the machine in IntMul.MultitapeTM.
Progress: the strictification tail and the compiler grid are in too. Pr6453.strictification (https://prove2.me/theorems/dd08f776-ee36-433b-b6a4-5e4f4782e50c) proves the block checks at the printed constants — , , , , , the absorbed tail and its coarse counterpart exceeding as a negative control, with and test exponent . The three tail ratios are defined but not yet bounded: they are ratios of the two rank moments at the shifted exponents and , which needs the moment enclosure rerun there.
Progress: the strictification layer is now closed. Pr6453.tail_ratios (https://prove2.me/theorems/983393b8-8850-4fb6-8e7a-4ea63950dfdf) proves the three tail ratios at the certificate's constants: , , , from the shifted moments of Pr6453.shifted_lower and Pr6453.shifted_upper and the split bounds , . With Pr6453.strictification this completes the strictification and compiler block. One specification defect was found and corrected on the way: writing the split as (12 : ℝ) ^ (1 / 7) gives a natural exponent, 1/7 = 0, hence a factor 12^0 = 1; the corrected definitions in Pr6453_TailRatiosFixed carry the real exponent ((1:ℝ)/7) explicitly, and with it the ratios reproduce the certificate's printed and .
The word layer is started. Pr6453_Word (https://prove2.me/definitions bundle Pr6453_Word) fixes the word: 770 public inputs, 104 ports, 1095 column frames, 104 live columns, 29 owned fields and a program of 17 926 events (INIT 45, MOVE 3458, SCALE 854, ADD 13524, CLEAR 45), together with the notion of a native map — an elementary linear map acting on the rows of a helper of a given rank — and the counts it must satisfy: 2 941 distinct maps, 1 124 helper normalizers, 208 main adapters and 562 helpers over ranks 1 to 9. Pr6453.word_receipts (https://prove2.me/theorems/b22d132f-6412-478c-86eb-76201f168cc2) proves those counts. The individual maps are not in the certificate; they live in the native source.
The replay is reduced to its frame chart, and the word's replay holds locally. Pr6453.replay_frame_determined (https://prove2.me/theorems/6a9600c3-0c2d-4f2a-a180-224803774d3b) proves that a replay is legal exactly when its frame component replays legally, so the 17 926 row operations of the word never have to be unfolded. With the program embedded in Lean (17 926 events over 1095 columns, tag census checked by rfl) this gives, in the workspace and without axioms, ReplayPR6453 initialFrames — the word's events are all legal from the recorded initial chart, verified by kernel evaluation of the frame chart alone (2 min 32 s). That evaluation's proof term is too large to serialize, so it is not a platform node; the reusable half is the reduction, which is.
Per-stage locality is in place. Pr6453.replay_const (https://prove2.me/theorems/4864a242-e199-4639-a6d7-089739098dd5) proves that a program which never writes the frame of a column leaves that column's frame alone — frames are written only by move, initialisation and clear events, never by scaling or addition. With Pr6453.replay_frame_determined this is the per-stage tool the word's replay is organised around: a construction stage acts on a known column set and leaves the rest untouched, and stages combine by composition of their replays. The remaining step of the word layer is to read the stage decomposition off the data (the 3548 frame events, grouped by the columns they move) and check each stage's column set against its recorded frames.
The frame chart is now factored into per-column tracks. Pr6453.replay_track (https://prove2.me/theorems/cad58ac3-a5bf-47f3-9824-ec01223a73d0) proves that the frame a column ends at is exactly what that column's own track trackRun computes, so the frame chart of a word is the product of 1095 independent one-dimensional tracks. Together with Pr6453.replay_const (a stage touches only the columns it names) and Pr6453.replay_frame_determined (legality is decided by the frame chart) this completes the structural reduction of the replay: legality of the 17 926-event word reduces to 1095 short one-dimensional checks, and the per-stage statements are read off column sets rather than from a global evaluation. What is left for the word layer is the output half — that the rows end as the product rows — and the native maps, which the package counts but does not contain.
The rows half is in. Pr6453.replay_linear (https://prove2.me/theorems/a91c74bf-bd3b-4ade-b12b-dba5190a595a) proves that a word's output rows are a linear function of its input rows: runs from rows and from rows , over the same frame chart, add up to a run from ending at the sum of their rows. Every row operation is additive and the guards read only the chart, so the word realises a matrix acting on its input. With Pr6453.replay_track (each column's frames by its own track) the replay now has both halves in structural form: legality is per column, and the output is linear. What is still open is the identification of that matrix with multiplication of the two input words — the module semantics of the construction — and the native maps, which the package counts but does not contain.
The CRT-basis algebra is in. CRTBasis.crt_basis_mul (https://prove2.me/theorems/52157241-e3dd-442b-aed9-d1dd9581638c) proves that in the CRT basis — a product of copies of a field, the image of a ring modulo a product of coprime moduli — the matrix of multiplication by is , that the product of two such matrices is , and hence that the composite matrix is multiplication. Together with Pr6453.replay_linear (a word's rows are a linear function of its input rows) this gives both halves of what an encoding argument needs: the word realises a matrix, and in the CRT basis multiplication is that matrix. The encoding of the two multiplicands into the 770 input rows, and the identification of the word's own matrix with this one, are not formalised — the certificate does not contain the word's maps.
The encoding is stated and its algebraic core proved. Pr6453Encoding.crt_encoding (https://prove2.me/theorems/4697dd2e-cf62-4ac7-b80c-c77552c82cab) states the encoding explicitly: evaluate a polynomial at the points of a finite set , multiply the values pointwise, interpolate — and proves that what comes back is the product whenever the product's degree is below . The ingredients are that evaluation is multiplicative and additive, and that a polynomial of degree below vanishing on is zero. With CRTBasis.crt_basis_mul (multiplication is diagonal in the CRT basis) and Pr6453.replay_linear (a word's rows are linear in its input) the algebraic frame is complete: encode, multiply pointwise, decode. What remains outside Lean is the incidence — which of the 770 input columns carries which coefficient, and which target columns hold which CRT coordinates — because the certificate records the shape of the module (six fields, four Gaussian characters, 1152 coefficients) but not the word's maps.
The incidence is reduced to a finite check. Pr6453Incidence.spec_of_basis (https://prove2.me/theorems/8ed4df44-6789-4bf9-9853-b219de3610b0) states the incidence as data — a bilinear map enc filling the input rows from the two coefficient vectors, a linear read-out read of the CRT coordinates from the target rows, and the product form P — and proves that because everything is linear in each slot, verifying the word on the basis pairs gives the specification for all inputs. For a word with 1152 coefficients that is basis checks instead of a statement about all pairs.
This is as far as the shipped evidence reaches. The certificate records the module's shape (six fields, four Gaussian characters, 1152 coefficients) and the identity , but not which column carries which coefficient: the maps live in the recipe payload, whose hash it records and which the PR does not ship. Exhibiting enc for this word therefore needs the payload, and the finite check needs the word's own matrix — neither is derivable from the package.
Correction: the native maps are in the repository, and I reproduced them. My earlier note that the maps were 'not in the package' was wrong. research/p104-root-relay-descent-2/sources.py opens an eight-level authenticated archive chain whose bottom layer is research/p104-unread-path-resynthesis/local.py; its native(w) computes every native map as an exact 9-bit Clifford recipe from research/p104-native-channel/vendor/clifford_exact.py. Run on the PR #6453 word it reproduces the published receipt exactly — 2941 distinct maps, 1124 helper normalizers, 208 main adapters, helpers {1:14, 2:8, 3:4, 4:107, 5:15, 6:3, 7:9, 8:39, 9:363} — and the recipe_payload_sha256 4649372e… printed in RESULT.json. The 562 helper columns, their (initial, final) frames and their recipes are extracted to results/pr6453/word/helper-maps.json. The incidence is therefore determined by WORD.json (frames, ports, live set) together with those recipes.
import Definitions.Def_IntMul_MultitapeModel set_option autoImplicit false
namespace IntMul.Kappa
theorem pr6453_machine :
∃ (M : MultitapeTM) (g C : ℝ) (A n₀ : ℕ),
0.003287014 < g ∧ 0 < C ∧
(∀ n : ℕ, 1 ≤ n → ∃ T : ℝ, MultipliesAt M n T) ∧
(∀ n : ℕ, n₀ ≤ n →
MultipliesAt M n (C * n * (lg n : ℝ) ^ (1 - g) * (Real.log (lg n) + 1) ^ A)) := by
sorry
end IntMul.Kappa