LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-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.

A cyclic group of order n has exactly n additive characters

Statement

Write $C_{n} = ⟨ g ⟩$ additively, so $j g$ denotes the sum of $j$ copies of $g$ and $n g = 0$ . If $C_{n}$ has order $n \geq 1$ , then its set $\hat{C_{n}}$ of additive characters has cardinality $n$ . Each character is uniquely determined by $χ (g)$ , and the possible values are exactly the $n$ distinct complex $n$ th roots of unity. For each such root $z$ , the corresponding character is $χ_{z} (j g) = z^{j}$ for every $j \in Z$ .

Facts & Assumptions

Given: A cyclic group $C_{n} = ⟨ g ⟩$ of finite order $n \geq 1$ .

[F1]

An additive character is a group homomorphism and sends $0$ to $1$ (Additive characters of a finite abelian group); a group homomorphism preserves integer powers, so $χ (j g) = χ (g)^{j}$ (A group homomorphism automatically satisfies $f (e) = e^{'}$ and $f (g^{- 1}) = f (g)^{- 1}$ , and $f (g^{n}) = f (g)^{n}$ for every $n \in Z$ ; for monoid homomorphisms preservation of the identity must be assumed).

[F2]

The finite-order case of the cyclic classification identifies $Z / n Z$ with $C_{n}$ by the map $[j] \mapsto j g$ ; hence every element is $j g$ , and $j g = k g$ exactly when $n$ divides $j - k$ (Every cyclic group is isomorphic to $(Z, +)$ or to $(Z / n, +)$ for its finite order $n \geq 1$ ).

[F3]

For $n \geq 1$ , the complex $n$ th roots of unity are exactly $n$ distinct values (The $n$ -th roots of a complex number and the $n$ distinct roots of unity for every $n \geq 1$ ).

[F4]

The notation $\hat{C_{n}}$ is the set of additive characters of $C_{n}$ (Dual group of a finite abelian group).

[F5]

Integer powers in a group satisfy $z^{j + k} = z^{j} z^{k}$ and $(z^{j})^{k} = z^{j k}$ (Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute).

Proof

1.1F1F2F3F4

If $χ \in \hat{C_{n}}$ as defined in [F4], then $χ (g)^{n} = χ (n g) = χ (0) = 1$ by [F1] and the given relation $n g = 0$ , so evaluation at $g$ maps this character set into the set in [F3]. Every element is $j g$ by [F2], and [F1] gives $χ (j g) = χ (g)^{j}$ ; thus evaluation at $g$ is injective.

1.2F1F2F3F4F5construct

Conversely, for each $n$ th root of unity $z$ , define $χ_{z} (j g) : = z^{j}$ for $j \in Z$ . If $j g = k g$ , [F2] gives $j - k = q n$ for some integer $q$ , so $z^{j} = z^{k} (z^{n})^{q} = z^{k}$ by [F3, F5]; hence the value is well defined. Also $χ_{z} (j g + k g) = z^{j + k} = χ_{z} (j g) χ_{z} (k g)$ by [F5], so $χ_{z}$ is an additive character in [F4], and $χ_{z} (g) = z$ .

2.1step 1.1step 1.2F3F4∎

Steps 1.1 and 1.2 make evaluation at $g$ a bijection from the character set [F4] to the $n$ distinct roots in [F3]. This also covers $n = 1$ : the quotient is trivial and the sole root is $1$ . Therefore $∣ \hat{C_{n}} ∣ = n$ .

Depends on

Used by

Dependency tree · two levels

41 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

Ronald de Wolf, Quantum Computing: Lecture Notes, version 6 (standard reference, not scraped)
Andrew M. Childs, Lecture Notes on Quantum Algorithms (standard reference, not scraped)
John Preskill, Quantum Information, Chapter 6: Quantum Algorithms (standard reference, not scraped)