Let $\mathcal X:=\{\varepsilon,\dots,U\}$ be the set of input numbers with resolution $\varepsilon=b^{m}$ and choose $\Phi = \{m,\dots,n\}$ so that $\mathcal F$ uniquely encodes the entire number range. Assume each encoding component has a finite precision $P$ (i.e., can represent $P$ distinct states). Suppose there exists an operator $\otimes_\phi:\mathbb T^{|\Phi|}\times\mathbb T^{|\Phi|}\mapsto\mathbb T$ such that $\otimes_\phi(\mathcal F(x),\mathcal F(y)) := \mathcal F_\phi(xy)$ for each output frequency $\phi\in\Phi$. Let $S_\phi^x,S_\phi^y\subseteq\Phi$ be the subsets of input frequencies that $\otimes_\phi$ is required to take as input from $\mathcal F(x)$ and $\mathcal F(y)$, respectively. Then:
- Non-locality. The operator $\otimes_\phi$ must access at least $d = \mathcal O\left(\log_P(U/\varepsilon)\right)$ components from each input vector with $|S_\phi^x|,\;|S_\phi^y|\;\ge\;\left\lceil \log_P |\mathcal X| \right\rceil$.
- Computational complexity. The operator $\otimes$ must perform a computation functionally equivalent to polynomial multiplication.
Proof.
1. Non-locality. The proof follows from a counting argument. Assume for contradiction that $|S_\phi^x|<\log_P|\mathcal X|$. Then the projection of $\mathcal{F}(x)|_{S_\phi^x}$, which is the only information about $x$ available to $\otimes_\phi$, can represent at most $P^{|S_\phi^x|}$ states. By the pigeonhole principle, there exist $x_1, x_2 \in \mathcal{X}$ with $x_1 \neq x_2$ that are indistinguishable to the operator, i.e., $\mathcal{F}(x_1)|_{S_\phi^x} = \mathcal{F}(x_2)|_{S_\phi^x}$. Let $\Delta:=x_1-x_2\neq 0$. The set $Y^*:=\{y\in \mathcal X:\; b^\phi \Delta y\in\mathbb Z\}$ is a proper subset of $\mathcal X$, so we can pick $y^\star\in\mathcal X \setminus Y^*$. Then $\mathcal F_\phi(x_1 y^\star)\neq \mathcal F_\phi(x_2 y^\star)$, yet $\otimes_\phi$ sees identical inputs from $\mathcal F(x_1)$ and $\mathcal F(x_2)$, which is a contradiction. The operator $\otimes_\phi$ is required by its definition to produce these two different outputs. However, since its inputs for $x_1$ and $x_2$ are identical ($\mathcal{F}(x_1)|_{S_\phi^x} = \mathcal{F}(x_2)|_{S_\phi^x}$), it is forced as a function to produce the same output for both. It cannot satisfy both conditions. Thus, the initial assumption must be false and $|S_\phi^x|\ge\lceil\log_P|\mathcal X|\rceil$. The same holds for $|S_\phi^y|$.
2. Computational complexity.
Multiplication in any positional system is equivalent to the discrete convolution of the coefficients $k$ and $l$, followed by carry propagation.
Write $x=\sum_{i} k_i b^i$ and $y=\sum_{j} l_j b^j$ as the sum of their coefficients. Then
$xy=\sum_{\tau}(k*l)_\tau b^\tau, \quad
(k*l)_\tau=\sum_{i+j=\tau}k_i l_j.$
Interpreting the circular sinusoidal component in its interval $[0,1)$ wrap-around form,
we can view the phase vector of the encoding, $\Theta_x \in [0, 1)^{|\Phi|}$, as a linear transformation of the coefficient vector $k$ modulo 1. From the definition of the encoding, the component at frequency $\phi$ accumulates contributions from lower-order coefficients:
$[\Theta_x]_\phi = \big( \sum_{i < \phi} k_i b^{i-\phi} \big) \bmod 1.$
This forms a linear system $\Theta_x \equiv Mk \bmod 1$, where $M$ is a lower-triangular mixing matrix with entries $M_{\phi,i} = b^{i-\phi}$ for $i < \phi$ and $0$ otherwise. Since the encoding uniquely represents the number range, $M$ is invertible over the domain.
To compute the encoding $\mathcal{F}(xy)$ of the product, the operator must produce the phase vector $\Theta_{xy} \equiv M(k * l) \bmod 1$. We analyze two pathways for this from inputs $\Theta_x$ and $\Theta_y$:
Pathway A: Disentangle First.
One effectively inverts the mixing matrix to recover coefficients: $k = M^{-1}\Theta_x$ and $l = M^{-1}\Theta_y$. The product is then computed as $\Theta_{xy} = M(M^{-1}\Theta_x * M^{-1}\Theta_y)$. The operation $M^{-1}$ represents the full cost of decoding the sinusoidal representation into positional digits.
Pathway B: Disentangle Later.
Alternatively, one might attempt to compute the result directly from the entangled phases. Any bilinear operation on the inputs can be expressed via the Kronecker product $\Theta_x \otimes_K \Theta_y$. Substituting the linear forms yields:
$\Theta_x \otimes_K \Theta_y = (Mk) \otimes_K (Ml) = (M \otimes_K M)(k \otimes_K l).$
The vector $k \otimes_K l$ contains all cross-terms $k_i l_j$. To construct the convolution $h$, one must sum all subsets of these cross-terms where $i+j=\tau$. However, the term $\Theta_x \otimes_K \Theta_y$ does not provide direct access to $k_i l_j$, only linear combinations weighted by the expanded mixing matrix $M \otimes_K M$.
Isolating the necessary convolution terms from the bilinear expansion requires inverting this mixing process.
This removal $(M \otimes_K M)^{-1} = M^{-1} \otimes_K M^{-1}$ of the cross-term redundancies is therefore computationally at least as expensive as the initial decoding $M^{-1}$.
Moreover, under finite precision, the condition number satisfies $\kappa(M \otimes_K M)=\kappa(M)^2$ with $\kappa(M)\ge1$, which means that postponing disentanglement amplifies quantization errors.
Since both pathways require inverting the linear mixing $M$, there exists no shortcut in the sinusoidal domain.
Any correct operator $\otimes$ must inherently learn the multi-stage procedure: (1) a non-local decoding of the sinusoidal inputs into internal coefficient sequences for $x$ and $y$, (2) a convolution of these sequences, followed by (3) a carry propagation step, and finally (4) a re-encoding of the result into the sinusoidal format.
