CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  Publicationsjournals
Publications        
Search results

Search: MSC category 30C10 ( Polynomials )

  Expand all        Collapse all Results 1 - 2 of 2

1. CMB 2008 (vol 51 pp. 497)

Borwein, Peter; Choi, Kwok-Kwong Stephen; Mercer, Idris
Expected Norms of Zero-One Polynomials
Let $\cA_n = \big\{ a_0 + a_1 z + \cdots + a_{n-1}z^{n-1} : a_j \in \{0, 1 \ } \big\}$, whose elements are called \emf{zero-one polynomials} and correspond naturally to the $2^n$ subsets of $[n] := \{ 0, 1, \ldots, n-1 \}$. We also let $\cA_{n,m} = \{ \alf(z) \in \cA_n : \alf(1) = m \}$, whose elements correspond to the ${n \choose m}$ subsets of~$[n]$ of size~$m$, and let $\cB_n = \cA_{n+1} \setminus \cA_n$, whose elements are the zero-one polynomials of degree exactly~$n$. Many researchers have studied norms of polynomials with restricted coefficients. Using $\norm{\alf}_p$ to denote the usual $L_p$ norm of~$\alf$ on the unit circle, one easily sees that $\alf(z) = a_0 + a_1 z + \cdots + a_N z^N \in \bR[z]$ satisfies $\norm{\alf}_2^2 = c_0$ and $\norm{\alf}_4^4 = c_0^2 + 2(c_1^2 + \cdots + c_N^2)$, where $c_k := \sum_{j=0}^{N-k} a_j a_{j+k}$ for $0 \le k \le N$. If $\alf(z) \in \cA_{n,m}$, say $\alf(z) = z^{\beta_1} + \cdots + z^{\beta_m}$ where $\beta_1 < \cdots < \beta_m$, then $c_k$ is the number of times $k$ appears as a difference $\beta_i - \beta_j$. The condition that $\alf \in \cA_{n,m}$ satisfies $c_k \in \{0,1\}$ for $1 \le k \le n-1$ is thus equivalent to the condition that $\{ \beta_1, \ldots, \beta_m \}$ is a \emf{Sidon set} (meaning all differences of pairs of elements are distinct). In this paper, we find the average of~$\|\alf\|_4^4$ over $\alf \in \cA_n$, $\alf \in \cB_n$, and $\alf \in \cA_{n,m}$. We further show that our expression for the average of~$\|\alf\|_4^4$ over~$\cA_{n,m}$ yields a new proof of the known result: if $m = o(n^{1/4})$ and $B(n,m)$ denotes the number of Sidon sets of size~$m$ in~$[n]$, then almost all subsets of~$[n]$ of size~$m$ are Sidon, in the sense that $\lim_{n \to \infty} B(n,m)/\binom{n}{m} = 1$.

Categories:11B83, 11C08, 30C10

2. CMB 1999 (vol 42 pp. 3)

Beauzamy, Bernard
How the Roots of a Polynomial Vary with Its Coefficients: A Local Quantitative Result
A well-known result, due to Ostrowski, states that if $\Vert P-Q \Vert_2< \varepsilon$, then the roots $(x_j)$ of $P$ and $(y_j)$ of $Q$ satisfy $|x_j -y_j|\le C n \varepsilon^{1/n}$, where $n$ is the degree of $P$ and $Q$. Though there are cases where this estimate is sharp, it can still be made more precise in general, in two ways: first by using Bombieri's norm instead of the classical $l_1$ or $l_2$ norms, and second by taking into account the multiplicity of each root. For instance, if $x$ is a simple root of $P$, we show that $|x-y|< C \varepsilon$ instead of $\varepsilon^{1/n}$. The proof uses the properties of Bombieri's scalar product and Walsh Contraction Principle.

Category:30C10

© Canadian Mathematical Society, 2014 : http://www.cms.math.ca/