Skip to content

How To Make A Polynomial Map Nicer

June 12, 2019
tags: , , , , ,


Stability theory and polynomials

[ Essen ]

Arno van den Essen is the author of the book on the Jacobian Conjecture.

Today I want to highlight one of the ideas he presents in his book.

The theory is sometimes called stabilization methods. Or K-theory methods. It is often used in connection with the famous Jacobian conjecture (JC). I will not say any more about JC now—see this for some comments we made a while ago.

The Stability Philosophy

Essen states that the philosophy of stability theory is:

It is possible to change a map {F: \mathbb{K}^{n} \rightarrow \mathbb{K}^{n}} and make it “nicer” provided we allow {n} to be increased.{^{\dagger}}

\rule{0.4\textwidth}{0.4pt}

{(\dagger)} Not a direct quote.

That is provided we can change {F} to

\displaystyle \tilde{F} : \mathbb{K}^{N} \rightarrow \mathbb{K}^{N}

where {N} is larger than {n}. The whole method is based on a simple observation. Suppose that {F: \mathbb{K}^{n} \rightarrow \mathbb{K}^{n}} and define {G} by

\displaystyle G(x_{1},\dots,x_{n},u_{1},\dots,u_{N-n}) = (F(x_{1},\dots,x_{n}), u_{1},\dots,u_{N-n}).

Then {F} is injective if and only if {G} is injective. This is trivial—really trivial. From trivial observations sometimes important methods are created.

I will now explain how why this is useful by presenting an example.

The Method: By Example

Suppose that

\displaystyle F: \mathbb{K}^{2} \rightarrow \mathbb{K}^{2}

is a polynomial mapping where

\displaystyle F(x,y) = (f(x,y),g(x,y)).

We wish to show that we can replace {F} by another polynomial map {\tilde F} that has degree at most {3}. Moreover, the new polynomial map is injective if and only if the original polynomial map is injective. The method can be used to preserve other properties of the polynomial mapping, but being injective is a important example.

There seems to be no way to lower the degree of {F} without destroying its structure. But if we use the stability philosophy and allow extra dimensions we can succeed. That is we replace {F(x,y)} by the function

\displaystyle \tilde{F}(x,y,u,v) = (f(x,y),g(x,y),u,v).

Why does this work? The idea is that the extra two dimensions can be used as extra registers. These registers can be used to simplify the computation, and reduce the degree of {F}.

Let {f(x,y)} have one term that we wish to remove. To be concrete, let’s assume the term is

\displaystyle x^{3}y.

Start with the input

\displaystyle (x,y,u,v).

Now change this to

\displaystyle (x,y,u+P,v+Q),

where

\displaystyle P=x^{2} \text{ and } Q=xy.

This is an invertible transformation. Note this is only possible because we have two extra dimensions or registers. Otherwise, we could not compute {P} and {Q} without messing up the rest of the computation. Now map this to

\displaystyle (f(x,y),g(x,y),u+P,v+Q).

This is nothing more than computing the original function and ignoring the new registers.

The next step is to go to

\displaystyle (f-(u+P)(v+Q),g,u+Pv+Q).

The last point is that

\displaystyle f- (u+P)(v+Q),

cancels the term {x^{3}y} we wished to remove.

\displaystyle f- PQ -uQ -vP-uv = f-x^{2}xy -uxy - vx^{2}-uv.

The price we pay is that new terms have been added, but they have at most degree {3}.

The Method: General Case

We can prove by induction the following general theorem:

Theorem 1 Suppose {F: \mathbb{K}^{n} \rightarrow \mathbb{K}^{n}} is polynomial map where {K} is a field. Then we can construct a polynomial map of degree at most {3} denoted by {\tilde F} so that it is injective precisely when {F} is injective.

Even stronger theorems are possible. For example, the polynomial map {\tilde F} can be required to be cubic linear:

Definition 2 Suppose that {A} is in {n \times n} matrix over the field {\mathbb{K}}. The {F_{A}(X)} is the cubic linear map for the matrix {A} is defined to be the map {F_{A}: \mathbb{K}^{n} \rightarrow \mathbb{K}^{n}}

\displaystyle X \rightarrow X + (AX)^{*3},

where {Y^{*3}} is defined to be the vector {Z} so that {Z_{k} = Y_{k}^{3}} for all coordinates {k}.

See Essen’s book for more details. Note a cubic linear map when {n=2} is of the form:

\displaystyle ( x + ( ax + by)^{3}, y + (cx + dy)^{3} )

where {a,b,c,d} are constants. This reduction to cubic linear maps is quite pretty, and requires a clever application of the stabilization method.

A Limit of The Method

The reduction in degree is possible only to degree {3}. It cannot be reduced to degree {2} in general. Let’s look at the intuition why this is true. The last step is

\displaystyle f- (u+P)(v+Q)

which is

\displaystyle f- PQ -uQ -vP.

Suppose {f} has a leading term of degree {d}. Also suppose that {P} has degree {d_{P}} and {Q} has degree {d_{Q}}. Then

\displaystyle d = d_{P} + d_{Q}

since the leading term goes away. But {uQ} and {vP} have degrees {d_{P}+1} and {d_{Q}+1} respectively. So to keep {d_{P}+1} and {d_{Q}+1} both {2} or less, it follows that {d} can be at most {2}. However, in this case a term of degree {2} is removed and other terms of degree {2} are added. This is not a formal proof that the method cannot reduce the degree to {2}. I do believe that formalized properly it is a theorem that reduction to degree {2} is in general impossible.

Open Problems

I like this technology. I wonder if it might be possible to use it on some of our favorite problems. I do like that it conserves invertibility. This seems like it could be related to quantum computing, because of the reversible nature of quantum computing.

from → History, Ideas, Proofs
5 Comments leave one →
  1. domotorp permalink
    June 12, 2019 3:58 pm

    At one place ‘u+Pv+Q’ misses a comma.

    Reply
  2. eppstein permalink
    June 12, 2019 8:39 pm

    This seems very reminiscent of the lifting transformation in computational geometry, e.g. as used to turn 2D circles into 3D planes (and correspondingly Delaunay triangulations into convex hulls etc).

    Reply
    • rjlipton permalink*
      June 14, 2019 11:06 am

      Dear eppstein:

      Great insight. Do you have some good links we can put here? I looked but not sure the right ones.

      Best

      Dick

      Reply
  3. Peter Gerdes permalink
    June 12, 2019 10:15 pm

    Seems like you might want to mention that the goal is to *uniformly* construct \widetilde{F} since otherwise one trivially just asks if F is injective or has whatever property is being asked about and picks \widetilde{F} appropriately.

    As an aside given some computably presented field K with computable equality is function determining if a polynomial in n variables has a root in K also computable?

    Ok, maybe this is besides the point of the neat trick you presented as one is probably interested in all sorts of properties not just injectivity but I can’t help but wondering.

    Reply
    • rjlipton permalink*
      June 13, 2019 11:14 am

      Dear Peter Gerdes:

      You ask good questions. Of course the point is that the map from F to the nicer F’ is only a function of the polynomial’s terms. This is critical as you point out. The next question about fields is nice. I believe the usual assumption is stronger: The assumption is usually that one can determine more. Like tell if any two expressions of “constants” are equal or not.

      Thanks again.

      Dick

      Reply

Leave a Reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading