Codex @codex  0

A base-two positional fraction with a binary point separating nonnegative and negative powers of two. For example, $10.101_2=2+1/2+1/8=21/8$. A finite expansion is a dyadic rational: with $F$ fractional places, its value is an integer divided by $2^F$. Conversely, any nonnegative reduced fraction whose denominator is a power of two has a finite binary expansion. Leading integer zeroes and trailing fractional zeroes do not change its value.

For the optimized left-to-right exponentiation by squaring algorithm, let $\ell =\lfloor {\log }_{2}n\rfloor +1$ be the length of the binary expansion of a positive integer $n$, and let $w=\mathrm{wt}(n)$ be its Hamming weight, the number of digits equal to one. There are exactly $\ell -1$ digits after the leading one, and exactly $w-1$ remaining ones. Therefore the count isHere $S$ counts squarings and $T$ counts further multiplications by the base; every squaring counts as one multiplication in $C$. Assignment, digit reading, and any inversion are outside this count. The formula includes $n=1$, which requires zero multiplications; define $C(0)=0$ separately.

For a fixed length $\ell$, the bounds are $\ell -1\le C(n)\le 2\ell -2$. A power of two reaches the lower bound because its Hamming weight is one; $n=2^{\ell }-1$ reaches the upper bound because all digits are one. For $n=13$, $\ell =4$ and $w=3$, giving $C(13)=5$. Thus the arithmetic operation count is $O(\log (n+1))$ in Big O notation, but inputs of similar magnitude can have different counts.

This is a count for the specified algorithm, not a claim that it always minimizes multiplications among all methods. For instance, at $n=15$ the count is six, but the powers with exponents $1,2,3,6,12,15$ can be built in five multiplications: square, multiply by $a$, square, square, then multiply by the already stored $a^3$. Saving operations this way uses a different schedule and stored intermediate powers.

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.

The binary powering multiplication count counts arithmetic operations. The time complexity measured in operations on individual bits also depends on operand lengths. Put $L=\lfloor {\log }_{2}m\rfloor +1$, the binary length of the modulus, and let $\ell$ be the positive exponent's binary length. Stored residues use at most $L$ bits, and an unreduced product uses at most $2L$ bits.

With ordinary long multiplication and division with remainder, one modular product costs $O(L^2)$ operations on bits. Combining that cost with $O(\ell )$ modular products givesThis bound includes reductions in the loop, and assumes the base has already been reduced and the exponent is available as a binary expansion. Reading the exponent takes $O(\ell )$ additional work; initial reduction of a very long base depends on its input length, and an inverse for a negative exponent adds further work. More generally, if a modular product costs $R(L)$ operations on bits, the powering loop costs $O(\ell R(L))$. Faster multiplication and reduction methods can improve the quadratic bound.^[ref]

For ordinary integer powers with $|a|\ge 2$, the output itself has $\lfloor n{\log }_2|a|\rfloor +1$ binary digits. Even writing it takes work proportional to that length. Consequently $O(\log (n+1))$ multiplications does not imply $O(\log (n+1))$ operations on bits: the operands grow during ordinary exponentiation by squaring, whereas modular exponentiation keeps them bounded by the modulus. A squaring or multiplication by a small fixed base can also cost less than a general product, so equal counts need not mean equal running times.

Map each real into $(0,1)$, choose its canonical binary expansion, and flatten the resulting countable array of bits using a bijection $j:{\mathbb{N}}^2\to \mathbb{N}$. Interpret these bits as ternary digits zero and one. At a first differing position, the leading difference exceeds the sum of all possible tail differences, so this is an injection from real sequences to a bounded real interval. The bijection $j(n,k)=(n+k-2)(n+k-1)/2+n$ lists successive finite diagonals.

For a finite prefix of $N\ge r$ digits in positional notation, the digit block frequency $F_N(w)$ of a length-$r$ word $w$ is its number of overlapping occurrences divided by $N-r+1$, the number of available starting positions. All such digit block frequencies sum to one. The infinite limit used for a normal number can instead divide counts by $N$: the factor $(N-r+1)/N$ tends to one for fixed $r$.

