Euler’s back-door pass to Gauss sinks a bucket

ACC stands for the Atlantic Coast Conference, which is an athletic organization that contains Georgia Tech and fourteen other colleges. In basketball, the top several teams in the ACC qualified for the NCAA championship tournament, which started today. We call the NCAA tournament “March Madness” because the opening rounds have games being shown on national TV seemingly every hour of every day, and often some spectacular upsets happen. Indeed Harvard has just beaten a favored University of Cincinnati team.

Today I want talk about another ACC: our own complexity class.

Recall that ACC, as a complexity class, is the class of Boolean functions computed by boolean circuits of constant depth and polynomial size, and the gates include modular gates that can count the number of ${1}$ inputs modulo a fixed constant. This class is quite mysterious. It could be very powerful, yet we do not even know if it contains the majority function.

Alas the ACC qualifiers for the men’s tournament did not contain Georgia Tech, for our men’s team had a losing record this year. Our women’s team, however, played well enough to receive an at-large entry into the NCAA Women’s championship, which is staggered two days after the men and so begins Saturday. No Buffalo team made either. The tournaments run through April 7 and 8. Go Yellow Jackets.

## The Problem

Suppose you have a number ${a}$. Now I give you an ${n}$-bit prime number ${p}$ and ask that you check whether ${a}$ is a quadratic residue modulo ${p}$. Recall that means that there is a ${b}$ such that

$\displaystyle a \equiv b^{2} \bmod p.$

This is the problem we are interested in solving with an ACC circuit. Note that it is a promise problem—we only ask that your computation works when the input number ${p}$ is a prime.

## An Approach

An obvious idea is to use the famous Euler criterion, which says that ${a}$ is a quadratic residue if and only if

$\displaystyle a^{\frac{p-1}{2}} \equiv 1 \bmod p.$

Thus we need only raise ${a}$ to a power by repeated squaring and so on. The trouble, of course, is that we do not know whether ACC can do the required repeated multiplication.

## Another Approach

Now let’s expressly state that ${a}$ is bounded in size by some constant. Still the Euler approach looks hopeless. But there is a deep theorem of number theory that comes to the rescue: quadratic reciprocity. Define the Legendre symbol

$\displaystyle \left( \frac{a}{p} \right)$

as the value ${ a^{\frac{p-1}{2}} \bmod p}$ where ${p}$ is a prime. Note it is always ${-1,0,+1}$: it is only ${0}$ when ${p}$ divides ${a}$. Thus our problem is to compute

$\displaystyle \left( \frac{a}{p} \right)$

for ${p}$ an input and ${a}$ bounded in size.

This is in ACC. The key is we can use the deep quadratic reciprocity theorem which says that

$\displaystyle \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2}}(-1)^{\frac{q-1}{2}},$

where ${p}$ and ${q}$ are primes. The theorem was conjectured by Leonhard Euler and Adrien-Marie Legendre, but finally proved by Carl Gauss. He referred to it as “the fundamental theorem” and wrote:

The fundamental theorem must certainly be regarded as one of the most elegant of its type.

So how do we proceed? Suppose first that the constant ${a}$ is a prime. Then we know by reciprocity that

$\displaystyle \left( \frac{a}{p} \right) \left( \frac{p}{a} \right) = (-1)^{\frac{a-1}{2}}(-1)^{\frac{p-1}{2}}.$

The right-hand side is easy to compute in ACC. To determine it we need only compute ${p}$‘s residue modulo ${4}$. Since ${p}$ is given in binary this is trivial. Thus, all reduces to the computation of ${\left( \frac{p}{a} \right)}$. The key is that the Legendre symbol only depends on the value of ${p}$ modulo ${a}$. Since we can do this in ACC we are done for the case when ${a}$ is a prime.

When ${a}$ is composite we use one simple fact about the Legendre symbol that follows directly from its definition.

$\displaystyle \left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right).$

Thus we can use the case where ${a}$ is prime multiple times.

## Open Problems

The Legendre symbol for bounded ${a}$ is thus in ACC—the complexity class, not the conference. The rationale for this discussion is two-fold. One it shows that obvious approaches to a problem may sometimes be avoided by deep mathematics. Is this possible to do the same for other problems that we care about? The permanent, for example? Another rationale is the perennially important open problem: what can ACC actually compute? It may be hard to resolve the majority function, but perhaps other functions can be shown to be in ACC. Good luck thinking about this.

1. March 20, 2014 5:24 pm

If a is composite, should factorization of a be given or is factoring a in ACC?

March 20, 2014 5:37 pm

$a$ is a constant, so factoring it is free.

• March 21, 2014 12:22 am

In the proof given, it was a constant, but in the first problem posed, it was not, so J’s question makes sense.

• March 25, 2014 9:40 am

In the original problem a is not a constant and the case of a prime is only given. So is there a way to find Legendre symbol for composite a in ACC assuming Legendre symbol for prime a is in ACC?

March 20, 2014 5:35 pm

This is very nice. But the fact that computing $p \mod a$ is in ACC when $p$ is given in binary and $a$ is a constant requires an argument (right?). First look at powers of two: the quantity $2^i \mod a$ depends only on $i \mod a$, but the important point is that there are at most $\log_2 p$ (= length of the input) relevant $i$’s to consider: the bit positions of $p$. Thus we can hardwire all those and add the ones selected by the binary representation of $p$ with one $\mod a$ gate.

3. March 20, 2014 6:11 pm

not an expert on this so am wondering, is this a new result or did someone already prove this? what do you think is a great ref on ACC? it seems very striking that majority is not known to be inside or outside ACC. any further discussion/survey of that in a paper etc?

March 23, 2014 8:02 pm

vznvzn

I am not sure. Also there are many nice structural theorems on ACC. I can look them up later. But not much on what cannot be done. There are weak results on restricted subfamilies of ACC.

4. March 21, 2014 4:08 am

I agree. It seems that ACC and majority function is beyond paywall, Can you give a link to oen access review related to topic. Thanks.