The L₄ norm of Littlewood polynomials derived from the Jacobi symbol

DOI10.2140/PJM.2012.257.395MaRDI QIDQ448917zbMATH OpenOpenAlexFDO

Authors Jonathan Jedwab, Kai-Uwe Schmidt

Publication date 11 September 2012

Published in Pacific Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.5180, http://msp.org/pjm/2012/257-2/p06.xhtml

asymptotic Littlewood polynomial merit factor multiplicative character norm

Special sequences and polynomials (11B83) Polynomials in number theory (11C08) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Abstract: Littlewood raised the question of how slowly the L_4 norm ||f||_4 of a Littlewood polynomial f (having all coefficients in {-1,+1}) of degree n-1 can grow with n. We consider such polynomials for odd square-free n, where phi(n) coefficients are determined by the Jacobi symbol, but the remaining coefficients can be freely chosen. When n is prime, these polynomials have the smallest known asymptotic value of the normalised L_4 norm ||f||_4/||f||_2 among all Littlewood polynomials, namely (7/6)^{1/4}. When n is not prime, our results show that the normalised L_4 norm varies considerably according to the free choices of the coefficients and can even grow without bound. However, by suitably choosing these coefficients, the limit of the normalised L_4 norm can be made as small as the best known value (7/6)^{1/4}.

Review text

A Littlewood polynomial is a polynomial \(A(z) = \sum_{z=0}^{n-1} \in \mathbb C[z]\) with coefficients \(a_j\in\{-1,1\}\) for each \(j\). An example is the polynomial NEWLINE\[NEWLINE X=J+1\;\quad\text{with}\quad J(z) = \sum_{j=1}^{p-1}(j\;|\;p)z^j, NEWLINE\]NEWLINE where \(p\) is an odd prime and \((\cdot\;|\;p)\) is the Legendre symbol.NEWLINENEWLINEGiven a polynomial \(A\in \mathbb C[z]\) of degree \(n-1\) and a real \(r\), the rotation \(A_r\) of \(A\) is defined by NEWLINE\[NEWLINE A_r(z) = z^{-\lfloor nr\rfloor}A(z) \bmod (z^n-1). NEWLINE\]NEWLINE \textit{T. Høholdt} and \textit{H. E. Jensen} [IEEE Trans. Inf. Theory 34, No. 1, 161--164 (1988; Zbl 0652.40006)] showed that the merit factor \(F(X_r)\) of \(X_r\) satisfies \(\lim_{p\rightarrow \infty}F(X_r) = f(r)\) with \(f(r) = (1/6+8(|r|-1/4)^2)^{-1}\), \(-1/2 < r \leq 1/2\). From this result, Littlewood polynomials with largest known asymptotic merit factor \(6\) are obtained.NEWLINENEWLINEThe authors consider the more general Littlewood polynomials \(J(z)+V(z)\), with NEWLINE\[NEWLINE J(z) = \sum_{j=1}^{n-1}(j\;|\;n)z^j, NEWLINE\]NEWLINE where \((\cdot\;|\;n)\) denotes the Jacobi symbol, and \(V(z) = \sum_{j=0}^{n-1}\) is some polynomial with \(v_j = 0 \leftrightarrow \gcd(j,n) = 1\). Consequently, \(J(z)+V(z)\) is a Littlewood polynomial which the authors call a Littlewood completion of \(J\). The authors show that subject to a mild condition on the growth rate of the smallest prime factor \(p_n\) of \(n\), there is no Littlewood completion of \(J\) for which the asymptotic merit factor of \(J_r+V_r\) exceeds \(f(r)\), but a choice of a polynomial \(V\) is given, for which \(\lim_{n\rightarrow\infty}F(J_r+V_r) = f(r)\). For a more restrictive condition on \(p_n\), namely \(n^{1/3}/p_n\rightarrow 0\), they show that \textit{all} Littlewood completions satisfy \(\lim_{n\rightarrow\infty}F(J_r+V_r) = f(r)\). The results in this paper significantly enlarge the set of explicitly defined Littlewood polynomials with asymptotic merit factor equal to the current best known value \(6\).

Recommendations

Cited in

(5)

This page was built for publication: The \(L_4\) norm of Littlewood polynomials derived from the Jacobi symbol

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q448917)