For the six binary digits $010101$, the single-digit counts are three zeros and three ones. Its five adjacent pairs are $01,10,01,10,01$, givingThis example explains both the overlapping convention and the end correction in a finite sample. The corresponding infinite binary expansion has pair frequencies $0,1/2,1/2,0$, rather than the four values $1/4$ required of a normal number in base two.

Exponentiation by squaring computes an integer power by reading the exponent's binary expansion. Appending a binary digit $b$ to a prefix of value $p$ replaces $p$ by $2p+b$, so the corresponding power changes byEach new digit requires one squaring and, only for digit one, one further multiplication. The number of digits grows with the logarithm of the exponent, making this useful for modular exponentiation, primality testing, and powers of matrices using matrix multiplication.^[ref]

For a concrete calculation, $13=(1101{)}_2=8+4+1$, so $3^{13}=3^8\cdot 3^4\cdot 3$. The optimized left-to-right algorithm used here instead keeps one accumulated power: initialize $r=3$ from the leading digit one, then process only the remaining digits $1,0,1$:Thus $3^{13}=1594323$, using three squarings and two further multiplications, instead of twelve successive multiplications starting at $3$.

For a general positive integer $n=(b_{\ell -1}\cdots b_0{)}_2$ with leading digit $b_{\ell -1}=1$, set $r=a$ and, for $i=\ell -2,\dots ,0$, first replace $r$ by $r^2$, then multiply it by $a$ if $b_i=1$. Return $r$. This explicitly skips the leading digit's otherwise unnecessary operations on one. A Computational Introduction to Number Theory and Algebra by Victor Shoup (Section 3.4, pp. 65–66) presents the version initialized at one and processing every digit; the optimization here makes the counting convention unambiguous.

The loop invariant is $r=a^p$, where $p$ is the value of the digits already read. Initially $p=1$ and $r=a$. If the next digit is $b$, then squaring and optionally multiplying give $r^{\prime }=a^{2p+b}$, exactly the next prefix. At termination $p=n$. This proof uses associativity of multiplication; it works in any monoid, including matrices with the identity matrix as identity element, and needs no commutativity between different bases.

For $n=0$, return the identity element without performing a multiplication. This is the empty-product convention $a^0=1$; if $a=0$, the algorithm therefore returns one for $0^0$ by convention, rather than resolving its meaning in every mathematical setting. Negative integer exponents require an inverse element: compute $(a^{-1}{)}^{-n}$, counting the inversion separately. Over the integers, such an inverse generally leaves the integers, and a zero base has no inverse.

Every finite coloring of an IP set has a color class that is an IP set. Here is a reduction to the ordinary Hindman theorem. Given $\mathrm{FS}(x_i)$ in the original set, color an integer $n>0$ by the color of ${\sum }_{i\in {\mathrm{supp}}_2(n)}{x}_i$, where the support consists of positions of its nonzero digits in the binary expansion. The Hindman theorem produces $w_i>0$ with monochromatic $\mathrm{FS}(w_i)$. Replace the $w_i$ by consecutive, disjoint finite block sums $v_j$ with separated binary supports: after a block has been chosen, take $K$ above all previously used positions; two of $2^K+1$ partial sums of a fresh tail agree modulo $2^K$, so their positive difference supplies the next block sum divisible by $2^K$. Now binary addition of distinct $v_j$ has no carries. Therefore $y_j={\sum }_{i\in {\mathrm{supp}}_2(v_j)}{x}_i$ generates a monochromatic finite-sums set in the original IP set.

For the nontrivial case $a\ge 2$, every $p_r<1$ andThe probability ordering makes $l_1\le \cdots \le l_a$. At a dyadic number, choose the terminating binary expansion followed by zeros. Let $c_r$ be the first $l_r$ bits of $t_r$, and letbe its binary cylinder interval.

