The Boolean Power of ReLU

# The Boolean Power of ReLU
Source: [https://arxiv.org/html/2608.12617](https://arxiv.org/html/2608.12617)
ChileFloris Geerts floris\.geerts@uantwerp\.be University of Antwerp BelgiumMatthias Lanzinger matthias\.lanzinger@tuwien\.ac\.at TU Wien AustriaKlara Pakhomenko klara\.pakhomenko@uhasselt\.be Universiteit Hasselt BelgiumJan Van den Bussche jan\.vandenbussche@uhasselt\.be Universiteit Hasselt Belgium

###### Abstract

We prove that, on finite simple undirected graphs equipped with a single Boolean node feature, the Boolean queries expressible inΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}, for*any*collectionΣ\\Sigmaof eventually constant activation functions and with arbitrary real coefficients, form a strict subclass of the Boolean queries expressible inReLU​\-​MPLang\\mathrm\{ReLU\}\\text\{\-\}\\mathrm\{MPLang\}\. We thereby settle a recently posed open problem: whetherReLU​\-​MPLang\\mathrm\{ReLU\}\\text\{\-\}\\mathrm\{MPLang\}is more powerful thanTrReLU​\-​MPLang\\mathrm\{TrReLU\}\\text\{\-\}\\mathrm\{MPLang\}when it comes to Boolean queries\. In particular, this implies thatReLU\\mathrm\{ReLU\}\-GNNs are strictly more expressive than\{TrReLU,id\}\\\{\\mathrm\{TrReLU\},\\mathrm\{id\}\\\}\-GNNs with respect to Boolean queries on Boolean\-featured graphs\.

## 1Introduction

Graph neural networks \(GNNs\) compute node embeddings by repeatedly combining a node’s current features with aggregated features from its neighbours, followed by a pointwise activation function\.Σ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}\(for*Σ\\Sigma\-Message\-Passing Language*\) provides a small declarative language for precisely this computation: its expressions are built from node features, affine combinations, neighbourhood aggregation, and activations from a setΣ\\Sigma\. This makesΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}a convenient formalism for isolating how architectural choices affect GNN expressivity\. In particular,Σ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}has the same expressive power as GNNs whose layers may use eitherσ∈Σ\\sigma\\in\\Sigmaor the identity activation \(i\.e\., a skip layer that passes a node’s incoming value through unchanged\), whileReLU​\-​MPLang\\mathrm\{ReLU\}\\text\{\-\}\\mathrm\{MPLang\}captures ReLU\-GNNs\([Geerts\_2022](https://arxiv.org/html/2608.12617#bib.bib3)\)\. Recent work showed that the unbounded ReLU is strictly more expressive than the bounded truncated ReLU for*numerical*queries, but left open whether this advantage survives Booleanisation, where the numerical output at a node is thresholded to obtain a Boolean query\([Barcelo\+2026](https://arxiv.org/html/2608.12617#bib.bib1)\)\. This does not follow from numerical separation: two languages may compute different real\-valued embeddings while still defining exactly the same Boolean queries\. Nor is the question settled by the Boolean separation result by Benedikt, Lu and Tan[benedikt2025decidabilitygraphneuralnetworks](https://arxiv.org/html/2608.12617#bib.bib2), since that result concerns GNNs without the identity layers implicit inΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}\. Because such linear layers can themselves increase expressive power, it remained possible that they eliminate the Boolean gap between truncated ReLU and ReLU\. We show that they do not\. Already on finite simple undirected graphs equipped with a single Boolean node feature,

bool⁡\(TrReLU​\-​MPLang\)⊊bool⁡\(ReLU​\-​MPLang\),\\mathrm\{bool\}\\bigl\(\\mathrm\{TrReLU\}\\text\{\-\}\\mathrm\{MPLang\}\\bigr\)\\subsetneq\\mathrm\{bool\}\\bigl\(\\mathrm\{ReLU\}\\text\{\-\}\\mathrm\{MPLang\}\\bigr\),wherebool⁡\(⋅\)\\mathrm\{bool\}\(\\cdot\)denotes Booleanisation\. More generally, we exhibit a Boolean ReLU query that is not definable inΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}for any collectionΣ\\Sigmaof eventually constant activation functions, even with arbitrary real coefficients\. Thus, the unboundedness of ReLU affects not only the numerical values of graph embeddings, but also the node properties that message\-passing GNNs can recognise after thresholding\.

Tool and computational resource disclosure

Generative AI tools were used during the development and preparation of this manuscript\. In particular, ChatGPT 5\.6 Sol \(Pro\) was used to explore proof strategies and generated the proof of the final result from a single prompt\. Claude Fable 5 and the authors subsequently checked, revised where necessary, and independently verified the argument before including it in the manuscript\.

ChatGPT and Claude were also used for language editing, improving exposition, and assisting withLaTeXpreparation\. All mathematical claims, proofs, citations, and conclusions appearing in the final manuscript have been reviewed and validated by the authors, who take full responsibility for the content and correctness of the paper\.

## 2Preliminaries

A*graph*G=\(V,E\)G=\(V,E\)is finite, simple and undirected:VVis a finite set andE⊆\{\{u,v\}:u,v∈V,u≠v\}E\\subseteq\\bigl\\\{\\\{u,v\\\}:u,v\\in V,\\ u\\neq v\\bigr\\\}\. We writeNG​\(v\)≔\{u:\{u,v\}∈E\}N\_\{G\}\(v\)\\coloneqq\\bigl\\\{u:\\\{u,v\\\}\\in E\\bigr\\\}anddegG⁡\(v\)≔\|NG​\(v\)\|\\deg\_\{G\}\(v\)\\coloneqq\|N\_\{G\}\(v\)\|, omitting the subscript whenGGis clear from the context\. Ford\>0d\>0, a*dd\-embedding*ofGGis a mapγ:V→ℝd\\gamma:V\\to\\mathbb\{R\}^\{d\}; the pair\(G,γ\)\(G,\\gamma\)is a*dd\-embedded graph*\. A*Boolean\-featured graph*is add\-embedded graph withγ⁡\(V\)⊆\{0,1\}d\\gamma\(V\)\\subseteq\\\{0,1\\\}^\{d\}\. Throughout, the separating graphs use only one Boolean node feature, denoted byPP\. Thus the separation already holds in the minimal settingd=1d=1\.

Fix a setΣ\\Sigmaof functionsσ:ℝ→ℝ\\sigma:\\mathbb\{R\}\\to\\mathbb\{R\}, called*activation functions*\. The languageΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}overdd\-embeddings is generated by the grammar

e⩴1\|Pi​∣a​e​∣e\+e∣◇\+

e∣​σ​\(e\),i∈\[d\],σ∈Σ,a∈ℝ\.e\\ \\Coloneqq\\ 1\\ \\mid\\ P\_\{i\}\\ \\mid\\ ae\\ \\mid\\ e\+e\\ \\mid\\ \\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}e\\ \\mid\\ \\sigma\(e\),\\qquad i\\in\[d\],\\ \\sigma\\in\\Sigma,\\ a\\in\\mathbb\{R\}\.The semantics on add\-embedded graph\(G,γ\)\(G,\\gamma\)assigns to each expressioneeand each nodevva real numbere​\(G,γ\)​\(v\)e\(G,\\gamma\)\(v\), as follows:

