The Dimension Bound for Graph Algebraic Immunity Is Attainable

Abstract

Let the graph algebraic immunity of a Boolean map f:F_2^n -> F_2^m be the least degree of a nonzero reduced Boolean polynomial vanishing on its graph. We prove that the dimension bound, the least d with sum_{j=0}^d binomial(n+m,j)>2^n, is attained for every n,m>=1. Translation invariance gives a rank-density inequality for every subset of the Boolean cube. Rado's classical independent-representative theorem, applied after adjoining dummy vectors, yields a basis using distinct input fibres. Completing those points to a graph proves the result. The proof is self-contained and answers the unrestricted existence question in Oberwolfach Report 31/2007. No balancing, permutation, or additional cryptographic property is imposed. Exact finite certificates accompany the argument. This is an unrefereed preprint using classical matroid tools, with no absolute priority claim.

An attainable Gill-Massar-type bound for spin-factor models
Koichi Yamagata
arXiv19 Sep 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Algebraic Dimension and Reduction of LVMB manifolds
Federico Thiella
arXiv28 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theory Analysis & PDEsarXiv
A dimension-free weak-type (1,1) bound for the vector Riesz transform on ℝⁿ
Yuyuan Ouyang, Daniel Spector, Cody B. Stockdale
arXiv (Cornell University)18 Aug 2026PreprintLicence not statedFull text12 citedGeneral mathematicsOpenAlex
Demazure Models of Algebraic Tori in Dimension 4
Nicole Lemire
arXiv24 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
Chiral Floquet Selection of an Algebraic Rydberg Bound State in the Continuum
X. Z. Zhang, X. F. ZHang, M. W. Liu
arXiv18 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv

Cite

BibTeX RIS

BibTeX

@misc{ferudun2026dimension,
  title = {{The Dimension Bound for Graph Algebraic Immunity Is Attainable}},
  author = {Alper Ferudun},
  howpublished = {Zenodo},
  year = {2026},
  month = oct,
  doi = {10.5281/zenodo.23587039},
  url = {https://zenodo.org/records/23587039},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - The Dimension Bound for Graph Algebraic Immunity Is Attainable
AU  - Alper Ferudun
PY  - 2026
DA  - 2026/10/23
PB  - Zenodo
DO  - 10.5281/zenodo.23587039
UR  - https://zenodo.org/records/23587039
AB  - Let the graph algebraic immunity of a Boolean map f:F_2^n -> F_2^m be the least degree of a nonzero reduced Boolean polynomial vanishing on its graph. We prove that the dimension bound, the least d with sum_{j=0}^d binomial(n+m,j)>2^n, is attained for every n,m>=1. Translation invariance gives a rank-density inequality for every subset of the Boolean cube. Rado's classical independent-representative theorem, applied after adjoining dummy vectors, yields a basis using distinct input fibres. Completing those points to a graph proves the result. The proof is self-contained and answers the unrestricted existence question in Oberwolfach Report 31/2007. No balancing, permutation, or additional cryptographic property is imposed. Exact finite certificates accompany the argument. This is an unrefereed preprint using classical matroid tools, with no absolute priority claim.
ER  -

Abstract

Related

Cite