# A $o((n-lgn)1-2)$ lower bound on the number of additions necessary to compute 0-1 polynomials over the ring of integer polynomials

Ronald L. Rivest, Jean-Paul van de Wiele

► To cite this version:

Ronald L. Rivest, Jean-Paul van de Wiele. A $o((n-lgn)1-2)$ lower bound on the number of additions necessary to compute 0-1 polynomials over the ring of integer polynomials. [Research Report] IRIA-RR-324, IRIA. 1978, pp.5. hal-04716514

HAL Id: hal-04716514

https://inria.hal.science/hal-04716514v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

laboria

laboratoire de recherche
en informatique
et automatique

AN Ω((n/lnn)¹/²) LOWER BOUND
ON THE NUMBER OF ADDITIONS
NECESSARY TO COMPUTE
0-1 POLYNOMIALS
OVER THE RING
OF INTEGER POLYNOMIALS

<figure><img src="image_3.png" /></figure>

Ronald L. RIVEST
Jean-Paul Van de WIELE

Rapport de Recherche N° 324
September 1978 sp.

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B.P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20
AN $\Omega((n/\lg n)^{1/2})$ LOWER BOUND ON THE NUMBER OF ADDITIONS NECESSARY TO COMPUTE 0-1 POLYNOMIALS OVER THE RING OF INTEGER POLYNOMIALS

Ronald L. Rivest*, Jean-Paul Van de Wiele**

**Résumé :**

Nous montrons une borne inférieure de l'ordre de $(n/\lg n)^{1/2}$ pour la complexité additive de l'évaluation des polynômes 0-1 de degré n sur l'anneau des polynômes à coefficients entiers.

**Abstract :**

We show a lower bound of order $(n/\lg n)^{1/2}$ on the additive complexity of the computation of 0-1 polynomials of degree n in the model with integer preconditioning.

<footnote>* Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139.</footnote>

<footnote>**IRIA/LABORIA.</footnote>
# 1 - Introduction

An interesting open problem in arithmetic complexity is to find concrete polynomials that are both simple and hard to compute. In this paper we study the complexity of univariate polynomials with 0-1 coefficients in the model with integer preconditioning. In this model the free constants are the integers and the allowed operations are addition, subtraction and multiplication (no division). We compute over the ring of integer polynomials. Using a counting argument, inspired by Paterson-Stockmeyer [1], we prove a lower bound of order $(n/\lg n)^{1/2}$ on the additive complexity of 0-1 polynomials in this model. In other words there is a strictly positive real number $\gamma$ such that for all natural numbers $n > 1$ there is a univariate $n$ degree 0-1 polynomial that requires at least $\gamma(n/\lg n)^{1/2}$ $\pm$ operations to be evaluated in $Z[x] \mod(Z \cup \{x\})$. This bound is better than the best known lower bound on the additive complexity of 0-1 polynomials in the model with general complex preconditioning, which is only $\Omega(n^{1/2}/\lg n)$. (Van de Wiele [4]. See also this paper for a survey of results on the computational complexity of 0-1 polynomials).

In both models the best upper bound is $O(n/\lg n)$. (Savage [2]). Hence a stronger lower bound may still be shown.

Paterson, Stockmeyer [1] have shown a lower bound of order $n^{1/2}$ on the non scalar multiplicative complexity of 0-1 $n$ degree polynomials in the model with integer preconditioning. Moreover they have shown the optimality of this bound. The question is also settled for the total number of operations. Indeed it has been shown (Van de Wiele [4]) that there are $n$ degree 0-1 polynomials that require order of $(n/\lg n)$ total arithmetic operations to be computed over the field of complex rational functions. Alike the previous one, this bound is asymptotically optimal.
## 2 - Definitions and model of computation

Let $F$ denote the set $\{0,1\}$ and let $N, Z, Z_p$ stand for the set of non-negative natural numbers, integers and integers modulo $p$, respectively. For a prime $p, Z_p$ is a field. Let $x$ be an indeterminate. $F[x]$ is the set of polynomials in $x$ with $0$-1 coefficients. Let $k$ be a ring. $k[x]$ is the ring of polynomials in $x$ over $k$.

A computation $\beta$ in $k[x] \mod (k \cup \{x\})$ for $p(x) \in k[x]$ is a sequence of computation steps $S_i$, $1 \le i \le 1$, such that there is $i_0$, $1 \le i_0 \le 1$, with $S_{i_0} = p(x)$ and either

(i) $S_i \in k \cup \{x\}$ or

(ii) $S_i = S_j \circ S_k$ with $j, k < i$ and $\circ \in \{+, -, .\}$.

The polynomials $S_i$ are the results of the computation and $\beta$ is said to compute the $S_i$.

The additive complexity of a polynomial $p(x) \in k[x]$ over the ring $k[x]$ is the minimum number of addition and subtraction steps in a computation for $p$ in $k[x] \mod (k \cup \{x\})$.

