Expected norms of zero-one polynomials Article

Borwein, P, Choi, KKS, Mercer, I. (2008). Expected norms of zero-one polynomials . Canadian Mathematical Bulletin, 51(4), 497-507. 10.4153/CMB-2008-050-2

cited authors

  • Borwein, P; Choi, KKS; Mercer, I

abstract

  • Let An = a0 + a1z + ⋯ + a n-1zn-1: aj ∈ {0,1}, whose elements are called zero-one polynomials and correspond naturally to the 2n subsets of [n]:= {0,1,...,n-1}. We also let An,m = {α(z) ∈ An: α(1) = m}, whose elements correspond to the mn subsets of [n] of size m, and let Bn = An+1 An, whose elements are the zero-one polynomials of degree exactly n. Many researchers have studied norms of polynomials with restricted coefficients. Using ||α||p to denote the usual Lp norm of α on the unit circle, one easily sees that α(z) = a0+a1z+⋯+aNzN ∈ ℝ[z] satisfies ||α||22 = c0 and ||a||44 = c02 + 2(c 12 + ⋯ + cN2), where c k := ∑j=0N-k ajaj+k for 0 ≤ k ≤ N. If a(z) ∈ An,m, say α(z) = z β1 + ⋯ + zβm where β1 < ⋯ < βm, then ck is the number of times k appears as a difference βi - βj. The condition that α ∈ An,m satisfies ck ∈; {0,1} for 1 ≤ k ≤ n-1 is thus equivalent to the condition that {β,...,βm} is a Sidon set (meaning all differences of pairs of elements are distinct). In this paper, we find the average of ||a|| 44 over α ∈ An, α ∈ Bn, and α ∈ An,m. We further show that our expression for the average of ||α||44 over A n,m yields a new proof of the known result: if m = o(n1/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 Iim n→∞ B(n, m)/ mn =1. ©Canadian Mathematical Society 2008.

authors

publication date

  • January 1, 2008

published in

Digital Object Identifier (DOI)

start page

  • 497

end page

  • 507

volume

  • 51

issue

  • 4