Arithmetic Complexity and Symmetry

Understanding the arithmetic complexity of symmetric polynomials is enough

Isaac Newton is of course Sir Isaac Newton. He did many many wonderful things, including proving some basic results about symmetric polynomials.

Today, I want to talk about the arithmetic complexity of polynomials. There is a folklore principle that the study of arithmetic complexity of polynomials can be reduced to the study of symmetric polynomials. I will show that this is almost true, and explain some of its consequences.

Since Isaac Newton was born in 1643, I have few–actually no–personal stories about him. However, I think that reading about his life is very enlightening. His life blends theory and practice in ways that almost no one does today. Who today could invent a whole branch of mathematics, calculus, yet also invent a new type of telescope? I think that we need more scientists today that can blend theory and practice, often theorists and practitioners are on completely separate wavelengths.

This was brought out clearly in the recent NSF workshop–especially the discussion of SAT. The design automation experts kept saying, but SAT is easy.

I am not suggesting that one can be a Newton. Some have argued that he had the greatest mind, ever. Ahead of Albert Einstein, for example. I am suggesting that we can profit from reading about him, and understanding his approach to the great problems of his day. There are a large number of readable books on his life. My suggestion is to pick one up for reading at the “beach” or whenever you have time this summer.

I cannot resist giving two examples from his life, based on various books I have read about him–here is one. Perhaps the most famous quote of Newton is:

“If I have seen further than others, it is by standing upon the shoulders of giants.”

The usual interpretation of this quote is that Newton is thanking those that came before him, and actually humbly thanking them. That is the classic view of this famous quote. However, there is a strong argument that he was actually making fun of his arch enemy Robert Hooke–who was a famous scientist in his own right. Newton was involved in a number of bitter disputes in his life over who knew what when, as we say today. His feud with Hooke lasted for years, was over the creation of the theory of gravity, and only ended when Hooke died. Hooke was short, not a “giant.”

Newton was famous, also, for being a terrible lecturer. As part of the rules of his Lucasian chair he had to give periodic lectures. After his first lecture, which was sparsely attended, no one came again. Ever.

“Not a single student showed up for Newton’s second lecture, and throughout almost every lecture for the next seventeen years Newton talked to an empty room, listening merely to his own voice bouncing back at him.”

Let’s turn now to study some basic properties of symmetric polynomials and their arithmetic complexity.

Elementary Symmetric Polynomials

Suppose that is the polynomial:

Then, after expanding the polynomial. The mapping from to defines in a natural way the elementary symmetric function. For example,

and

This way of looking at the elementary functions has two advantages. First, it shows that they are easy to compute. Second, it also shows that they are not too hard to “invert.” More, on inversion in a moment. For now it should be clear that they are easy to compute: If are given, then to compute the values of all the elementary functions, just form the polynomial

and expand. This clearly takes at most polynomial time.

Arithmetic Complexity and Symmetric Polynomials

Let . Suppose that is a polynomial–for us the coefficients will always be integers. The arithmetic complexity is the length of shortest straight-line computation that computes . Denote this as . Define . Note, is always a symmetric function.

Lemma: For any , .

The proof of this is very simple: the key is that the elementary functions are easy to compute, as I have already pointed out.

We would like the opposite to be true: . If this were true, then

would follow. This would mean that when trying to prove lower bounds on an arbitrary polynomial, one could replace that polynomial by a related symmetric one. Then, the complexity of the original and the symmetric polynomials would almost be the same. I do not know if this is true, but the following approximation to it is:

Theorem: Suppose that is a polynomial where . Then, there is an algorithm that computes within in time

The algorithm is not a circuit. The algorithm needs to perform branching operations, for example. The algorithm does not “cheat” in any sense, but it is not an arithmetic circuit. The point, however, is for lower bounds we can restrict our attention to symmetric polynomials, if we are happy with exponentially close answers.

Note, the extra term has gone from to . The extra dependencies are really not unreasonable. For example, the fact that the algorithm’s running time depends on the number of bits of the input is expected.

The Algorithm

Suppose that we can compute in steps, for any . Then, we must show how to compute in plus steps. Let be a given input, and we must show how to compute .

I will just outline the main idea, which is really quite simple. Suppose that we could find a so that for all . Then,

by definition of . Thus, the cost of evaluating is reduced to the cost of evaluating and cost of finding the .

But, finding can be reduced to finding the roots of a univariate polynomial. This is the “inversion step.” Consider the polynomial equation,

Call the roots . Then, by the definition of the elementary symmetric functions, if we set , we are done.

Therefore, the algorithm for evaluating operates as follows. It solves the equation (2) to high precision using any of the well known root finding algorithms–see for example Victor Pan’s survey paper. The running time of the root finder is polynomial in the values , , and . Then, the algorithm uses (1) to get the approximate value of to high precision.

Note, if , then the algorithm can get the exact value of by rounding.

Applications

If you wish to prove a lower bound on the permanent of an by matrix, then you can convert it into a symmetric function. Can being symmetric make the lower bound easier to prove? Another consequence is that it shows that determining the arithmetic complexity of a symmetric polynomial is as hard to determine as the complexity of an arbitrary polynomial.

Open Problems

For the boolean case the “equivalence” between general functions and symmetric is clearly false. The proof of the theorem fails because the Galois field on two elements is too small, which means the univariate polynomial will not always have a solution in the field. An obvious question is what happens if we allow the field to be finite, but let it be large enough that the required roots exist?

Note, it is reasonable that the theorem fails in the boolean case. In this case the value of a symmetric boolean function only depends on the weight of the input, i.e. the number of ‘s. Thus, all symmetric boolean functions are easy to compute. If the theorem were true, then all boolean functions would be easy, which is of course false.

Another question is can we make the algorithm into a circuit? Or must we leave the domain of circuits to get the theorem?