CS Paper Radar

Proofs of strong forms of the Bovdi--Geche universality conjecture and a complex analogue

Victor Bovdi, Ambrus Pal

cs.LG math.NTmath.RA ·submitted 2026-10-26 15:53 UTC · v1
theory

Abstract

We prove two universality theorems for neural networks consisting of a single neuron. First we prove a strong form of the Bovdi--Geche universality conjecture on neurons over finite fields, where the activation function is a certain modification of the discrete logarithm, using the Weil bound on multiplicative character sums over finite fields. Then we show a generalisation of Aizenberg's universality theorem for complex binary neurons with a weight vector independent of the target function, positively answering another question in the literature. The proof of the latter uses an equidistribution theorem for the dilates of certain maps into tori.

Comment
14 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Linear Independence of Polynomial Compositions with Bounded Input Degree

cs.LG math.AG ·2026-10-14 ·Xiaotian Chang, Yacoub Hendi
theory similarity 0.62
Abstract · 13 pages

We prove the weak composition-independence conjectures of Kohn, Marchetti, Massarenti and Mella. The proof uses deformations of rational curves and a single kernel of the linearized equation. Riemann-Roch gives a contradiction from tangent fields with controlled poles. By settling these conjectures, we prove that a neural network with a general polynomial activation function of sufficiently large degree is identifiable.

0.36

Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecture

cs.LG cs.LO ·2026-10-12 ·Daumantas Kojelis, Carsten Lutz
theory similarity 0.55
Abstract

A landmark result states that the expressive power of graph neural networks (GNNs) is bounded from above by the 1-dimensional Weisfeiler-Leman (1-WL) test. We ask whether a constant-depth GNN can match the expressive power of 1-WL while using only rational weights. We prove that this is the case when Schanuel's conjecture, a famous open problem from transcendental number theory, is taken to be true. Our GNN construction works even with integer weights, and more generally with a broad range of rational weights. As the activation function, it may use logistic sigmoid, hyperbolic tangent, or related functions. It is uniform across all graph sizes. We also prove a partial converse: if a GNN with exponentiation, hyperbolic sine or hyperbolic cosine as activation matches the expressive power of the 1-WL test in a slightly more expressive setting where graphs may contain certain auxiliary vertices, then this implies Schanuel's conjecture restricted to the numbers that arise in computations of the GNN. We also conduct experiments showing that the constructed GNNs indeed match the 1-WL test.

0.22

Linear Independence of Polynomial Compositions and Identifiability of Deep Neural Networks

cs.LG math.ACmath.AG ·2026-08-27 ·Kathlén Kohn, Giovanni Luca Marchetti, Alex Massarenti, Massimiliano Mella
theoryhighly cited similarity 0.55
Abstract

Motivated by theoretical problems in deep learning, we conjecture that post-composing a fixed number of pairwise distinct nonconstant polynomials with a generic polynomial of sufficiently large degree yields linearly independent polynomials. This generalizes Newman--Slater's theorem on powers of polynomials. We establish several cases of this conjecture and its origin-passing variant: We prove the result for two polynomials, and for an arbitrary number of polynomials when their degrees are bounded. Furthermore, we show how the conjecture implies a complete understanding of the identifiability (i.e., parameter symmetries) of deep fully connected neural network architectures with generic polynomial activation functions. In particular, for network architectures with layer-specific activations of increasing degree, our established versions of the conjecture fully characterize the set of parameters yielding the same end-to-end network function. As a special case, we fully resolve the identifiability of shallow polynomial networks.

0.43

Deep belief networks are exact

cs.AI cs.LGmath.PR ·2026-09-04 ·Gleb Smirnov
theory similarity 0.52
Abstract · 6 pages

We prove that every strictly positive probability distribution on \(\{-1,1\}^n\) is represented exactly by a sigmoid belief network with finite parameters. This answers a question of Sutskever and Hinton. The proof upgrades their probability-sharing approximation to exact representation using Brouwer's fixed-point theorem.

0.26

Canonical activation patterns and ReLU pattern varieties

cs.LG math.COmath.AG ·2026-11-16 ·Bella Finkel, Yaoying Fu, Chenxi Wu
similarity 0.52
Abstract

