Free-semigroup Toeplitz layer

1. Integration point: implement this as a message-mixing layer for rooted trees, hierarchical sequences, syntax trees, or graph neighborhoods represented as word-indexed hidden states. The input is \(H\in\mathbb{R}^{B\times d_M\times h}\), one hidden vector per word of length at most \(M\). Learn shared matrices \(Q_w\in\mathbb{R}^{h\times h}\) for every word with \(1\leq |w|\leq K\), plus \(Q_0\). This replaces a dense \(d_Mh\times d_Mh\) operator. 2. Pseudocode: precompute integer indices for every word and its extensions. Set \(Y=HQ_0^T\). For each word \(w\), gather every valid node \(v\) and its descendant \(wv\); add the forward contribution \(H[v]Q_w^T\) to the descendant output and add the reverse contribution \(H[wv]Q_w\) to the ancestor output. Mask nonexistent descendants, divide or normalize by the number of active neighbors, apply LayerNorm and an activation. This realizes \(Y=P_MT_qP_MH\). 3. Compute the index map exactly. Estimate spectral diagnostics without eigendecomposition using Rademacher vectors \(z_s\): \(\operatorname{Tr}(A^r)\approx S^{-1}\sum_s z_s^TA^rz_s\), where \(A=P_MT_qP_M\), and estimate the spectral radius by 10 to 20 power iterations. 4. First experiment: compare this layer against a dense MLP and ordinary tree message passing on synthetic binary and 4-ary tree classification, using matched hidden width and FLOPs. Sweep \(M\in\{4,6\}\) and \(K\in\{1,2\}\). Measure parameter count, activation memory, validation accuracy, loss at equal FLOPs, gradient norms by depth, and estimated spectral radius. Success is at least 2x lower parameter or activation memory at equal accuracy, with fewer exploding or vanishing gradients as tree depth grows.