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.
Finite coefficient bounds for the scaled cyclotomic grid
Statement
Let be the automorphism of defined in The nontrivial real-conjugation automorphism of the eighth cyclotomic field, so , and let satisfy and . Then . If , then
Thus for each fixed only finitely many coefficient vectors can occur; the integer search may be restricted to .
Facts & Assumptions
Given: has the four embeddings for , complex conjugation pairs with and with , and is the least square-root-of-two exponent.
Dyadic cyclotomic ring for Clifford+T synthesis: has unique power-basis coefficients and .
The nontrivial real-conjugation automorphism of the eighth cyclotomic field: is the field automorphism , fixes , commutes with complex conjugation, and preserves .
Proof
The two inequalities , together with their complex conjugates, give for all four embeddings ; these are the identity, complex conjugation, , and their composite by [F2]. If , the definition of gives , so . Thus for every . By [F3], with . Since negates and commutes with conjugation, the product of all four embeddings is . It is a nonzero integer because and each embedding is injective. Its modulus is at most , a contradiction. This proves .
For , set . Then for every . Fourier inversion in the power basis gives : expanding the sum, the coefficient of is , which equals for and for distinct . Therefore . Since is an integer, it lies in the stated finite interval.
Remarks
This proves a finite search bound, not a running-time bound for deciding exact real inequalities at an arbitrary real input angle. The norm-equation step of Cyclotomic scaled grid and norm-equation solver is a separate procedure with its own locally proved correctness and complexity suppliers.
Depends on
- Dyadic cyclotomic ring for Clifford+T synthesis
- The nontrivial real-conjugation automorphism of the eighth cyclotomic field
- Smallest square root of two denominator exponent
- Denominator exponent is a well-defined integer
- Canonical dyadic coefficient encoding
- Conjugate norms from the dyadic eighth-cyclotomic ring are real dyadics
Used by
- Cyclotomic scaled grid and norm-equation solver Algorithm
- Clifford+T denominator descent and finite base table Lemma
- Exponent growth of the Rz scaled grid Lemma
- Size and residue of the Rz candidate norm integer Lemma
- Complete scaled-grid enumeration with expected polynomial prefix cost Theorem
- H-count and T-count optimality of exact Clifford+T synthesis Theorem
- The Rz approximation procedure is correct when it returns Theorem
Dependency tree · two levels
10 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Ross and Selinger, Optimal ancilla-free Clifford+T approximation of z-rotations (standard reference, not scraped)