Level B · Reproducible Complexity P-constant-44a-maximal-number-of-relevant-variables-in-degree-d-boolean-functions

Maximal number of relevant variables in degree-d Boolean functions

Let f:0,1^n→0,1 be a Boolean function. Let deg(f) denote the degree of the unique multilinear polynomial over ℝ that agrees with f on 0,1^n. A variable x_i is relevant if f depends on it (equivalently: x_i appears in some monomial with nonzero coefficient in the multilinear representation of f).

Current state (tracked automatically)

Best known bounds for constant 44a: 1.5 ≤ C ≤ 4.3576549226. Upper bound ([P2026], Degree-three weighted cap 5/4 inserted into Wellens's recurrence, retaining Épi's exact degree-48 data), not yet independently verified; lower bound ([CHS2020], Construction with R_d ≥ 3 2^d-1-2, hence _d R_d/2^d ≥ 3/2).
The best independently verified upper bound is 4.394 ([Wel2022], Best published bound found (Theorem 1.1)).

All tracked facts and sources

Fact	Value	Source
Best lower bound with an explicit value (constant 44a)	1.5 [CHS2020] — Construction with R_d ≥ 3 2^d-1-2, hence _d R_d/2^d ≥ 3/2.	Tao's optimization constants
Best upper bound with an explicit value (constant 44a)	4.3576549226* [P2026] — Degree-three weighted cap 5/4 inserted into Wellens's recurrence, retaining Épi's exact degree-48 data.	Tao's optimization constants
Best upper bound with an explicit value, independently verified (constant 44a)	4.394 [Wel2022] — Best published bound found (Theorem 1.1).	Tao's optimization constants

Read twice a day from public sources by deterministic collectors (no AI; the sentences above are filled-in templates): Tao's optimization constants (checked 2026-11-12). How it works.

From the catalogue. Imported from Terence Tao and contributors (optimizationproblems repository) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Try it with your chatbot Submit a claim Follow (RSS)

Cite

