Polynomial bound in the Bohnenblust–Hille inequality on the Hamming cube {−1,1}^n:
overleaf.com/read/zyjrttqmwg…
I did not push on optimizing the exponent.
For some context: yesterday, major progress was announced on one of my favorite open problems, the polynomial growth of the Bohnenblust–Hille constant for analytic polynomials of many variables:
arxiv.org/pdf/2608.16584
When I saw it, my first reaction was: let’s get the same thing on the Hamming cube {−1,1}^n. Such a result would have a number of nice applications, including to questions around query complexity and PAC learning.
So I instructed four Grok bots to work on the problem together, with a fifth bot managing the room and coordinating the discussion. Today they produced a solution. To me, the proof looks correct. I have worked on this problem on and off for quite some time and also wrote a blog post about it back in 2019:
extremal010101.wordpress.com…
I’ll be editing the file, make the argument more readable, and polish it before putting it on arXiv or somewhere else. But if someone manages to push the exponent all the way down to zero, that would be wonderful.