About the problem
For a polynomial \(P\in\mathbb{C}[x],\) the \(L_{\lambda}\) norm of \(P\) for \(\lambda > 0\) is
\[\|P\|_{\lambda} = \left(\int_0^1 |P(e(t))|^{\lambda} d t\right)^{1/\lambda},\]and the Mahler measure of \(P\) is
\[M_0(P)=\exp\left(\int_{0}^1\log |P(e(t))|dt\right).\]This problem, known as the Borwein-Mahler problem, asks for an infinite family of polynomials \(P_n(x)=\sum_{k=0}^na_kx^k\), \(n \to \infty\), with \(a_k=\pm 1\) for all \(0\le k\le n\), such that the normalized Mahler measure is large for each polynomial. This benchmark specifically asks for an infinite family of polynomials such that for each \(P_n\), it holds that
\[b(P_n)=\frac{M_0(P_n)}{\sqrt{n+1}} \geq 0.97.\]Polynomials of this type, i.e. polynomials where each coefficient is \(\pm 1\), are known as Littlewood polynomials. A solution to this problem would likely involve ideas across analysis, combinatorics, and number theory, which were all involved in the current normalized Mahler measure record of 0.954. If a polynomial family were found with normalized Mahler measure arbitrarily close to one, this would shed light on the related important question about ultraflat Littlewood polynomials.
This verifier samples a finite set of \(n\) from the claimed infinite family of polynomials, and the Mahler measure computation involves the possibility of numerical error (since it uses FFT), so the verifier is not exact.
Prompt
For a polynomial P(x) = sum_{k=0}^d a_k x^k, write e(t) = exp(2*pi*i*t) and recall the Mahler measure
M_0(P) = exp( integral_0^1 log|P(e(t))| dt ).
A Littlewood polynomial is one whose coefficients all satisfy a_k = +-1. For such a polynomial of degree d, Parseval gives ||P||_2 = sqrt(d+1), and Jensen's inequality yields M_0(P) <= sqrt(d+1). Define the normalized Mahler measure
b(P) = M_0(P) / sqrt(d+1),
so that 0 < b(P) <= 1. The goal is to construct Littlewood polynomials whose normalized Mahler measure is as large as possible at arbitrarily large degree.
Concretely: find an algorithm that takes a positive integer n as input and produces a Littlewood polynomial of degree strictly greater than n whose normalized Mahler measure satisfies
b(P) > 0.97.
Solution format:
* Write a Python script defining a function `solution(n: int) -> str`.
* The returned string must be over the alphabet {'+', '-'} and have length d+1 > n+1, where the k-th character (0-indexed) is the sign of the coefficient a_k, listing a_0, a_1, ..., a_d (lowest-order coefficient first). '+' denotes the coefficient +1 and '-' denotes -1.
* Do not include any code at the file level. You may include a `main` block for testing, but it will not be executed by the verifier.
* For each tested n the call to solution(n) must complete within 5 minutes on a typical laptop, and the returned degree must not exceed 2000000.
* An example showing the required format is provided in the file "/solution_example.py".