1​\(G,γ\)​\(v\)\\displaystyle 1\(G,\\gamma\)\(v\)≔1,\\displaystyle\\coloneqq 1,Pi​\(G,γ\)​\(v\)\\displaystyle P\_\{i\}\(G,\\gamma\)\(v\)≔γ​\(v\)i,\\displaystyle\\coloneqq\\gamma\(v\)\_\{i\},\(a​e\)​\(G,γ\)​\(v\)\\displaystyle\(ae\)\(G,\\gamma\)\(v\)≔a⋅e​\(G,γ\)​\(v\),\\displaystyle\\coloneqq a\\cdot e\(G,\\gamma\)\(v\),\(e1\+e2\)​\(G,γ\)​\(v\)\\displaystyle\(e\_\{1\}\+e\_\{2\}\)\(G,\\gamma\)\(v\)≔e1​\(G,γ\)​\(v\)\+e2​\(G,γ\)​\(v\),\\displaystyle\\coloneqq e\_\{1\}\(G,\\gamma\)\(v\)\+e\_\{2\}\(G,\\gamma\)\(v\),\(◇\+e\)\(G,γ\)\(v\)\\displaystyle\(\\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}e\)\(G,\\gamma\)\(v\)≔∑u∈N⁡\(v\)e⁡\(G,γ\)​\(u\),\\displaystyle\\coloneqq\\textstyle\\sum\_\{u\\in N\(v\)\}e\(G,\\gamma\)\(u\),σ​\(e\)​\(G,γ\)​\(v\)\\displaystyle\\sigma\(e\)\(G,\\gamma\)\(v\)≔σ​\(e​\(G,γ\)​\(v\)\)\.\\displaystyle\\coloneqq\\sigma\\bigl\(e\(G,\\gamma\)\(v\)\\bigr\)\.We freely use the abbreviationse1−e2≔e1\+\(−1\)​e2e\_\{1\}\-e\_\{2\}\\coloneqq e\_\{1\}\+\(\-1\)e\_\{2\}andm≔m⋅1m\\coloneqq m\\cdot 1for integer constants, and we note that the identity activation is implicit in the grammar: linear terms need not pass through anyσ\\sigma\. Throughout we use

