3
$\begingroup$

$f(x_1,x_2,\ldots x_n)$ is polynomial with integer coefficients. $f$ is rather large to be computed explicitly, but an algorithm can compute it efficiently at integers and complex number and "lazy" form using parenthesis. The degree of $f$ is $n$. Let $C$ be the coefficient of the monomial $\prod_{i=1}^n x_i$.

Q1: What is the complexity of deciding if $C$ is zero or not?

Q2: What is the complexity of computing $C$?

Can we do better than $\exp(o(n())$ (small oh)?

Possible approaches:

  • Find some domain $K$ with many nilpotent elements and work over $K[x_1,x_2,\ldots x_n]/(x_1^2,x_2^2 \ldots x_n^2)$
  • Using Automatic differentiation compute the partial derivative.
$\endgroup$
  • 1
    $\begingroup$ The Alon-Tarsi conjecture is of this flavour (compute the coefficient of \prod_{i,j=1}^n x_{i,j} in \det((x_{i,j}))^n), just by the way. $\endgroup$ – alpoge Apr 15 at 12:37
3
$\begingroup$

Since the degree of $f$ is $n$, the monomial $x_1x_2\dots x_n$ is the only one containing every variable. Then by inclusion-exclusion, we have $$C = \sum_{v\in\{0,1\}^n} (-1)^{n-s(v)} f(v),$$ where $s(v):=\sum_{i=1}^n v_i$.

$\endgroup$
  • 1
    $\begingroup$ Thanks. Your solution is of complexity 2^n, is this optimal? $\endgroup$ – joro Apr 14 at 17:28
  • $\begingroup$ It may be the case, but I have no instant proof. $\endgroup$ – Max Alekseyev Apr 14 at 18:32
  • 1
    $\begingroup$ Here is my try at an instant proof that it takes $2^n$ evaluations, at least if they are all for variables taken from $\{0,1\}.$ I tell you in advance that $f$ is a product of $n$ terms with the $i$th either $x_i$ or $1-x_i.$ Then the coefficient we want is either $1$ or $-1.$ Of the $2^n$ possible evaluations we can do, all return $0$ except one returns $1.$ $\endgroup$ – Aaron Meyerowitz Apr 14 at 22:19
2
$\begingroup$

I think these comments may be helpful.

I will assume that we have some polynomial or multinomial (perhaps with monomials from some restricted set) and an oracle which instantly returns the value at any given point (perhaps from a restricted domain). We wish to find a specific coefficient and wonder how many queries we need to make and how hard the calculation would be. Each query gives a linear combination of the various coefficients so we wonder how small a system of equations (drawn from the restricted class available to us) suffices. I would expect that in general (but not always) $m$ queries would be required where $m$ is the potential number of monomials. So it (often) takes as many queries to get one particular coefficient as to get them all.

Consider first this problem: Given a polynomial $\sum_0^na_nx^n$ find $a_i.$ Then $a_0=f(0).$ But it would take $n+1$ queries to specify any other coefficient or even to find $a_0$ if we were not allowed to ask about $f(0).$ At that point we could find them all. If we had an upper bound $\max_i(|a_i|)\lt B$ and wanted $a_n$ then $|a_n-\frac{f(N)}{N^n}| \lt \varepsilon$ for $N \gt \frac{nB}{\varepsilon}.$ If the coefficients were know to be integers this might be effective.This isn't the given problem so I will not discuss finding $f(e^{2j\pi/n}),$ precomputing the inverse of a Vandermonde matrix or doing successive differences.

Next suppose that we know in advance that the vector of variables is $\mathbf{x}=(x_1,\cdots,x_n)$ and $f(\mathbf{x})=\sum_Sa_S\prod_{i \in S}x_i$ where $S$ varies over the subsets of $[n]=\{1,\cdots ,n\}.$ Then there are $2^n$ coefficients. If our queries need are restricted to $0-1$ vectors then to find $a_S$ would could do $2^{|S|}$ queries (setting all irrelevant variable to $0$) and use inclusion exclusion. If done correctly we could have all $a_T$ for $T \subseteq S$ for the same work. This would seem best possible.

Minimality Suppose I tell you in advance that $f=\prod_1^n z_i$ where either $z_i=x_i$ or $z_i=1-x_i.$ Then the coefficient of $x_1x_2\cdots x_n$ is $\pm 1$ and we wish to determine which it is. Then each of the $2^n$ possible queries will return $0$ except a particular one which will tell us everything. If we are lucky we find out in a few queries, but it could take $2^n$ queries.

In this rather restricted case one can technically do it with one evaluation: Set $$x_i=\frac{2^{2^i}}{1+2^{2^i}}.$$

Then the result is a fraction with an odd denominator and numerator $2^{2^k}$ where the bits of $k$ tell us which $z_i=x_i.$

The question as asked concerns linear combinations of monomials in $n$ variables all of degree at most $n.$ There are $\binom{n+k-1}k$ such monomials of degree $k$ so potentially $\binom{2n}n \approx \frac{4^n}{\sqrt{\pi n}}$ summands. In this case, for each $T \subseteq [n]$, $2^{|T|}$ queries suffice to determine the sum of all the coefficients for monomials using positive powers of exactly $\{x_t \mid t \in T\}.$ For $T=[n]$ this sum is, as remarked above, just what we want.

I suspect that if we can't use $0-1$ vectors , for example all the $x_i$ in a query need to be integers at least $2$, then $2^n$ queries would not be enough. Maybe then it would take $\binom{2n}n$ queries.


Here is an interesting case I wondered about. Suppose we explicitly see that $$f=\prod_{i=1}^n\left(\sum_{j=1}^na_{ij}x_j+c_i\right).$$ Then the finding the coefficient in question amounts to computing the permanent of the matrix $A={\huge(}a_{ij}{\huge)}.$ Naively that takes $n!n$ operations. This can perhaps be sped up to $2^nn^2$ or $2^nn.$ Much more than for the determinant. Of course each of our allowed queries instantly gives us the result of many arithmetic operations so it is not contradictory that $2^n$ suffice.

For that matter, we don’t need the information about where $f$ came from. I was just emphasizing that knowing that was no real help. The method here merely uses that $f$ is some linear combination of $\binom{2n}{n}$ monomials.

$\endgroup$
  • 1
    $\begingroup$ Since computing the permanent is known to be #P-hard, you have proved that this problem is too. So we can be pretty confident that nobody is likely to find a sub-exponential time algorithm any time soon. $\endgroup$ – Brendan McKay Apr 15 at 0:50
  • $\begingroup$ @BrendanMcKay Perhaps for doing it with “0-1” queries. The result of one evaluation with the variables set to mutually transcendental values should reveal all the coefficients, if we are smart enough. Of course in this last example we are just trying to avoid multiplying everything out. $\endgroup$ – Aaron Meyerowitz Apr 15 at 3:34
  • $\begingroup$ Thanks. For the univariate case you can compute the $m$ lowest coefficients by computing $f\ \mod x^m$ or ask the oracle to work in $Z[x]/x^m$. There could be reduction multivariate to univariate by setting $x_i=x^{2^i}$. Then $x_i x_j=x^{2^{i}+{2^j}}$ and this is unique by binary expansion. $\endgroup$ – joro Apr 15 at 3:56
  • $\begingroup$ 2^(2^i) grows prohibitively fast, Fermat numbers minus 1.. You will run out of memory for $i$ over say 16. $\endgroup$ – joro Apr 15 at 4:53
  • $\begingroup$ Aaron, I don't understand your response. It is #P-complete to find the permanent of a 0-1 matrix. You showed how to reduce that problem to this coefficient-extraction problem in polynomial time. Therefore, this problem is #P-complete too, even in the "simple" case of a product of linearly many linear factors. It isn't about queries. I'm using the usual Turing machine model. $\endgroup$ – Brendan McKay Apr 15 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.