16

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.

Community
  • 1
Dana Moshkovitz
  • 10,979
  • 1
  • 50
  • 77
  • Why total derivative wouldn't fit your requirements? – Tegiri Nenashi Mar 28 '12 at 17:43
  • 1
    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 Mar 28 '12 at 19:24
  • 1
    Your example in one dimensional case is not flawless. What if $g'(t)=0$ ? – Tegiri Nenashi Mar 29 '12 at 15:27
  • 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 Mar 29 '12 at 16:11
  • Suppose $g(t) = t^2$. You still can't evaluate $F'$ at 0? (I understand that you want point-wise evaluation) – Tegiri Nenashi Mar 29 '12 at 17:31
  • 1
    F(g(t))' and g'(t) are formal polynomials in t. You can divide the formal polynomials. – Dana Moshkovitz Mar 29 '12 at 19:58
  • 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 Oct 24 '12 at 19:16
  • 1
    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 Oct 30 '12 at 21:56

0 Answers0