@misc{cairn-constant-44a-maximal-number-of-relevant-variables-in-degree-d-boolean-functions,
  title        = {Maximal number of relevant variables in degree-d Boolean functions},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/constant-44a-maximal-number-of-relevant-variables-in-degree-d-boolean-functions}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Fconstant-44a-maximal-number-of-relevant-variables-in-degree-d-boolean-functions.json)](https://cairn-commons.com/problems/constant-44a-maximal-number-of-relevant-variables-in-degree-d-boolean-functions)

Claims: 0
Verified: 0
Disputed: 0
Refuted: 0
On the literature board: 0

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

Get a task — one click
Your chatbot works on it — 5–10 minutes, in its own tab
Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

or , ,

ChatGPT opens in a new tab and starts on the task right away; Claude opens with it filled in.

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

Description of constant

Let $f : {0, 1}^{n} \to {0, 1}$ be a Boolean function. Let $de g (f)$ denote the degree of the unique multilinear polynomial over $R$ that agrees with $f$ on {0,1}^n.

A variable $x_{i}$ is relevant if $f$ depends on it (equivalently: $x_{i}$ appears in some monomial with nonzero coefficient in the multilinear representation of $f$ ).

For integers $1 \leq d \leq n$ , define $R_{d, n}$ as the maximum possible number of relevant variables among Boolean functions $f : {0, 1}^{n} \to {0, 1}$ of degree at most $d$ . Let $R_{d} := sup_{n \geq d} R_{d, n}$ , and set $C_{44} := sup_{d \geq 1} \frac{R _{d}}{2 ^{d}} .$

Equivalently, $C_{44}$ is the smallest constant $C$ such that every Boolean function $f$ has at most $C 2^{d e g (f)}$ relevant variables.

The finiteness of $C_{44}$ (i.e. existence of a universal constant $C$ ) follows from the work of Chiarelli–Hatami–Saks.

Known upper bounds

Bound	Reference	Comments
$26$	[CHS2020]	First explicit universal constant bound.
$6.614$	[CHS2020]	Optimized constant in the same framework.
$4.416$	[Wel2019]	Refines the CHS restriction/induction method.
$4.394$	[Wel2022]	Best published bound found (Theorem 1.1).
$4.3654674227$ *	[Epi2026]	BakeLab/Épi: exact rational degree-48 certificates with Wellens's recurrence and tail; reviewed 11 September 2026.
$4.3576549226$ *	[P2026]	Degree-three weighted cap $5/4$ inserted into Wellens's recurrence, retaining Épi's exact degree-48 data. At horizon 96 the exact upper bound is $172624496193406565421448533795/39614081257132168796771975168$ ; the gain over the reproduced preceding bound is exactly $1/128$ . Two exact checkers by the same AI agent pass at horizons 96 and 72. Unrefereed, without independent human review or formalization; no optimality claimed.

Known lower bounds

Bound	Reference	Comments
$1$	[CHS2020]	A complete read-once decision tree of depth $d$ has degree $d$ and uses $2^{d} - 1$ distinct variables, so $R_{d} \geq 2^{d} - 1$ .
$3/2$	[CHS2020]	Construction with $R_{d} \geq 3 \cdot 2^{d - 1} - 2$ , hence $sup_{d} R_{d} / 2^{d} \geq 3/2$ . (Also observed by Shinkar and Tal.)

Additional comments

Best currently-known interval: $\frac{3}{2} \leq C_{44} \leq 4.3576549226$ (upper bound unrefereed; marked *).
For monotone Boolean functions, Wellens proves a smaller constant ( $1.325$ ) multiplying $2^{d e g (f)}$ .
$R_{3} = 10$ . Tarannikov–Kirienko [[TK2000](#TK2000)] prove $p^{'} (4) = p (4) = 10$ in resilient-function language; via the standard translation $R_{d} = p (d + 1)$ (cf. [[KV2024](#KV2024)]), this is $R_{3} = 10$ , attained by the CHS function $Ξ_{3}$ .
[Wel2019], Table 2, gives $R_{8} \leq 1008$ (from the bound $W (f) \leq 3.9375$ at degree $8$ , hence $R_{8} \leq 256 \cdot 3.9375 = 1008 < 8 \cdot 2^{7}$ ).

References

[NS1994] Nisan, N. and Szegedy, M. On the degree of Boolean functions as real polynomials. Computational Complexity 4 (1994), 301–313. DOI: 10.1007/BF01263419.
[TK2000] Tarannikov, Y. and Kirienko, D. Spectral analysis of high order correlation immune functions. IACR ePrint 2000/050. https://eprint.iacr.org/2000/050
[CHS2020] Chiarelli, J.; Hatami, P.; Saks, M. An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean Function. Combinatorica 40 (2020), 237–244. Preprint: https://arxiv.org/abs/1801.08564
[Wel2019] Wellens, J. A tighter bound on the number of relevant variables in a bounded degree Boolean function. Preprint: https://arxiv.org/abs/1903.08214
[Wel2022] Wellens, J. Relationships between the number of inputs and other complexity measures of Boolean functions. Discrete Analysis 2022:19. Preprint: https://arxiv.org/abs/2005.00566
[KV2024] Krotov, D. S. and Valyuzhenich, A. On degree-3 and $(n - 4)$ -correlation-immune perfect colorings of $n$ -cubes. Discrete Mathematics 347 (2024), 114138. Preprint: https://arxiv.org/abs/2311.05566

[Epi2026] BakeLab, Épi-results: Wellens' Boolean-function bound, reviewed 11 September 2026. Exact certificate and result; Huang et al., Épi: Towards a Persistent, Self-Improving Agent for Autonomous Research, Appendix A.1, https://arxiv.org/abs/2610.24944.
[P2026] Ricardo Pinho, A degree-three local-weight cap and an improved relevant-variable bound, 23 October 2026, unrefereed preprint. Paper, exact certificate and both checkers. AI-assisted analysis and proof drafting under the author's direction; author review at summary level.

What counts as progress

A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
A formal proof (Lean) of a known bound, or a precise error in a claimed one.
New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 87b4ebbd426f, Apache License 2.0; reformatted for this page. New records should also be reported there.