ReLU⁡\(x\)≔max⁡\{0,x\},TrReLU⁡\(x\)≔min⁡\{1,max⁡\{0,x\}\},bool⁡\(x\)≔\{1,x\>0,0,x≤0,\\mathrm\{ReLU\}\(x\)\\coloneqq\\max\\\{0,x\\\},\\qquad\\mathrm\{TrReLU\}\(x\)\\coloneqq\\min\\\{1,\\max\\\{0,x\\\}\\\},\\qquad\\mathrm\{bool\}\(x\)\\coloneqq\\begin\{cases\}1,&x\>0,\\\\ 0,&x\\leq 0,\\end\{cases\}for the ReLU, truncated ReLU, and unit\-step \(Booleanisation\) activations, respectively\. We also usesgn⁡\(x\)=\+1\\mathrm\{sgn\}\(x\)=\+1ifx\>0x\>0,sgn⁡\(x\)=0\\mathrm\{sgn\}\(x\)=0ifx=0x=0, andsgn⁡\(x\)=−1\\mathrm\{sgn\}\(x\)=\-1ifx<0x<0\. For a single activation functionσ\\sigma, we writeσ​\-​MPLang\\sigma\\text\{\-\}\\mathrm\{MPLang\}for\{σ\}​\-​MPLang\\\{\\sigma\\\}\\text\{\-\}\\mathrm\{MPLang\}; in particularReLU​\-​MPLang:=\{ReLU\}​\-​MPLang\\mathrm\{ReLU\}\\text\{\-\}\\mathrm\{MPLang\}:=\\\{\\mathrm\{ReLU\}\\\}\\text\{\-\}\\mathrm\{MPLang\}andTrReLU​\-​MPLang:=\{TrReLU\}​\-​MPLang\\mathrm\{TrReLU\}\\text\{\-\}\\mathrm\{MPLang\}:=\\\{\\mathrm\{TrReLU\}\\\}\\text\{\-\}\\mathrm\{MPLang\}\.

###### Definition 2\.1\(Booleanisation of a query\)\.

For an expressionee, its*Booleanisation*e𝔹e\_\{\\mathbb\{B\}\}is the Boolean query

e𝔹​\(G,γ\)​\(v\)≔\{1,if​e​\(G,γ\)​\(v\)\>0,0,otherwise\.e\_\{\\mathbb\{B\}\}\(G,\\gamma\)\(v\)\\coloneqq\\begin\{cases\}1,&\\text\{if \}e\(G,\\gamma\)\(v\)\>0,\\\\ 0,&\\text\{otherwise\.\}\\end\{cases\}Expressionse,e′e,e^\{\\prime\}are*numerically equivalent*on a class𝒞\\mathcal\{C\}of embedded graphs ife⁡\(G,γ\)=e′​\(G,γ\)e\(G,\\gamma\)=e^\{\\prime\}\(G,\\gamma\)for all\(G,γ\)∈𝒞\(G,\\gamma\)\\in\\mathcal\{C\}, and*Boolean equivalent*on𝒞\\mathcal\{C\}ife𝔹​\(G,γ\)=e𝔹′​\(G,γ\)e\_\{\\mathbb\{B\}\}\(G,\\gamma\)=e^\{\\prime\}\_\{\\mathbb\{B\}\}\(G,\\gamma\)for all\(G,γ\)∈𝒞\(G,\\gamma\)\\in\\mathcal\{C\}\. For a languageLLwe writebool⁡\(L\)≔\{e𝔹:e∈L\}\\mathrm\{bool\}\(L\)\\coloneqq\\\{e\_\{\\mathbb\{B\}\}:e\\in L\\\}for its class of Boolean queries\.

###### Definition 2\.2\(Eventually constant functions\)\.

A functionσ:ℝ→ℝ\\sigma:\\mathbb\{R\}\\to\\mathbb\{R\}is*eventually constant*if there exist realsx−σ≤x\+σx^\{\\sigma\}\_\{\-\}\\leq x^\{\\sigma\}\_\{\+\}and constantsC−σ,C\+σ∈ℝC^\{\\sigma\}\_\{\-\},C^\{\\sigma\}\_\{\+\}\\in\\mathbb\{R\}such thatσ⁡\(x\)=C−σ\\sigma\(x\)=C^\{\\sigma\}\_\{\-\}for allx≤x−σx\\leq x^\{\\sigma\}\_\{\-\}andσ⁡\(x\)=C\+σ\\sigma\(x\)=C^\{\\sigma\}\_\{\+\}for allx≥x\+σx\\geq x^\{\\sigma\}\_\{\+\}\.

For instance,TrReLU\\mathrm\{TrReLU\},bool\\mathrm\{bool\},sgn\\mathrm\{sgn\}, the hard sigmoid and the hard tanh are eventually constant, whereasReLU\\mathrm\{ReLU\}andid\\mathrm\{id\}are not\.

## 3The main theorem

We first recall thatTrReLU​\-​MPLang\\mathrm\{TrReLU\}\\text\{\-\}\\mathrm\{MPLang\}is subsumed byReLU​\-​MPLang\\mathrm\{ReLU\}\\text\{\-\}\\mathrm\{MPLang\}\([Barcelo\+2026](https://arxiv.org/html/2608.12617#bib.bib1)\)\.

###### Proposition 3\.1\.

EveryTrReLU​\-​MPLang\\mathrm\{TrReLU\}\\text\{\-\}\\mathrm\{MPLang\}expression is numerically equivalent, on all embedded graphs, to aReLU​\-​MPLang\\mathrm\{ReLU\}\\text\{\-\}\\mathrm\{MPLang\}expression\. Consequently,

bool⁡\(TrReLU​\-​MPLang\)⊆bool⁡\(ReLU​\-​MPLang\)\.\\mathrm\{bool\}\(\\mathrm\{TrReLU\}\\text\{\-\}\\mathrm\{MPLang\}\)\\subseteq\\mathrm\{bool\}\(\\mathrm\{ReLU\}\\text\{\-\}\\mathrm\{MPLang\}\)\.

###### Proof\.

For allx∈ℝx\\in\\mathbb\{R\}we haveTrReLU⁡\(x\)=ReLU⁡\(x\)−ReLU⁡\(x−1\)\\mathrm\{TrReLU\}\(x\)=\\mathrm\{ReLU\}\(x\)\-\\mathrm\{ReLU\}\(x\-1\)\. Define a translationTTthat recursively replaces every subexpression of the formTrReLU⁡\(e\)\\mathrm\{TrReLU\}\(e\)byReLU⁡\(T⁡\(e\)\)−ReLU⁡\(T⁡\(e\)−1\)\\mathrm\{ReLU\}\(T\(e\)\)\-\\mathrm\{ReLU\}\(T\(e\)\-1\)and commutes with all other constructors\. A straightforward structural induction shows thatT⁡\(e\)T\(e\)is numerically equivalent toeeon every embedded graph, and numerical equivalence implies Boolean equivalence\. ∎

Our main result is, as follows\.

###### Theorem 3\.2\(Main theorem\)\.

LetΣ\\Sigmabe any collection of eventually constant activation functions\. There exists aReLU​\-​MPLang\\mathrm\{ReLU\}\\text\{\-\}\\mathrm\{MPLang\}expressionE⋆E\_\{\\star\}such that noΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}expression \(with arbitrary real coefficients\) is Boolean equivalent to it on the class of finite graphs with a single Boolean feature\.

As a corollary, we resolve the problem left open in our previous work[Barcelo\+2026](https://arxiv.org/html/2608.12617#bib.bib1):

###### Corollary 3\.3\.

On finite Boolean\-featured graphs,

bool⁡\(TrReLU​\-​MPLang\)⊊bool⁡\(ReLU​\-​MPLang\),\\mathrm\{bool\}\\bigl\(\\mathrm\{TrReLU\}\\text\{\-\}\\mathrm\{MPLang\}\\bigr\)\\ \\subsetneq\\ \\mathrm\{bool\}\\bigl\(\\mathrm\{ReLU\}\\text\{\-\}\\mathrm\{MPLang\}\\bigr\),and this holds already on graphs with a single Boolean feature\.

###### Proof\.

The containmentbool⁡\(TrReLU​\-​MPLang\)⊆bool⁡\(ReLU​\-​MPLang\)\\mathrm\{bool\}\(\\mathrm\{TrReLU\}\\text\{\-\}\\mathrm\{MPLang\}\)\\subseteq\\mathrm\{bool\}\(\\mathrm\{ReLU\}\\text\{\-\}\\mathrm\{MPLang\}\)is Proposition[3\.1](https://arxiv.org/html/2608.12617#S3.Thmtheorem1); strictness follows from Theorem[3\.2](https://arxiv.org/html/2608.12617#S3.Thmtheorem2)withΣ=\{TrReLU\}\\Sigma=\\\{\\mathrm\{TrReLU\}\\\}, applied to the Boolean query\(E⋆\)𝔹∈bool⁡\(ReLU​\-​MPLang\)\(E\_\{\\star\}\)\_\{\\mathbb\{B\}\}\\in\\mathrm\{bool\}\(\\mathrm\{ReLU\}\\text\{\-\}\\mathrm\{MPLang\}\)\. ∎

### Proof strategy\.

Define theReLU​\-​MPLang\\mathrm\{ReLU\}\\text\{\-\}\\mathrm\{MPLang\}expression \(over one Boolean featurePP\)

E⋆≔◇\+

ReLU\(2◇\+

P−◇\+

1\+1\)−◇\+

1\+4\\boxed\{\\ E\_\{\\star\}\\ \\coloneqq\\ \\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}\\mathrm\{ReLU\}\\bigl\(2\\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}P\-\\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}1\+1\\bigr\)\\ \-\\ \\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}1\\ \+\\ 4\\ \}\(1\)Unravelling the semantics, its Booleanisation tests, at a nodevv,

\(E⋆\)𝔹​\(G\)​\(v\)=1⇔\\displaystyle\(E\_\{\\star\}\)\_\{\\mathbb\{B\}\}\(G\)\(v\)=1\\iff\{\}∑w∈N⁡\(v\)max⁡\{0,2​\#​\{x∈N⁡\(w\):P⁡\(x\)=1\}−deg⁡\(w\)\+1\}\\displaystyle\\sum\_\{w\\in N\(v\)\}\\max\\Bigl\\\{0,\\ 2\\,\\\#\\\{x\\in N\(w\):P\(x\)=1\\\}\-\\deg\(w\)\+1\\Bigr\\\}\(2\)−deg⁡\(v\)\+4\>0\.\\displaystyle\}\{\\displaystyle\-\\deg\(v\)\+4\>0\.We evaluate expressions on a three\-parameter family of graphsGN​\(u1,u2,α\)G\_\{N\}\(u\_\{1\},u\_\{2\},\\alpha\), whose nodes fall into classes that are indistinguishable toΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}expressions\. On one distinguished node class, denotedOO, the expressionE⋆E\_\{\\star\}takes the value2​N​\(u1\+u2−α\)2N\(u\_\{1\}\+u\_\{2\}\-\\alpha\)and thus detects on which side of the planeu1\+u2=αu\_\{1\}\+u\_\{2\}=\\alphathe parameters lie\. By contrast, we show that every expression built from eventually constant activations becomes*asymptotically local*: for all sufficiently large admissibleNN, its value onOOdepends only onNNandα\\alpha, not onu1u\_\{1\}oru2u\_\{2\}\. Choosing two nearby rational parameter points with the sameα\\alphabut lying on opposite sides of the planeu1\+u2=αu\_\{1\}\+u\_\{2\}=\\alphayields two graphs on which any candidate expression takes the same value atOO, whereasE⋆E\_\{\\star\}takes values of opposite sign\.

a0a\_\{0\}b0b\_\{0\}a1a\_\{1\}b1b\_\{1\}a2a\_\{2\}b2b\_\{2\}a3a\_\{3\}b3b\_\{3\}a4a\_\{4\}b4b\_\{4\}Figure 1:The regular gadget of Lemma[4\.1](https://arxiv.org/html/2608.12617#S4.Thmtheorem1)forn=5n=5,d=2d=2\.

## 4The graph family

We now construct the graph family\. LetΘ≔\(14,13\)2×\(12,23\)\\Theta\\coloneqq\\bigl\(\\tfrac\{1\}\{4\},\\tfrac\{1\}\{3\}\\bigr\)^\{2\}\\times\\bigl\(\\tfrac\{1\}\{2\},\\tfrac\{2\}\{3\}\\bigr\)and considerθ=\(u1,u2,α\)∈Θ\\theta=\(u\_\{1\},u\_\{2\},\\alpha\)\\in\\Theta\. For rationalθ∈Θ\\theta\\in\\Theta, we say an integerN≥1N\\geq 1is*θ\\theta\-admissible*ifN​u1Nu\_\{1\},N​u2Nu\_\{2\}and2​N​α2N\\alphaare integers; theθ\\theta\-admissibleNNare exactly the positive multiples of the least common denominator ofu1u\_\{1\},u2u\_\{2\}and2​α2\\alpha\. Put

ri=N⁡\(1\+ui\),bi=N⁡\(1−ui\),t=2​N​α\.r\_\{i\}=N\(1\+u\_\{i\}\),\\qquad b\_\{i\}=N\(1\-u\_\{i\}\),\\qquad t=2N\\alpha\.\(3\)Then

0<bi<N<ri<2​N,N<t<2​N,ri\+bi=2​N,ri−bi=2​N​ui\.0<b\_\{i\}<N<r\_\{i\}<2N,\\qquad N<t<2N,\\qquad r\_\{i\}\+b\_\{i\}=2N,\\qquad r\_\{i\}\-b\_\{i\}=2Nu\_\{i\}\.\(4\)
###### Lemma 4\.1\(Regular gadgets\)\.

LetA,BA,Bbe disjointnn\-element sets\.

1. 1\.For every0≤d≤n0\\leq d\\leq n, there is a simpledd\-regular bipartite graph betweenAAandBB\.
2. 2\.Ifnnis even, then for every0≤d<n0\\leq d<nthere is a simpledd\-regular graph onAA\.

###### Proof\.

Identify each set withℤn\\mathbb\{Z\}\_\{n\}\. For \(1\), joinj∈Aj\\in Atoj,j\+1,…,j\+d−1∈Bj,j\+1,\\ldots,j\+d\-1\\in B\(indices modnn\); each vertex on either side gets exactlydddistinct neighbours sinced≤nd\\leq n\. \(See Figure[1](https://arxiv.org/html/2608.12617#S3.F1)\.\) For \(2\), ifddis even, join eachj∈Aj\\in Atoj±1,…,j±d/2j\\pm 1,\\ldots,j\\pm d/2\(modnn\); this is a simpledd\-regular graph sinced/2<n/2d/2<n/2, so no two of theseddneighbours coincide andjjis not joined to itself\. Ifddis odd, use the same construction ford−1d\-1and add the antipodal matching\{j,j\+n/2\}\\\{j,j\+n/2\\\}\(modnn\), which requiresnneven to be a well\-defined fixed\-point\-free involution, and is disjoint from the edges already added sincen/2n/2is not among±1,…,±\(d−1\)/2\\pm 1,\\dots,\\pm\(d\-1\)/2onced<nd<n\. ∎

Fix a rationalθ∈Θ\\theta\\in\\Thetaand aθ\\theta\-admissibleNN\. Take five disjoint classes, each of size2​N2N,

O,W1\+,W1−,W2\+,W2−\.O,\\quad W\_\{1\}^\{\+\},W\_\{1\}^\{\-\},\\quad W\_\{2\}^\{\+\},W\_\{2\}^\{\-\}\.Using Lemma[4\.1](https://arxiv.org/html/2608.12617#S4.Thmtheorem1), place att\-regular graph insideOO, anrir\_\{i\}\-regular graph inside eachWi±W\_\{i\}^\{\\pm\}, abib\_\{i\}\-regular bipartite gadget betweenWi\+W\_\{i\}^\{\+\}andWi−W\_\{i\}^\{\-\}, and a perfect matching betweenOOand eachWi±W\_\{i\}^\{\\pm\}\. Add no other edges, and set the Boolean node feature to

P=1​on​W1\+∪W2\+,P=0​elsewhere\.P=1\\text\{ on \}W\_\{1\}^\{\+\}\\cup W\_\{2\}^\{\+\},\\qquad P=0\\text\{ elsewhere\}\.Call the resulting Boolean\-featured graphGN​\(u1,u2,α\)G\_\{N\}\(u\_\{1\},u\_\{2\},\\alpha\), orGN​\(θ\)G\_\{N\}\(\\theta\)for short; it is depicted in Figure[2](https://arxiv.org/html/2608.12617#S4.F2)\. ThusGN​\(θ\)G\_\{N\}\(\\theta\)includes not only the underlying graph, but also the feature mapγ:V→\{0,1\}\\gamma:V\\to\\\{0,1\\\}given byγ⁡\(v\)=P⁡\(v\)\\gamma\(v\)=P\(v\)\. Accordingly, for aΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}expressionhhand a nodevv, we writeh​\(GN​\(θ\)\)​\(v\)h\(G\_\{N\}\(\\theta\)\)\(v\)for the value ofhhatvv, rather thanh⁡\(GN​\(θ\),γ\)​\(v\)h\(G\_\{N\}\(\\theta\),\\gamma\)\(v\)\.

OOW1\+W\_\{1\}^\{\+\}W1−W\_\{1\}^\{\-\}W2\+W\_\{2\}^\{\+\}W2−W\_\{2\}^\{\-\}11111111b1b\_\{1\}b2b\_\{2\}ttr1r\_\{1\}r1r\_\{1\}r2r\_\{2\}r2r\_\{2\}Figure 2:A depiction of the graphGN​\(u1,u2,α\)G\_\{N\}\(u\_\{1\},u\_\{2\},\\alpha\)\. A loop labelleddddenotes add\-regular graph inside the class; an edge labelleddddenotes add\-regular bipartite gadget\. Shaded classes carryP=1P=1\. Recall thatri=N⁡\(1\+ui\)r\_\{i\}=N\(1\+u\_\{i\}\),bi=N⁡\(1−ui\)b\_\{i\}=N\(1\-u\_\{i\}\), andt=2​N​αt=2N\\alpha\.
## 5Evaluation of the separating expression on the graph family

We now evaluate the separating expressionE⋆E\_\{\\star\}on the graphsGN​\(θ\)G\_\{N\}\(\\theta\)\. The key observation is that any two nodes in the same class are interchangeable as far asΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}expressions are concerned\.

###### Lemma 5\.1\.

For everyΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}expressionhh, the maph​\(GN​\(θ\)\)​\(⋅\)h\(G\_\{N\}\(\\theta\)\)\(\\cdot\)is constant on each of the five classes\.

###### Proof\.

Recall that a partition𝒞\\mathcal\{C\}of the vertex set of a graph is*equitable*if, for every two classesX,Y∈𝒞X,Y\\in\\mathcal\{C\}, there is a numberdX​Yd\_\{XY\}such that every vertex inXXhas exactlydX​Yd\_\{XY\}neighbours inYY\. Note that the coarsest equitable partition of a graph corresponds to the partition resulting from running colour refinement on the graph\([grohe2014dimension](https://arxiv.org/html/2608.12617#bib.bib4)\)\. The partition𝒞=\{O,W1\+,W1−,W2\+,W2−\}\\mathcal\{C\}=\\\{O,W\_\{1\}^\{\+\},W\_\{1\}^\{\-\},W\_\{2\}^\{\+\},W\_\{2\}^\{\-\}\\\}is equitable: with the classes ordered asO,W1\+,W1−,W2\+,W2−O,\\ W\_\{1\}^\{\+\},\\ W\_\{1\}^\{\-\},\\ W\_\{2\}^\{\+\},\\ W\_\{2\}^\{\-\}, the inter\-class neighbour countsdX​Yd\_\{XY\}are given by the quotient matrix

D=\(dX​Y\)X,Y∈𝒞=\(t11111r1b1001b1r100100r2b2100b2r2\)\.D=\(d\_\{XY\}\)\_\{X,Y\\in\\mathcal\{C\}\}=\\begin\{pmatrix\}t&1&1&1&1\\\\ 1&r\_\{1\}&b\_\{1\}&0&0\\\\ 1&b\_\{1\}&r\_\{1\}&0&0\\\\ 1&0&0&r\_\{2\}&b\_\{2\}\\\\ 1&0&0&b\_\{2\}&r\_\{2\}\\end\{pmatrix\}\.Indeed, every vertex inOOhasttneighbours inOOand one neighbour in each of the four classesWi±W\_\{i\}^\{\\pm\}, while every vertex inWi\+W\_\{i\}^\{\+\}has one neighbour inOO,rir\_\{i\}neighbours inWi\+W\_\{i\}^\{\+\}, andbib\_\{i\}neighbours inWi−W\_\{i\}^\{\-\}; the description forWi−W\_\{i\}^\{\-\}is symmetric\. In particular,

deg⁡\(v\)=t\+4​for​v∈O,deg⁡\(v\)=ri\+bi\+1=2​N\+1​for​v∈Wi±\.\\deg\(v\)=t\+4\\ \\text\{ for \}v\\in O,\\qquad\\deg\(v\)=r\_\{i\}\+b\_\{i\}\+1=2N\+1\\ \\text\{ for \}v\\in W\_\{i\}^\{\\pm\}\.\(5\)We prove the claim by structural induction onhh\.*Base cases\.*The expression11has value11at every vertex, andPPis constant on each class by construction: it has value11onW1\+W\_\{1\}^\{\+\}andW2\+W\_\{2\}^\{\+\}, and value00on the other three classes\.*Linear and activation cases\.*Ifh1h\_\{1\}andh2h\_\{2\}are constant on every class, then so area​h1ah\_\{1\},h1\+h2h\_\{1\}\+h\_\{2\}, andσ⁡\(h1\)\\sigma\(h\_\{1\}\), since these operations are evaluated pointwise\.*Aggregation case\.*Suppose thath1h\_\{1\}is constant on every class, with value\(h1\)Y\(h\_\{1\}\)\_\{Y\}on classYY\. For any classX∈𝒞X\\in\\mathcal\{C\}and any vertexv∈Xv\\in X, equitability gives

\(◇\+h1\)\(GN\(θ\)\)\(v\)\\displaystyle\(\\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}h\_\{1\}\)\(G\_\{N\}\(\\theta\)\)\(v\)=∑u∈N⁡\(v\)h1​\(u\)=∑Y∈𝒞∑u∈N⁡\(v\)∩Yh1​\(GN​\(θ\)\)​\(u\)=∑Y∈𝒞dX​Y​\(h1\)Y,\\displaystyle=\\sum\_\{u\\in N\(v\)\}h\_\{1\}\(u\)=\\sum\_\{Y\\in\\mathcal\{C\}\}\\sum\_\{u\\in N\(v\)\\cap Y\}h\_\{1\}\(G\_\{N\}\(\\theta\)\)\(u\)=\\sum\_\{Y\\in\\mathcal\{C\}\}d\_\{XY\}\(h\_\{1\}\)\_\{Y\},which depends only on the classXXand not on the particular choice ofv∈Xv\\in X\. Hence◇\+ h1\\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}h\_\{1\}is constant on every class, completing the induction\. ∎

In view of Lemma[5\.1](https://arxiv.org/html/2608.12617#S5.Thmtheorem1), we writehXh\_\{X\}for the value ofhhon classXX, andhX​\(N,θ\)h\_\{X\}\(N,\\theta\)when the instance needs to be displayed\. Recall the separating expression

E⋆≔◇\+

ReLU\(2◇\+

P−◇\+

1\+1\)−◇\+

1\+4,E\_\{\\star\}\\ \\coloneqq\\ \\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}\\mathrm\{ReLU\}\\bigl\(2\\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}P\-\\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}1\+1\\bigr\)\\ \-\\ \\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}1\\ \+\\ 4,and letz≔2◇\+ P−◇\+ 1\+1z\\coloneqq 2\\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}P\-\\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}1\+1\. From the construction,

