Exact bracket output bit-growth bound

The state set has exactly $2^c$ elements by [F3]. A complete smoothing starts with $m$ circles. At each crossing the four local endpoints lie on one or two current circles, and either smoothing reconnects them into one or two circles. Thus the circle count increases by at most one at each of the $c$ smoothings. Every state has $1\le \mathrm{\mid }S\mathrm{\mid }\le m+c$.

For a fixed state, put $r=\mathrm{\mid }S\mathrm{\mid }-1$, so $0\le r\le m+c-1$. The binomial theorem gives ${\delta }^r=(-1{)}^r{\sum }_{k=0}^r\left(\genfrac{}{}{0px}{}{r}{k}\right)A^{2r-4k}$. These exponents are distinct, so its coefficient l1 norm is ${\sum }_{k=0}^r\left(\genfrac{}{}{0px}{}{r}{k}\right)=2^r$; multiplication by the monomial $A^{a(S)-b(S)}$ only shifts the exponents.

Since $a(S)+b(S)=c$, one has $\mathrm{\mid }a(S)-b(S)\mathrm{\mid }\le c$. The exponents in ${\delta }^r$ lie between $-2r$ and $2r$. Using $r\le m+c-1$, every exponent in every state term, and thus in the sum, has absolute value at most $c+2(m+c-1)=3c+2m-2$.

Put $q=c+m+1\ge 2$. Represent a crossing endpoint by an integer from $1$ to $4c$, grouped into four successive ports at each crossing, and write $\alpha$ for the supplied edge-pairing involution. For a state, let $\beta$ pair the two left and two right ports for A, or the two top and two bottom ports for B. The multigraph on the $4c$ endpoints with one $\alpha$-edge and one $\beta$-edge at every vertex is two-regular, allowing parallel edges. Each connected component follows one smoothed circle, and the $u$ supplied crossingless components add $u$ further circles. Thus a traversal marking a vertex when first queued computes $\mathrm{\mid }S\mathrm{\mid }$ exactly. The same traversal, with the opposite ports paired instead of smoothing ports, computes the original component count $m$; perform it once initially and then compute $q$ for allocation. Use binary counters and linear scans for all table and mark lookups: there are $O(q)$ endpoint visits, each using a bounded number of scans of $O(q)$ records with $O(\log q)$ index bits. Even with a work-tape queue or stack scanned linearly, each visit costs $O(q^2)$ bit steps, so tracing costs $O(q^3)$. Computing $a(S)-b(S)$ and adding $u$ use counters of $O(\log q)$ bits and fit this bound. Enumerate the states with a $c$-bit binary counter, making exactly $2^c$ visits; the $c=0$ case is one empty mask with $\mathrm{\mid }S\mathrm{\mid }=u=m$. Reading the stated input takes $O(q\log q)$ steps and is included.

Summing over all $2^c$ states, the l1 norm of the final coefficient sequence is at most the sum of the state-term l1 norms, hence at most $2^c{2}^{m+c-1}=2^{m+2c-1}$. Every individual coefficient therefore has absolute value at most $2^{m+2c-1}$.

Let $M=m+2c\ge 1$. By step 3.1, a nonzero coefficient $z_j$ satisfies $\mathrm{\mid }{z}_j\mathrm{\mid }\le 2^{M-1}$, so $\mathrm{\mid }{z}_j\mathrm{\mid }+1\le 2^M$ and ${\mathrm{\ell }}_{\mathbb{Z}}(z_j)=1+\lceil {\log }_2(\mathrm{\mid }{z}_j\mathrm{\mid }+1)\rceil \le M+1=m+2c+1$. The support lies in at most $6c+4m-3$ integer exponents by step 2.2, so storing the exact polynomial as a dense coefficient array takes $O((c+m{)}^2)$ bits. For a knot, $m=1$, giving degree at most $3c$ and coefficient-bit size at most $2c+2$, both linear in $c+1$.

Use coefficient slots for every exponent from $-3q$ to $3q$, padded with zeros, and use $2q+3$ bits per signed-magnitude slot, plus $O(\log q)$-bit position counters. These arrays have $O(q^2)$ tape cells. Every partial accumulator, not just the final sum, has coefficient l1 norm at most $2^c{2}^{m+c-1}$: apply the triangle inequality in step 3.1 to the subset of states already processed. Hence its coefficients fit the chosen width, since $m+2c-1<2q$. For one state compute $r=\mathrm{\mid }S\mathrm{\mid }-1$ and start with the array for $P_0=1$. For $k=0,\dots ,r-1$, form a new array by the exact recurrence $(P_{k+1}{)}_j=-(P_k{)}_{j-2}-(P_k{)}_{j+2}$, reading absent coefficients as zero. This is multiplication by $\delta$, so $P_r={\delta }^r$. All intermediate powers have degree at most $2r<2q$ and l1 norm at most $2^r\le 2^{m+c-1}$, so they too fit the arrays and widths.

Here is a direct tape bound without unit-cost access or integer arithmetic. To retrieve or write a coefficient, scan an entire array of $O(q)$ slots of $O(q)$ bits, advancing a binary slot counter and comparing it with the desired index. The counter work is $O(q\log q)$ and the scanned data have $O(q^2)$ bits, so one lookup or write costs $O(q^2)$ bit steps. Addition or subtraction of two signed integers in these slots is performed by sign comparison, a linear magnitude comparison, and the usual binary carry or borrow scan, costing $O(q)$ steps; the extra carry bit fits the reserved width. For each of the $O(q)$ destination coefficients in the recurrence of step 4.2, make at most two source lookups, one such addition, and one destination write. A multiplication by $\delta$ therefore costs $O(q^3)$ steps. There are $r<q$ repetitions, giving $O(q^4)$ work. Shift this state polynomial by $a(S)-b(S)$ and add it to the accumulator coefficient by coefficient using the same linear scans; the state shift has magnitude at most $c$, its support stays inside the slots by step 2.2, and this accumulation costs $O(q^3)$. Clearing arrays, moving the state counter, and loop-index bookkeeping are bounded by the same charges.

Summing the per-state bounds in steps 2.3, 4.2, and 5.1 over exactly $2^c$ visits gives $O(2^c{q}^4)$ bit steps. The initial component-count traversal costs $O(q^3)$ by step 2.3; coefficient-array initialization and writing the dense exact output cost $O(q^2)$. These are absorbed because $2^c\ge 1$ and $q\ge 2$. The loop tracing and arithmetic realize exactly the state terms in [F2], so [F3] identifies the result with the bracket. When $c=0$, the single state computes ${\delta }^{m-1}$ with the same bound; when $m=1$, $q=c+2$ gives $O(2^c(c+1{)}^4)$. All choices and operations are finite. The bit-cost argument concerns only the specified indexed table and elementary binary operations, so it makes no claim about parsing arbitrary code strings of length $L$ or the cost of an unspecified arithmetic library.