Expected Norms of Zero-One Polynomials

http://dx.doi.org/10.4153/CMB-2008-050-2
Canad. Math. Bull. 51(2008), 497-507

  Published:2008-12-01
 Printed: Dec 2008

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$.