zO=1−t<0,zWi\+=ri−bi=2​N​ui,zWi−=bi−ri=−2​N​ui\.z\_\{O\}=1\-t<0,\\qquad z\_\{W\_\{i\}^\{\+\}\}=r\_\{i\}\-b\_\{i\}=2Nu\_\{i\},\\qquad z\_\{W\_\{i\}^\{\-\}\}=b\_\{i\}\-r\_\{i\}=\-2Nu\_\{i\}\.Since everyo∈Oo\\in Ohasttneighbours inOOand one in each classWi±W\_\{i\}^\{\\pm\},

\(◇\+

ReLU\(z\)\)O=2N\(u1\+u2\)\.\(\\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}\\mathrm\{ReLU\}\(z\)\)\_\{O\}=2N\(u\_\{1\}\+u\_\{2\}\)\.As\(◇\+ 1\)O=t\+4\(\\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}1\)\_\{O\}=t\+4andt=2​N​αt=2N\\alpha, we obtain the following*key property*\.

###### Proposition 5\.2\.

For every rationalθ∈Θ\\theta\\in\\Theta, everyθ\\theta\-admissibleNN, and everyo∈Oo\\in O,

E⋆​\(GN​\(θ\)\)​\(o\)=2​N​\(u1\+u2−α\)\.E\_\{\\star\}\(G\_\{N\}\(\\theta\)\)\(o\)=2N\(u\_\{1\}\+u\_\{2\}\-\\alpha\)\.Thus\(E⋆\)𝔹​\(GN​\(θ\)\)​\(o\)=1\(E\_\{\\star\}\)\_\{\\mathbb\{B\}\}\(G\_\{N\}\(\\theta\)\)\(o\)=1exactly whenu1\+u2\>αu\_\{1\}\+u\_\{2\}\>\\alpha\.

