Paperlane

no. 2 · Monday 26 October 2026

A counterexample to Tokareva's conjecture on sums of two bent functions

Yansong Feng, Hao Jiang, Guancheng Li, Tianyi Li and Lili Tang

math.CO

Abstract

It is well known that the sum of two bent functions on $\mathbb{F}^n$ has algebraic degree at most $n/2$ for even $n\ge 4$. Tokareva conjectured that the converse holds: every Boolean function with degree at most $n/2$ can be written as a sum of two bent functions. The conjecture has been verified for even $n\leq 6$ and for several special classes of Boolean functions. We disprove this conjecture by showing that $x_1x_2(x_3x_4+x_5x_6+x_7x_8)$ is not a sum of two bent functions on $\mathbb{F}^8$. We extend this construction to obtain counterexamples in every even dimension $n\ge 8$. Using Shaporenko's reduction, we also obtain explicit counterexamples to Tokareva's derivative conjecture in every even dimension $n\ge 10$.

comments
The counterexamples and proofs in this paper were obtained through large-scale automated reasoning with LLM agents while solving Problem~10 in NSUCRYPTO~2026 (MiniMax M3.1-Flash-Preview, 19 rounds of up to 100 independent agents between 12 and 18 October 2026, 1889 reports in all), paired with 8 rounds of independent audits (227 reports)
fields
Combinatorics, Information Theory
pdf ↗ page arXiv:2610.32239 ↗