Optimal Algebraic Immunity of Boolean Functions

Graph algebraic immunity: a full scalar construction and a failed block extension

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

The graph of $f$ is $\{(x,f(x)):x\in\mathbb F_2^n\}$. Its algebraic immunity is the least degree of a nonzero Boolean polynomial in the input and output variables that vanishes on this graph; Boolean polynomials are taken modulo $z_i^2-z_i$.

A Boolean function maps $\{0,1\}^n$ to $\{0,1\}$. A Boolean circuit is an acyclic network of logical gates; a formula is a circuit with no sharing of intermediate gate outputs. Size and depth measure its number of gates and longest gate path.

Statement recorded in the supplied source.

For every $1\leq m\leq n$, there should exist a Boolean function $f:\{0,1\}^n\to\{0,1\}^m$ whose algebraic immunity equals $d^*(n,m)$, the least $d$ such that $\sum_{i=0}^d\binom{n+m}{i}>2^n$. [S2]

Scope qualification.

The vector-valued graph convention should be compared with the source; scalar immunity conventions involving both $f$ and $f+1$ are not substituted.

Source status.

The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Construct vector-valued Boolean functions attaining the stated optimal algebraic-immunity threshold.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30000784 (OWR-1587-003). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Complexity Theory $2008$, Oberwolfach Reports, DOI 10.4171/owr/2007/31, pp. 1793--1864 https://doi.org/10.4171/owr/2007/31.
• S3 Miloserdov, vectorial Boolean functions https://www.mathnet.ru/eng/pdma400. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

For every $1\leq m\leq n$, there should exist a Boolean function $f:\{0,1\}^n\to\{0,1\}^m$ whose algebraic immunity equals $d^*(n,m)$, the least $d$ such that $\sum_{i=0}^d\binom{n+m}{i}>2^n$.

Attempt and results

All polynomials here are over $\mathbb F_2$ modulo $z_i^2-z_i$, so they have unique squarefree representatives. The immunity is that of the graph, not the scalar annihilator convention often used elsewhere. We prove the scalar majority case and test a natural attempt to combine it into several outputs. The report already gives scalar constructions; no novelty or advance on the full multi-output conjecture is claimed.

Dimension gives the stated upper bound.

The squarefree monomials of degree at most $d$ in $n+m$ variables form a basis of dimension $D_d=\sum_{i=0}^d\binom{n+m}{i}$. To see independence as functions on the Boolean cube, if $\sum_A c_A\prod_{i\in A}z_i$ vanishes everywhere, evaluate at indicator vectors of subsets in increasing cardinality. The empty evaluation first gives $c_\varnothing=0$, and evaluation at a subset $S$ then gives $c_S=0$ after all proper-subset coefficients have vanished. Thus all coefficients vanish. Evaluation on the $2^n$ graph points is a linear map to a $2^n$-dimensional space. If $D_d>2^n$, it has a nontrivial kernel, giving a nonzero graph annihilator. Hence immunity is at most $d^*(n,m)$ exactly as defined.

A useful low-weight interpolation lemma.

If a squarefree polynomial $A(x)$ of degree at most $k$ vanishes on every Boolean point of Hamming weight at most $k$, then $A=0$. The same induction on subsets used above determines every coefficient of degree at most $k$; there are no other coefficients. Substitution $x_i\mapsto1-z_i$ cannot increase degree, so vanishing on all points with at most $k$ zero coordinates has the same consequence for a degree-at-most-$k$ polynomial.

The scalar construction in every input dimension.

Put $k=\lfloor n/2\rfloor$ and define $f(x)=1$ exactly when $\operatorname{wt}(x)>k$. Suppose a graph annihilator $P(x,y)$ has degree at most $k$. Because $y^2=y$, it is uniquely $A(x)+yB(x)$ with $\deg A\le k$ and $\deg B\le k-1$ (take $B=0$ when $k=0$). On points of weight at most $k$, $f=0$, so $A=0$ by the lemma. On points of weight at least $k+1$, it follows that $B=0$. If $n=2k$, those points become all points of weight at most $k-1$ after complementing the coordinates; if $n=2k+1$, they become all points of weight at most $k$, which includes the needed weight-at-most-$k-1$ set. The lemma applied to $B(1-z)$ yields $B=0$. Thus there is no nonzero graph annihilator of degree at most $k$, and immunity is at least $k+1$. For $n=2k$, symmetry of binomial coefficients in odd dimension $2k+1$ gives $\sum_{i=0}^k\binom{2k+1}{i}=2^{2k}$, so $d^*=k+1$. For $n=2k+1$, the sum through $k$ in dimension $2k+2$ is strictly below half the total, and adding the positive central coefficient makes it strictly above half. Hence again $d^*=k+1$. The upper bound therefore proves equality for the scalar construction, including $n=1$.

A direct-sum route to multiple outputs fails.

Take $n=8,m=2$, and define $f_1$ as strict majority on $x_1,\ldots,x_4$, and $f_2$ as strict majority on $x_5,\ldots,x_8$. Each separate four-input scalar function has optimal graph immunity three, as proved above. But the two-output graph has the nonzero annihilator \[ P(x,y_1,y_2)=y_1(1+x_1)(1+x_2), \] of degree three. If $y_1=0$ it vanishes; if $y_1=1$, at least three of the first four inputs equal one, so $x_1,x_2$ cannot both be zero and the product again vanishes. On the other hand $\sum_{i=0}^3\binom{10}{i}=176\le256$ and $\sum_{i=0}^4\binom{10}{i}=386>256$, so $d^*(8,2)=4$. Thus combining optimal independent scalar blocks is not a proof of optimal multi-output immunity. Copying the same scalar output would be even worse, since $y_1+y_2$ is then a nonzero degree-one annihilator.

Source context, finite checks, adversarial audit, and gap

The report's graph convention and exact threshold were inspected on printed page 1838. The source discusses already known scalar cases; the argument here is a direct proof under the preserved graph convention, without relying on an asserted external construction. Exact binary elimination in the accompanying script verified full column rank below $d^*$ for majority graphs at $n=1,\ldots,8$, and evaluated the displayed block annihilator at all 256 input points. All checks passed; they do not establish a general existence result. The audit checked squarefree uniqueness, even/odd cutoffs, $n=1$, and the block counterexample's exact target value. No construction for every $1<m\le n$ or full proof of the source conjecture is supplied.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. The complete known scalar construction and a counterexample to naive block composition leave the general multi-output existence conjecture unresolved.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Oberwolfach Report 31/2007, relevant contributions by Koiran (pp.1835--1836) and Krause (pp.1838--1839); primary cached report passages inspected. Historical status and external literature are not independently updated here. https://ems.press/content/serial-article-files/46116.

Final status

Unresolved in this attempt. The complete known scalar construction and a counterexample to naive block composition leave the general multi-output existence conjecture unresolved.