LemmaStatement: Literature-sourcedProof: 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.

QC24 Signed Ray Packing Code

Statement

Let $D \geq 2$ be an even integer and let $δ \in R$ satisfy $0 < δ < 1 / 4$ . There is a family of at least $\exp (c_{δ} D)$ unit sign vectors in $C^{D}$ , with their first $D / 2$ coordinates fixed at $1 / \sqrt{D}$ , such that the projective chord distance between distinct resulting rays is at least $2 \sqrt{δ}$ . Here $c_{δ} = (\ln 2 / 2) (1 - H_{2} (2 δ)) > 0$ and $H_{2} (t) = - t \log_{2} t - (1 - t) \log_{2} (1 - t)$ .

Facts & Assumptions

Given: Even $D \geq 2$ , $0 < δ < 1 / 4$ , and the distance formula below.

[F1]

For unit representatives, $d_{c h} ([u], [v]) = \sqrt{2 - 2 ∣ ⟨ u, v ⟩_{r o o t} ∣}$ (Projective Chord Distance Formula).

[F2]

For $y > 0$ , $(\ln y)^{'} = 1 / y$ and $\ln y = \int_{1}^{y} d t / t$ (The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t).

[F3]

A real function continuous on a closed interval and differentiable on its interior satisfies the mean value theorem (The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ ).

[F4]

The natural logarithm is strictly increasing, has $\ln 1 = 0$ , and satisfies $\ln (1 / y) = - \ln y$ and $\ln (a / b) = \ln a - \ln b$ for positive arguments (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm); hence $\ln 2 > 0$ and $\log_{2} t = \ln t / \ln 2$ for $t > 0$ .

[F5]

Product and chain rules hold for differentiable real functions, and differentiability implies continuity (Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ , The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ , A function differentiable at $c$ is continuous at $c$ ). The identity has derivative $1$ and constants have derivative $0$ , as their difference quotients are constant (The derivative $f^{'} (c) = \lim_{x \to c} \frac{f (x) - f (c)}{x - c}$ of $f : A \to R$ at a point $c \in A$ that is a limit point of $A$ , and differentiability on a set, The $ε$ - $δ$ limit $\lim_{x \to c} f (x) = L$ of $f : A \to R$ at a limit point $c$ of $A$ ).

[F6]

The real binomial expansion uses the coefficients $ι (\binom{m}{j})$ , where $ι$ embeds naturals into $R$ (The binomial theorem in $R$ : $(x + y)^{n} = \sum_{k < n + 1} ι ⁣ (\binom{n}{k}) x^{k} y^{n - k}$ ).

Proof

Given: As in Facts & Assumptions.

1.1givenconstructalgebra

Put $m = D / 2$ , $x = 2 δ \in (0, 1 / 2)$ and $R = ⌈ x m ⌉ - 1$ . Greedily scan the finite set ${0, 1}^{m}$ in lexicographic order: select the least remaining word and delete all words at Hamming distance at most $R$ , repeating until none remain. Distinct selected words have distance $h \geq R + 1 \geq x m = δ D$ , and each selection deletes at most $B = \sum_{j = 0}^{R} (\binom{m}{j})$ words, so the selected code has at least $2^{m} / B$ words.

2.1F2F3F4F5F6step 1.1algebra

For $j \leq R < x m$ , the ratio $x / (1 - x) < 1$ gives $x^{j} (1 - x)^{m - j} \geq x^{x m} (1 - x)^{(1 - x) m}$ . The binomial identity [F6], $1 = \sum_{j = 0}^{m} ι (\binom{m}{j}) x^{j} (1 - x)^{m - j}$ therefore yields $ι B \leq [x^{- x} (1 - x)^{- (1 - x)}]^{m} = 2^{m H_{2} (x)}$ . Put $h (t) = - [t \ln t + (1 - t) \ln (1 - t)] / \ln 2$ for $0 < t < 1$ , which is $H_{2} (t)$ by [F4]. The product and chain rules [F5] give $h^{'} (t) = (\ln (1 - t) - \ln t) / \ln 2 = \ln ((1 - t) / t) / \ln 2$ . For $0 < t < 1 / 2$ , the ratio exceeds $1$ , so [F4] gives $h^{'} (t) > 0$ . The same rules show $h$ is differentiable on $(0, 1)$ , and [F5] makes it continuous there; in particular it is continuous on $[x, 1 / 2]$ . By [F4], $\log_{2} (1 / 2) = - 1$ , so $h (1 / 2) = 1$ . The mean value theorem [F3] now gives $1 - h (x) = h^{'} (ξ) (1 / 2 - x) > 0$ for some $ξ \in (x, 1 / 2)$ . Thus $H_{2} (x) < 1$ and the code size is at least $2^{m (1 - H_{2} (x))} = \exp (c_{δ} D)$ .

3.1F1step 1.1step 2.1algebra∎

Map each selected bit word $b$ to the sign word $s_{i} = (- 1)^{b_{i}}$ ; this is a bijection preserving Hamming distance. Form $u_{s} = D^{- 1 / 2} (1, \dots, 1, s_{1}, \dots, s_{m})$ . It is unit because it has $D$ entries of modulus $D^{- 1 / 2}$ . If two selected words differ in $h$ places, then $⟨ u_{s}, u_{t} ⟩_{r o o t} = 1 - 2 h / D$ . Since $h \leq m = D / 2$ and $h \geq δ D$ , this lies in $[0, 1 - 2 δ]$ , so [F1] gives $d_{c h} ([u_{s}], [u_{t}]) = 2 \sqrt{h / D} \geq 2 \sqrt{δ}$ . The first half of each vector is fixed and nonzero, so scalar-proportional unit vectors must have scalar $1$ and identical last-half signs; distinct code words therefore give distinct rays.

Depends on

Used by

QC24 Discrete Alphabet Approximate Preparation Lower Bound Theorem

Dependency tree · two levels

55 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

John Preskill, Quantum Computation, Chapter 5, Classical and Quantum Circuits (standard reference, not scraped)
John Watrous, The Theory of Quantum Information (standard reference, not scraped)