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.
