The maximum number of relevant variables of a degree-3 Boolean function is $R_3 = 10$

Let $R_d$ be the largest number of variables a Boolean function $f:\{-1,1\}^n\to\{-1,1\}$ of Fourier degree $d$ can depend on. Nisan and Szegedy (1994) give $R_d \le d\,2^{d-1}$ and Chiarelli, Hatami and Saks (2020) give $R_d \ge 3\cdot 2^{d-1}-2$ ; for $d=3$ this reads $10 \le R_3 \le 12$ , and the exact value was listed as unknown (Tao's optimisation-problems page, entry 44a). Determine $R_3$ .

Result: Proved(see note)
Status: Resolved
AI contribution: AI-discovered
Method: Argument
Field: Analysis of Boolean functions: Fourier degree, juntas, relevant variables
Posed by: Nobody by name. Nisan-Szegedy (1994) and Chiarelli-Hatami-Saks (2020) bracket $R_3$ in $[10, 12]$ as a byproduct of two theorems; Tao's optimisation list entry 44a defines $R_d$ but asks for $C_{44}$
Year posed: 1994
Years open: 32y
Solved: 2026-09-13
Model: Claude Fable 5.1; Claude Opus 5; Claude Sonnet 5
Vendor: Anthropic
Collaborators: Andrew Moffat
Verification: Lean-checked, statement unaudited
Publication: Announced
Significance: 12 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

$R_3 = 10$ : no Boolean function of Fourier degree 3 depends on 11 or 12 variables, and the Chiarelli-Hatami-Saks function attains 10. Uniqueness up to symmetry of the extremal function is observed by exhaustive search, not proved. The same paper's general theorem, that the Nisan-Szegedy bound $d\,2^{d-1}$ is never attained for $d \ge 3$ , was submitted separately and declined: Wellens's 2019 Table 2 already gives $R_8 \le 1008 < 1024$ and keeps beating Nisan-Szegedy above that, so non-attainment was known for every $d \ge 8$ , $d = 3$ is this entry, and the new cases are $d = 4$ to $7$ .

What the AI did

Found and wrote the proof: the discrete derivative of a degree-3 Boolean function in any variable is a $\{0,\pm1\}$ -valued degree-2 polynomial whose monomials have empty symmetric difference, so vertex links are 4-cycles and the term hypergraph is rigid; a case analysis on the slack $\sum_i (m_i-4)\in\{0,2,4\}$ rules out 11 and 12 variables. Independent AI instances refereed the proof adversarially over four rounds (two real gaps found and fixed), wrote an exhaustive canonical search of the equivalent finite problem (0 solutions at $n=11$ ; exactly the CHS function at $n=10$ ), and formalised the whole finite statement in Lean 4, where the hardest case was machine-checked by a route simpler than the original topological one. The human author directed the campaign and takes responsibility for the write-up.

Verification

Statement.lean was read at commit eb50c0a on 15 September 2026. $F(n)$ is the standard finite encoding: a degree-3 Boolean function has Fourier coefficients in $2^{-2}\mathbb{Z}$ (granularity $2^{1-d}$ ), so $n_S = 4\hat f(S)$ is integral and supported on $|S| \le 3$ ; Parseval gives $\sum n_S^2 = 16$ (i); $f^2 = 1$ is the convolution identity $\sum_{S \triangle T = U} n_S n_T = 0$ for nonempty $U$ (ii); relevance is (iii). So $F(11)$ and $F(12)$ , both kernel-checked with axioms exactly propext, Classical.choice, Quot.sound, no sorry, no native_decide, rule out 11 and 12 relevant variables, and the Chiarelli-Hatami-Saks function gives 10. That reduction is a paper argument, not Lean, and this is the first outside reading of it, hence lean-checked as submitted. CI (lean and verify workflows) green on GitHub at eb50c0a, which is the commit v1.0 points at. Not established: anything about $R_4$ or $C_{44}$ . Announcement reflects repository-only publication; arXiv endorsement pending.

Sources

Submitted by CobaltPanther851 on 14 Sep 2026

CobaltPanther85115 Sep 2026, 08:33 UTC

Prior-art notice from the submitter: $R_3 = 10$ was proved in 2000, and we missed it.

Tarannikov and Kirienko, "Spectral analysis of high order correlation immune functions", IACR ePrint 2000/050 (https://eprint.iacr.org/2000/050), Theorem 11: $p(4) = 10$ . Here $p(k)$ is the least integer such that every $(n-k)$ -resilient Boolean function depends nonlinearly on at most $p(k)$ variables.

Why this is $R_3$ : put $f' = f\cdot\chi_{[n]}$ , so $\widehat{f'}(S) = \widehat{f}([n]\setminus S)$ . By Xiao–Massey, $\deg f \le d$ iff $f'$ is $(n-d-1)$ -resilient, and $x_i$ is irrelevant for $f$ iff $f'$ depends linearly on $x_i$ . Hence $R_d = p(d+1)$ , and $R_3 = p(4) = 10$ .

This translation is Lemma 1 of Krotov–Valyuzhenich, Discrete Math. 347 (2024) 114138 (arXiv:2311.05566). They state it in degree language: a Boolean function of degree at most 3 "cannot have more than 10 essential arguments". They also refer to "the unique such function with 10 essential arguments", so the uniqueness we observed by search is recorded there too.

The same literature has two more relevant results. Tarannikov–Korolev–Botev (ASIACRYPT 2001, LNCS 2248, Theorem 6) prove $p(k) \le (k-1)2^{k-2}$ , which is Nisan–Szegedy in resilient form. They also give the $3\cdot 2^{k-2}-2$ construction, earlier than CHS.

Consequences:
1. This entry settles a question already settled in 2000. What the campaign adds is an independent Fourier-analytic proof whose finite core is Lean-checked. Please re-tier or re-status the entry as you see fit. We would describe it as a new proof of a known result, not a resolution.
2. The problem statement's premise that "the exact value was listed as unknown (Tao's optimisation-problems page, entry 44a)" is wrong. The 44a page, including its source history since February 2026, never mentions $R_3$ . The error was ours.
3. For the declined companion entry: since $d = 3$ is also prior art, non-attainment of Nisan–Szegedy is new only for $4 \le d \le 7$ .

We have flagged the prior art on Tao's list: https://github.com/teorth/optimizationproblems/issues/190. The paper, README and result notes have been corrected to credit Tarannikov–Kirienko and to state novelty as $4 \le d \le 7$ plus the structural lemma. The corrected version will appear in the repository with its next push; the v1.0 release still has the old text. Thank you for the Wellens catch, which led us to find this.

The maximum number of relevant variables of a degree-3 Boolean function is R3=10R_3 = 10R3​=10

What was actually shown

What the AI did

Verification

Sources

Discussion1

The maximum number of relevant variables of a degree-3 Boolean function is $R_3 = 10$