Abstract view
Expected Norms of ZeroOne Polynomials


Published:20081201
Printed: Dec 2008
Peter Borwein
KwokKwong Stephen Choi
Idris Mercer
Abstract
Let $\cA_n = \big\{ a_0 + a_1 z + \cdots + a_{n1}z^{n1} : a_j \in \{0, 1 \
} \big\}$, whose elements are called \emf{zeroone polynomials}
and correspond naturally to the $2^n$ subsets of $[n] := \{ 0, 1,
\ldots, n1 \}$. 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 zeroone 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}^{Nk} 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 n1$ 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$.