Skip to main content
3 of 4
added 35 characters in body

When does composing polynomials reduce the degree?

Let $\mathbb{F}$ be the field of size 2. Say I have functions $p_1,\ldots,p_m : \mathbb{F}^n \to \mathbb{F}$ each with high degree $\approx n$ as (multilinear) polynomials, and another function $s : \mathbb{F}^m \to \mathbb{F}$ also with high degree $\approx m$. Are there general properties of $s$ and the $p_i$ that characterize when $f(x) := s(p_1(x),\ldots,p_m(x)) : \mathbb{F}^n \to \mathbb{F}$ can have very low degree, i.e. degree $\ll n$?

It's easy to come up with toy examples -- I'm wondering if there are any general statements one can make. E.g., some relationship among the $p_i$ that says that no choice of $s$ can reduce the degree too much, or a proof that for any set of $p_i$ there is some $s$ that reduces the degree by a lot, etc.