## 6Asymptotic locality

Call a polynomial inℝ⁡\[u1,u2,α\]\\mathbb\{R\}\[u\_\{1\},u\_\{2\},\\alpha\]*cylindrical*if it lies inℝ⁡\[α\]\\mathbb\{R\}\[\\alpha\],ℝ⁡\[u1,α\]\\mathbb\{R\}\[u\_\{1\},\\alpha\], orℝ⁡\[u2,α\]\\mathbb\{R\}\[u\_\{2\},\\alpha\]\. In other words, such polynomials never involve bothu1u\_\{1\}andu2u\_\{2\}\.

###### Definition 6\.1\(Sign decompositions\)\.

A finite set𝒫\\mathcal\{P\}of nonzero cylindrical polynomials determines, for each sign assignments:𝒫→\{\+1,−1\}s:\\mathcal\{P\}\\to\\\{\+1,\-1\\\}, the open \(possibly empty\)*cell*

Θs≔\{θ∈Θ:sgn⁡\(p⁡\(θ\)\)=s⁡\(p\)​for all​p∈𝒫\},\\Theta\_\{s\}\\coloneqq\\\{\\theta\\in\\Theta:\\ \\mathrm\{sgn\}\(p\(\\theta\)\)=s\(p\)\\ \\text\{for all \}p\\in\\mathcal\{P\}\\\},wherep∈ℝ⁡\[α\]p\\in\\mathbb\{R\}\[\\alpha\]orℝ⁡\[ui,α\]\\mathbb\{R\}\[u\_\{i\},\\alpha\]is evaluated at the corresponding coordinates ofθ\\theta\. The cells are pairwise disjoint and coverΘ∖Z⁡\(𝒫\)\\Theta\\setminus Z\(\\mathcal\{P\}\), whereZ⁡\(𝒫\)Z\(\\mathcal\{P\}\)is the zero set⋃p∈𝒫\{θ∈Θ:p⁡\(θ\)=0\}\\bigcup\_\{p\\in\\mathcal\{P\}\}\\\{\\theta\\in\\Theta:p\(\\theta\)=0\\\}\.

Put

A0=ℝ\+Nℝ\[N,α\],Ai=ℝ\+Nℝ\[N,ui,α\]\(i=1,2\)\.A\_\{0\}=\\mathbb\{R\}\+N\\mathbb\{R\}\[N,\\alpha\],\\qquad A\_\{i\}=\\mathbb\{R\}\+N\\mathbb\{R\}\[N,u\_\{i\},\\alpha\]\\quad\(i=1,2\)\.
###### Definition 6\.2\(Local vectors\)\.

