<p>I have a small, self-contained, math question, whose motivation is from theoretical computer science (specifically, list decoding of algebraic codes, derivative/multiplicity codes, etc).
I wonder whether someone might have an idea.</p>

<p>I'm looking for an operator T that can be applied to m-variate polynomials over a finite field.
When applied to a polynomial, the operator should yield a polynomial of not much higher degree. The operator should satisfy the following property:
for every m-variate polynomial $F$, and m univariate non-constant polynomials $g_1,...,g_m$, if you know $g_1,...,g_m$ and $F(g_1(t),...,g_m(t))$ for a parameter t, then you can also compute $TF(g_1(t),...,g_m(t))$. The operator should be non-trivial, in the sense that for a fixing $x_1,..,x_m$, the value $F(x_1,...,x_m)$ does not determine the value of $TF(x_1,...,x_m)$. </p>

<p>For $m=1$, the derivative operator gives exactly that:
By the chain rule
$(F(g(t)))&#39; = F&#39;(g(t))\cdot g&#39;(t)$, which implies that
$F&#39;(g(t)) = (F(g(t)))&#39;/g&#39;(t)$.
My question is whether there is an operator that works for general m.</p>

CC BY-SA 3.0
2012-03-28T17:43:28.123Z
Why total derivative wouldn't fit your requirements?
Tegiri Nenashi
CC BY-SA 3.0
2012-03-28T19:24:46.830Z
Suppose you take $TF(g_1(t),..,g_m(t)) = \sum_{i=1}^{m} g_i'(t) dF(x_1,...,x_m)/dx_i$ (known as the total derivative). How you do compute $dF(x_1,...,x_m)/dx_i$ from $F(g_1(t),...,g_m(t))$?
Dana Moshkovitz
CC BY-SA 3.0
2012-03-29T15:27:41.193Z
Your example in one dimensional case is not flawless. What if $g'(t)=0$ ?
Tegiri Nenashi
CC BY-SA 3.0
2012-03-29T16:11:21.927Z
If g' is identically zero then you can't expect anything (I'll edit the question to specify the g_i's are not identically zero).
Dana Moshkovitz
CC BY-SA 3.0
2012-03-29T17:31:16.093Z
Suppose $g(t) = t^2$. You still can't evaluate $F'$ at 0? (I understand that you want point-wise evaluation)
Tegiri Nenashi
CC BY-SA 3.0
2012-03-29T19:58:23.400Z
F(g(t))' and g'(t) are formal polynomials in t. You can divide the formal polynomials.
Dana Moshkovitz
CC BY-SA 3.0
2012-10-24T19:16:09.123Z
Dana, I may be missing something, what about $TF(x_1,...,x_n) = T(x_1,...,x_n) P(x_1, ..., x_n)$, where $P$ is some multivariate polynomial?
mkatkov
CC BY-SA 3.0
2012-10-30T21:56:06.520Z
Honestly, I asked this question so long ago, I only barely remember what I needed it for :-)... I believe that the issue is that multiplying by a fixed polynomial is "trivial" in the sense that to compute the multiplication at a point, you only need to know the value of F at the point (and nothing about F's inner-workings).
Dana Moshkovitz
<it.information-theory><coding-theory><algebra><polynomials>
Looking for an operator on polynomials
Dana Moshkovitz
# Looking for an operator on polynomials

(Asked by: username_0 on 2012-03-28)

I have a small, self-contained, math question, whose motivation is from theoretical computer science (specifically, list decoding of algebraic codes, derivative/multiplicity codes, etc).
I wonder whether someone might have an idea.

I'm looking for an operator T that can be applied to m-variate polynomials over a finite field.
When applied to a polynomial, the operator should yield a polynomial of not much higher degree. The operator should satisfy the following property:
for every m-variate polynomial $F$, and m univariate non-constant polynomials $g\_1,...,g\_m$, if you know $g\_1,...,g\_m$ and $F(g\_1(t),...,g\_m(t))$ for a parameter t, then you can also compute $TF(g\_1(t),...,g\_m(t))$. The operator should be non-trivial, in the sense that for a fixing $x\_1,..,x\_m$, the value $F(x\_1,...,x\_m)$ does not determine the value of $TF(x\_1,...,x\_m)$.

For $m=1$, the derivative operator gives exactly that:
By the chain rule
$(F(g(t)))' = F'(g(t))\cdot g'(t)$, which implies that
$F'(g(t)) = (F(g(t)))'/g'(t)$.
My question is whether there is an operator that works for general m.

**Tags:** it.information-theory, coding-theory, algebra, polynomials
> **Comments:**
> **username_1**: Why total derivative wouldn't fit your requirements?  
> **username_0**: Suppose you take $TF(g_1(t),..,g_m(t)) = \sum_{i=1}^{m} g_i'(t) dF(x_1,...,x_m)/dx_i$ (known as the total derivative). How you do compute $dF(x_1,...,x_m)/dx_i$ from $F(g_1(t),...,g_m(t))$?  
> **username_1**: Your example in one dimensional case is not flawless. What if $g'(t)=0$ ?  
> **username_0**: If g' is identically zero then you can't expect anything (I'll edit the question to specify the g_i's are not identically zero).  
> **username_1**: Suppose $g(t) = t^2$. You still can't evaluate $F'$ at 0? (I understand that you want point-wise evaluation)  
> **username_0**: F(g(t))' and g'(t) are formal polynomials in t. You can divide the formal polynomials.  
> **username_2**: Dana, I may be missing something, what about $TF(x_1,...,x_n) = T(x_1,...,x_n) P(x_1, ..., x_n)$, where $P$ is some multivariate polynomial?  
> **username_0**: Honestly, I asked this question so long ago, I only barely remember what I needed it for :-)... I believe that the issue is that multiplying by a fixed polynomial is "trivial" in the sense that to compute the multiplication at a point, you only need to know the value of F at the point (and nothing about F's inner-workings).  

---

## 0 answers