We are now going to study the additive complexity over $Z[x]$ of polynomials in $F[x]$. We denote by $L(\pm, p)$ the additive complexity over $Z[x]$ of a polynomial $p(x)$ in $Z[x]$.

If $f$ and $g$ are functions from $N$ to $N$, $f(n) = \Omega(g(n))$ means that there is a positive constant $\gamma$ such that finally $f(n) \ge \gamma g(n)$. The abbreviation $1g$ stands always for $\log_2$.

## 3 - An $\Omega((n/1g \cdot n)^{1/2})$ lower bound on the additive complexity of 0-1 polynomials over the ring of integers

**Theorem 3.1** There exists a real number $\gamma > 0$ such that for any natural number $n > 1$ there is a polynomial of degree $n$ in $F[x]$ that cannot be computed in
$Z[x] \mod (Z \cup \{x\})$ with less than $\gamma((n/\lg n))^{1/2}$ additive operations. $\square$

**Proof.** Let $n$ and $q$ be natural numbers, $q$ a prime. We shall fix $q$ later. Consider the finite field $Z_q$ and the ring homomorphism $H : Z \to Z_q$ given by $H(z) = z \mod (q)$. If $p(x) = \sum_{i=0}^n z_i x^i \in Z[x]$ can be evaluated by a computation in $Z[x] \mod (Z \cup \{x\})$ using $k$ additions, then certainly $\hat{p}(x) = \sum_{i=0}^n H(z_i) x^i \in Z_q[x]$ can be evaluated by an algorithm in $Z_q[x] \mod (Z_q \cup \{x\})$ using $k$ additions. In the rest of the paper the term additions will be employed in place of additive operations.

Any computation in $Z_q[x] \mod (Z_q \cup \{x\})$ with $\le k$ additions can be expressed by the following scheme $A_k$, where the $m_{ij}$, $m'_{ij}$ are natural numbers and the $c_i$, $d_i$ integers modulo $q$.

$$ A_k \left| \begin{array}{l} s_0 = x, \\ s_j = c_j \prod_{i=0}^{j-1} s_i^{m_{i,j}}, \quad + \quad d_j \prod_{i=0}^{j-1} s_i^{m'_{i,j}}, \quad \text{for } 1 \le j \le k, \\ p(x) = s_{k+1} = c_{k+1} \prod_{i=0}^{k} s_i^{m_{i,k+1}} \end{array} \right. $$

Let $N(k)$ be the number of different polynomials in $Z_q[x]$ that are computable by at least one algorithm in $A_k$. Let $a$ be an element in $Z_q$ and let $b$ and $c$ be natural numbers with $b \equiv c \mod(q-1)$. Then it is well known that $a^b \equiv a^c \mod (q)$, since $q$ is a prime. Therefore the exponents $m_{i,j}$, $m'_{i,j}$ can be assumed to range over $\{0, 1, \dots, q-2\}$ and $N(k)$ is bounded above by $q^s$ where $s$ is the number of different parameters in $A_k$.
Thus :

$$
N(k) \le q \left[ \sum_{j=1}^{k} 2(j+1) + k + 2 \right] = q^{k^2+4k+2} .
$$

Let now M(k) be the number of different n. degree 0-1 polynomials in
Z[x]. M(k) = 2ⁿ provided q ≥ n. Let's choose the prime q such that n ≤ q ≤ 2n.
Such a prime exists for all n ≥ 1. (See for instance Trost [3], p. 57, Satz 31).

Every 0-1 polynomial of degree n can be computed by an algorithm in A<sub>k</sub>
only if N(k) ≥ M(k). This means

$$
q^{k^2+4k+2} \ge 2^n
$$

Thus $k^2 + 4k + 2 \ge n/1g$ $q \ge n/(2 \lg n)$ for n large enough. Hence
$k \ge (n/2lg n)^{1/2} - 2 \ge \frac{1}{2}$. $(n/1g n)^{1/2}$ for n large enough. This proves
that there is a positive real number $\gamma$ such that for all natural numbers
$n > 1$ there exists some 0-1 polynomial $p$ of degree $n$ such that
$L(\pm,p) \ge \gamma(n/1g n)$. We are done.[]

4 - Références

[1] M.S. Paterson and L.J. Stockmeyer, On the number of non scalar multi-
plications necessary to evaluate polynomials, Siam J. Comput. 2(1)
(1973) 60-66.

[2] J.E. Savage, An algorithm for the computation of linear forms, Siam J. Comput. 3(2) (1974) 150-158.

[3] E. Trost, Primzahlen (Birkhäuser, Basel, 1953).

[4] J-P. Van de Wiele, An optimal lower bound on the number of total operations to compute 0-1 polynomials over the field of complex numbers, Rapport Laboria N° 303 (Mai 1978).