Assume I am given two polynomials f ( x ) and g ( x ) with coefficients from a field F p , where p is a prime. Now I know that the set of these polynomials is a ring and not a field, meaning that not every polynomial has an inverse.Given evaluation points f ( α 1 ) , g ( α 1 ) , f ( α 2 ) , g ( α 2 ) , … for some distinct values α i , one can first compute evaluation points h ( α i ) := f ( α i ) / g ( α i ) and then interpolate the polynomial h ( x ) = f ( x ) / g ( x ) from them such that the interpolated polynomial h contains the correct roots in the numerator and denominator. For example if the polynomial f has roots a, b, c and g has roots b, c, and d, then the interpolated rational function h will have a numerator with the root a and the denominator will have the root d.My confusion stems from the fact that g ( x ) may not have an inverse, yet we can interpolate a polynomial 1 / g ( x ), which is basically an inverse or not?P.S. In case it helps, I only care about polynomials of the form f ( x ) = ( x − a 1 ) ( x − a 2 ) . . . x ( a k ), where for all i ≠ j it holds that a i ≠ a j .

Question

Assume I am given two polynomials   f  (  x  ) and   g  (  x  ) with coefficients from a field             F        p  , where   p is a prime. Now I know that the set of these polynomials is a ring and not a field, meaning that not every polynomial has an inverse.Given evaluation points   f  (      α    1    )  ,  g  (      α    1    )  ,  f  (      α    2    )  ,  g  (      α    2    )  ,  … for some distinct values       α    i  , one can first compute evaluation points   h  (      α    i    )  :=  f  (      α    i    )      /    g  (      α    i    ) and then interpolate the polynomial   h  (  x  )  =  f  (  x  )      /    g  (  x  ) from them such that the interpolated polynomial   h contains the correct roots in the numerator and denominator. For example if the polynomial   f has roots   a,  b,  c and   g has roots   b,   c, and   d, then the interpolated rational function   h will have a numerator with the root   a and the denominator will have the root   d.My confusion stems from the fact that   g  (  x  ) may not have an inverse, yet we can interpolate a polynomial   1      /    g  (  x  ), which is basically an inverse or not?P.S. In case it helps, I only care about polynomials of the form   f  (  x  )  =  (  x  −      a    1    )  (  x  −      a    2    )  .  .  .  x  (      a    k    ), where for all   i  ≠  j it holds that       a    i    ≠      a    j  .

Mollie Roberts · Accepted Answer

&quot;a field             F        p  , where   p is a prime.&quot;In the paper   p is not necessarily a prime, see the last paragraph of Section 3.1. “For the rest of the paper we will interpret all bitstrings as elements of             F        q  , without specifying a choice of   q”.Given evaluation points   f  (      α    1    )  ,  g  (      α    1    )  ,  f  (      α    2    )  ,  g  (      α    2    )  ,  … for some distinct values       α    i  , one can first compute evaluation points   h  (      α    i    )  :=  f  (      α    i    )      /    g  (      α    i    ) and then interpolate the polynomial   h  (  x  )  =  f  (  x  )      /    g  (  x  ) from them such that the interpolated polynomial   h contains the correct roots in the numerator and denominator. For example if the polynomial   f has roots   a,  b,  c and   g has roots   b,   c, and   d, then the interpolated rational function   h will have a numerator with the root   a and the denominator will have the root   d.My confusion stems from the fact that   g  (  x  ) may not have an inverse, yet we can interpolate a polynomial   1      /    g  (  x  ), which is basically an inverse or not?I guess you are speaking about Theorems 4.1 and B.1. They deal with rational functions   f  =  P      /    Q, which are more general than polynomials   P. Given a support set   {  (      k    i    ,      r    i    )  } such that   f  (      k    i    )  =      r    i   for each   i we don’t interpolate   f as a polynomial, we recover it. For zeroes of   Q are provided tagged values, see Section 4.3. Theorem B.1 is parallel to Theorem 4.1 and assures that under the given conditions we indeed can recover   f, that is reconstruct   P and   Q uniquely from a support set for   f.

Assume I am given two polynomials f ( x ) and g ( x ) with coefficients from a f

Answered question

Answer & Explanation

New Questions in Algebra II