Skip to content

The More Variables, the Better?

April 16, 2014


Ideas from algebraic geometry and arithmetic complexity

BassBeret

Hyman Bass is a professor of both mathematics and mathematics education at the University of Michigan, after a long and storied career at Columbia University. He was one of the first generation of mathematicians to investigate K-theory, and gave what is now the recognized definition of the first generation of K-groups, that is {K_1(R)} for a ring {R}. He co-founded with Jean-Pierre Serre a theory of graphs of groups, that is mappings associating a group to each vertex and edge of a graph. He is a past President of the American Mathematical Society—and exemplifies the idea that the AMS promotes mathematics at all levels: since 1996 he has worked on on elementary school math education with his Michigan colleague Deborah Ball.

Today Ken and I wish to discuss an idea used in a paper on the Jacobian Conjecture by Bass with Edwin Connell and David Wright.

One of the most powerful methods we use in theory is often the reduction of the dimension of a problem. The famous JL theorem and its relatives show us that often problems in high-dimensional Euclidean spaces can be reduced to much lower dimensional problems, with little error. This method can and has been used in many areas of theory to solve a variety of problems.

The idea used by Bass and many others is the opposite. Now we are interested in lifting a problem from a space to a much higher space. The critical intuition is that by moving your problem to a higher space there is more “room” to navigate, and this extra “space” allows operations to be performed that would not have been possible in the original lower-dimensional space. An easily quoted example is that the Poincaré property was proved relatively easily for spaces of dimension {d = 5} and higher, then for {d=4} in the 1980’s, and finally for {d=3} by Grigory Perelman drawing on Richard Hamilton.

Adding Variables

Let {F(x)} be a polynomial map from {\mathbb{Z}^{n}} to {\mathbb{Z}^{n}} where

\displaystyle  x = x_{1},\dots,x_{n}.

The Jacobian Conjecture (JC), which we have covered several times before, indeed recently, studies when such maps are injective. The trouble with the JC is quite simply that such maps can be very complex in their structure, which explains the reason JC remains open after over 70 years.

A very simple idea, almost trivial idea, is to replace {F(x)} by {G(x,y)} which is defined by

\displaystyle  G(x,y) = (F(x),y),

for new variables {y=y_{1},\dots,y_{m}}. For example if {F(x) = (x_{1},x_{1}+x_{2}^{7})} then {G} could be

\displaystyle  (x_{1},x_{1}+x_{2}^{7},y_{1},y_{2},y_{3}).

The new variables {y} are used in a “trivial” way. One reason the method is useful for the JC conjecture is that {F} is injective if and only if {G} is injective. This is trivial: the new variables do not interact in any manner with the original variables, and so the map {G} is injective precisely when {F} is.

Why is this of any use? Clearly {G} is really just {F} with an identity function on the variables {y} “tacked on” to it. How can this help?

Using The Extra Variables

The answer is that we can use the extra variables to modify the polynomial {G} so that it looks very different from {F}. Suppose that we replace {G} by {H = A \circ G} where {A} is a nice polynomial map. We may be able to vastly change the structure of {G} and get a {H} that is much simpler on some measure. The hope is that this restructuring will allow us to prove something about {H} that then implies something about {G}. This is exactly what happens in the study of the JC conjecture.

Here is a famous result from the Bass-Connell-Wright paper:

Theorem 1 Given {F(x)} there is an automorphism {A} so that {H=A \circ G} has degree at most three. Moreover {F} is injective if and only if {H} is.

This allows the JC question to be reduced to the study of cubic maps. Of course such low degree maps still are complex in their behavior, but the hope is that while they are on many more variables the restrict on their degree many make their structure easier to understand. This has yet to be fruitful—the JC remains open. The following quotation from the paper explains the idea:

Kquote

General Use In Theory?

One idea is to try and use this stabilization philosophy to attack problems about polynomials that arise in complexity theory. For example can we use the addition of extra variables to attack the power of polynomial modulo composite numbers? Suppose that {F(x)} is a polynomial of many variables that modulo {pq} computes something interesting. What if we add extra variables as above, then rearrange the resulting polynomial to have a “better” structure? We must preserve not its injectivity, but for us its ability to compute something. If we can do this, then perhaps we can use the use the extra variables to obtain a lower bound.

Two simple examples from arithmetical complexity are aliasing variables in a formula to make it read-once, and the Derivative Lemma proved by Walter Baur and Volker Strassen. In the latter, the idea is to take a certain gate {g} of a circuit {C} computing a function {f}, and regard it as a new variable {x_{n+1}} in a circuit {C'}. The circuit {C'} computes a function {f'} of {n+1} variables such that

\displaystyle  f(x_1,\dots,x_n) = f'(x_1,\dots,x_n,g(x)).

In the Derivative Lemma the gate {g} is chosen to involve one-or-two input variables {x_i}, but the idea can be extended to other cases. When the construction is applied recursively we generate circuits {C'',C^{(3)},C^{(4)},\dots} in which the number of variables becomes higher and higher, but the circuits themselves become flatter and flatter, until only a “stardust” of many single-variable functions is left.

Open Problems

Are there general rules of thumb on when you should increase versus decrease the dimension? Or when to induct on the output gate(s) of a circuit, on the number of variables going down, or on the number of variables going up?

5 Comments leave one →
  1. April 17, 2014 1:39 am

    One example is extended formulations of polytopes. Sometimes optimizing over a complicated polytope Q can be done efficiently if one finds a higher dimensional polytope R that has few facets, but projects down to Q. Examples of such polytopes are the spanning tree polytope, or the permutahedron.

  2. April 17, 2014 8:36 am

    This brings up once again the problem of finding the proper form of derivatives (differentials, Jacobians, tangent functors, Taylor series, etc.) in Boolean spaces. A few wools of bit along these lines are gathered in this bag:

    Differential Logic and Dynamic Systems

  3. maybe wrong permalink
    April 17, 2014 12:48 pm

    Increasing variables could help in the study of random processes-processes that are highly memory dependent and non-Markovian could potentially be simplified by increasing dimensionality.

  4. Mike R permalink
    April 17, 2014 2:41 pm

    A similar idea is used in cryptography. Take a function f(x) and define a function F(x;r), where r denotes some extra variables. Then F is a *randomized encoding* of f if (1) you can efficiently “decode” f(x) from F(x,r) for any r, and (2) the distribution F(x,r) induced by random choice of r can be simulated given only f(x) — so this distribution carries no more information than f(x).

    Then F inherits many of the cryptographic properties of f (for example, if f is one-way, then so is F; if f is pseudorandom, then so is F). But F can have much lower computational complexity. So often it suffices to just design something that works for a low complexity class, then via randomized encodings you get some higher classes for free. For example, every poly-size circuit has a (computationally secure) randomized encoding with constant depth.

    There is a nice series of papers by Benny Applebaum, Yuval Ishai & Eyal Kushilevitz that develops randomized encoding and gives some very interesting applications.

  5. May 1, 2014 5:19 am

    IMHO similar approach we can see in graph theory. To represent a graph we need adjacency list only, but adjacency matrix is more useful for many algorithms and more over distance matrix may be much more useful. I.e. very often redundant representation is very helpful.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s