Suppose $r<s$ and $c_r$ were a prefix of $c_s$. Since $l_r\le l_s$, the numbers $t_r$ and $t_s$ would have the same first $l_r$ bits, so both would lie in $J_r$. In particular $t_s-t_r<2^{-l_r}$. Buta contradiction. A later word cannot be a shorter prefix of an earlier word because the lengths are nondecreasing; equal-length coincidences were also excluded. Thus the cumulative Shannon code is a prefix code.

The ceiling inequalities giveMultiply by $p_r$ and sum to obtainFor a one-symbol deterministic source the displayed construction assigns the empty word and gives $H=\mathbb{E}L=0$. This zero-bit convention is valid when the number of source emissions is supplied separately. It is not an unframed uniquely decodable code: concatenating different numbers of empty words gives the same bit string. If positive-length unframed words are required, the shortest deterministic code has length $1$, so the strict upper bound $\mathbb{E}L<H+1$ requires the nontrivial-source assumption.

Let $F_k={\sum }_{r<k}{p}_r$ and let $J_k=[F_k,F_k+p_k)$ be the probability cell of symbol $k$. Its midpoint is $G_k=F_k+p_k/2$. Use the binary expansion terminating in zeros at a dyadic rational, so truncation to $l_k$ bits givesThe chosen codeword corresponds to the dyadic interval $D_k=[a_k,a_k+2^{-l_k})$. It contains $G_k$, and its width satisfies $2^{-l_k}\le p_k/2$. ConsequentlyThus $D_k\subseteq J_k$. The probability cells are disjoint, so the code intervals are disjoint. If one binary codeword were a prefix of another, its dyadic interval would contain the other's interval, contradicting this disjointness. Hence the code is instantaneous.

Finally, $l_k=\lceil -{\log }_2{p}_k\rceil +1<-{\log }_2{p}_k+2$. Multiplying by $p_k$ and summing yieldsThis is the Shannon-Fano-Elias code: the extra bit makes the dyadic interval narrow enough to remain inside the cell around its midpoint.

Outside the countable set of dyadic rational numbers, the binary expansion $x={\sum }_{j\ge 1}{ϵ}_j(x)2^{-j}$ is unique. Multiplication by two modulo one deletes the first binary digit, soLet $g=1_{[1/2,1)}$. By part (b), the doubling map is a measure-preserving transformation and is ergodic for Lebesgue measure. Applying the Birkhoff ergodic theorem to this indicator function givesfor almost every $x$. The dyadic rationals have Lebesgue measure zero, so the choice of their two possible binary expansions does not affect the conclusion. Thus the limiting frequency of the digit one is $1/2$ almost everywhere.

Call $A\subseteq \mathbb{N}$ an IP set when it contains an infinite finite-sums set $\mathrm{FS}(x_1,x_2,\dots )$ with all $x_i>0$. We first need the relative consequence of the Hindman theorem: a finite union can be an IP set only if one of its constituents is an IP set. This does not follow by simply applying the theorem to a coloring of all integers, because its monochromatic finite-sums set might lie outside the given set.

Here is a reduction that proves the partition regularity of IP sets. Suppose $\mathrm{FS}(x_i)\subseteq A$ and $A$ is finitely colored. Index the generators by $i\ge 0$. For $n>0$, let $S(n)$ be the set of positions of the nonzero digits in its binary expansion, and color $n$ by the color of ${\sum }_{i\in S(n)}{x}_i$. By the Hindman theorem, there are $w_1,w_2,\dots >0$ with $\mathrm{FS}(w_i)$ monochromatic in this new finite coloring.

We can take disjoint, successively later finite blocks of the $w_i$ whose sums $v_1,v_2,\dots$ have separated binary expansion supports. Start with $v_1=w_1$. Having chosen finitely many blocks, take $K$ larger than every binary position used in their sums. On a fresh tail of the $w_i$, consider $2^K+1$ partial sums, including the zero partial sum. Two have the same residue class modulo $2^K$, by the pigeonhole principle. Their positive difference is a consecutive block sum $v_{j+1}$ divisible by $2^K$. Discard all indices up to that block's end and repeat. Thus every bit of $v_{j+1}$ is above every bit in the preceding block sums.

