Pith. sign in

REVIEW 3 major objections 4 minor 23 references

CantorNet: A Sandbox for Testing Geometrical and Topological Complexity Measures

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read CantorNet gives a ReLU decision surface whose recursive construction is minimal at O(k) neurons and whose polyhedral twin costs O(2^k), a controlled scale for testing complexity measures.

desk verdict A genuinely useful two-representation ReLU sandbox whose minimality theorem is asserted rather than proven, but the missing proof is straightforward. read the letter →

arxiv 2411.19713 v3 pith:2AB6P33H submitted 2024-11-29 cs.NE cs.AIstat.ML

Michal Lewandowski , Hamid Eghbalzadeh , Bernhard A.Moser This is my paper · ORCID
classification cs.NEcs.AIstat.ML MSC 68T0768Q3028A80
keywords CantorNetReLUneuralnetworkssetfractalsKolmogorovcomplexitytriadicexpansiondecisionboundarytopological
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces CantorNet, a family of ReLU neural networks (networks built from the activation $\max(x,0)$) whose decision boundary is the level-$k$ middle-third construction that defines the Cantor set. The same boundary is built in two ways: a recursion that reuses a fixed five-neuron block and needs $O(k)$ neurons total, and an explicit union of polyhedral pieces that needs $O(2^k)$ neurons. The authors claim the recursive representation is of minimal complexity order among ReLU networks for this surface, in the sense of description length as measured by neuron count. If correct, CantorNet supplies a tractable, analytically known family of decision surfaces that can be tuned from simple to arbitrarily ragged, giving complexity measures a ground truth to test against.

What carries the argument

The load-bearing object is the one-dimensional generating function $A(x)=\max\{-3x+1,0,3x-2\}$, nested $k$ times and lifted to a two-dimensional decision manifold $R_k=\{(x,y)\in[0,1]^2 : y\le(A^{(k)}(x)+1)/2\}$. The recursion is encoded by fixed weight matrices so that each extra level costs a constant number of neurons, giving the $O(k)$ representation. The triadic-expansion isomorphism is what connects activation patterns to the first $k$ digits of the input's base-3 expansion and carries the minimality argument. The opposing construction writes the same manifold as a min/max expression of affine half-spaces and uses the fact that $\min$ is itself expressible as a ReLU network, producing the exponential-size disjunctive normal form.

What would settle it

Try to build a ReLU network that computes the level-$k$ triadic-prefix decision for all points of $[0,1]$ using $o(k)$ neurons, for example by encoding several ternary digits per neuron or sharing subcircuits across depth, and test it on the $2^k$ interval endpoints; any correct sublinear construction would falsify Theorem 1.

Watch

Extended reading notes

Core claim

The central claim is that the recursion-based ReLU network $N_A^{(k)}$, formed by nesting the generating function $A(x)=\max\{-3x+1,0,3x-2\}$ through the weight matrices of Eq. (4), represents the level-$k$ Cantor decision manifold with $O(k)$ neurons, and that this is optimal: no equivalent ReLU network can have strictly lower order of complexity in neuron count. The proof route is an isomorphism between the network's activation patterns and the triadic (base-3) digit expansion of the input up to $k$ digits; deciding those digits has minimal description length $O(k)$, and the nested construction realizes it with exactly that many neurons. The same manifold also admits a disjunctive-normal-form description as $\min(h_1, h_2, h_{r(k)}, D_1, \ldots, D_{\lfloor r(k)/4\rfloor+1})=0$ with 'dent' terms $D_l=\max(h_{4l-1}, h_{4l}, h_{4l+1})$, whose ReLU realization costs $O(2^k)$ neurons. CantorNet therefore exhibits two exact descriptions of one decision boundary at opposite ends of the description-length spectrum and identifies which one is minimal.

Load-bearing premise

The theorem's lower bound depends on the claim that a ReLU network cannot decide where a point lands among the first $k$ base-3 digits of the Cantor construction in fewer than order $k$ neurons; the paper asserts this transfer from decision complexity to neuron count rather than deriving it formally.

Editorial extensions

