Support-Budgeted Hamming Polynomial Layer

Integrate this as the first feature-mixing layer for data represented by N categorical variables, binary attributes, or token-level indicator features. Encode each variable x_j as a q-th root of unity or as its real and imaginary parts. Choose a maximum interaction order S, usually 2 or 3. Enumerate interaction tuples (j_1,...,j_s) with distinct coordinates and Fourier frequencies k_{j_r} in {1,...,q-1}; omit the constant frequency. The layer computes y=base(x)+sum_{s=1}^S sum_{|supp(k)|=s} a_k product_j x_j^{k_j}, followed by a real projection and normalization. Attach the penalty R_BH to the training objective, using p_s=2s/(s+1); for numerical stability, implement the p_s quasi-norm as (sum_k (|a_k|^2+epsilon)^{p_s/2})^{1/p_s}. If the full interaction list is too large, sample a fixed number of tuples per order, maintain their coefficients in a hashed table, and rescale sampled sums by inverse inclusion probability. Estimate ||f_s||_infinity empirically as the maximum absolute order-s contribution over the current minibatch; optionally clip each order when its empirical coefficient norm exceeds B_hat_s times this maximum. The exact mathematical quantities are the support partition and p_s exponents; B_{q,s} can initially be treated as a tunable constant or estimated from random batch evaluations. First test on synthetic parity/XOR tasks and a small categorical tabular benchmark using a 2-layer MLP baseline with equal parameter count. Compare dense features, unrestricted Fourier interactions, and S=2 or S=3 support-budgeted layers. Success means better validation accuracy or sample efficiency at equal parameters, reduced sensitivity to learning rate, and lower contribution from high-order terms without degradation on tasks requiring only low-order interactions.