A*class\-vector*is a tupleq=\(qO,qW1\+,qW1−,qW2\+,qW2−\)q=\(q\_\{O\},q\_\{W\_\{1\}^\{\+\}\},q\_\{W\_\{1\}^\{\-\}\},q\_\{W\_\{2\}^\{\+\}\},q\_\{W\_\{2\}^\{\-\}\}\)of polynomials inN,u1,u2,αN,u\_\{1\},u\_\{2\},\\alpha\. Writingwi​\(q\)≔qWi\+\+qWi−w\_\{i\}\(q\)\\coloneqq q\_\{W\_\{i\}^\{\+\}\}\+q\_\{W\_\{i\}^\{\-\}\}, we callqq*local*when

qO,w1​\(q\),w2​\(q\)∈A0andqWi±∈Ai\(i=1,2\)\.q\_\{O\},\\,w\_\{1\}\(q\),\\,w\_\{2\}\(q\)\\in A\_\{0\}\\qquad\\text\{and\}\\qquad q\_\{W\_\{i\}^\{\\pm\}\}\\in A\_\{i\}\\quad\(i=1,2\)\.

Here “local” refers to parameter dependence\. The form ofA0A\_\{0\}andAiA\_\{i\}also ensures that every nonconstant parameter\-dependent term carries a positive power ofNN\.

###### Definition 6\.3\(Asymptotic locality\)\.

AΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}expressionhhis*asymptotically local*\(on the familyGN​\(θ\)G\_\{N\}\(\\theta\)\) if there exist

1. 1\.a finite set𝒫h\\mathcal\{P\}\_\{h\}of nonzero cylindrical polynomials, and
2. 2\.for each sign assignmentsson𝒫h\\mathcal\{P\}\_\{h\}withΘs≠∅\\Theta\_\{s\}\\neq\\emptyset, a local class\-vectorΦs\\Phi^\{s\},

such that for every rationalθ∈Θs\\theta\\in\\Theta\_\{s\}there is a thresholdN0​\(h,θ\)∈ℕN\_\{0\}\(h,\\theta\)\\in\\mathbb\{N\}with

hX​\(N,θ\)=ΦXs​\(N,θ\)for every classXand everyθ\-admissible​N≥N0​\(h,θ\),h\_\{X\}\(N,\\theta\)=\\Phi^\{s\}\_\{X\}\(N,\\theta\)\\qquad\\text\{for every class $X$ and every $\\theta$\-admissible \}N\\geq N\_\{0\}\(h,\\theta\),where evaluation substitutesNNand the coordinates ofθ\\thetaoccurring inΦXs\\Phi^\{s\}\_\{X\}\.