If this is right

  • CantorNet provides decision boundaries of exactly known raggedness, so a proposed geometrical or topological complexity measure can be calibrated against a ground-truth complexity of $O(k)$ in one representation and $O(2^k)$ in the other.
  • Because activation patterns in the recursive network are literally $k$-digit triadic codes, the family gives a closed-form map between input space and activation space for studying linear regions, Betti numbers, and related descriptors.
  • The same manifold being representable at both complexity extremes means CantorNet can expose measures that mistake representation size for intrinsic surface complexity.
  • The analytically known, arbitrarily ragged boundary makes CantorNet a natural testbed for showing how geometry-ignorant data augmentation or adversarial perturbations break down as $k$ grows.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The authors leave implicit that the same nesting trick should yield minimal-complexity ReLU networks for other digit-restricted self-similar sets, such as base-$b$ Cantor sets or higher-dimensional Sierpiński-like constructions.
  • A consequence of the two representations is that any single-number complexity measure should be run on both CantorNet twins; a measure that cannot distinguish $O(k)$ from $O(2^k)$ is measuring the representation rather than the geometry.
  • One testable extension is to train classifiers on samples from the inset and outset at growing $k$ and check whether generalization or adversarial robustness degrades exactly as predicted by the triadic digit structure.
  • The weight-sharing structure of the recursive representation suggests a notion of effective network depth based on description length rather than raw layer count, which the paper does not develop.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. This paper proposes CantorNet, a family of ReLU neural networks whose decision boundary is obtained by recursively composing the piecewise-linear function A(x)=max{-3x+1,0,3x-2}. For each recursion level k, the decision region R_k is defined in Eq. (3) as the subgraph of (A^{(k)}(x)+1)/2. The authors give two ReLU representations: a recursion-based network N_A^{(k)} with O(k) neurons and a disjunctive-normal-form network N_B^{(k)} with O(2^k) neurons, and they relate activation patterns of N_A^{(k)} to prefixes of triadic expansions. The central theoretical claim is Theorem 1, which states that the recursion-based representation is of minimal complexity order (Omega(k) neurons) among all ReLU networks realizing the same decision boundary. The paper also discusses applications to testing geometrical and topological complexity measures, data augmentation, and adversarial robustness.

Significance. The idea of a synthetic, analytically known, arbitrarily ragged ReLU decision surface is useful and timely: it gives the community a controlled benchmark for complexity measures, and the authors provide code. The explicit two-representation construction (recursion vs. DNF) is clear, and the O(k) versus O(2^k) neuron counts are easy to verify. However, the paper's main theorem is not proved as written: the Section 4 argument transfers an informal Kolmogorov-complexity claim to a neuron-count lower bound without a formal derivation. The missing lower bound is likely obtainable from the paper's own observation that activation patterns correspond to linear regions, since with N neurons there are at most 2^N activation patterns and the Cantor boundary has at least 2^k of them. Thus the central claim is plausible and repairable, but the current manuscript does not establish it rigorously. There are also local mathematical inaccuracies in the triadic-expansion discussion that should be corrected.

major comments (3)
  1. [Definition 1, Eq. (3)-(5)] Definition 1 states that N^{-1}(0)=R_k, but R_k defined in Eq. (3) is the two-dimensional set {y <= (A^{(k)}(x)+1)/2}, while the 0-preimage of the network N_A^{(k)} from Eqs. (4)-(5) is the one-dimensional boundary curve y=(A^{(k)}(x)+1)/2 (the network takes negative values below this curve). To make the definition consistent, one must either apply a final ReLU max(0,.) to N_A^{(k)} so that the zero set becomes the closed subgraph, or redefine R_k to be the boundary curve. This ambiguity affects all subsequent statements about insets, outsets, and activation patterns.
  2. [Section 4, Theorem 1] The proof of Theorem 1 consists of the assertion that the recursion step is equivalent to a triadic recursion 'which is of the minimal order of Kolmogorov complexity, there cannot exist an equivalent ReLU network of strictly lower order of Kolmogorov complexity.' This transfers a claim about the descriptive complexity of an algorithm to a lower bound on the number of neurons in any equivalent ReLU network, and no argument is given to rule out networks that encode the boundary in a different way, e.g., by using k-dependent weights or a different algorithmic strategy. A formal lower bound should be supplied. A natural route is to use the paper's own one-to-one correspondence between activation patterns and linear regions: since the Cantor-boundary construction has at least 2^k distinct activation patterns (or affine pieces along the x-axis) and any ReLU network with N neurons has at most 2^N activation patterns, N=Omega(k) follows. Without such an argument, Theorem 1 is unproved.
  3. [Section 3.2] The claim that any x in I1 union I3 can be described in a triadic system with arbitrary precision l as x = sum_{i=1}^l a_i/3^i with a_i in {0,2} is false. For instance, x=1/9 in I1 has the ternary expansion 0.01_3, which contains the digit 1. Only points of the middle-third Cantor set have a ternary expansion composed solely of 0s and 2s. The isomorphism between activation codes and triadic prefixes should be stated for points that stay in I1 union I3 for k iterations, or the code should be defined as ending when the point falls into I2. As written, this section overstates the correspondence and makes Lemma 1's proof imprecise.
