ReduceCoefficientsDim0 - Maple Help

RegularChains[FastArithmeticTools]

 ReduceCoefficientsDim0
 reduce the coefficients of a polynomial w.r.t a 0-dim regular chain

 Calling Sequence ReduceCoefficientsDim0(f, rc, R)

Parameters

 R - a polynomial ring rc - a regular chain of R f - polynomial of R

Description

 • The command ReduceCoefficientsDim0 returns the normal form of f w.r.t. rc in the sense of Groebner bases.
 • rc is assumed to be a normalized zero-dimensional regular chain and all variables of f but the main one must be algebraic w.r.t. rc. See the subpackage ChainTools for more information about these concepts.
 • R must have a prime characteristic $p$ such that FFT-based polynomial arithmetic can be used for this computation. The higher the degrees of f and rc are, the larger must be $e$ such that ${2}^{e}$ divides $p-1$.  If the degree of f or rc is too large, then an error is raised.
 • The algorithm relies on the fast division trick (based on power series inversion) and FFT-based multivariate multiplication.

Examples

 > $\mathrm{with}\left(\mathrm{RegularChains}\right)$
 $\left[{\mathrm{AlgebraicGeometryTools}}{,}{\mathrm{ChainTools}}{,}{\mathrm{ConstructibleSetTools}}{,}{\mathrm{Display}}{,}{\mathrm{DisplayPolynomialRing}}{,}{\mathrm{Equations}}{,}{\mathrm{ExtendedRegularGcd}}{,}{\mathrm{FastArithmeticTools}}{,}{\mathrm{Inequations}}{,}{\mathrm{Info}}{,}{\mathrm{Initial}}{,}{\mathrm{Intersect}}{,}{\mathrm{Inverse}}{,}{\mathrm{IsRegular}}{,}{\mathrm{LazyRealTriangularize}}{,}{\mathrm{MainDegree}}{,}{\mathrm{MainVariable}}{,}{\mathrm{MatrixCombine}}{,}{\mathrm{MatrixTools}}{,}{\mathrm{NormalForm}}{,}{\mathrm{ParametricSystemTools}}{,}{\mathrm{PolynomialRing}}{,}{\mathrm{Rank}}{,}{\mathrm{RealTriangularize}}{,}{\mathrm{RegularGcd}}{,}{\mathrm{RegularizeInitial}}{,}{\mathrm{SamplePoints}}{,}{\mathrm{SemiAlgebraicSetTools}}{,}{\mathrm{Separant}}{,}{\mathrm{SparsePseudoRemainder}}{,}{\mathrm{SuggestVariableOrder}}{,}{\mathrm{Tail}}{,}{\mathrm{Triangularize}}\right]$ (1)
 > $\mathrm{with}\left(\mathrm{FastArithmeticTools}\right)$
 $\left[{\mathrm{BivariateModularTriangularize}}{,}{\mathrm{IteratedResultantDim0}}{,}{\mathrm{IteratedResultantDim1}}{,}{\mathrm{NormalFormDim0}}{,}{\mathrm{NormalizePolynomialDim0}}{,}{\mathrm{NormalizeRegularChainDim0}}{,}{\mathrm{RandomRegularChainDim0}}{,}{\mathrm{RandomRegularChainDim1}}{,}{\mathrm{ReduceCoefficientsDim0}}{,}{\mathrm{RegularGcdBySpecializationCube}}{,}{\mathrm{RegularizeDim0}}{,}{\mathrm{ResultantBySpecializationCube}}{,}{\mathrm{SubresultantChainSpecializationCube}}\right]$ (2)
 > $\mathrm{with}\left(\mathrm{ChainTools}\right)$
 $\left[{\mathrm{Chain}}{,}{\mathrm{ChangeOfCoordinates}}{,}{\mathrm{ChangeOfOrder}}{,}{\mathrm{Construct}}{,}{\mathrm{Cut}}{,}{\mathrm{DahanSchostTransform}}{,}{\mathrm{Dimension}}{,}{\mathrm{Empty}}{,}{\mathrm{EqualSaturatedIdeals}}{,}{\mathrm{EquiprojectableDecomposition}}{,}{\mathrm{Extend}}{,}{\mathrm{ExtendedNormalizedGcd}}{,}{\mathrm{IsAlgebraic}}{,}{\mathrm{IsEmptyChain}}{,}{\mathrm{IsInRadical}}{,}{\mathrm{IsInSaturate}}{,}{\mathrm{IsIncluded}}{,}{\mathrm{IsPrimitive}}{,}{\mathrm{IsStronglyNormalized}}{,}{\mathrm{IsZeroDimensional}}{,}{\mathrm{IteratedResultant}}{,}{\mathrm{LastSubresultant}}{,}{\mathrm{Lift}}{,}{\mathrm{ListConstruct}}{,}{\mathrm{NormalizeRegularChain}}{,}{\mathrm{NumberOfSolutions}}{,}{\mathrm{Polynomial}}{,}{\mathrm{Regularize}}{,}{\mathrm{RemoveRedundantComponents}}{,}{\mathrm{SeparateSolutions}}{,}{\mathrm{Squarefree}}{,}{\mathrm{SquarefreeFactorization}}{,}{\mathrm{SubresultantChain}}{,}{\mathrm{SubresultantOfIndex}}{,}{\mathrm{Under}}{,}{\mathrm{Upper}}\right]$ (3)
 > $\mathrm{variables}≔\left[x,y,z\right];$$p≔957349889$
 ${\mathrm{variables}}{≔}\left[{x}{,}{y}{,}{z}\right]$
 ${p}{≔}{957349889}$ (4)
 > $\mathrm{sys}≔\left\{5{y}^{4}-3,-20x+y-z,-{x}^{5}+{y}^{5}-3y-1\right\}$
 ${\mathrm{sys}}{≔}\left\{{-}{20}{}{x}{+}{y}{-}{z}{,}{5}{}{{y}}^{{4}}{-}{3}{,}{-}{{x}}^{{5}}{+}{{y}}^{{5}}{-}{3}{}{y}{-}{1}\right\}$ (5)
 > $R≔\mathrm{PolynomialRing}\left(\mathrm{variables},p\right)$
 ${R}{≔}{\mathrm{polynomial_ring}}$ (6)

