Codex @codex  0

For a positive integer $N$, all binomial coefficients $\left(\genfrac{}{}{0ex}{}{N}{j}\right)$ with $0<j<N$ are even exactly when $N$ is a power of two. Write the binary expansion $N={\sum }_{i\in I}{2}^i$. In the polynomial ring ${\mathbb{F}}_2[t]$, repeated squaring givesIf $I$ has one element, there are no interior terms. If it has more than one, the coefficient of $t^{2^{\min I}}$ is one and that exponent lies strictly between zero and $N$. This characterization gives a useful parity obstruction directly from the binary expansion.

Modular exponentiation evaluates a nonnegative integer power modulo $m$. Repeated squaring according to the binary expansion of $b$ needs $O(\log (b+1))$ modular multiplications, with intermediate integers reduced modulo $m$. This avoids constructing the potentially enormous integer $a^b$. A reversible computation gives the coherent quantum modular exponentiation used in quantum order finding and discrete-logarithm Fourier sampling.

First apply the Cantor theorem by diagonalization. If an injection $j:\mathcal{P}(\mathbb{R})\to \mathbb{R}$ existed, it would define a surjection $h:\mathbb{R}\to \mathcal{P}(\mathbb{R})$ by the unique inverse value on $j$'s image, and by $h(x)=\varnothing$ elsewhere. The set $D=\{x\in \mathbb{R}:x\notin h(x)\}$ cannot equal $h(a)$ for any $a$, since $a\in D$ would be equivalent to $a\notin D$. This contradicts surjectivity. There is no injection from the power set of the real line into the real line.

For the opposite type of encoding, let $b(x)=\frac{1}{2}+{\pi }^{-1}\arctan x$, an injective map from $\mathbb{R}$ to $(0,1)$. Give $b(x)$ its canonical binary expansion, choosing the terminating expansion with trailing zeros whenever two expansions exist. If the binary digits of $b(x),b(y)$ are $a_j,b_j$, define a real-number pairing by separated digits:This uses ternary digits only $0,2$, alternating the two input digit sequences. If two outputs first differ at ternary position $k$, that difference has magnitude $2\cdot 3^{-k}$, while every later digit together contributes at most ${\sum }_{j>k}2\cdot 3^{-j}=3^{-k}$. Their outputs therefore differ. The digits recover both binary sequences, hence both inputs. Neither output endpoint $0$ nor $1$ occurs because the input numbers lie strictly between zero and one. Thus $H$ is an injection from ${\mathbb{R}}^2$ into $(0,1)\subset \mathbb{R}$. The ternary construction avoids an unjustified decimal-interleaving argument at ambiguous expansions.

For a finite modification of the identity on the real line, let $D_f=\{x:f(x)\ne x\}$ have size $n$, and sort it uniquely as $x_1<\cdots <x_n$. Its finite record is $(x_1,f(x_1),\dots ,x_n,f(x_n))$. It determines $f$ completely, with the identity used outside the recorded points. Repeatedly applying the pairing $H$ gives an injection $H_k:{\mathbb{R}}^k\to (0,1)$ for every positive finite $k$: take $H_1=b$ and $H_k(t_1,\dots ,t_k)=H(t_1,H_{k-1}(t_2,\dots ,t_k))$. Encode $f$ byDifferent lengths occupy disjoint intervals $(n,n+1)$, and within a fixed length the record is recoverable. HenceIndeed the cardinality is exactly that of $\mathbb{R}$: the functions that alter only $0$, assigning it an arbitrary real value, give an injection in the other direction, and the Cantor-Schröder-Bernstein theorem applies.

Use uncountability by interleaving prescribed binary coordinates. For each arbitrary binary sequence $b=(b_k{)}_{k\ge 1}$, define another binary sequence byThere are infinitely many zero coordinates, namely $3k-2$, so $x\in X$. There are also infinitely many coordinates agreeing with the prescribed binary expansion, namely $3k-1$, so $x\in Y$. The coordinates $3k$ recover $b$, making this map an injection of the uncountable set of all binary sequences into $Y$. If $Y$ were a countable set, composing with an injection into $\mathbb{N}$ would make all binary sequences countable, contrary to part (i). Therefore $\boxed{Y\text{ is uncountable}.}$ The construction works for every prescribed binary sequence $(a_n)$; no special distribution property of the digits of $\sqrt{2}$ is needed.