minor comments (4)
  1. [Section 2] The statement that 'there is a one-to-one correspondence between an activation pattern and a linear region' should be qualified to 'non-empty activation patterns', since many binary vectors can define empty polyhedra for a given network.
  2. [Figure 1, Algorithm 1] The interval-to-digit mapping is inconsistent: Fig. 1 labels I1, I2, I3 as digits 0, 1, 2, while Algorithm 1 outputs 0 for I1, terminates for I2, and outputs 1 for I3. Please align the notation, e.g., by treating termination in I2 as a special marker for the digit 1.
  3. [Abstract and Section 4] The phrase 'spans the whole spectrum of possible Kolmogorov complexities' is stronger than what is shown; the paper provides two endpoints and mentions an 'intermediate example' without demonstrating a continuum. Please qualify the claim.
  4. [Appendix B] Proposition 1 is only sketched; for a journal version, please provide the complete inductive construction with explicit definitions of the affine functions h_i for arbitrary k.

Circularity Check

1 steps flagged · score 6.0 of 10

Theorem 1's minimality proof is circular: it uses the recursion's 'minimal Kolmogorov complexity' as the premise for the very conclusion that no equivalent ReLU network has lower neuron count.

  1. self definitional [Section 4, proof of Theorem 1 (paragraph after Lemma 2)]
    "As a recursion step given by Eq. (5) and Eq. (6) is equivalent to a recursion in the triadic number expansion (Alg. 1), which is of the minimal order of Kolmogorov complexity, there cannot exist an equivalent ReLU network of strictly lower order of Kolmogorov complexity. This means that NA is of minimal description length in terms of the order of the number of neurons N = N(k), thus O(N(k)) = O(k)."

    Theorem 1's conclusion—"there cannot exist an equivalent ReLU network of strictly lower order"—is derived from the premise that the recursion "is of the minimal order of Kolmogorov complexity." Under the paper's own Section 2 identification of Kolmogorov complexity with the number of layers and neurons for networks sharing the same decision boundary, "minimal Kolmogorov complexity" is the same claim as "minimal number of neurons." The lower-bound content of the theorem is therefore assumed in its proof rather than established independently; the decision-problem lower bound in Lemma 1 is also asserted rather than derived.

full rationale

The two-representation construction of CantorNet is self-contained and checkable: the recursion-based network (Eq. 4-6), the DNF representation (Prop. 1), and the neuron counts O(k) versus O(2^k) follow explicitly from the defined architectures. No fitted parameters, data splits, or external benchmarks are used, and the self-citations (Shepeleva et al. 2020 for the activation-pattern/linear-region correspondence, Moser et al. 2022 for the DNF framing) are not load-bearing: the correspondence is a standard fact and the min-as-ReLU construction is proved in Appendix C. However, the headline claim of minimality in Theorem 1 reduces, by the paper's own size-as-complexity identification, to the assertion that the triadic recursion is already minimal; that is the theorem restated, not a derived lower bound. A correct proof would need an independent argument such as activation-pattern counting (N neurons give at most 2^N patterns, while level k requires exponentially many affine regions), but the paper does not supply it. Hence partial circularity in the central claim, with the underlying geometric construction itself non-circular.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

This construction uses no fitted parameters and introduces no new physical entities. The central assumptions are standard facts about ReLU linear regions (Montufar et al.; Shepeleva et al.), the decision to measure complexity by neuron and layer counts (Grunwald et al.), and the unproven assertion that the triadic recursion is of minimal description order, which carries Theorem 1. All other ingredients are explicitly constructed in the paper.