We solve a system in 3 variables and 3 unknowns

 > $\mathrm{lrc}≔\mathrm{Triangularize}\left(\mathrm{sys},R\right)$
 ${\mathrm{lrc}}{≔}\left[{\mathrm{regular_chain}}\right]$ (7)

Its triangular decomposition consists of only one regular chain

 > $\mathrm{rc}≔\mathrm{lrc}\left[1\right]$
 ${\mathrm{rc}}{≔}{\mathrm{regular_chain}}$ (8)
 > $\mathrm{Equations}\left(\mathrm{rc},R\right)$
 $\left[\left({{z}}^{{12}}{+}{94127136}{}{{z}}^{{8}}{+}{691135635}{}{{z}}^{{7}}{+}{676458799}{}{{z}}^{{4}}{+}{195425386}{}{{z}}^{{3}}{+}{326553470}{}{{z}}^{{2}}{+}{574327669}\right){}{x}{+}{27352854}{}{{z}}^{{13}}{+}{673373922}{}{{z}}^{{9}}{+}{410681381}{}{{z}}^{{8}}{+}{817312291}{}{{z}}^{{5}}{+}{308837227}{}{{z}}^{{4}}{+}{32655347}{}{{z}}^{{3}}{+}{116876413}{}{z}{+}{880926729}{,}\left({{z}}^{{12}}{+}{94127136}{}{{z}}^{{8}}{+}{691135635}{}{{z}}^{{7}}{+}{676458799}{}{{z}}^{{4}}{+}{195425386}{}{{z}}^{{3}}{+}{326553470}{}{{z}}^{{2}}{+}{574327669}\right){}{y}{+}{547057079}{}{{z}}^{{13}}{+}{927802747}{}{{z}}^{{9}}{+}{821042762}{}{{z}}^{{8}}{+}{352188797}{}{{z}}^{{5}}{+}{237219820}{}{{z}}^{{4}}{+}{326553470}{}{{z}}^{{3}}{+}{805850702}{}{z}{+}{386236578}{,}{{z}}^{{20}}{+}{957349886}{}{{z}}^{{16}}{+}{944549889}{}{{z}}^{{15}}{+}{886639826}{}{{z}}^{{12}}{+}{458149889}{}{{z}}^{{11}}{+}{156173647}{}{{z}}^{{10}}{+}{568152312}{}{{z}}^{{8}}{+}{120112423}{}{{z}}^{{7}}{+}{434195336}{}{{z}}^{{6}}{+}{398220483}{}{{z}}^{{5}}{+}{536874419}{}{{z}}^{{4}}{+}{604689895}{}{{z}}^{{3}}{+}{446611758}{}{{z}}^{{2}}{+}{237311560}{}{z}{+}{665813406}\right]$ (9)

The polynomial in x is not normalized

 > $\mathrm{px}≔\mathrm{Polynomial}\left(x,\mathrm{rc},R\right)$
 ${\mathrm{px}}{≔}{x}{}{{z}}^{{12}}{+}{27352854}{}{{z}}^{{13}}{+}{94127136}{}{x}{}{{z}}^{{8}}{+}{673373922}{}{{z}}^{{9}}{+}{691135635}{}{x}{}{{z}}^{{7}}{+}{410681381}{}{{z}}^{{8}}{+}{676458799}{}{x}{}{{z}}^{{4}}{+}{817312291}{}{{z}}^{{5}}{+}{195425386}{}{x}{}{{z}}^{{3}}{+}{308837227}{}{{z}}^{{4}}{+}{326553470}{}{x}{}{{z}}^{{2}}{+}{32655347}{}{{z}}^{{3}}{+}{574327669}{}{x}{+}{116876413}{}{z}{+}{880926729}$ (10)

