1

There's a paragraph in my book (Complexity and cryptography by Talbot and Welsh, chapter 4) that I don't fully understand:

Let $\mathbb Z[x_1,\dots,x_n]$ denote the set of polynomials in n variables with integer coefficients. [...] We have to be careful about how the polynomials are presented so that we know how to measure the input size. For example, the following polynomial $$f(x_1,\dots,x_n)=(x_1+x_2)(x_3+x_4)\dots(x_{2n-1}+x_{2n})$$ could clearly be encoded using the alphabet $\Sigma=\{*, 1, 0, x, (, ), +, -\}$with input size $O(n\log n)$. However if we expanded the parentheses, this same polynomial would then seem to have input size $O(n2^n\log n)$.

I don't understand how those input sizes are computed. Please clarify.

Gigili
  • 5,503
  • 8
  • 41
  • 62

1 Answers1

2

A much easier example might even be the case of a single variable. Consider $(1+x)^{1000}$. If I allow the input to be the string "(1+x)^(1000)", it takes just $11$ symbols to represent the polynomial. However, $$(1+x)^{1000}=\sum_{i=0}^{1000} \binom{1000}i x^i$$ so if I want to encode the polynomial as the array of its coefficients, I would have to store an integer array of length $1001$, and we are not talking about small numbers: $$\binom{1000}{349} = 21641441731297707077348545845272311836878450545908804528165639558 \\ 12217865325857621178201271717138465393830136766111168336839797876 \\ 007373244834924296399090470901253455374741637406778878451634116115\\ 025377035477150500931579776387615986613131159215927828897815143706 \\ 593214626066844000$$

The input sizes in your example (although there's something wrong with $f(x_1,\ldots,x_n)$ containing the variable $x_{2n}$) are computed as follows: You require $\log(n)$ space to represent an index $i\in\{1,\ldots,n\}=:[n]$, by encoding the number in base 2, for instance. This is the space required to encode a single variable from your polynomial ring. You have $O(n)$ factors in that expression, each of them a sum of constantly many two variables, that makes a total of $O(n\log(n))$.

If you expand the expression, it becomes $$(x_1+x_2)\cdots(x_{2n-1}+x_{2n}) =\sum_{\alpha:[n]\to\{0,1\}} \prod_{i=1}^n x_{2i-\alpha(i)}$$

and you may notice that those are $2^n$ many summands, each of them a product of $n$ variables, each of which requires the aforementioned $\log(n)$ bits to represent. That's $O(2^nn\log(n))$.

Jesko Hüttenhain
  • 14,792