assumptions (5)
  • domain assumption An activation pattern uniquely determines a linear region of a ReLU network.
    Invoked in Section 2 and used throughout to identify linear regions with binary codes; attributed to Shepeleva et al. (2020).
  • domain assumption The number of layers and neurons is a valid approximation to minimal description length or Kolmogorov complexity for networks with equal decision boundaries.
    Stated in Section 1 and Section 4 following Grunwald et al. (2005); the minimality theorem is stated in this surrogate sense, not for exact Kolmogorov complexity.
  • ad hoc to paper The triadic expansion recursion (Algorithm 1) has minimal Kolmogorov complexity order among decision procedures for the k-digit Cantor-prefix problem.
    Assumed in the proof of Theorem 1 (Section 4) without an external source or proof; it is the load-bearing premise for the O(k) minimality claim.
  • standard math Upper bounds on the number of linear regions of deep ReLU networks (Montufar et al. 2014; Arora et al. 2018) can be used to argue minimal neuron counts.
    Used implicitly in Lemma 2 and the minimality discussion, though the lower-bound direction is not formalized.
  • standard math The min and max operations over affine half-spaces can be exactly represented by ReLU networks with {0, +/-1} weights.
    Proved in Appendix C; underpins the DNF construction in Proposition 1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of CantorNet: A Sandbox for Testing Geometrical and Topological Complexity Measures." pith.science (2026). https://pith.science/paper/2AB6P33H

@misc{pith2026241119713,
  author       = {Pith},
  title        = {Pith review of: CantorNet: A Sandbox for Testing Geometrical and Topological Complexity Measures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2AB6P33H}},
  note         = {Machine review of arXiv:2411.19713}
}
abstract

Many natural phenomena are characterized by self-similarity, for example the symmetry of human faces, or a repetitive motif of a song. Studying of such symmetries will allow us to gain deeper insights into the underlying mechanisms of complex systems. Recognizing the importance of understanding these patterns, we propose a geometrically inspired framework to study such phenomena in artificial neural networks. To this end, we introduce \emph{CantorNet}, inspired by the triadic construction of the Cantor set, which was introduced by Georg Cantor in the $19^\text{th}$ century. In mathematics, the Cantor set is a set of points lying on a single line that is self-similar and has a counter intuitive property of being an uncountably infinite null set. Similarly, we introduce CantorNet as a sandbox for studying self-similarity by means of novel topological and geometrical complexity measures. CantorNet constitutes a family of ReLU neural networks that spans the whole spectrum of possible Kolmogorov complexities, including the two opposite descriptions (linear and exponential as measured by the description length). CantorNet's decision boundaries can be arbitrarily ragged, yet are analytically known. Besides serving as a testing ground for complexity measures, our work may serve to illustrate potential pitfalls in geometry-ignorant data augmentation techniques and adversarial attacks.

Figures

Figures reproduced from arXiv: 2411.19713 by the authors.