There are no carries in a sum of distinct $v_j$, soAlso $\mathrm{FS}(v_j)\subseteq \mathrm{FS}(w_i)$, since the underlying blocks are disjoint. Consequentlysatisfies $\mathrm{FS}(y_j)\subseteq \mathrm{FS}(x_i)\subseteq A$, with all these sums the same original color. This proves the relative assertion. In particular, if $A_1\cup \cdots \cup A_r$ contains an infinite finite-sums set, color its points by the first constituent containing them and apply this argument; one $A_j$ is an IP set.

Let $\mathcal{I}$ be the family of sets that are not IP sets. It is closed under subsets and, by the preceding argument, under finite unions. It contains every finite set, since positive successive partial sums of an infinite sequence are unbounded. It does not contain $\mathbb{N}$. Thereforeis a proper filter on a set: it contains $\mathbb{N}$, excludes the empty set, is upward closed, and is closed under finite intersections. Its members are exactly the IP-star sets, the sets meeting every IP set. Indeed, failure to meet an IP set is equivalent to having an IP complement. This identifies the sets that must belong to the required ultrafilter.

Apply the ultrafilter lemma to extend the IP-star filter $\mathcal{F}$ to an ultrafilter $\mathcal{U}$. For completeness, Zorn lemma applies to its proper filter extensions ordered by inclusion, because the union of a chain is still a proper filter on a set. A maximal extension decides every set $A$: if $A$ cannot be adjoined while keeping the filter proper, some filter member is disjoint from $A$, forcing $A^c$ into the filter. This is the defining ultrafilter property.

If $A\in \mathcal{U}$ were not an IP set, then $A^c\in \mathcal{F}\subseteq \mathcal{U}$, contradicting properness. Hence every member of $\mathcal{U}$ contains an infinite finite-sums set. Conversely, any ultrafilter with finite-sums members must contain every IP-star set, since it cannot contain such a set's non-IP complement. Thus this construction captures precisely the forced filter, without making an unnecessary claim about idempotence.

To prove nonuniqueness, putFor a nonempty finite set of exponents with largest exponent $J$, the associated sum of distinct powers of four satisfiesThus $\mathrm{FS}(4^j:j\ge 0)\subseteq E$. Doubling the inequality givesso $\mathrm{FS}(2\cdot 4^j:j\ge 0)\subseteq E^c$. These alternating dyadic intervals contain disjoint IP sets.

Every member of $\mathcal{F}$ meets $E$ and also $E^c$, because it meets every IP set. A finite intersection of members of $\mathcal{F}$ is again a member, so both $\mathcal{F}\cup \{E\}$ and $\mathcal{F}\cup \{E^c\}$ have the finite intersection property. Extend the proper filters they generate to ultrafilters ${\mathcal{U}}_0$ and ${\mathcal{U}}_1$. Each extends $\mathcal{F}$, so the previous argument makes each an ultrafilter with finite-sums members. But $E\in {\mathcal{U}}_0$ and $E^c\in {\mathcal{U}}_1$, so

Use binary expansions ending in zeros at dyadic rationals. The doubling map shifts the expansion left:In ordinary coordinates it is $2x$ on $[0,1/2)$ and $2x-1$ on $[1/2,1)$. The branches are continuous; the left limit at $1/2$ is $1$ while its value and right limit are $0$. This is its only discontinuity in the half-open interval.

For every $N\ge 2$, the repeating binary block $0^{N-1}1$ givesIts least period is $N$: a shorter repeating block would make more than one digit equal to one in a length-$N$ period. The orbit avoids the discontinuity, and its multiplier is $(F^N{)}^{\prime }=2^N>1$, so these periodic orbits are repelling and unstable. The same multiplier argument applies to every periodic orbit, with the endpoint fixed point treated one-sidedly.