We will show that everyΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}expression is asymptotically local \(Section[8](https://arxiv.org/html/2608.12617#S8)\) whenΣ\\Sigmacontains only eventually constant activation functions\. Before doing so, we show that the main theorem already follows\.

## 7Proof of Theorem[3\.2](https://arxiv.org/html/2608.12617#S3.Thmtheorem2)

The only ingredient needed is the specialisation of Definition[6\.3](https://arxiv.org/html/2608.12617#S6.Thmtheorem3)to the classOO: ifhhis asymptotically local then, on each cellΘs\\Theta\_\{s\}, there is a*single*polynomialFs≔ΦOs∈A0⊆ℝ⁡\[N,α\]F\_\{s\}\\coloneqq\\Phi^\{s\}\_\{O\}\\in A\_\{0\}\\subseteq\\mathbb\{R\}\[N,\\alpha\], mentioning neitheru1u\_\{1\}noru2u\_\{2\}, with

h⁡\(GN​\(θ\)\)​\(o\)=Fs​\(N,α\)​for all​o∈O,all rational​θ∈Θs,all admissible​N≥N0​\(h,θ\)\.h\\bigl\(G\_\{N\}\(\\theta\)\\bigr\)\(o\)=F\_\{s\}\(N,\\alpha\)\\text\{ for all \}o\\in O,\\ \\text\{all rational \}\\theta\\in\\Theta\_\{s\},\\ \\text\{all admissible \}N\\geq N\_\{0\}\(h,\\theta\)\.\(6\)In particular, letθ,θ′∈Θs\\theta,\\theta^\{\\prime\}\\in\\Theta\_\{s\}be two rational points with the sameα\\alpha\-coordinate\. For every common admissibleNNwithN≥max⁡\{N0​\(h,θ\),N0​\(h,θ′\)\}N\\geq\\max\\\{N\_\{0\}\(h,\\theta\),N\_\{0\}\(h,\\theta^\{\\prime\}\)\\\}, the expressionhhtakes the same value on the classOOinGN​\(θ\)G\_\{N\}\(\\theta\)andGN​\(θ′\)G\_\{N\}\(\\theta^\{\\prime\}\)– no matter how their parametersu1,u2u\_\{1\},u\_\{2\}differ\. The target query, by contrast, flips exactly across the surfaceu1\+u2=αu\_\{1\}\+u\_\{2\}=\\alpha\(Proposition[5\.2](https://arxiv.org/html/2608.12617#S5.Thmtheorem2)\)\. The proof below drives a wedge between the two, using one classical fact\.

###### Fact 7\.1\.

A polynomialp∈ℝ⁡\[x1,…,xn\]p\\in\\mathbb\{R\}\[x\_\{1\},\\dots,x\_\{n\}\]that vanishes on a nonempty open subsetU⊆ℝnU\\subseteq\\mathbb\{R\}^\{n\}is the zero polynomial\.

###### Proof of Theorem[3\.2](https://arxiv.org/html/2608.12617#S3.Thmtheorem2)\.

Suppose someΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}expressionffis Boolean equivalent toE⋆E\_\{\\star\}on all graphs with one Boolean feature\. We know thatffis asymptotically local; let𝒫\\mathcal\{P\}be its finite set of nonzero cylindrical polynomials andFsF\_\{s\}the cell\-wise polynomials of \([6](https://arxiv.org/html/2608.12617#S7.E6)\)\.

We first select a base point on the critical surfaceα=u1\+u2\\alpha=u\_\{1\}\+u\_\{2\}\. Consider the diagonal pieceH=\{\(x,y,x\+y\):\(x,y\)∈\(14,13\)2\}⊆ΘH=\\\{\(x,y,x\+y\):\(x,y\)\\in\(\\tfrac\{1\}\{4\},\\tfrac\{1\}\{3\}\)^\{2\}\\\}\\subseteq\\Thetaof the surfaceu1\+u2=αu\_\{1\}\+u\_\{2\}=\\alpha\. We first show that there is a point ofHHat which everyp∈𝒫p\\in\\mathcal\{P\}is nonzero\. For eachp∈𝒫p\\in\\mathcal\{P\}, we definep~∈ℝ⁡\[u1,u2\]\\tilde\{p\}\\in\\mathbb\{R\}\[u\_\{1\},u\_\{2\}\]byp~​\(u1,u2\)≔p⁡\(ui,u1\+u2\)\\tilde\{p\}\(u\_\{1\},u\_\{2\}\)\\coloneqq p\(u\_\{i\},u\_\{1\}\+u\_\{2\}\)ifp∈ℝ⁡\[ui,α\]p\\in\\mathbb\{R\}\[u\_\{i\},\\alpha\], andp~​\(u1,u2\)≔p⁡\(u1\+u2\)\\tilde\{p\}\(u\_\{1\},u\_\{2\}\)\\coloneqq p\(u\_\{1\}\+u\_\{2\}\)ifp∈ℝ⁡\[α\]p\\in\\mathbb\{R\}\[\\alpha\]\. Each polynomialp~\\tilde\{p\}is nonzero\. For instance, supposep∈ℝ⁡\[u1,α\]p\\in\\mathbb\{R\}\[u\_\{1\},\\alpha\]andp~\\tilde\{p\}were identically zero\. Then, for allu1,αu\_\{1\},\\alpha,

p⁡\(u1,α\)=p⁡\(u1,u1\+\(α−u1\)\)=p~​\(u1,α−u1\)=0,p\(u\_\{1\},\\alpha\)=p\(u\_\{1\},u\_\{1\}\+\(\\alpha\-u\_\{1\}\)\)=\\tilde\{p\}\(u\_\{1\},\\alpha\-u\_\{1\}\)=0,contradicting thatppis nonzero\. The casep∈ℝ⁡\[u2,α\]p\\in\\mathbb\{R\}\[u\_\{2\},\\alpha\]is the same, usingu1=α−u2u\_\{1\}=\\alpha\-u\_\{2\}, and the casep∈ℝ⁡\[α\]p\\in\\mathbb\{R\}\[\\alpha\]is immediate\. This is where cylindricity is indispensable: a polynomial mentioning bothu1u\_\{1\}andu2u\_\{2\}, such asu1\+u2−αu\_\{1\}\+u\_\{2\}\-\\alphaitself, could vanish identically onHH\. Their product∏p∈𝒫p~\\prod\_\{p\\in\\mathcal\{P\}\}\\tilde\{p\}is thus also nonzero, and by Fact[7\.1](https://arxiv.org/html/2608.12617#S7.Thmtheorem1), it is nonzero somewhere on the open box\(14,13\)2\(\\tfrac\{1\}\{4\},\\tfrac\{1\}\{3\}\)^\{2\}, so by continuity and the density ofℚ2\\mathbb\{Q\}^\{2\}it is nonzero at a rational point\(a,b\)∈\(14,13\)2\(a,b\)\\in\(\\tfrac\{1\}\{4\},\\tfrac\{1\}\{3\}\)^\{2\}\. Thus everyp∈𝒫p\\in\\mathcal\{P\}is nonzero at the pointθ∗≔\(a,b,a\+b\)\\theta^\{\*\}\\coloneqq\(a,b,a\+b\), by construction\. Thenθ∗∈Θs\\theta^\{\*\}\\in\\Theta\_\{s\}, wheres⁡\(p\)≔sgn⁡\(p⁡\(θ∗\)\)s\(p\)\\coloneqq\\mathrm\{sgn\}\(p\(\\theta^\{\*\}\)\)\.

We next create two nearby points on opposite sides of the critical surface, yet inside one cell\. Since𝒫\\mathcal\{P\}is finite and its members are continuous and nonzero atθ∗\\theta^\{\*\}, we may pick a rationalε\>0\\varepsilon\>0so small thata±ε∈\(14,13\)a\\pm\\varepsilon\\in\(\\tfrac\{1\}\{4\},\\tfrac\{1\}\{3\}\)and everyp∈𝒫p\\in\\mathcal\{P\}keeps its sign at

θ±≔\(a±ε,b,a\+b\)\.\\theta^\{\\pm\}\\coloneqq\(a\\pm\\varepsilon,\\,b,\\,a\+b\)\.Thenθ−,θ\+∈Θs\\theta^\{\-\},\\theta^\{\+\}\\in\\Theta\_\{s\}, they shareα0≔a\+b\\alpha\_\{0\}\\coloneqq a\+b, andu1\+u2−αu\_\{1\}\+u\_\{2\}\-\\alphaevaluates to∓ε\\mp\\varepsilonatθ∓\\theta^\{\\mp\}: the two points lie on opposite sides of the critical surface\.

We are now ready to obtain a contradiction\. ChooseNNto be a common multiple of the least common denominators ofθ−\\theta^\{\-\}andθ\+\\theta^\{\+\}withN≥max⁡\{N0​\(f,θ−\),N0​\(f,θ\+\)\}N\\geq\\max\\\{N\_\{0\}\(f,\\theta^\{\-\}\),N\_\{0\}\(f,\\theta^\{\+\}\)\\\}; suchNNexist, since there are arbitrarily large common multiples\. Both graphsGN​\(θ±\)G\_\{N\}\(\\theta^\{\\pm\}\)are then defined, and by \([6](https://arxiv.org/html/2608.12617#S7.E6)\), applied on the cellΘs\\Theta\_\{s\}containing both points, for everyo∈Oo\\in O

f⁡\(GN​\(θ−\)\)​\(o\)=Fs​\(N,α0\)=f⁡\(GN​\(θ\+\)\)​\(o\),f\\bigl\(G\_\{N\}\(\\theta^\{\-\}\)\\bigr\)\(o\)=F\_\{s\}\(N,\\alpha\_\{0\}\)=f\\bigl\(G\_\{N\}\(\\theta^\{\+\}\)\\bigr\)\(o\),one and the same real number\. Yet Proposition[5\.2](https://arxiv.org/html/2608.12617#S5.Thmtheorem2)givesE⋆​\(GN​\(θ∓\)\)​\(o\)=∓2​N​εE\_\{\\star\}\\bigl\(G\_\{N\}\(\\theta^\{\\mp\}\)\\bigr\)\(o\)=\\mp 2N\\varepsilon, of opposite signs\. So the Booleanisations offfagree at theOO\-vertices of the two graphs while those ofE⋆E\_\{\\star\}differ, contradicting Boolean equivalence\. ∎

## 8Eventually constant implies asymptotically local

It remains to prove that everyΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}expression is asymptotically local whenever all activations inΣ\\Sigmaare eventually constant\.

###### Lemma 8\.1\.

LetΣ\\Sigmabe a collection of eventually constant activation functions\. Then everyΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}expression is asymptotically local\.

###### Proof\.

We proceed by structural induction onΣ​\-​MPLang\\Sigma\\text\{\-\}\\mathrm\{MPLang\}expressionshh\. Along the induction the sets𝒫h\\mathcal\{P\}\_\{h\}only grow \(𝒫h′⊆𝒫h\\mathcal\{P\}\_\{h^\{\\prime\}\}\\subseteq\\mathcal\{P\}\_\{h\}forh′h^\{\\prime\}a subexpression ofhh\); a sign assignment on the larger set restricts to one on the smaller, whose cell contains the \(nonempty\) finer cell, so inductive data remains available and valid on every finer cell, with unchanged thresholds\.

*Base cases\.*Forh=1h=1andh=Ph=P, take𝒫h≔∅\\mathcal\{P\}\_\{h\}\\coloneqq\\emptyset\(the unique empty sign assignment has cellΘ\\Theta\) and the constant vectors

Φ1≔\(1,1,1,1,1\),ΦP≔\(0,1,0,1,0\),\\Phi\_\{1\}\\coloneqq\(1,1,1,1,1\),\\qquad\\Phi\_\{P\}\\coloneqq\(0,1,0,1,0\),recording thatP=1P=1exactly onW1\+∪W2\+W\_\{1\}^\{\+\}\\cup W\_\{2\}^\{\+\}\. Constants lie inA0⊆AiA\_\{0\}\\subseteq A\_\{i\}and the pair\-sums are constants, so both vectors are local; the defining equalities hold exactly, withN0=1N\_\{0\}=1\.

*Linear cases\.*Forh=a​h1h=a\\,h\_\{1\}andh=h1\+h2h=h\_\{1\}\+h\_\{2\}, take𝒫h≔𝒫h1\\mathcal\{P\}\_\{h\}\\coloneqq\\mathcal\{P\}\_\{h\_\{1\}\}, resp\.𝒫h1∪𝒫h2\\mathcal\{P\}\_\{h\_\{1\}\}\\cup\\mathcal\{P\}\_\{h\_\{2\}\}, and the corresponding linear combinations of the inductive vectors\. The classesA0,AiA\_\{0\},A\_\{i\}and the pair\-sum conditions are closed under linear combinations, and class values combine linearly\. So the resulting vector is local and continues to describe the class\-values for all sufficiently large admissibleNN\(by choosing the maximum of the inherited thresholds as the new threshold\)\.

*Aggregation\.*Forh=◇\+ h1h=\\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}h\_\{1\}, take𝒫h≔𝒫h1\\mathcal\{P\}\_\{h\}\\coloneqq\\mathcal\{P\}\_\{h\_\{1\}\}: aggregation makes no decisions\. LetDDbe the quotient adjacency operator of Lemma[5\.1](https://arxiv.org/html/2608.12617#S5.Thmtheorem1)andq≔Φsq\\coloneqq\\Phi^\{s\}the inductive vector; defineΦnews≔D​q\\Phi^\{s\}\_\{\\text\{new\}\}\\coloneqq Dq, i\.e\., substitutet=2​N​αt=2N\\alpha,ri=N⁡\(1\+ui\)r\_\{i\}=N\(1\+u\_\{i\}\),bi=N⁡\(1−ui\)b\_\{i\}=N\(1\-u\_\{i\}\)into the quotient matrix\. For every rationalθ\\thetain the cell and every admissibleN≥N0​\(h1,θ\)N\\geq N\_\{0\}\(h\_\{1\},\\theta\), the inductive vector gives the class\-values ofh1h\_\{1\}\. Hence the class\-values of◇\+ h1\\mathbin\{\\mathchoice\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\Diamond$\\cr$\\displaystyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\Diamond$\\cr$\\textstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\Diamond$\\cr$\\scriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\Diamond$\\cr$\\scriptscriptstyle\\raisebox\{0\.0pt\}\{\\scalebox\{1\}\[1\.1\]\{$\+$\}\}$\\cr\}\}\}\}h\_\{1\}are obtained by applying the quotient matrixDDto that vector\. For locality, compute from the quotient matrix:

\(D​q\)O=2​N​α​qO\+w1​\(q\)\+w2​\(q\),wi​\(D​q\)=2​qO\+2​N​wi​\(q\),\(Dq\)\_\{O\}=2N\\alpha\\,q\_\{O\}\+w\_\{1\}\(q\)\+w\_\{2\}\(q\),\\qquad w\_\{i\}\(Dq\)=2q\_\{O\}\+2N\\,w\_\{i\}\(q\),and individually\(D​q\)Wi±=qO\+N⁡\(1±ui\)​qWi\+\+N⁡\(1∓ui\)​qWi−\(Dq\)\_\{W\_\{i\}^\{\\pm\}\}=q\_\{O\}\+N\(1\\pm u\_\{i\}\)\\,q\_\{W\_\{i\}^\{\+\}\}\+N\(1\\mp u\_\{i\}\)\\,q\_\{W\_\{i\}^\{\-\}\}\. By inductionqO,w1​\(q\),w2​\(q\)∈A0q\_\{O\},w\_\{1\}\(q\),w\_\{2\}\(q\)\\in A\_\{0\}, and multiplying an element ofA0A\_\{0\}by2​N​α2N\\alphaor2​N2Nlands inN​ℝ​\[N,α\]⊆A0N\\mathbb\{R\}\[N,\\alpha\]\\subseteq A\_\{0\}; hence\(D​q\)O\(Dq\)\_\{O\}andwi​\(D​q\)w\_\{i\}\(Dq\)lie inA0A\_\{0\}\. Furthermore,\(D​q\)Wi±∈Ai\(Dq\)\_\{W\_\{i\}^\{\\pm\}\}\\in A\_\{i\}, as the multipliersN⁡\(1±ui\)N\(1\\pm u\_\{i\}\)carry a factorNNand involve onlyuiu\_\{i\}, andqO∈A0⊆Aiq\_\{O\}\\in A\_\{0\}\\subseteq A\_\{i\},qWi±∈Aiq\_\{W\_\{i\}^\{\\pm\}\}\\in A\_\{i\}by induction\. SoD​qDqis local\.

*Activation\.*Forh=σ⁡\(h1\)h=\\sigma\(h\_\{1\}\)withσ∈Σ\\sigma\\in\\Sigmaeventually constant, fix a sign assignmentsson𝒫h1\\mathcal\{P\}\_\{h\_\{1\}\}with nonempty cell and write each coordinate of the inductive vector as

ΦsX=cX\+∑k≥1aX,kNk,cX∈ℝ,aX,kcylindrical,\\Phi^\{s\}\_\{X\}=c\_\{X\}\+\\sum\_\{k\\geq 1\}a\_\{X,k\}N^\{k\},\\qquad c\_\{X\}\\in\\mathbb\{R\},\\quad a\_\{X,k\}\\ \\text\{cylindrical\},which is precisely what membership inA0,AiA\_\{0\},A\_\{i\}provides\. Enlarge𝒫h\\mathcal\{P\}\_\{h\}by all nonzeroaX,ka\_\{X,k\}\(over allssand the five classes: finitely many polynomials\)\. On any cell of the enlarged set, for each classXXeither allaX,ka\_\{X,k\}are zero polynomials, and then the argument ofσ\\sigmaatXXis the*parameter\-free*constantcXc\_\{X\}, soσ​\(h1\)X\\sigma\(h\_\{1\}\)\_\{X\}isσ⁡\(cX\)\\sigma\(c\_\{X\}\), or the leading nonzero coefficient inNNhas a fixed sign on the cell, so the argument is a polynomial function ofNNdiverging to\+∞\+\\inftyor−∞\-\\infty, andσ​\(h1\)X\\sigma\(h\_\{1\}\)\_\{X\}is eventuallyC\+σC^\{\\sigma\}\_\{\+\}orC−σC^\{\\sigma\}\_\{\-\}\(Definition[2\.2](https://arxiv.org/html/2608.12617#S2.Thmtheorem2)\)\. In every case the outcome is a real constant determined by the cell, reached beyond a threshold depending on the rational parameter point \(how largeNNmust be for the leading term to dominate and for the argument to leave\[x−σ,x\+σ\]\[x^\{\\sigma\}\_\{\-\},x^\{\\sigma\}\_\{\+\}\]\)\. The resulting constant vector is local, all its entries and pair\-sums being real numbers\. Note that the polynomials added to𝒫h\\mathcal\{P\}\_\{h\}are coefficients of entries of a local vector, hence lie inℝ⁡\[α\]\\mathbb\{R\}\[\\alpha\]orℝ⁡\[ui,α\]\\mathbb\{R\}\[u\_\{i\},\\alpha\]and cylindricity is maintained\. ∎

## References

- \[1\]Pablo Barceló, Floris Geerts, Matthias Lanzinger, Klara Pakhomenko, and Jan Van den Bussche\.A logical view of GNN\-style computation and the role of activation functions\.Proc\. ACM Manag\. Data, 4\(2\), May 2026\.
- \[2\]Michael Benedikt, Chia\-Hsuan Lu, and Tony Tan\.Decidability of graph neural networks via logical characterizations\.ACM Trans\. Comput\. Logic, 27\(2\), April 2026\.
- \[3\]Floris Geerts, Jasper Steegmans, and Jan Van den Bussche\.On the expressive power of message\-passing neural networks as global feature map transformers\.InFoundations of Information and Knowledge Systems, page 20–34\. Springer, 2022\.
- \[4\]Martin Grohe, Kristian Kersting, Martin Mladenov, and Erkal Selman\.Dimension reduction via colour refinement\.InEuropean Symposium on Algorithms, pages 505–516\. Springer, 2014\.