Question

Let \(D\) be a ring (commutative, with 1 ) and \(f, g \in D[x]\) monic of degree \(n>0\). (i) Prove that rev \((f g)^{-1}\) rem \(x^{2 n}\) can be computed from rev \((f)^{-1} \operatorname{rem} x^{n}\), rev \((g)^{-1}\) rem \(x^{n}\), and \(f g\) using \(2 \mathrm{M}(n)+\mathrm{M}(2 n)+O(n)\) arithmetic operations in \(D\). (ii) Prove that rev \((f)^{-1}\) rem \(x^{n}\) can be computed from rev \((f g)^{-1}\) rem \(x^{2 n}\) using \(M(n)+O(n)\) operations in \(D\).

Short answer

(i) Requires \(2\mathrm{M}(n)+\mathrm{M}(2n)+O(n)\) operations; (ii) Uses \(M(n)+O(n)\) operations.

Step-by-step solution

Understanding Reverse Polynomials and Definitions

To solve the problem, first recall that for a polynomial \( p(x) = a_0 + a_1x + ... + a_nx^n \) in \(D[x]\), the reverse polynomial, \( \text{rev}(p) \), is \( a_n + a_{n-1}x + ... + a_0x^n \). The inverse of a polynomial \( f(x) \) is the polynomial \( h(x) \) such that \( f(x)h(x) \equiv 1 \mod x^k \), where \( k \) is the degree or a suitable power of \( k \). We're interested in computing terms involving reverse and inverse of polynomials modulo certain powers of \(x\).

Decomposing the First Part (i) of the Problem

To compute \( \text{rev}((fg)^{-1}) \text{ rem } x^{2n} \) using \( \text{rev}(f)^{-1} \text{ rem } x^n \), \( \text{rev}(g)^{-1} \text{ rem } x^n \), and \( fg \), follow these steps:1. Compute the reverse polynomials \( \text{rev}(f) \) and \( \text{rev}(g) \).2. Compute their inverses modulo \( x^n \).3. Use these inverses to compute \( \text{rev}(f)^{-1} \cdot \text{rev}(g)^{-1} \equiv (fg)^{-1} \mod x^{2n} \). This step involves multiplying and reducing modulo \( x^{2n} \), which by Fast Fourier Transform (FFT) multiplication takes \( \mathrm{M}(2n) \) operations.

Adding Operations Count to First Part

Knowing that FFT multiplies two polynomials of degree \( n \) in \( O(n \log n) \) operations, the cost of each multiply step for degree \( 2n \) is \( \mathrm{M}(2n) \). Thus, the total arithmetic operations are \( 2\mathrm{M}(n) + \mathrm{M}(2n) + O(n) \).

Solving the Second Part (ii) of the Problem

To compute \( \text{rev}(f)^{-1} \text{ rem } x^n \) from \( \text{rev}((fg)^{-1}) \text{ rem } x^{2n} \), do the following:1. Find \( h(x) = \text{rev}((fg)^{-1}) \equiv 1 \mod x^{2n} \).2. Express this as \( h(x) \equiv \text{rev}(f)^{-1} \cdot \text{rev}(g)^{-1} \mod x^{2n} \).3. Extract \( \text{rev}(f)^{-1} \text{ rem } x^n \) from above using division. This involves \( \mathrm{M}(n) \) operations for calculating remainders and reductions.

Conclude Operations Count for Second Part

The operation \( \mathrm{M}(n) + O(n) \) accounts for the reduction and division operations for polynomials of degree at most \( n \). Here, \( \mathrm{M}(n) \) takes care of needed multiplications and other arithmetic steps, while \( O(n) \) serves for additional reductions of lower degree remainders.

Key concepts

Reverse Polynomial

In polynomial algebra, the reverse polynomial involves rearranging the terms of a given polynomial in descending order of power. If you have a polynomial \( p(x) = a_0 + a_1x + a_2x^2 + \, ... \, + a_nx^n \), its reverse polynomial, denoted as \( \text{rev}(p) \), is expressed as \( a_n + a_{n-1}x + \, ... \, + a_0x^n \). This concept is critical when dealing with polynomial inversion or when performing operations that involve reversing the orientation of terms.

• This reversal technique is particularly useful in simplifying complex polynomial equations when combined with inversion.
• The reverse polynomial provides a structured form that may enhance certain computational processes, such as multiplication or division, because it aligns with the degree of the polynomial.

Understanding the reverse polynomial is essential as it lays the groundwork for performing more complex arithmetic operations on polynomials in a polynomial ring, and is often the first step in processes like polynomial division.

Polynomial Division

Polynomial division, much like numeric division, is about determining how many times one polynomial can be subtracted from another. It's an operation used extensively in polynomial algebra, especially for finding remainders or simplifying expressions. The process of polynomial division results in a quotient and possibly a remainder, similar to integer division.

• Start by aligning the highest power of the divisor with the highest power of the dividend.
• Subtract the resulting product from the original polynomial, recalculating the new polynomial.
• Repeat these steps until the remainder is either zero or of a lower degree than the divisor.

In the context of reverse polynomials, the computation of inverses involves polynomial division because you seek a polynomial that divides a given one to yield a component that effectively inverts another polynomial.
This is typically done modulo some power of \(x\) as given in the task. Therefore, efficiency in polynomial division underlies many polynomial algorithms, often benefiting from techniques like Fast Fourier Transform (FFT) to speed up calculations.

Arithmetic Operations

Arithmetic operations in the polynomial ring \(D[x]\) include addition, subtraction, multiplication, and division, each operating within the rules of arithmetic tailored to polynomials. These are fundamental to all polynomial algebraic manipulations and underpin advanced operations such as inversion and finding remainders.

• Addition/Subtraction: This involves like terms of polynomials being either added or subtracted.
• Multiplication: Distributes each term in one polynomial against each term in another, accumulating results accordingly.
• Division: Used to ascertain the quotient and remainder when one polynomial is divided by another.

In the problem discussed, operation counts for tasks like multiplying two polynomials are denoted by \(\text{M}(n)\) and \(\text{M}(2n)\). The complexity arises in terms of both input size and computational techniques applied, such as FFT, to improve efficiency. Hence, managing these operations efficiently is vital for computing polynomial results in minimal time.

Monic Polynomial

A monic polynomial is a polynomial where the leading coefficient is equal to one. That is, for a polynomial \( f(x) = a_nx^n + \, ... \, + a_0 \), it is monic if \( a_n = 1 \). This simpler form can immensely facilitate polynomial manipulations in mathematic problems by reducing additional complexities associated with leading coefficients.

• Monic polynomials make certain algebraic processes more straightforward, such as finding the inverse modulo some power of \( x \).
• The standardization of leading coefficient aids in computational consistency across various algorithms.

In this exercise, understanding the properties of monic polynomials is key since the division and inversion processes assume these conditions.
By focusing on monic polynomials, it becomes easier to apply certain theorems and formulas, thereby simplifying otherwise complicated procedures in polynomial computations.