Hypercubes, Hyperplanes, and Constraint-Induced Complexity Collapse in Atomic Concept Learning

# Hypercubes, Hyperplanes, and Constraint-Induced Complexity Collapse in Atomic Concept Learning
Source: [https://arxiv.org/html/2608.02930](https://arxiv.org/html/2608.02930)
11institutetext:National University, San Diego, United States
11email:itsapara@nu\.edu###### Abstract

We revisit higher\-arity atomic concept learning through the geometry of hypercubes and hyperplanes of ground instances\. Our starting point is the observation that the ambientrr\-dimensional hypercube of ground atoms is not structurally uniform\. Its logical complexity is organised by hyperplanes: every hyperplane other than the full diagonal collapses into finitely many elementary\-equivalence classes, with a bound independent of the term depth, while the full diagonal is exceptional and its class count grows without bound\. This asymmetry is not merely geometric; it reflects the reduction\-theoretic structure of the concepts themselves\.

Building on a higher\-dimensional framework developed in the author’s earlier work, we reinterpret these results through canonical simple concepts, minimal orderings, and representative reductions\. This yields a taxonomy of hyperplane behaviour in higher dimensions and shows that complexity is localised rather than spread uniformly through the instance space\. The paper includes a fully worked binary case, an explicit treatment of the ternary hypercube, and an unpacked account of the reduction machinery that drives the collapse\. The three\-dimensional case already exhibits the essential phenomenon: orthogonal families, partial diagonals, and the exceptional full diagonal\. This geometric\-logical perspective clarifies where complexity is concentrated in atomic concept learning and suggests a modern interpretation in terms of constrained hypothesis spaces and structured classification\.

## 1Introduction

The learnability of logical concept classes depends not only on the size of the ambient instance space, but also on its internal structure\[[10](https://arxiv.org/html/2608.02930#bib.bib10),[9](https://arxiv.org/html/2608.02930#bib.bib9)\]\. Earlier work on exact learning and on atomic formulas with prescribed first\-order properties showed that logical restrictions can sharply reduce learning complexity\[[1](https://arxiv.org/html/2608.02930#bib.bib1),[9](https://arxiv.org/html/2608.02930#bib.bib9)\]\. In this paper we revisit that phenomenon geometrically, and we focus on the higher\-arity setting developed in the author’s doctoral thesis\[[10](https://arxiv.org/html/2608.02930#bib.bib10)\], henceforth cited simply as*the thesis*\.

Our starting point is the hypercube of ground instances generated by bounded\-depth terms\. For anrr\-ary predicate, this yields a discreterr\-dimensional space whose points represent ground atoms\[[10](https://arxiv.org/html/2608.02930#bib.bib10)\]\. The key observation is that this space is structurally inhomogeneous\. Complexity is not distributed uniformly across the hypercube\. Most hyperplanes collapse into a bounded number of elementary\-equivalence classes, while the full diagonal remains exceptional\.

#### What “finitely many” means here\.

One point deserves emphasis at the outset, because without it the main theorem can be misread\. For a fixed term depthnn, the hypercubeℋr,n\\mathcal\{H\}\_\{r,n\}is a finite set, so every family of concepts over it is trivially finite\. The content of the classification is therefore a statement that is*uniform innn*: on every hyperplane except the full diagonal, the number of elementary\-equivalence classes is bounded by a constant that does not depend onnn\. On the full diagonal no such uniform bound exists, and the number of classes grows without bound asnnincreases\. Throughout the paper, “finitely many” should be read in this uniform sense\. The geometric picture we develop is the reason such a bound exists off the diagonal and fails on it\.

#### Roadmap\.

Section[2](https://arxiv.org/html/2608.02930#S2)builds the geometric picture informally, with no formal machinery, starting from the binary lattice of ground atoms\. Section[3](https://arxiv.org/html/2608.02930#S3)fixes definitions\. Section[4](https://arxiv.org/html/2608.02930#S4)works the binary case out completely; a reader who follows only that section will already have the essential idea, since every concept there is a quadrant, a ray, or a point, and the diagonal is visibly the odd one out\. Section[5](https://arxiv.org/html/2608.02930#S5)explains the reduction machinery that converts this geometry into a statement about elementary equivalence\. Section[6](https://arxiv.org/html/2608.02930#S6)states and proves the classification theorem, Section[7](https://arxiv.org/html/2608.02930#S7)works the ternary case, and Section[8](https://arxiv.org/html/2608.02930#S8)isolates why the diagonal resists the argument\. Sections[9](https://arxiv.org/html/2608.02930#S9)–[10](https://arxiv.org/html/2608.02930#S10)give the monolithic and learning\-theoretic readings\.

#### Why the asymmetry matters\.

The split between regular and exceptional regions matters for two reasons\. First, it identifies where the logical complexity of atomic concept learning actually resides\. Second, it suggests a learning\-theoretic interpretation: structural constraints do not merely regularise globally, but collapse large regions of the hypothesis space while leaving a small set of highly interactive regions as the principal source of complexity\.

The contribution of this paper is therefore a structural reading of higher\-arity atomic concept learning\. We recover the hypercube and hyperplane framework, make the diagonal exceptionalism explicit, and reinterpret the resulting collapse in a way that connects to contemporary discussions of inductive bias and constrained classification\.

## 2The Geometric Picture, Informally

Before any definitions, it is worth seeing what the objects look like\. Everything in this paper takes place in a space built from one constantaaand one unary function symbolff\. Iteratingffonaaproduces the ground terms

a,f​\(a\),f​\(f​\(a\)\),…,fn​\(a\),a,\\quad f\(a\),\\quad f\(f\(a\)\),\\quad\\dots,\\quad f^\{n\}\(a\),so a ground term of depth at mostnnis completely described by a single number: how many timesffhas been applied\. The term space is a line ofn\+1n\+1points, indexed0,1,…,n0,1,\\dots,n\.

Now take a binary predicatePP\. A ground atomP​\(fi​\(a\),fj​\(a\)\)P\(f^\{i\}\(a\),f^\{j\}\(a\)\)is determined by the pair\(i,j\)\(i,j\), so the set of all ground atoms is a square lattice\. This is the picture in Figure[1](https://arxiv.org/html/2608.02930#S2.F1): the horizontal coordinate records the depth of the first argument, the vertical coordinate the depth of the second, and the highlighted linei=ji=jis the diagonal that will turn out to be exceptional\.

![Refer to caption](https://arxiv.org/html/2608.02930v1/figure1_2d_lattice.png)Figure 1:The binary case\. Each lattice point is a ground atomP​\(fi​\(a\),fj​\(a\)\)P\(f^\{i\}\(a\),f^\{j\}\(a\)\); the coordinates are the depths of the two arguments\. The highlighted line is the diagonali=ji=j\.A lattice point is not a featureless location\. Zooming in on one, as in Figure[2](https://arxiv.org/html/2608.02930#S2.F2), shows that it is a tuple of structured terms: the point\(i,j\)\(i,j\)carries the pair\(fi​\(a\),fj​\(a\)\)\\bigl\(f^\{i\}\(a\),\\,f^\{j\}\(a\)\\bigr\), and each coordinate is itself an element of the term space\. This is the observation that later becomes the*monolithic*reading of the hypercube in Section[9](https://arxiv.org/html/2608.02930#S9)\. First\-order constraints act across these structured coordinates, not merely on the lattice positions\.

![Refer to caption](https://arxiv.org/html/2608.02930v1/figure2_point_expansion.png)Figure 2:A point of the lattice, expanded\. The hypervertex\(i,j\)\(i,j\)is the pair of structured terms\(fi​\(a\),fj​\(a\)\)\\bigl\(f^\{i\}\(a\),f^\{j\}\(a\)\\bigr\), each drawn from the term spaceTnT\_\{n\}; the arrows in the term lattices denote application offf\.Raising the arity raises the dimension\. For a ternary predicate the ground atoms form a cube, shown in Figure[3](https://arxiv.org/html/2608.02930#S2.F3), and for anrr\-ary predicate anrr\-dimensional grid\. What changes in three dimensions is that coordinates can be identified*partially*: one can requirei=ji=jwhile leavingkkfree, which is not possible when there are only two coordinates\. The distinction between partial identification and total identification is invisible in the binary case and central in the general one\.

![Refer to caption](https://arxiv.org/html/2608.02930v1/figure3_3d_hypercube.png)Figure 3:The ternary hypercubeℋ3,n\\mathcal\{H\}\_\{3,n\}, with the partial diagonali=ji=j, the partial diagonalj=kj=k, and the full diagonali=j=ki=j=kindicated\.The claim this paper develops is that the grid is not uniform\. Slicing it by coordinate conditions produces families of concepts whose logical complexity depends sharply on which slice was taken, and exactly one slice, the full diagonal, behaves differently from all the others\.

## 3Preliminaries

### 3\.1Terms, atoms, and the hypercube

Letffbe a unary function symbol,aaa constant symbol, and let

Tn=\{a,f​\(a\),f2​\(a\),…,fn​\(a\)\}T\_\{n\}=\\\{a,f\(a\),f^\{2\}\(a\),\\dots,f^\{n\}\(a\)\\\}denote the set of ground terms of depth at mostnn\. We writefi​\(a\)f^\{i\}\(a\)for the element of depthiiand identifyTnT\_\{n\}with\{0,1,…,n\}\\\{0,1,\\dots,n\\\}whenever convenient\.

For anrr\-ary predicate symbolPP, define the ambient discrete space

ℋr,n=Tnr,\\mathcal\{H\}\_\{r,n\}=T\_\{n\}^\{\\,r\},the*hypercube of ground instances*\. Each point\(t1,…,tr\)∈ℋr,n\(t\_\{1\},\\dots,t\_\{r\}\)\\in\\mathcal\{H\}\_\{r,n\}represents the ground atomP​\(t1,…,tr\)P\(t\_\{1\},\\dots,t\_\{r\}\), and we use the coordinate notation\(i1,…,ir\)\(i\_\{1\},\\dots,i\_\{r\}\)for the corresponding depths\.

A*hypervertex*is a point ofℋr,n\\mathcal\{H\}\_\{r,n\}\.

### 3\.2Atomic formulas, subsumption, and concepts

###### Definition 1\(Atomic formulas and subsumption\)

A*term*over the present language is a variable, the constantaa, or an applicationf​\(s\)f\(s\)offfto a termss\. An*atomic formula*is an expressionP​\(s1,…,sr\)P\(s\_\{1\},\\dots,s\_\{r\}\)whose arguments are terms; it is a*ground atom*if no variable occurs in it\. An atomic formulaAA*subsumes*an atomic formulaBBif there is a substitutionθ\\theta, mapping variables to terms, withA​θ=BA\\theta=B\.

For example,P​\(f​\(x\),y\)P\(f\(x\),y\)subsumes the ground atomP​\(f​\(a\),f2​\(a\)\)P\(f\(a\),f^\{2\}\(a\)\)viaθ=\{x↦a,y↦f2​\(a\)\}\\theta=\\\{x\\mapsto a,\\ y\\mapsto f^\{2\}\(a\)\\\}\. It does*not*subsumeP​\(a,a\)P\(a,a\): substitution replaces variables by terms and can therefore only preserve or deepen the function structure of an argument, never remove the outerff\. This monotonicity is worth keeping in mind when reading the figures: every specialisation arrow in this paper increases \(or preserves\) term depth, and no arrow can decrease it\.

Given an atomic formulaA=P​\(s1,…,sr\)A=P\(s\_\{1\},\\dots,s\_\{r\}\), let

CA,n=\{P​\(t1,…,tr\)∈ℋr,n:A​subsumes​P​\(t1,…,tr\)\}C\_\{A,n\}=\\\{P\(t\_\{1\},\\dots,t\_\{r\}\)\\in\\mathcal\{H\}\_\{r,n\}\\;:\\;A\\text\{ subsumes \}P\(t\_\{1\},\\dots,t\_\{r\}\)\\\}be the*concept represented byAA*overℋr,n\\mathcal\{H\}\_\{r,n\}; that is, the set of ground atoms obtainable fromAAby substituting ground terms ofTnT\_\{n\}for its variables\. Letφ\\varphibe a first\-order sentence over the language containingPP\. We study the class of conceptsCA,nC\_\{A,n\}satisfyingφ\\varphi\.

### 3\.3Hyperplanes: orthogonal, diagonal, and the full diagonal

A natural temptation is to use “diagonal” for total coordinate coincidence only, and “non\-diagonal” for everything else\. That conflicts with the thesis, where diagonal hyperplanes occur at every dimension\. We therefore adopt the thesis vocabulary throughout and add one term for the exceptional case\.

###### Definition 2\(Hyperplanes\)

A*hyperplane*ofℋr,n\\mathcal\{H\}\_\{r,n\}is a subset determined by a coordinate condition\. It is

- •*orthogonal*if some coordinate is pinned to a fixed ground term, as ini1=pi\_\{1\}=p;
- •*diagonal*if some group of coordinates is required to be equal, as ini1=i2i\_\{1\}=i\_\{2\}, with the remaining coordinates free\.

A diagonal hyperplane is determined by a partition of the coordinate positions in which at least one block has size at least two\. The*full diagonal*

Δr=\{\(i,i,…,i\):i∈Tn\}\\Delta\_\{r\}=\\\{\(i,i,\\dots,i\)\\;:\\;i\\in T\_\{n\}\\\}is the diagonal hyperplane of the one\-block partition, in which allrrcoordinates coincide\.

Diagonal hyperplanes thus exist at every dimension: for a ternary predicate there are\(32\)=3\\binom\{3\}\{2\}=3diagonal hyperplanes of dimension two, namelyi=ji=j,i=ki=kandj=kj=k, alongside the orthogonal ones\. OnlyΔr\\Delta\_\{r\}identifies all coordinates at once\. The classification below distinguishesΔr\\Delta\_\{r\}from every other hyperplane, orthogonal or diagonal\.

### 3\.4Elementary equivalence and minimal reductions

###### Definition 3

Two conceptsCA,nC\_\{A,n\}andCB,nC\_\{B,n\}are*elementarily equivalent*if their associated relational structures satisfy the same first\-order sentences in the relevant language fragment\[[3](https://arxiv.org/html/2608.02930#bib.bib3)\]\.

###### Definition 4

A*minimal reduction*of a concept structure is a reduced representative preserving its elementary theory\. Two concepts with isomorphic minimal reductions are therefore elementarily equivalent\.

###### Example 1\(The mechanism in miniature\)

A standard fact of finite model theory illustrates both notions in the simplest structure this paper uses, the term chaina→f​\(a\)→⋯→fm​\(a\)a\\to f\(a\)\\to\\cdots\\to f^\{m\}\(a\)viewed as a finite successor structure\. Sentences of quantifier rankqqcannot distinguish two such chains once both have length at least2q2^\{q\}\[[3](https://arxiv.org/html/2608.02930#bib.bib3)\]: an Ehrenfeucht–Fraïssé argument shows that any two sufficiently long chains satisfy exactly the same sentences of rankqq, and are therefore elementarily equivalent relative to that fragment\. A minimal reduction, in this miniature setting, replaces any chain of length≥2q\\geq 2^\{q\}by one fixed representative of length2q2^\{q\}: the elementary theory \(relative to rankqq\) is preserved, and infinitely many chains collapse to one of boundedly many representatives, one per length below the threshold plus one for “long”\. The reductions used in the thesis operate on richer structures than bare chains, but the shape of the argument on hyperplanes other than the full diagonal is the same: beyond a bounded threshold determined byφ\\varphi, additional depth along a free coordinate direction is invisible, so it is discarded by the reduction\.

## 4The Binary Case, Worked in Full

Everything essential is already visible whenr=2r=2, and in that case the concepts can be listed exhaustively\. LetA=P​\(s1,s2\)A=P\(s\_\{1\},s\_\{2\}\)be an atomic formula\. Eachsms\_\{m\}is either a ground termfp​\(a\)f^\{p\}\(a\)or a termfp​\(x\)f^\{p\}\(x\)built on a variable, and there are at most two variables available\. Substitutingx↦fm​\(a\)x\\mapsto f^\{m\}\(a\)turnsfp​\(x\)f^\{p\}\(x\)intofp\+m​\(a\)f^\{p\+m\}\(a\), so a variable coordinate withppapplications offfsweeps out the depthsp,p\+1,p\+2,…p,p\+1,p\+2,\\dotsand never the depths belowpp\. This single fact determines the shape of every binary concept\.

#### The four shapes\.

Writing concepts as sets of coordinate pairs\(i,j\)\(i,j\)in\{0,…,n\}2\\\{0,\\dots,n\\\}^\{2\}:

1. 1\.Quadrants\.IfA=P​\(fp​\(x\),fq​\(y\)\)A=P\(f^\{p\}\(x\),f^\{q\}\(y\)\)withxxandyydistinct, then CA,n=\{\(i,j\):i≥p,j≥q\},C\_\{A,n\}=\\\{\(i,j\)\\;:\\;i\\geq p,\\ j\\geq q\\\},an axis\-parallel region anchored at\(p,q\)\(p,q\)\. The two coordinates move independently\.
2. 2\.Diagonal rays\.IfA=P​\(fp​\(x\),fq​\(x\)\)A=P\(f^\{p\}\(x\),f^\{q\}\(x\)\)with the*same*variable in both positions, then CA,n=\{\(p\+m,q\+m\):m≥0\},C\_\{A,n\}=\\\{\(p\+m,\\,q\+m\)\\;:\\;m\\geq 0\\\},a ray parallel to the main diagonal, offset by the fixed displacementq−pq\-p\. The two coordinates move in lockstep\.
3. 3\.Axis rays\.If exactly one argument is ground, sayA=P​\(fp​\(a\),fq​\(y\)\)A=P\(f^\{p\}\(a\),f^\{q\}\(y\)\), thenCA,n=\{\(p,j\):j≥q\}C\_\{A,n\}=\\\{\(p,j\):j\\geq q\\\}, a ray inside a single column\.
4. 4\.Points\.If both arguments are ground,CA,nC\_\{A,n\}is the single hypervertex\(p,q\)\(p,q\)\.

#### What the four shapes tell us\.

The taxonomy already separates the diagonal from everything else, and it does so for a reason that survives into higher arity\. Shapes 1, 3 and 4 are described by*independent*coordinate data: a lower bound onii, a lower bound onjj, or a fixed value for one of them\. Shape 2 is not\. A diagonal ray is described by a*relation between*the coordinates, the displacementq−pq\-p, and that relation is preserved by every application offf: advancing along the ray appliesffto both coordinates simultaneously and returns the displacement unchanged\.

That is precisely the difference the classification theorem turns on\. Off the diagonal, some coordinate direction remains free, and a minimal reduction can discard the depth information in that direction once it exceeds the finitely many thresholds that the constraintφ\\varphican detect; the reduced structures then fall into a bounded family\. On the diagonal, there is no free direction to discard, and the displacement is an invariant that distinguishes structures from one another without bound\. Asnngrows, the number of available displacements grows with it\.

Figure[4](https://arxiv.org/html/2608.02930#S4.F4)renders the contrast schematically, with the regular hyperplanes of Section[3\.3](https://arxiv.org/html/2608.02930#S3.SS3)on the left and the full diagonal on the right\.

![Refer to caption](https://arxiv.org/html/2608.02930v1/figure4_hyperplane_classification.png)Figure 4:Hyperplane classification\. Left: hyperplanes other than the full diagonal, whose induced concepts fall into a bounded number of structural classes\. Right: the full diagonal, whose class count is not bounded uniformly innn\.

## 5Reduction Machinery

The classification is not a purely geometric fact; the geometry is what makes a reduction\-theoretic argument go through\. This section sets out that argument in outline, so that the theorem of Section[6](https://arxiv.org/html/2608.02930#S6)does not have to be taken on trust\.

The machinery has three layers\. The first is a notion of structure\-preserving map between concept structures strong enough to preserve first\-order theories\. Strong homomorphisms preserve the relation and its complement; a*reductive*homomorphism is a strong homomorphism onto a smaller structure that in addition respects the term structure of the coordinates\. The basic fact is that reductive homomorphisms are elementary: a concept and its image satisfy the same sentences\. Consequently, if two concepts admit a common reduction, they are elementarily equivalent\.

The second layer makes the reduction canonical\. To each concept one attaches a hypergraph recording which coordinate patterns are realised in it, and among all reductions of that hypergraph there is a minimal one, unique up to isomorphism\. This minimal reductive hypergraph is the*canonical concept*\. The pivotal consequence is that the elementary\-equivalence classes are exactly the classes of concepts sharing a canonical concept, which converts a question about first\-order theories into a question about a finite combinatorial invariant\.

The third layer is a counting argument on those invariants\. Once elementary equivalence has been reduced to isomorphism of canonical concepts, bounding the number of classes on a region amounts to bounding the number of canonical concepts realisable there\. This is where the geometry does its work: what a hyperplane fixes about the coordinates determines how much of the term structure survives reduction, and therefore how many canonical concepts are available\.

## 6Hyperplane Classification

###### Theorem 6\.1\(Hyperplane Classification\)

Letℋr,n=Tnr\\mathcal\{H\}\_\{r,n\}=T\_\{n\}^\{\\,r\}be the hypercube of ground instances generated by one unary function symbolff, one constant symbolaa, and anrr\-ary predicate symbolPP, with terms of depth at mostnn\. Letφ\\varphibe a first\-order sentence over the language containingPP\.

Then for every hyperplaneH≠ΔrH\\neq\\Delta\_\{r\}ofℋr,n\\mathcal\{H\}\_\{r,n\}, the concepts induced onHHfall into at mostN​\(r\)N\(r\)elementary\-equivalence classes, whereN​\(r\)N\(r\)depends only onrrand onφ\\varphiand not onnn\. On the full diagonalΔr\\Delta\_\{r\}no such uniform bound exists: the number of elementary\-equivalence classes grows without bound asnnincreases\.

#### Shape of the argument\.

The proof has three steps\. Step 1 partitions the hypercube into hyperplanes and records what each one fixes about the coordinates\. Step 2 shows that when at least one coordinate direction survives unidentified, minimal reductions stabilise, giving a bound independent ofnn\. Step 3 shows that onΔr\\Delta\_\{r\}the stabilisation fails, because the identification of all coordinates leaves an unbounded invariant behind\.

###### Proof\(Proof sketch\)

*Step 1: stratification\.*The ambient hypercube is stratified by hyperplanes determined by coordinate equalities and by pinned coordinate values\. Each hyperplane fixes some coordinate information and leaves the rest free\. The binary case of Section[4](https://arxiv.org/html/2608.02930#S4)provides the base classification, in which the diagonal already appears as the unique exceptional region\.

*Step 2: stabilisation off the full diagonal\.*LetH≠ΔrH\\neq\\Delta\_\{r\}\. Then either some coordinate is pinned, or the identifying partition has at least two blocks, so at least one coordinate direction remains independent of the others\. The role of minimal reduction is to remove redundant structure while preserving the elementary theory of the concept\. Along an independent direction, depth information beyond the finitely many thresholds detectable byφ\\varphiis redundant and is discarded by the reduction, exactly as in Example[1](https://arxiv.org/html/2608.02930#Thmexample1): once the free coordinate exceeds every depth threshold expressible atφ\\varphi’s quantifier rank, a further application offfyields a structure indistinguishable from one already produced, so it reproduces one of finitely many reduced configurations rather than a new one\. The induced structures admit minimal reductions in which coordinate interactions remain separated, these reductions stabilise into a bounded family of canonical concepts, and by the correspondence of Section[5](https://arxiv.org/html/2608.02930#S5)the induced concepts fall into a bounded number of elementary\-equivalence classes\. The bound depends onrrandφ\\varphialone\.

*Step 3: failure on the full diagonal\.*OnΔr\\Delta\_\{r\}all coordinates coincide, so no independent direction remains\. Applyingffadvances every coordinate simultaneously and preserves the relative displacement pattern, which is therefore an invariant of the structure that the reduction cannot discard\. Distinct displacement patterns yield non\-isomorphic canonical concepts, and the number of available patterns grows withnn\. One obtains an unbounded sequence of pairwise non\-equivalent reduced structures, so no bound uniform innncan hold\. ∎

###### Corollary 1

Logical complexity inℋr,n\\mathcal\{H\}\_\{r,n\}is localised: every hyperplane other thanΔr\\Delta\_\{r\}is structurally regular, andΔr\\Delta\_\{r\}concentrates the exceptional behaviour\.

#### Scope\.

The theorem is stated in the thesis setting of one unary function symbol, one constant symbol, bounded term depth, and classification up to elementary equivalence\. The purpose of the present paper is to isolate the geometric consequence of that analysis rather than to claim a more general result\.

#### Beyond one unary function symbol\.

The restriction is not cosmetic, and it is worth stating exactly what depends on it\. With a single unaryff, the ground terms form a chain, so a ground atom is a tuple of natural numbers and the hypercube is a grid; the entire geometric reading rests on this\. Withkkunary function symbols the term space becomes a finitely branching tree, and the hypercube a product of trees: hyperplanes can still be defined by coordinate equalities, but a diagonal now identifies*paths*rather than depths, and the displacement invariant of Section[4](https://arxiv.org/html/2608.02930#S4)is replaced by a richer word\-valued invariant\. With function symbols of arity two or more, terms are trees and the coordinate reading of a ground atom is lost altogether\. Whether the localisation of complexity survives in either setting — and in particular whether some analogue of the full diagonal remains the unique exceptional region — is open, and we regard it as the natural next question raised by this work\.

## 7The Ternary Case

The ternary hypercube is the first setting in which the distinction that drives the theorem becomes visible, because it is the first in which coordinates can be identified partially\. Inℋ2,n\\mathcal\{H\}\_\{2,n\}there are only two coordinates, so identifying any two identifies all; inℋ3,n\\mathcal\{H\}\_\{3,n\}the conditionsi=ji=jandi=j=ki=j=kare genuinely different\.

Consider the hyperplanei=ji=jinℋ3,n\\mathcal\{H\}\_\{3,n\}\. It is a diagonal hyperplane of partial type: two coordinates are locked together, butkkis free\. The induced concepts therefore retain an independent direction, Step 2 of the proof applies, and their reductions stabilise into a bounded family\. Contrast the full diagonali=j=ki=j=k, where every coordinate is locked to every other and Step 2 has nothing to work with\.

The geometry makes the relationship clear: the planei=ji=jis itself a two\-dimensional grid, with coordinates the shared valueiiand the free valuekk, and inside it the linei=j=ki=j=kappears as its own main diagonal\. The classification is thus recursive in a natural sense\. A partial diagonal is a lower\-dimensional copy of the same picture, regular except along its own diagonal\.

## 8Why the Diagonal Is Exceptional

The diagonal case differs because coordinate independence is lost\. When all relevant coordinates coincide, substitutions and applications of the unary function feed back into the same coordinate pattern\. This creates a recursive self\-interaction that is not present elsewhere in the hypercube, and it is worth being precise about why the reduction machinery cannot absorb it\.

Off the diagonal, the reduction discards depth information along a free direction\. It can do so because that information is invisible toφ\\varphibeyond a bounded threshold: two structures agreeing up to the threshold agree on all sentencesφ\\varphican express, so their canonical concepts coincide\. The bound on the number of classes is then a bound on the number of threshold configurations, which depends onrrandφ\\varphibut not on how deep the terms are allowed to go\.

On the diagonal there is no free direction, and the surviving invariant is relational rather than positional\. The binary case of Section[4](https://arxiv.org/html/2608.02930#S4)shows the phenomenon concretely: a diagonal ray generated byP​\(fp​\(x\),fq​\(x\)\)P\(f^\{p\}\(x\),f^\{q\}\(x\)\)carries the displacementq−pq\-p, and applyingff\(that is, substitutingx↦f​\(x\)x\\mapsto f\(x\)\) advances both coordinates together, returning the displacement unchanged — this is what “substitutions feed back into the same coordinate pattern” means\. Two rays of different displacement are not carried onto one another by any reduction, since the displacement is definable from the structure; and the number of realisable displacements grows withnn\. Reduction cannot discard the invariant without changing the elementary theory\. The reduction process therefore need not terminate in a bounded family of elementary types, and the diagonal is the natural location of persistent complexity in the hypercube\.

## 9A Monolithic Interpretation

We use the term*monolithic*to emphasise that the hypercubeℋr,n=Tnr\\mathcal\{H\}\_\{r,n\}=T\_\{n\}^\{\\,r\}is not merely a flat Cartesian grid\. Each coordinate belongs to the structured term spaceTnT\_\{n\}, so each point is itself assembled from structured components, as Figure[2](https://arxiv.org/html/2608.02930#S2.F2)showed\. The ambient space is a product of structured term spaces, and first\-order constraints act across these layers simultaneously\.

Figure[5](https://arxiv.org/html/2608.02930#S9.F5)shows the effect at the level of formulas rather than points\. Starting from an atomic formula, substitution generates a hierarchy of specialisations, each a separate node, with arrows recording which substitution produced which\. The hierarchy is the syntactic counterpart of the geometric nesting seen in Section[7](https://arxiv.org/html/2608.02930#S7): specialising a formula moves to a lower\-dimensional region of the hypercube, and identifying two variables moves onto a diagonal\.

![Refer to caption](https://arxiv.org/html/2608.02930v1/figure6_monolith.png)Figure 5:Monolith generated fromP​\(f2​\(x\),f2​\(y\)\)P\(f^\{2\}\(x\),f^\{2\}\(y\)\)\. Every arrow is a specialisation by the substitution written on it, so along every arrow term depth is preserved or increased, as required by the definition of subsumption; identifying the two variables \(x,y↦zx,y\\mapsto z\) moves onto a diagonal hyperplane, while instantiating a variable by a ground term moves onto an orthogonal one\. The nodeP​\(f2​\(a\),f2​\(a\)\)P\(f^\{2\}\(a\),f^\{2\}\(a\)\)is reached along several routes, one from each of its subsuming formulas\.In this view the classification theorem says that first\-order constraints collapse most of the ambient space into a bounded number of structural types, with the full diagonal remaining the unique source of persistent complexity\[[10](https://arxiv.org/html/2608.02930#bib.bib10)\]\.

## 10A Learning\-Theoretic Reading

###### Proposition 1\(Learning\-Theoretic Interpretation\)

The hyperplane classification theorem suggests that, away from the full diagonal, the effective hypothesis space is controlled by a bounded number of structural classes, whereas the diagonal retains higher expressive complexity\.

###### Proof\(Interpretive proof sketch\)

By the Hyperplane Classification Theorem, regions other thanΔr\\Delta\_\{r\}admit only a bounded number of elementary\-equivalence classes\. A learner that distinguishes concepts only up to elementary equivalence therefore encounters a collapsed hypothesis space in those regions, and the collapse does not degrade as the term depth grows\.

The diagonal region does not admit such a bound, since its class count grows withnn\. The effective classification complexity is therefore asymmetrically distributed: bounded on regular hyperplanes and unbounded on the diagonal\. ∎

![Refer to caption](https://arxiv.org/html/2608.02930v1/figure5_neural_bridge.png)Figure 6:Constraint\-induced collapse of the effective hypothesis space under first\-order constraints\.
## 11Related Work

Classical work on inductive generalisation established the logical background for structured concept learning\. Plotkin’s notes on inductive generalisation and his thesis introduced least general generalisation and the subsumption ordering on atomic formulas\[[6](https://arxiv.org/html/2608.02930#bib.bib6),[7](https://arxiv.org/html/2608.02930#bib.bib7),[8](https://arxiv.org/html/2608.02930#bib.bib8)\], and Angluin’s query model supplied the learning\-theoretic setting\[[1](https://arxiv.org/html/2608.02930#bib.bib1)\]\. The thesis and the subsequent COLT paper belong to this line, showing that structural restrictions can make atomic formulas learnable\[[10](https://arxiv.org/html/2608.02930#bib.bib10),[9](https://arxiv.org/html/2608.02930#bib.bib9)\]\. Finite model theory supplies the notion of elementary equivalence and the classification techniques used here\[[3](https://arxiv.org/html/2608.02930#bib.bib3)\]\.

The present paper reinterprets that earlier theory geometrically, and the resulting picture has a counterpart in contemporary machine learning, where structural constraints are also used to shrink an effective hypothesis space rather than to regularise it uniformly\. Equivariant architectures build symmetry directly into the model class\[[2](https://arxiv.org/html/2608.02930#bib.bib2)\]; permutation\-invariant architectures do the same for set\-structured inputs\[[12](https://arxiv.org/html/2608.02930#bib.bib12)\]; higher\-order graph networks calibrate expressive power against a combinatorial hierarchy\[[5](https://arxiv.org/html/2608.02930#bib.bib5)\]; and semantic loss functions inject logical constraints into training\[[11](https://arxiv.org/html/2608.02930#bib.bib11)\]\. What the present analysis adds is a setting in which the collapse induced by a constraint can be located exactly, and in which the residual complexity is confined to an identifiable region\.

#### Relation to earlier work\.

The higher\-arity structural ingredients of this paper originate in the thesis, including the hypercube and hyperplane framework, minimal reductions, and the exceptional role of the diagonal\. What is new here is the unified geometric presentation, the explicit complexity\-localisation viewpoint, and the learning\-theoretic interpretation of the resulting structural collapse\[[10](https://arxiv.org/html/2608.02930#bib.bib10),[9](https://arxiv.org/html/2608.02930#bib.bib9)\]\.

## 12Future Work

Future work will connect the hyperplane classification developed here to neural classification and to explicit upper\-bound learning algorithms\. The main hypothesis is that first\-order or symmetry constraints collapse the effective hypothesis space on regular regions, while diagonal regions remain the primary source of expressive complexity\. This suggests architectures that do not treat all regions of the feature space uniformly: constrained or lower\-capacity components may suffice off the diagonal, while diagonal regions may require richer representations for higher\-order feature interactions\.

A corresponding upper\-bound algorithm would first decompose the instance space into hyperplanes, classify regular regions using representatives of their boundedly many elementary\-equivalence classes, and treat the diagonal separately as the exceptional high\-complexity component\. Such a decomposition would make the connection between logical and neural classification more precise, by allowing a neural model to approximate the same division between regular and exceptional regions\. The broader goal is to test whether bounded structural collapse off the diagonal yields measurable gains in sample efficiency, parameter reduction, and generalisation\.

## 13Conclusion

This paper revisits higher\-arity atomic concept learning through the geometry of hypercubes and hyperplanes of ground instances\. The main conclusion is that complexity is not uniformly distributed across the hypercube: every hyperplane other than the full diagonal collapses into boundedly many elementary\-equivalence classes, with a bound independent of the term depth, while the full diagonal is exceptional and its class count grows without bound\. The binary case makes the mechanism visible in four concept shapes, of which only the diagonal rays are described by a relation between coordinates rather than by independent coordinate data\. The ternary case shows that the picture is recursive, with each partial diagonal a lower\-dimensional copy of the same phenomenon\. Off the diagonal, coordinate separation lets minimal reductions discard depth information and stabilise; on the diagonal, coordinates coincide, a displacement invariant survives every reduction, and complexity persists\. The paper therefore recovers the higher\-arity learnability framework in geometric form and gives it a logic\-first interpretation as constraint\-induced structural collapse\.

## References

- \[1\]Angluin, D\.: Queries and Concept Learning\. Mach\. Learn\. 2\(4\), 319–342 \(1988\)
- \[2\]Cohen, T\.S\., Welling, M\.: Group Equivariant Convolutional Networks\. In: Proceedings of the 33rd International Conference on Machine Learning, pp\. 2990–2999 \(2016\)
- \[3\]Ebbinghaus, H\.\-D\., Flum, J\.:*Finite Model Theory*\. Springer \(1995\)
- \[4\]Elgueta, R\.: Subdirect representation theory for classes without equalities\. \(1997\)
- \[5\]Morris, C\., Ritzert, M\., Fey, M\., Hamilton, W\.L\., Lenssen, J\.E\., Rattan, G\., Grohe, M\.: Weisfeiler and Leman Go Neural: Higher\-Order Graph Neural Networks\. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol\. 33, pp\. 4602–4609 \(2019\)
- \[6\]Plotkin, G\.D\.: A Note on Inductive Generalization\. In: Meltzer, B\., Michie, D\. \(eds\.\)*Machine Intelligence 5*, pp\. 153–163\. Edinburgh University Press \(1970\)
- \[7\]Plotkin, G\.D\.: A Further Note on Inductive Generalization\. In: Meltzer, B\., Michie, D\. \(eds\.\)*Machine Intelligence 6*, pp\. 101–124\. Edinburgh University Press \(1971\)
- \[8\]Plotkin, G\.D\.:*Automatic Methods of Inductive Inference*\. PhD thesis, University of Edinburgh \(1972\)
- \[9\]Tsapara, I\., Turán, Gy\.: On the Learnability of Atomic Formulas\. In: Proceedings of COLT \(1998\)
- \[10\]Tsapara\-Vassiliades, I\.:*On Learnability of Atomic Formulas*\. PhD thesis, University of Illinois at Chicago \(1997\)
- \[11\]Xu, J\., Zhang, Z\., Friedman, T\., Liang, Y\., Van den Broeck, G\.: A Semantic Loss Function for Deep Learning with Symbolic Knowledge\. In: Proceedings of the 35th International Conference on Machine Learning, pp\. 5502–5511 \(2018\)
- \[12\]Zaheer, M\., Kottur, S\., Ravanbakhsh, S\., Póczos, B\., Salakhutdinov, R\., Smola, A\.: Deep Sets\. In: Advances in Neural Information Processing Systems 30 \(2017\)