OpenFrontiers
Join
← Back to the index
OP-12056OpenComputational complexity

Maximal number of relevant variables in Boolean functions of degree dd (C44C_{44})

Maximal number of relevant variables in Boolean functions of degree dd: determine C44C_{44} or improve its bounds; the repository records 1.5 (lower) and 4.394 (upper).

MSC 06E30 · Boolean functions

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Let

f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}

be a Boolean function. Let deg⁡(f)\deg(f) denote the degree of the unique multilinear polynomial over R\mathbb{R} that agrees with ff on {0,1}^n.

A variable xix_i is relevant if ff depends on it (equivalently: xix_i appears in some monomial with nonzero coefficient in the multilinear representation of ff).

For integers 1≤d≤n1\le d\le n, define Rd,nR_{d,n} as the maximum possible number of relevant variables among Boolean functions

f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}

of degree at most dd. Let Rd:=sup⁡n≥dRd,nR_d := \sup_{n\ge d} R_{d,n}, and set C44:=sup⁡d≥1Rd2d.C_{44} := \sup_{d\ge 1} \frac{R_d}{2^d}.

Equivalently, C44C_{44} is the smallest constant CC such that every Boolean function ff has at most C 2deg⁡(f)C\ 2^{\deg(f)} relevant variables.

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

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

  • Best currently-known interval: 32≤C44≤4.394.\frac{3}{2}\le C_{44}\le 4.394.
  • For monotone Boolean functions, Wellens proves a smaller constant (1.3251.325) multiplying 2deg⁡(f)2^{\deg(f)}.
  • R3=10R_3 = 10. Tarannikov–Kirienko [TK2000] prove p′(4)=p(4)=10p'(4)=p(4)=10 in resilient-function language; via the standard translation Rd=p(d+1)R_d = p(d+1) (cf. [KV2024]), this is R3=10R_3 = 10, attained by the CHS function Ξ3\Xi_3.
  • [Wel2019], Table 2, gives R8≤1008R_8 \le 1008 (from the bound W(f)≤3.9375W(f) \le 3.9375 at degree 88, hence R8≤256⋅3.9375=1008<8⋅27R_8 \le 256 \cdot 3.9375 = 1008 < 8 \cdot 2^7).

References (from the repository page)

  • [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)(n-4)-correlation-immune perfect colorings of nn-cubes. Discrete Mathematics 347 (2024), 114138. Preprint: https://arxiv.org/abs/2311.05566

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 1.5; best known upper bound 4.394. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
2626 [CHS2020] First explicit universal constant bound.
6.6146.614 [CHS2020] Optimized constant in the same framework.
4.4164.416 [Wel2019] Refines the CHS restriction/induction method.
4.3944.394 [Wel2022] Best published bound found (Theorem 1.1).

Known lower bounds

Bound Reference Comments
11 [CHS2020] A complete read-once decision tree of depth dd has degree dd and uses 2d−12^d-1 distinct variables, so Rd≥2d−1R_d\ge 2^d-1.
3/23/2 [CHS2020] Construction with Rd≥3⋅2d−1−2R_d \ge 3\cdot 2^{d-1}-2, hence sup⁡dRd/2d≥3/2\sup_d R_d/2^d \ge 3/2. (Also observed by Shinkar and Tal.)
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Maximal number of relevant variables in Boolean functions of degree $d$ ($C_{44}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.