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$
8
  • $\begingroup$ Why total derivative wouldn't fit your requirements? $\endgroup$
    – Tegiri Nenashi
    Mar 28, 2012 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, 2012 at 19:24
  • 1
    $\begingroup$ Your example in one dimensional case is not flawless. What if $g'(t)=0$ ? $\endgroup$
    – Tegiri Nenashi
    Mar 29, 2012 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, 2012 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, 2012 at 21:56

0

Reset to default

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.