Indeed its initial is not a constant in R

 > $\mathrm{ipx}≔\mathrm{Initial}\left(\mathrm{px},R\right)$
 ${\mathrm{ipx}}{≔}{{z}}^{{12}}{+}{94127136}{}{{z}}^{{8}}{+}{691135635}{}{{z}}^{{7}}{+}{676458799}{}{{z}}^{{4}}{+}{195425386}{}{{z}}^{{3}}{+}{326553470}{}{{z}}^{{2}}{+}{574327669}$ (11)

We compute the inverse of the initial of px w.r.t. rc Note that the Inverse will not fail if its first argument is not invertible w.r.t. its second one; computations will split if a zero-divisor is met. This explains the non-trivial signature of the Inverse function

 > $\mathrm{linv}≔\mathrm{Inverse}\left(\mathrm{ipx},\mathrm{rc},R\right)$
 ${\mathrm{linv}}{≔}\left[\left[\left[{174020324}{}{{z}}^{{19}}{+}{197335754}{}{{z}}^{{18}}{+}{7625943}{}{{z}}^{{17}}{+}{198840137}{}{{z}}^{{16}}{+}{378204215}{}{{z}}^{{15}}{+}{815531348}{}{{z}}^{{14}}{+}{358244196}{}{{z}}^{{13}}{+}{680868023}{}{{z}}^{{12}}{+}{248247024}{}{{z}}^{{11}}{+}{563170682}{}{{z}}^{{10}}{+}{678017442}{}{{z}}^{{9}}{+}{232546371}{}{{z}}^{{8}}{+}{493675934}{}{{z}}^{{7}}{+}{717866054}{}{{z}}^{{6}}{+}{661798200}{}{{z}}^{{5}}{+}{439140691}{}{{z}}^{{4}}{+}{372603338}{}{{z}}^{{3}}{+}{113779500}{}{{z}}^{{2}}{+}{110488854}{}{z}{+}{493921163}{,}{1}{,}{\mathrm{regular_chain}}\right]\right]{,}\left[\right]\right]$ (12)

We get the inverse the initial of px w.r.t. rc

 > $\mathrm{invipx}≔\mathrm{linv}\left[1\right]\left[1\right]\left[1\right]$
 ${\mathrm{invipx}}{≔}{174020324}{}{{z}}^{{19}}{+}{197335754}{}{{z}}^{{18}}{+}{7625943}{}{{z}}^{{17}}{+}{198840137}{}{{z}}^{{16}}{+}{378204215}{}{{z}}^{{15}}{+}{815531348}{}{{z}}^{{14}}{+}{358244196}{}{{z}}^{{13}}{+}{680868023}{}{{z}}^{{12}}{+}{248247024}{}{{z}}^{{11}}{+}{563170682}{}{{z}}^{{10}}{+}{678017442}{}{{z}}^{{9}}{+}{232546371}{}{{z}}^{{8}}{+}{493675934}{}{{z}}^{{7}}{+}{717866054}{}{{z}}^{{6}}{+}{661798200}{}{{z}}^{{5}}{+}{439140691}{}{{z}}^{{4}}{+}{372603338}{}{{z}}^{{3}}{+}{113779500}{}{{z}}^{{2}}{+}{110488854}{}{z}{+}{493921163}$ (13)

We multiply px by the inverse of its initial and reduce the product w.r.t rc. The returned polynomial is now normalized w.r.t. rc. Note that only the polynomials of rc in y and z are used during this reduction process.

 > $\mathrm{ReduceCoefficientsDim0}\left(\mathrm{invipx}\mathrm{px},\mathrm{rc},R\right)$
 ${703897958}{}{{z}}^{{19}}{+}{637307906}{}{{z}}^{{18}}{+}{745731651}{}{{z}}^{{17}}{+}{21899044}{}{{z}}^{{16}}{+}{658962013}{}{{z}}^{{15}}{+}{899050902}{}{{z}}^{{14}}{+}{77671904}{}{{z}}^{{13}}{+}{921629286}{}{{z}}^{{12}}{+}{870449919}{}{{z}}^{{11}}{+}{122035854}{}{{z}}^{{10}}{+}{791154398}{}{{z}}^{{9}}{+}{547395190}{}{{z}}^{{8}}{+}{624024465}{}{{z}}^{{7}}{+}{710904034}{}{{z}}^{{6}}{+}{4427709}{}{{z}}^{{5}}{+}{954705258}{}{{z}}^{{4}}{+}{221310023}{}{{z}}^{{3}}{+}{584706443}{}{{z}}^{{2}}{+}{x}{+}{332923317}{}{z}{+}{743851316}$ (14)