Expected Norms of Zero-One Polynomials

Borwein, Peter ; Choi, Kwok-Kwong Stephen ; Mercer, Idris

Canadian mathematical bulletin, Tome 51 (2008) no. 4, pp. 497-507

Résumé

Let ${{A}_{n}}\,=\,\{{{a}_{0}}+{{a}_{1}}z+\,.\,.\,.\,+\,{{a}_{n-1}}{{z}^{n-1}}\,:\,{{a}_{j}}\,\in \,\{0,1\}\}$ , whose elements are called zero-one polynomials and correspond naturally to the ${{2}^{n}}$ subsets of $\left[ n \right]\,:=\,\{0,\,1,\,.\,.\,.\,,\,n-1\}$ . We also let ${{A}_{n,m\,}}\,=\,\{\alpha \left( z \right)\,\in \,{{A}_{n}}\,:\,\alpha \left( 1 \right)\,=\,m\}$ , whose elements correspond to the $\left( _{m}^{n} \right)$ subsets of $\left[ n \right]$ of size $m$ , and let ${{B}_{n}}\,=\,{{A}_{n+1}}\,\backslash \,{{A}_{n}}$ , whose elements are the zero-one polynomials of degree exactly $n$ .Many researchers have studied norms of polynomials with restricted coefficients. Using $\|\alpha {{\|}_{p}}$ to denote the usual ${{L}_{p}}$ norm of $\alpha$ on the unit circle, one easily sees that $\alpha \left( z \right)\,=\,{{a}_{0}}+{{a}_{1}}z+.\,.\,.+{{a}_{N}}{{z}^{N}}\,\in \,\mathbb{R}\left[ z \right]$ satisfies $\|\alpha \|_{2}^{2}\,=\,{{c}_{0}}$ and $\|\alpha \|_{4}^{4}\,=\,c_{0}^{2}\,+\,2\left( c_{1}^{2}\,+\,.\,.\,.\,+\,c_{N}^{2} \right)$ , where ${{c}_{k}}\,:=\,\sum _{j=0}^{N-k}\,{{a}_{j}}{{a}_{j+k}}\,\text{for}\,\text{0}\le \,\text{k}\,\le N$ .If $\alpha \left( z \right)\,\in \,{{A}_{n,m}}$ , say $\alpha \left( z \right)\,=\,{{z}^{{{\text{ }\!\!\beta\!\!\text{ }}_{1}}}}\,+\,.\,.\,.\,+\,{{z}^{{{\text{ }\!\!\beta\!\!\text{ }}_{m}}}}$ where ${{\beta }_{1}}\,<\,.\,.\,.\,<\,{{\beta }_{m}}$ , then ${{c}_{k}}$ is the number of times $k$ appears as a difference ${{\beta }_{i}}\,-\,{{\beta }_{j}}$ . The condition that $\alpha \,\in \,{{A}_{n,m}}$ satisfies ${{c}_{k}}\,\in \,\{0,1\}$ for $1\,\le \,k\,\le \,n\,-\,1$ is thus equivalent to the condition that $\{{{\beta }_{1}},\,.\,.\,.\,,\,{{\beta }_{m}}\}$ is a Sidon set (meaning all differences of pairs of elements are distinct).In this paper, we find the average of $\left\| \alpha\right\|_{4}^{4}$ over $\alpha \,\in \,{{A}_{n}}$ , $\alpha \,\in \,{{B}_{n}}$ and $\alpha \,\in \,{{A}_{n,m}}$ . We further show that our expression for the average of $\left\| \alpha\right\|_{4}^{4}$ over ${{A}_{n,m}}$ yields a new proof of the known result: if $m\,=\,o\left( {{n}^{1/4}} \right)$ and $B\left( n,\,m \right)$ denotes the number of Sidon sets of size $m$ in $\left[ n \right]$ , then almost all subsets of $\left[ n \right]$ of size $m$ are Sidon, in the sense that ${{\lim }_{n\to \infty }}\,B\left( n,\,m \right)/\left( _{m}^{n} \right)\,=\,1$ .

Détail

DOI : 10.4153/CMB-2008-050-2

Mots-clés : 11B83, 11C08, 30C10

Bibliographie

[1] [1] Borwein, P. B., Computational Excursions in Analysis and Number Theory. CMS Books in Mathematics/Ouvrages de Mathmatiques de la SMC 10. Springer-Verlag, New York, 2002. Google Scholar

[2] [2] Borwein, P. B. and Choi, K.-K. S., The average norm of polynomials of fixed height. Trans. Amer. Math. Soc. 359(2007), no. 2, 923–936. Google Scholar

[3] [3] Erdős, P., Some unsolved problems. Michigan Math. J. 4(1957), 291–300. Google Scholar

[4] [4] Godbole, A. P., Janson, S., Locantore, N. W. Jr., and Rapoport, R., Random Sidon sequences. J. Number Theory 75(1999), no. 1, 7–22. Google Scholar

[5] [5] Littlewood, J. E., Some Problems in Real and Complex Analysis. D.C. Heath, Lexington, MA, 1968. Google Scholar

[6] [6] Nathanson, M. B.. On the ubiquity of Sidon sets. In: Number Theory. Springer, New York, 2004, pp. 263–272. Google Scholar

[7] [7] Newman, D. J. and Byrnes, J. S., The L 4 norm of a polynomial with coefficients ±1 . Amer. Math. Monthly 97(1990), 42–45. Google Scholar