16
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ Why total derivative wouldn't fit your requirements? $\endgroup$ – Tegiri Nenashi Mar 28 '12 at 17:43
  • 1
    $\begingroup$ 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))$? $\endgroup$ – Dana Moshkovitz Mar 28 '12 at 19:24
  • 1
    $\begingroup$ Your example in one dimensional case is not flawless. What if $g'(t)=0$ ? $\endgroup$ – Tegiri Nenashi Mar 29 '12 at 15:27
  • 1
    $\begingroup$ F(g(t))' and g'(t) are formal polynomials in t. You can divide the formal polynomials. $\endgroup$ – Dana Moshkovitz Mar 29 '12 at 19:58
  • 1
    $\begingroup$ 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). $\endgroup$ – Dana Moshkovitz Oct 30 '12 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.