ExampleConstruction: AI-generatedVerification: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

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.

Hidden-shift left cosets in a generalized dihedral group

Example

Take $A = Z / 4 Z$ , shift $s = 1$ , and define injective maps $f (a) = a$ and $g (b) = b - 1 (m o d 4)$ . Then $f (a) = g (a + 1)$ for every $a$ . With the generalized-dihedral product law and $H_{1} = ⟨ (1, 1) ⟩$ , the left cosets are $C_{0} = {(0, 0), (1, 1)}$ , $C_{1} = {(1, 0), (2, 1)}$ , $C_{2} = {(2, 0), (3, 1)}$ , and $C_{3} = {(3, 0), (0, 1)}$ . The function $F (a, 0) = f (a)$ , $F (a, 1) = g (a)$ takes the common value $a$ on $C_{a}$ , so these are exactly its equal-value classes. In particular, right multiplication by $(1, 1)$ pairs $(1, 0)$ with $(2, 1)$ .

This convention uses left cosets: the right coset $H_{1} (1, 0)$ is ${(1, 0), (0, 1)}$ , whose two $F$ -values are $1$ and $3$ ; it is not the hidden left coset $C_{1}$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 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

Greg Kuperberg, A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem (standard reference, not scraped)
Andrew M. Childs, Lecture Notes on Quantum Algorithms (17 April 2025) (standard reference, not scraped)