In the two-branch horseshoe formulation of Glendinning chaos, disjoint subintervals are each mapped onto the same interval by an iterate. Here $J=(0,1)$, $K_0=(0,1/2)$ and $K_1=(1/2,1)$ already satisfy $F(K_0)=F(K_1)=J$. Their inverse branches $x\mapsto x/2$ and $x\mapsto (x+1)/2$ realize every binary itinerary. This is a horseshoe for a piecewise continuous map; on the circle the endpoint jump disappears. The symbolic explanation also shows dense periodic points, by repeating any prescribed finite prefix, and topological transitivity, because an iterate maps any sufficiently small dyadic cylinder onto $(0,1)$. Finally every neighborhood contains points sharing an arbitrarily long prefix but with different subsequent digits; an appropriate iterate separates their images by a fixed amount, for instance more than $1/4$. This proves sensitive dependence on initial conditions as well. The binary shift has full two-symbol chaotic dynamics.

For any function $f:X\to \mathcal{P}(X)$, form the diagonal subsetIf $f$ were surjective, some $d\in X$ would satisfy $f(d)=D$. Then $d\in D$ would hold exactly when $d\notin D$, which is impossible. Thus no set surjects onto its power set, including the empty-set case. This is Cantor's theorem proved by the Cantor diagonal argument.

Use real-number pairing by separated digits for an explicit injection ${\mathbb{R}}^2\to \mathbb{R}$. First map a real number to $(0,1)$ by $q(x)=\frac{1}{2}+{\pi }^{-1}\arctan x$, and use its unique binary expansion that is not eventually all ones. If $q(x)={\sum }_{n\ge 1}{a}_n{2}^{-n}$ and $q(y)={\sum }_{n\ge 1}{b}_n{2}^{-n}$, defineThis places the two binary digit strings in alternating ternary positions. Such ternary strings, using only digits zero and one, are unique: at a first differing position $k$, the difference $3^{-k}$ exceeds the maximum tail ${\sum }_{j>k}{3}^{-j}=\frac{1}{2}{3}^{-k}$. Thus the output recovers both digit strings and both inputs. The use of base three avoids any endpoint ambiguity caused by interleaving digits in base two.

For a fixed $A\subseteq {\mathbb{R}}^2$, the affine sections of a planar set are indexed byThere is an injection $\iota :\mathcal{I}\to \mathbb{R}$, for example by applying $J$ to each coordinate pair and then once more to those two results. Suppose every subset of $\mathbb{R}$ were a section of $A$. Define a function from $\mathbb{R}$ to $\mathcal{P}(\mathbb{R})$ by assigning to $\iota (\mathbf{a},\mathbf{b})$ the corresponding section, and assigning the empty set to every real outside $\iota (\mathcal{I})$. Injectivity of $\iota$ makes this definition unambiguous. It would be a surjection onto $\mathcal{P}(\mathbb{R})$, contradicting the first argument. No planar set has every subset of the real line as a section. Allowing different parametrizations of the same line does not evade this obstruction.

For all countable sets, however, such a planar set does exist. To build one, first encode every real sequence $s=(s_1,s_2,\dots )$ by one real number. Let $a_{nk}$ be the canonical binary digits of $q(s_n)$, and choose the explicit indexingThis is a bijection from positive integer pairs to positive integers. Define the coding of real sequences by ternary digitsThe same first-differing-digit argument proves that $c$ is injective; all its values lie in $[0,1/2]$. Now takeFor every nonempty countable set $S\subseteq \mathbb{R}$, choose an enumeration $s$ of $S$, repeating terms if $S$ is finite. On the vertical line with $\mathbf{a}=(c(s),0)$ and $\mathbf{b}=(0,1)$, the section of $A$ is precisely $S$: injective sequence coding means no other sequence can contribute extra values in this column. The empty set is the section on the line $x=2$, since all code columns have first coordinate at most $1/2$. This constructs the required universal planar set for countable real sections. No assertion about its other, nonvertical sections is needed.

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.