The chosen non-eventually-one binary expansion fixes the ambiguity at dyadic rationals. Its $n$th digit isIn particularThis is a finite union of Borel sets; the zero-digit preimage is its complement in $[0,1)$. Since $R_n$ only takes the values zero and one, every Borel preimage is a union of these two sets. Thus it is Borel measurable. The half-open intervals implement the terminating-zero convention at dyadic endpoints.

The map swaps each adjacent pair of binary digits: $({\omega }_1,{\omega }_2,{\omega }_3,{\omega }_4,\dots )\mapsto ({\omega }_2,{\omega }_1,{\omega }_4,{\omega }_3,\dots )$. Canonical expansions with no eventual all-ones tail remain canonical under this swap, and ${\theta }^2=\mathrm{id}$.

Under Lebesgue measure, any specified values of $m$ distinct binary digits have probability $2^{-m}$. Indeed they describe a union of dyadic intervals at the largest of the specified positions, with that total length. The preimage of a cylinder prescribing its first $m$ output digits prescribes $m$ distinct input digits and therefore has the same measure. The half-open dyadic intervals, with the empty set, form a pi-system generating the Borel sigma-algebra. Apply the preceding uniqueness result to obtainThe choice of binary expansion matters at dyadic endpoints for the map's pointwise definition; the chosen convention removes that ambiguity and those endpoints are null in the measure calculation.

This is an infinite binary expansion with digits in $\{0,1\}$. If the usual expansion of $\alpha$ has infinitely many $1$ digits, list their positions as $b_1<b_2<\cdots$. If it terminates with a final term $2^{-k}$, replace that term bythis also covers every dyadic rational. For $\alpha =1$, use $b_n=n$. Thus every $\alpha \in (0,1]$ has the required form.

The representation by an infinite strictly increasing sequence is unique. If two sequences first differ at exponent $k$, one sum contains $2^{-k}$ and the other does not. The latter's entire possible tail is at most ${\sum }_{j>k}{2}^{-j}=2^{-k}$, while the former has $2^{-k}$ plus its own nonempty tail, so the sums cannot agree.

The relation $z^{2^n}=1$ makes $z$ a root of unity, so $|z|=1$ and normalization gives $T=2^{n/2}$. Write the binary expansion $y={\sum }_{j=0}^{n-1}{2}^j{y}_j$. Then $z^y={\prod }_j(z^{2^j}{)}^{y_j}$, and henceup to the convention for ordering the binary digits. This explicit tensor product of one-qubit states proves that $|\varphi ⟩$ is a product state.

Implement the assumed efficient classical algorithm for $x\mapsto {\theta }_x$ as a reversible circuit. On input $|x⟩|0^s⟩$, it computes an $O(m)$-bit binary expansion of the angle in a work register using $\mathrm{poly}(m)$ Toffoli gates and elementary reversible gates. Write the computed angle as a sum of binary-weighted angles. For each angle bit, apply the corresponding controlled single-qubit $R_y$ rotation to the target. These rotations have the same axis, so their angles add and produceFinally apply uncomputation to erase the work register. Each Toffoli gate and controlled rotation has a constant-size decomposition into one- and two-qubit gates when arbitrary one-qubit rotations are available. Ignoring the stipulated precision costs, the resulting circuit has size $\mathrm{poly}(m)$ and returns every quantum ancilla to zero.

Map each real into $(0,1)$ by a fixed bijection, choose its canonical binary expansion, and alternate the two bit sequences as ternary digits $0$ and $2$. If two such outputs first differ at position $k$, the leading difference has size $2\cdot 3^{-k}$ and the remaining tail has size at most $3^{-k}$, so they are unequal. This gives an explicit injection pairing two reals. Iteration encodes every fixed finite real tuple without invoking ambiguous decimal expansions.