The Fourier–Hahn–Lévy conjecture for tractable integer-valued moments

Let f:ZZf:\mathbb{Z}\to\mathbb{Z} be tractable, meaning that its ff-moment can be estimated to within a constant factor with a small sketch. The ff-moment is

v[n]f(x(v)).\sum_{v\in[n]} f(\mathbf{x}(v)).

Fourier–Hahn–Lévy conjecture. If f:ZZf:\mathbb{Z}\to\mathbb{Z} is tractable, then the ff-moment can be estimated to within a constant factor with a Lévy-Tower, either directly or after applying the Fourier–Hahn–Lévy method. The conjecture asserts that this method captures all tractable integer-valued ff-moments; the source does not provide a resolution.

Sources & referencesView supporting material

Primary source

Seth Pettie and Dingyu Wang, “A Unified Construction of Streaming Sketches via the Lévy-Khintchine Representation Theorem”, arXiv:2410.17426 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.