# Composition proof

$$ \def\F{\mathbb F} $$

**Context.** Are values are from a

**Goal.** *Given $P\in\F_{< N}[X]$ Proof the following constraint using Schwartz-Sippel and a $\le N$ low degree test:*

$$ F(G(X)) \mod H(X) = 0 $$

$$ \frac{P(X)^{2^{64}} - 1}{X^N - 1} $$

**Lemma.** *Polynomials satisfying the above constraint satisfy $P(\omega_N^i) = \omega_{2^{64}}^{k_i}$ for $i \in [0,N)$.*

**Definition.** *$\F_{< N}[X] \sim \F[X]/ X^N$*

Assume for the moment $N = 2^{64}$, we can generalize later

$$ \frac{P(X)^N - 1}{X^N - 1} $$

This puts some constraints on the coefficients of $P$.

$$ P(X) = \sum_{i\in[0,N)} p_i X^i $$

$$ \frac{P(X)^N - 1}{X^N - 1} = \frac{\left(\sum_{i\in[0,N)} p_i X^i\right)^N - 1}{X^N - 1} $$

We can now expand using something like the https://en.wikipedia.org/wiki/Binomial_theorem, i.e. https://en.wikipedia.org/wiki/Multinomial_theorem.

**To do.** Look into differentials.

## Simplifications

We can further restrict the problem to the case $h(x) = x^n - 1$. This can help because we can now factor $h$ as

$$ h(x) = (x - ω_n^0) (x - ω_n^1) (x - ω_n^2) \cdots (x - ω_n^{n-1}) $$

or (thanks Yan Zhang)

$$ h(x) = (x - 1) (x + 1) (x^2 + 1) (x^4 + 1) \cdots (x^n + 1) $$

The problem could be broken solved modulo these factors and then invoke CRT.