Inner product mod 2 as the sign of Fib(n + 2) exact threshold gates

Let IPₙ(x, y) = ⊕ᵢ xᵢyᵢ. Amano (LATA 2020) showed that IPₙ has depth-two threshold circuits (THR∘ETHR and THR∘THR) of size O(8^{n/4}) = O(1.682ⁿ), from a representation of IP₄ as the sign of an integer combination of 8 exact threshold functions, and remarked that base cases k ≥ 5 might improve the bound. We give a simple recursion that represents IPₙ, for every n, as the sign of an integer combination of at most Fib(n+2) exact threshold functions (2, 3, 5, 8, 13, 21, …; exactly Fib(n+2) for n ≤ 9). Hence IPₙ has THR∘ETHR and THR∘THR circuits of size O(φⁿ) ⊆ O(1.6181ⁿ), where φ = (1+√5)/2. The top-gate weights are large, so the bound for small top weights (MAJ∘THR) is not improved. The construction was verified by exhaustive evaluation on all inputs for n ≤ 9 (independently re-checked in z-space for n ≤ 10). Ancillary files: t23_fib.py (generator and checker), fib_check_k1-9.jsonl (check output for n ≤ 9), ip6_length21.json (explicit length-21 formula for IP₆). Provenance: the recursion was first found by the language model Claude Opus 5.5 (Anthropic), running without tools; AI agents also performed the independent verification and literature search and helped draft the note. The author checked the proof and is responsible for the content. See the Provenance paragraph and Acknowledgements in the PDF.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-18
DOI
https://doi.org/10.5281/zenodo.24354392
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Inner product mod 2 as the sign of Fib(n + 2) exact threshold gates

Xintian Huang
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

Inner product mod 2 as the sign of Fib(n + 2) exact threshold gates

Xintian Huang
preprint en

Abstract

Let IPₙ(x, y) = ⊕ᵢ xᵢyᵢ. Amano (LATA 2020) showed that IPₙ has depth-two threshold circuits (THR∘ETHR and THR∘THR) of size O(8^{n/4}) = O(1.682ⁿ), from a representation of IP₄ as the sign of an integer combination of 8 exact threshold functions, and remarked that base cases k ≥ 5 might improve the bound. We give a simple recursion that represents IPₙ, for every n, as the sign of an integer combination of at most Fib(n+2) exact threshold functions (2, 3, 5, 8, 13, 21, …; exactly Fib(n+2) for n ≤ 9). Hence IPₙ has THR∘ETHR and THR∘THR circuits of size O(φⁿ) ⊆ O(1.6181ⁿ), where φ = (1+√5)/2. The top-gate weights are large, so the bound for small top weights (MAJ∘THR) is not improved. The construction was verified by exhaustive evaluation on all inputs for n ≤ 9 (independently re-checked in z-space for n ≤ 10). Ancillary files: t23_fib.py (generator and checker), fib_check_k1-9.jsonl (check output for n ≤ 9), ip6_length21.json (explicit length-21 formula for IP₆). Provenance: the recursion was first found by the language model Claude Opus 5.5 (Anthropic), running without tools; AI agents also performed the independent verification and literature search and helped draft the note. The author checked the proof and is responsible for the content. See the Provenance paragraph and Acknowledgements in the PDF.

Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon