Expected Norms of Zero-One Polynomials

Abstract Let = {a0 + a1z + · · · + an–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 = ﹛α(z) ∈ : α(1) = m﹜, whose elements correspond to the subsets of [n] of size m, and let , 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 and , where . If α(z) ∈ , 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 α ∈ satisfies ck ∈ ﹛0, 1﹜ for 1 ≤ k ≤ n – 1 is thus equivalent to the condition that ﹛β1, … , βm﹜ is a Sidon set (meaning all differences of pairs of elements are distinct). In this paper, we find the average of over α ∈ , α ∈ , and α ∈ . We further show that our expression for the average of over 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 .

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.