While checking prior art for a result related to 44a, I found two items in the literature that the page does not record. They may be worth a line in "Additional comments". I extracted every quote below from the source text myself, not from a summary.
Notation as on the page: $R_d$ is the maximum number of relevant variables of a Boolean function of degree $d$, so $C_{44} = \sup_d R_d/2^d$.
1. $R_3 = 10$ has been known since 2000, in resilient-function language
Tarannikov and Kirienko, Spectral analysis of high order correlation immune functions, IACR ePrint 2000/050, Theorem 11:
p'(4)=p(4)=10
Here $p(k)$ is the least integer such that every $(n-k)$-resilient function on $\mathbb{F}_2^n$ depends nonlinearly on at most $p(k)$ variables.
Why this is $R_3$. Put $f' = f\cdot\chi_{[n]}$ (that is, $f$ XOR parity). Then $\widehat{f'}(S) = \widehat{f}([n]\setminus S)$.
- By the Xiao–Massey characterisation, $\deg f \le d$ iff $f'$ is $(n-d-1)$-resilient.
-
$x_i$ is irrelevant for $f$ iff $f'$ depends linearly on $x_i$.
Hence $R_d = p(d+1)$. This is Lemma 1 of Krotov and Valyuzhenich, On degree-3 and (n−4)-correlation-immune perfect colorings of n-cubes, Discrete Math. 347(10) (2024) 114138, arXiv:2311.05566. They state the consequence in degree language: a Boolean function of degree at most 3
cannot have more than 10 essential arguments
and they mention "the unique such function with 10 essential arguments". The CHS function $\Xi_3$ attains 10, so $R_3 = 10$.
Two more results from the same literature:
- Tarannikov, Korolev and Botev, Autocorrelation coefficients and correlation immunity of Boolean functions, ASIACRYPT 2001, LNCS 2248, pp. 460–479, Theorem 6, prove $n \le (k-1)2^{k-2}$. This is exactly the Nisan–Szegedy bound, in resilient form.
- The same paper notes that $(n-k)$-resilient functions depending nonlinearly on all $n = 3\cdot 2^{k-2}-2$ variables exist. That is the $R_d \ge 3\cdot 2^{d-1}-2$ construction, earlier than [CHS2020].
2. [Wel2019], Table 2, gives $R_8 \le 1008$
arXiv:1903.08214, Table 2, bounds $W(f) = \sum_i 2^{-\deg_i f}$ for $d \le 14$.
- At $d = 8$ it gives $3.9375$, so $R_8 \le 256 \cdot 3.9375 = 1008 < 8\cdot 2^7$.
- For $d \le 7$ the table gives $d/2$, which is exactly the Nisan–Szegedy bound.
I re-derived Tables 1 and 2 for $d \le 8$ in exact rational arithmetic, with certificates for every LP verdict, and the values agree.
Disclosure
I am the author of moffatstudio/relevant-variables-degree. It is a preprint, not peer-reviewed, developed with AI assistance. It proves $R_d \le d,2^{d-1}-1$ for every $d \ge 3$, which in view of the above is new only for $4 \le d \le 7$. It also gives a new proof of $R_3 = 10$, with the finite core checked in Lean. An earlier version wrongly presented $R_3 = 10$ as new; that is how I came across this prior art.
I am flagging the prior art here, not asking for our result to be listed. I am happy to open a Markdown-only PR for the comments section if that would help.
While checking prior art for a result related to 44a, I found two items in the literature that the page does not record. They may be worth a line in "Additional comments". I extracted every quote below from the source text myself, not from a summary.
Notation as on the page:$R_d$ is the maximum number of relevant variables of a Boolean function of degree $d$ , so $C_{44} = \sup_d R_d/2^d$ .
1.$R_3 = 10$ has been known since 2000, in resilient-function language
Tarannikov and Kirienko, Spectral analysis of high order correlation immune functions, IACR ePrint 2000/050, Theorem 11:
Here$p(k)$ is the least integer such that every $(n-k)$ -resilient function on $\mathbb{F}_2^n$ depends nonlinearly on at most $p(k)$ variables.
Why this is$R_3$ . Put $f' = f\cdot\chi_{[n]}$ (that is, $f$ XOR parity). Then $\widehat{f'}(S) = \widehat{f}([n]\setminus S)$ .
Hence$R_d = p(d+1)$ . This is Lemma 1 of Krotov and Valyuzhenich, On degree-3 and (n−4)-correlation-immune perfect colorings of n-cubes, Discrete Math. 347(10) (2024) 114138, arXiv:2311.05566. They state the consequence in degree language: a Boolean function of degree at most 3
and they mention "the unique such function with 10 essential arguments". The CHS function$\Xi_3$ attains 10, so $R_3 = 10$ .
Two more results from the same literature:
2. [Wel2019], Table 2, gives$R_8 \le 1008$
arXiv:1903.08214, Table 2, bounds$W(f) = \sum_i 2^{-\deg_i f}$ for $d \le 14$ .
I re-derived Tables 1 and 2 for$d \le 8$ in exact rational arithmetic, with certificates for every LP verdict, and the values agree.
Disclosure
I am the author of moffatstudio/relevant-variables-degree. It is a preprint, not peer-reviewed, developed with AI assistance. It proves$R_d \le d,2^{d-1}-1$ for every $d \ge 3$ , which in view of the above is new only for $4 \le d \le 7$ . It also gives a new proof of $R_3 = 10$ , with the finite core checked in Lean. An earlier version wrongly presented $R_3 = 10$ as new; that is how I came across this prior art.
I am flagging the prior art here, not asking for our result to be listed. I am happy to open a Markdown-only PR for the comments section if that would help.