# Polynomial-expander feature mixer

- ID: 197
- Canonical URL: https://synthcore.org/idea/197/polynomial-expander-feature-mixer
- API JSON: https://synthcore.org/api/idea/197.json
- API Markdown: https://synthcore.org/api/idea/197.md
- Verification status: unverified
- Source: [arXiv:2608.26349](https://arxiv.org/abs/2608.26349)
- Category: architecture
- Solves: accuracy, memory, generalization
- ML areas: embedding, mlp, retrieval
- Math tags: combinatorics, algebra, approximation-theory
- Ratings: usefulness 4/10; difficulty 4/10; novelty 7/10

## Idea description

Insert a fixed polynomial mixer before an MLP or retrieval index for tuples of discrete features. The mixer maps n+2 bounded scalar feature codes to one or several expanded scalar codes, and the paper's theorem guarantees that its image cannot collapse below order |A|^n when all coordinates come from a finite alphabet A. Use multiple independent permutations or coefficient choices to obtain a vector representation while retaining the deterministic algebraic structure.

## Mathematical statement

For fixed integer n at least 2, define P from C^(n+2) to C by P(x_1,...,x_{n+2}) = sum from i=1 to n of (x_2-x_1)^(i-1) x_1^(n-i) x_{i+2}. Here x_1 and x_2 are distinguished input coordinates and x_{i+2} is the coefficient-like coordinate associated with degree i-1. The paper proves that for every finite set A contained in C, there is a constant c_n greater than 0, depending only on n, such that |{P(x_1,...,x_{n+2}): x_i in A}| is at least c_n |A|^n. The transferable property is combinatorial expansion: among |A|^(n+2) possible tuples, the scalar output assumes at least order |A|^n distinct values. This is an exact discrete guarantee, not a claim that nearby real-valued inputs remain separated.

## Key formulas

- $$P(x_{1},x_{2},\ldots,x_{n+2})=\sum_{i=1}^{n}(x_{2}-x_{1})^{i-1}x_{1}^{n-i}x_{i+2}.$$
- $$\left|\left\{P(x_{1},x_{2},\ldots,x_{n+2}):x_i\in A\right\}\right|\ge c_n|A|^n,\qquad A\subset\mathbb C,\ n\ge2.$$
- $$z=\sum_{i=1}^{n}(u_2-u_1)^{i-1}u_1^{n-i}u_{i+2},\qquad u_j=\frac{2e_j}{K-1}-1\in[-1,1].$$

## Implementation notes

Integrate this at the input side of a small MLP, factorization machine, or retrieval key generator for examples containing n+2 categorical fields. First assign every category a scalar code e_j in {0,1,...,K-1}, normalize it to u_j = 2e_j/(K-1)-1, and group n+2 fields per mixer. Compute the polynomial by Horner evaluation to avoid separately materializing powers: set q = u_2-u_1, initialize z = 0, and for i = n,n-1,...,1 update z = q*z + u_1^(n-i)*u_{i+2}; alternatively precompute the n powers of u_1 for a vectorized batch. For a useful vector representation, create r channels using independent random permutations of the field order and independent signed affine codes, yielding z_1,...,z_r, then concatenate them with ordinary embeddings before the MLP. Keep the polynomial path fixed initially; optionally learn a small affine scale and bias after it, not the polynomial coefficients, so the discrete expansion property remains interpretable. The formula and cardinality lower bound come from the paper; the normalized coding, multiple channels, and Horner implementation are engineering adaptations. Estimate empirical expansion by enumerating all tuples for small K, counting unique quantized outputs, and measuring collision rates on held-out tuples. The first experiment should use n=3, K in {8,16,32}, and a two-layer MLP on synthetic parity, interaction, and Criteo-style categorical subsets. Compare against concatenated embeddings, a learned linear projection to one scalar, and random hashing at equal stored feature dimension. Success means lower unseen-tuple collision rate and equal-or-better downstream accuracy with less embedding memory; explicitly monitor activation magnitude, gradient norm, and sensitivity to code permutations because the theorem does not guarantee numerical separation after floating-point rounding.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.