A ReLU pattern variety records the polynomial relations among the coefficients of the affine maps associated with a prescribed set of activation patterns of a ReLU network. We study how the combinatorics of the canonical set of activation patterns of an unbiased ReLU network is reflected in the geometry of its pattern variety. In particular, we introduce the notion of pattern stability and characterize pattern stability and combinatorial stability for shallow networks. When the associated wall graph is connected and contains an edge of every neuron label, we resolve a problem of Alexandr and Montúfar by determining the defining ideal of the associated pattern variety explicitly. We establish a hierarchy of progressively weaker equivalence relations relating labeled combinatorial equivalence, equality and permutation equivalence of canonical pattern sets, and equivalences of the associated varieties. Finally, we relate functional dimension to the differential of the pattern map and show that it is bounded above by the dimension of the canonical pattern variety at every depth. For nondegenerate shallow networks, we give an exact formula for the functional dimension; for every shallow architecture, it equals the dimension of the canonical pattern variety on an open dense set of full Lebesgue measure.

0.30

Constructive Bounds for the Topological Expressivity of Neural Networks

cs.LG math.AT ·2026-10-09 ·Kosio Beshkov
similarity 0.52
Abstract

The expressivity of a neural network $Φ$ describes the class of functions that a network can express. The term topological expressivity refers to a family of measures particularly suited to understand binary classification and is often formulated in terms of the Betti numbers of a decision boundary $β(Φ^{-1}(0))$. Despite its popularity, this measure is not as useful for regression and other problems that do not involve a decision boundary. Instead, we propose to study topological expressivity in terms of the Betti numbers of the output of a neural network $β(Φ(X))$. We formally prove that a ReLU network with architecture $(d,\sum\limits_{k=1}^{d } β_k(3k+2),\sum\limits_{k=1}^{d}β_k(k+1))$ can express spaces homotopy equivalent to wedge sums of spheres with arbitrary Betti numbers. This gives upper bounds for any arbitrary connected ($β_0=1$) sequence of Betti numbers, but by constructing spaces homotopy equivalent to products of $N$ spheres of dimension $d_1,...,d_N$ we achieve much better bounds $(\sum\limits_{n=1} d_n, 3\sum\limits_{n=1}\limits^N d_n + 2N, \sum\limits_{n=1}\limits^N d_n + N) $ for Betti numbers given by $\prod_n (1+x^{d_n})$. Finally we conjecture a much stronger tight bound which gives the architectural bound $(d,d+1,d+1)$ for a space homeomorphic to the sphere.

0.35

Arbitrary-Accuracy Neural Approximation with Optimal Neuron Count and Near-Optimal Bit Complexity

cs.LG cs.NEstat.ML ·2026-09-28 ·Zilan Cheng, Li-Lian Wang, Zhongjian Wang
theory similarity 0.52
Abstract

We study the minimum number of hidden neurons required for arbitrary-accuracy approximation of multivariate Hölder-continuous functions on $[0,1]^d$ and the associated encoding complexity. For $d\geq 2$, we construct a fixed, explicitly defined activation function for which a closed-form network with two hidden layers of widths $d$ and $1$ achieves arbitrary accuracy in the uniform norm. We prove that $d+1$ is the exact minimum total number of hidden neurons among standard feedforward networks with locally integrable activations and affine outputs. We further give a simpler construction using a single elementary activation that combines the floor and exponential functions. This construction requires three hidden layers of widths $d$, $1$, and $2$, only two neurons above the minimum. If a skip connection is allowed, widths $d$, $1$, and $1$ suffice. These constructions use explicit grid addressing and integer encoding of quantized function values. For a bounded $α$-Hölder class, they require $O(\varepsilon^{-d/α}\log(1/\varepsilon))$ bits, matching the metric-entropy lower bound up to a logarithmic factor.

0.16

The Continuum Limit of the Deep Linear Network

cs.LG math.DG ·2026-10-31 ·Catherine Eva Pfaff, Karen Uhlenbeck
similarity 0.52
Abstract

The Deep Linear Network (DLN) is a simple version of a Multilayer Perceptron (MLP) in which the activation function is the identity and the bias vector is the zero vector. We examine the behavior of the model when the number of weight matrices, which is finite in the original model, goes to infinity. We show that a plausible continuum limit is a dimensionally reduced version of the Yang-Mills equation on the torus, revealing an unexpected geometric interpretation of infinite-depth DLNs. While we do not prove this rigorously, it is a very pretty calculation. It also gives some insight into several features of the construction. We note that the choices of boundary conditions on the ends of the discrete series survive better in the continuum limit. Also, the regularizing functional which uses the moment map survives nicely in the continuum limit, whereas the regularizing functional using the size of approximating terms has no sensible limit. This surely is useful information for the choices we make in the finite-dimensional theory, and might also be useful in the more complicated MLP setting.

0.52