Figure 1
Figure 1. Left: The first iteration of the 1-1 correspondence between the ReLU net [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Activation patterns πi induced by Eq. (5). We skip neurons with unchanged values. model ( [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. The greyed regions can be represented as a 0-preimage of [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: represents the partition of the decision manifold given by Eq. (3) into convex polytopes for k = 2 and k = 3, respectively. We utilize the minimum function to form their union, obtaining a ReLU network N (k) B that yields the same decision manifold as the recursion-bas…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 19 canonical work pages

  1. [1]

    Video segmentation through multiscale texture analysis

    Miguel Alemán-Flores and Luis Álvarez León. Video segmentation through multiscale texture analysis. In Image Analysis and Recognition, ICIAR 2004, Lecture Notes in Computer Science, volume 3212, pages 339--346. Springer, Berlin, Heidelberg, 2004

    work page 2004

  2. [2]

    Understanding Deep Neural Networks with Rectified Linear Units

    Raman Arora , Amitabh Basu , Poorya Mianjy , and Anirbit Mukherjee . Understanding Deep Neural Networks with Rectified Linear Units . ICLR, 2018

    work page 2018

  3. [3]

    On the complexity of neural network classifiers: A comparison between shallow and deep architectures

    Monica Bianchini and Franco Scarselli. On the complexity of neural network classifiers: A comparison between shallow and deep architectures. IEEE Trans. NN Learn. Syst. , 25 0 (8): 0 1553--1565, 2014

    work page 2014

  4. [4]

    Ueber unendliche, lineare punktmannichfaltigkeiten

    Georg Cantor. Ueber unendliche, lineare punktmannichfaltigkeiten. Mathematische Annalen, 15 0 (1): 0 1--7, 1879

    work page

  5. [5]

    Visualizing music and audio using self-similarity

    Jonathan Foote. Visualizing music and audio using self-similarity. In Proceedings of the Seventh ACM International Conference on Multimedia (Part 1), pages 77--80, 1999. doi:10.1145/319463.319472

    arXiv 1999

  6. [6]

    Adversarial spheres

    Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S Schoenholz, Maithra Raghu, Martin Wattenberg, and Ian Goodfellow. Adversarial spheres. arXiv preprint arXiv:1801.02774, 2018

    arXiv 2018

  7. [7]

    Grünwald, Jay Injae Myung, and Mark A

    Peter D. Grünwald, Jay Injae Myung, and Mark A. Pitt, editors. Advances in Minimum Description Length: Theory and Applications. Neural Information Processing. MIT Press, Cambridge, MA, 2005. ISBN 9780262072625

    work page 2005

  8. [8]

    Klir and Bo Yuan

    George J. Klir and Bo Yuan. Fuzzy Sets and Fuzzy Logic: Theory and Applications. Prentice Hall, Upper Saddle River, NJ, USA, 1995. ISBN 9780131011717

    work page 1995

Show all 23 references
  1. [9]

    Three approaches to the quantitative definition of information

    Andrey N Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission, 1 0 (1): 0 1--7, 1965

    1965

  2. [10]

    Imagenet classification with deep convolutional neural networks

    Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In NeurIPS, 2012

    2012

  3. [11]

    Maas, Awni Y

    Andrew L. Maas, Awni Y. Hannun, and Andrew Y. Ng. Rectifier nonlinearities improve neural network acoustic models. In ICML Workshop on Deep Learning for Audio, Speech and Language Processing, 2013

    2013

  4. [12]

    Mandelbrot

    Benoit B. Mandelbrot. The Fractal Geometry of Nature. Macmillan, 1983. ISBN 978-0-7167-1186-5

    1983

  5. [13]

    Mandelbrot

    Benoit B. Mandelbrot. Measures of fractal lacunarity: Minkowski content and alternatives. In Fractal Geometry and Stochastics, Progress in Probability, pages 15--42, Basel, 1995. Birkh \"a user Basel

    1995

  6. [14]

    Perceptrons: An Introduction to Computational Geometry

    Marvin Minsky and Seymour Papert. Perceptrons: An Introduction to Computational Geometry. MIT Press, 1969

    1969

  7. [15]

    On the number of linear regions of deep neural networks

    Guido F Mont \'u far, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In NeurIPS, volume 27, 2014

    2014

  8. [16]

    Moser, Michal Lewandowski, Somayeh Kargaran, Werner Zellinger, Battista Biggio, and Christoph Koutschan

    Bernhard A. Moser, Michal Lewandowski, Somayeh Kargaran, Werner Zellinger, Battista Biggio, and Christoph Koutschan. Tessellation-filtering relu neural networks. IJCAI, 2022

    2022

  9. [17]

    Discovering neural nets with low kolmogorov complexity and high generalization capability

    J \"u rgen Schmidhuber. Discovering neural nets with low kolmogorov complexity and high generalization capability. Neural Networks, 10 0 (5): 0 857--873, 1997

    1997

  10. [18]

    Relu code space: A basis for rating network quality besides accuracy

    Natalia Shepeleva, Werner Zellinger, Michal Lewandowski, and Bernhard Moser. Relu code space: A basis for rating network quality besides accuracy. ICLR, NAS workshop, 2020

    2020

  11. [19]

    A formal theory of inductive inference

    Ray J Solomonoff. A formal theory of inductive inference. part i. Information and Control, 7 0 (1): 0 1--22, 1964

    1964

  12. [20]

    R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018

    2018

  13. [21]

    Sur une courbe continue sans tangente, obtenue par une construction géométrique élémentaire

    Helge von Koch. Sur une courbe continue sans tangente, obtenue par une construction géométrique élémentaire. Arkiv för matematik, astronomi och fysik, 1: 0 681--704, 1904

    1904

  14. [22]

    A survey on face data augmentation for the training of deep neural networks

    Xiang Wang, Kai Wang, and Shiguo Lian. A survey on face data augmentation for the training of deep neural networks. Neural Computing and Applications, 32 0 (19): 0 15503--15531, Oct 2020. ISSN 1433-3058. doi:10.1007/s00521-020-04748-3

    2020 doi

  15. [23]

    Entropy of fractal systems

    Oldrich Zmeskal, Petr Dzik, and Michal Vesely. Entropy of fractal systems. Computers & Mathematics with Applications, 66 0 (2): 0 135--146, 2013. ISSN 0898-1221

    2013

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.