Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Quantum Order Finding and Rational Reconstruction — Examples

1 · Prerequisites

2 · Summary

The reconstruction example uses $N = 2$ , $Q = 17$ , and $y = 9$ to show that the exact weak inequality accepts a boundary tie, while the finite-rational Legendre step separately uses a strict approximation hypothesis. The order-finding example takes $N = 5$ , $x = 2$ , and order $4$ : Fourier index $k = 2$ reconstructs the proper divisor $2$ but fails the exact power test, while a coprime index reconstructs and retains $4$ .

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: Literature-sourcedVerification: AI-adaptedOpen item page →

Denominator-bounded reconstruction at the strict boundary

Example

Take $N = 2$ , $Q = 17$ , and $y = 9$ . The reconstruction hypothesis holds because $17 > 4 (2)^{2} = 16$ . The normalized continued fraction is $\frac{9}{17} = [0; 1, 1, 8],$ with convergents $0 / 1, 1 / 1, 1 / 2, 9 / 17$ . For $p / q = 1 / 2$ , the exact comparison is $2 ∣ y q - p Q ∣ = 2 ∣ 18 - 17 ∣ = 2 = q,$ so the candidate is accepted at equality. The integer comparison has no tolerance parameter.

Facts & Assumptions

Given: The exact candidate test from Denominator-bounded rational phase reconstruction, the finite rational criterion, and the uniqueness result.

[F1]

A candidate has reduced denominator $1 \leq q \leq N$ and passes exactly when $2 ∣ y q - p Q ∣ \leq q$ (Denominator-bounded rational phase reconstruction).

[F2]

A rational has a terminating continued-fraction algorithm, and each finite convergent is the recurrence-defined fraction $p_{j} / q_{j}$ (The continued-fraction algorithm terminates exactly on rational numbers, Convergents of a regular continued fraction).

[F3]

For $Q > 4 N^{2}$ , at most one reduced fraction with denominator at most $N$ passes this test (Uniqueness of denominator-bounded phase candidates).

[F4]

The finite-rational Legendre criterion assumes the strict inequality $∣ A / D - p / q ∣ < 1 / (2 q^{2})$ (Finite-rational Legendre criterion before the terminal convergent).

Proof

1.1givenF1F2algebra

The Euclidean divisions $17 = 1 \cdot 9 + 8$ , $9 = 1 \cdot 8 + 1$ , and $8 = 8 \cdot 1$ give the displayed normalized expansion and its convergents by [F2]. The denominator- $2$ convergent $1 / 2$ satisfies the exact equality in [F1], so it passes.

2.1F1F2F3F4step 1.1algebra∎

The other denominator- $1$ convergents fail: for $0 / 1$ , $2 ∣ 9 ∣ = 18 > 1$ ; for $1 / 1$ , $2 ∣ 9 - 17 ∣ = 16 > 1$ . The terminal fraction has denominator $17 > N$ and is excluded. Thus $1 / 2$ is the only candidate; this also follows from [F3]. The algorithm's weak inequality accepts the tie, while [F4] uses a separate strict approximation hypothesis and is not invoked to turn equality into strictness.

ExampleConstruction: Literature-sourcedVerification: AI-adaptedjudge pass (gpt-6-luna)Open item page →

A non-coprime phase gives a proper order divisor

Example

Let $N = 5$ and $x = 2$ . The powers modulo $5$ are $2, 4, 3, 1$ , so the order is $r = 4$ . Here $n = 3$ , $m = 9$ , and $Q = 512$ . In the Fourier orbit, phase index $k = 2$ gives phase $2 / 4 = 1 / 2$ , nearest label $y = 256$ , and reduced phase fraction $1 / 2$ . Its candidate denominator is $q = 2$ , but $2^{2} \equiv 4 \equiv̸ 1 (m o d 5)$ , so the order test rejects it. Phase index $k = 1$ gives phase $1 / 4$ , label $y = 128$ , denominator $q = 4$ , and $2^{4} \equiv 1 (m o d 5)$ , so this candidate is retained. The phase index is sampled from the order-four Fourier mixture, and the minimum rule never calls the rejected proper divisor the order.

Facts & Assumptions

Given: The order-finding instructions, the exact order criterion, and the Fourier phase law.

[F1]

The algorithm retains a reconstructed denominator $q$ only after the exact test $x^{q} \equiv 1 (m o d N)$ , and returns the smallest retained denominator (Modular order finding with rational reconstruction).

[F2]

A superposition of eigenspaces produces the eigenspace-weighted phase-estimation mixture, and exact grid phases are returned with probability one (Phase estimation on a superposition of eigenspaces, Phase-estimation nearest-grid and tail bounds).

[F3]

A nearest phase label for a reduced phase of denominator $r \leq N$ reconstructs that reduced fraction (Correctness of phase-sample rational reconstruction).

[F4]

If $x$ has order $r$ , then $x^{q} = 1$ exactly when $r ∣ q$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[F5]

For true order $r$ , the repeated algorithm returns the minimum retained candidate; an exact denominator- $r$ sample therefore suffices (Success probability and repetition for modular order finding).

Proof

1.1givenF1algebra

Direct multiplication gives $2^{1} \equiv 2$ , $2^{2} \equiv 4$ , $2^{3} \equiv 3$ , and $2^{4} \equiv 1 (m o d 5)$ , with no earlier power equal to $1$ ; thus the order is exactly $4$ . The specified register size gives $n = ⌈ \log_{2} 5 ⌉ = 3$ , $m = 2 n + 3 = 9$ , and $Q = 2^{9} = 512$ .

2.1F1F3step 1.1algebra

For $k = 2$ , the phase reduces to $1 / 2$ , so the exact grid label is $y = 512 / 2 = 256$ . Applying [F3] with reduced numerator $1$ , denominator $2$ , and $N = 5$ gives reconstructed denominator $q = 2$ . The verification test is $2^{2} = 4 \equiv̸ 1 (m o d 5)$ , hence [F1] rejects this candidate.

2.2F1F2F3step 1.1algebra

The four vectors $∣ ψ_{k} ⟩ = \frac{1}{2} \sum_{s = 0}^{3} i^{- k s} ∣ 2^{s} m o d 5 ⟩$ are eigenvectors with phases $k / 4$ : multiplication by $2$ cycles $1, 2, 4, 3$ , and shifting the sum multiplies it by $i^{k}$ . The four-term geometric sum gives $∣ 1 ⟩ = \frac{1}{2} \sum_{k = 0}^{3} ∣ ψ_{k} ⟩$ , so [F2] assigns weight $1 / 4$ to each phase and returns its exact grid label. For $k = 1$ , $y = 512 / 4 = 128$ ; [F3] reconstructs denominator $4$ , and $2^{4} = 16 \equiv 1 (m o d 5)$ , so [F1] retains it. Thus both the rejected $k = 2$ outcome and a successful $k = 1$ outcome have positive probability.

3.1F1F4F5step 2.1step 2.2∎

By [F4], every retained denominator is a multiple of $4$ . The bad denominator $2$ is rejected by step 2.1, while the denominator- $4$ sample in step 2.2 is retained; [F5] then makes the minimum retained value $4$ . This example verifies that a reconstructed divisor is never silently reported as the exact order.

Quantum Order Finding and Rational Reconstruction — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Denominator-bounded reconstruction at the strict boundary

Example

Facts & Assumptions

Proof

A non-coprime phase gives a proper order divisor

Example

Facts & Assumptions

Proof

Sources