More on the crypto approach to the Jacobian Conjecture

Arno van Essen is one of the world experts on the Jacobian conjecture (JC)—we have discussed his work before here. He has made many contributions to it, with my favorite being: To Believe Or Not To Believe: The Jacobian Conjecture. I like his attitude about conjectures: I think we should be more skeptical about our own. Oh well, few of my colleagues feel this way about ${\mathsf{P \neq NP}}$, for example.

Today I want to update a previous discussion on the JC, and prove a new theorem.

It does not solve JC, but has two nice properties. It shows that we can improve what we discussed before. Our previous, almost trivial observation, can be made into a a full-blown theorem. We can show that a class of polynomial maps, called ${D}$-maps, are injective. This is an improvement over what was previously known.

Also the same ideas can be used to prove a new statement equivalent to JC. This statement seems like it must be true, must be provable, but since it is equivalent to JC it will certainly not be trivial. This is joint work with Essen, and we are writing up a paper that will be available for discussion soon.

${D}$-Maps

I noticed before that a certain important class of maps, called ${D}$-maps “leak” some information—just more than a bit per variable. This was a fun, trivial observation. Yet with some modest additional insights I realized recently that such maps leak all their information: given the value of the map, there is exactly one pre-image.

In order to state the theorem I need the notion of a ${D}$-map. They are cubic maps of a special form.

Definition: Let ${A = (a_{ij})}$ be an ${n}$ by ${n}$ integer matrix such that ${A^{2}=0}$. Define the polynomial function ${F}$ from ${\mathbb{Z}^{n}}$ to ${\mathbb{Z}^{n}}$ by ${F(x_{1},\dots,x_{n})=(y_{1},\dots,y_{n})}$ where each ${y_{i}}$ is of the form

$\displaystyle x_{i} + (a_{i1}x_{1} + \cdots + a_{in}x_{n})^{3}.$

These are named ${D}$-maps after Ludwik Drużkowski. We will write this as ${F(X)=X + (AX)^{*3}}$. The mappings themselves can be defined without the condition ${A^2= 0}$, but this condition seems to be quite useful.

These maps are interesting since the JC is equivalent to the statement that all such maps over the complex numbers are injective, provided as usual their Jacobians are non-zero constants.

Here are two recent papers by Dan Yan and Michiel de Bondt involving them.

Integer D-maps Are Invertible

Theorem: Let ${A}$ be an ${n}$ by ${n}$ integer matrix and let ${F(X) = X + (AX)^{*3}}$ be a ${D}$-map such that ${A^{2}=0}$. Then ${F:\mathbb{Z}^{n} \rightarrow \mathbb{Z}^{n}}$ is injective.

Namely, let ${y \in F(\mathbb{Z}^{n})}$. We will show that all pre-images of ${y}$ (in ${\mathbb{Z}^{n}}$) are equivalent modulo ${3}$ and from that we deduce that they are equivalent modulo ${3^{k}}$ for all ${k \ge 1}$. This implies that ${y}$ has only one pre-image: for if ${F(x)=F(x')=y}$ and ${x-x' \neq 0}$,then for some ${k\ge 1}$, ${3^{k}}$ does not divide ${x-x'},$ i.e. ${x}$ is not equivalent ${x'}$ modulo ${3^{k}}$, a contradiction.

The following proof is a simplification due to Arno of a draft of mine.

Lemma 1: All pre-images of ${y}$ are equivalent mod ${3}$.

Proof: Let ${F(x)=y}$. Then ${y=(Ax)^{*3} \equiv x + (Ax) (mod \ 3)}$. So ${y \equiv (I +A)x (mod \ 3)}$. Multiplying by ${I-A}$, using ${A^{2}=0}$, we get that ${x \equiv (I-A)y (mod \ 3)}$. $\Box$

Lemma 1 is essentially the “trivial” observation that I made before.

Lemma: Let ${k \ge 1}$. Then all pre-images of ${y}$ are equivalent mod ${3^{k}}$.

Proof: We use induction on ${k}$, the case ${k=1}$ is Lemma 1. So let ${k \ge 1}$ and let ${F(x)=y}$. Write ${x = 3^{k}w + r}$, with ${0 \le r_{i} < 3^{k}}$, for all ${i}$. Then by the induction hypothesis ${r}$ is independent of ${x}$. Let ${a_{i}}$ be the ${i}$-th row of ${A}$. Then ${y_{i} = x_{i} + \langle a_{i},x \rangle^{3}}$, where ${\langle,\rangle}$ denotes the usual inner product. Now substitute ${x=3^{k}w +r}$ into this equation. This gives

$\displaystyle y_{i}= x_{i} + \langle 3^{k} a_{i},w \rangle + \langle a_{i},r \rangle \equiv x_{i} + \langle a_{i},r \rangle^{3} (mod \ 3^{k+1}).$

Since ${r}$ does not depend on ${x}$ this gives the desired result. $\Box$

Open Problems

This is close to solving the JC. Here “close” means that we need to do the above for maps that have coefficients that can be rational. Currently, the arithmetic arguments do not quite work: the problem is potential factors of ${3}$ in denominators of the entries of the matrix ${A}$. Can this be overcome by a more careful analysis?

[fixed error]

February 6, 2014 11:46 am

I would like to point out that your statement:

“the JC is equivalent to the statement that all such maps over the complex numbers are injective”

is not correct. The reason is that there exist nilpotent matrices A for which the determinant of the Jacobian of the corresponding D-maps are not constant, hence the D-maps are not injective. For example, we can take A to be the matrix whose rows are [1, 1/5, -2/5], [1, 1/5, -2/5],[3, 3/5, -6/5] (in that order). One can check that A^2=0, but the corresponding D-map is not injective over real numbers (though injective over rational numbers).

February 8, 2014 1:20 pm

Shuhong Gao

Thanks for pointing out our error in the comment after the definition of D-maps. It was an error. I will fix it in the text. Of course we should have said that it suffices to look at D-maps with usual Jacobian restriction and with added that $A^2=0$.

Thanks again