6.31.4  Building a polynomial from its evaluation: genpoly

The genpoly command finds a polynomial which evaluates to a given polynomial.

• genpoly takes three arguments:
  • P, a polynomial with n−1 variables.
  • b, an integer.
  • x, the name of a variable.
• genpoly(P,b,x) returns the polynomial Q with n variables (the n−1 variables in P and the variable x) such that the coefficients of Q are in the interval (−b/2,b/2] and Q|_x=b = P. In other words, P is written in base b but using the convention that the Euclidean remainder belongs to (−b/2,b/2] (this convention is also known as s-mod representation).

Examples.

• Input:
  genpoly(61,6,x)
  Output:

  2 x2−2 x+1

  Indeed 61 divided by 6 is 10 with remainder 1, then 10 divided by 6 is 2 with remainder -2 (instead of the usual quotient 1 and remainder 4 out of bounds),

  61=2*62−2*6+1

• Input:
  genpoly(5,6,x)
  Output:

  x−1

  Indeed: 5=6−1.
• Input:
  genpoly(7,6,x)
  Output:

  x+1

  Indeed: 7=6+1
  
• Input:
  genpoly(7*y+5,6,x)
  Output:

  x y+x+y−1

  Indeed: x*y+x+y−1=y(x+1)+(x−1).
• Input:
  genpoly(7*y+5*z^2,6,x)
  Output:

  x y+x z2+y−z2

  Indeed: x*y+x*z+y−z=y*(x+1)+z*(x−1).